1	/* Generate pattern matching and transform code shared between
2	GENERIC and GIMPLE folding code from match-and-simplify description.
3
4	Copyright (C) 2014-2024 Free Software Foundation, Inc.
5	Contributed by Richard Biener <rguenther@suse.de>
6	and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
7
8	This file is part of GCC.
9
10	GCC is free software; you can redistribute it and/or modify it under
11	the terms of the GNU General Public License as published by the Free
12	Software Foundation; either version 3, or (at your option) any later
13	version.
14
15	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16	WARRANTY; without even the implied warranty of MERCHANTABILITY or
17	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18	for more details.
19
20	You should have received a copy of the GNU General Public License
21	along with GCC; see the file COPYING3. If not see
22	<http://www.gnu.org/licenses/>. */
23
24	#include "bconfig.h"
25	#include "system.h"
26	#include "coretypes.h"
27	#include <cpplib.h>
28	#include "rich-location.h"
29	#include "errors.h"
30	#include "hash-table.h"
31	#include "hash-set.h"
32	#include "is-a.h"
33	#include "ordered-hash-map.h"
34
35
36	/* Stubs for GGC referenced through instantiations triggered by hash-map. */
37	void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
38	size_t, size_t MEM_STAT_DECL)
39	{
40	return NULL;
41	}
42	void ggc_free (void *)
43	{
44	}
45
46
47	/* Global state. */
48
49	/* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
50	unsigned verbose;
51
52
53	/* libccp helpers. */
54
55	static class line_maps *line_table;
56
57	/* The rich_location class within libcpp requires a way to expand
58	location_t instances, and relies on the client code
59	providing a symbol named
60	linemap_client_expand_location_to_spelling_point
61	to do this.
62
63	This is the implementation for genmatch. */
64
65	expanded_location
66	linemap_client_expand_location_to_spelling_point (const line_maps *set,
67	location_t loc,
68	enum location_aspect)
69	{
70	const struct line_map_ordinary *map;
71	loc = linemap_resolve_location (set, loc, lrk: LRK_SPELLING_LOCATION, loc_map: &map);
72	return linemap_expand_location (set, map, loc);
73	}
74
75	static bool
76	#if GCC_VERSION >= 4001
77	__attribute__((format (printf, 5, 0)))
78	#endif
79	diagnostic_cb (cpp_reader *, enum cpp_diagnostic_level errtype,
80	enum cpp_warning_reason, rich_location *richloc,
81	const char *msg, va_list *ap)
82	{
83	const line_map_ordinary *map;
84	location_t location = richloc->get_loc ();
85	linemap_resolve_location (line_table, loc: location, lrk: LRK_SPELLING_LOCATION, loc_map: &map);
86	expanded_location loc = linemap_expand_location (line_table, map, loc: location);
87	fprintf (stderr, format: "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
88	(errtype == CPP_DL_WARNING) ? "warning" : "error");
89	vfprintf (stderr, format: msg, arg: *ap);
90	fprintf (stderr, format: "\n");
91	FILE *f = fopen (loc.file, "r");
92	if (f)
93	{
94	char buf[128];
95	while (loc.line > 0)
96	{
97	if (!fgets (buf, 128, f))
98	goto notfound;
99	if (buf[strlen (s: buf) - 1] != '\n')
100	{
101	if (loc.line > 1)
102	loc.line++;
103	}
104	loc.line--;
105	}
106	fprintf (stderr, format: "%s", buf);
107	for (int i = 0; i < loc.column - 1; ++i)
108	fputc (' ', stderr);
109	fputc ('^', stderr);
110	fputc ('\n', stderr);
111	notfound:
112	fclose (stream: f);
113	}
114
115	if (errtype == CPP_DL_FATAL)
116	exit (status: 1);
117	return false;
118	}
119
120	static void
121	#if GCC_VERSION >= 4001
122	__attribute__((format (printf, 2, 3)))
123	#endif
124	fatal_at (const cpp_token *tk, const char *msg, ...)
125	{
126	rich_location richloc (line_table, tk->src_loc);
127	va_list ap;
128	va_start (ap, msg);
129	diagnostic_cb (NULL, errtype: CPP_DL_FATAL, CPP_W_NONE, richloc: &richloc, msg, ap: &ap);
130	va_end (ap);
131	}
132
133	static void
134	#if GCC_VERSION >= 4001
135	__attribute__((format (printf, 2, 3)))
136	#endif
137	fatal_at (location_t loc, const char *msg, ...)
138	{
139	rich_location richloc (line_table, loc);
140	va_list ap;
141	va_start (ap, msg);
142	diagnostic_cb (NULL, errtype: CPP_DL_FATAL, CPP_W_NONE, richloc: &richloc, msg, ap: &ap);
143	va_end (ap);
144	}
145
146	static void
147	#if GCC_VERSION >= 4001
148	__attribute__((format (printf, 2, 3)))
149	#endif
150	warning_at (const cpp_token *tk, const char *msg, ...)
151	{
152	rich_location richloc (line_table, tk->src_loc);
153	va_list ap;
154	va_start (ap, msg);
155	diagnostic_cb (NULL, errtype: CPP_DL_WARNING, CPP_W_NONE, richloc: &richloc, msg, ap: &ap);
156	va_end (ap);
157	}
158
159	static void
160	#if GCC_VERSION >= 4001
161	__attribute__((format (printf, 2, 3)))
162	#endif
163	warning_at (location_t loc, const char *msg, ...)
164	{
165	rich_location richloc (line_table, loc);
166	va_list ap;
167	va_start (ap, msg);
168	diagnostic_cb (NULL, errtype: CPP_DL_WARNING, CPP_W_NONE, richloc: &richloc, msg, ap: &ap);
169	va_end (ap);
170	}
171
172	/* Like fprintf, but print INDENT spaces at the beginning. */
173
174	static void
175	#if GCC_VERSION >= 4001
176	__attribute__((format (printf, 3, 4)))
177	#endif
178	fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
179	{
180	va_list ap;
181	for (; indent >= 8; indent -= 8)
182	fputc ('\t', f);
183	fprintf (stream: f, format: "%*s", indent, "");
184	va_start (ap, format);
185	vfprintf (s: f, format: format, arg: ap);
186	va_end (ap);
187	}
188
189	/* Secondary stream for fp_decl. */
190	static FILE *header_file;
191
192	/* Start or continue emitting a declaration in fprintf-like manner,
193	printing both to F and global header_file, if non-null. */
194	static void
195	#if GCC_VERSION >= 4001
196	__attribute__((format (printf, 2, 3)))
197	#endif
198	fp_decl (FILE *f, const char *format, ...)
199	{
200	va_list ap;
201	va_start (ap, format);
202	vfprintf (s: f, format: format, arg: ap);
203	va_end (ap);
204
205	if (!header_file)
206	return;
207
208	va_start (ap, format);
209	vfprintf (s: header_file, format: format, arg: ap);
210	va_end (ap);
211	}
212
213	/* Finish a declaration being emitted by fp_decl. */
214	static void
215	fp_decl_done (FILE *f, const char *trailer)
216	{
217	fprintf (stream: f, format: "%s\n", trailer);
218	if (header_file)
219	fprintf (stream: header_file, format: "%s;", trailer);
220	}
221
222	/* Line numbers for use by indirect line directives. */
223	static vec<int> dbg_line_numbers;
224
225	static void
226	write_header_declarations (bool gimple, FILE *f)
227	{
228	fprintf (stream: f, format: "\nextern void\n%s_dump_logs (const char *file1, int line1_id, "
229	"const char *file2, int line2, bool simplify);\n",
230	gimple ? "gimple" : "generic");
231	}
232
233	static void
234	define_dump_logs (bool gimple, FILE *f)
235	{
236	if (dbg_line_numbers.is_empty ())
237	return;
238
239	fprintf (stream: f , format: "void\n%s_dump_logs (const char *file1, int line1_id, "
240	"const char *file2, int line2, bool simplify)\n{\n",
241	gimple ? "gimple" : "generic");
242
243	fprintf_indent (f, indent: 2, format: "static int dbg_line_numbers[%d] = {",
244	dbg_line_numbers.length ());
245
246	for (unsigned i = 0; i < dbg_line_numbers.length () - 1; i++)
247	{
248	if (i % 20 == 0)
249	fprintf (stream: f, format: "\n\t");
250
251	fprintf (stream: f, format: "%d, ", dbg_line_numbers[i]);
252	}
253	fprintf (stream: f, format: "%d\n };\n\n", dbg_line_numbers.last ());
254
255
256	fprintf_indent (f, indent: 2, format: "fprintf (dump_file, \"%%s "
257	"%%s:%%d, %%s:%%d\\n\",\n");
258	fprintf_indent (f, indent: 10, format: "simplify ? \"Applying pattern\" : "
259	"\"Matching expression\", file1, "
260	"dbg_line_numbers[line1_id], file2, line2);");
261
262	fprintf (stream: f, format: "\n}\n\n");
263	}
264
265	static void
266	output_line_directive (FILE *f, location_t location,
267	bool dumpfile = false, bool fnargs = false,
268	bool indirect_line_numbers = false)
269	{
270	typedef pair_hash<nofree_string_hash, int_hash<int, -1>> location_hash;
271	static hash_map<location_hash, int> loc_id_map;
272	const line_map_ordinary *map;
273	linemap_resolve_location (line_table, loc: location, lrk: LRK_SPELLING_LOCATION, loc_map: &map);
274	expanded_location loc = linemap_expand_location (line_table, map, loc: location);
275	if (dumpfile)
276	{
277	/* When writing to a dumpfile only dump the filename. */
278	const char *file = strrchr (s: loc.file, DIR_SEPARATOR);
279	#if defined(DIR_SEPARATOR_2)
280	const char *pos2 = strrchr (loc.file, DIR_SEPARATOR_2);
281	if (pos2 && (!file || (pos2 > file)))
282	file = pos2;
283	#endif
284	if (!file)
285	file = loc.file;
286	else
287	++file;
288
289	if (fnargs)
290	{
291	if (indirect_line_numbers)
292	{
293	bool existed;
294	int &loc_id = loc_id_map.get_or_insert (
295	k: std::make_pair (x&: file, y&: loc.line), existed: &existed);
296	if (!existed)
297	{
298	loc_id = dbg_line_numbers.length ();
299	dbg_line_numbers.safe_push (obj: loc.line);
300	}
301
302	fprintf (stream: f, format: "\"%s\", %d", file, loc_id);
303	}
304	else
305	fprintf (stream: f, format: "\"%s\", %d", file, loc.line);
306	}
307	else
308	fprintf (stream: f, format: "%s:%d", file, loc.line);
309	}
310	else if (verbose >= 2)
311	/* Other gen programs really output line directives here, at least for
312	development it's right now more convenient to have line information
313	from the generated file. Still keep the directives as comment for now
314	to easily back-point to the meta-description. */
315	fprintf (stream: f, format: "/* #line %d \"%s\" */\n", loc.line, loc.file);
316	}
317
318	/* Find the file to write into next. We try to evenly distribute the contents
319	over the different files. */
320
321	#define SIZED_BASED_CHUNKS 1
322
323	static FILE *
324	choose_output (const vec<FILE *> &parts)
325	{
326	#ifdef SIZED_BASED_CHUNKS
327	FILE *shortest = NULL;
328	long min = 0;
329	for (FILE *part : parts)
330	{
331	long len = ftell (stream: part);
332	if (!shortest || min > len)
333	shortest = part, min = len;
334	}
335	return shortest;
336	#else
337	static int current_file;
338	return parts[current_file++ % parts.length ()];
339	#endif
340	}
341
342
343	/* Pull in tree codes and builtin function codes from their
344	definition files. */
345
346	#define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
347	enum tree_code {
348	#include "tree.def"
349	MAX_TREE_CODES
350	};
351	#undef DEFTREECODE
352
353	#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
354	enum built_in_function {
355	#include "builtins.def"
356	END_BUILTINS
357	};
358
359	#define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
360	enum internal_fn {
361	#include "internal-fn.def"
362	IFN_LAST
363	};
364
365	enum combined_fn {
366	#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
367	CFN_##ENUM = int (ENUM),
368	#include "builtins.def"
369
370	#define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
371	CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
372	#include "internal-fn.def"
373
374	CFN_LAST
375	};
376
377	#include "case-cfn-macros.h"
378
379	/* Return true if CODE represents a commutative tree code. Otherwise
380	return false. */
381	bool
382	commutative_tree_code (enum tree_code code)
383	{
384	switch (code)
385	{
386	case PLUS_EXPR:
387	case MULT_EXPR:
388	case MULT_HIGHPART_EXPR:
389	case MIN_EXPR:
390	case MAX_EXPR:
391	case BIT_IOR_EXPR:
392	case BIT_XOR_EXPR:
393	case BIT_AND_EXPR:
394	case NE_EXPR:
395	case EQ_EXPR:
396	case UNORDERED_EXPR:
397	case ORDERED_EXPR:
398	case UNEQ_EXPR:
399	case LTGT_EXPR:
400	case TRUTH_AND_EXPR:
401	case TRUTH_XOR_EXPR:
402	case TRUTH_OR_EXPR:
403	case WIDEN_MULT_EXPR:
404	case VEC_WIDEN_MULT_HI_EXPR:
405	case VEC_WIDEN_MULT_LO_EXPR:
406	case VEC_WIDEN_MULT_EVEN_EXPR:
407	case VEC_WIDEN_MULT_ODD_EXPR:
408	return true;
409
410	default:
411	break;
412	}
413	return false;
414	}
415
416	/* Return true if CODE represents a ternary tree code for which the
417	first two operands are commutative. Otherwise return false. */
418	bool
419	commutative_ternary_tree_code (enum tree_code code)
420	{
421	switch (code)
422	{
423	case WIDEN_MULT_PLUS_EXPR:
424	case WIDEN_MULT_MINUS_EXPR:
425	case DOT_PROD_EXPR:
426	return true;
427
428	default:
429	break;
430	}
431	return false;
432	}
433
434	/* Return true if CODE is a comparison. */
435
436	bool
437	comparison_code_p (enum tree_code code)
438	{
439	switch (code)
440	{
441	case EQ_EXPR:
442	case NE_EXPR:
443	case ORDERED_EXPR:
444	case UNORDERED_EXPR:
445	case LTGT_EXPR:
446	case UNEQ_EXPR:
447	case GT_EXPR:
448	case GE_EXPR:
449	case LT_EXPR:
450	case LE_EXPR:
451	case UNGT_EXPR:
452	case UNGE_EXPR:
453	case UNLT_EXPR:
454	case UNLE_EXPR:
455	return true;
456
457	default:
458	break;
459	}
460	return false;
461	}
462
463
464	/* Base class for all identifiers the parser knows. */
465
466	class id_base : public nofree_ptr_hash<id_base>
467	{
468	public:
469	enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
470
471	id_base (id_kind, const char *, int = -1);
472
473	hashval_t hashval;
474	int nargs;
475	const char *id;
476
477	/* hash_table support. */
478	static inline hashval_t hash (const id_base *);
479	static inline int equal (const id_base *, const id_base *);
480	};
481
482	inline hashval_t
483	id_base::hash (const id_base *op)
484	{
485	return op->hashval;
486	}
487
488	inline int
489	id_base::equal (const id_base *op1,
490	const id_base *op2)
491	{
492	return (op1->hashval == op2->hashval
493	&& strcmp (s1: op1->id, s2: op2->id) == 0);
494	}
495
496	/* The special id "null", which matches nothing. */
497	static id_base *null_id;
498
499	/* Hashtable of known pattern operators. This is pre-seeded from
500	all known tree codes and all known builtin function ids. */
501	static hash_table<id_base> *operators;
502
503	id_base::id_base (id_kind kind_, const char *id_, int nargs_)
504	{
505	kind = kind_;
506	id = id_;
507	nargs = nargs_;
508	hashval = htab_hash_string (id);
509	}
510
511	/* Identifier that maps to a tree code. */
512
513	class operator_id : public id_base
514	{
515	public:
516	operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
517	const char *tcc_)
518	: id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
519	enum tree_code code;
520	const char *tcc;
521	};
522
523	/* Identifier that maps to a builtin or internal function code. */
524
525	class fn_id : public id_base
526	{
527	public:
528	fn_id (enum built_in_function fn_, const char *id_)
529	: id_base (id_base::FN, id_), fn (fn_) {}
530	fn_id (enum internal_fn fn_, const char *id_)
531	: id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
532	unsigned int fn;
533	};
534
535	class simplify;
536
537	/* Identifier that maps to a user-defined predicate. */
538
539	class predicate_id : public id_base
540	{
541	public:
542	predicate_id (const char *id_)
543	: id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
544	vec<simplify *> matchers;
545	};
546
547	/* Identifier that maps to a operator defined by a 'for' directive. */
548
549	class user_id : public id_base
550	{
551	public:
552	user_id (const char *id_, bool is_oper_list_ = false)
553	: id_base (id_base::USER, id_), substitutes (vNULL),
554	used (false), is_oper_list (is_oper_list_) {}
555	vec<id_base *> substitutes;
556	bool used;
557	bool is_oper_list;
558	};
559
560	template<>
561	template<>
562	inline bool
563	is_a_helper <fn_id *>::test (id_base *id)
564	{
565	return id->kind == id_base::FN;
566	}
567
568	template<>
569	template<>
570	inline bool
571	is_a_helper <operator_id *>::test (id_base *id)
572	{
573	return id->kind == id_base::CODE;
574	}
575
576	template<>
577	template<>
578	inline bool
579	is_a_helper <predicate_id *>::test (id_base *id)
580	{
581	return id->kind == id_base::PREDICATE;
582	}
583
584	template<>
585	template<>
586	inline bool
587	is_a_helper <user_id *>::test (id_base *id)
588	{
589	return id->kind == id_base::USER;
590	}
591
592	/* If ID has a pair of consecutive, commutative operands, return the
593	index of the first, otherwise return -1. */
594
595	static int
596	commutative_op (id_base *id)
597	{
598	if (operator_id *code = dyn_cast <operator_id *> (p: id))
599	{
600	if (commutative_tree_code (code: code->code)
601	|| commutative_ternary_tree_code (code: code->code))
602	return 0;
603	return -1;
604	}
605	if (fn_id *fn = dyn_cast <fn_id *> (p: id))
606	switch (fn->fn)
607	{
608	CASE_CFN_FMA:
609	case CFN_FMS:
610	case CFN_FNMA:
611	case CFN_FNMS:
612	return 0;
613
614	case CFN_COND_ADD:
615	case CFN_COND_MUL:
616	case CFN_COND_MIN:
617	case CFN_COND_MAX:
618	case CFN_COND_FMIN:
619	case CFN_COND_FMAX:
620	case CFN_COND_AND:
621	case CFN_COND_IOR:
622	case CFN_COND_XOR:
623	case CFN_COND_FMA:
624	case CFN_COND_FMS:
625	case CFN_COND_FNMA:
626	case CFN_COND_FNMS:
627	case CFN_COND_LEN_ADD:
628	case CFN_COND_LEN_MUL:
629	case CFN_COND_LEN_MIN:
630	case CFN_COND_LEN_MAX:
631	case CFN_COND_LEN_FMIN:
632	case CFN_COND_LEN_FMAX:
633	case CFN_COND_LEN_AND:
634	case CFN_COND_LEN_IOR:
635	case CFN_COND_LEN_XOR:
636	case CFN_COND_LEN_FMA:
637	case CFN_COND_LEN_FMS:
638	case CFN_COND_LEN_FNMA:
639	case CFN_COND_LEN_FNMS:
640	return 1;
641
642	default:
643	return -1;
644	}
645	if (user_id *uid = dyn_cast<user_id *> (p: id))
646	{
647	int res = commutative_op (id: uid->substitutes[0]);
648	if (res < 0)
649	return -1;
650	for (unsigned i = 1; i < uid->substitutes.length (); ++i)
651	if (res != commutative_op (id: uid->substitutes[i]))
652	return -1;
653	return res;
654	}
655	return -1;
656	}
657
658	/* Add a predicate identifier to the hash. */
659
660	static predicate_id *
661	add_predicate (const char *id)
662	{
663	predicate_id *p = new predicate_id (id);
664	id_base **slot = operators->find_slot_with_hash (comparable: p, hash: p->hashval, insert: INSERT);
665	if (*slot)
666	fatal ("duplicate id definition");
667	*slot = p;
668	return p;
669	}
670
671	/* Add a tree code identifier to the hash. */
672
673	static void
674	add_operator (enum tree_code code, const char *id,
675	const char *tcc, unsigned nargs)
676	{
677	if (strcmp (s1: tcc, s2: "tcc_unary") != 0
678	&& strcmp (s1: tcc, s2: "tcc_binary") != 0
679	&& strcmp (s1: tcc, s2: "tcc_comparison") != 0
680	&& strcmp (s1: tcc, s2: "tcc_expression") != 0
681	/* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
682	&& strcmp (s1: tcc, s2: "tcc_reference") != 0
683	/* To have INTEGER_CST and friends as "predicate operators". */
684	&& strcmp (s1: tcc, s2: "tcc_constant") != 0
685	/* And allow CONSTRUCTOR for vector initializers. */
686	&& !(code == CONSTRUCTOR)
687	/* Allow SSA_NAME as predicate operator. */
688	&& !(code == SSA_NAME))
689	return;
690	/* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
691	if (code == ADDR_EXPR)
692	nargs = 0;
693	operator_id *op = new operator_id (code, id, nargs, tcc);
694	id_base **slot = operators->find_slot_with_hash (comparable: op, hash: op->hashval, insert: INSERT);
695	if (*slot)
696	fatal ("duplicate id definition");
697	*slot = op;
698	}
699
700	/* Add a built-in or internal function identifier to the hash. ID is
701	the name of its CFN_* enumeration value. */
702
703	template <typename T>
704	static void
705	add_function (T code, const char *id)
706	{
707	fn_id *fn = new fn_id (code, id);
708	id_base **slot = operators->find_slot_with_hash (comparable: fn, hash: fn->hashval, insert: INSERT);
709	if (*slot)
710	fatal ("duplicate id definition");
711	*slot = fn;
712	}
713
714	/* Helper for easy comparing ID with tree code CODE. */
715
716	static bool
717	operator==(id_base &id, enum tree_code code)
718	{
719	if (operator_id *oid = dyn_cast <operator_id *> (p: &id))
720	return oid->code == code;
721	return false;
722	}
723
724	/* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
725
726	id_base *
727	get_operator (const char *id, bool allow_null = false)
728	{
729	if (allow_null && strcmp (s1: id, s2: "null") == 0)
730	return null_id;
731
732	id_base tem (id_base::CODE, id);
733
734	id_base *op = operators->find_with_hash (comparable: &tem, hash: tem.hashval);
735	if (op)
736	{
737	/* If this is a user-defined identifier track whether it was used. */
738	if (user_id *uid = dyn_cast<user_id *> (p: op))
739	uid->used = true;
740	return op;
741	}
742
743	char *id2;
744	bool all_upper = true;
745	bool all_lower = true;
746	for (unsigned int i = 0; id[i]; ++i)
747	if (ISUPPER (id[i]))
748	all_lower = false;
749	else if (ISLOWER (id[i]))
750	all_upper = false;
751	if (all_lower)
752	{
753	/* Try in caps with _EXPR appended. */
754	id2 = ACONCAT ((id, "_EXPR", NULL));
755	for (unsigned int i = 0; id2[i]; ++i)
756	id2[i] = TOUPPER (id2[i]);
757	}
758	else if (all_upper && startswith (str: id, prefix: "IFN_"))
759	/* Try CFN_ instead of IFN_. */
760	id2 = ACONCAT (("CFN_", id + 4, NULL));
761	else if (all_upper && startswith (str: id, prefix: "BUILT_IN_"))
762	/* Try prepending CFN_. */
763	id2 = ACONCAT (("CFN_", id, NULL));
764	else
765	return NULL;
766
767	new (&tem) id_base (id_base::CODE, id2);
768	return operators->find_with_hash (comparable: &tem, hash: tem.hashval);
769	}
770
771	/* Return the comparison operators that results if the operands are
772	swapped. This is safe for floating-point. */
773
774	id_base *
775	swap_tree_comparison (operator_id *p)
776	{
777	switch (p->code)
778	{
779	case EQ_EXPR:
780	case NE_EXPR:
781	case ORDERED_EXPR:
782	case UNORDERED_EXPR:
783	case LTGT_EXPR:
784	case UNEQ_EXPR:
785	return p;
786	case GT_EXPR:
787	return get_operator (id: "LT_EXPR");
788	case GE_EXPR:
789	return get_operator (id: "LE_EXPR");
790	case LT_EXPR:
791	return get_operator (id: "GT_EXPR");
792	case LE_EXPR:
793	return get_operator (id: "GE_EXPR");
794	case UNGT_EXPR:
795	return get_operator (id: "UNLT_EXPR");
796	case UNGE_EXPR:
797	return get_operator (id: "UNLE_EXPR");
798	case UNLT_EXPR:
799	return get_operator (id: "UNGT_EXPR");
800	case UNLE_EXPR:
801	return get_operator (id: "UNGE_EXPR");
802	default:
803	gcc_unreachable ();
804	}
805	}
806
807	typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
808
809
810	/* The AST produced by parsing of the pattern definitions. */
811
812	class dt_operand;
813	class capture_info;
814
815	/* The base class for operands. */
816
817	class operand {
818	public:
819	enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
820	operand (enum op_type type_, location_t loc_)
821	: type (type_), location (loc_) {}
822	enum op_type type;
823	location_t location;
824	virtual void gen_transform (FILE *, int, const char *, bool, int,
825	const char *, capture_info *,
826	dt_operand ** = 0,
827	int = 0)
828	{ gcc_unreachable (); }
829	};
830
831	/* A predicate operand. Predicates are leafs in the AST. */
832
833	class predicate : public operand
834	{
835	public:
836	predicate (predicate_id *p_, location_t loc)
837	: operand (OP_PREDICATE, loc), p (p_) {}
838	predicate_id *p;
839	};
840
841	/* An operand that constitutes an expression. Expressions include
842	function calls and user-defined predicate invocations. */
843
844	class expr : public operand
845	{
846	public:
847	expr (id_base *operation_, location_t loc, bool is_commutative_ = false)
848	: operand (OP_EXPR, loc), operation (operation_),
849	ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
850	is_generic (false), force_single_use (false), force_leaf (false),
851	opt_grp (0) {}
852	expr (expr *e)
853	: operand (OP_EXPR, e->location), operation (e->operation),
854	ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
855	is_generic (e->is_generic), force_single_use (e->force_single_use),
856	force_leaf (e->force_leaf), opt_grp (e->opt_grp) {}
857	void append_op (operand *op) { ops.safe_push (obj: op); }
858	/* The operator and its operands. */
859	id_base *operation;
860	vec<operand *> ops;
861	/* An explicitely specified type - used exclusively for conversions. */
862	const char *expr_type;
863	/* Whether the operation is to be applied commutatively. This is
864	later lowered to two separate patterns. */
865	bool is_commutative;
866	/* Whether the expression is expected to be in GENERIC form. */
867	bool is_generic;
868	/* Whether pushing any stmt to the sequence should be conditional
869	on this expression having a single-use. */
870	bool force_single_use;
871	/* Whether in the result expression this should be a leaf node
872	with any children simplified down to simple operands. */
873	bool force_leaf;
874	/* If non-zero, the group for optional handling. */
875	unsigned char opt_grp;
876	void gen_transform (FILE *f, int, const char *, bool, int,
877	const char *, capture_info *,
878	dt_operand ** = 0, int = 0) override;
879	};
880
881	/* An operator that is represented by native C code. This is always
882	a leaf operand in the AST. This class is also used to represent
883	the code to be generated for 'if' and 'with' expressions. */
884
885	class c_expr : public operand
886	{
887	public:
888	/* A mapping of an identifier and its replacement. Used to apply
889	'for' lowering. */
890	class id_tab {
891	public:
892	const char *id;
893	const char *oper;
894	id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
895	};
896
897	c_expr (cpp_reader *r_, location_t loc,
898	vec<cpp_token> code_, unsigned nr_stmts_,
899	vec<id_tab> ids_, cid_map_t *capture_ids_)
900	: operand (OP_C_EXPR, loc), r (r_), code (code_),
901	capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
902	/* cpplib tokens and state to transform this back to source. */
903	cpp_reader *r;
904	vec<cpp_token> code;
905	cid_map_t *capture_ids;
906	/* The number of statements parsed (well, the number of ';'s). */
907	unsigned nr_stmts;
908	/* The identifier replacement vector. */
909	vec<id_tab> ids;
910	void gen_transform (FILE *f, int, const char *, bool, int,
911	const char *, capture_info *,
912	dt_operand ** = 0, int = 0) final override;
913	};
914
915	/* A wrapper around another operand that captures its value. */
916
917	class capture : public operand
918	{
919	public:
920	capture (location_t loc, unsigned where_, operand *what_, bool value_)
921	: operand (OP_CAPTURE, loc), where (where_), value_match (value_),
922	what (what_) {}
923	/* Identifier index for the value. */
924	unsigned where;
925	/* Whether in a match of two operands the compare should be for
926	equal values rather than equal atoms (boils down to a type
927	check or not). */
928	bool value_match;
929	/* The captured value. */
930	operand *what;
931	void gen_transform (FILE *f, int, const char *, bool, int,
932	const char *, capture_info *,
933	dt_operand ** = 0, int = 0) final override;
934	};
935
936	/* if expression. */
937
938	class if_expr : public operand
939	{
940	public:
941	if_expr (location_t loc)
942	: operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
943	c_expr *cond;
944	operand *trueexpr;
945	operand *falseexpr;
946	};
947
948	/* with expression. */
949
950	class with_expr : public operand
951	{
952	public:
953	with_expr (location_t loc)
954	: operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
955	c_expr *with;
956	operand *subexpr;
957	};
958
959	template<>
960	template<>
961	inline bool
962	is_a_helper <capture *>::test (operand *op)
963	{
964	return op->type == operand::OP_CAPTURE;
965	}
966
967	template<>
968	template<>
969	inline bool
970	is_a_helper <predicate *>::test (operand *op)
971	{
972	return op->type == operand::OP_PREDICATE;
973	}
974
975	template<>
976	template<>
977	inline bool
978	is_a_helper <c_expr *>::test (operand *op)
979	{
980	return op->type == operand::OP_C_EXPR;
981	}
982
983	template<>
984	template<>
985	inline bool
986	is_a_helper <expr *>::test (operand *op)
987	{
988	return op->type == operand::OP_EXPR;
989	}
990
991	template<>
992	template<>
993	inline bool
994	is_a_helper <if_expr *>::test (operand *op)
995	{
996	return op->type == operand::OP_IF;
997	}
998
999	template<>
1000	template<>
1001	inline bool
1002	is_a_helper <with_expr *>::test (operand *op)
1003	{
1004	return op->type == operand::OP_WITH;
1005	}
1006
1007	/* The main class of a pattern and its transform. This is used to
1008	represent both (simplify ...) and (match ...) kinds. The AST
1009	duplicates all outer 'if' and 'for' expressions here so each
1010	simplify can exist in isolation. */
1011
1012	class simplify
1013	{
1014	public:
1015	enum simplify_kind { SIMPLIFY, MATCH };
1016
1017	simplify (simplify_kind kind_, unsigned id_, operand *match_,
1018	operand *result_, vec<vec<user_id *> > for_vec_,
1019	cid_map_t *capture_ids_)
1020	: kind (kind_), id (id_), match (match_), result (result_),
1021	for_vec (for_vec_), for_subst_vec (vNULL),
1022	capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
1023
1024	simplify_kind kind;
1025	/* ID. This is kept to easily associate related simplifies expanded
1026	from the same original one. */
1027	unsigned id;
1028	/* The expression that is matched against the GENERIC or GIMPLE IL. */
1029	operand *match;
1030	/* For a (simplify ...) an expression with ifs and withs with the expression
1031	produced when the pattern applies in the leafs.
1032	For a (match ...) the leafs are either empty if it is a simple predicate
1033	or the single expression specifying the matched operands. */
1034	class operand *result;
1035	/* Collected 'for' expression operators that have to be replaced
1036	in the lowering phase. */
1037	vec<vec<user_id *> > for_vec;
1038	vec<std::pair<user_id *, id_base *> > for_subst_vec;
1039	/* A map of capture identifiers to indexes. */
1040	cid_map_t *capture_ids;
1041	int capture_max;
1042	};
1043
1044	/* Debugging routines for dumping the AST. */
1045
1046	DEBUG_FUNCTION void
1047	print_operand (operand *o, FILE *f = stderr, bool flattened = false)
1048	{
1049	if (capture *c = dyn_cast<capture *> (p: o))
1050	{
1051	if (c->what && flattened == false)
1052	print_operand (o: c->what, f, flattened);
1053	fprintf (stream: f, format: "@%u", c->where);
1054	}
1055
1056	else if (predicate *p = dyn_cast<predicate *> (p: o))
1057	fprintf (stream: f, format: "%s", p->p->id);
1058
1059	else if (is_a<c_expr *> (p: o))
1060	fprintf (stream: f, format: "c_expr");
1061
1062	else if (expr *e = dyn_cast<expr *> (p: o))
1063	{
1064	if (e->ops.length () == 0)
1065	fprintf (stream: f, format: "%s", e->operation->id);
1066	else
1067	{
1068	fprintf (stream: f, format: "(%s", e->operation->id);
1069
1070	if (flattened == false)
1071	{
1072	for (unsigned i = 0; i < e->ops.length (); ++i)
1073	{
1074	putc (' ', f);
1075	print_operand (o: e->ops[i], f, flattened);
1076	}
1077	}
1078	putc (')', f);
1079	}
1080	}
1081
1082	else
1083	gcc_unreachable ();
1084	}
1085
1086	DEBUG_FUNCTION void
1087	print_matches (class simplify *s, FILE *f = stderr)
1088	{
1089	fprintf (stream: f, format: "for expression: ");
1090	print_operand (o: s->match, f);
1091	putc ('\n', f);
1092	}
1093
1094
1095	/* AST lowering. */
1096
1097	/* Lowering of commutative operators. */
1098
1099	static void
1100	cartesian_product (const vec< vec<operand *> >& ops_vector,
1101	vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
1102	{
1103	if (n == ops_vector.length ())
1104	{
1105	vec<operand *> xv = v.copy ();
1106	result.safe_push (obj: xv);
1107	return;
1108	}
1109
1110	for (unsigned i = 0; i < ops_vector[n].length (); ++i)
1111	{
1112	v[n] = ops_vector[n][i];
1113	cartesian_product (ops_vector, result, v, n: n + 1);
1114	}
1115	}
1116
1117	/* Lower OP to two operands in case it is marked as commutative. */
1118
1119	static vec<operand *>
1120	commutate (operand *op, vec<vec<user_id *> > &for_vec)
1121	{
1122	vec<operand *> ret = vNULL;
1123
1124	if (capture *c = dyn_cast <capture *> (p: op))
1125	{
1126	if (!c->what)
1127	{
1128	ret.safe_push (obj: op);
1129	return ret;
1130	}
1131	vec<operand *> v = commutate (op: c->what, for_vec);
1132	for (unsigned i = 0; i < v.length (); ++i)
1133	{
1134	capture *nc = new capture (c->location, c->where, v[i],
1135	c->value_match);
1136	ret.safe_push (obj: nc);
1137	}
1138	return ret;
1139	}
1140
1141	expr *e = dyn_cast <expr *> (p: op);
1142	if (!e || e->ops.length () == 0)
1143	{
1144	ret.safe_push (obj: op);
1145	return ret;
1146	}
1147
1148	vec< vec<operand *> > ops_vector = vNULL;
1149	for (unsigned i = 0; i < e->ops.length (); ++i)
1150	ops_vector.safe_push (obj: commutate (op: e->ops[i], for_vec));
1151
1152	auto_vec< vec<operand *> > result;
1153	auto_vec<operand *> v (e->ops.length ());
1154	v.quick_grow_cleared (len: e->ops.length ());
1155	cartesian_product (ops_vector, result, v, n: 0);
1156
1157
1158	for (unsigned i = 0; i < result.length (); ++i)
1159	{
1160	expr *ne = new expr (e);
1161	ne->is_commutative = false;
1162	for (unsigned j = 0; j < result[i].length (); ++j)
1163	ne->append_op (op: result[i][j]);
1164	ret.safe_push (obj: ne);
1165	}
1166
1167	if (!e->is_commutative)
1168	return ret;
1169
1170	/* The operation is always binary if it isn't inherently commutative. */
1171	int natural_opno = commutative_op (id: e->operation);
1172	unsigned int opno = natural_opno >= 0 ? natural_opno : 0;
1173	for (unsigned i = 0; i < result.length (); ++i)
1174	{
1175	expr *ne = new expr (e);
1176	if (operator_id *r = dyn_cast <operator_id *> (p: ne->operation))
1177	{
1178	if (comparison_code_p (code: r->code))
1179	ne->operation = swap_tree_comparison (p: r);
1180	}
1181	else if (user_id *p = dyn_cast <user_id *> (p: ne->operation))
1182	{
1183	bool found_compare = false;
1184	for (unsigned j = 0; j < p->substitutes.length (); ++j)
1185	if (operator_id *q = dyn_cast <operator_id *> (p: p->substitutes[j]))
1186	{
1187	if (comparison_code_p (code: q->code)
1188	&& swap_tree_comparison (p: q) != q)
1189	{
1190	found_compare = true;
1191	break;
1192	}
1193	}
1194	if (found_compare)
1195	{
1196	user_id *newop = new user_id ("<internal>");
1197	for (unsigned j = 0; j < p->substitutes.length (); ++j)
1198	{
1199	id_base *subst = p->substitutes[j];
1200	if (operator_id *q = dyn_cast <operator_id *> (p: subst))
1201	{
1202	if (comparison_code_p (code: q->code))
1203	subst = swap_tree_comparison (p: q);
1204	}
1205	newop->substitutes.safe_push (obj: subst);
1206	}
1207	ne->operation = newop;
1208	/* Search for 'p' inside the for vector and push 'newop'
1209	to the same level. */
1210	for (unsigned j = 0; newop && j < for_vec.length (); ++j)
1211	for (unsigned k = 0; k < for_vec[j].length (); ++k)
1212	if (for_vec[j][k] == p)
1213	{
1214	for_vec[j].safe_push (obj: newop);
1215	newop = NULL;
1216	break;
1217	}
1218	}
1219	}
1220	ne->is_commutative = false;
1221	for (unsigned j = 0; j < result[i].length (); ++j)
1222	{
1223	int old_j = (j == opno ? opno + 1 : j == opno + 1 ? opno : j);
1224	ne->append_op (op: result[i][old_j]);
1225	}
1226	ret.safe_push (obj: ne);
1227	}
1228
1229	return ret;
1230	}
1231
1232	/* Lower operations marked as commutative in the AST of S and push
1233	the resulting patterns to SIMPLIFIERS. */
1234
1235	static void
1236	lower_commutative (simplify *s, vec<simplify *>& simplifiers)
1237	{
1238	vec<operand *> matchers = commutate (op: s->match, for_vec&: s->for_vec);
1239	for (unsigned i = 0; i < matchers.length (); ++i)
1240	{
1241	simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1242	s->for_vec, s->capture_ids);
1243	simplifiers.safe_push (obj: ns);
1244	}
1245	}
1246
1247	/* Strip conditional operations using group GRP from O and its
1248	children if STRIP, else replace them with an unconditional operation. */
1249
1250	operand *
1251	lower_opt (operand *o, unsigned char grp, bool strip)
1252	{
1253	if (capture *c = dyn_cast<capture *> (p: o))
1254	{
1255	if (c->what)
1256	return new capture (c->location, c->where,
1257	lower_opt (o: c->what, grp, strip),
1258	c->value_match);
1259	else
1260	return c;
1261	}
1262
1263	expr *e = dyn_cast<expr *> (p: o);
1264	if (!e)
1265	return o;
1266
1267	if (e->opt_grp == grp)
1268	{
1269	if (strip)
1270	return lower_opt (o: e->ops[0], grp, strip);
1271
1272	expr *ne = new expr (e);
1273	ne->opt_grp = 0;
1274	ne->append_op (op: lower_opt (o: e->ops[0], grp, strip));
1275	return ne;
1276	}
1277
1278	expr *ne = new expr (e);
1279	for (unsigned i = 0; i < e->ops.length (); ++i)
1280	ne->append_op (op: lower_opt (o: e->ops[i], grp, strip));
1281
1282	return ne;
1283	}
1284
1285	/* Determine whether O or its children uses the conditional operation
1286	group GRP. */
1287
1288	static bool
1289	has_opt (operand *o, unsigned char grp)
1290	{
1291	if (capture *c = dyn_cast<capture *> (p: o))
1292	{
1293	if (c->what)
1294	return has_opt (o: c->what, grp);
1295	else
1296	return false;
1297	}
1298
1299	expr *e = dyn_cast<expr *> (p: o);
1300	if (!e)
1301	return false;
1302
1303	if (e->opt_grp == grp)
1304	return true;
1305
1306	for (unsigned i = 0; i < e->ops.length (); ++i)
1307	if (has_opt (o: e->ops[i], grp))
1308	return true;
1309
1310	return false;
1311	}
1312
1313	/* Lower conditional convert operators in O, expanding it to a vector
1314	if required. */
1315
1316	static vec<operand *>
1317	lower_opt (operand *o)
1318	{
1319	vec<operand *> v1 = vNULL, v2;
1320
1321	v1.safe_push (obj: o);
1322
1323	/* Conditional operations are lowered to a pattern with the
1324	operation and one without. All different conditional operation
1325	groups are lowered separately. */
1326
1327	for (unsigned i = 1; i <= 10; ++i)
1328	{
1329	v2 = vNULL;
1330	for (unsigned j = 0; j < v1.length (); ++j)
1331	if (has_opt (o: v1[j], grp: i))
1332	{
1333	v2.safe_push (obj: lower_opt (o: v1[j], grp: i, strip: false));
1334	v2.safe_push (obj: lower_opt (o: v1[j], grp: i, strip: true));
1335	}
1336
1337	if (v2 != vNULL)
1338	{
1339	v1 = vNULL;
1340	for (unsigned j = 0; j < v2.length (); ++j)
1341	v1.safe_push (obj: v2[j]);
1342	}
1343	}
1344
1345	return v1;
1346	}
1347
1348	/* Lower conditional convert operators in the AST of S and push
1349	the resulting multiple patterns to SIMPLIFIERS. */
1350
1351	static void
1352	lower_opt (simplify *s, vec<simplify *>& simplifiers)
1353	{
1354	vec<operand *> matchers = lower_opt (o: s->match);
1355	for (unsigned i = 0; i < matchers.length (); ++i)
1356	{
1357	simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1358	s->for_vec, s->capture_ids);
1359	simplifiers.safe_push (obj: ns);
1360	}
1361	}
1362
1363	/* Lower the compare operand of COND_EXPRs to a
1364	GENERIC and a GIMPLE variant. */
1365
1366	static vec<operand *>
1367	lower_cond (operand *o)
1368	{
1369	vec<operand *> ro = vNULL;
1370
1371	if (capture *c = dyn_cast<capture *> (p: o))
1372	{
1373	if (c->what)
1374	{
1375	vec<operand *> lop = vNULL;
1376	lop = lower_cond (o: c->what);
1377
1378	for (unsigned i = 0; i < lop.length (); ++i)
1379	ro.safe_push (obj: new capture (c->location, c->where, lop[i],
1380	c->value_match));
1381	return ro;
1382	}
1383	}
1384
1385	expr *e = dyn_cast<expr *> (p: o);
1386	if (!e || e->ops.length () == 0)
1387	{
1388	ro.safe_push (obj: o);
1389	return ro;
1390	}
1391
1392	vec< vec<operand *> > ops_vector = vNULL;
1393	for (unsigned i = 0; i < e->ops.length (); ++i)
1394	ops_vector.safe_push (obj: lower_cond (o: e->ops[i]));
1395
1396	auto_vec< vec<operand *> > result;
1397	auto_vec<operand *> v (e->ops.length ());
1398	v.quick_grow_cleared (len: e->ops.length ());
1399	cartesian_product (ops_vector, result, v, n: 0);
1400
1401	for (unsigned i = 0; i < result.length (); ++i)
1402	{
1403	expr *ne = new expr (e);
1404	for (unsigned j = 0; j < result[i].length (); ++j)
1405	ne->append_op (op: result[i][j]);
1406	ro.safe_push (obj: ne);
1407	/* If this is a COND with a captured expression or an
1408	expression with two operands then also match a GENERIC
1409	form on the compare. */
1410	if (*e->operation == COND_EXPR
1411	&& ((is_a <capture *> (p: e->ops[0])
1412	&& as_a <capture *> (p: e->ops[0])->what
1413	&& is_a <expr *> (p: as_a <capture *> (p: e->ops[0])->what)
1414	&& as_a <expr *>
1415	(p: as_a <capture *> (p: e->ops[0])->what)->ops.length () == 2)
1416	|| (is_a <expr *> (p: e->ops[0])
1417	&& as_a <expr *> (p: e->ops[0])->ops.length () == 2)))
1418	{
1419	ne = new expr (e);
1420	for (unsigned j = 0; j < result[i].length (); ++j)
1421	ne->append_op (op: result[i][j]);
1422	if (capture *c = dyn_cast <capture *> (p: ne->ops[0]))
1423	{
1424	expr *ocmp = as_a <expr *> (p: c->what);
1425	expr *cmp = new expr (ocmp);
1426	for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1427	cmp->append_op (op: ocmp->ops[j]);
1428	cmp->is_generic = true;
1429	ne->ops[0] = new capture (c->location, c->where, cmp,
1430	c->value_match);
1431	}
1432	else
1433	{
1434	expr *ocmp = as_a <expr *> (p: ne->ops[0]);
1435	expr *cmp = new expr (ocmp);
1436	for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1437	cmp->append_op (op: ocmp->ops[j]);
1438	cmp->is_generic = true;
1439	ne->ops[0] = cmp;
1440	}
1441	ro.safe_push (obj: ne);
1442	}
1443	}
1444
1445	return ro;
1446	}
1447
1448	/* Lower the compare operand of COND_EXPRs to a
1449	GENERIC and a GIMPLE variant. */
1450
1451	static void
1452	lower_cond (simplify *s, vec<simplify *>& simplifiers)
1453	{
1454	vec<operand *> matchers = lower_cond (o: s->match);
1455	for (unsigned i = 0; i < matchers.length (); ++i)
1456	{
1457	simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1458	s->for_vec, s->capture_ids);
1459	ns->for_subst_vec.safe_splice (src: s->for_subst_vec);
1460	simplifiers.safe_push (obj: ns);
1461	}
1462	}
1463
1464	/* Return true if O refers to ID. */
1465
1466	bool
1467	contains_id (operand *o, user_id *id)
1468	{
1469	if (capture *c = dyn_cast<capture *> (p: o))
1470	return c->what && contains_id (o: c->what, id);
1471
1472	if (expr *e = dyn_cast<expr *> (p: o))
1473	{
1474	if (e->operation == id)
1475	return true;
1476	for (unsigned i = 0; i < e->ops.length (); ++i)
1477	if (contains_id (o: e->ops[i], id))
1478	return true;
1479	return false;
1480	}
1481
1482	if (with_expr *w = dyn_cast <with_expr *> (p: o))
1483	return (contains_id (o: w->with, id)
1484	|| contains_id (o: w->subexpr, id));
1485
1486	if (if_expr *ife = dyn_cast <if_expr *> (p: o))
1487	return (contains_id (o: ife->cond, id)
1488	|| contains_id (o: ife->trueexpr, id)
1489	|| (ife->falseexpr && contains_id (o: ife->falseexpr, id)));
1490
1491	if (c_expr *ce = dyn_cast<c_expr *> (p: o))
1492	return ce->capture_ids && ce->capture_ids->get (k: id->id);
1493
1494	return false;
1495	}
1496
1497
1498	/* In AST operand O replace operator ID with operator WITH. */
1499
1500	operand *
1501	replace_id (operand *o, user_id *id, id_base *with)
1502	{
1503	/* Deep-copy captures and expressions, replacing operations as
1504	needed. */
1505	if (capture *c = dyn_cast<capture *> (p: o))
1506	{
1507	if (!c->what)
1508	return c;
1509	return new capture (c->location, c->where,
1510	replace_id (o: c->what, id, with), c->value_match);
1511	}
1512	else if (expr *e = dyn_cast<expr *> (p: o))
1513	{
1514	expr *ne = new expr (e);
1515	if (e->operation == id)
1516	ne->operation = with;
1517	for (unsigned i = 0; i < e->ops.length (); ++i)
1518	ne->append_op (op: replace_id (o: e->ops[i], id, with));
1519	return ne;
1520	}
1521	else if (with_expr *w = dyn_cast <with_expr *> (p: o))
1522	{
1523	with_expr *nw = new with_expr (w->location);
1524	nw->with = as_a <c_expr *> (p: replace_id (o: w->with, id, with));
1525	nw->subexpr = replace_id (o: w->subexpr, id, with);
1526	return nw;
1527	}
1528	else if (if_expr *ife = dyn_cast <if_expr *> (p: o))
1529	{
1530	if_expr *nife = new if_expr (ife->location);
1531	nife->cond = as_a <c_expr *> (p: replace_id (o: ife->cond, id, with));
1532	nife->trueexpr = replace_id (o: ife->trueexpr, id, with);
1533	if (ife->falseexpr)
1534	nife->falseexpr = replace_id (o: ife->falseexpr, id, with);
1535	return nife;
1536	}
1537
1538	/* For c_expr we simply record a string replacement table which is
1539	applied at code-generation time. */
1540	if (c_expr *ce = dyn_cast<c_expr *> (p: o))
1541	{
1542	vec<c_expr::id_tab> ids = ce->ids.copy ();
1543	ids.safe_push (obj: c_expr::id_tab (id->id, with->id));
1544	return new c_expr (ce->r, ce->location,
1545	ce->code, ce->nr_stmts, ids, ce->capture_ids);
1546	}
1547
1548	return o;
1549	}
1550
1551	/* Return true if the binary operator OP is ok for delayed substitution
1552	during for lowering. */
1553
1554	static bool
1555	binary_ok (operator_id *op)
1556	{
1557	switch (op->code)
1558	{
1559	case PLUS_EXPR:
1560	case MINUS_EXPR:
1561	case MULT_EXPR:
1562	case TRUNC_DIV_EXPR:
1563	case CEIL_DIV_EXPR:
1564	case FLOOR_DIV_EXPR:
1565	case ROUND_DIV_EXPR:
1566	case TRUNC_MOD_EXPR:
1567	case CEIL_MOD_EXPR:
1568	case FLOOR_MOD_EXPR:
1569	case ROUND_MOD_EXPR:
1570	case RDIV_EXPR:
1571	case EXACT_DIV_EXPR:
1572	case MIN_EXPR:
1573	case MAX_EXPR:
1574	case BIT_IOR_EXPR:
1575	case BIT_XOR_EXPR:
1576	case BIT_AND_EXPR:
1577	return true;
1578	default:
1579	return false;
1580	}
1581	}
1582
1583	/* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1584
1585	static void
1586	lower_for (simplify *sin, vec<simplify *>& simplifiers)
1587	{
1588	vec<vec<user_id *> >& for_vec = sin->for_vec;
1589	unsigned worklist_start = 0;
1590	auto_vec<simplify *> worklist;
1591	worklist.safe_push (obj: sin);
1592
1593	/* Lower each recorded for separately, operating on the
1594	set of simplifiers created by the previous one.
1595	Lower inner-to-outer so inner for substitutes can refer
1596	to operators replaced by outer fors. */
1597	for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1598	{
1599	vec<user_id *>& ids = for_vec[fi];
1600	unsigned n_ids = ids.length ();
1601	unsigned max_n_opers = 0;
1602	bool can_delay_subst = true;
1603	for (unsigned i = 0; i < n_ids; ++i)
1604	{
1605	if (ids[i]->substitutes.length () > max_n_opers)
1606	max_n_opers = ids[i]->substitutes.length ();
1607	/* Require that all substitutes are of the same kind so that
1608	if we delay substitution to the result op code generation
1609	can look at the first substitute for deciding things like
1610	types of operands. */
1611	enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1612	for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1613	if (ids[i]->substitutes[j]->kind != kind)
1614	can_delay_subst = false;
1615	else if (operator_id *op
1616	= dyn_cast <operator_id *> (p: ids[i]->substitutes[j]))
1617	{
1618	operator_id *op0
1619	= as_a <operator_id *> (p: ids[i]->substitutes[0]);
1620	if (strcmp (s1: op->tcc, s2: "tcc_comparison") == 0
1621	&& strcmp (s1: op0->tcc, s2: "tcc_comparison") == 0)
1622	;
1623	/* Unfortunately we can't just allow all tcc_binary. */
1624	else if (strcmp (s1: op->tcc, s2: "tcc_binary") == 0
1625	&& strcmp (s1: op0->tcc, s2: "tcc_binary") == 0
1626	&& binary_ok (op)
1627	&& binary_ok (op: op0))
1628	;
1629	else if ((strcmp (s1: op->id + 1, s2: "SHIFT_EXPR") == 0
1630	|| strcmp (s1: op->id + 1, s2: "ROTATE_EXPR") == 0)
1631	&& (strcmp (s1: op0->id + 1, s2: "SHIFT_EXPR") == 0
1632	|| strcmp (s1: op0->id + 1, s2: "ROTATE_EXPR") == 0))
1633	;
1634	else
1635	can_delay_subst = false;
1636	}
1637	else if (is_a <fn_id *> (p: ids[i]->substitutes[j]))
1638	;
1639	else
1640	can_delay_subst = false;
1641	}
1642	if (sin->kind == simplify::MATCH
1643	&& can_delay_subst)
1644	continue;
1645
1646	unsigned worklist_end = worklist.length ();
1647	for (unsigned si = worklist_start; si < worklist_end; ++si)
1648	{
1649	simplify *s = worklist[si];
1650	for (unsigned j = 0; j < max_n_opers; ++j)
1651	{
1652	operand *match_op = s->match;
1653	operand *result_op = s->result;
1654	auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
1655	bool skip = false;
1656	for (unsigned i = 0; i < n_ids; ++i)
1657	{
1658	user_id *id = ids[i];
1659	id_base *oper = id->substitutes[j % id->substitutes.length ()];
1660	if (oper == null_id
1661	&& (contains_id (o: match_op, id)
1662	|| contains_id (o: result_op, id)))
1663	{
1664	skip = true;
1665	break;
1666	}
1667	subst.quick_push (obj: std::make_pair (x&: id, y&: oper));
1668	if (sin->kind == simplify::SIMPLIFY
1669	|| !can_delay_subst)
1670	match_op = replace_id (o: match_op, id, with: oper);
1671	if (result_op
1672	&& !can_delay_subst)
1673	result_op = replace_id (o: result_op, id, with: oper);
1674	}
1675	if (skip)
1676	continue;
1677
1678	simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
1679	vNULL, s->capture_ids);
1680	ns->for_subst_vec.safe_splice (src: s->for_subst_vec);
1681	if (result_op
1682	&& can_delay_subst)
1683	ns->for_subst_vec.safe_splice (src: subst);
1684
1685	worklist.safe_push (obj: ns);
1686	}
1687	}
1688	worklist_start = worklist_end;
1689	}
1690
1691	/* Copy out the result from the last for lowering. */
1692	for (unsigned i = worklist_start; i < worklist.length (); ++i)
1693	simplifiers.safe_push (obj: worklist[i]);
1694	}
1695
1696	/* Lower the AST for everything in SIMPLIFIERS. */
1697
1698	static void
1699	lower (vec<simplify *>& simplifiers, bool gimple)
1700	{
1701	auto_vec<simplify *> out_simplifiers;
1702	for (auto s: simplifiers)
1703	lower_opt (s, simplifiers&: out_simplifiers);
1704
1705	simplifiers.truncate (size: 0);
1706	for (auto s: out_simplifiers)
1707	lower_commutative (s, simplifiers);
1708
1709	/* Lower for needs to happen before lowering cond
1710	to support (for cnd (cond vec_cond)). This is
1711	safe as substitution delay does not happen for
1712	cond or vec_cond. */
1713	out_simplifiers.truncate (size: 0);
1714	for (auto s: simplifiers)
1715	lower_for (sin: s, simplifiers&: out_simplifiers);
1716
1717	simplifiers.truncate (size: 0);
1718	if (gimple)
1719	for (auto s: out_simplifiers)
1720	lower_cond (s, simplifiers);
1721	else
1722	simplifiers.safe_splice (src: out_simplifiers);
1723	}
1724
1725
1726
1727
1728	/* The decision tree built for generating GIMPLE and GENERIC pattern
1729	matching code. It represents the 'match' expression of all
1730	simplifies and has those as its leafs. */
1731
1732	class dt_simplify;
1733
1734	/* A hash-map collecting semantically equivalent leafs in the decision
1735	tree for splitting out to separate functions. */
1736	struct sinfo
1737	{
1738	dt_simplify *s;
1739
1740	const char *fname;
1741	unsigned cnt;
1742	};
1743
1744	struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1745	sinfo *>
1746	{
1747	static inline hashval_t hash (const key_type &);
1748	static inline bool equal_keys (const key_type &, const key_type &);
1749	template <typename T> static inline void remove (T &) {}
1750	};
1751
1752	typedef ordered_hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1753	sinfo_map_t;
1754
1755	/* Current simplifier ID we are processing during insertion into the
1756	decision tree. */
1757	static unsigned current_id;
1758
1759	/* Decision tree base class, used for DT_NODE. */
1760
1761	class dt_node
1762	{
1763	public:
1764	enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1765
1766	enum dt_type type;
1767	unsigned level;
1768	dt_node *parent;
1769	vec<dt_node *> kids;
1770
1771	/* Statistics. */
1772	unsigned num_leafs;
1773	unsigned total_size;
1774	unsigned max_level;
1775
1776	dt_node (enum dt_type type_, dt_node *parent_)
1777	: type (type_), level (0), parent (parent_), kids (vNULL) {}
1778
1779	dt_node *append_node (dt_node *);
1780	dt_node *append_op (operand *, dt_node *parent, unsigned pos);
1781	dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
1782	dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
1783	unsigned pos);
1784	dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1785
1786	virtual void gen (FILE *, int, bool, int) {}
1787
1788	void gen_kids (FILE *, int, bool, int);
1789	void gen_kids_1 (FILE *, int, bool, int,
1790	const vec<dt_operand *> &, const vec<dt_operand *> &,
1791	const vec<dt_operand *> &, const vec<dt_operand *> &,
1792	const vec<dt_operand *> &, const vec<dt_node *> &);
1793
1794	void analyze (sinfo_map_t &);
1795	};
1796
1797	/* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1798
1799	class dt_operand : public dt_node
1800	{
1801	public:
1802	operand *op;
1803	dt_operand *match_dop;
1804	unsigned pos;
1805	bool value_match;
1806	unsigned for_id;
1807
1808	dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1809	dt_operand *parent_, unsigned pos_)
1810	: dt_node (type, parent_), op (op_), match_dop (match_dop_),
1811	pos (pos_), value_match (false), for_id (current_id) {}
1812
1813	void gen (FILE *, int, bool, int) final override;
1814	unsigned gen_predicate (FILE *, int, const char *, bool);
1815	unsigned gen_match_op (FILE *, int, const char *, bool);
1816
1817	unsigned gen_gimple_expr (FILE *, int, int);
1818	unsigned gen_generic_expr (FILE *, int, const char *);
1819
1820	char *get_name (char *);
1821	void gen_opname (char *, unsigned);
1822	};
1823
1824	/* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1825
1826	class dt_simplify : public dt_node
1827	{
1828	public:
1829	simplify *s;
1830	unsigned pattern_no;
1831	dt_operand **indexes;
1832	sinfo *info;
1833
1834	dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1835	: dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
1836	indexes (indexes_), info (NULL) {}
1837
1838	void gen_1 (FILE *, int, bool, operand *);
1839	void gen (FILE *f, int, bool, int) final override;
1840	};
1841
1842	template<>
1843	template<>
1844	inline bool
1845	is_a_helper <dt_operand *>::test (dt_node *n)
1846	{
1847	return (n->type == dt_node::DT_OPERAND
1848	|| n->type == dt_node::DT_MATCH
1849	|| n->type == dt_node::DT_TRUE);
1850	}
1851
1852	template<>
1853	template<>
1854	inline bool
1855	is_a_helper <dt_simplify *>::test (dt_node *n)
1856	{
1857	return n->type == dt_node::DT_SIMPLIFY;
1858	}
1859
1860
1861
1862	/* A container for the actual decision tree. */
1863
1864	class decision_tree
1865	{
1866	public:
1867	dt_node *root;
1868
1869	void insert (class simplify *, unsigned);
1870	void gen (vec <FILE *> &f, bool gimple);
1871	void print (FILE *f = stderr);
1872
1873	decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
1874
1875	static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1876	unsigned pos = 0, dt_node *parent = 0);
1877	static dt_node *find_node (vec<dt_node *>&, dt_node *);
1878	static bool cmp_node (dt_node *, dt_node *);
1879	static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1880	};
1881
1882	/* Compare two AST operands O1 and O2 and return true if they are equal. */
1883
1884	bool
1885	cmp_operand (operand *o1, operand *o2)
1886	{
1887	if (!o1 || !o2 || o1->type != o2->type)
1888	return false;
1889
1890	if (o1->type == operand::OP_PREDICATE)
1891	{
1892	predicate *p1 = as_a<predicate *>(p: o1);
1893	predicate *p2 = as_a<predicate *>(p: o2);
1894	return p1->p == p2->p;
1895	}
1896	else if (o1->type == operand::OP_EXPR)
1897	{
1898	expr *e1 = static_cast<expr *>(o1);
1899	expr *e2 = static_cast<expr *>(o2);
1900	if (e1->operation != e2->operation
1901	|| e1->is_generic != e2->is_generic)
1902	return false;
1903	if (e1->operation->kind == id_base::FN
1904	/* For function calls also compare number of arguments. */
1905	&& e1->ops.length () != e2->ops.length ())
1906	return false;
1907	return true;
1908	}
1909	else
1910	return false;
1911	}
1912
1913	/* Compare two decision tree nodes N1 and N2 and return true if they
1914	are equal. */
1915
1916	bool
1917	decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1918	{
1919	if (!n1 || !n2 || n1->type != n2->type)
1920	return false;
1921
1922	if (n1 == n2)
1923	return true;
1924
1925	if (n1->type == dt_node::DT_TRUE)
1926	return false;
1927
1928	if (n1->type == dt_node::DT_OPERAND)
1929	return cmp_operand (o1: (as_a<dt_operand *> (p: n1))->op,
1930	o2: (as_a<dt_operand *> (p: n2))->op);
1931	else if (n1->type == dt_node::DT_MATCH)
1932	return (((as_a<dt_operand *> (p: n1))->match_dop
1933	== (as_a<dt_operand *> (p: n2))->match_dop)
1934	&& ((as_a<dt_operand *> (p: n1))->value_match
1935	== (as_a<dt_operand *> (p: n2))->value_match));
1936	return false;
1937	}
1938
1939	/* Search OPS for a decision tree node like P and return it if found. */
1940
1941	dt_node *
1942	decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1943	{
1944	/* We can merge adjacent DT_TRUE. */
1945	if (p->type == dt_node::DT_TRUE
1946	&& !ops.is_empty ()
1947	&& ops.last ()->type == dt_node::DT_TRUE)
1948	return ops.last ();
1949	dt_operand *true_node = NULL;
1950	for (int i = ops.length () - 1; i >= 0; --i)
1951	{
1952	/* But we can't merge across DT_TRUE nodes as they serve as
1953	pattern order barriers to make sure that patterns apply
1954	in order of appearance in case multiple matches are possible. */
1955	if (ops[i]->type == dt_node::DT_TRUE)
1956	{
1957	if (! true_node
1958	|| as_a <dt_operand *> (p: ops[i])->for_id > true_node->for_id)
1959	true_node = as_a <dt_operand *> (p: ops[i]);
1960	}
1961	if (decision_tree::cmp_node (n1: ops[i], n2: p))
1962	{
1963	/* Unless we are processing the same pattern or the blocking
1964	pattern is before the one we are going to merge with. */
1965	if (true_node
1966	&& true_node->for_id != current_id
1967	&& true_node->for_id > as_a <dt_operand *> (p: ops[i])->for_id)
1968	{
1969	if (verbose >= 1)
1970	{
1971	location_t p_loc = 0;
1972	if (p->type == dt_node::DT_OPERAND)
1973	p_loc = as_a <dt_operand *> (p)->op->location;
1974	location_t op_loc = 0;
1975	if (ops[i]->type == dt_node::DT_OPERAND)
1976	op_loc = as_a <dt_operand *> (p: ops[i])->op->location;
1977	location_t true_loc = 0;
1978	true_loc = true_node->op->location;
1979	warning_at (loc: p_loc,
1980	msg: "failed to merge decision tree node");
1981	warning_at (loc: op_loc,
1982	msg: "with the following");
1983	warning_at (loc: true_loc,
1984	msg: "because of the following which serves as ordering "
1985	"barrier");
1986	}
1987	return NULL;
1988	}
1989	return ops[i];
1990	}
1991	}
1992	return NULL;
1993	}
1994
1995	/* Append N to the decision tree if it there is not already an existing
1996	identical child. */
1997
1998	dt_node *
1999	dt_node::append_node (dt_node *n)
2000	{
2001	dt_node *kid;
2002
2003	kid = decision_tree::find_node (ops&: kids, p: n);
2004	if (kid)
2005	return kid;
2006
2007	kids.safe_push (obj: n);
2008	n->level = this->level + 1;
2009
2010	return n;
2011	}
2012
2013	/* Append OP to the decision tree. */
2014
2015	dt_node *
2016	dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
2017	{
2018	dt_operand *parent_ = safe_as_a<dt_operand *> (p: parent);
2019	dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
2020	return append_node (n);
2021	}
2022
2023	/* Append a DT_TRUE decision tree node. */
2024
2025	dt_node *
2026	dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
2027	{
2028	dt_operand *parent_ = safe_as_a<dt_operand *> (p: parent);
2029	dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
2030	return append_node (n);
2031	}
2032
2033	/* Append a DT_MATCH decision tree node. */
2034
2035	dt_node *
2036	dt_node::append_match_op (operand *op, dt_operand *match_dop,
2037	dt_node *parent, unsigned pos)
2038	{
2039	dt_operand *parent_ = as_a<dt_operand *> (p: parent);
2040	dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
2041	return append_node (n);
2042	}
2043
2044	/* Append S to the decision tree. */
2045
2046	dt_node *
2047	dt_node::append_simplify (simplify *s, unsigned pattern_no,
2048	dt_operand **indexes)
2049	{
2050	dt_simplify *s2;
2051	dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
2052	for (unsigned i = 0; i < kids.length (); ++i)
2053	if ((s2 = dyn_cast <dt_simplify *> (p: kids[i]))
2054	&& (verbose >= 1
2055	|| s->match->location != s2->s->match->location))
2056	{
2057	/* With a nested patters, it's hard to avoid these in order
2058	to keep match.pd rules relatively small. */
2059	warning_at (loc: s->match->location, msg: "duplicate pattern");
2060	warning_at (loc: s2->s->match->location, msg: "previous pattern defined here");
2061	print_operand (o: s->match, stderr);
2062	fprintf (stderr, format: "\n");
2063	}
2064	return append_node (n);
2065	}
2066
2067	/* Analyze the node and its children. */
2068
2069	void
2070	dt_node::analyze (sinfo_map_t &map)
2071	{
2072	num_leafs = 0;
2073	total_size = 1;
2074	max_level = level;
2075
2076	if (type == DT_SIMPLIFY)
2077	{
2078	/* Populate the map of equivalent simplifies. */
2079	dt_simplify *s = as_a <dt_simplify *> (p: this);
2080	bool existed;
2081	sinfo *&si = map.get_or_insert (k: s, existed: &existed);
2082	if (!existed)
2083	{
2084	si = new sinfo;
2085	si->s = s;
2086	si->cnt = 1;
2087	si->fname = NULL;
2088	}
2089	else
2090	si->cnt++;
2091	s->info = si;
2092	num_leafs = 1;
2093	return;
2094	}
2095
2096	for (unsigned i = 0; i < kids.length (); ++i)
2097	{
2098	kids[i]->analyze (map);
2099	num_leafs += kids[i]->num_leafs;
2100	total_size += kids[i]->total_size;
2101	max_level = MAX (max_level, kids[i]->max_level);
2102	}
2103	}
2104
2105	/* Insert O into the decision tree and return the decision tree node found
2106	or created. */
2107
2108	dt_node *
2109	decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
2110	unsigned pos, dt_node *parent)
2111	{
2112	dt_node *q, *elm = 0;
2113
2114	if (capture *c = dyn_cast<capture *> (p: o))
2115	{
2116	unsigned capt_index = c->where;
2117
2118	if (indexes[capt_index] == 0)
2119	{
2120	if (c->what)
2121	q = insert_operand (p, o: c->what, indexes, pos, parent);
2122	else
2123	{
2124	q = elm = p->append_true_op (op: o, parent, pos);
2125	goto at_assert_elm;
2126	}
2127	// get to the last capture
2128	for (operand *what = c->what;
2129	what && is_a<capture *> (p: what);
2130	c = as_a<capture *> (p: what), what = c->what)
2131	;
2132
2133	if (!c->what)
2134	{
2135	unsigned cc_index = c->where;
2136	dt_operand *match_op = indexes[cc_index];
2137
2138	dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
2139	elm = decision_tree::find_node (ops&: p->kids, p: &temp);
2140
2141	if (elm == 0)
2142	{
2143	dt_operand match (dt_node::DT_MATCH, 0, match_op, 0, 0);
2144	match.value_match = c->value_match;
2145	elm = decision_tree::find_node (ops&: p->kids, p: &match);
2146	}
2147	}
2148	else
2149	{
2150	dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
2151	elm = decision_tree::find_node (ops&: p->kids, p: &temp);
2152	}
2153
2154	at_assert_elm:
2155	gcc_assert (elm->type == dt_node::DT_TRUE
2156	|| elm->type == dt_node::DT_OPERAND
2157	|| elm->type == dt_node::DT_MATCH);
2158	indexes[capt_index] = static_cast<dt_operand *> (elm);
2159	return q;
2160	}
2161	else
2162	{
2163	p = p->append_match_op (op: o, match_dop: indexes[capt_index], parent, pos);
2164	as_a <dt_operand *>(p)->value_match = c->value_match;
2165	if (c->what)
2166	return insert_operand (p, o: c->what, indexes, pos: 0, parent: p);
2167	else
2168	return p;
2169	}
2170	}
2171	p = p->append_op (op: o, parent, pos);
2172	q = p;
2173
2174	if (expr *e = dyn_cast <expr *>(p: o))
2175	{
2176	for (unsigned i = 0; i < e->ops.length (); ++i)
2177	q = decision_tree::insert_operand (p: q, o: e->ops[i], indexes, pos: i, parent: p);
2178	}
2179
2180	return q;
2181	}
2182
2183	/* Insert S into the decision tree. */
2184
2185	void
2186	decision_tree::insert (class simplify *s, unsigned pattern_no)
2187	{
2188	current_id = s->id;
2189	dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
2190	dt_node *p = decision_tree::insert_operand (p: root, o: s->match, indexes);
2191	p->append_simplify (s, pattern_no, indexes);
2192	}
2193
2194	/* Debug functions to dump the decision tree. */
2195
2196	DEBUG_FUNCTION void
2197	decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
2198	{
2199	if (p->type == dt_node::DT_NODE)
2200	fprintf (stream: f, format: "root");
2201	else
2202	{
2203	fprintf (stream: f, format: "|");
2204	for (unsigned i = 0; i < indent; i++)
2205	fprintf (stream: f, format: "-");
2206
2207	if (p->type == dt_node::DT_OPERAND)
2208	{
2209	dt_operand *dop = static_cast<dt_operand *>(p);
2210	print_operand (o: dop->op, f, flattened: true);
2211	}
2212	else if (p->type == dt_node::DT_TRUE)
2213	fprintf (stream: f, format: "true");
2214	else if (p->type == dt_node::DT_MATCH)
2215	fprintf (stream: f, format: "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
2216	else if (p->type == dt_node::DT_SIMPLIFY)
2217	{
2218	dt_simplify *s = static_cast<dt_simplify *> (p);
2219	fprintf (stream: f, format: "simplify_%u { ", s->pattern_no);
2220	for (int i = 0; i <= s->s->capture_max; ++i)
2221	fprintf (stream: f, format: "%p, ", (void *) s->indexes[i]);
2222	fprintf (stream: f, format: " } ");
2223	}
2224	if (is_a <dt_operand *> (p))
2225	fprintf (stream: f, format: " [%u]", as_a <dt_operand *> (p)->for_id);
2226	}
2227
2228	fprintf (stderr, format: " (%p, %p), %u, %u\n",
2229	(void *) p, (void *) p->parent, p->level, p->kids.length ());
2230
2231	for (unsigned i = 0; i < p->kids.length (); ++i)
2232	decision_tree::print_node (p: p->kids[i], f, indent: indent + 2);
2233	}
2234
2235	DEBUG_FUNCTION void
2236	decision_tree::print (FILE *f)
2237	{
2238	return decision_tree::print_node (p: root, f);
2239	}
2240
2241
2242	/* For GENERIC we have to take care of wrapping multiple-used
2243	expressions with side-effects in save_expr and preserve side-effects
2244	of expressions with omit_one_operand. Analyze captures in
2245	match, result and with expressions and perform early-outs
2246	on the outermost match expression operands for cases we cannot
2247	handle. */
2248
2249	class capture_info
2250	{
2251	public:
2252	capture_info (simplify *s, operand *, bool);
2253	void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
2254	bool walk_result (operand *o, bool, operand *);
2255	void walk_c_expr (c_expr *);
2256
2257	struct cinfo
2258	{
2259	bool expr_p;
2260	bool cse_p;
2261	bool force_no_side_effects_p;
2262	bool force_single_use;
2263	bool cond_expr_cond_p;
2264	unsigned long toplevel_msk;
2265	unsigned match_use_count;
2266	unsigned result_use_count;
2267	unsigned same_as;
2268	capture *c;
2269	};
2270
2271	auto_vec<cinfo> info;
2272	unsigned long force_no_side_effects;
2273	bool gimple;
2274	};
2275
2276	/* Analyze captures in S. */
2277
2278	capture_info::capture_info (simplify *s, operand *result, bool gimple_)
2279	{
2280	gimple = gimple_;
2281
2282	expr *e;
2283	if (s->kind == simplify::MATCH)
2284	{
2285	force_no_side_effects = -1;
2286	return;
2287	}
2288
2289	force_no_side_effects = 0;
2290	info.safe_grow_cleared (len: s->capture_max + 1, exact: true);
2291	for (int i = 0; i <= s->capture_max; ++i)
2292	info[i].same_as = i;
2293
2294	e = as_a <expr *> (p: s->match);
2295	for (unsigned i = 0; i < e->ops.length (); ++i)
2296	walk_match (o: e->ops[i], toplevel_arg: i,
2297	(i != 0 && *e->operation == COND_EXPR)
2298	|| *e->operation == TRUTH_ANDIF_EXPR
2299	|| *e->operation == TRUTH_ORIF_EXPR,
2300	i == 0 && *e->operation == COND_EXPR);
2301
2302	walk_result (o: s->result, false, result);
2303	}
2304
2305	/* Analyze captures in the match expression piece O. */
2306
2307	void
2308	capture_info::walk_match (operand *o, unsigned toplevel_arg,
2309	bool conditional_p, bool cond_expr_cond_p)
2310	{
2311	if (capture *c = dyn_cast <capture *> (p: o))
2312	{
2313	unsigned where = c->where;
2314	info[where].match_use_count++;
2315	info[where].toplevel_msk |= 1 << toplevel_arg;
2316	info[where].force_no_side_effects_p |= conditional_p;
2317	info[where].cond_expr_cond_p |= cond_expr_cond_p;
2318	if (!info[where].c)
2319	info[where].c = c;
2320	if (!c->what)
2321	return;
2322	/* Recurse to exprs and captures. */
2323	if (is_a <capture *> (p: c->what)
2324	|| is_a <expr *> (p: c->what))
2325	walk_match (o: c->what, toplevel_arg, conditional_p, cond_expr_cond_p: false);
2326	/* We need to look past multiple captures to find a captured
2327	expression as with conditional converts two captures
2328	can be collapsed onto the same expression. Also collect
2329	what captures capture the same thing. */
2330	while (c->what && is_a <capture *> (p: c->what))
2331	{
2332	c = as_a <capture *> (p: c->what);
2333	if (info[c->where].same_as != c->where
2334	&& info[c->where].same_as != info[where].same_as)
2335	fatal_at (loc: c->location, msg: "cannot handle this collapsed capture");
2336	info[c->where].same_as = info[where].same_as;
2337	}
2338	/* Mark expr (non-leaf) captures and forced single-use exprs. */
2339	expr *e;
2340	if (c->what
2341	&& (e = dyn_cast <expr *> (p: c->what)))
2342	{
2343	/* Zero-operand expression captures like ADDR_EXPR@0 are
2344	similar as predicates -- if they are not mentioned in
2345	the result we have to force them to have no side-effects. */
2346	if (e->ops.length () != 0)
2347	info[where].expr_p = true;
2348	info[where].force_single_use |= e->force_single_use;
2349	}
2350	}
2351	else if (expr *e = dyn_cast <expr *> (p: o))
2352	{
2353	for (unsigned i = 0; i < e->ops.length (); ++i)
2354	{
2355	bool cond_p = conditional_p;
2356	bool expr_cond_p = false;
2357	if (i != 0 && *e->operation == COND_EXPR)
2358	cond_p = true;
2359	else if (*e->operation == TRUTH_ANDIF_EXPR
2360	|| *e->operation == TRUTH_ORIF_EXPR)
2361	cond_p = true;
2362	if (i == 0
2363	&& *e->operation == COND_EXPR)
2364	expr_cond_p = true;
2365	walk_match (o: e->ops[i], toplevel_arg, conditional_p: cond_p, cond_expr_cond_p: expr_cond_p);
2366	}
2367	}
2368	else if (is_a <predicate *> (p: o))
2369	{
2370	/* Mark non-captured leafs toplevel arg for checking. */
2371	force_no_side_effects |= 1 << toplevel_arg;
2372	if (verbose >= 1
2373	&& !gimple)
2374	warning_at (loc: o->location,
2375	msg: "forcing no side-effects on possibly lost leaf");
2376	}
2377	else
2378	gcc_unreachable ();
2379	}
2380
2381	/* Analyze captures in the result expression piece O. Return true
2382	if RESULT was visited in one of the children. Only visit
2383	non-if/with children if they are rooted on RESULT. */
2384
2385	bool
2386	capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2387	{
2388	if (capture *c = dyn_cast <capture *> (p: o))
2389	{
2390	unsigned where = info[c->where].same_as;
2391	info[where].result_use_count++;
2392	/* If we substitute an expression capture we don't know
2393	which captures this will end up using (well, we don't
2394	compute that). Force the uses to be side-effect free
2395	which means forcing the toplevels that reach the
2396	expression side-effect free. */
2397	if (info[where].expr_p)
2398	force_no_side_effects |= info[where].toplevel_msk;
2399	/* Mark CSE capture uses as forced to have no side-effects. */
2400	if (c->what
2401	&& is_a <expr *> (p: c->what))
2402	{
2403	info[where].cse_p = true;
2404	walk_result (o: c->what, conditional_p: true, result);
2405	}
2406	}
2407	else if (expr *e = dyn_cast <expr *> (p: o))
2408	{
2409	id_base *opr = e->operation;
2410	if (user_id *uid = dyn_cast <user_id *> (p: opr))
2411	opr = uid->substitutes[0];
2412	for (unsigned i = 0; i < e->ops.length (); ++i)
2413	{
2414	bool cond_p = conditional_p;
2415	if (i != 0 && *e->operation == COND_EXPR)
2416	cond_p = true;
2417	else if (*e->operation == TRUTH_ANDIF_EXPR
2418	|| *e->operation == TRUTH_ORIF_EXPR)
2419	cond_p = true;
2420	walk_result (o: e->ops[i], conditional_p: cond_p, result);
2421	}
2422	}
2423	else if (if_expr *ie = dyn_cast <if_expr *> (p: o))
2424	{
2425	/* 'if' conditions should be all fine. */
2426	if (ie->trueexpr == result)
2427	{
2428	walk_result (o: ie->trueexpr, conditional_p: false, result);
2429	return true;
2430	}
2431	if (ie->falseexpr == result)
2432	{
2433	walk_result (o: ie->falseexpr, conditional_p: false, result);
2434	return true;
2435	}
2436	bool res = false;
2437	if (is_a <if_expr *> (p: ie->trueexpr)
2438	|| is_a <with_expr *> (p: ie->trueexpr))
2439	res |= walk_result (o: ie->trueexpr, conditional_p: false, result);
2440	if (ie->falseexpr
2441	&& (is_a <if_expr *> (p: ie->falseexpr)
2442	|| is_a <with_expr *> (p: ie->falseexpr)))
2443	res |= walk_result (o: ie->falseexpr, conditional_p: false, result);
2444	return res;
2445	}
2446	else if (with_expr *we = dyn_cast <with_expr *> (p: o))
2447	{
2448	bool res = (we->subexpr == result);
2449	if (res
2450	|| is_a <if_expr *> (p: we->subexpr)
2451	|| is_a <with_expr *> (p: we->subexpr))
2452	res |= walk_result (o: we->subexpr, conditional_p: false, result);
2453	if (res)
2454	walk_c_expr (we->with);
2455	return res;
2456	}
2457	else if (c_expr *ce = dyn_cast <c_expr *> (p: o))
2458	walk_c_expr (ce);
2459	else
2460	gcc_unreachable ();
2461
2462	return false;
2463	}
2464
2465	/* Look for captures in the C expr E. */
2466
2467	void
2468	capture_info::walk_c_expr (c_expr *e)
2469	{
2470	/* Give up for C exprs mentioning captures not inside TREE_TYPE,
2471	TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2472	really escape through. */
2473	unsigned p_depth = 0;
2474	for (unsigned i = 0; i < e->code.length (); ++i)
2475	{
2476	const cpp_token *t = &e->code[i];
2477	const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2478	id_base *id;
2479	if (t->type == CPP_NAME
2480	&& (strcmp (s1: (const char *)CPP_HASHNODE
2481	(t->val.node.node)->ident.str, s2: "TREE_TYPE") == 0
2482	|| strcmp (s1: (const char *)CPP_HASHNODE
2483	(t->val.node.node)->ident.str, s2: "TREE_CODE") == 0
2484	|| strcmp (s1: (const char *)CPP_HASHNODE
2485	(t->val.node.node)->ident.str, s2: "TREE_REAL_CST") == 0
2486	|| ((id = get_operator (id: (const char *)CPP_HASHNODE
2487	(t->val.node.node)->ident.str))
2488	&& is_a <predicate_id *> (p: id)))
2489	&& n->type == CPP_OPEN_PAREN)
2490	p_depth++;
2491	else if (t->type == CPP_CLOSE_PAREN
2492	&& p_depth > 0)
2493	p_depth--;
2494	else if (p_depth == 0
2495	&& t->type == CPP_ATSIGN
2496	&& (n->type == CPP_NUMBER
2497	|| n->type == CPP_NAME)
2498	&& !(n->flags & PREV_WHITE))
2499	{
2500	const char *id1;
2501	if (n->type == CPP_NUMBER)
2502	id1 = (const char *)n->val.str.text;
2503	else
2504	id1 = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2505	unsigned *where = e->capture_ids->get(k: id1);
2506	if (! where)
2507	fatal_at (tk: n, msg: "unknown capture id '%s'", id1);
2508	info[info[*where].same_as].force_no_side_effects_p = true;
2509	if (verbose >= 1
2510	&& !gimple)
2511	warning_at (tk: t, msg: "capture escapes");
2512	}
2513	}
2514	}
2515
2516
2517	/* The current label failing the current matched pattern during
2518	code generation. */
2519	static char *fail_label;
2520
2521	/* Code generation off the decision tree and the refered AST nodes. */
2522
2523	bool
2524	is_conversion (id_base *op)
2525	{
2526	return (*op == CONVERT_EXPR
2527	|| *op == NOP_EXPR
2528	|| *op == FLOAT_EXPR
2529	|| *op == FIX_TRUNC_EXPR
2530	|| *op == VIEW_CONVERT_EXPR);
2531	}
2532
2533	/* Get the type to be used for generating operand POS of OP from the
2534	various sources. */
2535
2536	static const char *
2537	get_operand_type (id_base *op, unsigned pos,
2538	const char *in_type,
2539	const char *expr_type,
2540	const char *other_oprnd_type)
2541	{
2542	/* Generally operands whose type does not match the type of the
2543	expression generated need to know their types but match and
2544	thus can fall back to 'other_oprnd_type'. */
2545	if (is_conversion (op))
2546	return other_oprnd_type;
2547	else if (*op == REALPART_EXPR
2548	|| *op == IMAGPART_EXPR)
2549	return other_oprnd_type;
2550	else if (is_a <operator_id *> (p: op)
2551	&& strcmp (s1: as_a <operator_id *> (p: op)->tcc, s2: "tcc_comparison") == 0)
2552	return other_oprnd_type;
2553	else if (*op == COND_EXPR
2554	&& pos == 0)
2555	return "boolean_type_node";
2556	else if (startswith (str: op->id, prefix: "CFN_COND_"))
2557	{
2558	/* IFN_COND_* operands 1 and later by default have the same type
2559	as the result. The type of operand 0 needs to be specified
2560	explicitly. */
2561	if (pos > 0 && expr_type)
2562	return expr_type;
2563	else if (pos > 0 && in_type)
2564	return in_type;
2565	else
2566	return NULL;
2567	}
2568	else
2569	{
2570	/* Otherwise all types should match - choose one in order of
2571	preference. */
2572	if (expr_type)
2573	return expr_type;
2574	else if (in_type)
2575	return in_type;
2576	else
2577	return other_oprnd_type;
2578	}
2579	}
2580
2581	/* Generate transform code for an expression. */
2582
2583	void
2584	expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2585	int depth, const char *in_type, capture_info *cinfo,
2586	dt_operand **indexes, int)
2587	{
2588	id_base *opr = operation;
2589	/* When we delay operator substituting during lowering of fors we
2590	make sure that for code-gen purposes the effects of each substitute
2591	are the same. Thus just look at that. */
2592	if (user_id *uid = dyn_cast <user_id *> (p: opr))
2593	opr = uid->substitutes[0];
2594
2595	bool conversion_p = is_conversion (op: opr);
2596	const char *type = expr_type;
2597	char optype[64];
2598	if (type)
2599	/* If there was a type specification in the pattern use it. */
2600	;
2601	else if (conversion_p)
2602	/* For conversions we need to build the expression using the
2603	outer type passed in. */
2604	type = in_type;
2605	else if (*opr == REALPART_EXPR
2606	|| *opr == IMAGPART_EXPR)
2607	{
2608	/* __real and __imag use the component type of its operand. */
2609	snprintf (s: optype, maxlen: sizeof (optype), format: "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2610	depth);
2611	type = optype;
2612	}
2613	else if (is_a <operator_id *> (p: opr)
2614	&& !strcmp (s1: as_a <operator_id *> (p: opr)->tcc, s2: "tcc_comparison"))
2615	{
2616	/* comparisons use boolean_type_node (or what gets in), but
2617	their operands need to figure out the types themselves. */
2618	if (in_type)
2619	type = in_type;
2620	else
2621	{
2622	snprintf (s: optype, maxlen: sizeof (optype), format: "boolean_type_node");
2623	type = optype;
2624	}
2625	in_type = NULL;
2626	}
2627	else if (*opr == COND_EXPR
2628	|| *opr == VEC_COND_EXPR
2629	|| startswith (str: opr->id, prefix: "CFN_COND_"))
2630	{
2631	/* Conditions are of the same type as their first alternative. */
2632	snprintf (s: optype, maxlen: sizeof (optype), format: "TREE_TYPE (_o%d[1])", depth);
2633	type = optype;
2634	}
2635	else
2636	{
2637	/* Other operations are of the same type as their first operand. */
2638	snprintf (s: optype, maxlen: sizeof (optype), format: "TREE_TYPE (_o%d[0])", depth);
2639	type = optype;
2640	}
2641	if (!type)
2642	fatal_at (loc: location, msg: "cannot determine type of operand");
2643
2644	fprintf_indent (f, indent, format: "{\n");
2645	indent += 2;
2646	fprintf_indent (f, indent,
2647	format: "tree _o%d[%u], _r%d;\n", depth, ops.length (), depth);
2648	char op0type[64];
2649	snprintf (s: op0type, maxlen: sizeof (op0type), format: "TREE_TYPE (_o%d[0])", depth);
2650	for (unsigned i = 0; i < ops.length (); ++i)
2651	{
2652	char dest1[32];
2653	snprintf (s: dest1, maxlen: sizeof (dest1), format: "_o%d[%u]", depth, i);
2654	const char *optype1
2655	= get_operand_type (op: opr, pos: i, in_type, expr_type,
2656	other_oprnd_type: i == 0 ? NULL : op0type);
2657	ops[i]->gen_transform (f, indent, dest1, gimple, depth + 1, optype1,
2658	cinfo, indexes,
2659	*opr == COND_EXPR && i == 0 ? 1 : 2);
2660	}
2661
2662	const char *opr_name;
2663	if (*operation == CONVERT_EXPR)
2664	opr_name = "NOP_EXPR";
2665	else
2666	opr_name = operation->id;
2667
2668	if (gimple)
2669	{
2670	if (*opr == CONVERT_EXPR)
2671	{
2672	fprintf_indent (f, indent,
2673	format: "if (%s != TREE_TYPE (_o%d[0])\n",
2674	type, depth);
2675	fprintf_indent (f, indent,
2676	format: " && !useless_type_conversion_p (%s, TREE_TYPE "
2677	"(_o%d[0])))\n",
2678	type, depth);
2679	fprintf_indent (f, indent: indent + 2, format: "{\n");
2680	indent += 4;
2681	}
2682	/* ??? Building a stmt can fail for various reasons here, seq being
2683	NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2684	So if we fail here we should continue matching other patterns. */
2685	fprintf_indent (f, indent, format: "gimple_match_op tem_op "
2686	"(res_op->cond.any_else (), %s, %s", opr_name, type);
2687	for (unsigned i = 0; i < ops.length (); ++i)
2688	fprintf (stream: f, format: ", _o%d[%u]", depth, i);
2689	fprintf (stream: f, format: ");\n");
2690	fprintf_indent (f, indent, format: "tem_op.resimplify (%s, valueize);\n",
2691	!force_leaf ? "lseq" : "NULL");
2692	fprintf_indent (f, indent,
2693	format: "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth,
2694	!force_leaf ? "lseq" : "NULL");
2695	fprintf_indent (f, indent,
2696	format: "if (!_r%d) goto %s;\n",
2697	depth, fail_label);
2698	if (*opr == CONVERT_EXPR)
2699	{
2700	indent -= 4;
2701	fprintf_indent (f, indent, format: " }\n");
2702	fprintf_indent (f, indent, format: "else\n");
2703	fprintf_indent (f, indent, format: " _r%d = _o%d[0];\n", depth, depth);
2704	}
2705	}
2706	else
2707	{
2708	if (*opr == CONVERT_EXPR)
2709	{
2710	fprintf_indent (f, indent, format: "if (TREE_TYPE (_o%d[0]) != %s)\n",
2711	depth, type);
2712	fprintf_indent (f, indent: indent + 2, format: "{\n");
2713	indent += 4;
2714	}
2715	if (opr->kind == id_base::CODE)
2716	fprintf_indent (f, indent, format: "_r%d = fold_build%d_loc (loc, %s, %s",
2717	depth, ops.length(), opr_name, type);
2718	else
2719	fprintf_indent (f, indent, format: "_r%d = maybe_build_call_expr_loc (loc, "
2720	"%s, %s, %d", depth, opr_name, type, ops.length());
2721	for (unsigned i = 0; i < ops.length (); ++i)
2722	fprintf (stream: f, format: ", _o%d[%u]", depth, i);
2723	fprintf (stream: f, format: ");\n");
2724	if (opr->kind != id_base::CODE)
2725	{
2726	fprintf_indent (f, indent, format: "if (!_r%d)\n", depth);
2727	fprintf_indent (f, indent, format: " goto %s;\n", fail_label);
2728	}
2729	if (force_leaf)
2730	{
2731	fprintf_indent (f, indent, format: "if (EXPR_P (_r%d))\n", depth);
2732	fprintf_indent (f, indent, format: " goto %s;\n", fail_label);
2733	}
2734	if (*opr == CONVERT_EXPR)
2735	{
2736	fprintf_indent (f, indent: indent - 2, format: "}\n");
2737	indent -= 4;
2738	fprintf_indent (f, indent, format: "else\n");
2739	fprintf_indent (f, indent, format: " _r%d = _o%d[0];\n", depth, depth);
2740	}
2741	}
2742	fprintf_indent (f, indent, format: "%s = _r%d;\n", dest, depth);
2743	indent -= 2;
2744	fprintf_indent (f, indent, format: "}\n");
2745	}
2746
2747	/* Generate code for a c_expr which is either the expression inside
2748	an if statement or a sequence of statements which computes a
2749	result to be stored to DEST. */
2750
2751	void
2752	c_expr::gen_transform (FILE *f, int indent, const char *dest,
2753	bool, int, const char *, capture_info *,
2754	dt_operand **, int)
2755	{
2756	if (dest && nr_stmts == 1)
2757	fprintf_indent (f, indent, format: "%s = ", dest);
2758
2759	unsigned stmt_nr = 1;
2760	int prev_line = -1;
2761	for (unsigned i = 0; i < code.length (); ++i)
2762	{
2763	const cpp_token *token = &code[i];
2764
2765	/* We can't recover from all lexing losses but we can roughly restore line
2766	breaks from location info. */
2767	const line_map_ordinary *map;
2768	linemap_resolve_location (line_table, loc: token->src_loc,
2769	lrk: LRK_SPELLING_LOCATION, loc_map: &map);
2770	expanded_location loc = linemap_expand_location (line_table, map,
2771	loc: token->src_loc);
2772	if (prev_line != -1 && loc.line != prev_line)
2773	fputc ('\n', f);
2774	prev_line = loc.line;
2775
2776	/* Replace captures for code-gen. */
2777	if (token->type == CPP_ATSIGN)
2778	{
2779	const cpp_token *n = &code[i+1];
2780	if ((n->type == CPP_NUMBER
2781	|| n->type == CPP_NAME)
2782	&& !(n->flags & PREV_WHITE))
2783	{
2784	if (token->flags & PREV_WHITE)
2785	fputc (' ', f);
2786	const char *id;
2787	if (n->type == CPP_NUMBER)
2788	id = (const char *)n->val.str.text;
2789	else
2790	id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2791	unsigned *cid = capture_ids->get (k: id);
2792	if (!cid)
2793	fatal_at (tk: token, msg: "unknown capture id");
2794	fprintf (stream: f, format: "captures[%u]", *cid);
2795	++i;
2796	continue;
2797	}
2798	}
2799
2800	if (token->flags & PREV_WHITE)
2801	fputc (' ', f);
2802
2803	if (token->type == CPP_NAME)
2804	{
2805	const char *id = (const char *) NODE_NAME (token->val.node.node);
2806	unsigned j;
2807	for (j = 0; j < ids.length (); ++j)
2808	{
2809	if (strcmp (s1: id, s2: ids[j].id) == 0)
2810	{
2811	fprintf (stream: f, format: "%s", ids[j].oper);
2812	break;
2813	}
2814	}
2815	if (j < ids.length ())
2816	continue;
2817	}
2818
2819	/* Output the token as string. */
2820	char *tk = (char *)cpp_token_as_text (r, token);
2821	fputs (tk, f);
2822
2823	if (token->type == CPP_SEMICOLON)
2824	{
2825	stmt_nr++;
2826	if (dest && stmt_nr == nr_stmts)
2827	fprintf_indent (f, indent, format: "%s = ", dest);
2828	}
2829	}
2830	fputc ('\n', f);
2831	}
2832
2833	/* Generate transform code for a capture. */
2834
2835	void
2836	capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2837	int depth, const char *in_type, capture_info *cinfo,
2838	dt_operand **indexes, int cond_handling)
2839	{
2840	if (what && is_a<expr *> (p: what))
2841	{
2842	if (indexes[where] == 0)
2843	{
2844	char buf[20];
2845	snprintf (s: buf, maxlen: sizeof (buf), format: "captures[%u]", where);
2846	what->gen_transform (f, indent, buf, gimple, depth, in_type,
2847	cinfo, NULL);
2848	}
2849	}
2850
2851	/* If in GENERIC some capture is used multiple times, unshare it except
2852	when emitting the last use. */
2853	if (!gimple
2854	&& cinfo->info.exists ()
2855	&& cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
2856	{
2857	fprintf_indent (f, indent, format: "%s = unshare_expr (captures[%u]);\n",
2858	dest, where);
2859	cinfo->info[cinfo->info[where].same_as].result_use_count--;
2860	}
2861	else
2862	fprintf_indent (f, indent, format: "%s = captures[%u];\n", dest, where);
2863
2864	/* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2865	with substituting a capture of that. */
2866	if (gimple
2867	&& cond_handling != 0
2868	&& cinfo->info[where].cond_expr_cond_p)
2869	{
2870	/* If substituting into a cond_expr condition, unshare. */
2871	if (cond_handling == 1)
2872	fprintf_indent (f, indent, format: "%s = unshare_expr (%s);\n", dest, dest);
2873	/* If substituting elsewhere we might need to decompose it. */
2874	else if (cond_handling == 2)
2875	{
2876	/* ??? Returning false here will also not allow any other patterns
2877	to match unless this generator was split out. */
2878	fprintf_indent (f, indent, format: "if (COMPARISON_CLASS_P (%s))\n", dest);
2879	fprintf_indent (f, indent, format: " {\n");
2880	fprintf_indent (f, indent, format: " if (!seq) return false;\n");
2881	fprintf_indent (f, indent, format: " %s = gimple_build (seq,"
2882	" TREE_CODE (%s),"
2883	" TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2884	" TREE_OPERAND (%s, 1));\n",
2885	dest, dest, dest, dest, dest);
2886	fprintf_indent (f, indent, format: " }\n");
2887	}
2888	}
2889	}
2890
2891	/* Return the name of the operand representing the decision tree node.
2892	Use NAME as space to generate it. */
2893
2894	char *
2895	dt_operand::get_name (char *name)
2896	{
2897	if (! parent)
2898	sprintf (s: name, format: "t");
2899	else if (parent->level == 1)
2900	sprintf (s: name, format: "_p%u", pos);
2901	else if (parent->type == dt_node::DT_MATCH)
2902	return as_a <dt_operand *> (p: parent)->get_name (name);
2903	else
2904	sprintf (s: name, format: "_q%u%u", parent->level, pos);
2905	return name;
2906	}
2907
2908	/* Fill NAME with the operand name at position POS. */
2909
2910	void
2911	dt_operand::gen_opname (char *name, unsigned pos)
2912	{
2913	if (! parent)
2914	sprintf (s: name, format: "_p%u", pos);
2915	else
2916	sprintf (s: name, format: "_q%u%u", level, pos);
2917	}
2918
2919	/* Generate matching code for the decision tree operand which is
2920	a predicate. */
2921
2922	unsigned
2923	dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2924	{
2925	predicate *p = as_a <predicate *> (p: op);
2926
2927	if (p->p->matchers.exists ())
2928	{
2929	/* If this is a predicate generated from a pattern mangle its
2930	name and pass on the valueize hook. */
2931	if (gimple)
2932	fprintf_indent (f, indent, format: "if (gimple_%s (%s, valueize))\n",
2933	p->p->id, opname);
2934	else
2935	fprintf_indent (f, indent, format: "if (tree_%s (%s))\n", p->p->id, opname);
2936	}
2937	else
2938	fprintf_indent (f, indent, format: "if (%s (%s))\n", p->p->id, opname);
2939	fprintf_indent (f, indent: indent + 2, format: "{\n");
2940	return 1;
2941	}
2942
2943	/* Generate matching code for the decision tree operand which is
2944	a capture-match. */
2945
2946	unsigned
2947	dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
2948	{
2949	char match_opname[20];
2950	match_dop->get_name (name: match_opname);
2951	if (value_match)
2952	fprintf_indent (f, indent, format: "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2953	"|| operand_equal_p (%s, %s, 0))\n",
2954	opname, match_opname, opname, opname, match_opname);
2955	else
2956	fprintf_indent (f, indent, format: "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2957	"|| (operand_equal_p (%s, %s, 0) "
2958	"&& types_match (%s, %s)))\n",
2959	opname, match_opname, opname, opname, match_opname,
2960	opname, match_opname);
2961	fprintf_indent (f, indent: indent + 2, format: "{\n");
2962	return 1;
2963	}
2964
2965	/* Generate GIMPLE matching code for the decision tree operand. */
2966
2967	unsigned
2968	dt_operand::gen_gimple_expr (FILE *f, int indent, int depth)
2969	{
2970	expr *e = static_cast<expr *> (op);
2971	id_base *id = e->operation;
2972	unsigned n_ops = e->ops.length ();
2973	unsigned n_braces = 0;
2974
2975	if (user_id *u = dyn_cast <user_id *> (p: id))
2976	id = u->substitutes[0];
2977
2978	for (unsigned i = 0; i < n_ops; ++i)
2979	{
2980	char child_opname[20];
2981	gen_opname (name: child_opname, pos: i);
2982
2983	if (id->kind == id_base::CODE)
2984	{
2985	if (e->is_generic
2986	|| *id == REALPART_EXPR || *id == IMAGPART_EXPR
2987	|| *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2988	{
2989	/* ??? If this is a memory operation we can't (and should not)
2990	match this. The only sensible operand types are
2991	SSA names and invariants. */
2992	if (e->is_generic)
2993	{
2994	char opname[20];
2995	get_name (name: opname);
2996	fprintf_indent (f, indent,
2997	format: "tree %s = TREE_OPERAND (%s, %i);\n",
2998	child_opname, opname, i);
2999	}
3000	else
3001	fprintf_indent (f, indent,
3002	format: "tree %s = TREE_OPERAND "
3003	"(gimple_assign_rhs1 (_a%d), %i);\n",
3004	child_opname, depth, i);
3005	fprintf_indent (f, indent,
3006	format: "if ((TREE_CODE (%s) == SSA_NAME\n",
3007	child_opname);
3008	fprintf_indent (f, indent,
3009	format: " || is_gimple_min_invariant (%s)))\n",
3010	child_opname);
3011	fprintf_indent (f, indent,
3012	format: " {\n");
3013	indent += 4;
3014	n_braces++;
3015	fprintf_indent (f, indent,
3016	format: "%s = do_valueize (valueize, %s);\n",
3017	child_opname, child_opname);
3018	continue;
3019	}
3020	else
3021	fprintf_indent (f, indent,
3022	format: "tree %s = gimple_assign_rhs%u (_a%d);\n",
3023	child_opname, i + 1, depth);
3024	}
3025	else
3026	fprintf_indent (f, indent,
3027	format: "tree %s = gimple_call_arg (_c%d, %u);\n",
3028	child_opname, depth, i);
3029	fprintf_indent (f, indent,
3030	format: "%s = do_valueize (valueize, %s);\n",
3031	child_opname, child_opname);
3032	}
3033	/* While the toplevel operands are canonicalized by the caller
3034	after valueizing operands of sub-expressions we have to
3035	re-canonicalize operand order. */
3036	int opno = commutative_op (id);
3037	if (opno >= 0)
3038	{
3039	char child_opname0[20], child_opname1[20];
3040	gen_opname (name: child_opname0, pos: opno);
3041	gen_opname (name: child_opname1, pos: opno + 1);
3042	fprintf_indent (f, indent,
3043	format: "if (tree_swap_operands_p (%s, %s))\n",
3044	child_opname0, child_opname1);
3045	fprintf_indent (f, indent,
3046	format: " std::swap (%s, %s);\n",
3047	child_opname0, child_opname1);
3048	}
3049
3050	return n_braces;
3051	}
3052
3053	/* Generate GENERIC matching code for the decision tree operand. */
3054
3055	unsigned
3056	dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
3057	{
3058	expr *e = static_cast<expr *> (op);
3059	id_base *id = e->operation;
3060	unsigned n_ops = e->ops.length ();
3061
3062	if (user_id *u = dyn_cast <user_id *> (p: id))
3063	id = u->substitutes[0];
3064
3065	for (unsigned i = 0; i < n_ops; ++i)
3066	{
3067	char child_opname[20];
3068	gen_opname (name: child_opname, pos: i);
3069
3070	if (id->kind == id_base::CODE)
3071	fprintf_indent (f, indent, format: "tree %s = TREE_OPERAND (%s, %u);\n",
3072	child_opname, opname, i);
3073	else
3074	fprintf_indent (f, indent, format: "tree %s = CALL_EXPR_ARG (%s, %u);\n",
3075	child_opname, opname, i);
3076	}
3077
3078	return 0;
3079	}
3080
3081	/* Compare 2 fns or generic_fns vector entries for vector sorting.
3082	Same operation entries with different number of arguments should
3083	be adjacent. */
3084
3085	static int
3086	fns_cmp (const void *p1, const void *p2)
3087	{
3088	dt_operand *op1 = *(dt_operand *const *) p1;
3089	dt_operand *op2 = *(dt_operand *const *) p2;
3090	expr *e1 = as_a <expr *> (p: op1->op);
3091	expr *e2 = as_a <expr *> (p: op2->op);
3092	id_base *b1 = e1->operation;
3093	id_base *b2 = e2->operation;
3094	if (b1->hashval < b2->hashval)
3095	return -1;
3096	if (b1->hashval > b2->hashval)
3097	return 1;
3098	return strcmp (s1: b1->id, s2: b2->id);
3099	}
3100
3101	/* Generate matching code for the children of the decision tree node. */
3102
3103	void
3104	dt_node::gen_kids (FILE *f, int indent, bool gimple, int depth)
3105	{
3106	auto_vec<dt_operand *> gimple_exprs;
3107	auto_vec<dt_operand *> generic_exprs;
3108	auto_vec<dt_operand *> fns;
3109	auto_vec<dt_operand *> generic_fns;
3110	auto_vec<dt_operand *> preds;
3111	auto_vec<dt_node *> others;
3112
3113	for (unsigned i = 0; i < kids.length (); ++i)
3114	{
3115	if (kids[i]->type == dt_node::DT_OPERAND)
3116	{
3117	dt_operand *op = as_a<dt_operand *> (p: kids[i]);
3118	if (expr *e = dyn_cast <expr *> (p: op->op))
3119	{
3120	if (e->ops.length () == 0
3121	/* In GIMPLE a CONSTRUCTOR always appears in a
3122	separate definition. */
3123	&& (!gimple || !(*e->operation == CONSTRUCTOR)))
3124	{
3125	generic_exprs.safe_push (obj: op);
3126	/* But ADDR_EXPRs can appear directly when invariant
3127	and in a separate definition when not. */
3128	if (gimple && *e->operation == ADDR_EXPR)
3129	gimple_exprs.safe_push (obj: op);
3130	}
3131	else if (e->operation->kind == id_base::FN)
3132	{
3133	if (gimple)
3134	fns.safe_push (obj: op);
3135	else
3136	generic_fns.safe_push (obj: op);
3137	}
3138	else if (e->operation->kind == id_base::PREDICATE)
3139	preds.safe_push (obj: op);
3140	else
3141	{
3142	user_id *u = dyn_cast <user_id *> (p: e->operation);
3143	if (u && u->substitutes[0]->kind == id_base::FN)
3144	{
3145	if (gimple)
3146	fns.safe_push (obj: op);
3147	else
3148	generic_fns.safe_push (obj: op);
3149	}
3150	else
3151	{
3152	if (gimple && !e->is_generic)
3153	gimple_exprs.safe_push (obj: op);
3154	else
3155	generic_exprs.safe_push (obj: op);
3156	}
3157	}
3158	}
3159	else if (op->op->type == operand::OP_PREDICATE)
3160	others.safe_push (obj: kids[i]);
3161	else
3162	gcc_unreachable ();
3163	}
3164	else if (kids[i]->type == dt_node::DT_SIMPLIFY)
3165	others.safe_push (obj: kids[i]);
3166	else if (kids[i]->type == dt_node::DT_MATCH
3167	|| kids[i]->type == dt_node::DT_TRUE)
3168	{
3169	/* A DT_TRUE operand serves as a barrier - generate code now
3170	for what we have collected sofar.
3171	Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3172	dependent matches to get out-of-order. Generate code now
3173	for what we have collected sofar. */
3174	fns.qsort (fns_cmp);
3175	generic_fns.qsort (fns_cmp);
3176	gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
3177	fns, generic_fns, preds, others);
3178	/* And output the true operand itself. */
3179	kids[i]->gen (f, indent, gimple, depth);
3180	gimple_exprs.truncate (size: 0);
3181	generic_exprs.truncate (size: 0);
3182	fns.truncate (size: 0);
3183	generic_fns.truncate (size: 0);
3184	preds.truncate (size: 0);
3185	others.truncate (size: 0);
3186	}
3187	else
3188	gcc_unreachable ();
3189	}
3190
3191	/* Generate code for the remains. */
3192	fns.qsort (fns_cmp);
3193	generic_fns.qsort (fns_cmp);
3194	gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
3195	fns, generic_fns, preds, others);
3196	}
3197
3198	/* Generate matching code for the children of the decision tree node. */
3199
3200	void
3201	dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, int depth,
3202	const vec<dt_operand *> &gimple_exprs,
3203	const vec<dt_operand *> &generic_exprs,
3204	const vec<dt_operand *> &fns,
3205	const vec<dt_operand *> &generic_fns,
3206	const vec<dt_operand *> &preds,
3207	const vec<dt_node *> &others)
3208	{
3209	char buf[128];
3210	char *kid_opname = buf;
3211
3212	unsigned exprs_len = gimple_exprs.length ();
3213	unsigned gexprs_len = generic_exprs.length ();
3214	unsigned fns_len = fns.length ();
3215	unsigned gfns_len = generic_fns.length ();
3216
3217	if (exprs_len || fns_len || gexprs_len || gfns_len)
3218	{
3219	if (exprs_len)
3220	gimple_exprs[0]->get_name (name: kid_opname);
3221	else if (fns_len)
3222	fns[0]->get_name (name: kid_opname);
3223	else if (gfns_len)
3224	generic_fns[0]->get_name (name: kid_opname);
3225	else
3226	generic_exprs[0]->get_name (name: kid_opname);
3227
3228	fprintf_indent (f, indent, format: "switch (TREE_CODE (%s))\n", kid_opname);
3229	fprintf_indent (f, indent, format: " {\n");
3230	indent += 2;
3231	}
3232
3233	if (exprs_len || fns_len)
3234	{
3235	depth++;
3236	fprintf_indent (f, indent,
3237	format: "case SSA_NAME:\n");
3238	fprintf_indent (f, indent,
3239	format: " if (gimple *_d%d = get_def (valueize, %s))\n",
3240	depth, kid_opname);
3241	fprintf_indent (f, indent,
3242	format: " {\n");
3243	indent += 6;
3244	if (exprs_len)
3245	{
3246	fprintf_indent (f, indent,
3247	format: "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3248	depth, depth);
3249	fprintf_indent (f, indent,
3250	format: " switch (gimple_assign_rhs_code (_a%d))\n",
3251	depth);
3252	indent += 4;
3253	fprintf_indent (f, indent, format: "{\n");
3254	for (unsigned i = 0; i < exprs_len; ++i)
3255	{
3256	expr *e = as_a <expr *> (p: gimple_exprs[i]->op);
3257	if (user_id *u = dyn_cast <user_id *> (p: e->operation))
3258	{
3259	for (auto id : u->substitutes)
3260	fprintf_indent (f, indent, format: "case %s:\n", id->id);
3261	}
3262	else
3263	{
3264	id_base *op = e->operation;
3265	if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3266	fprintf_indent (f, indent, format: "CASE_CONVERT:\n");
3267	else
3268	fprintf_indent (f, indent, format: "case %s:\n", op->id);
3269	}
3270	fprintf_indent (f, indent, format: " {\n");
3271	gimple_exprs[i]->gen (f, indent + 4, true, depth);
3272	fprintf_indent (f, indent, format: " break;\n");
3273	fprintf_indent (f, indent, format: " }\n");
3274	}
3275	fprintf_indent (f, indent, format: "default:;\n");
3276	fprintf_indent (f, indent, format: "}\n");
3277	indent -= 4;
3278	}
3279
3280	if (fns_len)
3281	{
3282	fprintf_indent (f, indent,
3283	format: "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3284	exprs_len ? "else " : "", depth, depth);
3285	fprintf_indent (f, indent,
3286	format: " switch (gimple_call_combined_fn (_c%d))\n",
3287	depth);
3288
3289	indent += 4;
3290	fprintf_indent (f, indent, format: "{\n");
3291	id_base *last_op = NULL;
3292	for (unsigned i = 0; i < fns_len; ++i)
3293	{
3294	expr *e = as_a <expr *>(p: fns[i]->op);
3295	if (e->operation != last_op)
3296	{
3297	if (i)
3298	fprintf_indent (f, indent, format: " break;\n");
3299	if (user_id *u = dyn_cast <user_id *> (p: e->operation))
3300	for (auto id : u->substitutes)
3301	fprintf_indent (f, indent, format: "case %s:\n", id->id);
3302	else
3303	fprintf_indent (f, indent, format: "case %s:\n", e->operation->id);
3304	}
3305	last_op = e->operation;
3306	/* We need to be defensive against bogus prototypes allowing
3307	calls with not enough arguments. */
3308	fprintf_indent (f, indent,
3309	format: " if (gimple_call_num_args (_c%d) == %d)\n",
3310	depth, e->ops.length ());
3311	fprintf_indent (f, indent, format: " {\n");
3312	fns[i]->gen (f, indent + 6, true, depth);
3313	fprintf_indent (f, indent, format: " }\n");
3314	}
3315
3316	fprintf_indent (f, indent, format: " break;\n");
3317	fprintf_indent (f, indent, format: "default:;\n");
3318	fprintf_indent (f, indent, format: "}\n");
3319	indent -= 4;
3320	}
3321
3322	indent -= 6;
3323	depth--;
3324	fprintf_indent (f, indent, format: " }\n");
3325	/* See if there is SSA_NAME among generic_exprs and if yes, emit it
3326	here rather than in the next loop. */
3327	for (unsigned i = 0; i < generic_exprs.length (); ++i)
3328	{
3329	expr *e = as_a <expr *>(p: generic_exprs[i]->op);
3330	id_base *op = e->operation;
3331	if (*op == SSA_NAME && (exprs_len || fns_len))
3332	{
3333	fprintf_indent (f, indent: indent + 4, format: "{\n");
3334	generic_exprs[i]->gen (f, indent + 6, gimple, depth);
3335	fprintf_indent (f, indent: indent + 4, format: "}\n");
3336	}
3337	}
3338
3339	fprintf_indent (f, indent, format: " break;\n");
3340	}
3341
3342	for (unsigned i = 0; i < generic_exprs.length (); ++i)
3343	{
3344	expr *e = as_a <expr *>(p: generic_exprs[i]->op);
3345	id_base *op = e->operation;
3346	if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3347	fprintf_indent (f, indent, format: "CASE_CONVERT:\n");
3348	else if (*op == SSA_NAME && (exprs_len || fns_len))
3349	/* Already handled above. */
3350	continue;
3351	else
3352	{
3353	if (user_id *u = dyn_cast <user_id *> (p: op))
3354	for (auto id : u->substitutes)
3355	fprintf_indent (f, indent, format: "case %s:\n", id->id);
3356	else
3357	fprintf_indent (f, indent, format: "case %s:\n", op->id);
3358	}
3359	fprintf_indent (f, indent, format: " {\n");
3360	generic_exprs[i]->gen (f, indent + 4, gimple, depth);
3361	fprintf_indent (f, indent, format: " break;\n");
3362	fprintf_indent (f, indent, format: " }\n");
3363	}
3364
3365	if (gfns_len)
3366	{
3367	fprintf_indent (f, indent,
3368	format: "case CALL_EXPR:\n");
3369	fprintf_indent (f, indent,
3370	format: " switch (get_call_combined_fn (%s))\n",
3371	kid_opname);
3372	fprintf_indent (f, indent,
3373	format: " {\n");
3374	indent += 4;
3375
3376	id_base *last_op = NULL;
3377	for (unsigned j = 0; j < generic_fns.length (); ++j)
3378	{
3379	expr *e = as_a <expr *>(p: generic_fns[j]->op);
3380	gcc_assert (e->operation->kind == id_base::FN);
3381
3382	if (e->operation != last_op)
3383	{
3384	if (j)
3385	fprintf_indent (f, indent, format: " break;\n");
3386	fprintf_indent (f, indent, format: "case %s:\n", e->operation->id);
3387	}
3388	last_op = e->operation;
3389	fprintf_indent (f, indent, format: " if (call_expr_nargs (%s) == %d)\n"
3390	" {\n", kid_opname, e->ops.length ());
3391	generic_fns[j]->gen (f, indent + 6, false, depth);
3392	fprintf_indent (f, indent, format: " }\n");
3393	}
3394	fprintf_indent (f, indent, format: " break;\n");
3395	fprintf_indent (f, indent, format: "default:;\n");
3396
3397	indent -= 4;
3398	fprintf_indent (f, indent, format: " }\n");
3399	fprintf_indent (f, indent, format: " break;\n");
3400	}
3401
3402	/* Close switch (TREE_CODE ()). */
3403	if (exprs_len || fns_len || gexprs_len || gfns_len)
3404	{
3405	indent -= 4;
3406	fprintf_indent (f, indent, format: " default:;\n");
3407	fprintf_indent (f, indent, format: " }\n");
3408	}
3409
3410	for (unsigned i = 0; i < preds.length (); ++i)
3411	{
3412	expr *e = as_a <expr *> (p: preds[i]->op);
3413	predicate_id *p = as_a <predicate_id *> (p: e->operation);
3414	preds[i]->get_name (name: kid_opname);
3415	fprintf_indent (f, indent, format: "{\n");
3416	indent += 2;
3417	fprintf_indent (f, indent, format: "tree %s_pops[%d];\n", kid_opname, p->nargs);
3418	fprintf_indent (f, indent, format: "if (%s_%s (%s, %s_pops%s))\n",
3419	gimple ? "gimple" : "tree",
3420	p->id, kid_opname, kid_opname,
3421	gimple ? ", valueize" : "");
3422	fprintf_indent (f, indent, format: " {\n");
3423	for (int j = 0; j < p->nargs; ++j)
3424	{
3425	char child_opname[20];
3426	preds[i]->gen_opname (name: child_opname, pos: j);
3427	fprintf_indent (f, indent: indent + 4, format: "tree %s = %s_pops[%d];\n",
3428	child_opname, kid_opname, j);
3429	}
3430	preds[i]->gen_kids (f, indent: indent + 4, gimple, depth);
3431	fprintf (stream: f, format: "}\n");
3432	indent -= 2;
3433	fprintf_indent (f, indent, format: "}\n");
3434	}
3435
3436	for (unsigned i = 0; i < others.length (); ++i)
3437	others[i]->gen (f, indent, gimple, depth);
3438	}
3439
3440	/* Generate matching code for the decision tree operand. */
3441
3442	void
3443	dt_operand::gen (FILE *f, int indent, bool gimple, int depth)
3444	{
3445	char opname[20];
3446	get_name (name: opname);
3447
3448	unsigned n_braces = 0;
3449
3450	if (type == DT_OPERAND)
3451	switch (op->type)
3452	{
3453	case operand::OP_PREDICATE:
3454	n_braces = gen_predicate (f, indent, opname, gimple);
3455	break;
3456
3457	case operand::OP_EXPR:
3458	if (gimple)
3459	n_braces = gen_gimple_expr (f, indent, depth);
3460	else
3461	n_braces = gen_generic_expr (f, indent, opname);
3462	break;
3463
3464	default:
3465	gcc_unreachable ();
3466	}
3467	else if (type == DT_TRUE)
3468	;
3469	else if (type == DT_MATCH)
3470	n_braces = gen_match_op (f, indent, opname, gimple);
3471	else
3472	gcc_unreachable ();
3473
3474	indent += 4 * n_braces;
3475	gen_kids (f, indent, gimple, depth);
3476
3477	for (unsigned i = 0; i < n_braces; ++i)
3478	{
3479	indent -= 4;
3480	if (indent < 0)
3481	indent = 0;
3482	fprintf_indent (f, indent, format: " }\n");
3483	}
3484	}
3485
3486	/* Emit a logging call to the debug file to the file F, with the INDENT from
3487	either the RESULT location or the S's match location if RESULT is null. */
3488	static void
3489	emit_logging_call (FILE *f, int indent, class simplify *s, operand *result,
3490	bool gimple)
3491	{
3492	fprintf_indent (f, indent, format: "if (UNLIKELY (debug_dump)) "
3493	"%s_dump_logs (", gimple ? "gimple" : "generic");
3494	output_line_directive (f,
3495	location: result ? result->location : s->match->location,
3496	dumpfile: true, fnargs: true, indirect_line_numbers: true);
3497	fprintf (stream: f, format: ", __FILE__, __LINE__, %s);\n",
3498	s->kind == simplify::SIMPLIFY ? "true" : "false");
3499	}
3500
3501	/* Generate code for the '(if ...)', '(with ..)' and actual transform
3502	step of a '(simplify ...)' or '(match ...)'. This handles everything
3503	that is not part of the decision tree (simplify->match).
3504	Main recursive worker. */
3505
3506	void
3507	dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3508	{
3509	if (result)
3510	{
3511	if (with_expr *w = dyn_cast <with_expr *> (p: result))
3512	{
3513	fprintf_indent (f, indent, format: "{\n");
3514	indent += 4;
3515	output_line_directive (f, location: w->location);
3516	w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3517	gen_1 (f, indent, gimple, result: w->subexpr);
3518	indent -= 4;
3519	fprintf_indent (f, indent, format: "}\n");
3520	return;
3521	}
3522	else if (if_expr *ife = dyn_cast <if_expr *> (p: result))
3523	{
3524	output_line_directive (f, location: ife->location);
3525	fprintf_indent (f, indent, format: "if (");
3526	ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3527	fprintf (stream: f, format: ")\n");
3528	fprintf_indent (f, indent: indent + 2, format: "{\n");
3529	indent += 4;
3530	gen_1 (f, indent, gimple, result: ife->trueexpr);
3531	indent -= 4;
3532	fprintf_indent (f, indent: indent + 2, format: "}\n");
3533	if (ife->falseexpr)
3534	{
3535	fprintf_indent (f, indent, format: "else\n");
3536	fprintf_indent (f, indent: indent + 2, format: "{\n");
3537	indent += 4;
3538	gen_1 (f, indent, gimple, result: ife->falseexpr);
3539	indent -= 4;
3540	fprintf_indent (f, indent: indent + 2, format: "}\n");
3541	}
3542	return;
3543	}
3544	}
3545
3546	static unsigned fail_label_cnt;
3547	char local_fail_label[256];
3548	snprintf (s: local_fail_label, maxlen: 256, format: "next_after_fail%u", ++fail_label_cnt);
3549	fail_label = local_fail_label;
3550	bool needs_label = false;
3551
3552	/* Analyze captures and perform early-outs on the incoming arguments
3553	that cover cases we cannot handle. */
3554	capture_info cinfo (s, result, gimple);
3555	if (s->kind == simplify::SIMPLIFY)
3556	{
3557	if (!gimple)
3558	{
3559	for (unsigned i = 0; i < as_a <expr *> (p: s->match)->ops.length (); ++i)
3560	if (cinfo.force_no_side_effects & (1 << i))
3561	{
3562	fprintf_indent (f, indent,
3563	format: "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3564	i, fail_label);
3565	needs_label = true;
3566	if (verbose >= 1)
3567	warning_at (loc: as_a <expr *> (p: s->match)->ops[i]->location,
3568	msg: "forcing toplevel operand to have no "
3569	"side-effects");
3570	}
3571	for (int i = 0; i <= s->capture_max; ++i)
3572	if (cinfo.info[i].cse_p)
3573	;
3574	else if (cinfo.info[i].force_no_side_effects_p
3575	&& (cinfo.info[i].toplevel_msk
3576	& cinfo.force_no_side_effects) == 0)
3577	{
3578	fprintf_indent (f, indent,
3579	format: "if (TREE_SIDE_EFFECTS (captures[%d])) "
3580	"goto %s;\n", i, fail_label);
3581	needs_label = true;
3582	if (verbose >= 1)
3583	warning_at (loc: cinfo.info[i].c->location,
3584	msg: "forcing captured operand to have no "
3585	"side-effects");
3586	}
3587	else if ((cinfo.info[i].toplevel_msk
3588	& cinfo.force_no_side_effects) != 0)
3589	/* Mark capture as having no side-effects if we had to verify
3590	that via forced toplevel operand checks. */
3591	cinfo.info[i].force_no_side_effects_p = true;
3592	}
3593	if (gimple)
3594	{
3595	/* Force single-use restriction by only allowing simple
3596	results via setting seq to NULL. */
3597	fprintf_indent (f, indent, format: "gimple_seq *lseq = seq;\n");
3598	bool first_p = true;
3599	for (int i = 0; i <= s->capture_max; ++i)
3600	if (cinfo.info[i].force_single_use)
3601	{
3602	if (first_p)
3603	{
3604	fprintf_indent (f, indent, format: "if (lseq\n");
3605	fprintf_indent (f, indent, format: " && (");
3606	first_p = false;
3607	}
3608	else
3609	{
3610	fprintf (stream: f, format: "\n");
3611	fprintf_indent (f, indent, format: " || ");
3612	}
3613	fprintf (stream: f, format: "!single_use (captures[%d])", i);
3614	}
3615	if (!first_p)
3616	{
3617	fprintf (stream: f, format: "))\n");
3618	fprintf_indent (f, indent, format: " lseq = NULL;\n");
3619	}
3620	}
3621	}
3622
3623	if (s->kind == simplify::SIMPLIFY)
3624	{
3625	fprintf_indent (f, indent, format: "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label);
3626	needs_label = true;
3627	}
3628
3629	fprintf_indent (f, indent, format: "{\n");
3630	indent += 2;
3631	if (!result)
3632	{
3633	/* If there is no result then this is a predicate implementation. */
3634	emit_logging_call (f, indent, s, result, gimple);
3635	fprintf_indent (f, indent, format: "return true;\n");
3636	}
3637	else if (gimple)
3638	{
3639	/* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3640	in outermost position). */
3641	if (result->type == operand::OP_EXPR
3642	&& *as_a <expr *> (p: result)->operation == NON_LVALUE_EXPR)
3643	result = as_a <expr *> (p: result)->ops[0];
3644	if (result->type == operand::OP_EXPR)
3645	{
3646	expr *e = as_a <expr *> (p: result);
3647	id_base *opr = e->operation;
3648	bool is_predicate = false;
3649	/* When we delay operator substituting during lowering of fors we
3650	make sure that for code-gen purposes the effects of each substitute
3651	are the same. Thus just look at that. */
3652	if (user_id *uid = dyn_cast <user_id *> (p: opr))
3653	opr = uid->substitutes[0];
3654	else if (is_a <predicate_id *> (p: opr))
3655	is_predicate = true;
3656	if (!is_predicate)
3657	fprintf_indent (f, indent, format: "res_op->set_op (%s, type, %d);\n",
3658	*e->operation == CONVERT_EXPR
3659	? "NOP_EXPR" : e->operation->id,
3660	e->ops.length ());
3661	for (unsigned j = 0; j < e->ops.length (); ++j)
3662	{
3663	char dest[32];
3664	if (is_predicate)
3665	snprintf (s: dest, maxlen: sizeof (dest), format: "res_ops[%d]", j);
3666	else
3667	snprintf (s: dest, maxlen: sizeof (dest), format: "res_op->ops[%d]", j);
3668	const char *optype
3669	= get_operand_type (op: opr, pos: j,
3670	in_type: "type", expr_type: e->expr_type,
3671	other_oprnd_type: j == 0 ? NULL
3672	: "TREE_TYPE (res_op->ops[0])");
3673	/* We need to expand GENERIC conditions we captured from
3674	COND_EXPRs and we need to unshare them when substituting
3675	into COND_EXPRs. */
3676	int cond_handling = 0;
3677	if (!is_predicate)
3678	cond_handling = (*opr == COND_EXPR && j == 0) ? 1 : 2;
3679	e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3680	&cinfo, indexes, cond_handling);
3681	}
3682
3683	/* Re-fold the toplevel result. It's basically an embedded
3684	gimple_build w/o actually building the stmt. */
3685	if (!is_predicate)
3686	{
3687	fprintf_indent (f, indent,
3688	format: "res_op->resimplify (%s, valueize);\n",
3689	!e->force_leaf ? "lseq" : "NULL");
3690	if (e->force_leaf)
3691	{
3692	fprintf_indent (f, indent,
3693	format: "if (!maybe_push_res_to_seq (res_op, NULL)) "
3694	"goto %s;\n", fail_label);
3695	needs_label = true;
3696	}
3697	}
3698	}
3699	else if (result->type == operand::OP_CAPTURE
3700	|| result->type == operand::OP_C_EXPR)
3701	{
3702	fprintf_indent (f, indent, format: "tree tem;\n");
3703	result->gen_transform (f, indent, "tem", true, 1, "type",
3704	&cinfo, indexes);
3705	fprintf_indent (f, indent, format: "res_op->set_value (tem);\n");
3706	if (is_a <capture *> (p: result)
3707	&& cinfo.info[as_a <capture *> (p: result)->where].cond_expr_cond_p)
3708	{
3709	/* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3710	with substituting a capture of that. */
3711	fprintf_indent (f, indent,
3712	format: "if (COMPARISON_CLASS_P (tem))\n");
3713	fprintf_indent (f, indent,
3714	format: " {\n");
3715	fprintf_indent (f, indent,
3716	format: " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3717	fprintf_indent (f, indent,
3718	format: " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3719	fprintf_indent (f, indent,
3720	format: " }\n");
3721	}
3722	}
3723	else
3724	gcc_unreachable ();
3725	emit_logging_call (f, indent, s, result, gimple);
3726	fprintf_indent (f, indent, format: "return true;\n");
3727	}
3728	else /* GENERIC */
3729	{
3730	bool is_predicate = false;
3731	if (result->type == operand::OP_EXPR)
3732	{
3733	expr *e = as_a <expr *> (p: result);
3734	id_base *opr = e->operation;
3735	/* When we delay operator substituting during lowering of fors we
3736	make sure that for code-gen purposes the effects of each substitute
3737	are the same. Thus just look at that. */
3738	if (user_id *uid = dyn_cast <user_id *> (p: opr))
3739	opr = uid->substitutes[0];
3740	else if (is_a <predicate_id *> (p: opr))
3741	is_predicate = true;
3742	/* Search for captures used multiple times in the result expression
3743	and wrap them in a SAVE_EXPR. Allow as many uses as in the
3744	original expression. */
3745	if (!is_predicate)
3746	for (int i = 0; i < s->capture_max + 1; ++i)
3747	{
3748	if (cinfo.info[i].same_as != (unsigned)i
3749	|| cinfo.info[i].cse_p)
3750	continue;
3751	if (cinfo.info[i].result_use_count
3752	> cinfo.info[i].match_use_count)
3753	{
3754	fprintf_indent (f, indent,
3755	format: "if (! tree_invariant_p (captures[%d])) "
3756	"goto %s;\n", i, fail_label);
3757	needs_label = true;
3758	}
3759	}
3760	for (unsigned j = 0; j < e->ops.length (); ++j)
3761	{
3762	char dest[32];
3763	if (is_predicate)
3764	snprintf (s: dest, maxlen: sizeof (dest), format: "res_ops[%d]", j);
3765	else
3766	{
3767	fprintf_indent (f, indent, format: "tree res_op%d;\n", j);
3768	snprintf (s: dest, maxlen: sizeof (dest), format: "res_op%d", j);
3769	}
3770	const char *optype
3771	= get_operand_type (op: opr, pos: j,
3772	in_type: "type", expr_type: e->expr_type,
3773	other_oprnd_type: j == 0
3774	? NULL : "TREE_TYPE (res_op0)");
3775	e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3776	&cinfo, indexes);
3777	}
3778	if (is_predicate)
3779	{
3780	emit_logging_call (f, indent, s, result, gimple);
3781	fprintf_indent (f, indent, format: "return true;\n");
3782	}
3783	else
3784	{
3785	fprintf_indent (f, indent, format: "tree _r;\n");
3786	/* Re-fold the toplevel result. Use non_lvalue to
3787	build NON_LVALUE_EXPRs so they get properly
3788	ignored when in GIMPLE form. */
3789	if (*opr == NON_LVALUE_EXPR)
3790	fprintf_indent (f, indent,
3791	format: "_r = non_lvalue_loc (loc, res_op0);\n");
3792	else
3793	{
3794	if (is_a <operator_id *> (p: opr))
3795	fprintf_indent (f, indent,
3796	format: "_r = fold_build%d_loc (loc, %s, type",
3797	e->ops.length (),
3798	*e->operation == CONVERT_EXPR
3799	? "NOP_EXPR" : e->operation->id);
3800	else
3801	fprintf_indent (f, indent,
3802	format: "_r = maybe_build_call_expr_loc (loc, "
3803	"%s, type, %d", e->operation->id,
3804	e->ops.length());
3805	for (unsigned j = 0; j < e->ops.length (); ++j)
3806	fprintf (stream: f, format: ", res_op%d", j);
3807	fprintf (stream: f, format: ");\n");
3808	if (!is_a <operator_id *> (p: opr))
3809	{
3810	fprintf_indent (f, indent, format: "if (!_r)\n");
3811	fprintf_indent (f, indent, format: " goto %s;\n", fail_label);
3812	needs_label = true;
3813	}
3814	}
3815	}
3816	}
3817	else if (result->type == operand::OP_CAPTURE
3818	|| result->type == operand::OP_C_EXPR)
3819
3820	{
3821	fprintf_indent (f, indent, format: "tree _r;\n");
3822	result->gen_transform (f, indent, "_r", false, 1, "type",
3823	&cinfo, indexes);
3824	}
3825	else
3826	gcc_unreachable ();
3827	if (!is_predicate)
3828	{
3829	/* Search for captures not used in the result expression and dependent
3830	on TREE_SIDE_EFFECTS emit omit_one_operand. */
3831	for (int i = 0; i < s->capture_max + 1; ++i)
3832	{
3833	if (cinfo.info[i].same_as != (unsigned)i)
3834	continue;
3835	if (!cinfo.info[i].force_no_side_effects_p
3836	&& !cinfo.info[i].expr_p
3837	&& cinfo.info[i].result_use_count == 0)
3838	{
3839	fprintf_indent (f, indent,
3840	format: "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3841	i);
3842	fprintf_indent (f, indent: indent + 2,
3843	format: "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3844	"fold_ignored_result (captures[%d]), _r);\n",
3845	i);
3846	}
3847	}
3848	emit_logging_call (f, indent, s, result, gimple);
3849	fprintf_indent (f, indent, format: "return _r;\n");
3850	}
3851	}
3852	indent -= 2;
3853	fprintf_indent (f, indent, format: "}\n");
3854	if (needs_label)
3855	fprintf (stream: f, format: "%s:;\n", fail_label);
3856	fail_label = NULL;
3857	}
3858
3859	/* Generate code for the '(if ...)', '(with ..)' and actual transform
3860	step of a '(simplify ...)' or '(match ...)'. This handles everything
3861	that is not part of the decision tree (simplify->match). */
3862
3863	void
3864	dt_simplify::gen (FILE *f, int indent, bool gimple, int depth ATTRIBUTE_UNUSED)
3865	{
3866	fprintf_indent (f, indent, format: "{\n");
3867	indent += 2;
3868	output_line_directive (f,
3869	location: s->result ? s->result->location : s->match->location);
3870	if (s->capture_max >= 0)
3871	{
3872	char opname[20];
3873	fprintf_indent (f, indent, format: "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3874	s->capture_max + 1, indexes[0]->get_name (name: opname));
3875
3876	for (int i = 1; i <= s->capture_max; ++i)
3877	{
3878	if (!indexes[i])
3879	break;
3880	fprintf (stream: f, format: ", %s", indexes[i]->get_name (name: opname));
3881	}
3882	fprintf (stream: f, format: " };\n");
3883	}
3884
3885	/* If we have a split-out function for the actual transform, call it. */
3886	if (info && info->fname)
3887	{
3888	if (gimple)
3889	{
3890	fprintf_indent (f, indent, format: "if (%s (res_op, seq, "
3891	"valueize, type, captures", info->fname);
3892	for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3893	if (s->for_subst_vec[i].first->used)
3894	fprintf (stream: f, format: ", %s", s->for_subst_vec[i].second->id);
3895	fprintf (stream: f, format: "))\n");
3896	fprintf_indent (f, indent, format: " return true;\n");
3897	}
3898	else
3899	{
3900	fprintf_indent (f, indent, format: "tree res = %s (loc, type",
3901	info->fname);
3902	for (unsigned i = 0; i < as_a <expr *> (p: s->match)->ops.length (); ++i)
3903	fprintf (stream: f, format: ", _p%d", i);
3904	fprintf (stream: f, format: ", captures");
3905	for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3906	{
3907	if (s->for_subst_vec[i].first->used)
3908	fprintf (stream: f, format: ", %s", s->for_subst_vec[i].second->id);
3909	}
3910	fprintf (stream: f, format: ");\n");
3911	fprintf_indent (f, indent, format: "if (res) return res;\n");
3912	}
3913	}
3914	else
3915	{
3916	for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3917	{
3918	if (! s->for_subst_vec[i].first->used)
3919	continue;
3920	if (is_a <operator_id *> (p: s->for_subst_vec[i].second))
3921	fprintf_indent (f, indent, format: "const enum tree_code %s = %s;\n",
3922	s->for_subst_vec[i].first->id,
3923	s->for_subst_vec[i].second->id);
3924	else if (is_a <fn_id *> (p: s->for_subst_vec[i].second))
3925	fprintf_indent (f, indent, format: "const combined_fn %s = %s;\n",
3926	s->for_subst_vec[i].first->id,
3927	s->for_subst_vec[i].second->id);
3928	else
3929	gcc_unreachable ();
3930	}
3931	gen_1 (f, indent, gimple, result: s->result);
3932	}
3933
3934	indent -= 2;
3935	fprintf_indent (f, indent, format: "}\n");
3936	}
3937
3938
3939	/* Hash function for finding equivalent transforms. */
3940
3941	hashval_t
3942	sinfo_hashmap_traits::hash (const key_type &v)
3943	{
3944	/* Only bother to compare those originating from the same source pattern. */
3945	return v->s->result->location;
3946	}
3947
3948	/* Compare function for finding equivalent transforms. */
3949
3950	static bool
3951	compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3952	{
3953	if (o1->type != o2->type)
3954	return false;
3955
3956	switch (o1->type)
3957	{
3958	case operand::OP_IF:
3959	{
3960	if_expr *if1 = as_a <if_expr *> (p: o1);
3961	if_expr *if2 = as_a <if_expr *> (p: o2);
3962	/* ??? Properly compare c-exprs. */
3963	if (if1->cond != if2->cond)
3964	return false;
3965	if (!compare_op (o1: if1->trueexpr, s1, o2: if2->trueexpr, s2))
3966	return false;
3967	if (if1->falseexpr != if2->falseexpr
3968	|| (if1->falseexpr
3969	&& !compare_op (o1: if1->falseexpr, s1, o2: if2->falseexpr, s2)))
3970	return false;
3971	return true;
3972	}
3973	case operand::OP_WITH:
3974	{
3975	with_expr *with1 = as_a <with_expr *> (p: o1);
3976	with_expr *with2 = as_a <with_expr *> (p: o2);
3977	if (with1->with != with2->with)
3978	return false;
3979	return compare_op (o1: with1->subexpr, s1, o2: with2->subexpr, s2);
3980	}
3981	default:;
3982	}
3983
3984	/* We've hit a result. Time to compare capture-infos - this is required
3985	in addition to the conservative pointer-equivalency of the result IL. */
3986	capture_info cinfo1 (s1, o1, true);
3987	capture_info cinfo2 (s2, o2, true);
3988
3989	if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3990	|| cinfo1.info.length () != cinfo2.info.length ())
3991	return false;
3992
3993	for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3994	{
3995	if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3996	|| cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3997	|| (cinfo1.info[i].force_no_side_effects_p
3998	!= cinfo2.info[i].force_no_side_effects_p)
3999	|| cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
4000	|| cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
4001	/* toplevel_msk is an optimization */
4002	|| cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
4003	|| cinfo1.info[i].same_as != cinfo2.info[i].same_as
4004	/* the pointer back to the capture is for diagnostics only */)
4005	return false;
4006	}
4007
4008	/* ??? Deep-compare the actual result. */
4009	return o1 == o2;
4010	}
4011
4012	bool
4013	sinfo_hashmap_traits::equal_keys (const key_type &v,
4014	const key_type &candidate)
4015	{
4016	return compare_op (o1: v->s->result, s1: v->s, o2: candidate->s->result, s2: candidate->s);
4017	}
4018
4019
4020	/* Main entry to generate code for matching GIMPLE IL off the decision
4021	tree. */
4022
4023	void
4024	decision_tree::gen (vec <FILE *> &files, bool gimple)
4025	{
4026	sinfo_map_t si;
4027
4028	root->analyze (map&: si);
4029
4030	fprintf (stderr, format: "%s decision tree has %u leafs, maximum depth %u and "
4031	"a total number of %u nodes\n",
4032	gimple ? "GIMPLE" : "GENERIC",
4033	root->num_leafs, root->max_level, root->total_size);
4034
4035	/* First split out the transform part of equal leafs. */
4036	unsigned rcnt = 0;
4037	unsigned fcnt = 1;
4038	for (sinfo_map_t::iterator iter = si.begin ();
4039	iter != si.end (); ++iter)
4040	{
4041	sinfo *s = (*iter).second;
4042	/* Do not split out single uses. */
4043	if (s->cnt <= 1)
4044	continue;
4045
4046	rcnt += s->cnt - 1;
4047	if (verbose >= 1)
4048	{
4049	fprintf (stderr, format: "found %u uses of", s->cnt);
4050	output_line_directive (stderr, location: s->s->s->result->location);
4051	}
4052
4053	/* Cycle the file buffers. */
4054	FILE *f = choose_output (parts: files);
4055
4056	/* Generate a split out function with the leaf transform code. */
4057	s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
4058	fcnt++);
4059	if (gimple)
4060	fp_decl (f, format: "\nbool\n"
4061	"%s (gimple_match_op *res_op, gimple_seq *seq,\n"
4062	" tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4063	" const tree ARG_UNUSED (type), tree *ARG_UNUSED "
4064	"(captures)",
4065	s->fname);
4066	else
4067	{
4068	fp_decl (f, format: "\ntree\n"
4069	"%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
4070	(*iter).second->fname);
4071	for (unsigned i = 0;
4072	i < as_a <expr *>(p: s->s->s->match)->ops.length (); ++i)
4073	fp_decl (f, format: " tree ARG_UNUSED (_p%d),", i);
4074	fp_decl (f, format: " tree *ARG_UNUSED (captures)");
4075	}
4076	for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
4077	{
4078	if (! s->s->s->for_subst_vec[i].first->used)
4079	continue;
4080	if (is_a <operator_id *> (p: s->s->s->for_subst_vec[i].second))
4081	fp_decl (f, format: ",\n const enum tree_code ARG_UNUSED (%s)",
4082	s->s->s->for_subst_vec[i].first->id);
4083	else if (is_a <fn_id *> (p: s->s->s->for_subst_vec[i].second))
4084	fp_decl (f, format: ",\n const combined_fn ARG_UNUSED (%s)",
4085	s->s->s->for_subst_vec[i].first->id);
4086	}
4087
4088	fp_decl_done (f, trailer: ")");
4089	fprintf (stream: f, format: "{\n");
4090	fprintf_indent (f, indent: 2, format: "const bool debug_dump = "
4091	"dump_file && (dump_flags & TDF_FOLDING);\n");
4092	s->s->gen_1 (f, indent: 2, gimple, result: s->s->s->result);
4093	if (gimple)
4094	fprintf (stream: f, format: " return false;\n");
4095	else
4096	fprintf (stream: f, format: " return NULL_TREE;\n");
4097	fprintf (stream: f, format: "}\n");
4098	}
4099	fprintf (stderr, format: "removed %u duplicate tails\n", rcnt);
4100
4101	for (unsigned n = 1; n <= 7; ++n)
4102	{
4103	bool has_kids_p = false;
4104
4105	/* First generate split-out functions. */
4106	for (unsigned j = 0; j < root->kids.length (); j++)
4107	{
4108	dt_operand *dop = static_cast<dt_operand *>(root->kids[j]);
4109	expr *e = static_cast<expr *>(dop->op);
4110	if (e->ops.length () != n
4111	/* Builtin simplifications are somewhat premature on
4112	GENERIC. The following drops patterns with outermost
4113	calls. It's easy to emit overloads for function code
4114	though if necessary. */
4115	|| (!gimple
4116	&& e->operation->kind != id_base::CODE))
4117	continue;
4118
4119
4120	/* Cycle the file buffers. */
4121	FILE *f = choose_output (parts: files);
4122
4123	if (gimple)
4124	fp_decl (f, format: "\nbool\n"
4125	"gimple_simplify_%s (gimple_match_op *res_op,"
4126	" gimple_seq *seq,\n"
4127	" tree (*valueize)(tree) "
4128	"ATTRIBUTE_UNUSED,\n"
4129	" code_helper ARG_UNUSED (code), tree "
4130	"ARG_UNUSED (type)",
4131	e->operation->id);
4132	else
4133	fp_decl (f, format: "\ntree\n"
4134	"generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
4135	"tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
4136	e->operation->id);
4137	for (unsigned i = 0; i < n; ++i)
4138	fp_decl (f, format: ", tree _p%d", i);
4139	fp_decl_done (f, trailer: ")");
4140	fprintf (stream: f, format: "{\n");
4141	fprintf_indent (f, indent: 2, format: "const bool debug_dump = "
4142	"dump_file && (dump_flags & TDF_FOLDING);\n");
4143	dop->gen_kids (f, indent: 2, gimple, depth: 0);
4144	if (gimple)
4145	fprintf (stream: f, format: " return false;\n");
4146	else
4147	fprintf (stream: f, format: " return NULL_TREE;\n");
4148	fprintf (stream: f, format: "}\n");
4149	has_kids_p = true;
4150	}
4151
4152	/* If this main entry has no children, avoid generating code
4153	with compiler warnings, by generating a simple stub. */
4154	if (! has_kids_p)
4155	{
4156
4157	/* Cycle the file buffers. */
4158	FILE *f = choose_output (parts: files);
4159
4160	if (gimple)
4161	fp_decl (f, format: "\nbool\n"
4162	"gimple_simplify (gimple_match_op*, gimple_seq*,\n"
4163	" tree (*)(tree), code_helper,\n"
4164	" const tree");
4165	else
4166	fp_decl (f, format: "\ntree\n"
4167	"generic_simplify (location_t, enum tree_code,\n"
4168	" const tree");
4169	for (unsigned i = 0; i < n; ++i)
4170	fp_decl (f, format: ", tree");
4171	fp_decl_done (f, trailer: ")");
4172	fprintf (stream: f, format: "{\n");
4173	if (gimple)
4174	fprintf (stream: f, format: " return false;\n");
4175	else
4176	fprintf (stream: f, format: " return NULL_TREE;\n");
4177	fprintf (stream: f, format: "}\n");
4178	continue;
4179	}
4180
4181
4182	/* Cycle the file buffers. */
4183	FILE *f = choose_output (parts: files);
4184
4185	/* Then generate the main entry with the outermost switch and
4186	tail-calls to the split-out functions. */
4187	if (gimple)
4188	fp_decl (f, format: "\nbool\n"
4189	"gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
4190	" tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4191	" code_helper code, const tree type");
4192	else
4193	fp_decl (f, format: "\ntree\n"
4194	"generic_simplify (location_t loc, enum tree_code code, "
4195	"const tree type ATTRIBUTE_UNUSED");
4196	for (unsigned i = 0; i < n; ++i)
4197	fp_decl (f, format: ", tree _p%d", i);
4198	fp_decl_done (f, trailer: ")");
4199	fprintf (stream: f, format: "{\n");
4200
4201	if (gimple)
4202	fprintf (stream: f, format: " switch (code.get_rep())\n"
4203	" {\n");
4204	else
4205	fprintf (stream: f, format: " switch (code)\n"
4206	" {\n");
4207	for (unsigned i = 0; i < root->kids.length (); i++)
4208	{
4209	dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
4210	expr *e = static_cast<expr *>(dop->op);
4211	if (e->ops.length () != n
4212	/* Builtin simplifications are somewhat premature on
4213	GENERIC. The following drops patterns with outermost
4214	calls. It's easy to emit overloads for function code
4215	though if necessary. */
4216	|| (!gimple
4217	&& e->operation->kind != id_base::CODE))
4218	continue;
4219
4220	if (*e->operation == CONVERT_EXPR
4221	|| *e->operation == NOP_EXPR)
4222	fprintf (stream: f, format: " CASE_CONVERT:\n");
4223	else
4224	fprintf (stream: f, format: " case %s%s:\n",
4225	is_a <fn_id *> (p: e->operation) ? "-" : "",
4226	e->operation->id);
4227	if (gimple)
4228	fprintf (stream: f, format: " return gimple_simplify_%s (res_op, "
4229	"seq, valueize, code, type", e->operation->id);
4230	else
4231	fprintf (stream: f, format: " return generic_simplify_%s (loc, code, type",
4232	e->operation->id);
4233	for (unsigned j = 0; j < n; ++j)
4234	fprintf (stream: f, format: ", _p%d", j);
4235	fprintf (stream: f, format: ");\n");
4236	}
4237	fprintf (stream: f, format: " default:;\n"
4238	" }\n");
4239
4240	if (gimple)
4241	fprintf (stream: f, format: " return false;\n");
4242	else
4243	fprintf (stream: f, format: " return NULL_TREE;\n");
4244	fprintf (stream: f, format: "}\n");
4245	}
4246	}
4247
4248	/* Output code to implement the predicate P from the decision tree DT. */
4249
4250	void
4251	write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
4252	{
4253	fp_decl (f, format: "\nbool\n%s%s (tree t%s%s)",
4254	gimple ? "gimple_" : "tree_", p->id,
4255	p->nargs > 0 ? ", tree *res_ops" : "",
4256	gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4257	fp_decl_done (f, trailer: "");
4258	fprintf (stream: f, format: "{\n");
4259	/* Conveniently make 'type' available. */
4260	fprintf_indent (f, indent: 2, format: "const tree type = TREE_TYPE (t);\n");
4261	fprintf_indent (f, indent: 2, format: "const bool debug_dump = "
4262	"dump_file && (dump_flags & TDF_FOLDING);\n");
4263
4264	if (!gimple)
4265	fprintf_indent (f, indent: 2, format: "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4266	dt.root->gen_kids (f, indent: 2, gimple, depth: 0);
4267
4268	fprintf_indent (f, indent: 2, format: "return false;\n"
4269	"}\n");
4270	}
4271
4272	/* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4273
4274	static void
4275	write_header (FILE *f, const char *head)
4276	{
4277	fprintf (stream: f, format: "/* Generated automatically by the program `genmatch' from\n");
4278	fprintf (stream: f, format: " a IL pattern matching and simplification description. */\n");
4279	fprintf (stream: f, format: "#pragma GCC diagnostic push\n");
4280	fprintf (stream: f, format: "#pragma GCC diagnostic ignored \"-Wunused-variable\"\n");
4281	fprintf (stream: f, format: "#pragma GCC diagnostic ignored \"-Wunused-function\"\n");
4282
4283	/* Include the header instead of writing it awkwardly quoted here. */
4284	if (head)
4285	fprintf (stream: f, format: "\n#include \"%s\"\n", head);
4286	}
4287
4288
4289
4290	/* AST parsing. */
4291
4292	class parser
4293	{
4294	public:
4295	parser (cpp_reader *, bool gimple);
4296
4297	private:
4298	const cpp_token *next ();
4299	const cpp_token *peek (unsigned = 1);
4300	const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
4301	const cpp_token *expect (enum cpp_ttype);
4302	const cpp_token *eat_token (enum cpp_ttype);
4303	const char *get_string ();
4304	const char *get_ident ();
4305	const cpp_token *eat_ident (const char *);
4306	const char *get_number ();
4307
4308	unsigned get_internal_capture_id ();
4309
4310	id_base *parse_operation (unsigned char &);
4311	operand *parse_capture (operand *, bool);
4312	operand *parse_expr ();
4313	c_expr *parse_c_expr (cpp_ttype);
4314	operand *parse_op ();
4315
4316	void record_operlist (location_t, user_id *);
4317
4318	void parse_pattern ();
4319	operand *parse_result (operand *, predicate_id *);
4320	void push_simplify (simplify::simplify_kind,
4321	vec<simplify *>&, operand *, operand *);
4322	void parse_simplify (simplify::simplify_kind,
4323	vec<simplify *>&, predicate_id *, operand *);
4324	void parse_for (location_t);
4325	void parse_if (location_t);
4326	void parse_predicates (location_t);
4327	void parse_operator_list (location_t);
4328
4329	void finish_match_operand (operand *);
4330
4331	cpp_reader *r;
4332	bool gimple;
4333	vec<c_expr *> active_ifs;
4334	vec<vec<user_id *> > active_fors;
4335	hash_set<user_id *> *oper_lists_set;
4336	vec<user_id *> oper_lists;
4337
4338	cid_map_t *capture_ids;
4339	unsigned last_id;
4340
4341	public:
4342	vec<simplify *> simplifiers;
4343	vec<predicate_id *> user_predicates;
4344	bool parsing_match_operand;
4345	};
4346
4347	/* Lexing helpers. */
4348
4349	/* Read the next non-whitespace token from R. */
4350
4351	const cpp_token *
4352	parser::next ()
4353	{
4354	const cpp_token *token;
4355	do
4356	{
4357	token = cpp_get_token (r);
4358	}
4359	while (token->type == CPP_PADDING);
4360	return token;
4361	}
4362
4363	/* Peek at the next non-whitespace token from R. */
4364
4365	const cpp_token *
4366	parser::peek (unsigned num)
4367	{
4368	const cpp_token *token;
4369	unsigned i = 0;
4370	do
4371	{
4372	token = cpp_peek_token (r, i++);
4373	}
4374	while (token->type == CPP_PADDING
4375	|| (--num > 0));
4376	/* If we peek at EOF this is a fatal error as it leaves the
4377	cpp_reader in unusable state. Assume we really wanted a
4378	token and thus this EOF is unexpected. */
4379	if (token->type == CPP_EOF)
4380	fatal_at (tk: token, msg: "unexpected end of file");
4381	return token;
4382	}
4383
4384	/* Peek at the next identifier token (or return NULL if the next
4385	token is not an identifier or equal to ID if supplied). */
4386
4387	const cpp_token *
4388	parser::peek_ident (const char *id, unsigned num)
4389	{
4390	const cpp_token *token = peek (num);
4391	if (token->type != CPP_NAME)
4392	return 0;
4393
4394	if (id == 0)
4395	return token;
4396
4397	const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
4398	if (strcmp (s1: id, s2: t) == 0)
4399	return token;
4400
4401	return 0;
4402	}
4403
4404	/* Read the next token from R and assert it is of type TK. */
4405
4406	const cpp_token *
4407	parser::expect (enum cpp_ttype tk)
4408	{
4409	const cpp_token *token = next ();
4410	if (token->type != tk)
4411	fatal_at (tk: token, msg: "expected %s, got %s",
4412	cpp_type2name (tk, flags: 0), cpp_type2name (token->type, flags: 0));
4413
4414	return token;
4415	}
4416
4417	/* Consume the next token from R and assert it is of type TK. */
4418
4419	const cpp_token *
4420	parser::eat_token (enum cpp_ttype tk)
4421	{
4422	return expect (tk);
4423	}
4424
4425	/* Read the next token from R and assert it is of type CPP_STRING and
4426	return its value. */
4427
4428	const char *
4429	parser::get_string ()
4430	{
4431	const cpp_token *token = expect (tk: CPP_STRING);
4432	return (const char *)token->val.str.text;
4433	}
4434
4435	/* Read the next token from R and assert it is of type CPP_NAME and
4436	return its value. */
4437
4438	const char *
4439	parser::get_ident ()
4440	{
4441	const cpp_token *token = expect (tk: CPP_NAME);
4442	return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
4443	}
4444
4445	/* Eat an identifier token with value S from R. */
4446
4447	const cpp_token *
4448	parser::eat_ident (const char *s)
4449	{
4450	const cpp_token *token = peek ();
4451	const char *t = get_ident ();
4452	if (strcmp (s1: s, s2: t) != 0)
4453	fatal_at (tk: token, msg: "expected '%s' got '%s'\n", s, t);
4454	return token;
4455	}
4456
4457	/* Read the next token from R and assert it is of type CPP_NUMBER and
4458	return its value. */
4459
4460	const char *
4461	parser::get_number ()
4462	{
4463	const cpp_token *token = expect (tk: CPP_NUMBER);
4464	return (const char *)token->val.str.text;
4465	}
4466
4467	/* Return a capture ID that can be used internally. */
4468
4469	unsigned
4470	parser::get_internal_capture_id ()
4471	{
4472	unsigned newid = capture_ids->elements ();
4473	/* Big enough for a 32-bit UINT_MAX plus prefix. */
4474	char id[13];
4475	bool existed;
4476	snprintf (s: id, maxlen: sizeof (id), format: "__%u", newid);
4477	capture_ids->get_or_insert (k: xstrdup (id), existed: &existed);
4478	if (existed)
4479	fatal ("reserved capture id '%s' already used", id);
4480	return newid;
4481	}
4482
4483	/* Record an operator-list use for transparent for handling. */
4484
4485	void
4486	parser::record_operlist (location_t loc, user_id *p)
4487	{
4488	if (!oper_lists_set->add (k: p))
4489	{
4490	if (!oper_lists.is_empty ()
4491	&& oper_lists[0]->substitutes.length () != p->substitutes.length ())
4492	fatal_at (loc, msg: "User-defined operator list does not have the "
4493	"same number of entries as others used in the pattern");
4494	oper_lists.safe_push (obj: p);
4495	}
4496	}
4497
4498	/* Parse the operator ID, special-casing convert?, convert1? and
4499	convert2? */
4500
4501	id_base *
4502	parser::parse_operation (unsigned char &opt_grp)
4503	{
4504	const cpp_token *id_tok = peek ();
4505	char *alt_id = NULL;
4506	const char *id = get_ident ();
4507	const cpp_token *token = peek ();
4508	opt_grp = 0;
4509	if (token->type == CPP_QUERY
4510	&& !(token->flags & PREV_WHITE))
4511	{
4512	if (!parsing_match_operand)
4513	fatal_at (tk: id_tok, msg: "conditional convert can only be used in "
4514	"match expression");
4515	if (ISDIGIT (id[strlen (id) - 1]))
4516	{
4517	opt_grp = id[strlen (s: id) - 1] - '0' + 1;
4518	alt_id = xstrdup (id);
4519	alt_id[strlen (s: id) - 1] = '\0';
4520	if (opt_grp == 1)
4521	fatal_at (tk: id_tok, msg: "use '%s?' here", alt_id);
4522	}
4523	else
4524	opt_grp = 1;
4525	eat_token (tk: CPP_QUERY);
4526	}
4527	id_base *op = get_operator (id: alt_id ? alt_id : id);
4528	if (!op)
4529	fatal_at (tk: id_tok, msg: "unknown operator %s", alt_id ? alt_id : id);
4530	if (alt_id)
4531	free (ptr: alt_id);
4532	user_id *p = dyn_cast<user_id *> (p: op);
4533	if (p && p->is_oper_list)
4534	{
4535	if (active_fors.length() == 0)
4536	record_operlist (loc: id_tok->src_loc, p);
4537	else
4538	fatal_at (tk: id_tok, msg: "operator-list %s cannot be expanded inside 'for'", id);
4539	}
4540	return op;
4541	}
4542
4543	/* Parse a capture.
4544	capture = '@'<number> */
4545
4546	class operand *
4547	parser::parse_capture (operand *op, bool require_existing)
4548	{
4549	location_t src_loc = eat_token (tk: CPP_ATSIGN)->src_loc;
4550	const cpp_token *token = peek ();
4551	const char *id = NULL;
4552	bool value_match = false;
4553	/* For matches parse @@ as a value-match denoting the prevailing operand. */
4554	if (token->type == CPP_ATSIGN
4555	&& ! (token->flags & PREV_WHITE)
4556	&& parsing_match_operand)
4557	{
4558	eat_token (tk: CPP_ATSIGN);
4559	token = peek ();
4560	value_match = true;
4561	}
4562	if (token->type == CPP_NUMBER)
4563	id = get_number ();
4564	else if (token->type == CPP_NAME)
4565	id = get_ident ();
4566	else
4567	fatal_at (tk: token, msg: "expected number or identifier");
4568	unsigned next_id = capture_ids->elements ();
4569	bool existed;
4570	unsigned &num = capture_ids->get_or_insert (k: id, existed: &existed);
4571	if (!existed)
4572	{
4573	if (require_existing)
4574	fatal_at (loc: src_loc, msg: "unknown capture id");
4575	num = next_id;
4576	}
4577	return new capture (src_loc, num, op, value_match);
4578	}
4579
4580	/* Parse an expression
4581	expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4582
4583	class operand *
4584	parser::parse_expr ()
4585	{
4586	const cpp_token *token = peek ();
4587	unsigned char opt_grp;
4588	expr *e = new expr (parse_operation (opt_grp), token->src_loc);
4589	token = peek ();
4590	operand *op;
4591	bool is_commutative = false;
4592	bool force_capture = false;
4593	const char *expr_type = NULL;
4594
4595	if (!parsing_match_operand
4596	&& token->type == CPP_NOT
4597	&& !(token->flags & PREV_WHITE))
4598	{
4599	eat_token (tk: CPP_NOT);
4600	e->force_leaf = true;
4601	}
4602
4603	if (token->type == CPP_COLON
4604	&& !(token->flags & PREV_WHITE))
4605	{
4606	eat_token (tk: CPP_COLON);
4607	token = peek ();
4608	if (token->type == CPP_NAME
4609	&& !(token->flags & PREV_WHITE))
4610	{
4611	const char *s = get_ident ();
4612	if (!parsing_match_operand)
4613	expr_type = s;
4614	else
4615	{
4616	const char *sp = s;
4617	while (*sp)
4618	{
4619	if (*sp == 'c')
4620	{
4621	if (operator_id *o
4622	= dyn_cast<operator_id *> (p: e->operation))
4623	{
4624	if (!commutative_tree_code (code: o->code)
4625	&& !comparison_code_p (code: o->code))
4626	fatal_at (tk: token, msg: "operation is not commutative");
4627	}
4628	else if (user_id *p = dyn_cast<user_id *> (p: e->operation))
4629	for (unsigned i = 0;
4630	i < p->substitutes.length (); ++i)
4631	{
4632	if (operator_id *q
4633	= dyn_cast<operator_id *> (p: p->substitutes[i]))
4634	{
4635	if (!commutative_tree_code (code: q->code)
4636	&& !comparison_code_p (code: q->code))
4637	fatal_at (tk: token, msg: "operation %s is not "
4638	"commutative", q->id);
4639	}
4640	}
4641	is_commutative = true;
4642	}
4643	else if (*sp == 'C')
4644	is_commutative = true;
4645	else if (*sp == 's')
4646	{
4647	e->force_single_use = true;
4648	force_capture = true;
4649	}
4650	else
4651	fatal_at (tk: token, msg: "flag %c not recognized", *sp);
4652	sp++;
4653	}
4654	}
4655	token = peek ();
4656	}
4657	else
4658	fatal_at (tk: token, msg: "expected flag or type specifying identifier");
4659	}
4660
4661	if (token->type == CPP_ATSIGN
4662	&& !(token->flags & PREV_WHITE))
4663	op = parse_capture (op: e, require_existing: false);
4664	else if (force_capture)
4665	{
4666	unsigned num = get_internal_capture_id ();
4667	op = new capture (token->src_loc, num, e, false);
4668	}
4669	else
4670	op = e;
4671	do
4672	{
4673	token = peek ();
4674	if (token->type == CPP_CLOSE_PAREN)
4675	{
4676	if (e->operation->nargs != -1
4677	&& e->operation->nargs != (int) e->ops.length ())
4678	fatal_at (tk: token, msg: "'%s' expects %u operands, not %u",
4679	e->operation->id, e->operation->nargs, e->ops.length ());
4680	if (is_commutative)
4681	{
4682	if (e->ops.length () == 2
4683	|| commutative_op (id: e->operation) >= 0)
4684	e->is_commutative = true;
4685	else
4686	fatal_at (tk: token, msg: "only binary operators or functions with "
4687	"two arguments can be marked commutative, "
4688	"unless the operation is known to be inherently "
4689	"commutative");
4690	}
4691	e->expr_type = expr_type;
4692	if (opt_grp != 0)
4693	{
4694	if (e->ops.length () != 1)
4695	fatal_at (tk: token, msg: "only unary operations can be conditional");
4696	e->opt_grp = opt_grp;
4697	}
4698	return op;
4699	}
4700	else if (!(token->flags & PREV_WHITE))
4701	fatal_at (tk: token, msg: "expected expression operand");
4702
4703	e->append_op (op: parse_op ());
4704	}
4705	while (1);
4706	}
4707
4708	/* Lex native C code delimited by START recording the preprocessing tokens
4709	for later processing.
4710	c_expr = ('{'|'(') <pp token>... ('}'|')') */
4711
4712	c_expr *
4713	parser::parse_c_expr (cpp_ttype start)
4714	{
4715	const cpp_token *token;
4716	cpp_ttype end;
4717	unsigned opencnt;
4718	vec<cpp_token> code = vNULL;
4719	unsigned nr_stmts = 0;
4720	location_t loc = eat_token (tk: start)->src_loc;
4721	if (start == CPP_OPEN_PAREN)
4722	end = CPP_CLOSE_PAREN;
4723	else if (start == CPP_OPEN_BRACE)
4724	end = CPP_CLOSE_BRACE;
4725	else
4726	gcc_unreachable ();
4727	opencnt = 1;
4728	do
4729	{
4730	token = next ();
4731
4732	/* Count brace pairs to find the end of the expr to match. */
4733	if (token->type == start)
4734	opencnt++;
4735	else if (token->type == end
4736	&& --opencnt == 0)
4737	break;
4738	else if (token->type == CPP_EOF)
4739	fatal_at (tk: token, msg: "unexpected end of file");
4740
4741	/* This is a lame way of counting the number of statements. */
4742	if (token->type == CPP_SEMICOLON)
4743	nr_stmts++;
4744
4745	/* If this is possibly a user-defined identifier mark it used. */
4746	if (token->type == CPP_NAME)
4747	{
4748	const char *str
4749	= (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
4750	if (strcmp (s1: str, s2: "return") == 0)
4751	fatal_at (tk: token, msg: "return statement not allowed in C expression");
4752	/* Mark user operators corresponding to 'str' as used. */
4753	get_operator (id: str);
4754	}
4755
4756	/* Record the token. */
4757	code.safe_push (obj: *token);
4758	}
4759	while (1);
4760	return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4761	}
4762
4763	/* Parse an operand which is either an expression, a predicate or
4764	a standalone capture.
4765	op = predicate | expr | c_expr | capture */
4766
4767	class operand *
4768	parser::parse_op ()
4769	{
4770	const cpp_token *token = peek ();
4771	class operand *op = NULL;
4772	if (token->type == CPP_OPEN_PAREN)
4773	{
4774	eat_token (tk: CPP_OPEN_PAREN);
4775	op = parse_expr ();
4776	eat_token (tk: CPP_CLOSE_PAREN);
4777	}
4778	else if (token->type == CPP_OPEN_BRACE)
4779	{
4780	op = parse_c_expr (start: CPP_OPEN_BRACE);
4781	}
4782	else
4783	{
4784	/* Remaining ops are either empty or predicates */
4785	if (token->type == CPP_NAME)
4786	{
4787	const char *id = get_ident ();
4788	id_base *opr = get_operator (id);
4789	if (!opr)
4790	fatal_at (tk: token, msg: "expected predicate name");
4791	if (operator_id *code1 = dyn_cast <operator_id *> (p: opr))
4792	{
4793	if (code1->nargs != 0)
4794	fatal_at (tk: token, msg: "using an operator with operands as predicate");
4795	/* Parse the zero-operand operator "predicates" as
4796	expression. */
4797	op = new expr (opr, token->src_loc);
4798	}
4799	else if (user_id *code2 = dyn_cast <user_id *> (p: opr))
4800	{
4801	if (code2->nargs != 0)
4802	fatal_at (tk: token, msg: "using an operator with operands as predicate");
4803	/* Parse the zero-operand operator "predicates" as
4804	expression. */
4805	op = new expr (opr, token->src_loc);
4806	}
4807	else if (predicate_id *p = dyn_cast <predicate_id *> (p: opr))
4808	op = new predicate (p, token->src_loc);
4809	else
4810	fatal_at (tk: token, msg: "using an unsupported operator as predicate");
4811	if (!parsing_match_operand)
4812	fatal_at (tk: token, msg: "predicates are only allowed in match expression");
4813	token = peek ();
4814	if (token->flags & PREV_WHITE)
4815	return op;
4816	}
4817	else if (token->type != CPP_COLON
4818	&& token->type != CPP_ATSIGN)
4819	fatal_at (tk: token, msg: "expected expression or predicate");
4820	/* optionally followed by a capture and a predicate. */
4821	if (token->type == CPP_COLON)
4822	fatal_at (tk: token, msg: "not implemented: predicate on leaf operand");
4823	if (token->type == CPP_ATSIGN)
4824	op = parse_capture (op, require_existing: !parsing_match_operand);
4825	}
4826
4827	return op;
4828	}
4829
4830	/* Create a new simplify from the current parsing state and MATCH,
4831	MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4832
4833	void
4834	parser::push_simplify (simplify::simplify_kind kind,
4835	vec<simplify *>& simplifiers,
4836	operand *match, operand *result)
4837	{
4838	/* Build and push a temporary for operator list uses in expressions. */
4839	if (!oper_lists.is_empty ())
4840	active_fors.safe_push (obj: oper_lists);
4841
4842	simplifiers.safe_push
4843	(obj: new simplify (kind, last_id++, match, result,
4844	active_fors.copy (), capture_ids));
4845
4846	if (!oper_lists.is_empty ())
4847	active_fors.pop ();
4848	}
4849
4850	/* Parse
4851	<result-op> = <op> | <if> | <with>
4852	<if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4853	<with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4854	and return it. */
4855
4856	operand *
4857	parser::parse_result (operand *result, predicate_id *matcher)
4858	{
4859	const cpp_token *token = peek ();
4860	if (token->type != CPP_OPEN_PAREN)
4861	return parse_op ();
4862
4863	eat_token (tk: CPP_OPEN_PAREN);
4864	if (peek_ident (id: "if"))
4865	{
4866	eat_ident (s: "if");
4867	if_expr *ife = new if_expr (token->src_loc);
4868	ife->cond = parse_c_expr (start: CPP_OPEN_PAREN);
4869	if (peek ()->type == CPP_OPEN_PAREN)
4870	{
4871	ife->trueexpr = parse_result (result, matcher);
4872	if (peek ()->type == CPP_OPEN_PAREN)
4873	ife->falseexpr = parse_result (result, matcher);
4874	else if (peek ()->type != CPP_CLOSE_PAREN)
4875	ife->falseexpr = parse_op ();
4876	}
4877	else if (peek ()->type != CPP_CLOSE_PAREN)
4878	{
4879	ife->trueexpr = parse_op ();
4880	if (peek ()->type == CPP_OPEN_PAREN)
4881	ife->falseexpr = parse_result (result, matcher);
4882	else if (peek ()->type != CPP_CLOSE_PAREN)
4883	ife->falseexpr = parse_op ();
4884	}
4885	/* If this if is immediately closed then it contains a
4886	manual matcher or is part of a predicate definition. */
4887	else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4888	{
4889	if (!matcher)
4890	fatal_at (tk: peek (), msg: "manual transform not implemented");
4891	ife->trueexpr = result;
4892	}
4893	eat_token (tk: CPP_CLOSE_PAREN);
4894	return ife;
4895	}
4896	else if (peek_ident (id: "with"))
4897	{
4898	eat_ident (s: "with");
4899	with_expr *withe = new with_expr (token->src_loc);
4900	/* Parse (with c-expr expr) as (if-with (true) expr). */
4901	withe->with = parse_c_expr (start: CPP_OPEN_BRACE);
4902	withe->with->nr_stmts = 0;
4903	withe->subexpr = parse_result (result, matcher);
4904	eat_token (tk: CPP_CLOSE_PAREN);
4905	return withe;
4906	}
4907	else if (peek_ident (id: "switch"))
4908	{
4909	token = eat_ident (s: "switch");
4910	location_t ifloc = eat_token (tk: CPP_OPEN_PAREN)->src_loc;
4911	eat_ident (s: "if");
4912	if_expr *ife = new if_expr (ifloc);
4913	operand *res = ife;
4914	ife->cond = parse_c_expr (start: CPP_OPEN_PAREN);
4915	if (peek ()->type == CPP_OPEN_PAREN)
4916	ife->trueexpr = parse_result (result, matcher);
4917	else
4918	ife->trueexpr = parse_op ();
4919	eat_token (tk: CPP_CLOSE_PAREN);
4920	if (peek ()->type != CPP_OPEN_PAREN
4921	|| !peek_ident (id: "if", num: 2))
4922	fatal_at (tk: token, msg: "switch can be implemented with a single if");
4923	while (peek ()->type != CPP_CLOSE_PAREN)
4924	{
4925	if (peek ()->type == CPP_OPEN_PAREN)
4926	{
4927	if (peek_ident (id: "if", num: 2))
4928	{
4929	ifloc = eat_token (tk: CPP_OPEN_PAREN)->src_loc;
4930	eat_ident (s: "if");
4931	ife->falseexpr = new if_expr (ifloc);
4932	ife = as_a <if_expr *> (p: ife->falseexpr);
4933	ife->cond = parse_c_expr (start: CPP_OPEN_PAREN);
4934	if (peek ()->type == CPP_OPEN_PAREN)
4935	ife->trueexpr = parse_result (result, matcher);
4936	else
4937	ife->trueexpr = parse_op ();
4938	if (peek ()->type == CPP_OPEN_PAREN)
4939	fatal_at (tk: peek(), msg: "if inside switch cannot have an else");
4940	eat_token (tk: CPP_CLOSE_PAREN);
4941	}
4942	else
4943	{
4944	/* switch default clause */
4945	ife->falseexpr = parse_result (result, matcher);
4946	eat_token (tk: CPP_CLOSE_PAREN);
4947	return res;
4948	}
4949	}
4950	else
4951	{
4952	/* switch default clause */
4953	ife->falseexpr = parse_op ();
4954	eat_token (tk: CPP_CLOSE_PAREN);
4955	return res;
4956	}
4957	}
4958	eat_token (tk: CPP_CLOSE_PAREN);
4959	return res;
4960	}
4961	else
4962	{
4963	operand *op = result;
4964	if (!matcher)
4965	op = parse_expr ();
4966	eat_token (tk: CPP_CLOSE_PAREN);
4967	return op;
4968	}
4969	}
4970
4971	/* Parse
4972	simplify = 'simplify' <expr> <result-op>
4973	or
4974	match = 'match' <ident> <expr> [<result-op>]
4975	and fill SIMPLIFIERS with the results. */
4976
4977	void
4978	parser::parse_simplify (simplify::simplify_kind kind,
4979	vec<simplify *>& simplifiers, predicate_id *matcher,
4980	operand *result)
4981	{
4982	/* Reset the capture map. */
4983	if (!capture_ids)
4984	capture_ids = new cid_map_t;
4985	/* Reset oper_lists and set. */
4986	hash_set <user_id *> olist;
4987	oper_lists_set = &olist;
4988	oper_lists = vNULL;
4989
4990	const cpp_token *loc = peek ();
4991	parsing_match_operand = true;
4992	class operand *match = parse_op ();
4993	finish_match_operand (match);
4994	parsing_match_operand = false;
4995	if (match->type == operand::OP_CAPTURE && !matcher)
4996	fatal_at (tk: loc, msg: "outermost expression cannot be captured");
4997	if (match->type == operand::OP_EXPR
4998	&& is_a <predicate_id *> (p: as_a <expr *> (p: match)->operation))
4999	fatal_at (tk: loc, msg: "outermost expression cannot be a predicate");
5000
5001	/* Splice active_ifs onto result and continue parsing the
5002	"then" expr. */
5003	if_expr *active_if = NULL;
5004	for (int i = active_ifs.length (); i > 0; --i)
5005	{
5006	if_expr *ifc = new if_expr (active_ifs[i-1]->location);
5007	ifc->cond = active_ifs[i-1];
5008	ifc->trueexpr = active_if;
5009	active_if = ifc;
5010	}
5011	if_expr *outermost_if = active_if;
5012	while (active_if && active_if->trueexpr)
5013	active_if = as_a <if_expr *> (p: active_if->trueexpr);
5014
5015	const cpp_token *token = peek ();
5016
5017	/* If this if is immediately closed then it is part of a predicate
5018	definition. Push it. */
5019	if (token->type == CPP_CLOSE_PAREN)
5020	{
5021	if (!matcher)
5022	fatal_at (tk: token, msg: "expected transform expression");
5023	if (active_if)
5024	{
5025	active_if->trueexpr = result;
5026	result = outermost_if;
5027	}
5028	push_simplify (kind, simplifiers, match, result);
5029	return;
5030	}
5031
5032	operand *tem = parse_result (result, matcher);
5033	if (active_if)
5034	{
5035	active_if->trueexpr = tem;
5036	result = outermost_if;
5037	}
5038	else
5039	result = tem;
5040
5041	push_simplify (kind, simplifiers, match, result);
5042	}
5043
5044	/* Parsing of the outer control structures. */
5045
5046	/* Parse a for expression
5047	for = '(' 'for' <subst>... <pattern> ')'
5048	subst = <ident> '(' <ident>... ')' */
5049
5050	void
5051	parser::parse_for (location_t)
5052	{
5053	auto_vec<const cpp_token *> user_id_tokens;
5054	vec<user_id *> user_ids = vNULL;
5055	const cpp_token *token;
5056	unsigned min_n_opers = 0, max_n_opers = 0;
5057
5058	while (1)
5059	{
5060	token = peek ();
5061	if (token->type != CPP_NAME)
5062	break;
5063
5064	/* Insert the user defined operators into the operator hash. */
5065	const char *id = get_ident ();
5066	if (get_operator (id, allow_null: true) != NULL)
5067	fatal_at (tk: token, msg: "operator already defined");
5068	user_id *op = new user_id (id);
5069	id_base **slot = operators->find_slot_with_hash (comparable: op, hash: op->hashval, insert: INSERT);
5070	*slot = op;
5071	user_ids.safe_push (obj: op);
5072	user_id_tokens.safe_push (obj: token);
5073
5074	eat_token (tk: CPP_OPEN_PAREN);
5075
5076	int arity = -1;
5077	while ((token = peek_ident ()) != 0)
5078	{
5079	const char *oper = get_ident ();
5080	id_base *idb = get_operator (id: oper, allow_null: true);
5081	if (idb == NULL)
5082	fatal_at (tk: token, msg: "no such operator '%s'", oper);
5083
5084	if (arity == -1)
5085	arity = idb->nargs;
5086	else if (idb->nargs == -1)
5087	;
5088	else if (idb->nargs != arity)
5089	fatal_at (tk: token, msg: "operator '%s' with arity %d does not match "
5090	"others with arity %d", oper, idb->nargs, arity);
5091
5092	user_id *p = dyn_cast<user_id *> (p: idb);
5093	if (p)
5094	{
5095	if (p->is_oper_list)
5096	op->substitutes.safe_splice (src: p->substitutes);
5097	else
5098	fatal_at (tk: token, msg: "iterator cannot be used as operator-list");
5099	}
5100	else
5101	op->substitutes.safe_push (obj: idb);
5102	}
5103	op->nargs = arity;
5104	token = expect (tk: CPP_CLOSE_PAREN);
5105
5106	unsigned nsubstitutes = op->substitutes.length ();
5107	if (nsubstitutes == 0)
5108	fatal_at (tk: token, msg: "A user-defined operator must have at least "
5109	"one substitution");
5110	if (max_n_opers == 0)
5111	{
5112	min_n_opers = nsubstitutes;
5113	max_n_opers = nsubstitutes;
5114	}
5115	else
5116	{
5117	if (nsubstitutes % min_n_opers != 0
5118	&& min_n_opers % nsubstitutes != 0)
5119	fatal_at (tk: token, msg: "All user-defined identifiers must have a "
5120	"multiple number of operator substitutions of the "
5121	"smallest number of substitutions");
5122	if (nsubstitutes < min_n_opers)
5123	min_n_opers = nsubstitutes;
5124	else if (nsubstitutes > max_n_opers)
5125	max_n_opers = nsubstitutes;
5126	}
5127	}
5128
5129	unsigned n_ids = user_ids.length ();
5130	if (n_ids == 0)
5131	fatal_at (tk: token, msg: "for requires at least one user-defined identifier");
5132
5133	token = peek ();
5134	if (token->type == CPP_CLOSE_PAREN)
5135	fatal_at (tk: token, msg: "no pattern defined in for");
5136
5137	active_fors.safe_push (obj: user_ids);
5138	while (1)
5139	{
5140	token = peek ();
5141	if (token->type == CPP_CLOSE_PAREN)
5142	break;
5143	parse_pattern ();
5144	}
5145	active_fors.pop ();
5146
5147	/* Remove user-defined operators from the hash again. */
5148	for (unsigned i = 0; i < user_ids.length (); ++i)
5149	{
5150	if (!user_ids[i]->used)
5151	warning_at (tk: user_id_tokens[i],
5152	msg: "operator %s defined but not used", user_ids[i]->id);
5153	operators->remove_elt (value: user_ids[i]);
5154	}
5155	}
5156
5157	/* Parse an identifier associated with a list of operators.
5158	oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
5159
5160	void
5161	parser::parse_operator_list (location_t)
5162	{
5163	const cpp_token *token = peek ();
5164	const char *id = get_ident ();
5165
5166	if (get_operator (id, allow_null: true) != 0)
5167	fatal_at (tk: token, msg: "operator %s already defined", id);
5168
5169	user_id *op = new user_id (id, true);
5170	int arity = -1;
5171
5172	while ((token = peek_ident ()) != 0)
5173	{
5174	token = peek ();
5175	const char *oper = get_ident ();
5176	id_base *idb = get_operator (id: oper, allow_null: true);
5177
5178	if (idb == 0)
5179	fatal_at (tk: token, msg: "no such operator '%s'", oper);
5180
5181	if (arity == -1)
5182	arity = idb->nargs;
5183	else if (idb->nargs == -1)
5184	;
5185	else if (arity != idb->nargs)
5186	fatal_at (tk: token, msg: "operator '%s' with arity %d does not match "
5187	"others with arity %d", oper, idb->nargs, arity);
5188
5189	/* We allow composition of multiple operator lists. */
5190	if (user_id *p = dyn_cast<user_id *> (p: idb))
5191	op->substitutes.safe_splice (src: p->substitutes);
5192	else
5193	op->substitutes.safe_push (obj: idb);
5194	}
5195
5196	// Check that there is no junk after id-list
5197	token = peek();
5198	if (token->type != CPP_CLOSE_PAREN)
5199	fatal_at (tk: token, msg: "expected identifier got %s", cpp_type2name (token->type, flags: 0));
5200
5201	if (op->substitutes.length () == 0)
5202	fatal_at (tk: token, msg: "operator-list cannot be empty");
5203
5204	op->nargs = arity;
5205	id_base **slot = operators->find_slot_with_hash (comparable: op, hash: op->hashval, insert: INSERT);
5206	*slot = op;
5207	}
5208
5209	/* Parse an outer if expression.
5210	if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
5211
5212	void
5213	parser::parse_if (location_t)
5214	{
5215	c_expr *ifexpr = parse_c_expr (start: CPP_OPEN_PAREN);
5216
5217	const cpp_token *token = peek ();
5218	if (token->type == CPP_CLOSE_PAREN)
5219	fatal_at (tk: token, msg: "no pattern defined in if");
5220
5221	active_ifs.safe_push (obj: ifexpr);
5222	while (1)
5223	{
5224	token = peek ();
5225	if (token->type == CPP_CLOSE_PAREN)
5226	break;
5227
5228	parse_pattern ();
5229	}
5230	active_ifs.pop ();
5231	}
5232
5233	/* Parse a list of predefined predicate identifiers.
5234	preds = '(' 'define_predicates' <ident>... ')' */
5235
5236	void
5237	parser::parse_predicates (location_t)
5238	{
5239	do
5240	{
5241	const cpp_token *token = peek ();
5242	if (token->type != CPP_NAME)
5243	break;
5244
5245	add_predicate (id: get_ident ());
5246	}
5247	while (1);
5248	}
5249
5250	/* Parse outer control structures.
5251	pattern = <preds>|<for>|<if>|<simplify>|<match> */
5252
5253	void
5254	parser::parse_pattern ()
5255	{
5256	/* All clauses start with '('. */
5257	eat_token (tk: CPP_OPEN_PAREN);
5258	const cpp_token *token = peek ();
5259	const char *id = get_ident ();
5260	if (strcmp (s1: id, s2: "simplify") == 0)
5261	{
5262	parse_simplify (kind: simplify::SIMPLIFY, simplifiers, NULL, NULL);
5263	capture_ids = NULL;
5264	}
5265	else if (strcmp (s1: id, s2: "match") == 0)
5266	{
5267	bool with_args = false;
5268	location_t e_loc = peek ()->src_loc;
5269	if (peek ()->type == CPP_OPEN_PAREN)
5270	{
5271	eat_token (tk: CPP_OPEN_PAREN);
5272	with_args = true;
5273	}
5274	const char *name = get_ident ();
5275	id_base *id1 = get_operator (id: name);
5276	predicate_id *p;
5277	if (!id1)
5278	{
5279	p = add_predicate (id: name);
5280	user_predicates.safe_push (obj: p);
5281	}
5282	else if ((p = dyn_cast <predicate_id *> (p: id1)))
5283	;
5284	else
5285	fatal_at (tk: token, msg: "cannot add a match to a non-predicate ID");
5286	/* Parse (match <id> <arg>... (match-expr)) here. */
5287	expr *e = NULL;
5288	if (with_args)
5289	{
5290	capture_ids = new cid_map_t;
5291	e = new expr (p, e_loc);
5292	while (peek ()->type == CPP_ATSIGN)
5293	e->append_op (op: parse_capture (NULL, require_existing: false));
5294	eat_token (tk: CPP_CLOSE_PAREN);
5295	}
5296	if (p->nargs != -1
5297	&& ((e && e->ops.length () != (unsigned)p->nargs)
5298	|| (!e && p->nargs != 0)))
5299	fatal_at (tk: token, msg: "non-matching number of match operands");
5300	p->nargs = e ? e->ops.length () : 0;
5301	parse_simplify (kind: simplify::MATCH, simplifiers&: p->matchers, matcher: p, result: e);
5302	capture_ids = NULL;
5303	}
5304	else if (strcmp (s1: id, s2: "for") == 0)
5305	parse_for (token->src_loc);
5306	else if (strcmp (s1: id, s2: "if") == 0)
5307	parse_if (token->src_loc);
5308	else if (strcmp (s1: id, s2: "define_predicates") == 0)
5309	{
5310	if (active_ifs.length () > 0
5311	|| active_fors.length () > 0)
5312	fatal_at (tk: token, msg: "define_predicates inside if or for is not supported");
5313	parse_predicates (token->src_loc);
5314	}
5315	else if (strcmp (s1: id, s2: "define_operator_list") == 0)
5316	{
5317	if (active_ifs.length () > 0
5318	|| active_fors.length () > 0)
5319	fatal_at (tk: token, msg: "operator-list inside if or for is not supported");
5320	parse_operator_list (token->src_loc);
5321	}
5322	else
5323	fatal_at (tk: token, msg: "expected %s'simplify', 'match', 'for' or 'if'",
5324	active_ifs.length () == 0 && active_fors.length () == 0
5325	? "'define_predicates', " : "");
5326
5327	eat_token (tk: CPP_CLOSE_PAREN);
5328	}
5329
5330	/* Helper for finish_match_operand, collecting captures of OP in CPTS
5331	recursively. */
5332
5333	static void
5334	walk_captures (operand *op, vec<vec<capture *> > &cpts)
5335	{
5336	if (! op)
5337	return;
5338
5339	if (capture *c = dyn_cast <capture *> (p: op))
5340	{
5341	cpts[c->where].safe_push (obj: c);
5342	walk_captures (op: c->what, cpts);
5343	}
5344	else if (expr *e = dyn_cast <expr *> (p: op))
5345	for (unsigned i = 0; i < e->ops.length (); ++i)
5346	walk_captures (op: e->ops[i], cpts);
5347	}
5348
5349	/* Finish up OP which is a match operand. */
5350
5351	void
5352	parser::finish_match_operand (operand *op)
5353	{
5354	/* Look for matching captures, diagnose mis-uses of @@ and apply
5355	early lowering and distribution of value_match. */
5356	auto_vec<vec<capture *> > cpts;
5357	cpts.safe_grow_cleared (len: capture_ids->elements (), exact: true);
5358	walk_captures (op, cpts);
5359	for (unsigned i = 0; i < cpts.length (); ++i)
5360	{
5361	capture *value_match = NULL;
5362	for (unsigned j = 0; j < cpts[i].length (); ++j)
5363	{
5364	if (cpts[i][j]->value_match)
5365	{
5366	if (value_match)
5367	fatal_at (loc: cpts[i][j]->location, msg: "duplicate @@");
5368	value_match = cpts[i][j];
5369	}
5370	}
5371	if (cpts[i].length () == 1 && value_match)
5372	fatal_at (loc: value_match->location, msg: "@@ without a matching capture");
5373	if (value_match)
5374	{
5375	/* Duplicate prevailing capture with the existing ID, create
5376	a fake ID and rewrite all captures to use it. This turns
5377	@@1 into @__<newid>@1 and @1 into @__<newid>. */
5378	value_match->what = new capture (value_match->location,
5379	value_match->where,
5380	value_match->what, false);
5381	/* Create a fake ID and rewrite all captures to use it. */
5382	unsigned newid = get_internal_capture_id ();
5383	for (unsigned j = 0; j < cpts[i].length (); ++j)
5384	{
5385	cpts[i][j]->where = newid;
5386	cpts[i][j]->value_match = true;
5387	}
5388	}
5389	cpts[i].release ();
5390	}
5391	}
5392
5393	/* Main entry of the parser. Repeatedly parse outer control structures. */
5394
5395	parser::parser (cpp_reader *r_, bool gimple_)
5396	{
5397	r = r_;
5398	gimple = gimple_;
5399	active_ifs = vNULL;
5400	active_fors = vNULL;
5401	simplifiers = vNULL;
5402	oper_lists_set = NULL;
5403	oper_lists = vNULL;
5404	capture_ids = NULL;
5405	user_predicates = vNULL;
5406	parsing_match_operand = false;
5407	last_id = 0;
5408
5409	const cpp_token *token = next ();
5410	while (token->type != CPP_EOF)
5411	{
5412	_cpp_backup_tokens (r, 1);
5413	parse_pattern ();
5414	token = next ();
5415	}
5416	}
5417
5418
5419	/* Helper for the linemap code. */
5420
5421	static size_t
5422	round_alloc_size (size_t s)
5423	{
5424	return s;
5425	}
5426
5427
5428	/* Construct and display the help menu. */
5429
5430	static void
5431	usage ()
5432	{
5433	const char *usage = "Usage:\n"
5434	" %s [--gimple|--generic] [-v[v]] <input>\n"
5435	" %s [options] [--include=FILE] --header=FILE <input> <output>...\n";
5436	fprintf (stderr, format: usage, progname, progname);
5437	}
5438
5439	/* Write out the correct include to the match-head fle containing the helper
5440	files. */
5441
5442	static void
5443	write_header_includes (bool gimple, FILE *header_file)
5444	{
5445	if (gimple)
5446	fprintf (stream: header_file, format: "#include \"gimple-match-head.cc\"\n");
5447	else
5448	fprintf (stream: header_file, format: "#include \"generic-match-head.cc\"\n");
5449	}
5450
5451	/* The genmatch generator program. It reads from a pattern description
5452	and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5453
5454	int
5455	main (int argc, char **argv)
5456	{
5457	cpp_reader *r;
5458
5459	progname = "genmatch";
5460
5461	bool gimple = true;
5462	char *s_header_file = NULL;
5463	char *s_include_file = NULL;
5464	auto_vec <char *> files;
5465	char *input = NULL;
5466	int last_file = argc - 1;
5467	for (int i = argc - 1; i >= 1; --i)
5468	{
5469	if (strcmp (s1: argv[i], s2: "--gimple") == 0)
5470	gimple = true;
5471	else if (strcmp (s1: argv[i], s2: "--generic") == 0)
5472	gimple = false;
5473	else if (strncmp (s1: argv[i], s2: "--header=", n: 9) == 0)
5474	s_header_file = &argv[i][9];
5475	else if (strncmp (s1: argv[i], s2: "--include=", n: 10) == 0)
5476	s_include_file = &argv[i][10];
5477	else if (strcmp (s1: argv[i], s2: "-v") == 0)
5478	verbose = 1;
5479	else if (strcmp (s1: argv[i], s2: "-vv") == 0)
5480	verbose = 2;
5481	else if (strncmp (s1: argv[i], s2: "--", n: 2) != 0 && last_file-- == i)
5482	files.safe_push (obj: argv[i]);
5483	else
5484	{
5485	usage ();
5486	return 1;
5487	}
5488	}
5489
5490	/* Validate if the combinations are valid. */
5491	if ((files.length () > 1 && !s_header_file) || files.is_empty ())
5492	{
5493	usage ();
5494	return 1;
5495	}
5496
5497	if (!s_include_file)
5498	s_include_file = s_header_file;
5499
5500	/* Input file is the last in the reverse list. */
5501	input = files.pop ();
5502
5503	line_table = XCNEW (class line_maps);
5504	linemap_init (set: line_table, builtin_location: 0);
5505	line_table->m_reallocator = xrealloc;
5506	line_table->m_round_alloc_size = round_alloc_size;
5507
5508	r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
5509	cpp_callbacks *cb = cpp_get_callbacks (r);
5510	cb->diagnostic = diagnostic_cb;
5511
5512	/* Add the build directory to the #include "" search path. */
5513	cpp_dir *dir = XCNEW (cpp_dir);
5514	dir->name = getpwd ();
5515	if (!dir->name)
5516	dir->name = ASTRDUP (".");
5517	cpp_set_include_chains (r, dir, NULL, false);
5518
5519	if (!cpp_read_main_file (r, input))
5520	return 1;
5521	cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
5522	cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
5523
5524	null_id = new id_base (id_base::NULL_ID, "null");
5525
5526	/* Pre-seed operators. */
5527	operators = new hash_table<id_base> (1024);
5528	#define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5529	add_operator (SYM, # SYM, # TYPE, NARGS);
5530	#define END_OF_BASE_TREE_CODES
5531	#include "tree.def"
5532	#undef END_OF_BASE_TREE_CODES
5533	#undef DEFTREECODE
5534
5535	/* Pre-seed builtin functions.
5536	??? Cannot use N (name) as that is targetm.emultls.get_address
5537	for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5538	#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5539	add_function (ENUM, "CFN_" # ENUM);
5540	#include "builtins.def"
5541
5542	#define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5543	add_function (IFN_##CODE, "CFN_" #CODE);
5544	#include "internal-fn.def"
5545
5546	/* Parse ahead! */
5547	parser p (r, gimple);
5548
5549	/* Create file buffers. */
5550	int n_parts = files.is_empty () ? 1 : files.length ();
5551	auto_vec <FILE *> parts (n_parts);
5552	if (files.is_empty ())
5553	{
5554	parts.quick_push (stdout);
5555	write_header (stdout, head: s_include_file);
5556	write_header_includes (gimple, stdout);
5557	write_header_declarations (gimple, stdout);
5558	}
5559	else
5560	{
5561	for (char *s_file : files)
5562	{
5563	parts.quick_push (fopen (s_file, "w"));
5564	write_header (f: parts.last (), head: s_include_file);
5565	}
5566
5567	header_file = fopen (s_header_file, "w");
5568	fprintf (stream: header_file, format: "#ifndef GCC_GIMPLE_MATCH_AUTO_H\n"
5569	"#define GCC_GIMPLE_MATCH_AUTO_H\n");
5570	write_header_includes (gimple, header_file);
5571	write_header_declarations (gimple, f: header_file);
5572	}
5573
5574	/* Go over all predicates defined with patterns and perform
5575	lowering and code generation. */
5576	for (unsigned i = 0; i < p.user_predicates.length (); ++i)
5577	{
5578	predicate_id *pred = p.user_predicates[i];
5579	lower (simplifiers&: pred->matchers, gimple);
5580
5581	if (verbose == 2)
5582	for (unsigned j = 0; j < pred->matchers.length (); ++j)
5583	print_matches (s: pred->matchers[j]);
5584
5585	decision_tree dt;
5586	for (unsigned j = 0; j < pred->matchers.length (); ++j)
5587	dt.insert (s: pred->matchers[j], pattern_no: j);
5588
5589	if (verbose == 2)
5590	dt.print (stderr);
5591
5592	/* Cycle the file buffers. */
5593	FILE *f = choose_output (parts);
5594
5595	write_predicate (f, p: pred, dt, gimple);
5596	}
5597
5598	/* Lower the main simplifiers and generate code for them. */
5599	lower (simplifiers&: p.simplifiers, gimple);
5600
5601	if (verbose == 2)
5602	for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5603	print_matches (s: p.simplifiers[i]);
5604
5605	decision_tree dt;
5606	for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5607	dt.insert (s: p.simplifiers[i], pattern_no: i);
5608
5609	if (verbose == 2)
5610	dt.print (stderr);
5611
5612	dt.gen (files&: parts, gimple);
5613
5614	define_dump_logs (gimple, f: choose_output (parts));
5615
5616	for (FILE *f : parts)
5617	{
5618	fprintf (stream: f, format: "#pragma GCC diagnostic pop\n");
5619	fclose (stream: f);
5620	}
5621
5622	if (header_file)
5623	{
5624	fprintf (stream: header_file, format: "\n#endif /* GCC_GIMPLE_MATCH_AUTO_H. */\n");
5625	fclose (stream: header_file);
5626	}
5627
5628	/* Finalize. */
5629	cpp_finish (r, NULL);
5630	cpp_destroy (r);
5631
5632	delete operators;
5633
5634	return 0;
5635	}
5636