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
4 Free Software Foundation, Inc.
5 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
6 Hacked by Michael Tiemann (tiemann@cygnus.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 /* Instruction reorganization pass.
26 This pass runs after register allocation and final jump
27 optimization. It should be the last pass to run before peephole.
28 It serves primarily to fill delay slots of insns, typically branch
29 and call insns. Other insns typically involve more complicated
30 interactions of data dependencies and resource constraints, and
31 are better handled by scheduling before register allocation (by the
32 function `schedule_insns').
34 The Branch Penalty is the number of extra cycles that are needed to
35 execute a branch insn. On an ideal machine, branches take a single
36 cycle, and the Branch Penalty is 0. Several RISC machines approach
37 branch delays differently:
39 The MIPS has a single branch delay slot. Most insns
40 (except other branches) can be used to fill this slot. When the
41 slot is filled, two insns execute in two cycles, reducing the
42 branch penalty to zero.
44 The SPARC always has a branch delay slot, but its effects can be
45 annulled when the branch is not taken. This means that failing to
46 find other sources of insns, we can hoist an insn from the branch
47 target that would only be safe to execute knowing that the branch
50 The HP-PA always has a branch delay slot. For unconditional branches
51 its effects can be annulled when the branch is taken. The effects
52 of the delay slot in a conditional branch can be nullified for forward
53 taken branches, or for untaken backward branches. This means
54 we can hoist insns from the fall-through path for forward branches or
55 steal insns from the target of backward branches.
57 The TMS320C3x and C4x have three branch delay slots. When the three
58 slots are filled, the branch penalty is zero. Most insns can fill the
59 delay slots except jump insns.
61 Three techniques for filling delay slots have been implemented so far:
63 (1) `fill_simple_delay_slots' is the simplest, most efficient way
64 to fill delay slots. This pass first looks for insns which come
65 from before the branch and which are safe to execute after the
66 branch. Then it searches after the insn requiring delay slots or,
67 in the case of a branch, for insns that are after the point at
68 which the branch merges into the fallthrough code, if such a point
69 exists. When such insns are found, the branch penalty decreases
70 and no code expansion takes place.
72 (2) `fill_eager_delay_slots' is more complicated: it is used for
73 scheduling conditional jumps, or for scheduling jumps which cannot
74 be filled using (1). A machine need not have annulled jumps to use
75 this strategy, but it helps (by keeping more options open).
76 `fill_eager_delay_slots' tries to guess the direction the branch
77 will go; if it guesses right 100% of the time, it can reduce the
78 branch penalty as much as `fill_simple_delay_slots' does. If it
79 guesses wrong 100% of the time, it might as well schedule nops. When
80 `fill_eager_delay_slots' takes insns from the fall-through path of
81 the jump, usually there is no code expansion; when it takes insns
82 from the branch target, there is code expansion if it is not the
83 only way to reach that target.
85 (3) `relax_delay_slots' uses a set of rules to simplify code that
86 has been reorganized by (1) and (2). It finds cases where
87 conditional test can be eliminated, jumps can be threaded, extra
88 insns can be eliminated, etc. It is the job of (1) and (2) to do a
89 good job of scheduling locally; `relax_delay_slots' takes care of
90 making the various individual schedules work well together. It is
91 especially tuned to handle the control flow interactions of branch
92 insns. It does nothing for insns with delay slots that do not
95 On machines that use CC0, we are very conservative. We will not make
96 a copy of an insn involving CC0 since we want to maintain a 1-1
97 correspondence between the insn that sets and uses CC0. The insns are
98 allowed to be separated by placing an insn that sets CC0 (but not an insn
99 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
100 delay slot. In that case, we point each insn at the other with REG_CC_USER
101 and REG_CC_SETTER notes. Note that these restrictions affect very few
102 machines because most RISC machines with delay slots will not use CC0
103 (the RT is the only known exception at this point).
107 The Acorn Risc Machine can conditionally execute most insns, so
108 it is profitable to move single insns into a position to execute
109 based on the condition code of the previous insn.
111 The HP-PA can conditionally nullify insns, providing a similar
112 effect to the ARM, differing mostly in which insn is "in charge". */
116 #include "coretypes.h"
118 #include "diagnostic-core.h"
122 #include "function.h"
123 #include "insn-config.h"
124 #include "conditions.h"
125 #include "hard-reg-set.h"
126 #include "basic-block.h"
131 #include "insn-attr.h"
132 #include "resource.h"
136 #include "tree-pass.h"
140 #ifndef ANNUL_IFTRUE_SLOTS
141 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
143 #ifndef ANNUL_IFFALSE_SLOTS
144 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
147 /* Insns which have delay slots that have not yet been filled. */
149 static struct obstack unfilled_slots_obstack
;
150 static rtx
*unfilled_firstobj
;
152 /* Define macros to refer to the first and last slot containing unfilled
153 insns. These are used because the list may move and its address
154 should be recomputed at each use. */
156 #define unfilled_slots_base \
157 ((rtx *) obstack_base (&unfilled_slots_obstack))
159 #define unfilled_slots_next \
160 ((rtx *) obstack_next_free (&unfilled_slots_obstack))
162 /* Points to the label before the end of the function, or before a
164 static rtx function_return_label
;
165 /* Likewise for a simple_return. */
166 static rtx function_simple_return_label
;
168 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
169 not always monotonically increase. */
170 static int *uid_to_ruid
;
172 /* Highest valid index in `uid_to_ruid'. */
175 static int stop_search_p (rtx
, int);
176 static int resource_conflicts_p (struct resources
*, struct resources
*);
177 static int insn_references_resource_p (rtx
, struct resources
*, bool);
178 static int insn_sets_resource_p (rtx
, struct resources
*, bool);
179 static rtx
find_end_label (rtx
);
180 static rtx
emit_delay_sequence (rtx
, rtx
, int);
181 static rtx
add_to_delay_list (rtx
, rtx
);
182 static rtx
delete_from_delay_slot (rtx
);
183 static void delete_scheduled_jump (rtx
);
184 static void note_delay_statistics (int, int);
185 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
186 static rtx
optimize_skip (rtx
);
188 static int get_jump_flags (rtx
, rtx
);
189 static int rare_destination (rtx
);
190 static int mostly_true_jump (rtx
, rtx
);
191 static rtx
get_branch_condition (rtx
, rtx
);
192 static int condition_dominates_p (rtx
, rtx
);
193 static int redirect_with_delay_slots_safe_p (rtx
, rtx
, rtx
);
194 static int redirect_with_delay_list_safe_p (rtx
, rtx
, rtx
);
195 static int check_annul_list_true_false (int, rtx
);
196 static rtx
steal_delay_list_from_target (rtx
, rtx
, rtx
, rtx
,
200 int, int *, int *, rtx
*);
201 static rtx
steal_delay_list_from_fallthrough (rtx
, rtx
, rtx
, rtx
,
206 static void try_merge_delay_insns (rtx
, rtx
);
207 static rtx
redundant_insn (rtx
, rtx
, rtx
);
208 static int own_thread_p (rtx
, rtx
, int);
209 static void update_block (rtx
, rtx
);
210 static int reorg_redirect_jump (rtx
, rtx
);
211 static void update_reg_dead_notes (rtx
, rtx
);
212 static void fix_reg_dead_note (rtx
, rtx
);
213 static void update_reg_unused_notes (rtx
, rtx
);
214 static void fill_simple_delay_slots (int);
215 static rtx
fill_slots_from_thread (rtx
, rtx
, rtx
, rtx
,
218 static void fill_eager_delay_slots (void);
219 static void relax_delay_slots (rtx
);
220 static void make_return_insns (rtx
);
222 /* A wrapper around next_active_insn which takes care to return ret_rtx
226 first_active_target_insn (rtx insn
)
228 if (ANY_RETURN_P (insn
))
230 return next_active_insn (insn
);
233 /* Return true iff INSN is a simplejump, or any kind of return insn. */
236 simplejump_or_return_p (rtx insn
)
238 return (JUMP_P (insn
)
239 && (simplejump_p (insn
) || ANY_RETURN_P (PATTERN (insn
))));
242 /* Return TRUE if this insn should stop the search for insn to fill delay
243 slots. LABELS_P indicates that labels should terminate the search.
244 In all cases, jumps terminate the search. */
247 stop_search_p (rtx insn
, int labels_p
)
252 /* If the insn can throw an exception that is caught within the function,
253 it may effectively perform a jump from the viewpoint of the function.
254 Therefore act like for a jump. */
255 if (can_throw_internal (insn
))
258 switch (GET_CODE (insn
))
272 /* OK unless it contains a delay slot or is an `asm' insn of some type.
273 We don't know anything about these. */
274 return (GET_CODE (PATTERN (insn
)) == SEQUENCE
275 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
276 || asm_noperands (PATTERN (insn
)) >= 0);
283 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
284 resource set contains a volatile memory reference. Otherwise, return FALSE. */
287 resource_conflicts_p (struct resources
*res1
, struct resources
*res2
)
289 if ((res1
->cc
&& res2
->cc
) || (res1
->memory
&& res2
->memory
)
290 || (res1
->unch_memory
&& res2
->unch_memory
)
291 || res1
->volatil
|| res2
->volatil
)
295 return (res1
->regs
& res2
->regs
) != HARD_CONST (0);
300 for (i
= 0; i
< HARD_REG_SET_LONGS
; i
++)
301 if ((res1
->regs
[i
] & res2
->regs
[i
]) != 0)
308 /* Return TRUE if any resource marked in RES, a `struct resources', is
309 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
310 routine is using those resources.
312 We compute this by computing all the resources referenced by INSN and
313 seeing if this conflicts with RES. It might be faster to directly check
314 ourselves, and this is the way it used to work, but it means duplicating
315 a large block of complex code. */
318 insn_references_resource_p (rtx insn
, struct resources
*res
,
319 bool include_delayed_effects
)
321 struct resources insn_res
;
323 CLEAR_RESOURCE (&insn_res
);
324 mark_referenced_resources (insn
, &insn_res
, include_delayed_effects
);
325 return resource_conflicts_p (&insn_res
, res
);
328 /* Return TRUE if INSN modifies resources that are marked in RES.
329 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
330 included. CC0 is only modified if it is explicitly set; see comments
331 in front of mark_set_resources for details. */
334 insn_sets_resource_p (rtx insn
, struct resources
*res
,
335 bool include_delayed_effects
)
337 struct resources insn_sets
;
339 CLEAR_RESOURCE (&insn_sets
);
340 mark_set_resources (insn
, &insn_sets
, 0,
341 (include_delayed_effects
344 return resource_conflicts_p (&insn_sets
, res
);
347 /* Find a label at the end of the function or before a RETURN. If there
348 is none, try to make one. If that fails, returns 0.
350 The property of such a label is that it is placed just before the
351 epilogue or a bare RETURN insn, so that another bare RETURN can be
352 turned into a jump to the label unconditionally. In particular, the
353 label cannot be placed before a RETURN insn with a filled delay slot.
355 ??? There may be a problem with the current implementation. Suppose
356 we start with a bare RETURN insn and call find_end_label. It may set
357 function_return_label just before the RETURN. Suppose the machinery
358 is able to fill the delay slot of the RETURN insn afterwards. Then
359 function_return_label is no longer valid according to the property
360 described above and find_end_label will still return it unmodified.
361 Note that this is probably mitigated by the following observation:
362 once function_return_label is made, it is very likely the target of
363 a jump, so filling the delay slot of the RETURN will be much more
365 KIND is either simple_return_rtx or ret_rtx, indicating which type of
366 return we're looking for. */
369 find_end_label (rtx kind
)
375 plabel
= &function_return_label
;
378 gcc_assert (kind
== simple_return_rtx
);
379 plabel
= &function_simple_return_label
;
382 /* If we found one previously, return it. */
386 /* Otherwise, see if there is a label at the end of the function. If there
387 is, it must be that RETURN insns aren't needed, so that is our return
388 label and we don't have to do anything else. */
390 insn
= get_last_insn ();
392 || (NONJUMP_INSN_P (insn
)
393 && (GET_CODE (PATTERN (insn
)) == USE
394 || GET_CODE (PATTERN (insn
)) == CLOBBER
)))
395 insn
= PREV_INSN (insn
);
397 /* When a target threads its epilogue we might already have a
398 suitable return insn. If so put a label before it for the
399 function_return_label. */
401 && JUMP_P (PREV_INSN (insn
))
402 && PATTERN (PREV_INSN (insn
)) == kind
)
404 rtx temp
= PREV_INSN (PREV_INSN (insn
));
405 rtx label
= gen_label_rtx ();
406 LABEL_NUSES (label
) = 0;
408 /* Put the label before any USE insns that may precede the RETURN
410 while (GET_CODE (temp
) == USE
)
411 temp
= PREV_INSN (temp
);
413 emit_label_after (label
, temp
);
417 else if (LABEL_P (insn
))
421 rtx label
= gen_label_rtx ();
422 LABEL_NUSES (label
) = 0;
423 /* If the basic block reorder pass moves the return insn to
424 some other place try to locate it again and put our
425 function_return_label there. */
426 while (insn
&& ! (JUMP_P (insn
) && (PATTERN (insn
) == kind
)))
427 insn
= PREV_INSN (insn
);
430 insn
= PREV_INSN (insn
);
432 /* Put the label before any USE insns that may precede the
434 while (GET_CODE (insn
) == USE
)
435 insn
= PREV_INSN (insn
);
437 emit_label_after (label
, insn
);
447 /* The RETURN insn has its delay slot filled so we cannot
448 emit the label just before it. Since we already have
449 an epilogue and cannot emit a new RETURN, we cannot
450 emit the label at all. */
452 #endif /* HAVE_epilogue */
454 /* Otherwise, make a new label and emit a RETURN and BARRIER,
458 /* We don't bother trying to create a return insn if the
459 epilogue has filled delay-slots; we would have to try and
460 move the delay-slot fillers to the delay-slots for the new
461 return insn or in front of the new return insn. */
462 if (crtl
->epilogue_delay_list
== NULL
465 /* The return we make may have delay slots too. */
466 rtx insn
= gen_return ();
467 insn
= emit_jump_insn (insn
);
468 set_return_jump_label (insn
);
470 if (num_delay_slots (insn
) > 0)
471 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
478 /* Show one additional use for this label so it won't go away until
480 ++LABEL_NUSES (*plabel
);
485 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
486 the pattern of INSN with the SEQUENCE.
488 Chain the insns so that NEXT_INSN of each insn in the sequence points to
489 the next and NEXT_INSN of the last insn in the sequence points to
490 the first insn after the sequence. Similarly for PREV_INSN. This makes
491 it easier to scan all insns.
493 Returns the SEQUENCE that replaces INSN. */
496 emit_delay_sequence (rtx insn
, rtx list
, int length
)
502 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
503 rtvec seqv
= rtvec_alloc (length
+ 1);
504 rtx seq
= gen_rtx_SEQUENCE (VOIDmode
, seqv
);
505 rtx seq_insn
= make_insn_raw (seq
);
506 rtx first
= get_insns ();
507 rtx last
= get_last_insn ();
509 /* Make a copy of the insn having delay slots. */
510 rtx delay_insn
= copy_rtx (insn
);
512 /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
513 confuse further processing. Update LAST in case it was the last insn.
514 We will put the BARRIER back in later. */
515 if (NEXT_INSN (insn
) && BARRIER_P (NEXT_INSN (insn
)))
517 delete_related_insns (NEXT_INSN (insn
));
518 last
= get_last_insn ();
522 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
523 NEXT_INSN (seq_insn
) = NEXT_INSN (insn
);
524 PREV_INSN (seq_insn
) = PREV_INSN (insn
);
527 PREV_INSN (NEXT_INSN (seq_insn
)) = seq_insn
;
530 NEXT_INSN (PREV_INSN (seq_insn
)) = seq_insn
;
532 /* Note the calls to set_new_first_and_last_insn must occur after
533 SEQ_INSN has been completely spliced into the insn stream.
535 Otherwise CUR_INSN_UID will get set to an incorrect value because
536 set_new_first_and_last_insn will not find SEQ_INSN in the chain. */
538 set_new_first_and_last_insn (first
, seq_insn
);
541 set_new_first_and_last_insn (seq_insn
, last
);
543 /* Build our SEQUENCE and rebuild the insn chain. */
544 XVECEXP (seq
, 0, 0) = delay_insn
;
545 INSN_DELETED_P (delay_insn
) = 0;
546 PREV_INSN (delay_insn
) = PREV_INSN (seq_insn
);
548 INSN_LOCATION (seq_insn
) = INSN_LOCATION (delay_insn
);
550 for (li
= list
; li
; li
= XEXP (li
, 1), i
++)
552 rtx tem
= XEXP (li
, 0);
555 /* Show that this copy of the insn isn't deleted. */
556 INSN_DELETED_P (tem
) = 0;
558 XVECEXP (seq
, 0, i
) = tem
;
559 PREV_INSN (tem
) = XVECEXP (seq
, 0, i
- 1);
560 NEXT_INSN (XVECEXP (seq
, 0, i
- 1)) = tem
;
562 /* SPARC assembler, for instance, emit warning when debug info is output
563 into the delay slot. */
564 if (INSN_LOCATION (tem
) && !INSN_LOCATION (seq_insn
))
565 INSN_LOCATION (seq_insn
) = INSN_LOCATION (tem
);
566 INSN_LOCATION (tem
) = 0;
568 for (note
= REG_NOTES (tem
); note
; note
= next
)
570 next
= XEXP (note
, 1);
571 switch (REG_NOTE_KIND (note
))
574 /* Remove any REG_DEAD notes because we can't rely on them now
575 that the insn has been moved. */
576 remove_note (tem
, note
);
579 case REG_LABEL_OPERAND
:
580 case REG_LABEL_TARGET
:
581 /* Keep the label reference count up to date. */
582 if (LABEL_P (XEXP (note
, 0)))
583 LABEL_NUSES (XEXP (note
, 0)) ++;
592 NEXT_INSN (XVECEXP (seq
, 0, length
)) = NEXT_INSN (seq_insn
);
594 /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
595 last insn in that SEQUENCE to point to us. Similarly for the first
596 insn in the following insn if it is a SEQUENCE. */
598 if (PREV_INSN (seq_insn
) && NONJUMP_INSN_P (PREV_INSN (seq_insn
))
599 && GET_CODE (PATTERN (PREV_INSN (seq_insn
))) == SEQUENCE
)
600 NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn
)), 0,
601 XVECLEN (PATTERN (PREV_INSN (seq_insn
)), 0) - 1))
604 if (NEXT_INSN (seq_insn
) && NONJUMP_INSN_P (NEXT_INSN (seq_insn
))
605 && GET_CODE (PATTERN (NEXT_INSN (seq_insn
))) == SEQUENCE
)
606 PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn
)), 0, 0)) = seq_insn
;
608 /* If there used to be a BARRIER, put it back. */
610 emit_barrier_after (seq_insn
);
612 gcc_assert (i
== length
+ 1);
617 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
618 be in the order in which the insns are to be executed. */
621 add_to_delay_list (rtx insn
, rtx delay_list
)
623 /* If we have an empty list, just make a new list element. If
624 INSN has its block number recorded, clear it since we may
625 be moving the insn to a new block. */
629 clear_hashed_info_for_insn (insn
);
630 return gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
633 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
635 XEXP (delay_list
, 1) = add_to_delay_list (insn
, XEXP (delay_list
, 1));
640 /* Delete INSN from the delay slot of the insn that it is in, which may
641 produce an insn with no delay slots. Return the new insn. */
644 delete_from_delay_slot (rtx insn
)
646 rtx trial
, seq_insn
, seq
, prev
;
651 /* We first must find the insn containing the SEQUENCE with INSN in its
652 delay slot. Do this by finding an insn, TRIAL, where
653 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
656 PREV_INSN (NEXT_INSN (trial
)) == trial
;
657 trial
= NEXT_INSN (trial
))
660 seq_insn
= PREV_INSN (NEXT_INSN (trial
));
661 seq
= PATTERN (seq_insn
);
663 if (NEXT_INSN (seq_insn
) && BARRIER_P (NEXT_INSN (seq_insn
)))
666 /* Create a delay list consisting of all the insns other than the one
667 we are deleting (unless we were the only one). */
668 if (XVECLEN (seq
, 0) > 2)
669 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
670 if (XVECEXP (seq
, 0, i
) != insn
)
671 delay_list
= add_to_delay_list (XVECEXP (seq
, 0, i
), delay_list
);
673 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
674 list, and rebuild the delay list if non-empty. */
675 prev
= PREV_INSN (seq_insn
);
676 trial
= XVECEXP (seq
, 0, 0);
677 delete_related_insns (seq_insn
);
678 add_insn_after (trial
, prev
, NULL
);
680 /* If there was a barrier after the old SEQUENCE, remit it. */
682 emit_barrier_after (trial
);
684 /* If there are any delay insns, remit them. Otherwise clear the
687 trial
= emit_delay_sequence (trial
, delay_list
, XVECLEN (seq
, 0) - 2);
688 else if (JUMP_P (trial
))
689 INSN_ANNULLED_BRANCH_P (trial
) = 0;
691 INSN_FROM_TARGET_P (insn
) = 0;
693 /* Show we need to fill this insn again. */
694 obstack_ptr_grow (&unfilled_slots_obstack
, trial
);
699 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
700 the insn that sets CC0 for it and delete it too. */
703 delete_scheduled_jump (rtx insn
)
705 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
706 delete the insn that sets the condition code, but it is hard to find it.
707 Since this case is rare anyway, don't bother trying; there would likely
708 be other insns that became dead anyway, which we wouldn't know to
712 if (reg_mentioned_p (cc0_rtx
, insn
))
714 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
716 /* If a reg-note was found, it points to an insn to set CC0. This
717 insn is in the delay list of some other insn. So delete it from
718 the delay list it was in. */
721 if (! FIND_REG_INC_NOTE (XEXP (note
, 0), NULL_RTX
)
722 && sets_cc0_p (PATTERN (XEXP (note
, 0))) == 1)
723 delete_from_delay_slot (XEXP (note
, 0));
727 /* The insn setting CC0 is our previous insn, but it may be in
728 a delay slot. It will be the last insn in the delay slot, if
730 rtx trial
= previous_insn (insn
);
732 trial
= prev_nonnote_insn (trial
);
733 if (sets_cc0_p (PATTERN (trial
)) != 1
734 || FIND_REG_INC_NOTE (trial
, NULL_RTX
))
736 if (PREV_INSN (NEXT_INSN (trial
)) == trial
)
737 delete_related_insns (trial
);
739 delete_from_delay_slot (trial
);
744 delete_related_insns (insn
);
747 /* Counters for delay-slot filling. */
749 #define NUM_REORG_FUNCTIONS 2
750 #define MAX_DELAY_HISTOGRAM 3
751 #define MAX_REORG_PASSES 2
753 static int num_insns_needing_delays
[NUM_REORG_FUNCTIONS
][MAX_REORG_PASSES
];
755 static int num_filled_delays
[NUM_REORG_FUNCTIONS
][MAX_DELAY_HISTOGRAM
+1][MAX_REORG_PASSES
];
757 static int reorg_pass_number
;
760 note_delay_statistics (int slots_filled
, int index
)
762 num_insns_needing_delays
[index
][reorg_pass_number
]++;
763 if (slots_filled
> MAX_DELAY_HISTOGRAM
)
764 slots_filled
= MAX_DELAY_HISTOGRAM
;
765 num_filled_delays
[index
][slots_filled
][reorg_pass_number
]++;
768 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
770 /* Optimize the following cases:
772 1. When a conditional branch skips over only one instruction,
773 use an annulling branch and put that insn in the delay slot.
774 Use either a branch that annuls when the condition if true or
775 invert the test with a branch that annuls when the condition is
776 false. This saves insns, since otherwise we must copy an insn
779 (orig) (skip) (otherwise)
780 Bcc.n L1 Bcc',a L1 Bcc,a L1'
787 2. When a conditional branch skips over only one instruction,
788 and after that, it unconditionally branches somewhere else,
789 perform the similar optimization. This saves executing the
790 second branch in the case where the inverted condition is true.
799 This should be expanded to skip over N insns, where N is the number
800 of delay slots required. */
803 optimize_skip (rtx insn
)
805 rtx trial
= next_nonnote_insn (insn
);
806 rtx next_trial
= next_active_insn (trial
);
810 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
813 || !NONJUMP_INSN_P (trial
)
814 || GET_CODE (PATTERN (trial
)) == SEQUENCE
815 || recog_memoized (trial
) < 0
816 || (! eligible_for_annul_false (insn
, 0, trial
, flags
)
817 && ! eligible_for_annul_true (insn
, 0, trial
, flags
))
818 || can_throw_internal (trial
))
821 /* There are two cases where we are just executing one insn (we assume
822 here that a branch requires only one insn; this should be generalized
823 at some point): Where the branch goes around a single insn or where
824 we have one insn followed by a branch to the same label we branch to.
825 In both of these cases, inverting the jump and annulling the delay
826 slot give the same effect in fewer insns. */
827 if ((next_trial
== next_active_insn (JUMP_LABEL (insn
))
828 && ! (next_trial
== 0 && crtl
->epilogue_delay_list
!= 0))
830 && simplejump_or_return_p (next_trial
)
831 && JUMP_LABEL (insn
) == JUMP_LABEL (next_trial
)))
833 if (eligible_for_annul_false (insn
, 0, trial
, flags
))
835 if (invert_jump (insn
, JUMP_LABEL (insn
), 1))
836 INSN_FROM_TARGET_P (trial
) = 1;
837 else if (! eligible_for_annul_true (insn
, 0, trial
, flags
))
841 delay_list
= add_to_delay_list (trial
, NULL_RTX
);
842 next_trial
= next_active_insn (trial
);
843 update_block (trial
, trial
);
844 delete_related_insns (trial
);
846 /* Also, if we are targeting an unconditional
847 branch, thread our jump to the target of that branch. Don't
848 change this into a RETURN here, because it may not accept what
849 we have in the delay slot. We'll fix this up later. */
850 if (next_trial
&& simplejump_or_return_p (next_trial
))
852 rtx target_label
= JUMP_LABEL (next_trial
);
853 if (ANY_RETURN_P (target_label
))
854 target_label
= find_end_label (target_label
);
858 /* Recompute the flags based on TARGET_LABEL since threading
859 the jump to TARGET_LABEL may change the direction of the
860 jump (which may change the circumstances in which the
861 delay slot is nullified). */
862 flags
= get_jump_flags (insn
, target_label
);
863 if (eligible_for_annul_true (insn
, 0, trial
, flags
))
864 reorg_redirect_jump (insn
, target_label
);
868 INSN_ANNULLED_BRANCH_P (insn
) = 1;
875 /* Encode and return branch direction and prediction information for
876 INSN assuming it will jump to LABEL.
878 Non conditional branches return no direction information and
879 are predicted as very likely taken. */
882 get_jump_flags (rtx insn
, rtx label
)
886 /* get_jump_flags can be passed any insn with delay slots, these may
887 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
888 direction information, and only if they are conditional jumps.
890 If LABEL is a return, then there is no way to determine the branch
893 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
894 && !ANY_RETURN_P (label
)
895 && INSN_UID (insn
) <= max_uid
896 && INSN_UID (label
) <= max_uid
)
898 = (uid_to_ruid
[INSN_UID (label
)] > uid_to_ruid
[INSN_UID (insn
)])
899 ? ATTR_FLAG_forward
: ATTR_FLAG_backward
;
900 /* No valid direction information. */
907 /* Return 1 if INSN is a destination that will be branched to rarely (the
908 return point of a function); return 2 if DEST will be branched to very
909 rarely (a call to a function that doesn't return). Otherwise,
913 rare_destination (rtx insn
)
918 for (; insn
&& !ANY_RETURN_P (insn
); insn
= next
)
920 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
921 insn
= XVECEXP (PATTERN (insn
), 0, 0);
923 next
= NEXT_INSN (insn
);
925 switch (GET_CODE (insn
))
930 /* A BARRIER can either be after a JUMP_INSN or a CALL_INSN. We
931 don't scan past JUMP_INSNs, so any barrier we find here must
932 have been after a CALL_INSN and hence mean the call doesn't
936 if (ANY_RETURN_P (PATTERN (insn
)))
938 else if (simplejump_p (insn
)
939 && jump_count
++ < 10)
940 next
= JUMP_LABEL (insn
);
949 /* If we got here it means we hit the end of the function. So this
950 is an unlikely destination. */
955 /* Return truth value of the statement that this branch
956 is mostly taken. If we think that the branch is extremely likely
957 to be taken, we return 2. If the branch is slightly more likely to be
958 taken, return 1. If the branch is slightly less likely to be taken,
959 return 0 and if the branch is highly unlikely to be taken, return -1.
961 CONDITION, if nonzero, is the condition that JUMP_INSN is testing. */
964 mostly_true_jump (rtx jump_insn
, rtx condition
)
966 rtx target_label
= JUMP_LABEL (jump_insn
);
968 int rare_dest
, rare_fallthrough
;
970 /* If branch probabilities are available, then use that number since it
971 always gives a correct answer. */
972 note
= find_reg_note (jump_insn
, REG_BR_PROB
, 0);
975 int prob
= INTVAL (XEXP (note
, 0));
977 if (prob
>= REG_BR_PROB_BASE
* 9 / 10)
979 else if (prob
>= REG_BR_PROB_BASE
/ 2)
981 else if (prob
>= REG_BR_PROB_BASE
/ 10)
987 /* Look at the relative rarities of the fallthrough and destination. If
988 they differ, we can predict the branch that way. */
989 rare_dest
= rare_destination (target_label
);
990 rare_fallthrough
= rare_destination (NEXT_INSN (jump_insn
));
992 switch (rare_fallthrough
- rare_dest
)
1006 /* If we couldn't figure out what this jump was, assume it won't be
1007 taken. This should be rare. */
1011 /* Predict backward branches usually take, forward branches usually not. If
1012 we don't know whether this is forward or backward, assume the branch
1013 will be taken, since most are. */
1014 return (ANY_RETURN_P (target_label
) || INSN_UID (jump_insn
) > max_uid
1015 || INSN_UID (target_label
) > max_uid
1016 || (uid_to_ruid
[INSN_UID (jump_insn
)]
1017 > uid_to_ruid
[INSN_UID (target_label
)]));
1020 /* Return the condition under which INSN will branch to TARGET. If TARGET
1021 is zero, return the condition under which INSN will return. If INSN is
1022 an unconditional branch, return const_true_rtx. If INSN isn't a simple
1023 type of jump, or it doesn't go to TARGET, return 0. */
1026 get_branch_condition (rtx insn
, rtx target
)
1028 rtx pat
= PATTERN (insn
);
1031 if (condjump_in_parallel_p (insn
))
1032 pat
= XVECEXP (pat
, 0, 0);
1034 if (ANY_RETURN_P (pat
))
1035 return pat
== target
? const_true_rtx
: 0;
1037 if (GET_CODE (pat
) != SET
|| SET_DEST (pat
) != pc_rtx
)
1040 src
= SET_SRC (pat
);
1041 if (GET_CODE (src
) == LABEL_REF
&& XEXP (src
, 0) == target
)
1042 return const_true_rtx
;
1044 else if (GET_CODE (src
) == IF_THEN_ELSE
1045 && XEXP (src
, 2) == pc_rtx
1046 && GET_CODE (XEXP (src
, 1)) == LABEL_REF
1047 && XEXP (XEXP (src
, 1), 0) == target
)
1048 return XEXP (src
, 0);
1050 else if (GET_CODE (src
) == IF_THEN_ELSE
1051 && XEXP (src
, 1) == pc_rtx
1052 && GET_CODE (XEXP (src
, 2)) == LABEL_REF
1053 && XEXP (XEXP (src
, 2), 0) == target
)
1056 rev
= reversed_comparison_code (XEXP (src
, 0), insn
);
1058 return gen_rtx_fmt_ee (rev
, GET_MODE (XEXP (src
, 0)),
1059 XEXP (XEXP (src
, 0), 0),
1060 XEXP (XEXP (src
, 0), 1));
1066 /* Return nonzero if CONDITION is more strict than the condition of
1067 INSN, i.e., if INSN will always branch if CONDITION is true. */
1070 condition_dominates_p (rtx condition
, rtx insn
)
1072 rtx other_condition
= get_branch_condition (insn
, JUMP_LABEL (insn
));
1073 enum rtx_code code
= GET_CODE (condition
);
1074 enum rtx_code other_code
;
1076 if (rtx_equal_p (condition
, other_condition
)
1077 || other_condition
== const_true_rtx
)
1080 else if (condition
== const_true_rtx
|| other_condition
== 0)
1083 other_code
= GET_CODE (other_condition
);
1084 if (GET_RTX_LENGTH (code
) != 2 || GET_RTX_LENGTH (other_code
) != 2
1085 || ! rtx_equal_p (XEXP (condition
, 0), XEXP (other_condition
, 0))
1086 || ! rtx_equal_p (XEXP (condition
, 1), XEXP (other_condition
, 1)))
1089 return comparison_dominates_p (code
, other_code
);
1092 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1093 any insns already in the delay slot of JUMP. */
1096 redirect_with_delay_slots_safe_p (rtx jump
, rtx newlabel
, rtx seq
)
1099 rtx pat
= PATTERN (seq
);
1101 /* Make sure all the delay slots of this jump would still
1102 be valid after threading the jump. If they are still
1103 valid, then return nonzero. */
1105 flags
= get_jump_flags (jump
, newlabel
);
1106 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1108 #ifdef ANNUL_IFFALSE_SLOTS
1109 (INSN_ANNULLED_BRANCH_P (jump
)
1110 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1111 ? eligible_for_annul_false (jump
, i
- 1,
1112 XVECEXP (pat
, 0, i
), flags
) :
1114 #ifdef ANNUL_IFTRUE_SLOTS
1115 (INSN_ANNULLED_BRANCH_P (jump
)
1116 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1117 ? eligible_for_annul_true (jump
, i
- 1,
1118 XVECEXP (pat
, 0, i
), flags
) :
1120 eligible_for_delay (jump
, i
- 1, XVECEXP (pat
, 0, i
), flags
)))
1123 return (i
== XVECLEN (pat
, 0));
1126 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1127 any insns we wish to place in the delay slot of JUMP. */
1130 redirect_with_delay_list_safe_p (rtx jump
, rtx newlabel
, rtx delay_list
)
1135 /* Make sure all the insns in DELAY_LIST would still be
1136 valid after threading the jump. If they are still
1137 valid, then return nonzero. */
1139 flags
= get_jump_flags (jump
, newlabel
);
1140 for (li
= delay_list
, i
= 0; li
; li
= XEXP (li
, 1), i
++)
1142 #ifdef ANNUL_IFFALSE_SLOTS
1143 (INSN_ANNULLED_BRANCH_P (jump
)
1144 && INSN_FROM_TARGET_P (XEXP (li
, 0)))
1145 ? eligible_for_annul_false (jump
, i
, XEXP (li
, 0), flags
) :
1147 #ifdef ANNUL_IFTRUE_SLOTS
1148 (INSN_ANNULLED_BRANCH_P (jump
)
1149 && ! INSN_FROM_TARGET_P (XEXP (li
, 0)))
1150 ? eligible_for_annul_true (jump
, i
, XEXP (li
, 0), flags
) :
1152 eligible_for_delay (jump
, i
, XEXP (li
, 0), flags
)))
1155 return (li
== NULL
);
1158 /* DELAY_LIST is a list of insns that have already been placed into delay
1159 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1160 If not, return 0; otherwise return 1. */
1163 check_annul_list_true_false (int annul_true_p
, rtx delay_list
)
1169 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1171 rtx trial
= XEXP (temp
, 0);
1173 if ((annul_true_p
&& INSN_FROM_TARGET_P (trial
))
1174 || (!annul_true_p
&& !INSN_FROM_TARGET_P (trial
)))
1182 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1183 the condition tested by INSN is CONDITION and the resources shown in
1184 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1185 from SEQ's delay list, in addition to whatever insns it may execute
1186 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1187 needed while searching for delay slot insns. Return the concatenated
1188 delay list if possible, otherwise, return 0.
1190 SLOTS_TO_FILL is the total number of slots required by INSN, and
1191 PSLOTS_FILLED points to the number filled so far (also the number of
1192 insns in DELAY_LIST). It is updated with the number that have been
1193 filled from the SEQUENCE, if any.
1195 PANNUL_P points to a nonzero value if we already know that we need
1196 to annul INSN. If this routine determines that annulling is needed,
1197 it may set that value nonzero.
1199 PNEW_THREAD points to a location that is to receive the place at which
1200 execution should continue. */
1203 steal_delay_list_from_target (rtx insn
, rtx condition
, rtx seq
,
1204 rtx delay_list
, struct resources
*sets
,
1205 struct resources
*needed
,
1206 struct resources
*other_needed
,
1207 int slots_to_fill
, int *pslots_filled
,
1208 int *pannul_p
, rtx
*pnew_thread
)
1211 int slots_remaining
= slots_to_fill
- *pslots_filled
;
1212 int total_slots_filled
= *pslots_filled
;
1213 rtx new_delay_list
= 0;
1214 int must_annul
= *pannul_p
;
1217 struct resources cc_set
;
1219 /* We can't do anything if there are more delay slots in SEQ than we
1220 can handle, or if we don't know that it will be a taken branch.
1221 We know that it will be a taken branch if it is either an unconditional
1222 branch or a conditional branch with a stricter branch condition.
1224 Also, exit if the branch has more than one set, since then it is computing
1225 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1226 ??? It may be possible to move other sets into INSN in addition to
1227 moving the instructions in the delay slots.
1229 We can not steal the delay list if one of the instructions in the
1230 current delay_list modifies the condition codes and the jump in the
1231 sequence is a conditional jump. We can not do this because we can
1232 not change the direction of the jump because the condition codes
1233 will effect the direction of the jump in the sequence. */
1235 CLEAR_RESOURCE (&cc_set
);
1236 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1238 rtx trial
= XEXP (temp
, 0);
1240 mark_set_resources (trial
, &cc_set
, 0, MARK_SRC_DEST_CALL
);
1241 if (insn_references_resource_p (XVECEXP (seq
, 0, 0), &cc_set
, false))
1245 if (XVECLEN (seq
, 0) - 1 > slots_remaining
1246 || ! condition_dominates_p (condition
, XVECEXP (seq
, 0, 0))
1247 || ! single_set (XVECEXP (seq
, 0, 0)))
1250 #ifdef MD_CAN_REDIRECT_BRANCH
1251 /* On some targets, branches with delay slots can have a limited
1252 displacement. Give the back end a chance to tell us we can't do
1254 if (! MD_CAN_REDIRECT_BRANCH (insn
, XVECEXP (seq
, 0, 0)))
1258 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1260 rtx trial
= XVECEXP (seq
, 0, i
);
1263 if (insn_references_resource_p (trial
, sets
, false)
1264 || insn_sets_resource_p (trial
, needed
, false)
1265 || insn_sets_resource_p (trial
, sets
, false)
1267 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1269 || find_reg_note (trial
, REG_CC_USER
, NULL_RTX
)
1271 /* If TRIAL is from the fallthrough code of an annulled branch insn
1272 in SEQ, we cannot use it. */
1273 || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq
, 0, 0))
1274 && ! INSN_FROM_TARGET_P (trial
)))
1277 /* If this insn was already done (usually in a previous delay slot),
1278 pretend we put it in our delay slot. */
1279 if (redundant_insn (trial
, insn
, new_delay_list
))
1282 /* We will end up re-vectoring this branch, so compute flags
1283 based on jumping to the new label. */
1284 flags
= get_jump_flags (insn
, JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1287 && ((condition
== const_true_rtx
1288 || (! insn_sets_resource_p (trial
, other_needed
, false)
1289 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1290 ? eligible_for_delay (insn
, total_slots_filled
, trial
, flags
)
1291 : (must_annul
|| (delay_list
== NULL
&& new_delay_list
== NULL
))
1293 check_annul_list_true_false (0, delay_list
)
1294 && check_annul_list_true_false (0, new_delay_list
)
1295 && eligible_for_annul_false (insn
, total_slots_filled
,
1300 temp
= copy_rtx (trial
);
1301 INSN_FROM_TARGET_P (temp
) = 1;
1302 new_delay_list
= add_to_delay_list (temp
, new_delay_list
);
1303 total_slots_filled
++;
1305 if (--slots_remaining
== 0)
1312 /* Show the place to which we will be branching. */
1313 *pnew_thread
= first_active_target_insn (JUMP_LABEL (XVECEXP (seq
, 0, 0)));
1315 /* Add any new insns to the delay list and update the count of the
1316 number of slots filled. */
1317 *pslots_filled
= total_slots_filled
;
1321 if (delay_list
== 0)
1322 return new_delay_list
;
1324 for (temp
= new_delay_list
; temp
; temp
= XEXP (temp
, 1))
1325 delay_list
= add_to_delay_list (XEXP (temp
, 0), delay_list
);
1330 /* Similar to steal_delay_list_from_target except that SEQ is on the
1331 fallthrough path of INSN. Here we only do something if the delay insn
1332 of SEQ is an unconditional branch. In that case we steal its delay slot
1333 for INSN since unconditional branches are much easier to fill. */
1336 steal_delay_list_from_fallthrough (rtx insn
, rtx condition
, rtx seq
,
1337 rtx delay_list
, struct resources
*sets
,
1338 struct resources
*needed
,
1339 struct resources
*other_needed
,
1340 int slots_to_fill
, int *pslots_filled
,
1345 int must_annul
= *pannul_p
;
1348 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
1350 /* We can't do anything if SEQ's delay insn isn't an
1351 unconditional branch. */
1353 if (! simplejump_or_return_p (XVECEXP (seq
, 0, 0)))
1356 for (i
= 1; i
< XVECLEN (seq
, 0); i
++)
1358 rtx trial
= XVECEXP (seq
, 0, i
);
1360 /* If TRIAL sets CC0, stealing it will move it too far from the use
1362 if (insn_references_resource_p (trial
, sets
, false)
1363 || insn_sets_resource_p (trial
, needed
, false)
1364 || insn_sets_resource_p (trial
, sets
, false)
1366 || sets_cc0_p (PATTERN (trial
))
1372 /* If this insn was already done, we don't need it. */
1373 if (redundant_insn (trial
, insn
, delay_list
))
1375 delete_from_delay_slot (trial
);
1380 && ((condition
== const_true_rtx
1381 || (! insn_sets_resource_p (trial
, other_needed
, false)
1382 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1383 ? eligible_for_delay (insn
, *pslots_filled
, trial
, flags
)
1384 : (must_annul
|| delay_list
== NULL
) && (must_annul
= 1,
1385 check_annul_list_true_false (1, delay_list
)
1386 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
1390 delete_from_delay_slot (trial
);
1391 delay_list
= add_to_delay_list (trial
, delay_list
);
1393 if (++(*pslots_filled
) == slots_to_fill
)
1405 /* Try merging insns starting at THREAD which match exactly the insns in
1408 If all insns were matched and the insn was previously annulling, the
1409 annul bit will be cleared.
1411 For each insn that is merged, if the branch is or will be non-annulling,
1412 we delete the merged insn. */
1415 try_merge_delay_insns (rtx insn
, rtx thread
)
1417 rtx trial
, next_trial
;
1418 rtx delay_insn
= XVECEXP (PATTERN (insn
), 0, 0);
1419 int annul_p
= JUMP_P (delay_insn
) && INSN_ANNULLED_BRANCH_P (delay_insn
);
1420 int slot_number
= 1;
1421 int num_slots
= XVECLEN (PATTERN (insn
), 0);
1422 rtx next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1423 struct resources set
, needed
;
1424 rtx merged_insns
= 0;
1428 flags
= get_jump_flags (delay_insn
, JUMP_LABEL (delay_insn
));
1430 CLEAR_RESOURCE (&needed
);
1431 CLEAR_RESOURCE (&set
);
1433 /* If this is not an annulling branch, take into account anything needed in
1434 INSN's delay slot. This prevents two increments from being incorrectly
1435 folded into one. If we are annulling, this would be the correct
1436 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1437 will essentially disable this optimization. This method is somewhat of
1438 a kludge, but I don't see a better way.) */
1440 for (i
= 1 ; i
< num_slots
; i
++)
1441 if (XVECEXP (PATTERN (insn
), 0, i
))
1442 mark_referenced_resources (XVECEXP (PATTERN (insn
), 0, i
), &needed
,
1445 for (trial
= thread
; !stop_search_p (trial
, 1); trial
= next_trial
)
1447 rtx pat
= PATTERN (trial
);
1448 rtx oldtrial
= trial
;
1450 next_trial
= next_nonnote_insn (trial
);
1452 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1453 if (NONJUMP_INSN_P (trial
)
1454 && (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
))
1457 if (GET_CODE (next_to_match
) == GET_CODE (trial
)
1459 /* We can't share an insn that sets cc0. */
1460 && ! sets_cc0_p (pat
)
1462 && ! insn_references_resource_p (trial
, &set
, true)
1463 && ! insn_sets_resource_p (trial
, &set
, true)
1464 && ! insn_sets_resource_p (trial
, &needed
, true)
1465 && (trial
= try_split (pat
, trial
, 0)) != 0
1466 /* Update next_trial, in case try_split succeeded. */
1467 && (next_trial
= next_nonnote_insn (trial
))
1468 /* Likewise THREAD. */
1469 && (thread
= oldtrial
== thread
? trial
: thread
)
1470 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (trial
))
1471 /* Have to test this condition if annul condition is different
1472 from (and less restrictive than) non-annulling one. */
1473 && eligible_for_delay (delay_insn
, slot_number
- 1, trial
, flags
))
1478 update_block (trial
, thread
);
1479 if (trial
== thread
)
1480 thread
= next_active_insn (thread
);
1482 delete_related_insns (trial
);
1483 INSN_FROM_TARGET_P (next_to_match
) = 0;
1486 merged_insns
= gen_rtx_INSN_LIST (VOIDmode
, trial
, merged_insns
);
1488 if (++slot_number
== num_slots
)
1491 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1494 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
1495 mark_referenced_resources (trial
, &needed
, true);
1498 /* See if we stopped on a filled insn. If we did, try to see if its
1499 delay slots match. */
1500 if (slot_number
!= num_slots
1501 && trial
&& NONJUMP_INSN_P (trial
)
1502 && GET_CODE (PATTERN (trial
)) == SEQUENCE
1503 && !(JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
1504 && INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial
), 0, 0))))
1506 rtx pat
= PATTERN (trial
);
1507 rtx filled_insn
= XVECEXP (pat
, 0, 0);
1509 /* Account for resources set/needed by the filled insn. */
1510 mark_set_resources (filled_insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1511 mark_referenced_resources (filled_insn
, &needed
, true);
1513 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
1515 rtx dtrial
= XVECEXP (pat
, 0, i
);
1517 if (! insn_references_resource_p (dtrial
, &set
, true)
1518 && ! insn_sets_resource_p (dtrial
, &set
, true)
1519 && ! insn_sets_resource_p (dtrial
, &needed
, true)
1521 && ! sets_cc0_p (PATTERN (dtrial
))
1523 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (dtrial
))
1524 && eligible_for_delay (delay_insn
, slot_number
- 1, dtrial
, flags
))
1530 update_block (dtrial
, thread
);
1531 new_rtx
= delete_from_delay_slot (dtrial
);
1532 if (INSN_DELETED_P (thread
))
1534 INSN_FROM_TARGET_P (next_to_match
) = 0;
1537 merged_insns
= gen_rtx_INSN_LIST (SImode
, dtrial
,
1540 if (++slot_number
== num_slots
)
1543 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1547 /* Keep track of the set/referenced resources for the delay
1548 slots of any trial insns we encounter. */
1549 mark_set_resources (dtrial
, &set
, 0, MARK_SRC_DEST_CALL
);
1550 mark_referenced_resources (dtrial
, &needed
, true);
1555 /* If all insns in the delay slot have been matched and we were previously
1556 annulling the branch, we need not any more. In that case delete all the
1557 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1558 the delay list so that we know that it isn't only being used at the
1560 if (slot_number
== num_slots
&& annul_p
)
1562 for (; merged_insns
; merged_insns
= XEXP (merged_insns
, 1))
1564 if (GET_MODE (merged_insns
) == SImode
)
1568 update_block (XEXP (merged_insns
, 0), thread
);
1569 new_rtx
= delete_from_delay_slot (XEXP (merged_insns
, 0));
1570 if (INSN_DELETED_P (thread
))
1575 update_block (XEXP (merged_insns
, 0), thread
);
1576 delete_related_insns (XEXP (merged_insns
, 0));
1580 INSN_ANNULLED_BRANCH_P (delay_insn
) = 0;
1582 for (i
= 0; i
< XVECLEN (PATTERN (insn
), 0); i
++)
1583 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn
), 0, i
)) = 0;
1587 /* See if INSN is redundant with an insn in front of TARGET. Often this
1588 is called when INSN is a candidate for a delay slot of TARGET.
1589 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1590 of INSN. Often INSN will be redundant with an insn in a delay slot of
1591 some previous insn. This happens when we have a series of branches to the
1592 same label; in that case the first insn at the target might want to go
1593 into each of the delay slots.
1595 If we are not careful, this routine can take up a significant fraction
1596 of the total compilation time (4%), but only wins rarely. Hence we
1597 speed this routine up by making two passes. The first pass goes back
1598 until it hits a label and sees if it finds an insn with an identical
1599 pattern. Only in this (relatively rare) event does it check for
1602 We do not split insns we encounter. This could cause us not to find a
1603 redundant insn, but the cost of splitting seems greater than the possible
1604 gain in rare cases. */
1607 redundant_insn (rtx insn
, rtx target
, rtx delay_list
)
1609 rtx target_main
= target
;
1610 rtx ipat
= PATTERN (insn
);
1612 struct resources needed
, set
;
1614 unsigned insns_to_search
;
1616 /* If INSN has any REG_UNUSED notes, it can't match anything since we
1617 are allowed to not actually assign to such a register. */
1618 if (find_reg_note (insn
, REG_UNUSED
, NULL_RTX
) != 0)
1621 /* Scan backwards looking for a match. */
1622 for (trial
= PREV_INSN (target
),
1623 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1624 trial
&& insns_to_search
> 0;
1625 trial
= PREV_INSN (trial
))
1627 if (LABEL_P (trial
))
1630 if (!NONDEBUG_INSN_P (trial
))
1634 pat
= PATTERN (trial
);
1635 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1638 if (GET_CODE (pat
) == SEQUENCE
)
1640 /* Stop for a CALL and its delay slots because it is difficult to
1641 track its resource needs correctly. */
1642 if (CALL_P (XVECEXP (pat
, 0, 0)))
1645 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1646 slots because it is difficult to track its resource needs
1649 #ifdef INSN_SETS_ARE_DELAYED
1650 if (INSN_SETS_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
1654 #ifdef INSN_REFERENCES_ARE_DELAYED
1655 if (INSN_REFERENCES_ARE_DELAYED (XVECEXP (pat
, 0, 0)))
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
--)
1662 if (GET_CODE (XVECEXP (pat
, 0, i
)) == GET_CODE (insn
)
1663 && rtx_equal_p (PATTERN (XVECEXP (pat
, 0, i
)), ipat
)
1664 && ! find_reg_note (XVECEXP (pat
, 0, i
), REG_UNUSED
, NULL_RTX
))
1667 /* If found a match, exit this loop early. */
1672 else if (GET_CODE (trial
) == GET_CODE (insn
) && rtx_equal_p (pat
, ipat
)
1673 && ! find_reg_note (trial
, REG_UNUSED
, NULL_RTX
))
1677 /* If we didn't find an insn that matches, return 0. */
1681 /* See what resources this insn sets and needs. If they overlap, or
1682 if this insn references CC0, it can't be redundant. */
1684 CLEAR_RESOURCE (&needed
);
1685 CLEAR_RESOURCE (&set
);
1686 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1687 mark_referenced_resources (insn
, &needed
, true);
1689 /* If TARGET is a SEQUENCE, get the main insn. */
1690 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1691 target_main
= XVECEXP (PATTERN (target
), 0, 0);
1693 if (resource_conflicts_p (&needed
, &set
)
1695 || reg_mentioned_p (cc0_rtx
, ipat
)
1697 /* The insn requiring the delay may not set anything needed or set by
1699 || insn_sets_resource_p (target_main
, &needed
, true)
1700 || insn_sets_resource_p (target_main
, &set
, true))
1703 /* Insns we pass may not set either NEEDED or SET, so merge them for
1705 needed
.memory
|= set
.memory
;
1706 needed
.unch_memory
|= set
.unch_memory
;
1707 IOR_HARD_REG_SET (needed
.regs
, set
.regs
);
1709 /* This insn isn't redundant if it conflicts with an insn that either is
1710 or will be in a delay slot of TARGET. */
1714 if (insn_sets_resource_p (XEXP (delay_list
, 0), &needed
, true))
1716 delay_list
= XEXP (delay_list
, 1);
1719 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1720 for (i
= 1; i
< XVECLEN (PATTERN (target
), 0); i
++)
1721 if (insn_sets_resource_p (XVECEXP (PATTERN (target
), 0, i
), &needed
,
1725 /* Scan backwards until we reach a label or an insn that uses something
1726 INSN sets or sets something insn uses or sets. */
1728 for (trial
= PREV_INSN (target
),
1729 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1730 trial
&& !LABEL_P (trial
) && insns_to_search
> 0;
1731 trial
= PREV_INSN (trial
))
1733 if (!NONDEBUG_INSN_P (trial
))
1737 pat
= PATTERN (trial
);
1738 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1741 if (GET_CODE (pat
) == SEQUENCE
)
1743 bool annul_p
= false;
1744 rtx control
= XVECEXP (pat
, 0, 0);
1746 /* If this is a CALL_INSN and its delay slots, it is hard to track
1747 the resource needs properly, so give up. */
1748 if (CALL_P (control
))
1751 /* If this is an INSN or JUMP_INSN with delayed effects, it
1752 is hard to track the resource needs properly, so give up. */
1754 #ifdef INSN_SETS_ARE_DELAYED
1755 if (INSN_SETS_ARE_DELAYED (control
))
1759 #ifdef INSN_REFERENCES_ARE_DELAYED
1760 if (INSN_REFERENCES_ARE_DELAYED (control
))
1764 if (JUMP_P (control
))
1765 annul_p
= INSN_ANNULLED_BRANCH_P (control
);
1767 /* See if any of the insns in the delay slot match, updating
1768 resource requirements as we go. */
1769 for (i
= XVECLEN (pat
, 0) - 1; i
> 0; i
--)
1771 rtx candidate
= XVECEXP (pat
, 0, i
);
1773 /* If an insn will be annulled if the branch is false, it isn't
1774 considered as a possible duplicate insn. */
1775 if (rtx_equal_p (PATTERN (candidate
), ipat
)
1776 && ! (annul_p
&& INSN_FROM_TARGET_P (candidate
)))
1778 /* Show that this insn will be used in the sequel. */
1779 INSN_FROM_TARGET_P (candidate
) = 0;
1783 /* Unless this is an annulled insn from the target of a branch,
1784 we must stop if it sets anything needed or set by INSN. */
1785 if ((!annul_p
|| !INSN_FROM_TARGET_P (candidate
))
1786 && insn_sets_resource_p (candidate
, &needed
, true))
1790 /* If the insn requiring the delay slot conflicts with INSN, we
1792 if (insn_sets_resource_p (control
, &needed
, true))
1797 /* See if TRIAL is the same as INSN. */
1798 pat
= PATTERN (trial
);
1799 if (rtx_equal_p (pat
, ipat
))
1802 /* Can't go any further if TRIAL conflicts with INSN. */
1803 if (insn_sets_resource_p (trial
, &needed
, true))
1811 /* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero,
1812 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1813 is nonzero, we are allowed to fall into this thread; otherwise, we are
1816 If LABEL is used more than one or we pass a label other than LABEL before
1817 finding an active insn, we do not own this thread. */
1820 own_thread_p (rtx thread
, rtx label
, int allow_fallthrough
)
1825 /* We don't own the function end. */
1826 if (thread
== 0 || ANY_RETURN_P (thread
))
1829 /* Get the first active insn, or THREAD, if it is an active insn. */
1830 active_insn
= next_active_insn (PREV_INSN (thread
));
1832 for (insn
= thread
; insn
!= active_insn
; insn
= NEXT_INSN (insn
))
1834 && (insn
!= label
|| LABEL_NUSES (insn
) != 1))
1837 if (allow_fallthrough
)
1840 /* Ensure that we reach a BARRIER before any insn or label. */
1841 for (insn
= prev_nonnote_insn (thread
);
1842 insn
== 0 || !BARRIER_P (insn
);
1843 insn
= prev_nonnote_insn (insn
))
1846 || (NONJUMP_INSN_P (insn
)
1847 && GET_CODE (PATTERN (insn
)) != USE
1848 && GET_CODE (PATTERN (insn
)) != CLOBBER
))
1854 /* Called when INSN is being moved from a location near the target of a jump.
1855 We leave a marker of the form (use (INSN)) immediately in front
1856 of WHERE for mark_target_live_regs. These markers will be deleted when
1859 We used to try to update the live status of registers if WHERE is at
1860 the start of a basic block, but that can't work since we may remove a
1861 BARRIER in relax_delay_slots. */
1864 update_block (rtx insn
, rtx where
)
1866 /* Ignore if this was in a delay slot and it came from the target of
1868 if (INSN_FROM_TARGET_P (insn
))
1871 emit_insn_before (gen_rtx_USE (VOIDmode
, insn
), where
);
1873 /* INSN might be making a value live in a block where it didn't use to
1874 be. So recompute liveness information for this block. */
1876 incr_ticks_for_insn (insn
);
1879 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1880 the basic block containing the jump. */
1883 reorg_redirect_jump (rtx jump
, rtx nlabel
)
1885 incr_ticks_for_insn (jump
);
1886 return redirect_jump (jump
, nlabel
, 1);
1889 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1890 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1891 that reference values used in INSN. If we find one, then we move the
1892 REG_DEAD note to INSN.
1894 This is needed to handle the case where a later insn (after INSN) has a
1895 REG_DEAD note for a register used by INSN, and this later insn subsequently
1896 gets moved before a CODE_LABEL because it is a redundant insn. In this
1897 case, mark_target_live_regs may be confused into thinking the register
1898 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1901 update_reg_dead_notes (rtx insn
, rtx delayed_insn
)
1905 for (p
= next_nonnote_insn (insn
); p
!= delayed_insn
;
1906 p
= next_nonnote_insn (p
))
1907 for (link
= REG_NOTES (p
); link
; link
= next
)
1909 next
= XEXP (link
, 1);
1911 if (REG_NOTE_KIND (link
) != REG_DEAD
1912 || !REG_P (XEXP (link
, 0)))
1915 if (reg_referenced_p (XEXP (link
, 0), PATTERN (insn
)))
1917 /* Move the REG_DEAD note from P to INSN. */
1918 remove_note (p
, link
);
1919 XEXP (link
, 1) = REG_NOTES (insn
);
1920 REG_NOTES (insn
) = link
;
1925 /* Called when an insn redundant with start_insn is deleted. If there
1926 is a REG_DEAD note for the target of start_insn between start_insn
1927 and stop_insn, then the REG_DEAD note needs to be deleted since the
1928 value no longer dies there.
1930 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1931 confused into thinking the register is dead. */
1934 fix_reg_dead_note (rtx start_insn
, rtx stop_insn
)
1938 for (p
= next_nonnote_insn (start_insn
); p
!= stop_insn
;
1939 p
= next_nonnote_insn (p
))
1940 for (link
= REG_NOTES (p
); link
; link
= next
)
1942 next
= XEXP (link
, 1);
1944 if (REG_NOTE_KIND (link
) != REG_DEAD
1945 || !REG_P (XEXP (link
, 0)))
1948 if (reg_set_p (XEXP (link
, 0), PATTERN (start_insn
)))
1950 remove_note (p
, link
);
1956 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
1958 This handles the case of udivmodXi4 instructions which optimize their
1959 output depending on whether any REG_UNUSED notes are present.
1960 we must make sure that INSN calculates as many results as REDUNDANT_INSN
1964 update_reg_unused_notes (rtx insn
, rtx redundant_insn
)
1968 for (link
= REG_NOTES (insn
); link
; link
= next
)
1970 next
= XEXP (link
, 1);
1972 if (REG_NOTE_KIND (link
) != REG_UNUSED
1973 || !REG_P (XEXP (link
, 0)))
1976 if (! find_regno_note (redundant_insn
, REG_UNUSED
,
1977 REGNO (XEXP (link
, 0))))
1978 remove_note (insn
, link
);
1982 /* Return the label before INSN, or put a new label there. */
1985 get_label_before (rtx insn
)
1989 /* Find an existing label at this point
1990 or make a new one if there is none. */
1991 label
= prev_nonnote_insn (insn
);
1993 if (label
== 0 || !LABEL_P (label
))
1995 rtx prev
= PREV_INSN (insn
);
1997 label
= gen_label_rtx ();
1998 emit_label_after (label
, prev
);
1999 LABEL_NUSES (label
) = 0;
2004 /* Scan a function looking for insns that need a delay slot and find insns to
2005 put into the delay slot.
2007 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
2008 as calls). We do these first since we don't want jump insns (that are
2009 easier to fill) to get the only insns that could be used for non-jump insns.
2010 When it is zero, only try to fill JUMP_INSNs.
2012 When slots are filled in this manner, the insns (including the
2013 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2014 it is possible to tell whether a delay slot has really been filled
2015 or not. `final' knows how to deal with this, by communicating
2016 through FINAL_SEQUENCE. */
2019 fill_simple_delay_slots (int non_jumps_p
)
2021 rtx insn
, pat
, trial
, next_trial
;
2023 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
2024 struct resources needed
, set
;
2025 int slots_to_fill
, slots_filled
;
2028 for (i
= 0; i
< num_unfilled_slots
; i
++)
2031 /* Get the next insn to fill. If it has already had any slots assigned,
2032 we can't do anything with it. Maybe we'll improve this later. */
2034 insn
= unfilled_slots_base
[i
];
2036 || INSN_DELETED_P (insn
)
2037 || (NONJUMP_INSN_P (insn
)
2038 && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
2039 || (JUMP_P (insn
) && non_jumps_p
)
2040 || (!JUMP_P (insn
) && ! non_jumps_p
))
2043 /* It may have been that this insn used to need delay slots, but
2044 now doesn't; ignore in that case. This can happen, for example,
2045 on the HP PA RISC, where the number of delay slots depends on
2046 what insns are nearby. */
2047 slots_to_fill
= num_delay_slots (insn
);
2049 /* Some machine description have defined instructions to have
2050 delay slots only in certain circumstances which may depend on
2051 nearby insns (which change due to reorg's actions).
2053 For example, the PA port normally has delay slots for unconditional
2056 However, the PA port claims such jumps do not have a delay slot
2057 if they are immediate successors of certain CALL_INSNs. This
2058 allows the port to favor filling the delay slot of the call with
2059 the unconditional jump. */
2060 if (slots_to_fill
== 0)
2063 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2064 says how many. After initialization, first try optimizing
2067 nop add %o7,.-L1,%o7
2071 If this case applies, the delay slot of the call is filled with
2072 the unconditional jump. This is done first to avoid having the
2073 delay slot of the call filled in the backward scan. Also, since
2074 the unconditional jump is likely to also have a delay slot, that
2075 insn must exist when it is subsequently scanned.
2077 This is tried on each insn with delay slots as some machines
2078 have insns which perform calls, but are not represented as
2085 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2087 flags
= get_jump_flags (insn
, NULL_RTX
);
2089 if ((trial
= next_active_insn (insn
))
2091 && simplejump_p (trial
)
2092 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2093 && no_labels_between_p (insn
, trial
)
2094 && ! can_throw_internal (trial
))
2098 delay_list
= add_to_delay_list (trial
, delay_list
);
2100 /* TRIAL may have had its delay slot filled, then unfilled. When
2101 the delay slot is unfilled, TRIAL is placed back on the unfilled
2102 slots obstack. Unfortunately, it is placed on the end of the
2103 obstack, not in its original location. Therefore, we must search
2104 from entry i + 1 to the end of the unfilled slots obstack to
2105 try and find TRIAL. */
2106 tmp
= &unfilled_slots_base
[i
+ 1];
2107 while (*tmp
!= trial
&& tmp
!= unfilled_slots_next
)
2110 /* Remove the unconditional jump from consideration for delay slot
2111 filling and unthread it. */
2115 rtx next
= NEXT_INSN (trial
);
2116 rtx prev
= PREV_INSN (trial
);
2118 NEXT_INSN (prev
) = next
;
2120 PREV_INSN (next
) = prev
;
2124 /* Now, scan backwards from the insn to search for a potential
2125 delay-slot candidate. Stop searching when a label or jump is hit.
2127 For each candidate, if it is to go into the delay slot (moved
2128 forward in execution sequence), it must not need or set any resources
2129 that were set by later insns and must not set any resources that
2130 are needed for those insns.
2132 The delay slot insn itself sets resources unless it is a call
2133 (in which case the called routine, not the insn itself, is doing
2136 if (slots_filled
< slots_to_fill
)
2138 CLEAR_RESOURCE (&needed
);
2139 CLEAR_RESOURCE (&set
);
2140 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST
);
2141 mark_referenced_resources (insn
, &needed
, false);
2143 for (trial
= prev_nonnote_insn (insn
); ! stop_search_p (trial
, 1);
2146 next_trial
= prev_nonnote_insn (trial
);
2148 /* This must be an INSN or CALL_INSN. */
2149 pat
= PATTERN (trial
);
2151 /* Stand-alone USE and CLOBBER are just for flow. */
2152 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2155 /* Check for resource conflict first, to avoid unnecessary
2157 if (! insn_references_resource_p (trial
, &set
, true)
2158 && ! insn_sets_resource_p (trial
, &set
, true)
2159 && ! insn_sets_resource_p (trial
, &needed
, true)
2161 /* Can't separate set of cc0 from its use. */
2162 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2164 && ! can_throw_internal (trial
))
2166 trial
= try_split (pat
, trial
, 1);
2167 next_trial
= prev_nonnote_insn (trial
);
2168 if (eligible_for_delay (insn
, slots_filled
, trial
, flags
))
2170 /* In this case, we are searching backward, so if we
2171 find insns to put on the delay list, we want
2172 to put them at the head, rather than the
2173 tail, of the list. */
2175 update_reg_dead_notes (trial
, insn
);
2176 delay_list
= gen_rtx_INSN_LIST (VOIDmode
,
2178 update_block (trial
, trial
);
2179 delete_related_insns (trial
);
2180 if (slots_to_fill
== ++slots_filled
)
2186 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2187 mark_referenced_resources (trial
, &needed
, true);
2191 /* If all needed slots haven't been filled, we come here. */
2193 /* Try to optimize case of jumping around a single insn. */
2194 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2195 if (slots_filled
!= slots_to_fill
2198 && (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
2200 delay_list
= optimize_skip (insn
);
2206 /* Try to get insns from beyond the insn needing the delay slot.
2207 These insns can neither set or reference resources set in insns being
2208 skipped, cannot set resources in the insn being skipped, and, if this
2209 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2210 call might not return).
2212 There used to be code which continued past the target label if
2213 we saw all uses of the target label. This code did not work,
2214 because it failed to account for some instructions which were
2215 both annulled and marked as from the target. This can happen as a
2216 result of optimize_skip. Since this code was redundant with
2217 fill_eager_delay_slots anyways, it was just deleted. */
2219 if (slots_filled
!= slots_to_fill
2220 /* If this instruction could throw an exception which is
2221 caught in the same function, then it's not safe to fill
2222 the delay slot with an instruction from beyond this
2223 point. For example, consider:
2234 Even though `i' is a local variable, we must be sure not
2235 to put `i = 3' in the delay slot if `f' might throw an
2238 Presumably, we should also check to see if we could get
2239 back to this function via `setjmp'. */
2240 && ! can_throw_internal (insn
)
2242 || ((condjump_p (insn
) || condjump_in_parallel_p (insn
))
2243 && ! simplejump_p (insn
)
2244 && !ANY_RETURN_P (JUMP_LABEL (insn
)))))
2246 /* Invariant: If insn is a JUMP_INSN, the insn's jump
2247 label. Otherwise, zero. */
2249 int maybe_never
= 0;
2250 rtx pat
, trial_delay
;
2252 CLEAR_RESOURCE (&needed
);
2253 CLEAR_RESOURCE (&set
);
2257 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2258 mark_referenced_resources (insn
, &needed
, true);
2263 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2264 mark_referenced_resources (insn
, &needed
, true);
2266 target
= JUMP_LABEL (insn
);
2269 if (target
== 0 || ANY_RETURN_P (target
))
2270 for (trial
= next_nonnote_insn (insn
); !stop_search_p (trial
, 1);
2273 next_trial
= next_nonnote_insn (trial
);
2275 /* This must be an INSN or CALL_INSN. */
2276 pat
= PATTERN (trial
);
2278 /* Stand-alone USE and CLOBBER are just for flow. */
2279 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2282 /* If this already has filled delay slots, get the insn needing
2284 if (GET_CODE (pat
) == SEQUENCE
)
2285 trial_delay
= XVECEXP (pat
, 0, 0);
2287 trial_delay
= trial
;
2289 /* Stop our search when seeing a jump. */
2290 if (JUMP_P (trial_delay
))
2293 /* See if we have a resource problem before we try to
2295 if (GET_CODE (pat
) != SEQUENCE
2296 && ! insn_references_resource_p (trial
, &set
, true)
2297 && ! insn_sets_resource_p (trial
, &set
, true)
2298 && ! insn_sets_resource_p (trial
, &needed
, true)
2300 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2302 && ! (maybe_never
&& may_trap_or_fault_p (pat
))
2303 && (trial
= try_split (pat
, trial
, 0))
2304 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2305 && ! can_throw_internal(trial
))
2307 next_trial
= next_nonnote_insn (trial
);
2308 delay_list
= add_to_delay_list (trial
, delay_list
);
2311 if (reg_mentioned_p (cc0_rtx
, pat
))
2312 link_cc0_insns (trial
);
2315 delete_related_insns (trial
);
2316 if (slots_to_fill
== ++slots_filled
)
2321 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2322 mark_referenced_resources (trial
, &needed
, true);
2324 /* Ensure we don't put insns between the setting of cc and the
2325 comparison by moving a setting of cc into an earlier delay
2326 slot since these insns could clobber the condition code. */
2329 /* If this is a call or jump, we might not get here. */
2330 if (CALL_P (trial_delay
)
2331 || JUMP_P (trial_delay
))
2335 /* If there are slots left to fill and our search was stopped by an
2336 unconditional branch, try the insn at the branch target. We can
2337 redirect the branch if it works.
2339 Don't do this if the insn at the branch target is a branch. */
2340 if (slots_to_fill
!= slots_filled
2342 && jump_to_label_p (trial
)
2343 && simplejump_p (trial
)
2344 && (target
== 0 || JUMP_LABEL (trial
) == target
)
2345 && (next_trial
= next_active_insn (JUMP_LABEL (trial
))) != 0
2346 && ! (NONJUMP_INSN_P (next_trial
)
2347 && GET_CODE (PATTERN (next_trial
)) == SEQUENCE
)
2348 && !JUMP_P (next_trial
)
2349 && ! insn_references_resource_p (next_trial
, &set
, true)
2350 && ! insn_sets_resource_p (next_trial
, &set
, true)
2351 && ! insn_sets_resource_p (next_trial
, &needed
, true)
2353 && ! reg_mentioned_p (cc0_rtx
, PATTERN (next_trial
))
2355 && ! (maybe_never
&& may_trap_or_fault_p (PATTERN (next_trial
)))
2356 && (next_trial
= try_split (PATTERN (next_trial
), next_trial
, 0))
2357 && eligible_for_delay (insn
, slots_filled
, next_trial
, flags
)
2358 && ! can_throw_internal (trial
))
2360 /* See comment in relax_delay_slots about necessity of using
2361 next_real_insn here. */
2362 rtx new_label
= next_real_insn (next_trial
);
2365 new_label
= get_label_before (new_label
);
2367 new_label
= find_end_label (simple_return_rtx
);
2372 = add_to_delay_list (copy_rtx (next_trial
), delay_list
);
2374 reorg_redirect_jump (trial
, new_label
);
2376 /* If we merged because we both jumped to the same place,
2377 redirect the original insn also. */
2379 reorg_redirect_jump (insn
, new_label
);
2384 /* If this is an unconditional jump, then try to get insns from the
2385 target of the jump. */
2387 && simplejump_p (insn
)
2388 && slots_filled
!= slots_to_fill
)
2390 = fill_slots_from_thread (insn
, const_true_rtx
,
2391 next_active_insn (JUMP_LABEL (insn
)),
2393 own_thread_p (JUMP_LABEL (insn
),
2394 JUMP_LABEL (insn
), 0),
2395 slots_to_fill
, &slots_filled
,
2399 unfilled_slots_base
[i
]
2400 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
2402 if (slots_to_fill
== slots_filled
)
2403 unfilled_slots_base
[i
] = 0;
2405 note_delay_statistics (slots_filled
, 0);
2408 #ifdef DELAY_SLOTS_FOR_EPILOGUE
2409 /* See if the epilogue needs any delay slots. Try to fill them if so.
2410 The only thing we can do is scan backwards from the end of the
2411 function. If we did this in a previous pass, it is incorrect to do it
2413 if (crtl
->epilogue_delay_list
)
2416 slots_to_fill
= DELAY_SLOTS_FOR_EPILOGUE
;
2417 if (slots_to_fill
== 0)
2421 CLEAR_RESOURCE (&set
);
2423 /* The frame pointer and stack pointer are needed at the beginning of
2424 the epilogue, so instructions setting them can not be put in the
2425 epilogue delay slot. However, everything else needed at function
2426 end is safe, so we don't want to use end_of_function_needs here. */
2427 CLEAR_RESOURCE (&needed
);
2428 if (frame_pointer_needed
)
2430 SET_HARD_REG_BIT (needed
.regs
, FRAME_POINTER_REGNUM
);
2431 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2432 SET_HARD_REG_BIT (needed
.regs
, HARD_FRAME_POINTER_REGNUM
);
2434 if (! EXIT_IGNORE_STACK
2435 || crtl
->sp_is_unchanging
)
2436 SET_HARD_REG_BIT (needed
.regs
, STACK_POINTER_REGNUM
);
2439 SET_HARD_REG_BIT (needed
.regs
, STACK_POINTER_REGNUM
);
2441 #ifdef EPILOGUE_USES
2442 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
2444 if (EPILOGUE_USES (i
))
2445 SET_HARD_REG_BIT (needed
.regs
, i
);
2449 for (trial
= get_last_insn (); ! stop_search_p (trial
, 1);
2450 trial
= PREV_INSN (trial
))
2454 pat
= PATTERN (trial
);
2455 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2458 if (! insn_references_resource_p (trial
, &set
, true)
2459 && ! insn_sets_resource_p (trial
, &needed
, true)
2460 && ! insn_sets_resource_p (trial
, &set
, true)
2462 /* Don't want to mess with cc0 here. */
2463 && ! reg_mentioned_p (cc0_rtx
, pat
)
2465 && ! can_throw_internal (trial
))
2467 trial
= try_split (pat
, trial
, 1);
2468 if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial
, slots_filled
))
2470 /* Here as well we are searching backward, so put the
2471 insns we find on the head of the list. */
2473 crtl
->epilogue_delay_list
2474 = gen_rtx_INSN_LIST (VOIDmode
, trial
,
2475 crtl
->epilogue_delay_list
);
2476 mark_end_of_function_resources (trial
, true);
2477 update_block (trial
, trial
);
2478 delete_related_insns (trial
);
2480 /* Clear deleted bit so final.c will output the insn. */
2481 INSN_DELETED_P (trial
) = 0;
2483 if (slots_to_fill
== ++slots_filled
)
2489 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2490 mark_referenced_resources (trial
, &needed
, true);
2493 note_delay_statistics (slots_filled
, 0);
2497 /* Follow any unconditional jump at LABEL, for the purpose of redirecting JUMP;
2498 return the ultimate label reached by any such chain of jumps.
2499 Return a suitable return rtx if the chain ultimately leads to a
2501 If LABEL is not followed by a jump, return LABEL.
2502 If the chain loops or we can't find end, return LABEL,
2503 since that tells caller to avoid changing the insn.
2504 If the returned label is obtained by following a REG_CROSSING_JUMP
2505 jump, set *CROSSING to true, otherwise set it to false. */
2508 follow_jumps (rtx label
, rtx jump
, bool *crossing
)
2516 if (ANY_RETURN_P (label
))
2520 && (insn
= next_active_insn (value
)) != 0
2522 && JUMP_LABEL (insn
) != NULL_RTX
2523 && ((any_uncondjump_p (insn
) && onlyjump_p (insn
))
2524 || ANY_RETURN_P (PATTERN (insn
)))
2525 && (next
= NEXT_INSN (insn
))
2526 && BARRIER_P (next
));
2529 rtx this_label
= JUMP_LABEL (insn
);
2532 /* If we have found a cycle, make the insn jump to itself. */
2533 if (this_label
== label
)
2535 if (ANY_RETURN_P (this_label
))
2537 tem
= next_active_insn (this_label
);
2539 && (GET_CODE (PATTERN (tem
)) == ADDR_VEC
2540 || GET_CODE (PATTERN (tem
)) == ADDR_DIFF_VEC
))
2543 if (!targetm
.can_follow_jump (jump
, insn
))
2547 = find_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
) != NULL_RTX
;
2555 /* Try to find insns to place in delay slots.
2557 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2558 or is an unconditional branch if CONDITION is const_true_rtx.
2559 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2561 THREAD is a flow-of-control, either the insns to be executed if the
2562 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2564 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2565 to see if any potential delay slot insns set things needed there.
2567 LIKELY is nonzero if it is extremely likely that the branch will be
2568 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2569 end of a loop back up to the top.
2571 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2572 thread. I.e., it is the fallthrough code of our jump or the target of the
2573 jump when we are the only jump going there.
2575 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2576 case, we can only take insns from the head of the thread for our delay
2577 slot. We then adjust the jump to point after the insns we have taken. */
2580 fill_slots_from_thread (rtx insn
, rtx condition
, rtx thread
,
2581 rtx opposite_thread
, int likely
, int thread_if_true
,
2582 int own_thread
, int slots_to_fill
,
2583 int *pslots_filled
, rtx delay_list
)
2586 struct resources opposite_needed
, set
, needed
;
2592 /* Validate our arguments. */
2593 gcc_assert(condition
!= const_true_rtx
|| thread_if_true
);
2594 gcc_assert(own_thread
|| thread_if_true
);
2596 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2598 /* If our thread is the end of subroutine, we can't get any delay
2600 if (thread
== NULL_RTX
|| ANY_RETURN_P (thread
))
2603 /* If this is an unconditional branch, nothing is needed at the
2604 opposite thread. Otherwise, compute what is needed there. */
2605 if (condition
== const_true_rtx
)
2606 CLEAR_RESOURCE (&opposite_needed
);
2608 mark_target_live_regs (get_insns (), opposite_thread
, &opposite_needed
);
2610 /* If the insn at THREAD can be split, do it here to avoid having to
2611 update THREAD and NEW_THREAD if it is done in the loop below. Also
2612 initialize NEW_THREAD. */
2614 new_thread
= thread
= try_split (PATTERN (thread
), thread
, 0);
2616 /* Scan insns at THREAD. We are looking for an insn that can be removed
2617 from THREAD (it neither sets nor references resources that were set
2618 ahead of it and it doesn't set anything needs by the insns ahead of
2619 it) and that either can be placed in an annulling insn or aren't
2620 needed at OPPOSITE_THREAD. */
2622 CLEAR_RESOURCE (&needed
);
2623 CLEAR_RESOURCE (&set
);
2625 /* If we do not own this thread, we must stop as soon as we find
2626 something that we can't put in a delay slot, since all we can do
2627 is branch into THREAD at a later point. Therefore, labels stop
2628 the search if this is not the `true' thread. */
2630 for (trial
= thread
;
2631 ! stop_search_p (trial
, ! thread_if_true
) && (! lose
|| own_thread
);
2632 trial
= next_nonnote_insn (trial
))
2636 /* If we have passed a label, we no longer own this thread. */
2637 if (LABEL_P (trial
))
2643 pat
= PATTERN (trial
);
2644 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2647 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2648 don't separate or copy insns that set and use CC0. */
2649 if (! insn_references_resource_p (trial
, &set
, true)
2650 && ! insn_sets_resource_p (trial
, &set
, true)
2651 && ! insn_sets_resource_p (trial
, &needed
, true)
2653 && ! (reg_mentioned_p (cc0_rtx
, pat
)
2654 && (! own_thread
|| ! sets_cc0_p (pat
)))
2656 && ! can_throw_internal (trial
))
2660 /* If TRIAL is redundant with some insn before INSN, we don't
2661 actually need to add it to the delay list; we can merely pretend
2663 if ((prior_insn
= redundant_insn (trial
, insn
, delay_list
)))
2665 fix_reg_dead_note (prior_insn
, insn
);
2668 update_block (trial
, thread
);
2669 if (trial
== thread
)
2671 thread
= next_active_insn (thread
);
2672 if (new_thread
== trial
)
2673 new_thread
= thread
;
2676 delete_related_insns (trial
);
2680 update_reg_unused_notes (prior_insn
, trial
);
2681 new_thread
= next_active_insn (trial
);
2687 /* There are two ways we can win: If TRIAL doesn't set anything
2688 needed at the opposite thread and can't trap, or if it can
2689 go into an annulled delay slot. */
2691 && (condition
== const_true_rtx
2692 || (! insn_sets_resource_p (trial
, &opposite_needed
, true)
2693 && ! may_trap_or_fault_p (pat
)
2694 && ! RTX_FRAME_RELATED_P (trial
))))
2697 trial
= try_split (pat
, trial
, 0);
2698 if (new_thread
== old_trial
)
2700 if (thread
== old_trial
)
2702 pat
= PATTERN (trial
);
2703 if (eligible_for_delay (insn
, *pslots_filled
, trial
, flags
))
2707 #ifdef ANNUL_IFTRUE_SLOTS
2710 #ifdef ANNUL_IFFALSE_SLOTS
2716 trial
= try_split (pat
, trial
, 0);
2717 if (new_thread
== old_trial
)
2719 if (thread
== old_trial
)
2721 pat
= PATTERN (trial
);
2722 if ((must_annul
|| delay_list
== NULL
) && (thread_if_true
2723 ? check_annul_list_true_false (0, delay_list
)
2724 && eligible_for_annul_false (insn
, *pslots_filled
, trial
, flags
)
2725 : check_annul_list_true_false (1, delay_list
)
2726 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
2734 if (reg_mentioned_p (cc0_rtx
, pat
))
2735 link_cc0_insns (trial
);
2738 /* If we own this thread, delete the insn. If this is the
2739 destination of a branch, show that a basic block status
2740 may have been updated. In any case, mark the new
2741 starting point of this thread. */
2746 update_block (trial
, thread
);
2747 if (trial
== thread
)
2749 thread
= next_active_insn (thread
);
2750 if (new_thread
== trial
)
2751 new_thread
= thread
;
2754 /* We are moving this insn, not deleting it. We must
2755 temporarily increment the use count on any referenced
2756 label lest it be deleted by delete_related_insns. */
2757 for (note
= REG_NOTES (trial
);
2759 note
= XEXP (note
, 1))
2760 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2761 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2763 /* REG_LABEL_OPERAND could be
2764 NOTE_INSN_DELETED_LABEL too. */
2765 if (LABEL_P (XEXP (note
, 0)))
2766 LABEL_NUSES (XEXP (note
, 0))++;
2768 gcc_assert (REG_NOTE_KIND (note
)
2769 == REG_LABEL_OPERAND
);
2771 if (jump_to_label_p (trial
))
2772 LABEL_NUSES (JUMP_LABEL (trial
))++;
2774 delete_related_insns (trial
);
2776 for (note
= REG_NOTES (trial
);
2778 note
= XEXP (note
, 1))
2779 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2780 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2782 /* REG_LABEL_OPERAND could be
2783 NOTE_INSN_DELETED_LABEL too. */
2784 if (LABEL_P (XEXP (note
, 0)))
2785 LABEL_NUSES (XEXP (note
, 0))--;
2787 gcc_assert (REG_NOTE_KIND (note
)
2788 == REG_LABEL_OPERAND
);
2790 if (jump_to_label_p (trial
))
2791 LABEL_NUSES (JUMP_LABEL (trial
))--;
2794 new_thread
= next_active_insn (trial
);
2796 temp
= own_thread
? trial
: copy_rtx (trial
);
2798 INSN_FROM_TARGET_P (temp
) = 1;
2800 delay_list
= add_to_delay_list (temp
, delay_list
);
2802 if (slots_to_fill
== ++(*pslots_filled
))
2804 /* Even though we have filled all the slots, we
2805 may be branching to a location that has a
2806 redundant insn. Skip any if so. */
2807 while (new_thread
&& ! own_thread
2808 && ! insn_sets_resource_p (new_thread
, &set
, true)
2809 && ! insn_sets_resource_p (new_thread
, &needed
,
2811 && ! insn_references_resource_p (new_thread
,
2814 = redundant_insn (new_thread
, insn
,
2817 /* We know we do not own the thread, so no need
2818 to call update_block and delete_insn. */
2819 fix_reg_dead_note (prior_insn
, insn
);
2820 update_reg_unused_notes (prior_insn
, new_thread
);
2821 new_thread
= next_active_insn (new_thread
);
2831 /* This insn can't go into a delay slot. */
2833 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2834 mark_referenced_resources (trial
, &needed
, true);
2836 /* Ensure we don't put insns between the setting of cc and the comparison
2837 by moving a setting of cc into an earlier delay slot since these insns
2838 could clobber the condition code. */
2841 /* If this insn is a register-register copy and the next insn has
2842 a use of our destination, change it to use our source. That way,
2843 it will become a candidate for our delay slot the next time
2844 through this loop. This case occurs commonly in loops that
2847 We could check for more complex cases than those tested below,
2848 but it doesn't seem worth it. It might also be a good idea to try
2849 to swap the two insns. That might do better.
2851 We can't do this if the next insn modifies our destination, because
2852 that would make the replacement into the insn invalid. We also can't
2853 do this if it modifies our source, because it might be an earlyclobber
2854 operand. This latter test also prevents updating the contents of
2855 a PRE_INC. We also can't do this if there's overlap of source and
2856 destination. Overlap may happen for larger-than-register-size modes. */
2858 if (NONJUMP_INSN_P (trial
) && GET_CODE (pat
) == SET
2859 && REG_P (SET_SRC (pat
))
2860 && REG_P (SET_DEST (pat
))
2861 && !reg_overlap_mentioned_p (SET_DEST (pat
), SET_SRC (pat
)))
2863 rtx next
= next_nonnote_insn (trial
);
2865 if (next
&& NONJUMP_INSN_P (next
)
2866 && GET_CODE (PATTERN (next
)) != USE
2867 && ! reg_set_p (SET_DEST (pat
), next
)
2868 && ! reg_set_p (SET_SRC (pat
), next
)
2869 && reg_referenced_p (SET_DEST (pat
), PATTERN (next
))
2870 && ! modified_in_p (SET_DEST (pat
), next
))
2871 validate_replace_rtx (SET_DEST (pat
), SET_SRC (pat
), next
);
2875 /* If we stopped on a branch insn that has delay slots, see if we can
2876 steal some of the insns in those slots. */
2877 if (trial
&& NONJUMP_INSN_P (trial
)
2878 && GET_CODE (PATTERN (trial
)) == SEQUENCE
2879 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0)))
2881 /* If this is the `true' thread, we will want to follow the jump,
2882 so we can only do this if we have taken everything up to here. */
2883 if (thread_if_true
&& trial
== new_thread
)
2886 = steal_delay_list_from_target (insn
, condition
, PATTERN (trial
),
2887 delay_list
, &set
, &needed
,
2888 &opposite_needed
, slots_to_fill
,
2889 pslots_filled
, &must_annul
,
2891 /* If we owned the thread and are told that it branched
2892 elsewhere, make sure we own the thread at the new location. */
2893 if (own_thread
&& trial
!= new_thread
)
2894 own_thread
= own_thread_p (new_thread
, new_thread
, 0);
2896 else if (! thread_if_true
)
2898 = steal_delay_list_from_fallthrough (insn
, condition
,
2900 delay_list
, &set
, &needed
,
2901 &opposite_needed
, slots_to_fill
,
2902 pslots_filled
, &must_annul
);
2905 /* If we haven't found anything for this delay slot and it is very
2906 likely that the branch will be taken, see if the insn at our target
2907 increments or decrements a register with an increment that does not
2908 depend on the destination register. If so, try to place the opposite
2909 arithmetic insn after the jump insn and put the arithmetic insn in the
2910 delay slot. If we can't do this, return. */
2911 if (delay_list
== 0 && likely
2912 && new_thread
&& !ANY_RETURN_P (new_thread
)
2913 && NONJUMP_INSN_P (new_thread
)
2914 && !RTX_FRAME_RELATED_P (new_thread
)
2915 && GET_CODE (PATTERN (new_thread
)) != ASM_INPUT
2916 && asm_noperands (PATTERN (new_thread
)) < 0)
2918 rtx pat
= PATTERN (new_thread
);
2923 pat
= PATTERN (trial
);
2925 if (!NONJUMP_INSN_P (trial
)
2926 || GET_CODE (pat
) != SET
2927 || ! eligible_for_delay (insn
, 0, trial
, flags
)
2928 || can_throw_internal (trial
))
2931 dest
= SET_DEST (pat
), src
= SET_SRC (pat
);
2932 if ((GET_CODE (src
) == PLUS
|| GET_CODE (src
) == MINUS
)
2933 && rtx_equal_p (XEXP (src
, 0), dest
)
2934 && (!FLOAT_MODE_P (GET_MODE (src
))
2935 || flag_unsafe_math_optimizations
)
2936 && ! reg_overlap_mentioned_p (dest
, XEXP (src
, 1))
2937 && ! side_effects_p (pat
))
2939 rtx other
= XEXP (src
, 1);
2943 /* If this is a constant adjustment, use the same code with
2944 the negated constant. Otherwise, reverse the sense of the
2946 if (CONST_INT_P (other
))
2947 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
), GET_MODE (src
), dest
,
2948 negate_rtx (GET_MODE (src
), other
));
2950 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
) == PLUS
? MINUS
: PLUS
,
2951 GET_MODE (src
), dest
, other
);
2953 ninsn
= emit_insn_after (gen_rtx_SET (VOIDmode
, dest
, new_arith
),
2956 if (recog_memoized (ninsn
) < 0
2957 || (extract_insn (ninsn
), ! constrain_operands (1)))
2959 delete_related_insns (ninsn
);
2965 update_block (trial
, thread
);
2966 if (trial
== thread
)
2968 thread
= next_active_insn (thread
);
2969 if (new_thread
== trial
)
2970 new_thread
= thread
;
2972 delete_related_insns (trial
);
2975 new_thread
= next_active_insn (trial
);
2977 ninsn
= own_thread
? trial
: copy_rtx (trial
);
2979 INSN_FROM_TARGET_P (ninsn
) = 1;
2981 delay_list
= add_to_delay_list (ninsn
, NULL_RTX
);
2986 if (delay_list
&& must_annul
)
2987 INSN_ANNULLED_BRANCH_P (insn
) = 1;
2989 /* If we are to branch into the middle of this thread, find an appropriate
2990 label or make a new one if none, and redirect INSN to it. If we hit the
2991 end of the function, use the end-of-function label. */
2992 if (new_thread
!= thread
)
2995 bool crossing
= false;
2997 gcc_assert (thread_if_true
);
2999 if (new_thread
&& simplejump_or_return_p (new_thread
)
3000 && redirect_with_delay_list_safe_p (insn
,
3001 JUMP_LABEL (new_thread
),
3003 new_thread
= follow_jumps (JUMP_LABEL (new_thread
), insn
, &crossing
);
3005 if (ANY_RETURN_P (new_thread
))
3006 label
= find_end_label (new_thread
);
3007 else if (LABEL_P (new_thread
))
3010 label
= get_label_before (new_thread
);
3014 reorg_redirect_jump (insn
, label
);
3016 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
3023 /* Make another attempt to find insns to place in delay slots.
3025 We previously looked for insns located in front of the delay insn
3026 and, for non-jump delay insns, located behind the delay insn.
3028 Here only try to schedule jump insns and try to move insns from either
3029 the target or the following insns into the delay slot. If annulling is
3030 supported, we will be likely to do this. Otherwise, we can do this only
3034 fill_eager_delay_slots (void)
3038 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
3040 for (i
= 0; i
< num_unfilled_slots
; i
++)
3043 rtx target_label
, insn_at_target
, fallthrough_insn
;
3046 int own_fallthrough
;
3047 int prediction
, slots_to_fill
, slots_filled
;
3049 insn
= unfilled_slots_base
[i
];
3051 || INSN_DELETED_P (insn
)
3053 || ! (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
3056 slots_to_fill
= num_delay_slots (insn
);
3057 /* Some machine description have defined instructions to have
3058 delay slots only in certain circumstances which may depend on
3059 nearby insns (which change due to reorg's actions).
3061 For example, the PA port normally has delay slots for unconditional
3064 However, the PA port claims such jumps do not have a delay slot
3065 if they are immediate successors of certain CALL_INSNs. This
3066 allows the port to favor filling the delay slot of the call with
3067 the unconditional jump. */
3068 if (slots_to_fill
== 0)
3072 target_label
= JUMP_LABEL (insn
);
3073 condition
= get_branch_condition (insn
, target_label
);
3078 /* Get the next active fallthrough and target insns and see if we own
3079 them. Then see whether the branch is likely true. We don't need
3080 to do a lot of this for unconditional branches. */
3082 insn_at_target
= first_active_target_insn (target_label
);
3083 own_target
= own_thread_p (target_label
, target_label
, 0);
3085 if (condition
== const_true_rtx
)
3087 own_fallthrough
= 0;
3088 fallthrough_insn
= 0;
3093 fallthrough_insn
= next_active_insn (insn
);
3094 own_fallthrough
= own_thread_p (NEXT_INSN (insn
), NULL_RTX
, 1);
3095 prediction
= mostly_true_jump (insn
, condition
);
3098 /* If this insn is expected to branch, first try to get insns from our
3099 target, then our fallthrough insns. If it is not expected to branch,
3100 try the other order. */
3105 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
3106 fallthrough_insn
, prediction
== 2, 1,
3108 slots_to_fill
, &slots_filled
, delay_list
);
3110 if (delay_list
== 0 && own_fallthrough
)
3112 /* Even though we didn't find anything for delay slots,
3113 we might have found a redundant insn which we deleted
3114 from the thread that was filled. So we have to recompute
3115 the next insn at the target. */
3116 target_label
= JUMP_LABEL (insn
);
3117 insn_at_target
= first_active_target_insn (target_label
);
3120 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
3121 insn_at_target
, 0, 0,
3123 slots_to_fill
, &slots_filled
,
3129 if (own_fallthrough
)
3131 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
3132 insn_at_target
, 0, 0,
3134 slots_to_fill
, &slots_filled
,
3137 if (delay_list
== 0)
3139 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
3140 next_active_insn (insn
), 0, 1,
3142 slots_to_fill
, &slots_filled
,
3147 unfilled_slots_base
[i
]
3148 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
3150 if (slots_to_fill
== slots_filled
)
3151 unfilled_slots_base
[i
] = 0;
3153 note_delay_statistics (slots_filled
, 1);
3157 static void delete_computation (rtx insn
);
3159 /* Recursively delete prior insns that compute the value (used only by INSN
3160 which the caller is deleting) stored in the register mentioned by NOTE
3161 which is a REG_DEAD note associated with INSN. */
3164 delete_prior_computation (rtx note
, rtx insn
)
3167 rtx reg
= XEXP (note
, 0);
3169 for (our_prev
= prev_nonnote_insn (insn
);
3170 our_prev
&& (NONJUMP_INSN_P (our_prev
)
3171 || CALL_P (our_prev
));
3172 our_prev
= prev_nonnote_insn (our_prev
))
3174 rtx pat
= PATTERN (our_prev
);
3176 /* If we reach a CALL which is not calling a const function
3177 or the callee pops the arguments, then give up. */
3178 if (CALL_P (our_prev
)
3179 && (! RTL_CONST_CALL_P (our_prev
)
3180 || GET_CODE (pat
) != SET
|| GET_CODE (SET_SRC (pat
)) != CALL
))
3183 /* If we reach a SEQUENCE, it is too complex to try to
3184 do anything with it, so give up. We can be run during
3185 and after reorg, so SEQUENCE rtl can legitimately show
3187 if (GET_CODE (pat
) == SEQUENCE
)
3190 if (GET_CODE (pat
) == USE
3191 && NONJUMP_INSN_P (XEXP (pat
, 0)))
3192 /* reorg creates USEs that look like this. We leave them
3193 alone because reorg needs them for its own purposes. */
3196 if (reg_set_p (reg
, pat
))
3198 if (side_effects_p (pat
) && !CALL_P (our_prev
))
3201 if (GET_CODE (pat
) == PARALLEL
)
3203 /* If we find a SET of something else, we can't
3208 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3210 rtx part
= XVECEXP (pat
, 0, i
);
3212 if (GET_CODE (part
) == SET
3213 && SET_DEST (part
) != reg
)
3217 if (i
== XVECLEN (pat
, 0))
3218 delete_computation (our_prev
);
3220 else if (GET_CODE (pat
) == SET
3221 && REG_P (SET_DEST (pat
)))
3223 int dest_regno
= REGNO (SET_DEST (pat
));
3224 int dest_endregno
= END_REGNO (SET_DEST (pat
));
3225 int regno
= REGNO (reg
);
3226 int endregno
= END_REGNO (reg
);
3228 if (dest_regno
>= regno
3229 && dest_endregno
<= endregno
)
3230 delete_computation (our_prev
);
3232 /* We may have a multi-word hard register and some, but not
3233 all, of the words of the register are needed in subsequent
3234 insns. Write REG_UNUSED notes for those parts that were not
3236 else if (dest_regno
<= regno
3237 && dest_endregno
>= endregno
)
3241 add_reg_note (our_prev
, REG_UNUSED
, reg
);
3243 for (i
= dest_regno
; i
< dest_endregno
; i
++)
3244 if (! find_regno_note (our_prev
, REG_UNUSED
, i
))
3247 if (i
== dest_endregno
)
3248 delete_computation (our_prev
);
3255 /* If PAT references the register that dies here, it is an
3256 additional use. Hence any prior SET isn't dead. However, this
3257 insn becomes the new place for the REG_DEAD note. */
3258 if (reg_overlap_mentioned_p (reg
, pat
))
3260 XEXP (note
, 1) = REG_NOTES (our_prev
);
3261 REG_NOTES (our_prev
) = note
;
3267 /* Delete INSN and recursively delete insns that compute values used only
3268 by INSN. This uses the REG_DEAD notes computed during flow analysis.
3270 Look at all our REG_DEAD notes. If a previous insn does nothing other
3271 than set a register that dies in this insn, we can delete that insn
3274 On machines with CC0, if CC0 is used in this insn, we may be able to
3275 delete the insn that set it. */
3278 delete_computation (rtx insn
)
3283 if (reg_referenced_p (cc0_rtx
, PATTERN (insn
)))
3285 rtx prev
= prev_nonnote_insn (insn
);
3286 /* We assume that at this stage
3287 CC's are always set explicitly
3288 and always immediately before the jump that
3289 will use them. So if the previous insn
3290 exists to set the CC's, delete it
3291 (unless it performs auto-increments, etc.). */
3292 if (prev
&& NONJUMP_INSN_P (prev
)
3293 && sets_cc0_p (PATTERN (prev
)))
3295 if (sets_cc0_p (PATTERN (prev
)) > 0
3296 && ! side_effects_p (PATTERN (prev
)))
3297 delete_computation (prev
);
3299 /* Otherwise, show that cc0 won't be used. */
3300 add_reg_note (prev
, REG_UNUSED
, cc0_rtx
);
3305 for (note
= REG_NOTES (insn
); note
; note
= next
)
3307 next
= XEXP (note
, 1);
3309 if (REG_NOTE_KIND (note
) != REG_DEAD
3310 /* Verify that the REG_NOTE is legitimate. */
3311 || !REG_P (XEXP (note
, 0)))
3314 delete_prior_computation (note
, insn
);
3317 delete_related_insns (insn
);
3320 /* If all INSN does is set the pc, delete it,
3321 and delete the insn that set the condition codes for it
3322 if that's what the previous thing was. */
3325 delete_jump (rtx insn
)
3327 rtx set
= single_set (insn
);
3329 if (set
&& GET_CODE (SET_DEST (set
)) == PC
)
3330 delete_computation (insn
);
3334 label_before_next_insn (rtx x
, rtx scan_limit
)
3336 rtx insn
= next_active_insn (x
);
3339 insn
= PREV_INSN (insn
);
3340 if (insn
== scan_limit
|| insn
== NULL_RTX
)
3349 /* Once we have tried two ways to fill a delay slot, make a pass over the
3350 code to try to improve the results and to do such things as more jump
3354 relax_delay_slots (rtx first
)
3356 rtx insn
, next
, pat
;
3357 rtx trial
, delay_insn
, target_label
;
3359 /* Look at every JUMP_INSN and see if we can improve it. */
3360 for (insn
= first
; insn
; insn
= next
)
3365 next
= next_active_insn (insn
);
3367 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3368 the next insn, or jumps to a label that is not the last of a
3369 group of consecutive labels. */
3371 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3372 && !ANY_RETURN_P (target_label
= JUMP_LABEL (insn
)))
3375 = skip_consecutive_labels (follow_jumps (target_label
, insn
,
3377 if (ANY_RETURN_P (target_label
))
3378 target_label
= find_end_label (target_label
);
3380 if (target_label
&& next_active_insn (target_label
) == next
3381 && ! condjump_in_parallel_p (insn
))
3387 if (target_label
&& target_label
!= JUMP_LABEL (insn
))
3389 reorg_redirect_jump (insn
, target_label
);
3391 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
3394 /* See if this jump conditionally branches around an unconditional
3395 jump. If so, invert this jump and point it to the target of the
3397 if (next
&& simplejump_or_return_p (next
)
3398 && any_condjump_p (insn
)
3400 && next_active_insn (target_label
) == next_active_insn (next
)
3401 && no_labels_between_p (insn
, next
))
3403 rtx label
= JUMP_LABEL (next
);
3405 /* Be careful how we do this to avoid deleting code or
3406 labels that are momentarily dead. See similar optimization
3409 We also need to ensure we properly handle the case when
3410 invert_jump fails. */
3412 ++LABEL_NUSES (target_label
);
3413 if (!ANY_RETURN_P (label
))
3414 ++LABEL_NUSES (label
);
3416 if (invert_jump (insn
, label
, 1))
3418 delete_related_insns (next
);
3422 if (!ANY_RETURN_P (label
))
3423 --LABEL_NUSES (label
);
3425 if (--LABEL_NUSES (target_label
) == 0)
3426 delete_related_insns (target_label
);
3432 /* If this is an unconditional jump and the previous insn is a
3433 conditional jump, try reversing the condition of the previous
3434 insn and swapping our targets. The next pass might be able to
3437 Don't do this if we expect the conditional branch to be true, because
3438 we would then be making the more common case longer. */
3440 if (simplejump_or_return_p (insn
)
3441 && (other
= prev_active_insn (insn
)) != 0
3442 && any_condjump_p (other
)
3443 && no_labels_between_p (other
, insn
)
3444 && 0 > mostly_true_jump (other
,
3445 get_branch_condition (other
,
3446 JUMP_LABEL (other
))))
3448 rtx other_target
= JUMP_LABEL (other
);
3449 target_label
= JUMP_LABEL (insn
);
3451 if (invert_jump (other
, target_label
, 0))
3452 reorg_redirect_jump (insn
, other_target
);
3455 /* Now look only at cases where we have a filled delay slot. */
3456 if (!NONJUMP_INSN_P (insn
) || GET_CODE (PATTERN (insn
)) != SEQUENCE
)
3459 pat
= PATTERN (insn
);
3460 delay_insn
= XVECEXP (pat
, 0, 0);
3462 /* See if the first insn in the delay slot is redundant with some
3463 previous insn. Remove it from the delay slot if so; then set up
3464 to reprocess this insn. */
3465 if (redundant_insn (XVECEXP (pat
, 0, 1), delay_insn
, 0))
3467 delete_from_delay_slot (XVECEXP (pat
, 0, 1));
3468 next
= prev_active_insn (next
);
3472 /* See if we have a RETURN insn with a filled delay slot followed
3473 by a RETURN insn with an unfilled a delay slot. If so, we can delete
3474 the first RETURN (but not its delay insn). This gives the same
3475 effect in fewer instructions.
3477 Only do so if optimizing for size since this results in slower, but
3479 if (optimize_function_for_size_p (cfun
)
3480 && ANY_RETURN_P (PATTERN (delay_insn
))
3483 && PATTERN (next
) == PATTERN (delay_insn
))
3488 /* Delete the RETURN and just execute the delay list insns.
3490 We do this by deleting the INSN containing the SEQUENCE, then
3491 re-emitting the insns separately, and then deleting the RETURN.
3492 This allows the count of the jump target to be properly
3495 Note that we need to change the INSN_UID of the re-emitted insns
3496 since it is used to hash the insns for mark_target_live_regs and
3497 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3499 Clear the from target bit, since these insns are no longer
3501 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3502 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3504 trial
= PREV_INSN (insn
);
3505 delete_related_insns (insn
);
3506 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3507 add_insn_after (delay_insn
, trial
, NULL
);
3509 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3510 after
= emit_copy_of_insn_after (XVECEXP (pat
, 0, i
), after
);
3511 delete_scheduled_jump (delay_insn
);
3515 /* Now look only at the cases where we have a filled JUMP_INSN. */
3516 if (!JUMP_P (delay_insn
)
3517 || !(condjump_p (delay_insn
) || condjump_in_parallel_p (delay_insn
)))
3520 target_label
= JUMP_LABEL (delay_insn
);
3521 if (target_label
&& ANY_RETURN_P (target_label
))
3524 /* If this jump goes to another unconditional jump, thread it, but
3525 don't convert a jump into a RETURN here. */
3526 trial
= skip_consecutive_labels (follow_jumps (target_label
, delay_insn
,
3528 if (ANY_RETURN_P (trial
))
3529 trial
= find_end_label (trial
);
3531 if (trial
&& trial
!= target_label
3532 && redirect_with_delay_slots_safe_p (delay_insn
, trial
, insn
))
3534 reorg_redirect_jump (delay_insn
, trial
);
3535 target_label
= trial
;
3537 set_unique_reg_note (insn
, REG_CROSSING_JUMP
, NULL_RTX
);
3540 /* If the first insn at TARGET_LABEL is redundant with a previous
3541 insn, redirect the jump to the following insn and process again.
3542 We use next_real_insn instead of next_active_insn so we
3543 don't skip USE-markers, or we'll end up with incorrect
3545 trial
= next_real_insn (target_label
);
3546 if (trial
&& GET_CODE (PATTERN (trial
)) != SEQUENCE
3547 && redundant_insn (trial
, insn
, 0)
3548 && ! can_throw_internal (trial
))
3550 /* Figure out where to emit the special USE insn so we don't
3551 later incorrectly compute register live/death info. */
3552 rtx tmp
= next_active_insn (trial
);
3554 tmp
= find_end_label (simple_return_rtx
);
3558 /* Insert the special USE insn and update dataflow info. */
3559 update_block (trial
, tmp
);
3561 /* Now emit a label before the special USE insn, and
3562 redirect our jump to the new label. */
3563 target_label
= get_label_before (PREV_INSN (tmp
));
3564 reorg_redirect_jump (delay_insn
, target_label
);
3570 /* Similarly, if it is an unconditional jump with one insn in its
3571 delay list and that insn is redundant, thread the jump. */
3572 if (trial
&& GET_CODE (PATTERN (trial
)) == SEQUENCE
3573 && XVECLEN (PATTERN (trial
), 0) == 2
3574 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
3575 && simplejump_or_return_p (XVECEXP (PATTERN (trial
), 0, 0))
3576 && redundant_insn (XVECEXP (PATTERN (trial
), 0, 1), insn
, 0))
3578 target_label
= JUMP_LABEL (XVECEXP (PATTERN (trial
), 0, 0));
3579 if (ANY_RETURN_P (target_label
))
3580 target_label
= find_end_label (target_label
);
3583 && redirect_with_delay_slots_safe_p (delay_insn
, target_label
,
3586 reorg_redirect_jump (delay_insn
, target_label
);
3592 /* See if we have a simple (conditional) jump that is useless. */
3593 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3594 && ! condjump_in_parallel_p (delay_insn
)
3595 && prev_active_insn (target_label
) == insn
3596 && ! BARRIER_P (prev_nonnote_insn (target_label
))
3598 /* If the last insn in the delay slot sets CC0 for some insn,
3599 various code assumes that it is in a delay slot. We could
3600 put it back where it belonged and delete the register notes,
3601 but it doesn't seem worthwhile in this uncommon case. */
3602 && ! find_reg_note (XVECEXP (pat
, 0, XVECLEN (pat
, 0) - 1),
3603 REG_CC_USER
, NULL_RTX
)
3610 /* All this insn does is execute its delay list and jump to the
3611 following insn. So delete the jump and just execute the delay
3614 We do this by deleting the INSN containing the SEQUENCE, then
3615 re-emitting the insns separately, and then deleting the jump.
3616 This allows the count of the jump target to be properly
3619 Note that we need to change the INSN_UID of the re-emitted insns
3620 since it is used to hash the insns for mark_target_live_regs and
3621 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3623 Clear the from target bit, since these insns are no longer
3625 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3626 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3628 trial
= PREV_INSN (insn
);
3629 delete_related_insns (insn
);
3630 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3631 add_insn_after (delay_insn
, trial
, NULL
);
3633 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3634 after
= emit_copy_of_insn_after (XVECEXP (pat
, 0, i
), after
);
3635 delete_scheduled_jump (delay_insn
);
3639 /* See if this is an unconditional jump around a single insn which is
3640 identical to the one in its delay slot. In this case, we can just
3641 delete the branch and the insn in its delay slot. */
3642 if (next
&& NONJUMP_INSN_P (next
)
3643 && label_before_next_insn (next
, insn
) == target_label
3644 && simplejump_p (insn
)
3645 && XVECLEN (pat
, 0) == 2
3646 && rtx_equal_p (PATTERN (next
), PATTERN (XVECEXP (pat
, 0, 1))))
3648 delete_related_insns (insn
);
3652 /* See if this jump (with its delay slots) conditionally branches
3653 around an unconditional jump (without delay slots). If so, invert
3654 this jump and point it to the target of the second jump. We cannot
3655 do this for annulled jumps, though. Again, don't convert a jump to
3657 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3658 && any_condjump_p (delay_insn
)
3659 && next
&& simplejump_or_return_p (next
)
3660 && next_active_insn (target_label
) == next_active_insn (next
)
3661 && no_labels_between_p (insn
, next
))
3663 rtx label
= JUMP_LABEL (next
);
3664 rtx old_label
= JUMP_LABEL (delay_insn
);
3666 if (ANY_RETURN_P (label
))
3667 label
= find_end_label (label
);
3669 /* find_end_label can generate a new label. Check this first. */
3671 && no_labels_between_p (insn
, next
)
3672 && redirect_with_delay_slots_safe_p (delay_insn
, label
, insn
))
3674 /* Be careful how we do this to avoid deleting code or labels
3675 that are momentarily dead. See similar optimization in
3678 ++LABEL_NUSES (old_label
);
3680 if (invert_jump (delay_insn
, label
, 1))
3684 /* Must update the INSN_FROM_TARGET_P bits now that
3685 the branch is reversed, so that mark_target_live_regs
3686 will handle the delay slot insn correctly. */
3687 for (i
= 1; i
< XVECLEN (PATTERN (insn
), 0); i
++)
3689 rtx slot
= XVECEXP (PATTERN (insn
), 0, i
);
3690 INSN_FROM_TARGET_P (slot
) = ! INSN_FROM_TARGET_P (slot
);
3693 delete_related_insns (next
);
3697 if (old_label
&& --LABEL_NUSES (old_label
) == 0)
3698 delete_related_insns (old_label
);
3703 /* If we own the thread opposite the way this insn branches, see if we
3704 can merge its delay slots with following insns. */
3705 if (INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3706 && own_thread_p (NEXT_INSN (insn
), 0, 1))
3707 try_merge_delay_insns (insn
, next
);
3708 else if (! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, 1))
3709 && own_thread_p (target_label
, target_label
, 0))
3710 try_merge_delay_insns (insn
, next_active_insn (target_label
));
3712 /* If we get here, we haven't deleted INSN. But we may have deleted
3713 NEXT, so recompute it. */
3714 next
= next_active_insn (insn
);
3719 /* Look for filled jumps to the end of function label. We can try to convert
3720 them into RETURN insns if the insns in the delay slot are valid for the
3724 make_return_insns (rtx first
)
3726 rtx insn
, jump_insn
, pat
;
3727 rtx real_return_label
= function_return_label
;
3728 rtx real_simple_return_label
= function_simple_return_label
;
3731 #ifdef DELAY_SLOTS_FOR_EPILOGUE
3732 /* If a previous pass filled delay slots in the epilogue, things get a
3733 bit more complicated, as those filler insns would generally (without
3734 data flow analysis) have to be executed after any existing branch
3735 delay slot filler insns. It is also unknown whether such a
3736 transformation would actually be profitable. Note that the existing
3737 code only cares for branches with (some) filled delay slots. */
3738 if (crtl
->epilogue_delay_list
!= NULL
)
3742 /* See if there is a RETURN insn in the function other than the one we
3743 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3744 into a RETURN to jump to it. */
3745 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3746 if (JUMP_P (insn
) && ANY_RETURN_P (PATTERN (insn
)))
3748 rtx t
= get_label_before (insn
);
3749 if (PATTERN (insn
) == ret_rtx
)
3750 real_return_label
= t
;
3752 real_simple_return_label
= t
;
3756 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3757 was equal to END_OF_FUNCTION_LABEL. */
3758 if (real_return_label
)
3759 LABEL_NUSES (real_return_label
)++;
3760 if (real_simple_return_label
)
3761 LABEL_NUSES (real_simple_return_label
)++;
3763 /* Clear the list of insns to fill so we can use it. */
3764 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3766 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3769 rtx kind
, real_label
;
3771 /* Only look at filled JUMP_INSNs that go to the end of function
3773 if (!NONJUMP_INSN_P (insn
)
3774 || GET_CODE (PATTERN (insn
)) != SEQUENCE
3775 || !jump_to_label_p (XVECEXP (PATTERN (insn
), 0, 0)))
3778 if (JUMP_LABEL (XVECEXP (PATTERN (insn
), 0, 0)) == function_return_label
)
3781 real_label
= real_return_label
;
3783 else if (JUMP_LABEL (XVECEXP (PATTERN (insn
), 0, 0))
3784 == function_simple_return_label
)
3786 kind
= simple_return_rtx
;
3787 real_label
= real_simple_return_label
;
3792 pat
= PATTERN (insn
);
3793 jump_insn
= XVECEXP (pat
, 0, 0);
3795 /* If we can't make the jump into a RETURN, try to redirect it to the best
3796 RETURN and go on to the next insn. */
3797 if (!reorg_redirect_jump (jump_insn
, kind
))
3799 /* Make sure redirecting the jump will not invalidate the delay
3801 if (redirect_with_delay_slots_safe_p (jump_insn
, real_label
, insn
))
3802 reorg_redirect_jump (jump_insn
, real_label
);
3806 /* See if this RETURN can accept the insns current in its delay slot.
3807 It can if it has more or an equal number of slots and the contents
3808 of each is valid. */
3810 flags
= get_jump_flags (jump_insn
, JUMP_LABEL (jump_insn
));
3811 slots
= num_delay_slots (jump_insn
);
3812 if (slots
>= XVECLEN (pat
, 0) - 1)
3814 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3816 #ifdef ANNUL_IFFALSE_SLOTS
3817 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3818 && INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3819 ? eligible_for_annul_false (jump_insn
, i
- 1,
3820 XVECEXP (pat
, 0, i
), flags
) :
3822 #ifdef ANNUL_IFTRUE_SLOTS
3823 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3824 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
3825 ? eligible_for_annul_true (jump_insn
, i
- 1,
3826 XVECEXP (pat
, 0, i
), flags
) :
3828 eligible_for_delay (jump_insn
, i
- 1,
3829 XVECEXP (pat
, 0, i
), flags
)))
3835 if (i
== XVECLEN (pat
, 0))
3838 /* We have to do something with this insn. If it is an unconditional
3839 RETURN, delete the SEQUENCE and output the individual insns,
3840 followed by the RETURN. Then set things up so we try to find
3841 insns for its delay slots, if it needs some. */
3842 if (ANY_RETURN_P (PATTERN (jump_insn
)))
3844 rtx prev
= PREV_INSN (insn
);
3846 delete_related_insns (insn
);
3847 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3848 prev
= emit_insn_after (PATTERN (XVECEXP (pat
, 0, i
)), prev
);
3850 insn
= emit_jump_insn_after (PATTERN (jump_insn
), prev
);
3851 emit_barrier_after (insn
);
3854 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3857 /* It is probably more efficient to keep this with its current
3858 delay slot as a branch to a RETURN. */
3859 reorg_redirect_jump (jump_insn
, real_label
);
3862 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3863 new delay slots we have created. */
3864 if (real_return_label
!= NULL_RTX
&& --LABEL_NUSES (real_return_label
) == 0)
3865 delete_related_insns (real_return_label
);
3866 if (real_simple_return_label
!= NULL_RTX
3867 && --LABEL_NUSES (real_simple_return_label
) == 0)
3868 delete_related_insns (real_simple_return_label
);
3870 fill_simple_delay_slots (1);
3871 fill_simple_delay_slots (0);
3874 /* Try to find insns to place in delay slots. */
3877 dbr_schedule (rtx first
)
3879 rtx insn
, next
, epilogue_insn
= 0;
3881 bool need_return_insns
;
3883 /* If the current function has no insns other than the prologue and
3884 epilogue, then do not try to fill any delay slots. */
3885 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
3888 /* Find the highest INSN_UID and allocate and initialize our map from
3889 INSN_UID's to position in code. */
3890 for (max_uid
= 0, insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3892 if (INSN_UID (insn
) > max_uid
)
3893 max_uid
= INSN_UID (insn
);
3895 && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3896 epilogue_insn
= insn
;
3899 uid_to_ruid
= XNEWVEC (int, max_uid
+ 1);
3900 for (i
= 0, insn
= first
; insn
; i
++, insn
= NEXT_INSN (insn
))
3901 uid_to_ruid
[INSN_UID (insn
)] = i
;
3903 /* Initialize the list of insns that need filling. */
3904 if (unfilled_firstobj
== 0)
3906 gcc_obstack_init (&unfilled_slots_obstack
);
3907 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3910 for (insn
= next_active_insn (first
); insn
; insn
= next_active_insn (insn
))
3915 INSN_ANNULLED_BRANCH_P (insn
) = 0;
3916 INSN_FROM_TARGET_P (insn
) = 0;
3918 /* Skip vector tables. We can't get attributes for them. */
3919 if (JUMP_TABLE_DATA_P (insn
))
3922 if (num_delay_slots (insn
) > 0)
3923 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3925 /* Ensure all jumps go to the last of a set of consecutive labels. */
3927 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3928 && !ANY_RETURN_P (JUMP_LABEL (insn
))
3929 && ((target
= skip_consecutive_labels (JUMP_LABEL (insn
)))
3930 != JUMP_LABEL (insn
)))
3931 redirect_jump (insn
, target
, 1);
3934 init_resource_info (epilogue_insn
);
3936 /* Show we haven't computed an end-of-function label yet. */
3937 function_return_label
= function_simple_return_label
= NULL_RTX
;
3939 /* Initialize the statistics for this function. */
3940 memset (num_insns_needing_delays
, 0, sizeof num_insns_needing_delays
);
3941 memset (num_filled_delays
, 0, sizeof num_filled_delays
);
3943 /* Now do the delay slot filling. Try everything twice in case earlier
3944 changes make more slots fillable. */
3946 for (reorg_pass_number
= 0;
3947 reorg_pass_number
< MAX_REORG_PASSES
;
3948 reorg_pass_number
++)
3950 fill_simple_delay_slots (1);
3951 fill_simple_delay_slots (0);
3952 fill_eager_delay_slots ();
3953 relax_delay_slots (first
);
3956 /* If we made an end of function label, indicate that it is now
3957 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3958 If it is now unused, delete it. */
3959 if (function_return_label
&& --LABEL_NUSES (function_return_label
) == 0)
3960 delete_related_insns (function_return_label
);
3961 if (function_simple_return_label
3962 && --LABEL_NUSES (function_simple_return_label
) == 0)
3963 delete_related_insns (function_simple_return_label
);
3965 need_return_insns
= false;
3967 need_return_insns
|= HAVE_return
&& function_return_label
!= 0;
3969 #ifdef HAVE_simple_return
3970 need_return_insns
|= HAVE_simple_return
&& function_simple_return_label
!= 0;
3972 if (need_return_insns
)
3973 make_return_insns (first
);
3975 /* Delete any USE insns made by update_block; subsequent passes don't need
3976 them or know how to deal with them. */
3977 for (insn
= first
; insn
; insn
= next
)
3979 next
= NEXT_INSN (insn
);
3981 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == USE
3982 && INSN_P (XEXP (PATTERN (insn
), 0)))
3983 next
= delete_related_insns (insn
);
3986 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3988 /* It is not clear why the line below is needed, but it does seem to be. */
3989 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3993 int i
, j
, need_comma
;
3994 int total_delay_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3995 int total_annul_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3997 for (reorg_pass_number
= 0;
3998 reorg_pass_number
< MAX_REORG_PASSES
;
3999 reorg_pass_number
++)
4001 fprintf (dump_file
, ";; Reorg pass #%d:\n", reorg_pass_number
+ 1);
4002 for (i
= 0; i
< NUM_REORG_FUNCTIONS
; i
++)
4005 fprintf (dump_file
, ";; Reorg function #%d\n", i
);
4007 fprintf (dump_file
, ";; %d insns needing delay slots\n;; ",
4008 num_insns_needing_delays
[i
][reorg_pass_number
]);
4010 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
4011 if (num_filled_delays
[i
][j
][reorg_pass_number
])
4014 fprintf (dump_file
, ", ");
4016 fprintf (dump_file
, "%d got %d delays",
4017 num_filled_delays
[i
][j
][reorg_pass_number
], j
);
4019 fprintf (dump_file
, "\n");
4022 memset (total_delay_slots
, 0, sizeof total_delay_slots
);
4023 memset (total_annul_slots
, 0, sizeof total_annul_slots
);
4024 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
4026 if (! INSN_DELETED_P (insn
)
4027 && NONJUMP_INSN_P (insn
)
4028 && GET_CODE (PATTERN (insn
)) != USE
4029 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
4031 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
4034 j
= XVECLEN (PATTERN (insn
), 0) - 1;
4035 if (j
> MAX_DELAY_HISTOGRAM
)
4036 j
= MAX_DELAY_HISTOGRAM
;
4037 control
= XVECEXP (PATTERN (insn
), 0, 0);
4038 if (JUMP_P (control
) && INSN_ANNULLED_BRANCH_P (control
))
4039 total_annul_slots
[j
]++;
4041 total_delay_slots
[j
]++;
4043 else if (num_delay_slots (insn
) > 0)
4044 total_delay_slots
[0]++;
4047 fprintf (dump_file
, ";; Reorg totals: ");
4049 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
4051 if (total_delay_slots
[j
])
4054 fprintf (dump_file
, ", ");
4056 fprintf (dump_file
, "%d got %d delays", total_delay_slots
[j
], j
);
4059 fprintf (dump_file
, "\n");
4060 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
4061 fprintf (dump_file
, ";; Reorg annuls: ");
4063 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
4065 if (total_annul_slots
[j
])
4068 fprintf (dump_file
, ", ");
4070 fprintf (dump_file
, "%d got %d delays", total_annul_slots
[j
], j
);
4073 fprintf (dump_file
, "\n");
4075 fprintf (dump_file
, "\n");
4078 free_resource_info ();
4080 #ifdef DELAY_SLOTS_FOR_EPILOGUE
4081 /* SPARC assembler, for instance, emit warning when debug info is output
4082 into the delay slot. */
4086 for (link
= crtl
->epilogue_delay_list
;
4088 link
= XEXP (link
, 1))
4089 INSN_LOCATION (XEXP (link
, 0)) = 0;
4093 crtl
->dbr_scheduled_p
= true;
4095 #endif /* DELAY_SLOTS */
4098 gate_handle_delay_slots (void)
4101 /* At -O0 dataflow info isn't updated after RA. */
4102 return optimize
> 0 && flag_delayed_branch
&& !crtl
->dbr_scheduled_p
;
4108 /* Run delay slot optimization. */
4110 rest_of_handle_delay_slots (void)
4113 dbr_schedule (get_insns ());
4118 struct rtl_opt_pass pass_delay_slots
=
4123 gate_handle_delay_slots
, /* gate */
4124 rest_of_handle_delay_slots
, /* execute */
4127 0, /* static_pass_number */
4128 TV_DBR_SCHED
, /* tv_id */
4129 0, /* properties_required */
4130 0, /* properties_provided */
4131 0, /* properties_destroyed */
4132 0, /* todo_flags_start */
4133 TODO_ggc_collect
/* todo_flags_finish */
4137 /* Machine dependent reorg pass. */
4139 gate_handle_machine_reorg (void)
4141 return targetm
.machine_dependent_reorg
!= 0;
4146 rest_of_handle_machine_reorg (void)
4148 targetm
.machine_dependent_reorg ();
4152 struct rtl_opt_pass pass_machine_reorg
=
4157 gate_handle_machine_reorg
, /* gate */
4158 rest_of_handle_machine_reorg
, /* execute */
4161 0, /* static_pass_number */
4162 TV_MACH_DEP
, /* tv_id */
4163 0, /* properties_required */
4164 0, /* properties_provided */
4165 0, /* properties_destroyed */
4166 0, /* todo_flags_start */
4167 TODO_ggc_collect
/* todo_flags_finish */