1	/* Support routines for the various generation passes.
2	Copyright (C) 2000-2024 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	#include "bconfig.h"
21	#define INCLUDE_STRING
22	#define INCLUDE_VECTOR
23	#include "system.h"
24	#include "coretypes.h"
25	#include "tm.h"
26	#include "rtl.h"
27	#include "obstack.h"
28	#include "errors.h"
29	#include "read-md.h"
30	#include "gensupport.h"
31	#include "vec.h"
32
33	#define MAX_OPERANDS 40
34
35	static rtx operand_data[MAX_OPERANDS];
36	static rtx match_operand_entries_in_pattern[MAX_OPERANDS];
37	static char used_operands_numbers[MAX_OPERANDS];
38	/* List of entries which are part of the new syntax. */
39	hash_set<rtx> compact_syntax;
40
41
42	/* In case some macros used by files we include need it, define this here. */
43	int target_flags;
44
45	int insn_elision = 1;
46
47	static struct obstack obstack;
48	struct obstack *rtl_obstack = &obstack;
49
50	/* Counter for named patterns and INSN_CODEs. */
51	static int insn_sequence_num;
52
53	/* Counter for define_splits. */
54	static int split_sequence_num;
55
56	/* Counter for define_peephole2s. */
57	static int peephole2_sequence_num;
58
59	static int predicable_default;
60	static const char *predicable_true;
61	static const char *predicable_false;
62
63	static const char *subst_true = "yes";
64	static const char *subst_false = "no";
65
66	static htab_t condition_table;
67
68	/* We initially queue all patterns, process the define_insn,
69	define_cond_exec and define_subst patterns, then return
70	them one at a time. */
71
72	class queue_elem
73	{
74	public:
75	rtx data;
76	file_location loc;
77	class queue_elem *next;
78	/* In a DEFINE_INSN that came from a DEFINE_INSN_AND_SPLIT or
79	DEFINE_INSN_AND_REWRITE, SPLIT points to the generated DEFINE_SPLIT. */
80	class queue_elem *split;
81	};
82
83	#define MNEMONIC_ATTR_NAME "mnemonic"
84	#define MNEMONIC_HTAB_SIZE 1024
85
86	static class queue_elem *define_attr_queue;
87	static class queue_elem **define_attr_tail = &define_attr_queue;
88	static class queue_elem *define_pred_queue;
89	static class queue_elem **define_pred_tail = &define_pred_queue;
90	static class queue_elem *define_insn_queue;
91	static class queue_elem **define_insn_tail = &define_insn_queue;
92	static class queue_elem *define_cond_exec_queue;
93	static class queue_elem **define_cond_exec_tail = &define_cond_exec_queue;
94	static class queue_elem *define_subst_queue;
95	static class queue_elem **define_subst_tail = &define_subst_queue;
96	static class queue_elem *other_queue;
97	static class queue_elem **other_tail = &other_queue;
98	static class queue_elem *define_subst_attr_queue;
99	static class queue_elem **define_subst_attr_tail = &define_subst_attr_queue;
100
101	/* Mapping from DEFINE_* rtxes to their location in the source file. */
102	static hash_map <rtx, file_location> *rtx_locs;
103
104	static void remove_constraints (rtx);
105
106	static int is_predicable (class queue_elem *);
107	static void identify_predicable_attribute (void);
108	static int n_alternatives (const char *);
109	static void collect_insn_data (rtx, int *, int *);
110	static const char *alter_test_for_insn (class queue_elem *,
111	class queue_elem *);
112	static char *shift_output_template (char *, const char *, int);
113	static const char *alter_output_for_insn (class queue_elem *,
114	class queue_elem *,
115	int, int);
116	static void process_one_cond_exec (class queue_elem *);
117	static void process_define_cond_exec (void);
118	static void init_predicate_table (void);
119	static void record_insn_name (int, const char *);
120
121	static bool has_subst_attribute (class queue_elem *, class queue_elem *);
122	static const char * alter_output_for_subst_insn (rtx, int);
123	static void alter_attrs_for_subst_insn (class queue_elem *, int);
124	static void process_substs_on_one_elem (class queue_elem *,
125	class queue_elem *);
126	static rtx subst_dup (rtx, int, int);
127	static void process_define_subst (void);
128
129	static const char * duplicate_alternatives (const char *, int);
130	static const char * duplicate_each_alternative (const char * str, int n_dup);
131
132	typedef const char * (*constraints_handler_t) (const char *, int);
133	static rtx alter_constraints (rtx, int, constraints_handler_t);
134	static rtx adjust_operands_numbers (rtx);
135	static rtx replace_duplicating_operands_in_pattern (rtx);
136
137	/* Make a version of gen_rtx_CONST_INT so that GEN_INT can be used in
138	the gensupport programs. */
139
140	rtx
141	gen_rtx_CONST_INT (machine_mode ARG_UNUSED (mode),
142	HOST_WIDE_INT arg)
143	{
144	rtx rt = rtx_alloc (CONST_INT);
145
146	XWINT (rt, 0) = arg;
147	return rt;
148	}
149
150	/* Return the rtx pattern specified by the list of rtxes in a
151	define_insn or define_split. */
152
153	rtx
154	add_implicit_parallel (rtvec vec)
155	{
156	if (GET_NUM_ELEM (vec) == 1)
157	return RTVEC_ELT (vec, 0);
158	else
159	{
160	rtx pattern = rtx_alloc (PARALLEL);
161	XVEC (pattern, 0) = vec;
162	return pattern;
163	}
164	}
165
166	/* Predicate handling.
167
168	We construct from the machine description a table mapping each
169	predicate to a list of the rtl codes it can possibly match. The
170	function 'maybe_both_true' uses it to deduce that there are no
171	expressions that can be matches by certain pairs of tree nodes.
172	Also, if a predicate can match only one code, we can hardwire that
173	code into the node testing the predicate.
174
175	Some predicates are flagged as special. validate_pattern will not
176	warn about modeless match_operand expressions if they have a
177	special predicate. Predicates that allow only constants are also
178	treated as special, for this purpose.
179
180	validate_pattern will warn about predicates that allow non-lvalues
181	when they appear in destination operands.
182
183	Calculating the set of rtx codes that can possibly be accepted by a
184	predicate expression EXP requires a three-state logic: any given
185	subexpression may definitively accept a code C (Y), definitively
186	reject a code C (N), or may have an indeterminate effect (I). N
187	and I is N; Y or I is Y; Y and I, N or I are both I. Here are full
188	truth tables.
189
190	a b a&b a|b
191	Y Y Y Y
192	N Y N Y
193	N N N N
194	I Y I Y
195	I N N I
196	I I I I
197
198	We represent Y with 1, N with 0, I with 2. If any code is left in
199	an I state by the complete expression, we must assume that that
200	code can be accepted. */
201
202	#define N 0
203	#define Y 1
204	#define I 2
205
206	#define TRISTATE_AND(a,b) \
207	((a) == I ? ((b) == N ? N : I) : \
208	(b) == I ? ((a) == N ? N : I) : \
209	(a) && (b))
210
211	#define TRISTATE_OR(a,b) \
212	((a) == I ? ((b) == Y ? Y : I) : \
213	(b) == I ? ((a) == Y ? Y : I) : \
214	(a) || (b))
215
216	#define TRISTATE_NOT(a) \
217	((a) == I ? I : !(a))
218
219	/* 0 means no warning about that code yet, 1 means warned. */
220	static char did_you_mean_codes[NUM_RTX_CODE];
221
222	/* Recursively calculate the set of rtx codes accepted by the
223	predicate expression EXP, writing the result to CODES. LOC is
224	the .md file location of the directive containing EXP. */
225
226	void
227	compute_test_codes (rtx exp, file_location loc, char *codes)
228	{
229	char op0_codes[NUM_RTX_CODE];
230	char op1_codes[NUM_RTX_CODE];
231	char op2_codes[NUM_RTX_CODE];
232	int i;
233
234	switch (GET_CODE (exp))
235	{
236	case AND:
237	compute_test_codes (XEXP (exp, 0), loc, codes: op0_codes);
238	compute_test_codes (XEXP (exp, 1), loc, codes: op1_codes);
239	for (i = 0; i < NUM_RTX_CODE; i++)
240	codes[i] = TRISTATE_AND (op0_codes[i], op1_codes[i]);
241	break;
242
243	case IOR:
244	compute_test_codes (XEXP (exp, 0), loc, codes: op0_codes);
245	compute_test_codes (XEXP (exp, 1), loc, codes: op1_codes);
246	for (i = 0; i < NUM_RTX_CODE; i++)
247	codes[i] = TRISTATE_OR (op0_codes[i], op1_codes[i]);
248	break;
249	case NOT:
250	compute_test_codes (XEXP (exp, 0), loc, codes: op0_codes);
251	for (i = 0; i < NUM_RTX_CODE; i++)
252	codes[i] = TRISTATE_NOT (op0_codes[i]);
253	break;
254
255	case IF_THEN_ELSE:
256	/* a ? b : c accepts the same codes as (a & b) | (!a & c). */
257	compute_test_codes (XEXP (exp, 0), loc, codes: op0_codes);
258	compute_test_codes (XEXP (exp, 1), loc, codes: op1_codes);
259	compute_test_codes (XEXP (exp, 2), loc, codes: op2_codes);
260	for (i = 0; i < NUM_RTX_CODE; i++)
261	codes[i] = TRISTATE_OR (TRISTATE_AND (op0_codes[i], op1_codes[i]),
262	TRISTATE_AND (TRISTATE_NOT (op0_codes[i]),
263	op2_codes[i]));
264	break;
265
266	case MATCH_CODE:
267	/* MATCH_CODE allows a specified list of codes. However, if it
268	does not apply to the top level of the expression, it does not
269	constrain the set of codes for the top level. */
270	if (XSTR (exp, 1)[0] != '\0')
271	{
272	memset (s: codes, Y, NUM_RTX_CODE);
273	break;
274	}
275
276	memset (s: codes, N, NUM_RTX_CODE);
277	{
278	const char *next_code = XSTR (exp, 0);
279	const char *code;
280
281	if (*next_code == '\0')
282	{
283	error_at (loc, "empty match_code expression");
284	break;
285	}
286
287	while ((code = scan_comma_elt (&next_code)) != 0)
288	{
289	size_t n = next_code - code;
290	int found_it = 0;
291
292	for (i = 0; i < NUM_RTX_CODE; i++)
293	if (!strncmp (s1: code, GET_RTX_NAME (i), n: n)
294	&& GET_RTX_NAME (i)[n] == '\0')
295	{
296	codes[i] = Y;
297	found_it = 1;
298	break;
299	}
300	if (!found_it)
301	{
302	error_at (loc, "match_code \"%.*s\" matches nothing",
303	(int) n, code);
304	for (i = 0; i < NUM_RTX_CODE; i++)
305	if (!strncasecmp (s1: code, GET_RTX_NAME (i), n: n)
306	&& GET_RTX_NAME (i)[n] == '\0'
307	&& !did_you_mean_codes[i])
308	{
309	did_you_mean_codes[i] = 1;
310	message_at (loc, "(did you mean \"%s\"?)",
311	GET_RTX_NAME (i));
312	}
313	}
314	}
315	}
316	break;
317
318	case MATCH_OPERAND:
319	/* MATCH_OPERAND disallows the set of codes that the named predicate
320	disallows, and is indeterminate for the codes that it does allow. */
321	{
322	struct pred_data *p = lookup_predicate (XSTR (exp, 1));
323	if (!p)
324	{
325	error_at (loc, "reference to unknown predicate '%s'",
326	XSTR (exp, 1));
327	break;
328	}
329	for (i = 0; i < NUM_RTX_CODE; i++)
330	codes[i] = p->codes[i] ? I : N;
331	}
332	break;
333
334
335	case MATCH_TEST:
336	/* (match_test WHATEVER) is completely indeterminate. */
337	memset (s: codes, I, NUM_RTX_CODE);
338	break;
339
340	default:
341	error_at (loc, "'%s' cannot be used in predicates or constraints",
342	GET_RTX_NAME (GET_CODE (exp)));
343	memset (s: codes, I, NUM_RTX_CODE);
344	break;
345	}
346	}
347
348	#undef TRISTATE_OR
349	#undef TRISTATE_AND
350	#undef TRISTATE_NOT
351
352	/* Return true if NAME is a valid predicate name. */
353
354	static bool
355	valid_predicate_name_p (const char *name)
356	{
357	const char *p;
358
359	if (!ISALPHA (name[0]) && name[0] != '_')
360	return false;
361	for (p = name + 1; *p; p++)
362	if (!ISALNUM (*p) && *p != '_')
363	return false;
364	return true;
365	}
366
367	/* Process define_predicate directive DESC, which appears at location LOC.
368	Compute the set of codes that can be matched, and record this as a known
369	predicate. */
370
371	static void
372	process_define_predicate (rtx desc, file_location loc)
373	{
374	struct pred_data *pred;
375	char codes[NUM_RTX_CODE];
376	int i;
377
378	if (!valid_predicate_name_p (XSTR (desc, 0)))
379	{
380	error_at (loc, "%s: predicate name must be a valid C function name",
381	XSTR (desc, 0));
382	return;
383	}
384
385	pred = XCNEW (struct pred_data);
386	pred->name = XSTR (desc, 0);
387	pred->exp = XEXP (desc, 1);
388	pred->c_block = XSTR (desc, 2);
389	if (GET_CODE (desc) == DEFINE_SPECIAL_PREDICATE)
390	pred->special = true;
391
392	compute_test_codes (XEXP (desc, 1), loc, codes);
393
394	for (i = 0; i < NUM_RTX_CODE; i++)
395	if (codes[i] != N)
396	add_predicate_code (pred, (enum rtx_code) i);
397
398	add_predicate (pred);
399	}
400	#undef I
401	#undef N
402	#undef Y
403
404	/* Maps register filter conditions to the associated filter identifier. */
405	static hash_map<nofree_string_hash, unsigned int> register_filter_map;
406
407	/* All register filter conditions, indexed by identifier. */
408	vec<const char *> register_filters;
409
410	/* Return the unique identifier for filter condition FILTER. Identifiers
411	are assigned automatically when the define_register_constraint is
412	parsed. */
413
414	unsigned int
415	get_register_filter_id (const char *filter)
416	{
417	unsigned int *slot = register_filter_map.get (k: filter);
418	gcc_assert (slot);
419	return *slot;
420	}
421
422	/* Process define_register_constraint directive DESC, at location LOC. */
423
424	static void
425	process_define_register_constraint (rtx desc, file_location loc)
426	{
427	/* Assign identifiers to each unique register filter condition. */
428	if (const char *filter = XSTR (desc, 3))
429	{
430	bool existed = false;
431	unsigned int &id = register_filter_map.get_or_insert (k: filter, existed: &existed);
432	if (!existed)
433	{
434	id = register_filters.length ();
435	if (id == 32)
436	fatal_at (loc, "too many distinct register filters, maximum"
437	" is 32");
438	register_filters.safe_push (obj: filter);
439	}
440	}
441	}
442
443	/* Queue PATTERN on LIST_TAIL. Return the address of the new queue
444	element. */
445
446	static class queue_elem *
447	queue_pattern (rtx pattern, class queue_elem ***list_tail,
448	file_location loc)
449	{
450	class queue_elem *e = XNEW (class queue_elem);
451	e->data = pattern;
452	e->loc = loc;
453	e->next = NULL;
454	e->split = NULL;
455	**list_tail = e;
456	*list_tail = &e->next;
457	return e;
458	}
459
460	/* Remove element ELEM from QUEUE. */
461	static void
462	remove_from_queue (class queue_elem *elem, class queue_elem **queue)
463	{
464	class queue_elem *prev, *e;
465	prev = NULL;
466	for (e = *queue; e ; e = e->next)
467	{
468	if (e == elem)
469	break;
470	prev = e;
471	}
472	if (e == NULL)
473	return;
474
475	if (prev)
476	prev->next = elem->next;
477	else
478	*queue = elem->next;
479	}
480
481	/* Build a define_attr for an binary attribute with name NAME and
482	possible values "yes" and "no", and queue it. */
483	static void
484	add_define_attr (const char *name)
485	{
486	class queue_elem *e = XNEW (class queue_elem);
487	rtx t1 = rtx_alloc (DEFINE_ATTR);
488	XSTR (t1, 0) = name;
489	XSTR (t1, 1) = "no,yes";
490	XEXP (t1, 2) = rtx_alloc (CONST_STRING);
491	XSTR (XEXP (t1, 2), 0) = "yes";
492	e->data = t1;
493	e->loc = file_location ("built-in", -1, -1);
494	e->next = define_attr_queue;
495	define_attr_queue = e;
496
497	}
498
499	/* Recursively remove constraints from an rtx. */
500
501	static void
502	remove_constraints (rtx part)
503	{
504	int i, j;
505	const char *format_ptr;
506
507	if (part == 0)
508	return;
509
510	if (GET_CODE (part) == MATCH_OPERAND)
511	XSTR (part, 2) = "";
512	else if (GET_CODE (part) == MATCH_SCRATCH)
513	XSTR (part, 1) = "";
514
515	format_ptr = GET_RTX_FORMAT (GET_CODE (part));
516
517	for (i = 0; i < GET_RTX_LENGTH (GET_CODE (part)); i++)
518	switch (*format_ptr++)
519	{
520	case 'e':
521	case 'u':
522	remove_constraints (XEXP (part, i));
523	break;
524	case 'E':
525	if (XVEC (part, i) != NULL)
526	for (j = 0; j < XVECLEN (part, i); j++)
527	remove_constraints (XVECEXP (part, i, j));
528	break;
529	}
530	}
531
532	/* Recursively replace MATCH_OPERANDs with MATCH_DUPs and MATCH_OPERATORs
533	with MATCH_OP_DUPs in X. */
534
535	static rtx
536	replace_operands_with_dups (rtx x)
537	{
538	if (x == 0)
539	return x;
540
541	rtx newx;
542	if (GET_CODE (x) == MATCH_OPERAND)
543	{
544	newx = rtx_alloc (MATCH_DUP);
545	XINT (newx, 0) = XINT (x, 0);
546	x = newx;
547	}
548	else if (GET_CODE (x) == MATCH_OPERATOR)
549	{
550	newx = rtx_alloc (MATCH_OP_DUP);
551	XINT (newx, 0) = XINT (x, 0);
552	XVEC (newx, 1) = XVEC (x, 2);
553	x = newx;
554	}
555	else
556	newx = shallow_copy_rtx (x);
557
558	const char *format_ptr = GET_RTX_FORMAT (GET_CODE (x));
559	for (int i = 0; i < GET_RTX_LENGTH (GET_CODE (x)); i++)
560	switch (*format_ptr++)
561	{
562	case 'e':
563	case 'u':
564	XEXP (newx, i) = replace_operands_with_dups (XEXP (x, i));
565	break;
566	case 'E':
567	if (XVEC (x, i) != NULL)
568	{
569	XVEC (newx, i) = rtvec_alloc (XVECLEN (x, i));
570	for (int j = 0; j < XVECLEN (x, i); j++)
571	XVECEXP (newx, i, j)
572	= replace_operands_with_dups (XVECEXP (x, i, j));
573	}
574	break;
575	}
576	return newx;
577	}
578
579	/* Convert matching pattern VEC from a DEFINE_INSN_AND_REWRITE into
580	a sequence that should be generated by the splitter. */
581
582	static rtvec
583	gen_rewrite_sequence (rtvec vec)
584	{
585	rtvec new_vec = rtvec_alloc (1);
586	rtx x = add_implicit_parallel (vec);
587	RTVEC_ELT (new_vec, 0) = replace_operands_with_dups (x);
588	return new_vec;
589	}
590
591	/* The following is for handling the compact syntax for constraints and
592	attributes.
593
594	The normal syntax looks like this:
595
596	...
597	(match_operand: 0 "s_register_operand" "r,I,k")
598	(match_operand: 2 "s_register_operand" "r,k,I")
599	...
600	"@
601	<asm>
602	<asm>
603	<asm>"
604	...
605	(set_attr "length" "4,8,8")
606
607	The compact syntax looks like this:
608
609	...
610	(match_operand: 0 "s_register_operand")
611	(match_operand: 2 "s_register_operand")
612	...
613	{@ [cons: 0, 2; attrs: length]
614	[r,r; 4] <asm>
615	[I,k; 8] <asm>
616	[k,I; 8] <asm>
617	}
618	...
619	[<other attributes>]
620
621	This is the only place where this syntax needs to be handled. Relevant
622	patterns are transformed from compact to the normal syntax before they are
623	queued, so none of the gen* programs need to know about this syntax at all.
624
625	Conversion process (convert_syntax):
626
627	0) Check that pattern actually uses new syntax (check for {@ ... }).
628
629	1) Get the "layout", i.e. the "[cons: 0 2; attrs: length]" from the above
630	example. cons must come first; both are optional. Set up two vecs,
631	convec and attrvec, for holding the results of the transformation.
632
633	2) For each alternative: parse the list of constraints and/or attributes,
634	and enqueue them in the relevant lists in convec and attrvec. By the end
635	of this process, convec[N].con and attrvec[N].con should contain regular
636	syntax constraint/attribute lists like "r,I,k". Copy the asm to a string
637	as we go.
638
639	3) Search the rtx and write the constraint and attribute lists into the
640	correct places. Write the asm back into the template. */
641
642	/* Helper class for shuffling constraints/attributes in convert_syntax and
643	add_constraints/add_attributes. This includes commas but not whitespace. */
644
645	class conlist {
646	private:
647	std::string con;
648
649	public:
650	std::string name;
651	int idx = -1;
652
653	conlist () = default;
654
655	/* [ns..ns + len) should be a string with the id of the rtx to match
656	i.e. if rtx is the relevant match_operand or match_scratch then
657	[ns..ns + len) should equal itoa (XINT (rtx, 0)), and if set_attr then
658	[ns..ns + len) should equal XSTR (rtx, 0). */
659	conlist (const char *ns, unsigned int len, bool numeric)
660	{
661	/* Trim leading whitespaces. */
662	while (len > 0 && ISBLANK (*ns))
663	{
664	ns++;
665	len--;
666	}
667
668	/* Trim trailing whitespace. */
669	for (int i = len - 1; i >= 0; i--, len--)
670	if (!ISBLANK (ns[i]))
671	break;
672
673	/* Parse off any modifiers. */
674	while (len > 0 && !ISALNUM (*ns))
675	{
676	con += *(ns++);
677	len--;
678	}
679
680	name.assign (s: ns, n: len);
681	if (numeric)
682	idx = strtol (nptr: name.c_str (), endptr: (char **)NULL, base: 10);
683	}
684
685	/* Adds a character to the end of the string. */
686	void add (char c)
687	{
688	con += c;
689	}
690
691	/* Output the string in the form of a brand-new char *, then effectively
692	clear the internal string by resetting len to 0. */
693	char *out ()
694	{
695	/* Final character is always a trailing comma, so strip it out. */
696	char *q = xstrndup (con.c_str (), con.size () - 1);
697	con.clear ();
698	return q;
699	}
700	};
701
702	typedef std::vector<conlist> vec_conlist;
703
704	/* Add constraints to an rtx. This function is similar to remove_constraints.
705	Errors if adding the constraints would overwrite existing constraints. */
706
707	static void
708	add_constraints (rtx part, file_location loc, vec_conlist &cons)
709	{
710	const char *format_ptr;
711
712	if (part == NULL_RTX)
713	return;
714
715	/* If match_op or match_scr, check if we have the right one, and if so, copy
716	over the constraint list. */
717	if (GET_CODE (part) == MATCH_OPERAND || GET_CODE (part) == MATCH_SCRATCH)
718	{
719	int field = GET_CODE (part) == MATCH_OPERAND ? 2 : 1;
720	unsigned id = XINT (part, 0);
721
722	if (id >= cons.size () || cons[id].idx == -1)
723	return;
724
725	if (XSTR (part, field)[0] != '\0')
726	{
727	error_at (loc, "can't mix normal and compact constraint syntax");
728	return;
729	}
730	XSTR (part, field) = cons[id].out ();
731	cons[id].idx = -1;
732	}
733
734	format_ptr = GET_RTX_FORMAT (GET_CODE (part));
735
736	/* Recursively search the rtx. */
737	for (int i = 0; i < GET_RTX_LENGTH (GET_CODE (part)); i++)
738	switch (*format_ptr++)
739	{
740	case 'e':
741	case 'u':
742	add_constraints (XEXP (part, i), loc, cons);
743	break;
744	case 'E':
745	if (XVEC (part, i) != NULL)
746	for (int j = 0; j < XVECLEN (part, i); j++)
747	add_constraints (XVECEXP (part, i, j), loc, cons);
748	break;
749	default:
750	continue;
751	}
752	}
753
754	/* Add ATTRS to definition X's attribute list. */
755
756	static void
757	add_attributes (rtx x, vec_conlist &attrs)
758	{
759	unsigned int attr_index = GET_CODE (x) == DEFINE_INSN ? 4 : 3;
760	rtvec orig = XVEC (x, attr_index);
761	if (orig)
762	{
763	size_t n_curr = XVECLEN (x, attr_index);
764	rtvec copy = rtvec_alloc (n_curr + attrs.size ());
765
766	/* Create a shallow copy of existing entries. */
767	memcpy (dest: &copy->elem[attrs.size ()], src: &orig->elem[0],
768	n: sizeof (rtx) * n_curr);
769	XVEC (x, attr_index) = copy;
770	}
771	else
772	XVEC (x, attr_index) = rtvec_alloc (attrs.size ());
773
774	/* Create the new elements. */
775	for (unsigned i = 0; i < attrs.size (); i++)
776	{
777	rtx attr = rtx_alloc (SET_ATTR);
778	XSTR (attr, 0) = xstrdup (attrs[i].name.c_str ());
779	XSTR (attr, 1) = attrs[i].out ();
780	XVECEXP (x, attr_index, i) = attr;
781	}
782	}
783
784	/* Consumes spaces and tabs. */
785
786	static inline void
787	skip_spaces (const char **str)
788	{
789	while (ISBLANK (**str))
790	(*str)++;
791	}
792
793	/* Consumes the given character, if it's there. */
794
795	static inline bool
796	expect_char (const char **str, char c)
797	{
798	if (**str != c)
799	return false;
800	(*str)++;
801	return true;
802	}
803
804	/* Parses the section layout that follows a "{@" if using new syntax. Builds
805	a vector for a single section. E.g. if we have "attrs: length, arch]..."
806	then list will have two elements, the first for "length" and the second
807	for "arch". */
808
809	static void
810	parse_section_layout (file_location loc, const char **templ, const char *label,
811	vec_conlist &list, bool numeric)
812	{
813	const char *name_start;
814	size_t label_len = strlen (s: label);
815	if (strncmp (s1: label, s2: *templ, n: label_len) == 0)
816	{
817	*templ += label_len;
818
819	/* Gather the names. */
820	while (**templ != ';' && **templ != ']')
821	{
822	skip_spaces (str: templ);
823	name_start = *templ;
824	int len = 0;
825	char val = (*templ)[len];
826	while (val != ',' && val != ';' && val != ']')
827	{
828	if (val == 0 || val == '\n')
829	fatal_at (loc, "missing ']'");
830	val = (*templ)[++len];
831	}
832	*templ += len;
833	if (val == ',')
834	(*templ)++;
835	list.push_back (x: conlist (name_start, len, numeric));
836	}
837	}
838	}
839
840	/* Parse a section, a section is defined as a named space separated list, e.g.
841
842	foo: a, b, c
843
844	is a section named "foo" with entries a, b and c. */
845
846	static void
847	parse_section (const char **templ, unsigned int n_elems, unsigned int alt_no,
848	vec_conlist &list, file_location loc, const char *name)
849	{
850	unsigned int i;
851
852	/* Go through the list, one character at a time, adding said character
853	to the correct string. */
854	for (i = 0; **templ != ']' && **templ != ';'; (*templ)++)
855	if (!ISBLANK (**templ))
856	{
857	if (**templ == 0 || **templ == '\n')
858	fatal_at (loc, "missing ']'");
859	list[i].add (c: **templ);
860	if (**templ == ',')
861	{
862	++i;
863	if (i == n_elems)
864	fatal_at (loc, "too many %ss in alternative %d: expected %d",
865	name, alt_no, n_elems);
866	}
867	}
868
869	if (i + 1 < n_elems)
870	fatal_at (loc, "too few %ss in alternative %d: expected %d, got %d",
871	name, alt_no, n_elems, i);
872
873	list[i].add (c: ',');
874	}
875
876	/* The compact syntax has more convience syntaxes. As such we post process
877	the lines to get them back to something the normal syntax understands. */
878
879	static void
880	preprocess_compact_syntax (file_location loc, int alt_no, std::string &line,
881	std::string &last_line)
882	{
883	/* Check if we're copying the last statement. */
884	if (line.find (s: "^") == 0 && line.size () == 1)
885	{
886	if (last_line.empty ())
887	fatal_at (loc, "found instruction to copy previous line (^) in"
888	"alternative %d but no previous line to copy", alt_no);
889	line = last_line;
890	return;
891	}
892
893	std::string result;
894	std::string buffer;
895	/* Check if we have << which means return c statement. */
896	if (line.find (s: "<<") == 0)
897	{
898	result.append (s: "* return ");
899	const char *chunk = line.c_str () + 2;
900	skip_spaces (str: &chunk);
901	result.append (s: chunk);
902	}
903	else
904	result.append (str: line);
905
906	line = result;
907	return;
908	}
909
910	/* Converts an rtx from compact syntax to normal syntax if possible. */
911
912	static void
913	convert_syntax (rtx x, file_location loc)
914	{
915	int alt_no;
916	unsigned int templ_index;
917	const char *templ;
918	vec_conlist tconvec, convec, attrvec;
919
920	templ_index = 3;
921	gcc_assert (GET_CODE (x) == DEFINE_INSN);
922
923	templ = XTMPL (x, templ_index);
924
925	/* Templates with constraints start with "{@". */
926	if (strncmp (s1: "*{@", s2: templ, n: 3))
927	return;
928
929	/* Get the layout for the template. */
930	templ += 3;
931	skip_spaces (str: &templ);
932
933	if (!expect_char (str: &templ, c: '['))
934	fatal_at (loc, "expecing `[' to begin section list");
935
936	skip_spaces (str: &templ);
937
938	parse_section_layout (loc, templ: &templ, label: "cons:", list&: tconvec, numeric: true);
939
940	if (*templ != ']')
941	{
942	if (*templ == ';')
943	skip_spaces (str: &(++templ));
944	parse_section_layout (loc, templ: &templ, label: "attrs:", list&: attrvec, numeric: false);
945	}
946
947	if (!expect_char (str: &templ, c: ']'))
948	fatal_at (loc, "expecting `]` to end section list - section list must have "
949	"cons first, attrs second");
950
951	/* We will write the un-constrainified template into new_templ. */
952	std::string new_templ;
953	new_templ.append (s: "@");
954
955	/* Skip to the first proper line. */
956	skip_spaces (str: &templ);
957	if (*templ == 0)
958	fatal_at (loc, "'{@...}' blocks must have at least one alternative");
959	if (*templ != '\n')
960	fatal_at (loc, "unexpected character '%c' after ']'", *templ);
961	templ++;
962
963	alt_no = 0;
964	std::string last_line;
965
966	/* Process the alternatives. */
967	while (*(templ - 1) != '\0')
968	{
969	/* Skip leading whitespace. */
970	std::string buffer;
971	skip_spaces (str: &templ);
972
973	/* Check if we're at the end. */
974	if (templ[0] == '}' && templ[1] == '\0')
975	break;
976
977	if (expect_char (str: &templ, c: '['))
978	{
979	new_templ += '\n';
980	new_templ.append (str: buffer);
981	/* Parse the constraint list, then the attribute list. */
982	if (tconvec.size () > 0)
983	parse_section (templ: &templ, n_elems: tconvec.size (), alt_no, list&: tconvec, loc,
984	name: "constraint");
985
986	if (attrvec.size () > 0)
987	{
988	if (tconvec.size () > 0 && !expect_char (str: &templ, c: ';'))
989	fatal_at (loc, "expected `;' to separate constraints "
990	"and attributes in alternative %d", alt_no);
991
992	parse_section (templ: &templ, n_elems: attrvec.size (), alt_no,
993	list&: attrvec, loc, name: "attribute");
994	}
995
996	if (!expect_char (str: &templ, c: ']'))
997	fatal_at (loc, "expected end of constraint/attribute list but "
998	"missing an ending `]' in alternative %d", alt_no);
999	}
1000	else if (templ[0] == '/' && templ[1] == '/')
1001	{
1002	templ += 2;
1003	/* Glob till newline or end of string. */
1004	while (*templ != '\n' || *templ != '\0')
1005	templ++;
1006
1007	/* Skip any newlines or whitespaces needed. */
1008	while (ISSPACE(*templ))
1009	templ++;
1010	continue;
1011	}
1012	else if (templ[0] == '/' && templ[1] == '*')
1013	{
1014	templ += 2;
1015	/* Glob till newline or end of multiline comment. */
1016	while (templ[0] != 0 && templ[0] != '*' && templ[1] != '/')
1017	templ++;
1018
1019	while (templ[0] != '*' || templ[1] != '/')
1020	{
1021	if (templ[0] == 0)
1022	fatal_at (loc, "unterminated '/*'");
1023	templ++;
1024	}
1025	templ += 2;
1026
1027	/* Skip any newlines or whitespaces needed. */
1028	while (ISSPACE(*templ))
1029	templ++;
1030	continue;
1031	}
1032	else
1033	fatal_at (loc, "expected constraint/attribute list at beginning of "
1034	"alternative %d but missing a starting `['", alt_no);
1035
1036	/* Skip whitespace between list and asm. */
1037	skip_spaces (str: &templ);
1038
1039	/* Copy asm to new template. */
1040	std::string line;
1041	while (*templ != '\n' && *templ != '\0')
1042	line += *templ++;
1043
1044	/* Apply any pre-processing needed to the line. */
1045	preprocess_compact_syntax (loc, alt_no, line, last_line);
1046	new_templ.append (str: line);
1047	last_line = line;
1048
1049	/* Normal "*..." syntax expects the closing quote to be on the final
1050	line of asm, whereas we allow the closing "}" to be on its own line.
1051	Postpone copying the '\n' until we know that there is another
1052	alternative in the list. */
1053	while (ISSPACE (*templ))
1054	templ++;
1055	++alt_no;
1056	}
1057
1058	/* Check for any duplicate cons entries and sort based on i. */
1059	for (auto e : tconvec)
1060	{
1061	unsigned idx = e.idx;
1062	if (idx >= convec.size ())
1063	convec.resize (new_size: idx + 1);
1064
1065	if (convec[idx].idx >= 0)
1066	fatal_at (loc, "duplicate cons number found: %d", idx);
1067	convec[idx] = e;
1068	}
1069	tconvec.clear ();
1070
1071	/* Write the constraints and attributes into their proper places. */
1072	if (convec.size () > 0)
1073	add_constraints (part: x, loc, cons&: convec);
1074
1075	if (attrvec.size () > 0)
1076	add_attributes (x, attrs&: attrvec);
1077
1078	/* Copy over the new un-constrainified template. */
1079	XTMPL (x, templ_index) = xstrdup (new_templ.c_str ());
1080
1081	/* Register for later checks during iterator expansions. */
1082	compact_syntax.add (k: x);
1083	}
1084
1085	/* Process a top level rtx in some way, queuing as appropriate. */
1086
1087	static void
1088	process_rtx (rtx desc, file_location loc)
1089	{
1090	switch (GET_CODE (desc))
1091	{
1092	case DEFINE_INSN:
1093	convert_syntax (x: desc, loc);
1094	queue_pattern (pattern: desc, list_tail: &define_insn_tail, loc);
1095	break;
1096
1097	case DEFINE_COND_EXEC:
1098	queue_pattern (pattern: desc, list_tail: &define_cond_exec_tail, loc);
1099	break;
1100
1101	case DEFINE_SUBST:
1102	queue_pattern (pattern: desc, list_tail: &define_subst_tail, loc);
1103	break;
1104
1105	case DEFINE_SUBST_ATTR:
1106	queue_pattern (pattern: desc, list_tail: &define_subst_attr_tail, loc);
1107	break;
1108
1109	case DEFINE_ATTR:
1110	case DEFINE_ENUM_ATTR:
1111	queue_pattern (pattern: desc, list_tail: &define_attr_tail, loc);
1112	break;
1113
1114	case DEFINE_PREDICATE:
1115	case DEFINE_SPECIAL_PREDICATE:
1116	process_define_predicate (desc, loc);
1117	queue_pattern (pattern: desc, list_tail: &define_pred_tail, loc);
1118	break;
1119
1120	case DEFINE_REGISTER_CONSTRAINT:
1121	process_define_register_constraint (desc, loc);
1122	queue_pattern (pattern: desc, list_tail: &define_pred_tail, loc);
1123	break;
1124
1125	case DEFINE_CONSTRAINT:
1126	case DEFINE_MEMORY_CONSTRAINT:
1127	case DEFINE_SPECIAL_MEMORY_CONSTRAINT:
1128	case DEFINE_RELAXED_MEMORY_CONSTRAINT:
1129	case DEFINE_ADDRESS_CONSTRAINT:
1130	queue_pattern (pattern: desc, list_tail: &define_pred_tail, loc);
1131	break;
1132
1133	case DEFINE_INSN_AND_SPLIT:
1134	case DEFINE_INSN_AND_REWRITE:
1135	{
1136	const char *split_cond;
1137	rtx split;
1138	rtvec attr;
1139	int i;
1140	class queue_elem *insn_elem;
1141	class queue_elem *split_elem;
1142	int split_code = (GET_CODE (desc) == DEFINE_INSN_AND_REWRITE ? 5 : 6);
1143
1144	/* Create a split with values from the insn_and_split. */
1145	split = rtx_alloc (DEFINE_SPLIT);
1146
1147	i = XVECLEN (desc, 1);
1148	XVEC (split, 0) = rtvec_alloc (i);
1149	while (--i >= 0)
1150	{
1151	XVECEXP (split, 0, i) = copy_rtx (XVECEXP (desc, 1, i));
1152	remove_constraints (XVECEXP (split, 0, i));
1153	}
1154
1155	/* If the split condition starts with "&&", append it to the
1156	insn condition to create the new split condition. */
1157	split_cond = XSTR (desc, 4);
1158	if (split_cond[0] == '&' && split_cond[1] == '&')
1159	{
1160	rtx_reader_ptr->copy_md_ptr_loc (new_ptr: split_cond + 2, old_ptr: split_cond);
1161	split_cond = rtx_reader_ptr->join_c_conditions (XSTR (desc, 2),
1162	cond2: split_cond + 2);
1163	}
1164	else if (GET_CODE (desc) == DEFINE_INSN_AND_REWRITE)
1165	error_at (loc, "the rewrite condition must start with `&&'");
1166	XSTR (split, 1) = split_cond;
1167	if (GET_CODE (desc) == DEFINE_INSN_AND_REWRITE)
1168	XVEC (split, 2) = gen_rewrite_sequence (XVEC (desc, 1));
1169	else
1170	XVEC (split, 2) = XVEC (desc, 5);
1171	XSTR (split, 3) = XSTR (desc, split_code);
1172
1173	/* Fix up the DEFINE_INSN. */
1174	attr = XVEC (desc, split_code + 1);
1175	PUT_CODE (desc, DEFINE_INSN);
1176	XVEC (desc, 4) = attr;
1177	convert_syntax (x: desc, loc);
1178
1179	/* Queue them. */
1180	insn_elem = queue_pattern (pattern: desc, list_tail: &define_insn_tail, loc);
1181	split_elem = queue_pattern (pattern: split, list_tail: &other_tail, loc);
1182	insn_elem->split = split_elem;
1183	break;
1184	}
1185
1186	default:
1187	queue_pattern (pattern: desc, list_tail: &other_tail, loc);
1188	break;
1189	}
1190	}
1191
1192	/* Return true if attribute PREDICABLE is true for ELEM, which holds
1193	a DEFINE_INSN. */
1194
1195	static int
1196	is_predicable (class queue_elem *elem)
1197	{
1198	rtvec vec = XVEC (elem->data, 4);
1199	const char *value;
1200	int i;
1201
1202	if (! vec)
1203	return predicable_default;
1204
1205	for (i = GET_NUM_ELEM (vec) - 1; i >= 0; --i)
1206	{
1207	rtx sub = RTVEC_ELT (vec, i);
1208	switch (GET_CODE (sub))
1209	{
1210	case SET_ATTR:
1211	if (strcmp (XSTR (sub, 0), s2: "predicable") == 0)
1212	{
1213	value = XSTR (sub, 1);
1214	goto found;
1215	}
1216	break;
1217
1218	case SET_ATTR_ALTERNATIVE:
1219	if (strcmp (XSTR (sub, 0), s2: "predicable") == 0)
1220	{
1221	error_at (elem->loc, "multiple alternatives for `predicable'");
1222	return 0;
1223	}
1224	break;
1225
1226	case SET:
1227	if (GET_CODE (SET_DEST (sub)) != ATTR
1228	|| strcmp (XSTR (SET_DEST (sub), 0), s2: "predicable") != 0)
1229	break;
1230	sub = SET_SRC (sub);
1231	if (GET_CODE (sub) == CONST_STRING)
1232	{
1233	value = XSTR (sub, 0);
1234	goto found;
1235	}
1236
1237	/* ??? It would be possible to handle this if we really tried.
1238	It's not easy though, and I'm not going to bother until it
1239	really proves necessary. */
1240	error_at (elem->loc, "non-constant value for `predicable'");
1241	return 0;
1242
1243	default:
1244	gcc_unreachable ();
1245	}
1246	}
1247
1248	return predicable_default;
1249
1250	found:
1251	/* Find out which value we're looking at. Multiple alternatives means at
1252	least one is predicable. */
1253	if (strchr (s: value, c: ',') != NULL)
1254	return 1;
1255	if (strcmp (s1: value, s2: predicable_true) == 0)
1256	return 1;
1257	if (strcmp (s1: value, s2: predicable_false) == 0)
1258	return 0;
1259
1260	error_at (elem->loc, "unknown value `%s' for `predicable' attribute", value);
1261	return 0;
1262	}
1263
1264	/* Find attribute SUBST in ELEM and assign NEW_VALUE to it. */
1265	static void
1266	change_subst_attribute (class queue_elem *elem,
1267	class queue_elem *subst_elem,
1268	const char *new_value)
1269	{
1270	rtvec attrs_vec = XVEC (elem->data, 4);
1271	const char *subst_name = XSTR (subst_elem->data, 0);
1272	int i;
1273
1274	if (! attrs_vec)
1275	return;
1276
1277	for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
1278	{
1279	rtx cur_attr = RTVEC_ELT (attrs_vec, i);
1280	if (GET_CODE (cur_attr) != SET_ATTR)
1281	continue;
1282	if (strcmp (XSTR (cur_attr, 0), s2: subst_name) == 0)
1283	{
1284	XSTR (cur_attr, 1) = new_value;
1285	return;
1286	}
1287	}
1288	}
1289
1290	/* Return true if ELEM has the attribute with the name of DEFINE_SUBST
1291	represented by SUBST_ELEM and this attribute has value SUBST_TRUE.
1292	DEFINE_SUBST isn't applied to patterns without such attribute. In other
1293	words, we suppose the default value of the attribute to be 'no' since it is
1294	always generated automatically in read-rtl.cc. */
1295	static bool
1296	has_subst_attribute (class queue_elem *elem, class queue_elem *subst_elem)
1297	{
1298	rtvec attrs_vec = XVEC (elem->data, 4);
1299	const char *value, *subst_name = XSTR (subst_elem->data, 0);
1300	int i;
1301
1302	if (! attrs_vec)
1303	return false;
1304
1305	for (i = GET_NUM_ELEM (attrs_vec) - 1; i >= 0; --i)
1306	{
1307	rtx cur_attr = RTVEC_ELT (attrs_vec, i);
1308	switch (GET_CODE (cur_attr))
1309	{
1310	case SET_ATTR:
1311	if (strcmp (XSTR (cur_attr, 0), s2: subst_name) == 0)
1312	{
1313	value = XSTR (cur_attr, 1);
1314	goto found;
1315	}
1316	break;
1317
1318	case SET:
1319	if (GET_CODE (SET_DEST (cur_attr)) != ATTR
1320	|| strcmp (XSTR (SET_DEST (cur_attr), 0), s2: subst_name) != 0)
1321	break;
1322	cur_attr = SET_SRC (cur_attr);
1323	if (GET_CODE (cur_attr) == CONST_STRING)
1324	{
1325	value = XSTR (cur_attr, 0);
1326	goto found;
1327	}
1328
1329	/* Only (set_attr "subst" "yes/no") and
1330	(set (attr "subst" (const_string "yes/no")))
1331	are currently allowed. */
1332	error_at (elem->loc, "unsupported value for `%s'", subst_name);
1333	return false;
1334
1335	case SET_ATTR_ALTERNATIVE:
1336	if (strcmp (XSTR (cur_attr, 0), s2: subst_name) == 0)
1337	error_at (elem->loc,
1338	"%s: `set_attr_alternative' is unsupported by "
1339	"`define_subst'", XSTR (elem->data, 0));
1340	return false;
1341
1342
1343	default:
1344	gcc_unreachable ();
1345	}
1346	}
1347
1348	return false;
1349
1350	found:
1351	if (strcmp (s1: value, s2: subst_true) == 0)
1352	return true;
1353	if (strcmp (s1: value, s2: subst_false) == 0)
1354	return false;
1355
1356	error_at (elem->loc, "unknown value `%s' for `%s' attribute",
1357	value, subst_name);
1358	return false;
1359	}
1360
1361	/* Compare RTL-template of original define_insn X to input RTL-template of
1362	define_subst PT. Return 1 if the templates match, 0 otherwise.
1363	During the comparison, the routine also fills global_array OPERAND_DATA. */
1364	static bool
1365	subst_pattern_match (rtx x, rtx pt, file_location loc)
1366	{
1367	RTX_CODE code, code_pt;
1368	int i, j, len;
1369	const char *fmt, *pred_name;
1370
1371	code = GET_CODE (x);
1372	code_pt = GET_CODE (pt);
1373
1374	if (code_pt == MATCH_OPERAND)
1375	{
1376	/* MATCH_DUP, and MATCH_OP_DUP don't have a specified mode, so we
1377	always accept them. */
1378	if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt)
1379	&& (code != MATCH_DUP && code != MATCH_OP_DUP))
1380	return false; /* Modes don't match. */
1381
1382	if (code == MATCH_OPERAND)
1383	{
1384	pred_name = XSTR (pt, 1);
1385	if (pred_name[0] != 0)
1386	{
1387	const struct pred_data *pred_pt = lookup_predicate (pred_name);
1388	if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
1389	return false; /* Predicates don't match. */
1390	}
1391	}
1392
1393	gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
1394	operand_data[XINT (pt, 0)] = x;
1395	return true;
1396	}
1397
1398	if (code_pt == MATCH_OPERATOR)
1399	{
1400	int x_vecexp_pos = -1;
1401
1402	/* Compare modes. */
1403	if (GET_MODE (pt) != VOIDmode && GET_MODE (x) != GET_MODE (pt))
1404	return false;
1405
1406	/* In case X is also match_operator, compare predicates. */
1407	if (code == MATCH_OPERATOR)
1408	{
1409	pred_name = XSTR (pt, 1);
1410	if (pred_name[0] != 0)
1411	{
1412	const struct pred_data *pred_pt = lookup_predicate (pred_name);
1413	if (!pred_pt || pred_pt != lookup_predicate (XSTR (x, 1)))
1414	return false;
1415	}
1416	}
1417
1418	/* Compare operands.
1419	MATCH_OPERATOR in input template could match in original template
1420	either 1) MATCH_OPERAND, 2) UNSPEC, 3) ordinary operation (like PLUS).
1421	In the first case operands are at (XVECEXP (x, 2, j)), in the second
1422	- at (XVECEXP (x, 0, j)), in the last one - (XEXP (x, j)).
1423	X_VECEXP_POS variable shows, where to look for these operands. */
1424	if (code == UNSPEC
1425	|| code == UNSPEC_VOLATILE)
1426	x_vecexp_pos = 0;
1427	else if (code == MATCH_OPERATOR)
1428	x_vecexp_pos = 2;
1429	else
1430	x_vecexp_pos = -1;
1431
1432	/* MATCH_OPERATOR or UNSPEC case. */
1433	if (x_vecexp_pos >= 0)
1434	{
1435	/* Compare operands number in X and PT. */
1436	if (XVECLEN (x, x_vecexp_pos) != XVECLEN (pt, 2))
1437	return false;
1438	for (j = 0; j < XVECLEN (pt, 2); j++)
1439	if (!subst_pattern_match (XVECEXP (x, x_vecexp_pos, j),
1440	XVECEXP (pt, 2, j), loc))
1441	return false;
1442	}
1443
1444	/* Ordinary operator. */
1445	else
1446	{
1447	/* Compare operands number in X and PT.
1448	We count operands differently for X and PT since we compare
1449	an operator (with operands directly in RTX) and MATCH_OPERATOR
1450	(that has a vector with operands). */
1451	if (GET_RTX_LENGTH (code) != XVECLEN (pt, 2))
1452	return false;
1453	for (j = 0; j < XVECLEN (pt, 2); j++)
1454	if (!subst_pattern_match (XEXP (x, j), XVECEXP (pt, 2, j), loc))
1455	return false;
1456	}
1457
1458	/* Store the operand to OPERAND_DATA array. */
1459	gcc_assert (XINT (pt, 0) >= 0 && XINT (pt, 0) < MAX_OPERANDS);
1460	operand_data[XINT (pt, 0)] = x;
1461	return true;
1462	}
1463
1464	if (code_pt == MATCH_PAR_DUP
1465	|| code_pt == MATCH_DUP
1466	|| code_pt == MATCH_OP_DUP
1467	|| code_pt == MATCH_SCRATCH
1468	|| code_pt == MATCH_PARALLEL)
1469	{
1470	/* Currently interface for these constructions isn't defined -
1471	probably they aren't needed in input template of define_subst at all.
1472	So, for now their usage in define_subst is forbidden. */
1473	error_at (loc, "%s cannot be used in define_subst",
1474	GET_RTX_NAME (code_pt));
1475	}
1476
1477	gcc_assert (code != MATCH_PAR_DUP
1478	&& code_pt != MATCH_DUP
1479	&& code_pt != MATCH_OP_DUP
1480	&& code_pt != MATCH_SCRATCH
1481	&& code_pt != MATCH_PARALLEL
1482	&& code_pt != MATCH_OPERAND
1483	&& code_pt != MATCH_OPERATOR);
1484	/* If PT is none of the handled above, then we match only expressions with
1485	the same code in X. */
1486	if (code != code_pt)
1487	return false;
1488
1489	fmt = GET_RTX_FORMAT (code_pt);
1490	len = GET_RTX_LENGTH (code_pt);
1491
1492	for (i = 0; i < len; i++)
1493	{
1494	if (fmt[i] == '0')
1495	break;
1496
1497	switch (fmt[i])
1498	{
1499	case 'r': case 'p': case 'i': case 'w': case 's':
1500	continue;
1501
1502	case 'e': case 'u':
1503	if (!subst_pattern_match (XEXP (x, i), XEXP (pt, i), loc))
1504	return false;
1505	break;
1506	case 'E':
1507	{
1508	if (XVECLEN (x, i) != XVECLEN (pt, i))
1509	return false;
1510	for (j = 0; j < XVECLEN (pt, i); j++)
1511	if (!subst_pattern_match (XVECEXP (x, i, j),
1512	XVECEXP (pt, i, j), loc))
1513	return false;
1514	break;
1515	}
1516	default:
1517	gcc_unreachable ();
1518	}
1519	}
1520
1521	return true;
1522	}
1523
1524	/* Examine the attribute "predicable"; discover its boolean values
1525	and its default. */
1526
1527	static void
1528	identify_predicable_attribute (void)
1529	{
1530	class queue_elem *elem;
1531	char *p_true, *p_false;
1532	const char *value;
1533
1534	/* Look for the DEFINE_ATTR for `predicable', which must exist. */
1535	for (elem = define_attr_queue; elem ; elem = elem->next)
1536	if (strcmp (XSTR (elem->data, 0), s2: "predicable") == 0)
1537	goto found;
1538
1539	error_at (define_cond_exec_queue->loc,
1540	"attribute `predicable' not defined");
1541	return;
1542
1543	found:
1544	value = XSTR (elem->data, 1);
1545	p_false = xstrdup (value);
1546	p_true = strchr (s: p_false, c: ',');
1547	if (p_true == NULL || strchr (s: ++p_true, c: ',') != NULL)
1548	{
1549	error_at (elem->loc, "attribute `predicable' is not a boolean");
1550	free (ptr: p_false);
1551	return;
1552	}
1553	p_true[-1] = '\0';
1554
1555	predicable_true = p_true;
1556	predicable_false = p_false;
1557
1558	switch (GET_CODE (XEXP (elem->data, 2)))
1559	{
1560	case CONST_STRING:
1561	value = XSTR (XEXP (elem->data, 2), 0);
1562	break;
1563
1564	case CONST:
1565	error_at (elem->loc, "attribute `predicable' cannot be const");
1566	free (ptr: p_false);
1567	return;
1568
1569	default:
1570	error_at (elem->loc,
1571	"attribute `predicable' must have a constant default");
1572	free (ptr: p_false);
1573	return;
1574	}
1575
1576	if (strcmp (s1: value, s2: p_true) == 0)
1577	predicable_default = 1;
1578	else if (strcmp (s1: value, s2: p_false) == 0)
1579	predicable_default = 0;
1580	else
1581	{
1582	error_at (elem->loc, "unknown value `%s' for `predicable' attribute",
1583	value);
1584	free (ptr: p_false);
1585	}
1586	}
1587
1588	/* Return the number of alternatives in constraint S. */
1589
1590	static int
1591	n_alternatives (const char *s)
1592	{
1593	int n = 1;
1594
1595	if (s)
1596	while (*s)
1597	n += (*s++ == ',');
1598
1599	return n;
1600	}
1601
1602	/* The routine scans rtl PATTERN, find match_operand in it and counts
1603	number of alternatives. If PATTERN contains several match_operands
1604	with different number of alternatives, error is emitted, and the
1605	routine returns 0. If all match_operands in PATTERN have the same
1606	number of alternatives, it's stored in N_ALT, and the routine returns 1.
1607	LOC is the location of PATTERN, for error reporting. */
1608	static int
1609	get_alternatives_number (rtx pattern, int *n_alt, file_location loc)
1610	{
1611	const char *fmt;
1612	enum rtx_code code;
1613	int i, j, len;
1614
1615	if (!n_alt)
1616	return 0;
1617
1618	code = GET_CODE (pattern);
1619	switch (code)
1620	{
1621	case MATCH_OPERAND:
1622	i = n_alternatives (XSTR (pattern, 2));
1623	/* n_alternatives returns 1 if constraint string is empty -
1624	here we fix it up. */
1625	if (!*(XSTR (pattern, 2)))
1626	i = 0;
1627	if (*n_alt <= 0)
1628	*n_alt = i;
1629
1630	else if (i && i != *n_alt)
1631	{
1632	error_at (loc, "wrong number of alternatives in operand %d",
1633	XINT (pattern, 0));
1634	return 0;
1635	}
1636
1637	default:
1638	break;
1639	}
1640
1641	fmt = GET_RTX_FORMAT (code);
1642	len = GET_RTX_LENGTH (code);
1643	for (i = 0; i < len; i++)
1644	{
1645	switch (fmt[i])
1646	{
1647	case 'e': case 'u':
1648	if (!get_alternatives_number (XEXP (pattern, i), n_alt, loc))
1649	return 0;
1650	break;
1651
1652	case 'V':
1653	if (XVEC (pattern, i) == NULL)
1654	break;
1655	/* FALLTHRU */
1656
1657	case 'E':
1658	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1659	if (!get_alternatives_number (XVECEXP (pattern, i, j), n_alt, loc))
1660	return 0;
1661	break;
1662
1663	case 'r': case 'p': case 'i': case 'w':
1664	case '0': case 's': case 'S': case 'T':
1665	break;
1666
1667	default:
1668	gcc_unreachable ();
1669	}
1670	}
1671	return 1;
1672	}
1673
1674	/* Determine how many alternatives there are in INSN, and how many
1675	operands. */
1676
1677	static void
1678	collect_insn_data (rtx pattern, int *palt, int *pmax)
1679	{
1680	const char *fmt;
1681	enum rtx_code code;
1682	int i, j, len;
1683
1684	code = GET_CODE (pattern);
1685	switch (code)
1686	{
1687	case MATCH_OPERAND:
1688	case MATCH_SCRATCH:
1689	i = n_alternatives (XSTR (pattern, code == MATCH_SCRATCH ? 1 : 2));
1690	*palt = (i > *palt ? i : *palt);
1691	/* Fall through. */
1692
1693	case MATCH_OPERATOR:
1694	case MATCH_PARALLEL:
1695	i = XINT (pattern, 0);
1696	if (i > *pmax)
1697	*pmax = i;
1698	break;
1699
1700	default:
1701	break;
1702	}
1703
1704	fmt = GET_RTX_FORMAT (code);
1705	len = GET_RTX_LENGTH (code);
1706	for (i = 0; i < len; i++)
1707	{
1708	switch (fmt[i])
1709	{
1710	case 'e': case 'u':
1711	collect_insn_data (XEXP (pattern, i), palt, pmax);
1712	break;
1713
1714	case 'V':
1715	if (XVEC (pattern, i) == NULL)
1716	break;
1717	/* Fall through. */
1718	case 'E':
1719	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1720	collect_insn_data (XVECEXP (pattern, i, j), palt, pmax);
1721	break;
1722
1723	case 'r': case 'p': case 'i': case 'w':
1724	case '0': case 's': case 'S': case 'T':
1725	break;
1726
1727	default:
1728	gcc_unreachable ();
1729	}
1730	}
1731	}
1732
1733	static rtx
1734	alter_predicate_for_insn (rtx pattern, int alt, int max_op,
1735	file_location loc)
1736	{
1737	const char *fmt;
1738	enum rtx_code code;
1739	int i, j, len;
1740
1741	code = GET_CODE (pattern);
1742	switch (code)
1743	{
1744	case MATCH_OPERAND:
1745	{
1746	const char *c = XSTR (pattern, 2);
1747
1748	if (n_alternatives (s: c) != 1)
1749	{
1750	error_at (loc, "too many alternatives for operand %d",
1751	XINT (pattern, 0));
1752	return NULL;
1753	}
1754
1755	/* Replicate C as needed to fill out ALT alternatives. */
1756	if (c && *c && alt > 1)
1757	{
1758	size_t c_len = strlen (s: c);
1759	size_t len = alt * (c_len + 1);
1760	char *new_c = XNEWVEC (char, len);
1761
1762	memcpy (dest: new_c, src: c, n: c_len);
1763	for (i = 1; i < alt; ++i)
1764	{
1765	new_c[i * (c_len + 1) - 1] = ',';
1766	memcpy (dest: &new_c[i * (c_len + 1)], src: c, n: c_len);
1767	}
1768	new_c[len - 1] = '\0';
1769	XSTR (pattern, 2) = new_c;
1770	}
1771	}
1772	/* Fall through. */
1773
1774	case MATCH_OPERATOR:
1775	case MATCH_SCRATCH:
1776	case MATCH_PARALLEL:
1777	case MATCH_DUP:
1778	XINT (pattern, 0) += max_op;
1779	break;
1780
1781	default:
1782	break;
1783	}
1784
1785	fmt = GET_RTX_FORMAT (code);
1786	len = GET_RTX_LENGTH (code);
1787	for (i = 0; i < len; i++)
1788	{
1789	rtx r;
1790
1791	switch (fmt[i])
1792	{
1793	case 'e': case 'u':
1794	r = alter_predicate_for_insn (XEXP (pattern, i), alt, max_op, loc);
1795	if (r == NULL)
1796	return r;
1797	break;
1798
1799	case 'E':
1800	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1801	{
1802	r = alter_predicate_for_insn (XVECEXP (pattern, i, j),
1803	alt, max_op, loc);
1804	if (r == NULL)
1805	return r;
1806	}
1807	break;
1808
1809	case 'r': case 'p': case 'i': case 'w': case '0': case 's':
1810	break;
1811
1812	default:
1813	gcc_unreachable ();
1814	}
1815	}
1816
1817	return pattern;
1818	}
1819
1820	/* Duplicate constraints in PATTERN. If pattern is from original
1821	rtl-template, we need to duplicate each alternative - for that we
1822	need to use duplicate_each_alternative () as a functor ALTER.
1823	If pattern is from output-pattern of define_subst, we need to
1824	duplicate constraints in another way - with duplicate_alternatives ().
1825	N_DUP is multiplication factor. */
1826	static rtx
1827	alter_constraints (rtx pattern, int n_dup, constraints_handler_t alter)
1828	{
1829	const char *fmt;
1830	enum rtx_code code;
1831	int i, j, len;
1832
1833	code = GET_CODE (pattern);
1834	switch (code)
1835	{
1836	case MATCH_OPERAND:
1837	XSTR (pattern, 2) = alter (XSTR (pattern, 2), n_dup);
1838	break;
1839	case MATCH_SCRATCH:
1840	XSTR (pattern, 1) = alter (XSTR (pattern, 1), n_dup);
1841	break;
1842
1843	default:
1844	break;
1845	}
1846
1847	fmt = GET_RTX_FORMAT (code);
1848	len = GET_RTX_LENGTH (code);
1849	for (i = 0; i < len; i++)
1850	{
1851	rtx r;
1852
1853	switch (fmt[i])
1854	{
1855	case 'e': case 'u':
1856	r = alter_constraints (XEXP (pattern, i), n_dup, alter);
1857	if (r == NULL)
1858	return r;
1859	break;
1860
1861	case 'E':
1862	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
1863	{
1864	r = alter_constraints (XVECEXP (pattern, i, j), n_dup, alter);
1865	if (r == NULL)
1866	return r;
1867	}
1868	break;
1869
1870	case 'r': case 'p': case 'i': case 'w': case '0': case 's':
1871	break;
1872
1873	default:
1874	break;
1875	}
1876	}
1877
1878	return pattern;
1879	}
1880
1881	static const char *
1882	alter_test_for_insn (class queue_elem *ce_elem,
1883	class queue_elem *insn_elem)
1884	{
1885	return rtx_reader_ptr->join_c_conditions (XSTR (ce_elem->data, 1),
1886	XSTR (insn_elem->data, 2));
1887	}
1888
1889	/* Modify VAL, which is an attribute expression for the "enabled" attribute,
1890	to take "ce_enabled" into account. Return the new expression. */
1891	static rtx
1892	modify_attr_enabled_ce (rtx val)
1893	{
1894	rtx eq_attr, str;
1895	rtx ite;
1896	eq_attr = rtx_alloc (EQ_ATTR);
1897	ite = rtx_alloc (IF_THEN_ELSE);
1898	str = rtx_alloc (CONST_STRING);
1899
1900	XSTR (eq_attr, 0) = "ce_enabled";
1901	XSTR (eq_attr, 1) = "yes";
1902	XSTR (str, 0) = "no";
1903	XEXP (ite, 0) = eq_attr;
1904	XEXP (ite, 1) = val;
1905	XEXP (ite, 2) = str;
1906
1907	return ite;
1908	}
1909
1910	/* Alter the attribute vector of INSN, which is a COND_EXEC variant created
1911	from a define_insn pattern. We must modify the "predicable" attribute
1912	to be named "ce_enabled", and also change any "enabled" attribute that's
1913	present so that it takes ce_enabled into account.
1914	We rely on the fact that INSN was created with copy_rtx, and modify data
1915	in-place. */
1916
1917	static void
1918	alter_attrs_for_insn (rtx insn)
1919	{
1920	static bool global_changes_made = false;
1921	rtvec vec = XVEC (insn, 4);
1922	rtvec new_vec;
1923	rtx val, set;
1924	int num_elem;
1925	int predicable_idx = -1;
1926	int enabled_idx = -1;
1927	int i;
1928
1929	if (! vec)
1930	return;
1931
1932	num_elem = GET_NUM_ELEM (vec);
1933	for (i = num_elem - 1; i >= 0; --i)
1934	{
1935	rtx sub = RTVEC_ELT (vec, i);
1936	switch (GET_CODE (sub))
1937	{
1938	case SET_ATTR:
1939	if (strcmp (XSTR (sub, 0), s2: "predicable") == 0)
1940	{
1941	predicable_idx = i;
1942	XSTR (sub, 0) = "ce_enabled";
1943	}
1944	else if (strcmp (XSTR (sub, 0), s2: "enabled") == 0)
1945	{
1946	enabled_idx = i;
1947	XSTR (sub, 0) = "nonce_enabled";
1948	}
1949	break;
1950
1951	case SET_ATTR_ALTERNATIVE:
1952	if (strcmp (XSTR (sub, 0), s2: "predicable") == 0)
1953	/* We already give an error elsewhere. */
1954	return;
1955	else if (strcmp (XSTR (sub, 0), s2: "enabled") == 0)
1956	{
1957	enabled_idx = i;
1958	XSTR (sub, 0) = "nonce_enabled";
1959	}
1960	break;
1961
1962	case SET:
1963	if (GET_CODE (SET_DEST (sub)) != ATTR)
1964	break;
1965	if (strcmp (XSTR (SET_DEST (sub), 0), s2: "predicable") == 0)
1966	{
1967	sub = SET_SRC (sub);
1968	if (GET_CODE (sub) == CONST_STRING)
1969	{
1970	predicable_idx = i;
1971	XSTR (sub, 0) = "ce_enabled";
1972	}
1973	else
1974	/* We already give an error elsewhere. */
1975	return;
1976	break;
1977	}
1978	if (strcmp (XSTR (SET_DEST (sub), 0), s2: "enabled") == 0)
1979	{
1980	enabled_idx = i;
1981	XSTR (SET_DEST (sub), 0) = "nonce_enabled";
1982	}
1983	break;
1984
1985	default:
1986	gcc_unreachable ();
1987	}
1988	}
1989	if (predicable_idx == -1)
1990	return;
1991
1992	if (!global_changes_made)
1993	{
1994	class queue_elem *elem;
1995
1996	global_changes_made = true;
1997	add_define_attr (name: "ce_enabled");
1998	add_define_attr (name: "nonce_enabled");
1999
2000	for (elem = define_attr_queue; elem ; elem = elem->next)
2001	if (strcmp (XSTR (elem->data, 0), s2: "enabled") == 0)
2002	{
2003	XEXP (elem->data, 2)
2004	= modify_attr_enabled_ce (XEXP (elem->data, 2));
2005	}
2006	}
2007	if (enabled_idx == -1)
2008	return;
2009
2010	new_vec = rtvec_alloc (num_elem + 1);
2011	for (i = 0; i < num_elem; i++)
2012	RTVEC_ELT (new_vec, i) = RTVEC_ELT (vec, i);
2013	val = rtx_alloc (IF_THEN_ELSE);
2014	XEXP (val, 0) = rtx_alloc (EQ_ATTR);
2015	XEXP (val, 1) = rtx_alloc (CONST_STRING);
2016	XEXP (val, 2) = rtx_alloc (CONST_STRING);
2017	XSTR (XEXP (val, 0), 0) = "nonce_enabled";
2018	XSTR (XEXP (val, 0), 1) = "yes";
2019	XSTR (XEXP (val, 1), 0) = "yes";
2020	XSTR (XEXP (val, 2), 0) = "no";
2021	set = rtx_alloc (SET);
2022	SET_DEST (set) = rtx_alloc (ATTR);
2023	XSTR (SET_DEST (set), 0) = "enabled";
2024	SET_SRC (set) = modify_attr_enabled_ce (val);
2025	RTVEC_ELT (new_vec, i) = set;
2026	XVEC (insn, 4) = new_vec;
2027	}
2028
2029	/* As number of constraints is changed after define_subst, we need to
2030	process attributes as well - we need to duplicate them the same way
2031	that we duplicated constraints in original pattern
2032	ELEM is a queue element, containing our rtl-template,
2033	N_DUP - multiplication factor. */
2034	static void
2035	alter_attrs_for_subst_insn (class queue_elem * elem, int n_dup)
2036	{
2037	rtvec vec = XVEC (elem->data, 4);
2038	int num_elem;
2039	int i;
2040
2041	if (n_dup < 2 || ! vec)
2042	return;
2043
2044	num_elem = GET_NUM_ELEM (vec);
2045	for (i = num_elem - 1; i >= 0; --i)
2046	{
2047	rtx sub = RTVEC_ELT (vec, i);
2048	switch (GET_CODE (sub))
2049	{
2050	case SET_ATTR:
2051	if (strchr (XSTR (sub, 1), c: ',') != NULL)
2052	XSTR (sub, 1) = duplicate_alternatives (XSTR (sub, 1), n_dup);
2053	break;
2054
2055	case SET_ATTR_ALTERNATIVE:
2056	case SET:
2057	error_at (elem->loc,
2058	"%s: `define_subst' does not support attributes "
2059	"assigned by `set' and `set_attr_alternative'",
2060	XSTR (elem->data, 0));
2061	return;
2062
2063	default:
2064	gcc_unreachable ();
2065	}
2066	}
2067	}
2068
2069	/* Adjust all of the operand numbers in SRC to match the shift they'll
2070	get from an operand displacement of DISP. Return a pointer after the
2071	adjusted string. */
2072
2073	static char *
2074	shift_output_template (char *dest, const char *src, int disp)
2075	{
2076	while (*src)
2077	{
2078	char c = *src++;
2079	*dest++ = c;
2080	if (c == '%')
2081	{
2082	c = *src++;
2083	if (ISDIGIT ((unsigned char) c))
2084	c += disp;
2085	else if (ISALPHA (c))
2086	{
2087	*dest++ = c;
2088	c = *src++ + disp;
2089	}
2090	*dest++ = c;
2091	}
2092	}
2093
2094	return dest;
2095	}
2096
2097	static const char *
2098	alter_output_for_insn (class queue_elem *ce_elem,
2099	class queue_elem *insn_elem,
2100	int alt, int max_op)
2101	{
2102	const char *ce_out, *insn_out;
2103	char *result, *p;
2104	size_t len, ce_len, insn_len;
2105
2106	/* ??? Could coordinate with genoutput to not duplicate code here. */
2107
2108	ce_out = XSTR (ce_elem->data, 2);
2109	insn_out = XTMPL (insn_elem->data, 3);
2110	if (!ce_out || *ce_out == '\0')
2111	return insn_out;
2112
2113	ce_len = strlen (s: ce_out);
2114	insn_len = strlen (s: insn_out);
2115
2116	if (*insn_out == '*')
2117	/* You must take care of the predicate yourself. */
2118	return insn_out;
2119
2120	if (*insn_out == '@')
2121	{
2122	len = (ce_len + 1) * alt + insn_len + 1;
2123	p = result = XNEWVEC (char, len);
2124
2125	do
2126	{
2127	do
2128	*p++ = *insn_out++;
2129	while (ISSPACE ((unsigned char) *insn_out));
2130
2131	if (*insn_out != '#')
2132	{
2133	p = shift_output_template (dest: p, src: ce_out, disp: max_op);
2134	*p++ = ' ';
2135	}
2136
2137	do
2138	*p++ = *insn_out++;
2139	while (*insn_out && *insn_out != '\n');
2140	}
2141	while (*insn_out);
2142	*p = '\0';
2143	}
2144	else
2145	{
2146	len = ce_len + 1 + insn_len + 1;
2147	result = XNEWVEC (char, len);
2148
2149	p = shift_output_template (dest: result, src: ce_out, disp: max_op);
2150	*p++ = ' ';
2151	memcpy (dest: p, src: insn_out, n: insn_len + 1);
2152	}
2153
2154	return result;
2155	}
2156
2157	/* From string STR "a,b,c" produce "a,b,c,a,b,c,a,b,c", i.e. original
2158	string, duplicated N_DUP times. */
2159
2160	static const char *
2161	duplicate_alternatives (const char * str, int n_dup)
2162	{
2163	int i, len, new_len;
2164	char *result, *sp;
2165	const char *cp;
2166
2167	if (n_dup < 2)
2168	return str;
2169
2170	while (ISSPACE (*str))
2171	str++;
2172
2173	if (*str == '\0')
2174	return str;
2175
2176	cp = str;
2177	len = strlen (s: str);
2178	new_len = (len + 1) * n_dup;
2179
2180	sp = result = XNEWVEC (char, new_len);
2181
2182	/* Global modifier characters mustn't be duplicated: skip if found. */
2183	if (*cp == '=' || *cp == '+' || *cp == '%')
2184	{
2185	*sp++ = *cp++;
2186	len--;
2187	}
2188
2189	/* Copy original constraints N_DUP times. */
2190	for (i = 0; i < n_dup; i++, sp += len+1)
2191	{
2192	memcpy (dest: sp, src: cp, n: len);
2193	*(sp+len) = (i == n_dup - 1) ? '\0' : ',';
2194	}
2195
2196	return result;
2197	}
2198
2199	/* From string STR "a,b,c" produce "a,a,a,b,b,b,c,c,c", i.e. string where
2200	each alternative from the original string is duplicated N_DUP times. */
2201	static const char *
2202	duplicate_each_alternative (const char * str, int n_dup)
2203	{
2204	int i, len, new_len;
2205	char *result, *sp, *ep, *cp;
2206
2207	if (n_dup < 2)
2208	return str;
2209
2210	while (ISSPACE (*str))
2211	str++;
2212
2213	if (*str == '\0')
2214	return str;
2215
2216	cp = xstrdup (str);
2217
2218	new_len = (strlen (s: cp) + 1) * n_dup;
2219
2220	sp = result = XNEWVEC (char, new_len);
2221
2222	/* Global modifier characters mustn't be duplicated: skip if found. */
2223	if (*cp == '=' || *cp == '+' || *cp == '%')
2224	*sp++ = *cp++;
2225
2226	do
2227	{
2228	if ((ep = strchr (s: cp, c: ',')) != NULL)
2229	*ep++ = '\0';
2230	len = strlen (s: cp);
2231
2232	/* Copy a constraint N_DUP times. */
2233	for (i = 0; i < n_dup; i++, sp += len + 1)
2234	{
2235	memcpy (dest: sp, src: cp, n: len);
2236	*(sp+len) = (ep == NULL && i == n_dup - 1) ? '\0' : ',';
2237	}
2238
2239	cp = ep;
2240	}
2241	while (cp != NULL);
2242
2243	return result;
2244	}
2245
2246	/* Alter the output of INSN whose pattern was modified by
2247	DEFINE_SUBST. We must replicate output strings according
2248	to the new number of alternatives ALT in substituted pattern.
2249	If ALT equals 1, output has one alternative or defined by C
2250	code, then output is returned without any changes. */
2251
2252	static const char *
2253	alter_output_for_subst_insn (rtx insn, int alt)
2254	{
2255	const char *insn_out, *old_out;
2256	char *new_out, *cp;
2257	size_t old_len, new_len;
2258	int j;
2259
2260	insn_out = XTMPL (insn, 3);
2261
2262	if (alt < 2 || *insn_out != '@')
2263	return insn_out;
2264
2265	old_out = insn_out + 1;
2266	while (ISSPACE (*old_out))
2267	old_out++;
2268	old_len = strlen (s: old_out);
2269
2270	new_len = alt * (old_len + 1) + 1;
2271
2272	new_out = XNEWVEC (char, new_len);
2273	new_out[0] = '@';
2274
2275	for (j = 0, cp = new_out + 1; j < alt; j++, cp += old_len + 1)
2276	{
2277	memcpy (dest: cp, src: old_out, n: old_len);
2278	cp[old_len] = (j == alt - 1) ? '\0' : '\n';
2279	}
2280
2281	return new_out;
2282	}
2283
2284	/* Replicate insns as appropriate for the given DEFINE_COND_EXEC. */
2285
2286	static void
2287	process_one_cond_exec (class queue_elem *ce_elem)
2288	{
2289	class queue_elem *insn_elem;
2290	for (insn_elem = define_insn_queue; insn_elem ; insn_elem = insn_elem->next)
2291	{
2292	int alternatives, max_operand;
2293	rtx pred, insn, pattern, split;
2294	char *new_name;
2295	int i;
2296
2297	if (! is_predicable (elem: insn_elem))
2298	continue;
2299
2300	alternatives = 1;
2301	max_operand = -1;
2302	collect_insn_data (pattern: insn_elem->data, palt: &alternatives, pmax: &max_operand);
2303	max_operand += 1;
2304
2305	if (XVECLEN (ce_elem->data, 0) != 1)
2306	{
2307	error_at (ce_elem->loc, "too many patterns in predicate");
2308	return;
2309	}
2310
2311	pred = copy_rtx (XVECEXP (ce_elem->data, 0, 0));
2312	pred = alter_predicate_for_insn (pattern: pred, alt: alternatives, max_op: max_operand,
2313	loc: ce_elem->loc);
2314	if (pred == NULL)
2315	return;
2316
2317	/* Construct a new pattern for the new insn. */
2318	insn = copy_rtx (insn_elem->data);
2319	new_name = XNEWVAR (char, strlen XSTR (insn_elem->data, 0) + 4);
2320	sprintf (s: new_name, format: "*p %s", XSTR (insn_elem->data, 0));
2321	XSTR (insn, 0) = new_name;
2322	pattern = rtx_alloc (COND_EXEC);
2323	XEXP (pattern, 0) = pred;
2324	XEXP (pattern, 1) = add_implicit_parallel (XVEC (insn, 1));
2325	XVEC (insn, 1) = rtvec_alloc (1);
2326	XVECEXP (insn, 1, 0) = pattern;
2327
2328	if (XVEC (ce_elem->data, 3) != NULL)
2329	{
2330	rtvec attributes = rtvec_alloc (XVECLEN (insn, 4)
2331	+ XVECLEN (ce_elem->data, 3));
2332	int i = 0;
2333	int j = 0;
2334	for (i = 0; i < XVECLEN (insn, 4); i++)
2335	RTVEC_ELT (attributes, i) = XVECEXP (insn, 4, i);
2336
2337	for (j = 0; j < XVECLEN (ce_elem->data, 3); j++, i++)
2338	RTVEC_ELT (attributes, i) = XVECEXP (ce_elem->data, 3, j);
2339
2340	XVEC (insn, 4) = attributes;
2341	}
2342
2343	XSTR (insn, 2) = alter_test_for_insn (ce_elem, insn_elem);
2344	XTMPL (insn, 3) = alter_output_for_insn (ce_elem, insn_elem,
2345	alt: alternatives, max_op: max_operand);
2346	alter_attrs_for_insn (insn);
2347
2348	/* Put the new pattern on the `other' list so that it
2349	(a) is not reprocessed by other define_cond_exec patterns
2350	(b) appears after all normal define_insn patterns.
2351
2352	??? B is debatable. If one has normal insns that match
2353	cond_exec patterns, they will be preferred over these
2354	generated patterns. Whether this matters in practice, or if
2355	it's a good thing, or whether we should thread these new
2356	patterns into the define_insn chain just after their generator
2357	is something we'll have to experiment with. */
2358
2359	queue_pattern (pattern: insn, list_tail: &other_tail, loc: insn_elem->loc);
2360
2361	if (!insn_elem->split)
2362	continue;
2363
2364	/* If the original insn came from a define_insn_and_split,
2365	generate a new split to handle the predicated insn. */
2366	split = copy_rtx (insn_elem->split->data);
2367	/* Predicate the pattern matched by the split. */
2368	pattern = rtx_alloc (COND_EXEC);
2369	XEXP (pattern, 0) = pred;
2370	XEXP (pattern, 1) = add_implicit_parallel (XVEC (split, 0));
2371	XVEC (split, 0) = rtvec_alloc (1);
2372	XVECEXP (split, 0, 0) = pattern;
2373
2374	/* Predicate all of the insns generated by the split. */
2375	for (i = 0; i < XVECLEN (split, 2); i++)
2376	{
2377	pattern = rtx_alloc (COND_EXEC);
2378	XEXP (pattern, 0) = pred;
2379	XEXP (pattern, 1) = XVECEXP (split, 2, i);
2380	XVECEXP (split, 2, i) = pattern;
2381	}
2382	/* Add the new split to the queue. */
2383	queue_pattern (pattern: split, list_tail: &other_tail, loc: insn_elem->split->loc);
2384	}
2385	}
2386
2387	/* Try to apply define_substs to the given ELEM.
2388	Only define_substs, specified via attributes would be applied.
2389	If attribute, requiring define_subst, is set, but no define_subst
2390	was applied, ELEM would be deleted. */
2391
2392	static void
2393	process_substs_on_one_elem (class queue_elem *elem,
2394	class queue_elem *queue)
2395	{
2396	class queue_elem *subst_elem;
2397	int i, j, patterns_match;
2398
2399	for (subst_elem = define_subst_queue;
2400	subst_elem; subst_elem = subst_elem->next)
2401	{
2402	int alternatives, alternatives_subst;
2403	rtx subst_pattern;
2404	rtvec subst_pattern_vec;
2405
2406	if (!has_subst_attribute (elem, subst_elem))
2407	continue;
2408
2409	/* Compare original rtl-pattern from define_insn with input
2410	pattern from define_subst.
2411	Also, check if numbers of alternatives are the same in all
2412	match_operands. */
2413	if (XVECLEN (elem->data, 1) != XVECLEN (subst_elem->data, 1))
2414	continue;
2415	patterns_match = 1;
2416	alternatives = -1;
2417	alternatives_subst = -1;
2418	for (j = 0; j < XVECLEN (elem->data, 1); j++)
2419	{
2420	if (!subst_pattern_match (XVECEXP (elem->data, 1, j),
2421	XVECEXP (subst_elem->data, 1, j),
2422	loc: subst_elem->loc))
2423	{
2424	patterns_match = 0;
2425	break;
2426	}
2427
2428	if (!get_alternatives_number (XVECEXP (elem->data, 1, j),
2429	n_alt: &alternatives, loc: subst_elem->loc))
2430	{
2431	patterns_match = 0;
2432	break;
2433	}
2434	}
2435
2436	/* Check if numbers of alternatives are the same in all
2437	match_operands in output template of define_subst. */
2438	for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
2439	{
2440	if (!get_alternatives_number (XVECEXP (subst_elem->data, 3, j),
2441	n_alt: &alternatives_subst,
2442	loc: subst_elem->loc))
2443	{
2444	patterns_match = 0;
2445	break;
2446	}
2447	}
2448
2449	if (!patterns_match)
2450	continue;
2451
2452	/* Clear array in which we save occupied indexes of operands. */
2453	memset (s: used_operands_numbers, c: 0, n: sizeof (used_operands_numbers));
2454
2455	/* Create a pattern, based on the output one from define_subst. */
2456	subst_pattern_vec = rtvec_alloc (XVECLEN (subst_elem->data, 3));
2457	for (j = 0; j < XVECLEN (subst_elem->data, 3); j++)
2458	{
2459	subst_pattern = copy_rtx (XVECEXP (subst_elem->data, 3, j));
2460
2461	/* Duplicate constraints in substitute-pattern. */
2462	subst_pattern = alter_constraints (pattern: subst_pattern, n_dup: alternatives,
2463	alter: duplicate_each_alternative);
2464
2465	subst_pattern = adjust_operands_numbers (subst_pattern);
2466
2467	/* Substitute match_dup and match_op_dup in the new pattern and
2468	duplicate constraints. */
2469	subst_pattern = subst_dup (subst_pattern, alternatives,
2470	alternatives_subst);
2471
2472	replace_duplicating_operands_in_pattern (subst_pattern);
2473
2474	/* We don't need any constraints in DEFINE_EXPAND. */
2475	if (GET_CODE (elem->data) == DEFINE_EXPAND)
2476	remove_constraints (part: subst_pattern);
2477
2478	RTVEC_ELT (subst_pattern_vec, j) = subst_pattern;
2479	}
2480	XVEC (elem->data, 1) = subst_pattern_vec;
2481
2482	for (i = 0; i < MAX_OPERANDS; i++)
2483	match_operand_entries_in_pattern[i] = NULL;
2484
2485	if (GET_CODE (elem->data) == DEFINE_INSN)
2486	{
2487	XTMPL (elem->data, 3) =
2488	alter_output_for_subst_insn (insn: elem->data, alt: alternatives_subst);
2489	alter_attrs_for_subst_insn (elem, n_dup: alternatives_subst);
2490	}
2491
2492	/* Recalculate condition, joining conditions from original and
2493	DEFINE_SUBST input patterns. */
2494	XSTR (elem->data, 2)
2495	= rtx_reader_ptr->join_c_conditions (XSTR (subst_elem->data, 2),
2496	XSTR (elem->data, 2));
2497	/* Mark that subst was applied by changing attribute from "yes"
2498	to "no". */
2499	change_subst_attribute (elem, subst_elem, new_value: subst_false);
2500	}
2501
2502	/* If ELEM contains a subst attribute with value "yes", then we
2503	expected that a subst would be applied, but it wasn't - so,
2504	we need to remove that elementto avoid duplicating. */
2505	for (subst_elem = define_subst_queue;
2506	subst_elem; subst_elem = subst_elem->next)
2507	{
2508	if (has_subst_attribute (elem, subst_elem))
2509	{
2510	remove_from_queue (elem, queue: &queue);
2511	return;
2512	}
2513	}
2514	}
2515
2516	/* This is a subroutine of mark_operands_used_in_match_dup.
2517	This routine is marks all MATCH_OPERANDs inside PATTERN as occupied. */
2518	static void
2519	mark_operands_from_match_dup (rtx pattern)
2520	{
2521	const char *fmt;
2522	int i, j, len, opno;
2523
2524	if (GET_CODE (pattern) == MATCH_OPERAND
2525	|| GET_CODE (pattern) == MATCH_OPERATOR
2526	|| GET_CODE (pattern) == MATCH_PARALLEL)
2527	{
2528	opno = XINT (pattern, 0);
2529	gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2530	used_operands_numbers [opno] = 1;
2531	}
2532	fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2533	len = GET_RTX_LENGTH (GET_CODE (pattern));
2534	for (i = 0; i < len; i++)
2535	{
2536	switch (fmt[i])
2537	{
2538	case 'e': case 'u':
2539	mark_operands_from_match_dup (XEXP (pattern, i));
2540	break;
2541	case 'E':
2542	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2543	mark_operands_from_match_dup (XVECEXP (pattern, i, j));
2544	break;
2545	}
2546	}
2547	}
2548
2549	/* This is a subroutine of adjust_operands_numbers.
2550	It goes through all expressions in PATTERN and when MATCH_DUP is
2551	met, all MATCH_OPERANDs inside it is marked as occupied. The
2552	process of marking is done by routin mark_operands_from_match_dup. */
2553	static void
2554	mark_operands_used_in_match_dup (rtx pattern)
2555	{
2556	const char *fmt;
2557	int i, j, len, opno;
2558
2559	if (GET_CODE (pattern) == MATCH_DUP)
2560	{
2561	opno = XINT (pattern, 0);
2562	gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2563	mark_operands_from_match_dup (pattern: operand_data[opno]);
2564	return;
2565	}
2566	fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2567	len = GET_RTX_LENGTH (GET_CODE (pattern));
2568	for (i = 0; i < len; i++)
2569	{
2570	switch (fmt[i])
2571	{
2572	case 'e': case 'u':
2573	mark_operands_used_in_match_dup (XEXP (pattern, i));
2574	break;
2575	case 'E':
2576	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2577	mark_operands_used_in_match_dup (XVECEXP (pattern, i, j));
2578	break;
2579	}
2580	}
2581	}
2582
2583	/* This is subroutine of renumerate_operands_in_pattern.
2584	It finds first not-occupied operand-index. */
2585	static int
2586	find_first_unused_number_of_operand ()
2587	{
2588	int i;
2589	for (i = 0; i < MAX_OPERANDS; i++)
2590	if (!used_operands_numbers[i])
2591	return i;
2592	return MAX_OPERANDS;
2593	}
2594
2595	/* This is subroutine of adjust_operands_numbers.
2596	It visits all expressions in PATTERN and assigns not-occupied
2597	operand indexes to MATCH_OPERANDs and MATCH_OPERATORs of this
2598	PATTERN. */
2599	static void
2600	renumerate_operands_in_pattern (rtx pattern)
2601	{
2602	const char *fmt;
2603	enum rtx_code code;
2604	int i, j, len, new_opno;
2605	code = GET_CODE (pattern);
2606
2607	if (code == MATCH_OPERAND
2608	|| code == MATCH_OPERATOR)
2609	{
2610	new_opno = find_first_unused_number_of_operand ();
2611	gcc_assert (new_opno >= 0 && new_opno < MAX_OPERANDS);
2612	XINT (pattern, 0) = new_opno;
2613	used_operands_numbers [new_opno] = 1;
2614	}
2615
2616	fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2617	len = GET_RTX_LENGTH (GET_CODE (pattern));
2618	for (i = 0; i < len; i++)
2619	{
2620	switch (fmt[i])
2621	{
2622	case 'e': case 'u':
2623	renumerate_operands_in_pattern (XEXP (pattern, i));
2624	break;
2625	case 'E':
2626	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2627	renumerate_operands_in_pattern (XVECEXP (pattern, i, j));
2628	break;
2629	}
2630	}
2631	}
2632
2633	/* If output pattern of define_subst contains MATCH_DUP, then this
2634	expression would be replaced with the pattern, matched with
2635	MATCH_OPERAND from input pattern. This pattern could contain any
2636	number of MATCH_OPERANDs, MATCH_OPERATORs etc., so it's possible
2637	that a MATCH_OPERAND from output_pattern (if any) would have the
2638	same number, as MATCH_OPERAND from copied pattern. To avoid such
2639	indexes overlapping, we assign new indexes to MATCH_OPERANDs,
2640	laying in the output pattern outside of MATCH_DUPs. */
2641	static rtx
2642	adjust_operands_numbers (rtx pattern)
2643	{
2644	mark_operands_used_in_match_dup (pattern);
2645
2646	renumerate_operands_in_pattern (pattern);
2647
2648	return pattern;
2649	}
2650
2651	/* Generate RTL expression
2652	(match_dup OPNO)
2653	*/
2654	static rtx
2655	generate_match_dup (int opno)
2656	{
2657	rtx return_rtx = rtx_alloc (MATCH_DUP);
2658	PUT_CODE (return_rtx, MATCH_DUP);
2659	XINT (return_rtx, 0) = opno;
2660	return return_rtx;
2661	}
2662
2663	/* This routine checks all match_operands in PATTERN and if some of
2664	have the same index, it replaces all of them except the first one to
2665	match_dup.
2666	Usually, match_operands with the same indexes are forbidden, but
2667	after define_subst copy an RTL-expression from original template,
2668	indexes of existed and just-copied match_operands could coincide.
2669	To fix it, we replace one of them with match_dup. */
2670	static rtx
2671	replace_duplicating_operands_in_pattern (rtx pattern)
2672	{
2673	const char *fmt;
2674	int i, j, len, opno;
2675	rtx mdup;
2676
2677	if (GET_CODE (pattern) == MATCH_OPERAND)
2678	{
2679	opno = XINT (pattern, 0);
2680	gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2681	if (match_operand_entries_in_pattern[opno] == NULL)
2682	{
2683	match_operand_entries_in_pattern[opno] = pattern;
2684	return NULL;
2685	}
2686	else
2687	{
2688	/* Compare predicates before replacing with match_dup. */
2689	if (strcmp (XSTR (pattern, 1),
2690	XSTR (match_operand_entries_in_pattern[opno], 1)))
2691	{
2692	error ("duplicated match_operands with different predicates were"
2693	" found.");
2694	return NULL;
2695	}
2696	return generate_match_dup (opno);
2697	}
2698	}
2699	fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2700	len = GET_RTX_LENGTH (GET_CODE (pattern));
2701	for (i = 0; i < len; i++)
2702	{
2703	switch (fmt[i])
2704	{
2705	case 'e': case 'u':
2706	mdup = replace_duplicating_operands_in_pattern (XEXP (pattern, i));
2707	if (mdup)
2708	XEXP (pattern, i) = mdup;
2709	break;
2710	case 'E':
2711	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2712	{
2713	mdup =
2714	replace_duplicating_operands_in_pattern (XVECEXP
2715	(pattern, i, j));
2716	if (mdup)
2717	XVECEXP (pattern, i, j) = mdup;
2718	}
2719	break;
2720	}
2721	}
2722	return NULL;
2723	}
2724
2725	/* The routine modifies given input PATTERN of define_subst, replacing
2726	MATCH_DUP and MATCH_OP_DUP with operands from define_insn original
2727	pattern, whose operands are stored in OPERAND_DATA array.
2728	It also duplicates constraints in operands - constraints from
2729	define_insn operands are duplicated N_SUBST_ALT times, constraints
2730	from define_subst operands are duplicated N_ALT times.
2731	After the duplication, returned output rtl-pattern contains every
2732	combination of input constraints Vs constraints from define_subst
2733	output. */
2734	static rtx
2735	subst_dup (rtx pattern, int n_alt, int n_subst_alt)
2736	{
2737	const char *fmt;
2738	enum rtx_code code;
2739	int i, j, len, opno;
2740
2741	code = GET_CODE (pattern);
2742	switch (code)
2743	{
2744	case MATCH_DUP:
2745	case MATCH_OP_DUP:
2746	opno = XINT (pattern, 0);
2747
2748	gcc_assert (opno >= 0 && opno < MAX_OPERANDS);
2749
2750	if (operand_data[opno])
2751	{
2752	pattern = copy_rtx (operand_data[opno]);
2753
2754	/* Duplicate constraints. */
2755	pattern = alter_constraints (pattern, n_dup: n_subst_alt,
2756	alter: duplicate_alternatives);
2757	}
2758	break;
2759
2760	default:
2761	break;
2762	}
2763
2764	fmt = GET_RTX_FORMAT (GET_CODE (pattern));
2765	len = GET_RTX_LENGTH (GET_CODE (pattern));
2766	for (i = 0; i < len; i++)
2767	{
2768	switch (fmt[i])
2769	{
2770	case 'e': case 'u':
2771	if (code != MATCH_DUP && code != MATCH_OP_DUP)
2772	XEXP (pattern, i) = subst_dup (XEXP (pattern, i),
2773	n_alt, n_subst_alt);
2774	break;
2775	case 'V':
2776	if (XVEC (pattern, i) == NULL)
2777	break;
2778	/* FALLTHRU */
2779	case 'E':
2780	if (code != MATCH_DUP && code != MATCH_OP_DUP)
2781	for (j = XVECLEN (pattern, i) - 1; j >= 0; --j)
2782	XVECEXP (pattern, i, j) = subst_dup (XVECEXP (pattern, i, j),
2783	n_alt, n_subst_alt);
2784	break;
2785
2786	case 'r': case 'p': case 'i': case 'w':
2787	case '0': case 's': case 'S': case 'T':
2788	break;
2789
2790	default:
2791	gcc_unreachable ();
2792	}
2793	}
2794	return pattern;
2795	}
2796
2797	/* If we have any DEFINE_COND_EXEC patterns, expand the DEFINE_INSN
2798	patterns appropriately. */
2799
2800	static void
2801	process_define_cond_exec (void)
2802	{
2803	class queue_elem *elem;
2804
2805	identify_predicable_attribute ();
2806	if (have_error)
2807	return;
2808
2809	for (elem = define_cond_exec_queue; elem ; elem = elem->next)
2810	process_one_cond_exec (ce_elem: elem);
2811	}
2812
2813	/* If we have any DEFINE_SUBST patterns, expand DEFINE_INSN and
2814	DEFINE_EXPAND patterns appropriately. */
2815
2816	static void
2817	process_define_subst (void)
2818	{
2819	class queue_elem *elem, *elem_attr;
2820
2821	/* Check if each define_subst has corresponding define_subst_attr. */
2822	for (elem = define_subst_queue; elem ; elem = elem->next)
2823	{
2824	for (elem_attr = define_subst_attr_queue;
2825	elem_attr;
2826	elem_attr = elem_attr->next)
2827	if (strcmp (XSTR (elem->data, 0), XSTR (elem_attr->data, 1)) == 0)
2828	goto found;
2829
2830	error_at (elem->loc,
2831	"%s: `define_subst' must have at least one "
2832	"corresponding `define_subst_attr'",
2833	XSTR (elem->data, 0));
2834	return;
2835
2836	found:
2837	continue;
2838	}
2839
2840	for (elem = define_insn_queue; elem ; elem = elem->next)
2841	process_substs_on_one_elem (elem, queue: define_insn_queue);
2842	for (elem = other_queue; elem ; elem = elem->next)
2843	{
2844	if (GET_CODE (elem->data) != DEFINE_EXPAND)
2845	continue;
2846	process_substs_on_one_elem (elem, queue: other_queue);
2847	}
2848	}
2849
2850	/* A subclass of rtx_reader which reads .md files and calls process_rtx on
2851	the top-level elements. */
2852
2853	class gen_reader : public rtx_reader
2854	{
2855	public:
2856	gen_reader () : rtx_reader (false) {}
2857	void handle_unknown_directive (file_location, const char *) final override;
2858	};
2859
2860	void
2861	gen_reader::handle_unknown_directive (file_location loc, const char *rtx_name)
2862	{
2863	auto_vec<rtx, 32> subrtxs;
2864	if (!read_rtx (rtx_name, rtxen: &subrtxs))
2865	return;
2866
2867	rtx x;
2868	unsigned int i;
2869	FOR_EACH_VEC_ELT (subrtxs, i, x)
2870	process_rtx (desc: x, loc);
2871	}
2872
2873	/* Add mnemonic STR with length LEN to the mnemonic hash table
2874	MNEMONIC_HTAB. A trailing zero end character is appended to STR
2875	and a permanent heap copy of STR is created. */
2876
2877	static void
2878	add_mnemonic_string (htab_t mnemonic_htab, const char *str, size_t len)
2879	{
2880	char *new_str;
2881	void **slot;
2882	char *str_zero = (char*)alloca (len + 1);
2883
2884	memcpy (dest: str_zero, src: str, n: len);
2885	str_zero[len] = '\0';
2886
2887	slot = htab_find_slot (mnemonic_htab, str_zero, INSERT);
2888
2889	if (*slot)
2890	return;
2891
2892	/* Not found; create a permanent copy and add it to the hash table. */
2893	new_str = XNEWVAR (char, len + 1);
2894	memcpy (dest: new_str, src: str_zero, n: len + 1);
2895	*slot = new_str;
2896	}
2897
2898	/* Scan INSN for mnemonic strings and add them to the mnemonic hash
2899	table in MNEMONIC_HTAB.
2900
2901	The mnemonics cannot be found if they are emitted using C code.
2902
2903	If a mnemonic string contains ';' or a newline the string assumed
2904	to consist of more than a single instruction. The attribute value
2905	will then be set to the user defined default value. */
2906
2907	static void
2908	gen_mnemonic_setattr (htab_t mnemonic_htab, rtx insn)
2909	{
2910	const char *template_code, *cp;
2911	int i;
2912	int vec_len;
2913	rtx set_attr;
2914	char *attr_name;
2915	rtvec new_vec;
2916	struct obstack *string_obstack = rtx_reader_ptr->get_string_obstack ();
2917
2918	template_code = XTMPL (insn, 3);
2919
2920	/* Skip patterns which use C code to emit the template. */
2921	if (template_code[0] == '*')
2922	return;
2923
2924	if (template_code[0] == '@')
2925	cp = &template_code[1];
2926	else
2927	cp = &template_code[0];
2928
2929	for (i = 0; *cp; )
2930	{
2931	const char *ep, *sp;
2932	size_t size = 0;
2933
2934	while (ISSPACE (*cp))
2935	cp++;
2936
2937	for (ep = sp = cp; !IS_VSPACE (*ep) && *ep != '\0'; ++ep)
2938	if (!ISSPACE (*ep))
2939	sp = ep + 1;
2940
2941	if (i > 0)
2942	obstack_1grow (string_obstack, ',');
2943
2944	while (cp < sp && ((*cp >= '0' && *cp <= '9')
2945	|| (*cp >= 'a' && *cp <= 'z')))
2946
2947	{
2948	obstack_1grow (string_obstack, *cp);
2949	cp++;
2950	size++;
2951	}
2952
2953	while (cp < sp)
2954	{
2955	if (*cp == ';' || (*cp == '\\' && cp[1] == 'n'))
2956	{
2957	/* Don't set a value if there are more than one
2958	instruction in the string. */
2959	obstack_blank_fast (string_obstack, -size);
2960	size = 0;
2961
2962	cp = sp;
2963	break;
2964	}
2965	cp++;
2966	}
2967	if (size == 0)
2968	obstack_1grow (string_obstack, '*');
2969	else
2970	add_mnemonic_string (mnemonic_htab,
2971	str: (char *) obstack_next_free (string_obstack) - size,
2972	len: size);
2973	i++;
2974	}
2975
2976	/* An insn definition might emit an empty string. */
2977	if (obstack_object_size (string_obstack) == 0)
2978	return;
2979
2980	obstack_1grow (string_obstack, '\0');
2981
2982	set_attr = rtx_alloc (SET_ATTR);
2983	XSTR (set_attr, 1) = XOBFINISH (string_obstack, char *);
2984	attr_name = XNEWVAR (char, strlen (MNEMONIC_ATTR_NAME) + 1);
2985	strcpy (dest: attr_name, MNEMONIC_ATTR_NAME);
2986	XSTR (set_attr, 0) = attr_name;
2987
2988	if (!XVEC (insn, 4))
2989	vec_len = 0;
2990	else
2991	vec_len = XVECLEN (insn, 4);
2992
2993	new_vec = rtvec_alloc (vec_len + 1);
2994	for (i = 0; i < vec_len; i++)
2995	RTVEC_ELT (new_vec, i) = XVECEXP (insn, 4, i);
2996	RTVEC_ELT (new_vec, vec_len) = set_attr;
2997	XVEC (insn, 4) = new_vec;
2998	}
2999
3000	/* This function is called for the elements in the mnemonic hashtable
3001	and generates a comma separated list of the mnemonics. */
3002
3003	static int
3004	mnemonic_htab_callback (void **slot, void *info ATTRIBUTE_UNUSED)
3005	{
3006	struct obstack *string_obstack = rtx_reader_ptr->get_string_obstack ();
3007
3008	obstack_grow (string_obstack, (char*) *slot, strlen ((char*) *slot));
3009	obstack_1grow (string_obstack, ',');
3010	return 1;
3011	}
3012
3013	/* Generate (set_attr "mnemonic" "..") RTXs and append them to every
3014	insn definition in case the back end requests it by defining the
3015	mnemonic attribute. The values for the attribute will be extracted
3016	from the output patterns of the insn definitions as far as
3017	possible. */
3018
3019	static void
3020	gen_mnemonic_attr (void)
3021	{
3022	class queue_elem *elem;
3023	rtx mnemonic_attr = NULL;
3024	htab_t mnemonic_htab;
3025	const char *str, *p;
3026	int i;
3027	struct obstack *string_obstack = rtx_reader_ptr->get_string_obstack ();
3028
3029	if (have_error)
3030	return;
3031
3032	/* Look for the DEFINE_ATTR for `mnemonic'. */
3033	for (elem = define_attr_queue; elem != *define_attr_tail; elem = elem->next)
3034	if (GET_CODE (elem->data) == DEFINE_ATTR
3035	&& strcmp (XSTR (elem->data, 0), MNEMONIC_ATTR_NAME) == 0)
3036	{
3037	mnemonic_attr = elem->data;
3038	break;
3039	}
3040
3041	/* A (define_attr "mnemonic" "...") indicates that the back-end
3042	wants a mnemonic attribute to be generated. */
3043	if (!mnemonic_attr)
3044	return;
3045
3046	mnemonic_htab = htab_create_alloc (MNEMONIC_HTAB_SIZE, htab_hash_string,
3047	htab_eq_string, 0, xcalloc, free);
3048
3049	for (elem = define_insn_queue; elem; elem = elem->next)
3050	{
3051	rtx insn = elem->data;
3052	bool found = false;
3053
3054	/* Check if the insn definition already has
3055	(set_attr "mnemonic" ...) or (set (attr "mnemonic") ...). */
3056	if (XVEC (insn, 4))
3057	for (i = 0; i < XVECLEN (insn, 4); i++)
3058	{
3059	rtx set_attr = XVECEXP (insn, 4, i);
3060
3061	switch (GET_CODE (set_attr))
3062	{
3063	case SET_ATTR:
3064	case SET_ATTR_ALTERNATIVE:
3065	if (strcmp (XSTR (set_attr, 0), MNEMONIC_ATTR_NAME) == 0)
3066	found = true;
3067	break;
3068	case SET:
3069	if (GET_CODE (SET_DEST (set_attr)) == ATTR
3070	&& strcmp (XSTR (SET_DEST (set_attr), 0),
3071	MNEMONIC_ATTR_NAME) == 0)
3072	found = true;
3073	break;
3074	default:
3075	break;
3076	}
3077	}
3078
3079	if (!found)
3080	gen_mnemonic_setattr (mnemonic_htab, insn);
3081	}
3082
3083	/* Add the user defined values to the hash table. */
3084	str = XSTR (mnemonic_attr, 1);
3085	while ((p = scan_comma_elt (&str)) != NULL)
3086	add_mnemonic_string (mnemonic_htab, str: p, len: str - p);
3087
3088	htab_traverse (mnemonic_htab, mnemonic_htab_callback, NULL);
3089
3090	/* Replace the last ',' with the zero end character. */
3091	*((char *) obstack_next_free (string_obstack) - 1) = '\0';
3092	XSTR (mnemonic_attr, 1) = XOBFINISH (string_obstack, char *);
3093	}
3094
3095	/* Check if there are DEFINE_ATTRs with the same name. */
3096	static void
3097	check_define_attr_duplicates ()
3098	{
3099	class queue_elem *elem;
3100	htab_t attr_htab;
3101	char * attr_name;
3102	void **slot;
3103
3104	attr_htab = htab_create (500, htab_hash_string, htab_eq_string, NULL);
3105
3106	for (elem = define_attr_queue; elem; elem = elem->next)
3107	{
3108	attr_name = xstrdup (XSTR (elem->data, 0));
3109
3110	slot = htab_find_slot (attr_htab, attr_name, INSERT);
3111
3112	/* Duplicate. */
3113	if (*slot)
3114	{
3115	error_at (elem->loc, "redefinition of attribute '%s'", attr_name);
3116	htab_delete (attr_htab);
3117	return;
3118	}
3119
3120	*slot = attr_name;
3121	}
3122
3123	htab_delete (attr_htab);
3124	}
3125
3126	/* The entry point for initializing the reader. */
3127
3128	rtx_reader *
3129	init_rtx_reader_args_cb (int argc, const char **argv,
3130	bool (*parse_opt) (const char *))
3131	{
3132	/* Prepare to read input. */
3133	condition_table = htab_create (500, hash_c_test, cmp_c_test, NULL);
3134	init_predicate_table ();
3135	obstack_init (rtl_obstack);
3136
3137	/* Start at 1, to make 0 available for CODE_FOR_nothing. */
3138	insn_sequence_num = 1;
3139
3140	/* These sequences are not used as indices, so can start at 1 also. */
3141	split_sequence_num = 1;
3142	peephole2_sequence_num = 1;
3143
3144	gen_reader *reader = new gen_reader ();
3145	reader->read_md_files (argc, argv, parse_opt);
3146
3147	if (define_attr_queue != NULL)
3148	check_define_attr_duplicates ();
3149
3150	/* Process define_cond_exec patterns. */
3151	if (define_cond_exec_queue != NULL)
3152	process_define_cond_exec ();
3153
3154	/* Process define_subst patterns. */
3155	if (define_subst_queue != NULL)
3156	process_define_subst ();
3157
3158	if (define_attr_queue != NULL)
3159	gen_mnemonic_attr ();
3160
3161	if (have_error)
3162	{
3163	delete reader;
3164	return NULL;
3165	}
3166
3167	return reader;
3168	}
3169
3170	/* Programs that don't have their own options can use this entry point
3171	instead. */
3172	rtx_reader *
3173	init_rtx_reader_args (int argc, const char **argv)
3174	{
3175	return init_rtx_reader_args_cb (argc, argv, parse_opt: 0);
3176	}
3177
3178	/* Count the number of patterns in all queues and return the count. */
3179	int
3180	count_patterns ()
3181	{
3182	int count = 0, truth = 1;
3183	rtx def;
3184	class queue_elem *cur = define_attr_queue;
3185	while (cur)
3186	{
3187	def = cur->data;
3188
3189	truth = maybe_eval_c_test (get_c_test (def));
3190	if (truth || !insn_elision)
3191	count++;
3192	cur = cur->next;
3193	}
3194
3195	cur = define_pred_queue;
3196	while (cur)
3197	{
3198	def = cur->data;
3199
3200	truth = maybe_eval_c_test (get_c_test (def));
3201	if (truth || !insn_elision)
3202	count++;
3203	cur = cur->next;
3204	}
3205
3206	cur = define_insn_queue;
3207	truth = 1;
3208	while (cur)
3209	{
3210	def = cur->data;
3211
3212	truth = maybe_eval_c_test (get_c_test (def));
3213	if (truth || !insn_elision)
3214	count++;
3215	cur = cur->next;
3216	}
3217
3218	cur = other_queue;
3219	truth = 1;
3220	while (cur)
3221	{
3222	def = cur->data;
3223
3224	truth = maybe_eval_c_test (get_c_test (def));
3225	if (truth || !insn_elision)
3226	count++;
3227	cur = cur->next;
3228	}
3229
3230	return count;
3231	}
3232
3233	/* Try to read a single rtx from the file. Return true on success,
3234	describing it in *INFO. */
3235
3236	bool
3237	read_md_rtx (md_rtx_info *info)
3238	{
3239	int truth, *counter;
3240	rtx def;
3241
3242	/* Discard insn patterns which we know can never match (because
3243	their C test is provably always false). If insn_elision is
3244	false, our caller needs to see all the patterns. Note that the
3245	elided patterns are never counted by the sequence numbering; it
3246	is the caller's responsibility, when insn_elision is false, not
3247	to use elided pattern numbers for anything. */
3248	do
3249	{
3250	class queue_elem **queue, *elem;
3251
3252	/* Read all patterns from a given queue before moving on to the next. */
3253	if (define_attr_queue != NULL)
3254	queue = &define_attr_queue;
3255	else if (define_pred_queue != NULL)
3256	queue = &define_pred_queue;
3257	else if (define_insn_queue != NULL)
3258	queue = &define_insn_queue;
3259	else if (other_queue != NULL)
3260	queue = &other_queue;
3261	else
3262	return false;
3263
3264	elem = *queue;
3265	*queue = elem->next;
3266	def = elem->data;
3267	info->def = def;
3268	info->loc = elem->loc;
3269	free (ptr: elem);
3270
3271	truth = maybe_eval_c_test (get_c_test (def));
3272	}
3273	while (truth == 0 && insn_elision);
3274
3275	/* Perform code-specific processing and pick the appropriate sequence
3276	number counter. */
3277	switch (GET_CODE (def))
3278	{
3279	case DEFINE_INSN:
3280	case DEFINE_EXPAND:
3281	/* insn_sequence_num is used here so the name table will match caller's
3282	idea of insn numbering, whether or not elision is active. */
3283	record_insn_name (insn_sequence_num, XSTR (def, 0));
3284
3285	/* Fall through. */
3286	case DEFINE_PEEPHOLE:
3287	counter = &insn_sequence_num;
3288	break;
3289
3290	case DEFINE_SPLIT:
3291	counter = &split_sequence_num;
3292	break;
3293
3294	case DEFINE_PEEPHOLE2:
3295	counter = &peephole2_sequence_num;
3296	break;
3297
3298	default:
3299	counter = NULL;
3300	break;
3301	}
3302
3303	if (counter)
3304	{
3305	info->index = *counter;
3306	if (truth != 0)
3307	*counter += 1;
3308	}
3309	else
3310	info->index = -1;
3311
3312	if (!rtx_locs)
3313	rtx_locs = new hash_map <rtx, file_location>;
3314	rtx_locs->put (k: info->def, v: info->loc);
3315
3316	return true;
3317	}
3318
3319	/* Return the file location of DEFINE_* rtx X, which was previously
3320	returned by read_md_rtx. */
3321	file_location
3322	get_file_location (rtx x)
3323	{
3324	gcc_assert (rtx_locs);
3325	file_location *entry = rtx_locs->get (k: x);
3326	gcc_assert (entry);
3327	return *entry;
3328	}
3329
3330	/* Return the number of possible INSN_CODEs. Only meaningful once the
3331	whole file has been processed. */
3332	unsigned int
3333	get_num_insn_codes ()
3334	{
3335	return insn_sequence_num;
3336	}
3337
3338	/* Return the C test that says whether definition rtx DEF can be used,
3339	or "" if it can be used unconditionally. */
3340
3341	const char *
3342	get_c_test (rtx x)
3343	{
3344	switch (GET_CODE (x))
3345	{
3346	case DEFINE_INSN:
3347	case DEFINE_EXPAND:
3348	case DEFINE_SUBST:
3349	return XSTR (x, 2);
3350
3351	case DEFINE_SPLIT:
3352	case DEFINE_PEEPHOLE:
3353	case DEFINE_PEEPHOLE2:
3354	return XSTR (x, 1);
3355
3356	default:
3357	return "";
3358	}
3359	}
3360
3361	/* Helper functions for insn elision. */
3362
3363	/* Compute a hash function of a c_test structure, which is keyed
3364	by its ->expr field. */
3365	hashval_t
3366	hash_c_test (const void *x)
3367	{
3368	const struct c_test *a = (const struct c_test *) x;
3369	const unsigned char *base, *s = (const unsigned char *) a->expr;
3370	hashval_t hash;
3371	unsigned char c;
3372	unsigned int len;
3373
3374	base = s;
3375	hash = 0;
3376
3377	while ((c = *s++) != '\0')
3378	{
3379	hash += c + (c << 17);
3380	hash ^= hash >> 2;
3381	}
3382
3383	len = s - base;
3384	hash += len + (len << 17);
3385	hash ^= hash >> 2;
3386
3387	return hash;
3388	}
3389
3390	/* Compare two c_test expression structures. */
3391	int
3392	cmp_c_test (const void *x, const void *y)
3393	{
3394	const struct c_test *a = (const struct c_test *) x;
3395	const struct c_test *b = (const struct c_test *) y;
3396
3397	return !strcmp (s1: a->expr, s2: b->expr);
3398	}
3399
3400	/* Given a string representing a C test expression, look it up in the
3401	condition_table and report whether or not its value is known
3402	at compile time. Returns a tristate: 1 for known true, 0 for
3403	known false, -1 for unknown. */
3404	int
3405	maybe_eval_c_test (const char *expr)
3406	{
3407	const struct c_test *test;
3408	struct c_test dummy;
3409
3410	if (expr[0] == 0)
3411	return 1;
3412
3413	dummy.expr = expr;
3414	test = (const struct c_test *)htab_find (condition_table, &dummy);
3415	if (!test)
3416	return -1;
3417	return test->value;
3418	}
3419
3420	/* Record the C test expression EXPR in the condition_table, with
3421	value VAL. Duplicates clobber previous entries. */
3422
3423	void
3424	add_c_test (const char *expr, int value)
3425	{
3426	struct c_test *test;
3427
3428	if (expr[0] == 0)
3429	return;
3430
3431	test = XNEW (struct c_test);
3432	test->expr = expr;
3433	test->value = value;
3434
3435	*(htab_find_slot (condition_table, test, INSERT)) = test;
3436	}
3437
3438	/* For every C test, call CALLBACK with two arguments: a pointer to
3439	the condition structure and INFO. Stops when CALLBACK returns zero. */
3440	void
3441	traverse_c_tests (htab_trav callback, void *info)
3442	{
3443	if (condition_table)
3444	htab_traverse (condition_table, callback, info);
3445	}
3446
3447	/* Helper functions for define_predicate and define_special_predicate
3448	processing. Shared between genrecog.cc and genpreds.cc. */
3449
3450	static htab_t predicate_table;
3451	struct pred_data *first_predicate;
3452	static struct pred_data **last_predicate = &first_predicate;
3453
3454	static hashval_t
3455	hash_struct_pred_data (const void *ptr)
3456	{
3457	return htab_hash_string (((const struct pred_data *)ptr)->name);
3458	}
3459
3460	static int
3461	eq_struct_pred_data (const void *a, const void *b)
3462	{
3463	return !strcmp (s1: ((const struct pred_data *)a)->name,
3464	s2: ((const struct pred_data *)b)->name);
3465	}
3466
3467	struct pred_data *
3468	lookup_predicate (const char *name)
3469	{
3470	struct pred_data key;
3471	key.name = name;
3472	return (struct pred_data *) htab_find (predicate_table, &key);
3473	}
3474
3475	/* Record that predicate PRED can accept CODE. */
3476
3477	void
3478	add_predicate_code (struct pred_data *pred, enum rtx_code code)
3479	{
3480	if (!pred->codes[code])
3481	{
3482	pred->num_codes++;
3483	pred->codes[code] = true;
3484
3485	if (GET_RTX_CLASS (code) != RTX_CONST_OBJ)
3486	pred->allows_non_const = true;
3487
3488	if (code != REG
3489	&& code != SUBREG
3490	&& code != MEM
3491	&& code != CONCAT
3492	&& code != PARALLEL
3493	&& code != STRICT_LOW_PART
3494	&& code != ZERO_EXTRACT
3495	&& code != SCRATCH)
3496	pred->allows_non_lvalue = true;
3497
3498	if (pred->num_codes == 1)
3499	pred->singleton = code;
3500	else if (pred->num_codes == 2)
3501	pred->singleton = UNKNOWN;
3502	}
3503	}
3504
3505	void
3506	add_predicate (struct pred_data *pred)
3507	{
3508	void **slot = htab_find_slot (predicate_table, pred, INSERT);
3509	if (*slot)
3510	{
3511	error ("duplicate predicate definition for '%s'", pred->name);
3512	return;
3513	}
3514	*slot = pred;
3515	*last_predicate = pred;
3516	last_predicate = &pred->next;
3517	}
3518
3519	/* This array gives the initial content of the predicate table. It
3520	has entries for all predicates defined in recog.cc. */
3521
3522	struct std_pred_table
3523	{
3524	const char *name;
3525	bool special;
3526	bool allows_const_p;
3527	RTX_CODE codes[NUM_RTX_CODE];
3528	};
3529
3530	static const struct std_pred_table std_preds[] = {
3531	{.name: "general_operand", .special: false, .allows_const_p: true, .codes: {SUBREG, REG, MEM}},
3532	{.name: "address_operand", .special: true, .allows_const_p: true, .codes: {SUBREG, REG, MEM, PLUS, MINUS, MULT,
3533	ZERO_EXTEND, SIGN_EXTEND, AND}},
3534	{.name: "register_operand", .special: false, .allows_const_p: false, .codes: {SUBREG, REG}},
3535	{.name: "pmode_register_operand", .special: true, .allows_const_p: false, .codes: {SUBREG, REG}},
3536	{.name: "scratch_operand", .special: false, .allows_const_p: false, .codes: {SCRATCH, REG}},
3537	{.name: "immediate_operand", .special: false, .allows_const_p: true, .codes: {UNKNOWN}},
3538	{.name: "const_int_operand", .special: false, .allows_const_p: false, .codes: {CONST_INT}},
3539	#if TARGET_SUPPORTS_WIDE_INT
3540	{.name: "const_scalar_int_operand", .special: false, .allows_const_p: false, .codes: {CONST_INT, CONST_WIDE_INT}},
3541	{.name: "const_double_operand", .special: false, .allows_const_p: false, .codes: {CONST_DOUBLE}},
3542	#else
3543	{"const_double_operand", false, false, {CONST_INT, CONST_DOUBLE}},
3544	#endif
3545	{.name: "nonimmediate_operand", .special: false, .allows_const_p: false, .codes: {SUBREG, REG, MEM}},
3546	{.name: "nonmemory_operand", .special: false, .allows_const_p: true, .codes: {SUBREG, REG}},
3547	{.name: "push_operand", .special: false, .allows_const_p: false, .codes: {MEM}},
3548	{.name: "pop_operand", .special: false, .allows_const_p: false, .codes: {MEM}},
3549	{.name: "memory_operand", .special: false, .allows_const_p: false, .codes: {SUBREG, MEM}},
3550	{.name: "indirect_operand", .special: false, .allows_const_p: false, .codes: {SUBREG, MEM}},
3551	{.name: "ordered_comparison_operator", .special: false, .allows_const_p: false, .codes: {EQ, NE,
3552	LE, LT, GE, GT,
3553	LEU, LTU, GEU, GTU}},
3554	{.name: "comparison_operator", .special: false, .allows_const_p: false, .codes: {EQ, NE,
3555	LE, LT, GE, GT,
3556	LEU, LTU, GEU, GTU,
3557	UNORDERED, ORDERED,
3558	UNEQ, UNGE, UNGT,
3559	UNLE, UNLT, LTGT}}
3560	};
3561	#define NUM_KNOWN_STD_PREDS ARRAY_SIZE (std_preds)
3562
3563	/* Initialize the table of predicate definitions, starting with
3564	the information we have on generic predicates. */
3565
3566	static void
3567	init_predicate_table (void)
3568	{
3569	size_t i, j;
3570	struct pred_data *pred;
3571
3572	predicate_table = htab_create_alloc (37, hash_struct_pred_data,
3573	eq_struct_pred_data, 0,
3574	xcalloc, free);
3575
3576	for (i = 0; i < NUM_KNOWN_STD_PREDS; i++)
3577	{
3578	pred = XCNEW (struct pred_data);
3579	pred->name = std_preds[i].name;
3580	pred->special = std_preds[i].special;
3581
3582	for (j = 0; std_preds[i].codes[j] != 0; j++)
3583	add_predicate_code (pred, code: std_preds[i].codes[j]);
3584
3585	if (std_preds[i].allows_const_p)
3586	for (j = 0; j < NUM_RTX_CODE; j++)
3587	if (GET_RTX_CLASS (j) == RTX_CONST_OBJ)
3588	add_predicate_code (pred, code: (enum rtx_code) j);
3589
3590	add_predicate (pred);
3591	}
3592	}
3593
3594	/* These functions allow linkage with print-rtl.cc. Also, some generators
3595	like to annotate their output with insn names. */
3596
3597	/* Holds an array of names indexed by insn_code_number. */
3598	static char **insn_name_ptr = 0;
3599	static int insn_name_ptr_size = 0;
3600
3601	const char *
3602	get_insn_name (int code)
3603	{
3604	if (code < insn_name_ptr_size)
3605	return insn_name_ptr[code];
3606	else
3607	return NULL;
3608	}
3609
3610	static void
3611	record_insn_name (int code, const char *name)
3612	{
3613	static const char *last_real_name = "insn";
3614	static int last_real_code = 0;
3615	char *new_name;
3616
3617	if (insn_name_ptr_size <= code)
3618	{
3619	int new_size;
3620	new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512);
3621	insn_name_ptr = XRESIZEVEC (char *, insn_name_ptr, new_size);
3622	memset (s: insn_name_ptr + insn_name_ptr_size, c: 0,
3623	n: sizeof (char *) * (new_size - insn_name_ptr_size));
3624	insn_name_ptr_size = new_size;
3625	}
3626
3627	if (!name || name[0] == '\0')
3628	{
3629	new_name = XNEWVAR (char, strlen (last_real_name) + 10);
3630	sprintf (s: new_name, format: "%s+%d", last_real_name, code - last_real_code);
3631	}
3632	else
3633	{
3634	last_real_name = new_name = xstrdup (name);
3635	last_real_code = code;
3636	}
3637
3638	insn_name_ptr[code] = new_name;
3639	}
3640
3641	/* Make STATS describe the operands that appear in rtx X. */
3642
3643	static void
3644	get_pattern_stats_1 (struct pattern_stats *stats, rtx x)
3645	{
3646	RTX_CODE code;
3647	int i;
3648	int len;
3649	const char *fmt;
3650
3651	if (x == NULL_RTX)
3652	return;
3653
3654	code = GET_CODE (x);
3655	switch (code)
3656	{
3657	case MATCH_OPERAND:
3658	case MATCH_OPERATOR:
3659	case MATCH_PARALLEL:
3660	stats->max_opno = MAX (stats->max_opno, XINT (x, 0));
3661	break;
3662
3663	case MATCH_DUP:
3664	case MATCH_OP_DUP:
3665	case MATCH_PAR_DUP:
3666	stats->num_dups++;
3667	stats->max_dup_opno = MAX (stats->max_dup_opno, XINT (x, 0));
3668	break;
3669
3670	case MATCH_SCRATCH:
3671	if (stats->min_scratch_opno == -1)
3672	stats->min_scratch_opno = XINT (x, 0);
3673	else
3674	stats->min_scratch_opno = MIN (stats->min_scratch_opno, XINT (x, 0));
3675	stats->max_scratch_opno = MAX (stats->max_scratch_opno, XINT (x, 0));
3676	break;
3677
3678	default:
3679	break;
3680	}
3681
3682	fmt = GET_RTX_FORMAT (code);
3683	len = GET_RTX_LENGTH (code);
3684	for (i = 0; i < len; i++)
3685	{
3686	if (fmt[i] == 'e' || fmt[i] == 'u')
3687	get_pattern_stats_1 (stats, XEXP (x, i));
3688	else if (fmt[i] == 'E')
3689	{
3690	int j;
3691	for (j = 0; j < XVECLEN (x, i); j++)
3692	get_pattern_stats_1 (stats, XVECEXP (x, i, j));
3693	}
3694	}
3695	}
3696
3697	/* Make STATS describe the operands that appear in instruction pattern
3698	PATTERN. */
3699
3700	void
3701	get_pattern_stats (struct pattern_stats *stats, rtvec pattern)
3702	{
3703	int i, len;
3704
3705	stats->max_opno = -1;
3706	stats->max_dup_opno = -1;
3707	stats->min_scratch_opno = -1;
3708	stats->max_scratch_opno = -1;
3709	stats->num_dups = 0;
3710
3711	len = GET_NUM_ELEM (pattern);
3712	for (i = 0; i < len; i++)
3713	get_pattern_stats_1 (stats, RTVEC_ELT (pattern, i));
3714
3715	stats->num_generator_args = stats->max_opno + 1;
3716	stats->num_insn_operands = MAX (stats->max_opno,
3717	stats->max_scratch_opno) + 1;
3718	stats->num_operand_vars = MAX (stats->max_opno,
3719	MAX (stats->max_dup_opno,
3720	stats->max_scratch_opno)) + 1;
3721	}
3722
3723	/* Return the emit_* function that should be used for pattern X, or NULL
3724	if we can't pick a particular type at compile time and should instead
3725	fall back to "emit". */
3726
3727	const char *
3728	get_emit_function (rtx x)
3729	{
3730	switch (classify_insn (x))
3731	{
3732	case INSN:
3733	return "emit_insn";
3734
3735	case CALL_INSN:
3736	return "emit_call_insn";
3737
3738	case JUMP_INSN:
3739	return "emit_jump_insn";
3740
3741	case UNKNOWN:
3742	return NULL;
3743
3744	default:
3745	gcc_unreachable ();
3746	}
3747	}
3748
3749	/* Return true if we must emit a barrier after pattern X. */
3750
3751	bool
3752	needs_barrier_p (rtx x)
3753	{
3754	return (GET_CODE (x) == SET
3755	&& GET_CODE (SET_DEST (x)) == PC
3756	&& GET_CODE (SET_SRC (x)) == LABEL_REF);
3757	}
3758
3759	#define NS "NULL"
3760	#define ZS "'\\0'"
3761	#define OPTAB_CL(o, p, c, b, l) { #o, p, #b, ZS, #l, o, c, UNKNOWN, 1 },
3762	#define OPTAB_CX(o, p) { #o, p, NULL, NULL, NULL, o, UNKNOWN, UNKNOWN, 1 },
3763	#define OPTAB_CD(o, p) { #o, p, NS, ZS, NS, o, UNKNOWN, UNKNOWN, 2 },
3764	#define OPTAB_NL(o, p, c, b, s, l) { #o, p, #b, #s, #l, o, c, c, 3 },
3765	#define OPTAB_NC(o, p, c) { #o, p, NS, ZS, NS, o, c, c, 3 },
3766	#define OPTAB_NX(o, p) { #o, p, NULL, NULL, NULL, o, UNKNOWN, UNKNOWN, 3 },
3767	#define OPTAB_VL(o, p, c, b, s, l) { #o, p, #b, #s, #l, o, c, UNKNOWN, 3 },
3768	#define OPTAB_VC(o, p, c) { #o, p, NS, ZS, NS, o, c, UNKNOWN, 3 },
3769	#define OPTAB_VX(o, p) { #o, p, NULL, NULL, NULL, o, UNKNOWN, UNKNOWN, 3 },
3770	#define OPTAB_DC(o, p, c) { #o, p, NS, ZS, NS, o, c, c, 4 },
3771	#define OPTAB_D(o, p) { #o, p, NS, ZS, NS, o, UNKNOWN, UNKNOWN, 4 },
3772
3773	/* An array of all optabs. Note that the same optab can appear more
3774	than once, with a different pattern. */
3775	optab_def optabs[] = {
3776	{ .name: "unknown_optab", NULL, NS, ZS, NS, .op: unknown_optab, .fcode: UNKNOWN, .rcode: UNKNOWN, .kind: 0 },
3777	#include "optabs.def"
3778	};
3779
3780	/* The number of entries in optabs[]. */
3781	unsigned int num_optabs = ARRAY_SIZE (optabs);
3782
3783	#undef OPTAB_CL
3784	#undef OPTAB_CX
3785	#undef OPTAB_CD
3786	#undef OPTAB_NL
3787	#undef OPTAB_NC
3788	#undef OPTAB_NX
3789	#undef OPTAB_VL
3790	#undef OPTAB_VC
3791	#undef OPTAB_VX
3792	#undef OPTAB_DC
3793	#undef OPTAB_D
3794
3795	/* Return true if instruction NAME matches pattern PAT, storing information
3796	about the match in P if so. */
3797
3798	static bool
3799	match_pattern (optab_pattern *p, const char *name, const char *pat)
3800	{
3801	bool force_float = false;
3802	bool force_int = false;
3803	bool force_partial_int = false;
3804	bool force_fixed = false;
3805
3806	if (pat == NULL)
3807	return false;
3808	for (; ; ++pat)
3809	{
3810	if (*pat != '$')
3811	{
3812	if (*pat != *name++)
3813	return false;
3814	if (*pat == '\0')
3815	return true;
3816	continue;
3817	}
3818	switch (*++pat)
3819	{
3820	case 'I':
3821	force_int = 1;
3822	break;
3823	case 'P':
3824	force_partial_int = 1;
3825	break;
3826	case 'F':
3827	force_float = 1;
3828	break;
3829	case 'Q':
3830	force_fixed = 1;
3831	break;
3832
3833	case 'a':
3834	case 'b':
3835	{
3836	int i;
3837
3838	/* This loop will stop at the first prefix match, so
3839	look through the modes in reverse order, in case
3840	there are extra CC modes and CC is a prefix of the
3841	CC modes (as it should be). */
3842	for (i = (MAX_MACHINE_MODE) - 1; i >= 0; i--)
3843	{
3844	const char *p, *q;
3845	for (p = GET_MODE_NAME (i), q = name; *p; p++, q++)
3846	if (TOLOWER (*p) != *q)
3847	break;
3848	if (*p == 0
3849	&& (! force_int || mode_class[i] == MODE_INT
3850	|| mode_class[i] == MODE_VECTOR_INT)
3851	&& (! force_partial_int
3852	|| mode_class[i] == MODE_INT
3853	|| mode_class[i] == MODE_PARTIAL_INT
3854	|| mode_class[i] == MODE_VECTOR_INT)
3855	&& (! force_float
3856	|| mode_class[i] == MODE_FLOAT
3857	|| mode_class[i] == MODE_DECIMAL_FLOAT
3858	|| mode_class[i] == MODE_COMPLEX_FLOAT
3859	|| mode_class[i] == MODE_VECTOR_FLOAT)
3860	&& (! force_fixed
3861	|| mode_class[i] == MODE_FRACT
3862	|| mode_class[i] == MODE_UFRACT
3863	|| mode_class[i] == MODE_ACCUM
3864	|| mode_class[i] == MODE_UACCUM
3865	|| mode_class[i] == MODE_VECTOR_FRACT
3866	|| mode_class[i] == MODE_VECTOR_UFRACT
3867	|| mode_class[i] == MODE_VECTOR_ACCUM
3868	|| mode_class[i] == MODE_VECTOR_UACCUM))
3869	break;
3870	}
3871
3872	if (i < 0)
3873	return false;
3874	name += strlen (GET_MODE_NAME (i));
3875	if (*pat == 'a')
3876	p->m1 = i;
3877	else
3878	p->m2 = i;
3879
3880	force_int = false;
3881	force_partial_int = false;
3882	force_float = false;
3883	force_fixed = false;
3884	}
3885	break;
3886
3887	default:
3888	gcc_unreachable ();
3889	}
3890	}
3891	}
3892
3893	/* Return true if NAME is the name of an optab, describing it in P if so. */
3894
3895	bool
3896	find_optab (optab_pattern *p, const char *name)
3897	{
3898	if (*name == 0 || *name == '*')
3899	return false;
3900
3901	/* See if NAME matches one of the patterns we have for the optabs
3902	we know about. */
3903	for (unsigned int pindex = 0; pindex < ARRAY_SIZE (optabs); pindex++)
3904	{
3905	p->m1 = p->m2 = 0;
3906	if (match_pattern (p, name, pat: optabs[pindex].pattern))
3907	{
3908	p->name = name;
3909	p->op = optabs[pindex].op;
3910	p->sort_num = (p->op << 20) | (p->m2 << 10) | p->m1;
3911	return true;
3912	}
3913	}
3914	return false;
3915	}
3916