1	/* Perform instruction reorganizations for delay slot filling.
2	Copyright (C) 1992-2023 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 && !ANY_RETURN_P (new_thread)
2645	&& NONJUMP_INSN_P (new_thread)
2646	&& !RTX_FRAME_RELATED_P (new_thread)
2647	&& GET_CODE (PATTERN (new_thread)) != ASM_INPUT
2648	&& asm_noperands (PATTERN (insn: new_thread)) < 0)
2649	{
2650	rtx dest;
2651	rtx src;
2652
2653	/* We know "new_thread" is an insn due to NONJUMP_INSN_P (new_thread)
2654	above. */
2655	trial = as_a <rtx_insn *> (p: new_thread);
2656	rtx pat = PATTERN (insn: trial);
2657
2658	if (!NONJUMP_INSN_P (trial)
2659	|| GET_CODE (pat) != SET
2660	|| ! eligible_for_delay (insn, 0, trial, flags)
2661	|| can_throw_internal (trial))
2662	return;
2663
2664	dest = SET_DEST (pat), src = SET_SRC (pat);
2665	if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2666	&& rtx_equal_p (XEXP (src, 0), dest)
2667	&& (!FLOAT_MODE_P (GET_MODE (src))
2668	|| flag_unsafe_math_optimizations)
2669	&& ! reg_overlap_mentioned_p (dest, XEXP (src, 1))
2670	&& ! side_effects_p (pat))
2671	{
2672	rtx other = XEXP (src, 1);
2673	rtx new_arith;
2674	rtx_insn *ninsn;
2675
2676	/* If this is a constant adjustment, use the same code with
2677	the negated constant. Otherwise, reverse the sense of the
2678	arithmetic. */
2679	if (CONST_INT_P (other))
2680	new_arith = gen_rtx_fmt_ee (GET_CODE (src), GET_MODE (src), dest,
2681	negate_rtx (GET_MODE (src), other));
2682	else
2683	new_arith = gen_rtx_fmt_ee (GET_CODE (src) == PLUS ? MINUS : PLUS,
2684	GET_MODE (src), dest, other);
2685
2686	ninsn = emit_insn_after (gen_rtx_SET (dest, new_arith), insn);
2687
2688	if (recog_memoized (insn: ninsn) < 0
2689	|| (extract_insn (ninsn),
2690	!constrain_operands (1, get_preferred_alternatives (ninsn))))
2691	{
2692	delete_related_insns (ninsn);
2693	return;
2694	}
2695
2696	if (own_thread)
2697	{
2698	update_block (insn: trial, where: thread);
2699	if (trial == thread)
2700	{
2701	thread = next_active_insn (thread);
2702	if (new_thread == trial)
2703	new_thread = thread;
2704	}
2705	delete_related_insns (trial);
2706	}
2707	else
2708	new_thread = next_active_insn (trial);
2709
2710	ninsn = own_thread ? trial : copy_delay_slot_insn (trial);
2711	if (thread_if_true)
2712	INSN_FROM_TARGET_P (ninsn) = 1;
2713
2714	add_to_delay_list (insn: ninsn, delay_list);
2715	(*pslots_filled)++;
2716	}
2717	}
2718
2719	if (!delay_list->is_empty () && must_annul)
2720	INSN_ANNULLED_BRANCH_P (insn) = 1;
2721
2722	/* If we are to branch into the middle of this thread, find an appropriate
2723	label or make a new one if none, and redirect INSN to it. If we hit the
2724	end of the function, use the end-of-function label. */
2725	if (new_thread != thread)
2726	{
2727	rtx label;
2728	bool crossing = false;
2729
2730	gcc_assert (thread_if_true);
2731
2732	if (new_thread && simplejump_or_return_p (insn: new_thread)
2733	&& redirect_with_delay_list_safe_p (jump: insn,
2734	JUMP_LABEL (new_thread),
2735	delay_list: *delay_list))
2736	new_thread = follow_jumps (JUMP_LABEL (new_thread), jump: insn,
2737	crossing: &crossing);
2738
2739	if (ANY_RETURN_P (new_thread))
2740	label = find_end_label (kind: new_thread);
2741	else if (LABEL_P (new_thread))
2742	label = new_thread;
2743	else
2744	label = get_label_before (insn: as_a <rtx_insn *> (p: new_thread),
2745	JUMP_LABEL (insn));
2746
2747	if (label)
2748	{
2749	reorg_redirect_jump (jump: insn, nlabel: label);
2750	if (crossing)
2751	CROSSING_JUMP_P (insn) = 1;
2752	}
2753	}
2754	}
2755
2756	/* Make another attempt to find insns to place in delay slots.
2757
2758	We previously looked for insns located in front of the delay insn
2759	and, for non-jump delay insns, located behind the delay insn.
2760
2761	Here only try to schedule jump insns and try to move insns from either
2762	the target or the following insns into the delay slot. If annulling is
2763	supported, we will be likely to do this. Otherwise, we can do this only
2764	if safe. */
2765
2766	static void
2767	fill_eager_delay_slots (void)
2768	{
2769	rtx_insn *insn;
2770	int i;
2771	int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2772
2773	for (i = 0; i < num_unfilled_slots; i++)
2774	{
2775	rtx condition;
2776	rtx target_label, insn_at_target;
2777	rtx_insn *fallthrough_insn;
2778	auto_vec<rtx_insn *, 5> delay_list;
2779	rtx_jump_insn *jump_insn;
2780	bool own_target;
2781	bool own_fallthrough;
2782	int prediction, slots_to_fill, slots_filled;
2783
2784	insn = unfilled_slots_base[i];
2785	if (insn == 0
2786	|| insn->deleted ()
2787	|| ! (jump_insn = dyn_cast <rtx_jump_insn *> (p: insn))
2788	|| ! (condjump_p (jump_insn) || condjump_in_parallel_p (jump_insn)))
2789	continue;
2790
2791	slots_to_fill = num_delay_slots (jump_insn);
2792	/* Some machine description have defined instructions to have
2793	delay slots only in certain circumstances which may depend on
2794	nearby insns (which change due to reorg's actions).
2795
2796	For example, the PA port normally has delay slots for unconditional
2797	jumps.
2798
2799	However, the PA port claims such jumps do not have a delay slot
2800	if they are immediate successors of certain CALL_INSNs. This
2801	allows the port to favor filling the delay slot of the call with
2802	the unconditional jump. */
2803	if (slots_to_fill == 0)
2804	continue;
2805
2806	slots_filled = 0;
2807	target_label = JUMP_LABEL (jump_insn);
2808	condition = get_branch_condition (insn: jump_insn, target: target_label);
2809
2810	if (condition == 0)
2811	continue;
2812
2813	/* Get the next active fallthrough and target insns and see if we own
2814	them. Then see whether the branch is likely true. We don't need
2815	to do a lot of this for unconditional branches. */
2816
2817	insn_at_target = first_active_target_insn (insn: target_label);
2818	own_target = own_thread_p (thread: target_label, label: target_label, allow_fallthrough: false);
2819
2820	if (condition == const_true_rtx)
2821	{
2822	own_fallthrough = false;
2823	fallthrough_insn = 0;
2824	prediction = 2;
2825	}
2826	else
2827	{
2828	fallthrough_insn = next_active_insn (jump_insn);
2829	own_fallthrough = own_thread_p (thread: NEXT_INSN (insn: jump_insn),
2830	NULL_RTX, allow_fallthrough: true);
2831	prediction = mostly_true_jump (jump_insn);
2832	}
2833
2834	/* If this insn is expected to branch, first try to get insns from our
2835	target, then our fallthrough insns. If it is not expected to branch,
2836	try the other order. */
2837
2838	if (prediction > 0)
2839	{
2840	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: insn_at_target,
2841	opposite_thread: fallthrough_insn, likely: prediction == 2, thread_if_true: true,
2842	own_thread: own_target, slots_to_fill,
2843	pslots_filled: &slots_filled, delay_list: &delay_list);
2844
2845	if (delay_list.is_empty () && own_fallthrough)
2846	{
2847	/* Even though we didn't find anything for delay slots,
2848	we might have found a redundant insn which we deleted
2849	from the thread that was filled. So we have to recompute
2850	the next insn at the target. */
2851	target_label = JUMP_LABEL (jump_insn);
2852	insn_at_target = first_active_target_insn (insn: target_label);
2853
2854	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: fallthrough_insn,
2855	opposite_thread: insn_at_target, likely: false, thread_if_true: false,
2856	own_thread: own_fallthrough, slots_to_fill,
2857	pslots_filled: &slots_filled, delay_list: &delay_list);
2858	}
2859	}
2860	else
2861	{
2862	if (own_fallthrough)
2863	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: fallthrough_insn,
2864	opposite_thread: insn_at_target, likely: false, thread_if_true: false,
2865	own_thread: own_fallthrough, slots_to_fill,
2866	pslots_filled: &slots_filled, delay_list: &delay_list);
2867
2868	if (delay_list.is_empty ())
2869	fill_slots_from_thread (insn: jump_insn, condition, thread_or_return: insn_at_target,
2870	opposite_thread: next_active_insn (insn), likely: false, thread_if_true: true,
2871	own_thread: own_target, slots_to_fill,
2872	pslots_filled: &slots_filled, delay_list: &delay_list);
2873	}
2874
2875	if (!delay_list.is_empty ())
2876	unfilled_slots_base[i]
2877	= emit_delay_sequence (insn: jump_insn, list: delay_list, length: slots_filled);
2878
2879	if (slots_to_fill == slots_filled)
2880	unfilled_slots_base[i] = 0;
2881
2882	note_delay_statistics (slots_filled, index: 1);
2883	}
2884	}
2885
2886	static void delete_computation (rtx_insn *insn);
2887
2888	/* Recursively delete prior insns that compute the value (used only by INSN
2889	which the caller is deleting) stored in the register mentioned by NOTE
2890	which is a REG_DEAD note associated with INSN. */
2891
2892	static void
2893	delete_prior_computation (rtx note, rtx_insn *insn)
2894	{
2895	rtx_insn *our_prev;
2896	rtx reg = XEXP (note, 0);
2897
2898	for (our_prev = prev_nonnote_insn (insn);
2899	our_prev && (NONJUMP_INSN_P (our_prev)
2900	|| CALL_P (our_prev));
2901	our_prev = prev_nonnote_insn (our_prev))
2902	{
2903	rtx pat = PATTERN (insn: our_prev);
2904
2905	/* If we reach a CALL which is not calling a const function
2906	or the callee pops the arguments, then give up. */
2907	if (CALL_P (our_prev)
2908	&& (! RTL_CONST_CALL_P (our_prev)
2909	|| GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
2910	break;
2911
2912	/* If we reach a SEQUENCE, it is too complex to try to
2913	do anything with it, so give up. We can be run during
2914	and after reorg, so SEQUENCE rtl can legitimately show
2915	up here. */
2916	if (GET_CODE (pat) == SEQUENCE)
2917	break;
2918
2919	if (GET_CODE (pat) == USE
2920	&& NONJUMP_INSN_P (XEXP (pat, 0)))
2921	/* reorg creates USEs that look like this. We leave them
2922	alone because reorg needs them for its own purposes. */
2923	break;
2924
2925	if (reg_set_p (reg, pat))
2926	{
2927	if (side_effects_p (pat) && !CALL_P (our_prev))
2928	break;
2929
2930	if (GET_CODE (pat) == PARALLEL)
2931	{
2932	/* If we find a SET of something else, we can't
2933	delete the insn. */
2934
2935	int i;
2936
2937	for (i = 0; i < XVECLEN (pat, 0); i++)
2938	{
2939	rtx part = XVECEXP (pat, 0, i);
2940
2941	if (GET_CODE (part) == SET
2942	&& SET_DEST (part) != reg)
2943	break;
2944	}
2945
2946	if (i == XVECLEN (pat, 0))
2947	delete_computation (insn: our_prev);
2948	}
2949	else if (GET_CODE (pat) == SET
2950	&& REG_P (SET_DEST (pat)))
2951	{
2952	int dest_regno = REGNO (SET_DEST (pat));
2953	int dest_endregno = END_REGNO (SET_DEST (pat));
2954	int regno = REGNO (reg);
2955	int endregno = END_REGNO (x: reg);
2956
2957	if (dest_regno >= regno
2958	&& dest_endregno <= endregno)
2959	delete_computation (insn: our_prev);
2960
2961	/* We may have a multi-word hard register and some, but not
2962	all, of the words of the register are needed in subsequent
2963	insns. Write REG_UNUSED notes for those parts that were not
2964	needed. */
2965	else if (dest_regno <= regno
2966	&& dest_endregno >= endregno)
2967	{
2968	int i;
2969
2970	add_reg_note (our_prev, REG_UNUSED, reg);
2971
2972	for (i = dest_regno; i < dest_endregno; i++)
2973	if (! find_regno_note (our_prev, REG_UNUSED, i))
2974	break;
2975
2976	if (i == dest_endregno)
2977	delete_computation (insn: our_prev);
2978	}
2979	}
2980
2981	break;
2982	}
2983
2984	/* If PAT references the register that dies here, it is an
2985	additional use. Hence any prior SET isn't dead. However, this
2986	insn becomes the new place for the REG_DEAD note. */
2987	if (reg_overlap_mentioned_p (reg, pat))
2988	{
2989	XEXP (note, 1) = REG_NOTES (our_prev);
2990	REG_NOTES (our_prev) = note;
2991	break;
2992	}
2993	}
2994	}
2995
2996	/* Delete INSN and recursively delete insns that compute values used only
2997	by INSN. This uses the REG_DEAD notes computed during flow analysis.
2998
2999	Look at all our REG_DEAD notes. If a previous insn does nothing other
3000	than set a register that dies in this insn, we can delete that insn
3001	as well. */
3002
3003	static void
3004	delete_computation (rtx_insn *insn)
3005	{
3006	rtx note, next;
3007
3008	for (note = REG_NOTES (insn); note; note = next)
3009	{
3010	next = XEXP (note, 1);
3011
3012	if (REG_NOTE_KIND (note) != REG_DEAD
3013	/* Verify that the REG_NOTE is legitimate. */
3014	|| !REG_P (XEXP (note, 0)))
3015	continue;
3016
3017	delete_prior_computation (note, insn);
3018	}
3019
3020	delete_related_insns (insn);
3021	}
3022
3023	/* If all INSN does is set the pc, delete it,
3024	and delete the insn that set the condition codes for it
3025	if that's what the previous thing was. */
3026
3027	static void
3028	delete_jump (rtx_insn *insn)
3029	{
3030	rtx set = single_set (insn);
3031
3032	if (set && GET_CODE (SET_DEST (set)) == PC)
3033	delete_computation (insn);
3034	}
3035
3036	static rtx_insn *
3037	label_before_next_insn (rtx_insn *x, rtx scan_limit)
3038	{
3039	rtx_insn *insn = next_active_insn (x);
3040	while (insn)
3041	{
3042	insn = PREV_INSN (insn);
3043	if (insn == scan_limit || insn == NULL_RTX)
3044	return NULL;
3045	if (LABEL_P (insn))
3046	break;
3047	}
3048	return insn;
3049	}
3050
3051	/* Return TRUE if there is a NOTE_INSN_SWITCH_TEXT_SECTIONS note in between
3052	BEG and END. */
3053
3054	static bool
3055	switch_text_sections_between_p (const rtx_insn *beg, const rtx_insn *end)
3056	{
3057	const rtx_insn *p;
3058	for (p = beg; p != end; p = NEXT_INSN (insn: p))
3059	if (NOTE_P (p) && NOTE_KIND (p) == NOTE_INSN_SWITCH_TEXT_SECTIONS)
3060	return true;
3061	return false;
3062	}
3063
3064
3065	/* Once we have tried two ways to fill a delay slot, make a pass over the
3066	code to try to improve the results and to do such things as more jump
3067	threading. */
3068
3069	static void
3070	relax_delay_slots (rtx_insn *first)
3071	{
3072	rtx_insn *insn, *next;
3073	rtx_sequence *pat;
3074	rtx_insn *delay_insn;
3075	rtx target_label;
3076
3077	/* Look at every JUMP_INSN and see if we can improve it. */
3078	for (insn = first; insn; insn = next)
3079	{
3080	rtx_insn *other, *prior_insn;
3081	bool crossing;
3082
3083	next = next_active_insn (insn);
3084
3085	/* If this is a jump insn, see if it now jumps to a jump, jumps to
3086	the next insn, or jumps to a label that is not the last of a
3087	group of consecutive labels. */
3088	if (is_a <rtx_jump_insn *> (p: insn)
3089	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
3090	&& !ANY_RETURN_P (target_label = JUMP_LABEL (insn)))
3091	{
3092	rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (p: insn);
3093	target_label
3094	= skip_consecutive_labels (label_or_return: follow_jumps (label: target_label, jump: jump_insn,
3095	crossing: &crossing));
3096	if (ANY_RETURN_P (target_label))
3097	target_label = find_end_label (kind: target_label);
3098
3099	if (target_label
3100	&& next_active_insn (as_a<rtx_insn *> (p: target_label)) == next
3101	&& ! condjump_in_parallel_p (jump_insn)
3102	&& ! (next && switch_text_sections_between_p (beg: jump_insn, end: next)))
3103	{
3104	rtx_insn *direct_label = as_a<rtx_insn *> (JUMP_LABEL (insn));
3105	rtx_insn *prev = prev_nonnote_insn (direct_label);
3106
3107	/* If the insn jumps over a BARRIER and is the only way to reach
3108	its target, then we need to delete the BARRIER before the jump
3109	because, otherwise, the target may end up being considered as
3110	unreachable and thus also deleted. */
3111	if (BARRIER_P (prev) && LABEL_NUSES (direct_label) == 1)
3112	{
3113	delete_related_insns (prev);
3114
3115	/* We have just removed a BARRIER, which means that the block
3116	number of the next insns has effectively been changed (see
3117	find_basic_block in resource.cc), so clear it. */
3118	clear_hashed_info_until_next_barrier (direct_label);
3119	}
3120
3121	delete_jump (insn: jump_insn);
3122	continue;
3123	}
3124
3125	if (target_label && target_label != JUMP_LABEL (jump_insn))
3126	{
3127	reorg_redirect_jump (jump: jump_insn, nlabel: target_label);
3128	if (crossing)
3129	CROSSING_JUMP_P (jump_insn) = 1;
3130	}
3131
3132	/* See if this jump conditionally branches around an unconditional
3133	jump. If so, invert this jump and point it to the target of the
3134	second jump. Check if it's possible on the target. */
3135	if (next && simplejump_or_return_p (insn: next)
3136	&& any_condjump_p (jump_insn)
3137	&& target_label
3138	&& (next_active_insn (as_a<rtx_insn *> (p: target_label))
3139	== next_active_insn (next))
3140	&& no_labels_between_p (jump_insn, next)
3141	&& targetm.can_follow_jump (jump_insn, next))
3142	{
3143	rtx label = JUMP_LABEL (next);
3144
3145	/* Be careful how we do this to avoid deleting code or
3146	labels that are momentarily dead. See similar optimization
3147	in jump.cc.
3148
3149	We also need to ensure we properly handle the case when
3150	invert_jump fails. */
3151
3152	++LABEL_NUSES (target_label);
3153	if (!ANY_RETURN_P (label))
3154	++LABEL_NUSES (label);
3155
3156	if (invert_jump (jump_insn, label, 1))
3157	{
3158	rtx_insn *from = delete_related_insns (next);
3159
3160	/* We have just removed a BARRIER, which means that the block
3161	number of the next insns has effectively been changed (see
3162	find_basic_block in resource.cc), so clear it. */
3163	if (from)
3164	clear_hashed_info_until_next_barrier (from);
3165
3166	next = jump_insn;
3167	}
3168
3169	if (!ANY_RETURN_P (label))
3170	--LABEL_NUSES (label);
3171
3172	if (--LABEL_NUSES (target_label) == 0)
3173	delete_related_insns (target_label);
3174
3175	continue;
3176	}
3177	}
3178
3179	/* If this is an unconditional jump and the previous insn is a
3180	conditional jump, try reversing the condition of the previous
3181	insn and swapping our targets. The next pass might be able to
3182	fill the slots.
3183
3184	Don't do this if we expect the conditional branch to be true, because
3185	we would then be making the more common case longer. */
3186
3187	if (simplejump_or_return_p (insn)
3188	&& (other = prev_active_insn (insn)) != 0
3189	&& any_condjump_p (other)
3190	&& no_labels_between_p (other, insn)
3191	&& mostly_true_jump (jump_insn: other) < 0)
3192	{
3193	rtx other_target = JUMP_LABEL (other);
3194	target_label = JUMP_LABEL (insn);
3195
3196	if (invert_jump (as_a <rtx_jump_insn *> (p: other), target_label, 0))
3197	reorg_redirect_jump (jump: as_a <rtx_jump_insn *> (p: insn), nlabel: other_target);
3198	}
3199
3200	/* Now look only at cases where we have a filled delay slot. */
3201	if (!NONJUMP_INSN_P (insn) || GET_CODE (PATTERN (insn)) != SEQUENCE)
3202	continue;
3203
3204	pat = as_a <rtx_sequence *> (p: PATTERN (insn));
3205	delay_insn = pat->insn (index: 0);
3206
3207	/* See if the first insn in the delay slot is redundant with some
3208	previous insn. Remove it from the delay slot if so; then set up
3209	to reprocess this insn. */
3210	if ((prior_insn = redundant_insn (insn: pat->insn (index: 1), target: delay_insn, delay_list: vNULL)))
3211	{
3212	fix_reg_dead_note (start_insn: prior_insn, stop_insn: insn);
3213	update_block (insn: pat->insn (index: 1), where: insn);
3214	delete_from_delay_slot (insn: pat->insn (index: 1));
3215	next = prev_active_insn (next);
3216	continue;
3217	}
3218
3219	/* See if we have a RETURN insn with a filled delay slot followed
3220	by a RETURN insn with an unfilled a delay slot. If so, we can delete
3221	the first RETURN (but not its delay insn). This gives the same
3222	effect in fewer instructions.
3223
3224	Only do so if optimizing for size since this results in slower, but
3225	smaller code. */
3226	if (optimize_function_for_size_p (cfun)
3227	&& ANY_RETURN_P (PATTERN (delay_insn))
3228	&& next
3229	&& JUMP_P (next)
3230	&& PATTERN (insn: next) == PATTERN (insn: delay_insn))
3231	{
3232	rtx_insn *after;
3233	int i;
3234
3235	/* Delete the RETURN and just execute the delay list insns.
3236
3237	We do this by deleting the INSN containing the SEQUENCE, then
3238	re-emitting the insns separately, and then deleting the RETURN.
3239	This allows the count of the jump target to be properly
3240	decremented.
3241
3242	Note that we need to change the INSN_UID of the re-emitted insns
3243	since it is used to hash the insns for mark_target_live_regs and
3244	the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3245
3246	Clear the from target bit, since these insns are no longer
3247	in delay slots. */
3248	for (i = 0; i < XVECLEN (pat, 0); i++)
3249	INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3250
3251	rtx_insn *prev = PREV_INSN (insn);
3252	delete_related_insns (insn);
3253	gcc_assert (GET_CODE (pat) == SEQUENCE);
3254	add_insn_after (delay_insn, prev, NULL);
3255	after = delay_insn;
3256	for (i = 1; i < pat->len (); i++)
3257	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3258	delete_scheduled_jump (insn: delay_insn);
3259	continue;
3260	}
3261
3262	/* Now look only at the cases where we have a filled JUMP_INSN. */
3263	rtx_jump_insn *delay_jump_insn =
3264	dyn_cast <rtx_jump_insn *> (p: delay_insn);
3265	if (! delay_jump_insn || !(condjump_p (delay_jump_insn)
3266	|| condjump_in_parallel_p (delay_jump_insn)))
3267	continue;
3268
3269	target_label = JUMP_LABEL (delay_jump_insn);
3270	if (target_label && ANY_RETURN_P (target_label))
3271	continue;
3272
3273	/* If this jump goes to another unconditional jump, thread it, but
3274	don't convert a jump into a RETURN here. */
3275	rtx trial = skip_consecutive_labels (label_or_return: follow_jumps (label: target_label,
3276	jump: delay_jump_insn,
3277	crossing: &crossing));
3278	if (ANY_RETURN_P (trial))
3279	trial = find_end_label (kind: trial);
3280
3281	if (trial && trial != target_label
3282	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn, newlabel: trial, seq: insn))
3283	{
3284	reorg_redirect_jump (jump: delay_jump_insn, nlabel: trial);
3285	target_label = trial;
3286	if (crossing)
3287	CROSSING_JUMP_P (delay_jump_insn) = 1;
3288	}
3289
3290	/* If the first insn at TARGET_LABEL is redundant with a previous
3291	insn, redirect the jump to the following insn and process again.
3292	We use next_real_nondebug_insn instead of next_active_insn so we
3293	don't skip USE-markers, or we'll end up with incorrect
3294	liveness info. */
3295	trial = next_real_nondebug_insn (target_label);
3296	if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3297	&& redundant_insn (insn: trial, target: insn, delay_list: vNULL)
3298	&& ! can_throw_internal (trial))
3299	{
3300	/* Figure out where to emit the special USE insn so we don't
3301	later incorrectly compute register live/death info. */
3302	rtx_insn *tmp = next_active_insn (as_a<rtx_insn *> (p: trial));
3303	if (tmp == 0)
3304	tmp = find_end_label (kind: simple_return_rtx);
3305
3306	if (tmp)
3307	{
3308	/* Insert the special USE insn and update dataflow info.
3309	We know "trial" is an insn here as it is the output of
3310	next_real_nondebug_insn () above. */
3311	update_block (insn: as_a <rtx_insn *> (p: trial), where: tmp);
3312
3313	/* Now emit a label before the special USE insn, and
3314	redirect our jump to the new label. */
3315	target_label = get_label_before (insn: PREV_INSN (insn: tmp), sibling: target_label);
3316	reorg_redirect_jump (jump: delay_jump_insn, nlabel: target_label);
3317	next = insn;
3318	continue;
3319	}
3320	}
3321
3322	/* Similarly, if it is an unconditional jump with one insn in its
3323	delay list and that insn is redundant, thread the jump. */
3324	rtx_sequence *trial_seq =
3325	trial ? dyn_cast <rtx_sequence *> (p: PATTERN (insn: trial)) : NULL;
3326	if (trial_seq
3327	&& trial_seq->len () == 2
3328	&& JUMP_P (trial_seq->insn (0))
3329	&& simplejump_or_return_p (insn: trial_seq->insn (index: 0))
3330	&& redundant_insn (insn: trial_seq->insn (index: 1), target: insn, delay_list: vNULL))
3331	{
3332	rtx temp_label = JUMP_LABEL (trial_seq->insn (0));
3333	if (ANY_RETURN_P (temp_label))
3334	temp_label = find_end_label (kind: temp_label);
3335
3336	if (temp_label
3337	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn,
3338	newlabel: temp_label, seq: insn))
3339	{
3340	update_block (insn: trial_seq->insn (index: 1), where: insn);
3341	reorg_redirect_jump (jump: delay_jump_insn, nlabel: temp_label);
3342	next = insn;
3343	continue;
3344	}
3345	}
3346
3347	/* See if we have a simple (conditional) jump that is useless. */
3348	if (!CROSSING_JUMP_P (delay_jump_insn)
3349	&& !INSN_ANNULLED_BRANCH_P (delay_jump_insn)
3350	&& !condjump_in_parallel_p (delay_jump_insn)
3351	&& prev_active_insn (as_a<rtx_insn *> (p: target_label)) == insn
3352	&& !BARRIER_P (prev_nonnote_insn (as_a<rtx_insn *> (target_label))))
3353	{
3354	rtx_insn *after;
3355	int i;
3356
3357	/* All this insn does is execute its delay list and jump to the
3358	following insn. So delete the jump and just execute the delay
3359	list insns.
3360
3361	We do this by deleting the INSN containing the SEQUENCE, then
3362	re-emitting the insns separately, and then deleting the jump.
3363	This allows the count of the jump target to be properly
3364	decremented.
3365
3366	Note that we need to change the INSN_UID of the re-emitted insns
3367	since it is used to hash the insns for mark_target_live_regs and
3368	the re-emitted insns will no longer be wrapped up in a SEQUENCE.
3369
3370	Clear the from target bit, since these insns are no longer
3371	in delay slots. */
3372	for (i = 0; i < XVECLEN (pat, 0); i++)
3373	INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)) = 0;
3374
3375	rtx_insn *prev = PREV_INSN (insn);
3376	delete_related_insns (insn);
3377	gcc_assert (GET_CODE (pat) == SEQUENCE);
3378	add_insn_after (delay_jump_insn, prev, NULL);
3379	after = delay_jump_insn;
3380	for (i = 1; i < pat->len (); i++)
3381	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3382	delete_scheduled_jump (insn: delay_jump_insn);
3383	continue;
3384	}
3385
3386	/* See if this is an unconditional jump around a single insn which is
3387	identical to the one in its delay slot. In this case, we can just
3388	delete the branch and the insn in its delay slot. */
3389	if (next && NONJUMP_INSN_P (next)
3390	&& label_before_next_insn (x: next, scan_limit: insn) == target_label
3391	&& simplejump_p (insn)
3392	&& XVECLEN (pat, 0) == 2
3393	&& rtx_equal_p (PATTERN (insn: next), PATTERN (insn: pat->insn (index: 1))))
3394	{
3395	delete_related_insns (insn);
3396	continue;
3397	}
3398
3399	/* See if this jump (with its delay slots) conditionally branches
3400	around an unconditional jump (without delay slots). If so, invert
3401	this jump and point it to the target of the second jump. We cannot
3402	do this for annulled jumps, though. Again, don't convert a jump to
3403	a RETURN here. */
3404	if (! INSN_ANNULLED_BRANCH_P (delay_jump_insn)
3405	&& any_condjump_p (delay_jump_insn)
3406	&& next && simplejump_or_return_p (insn: next)
3407	&& (next_active_insn (as_a<rtx_insn *> (p: target_label))
3408	== next_active_insn (next))
3409	&& no_labels_between_p (insn, next))
3410	{
3411	rtx label = JUMP_LABEL (next);
3412	rtx old_label = JUMP_LABEL (delay_jump_insn);
3413
3414	if (ANY_RETURN_P (label))
3415	label = find_end_label (kind: label);
3416
3417	/* find_end_label can generate a new label. Check this first. */
3418	if (label
3419	&& no_labels_between_p (insn, next)
3420	&& redirect_with_delay_slots_safe_p (jump: delay_jump_insn,
3421	newlabel: label, seq: insn))
3422	{
3423	/* Be careful how we do this to avoid deleting code or labels
3424	that are momentarily dead. See similar optimization in
3425	jump.cc */
3426	if (old_label)
3427	++LABEL_NUSES (old_label);
3428
3429	if (invert_jump (delay_jump_insn, label, 1))
3430	{
3431	/* Must update the INSN_FROM_TARGET_P bits now that
3432	the branch is reversed, so that mark_target_live_regs
3433	will handle the delay slot insn correctly. */
3434	for (int i = 1; i < XVECLEN (PATTERN (insn), 0); i++)
3435	{
3436	rtx slot = XVECEXP (PATTERN (insn), 0, i);
3437	INSN_FROM_TARGET_P (slot) = ! INSN_FROM_TARGET_P (slot);
3438	}
3439
3440	/* We have just removed a BARRIER, which means that the block
3441	number of the next insns has effectively been changed (see
3442	find_basic_block in resource.cc), so clear it. */
3443	rtx_insn *from = delete_related_insns (next);
3444	if (from)
3445	clear_hashed_info_until_next_barrier (from);
3446
3447	next = insn;
3448	}
3449
3450	if (old_label && --LABEL_NUSES (old_label) == 0)
3451	delete_related_insns (old_label);
3452	continue;
3453	}
3454	}
3455
3456	/* If we own the thread opposite the way this insn branches, see if we
3457	can merge its delay slots with following insns. */
3458	if (INSN_FROM_TARGET_P (pat->insn (1))
3459	&& own_thread_p (thread: NEXT_INSN (insn), label: 0, allow_fallthrough: true))
3460	try_merge_delay_insns (insn, thread: next);
3461	else if (! INSN_FROM_TARGET_P (pat->insn (1))
3462	&& own_thread_p (thread: target_label, label: target_label, allow_fallthrough: false))
3463	try_merge_delay_insns (insn,
3464	thread: next_active_insn (as_a<rtx_insn *> (p: target_label)));
3465
3466	/* If we get here, we haven't deleted INSN. But we may have deleted
3467	NEXT, so recompute it. */
3468	next = next_active_insn (insn);
3469	}
3470	}
3471
3472
3473	/* Look for filled jumps to the end of function label. We can try to convert
3474	them into RETURN insns if the insns in the delay slot are valid for the
3475	RETURN as well. */
3476
3477	static void
3478	make_return_insns (rtx_insn *first)
3479	{
3480	rtx_insn *insn;
3481	rtx_jump_insn *jump_insn;
3482	rtx real_return_label = function_return_label;
3483	rtx real_simple_return_label = function_simple_return_label;
3484	int slots, i;
3485
3486	/* See if there is a RETURN insn in the function other than the one we
3487	made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3488	into a RETURN to jump to it. */
3489	for (insn = first; insn; insn = NEXT_INSN (insn))
3490	if (JUMP_P (insn) && ANY_RETURN_P (PATTERN (insn)))
3491	{
3492	rtx t = get_label_before (insn, NULL_RTX);
3493	if (PATTERN (insn) == ret_rtx)
3494	real_return_label = t;
3495	else
3496	real_simple_return_label = t;
3497	break;
3498	}
3499
3500	/* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3501	was equal to END_OF_FUNCTION_LABEL. */
3502	if (real_return_label)
3503	LABEL_NUSES (real_return_label)++;
3504	if (real_simple_return_label)
3505	LABEL_NUSES (real_simple_return_label)++;
3506
3507	/* Clear the list of insns to fill so we can use it. */
3508	obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3509
3510	for (insn = first; insn; insn = NEXT_INSN (insn))
3511	{
3512	int flags;
3513	rtx kind, real_label;
3514
3515	/* Only look at filled JUMP_INSNs that go to the end of function
3516	label. */
3517	if (!NONJUMP_INSN_P (insn))
3518	continue;
3519
3520	if (GET_CODE (PATTERN (insn)) != SEQUENCE)
3521	continue;
3522
3523	rtx_sequence *pat = as_a <rtx_sequence *> (p: PATTERN (insn));
3524
3525	if (!jump_to_label_p (pat->insn (index: 0)))
3526	continue;
3527
3528	if (JUMP_LABEL (pat->insn (0)) == function_return_label)
3529	{
3530	kind = ret_rtx;
3531	real_label = real_return_label;
3532	}
3533	else if (JUMP_LABEL (pat->insn (0)) == function_simple_return_label)
3534	{
3535	kind = simple_return_rtx;
3536	real_label = real_simple_return_label;
3537	}
3538	else
3539	continue;
3540
3541	jump_insn = as_a <rtx_jump_insn *> (p: pat->insn (index: 0));
3542
3543	/* If we can't make the jump into a RETURN, try to redirect it to the best
3544	RETURN and go on to the next insn. */
3545	if (!reorg_redirect_jump (jump: jump_insn, nlabel: kind))
3546	{
3547	/* Make sure redirecting the jump will not invalidate the delay
3548	slot insns. */
3549	if (redirect_with_delay_slots_safe_p (jump: jump_insn, newlabel: real_label, seq: insn))
3550	reorg_redirect_jump (jump: jump_insn, nlabel: real_label);
3551	continue;
3552	}
3553
3554	/* See if this RETURN can accept the insns current in its delay slot.
3555	It can if it has more or an equal number of slots and the contents
3556	of each is valid. */
3557
3558	flags = get_jump_flags (insn: jump_insn, JUMP_LABEL (jump_insn));
3559	slots = num_delay_slots (jump_insn);
3560	if (slots >= XVECLEN (pat, 0) - 1)
3561	{
3562	for (i = 1; i < XVECLEN (pat, 0); i++)
3563	if (! (
3564	#if ANNUL_IFFALSE_SLOTS
3565	(INSN_ANNULLED_BRANCH_P (jump_insn)
3566	&& INSN_FROM_TARGET_P (pat->insn (i)))
3567	? eligible_for_annul_false (jump_insn, i - 1,
3568	pat->insn (i), flags) :
3569	#endif
3570	#if ANNUL_IFTRUE_SLOTS
3571	(INSN_ANNULLED_BRANCH_P (jump_insn)
3572	&& ! INSN_FROM_TARGET_P (pat->insn (i)))
3573	? eligible_for_annul_true (jump_insn, i - 1,
3574	pat->insn (i), flags) :
3575	#endif
3576	eligible_for_delay (jump_insn, i - 1,
3577	pat->insn (index: i), flags)))
3578	break;
3579	}
3580	else
3581	i = 0;
3582
3583	if (i == XVECLEN (pat, 0))
3584	continue;
3585
3586	/* We have to do something with this insn. If it is an unconditional
3587	RETURN, delete the SEQUENCE and output the individual insns,
3588	followed by the RETURN. Then set things up so we try to find
3589	insns for its delay slots, if it needs some. */
3590	if (ANY_RETURN_P (PATTERN (jump_insn)))
3591	{
3592	rtx_insn *after = PREV_INSN (insn);
3593
3594	delete_related_insns (insn);
3595	insn = jump_insn;
3596	for (i = 1; i < pat->len (); i++)
3597	after = emit_copy_of_insn_after (pat->insn (index: i), after);
3598	add_insn_after (insn, after, NULL);
3599	emit_barrier_after (insn);
3600
3601	if (slots)
3602	obstack_ptr_grow (&unfilled_slots_obstack, insn);
3603	}
3604	else
3605	/* It is probably more efficient to keep this with its current
3606	delay slot as a branch to a RETURN. */
3607	reorg_redirect_jump (jump: jump_insn, nlabel: real_label);
3608	}
3609
3610	/* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3611	new delay slots we have created. */
3612	if (real_return_label != NULL_RTX && --LABEL_NUSES (real_return_label) == 0)
3613	delete_related_insns (real_return_label);
3614	if (real_simple_return_label != NULL_RTX
3615	&& --LABEL_NUSES (real_simple_return_label) == 0)
3616	delete_related_insns (real_simple_return_label);
3617
3618	fill_simple_delay_slots (non_jumps_p: true);
3619	fill_simple_delay_slots (non_jumps_p: false);
3620	}
3621
3622	/* Try to find insns to place in delay slots. */
3623
3624	static void
3625	dbr_schedule (rtx_insn *first)
3626	{
3627	rtx_insn *insn, *next, *epilogue_insn = 0;
3628	bool need_return_insns;
3629	int i;
3630
3631	/* If the current function has no insns other than the prologue and
3632	epilogue, then do not try to fill any delay slots. */
3633	if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
3634	return;
3635
3636	/* Find the highest INSN_UID and allocate and initialize our map from
3637	INSN_UID's to position in code. */
3638	for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3639	{
3640	if (INSN_UID (insn) > max_uid)
3641	max_uid = INSN_UID (insn);
3642	if (NOTE_P (insn)
3643	&& NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
3644	epilogue_insn = insn;
3645	}
3646
3647	uid_to_ruid = XNEWVEC (int, max_uid + 1);
3648	for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3649	uid_to_ruid[INSN_UID (insn)] = i;
3650
3651	/* Initialize the list of insns that need filling. */
3652	if (unfilled_firstobj == 0)
3653	{
3654	gcc_obstack_init (&unfilled_slots_obstack);
3655	unfilled_firstobj = XOBNEWVAR (&unfilled_slots_obstack, rtx, 0);
3656	}
3657
3658	for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3659	{
3660	rtx target;
3661
3662	/* Skip vector tables. We can't get attributes for them. */
3663	if (JUMP_TABLE_DATA_P (insn))
3664	continue;
3665
3666	if (JUMP_P (insn))
3667	INSN_ANNULLED_BRANCH_P (insn) = 0;
3668	INSN_FROM_TARGET_P (insn) = 0;
3669
3670	if (num_delay_slots (insn) > 0)
3671	obstack_ptr_grow (&unfilled_slots_obstack, insn);
3672
3673	/* Ensure all jumps go to the last of a set of consecutive labels. */
3674	if (JUMP_P (insn)
3675	&& (condjump_p (insn) || condjump_in_parallel_p (insn))
3676	&& !ANY_RETURN_P (JUMP_LABEL (insn))
3677	&& ((target = skip_consecutive_labels (JUMP_LABEL (insn)))
3678	!= JUMP_LABEL (insn)))
3679	redirect_jump (as_a <rtx_jump_insn *> (p: insn), target, 1);
3680	}
3681
3682	init_resource_info (epilogue_insn);
3683
3684	/* Show we haven't computed an end-of-function label yet. */
3685	function_return_label = function_simple_return_label = NULL;
3686
3687	/* Initialize the statistics for this function. */
3688	memset (s: num_insns_needing_delays, c: 0, n: sizeof num_insns_needing_delays);
3689	memset (s: num_filled_delays, c: 0, n: sizeof num_filled_delays);
3690
3691	/* Now do the delay slot filling. Try everything twice in case earlier
3692	changes make more slots fillable. */
3693
3694	for (reorg_pass_number = 0;
3695	reorg_pass_number < MAX_REORG_PASSES;
3696	reorg_pass_number++)
3697	{
3698	fill_simple_delay_slots (non_jumps_p: true);
3699	fill_simple_delay_slots (non_jumps_p: false);
3700	if (!targetm.no_speculation_in_delay_slots_p ())
3701	fill_eager_delay_slots ();
3702	relax_delay_slots (first);
3703	}
3704
3705	/* If we made an end of function label, indicate that it is now
3706	safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3707	If it is now unused, delete it. */
3708	if (function_return_label && --LABEL_NUSES (function_return_label) == 0)
3709	delete_related_insns (function_return_label);
3710	if (function_simple_return_label
3711	&& --LABEL_NUSES (function_simple_return_label) == 0)
3712	delete_related_insns (function_simple_return_label);
3713
3714	need_return_insns = false;
3715	need_return_insns |= targetm.have_return () && function_return_label != 0;
3716	need_return_insns |= (targetm.have_simple_return ()
3717	&& function_simple_return_label != 0);
3718	if (need_return_insns)
3719	make_return_insns (first);
3720
3721	/* Delete any USE insns made by update_block; subsequent passes don't need
3722	them or know how to deal with them. */
3723	for (insn = first; insn; insn = next)
3724	{
3725	next = NEXT_INSN (insn);
3726
3727	if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == USE
3728	&& INSN_P (XEXP (PATTERN (insn), 0)))
3729	next = delete_related_insns (insn);
3730	}
3731
3732	obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3733
3734	/* It is not clear why the line below is needed, but it does seem to be. */
3735	unfilled_firstobj = XOBNEWVAR (&unfilled_slots_obstack, rtx, 0);
3736
3737	if (dump_file)
3738	{
3739	int i, j, need_comma;
3740	int total_delay_slots[MAX_DELAY_HISTOGRAM + 1];
3741	int total_annul_slots[MAX_DELAY_HISTOGRAM + 1];
3742
3743	for (reorg_pass_number = 0;
3744	reorg_pass_number < MAX_REORG_PASSES;
3745	reorg_pass_number++)
3746	{
3747	fprintf (stream: dump_file, format: ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3748	for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3749	{
3750	need_comma = 0;
3751	fprintf (stream: dump_file, format: ";; Reorg function #%d\n", i);
3752
3753	fprintf (stream: dump_file, format: ";; %d insns needing delay slots\n;; ",
3754	num_insns_needing_delays[i][reorg_pass_number]);
3755
3756	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3757	if (num_filled_delays[i][j][reorg_pass_number])
3758	{
3759	if (need_comma)
3760	fprintf (stream: dump_file, format: ", ");
3761	need_comma = 1;
3762	fprintf (stream: dump_file, format: "%d got %d delays",
3763	num_filled_delays[i][j][reorg_pass_number], j);
3764	}
3765	fprintf (stream: dump_file, format: "\n");
3766	}
3767	}
3768	memset (s: total_delay_slots, c: 0, n: sizeof total_delay_slots);
3769	memset (s: total_annul_slots, c: 0, n: sizeof total_annul_slots);
3770	for (insn = first; insn; insn = NEXT_INSN (insn))
3771	{
3772	if (! insn->deleted ()
3773	&& NONJUMP_INSN_P (insn)
3774	&& GET_CODE (PATTERN (insn)) != USE
3775	&& GET_CODE (PATTERN (insn)) != CLOBBER)
3776	{
3777	if (GET_CODE (PATTERN (insn)) == SEQUENCE)
3778	{
3779	rtx control;
3780	j = XVECLEN (PATTERN (insn), 0) - 1;
3781	if (j > MAX_DELAY_HISTOGRAM)
3782	j = MAX_DELAY_HISTOGRAM;
3783	control = XVECEXP (PATTERN (insn), 0, 0);
3784	if (JUMP_P (control) && INSN_ANNULLED_BRANCH_P (control))
3785	total_annul_slots[j]++;
3786	else
3787	total_delay_slots[j]++;
3788	}
3789	else if (num_delay_slots (insn) > 0)
3790	total_delay_slots[0]++;
3791	}
3792	}
3793	fprintf (stream: dump_file, format: ";; Reorg totals: ");
3794	need_comma = 0;
3795	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3796	{
3797	if (total_delay_slots[j])
3798	{
3799	if (need_comma)
3800	fprintf (stream: dump_file, format: ", ");
3801	need_comma = 1;
3802	fprintf (stream: dump_file, format: "%d got %d delays", total_delay_slots[j], j);
3803	}
3804	}
3805	fprintf (stream: dump_file, format: "\n");
3806
3807	if (ANNUL_IFTRUE_SLOTS || ANNUL_IFFALSE_SLOTS)
3808	{
3809	fprintf (stream: dump_file, format: ";; Reorg annuls: ");
3810	need_comma = 0;
3811	for (j = 0; j < MAX_DELAY_HISTOGRAM + 1; j++)
3812	{
3813	if (total_annul_slots[j])
3814	{
3815	if (need_comma)
3816	fprintf (stream: dump_file, format: ", ");
3817	need_comma = 1;
3818	fprintf (stream: dump_file, format: "%d got %d delays", total_annul_slots[j], j);
3819	}
3820	}
3821	fprintf (stream: dump_file, format: "\n");
3822	}
3823
3824	fprintf (stream: dump_file, format: "\n");
3825	}
3826
3827	if (!sibling_labels.is_empty ())
3828	{
3829	update_alignments (sibling_labels);
3830	sibling_labels.release ();
3831	}
3832
3833	free_resource_info ();
3834	free (ptr: uid_to_ruid);
3835	crtl->dbr_scheduled_p = true;
3836	}
3837
3838	/* Run delay slot optimization. */
3839	static void
3840	rest_of_handle_delay_slots (void)
3841	{
3842	if (DELAY_SLOTS)
3843	dbr_schedule (first: get_insns ());
3844	}
3845
3846	namespace {
3847
3848	const pass_data pass_data_delay_slots =
3849	{
3850	.type: RTL_PASS, /* type */
3851	.name: "dbr", /* name */
3852	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3853	.tv_id: TV_DBR_SCHED, /* tv_id */
3854	.properties_required: 0, /* properties_required */
3855	.properties_provided: 0, /* properties_provided */
3856	.properties_destroyed: 0, /* properties_destroyed */
3857	.todo_flags_start: 0, /* todo_flags_start */
3858	.todo_flags_finish: 0, /* todo_flags_finish */
3859	};
3860
3861	class pass_delay_slots : public rtl_opt_pass
3862	{
3863	public:
3864	pass_delay_slots (gcc::context *ctxt)
3865	: rtl_opt_pass (pass_data_delay_slots, ctxt)
3866	{}
3867
3868	/* opt_pass methods: */
3869	bool gate (function *) final override;
3870	unsigned int execute (function *) final override
3871	{
3872	rest_of_handle_delay_slots ();
3873	return 0;
3874	}
3875
3876	}; // class pass_delay_slots
3877
3878	bool
3879	pass_delay_slots::gate (function *)
3880	{
3881	/* At -O0 dataflow info isn't updated after RA. */
3882	if (DELAY_SLOTS)
3883	return optimize > 0 && flag_delayed_branch && !crtl->dbr_scheduled_p;
3884
3885	return false;
3886	}
3887
3888	} // anon namespace
3889
3890	rtl_opt_pass *
3891	make_pass_delay_slots (gcc::context *ctxt)
3892	{
3893	return new pass_delay_slots (ctxt);
3894	}
3895
3896	/* Machine dependent reorg pass. */
3897
3898	namespace {
3899
3900	const pass_data pass_data_machine_reorg =
3901	{
3902	.type: RTL_PASS, /* type */
3903	.name: "mach", /* name */
3904	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
3905	.tv_id: TV_MACH_DEP, /* tv_id */
3906	.properties_required: 0, /* properties_required */
3907	.properties_provided: 0, /* properties_provided */
3908	.properties_destroyed: 0, /* properties_destroyed */
3909	.todo_flags_start: 0, /* todo_flags_start */
3910	.todo_flags_finish: 0, /* todo_flags_finish */
3911	};
3912
3913	class pass_machine_reorg : public rtl_opt_pass
3914	{
3915	public:
3916	pass_machine_reorg (gcc::context *ctxt)
3917	: rtl_opt_pass (pass_data_machine_reorg, ctxt)
3918	{}
3919
3920	/* opt_pass methods: */
3921	bool gate (function *) final override
3922	{
3923	return targetm.machine_dependent_reorg != 0;
3924	}
3925
3926	unsigned int execute (function *) final override
3927	{
3928	targetm.machine_dependent_reorg ();
3929	return 0;
3930	}
3931
3932	}; // class pass_machine_reorg
3933
3934	} // anon namespace
3935
3936	rtl_opt_pass *
3937	make_pass_machine_reorg (gcc::context *ctxt)
3938	{
3939	return new pass_machine_reorg (ctxt);
3940	}
3941