Bug Summary

File:build/gcc/genmatch.cc
Warning:line 1884, column 3
Potential leak of memory pointed to by 'n'

Annotated Source Code

Press '?' to see keyboard shortcuts

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