/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c

Bug Summary

File:	build/gcc/genmatch.c
Warning:	line 2249, column 2 Value stored to 'opr' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name genmatch.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /usr/lib64/clang/11.0.0 -D IN_GCC -D HAVE_CONFIG_H -D GENERATOR_FILE -I . -I build -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/build -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/10/../../../../include/c++/10/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib64/clang/11.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-01-16-135054-17580-1/report-W4UAd7.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c

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