Bug Summary

File:build/gcc/genmatch.c
Warning:line 2250, 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 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -resource-dir /usr/lib64/clang/13.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/11/../../../../include/c++/11 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/backward -internal-isystem /usr/lib64/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../x86_64-suse-linux/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 -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-11-20-133755-20252-1/report-wIs7Xo.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 && startswith (id, "IFN_"))
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 && startswith (id, "BUILT_IN_"))
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 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 && ((is_a <capture *> (e->ops[0])
1262 && as_a <capture *> (e->ops[0])->what
1263 && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1264 && as_a <expr *>
1265 (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1266 || (is_a <expr *> (e->ops[0])
1267 && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1268 {
1269 ne = new expr (e);
1270 for (unsigned j = 0; j < result[i].length (); ++j)
1271 ne->append_op (result[i][j]);
1272 if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1273 {
1274 expr *ocmp = as_a <expr *> (c->what);
1275 expr *cmp = new expr (ocmp);
1276 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1277 cmp->append_op (ocmp->ops[j]);
1278 cmp->is_generic = true;
1279 ne->ops[0] = new capture (c->location, c->where, cmp,
1280 c->value_match);
1281 }
1282 else
1283 {
1284 expr *ocmp = as_a <expr *> (ne->ops[0]);
1285 expr *cmp = new expr (ocmp);
1286 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1287 cmp->append_op (ocmp->ops[j]);
1288 cmp->is_generic = true;
1289 ne->ops[0] = cmp;
1290 }
1291 ro.safe_push (ne);
1292 }
1293 }
1294
1295 return ro;
1296}
1297
1298/* Lower the compare operand of COND_EXPRs to a
1299 GENERIC and a GIMPLE variant. */
1300
1301static void
1302lower_cond (simplify *s, vec<simplify *>& simplifiers)
1303{
1304 vec<operand *> matchers = lower_cond (s->match);
1305 for (unsigned i = 0; i < matchers.length (); ++i)
1306 {
1307 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1308 s->for_vec, s->capture_ids);
1309 ns->for_subst_vec.safe_splice (s->for_subst_vec);
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 (auto s: simplifiers)
1548 lower_opt (s, out_simplifiers);
1549
1550 simplifiers.truncate (0);
1551 for (auto s: out_simplifiers)
1552 lower_commutative (s, simplifiers);
1553
1554 /* Lower for needs to happen before lowering cond
1555 to support (for cnd (cond vec_cond)). This is
1556 safe as substitution delay does not happen for
1557 cond or vec_cond. */
1558 out_simplifiers.truncate (0);
1559 for (auto s: simplifiers)
1560 lower_for (s, out_simplifiers);
1561
1562 simplifiers.truncate (0);
1563 if (gimple)
1564 for (auto s: out_simplifiers)
1565 lower_cond (s, simplifiers);
1566 else
1567 simplifiers.safe_splice (out_simplifiers);
1568}
1569
1570
1571
1572
1573/* The decision tree built for generating GIMPLE and GENERIC pattern
1574 matching code. It represents the 'match' expression of all
1575 simplifies and has those as its leafs. */
1576
1577class dt_simplify;
1578
1579/* A hash-map collecting semantically equivalent leafs in the decision
1580 tree for splitting out to separate functions. */
1581struct sinfo
1582{
1583 dt_simplify *s;
1584
1585 const char *fname;
1586 unsigned cnt;
1587};
1588
1589struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1590 sinfo *>
1591{
1592 static inline hashval_t hash (const key_type &);
1593 static inline bool equal_keys (const key_type &, const key_type &);
1594 template <typename T> static inline void remove (T &) {}
1595};
1596
1597typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1598 sinfo_map_t;
1599
1600/* Current simplifier ID we are processing during insertion into the
1601 decision tree. */
1602static unsigned current_id;
1603
1604/* Decision tree base class, used for DT_NODE. */
1605
1606class dt_node
1607{
1608public:
1609 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1610
1611 enum dt_type type;
1612 unsigned level;
1613 dt_node *parent;
1614 vec<dt_node *> kids;
1615
1616 /* Statistics. */
1617 unsigned num_leafs;
1618 unsigned total_size;
1619 unsigned max_level;
1620
1621 dt_node (enum dt_type type_, dt_node *parent_)
1622 : type (type_), level (0), parent (parent_), kids (vNULL) {}
1623
1624 dt_node *append_node (dt_node *);
1625 dt_node *append_op (operand *, dt_node *parent, unsigned pos);
1626 dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
1627 dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
1628 unsigned pos);
1629 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1630
1631 virtual void gen (FILE *, int, bool, int) {}
1632
1633 void gen_kids (FILE *, int, bool, int);
1634 void gen_kids_1 (FILE *, int, bool, int,
1635 const vec<dt_operand *> &, const vec<dt_operand *> &,
1636 const vec<dt_operand *> &, const vec<dt_operand *> &,
1637 const vec<dt_operand *> &, const vec<dt_node *> &);
1638
1639 void analyze (sinfo_map_t &);
1640};
1641
1642/* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1643
1644class dt_operand : public dt_node
1645{
1646public:
1647 operand *op;
1648 dt_operand *match_dop;
1649 unsigned pos;
1650 bool value_match;
1651 unsigned for_id;
1652
1653 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1654 dt_operand *parent_, unsigned pos_)
1655 : dt_node (type, parent_), op (op_), match_dop (match_dop_),
1656 pos (pos_), value_match (false), for_id (current_id) {}
1657
1658 void gen (FILE *, int, bool, int);
1659 unsigned gen_predicate (FILE *, int, const char *, bool);
1660 unsigned gen_match_op (FILE *, int, const char *, bool);
1661
1662 unsigned gen_gimple_expr (FILE *, int, int);
1663 unsigned gen_generic_expr (FILE *, int, const char *);
1664
1665 char *get_name (char *);
1666 void gen_opname (char *, unsigned);
1667};
1668
1669/* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1670
1671class dt_simplify : public dt_node
1672{
1673public:
1674 simplify *s;
1675 unsigned pattern_no;
1676 dt_operand **indexes;
1677 sinfo *info;
1678
1679 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1680 : dt_node (DT_SIMPLIFY, NULLnullptr), s (s_), pattern_no (pattern_no_),
1681 indexes (indexes_), info (NULLnullptr) {}
1682
1683 void gen_1 (FILE *, int, bool, operand *);
1684 void gen (FILE *f, int, bool, int);
1685};
1686
1687template<>
1688template<>
1689inline bool
1690is_a_helper <dt_operand *>::test (dt_node *n)
1691{
1692 return (n->type == dt_node::DT_OPERAND
1693 || n->type == dt_node::DT_MATCH
1694 || n->type == dt_node::DT_TRUE);
1695}
1696
1697template<>
1698template<>
1699inline bool
1700is_a_helper <dt_simplify *>::test (dt_node *n)
1701{
1702 return n->type == dt_node::DT_SIMPLIFY;
1703}
1704
1705
1706
1707/* A container for the actual decision tree. */
1708
1709class decision_tree
1710{
1711public:
1712 dt_node *root;
1713
1714 void insert (class simplify *, unsigned);
1715 void gen (FILE *f, bool gimple);
1716 void print (FILE *f = stderrstderr);
1717
1718 decision_tree () { root = new dt_node (dt_node::DT_NODE, NULLnullptr); }
1719
1720 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1721 unsigned pos = 0, dt_node *parent = 0);
1722 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1723 static bool cmp_node (dt_node *, dt_node *);
1724 static void print_node (dt_node *, FILE *f = stderrstderr, unsigned = 0);
1725};
1726
1727/* Compare two AST operands O1 and O2 and return true if they are equal. */
1728
1729bool
1730cmp_operand (operand *o1, operand *o2)
1731{
1732 if (!o1 || !o2 || o1->type != o2->type)
1733 return false;
1734
1735 if (o1->type == operand::OP_PREDICATE)
1736 {
1737 predicate *p1 = as_a<predicate *>(o1);
1738 predicate *p2 = as_a<predicate *>(o2);
1739 return p1->p == p2->p;
1740 }
1741 else if (o1->type == operand::OP_EXPR)
1742 {
1743 expr *e1 = static_cast<expr *>(o1);
1744 expr *e2 = static_cast<expr *>(o2);
1745 return (e1->operation == e2->operation
1746 && e1->is_generic == e2->is_generic);
1747 }
1748 else
1749 return false;
1750}
1751
1752/* Compare two decision tree nodes N1 and N2 and return true if they
1753 are equal. */
1754
1755bool
1756decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1757{
1758 if (!n1 || !n2 || n1->type != n2->type)
1759 return false;
1760
1761 if (n1 == n2)
1762 return true;
1763
1764 if (n1->type == dt_node::DT_TRUE)
1765 return false;
1766
1767 if (n1->type == dt_node::DT_OPERAND)
1768 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1769 (as_a<dt_operand *> (n2))->op);
1770 else if (n1->type == dt_node::DT_MATCH)
1771 return (((as_a<dt_operand *> (n1))->match_dop
1772 == (as_a<dt_operand *> (n2))->match_dop)
1773 && ((as_a<dt_operand *> (n1))->value_match
1774 == (as_a<dt_operand *> (n2))->value_match));
1775 return false;
1776}
1777
1778/* Search OPS for a decision tree node like P and return it if found. */
1779
1780dt_node *
1781decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1782{
1783 /* We can merge adjacent DT_TRUE. */
1784 if (p->type == dt_node::DT_TRUE
1785 && !ops.is_empty ()
1786 && ops.last ()->type == dt_node::DT_TRUE)
1787 return ops.last ();
1788 dt_operand *true_node = NULLnullptr;
1789 for (int i = ops.length () - 1; i >= 0; --i)
1790 {
1791 /* But we can't merge across DT_TRUE nodes as they serve as
1792 pattern order barriers to make sure that patterns apply
1793 in order of appearance in case multiple matches are possible. */
1794 if (ops[i]->type == dt_node::DT_TRUE)
1795 {
1796 if (! true_node
1797 || as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
1798 true_node = as_a <dt_operand *> (ops[i]);
1799 }
1800 if (decision_tree::cmp_node (ops[i], p))
1801 {
1802 /* Unless we are processing the same pattern or the blocking
1803 pattern is before the one we are going to merge with. */
1804 if (true_node
1805 && true_node->for_id != current_id
1806 && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
1807 {
1808 if (verbose >= 1)
1809 {
1810 location_t p_loc = 0;
1811 if (p->type == dt_node::DT_OPERAND)
1812 p_loc = as_a <dt_operand *> (p)->op->location;
1813 location_t op_loc = 0;
1814 if (ops[i]->type == dt_node::DT_OPERAND)
1815 op_loc = as_a <dt_operand *> (ops[i])->op->location;
1816 location_t true_loc = 0;
1817 true_loc = true_node->op->location;
1818 warning_at (p_loc,
1819 "failed to merge decision tree node");
1820 warning_at (op_loc,
1821 "with the following");
1822 warning_at (true_loc,
1823 "because of the following which serves as ordering "
1824 "barrier");
1825 }
1826 return NULLnullptr;
1827 }
1828 return ops[i];
1829 }
1830 }
1831 return NULLnullptr;
1832}
1833
1834/* Append N to the decision tree if it there is not already an existing
1835 identical child. */
1836
1837dt_node *
1838dt_node::append_node (dt_node *n)
1839{
1840 dt_node *kid;
1841
1842 kid = decision_tree::find_node (kids, n);
1843 if (kid)
1844 return kid;
1845
1846 kids.safe_push (n);
1847 n->level = this->level + 1;
1848
1849 return n;
1850}
1851
1852/* Append OP to the decision tree. */
1853
1854dt_node *
1855dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1856{
1857 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1858 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1859 return append_node (n);
1860}
1861
1862/* Append a DT_TRUE decision tree node. */
1863
1864dt_node *
1865dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
1866{
1867 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1868 dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
1869 return append_node (n);
1870}
1871
1872/* Append a DT_MATCH decision tree node. */
1873
1874dt_node *
1875dt_node::append_match_op (operand *op, dt_operand *match_dop,
1876 dt_node *parent, unsigned pos)
1877{
1878 dt_operand *parent_ = as_a<dt_operand *> (parent);
1879 dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
1880 return append_node (n);
1881}
1882
1883/* Append S to the decision tree. */
1884
1885dt_node *
1886dt_node::append_simplify (simplify *s, unsigned pattern_no,
1887 dt_operand **indexes)
1888{
1889 dt_simplify *s2;
1890 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1891 for (unsigned i = 0; i < kids.length (); ++i)
1892 if ((s2 = dyn_cast <dt_simplify *> (kids[i]))
1893 && (verbose >= 1
1894 || s->match->location != s2->s->match->location))
1895 {
1896 /* With a nested patters, it's hard to avoid these in order
1897 to keep match.pd rules relatively small. */
1898 warning_at (s->match->location, "duplicate pattern");
1899 warning_at (s2->s->match->location, "previous pattern defined here");
1900 print_operand (s->match, stderrstderr);
1901 fprintf (stderrstderr, "\n");
1902 }
1903 return append_node (n);
1904}
1905
1906/* Analyze the node and its children. */
1907
1908void
1909dt_node::analyze (sinfo_map_t &map)
1910{
1911 num_leafs = 0;
1912 total_size = 1;
1913 max_level = level;
1914
1915 if (type == DT_SIMPLIFY)
1916 {
1917 /* Populate the map of equivalent simplifies. */
1918 dt_simplify *s = as_a <dt_simplify *> (this);
1919 bool existed;
1920 sinfo *&si = map.get_or_insert (s, &existed);
1921 if (!existed)
1922 {
1923 si = new sinfo;
1924 si->s = s;
1925 si->cnt = 1;
1926 si->fname = NULLnullptr;
1927 }
1928 else
1929 si->cnt++;
1930 s->info = si;
1931 num_leafs = 1;
1932 return;
1933 }
1934
1935 for (unsigned i = 0; i < kids.length (); ++i)
1936 {
1937 kids[i]->analyze (map);
1938 num_leafs += kids[i]->num_leafs;
1939 total_size += kids[i]->total_size;
1940 max_level = MAX (max_level, kids[i]->max_level)((max_level) > (kids[i]->max_level) ? (max_level) : (kids
[i]->max_level))
;
1941 }
1942}
1943
1944/* Insert O into the decision tree and return the decision tree node found
1945 or created. */
1946
1947dt_node *
1948decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1949 unsigned pos, dt_node *parent)
1950{
1951 dt_node *q, *elm = 0;
1952
1953 if (capture *c = dyn_cast<capture *> (o))
1954 {
1955 unsigned capt_index = c->where;
1956
1957 if (indexes[capt_index] == 0)
1958 {
1959 if (c->what)
1960 q = insert_operand (p, c->what, indexes, pos, parent);
1961 else
1962 {
1963 q = elm = p->append_true_op (o, parent, pos);
1964 goto at_assert_elm;
1965 }
1966 // get to the last capture
1967 for (operand *what = c->what;
1968 what && is_a<capture *> (what);
1969 c = as_a<capture *> (what), what = c->what)
1970 ;
1971
1972 if (!c->what)
1973 {
1974 unsigned cc_index = c->where;
1975 dt_operand *match_op = indexes[cc_index];
1976
1977 dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
1978 elm = decision_tree::find_node (p->kids, &temp);
1979
1980 if (elm == 0)
1981 {
1982 dt_operand match (dt_node::DT_MATCH, 0, match_op, 0, 0);
1983 match.value_match = c->value_match;
1984 elm = decision_tree::find_node (p->kids, &match);
1985 }
1986 }
1987 else
1988 {
1989 dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
1990 elm = decision_tree::find_node (p->kids, &temp);
1991 }
1992
1993at_assert_elm:
1994 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"
, 1996, __FUNCTION__), 0 : 0))
1995 || 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"
, 1996, __FUNCTION__), 0 : 0))
1996 || 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"
, 1996, __FUNCTION__), 0 : 0))
;
1997 indexes[capt_index] = static_cast<dt_operand *> (elm);
1998 return q;
1999 }
2000 else
2001 {
2002 p = p->append_match_op (o, indexes[capt_index], parent, pos);
2003 as_a <dt_operand *>(p)->value_match = c->value_match;
2004 if (c->what)
2005 return insert_operand (p, c->what, indexes, 0, p);
2006 else
2007 return p;
2008 }
2009 }
2010 p = p->append_op (o, parent, pos);
2011 q = p;
2012
2013 if (expr *e = dyn_cast <expr *>(o))
2014 {
2015 for (unsigned i = 0; i < e->ops.length (); ++i)
2016 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
2017 }
2018
2019 return q;
2020}
2021
2022/* Insert S into the decision tree. */
2023
2024void
2025decision_tree::insert (class simplify *s, unsigned pattern_no)
2026{
2027 current_id = s->id;
2028 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1)((dt_operand * *) xcalloc ((s->capture_max + 1), sizeof (dt_operand
*)))
;
2029 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
2030 p->append_simplify (s, pattern_no, indexes);
2031}
2032
2033/* Debug functions to dump the decision tree. */
2034
2035DEBUG_FUNCTION__attribute__ ((__used__)) void
2036decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
2037{
2038 if (p->type == dt_node::DT_NODE)
2039 fprintf (f, "root");
2040 else
2041 {
2042 fprintf (f, "|");
2043 for (unsigned i = 0; i < indent; i++)
2044 fprintf (f, "-");
2045
2046 if (p->type == dt_node::DT_OPERAND)
2047 {
2048 dt_operand *dop = static_cast<dt_operand *>(p);
2049 print_operand (dop->op, f, true);
2050 }
2051 else if (p->type == dt_node::DT_TRUE)
2052 fprintf (f, "true");
2053 else if (p->type == dt_node::DT_MATCH)
2054 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
2055 else if (p->type == dt_node::DT_SIMPLIFY)
2056 {
2057 dt_simplify *s = static_cast<dt_simplify *> (p);
2058 fprintf (f, "simplify_%u { ", s->pattern_no);
2059 for (int i = 0; i <= s->s->capture_max; ++i)
2060 fprintf (f, "%p, ", (void *) s->indexes[i]);
2061 fprintf (f, " } ");
2062 }
2063 if (is_a <dt_operand *> (p))
2064 fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
2065 }
2066
2067 fprintf (stderrstderr, " (%p, %p), %u, %u\n",
2068 (void *) p, (void *) p->parent, p->level, p->kids.length ());
2069
2070 for (unsigned i = 0; i < p->kids.length (); ++i)
2071 decision_tree::print_node (p->kids[i], f, indent + 2);
2072}
2073
2074DEBUG_FUNCTION__attribute__ ((__used__)) void
2075decision_tree::print (FILE *f)
2076{
2077 return decision_tree::print_node (root, f);
2078}
2079
2080
2081/* For GENERIC we have to take care of wrapping multiple-used
2082 expressions with side-effects in save_expr and preserve side-effects
2083 of expressions with omit_one_operand. Analyze captures in
2084 match, result and with expressions and perform early-outs
2085 on the outermost match expression operands for cases we cannot
2086 handle. */
2087
2088class capture_info
2089{
2090public:
2091 capture_info (simplify *s, operand *, bool);
2092 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
2093 bool walk_result (operand *o, bool, operand *);
2094 void walk_c_expr (c_expr *);
2095
2096 struct cinfo
2097 {
2098 bool expr_p;
2099 bool cse_p;
2100 bool force_no_side_effects_p;
2101 bool force_single_use;
2102 bool cond_expr_cond_p;
2103 unsigned long toplevel_msk;
2104 unsigned match_use_count;
2105 unsigned result_use_count;
2106 unsigned same_as;
2107 capture *c;
2108 };
2109
2110 auto_vec<cinfo> info;
2111 unsigned long force_no_side_effects;
2112 bool gimple;
2113};
2114
2115/* Analyze captures in S. */
2116
2117capture_info::capture_info (simplify *s, operand *result, bool gimple_)
2118{
2119 gimple = gimple_;
2120
2121 expr *e;
2122 if (s->kind == simplify::MATCH)
2123 {
2124 force_no_side_effects = -1;
2125 return;
2126 }
2127
2128 force_no_side_effects = 0;
2129 info.safe_grow_cleared (s->capture_max + 1, true);
2130 for (int i = 0; i <= s->capture_max; ++i)
2131 info[i].same_as = i;
2132
2133 e = as_a <expr *> (s->match);
2134 for (unsigned i = 0; i < e->ops.length (); ++i)
2135 walk_match (e->ops[i], i,
2136 (i != 0 && *e->operation == COND_EXPR)
2137 || *e->operation == TRUTH_ANDIF_EXPR
2138 || *e->operation == TRUTH_ORIF_EXPR,
2139 i == 0 && *e->operation == COND_EXPR);
2140
2141 walk_result (s->result, false, result);
2142}
2143
2144/* Analyze captures in the match expression piece O. */
2145
2146void
2147capture_info::walk_match (operand *o, unsigned toplevel_arg,
2148 bool conditional_p, bool cond_expr_cond_p)
2149{
2150 if (capture *c = dyn_cast <capture *> (o))
2151 {
2152 unsigned where = c->where;
2153 info[where].match_use_count++;
2154 info[where].toplevel_msk |= 1 << toplevel_arg;
2155 info[where].force_no_side_effects_p |= conditional_p;
2156 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2157 if (!info[where].c)
2158 info[where].c = c;
2159 if (!c->what)
2160 return;
2161 /* Recurse to exprs and captures. */
2162 if (is_a <capture *> (c->what)
2163 || is_a <expr *> (c->what))
2164 walk_match (c->what, toplevel_arg, conditional_p, false);
2165 /* We need to look past multiple captures to find a captured
2166 expression as with conditional converts two captures
2167 can be collapsed onto the same expression. Also collect
2168 what captures capture the same thing. */
2169 while (c->what && is_a <capture *> (c->what))
2170 {
2171 c = as_a <capture *> (c->what);
2172 if (info[c->where].same_as != c->where
2173 && info[c->where].same_as != info[where].same_as)
2174 fatal_at (c->location, "cannot handle this collapsed capture");
2175 info[c->where].same_as = info[where].same_as;
2176 }
2177 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2178 expr *e;
2179 if (c->what
2180 && (e = dyn_cast <expr *> (c->what)))
2181 {
2182 /* Zero-operand expression captures like ADDR_EXPR@0 are
2183 similar as predicates -- if they are not mentioned in
2184 the result we have to force them to have no side-effects. */
2185 if (e->ops.length () != 0)
2186 info[where].expr_p = true;
2187 info[where].force_single_use |= e->force_single_use;
2188 }
2189 }
2190 else if (expr *e = dyn_cast <expr *> (o))
2191 {
2192 for (unsigned i = 0; i < e->ops.length (); ++i)
2193 {
2194 bool cond_p = conditional_p;
2195 bool expr_cond_p = false;
2196 if (i != 0 && *e->operation == COND_EXPR)
2197 cond_p = true;
2198 else if (*e->operation == TRUTH_ANDIF_EXPR
2199 || *e->operation == TRUTH_ORIF_EXPR)
2200 cond_p = true;
2201 if (i == 0
2202 && *e->operation == COND_EXPR)
2203 expr_cond_p = true;
2204 walk_match (e->ops[i], toplevel_arg, cond_p, expr_cond_p);
2205 }
2206 }
2207 else if (is_a <predicate *> (o))
2208 {
2209 /* Mark non-captured leafs toplevel arg for checking. */
2210 force_no_side_effects |= 1 << toplevel_arg;
2211 if (verbose >= 1
2212 && !gimple)
2213 warning_at (o->location,
2214 "forcing no side-effects on possibly lost leaf");
2215 }
2216 else
2217 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 2217, __FUNCTION__))
;
2218}
2219
2220/* Analyze captures in the result expression piece O. Return true
2221 if RESULT was visited in one of the children. Only visit
2222 non-if/with children if they are rooted on RESULT. */
2223
2224bool
2225capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2226{
2227 if (capture *c = dyn_cast <capture *> (o))
2228 {
2229 unsigned where = info[c->where].same_as;
2230 info[where].result_use_count++;
2231 /* If we substitute an expression capture we don't know
2232 which captures this will end up using (well, we don't
2233 compute that). Force the uses to be side-effect free
2234 which means forcing the toplevels that reach the
2235 expression side-effect free. */
2236 if (info[where].expr_p)
2237 force_no_side_effects |= info[where].toplevel_msk;
2238 /* Mark CSE capture uses as forced to have no side-effects. */
2239 if (c->what
2240 && is_a <expr *> (c->what))
2241 {
2242 info[where].cse_p = true;
2243 walk_result (c->what, true, result);
2244 }
2245 }
2246 else if (expr *e = dyn_cast <expr *> (o))
2247 {
2248 id_base *opr = e->operation;
2249 if (user_id *uid = dyn_cast <user_id *> (opr))
2250 opr = uid->substitutes[0];
Value stored to 'opr' is never read
2251 for (unsigned i = 0; i < e->ops.length (); ++i)
2252 {
2253 bool cond_p = conditional_p;
2254 if (i != 0 && *e->operation == COND_EXPR)
2255 cond_p = true;
2256 else if (*e->operation == TRUTH_ANDIF_EXPR
2257 || *e->operation == TRUTH_ORIF_EXPR)
2258 cond_p = true;
2259 walk_result (e->ops[i], cond_p, result);
2260 }
2261 }
2262 else if (if_expr *ie = dyn_cast <if_expr *> (o))
2263 {
2264 /* 'if' conditions should be all fine. */
2265 if (ie->trueexpr == result)
2266 {
2267 walk_result (ie->trueexpr, false, result);
2268 return true;
2269 }
2270 if (ie->falseexpr == result)
2271 {
2272 walk_result (ie->falseexpr, false, result);
2273 return true;
2274 }
2275 bool res = false;
2276 if (is_a <if_expr *> (ie->trueexpr)
2277 || is_a <with_expr *> (ie->trueexpr))
2278 res |= walk_result (ie->trueexpr, false, result);
2279 if (ie->falseexpr
2280 && (is_a <if_expr *> (ie->falseexpr)
2281 || is_a <with_expr *> (ie->falseexpr)))
2282 res |= walk_result (ie->falseexpr, false, result);
2283 return res;
2284 }
2285 else if (with_expr *we = dyn_cast <with_expr *> (o))
2286 {
2287 bool res = (we->subexpr == result);
2288 if (res
2289 || is_a <if_expr *> (we->subexpr)
2290 || is_a <with_expr *> (we->subexpr))
2291 res |= walk_result (we->subexpr, false, result);
2292 if (res)
2293 walk_c_expr (we->with);
2294 return res;
2295 }
2296 else if (c_expr *ce = dyn_cast <c_expr *> (o))
2297 walk_c_expr (ce);
2298 else
2299 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 2299, __FUNCTION__))
;
2300
2301 return false;
2302}
2303
2304/* Look for captures in the C expr E. */
2305
2306void
2307capture_info::walk_c_expr (c_expr *e)
2308{
2309 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2310 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2311 really escape through. */
2312 unsigned p_depth = 0;
2313 for (unsigned i = 0; i < e->code.length (); ++i)
2314 {
2315 const cpp_token *t = &e->code[i];
2316 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULLnullptr;
2317 id_base *id;
2318 if (t->type == CPP_NAME
2319 && (strcmp ((const char *)CPP_HASHNODE((cpp_hashnode *) (t->val.node.node))
2320 (t->val.node.node)((cpp_hashnode *) (t->val.node.node))->ident.str, "TREE_TYPE") == 0
2321 || strcmp ((const char *)CPP_HASHNODE((cpp_hashnode *) (t->val.node.node))
2322 (t->val.node.node)((cpp_hashnode *) (t->val.node.node))->ident.str, "TREE_CODE") == 0
2323 || strcmp ((const char *)CPP_HASHNODE((cpp_hashnode *) (t->val.node.node))
2324 (t->val.node.node)((cpp_hashnode *) (t->val.node.node))->ident.str, "TREE_REAL_CST") == 0
2325 || ((id = get_operator ((const char *)CPP_HASHNODE((cpp_hashnode *) (t->val.node.node))
2326 (t->val.node.node)((cpp_hashnode *) (t->val.node.node))->ident.str))
2327 && is_a <predicate_id *> (id)))
2328 && n->type == CPP_OPEN_PAREN)
2329 p_depth++;
2330 else if (t->type == CPP_CLOSE_PAREN
2331 && p_depth > 0)
2332 p_depth--;
2333 else if (p_depth == 0
2334 && t->type == CPP_ATSIGN
2335 && (n->type == CPP_NUMBER
2336 || n->type == CPP_NAME)
2337 && !(n->flags & PREV_WHITE(1 << 0)))
2338 {
2339 const char *id1;
2340 if (n->type == CPP_NUMBER)
2341 id1 = (const char *)n->val.str.text;
2342 else
2343 id1 = (const char *)CPP_HASHNODE (n->val.node.node)((cpp_hashnode *) (n->val.node.node))->ident.str;
2344 unsigned *where = e->capture_ids->get(id1);
2345 if (! where)
2346 fatal_at (n, "unknown capture id '%s'", id1);
2347 info[info[*where].same_as].force_no_side_effects_p = true;
2348 if (verbose >= 1
2349 && !gimple)
2350 warning_at (t, "capture escapes");
2351 }
2352 }
2353}
2354
2355
2356/* The current label failing the current matched pattern during
2357 code generation. */
2358static char *fail_label;
2359
2360/* Code generation off the decision tree and the refered AST nodes. */
2361
2362bool
2363is_conversion (id_base *op)
2364{
2365 return (*op == CONVERT_EXPR
2366 || *op == NOP_EXPR
2367 || *op == FLOAT_EXPR
2368 || *op == FIX_TRUNC_EXPR
2369 || *op == VIEW_CONVERT_EXPR);
2370}
2371
2372/* Get the type to be used for generating operand POS of OP from the
2373 various sources. */
2374
2375static const char *
2376get_operand_type (id_base *op, unsigned pos,
2377 const char *in_type,
2378 const char *expr_type,
2379 const char *other_oprnd_type)
2380{
2381 /* Generally operands whose type does not match the type of the
2382 expression generated need to know their types but match and
2383 thus can fall back to 'other_oprnd_type'. */
2384 if (is_conversion (op))
2385 return other_oprnd_type;
2386 else if (*op == REALPART_EXPR
2387 || *op == IMAGPART_EXPR)
2388 return other_oprnd_type;
2389 else if (is_a <operator_id *> (op)
2390 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2391 return other_oprnd_type;
2392 else if (*op == COND_EXPR
2393 && pos == 0)
2394 return "boolean_type_node";
2395 else if (startswith (op->id, "CFN_COND_"))
2396 {
2397 /* IFN_COND_* operands 1 and later by default have the same type
2398 as the result. The type of operand 0 needs to be specified
2399 explicitly. */
2400 if (pos > 0 && expr_type)
2401 return expr_type;
2402 else if (pos > 0 && in_type)
2403 return in_type;
2404 else
2405 return NULLnullptr;
2406 }
2407 else
2408 {
2409 /* Otherwise all types should match - choose one in order of
2410 preference. */
2411 if (expr_type)
2412 return expr_type;
2413 else if (in_type)
2414 return in_type;
2415 else
2416 return other_oprnd_type;
2417 }
2418}
2419
2420/* Generate transform code for an expression. */
2421
2422void
2423expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2424 int depth, const char *in_type, capture_info *cinfo,
2425 dt_operand **indexes, int)
2426{
2427 id_base *opr = operation;
2428 /* When we delay operator substituting during lowering of fors we
2429 make sure that for code-gen purposes the effects of each substitute
2430 are the same. Thus just look at that. */
2431 if (user_id *uid = dyn_cast <user_id *> (opr))
2432 opr = uid->substitutes[0];
2433
2434 bool conversion_p = is_conversion (opr);
2435 const char *type = expr_type;
2436 char optype[64];
2437 if (type)
2438 /* If there was a type specification in the pattern use it. */
2439 ;
2440 else if (conversion_p)
2441 /* For conversions we need to build the expression using the
2442 outer type passed in. */
2443 type = in_type;
2444 else if (*opr == REALPART_EXPR
2445 || *opr == IMAGPART_EXPR)
2446 {
2447 /* __real and __imag use the component type of its operand. */
2448 snprintf (optype, sizeof (optype), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2449 depth);
2450 type = optype;
2451 }
2452 else if (is_a <operator_id *> (opr)
2453 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2454 {
2455 /* comparisons use boolean_type_node (or what gets in), but
2456 their operands need to figure out the types themselves. */
2457 if (in_type)
2458 type = in_type;
2459 else
2460 {
2461 snprintf (optype, sizeof (optype), "boolean_type_node");
2462 type = optype;
2463 }
2464 in_type = NULLnullptr;
2465 }
2466 else if (*opr == COND_EXPR
2467 || *opr == VEC_COND_EXPR
2468 || startswith (opr->id, "CFN_COND_"))
2469 {
2470 /* Conditions are of the same type as their first alternative. */
2471 snprintf (optype, sizeof (optype), "TREE_TYPE (_o%d[1])", depth);
2472 type = optype;
2473 }
2474 else
2475 {
2476 /* Other operations are of the same type as their first operand. */
2477 snprintf (optype, sizeof (optype), "TREE_TYPE (_o%d[0])", depth);
2478 type = optype;
2479 }
2480 if (!type)
2481 fatal_at (location, "cannot determine type of operand");
2482
2483 fprintf_indent (f, indent, "{\n");
2484 indent += 2;
2485 fprintf_indent (f, indent,
2486 "tree _o%d[%u], _r%d;\n", depth, ops.length (), depth);
2487 char op0type[64];
2488 snprintf (op0type, sizeof (op0type), "TREE_TYPE (_o%d[0])", depth);
2489 for (unsigned i = 0; i < ops.length (); ++i)
2490 {
2491 char dest1[32];
2492 snprintf (dest1, sizeof (dest1), "_o%d[%u]", depth, i);
2493 const char *optype1
2494 = get_operand_type (opr, i, in_type, expr_type,
2495 i == 0 ? NULLnullptr : op0type);
2496 ops[i]->gen_transform (f, indent, dest1, gimple, depth + 1, optype1,
2497 cinfo, indexes,
2498 *opr == 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 const vec<dt_operand *> &gimple_exprs,
2988 const vec<dt_operand *> &generic_exprs,
2989 const vec<dt_operand *> &fns,
2990 const vec<dt_operand *> &generic_fns,
2991 const vec<dt_operand *> &preds,
2992 const 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 && j == 0) ? 1 : 2;
3421 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3422 &cinfo, indexes, cond_handling);
3423 }
3424
3425 /* Re-fold the toplevel result. It's basically an embedded
3426 gimple_build w/o actually building the stmt. */
3427 if (!is_predicate)
3428 {
3429 fprintf_indent (f, indent,
3430 "res_op->resimplify (lseq, valueize);\n");
3431 if (e->force_leaf)
3432 fprintf_indent (f, indent,
3433 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3434 "goto %s;\n", fail_label);
3435 }
3436 }
3437 else if (result->type == operand::OP_CAPTURE
3438 || result->type == operand::OP_C_EXPR)
3439 {
3440 fprintf_indent (f, indent, "tree tem;\n");
3441 result->gen_transform (f, indent, "tem", true, 1, "type",
3442 &cinfo, indexes);
3443 fprintf_indent (f, indent, "res_op->set_value (tem);\n");
3444 if (is_a <capture *> (result)
3445 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3446 {
3447 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3448 with substituting a capture of that. */
3449 fprintf_indent (f, indent,
3450 "if (COMPARISON_CLASS_P (tem))\n");
3451 fprintf_indent (f, indent,
3452 " {\n");
3453 fprintf_indent (f, indent,
3454 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3455 fprintf_indent (f, indent,
3456 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3457 fprintf_indent (f, indent,
3458 " }\n");
3459 }
3460 }
3461 else
3462 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 3462, __FUNCTION__))
;
3463 fprintf_indent (f, indent, "return true;\n");
3464 }
3465 else /* GENERIC */
3466 {
3467 bool is_predicate = false;
3468 if (result->type == operand::OP_EXPR)
3469 {
3470 expr *e = as_a <expr *> (result);
3471 id_base *opr = e->operation;
3472 /* When we delay operator substituting during lowering of fors we
3473 make sure that for code-gen purposes the effects of each substitute
3474 are the same. Thus just look at that. */
3475 if (user_id *uid = dyn_cast <user_id *> (opr))
3476 opr = uid->substitutes[0];
3477 else if (is_a <predicate_id *> (opr))
3478 is_predicate = true;
3479 /* Search for captures used multiple times in the result expression
3480 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3481 original expression. */
3482 if (!is_predicate)
3483 for (int i = 0; i < s->capture_max + 1; ++i)
3484 {
3485 if (cinfo.info[i].same_as != (unsigned)i
3486 || cinfo.info[i].cse_p)
3487 continue;
3488 if (cinfo.info[i].result_use_count
3489 > cinfo.info[i].match_use_count)
3490 fprintf_indent (f, indent,
3491 "if (! tree_invariant_p (captures[%d])) "
3492 "goto %s;\n", i, fail_label);
3493 }
3494 for (unsigned j = 0; j < e->ops.length (); ++j)
3495 {
3496 char dest[32];
3497 if (is_predicate)
3498 snprintf (dest, sizeof (dest), "res_ops[%d]", j);
3499 else
3500 {
3501 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3502 snprintf (dest, sizeof (dest), "res_op%d", j);
3503 }
3504 const char *optype
3505 = get_operand_type (opr, j,
3506 "type", e->expr_type,
3507 j == 0
3508 ? NULLnullptr : "TREE_TYPE (res_op0)");
3509 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3510 &cinfo, indexes);
3511 }
3512 if (is_predicate)
3513 fprintf_indent (f, indent, "return true;\n");
3514 else
3515 {
3516 fprintf_indent (f, indent, "tree _r;\n");
3517 /* Re-fold the toplevel result. Use non_lvalue to
3518 build NON_LVALUE_EXPRs so they get properly
3519 ignored when in GIMPLE form. */
3520 if (*opr == NON_LVALUE_EXPR)
3521 fprintf_indent (f, indent,
3522 "_r = non_lvalue_loc (loc, res_op0);\n");
3523 else
3524 {
3525 if (is_a <operator_id *> (opr))
3526 fprintf_indent (f, indent,
3527 "_r = fold_build%d_loc (loc, %s, type",
3528 e->ops.length (),
3529 *e->operation == CONVERT_EXPR
3530 ? "NOP_EXPR" : e->operation->id);
3531 else
3532 fprintf_indent (f, indent,
3533 "_r = maybe_build_call_expr_loc (loc, "
3534 "%s, type, %d", e->operation->id,
3535 e->ops.length());
3536 for (unsigned j = 0; j < e->ops.length (); ++j)
3537 fprintf (f, ", res_op%d", j);
3538 fprintf (f, ");\n");
3539 if (!is_a <operator_id *> (opr))
3540 {
3541 fprintf_indent (f, indent, "if (!_r)\n");
3542 fprintf_indent (f, indent, " goto %s;\n", fail_label);
3543 }
3544 }
3545 }
3546 }
3547 else if (result->type == operand::OP_CAPTURE
3548 || result->type == operand::OP_C_EXPR)
3549
3550 {
3551 fprintf_indent (f, indent, "tree _r;\n");
3552 result->gen_transform (f, indent, "_r", false, 1, "type",
3553 &cinfo, indexes);
3554 }
3555 else
3556 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 3556, __FUNCTION__))
;
3557 if (!is_predicate)
3558 {
3559 /* Search for captures not used in the result expression and dependent
3560 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3561 for (int i = 0; i < s->capture_max + 1; ++i)
3562 {
3563 if (cinfo.info[i].same_as != (unsigned)i)
3564 continue;
3565 if (!cinfo.info[i].force_no_side_effects_p
3566 && !cinfo.info[i].expr_p
3567 && cinfo.info[i].result_use_count == 0)
3568 {
3569 fprintf_indent (f, indent,
3570 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3571 i);
3572 fprintf_indent (f, indent + 2,
3573 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3574 "fold_ignored_result (captures[%d]), _r);\n",
3575 i);
3576 }
3577 }
3578 fprintf_indent (f, indent, "return _r;\n");
3579 }
3580 }
3581 indent -= 2;
3582 fprintf_indent (f, indent, "}\n");
3583 fprintf (f, "%s:;\n", fail_label);
3584 fail_label = NULLnullptr;
3585}
3586
3587/* Generate code for the '(if ...)', '(with ..)' and actual transform
3588 step of a '(simplify ...)' or '(match ...)'. This handles everything
3589 that is not part of the decision tree (simplify->match). */
3590
3591void
3592dt_simplify::gen (FILE *f, int indent, bool gimple, int depth ATTRIBUTE_UNUSED__attribute__ ((__unused__)))
3593{
3594 fprintf_indent (f, indent, "{\n");
3595 indent += 2;
3596 output_line_directive (f,
3597 s->result ? s->result->location : s->match->location);
3598 if (s->capture_max >= 0)
3599 {
3600 char opname[20];
3601 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3602 s->capture_max + 1, indexes[0]->get_name (opname));
3603
3604 for (int i = 1; i <= s->capture_max; ++i)
3605 {
3606 if (!indexes[i])
3607 break;
3608 fprintf (f, ", %s", indexes[i]->get_name (opname));
3609 }
3610 fprintf (f, " };\n");
3611 }
3612
3613 /* If we have a split-out function for the actual transform, call it. */
3614 if (info && info->fname)
3615 {
3616 if (gimple)
3617 {
3618 fprintf_indent (f, indent, "if (%s (res_op, seq, "
3619 "valueize, type, captures", info->fname);
3620 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3621 if (s->for_subst_vec[i].first->used)
3622 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3623 fprintf (f, "))\n");
3624 fprintf_indent (f, indent, " return true;\n");
3625 }
3626 else
3627 {
3628 fprintf_indent (f, indent, "tree res = %s (loc, type",
3629 info->fname);
3630 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3631 fprintf (f, ", _p%d", i);
3632 fprintf (f, ", captures");
3633 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3634 {
3635 if (s->for_subst_vec[i].first->used)
3636 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3637 }
3638 fprintf (f, ");\n");
3639 fprintf_indent (f, indent, "if (res) return res;\n");
3640 }
3641 }
3642 else
3643 {
3644 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3645 {
3646 if (! s->for_subst_vec[i].first->used)
3647 continue;
3648 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3649 fprintf_indent (f, indent, "const enum tree_code %s = %s;\n",
3650 s->for_subst_vec[i].first->id,
3651 s->for_subst_vec[i].second->id);
3652 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3653 fprintf_indent (f, indent, "const combined_fn %s = %s;\n",
3654 s->for_subst_vec[i].first->id,
3655 s->for_subst_vec[i].second->id);
3656 else
3657 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 3657, __FUNCTION__))
;
3658 }
3659 gen_1 (f, indent, gimple, s->result);
3660 }
3661
3662 indent -= 2;
3663 fprintf_indent (f, indent, "}\n");
3664}
3665
3666
3667/* Hash function for finding equivalent transforms. */
3668
3669hashval_t
3670sinfo_hashmap_traits::hash (const key_type &v)
3671{
3672 /* Only bother to compare those originating from the same source pattern. */
3673 return v->s->result->location;
3674}
3675
3676/* Compare function for finding equivalent transforms. */
3677
3678static bool
3679compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3680{
3681 if (o1->type != o2->type)
3682 return false;
3683
3684 switch (o1->type)
3685 {
3686 case operand::OP_IF:
3687 {
3688 if_expr *if1 = as_a <if_expr *> (o1);
3689 if_expr *if2 = as_a <if_expr *> (o2);
3690 /* ??? Properly compare c-exprs. */
3691 if (if1->cond != if2->cond)
3692 return false;
3693 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3694 return false;
3695 if (if1->falseexpr != if2->falseexpr
3696 || (if1->falseexpr
3697 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3698 return false;
3699 return true;
3700 }
3701 case operand::OP_WITH:
3702 {
3703 with_expr *with1 = as_a <with_expr *> (o1);
3704 with_expr *with2 = as_a <with_expr *> (o2);
3705 if (with1->with != with2->with)
3706 return false;
3707 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3708 }
3709 default:;
3710 }
3711
3712 /* We've hit a result. Time to compare capture-infos - this is required
3713 in addition to the conservative pointer-equivalency of the result IL. */
3714 capture_info cinfo1 (s1, o1, true);
3715 capture_info cinfo2 (s2, o2, true);
3716
3717 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3718 || cinfo1.info.length () != cinfo2.info.length ())
3719 return false;
3720
3721 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3722 {
3723 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3724 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3725 || (cinfo1.info[i].force_no_side_effects_p
3726 != cinfo2.info[i].force_no_side_effects_p)
3727 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3728 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3729 /* toplevel_msk is an optimization */
3730 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3731 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3732 /* the pointer back to the capture is for diagnostics only */)
3733 return false;
3734 }
3735
3736 /* ??? Deep-compare the actual result. */
3737 return o1 == o2;
3738}
3739
3740bool
3741sinfo_hashmap_traits::equal_keys (const key_type &v,
3742 const key_type &candidate)
3743{
3744 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3745}
3746
3747
3748/* Main entry to generate code for matching GIMPLE IL off the decision
3749 tree. */
3750
3751void
3752decision_tree::gen (FILE *f, bool gimple)
3753{
3754 sinfo_map_t si;
3755
3756 root->analyze (si);
3757
3758 fprintf (stderrstderr, "%s decision tree has %u leafs, maximum depth %u and "
3759 "a total number of %u nodes\n",
3760 gimple ? "GIMPLE" : "GENERIC",
3761 root->num_leafs, root->max_level, root->total_size);
3762
3763 /* First split out the transform part of equal leafs. */
3764 unsigned rcnt = 0;
3765 unsigned fcnt = 1;
3766 for (sinfo_map_t::iterator iter = si.begin ();
3767 iter != si.end (); ++iter)
3768 {
3769 sinfo *s = (*iter).second;
3770 /* Do not split out single uses. */
3771 if (s->cnt <= 1)
3772 continue;
3773
3774 rcnt += s->cnt - 1;
3775 if (verbose >= 1)
3776 {
3777 fprintf (stderrstderr, "found %u uses of", s->cnt);
3778 output_line_directive (stderrstderr, s->s->s->result->location);
3779 }
3780
3781 /* Generate a split out function with the leaf transform code. */
3782 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3783 fcnt++);
3784 if (gimple)
3785 fprintf (f, "\nstatic bool\n"
3786 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3787 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3788 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3789 "(captures)\n",
3790 s->fname);
3791 else
3792 {
3793 fprintf (f, "\nstatic tree\n"
3794 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3795 (*iter).second->fname);
3796 for (unsigned i = 0;
3797 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3798 fprintf (f, " tree ARG_UNUSED (_p%d),", i);
3799 fprintf (f, " tree *captures\n");
3800 }
3801 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3802 {
3803 if (! s->s->s->for_subst_vec[i].first->used)
3804 continue;
3805 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3806 fprintf (f, ", const enum tree_code ARG_UNUSED (%s)",
3807 s->s->s->for_subst_vec[i].first->id);
3808 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3809 fprintf (f, ", const combined_fn ARG_UNUSED (%s)",
3810 s->s->s->for_subst_vec[i].first->id);
3811 }
3812
3813 fprintf (f, ")\n{\n");
3814 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3815 if (gimple)
3816 fprintf (f, " return false;\n");
3817 else
3818 fprintf (f, " return NULL_TREE;\n");
3819 fprintf (f, "}\n");
3820 }
3821 fprintf (stderrstderr, "removed %u duplicate tails\n", rcnt);
3822
3823 for (unsigned n = 1; n <= 5; ++n)
3824 {
3825 bool has_kids_p = false;
3826
3827 /* First generate split-out functions. */
3828 for (unsigned j = 0; j < root->kids.length (); j++)
3829 {
3830 dt_operand *dop = static_cast<dt_operand *>(root->kids[j]);
3831 expr *e = static_cast<expr *>(dop->op);
3832 if (e->ops.length () != n
3833 /* Builtin simplifications are somewhat premature on
3834 GENERIC. The following drops patterns with outermost
3835 calls. It's easy to emit overloads for function code
3836 though if necessary. */
3837 || (!gimple
3838 && e->operation->kind != id_base::CODE))
3839 continue;
3840
3841 if (gimple)
3842 fprintf (f, "\nstatic bool\n"
3843 "gimple_simplify_%s (gimple_match_op *res_op,"
3844 " gimple_seq *seq,\n"
3845 " tree (*valueize)(tree) "
3846 "ATTRIBUTE_UNUSED,\n"
3847 " code_helper ARG_UNUSED (code), tree "
3848 "ARG_UNUSED (type)\n",
3849 e->operation->id);
3850 else
3851 fprintf (f, "\nstatic tree\n"
3852 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3853 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3854 e->operation->id);
3855 for (unsigned i = 0; i < n; ++i)
3856 fprintf (f, ", tree _p%d", i);
3857 fprintf (f, ")\n");
3858 fprintf (f, "{\n");
3859 dop->gen_kids (f, 2, gimple, 0);
3860 if (gimple)
3861 fprintf (f, " return false;\n");
3862 else
3863 fprintf (f, " return NULL_TREE;\n");
3864 fprintf (f, "}\n");
3865 has_kids_p = true;
3866 }
3867
3868 /* If this main entry has no children, avoid generating code
3869 with compiler warnings, by generating a simple stub. */
3870 if (! has_kids_p)
3871 {
3872 if (gimple)
3873 fprintf (f, "\nstatic bool\n"
3874 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3875 " tree (*)(tree), code_helper,\n"
3876 " const tree");
3877 else
3878 fprintf (f, "\ntree\n"
3879 "generic_simplify (location_t, enum tree_code,\n"
3880 " const tree");
3881 for (unsigned i = 0; i < n; ++i)
3882 fprintf (f, ", tree");
3883 fprintf (f, ")\n");
3884 fprintf (f, "{\n");
3885 if (gimple)
3886 fprintf (f, " return false;\n");
3887 else
3888 fprintf (f, " return NULL_TREE;\n");
3889 fprintf (f, "}\n");
3890 continue;
3891 }
3892
3893 /* Then generate the main entry with the outermost switch and
3894 tail-calls to the split-out functions. */
3895 if (gimple)
3896 fprintf (f, "\nstatic bool\n"
3897 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3898 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3899 " code_helper code, const tree type");
3900 else
3901 fprintf (f, "\ntree\n"
3902 "generic_simplify (location_t loc, enum tree_code code, "
3903 "const tree type ATTRIBUTE_UNUSED");
3904 for (unsigned i = 0; i < n; ++i)
3905 fprintf (f, ", tree _p%d", i);
3906 fprintf (f, ")\n");
3907 fprintf (f, "{\n");
3908
3909 if (gimple)
3910 fprintf (f, " switch (code.get_rep())\n"
3911 " {\n");
3912 else
3913 fprintf (f, " switch (code)\n"
3914 " {\n");
3915 for (unsigned i = 0; i < root->kids.length (); i++)
3916 {
3917 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3918 expr *e = static_cast<expr *>(dop->op);
3919 if (e->ops.length () != n
3920 /* Builtin simplifications are somewhat premature on
3921 GENERIC. The following drops patterns with outermost
3922 calls. It's easy to emit overloads for function code
3923 though if necessary. */
3924 || (!gimple
3925 && e->operation->kind != id_base::CODE))
3926 continue;
3927
3928 if (*e->operation == CONVERT_EXPR
3929 || *e->operation == NOP_EXPR)
3930 fprintf (f, " CASE_CONVERT:\n");
3931 else
3932 fprintf (f, " case %s%s:\n",
3933 is_a <fn_id *> (e->operation) ? "-" : "",
3934 e->operation->id);
3935 if (gimple)
3936 fprintf (f, " return gimple_simplify_%s (res_op, "
3937 "seq, valueize, code, type", e->operation->id);
3938 else
3939 fprintf (f, " return generic_simplify_%s (loc, code, type",
3940 e->operation->id);
3941 for (unsigned j = 0; j < n; ++j)
3942 fprintf (f, ", _p%d", j);
3943 fprintf (f, ");\n");
3944 }
3945 fprintf (f, " default:;\n"
3946 " }\n");
3947
3948 if (gimple)
3949 fprintf (f, " return false;\n");
3950 else
3951 fprintf (f, " return NULL_TREE;\n");
3952 fprintf (f, "}\n");
3953 }
3954}
3955
3956/* Output code to implement the predicate P from the decision tree DT. */
3957
3958void
3959write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3960{
3961 fprintf (f, "\nbool\n"
3962 "%s%s (tree t%s%s)\n"
3963 "{\n", gimple ? "gimple_" : "tree_", p->id,
3964 p->nargs > 0 ? ", tree *res_ops" : "",
3965 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3966 /* Conveniently make 'type' available. */
3967 fprintf_indent (f, 2, "const tree type = TREE_TYPE (t);\n");
3968
3969 if (!gimple)
3970 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3971 dt.root->gen_kids (f, 2, gimple, 0);
3972
3973 fprintf_indent (f, 2, "return false;\n"
3974 "}\n");
3975}
3976
3977/* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3978
3979static void
3980write_header (FILE *f, const char *head)
3981{
3982 fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3983 fprintf (f, " a IL pattern matching and simplification description. */\n");
3984
3985 /* Include the header instead of writing it awkwardly quoted here. */
3986 fprintf (f, "\n#include \"%s\"\n", head);
3987}
3988
3989
3990
3991/* AST parsing. */
3992
3993class parser
3994{
3995public:
3996 parser (cpp_reader *, bool gimple);
3997
3998private:
3999 const cpp_token *next ();
4000 const cpp_token *peek (unsigned = 1);
4001 const cpp_token *peek_ident (const char * = NULLnullptr, unsigned = 1);
4002 const cpp_token *expect (enum cpp_ttype);
4003 const cpp_token *eat_token (enum cpp_ttype);
4004 const char *get_string ();
4005 const char *get_ident ();
4006 const cpp_token *eat_ident (const char *);
4007 const char *get_number ();
4008
4009 unsigned get_internal_capture_id ();
4010
4011 id_base *parse_operation (unsigned char &);
4012 operand *parse_capture (operand *, bool);
4013 operand *parse_expr ();
4014 c_expr *parse_c_expr (cpp_ttype);
4015 operand *parse_op ();
4016
4017 void record_operlist (location_t, user_id *);
4018
4019 void parse_pattern ();
4020 operand *parse_result (operand *, predicate_id *);
4021 void push_simplify (simplify::simplify_kind,
4022 vec<simplify *>&, operand *, operand *);
4023 void parse_simplify (simplify::simplify_kind,
4024 vec<simplify *>&, predicate_id *, operand *);
4025 void parse_for (location_t);
4026 void parse_if (location_t);
4027 void parse_predicates (location_t);
4028 void parse_operator_list (location_t);
4029
4030 void finish_match_operand (operand *);
4031
4032 cpp_reader *r;
4033 bool gimple;
4034 vec<c_expr *> active_ifs;
4035 vec<vec<user_id *> > active_fors;
4036 hash_set<user_id *> *oper_lists_set;
4037 vec<user_id *> oper_lists;
4038
4039 cid_map_t *capture_ids;
4040 unsigned last_id;
4041
4042public:
4043 vec<simplify *> simplifiers;
4044 vec<predicate_id *> user_predicates;
4045 bool parsing_match_operand;
4046};
4047
4048/* Lexing helpers. */
4049
4050/* Read the next non-whitespace token from R. */
4051
4052const cpp_token *
4053parser::next ()
4054{
4055 const cpp_token *token;
4056 do
4057 {
4058 token = cpp_get_token (r);
4059 }
4060 while (token->type == CPP_PADDING);
4061 return token;
4062}
4063
4064/* Peek at the next non-whitespace token from R. */
4065
4066const cpp_token *
4067parser::peek (unsigned num)
4068{
4069 const cpp_token *token;
4070 unsigned i = 0;
4071 do
4072 {
4073 token = cpp_peek_token (r, i++);
4074 }
4075 while (token->type == CPP_PADDING
4076 || (--num > 0));
4077 /* If we peek at EOF this is a fatal error as it leaves the
4078 cpp_reader in unusable state. Assume we really wanted a
4079 token and thus this EOF is unexpected. */
4080 if (token->type == CPP_EOF)
4081 fatal_at (token, "unexpected end of file");
4082 return token;
4083}
4084
4085/* Peek at the next identifier token (or return NULL if the next
4086 token is not an identifier or equal to ID if supplied). */
4087
4088const cpp_token *
4089parser::peek_ident (const char *id, unsigned num)
4090{
4091 const cpp_token *token = peek (num);
4092 if (token->type != CPP_NAME)
4093 return 0;
4094
4095 if (id == 0)
4096 return token;
4097
4098 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)((cpp_hashnode *) (token->val.node.node))->ident.str;
4099 if (strcmp (id, t) == 0)
4100 return token;
4101
4102 return 0;
4103}
4104
4105/* Read the next token from R and assert it is of type TK. */
4106
4107const cpp_token *
4108parser::expect (enum cpp_ttype tk)
4109{
4110 const cpp_token *token = next ();
4111 if (token->type != tk)
4112 fatal_at (token, "expected %s, got %s",
4113 cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
4114
4115 return token;
4116}
4117
4118/* Consume the next token from R and assert it is of type TK. */
4119
4120const cpp_token *
4121parser::eat_token (enum cpp_ttype tk)
4122{
4123 return expect (tk);
4124}
4125
4126/* Read the next token from R and assert it is of type CPP_STRING and
4127 return its value. */
4128
4129const char *
4130parser::get_string ()
4131{
4132 const cpp_token *token = expect (CPP_STRING);
4133 return (const char *)token->val.str.text;
4134}
4135
4136/* Read the next token from R and assert it is of type CPP_NAME and
4137 return its value. */
4138
4139const char *
4140parser::get_ident ()
4141{
4142 const cpp_token *token = expect (CPP_NAME);
4143 return (const char *)CPP_HASHNODE (token->val.node.node)((cpp_hashnode *) (token->val.node.node))->ident.str;
4144}
4145
4146/* Eat an identifier token with value S from R. */
4147
4148const cpp_token *
4149parser::eat_ident (const char *s)
4150{
4151 const cpp_token *token = peek ();
4152 const char *t = get_ident ();
4153 if (strcmp (s, t) != 0)
4154 fatal_at (token, "expected '%s' got '%s'\n", s, t);
4155 return token;
4156}
4157
4158/* Read the next token from R and assert it is of type CPP_NUMBER and
4159 return its value. */
4160
4161const char *
4162parser::get_number ()
4163{
4164 const cpp_token *token = expect (CPP_NUMBER);
4165 return (const char *)token->val.str.text;
4166}
4167
4168/* Return a capture ID that can be used internally. */
4169
4170unsigned
4171parser::get_internal_capture_id ()
4172{
4173 unsigned newid = capture_ids->elements ();
4174 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4175 char id[13];
4176 bool existed;
4177 snprintf (id, sizeof (id), "__%u", newid);
4178 capture_ids->get_or_insert (xstrdup (id), &existed);
4179 if (existed)
4180 fatal ("reserved capture id '%s' already used", id);
4181 return newid;
4182}
4183
4184/* Record an operator-list use for transparent for handling. */
4185
4186void
4187parser::record_operlist (location_t loc, user_id *p)
4188{
4189 if (!oper_lists_set->add (p))
4190 {
4191 if (!oper_lists.is_empty ()
4192 && oper_lists[0]->substitutes.length () != p->substitutes.length ())
4193 fatal_at (loc, "User-defined operator list does not have the "
4194 "same number of entries as others used in the pattern");
4195 oper_lists.safe_push (p);
4196 }
4197}
4198
4199/* Parse the operator ID, special-casing convert?, convert1? and
4200 convert2? */
4201
4202id_base *
4203parser::parse_operation (unsigned char &opt_grp)
4204{
4205 const cpp_token *id_tok = peek ();
4206 char *alt_id = NULLnullptr;
4207 const char *id = get_ident ();
4208 const cpp_token *token = peek ();
4209 opt_grp = 0;
4210 if (token->type == CPP_QUERY
4211 && !(token->flags & PREV_WHITE(1 << 0)))
4212 {
4213 if (!parsing_match_operand)
4214 fatal_at (id_tok, "conditional convert can only be used in "
4215 "match expression");
4216 if (ISDIGIT (id[strlen (id) - 1])(_sch_istable[(id[strlen (id) - 1]) & 0xff] & (unsigned
short)(_sch_isdigit))
)
4217 {
4218 opt_grp = id[strlen (id) - 1] - '0' + 1;
4219 alt_id = xstrdup (id);
4220 alt_id[strlen (id) - 1] = '\0';
4221 if (opt_grp == 1)
4222 fatal_at (id_tok, "use '%s?' here", alt_id);
4223 }
4224 else
4225 opt_grp = 1;
4226 eat_token (CPP_QUERY);
4227 }
4228 id_base *op = get_operator (alt_id ? alt_id : id);
4229 if (!op)
4230 fatal_at (id_tok, "unknown operator %s", alt_id ? alt_id : id);
4231 if (alt_id)
4232 free (alt_id);
4233 user_id *p = dyn_cast<user_id *> (op);
4234 if (p && p->is_oper_list)
4235 {
4236 if (active_fors.length() == 0)
4237 record_operlist (id_tok->src_loc, p);
4238 else
4239 fatal_at (id_tok, "operator-list %s cannot be expanded inside 'for'", id);
4240 }
4241 return op;
4242}
4243
4244/* Parse a capture.
4245 capture = '@'<number> */
4246
4247class operand *
4248parser::parse_capture (operand *op, bool require_existing)
4249{
4250 location_t src_loc = eat_token (CPP_ATSIGN)->src_loc;
4251 const cpp_token *token = peek ();
4252 const char *id = NULLnullptr;
4253 bool value_match = false;
4254 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4255 if (token->type == CPP_ATSIGN
4256 && ! (token->flags & PREV_WHITE(1 << 0))
4257 && parsing_match_operand)
4258 {
4259 eat_token (CPP_ATSIGN);
4260 token = peek ();
4261 value_match = true;
4262 }
4263 if (token->type == CPP_NUMBER)
4264 id = get_number ();
4265 else if (token->type == CPP_NAME)
4266 id = get_ident ();
4267 else
4268 fatal_at (token, "expected number or identifier");
4269 unsigned next_id = capture_ids->elements ();
4270 bool existed;
4271 unsigned &num = capture_ids->get_or_insert (id, &existed);
4272 if (!existed)
4273 {
4274 if (require_existing)
4275 fatal_at (src_loc, "unknown capture id");
4276 num = next_id;
4277 }
4278 return new capture (src_loc, num, op, value_match);
4279}
4280
4281/* Parse an expression
4282 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4283
4284class operand *
4285parser::parse_expr ()
4286{
4287 const cpp_token *token = peek ();
4288 unsigned char opt_grp;
4289 expr *e = new expr (parse_operation (opt_grp), token->src_loc);
4290 token = peek ();
4291 operand *op;
4292 bool is_commutative = false;
4293 bool force_capture = false;
4294 const char *expr_type = NULLnullptr;
4295
4296 if (!parsing_match_operand
4297 && token->type == CPP_NOT
4298 && !(token->flags & PREV_WHITE(1 << 0)))
4299 {
4300 if (!gimple)
4301 fatal_at (token, "forcing simplification to a leaf is not supported "
4302 "for GENERIC");
4303 eat_token (CPP_NOT);
4304 e->force_leaf = true;
4305 }
4306
4307 if (token->type == CPP_COLON
4308 && !(token->flags & PREV_WHITE(1 << 0)))
4309 {
4310 eat_token (CPP_COLON);
4311 token = peek ();
4312 if (token->type == CPP_NAME
4313 && !(token->flags & PREV_WHITE(1 << 0)))
4314 {
4315 const char *s = get_ident ();
4316 if (!parsing_match_operand)
4317 expr_type = s;
4318 else
4319 {
4320 const char *sp = s;
4321 while (*sp)
4322 {
4323 if (*sp == 'c')
4324 {
4325 if (operator_id *o
4326 = dyn_cast<operator_id *> (e->operation))
4327 {
4328 if (!commutative_tree_code (o->code)
4329 && !comparison_code_p (o->code))
4330 fatal_at (token, "operation is not commutative");
4331 }
4332 else if (user_id *p = dyn_cast<user_id *> (e->operation))
4333 for (unsigned i = 0;
4334 i < p->substitutes.length (); ++i)
4335 {
4336 if (operator_id *q
4337 = dyn_cast<operator_id *> (p->substitutes[i]))
4338 {
4339 if (!commutative_tree_code (q->code)
4340 && !comparison_code_p (q->code))
4341 fatal_at (token, "operation %s is not "
4342 "commutative", q->id);
4343 }
4344 }
4345 is_commutative = true;
4346 }
4347 else if (*sp == 'C')
4348 is_commutative = true;
4349 else if (*sp == 's')
4350 {
4351 e->force_single_use = true;
4352 force_capture = true;
4353 }
4354 else
4355 fatal_at (token, "flag %c not recognized", *sp);
4356 sp++;
4357 }
4358 }
4359 token = peek ();
4360 }
4361 else
4362 fatal_at (token, "expected flag or type specifying identifier");
4363 }
4364
4365 if (token->type == CPP_ATSIGN
4366 && !(token->flags & PREV_WHITE(1 << 0)))
4367 op = parse_capture (e, false);
4368 else if (force_capture)
4369 {
4370 unsigned num = get_internal_capture_id ();
4371 op = new capture (token->src_loc, num, e, false);
4372 }
4373 else
4374 op = e;
4375 do
4376 {
4377 token = peek ();
4378 if (token->type == CPP_CLOSE_PAREN)
4379 {
4380 if (e->operation->nargs != -1
4381 && e->operation->nargs != (int) e->ops.length ())
4382 fatal_at (token, "'%s' expects %u operands, not %u",
4383 e->operation->id, e->operation->nargs, e->ops.length ());
4384 if (is_commutative)
4385 {
4386 if (e->ops.length () == 2
4387 || commutative_op (e->operation) >= 0)
4388 e->is_commutative = true;
4389 else
4390 fatal_at (token, "only binary operators or functions with "
4391 "two arguments can be marked commutative, "
4392 "unless the operation is known to be inherently "
4393 "commutative");
4394 }
4395 e->expr_type = expr_type;
4396 if (opt_grp != 0)
4397 {
4398 if (e->ops.length () != 1)
4399 fatal_at (token, "only unary operations can be conditional");
4400 e->opt_grp = opt_grp;
4401 }
4402 return op;
4403 }
4404 else if (!(token->flags & PREV_WHITE(1 << 0)))
4405 fatal_at (token, "expected expression operand");
4406
4407 e->append_op (parse_op ());
4408 }
4409 while (1);
4410}
4411
4412/* Lex native C code delimited by START recording the preprocessing tokens
4413 for later processing.
4414 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4415
4416c_expr *
4417parser::parse_c_expr (cpp_ttype start)
4418{
4419 const cpp_token *token;
4420 cpp_ttype end;
4421 unsigned opencnt;
4422 vec<cpp_token> code = vNULL;
4423 unsigned nr_stmts = 0;
4424 location_t loc = eat_token (start)->src_loc;
4425 if (start == CPP_OPEN_PAREN)
4426 end = CPP_CLOSE_PAREN;
4427 else if (start == CPP_OPEN_BRACE)
4428 end = CPP_CLOSE_BRACE;
4429 else
4430 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/genmatch.c"
, 4430, __FUNCTION__))
;
4431 opencnt = 1;
4432 do
4433 {
4434 token = next ();
4435
4436 /* Count brace pairs to find the end of the expr to match. */
4437 if (token->type == start)
4438 opencnt++;
4439 else if (token->type == end
4440 && --opencnt == 0)
4441 break;
4442 else if (token->type == CPP_EOF)
4443 fatal_at (token, "unexpected end of file");
4444
4445 /* This is a lame way of counting the number of statements. */
4446 if (token->type == CPP_SEMICOLON)
4447 nr_stmts++;
4448
4449 /* If this is possibly a user-defined identifier mark it used. */
4450 if (token->type == CPP_NAME)
4451 {
4452 id_base *idb = get_operator ((const char *)CPP_HASHNODE((cpp_hashnode *) (token->val.node.node))
4453 (token->val.node.node)((cpp_hashnode *) (token->val.node.node))->ident.str);
4454 user_id *p;
4455 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
4456 record_operlist (token->src_loc, p);
4457 }
4458
4459 /* Record the token. */
4460 code.safe_push (*token);
4461 }
4462 while (1);
4463 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4464}
4465
4466/* Parse an operand which is either an expression, a predicate or
4467 a standalone capture.
4468 op = predicate | expr | c_expr | capture */
4469
4470class operand *
4471parser::parse_op ()
4472{
4473 const cpp_token *token = peek ();
4474 class operand *op = NULLnullptr;
4475 if (token->type == CPP_OPEN_PAREN)
4476 {
4477 eat_token (CPP_OPEN_PAREN);
4478 op = parse_expr ();
4479 eat_token (CPP_CLOSE_PAREN);
4480 }
4481 else if (token->type == CPP_OPEN_BRACE)
4482 {
4483 op = parse_c_expr (CPP_OPEN_BRACE);
4484 }
4485 else
4486 {
4487 /* Remaining ops are either empty or predicates */
4488 if (token->type == CPP_NAME)
4489 {
4490 const char *id = get_ident ();
4491 id_base *opr = get_operator (id);
4492 if (!opr)
4493 fatal_at (token, "expected predicate name");
4494 if (operator_id *code1 = dyn_cast <operator_id *> (opr))
4495 {
4496 if (code1->nargs != 0)
4497 fatal_at (token, "using an operator with operands as predicate");
4498 /* Parse the zero-operand operator "predicates" as
4499 expression. */
4500 op = new expr (opr, token->src_loc);
4501 }
4502 else if (user_id *code2 = dyn_cast <user_id *> (opr))
4503 {
4504 if (code2->nargs != 0)
4505 fatal_at (token, "using an operator with operands as predicate");
4506 /* Parse the zero-operand operator "predicates" as
4507 expression. */
4508 op = new expr (opr, token->src_loc);
4509 }
4510 else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
4511 op = new predicate (p, token->src_loc);
4512 else
4513 fatal_at (token, "using an unsupported operator as predicate");
4514 if (!parsing_match_operand)
4515 fatal_at (token, "predicates are only allowed in match expression");
4516 token = peek ();
4517 if (token->flags & PREV_WHITE(1 << 0))
4518 return op;
4519 }
4520 else if (token->type != CPP_COLON
4521 && token->type != CPP_ATSIGN)
4522 fatal_at (token, "expected expression or predicate");
4523 /* optionally followed by a capture and a predicate. */
4524 if (token->type == CPP_COLON)
4525 fatal_at (token, "not implemented: predicate on leaf operand");
4526 if (token->type == CPP_ATSIGN)
4527 op = parse_capture (op, !parsing_match_operand);
4528 }
4529
4530 return op;
4531}
4532
4533/* Create a new simplify from the current parsing state and MATCH,
4534 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4535
4536void
4537parser::push_simplify (simplify::simplify_kind kind,
4538 vec<simplify *>& simplifiers,
4539 operand *match, operand *result)
4540{
4541 /* Build and push a temporary for operator list uses in expressions. */
4542 if (!oper_lists.is_empty ())
4543 active_fors.safe_push (oper_lists);
4544
4545 simplifiers.safe_push
4546 (new simplify (kind, last_id++, match, result,
4547 active_fors.copy (), capture_ids));
4548
4549 if (!oper_lists.is_empty ())
4550 active_fors.pop ();
4551}
4552
4553/* Parse
4554 <result-op> = <op> | <if> | <with>
4555 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4556 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4557 and return it. */
4558
4559operand *
4560parser::parse_result (operand *result, predicate_id *matcher)
4561{
4562 const cpp_token *token = peek ();
4563 if (token->type != CPP_OPEN_PAREN)
4564 return parse_op ();
4565
4566 eat_token (CPP_OPEN_PAREN);
4567 if (peek_ident ("if"))
4568 {
4569 eat_ident ("if");
4570 if_expr *ife = new if_expr (token->src_loc);
4571 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4572 if (peek ()->type == CPP_OPEN_PAREN)
4573 {
4574 ife->trueexpr = parse_result (result, matcher);
4575 if (peek ()->type == CPP_OPEN_PAREN)
4576 ife->falseexpr = parse_result (result, matcher);
4577 else if (peek ()->type != CPP_CLOSE_PAREN)
4578 ife->falseexpr = parse_op ();
4579 }
4580 else if (peek ()->type != CPP_CLOSE_PAREN)
4581 {
4582 ife->trueexpr = parse_op ();
4583 if (peek ()->type == CPP_OPEN_PAREN)
4584 ife->falseexpr = parse_result (result, matcher);
4585 else if (peek ()->type != CPP_CLOSE_PAREN)
4586 ife->falseexpr = parse_op ();
4587 }
4588 /* If this if is immediately closed then it contains a
4589 manual matcher or is part of a predicate definition. */
4590 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4591 {
4592 if (!matcher)
4593 fatal_at (peek (), "manual transform not implemented");
4594 ife->trueexpr = result;
4595 }
4596 eat_token (CPP_CLOSE_PAREN);
4597 return ife;
4598 }
4599 else if (peek_ident ("with"))
4600 {
4601 eat_ident ("with");
4602 with_expr *withe = new with_expr (token->src_loc);
4603 /* Parse (with c-expr expr) as (if-with (true) expr). */
4604 withe->with = parse_c_expr (CPP_OPEN_BRACE);
4605 withe->with->nr_stmts = 0;
4606 withe->subexpr = parse_result (result, matcher);
4607 eat_token (CPP_CLOSE_PAREN);
4608 return withe;
4609 }
4610 else if (peek_ident ("switch"))
4611 {
4612 token = eat_ident ("switch");
4613 location_t ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4614 eat_ident ("if");
4615 if_expr *ife = new if_expr (ifloc);
4616 operand *res = ife;
4617 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4618 if (peek ()->type == CPP_OPEN_PAREN)
4619 ife->trueexpr = parse_result (result, matcher);
4620 else
4621 ife->trueexpr = parse_op ();
4622 eat_token (CPP_CLOSE_PAREN);
4623 if (peek ()->type != CPP_OPEN_PAREN
4624 || !peek_ident ("if", 2))
4625 fatal_at (token, "switch can be implemented with a single if");
4626 while (peek ()->type != CPP_CLOSE_PAREN)
4627 {
4628 if (peek ()->type == CPP_OPEN_PAREN)
4629 {
4630 if (peek_ident ("if", 2))
4631 {
4632 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4633 eat_ident ("if");
4634 ife->falseexpr = new if_expr (ifloc);
4635 ife = as_a <if_expr *> (ife->falseexpr);
4636 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4637 if (peek ()->type == CPP_OPEN_PAREN)
4638 ife->trueexpr = parse_result (result, matcher);
4639 else
4640 ife->trueexpr = parse_op ();
4641 eat_token (CPP_CLOSE_PAREN);
4642 }
4643 else
4644 {
4645 /* switch default clause */
4646 ife->falseexpr = parse_result (result, matcher);
4647 eat_token (CPP_CLOSE_PAREN);
4648 return res;
4649 }
4650 }
4651 else
4652 {
4653 /* switch default clause */
4654 ife->falseexpr = parse_op ();
4655 eat_token (CPP_CLOSE_PAREN);
4656 return res;
4657 }
4658 }
4659 eat_token (CPP_CLOSE_PAREN);
4660 return res;
4661 }
4662 else
4663 {
4664 operand *op = result;
4665 if (!matcher)
4666 op = parse_expr ();
4667 eat_token (CPP_CLOSE_PAREN);
4668 return op;
4669 }
4670}
4671
4672/* Parse
4673 simplify = 'simplify' <expr> <result-op>
4674 or
4675 match = 'match' <ident> <expr> [<result-op>]
4676 and fill SIMPLIFIERS with the results. */
4677
4678void
4679parser::parse_simplify (simplify::simplify_kind kind,
4680 vec<simplify *>& simplifiers, predicate_id *matcher,
4681 operand *result)
4682{
4683 /* Reset the capture map. */
4684 if (!capture_ids)
4685 capture_ids = new cid_map_t;
4686 /* Reset oper_lists and set. */
4687 hash_set <user_id *> olist;
4688 oper_lists_set = &olist;
4689 oper_lists = vNULL;
4690
4691 const cpp_token *loc = peek ();
4692 parsing_match_operand = true;
4693 class operand *match = parse_op ();
4694 finish_match_operand (match);
4695 parsing_match_operand = false;
4696 if (match->type == operand::OP_CAPTURE && !matcher)
4697 fatal_at (loc, "outermost expression cannot be captured");
4698 if (match->type == operand::OP_EXPR
4699 && is_a <predicate_id *> (as_a <expr *> (match)->operation))
4700 fatal_at (loc, "outermost expression cannot be a predicate");
4701
4702 /* Splice active_ifs onto result and continue parsing the
4703 "then" expr. */
4704 if_expr *active_if = NULLnullptr;
4705 for (int i = active_ifs.length (); i > 0; --i)
4706 {
4707 if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4708 ifc->cond = active_ifs[i-1];
4709 ifc->trueexpr = active_if;
4710 active_if = ifc;
4711 }
4712 if_expr *outermost_if = active_if;
4713 while (active_if && active_if->trueexpr)
4714 active_if = as_a <if_expr *> (active_if->trueexpr);
4715
4716 const cpp_token *token = peek ();
4717
4718 /* If this if is immediately closed then it is part of a predicate
4719 definition. Push it. */
4720 if (token->type == CPP_CLOSE_PAREN)
4721 {
4722 if (!matcher)
4723 fatal_at (token, "expected transform expression");
4724 if (active_if)
4725 {
4726 active_if->trueexpr = result;
4727 result = outermost_if;
4728 }
4729 push_simplify (kind, simplifiers, match, result);
4730 return;
4731 }
4732
4733 operand *tem = parse_result (result, matcher);
4734 if (active_if)
4735 {
4736 active_if->trueexpr = tem;
4737 result = outermost_if;
4738 }
4739 else
4740 result = tem;
4741
4742 push_simplify (kind, simplifiers, match, result);
4743}
4744
4745/* Parsing of the outer control structures. */
4746
4747/* Parse a for expression
4748 for = '(' 'for' <subst>... <pattern> ')'
4749 subst = <ident> '(' <ident>... ')' */
4750
4751void
4752parser::parse_for (location_t)
4753{
4754 auto_vec<const cpp_token *> user_id_tokens;
4755 vec<user_id *> user_ids = vNULL;
4756 const cpp_token *token;
4757 unsigned min_n_opers = 0, max_n_opers = 0;
4758
4759 while (1)
4760 {
4761 token = peek ();
4762 if (token->type != CPP_NAME)
4763 break;
4764
4765 /* Insert the user defined operators into the operator hash. */
4766 const char *id = get_ident ();
4767 if (get_operator (id, true) != NULLnullptr)
4768 fatal_at (token, "operator already defined");
4769 user_id *op = new user_id (id);
4770 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4771 *slot = op;
4772 user_ids.safe_push (op);
4773 user_id_tokens.safe_push (token);
4774
4775 eat_token (CPP_OPEN_PAREN);
4776
4777 int arity = -1;
4778 while ((token = peek_ident ()) != 0)
4779 {
4780 const char *oper = get_ident ();
4781 id_base *idb = get_operator (oper, true);
4782 if (idb == NULLnullptr)
4783 fatal_at (token, "no such operator '%s'", oper);
4784
4785 if (arity == -1)
4786 arity = idb->nargs;
4787 else if (idb->nargs == -1)
4788 ;
4789 else if (idb->nargs != arity)
4790 fatal_at (token, "operator '%s' with arity %d does not match "
4791 "others with arity %d", oper, idb->nargs, arity);
4792
4793 user_id *p = dyn_cast<user_id *> (idb);
4794 if (p)
4795 {
4796 if (p->is_oper_list)
4797 op->substitutes.safe_splice (p->substitutes);
4798 else
4799 fatal_at (token, "iterator cannot be used as operator-list");
4800 }
4801 else
4802 op->substitutes.safe_push (idb);
4803 }
4804 op->nargs = arity;
4805 token = expect (CPP_CLOSE_PAREN);
4806
4807 unsigned nsubstitutes = op->substitutes.length ();
4808 if (nsubstitutes == 0)
4809 fatal_at (token, "A user-defined operator must have at least "
4810 "one substitution");
4811 if (max_n_opers == 0)
4812 {
4813 min_n_opers = nsubstitutes;
4814 max_n_opers = nsubstitutes;
4815 }
4816 else
4817 {
4818 if (nsubstitutes % min_n_opers != 0
4819 && min_n_opers % nsubstitutes != 0)
4820 fatal_at (token, "All user-defined identifiers must have a "
4821 "multiple number of operator substitutions of the "
4822 "smallest number of substitutions");
4823 if (nsubstitutes < min_n_opers)
4824 min_n_opers = nsubstitutes;
4825 else if (nsubstitutes > max_n_opers)
4826 max_n_opers = nsubstitutes;
4827 }
4828 }
4829
4830 unsigned n_ids = user_ids.length ();
4831 if (n_ids == 0)
4832 fatal_at (token, "for requires at least one user-defined identifier");
4833
4834 token = peek ();
4835 if (token->type == CPP_CLOSE_PAREN)
4836 fatal_at (token, "no pattern defined in for");
4837
4838 active_fors.safe_push (user_ids);
4839 while (1)
4840 {
4841 token = peek ();
4842 if (token->type == CPP_CLOSE_PAREN)
4843 break;
4844 parse_pattern ();
4845 }
4846 active_fors.pop ();
4847
4848 /* Remove user-defined operators from the hash again. */
4849 for (unsigned i = 0; i < user_ids.length (); ++i)
4850 {
4851 if (!user_ids[i]->used)
4852 warning_at (user_id_tokens[i],
4853 "operator %s defined but not used", user_ids[i]->id);
4854 operators->remove_elt (user_ids[i]);
4855 }
4856}
4857
4858/* Parse an identifier associated with a list of operators.
4859 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4860
4861void
4862parser::parse_operator_list (location_t)
4863{
4864 const cpp_token *token = peek ();
4865 const char *id = get_ident ();
4866
4867 if (get_operator (id, true) != 0)
4868 fatal_at (token, "operator %s already defined", id);
4869
4870 user_id *op = new user_id (id, true);
4871 int arity = -1;
4872
4873 while ((token = peek_ident ()) != 0)
4874 {
4875 token = peek ();
4876 const char *oper = get_ident ();
4877 id_base *idb = get_operator (oper, true);
4878
4879 if (idb == 0)
4880 fatal_at (token, "no such operator '%s'", oper);
4881
4882 if (arity == -1)
4883 arity = idb->nargs;
4884 else if (idb->nargs == -1)
4885 ;
4886 else if (arity != idb->nargs)
4887 fatal_at (token, "operator '%s' with arity %d does not match "
4888 "others with arity %d", oper, idb->nargs, arity);
4889
4890 /* We allow composition of multiple operator lists. */
4891 if (user_id *p = dyn_cast<user_id *> (idb))
4892 op->substitutes.safe_splice (p->substitutes);
4893 else
4894 op->substitutes.safe_push (idb);
4895 }
4896
4897 // Check that there is no junk after id-list
4898 token = peek();
4899 if (token->type != CPP_CLOSE_PAREN)
4900 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4901
4902 if (op->substitutes.length () == 0)
4903 fatal_at (token, "operator-list cannot be empty");
4904
4905 op->nargs = arity;
4906 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4907 *slot = op;
4908}
4909
4910/* Parse an outer if expression.
4911 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4912
4913void
4914parser::parse_if (location_t)
4915{
4916 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4917
4918 const cpp_token *token = peek ();
4919 if (token->type == CPP_CLOSE_PAREN)
4920 fatal_at (token, "no pattern defined in if");
4921
4922 active_ifs.safe_push (ifexpr);
4923 while (1)
4924 {
4925 token = peek ();
4926 if (token->type == CPP_CLOSE_PAREN)
4927 break;
4928
4929 parse_pattern ();
4930 }
4931 active_ifs.pop ();
4932}
4933
4934/* Parse a list of predefined predicate identifiers.
4935 preds = '(' 'define_predicates' <ident>... ')' */
4936
4937void
4938parser::parse_predicates (location_t)
4939{
4940 do
4941 {
4942 const cpp_token *token = peek ();
4943 if (token->type != CPP_NAME)
4944 break;
4945
4946 add_predicate (get_ident ());
4947 }
4948 while (1);
4949}
4950
4951/* Parse outer control structures.
4952 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4953
4954void
4955parser::parse_pattern ()
4956{
4957 /* All clauses start with '('. */
4958 eat_token (CPP_OPEN_PAREN);
4959 const cpp_token *token = peek ();
4960 const char *id = get_ident ();
4961 if (strcmp (id, "simplify") == 0)
4962 {
4963 parse_simplify (simplify::SIMPLIFY, simplifiers, NULLnullptr, NULLnullptr);
4964 capture_ids = NULLnullptr;
4965 }
4966 else if (strcmp (id, "match") == 0)
4967 {
4968 bool with_args = false;
4969 location_t e_loc = peek ()->src_loc;
4970 if (peek ()->type == CPP_OPEN_PAREN)
4971 {
4972 eat_token (CPP_OPEN_PAREN);
4973 with_args = true;
4974 }
4975 const char *name = get_ident ();
4976 id_base *id1 = get_operator (name);
4977 predicate_id *p;
4978 if (!id1)
4979 {
4980 p = add_predicate (name);
4981 user_predicates.safe_push (p);
4982 }
4983 else if ((p = dyn_cast <predicate_id *> (id1)))
4984 ;
4985 else
4986 fatal_at (token, "cannot add a match to a non-predicate ID");
4987 /* Parse (match <id> <arg>... (match-expr)) here. */
4988 expr *e = NULLnullptr;
4989 if (with_args)
4990 {
4991 capture_ids = new cid_map_t;
4992 e = new expr (p, e_loc);
4993 while (peek ()->type == CPP_ATSIGN)
4994 e->append_op (parse_capture (NULLnullptr, false));
4995 eat_token (CPP_CLOSE_PAREN);
4996 }
4997 if (p->nargs != -1
4998 && ((e && e->ops.length () != (unsigned)p->nargs)
4999 || (!e && p->nargs != 0)))
5000 fatal_at (token, "non-matching number of match operands");
5001 p->nargs = e ? e->ops.length () : 0;
5002 parse_simplify (simplify::MATCH, p->matchers, p, e);
5003 capture_ids = NULLnullptr;
5004 }
5005 else if (strcmp (id, "for") == 0)
5006 parse_for (token->src_loc);
5007 else if (strcmp (id, "if") == 0)
5008 parse_if (token->src_loc);
5009 else if (strcmp (id, "define_predicates") == 0)
5010 {
5011 if (active_ifs.length () > 0
5012 || active_fors.length () > 0)
5013 fatal_at (token, "define_predicates inside if or for is not supported");
5014 parse_predicates (token->src_loc);
5015 }
5016 else if (strcmp (id, "define_operator_list") == 0)
5017 {
5018 if (active_ifs.length () > 0
5019 || active_fors.length () > 0)
5020 fatal_at (token, "operator-list inside if or for is not supported");
5021 parse_operator_list (token->src_loc);
5022 }
5023 else
5024 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
5025 active_ifs.length () == 0 && active_fors.length () == 0
5026 ? "'define_predicates', " : "");
5027
5028 eat_token (CPP_CLOSE_PAREN);
5029}
5030
5031/* Helper for finish_match_operand, collecting captures of OP in CPTS
5032 recursively. */
5033
5034static void
5035walk_captures (operand *op, vec<vec<capture *> > &cpts)
5036{
5037 if (! op)
5038 return;
5039
5040 if (capture *c = dyn_cast <capture *> (op))
5041 {
5042 cpts[c->where].safe_push (c);
5043 walk_captures (c->what, cpts);
5044 }
5045 else if (expr *e = dyn_cast <expr *> (op))
5046 for (unsigned i = 0; i < e->ops.length (); ++i)
5047 walk_captures (e->ops[i], cpts);
5048}
5049
5050/* Finish up OP which is a match operand. */
5051
5052void
5053parser::finish_match_operand (operand *op)
5054{
5055 /* Look for matching captures, diagnose mis-uses of @@ and apply
5056 early lowering and distribution of value_match. */
5057 auto_vec<vec<capture *> > cpts;
5058 cpts.safe_grow_cleared (capture_ids->elements (), true);
5059 walk_captures (op, cpts);
5060 for (unsigned i = 0; i < cpts.length (); ++i)
5061 {
5062 capture *value_match = NULLnullptr;
5063 for (unsigned j = 0; j < cpts[i].length (); ++j)
5064 {
5065 if (cpts[i][j]->value_match)
5066 {
5067 if (value_match)
5068 fatal_at (cpts[i][j]->location, "duplicate @@");
5069 value_match = cpts[i][j];
5070 }
5071 }
5072 if (cpts[i].length () == 1 && value_match)
5073 fatal_at (value_match->location, "@@ without a matching capture");
5074 if (value_match)
5075 {
5076 /* Duplicate prevailing capture with the existing ID, create
5077 a fake ID and rewrite all captures to use it. This turns
5078 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5079 value_match->what = new capture (value_match->location,
5080 value_match->where,
5081 value_match->what, false);
5082 /* Create a fake ID and rewrite all captures to use it. */
5083 unsigned newid = get_internal_capture_id ();
5084 for (unsigned j = 0; j < cpts[i].length (); ++j)
5085 {
5086 cpts[i][j]->where = newid;
5087 cpts[i][j]->value_match = true;
5088 }
5089 }
5090 cpts[i].release ();
5091 }
5092}
5093
5094/* Main entry of the parser. Repeatedly parse outer control structures. */
5095
5096parser::parser (cpp_reader *r_, bool gimple_)
5097{
5098 r = r_;
5099 gimple = gimple_;
5100 active_ifs = vNULL;
5101 active_fors = vNULL;
5102 simplifiers = vNULL;
5103 oper_lists_set = NULLnullptr;
5104 oper_lists = vNULL;
5105 capture_ids = NULLnullptr;
5106 user_predicates = vNULL;
5107 parsing_match_operand = false;
5108 last_id = 0;
5109
5110 const cpp_token *token = next ();
5111 while (token->type != CPP_EOF)
5112 {
5113 _cpp_backup_tokens (r, 1);
5114 parse_pattern ();
5115 token = next ();
5116 }
5117}
5118
5119
5120/* Helper for the linemap code. */
5121
5122static size_t
5123round_alloc_size (size_t s)
5124{
5125 return s;
5126}
5127
5128
5129/* The genmatch generator program. It reads from a pattern description
5130 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5131
5132int
5133main (int argc, char **argv)
5134{
5135 cpp_reader *r;
5136
5137 progname = "genmatch";
5138
5139 if (argc < 2)
5140 return 1;
5141
5142 bool gimple = true;
5143 char *input = argv[argc-1];
5144 for (int i = 1; i < argc - 1; ++i)
5145 {
5146 if (strcmp (argv[i], "--gimple") == 0)
5147 gimple = true;
5148 else if (strcmp (argv[i], "--generic") == 0)
5149 gimple = false;
5150 else if (strcmp (argv[i], "-v") == 0)
5151 verbose = 1;
5152 else if (strcmp (argv[i], "-vv") == 0)
5153 verbose = 2;
5154 else
5155 {
5156 fprintf (stderrstderr, "Usage: genmatch "
5157 "[--gimple] [--generic] [-v[v]] input\n");
5158 return 1;
5159 }
5160 }
5161
5162 line_table = XCNEW (class line_maps)((class line_maps *) xcalloc (1, sizeof (class line_maps)));
5163 linemap_init (line_table, 0);
5164 line_table->reallocator = xrealloc;
5165 line_table->round_alloc_size = round_alloc_size;
5166
5167 r = cpp_create_reader (CLK_GNUC99, NULLnullptr, line_table);
5168 cpp_callbacks *cb = cpp_get_callbacks (r);
5169 cb->diagnostic = diagnostic_cb;
5170
5171 /* Add the build directory to the #include "" search path. */
5172 cpp_dir *dir = XCNEW (cpp_dir)((cpp_dir *) xcalloc (1, sizeof (cpp_dir)));
5173 dir->name = getpwd ();
5174 if (!dir->name)
5175 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
); }))
;
5176 cpp_set_include_chains (r, dir, NULLnullptr, false);
5177
5178 if (!cpp_read_main_file (r, input))
5179 return 1;
5180 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
5181 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
5182
5183 null_id = new id_base (id_base::NULL_ID, "null");
5184
5185 /* Pre-seed operators. */
5186 operators = new hash_table<id_base> (1024);
5187#define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5188 add_operator (SYM, # SYM, # TYPE, NARGS);
5189#define END_OF_BASE_TREE_CODES
5190#include "tree.def"
5191#undef END_OF_BASE_TREE_CODES
5192#undef DEFTREECODE
5193
5194 /* Pre-seed builtin functions.
5195 ??? Cannot use N (name) as that is targetm.emultls.get_address
5196 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5197#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5198 add_function (ENUM, "CFN_" # ENUM);
5199#include "builtins.def"
5200
5201#define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5202 add_function (IFN_##CODE, "CFN_" #CODE);
5203#include "internal-fn.def"
5204
5205 /* Parse ahead! */
5206 parser p (r, gimple);
5207
5208 if (gimple)
5209 write_header (stdoutstdout, "gimple-match-head.c");
5210 else
5211 write_header (stdoutstdout, "generic-match-head.c");
5212
5213 /* Go over all predicates defined with patterns and perform
5214 lowering and code generation. */
5215 for (unsigned i = 0; i < p.user_predicates.length (); ++i)
5216 {
5217 predicate_id *pred = p.user_predicates[i];
5218 lower (pred->matchers, gimple);
5219
5220 if (verbose == 2)
5221 for (unsigned j = 0; j < pred->matchers.length (); ++j)
5222 print_matches (pred->matchers[j]);
5223
5224 decision_tree dt;
5225 for (unsigned j = 0; j < pred->matchers.length (); ++j)
5226 dt.insert (pred->matchers[j], j);
5227
5228 if (verbose == 2)
5229 dt.print (stderrstderr);
5230
5231 write_predicate (stdoutstdout, pred, dt, gimple);
5232 }
5233
5234 /* Lower the main simplifiers and generate code for them. */
5235 lower (p.simplifiers, gimple);
5236
5237 if (verbose == 2)
5238 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5239 print_matches (p.simplifiers[i]);
5240
5241 decision_tree dt;
5242 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5243 dt.insert (p.simplifiers[i], i);
5244
5245 if (verbose == 2)
5246 dt.print (stderrstderr);
5247
5248 dt.gen (stdoutstdout, gimple);
5249
5250 /* Finalize. */
5251 cpp_finish (r, NULLnullptr);
5252 cpp_destroy (r);
5253
5254 delete operators;
5255
5256 return 0;
5257}