1 /* Perform instruction reorganizations for delay slot filling.
2 Copyright (C) 1992-2015 Free Software Foundation, Inc.
3 Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
4 Hacked by Michael Tiemann (tiemann@cygnus.com).
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Instruction reorganization pass.
24 This pass runs after register allocation and final jump
25 optimization. It should be the last pass to run before peephole.
26 It serves primarily to fill delay slots of insns, typically branch
27 and call insns. Other insns typically involve more complicated
28 interactions of data dependencies and resource constraints, and
29 are better handled by scheduling before register allocation (by the
30 function `schedule_insns').
32 The Branch Penalty is the number of extra cycles that are needed to
33 execute a branch insn. On an ideal machine, branches take a single
34 cycle, and the Branch Penalty is 0. Several RISC machines approach
35 branch delays differently:
37 The MIPS has a single branch delay slot. Most insns
38 (except other branches) can be used to fill this slot. When the
39 slot is filled, two insns execute in two cycles, reducing the
40 branch penalty to zero.
42 The SPARC always has a branch delay slot, but its effects can be
43 annulled when the branch is not taken. This means that failing to
44 find other sources of insns, we can hoist an insn from the branch
45 target that would only be safe to execute knowing that the branch
48 The HP-PA always has a branch delay slot. For unconditional branches
49 its effects can be annulled when the branch is taken. The effects
50 of the delay slot in a conditional branch can be nullified for forward
51 taken branches, or for untaken backward branches. This means
52 we can hoist insns from the fall-through path for forward branches or
53 steal insns from the target of backward branches.
55 The TMS320C3x and C4x have three branch delay slots. When the three
56 slots are filled, the branch penalty is zero. Most insns can fill the
57 delay slots except jump insns.
59 Three techniques for filling delay slots have been implemented so far:
61 (1) `fill_simple_delay_slots' is the simplest, most efficient way
62 to fill delay slots. This pass first looks for insns which come
63 from before the branch and which are safe to execute after the
64 branch. Then it searches after the insn requiring delay slots or,
65 in the case of a branch, for insns that are after the point at
66 which the branch merges into the fallthrough code, if such a point
67 exists. When such insns are found, the branch penalty decreases
68 and no code expansion takes place.
70 (2) `fill_eager_delay_slots' is more complicated: it is used for
71 scheduling conditional jumps, or for scheduling jumps which cannot
72 be filled using (1). A machine need not have annulled jumps to use
73 this strategy, but it helps (by keeping more options open).
74 `fill_eager_delay_slots' tries to guess the direction the branch
75 will go; if it guesses right 100% of the time, it can reduce the
76 branch penalty as much as `fill_simple_delay_slots' does. If it
77 guesses wrong 100% of the time, it might as well schedule nops. When
78 `fill_eager_delay_slots' takes insns from the fall-through path of
79 the jump, usually there is no code expansion; when it takes insns
80 from the branch target, there is code expansion if it is not the
81 only way to reach that target.
83 (3) `relax_delay_slots' uses a set of rules to simplify code that
84 has been reorganized by (1) and (2). It finds cases where
85 conditional test can be eliminated, jumps can be threaded, extra
86 insns can be eliminated, etc. It is the job of (1) and (2) to do a
87 good job of scheduling locally; `relax_delay_slots' takes care of
88 making the various individual schedules work well together. It is
89 especially tuned to handle the control flow interactions of branch
90 insns. It does nothing for insns with delay slots that do not
93 On machines that use CC0, we are very conservative. We will not make
94 a copy of an insn involving CC0 since we want to maintain a 1-1
95 correspondence between the insn that sets and uses CC0. The insns are
96 allowed to be separated by placing an insn that sets CC0 (but not an insn
97 that uses CC0; we could do this, but it doesn't seem worthwhile) in a
98 delay slot. In that case, we point each insn at the other with REG_CC_USER
99 and REG_CC_SETTER notes. Note that these restrictions affect very few
100 machines because most RISC machines with delay slots will not use CC0
101 (the RT is the only known exception at this point). */
105 #include "coretypes.h"
107 #include "diagnostic-core.h"
112 #include "hash-set.h"
114 #include "machmode.h"
115 #include "hard-reg-set.h"
117 #include "function.h"
119 #include "statistics.h"
120 #include "double-int.h"
122 #include "fixed-value.h"
124 #include "wide-int.h"
127 #include "insn-config.h"
132 #include "emit-rtl.h"
136 #include "conditions.h"
138 #include "dominance.h"
140 #include "basic-block.h"
144 #include "insn-attr.h"
145 #include "resource.h"
149 #include "tree-pass.h"
153 #ifndef ANNUL_IFTRUE_SLOTS
154 #define eligible_for_annul_true(INSN, SLOTS, TRIAL, FLAGS) 0
156 #ifndef ANNUL_IFFALSE_SLOTS
157 #define eligible_for_annul_false(INSN, SLOTS, TRIAL, FLAGS) 0
161 /* First, some functions that were used before GCC got a control flow graph.
162 These functions are now only used here in reorg.c, and have therefore
163 been moved here to avoid inadvertent misuse elsewhere in the compiler. */
165 /* Return the last label to mark the same position as LABEL. Return LABEL
166 itself if it is null or any return rtx. */
169 skip_consecutive_labels (rtx label_or_return
)
173 if (label_or_return
&& ANY_RETURN_P (label_or_return
))
174 return label_or_return
;
176 rtx_insn
*label
= as_a
<rtx_insn
*> (label_or_return
);
178 for (insn
= label
; insn
!= 0 && !INSN_P (insn
); insn
= NEXT_INSN (insn
))
185 /* INSN uses CC0 and is being moved into a delay slot. Set up REG_CC_SETTER
186 and REG_CC_USER notes so we can find it. */
189 link_cc0_insns (rtx insn
)
191 rtx user
= next_nonnote_insn (insn
);
193 if (NONJUMP_INSN_P (user
) && GET_CODE (PATTERN (user
)) == SEQUENCE
)
194 user
= XVECEXP (PATTERN (user
), 0, 0);
196 add_reg_note (user
, REG_CC_SETTER
, insn
);
197 add_reg_note (insn
, REG_CC_USER
, user
);
200 /* Insns which have delay slots that have not yet been filled. */
202 static struct obstack unfilled_slots_obstack
;
203 static rtx
*unfilled_firstobj
;
205 /* Define macros to refer to the first and last slot containing unfilled
206 insns. These are used because the list may move and its address
207 should be recomputed at each use. */
209 #define unfilled_slots_base \
210 ((rtx_insn **) obstack_base (&unfilled_slots_obstack))
212 #define unfilled_slots_next \
213 ((rtx_insn **) obstack_next_free (&unfilled_slots_obstack))
215 /* Points to the label before the end of the function, or before a
217 static rtx_code_label
*function_return_label
;
218 /* Likewise for a simple_return. */
219 static rtx_code_label
*function_simple_return_label
;
221 /* Mapping between INSN_UID's and position in the code since INSN_UID's do
222 not always monotonically increase. */
223 static int *uid_to_ruid
;
225 /* Highest valid index in `uid_to_ruid'. */
228 static int stop_search_p (rtx
, int);
229 static int resource_conflicts_p (struct resources
*, struct resources
*);
230 static int insn_references_resource_p (rtx
, struct resources
*, bool);
231 static int insn_sets_resource_p (rtx
, struct resources
*, bool);
232 static rtx_code_label
*find_end_label (rtx
);
233 static rtx_insn
*emit_delay_sequence (rtx_insn
*, rtx_insn_list
*, int);
234 static rtx_insn_list
*add_to_delay_list (rtx_insn
*, rtx_insn_list
*);
235 static rtx_insn
*delete_from_delay_slot (rtx_insn
*);
236 static void delete_scheduled_jump (rtx_insn
*);
237 static void note_delay_statistics (int, int);
238 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
239 static rtx_insn_list
*optimize_skip (rtx_insn
*);
241 static int get_jump_flags (const rtx_insn
*, rtx
);
242 static int mostly_true_jump (rtx
);
243 static rtx
get_branch_condition (const rtx_insn
*, rtx
);
244 static int condition_dominates_p (rtx
, const rtx_insn
*);
245 static int redirect_with_delay_slots_safe_p (rtx_insn
*, rtx
, rtx
);
246 static int redirect_with_delay_list_safe_p (rtx_insn
*, rtx
, rtx_insn_list
*);
247 static int check_annul_list_true_false (int, rtx
);
248 static rtx_insn_list
*steal_delay_list_from_target (rtx_insn
*, rtx
,
256 static rtx_insn_list
*steal_delay_list_from_fallthrough (rtx_insn
*, rtx
,
263 static void try_merge_delay_insns (rtx
, rtx_insn
*);
264 static rtx
redundant_insn (rtx
, rtx_insn
*, rtx
);
265 static int own_thread_p (rtx
, rtx
, int);
266 static void update_block (rtx_insn
*, rtx
);
267 static int reorg_redirect_jump (rtx_insn
*, rtx
);
268 static void update_reg_dead_notes (rtx
, rtx
);
269 static void fix_reg_dead_note (rtx
, rtx
);
270 static void update_reg_unused_notes (rtx
, rtx
);
271 static void fill_simple_delay_slots (int);
272 static rtx_insn_list
*fill_slots_from_thread (rtx_insn
*, rtx
, rtx
, rtx
,
274 int *, rtx_insn_list
*);
275 static void fill_eager_delay_slots (void);
276 static void relax_delay_slots (rtx_insn
*);
277 static void make_return_insns (rtx_insn
*);
279 /* A wrapper around next_active_insn which takes care to return ret_rtx
283 first_active_target_insn (rtx insn
)
285 if (ANY_RETURN_P (insn
))
287 return next_active_insn (as_a
<rtx_insn
*> (insn
));
290 /* Return true iff INSN is a simplejump, or any kind of return insn. */
293 simplejump_or_return_p (rtx insn
)
295 return (JUMP_P (insn
)
296 && (simplejump_p (as_a
<rtx_insn
*> (insn
))
297 || ANY_RETURN_P (PATTERN (insn
))));
300 /* Return TRUE if this insn should stop the search for insn to fill delay
301 slots. LABELS_P indicates that labels should terminate the search.
302 In all cases, jumps terminate the search. */
305 stop_search_p (rtx insn
, int labels_p
)
310 /* If the insn can throw an exception that is caught within the function,
311 it may effectively perform a jump from the viewpoint of the function.
312 Therefore act like for a jump. */
313 if (can_throw_internal (insn
))
316 switch (GET_CODE (insn
))
330 /* OK unless it contains a delay slot or is an `asm' insn of some type.
331 We don't know anything about these. */
332 return (GET_CODE (PATTERN (insn
)) == SEQUENCE
333 || GET_CODE (PATTERN (insn
)) == ASM_INPUT
334 || asm_noperands (PATTERN (insn
)) >= 0);
341 /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
342 resource set contains a volatile memory reference. Otherwise, return FALSE. */
345 resource_conflicts_p (struct resources
*res1
, struct resources
*res2
)
347 if ((res1
->cc
&& res2
->cc
) || (res1
->memory
&& res2
->memory
)
348 || res1
->volatil
|| res2
->volatil
)
351 return hard_reg_set_intersect_p (res1
->regs
, res2
->regs
);
354 /* Return TRUE if any resource marked in RES, a `struct resources', is
355 referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
356 routine is using those resources.
358 We compute this by computing all the resources referenced by INSN and
359 seeing if this conflicts with RES. It might be faster to directly check
360 ourselves, and this is the way it used to work, but it means duplicating
361 a large block of complex code. */
364 insn_references_resource_p (rtx insn
, struct resources
*res
,
365 bool include_delayed_effects
)
367 struct resources insn_res
;
369 CLEAR_RESOURCE (&insn_res
);
370 mark_referenced_resources (insn
, &insn_res
, include_delayed_effects
);
371 return resource_conflicts_p (&insn_res
, res
);
374 /* Return TRUE if INSN modifies resources that are marked in RES.
375 INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
376 included. CC0 is only modified if it is explicitly set; see comments
377 in front of mark_set_resources for details. */
380 insn_sets_resource_p (rtx insn
, struct resources
*res
,
381 bool include_delayed_effects
)
383 struct resources insn_sets
;
385 CLEAR_RESOURCE (&insn_sets
);
386 mark_set_resources (insn
, &insn_sets
, 0,
387 (include_delayed_effects
390 return resource_conflicts_p (&insn_sets
, res
);
393 /* Find a label at the end of the function or before a RETURN. If there
394 is none, try to make one. If that fails, returns 0.
396 The property of such a label is that it is placed just before the
397 epilogue or a bare RETURN insn, so that another bare RETURN can be
398 turned into a jump to the label unconditionally. In particular, the
399 label cannot be placed before a RETURN insn with a filled delay slot.
401 ??? There may be a problem with the current implementation. Suppose
402 we start with a bare RETURN insn and call find_end_label. It may set
403 function_return_label just before the RETURN. Suppose the machinery
404 is able to fill the delay slot of the RETURN insn afterwards. Then
405 function_return_label is no longer valid according to the property
406 described above and find_end_label will still return it unmodified.
407 Note that this is probably mitigated by the following observation:
408 once function_return_label is made, it is very likely the target of
409 a jump, so filling the delay slot of the RETURN will be much more
411 KIND is either simple_return_rtx or ret_rtx, indicating which type of
412 return we're looking for. */
414 static rtx_code_label
*
415 find_end_label (rtx kind
)
418 rtx_code_label
**plabel
;
421 plabel
= &function_return_label
;
424 gcc_assert (kind
== simple_return_rtx
);
425 plabel
= &function_simple_return_label
;
428 /* If we found one previously, return it. */
432 /* Otherwise, see if there is a label at the end of the function. If there
433 is, it must be that RETURN insns aren't needed, so that is our return
434 label and we don't have to do anything else. */
436 insn
= get_last_insn ();
438 || (NONJUMP_INSN_P (insn
)
439 && (GET_CODE (PATTERN (insn
)) == USE
440 || GET_CODE (PATTERN (insn
)) == CLOBBER
)))
441 insn
= PREV_INSN (insn
);
443 /* When a target threads its epilogue we might already have a
444 suitable return insn. If so put a label before it for the
445 function_return_label. */
447 && JUMP_P (PREV_INSN (insn
))
448 && PATTERN (PREV_INSN (insn
)) == kind
)
450 rtx_insn
*temp
= PREV_INSN (PREV_INSN (insn
));
451 rtx_code_label
*label
= gen_label_rtx ();
452 LABEL_NUSES (label
) = 0;
454 /* Put the label before any USE insns that may precede the RETURN
456 while (GET_CODE (temp
) == USE
)
457 temp
= PREV_INSN (temp
);
459 emit_label_after (label
, temp
);
463 else if (LABEL_P (insn
))
464 *plabel
= as_a
<rtx_code_label
*> (insn
);
467 rtx_code_label
*label
= gen_label_rtx ();
468 LABEL_NUSES (label
) = 0;
469 /* If the basic block reorder pass moves the return insn to
470 some other place try to locate it again and put our
471 function_return_label there. */
472 while (insn
&& ! (JUMP_P (insn
) && (PATTERN (insn
) == kind
)))
473 insn
= PREV_INSN (insn
);
476 insn
= PREV_INSN (insn
);
478 /* Put the label before any USE insns that may precede the
480 while (GET_CODE (insn
) == USE
)
481 insn
= PREV_INSN (insn
);
483 emit_label_after (label
, insn
);
493 /* The RETURN insn has its delay slot filled so we cannot
494 emit the label just before it. Since we already have
495 an epilogue and cannot emit a new RETURN, we cannot
496 emit the label at all. */
498 #endif /* HAVE_epilogue */
500 /* Otherwise, make a new label and emit a RETURN and BARRIER,
506 /* The return we make may have delay slots too. */
507 rtx pat
= gen_return ();
508 rtx_insn
*insn
= emit_jump_insn (pat
);
509 set_return_jump_label (insn
);
511 if (num_delay_slots (insn
) > 0)
512 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
519 /* Show one additional use for this label so it won't go away until
521 ++LABEL_NUSES (*plabel
);
526 /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
527 the pattern of INSN with the SEQUENCE.
529 Returns the insn containing the SEQUENCE that replaces INSN. */
532 emit_delay_sequence (rtx_insn
*insn
, rtx_insn_list
*list
, int length
)
534 /* Allocate the rtvec to hold the insns and the SEQUENCE. */
535 rtvec seqv
= rtvec_alloc (length
+ 1);
536 rtx seq
= gen_rtx_SEQUENCE (VOIDmode
, seqv
);
537 rtx_insn
*seq_insn
= make_insn_raw (seq
);
539 /* If DELAY_INSN has a location, use it for SEQ_INSN. If DELAY_INSN does
540 not have a location, but one of the delayed insns does, we pick up a
541 location from there later. */
542 INSN_LOCATION (seq_insn
) = INSN_LOCATION (insn
);
544 /* Unlink INSN from the insn chain, so that we can put it into
545 the SEQUENCE. Remember where we want to emit SEQUENCE in AFTER. */
546 rtx after
= PREV_INSN (insn
);
548 SET_NEXT_INSN (insn
) = SET_PREV_INSN (insn
) = NULL
;
550 /* Build our SEQUENCE and rebuild the insn chain. */
553 XVECEXP (seq
, 0, 0) = emit_insn (insn
);
554 for (rtx_insn_list
*li
= list
; li
; li
= li
->next (), i
++)
556 rtx_insn
*tem
= li
->insn ();
559 /* Show that this copy of the insn isn't deleted. */
560 tem
->set_undeleted ();
562 /* Unlink insn from its original place, and re-emit it into
564 SET_NEXT_INSN (tem
) = SET_PREV_INSN (tem
) = NULL
;
565 XVECEXP (seq
, 0, i
) = emit_insn (tem
);
567 /* SPARC assembler, for instance, emit warning when debug info is output
568 into the delay slot. */
569 if (INSN_LOCATION (tem
) && !INSN_LOCATION (seq_insn
))
570 INSN_LOCATION (seq_insn
) = INSN_LOCATION (tem
);
571 INSN_LOCATION (tem
) = 0;
573 for (note
= REG_NOTES (tem
); note
; note
= next
)
575 next
= XEXP (note
, 1);
576 switch (REG_NOTE_KIND (note
))
579 /* Remove any REG_DEAD notes because we can't rely on them now
580 that the insn has been moved. */
581 remove_note (tem
, note
);
584 case REG_LABEL_OPERAND
:
585 case REG_LABEL_TARGET
:
586 /* Keep the label reference count up to date. */
587 if (LABEL_P (XEXP (note
, 0)))
588 LABEL_NUSES (XEXP (note
, 0)) ++;
597 gcc_assert (i
== length
+ 1);
599 /* Splice our SEQUENCE into the insn stream where INSN used to be. */
600 add_insn_after (seq_insn
, after
, NULL
);
605 /* Add INSN to DELAY_LIST and return the head of the new list. The list must
606 be in the order in which the insns are to be executed. */
608 static rtx_insn_list
*
609 add_to_delay_list (rtx_insn
*insn
, rtx_insn_list
*delay_list
)
611 /* If we have an empty list, just make a new list element. If
612 INSN has its block number recorded, clear it since we may
613 be moving the insn to a new block. */
617 clear_hashed_info_for_insn (insn
);
618 return gen_rtx_INSN_LIST (VOIDmode
, insn
, NULL_RTX
);
621 /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
623 XEXP (delay_list
, 1) = add_to_delay_list (insn
, delay_list
->next ());
628 /* Delete INSN from the delay slot of the insn that it is in, which may
629 produce an insn with no delay slots. Return the new insn. */
632 delete_from_delay_slot (rtx_insn
*insn
)
634 rtx_insn
*trial
, *seq_insn
, *prev
;
636 rtx_insn_list
*delay_list
= 0;
640 /* We first must find the insn containing the SEQUENCE with INSN in its
641 delay slot. Do this by finding an insn, TRIAL, where
642 PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
645 PREV_INSN (NEXT_INSN (trial
)) == trial
;
646 trial
= NEXT_INSN (trial
))
649 seq_insn
= PREV_INSN (NEXT_INSN (trial
));
650 seq
= as_a
<rtx_sequence
*> (PATTERN (seq_insn
));
652 if (NEXT_INSN (seq_insn
) && BARRIER_P (NEXT_INSN (seq_insn
)))
655 /* Create a delay list consisting of all the insns other than the one
656 we are deleting (unless we were the only one). */
658 for (i
= 1; i
< seq
->len (); i
++)
659 if (seq
->insn (i
) != insn
)
660 delay_list
= add_to_delay_list (seq
->insn (i
), delay_list
);
662 /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
663 list, and rebuild the delay list if non-empty. */
664 prev
= PREV_INSN (seq_insn
);
665 trial
= seq
->insn (0);
666 delete_related_insns (seq_insn
);
667 add_insn_after (trial
, prev
, NULL
);
669 /* If there was a barrier after the old SEQUENCE, remit it. */
671 emit_barrier_after (trial
);
673 /* If there are any delay insns, remit them. Otherwise clear the
676 trial
= emit_delay_sequence (trial
, delay_list
, XVECLEN (seq
, 0) - 2);
677 else if (JUMP_P (trial
))
678 INSN_ANNULLED_BRANCH_P (trial
) = 0;
680 INSN_FROM_TARGET_P (insn
) = 0;
682 /* Show we need to fill this insn again. */
683 obstack_ptr_grow (&unfilled_slots_obstack
, trial
);
688 /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
689 the insn that sets CC0 for it and delete it too. */
692 delete_scheduled_jump (rtx_insn
*insn
)
694 /* Delete the insn that sets cc0 for us. On machines without cc0, we could
695 delete the insn that sets the condition code, but it is hard to find it.
696 Since this case is rare anyway, don't bother trying; there would likely
697 be other insns that became dead anyway, which we wouldn't know to
700 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, insn
))
702 rtx note
= find_reg_note (insn
, REG_CC_SETTER
, NULL_RTX
);
704 /* If a reg-note was found, it points to an insn to set CC0. This
705 insn is in the delay list of some other insn. So delete it from
706 the delay list it was in. */
709 if (! FIND_REG_INC_NOTE (XEXP (note
, 0), NULL_RTX
)
710 && sets_cc0_p (PATTERN (XEXP (note
, 0))) == 1)
711 delete_from_delay_slot (as_a
<rtx_insn
*> (XEXP (note
, 0)));
715 /* The insn setting CC0 is our previous insn, but it may be in
716 a delay slot. It will be the last insn in the delay slot, if
718 rtx_insn
*trial
= previous_insn (insn
);
720 trial
= prev_nonnote_insn (trial
);
721 if (sets_cc0_p (PATTERN (trial
)) != 1
722 || FIND_REG_INC_NOTE (trial
, NULL_RTX
))
724 if (PREV_INSN (NEXT_INSN (trial
)) == trial
)
725 delete_related_insns (trial
);
727 delete_from_delay_slot (trial
);
731 delete_related_insns (insn
);
734 /* Counters for delay-slot filling. */
736 #define NUM_REORG_FUNCTIONS 2
737 #define MAX_DELAY_HISTOGRAM 3
738 #define MAX_REORG_PASSES 2
740 static int num_insns_needing_delays
[NUM_REORG_FUNCTIONS
][MAX_REORG_PASSES
];
742 static int num_filled_delays
[NUM_REORG_FUNCTIONS
][MAX_DELAY_HISTOGRAM
+1][MAX_REORG_PASSES
];
744 static int reorg_pass_number
;
747 note_delay_statistics (int slots_filled
, int index
)
749 num_insns_needing_delays
[index
][reorg_pass_number
]++;
750 if (slots_filled
> MAX_DELAY_HISTOGRAM
)
751 slots_filled
= MAX_DELAY_HISTOGRAM
;
752 num_filled_delays
[index
][slots_filled
][reorg_pass_number
]++;
755 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
757 /* Optimize the following cases:
759 1. When a conditional branch skips over only one instruction,
760 use an annulling branch and put that insn in the delay slot.
761 Use either a branch that annuls when the condition if true or
762 invert the test with a branch that annuls when the condition is
763 false. This saves insns, since otherwise we must copy an insn
766 (orig) (skip) (otherwise)
767 Bcc.n L1 Bcc',a L1 Bcc,a L1'
774 2. When a conditional branch skips over only one instruction,
775 and after that, it unconditionally branches somewhere else,
776 perform the similar optimization. This saves executing the
777 second branch in the case where the inverted condition is true.
786 This should be expanded to skip over N insns, where N is the number
787 of delay slots required. */
789 static rtx_insn_list
*
790 optimize_skip (rtx_insn
*insn
)
792 rtx_insn
*trial
= next_nonnote_insn (insn
);
793 rtx_insn
*next_trial
= next_active_insn (trial
);
794 rtx_insn_list
*delay_list
= 0;
797 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
800 || !NONJUMP_INSN_P (trial
)
801 || GET_CODE (PATTERN (trial
)) == SEQUENCE
802 || recog_memoized (trial
) < 0
803 || (! eligible_for_annul_false (insn
, 0, trial
, flags
)
804 && ! eligible_for_annul_true (insn
, 0, trial
, flags
))
805 || can_throw_internal (trial
))
808 /* There are two cases where we are just executing one insn (we assume
809 here that a branch requires only one insn; this should be generalized
810 at some point): Where the branch goes around a single insn or where
811 we have one insn followed by a branch to the same label we branch to.
812 In both of these cases, inverting the jump and annulling the delay
813 slot give the same effect in fewer insns. */
814 if (next_trial
== next_active_insn (JUMP_LABEL (insn
))
816 && simplejump_or_return_p (next_trial
)
817 && JUMP_LABEL (insn
) == JUMP_LABEL (next_trial
)))
819 if (eligible_for_annul_false (insn
, 0, trial
, flags
))
821 if (invert_jump (insn
, JUMP_LABEL (insn
), 1))
822 INSN_FROM_TARGET_P (trial
) = 1;
823 else if (! eligible_for_annul_true (insn
, 0, trial
, flags
))
827 delay_list
= add_to_delay_list (trial
, NULL
);
828 next_trial
= next_active_insn (trial
);
829 update_block (trial
, trial
);
830 delete_related_insns (trial
);
832 /* Also, if we are targeting an unconditional
833 branch, thread our jump to the target of that branch. Don't
834 change this into a RETURN here, because it may not accept what
835 we have in the delay slot. We'll fix this up later. */
836 if (next_trial
&& simplejump_or_return_p (next_trial
))
838 rtx target_label
= JUMP_LABEL (next_trial
);
839 if (ANY_RETURN_P (target_label
))
840 target_label
= find_end_label (target_label
);
844 /* Recompute the flags based on TARGET_LABEL since threading
845 the jump to TARGET_LABEL may change the direction of the
846 jump (which may change the circumstances in which the
847 delay slot is nullified). */
848 flags
= get_jump_flags (insn
, target_label
);
849 if (eligible_for_annul_true (insn
, 0, trial
, flags
))
850 reorg_redirect_jump (insn
, target_label
);
854 INSN_ANNULLED_BRANCH_P (insn
) = 1;
861 /* Encode and return branch direction and prediction information for
862 INSN assuming it will jump to LABEL.
864 Non conditional branches return no direction information and
865 are predicted as very likely taken. */
868 get_jump_flags (const rtx_insn
*insn
, rtx label
)
872 /* get_jump_flags can be passed any insn with delay slots, these may
873 be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
874 direction information, and only if they are conditional jumps.
876 If LABEL is a return, then there is no way to determine the branch
879 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
880 && !ANY_RETURN_P (label
)
881 && INSN_UID (insn
) <= max_uid
882 && INSN_UID (label
) <= max_uid
)
884 = (uid_to_ruid
[INSN_UID (label
)] > uid_to_ruid
[INSN_UID (insn
)])
885 ? ATTR_FLAG_forward
: ATTR_FLAG_backward
;
886 /* No valid direction information. */
893 /* Return truth value of the statement that this branch
894 is mostly taken. If we think that the branch is extremely likely
895 to be taken, we return 2. If the branch is slightly more likely to be
896 taken, return 1. If the branch is slightly less likely to be taken,
897 return 0 and if the branch is highly unlikely to be taken, return -1. */
900 mostly_true_jump (rtx jump_insn
)
902 /* If branch probabilities are available, then use that number since it
903 always gives a correct answer. */
904 rtx note
= find_reg_note (jump_insn
, REG_BR_PROB
, 0);
907 int prob
= XINT (note
, 0);
909 if (prob
>= REG_BR_PROB_BASE
* 9 / 10)
911 else if (prob
>= REG_BR_PROB_BASE
/ 2)
913 else if (prob
>= REG_BR_PROB_BASE
/ 10)
919 /* If there is no note, assume branches are not taken.
920 This should be rare. */
924 /* Return the condition under which INSN will branch to TARGET. If TARGET
925 is zero, return the condition under which INSN will return. If INSN is
926 an unconditional branch, return const_true_rtx. If INSN isn't a simple
927 type of jump, or it doesn't go to TARGET, return 0. */
930 get_branch_condition (const rtx_insn
*insn
, rtx target
)
932 rtx pat
= PATTERN (insn
);
935 if (condjump_in_parallel_p (insn
))
936 pat
= XVECEXP (pat
, 0, 0);
938 if (ANY_RETURN_P (pat
) && pat
== target
)
939 return const_true_rtx
;
941 if (GET_CODE (pat
) != SET
|| SET_DEST (pat
) != pc_rtx
)
945 if (GET_CODE (src
) == LABEL_REF
&& LABEL_REF_LABEL (src
) == target
)
946 return const_true_rtx
;
948 else if (GET_CODE (src
) == IF_THEN_ELSE
949 && XEXP (src
, 2) == pc_rtx
950 && ((GET_CODE (XEXP (src
, 1)) == LABEL_REF
951 && LABEL_REF_LABEL (XEXP (src
, 1)) == target
)
952 || (ANY_RETURN_P (XEXP (src
, 1)) && XEXP (src
, 1) == target
)))
953 return XEXP (src
, 0);
955 else if (GET_CODE (src
) == IF_THEN_ELSE
956 && XEXP (src
, 1) == pc_rtx
957 && ((GET_CODE (XEXP (src
, 2)) == LABEL_REF
958 && LABEL_REF_LABEL (XEXP (src
, 2)) == target
)
959 || (ANY_RETURN_P (XEXP (src
, 2)) && XEXP (src
, 2) == target
)))
962 rev
= reversed_comparison_code (XEXP (src
, 0), insn
);
964 return gen_rtx_fmt_ee (rev
, GET_MODE (XEXP (src
, 0)),
965 XEXP (XEXP (src
, 0), 0),
966 XEXP (XEXP (src
, 0), 1));
972 /* Return nonzero if CONDITION is more strict than the condition of
973 INSN, i.e., if INSN will always branch if CONDITION is true. */
976 condition_dominates_p (rtx condition
, const rtx_insn
*insn
)
978 rtx other_condition
= get_branch_condition (insn
, JUMP_LABEL (insn
));
979 enum rtx_code code
= GET_CODE (condition
);
980 enum rtx_code other_code
;
982 if (rtx_equal_p (condition
, other_condition
)
983 || other_condition
== const_true_rtx
)
986 else if (condition
== const_true_rtx
|| other_condition
== 0)
989 other_code
= GET_CODE (other_condition
);
990 if (GET_RTX_LENGTH (code
) != 2 || GET_RTX_LENGTH (other_code
) != 2
991 || ! rtx_equal_p (XEXP (condition
, 0), XEXP (other_condition
, 0))
992 || ! rtx_equal_p (XEXP (condition
, 1), XEXP (other_condition
, 1)))
995 return comparison_dominates_p (code
, other_code
);
998 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
999 any insns already in the delay slot of JUMP. */
1002 redirect_with_delay_slots_safe_p (rtx_insn
*jump
, rtx newlabel
, rtx seq
)
1005 rtx_sequence
*pat
= as_a
<rtx_sequence
*> (PATTERN (seq
));
1007 /* Make sure all the delay slots of this jump would still
1008 be valid after threading the jump. If they are still
1009 valid, then return nonzero. */
1011 flags
= get_jump_flags (jump
, newlabel
);
1012 for (i
= 1; i
< pat
->len (); i
++)
1014 #ifdef ANNUL_IFFALSE_SLOTS
1015 (INSN_ANNULLED_BRANCH_P (jump
)
1016 && INSN_FROM_TARGET_P (pat
->insn (i
)))
1017 ? eligible_for_annul_false (jump
, i
- 1, pat
->insn (i
), flags
) :
1019 #ifdef ANNUL_IFTRUE_SLOTS
1020 (INSN_ANNULLED_BRANCH_P (jump
)
1021 && ! INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)))
1022 ? eligible_for_annul_true (jump
, i
- 1, pat
->insn (i
), flags
) :
1024 eligible_for_delay (jump
, i
- 1, pat
->insn (i
), flags
)))
1027 return (i
== pat
->len ());
1030 /* Return nonzero if redirecting JUMP to NEWLABEL does not invalidate
1031 any insns we wish to place in the delay slot of JUMP. */
1034 redirect_with_delay_list_safe_p (rtx_insn
*jump
, rtx newlabel
,
1035 rtx_insn_list
*delay_list
)
1040 /* Make sure all the insns in DELAY_LIST would still be
1041 valid after threading the jump. If they are still
1042 valid, then return nonzero. */
1044 flags
= get_jump_flags (jump
, newlabel
);
1045 for (li
= delay_list
, i
= 0; li
; li
= li
->next (), i
++)
1047 #ifdef ANNUL_IFFALSE_SLOTS
1048 (INSN_ANNULLED_BRANCH_P (jump
)
1049 && INSN_FROM_TARGET_P (li
->insn ()))
1050 ? eligible_for_annul_false (jump
, i
, li
->insn (), flags
) :
1052 #ifdef ANNUL_IFTRUE_SLOTS
1053 (INSN_ANNULLED_BRANCH_P (jump
)
1054 && ! INSN_FROM_TARGET_P (XEXP (li
, 0)))
1055 ? eligible_for_annul_true (jump
, i
, li
->insn (), flags
) :
1057 eligible_for_delay (jump
, i
, li
->insn (), flags
)))
1060 return (li
== NULL
);
1063 /* DELAY_LIST is a list of insns that have already been placed into delay
1064 slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
1065 If not, return 0; otherwise return 1. */
1068 check_annul_list_true_false (int annul_true_p
, rtx delay_list
)
1074 for (temp
= delay_list
; temp
; temp
= XEXP (temp
, 1))
1076 rtx trial
= XEXP (temp
, 0);
1078 if ((annul_true_p
&& INSN_FROM_TARGET_P (trial
))
1079 || (!annul_true_p
&& !INSN_FROM_TARGET_P (trial
)))
1087 /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1088 the condition tested by INSN is CONDITION and the resources shown in
1089 OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1090 from SEQ's delay list, in addition to whatever insns it may execute
1091 (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1092 needed while searching for delay slot insns. Return the concatenated
1093 delay list if possible, otherwise, return 0.
1095 SLOTS_TO_FILL is the total number of slots required by INSN, and
1096 PSLOTS_FILLED points to the number filled so far (also the number of
1097 insns in DELAY_LIST). It is updated with the number that have been
1098 filled from the SEQUENCE, if any.
1100 PANNUL_P points to a nonzero value if we already know that we need
1101 to annul INSN. If this routine determines that annulling is needed,
1102 it may set that value nonzero.
1104 PNEW_THREAD points to a location that is to receive the place at which
1105 execution should continue. */
1107 static rtx_insn_list
*
1108 steal_delay_list_from_target (rtx_insn
*insn
, rtx condition
, rtx_sequence
*seq
,
1109 rtx_insn_list
*delay_list
, struct resources
*sets
,
1110 struct resources
*needed
,
1111 struct resources
*other_needed
,
1112 int slots_to_fill
, int *pslots_filled
,
1113 int *pannul_p
, rtx
*pnew_thread
)
1115 int slots_remaining
= slots_to_fill
- *pslots_filled
;
1116 int total_slots_filled
= *pslots_filled
;
1117 rtx_insn_list
*new_delay_list
= 0;
1118 int must_annul
= *pannul_p
;
1121 struct resources cc_set
;
1124 /* We can't do anything if there are more delay slots in SEQ than we
1125 can handle, or if we don't know that it will be a taken branch.
1126 We know that it will be a taken branch if it is either an unconditional
1127 branch or a conditional branch with a stricter branch condition.
1129 Also, exit if the branch has more than one set, since then it is computing
1130 other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1131 ??? It may be possible to move other sets into INSN in addition to
1132 moving the instructions in the delay slots.
1134 We can not steal the delay list if one of the instructions in the
1135 current delay_list modifies the condition codes and the jump in the
1136 sequence is a conditional jump. We can not do this because we can
1137 not change the direction of the jump because the condition codes
1138 will effect the direction of the jump in the sequence. */
1140 CLEAR_RESOURCE (&cc_set
);
1141 for (rtx_insn_list
*temp
= delay_list
; temp
; temp
= temp
->next ())
1143 rtx_insn
*trial
= temp
->insn ();
1145 mark_set_resources (trial
, &cc_set
, 0, MARK_SRC_DEST_CALL
);
1146 if (insn_references_resource_p (seq
->insn (0), &cc_set
, false))
1150 if (XVECLEN (seq
, 0) - 1 > slots_remaining
1151 || ! condition_dominates_p (condition
, seq
->insn (0))
1152 || ! single_set (seq
->insn (0)))
1155 /* On some targets, branches with delay slots can have a limited
1156 displacement. Give the back end a chance to tell us we can't do
1158 if (! targetm
.can_follow_jump (insn
, seq
->insn (0)))
1161 redundant
= XALLOCAVEC (bool, XVECLEN (seq
, 0));
1162 for (i
= 1; i
< seq
->len (); i
++)
1164 rtx_insn
*trial
= seq
->insn (i
);
1167 if (insn_references_resource_p (trial
, sets
, false)
1168 || insn_sets_resource_p (trial
, needed
, false)
1169 || insn_sets_resource_p (trial
, sets
, false)
1170 /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1172 || (HAVE_cc0
&& find_reg_note (trial
, REG_CC_USER
, NULL_RTX
))
1173 /* If TRIAL is from the fallthrough code of an annulled branch insn
1174 in SEQ, we cannot use it. */
1175 || (INSN_ANNULLED_BRANCH_P (seq
->insn (0))
1176 && ! INSN_FROM_TARGET_P (trial
)))
1179 /* If this insn was already done (usually in a previous delay slot),
1180 pretend we put it in our delay slot. */
1181 redundant
[i
] = redundant_insn (trial
, insn
, new_delay_list
);
1185 /* We will end up re-vectoring this branch, so compute flags
1186 based on jumping to the new label. */
1187 flags
= get_jump_flags (insn
, JUMP_LABEL (seq
->insn (0)));
1190 && ((condition
== const_true_rtx
1191 || (! insn_sets_resource_p (trial
, other_needed
, false)
1192 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1193 ? eligible_for_delay (insn
, total_slots_filled
, trial
, flags
)
1194 : (must_annul
|| (delay_list
== NULL
&& new_delay_list
== NULL
))
1196 check_annul_list_true_false (0, delay_list
)
1197 && check_annul_list_true_false (0, new_delay_list
)
1198 && eligible_for_annul_false (insn
, total_slots_filled
,
1203 rtx_insn
*temp
= copy_delay_slot_insn (trial
);
1204 INSN_FROM_TARGET_P (temp
) = 1;
1205 new_delay_list
= add_to_delay_list (temp
, new_delay_list
);
1206 total_slots_filled
++;
1208 if (--slots_remaining
== 0)
1215 /* Record the effect of the instructions that were redundant and which
1216 we therefore decided not to copy. */
1217 for (i
= 1; i
< seq
->len (); i
++)
1219 update_block (seq
->insn (i
), insn
);
1221 /* Show the place to which we will be branching. */
1222 *pnew_thread
= first_active_target_insn (JUMP_LABEL (seq
->insn (0)));
1224 /* Add any new insns to the delay list and update the count of the
1225 number of slots filled. */
1226 *pslots_filled
= total_slots_filled
;
1230 if (delay_list
== 0)
1231 return new_delay_list
;
1233 for (rtx_insn_list
*temp
= new_delay_list
; temp
; temp
= temp
->next ())
1234 delay_list
= add_to_delay_list (temp
->insn (), delay_list
);
1239 /* Similar to steal_delay_list_from_target except that SEQ is on the
1240 fallthrough path of INSN. Here we only do something if the delay insn
1241 of SEQ is an unconditional branch. In that case we steal its delay slot
1242 for INSN since unconditional branches are much easier to fill. */
1244 static rtx_insn_list
*
1245 steal_delay_list_from_fallthrough (rtx_insn
*insn
, rtx condition
,
1247 rtx_insn_list
*delay_list
,
1248 struct resources
*sets
,
1249 struct resources
*needed
,
1250 struct resources
*other_needed
,
1251 int slots_to_fill
, int *pslots_filled
,
1256 int must_annul
= *pannul_p
;
1259 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
1261 /* We can't do anything if SEQ's delay insn isn't an
1262 unconditional branch. */
1264 if (! simplejump_or_return_p (seq
->insn (0)))
1267 for (i
= 1; i
< seq
->len (); i
++)
1269 rtx_insn
*trial
= seq
->insn (i
);
1271 /* If TRIAL sets CC0, stealing it will move it too far from the use
1273 if (insn_references_resource_p (trial
, sets
, false)
1274 || insn_sets_resource_p (trial
, needed
, false)
1275 || insn_sets_resource_p (trial
, sets
, false)
1276 || (HAVE_cc0
&& sets_cc0_p (PATTERN (trial
))))
1280 /* If this insn was already done, we don't need it. */
1281 if (redundant_insn (trial
, insn
, delay_list
))
1283 update_block (trial
, insn
);
1284 delete_from_delay_slot (trial
);
1289 && ((condition
== const_true_rtx
1290 || (! insn_sets_resource_p (trial
, other_needed
, false)
1291 && ! may_trap_or_fault_p (PATTERN (trial
)))))
1292 ? eligible_for_delay (insn
, *pslots_filled
, trial
, flags
)
1293 : (must_annul
|| delay_list
== NULL
) && (must_annul
= 1,
1294 check_annul_list_true_false (1, delay_list
)
1295 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
1299 delete_from_delay_slot (trial
);
1300 delay_list
= add_to_delay_list (trial
, delay_list
);
1302 if (++(*pslots_filled
) == slots_to_fill
)
1314 /* Try merging insns starting at THREAD which match exactly the insns in
1317 If all insns were matched and the insn was previously annulling, the
1318 annul bit will be cleared.
1320 For each insn that is merged, if the branch is or will be non-annulling,
1321 we delete the merged insn. */
1324 try_merge_delay_insns (rtx insn
, rtx_insn
*thread
)
1326 rtx_insn
*trial
, *next_trial
;
1327 rtx_insn
*delay_insn
= as_a
<rtx_insn
*> (XVECEXP (PATTERN (insn
), 0, 0));
1328 int annul_p
= JUMP_P (delay_insn
) && INSN_ANNULLED_BRANCH_P (delay_insn
);
1329 int slot_number
= 1;
1330 int num_slots
= XVECLEN (PATTERN (insn
), 0);
1331 rtx next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1332 struct resources set
, needed
, modified
;
1333 rtx_insn_list
*merged_insns
= 0;
1337 flags
= get_jump_flags (delay_insn
, JUMP_LABEL (delay_insn
));
1339 CLEAR_RESOURCE (&needed
);
1340 CLEAR_RESOURCE (&set
);
1342 /* If this is not an annulling branch, take into account anything needed in
1343 INSN's delay slot. This prevents two increments from being incorrectly
1344 folded into one. If we are annulling, this would be the correct
1345 thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1346 will essentially disable this optimization. This method is somewhat of
1347 a kludge, but I don't see a better way.) */
1349 for (i
= 1 ; i
< num_slots
; i
++)
1350 if (XVECEXP (PATTERN (insn
), 0, i
))
1351 mark_referenced_resources (XVECEXP (PATTERN (insn
), 0, i
), &needed
,
1354 for (trial
= thread
; !stop_search_p (trial
, 1); trial
= next_trial
)
1356 rtx pat
= PATTERN (trial
);
1357 rtx oldtrial
= trial
;
1359 next_trial
= next_nonnote_insn (trial
);
1361 /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1362 if (NONJUMP_INSN_P (trial
)
1363 && (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
))
1366 if (GET_CODE (next_to_match
) == GET_CODE (trial
)
1368 /* We can't share an insn that sets cc0. */
1369 && ! sets_cc0_p (pat
)
1371 && ! insn_references_resource_p (trial
, &set
, true)
1372 && ! insn_sets_resource_p (trial
, &set
, true)
1373 && ! insn_sets_resource_p (trial
, &needed
, true)
1374 && (trial
= try_split (pat
, trial
, 0)) != 0
1375 /* Update next_trial, in case try_split succeeded. */
1376 && (next_trial
= next_nonnote_insn (trial
))
1377 /* Likewise THREAD. */
1378 && (thread
= oldtrial
== thread
? trial
: thread
)
1379 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (trial
))
1380 /* Have to test this condition if annul condition is different
1381 from (and less restrictive than) non-annulling one. */
1382 && eligible_for_delay (delay_insn
, slot_number
- 1, trial
, flags
))
1387 update_block (trial
, thread
);
1388 if (trial
== thread
)
1389 thread
= next_active_insn (thread
);
1391 delete_related_insns (trial
);
1392 INSN_FROM_TARGET_P (next_to_match
) = 0;
1395 merged_insns
= gen_rtx_INSN_LIST (VOIDmode
, trial
, merged_insns
);
1397 if (++slot_number
== num_slots
)
1400 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1403 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
1404 mark_referenced_resources (trial
, &needed
, true);
1407 /* See if we stopped on a filled insn. If we did, try to see if its
1408 delay slots match. */
1409 if (slot_number
!= num_slots
1410 && trial
&& NONJUMP_INSN_P (trial
)
1411 && GET_CODE (PATTERN (trial
)) == SEQUENCE
1412 && !(JUMP_P (XVECEXP (PATTERN (trial
), 0, 0))
1413 && INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial
), 0, 0))))
1415 rtx_sequence
*pat
= as_a
<rtx_sequence
*> (PATTERN (trial
));
1416 rtx filled_insn
= XVECEXP (pat
, 0, 0);
1418 /* Account for resources set/needed by the filled insn. */
1419 mark_set_resources (filled_insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1420 mark_referenced_resources (filled_insn
, &needed
, true);
1422 for (i
= 1; i
< pat
->len (); i
++)
1424 rtx_insn
*dtrial
= pat
->insn (i
);
1426 CLEAR_RESOURCE (&modified
);
1427 /* Account for resources set by the the insn following NEXT_TO_MATCH
1428 inside INSN's delay list. */
1429 for (j
= 1; slot_number
+ j
< num_slots
; j
++)
1430 mark_set_resources (XVECEXP (PATTERN (insn
), 0, slot_number
+ j
),
1431 &modified
, 0, MARK_SRC_DEST_CALL
);
1432 /* Account for resources set by the the insn before DTRIAL and inside
1433 TRIAL's delay list. */
1434 for (j
= 1; j
< i
; j
++)
1435 mark_set_resources (XVECEXP (pat
, 0, j
),
1436 &modified
, 0, MARK_SRC_DEST_CALL
);
1437 if (! insn_references_resource_p (dtrial
, &set
, true)
1438 && ! insn_sets_resource_p (dtrial
, &set
, true)
1439 && ! insn_sets_resource_p (dtrial
, &needed
, true)
1441 && ! sets_cc0_p (PATTERN (dtrial
))
1443 && rtx_equal_p (PATTERN (next_to_match
), PATTERN (dtrial
))
1444 /* Check that DTRIAL and NEXT_TO_MATCH does not reference a
1445 resource modified between them (only dtrial is checked because
1446 next_to_match and dtrial shall to be equal in order to hit
1448 && ! insn_references_resource_p (dtrial
, &modified
, true)
1449 && eligible_for_delay (delay_insn
, slot_number
- 1, dtrial
, flags
))
1455 update_block (dtrial
, thread
);
1456 new_rtx
= delete_from_delay_slot (dtrial
);
1457 if (thread
->deleted ())
1459 INSN_FROM_TARGET_P (next_to_match
) = 0;
1462 merged_insns
= gen_rtx_INSN_LIST (SImode
, dtrial
,
1465 if (++slot_number
== num_slots
)
1468 next_to_match
= XVECEXP (PATTERN (insn
), 0, slot_number
);
1472 /* Keep track of the set/referenced resources for the delay
1473 slots of any trial insns we encounter. */
1474 mark_set_resources (dtrial
, &set
, 0, MARK_SRC_DEST_CALL
);
1475 mark_referenced_resources (dtrial
, &needed
, true);
1480 /* If all insns in the delay slot have been matched and we were previously
1481 annulling the branch, we need not any more. In that case delete all the
1482 merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1483 the delay list so that we know that it isn't only being used at the
1485 if (slot_number
== num_slots
&& annul_p
)
1487 for (; merged_insns
; merged_insns
= merged_insns
->next ())
1489 if (GET_MODE (merged_insns
) == SImode
)
1493 update_block (merged_insns
->insn (), thread
);
1494 new_rtx
= delete_from_delay_slot (merged_insns
->insn ());
1495 if (thread
->deleted ())
1500 update_block (merged_insns
->insn (), thread
);
1501 delete_related_insns (merged_insns
->insn ());
1505 INSN_ANNULLED_BRANCH_P (delay_insn
) = 0;
1507 for (i
= 0; i
< XVECLEN (PATTERN (insn
), 0); i
++)
1508 INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn
), 0, i
)) = 0;
1512 /* See if INSN is redundant with an insn in front of TARGET. Often this
1513 is called when INSN is a candidate for a delay slot of TARGET.
1514 DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1515 of INSN. Often INSN will be redundant with an insn in a delay slot of
1516 some previous insn. This happens when we have a series of branches to the
1517 same label; in that case the first insn at the target might want to go
1518 into each of the delay slots.
1520 If we are not careful, this routine can take up a significant fraction
1521 of the total compilation time (4%), but only wins rarely. Hence we
1522 speed this routine up by making two passes. The first pass goes back
1523 until it hits a label and sees if it finds an insn with an identical
1524 pattern. Only in this (relatively rare) event does it check for
1527 We do not split insns we encounter. This could cause us not to find a
1528 redundant insn, but the cost of splitting seems greater than the possible
1529 gain in rare cases. */
1532 redundant_insn (rtx insn
, rtx_insn
*target
, rtx delay_list
)
1534 rtx target_main
= target
;
1535 rtx ipat
= PATTERN (insn
);
1538 struct resources needed
, set
;
1540 unsigned insns_to_search
;
1542 /* If INSN has any REG_UNUSED notes, it can't match anything since we
1543 are allowed to not actually assign to such a register. */
1544 if (find_reg_note (insn
, REG_UNUSED
, NULL_RTX
) != 0)
1547 /* Scan backwards looking for a match. */
1548 for (trial
= PREV_INSN (target
),
1549 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1550 trial
&& insns_to_search
> 0;
1551 trial
= PREV_INSN (trial
))
1553 /* (use (insn))s can come immediately after a barrier if the
1554 label that used to precede them has been deleted as dead.
1555 See delete_related_insns. */
1556 if (LABEL_P (trial
) || BARRIER_P (trial
))
1559 if (!INSN_P (trial
))
1563 pat
= PATTERN (trial
);
1564 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1567 if (rtx_sequence
*seq
= dyn_cast
<rtx_sequence
*> (pat
))
1569 /* Stop for a CALL and its delay slots because it is difficult to
1570 track its resource needs correctly. */
1571 if (CALL_P (seq
->element (0)))
1574 /* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1575 slots because it is difficult to track its resource needs
1578 #ifdef INSN_SETS_ARE_DELAYED
1579 if (INSN_SETS_ARE_DELAYED (seq
->insn (0)))
1583 #ifdef INSN_REFERENCES_ARE_DELAYED
1584 if (INSN_REFERENCES_ARE_DELAYED (seq
->insn (0)))
1588 /* See if any of the insns in the delay slot match, updating
1589 resource requirements as we go. */
1590 for (i
= seq
->len () - 1; i
> 0; i
--)
1591 if (GET_CODE (seq
->element (i
)) == GET_CODE (insn
)
1592 && rtx_equal_p (PATTERN (seq
->element (i
)), ipat
)
1593 && ! find_reg_note (seq
->element (i
), REG_UNUSED
, NULL_RTX
))
1596 /* If found a match, exit this loop early. */
1601 else if (GET_CODE (trial
) == GET_CODE (insn
) && rtx_equal_p (pat
, ipat
)
1602 && ! find_reg_note (trial
, REG_UNUSED
, NULL_RTX
))
1606 /* If we didn't find an insn that matches, return 0. */
1610 /* See what resources this insn sets and needs. If they overlap, or
1611 if this insn references CC0, it can't be redundant. */
1613 CLEAR_RESOURCE (&needed
);
1614 CLEAR_RESOURCE (&set
);
1615 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
1616 mark_referenced_resources (insn
, &needed
, true);
1618 /* If TARGET is a SEQUENCE, get the main insn. */
1619 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1620 target_main
= XVECEXP (PATTERN (target
), 0, 0);
1622 if (resource_conflicts_p (&needed
, &set
)
1623 || (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, ipat
))
1624 /* The insn requiring the delay may not set anything needed or set by
1626 || insn_sets_resource_p (target_main
, &needed
, true)
1627 || insn_sets_resource_p (target_main
, &set
, true))
1630 /* Insns we pass may not set either NEEDED or SET, so merge them for
1632 needed
.memory
|= set
.memory
;
1633 IOR_HARD_REG_SET (needed
.regs
, set
.regs
);
1635 /* This insn isn't redundant if it conflicts with an insn that either is
1636 or will be in a delay slot of TARGET. */
1640 if (insn_sets_resource_p (XEXP (delay_list
, 0), &needed
, true))
1642 delay_list
= XEXP (delay_list
, 1);
1645 if (NONJUMP_INSN_P (target
) && GET_CODE (PATTERN (target
)) == SEQUENCE
)
1646 for (i
= 1; i
< XVECLEN (PATTERN (target
), 0); i
++)
1647 if (insn_sets_resource_p (XVECEXP (PATTERN (target
), 0, i
), &needed
,
1651 /* Scan backwards until we reach a label or an insn that uses something
1652 INSN sets or sets something insn uses or sets. */
1654 for (trial
= PREV_INSN (target
),
1655 insns_to_search
= MAX_DELAY_SLOT_INSN_SEARCH
;
1656 trial
&& !LABEL_P (trial
) && insns_to_search
> 0;
1657 trial
= PREV_INSN (trial
))
1659 if (!INSN_P (trial
))
1663 pat
= PATTERN (trial
);
1664 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
1667 if (rtx_sequence
*seq
= dyn_cast
<rtx_sequence
*> (pat
))
1669 bool annul_p
= false;
1670 rtx_insn
*control
= seq
->insn (0);
1672 /* If this is a CALL_INSN and its delay slots, it is hard to track
1673 the resource needs properly, so give up. */
1674 if (CALL_P (control
))
1677 /* If this is an INSN or JUMP_INSN with delayed effects, it
1678 is hard to track the resource needs properly, so give up. */
1680 #ifdef INSN_SETS_ARE_DELAYED
1681 if (INSN_SETS_ARE_DELAYED (control
))
1685 #ifdef INSN_REFERENCES_ARE_DELAYED
1686 if (INSN_REFERENCES_ARE_DELAYED (control
))
1690 if (JUMP_P (control
))
1691 annul_p
= INSN_ANNULLED_BRANCH_P (control
);
1693 /* See if any of the insns in the delay slot match, updating
1694 resource requirements as we go. */
1695 for (i
= seq
->len () - 1; i
> 0; i
--)
1697 rtx candidate
= seq
->element (i
);
1699 /* If an insn will be annulled if the branch is false, it isn't
1700 considered as a possible duplicate insn. */
1701 if (rtx_equal_p (PATTERN (candidate
), ipat
)
1702 && ! (annul_p
&& INSN_FROM_TARGET_P (candidate
)))
1704 /* Show that this insn will be used in the sequel. */
1705 INSN_FROM_TARGET_P (candidate
) = 0;
1709 /* Unless this is an annulled insn from the target of a branch,
1710 we must stop if it sets anything needed or set by INSN. */
1711 if ((!annul_p
|| !INSN_FROM_TARGET_P (candidate
))
1712 && insn_sets_resource_p (candidate
, &needed
, true))
1716 /* If the insn requiring the delay slot conflicts with INSN, we
1718 if (insn_sets_resource_p (control
, &needed
, true))
1723 /* See if TRIAL is the same as INSN. */
1724 pat
= PATTERN (trial
);
1725 if (rtx_equal_p (pat
, ipat
))
1728 /* Can't go any further if TRIAL conflicts with INSN. */
1729 if (insn_sets_resource_p (trial
, &needed
, true))
1737 /* Return 1 if THREAD can only be executed in one way. If LABEL is nonzero,
1738 it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1739 is nonzero, we are allowed to fall into this thread; otherwise, we are
1742 If LABEL is used more than one or we pass a label other than LABEL before
1743 finding an active insn, we do not own this thread. */
1746 own_thread_p (rtx thread
, rtx label
, int allow_fallthrough
)
1748 rtx_insn
*active_insn
;
1751 /* We don't own the function end. */
1752 if (thread
== 0 || ANY_RETURN_P (thread
))
1755 /* We have a non-NULL insn. */
1756 rtx_insn
*thread_insn
= as_a
<rtx_insn
*> (thread
);
1758 /* Get the first active insn, or THREAD_INSN, if it is an active insn. */
1759 active_insn
= next_active_insn (PREV_INSN (thread_insn
));
1761 for (insn
= thread_insn
; insn
!= active_insn
; insn
= NEXT_INSN (insn
))
1763 && (insn
!= label
|| LABEL_NUSES (insn
) != 1))
1766 if (allow_fallthrough
)
1769 /* Ensure that we reach a BARRIER before any insn or label. */
1770 for (insn
= prev_nonnote_insn (thread_insn
);
1771 insn
== 0 || !BARRIER_P (insn
);
1772 insn
= prev_nonnote_insn (insn
))
1775 || (NONJUMP_INSN_P (insn
)
1776 && GET_CODE (PATTERN (insn
)) != USE
1777 && GET_CODE (PATTERN (insn
)) != CLOBBER
))
1783 /* Called when INSN is being moved from a location near the target of a jump.
1784 We leave a marker of the form (use (INSN)) immediately in front
1785 of WHERE for mark_target_live_regs. These markers will be deleted when
1788 We used to try to update the live status of registers if WHERE is at
1789 the start of a basic block, but that can't work since we may remove a
1790 BARRIER in relax_delay_slots. */
1793 update_block (rtx_insn
*insn
, rtx where
)
1795 /* Ignore if this was in a delay slot and it came from the target of
1797 if (INSN_FROM_TARGET_P (insn
))
1800 emit_insn_before (gen_rtx_USE (VOIDmode
, insn
), where
);
1802 /* INSN might be making a value live in a block where it didn't use to
1803 be. So recompute liveness information for this block. */
1805 incr_ticks_for_insn (insn
);
1808 /* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1809 the basic block containing the jump. */
1812 reorg_redirect_jump (rtx_insn
*jump
, rtx nlabel
)
1814 incr_ticks_for_insn (jump
);
1815 return redirect_jump (jump
, nlabel
, 1);
1818 /* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1819 We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1820 that reference values used in INSN. If we find one, then we move the
1821 REG_DEAD note to INSN.
1823 This is needed to handle the case where a later insn (after INSN) has a
1824 REG_DEAD note for a register used by INSN, and this later insn subsequently
1825 gets moved before a CODE_LABEL because it is a redundant insn. In this
1826 case, mark_target_live_regs may be confused into thinking the register
1827 is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1830 update_reg_dead_notes (rtx insn
, rtx delayed_insn
)
1834 for (p
= next_nonnote_insn (insn
); p
!= delayed_insn
;
1835 p
= next_nonnote_insn (p
))
1836 for (link
= REG_NOTES (p
); link
; link
= next
)
1838 next
= XEXP (link
, 1);
1840 if (REG_NOTE_KIND (link
) != REG_DEAD
1841 || !REG_P (XEXP (link
, 0)))
1844 if (reg_referenced_p (XEXP (link
, 0), PATTERN (insn
)))
1846 /* Move the REG_DEAD note from P to INSN. */
1847 remove_note (p
, link
);
1848 XEXP (link
, 1) = REG_NOTES (insn
);
1849 REG_NOTES (insn
) = link
;
1854 /* Called when an insn redundant with start_insn is deleted. If there
1855 is a REG_DEAD note for the target of start_insn between start_insn
1856 and stop_insn, then the REG_DEAD note needs to be deleted since the
1857 value no longer dies there.
1859 If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1860 confused into thinking the register is dead. */
1863 fix_reg_dead_note (rtx start_insn
, rtx stop_insn
)
1867 for (p
= next_nonnote_insn (start_insn
); p
!= stop_insn
;
1868 p
= next_nonnote_insn (p
))
1869 for (link
= REG_NOTES (p
); link
; link
= next
)
1871 next
= XEXP (link
, 1);
1873 if (REG_NOTE_KIND (link
) != REG_DEAD
1874 || !REG_P (XEXP (link
, 0)))
1877 if (reg_set_p (XEXP (link
, 0), PATTERN (start_insn
)))
1879 remove_note (p
, link
);
1885 /* Delete any REG_UNUSED notes that exist on INSN but not on REDUNDANT_INSN.
1887 This handles the case of udivmodXi4 instructions which optimize their
1888 output depending on whether any REG_UNUSED notes are present.
1889 we must make sure that INSN calculates as many results as REDUNDANT_INSN
1893 update_reg_unused_notes (rtx insn
, rtx redundant_insn
)
1897 for (link
= REG_NOTES (insn
); link
; link
= next
)
1899 next
= XEXP (link
, 1);
1901 if (REG_NOTE_KIND (link
) != REG_UNUSED
1902 || !REG_P (XEXP (link
, 0)))
1905 if (! find_regno_note (redundant_insn
, REG_UNUSED
,
1906 REGNO (XEXP (link
, 0))))
1907 remove_note (insn
, link
);
1911 static vec
<rtx
> sibling_labels
;
1913 /* Return the label before INSN, or put a new label there. If SIBLING is
1914 non-zero, it is another label associated with the new label (if any),
1915 typically the former target of the jump that will be redirected to
1919 get_label_before (rtx_insn
*insn
, rtx sibling
)
1923 /* Find an existing label at this point
1924 or make a new one if there is none. */
1925 label
= prev_nonnote_insn (insn
);
1927 if (label
== 0 || !LABEL_P (label
))
1929 rtx_insn
*prev
= PREV_INSN (insn
);
1931 label
= gen_label_rtx ();
1932 emit_label_after (label
, prev
);
1933 LABEL_NUSES (label
) = 0;
1936 sibling_labels
.safe_push (label
);
1937 sibling_labels
.safe_push (sibling
);
1943 /* Scan a function looking for insns that need a delay slot and find insns to
1944 put into the delay slot.
1946 NON_JUMPS_P is nonzero if we are to only try to fill non-jump insns (such
1947 as calls). We do these first since we don't want jump insns (that are
1948 easier to fill) to get the only insns that could be used for non-jump insns.
1949 When it is zero, only try to fill JUMP_INSNs.
1951 When slots are filled in this manner, the insns (including the
1952 delay_insn) are put together in a SEQUENCE rtx. In this fashion,
1953 it is possible to tell whether a delay slot has really been filled
1954 or not. `final' knows how to deal with this, by communicating
1955 through FINAL_SEQUENCE. */
1958 fill_simple_delay_slots (int non_jumps_p
)
1960 rtx_insn
*insn
, *trial
, *next_trial
;
1963 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
1964 struct resources needed
, set
;
1965 int slots_to_fill
, slots_filled
;
1966 rtx_insn_list
*delay_list
;
1968 for (i
= 0; i
< num_unfilled_slots
; i
++)
1971 /* Get the next insn to fill. If it has already had any slots assigned,
1972 we can't do anything with it. Maybe we'll improve this later. */
1974 insn
= unfilled_slots_base
[i
];
1977 || (NONJUMP_INSN_P (insn
)
1978 && GET_CODE (PATTERN (insn
)) == SEQUENCE
)
1979 || (JUMP_P (insn
) && non_jumps_p
)
1980 || (!JUMP_P (insn
) && ! non_jumps_p
))
1983 /* It may have been that this insn used to need delay slots, but
1984 now doesn't; ignore in that case. This can happen, for example,
1985 on the HP PA RISC, where the number of delay slots depends on
1986 what insns are nearby. */
1987 slots_to_fill
= num_delay_slots (insn
);
1989 /* Some machine description have defined instructions to have
1990 delay slots only in certain circumstances which may depend on
1991 nearby insns (which change due to reorg's actions).
1993 For example, the PA port normally has delay slots for unconditional
1996 However, the PA port claims such jumps do not have a delay slot
1997 if they are immediate successors of certain CALL_INSNs. This
1998 allows the port to favor filling the delay slot of the call with
1999 the unconditional jump. */
2000 if (slots_to_fill
== 0)
2003 /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2004 says how many. After initialization, first try optimizing
2007 nop add %o7,.-L1,%o7
2011 If this case applies, the delay slot of the call is filled with
2012 the unconditional jump. This is done first to avoid having the
2013 delay slot of the call filled in the backward scan. Also, since
2014 the unconditional jump is likely to also have a delay slot, that
2015 insn must exist when it is subsequently scanned.
2017 This is tried on each insn with delay slots as some machines
2018 have insns which perform calls, but are not represented as
2025 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2027 flags
= get_jump_flags (insn
, NULL_RTX
);
2029 if ((trial
= next_active_insn (insn
))
2031 && simplejump_p (trial
)
2032 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2033 && no_labels_between_p (insn
, trial
)
2034 && ! can_throw_internal (trial
))
2038 delay_list
= add_to_delay_list (trial
, delay_list
);
2040 /* TRIAL may have had its delay slot filled, then unfilled. When
2041 the delay slot is unfilled, TRIAL is placed back on the unfilled
2042 slots obstack. Unfortunately, it is placed on the end of the
2043 obstack, not in its original location. Therefore, we must search
2044 from entry i + 1 to the end of the unfilled slots obstack to
2045 try and find TRIAL. */
2046 tmp
= &unfilled_slots_base
[i
+ 1];
2047 while (*tmp
!= trial
&& tmp
!= unfilled_slots_next
)
2050 /* Remove the unconditional jump from consideration for delay slot
2051 filling and unthread it. */
2055 rtx_insn
*next
= NEXT_INSN (trial
);
2056 rtx_insn
*prev
= PREV_INSN (trial
);
2058 SET_NEXT_INSN (prev
) = next
;
2060 SET_PREV_INSN (next
) = prev
;
2064 /* Now, scan backwards from the insn to search for a potential
2065 delay-slot candidate. Stop searching when a label or jump is hit.
2067 For each candidate, if it is to go into the delay slot (moved
2068 forward in execution sequence), it must not need or set any resources
2069 that were set by later insns and must not set any resources that
2070 are needed for those insns.
2072 The delay slot insn itself sets resources unless it is a call
2073 (in which case the called routine, not the insn itself, is doing
2076 if (slots_filled
< slots_to_fill
)
2078 /* If the flags register is dead after the insn, then we want to be
2079 able to accept a candidate that clobbers it. For this purpose,
2080 we need to filter the flags register during life analysis, so
2081 that it doesn't create RAW and WAW dependencies, while still
2082 creating the necessary WAR dependencies. */
2084 = (slots_to_fill
== 1
2085 && targetm
.flags_regnum
!= INVALID_REGNUM
2086 && find_regno_note (insn
, REG_DEAD
, targetm
.flags_regnum
));
2087 struct resources fset
;
2088 CLEAR_RESOURCE (&needed
);
2089 CLEAR_RESOURCE (&set
);
2090 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST
);
2093 CLEAR_RESOURCE (&fset
);
2094 mark_set_resources (insn
, &fset
, 0, MARK_SRC_DEST
);
2096 mark_referenced_resources (insn
, &needed
, false);
2098 for (trial
= prev_nonnote_insn (insn
); ! stop_search_p (trial
, 1);
2101 next_trial
= prev_nonnote_insn (trial
);
2103 /* This must be an INSN or CALL_INSN. */
2104 pat
= PATTERN (trial
);
2106 /* Stand-alone USE and CLOBBER are just for flow. */
2107 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2110 /* Check for resource conflict first, to avoid unnecessary
2112 if (! insn_references_resource_p (trial
, &set
, true)
2113 && ! insn_sets_resource_p (trial
,
2114 filter_flags
? &fset
: &set
,
2116 && ! insn_sets_resource_p (trial
, &needed
, true)
2118 /* Can't separate set of cc0 from its use. */
2119 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2121 && ! can_throw_internal (trial
))
2123 trial
= try_split (pat
, trial
, 1);
2124 next_trial
= prev_nonnote_insn (trial
);
2125 if (eligible_for_delay (insn
, slots_filled
, trial
, flags
))
2127 /* In this case, we are searching backward, so if we
2128 find insns to put on the delay list, we want
2129 to put them at the head, rather than the
2130 tail, of the list. */
2132 update_reg_dead_notes (trial
, insn
);
2133 delay_list
= gen_rtx_INSN_LIST (VOIDmode
,
2135 update_block (trial
, trial
);
2136 delete_related_insns (trial
);
2137 if (slots_to_fill
== ++slots_filled
)
2143 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2146 mark_set_resources (trial
, &fset
, 0, MARK_SRC_DEST_CALL
);
2147 /* If the flags register is set, then it doesn't create RAW
2148 dependencies any longer and it also doesn't create WAW
2149 dependencies since it's dead after the original insn. */
2150 if (TEST_HARD_REG_BIT (fset
.regs
, targetm
.flags_regnum
))
2152 CLEAR_HARD_REG_BIT (needed
.regs
, targetm
.flags_regnum
);
2153 CLEAR_HARD_REG_BIT (fset
.regs
, targetm
.flags_regnum
);
2156 mark_referenced_resources (trial
, &needed
, true);
2160 /* If all needed slots haven't been filled, we come here. */
2162 /* Try to optimize case of jumping around a single insn. */
2163 #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2164 if (slots_filled
!= slots_to_fill
2167 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
2168 && !ANY_RETURN_P (JUMP_LABEL (insn
)))
2170 delay_list
= optimize_skip (insn
);
2176 /* Try to get insns from beyond the insn needing the delay slot.
2177 These insns can neither set or reference resources set in insns being
2178 skipped, cannot set resources in the insn being skipped, and, if this
2179 is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2180 call might not return).
2182 There used to be code which continued past the target label if
2183 we saw all uses of the target label. This code did not work,
2184 because it failed to account for some instructions which were
2185 both annulled and marked as from the target. This can happen as a
2186 result of optimize_skip. Since this code was redundant with
2187 fill_eager_delay_slots anyways, it was just deleted. */
2189 if (slots_filled
!= slots_to_fill
2190 /* If this instruction could throw an exception which is
2191 caught in the same function, then it's not safe to fill
2192 the delay slot with an instruction from beyond this
2193 point. For example, consider:
2204 Even though `i' is a local variable, we must be sure not
2205 to put `i = 3' in the delay slot if `f' might throw an
2208 Presumably, we should also check to see if we could get
2209 back to this function via `setjmp'. */
2210 && ! can_throw_internal (insn
)
2213 int maybe_never
= 0;
2214 rtx pat
, trial_delay
;
2216 CLEAR_RESOURCE (&needed
);
2217 CLEAR_RESOURCE (&set
);
2218 mark_set_resources (insn
, &set
, 0, MARK_SRC_DEST_CALL
);
2219 mark_referenced_resources (insn
, &needed
, true);
2224 for (trial
= next_nonnote_insn (insn
); !stop_search_p (trial
, 1);
2227 next_trial
= next_nonnote_insn (trial
);
2229 /* This must be an INSN or CALL_INSN. */
2230 pat
= PATTERN (trial
);
2232 /* Stand-alone USE and CLOBBER are just for flow. */
2233 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2236 /* If this already has filled delay slots, get the insn needing
2238 if (GET_CODE (pat
) == SEQUENCE
)
2239 trial_delay
= XVECEXP (pat
, 0, 0);
2241 trial_delay
= trial
;
2243 /* Stop our search when seeing a jump. */
2244 if (JUMP_P (trial_delay
))
2247 /* See if we have a resource problem before we try to split. */
2248 if (GET_CODE (pat
) != SEQUENCE
2249 && ! insn_references_resource_p (trial
, &set
, true)
2250 && ! insn_sets_resource_p (trial
, &set
, true)
2251 && ! insn_sets_resource_p (trial
, &needed
, true)
2253 && ! (reg_mentioned_p (cc0_rtx
, pat
) && ! sets_cc0_p (pat
))
2255 && ! (maybe_never
&& may_trap_or_fault_p (pat
))
2256 && (trial
= try_split (pat
, trial
, 0))
2257 && eligible_for_delay (insn
, slots_filled
, trial
, flags
)
2258 && ! can_throw_internal (trial
))
2260 next_trial
= next_nonnote_insn (trial
);
2261 delay_list
= add_to_delay_list (trial
, delay_list
);
2262 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, pat
))
2263 link_cc0_insns (trial
);
2265 delete_related_insns (trial
);
2266 if (slots_to_fill
== ++slots_filled
)
2271 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2272 mark_referenced_resources (trial
, &needed
, true);
2274 /* Ensure we don't put insns between the setting of cc and the
2275 comparison by moving a setting of cc into an earlier delay
2276 slot since these insns could clobber the condition code. */
2279 /* If this is a call, we might not get here. */
2280 if (CALL_P (trial_delay
))
2284 /* If there are slots left to fill and our search was stopped by an
2285 unconditional branch, try the insn at the branch target. We can
2286 redirect the branch if it works.
2288 Don't do this if the insn at the branch target is a branch. */
2289 if (slots_to_fill
!= slots_filled
2291 && jump_to_label_p (trial
)
2292 && simplejump_p (trial
)
2293 && (next_trial
= next_active_insn (JUMP_LABEL (trial
))) != 0
2294 && ! (NONJUMP_INSN_P (next_trial
)
2295 && GET_CODE (PATTERN (next_trial
)) == SEQUENCE
)
2296 && !JUMP_P (next_trial
)
2297 && ! insn_references_resource_p (next_trial
, &set
, true)
2298 && ! insn_sets_resource_p (next_trial
, &set
, true)
2299 && ! insn_sets_resource_p (next_trial
, &needed
, true)
2301 && ! reg_mentioned_p (cc0_rtx
, PATTERN (next_trial
))
2303 && ! (maybe_never
&& may_trap_or_fault_p (PATTERN (next_trial
)))
2304 && (next_trial
= try_split (PATTERN (next_trial
), next_trial
, 0))
2305 && eligible_for_delay (insn
, slots_filled
, next_trial
, flags
)
2306 && ! can_throw_internal (trial
))
2308 /* See comment in relax_delay_slots about necessity of using
2309 next_real_insn here. */
2310 rtx_insn
*new_label
= next_real_insn (next_trial
);
2313 new_label
= get_label_before (new_label
, JUMP_LABEL (trial
));
2315 new_label
= find_end_label (simple_return_rtx
);
2320 = add_to_delay_list (copy_delay_slot_insn (next_trial
),
2323 reorg_redirect_jump (trial
, new_label
);
2328 /* If this is an unconditional jump, then try to get insns from the
2329 target of the jump. */
2331 && simplejump_p (insn
)
2332 && slots_filled
!= slots_to_fill
)
2334 = fill_slots_from_thread (insn
, const_true_rtx
,
2335 next_active_insn (JUMP_LABEL (insn
)),
2337 own_thread_p (JUMP_LABEL (insn
),
2338 JUMP_LABEL (insn
), 0),
2339 slots_to_fill
, &slots_filled
,
2343 unfilled_slots_base
[i
]
2344 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
2346 if (slots_to_fill
== slots_filled
)
2347 unfilled_slots_base
[i
] = 0;
2349 note_delay_statistics (slots_filled
, 0);
2353 /* Follow any unconditional jump at LABEL, for the purpose of redirecting JUMP;
2354 return the ultimate label reached by any such chain of jumps.
2355 Return a suitable return rtx if the chain ultimately leads to a
2357 If LABEL is not followed by a jump, return LABEL.
2358 If the chain loops or we can't find end, return LABEL,
2359 since that tells caller to avoid changing the insn.
2360 If the returned label is obtained by following a crossing jump,
2361 set *CROSSING to true, otherwise set it to false. */
2364 follow_jumps (rtx label
, rtx_insn
*jump
, bool *crossing
)
2371 if (ANY_RETURN_P (label
))
2374 rtx_insn
*value
= as_a
<rtx_insn
*> (label
);
2378 && (insn
= next_active_insn (value
)) != 0
2380 && JUMP_LABEL (insn
) != NULL_RTX
2381 && ((any_uncondjump_p (insn
) && onlyjump_p (insn
))
2382 || ANY_RETURN_P (PATTERN (insn
)))
2383 && (next
= NEXT_INSN (insn
))
2384 && BARRIER_P (next
));
2387 rtx this_label_or_return
= JUMP_LABEL (insn
);
2389 /* If we have found a cycle, make the insn jump to itself. */
2390 if (this_label_or_return
== label
)
2393 /* Cannot follow returns and cannot look through tablejumps. */
2394 if (ANY_RETURN_P (this_label_or_return
))
2395 return this_label_or_return
;
2397 rtx_insn
*this_label
= as_a
<rtx_insn
*> (this_label_or_return
);
2398 if (NEXT_INSN (this_label
)
2399 && JUMP_TABLE_DATA_P (NEXT_INSN (this_label
)))
2402 if (!targetm
.can_follow_jump (jump
, insn
))
2405 *crossing
= CROSSING_JUMP_P (jump
);
2413 /* Try to find insns to place in delay slots.
2415 INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2416 or is an unconditional branch if CONDITION is const_true_rtx.
2417 *PSLOTS_FILLED is updated with the number of slots that we have filled.
2419 THREAD is a flow-of-control, either the insns to be executed if the
2420 branch is true or if the branch is false, THREAD_IF_TRUE says which.
2422 OPPOSITE_THREAD is the thread in the opposite direction. It is used
2423 to see if any potential delay slot insns set things needed there.
2425 LIKELY is nonzero if it is extremely likely that the branch will be
2426 taken and THREAD_IF_TRUE is set. This is used for the branch at the
2427 end of a loop back up to the top.
2429 OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2430 thread. I.e., it is the fallthrough code of our jump or the target of the
2431 jump when we are the only jump going there.
2433 If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2434 case, we can only take insns from the head of the thread for our delay
2435 slot. We then adjust the jump to point after the insns we have taken. */
2437 static rtx_insn_list
*
2438 fill_slots_from_thread (rtx_insn
*insn
, rtx condition
, rtx thread_or_return
,
2439 rtx opposite_thread
, int likely
,
2441 int own_thread
, int slots_to_fill
,
2442 int *pslots_filled
, rtx_insn_list
*delay_list
)
2445 struct resources opposite_needed
, set
, needed
;
2451 /* Validate our arguments. */
2452 gcc_assert (condition
!= const_true_rtx
|| thread_if_true
);
2453 gcc_assert (own_thread
|| thread_if_true
);
2455 flags
= get_jump_flags (insn
, JUMP_LABEL (insn
));
2457 /* If our thread is the end of subroutine, we can't get any delay
2459 if (thread_or_return
== NULL_RTX
|| ANY_RETURN_P (thread_or_return
))
2462 rtx_insn
*thread
= as_a
<rtx_insn
*> (thread_or_return
);
2464 /* If this is an unconditional branch, nothing is needed at the
2465 opposite thread. Otherwise, compute what is needed there. */
2466 if (condition
== const_true_rtx
)
2467 CLEAR_RESOURCE (&opposite_needed
);
2469 mark_target_live_regs (get_insns (), opposite_thread
, &opposite_needed
);
2471 /* If the insn at THREAD can be split, do it here to avoid having to
2472 update THREAD and NEW_THREAD if it is done in the loop below. Also
2473 initialize NEW_THREAD. */
2475 new_thread
= thread
= try_split (PATTERN (thread
), thread
, 0);
2477 /* Scan insns at THREAD. We are looking for an insn that can be removed
2478 from THREAD (it neither sets nor references resources that were set
2479 ahead of it and it doesn't set anything needs by the insns ahead of
2480 it) and that either can be placed in an annulling insn or aren't
2481 needed at OPPOSITE_THREAD. */
2483 CLEAR_RESOURCE (&needed
);
2484 CLEAR_RESOURCE (&set
);
2486 /* If we do not own this thread, we must stop as soon as we find
2487 something that we can't put in a delay slot, since all we can do
2488 is branch into THREAD at a later point. Therefore, labels stop
2489 the search if this is not the `true' thread. */
2491 for (trial
= thread
;
2492 ! stop_search_p (trial
, ! thread_if_true
) && (! lose
|| own_thread
);
2493 trial
= next_nonnote_insn (trial
))
2497 /* If we have passed a label, we no longer own this thread. */
2498 if (LABEL_P (trial
))
2504 pat
= PATTERN (trial
);
2505 if (GET_CODE (pat
) == USE
|| GET_CODE (pat
) == CLOBBER
)
2508 /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2509 don't separate or copy insns that set and use CC0. */
2510 if (! insn_references_resource_p (trial
, &set
, true)
2511 && ! insn_sets_resource_p (trial
, &set
, true)
2512 && ! insn_sets_resource_p (trial
, &needed
, true)
2514 && ! (reg_mentioned_p (cc0_rtx
, pat
)
2515 && (! own_thread
|| ! sets_cc0_p (pat
)))
2517 && ! can_throw_internal (trial
))
2521 /* If TRIAL is redundant with some insn before INSN, we don't
2522 actually need to add it to the delay list; we can merely pretend
2524 if ((prior_insn
= redundant_insn (trial
, insn
, delay_list
)))
2526 fix_reg_dead_note (prior_insn
, insn
);
2529 update_block (trial
, thread
);
2530 if (trial
== thread
)
2532 thread
= next_active_insn (thread
);
2533 if (new_thread
== trial
)
2534 new_thread
= thread
;
2537 delete_related_insns (trial
);
2541 update_reg_unused_notes (prior_insn
, trial
);
2542 new_thread
= next_active_insn (trial
);
2548 /* There are two ways we can win: If TRIAL doesn't set anything
2549 needed at the opposite thread and can't trap, or if it can
2550 go into an annulled delay slot. But we want neither to copy
2551 nor to speculate frame-related insns. */
2553 && ((condition
== const_true_rtx
2554 && (own_thread
|| !RTX_FRAME_RELATED_P (trial
)))
2555 || (! insn_sets_resource_p (trial
, &opposite_needed
, true)
2556 && ! may_trap_or_fault_p (pat
)
2557 && ! RTX_FRAME_RELATED_P (trial
))))
2560 trial
= try_split (pat
, trial
, 0);
2561 if (new_thread
== old_trial
)
2563 if (thread
== old_trial
)
2565 pat
= PATTERN (trial
);
2566 if (eligible_for_delay (insn
, *pslots_filled
, trial
, flags
))
2570 #ifdef ANNUL_IFTRUE_SLOTS
2573 #ifdef ANNUL_IFFALSE_SLOTS
2579 trial
= try_split (pat
, trial
, 0);
2580 if (new_thread
== old_trial
)
2582 if (thread
== old_trial
)
2584 pat
= PATTERN (trial
);
2585 if ((must_annul
|| delay_list
== NULL
) && (thread_if_true
2586 ? check_annul_list_true_false (0, delay_list
)
2587 && eligible_for_annul_false (insn
, *pslots_filled
, trial
, flags
)
2588 : check_annul_list_true_false (1, delay_list
)
2589 && eligible_for_annul_true (insn
, *pslots_filled
, trial
, flags
)))
2596 if (HAVE_cc0
&& reg_mentioned_p (cc0_rtx
, pat
))
2597 link_cc0_insns (trial
);
2599 /* If we own this thread, delete the insn. If this is the
2600 destination of a branch, show that a basic block status
2601 may have been updated. In any case, mark the new
2602 starting point of this thread. */
2607 update_block (trial
, thread
);
2608 if (trial
== thread
)
2610 thread
= next_active_insn (thread
);
2611 if (new_thread
== trial
)
2612 new_thread
= thread
;
2615 /* We are moving this insn, not deleting it. We must
2616 temporarily increment the use count on any referenced
2617 label lest it be deleted by delete_related_insns. */
2618 for (note
= REG_NOTES (trial
);
2620 note
= XEXP (note
, 1))
2621 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2622 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2624 /* REG_LABEL_OPERAND could be
2625 NOTE_INSN_DELETED_LABEL too. */
2626 if (LABEL_P (XEXP (note
, 0)))
2627 LABEL_NUSES (XEXP (note
, 0))++;
2629 gcc_assert (REG_NOTE_KIND (note
)
2630 == REG_LABEL_OPERAND
);
2632 if (jump_to_label_p (trial
))
2633 LABEL_NUSES (JUMP_LABEL (trial
))++;
2635 delete_related_insns (trial
);
2637 for (note
= REG_NOTES (trial
);
2639 note
= XEXP (note
, 1))
2640 if (REG_NOTE_KIND (note
) == REG_LABEL_OPERAND
2641 || REG_NOTE_KIND (note
) == REG_LABEL_TARGET
)
2643 /* REG_LABEL_OPERAND could be
2644 NOTE_INSN_DELETED_LABEL too. */
2645 if (LABEL_P (XEXP (note
, 0)))
2646 LABEL_NUSES (XEXP (note
, 0))--;
2648 gcc_assert (REG_NOTE_KIND (note
)
2649 == REG_LABEL_OPERAND
);
2651 if (jump_to_label_p (trial
))
2652 LABEL_NUSES (JUMP_LABEL (trial
))--;
2655 new_thread
= next_active_insn (trial
);
2657 temp
= own_thread
? trial
: copy_delay_slot_insn (trial
);
2659 INSN_FROM_TARGET_P (temp
) = 1;
2661 delay_list
= add_to_delay_list (temp
, delay_list
);
2663 if (slots_to_fill
== ++(*pslots_filled
))
2665 /* Even though we have filled all the slots, we
2666 may be branching to a location that has a
2667 redundant insn. Skip any if so. */
2668 while (new_thread
&& ! own_thread
2669 && ! insn_sets_resource_p (new_thread
, &set
, true)
2670 && ! insn_sets_resource_p (new_thread
, &needed
,
2672 && ! insn_references_resource_p (new_thread
,
2675 = redundant_insn (new_thread
, insn
,
2678 /* We know we do not own the thread, so no need
2679 to call update_block and delete_insn. */
2680 fix_reg_dead_note (prior_insn
, insn
);
2681 update_reg_unused_notes (prior_insn
, new_thread
);
2682 new_thread
= next_active_insn (new_thread
);
2692 /* This insn can't go into a delay slot. */
2694 mark_set_resources (trial
, &set
, 0, MARK_SRC_DEST_CALL
);
2695 mark_referenced_resources (trial
, &needed
, true);
2697 /* Ensure we don't put insns between the setting of cc and the comparison
2698 by moving a setting of cc into an earlier delay slot since these insns
2699 could clobber the condition code. */
2702 /* If this insn is a register-register copy and the next insn has
2703 a use of our destination, change it to use our source. That way,
2704 it will become a candidate for our delay slot the next time
2705 through this loop. This case occurs commonly in loops that
2708 We could check for more complex cases than those tested below,
2709 but it doesn't seem worth it. It might also be a good idea to try
2710 to swap the two insns. That might do better.
2712 We can't do this if the next insn modifies our destination, because
2713 that would make the replacement into the insn invalid. We also can't
2714 do this if it modifies our source, because it might be an earlyclobber
2715 operand. This latter test also prevents updating the contents of
2716 a PRE_INC. We also can't do this if there's overlap of source and
2717 destination. Overlap may happen for larger-than-register-size modes. */
2719 if (NONJUMP_INSN_P (trial
) && GET_CODE (pat
) == SET
2720 && REG_P (SET_SRC (pat
))
2721 && REG_P (SET_DEST (pat
))
2722 && !reg_overlap_mentioned_p (SET_DEST (pat
), SET_SRC (pat
)))
2724 rtx next
= next_nonnote_insn (trial
);
2726 if (next
&& NONJUMP_INSN_P (next
)
2727 && GET_CODE (PATTERN (next
)) != USE
2728 && ! reg_set_p (SET_DEST (pat
), next
)
2729 && ! reg_set_p (SET_SRC (pat
), next
)
2730 && reg_referenced_p (SET_DEST (pat
), PATTERN (next
))
2731 && ! modified_in_p (SET_DEST (pat
), next
))
2732 validate_replace_rtx (SET_DEST (pat
), SET_SRC (pat
), next
);
2736 /* If we stopped on a branch insn that has delay slots, see if we can
2737 steal some of the insns in those slots. */
2738 if (trial
&& NONJUMP_INSN_P (trial
)
2739 && GET_CODE (PATTERN (trial
)) == SEQUENCE
2740 && JUMP_P (XVECEXP (PATTERN (trial
), 0, 0)))
2742 rtx_sequence
*sequence
= as_a
<rtx_sequence
*> (PATTERN (trial
));
2743 /* If this is the `true' thread, we will want to follow the jump,
2744 so we can only do this if we have taken everything up to here. */
2745 if (thread_if_true
&& trial
== new_thread
)
2748 = steal_delay_list_from_target (insn
, condition
, sequence
,
2749 delay_list
, &set
, &needed
,
2750 &opposite_needed
, slots_to_fill
,
2751 pslots_filled
, &must_annul
,
2753 /* If we owned the thread and are told that it branched
2754 elsewhere, make sure we own the thread at the new location. */
2755 if (own_thread
&& trial
!= new_thread
)
2756 own_thread
= own_thread_p (new_thread
, new_thread
, 0);
2758 else if (! thread_if_true
)
2760 = steal_delay_list_from_fallthrough (insn
, condition
,
2762 delay_list
, &set
, &needed
,
2763 &opposite_needed
, slots_to_fill
,
2764 pslots_filled
, &must_annul
);
2767 /* If we haven't found anything for this delay slot and it is very
2768 likely that the branch will be taken, see if the insn at our target
2769 increments or decrements a register with an increment that does not
2770 depend on the destination register. If so, try to place the opposite
2771 arithmetic insn after the jump insn and put the arithmetic insn in the
2772 delay slot. If we can't do this, return. */
2773 if (delay_list
== 0 && likely
2774 && new_thread
&& !ANY_RETURN_P (new_thread
)
2775 && NONJUMP_INSN_P (new_thread
)
2776 && !RTX_FRAME_RELATED_P (new_thread
)
2777 && GET_CODE (PATTERN (new_thread
)) != ASM_INPUT
2778 && asm_noperands (PATTERN (new_thread
)) < 0)
2780 rtx pat
= PATTERN (new_thread
);
2784 /* We know "new_thread" is an insn due to NONJUMP_INSN_P (new_thread)
2786 trial
= as_a
<rtx_insn
*> (new_thread
);
2787 pat
= PATTERN (trial
);
2789 if (!NONJUMP_INSN_P (trial
)
2790 || GET_CODE (pat
) != SET
2791 || ! eligible_for_delay (insn
, 0, trial
, flags
)
2792 || can_throw_internal (trial
))
2795 dest
= SET_DEST (pat
), src
= SET_SRC (pat
);
2796 if ((GET_CODE (src
) == PLUS
|| GET_CODE (src
) == MINUS
)
2797 && rtx_equal_p (XEXP (src
, 0), dest
)
2798 && (!FLOAT_MODE_P (GET_MODE (src
))
2799 || flag_unsafe_math_optimizations
)
2800 && ! reg_overlap_mentioned_p (dest
, XEXP (src
, 1))
2801 && ! side_effects_p (pat
))
2803 rtx other
= XEXP (src
, 1);
2807 /* If this is a constant adjustment, use the same code with
2808 the negated constant. Otherwise, reverse the sense of the
2810 if (CONST_INT_P (other
))
2811 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
), GET_MODE (src
), dest
,
2812 negate_rtx (GET_MODE (src
), other
));
2814 new_arith
= gen_rtx_fmt_ee (GET_CODE (src
) == PLUS
? MINUS
: PLUS
,
2815 GET_MODE (src
), dest
, other
);
2817 ninsn
= emit_insn_after (gen_rtx_SET (VOIDmode
, dest
, new_arith
),
2820 if (recog_memoized (ninsn
) < 0
2821 || (extract_insn (ninsn
),
2822 !constrain_operands (1, get_preferred_alternatives (ninsn
))))
2824 delete_related_insns (ninsn
);
2830 update_block (trial
, thread
);
2831 if (trial
== thread
)
2833 thread
= next_active_insn (thread
);
2834 if (new_thread
== trial
)
2835 new_thread
= thread
;
2837 delete_related_insns (trial
);
2840 new_thread
= next_active_insn (trial
);
2842 ninsn
= own_thread
? trial
: copy_delay_slot_insn (trial
);
2844 INSN_FROM_TARGET_P (ninsn
) = 1;
2846 delay_list
= add_to_delay_list (ninsn
, NULL
);
2851 if (delay_list
&& must_annul
)
2852 INSN_ANNULLED_BRANCH_P (insn
) = 1;
2854 /* If we are to branch into the middle of this thread, find an appropriate
2855 label or make a new one if none, and redirect INSN to it. If we hit the
2856 end of the function, use the end-of-function label. */
2857 if (new_thread
!= thread
)
2860 bool crossing
= false;
2862 gcc_assert (thread_if_true
);
2864 if (new_thread
&& simplejump_or_return_p (new_thread
)
2865 && redirect_with_delay_list_safe_p (insn
,
2866 JUMP_LABEL (new_thread
),
2868 new_thread
= follow_jumps (JUMP_LABEL (new_thread
), insn
,
2871 if (ANY_RETURN_P (new_thread
))
2872 label
= find_end_label (new_thread
);
2873 else if (LABEL_P (new_thread
))
2876 label
= get_label_before (as_a
<rtx_insn
*> (new_thread
),
2881 reorg_redirect_jump (insn
, label
);
2883 CROSSING_JUMP_P (insn
) = 1;
2890 /* Make another attempt to find insns to place in delay slots.
2892 We previously looked for insns located in front of the delay insn
2893 and, for non-jump delay insns, located behind the delay insn.
2895 Here only try to schedule jump insns and try to move insns from either
2896 the target or the following insns into the delay slot. If annulling is
2897 supported, we will be likely to do this. Otherwise, we can do this only
2901 fill_eager_delay_slots (void)
2905 int num_unfilled_slots
= unfilled_slots_next
- unfilled_slots_base
;
2907 for (i
= 0; i
< num_unfilled_slots
; i
++)
2910 rtx target_label
, insn_at_target
;
2911 rtx_insn
*fallthrough_insn
;
2912 rtx_insn_list
*delay_list
= 0;
2914 int own_fallthrough
;
2915 int prediction
, slots_to_fill
, slots_filled
;
2917 insn
= unfilled_slots_base
[i
];
2921 || ! (condjump_p (insn
) || condjump_in_parallel_p (insn
)))
2924 slots_to_fill
= num_delay_slots (insn
);
2925 /* Some machine description have defined instructions to have
2926 delay slots only in certain circumstances which may depend on
2927 nearby insns (which change due to reorg's actions).
2929 For example, the PA port normally has delay slots for unconditional
2932 However, the PA port claims such jumps do not have a delay slot
2933 if they are immediate successors of certain CALL_INSNs. This
2934 allows the port to favor filling the delay slot of the call with
2935 the unconditional jump. */
2936 if (slots_to_fill
== 0)
2940 target_label
= JUMP_LABEL (insn
);
2941 condition
= get_branch_condition (insn
, target_label
);
2946 /* Get the next active fallthrough and target insns and see if we own
2947 them. Then see whether the branch is likely true. We don't need
2948 to do a lot of this for unconditional branches. */
2950 insn_at_target
= first_active_target_insn (target_label
);
2951 own_target
= own_thread_p (target_label
, target_label
, 0);
2953 if (condition
== const_true_rtx
)
2955 own_fallthrough
= 0;
2956 fallthrough_insn
= 0;
2961 fallthrough_insn
= next_active_insn (insn
);
2962 own_fallthrough
= own_thread_p (NEXT_INSN (insn
), NULL_RTX
, 1);
2963 prediction
= mostly_true_jump (insn
);
2966 /* If this insn is expected to branch, first try to get insns from our
2967 target, then our fallthrough insns. If it is not expected to branch,
2968 try the other order. */
2973 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
2974 fallthrough_insn
, prediction
== 2, 1,
2976 slots_to_fill
, &slots_filled
, delay_list
);
2978 if (delay_list
== 0 && own_fallthrough
)
2980 /* Even though we didn't find anything for delay slots,
2981 we might have found a redundant insn which we deleted
2982 from the thread that was filled. So we have to recompute
2983 the next insn at the target. */
2984 target_label
= JUMP_LABEL (insn
);
2985 insn_at_target
= first_active_target_insn (target_label
);
2988 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
2989 insn_at_target
, 0, 0,
2991 slots_to_fill
, &slots_filled
,
2997 if (own_fallthrough
)
2999 = fill_slots_from_thread (insn
, condition
, fallthrough_insn
,
3000 insn_at_target
, 0, 0,
3002 slots_to_fill
, &slots_filled
,
3005 if (delay_list
== 0)
3007 = fill_slots_from_thread (insn
, condition
, insn_at_target
,
3008 next_active_insn (insn
), 0, 1,
3010 slots_to_fill
, &slots_filled
,
3015 unfilled_slots_base
[i
]
3016 = emit_delay_sequence (insn
, delay_list
, slots_filled
);
3018 if (slots_to_fill
== slots_filled
)
3019 unfilled_slots_base
[i
] = 0;
3021 note_delay_statistics (slots_filled
, 1);
3025 static void delete_computation (rtx insn
);
3027 /* Recursively delete prior insns that compute the value (used only by INSN
3028 which the caller is deleting) stored in the register mentioned by NOTE
3029 which is a REG_DEAD note associated with INSN. */
3032 delete_prior_computation (rtx note
, rtx insn
)
3035 rtx reg
= XEXP (note
, 0);
3037 for (our_prev
= prev_nonnote_insn (insn
);
3038 our_prev
&& (NONJUMP_INSN_P (our_prev
)
3039 || CALL_P (our_prev
));
3040 our_prev
= prev_nonnote_insn (our_prev
))
3042 rtx pat
= PATTERN (our_prev
);
3044 /* If we reach a CALL which is not calling a const function
3045 or the callee pops the arguments, then give up. */
3046 if (CALL_P (our_prev
)
3047 && (! RTL_CONST_CALL_P (our_prev
)
3048 || GET_CODE (pat
) != SET
|| GET_CODE (SET_SRC (pat
)) != CALL
))
3051 /* If we reach a SEQUENCE, it is too complex to try to
3052 do anything with it, so give up. We can be run during
3053 and after reorg, so SEQUENCE rtl can legitimately show
3055 if (GET_CODE (pat
) == SEQUENCE
)
3058 if (GET_CODE (pat
) == USE
3059 && NONJUMP_INSN_P (XEXP (pat
, 0)))
3060 /* reorg creates USEs that look like this. We leave them
3061 alone because reorg needs them for its own purposes. */
3064 if (reg_set_p (reg
, pat
))
3066 if (side_effects_p (pat
) && !CALL_P (our_prev
))
3069 if (GET_CODE (pat
) == PARALLEL
)
3071 /* If we find a SET of something else, we can't
3076 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3078 rtx part
= XVECEXP (pat
, 0, i
);
3080 if (GET_CODE (part
) == SET
3081 && SET_DEST (part
) != reg
)
3085 if (i
== XVECLEN (pat
, 0))
3086 delete_computation (our_prev
);
3088 else if (GET_CODE (pat
) == SET
3089 && REG_P (SET_DEST (pat
)))
3091 int dest_regno
= REGNO (SET_DEST (pat
));
3092 int dest_endregno
= END_REGNO (SET_DEST (pat
));
3093 int regno
= REGNO (reg
);
3094 int endregno
= END_REGNO (reg
);
3096 if (dest_regno
>= regno
3097 && dest_endregno
<= endregno
)
3098 delete_computation (our_prev
);
3100 /* We may have a multi-word hard register and some, but not
3101 all, of the words of the register are needed in subsequent
3102 insns. Write REG_UNUSED notes for those parts that were not
3104 else if (dest_regno
<= regno
3105 && dest_endregno
>= endregno
)
3109 add_reg_note (our_prev
, REG_UNUSED
, reg
);
3111 for (i
= dest_regno
; i
< dest_endregno
; i
++)
3112 if (! find_regno_note (our_prev
, REG_UNUSED
, i
))
3115 if (i
== dest_endregno
)
3116 delete_computation (our_prev
);
3123 /* If PAT references the register that dies here, it is an
3124 additional use. Hence any prior SET isn't dead. However, this
3125 insn becomes the new place for the REG_DEAD note. */
3126 if (reg_overlap_mentioned_p (reg
, pat
))
3128 XEXP (note
, 1) = REG_NOTES (our_prev
);
3129 REG_NOTES (our_prev
) = note
;
3135 /* Delete INSN and recursively delete insns that compute values used only
3136 by INSN. This uses the REG_DEAD notes computed during flow analysis.
3138 Look at all our REG_DEAD notes. If a previous insn does nothing other
3139 than set a register that dies in this insn, we can delete that insn
3142 On machines with CC0, if CC0 is used in this insn, we may be able to
3143 delete the insn that set it. */
3146 delete_computation (rtx insn
)
3150 if (HAVE_cc0
&& reg_referenced_p (cc0_rtx
, PATTERN (insn
)))
3152 rtx prev
= prev_nonnote_insn (insn
);
3153 /* We assume that at this stage
3154 CC's are always set explicitly
3155 and always immediately before the jump that
3156 will use them. So if the previous insn
3157 exists to set the CC's, delete it
3158 (unless it performs auto-increments, etc.). */
3159 if (prev
&& NONJUMP_INSN_P (prev
)
3160 && sets_cc0_p (PATTERN (prev
)))
3162 if (sets_cc0_p (PATTERN (prev
)) > 0
3163 && ! side_effects_p (PATTERN (prev
)))
3164 delete_computation (prev
);
3166 /* Otherwise, show that cc0 won't be used. */
3167 add_reg_note (prev
, REG_UNUSED
, cc0_rtx
);
3171 for (note
= REG_NOTES (insn
); note
; note
= next
)
3173 next
= XEXP (note
, 1);
3175 if (REG_NOTE_KIND (note
) != REG_DEAD
3176 /* Verify that the REG_NOTE is legitimate. */
3177 || !REG_P (XEXP (note
, 0)))
3180 delete_prior_computation (note
, insn
);
3183 delete_related_insns (insn
);
3186 /* If all INSN does is set the pc, delete it,
3187 and delete the insn that set the condition codes for it
3188 if that's what the previous thing was. */
3191 delete_jump (rtx_insn
*insn
)
3193 rtx set
= single_set (insn
);
3195 if (set
&& GET_CODE (SET_DEST (set
)) == PC
)
3196 delete_computation (insn
);
3200 label_before_next_insn (rtx x
, rtx scan_limit
)
3202 rtx_insn
*insn
= next_active_insn (x
);
3205 insn
= PREV_INSN (insn
);
3206 if (insn
== scan_limit
|| insn
== NULL_RTX
)
3214 /* Return TRUE if there is a NOTE_INSN_SWITCH_TEXT_SECTIONS note in between
3218 switch_text_sections_between_p (const rtx_insn
*beg
, const rtx_insn
*end
)
3221 for (p
= beg
; p
!= end
; p
= NEXT_INSN (p
))
3222 if (NOTE_P (p
) && NOTE_KIND (p
) == NOTE_INSN_SWITCH_TEXT_SECTIONS
)
3228 /* Once we have tried two ways to fill a delay slot, make a pass over the
3229 code to try to improve the results and to do such things as more jump
3233 relax_delay_slots (rtx_insn
*first
)
3235 rtx_insn
*insn
, *next
;
3238 rtx_insn
*delay_insn
;
3241 /* Look at every JUMP_INSN and see if we can improve it. */
3242 for (insn
= first
; insn
; insn
= next
)
3247 next
= next_active_insn (insn
);
3249 /* If this is a jump insn, see if it now jumps to a jump, jumps to
3250 the next insn, or jumps to a label that is not the last of a
3251 group of consecutive labels. */
3253 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3254 && !ANY_RETURN_P (target_label
= JUMP_LABEL (insn
)))
3257 = skip_consecutive_labels (follow_jumps (target_label
, insn
,
3259 if (ANY_RETURN_P (target_label
))
3260 target_label
= find_end_label (target_label
);
3262 if (target_label
&& next_active_insn (target_label
) == next
3263 && ! condjump_in_parallel_p (insn
)
3264 && ! (next
&& switch_text_sections_between_p (insn
, next
)))
3270 if (target_label
&& target_label
!= JUMP_LABEL (insn
))
3272 reorg_redirect_jump (insn
, target_label
);
3274 CROSSING_JUMP_P (insn
) = 1;
3277 /* See if this jump conditionally branches around an unconditional
3278 jump. If so, invert this jump and point it to the target of the
3279 second jump. Check if it's possible on the target. */
3280 if (next
&& simplejump_or_return_p (next
)
3281 && any_condjump_p (insn
)
3283 && next_active_insn (target_label
) == next_active_insn (next
)
3284 && no_labels_between_p (insn
, next
)
3285 && targetm
.can_follow_jump (insn
, next
))
3287 rtx label
= JUMP_LABEL (next
);
3289 /* Be careful how we do this to avoid deleting code or
3290 labels that are momentarily dead. See similar optimization
3293 We also need to ensure we properly handle the case when
3294 invert_jump fails. */
3296 ++LABEL_NUSES (target_label
);
3297 if (!ANY_RETURN_P (label
))
3298 ++LABEL_NUSES (label
);
3300 if (invert_jump (insn
, label
, 1))
3302 delete_related_insns (next
);
3306 if (!ANY_RETURN_P (label
))
3307 --LABEL_NUSES (label
);
3309 if (--LABEL_NUSES (target_label
) == 0)
3310 delete_related_insns (target_label
);
3316 /* If this is an unconditional jump and the previous insn is a
3317 conditional jump, try reversing the condition of the previous
3318 insn and swapping our targets. The next pass might be able to
3321 Don't do this if we expect the conditional branch to be true, because
3322 we would then be making the more common case longer. */
3324 if (simplejump_or_return_p (insn
)
3325 && (other
= prev_active_insn (insn
)) != 0
3326 && any_condjump_p (other
)
3327 && no_labels_between_p (other
, insn
)
3328 && 0 > mostly_true_jump (other
))
3330 rtx other_target
= JUMP_LABEL (other
);
3331 target_label
= JUMP_LABEL (insn
);
3333 if (invert_jump (other
, target_label
, 0))
3334 reorg_redirect_jump (insn
, other_target
);
3337 /* Now look only at cases where we have a filled delay slot. */
3338 if (!NONJUMP_INSN_P (insn
) || GET_CODE (PATTERN (insn
)) != SEQUENCE
)
3341 pat
= as_a
<rtx_sequence
*> (PATTERN (insn
));
3342 delay_insn
= pat
->insn (0);
3344 /* See if the first insn in the delay slot is redundant with some
3345 previous insn. Remove it from the delay slot if so; then set up
3346 to reprocess this insn. */
3347 if (redundant_insn (pat
->insn (1), delay_insn
, 0))
3349 update_block (pat
->insn (1), insn
);
3350 delete_from_delay_slot (pat
->insn (1));
3351 next
= prev_active_insn (next
);
3355 /* See if we have a RETURN insn with a filled delay slot followed
3356 by a RETURN insn with an unfilled a delay slot. If so, we can delete
3357 the first RETURN (but not its delay insn). This gives the same
3358 effect in fewer instructions.
3360 Only do so if optimizing for size since this results in slower, but
3362 if (optimize_function_for_size_p (cfun
)
3363 && ANY_RETURN_P (PATTERN (delay_insn
))
3366 && PATTERN (next
) == PATTERN (delay_insn
))
3371 /* Delete the RETURN and just execute the delay list insns.
3373 We do this by deleting the INSN containing the SEQUENCE, then
3374 re-emitting the insns separately, and then deleting the RETURN.
3375 This allows the count of the jump target to be properly
3378 Note that we need to change the INSN_UID of the re-emitted insns
3379 since it is used to hash the insns for mark_target_live_regs and
3380 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3382 Clear the from target bit, since these insns are no longer
3384 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3385 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3387 trial
= PREV_INSN (insn
);
3388 delete_related_insns (insn
);
3389 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3390 add_insn_after (delay_insn
, trial
, NULL
);
3392 for (i
= 1; i
< pat
->len (); i
++)
3393 after
= emit_copy_of_insn_after (pat
->insn (i
), after
);
3394 delete_scheduled_jump (delay_insn
);
3398 /* Now look only at the cases where we have a filled JUMP_INSN. */
3399 if (!JUMP_P (delay_insn
)
3400 || !(condjump_p (delay_insn
) || condjump_in_parallel_p (delay_insn
)))
3403 target_label
= JUMP_LABEL (delay_insn
);
3404 if (target_label
&& ANY_RETURN_P (target_label
))
3407 /* If this jump goes to another unconditional jump, thread it, but
3408 don't convert a jump into a RETURN here. */
3409 trial
= skip_consecutive_labels (follow_jumps (target_label
, delay_insn
,
3411 if (ANY_RETURN_P (trial
))
3412 trial
= find_end_label (trial
);
3414 if (trial
&& trial
!= target_label
3415 && redirect_with_delay_slots_safe_p (delay_insn
, trial
, insn
))
3417 reorg_redirect_jump (delay_insn
, trial
);
3418 target_label
= trial
;
3420 CROSSING_JUMP_P (insn
) = 1;
3423 /* If the first insn at TARGET_LABEL is redundant with a previous
3424 insn, redirect the jump to the following insn and process again.
3425 We use next_real_insn instead of next_active_insn so we
3426 don't skip USE-markers, or we'll end up with incorrect
3428 trial
= next_real_insn (target_label
);
3429 if (trial
&& GET_CODE (PATTERN (trial
)) != SEQUENCE
3430 && redundant_insn (trial
, insn
, 0)
3431 && ! can_throw_internal (trial
))
3433 /* Figure out where to emit the special USE insn so we don't
3434 later incorrectly compute register live/death info. */
3435 rtx_insn
*tmp
= next_active_insn (trial
);
3437 tmp
= find_end_label (simple_return_rtx
);
3441 /* Insert the special USE insn and update dataflow info.
3442 We know "trial" is an insn here as it is the output of
3443 next_real_insn () above. */
3444 update_block (as_a
<rtx_insn
*> (trial
), tmp
);
3446 /* Now emit a label before the special USE insn, and
3447 redirect our jump to the new label. */
3448 target_label
= get_label_before (PREV_INSN (tmp
), target_label
);
3449 reorg_redirect_jump (delay_insn
, target_label
);
3455 /* Similarly, if it is an unconditional jump with one insn in its
3456 delay list and that insn is redundant, thread the jump. */
3457 rtx_sequence
*trial_seq
=
3458 trial
? dyn_cast
<rtx_sequence
*> (PATTERN (trial
)) : NULL
;
3460 && trial_seq
->len () == 2
3461 && JUMP_P (trial_seq
->insn (0))
3462 && simplejump_or_return_p (trial_seq
->insn (0))
3463 && redundant_insn (trial_seq
->insn (1), insn
, 0))
3465 target_label
= JUMP_LABEL (trial_seq
->insn (0));
3466 if (ANY_RETURN_P (target_label
))
3467 target_label
= find_end_label (target_label
);
3470 && redirect_with_delay_slots_safe_p (delay_insn
, target_label
,
3473 update_block (trial_seq
->insn (1), insn
);
3474 reorg_redirect_jump (delay_insn
, target_label
);
3480 /* See if we have a simple (conditional) jump that is useless. */
3481 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3482 && ! condjump_in_parallel_p (delay_insn
)
3483 && prev_active_insn (target_label
) == insn
3484 && ! BARRIER_P (prev_nonnote_insn (target_label
))
3486 /* If the last insn in the delay slot sets CC0 for some insn,
3487 various code assumes that it is in a delay slot. We could
3488 put it back where it belonged and delete the register notes,
3489 but it doesn't seem worthwhile in this uncommon case. */
3490 && ! find_reg_note (XVECEXP (pat
, 0, XVECLEN (pat
, 0) - 1),
3491 REG_CC_USER
, NULL_RTX
)
3498 /* All this insn does is execute its delay list and jump to the
3499 following insn. So delete the jump and just execute the delay
3502 We do this by deleting the INSN containing the SEQUENCE, then
3503 re-emitting the insns separately, and then deleting the jump.
3504 This allows the count of the jump target to be properly
3507 Note that we need to change the INSN_UID of the re-emitted insns
3508 since it is used to hash the insns for mark_target_live_regs and
3509 the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3511 Clear the from target bit, since these insns are no longer
3513 for (i
= 0; i
< XVECLEN (pat
, 0); i
++)
3514 INSN_FROM_TARGET_P (XVECEXP (pat
, 0, i
)) = 0;
3516 trial
= PREV_INSN (insn
);
3517 delete_related_insns (insn
);
3518 gcc_assert (GET_CODE (pat
) == SEQUENCE
);
3519 add_insn_after (delay_insn
, trial
, NULL
);
3521 for (i
= 1; i
< pat
->len (); i
++)
3522 after
= emit_copy_of_insn_after (pat
->insn (i
), after
);
3523 delete_scheduled_jump (delay_insn
);
3527 /* See if this is an unconditional jump around a single insn which is
3528 identical to the one in its delay slot. In this case, we can just
3529 delete the branch and the insn in its delay slot. */
3530 if (next
&& NONJUMP_INSN_P (next
)
3531 && label_before_next_insn (next
, insn
) == target_label
3532 && simplejump_p (insn
)
3533 && XVECLEN (pat
, 0) == 2
3534 && rtx_equal_p (PATTERN (next
), PATTERN (pat
->insn (1))))
3536 delete_related_insns (insn
);
3540 /* See if this jump (with its delay slots) conditionally branches
3541 around an unconditional jump (without delay slots). If so, invert
3542 this jump and point it to the target of the second jump. We cannot
3543 do this for annulled jumps, though. Again, don't convert a jump to
3545 if (! INSN_ANNULLED_BRANCH_P (delay_insn
)
3546 && any_condjump_p (delay_insn
)
3547 && next
&& simplejump_or_return_p (next
)
3548 && next_active_insn (target_label
) == next_active_insn (next
)
3549 && no_labels_between_p (insn
, next
))
3551 rtx label
= JUMP_LABEL (next
);
3552 rtx old_label
= JUMP_LABEL (delay_insn
);
3554 if (ANY_RETURN_P (label
))
3555 label
= find_end_label (label
);
3557 /* find_end_label can generate a new label. Check this first. */
3559 && no_labels_between_p (insn
, next
)
3560 && redirect_with_delay_slots_safe_p (delay_insn
, label
, insn
))
3562 /* Be careful how we do this to avoid deleting code or labels
3563 that are momentarily dead. See similar optimization in
3566 ++LABEL_NUSES (old_label
);
3568 if (invert_jump (delay_insn
, label
, 1))
3572 /* Must update the INSN_FROM_TARGET_P bits now that
3573 the branch is reversed, so that mark_target_live_regs
3574 will handle the delay slot insn correctly. */
3575 for (i
= 1; i
< XVECLEN (PATTERN (insn
), 0); i
++)
3577 rtx slot
= XVECEXP (PATTERN (insn
), 0, i
);
3578 INSN_FROM_TARGET_P (slot
) = ! INSN_FROM_TARGET_P (slot
);
3581 delete_related_insns (next
);
3585 if (old_label
&& --LABEL_NUSES (old_label
) == 0)
3586 delete_related_insns (old_label
);
3591 /* If we own the thread opposite the way this insn branches, see if we
3592 can merge its delay slots with following insns. */
3593 if (INSN_FROM_TARGET_P (pat
->insn (1))
3594 && own_thread_p (NEXT_INSN (insn
), 0, 1))
3595 try_merge_delay_insns (insn
, next
);
3596 else if (! INSN_FROM_TARGET_P (pat
->insn (1))
3597 && own_thread_p (target_label
, target_label
, 0))
3598 try_merge_delay_insns (insn
, next_active_insn (target_label
));
3600 /* If we get here, we haven't deleted INSN. But we may have deleted
3601 NEXT, so recompute it. */
3602 next
= next_active_insn (insn
);
3607 /* Look for filled jumps to the end of function label. We can try to convert
3608 them into RETURN insns if the insns in the delay slot are valid for the
3612 make_return_insns (rtx_insn
*first
)
3615 rtx_insn
*jump_insn
;
3616 rtx real_return_label
= function_return_label
;
3617 rtx real_simple_return_label
= function_simple_return_label
;
3620 /* See if there is a RETURN insn in the function other than the one we
3621 made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3622 into a RETURN to jump to it. */
3623 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3624 if (JUMP_P (insn
) && ANY_RETURN_P (PATTERN (insn
)))
3626 rtx t
= get_label_before (insn
, NULL_RTX
);
3627 if (PATTERN (insn
) == ret_rtx
)
3628 real_return_label
= t
;
3630 real_simple_return_label
= t
;
3634 /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3635 was equal to END_OF_FUNCTION_LABEL. */
3636 if (real_return_label
)
3637 LABEL_NUSES (real_return_label
)++;
3638 if (real_simple_return_label
)
3639 LABEL_NUSES (real_simple_return_label
)++;
3641 /* Clear the list of insns to fill so we can use it. */
3642 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3644 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3647 rtx kind
, real_label
;
3649 /* Only look at filled JUMP_INSNs that go to the end of function
3651 if (!NONJUMP_INSN_P (insn
))
3654 if (GET_CODE (PATTERN (insn
)) != SEQUENCE
)
3657 rtx_sequence
*pat
= as_a
<rtx_sequence
*> (PATTERN (insn
));
3659 if (!jump_to_label_p (pat
->insn (0)))
3662 if (JUMP_LABEL (pat
->insn (0)) == function_return_label
)
3665 real_label
= real_return_label
;
3667 else if (JUMP_LABEL (pat
->insn (0)) == function_simple_return_label
)
3669 kind
= simple_return_rtx
;
3670 real_label
= real_simple_return_label
;
3675 jump_insn
= pat
->insn (0);
3677 /* If we can't make the jump into a RETURN, try to redirect it to the best
3678 RETURN and go on to the next insn. */
3679 if (!reorg_redirect_jump (jump_insn
, kind
))
3681 /* Make sure redirecting the jump will not invalidate the delay
3683 if (redirect_with_delay_slots_safe_p (jump_insn
, real_label
, insn
))
3684 reorg_redirect_jump (jump_insn
, real_label
);
3688 /* See if this RETURN can accept the insns current in its delay slot.
3689 It can if it has more or an equal number of slots and the contents
3690 of each is valid. */
3692 flags
= get_jump_flags (jump_insn
, JUMP_LABEL (jump_insn
));
3693 slots
= num_delay_slots (jump_insn
);
3694 if (slots
>= XVECLEN (pat
, 0) - 1)
3696 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3698 #ifdef ANNUL_IFFALSE_SLOTS
3699 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3700 && INSN_FROM_TARGET_P (pat
->insn (i
)))
3701 ? eligible_for_annul_false (jump_insn
, i
- 1,
3702 pat
->insn (i
), flags
) :
3704 #ifdef ANNUL_IFTRUE_SLOTS
3705 (INSN_ANNULLED_BRANCH_P (jump_insn
)
3706 && ! INSN_FROM_TARGET_P (pat
->insn (i
)))
3707 ? eligible_for_annul_true (jump_insn
, i
- 1,
3708 pat
->insn (i
), flags
) :
3710 eligible_for_delay (jump_insn
, i
- 1,
3711 pat
->insn (i
), flags
)))
3717 if (i
== XVECLEN (pat
, 0))
3720 /* We have to do something with this insn. If it is an unconditional
3721 RETURN, delete the SEQUENCE and output the individual insns,
3722 followed by the RETURN. Then set things up so we try to find
3723 insns for its delay slots, if it needs some. */
3724 if (ANY_RETURN_P (PATTERN (jump_insn
)))
3726 rtx_insn
*prev
= PREV_INSN (insn
);
3728 delete_related_insns (insn
);
3729 for (i
= 1; i
< XVECLEN (pat
, 0); i
++)
3730 prev
= emit_insn_after (PATTERN (XVECEXP (pat
, 0, i
)), prev
);
3732 insn
= emit_jump_insn_after (PATTERN (jump_insn
), prev
);
3733 emit_barrier_after (insn
);
3736 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3739 /* It is probably more efficient to keep this with its current
3740 delay slot as a branch to a RETURN. */
3741 reorg_redirect_jump (jump_insn
, real_label
);
3744 /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3745 new delay slots we have created. */
3746 if (real_return_label
!= NULL_RTX
&& --LABEL_NUSES (real_return_label
) == 0)
3747 delete_related_insns (real_return_label
);
3748 if (real_simple_return_label
!= NULL_RTX
3749 && --LABEL_NUSES (real_simple_return_label
) == 0)
3750 delete_related_insns (real_simple_return_label
);
3752 fill_simple_delay_slots (1);
3753 fill_simple_delay_slots (0);
3756 /* Try to find insns to place in delay slots. */
3759 dbr_schedule (rtx_insn
*first
)
3761 rtx_insn
*insn
, *next
, *epilogue_insn
= 0;
3763 bool need_return_insns
;
3765 /* If the current function has no insns other than the prologue and
3766 epilogue, then do not try to fill any delay slots. */
3767 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
3770 /* Find the highest INSN_UID and allocate and initialize our map from
3771 INSN_UID's to position in code. */
3772 for (max_uid
= 0, insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3774 if (INSN_UID (insn
) > max_uid
)
3775 max_uid
= INSN_UID (insn
);
3777 && NOTE_KIND (insn
) == NOTE_INSN_EPILOGUE_BEG
)
3778 epilogue_insn
= insn
;
3781 uid_to_ruid
= XNEWVEC (int, max_uid
+ 1);
3782 for (i
= 0, insn
= first
; insn
; i
++, insn
= NEXT_INSN (insn
))
3783 uid_to_ruid
[INSN_UID (insn
)] = i
;
3785 /* Initialize the list of insns that need filling. */
3786 if (unfilled_firstobj
== 0)
3788 gcc_obstack_init (&unfilled_slots_obstack
);
3789 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3792 for (insn
= next_active_insn (first
); insn
; insn
= next_active_insn (insn
))
3796 /* Skip vector tables. We can't get attributes for them. */
3797 if (JUMP_TABLE_DATA_P (insn
))
3801 INSN_ANNULLED_BRANCH_P (insn
) = 0;
3802 INSN_FROM_TARGET_P (insn
) = 0;
3804 if (num_delay_slots (insn
) > 0)
3805 obstack_ptr_grow (&unfilled_slots_obstack
, insn
);
3807 /* Ensure all jumps go to the last of a set of consecutive labels. */
3809 && (condjump_p (insn
) || condjump_in_parallel_p (insn
))
3810 && !ANY_RETURN_P (JUMP_LABEL (insn
))
3811 && ((target
= skip_consecutive_labels (JUMP_LABEL (insn
)))
3812 != JUMP_LABEL (insn
)))
3813 redirect_jump (insn
, target
, 1);
3816 init_resource_info (epilogue_insn
);
3818 /* Show we haven't computed an end-of-function label yet. */
3819 function_return_label
= function_simple_return_label
= NULL
;
3821 /* Initialize the statistics for this function. */
3822 memset (num_insns_needing_delays
, 0, sizeof num_insns_needing_delays
);
3823 memset (num_filled_delays
, 0, sizeof num_filled_delays
);
3825 /* Now do the delay slot filling. Try everything twice in case earlier
3826 changes make more slots fillable. */
3828 for (reorg_pass_number
= 0;
3829 reorg_pass_number
< MAX_REORG_PASSES
;
3830 reorg_pass_number
++)
3832 fill_simple_delay_slots (1);
3833 fill_simple_delay_slots (0);
3834 fill_eager_delay_slots ();
3835 relax_delay_slots (first
);
3838 /* If we made an end of function label, indicate that it is now
3839 safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3840 If it is now unused, delete it. */
3841 if (function_return_label
&& --LABEL_NUSES (function_return_label
) == 0)
3842 delete_related_insns (function_return_label
);
3843 if (function_simple_return_label
3844 && --LABEL_NUSES (function_simple_return_label
) == 0)
3845 delete_related_insns (function_simple_return_label
);
3847 need_return_insns
= false;
3849 need_return_insns
|= HAVE_return
&& function_return_label
!= 0;
3851 #ifdef HAVE_simple_return
3852 need_return_insns
|= HAVE_simple_return
&& function_simple_return_label
!= 0;
3854 if (need_return_insns
)
3855 make_return_insns (first
);
3857 /* Delete any USE insns made by update_block; subsequent passes don't need
3858 them or know how to deal with them. */
3859 for (insn
= first
; insn
; insn
= next
)
3861 next
= NEXT_INSN (insn
);
3863 if (NONJUMP_INSN_P (insn
) && GET_CODE (PATTERN (insn
)) == USE
3864 && INSN_P (XEXP (PATTERN (insn
), 0)))
3865 next
= delete_related_insns (insn
);
3868 obstack_free (&unfilled_slots_obstack
, unfilled_firstobj
);
3870 /* It is not clear why the line below is needed, but it does seem to be. */
3871 unfilled_firstobj
= XOBNEWVAR (&unfilled_slots_obstack
, rtx
, 0);
3875 int i
, j
, need_comma
;
3876 int total_delay_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3877 int total_annul_slots
[MAX_DELAY_HISTOGRAM
+ 1];
3879 for (reorg_pass_number
= 0;
3880 reorg_pass_number
< MAX_REORG_PASSES
;
3881 reorg_pass_number
++)
3883 fprintf (dump_file
, ";; Reorg pass #%d:\n", reorg_pass_number
+ 1);
3884 for (i
= 0; i
< NUM_REORG_FUNCTIONS
; i
++)
3887 fprintf (dump_file
, ";; Reorg function #%d\n", i
);
3889 fprintf (dump_file
, ";; %d insns needing delay slots\n;; ",
3890 num_insns_needing_delays
[i
][reorg_pass_number
]);
3892 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3893 if (num_filled_delays
[i
][j
][reorg_pass_number
])
3896 fprintf (dump_file
, ", ");
3898 fprintf (dump_file
, "%d got %d delays",
3899 num_filled_delays
[i
][j
][reorg_pass_number
], j
);
3901 fprintf (dump_file
, "\n");
3904 memset (total_delay_slots
, 0, sizeof total_delay_slots
);
3905 memset (total_annul_slots
, 0, sizeof total_annul_slots
);
3906 for (insn
= first
; insn
; insn
= NEXT_INSN (insn
))
3908 if (! insn
->deleted ()
3909 && NONJUMP_INSN_P (insn
)
3910 && GET_CODE (PATTERN (insn
)) != USE
3911 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3913 if (GET_CODE (PATTERN (insn
)) == SEQUENCE
)
3916 j
= XVECLEN (PATTERN (insn
), 0) - 1;
3917 if (j
> MAX_DELAY_HISTOGRAM
)
3918 j
= MAX_DELAY_HISTOGRAM
;
3919 control
= XVECEXP (PATTERN (insn
), 0, 0);
3920 if (JUMP_P (control
) && INSN_ANNULLED_BRANCH_P (control
))
3921 total_annul_slots
[j
]++;
3923 total_delay_slots
[j
]++;
3925 else if (num_delay_slots (insn
) > 0)
3926 total_delay_slots
[0]++;
3929 fprintf (dump_file
, ";; Reorg totals: ");
3931 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3933 if (total_delay_slots
[j
])
3936 fprintf (dump_file
, ", ");
3938 fprintf (dump_file
, "%d got %d delays", total_delay_slots
[j
], j
);
3941 fprintf (dump_file
, "\n");
3942 #if defined (ANNUL_IFTRUE_SLOTS) || defined (ANNUL_IFFALSE_SLOTS)
3943 fprintf (dump_file
, ";; Reorg annuls: ");
3945 for (j
= 0; j
< MAX_DELAY_HISTOGRAM
+ 1; j
++)
3947 if (total_annul_slots
[j
])
3950 fprintf (dump_file
, ", ");
3952 fprintf (dump_file
, "%d got %d delays", total_annul_slots
[j
], j
);
3955 fprintf (dump_file
, "\n");
3957 fprintf (dump_file
, "\n");
3960 if (!sibling_labels
.is_empty ())
3962 update_alignments (sibling_labels
);
3963 sibling_labels
.release ();
3966 free_resource_info ();
3968 crtl
->dbr_scheduled_p
= true;
3970 #endif /* DELAY_SLOTS */
3972 /* Run delay slot optimization. */
3974 rest_of_handle_delay_slots (void)
3977 dbr_schedule (get_insns ());
3984 const pass_data pass_data_delay_slots
=
3986 RTL_PASS
, /* type */
3988 OPTGROUP_NONE
, /* optinfo_flags */
3989 TV_DBR_SCHED
, /* tv_id */
3990 0, /* properties_required */
3991 0, /* properties_provided */
3992 0, /* properties_destroyed */
3993 0, /* todo_flags_start */
3994 0, /* todo_flags_finish */
3997 class pass_delay_slots
: public rtl_opt_pass
4000 pass_delay_slots (gcc::context
*ctxt
)
4001 : rtl_opt_pass (pass_data_delay_slots
, ctxt
)
4004 /* opt_pass methods: */
4005 virtual bool gate (function
*);
4006 virtual unsigned int execute (function
*)
4008 return rest_of_handle_delay_slots ();
4011 }; // class pass_delay_slots
4014 pass_delay_slots::gate (function
*)
4017 /* At -O0 dataflow info isn't updated after RA. */
4018 return optimize
> 0 && flag_delayed_branch
&& !crtl
->dbr_scheduled_p
;
4027 make_pass_delay_slots (gcc::context
*ctxt
)
4029 return new pass_delay_slots (ctxt
);
4032 /* Machine dependent reorg pass. */
4036 const pass_data pass_data_machine_reorg
=
4038 RTL_PASS
, /* type */
4040 OPTGROUP_NONE
, /* optinfo_flags */
4041 TV_MACH_DEP
, /* tv_id */
4042 0, /* properties_required */
4043 0, /* properties_provided */
4044 0, /* properties_destroyed */
4045 0, /* todo_flags_start */
4046 0, /* todo_flags_finish */
4049 class pass_machine_reorg
: public rtl_opt_pass
4052 pass_machine_reorg (gcc::context
*ctxt
)
4053 : rtl_opt_pass (pass_data_machine_reorg
, ctxt
)
4056 /* opt_pass methods: */
4057 virtual bool gate (function
*)
4059 return targetm
.machine_dependent_reorg
!= 0;
4062 virtual unsigned int execute (function
*)
4064 targetm
.machine_dependent_reorg ();
4068 }; // class pass_machine_reorg
4073 make_pass_machine_reorg (gcc::context
*ctxt
)
4075 return new pass_machine_reorg (ctxt
);