1	/* Generate code from machine description to recognize rtl as insns.
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
7	under the terms of the GNU General Public License as published by
8	the Free Software Foundation; either version 3, or (at your option)
9	any later version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT
12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13	or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14	License 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
21	/* This program is used to produce insn-recog.cc, which contains a
22	function called `recog' plus its subroutines. These functions
23	contain a decision tree that recognizes whether an rtx, the
24	argument given to recog, is a valid instruction.
25
26	recog returns -1 if the rtx is not valid. If the rtx is valid,
27	recog returns a nonnegative number which is the insn code number
28	for the pattern that matched. This is the same as the order in the
29	machine description of the entry that matched. This number can be
30	used as an index into various insn_* tables, such as insn_template,
31	insn_outfun, and insn_n_operands (found in insn-output.cc).
32
33	The third argument to recog is an optional pointer to an int. If
34	present, recog will accept a pattern if it matches except for
35	missing CLOBBER expressions at the end. In that case, the value
36	pointed to by the optional pointer will be set to the number of
37	CLOBBERs that need to be added (it should be initialized to zero by
38	the caller). If it is set nonzero, the caller should allocate a
39	PARALLEL of the appropriate size, copy the initial entries, and
40	call add_clobbers (found in insn-emit.cc) to fill in the CLOBBERs.
41
42	This program also generates the function `split_insns', which
43	returns 0 if the rtl could not be split, or it returns the split
44	rtl as an INSN list.
45
46	This program also generates the function `peephole2_insns', which
47	returns 0 if the rtl could not be matched. If there was a match,
48	the new rtl is returned in an INSN list, and LAST_INSN will point
49	to the last recognized insn in the old sequence.
50
51
52	At a high level, the algorithm used in this file is as follows:
53
54	1. Build up a decision tree for each routine, using the following
55	approach to matching an rtx:
56
57	- First determine the "shape" of the rtx, based on GET_CODE,
58	XVECLEN and XINT. This phase examines SET_SRCs before SET_DESTs
59	since SET_SRCs tend to be more distinctive. It examines other
60	operands in numerical order, since the canonicalization rules
61	prefer putting complex operands of commutative operators first.
62
63	- Next check modes and predicates. This phase examines all
64	operands in numerical order, even for SETs, since the mode of a
65	SET_DEST is exact while the mode of a SET_SRC can be VOIDmode
66	for constant integers.
67
68	- Next check match_dups.
69
70	- Finally check the C condition and (where appropriate) pnum_clobbers.
71
72	2. Try to optimize the tree by removing redundant tests, CSEing tests,
73	folding tests together, etc.
74
75	3. Look for common subtrees and split them out into "pattern" routines.
76	These common subtrees can be identical or they can differ in mode,
77	code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code).
78	In the latter case the users of the pattern routine pass the
79	appropriate mode, etc., as argument. For example, if two patterns
80	contain:
81
82	(plus:SI (match_operand:SI 1 "register_operand")
83	(match_operand:SI 2 "register_operand"))
84
85	we can split the associated matching code out into a subroutine.
86	If a pattern contains:
87
88	(minus:DI (match_operand:DI 1 "register_operand")
89	(match_operand:DI 2 "register_operand"))
90
91	then we can consider using the same matching routine for both
92	the plus and minus expressions, passing PLUS and SImode in the
93	former case and MINUS and DImode in the latter case.
94
95	The main aim of this phase is to reduce the compile time of the
96	insn-recog.cc code and to reduce the amount of object code in
97	insn-recog.o.
98
99	4. Split the matching trees into functions, trying to limit the
100	size of each function to a sensible amount.
101
102	Again, the main aim of this phase is to reduce the compile time
103	of insn-recog.cc. (It doesn't help with the size of insn-recog.o.)
104
105	5. Write out C++ code for each function. */
106
107	#include "bconfig.h"
108	#define INCLUDE_ALGORITHM
109	#include "system.h"
110	#include "coretypes.h"
111	#include "tm.h"
112	#include "rtl.h"
113	#include "errors.h"
114	#include "read-md.h"
115	#include "gensupport.h"
116
117	#undef GENERATOR_FILE
118	enum true_rtx_doe {
119	#define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM,
120	#include "rtl.def"
121	#undef DEF_RTL_EXPR
122	FIRST_GENERATOR_RTX_CODE
123	};
124	#define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE)
125	#define GENERATOR_FILE 1
126
127	/* Debugging variables to control which optimizations are performed.
128	Note that disabling merge_states_p leads to very large output. */
129	static const bool merge_states_p = true;
130	static const bool collapse_optional_decisions_p = true;
131	static const bool cse_tests_p = true;
132	static const bool simplify_tests_p = true;
133	static const bool use_operand_variables_p = true;
134	static const bool use_subroutines_p = true;
135	static const bool use_pattern_routines_p = true;
136
137	/* Whether to add comments for optional tests that we decided to keep.
138	Can be useful when debugging the generator itself but is noise when
139	debugging the generated code. */
140	static const bool mark_optional_transitions_p = false;
141
142	/* Whether pattern routines should calculate positions relative to their
143	rtx parameter rather than use absolute positions. This e.g. allows
144	a pattern routine to be shared between a plain SET and a PARALLEL
145	that includes a SET.
146
147	In principle it sounds like this should be useful, especially for
148	recog_for_combine, where the plain SET form is generated automatically
149	from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't
150	seem to help much and leads to slightly bigger object files. */
151	static const bool relative_patterns_p = false;
152
153	/* Whether pattern routines should be allowed to test whether pnum_clobbers
154	is null. This requires passing pnum_clobbers around as a parameter. */
155	static const bool pattern_have_num_clobbers_p = true;
156
157	/* Whether pattern routines should be allowed to test .md file C conditions.
158	This requires passing insn around as a parameter, in case the C
159	condition refers to it. In practice this tends to lead to bigger
160	object files. */
161	static const bool pattern_c_test_p = false;
162
163	/* Whether to require each parameter passed to a pattern routine to be
164	unique. Disabling this check for example allows unary operators with
165	matching modes (like NEG) and unary operators with mismatched modes
166	(like ZERO_EXTEND) to be matched by a single pattern. However, we then
167	often have cases where the same value is passed too many times. */
168	static const bool force_unique_params_p = true;
169
170	/* The maximum (approximate) depth of block nesting that an individual
171	routine or subroutine should have. This limit is about keeping the
172	output readable rather than reducing compile time. */
173	static const unsigned int MAX_DEPTH = 6;
174
175	/* The minimum number of pseudo-statements that a state must have before
176	we split it out into a subroutine. */
177	static const unsigned int MIN_NUM_STATEMENTS = 5;
178
179	/* The number of pseudo-statements a state can have before we consider
180	splitting out substates into subroutines. This limit is about avoiding
181	compile-time problems with very big functions (and also about keeping
182	functions within --param optimization limits, etc.). */
183	static const unsigned int MAX_NUM_STATEMENTS = 200;
184
185	/* The minimum number of pseudo-statements that can be used in a pattern
186	routine. */
187	static const unsigned int MIN_COMBINE_COST = 4;
188
189	/* The maximum number of arguments that a pattern routine can have.
190	The idea is to prevent one pattern getting a ridiculous number of
191	arguments when it would be more beneficial to have a separate pattern
192	routine instead. */
193	static const unsigned int MAX_PATTERN_PARAMS = 5;
194
195	/* The maximum operand number plus one. */
196	int num_operands;
197
198	/* Ways of obtaining an rtx to be tested. */
199	enum position_type {
200	/* PATTERN (peep2_next_insn (ARG)). */
201	POS_PEEP2_INSN,
202
203	/* XEXP (BASE, ARG). */
204	POS_XEXP,
205
206	/* XVECEXP (BASE, 0, ARG). */
207	POS_XVECEXP0
208	};
209
210	/* The position of an rtx relative to X0. Each useful position is
211	represented by exactly one instance of this structure. */
212	struct position
213	{
214	/* The parent rtx. This is the root position for POS_PEEP2_INSNs. */
215	struct position *base;
216
217	/* A position with the same BASE and TYPE, but with the next value
218	of ARG. */
219	struct position *next;
220
221	/* A list of all POS_XEXP positions that use this one as their base,
222	chained by NEXT fields. The first entry represents XEXP (this, 0),
223	the second represents XEXP (this, 1), and so on. */
224	struct position *xexps;
225
226	/* A list of POS_XVECEXP0 positions that use this one as their base,
227	chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0),
228	the second represents XVECEXP (this, 0, 1), and so on. */
229	struct position *xvecexp0s;
230
231	/* The type of position. */
232	enum position_type type;
233
234	/* The argument to TYPE (shown as ARG in the position_type comments). */
235	int arg;
236
237	/* The instruction to which the position belongs. */
238	unsigned int insn_id;
239
240	/* The depth of this position relative to the instruction pattern.
241	E.g. if the instruction pattern is a SET, the SET itself has a
242	depth of 0 while the SET_DEST and SET_SRC have depths of 1. */
243	unsigned int depth;
244
245	/* A unique identifier for this position. */
246	unsigned int id;
247	};
248
249	enum routine_type {
250	SUBPATTERN, RECOG, SPLIT, PEEPHOLE2
251	};
252
253	/* The root position (x0). */
254	static struct position root_pos;
255
256	/* The number of positions created. Also one higher than the maximum
257	position id. */
258	static unsigned int num_positions = 1;
259
260	/* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position,
261	since we are given that instruction's pattern as x0. */
262	static struct position *peep2_insn_pos_list = &root_pos;
263
264	/* Return a position with the given BASE, TYPE and ARG. NEXT_PTR
265	points to where the unique object that represents the position
266	should be stored. Create the object if it doesn't already exist,
267	otherwise reuse the object that is already there. */
268
269	static struct position *
270	next_position (struct position **next_ptr, struct position *base,
271	enum position_type type, int arg)
272	{
273	struct position *pos;
274
275	pos = *next_ptr;
276	if (!pos)
277	{
278	pos = XCNEW (struct position);
279	pos->type = type;
280	pos->arg = arg;
281	if (type == POS_PEEP2_INSN)
282	{
283	pos->base = 0;
284	pos->insn_id = arg;
285	pos->depth = base->depth;
286	}
287	else
288	{
289	pos->base = base;
290	pos->insn_id = base->insn_id;
291	pos->depth = base->depth + 1;
292	}
293	pos->id = num_positions++;
294	*next_ptr = pos;
295	}
296	return pos;
297	}
298
299	/* Compare positions POS1 and POS2 lexicographically. */
300
301	static int
302	compare_positions (struct position *pos1, struct position *pos2)
303	{
304	int diff;
305
306	diff = pos1->depth - pos2->depth;
307	if (diff < 0)
308	do
309	pos2 = pos2->base;
310	while (pos1->depth != pos2->depth);
311	else if (diff > 0)
312	do
313	pos1 = pos1->base;
314	while (pos1->depth != pos2->depth);
315	while (pos1 != pos2)
316	{
317	diff = (int) pos1->type - (int) pos2->type;
318	if (diff == 0)
319	diff = pos1->arg - pos2->arg;
320	pos1 = pos1->base;
321	pos2 = pos2->base;
322	}
323	return diff;
324	}
325
326	/* Return the most deeply-nested position that is common to both
327	POS1 and POS2. If the positions are from different instructions,
328	return the one with the lowest insn_id. */
329
330	static struct position *
331	common_position (struct position *pos1, struct position *pos2)
332	{
333	if (pos1->insn_id != pos2->insn_id)
334	return pos1->insn_id < pos2->insn_id ? pos1 : pos2;
335	if (pos1->depth > pos2->depth)
336	std::swap (a&: pos1, b&: pos2);
337	while (pos1->depth != pos2->depth)
338	pos2 = pos2->base;
339	while (pos1 != pos2)
340	{
341	pos1 = pos1->base;
342	pos2 = pos2->base;
343	}
344	return pos1;
345	}
346
347	/* Search for and return operand N, stop when reaching node STOP. */
348
349	static rtx
350	find_operand (rtx pattern, int n, rtx stop)
351	{
352	const char *fmt;
353	RTX_CODE code;
354	int i, j, len;
355	rtx r;
356
357	if (pattern == stop)
358	return stop;
359
360	code = GET_CODE (pattern);
361	if ((code == MATCH_SCRATCH
362	|| code == MATCH_OPERAND
363	|| code == MATCH_OPERATOR
364	|| code == MATCH_PARALLEL)
365	&& XINT (pattern, 0) == n)
366	return pattern;
367
368	fmt = GET_RTX_FORMAT (code);
369	len = GET_RTX_LENGTH (code);
370	for (i = 0; i < len; i++)
371	{
372	switch (fmt[i])
373	{
374	case 'e': case 'u':
375	if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX)
376	return r;
377	break;
378
379	case 'V':
380	if (! XVEC (pattern, i))
381	break;
382	/* Fall through. */
383
384	case 'E':
385	for (j = 0; j < XVECLEN (pattern, i); j++)
386	if ((r = find_operand (XVECEXP (pattern, i, j), n, stop))
387	!= NULL_RTX)
388	return r;
389	break;
390
391	case 'r': case 'p': case 'i': case 'w': case '0': case 's':
392	break;
393
394	default:
395	gcc_unreachable ();
396	}
397	}
398
399	return NULL;
400	}
401
402	/* Search for and return operand M, such that it has a matching
403	constraint for operand N. */
404
405	static rtx
406	find_matching_operand (rtx pattern, int n)
407	{
408	const char *fmt;
409	RTX_CODE code;
410	int i, j, len;
411	rtx r;
412
413	code = GET_CODE (pattern);
414	if (code == MATCH_OPERAND
415	&& (XSTR (pattern, 2)[0] == '0' + n
416	|| (XSTR (pattern, 2)[0] == '%'
417	&& XSTR (pattern, 2)[1] == '0' + n)))
418	return pattern;
419
420	fmt = GET_RTX_FORMAT (code);
421	len = GET_RTX_LENGTH (code);
422	for (i = 0; i < len; i++)
423	{
424	switch (fmt[i])
425	{
426	case 'e': case 'u':
427	if ((r = find_matching_operand (XEXP (pattern, i), n)))
428	return r;
429	break;
430
431	case 'V':
432	if (! XVEC (pattern, i))
433	break;
434	/* Fall through. */
435
436	case 'E':
437	for (j = 0; j < XVECLEN (pattern, i); j++)
438	if ((r = find_matching_operand (XVECEXP (pattern, i, j), n)))
439	return r;
440	break;
441
442	case 'r': case 'p': case 'i': case 'w': case '0': case 's':
443	break;
444
445	default:
446	gcc_unreachable ();
447	}
448	}
449
450	return NULL;
451	}
452
453	/* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we
454	don't use the MATCH_OPERAND constraint, only the predicate.
455	This is confusing to folks doing new ports, so help them
456	not make the mistake. */
457
458	static bool
459	constraints_supported_in_insn_p (rtx insn)
460	{
461	return !(GET_CODE (insn) == DEFINE_EXPAND
462	|| GET_CODE (insn) == DEFINE_SPLIT
463	|| GET_CODE (insn) == DEFINE_PEEPHOLE2);
464	}
465
466	/* Return the name of the predicate matched by MATCH_RTX. */
467
468	static const char *
469	predicate_name (rtx match_rtx)
470	{
471	if (GET_CODE (match_rtx) == MATCH_SCRATCH)
472	return "scratch_operand";
473	else
474	return XSTR (match_rtx, 1);
475	}
476
477	/* Return true if OPERAND is a MATCH_OPERAND using a special predicate
478	function. */
479
480	static bool
481	special_predicate_operand_p (rtx operand)
482	{
483	if (GET_CODE (operand) == MATCH_OPERAND)
484	{
485	const char *pred_name = predicate_name (match_rtx: operand);
486	if (pred_name[0] != 0)
487	{
488	const struct pred_data *pred;
489
490	pred = lookup_predicate (pred_name);
491	return pred != NULL && pred->special;
492	}
493	}
494
495	return false;
496	}
497
498	/* Check for various errors in PATTERN, which is part of INFO.
499	SET is nonnull for a destination, and is the complete set pattern.
500	SET_CODE is '=' for normal sets, and '+' within a context that
501	requires in-out constraints. */
502
503	static void
504	validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code)
505	{
506	const char *fmt;
507	RTX_CODE code;
508	size_t i, len;
509	int j;
510
511	code = GET_CODE (pattern);
512	switch (code)
513	{
514	case MATCH_SCRATCH:
515	{
516	const char constraints0 = XSTR (pattern, 1)[0];
517
518	if (!constraints_supported_in_insn_p (insn: info->def))
519	{
520	if (constraints0)
521	{
522	error_at (info->loc, "constraints not supported in %s",
523	GET_RTX_NAME (GET_CODE (info->def)));
524	}
525	return;
526	}
527
528	/* If a MATCH_SCRATCH is used in a context requiring an write-only
529	or read/write register, validate that. */
530	if (set_code == '='
531	&& constraints0
532	&& constraints0 != '='
533	&& constraints0 != '+')
534	{
535	error_at (info->loc, "operand %d missing output reload",
536	XINT (pattern, 0));
537	}
538	return;
539	}
540	case MATCH_DUP:
541	case MATCH_OP_DUP:
542	case MATCH_PAR_DUP:
543	if (find_operand (pattern: info->def, XINT (pattern, 0), stop: pattern) == pattern)
544	error_at (info->loc, "operand %i duplicated before defined",
545	XINT (pattern, 0));
546	break;
547	case MATCH_OPERAND:
548	case MATCH_OPERATOR:
549	{
550	const char *pred_name = XSTR (pattern, 1);
551	const struct pred_data *pred;
552	const char *c_test;
553
554	c_test = get_c_test (info->def);
555
556	if (pred_name[0] != 0)
557	{
558	pred = lookup_predicate (pred_name);
559	if (!pred)
560	error_at (info->loc, "unknown predicate '%s'", pred_name);
561	}
562	else
563	pred = 0;
564
565	if (code == MATCH_OPERAND)
566	{
567	const char *constraints = XSTR (pattern, 2);
568	const char constraints0 = constraints[0];
569
570	if (!constraints_supported_in_insn_p (insn: info->def))
571	{
572	if (constraints0)
573	{
574	error_at (info->loc, "constraints not supported in %s",
575	GET_RTX_NAME (GET_CODE (info->def)));
576	}
577	}
578
579	/* A MATCH_OPERAND that is a SET should have an output reload. */
580	else if (set && constraints0)
581	{
582	if (set_code == '+')
583	{
584	if (constraints0 == '+')
585	;
586	/* If we've only got an output reload for this operand,
587	we'd better have a matching input operand. */
588	else if (constraints0 == '='
589	&& find_matching_operand (pattern: info->def,
590	XINT (pattern, 0)))
591	;
592	else
593	error_at (info->loc, "operand %d missing in-out reload",
594	XINT (pattern, 0));
595	}
596	else if (constraints0 != '=' && constraints0 != '+')
597	error_at (info->loc, "operand %d missing output reload",
598	XINT (pattern, 0));
599	}
600
601	/* For matching constraint in MATCH_OPERAND, the digit must be a
602	smaller number than the number of the operand that uses it in the
603	constraint. */
604	while (1)
605	{
606	while (constraints[0]
607	&& (constraints[0] == ' ' || constraints[0] == ','))
608	constraints++;
609	if (!constraints[0])
610	break;
611
612	if (constraints[0] >= '0' && constraints[0] <= '9')
613	{
614	int val;
615
616	sscanf (s: constraints, format: "%d", &val);
617	if (val >= XINT (pattern, 0))
618	error_at (info->loc, "constraint digit %d is not"
619	" smaller than operand %d",
620	val, XINT (pattern, 0));
621	}
622
623	while (constraints[0] && constraints[0] != ',')
624	constraints++;
625	}
626	}
627
628	/* Allowing non-lvalues in destinations -- particularly CONST_INT --
629	while not likely to occur at runtime, results in less efficient
630	code from insn-recog.cc. */
631	if (set && pred && pred->allows_non_lvalue)
632	error_at (info->loc, "destination operand %d allows non-lvalue",
633	XINT (pattern, 0));
634
635	/* A modeless MATCH_OPERAND can be handy when we can check for
636	multiple modes in the c_test. In most other cases, it is a
637	mistake. Only DEFINE_INSN is eligible, since SPLIT and
638	PEEP2 can FAIL within the output pattern. Exclude special
639	predicates, which check the mode themselves. Also exclude
640	predicates that allow only constants. Exclude the SET_DEST
641	of a call instruction, as that is a common idiom. */
642
643	if (GET_MODE (pattern) == VOIDmode
644	&& code == MATCH_OPERAND
645	&& GET_CODE (info->def) == DEFINE_INSN
646	&& pred
647	&& !pred->special
648	&& pred->allows_non_const
649	&& strstr (haystack: c_test, needle: "operands") == NULL
650	&& ! (set
651	&& GET_CODE (set) == SET
652	&& GET_CODE (SET_SRC (set)) == CALL))
653	message_at (info->loc, "warning: operand %d missing mode?",
654	XINT (pattern, 0));
655	return;
656	}
657
658	case SET:
659	{
660	machine_mode dmode, smode;
661	rtx dest, src;
662
663	dest = SET_DEST (pattern);
664	src = SET_SRC (pattern);
665
666	/* STRICT_LOW_PART is a wrapper. Its argument is the real
667	destination, and it's mode should match the source. */
668	if (GET_CODE (dest) == STRICT_LOW_PART)
669	dest = XEXP (dest, 0);
670
671	/* Find the referent for a DUP. */
672
673	if (GET_CODE (dest) == MATCH_DUP
674	|| GET_CODE (dest) == MATCH_OP_DUP
675	|| GET_CODE (dest) == MATCH_PAR_DUP)
676	dest = find_operand (pattern: info->def, XINT (dest, 0), NULL);
677
678	if (GET_CODE (src) == MATCH_DUP
679	|| GET_CODE (src) == MATCH_OP_DUP
680	|| GET_CODE (src) == MATCH_PAR_DUP)
681	src = find_operand (pattern: info->def, XINT (src, 0), NULL);
682
683	dmode = GET_MODE (dest);
684	smode = GET_MODE (src);
685
686	/* Mode checking is not performed for special predicates. */
687	if (special_predicate_operand_p (operand: src)
688	|| special_predicate_operand_p (operand: dest))
689	;
690
691	/* The operands of a SET must have the same mode unless one
692	is VOIDmode. */
693	else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode)
694	error_at (info->loc, "mode mismatch in set: %smode vs %smode",
695	GET_MODE_NAME (dmode), GET_MODE_NAME (smode));
696
697	/* If only one of the operands is VOIDmode, and PC is not involved,
698	it's probably a mistake. */
699	else if (dmode != smode
700	&& GET_CODE (dest) != PC
701	&& GET_CODE (src) != PC
702	&& !CONST_INT_P (src)
703	&& !CONST_WIDE_INT_P (src)
704	&& GET_CODE (src) != CALL)
705	{
706	const char *which;
707	which = (dmode == VOIDmode ? "destination" : "source");
708	message_at (info->loc, "warning: %s missing a mode?", which);
709	}
710
711	if (dest != SET_DEST (pattern))
712	validate_pattern (pattern: dest, info, set: pattern, set_code: '=');
713	validate_pattern (SET_DEST (pattern), info, set: pattern, set_code: '=');
714	validate_pattern (SET_SRC (pattern), info, NULL_RTX, set_code: 0);
715	return;
716	}
717
718	case CLOBBER:
719	validate_pattern (SET_DEST (pattern), info, set: pattern, set_code: '=');
720	return;
721
722	case ZERO_EXTRACT:
723	validate_pattern (XEXP (pattern, 0), info, set, set_code: set ? '+' : 0);
724	validate_pattern (XEXP (pattern, 1), info, NULL_RTX, set_code: 0);
725	validate_pattern (XEXP (pattern, 2), info, NULL_RTX, set_code: 0);
726	return;
727
728	case STRICT_LOW_PART:
729	validate_pattern (XEXP (pattern, 0), info, set, set_code: set ? '+' : 0);
730	return;
731
732	case LABEL_REF:
733	if (GET_MODE (XEXP (pattern, 0)) != VOIDmode)
734	error_at (info->loc, "operand to label_ref %smode not VOIDmode",
735	GET_MODE_NAME (GET_MODE (XEXP (pattern, 0))));
736	break;
737
738	case VEC_SELECT:
739	if (GET_MODE (pattern) != VOIDmode)
740	{
741	machine_mode mode = GET_MODE (pattern);
742	machine_mode imode = GET_MODE (XEXP (pattern, 0));
743	machine_mode emode
744	= VECTOR_MODE_P (mode) ? GET_MODE_INNER (mode) : mode;
745	if (GET_CODE (XEXP (pattern, 1)) == PARALLEL)
746	{
747	int expected = 1;
748	unsigned int nelems;
749	if (VECTOR_MODE_P (mode)
750	&& !GET_MODE_NUNITS (mode).is_constant (const_value: &expected))
751	error_at (info->loc,
752	"vec_select with variable-sized mode %s",
753	GET_MODE_NAME (mode));
754	else if (XVECLEN (XEXP (pattern, 1), 0) != expected)
755	error_at (info->loc,
756	"vec_select parallel with %d elements, expected %d",
757	XVECLEN (XEXP (pattern, 1), 0), expected);
758	else if (VECTOR_MODE_P (imode)
759	&& GET_MODE_NUNITS (mode: imode).is_constant (const_value: &nelems))
760	{
761	int i;
762	for (i = 0; i < expected; ++i)
763	if (CONST_INT_P (XVECEXP (XEXP (pattern, 1), 0, i))
764	&& (UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i))
765	>= nelems))
766	error_at (info->loc,
767	"out of bounds selector %u in vec_select, "
768	"expected at most %u",
769	(unsigned)
770	UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)),
771	nelems - 1);
772	}
773	}
774	if (imode != VOIDmode && !VECTOR_MODE_P (imode))
775	error_at (info->loc, "%smode of first vec_select operand is not a "
776	"vector mode", GET_MODE_NAME (imode));
777	else if (imode != VOIDmode && GET_MODE_INNER (imode) != emode)
778	error_at (info->loc, "element mode mismatch between vec_select "
779	"%smode and its operand %smode",
780	GET_MODE_NAME (emode),
781	GET_MODE_NAME (GET_MODE_INNER (imode)));
782	}
783	break;
784
785	default:
786	break;
787	}
788
789	fmt = GET_RTX_FORMAT (code);
790	len = GET_RTX_LENGTH (code);
791	for (i = 0; i < len; i++)
792	{
793	switch (fmt[i])
794	{
795	case 'e': case 'u':
796	validate_pattern (XEXP (pattern, i), info, NULL_RTX, set_code: 0);
797	break;
798
799	case 'E':
800	for (j = 0; j < XVECLEN (pattern, i); j++)
801	validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, set_code: 0);
802	break;
803
804	case 'r': case 'p': case 'i': case 'w': case '0': case 's':
805	break;
806
807	default:
808	gcc_unreachable ();
809	}
810	}
811	}
812
813	/* Simple list structure for items of type T, for use when being part
814	of a list is an inherent property of T. T must have members equivalent
815	to "T *prev, *next;" and a function "void set_parent (list_head <T> *)"
816	to set the parent list. */
817	template <typename T>
818	class list_head
819	{
820	public:
821	/* A range of linked items. */
822	class range
823	{
824	public:
825	range (T *);
826	range (T *, T *);
827
828	T *start, *end;
829	void set_parent (list_head *);
830	};
831
832	list_head ();
833	range release ();
834	void push_back (range);
835	range remove (range);
836	void replace (range, range);
837	T *singleton () const;
838
839	T *first, *last;
840	};
841
842	/* Create a range [START_IN, START_IN]. */
843
844	template <typename T>
845	list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {}
846
847	/* Create a range [START_IN, END_IN], linked by next and prev fields. */
848
849	template <typename T>
850	list_head <T>::range::range (T *start_in, T *end_in)
851	: start (start_in), end (end_in) {}
852
853	template <typename T>
854	void
855	list_head <T>::range::set_parent (list_head <T> *owner)
856	{
857	for (T *item = start; item != end; item = item->next)
858	item->set_parent (owner);
859	end->set_parent (owner);
860	}
861
862	template <typename T>
863	list_head <T>::list_head () : first (0), last (0) {}
864
865	/* Add R to the end of the list. */
866
867	template <typename T>
868	void
869	list_head <T>::push_back (range r)
870	{
871	if (last)
872	last->next = r.start;
873	else
874	first = r.start;
875	r.start->prev = last;
876	last = r.end;
877	r.set_parent (this);
878	}
879
880	/* Remove R from the list. R remains valid and can be inserted into
881	other lists. */
882
883	template <typename T>
884	typename list_head <T>::range
885	list_head <T>::remove (range r)
886	{
887	if (r.start->prev)
888	r.start->prev->next = r.end->next;
889	else
890	first = r.end->next;
891	if (r.end->next)
892	r.end->next->prev = r.start->prev;
893	else
894	last = r.start->prev;
895	r.start->prev = 0;
896	r.end->next = 0;
897	r.set_parent (0);
898	return r;
899	}
900
901	/* Replace OLDR with NEWR. OLDR remains valid and can be inserted into
902	other lists. */
903
904	template <typename T>
905	void
906	list_head <T>::replace (range oldr, range newr)
907	{
908	newr.start->prev = oldr.start->prev;
909	newr.end->next = oldr.end->next;
910
911	oldr.start->prev = 0;
912	oldr.end->next = 0;
913	oldr.set_parent (0);
914
915	if (newr.start->prev)
916	newr.start->prev->next = newr.start;
917	else
918	first = newr.start;
919	if (newr.end->next)
920	newr.end->next->prev = newr.end;
921	else
922	last = newr.end;
923	newr.set_parent (this);
924	}
925
926	/* Empty the list and return the previous contents as a range that can
927	be inserted into other lists. */
928
929	template <typename T>
930	typename list_head <T>::range
931	list_head <T>::release ()
932	{
933	range r (first, last);
934	first = 0;
935	last = 0;
936	r.set_parent (0);
937	return r;
938	}
939
940	/* If the list contains a single item, return that item, otherwise return
941	null. */
942
943	template <typename T>
944	T *
945	list_head <T>::singleton () const
946	{
947	return first == last ? first : 0;
948	}
949
950	class state;
951
952	/* Describes a possible successful return from a routine. */
953	struct acceptance_type
954	{
955	/* The type of routine we're returning from. */
956	routine_type type : 16;
957
958	/* True if this structure only really represents a partial match,
959	and if we must call a subroutine of type TYPE to complete the match.
960	In this case we'll call the subroutine and, if it succeeds, return
961	whatever the subroutine returned.
962
963	False if this structure presents a full match. */
964	unsigned int partial_p : 1;
965
966	union
967	{
968	/* If PARTIAL_P, this is the number of the subroutine to call. */
969	int subroutine_id;
970
971	/* Valid if !PARTIAL_P. */
972	struct
973	{
974	/* The identifier of the matching pattern. For SUBPATTERNs this
975	value belongs to an ad-hoc routine-specific enum. For the
976	others it's the number of an .md file pattern. */
977	int code;
978	union
979	{
980	/* For RECOG, the number of clobbers that must be added to the
981	pattern in order for it to match CODE. */
982	int num_clobbers;
983
984	/* For PEEPHOLE2, the number of additional instructions that were
985	included in the optimization. */
986	int match_len;
987	} u;
988	} full;
989	} u;
990	};
991
992	bool
993	operator == (const acceptance_type &a, const acceptance_type &b)
994	{
995	if (a.partial_p != b.partial_p)
996	return false;
997	if (a.partial_p)
998	return a.u.subroutine_id == b.u.subroutine_id;
999	else
1000	return a.u.full.code == b.u.full.code;
1001	}
1002
1003	bool
1004	operator != (const acceptance_type &a, const acceptance_type &b)
1005	{
1006	return !operator == (a, b);
1007	}
1008
1009	/* Represents a parameter to a pattern routine. */
1010	class parameter
1011	{
1012	public:
1013	/* The C type of parameter. */
1014	enum type_enum {
1015	/* Represents an invalid parameter. */
1016	UNSET,
1017
1018	/* A machine_mode parameter. */
1019	MODE,
1020
1021	/* An rtx_code parameter. */
1022	CODE,
1023
1024	/* An int parameter. */
1025	INT,
1026
1027	/* An unsigned int parameter. */
1028	UINT,
1029
1030	/* A HOST_WIDE_INT parameter. */
1031	WIDE_INT
1032	};
1033
1034	parameter ();
1035	parameter (type_enum, bool, uint64_t);
1036
1037	/* The type of the parameter. */
1038	type_enum type;
1039
1040	/* True if the value passed is variable, false if it is constant. */
1041	bool is_param;
1042
1043	/* If IS_PARAM, this is the number of the variable passed, for an "i%d"
1044	format string. If !IS_PARAM, this is the constant value passed. */
1045	uint64_t value;
1046	};
1047
1048	parameter::parameter ()
1049	: type (UNSET), is_param (false), value (0) {}
1050
1051	parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in)
1052	: type (type_in), is_param (is_param_in), value (value_in) {}
1053
1054	bool
1055	operator == (const parameter &param1, const parameter &param2)
1056	{
1057	return (param1.type == param2.type
1058	&& param1.is_param == param2.is_param
1059	&& param1.value == param2.value);
1060	}
1061
1062	bool
1063	operator != (const parameter &param1, const parameter &param2)
1064	{
1065	return !operator == (param1, param2);
1066	}
1067
1068	/* Represents a routine that matches a partial rtx pattern, returning
1069	an ad-hoc enum value on success and -1 on failure. The routine can
1070	be used by any subroutine type. The match can be parameterized by
1071	things like mode, code and UNSPEC number. */
1072	class pattern_routine
1073	{
1074	public:
1075	/* The state that implements the pattern. */
1076	state *s;
1077
1078	/* The deepest root position from which S can access all the rtxes it needs.
1079	This is NULL if the pattern doesn't need an rtx input, usually because
1080	all matching is done on operands[] instead. */
1081	position *pos;
1082
1083	/* A unique identifier for the routine. */
1084	unsigned int pattern_id;
1085
1086	/* True if the routine takes pnum_clobbers as argument. */
1087	bool pnum_clobbers_p;
1088
1089	/* True if the routine takes the enclosing instruction as argument. */
1090	bool insn_p;
1091
1092	/* The types of the other parameters to the routine, if any. */
1093	auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types;
1094	};
1095
1096	/* All defined patterns. */
1097	static vec <pattern_routine *> patterns;
1098
1099	/* Represents one use of a pattern routine. */
1100	class pattern_use
1101	{
1102	public:
1103	/* The pattern routine to use. */
1104	pattern_routine *routine;
1105
1106	/* The values to pass as parameters. This vector has the same length
1107	as ROUTINE->PARAM_TYPES. */
1108	auto_vec <parameter, MAX_PATTERN_PARAMS> params;
1109	};
1110
1111	/* Represents a test performed by a decision. */
1112	class rtx_test
1113	{
1114	public:
1115	rtx_test ();
1116
1117	/* The types of test that can be performed. Most of them take as input
1118	an rtx X. Some also take as input a transition label LABEL; the others
1119	are booleans for which the transition label is always "true".
1120
1121	The order of the enum isn't important. */
1122	enum kind_enum {
1123	/* Check GET_CODE (X) == LABEL. */
1124	CODE,
1125
1126	/* Check GET_MODE (X) == LABEL. */
1127	MODE,
1128
1129	/* Check REGNO (X) == LABEL. */
1130	REGNO_FIELD,
1131
1132	/* Check known_eq (SUBREG_BYTE (X), LABEL). */
1133	SUBREG_FIELD,
1134
1135	/* Check XINT (X, u.opno) == LABEL. */
1136	INT_FIELD,
1137
1138	/* Check XWINT (X, u.opno) == LABEL. */
1139	WIDE_INT_FIELD,
1140
1141	/* Check XVECLEN (X, 0) == LABEL. */
1142	VECLEN,
1143
1144	/* Check peep2_current_count >= u.min_len. */
1145	PEEP2_COUNT,
1146
1147	/* Check XVECLEN (X, 0) >= u.min_len. */
1148	VECLEN_GE,
1149
1150	/* Check whether X is a cached const_int with value u.integer. */
1151	SAVED_CONST_INT,
1152
1153	/* Check u.predicate.data (X, u.predicate.mode). */
1154	PREDICATE,
1155
1156	/* Check rtx_equal_p (X, operands[u.opno]). */
1157	DUPLICATE,
1158
1159	/* Check whether X matches pattern u.pattern. */
1160	PATTERN,
1161
1162	/* Check whether pnum_clobbers is nonnull (RECOG only). */
1163	HAVE_NUM_CLOBBERS,
1164
1165	/* Check whether general C test u.string holds. In general the condition
1166	needs access to "insn" and the full operand list. */
1167	C_TEST,
1168
1169	/* Execute operands[u.opno] = X. (Always succeeds.) */
1170	SET_OP,
1171
1172	/* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT.
1173	May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */
1174	ACCEPT
1175	};
1176
1177	/* The position of rtx X in the above description, relative to the
1178	incoming instruction "insn". The position is null if the test
1179	doesn't take an X as input. */
1180	position *pos;
1181
1182	/* Which element of operands[] already contains POS, or -1 if no element
1183	is known to hold POS. */
1184	int pos_operand;
1185
1186	/* The type of test and its parameters, as described above. */
1187	kind_enum kind;
1188	union
1189	{
1190	int opno;
1191	int min_len;
1192	struct
1193	{
1194	bool is_param;
1195	int value;
1196	} integer;
1197	struct
1198	{
1199	const struct pred_data *data;
1200	/* True if the mode is taken from a machine_mode parameter
1201	to the routine rather than a constant machine_mode. If true,
1202	MODE is the number of the parameter (for an "i%d" format string),
1203	otherwise it is the mode itself. */
1204	bool mode_is_param;
1205	unsigned int mode;
1206	} predicate;
1207	pattern_use *pattern;
1208	const char *string;
1209	acceptance_type acceptance;
1210	} u;
1211
1212	static rtx_test code (position *);
1213	static rtx_test mode (position *);
1214	static rtx_test regno_field (position *);
1215	static rtx_test subreg_field (position *);
1216	static rtx_test int_field (position *, int);
1217	static rtx_test wide_int_field (position *, int);
1218	static rtx_test veclen (position *);
1219	static rtx_test peep2_count (int);
1220	static rtx_test veclen_ge (position *, int);
1221	static rtx_test predicate (position *, const pred_data *, machine_mode);
1222	static rtx_test duplicate (position *, int);
1223	static rtx_test pattern (position *, pattern_use *);
1224	static rtx_test have_num_clobbers ();
1225	static rtx_test c_test (const char *);
1226	static rtx_test set_op (position *, int);
1227	static rtx_test accept (const acceptance_type &);
1228
1229	bool terminal_p () const;
1230	bool single_outcome_p () const;
1231
1232	private:
1233	rtx_test (position *, kind_enum);
1234	};
1235
1236	rtx_test::rtx_test () {}
1237
1238	rtx_test::rtx_test (position *pos_in, kind_enum kind_in)
1239	: pos (pos_in), pos_operand (-1), kind (kind_in) {}
1240
1241	rtx_test
1242	rtx_test::code (position *pos)
1243	{
1244	return rtx_test (pos, rtx_test::CODE);
1245	}
1246
1247	rtx_test
1248	rtx_test::mode (position *pos)
1249	{
1250	return rtx_test (pos, rtx_test::MODE);
1251	}
1252
1253	rtx_test
1254	rtx_test::regno_field (position *pos)
1255	{
1256	rtx_test res (pos, rtx_test::REGNO_FIELD);
1257	return res;
1258	}
1259
1260	rtx_test
1261	rtx_test::subreg_field (position *pos)
1262	{
1263	rtx_test res (pos, rtx_test::SUBREG_FIELD);
1264	return res;
1265	}
1266
1267	rtx_test
1268	rtx_test::int_field (position *pos, int opno)
1269	{
1270	rtx_test res (pos, rtx_test::INT_FIELD);
1271	res.u.opno = opno;
1272	return res;
1273	}
1274
1275	rtx_test
1276	rtx_test::wide_int_field (position *pos, int opno)
1277	{
1278	rtx_test res (pos, rtx_test::WIDE_INT_FIELD);
1279	res.u.opno = opno;
1280	return res;
1281	}
1282
1283	rtx_test
1284	rtx_test::veclen (position *pos)
1285	{
1286	return rtx_test (pos, rtx_test::VECLEN);
1287	}
1288
1289	rtx_test
1290	rtx_test::peep2_count (int min_len)
1291	{
1292	rtx_test res (0, rtx_test::PEEP2_COUNT);
1293	res.u.min_len = min_len;
1294	return res;
1295	}
1296
1297	rtx_test
1298	rtx_test::veclen_ge (position *pos, int min_len)
1299	{
1300	rtx_test res (pos, rtx_test::VECLEN_GE);
1301	res.u.min_len = min_len;
1302	return res;
1303	}
1304
1305	rtx_test
1306	rtx_test::predicate (position *pos, const struct pred_data *data,
1307	machine_mode mode)
1308	{
1309	rtx_test res (pos, rtx_test::PREDICATE);
1310	res.u.predicate.data = data;
1311	res.u.predicate.mode_is_param = false;
1312	res.u.predicate.mode = mode;
1313	return res;
1314	}
1315
1316	rtx_test
1317	rtx_test::duplicate (position *pos, int opno)
1318	{
1319	rtx_test res (pos, rtx_test::DUPLICATE);
1320	res.u.opno = opno;
1321	return res;
1322	}
1323
1324	rtx_test
1325	rtx_test::pattern (position *pos, pattern_use *pattern)
1326	{
1327	rtx_test res (pos, rtx_test::PATTERN);
1328	res.u.pattern = pattern;
1329	return res;
1330	}
1331
1332	rtx_test
1333	rtx_test::have_num_clobbers ()
1334	{
1335	return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS);
1336	}
1337
1338	rtx_test
1339	rtx_test::c_test (const char *string)
1340	{
1341	rtx_test res (0, rtx_test::C_TEST);
1342	res.u.string = string;
1343	return res;
1344	}
1345
1346	rtx_test
1347	rtx_test::set_op (position *pos, int opno)
1348	{
1349	rtx_test res (pos, rtx_test::SET_OP);
1350	res.u.opno = opno;
1351	return res;
1352	}
1353
1354	rtx_test
1355	rtx_test::accept (const acceptance_type &acceptance)
1356	{
1357	rtx_test res (0, rtx_test::ACCEPT);
1358	res.u.acceptance = acceptance;
1359	return res;
1360	}
1361
1362	/* Return true if the test represents an unconditionally successful match. */
1363
1364	bool
1365	rtx_test::terminal_p () const
1366	{
1367	return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2;
1368	}
1369
1370	/* Return true if the test is a boolean that is always true. */
1371
1372	bool
1373	rtx_test::single_outcome_p () const
1374	{
1375	return terminal_p () || kind == rtx_test::SET_OP;
1376	}
1377
1378	bool
1379	operator == (const rtx_test &a, const rtx_test &b)
1380	{
1381	if (a.pos != b.pos || a.kind != b.kind)
1382	return false;
1383	switch (a.kind)
1384	{
1385	case rtx_test::CODE:
1386	case rtx_test::MODE:
1387	case rtx_test::REGNO_FIELD:
1388	case rtx_test::SUBREG_FIELD:
1389	case rtx_test::VECLEN:
1390	case rtx_test::HAVE_NUM_CLOBBERS:
1391	return true;
1392
1393	case rtx_test::PEEP2_COUNT:
1394	case rtx_test::VECLEN_GE:
1395	return a.u.min_len == b.u.min_len;
1396
1397	case rtx_test::INT_FIELD:
1398	case rtx_test::WIDE_INT_FIELD:
1399	case rtx_test::DUPLICATE:
1400	case rtx_test::SET_OP:
1401	return a.u.opno == b.u.opno;
1402
1403	case rtx_test::SAVED_CONST_INT:
1404	return (a.u.integer.is_param == b.u.integer.is_param
1405	&& a.u.integer.value == b.u.integer.value);
1406
1407	case rtx_test::PREDICATE:
1408	return (a.u.predicate.data == b.u.predicate.data
1409	&& a.u.predicate.mode_is_param == b.u.predicate.mode_is_param
1410	&& a.u.predicate.mode == b.u.predicate.mode);
1411
1412	case rtx_test::PATTERN:
1413	return (a.u.pattern->routine == b.u.pattern->routine
1414	&& a.u.pattern->params == b.u.pattern->params);
1415
1416	case rtx_test::C_TEST:
1417	return strcmp (s1: a.u.string, s2: b.u.string) == 0;
1418
1419	case rtx_test::ACCEPT:
1420	return a.u.acceptance == b.u.acceptance;
1421	}
1422	gcc_unreachable ();
1423	}
1424
1425	bool
1426	operator != (const rtx_test &a, const rtx_test &b)
1427	{
1428	return !operator == (a, b);
1429	}
1430
1431	/* A simple set of transition labels. Most transitions have a singleton
1432	label, so try to make that case as efficient as possible. */
1433	class int_set : public auto_vec <uint64_t, 1>
1434	{
1435	public:
1436	typedef uint64_t *iterator;
1437
1438	int_set ();
1439	int_set (uint64_t);
1440	int_set (const int_set &);
1441
1442	int_set &operator = (const int_set &);
1443
1444	iterator begin ();
1445	iterator end ();
1446	};
1447
1448	int_set::int_set () : auto_vec<uint64_t, 1> () {}
1449
1450	int_set::int_set (uint64_t label) :
1451	auto_vec<uint64_t, 1> ()
1452	{
1453	safe_push (obj: label);
1454	}
1455
1456	int_set::int_set (const int_set &other) :
1457	auto_vec<uint64_t, 1> ()
1458	{
1459	safe_splice (src: other);
1460	}
1461
1462	int_set &
1463	int_set::operator = (const int_set &other)
1464	{
1465	truncate (size: 0);
1466	safe_splice (src: other);
1467	return *this;
1468	}
1469
1470	int_set::iterator
1471	int_set::begin ()
1472	{
1473	return address ();
1474	}
1475
1476	int_set::iterator
1477	int_set::end ()
1478	{
1479	return address () + length ();
1480	}
1481
1482	bool
1483	operator == (const int_set &a, const int_set &b)
1484	{
1485	if (a.length () != b.length ())
1486	return false;
1487	for (unsigned int i = 0; i < a.length (); ++i)
1488	if (a[i] != b[i])
1489	return false;
1490	return true;
1491	}
1492
1493	bool
1494	operator != (const int_set &a, const int_set &b)
1495	{
1496	return !operator == (a, b);
1497	}
1498
1499	class decision;
1500
1501	/* Represents a transition between states, dependent on the result of
1502	a test T. */
1503	class transition
1504	{
1505	public:
1506	transition (const int_set &, state *, bool);
1507
1508	void set_parent (list_head <transition> *);
1509
1510	/* Links to other transitions for T. Always null for boolean tests. */
1511	transition *prev, *next;
1512
1513	/* The transition should be taken when T has one of these values.
1514	E.g. for rtx_test::CODE this is a set of codes, while for booleans like
1515	rtx_test::PREDICATE it is always a singleton "true". The labels are
1516	sorted in ascending order. */
1517	int_set labels;
1518
1519	/* The source decision. */
1520	decision *from;
1521
1522	/* The target state. */
1523	state *to;
1524
1525	/* True if TO would function correctly even if TEST wasn't performed.
1526	E.g. it isn't necessary to check whether GET_MODE (x1) is SImode
1527	before calling register_operand (x1, SImode), since register_operand
1528	performs its own mode check. However, checking GET_MODE can be a cheap
1529	way of disambiguating SImode and DImode register operands. */
1530	bool optional;
1531
1532	/* True if LABELS contains parameter numbers rather than constants.
1533	E.g. if this is true for a rtx_test::CODE, the label is the number
1534	of an rtx_code parameter rather than an rtx_code itself.
1535	LABELS is always a singleton when this variable is true. */
1536	bool is_param;
1537	};
1538
1539	/* Represents a test and the action that should be taken on the result.
1540	If a transition exists for the test outcome, the machine switches
1541	to the transition's target state. If no suitable transition exists,
1542	the machine either falls through to the next decision or, if there are no
1543	more decisions to try, fails the match. */
1544	class decision : public list_head <transition>
1545	{
1546	public:
1547	decision (const rtx_test &);
1548
1549	void set_parent (list_head <decision> *s);
1550	bool if_statement_p (uint64_t * = 0) const;
1551
1552	/* The state to which this decision belongs. */
1553	state *s;
1554
1555	/* Links to other decisions in the same state. */
1556	decision *prev, *next;
1557
1558	/* The test to perform. */
1559	rtx_test test;
1560	};
1561
1562	/* Represents one machine state. For each state the machine tries a list
1563	of decisions, in order, and acts on the first match. It fails without
1564	further backtracking if no decisions match. */
1565	class state : public list_head <decision>
1566	{
1567	public:
1568	void set_parent (list_head <state> *) {}
1569	};
1570
1571	transition::transition (const int_set &labels_in, state *to_in,
1572	bool optional_in)
1573	: prev (0), next (0), labels (labels_in), from (0), to (to_in),
1574	optional (optional_in), is_param (false) {}
1575
1576	/* Set the source decision of the transition. */
1577
1578	void
1579	transition::set_parent (list_head <transition> *from_in)
1580	{
1581	from = static_cast <decision *> (from_in);
1582	}
1583
1584	decision::decision (const rtx_test &test_in)
1585	: prev (0), next (0), test (test_in) {}
1586
1587	/* Set the state to which this decision belongs. */
1588
1589	void
1590	decision::set_parent (list_head <decision> *s_in)
1591	{
1592	s = static_cast <state *> (s_in);
1593	}
1594
1595	/* Return true if the decision has a single transition with a single label.
1596	If so, return the label in *LABEL if nonnull. */
1597
1598	inline bool
1599	decision::if_statement_p (uint64_t *label) const
1600	{
1601	if (singleton () && first->labels.length () == 1)
1602	{
1603	if (label)
1604	*label = first->labels[0];
1605	return true;
1606	}
1607	return false;
1608	}
1609
1610	/* Add to FROM a decision that performs TEST and has a single transition
1611	TRANS. */
1612
1613	static void
1614	add_decision (state *from, const rtx_test &test, transition *trans)
1615	{
1616	decision *d = new decision (test);
1617	from->push_back (r: d);
1618	d->push_back (r: trans);
1619	}
1620
1621	/* Add a transition from FROM to a new, empty state that is taken
1622	when TEST == LABELS. OPTIONAL says whether the new transition
1623	should be optional. Return the new state. */
1624
1625	static state *
1626	add_decision (state *from, const rtx_test &test, int_set labels, bool optional)
1627	{
1628	state *to = new state;
1629	add_decision (from, test, trans: new transition (labels, to, optional));
1630	return to;
1631	}
1632
1633	/* Insert a decision before decisions R to make them dependent on
1634	TEST == LABELS. OPTIONAL says whether the new transition should be
1635	optional. */
1636
1637	static decision *
1638	insert_decision_before (state::range r, const rtx_test &test,
1639	const int_set &labels, bool optional)
1640	{
1641	decision *newd = new decision (test);
1642	state *news = new state;
1643	newd->push_back (r: new transition (labels, news, optional));
1644	r.start->s->replace (oldr: r, newr: newd);
1645	news->push_back (r);
1646	return newd;
1647	}
1648
1649	/* Remove any optional transitions from S that turned out not to be useful. */
1650
1651	static void
1652	collapse_optional_decisions (state *s)
1653	{
1654	decision *d = s->first;
1655	while (d)
1656	{
1657	decision *next = d->next;
1658	for (transition *trans = d->first; trans; trans = trans->next)
1659	collapse_optional_decisions (s: trans->to);
1660	/* A decision with a single optional transition doesn't help
1661	partition the potential matches and so is unlikely to be
1662	worthwhile. In particular, if the decision that performs the
1663	test is the last in the state, the best it could do is reject
1664	an invalid pattern slightly earlier. If instead the decision
1665	is not the last in the state, the condition it tests could hold
1666	even for the later decisions in the state. The best it can do
1667	is save work in some cases where only the later decisions can
1668	succeed.
1669
1670	In both cases the optional transition would add extra work to
1671	successful matches when the tested condition holds. */
1672	if (transition *trans = d->singleton ())
1673	if (trans->optional)
1674	s->replace (oldr: d, newr: trans->to->release ());
1675	d = next;
1676	}
1677	}
1678
1679	/* Try to squash several separate tests into simpler ones. */
1680
1681	static void
1682	simplify_tests (state *s)
1683	{
1684	for (decision *d = s->first; d; d = d->next)
1685	{
1686	uint64_t label;
1687	/* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N
1688	into checks for const_int_rtx[N'], if N is suitably small. */
1689	if (d->test.kind == rtx_test::CODE
1690	&& d->if_statement_p (label: &label)
1691	&& label == CONST_INT)
1692	if (decision *second = d->first->to->singleton ())
1693	if (d->test.pos == second->test.pos
1694	&& second->test.kind == rtx_test::WIDE_INT_FIELD
1695	&& second->test.u.opno == 0
1696	&& second->if_statement_p (label: &label)
1697	&& IN_RANGE (int64_t (label),
1698	-MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT))
1699	{
1700	d->test.kind = rtx_test::SAVED_CONST_INT;
1701	d->test.u.integer.is_param = false;
1702	d->test.u.integer.value = label;
1703	d->replace (oldr: d->first, newr: second->release ());
1704	d->first->labels[0] = true;
1705	}
1706	/* If we have a CODE test followed by a PREDICATE test, rely on
1707	the predicate to test the code.
1708
1709	This case exists for match_operators. We initially treat the
1710	CODE test for a match_operator as non-optional so that we can
1711	safely move down to its operands. It may turn out that all
1712	paths that reach that code test require the same predicate
1713	to be true. cse_tests will then put the predicate test in
1714	series with the code test. */
1715	if (d->test.kind == rtx_test::CODE)
1716	if (transition *trans = d->singleton ())
1717	{
1718	state *s = trans->to;
1719	while (decision *d2 = s->singleton ())
1720	{
1721	if (d->test.pos != d2->test.pos)
1722	break;
1723	transition *trans2 = d2->singleton ();
1724	if (!trans2)
1725	break;
1726	if (d2->test.kind == rtx_test::PREDICATE)
1727	{
1728	d->test = d2->test;
1729	trans->labels = int_set (true);
1730	s->replace (oldr: d2, newr: trans2->to->release ());
1731	break;
1732	}
1733	s = trans2->to;
1734	}
1735	}
1736	for (transition *trans = d->first; trans; trans = trans->next)
1737	simplify_tests (s: trans->to);
1738	}
1739	}
1740
1741	/* Return true if all successful returns passing through D require the
1742	condition tested by COMMON to be true.
1743
1744	When returning true, add all transitions like COMMON in D to WHERE.
1745	WHERE may contain a partial result on failure. */
1746
1747	static bool
1748	common_test_p (decision *d, transition *common, vec <transition *> *where)
1749	{
1750	if (d->test.kind == rtx_test::ACCEPT)
1751	/* We found a successful return that didn't require COMMON. */
1752	return false;
1753	if (d->test == common->from->test)
1754	{
1755	transition *trans = d->singleton ();
1756	if (!trans
1757	|| trans->optional != common->optional
1758	|| trans->labels != common->labels)
1759	return false;
1760	where->safe_push (obj: trans);
1761	return true;
1762	}
1763	for (transition *trans = d->first; trans; trans = trans->next)
1764	for (decision *subd = trans->to->first; subd; subd = subd->next)
1765	if (!common_test_p (d: subd, common, where))
1766	return false;
1767	return true;
1768	}
1769
1770	/* Indicates that we have tested GET_CODE (X) for a particular rtx X. */
1771	const unsigned char TESTED_CODE = 1;
1772
1773	/* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */
1774	const unsigned char TESTED_VECLEN = 2;
1775
1776	/* Represents a set of conditions that are known to hold. */
1777	class known_conditions
1778	{
1779	public:
1780	/* A mask of TESTED_ values for each position, indexed by the position's
1781	id field. */
1782	auto_vec <unsigned char> position_tests;
1783
1784	/* Index N says whether operands[N] has been set. */
1785	auto_vec <bool> set_operands;
1786
1787	/* A guranteed lower bound on the value of peep2_current_count. */
1788	int peep2_count;
1789	};
1790
1791	/* Return true if TEST can safely be performed at D, where
1792	the conditions in KC hold. TEST is known to occur along the
1793	first path from D (i.e. always following the first transition
1794	of the first decision). Any intervening tests can be used as
1795	negative proof that hoisting isn't safe, but only KC can be used
1796	as positive proof. */
1797
1798	static bool
1799	safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc)
1800	{
1801	switch (test.kind)
1802	{
1803	case rtx_test::C_TEST:
1804	/* In general, C tests require everything else to have been
1805	verified and all operands to have been set up. */
1806	return false;
1807
1808	case rtx_test::ACCEPT:
1809	/* Don't accept something before all conditions have been tested. */
1810	return false;
1811
1812	case rtx_test::PREDICATE:
1813	/* Don't move a predicate over a test for VECLEN_GE, since the
1814	predicate used in a match_parallel can legitimately expect the
1815	length to be checked first. */
1816	for (decision *subd = d;
1817	subd->test != test;
1818	subd = subd->first->to->first)
1819	if (subd->test.pos == test.pos
1820	&& subd->test.kind == rtx_test::VECLEN_GE)
1821	return false;
1822	goto any_rtx;
1823
1824	case rtx_test::DUPLICATE:
1825	/* Don't test for a match_dup until the associated operand has
1826	been set. */
1827	if (!kc->set_operands[test.u.opno])
1828	return false;
1829	goto any_rtx;
1830
1831	case rtx_test::CODE:
1832	case rtx_test::MODE:
1833	case rtx_test::SAVED_CONST_INT:
1834	case rtx_test::SET_OP:
1835	any_rtx:
1836	/* Check whether it is safe to access the rtx under test. */
1837	switch (test.pos->type)
1838	{
1839	case POS_PEEP2_INSN:
1840	return test.pos->arg < kc->peep2_count;
1841
1842	case POS_XEXP:
1843	return kc->position_tests[test.pos->base->id] & TESTED_CODE;
1844
1845	case POS_XVECEXP0:
1846	return kc->position_tests[test.pos->base->id] & TESTED_VECLEN;
1847	}
1848	gcc_unreachable ();
1849
1850	case rtx_test::REGNO_FIELD:
1851	case rtx_test::SUBREG_FIELD:
1852	case rtx_test::INT_FIELD:
1853	case rtx_test::WIDE_INT_FIELD:
1854	case rtx_test::VECLEN:
1855	case rtx_test::VECLEN_GE:
1856	/* These tests access a specific part of an rtx, so are only safe
1857	once we know what the rtx is. */
1858	return kc->position_tests[test.pos->id] & TESTED_CODE;
1859
1860	case rtx_test::PEEP2_COUNT:
1861	case rtx_test::HAVE_NUM_CLOBBERS:
1862	/* These tests can be performed anywhere. */
1863	return true;
1864
1865	case rtx_test::PATTERN:
1866	gcc_unreachable ();
1867	}
1868	gcc_unreachable ();
1869	}
1870
1871	/* Look for a transition that is taken by all successful returns from a range
1872	of decisions starting at OUTER and that would be better performed by
1873	OUTER's state instead. On success, store all instances of that transition
1874	in WHERE and return the last decision in the range. The range could
1875	just be OUTER, or it could include later decisions as well.
1876
1877	WITH_POSITION_P is true if only tests with position POS should be tried,
1878	false if any test should be tried. WORTHWHILE_SINGLE_P is true if the
1879	result is useful even when the range contains just a single decision
1880	with a single transition. KC are the conditions that are known to
1881	hold at OUTER. */
1882
1883	static decision *
1884	find_common_test (decision *outer, bool with_position_p,
1885	position *pos, bool worthwhile_single_p,
1886	known_conditions *kc, vec <transition *> *where)
1887	{
1888	/* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains
1889	just a single decision is useful, regardless of the number of
1890	transitions it has. */
1891	if (!outer->singleton ())
1892	worthwhile_single_p = true;
1893	/* Quick exit if we don't have enough decisions to form a worthwhile
1894	range. */
1895	if (!worthwhile_single_p && !outer->next)
1896	return 0;
1897	/* Follow the first chain down, as one example of a path that needs
1898	to contain the common test. */
1899	for (decision *d = outer; d; d = d->first->to->first)
1900	{
1901	transition *trans = d->singleton ();
1902	if (trans
1903	&& (!with_position_p || d->test.pos == pos)
1904	&& safe_to_hoist_p (d: outer, test: d->test, kc))
1905	{
1906	if (common_test_p (d: outer, common: trans, where))
1907	{
1908	if (!outer->next)
1909	/* We checked above whether the move is worthwhile. */
1910	return outer;
1911	/* See how many decisions in OUTER's chain could reuse
1912	the same test. */
1913	decision *outer_end = outer;
1914	do
1915	{
1916	unsigned int length = where->length ();
1917	if (!common_test_p (d: outer_end->next, common: trans, where))
1918	{
1919	where->truncate (size: length);
1920	break;
1921	}
1922	outer_end = outer_end->next;
1923	}
1924	while (outer_end->next);
1925	/* It is worth moving TRANS if it can be shared by more than
1926	one decision. */
1927	if (outer_end != outer || worthwhile_single_p)
1928	return outer_end;
1929	}
1930	where->truncate (size: 0);
1931	}
1932	}
1933	return 0;
1934	}
1935
1936	/* Try to promote common subtests in S to a single, shared decision.
1937	Also try to bunch tests for the same position together. POS is the
1938	position of the rtx tested before reaching S. KC are the conditions
1939	that are known to hold on entry to S. */
1940
1941	static void
1942	cse_tests (position *pos, state *s, known_conditions *kc)
1943	{
1944	for (decision *d = s->first; d; d = d->next)
1945	{
1946	auto_vec <transition *, 16> where;
1947	if (d->test.pos)
1948	{
1949	/* Try to find conditions that don't depend on a particular rtx,
1950	such as pnum_clobbers != NULL or peep2_current_count >= X.
1951	It's usually better to check these conditions as soon as
1952	possible, so the change is worthwhile even if there is
1953	only one copy of the test. */
1954	decision *endd = find_common_test (outer: d, with_position_p: true, pos: 0, worthwhile_single_p: true, kc, where: &where);
1955	if (!endd && d->test.pos != pos)
1956	/* Try to find other conditions related to position POS
1957	before moving to the new position. Again, this is
1958	worthwhile even if there is only one copy of the test,
1959	since it means that fewer position variables are live
1960	at a given time. */
1961	endd = find_common_test (outer: d, with_position_p: true, pos, worthwhile_single_p: true, kc, where: &where);
1962	if (!endd)
1963	/* Try to find any condition that is used more than once. */
1964	endd = find_common_test (outer: d, with_position_p: false, pos: 0, worthwhile_single_p: false, kc, where: &where);
1965	if (endd)
1966	{
1967	transition *common = where[0];
1968	/* Replace [D, ENDD] with a test like COMMON. We'll recurse
1969	on the common test and see the original D again next time. */
1970	d = insert_decision_before (r: state::range (d, endd),
1971	test: common->from->test,
1972	labels: common->labels,
1973	optional: common->optional);
1974	/* Remove the old tests. */
1975	while (!where.is_empty ())
1976	{
1977	transition *trans = where.pop ();
1978	trans->from->s->replace (oldr: trans->from, newr: trans->to->release ());
1979	}
1980	}
1981	}
1982
1983	/* Make sure that safe_to_hoist_p isn't being overly conservative.
1984	It should realize that D's test is safe in the current
1985	environment. */
1986	gcc_assert (d->test.kind == rtx_test::C_TEST
1987	|| d->test.kind == rtx_test::ACCEPT
1988	|| safe_to_hoist_p (d, d->test, kc));
1989
1990	/* D won't be changed any further by the current optimization.
1991	Recurse with the state temporarily updated to include D. */
1992	int prev = 0;
1993	switch (d->test.kind)
1994	{
1995	case rtx_test::CODE:
1996	prev = kc->position_tests[d->test.pos->id];
1997	kc->position_tests[d->test.pos->id] |= TESTED_CODE;
1998	break;
1999
2000	case rtx_test::VECLEN:
2001	case rtx_test::VECLEN_GE:
2002	prev = kc->position_tests[d->test.pos->id];
2003	kc->position_tests[d->test.pos->id] |= TESTED_VECLEN;
2004	break;
2005
2006	case rtx_test::SET_OP:
2007	prev = kc->set_operands[d->test.u.opno];
2008	gcc_assert (!prev);
2009	kc->set_operands[d->test.u.opno] = true;
2010	break;
2011
2012	case rtx_test::PEEP2_COUNT:
2013	prev = kc->peep2_count;
2014	kc->peep2_count = MAX (prev, d->test.u.min_len);
2015	break;
2016
2017	default:
2018	break;
2019	}
2020	for (transition *trans = d->first; trans; trans = trans->next)
2021	cse_tests (pos: d->test.pos ? d->test.pos : pos, s: trans->to, kc);
2022	switch (d->test.kind)
2023	{
2024	case rtx_test::CODE:
2025	case rtx_test::VECLEN:
2026	case rtx_test::VECLEN_GE:
2027	kc->position_tests[d->test.pos->id] = prev;
2028	break;
2029
2030	case rtx_test::SET_OP:
2031	kc->set_operands[d->test.u.opno] = prev;
2032	break;
2033
2034	case rtx_test::PEEP2_COUNT:
2035	kc->peep2_count = prev;
2036	break;
2037
2038	default:
2039	break;
2040	}
2041	}
2042	}
2043
2044	/* Return the type of value that can be used to parameterize test KIND,
2045	or parameter::UNSET if none. */
2046
2047	parameter::type_enum
2048	transition_parameter_type (rtx_test::kind_enum kind)
2049	{
2050	switch (kind)
2051	{
2052	case rtx_test::CODE:
2053	return parameter::CODE;
2054
2055	case rtx_test::MODE:
2056	return parameter::MODE;
2057
2058	case rtx_test::REGNO_FIELD:
2059	case rtx_test::SUBREG_FIELD:
2060	return parameter::UINT;
2061
2062	case rtx_test::INT_FIELD:
2063	case rtx_test::VECLEN:
2064	case rtx_test::PATTERN:
2065	return parameter::INT;
2066
2067	case rtx_test::WIDE_INT_FIELD:
2068	return parameter::WIDE_INT;
2069
2070	case rtx_test::PEEP2_COUNT:
2071	case rtx_test::VECLEN_GE:
2072	case rtx_test::SAVED_CONST_INT:
2073	case rtx_test::PREDICATE:
2074	case rtx_test::DUPLICATE:
2075	case rtx_test::HAVE_NUM_CLOBBERS:
2076	case rtx_test::C_TEST:
2077	case rtx_test::SET_OP:
2078	case rtx_test::ACCEPT:
2079	return parameter::UNSET;
2080	}
2081	gcc_unreachable ();
2082	}
2083
2084	/* Initialize the pos_operand fields of each state reachable from S.
2085	If OPERAND_POS[ID] >= 0, the position with id ID is stored in
2086	operands[OPERAND_POS[ID]] on entry to S. */
2087
2088	static void
2089	find_operand_positions (state *s, vec <int> &operand_pos)
2090	{
2091	for (decision *d = s->first; d; d = d->next)
2092	{
2093	int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1);
2094	if (this_operand >= 0)
2095	d->test.pos_operand = this_operand;
2096	if (d->test.kind == rtx_test::SET_OP)
2097	operand_pos[d->test.pos->id] = d->test.u.opno;
2098	for (transition *trans = d->first; trans; trans = trans->next)
2099	find_operand_positions (s: trans->to, operand_pos);
2100	if (d->test.kind == rtx_test::SET_OP)
2101	operand_pos[d->test.pos->id] = this_operand;
2102	}
2103	}
2104
2105	/* Statistics about a matching routine. */
2106	class stats
2107	{
2108	public:
2109	stats ();
2110
2111	/* The total number of decisions in the routine, excluding trivial
2112	ones that never fail. */
2113	unsigned int num_decisions;
2114
2115	/* The number of non-trivial decisions on the longest path through
2116	the routine, and the return value that contributes most to that
2117	long path. */
2118	unsigned int longest_path;
2119	int longest_path_code;
2120
2121	/* The maximum number of times that a single call to the routine
2122	can backtrack, and the value returned at the end of that path.
2123	"Backtracking" here means failing one decision in state and
2124	going onto to the next. */
2125	unsigned int longest_backtrack;
2126	int longest_backtrack_code;
2127	};
2128
2129	stats::stats ()
2130	: num_decisions (0), longest_path (0), longest_path_code (-1),
2131	longest_backtrack (0), longest_backtrack_code (-1) {}
2132
2133	/* Return statistics about S. */
2134
2135	static stats
2136	get_stats (state *s)
2137	{
2138	stats for_s;
2139	unsigned int longest_path = 0;
2140	for (decision *d = s->first; d; d = d->next)
2141	{
2142	/* Work out the statistics for D. */
2143	stats for_d;
2144	for (transition *trans = d->first; trans; trans = trans->next)
2145	{
2146	stats for_trans = get_stats (s: trans->to);
2147	for_d.num_decisions += for_trans.num_decisions;
2148	/* Each transition is mutually-exclusive, so just pick the
2149	longest of the individual paths. */
2150	if (for_d.longest_path <= for_trans.longest_path)
2151	{
2152	for_d.longest_path = for_trans.longest_path;
2153	for_d.longest_path_code = for_trans.longest_path_code;
2154	}
2155	/* Likewise for backtracking. */
2156	if (for_d.longest_backtrack <= for_trans.longest_backtrack)
2157	{
2158	for_d.longest_backtrack = for_trans.longest_backtrack;
2159	for_d.longest_backtrack_code = for_trans.longest_backtrack_code;
2160	}
2161	}
2162
2163	/* Account for D's test in its statistics. */
2164	if (!d->test.single_outcome_p ())
2165	{
2166	for_d.num_decisions += 1;
2167	for_d.longest_path += 1;
2168	}
2169	if (d->test.kind == rtx_test::ACCEPT)
2170	{
2171	for_d.longest_path_code = d->test.u.acceptance.u.full.code;
2172	for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code;
2173	}
2174
2175	/* Keep a running count of the number of backtracks. */
2176	if (d->prev)
2177	for_s.longest_backtrack += 1;
2178
2179	/* Accumulate D's statistics into S's. */
2180	for_s.num_decisions += for_d.num_decisions;
2181	for_s.longest_path += for_d.longest_path;
2182	for_s.longest_backtrack += for_d.longest_backtrack;
2183
2184	/* Use the code from the decision with the longest individual path,
2185	since that's more likely to be useful if trying to make the
2186	path shorter. In the event of a tie, pick the later decision,
2187	since that's closer to the end of the path. */
2188	if (longest_path <= for_d.longest_path)
2189	{
2190	longest_path = for_d.longest_path;
2191	for_s.longest_path_code = for_d.longest_path_code;
2192	}
2193
2194	/* Later decisions in a state are necessarily in a longer backtrack
2195	than earlier decisions. */
2196	for_s.longest_backtrack_code = for_d.longest_backtrack_code;
2197	}
2198	return for_s;
2199	}
2200
2201	/* Optimize ROOT. Use TYPE to describe ROOT in status messages. */
2202
2203	static void
2204	optimize_subroutine_group (const char *type, state *root)
2205	{
2206	/* Remove optional transitions that turned out not to be worthwhile. */
2207	if (collapse_optional_decisions_p)
2208	collapse_optional_decisions (s: root);
2209
2210	/* Try to remove duplicated tests and to rearrange tests into a more
2211	logical order. */
2212	if (cse_tests_p)
2213	{
2214	known_conditions kc;
2215	kc.position_tests.safe_grow_cleared (len: num_positions, exact: true);
2216	kc.set_operands.safe_grow_cleared (len: num_operands, exact: true);
2217	kc.peep2_count = 1;
2218	cse_tests (pos: &root_pos, s: root, kc: &kc);
2219	}
2220
2221	/* Try to simplify two or more tests into one. */
2222	if (simplify_tests_p)
2223	simplify_tests (s: root);
2224
2225	/* Try to use operands[] instead of xN variables. */
2226	if (use_operand_variables_p)
2227	{
2228	auto_vec <int> operand_pos (num_positions);
2229	for (unsigned int i = 0; i < num_positions; ++i)
2230	operand_pos.quick_push (obj: -1);
2231	find_operand_positions (s: root, operand_pos);
2232	}
2233
2234	/* Print a summary of the new state. */
2235	stats st = get_stats (s: root);
2236	fprintf (stderr, format: "Statistics for %s:\n", type);
2237	fprintf (stderr, format: " Number of decisions: %6d\n", st.num_decisions);
2238	fprintf (stderr, format: " longest path: %6d (code: %6d)\n",
2239	st.longest_path, st.longest_path_code);
2240	fprintf (stderr, format: " longest backtrack: %6d (code: %6d)\n",
2241	st.longest_backtrack, st.longest_backtrack_code);
2242	}
2243
2244	class merge_pattern_info;
2245
2246	/* Represents a transition from one pattern to another. */
2247	class merge_pattern_transition
2248	{
2249	public:
2250	merge_pattern_transition (merge_pattern_info *);
2251
2252	/* The target pattern. */
2253	merge_pattern_info *to;
2254
2255	/* The parameters that the source pattern passes to the target pattern.
2256	"parameter (TYPE, true, I)" represents parameter I of the source
2257	pattern. */
2258	auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2259	};
2260
2261	merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in)
2262	: to (to_in)
2263	{
2264	}
2265
2266	/* Represents a pattern that can might match several states. The pattern
2267	may replace parts of the test with a parameter value. It may also
2268	replace transition labels with parameters. */
2269	class merge_pattern_info
2270	{
2271	public:
2272	merge_pattern_info (unsigned int);
2273
2274	/* If PARAM_TEST_P, the state's singleton test should be generalized
2275	to use the runtime value of PARAMS[PARAM_TEST]. */
2276	unsigned int param_test : 8;
2277
2278	/* If PARAM_TRANSITION_P, the state's single transition label should
2279	be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */
2280	unsigned int param_transition : 8;
2281
2282	/* True if we have decided to generalize the root decision's test,
2283	as per PARAM_TEST. */
2284	unsigned int param_test_p : 1;
2285
2286	/* Likewise for the root decision's transition, as per PARAM_TRANSITION. */
2287	unsigned int param_transition_p : 1;
2288
2289	/* True if the contents of the structure are completely filled in. */
2290	unsigned int complete_p : 1;
2291
2292	/* The number of pseudo-statements in the pattern. Used to decide
2293	whether it's big enough to break out into a subroutine. */
2294	unsigned int num_statements;
2295
2296	/* The number of states that use this pattern. */
2297	unsigned int num_users;
2298
2299	/* The number of distinct success values that the pattern returns. */
2300	unsigned int num_results;
2301
2302	/* This array has one element for each runtime parameter to the pattern.
2303	PARAMS[I] gives the default value of parameter I, which is always
2304	constant.
2305
2306	These default parameters are used in cases where we match the
2307	pattern against some state S1, then add more parameters while
2308	matching against some state S2. S1 is then left passing fewer
2309	parameters than S2. The array gives us enough informatino to
2310	construct a full parameter list for S1 (see update_parameters).
2311
2312	If we decide to create a subroutine for this pattern,
2313	PARAMS[I].type determines the C type of parameter I. */
2314	auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2315
2316	/* All states that match this pattern must have the same number of
2317	transitions. TRANSITIONS[I] describes the subpattern for transition
2318	number I; it is null if transition I represents a successful return
2319	from the pattern. */
2320	auto_vec <merge_pattern_transition *, 1> transitions;
2321
2322	/* The routine associated with the pattern, or null if we haven't generated
2323	one yet. */
2324	pattern_routine *routine;
2325	};
2326
2327	merge_pattern_info::merge_pattern_info (unsigned int num_transitions)
2328	: param_test (0),
2329	param_transition (0),
2330	param_test_p (false),
2331	param_transition_p (false),
2332	complete_p (false),
2333	num_statements (0),
2334	num_users (0),
2335	num_results (0),
2336	routine (0)
2337	{
2338	transitions.safe_grow_cleared (len: num_transitions, exact: true);
2339	}
2340
2341	/* Describes one way of matching a particular state to a particular
2342	pattern. */
2343	class merge_state_result
2344	{
2345	public:
2346	merge_state_result (merge_pattern_info *, position *, merge_state_result *);
2347
2348	/* A pattern that matches the state. */
2349	merge_pattern_info *pattern;
2350
2351	/* If we decide to use this match and create a subroutine for PATTERN,
2352	the state should pass the rtx at position ROOT to the pattern's
2353	rtx parameter. A null root means that the pattern doesn't need
2354	an rtx parameter; all the rtxes it matches come from elsewhere. */
2355	position *root;
2356
2357	/* The parameters that should be passed to PATTERN for this state.
2358	If the array is shorter than PATTERN->params, the missing entries
2359	should be taken from the corresponding element of PATTERN->params. */
2360	auto_vec <parameter, MAX_PATTERN_PARAMS> params;
2361
2362	/* An earlier match for the same state, or null if none. Patterns
2363	matched by earlier entries are smaller than PATTERN. */
2364	merge_state_result *prev;
2365	};
2366
2367	merge_state_result::merge_state_result (merge_pattern_info *pattern_in,
2368	position *root_in,
2369	merge_state_result *prev_in)
2370	: pattern (pattern_in), root (root_in), prev (prev_in)
2371	{}
2372
2373	/* Information about a state, used while trying to match it against
2374	a pattern. */
2375	class merge_state_info
2376	{
2377	public:
2378	merge_state_info (state *);
2379
2380	/* The state itself. */
2381	state *s;
2382
2383	/* Index I gives information about the target of transition I. */
2384	merge_state_info *to_states;
2385
2386	/* The number of transitions in S. */
2387	unsigned int num_transitions;
2388
2389	/* True if the state has been deleted in favor of a call to a
2390	pattern routine. */
2391	bool merged_p;
2392
2393	/* The previous state that might be a merge candidate for S, or null
2394	if no previous states could be merged with S. */
2395	merge_state_info *prev_same_test;
2396
2397	/* A list of pattern matches for this state. */
2398	merge_state_result *res;
2399	};
2400
2401	merge_state_info::merge_state_info (state *s_in)
2402	: s (s_in),
2403	to_states (0),
2404	num_transitions (0),
2405	merged_p (false),
2406	prev_same_test (0),
2407	res (0) {}
2408
2409	/* True if PAT would be useful as a subroutine. */
2410
2411	static bool
2412	useful_pattern_p (merge_pattern_info *pat)
2413	{
2414	return pat->num_statements >= MIN_COMBINE_COST;
2415	}
2416
2417	/* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined
2418	into PAT1's C routine. */
2419
2420	static bool
2421	same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2)
2422	{
2423	return pat1->num_users == pat2->num_users || !useful_pattern_p (pat: pat2);
2424	}
2425
2426	/* PAT was previously matched against SINFO based on tentative matches
2427	for the target states of SINFO's state. Return true if the match
2428	still holds; that is, if the target states of SINFO's state still
2429	match the corresponding transitions of PAT. */
2430
2431	static bool
2432	valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2433	{
2434	for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2435	if (merge_pattern_transition *ptrans = pat->transitions[j])
2436	{
2437	merge_state_result *to_res = sinfo->to_states[j].res;
2438	if (!to_res || to_res->pattern != ptrans->to)
2439	return false;
2440	}
2441	return true;
2442	}
2443
2444	/* Remove any matches that are no longer valid from the head of SINFO's
2445	list of matches. */
2446
2447	static void
2448	prune_invalid_results (merge_state_info *sinfo)
2449	{
2450	while (sinfo->res && !valid_result_p (pat: sinfo->res->pattern, sinfo))
2451	{
2452	sinfo->res = sinfo->res->prev;
2453	gcc_assert (sinfo->res);
2454	}
2455	}
2456
2457	/* Return true if PAT represents the biggest posssible match for SINFO;
2458	that is, if the next action of SINFO's state on return from PAT will
2459	be something that cannot be merged with any other state. */
2460
2461	static bool
2462	complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo)
2463	{
2464	for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
2465	if (sinfo->to_states[j].res && !pat->transitions[j])
2466	return false;
2467	return true;
2468	}
2469
2470	/* Update TO for any parameters that have been added to FROM since TO
2471	was last set. The extra parameters in FROM will be constants or
2472	instructions to duplicate earlier parameters. */
2473
2474	static void
2475	update_parameters (vec <parameter> &to, const vec <parameter> &from)
2476	{
2477	for (unsigned int i = to.length (); i < from.length (); ++i)
2478	to.quick_push (obj: from[i]);
2479	}
2480
2481	/* Return true if A and B can be tested by a single test. If the test
2482	can be parameterised, store the parameter value for A in *PARAMA and
2483	the parameter value for B in *PARAMB, otherwise leave PARAMA and
2484	PARAMB alone. */
2485
2486	static bool
2487	compatible_tests_p (const rtx_test &a, const rtx_test &b,
2488	parameter *parama, parameter *paramb)
2489	{
2490	if (a.kind != b.kind)
2491	return false;
2492	switch (a.kind)
2493	{
2494	case rtx_test::PREDICATE:
2495	if (a.u.predicate.data != b.u.predicate.data)
2496	return false;
2497	*parama = parameter (parameter::MODE, false, a.u.predicate.mode);
2498	*paramb = parameter (parameter::MODE, false, b.u.predicate.mode);
2499	return true;
2500
2501	case rtx_test::SAVED_CONST_INT:
2502	*parama = parameter (parameter::INT, false, a.u.integer.value);
2503	*paramb = parameter (parameter::INT, false, b.u.integer.value);
2504	return true;
2505
2506	default:
2507	return a == b;
2508	}
2509	}
2510
2511	/* PARAMS is an array of the parameters that a state is going to pass
2512	to a pattern routine. It is still incomplete; index I has a kind of
2513	parameter::UNSET if we don't yet know what the state will pass
2514	as parameter I. Try to make parameter ID equal VALUE, returning
2515	true on success. */
2516
2517	static bool
2518	set_parameter (vec <parameter> &params, unsigned int id,
2519	const parameter &value)
2520	{
2521	if (params[id].type == parameter::UNSET)
2522	{
2523	if (force_unique_params_p)
2524	for (unsigned int i = 0; i < params.length (); ++i)
2525	if (params[i] == value)
2526	return false;
2527	params[id] = value;
2528	return true;
2529	}
2530	return params[id] == value;
2531	}
2532
2533	/* PARAMS2 is the "params" array for a pattern and PARAMS1 is the
2534	set of parameters that a particular state is going to pass to
2535	that pattern.
2536
2537	Try to extend PARAMS1 and PARAMS2 so that there is a parameter
2538	that is equal to PARAM1 for the state and has a default value of
2539	PARAM2. Parameters beginning at START were added as part of the
2540	same match and so may be reused. */
2541
2542	static bool
2543	add_parameter (vec <parameter> &params1, vec <parameter> &params2,
2544	const parameter &param1, const parameter &param2,
2545	unsigned int start, unsigned int *res)
2546	{
2547	gcc_assert (params1.length () == params2.length ());
2548	gcc_assert (!param1.is_param && !param2.is_param);
2549
2550	for (unsigned int i = start; i < params2.length (); ++i)
2551	if (params1[i] == param1 && params2[i] == param2)
2552	{
2553	*res = i;
2554	return true;
2555	}
2556
2557	if (force_unique_params_p)
2558	for (unsigned int i = 0; i < params2.length (); ++i)
2559	if (params1[i] == param1 || params2[i] == param2)
2560	return false;
2561
2562	if (params2.length () >= MAX_PATTERN_PARAMS)
2563	return false;
2564
2565	*res = params2.length ();
2566	params1.quick_push (obj: param1);
2567	params2.quick_push (obj: param2);
2568	return true;
2569	}
2570
2571	/* If *ROOTA is nonnull, return true if the same sequence of steps are
2572	required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA
2573	is null, update it if necessary in order to make the condition hold. */
2574
2575	static bool
2576	merge_relative_positions (position **roota, position *a,
2577	position *rootb, position *b)
2578	{
2579	if (!relative_patterns_p)
2580	{
2581	if (a != b)
2582	return false;
2583	if (!*roota)
2584	{
2585	*roota = rootb;
2586	return true;
2587	}
2588	return *roota == rootb;
2589	}
2590	/* If B does not belong to the same instruction as ROOTB, we don't
2591	start with ROOTB but instead start with a call to peep2_next_insn.
2592	In that case the sequences for B and A are identical iff B and A
2593	are themselves identical. */
2594	if (rootb->insn_id != b->insn_id)
2595	return a == b;
2596	while (rootb != b)
2597	{
2598	if (!a || b->type != a->type || b->arg != a->arg)
2599	return false;
2600	b = b->base;
2601	a = a->base;
2602	}
2603	if (!*roota)
2604	*roota = a;
2605	return *roota == a;
2606	}
2607
2608	/* A hasher of states that treats two states as "equal" if they might be
2609	merged (but trying to be more discriminating than "return true"). */
2610	struct test_pattern_hasher : nofree_ptr_hash <merge_state_info>
2611	{
2612	static inline hashval_t hash (const value_type &);
2613	static inline bool equal (const value_type &, const compare_type &);
2614	};
2615
2616	hashval_t
2617	test_pattern_hasher::hash (merge_state_info *const &sinfo)
2618	{
2619	inchash::hash h;
2620	decision *d = sinfo->s->singleton ();
2621	h.add_int (v: d->test.pos_operand + 1);
2622	if (!relative_patterns_p)
2623	h.add_int (v: d->test.pos ? d->test.pos->id + 1 : 0);
2624	h.add_int (v: d->test.kind);
2625	h.add_int (v: sinfo->num_transitions);
2626	return h.end ();
2627	}
2628
2629	bool
2630	test_pattern_hasher::equal (merge_state_info *const &sinfo1,
2631	merge_state_info *const &sinfo2)
2632	{
2633	decision *d1 = sinfo1->s->singleton ();
2634	decision *d2 = sinfo2->s->singleton ();
2635	gcc_assert (d1 && d2);
2636
2637	parameter new_param1, new_param2;
2638	return (d1->test.pos_operand == d2->test.pos_operand
2639	&& (relative_patterns_p || d1->test.pos == d2->test.pos)
2640	&& compatible_tests_p (a: d1->test, b: d2->test, parama: &new_param1, paramb: &new_param2)
2641	&& sinfo1->num_transitions == sinfo2->num_transitions);
2642	}
2643
2644	/* Try to make the state described by SINFO1 use the same pattern as the
2645	state described by SINFO2. Return true on success.
2646
2647	SINFO1 and SINFO2 are known to have the same hash value. */
2648
2649	static bool
2650	merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2)
2651	{
2652	merge_state_result *res2 = sinfo2->res;
2653	merge_pattern_info *pat = res2->pattern;
2654
2655	/* Write to temporary arrays while matching, in case we have to abort
2656	half way through. */
2657	auto_vec <parameter, MAX_PATTERN_PARAMS> params1;
2658	auto_vec <parameter, MAX_PATTERN_PARAMS> params2;
2659	params1.quick_grow_cleared (len: pat->params.length ());
2660	params2.splice (src: pat->params);
2661	unsigned int start_param = params2.length ();
2662
2663	/* An array for recording changes to PAT->transitions[?].params.
2664	All changes involve replacing a constant parameter with some
2665	PAT->params[N], where N is the second element of the pending_param. */
2666	typedef std::pair <parameter *, unsigned int> pending_param;
2667	auto_vec <pending_param, 32> pending_params;
2668
2669	decision *d1 = sinfo1->s->singleton ();
2670	decision *d2 = sinfo2->s->singleton ();
2671	gcc_assert (d1 && d2);
2672
2673	/* If D2 tests a position, SINFO1's root relative to D1 is the same
2674	as SINFO2's root relative to D2. */
2675	position *root1 = 0;
2676	position *root2 = res2->root;
2677	if (d2->test.pos_operand < 0
2678	&& d1->test.pos
2679	&& !merge_relative_positions (roota: &root1, a: d1->test.pos,
2680	rootb: root2, b: d2->test.pos))
2681	return false;
2682
2683	/* Check whether the patterns have the same shape. */
2684	unsigned int num_transitions = sinfo1->num_transitions;
2685	gcc_assert (num_transitions == sinfo2->num_transitions);
2686	for (unsigned int i = 0; i < num_transitions; ++i)
2687	if (merge_pattern_transition *ptrans = pat->transitions[i])
2688	{
2689	merge_state_result *to1_res = sinfo1->to_states[i].res;
2690	merge_state_result *to2_res = sinfo2->to_states[i].res;
2691	merge_pattern_info *to_pat = ptrans->to;
2692	gcc_assert (to2_res && to2_res->pattern == to_pat);
2693	if (!to1_res || to1_res->pattern != to_pat)
2694	return false;
2695	if (to2_res->root
2696	&& !merge_relative_positions (roota: &root1, a: to1_res->root,
2697	rootb: root2, b: to2_res->root))
2698	return false;
2699	/* Match the parameters that TO1_RES passes to TO_PAT with the
2700	parameters that PAT passes to TO_PAT. */
2701	update_parameters (to&: to1_res->params, from: to_pat->params);
2702	for (unsigned int j = 0; j < to1_res->params.length (); ++j)
2703	{
2704	const parameter &param1 = to1_res->params[j];
2705	const parameter &param2 = ptrans->params[j];
2706	gcc_assert (!param1.is_param);
2707	if (param2.is_param)
2708	{
2709	if (!set_parameter (params&: params1, id: param2.value, value: param1))
2710	return false;
2711	}
2712	else if (param1 != param2)
2713	{
2714	unsigned int id;
2715	if (!add_parameter (params1, params2,
2716	param1, param2, start: start_param, res: &id))
2717	return false;
2718	/* Record that PAT should now pass parameter ID to TO_PAT,
2719	instead of the current contents of *PARAM2. We only
2720	make the change if the rest of the match succeeds. */
2721	pending_params.safe_push
2722	(obj: pending_param (&ptrans->params[j], id));
2723	}
2724	}
2725	}
2726
2727	unsigned int param_test = pat->param_test;
2728	unsigned int param_transition = pat->param_transition;
2729	bool param_test_p = pat->param_test_p;
2730	bool param_transition_p = pat->param_transition_p;
2731
2732	/* If the tests don't match exactly, try to parameterize them. */
2733	parameter new_param1, new_param2;
2734	if (!compatible_tests_p (a: d1->test, b: d2->test, parama: &new_param1, paramb: &new_param2))
2735	gcc_unreachable ();
2736	if (new_param1.type != parameter::UNSET)
2737	{
2738	/* If the test has not already been parameterized, all existing
2739	matches use constant NEW_PARAM2. */
2740	if (param_test_p)
2741	{
2742	if (!set_parameter (params&: params1, id: param_test, value: new_param1))
2743	return false;
2744	}
2745	else if (new_param1 != new_param2)
2746	{
2747	if (!add_parameter (params1, params2, param1: new_param1, param2: new_param2,
2748	start: start_param, res: &param_test))
2749	return false;
2750	param_test_p = true;
2751	}
2752	}
2753
2754	/* Match the transitions. */
2755	transition *trans1 = d1->first;
2756	transition *trans2 = d2->first;
2757	for (unsigned int i = 0; i < num_transitions; ++i)
2758	{
2759	if (param_transition_p || trans1->labels != trans2->labels)
2760	{
2761	/* We can only generalize a single transition with a single
2762	label. */
2763	if (num_transitions != 1
2764	|| trans1->labels.length () != 1
2765	|| trans2->labels.length () != 1)
2766	return false;
2767
2768	/* Although we can match wide-int fields, in practice it leads
2769	to some odd results for const_vectors. We end up
2770	parameterizing the first N const_ints of the vector
2771	and then (once we reach the maximum number of parameters)
2772	we go on to match the other elements exactly. */
2773	if (d1->test.kind == rtx_test::WIDE_INT_FIELD)
2774	return false;
2775
2776	/* See whether the label has a generalizable type. */
2777	parameter::type_enum param_type
2778	= transition_parameter_type (kind: d1->test.kind);
2779	if (param_type == parameter::UNSET)
2780	return false;
2781
2782	/* Match the labels using parameters. */
2783	new_param1 = parameter (param_type, false, trans1->labels[0]);
2784	if (param_transition_p)
2785	{
2786	if (!set_parameter (params&: params1, id: param_transition, value: new_param1))
2787	return false;
2788	}
2789	else
2790	{
2791	new_param2 = parameter (param_type, false, trans2->labels[0]);
2792	if (!add_parameter (params1, params2, param1: new_param1, param2: new_param2,
2793	start: start_param, res: &param_transition))
2794	return false;
2795	param_transition_p = true;
2796	}
2797	}
2798	trans1 = trans1->next;
2799	trans2 = trans2->next;
2800	}
2801
2802	/* Set any unset parameters to their default values. This occurs if some
2803	other state needed something to be parameterized in order to match SINFO2,
2804	but SINFO1 on its own does not. */
2805	for (unsigned int i = 0; i < params1.length (); ++i)
2806	if (params1[i].type == parameter::UNSET)
2807	params1[i] = params2[i];
2808
2809	/* The match was successful. Commit all pending changes to PAT. */
2810	update_parameters (to&: pat->params, from: params2);
2811	{
2812	pending_param *pp;
2813	unsigned int i;
2814	FOR_EACH_VEC_ELT (pending_params, i, pp)
2815	*pp->first = parameter (pp->first->type, true, pp->second);
2816	}
2817	pat->param_test = param_test;
2818	pat->param_transition = param_transition;
2819	pat->param_test_p = param_test_p;
2820	pat->param_transition_p = param_transition_p;
2821
2822	/* Record the match of SINFO1. */
2823	merge_state_result *new_res1 = new merge_state_result (pat, root1,
2824	sinfo1->res);
2825	new_res1->params.splice (src: params1);
2826	sinfo1->res = new_res1;
2827	return true;
2828	}
2829
2830	/* The number of states that were removed by calling pattern routines. */
2831	static unsigned int pattern_use_states;
2832
2833	/* The number of states used while defining pattern routines. */
2834	static unsigned int pattern_def_states;
2835
2836	/* Information used while constructing a use or definition of a pattern
2837	routine. */
2838	struct create_pattern_info
2839	{
2840	/* The routine itself. */
2841	pattern_routine *routine;
2842
2843	/* The first unclaimed return value for this particular use or definition.
2844	We walk the substates of uses and definitions in the same order
2845	so each return value always refers to the same position within
2846	the pattern. */
2847	unsigned int next_result;
2848	};
2849
2850	static void populate_pattern_routine (create_pattern_info *,
2851	merge_state_info *, state *,
2852	const vec <parameter> &);
2853
2854	/* SINFO matches a pattern for which we've decided to create a C routine.
2855	Return a decision that performs a call to the pattern routine,
2856	but leave the caller to add the transitions to it. Initialize CPI
2857	for this purpose. Also create a definition for the pattern routine,
2858	if it doesn't already have one.
2859
2860	PARAMS are the parameters that SINFO passes to its pattern. */
2861
2862	static decision *
2863	init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo,
2864	const vec <parameter> &params)
2865	{
2866	state *s = sinfo->s;
2867	merge_state_result *res = sinfo->res;
2868	merge_pattern_info *pat = res->pattern;
2869	cpi->routine = pat->routine;
2870	if (!cpi->routine)
2871	{
2872	/* We haven't defined the pattern routine yet, so create
2873	a definition now. */
2874	pattern_routine *routine = new pattern_routine;
2875	pat->routine = routine;
2876	cpi->routine = routine;
2877	routine->s = new state;
2878	routine->insn_p = false;
2879	routine->pnum_clobbers_p = false;
2880
2881	/* Create an "idempotent" mapping of parameter I to parameter I.
2882	Also record the C type of each parameter to the routine. */
2883	auto_vec <parameter, MAX_PATTERN_PARAMS> def_params;
2884	for (unsigned int i = 0; i < pat->params.length (); ++i)
2885	{
2886	def_params.quick_push (obj: parameter (pat->params[i].type, true, i));
2887	routine->param_types.quick_push (obj: pat->params[i].type);
2888	}
2889
2890	/* Any of the states that match the pattern could be used to
2891	create the routine definition. We might as well use SINFO
2892	since it's already to hand. This means that all positions
2893	in the definition will be relative to RES->root. */
2894	routine->pos = res->root;
2895	cpi->next_result = 0;
2896	populate_pattern_routine (cpi, sinfo, routine->s, def_params);
2897	gcc_assert (cpi->next_result == pat->num_results);
2898
2899	/* Add the routine to the global list, after the subroutines
2900	that it calls. */
2901	routine->pattern_id = patterns.length ();
2902	patterns.safe_push (obj: routine);
2903	}
2904
2905	/* Create a decision to call the routine, passing PARAMS to it. */
2906	pattern_use *use = new pattern_use;
2907	use->routine = pat->routine;
2908	use->params.splice (src: params);
2909	decision *d = new decision (rtx_test::pattern (pos: res->root, pattern: use));
2910
2911	/* If the original decision could use an element of operands[] instead
2912	of an rtx variable, try to transfer it to the new decision. */
2913	if (s->first->test.pos && res->root == s->first->test.pos)
2914	d->test.pos_operand = s->first->test.pos_operand;
2915
2916	cpi->next_result = 0;
2917	return d;
2918	}
2919
2920	/* Make S return the next unclaimed pattern routine result for CPI. */
2921
2922	static void
2923	add_pattern_acceptance (create_pattern_info *cpi, state *s)
2924	{
2925	acceptance_type acceptance;
2926	acceptance.type = SUBPATTERN;
2927	acceptance.partial_p = false;
2928	acceptance.u.full.code = cpi->next_result;
2929	add_decision (from: s, test: rtx_test::accept (acceptance), labels: true, optional: false);
2930	cpi->next_result += 1;
2931	}
2932
2933	/* Initialize new empty state NEWS so that it implements SINFO's pattern
2934	(here referred to as "P"). P may be the top level of a pattern routine
2935	or a subpattern that should be inlined into its parent pattern's routine
2936	(as per same_pattern_p). The choice of SINFO for a top-level pattern is
2937	arbitrary; it could be any of the states that use P. The choice for
2938	subpatterns follows the choice for the parent pattern.
2939
2940	PARAMS gives the value of each parameter to P in terms of the parameters
2941	to the top-level pattern. If P itself is the top level pattern, PARAMS[I]
2942	is always "parameter (TYPE, true, I)". */
2943
2944	static void
2945	populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo,
2946	state *news, const vec <parameter> &params)
2947	{
2948	pattern_def_states += 1;
2949
2950	decision *d = sinfo->s->singleton ();
2951	merge_pattern_info *pat = sinfo->res->pattern;
2952	pattern_routine *routine = cpi->routine;
2953
2954	/* Create a copy of D's test for the pattern routine and generalize it
2955	as appropriate. */
2956	decision *newd = new decision (d->test);
2957	gcc_assert (newd->test.pos_operand >= 0
2958	|| !newd->test.pos
2959	|| common_position (newd->test.pos,
2960	routine->pos) == routine->pos);
2961	if (pat->param_test_p)
2962	{
2963	const parameter &param = params[pat->param_test];
2964	switch (newd->test.kind)
2965	{
2966	case rtx_test::PREDICATE:
2967	newd->test.u.predicate.mode_is_param = param.is_param;
2968	newd->test.u.predicate.mode = param.value;
2969	break;
2970
2971	case rtx_test::SAVED_CONST_INT:
2972	newd->test.u.integer.is_param = param.is_param;
2973	newd->test.u.integer.value = param.value;
2974	break;
2975
2976	default:
2977	gcc_unreachable ();
2978	break;
2979	}
2980	}
2981	if (d->test.kind == rtx_test::C_TEST)
2982	routine->insn_p = true;
2983	else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS)
2984	routine->pnum_clobbers_p = true;
2985	news->push_back (r: newd);
2986
2987	/* Fill in the transitions of NEWD. */
2988	unsigned int i = 0;
2989	for (transition *trans = d->first; trans; trans = trans->next)
2990	{
2991	/* Create a new state to act as the target of the new transition. */
2992	state *to_news = new state;
2993	if (merge_pattern_transition *ptrans = pat->transitions[i])
2994	{
2995	/* The pattern hasn't finished matching yet. Get the target
2996	pattern and the corresponding target state of SINFO. */
2997	merge_pattern_info *to_pat = ptrans->to;
2998	merge_state_info *to = sinfo->to_states + i;
2999	gcc_assert (to->res->pattern == to_pat);
3000	gcc_assert (ptrans->params.length () == to_pat->params.length ());
3001
3002	/* Express the parameters to TO_PAT in terms of the parameters
3003	to the top-level pattern. */
3004	auto_vec <parameter, MAX_PATTERN_PARAMS> to_params;
3005	for (unsigned int j = 0; j < ptrans->params.length (); ++j)
3006	{
3007	const parameter &param = ptrans->params[j];
3008	to_params.quick_push (obj: param.is_param
3009	? params[param.value]
3010	: param);
3011	}
3012
3013	if (same_pattern_p (pat1: pat, pat2: to_pat))
3014	/* TO_PAT is part of the current routine, so just recurse. */
3015	populate_pattern_routine (cpi, sinfo: to, news: to_news, params: to_params);
3016	else
3017	{
3018	/* TO_PAT should be matched by calling a separate routine. */
3019	create_pattern_info sub_cpi;
3020	decision *subd = init_pattern_use (cpi: &sub_cpi, sinfo: to, params: to_params);
3021	routine->insn_p |= sub_cpi.routine->insn_p;
3022	routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p;
3023
3024	/* Add the pattern routine call to the new target state. */
3025	to_news->push_back (r: subd);
3026
3027	/* Add a transition for each successful call result. */
3028	for (unsigned int j = 0; j < to_pat->num_results; ++j)
3029	{
3030	state *res = new state;
3031	add_pattern_acceptance (cpi, s: res);
3032	subd->push_back (r: new transition (j, res, false));
3033	}
3034	}
3035	}
3036	else
3037	/* This transition corresponds to a successful match. */
3038	add_pattern_acceptance (cpi, s: to_news);
3039
3040	/* Create the transition itself, generalizing as necessary. */
3041	transition *new_trans = new transition (trans->labels, to_news,
3042	trans->optional);
3043	if (pat->param_transition_p)
3044	{
3045	const parameter &param = params[pat->param_transition];
3046	new_trans->is_param = param.is_param;
3047	new_trans->labels[0] = param.value;
3048	}
3049	newd->push_back (r: new_trans);
3050	i += 1;
3051	}
3052	}
3053
3054	/* USE is a decision that calls a pattern routine and SINFO is part of the
3055	original state tree that the call is supposed to replace. Add the
3056	transitions for SINFO and its substates to USE. */
3057
3058	static void
3059	populate_pattern_use (create_pattern_info *cpi, decision *use,
3060	merge_state_info *sinfo)
3061	{
3062	pattern_use_states += 1;
3063	gcc_assert (!sinfo->merged_p);
3064	sinfo->merged_p = true;
3065	merge_state_result *res = sinfo->res;
3066	merge_pattern_info *pat = res->pattern;
3067	decision *d = sinfo->s->singleton ();
3068	unsigned int i = 0;
3069	for (transition *trans = d->first; trans; trans = trans->next)
3070	{
3071	if (pat->transitions[i])
3072	/* The target state is also part of the pattern. */
3073	populate_pattern_use (cpi, use, sinfo: sinfo->to_states + i);
3074	else
3075	{
3076	/* The transition corresponds to a successful return from the
3077	pattern routine. */
3078	use->push_back (r: new transition (cpi->next_result, trans->to, false));
3079	cpi->next_result += 1;
3080	}
3081	i += 1;
3082	}
3083	}
3084
3085	/* We have decided to replace SINFO's state with a call to a pattern
3086	routine. Make the change, creating a definition of the pattern routine
3087	if it doesn't have one already. */
3088
3089	static void
3090	use_pattern (merge_state_info *sinfo)
3091	{
3092	merge_state_result *res = sinfo->res;
3093	merge_pattern_info *pat = res->pattern;
3094	state *s = sinfo->s;
3095
3096	/* The pattern may have acquired new parameters after it was matched
3097	against SINFO. Update the parameters that SINFO passes accordingly. */
3098	update_parameters (to&: res->params, from: pat->params);
3099
3100	create_pattern_info cpi;
3101	decision *d = init_pattern_use (cpi: &cpi, sinfo, params: res->params);
3102	populate_pattern_use (cpi: &cpi, use: d, sinfo);
3103	s->release ();
3104	s->push_back (r: d);
3105	}
3106
3107	/* Look through the state trees in STATES for common patterns and
3108	split them into subroutines. */
3109
3110	static void
3111	split_out_patterns (vec <merge_state_info> &states)
3112	{
3113	unsigned int first_transition = states.length ();
3114	hash_table <test_pattern_hasher> hashtab (128);
3115	/* Stage 1: Create an order in which parent states come before their child
3116	states and in which sibling states are at consecutive locations.
3117	Having consecutive sibling states allows merge_state_info to have
3118	a single to_states pointer. */
3119	for (unsigned int i = 0; i < states.length (); ++i)
3120	for (decision *d = states[i].s->first; d; d = d->next)
3121	for (transition *trans = d->first; trans; trans = trans->next)
3122	{
3123	states.safe_push (obj: trans->to);
3124	states[i].num_transitions += 1;
3125	}
3126	/* Stage 2: Now that the addresses are stable, set up the to_states
3127	pointers. Look for states that might be merged and enter them
3128	into the hash table. */
3129	for (unsigned int i = 0; i < states.length (); ++i)
3130	{
3131	merge_state_info *sinfo = &states[i];
3132	if (sinfo->num_transitions)
3133	{
3134	sinfo->to_states = &states[first_transition];
3135	first_transition += sinfo->num_transitions;
3136	}
3137	/* For simplicity, we only try to merge states that have a single
3138	decision. This is in any case the best we can do for peephole2,
3139	since whether a peephole2 ACCEPT succeeds or not depends on the
3140	specific peephole2 pattern (which is unique to each ACCEPT
3141	and so couldn't be shared between states). */
3142	if (decision *d = sinfo->s->singleton ())
3143	/* ACCEPT states are unique, so don't even try to merge them. */
3144	if (d->test.kind != rtx_test::ACCEPT
3145	&& (pattern_have_num_clobbers_p
3146	|| d->test.kind != rtx_test::HAVE_NUM_CLOBBERS)
3147	&& (pattern_c_test_p
3148	|| d->test.kind != rtx_test::C_TEST))
3149	{
3150	merge_state_info **slot = hashtab.find_slot (value: sinfo, insert: INSERT);
3151	sinfo->prev_same_test = *slot;
3152	*slot = sinfo;
3153	}
3154	}
3155	/* Stage 3: Walk backwards through the list of states and try to merge
3156	them. This is a greedy, bottom-up match; parent nodes can only start
3157	a new leaf pattern if they fail to match when combined with all child
3158	nodes that have matching patterns.
3159
3160	For each state we keep a list of potential matches, with each
3161	potential match being larger (and deeper) than the next match in
3162	the list. The final element in the list is a leaf pattern that
3163	matches just a single state.
3164
3165	Each candidate pattern created in this loop is unique -- it won't
3166	have been seen by an earlier iteration. We try to match each pattern
3167	with every state that appears earlier in STATES.
3168
3169	Because the patterns created in the loop are unique, any state
3170	that already has a match must have a final potential match that
3171	is different from any new leaf pattern. Therefore, when matching
3172	leaf patterns, we need only consider states whose list of matches
3173	is empty.
3174
3175	The non-leaf patterns that we try are as deep as possible
3176	and are an extension of the state's previous best candidate match (PB).
3177	We need only consider states whose current potential match is also PB;
3178	any states that don't match as much as PB cannnot match the new pattern,
3179	while any states that already match more than PB must be different from
3180	the new pattern. */
3181	for (unsigned int i2 = states.length (); i2-- > 0; )
3182	{
3183	merge_state_info *sinfo2 = &states[i2];
3184
3185	/* Enforce the bottom-upness of the match: remove matches with later
3186	states if SINFO2's child states ended up finding a better match. */
3187	prune_invalid_results (sinfo: sinfo2);
3188
3189	/* Do nothing if the state doesn't match a later one and if there are
3190	no earlier states it could match. */
3191	if (!sinfo2->res && !sinfo2->prev_same_test)
3192	continue;
3193
3194	merge_state_result *res2 = sinfo2->res;
3195	decision *d2 = sinfo2->s->singleton ();
3196	position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0);
3197	unsigned int num_transitions = sinfo2->num_transitions;
3198
3199	/* If RES2 is null then SINFO2's test in isolation has not been seen
3200	before. First try matching that on its own. */
3201	if (!res2)
3202	{
3203	merge_pattern_info *new_pat
3204	= new merge_pattern_info (num_transitions);
3205	merge_state_result *new_res2
3206	= new merge_state_result (new_pat, root2, res2);
3207	sinfo2->res = new_res2;
3208
3209	new_pat->num_statements = !d2->test.single_outcome_p ();
3210	new_pat->num_results = num_transitions;
3211	bool matched_p = false;
3212	/* Look for states that don't currently match anything but
3213	can be made to match SINFO2 on its own. */
3214	for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3215	sinfo1 = sinfo1->prev_same_test)
3216	if (!sinfo1->res && merge_patterns (sinfo1, sinfo2))
3217	matched_p = true;
3218	if (!matched_p)
3219	{
3220	/* No other states match. */
3221	sinfo2->res = res2;
3222	delete new_pat;
3223	delete new_res2;
3224	continue;
3225	}
3226	else
3227	res2 = new_res2;
3228	}
3229
3230	/* Keep the existing pattern if it's as good as anything we'd
3231	create for SINFO2. */
3232	if (complete_result_p (pat: res2->pattern, sinfo: sinfo2))
3233	{
3234	res2->pattern->num_users += 1;
3235	continue;
3236	}
3237
3238	/* Create a new pattern for SINFO2. */
3239	merge_pattern_info *new_pat = new merge_pattern_info (num_transitions);
3240	merge_state_result *new_res2
3241	= new merge_state_result (new_pat, root2, res2);
3242	sinfo2->res = new_res2;
3243
3244	/* Fill in details about the pattern. */
3245	new_pat->num_statements = !d2->test.single_outcome_p ();
3246	new_pat->num_results = 0;
3247	for (unsigned int j = 0; j < num_transitions; ++j)
3248	if (merge_state_result *to_res = sinfo2->to_states[j].res)
3249	{
3250	/* Count the target state as part of this pattern.
3251	First update the root position so that it can reach
3252	the target state's root. */
3253	if (to_res->root)
3254	{
3255	if (new_res2->root)
3256	new_res2->root = common_position (pos1: new_res2->root,
3257	pos2: to_res->root);
3258	else
3259	new_res2->root = to_res->root;
3260	}
3261	merge_pattern_info *to_pat = to_res->pattern;
3262	merge_pattern_transition *ptrans
3263	= new merge_pattern_transition (to_pat);
3264
3265	/* TO_PAT may have acquired more parameters when matching
3266	states earlier in STATES than TO_RES's, but the list is
3267	now final. Make sure that TO_RES is up to date. */
3268	update_parameters (to&: to_res->params, from: to_pat->params);
3269
3270	/* Start out by assuming that every user of NEW_PAT will
3271	want to pass the same (constant) parameters as TO_RES. */
3272	update_parameters (to&: ptrans->params, from: to_res->params);
3273
3274	new_pat->transitions[j] = ptrans;
3275	new_pat->num_statements += to_pat->num_statements;
3276	new_pat->num_results += to_pat->num_results;
3277	}
3278	else
3279	/* The target state doesn't match anything and so is not part
3280	of the pattern. */
3281	new_pat->num_results += 1;
3282
3283	/* See if any earlier states that match RES2's pattern also match
3284	NEW_PAT. */
3285	bool matched_p = false;
3286	for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1;
3287	sinfo1 = sinfo1->prev_same_test)
3288	{
3289	prune_invalid_results (sinfo: sinfo1);
3290	if (sinfo1->res
3291	&& sinfo1->res->pattern == res2->pattern
3292	&& merge_patterns (sinfo1, sinfo2))
3293	matched_p = true;
3294	}
3295	if (!matched_p)
3296	{
3297	/* Nothing else matches NEW_PAT, so go back to the previous
3298	pattern (possibly just a single-state one). */
3299	sinfo2->res = res2;
3300	delete new_pat;
3301	delete new_res2;
3302	}
3303	/* Assume that SINFO2 will use RES. At this point we don't know
3304	whether earlier states that match the same pattern will use
3305	that match or a different one. */
3306	sinfo2->res->pattern->num_users += 1;
3307	}
3308	/* Step 4: Finalize the choice of pattern for each state, ignoring
3309	patterns that were only used once. Update each pattern's size
3310	so that it doesn't include subpatterns that are going to be split
3311	out into subroutines. */
3312	for (unsigned int i = 0; i < states.length (); ++i)
3313	{
3314	merge_state_info *sinfo = &states[i];
3315	merge_state_result *res = sinfo->res;
3316	/* Wind past patterns that are only used by SINFO. */
3317	while (res && res->pattern->num_users == 1)
3318	{
3319	res = res->prev;
3320	sinfo->res = res;
3321	if (res)
3322	res->pattern->num_users += 1;
3323	}
3324	if (!res)
3325	continue;
3326
3327	/* We have a shared pattern and are now committed to the match. */
3328	merge_pattern_info *pat = res->pattern;
3329	gcc_assert (valid_result_p (pat, sinfo));
3330
3331	if (!pat->complete_p)
3332	{
3333	/* Look for subpatterns that are going to be split out and remove
3334	them from the number of statements. */
3335	for (unsigned int j = 0; j < sinfo->num_transitions; ++j)
3336	if (merge_pattern_transition *ptrans = pat->transitions[j])
3337	{
3338	merge_pattern_info *to_pat = ptrans->to;
3339	if (!same_pattern_p (pat1: pat, pat2: to_pat))
3340	pat->num_statements -= to_pat->num_statements;
3341	}
3342	pat->complete_p = true;
3343	}
3344	}
3345	/* Step 5: Split out the patterns. */
3346	for (unsigned int i = 0; i < states.length (); ++i)
3347	{
3348	merge_state_info *sinfo = &states[i];
3349	merge_state_result *res = sinfo->res;
3350	if (!sinfo->merged_p && res && useful_pattern_p (pat: res->pattern))
3351	use_pattern (sinfo);
3352	}
3353	fprintf (stderr, format: "Shared %d out of %d states by creating %d new states,"
3354	" saving %d\n",
3355	pattern_use_states, states.length (), pattern_def_states,
3356	pattern_use_states - pattern_def_states);
3357	}
3358
3359	/* Information about a state tree that we're considering splitting into a
3360	subroutine. */
3361	struct state_size
3362	{
3363	/* The number of pseudo-statements in the state tree. */
3364	unsigned int num_statements;
3365
3366	/* The approximate number of nested "if" and "switch" statements that
3367	would be required if control could fall through to a later state. */
3368	unsigned int depth;
3369	};
3370
3371	/* Pairs a transition with information about its target state. */
3372	typedef std::pair <transition *, state_size> subroutine_candidate;
3373
3374	/* Sort two subroutine_candidates so that the one with the largest
3375	number of statements comes last. */
3376
3377	static int
3378	subroutine_candidate_cmp (const void *a, const void *b)
3379	{
3380	return int (((const subroutine_candidate *) a)->second.num_statements
3381	- ((const subroutine_candidate *) b)->second.num_statements);
3382	}
3383
3384	/* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new
3385	state that performs a subroutine call to S. */
3386
3387	static state *
3388	create_subroutine (routine_type type, state *s, vec <state *> &procs)
3389	{
3390	procs.safe_push (obj: s);
3391	acceptance_type acceptance;
3392	acceptance.type = type;
3393	acceptance.partial_p = true;
3394	acceptance.u.subroutine_id = procs.length ();
3395	state *news = new state;
3396	add_decision (from: news, test: rtx_test::accept (acceptance), labels: true, optional: false);
3397	return news;
3398	}
3399
3400	/* Walk state tree S, of type TYPE, and look for subtrees that would be
3401	better split into subroutines. Accumulate all such subroutines in PROCS.
3402	Return the size of the new state tree (excluding subroutines). */
3403
3404	static state_size
3405	find_subroutines (routine_type type, state *s, vec <state *> &procs)
3406	{
3407	auto_vec <subroutine_candidate, 16> candidates;
3408	state_size size;
3409	size.num_statements = 0;
3410	size.depth = 0;
3411	for (decision *d = s->first; d; d = d->next)
3412	{
3413	if (!d->test.single_outcome_p ())
3414	size.num_statements += 1;
3415	for (transition *trans = d->first; trans; trans = trans->next)
3416	{
3417	/* Keep chains of simple decisions together if we know that no
3418	change of position is required. We'll output this chain as a
3419	single "if" statement, so it counts as a single nesting level. */
3420	if (d->test.pos && d->if_statement_p ())
3421	for (;;)
3422	{
3423	decision *newd = trans->to->singleton ();
3424	if (!newd
3425	|| (newd->test.pos
3426	&& newd->test.pos_operand < 0
3427	&& newd->test.pos != d->test.pos)
3428	|| !newd->if_statement_p ())
3429	break;
3430	if (!newd->test.single_outcome_p ())
3431	size.num_statements += 1;
3432	trans = newd->singleton ();
3433	if (newd->test.kind == rtx_test::SET_OP
3434	|| newd->test.kind == rtx_test::ACCEPT)
3435	break;
3436	}
3437	/* The target of TRANS is a subroutine candidate. First recurse
3438	on it to see how big it is after subroutines have been
3439	split out. */
3440	state_size to_size = find_subroutines (type, s: trans->to, procs);
3441	if (d->next && to_size.depth > MAX_DEPTH)
3442	/* Keeping the target state in the same routine would lead
3443	to an excessive nesting of "if" and "switch" statements.
3444	Split it out into a subroutine so that it can use
3445	inverted tests that return early on failure. */
3446	trans->to = create_subroutine (type, s: trans->to, procs);
3447	else
3448	{
3449	size.num_statements += to_size.num_statements;
3450	if (to_size.num_statements < MIN_NUM_STATEMENTS)
3451	/* The target state is too small to be worth splitting.
3452	Keep it in the same routine as S. */
3453	size.depth = MAX (size.depth, to_size.depth);
3454	else
3455	/* Assume for now that we'll keep the target state in the
3456	same routine as S, but record it as a subroutine candidate
3457	if S grows too big. */
3458	candidates.safe_push (obj: subroutine_candidate (trans, to_size));
3459	}
3460	}
3461	}
3462	if (size.num_statements > MAX_NUM_STATEMENTS)
3463	{
3464	/* S is too big. Sort the subroutine candidates so that bigger ones
3465	are nearer the end. */
3466	candidates.qsort (subroutine_candidate_cmp);
3467	while (!candidates.is_empty ()
3468	&& size.num_statements > MAX_NUM_STATEMENTS)
3469	{
3470	/* Peel off a candidate and force it into a subroutine. */
3471	subroutine_candidate cand = candidates.pop ();
3472	size.num_statements -= cand.second.num_statements;
3473	cand.first->to = create_subroutine (type, s: cand.first->to, procs);
3474	}
3475	}
3476	/* Update the depth for subroutine candidates that we decided not to
3477	split out. */
3478	for (unsigned int i = 0; i < candidates.length (); ++i)
3479	size.depth = MAX (size.depth, candidates[i].second.depth);
3480	size.depth += 1;
3481	return size;
3482	}
3483
3484	/* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */
3485
3486	static bool
3487	safe_predicate_mode (const struct pred_data *pred, machine_mode mode)
3488	{
3489	/* Scalar integer constants have VOIDmode. */
3490	if (GET_MODE_CLASS (mode) == MODE_INT
3491	&& (pred->codes[CONST_INT]
3492	|| pred->codes[CONST_DOUBLE]
3493	|| pred->codes[CONST_WIDE_INT]
3494	|| pred->codes[LABEL_REF]))
3495	return false;
3496
3497	return !pred->special && mode != VOIDmode;
3498	}
3499
3500	/* Fill CODES with the set of codes that could be matched by PRED. */
3501
3502	static void
3503	get_predicate_codes (const struct pred_data *pred, int_set *codes)
3504	{
3505	for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i)
3506	if (!pred || pred->codes[i])
3507	codes->safe_push (obj: i);
3508	}
3509
3510	/* Return true if the first path through D1 tests the same thing as D2. */
3511
3512	static bool
3513	has_same_test_p (decision *d1, decision *d2)
3514	{
3515	do
3516	{
3517	if (d1->test == d2->test)
3518	return true;
3519	d1 = d1->first->to->first;
3520	}
3521	while (d1);
3522	return false;
3523	}
3524
3525	/* Return true if D1 and D2 cannot match the same rtx. All states reachable
3526	from D2 have single decisions and all those decisions have single
3527	transitions. */
3528
3529	static bool
3530	mutually_exclusive_p (decision *d1, decision *d2)
3531	{
3532	/* If one path through D1 fails to test the same thing as D2, assume
3533	that D2's test could be true for D1 and look for a later, more useful,
3534	test. This isn't as expensive as it looks in practice. */
3535	while (!has_same_test_p (d1, d2))
3536	{
3537	d2 = d2->singleton ()->to->singleton ();
3538	if (!d2)
3539	return false;
3540	}
3541	if (d1->test == d2->test)
3542	{
3543	/* Look for any transitions from D1 that have the same labels as
3544	the transition from D2. */
3545	transition *trans2 = d2->singleton ();
3546	for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3547	{
3548	int_set::iterator i1 = trans1->labels.begin ();
3549	int_set::iterator end1 = trans1->labels.end ();
3550	int_set::iterator i2 = trans2->labels.begin ();
3551	int_set::iterator end2 = trans2->labels.end ();
3552	while (i1 != end1 && i2 != end2)
3553	if (*i1 < *i2)
3554	++i1;
3555	else if (*i2 < *i1)
3556	++i2;
3557	else
3558	{
3559	/* TRANS1 has some labels in common with TRANS2. Assume
3560	that D1 and D2 could match the same rtx if the target
3561	of TRANS1 could match the same rtx as D2. */
3562	for (decision *subd1 = trans1->to->first;
3563	subd1; subd1 = subd1->next)
3564	if (!mutually_exclusive_p (d1: subd1, d2))
3565	return false;
3566	break;
3567	}
3568	}
3569	return true;
3570	}
3571	for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3572	for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next)
3573	if (!mutually_exclusive_p (d1: subd1, d2))
3574	return false;
3575	return true;
3576	}
3577
3578	/* Try to merge S2's decision into D1, given that they have the same test.
3579	Fail only if EXCLUDE is nonnull and the new transition would have the
3580	same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2
3581	and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null
3582	if the merge is complete. */
3583
3584	static bool
3585	merge_into_decision (decision *d1, state *s2, const int_set *exclude,
3586	state **next_s1, state **next_s2,
3587	const int_set **next_exclude)
3588	{
3589	decision *d2 = s2->singleton ();
3590	transition *trans2 = d2->singleton ();
3591
3592	/* Get a list of the transitions that intersect TRANS2. */
3593	auto_vec <transition *, 32> intersecting;
3594	for (transition *trans1 = d1->first; trans1; trans1 = trans1->next)
3595	{
3596	int_set::iterator i1 = trans1->labels.begin ();
3597	int_set::iterator end1 = trans1->labels.end ();
3598	int_set::iterator i2 = trans2->labels.begin ();
3599	int_set::iterator end2 = trans2->labels.end ();
3600	bool trans1_is_subset = true;
3601	bool trans2_is_subset = true;
3602	bool intersect_p = false;
3603	while (i1 != end1 && i2 != end2)
3604	if (*i1 < *i2)
3605	{
3606	trans1_is_subset = false;
3607	++i1;
3608	}
3609	else if (*i2 < *i1)
3610	{
3611	trans2_is_subset = false;
3612	++i2;
3613	}
3614	else
3615	{
3616	intersect_p = true;
3617	++i1;
3618	++i2;
3619	}
3620	if (i1 != end1)
3621	trans1_is_subset = false;
3622	if (i2 != end2)
3623	trans2_is_subset = false;
3624	if (trans1_is_subset && trans2_is_subset)
3625	{
3626	/* There's already a transition that matches exactly.
3627	Merge the target states. */
3628	trans1->optional &= trans2->optional;
3629	*next_s1 = trans1->to;
3630	*next_s2 = trans2->to;
3631	*next_exclude = 0;
3632	return true;
3633	}
3634	if (trans2_is_subset)
3635	{
3636	/* TRANS1 has all the labels that TRANS2 needs. Merge S2 into
3637	the target of TRANS1, but (to avoid infinite recursion)
3638	make sure that we don't end up creating another transition
3639	like TRANS1. */
3640	*next_s1 = trans1->to;
3641	*next_s2 = s2;
3642	*next_exclude = &trans1->labels;
3643	return true;
3644	}
3645	if (intersect_p)
3646	intersecting.safe_push (obj: trans1);
3647	}
3648
3649	if (intersecting.is_empty ())
3650	{
3651	/* No existing labels intersect the new ones. We can just add
3652	TRANS2 itself. */
3653	d1->push_back (r: d2->release ());
3654	*next_s1 = 0;
3655	*next_s2 = 0;
3656	*next_exclude = 0;
3657	return true;
3658	}
3659
3660	/* Take the union of the labels in INTERSECTING and TRANS2. Store the
3661	result in COMBINED and use NEXT as a temporary. */
3662	int_set tmp1 = trans2->labels, tmp2;
3663	int_set *combined = &tmp1, *next = &tmp2;
3664	for (unsigned int i = 0; i < intersecting.length (); ++i)
3665	{
3666	transition *trans1 = intersecting[i];
3667	next->truncate (size: 0);
3668	next->safe_grow (len: trans1->labels.length () + combined->length (), exact: true);
3669	int_set::iterator end
3670	= std::set_union (first1: trans1->labels.begin (), last1: trans1->labels.end (),
3671	first2: combined->begin (), last2: combined->end (),
3672	result: next->begin ());
3673	next->truncate (size: end - next->begin ());
3674	std::swap (a&: next, b&: combined);
3675	}
3676
3677	/* Stop now if we've been told not to create a transition with these
3678	labels. */
3679	if (exclude && *combined == *exclude)
3680	return false;
3681
3682	/* Get the transition that should carry the new labels. */
3683	transition *new_trans = intersecting[0];
3684	if (intersecting.length () == 1)
3685	{
3686	/* We're merging with one existing transition whose labels are a
3687	subset of those required. If both transitions are optional,
3688	we can just expand the set of labels so that it's suitable
3689	for both transitions. It isn't worth preserving the original
3690	transitions since we know that they can't be merged; we would
3691	need to backtrack to S2 if TRANS1->to fails. In contrast,
3692	we might be able to merge the targets of the transitions
3693	without any backtracking.
3694
3695	If instead the existing transition is not optional, ensure that
3696	all target decisions are suitably protected. Some decisions
3697	might already have a more specific requirement than NEW_TRANS,
3698	in which case there's no point testing NEW_TRANS as well. E.g. this
3699	would have happened if a test for an (eq ...) rtx had been
3700	added to a decision that tested whether the code is suitable
3701	for comparison_operator. The original comparison_operator
3702	transition would have been non-optional and the (eq ...) test
3703	would be performed by a second decision in the target of that
3704	transition.
3705
3706	The remaining case -- keeping the original optional transition
3707	when adding a non-optional TRANS2 -- is a wash. Preserving
3708	the optional transition only helps if we later merge another
3709	state S3 that is mutually exclusive with S2 and whose labels
3710	belong to *COMBINED - TRANS1->labels. We can then test the
3711	original NEW_TRANS and S3 in the same decision. We keep the
3712	optional transition around for that case, but it occurs very
3713	rarely. */
3714	gcc_assert (new_trans->labels != *combined);
3715	if (!new_trans->optional || !trans2->optional)
3716	{
3717	decision *start = 0;
3718	for (decision *end = new_trans->to->first; end; end = end->next)
3719	{
3720	if (!start && end->test != d1->test)
3721	/* END belongs to a range of decisions that need to be
3722	protected by NEW_TRANS. */
3723	start = end;
3724	if (start && (!end->next || end->next->test == d1->test))
3725	{
3726	/* Protect [START, END] with NEW_TRANS. The decisions
3727	move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */
3728	state *new_s = new state;
3729	decision *new_d = new decision (d1->test);
3730	new_d->push_back (r: new transition (new_trans->labels, new_s,
3731	new_trans->optional));
3732	state::range r (start, end);
3733	new_trans->to->replace (oldr: r, newr: new_d);
3734	new_s->push_back (r);
3735
3736	/* Continue with an empty range. */
3737	start = 0;
3738
3739	/* Continue from the decision after NEW_D. */
3740	end = new_d;
3741	}
3742	}
3743	}
3744	new_trans->optional = true;
3745	new_trans->labels = *combined;
3746	}
3747	else
3748	{
3749	/* We're merging more than one existing transition together.
3750	Those transitions are successfully dividing the matching space
3751	and so we want to preserve them, even if they're optional.
3752
3753	Create a new transition with the union set of labels and make
3754	it go to a state that has the original transitions. */
3755	decision *new_d = new decision (d1->test);
3756	for (unsigned int i = 0; i < intersecting.length (); ++i)
3757	new_d->push_back (r: d1->remove (r: intersecting[i]));
3758
3759	state *new_s = new state;
3760	new_s->push_back (r: new_d);
3761
3762	new_trans = new transition (*combined, new_s, true);
3763	d1->push_back (r: new_trans);
3764	}
3765
3766	/* We now have an optional transition with labels *COMBINED. Decide
3767	whether we can use it as TRANS2 or whether we need to merge S2
3768	into the target of NEW_TRANS. */
3769	gcc_assert (new_trans->optional);
3770	if (new_trans->labels == trans2->labels)
3771	{
3772	/* NEW_TRANS matches TRANS2. Just merge the target states. */
3773	new_trans->optional = trans2->optional;
3774	*next_s1 = new_trans->to;
3775	*next_s2 = trans2->to;
3776	*next_exclude = 0;
3777	}
3778	else
3779	{
3780	/* Try to merge TRANS2 into the target of the overlapping transition,
3781	but (to prevent infinite recursion or excessive redundancy) without
3782	creating another transition of the same type. */
3783	*next_s1 = new_trans->to;
3784	*next_s2 = s2;
3785	*next_exclude = &new_trans->labels;
3786	}
3787	return true;
3788	}
3789
3790	/* Make progress in merging S2 into S1, given that each state in S2
3791	has a single decision. If EXCLUDE is nonnull, avoid creating a new
3792	transition with the same test as S2's decision and with the labels
3793	in *EXCLUDE.
3794
3795	Return true if there is still work to do. When returning true,
3796	set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that
3797	S1, S2 and EXCLUDE should have next time round.
3798
3799	If S1 and S2 both match a particular rtx, give priority to S1. */
3800
3801	static bool
3802	merge_into_state_1 (state *s1, state *s2, const int_set *exclude,
3803	state **next_s1, state **next_s2,
3804	const int_set **next_exclude)
3805	{
3806	decision *d2 = s2->singleton ();
3807	if (decision *d1 = s1->last)
3808	{
3809	if (d1->test.terminal_p ())
3810	/* D1 is an unconditional return, so S2 can never match. This can
3811	sometimes be a bug in the .md description, but might also happen
3812	if genconditions forces some conditions to true for certain
3813	configurations. */
3814	return false;
3815
3816	/* Go backwards through the decisions in S1, stopping once we find one
3817	that could match the same thing as S2. */
3818	while (d1->prev && mutually_exclusive_p (d1, d2))
3819	d1 = d1->prev;
3820
3821	/* Search forwards from that point, merging D2 into the first
3822	decision we can. */
3823	for (; d1; d1 = d1->next)
3824	{
3825	/* If S2 performs some optional tests before testing the same thing
3826	as D1, those tests do not help to distinguish D1 and S2, so it's
3827	better to drop them. Search through such optional decisions
3828	until we find something that tests the same thing as D1. */
3829	state *sub_s2 = s2;
3830	for (;;)
3831	{
3832	decision *sub_d2 = sub_s2->singleton ();
3833	if (d1->test == sub_d2->test)
3834	{
3835	/* Only apply EXCLUDE if we're testing the same thing
3836	as D2. */
3837	const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0);
3838
3839	/* Try to merge SUB_S2 into D1. This can only fail if
3840	it would involve creating a new transition with
3841	labels SUB_EXCLUDE. */
3842	if (merge_into_decision (d1, s2: sub_s2, exclude: sub_exclude,
3843	next_s1, next_s2, next_exclude))
3844	return *next_s2 != 0;
3845
3846	/* Can't merge with D1; try a later decision. */
3847	break;
3848	}
3849	transition *sub_trans2 = sub_d2->singleton ();
3850	if (!sub_trans2->optional)
3851	/* Can't merge with D1; try a later decision. */
3852	break;
3853	sub_s2 = sub_trans2->to;
3854	}
3855	}
3856	}
3857
3858	/* We can't merge D2 with any existing decision. Just add it to the end. */
3859	s1->push_back (r: s2->release ());
3860	return false;
3861	}
3862
3863	/* Merge S2 into S1. If they both match a particular rtx, give
3864	priority to S1. Each state in S2 has a single decision. */
3865
3866	static void
3867	merge_into_state (state *s1, state *s2)
3868	{
3869	const int_set *exclude = 0;
3870	while (s2 && merge_into_state_1 (s1, s2, exclude, next_s1: &s1, next_s2: &s2, next_exclude: &exclude))
3871	continue;
3872	}
3873
3874	/* Pairs a pattern that needs to be matched with the rtx position at
3875	which the pattern should occur. */
3876	class pattern_pos {
3877	public:
3878	pattern_pos () {}
3879	pattern_pos (rtx, position *);
3880
3881	rtx pattern;
3882	position *pos;
3883	};
3884
3885	pattern_pos::pattern_pos (rtx pattern_in, position *pos_in)
3886	: pattern (pattern_in), pos (pos_in)
3887	{}
3888
3889	/* Compare entries according to their depth-first order. There shouldn't
3890	be two entries at the same position. */
3891
3892	bool
3893	operator < (const pattern_pos &e1, const pattern_pos &e2)
3894	{
3895	int diff = compare_positions (pos1: e1.pos, pos2: e2.pos);
3896	gcc_assert (diff != 0 || e1.pattern == e2.pattern);
3897	return diff < 0;
3898	}
3899
3900	/* Add new decisions to S that check whether the rtx at position POS
3901	matches PATTERN. Return the state that is reached in that case.
3902	TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */
3903
3904	static state *
3905	match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern)
3906	{
3907	auto_vec <pattern_pos, 32> worklist;
3908	auto_vec <pattern_pos, 32> pred_and_mode_tests;
3909	auto_vec <pattern_pos, 32> dup_tests;
3910
3911	worklist.safe_push (obj: pattern_pos (pattern, pos));
3912	while (!worklist.is_empty ())
3913	{
3914	pattern_pos next = worklist.pop ();
3915	pattern = next.pattern;
3916	pos = next.pos;
3917	unsigned int reverse_s = worklist.length ();
3918
3919	enum rtx_code code = GET_CODE (pattern);
3920	switch (code)
3921	{
3922	case MATCH_OP_DUP:
3923	case MATCH_DUP:
3924	case MATCH_PAR_DUP:
3925	/* Add a test that the rtx matches the earlier one, but only
3926	after the structure and predicates have been checked. */
3927	dup_tests.safe_push (obj: pattern_pos (pattern, pos));
3928
3929	/* Use the same code check as the original operand. */
3930	pattern = find_operand (pattern: info->def, XINT (pattern, 0), NULL_RTX);
3931	/* Fall through. */
3932
3933	case MATCH_PARALLEL:
3934	case MATCH_OPERAND:
3935	case MATCH_SCRATCH:
3936	case MATCH_OPERATOR:
3937	{
3938	const char *pred_name = predicate_name (match_rtx: pattern);
3939	const struct pred_data *pred = 0;
3940	if (pred_name[0] != 0)
3941	{
3942	pred = lookup_predicate (pred_name);
3943	/* Only report errors once per rtx. */
3944	if (code == GET_CODE (pattern))
3945	{
3946	if (!pred)
3947	error_at (info->loc, "unknown predicate '%s' used in %s",
3948	pred_name, GET_RTX_NAME (code));
3949	else if (code == MATCH_PARALLEL
3950	&& pred->singleton != PARALLEL)
3951	error_at (info->loc, "predicate '%s' used in"
3952	" match_parallel does not allow only PARALLEL",
3953	pred->name);
3954	}
3955	}
3956
3957	if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP)
3958	{
3959	/* Check that we have a parallel with enough elements. */
3960	s = add_decision (from: s, test: rtx_test::code (pos), labels: PARALLEL, optional: false);
3961	int min_len = XVECLEN (pattern, 2);
3962	s = add_decision (from: s, test: rtx_test::veclen_ge (pos, min_len),
3963	labels: true, optional: false);
3964	}
3965	else
3966	{
3967	/* Check that the rtx has one of codes accepted by the
3968	predicate. This is necessary when matching suboperands
3969	of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't
3970	call XEXP (X, N) without checking that X has at least
3971	N+1 operands. */
3972	int_set codes;
3973	get_predicate_codes (pred, codes: &codes);
3974	bool need_codes = (pred
3975	&& (code == MATCH_OPERATOR
3976	|| code == MATCH_OP_DUP));
3977	s = add_decision (from: s, test: rtx_test::code (pos), labels: codes, optional: !need_codes);
3978	}
3979
3980	/* Postpone the predicate check until we've checked the rest
3981	of the rtx structure. */
3982	if (code == GET_CODE (pattern))
3983	pred_and_mode_tests.safe_push (obj: pattern_pos (pattern, pos));
3984
3985	/* If we need to match suboperands, add them to the worklist. */
3986	if (code == MATCH_OPERATOR || code == MATCH_PARALLEL)
3987	{
3988	position **subpos_ptr;
3989	enum position_type pos_type;
3990	int i;
3991	if (code == MATCH_OPERATOR || code == MATCH_OP_DUP)
3992	{
3993	pos_type = POS_XEXP;
3994	subpos_ptr = &pos->xexps;
3995	i = (code == MATCH_OPERATOR ? 2 : 1);
3996	}
3997	else
3998	{
3999	pos_type = POS_XVECEXP0;
4000	subpos_ptr = &pos->xvecexp0s;
4001	i = 2;
4002	}
4003	for (int j = 0; j < XVECLEN (pattern, i); ++j)
4004	{
4005	position *subpos = next_position (next_ptr: subpos_ptr, base: pos,
4006	type: pos_type, arg: j);
4007	worklist.safe_push (obj: pattern_pos (XVECEXP (pattern, i, j),
4008	subpos));
4009	subpos_ptr = &subpos->next;
4010	}
4011	}
4012	break;
4013	}
4014
4015	default:
4016	{
4017	/* Check that the rtx has the right code. */
4018	s = add_decision (from: s, test: rtx_test::code (pos), labels: code, optional: false);
4019
4020	/* Queue a test for the mode if one is specified. */
4021	if (GET_MODE (pattern) != VOIDmode)
4022	pred_and_mode_tests.safe_push (obj: pattern_pos (pattern, pos));
4023
4024	/* Push subrtxes onto the worklist. Match nonrtx operands now. */
4025	const char *fmt = GET_RTX_FORMAT (code);
4026	position **subpos_ptr = &pos->xexps;
4027	for (size_t i = 0; fmt[i]; ++i)
4028	{
4029	position *subpos = next_position (next_ptr: subpos_ptr, base: pos,
4030	type: POS_XEXP, arg: i);
4031	switch (fmt[i])
4032	{
4033	case 'e': case 'u':
4034	worklist.safe_push (obj: pattern_pos (XEXP (pattern, i),
4035	subpos));
4036	break;
4037
4038	case 'E':
4039	{
4040	/* Make sure the vector has the right number of
4041	elements. */
4042	int length = XVECLEN (pattern, i);
4043	s = add_decision (from: s, test: rtx_test::veclen (pos),
4044	labels: length, optional: false);
4045
4046	position **subpos2_ptr = &pos->xvecexp0s;
4047	for (int j = 0; j < length; j++)
4048	{
4049	position *subpos2 = next_position (next_ptr: subpos2_ptr, base: pos,
4050	type: POS_XVECEXP0, arg: j);
4051	rtx x = XVECEXP (pattern, i, j);
4052	worklist.safe_push (obj: pattern_pos (x, subpos2));
4053	subpos2_ptr = &subpos2->next;
4054	}
4055	break;
4056	}
4057
4058	case 'i':
4059	/* Make sure that XINT (X, I) has the right value. */
4060	s = add_decision (from: s, test: rtx_test::int_field (pos, opno: i),
4061	XINT (pattern, i), optional: false);
4062	break;
4063
4064	case 'r':
4065	/* Make sure that REGNO (X) has the right value. */
4066	gcc_assert (i == 0);
4067	s = add_decision (from: s, test: rtx_test::regno_field (pos),
4068	REGNO (pattern), optional: false);
4069	break;
4070
4071	case 'w':
4072	/* Make sure that XWINT (X, I) has the right value. */
4073	s = add_decision (from: s, test: rtx_test::wide_int_field (pos, opno: i),
4074	XWINT (pattern, 0), optional: false);
4075	break;
4076
4077	case 'p':
4078	/* We don't have a way of parsing polynomial offsets yet,
4079	and hopefully never will. */
4080	s = add_decision (from: s, test: rtx_test::subreg_field (pos),
4081	SUBREG_BYTE (pattern).to_constant (),
4082	optional: false);
4083	break;
4084
4085	case '0':
4086	break;
4087
4088	default:
4089	gcc_unreachable ();
4090	}
4091	subpos_ptr = &subpos->next;
4092	}
4093	}
4094	break;
4095	}
4096	/* Operands are pushed onto the worklist so that later indices are
4097	nearer the top. That's what we want for SETs, since a SET_SRC
4098	is a better discriminator than a SET_DEST. In other cases it's
4099	usually better to match earlier indices first. This is especially
4100	true of PARALLELs, where the first element tends to be the most
4101	individual. It's also true for commutative operators, where the
4102	canonicalization rules say that the more complex operand should
4103	come first. */
4104	if (code != SET && worklist.length () > reverse_s)
4105	std::reverse (first: &worklist[0] + reverse_s,
4106	last: &worklist[0] + worklist.length ());
4107	}
4108
4109	/* Sort the predicate and mode tests so that they're in depth-first order.
4110	The main goal of this is to put SET_SRC match_operands after SET_DEST
4111	match_operands and after mode checks for the enclosing SET_SRC operators
4112	(such as the mode of a PLUS in an addition instruction). The latter
4113	two types of test can determine the mode exactly, whereas a SET_SRC
4114	match_operand often has to cope with the possibility of the operand
4115	being a modeless constant integer. E.g. something that matches
4116	register_operand (x, SImode) never matches register_operand (x, DImode),
4117	but a const_int that matches immediate_operand (x, SImode) also matches
4118	immediate_operand (x, DImode). The register_operand cases can therefore
4119	be distinguished by a switch on the mode, but the immediate_operand
4120	cases can't. */
4121	if (pred_and_mode_tests.length () > 1)
4122	std::sort (first: &pred_and_mode_tests[0],
4123	last: &pred_and_mode_tests[0] + pred_and_mode_tests.length ());
4124
4125	/* Add the mode and predicate tests. */
4126	pattern_pos *e;
4127	unsigned int i;
4128	FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e)
4129	{
4130	switch (GET_CODE (e->pattern))
4131	{
4132	case MATCH_PARALLEL:
4133	case MATCH_OPERAND:
4134	case MATCH_SCRATCH:
4135	case MATCH_OPERATOR:
4136	{
4137	int opno = XINT (e->pattern, 0);
4138	num_operands = MAX (num_operands, opno + 1);
4139	const char *pred_name = predicate_name (match_rtx: e->pattern);
4140	if (pred_name[0])
4141	{
4142	const struct pred_data *pred = lookup_predicate (pred_name);
4143	/* Check the mode first, to distinguish things like SImode
4144	and DImode register_operands, as described above. */
4145	machine_mode mode = GET_MODE (e->pattern);
4146	if (pred && safe_predicate_mode (pred, mode))
4147	s = add_decision (from: s, test: rtx_test::mode (pos: e->pos), labels: mode, optional: true);
4148
4149	/* Assign to operands[] first, so that the rtx usually doesn't
4150	need to be live across the call to the predicate.
4151
4152	This shouldn't cause a problem with dirtying the page,
4153	since we fully expect to assign to operands[] at some point,
4154	and since the caller usually writes to other parts of
4155	recog_data anyway. */
4156	s = add_decision (from: s, test: rtx_test::set_op (pos: e->pos, opno),
4157	labels: true, optional: false);
4158	s = add_decision (from: s, test: rtx_test::predicate (pos: e->pos, data: pred, mode),
4159	labels: true, optional: false);
4160	}
4161	else
4162	/* Historically we've ignored the mode when there's no
4163	predicate. Just set up operands[] unconditionally. */
4164	s = add_decision (from: s, test: rtx_test::set_op (pos: e->pos, opno),
4165	labels: true, optional: false);
4166	break;
4167	}
4168
4169	default:
4170	s = add_decision (from: s, test: rtx_test::mode (pos: e->pos),
4171	GET_MODE (e->pattern), optional: false);
4172	break;
4173	}
4174	}
4175
4176	/* Finally add rtx_equal_p checks for duplicated operands. */
4177	FOR_EACH_VEC_ELT (dup_tests, i, e)
4178	s = add_decision (from: s, test: rtx_test::duplicate (pos: e->pos, XINT (e->pattern, 0)),
4179	labels: true, optional: false);
4180	return s;
4181	}
4182
4183	/* Add new decisions to S that make it return ACCEPTANCE if:
4184
4185	(1) the rtx doesn't match anything already matched by S
4186	(2) the rtx matches TOP_PATTERN and
4187	(3) the C test required by INFO->def is true
4188
4189	For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns
4190	to match, otherwise it is a single instruction pattern. */
4191
4192	static void
4193	match_pattern_1 (state *s, md_rtx_info *info, rtx pattern,
4194	acceptance_type acceptance)
4195	{
4196	if (acceptance.type == PEEPHOLE2)
4197	{
4198	/* Match each individual instruction. */
4199	position **subpos_ptr = &peep2_insn_pos_list;
4200	int count = 0;
4201	for (int i = 0; i < XVECLEN (pattern, 0); ++i)
4202	{
4203	rtx x = XVECEXP (pattern, 0, i);
4204	position *subpos = next_position (next_ptr: subpos_ptr, base: &root_pos,
4205	type: POS_PEEP2_INSN, arg: count);
4206	if (count > 0)
4207	s = add_decision (from: s, test: rtx_test::peep2_count (min_len: count + 1),
4208	labels: true, optional: false);
4209	s = match_pattern_2 (s, info, pos: subpos, pattern: x);
4210	subpos_ptr = &subpos->next;
4211	count += 1;
4212	}
4213	acceptance.u.full.u.match_len = count - 1;
4214	}
4215	else
4216	{
4217	/* Make the rtx itself. */
4218	s = match_pattern_2 (s, info, pos: &root_pos, pattern);
4219
4220	/* If the match is only valid when extra clobbers are added,
4221	make sure we're able to pass that information to the caller. */
4222	if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers)
4223	s = add_decision (from: s, test: rtx_test::have_num_clobbers (), labels: true, optional: false);
4224	}
4225
4226	/* Make sure that the C test is true. */
4227	const char *c_test = get_c_test (info->def);
4228	if (maybe_eval_c_test (c_test) != 1)
4229	s = add_decision (from: s, test: rtx_test::c_test (string: c_test), labels: true, optional: false);
4230
4231	/* Accept the pattern. */
4232	add_decision (from: s, test: rtx_test::accept (acceptance), labels: true, optional: false);
4233	}
4234
4235	/* Like match_pattern_1, but (if merge_states_p) try to merge the
4236	decisions with what's already in S, to reduce the amount of
4237	backtracking. */
4238
4239	static void
4240	match_pattern (state *s, md_rtx_info *info, rtx pattern,
4241	acceptance_type acceptance)
4242	{
4243	if (merge_states_p)
4244	{
4245	state root;
4246	/* Add the decisions to a fresh state and then merge the full tree
4247	into the existing one. */
4248	match_pattern_1 (s: &root, info, pattern, acceptance);
4249	merge_into_state (s1: s, s2: &root);
4250	}
4251	else
4252	match_pattern_1 (s, info, pattern, acceptance);
4253	}
4254
4255	/* Begin the output file. */
4256
4257	static void
4258	write_header (void)
4259	{
4260	puts (s: "\
4261	/* Generated automatically by the program `genrecog' from the target\n\
4262	machine description file. */\n\
4263	\n\
4264	#define IN_TARGET_CODE 1\n\
4265	\n\
4266	#include \"config.h\"\n\
4267	#include \"system.h\"\n\
4268	#include \"coretypes.h\"\n\
4269	#include \"backend.h\"\n\
4270	#include \"predict.h\"\n\
4271	#include \"rtl.h\"\n\
4272	#include \"memmodel.h\"\n\
4273	#include \"tm_p.h\"\n\
4274	#include \"emit-rtl.h\"\n\
4275	#include \"insn-config.h\"\n\
4276	#include \"recog.h\"\n\
4277	#include \"output.h\"\n\
4278	#include \"flags.h\"\n\
4279	#include \"df.h\"\n\
4280	#include \"resource.h\"\n\
4281	#include \"diagnostic-core.h\"\n\
4282	#include \"reload.h\"\n\
4283	#include \"regs.h\"\n\
4284	#include \"tm-constrs.h\"\n\
4285	\n");
4286
4287	puts (s: "\n\
4288	/* `recog' contains a decision tree that recognizes whether the rtx\n\
4289	X0 is a valid instruction.\n\
4290	\n\
4291	recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\
4292	returns a nonnegative number which is the insn code number for the\n\
4293	pattern that matched. This is the same as the order in the machine\n\
4294	description of the entry that matched. This number can be used as an\n\
4295	index into `insn_data' and other tables.\n");
4296	puts (s: "\
4297	The third parameter to recog is an optional pointer to an int. If\n\
4298	present, recog will accept a pattern if it matches except for missing\n\
4299	CLOBBER expressions at the end. In that case, the value pointed to by\n\
4300	the optional pointer will be set to the number of CLOBBERs that need\n\
4301	to be added (it should be initialized to zero by the caller). If it");
4302	puts (s: "\
4303	is set nonzero, the caller should allocate a PARALLEL of the\n\
4304	appropriate size, copy the initial entries, and call add_clobbers\n\
4305	(found in insn-emit.cc) to fill in the CLOBBERs.\n\
4306	");
4307
4308	puts (s: "\n\
4309	The function split_insns returns 0 if the rtl could not\n\
4310	be split or the split rtl as an INSN list if it can be.\n\
4311	\n\
4312	The function peephole2_insns returns 0 if the rtl could not\n\
4313	be matched. If there was a match, the new rtl is returned in an INSN list,\n\
4314	and LAST_INSN will point to the last recognized insn in the old sequence.\n\
4315	*/\n\n");
4316	}
4317
4318	/* Return the C type of a parameter with type TYPE. */
4319
4320	static const char *
4321	parameter_type_string (parameter::type_enum type)
4322	{
4323	switch (type)
4324	{
4325	case parameter::UNSET:
4326	break;
4327
4328	case parameter::CODE:
4329	return "rtx_code";
4330
4331	case parameter::MODE:
4332	return "machine_mode";
4333
4334	case parameter::INT:
4335	return "int";
4336
4337	case parameter::UINT:
4338	return "unsigned int";
4339
4340	case parameter::WIDE_INT:
4341	return "HOST_WIDE_INT";
4342	}
4343	gcc_unreachable ();
4344	}
4345
4346	/* Return true if ACCEPTANCE requires only a single C statement even in
4347	a backtracking context. */
4348
4349	static bool
4350	single_statement_p (const acceptance_type &acceptance)
4351	{
4352	if (acceptance.partial_p)
4353	/* We need to handle failures of the subroutine. */
4354	return false;
4355	switch (acceptance.type)
4356	{
4357	case SUBPATTERN:
4358	case SPLIT:
4359	return true;
4360
4361	case RECOG:
4362	/* False if we need to assign to pnum_clobbers. */
4363	return acceptance.u.full.u.num_clobbers == 0;
4364
4365	case PEEPHOLE2:
4366	/* We need to assign to pmatch_len_ and handle null returns from the
4367	peephole2 routine. */
4368	return false;
4369	}
4370	gcc_unreachable ();
4371	}
4372
4373	/* Return the C failure value for a routine of type TYPE. */
4374
4375	static const char *
4376	get_failure_return (routine_type type)
4377	{
4378	switch (type)
4379	{
4380	case SUBPATTERN:
4381	case RECOG:
4382	return "-1";
4383
4384	case SPLIT:
4385	case PEEPHOLE2:
4386	return "NULL";
4387	}
4388	gcc_unreachable ();
4389	}
4390
4391	/* Indicates whether a block of code always returns or whether it can fall
4392	through. */
4393
4394	enum exit_state {
4395	ES_RETURNED,
4396	ES_FALLTHROUGH
4397	};
4398
4399	/* Information used while writing out code. */
4400
4401	class output_state
4402	{
4403	public:
4404	/* The type of routine that we're generating. */
4405	routine_type type;
4406
4407	/* Maps position ids to xN variable numbers. The entry is only valid if
4408	it is less than the length of VAR_TO_ID, but this holds for every position
4409	tested by a state when writing out that state. */
4410	auto_vec <unsigned int> id_to_var;
4411
4412	/* Maps xN variable numbers to position ids. */
4413	auto_vec <unsigned int> var_to_id;
4414
4415	/* Index N is true if variable xN has already been set. */
4416	auto_vec <bool> seen_vars;
4417	};
4418
4419	/* Return true if D is a call to a pattern routine and if there is some X
4420	such that the transition for pattern result N goes to a successful return
4421	with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT
4422	to the number of return values. (We know that every PATTERN decision has
4423	a transition for every successful return.) */
4424
4425	static bool
4426	terminal_pattern_p (decision *d, unsigned int *base_out,
4427	unsigned int *count_out)
4428	{
4429	if (d->test.kind != rtx_test::PATTERN)
4430	return false;
4431	unsigned int base = 0;
4432	unsigned int count = 0;
4433	for (transition *trans = d->first; trans; trans = trans->next)
4434	{
4435	if (trans->is_param || trans->labels.length () != 1)
4436	return false;
4437	decision *subd = trans->to->singleton ();
4438	if (!subd || subd->test.kind != rtx_test::ACCEPT)
4439	return false;
4440	unsigned int this_base = (subd->test.u.acceptance.u.full.code
4441	- trans->labels[0]);
4442	if (trans == d->first)
4443	base = this_base;
4444	else if (base != this_base)
4445	return false;
4446	count += 1;
4447	}
4448	*base_out = base;
4449	*count_out = count;
4450	return true;
4451	}
4452
4453	/* Return true if TEST doesn't test an rtx or if the rtx it tests is
4454	already available in state OS. */
4455
4456	static bool
4457	test_position_available_p (output_state *os, const rtx_test &test)
4458	{
4459	return (!test.pos
4460	|| test.pos_operand >= 0
4461	|| os->seen_vars[os->id_to_var[test.pos->id]]);
4462	}
4463
4464	/* Like printf, but print INDENT spaces at the beginning. */
4465
4466	static void ATTRIBUTE_PRINTF_2
4467	printf_indent (unsigned int indent, const char *format, ...)
4468	{
4469	va_list ap;
4470	va_start (ap, format);
4471	printf (format: "%*s", indent, "");
4472	vprintf (fmt: format, arg: ap);
4473	va_end (ap);
4474	}
4475
4476	/* Emit code to initialize the variable associated with POS, if it isn't
4477	already valid in state OS. Indent each line by INDENT spaces. Update
4478	OS with the new state. */
4479
4480	static void
4481	change_state (output_state *os, position *pos, unsigned int indent)
4482	{
4483	unsigned int var = os->id_to_var[pos->id];
4484	gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id);
4485	if (os->seen_vars[var])
4486	return;
4487	switch (pos->type)
4488	{
4489	case POS_PEEP2_INSN:
4490	printf_indent (indent, format: "x%d = PATTERN (peep2_next_insn (%d));\n",
4491	var, pos->arg);
4492	break;
4493
4494	case POS_XEXP:
4495	change_state (os, pos: pos->base, indent);
4496	printf_indent (indent, format: "x%d = XEXP (x%d, %d);\n",
4497	var, os->id_to_var[pos->base->id], pos->arg);
4498	break;
4499
4500	case POS_XVECEXP0:
4501	change_state (os, pos: pos->base, indent);
4502	printf_indent (indent, format: "x%d = XVECEXP (x%d, 0, %d);\n",
4503	var, os->id_to_var[pos->base->id], pos->arg);
4504	break;
4505	}
4506	os->seen_vars[var] = true;
4507	}
4508
4509	/* Print the enumerator constant for CODE -- the upcase version of
4510	the name. */
4511
4512	static void
4513	print_code (enum rtx_code code)
4514	{
4515	const char *p;
4516	for (p = GET_RTX_NAME (code); *p; p++)
4517	putchar (TOUPPER (*p));
4518	}
4519
4520	/* Emit a uint64_t as an integer constant expression. We need to take
4521	special care to avoid "decimal constant is so large that it is unsigned"
4522	warnings in the resulting code. */
4523
4524	static void
4525	print_host_wide_int (uint64_t val)
4526	{
4527	uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1);
4528	if (val == min)
4529	printf (format: "(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1);
4530	else
4531	printf (HOST_WIDE_INT_PRINT_DEC_C, val);
4532	}
4533
4534	/* Print the C expression for actual parameter PARAM. */
4535
4536	static void
4537	print_parameter_value (const parameter &param)
4538	{
4539	if (param.is_param)
4540	printf (format: "i%d", (int) param.value + 1);
4541	else
4542	switch (param.type)
4543	{
4544	case parameter::UNSET:
4545	gcc_unreachable ();
4546	break;
4547
4548	case parameter::CODE:
4549	print_code (code: (enum rtx_code) param.value);
4550	break;
4551
4552	case parameter::MODE:
4553	printf (format: "E_%smode", GET_MODE_NAME ((machine_mode) param.value));
4554	break;
4555
4556	case parameter::INT:
4557	printf (format: "%d", (int) param.value);
4558	break;
4559
4560	case parameter::UINT:
4561	printf (format: "%u", (unsigned int) param.value);
4562	break;
4563
4564	case parameter::WIDE_INT:
4565	print_host_wide_int (val: param.value);
4566	break;
4567	}
4568	}
4569
4570	/* Print the C expression for the rtx tested by TEST. */
4571
4572	static void
4573	print_test_rtx (output_state *os, const rtx_test &test)
4574	{
4575	if (test.pos_operand >= 0)
4576	printf (format: "operands[%d]", test.pos_operand);
4577	else
4578	printf (format: "x%d", os->id_to_var[test.pos->id]);
4579	}
4580
4581	/* Print the C expression for non-boolean test TEST. */
4582
4583	static void
4584	print_nonbool_test (output_state *os, const rtx_test &test)
4585	{
4586	switch (test.kind)
4587	{
4588	case rtx_test::CODE:
4589	printf (format: "GET_CODE (");
4590	print_test_rtx (os, test);
4591	printf (format: ")");
4592	break;
4593
4594	case rtx_test::MODE:
4595	printf (format: "GET_MODE (");
4596	print_test_rtx (os, test);
4597	printf (format: ")");
4598	break;
4599
4600	case rtx_test::VECLEN:
4601	printf (format: "XVECLEN (");
4602	print_test_rtx (os, test);
4603	printf (format: ", 0)");
4604	break;
4605
4606	case rtx_test::INT_FIELD:
4607	printf (format: "XINT (");
4608	print_test_rtx (os, test);
4609	printf (format: ", %d)", test.u.opno);
4610	break;
4611
4612	case rtx_test::REGNO_FIELD:
4613	printf (format: "REGNO (");
4614	print_test_rtx (os, test);
4615	printf (format: ")");
4616	break;
4617
4618	case rtx_test::SUBREG_FIELD:
4619	printf (format: "SUBREG_BYTE (");
4620	print_test_rtx (os, test);
4621	printf (format: ")");
4622	break;
4623
4624	case rtx_test::WIDE_INT_FIELD:
4625	printf (format: "XWINT (");
4626	print_test_rtx (os, test);
4627	printf (format: ", %d)", test.u.opno);
4628	break;
4629
4630	case rtx_test::PATTERN:
4631	{
4632	pattern_routine *routine = test.u.pattern->routine;
4633	printf (format: "pattern%d (", routine->pattern_id);
4634	const char *sep = "";
4635	if (test.pos)
4636	{
4637	print_test_rtx (os, test);
4638	sep = ", ";
4639	}
4640	if (routine->insn_p)
4641	{
4642	printf (format: "%sinsn", sep);
4643	sep = ", ";
4644	}
4645	if (routine->pnum_clobbers_p)
4646	{
4647	printf (format: "%spnum_clobbers", sep);
4648	sep = ", ";
4649	}
4650	for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i)
4651	{
4652	fputs (sep, stdout);
4653	print_parameter_value (param: test.u.pattern->params[i]);
4654	sep = ", ";
4655	}
4656	printf (format: ")");
4657	break;
4658	}
4659
4660	case rtx_test::PEEP2_COUNT:
4661	case rtx_test::VECLEN_GE:
4662	case rtx_test::SAVED_CONST_INT:
4663	case rtx_test::DUPLICATE:
4664	case rtx_test::PREDICATE:
4665	case rtx_test::SET_OP:
4666	case rtx_test::HAVE_NUM_CLOBBERS:
4667	case rtx_test::C_TEST:
4668	case rtx_test::ACCEPT:
4669	gcc_unreachable ();
4670	}
4671	}
4672
4673	/* IS_PARAM and LABEL are taken from a transition whose source
4674	decision performs TEST. Print the C code for the label. */
4675
4676	static void
4677	print_label_value (const rtx_test &test, bool is_param, uint64_t value)
4678	{
4679	print_parameter_value (param: parameter (transition_parameter_type (kind: test.kind),
4680	is_param, value));
4681	}
4682
4683	/* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>.
4684	If !IS_PARAM, print code to compare TEST with the C constant VALUE.
4685	Test for inequality if INVERT_P, otherwise test for equality. */
4686
4687	static void
4688	print_test (output_state *os, const rtx_test &test, bool is_param,
4689	uint64_t value, bool invert_p)
4690	{
4691	switch (test.kind)
4692	{
4693	/* Handle the non-boolean TESTs. */
4694	case rtx_test::CODE:
4695	case rtx_test::MODE:
4696	case rtx_test::VECLEN:
4697	case rtx_test::REGNO_FIELD:
4698	case rtx_test::INT_FIELD:
4699	case rtx_test::WIDE_INT_FIELD:
4700	case rtx_test::PATTERN:
4701	print_nonbool_test (os, test);
4702	printf (format: " %s ", invert_p ? "!=" : "==");
4703	print_label_value (test, is_param, value);
4704	break;
4705
4706	case rtx_test::SUBREG_FIELD:
4707	printf (format: "%s (", invert_p ? "maybe_ne" : "known_eq");
4708	print_nonbool_test (os, test);
4709	printf (format: ", ");
4710	print_label_value (test, is_param, value);
4711	printf (format: ")");
4712	break;
4713
4714	case rtx_test::SAVED_CONST_INT:
4715	gcc_assert (!is_param && value == 1);
4716	print_test_rtx (os, test);
4717	printf (format: " %s const_int_rtx[MAX_SAVED_CONST_INT + ",
4718	invert_p ? "!=" : "==");
4719	print_parameter_value (param: parameter (parameter::INT,
4720	test.u.integer.is_param,
4721	test.u.integer.value));
4722	printf (format: "]");
4723	break;
4724
4725	case rtx_test::PEEP2_COUNT:
4726	gcc_assert (!is_param && value == 1);
4727	printf (format: "peep2_current_count %s %d", invert_p ? "<" : ">=",
4728	test.u.min_len);
4729	break;
4730
4731	case rtx_test::VECLEN_GE:
4732	gcc_assert (!is_param && value == 1);
4733	printf (format: "XVECLEN (");
4734	print_test_rtx (os, test);
4735	printf (format: ", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len);
4736	break;
4737
4738	case rtx_test::PREDICATE:
4739	gcc_assert (!is_param && value == 1);
4740	printf (format: "%s%s (", invert_p ? "!" : "", test.u.predicate.data->name);
4741	print_test_rtx (os, test);
4742	printf (format: ", ");
4743	print_parameter_value (param: parameter (parameter::MODE,
4744	test.u.predicate.mode_is_param,
4745	test.u.predicate.mode));
4746	printf (format: ")");
4747	break;
4748
4749	case rtx_test::DUPLICATE:
4750	gcc_assert (!is_param && value == 1);
4751	printf (format: "%srtx_equal_p (", invert_p ? "!" : "");
4752	print_test_rtx (os, test);
4753	printf (format: ", operands[%d])", test.u.opno);
4754	break;
4755
4756	case rtx_test::HAVE_NUM_CLOBBERS:
4757	gcc_assert (!is_param && value == 1);
4758	printf (format: "pnum_clobbers %s NULL", invert_p ? "==" : "!=");
4759	break;
4760
4761	case rtx_test::C_TEST:
4762	gcc_assert (!is_param && value == 1);
4763	if (invert_p)
4764	printf (format: "!");
4765	rtx_reader_ptr->print_c_condition (cond: test.u.string);
4766	break;
4767
4768	case rtx_test::ACCEPT:
4769	case rtx_test::SET_OP:
4770	gcc_unreachable ();
4771	}
4772	}
4773
4774	static exit_state print_decision (output_state *, decision *,
4775	unsigned int, bool);
4776
4777	/* Print code to perform S, indent each line by INDENT spaces.
4778	IS_FINAL is true if there are no fallback decisions to test on failure;
4779	if the state fails then the entire routine fails. */
4780
4781	static exit_state
4782	print_state (output_state *os, state *s, unsigned int indent, bool is_final)
4783	{
4784	exit_state es = ES_FALLTHROUGH;
4785	for (decision *d = s->first; d; d = d->next)
4786	es = print_decision (os, d, indent, is_final && !d->next);
4787	if (es != ES_RETURNED && is_final)
4788	{
4789	printf_indent (indent, format: "return %s;\n", get_failure_return (type: os->type));
4790	es = ES_RETURNED;
4791	}
4792	return es;
4793	}
4794
4795	/* Print the code for subroutine call ACCEPTANCE (for which partial_p
4796	is known to be true). Return the C condition that indicates a successful
4797	match. */
4798
4799	static const char *
4800	print_subroutine_call (const acceptance_type &acceptance)
4801	{
4802	switch (acceptance.type)
4803	{
4804	case SUBPATTERN:
4805	gcc_unreachable ();
4806
4807	case RECOG:
4808	printf (format: "recog_%d (x1, insn, pnum_clobbers)",
4809	acceptance.u.subroutine_id);
4810	return ">= 0";
4811
4812	case SPLIT:
4813	printf (format: "split_%d (x1, insn)", acceptance.u.subroutine_id);
4814	return "!= NULL_RTX";
4815
4816	case PEEPHOLE2:
4817	printf (format: "peephole2_%d (x1, insn, pmatch_len_)",
4818	acceptance.u.subroutine_id);
4819	return "!= NULL_RTX";
4820	}
4821	gcc_unreachable ();
4822	}
4823
4824	/* Print code for the successful match described by ACCEPTANCE.
4825	INDENT and IS_FINAL are as for print_state. */
4826
4827	static exit_state
4828	print_acceptance (const acceptance_type &acceptance, unsigned int indent,
4829	bool is_final)
4830	{
4831	if (acceptance.partial_p)
4832	{
4833	/* Defer the rest of the match to a subroutine. */
4834	if (is_final)
4835	{
4836	printf_indent (indent, format: "return ");
4837	print_subroutine_call (acceptance);
4838	printf (format: ";\n");
4839	return ES_RETURNED;
4840	}
4841	else
4842	{
4843	printf_indent (indent, format: "res = ");
4844	const char *res_test = print_subroutine_call (acceptance);
4845	printf (format: ";\n");
4846	printf_indent (indent, format: "if (res %s)\n", res_test);
4847	printf_indent (indent: indent + 2, format: "return res;\n");
4848	return ES_FALLTHROUGH;
4849	}
4850	}
4851	switch (acceptance.type)
4852	{
4853	case SUBPATTERN:
4854	printf_indent (indent, format: "return %d;\n", acceptance.u.full.code);
4855	return ES_RETURNED;
4856
4857	case RECOG:
4858	if (acceptance.u.full.u.num_clobbers != 0)
4859	printf_indent (indent, format: "*pnum_clobbers = %d;\n",
4860	acceptance.u.full.u.num_clobbers);
4861	printf_indent (indent, format: "return %d; /* %s */\n", acceptance.u.full.code,
4862	get_insn_name (acceptance.u.full.code));
4863	return ES_RETURNED;
4864
4865	case SPLIT:
4866	printf_indent (indent, format: "return gen_split_%d (insn, operands);\n",
4867	acceptance.u.full.code);
4868	return ES_RETURNED;
4869
4870	case PEEPHOLE2:
4871	printf_indent (indent, format: "*pmatch_len_ = %d;\n",
4872	acceptance.u.full.u.match_len);
4873	if (is_final)
4874	{
4875	printf_indent (indent, format: "return gen_peephole2_%d (insn, operands);\n",
4876	acceptance.u.full.code);
4877	return ES_RETURNED;
4878	}
4879	else
4880	{
4881	printf_indent (indent, format: "res = gen_peephole2_%d (insn, operands);\n",
4882	acceptance.u.full.code);
4883	printf_indent (indent, format: "if (res != NULL_RTX)\n");
4884	printf_indent (indent: indent + 2, format: "return res;\n");
4885	return ES_FALLTHROUGH;
4886	}
4887	}
4888	gcc_unreachable ();
4889	}
4890
4891	/* Print code to perform D. INDENT and IS_FINAL are as for print_state. */
4892
4893	static exit_state
4894	print_decision (output_state *os, decision *d, unsigned int indent,
4895	bool is_final)
4896	{
4897	uint64_t label;
4898	unsigned int base, count;
4899
4900	/* Make sure the rtx under test is available either in operands[] or
4901	in an xN variable. */
4902	if (d->test.pos && d->test.pos_operand < 0)
4903	change_state (os, pos: d->test.pos, indent);
4904
4905	/* Look for cases where a pattern routine P1 calls another pattern routine
4906	P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL
4907	is true and BASE is zero we can simply use:
4908
4909	return patternN (...);
4910
4911	Otherwise we can use:
4912
4913	res = patternN (...);
4914	if (res >= 0)
4915	return res + BASE;
4916
4917	However, if BASE is nonzero and patternN only returns 0 or -1,
4918	the usual "return BASE;" is better than "return res + BASE;".
4919	If BASE is zero, "return res;" should be better than "return 0;",
4920	since no assignment to the return register is required. */
4921	if (os->type == SUBPATTERN
4922	&& terminal_pattern_p (d, base_out: &base, count_out: &count)
4923	&& (base == 0 || count > 1))
4924	{
4925	if (is_final && base == 0)
4926	{
4927	printf_indent (indent, format: "return ");
4928	print_nonbool_test (os, test: d->test);
4929	printf (format: "; /* [-1, %d] */\n", count - 1);
4930	return ES_RETURNED;
4931	}
4932	else
4933	{
4934	printf_indent (indent, format: "res = ");
4935	print_nonbool_test (os, test: d->test);
4936	printf (format: ";\n");
4937	printf_indent (indent, format: "if (res >= 0)\n");
4938	printf_indent (indent: indent + 2, format: "return res");
4939	if (base != 0)
4940	printf (format: " + %d", base);
4941	printf (format: "; /* [%d, %d] */\n", base, base + count - 1);
4942	return ES_FALLTHROUGH;
4943	}
4944	}
4945	else if (d->test.kind == rtx_test::ACCEPT)
4946	return print_acceptance (acceptance: d->test.u.acceptance, indent, is_final);
4947	else if (d->test.kind == rtx_test::SET_OP)
4948	{
4949	printf_indent (indent, format: "operands[%d] = ", d->test.u.opno);
4950	print_test_rtx (os, test: d->test);
4951	printf (format: ";\n");
4952	return print_state (os, s: d->singleton ()->to, indent, is_final);
4953	}
4954	/* Handle decisions with a single transition and a single transition
4955	label. */
4956	else if (d->if_statement_p (label: &label))
4957	{
4958	transition *trans = d->singleton ();
4959	if (mark_optional_transitions_p && trans->optional)
4960	printf_indent (indent, format: "/* OPTIONAL IF */\n");
4961
4962	/* Print the condition associated with TRANS. Invert it if IS_FINAL,
4963	so that we return immediately on failure and fall through on
4964	success. */
4965	printf_indent (indent, format: "if (");
4966	print_test (os, test: d->test, is_param: trans->is_param, value: label, invert_p: is_final);
4967
4968	/* Look for following states that would be handled by this code
4969	on recursion. If they don't need any preparatory statements,
4970	include them in the current "if" statement rather than creating
4971	a new one. */
4972	for (;;)
4973	{
4974	d = trans->to->singleton ();
4975	if (!d
4976	|| d->test.kind == rtx_test::ACCEPT
4977	|| d->test.kind == rtx_test::SET_OP
4978	|| !d->if_statement_p (label: &label)
4979	|| !test_position_available_p (os, test: d->test))
4980	break;
4981	trans = d->first;
4982	printf (format: "\n");
4983	if (mark_optional_transitions_p && trans->optional)
4984	printf_indent (indent: indent + 4, format: "/* OPTIONAL IF */\n");
4985	printf_indent (indent: indent + 4, format: "%s ", is_final ? "||" : "&&");
4986	print_test (os, test: d->test, is_param: trans->is_param, value: label, invert_p: is_final);
4987	}
4988	printf (format: ")\n");
4989
4990	/* Print the conditional code with INDENT + 2 and the fallthrough
4991	code with indent INDENT. */
4992	state *to = trans->to;
4993	if (is_final)
4994	{
4995	/* We inverted the condition above, so return failure in the
4996	"if" body and fall through to the target of the transition. */
4997	printf_indent (indent: indent + 2, format: "return %s;\n",
4998	get_failure_return (type: os->type));
4999	return print_state (os, s: to, indent, is_final);
5000	}
5001	else if (to->singleton ()
5002	&& to->first->test.kind == rtx_test::ACCEPT
5003	&& single_statement_p (acceptance: to->first->test.u.acceptance))
5004	{
5005	/* The target of the transition is a simple "return" statement.
5006	It doesn't need any braces and doesn't fall through. */
5007	if (print_acceptance (acceptance: to->first->test.u.acceptance,
5008	indent: indent + 2, is_final: true) != ES_RETURNED)
5009	gcc_unreachable ();
5010	return ES_FALLTHROUGH;
5011	}
5012	else
5013	{
5014	/* The general case. Output code for the target of the transition
5015	in braces. This will not invalidate any of the xN variables
5016	that are already valid, but we mustn't rely on any that are
5017	set by the "if" body. */
5018	auto_vec <bool, 32> old_seen;
5019	old_seen.safe_splice (src: os->seen_vars);
5020
5021	printf_indent (indent: indent + 2, format: "{\n");
5022	print_state (os, s: trans->to, indent: indent + 4, is_final);
5023	printf_indent (indent: indent + 2, format: "}\n");
5024
5025	os->seen_vars.truncate (size: 0);
5026	os->seen_vars.splice (src: old_seen);
5027	return ES_FALLTHROUGH;
5028	}
5029	}
5030	else
5031	{
5032	/* Output the decision as a switch statement. */
5033	printf_indent (indent, format: "switch (");
5034	print_nonbool_test (os, test: d->test);
5035	printf (format: ")\n");
5036
5037	/* Each case statement starts with the same set of valid variables.
5038	These are also the only variables will be valid on fallthrough. */
5039	auto_vec <bool, 32> old_seen;
5040	old_seen.safe_splice (src: os->seen_vars);
5041
5042	printf_indent (indent: indent + 2, format: "{\n");
5043	for (transition *trans = d->first; trans; trans = trans->next)
5044	{
5045	gcc_assert (!trans->is_param);
5046	if (mark_optional_transitions_p && trans->optional)
5047	printf_indent (indent: indent + 2, format: "/* OPTIONAL CASE */\n");
5048	for (int_set::iterator j = trans->labels.begin ();
5049	j != trans->labels.end (); ++j)
5050	{
5051	printf_indent (indent: indent + 2, format: "case ");
5052	print_label_value (test: d->test, is_param: trans->is_param, value: *j);
5053	printf (format: ":\n");
5054	}
5055	if (print_state (os, s: trans->to, indent: indent + 4, is_final))
5056	{
5057	/* The state can fall through. Add an explicit break. */
5058	gcc_assert (!is_final);
5059	printf_indent (indent: indent + 4, format: "break;\n");
5060	}
5061	printf (format: "\n");
5062
5063	/* Restore the original set of valid variables. */
5064	os->seen_vars.truncate (size: 0);
5065	os->seen_vars.splice (src: old_seen);
5066	}
5067	/* Add a default case. */
5068	printf_indent (indent: indent + 2, format: "default:\n");
5069	if (is_final)
5070	printf_indent (indent: indent + 4, format: "return %s;\n",
5071	get_failure_return (type: os->type));
5072	else
5073	printf_indent (indent: indent + 4, format: "break;\n");
5074	printf_indent (indent: indent + 2, format: "}\n");
5075	return is_final ? ES_RETURNED : ES_FALLTHROUGH;
5076	}
5077	}
5078
5079	/* Make sure that OS has a position variable for POS. ROOT_P is true if
5080	POS is the root position for the routine. */
5081
5082	static void
5083	assign_position_var (output_state *os, position *pos, bool root_p)
5084	{
5085	unsigned int idx = os->id_to_var[pos->id];
5086	if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id)
5087	return;
5088	if (!root_p && pos->type != POS_PEEP2_INSN)
5089	assign_position_var (os, pos: pos->base, root_p: false);
5090	os->id_to_var[pos->id] = os->var_to_id.length ();
5091	os->var_to_id.safe_push (obj: pos->id);
5092	}
5093
5094	/* Make sure that OS has the position variables required by S. */
5095
5096	static void
5097	assign_position_vars (output_state *os, state *s)
5098	{
5099	for (decision *d = s->first; d; d = d->next)
5100	{
5101	/* Positions associated with operands can be read from the
5102	operands[] array. */
5103	if (d->test.pos && d->test.pos_operand < 0)
5104	assign_position_var (os, pos: d->test.pos, root_p: false);
5105	for (transition *trans = d->first; trans; trans = trans->next)
5106	assign_position_vars (os, s: trans->to);
5107	}
5108	}
5109
5110	/* Print the open brace and variable definitions for a routine that
5111	implements S. ROOT is the deepest rtx from which S can access all
5112	relevant parts of the first instruction it matches. Initialize OS
5113	so that every relevant position has an rtx variable xN and so that
5114	only ROOT's variable has a valid value. */
5115
5116	static void
5117	print_subroutine_start (output_state *os, state *s, position *root)
5118	{
5119	printf (format: "{\n rtx * const operands ATTRIBUTE_UNUSED"
5120	" = &recog_data.operand[0];\n");
5121	os->var_to_id.truncate (size: 0);
5122	os->seen_vars.truncate (size: 0);
5123	if (root)
5124	{
5125	/* Create a fake entry for position 0 so that an id_to_var of 0
5126	is always invalid. This also makes the xN variables naturally
5127	1-based rather than 0-based. */
5128	os->var_to_id.safe_push (obj: num_positions);
5129
5130	/* Associate ROOT with x1. */
5131	assign_position_var (os, pos: root, root_p: true);
5132
5133	/* Assign xN variables to all other relevant positions. */
5134	assign_position_vars (os, s);
5135
5136	/* Output the variable declarations (except for ROOT's, which is
5137	passed in as a parameter). */
5138	unsigned int num_vars = os->var_to_id.length ();
5139	if (num_vars > 2)
5140	{
5141	for (unsigned int i = 2; i < num_vars; ++i)
5142	/* Print 8 rtx variables to a line. */
5143	printf (format: "%s x%d",
5144	i == 2 ? " rtx" : (i - 2) % 8 == 0 ? ";\n rtx" : ",", i);
5145	printf (format: ";\n");
5146	}
5147
5148	/* Say that x1 is valid and the rest aren't. */
5149	os->seen_vars.safe_grow_cleared (len: num_vars, exact: true);
5150	os->seen_vars[1] = true;
5151	}
5152	if (os->type == SUBPATTERN || os->type == RECOG)
5153	printf (format: " int res ATTRIBUTE_UNUSED;\n");
5154	else
5155	printf (format: " rtx_insn *res ATTRIBUTE_UNUSED;\n");
5156	}
5157
5158	/* Output the definition of pattern routine ROUTINE. */
5159
5160	static void
5161	print_pattern (output_state *os, pattern_routine *routine)
5162	{
5163	printf (format: "\nstatic int\npattern%d (", routine->pattern_id);
5164	const char *sep = "";
5165	/* Add the top-level rtx parameter, if any. */
5166	if (routine->pos)
5167	{
5168	printf (format: "%srtx x1", sep);
5169	sep = ", ";
5170	}
5171	/* Add the optional parameters. */
5172	if (routine->insn_p)
5173	{
5174	/* We can't easily tell whether a C condition actually reads INSN,
5175	so add an ATTRIBUTE_UNUSED just in case. */
5176	printf (format: "%srtx_insn *insn ATTRIBUTE_UNUSED", sep);
5177	sep = ", ";
5178	}
5179	if (routine->pnum_clobbers_p)
5180	{
5181	printf (format: "%sint *pnum_clobbers", sep);
5182	sep = ", ";
5183	}
5184	/* Add the "i" parameters. */
5185	for (unsigned int i = 0; i < routine->param_types.length (); ++i)
5186	{
5187	printf (format: "%s%s i%d", sep,
5188	parameter_type_string (type: routine->param_types[i]), i + 1);
5189	sep = ", ";
5190	}
5191	printf (format: ")\n");
5192	os->type = SUBPATTERN;
5193	print_subroutine_start (os, s: routine->s, root: routine->pos);
5194	print_state (os, s: routine->s, indent: 2, is_final: true);
5195	printf (format: "}\n");
5196	}
5197
5198	/* Output a routine of type TYPE that implements S. PROC_ID is the
5199	number of the subroutine associated with S, or 0 if S is the main
5200	routine. */
5201
5202	static void
5203	print_subroutine (output_state *os, state *s, int proc_id)
5204	{
5205	printf (format: "\n");
5206	switch (os->type)
5207	{
5208	case SUBPATTERN:
5209	gcc_unreachable ();
5210
5211	case RECOG:
5212	if (proc_id)
5213	printf (format: "static int\nrecog_%d", proc_id);
5214	else
5215	printf (format: "int\nrecog");
5216	printf (format: " (rtx x1 ATTRIBUTE_UNUSED,\n"
5217	"\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5218	"\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n");
5219	break;
5220
5221	case SPLIT:
5222	if (proc_id)
5223	printf (format: "static rtx_insn *\nsplit_%d", proc_id);
5224	else
5225	printf (format: "rtx_insn *\nsplit_insns");
5226	printf (format: " (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n");
5227	break;
5228
5229	case PEEPHOLE2:
5230	if (proc_id)
5231	printf (format: "static rtx_insn *\npeephole2_%d", proc_id);
5232	else
5233	printf (format: "rtx_insn *\npeephole2_insns");
5234	printf (format: " (rtx x1 ATTRIBUTE_UNUSED,\n"
5235	"\trtx_insn *insn ATTRIBUTE_UNUSED,\n"
5236	"\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n");
5237	break;
5238	}
5239	print_subroutine_start (os, s, root: &root_pos);
5240	if (proc_id == 0)
5241	{
5242	printf (format: " recog_data.insn = NULL;\n");
5243	}
5244	print_state (os, s, indent: 2, is_final: true);
5245	printf (format: "}\n");
5246	}
5247
5248	/* Print out a routine of type TYPE that performs ROOT. */
5249
5250	static void
5251	print_subroutine_group (output_state *os, routine_type type, state *root)
5252	{
5253	os->type = type;
5254	if (use_subroutines_p)
5255	{
5256	/* Split ROOT up into smaller pieces, both for readability and to
5257	help the compiler. */
5258	auto_vec <state *> subroutines;
5259	find_subroutines (type, s: root, procs&: subroutines);
5260
5261	/* Output the subroutines (but not ROOT itself). */
5262	unsigned int i;
5263	state *s;
5264	FOR_EACH_VEC_ELT (subroutines, i, s)
5265	print_subroutine (os, s, proc_id: i + 1);
5266	}
5267	/* Output the main routine. */
5268	print_subroutine (os, s: root, proc_id: 0);
5269	}
5270
5271	/* Return the rtx pattern for the list of rtxes in a define_peephole2. */
5272
5273	static rtx
5274	get_peephole2_pattern (md_rtx_info *info)
5275	{
5276	int i, j;
5277	rtvec vec = XVEC (info->def, 0);
5278	rtx pattern = rtx_alloc (SEQUENCE);
5279	XVEC (pattern, 0) = rtvec_alloc (GET_NUM_ELEM (vec));
5280	for (i = j = 0; i < GET_NUM_ELEM (vec); i++)
5281	{
5282	rtx x = RTVEC_ELT (vec, i);
5283	/* Ignore scratch register requirements. */
5284	if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP)
5285	{
5286	XVECEXP (pattern, 0, j) = x;
5287	j++;
5288	}
5289	}
5290	XVECLEN (pattern, 0) = j;
5291	if (j == 0)
5292	error_at (info->loc, "empty define_peephole2");
5293	return pattern;
5294	}
5295
5296	/* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing
5297	rtx can be added automatically by add_clobbers. If so, update
5298	*ACCEPTANCE_PTR so that its num_clobbers field contains the number
5299	of such trailing rtxes and update *PATTERN_PTR so that it contains
5300	the pattern without those rtxes. */
5301
5302	static bool
5303	remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr)
5304	{
5305	int i;
5306	rtx new_pattern;
5307
5308	/* Find the last non-clobber in the parallel. */
5309	rtx pattern = *pattern_ptr;
5310	for (i = XVECLEN (pattern, 0); i > 0; i--)
5311	{
5312	rtx x = XVECEXP (pattern, 0, i - 1);
5313	if (GET_CODE (x) != CLOBBER
5314	|| (!REG_P (XEXP (x, 0))
5315	&& GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH))
5316	break;
5317	}
5318
5319	if (i == XVECLEN (pattern, 0))
5320	return false;
5321
5322	/* Build a similar insn without the clobbers. */
5323	if (i == 1)
5324	new_pattern = XVECEXP (pattern, 0, 0);
5325	else
5326	{
5327	new_pattern = rtx_alloc (PARALLEL);
5328	XVEC (new_pattern, 0) = rtvec_alloc (i);
5329	for (int j = 0; j < i; ++j)
5330	XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j);
5331	}
5332
5333	/* Recognize it. */
5334	acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i;
5335	*pattern_ptr = new_pattern;
5336	return true;
5337	}
5338
5339	int
5340	main (int argc, const char **argv)
5341	{
5342	state insn_root, split_root, peephole2_root;
5343
5344	progname = "genrecog";
5345
5346	if (!init_rtx_reader_args (argc, argv))
5347	return (FATAL_EXIT_CODE);
5348
5349	write_header ();
5350
5351	/* Read the machine description. */
5352
5353	md_rtx_info info;
5354	while (read_md_rtx (&info))
5355	{
5356	rtx def = info.def;
5357
5358	acceptance_type acceptance;
5359	acceptance.partial_p = false;
5360	acceptance.u.full.code = info.index;
5361
5362	rtx pattern;
5363	switch (GET_CODE (def))
5364	{
5365	case DEFINE_INSN:
5366	{
5367	/* Match the instruction in the original .md form. */
5368	acceptance.type = RECOG;
5369	acceptance.u.full.u.num_clobbers = 0;
5370	pattern = add_implicit_parallel (XVEC (def, 1));
5371	validate_pattern (pattern, info: &info, NULL_RTX, set_code: 0);
5372	match_pattern (s: &insn_root, info: &info, pattern, acceptance);
5373
5374	/* If the pattern is a PARALLEL with trailing CLOBBERs,
5375	allow recog_for_combine to match without the clobbers. */
5376	if (GET_CODE (pattern) == PARALLEL
5377	&& remove_clobbers (acceptance_ptr: &acceptance, pattern_ptr: &pattern))
5378	match_pattern (s: &insn_root, info: &info, pattern, acceptance);
5379	break;
5380	}
5381
5382	case DEFINE_SPLIT:
5383	acceptance.type = SPLIT;
5384	pattern = add_implicit_parallel (XVEC (def, 0));
5385	validate_pattern (pattern, info: &info, NULL_RTX, set_code: 0);
5386	match_pattern (s: &split_root, info: &info, pattern, acceptance);
5387
5388	/* Declare the gen_split routine that we'll call if the
5389	pattern matches. The definition comes from insn-emit.cc. */
5390	printf (format: "extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n",
5391	info.index);
5392	break;
5393
5394	case DEFINE_PEEPHOLE2:
5395	acceptance.type = PEEPHOLE2;
5396	pattern = get_peephole2_pattern (info: &info);
5397	validate_pattern (pattern, info: &info, NULL_RTX, set_code: 0);
5398	match_pattern (s: &peephole2_root, info: &info, pattern, acceptance);
5399
5400	/* Declare the gen_peephole2 routine that we'll call if the
5401	pattern matches. The definition comes from insn-emit.cc. */
5402	printf (format: "extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n",
5403	info.index);
5404	break;
5405
5406	default:
5407	/* do nothing */;
5408	}
5409	}
5410
5411	if (have_error)
5412	return FATAL_EXIT_CODE;
5413
5414	puts (s: "\n\n");
5415
5416	/* Optimize each routine in turn. */
5417	optimize_subroutine_group (type: "recog", root: &insn_root);
5418	optimize_subroutine_group (type: "split_insns", root: &split_root);
5419	optimize_subroutine_group (type: "peephole2_insns", root: &peephole2_root);
5420
5421	output_state os;
5422	os.id_to_var.safe_grow_cleared (len: num_positions, exact: true);
5423
5424	if (use_pattern_routines_p)
5425	{
5426	/* Look for common patterns and split them out into subroutines. */
5427	auto_vec <merge_state_info> states;
5428	states.safe_push (obj: &insn_root);
5429	states.safe_push (obj: &split_root);
5430	states.safe_push (obj: &peephole2_root);
5431	split_out_patterns (states);
5432
5433	/* Print out the routines that we just created. */
5434	unsigned int i;
5435	pattern_routine *routine;
5436	FOR_EACH_VEC_ELT (patterns, i, routine)
5437	print_pattern (os: &os, routine);
5438	}
5439
5440	/* Print out the matching routines. */
5441	print_subroutine_group (os: &os, type: RECOG, root: &insn_root);
5442	print_subroutine_group (os: &os, type: SPLIT, root: &split_root);
5443	print_subroutine_group (os: &os, type: PEEPHOLE2, root: &peephole2_root);
5444
5445	fflush (stdout);
5446	return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE);
5447	}
5448