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