Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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