1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
3 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012
4 Free Software Foundation, Inc.
5 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
6 Hacked by Michael Tiemann (tiemann@cygnus.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction reorganization pass.
26 This pass runs after register allocation and final jump
27 optimization. It should be the last pass to run before peephole.
28 It serves primarily to fill delay slots of insns, typically branch
29 and call insns. Other insns typically involve more complicated
30 interactions of data dependencies and resource constraints, and
31 are better handled by scheduling before register allocation (by the
32 function `schedule_insns').
34 The Branch Penalty is the number of extra cycles that are needed to
35 execute a branch insn. On an ideal machine, branches take a single
36 cycle, and the Branch Penalty is 0. Several RISC machines approach
37 branch delays differently:
39 The MIPS has a single branch delay slot. Most insns
40 (except other branches) can be used to fill this slot. When the
41 slot is filled, two insns execute in two cycles, reducing the
42 branch penalty to zero.
44 The SPARC always has a branch delay slot, but its effects can be
45 annulled when the branch is not taken. This means that failing to
46 find other sources of insns, we can hoist an insn from the branch
47 target that would only be safe to execute knowing that the branch
50 The HP-PA always has a branch delay slot. For unconditional branches
51 its effects can be annulled when the branch is taken. The effects
52 of the delay slot in a conditional branch can be nullified for forward
53 taken branches, or for untaken backward branches. This means
54 we can hoist insns from the fall-through path for forward branches or
55 steal insns from the target of backward branches.
57 The TMS320C3x and C4x have three branch delay slots. When the three
58 slots are filled, the branch penalty is zero. Most insns can fill the
59 delay slots except jump insns.
61 Three techniques for filling delay slots have been implemented so far:
63 (1) `fill_simple_delay_slots' is the simplest, most efficient way
64 to fill delay slots. This pass first looks for insns which come
65 from before the branch and which are safe to execute after the
66 branch. Then it searches after the insn requiring delay slots or,
67 in the case of a branch, for insns that are after the point at
68 which the branch merges into the fallthrough code, if such a point
69 exists. When such insns are found, the branch penalty decreases
70 and no code expansion takes place.
72 (2) `fill_eager_delay_slots' is more complicated: it is used for
73 scheduling conditional jumps, or for scheduling jumps which cannot
74 be filled using (1). A machine need not have annulled jumps to use
75 this strategy, but it helps (by keeping more options open).
76 `fill_eager_delay_slots' tries to guess the direction the branch
77 will go; if it guesses right 100% of the time, it can reduce the
78 branch penalty as much as `fill_simple_delay_slots' does. If it
79 guesses wrong 100% of the time, it might as well schedule nops. When
80 `fill_eager_delay_slots' takes insns from the fall-through path of
81 the jump, usually there is no code expansion; when it takes insns
82 from the branch target, there is code expansion if it is not the
83 only way to reach that target.
85 (3) `relax_delay_slots' uses a set of rules to simplify code that
86 has been reorganized by (1) and (2). It finds cases where
87 conditional test can be eliminated, jumps can be threaded, extra
88 insns can be eliminated, etc. It is the job of (1) and (2) to do a
89 good job of scheduling locally; `relax_delay_slots' takes care of
90 making the various individual schedules work well together. It is
91 especially tuned to handle the control flow interactions of branch
92 insns. It does nothing for insns with delay slots that do not
95 On machines that use CC0, we are very conservative. We will not make
96 a copy of an insn involving CC0 since we want to maintain a 1-1
97 correspondence between the insn that sets and uses CC0. The insns are
98 allowed to be separated by placing an insn that sets CC0 (but not an insn
99 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
100 delay slot. In that case, we point each insn at the other with REG_CC_USER
101 and REG_CC_SETTER notes. Note that these restrictions affect very few
102 machines because most RISC machines with delay slots will not use CC0
103 (the RT is the only known exception at this point). */
107 #include "coretypes.h"
109 #include "diagnostic-core.h"
113 #include "function.h"
114 #include "insn-config.h"
115 #include "conditions.h"
116 #include "hard-reg-set.h"
117 #include "basic-block.h"
122 #include "insn-attr.h"
123 #include "resource.h"
127 #include "tree-pass.h"
128 #include "emit-rtl.h"
132 #ifndef ANNUL_IFTRUE_SLOTS
133 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
135 #ifndef ANNUL_IFFALSE_SLOTS
136 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
139 /* Insns which have delay slots that have not yet been filled. */
141 static struct obstack unfilled_slots_obstack
;
142 static rtx
*unfilled_firstobj
;
144 /* Define macros to refer to the first and last slot containing unfilled
145 insns. These are used because the list may move and its address
146 should be recomputed at each use. */
148 #define unfilled_slots_base \
149 ((rtx *) obstack_base (&unfilled_slots_obstack))
151 #define unfilled_slots_next \
152 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
154 /* Points to the label before the end of the function, or before a
156 static rtx function_return_label
;
157 /* Likewise for a simple_return. */
158 static rtx function_simple_return_label
;
160 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
161 not always monotonically increase. */
162 static int *uid_to_ruid
;
164 /* Highest valid index in `uid_to_ruid'. */
167 static int stop_search_p (rtx
, int);
168 static int resource_conflicts_p (struct resources
*, struct resources
*);
169 static int insn_references_resource_p (rtx
, struct resources
*, bool);
170 static int insn_sets_resource_p (rtx
, struct resources
*, bool);
171 static rtx
find_end_label (rtx
);
172 static rtx
emit_delay_sequence (rtx
, rtx
, int);
173 static rtx
add_to_delay_list (rtx
, rtx
);
174 static rtx
delete_from_delay_slot (rtx
);
175 static void delete_scheduled_jump (rtx
);
176 static void note_delay_statistics (int, int);
177 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
178 static rtx
optimize_skip (rtx
);
180 static int get_jump_flags (rtx
, rtx
);
181 static int mostly_true_jump (rtx
);
182 static rtx
get_branch_condition (rtx
, rtx
);
183 static int condition_dominates_p (rtx
, rtx
);
184 static int redirect_with_delay_slots_safe_p (rtx
, rtx
, rtx
);
185 static int redirect_with_delay_list_safe_p (rtx
, rtx
, rtx
);
186 static int check_annul_list_true_false (int, rtx
);
187 static rtx
steal_delay_list_from_target (rtx
, rtx
, rtx
, rtx
,
191 int, int *, int *, rtx
*);
192 static rtx
steal_delay_list_from_fallthrough (rtx
, rtx
, rtx
, rtx
,
197 static void try_merge_delay_insns (rtx
, rtx
);
198 static rtx
redundant_insn (rtx
, rtx
, rtx
);
199 static int own_thread_p (rtx
, rtx
, int);
200 static void update_block (rtx
, rtx
);
201 static int reorg_redirect_jump (rtx
, rtx
);
202 static void update_reg_dead_notes (rtx
, rtx
);
203 static void fix_reg_dead_note (rtx
, rtx
);
204 static void update_reg_unused_notes (rtx
, rtx
);
205 static void fill_simple_delay_slots (int);
206 static rtx
fill_slots_from_thread (rtx
, rtx
, rtx
, rtx
,
209 static void fill_eager_delay_slots (void);
210 static void relax_delay_slots (rtx
);
211 static void make_return_insns (rtx
);
213 /* A wrapper around next_active_insn which takes care to return ret_rtx
217 first_active_target_insn (rtx insn
)
219 if (ANY_RETURN_P (insn
))
221 return next_active_insn (insn
);
224 /* Return true iff INSN is a simplejump, or any kind of return insn. */
227 simplejump_or_return_p (rtx insn
)
229 return (JUMP_P (insn
)
230 && (simplejump_p (insn
) || ANY_RETURN_P (PATTERN (insn
))));
233 /* Return TRUE if this insn should stop the search for insn to fill delay
234 slots. LABELS_P indicates that labels should terminate the search.
235 In all cases, jumps terminate the search. */
238 stop_search_p (rtx insn
, int labels_p
)
243 /* If the insn can throw an exception that is caught within the function,
244 it may effectively perform a jump from the viewpoint of the function.
245 Therefore act like for a jump. */
246 if (can_throw_internal (insn
))
249 switch (GET_CODE (insn
))
263 /* OK unless it contains a delay slot or is an `asm' insn of some type.
264 We don't know anything about these. */
265 return (GET_CODE (PATTERN (insn
)) == SEQUENCE
266 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
267 || asm_noperands (PATTERN (insn
)) >= 0);
274 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
275 resource set contains a volatile memory reference. Otherwise, return FALSE. */
278 resource_conflicts_p (struct resources
*res1
, struct resources
*res2
)
280 if ((res1
->cc
&& res2
->cc
) || (res1
->memory
&& res2
->memory
)
281 || (res1
->unch_memory
&& res2
->unch_memory
)
282 || res1
->volatil
|| res2
->volatil
)
285 return hard_reg_set_intersect_p (res1
->regs
, res2
->regs
);
288 /* Return TRUE if any resource marked in RES, a `struct resources', is
289 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
290 routine is using those resources.
292 We compute this by computing all the resources referenced by INSN and
293 seeing if this conflicts with RES. It might be faster to directly check
294 ourselves, and this is the way it used to work, but it means duplicating
295 a large block of complex code. */
298 insn_references_resource_p (rtx insn
, struct resources
*res
,
299 bool include_delayed_effects
)
301 struct resources insn_res
;
303 CLEAR_RESOURCE (&insn_res
);
304 mark_referenced_resources (insn
, &insn_res
, include_delayed_effects
);
305 return resource_conflicts_p (&insn_res
, res
);
308 /* Return TRUE if INSN modifies resources that are marked in RES.
309 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
310 included. CC0 is only modified if it is explicitly set; see comments
311 in front of mark_set_resources for details. */
314 insn_sets_resource_p (rtx insn
, struct resources
*res
,
315 bool include_delayed_effects
)
317 struct resources insn_sets
;
319 CLEAR_RESOURCE (&insn_sets
);
320 mark_set_resources (insn
, &insn_sets
, 0,
321 (include_delayed_effects
324 return resource_conflicts_p (&insn_sets
, res
);
327 /* Find a label at the end of the function or before a RETURN. If there
328 is none, try to make one. If that fails, returns 0.
330 The property of such a label is that it is placed just before the
331 epilogue or a bare RETURN insn, so that another bare RETURN can be
332 turned into a jump to the label unconditionally. In particular, the
333 label cannot be placed before a RETURN insn with a filled delay slot.
335 ??? There may be a problem with the current implementation. Suppose
336 we start with a bare RETURN insn and call find_end_label. It may set
337 function_return_label just before the RETURN. Suppose the machinery
338 is able to fill the delay slot of the RETURN insn afterwards. Then
339 function_return_label is no longer valid according to the property
340 described above and find_end_label will still return it unmodified.
341 Note that this is probably mitigated by the following observation:
342 once function_return_label is made, it is very likely the target of
343 a jump, so filling the delay slot of the RETURN will be much more
345 KIND is either simple_return_rtx or ret_rtx, indicating which type of
346 return we're looking for. */
349 find_end_label (rtx kind
)
355 plabel
= &function_return_label
;
358 gcc_assert (kind
== simple_return_rtx
);
359 plabel
= &function_simple_return_label
;
362 /* If we found one previously, return it. */
366 /* Otherwise, see if there is a label at the end of the function. If there
367 is, it must be that RETURN insns aren't needed, so that is our return
368 label and we don't have to do anything else. */
370 insn
= get_last_insn ();
372 || (NONJUMP_INSN_P (insn
)
373 && (GET_CODE (PATTERN (insn
)) == USE
374 || GET_CODE (PATTERN (insn
)) == CLOBBER
)))
375 insn
= PREV_INSN (insn
);
377 /* When a target threads its epilogue we might already have a
378 suitable return insn. If so put a label before it for the
379 function_return_label. */
381 && JUMP_P (PREV_INSN (insn
))
382 && PATTERN (PREV_INSN (insn
)) == kind
)
384 rtx temp
= PREV_INSN (PREV_INSN (insn
));
385 rtx label
= gen_label_rtx ();
386 LABEL_NUSES (label
) = 0;
388 /* Put the label before any USE insns that may precede the RETURN
390 while (GET_CODE (temp
) == USE
)
391 temp
= PREV_INSN (temp
);
393 emit_label_after (label
, temp
);
397 else if (LABEL_P (insn
))
401 rtx label
= gen_label_rtx ();
402 LABEL_NUSES (label
) = 0;
403 /* If the basic block reorder pass moves the return insn to
404 some other place try to locate it again and put our
405 function_return_label there. */
406 while (insn
&& ! (JUMP_P (insn
) && (PATTERN (insn
) == kind
)))
407 insn
= PREV_INSN (insn
);
410 insn
= PREV_INSN (insn
);
412 /* Put the label before any USE insns that may precede the
414 while (GET_CODE (insn
) == USE
)
415 insn
= PREV_INSN (insn
);
417 emit_label_after (label
, insn
);
427 /* The RETURN insn has its delay slot filled so we cannot
428 emit the label just before it. Since we already have
429 an epilogue and cannot emit a new RETURN, we cannot
430 emit the label at all. */
432 #endif /* HAVE_epilogue */
434 /* Otherwise, make a new label and emit a RETURN and BARRIER,
440 /* The return we make may have delay slots too. */
441 rtx insn
= gen_return ();
442 insn
= emit_jump_insn (insn
);
443 set_return_jump_label (insn
);
445 if (num_delay_slots (insn
) > 0)
446 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
453 /* Show one additional use for this label so it won't go away until
455 ++LABEL_NUSES (*plabel
);
460 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
461 the pattern of INSN with the SEQUENCE.
463 Chain the insns so that NEXT_INSN of each insn in the sequence points to
464 the next and NEXT_INSN of the last insn in the sequence points to
465 the first insn after the sequence. Similarly for PREV_INSN. This makes
466 it easier to scan all insns.
468 Returns the SEQUENCE that replaces INSN. */
471 emit_delay_sequence (rtx insn
, rtx list
, int length
)
477 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
478 rtvec seqv
= rtvec_alloc (length
+ 1);
479 rtx seq
= gen_rtx_SEQUENCE (VOIDmode
, seqv
);
480 rtx seq_insn
= make_insn_raw (seq
);
481 rtx first
= get_insns ();
482 rtx last
= get_last_insn ();
484 /* Make a copy of the insn having delay slots. */
485 rtx delay_insn
= copy_rtx (insn
);
487 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
488 confuse further processing. Update LAST in case it was the last insn.
489 We will put the BARRIER back in later. */
490 if (NEXT_INSN (insn
) && BARRIER_P (NEXT_INSN (insn
)))
492 delete_related_insns (NEXT_INSN (insn
));
493 last
= get_last_insn ();
497 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
498 NEXT_INSN (seq_insn
) = NEXT_INSN (insn
);
499 PREV_INSN (seq_insn
) = PREV_INSN (insn
);
502 PREV_INSN (NEXT_INSN (seq_insn
)) = seq_insn
;
505 NEXT_INSN (PREV_INSN (seq_insn
)) = seq_insn
;
507 /* Note the calls to set_new_first_and_last_insn must occur after
508 SEQ_INSN has been completely spliced into the insn stream.
510 Otherwise CUR_INSN_UID will get set to an incorrect value because
511 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
513 set_new_first_and_last_insn (first
, seq_insn
);
516 set_new_first_and_last_insn (seq_insn
, last
);
518 /* Build our SEQUENCE and rebuild the insn chain. */
519 XVECEXP (seq
, 0, 0) = delay_insn
;
520 INSN_DELETED_P (delay_insn
) = 0;
521 PREV_INSN (delay_insn
) = PREV_INSN (seq_insn
);
523 INSN_LOCATION (seq_insn
) = INSN_LOCATION (delay_insn
);
525 for (li
= list
; li
; li
= XEXP (li
, 1), i
++)
527 rtx tem
= XEXP (li
, 0);
530 /* Show that this copy of the insn isn't deleted. */
531 INSN_DELETED_P (tem
) = 0;
533 XVECEXP (seq
, 0, i
) = tem
;
534 PREV_INSN (tem
) = XVECEXP (seq
, 0, i
- 1);
535 NEXT_INSN (XVECEXP (seq
, 0, i
- 1)) = tem
;
537 /* SPARC assembler, for instance, emit warning when debug info is output
538 into the delay slot. */
539 if (INSN_LOCATION (tem
) && !INSN_LOCATION (seq_insn
))
540 INSN_LOCATION (seq_insn
) = INSN_LOCATION (tem
);
541 INSN_LOCATION (tem
) = 0;
543 for (note
= REG_NOTES (tem
); note
; note
= next
)
545 next
= XEXP (note
, 1);
546 switch (REG_NOTE_KIND (note
))
549 /* Remove any REG_DEAD notes because we can't rely on them now
550 that the insn has been moved. */
551 remove_note (tem
, note
);
554 case REG_LABEL_OPERAND
:
555 case REG_LABEL_TARGET
:
556 /* Keep the label reference count up to date. */
557 if (LABEL_P (XEXP (note
, 0)))
558 LABEL_NUSES (XEXP (note
, 0)) ++;
567 NEXT_INSN (XVECEXP (seq
, 0, length
)) = NEXT_INSN (seq_insn
);
569 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
570 last insn in that SEQUENCE to point to us. Similarly for the first
571 insn in the following insn if it is a SEQUENCE. */
573 if (PREV_INSN (seq_insn
) && NONJUMP_INSN_P (PREV_INSN (seq_insn
))
574 && GET_CODE (PATTERN (PREV_INSN (seq_insn
))) == SEQUENCE
)
575 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn
)), 0,
576 XVECLEN (PATTERN (PREV_INSN (seq_insn
)), 0) - 1))
579 if (NEXT_INSN (seq_insn
) && NONJUMP_INSN_P (NEXT_INSN (seq_insn
))
580 && GET_CODE (PATTERN (NEXT_INSN (seq_insn
))) == SEQUENCE
)
581 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn
)), 0, 0)) = seq_insn
;
583 /* If there used to be a BARRIER, put it back. */
585 emit_barrier_after (seq_insn
);
587 gcc_assert (i
== length
+ 1);
592 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
593 be in the order in which the insns are to be executed. */
596 add_to_delay_list (rtx insn
, rtx delay_list
)
598 /* If we have an empty list, just make a new list element. If
599 INSN has its block number recorded, clear it since we may
600 be moving the insn to a new block. */
604 clear_hashed_info_for_insn (insn
);
605 return gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
608 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
610 XEXP (delay_list
, 1) = add_to_delay_list (insn
, XEXP (delay_list
, 1));
615 /* Delete INSN from the delay slot of the insn that it is in, which may
616 produce an insn with no delay slots. Return the new insn. */
619 delete_from_delay_slot (rtx insn
)
621 rtx trial
, seq_insn
, seq
, prev
;
626 /* We first must find the insn containing the SEQUENCE with INSN in its
627 delay slot. Do this by finding an insn, TRIAL, where
628 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
631 PREV_INSN (NEXT_INSN (trial
)) == trial
;
632 trial
= NEXT_INSN (trial
))
635 seq_insn
= PREV_INSN (NEXT_INSN (trial
));
636 seq
= PATTERN (seq_insn
);
638 if (NEXT_INSN (seq_insn
) && BARRIER_P (NEXT_INSN (seq_insn
)))
641 /* Create a delay list consisting of all the insns other than the one
642 we are deleting (unless we were the only one). */
643 if (XVECLEN (seq
, 0) > 2)
644 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
645 if (XVECEXP (seq
, 0, i
) != insn
)
646 delay_list
= add_to_delay_list (XVECEXP (seq
, 0, i
), delay_list
);
648 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
649 list, and rebuild the delay list if non-empty. */
650 prev
= PREV_INSN (seq_insn
);
651 trial
= XVECEXP (seq
, 0, 0);
652 delete_related_insns (seq_insn
);
653 add_insn_after (trial
, prev
, NULL
);
655 /* If there was a barrier after the old SEQUENCE, remit it. */
657 emit_barrier_after (trial
);
659 /* If there are any delay insns, remit them. Otherwise clear the
662 trial
= emit_delay_sequence (trial
, delay_list
, XVECLEN (seq
, 0) - 2);
663 else if (JUMP_P (trial
))
664 INSN_ANNULLED_BRANCH_P (trial
) = 0;
666 INSN_FROM_TARGET_P (insn
) = 0;
668 /* Show we need to fill this insn again. */
669 obstack_ptr_grow (&unfilled_slots_obstack
, trial
);
674 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
675 the insn that sets CC0 for it and delete it too. */
678 delete_scheduled_jump (rtx insn
)
680 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
681 delete the insn that sets the condition code, but it is hard to find it.
682 Since this case is rare anyway, don't bother trying; there would likely
683 be other insns that became dead anyway, which we wouldn't know to
687 if (reg_mentioned_p (cc0_rtx
, insn
))
689 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
691 /* If a reg-note was found, it points to an insn to set CC0. This
692 insn is in the delay list of some other insn. So delete it from
693 the delay list it was in. */
696 if (! FIND_REG_INC_NOTE (XEXP (note
, 0), NULL_RTX
)
697 && sets_cc0_p (PATTERN (XEXP (note
, 0))) == 1)
698 delete_from_delay_slot (XEXP (note
, 0));
702 /* The insn setting CC0 is our previous insn, but it may be in
703 a delay slot. It will be the last insn in the delay slot, if
705 rtx trial
= previous_insn (insn
);
707 trial
= prev_nonnote_insn (trial
);
708 if (sets_cc0_p (PATTERN (trial
)) != 1
709 || FIND_REG_INC_NOTE (trial
, NULL_RTX
))
711 if (PREV_INSN (NEXT_INSN (trial
)) == trial
)
712 delete_related_insns (trial
);
714 delete_from_delay_slot (trial
);
719 delete_related_insns (insn
);
722 /* Counters for delay-slot filling. */
724 #define NUM_REORG_FUNCTIONS 2
725 #define MAX_DELAY_HISTOGRAM 3
726 #define MAX_REORG_PASSES 2
728 static int num_insns_needing_delays
[NUM_REORG_FUNCTIONS
][MAX_REORG_PASSES
];
730 static int num_filled_delays
[NUM_REORG_FUNCTIONS
][MAX_DELAY_HISTOGRAM
+1][MAX_REORG_PASSES
];
732 static int reorg_pass_number
;
735 note_delay_statistics (int slots_filled
, int index
)
737 num_insns_needing_delays
[index
][reorg_pass_number
]++;
738 if (slots_filled
> MAX_DELAY_HISTOGRAM
)
739 slots_filled
= MAX_DELAY_HISTOGRAM
;
740 num_filled_delays
[index
][slots_filled
][reorg_pass_number
]++;
743 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
745 /* Optimize the following cases:
747 1. When a conditional branch skips over only one instruction,
748 use an annulling branch and put that insn in the delay slot.
749 Use either a branch that annuls when the condition if true or
750 invert the test with a branch that annuls when the condition is
751 false. This saves insns, since otherwise we must copy an insn
754 (orig) (skip) (otherwise)
755 Bcc.n L1 Bcc',a L1 Bcc,a L1'
762 2. When a conditional branch skips over only one instruction,
763 and after that, it unconditionally branches somewhere else,
764 perform the similar optimization. This saves executing the
765 second branch in the case where the inverted condition is true.
774 This should be expanded to skip over N insns, where N is the number
775 of delay slots required. */
778 optimize_skip (rtx insn
)
780 rtx trial
= next_nonnote_insn (insn
);
781 rtx next_trial
= next_active_insn (trial
);
785 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
788 || !NONJUMP_INSN_P (trial
)
789 || GET_CODE (PATTERN (trial
)) == SEQUENCE
790 || recog_memoized (trial
) < 0
791 || (! eligible_for_annul_false (insn
, 0, trial
, flags
)
792 && ! eligible_for_annul_true (insn
, 0, trial
, flags
))
793 || can_throw_internal (trial
))
796 /* There are two cases where we are just executing one insn (we assume
797 here that a branch requires only one insn; this should be generalized
798 at some point): Where the branch goes around a single insn or where
799 we have one insn followed by a branch to the same label we branch to.
800 In both of these cases, inverting the jump and annulling the delay
801 slot give the same effect in fewer insns. */
802 if (next_trial
== next_active_insn (JUMP_LABEL (insn
))
804 && simplejump_or_return_p (next_trial
)
805 && JUMP_LABEL (insn
) == JUMP_LABEL (next_trial
)))
807 if (eligible_for_annul_false (insn
, 0, trial
, flags
))
809 if (invert_jump (insn
, JUMP_LABEL (insn
), 1))
810 INSN_FROM_TARGET_P (trial
) = 1;
811 else if (! eligible_for_annul_true (insn
, 0, trial
, flags
))
815 delay_list
= add_to_delay_list (trial
, NULL_RTX
);
816 next_trial
= next_active_insn (trial
);
817 update_block (trial
, trial
);
818 delete_related_insns (trial
);
820 /* Also, if we are targeting an unconditional
821 branch, thread our jump to the target of that branch. Don't
822 change this into a RETURN here, because it may not accept what
823 we have in the delay slot. We'll fix this up later. */
824 if (next_trial
&& simplejump_or_return_p (next_trial
))
826 rtx target_label
= JUMP_LABEL (next_trial
);
827 if (ANY_RETURN_P (target_label
))
828 target_label
= find_end_label (target_label
);
832 /* Recompute the flags based on TARGET_LABEL since threading
833 the jump to TARGET_LABEL may change the direction of the
834 jump (which may change the circumstances in which the
835 delay slot is nullified). */
836 flags
= get_jump_flags (insn
, target_label
);
837 if (eligible_for_annul_true (insn
, 0, trial
, flags
))
838 reorg_redirect_jump (insn
, target_label
);
842 INSN_ANNULLED_BRANCH_P (insn
) = 1;
849 /* Encode and return branch direction and prediction information for
850 INSN assuming it will jump to LABEL.
852 Non conditional branches return no direction information and
853 are predicted as very likely taken. */
856 get_jump_flags (rtx insn
, rtx label
)
860 /* get_jump_flags can be passed any insn with delay slots, these may
861 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
862 direction information, and only if they are conditional jumps.
864 If LABEL is a return, then there is no way to determine the branch
867 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
868 && !ANY_RETURN_P (label
)
869 && INSN_UID (insn
) <= max_uid
870 && INSN_UID (label
) <= max_uid
)
872 = (uid_to_ruid
[INSN_UID (label
)] > uid_to_ruid
[INSN_UID (insn
)])
873 ? ATTR_FLAG_forward
: ATTR_FLAG_backward
;
874 /* No valid direction information. */
881 /* Return truth value of the statement that this branch
882 is mostly taken. If we think that the branch is extremely likely
883 to be taken, we return 2. If the branch is slightly more likely to be
884 taken, return 1. If the branch is slightly less likely to be taken,
885 return 0 and if the branch is highly unlikely to be taken, return -1. */
888 mostly_true_jump (rtx jump_insn
)
890 /* If branch probabilities are available, then use that number since it
891 always gives a correct answer. */
892 rtx note
= find_reg_note (jump_insn
, REG_BR_PROB
, 0);
895 int prob
= INTVAL (XEXP (note
, 0));
897 if (prob
>= REG_BR_PROB_BASE
* 9 / 10)
899 else if (prob
>= REG_BR_PROB_BASE
/ 2)
901 else if (prob
>= REG_BR_PROB_BASE
/ 10)
907 /* If there is no note, assume branches are not taken.
908 This should be rare. */
912 /* Return the condition under which INSN will branch to TARGET. If TARGET
913 is zero, return the condition under which INSN will return. If INSN is
914 an unconditional branch, return const_true_rtx. If INSN isn't a simple
915 type of jump, or it doesn't go to TARGET, return 0. */
918 get_branch_condition (rtx insn
, rtx target
)
920 rtx pat
= PATTERN (insn
);
923 if (condjump_in_parallel_p (insn
))
924 pat
= XVECEXP (pat
, 0, 0);
926 if (ANY_RETURN_P (pat
))
927 return pat
== target
? const_true_rtx
: 0;
929 if (GET_CODE (pat
) != SET
|| SET_DEST (pat
) != pc_rtx
)
933 if (GET_CODE (src
) == LABEL_REF
&& XEXP (src
, 0) == target
)
934 return const_true_rtx
;
936 else if (GET_CODE (src
) == IF_THEN_ELSE
937 && XEXP (src
, 2) == pc_rtx
938 && GET_CODE (XEXP (src
, 1)) == LABEL_REF
939 && XEXP (XEXP (src
, 1), 0) == target
)
940 return XEXP (src
, 0);
942 else if (GET_CODE (src
) == IF_THEN_ELSE
943 && XEXP (src
, 1) == pc_rtx
944 && GET_CODE (XEXP (src
, 2)) == LABEL_REF
945 && XEXP (XEXP (src
, 2), 0) == target
)
948 rev
= reversed_comparison_code (XEXP (src
, 0), insn
);
950 return gen_rtx_fmt_ee (rev
, GET_MODE (XEXP (src
, 0)),
951 XEXP (XEXP (src
, 0), 0),
952 XEXP (XEXP (src
, 0), 1));
958 /* Return nonzero if CONDITION is more strict than the condition of
959 INSN, i.e., if INSN will always branch if CONDITION is true. */
962 condition_dominates_p (rtx condition
, rtx insn
)
964 rtx other_condition
= get_branch_condition (insn
, JUMP_LABEL (insn
));
965 enum rtx_code code
= GET_CODE (condition
);
966 enum rtx_code other_code
;
968 if (rtx_equal_p (condition
, other_condition
)
969 || other_condition
== const_true_rtx
)
972 else if (condition
== const_true_rtx
|| other_condition
== 0)
975 other_code
= GET_CODE (other_condition
);
976 if (GET_RTX_LENGTH (code
) != 2 || GET_RTX_LENGTH (other_code
) != 2
977 || ! rtx_equal_p (XEXP (condition
, 0), XEXP (other_condition
, 0))
978 || ! rtx_equal_p (XEXP (condition
, 1), XEXP (other_condition
, 1)))
981 return comparison_dominates_p (code
, other_code
);
984 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
985 any insns already in the delay slot of JUMP. */
988 redirect_with_delay_slots_safe_p (rtx jump
, rtx newlabel
, rtx seq
)
991 rtx pat
= PATTERN (seq
);
993 /* Make sure all the delay slots of this jump would still
994 be valid after threading the jump. If they are still
995 valid, then return nonzero. */
997 flags
= get_jump_flags (jump
, newlabel
);
998 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1000 #ifdef ANNUL_IFFALSE_SLOTS
1001 (INSN_ANNULLED_BRANCH_P (jump
)
1002 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1003 ? eligible_for_annul_false (jump
, i
- 1,
1004 XVECEXP (pat
, 0, i
), flags
) :
1006 #ifdef ANNUL_IFTRUE_SLOTS
1007 (INSN_ANNULLED_BRANCH_P (jump
)
1008 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1009 ? eligible_for_annul_true (jump
, i
- 1,
1010 XVECEXP (pat
, 0, i
), flags
) :
1012 eligible_for_delay (jump
, i
- 1, XVECEXP (pat
, 0, i
), flags
)))
1015 return (i
== XVECLEN (pat
, 0));
1018 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1019 any insns we wish to place in the delay slot of JUMP. */
1022 redirect_with_delay_list_safe_p (rtx jump
, rtx newlabel
, rtx delay_list
)
1027 /* Make sure all the insns in DELAY_LIST would still be
1028 valid after threading the jump. If they are still
1029 valid, then return nonzero. */
1031 flags
= get_jump_flags (jump
, newlabel
);
1032 for (li
= delay_list
, i
= 0; li
; li
= XEXP (li
, 1), i
++)
1034 #ifdef ANNUL_IFFALSE_SLOTS
1035 (INSN_ANNULLED_BRANCH_P (jump
)
1036 && INSN_FROM_TARGET_P (XEXP (li
, 0)))
1037 ? eligible_for_annul_false (jump
, i
, XEXP (li
, 0), flags
) :
1039 #ifdef ANNUL_IFTRUE_SLOTS
1040 (INSN_ANNULLED_BRANCH_P (jump
)
1041 && ! INSN_FROM_TARGET_P (XEXP (li
, 0)))
1042 ? eligible_for_annul_true (jump
, i
, XEXP (li
, 0), flags
) :
1044 eligible_for_delay (jump
, i
, XEXP (li
, 0), flags
)))
1047 return (li
== NULL
);
1050 /* DELAY_LIST is a list of insns that have already been placed into delay
1051 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1052 If not, return 0; otherwise return 1. */
1055 check_annul_list_true_false (int annul_true_p
, rtx delay_list
)
1061 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1063 rtx trial
= XEXP (temp
, 0);
1065 if ((annul_true_p
&& INSN_FROM_TARGET_P (trial
))
1066 || (!annul_true_p
&& !INSN_FROM_TARGET_P (trial
)))
1074 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1075 the condition tested by INSN is CONDITION and the resources shown in
1076 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1077 from SEQ's delay list, in addition to whatever insns it may execute
1078 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1079 needed while searching for delay slot insns. Return the concatenated
1080 delay list if possible, otherwise, return 0.
1082 SLOTS_TO_FILL is the total number of slots required by INSN, and
1083 PSLOTS_FILLED points to the number filled so far (also the number of
1084 insns in DELAY_LIST). It is updated with the number that have been
1085 filled from the SEQUENCE, if any.
1087 PANNUL_P points to a nonzero value if we already know that we need
1088 to annul INSN. If this routine determines that annulling is needed,
1089 it may set that value nonzero.
1091 PNEW_THREAD points to a location that is to receive the place at which
1092 execution should continue. */
1095 steal_delay_list_from_target (rtx insn
, rtx condition
, rtx seq
,
1096 rtx delay_list
, struct resources
*sets
,
1097 struct resources
*needed
,
1098 struct resources
*other_needed
,
1099 int slots_to_fill
, int *pslots_filled
,
1100 int *pannul_p
, rtx
*pnew_thread
)
1103 int slots_remaining
= slots_to_fill
- *pslots_filled
;
1104 int total_slots_filled
= *pslots_filled
;
1105 rtx new_delay_list
= 0;
1106 int must_annul
= *pannul_p
;
1109 struct resources cc_set
;
1111 /* We can't do anything if there are more delay slots in SEQ than we
1112 can handle, or if we don't know that it will be a taken branch.
1113 We know that it will be a taken branch if it is either an unconditional
1114 branch or a conditional branch with a stricter branch condition.
1116 Also, exit if the branch has more than one set, since then it is computing
1117 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1118 ??? It may be possible to move other sets into INSN in addition to
1119 moving the instructions in the delay slots.
1121 We can not steal the delay list if one of the instructions in the
1122 current delay_list modifies the condition codes and the jump in the
1123 sequence is a conditional jump. We can not do this because we can
1124 not change the direction of the jump because the condition codes
1125 will effect the direction of the jump in the sequence. */
1127 CLEAR_RESOURCE (&cc_set
);
1128 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1130 rtx trial
= XEXP (temp
, 0);
1132 mark_set_resources (trial
, &cc_set
, 0, MARK_SRC_DEST_CALL
);
1133 if (insn_references_resource_p (XVECEXP (seq
, 0, 0), &cc_set
, false))
1137 if (XVECLEN (seq
, 0) - 1 > slots_remaining
1138 || ! condition_dominates_p (condition
, XVECEXP (seq
, 0, 0))
1139 || ! single_set (XVECEXP (seq
, 0, 0)))
1142 #ifdef MD_CAN_REDIRECT_BRANCH
1143 /* On some targets, branches with delay slots can have a limited
1144 displacement. Give the back end a chance to tell us we can't do
1146 if (! MD_CAN_REDIRECT_BRANCH (insn
, XVECEXP (seq
, 0, 0)))
1150 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1152 rtx trial
= XVECEXP (seq
, 0, i
);
1155 if (insn_references_resource_p (trial
, sets
, false)
1156 || insn_sets_resource_p (trial
, needed
, false)
1157 || insn_sets_resource_p (trial
, sets
, false)
1159 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1161 || find_reg_note (trial
, REG_CC_USER
, NULL_RTX
)
1163 /* If TRIAL is from the fallthrough code of an annulled branch insn
1164 in SEQ, we cannot use it. */
1165 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq
, 0, 0))
1166 && ! INSN_FROM_TARGET_P (trial
)))
1169 /* If this insn was already done (usually in a previous delay slot),
1170 pretend we put it in our delay slot. */
1171 if (redundant_insn (trial
, insn
, new_delay_list
))
1174 /* We will end up re-vectoring this branch, so compute flags
1175 based on jumping to the new label. */
1176 flags
= get_jump_flags (insn
, JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1179 && ((condition
== const_true_rtx
1180 || (! insn_sets_resource_p (trial
, other_needed
, false)
1181 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1182 ? eligible_for_delay (insn
, total_slots_filled
, trial
, flags
)
1183 : (must_annul
|| (delay_list
== NULL
&& new_delay_list
== NULL
))
1185 check_annul_list_true_false (0, delay_list
)
1186 && check_annul_list_true_false (0, new_delay_list
)
1187 && eligible_for_annul_false (insn
, total_slots_filled
,
1192 temp
= copy_delay_slot_insn (trial
);
1193 INSN_FROM_TARGET_P (temp
) = 1;
1194 new_delay_list
= add_to_delay_list (temp
, new_delay_list
);
1195 total_slots_filled
++;
1197 if (--slots_remaining
== 0)
1204 /* Show the place to which we will be branching. */
1205 *pnew_thread
= first_active_target_insn (JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1207 /* Add any new insns to the delay list and update the count of the
1208 number of slots filled. */
1209 *pslots_filled
= total_slots_filled
;
1213 if (delay_list
== 0)
1214 return new_delay_list
;
1216 for (temp
= new_delay_list
; temp
; temp
= XEXP (temp
, 1))
1217 delay_list
= add_to_delay_list (XEXP (temp
, 0), delay_list
);
1222 /* Similar to steal_delay_list_from_target except that SEQ is on the
1223 fallthrough path of INSN. Here we only do something if the delay insn
1224 of SEQ is an unconditional branch. In that case we steal its delay slot
1225 for INSN since unconditional branches are much easier to fill. */
1228 steal_delay_list_from_fallthrough (rtx insn
, rtx condition
, rtx seq
,
1229 rtx delay_list
, struct resources
*sets
,
1230 struct resources
*needed
,
1231 struct resources
*other_needed
,
1232 int slots_to_fill
, int *pslots_filled
,
1237 int must_annul
= *pannul_p
;
1240 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
1242 /* We can't do anything if SEQ's delay insn isn't an
1243 unconditional branch. */
1245 if (! simplejump_or_return_p (XVECEXP (seq
, 0, 0)))
1248 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1250 rtx trial
= XVECEXP (seq
, 0, i
);
1252 /* If TRIAL sets CC0, stealing it will move it too far from the use
1254 if (insn_references_resource_p (trial
, sets
, false)
1255 || insn_sets_resource_p (trial
, needed
, false)
1256 || insn_sets_resource_p (trial
, sets
, false)
1258 || sets_cc0_p (PATTERN (trial
))
1264 /* If this insn was already done, we don't need it. */
1265 if (redundant_insn (trial
, insn
, delay_list
))
1267 delete_from_delay_slot (trial
);
1272 && ((condition
== const_true_rtx
1273 || (! insn_sets_resource_p (trial
, other_needed
, false)
1274 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1275 ? eligible_for_delay (insn
, *pslots_filled
, trial
, flags
)
1276 : (must_annul
|| delay_list
== NULL
) && (must_annul
= 1,
1277 check_annul_list_true_false (1, delay_list
)
1278 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
1282 delete_from_delay_slot (trial
);
1283 delay_list
= add_to_delay_list (trial
, delay_list
);
1285 if (++(*pslots_filled
) == slots_to_fill
)
1297 /* Try merging insns starting at THREAD which match exactly the insns in
1300 If all insns were matched and the insn was previously annulling, the
1301 annul bit will be cleared.
1303 For each insn that is merged, if the branch is or will be non-annulling,
1304 we delete the merged insn. */
1307 try_merge_delay_insns (rtx insn
, rtx thread
)
1309 rtx trial
, next_trial
;
1310 rtx delay_insn
= XVECEXP (PATTERN (insn
), 0, 0);
1311 int annul_p
= JUMP_P (delay_insn
) && INSN_ANNULLED_BRANCH_P (delay_insn
);
1312 int slot_number
= 1;
1313 int num_slots
= XVECLEN (PATTERN (insn
), 0);
1314 rtx next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1315 struct resources set
, needed
;
1316 rtx merged_insns
= 0;
1320 flags
= get_jump_flags (delay_insn
, JUMP_LABEL (delay_insn
));
1322 CLEAR_RESOURCE (&needed
);
1323 CLEAR_RESOURCE (&set
);
1325 /* If this is not an annulling branch, take into account anything needed in
1326 INSN's delay slot. This prevents two increments from being incorrectly
1327 folded into one. If we are annulling, this would be the correct
1328 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1329 will essentially disable this optimization. This method is somewhat of
1330 a kludge, but I don't see a better way.) */
1332 for (i
= 1 ; i
< num_slots
; i
++)
1333 if (XVECEXP (PATTERN (insn
), 0, i
))
1334 mark_referenced_resources (XVECEXP (PATTERN (insn
), 0, i
), &needed
,
1337 for (trial
= thread
; !stop_search_p (trial
, 1); trial
= next_trial
)
1339 rtx pat
= PATTERN (trial
);
1340 rtx oldtrial
= trial
;
1342 next_trial
= next_nonnote_insn (trial
);
1344 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1345 if (NONJUMP_INSN_P (trial
)
1346 && (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
))
1349 if (GET_CODE (next_to_match
) == GET_CODE (trial
)
1351 /* We can't share an insn that sets cc0. */
1352 && ! sets_cc0_p (pat
)
1354 && ! insn_references_resource_p (trial
, &set
, true)
1355 && ! insn_sets_resource_p (trial
, &set
, true)
1356 && ! insn_sets_resource_p (trial
, &needed
, true)
1357 && (trial
= try_split (pat
, trial
, 0)) != 0
1358 /* Update next_trial, in case try_split succeeded. */
1359 && (next_trial
= next_nonnote_insn (trial
))
1360 /* Likewise THREAD. */
1361 && (thread
= oldtrial
== thread
? trial
: thread
)
1362 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (trial
))
1363 /* Have to test this condition if annul condition is different
1364 from (and less restrictive than) non-annulling one. */
1365 && eligible_for_delay (delay_insn
, slot_number
- 1, trial
, flags
))
1370 update_block (trial
, thread
);
1371 if (trial
== thread
)
1372 thread
= next_active_insn (thread
);
1374 delete_related_insns (trial
);
1375 INSN_FROM_TARGET_P (next_to_match
) = 0;
1378 merged_insns
= gen_rtx_INSN_LIST (VOIDmode
, trial
, merged_insns
);
1380 if (++slot_number
== num_slots
)
1383 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1386 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
1387 mark_referenced_resources (trial
, &needed
, true);
1390 /* See if we stopped on a filled insn. If we did, try to see if its
1391 delay slots match. */
1392 if (slot_number
!= num_slots
1393 && trial
&& NONJUMP_INSN_P (trial
)
1394 && GET_CODE (PATTERN (trial
)) == SEQUENCE
1395 && !(JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
1396 && INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial
), 0, 0))))
1398 rtx pat
= PATTERN (trial
);
1399 rtx filled_insn
= XVECEXP (pat
, 0, 0);
1401 /* Account for resources set/needed by the filled insn. */
1402 mark_set_resources (filled_insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1403 mark_referenced_resources (filled_insn
, &needed
, true);
1405 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1407 rtx dtrial
= XVECEXP (pat
, 0, i
);
1409 if (! insn_references_resource_p (dtrial
, &set
, true)
1410 && ! insn_sets_resource_p (dtrial
, &set
, true)
1411 && ! insn_sets_resource_p (dtrial
, &needed
, true)
1413 && ! sets_cc0_p (PATTERN (dtrial
))
1415 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (dtrial
))
1416 && eligible_for_delay (delay_insn
, slot_number
- 1, dtrial
, flags
))
1422 update_block (dtrial
, thread
);
1423 new_rtx
= delete_from_delay_slot (dtrial
);
1424 if (INSN_DELETED_P (thread
))
1426 INSN_FROM_TARGET_P (next_to_match
) = 0;
1429 merged_insns
= gen_rtx_INSN_LIST (SImode
, dtrial
,
1432 if (++slot_number
== num_slots
)
1435 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1439 /* Keep track of the set/referenced resources for the delay
1440 slots of any trial insns we encounter. */
1441 mark_set_resources (dtrial
, &set
, 0, MARK_SRC_DEST_CALL
);
1442 mark_referenced_resources (dtrial
, &needed
, true);
1447 /* If all insns in the delay slot have been matched and we were previously
1448 annulling the branch, we need not any more. In that case delete all the
1449 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1450 the delay list so that we know that it isn't only being used at the
1452 if (slot_number
== num_slots
&& annul_p
)
1454 for (; merged_insns
; merged_insns
= XEXP (merged_insns
, 1))
1456 if (GET_MODE (merged_insns
) == SImode
)
1460 update_block (XEXP (merged_insns
, 0), thread
);
1461 new_rtx
= delete_from_delay_slot (XEXP (merged_insns
, 0));
1462 if (INSN_DELETED_P (thread
))
1467 update_block (XEXP (merged_insns
, 0), thread
);
1468 delete_related_insns (XEXP (merged_insns
, 0));
1472 INSN_ANNULLED_BRANCH_P (delay_insn
) = 0;
1474 for (i
= 0; i
< XVECLEN (PATTERN (insn
), 0); i
++)
1475 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn
), 0, i
)) = 0;
1479 /* See if INSN is redundant with an insn in front of TARGET. Often this
1480 is called when INSN is a candidate for a delay slot of TARGET.
1481 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1482 of INSN. Often INSN will be redundant with an insn in a delay slot of
1483 some previous insn. This happens when we have a series of branches to the
1484 same label; in that case the first insn at the target might want to go
1485 into each of the delay slots.
1487 If we are not careful, this routine can take up a significant fraction
1488 of the total compilation time (4%), but only wins rarely. Hence we
1489 speed this routine up by making two passes. The first pass goes back
1490 until it hits a label and sees if it finds an insn with an identical
1491 pattern. Only in this (relatively rare) event does it check for
1494 We do not split insns we encounter. This could cause us not to find a
1495 redundant insn, but the cost of splitting seems greater than the possible
1496 gain in rare cases. */
1499 redundant_insn (rtx insn
, rtx target
, rtx delay_list
)
1501 rtx target_main
= target
;
1502 rtx ipat
= PATTERN (insn
);
1504 struct resources needed
, set
;
1506 unsigned insns_to_search
;
1508 /* If INSN has any REG_UNUSED notes, it can't match anything since we
1509 are allowed to not actually assign to such a register. */
1510 if (find_reg_note (insn
, REG_UNUSED
, NULL_RTX
) != 0)
1513 /* Scan backwards looking for a match. */
1514 for (trial
= PREV_INSN (target
),
1515 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1516 trial
&& insns_to_search
> 0;
1517 trial
= PREV_INSN (trial
))
1519 if (LABEL_P (trial
))
1522 if (!INSN_P (trial
))
1526 pat
= PATTERN (trial
);
1527 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1530 if (GET_CODE (pat
) == SEQUENCE
)
1532 /* Stop for a CALL and its delay slots because it is difficult to
1533 track its resource needs correctly. */
1534 if (CALL_P (XVECEXP (pat
, 0, 0)))
1537 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1538 slots because it is difficult to track its resource needs
1541 #ifdef INSN_SETS_ARE_DELAYED
1542 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1546 #ifdef INSN_REFERENCES_ARE_DELAYED
1547 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1551 /* See if any of the insns in the delay slot match, updating
1552 resource requirements as we go. */
1553 for (i
= XVECLEN (pat
, 0) - 1; i
> 0; i
--)
1554 if (GET_CODE (XVECEXP (pat
, 0, i
)) == GET_CODE (insn
)
1555 && rtx_equal_p (PATTERN (XVECEXP (pat
, 0, i
)), ipat
)
1556 && ! find_reg_note (XVECEXP (pat
, 0, i
), REG_UNUSED
, NULL_RTX
))
1559 /* If found a match, exit this loop early. */
1564 else if (GET_CODE (trial
) == GET_CODE (insn
) && rtx_equal_p (pat
, ipat
)
1565 && ! find_reg_note (trial
, REG_UNUSED
, NULL_RTX
))
1569 /* If we didn't find an insn that matches, return 0. */
1573 /* See what resources this insn sets and needs. If they overlap, or
1574 if this insn references CC0, it can't be redundant. */
1576 CLEAR_RESOURCE (&needed
);
1577 CLEAR_RESOURCE (&set
);
1578 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1579 mark_referenced_resources (insn
, &needed
, true);
1581 /* If TARGET is a SEQUENCE, get the main insn. */
1582 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1583 target_main
= XVECEXP (PATTERN (target
), 0, 0);
1585 if (resource_conflicts_p (&needed
, &set
)
1587 || reg_mentioned_p (cc0_rtx
, ipat
)
1589 /* The insn requiring the delay may not set anything needed or set by
1591 || insn_sets_resource_p (target_main
, &needed
, true)
1592 || insn_sets_resource_p (target_main
, &set
, true))
1595 /* Insns we pass may not set either NEEDED or SET, so merge them for
1597 needed
.memory
|= set
.memory
;
1598 needed
.unch_memory
|= set
.unch_memory
;
1599 IOR_HARD_REG_SET (needed
.regs
, set
.regs
);
1601 /* This insn isn't redundant if it conflicts with an insn that either is
1602 or will be in a delay slot of TARGET. */
1606 if (insn_sets_resource_p (XEXP (delay_list
, 0), &needed
, true))
1608 delay_list
= XEXP (delay_list
, 1);
1611 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1612 for (i
= 1; i
< XVECLEN (PATTERN (target
), 0); i
++)
1613 if (insn_sets_resource_p (XVECEXP (PATTERN (target
), 0, i
), &needed
,
1617 /* Scan backwards until we reach a label or an insn that uses something
1618 INSN sets or sets something insn uses or sets. */
1620 for (trial
= PREV_INSN (target
),
1621 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1622 trial
&& !LABEL_P (trial
) && insns_to_search
> 0;
1623 trial
= PREV_INSN (trial
))
1625 if (!INSN_P (trial
))
1629 pat
= PATTERN (trial
);
1630 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1633 if (GET_CODE (pat
) == SEQUENCE
)
1635 bool annul_p
= false;
1636 rtx control
= XVECEXP (pat
, 0, 0);
1638 /* If this is a CALL_INSN and its delay slots, it is hard to track
1639 the resource needs properly, so give up. */
1640 if (CALL_P (control
))
1643 /* If this is an INSN or JUMP_INSN with delayed effects, it
1644 is hard to track the resource needs properly, so give up. */
1646 #ifdef INSN_SETS_ARE_DELAYED
1647 if (INSN_SETS_ARE_DELAYED (control
))
1651 #ifdef INSN_REFERENCES_ARE_DELAYED
1652 if (INSN_REFERENCES_ARE_DELAYED (control
))
1656 if (JUMP_P (control
))
1657 annul_p
= INSN_ANNULLED_BRANCH_P (control
);
1659 /* See if any of the insns in the delay slot match, updating
1660 resource requirements as we go. */
1661 for (i
= XVECLEN (pat
, 0) - 1; i
> 0; i
--)
1663 rtx candidate
= XVECEXP (pat
, 0, i
);
1665 /* If an insn will be annulled if the branch is false, it isn't
1666 considered as a possible duplicate insn. */
1667 if (rtx_equal_p (PATTERN (candidate
), ipat
)
1668 && ! (annul_p
&& INSN_FROM_TARGET_P (candidate
)))
1670 /* Show that this insn will be used in the sequel. */
1671 INSN_FROM_TARGET_P (candidate
) = 0;
1675 /* Unless this is an annulled insn from the target of a branch,
1676 we must stop if it sets anything needed or set by INSN. */
1677 if ((!annul_p
|| !INSN_FROM_TARGET_P (candidate
))
1678 && insn_sets_resource_p (candidate
, &needed
, true))
1682 /* If the insn requiring the delay slot conflicts with INSN, we
1684 if (insn_sets_resource_p (control
, &needed
, true))
1689 /* See if TRIAL is the same as INSN. */
1690 pat
= PATTERN (trial
);
1691 if (rtx_equal_p (pat
, ipat
))
1694 /* Can't go any further if TRIAL conflicts with INSN. */
1695 if (insn_sets_resource_p (trial
, &needed
, true))
1703 /* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero,
1704 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1705 is nonzero, we are allowed to fall into this thread; otherwise, we are
1708 If LABEL is used more than one or we pass a label other than LABEL before
1709 finding an active insn, we do not own this thread. */
1712 own_thread_p (rtx thread
, rtx label
, int allow_fallthrough
)
1717 /* We don't own the function end. */
1718 if (thread
== 0 || ANY_RETURN_P (thread
))
1721 /* Get the first active insn, or THREAD, if it is an active insn. */
1722 active_insn
= next_active_insn (PREV_INSN (thread
));
1724 for (insn
= thread
; insn
!= active_insn
; insn
= NEXT_INSN (insn
))
1726 && (insn
!= label
|| LABEL_NUSES (insn
) != 1))
1729 if (allow_fallthrough
)
1732 /* Ensure that we reach a BARRIER before any insn or label. */
1733 for (insn
= prev_nonnote_insn (thread
);
1734 insn
== 0 || !BARRIER_P (insn
);
1735 insn
= prev_nonnote_insn (insn
))
1738 || (NONJUMP_INSN_P (insn
)
1739 && GET_CODE (PATTERN (insn
)) != USE
1740 && GET_CODE (PATTERN (insn
)) != CLOBBER
))
1746 /* Called when INSN is being moved from a location near the target of a jump.
1747 We leave a marker of the form (use (INSN)) immediately in front
1748 of WHERE for mark_target_live_regs. These markers will be deleted when
1751 We used to try to update the live status of registers if WHERE is at
1752 the start of a basic block, but that can't work since we may remove a
1753 BARRIER in relax_delay_slots. */
1756 update_block (rtx insn
, rtx where
)
1758 /* Ignore if this was in a delay slot and it came from the target of
1760 if (INSN_FROM_TARGET_P (insn
))
1763 emit_insn_before (gen_rtx_USE (VOIDmode
, insn
), where
);
1765 /* INSN might be making a value live in a block where it didn't use to
1766 be. So recompute liveness information for this block. */
1768 incr_ticks_for_insn (insn
);
1771 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1772 the basic block containing the jump. */
1775 reorg_redirect_jump (rtx jump
, rtx nlabel
)
1777 incr_ticks_for_insn (jump
);
1778 return redirect_jump (jump
, nlabel
, 1);
1781 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1782 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1783 that reference values used in INSN. If we find one, then we move the
1784 REG_DEAD note to INSN.
1786 This is needed to handle the case where a later insn (after INSN) has a
1787 REG_DEAD note for a register used by INSN, and this later insn subsequently
1788 gets moved before a CODE_LABEL because it is a redundant insn. In this
1789 case, mark_target_live_regs may be confused into thinking the register
1790 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1793 update_reg_dead_notes (rtx insn
, rtx delayed_insn
)
1797 for (p
= next_nonnote_insn (insn
); p
!= delayed_insn
;
1798 p
= next_nonnote_insn (p
))
1799 for (link
= REG_NOTES (p
); link
; link
= next
)
1801 next
= XEXP (link
, 1);
1803 if (REG_NOTE_KIND (link
) != REG_DEAD
1804 || !REG_P (XEXP (link
, 0)))
1807 if (reg_referenced_p (XEXP (link
, 0), PATTERN (insn
)))
1809 /* Move the REG_DEAD note from P to INSN. */
1810 remove_note (p
, link
);
1811 XEXP (link
, 1) = REG_NOTES (insn
);
1812 REG_NOTES (insn
) = link
;
1817 /* Called when an insn redundant with start_insn is deleted. If there
1818 is a REG_DEAD note for the target of start_insn between start_insn
1819 and stop_insn, then the REG_DEAD note needs to be deleted since the
1820 value no longer dies there.
1822 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1823 confused into thinking the register is dead. */
1826 fix_reg_dead_note (rtx start_insn
, rtx stop_insn
)
1830 for (p
= next_nonnote_insn (start_insn
); p
!= stop_insn
;
1831 p
= next_nonnote_insn (p
))
1832 for (link
= REG_NOTES (p
); link
; link
= next
)
1834 next
= XEXP (link
, 1);
1836 if (REG_NOTE_KIND (link
) != REG_DEAD
1837 || !REG_P (XEXP (link
, 0)))
1840 if (reg_set_p (XEXP (link
, 0), PATTERN (start_insn
)))
1842 remove_note (p
, link
);
1848 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
1850 This handles the case of udivmodXi4 instructions which optimize their
1851 output depending on whether any REG_UNUSED notes are present.
1852 we must make sure that INSN calculates as many results as REDUNDANT_INSN
1856 update_reg_unused_notes (rtx insn
, rtx redundant_insn
)
1860 for (link
= REG_NOTES (insn
); link
; link
= next
)
1862 next
= XEXP (link
, 1);
1864 if (REG_NOTE_KIND (link
) != REG_UNUSED
1865 || !REG_P (XEXP (link
, 0)))
1868 if (! find_regno_note (redundant_insn
, REG_UNUSED
,
1869 REGNO (XEXP (link
, 0))))
1870 remove_note (insn
, link
);
1874 /* Return the label before INSN, or put a new label there. */
1877 get_label_before (rtx insn
)
1881 /* Find an existing label at this point
1882 or make a new one if there is none. */
1883 label
= prev_nonnote_insn (insn
);
1885 if (label
== 0 || !LABEL_P (label
))
1887 rtx prev
= PREV_INSN (insn
);
1889 label
= gen_label_rtx ();
1890 emit_label_after (label
, prev
);
1891 LABEL_NUSES (label
) = 0;
1896 /* Scan a function looking for insns that need a delay slot and find insns to
1897 put into the delay slot.
1899 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
1900 as calls). We do these first since we don't want jump insns (that are
1901 easier to fill) to get the only insns that could be used for non-jump insns.
1902 When it is zero, only try to fill JUMP_INSNs.
1904 When slots are filled in this manner, the insns (including the
1905 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
1906 it is possible to tell whether a delay slot has really been filled
1907 or not. `final' knows how to deal with this, by communicating
1908 through FINAL_SEQUENCE. */
1911 fill_simple_delay_slots (int non_jumps_p
)
1913 rtx insn
, pat
, trial
, next_trial
;
1915 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
1916 struct resources needed
, set
;
1917 int slots_to_fill
, slots_filled
;
1920 for (i
= 0; i
< num_unfilled_slots
; i
++)
1923 /* Get the next insn to fill. If it has already had any slots assigned,
1924 we can't do anything with it. Maybe we'll improve this later. */
1926 insn
= unfilled_slots_base
[i
];
1928 || INSN_DELETED_P (insn
)
1929 || (NONJUMP_INSN_P (insn
)
1930 && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
1931 || (JUMP_P (insn
) && non_jumps_p
)
1932 || (!JUMP_P (insn
) && ! non_jumps_p
))
1935 /* It may have been that this insn used to need delay slots, but
1936 now doesn't; ignore in that case. This can happen, for example,
1937 on the HP PA RISC, where the number of delay slots depends on
1938 what insns are nearby. */
1939 slots_to_fill
= num_delay_slots (insn
);
1941 /* Some machine description have defined instructions to have
1942 delay slots only in certain circumstances which may depend on
1943 nearby insns (which change due to reorg's actions).
1945 For example, the PA port normally has delay slots for unconditional
1948 However, the PA port claims such jumps do not have a delay slot
1949 if they are immediate successors of certain CALL_INSNs. This
1950 allows the port to favor filling the delay slot of the call with
1951 the unconditional jump. */
1952 if (slots_to_fill
== 0)
1955 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
1956 says how many. After initialization, first try optimizing
1959 nop add %o7,.-L1,%o7
1963 If this case applies, the delay slot of the call is filled with
1964 the unconditional jump. This is done first to avoid having the
1965 delay slot of the call filled in the backward scan. Also, since
1966 the unconditional jump is likely to also have a delay slot, that
1967 insn must exist when it is subsequently scanned.
1969 This is tried on each insn with delay slots as some machines
1970 have insns which perform calls, but are not represented as
1977 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
1979 flags
= get_jump_flags (insn
, NULL_RTX
);
1981 if ((trial
= next_active_insn (insn
))
1983 && simplejump_p (trial
)
1984 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
1985 && no_labels_between_p (insn
, trial
)
1986 && ! can_throw_internal (trial
))
1990 delay_list
= add_to_delay_list (trial
, delay_list
);
1992 /* TRIAL may have had its delay slot filled, then unfilled. When
1993 the delay slot is unfilled, TRIAL is placed back on the unfilled
1994 slots obstack. Unfortunately, it is placed on the end of the
1995 obstack, not in its original location. Therefore, we must search
1996 from entry i + 1 to the end of the unfilled slots obstack to
1997 try and find TRIAL. */
1998 tmp
= &unfilled_slots_base
[i
+ 1];
1999 while (*tmp
!= trial
&& tmp
!= unfilled_slots_next
)
2002 /* Remove the unconditional jump from consideration for delay slot
2003 filling and unthread it. */
2007 rtx next
= NEXT_INSN (trial
);
2008 rtx prev
= PREV_INSN (trial
);
2010 NEXT_INSN (prev
) = next
;
2012 PREV_INSN (next
) = prev
;
2016 /* Now, scan backwards from the insn to search for a potential
2017 delay-slot candidate. Stop searching when a label or jump is hit.
2019 For each candidate, if it is to go into the delay slot (moved
2020 forward in execution sequence), it must not need or set any resources
2021 that were set by later insns and must not set any resources that
2022 are needed for those insns.
2024 The delay slot insn itself sets resources unless it is a call
2025 (in which case the called routine, not the insn itself, is doing
2028 if (slots_filled
< slots_to_fill
)
2030 CLEAR_RESOURCE (&needed
);
2031 CLEAR_RESOURCE (&set
);
2032 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST
);
2033 mark_referenced_resources (insn
, &needed
, false);
2035 for (trial
= prev_nonnote_insn (insn
); ! stop_search_p (trial
, 1);
2038 next_trial
= prev_nonnote_insn (trial
);
2040 /* This must be an INSN or CALL_INSN. */
2041 pat
= PATTERN (trial
);
2043 /* Stand-alone USE and CLOBBER are just for flow. */
2044 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2047 /* Check for resource conflict first, to avoid unnecessary
2049 if (! insn_references_resource_p (trial
, &set
, true)
2050 && ! insn_sets_resource_p (trial
, &set
, true)
2051 && ! insn_sets_resource_p (trial
, &needed
, true)
2053 /* Can't separate set of cc0 from its use. */
2054 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2056 && ! can_throw_internal (trial
))
2058 trial
= try_split (pat
, trial
, 1);
2059 next_trial
= prev_nonnote_insn (trial
);
2060 if (eligible_for_delay (insn
, slots_filled
, trial
, flags
))
2062 /* In this case, we are searching backward, so if we
2063 find insns to put on the delay list, we want
2064 to put them at the head, rather than the
2065 tail, of the list. */
2067 update_reg_dead_notes (trial
, insn
);
2068 delay_list
= gen_rtx_INSN_LIST (VOIDmode
,
2070 update_block (trial
, trial
);
2071 delete_related_insns (trial
);
2072 if (slots_to_fill
== ++slots_filled
)
2078 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2079 mark_referenced_resources (trial
, &needed
, true);
2083 /* If all needed slots haven't been filled, we come here. */
2085 /* Try to optimize case of jumping around a single insn. */
2086 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2087 if (slots_filled
!= slots_to_fill
2090 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
2091 && !ANY_RETURN_P (JUMP_LABEL (insn
)))
2093 delay_list
= optimize_skip (insn
);
2099 /* Try to get insns from beyond the insn needing the delay slot.
2100 These insns can neither set or reference resources set in insns being
2101 skipped, cannot set resources in the insn being skipped, and, if this
2102 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2103 call might not return).
2105 There used to be code which continued past the target label if
2106 we saw all uses of the target label. This code did not work,
2107 because it failed to account for some instructions which were
2108 both annulled and marked as from the target. This can happen as a
2109 result of optimize_skip. Since this code was redundant with
2110 fill_eager_delay_slots anyways, it was just deleted. */
2112 if (slots_filled
!= slots_to_fill
2113 /* If this instruction could throw an exception which is
2114 caught in the same function, then it's not safe to fill
2115 the delay slot with an instruction from beyond this
2116 point. For example, consider:
2127 Even though `i' is a local variable, we must be sure not
2128 to put `i = 3' in the delay slot if `f' might throw an
2131 Presumably, we should also check to see if we could get
2132 back to this function via `setjmp'. */
2133 && ! can_throw_internal (insn
)
2135 || ((condjump_p (insn
) || condjump_in_parallel_p (insn
))
2136 && ! simplejump_p (insn
)
2137 && !ANY_RETURN_P (JUMP_LABEL (insn
)))))
2139 /* Invariant: If insn is a JUMP_INSN, the insn's jump
2140 label. Otherwise, zero. */
2142 int maybe_never
= 0;
2143 rtx pat
, trial_delay
;
2145 CLEAR_RESOURCE (&needed
);
2146 CLEAR_RESOURCE (&set
);
2150 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2151 mark_referenced_resources (insn
, &needed
, true);
2156 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2157 mark_referenced_resources (insn
, &needed
, true);
2159 target
= JUMP_LABEL (insn
);
2162 if (target
== 0 || ANY_RETURN_P (target
))
2163 for (trial
= next_nonnote_insn (insn
); !stop_search_p (trial
, 1);
2166 next_trial
= next_nonnote_insn (trial
);
2168 /* This must be an INSN or CALL_INSN. */
2169 pat
= PATTERN (trial
);
2171 /* Stand-alone USE and CLOBBER are just for flow. */
2172 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2175 /* If this already has filled delay slots, get the insn needing
2177 if (GET_CODE (pat
) == SEQUENCE
)
2178 trial_delay
= XVECEXP (pat
, 0, 0);
2180 trial_delay
= trial
;
2182 /* Stop our search when seeing a jump. */
2183 if (JUMP_P (trial_delay
))
2186 /* See if we have a resource problem before we try to
2188 if (GET_CODE (pat
) != SEQUENCE
2189 && ! insn_references_resource_p (trial
, &set
, true)
2190 && ! insn_sets_resource_p (trial
, &set
, true)
2191 && ! insn_sets_resource_p (trial
, &needed
, true)
2193 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2195 && ! (maybe_never
&& may_trap_or_fault_p (pat
))
2196 && (trial
= try_split (pat
, trial
, 0))
2197 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2198 && ! can_throw_internal(trial
))
2200 next_trial
= next_nonnote_insn (trial
);
2201 delay_list
= add_to_delay_list (trial
, delay_list
);
2204 if (reg_mentioned_p (cc0_rtx
, pat
))
2205 link_cc0_insns (trial
);
2208 delete_related_insns (trial
);
2209 if (slots_to_fill
== ++slots_filled
)
2214 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2215 mark_referenced_resources (trial
, &needed
, true);
2217 /* Ensure we don't put insns between the setting of cc and the
2218 comparison by moving a setting of cc into an earlier delay
2219 slot since these insns could clobber the condition code. */
2222 /* If this is a call or jump, we might not get here. */
2223 if (CALL_P (trial_delay
)
2224 || JUMP_P (trial_delay
))
2228 /* If there are slots left to fill and our search was stopped by an
2229 unconditional branch, try the insn at the branch target. We can
2230 redirect the branch if it works.
2232 Don't do this if the insn at the branch target is a branch. */
2233 if (slots_to_fill
!= slots_filled
2235 && jump_to_label_p (trial
)
2236 && simplejump_p (trial
)
2237 && (target
== 0 || JUMP_LABEL (trial
) == target
)
2238 && (next_trial
= next_active_insn (JUMP_LABEL (trial
))) != 0
2239 && ! (NONJUMP_INSN_P (next_trial
)
2240 && GET_CODE (PATTERN (next_trial
)) == SEQUENCE
)
2241 && !JUMP_P (next_trial
)
2242 && ! insn_references_resource_p (next_trial
, &set
, true)
2243 && ! insn_sets_resource_p (next_trial
, &set
, true)
2244 && ! insn_sets_resource_p (next_trial
, &needed
, true)
2246 && ! reg_mentioned_p (cc0_rtx
, PATTERN (next_trial
))
2248 && ! (maybe_never
&& may_trap_or_fault_p (PATTERN (next_trial
)))
2249 && (next_trial
= try_split (PATTERN (next_trial
), next_trial
, 0))
2250 && eligible_for_delay (insn
, slots_filled
, next_trial
, flags
)
2251 && ! can_throw_internal (trial
))
2253 /* See comment in relax_delay_slots about necessity of using
2254 next_real_insn here. */
2255 rtx new_label
= next_real_insn (next_trial
);
2258 new_label
= get_label_before (new_label
);
2260 new_label
= find_end_label (simple_return_rtx
);
2265 = add_to_delay_list (copy_delay_slot_insn (next_trial
),
2268 reorg_redirect_jump (trial
, new_label
);
2270 /* If we merged because we both jumped to the same place,
2271 redirect the original insn also. */
2273 reorg_redirect_jump (insn
, new_label
);
2278 /* If this is an unconditional jump, then try to get insns from the
2279 target of the jump. */
2281 && simplejump_p (insn
)
2282 && slots_filled
!= slots_to_fill
)
2284 = fill_slots_from_thread (insn
, const_true_rtx
,
2285 next_active_insn (JUMP_LABEL (insn
)),
2287 own_thread_p (JUMP_LABEL (insn
),
2288 JUMP_LABEL (insn
), 0),
2289 slots_to_fill
, &slots_filled
,
2293 unfilled_slots_base
[i
]
2294 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
2296 if (slots_to_fill
== slots_filled
)
2297 unfilled_slots_base
[i
] = 0;
2299 note_delay_statistics (slots_filled
, 0);
2303 /* Follow any unconditional jump at LABEL, for the purpose of redirecting JUMP;
2304 return the ultimate label reached by any such chain of jumps.
2305 Return a suitable return rtx if the chain ultimately leads to a
2307 If LABEL is not followed by a jump, return LABEL.
2308 If the chain loops or we can't find end, return LABEL,
2309 since that tells caller to avoid changing the insn.
2310 If the returned label is obtained by following a REG_CROSSING_JUMP
2311 jump, set *CROSSING to true, otherwise set it to false. */
2314 follow_jumps (rtx label
, rtx jump
, bool *crossing
)
2322 if (ANY_RETURN_P (label
))
2326 && (insn
= next_active_insn (value
)) != 0
2328 && JUMP_LABEL (insn
) != NULL_RTX
2329 && ((any_uncondjump_p (insn
) && onlyjump_p (insn
))
2330 || ANY_RETURN_P (PATTERN (insn
)))
2331 && (next
= NEXT_INSN (insn
))
2332 && BARRIER_P (next
));
2335 rtx this_label
= JUMP_LABEL (insn
);
2338 /* If we have found a cycle, make the insn jump to itself. */
2339 if (this_label
== label
)
2341 if (ANY_RETURN_P (this_label
))
2343 tem
= next_active_insn (this_label
);
2345 && (GET_CODE (PATTERN (tem
)) == ADDR_VEC
2346 || GET_CODE (PATTERN (tem
)) == ADDR_DIFF_VEC
))
2349 if (!targetm
.can_follow_jump (jump
, insn
))
2353 = find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
) != NULL_RTX
;
2361 /* Try to find insns to place in delay slots.
2363 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2364 or is an unconditional branch if CONDITION is const_true_rtx.
2365 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2367 THREAD is a flow-of-control, either the insns to be executed if the
2368 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2370 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2371 to see if any potential delay slot insns set things needed there.
2373 LIKELY is nonzero if it is extremely likely that the branch will be
2374 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2375 end of a loop back up to the top.
2377 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2378 thread. I.e., it is the fallthrough code of our jump or the target of the
2379 jump when we are the only jump going there.
2381 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2382 case, we can only take insns from the head of the thread for our delay
2383 slot. We then adjust the jump to point after the insns we have taken. */
2386 fill_slots_from_thread (rtx insn
, rtx condition
, rtx thread
,
2387 rtx opposite_thread
, int likely
, int thread_if_true
,
2388 int own_thread
, int slots_to_fill
,
2389 int *pslots_filled
, rtx delay_list
)
2392 struct resources opposite_needed
, set
, needed
;
2398 /* Validate our arguments. */
2399 gcc_assert(condition
!= const_true_rtx
|| thread_if_true
);
2400 gcc_assert(own_thread
|| thread_if_true
);
2402 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2404 /* If our thread is the end of subroutine, we can't get any delay
2406 if (thread
== NULL_RTX
|| ANY_RETURN_P (thread
))
2409 /* If this is an unconditional branch, nothing is needed at the
2410 opposite thread. Otherwise, compute what is needed there. */
2411 if (condition
== const_true_rtx
)
2412 CLEAR_RESOURCE (&opposite_needed
);
2414 mark_target_live_regs (get_insns (), opposite_thread
, &opposite_needed
);
2416 /* If the insn at THREAD can be split, do it here to avoid having to
2417 update THREAD and NEW_THREAD if it is done in the loop below. Also
2418 initialize NEW_THREAD. */
2420 new_thread
= thread
= try_split (PATTERN (thread
), thread
, 0);
2422 /* Scan insns at THREAD. We are looking for an insn that can be removed
2423 from THREAD (it neither sets nor references resources that were set
2424 ahead of it and it doesn't set anything needs by the insns ahead of
2425 it) and that either can be placed in an annulling insn or aren't
2426 needed at OPPOSITE_THREAD. */
2428 CLEAR_RESOURCE (&needed
);
2429 CLEAR_RESOURCE (&set
);
2431 /* If we do not own this thread, we must stop as soon as we find
2432 something that we can't put in a delay slot, since all we can do
2433 is branch into THREAD at a later point. Therefore, labels stop
2434 the search if this is not the `true' thread. */
2436 for (trial
= thread
;
2437 ! stop_search_p (trial
, ! thread_if_true
) && (! lose
|| own_thread
);
2438 trial
= next_nonnote_insn (trial
))
2442 /* If we have passed a label, we no longer own this thread. */
2443 if (LABEL_P (trial
))
2449 pat
= PATTERN (trial
);
2450 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2453 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2454 don't separate or copy insns that set and use CC0. */
2455 if (! insn_references_resource_p (trial
, &set
, true)
2456 && ! insn_sets_resource_p (trial
, &set
, true)
2457 && ! insn_sets_resource_p (trial
, &needed
, true)
2459 && ! (reg_mentioned_p (cc0_rtx
, pat
)
2460 && (! own_thread
|| ! sets_cc0_p (pat
)))
2462 && ! can_throw_internal (trial
))
2466 /* If TRIAL is redundant with some insn before INSN, we don't
2467 actually need to add it to the delay list; we can merely pretend
2469 if ((prior_insn
= redundant_insn (trial
, insn
, delay_list
)))
2471 fix_reg_dead_note (prior_insn
, insn
);
2474 update_block (trial
, thread
);
2475 if (trial
== thread
)
2477 thread
= next_active_insn (thread
);
2478 if (new_thread
== trial
)
2479 new_thread
= thread
;
2482 delete_related_insns (trial
);
2486 update_reg_unused_notes (prior_insn
, trial
);
2487 new_thread
= next_active_insn (trial
);
2493 /* There are two ways we can win: If TRIAL doesn't set anything
2494 needed at the opposite thread and can't trap, or if it can
2495 go into an annulled delay slot. */
2497 && (condition
== const_true_rtx
2498 || (! insn_sets_resource_p (trial
, &opposite_needed
, true)
2499 && ! may_trap_or_fault_p (pat
)
2500 && ! RTX_FRAME_RELATED_P (trial
))))
2503 trial
= try_split (pat
, trial
, 0);
2504 if (new_thread
== old_trial
)
2506 if (thread
== old_trial
)
2508 pat
= PATTERN (trial
);
2509 if (eligible_for_delay (insn
, *pslots_filled
, trial
, flags
))
2513 #ifdef ANNUL_IFTRUE_SLOTS
2516 #ifdef ANNUL_IFFALSE_SLOTS
2522 trial
= try_split (pat
, trial
, 0);
2523 if (new_thread
== old_trial
)
2525 if (thread
== old_trial
)
2527 pat
= PATTERN (trial
);
2528 if ((must_annul
|| delay_list
== NULL
) && (thread_if_true
2529 ? check_annul_list_true_false (0, delay_list
)
2530 && eligible_for_annul_false (insn
, *pslots_filled
, trial
, flags
)
2531 : check_annul_list_true_false (1, delay_list
)
2532 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
2540 if (reg_mentioned_p (cc0_rtx
, pat
))
2541 link_cc0_insns (trial
);
2544 /* If we own this thread, delete the insn. If this is the
2545 destination of a branch, show that a basic block status
2546 may have been updated. In any case, mark the new
2547 starting point of this thread. */
2552 update_block (trial
, thread
);
2553 if (trial
== thread
)
2555 thread
= next_active_insn (thread
);
2556 if (new_thread
== trial
)
2557 new_thread
= thread
;
2560 /* We are moving this insn, not deleting it. We must
2561 temporarily increment the use count on any referenced
2562 label lest it be deleted by delete_related_insns. */
2563 for (note
= REG_NOTES (trial
);
2565 note
= XEXP (note
, 1))
2566 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2567 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2569 /* REG_LABEL_OPERAND could be
2570 NOTE_INSN_DELETED_LABEL too. */
2571 if (LABEL_P (XEXP (note
, 0)))
2572 LABEL_NUSES (XEXP (note
, 0))++;
2574 gcc_assert (REG_NOTE_KIND (note
)
2575 == REG_LABEL_OPERAND
);
2577 if (jump_to_label_p (trial
))
2578 LABEL_NUSES (JUMP_LABEL (trial
))++;
2580 delete_related_insns (trial
);
2582 for (note
= REG_NOTES (trial
);
2584 note
= XEXP (note
, 1))
2585 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2586 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2588 /* REG_LABEL_OPERAND could be
2589 NOTE_INSN_DELETED_LABEL too. */
2590 if (LABEL_P (XEXP (note
, 0)))
2591 LABEL_NUSES (XEXP (note
, 0))--;
2593 gcc_assert (REG_NOTE_KIND (note
)
2594 == REG_LABEL_OPERAND
);
2596 if (jump_to_label_p (trial
))
2597 LABEL_NUSES (JUMP_LABEL (trial
))--;
2600 new_thread
= next_active_insn (trial
);
2602 temp
= own_thread
? trial
: copy_delay_slot_insn (trial
);
2604 INSN_FROM_TARGET_P (temp
) = 1;
2606 delay_list
= add_to_delay_list (temp
, delay_list
);
2608 if (slots_to_fill
== ++(*pslots_filled
))
2610 /* Even though we have filled all the slots, we
2611 may be branching to a location that has a
2612 redundant insn. Skip any if so. */
2613 while (new_thread
&& ! own_thread
2614 && ! insn_sets_resource_p (new_thread
, &set
, true)
2615 && ! insn_sets_resource_p (new_thread
, &needed
,
2617 && ! insn_references_resource_p (new_thread
,
2620 = redundant_insn (new_thread
, insn
,
2623 /* We know we do not own the thread, so no need
2624 to call update_block and delete_insn. */
2625 fix_reg_dead_note (prior_insn
, insn
);
2626 update_reg_unused_notes (prior_insn
, new_thread
);
2627 new_thread
= next_active_insn (new_thread
);
2637 /* This insn can't go into a delay slot. */
2639 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2640 mark_referenced_resources (trial
, &needed
, true);
2642 /* Ensure we don't put insns between the setting of cc and the comparison
2643 by moving a setting of cc into an earlier delay slot since these insns
2644 could clobber the condition code. */
2647 /* If this insn is a register-register copy and the next insn has
2648 a use of our destination, change it to use our source. That way,
2649 it will become a candidate for our delay slot the next time
2650 through this loop. This case occurs commonly in loops that
2653 We could check for more complex cases than those tested below,
2654 but it doesn't seem worth it. It might also be a good idea to try
2655 to swap the two insns. That might do better.
2657 We can't do this if the next insn modifies our destination, because
2658 that would make the replacement into the insn invalid. We also can't
2659 do this if it modifies our source, because it might be an earlyclobber
2660 operand. This latter test also prevents updating the contents of
2661 a PRE_INC. We also can't do this if there's overlap of source and
2662 destination. Overlap may happen for larger-than-register-size modes. */
2664 if (NONJUMP_INSN_P (trial
) && GET_CODE (pat
) == SET
2665 && REG_P (SET_SRC (pat
))
2666 && REG_P (SET_DEST (pat
))
2667 && !reg_overlap_mentioned_p (SET_DEST (pat
), SET_SRC (pat
)))
2669 rtx next
= next_nonnote_insn (trial
);
2671 if (next
&& NONJUMP_INSN_P (next
)
2672 && GET_CODE (PATTERN (next
)) != USE
2673 && ! reg_set_p (SET_DEST (pat
), next
)
2674 && ! reg_set_p (SET_SRC (pat
), next
)
2675 && reg_referenced_p (SET_DEST (pat
), PATTERN (next
))
2676 && ! modified_in_p (SET_DEST (pat
), next
))
2677 validate_replace_rtx (SET_DEST (pat
), SET_SRC (pat
), next
);
2681 /* If we stopped on a branch insn that has delay slots, see if we can
2682 steal some of the insns in those slots. */
2683 if (trial
&& NONJUMP_INSN_P (trial
)
2684 && GET_CODE (PATTERN (trial
)) == SEQUENCE
2685 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0)))
2687 /* If this is the `true' thread, we will want to follow the jump,
2688 so we can only do this if we have taken everything up to here. */
2689 if (thread_if_true
&& trial
== new_thread
)
2692 = steal_delay_list_from_target (insn
, condition
, PATTERN (trial
),
2693 delay_list
, &set
, &needed
,
2694 &opposite_needed
, slots_to_fill
,
2695 pslots_filled
, &must_annul
,
2697 /* If we owned the thread and are told that it branched
2698 elsewhere, make sure we own the thread at the new location. */
2699 if (own_thread
&& trial
!= new_thread
)
2700 own_thread
= own_thread_p (new_thread
, new_thread
, 0);
2702 else if (! thread_if_true
)
2704 = steal_delay_list_from_fallthrough (insn
, condition
,
2706 delay_list
, &set
, &needed
,
2707 &opposite_needed
, slots_to_fill
,
2708 pslots_filled
, &must_annul
);
2711 /* If we haven't found anything for this delay slot and it is very
2712 likely that the branch will be taken, see if the insn at our target
2713 increments or decrements a register with an increment that does not
2714 depend on the destination register. If so, try to place the opposite
2715 arithmetic insn after the jump insn and put the arithmetic insn in the
2716 delay slot. If we can't do this, return. */
2717 if (delay_list
== 0 && likely
2718 && new_thread
&& !ANY_RETURN_P (new_thread
)
2719 && NONJUMP_INSN_P (new_thread
)
2720 && !RTX_FRAME_RELATED_P (new_thread
)
2721 && GET_CODE (PATTERN (new_thread
)) != ASM_INPUT
2722 && asm_noperands (PATTERN (new_thread
)) < 0)
2724 rtx pat
= PATTERN (new_thread
);
2729 pat
= PATTERN (trial
);
2731 if (!NONJUMP_INSN_P (trial
)
2732 || GET_CODE (pat
) != SET
2733 || ! eligible_for_delay (insn
, 0, trial
, flags
)
2734 || can_throw_internal (trial
))
2737 dest
= SET_DEST (pat
), src
= SET_SRC (pat
);
2738 if ((GET_CODE (src
) == PLUS
|| GET_CODE (src
) == MINUS
)
2739 && rtx_equal_p (XEXP (src
, 0), dest
)
2740 && (!FLOAT_MODE_P (GET_MODE (src
))
2741 || flag_unsafe_math_optimizations
)
2742 && ! reg_overlap_mentioned_p (dest
, XEXP (src
, 1))
2743 && ! side_effects_p (pat
))
2745 rtx other
= XEXP (src
, 1);
2749 /* If this is a constant adjustment, use the same code with
2750 the negated constant. Otherwise, reverse the sense of the
2752 if (CONST_INT_P (other
))
2753 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
), GET_MODE (src
), dest
,
2754 negate_rtx (GET_MODE (src
), other
));
2756 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
) == PLUS
? MINUS
: PLUS
,
2757 GET_MODE (src
), dest
, other
);
2759 ninsn
= emit_insn_after (gen_rtx_SET (VOIDmode
, dest
, new_arith
),
2762 if (recog_memoized (ninsn
) < 0
2763 || (extract_insn (ninsn
), ! constrain_operands (1)))
2765 delete_related_insns (ninsn
);
2771 update_block (trial
, thread
);
2772 if (trial
== thread
)
2774 thread
= next_active_insn (thread
);
2775 if (new_thread
== trial
)
2776 new_thread
= thread
;
2778 delete_related_insns (trial
);
2781 new_thread
= next_active_insn (trial
);
2783 ninsn
= own_thread
? trial
: copy_delay_slot_insn (trial
);
2785 INSN_FROM_TARGET_P (ninsn
) = 1;
2787 delay_list
= add_to_delay_list (ninsn
, NULL_RTX
);
2792 if (delay_list
&& must_annul
)
2793 INSN_ANNULLED_BRANCH_P (insn
) = 1;
2795 /* If we are to branch into the middle of this thread, find an appropriate
2796 label or make a new one if none, and redirect INSN to it. If we hit the
2797 end of the function, use the end-of-function label. */
2798 if (new_thread
!= thread
)
2801 bool crossing
= false;
2803 gcc_assert (thread_if_true
);
2805 if (new_thread
&& simplejump_or_return_p (new_thread
)
2806 && redirect_with_delay_list_safe_p (insn
,
2807 JUMP_LABEL (new_thread
),
2809 new_thread
= follow_jumps (JUMP_LABEL (new_thread
), insn
, &crossing
);
2811 if (ANY_RETURN_P (new_thread
))
2812 label
= find_end_label (new_thread
);
2813 else if (LABEL_P (new_thread
))
2816 label
= get_label_before (new_thread
);
2820 reorg_redirect_jump (insn
, label
);
2822 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
2829 /* Make another attempt to find insns to place in delay slots.
2831 We previously looked for insns located in front of the delay insn
2832 and, for non-jump delay insns, located behind the delay insn.
2834 Here only try to schedule jump insns and try to move insns from either
2835 the target or the following insns into the delay slot. If annulling is
2836 supported, we will be likely to do this. Otherwise, we can do this only
2840 fill_eager_delay_slots (void)
2844 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
2846 for (i
= 0; i
< num_unfilled_slots
; i
++)
2849 rtx target_label
, insn_at_target
, fallthrough_insn
;
2852 int own_fallthrough
;
2853 int prediction
, slots_to_fill
, slots_filled
;
2855 insn
= unfilled_slots_base
[i
];
2857 || INSN_DELETED_P (insn
)
2859 || ! (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
2862 slots_to_fill
= num_delay_slots (insn
);
2863 /* Some machine description have defined instructions to have
2864 delay slots only in certain circumstances which may depend on
2865 nearby insns (which change due to reorg's actions).
2867 For example, the PA port normally has delay slots for unconditional
2870 However, the PA port claims such jumps do not have a delay slot
2871 if they are immediate successors of certain CALL_INSNs. This
2872 allows the port to favor filling the delay slot of the call with
2873 the unconditional jump. */
2874 if (slots_to_fill
== 0)
2878 target_label
= JUMP_LABEL (insn
);
2879 condition
= get_branch_condition (insn
, target_label
);
2884 /* Get the next active fallthrough and target insns and see if we own
2885 them. Then see whether the branch is likely true. We don't need
2886 to do a lot of this for unconditional branches. */
2888 insn_at_target
= first_active_target_insn (target_label
);
2889 own_target
= own_thread_p (target_label
, target_label
, 0);
2891 if (condition
== const_true_rtx
)
2893 own_fallthrough
= 0;
2894 fallthrough_insn
= 0;
2899 fallthrough_insn
= next_active_insn (insn
);
2900 own_fallthrough
= own_thread_p (NEXT_INSN (insn
), NULL_RTX
, 1);
2901 prediction
= mostly_true_jump (insn
);
2904 /* If this insn is expected to branch, first try to get insns from our
2905 target, then our fallthrough insns. If it is not expected to branch,
2906 try the other order. */
2911 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
2912 fallthrough_insn
, prediction
== 2, 1,
2914 slots_to_fill
, &slots_filled
, delay_list
);
2916 if (delay_list
== 0 && own_fallthrough
)
2918 /* Even though we didn't find anything for delay slots,
2919 we might have found a redundant insn which we deleted
2920 from the thread that was filled. So we have to recompute
2921 the next insn at the target. */
2922 target_label
= JUMP_LABEL (insn
);
2923 insn_at_target
= first_active_target_insn (target_label
);
2926 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
2927 insn_at_target
, 0, 0,
2929 slots_to_fill
, &slots_filled
,
2935 if (own_fallthrough
)
2937 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
2938 insn_at_target
, 0, 0,
2940 slots_to_fill
, &slots_filled
,
2943 if (delay_list
== 0)
2945 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
2946 next_active_insn (insn
), 0, 1,
2948 slots_to_fill
, &slots_filled
,
2953 unfilled_slots_base
[i
]
2954 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
2956 if (slots_to_fill
== slots_filled
)
2957 unfilled_slots_base
[i
] = 0;
2959 note_delay_statistics (slots_filled
, 1);
2963 static void delete_computation (rtx insn
);
2965 /* Recursively delete prior insns that compute the value (used only by INSN
2966 which the caller is deleting) stored in the register mentioned by NOTE
2967 which is a REG_DEAD note associated with INSN. */
2970 delete_prior_computation (rtx note
, rtx insn
)
2973 rtx reg
= XEXP (note
, 0);
2975 for (our_prev
= prev_nonnote_insn (insn
);
2976 our_prev
&& (NONJUMP_INSN_P (our_prev
)
2977 || CALL_P (our_prev
));
2978 our_prev
= prev_nonnote_insn (our_prev
))
2980 rtx pat
= PATTERN (our_prev
);
2982 /* If we reach a CALL which is not calling a const function
2983 or the callee pops the arguments, then give up. */
2984 if (CALL_P (our_prev
)
2985 && (! RTL_CONST_CALL_P (our_prev
)
2986 || GET_CODE (pat
) != SET
|| GET_CODE (SET_SRC (pat
)) != CALL
))
2989 /* If we reach a SEQUENCE, it is too complex to try to
2990 do anything with it, so give up. We can be run during
2991 and after reorg, so SEQUENCE rtl can legitimately show
2993 if (GET_CODE (pat
) == SEQUENCE
)
2996 if (GET_CODE (pat
) == USE
2997 && NONJUMP_INSN_P (XEXP (pat
, 0)))
2998 /* reorg creates USEs that look like this. We leave them
2999 alone because reorg needs them for its own purposes. */
3002 if (reg_set_p (reg
, pat
))
3004 if (side_effects_p (pat
) && !CALL_P (our_prev
))
3007 if (GET_CODE (pat
) == PARALLEL
)
3009 /* If we find a SET of something else, we can't
3014 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3016 rtx part
= XVECEXP (pat
, 0, i
);
3018 if (GET_CODE (part
) == SET
3019 && SET_DEST (part
) != reg
)
3023 if (i
== XVECLEN (pat
, 0))
3024 delete_computation (our_prev
);
3026 else if (GET_CODE (pat
) == SET
3027 && REG_P (SET_DEST (pat
)))
3029 int dest_regno
= REGNO (SET_DEST (pat
));
3030 int dest_endregno
= END_REGNO (SET_DEST (pat
));
3031 int regno
= REGNO (reg
);
3032 int endregno
= END_REGNO (reg
);
3034 if (dest_regno
>= regno
3035 && dest_endregno
<= endregno
)
3036 delete_computation (our_prev
);
3038 /* We may have a multi-word hard register and some, but not
3039 all, of the words of the register are needed in subsequent
3040 insns. Write REG_UNUSED notes for those parts that were not
3042 else if (dest_regno
<= regno
3043 && dest_endregno
>= endregno
)
3047 add_reg_note (our_prev
, REG_UNUSED
, reg
);
3049 for (i
= dest_regno
; i
< dest_endregno
; i
++)
3050 if (! find_regno_note (our_prev
, REG_UNUSED
, i
))
3053 if (i
== dest_endregno
)
3054 delete_computation (our_prev
);
3061 /* If PAT references the register that dies here, it is an
3062 additional use. Hence any prior SET isn't dead. However, this
3063 insn becomes the new place for the REG_DEAD note. */
3064 if (reg_overlap_mentioned_p (reg
, pat
))
3066 XEXP (note
, 1) = REG_NOTES (our_prev
);
3067 REG_NOTES (our_prev
) = note
;
3073 /* Delete INSN and recursively delete insns that compute values used only
3074 by INSN. This uses the REG_DEAD notes computed during flow analysis.
3076 Look at all our REG_DEAD notes. If a previous insn does nothing other
3077 than set a register that dies in this insn, we can delete that insn
3080 On machines with CC0, if CC0 is used in this insn, we may be able to
3081 delete the insn that set it. */
3084 delete_computation (rtx insn
)
3089 if (reg_referenced_p (cc0_rtx
, PATTERN (insn
)))
3091 rtx prev
= prev_nonnote_insn (insn
);
3092 /* We assume that at this stage
3093 CC's are always set explicitly
3094 and always immediately before the jump that
3095 will use them. So if the previous insn
3096 exists to set the CC's, delete it
3097 (unless it performs auto-increments, etc.). */
3098 if (prev
&& NONJUMP_INSN_P (prev
)
3099 && sets_cc0_p (PATTERN (prev
)))
3101 if (sets_cc0_p (PATTERN (prev
)) > 0
3102 && ! side_effects_p (PATTERN (prev
)))
3103 delete_computation (prev
);
3105 /* Otherwise, show that cc0 won't be used. */
3106 add_reg_note (prev
, REG_UNUSED
, cc0_rtx
);
3111 for (note
= REG_NOTES (insn
); note
; note
= next
)
3113 next
= XEXP (note
, 1);
3115 if (REG_NOTE_KIND (note
) != REG_DEAD
3116 /* Verify that the REG_NOTE is legitimate. */
3117 || !REG_P (XEXP (note
, 0)))
3120 delete_prior_computation (note
, insn
);
3123 delete_related_insns (insn
);
3126 /* If all INSN does is set the pc, delete it,
3127 and delete the insn that set the condition codes for it
3128 if that's what the previous thing was. */
3131 delete_jump (rtx insn
)
3133 rtx set
= single_set (insn
);
3135 if (set
&& GET_CODE (SET_DEST (set
)) == PC
)
3136 delete_computation (insn
);
3140 label_before_next_insn (rtx x
, rtx scan_limit
)
3142 rtx insn
= next_active_insn (x
);
3145 insn
= PREV_INSN (insn
);
3146 if (insn
== scan_limit
|| insn
== NULL_RTX
)
3155 /* Once we have tried two ways to fill a delay slot, make a pass over the
3156 code to try to improve the results and to do such things as more jump
3160 relax_delay_slots (rtx first
)
3162 rtx insn
, next
, pat
;
3163 rtx trial
, delay_insn
, target_label
;
3165 /* Look at every JUMP_INSN and see if we can improve it. */
3166 for (insn
= first
; insn
; insn
= next
)
3171 next
= next_active_insn (insn
);
3173 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3174 the next insn, or jumps to a label that is not the last of a
3175 group of consecutive labels. */
3177 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3178 && !ANY_RETURN_P (target_label
= JUMP_LABEL (insn
)))
3181 = skip_consecutive_labels (follow_jumps (target_label
, insn
,
3183 if (ANY_RETURN_P (target_label
))
3184 target_label
= find_end_label (target_label
);
3186 if (target_label
&& next_active_insn (target_label
) == next
3187 && ! condjump_in_parallel_p (insn
))
3193 if (target_label
&& target_label
!= JUMP_LABEL (insn
))
3195 reorg_redirect_jump (insn
, target_label
);
3197 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
3200 /* See if this jump conditionally branches around an unconditional
3201 jump. If so, invert this jump and point it to the target of the
3203 if (next
&& simplejump_or_return_p (next
)
3204 && any_condjump_p (insn
)
3206 && next_active_insn (target_label
) == next_active_insn (next
)
3207 && no_labels_between_p (insn
, next
))
3209 rtx label
= JUMP_LABEL (next
);
3211 /* Be careful how we do this to avoid deleting code or
3212 labels that are momentarily dead. See similar optimization
3215 We also need to ensure we properly handle the case when
3216 invert_jump fails. */
3218 ++LABEL_NUSES (target_label
);
3219 if (!ANY_RETURN_P (label
))
3220 ++LABEL_NUSES (label
);
3222 if (invert_jump (insn
, label
, 1))
3224 delete_related_insns (next
);
3228 if (!ANY_RETURN_P (label
))
3229 --LABEL_NUSES (label
);
3231 if (--LABEL_NUSES (target_label
) == 0)
3232 delete_related_insns (target_label
);
3238 /* If this is an unconditional jump and the previous insn is a
3239 conditional jump, try reversing the condition of the previous
3240 insn and swapping our targets. The next pass might be able to
3243 Don't do this if we expect the conditional branch to be true, because
3244 we would then be making the more common case longer. */
3246 if (simplejump_or_return_p (insn
)
3247 && (other
= prev_active_insn (insn
)) != 0
3248 && any_condjump_p (other
)
3249 && no_labels_between_p (other
, insn
)
3250 && 0 > mostly_true_jump (other
))
3252 rtx other_target
= JUMP_LABEL (other
);
3253 target_label
= JUMP_LABEL (insn
);
3255 if (invert_jump (other
, target_label
, 0))
3256 reorg_redirect_jump (insn
, other_target
);
3259 /* Now look only at cases where we have a filled delay slot. */
3260 if (!NONJUMP_INSN_P (insn
) || GET_CODE (PATTERN (insn
)) != SEQUENCE
)
3263 pat
= PATTERN (insn
);
3264 delay_insn
= XVECEXP (pat
, 0, 0);
3266 /* See if the first insn in the delay slot is redundant with some
3267 previous insn. Remove it from the delay slot if so; then set up
3268 to reprocess this insn. */
3269 if (redundant_insn (XVECEXP (pat
, 0, 1), delay_insn
, 0))
3271 delete_from_delay_slot (XVECEXP (pat
, 0, 1));
3272 next
= prev_active_insn (next
);
3276 /* See if we have a RETURN insn with a filled delay slot followed
3277 by a RETURN insn with an unfilled a delay slot. If so, we can delete
3278 the first RETURN (but not its delay insn). This gives the same
3279 effect in fewer instructions.
3281 Only do so if optimizing for size since this results in slower, but
3283 if (optimize_function_for_size_p (cfun
)
3284 && ANY_RETURN_P (PATTERN (delay_insn
))
3287 && PATTERN (next
) == PATTERN (delay_insn
))
3292 /* Delete the RETURN and just execute the delay list insns.
3294 We do this by deleting the INSN containing the SEQUENCE, then
3295 re-emitting the insns separately, and then deleting the RETURN.
3296 This allows the count of the jump target to be properly
3299 Note that we need to change the INSN_UID of the re-emitted insns
3300 since it is used to hash the insns for mark_target_live_regs and
3301 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3303 Clear the from target bit, since these insns are no longer
3305 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3306 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3308 trial
= PREV_INSN (insn
);
3309 delete_related_insns (insn
);
3310 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3311 add_insn_after (delay_insn
, trial
, NULL
);
3313 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3314 after
= emit_copy_of_insn_after (XVECEXP (pat
, 0, i
), after
);
3315 delete_scheduled_jump (delay_insn
);
3319 /* Now look only at the cases where we have a filled JUMP_INSN. */
3320 if (!JUMP_P (delay_insn
)
3321 || !(condjump_p (delay_insn
) || condjump_in_parallel_p (delay_insn
)))
3324 target_label
= JUMP_LABEL (delay_insn
);
3325 if (target_label
&& ANY_RETURN_P (target_label
))
3328 /* If this jump goes to another unconditional jump, thread it, but
3329 don't convert a jump into a RETURN here. */
3330 trial
= skip_consecutive_labels (follow_jumps (target_label
, delay_insn
,
3332 if (ANY_RETURN_P (trial
))
3333 trial
= find_end_label (trial
);
3335 if (trial
&& trial
!= target_label
3336 && redirect_with_delay_slots_safe_p (delay_insn
, trial
, insn
))
3338 reorg_redirect_jump (delay_insn
, trial
);
3339 target_label
= trial
;
3341 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
3344 /* If the first insn at TARGET_LABEL is redundant with a previous
3345 insn, redirect the jump to the following insn and process again.
3346 We use next_real_insn instead of next_active_insn so we
3347 don't skip USE-markers, or we'll end up with incorrect
3349 trial
= next_real_insn (target_label
);
3350 if (trial
&& GET_CODE (PATTERN (trial
)) != SEQUENCE
3351 && redundant_insn (trial
, insn
, 0)
3352 && ! can_throw_internal (trial
))
3354 /* Figure out where to emit the special USE insn so we don't
3355 later incorrectly compute register live/death info. */
3356 rtx tmp
= next_active_insn (trial
);
3358 tmp
= find_end_label (simple_return_rtx
);
3362 /* Insert the special USE insn and update dataflow info. */
3363 update_block (trial
, tmp
);
3365 /* Now emit a label before the special USE insn, and
3366 redirect our jump to the new label. */
3367 target_label
= get_label_before (PREV_INSN (tmp
));
3368 reorg_redirect_jump (delay_insn
, target_label
);
3374 /* Similarly, if it is an unconditional jump with one insn in its
3375 delay list and that insn is redundant, thread the jump. */
3376 if (trial
&& GET_CODE (PATTERN (trial
)) == SEQUENCE
3377 && XVECLEN (PATTERN (trial
), 0) == 2
3378 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
3379 && simplejump_or_return_p (XVECEXP (PATTERN (trial
), 0, 0))
3380 && redundant_insn (XVECEXP (PATTERN (trial
), 0, 1), insn
, 0))
3382 target_label
= JUMP_LABEL (XVECEXP (PATTERN (trial
), 0, 0));
3383 if (ANY_RETURN_P (target_label
))
3384 target_label
= find_end_label (target_label
);
3387 && redirect_with_delay_slots_safe_p (delay_insn
, target_label
,
3390 reorg_redirect_jump (delay_insn
, target_label
);
3396 /* See if we have a simple (conditional) jump that is useless. */
3397 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3398 && ! condjump_in_parallel_p (delay_insn
)
3399 && prev_active_insn (target_label
) == insn
3400 && ! BARRIER_P (prev_nonnote_insn (target_label
))
3402 /* If the last insn in the delay slot sets CC0 for some insn,
3403 various code assumes that it is in a delay slot. We could
3404 put it back where it belonged and delete the register notes,
3405 but it doesn't seem worthwhile in this uncommon case. */
3406 && ! find_reg_note (XVECEXP (pat
, 0, XVECLEN (pat
, 0) - 1),
3407 REG_CC_USER
, NULL_RTX
)
3414 /* All this insn does is execute its delay list and jump to the
3415 following insn. So delete the jump and just execute the delay
3418 We do this by deleting the INSN containing the SEQUENCE, then
3419 re-emitting the insns separately, and then deleting the jump.
3420 This allows the count of the jump target to be properly
3423 Note that we need to change the INSN_UID of the re-emitted insns
3424 since it is used to hash the insns for mark_target_live_regs and
3425 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3427 Clear the from target bit, since these insns are no longer
3429 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3430 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3432 trial
= PREV_INSN (insn
);
3433 delete_related_insns (insn
);
3434 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3435 add_insn_after (delay_insn
, trial
, NULL
);
3437 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3438 after
= emit_copy_of_insn_after (XVECEXP (pat
, 0, i
), after
);
3439 delete_scheduled_jump (delay_insn
);
3443 /* See if this is an unconditional jump around a single insn which is
3444 identical to the one in its delay slot. In this case, we can just
3445 delete the branch and the insn in its delay slot. */
3446 if (next
&& NONJUMP_INSN_P (next
)
3447 && label_before_next_insn (next
, insn
) == target_label
3448 && simplejump_p (insn
)
3449 && XVECLEN (pat
, 0) == 2
3450 && rtx_equal_p (PATTERN (next
), PATTERN (XVECEXP (pat
, 0, 1))))
3452 delete_related_insns (insn
);
3456 /* See if this jump (with its delay slots) conditionally branches
3457 around an unconditional jump (without delay slots). If so, invert
3458 this jump and point it to the target of the second jump. We cannot
3459 do this for annulled jumps, though. Again, don't convert a jump to
3461 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3462 && any_condjump_p (delay_insn
)
3463 && next
&& simplejump_or_return_p (next
)
3464 && next_active_insn (target_label
) == next_active_insn (next
)
3465 && no_labels_between_p (insn
, next
))
3467 rtx label
= JUMP_LABEL (next
);
3468 rtx old_label
= JUMP_LABEL (delay_insn
);
3470 if (ANY_RETURN_P (label
))
3471 label
= find_end_label (label
);
3473 /* find_end_label can generate a new label. Check this first. */
3475 && no_labels_between_p (insn
, next
)
3476 && redirect_with_delay_slots_safe_p (delay_insn
, label
, insn
))
3478 /* Be careful how we do this to avoid deleting code or labels
3479 that are momentarily dead. See similar optimization in
3482 ++LABEL_NUSES (old_label
);
3484 if (invert_jump (delay_insn
, label
, 1))
3488 /* Must update the INSN_FROM_TARGET_P bits now that
3489 the branch is reversed, so that mark_target_live_regs
3490 will handle the delay slot insn correctly. */
3491 for (i
= 1; i
< XVECLEN (PATTERN (insn
), 0); i
++)
3493 rtx slot
= XVECEXP (PATTERN (insn
), 0, i
);
3494 INSN_FROM_TARGET_P (slot
) = ! INSN_FROM_TARGET_P (slot
);
3497 delete_related_insns (next
);
3501 if (old_label
&& --LABEL_NUSES (old_label
) == 0)
3502 delete_related_insns (old_label
);
3507 /* If we own the thread opposite the way this insn branches, see if we
3508 can merge its delay slots with following insns. */
3509 if (INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3510 && own_thread_p (NEXT_INSN (insn
), 0, 1))
3511 try_merge_delay_insns (insn
, next
);
3512 else if (! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3513 && own_thread_p (target_label
, target_label
, 0))
3514 try_merge_delay_insns (insn
, next_active_insn (target_label
));
3516 /* If we get here, we haven't deleted INSN. But we may have deleted
3517 NEXT, so recompute it. */
3518 next
= next_active_insn (insn
);
3523 /* Look for filled jumps to the end of function label. We can try to convert
3524 them into RETURN insns if the insns in the delay slot are valid for the
3528 make_return_insns (rtx first
)
3530 rtx insn
, jump_insn
, pat
;
3531 rtx real_return_label
= function_return_label
;
3532 rtx real_simple_return_label
= function_simple_return_label
;
3535 /* See if there is a RETURN insn in the function other than the one we
3536 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3537 into a RETURN to jump to it. */
3538 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3539 if (JUMP_P (insn
) && ANY_RETURN_P (PATTERN (insn
)))
3541 rtx t
= get_label_before (insn
);
3542 if (PATTERN (insn
) == ret_rtx
)
3543 real_return_label
= t
;
3545 real_simple_return_label
= t
;
3549 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3550 was equal to END_OF_FUNCTION_LABEL. */
3551 if (real_return_label
)
3552 LABEL_NUSES (real_return_label
)++;
3553 if (real_simple_return_label
)
3554 LABEL_NUSES (real_simple_return_label
)++;
3556 /* Clear the list of insns to fill so we can use it. */
3557 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3559 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3562 rtx kind
, real_label
;
3564 /* Only look at filled JUMP_INSNs that go to the end of function
3566 if (!NONJUMP_INSN_P (insn
)
3567 || GET_CODE (PATTERN (insn
)) != SEQUENCE
3568 || !jump_to_label_p (XVECEXP (PATTERN (insn
), 0, 0)))
3571 if (JUMP_LABEL (XVECEXP (PATTERN (insn
), 0, 0)) == function_return_label
)
3574 real_label
= real_return_label
;
3576 else if (JUMP_LABEL (XVECEXP (PATTERN (insn
), 0, 0))
3577 == function_simple_return_label
)
3579 kind
= simple_return_rtx
;
3580 real_label
= real_simple_return_label
;
3585 pat
= PATTERN (insn
);
3586 jump_insn
= XVECEXP (pat
, 0, 0);
3588 /* If we can't make the jump into a RETURN, try to redirect it to the best
3589 RETURN and go on to the next insn. */
3590 if (!reorg_redirect_jump (jump_insn
, kind
))
3592 /* Make sure redirecting the jump will not invalidate the delay
3594 if (redirect_with_delay_slots_safe_p (jump_insn
, real_label
, insn
))
3595 reorg_redirect_jump (jump_insn
, real_label
);
3599 /* See if this RETURN can accept the insns current in its delay slot.
3600 It can if it has more or an equal number of slots and the contents
3601 of each is valid. */
3603 flags
= get_jump_flags (jump_insn
, JUMP_LABEL (jump_insn
));
3604 slots
= num_delay_slots (jump_insn
);
3605 if (slots
>= XVECLEN (pat
, 0) - 1)
3607 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3609 #ifdef ANNUL_IFFALSE_SLOTS
3610 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3611 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3612 ? eligible_for_annul_false (jump_insn
, i
- 1,
3613 XVECEXP (pat
, 0, i
), flags
) :
3615 #ifdef ANNUL_IFTRUE_SLOTS
3616 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3617 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3618 ? eligible_for_annul_true (jump_insn
, i
- 1,
3619 XVECEXP (pat
, 0, i
), flags
) :
3621 eligible_for_delay (jump_insn
, i
- 1,
3622 XVECEXP (pat
, 0, i
), flags
)))
3628 if (i
== XVECLEN (pat
, 0))
3631 /* We have to do something with this insn. If it is an unconditional
3632 RETURN, delete the SEQUENCE and output the individual insns,
3633 followed by the RETURN. Then set things up so we try to find
3634 insns for its delay slots, if it needs some. */
3635 if (ANY_RETURN_P (PATTERN (jump_insn
)))
3637 rtx prev
= PREV_INSN (insn
);
3639 delete_related_insns (insn
);
3640 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3641 prev
= emit_insn_after (PATTERN (XVECEXP (pat
, 0, i
)), prev
);
3643 insn
= emit_jump_insn_after (PATTERN (jump_insn
), prev
);
3644 emit_barrier_after (insn
);
3647 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3650 /* It is probably more efficient to keep this with its current
3651 delay slot as a branch to a RETURN. */
3652 reorg_redirect_jump (jump_insn
, real_label
);
3655 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3656 new delay slots we have created. */
3657 if (real_return_label
!= NULL_RTX
&& --LABEL_NUSES (real_return_label
) == 0)
3658 delete_related_insns (real_return_label
);
3659 if (real_simple_return_label
!= NULL_RTX
3660 && --LABEL_NUSES (real_simple_return_label
) == 0)
3661 delete_related_insns (real_simple_return_label
);
3663 fill_simple_delay_slots (1);
3664 fill_simple_delay_slots (0);
3667 /* Try to find insns to place in delay slots. */
3670 dbr_schedule (rtx first
)
3672 rtx insn
, next
, epilogue_insn
= 0;
3674 bool need_return_insns
;
3676 /* If the current function has no insns other than the prologue and
3677 epilogue, then do not try to fill any delay slots. */
3678 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
3681 /* Find the highest INSN_UID and allocate and initialize our map from
3682 INSN_UID's to position in code. */
3683 for (max_uid
= 0, insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3685 if (INSN_UID (insn
) > max_uid
)
3686 max_uid
= INSN_UID (insn
);
3688 && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3689 epilogue_insn
= insn
;
3692 uid_to_ruid
= XNEWVEC (int, max_uid
+ 1);
3693 for (i
= 0, insn
= first
; insn
; i
++, insn
= NEXT_INSN (insn
))
3694 uid_to_ruid
[INSN_UID (insn
)] = i
;
3696 /* Initialize the list of insns that need filling. */
3697 if (unfilled_firstobj
== 0)
3699 gcc_obstack_init (&unfilled_slots_obstack
);
3700 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3703 for (insn
= next_active_insn (first
); insn
; insn
= next_active_insn (insn
))
3708 INSN_ANNULLED_BRANCH_P (insn
) = 0;
3709 INSN_FROM_TARGET_P (insn
) = 0;
3711 /* Skip vector tables. We can't get attributes for them. */
3712 if (JUMP_TABLE_DATA_P (insn
))
3715 if (num_delay_slots (insn
) > 0)
3716 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3718 /* Ensure all jumps go to the last of a set of consecutive labels. */
3720 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3721 && !ANY_RETURN_P (JUMP_LABEL (insn
))
3722 && ((target
= skip_consecutive_labels (JUMP_LABEL (insn
)))
3723 != JUMP_LABEL (insn
)))
3724 redirect_jump (insn
, target
, 1);
3727 init_resource_info (epilogue_insn
);
3729 /* Show we haven't computed an end-of-function label yet. */
3730 function_return_label
= function_simple_return_label
= NULL_RTX
;
3732 /* Initialize the statistics for this function. */
3733 memset (num_insns_needing_delays
, 0, sizeof num_insns_needing_delays
);
3734 memset (num_filled_delays
, 0, sizeof num_filled_delays
);
3736 /* Now do the delay slot filling. Try everything twice in case earlier
3737 changes make more slots fillable. */
3739 for (reorg_pass_number
= 0;
3740 reorg_pass_number
< MAX_REORG_PASSES
;
3741 reorg_pass_number
++)
3743 fill_simple_delay_slots (1);
3744 fill_simple_delay_slots (0);
3745 fill_eager_delay_slots ();
3746 relax_delay_slots (first
);
3749 /* If we made an end of function label, indicate that it is now
3750 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3751 If it is now unused, delete it. */
3752 if (function_return_label
&& --LABEL_NUSES (function_return_label
) == 0)
3753 delete_related_insns (function_return_label
);
3754 if (function_simple_return_label
3755 && --LABEL_NUSES (function_simple_return_label
) == 0)
3756 delete_related_insns (function_simple_return_label
);
3758 need_return_insns
= false;
3760 need_return_insns
|= HAVE_return
&& function_return_label
!= 0;
3762 #ifdef HAVE_simple_return
3763 need_return_insns
|= HAVE_simple_return
&& function_simple_return_label
!= 0;
3765 if (need_return_insns
)
3766 make_return_insns (first
);
3768 /* Delete any USE insns made by update_block; subsequent passes don't need
3769 them or know how to deal with them. */
3770 for (insn
= first
; insn
; insn
= next
)
3772 next
= NEXT_INSN (insn
);
3774 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == USE
3775 && INSN_P (XEXP (PATTERN (insn
), 0)))
3776 next
= delete_related_insns (insn
);
3779 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3781 /* It is not clear why the line below is needed, but it does seem to be. */
3782 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3786 int i
, j
, need_comma
;
3787 int total_delay_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3788 int total_annul_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3790 for (reorg_pass_number
= 0;
3791 reorg_pass_number
< MAX_REORG_PASSES
;
3792 reorg_pass_number
++)
3794 fprintf (dump_file
, ";; Reorg pass #%d:\n", reorg_pass_number
+ 1);
3795 for (i
= 0; i
< NUM_REORG_FUNCTIONS
; i
++)
3798 fprintf (dump_file
, ";; Reorg function #%d\n", i
);
3800 fprintf (dump_file
, ";; %d insns needing delay slots\n;; ",
3801 num_insns_needing_delays
[i
][reorg_pass_number
]);
3803 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3804 if (num_filled_delays
[i
][j
][reorg_pass_number
])
3807 fprintf (dump_file
, ", ");
3809 fprintf (dump_file
, "%d got %d delays",
3810 num_filled_delays
[i
][j
][reorg_pass_number
], j
);
3812 fprintf (dump_file
, "\n");
3815 memset (total_delay_slots
, 0, sizeof total_delay_slots
);
3816 memset (total_annul_slots
, 0, sizeof total_annul_slots
);
3817 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3819 if (! INSN_DELETED_P (insn
)
3820 && NONJUMP_INSN_P (insn
)
3821 && GET_CODE (PATTERN (insn
)) != USE
3822 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3824 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
3827 j
= XVECLEN (PATTERN (insn
), 0) - 1;
3828 if (j
> MAX_DELAY_HISTOGRAM
)
3829 j
= MAX_DELAY_HISTOGRAM
;
3830 control
= XVECEXP (PATTERN (insn
), 0, 0);
3831 if (JUMP_P (control
) && INSN_ANNULLED_BRANCH_P (control
))
3832 total_annul_slots
[j
]++;
3834 total_delay_slots
[j
]++;
3836 else if (num_delay_slots (insn
) > 0)
3837 total_delay_slots
[0]++;
3840 fprintf (dump_file
, ";; Reorg totals: ");
3842 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3844 if (total_delay_slots
[j
])
3847 fprintf (dump_file
, ", ");
3849 fprintf (dump_file
, "%d got %d delays", total_delay_slots
[j
], j
);
3852 fprintf (dump_file
, "\n");
3853 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3854 fprintf (dump_file
, ";; Reorg annuls: ");
3856 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3858 if (total_annul_slots
[j
])
3861 fprintf (dump_file
, ", ");
3863 fprintf (dump_file
, "%d got %d delays", total_annul_slots
[j
], j
);
3866 fprintf (dump_file
, "\n");
3868 fprintf (dump_file
, "\n");
3871 free_resource_info ();
3873 crtl
->dbr_scheduled_p
= true;
3875 #endif /* DELAY_SLOTS */
3878 gate_handle_delay_slots (void)
3881 /* At -O0 dataflow info isn't updated after RA. */
3882 return optimize
> 0 && flag_delayed_branch
&& !crtl
->dbr_scheduled_p
;
3888 /* Run delay slot optimization. */
3890 rest_of_handle_delay_slots (void)
3893 dbr_schedule (get_insns ());
3898 struct rtl_opt_pass pass_delay_slots
=
3903 OPTGROUP_NONE
, /* optinfo_flags */
3904 gate_handle_delay_slots
, /* gate */
3905 rest_of_handle_delay_slots
, /* execute */
3908 0, /* static_pass_number */
3909 TV_DBR_SCHED
, /* tv_id */
3910 0, /* properties_required */
3911 0, /* properties_provided */
3912 0, /* properties_destroyed */
3913 0, /* todo_flags_start */
3914 TODO_ggc_collect
/* todo_flags_finish */
3918 /* Machine dependent reorg pass. */
3920 gate_handle_machine_reorg (void)
3922 return targetm
.machine_dependent_reorg
!= 0;
3927 rest_of_handle_machine_reorg (void)
3929 targetm
.machine_dependent_reorg ();
3933 struct rtl_opt_pass pass_machine_reorg
=
3938 OPTGROUP_NONE
, /* optinfo_flags */
3939 gate_handle_machine_reorg
, /* gate */
3940 rest_of_handle_machine_reorg
, /* execute */
3943 0, /* static_pass_number */
3944 TV_MACH_DEP
, /* tv_id */
3945 0, /* properties_required */
3946 0, /* properties_provided */
3947 0, /* properties_destroyed */
3948 0, /* todo_flags_start */
3949 TODO_ggc_collect
/* todo_flags_finish */