1	/* Optimize jump instructions, for GNU compiler.
2	Copyright (C) 1987-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it under
7	the terms of the GNU General Public License as published by the Free
8	Software Foundation; either version 3, or (at your option) any later
9	version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12	WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	/* This is the pathetic reminder of old fame of the jump-optimization pass
21	of the compiler. Now it contains basically a set of utility functions to
22	operate with jumps.
23
24	Each CODE_LABEL has a count of the times it is used
25	stored in the LABEL_NUSES internal field, and each JUMP_INSN
26	has one label that it refers to stored in the
27	JUMP_LABEL internal field. With this we can detect labels that
28	become unused because of the deletion of all the jumps that
29	formerly used them. The JUMP_LABEL info is sometimes looked
30	at by later passes. For return insns, it contains either a
31	RETURN or a SIMPLE_RETURN rtx.
32
33	The subroutines redirect_jump and invert_jump are used
34	from other passes as well. */
35
36	#include "config.h"
37	#include "system.h"
38	#include "coretypes.h"
39	#include "backend.h"
40	#include "target.h"
41	#include "rtl.h"
42	#include "tree.h"
43	#include "cfghooks.h"
44	#include "tree-pass.h"
45	#include "memmodel.h"
46	#include "tm_p.h"
47	#include "insn-config.h"
48	#include "regs.h"
49	#include "emit-rtl.h"
50	#include "recog.h"
51	#include "cfgrtl.h"
52	#include "rtl-iter.h"
53
54	/* Optimize jump y; x: ... y: jumpif... x?
55	Don't know if it is worth bothering with. */
56	/* Optimize two cases of conditional jump to conditional jump?
57	This can never delete any instruction or make anything dead,
58	or even change what is live at any point.
59	So perhaps let combiner do it. */
60
61	static void init_label_info (rtx_insn *);
62	static void mark_all_labels (rtx_insn *);
63	static void mark_jump_label_1 (rtx, rtx_insn *, bool, bool);
64	static void mark_jump_label_asm (rtx, rtx_insn *);
65	static void redirect_exp_1 (rtx *, rtx, rtx, rtx_insn *);
66	static bool invert_exp_1 (rtx, rtx_insn *);
67
68	/* Worker for rebuild_jump_labels and rebuild_jump_labels_chain. */
69	static void
70	rebuild_jump_labels_1 (rtx_insn *f, bool count_forced)
71	{
72	timevar_push (tv: TV_REBUILD_JUMP);
73	init_label_info (f);
74	mark_all_labels (f);
75
76	/* Keep track of labels used from static data; we don't track them
77	closely enough to delete them here, so make sure their reference
78	count doesn't drop to zero. */
79
80	if (count_forced)
81	{
82	rtx_insn *insn;
83	unsigned int i;
84	FOR_EACH_VEC_SAFE_ELT (forced_labels, i, insn)
85	if (LABEL_P (insn))
86	LABEL_NUSES (insn)++;
87	}
88	timevar_pop (tv: TV_REBUILD_JUMP);
89	}
90
91	/* This function rebuilds the JUMP_LABEL field and REG_LABEL_TARGET
92	notes in jumping insns and REG_LABEL_OPERAND notes in non-jumping
93	instructions and jumping insns that have labels as operands
94	(e.g. cbranchsi4). */
95	void
96	rebuild_jump_labels (rtx_insn *f)
97	{
98	rebuild_jump_labels_1 (f, count_forced: true);
99	}
100
101	/* This function is like rebuild_jump_labels, but doesn't run over
102	forced_labels. It can be used on insn chains that aren't the
103	main function chain. */
104	void
105	rebuild_jump_labels_chain (rtx_insn *chain)
106	{
107	rebuild_jump_labels_1 (f: chain, count_forced: false);
108	}
109
110	/* Some old code expects exactly one BARRIER as the NEXT_INSN of a
111	non-fallthru insn. This is not generally true, as multiple barriers
112	may have crept in, or the BARRIER may be separated from the last
113	real insn by one or more NOTEs.
114
115	This simple pass moves barriers and removes duplicates so that the
116	old code is happy.
117	*/
118	static unsigned int
119	cleanup_barriers (void)
120	{
121	rtx_insn *insn;
122	for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
123	{
124	if (BARRIER_P (insn))
125	{
126	rtx_insn *prev = prev_nonnote_nondebug_insn (insn);
127	if (!prev)
128	continue;
129
130	if (BARRIER_P (prev))
131	delete_insn (insn);
132	else if (prev != PREV_INSN (insn))
133	{
134	basic_block bb = BLOCK_FOR_INSN (insn: prev);
135	rtx_insn *end = PREV_INSN (insn);
136	reorder_insns_nobb (insn, insn, prev);
137	if (bb)
138	{
139	/* If the backend called in machine reorg compute_bb_for_insn
140	and didn't free_bb_for_insn again, preserve basic block
141	boundaries. Move the end of basic block to PREV since
142	it is followed by a barrier now, and clear BLOCK_FOR_INSN
143	on the following notes.
144	??? Maybe the proper solution for the targets that have
145	cfg around after machine reorg is not to run cleanup_barriers
146	pass at all. */
147	BB_END (bb) = prev;
148	do
149	{
150	prev = NEXT_INSN (insn: prev);
151	if (prev != insn && BLOCK_FOR_INSN (insn: prev) == bb)
152	BLOCK_FOR_INSN (insn: prev) = NULL;
153	}
154	while (prev != end);
155	}
156	}
157	}
158	}
159	return 0;
160	}
161
162	namespace {
163
164	const pass_data pass_data_cleanup_barriers =
165	{
166	.type: RTL_PASS, /* type */
167	.name: "barriers", /* name */
168	.optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
169	.tv_id: TV_NONE, /* tv_id */
170	.properties_required: 0, /* properties_required */
171	.properties_provided: 0, /* properties_provided */
172	.properties_destroyed: 0, /* properties_destroyed */
173	.todo_flags_start: 0, /* todo_flags_start */
174	.todo_flags_finish: 0, /* todo_flags_finish */
175	};
176
177	class pass_cleanup_barriers : public rtl_opt_pass
178	{
179	public:
180	pass_cleanup_barriers (gcc::context *ctxt)
181	: rtl_opt_pass (pass_data_cleanup_barriers, ctxt)
182	{}
183
184	/* opt_pass methods: */
185	unsigned int execute (function *) final override
186	{
187	return cleanup_barriers ();
188	}
189
190	}; // class pass_cleanup_barriers
191
192	} // anon namespace
193
194	rtl_opt_pass *
195	make_pass_cleanup_barriers (gcc::context *ctxt)
196	{
197	return new pass_cleanup_barriers (ctxt);
198	}
199
200
201	/* Initialize LABEL_NUSES and JUMP_LABEL fields, add REG_LABEL_TARGET
202	for remaining targets for JUMP_P. Delete any REG_LABEL_OPERAND
203	notes whose labels don't occur in the insn any more. */
204
205	static void
206	init_label_info (rtx_insn *f)
207	{
208	rtx_insn *insn;
209
210	for (insn = f; insn; insn = NEXT_INSN (insn))
211	{
212	if (LABEL_P (insn))
213	LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
214
215	/* REG_LABEL_TARGET notes (including the JUMP_LABEL field) are
216	sticky and not reset here; that way we won't lose association
217	with a label when e.g. the source for a target register
218	disappears out of reach for targets that may use jump-target
219	registers. Jump transformations are supposed to transform
220	any REG_LABEL_TARGET notes. The target label reference in a
221	branch may disappear from the branch (and from the
222	instruction before it) for other reasons, like register
223	allocation. */
224
225	if (INSN_P (insn))
226	{
227	rtx note, next;
228
229	for (note = REG_NOTES (insn); note; note = next)
230	{
231	next = XEXP (note, 1);
232	if (REG_NOTE_KIND (note) == REG_LABEL_OPERAND
233	&& ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
234	remove_note (insn, note);
235	}
236	}
237	}
238	}
239
240	/* A subroutine of mark_all_labels. Trivially propagate a simple label
241	load into a jump_insn that uses it. */
242
243	static void
244	maybe_propagate_label_ref (rtx_insn *jump_insn, rtx_insn *prev_nonjump_insn)
245	{
246	rtx label_note, pc, pc_src;
247
248	pc = pc_set (jump_insn);
249	pc_src = pc != NULL ? SET_SRC (pc) : NULL;
250	label_note = find_reg_note (prev_nonjump_insn, REG_LABEL_OPERAND, NULL);
251
252	/* If the previous non-jump insn sets something to a label,
253	something that this jump insn uses, make that label the primary
254	target of this insn if we don't yet have any. That previous
255	insn must be a single_set and not refer to more than one label.
256	The jump insn must not refer to other labels as jump targets
257	and must be a plain (set (pc) ...), maybe in a parallel, and
258	may refer to the item being set only directly or as one of the
259	arms in an IF_THEN_ELSE. */
260
261	if (label_note != NULL && pc_src != NULL)
262	{
263	rtx label_set = single_set (insn: prev_nonjump_insn);
264	rtx label_dest = label_set != NULL ? SET_DEST (label_set) : NULL;
265
266	if (label_set != NULL
267	/* The source must be the direct LABEL_REF, not a
268	PLUS, UNSPEC, IF_THEN_ELSE etc. */
269	&& GET_CODE (SET_SRC (label_set)) == LABEL_REF
270	&& (rtx_equal_p (label_dest, pc_src)
271	|| (GET_CODE (pc_src) == IF_THEN_ELSE
272	&& (rtx_equal_p (label_dest, XEXP (pc_src, 1))
273	|| rtx_equal_p (label_dest, XEXP (pc_src, 2))))))
274	{
275	/* The CODE_LABEL referred to in the note must be the
276	CODE_LABEL in the LABEL_REF of the "set". We can
277	conveniently use it for the marker function, which
278	requires a LABEL_REF wrapping. */
279	gcc_assert (XEXP (label_note, 0) == label_ref_label (SET_SRC (label_set)));
280
281	mark_jump_label_1 (label_set, jump_insn, false, true);
282
283	gcc_assert (JUMP_LABEL (jump_insn) == XEXP (label_note, 0));
284	}
285	}
286	}
287
288	/* Mark the label each jump jumps to.
289	Combine consecutive labels, and count uses of labels. */
290
291	static void
292	mark_all_labels (rtx_insn *f)
293	{
294	rtx_insn *insn;
295
296	if (current_ir_type () == IR_RTL_CFGLAYOUT)
297	{
298	basic_block bb;
299	FOR_EACH_BB_FN (bb, cfun)
300	{
301	/* In cfglayout mode, we don't bother with trivial next-insn
302	propagation of LABEL_REFs into JUMP_LABEL. This will be
303	handled by other optimizers using better algorithms. */
304	FOR_BB_INSNS (bb, insn)
305	{
306	gcc_assert (! insn->deleted ());
307	if (NONDEBUG_INSN_P (insn))
308	mark_jump_label (PATTERN (insn), insn, 0);
309	}
310
311	/* In cfglayout mode, there may be non-insns between the
312	basic blocks. If those non-insns represent tablejump data,
313	they contain label references that we must record. */
314	for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
315	if (JUMP_TABLE_DATA_P (insn))
316	mark_jump_label (PATTERN (insn), insn, 0);
317	for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
318	if (JUMP_TABLE_DATA_P (insn))
319	mark_jump_label (PATTERN (insn), insn, 0);
320	}
321	}
322	else
323	{
324	rtx_insn *prev_nonjump_insn = NULL;
325	for (insn = f; insn; insn = NEXT_INSN (insn))
326	{
327	if (insn->deleted ())
328	;
329	else if (LABEL_P (insn))
330	prev_nonjump_insn = NULL;
331	else if (JUMP_TABLE_DATA_P (insn))
332	mark_jump_label (PATTERN (insn), insn, 0);
333	else if (NONDEBUG_INSN_P (insn))
334	{
335	mark_jump_label (PATTERN (insn), insn, 0);
336	if (JUMP_P (insn))
337	{
338	if (JUMP_LABEL (insn) == NULL && prev_nonjump_insn != NULL)
339	maybe_propagate_label_ref (jump_insn: insn, prev_nonjump_insn);
340	}
341	else
342	prev_nonjump_insn = insn;
343	}
344	}
345	}
346	}
347
348	/* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
349	of reversed comparison if it is possible to do so. Otherwise return UNKNOWN.
350	UNKNOWN may be returned in case we are having CC_MODE compare and we don't
351	know whether it's source is floating point or integer comparison. Machine
352	description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
353	to help this function avoid overhead in these cases. */
354	enum rtx_code
355	reversed_comparison_code_parts (enum rtx_code code, const_rtx arg0,
356	const_rtx arg1, const rtx_insn *insn)
357	{
358	machine_mode mode;
359
360	/* If this is not actually a comparison, we can't reverse it. */
361	if (GET_RTX_CLASS (code) != RTX_COMPARE
362	&& GET_RTX_CLASS (code) != RTX_COMM_COMPARE)
363	return UNKNOWN;
364
365	mode = GET_MODE (arg0);
366	if (mode == VOIDmode)
367	mode = GET_MODE (arg1);
368
369	/* First see if machine description supplies us way to reverse the
370	comparison. Give it priority over everything else to allow
371	machine description to do tricks. */
372	if (GET_MODE_CLASS (mode) == MODE_CC
373	&& REVERSIBLE_CC_MODE (mode))
374	return REVERSE_CONDITION (code, mode);
375
376	/* Try a few special cases based on the comparison code. */
377	switch (code)
378	{
379	case GEU:
380	case GTU:
381	case LEU:
382	case LTU:
383	case NE:
384	case EQ:
385	/* It is always safe to reverse EQ and NE, even for the floating
386	point. Similarly the unsigned comparisons are never used for
387	floating point so we can reverse them in the default way. */
388	return reverse_condition (code);
389	case ORDERED:
390	case UNORDERED:
391	case LTGT:
392	case UNEQ:
393	/* In case we already see unordered comparison, we can be sure to
394	be dealing with floating point so we don't need any more tests. */
395	return reverse_condition_maybe_unordered (code);
396	case UNLT:
397	case UNLE:
398	case UNGT:
399	case UNGE:
400	/* We don't have safe way to reverse these yet. */
401	return UNKNOWN;
402	default:
403	break;
404	}
405
406	if (GET_MODE_CLASS (mode) == MODE_CC)
407	{
408	/* Try to search for the comparison to determine the real mode.
409	This code is expensive, but with sane machine description it
410	will be never used, since REVERSIBLE_CC_MODE will return true
411	in all cases. */
412	if (! insn)
413	return UNKNOWN;
414
415	/* These CONST_CAST's are okay because prev_nonnote_insn just
416	returns its argument and we assign it to a const_rtx
417	variable. */
418	for (rtx_insn *prev = prev_nonnote_insn (const_cast<rtx_insn *> (insn));
419	prev != 0 && !LABEL_P (prev);
420	prev = prev_nonnote_insn (prev))
421	{
422	const_rtx set = set_of (arg0, prev);
423	if (set && GET_CODE (set) == SET
424	&& rtx_equal_p (SET_DEST (set), arg0))
425	{
426	rtx src = SET_SRC (set);
427
428	if (GET_CODE (src) == COMPARE)
429	{
430	rtx comparison = src;
431	arg0 = XEXP (src, 0);
432	mode = GET_MODE (arg0);
433	if (mode == VOIDmode)
434	mode = GET_MODE (XEXP (comparison, 1));
435	break;
436	}
437	/* We can get past reg-reg moves. This may be useful for model
438	of i387 comparisons that first move flag registers around. */
439	if (REG_P (src))
440	{
441	arg0 = src;
442	continue;
443	}
444	}
445	/* If register is clobbered in some ununderstandable way,
446	give up. */
447	if (set)
448	return UNKNOWN;
449	}
450	}
451
452	/* Test for an integer condition, or a floating-point comparison
453	in which NaNs can be ignored. */
454	if (CONST_INT_P (arg0)
455	|| (GET_MODE (arg0) != VOIDmode
456	&& GET_MODE_CLASS (mode) != MODE_CC
457	&& !HONOR_NANS (mode)))
458	return reverse_condition (code);
459
460	return UNKNOWN;
461	}
462
463	/* A wrapper around the previous function to take COMPARISON as rtx
464	expression. This simplifies many callers. */
465	enum rtx_code
466	reversed_comparison_code (const_rtx comparison, const rtx_insn *insn)
467	{
468	if (!COMPARISON_P (comparison))
469	return UNKNOWN;
470	return reversed_comparison_code_parts (GET_CODE (comparison),
471	XEXP (comparison, 0),
472	XEXP (comparison, 1), insn);
473	}
474
475	/* Return comparison with reversed code of EXP.
476	Return NULL_RTX in case we fail to do the reversal. */
477	rtx
478	reversed_comparison (const_rtx exp, machine_mode mode)
479	{
480	enum rtx_code reversed_code = reversed_comparison_code (comparison: exp, NULL);
481	if (reversed_code == UNKNOWN)
482	return NULL_RTX;
483	else
484	return simplify_gen_relational (code: reversed_code, mode, VOIDmode,
485	XEXP (exp, 0), XEXP (exp, 1));
486	}
487
488
489	/* Given an rtx-code for a comparison, return the code for the negated
490	comparison. If no such code exists, return UNKNOWN.
491
492	WATCH OUT! reverse_condition is not safe to use on a jump that might
493	be acting on the results of an IEEE floating point comparison, because
494	of the special treatment of non-signaling nans in comparisons.
495	Use reversed_comparison_code instead. */
496
497	enum rtx_code
498	reverse_condition (enum rtx_code code)
499	{
500	switch (code)
501	{
502	case EQ:
503	return NE;
504	case NE:
505	return EQ;
506	case GT:
507	return LE;
508	case GE:
509	return LT;
510	case LT:
511	return GE;
512	case LE:
513	return GT;
514	case GTU:
515	return LEU;
516	case GEU:
517	return LTU;
518	case LTU:
519	return GEU;
520	case LEU:
521	return GTU;
522	case UNORDERED:
523	return ORDERED;
524	case ORDERED:
525	return UNORDERED;
526
527	case UNLT:
528	case UNLE:
529	case UNGT:
530	case UNGE:
531	case UNEQ:
532	case LTGT:
533	return UNKNOWN;
534
535	default:
536	gcc_unreachable ();
537	}
538	}
539
540	/* Similar, but we're allowed to generate unordered comparisons, which
541	makes it safe for IEEE floating-point. Of course, we have to recognize
542	that the target will support them too... */
543
544	enum rtx_code
545	reverse_condition_maybe_unordered (enum rtx_code code)
546	{
547	switch (code)
548	{
549	case EQ:
550	return NE;
551	case NE:
552	return EQ;
553	case GT:
554	return UNLE;
555	case GE:
556	return UNLT;
557	case LT:
558	return UNGE;
559	case LE:
560	return UNGT;
561	case LTGT:
562	return UNEQ;
563	case UNORDERED:
564	return ORDERED;
565	case ORDERED:
566	return UNORDERED;
567	case UNLT:
568	return GE;
569	case UNLE:
570	return GT;
571	case UNGT:
572	return LE;
573	case UNGE:
574	return LT;
575	case UNEQ:
576	return LTGT;
577
578	default:
579	gcc_unreachable ();
580	}
581	}
582
583	/* Similar, but return the code when two operands of a comparison are swapped.
584	This IS safe for IEEE floating-point. */
585
586	enum rtx_code
587	swap_condition (enum rtx_code code)
588	{
589	switch (code)
590	{
591	case EQ:
592	case NE:
593	case UNORDERED:
594	case ORDERED:
595	case UNEQ:
596	case LTGT:
597	return code;
598
599	case GT:
600	return LT;
601	case GE:
602	return LE;
603	case LT:
604	return GT;
605	case LE:
606	return GE;
607	case GTU:
608	return LTU;
609	case GEU:
610	return LEU;
611	case LTU:
612	return GTU;
613	case LEU:
614	return GEU;
615	case UNLT:
616	return UNGT;
617	case UNLE:
618	return UNGE;
619	case UNGT:
620	return UNLT;
621	case UNGE:
622	return UNLE;
623
624	default:
625	gcc_unreachable ();
626	}
627	}
628
629	/* Given a comparison CODE, return the corresponding unsigned comparison.
630	If CODE is an equality comparison or already an unsigned comparison,
631	CODE is returned. */
632
633	enum rtx_code
634	unsigned_condition (enum rtx_code code)
635	{
636	switch (code)
637	{
638	case EQ:
639	case NE:
640	case GTU:
641	case GEU:
642	case LTU:
643	case LEU:
644	return code;
645
646	case GT:
647	return GTU;
648	case GE:
649	return GEU;
650	case LT:
651	return LTU;
652	case LE:
653	return LEU;
654
655	default:
656	gcc_unreachable ();
657	}
658	}
659
660	/* Similarly, return the signed version of a comparison. */
661
662	enum rtx_code
663	signed_condition (enum rtx_code code)
664	{
665	switch (code)
666	{
667	case EQ:
668	case NE:
669	case GT:
670	case GE:
671	case LT:
672	case LE:
673	return code;
674
675	case GTU:
676	return GT;
677	case GEU:
678	return GE;
679	case LTU:
680	return LT;
681	case LEU:
682	return LE;
683
684	default:
685	gcc_unreachable ();
686	}
687	}
688
689	/* Return true if CODE1 is more strict than CODE2, i.e., if the
690	truth of CODE1 implies the truth of CODE2. */
691
692	bool
693	comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
694	{
695	/* UNKNOWN comparison codes can happen as a result of trying to revert
696	comparison codes.
697	They can't match anything, so we have to reject them here. */
698	if (code1 == UNKNOWN || code2 == UNKNOWN)
699	return false;
700
701	if (code1 == code2)
702	return true;
703
704	switch (code1)
705	{
706	case UNEQ:
707	if (code2 == UNLE || code2 == UNGE)
708	return true;
709	break;
710
711	case EQ:
712	if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
713	|| code2 == ORDERED)
714	return true;
715	break;
716
717	case UNLT:
718	if (code2 == UNLE || code2 == NE)
719	return true;
720	break;
721
722	case LT:
723	if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
724	return true;
725	break;
726
727	case UNGT:
728	if (code2 == UNGE || code2 == NE)
729	return true;
730	break;
731
732	case GT:
733	if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
734	return true;
735	break;
736
737	case GE:
738	case LE:
739	if (code2 == ORDERED)
740	return true;
741	break;
742
743	case LTGT:
744	if (code2 == NE || code2 == ORDERED)
745	return true;
746	break;
747
748	case LTU:
749	if (code2 == LEU || code2 == NE)
750	return true;
751	break;
752
753	case GTU:
754	if (code2 == GEU || code2 == NE)
755	return true;
756	break;
757
758	case UNORDERED:
759	if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
760	|| code2 == UNGE || code2 == UNGT)
761	return true;
762	break;
763
764	default:
765	break;
766	}
767
768	return false;
769	}
770
771	/* Return true if INSN is an unconditional jump and nothing else. */
772
773	bool
774	simplejump_p (const rtx_insn *insn)
775	{
776	return (JUMP_P (insn)
777	&& GET_CODE (PATTERN (insn)) == SET
778	&& GET_CODE (SET_DEST (PATTERN (insn))) == PC
779	&& GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
780	}
781
782	/* Return true if INSN is a (possibly) conditional jump
783	and nothing more.
784
785	Use of this function is deprecated, since we need to support combined
786	branch and compare insns. Use any_condjump_p instead whenever possible. */
787
788	bool
789	condjump_p (const rtx_insn *insn)
790	{
791	const_rtx x = PATTERN (insn);
792
793	if (GET_CODE (x) != SET
794	|| GET_CODE (SET_DEST (x)) != PC)
795	return false;
796
797	x = SET_SRC (x);
798	if (GET_CODE (x) == LABEL_REF)
799	return true;
800	else
801	return (GET_CODE (x) == IF_THEN_ELSE
802	&& ((GET_CODE (XEXP (x, 2)) == PC
803	&& (GET_CODE (XEXP (x, 1)) == LABEL_REF
804	|| ANY_RETURN_P (XEXP (x, 1))))
805	|| (GET_CODE (XEXP (x, 1)) == PC
806	&& (GET_CODE (XEXP (x, 2)) == LABEL_REF
807	|| ANY_RETURN_P (XEXP (x, 2))))));
808	}
809
810	/* Return true if INSN is a (possibly) conditional jump inside a
811	PARALLEL.
812
813	Use this function is deprecated, since we need to support combined
814	branch and compare insns. Use any_condjump_p instead whenever possible. */
815
816	bool
817	condjump_in_parallel_p (const rtx_insn *insn)
818	{
819	const_rtx x = PATTERN (insn);
820
821	if (GET_CODE (x) != PARALLEL)
822	return false;
823	else
824	x = XVECEXP (x, 0, 0);
825
826	if (GET_CODE (x) != SET)
827	return false;
828	if (GET_CODE (SET_DEST (x)) != PC)
829	return false;
830	if (GET_CODE (SET_SRC (x)) == LABEL_REF)
831	return true;
832	if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
833	return false;
834	if (XEXP (SET_SRC (x), 2) == pc_rtx
835	&& (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
836	|| ANY_RETURN_P (XEXP (SET_SRC (x), 1))))
837	return true;
838	if (XEXP (SET_SRC (x), 1) == pc_rtx
839	&& (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
840	|| ANY_RETURN_P (XEXP (SET_SRC (x), 2))))
841	return true;
842	return false;
843	}
844
845	/* Return set of PC, otherwise NULL. */
846
847	rtx
848	pc_set (const rtx_insn *insn)
849	{
850	rtx pat;
851	if (!JUMP_P (insn))
852	return NULL_RTX;
853	pat = PATTERN (insn);
854
855	/* The set is allowed to appear either as the insn pattern or
856	the first set in a PARALLEL, UNSPEC or UNSPEC_VOLATILE. */
857	switch (GET_CODE (pat))
858	{
859	case PARALLEL:
860	case UNSPEC:
861	case UNSPEC_VOLATILE:
862	pat = XVECEXP (pat, 0, 0);
863	break;
864	default:
865	break;
866	}
867	if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
868	return pat;
869
870	return NULL_RTX;
871	}
872
873	/* Return true when insn is an unconditional direct jump,
874	possibly bundled inside a PARALLEL, UNSPEC or UNSPEC_VOLATILE.
875	The instruction may have various other effects so before removing the jump
876	you must verify onlyjump_p. */
877
878	bool
879	any_uncondjump_p (const rtx_insn *insn)
880	{
881	const_rtx x = pc_set (insn);
882	if (!x)
883	return false;
884	if (GET_CODE (SET_SRC (x)) != LABEL_REF)
885	return false;
886	if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
887	return false;
888	return true;
889	}
890
891	/* Return true when insn is a conditional jump. This function works for
892	instructions containing PC sets in PARALLELs, UNSPECs or UNSPEC_VOLATILEs.
893	The instruction may have various other effects so before removing the jump
894	you must verify onlyjump_p.
895
896	Note that unlike condjump_p it returns false for unconditional jumps. */
897
898	bool
899	any_condjump_p (const rtx_insn *insn)
900	{
901	const_rtx x = pc_set (insn);
902	enum rtx_code a, b;
903
904	if (!x)
905	return false;
906	if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
907	return false;
908
909	a = GET_CODE (XEXP (SET_SRC (x), 1));
910	b = GET_CODE (XEXP (SET_SRC (x), 2));
911
912	return ((b == PC && (a == LABEL_REF || a == RETURN || a == SIMPLE_RETURN))
913	|| (a == PC
914	&& (b == LABEL_REF || b == RETURN || b == SIMPLE_RETURN)));
915	}
916
917	/* Return the label of a conditional jump. */
918
919	rtx
920	condjump_label (const rtx_insn *insn)
921	{
922	rtx x = pc_set (insn);
923
924	if (!x)
925	return NULL_RTX;
926	x = SET_SRC (x);
927	if (GET_CODE (x) == LABEL_REF)
928	return x;
929	if (GET_CODE (x) != IF_THEN_ELSE)
930	return NULL_RTX;
931	if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
932	return XEXP (x, 1);
933	if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
934	return XEXP (x, 2);
935	return NULL_RTX;
936	}
937
938	/* Return TRUE if INSN is a return jump. */
939
940	bool
941	returnjump_p (const rtx_insn *insn)
942	{
943	if (JUMP_P (insn))
944	{
945	subrtx_iterator::array_type array;
946	FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
947	{
948	const_rtx x = *iter;
949	switch (GET_CODE (x))
950	{
951	case RETURN:
952	case SIMPLE_RETURN:
953	case EH_RETURN:
954	return true;
955
956	case SET:
957	if (SET_IS_RETURN_P (x))
958	return true;
959	break;
960
961	default:
962	break;
963	}
964	}
965	}
966	return false;
967	}
968
969	/* Return true if INSN is a (possibly conditional) return insn. */
970
971	bool
972	eh_returnjump_p (rtx_insn *insn)
973	{
974	if (JUMP_P (insn))
975	{
976	subrtx_iterator::array_type array;
977	FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
978	if (GET_CODE (*iter) == EH_RETURN)
979	return true;
980	}
981	return false;
982	}
983
984	/* Return true if INSN is a jump that only transfers control and
985	nothing more. */
986
987	bool
988	onlyjump_p (const rtx_insn *insn)
989	{
990	rtx set;
991
992	if (!JUMP_P (insn))
993	return false;
994
995	set = single_set (insn);
996	if (set == NULL)
997	return false;
998	if (GET_CODE (SET_DEST (set)) != PC)
999	return false;
1000	if (side_effects_p (SET_SRC (set)))
1001	return false;
1002
1003	return true;
1004	}
1005
1006	/* Return true iff INSN is a jump and its JUMP_LABEL is a label, not
1007	NULL or a return. */
1008	bool
1009	jump_to_label_p (const rtx_insn *insn)
1010	{
1011	return (JUMP_P (insn)
1012	&& JUMP_LABEL (insn) != NULL && !ANY_RETURN_P (JUMP_LABEL (insn)));
1013	}
1014
1015	/* Find all CODE_LABELs referred to in X, and increment their use
1016	counts. If INSN is a JUMP_INSN and there is at least one
1017	CODE_LABEL referenced in INSN as a jump target, then store the last
1018	one in JUMP_LABEL (INSN). For a tablejump, this must be the label
1019	for the ADDR_VEC. Store any other jump targets as REG_LABEL_TARGET
1020	notes. If INSN is an INSN or a CALL_INSN or non-target operands of
1021	a JUMP_INSN, and there is at least one CODE_LABEL referenced in
1022	INSN, add a REG_LABEL_OPERAND note containing that label to INSN.
1023	For returnjumps, the JUMP_LABEL will also be set as appropriate.
1024
1025	Note that two labels separated by a loop-beginning note
1026	must be kept distinct if we have not yet done loop-optimization,
1027	because the gap between them is where loop-optimize
1028	will want to move invariant code to. CROSS_JUMP tells us
1029	that loop-optimization is done with. */
1030
1031	void
1032	mark_jump_label (rtx x, rtx_insn *insn, int in_mem)
1033	{
1034	rtx asmop = extract_asm_operands (x);
1035	if (asmop)
1036	mark_jump_label_asm (asmop, insn);
1037	else
1038	mark_jump_label_1 (x, insn, in_mem != 0,
1039	(insn != NULL && x == PATTERN (insn) && JUMP_P (insn)));
1040	}
1041
1042	/* Worker function for mark_jump_label. IN_MEM is TRUE when X occurs
1043	within a (MEM ...). IS_TARGET is TRUE when X is to be treated as a
1044	jump-target; when the JUMP_LABEL field of INSN should be set or a
1045	REG_LABEL_TARGET note should be added, not a REG_LABEL_OPERAND
1046	note. */
1047
1048	static void
1049	mark_jump_label_1 (rtx x, rtx_insn *insn, bool in_mem, bool is_target)
1050	{
1051	RTX_CODE code = GET_CODE (x);
1052	int i;
1053	const char *fmt;
1054
1055	switch (code)
1056	{
1057	case PC:
1058	case REG:
1059	case CLOBBER:
1060	case CALL:
1061	return;
1062
1063	case RETURN:
1064	case SIMPLE_RETURN:
1065	if (is_target)
1066	{
1067	gcc_assert (JUMP_LABEL (insn) == NULL || JUMP_LABEL (insn) == x);
1068	JUMP_LABEL (insn) = x;
1069	}
1070	return;
1071
1072	case MEM:
1073	in_mem = true;
1074	break;
1075
1076	case SEQUENCE:
1077	{
1078	rtx_sequence *seq = as_a <rtx_sequence *> (p: x);
1079	for (i = 0; i < seq->len (); i++)
1080	mark_jump_label (x: PATTERN (insn: seq->insn (index: i)),
1081	insn: seq->insn (index: i), in_mem: 0);
1082	}
1083	return;
1084
1085	case SYMBOL_REF:
1086	if (!in_mem)
1087	return;
1088
1089	/* If this is a constant-pool reference, see if it is a label. */
1090	if (CONSTANT_POOL_ADDRESS_P (x))
1091	mark_jump_label_1 (x: get_pool_constant (x), insn, in_mem, is_target);
1092	break;
1093
1094	/* Handle operands in the condition of an if-then-else as for a
1095	non-jump insn. */
1096	case IF_THEN_ELSE:
1097	if (!is_target)
1098	break;
1099	mark_jump_label_1 (XEXP (x, 0), insn, in_mem, is_target: false);
1100	mark_jump_label_1 (XEXP (x, 1), insn, in_mem, is_target: true);
1101	mark_jump_label_1 (XEXP (x, 2), insn, in_mem, is_target: true);
1102	return;
1103
1104	case LABEL_REF:
1105	{
1106	rtx_insn *label = label_ref_label (ref: x);
1107
1108	/* Ignore remaining references to unreachable labels that
1109	have been deleted. */
1110	if (NOTE_P (label)
1111	&& NOTE_KIND (label) == NOTE_INSN_DELETED_LABEL)
1112	break;
1113
1114	gcc_assert (LABEL_P (label));
1115
1116	/* Ignore references to labels of containing functions. */
1117	if (LABEL_REF_NONLOCAL_P (x))
1118	break;
1119
1120	set_label_ref_label (ref: x, label);
1121	if (! insn || ! insn->deleted ())
1122	++LABEL_NUSES (label);
1123
1124	if (insn)
1125	{
1126	if (is_target
1127	/* Do not change a previous setting of JUMP_LABEL. If the
1128	JUMP_LABEL slot is occupied by a different label,
1129	create a note for this label. */
1130	&& (JUMP_LABEL (insn) == NULL || JUMP_LABEL (insn) == label))
1131	JUMP_LABEL (insn) = label;
1132	else
1133	{
1134	enum reg_note kind
1135	= is_target ? REG_LABEL_TARGET : REG_LABEL_OPERAND;
1136
1137	/* Add a REG_LABEL_OPERAND or REG_LABEL_TARGET note
1138	for LABEL unless there already is one. All uses of
1139	a label, except for the primary target of a jump,
1140	must have such a note. */
1141	if (! find_reg_note (insn, kind, label))
1142	add_reg_note (insn, kind, label);
1143	}
1144	}
1145	return;
1146	}
1147
1148	/* Do walk the labels in a vector, but not the first operand of an
1149	ADDR_DIFF_VEC. Don't set the JUMP_LABEL of a vector. */
1150	case ADDR_VEC:
1151	case ADDR_DIFF_VEC:
1152	if (! insn->deleted ())
1153	{
1154	int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1155
1156	for (i = 0; i < XVECLEN (x, eltnum); i++)
1157	mark_jump_label_1 (XVECEXP (x, eltnum, i), NULL, in_mem,
1158	is_target);
1159	}
1160	return;
1161
1162	default:
1163	break;
1164	}
1165
1166	fmt = GET_RTX_FORMAT (code);
1167
1168	/* The primary target of a tablejump is the label of the ADDR_VEC,
1169	which is canonically mentioned *last* in the insn. To get it
1170	marked as JUMP_LABEL, we iterate over items in reverse order. */
1171	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1172	{
1173	if (fmt[i] == 'e')
1174	mark_jump_label_1 (XEXP (x, i), insn, in_mem, is_target);
1175	else if (fmt[i] == 'E')
1176	{
1177	int j;
1178
1179	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1180	mark_jump_label_1 (XVECEXP (x, i, j), insn, in_mem,
1181	is_target);
1182	}
1183	}
1184	}
1185
1186	/* Worker function for mark_jump_label. Handle asm insns specially.
1187	In particular, output operands need not be considered so we can
1188	avoid re-scanning the replicated asm_operand. Also, the asm_labels
1189	need to be considered targets. */
1190
1191	static void
1192	mark_jump_label_asm (rtx asmop, rtx_insn *insn)
1193	{
1194	int i;
1195
1196	for (i = ASM_OPERANDS_INPUT_LENGTH (asmop) - 1; i >= 0; --i)
1197	mark_jump_label_1 (ASM_OPERANDS_INPUT (asmop, i), insn, in_mem: false, is_target: false);
1198
1199	for (i = ASM_OPERANDS_LABEL_LENGTH (asmop) - 1; i >= 0; --i)
1200	mark_jump_label_1 (ASM_OPERANDS_LABEL (asmop, i), insn, in_mem: false, is_target: true);
1201	}
1202
1203	/* Delete insn INSN from the chain of insns and update label ref counts
1204	and delete insns now unreachable.
1205
1206	Returns the first insn after INSN that was not deleted.
1207
1208	Usage of this instruction is deprecated. Use delete_insn instead and
1209	subsequent cfg_cleanup pass to delete unreachable code if needed. */
1210
1211	rtx_insn *
1212	delete_related_insns (rtx uncast_insn)
1213	{
1214	rtx_insn *insn = as_a <rtx_insn *> (p: uncast_insn);
1215	bool was_code_label = LABEL_P (insn);
1216	rtx note;
1217	rtx_insn *next = NEXT_INSN (insn), *prev = PREV_INSN (insn);
1218
1219	while (next && next->deleted ())
1220	next = NEXT_INSN (insn: next);
1221
1222	/* This insn is already deleted => return first following nondeleted. */
1223	if (insn->deleted ())
1224	return next;
1225
1226	delete_insn (insn);
1227
1228	/* If instruction is followed by a barrier,
1229	delete the barrier too. */
1230
1231	if (next != 0 && BARRIER_P (next))
1232	delete_insn (next);
1233
1234	/* If deleting a jump, decrement the count of the label,
1235	and delete the label if it is now unused. */
1236
1237	if (jump_to_label_p (insn))
1238	{
1239	rtx lab = JUMP_LABEL (insn);
1240	rtx_jump_table_data *lab_next;
1241
1242	if (LABEL_NUSES (lab) == 0)
1243	/* This can delete NEXT or PREV,
1244	either directly if NEXT is JUMP_LABEL (INSN),
1245	or indirectly through more levels of jumps. */
1246	delete_related_insns (uncast_insn: lab);
1247	else if (tablejump_p (insn, NULL, &lab_next))
1248	{
1249	/* If we're deleting the tablejump, delete the dispatch table.
1250	We may not be able to kill the label immediately preceding
1251	just yet, as it might be referenced in code leading up to
1252	the tablejump. */
1253	delete_related_insns (uncast_insn: lab_next);
1254	}
1255	}
1256
1257	/* Likewise if we're deleting a dispatch table. */
1258
1259	if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (p: insn))
1260	{
1261	rtvec labels = table->get_labels ();
1262	int i;
1263	int len = GET_NUM_ELEM (labels);
1264
1265	for (i = 0; i < len; i++)
1266	if (LABEL_NUSES (XEXP (RTVEC_ELT (labels, i), 0)) == 0)
1267	delete_related_insns (XEXP (RTVEC_ELT (labels, i), 0));
1268	while (next && next->deleted ())
1269	next = NEXT_INSN (insn: next);
1270	return next;
1271	}
1272
1273	/* Likewise for any JUMP_P / INSN / CALL_INSN with a
1274	REG_LABEL_OPERAND or REG_LABEL_TARGET note. */
1275	if (INSN_P (insn))
1276	for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1277	if ((REG_NOTE_KIND (note) == REG_LABEL_OPERAND
1278	|| REG_NOTE_KIND (note) == REG_LABEL_TARGET)
1279	/* This could also be a NOTE_INSN_DELETED_LABEL note. */
1280	&& LABEL_P (XEXP (note, 0)))
1281	if (LABEL_NUSES (XEXP (note, 0)) == 0)
1282	delete_related_insns (XEXP (note, 0));
1283
1284	while (prev && (prev->deleted () || NOTE_P (prev)))
1285	prev = PREV_INSN (insn: prev);
1286
1287	/* If INSN was a label and a dispatch table follows it,
1288	delete the dispatch table. The tablejump must have gone already.
1289	It isn't useful to fall through into a table. */
1290
1291	if (was_code_label
1292	&& NEXT_INSN (insn) != 0
1293	&& JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
1294	next = delete_related_insns (uncast_insn: NEXT_INSN (insn));
1295
1296	/* If INSN was a label, delete insns following it if now unreachable. */
1297
1298	if (was_code_label && prev && BARRIER_P (prev))
1299	{
1300	enum rtx_code code;
1301	while (next)
1302	{
1303	code = GET_CODE (next);
1304	if (code == NOTE)
1305	next = NEXT_INSN (insn: next);
1306	/* Keep going past other deleted labels to delete what follows. */
1307	else if (code == CODE_LABEL && next->deleted ())
1308	next = NEXT_INSN (insn: next);
1309	/* Keep the (use (insn))s created by dbr_schedule, which needs
1310	them in order to track liveness relative to a previous
1311	barrier. */
1312	else if (INSN_P (next)
1313	&& GET_CODE (PATTERN (next)) == USE
1314	&& INSN_P (XEXP (PATTERN (next), 0)))
1315	next = NEXT_INSN (insn: next);
1316	else if (code == BARRIER || INSN_P (next))
1317	/* Note: if this deletes a jump, it can cause more
1318	deletion of unreachable code, after a different label.
1319	As long as the value from this recursive call is correct,
1320	this invocation functions correctly. */
1321	next = delete_related_insns (uncast_insn: next);
1322	else
1323	break;
1324	}
1325	}
1326
1327	/* I feel a little doubtful about this loop,
1328	but I see no clean and sure alternative way
1329	to find the first insn after INSN that is not now deleted.
1330	I hope this works. */
1331	while (next && next->deleted ())
1332	next = NEXT_INSN (insn: next);
1333	return next;
1334	}
1335
1336	/* Delete a range of insns from FROM to TO, inclusive.
1337	This is for the sake of peephole optimization, so assume
1338	that whatever these insns do will still be done by a new
1339	peephole insn that will replace them. */
1340
1341	void
1342	delete_for_peephole (rtx_insn *from, rtx_insn *to)
1343	{
1344	rtx_insn *insn = from;
1345
1346	while (1)
1347	{
1348	rtx_insn *next = NEXT_INSN (insn);
1349	rtx_insn *prev = PREV_INSN (insn);
1350
1351	if (!NOTE_P (insn))
1352	{
1353	insn->set_deleted();
1354
1355	/* Patch this insn out of the chain. */
1356	/* We don't do this all at once, because we
1357	must preserve all NOTEs. */
1358	if (prev)
1359	SET_NEXT_INSN (prev) = next;
1360
1361	if (next)
1362	SET_PREV_INSN (next) = prev;
1363	}
1364
1365	if (insn == to)
1366	break;
1367	insn = next;
1368	}
1369
1370	/* Note that if TO is an unconditional jump
1371	we *do not* delete the BARRIER that follows,
1372	since the peephole that replaces this sequence
1373	is also an unconditional jump in that case. */
1374	}
1375
1376	/* A helper function for redirect_exp_1; examines its input X and returns
1377	either a LABEL_REF around a label, or a RETURN if X was NULL. */
1378	static rtx
1379	redirect_target (rtx x)
1380	{
1381	if (x == NULL_RTX)
1382	return ret_rtx;
1383	if (!ANY_RETURN_P (x))
1384	return gen_rtx_LABEL_REF (Pmode, x);
1385	return x;
1386	}
1387
1388	/* Throughout LOC, redirect OLABEL to NLABEL. Treat null OLABEL or
1389	NLABEL as a return. Accrue modifications into the change group. */
1390
1391	static void
1392	redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx_insn *insn)
1393	{
1394	rtx x = *loc;
1395	RTX_CODE code = GET_CODE (x);
1396	int i;
1397	const char *fmt;
1398
1399	if ((code == LABEL_REF && label_ref_label (ref: x) == olabel)
1400	|| x == olabel)
1401	{
1402	x = redirect_target (x: nlabel);
1403	if (GET_CODE (x) == LABEL_REF && loc == &PATTERN (insn))
1404	x = gen_rtx_SET (pc_rtx, x);
1405	validate_change (insn, loc, x, 1);
1406	return;
1407	}
1408
1409	if (code == SET && SET_DEST (x) == pc_rtx
1410	&& ANY_RETURN_P (nlabel)
1411	&& GET_CODE (SET_SRC (x)) == LABEL_REF
1412	&& label_ref_label (SET_SRC (x)) == olabel)
1413	{
1414	validate_change (insn, loc, nlabel, 1);
1415	return;
1416	}
1417
1418	if (code == IF_THEN_ELSE)
1419	{
1420	/* Skip the condition of an IF_THEN_ELSE. We only want to
1421	change jump destinations, not eventual label comparisons. */
1422	redirect_exp_1 (loc: &XEXP (x, 1), olabel, nlabel, insn);
1423	redirect_exp_1 (loc: &XEXP (x, 2), olabel, nlabel, insn);
1424	return;
1425	}
1426
1427	fmt = GET_RTX_FORMAT (code);
1428	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1429	{
1430	if (fmt[i] == 'e')
1431	redirect_exp_1 (loc: &XEXP (x, i), olabel, nlabel, insn);
1432	else if (fmt[i] == 'E')
1433	{
1434	int j;
1435	for (j = 0; j < XVECLEN (x, i); j++)
1436	redirect_exp_1 (loc: &XVECEXP (x, i, j), olabel, nlabel, insn);
1437	}
1438	}
1439	}
1440
1441	/* Make JUMP go to NLABEL instead of where it jumps now. Accrue
1442	the modifications into the change group. Return false if we did
1443	not see how to do that. */
1444
1445	bool
1446	redirect_jump_1 (rtx_insn *jump, rtx nlabel)
1447	{
1448	int ochanges = num_validated_changes ();
1449	rtx *loc, asmop;
1450
1451	gcc_assert (nlabel != NULL_RTX);
1452	asmop = extract_asm_operands (PATTERN (insn: jump));
1453	if (asmop)
1454	{
1455	if (nlabel == NULL)
1456	return false;
1457	gcc_assert (ASM_OPERANDS_LABEL_LENGTH (asmop) == 1);
1458	loc = &ASM_OPERANDS_LABEL (asmop, 0);
1459	}
1460	else if (GET_CODE (PATTERN (jump)) == PARALLEL)
1461	loc = &XVECEXP (PATTERN (jump), 0, 0);
1462	else
1463	loc = &PATTERN (insn: jump);
1464
1465	redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, insn: jump);
1466	return num_validated_changes () > ochanges;
1467	}
1468
1469	/* Make JUMP go to NLABEL instead of where it jumps now. If the old
1470	jump target label is unused as a result, it and the code following
1471	it may be deleted.
1472
1473	Normally, NLABEL will be a label, but it may also be a RETURN rtx;
1474	in that case we are to turn the jump into a (possibly conditional)
1475	return insn.
1476
1477	The return value will be true if the change was made, false if it wasn't
1478	(this can only occur when trying to produce return insns). */
1479
1480	bool
1481	redirect_jump (rtx_jump_insn *jump, rtx nlabel, int delete_unused)
1482	{
1483	rtx olabel = jump->jump_label ();
1484
1485	if (!nlabel)
1486	{
1487	/* If there is no label, we are asked to redirect to the EXIT block.
1488	When before the epilogue is emitted, return/simple_return cannot be
1489	created so we return false immediately. After the epilogue
1490	is emitted, we always expect a label, either a non-null label, or a
1491	return/simple_return RTX. */
1492
1493	if (!epilogue_completed)
1494	return false;
1495	gcc_unreachable ();
1496	}
1497
1498	if (nlabel == olabel)
1499	return true;
1500
1501	if (! redirect_jump_1 (jump, nlabel) || ! apply_change_group ())
1502	return false;
1503
1504	redirect_jump_2 (jump, olabel, nlabel, delete_unused, 0);
1505	return true;
1506	}
1507
1508	/* Fix up JUMP_LABEL and label ref counts after OLABEL has been replaced with
1509	NLABEL in JUMP.
1510	If DELETE_UNUSED is positive, delete related insn to OLABEL if its ref
1511	count has dropped to zero. */
1512	void
1513	redirect_jump_2 (rtx_jump_insn *jump, rtx olabel, rtx nlabel, int delete_unused,
1514	int invert)
1515	{
1516	rtx note;
1517
1518	gcc_assert (JUMP_LABEL (jump) == olabel);
1519
1520	/* Negative DELETE_UNUSED used to be used to signalize behavior on
1521	moving FUNCTION_END note. Just sanity check that no user still worry
1522	about this. */
1523	gcc_assert (delete_unused >= 0);
1524	JUMP_LABEL (jump) = nlabel;
1525	if (!ANY_RETURN_P (nlabel))
1526	++LABEL_NUSES (nlabel);
1527
1528	/* Update labels in any REG_EQUAL note. */
1529	if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
1530	{
1531	if (ANY_RETURN_P (nlabel)
1532	|| (invert && !invert_exp_1 (XEXP (note, 0), jump)))
1533	remove_note (jump, note);
1534	else
1535	{
1536	redirect_exp_1 (loc: &XEXP (note, 0), olabel, nlabel, insn: jump);
1537	confirm_change_group ();
1538	}
1539	}
1540
1541	/* Handle the case where we had a conditional crossing jump to a return
1542	label and are now changing it into a direct conditional return.
1543	The jump is no longer crossing in that case. */
1544	if (ANY_RETURN_P (nlabel))
1545	CROSSING_JUMP_P (jump) = 0;
1546
1547	if (!ANY_RETURN_P (olabel)
1548	&& --LABEL_NUSES (olabel) == 0 && delete_unused > 0
1549	/* Undefined labels will remain outside the insn stream. */
1550	&& INSN_UID (insn: olabel))
1551	delete_related_insns (uncast_insn: olabel);
1552	if (invert)
1553	invert_br_probabilities (jump);
1554	}
1555
1556	/* Invert the jump condition X contained in jump insn INSN. Accrue the
1557	modifications into the change group. Return true for success. */
1558	static bool
1559	invert_exp_1 (rtx x, rtx_insn *insn)
1560	{
1561	RTX_CODE code = GET_CODE (x);
1562
1563	if (code == IF_THEN_ELSE)
1564	{
1565	rtx comp = XEXP (x, 0);
1566	rtx tem;
1567	enum rtx_code reversed_code;
1568
1569	/* We can do this in two ways: The preferable way, which can only
1570	be done if this is not an integer comparison, is to reverse
1571	the comparison code. Otherwise, swap the THEN-part and ELSE-part
1572	of the IF_THEN_ELSE. If we can't do either, fail. */
1573
1574	reversed_code = reversed_comparison_code (comparison: comp, insn);
1575
1576	if (reversed_code != UNKNOWN)
1577	{
1578	validate_change (insn, &XEXP (x, 0),
1579	gen_rtx_fmt_ee (reversed_code,
1580	GET_MODE (comp), XEXP (comp, 0),
1581	XEXP (comp, 1)),
1582	1);
1583	return true;
1584	}
1585
1586	tem = XEXP (x, 1);
1587	validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
1588	validate_change (insn, &XEXP (x, 2), tem, 1);
1589	return true;
1590	}
1591	else
1592	return false;
1593	}
1594
1595	/* Invert the condition of the jump JUMP, and make it jump to label
1596	NLABEL instead of where it jumps now. Accrue changes into the
1597	change group. Return false if we didn't see how to perform the
1598	inversion and redirection. */
1599
1600	bool
1601	invert_jump_1 (rtx_jump_insn *jump, rtx nlabel)
1602	{
1603	rtx x = pc_set (insn: jump);
1604	int ochanges;
1605	bool ok;
1606
1607	ochanges = num_validated_changes ();
1608	if (x == NULL)
1609	return false;
1610	ok = invert_exp_1 (SET_SRC (x), insn: jump);
1611	gcc_assert (ok);
1612
1613	if (num_validated_changes () == ochanges)
1614	return false;
1615
1616	/* redirect_jump_1 will fail of nlabel == olabel, and the current use is
1617	in Pmode, so checking this is not merely an optimization. */
1618	return nlabel == JUMP_LABEL (jump) || redirect_jump_1 (jump, nlabel);
1619	}
1620
1621	/* Invert the condition of the jump JUMP, and make it jump to label
1622	NLABEL instead of where it jumps now. Return true if successful. */
1623
1624	bool
1625	invert_jump (rtx_jump_insn *jump, rtx nlabel, int delete_unused)
1626	{
1627	rtx olabel = JUMP_LABEL (jump);
1628
1629	if (invert_jump_1 (jump, nlabel) && apply_change_group ())
1630	{
1631	redirect_jump_2 (jump, olabel, nlabel, delete_unused, invert: 1);
1632	return true;
1633	}
1634	cancel_changes (0);
1635	return false;
1636	}
1637
1638
1639	/* Like rtx_equal_p except that it considers two REGs as equal
1640	if they renumber to the same value and considers two commutative
1641	operations to be the same if the order of the operands has been
1642	reversed. */
1643
1644	bool
1645	rtx_renumbered_equal_p (const_rtx x, const_rtx y)
1646	{
1647	int i;
1648	const enum rtx_code code = GET_CODE (x);
1649	const char *fmt;
1650
1651	if (x == y)
1652	return true;
1653
1654	if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
1655	&& (REG_P (y) || (GET_CODE (y) == SUBREG
1656	&& REG_P (SUBREG_REG (y)))))
1657	{
1658	int reg_x = -1, reg_y = -1;
1659	poly_int64 byte_x = 0, byte_y = 0;
1660	struct subreg_info info;
1661
1662	if (GET_MODE (x) != GET_MODE (y))
1663	return false;
1664
1665	/* If we haven't done any renumbering, don't
1666	make any assumptions. */
1667	if (reg_renumber == 0)
1668	return rtx_equal_p (x, y);
1669
1670	if (code == SUBREG)
1671	{
1672	reg_x = REGNO (SUBREG_REG (x));
1673	byte_x = SUBREG_BYTE (x);
1674
1675	if (reg_renumber[reg_x] >= 0)
1676	{
1677	subreg_get_info (reg_renumber[reg_x],
1678	GET_MODE (SUBREG_REG (x)), byte_x,
1679	GET_MODE (x), &info);
1680	if (!info.representable_p)
1681	return false;
1682	reg_x = info.offset;
1683	byte_x = 0;
1684	}
1685	}
1686	else
1687	{
1688	reg_x = REGNO (x);
1689	if (reg_renumber[reg_x] >= 0)
1690	reg_x = reg_renumber[reg_x];
1691	}
1692
1693	if (GET_CODE (y) == SUBREG)
1694	{
1695	reg_y = REGNO (SUBREG_REG (y));
1696	byte_y = SUBREG_BYTE (y);
1697
1698	if (reg_renumber[reg_y] >= 0)
1699	{
1700	subreg_get_info (reg_renumber[reg_y],
1701	GET_MODE (SUBREG_REG (y)), byte_y,
1702	GET_MODE (y), &info);
1703	if (!info.representable_p)
1704	return false;
1705	reg_y = info.offset;
1706	byte_y = 0;
1707	}
1708	}
1709	else
1710	{
1711	reg_y = REGNO (y);
1712	if (reg_renumber[reg_y] >= 0)
1713	reg_y = reg_renumber[reg_y];
1714	}
1715
1716	return reg_x >= 0 && reg_x == reg_y && known_eq (byte_x, byte_y);
1717	}
1718
1719	/* Now we have disposed of all the cases
1720	in which different rtx codes can match. */
1721	if (code != GET_CODE (y))
1722	return false;
1723
1724	switch (code)
1725	{
1726	case PC:
1727	case ADDR_VEC:
1728	case ADDR_DIFF_VEC:
1729	CASE_CONST_UNIQUE:
1730	return false;
1731
1732	case CONST_VECTOR:
1733	if (!same_vector_encodings_p (x, y))
1734	return false;
1735	break;
1736
1737	case LABEL_REF:
1738	/* We can't assume nonlocal labels have their following insns yet. */
1739	if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
1740	return label_ref_label (ref: x) == label_ref_label (ref: y);
1741
1742	/* Two label-refs are equivalent if they point at labels
1743	in the same position in the instruction stream. */
1744	else
1745	{
1746	rtx_insn *xi = next_nonnote_nondebug_insn (label_ref_label (ref: x));
1747	rtx_insn *yi = next_nonnote_nondebug_insn (label_ref_label (ref: y));
1748	while (xi && LABEL_P (xi))
1749	xi = next_nonnote_nondebug_insn (xi);
1750	while (yi && LABEL_P (yi))
1751	yi = next_nonnote_nondebug_insn (yi);
1752	return xi == yi;
1753	}
1754
1755	case SYMBOL_REF:
1756	return XSTR (x, 0) == XSTR (y, 0);
1757
1758	case CODE_LABEL:
1759	/* If we didn't match EQ equality above, they aren't the same. */
1760	return false;
1761
1762	default:
1763	break;
1764	}
1765
1766	/* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1767
1768	if (GET_MODE (x) != GET_MODE (y))
1769	return false;
1770
1771	/* MEMs referring to different address space are not equivalent. */
1772	if (code == MEM && MEM_ADDR_SPACE (x) != MEM_ADDR_SPACE (y))
1773	return false;
1774
1775	/* For commutative operations, the RTX match if the operand match in any
1776	order. Also handle the simple binary and unary cases without a loop. */
1777	if (targetm.commutative_p (x, UNKNOWN))
1778	return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1779	&& rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
1780	|| (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
1781	&& rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
1782	else if (NON_COMMUTATIVE_P (x))
1783	return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1784	&& rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
1785	else if (UNARY_P (x))
1786	return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
1787
1788	/* Compare the elements. If any pair of corresponding elements
1789	fail to match, return false for the whole things. */
1790
1791	fmt = GET_RTX_FORMAT (code);
1792	for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1793	{
1794	int j;
1795	switch (fmt[i])
1796	{
1797	case 'w':
1798	if (XWINT (x, i) != XWINT (y, i))
1799	return false;
1800	break;
1801
1802	case 'i':
1803	if (XINT (x, i) != XINT (y, i))
1804	{
1805	if (((code == ASM_OPERANDS && i == 6)
1806	|| (code == ASM_INPUT && i == 1)))
1807	break;
1808	return false;
1809	}
1810	break;
1811
1812	case 'p':
1813	if (maybe_ne (SUBREG_BYTE (x), SUBREG_BYTE (y)))
1814	return false;
1815	break;
1816
1817	case 't':
1818	if (XTREE (x, i) != XTREE (y, i))
1819	return false;
1820	break;
1821
1822	case 's':
1823	if (strcmp (XSTR (x, i), XSTR (y, i)))
1824	return false;
1825	break;
1826
1827	case 'e':
1828	if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1829	return false;
1830	break;
1831
1832	case 'u':
1833	if (XEXP (x, i) != XEXP (y, i))
1834	return false;
1835	/* Fall through. */
1836	case '0':
1837	break;
1838
1839	case 'E':
1840	if (XVECLEN (x, i) != XVECLEN (y, i))
1841	return false;
1842	for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1843	if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1844	return false;
1845	break;
1846
1847	default:
1848	gcc_unreachable ();
1849	}
1850	}
1851	return true;
1852	}
1853
1854	/* If X is a hard register or equivalent to one or a subregister of one,
1855	return the hard register number. If X is a pseudo register that was not
1856	assigned a hard register, return the pseudo register number. Otherwise,
1857	return -1. Any rtx is valid for X. */
1858
1859	int
1860	true_regnum (const_rtx x)
1861	{
1862	if (REG_P (x))
1863	{
1864	if (REGNO (x) >= FIRST_PSEUDO_REGISTER
1865	&& (lra_in_progress || reg_renumber[REGNO (x)] >= 0))
1866	return reg_renumber[REGNO (x)];
1867	return REGNO (x);
1868	}
1869	if (GET_CODE (x) == SUBREG)
1870	{
1871	int base = true_regnum (SUBREG_REG (x));
1872	if (base >= 0
1873	&& base < FIRST_PSEUDO_REGISTER)
1874	{
1875	struct subreg_info info;
1876
1877	subreg_get_info (lra_in_progress
1878	? (unsigned) base : REGNO (SUBREG_REG (x)),
1879	GET_MODE (SUBREG_REG (x)),
1880	SUBREG_BYTE (x), GET_MODE (x), &info);
1881
1882	if (info.representable_p)
1883	return base + info.offset;
1884	}
1885	}
1886	return -1;
1887	}
1888
1889	/* Return regno of the register REG and handle subregs too. */
1890	unsigned int
1891	reg_or_subregno (const_rtx reg)
1892	{
1893	if (GET_CODE (reg) == SUBREG)
1894	reg = SUBREG_REG (reg);
1895	gcc_assert (REG_P (reg));
1896	return REGNO (reg);
1897	}
1898