1	/* Perform instruction reorganizations for delay slot filling.
2	Copyright (C) 1992-2024 Free Software Foundation, Inc.
3	Contributed by Richard Kenner (kenner@vlsi1.ultra.nyu.edu).
4	Hacked by Michael Tiemann (tiemann@cygnus.com).
5
6	This file is part of GCC.
7
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
11	version.
12
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
16	for more details.
17
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/>. */
21
22	/* Instruction reorganization pass.
23
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').
31
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:
36
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.
41
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
46	is taken.
47
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.
54
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.
58
59	Three techniques for filling delay slots have been implemented so far:
60
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.
69
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.
82
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
91	branch. */
92
93	#include "config.h"
94	#include "system.h"
95	#include "coretypes.h"
96	#include "backend.h"
97	#include "target.h"
98	#include "rtl.h"
99	#include "tree.h"
100	#include "predict.h"
101	#include "memmodel.h"
102	#include "tm_p.h"
103	#include "expmed.h"
104	#include "insn-config.h"
105	#include "emit-rtl.h"
106	#include "recog.h"
107	#include "insn-attr.h"
108	#include "resource.h"
109	#include "tree-pass.h"
110
111
112	/* First, some functions that were used before GCC got a control flow graph.
113	These functions are now only used here in reorg.cc, and have therefore
114	been moved here to avoid inadvertent misuse elsewhere in the compiler. */
115
116	/* Return the last label to mark the same position as LABEL. Return LABEL
117	itself if it is null or any return rtx. */
118
119	static rtx
120	skip_consecutive_labels (rtx label_or_return)
121	{
122	rtx_insn *insn;
123
124	if (label_or_return && ANY_RETURN_P (label_or_return))
125	return label_or_return;
126
127	rtx_insn *label = as_a <rtx_insn *> (p: label_or_return);
128
129	/* __builtin_unreachable can create a CODE_LABEL followed by a BARRIER.
130
131	Since reaching the CODE_LABEL is undefined behavior, we can return
132	any code label and we're OK at run time.
133
134	However, if we return a CODE_LABEL which leads to a shrink-wrapped
135	epilogue, but the path does not have a prologue, then we will trip
136	a sanity check in the dwarf2 cfi code which wants to verify that
137	the CFIs are all the same on the traces leading to the epilogue.
138
139	So we explicitly disallow looking through BARRIERS here. */
140	for (insn = label;
141	insn != 0 && !INSN_P (insn) && !BARRIER_P (insn);
142	insn = NEXT_INSN (insn))
143	if (LABEL_P (insn))
144	label = insn;
145
146	return label;
147	}
148
149	/* Insns which have delay slots that have not yet been filled. */
150
151	static struct obstack unfilled_slots_obstack;
152	static rtx *unfilled_firstobj;
153
154	/* Define macros to refer to the first and last slot containing unfilled
155	insns. These are used because the list may move and its address
156	should be recomputed at each use. */
157
158	#define unfilled_slots_base \
159	((rtx_insn **) obstack_base (&unfilled_slots_obstack))
160
161	#define unfilled_slots_next \
162	((rtx_insn **) obstack_next_free (&unfilled_slots_obstack))
163
164	/* Points to the label before the end of the function, or before a
165	return insn. */
166	static rtx_code_label *function_return_label;
167	/* Likewise for a simple_return. */
168	static rtx_code_label *function_simple_return_label;
169
170	/* Mapping between INSN_UID's and position in the code since INSN_UID's do
171	not always monotonically increase. */
172	static int *uid_to_ruid;
173
174	/* Highest valid index in `uid_to_ruid'. */
175	static int max_uid;
176
177	static bool stop_search_p (rtx_insn *, bool);
178	static bool resource_conflicts_p (struct resources *, struct resources *);
179	static bool insn_references_resource_p (rtx, struct resources *, bool);
180	static bool insn_sets_resource_p (rtx, struct resources *, bool);
181	static rtx_code_label *find_end_label (rtx);
182	static rtx_insn *emit_delay_sequence (rtx_insn *, const vec<rtx_insn *> &,
183	int);
184	static void add_to_delay_list (rtx_insn *, vec<rtx_insn *> *);
185	static rtx_insn *delete_from_delay_slot (rtx_insn *);
186	static void delete_scheduled_jump (rtx_insn *);
187	static void note_delay_statistics (int, int);
188	static int get_jump_flags (const rtx_insn *, rtx);
189	static int mostly_true_jump (rtx);
190	static rtx get_branch_condition (const rtx_insn *, rtx);
191	static bool condition_dominates_p (rtx, const rtx_insn *);
192	static bool redirect_with_delay_slots_safe_p (rtx_insn *, rtx, rtx);
193	static bool redirect_with_delay_list_safe_p (rtx_insn *, rtx,
194	const vec<rtx_insn *> &);
195	static bool check_annul_list_true_false (bool, const vec<rtx_insn *> &);
196	static void steal_delay_list_from_target (rtx_insn *, rtx, rtx_sequence *,
197	vec<rtx_insn *> *,
198	struct resources *,
199	struct resources *,
200	struct resources *,
201	int, int *, bool *,
202	rtx *);
203	static void steal_delay_list_from_fallthrough (rtx_insn *, rtx, rtx_sequence *,
204	vec<rtx_insn *> *,
205	struct resources *,
206	struct resources *,
207	struct resources *,
208	int, int *, bool *);
209	static void try_merge_delay_insns (rtx_insn *, rtx_insn *);
210	static rtx_insn *redundant_insn (rtx, rtx_insn *, const vec<rtx_insn *> &);
211	static bool own_thread_p (rtx, rtx, bool);
212	static void update_block (rtx_insn *, rtx_insn *);
213	static bool reorg_redirect_jump (rtx_jump_insn *, rtx);
214	static void update_reg_dead_notes (rtx_insn *, rtx_insn *);
215	static void fix_reg_dead_note (rtx_insn *, rtx);
216	static void update_reg_unused_notes (rtx_insn *, rtx);
217	static void fill_simple_delay_slots (bool);
218	static void fill_slots_from_thread (rtx_jump_insn *, rtx, rtx, rtx,
219	bool, bool, bool, int,
220	int *, vec<rtx_insn *> *);
221	static void fill_eager_delay_slots (void);
222	static void relax_delay_slots (rtx_insn *);
223	static void make_return_insns (rtx_insn *);
224
225	/* A wrapper around next_active_insn which takes care to return ret_rtx
226	unchanged. */
227
228	static rtx
229	first_active_target_insn (rtx insn)
230	{
231	if (ANY_RETURN_P (insn))
232	return insn;
233	return next_active_insn (as_a <rtx_insn *> (p: insn));
234	}
235
236	/* Return true iff INSN is a simplejump, or any kind of return insn. */
237
238	static bool
239	simplejump_or_return_p (rtx insn)
240	{
241	return (JUMP_P (insn)
242	&& (simplejump_p (as_a <rtx_insn *> (p: insn))
243	|| ANY_RETURN_P (PATTERN (insn))));
244	}
245
246	/* Return TRUE if this insn should stop the search for insn to fill delay
247	slots. LABELS_P indicates that labels should terminate the search.
248	In all cases, jumps terminate the search. */
249
250	static bool
251	stop_search_p (rtx_insn *insn, bool labels_p)
252	{
253	if (insn == 0)
254	return true;
255
256	/* If the insn can throw an exception that is caught within the function,
257	it may effectively perform a jump from the viewpoint of the function.
258	Therefore act like for a jump. */
259	if (can_throw_internal (insn))
260	return true;
261
262	switch (GET_CODE (insn))
263	{
264	case NOTE:
265	case CALL_INSN:
266	case DEBUG_INSN:
267	return false;
268
269	case CODE_LABEL:
270	return labels_p;
271
272	case JUMP_INSN:
273	case BARRIER:
274	return true;
275
276	case INSN:
277	/* OK unless it contains a delay slot or is an `asm' insn of some type.
278	We don't know anything about these. */
279	return (GET_CODE (PATTERN (insn)) == SEQUENCE
280	|| GET_CODE (PATTERN (insn)) == ASM_INPUT
281	|| asm_noperands (PATTERN (insn)) >= 0);
282
283	default:
284	gcc_unreachable ();
285	}
286	}
287
288	/* Return TRUE if any resources are marked in both RES1 and RES2 or if either
289	resource set contains a volatile memory reference. Otherwise, return FALSE. */
290
291	static bool
292	resource_conflicts_p (struct resources *res1, struct resources *res2)
293	{
294	if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
295	|| res1->volatil || res2->volatil)
296	return true;
297
298	return hard_reg_set_intersect_p (x: res1->regs, y: res2->regs);
299	}
300
301	/* Return TRUE if any resource marked in RES, a `struct resources', is
302	referenced by INSN. If INCLUDE_DELAYED_EFFECTS is set, return if the called
303	routine is using those resources.
304
305	We compute this by computing all the resources referenced by INSN and
306	seeing if this conflicts with RES. It might be faster to directly check
307	ourselves, and this is the way it used to work, but it means duplicating
308	a large block of complex code. */
309
310	static bool
311	insn_references_resource_p (rtx insn, struct resources *res,
312	bool include_delayed_effects)
313	{
314	struct resources insn_res;
315
316	CLEAR_RESOURCE (&insn_res);
317	mark_referenced_resources (insn, &insn_res, include_delayed_effects);
318	return resource_conflicts_p (res1: &insn_res, res2: res);
319	}
320
321	/* Return TRUE if INSN modifies resources that are marked in RES.
322	INCLUDE_DELAYED_EFFECTS is set if the actions of that routine should be
323	included. */
324
325	static bool
326	insn_sets_resource_p (rtx insn, struct resources *res,
327	bool include_delayed_effects)
328	{
329	struct resources insn_sets;
330
331	CLEAR_RESOURCE (&insn_sets);
332	mark_set_resources (insn, &insn_sets, 0,
333	(include_delayed_effects
334	? MARK_SRC_DEST_CALL
335	: MARK_SRC_DEST));
336	return resource_conflicts_p (res1: &insn_sets, res2: res);
337	}
338
339	/* Find a label at the end of the function or before a RETURN. If there
340	is none, try to make one. If that fails, returns 0.
341
342	The property of such a label is that it is placed just before the
343	epilogue or a bare RETURN insn, so that another bare RETURN can be
344	turned into a jump to the label unconditionally. In particular, the
345	label cannot be placed before a RETURN insn with a filled delay slot.
346
347	??? There may be a problem with the current implementation. Suppose
348	we start with a bare RETURN insn and call find_end_label. It may set
349	function_return_label just before the RETURN. Suppose the machinery
350	is able to fill the delay slot of the RETURN insn afterwards. Then
351	function_return_label is no longer valid according to the property
352	described above and find_end_label will still return it unmodified.
353	Note that this is probably mitigated by the following observation:
354	once function_return_label is made, it is very likely the target of
355	a jump, so filling the delay slot of the RETURN will be much more
356	difficult.
357	KIND is either simple_return_rtx or ret_rtx, indicating which type of
358	return we're looking for. */
359
360	static rtx_code_label *
361	find_end_label (rtx kind)
362	{
363	rtx_insn *insn;
364	rtx_code_label **plabel;
365
366	if (kind == ret_rtx)
367	plabel = &function_return_label;
368	else
369	{
370	gcc_assert (kind == simple_return_rtx);
371	plabel = &function_simple_return_label;
372	}
373
374	/* If we found one previously, return it. */
375	if (*plabel)
376	return *plabel;
377
378	/* Otherwise, see if there is a label at the end of the function. If there
379	is, it must be that RETURN insns aren't needed, so that is our return
380	label and we don't have to do anything else. */
381
382	insn = get_last_insn ();
383	while (NOTE_P (insn)
384	|| (NONJUMP_INSN_P (insn)
385	&& (GET_CODE (PATTERN (insn)) == USE
386	|| GET_CODE (PATTERN (insn)) == CLOBBER)))
387	insn = PREV_INSN (insn);
388
389	/* When a target threads its epilogue we might already have a
390	suitable return insn. If so put a label before it for the
391	function_return_label. */
392	if (BARRIER_P (insn)
393	&& JUMP_P (PREV_INSN (insn))
394	&& PATTERN (insn: PREV_INSN (insn)) == kind)
395	{
396	rtx_insn *temp = PREV_INSN (insn: PREV_INSN (insn));
397	rtx_code_label *label = gen_label_rtx ();
398	LABEL_NUSES (label) = 0;
399
400	/* Put the label before any USE insns that may precede the RETURN
401	insn. */
402	while (GET_CODE (temp) == USE)
403	temp = PREV_INSN (insn: temp);
404
405	emit_label_after (label, temp);
406	*plabel = label;
407	}
408
409	else if (LABEL_P (insn))
410	*plabel = as_a <rtx_code_label *> (p: insn);
411	else
412	{
413	rtx_code_label *label = gen_label_rtx ();
414	LABEL_NUSES (label) = 0;
415	/* If the basic block reorder pass moves the return insn to
416	some other place try to locate it again and put our
417	function_return_label there. */
418	while (insn && ! (JUMP_P (insn) && (PATTERN (insn) == kind)))
419	insn = PREV_INSN (insn);
420	if (insn)
421	{
422	insn = PREV_INSN (insn);
423
424	/* Put the label before any USE insns that may precede the
425	RETURN insn. */
426	while (GET_CODE (insn) == USE)
427	insn = PREV_INSN (insn);
428
429	emit_label_after (label, insn);
430	}
431	else
432	{
433	if (targetm.have_epilogue () && ! targetm.have_return ())
434	/* The RETURN insn has its delay slot filled so we cannot
435	emit the label just before it. Since we already have
436	an epilogue and cannot emit a new RETURN, we cannot
437	emit the label at all. */
438	return NULL;
439
440	/* Otherwise, make a new label and emit a RETURN and BARRIER,
441	if needed. */
442	emit_label (label);
443	if (targetm.have_return ())
444	{
445	/* The return we make may have delay slots too. */
446	rtx_insn *pat = targetm.gen_return ();
447	rtx_insn *insn = emit_jump_insn (pat);
448	set_return_jump_label (insn);
449	emit_barrier ();
450	if (num_delay_slots (insn) > 0)
451	obstack_ptr_grow (&unfilled_slots_obstack, insn);
452	}
453	}
454	*plabel = label;
455	}
456
457	/* Show one additional use for this label so it won't go away until
458	we are done. */
459	++LABEL_NUSES (*plabel);
460
461	return *plabel;
462	}
463
464	/* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
465	the pattern of INSN with the SEQUENCE.
466
467	Returns the insn containing the SEQUENCE that replaces INSN. */
468
469	static rtx_insn *
470	emit_delay_sequence (rtx_insn *insn, const vec<rtx_insn *> &list, int length)
471	{
472	/* Allocate the rtvec to hold the insns and the SEQUENCE. */
473	rtvec seqv = rtvec_alloc (length + 1);
474	rtx seq = gen_rtx_SEQUENCE (VOIDmode, seqv);
475	rtx_insn *seq_insn = make_insn_raw (seq);
476
477	/* If DELAY_INSN has a location, use it for SEQ_INSN. If DELAY_INSN does
478	not have a location, but one of the delayed insns does, we pick up a
479	location from there later. */
480	INSN_LOCATION (insn: seq_insn) = INSN_LOCATION (insn);
481
482	/* Unlink INSN from the insn chain, so that we can put it into
483	the SEQUENCE. Remember where we want to emit SEQUENCE in AFTER. */
484	rtx_insn *after = PREV_INSN (insn);
485	remove_insn (insn);
486	SET_NEXT_INSN (insn) = SET_PREV_INSN (insn) = NULL;
487
488	/* Build our SEQUENCE and rebuild the insn chain. */
489	start_sequence ();
490	XVECEXP (seq, 0, 0) = emit_insn (insn);
491
492	unsigned int delay_insns = list.length ();
493	gcc_assert (delay_insns == (unsigned int) length);
494	for (unsigned int i = 0; i < delay_insns; i++)
495	{
496	rtx_insn *tem = list[i];
497	rtx note, next;
498
499	/* Show that this copy of the insn isn't deleted. */
500	tem->set_undeleted ();
501
502	/* Unlink insn from its original place, and re-emit it into
503	the sequence. */
504	SET_NEXT_INSN (tem) = SET_PREV_INSN (tem) = NULL;
505	XVECEXP (seq, 0, i + 1) = emit_insn (tem);
506
507	/* SPARC assembler, for instance, emit warning when debug info is output
508	into the delay slot. */
509	if (INSN_LOCATION (insn: tem) && !INSN_LOCATION (insn: seq_insn))
510	INSN_LOCATION (insn: seq_insn) = INSN_LOCATION (insn: tem);
511	INSN_LOCATION (insn: tem) = 0;
512
513	for (note = REG_NOTES (tem); note; note = next)
514	{
515	next = XEXP (note, 1);
516	switch (REG_NOTE_KIND (note))
517	{
518	case REG_DEAD:
519	/* Remove any REG_DEAD notes because we can't rely on them now
520	that the insn has been moved. */
521	remove_note (tem, note);
522	break;
523
524	case REG_LABEL_OPERAND:
525	case REG_LABEL_TARGET:
526	/* Keep the label reference count up to date. */
527	if (LABEL_P (XEXP (note, 0)))
528	LABEL_NUSES (XEXP (note, 0)) ++;
529	break;
530
531	default:
532	break;
533	}
534	}
535	}
536	end_sequence ();
537
538	/* Splice our SEQUENCE into the insn stream where INSN used to be. */
539	add_insn_after (seq_insn, after, NULL);
540
541	return seq_insn;
542	}
543
544	/* Add INSN to DELAY_LIST and return the head of the new list. The list must
545	be in the order in which the insns are to be executed. */
546
547	static void
548	add_to_delay_list (rtx_insn *insn, vec<rtx_insn *> *delay_list)
549	{
550	/* If INSN has its block number recorded, clear it since we may
551	be moving the insn to a new block. */
552	clear_hashed_info_for_insn (insn);
553
554	delay_list->safe_push (obj: insn);
555	}
556
557	/* Delete INSN from the delay slot of the insn that it is in, which may
558	produce an insn with no delay slots. Return the new insn. */
559
560	static rtx_insn *
561	delete_from_delay_slot (rtx_insn *insn)
562	{
563	rtx_insn *trial, *seq_insn, *prev;
564	rtx_sequence *seq;
565	bool had_barrier = false;
566	int i;
567
568	/* We first must find the insn containing the SEQUENCE with INSN in its
569	delay slot. Do this by finding an insn, TRIAL, where
570	PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
571
572	for (trial = insn;
573	PREV_INSN (insn: NEXT_INSN (insn: trial)) == trial;
574	trial = NEXT_INSN (insn: trial))
575	;
576
577	seq_insn = PREV_INSN (insn: NEXT_INSN (insn: trial));
578	seq = as_a <rtx_sequence *> (p: PATTERN (insn: seq_insn));
579
580	if (NEXT_INSN (insn: seq_insn) && BARRIER_P (NEXT_INSN (seq_insn)))
581	had_barrier = true;
582
583	/* Create a delay list consisting of all the insns other than the one
584	we are deleting (unless we were the only one). */
585	auto_vec<rtx_insn *, 5> delay_list;
586	if (seq->len () > 2)
587	for (i = 1; i < seq->len (); i++)
588	if (seq->insn (index: i) != insn)
589	add_to_delay_list (insn: seq->insn (index: i), delay_list: &delay_list);
590
591	/* Delete the old SEQUENCE, re-emit the insn that used to have the delay
592	list, and rebuild the delay list if non-empty. */
593	prev = PREV_INSN (insn: seq_insn);
594	trial = seq->insn (index: 0);
595	delete_related_insns (seq_insn);
596	add_insn_after (trial, prev, NULL);
597
598	/* If there was a barrier after the old SEQUENCE, remit it. */
599	if (had_barrier)
600	emit_barrier_after (trial);
601
602	/* If there are any delay insns, remit them. Otherwise clear the
603	annul flag. */
604	if (!delay_list.is_empty ())
605	trial = emit_delay_sequence (insn: trial, list: delay_list, XVECLEN (seq, 0) - 2);
606	else if (JUMP_P (trial))
607	INSN_ANNULLED_BRANCH_P (trial) = 0;
608
609	INSN_FROM_TARGET_P (insn) = 0;
610
611	/* Show we need to fill this insn again. */
612	obstack_ptr_grow (&unfilled_slots_obstack, trial);
613
614	return trial;
615	}
616
617	/* Delete INSN, a JUMP_INSN. */
618
619	static void
620	delete_scheduled_jump (rtx_insn *insn)
621	{
622	delete_related_insns (insn);
623	}
624
625	/* Counters for delay-slot filling. */
626
627	#define NUM_REORG_FUNCTIONS 2
628	#define MAX_DELAY_HISTOGRAM 3
629	#define MAX_REORG_PASSES 2
630
631	static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
632
633	static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
634
635	static int reorg_pass_number;
636
637	static void
638	note_delay_statistics (int slots_filled, int index)
639	{
640	num_insns_needing_delays[index][reorg_pass_number]++;
641	if (slots_filled > MAX_DELAY_HISTOGRAM)
642	slots_filled = MAX_DELAY_HISTOGRAM;
643	num_filled_delays[index][slots_filled][reorg_pass_number]++;
644	}
645
646	/* Optimize the following cases:
647
648	1. When a conditional branch skips over only one instruction,
649	use an annulling branch and put that insn in the delay slot.
650	Use either a branch that annuls when the condition if true or
651	invert the test with a branch that annuls when the condition is
652	false. This saves insns, since otherwise we must copy an insn
653	from the L1 target.
654
655	(orig) (skip) (otherwise)
656	Bcc.n L1 Bcc',a L1 Bcc,a L1'
657	insn insn insn2
658	L1: L1: L1:
659	insn2 insn2 insn2
660	insn3 insn3 L1':
661	insn3
662
663	2. When a conditional branch skips over only one instruction,
664	and after that, it unconditionally branches somewhere else,
665	perform the similar optimization. This saves executing the
666	second branch in the case where the inverted condition is true.
667
668	Bcc.n L1 Bcc',a L2
669	insn insn
670	L1: L1:
671	Bra L2 Bra L2
672
673	INSN is a JUMP_INSN.
674
675	This should be expanded to skip over N insns, where N is the number
676	of delay slots required. */
677
678	static void
679	optimize_skip (rtx_jump_insn *insn, vec<rtx_insn *> *delay_list)
680	{
681	rtx_insn *trial = next_nonnote_insn (insn);
682	rtx_insn *next_trial = next_active_insn (trial);
683	int flags;
684
685	flags = get_jump_flags (insn, JUMP_LABEL (insn));
686
687	if (trial == 0
688	|| !NONJUMP_INSN_P (trial)
689	|| GET_CODE (PATTERN (trial)) == SEQUENCE
690	|| recog_memoized (insn: trial) < 0
691	|| (! eligible_for_annul_false (insn, 0, trial, flags)
692	&& ! eligible_for_annul_true (insn, 0, trial, flags))
693	|| RTX_FRAME_RELATED_P (trial)
694	|| can_throw_internal (trial))
695	return;
696
697	/* There are two cases where we are just executing one insn (we assume
698	here that a branch requires only one insn; this should be generalized
699	at some point): Where the branch goes around a single insn or where
700	we have one insn followed by a branch to the same label we branch to.
701	In both of these cases, inverting the jump and annulling the delay
702	slot give the same effect in fewer insns. */
703	if (next_trial == next_active_insn (JUMP_LABEL_AS_INSN (insn))
704	|| (next_trial != 0
705	&& simplejump_or_return_p (insn: next_trial)
706	&& JUMP_LABEL (insn) == JUMP_LABEL (next_trial)))
707	{
708	if (eligible_for_annul_false (insn, 0, trial, flags))
709	{
710	if (invert_jump (insn, JUMP_LABEL (insn), 1))
711	INSN_FROM_TARGET_P (trial) = 1;
712	else if (! eligible_for_annul_true (insn, 0, trial, flags))
713	return;
714	}
715
716	add_to_delay_list (insn: trial, delay_list);
717	next_trial = next_active_insn (trial);
718	update_block (trial, trial);
719	delete_related_insns (trial);
720
721	/* Also, if we are targeting an unconditional
722	branch, thread our jump to the target of that branch. Don't
723	change this into a RETURN here, because it may not accept what
724	we have in the delay slot. We'll fix this up later. */
725	if (next_trial && simplejump_or_return_p (insn: next_trial))
726	{
727	rtx target_label = JUMP_LABEL (next_trial);
728	if (ANY_RETURN_P (target_label))
729	target_label = find_end_label (kind: target_label);
730
731	if (target_label)
732	{
733	/* Recompute the flags based on TARGET_LABEL since threading
734	the jump to TARGET_LABEL may change the direction of the
735	jump (which may change the circumstances in which the
736	delay slot is nullified). */
737	flags = get_jump_flags (insn, target_label);
738	if (eligible_for_annul_true (insn, 0, trial, flags))
739	reorg_redirect_jump (insn, target_label);
740	}
741	}
742
743	INSN_ANNULLED_BRANCH_P (insn) = 1;
744	}
745	}
746
747	/* Encode and return branch direction and prediction information for
748	INSN assuming it will jump to LABEL.
749
750	Non conditional branches return no direction information and
751	are predicted as very likely taken. */
752
753	static int
754	get_jump_flags (const rtx_insn *insn, rtx label)
755	{
756	int flags;
757
758	/* get_jump_flags can be passed any insn with delay slots, these may
759	be INSNs, CALL_INSNs, or JUMP_INSNs. Only JUMP_INSNs have branch
760	direction information, and only if they are conditional jumps.
761
762	If LABEL is a return, then there is no way to determine the branch
763	direction. */
764	if (JUMP_P (insn)
765	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
766	&& !ANY_RETURN_P (label)
767	&& INSN_UID (insn) <= max_uid
768	&& INSN_UID (insn: label) <= max_uid)
769	flags
770	= (uid_to_ruid[INSN_UID (insn: label)] > uid_to_ruid[INSN_UID (insn)])
771	? ATTR_FLAG_forward : ATTR_FLAG_backward;
772	/* No valid direction information. */
773	else
774	flags = 0;
775
776	return flags;
777	}
778
779	/* Return truth value of the statement that this branch
780	is mostly taken. If we think that the branch is extremely likely
781	to be taken, we return 2. If the branch is slightly more likely to be
782	taken, return 1. If the branch is slightly less likely to be taken,
783	return 0 and if the branch is highly unlikely to be taken, return -1. */
784
785	static int
786	mostly_true_jump (rtx jump_insn)
787	{
788	/* If branch probabilities are available, then use that number since it
789	always gives a correct answer. */
790	rtx note = find_reg_note (jump_insn, REG_BR_PROB, 0);
791	if (note)
792	{
793	int prob = profile_probability::from_reg_br_prob_note (XINT (note, 0))
794	.to_reg_br_prob_base ();
795
796	if (prob >= REG_BR_PROB_BASE * 9 / 10)
797	return 2;
798	else if (prob >= REG_BR_PROB_BASE / 2)
799	return 1;
800	else if (prob >= REG_BR_PROB_BASE / 10)
801	return 0;
802	else
803	return -1;
804	}
805
806	/* If there is no note, assume branches are not taken.
807	This should be rare. */
808	return 0;
809	}
810
811	/* Return the condition under which INSN will branch to TARGET. If TARGET
812	is zero, return the condition under which INSN will return. If INSN is
813	an unconditional branch, return const_true_rtx. If INSN isn't a simple
814	type of jump, or it doesn't go to TARGET, return 0. */
815
816	static rtx
817	get_branch_condition (const rtx_insn *insn, rtx target)
818	{
819	rtx pat = PATTERN (insn);
820	rtx src;
821
822	if (condjump_in_parallel_p (insn))
823	pat = XVECEXP (pat, 0, 0);
824
825	if (ANY_RETURN_P (pat) && pat == target)
826	return const_true_rtx;
827
828	if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
829	return 0;
830
831	src = SET_SRC (pat);
832	if (GET_CODE (src) == LABEL_REF && label_ref_label (ref: src) == target)
833	return const_true_rtx;
834
835	else if (GET_CODE (src) == IF_THEN_ELSE
836	&& XEXP (src, 2) == pc_rtx
837	&& ((GET_CODE (XEXP (src, 1)) == LABEL_REF
838	&& label_ref_label (XEXP (src, 1)) == target)
839	|| (ANY_RETURN_P (XEXP (src, 1)) && XEXP (src, 1) == target)))
840	return XEXP (src, 0);
841
842	else if (GET_CODE (src) == IF_THEN_ELSE
843	&& XEXP (src, 1) == pc_rtx
844	&& ((GET_CODE (XEXP (src, 2)) == LABEL_REF
845	&& label_ref_label (XEXP (src, 2)) == target)
846	|| (ANY_RETURN_P (XEXP (src, 2)) && XEXP (src, 2) == target)))
847	{
848	enum rtx_code rev;
849	rev = reversed_comparison_code (XEXP (src, 0), insn);
850	if (rev != UNKNOWN)
851	return gen_rtx_fmt_ee (rev, GET_MODE (XEXP (src, 0)),
852	XEXP (XEXP (src, 0), 0),
853	XEXP (XEXP (src, 0), 1));
854	}
855
856	return 0;
857	}
858
859	/* Return true if CONDITION is more strict than the condition of
860	INSN, i.e., if INSN will always branch if CONDITION is true. */
861
862	static bool
863	condition_dominates_p (rtx condition, const rtx_insn *insn)
864	{
865	rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
866	enum rtx_code code = GET_CODE (condition);
867	enum rtx_code other_code;
868
869	if (rtx_equal_p (condition, other_condition)
870	|| other_condition == const_true_rtx)
871	return true;
872
873	else if (condition == const_true_rtx || other_condition == 0)
874	return false;
875
876	other_code = GET_CODE (other_condition);
877	if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
878	|| ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
879	|| ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
880	return false;
881
882	return comparison_dominates_p (code, other_code);
883	}
884
885	/* Return true if redirecting JUMP to NEWLABEL does not invalidate
886	any insns already in the delay slot of JUMP. */
887
888	static bool
889	redirect_with_delay_slots_safe_p (rtx_insn *jump, rtx newlabel, rtx seq)
890	{
891	int flags, i;
892	rtx_sequence *pat = as_a <rtx_sequence *> (p: PATTERN (insn: seq));
893
894	/* Make sure all the delay slots of this jump would still
895	be valid after threading the jump. If they are still
896	valid, then return nonzero. */
897
898	flags = get_jump_flags (insn: jump, label: newlabel);
899	for (i = 1; i < pat->len (); i++)
900	if (! (
901	#if ANNUL_IFFALSE_SLOTS
902	(INSN_ANNULLED_BRANCH_P (jump)
903	&& INSN_FROM_TARGET_P (pat->insn (i)))
904	? eligible_for_annul_false (jump, i - 1, pat->insn (i), flags) :
905	#endif
906	#if ANNUL_IFTRUE_SLOTS
907	(INSN_ANNULLED_BRANCH_P (jump)
908	&& ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
909	? eligible_for_annul_true (jump, i - 1, pat->insn (i), flags) :
910	#endif
911	eligible_for_delay (jump, i - 1, pat->insn (index: i), flags)))
912	break;
913
914	return (i == pat->len ());
915	}
916
917	/* Return true if redirecting JUMP to NEWLABEL does not invalidate
918	any insns we wish to place in the delay slot of JUMP. */
919
920	static bool
921	redirect_with_delay_list_safe_p (rtx_insn *jump, rtx newlabel,
922	const vec<rtx_insn *> &delay_list)
923	{
924	/* Make sure all the insns in DELAY_LIST would still be
925	valid after threading the jump. If they are still
926	valid, then return true. */
927
928	int flags = get_jump_flags (insn: jump, label: newlabel);
929	unsigned int delay_insns = delay_list.length ();
930	unsigned int i = 0;
931	for (; i < delay_insns; i++)
932	if (! (
933	#if ANNUL_IFFALSE_SLOTS
934	(INSN_ANNULLED_BRANCH_P (jump)
935	&& INSN_FROM_TARGET_P (delay_list[i]))
936	? eligible_for_annul_false (jump, i, delay_list[i], flags) :
937	#endif
938	#if ANNUL_IFTRUE_SLOTS
939	(INSN_ANNULLED_BRANCH_P (jump)
940	&& ! INSN_FROM_TARGET_P (delay_list[i]))
941	? eligible_for_annul_true (jump, i, delay_list[i], flags) :
942	#endif
943	eligible_for_delay (jump, i, delay_list[i], flags)))
944	break;
945
946	return i == delay_insns;
947	}
948
949	/* DELAY_LIST is a list of insns that have already been placed into delay
950	slots. See if all of them have the same annulling status as ANNUL_TRUE_P.
951	If not, return false; otherwise return true. */
952
953	static bool
954	check_annul_list_true_false (bool annul_true_p,
955	const vec<rtx_insn *> &delay_list)
956	{
957	rtx_insn *trial;
958	unsigned int i;
959	FOR_EACH_VEC_ELT (delay_list, i, trial)
960	if ((annul_true_p && INSN_FROM_TARGET_P (trial))
961	|| (!annul_true_p && !INSN_FROM_TARGET_P (trial)))
962	return false;
963
964	return true;
965	}
966
967	/* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
968	the condition tested by INSN is CONDITION and the resources shown in
969	OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
970	from SEQ's delay list, in addition to whatever insns it may execute
971	(in DELAY_LIST). SETS and NEEDED are denote resources already set and
972	needed while searching for delay slot insns. Return the concatenated
973	delay list if possible, otherwise, return 0.
974
975	SLOTS_TO_FILL is the total number of slots required by INSN, and
976	PSLOTS_FILLED points to the number filled so far (also the number of
977	insns in DELAY_LIST). It is updated with the number that have been
978	filled from the SEQUENCE, if any.
979
980	PANNUL_P points to a nonzero value if we already know that we need
981	to annul INSN. If this routine determines that annulling is needed,
982	it may set that value to true.
983
984	PNEW_THREAD points to a location that is to receive the place at which
985	execution should continue. */
986
987	static void
988	steal_delay_list_from_target (rtx_insn *insn, rtx condition, rtx_sequence *seq,
989	vec<rtx_insn *> *delay_list,
990	struct resources *sets,
991	struct resources *needed,
992	struct resources *other_needed,
993	int slots_to_fill, int *pslots_filled,
994	bool *pannul_p, rtx *pnew_thread)
995	{
996	int slots_remaining = slots_to_fill - *pslots_filled;
997	int total_slots_filled = *pslots_filled;
998	auto_vec<rtx_insn *, 5> new_delay_list;
999	bool must_annul = *pannul_p;
1000	bool used_annul = false;
1001	int i;
1002	struct resources cc_set;
1003	rtx_insn **redundant;
1004
1005	/* We can't do anything if there are more delay slots in SEQ than we
1006	can handle, or if we don't know that it will be a taken branch.
1007	We know that it will be a taken branch if it is either an unconditional
1008	branch or a conditional branch with a stricter branch condition.
1009
1010	Also, exit if the branch has more than one set, since then it is computing
1011	other results that can't be ignored, e.g. the HPPA mov&branch instruction.
1012	??? It may be possible to move other sets into INSN in addition to
1013	moving the instructions in the delay slots.
1014
1015	We cannot steal the delay list if one of the instructions in the
1016	current delay_list modifies the condition codes and the jump in the
1017	sequence is a conditional jump. We cannot do this because we cannot
1018	change the direction of the jump because the condition codes
1019	will effect the direction of the jump in the sequence. */
1020
1021	CLEAR_RESOURCE (&cc_set);
1022
1023	rtx_insn *trial;
1024	FOR_EACH_VEC_ELT (*delay_list, i, trial)
1025	{
1026	mark_set_resources (trial, &cc_set, 0, MARK_SRC_DEST_CALL);
1027	if (insn_references_resource_p (insn: seq->insn (index: 0), res: &cc_set, include_delayed_effects: false))
1028	return;
1029	}
1030
1031	if (XVECLEN (seq, 0) - 1 > slots_remaining
1032	|| ! condition_dominates_p (condition, insn: seq->insn (index: 0))
1033	|| ! single_set (insn: seq->insn (index: 0)))
1034	return;
1035
1036	/* On some targets, branches with delay slots can have a limited
1037	displacement. Give the back end a chance to tell us we can't do
1038	this. */
1039	if (! targetm.can_follow_jump (insn, seq->insn (index: 0)))
1040	return;
1041
1042	redundant = XALLOCAVEC (rtx_insn *, XVECLEN (seq, 0));
1043	for (i = 1; i < seq->len (); i++)
1044	{
1045	rtx_insn *trial = seq->insn (index: i);
1046	int flags;
1047
1048	if (insn_references_resource_p (insn: trial, res: sets, include_delayed_effects: false)
1049	|| insn_sets_resource_p (insn: trial, res: needed, include_delayed_effects: false)
1050	|| insn_sets_resource_p (insn: trial, res: sets, include_delayed_effects: false)
1051	/* If TRIAL is from the fallthrough code of an annulled branch insn
1052	in SEQ, we cannot use it. */
1053	|| (INSN_ANNULLED_BRANCH_P (seq->insn (0))
1054	&& ! INSN_FROM_TARGET_P (trial)))
1055	return;
1056
1057	/* If this insn was already done (usually in a previous delay slot),
1058	pretend we put it in our delay slot. */
1059	redundant[i] = redundant_insn (trial, insn, new_delay_list);
1060	if (redundant[i])
1061	continue;
1062
1063	/* We will end up re-vectoring this branch, so compute flags
1064	based on jumping to the new label. */
1065	flags = get_jump_flags (insn, JUMP_LABEL (seq->insn (0)));
1066
1067	if (! must_annul
1068	&& ((condition == const_true_rtx
1069	|| (! insn_sets_resource_p (insn: trial, res: other_needed, include_delayed_effects: false)
1070	&& ! may_trap_or_fault_p (PATTERN (insn: trial)))))
1071	? eligible_for_delay (insn, total_slots_filled, trial, flags)
1072	: (must_annul || (delay_list->is_empty () && new_delay_list.is_empty ()))
1073	&& (must_annul = true,
1074	check_annul_list_true_false (annul_true_p: false, delay_list: *delay_list)
1075	&& check_annul_list_true_false (annul_true_p: false, delay_list: new_delay_list)
1076	&& eligible_for_annul_false (insn, total_slots_filled,
1077	trial, flags)))
1078	{
1079	if (must_annul)
1080	{
1081	/* Frame related instructions cannot go into annulled delay
1082	slots, it messes up the dwarf info. */
1083	if (RTX_FRAME_RELATED_P (trial))
1084	return;
1085	used_annul = true;
1086	}
1087	rtx_insn *temp = copy_delay_slot_insn (trial);
1088	INSN_FROM_TARGET_P (temp) = 1;
1089	add_to_delay_list (insn: temp, delay_list: &new_delay_list);
1090	total_slots_filled++;
1091
1092	if (--slots_remaining == 0)
1093	break;
1094	}
1095	else
1096	return;
1097	}
1098
1099	/* Record the effect of the instructions that were redundant and which
1100	we therefore decided not to copy. */
1101	for (i = 1; i < seq->len (); i++)
1102	if (redundant[i])
1103	{
1104	fix_reg_dead_note (redundant[i], insn);
1105	update_block (seq->insn (index: i), insn);
1106	}
1107
1108	/* Show the place to which we will be branching. */
1109	*pnew_thread = first_active_target_insn (JUMP_LABEL (seq->insn (0)));
1110
1111	/* Add any new insns to the delay list and update the count of the
1112	number of slots filled. */
1113	*pslots_filled = total_slots_filled;
1114	if (used_annul)
1115	*pannul_p = true;
1116
1117	rtx_insn *temp;
1118	FOR_EACH_VEC_ELT (new_delay_list, i, temp)
1119	add_to_delay_list (insn: temp, delay_list);
1120	}
1121
1122	/* Similar to steal_delay_list_from_target except that SEQ is on the
1123	fallthrough path of INSN. Here we only do something if the delay insn
1124	of SEQ is an unconditional branch. In that case we steal its delay slot
1125	for INSN since unconditional branches are much easier to fill. */
1126
1127	static void
1128	steal_delay_list_from_fallthrough (rtx_insn *insn, rtx condition,
1129	rtx_sequence *seq,
1130	vec<rtx_insn *> *delay_list,
1131	struct resources *sets,
1132	struct resources *needed,
1133	struct resources *other_needed,
1134	int slots_to_fill, int *pslots_filled,
1135	bool *pannul_p)
1136	{
1137	int i;
1138	int flags;
1139	bool must_annul = *pannul_p;
1140	bool used_annul = false;
1141
1142	flags = get_jump_flags (insn, JUMP_LABEL (insn));
1143
1144	/* We can't do anything if SEQ's delay insn isn't an
1145	unconditional branch. */
1146
1147	if (! simplejump_or_return_p (insn: seq->insn (index: 0)))
1148	return;
1149
1150	for (i = 1; i < seq->len (); i++)
1151	{
1152	rtx_insn *trial = seq->insn (index: i);
1153	rtx_insn *prior_insn;
1154
1155	if (insn_references_resource_p (insn: trial, res: sets, include_delayed_effects: false)
1156	|| insn_sets_resource_p (insn: trial, res: needed, include_delayed_effects: false)
1157	|| insn_sets_resource_p (insn: trial, res: sets, include_delayed_effects: false))
1158	break;
1159
1160	/* If this insn was already done, we don't need it. */
1161	if ((prior_insn = redundant_insn (trial, insn, *delay_list)))
1162	{
1163	fix_reg_dead_note (prior_insn, insn);
1164	update_block (trial, insn);
1165	delete_from_delay_slot (insn: trial);
1166	continue;
1167	}
1168
1169	if (! must_annul
1170	&& ((condition == const_true_rtx
1171	|| (! insn_sets_resource_p (insn: trial, res: other_needed, include_delayed_effects: false)
1172	&& ! may_trap_or_fault_p (PATTERN (insn: trial)))))
1173	? eligible_for_delay (insn, *pslots_filled, trial, flags)
1174	: (must_annul || delay_list->is_empty ()) && (must_annul = true,
1175	check_annul_list_true_false (annul_true_p: true, delay_list: *delay_list)
1176	&& eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
1177	{
1178	if (must_annul)
1179	used_annul = true;
1180	delete_from_delay_slot (insn: trial);
1181	add_to_delay_list (insn: trial, delay_list);
1182
1183	if (++(*pslots_filled) == slots_to_fill)
1184	break;
1185	}
1186	else
1187	break;
1188	}
1189
1190	if (used_annul)
1191	*pannul_p = true;
1192	}
1193
1194	/* Try merging insns starting at THREAD which match exactly the insns in
1195	INSN's delay list.
1196
1197	If all insns were matched and the insn was previously annulling, the
1198	annul bit will be cleared.
1199
1200	For each insn that is merged, if the branch is or will be non-annulling,
1201	we delete the merged insn. */
1202
1203	static void
1204	try_merge_delay_insns (rtx_insn *insn, rtx_insn *thread)
1205	{
1206	rtx_insn *trial, *next_trial;
1207	rtx_insn *delay_insn = as_a <rtx_insn *> (XVECEXP (PATTERN (insn), 0, 0));
1208	bool annul_p = JUMP_P (delay_insn) && INSN_ANNULLED_BRANCH_P (delay_insn);
1209	int slot_number = 1;
1210	int num_slots = XVECLEN (PATTERN (insn), 0);
1211	rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1212	struct resources set, needed, modified;
1213	auto_vec<std::pair<rtx_insn *, bool>, 10> merged_insns;
1214	int flags;
1215
1216	flags = get_jump_flags (insn: delay_insn, JUMP_LABEL (delay_insn));
1217
1218	CLEAR_RESOURCE (&needed);
1219	CLEAR_RESOURCE (&set);
1220
1221	/* If this is not an annulling branch, take into account anything needed in
1222	INSN's delay slot. This prevents two increments from being incorrectly
1223	folded into one. If we are annulling, this would be the correct
1224	thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1225	will essentially disable this optimization. This method is somewhat of
1226	a kludge, but I don't see a better way.) */
1227	if (! annul_p)
1228	for (int i = 1; i < num_slots; i++)
1229	if (XVECEXP (PATTERN (insn), 0, i))
1230	mark_referenced_resources (XVECEXP (PATTERN (insn), 0, i), &needed,
1231	true);
1232
1233	for (trial = thread; !stop_search_p (insn: trial, labels_p: true); trial = next_trial)
1234	{
1235	rtx pat = PATTERN (insn: trial);
1236	rtx oldtrial = trial;
1237
1238	next_trial = next_nonnote_insn (trial);
1239
1240	/* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1241	if (NONJUMP_INSN_P (trial)
1242	&& (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1243	continue;
1244
1245	if (GET_CODE (next_to_match) == GET_CODE (trial)
1246	&& ! insn_references_resource_p (insn: trial, res: &set, include_delayed_effects: true)
1247	&& ! insn_sets_resource_p (insn: trial, res: &set, include_delayed_effects: true)
1248	&& ! insn_sets_resource_p (insn: trial, res: &needed, include_delayed_effects: true)
1249	&& (trial = try_split (pat, trial, 0)) != 0
1250	/* Update next_trial, in case try_split succeeded. */
1251	&& (next_trial = next_nonnote_insn (trial))
1252	/* Likewise THREAD. */
1253	&& (thread = oldtrial == thread ? trial : thread)
1254	&& rtx_equal_p (PATTERN (insn: next_to_match), PATTERN (insn: trial))
1255	/* Have to test this condition if annul condition is different
1256	from (and less restrictive than) non-annulling one. */
1257	&& eligible_for_delay (delay_insn, slot_number - 1, trial, flags))
1258	{
1259
1260	if (! annul_p)
1261	{
1262	update_block (trial, thread);
1263	if (trial == thread)
1264	thread = next_active_insn (thread);
1265
1266	delete_related_insns (trial);
1267	INSN_FROM_TARGET_P (next_to_match) = 0;
1268	}
1269	else
1270	merged_insns.safe_push (obj: std::pair<rtx_insn *, bool> (trial, false));
1271
1272	if (++slot_number == num_slots)
1273	break;
1274
1275	next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1276	}
1277
1278	mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
1279	mark_referenced_resources (trial, &needed, true);
1280	}
1281
1282	/* See if we stopped on a filled insn. If we did, try to see if its
1283	delay slots match. */
1284	if (slot_number != num_slots
1285	&& trial && NONJUMP_INSN_P (trial)
1286	&& GET_CODE (PATTERN (trial)) == SEQUENCE
1287	&& !(JUMP_P (XVECEXP (PATTERN (trial), 0, 0))
1288	&& INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0))))
1289	{
1290	rtx_sequence *pat = as_a <rtx_sequence *> (p: PATTERN (insn: trial));
1291	rtx filled_insn = XVECEXP (pat, 0, 0);
1292
1293	/* Account for resources set/needed by the filled insn. */
1294	mark_set_resources (filled_insn, &set, 0, MARK_SRC_DEST_CALL);
1295	mark_referenced_resources (filled_insn, &needed, true);
1296
1297	for (int i = 1; i < pat->len (); i++)
1298	{
1299	rtx_insn *dtrial = pat->insn (index: i);
1300
1301	CLEAR_RESOURCE (&modified);
1302	/* Account for resources set by the insn following NEXT_TO_MATCH
1303	inside INSN's delay list. */
1304	for (int j = 1; slot_number + j < num_slots; j++)
1305	mark_set_resources (XVECEXP (PATTERN (insn), 0, slot_number + j),
1306	&modified, 0, MARK_SRC_DEST_CALL);
1307	/* Account for resources set by the insn before DTRIAL and inside
1308	TRIAL's delay list. */
1309	for (int j = 1; j < i; j++)
1310	mark_set_resources (XVECEXP (pat, 0, j),
1311	&modified, 0, MARK_SRC_DEST_CALL);
1312	if (! insn_references_resource_p (insn: dtrial, res: &set, include_delayed_effects: true)
1313	&& ! insn_sets_resource_p (insn: dtrial, res: &set, include_delayed_effects: true)
1314	&& ! insn_sets_resource_p (insn: dtrial, res: &needed, include_delayed_effects: true)
1315	&& rtx_equal_p (PATTERN (insn: next_to_match), PATTERN (insn: dtrial))
1316	/* Check that DTRIAL and NEXT_TO_MATCH does not reference a
1317	resource modified between them (only dtrial is checked because
1318	next_to_match and dtrial shall to be equal in order to hit
1319	this line) */
1320	&& ! insn_references_resource_p (insn: dtrial, res: &modified, include_delayed_effects: true)
1321	&& eligible_for_delay (delay_insn, slot_number - 1, dtrial, flags))
1322	{
1323	if (! annul_p)
1324	{
1325	rtx_insn *new_rtx;
1326
1327	update_block (dtrial, thread);
1328	new_rtx = delete_from_delay_slot (insn: dtrial);
1329	if (thread->deleted ())
1330	thread = new_rtx;
1331	INSN_FROM_TARGET_P (next_to_match) = 0;
1332	}
1333	else
1334	merged_insns.safe_push (obj: std::pair<rtx_insn *, bool> (dtrial,
1335	true));
1336
1337	if (++slot_number == num_slots)
1338	break;
1339
1340	next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1341	}
1342	else
1343	{
1344	/* Keep track of the set/referenced resources for the delay
1345	slots of any trial insns we encounter. */
1346	mark_set_resources (dtrial, &set, 0, MARK_SRC_DEST_CALL);
1347	mark_referenced_resources (dtrial, &needed, true);
1348	}
1349	}
1350	}
1351
1352	/* If all insns in the delay slot have been matched and we were previously
1353	annulling the branch, we need not any more. In that case delete all the
1354	merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn in
1355	the delay list so that we know that it isn't only being used at the
1356	target. */
1357	if (slot_number == num_slots && annul_p)
1358	{
1359	unsigned int len = merged_insns.length ();
1360	for (unsigned int i = len - 1; i < len; i--)
1361	if (merged_insns[i].second)
1362	{
1363	update_block (merged_insns[i].first, thread);
1364	rtx_insn *new_rtx = delete_from_delay_slot (insn: merged_insns[i].first);
1365	if (thread->deleted ())
1366	thread = new_rtx;
1367	}
1368	else
1369	{
1370	update_block (merged_insns[i].first, thread);
1371	delete_related_insns (merged_insns[i].first);
1372	}
1373
1374	INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1375
1376	for (int i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1377	INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1378	}
1379	}
1380
1381	/* See if INSN is redundant with an insn in front of TARGET. Often this
1382	is called when INSN is a candidate for a delay slot of TARGET.
1383	DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1384	of INSN. Often INSN will be redundant with an insn in a delay slot of
1385	some previous insn. This happens when we have a series of branches to the
1386	same label; in that case the first insn at the target might want to go
1387	into each of the delay slots.
1388
1389	If we are not careful, this routine can take up a significant fraction
1390	of the total compilation time (4%), but only wins rarely. Hence we
1391	speed this routine up by making two passes. The first pass goes back
1392	until it hits a label and sees if it finds an insn with an identical
1393	pattern. Only in this (relatively rare) event does it check for
1394	data conflicts.
1395
1396	We do not split insns we encounter. This could cause us not to find a
1397	redundant insn, but the cost of splitting seems greater than the possible
1398	gain in rare cases. */
1399
1400	static rtx_insn *
1401	redundant_insn (rtx insn, rtx_insn *target, const vec<rtx_insn *> &delay_list)
1402	{
1403	rtx target_main = target;
1404	rtx ipat = PATTERN (insn);
1405	rtx_insn *trial;
1406	rtx pat;
1407	struct resources needed, set;
1408	int i;
1409	unsigned insns_to_search;
1410
1411	/* If INSN has any REG_UNUSED notes, it can't match anything since we
1412	are allowed to not actually assign to such a register. */
1413	if (find_reg_note (insn, REG_UNUSED, NULL_RTX) != 0)
1414	return 0;
1415
1416	/* Scan backwards looking for a match. */
1417	for (trial = PREV_INSN (insn: target),
1418	insns_to_search = param_max_delay_slot_insn_search;
1419	trial && insns_to_search > 0;
1420	trial = PREV_INSN (insn: trial))
1421	{
1422	/* (use (insn))s can come immediately after a barrier if the
1423	label that used to precede them has been deleted as dead.
1424	See delete_related_insns. */
1425	if (LABEL_P (trial) || BARRIER_P (trial))
1426	return 0;
1427
1428	if (!INSN_P (trial))
1429	continue;
1430	--insns_to_search;
1431
1432	pat = PATTERN (insn: trial);
1433	if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1434	continue;
1435
1436	if (GET_CODE (trial) == DEBUG_INSN)
1437	continue;
1438
1439	if (rtx_sequence *seq = dyn_cast <rtx_sequence *> (p: pat))
1440	{
1441	/* Stop for a CALL and its delay slots because it is difficult to
1442	track its resource needs correctly. */
1443	if (CALL_P (seq->element (0)))
1444	return 0;
1445
1446	/* Stop for an INSN or JUMP_INSN with delayed effects and its delay
1447	slots because it is difficult to track its resource needs
1448	correctly. */
1449
1450	if (INSN_SETS_ARE_DELAYED (seq->insn (0)))
1451	return 0;
1452
1453	if (INSN_REFERENCES_ARE_DELAYED (seq->insn (0)))
1454	return 0;
1455
1456	/* See if any of the insns in the delay slot match, updating
1457	resource requirements as we go. */
1458	for (i = seq->len () - 1; i > 0; i--)
1459	if (GET_CODE (seq->element (i)) == GET_CODE (insn)
1460	&& rtx_equal_p (PATTERN (insn: seq->element (index: i)), ipat)
1461	&& ! find_reg_note (seq->element (index: i), REG_UNUSED, NULL_RTX))
1462	break;
1463
1464	/* If found a match, exit this loop early. */
1465	if (i > 0)
1466	break;
1467	}
1468
1469	else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat)
1470	&& ! find_reg_note (trial, REG_UNUSED, NULL_RTX))
1471	break;
1472	}
1473
1474	/* If we didn't find an insn that matches, return 0. */
1475	if (trial == 0)
1476	return 0;
1477
1478	/* See what resources this insn sets and needs. If they overlap, it
1479	can't be redundant. */
1480
1481	CLEAR_RESOURCE (&needed);
1482	CLEAR_RESOURCE (&set);
1483	mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
1484	mark_referenced_resources (insn, &needed, true);
1485
1486	/* If TARGET is a SEQUENCE, get the main insn. */
1487	if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE)
1488	target_main = XVECEXP (PATTERN (target), 0, 0);
1489
1490	if (resource_conflicts_p (res1: &needed, res2: &set)
1491	/* The insn requiring the delay may not set anything needed or set by
1492	INSN. */
1493	|| insn_sets_resource_p (insn: target_main, res: &needed, include_delayed_effects: true)
1494	|| insn_sets_resource_p (insn: target_main, res: &set, include_delayed_effects: true))
1495	return 0;
1496
1497	/* Insns we pass may not set either NEEDED or SET, so merge them for
1498	simpler tests. */
1499	needed.memory |= set.memory;
1500	needed.regs |= set.regs;
1501
1502	/* This insn isn't redundant if it conflicts with an insn that either is
1503	or will be in a delay slot of TARGET. */
1504
1505	unsigned int j;
1506	rtx_insn *temp;
1507	FOR_EACH_VEC_ELT (delay_list, j, temp)
1508	if (insn_sets_resource_p (insn: temp, res: &needed, include_delayed_effects: true))
1509	return 0;
1510
1511	if (NONJUMP_INSN_P (target) && GET_CODE (PATTERN (target)) == SEQUENCE)
1512	for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1513	if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), res: &needed,
1514	include_delayed_effects: true))
1515	return 0;
1516
1517	/* Scan backwards until we reach a label or an insn that uses something
1518	INSN sets or sets something insn uses or sets. */
1519
1520	for (trial = PREV_INSN (insn: target),
1521	insns_to_search = param_max_delay_slot_insn_search;
1522	trial && !LABEL_P (trial) && insns_to_search > 0;
1523	trial = PREV_INSN (insn: trial))
1524	{
1525	if (!INSN_P (trial))
1526	continue;
1527	--insns_to_search;
1528
1529	pat = PATTERN (insn: trial);
1530	if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1531	continue;
1532
1533	if (GET_CODE (trial) == DEBUG_INSN)
1534	continue;
1535
1536	if (rtx_sequence *seq = dyn_cast <rtx_sequence *> (p: pat))
1537	{
1538	bool annul_p = false;
1539	rtx_insn *control = seq->insn (index: 0);
1540
1541	/* If this is a CALL_INSN and its delay slots, it is hard to track
1542	the resource needs properly, so give up. */
1543	if (CALL_P (control))
1544	return 0;
1545
1546	/* If this is an INSN or JUMP_INSN with delayed effects, it
1547	is hard to track the resource needs properly, so give up. */
1548
1549	if (INSN_SETS_ARE_DELAYED (control))
1550	return 0;
1551
1552	if (INSN_REFERENCES_ARE_DELAYED (control))
1553	return 0;
1554
1555	if (JUMP_P (control))
1556	annul_p = INSN_ANNULLED_BRANCH_P (control);
1557
1558	/* See if any of the insns in the delay slot match, updating
1559	resource requirements as we go. */
1560	for (i = seq->len () - 1; i > 0; i--)
1561	{
1562	rtx_insn *candidate = seq->insn (index: i);
1563
1564	/* If an insn will be annulled if the branch is false, it isn't
1565	considered as a possible duplicate insn. */
1566	if (rtx_equal_p (PATTERN (insn: candidate), ipat)
1567	&& ! (annul_p && INSN_FROM_TARGET_P (candidate)))
1568	{
1569	/* Show that this insn will be used in the sequel. */
1570	INSN_FROM_TARGET_P (candidate) = 0;
1571	return candidate;
1572	}
1573
1574	/* Unless this is an annulled insn from the target of a branch,
1575	we must stop if it sets anything needed or set by INSN. */
1576	if ((!annul_p || !INSN_FROM_TARGET_P (candidate))
1577	&& insn_sets_resource_p (insn: candidate, res: &needed, include_delayed_effects: true))
1578	return 0;
1579	}
1580
1581	/* If the insn requiring the delay slot conflicts with INSN, we
1582	must stop. */
1583	if (insn_sets_resource_p (insn: control, res: &needed, include_delayed_effects: true))
1584	return 0;
1585	}
1586	else
1587	{
1588	/* See if TRIAL is the same as INSN. */
1589	pat = PATTERN (insn: trial);
1590	if (rtx_equal_p (pat, ipat))
1591	return trial;
1592
1593	/* Can't go any further if TRIAL conflicts with INSN. */
1594	if (insn_sets_resource_p (insn: trial, res: &needed, include_delayed_effects: true))
1595	return 0;
1596	}
1597	}
1598
1599	return 0;
1600	}
1601
1602	/* Return true if THREAD can only be executed in one way. If LABEL is nonzero,
1603	it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1604	is true, we are allowed to fall into this thread; otherwise, we are not.
1605
1606	If LABEL is used more than one or we pass a label other than LABEL before
1607	finding an active insn, we do not own this thread. */
1608
1609	static bool
1610	own_thread_p (rtx thread, rtx label, bool allow_fallthrough)
1611	{
1612	rtx_insn *active_insn;
1613	rtx_insn *insn;
1614
1615	/* We don't own the function end. */
1616	if (thread == 0 || ANY_RETURN_P (thread))
1617	return false;
1618
1619	/* We have a non-NULL insn. */
1620	rtx_insn *thread_insn = as_a <rtx_insn *> (p: thread);
1621
1622	/* Get the first active insn, or THREAD_INSN, if it is an active insn. */
1623	active_insn = next_active_insn (PREV_INSN (insn: thread_insn));
1624
1625	for (insn = thread_insn; insn != active_insn; insn = NEXT_INSN (insn))
1626	if (LABEL_P (insn)
1627	&& (insn != label || LABEL_NUSES (insn) != 1))
1628	return false;
1629
1630	if (allow_fallthrough)
1631	return true;
1632
1633	/* Ensure that we reach a BARRIER before any insn or label. */
1634	for (insn = prev_nonnote_insn (thread_insn);
1635	insn == 0 || !BARRIER_P (insn);
1636	insn = prev_nonnote_insn (insn))
1637	if (insn == 0
1638	|| LABEL_P (insn)
1639	|| (NONJUMP_INSN_P (insn)
1640	&& GET_CODE (PATTERN (insn)) != USE
1641	&& GET_CODE (PATTERN (insn)) != CLOBBER))
1642	return false;
1643
1644	return true;
1645	}
1646
1647	/* Called when INSN is being moved from a location near the target of a jump.
1648	We leave a marker of the form (use (INSN)) immediately in front of WHERE
1649	for mark_target_live_regs. These markers will be deleted at the end.
1650
1651	We used to try to update the live status of registers if WHERE is at
1652	the start of a basic block, but that can't work since we may remove a
1653	BARRIER in relax_delay_slots. */
1654
1655	static void
1656	update_block (rtx_insn *insn, rtx_insn *where)
1657	{
1658	emit_insn_before (gen_rtx_USE (VOIDmode, insn), where);
1659
1660	/* INSN might be making a value live in a block where it didn't use to
1661	be. So recompute liveness information for this block. */
1662	incr_ticks_for_insn (insn);
1663	}
1664
1665	/* Similar to REDIRECT_JUMP except that we update the BB_TICKS entry for
1666	the basic block containing the jump. */
1667
1668	static bool
1669	reorg_redirect_jump (rtx_jump_insn *jump, rtx nlabel)
1670	{
1671	incr_ticks_for_insn (jump);
1672	return redirect_jump (jump, nlabel, 1);
1673	}
1674
1675	/* Called when INSN is being moved forward into a delay slot of DELAYED_INSN.
1676	We check every instruction between INSN and DELAYED_INSN for REG_DEAD notes
1677	that reference values used in INSN. If we find one, then we move the
1678	REG_DEAD note to INSN.
1679
1680	This is needed to handle the case where a later insn (after INSN) has a
1681	REG_DEAD note for a register used by INSN, and this later insn subsequently
1682	gets moved before a CODE_LABEL because it is a redundant insn. In this
1683	case, mark_target_live_regs may be confused into thinking the register
1684	is dead because it sees a REG_DEAD note immediately before a CODE_LABEL. */
1685
1686	static void
1687	update_reg_dead_notes (rtx_insn *insn, rtx_insn *delayed_insn)
1688	{
1689	rtx link, next;
1690	rtx_insn *p;
1691
1692	for (p = next_nonnote_insn (insn); p != delayed_insn;
1693	p = next_nonnote_insn (p))
1694	for (link = REG_NOTES (p); link; link = next)
1695	{
1696	next = XEXP (link, 1);
1697
1698	if (REG_NOTE_KIND (link) != REG_DEAD
1699	|| !REG_P (XEXP (link, 0)))
1700	continue;
1701
1702	if (reg_referenced_p (XEXP (link, 0), PATTERN (insn)))
1703	{
1704	/* Move the REG_DEAD note from P to INSN. */
1705	remove_note (p, link);
1706	XEXP (link, 1) = REG_NOTES (insn);
1707	REG_NOTES (insn) = link;
1708	}
1709	}
1710	}
1711
1712	/* Called when an insn redundant with start_insn is deleted. If there
1713	is a REG_DEAD note for the target of start_insn between start_insn
1714	and stop_insn, then the REG_DEAD note needs to be deleted since the
1715	value no longer dies there.
1716
1717	If the REG_DEAD note isn't deleted, then mark_target_live_regs may be
1718	confused into thinking the register is dead. */
1719
1720	static void
1721	fix_reg_dead_note (rtx_insn *start_insn, rtx stop_insn)
1722	{
1723	rtx link, next;
1724	rtx_insn *p;
1725
1726	for (p = next_nonnote_insn (start_insn); p != stop_insn;
1727	p = next_nonnote_insn (p))
1728	for (link = REG_NOTES (p); link; link = next)
1729	{
1730	next = XEXP (link, 1);
1731
1732	if (REG_NOTE_KIND (link) != REG_DEAD
1733	|| !REG_P (XEXP (link, 0)))
1734	continue;
1735
1736	if (reg_set_p (XEXP (link, 0), PATTERN (insn: start_insn)))
1737	{
1738	remove_note (p, link);
1739	return;
1740	}
1741	}
1742	}
1743
1744	/* Delete any REG_UNUSED notes that exist on INSN but not on OTHER_INSN.
1745
1746	This handles the case of udivmodXi4 instructions which optimize their
1747	output depending on whether any REG_UNUSED notes are present. We must
1748	make sure that INSN calculates as many results as OTHER_INSN does. */
1749
1750	static void
1751	update_reg_unused_notes (rtx_insn *insn, rtx other_insn)
1752	{
1753	rtx link, next;
1754
1755	for (link = REG_NOTES (insn); link; link = next)
1756	{
1757	next = XEXP (link, 1);
1758
1759	if (REG_NOTE_KIND (link) != REG_UNUSED
1760	|| !REG_P (XEXP (link, 0)))
1761	continue;
1762
1763	if (!find_regno_note (other_insn, REG_UNUSED, REGNO (XEXP (link, 0))))
1764	remove_note (insn, link);
1765	}
1766	}
1767
1768	static vec <rtx> sibling_labels;
1769
1770	/* Return the label before INSN, or put a new label there. If SIBLING is
1771	non-zero, it is another label associated with the new label (if any),
1772	typically the former target of the jump that will be redirected to
1773	the new label. */
1774
1775	static rtx_insn *
1776	get_label_before (rtx_insn *insn, rtx sibling)
1777	{
1778	rtx_insn *label;
1779
1780	/* Find an existing label at this point
1781	or make a new one if there is none. */
1782	label = prev_nonnote_insn (insn);
1783
1784	if (label == 0 || !LABEL_P (label))
1785	{
1786	rtx_insn *prev = PREV_INSN (insn);
1787
1788	label = gen_label_rtx ();
1789	emit_label_after (label, prev);
1790	LABEL_NUSES (label) = 0;
1791	if (sibling)
1792	{
1793	sibling_labels.safe_push (obj: label);
1794	sibling_labels.safe_push (obj: sibling);
1795	}
1796	}
1797	return label;
1798	}
1799
1800	/* Scan a function looking for insns that need a delay slot and find insns to
1801	put into the delay slot.
1802
1803	NON_JUMPS_P is true if we are to only try to fill non-jump insns (such
1804	as calls). We do these first since we don't want jump insns (that are
1805	easier to fill) to get the only insns that could be used for non-jump insns.
1806	When it is zero, only try to fill JUMP_INSNs.
1807
1808	When slots are filled in this manner, the insns (including the
1809	delay_insn) are put together in a SEQUENCE rtx. In this fashion,
1810	it is possible to tell whether a delay slot has really been filled
1811	or not. `final' knows how to deal with this, by communicating
1812	through FINAL_SEQUENCE. */
1813
1814	static void
1815	fill_simple_delay_slots (bool non_jumps_p)
1816	{
1817	rtx_insn *insn, *trial, *next_trial;
1818	rtx pat;
1819	int i;
1820	int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
1821	struct resources needed, set;
1822	int slots_to_fill, slots_filled;
1823	auto_vec<rtx_insn *, 5> delay_list;
1824
1825	for (i = 0; i < num_unfilled_slots; i++)
1826	{
1827	int flags;
1828	/* Get the next insn to fill. If it has already had any slots assigned,
1829	we can't do anything with it. Maybe we'll improve this later. */
1830
1831	insn = unfilled_slots_base[i];
1832	if (insn == 0
1833	|| insn->deleted ()
1834	|| (NONJUMP_INSN_P (insn)
1835	&& GET_CODE (PATTERN (insn)) == SEQUENCE)
1836	|| (JUMP_P (insn) && non_jumps_p)
1837	|| (!JUMP_P (insn) && ! non_jumps_p))
1838	continue;
1839
1840	/* It may have been that this insn used to need delay slots, but
1841	now doesn't; ignore in that case. This can happen, for example,
1842	on the HP PA RISC, where the number of delay slots depends on
1843	what insns are nearby. */
1844	slots_to_fill = num_delay_slots (insn);
1845
1846	/* Some machine description have defined instructions to have
1847	delay slots only in certain circumstances which may depend on
1848	nearby insns (which change due to reorg's actions).
1849
1850	For example, the PA port normally has delay slots for unconditional
1851	jumps.
1852
1853	However, the PA port claims such jumps do not have a delay slot
1854	if they are immediate successors of certain CALL_INSNs. This
1855	allows the port to favor filling the delay slot of the call with
1856	the unconditional jump. */
1857	if (slots_to_fill == 0)
1858	continue;
1859
1860	/* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
1861	says how many. After initialization, first try optimizing
1862
1863	call _foo call _foo
1864	nop add %o7,.-L1,%o7
1865	b,a L1
1866	nop
1867
1868	If this case applies, the delay slot of the call is filled with
1869	the unconditional jump. This is done first to avoid having the
1870	delay slot of the call filled in the backward scan. Also, since
1871	the unconditional jump is likely to also have a delay slot, that
1872	insn must exist when it is subsequently scanned.
1873
1874	This is tried on each insn with delay slots as some machines
1875	have insns which perform calls, but are not represented as
1876	CALL_INSNs. */
1877
1878	slots_filled = 0;
1879	delay_list.truncate (size: 0);
1880
1881	if (JUMP_P (insn))
1882	flags = get_jump_flags (insn, JUMP_LABEL (insn));
1883	else
1884	flags = get_jump_flags (insn, NULL_RTX);
1885
1886	if ((trial = next_active_insn (insn))
1887	&& JUMP_P (trial)
1888	&& simplejump_p (trial)
1889	&& eligible_for_delay (insn, slots_filled, trial, flags)
1890	&& no_labels_between_p (insn, trial)
1891	&& ! can_throw_internal (trial))
1892	{
1893	rtx_insn **tmp;
1894	slots_filled++;
1895	add_to_delay_list (insn: trial, delay_list: &delay_list);
1896
1897	/* TRIAL may have had its delay slot filled, then unfilled. When
1898	the delay slot is unfilled, TRIAL is placed back on the unfilled
1899	slots obstack. Unfortunately, it is placed on the end of the
1900	obstack, not in its original location. Therefore, we must search
1901	from entry i + 1 to the end of the unfilled slots obstack to
1902	try and find TRIAL. */
1903	tmp = &unfilled_slots_base[i + 1];
1904	while (*tmp != trial && tmp != unfilled_slots_next)
1905	tmp++;
1906
1907	/* Remove the unconditional jump from consideration for delay slot
1908	filling and unthread it. */
1909	if (*tmp == trial)
1910	*tmp = 0;
1911	{
1912	rtx_insn *next = NEXT_INSN (insn: trial);
1913	rtx_insn *prev = PREV_INSN (insn: trial);
1914	if (prev)
1915	SET_NEXT_INSN (prev) = next;
1916	if (next)
1917	SET_PREV_INSN (next) = prev;
1918	}
1919	}
1920
1921	/* Now, scan backwards from the insn to search for a potential
1922	delay-slot candidate. Stop searching when a label or jump is hit.
1923
1924	For each candidate, if it is to go into the delay slot (moved
1925	forward in execution sequence), it must not need or set any resources
1926	that were set by later insns and must not set any resources that
1927	are needed for those insns.
1928
1929	The delay slot insn itself sets resources unless it is a call
1930	(in which case the called routine, not the insn itself, is doing
1931	the setting). */
1932
1933	if (slots_filled < slots_to_fill)
1934	{
1935	/* If the flags register is dead after the insn, then we want to be
1936	able to accept a candidate that clobbers it. For this purpose,
1937	we need to filter the flags register during life analysis, so
1938	that it doesn't create RAW and WAW dependencies, while still
1939	creating the necessary WAR dependencies. */
1940	bool filter_flags
1941	= (slots_to_fill == 1
1942	&& targetm.flags_regnum != INVALID_REGNUM
1943	&& find_regno_note (insn, REG_DEAD, targetm.flags_regnum));
1944	struct resources fset;
1945	CLEAR_RESOURCE (&needed);
1946	CLEAR_RESOURCE (&set);
1947	mark_set_resources (insn, &set, 0, MARK_SRC_DEST);
1948	if (filter_flags)
1949	{
1950	CLEAR_RESOURCE (&fset);
1951	mark_set_resources (insn, &fset, 0, MARK_SRC_DEST);
1952	}
1953	mark_referenced_resources (insn, &needed, false);
1954
1955	for (trial = prev_nonnote_insn (insn); ! stop_search_p (insn: trial, labels_p: true);
1956	trial = next_trial)
1957	{
1958	next_trial = prev_nonnote_insn (trial);
1959
1960	/* This must be an INSN or CALL_INSN. */
1961	pat = PATTERN (insn: trial);
1962
1963	/* Stand-alone USE and CLOBBER are just for flow. */
1964	if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1965	continue;
1966
1967	/* And DEBUG_INSNs never go into delay slots. */
1968	if (GET_CODE (trial) == DEBUG_INSN)
1969	continue;
1970
1971	/* Check for resource conflict first, to avoid unnecessary
1972	splitting. */
1973	if (! insn_references_resource_p (insn: trial, res: &set, include_delayed_effects: true)
1974	&& ! insn_sets_resource_p (insn: trial,
1975	res: filter_flags ? &fset : &set,
1976	include_delayed_effects: true)
1977	&& ! insn_sets_resource_p (insn: trial, res: &needed, include_delayed_effects: true)
1978	&& ! can_throw_internal (trial))
1979	{
1980	trial = try_split (pat, trial, 1);
1981	next_trial = prev_nonnote_insn (trial);
1982	if (eligible_for_delay (insn, slots_filled, trial, flags))
1983	{
1984	/* In this case, we are searching backward, so if we
1985	find insns to put on the delay list, we want
1986	to put them at the head, rather than the
1987	tail, of the list. */
1988
1989	update_reg_dead_notes (insn: trial, delayed_insn: insn);
1990	delay_list.safe_insert (ix: 0, obj: trial);
1991	update_block (insn: trial, where: trial);
1992	delete_related_insns (trial);
1993	if (slots_to_fill == ++slots_filled)
1994	break;
1995	continue;
1996	}
1997	}
1998
1999	mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2000	if (filter_flags)
2001	{
2002	mark_set_resources (trial, &fset, 0, MARK_SRC_DEST_CALL);
2003	/* If the flags register is set, then it doesn't create RAW
2004	dependencies any longer and it also doesn't create WAW
2005	dependencies since it's dead after the original insn. */
2006	if (TEST_HARD_REG_BIT (set: fset.regs, bit: targetm.flags_regnum))
2007	{
2008	CLEAR_HARD_REG_BIT (set&: needed.regs, bit: targetm.flags_regnum);
2009	CLEAR_HARD_REG_BIT (set&: fset.regs, bit: targetm.flags_regnum);
2010	}
2011	}
2012	mark_referenced_resources (trial, &needed, true);
2013	}
2014	}
2015
2016	/* If all needed slots haven't been filled, we come here. */
2017
2018	/* Try to optimize case of jumping around a single insn. */
2019	if ((ANNUL_IFTRUE_SLOTS || ANNUL_IFFALSE_SLOTS)
2020	&& slots_filled != slots_to_fill
2021	&& delay_list.is_empty ()
2022	&& JUMP_P (insn)
2023	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
2024	&& !ANY_RETURN_P (JUMP_LABEL (insn)))
2025	{
2026	optimize_skip (insn: as_a <rtx_jump_insn *> (p: insn), delay_list: &delay_list);
2027	if (!delay_list.is_empty ())
2028	slots_filled += 1;
2029	}
2030
2031	/* Try to get insns from beyond the insn needing the delay slot.
2032	These insns can neither set or reference resources set in insns being
2033	skipped, cannot set resources in the insn being skipped, and, if this
2034	is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2035	call might not return).
2036
2037	There used to be code which continued past the target label if
2038	we saw all uses of the target label. This code did not work,
2039	because it failed to account for some instructions which were
2040	both annulled and marked as from the target. This can happen as a
2041	result of optimize_skip. Since this code was redundant with
2042	fill_eager_delay_slots anyways, it was just deleted. */
2043
2044	if (slots_filled != slots_to_fill
2045	/* If this instruction could throw an exception which is
2046	caught in the same function, then it's not safe to fill
2047	the delay slot with an instruction from beyond this
2048	point. For example, consider:
2049
2050	int i = 2;
2051
2052	try {
2053	f();
2054	i = 3;
2055	} catch (...) {}
2056
2057	return i;
2058
2059	Even though `i' is a local variable, we must be sure not
2060	to put `i = 3' in the delay slot if `f' might throw an
2061	exception.
2062
2063	Presumably, we should also check to see if we could get
2064	back to this function via `setjmp'. */
2065	&& ! can_throw_internal (insn)
2066	&& !JUMP_P (insn))
2067	{
2068	bool maybe_never = false;
2069	rtx pat, trial_delay;
2070
2071	CLEAR_RESOURCE (&needed);
2072	CLEAR_RESOURCE (&set);
2073	mark_set_resources (insn, &set, 0, MARK_SRC_DEST_CALL);
2074	mark_referenced_resources (insn, &needed, true);
2075
2076	if (CALL_P (insn))
2077	maybe_never = true;
2078
2079	for (trial = next_nonnote_insn (insn); !stop_search_p (insn: trial, labels_p: true);
2080	trial = next_trial)
2081	{
2082	next_trial = next_nonnote_insn (trial);
2083
2084	/* This must be an INSN or CALL_INSN. */
2085	pat = PATTERN (insn: trial);
2086
2087	/* Stand-alone USE and CLOBBER are just for flow. */
2088	if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2089	continue;
2090
2091	/* And DEBUG_INSNs do not go in delay slots. */
2092	if (GET_CODE (trial) == DEBUG_INSN)
2093	continue;
2094
2095	/* If this already has filled delay slots, get the insn needing
2096	the delay slots. */
2097	if (GET_CODE (pat) == SEQUENCE)
2098	trial_delay = XVECEXP (pat, 0, 0);
2099	else
2100	trial_delay = trial;
2101
2102	/* Stop our search when seeing a jump. */
2103	if (JUMP_P (trial_delay))
2104	break;
2105
2106	/* See if we have a resource problem before we try to split. */
2107	if (GET_CODE (pat) != SEQUENCE
2108	&& ! insn_references_resource_p (insn: trial, res: &set, include_delayed_effects: true)
2109	&& ! insn_sets_resource_p (insn: trial, res: &set, include_delayed_effects: true)
2110	&& ! insn_sets_resource_p (insn: trial, res: &needed, include_delayed_effects: true)
2111	&& ! (maybe_never && may_trap_or_fault_p (pat))
2112	&& (trial = try_split (pat, trial, 0))
2113	&& eligible_for_delay (insn, slots_filled, trial, flags)
2114	&& ! can_throw_internal (trial))
2115	{
2116	next_trial = next_nonnote_insn (trial);
2117	add_to_delay_list (insn: trial, delay_list: &delay_list);
2118
2119	delete_related_insns (trial);
2120	if (slots_to_fill == ++slots_filled)
2121	break;
2122	continue;
2123	}
2124
2125	mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2126	mark_referenced_resources (trial, &needed, true);
2127
2128	/* Ensure we don't put insns between the setting of cc and the
2129	comparison by moving a setting of cc into an earlier delay
2130	slot since these insns could clobber the condition code. */
2131	set.cc = 1;
2132
2133	/* If this is a call, we might not get here. */
2134	if (CALL_P (trial_delay))
2135	maybe_never = true;
2136	}
2137
2138	/* If there are slots left to fill and our search was stopped by an
2139	unconditional branch, try the insn at the branch target. We can
2140	redirect the branch if it works.
2141
2142	Don't do this if the insn at the branch target is a branch. */
2143	if (slots_to_fill != slots_filled
2144	&& trial
2145	&& jump_to_label_p (trial)
2146	&& simplejump_p (trial)
2147	&& (next_trial = next_active_insn (JUMP_LABEL_AS_INSN (insn: trial))) != 0
2148	&& ! (NONJUMP_INSN_P (next_trial)
2149	&& GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2150	&& !JUMP_P (next_trial)
2151	&& ! insn_references_resource_p (insn: next_trial, res: &set, include_delayed_effects: true)
2152	&& ! insn_sets_resource_p (insn: next_trial, res: &set, include_delayed_effects: true)
2153	&& ! insn_sets_resource_p (insn: next_trial, res: &needed, include_delayed_effects: true)
2154	&& ! (maybe_never && may_trap_or_fault_p (PATTERN (insn: next_trial)))
2155	&& (next_trial = try_split (PATTERN (insn: next_trial), next_trial, 0))
2156	&& eligible_for_delay (insn, slots_filled, next_trial, flags)
2157	&& ! can_throw_internal (trial))
2158	{
2159	/* See comment in relax_delay_slots about necessity of using
2160	next_real_nondebug_insn here. */
2161	rtx_insn *new_label = next_real_nondebug_insn (next_trial);
2162
2163	if (new_label != 0)
2164	new_label = get_label_before (insn: new_label, JUMP_LABEL (trial));
2165	else
2166	new_label = find_end_label (kind: simple_return_rtx);
2167
2168	if (new_label)
2169	{
2170	add_to_delay_list (insn: copy_delay_slot_insn (next_trial),
2171	delay_list: &delay_list);
2172	slots_filled++;
2173	reorg_redirect_jump (jump: as_a <rtx_jump_insn *> (p: trial),
2174	nlabel: new_label);
2175	}
2176	}
2177	}
2178
2179	/* If this is an unconditional jump, then try to get insns from the
2180	target of the jump. */
2181	rtx_jump_insn *jump_insn;
2182	if ((jump_insn = dyn_cast <rtx_jump_insn *> (p: insn))
2183	&& simplejump_p (jump_insn)
2184	&& slots_filled != slots_to_fill)
2185	fill_slots_from_thread (jump_insn, const_true_rtx,
2186	next_active_insn (JUMP_LABEL_AS_INSN (insn)),
2187	NULL, 1, 1, own_thread_p (JUMP_LABEL (insn),
2188	JUMP_LABEL (insn), allow_fallthrough: false),
2189	slots_to_fill, &slots_filled, &delay_list);
2190
2191	if (!delay_list.is_empty ())
2192	unfilled_slots_base[i]
2193	= emit_delay_sequence (insn, list: delay_list, length: slots_filled);
2194
2195	if (slots_to_fill == slots_filled)
2196	unfilled_slots_base[i] = 0;
2197
2198	note_delay_statistics (slots_filled, index: 0);
2199	}
2200	}
2201
2202	/* Follow any unconditional jump at LABEL, for the purpose of redirecting JUMP;
2203	return the ultimate label reached by any such chain of jumps.
2204	Return a suitable return rtx if the chain ultimately leads to a
2205	return instruction.
2206	If LABEL is not followed by a jump, return LABEL.
2207	If the chain loops or we can't find end, return LABEL,
2208	since that tells caller to avoid changing the insn.
2209	If the returned label is obtained by following a crossing jump,
2210	set *CROSSING to true, otherwise set it to false. */
2211
2212	static rtx
2213	follow_jumps (rtx label, rtx_insn *jump, bool *crossing)
2214	{
2215	rtx_insn *insn;
2216	rtx_insn *next;
2217	int depth;
2218
2219	*crossing = false;
2220	if (ANY_RETURN_P (label))
2221	return label;
2222
2223	rtx_insn *value = as_a <rtx_insn *> (p: label);
2224
2225	for (depth = 0;
2226	(depth < 10
2227	&& (insn = next_active_insn (value)) != 0
2228	&& JUMP_P (insn)
2229	&& JUMP_LABEL (insn) != NULL_RTX
2230	&& ((any_uncondjump_p (insn) && onlyjump_p (insn))
2231	|| ANY_RETURN_P (PATTERN (insn)))
2232	&& (next = NEXT_INSN (insn))
2233	&& BARRIER_P (next));
2234	depth++)
2235	{
2236	rtx this_label_or_return = JUMP_LABEL (insn);
2237
2238	/* If we have found a cycle, make the insn jump to itself. */
2239	if (this_label_or_return == label)
2240	return label;
2241
2242	/* Cannot follow returns and cannot look through tablejumps. */
2243	if (ANY_RETURN_P (this_label_or_return))
2244	return this_label_or_return;
2245
2246	rtx_insn *this_label = as_a <rtx_insn *> (p: this_label_or_return);
2247	if (NEXT_INSN (insn: this_label)
2248	&& JUMP_TABLE_DATA_P (NEXT_INSN (this_label)))
2249	break;
2250
2251	if (!targetm.can_follow_jump (jump, insn))
2252	break;
2253	if (!*crossing)
2254	*crossing = CROSSING_JUMP_P (jump);
2255	value = this_label;
2256	}
2257	if (depth == 10)
2258	return label;
2259	return value;
2260	}
2261
2262	/* Try to find insns to place in delay slots.
2263
2264	INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2265	or is an unconditional branch if CONDITION is const_true_rtx.
2266	*PSLOTS_FILLED is updated with the number of slots that we have filled.
2267
2268	THREAD is a flow-of-control, either the insns to be executed if the
2269	branch is true or if the branch is false, THREAD_IF_TRUE says which.
2270
2271	OPPOSITE_THREAD is the thread in the opposite direction. It is used
2272	to see if any potential delay slot insns set things needed there.
2273
2274	LIKELY is true if it is extremely likely that the branch will be
2275	taken and THREAD_IF_TRUE is set. This is used for the branch at the
2276	end of a loop back up to the top.
2277
2278	OWN_THREAD is true if we are the only user of the thread, i.e. it is
2279	the target of the jump when we are the only jump going there.
2280
2281	If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2282	case, we can only take insns from the head of the thread for our delay
2283	slot. We then adjust the jump to point after the insns we have taken. */
2284
2285	static void
2286	fill_slots_from_thread (rtx_jump_insn *insn, rtx condition,
2287	rtx thread_or_return, rtx opposite_thread, bool likely,
2288	bool thread_if_true, bool own_thread, int slots_to_fill,
2289	int *pslots_filled, vec<rtx_insn *> *delay_list)
2290	{
2291	rtx new_thread;
2292	struct resources opposite_needed, set, needed;
2293	rtx_insn *trial;
2294	bool lose = false;
2295	bool must_annul = false;
2296	int flags;
2297
2298	/* Validate our arguments. */
2299	gcc_assert (condition != const_true_rtx || thread_if_true);
2300	gcc_assert (own_thread || thread_if_true);
2301
2302	flags = get_jump_flags (insn, JUMP_LABEL (insn));
2303
2304	/* If our thread is the end of subroutine, we can't get any delay
2305	insns from that. */
2306	if (thread_or_return == NULL_RTX || ANY_RETURN_P (thread_or_return))
2307	return;
2308
2309	rtx_insn *thread = as_a <rtx_insn *> (p: thread_or_return);
2310
2311	/* If this is an unconditional branch, nothing is needed at the
2312	opposite thread. Otherwise, compute what is needed there. */
2313	if (condition == const_true_rtx)
2314	CLEAR_RESOURCE (&opposite_needed);
2315	else
2316	mark_target_live_regs (get_insns (), opposite_thread, &opposite_needed);
2317
2318	/* If the insn at THREAD can be split, do it here to avoid having to
2319	update THREAD and NEW_THREAD if it is done in the loop below. Also
2320	initialize NEW_THREAD. */
2321
2322	new_thread = thread = try_split (PATTERN (insn: thread), thread, 0);
2323
2324	/* Scan insns at THREAD. We are looking for an insn that can be removed
2325	from THREAD (it neither sets nor references resources that were set
2326	ahead of it and it doesn't set anything needs by the insns ahead of
2327	it) and that either can be placed in an annulling insn or aren't
2328	needed at OPPOSITE_THREAD. */
2329
2330	CLEAR_RESOURCE (&needed);
2331	CLEAR_RESOURCE (&set);
2332
2333	/* Handle the flags register specially, to be able to accept a
2334	candidate that clobbers it. See also fill_simple_delay_slots. */
2335	bool filter_flags
2336	= (slots_to_fill == 1
2337	&& targetm.flags_regnum != INVALID_REGNUM
2338	&& find_regno_note (insn, REG_DEAD, targetm.flags_regnum));
2339	struct resources fset;
2340	struct resources flags_res;
2341	if (filter_flags)
2342	{
2343	CLEAR_RESOURCE (&fset);
2344	CLEAR_RESOURCE (&flags_res);
2345	SET_HARD_REG_BIT (set&: flags_res.regs, bit: targetm.flags_regnum);
2346	}
2347
2348	/* If we do not own this thread, we must stop as soon as we find
2349	something that we can't put in a delay slot, since all we can do
2350	is branch into THREAD at a later point. Therefore, labels stop
2351	the search if this is not the `true' thread. */
2352
2353	for (trial = thread;
2354	! stop_search_p (insn: trial, labels_p: ! thread_if_true) && (! lose || own_thread);
2355	trial = next_nonnote_insn (trial))
2356	{
2357	rtx pat, old_trial;
2358
2359	/* If we have passed a label, we no longer own this thread. */
2360	if (LABEL_P (trial))
2361	{
2362	own_thread = 0;
2363	continue;
2364	}
2365
2366	pat = PATTERN (insn: trial);
2367	if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2368	continue;
2369
2370	if (GET_CODE (trial) == DEBUG_INSN)
2371	continue;
2372
2373	/* If TRIAL conflicts with the insns ahead of it, we lose. */
2374	if (! insn_references_resource_p (insn: trial, res: &set, include_delayed_effects: true)
2375	&& ! insn_sets_resource_p (insn: trial, res: filter_flags ? &fset : &set, include_delayed_effects: true)
2376	&& ! insn_sets_resource_p (insn: trial, res: &needed, include_delayed_effects: true)
2377	/* If we're handling sets to the flags register specially, we
2378	only allow an insn into a delay-slot, if it either:
2379	- doesn't set the flags register,
2380	- the "set" of the flags register isn't used (clobbered),
2381	- insns between the delay-slot insn and the trial-insn
2382	as accounted in "set", have not affected the flags register. */
2383	&& (! filter_flags
2384	|| ! insn_sets_resource_p (insn: trial, res: &flags_res, include_delayed_effects: true)
2385	|| find_regno_note (trial, REG_UNUSED, targetm.flags_regnum)
2386	|| ! TEST_HARD_REG_BIT (set: set.regs, bit: targetm.flags_regnum))
2387	&& ! can_throw_internal (trial))
2388	{
2389	rtx_insn *prior_insn;
2390
2391	/* If TRIAL is redundant with some insn before INSN, we don't
2392	actually need to add it to the delay list; we can merely pretend
2393	we did. */
2394	if ((prior_insn = redundant_insn (insn: trial, target: insn, delay_list: *delay_list)))
2395	{
2396	fix_reg_dead_note (start_insn: prior_insn, stop_insn: insn);
2397	if (own_thread)
2398	{
2399	update_block (insn: trial, where: thread);
2400	if (trial == thread)
2401	{
2402	thread = next_active_insn (thread);
2403	if (new_thread == trial)
2404	new_thread = thread;
2405	}
2406
2407	delete_related_insns (trial);
2408	}
2409	else
2410	{
2411	update_reg_unused_notes (insn: prior_insn, other_insn: trial);
2412	new_thread = next_active_insn (trial);
2413	}
2414
2415	continue;
2416	}
2417
2418	/* There are two ways we can win: If TRIAL doesn't set anything
2419	needed at the opposite thread and can't trap, or if it can
2420	go into an annulled delay slot. But we want neither to copy
2421	nor to speculate frame-related insns. */
2422	if (!must_annul
2423	&& ((condition == const_true_rtx
2424	&& (own_thread || !RTX_FRAME_RELATED_P (trial)))
2425	|| (! insn_sets_resource_p (insn: trial, res: &opposite_needed, include_delayed_effects: true)
2426	&& ! may_trap_or_fault_p (pat)
2427	&& ! RTX_FRAME_RELATED_P (trial))))
2428	{
2429	old_trial = trial;
2430	trial = try_split (pat, trial, 0);
2431	if (new_thread == old_trial)
2432	new_thread = trial;
2433	if (thread == old_trial)
2434	thread = trial;
2435	pat = PATTERN (insn: trial);
2436	if (eligible_for_delay (insn, *pslots_filled, trial, flags))
2437	goto winner;
2438	}
2439	else if (!RTX_FRAME_RELATED_P (trial)
2440	&& ((ANNUL_IFTRUE_SLOTS && ! thread_if_true)
2441	|| (ANNUL_IFFALSE_SLOTS && thread_if_true)))
2442	{
2443	old_trial = trial;
2444	trial = try_split (pat, trial, 0);
2445	if (new_thread == old_trial)
2446	new_thread = trial;
2447	if (thread == old_trial)
2448	thread = trial;
2449	pat = PATTERN (insn: trial);
2450	if ((must_annul || delay_list->is_empty ()) && (thread_if_true
2451	? check_annul_list_true_false (annul_true_p: false, delay_list: *delay_list)
2452	&& eligible_for_annul_false (insn, *pslots_filled, trial, flags)
2453	: check_annul_list_true_false (annul_true_p: true, delay_list: *delay_list)
2454	&& eligible_for_annul_true (insn, *pslots_filled, trial, flags)))
2455	{
2456	rtx_insn *temp;
2457
2458	must_annul = true;
2459	winner:
2460
2461	/* If we own this thread, delete the insn. If this is the
2462	destination of a branch, show that a basic block status
2463	may have been updated. In any case, mark the new
2464	starting point of this thread. */
2465	if (own_thread)
2466	{
2467	rtx note;
2468
2469	update_block (insn: trial, where: thread);
2470	if (trial == thread)
2471	{
2472	thread = next_active_insn (thread);
2473	if (new_thread == trial)
2474	new_thread = thread;
2475	}
2476
2477	/* We are moving this insn, not deleting it. We must
2478	temporarily increment the use count on any referenced
2479	label lest it be deleted by delete_related_insns. */
2480	for (note = REG_NOTES (trial);
2481	note != NULL_RTX;
2482	note = XEXP (note, 1))
2483	if (REG_NOTE_KIND (note) == REG_LABEL_OPERAND
2484	|| REG_NOTE_KIND (note) == REG_LABEL_TARGET)
2485	{
2486	/* REG_LABEL_OPERAND could be
2487	NOTE_INSN_DELETED_LABEL too. */
2488	if (LABEL_P (XEXP (note, 0)))
2489	LABEL_NUSES (XEXP (note, 0))++;
2490	else
2491	gcc_assert (REG_NOTE_KIND (note)
2492	== REG_LABEL_OPERAND);
2493	}
2494	if (jump_to_label_p (trial))
2495	LABEL_NUSES (JUMP_LABEL (trial))++;
2496
2497	delete_related_insns (trial);
2498
2499	for (note = REG_NOTES (trial);
2500	note != NULL_RTX;
2501	note = XEXP (note, 1))
2502	if (REG_NOTE_KIND (note) == REG_LABEL_OPERAND
2503	|| REG_NOTE_KIND (note) == REG_LABEL_TARGET)
2504	{
2505	/* REG_LABEL_OPERAND could be
2506	NOTE_INSN_DELETED_LABEL too. */
2507	if (LABEL_P (XEXP (note, 0)))
2508	LABEL_NUSES (XEXP (note, 0))--;
2509	else
2510	gcc_assert (REG_NOTE_KIND (note)
2511	== REG_LABEL_OPERAND);
2512	}
2513	if (jump_to_label_p (trial))
2514	LABEL_NUSES (JUMP_LABEL (trial))--;
2515	}
2516	else
2517	new_thread = next_active_insn (trial);
2518
2519	temp = own_thread ? trial : copy_delay_slot_insn (trial);
2520	if (thread_if_true)
2521	INSN_FROM_TARGET_P (temp) = 1;
2522
2523	add_to_delay_list (insn: temp, delay_list);
2524
2525	if (slots_to_fill == ++(*pslots_filled))
2526	{
2527	/* Even though we have filled all the slots, we
2528	may be branching to a location that has a
2529	redundant insn. Skip any if so. */
2530	while (new_thread && ! own_thread
2531	&& ! insn_sets_resource_p (insn: new_thread, res: &set, include_delayed_effects: true)
2532	&& ! insn_sets_resource_p (insn: new_thread, res: &needed,
2533	include_delayed_effects: true)
2534	&& ! insn_references_resource_p (insn: new_thread,
2535	res: &set, include_delayed_effects: true)
2536	&& (prior_insn
2537	= redundant_insn (insn: new_thread, target: insn,
2538	delay_list: *delay_list)))
2539	{
2540	/* We know we do not own the thread, so no need
2541	to call update_block and delete_insn. */
2542	fix_reg_dead_note (start_insn: prior_insn, stop_insn: insn);
2543	update_reg_unused_notes (insn: prior_insn, other_insn: new_thread);
2544	new_thread
2545	= next_active_insn (as_a<rtx_insn *> (p: new_thread));
2546	}
2547	break;
2548	}
2549
2550	continue;
2551	}
2552	}
2553	}
2554
2555	/* This insn can't go into a delay slot. */
2556	lose = true;
2557	mark_set_resources (trial, &set, 0, MARK_SRC_DEST_CALL);
2558	mark_referenced_resources (trial, &needed, true);
2559	if (filter_flags)
2560	{
2561	mark_set_resources (trial, &fset, 0, MARK_SRC_DEST_CALL);
2562
2563	/* Groups of flags-register setters with users should not
2564	affect opportunities to move flags-register-setting insns
2565	(clobbers) into the delay-slot. */
2566	CLEAR_HARD_REG_BIT (set&: needed.regs, bit: targetm.flags_regnum);
2567	CLEAR_HARD_REG_BIT (set&: fset.regs, bit: targetm.flags_regnum);
2568	}
2569
2570	/* Ensure we don't put insns between the setting of cc and the comparison
2571	by moving a setting of cc into an earlier delay slot since these insns
2572	could clobber the condition code. */
2573	set.cc = 1;
2574
2575	/* If this insn is a register-register copy and the next insn has
2576	a use of our destination, change it to use our source. That way,
2577	it will become a candidate for our delay slot the next time
2578	through this loop. This case occurs commonly in loops that
2579	scan a list.
2580
2581	We could check for more complex cases than those tested below,
2582	but it doesn't seem worth it. It might also be a good idea to try
2583	to swap the two insns. That might do better.
2584
2585	We can't do this if the next insn modifies our destination, because
2586	that would make the replacement into the insn invalid. We also can't
2587	do this if it modifies our source, because it might be an earlyclobber
2588	operand. This latter test also prevents updating the contents of
2589	a PRE_INC. We also can't do this if there's overlap of source and
2590	destination. Overlap may happen for larger-than-register-size modes. */
2591
2592	if (NONJUMP_INSN_P (trial) && GET_CODE (pat) == SET
2593	&& REG_P (SET_SRC (pat))
2594	&& REG_P (SET_DEST (pat))
2595	&& !reg_overlap_mentioned_p (SET_DEST (pat), SET_SRC (pat)))
2596	{
2597	rtx_insn *next = next_nonnote_insn (trial);
2598
2599	if (next && NONJUMP_INSN_P (next)
2600	&& GET_CODE (PATTERN (next)) != USE
2601	&& ! reg_set_p (SET_DEST (pat), next)
2602	&& ! reg_set_p (SET_SRC (pat), next)
2603	&& reg_referenced_p (SET_DEST (pat), PATTERN (insn: next))
2604	&& ! modified_in_p (SET_DEST (pat), next))
2605	validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2606	}
2607	}
2608
2609	/* If we stopped on a branch insn that has delay slots, see if we can
2610	steal some of the insns in those slots. */
2611	if (trial && NONJUMP_INSN_P (trial)
2612	&& GET_CODE (PATTERN (trial)) == SEQUENCE
2613	&& JUMP_P (XVECEXP (PATTERN (trial), 0, 0)))
2614	{
2615	rtx_sequence *sequence = as_a <rtx_sequence *> (p: PATTERN (insn: trial));
2616	/* If this is the `true' thread, we will want to follow the jump,
2617	so we can only do this if we have taken everything up to here. */
2618	if (thread_if_true && trial == new_thread)
2619	{
2620	steal_delay_list_from_target (insn, condition, seq: sequence,
2621	delay_list, sets: &set, needed: &needed,
2622	other_needed: &opposite_needed, slots_to_fill,
2623	pslots_filled, pannul_p: &must_annul,
2624	pnew_thread: &new_thread);
2625	/* If we owned the thread and are told that it branched
2626	elsewhere, make sure we own the thread at the new location. */
2627	if (own_thread && trial != new_thread)
2628	own_thread = own_thread_p (thread: new_thread, label: new_thread, allow_fallthrough: false);
2629	}
2630	else if (! thread_if_true)
2631	steal_delay_list_from_fallthrough (insn, condition, seq: sequence,
2632	delay_list, sets: &set, needed: &needed,
2633	other_needed: &opposite_needed, slots_to_fill,
2634	pslots_filled, pannul_p: &must_annul);
2635	}
2636
2637	/* If we haven't found anything for this delay slot and it is very
2638	likely that the branch will be taken, see if the insn at our target
2639	increments or decrements a register with an increment that does not
2640	depend on the destination register. If so, try to place the opposite
2641	arithmetic insn after the jump insn and put the arithmetic insn in the
2642	delay slot. If we can't do this, return. */
2643	if (delay_list->is_empty () && likely
2644	&& new_thread
2645	&& !ANY_RETURN_P (new_thread)
2646	&& NONJUMP_INSN_P (new_thread)
2647	&& !RTX_FRAME_RELATED_P (new_thread)
2648	&& GET_CODE (PATTERN (new_thread)) != ASM_INPUT
2649	&& asm_noperands (PATTERN (insn: new_thread)) < 0)
2650	{
2651	rtx dest;
2652	rtx src;
2653
2654	/* We know "new_thread" is an insn due to NONJUMP_INSN_P (new_thread)
2655	above. */
2656	trial = as_a <rtx_insn *> (p: new_thread);
2657	rtx pat = PATTERN (insn: trial);
2658
2659	if (!NONJUMP_INSN_P (trial)
2660	|| GET_CODE (pat) != SET
2661	|| ! eligible_for_delay (insn, 0, trial, flags)
2662	|| can_throw_internal (trial))
2663	return;
2664
2665	dest = SET_DEST (pat), src = SET_SRC (pat);
2666	if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2667	&& rtx_equal_p (XEXP (src, 0), dest)
2668	&& (!FLOAT_MODE_P (GET_MODE (src))
2669	|| flag_unsafe_math_optimizations)
2670	&& ! reg_overlap_mentioned_p (dest, XEXP (src, 1))
2671	&& ! side_effects_p (pat))
2672	{
2673	rtx other = XEXP (src, 1);
2674	rtx new_arith;
2675	rtx_insn *ninsn;
2676
2677	/* If this is a constant adjustment, use the same code with
2678	the negated constant. Otherwise, reverse the sense of the
2679	arithmetic. */
2680	if (CONST_INT_P (other))
2681	new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
2682	negate_rtx (GET_MODE (src), other));
2683	else
2684	new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
2685	GET_MODE (src), dest, other);
2686
2687	ninsn = emit_insn_after (gen_rtx_SET (dest, new_arith), insn);
2688
2689	if (recog_memoized (insn: ninsn) < 0
2690	|| (extract_insn (ninsn),
2691	!constrain_operands (1, get_preferred_alternatives (ninsn))))
2692	{
2693	delete_related_insns (ninsn);
2694	return;
2695	}
2696
2697	if (own_thread)
2698	{
2699	update_block (insn: trial, where: thread);
2700	if (trial == thread)
2701	{
2702	thread = next_active_insn (thread);
2703	if (new_thread == trial)
2704	new_thread = thread;
2705	}
2706	delete_related_insns (trial);
2707	}
2708	else
2709	new_thread = next_active_insn (trial);
2710
2711	ninsn = own_thread ? trial : copy_delay_slot_insn (trial);
2712	if (thread_if_true)
2713	INSN_FROM_TARGET_P (ninsn) = 1;
2714
2715	add_to_delay_list (insn: ninsn, delay_list);
2716	(*pslots_filled)++;
2717	}
2718	}
2719
2720	if (!delay_list->is_empty () && must_annul)
2721	INSN_ANNULLED_BRANCH_P (insn) = 1;
2722
2723	/* If we are to branch into the middle of this thread, find an appropriate
2724	label or make a new one if none, and redirect INSN to it. If we hit the
2725	end of the function, use the end-of-function label. */
2726	if (new_thread != thread)
2727	{
2728	rtx label;
2729	bool crossing = false;
2730
2731	gcc_assert (thread_if_true);
2732
2733	if (new_thread
2734	&& simplejump_or_return_p (insn: new_thread)
2735	&& redirect_with_delay_list_safe_p (jump: insn,
2736	JUMP_LABEL (new_thread),
2737	delay_list: *delay_list))
2738	new_thread = follow_jumps (JUMP_LABEL (new_thread), jump: insn, crossing: &crossing);
2739
2740	if (!new_thread)
2741	label = find_end_label (kind: simple_return_rtx);
2742	else if (ANY_RETURN_P (new_thread))
2743	label = find_end_label (kind: new_thread);
2744	else if (LABEL_P (new_thread))
2745	label = new_thread;
2746	else
2747	label = get_label_before (insn: as_a <rtx_insn *> (p: new_thread),
2748	JUMP_LABEL (insn));
2749
2750	if (label)
2751	{
2752	reorg_redirect_jump (jump: insn, nlabel: label);
2753	if (crossing)
2754	CROSSING_JUMP_P (insn) = 1;
2755	}
2756	}
2757	}
2758
2759	/* Make another attempt to find insns to place in delay slots.
2760
2761	We previously looked for insns located in front of the delay insn
2762	and, for non-jump delay insns, located behind the delay insn.
2763
2764	Here only try to schedule jump insns and try to move insns from either
2765	the target or the following insns into the delay slot. If annulling is
2766	supported, we will be likely to do this. Otherwise, we can do this only
2767	if safe. */
2768
2769	static void
2770	fill_eager_delay_slots (void)
2771	{
2772	rtx_insn *insn;
2773	int i;
2774	int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2775
2776	for (i = 0; i < num_unfilled_slots; i++)
2777	{
2778	rtx condition;
2779	rtx target_label, insn_at_target;
2780	rtx_insn *fallthrough_insn;
2781	auto_vec<rtx_insn *, 5> delay_list;
2782	rtx_jump_insn *jump_insn;
2783	bool own_target;
2784	bool own_fallthrough;
2785	int prediction, slots_to_fill, slots_filled;
2786
2787	insn = unfilled_slots_base[i];
2788	if (insn == 0
2789	|| insn->deleted ()
2790	|| ! (jump_insn = dyn_cast <rtx_jump_insn *> (p: insn))
2791	|| ! (condjump_p (jump_insn) || condjump_in_parallel_p (jump_insn)))
2792	continue;
2793
2794	slots_to_fill = num_delay_slots (jump_insn);
2795	/* Some machine description have defined instructions to have
2796	delay slots only in certain circumstances which may depend on
2797	nearby insns (which change due to reorg's actions).
2798
2799	For example, the PA port normally has delay slots for unconditional
2800	jumps.
2801
2802	However, the PA port claims such jumps do not have a delay slot
2803	if they are immediate successors of certain CALL_INSNs. This
2804	allows the port to favor filling the delay slot of the call with
2805	the unconditional jump. */
2806	if (slots_to_fill == 0)
2807	continue;
2808
2809	slots_filled = 0;
2810	target_label = JUMP_LABEL (jump_insn);
2811	condition = get_branch_condition (insn: jump_insn, target: target_label);
2812
2813	if (condition == 0)
2814	continue;
2815
2816	/* Get the next active fallthrough and target insns and see if we own
2817	them. Then see whether the branch is likely true. We don't need
2818	to do a lot of this for unconditional branches. */
2819
2820	insn_at_target = first_active_target_insn (insn: target_label);
2821	own_target = own_thread_p (thread: target_label, label: target_label, allow_fallthrough: false);
2822
2823	if (condition == const_true_rtx)
2824	{
2825	own_fallthrough = false;
2826	fallthrough_insn = 0;
2827	prediction = 2;
2828	}
2829	else
2830	{
2831	fallthrough_insn = next_active_insn (jump_insn);
2832	own_fallthrough = own_thread_p (thread: NEXT_INSN (insn: jump_insn),
2833	NULL_RTX, allow_fallthrough: true);
2834	prediction = mostly_true_jump (jump_insn);
2835	}
2836
2837	/* If this insn is expected to branch, first try to get insns from our
2838	target, then our fallthrough insns. If it is not expected to branch,
2839	try the other order. */
2840
2841	if (prediction > 0)
2842	{
2843	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: insn_at_target,
2844	opposite_thread: fallthrough_insn, likely: prediction == 2, thread_if_true: true,
2845	own_thread: own_target, slots_to_fill,
2846	pslots_filled: &slots_filled, delay_list: &delay_list);
2847
2848	if (delay_list.is_empty () && own_fallthrough)
2849	{
2850	/* Even though we didn't find anything for delay slots,
2851	we might have found a redundant insn which we deleted
2852	from the thread that was filled. So we have to recompute
2853	the next insn at the target. */
2854	target_label = JUMP_LABEL (jump_insn);
2855	insn_at_target = first_active_target_insn (insn: target_label);
2856
2857	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: fallthrough_insn,
2858	opposite_thread: insn_at_target, likely: false, thread_if_true: false,
2859	own_thread: own_fallthrough, slots_to_fill,
2860	pslots_filled: &slots_filled, delay_list: &delay_list);
2861	}
2862	}
2863	else
2864	{
2865	if (own_fallthrough)
2866	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: fallthrough_insn,
2867	opposite_thread: insn_at_target, likely: false, thread_if_true: false,
2868	own_thread: own_fallthrough, slots_to_fill,
2869	pslots_filled: &slots_filled, delay_list: &delay_list);
2870
2871	if (delay_list.is_empty ())
2872	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: insn_at_target,
2873	opposite_thread: next_active_insn (insn), likely: false, thread_if_true: true,
2874	own_thread: own_target, slots_to_fill,
2875	pslots_filled: &slots_filled, delay_list: &delay_list);
2876	}
2877
2878	if (!delay_list.is_empty ())
2879	unfilled_slots_base[i]
2880	= emit_delay_sequence (insn: jump_insn, list: delay_list, length: slots_filled);
2881
2882	if (slots_to_fill == slots_filled)
2883	unfilled_slots_base[i] = 0;
2884
2885	note_delay_statistics (slots_filled, index: 1);
2886	}
2887	}
2888
2889	static void delete_computation (rtx_insn *insn);
2890
2891	/* Recursively delete prior insns that compute the value (used only by INSN
2892	which the caller is deleting) stored in the register mentioned by NOTE
2893	which is a REG_DEAD note associated with INSN. */
2894
2895	static void
2896	delete_prior_computation (rtx note, rtx_insn *insn)
2897	{
2898	rtx_insn *our_prev;
2899	rtx reg = XEXP (note, 0);
2900
2901	for (our_prev = prev_nonnote_insn (insn);
2902	our_prev && (NONJUMP_INSN_P (our_prev)
2903	|| CALL_P (our_prev));
2904	our_prev = prev_nonnote_insn (our_prev))
2905	{
2906	rtx pat = PATTERN (insn: our_prev);
2907
2908	/* If we reach a CALL which is not calling a const function
2909	or the callee pops the arguments, then give up. */
2910	if (CALL_P (our_prev)
2911	&& (! RTL_CONST_CALL_P (our_prev)
2912	|| GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
2913	break;
2914
2915	/* If we reach a SEQUENCE, it is too complex to try to
2916	do anything with it, so give up. We can be run during
2917	and after reorg, so SEQUENCE rtl can legitimately show
2918	up here. */
2919	if (GET_CODE (pat) == SEQUENCE)
2920	break;
2921
2922	if (GET_CODE (pat) == USE
2923	&& NONJUMP_INSN_P (XEXP (pat, 0)))
2924	/* reorg creates USEs that look like this. We leave them
2925	alone because reorg needs them for its own purposes. */
2926	break;
2927
2928	if (reg_set_p (reg, pat))
2929	{
2930	if (side_effects_p (pat) && !CALL_P (our_prev))
2931	break;
2932
2933	if (GET_CODE (pat) == PARALLEL)
2934	{
2935	/* If we find a SET of something else, we can't
2936	delete the insn. */
2937
2938	int i;
2939
2940	for (i = 0; i < XVECLEN (pat, 0); i++)
2941	{
2942	rtx part = XVECEXP (pat, 0, i);
2943
2944	if (GET_CODE (part) == SET
2945	&& SET_DEST (part) != reg)
2946	break;
2947	}
2948
2949	if (i == XVECLEN (pat, 0))
2950	delete_computation (insn: our_prev);
2951	}
2952	else if (GET_CODE (pat) == SET
2953	&& REG_P (SET_DEST (pat)))
2954	{
2955	int dest_regno = REGNO (SET_DEST (pat));
2956	int dest_endregno = END_REGNO (SET_DEST (pat));
2957	int regno = REGNO (reg);
2958	int endregno = END_REGNO (x: reg);
2959
2960	if (dest_regno >= regno
2961	&& dest_endregno <= endregno)
2962	delete_computation (insn: our_prev);
2963
2964	/* We may have a multi-word hard register and some, but not
2965	all, of the words of the register are needed in subsequent
2966	insns. Write REG_UNUSED notes for those parts that were not
2967	needed. */
2968	else if (dest_regno <= regno
2969	&& dest_endregno >= endregno)
2970	{
2971	int i;
2972
2973	add_reg_note (our_prev, REG_UNUSED, reg);
2974
2975	for (i = dest_regno; i < dest_endregno; i++)
2976	if (! find_regno_note (our_prev, REG_UNUSED, i))
2977	break;
2978
2979	if (i == dest_endregno)
2980	delete_computation (insn: our_prev);
2981	}
2982	}
2983
2984	break;
2985	}
2986
2987	/* If PAT references the register that dies here, it is an
2988	additional use. Hence any prior SET isn't dead. However, this
2989	insn becomes the new place for the REG_DEAD note. */
2990	if (reg_overlap_mentioned_p (reg, pat))
2991	{
2992	XEXP (note, 1) = REG_NOTES (our_prev);
2993	REG_NOTES (our_prev) = note;
2994	break;
2995	}
2996	}
2997	}
2998
2999	/* Delete INSN and recursively delete insns that compute values used only
3000	by INSN. This uses the REG_DEAD notes computed during flow analysis.
3001
3002	Look at all our REG_DEAD notes. If a previous insn does nothing other
3003	than set a register that dies in this insn, we can delete that insn
3004	as well. */
3005
3006	static void
3007	delete_computation (rtx_insn *insn)
3008	{
3009	rtx note, next;
3010
3011	for (note = REG_NOTES (insn); note; note = next)
3012	{
3013	next = XEXP (note, 1);
3014
3015	if (REG_NOTE_KIND (note) != REG_DEAD
3016	/* Verify that the REG_NOTE is legitimate. */
3017	|| !REG_P (XEXP (note, 0)))
3018	continue;
3019
3020	delete_prior_computation (note, insn);
3021	}
3022
3023	delete_related_insns (insn);
3024	}
3025
3026	/* If all INSN does is set the pc, delete it,
3027	and delete the insn that set the condition codes for it
3028	if that's what the previous thing was. */
3029
3030	static void
3031	delete_jump (rtx_insn *insn)
3032	{
3033	rtx set = single_set (insn);
3034
3035	if (set && GET_CODE (SET_DEST (set)) == PC)
3036	delete_computation (insn);
3037	}
3038
3039	static rtx_insn *
3040	label_before_next_insn (rtx_insn *x, rtx scan_limit)
3041	{
3042	rtx_insn *insn = next_active_insn (x);
3043	while (insn)
3044	{
3045	insn = PREV_INSN (insn);
3046	if (insn == scan_limit || insn == NULL_RTX)
3047	return NULL;
3048	if (LABEL_P (insn))
3049	break;
3050	}
3051	return insn;
3052	}
3053
3054	/* Return TRUE if there is a NOTE_INSN_SWITCH_TEXT_SECTIONS note in between
3055	BEG and END. */
3056
3057	static bool
3058	switch_text_sections_between_p (const rtx_insn *beg, const rtx_insn *end)
3059	{
3060	const rtx_insn *p;
3061	for (p = beg; p != end; p = NEXT_INSN (insn: p))
3062	if (NOTE_P (p) && NOTE_KIND (p) == NOTE_INSN_SWITCH_TEXT_SECTIONS)
3063	return true;
3064	return false;
3065	}
3066
3067
3068	/* Once we have tried two ways to fill a delay slot, make a pass over the
3069	code to try to improve the results and to do such things as more jump
3070	threading. */
3071
3072	static void
3073	relax_delay_slots (rtx_insn *first)
3074	{
3075	rtx_insn *insn, *next;
3076	rtx_sequence *pat;
3077	rtx_insn *delay_insn;
3078	rtx target_label;
3079
3080	/* Look at every JUMP_INSN and see if we can improve it. */
3081	for (insn = first; insn; insn = next)
3082	{
3083	rtx_insn *other, *prior_insn;
3084	bool crossing;
3085
3086	next = next_active_insn (insn);
3087
3088	/* If this is a jump insn, see if it now jumps to a jump, jumps to
3089	the next insn, or jumps to a label that is not the last of a
3090	group of consecutive labels. */
3091	if (is_a <rtx_jump_insn *> (p: insn)
3092	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
3093	&& !ANY_RETURN_P (target_label = JUMP_LABEL (insn)))
3094	{
3095	rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (p: insn);
3096	target_label
3097	= skip_consecutive_labels (label_or_return: follow_jumps (label: target_label, jump: jump_insn,
3098	crossing: &crossing));
3099	if (ANY_RETURN_P (target_label))
3100	target_label = find_end_label (kind: target_label);
3101
3102	if (target_label
3103	&& next_active_insn (as_a<rtx_insn *> (p: target_label)) == next
3104	&& ! condjump_in_parallel_p (jump_insn)
3105	&& ! (next && switch_text_sections_between_p (beg: jump_insn, end: next)))
3106	{
3107	rtx_insn *direct_label = as_a<rtx_insn *> (JUMP_LABEL (insn));
3108	rtx_insn *prev = prev_nonnote_insn (direct_label);
3109
3110	/* If the insn jumps over a BARRIER and is the only way to reach
3111	its target, then we need to delete the BARRIER before the jump
3112	because, otherwise, the target may end up being considered as
3113	unreachable and thus also deleted. */
3114	if (BARRIER_P (prev) && LABEL_NUSES (direct_label) == 1)
3115	{
3116	delete_related_insns (prev);
3117
3118	/* We have just removed a BARRIER, which means that the block
3119	number of the next insns has effectively been changed (see
3120	find_basic_block in resource.cc), so clear it. */
3121	clear_hashed_info_until_next_barrier (direct_label);
3122	}
3123
3124	delete_jump (insn: jump_insn);
3125	continue;
3126	}
3127
3128	if (target_label && target_label != JUMP_LABEL (jump_insn))
3129	{
3130	reorg_redirect_jump (jump: jump_insn, nlabel: target_label);
3131	if (crossing)
3132	CROSSING_JUMP_P (jump_insn) = 1;
3133	}
3134
3135	/* See if this jump conditionally branches around an unconditional
3136	jump. If so, invert this jump and point it to the target of the
3137	second jump. Check if it's possible on the target. */
3138	if (next && simplejump_or_return_p (insn: next)
3139	&& any_condjump_p (jump_insn)
3140	&& target_label
3141	&& (next_active_insn (as_a<rtx_insn *> (p: target_label))
3142	== next_active_insn (next))
3143	&& no_labels_between_p (jump_insn, next)
3144	&& targetm.can_follow_jump (jump_insn, next))
3145	{
3146	rtx label = JUMP_LABEL (next);
3147
3148	/* Be careful how we do this to avoid deleting code or
3149	labels that are momentarily dead. See similar optimization
3150	in jump.cc.
3151
3152	We also need to ensure we properly handle the case when
3153	invert_jump fails. */
3154
3155	++LABEL_NUSES (target_label);
3156	if (!ANY_RETURN_P (label))
3157	++LABEL_NUSES (label);
3158
3159	if (invert_jump (jump_insn, label, 1))
3160	{
3161	rtx_insn *from = delete_related_insns (next);
3162
3163	/* We have just removed a BARRIER, which means that the block
3164	number of the next insns has effectively been changed (see
3165	find_basic_block in resource.cc), so clear it. */
3166	if (from)
3167	clear_hashed_info_until_next_barrier (from);
3168
3169	next = jump_insn;
3170	}
3171
3172	if (!ANY_RETURN_P (label))
3173	--LABEL_NUSES (label);
3174
3175	if (--LABEL_NUSES (target_label) == 0)
3176	delete_related_insns (target_label);
3177
3178	continue;
3179	}
3180	}
3181
3182	/* If this is an unconditional jump and the previous insn is a
3183	conditional jump, try reversing the condition of the previous
3184	insn and swapping our targets. The next pass might be able to
3185	fill the slots.
3186
3187	Don't do this if we expect the conditional branch to be true, because
3188	we would then be making the more common case longer. */
3189
3190	if (simplejump_or_return_p (insn)
3191	&& (other = prev_active_insn (insn)) != 0
3192	&& any_condjump_p (other)
3193	&& no_labels_between_p (other, insn)
3194	&& mostly_true_jump (jump_insn: other) < 0)
3195	{
3196	rtx other_target = JUMP_LABEL (other);
3197	target_label = JUMP_LABEL (insn);
3198
3199	if (invert_jump (as_a <rtx_jump_insn *> (p: other), target_label, 0))
3200	reorg_redirect_jump (jump: as_a <rtx_jump_insn *> (p: insn), nlabel: other_target);
3201	}
3202
3203	/* Now look only at cases where we have a filled delay slot. */
3204	if (!NONJUMP_INSN_P (insn) || GET_CODE (PATTERN (insn)) != SEQUENCE)
3205	continue;
3206
3207	pat = as_a <rtx_sequence *> (p: PATTERN (insn));
3208	delay_insn = pat->insn (index: 0);
3209
3210	/* See if the first insn in the delay slot is redundant with some
3211	previous insn. Remove it from the delay slot if so; then set up
3212	to reprocess this insn. */
3213	if ((prior_insn = redundant_insn (insn: pat->insn (index: 1), target: delay_insn, delay_list: vNULL)))
3214	{
3215	fix_reg_dead_note (start_insn: prior_insn, stop_insn: insn);
3216	update_block (insn: pat->insn (index: 1), where: insn);
3217	delete_from_delay_slot (insn: pat->insn (index: 1));
3218	next = prev_active_insn (next);
3219	continue;
3220	}
3221
3222	/* See if we have a RETURN insn with a filled delay slot followed
3223	by a RETURN insn with an unfilled a delay slot. If so, we can delete
3224	the first RETURN (but not its delay insn). This gives the same
3225	effect in fewer instructions.
3226
3227	Only do so if optimizing for size since this results in slower, but
3228	smaller code. */
3229	if (optimize_function_for_size_p (cfun)
3230	&& ANY_RETURN_P (PATTERN (delay_insn))
3231	&& next
3232	&& JUMP_P (next)
3233	&& PATTERN (insn: next) == PATTERN (insn: delay_insn))
3234	{
3235	rtx_insn *after;
3236	int i;
3237
3238	/* Delete the RETURN and just execute the delay list insns.
3239
3240	We do this by deleting the INSN containing the SEQUENCE, then
3241	re-emitting the insns separately, and then deleting the RETURN.
3242	This allows the count of the jump target to be properly
3243	decremented.
3244
3245	Note that we need to change the INSN_UID of the re-emitted insns
3246	since it is used to hash the insns for mark_target_live_regs and
3247	the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3248
3249	Clear the from target bit, since these insns are no longer
3250	in delay slots. */
3251	for (i = 0; i < XVECLEN (pat, 0); i++)
3252	INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3253
3254	rtx_insn *prev = PREV_INSN (insn);
3255	delete_related_insns (insn);
3256	gcc_assert (GET_CODE (pat) == SEQUENCE);
3257	add_insn_after (delay_insn, prev, NULL);
3258	after = delay_insn;
3259	for (i = 1; i < pat->len (); i++)
3260	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3261	delete_scheduled_jump (insn: delay_insn);
3262	continue;
3263	}
3264
3265	/* Now look only at the cases where we have a filled JUMP_INSN. */
3266	rtx_jump_insn *delay_jump_insn =
3267	dyn_cast <rtx_jump_insn *> (p: delay_insn);
3268	if (! delay_jump_insn || !(condjump_p (delay_jump_insn)
3269	|| condjump_in_parallel_p (delay_jump_insn)))
3270	continue;
3271
3272	target_label = JUMP_LABEL (delay_jump_insn);
3273	if (target_label && ANY_RETURN_P (target_label))
3274	continue;
3275
3276	/* If this jump goes to another unconditional jump, thread it, but
3277	don't convert a jump into a RETURN here. */
3278	rtx trial = skip_consecutive_labels (label_or_return: follow_jumps (label: target_label,
3279	jump: delay_jump_insn,
3280	crossing: &crossing));
3281	if (ANY_RETURN_P (trial))
3282	trial = find_end_label (kind: trial);
3283
3284	if (trial && trial != target_label
3285	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn, newlabel: trial, seq: insn))
3286	{
3287	reorg_redirect_jump (jump: delay_jump_insn, nlabel: trial);
3288	target_label = trial;
3289	if (crossing)
3290	CROSSING_JUMP_P (delay_jump_insn) = 1;
3291	}
3292
3293	/* If the first insn at TARGET_LABEL is redundant with a previous
3294	insn, redirect the jump to the following insn and process again.
3295	We use next_real_nondebug_insn instead of next_active_insn so we
3296	don't skip USE-markers, or we'll end up with incorrect
3297	liveness info. */
3298	trial = next_real_nondebug_insn (target_label);
3299	if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3300	&& redundant_insn (insn: trial, target: insn, delay_list: vNULL)
3301	&& ! can_throw_internal (trial))
3302	{
3303	/* Figure out where to emit the special USE insn so we don't
3304	later incorrectly compute register live/death info. */
3305	rtx_insn *tmp = next_active_insn (as_a<rtx_insn *> (p: trial));
3306	if (tmp == 0)
3307	tmp = find_end_label (kind: simple_return_rtx);
3308
3309	if (tmp)
3310	{
3311	/* Insert the special USE insn and update dataflow info.
3312	We know "trial" is an insn here as it is the output of
3313	next_real_nondebug_insn () above. */
3314	update_block (insn: as_a <rtx_insn *> (p: trial), where: tmp);
3315
3316	/* Now emit a label before the special USE insn, and
3317	redirect our jump to the new label. */
3318	target_label = get_label_before (insn: PREV_INSN (insn: tmp), sibling: target_label);
3319	reorg_redirect_jump (jump: delay_jump_insn, nlabel: target_label);
3320	next = insn;
3321	continue;
3322	}
3323	}
3324
3325	/* Similarly, if it is an unconditional jump with one insn in its
3326	delay list and that insn is redundant, thread the jump. */
3327	rtx_sequence *trial_seq =
3328	trial ? dyn_cast <rtx_sequence *> (p: PATTERN (insn: trial)) : NULL;
3329	if (trial_seq
3330	&& trial_seq->len () == 2
3331	&& JUMP_P (trial_seq->insn (0))
3332	&& simplejump_or_return_p (insn: trial_seq->insn (index: 0))
3333	&& redundant_insn (insn: trial_seq->insn (index: 1), target: insn, delay_list: vNULL))
3334	{
3335	rtx temp_label = JUMP_LABEL (trial_seq->insn (0));
3336	if (ANY_RETURN_P (temp_label))
3337	temp_label = find_end_label (kind: temp_label);
3338
3339	if (temp_label
3340	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn,
3341	newlabel: temp_label, seq: insn))
3342	{
3343	update_block (insn: trial_seq->insn (index: 1), where: insn);
3344	reorg_redirect_jump (jump: delay_jump_insn, nlabel: temp_label);
3345	next = insn;
3346	continue;
3347	}
3348	}
3349
3350	/* See if we have a simple (conditional) jump that is useless. */
3351	if (!CROSSING_JUMP_P (delay_jump_insn)
3352	&& !INSN_ANNULLED_BRANCH_P (delay_jump_insn)
3353	&& !condjump_in_parallel_p (delay_jump_insn)
3354	&& prev_active_insn (as_a<rtx_insn *> (p: target_label)) == insn
3355	&& !BARRIER_P (prev_nonnote_insn (as_a<rtx_insn *> (target_label))))
3356	{
3357	rtx_insn *after;
3358	int i;
3359
3360	/* All this insn does is execute its delay list and jump to the
3361	following insn. So delete the jump and just execute the delay
3362	list insns.
3363
3364	We do this by deleting the INSN containing the SEQUENCE, then
3365	re-emitting the insns separately, and then deleting the jump.
3366	This allows the count of the jump target to be properly
3367	decremented.
3368
3369	Note that we need to change the INSN_UID of the re-emitted insns
3370	since it is used to hash the insns for mark_target_live_regs and
3371	the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3372
3373	Clear the from target bit, since these insns are no longer
3374	in delay slots. */
3375	for (i = 0; i < XVECLEN (pat, 0); i++)
3376	INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3377
3378	rtx_insn *prev = PREV_INSN (insn);
3379	delete_related_insns (insn);
3380	gcc_assert (GET_CODE (pat) == SEQUENCE);
3381	add_insn_after (delay_jump_insn, prev, NULL);
3382	after = delay_jump_insn;
3383	for (i = 1; i < pat->len (); i++)
3384	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3385	delete_scheduled_jump (insn: delay_jump_insn);
3386	continue;
3387	}
3388
3389	/* See if this is an unconditional jump around a single insn which is
3390	identical to the one in its delay slot. In this case, we can just
3391	delete the branch and the insn in its delay slot. */
3392	if (next && NONJUMP_INSN_P (next)
3393	&& label_before_next_insn (x: next, scan_limit: insn) == target_label
3394	&& simplejump_p (insn)
3395	&& XVECLEN (pat, 0) == 2
3396	&& rtx_equal_p (PATTERN (insn: next), PATTERN (insn: pat->insn (index: 1))))
3397	{
3398	delete_related_insns (insn);
3399	continue;
3400	}
3401
3402	/* See if this jump (with its delay slots) conditionally branches
3403	around an unconditional jump (without delay slots). If so, invert
3404	this jump and point it to the target of the second jump. We cannot
3405	do this for annulled jumps, though. Again, don't convert a jump to
3406	a RETURN here. */
3407	if (! INSN_ANNULLED_BRANCH_P (delay_jump_insn)
3408	&& any_condjump_p (delay_jump_insn)
3409	&& next && simplejump_or_return_p (insn: next)
3410	&& (next_active_insn (as_a<rtx_insn *> (p: target_label))
3411	== next_active_insn (next))
3412	&& no_labels_between_p (insn, next))
3413	{
3414	rtx label = JUMP_LABEL (next);
3415	rtx old_label = JUMP_LABEL (delay_jump_insn);
3416
3417	if (ANY_RETURN_P (label))
3418	label = find_end_label (kind: label);
3419
3420	/* find_end_label can generate a new label. Check this first. */
3421	if (label
3422	&& no_labels_between_p (insn, next)
3423	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn,
3424	newlabel: label, seq: insn))
3425	{
3426	/* Be careful how we do this to avoid deleting code or labels
3427	that are momentarily dead. See similar optimization in
3428	jump.cc */
3429	if (old_label)
3430	++LABEL_NUSES (old_label);
3431
3432	if (invert_jump (delay_jump_insn, label, 1))
3433	{
3434	/* Must update the INSN_FROM_TARGET_P bits now that
3435	the branch is reversed, so that mark_target_live_regs
3436	will handle the delay slot insn correctly. */
3437	for (int i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
3438	{
3439	rtx slot = XVECEXP (PATTERN (insn), 0, i);
3440	INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
3441	}
3442
3443	/* We have just removed a BARRIER, which means that the block
3444	number of the next insns has effectively been changed (see
3445	find_basic_block in resource.cc), so clear it. */
3446	rtx_insn *from = delete_related_insns (next);
3447	if (from)
3448	clear_hashed_info_until_next_barrier (from);
3449
3450	next = insn;
3451	}
3452
3453	if (old_label && --LABEL_NUSES (old_label) == 0)
3454	delete_related_insns (old_label);
3455	continue;
3456	}
3457	}
3458
3459	/* If we own the thread opposite the way this insn branches, see if we
3460	can merge its delay slots with following insns. */
3461	if (INSN_FROM_TARGET_P (pat->insn (1))
3462	&& own_thread_p (thread: NEXT_INSN (insn), label: 0, allow_fallthrough: true))
3463	try_merge_delay_insns (insn, thread: next);
3464	else if (! INSN_FROM_TARGET_P (pat->insn (1))
3465	&& own_thread_p (thread: target_label, label: target_label, allow_fallthrough: false))
3466	try_merge_delay_insns (insn,
3467	thread: next_active_insn (as_a<rtx_insn *> (p: target_label)));
3468
3469	/* If we get here, we haven't deleted INSN. But we may have deleted
3470	NEXT, so recompute it. */
3471	next = next_active_insn (insn);
3472	}
3473	}
3474
3475
3476	/* Look for filled jumps to the end of function label. We can try to convert
3477	them into RETURN insns if the insns in the delay slot are valid for the
3478	RETURN as well. */
3479
3480	static void
3481	make_return_insns (rtx_insn *first)
3482	{
3483	rtx_insn *insn;
3484	rtx_jump_insn *jump_insn;
3485	rtx real_return_label = function_return_label;
3486	rtx real_simple_return_label = function_simple_return_label;
3487	int slots, i;
3488
3489	/* See if there is a RETURN insn in the function other than the one we
3490	made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3491	into a RETURN to jump to it. */
3492	for (insn = first; insn; insn = NEXT_INSN (insn))
3493	if (JUMP_P (insn) && ANY_RETURN_P (PATTERN (insn)))
3494	{
3495	rtx t = get_label_before (insn, NULL_RTX);
3496	if (PATTERN (insn) == ret_rtx)
3497	real_return_label = t;
3498	else
3499	real_simple_return_label = t;
3500	break;
3501	}
3502
3503	/* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3504	was equal to END_OF_FUNCTION_LABEL. */
3505	if (real_return_label)
3506	LABEL_NUSES (real_return_label)++;
3507	if (real_simple_return_label)
3508	LABEL_NUSES (real_simple_return_label)++;
3509
3510	/* Clear the list of insns to fill so we can use it. */
3511	obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3512
3513	for (insn = first; insn; insn = NEXT_INSN (insn))
3514	{
3515	int flags;
3516	rtx kind, real_label;
3517
3518	/* Only look at filled JUMP_INSNs that go to the end of function
3519	label. */
3520	if (!NONJUMP_INSN_P (insn))
3521	continue;
3522
3523	if (GET_CODE (PATTERN (insn)) != SEQUENCE)
3524	continue;
3525
3526	rtx_sequence *pat = as_a <rtx_sequence *> (p: PATTERN (insn));
3527
3528	if (!jump_to_label_p (pat->insn (index: 0)))
3529	continue;
3530
3531	if (JUMP_LABEL (pat->insn (0)) == function_return_label)
3532	{
3533	kind = ret_rtx;
3534	real_label = real_return_label;
3535	}
3536	else if (JUMP_LABEL (pat->insn (0)) == function_simple_return_label)
3537	{
3538	kind = simple_return_rtx;
3539	real_label = real_simple_return_label;
3540	}
3541	else
3542	continue;
3543
3544	jump_insn = as_a <rtx_jump_insn *> (p: pat->insn (index: 0));
3545
3546	/* If we can't make the jump into a RETURN, try to redirect it to the best
3547	RETURN and go on to the next insn. */
3548	if (!reorg_redirect_jump (jump: jump_insn, nlabel: kind))
3549	{
3550	/* Make sure redirecting the jump will not invalidate the delay
3551	slot insns. */
3552	if (redirect_with_delay_slots_safe_p (jump: jump_insn, newlabel: real_label, seq: insn))
3553	reorg_redirect_jump (jump: jump_insn, nlabel: real_label);
3554	continue;
3555	}
3556
3557	/* See if this RETURN can accept the insns current in its delay slot.
3558	It can if it has more or an equal number of slots and the contents
3559	of each is valid. */
3560
3561	flags = get_jump_flags (insn: jump_insn, JUMP_LABEL (jump_insn));
3562	slots = num_delay_slots (jump_insn);
3563	if (slots >= XVECLEN (pat, 0) - 1)
3564	{
3565	for (i = 1; i < XVECLEN (pat, 0); i++)
3566	if (! (
3567	#if ANNUL_IFFALSE_SLOTS
3568	(INSN_ANNULLED_BRANCH_P (jump_insn)
3569	&& INSN_FROM_TARGET_P (pat->insn (i)))
3570	? eligible_for_annul_false (jump_insn, i - 1,
3571	pat->insn (i), flags) :
3572	#endif
3573	#if ANNUL_IFTRUE_SLOTS
3574	(INSN_ANNULLED_BRANCH_P (jump_insn)
3575	&& ! INSN_FROM_TARGET_P (pat->insn (i)))
3576	? eligible_for_annul_true (jump_insn, i - 1,
3577	pat->insn (i), flags) :
3578	#endif
3579	eligible_for_delay (jump_insn, i - 1,
3580	pat->insn (index: i), flags)))
3581	break;
3582	}
3583	else
3584	i = 0;
3585
3586	if (i == XVECLEN (pat, 0))
3587	continue;
3588
3589	/* We have to do something with this insn. If it is an unconditional
3590	RETURN, delete the SEQUENCE and output the individual insns,
3591	followed by the RETURN. Then set things up so we try to find
3592	insns for its delay slots, if it needs some. */
3593	if (ANY_RETURN_P (PATTERN (jump_insn)))
3594	{
3595	rtx_insn *after = PREV_INSN (insn);
3596
3597	delete_related_insns (insn);
3598	insn = jump_insn;
3599	for (i = 1; i < pat->len (); i++)
3600	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3601	add_insn_after (insn, after, NULL);
3602	emit_barrier_after (insn);
3603
3604	if (slots)
3605	obstack_ptr_grow (&unfilled_slots_obstack, insn);
3606	}
3607	else
3608	/* It is probably more efficient to keep this with its current
3609	delay slot as a branch to a RETURN. */
3610	reorg_redirect_jump (jump: jump_insn, nlabel: real_label);
3611	}
3612
3613	/* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3614	new delay slots we have created. */
3615	if (real_return_label != NULL_RTX && --LABEL_NUSES (real_return_label) == 0)
3616	delete_related_insns (real_return_label);
3617	if (real_simple_return_label != NULL_RTX
3618	&& --LABEL_NUSES (real_simple_return_label) == 0)
3619	delete_related_insns (real_simple_return_label);
3620
3621	fill_simple_delay_slots (non_jumps_p: true);
3622	fill_simple_delay_slots (non_jumps_p: false);
3623	}
3624
3625	/* Try to find insns to place in delay slots. */
3626
3627	static void
3628	dbr_schedule (rtx_insn *first)
3629	{
3630	rtx_insn *insn, *next, *epilogue_insn = 0;
3631	bool need_return_insns;
3632	int i;
3633
3634	/* If the current function has no insns other than the prologue and
3635	epilogue, then do not try to fill any delay slots. */
3636	if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3637	return;
3638
3639	/* Find the highest INSN_UID and allocate and initialize our map from
3640	INSN_UID's to position in code. */
3641	for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3642	{
3643	if (INSN_UID (insn) > max_uid)
3644	max_uid = INSN_UID (insn);
3645	if (NOTE_P (insn)
3646	&& NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
3647	epilogue_insn = insn;
3648	}
3649
3650	uid_to_ruid = XNEWVEC (int, max_uid + 1);
3651	for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3652	uid_to_ruid[INSN_UID (insn)] = i;
3653
3654	/* Initialize the list of insns that need filling. */
3655	if (unfilled_firstobj == 0)
3656	{
3657	gcc_obstack_init (&unfilled_slots_obstack);
3658	unfilled_firstobj = XOBNEWVAR (&unfilled_slots_obstack, rtx, 0);
3659	}
3660
3661	for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3662	{
3663	rtx target;
3664
3665	/* Skip vector tables. We can't get attributes for them. */
3666	if (JUMP_TABLE_DATA_P (insn))
3667	continue;
3668
3669	if (JUMP_P (insn))
3670	INSN_ANNULLED_BRANCH_P (insn) = 0;
3671	INSN_FROM_TARGET_P (insn) = 0;
3672
3673	if (num_delay_slots (insn) > 0)
3674	obstack_ptr_grow (&unfilled_slots_obstack, insn);
3675
3676	/* Ensure all jumps go to the last of a set of consecutive labels. */
3677	if (JUMP_P (insn)
3678	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
3679	&& !ANY_RETURN_P (JUMP_LABEL (insn))
3680	&& ((target = skip_consecutive_labels (JUMP_LABEL (insn)))
3681	!= JUMP_LABEL (insn)))
3682	redirect_jump (as_a <rtx_jump_insn *> (p: insn), target, 1);
3683	}
3684
3685	init_resource_info (epilogue_insn);
3686
3687	/* Show we haven't computed an end-of-function label yet. */
3688	function_return_label = function_simple_return_label = NULL;
3689
3690	/* Initialize the statistics for this function. */
3691	memset (s: num_insns_needing_delays, c: 0, n: sizeof num_insns_needing_delays);
3692	memset (s: num_filled_delays, c: 0, n: sizeof num_filled_delays);
3693
3694	/* Now do the delay slot filling. Try everything twice in case earlier
3695	changes make more slots fillable. */
3696
3697	for (reorg_pass_number = 0;
3698	reorg_pass_number < MAX_REORG_PASSES;
3699	reorg_pass_number++)
3700	{
3701	fill_simple_delay_slots (non_jumps_p: true);
3702	fill_simple_delay_slots (non_jumps_p: false);
3703	if (!targetm.no_speculation_in_delay_slots_p ())
3704	fill_eager_delay_slots ();
3705	relax_delay_slots (first);
3706	}
3707
3708	/* If we made an end of function label, indicate that it is now
3709	safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3710	If it is now unused, delete it. */
3711	if (function_return_label && --LABEL_NUSES (function_return_label) == 0)
3712	delete_related_insns (function_return_label);
3713	if (function_simple_return_label
3714	&& --LABEL_NUSES (function_simple_return_label) == 0)
3715	delete_related_insns (function_simple_return_label);
3716
3717	need_return_insns = false;
3718	need_return_insns |= targetm.have_return () && function_return_label != 0;
3719	need_return_insns |= (targetm.have_simple_return ()
3720	&& function_simple_return_label != 0);
3721	if (need_return_insns)
3722	make_return_insns (first);
3723
3724	/* Delete any USE insns made by update_block; subsequent passes don't need
3725	them or know how to deal with them. */
3726	for (insn = first; insn; insn = next)
3727	{
3728	next = NEXT_INSN (insn);
3729
3730	if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE
3731	&& INSN_P (XEXP (PATTERN (insn), 0)))
3732	next = delete_related_insns (insn);
3733	}
3734
3735	obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3736
3737	/* It is not clear why the line below is needed, but it does seem to be. */
3738	unfilled_firstobj = XOBNEWVAR (&unfilled_slots_obstack, rtx, 0);
3739
3740	if (dump_file)
3741	{
3742	int i, j, need_comma;
3743	int total_delay_slots[MAX_DELAY_HISTOGRAM + 1];
3744	int total_annul_slots[MAX_DELAY_HISTOGRAM + 1];
3745
3746	for (reorg_pass_number = 0;
3747	reorg_pass_number < MAX_REORG_PASSES;
3748	reorg_pass_number++)
3749	{
3750	fprintf (stream: dump_file, format: ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3751	for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3752	{
3753	need_comma = 0;
3754	fprintf (stream: dump_file, format: ";; Reorg function #%d\n", i);
3755
3756	fprintf (stream: dump_file, format: ";; %d insns needing delay slots\n;; ",
3757	num_insns_needing_delays[i][reorg_pass_number]);
3758
3759	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3760	if (num_filled_delays[i][j][reorg_pass_number])
3761	{
3762	if (need_comma)
3763	fprintf (stream: dump_file, format: ", ");
3764	need_comma = 1;
3765	fprintf (stream: dump_file, format: "%d got %d delays",
3766	num_filled_delays[i][j][reorg_pass_number], j);
3767	}
3768	fprintf (stream: dump_file, format: "\n");
3769	}
3770	}
3771	memset (s: total_delay_slots, c: 0, n: sizeof total_delay_slots);
3772	memset (s: total_annul_slots, c: 0, n: sizeof total_annul_slots);
3773	for (insn = first; insn; insn = NEXT_INSN (insn))
3774	{
3775	if (! insn->deleted ()
3776	&& NONJUMP_INSN_P (insn)
3777	&& GET_CODE (PATTERN (insn)) != USE
3778	&& GET_CODE (PATTERN (insn)) != CLOBBER)
3779	{
3780	if (GET_CODE (PATTERN (insn)) == SEQUENCE)
3781	{
3782	rtx control;
3783	j = XVECLEN (PATTERN (insn), 0) - 1;
3784	if (j > MAX_DELAY_HISTOGRAM)
3785	j = MAX_DELAY_HISTOGRAM;
3786	control = XVECEXP (PATTERN (insn), 0, 0);
3787	if (JUMP_P (control) && INSN_ANNULLED_BRANCH_P (control))
3788	total_annul_slots[j]++;
3789	else
3790	total_delay_slots[j]++;
3791	}
3792	else if (num_delay_slots (insn) > 0)
3793	total_delay_slots[0]++;
3794	}
3795	}
3796	fprintf (stream: dump_file, format: ";; Reorg totals: ");
3797	need_comma = 0;
3798	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3799	{
3800	if (total_delay_slots[j])
3801	{
3802	if (need_comma)
3803	fprintf (stream: dump_file, format: ", ");
3804	need_comma = 1;
3805	fprintf (stream: dump_file, format: "%d got %d delays", total_delay_slots[j], j);
3806	}
3807	}
3808	fprintf (stream: dump_file, format: "\n");
3809
3810	if (ANNUL_IFTRUE_SLOTS || ANNUL_IFFALSE_SLOTS)
3811	{
3812	fprintf (stream: dump_file, format: ";; Reorg annuls: ");
3813	need_comma = 0;
3814	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3815	{
3816	if (total_annul_slots[j])
3817	{
3818	if (need_comma)
3819	fprintf (stream: dump_file, format: ", ");
3820	need_comma = 1;
3821	fprintf (stream: dump_file, format: "%d got %d delays", total_annul_slots[j], j);
3822	}
3823	}
3824	fprintf (stream: dump_file, format: "\n");
3825	}
3826
3827	fprintf (stream: dump_file, format: "\n");
3828	}
3829
3830	if (!sibling_labels.is_empty ())
3831	{
3832	update_alignments (sibling_labels);
3833	sibling_labels.release ();
3834	}
3835
3836	free_resource_info ();
3837	free (ptr: uid_to_ruid);
3838	crtl->dbr_scheduled_p = true;
3839	}
3840
3841	/* Run delay slot optimization. */
3842	static void
3843	rest_of_handle_delay_slots (void)
3844	{
3845	if (DELAY_SLOTS)
3846	dbr_schedule (first: get_insns ());
3847	}
3848
3849	namespace {
3850
3851	const pass_data pass_data_delay_slots =
3852	{
3853	.type: RTL_PASS, /* type */
3854	.name: "dbr", /* name */
3855	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3856	.tv_id: TV_DBR_SCHED, /* tv_id */
3857	.properties_required: 0, /* properties_required */
3858	.properties_provided: 0, /* properties_provided */
3859	.properties_destroyed: 0, /* properties_destroyed */
3860	.todo_flags_start: 0, /* todo_flags_start */
3861	.todo_flags_finish: 0, /* todo_flags_finish */
3862	};
3863
3864	class pass_delay_slots : public rtl_opt_pass
3865	{
3866	public:
3867	pass_delay_slots (gcc::context *ctxt)
3868	: rtl_opt_pass (pass_data_delay_slots, ctxt)
3869	{}
3870
3871	/* opt_pass methods: */
3872	bool gate (function *) final override;
3873	unsigned int execute (function *) final override
3874	{
3875	rest_of_handle_delay_slots ();
3876	return 0;
3877	}
3878
3879	}; // class pass_delay_slots
3880
3881	bool
3882	pass_delay_slots::gate (function *)
3883	{
3884	/* At -O0 dataflow info isn't updated after RA. */
3885	if (DELAY_SLOTS)
3886	return optimize > 0 && flag_delayed_branch && !crtl->dbr_scheduled_p;
3887
3888	return false;
3889	}
3890
3891	} // anon namespace
3892
3893	rtl_opt_pass *
3894	make_pass_delay_slots (gcc::context *ctxt)
3895	{
3896	return new pass_delay_slots (ctxt);
3897	}
3898
3899	/* Machine dependent reorg pass. */
3900
3901	namespace {
3902
3903	const pass_data pass_data_machine_reorg =
3904	{
3905	.type: RTL_PASS, /* type */
3906	.name: "mach", /* name */
3907	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3908	.tv_id: TV_MACH_DEP, /* tv_id */
3909	.properties_required: 0, /* properties_required */
3910	.properties_provided: 0, /* properties_provided */
3911	.properties_destroyed: 0, /* properties_destroyed */
3912	.todo_flags_start: 0, /* todo_flags_start */
3913	.todo_flags_finish: 0, /* todo_flags_finish */
3914	};
3915
3916	class pass_machine_reorg : public rtl_opt_pass
3917	{
3918	public:
3919	pass_machine_reorg (gcc::context *ctxt)
3920	: rtl_opt_pass (pass_data_machine_reorg, ctxt)
3921	{}
3922
3923	/* opt_pass methods: */
3924	bool gate (function *) final override
3925	{
3926	return targetm.machine_dependent_reorg != 0;
3927	}
3928
3929	unsigned int execute (function *) final override
3930	{
3931	targetm.machine_dependent_reorg ();
3932	return 0;
3933	}
3934
3935	}; // class pass_machine_reorg
3936
3937	} // anon namespace
3938
3939	rtl_opt_pass *
3940	make_pass_machine_reorg (gcc::context *ctxt)
3941	{
3942	return new pass_machine_reorg (ctxt);
3943	}
3944