mklog: add subject line skeleton
[official-gcc.git] / gcc / genmatch.c
blob4d476720c9e215fa8de0c393b3b11473f0dea860
1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2021 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
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"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL)
38 return NULL;
40 void ggc_free (void *)
45 /* Global state. */
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
48 unsigned verbose;
51 /* libccp helpers. */
53 static class line_maps *line_table;
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.
61 This is the implementation for genmatch. */
63 expanded_location
64 linemap_client_expand_location_to_spelling_point (location_t loc,
65 enum location_aspect)
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);
72 static bool
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf, 5, 0)))
75 #endif
76 diagnostic_cb (cpp_reader *, enum cpp_diagnostic_level errtype,
77 enum cpp_warning_reason, rich_location *richloc,
78 const char *msg, va_list *ap)
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 (stderr, "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
85 (errtype == CPP_DL_WARNING) ? "warning" : "error");
86 vfprintf (stderr, msg, *ap);
87 fprintf (stderr, "\n");
88 FILE *f = fopen (loc.file, "r");
89 if (f)
91 char buf[128];
92 while (loc.line > 0)
94 if (!fgets (buf, 128, f))
95 goto notfound;
96 if (buf[strlen (buf) - 1] != '\n')
98 if (loc.line > 1)
99 loc.line++;
101 loc.line--;
103 fprintf (stderr, "%s", buf);
104 for (int i = 0; i < loc.column - 1; ++i)
105 fputc (' ', stderr);
106 fputc ('^', stderr);
107 fputc ('\n', stderr);
108 notfound:
109 fclose (f);
112 if (errtype == CPP_DL_FATAL)
113 exit (1);
114 return false;
117 static void
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf, 2, 3)))
120 #endif
121 fatal_at (const cpp_token *tk, const char *msg, ...)
123 rich_location richloc (line_table, tk->src_loc);
124 va_list ap;
125 va_start (ap, msg);
126 diagnostic_cb (NULL, CPP_DL_FATAL, CPP_W_NONE, &richloc, msg, &ap);
127 va_end (ap);
130 static void
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf, 2, 3)))
133 #endif
134 fatal_at (location_t loc, const char *msg, ...)
136 rich_location richloc (line_table, loc);
137 va_list ap;
138 va_start (ap, msg);
139 diagnostic_cb (NULL, CPP_DL_FATAL, CPP_W_NONE, &richloc, msg, &ap);
140 va_end (ap);
143 static void
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf, 2, 3)))
146 #endif
147 warning_at (const cpp_token *tk, const char *msg, ...)
149 rich_location richloc (line_table, tk->src_loc);
150 va_list ap;
151 va_start (ap, msg);
152 diagnostic_cb (NULL, CPP_DL_WARNING, CPP_W_NONE, &richloc, msg, &ap);
153 va_end (ap);
156 static void
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf, 2, 3)))
159 #endif
160 warning_at (location_t loc, const char *msg, ...)
162 rich_location richloc (line_table, loc);
163 va_list ap;
164 va_start (ap, msg);
165 diagnostic_cb (NULL, CPP_DL_WARNING, CPP_W_NONE, &richloc, msg, &ap);
166 va_end (ap);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
171 static void
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf, 3, 4)))
174 #endif
175 fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
177 va_list ap;
178 for (; indent >= 8; indent -= 8)
179 fputc ('\t', f);
180 fprintf (f, "%*s", indent, "");
181 va_start (ap, format);
182 vfprintf (f, format, ap);
183 va_end (ap);
186 static void
187 output_line_directive (FILE *f, location_t location,
188 bool dumpfile = false, bool fnargs = false)
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)
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;
207 if (fnargs)
208 fprintf (f, "\"%s\", %d", file, loc.line);
209 else
210 fprintf (f, "%s:%d", file, loc.line);
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);
221 /* Pull in tree codes and builtin function codes from their
222 definition files. */
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
225 enum tree_code {
226 #include "tree.def"
227 MAX_TREE_CODES
229 #undef DEFTREECODE
231 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
232 enum built_in_function {
233 #include "builtins.def"
234 END_BUILTINS
237 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
238 enum internal_fn {
239 #include "internal-fn.def"
240 IFN_LAST
243 enum combined_fn {
244 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
245 CFN_##ENUM = int (ENUM),
246 #include "builtins.def"
248 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
249 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
250 #include "internal-fn.def"
252 CFN_LAST
255 #include "case-cfn-macros.h"
257 /* Return true if CODE represents a commutative tree code. Otherwise
258 return false. */
259 bool
260 commutative_tree_code (enum tree_code code)
262 switch (code)
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;
288 default:
289 break;
291 return false;
294 /* Return true if CODE represents a ternary tree code for which the
295 first two operands are commutative. Otherwise return false. */
296 bool
297 commutative_ternary_tree_code (enum tree_code code)
299 switch (code)
301 case WIDEN_MULT_PLUS_EXPR:
302 case WIDEN_MULT_MINUS_EXPR:
303 case DOT_PROD_EXPR:
304 return true;
306 default:
307 break;
309 return false;
312 /* Return true if CODE is a comparison. */
314 bool
315 comparison_code_p (enum tree_code code)
317 switch (code)
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;
335 default:
336 break;
338 return false;
342 /* Base class for all identifiers the parser knows. */
344 class id_base : public nofree_ptr_hash<id_base>
346 public:
347 enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
349 id_base (id_kind, const char *, int = -1);
351 hashval_t hashval;
352 int nargs;
353 const char *id;
355 /* hash_table support. */
356 static inline hashval_t hash (const id_base *);
357 static inline int equal (const id_base *, const id_base *);
360 inline hashval_t
361 id_base::hash (const id_base *op)
363 return op->hashval;
366 inline int
367 id_base::equal (const id_base *op1,
368 const id_base *op2)
370 return (op1->hashval == op2->hashval
371 && strcmp (op1->id, op2->id) == 0);
374 /* The special id "null", which matches nothing. */
375 static id_base *null_id;
377 /* Hashtable of known pattern operators. This is pre-seeded from
378 all known tree codes and all known builtin function ids. */
379 static hash_table<id_base> *operators;
381 id_base::id_base (id_kind kind_, const char *id_, int nargs_)
383 kind = kind_;
384 id = id_;
385 nargs = nargs_;
386 hashval = htab_hash_string (id);
389 /* Identifier that maps to a tree code. */
391 class operator_id : public id_base
393 public:
394 operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
395 const char *tcc_)
396 : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
397 enum tree_code code;
398 const char *tcc;
401 /* Identifier that maps to a builtin or internal function code. */
403 class fn_id : public id_base
405 public:
406 fn_id (enum built_in_function fn_, const char *id_)
407 : id_base (id_base::FN, id_), fn (fn_) {}
408 fn_id (enum internal_fn fn_, const char *id_)
409 : id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
410 unsigned int fn;
413 class simplify;
415 /* Identifier that maps to a user-defined predicate. */
417 class predicate_id : public id_base
419 public:
420 predicate_id (const char *id_)
421 : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
422 vec<simplify *> matchers;
425 /* Identifier that maps to a operator defined by a 'for' directive. */
427 class user_id : public id_base
429 public:
430 user_id (const char *id_, bool is_oper_list_ = false)
431 : id_base (id_base::USER, id_), substitutes (vNULL),
432 used (false), is_oper_list (is_oper_list_) {}
433 vec<id_base *> substitutes;
434 bool used;
435 bool is_oper_list;
438 template<>
439 template<>
440 inline bool
441 is_a_helper <fn_id *>::test (id_base *id)
443 return id->kind == id_base::FN;
446 template<>
447 template<>
448 inline bool
449 is_a_helper <operator_id *>::test (id_base *id)
451 return id->kind == id_base::CODE;
454 template<>
455 template<>
456 inline bool
457 is_a_helper <predicate_id *>::test (id_base *id)
459 return id->kind == id_base::PREDICATE;
462 template<>
463 template<>
464 inline bool
465 is_a_helper <user_id *>::test (id_base *id)
467 return id->kind == id_base::USER;
470 /* If ID has a pair of consecutive, commutative operands, return the
471 index of the first, otherwise return -1. */
473 static int
474 commutative_op (id_base *id)
476 if (operator_id *code = dyn_cast <operator_id *> (id))
478 if (commutative_tree_code (code->code)
479 || commutative_ternary_tree_code (code->code))
480 return 0;
481 return -1;
483 if (fn_id *fn = dyn_cast <fn_id *> (id))
484 switch (fn->fn)
486 CASE_CFN_FMA:
487 case CFN_FMS:
488 case CFN_FNMA:
489 case CFN_FNMS:
490 return 0;
492 default:
493 return -1;
495 if (user_id *uid = dyn_cast<user_id *> (id))
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;
505 return -1;
508 /* Add a predicate identifier to the hash. */
510 static predicate_id *
511 add_predicate (const char *id)
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;
521 /* Add a tree code identifier to the hash. */
523 static void
524 add_operator (enum tree_code code, const char *id,
525 const char *tcc, unsigned nargs)
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;
550 /* Add a built-in or internal function identifier to the hash. ID is
551 the name of its CFN_* enumeration value. */
553 template <typename T>
554 static void
555 add_function (T code, const char *id)
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;
564 /* Helper for easy comparing ID with tree code CODE. */
566 static bool
567 operator==(id_base &id, enum tree_code code)
569 if (operator_id *oid = dyn_cast <operator_id *> (&id))
570 return oid->code == code;
571 return false;
574 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
576 id_base *
577 get_operator (const char *id, bool allow_null = false)
579 if (allow_null && strcmp (id, "null") == 0)
580 return null_id;
582 id_base tem (id_base::CODE, id);
584 id_base *op = operators->find_with_hash (&tem, tem.hashval);
585 if (op)
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;
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]))
598 all_lower = false;
599 else if (ISLOWER (id[i]))
600 all_upper = false;
601 if (all_lower)
603 /* Try in caps with _EXPR appended. */
604 id2 = ACONCAT ((id, "_EXPR", NULL));
605 for (unsigned int i = 0; id2[i]; ++i)
606 id2[i] = TOUPPER (id2[i]);
608 else if (all_upper && startswith (id, "IFN_"))
609 /* Try CFN_ instead of IFN_. */
610 id2 = ACONCAT (("CFN_", id + 4, NULL));
611 else if (all_upper && startswith (id, "BUILT_IN_"))
612 /* Try prepending CFN_. */
613 id2 = ACONCAT (("CFN_", id, NULL));
614 else
615 return NULL;
617 new (&tem) id_base (id_base::CODE, id2);
618 return operators->find_with_hash (&tem, tem.hashval);
621 /* Return the comparison operators that results if the operands are
622 swapped. This is safe for floating-point. */
624 id_base *
625 swap_tree_comparison (operator_id *p)
627 switch (p->code)
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 ();
657 typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
660 /* The AST produced by parsing of the pattern definitions. */
662 class dt_operand;
663 class capture_info;
665 /* The base class for operands. */
667 class operand {
668 public:
669 enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
670 operand (enum op_type type_, location_t loc_)
671 : type (type_), location (loc_) {}
672 enum op_type type;
673 location_t location;
674 virtual void gen_transform (FILE *, int, const char *, bool, int,
675 const char *, capture_info *,
676 dt_operand ** = 0,
677 int = 0)
678 { gcc_unreachable (); }
681 /* A predicate operand. Predicates are leafs in the AST. */
683 class predicate : public operand
685 public:
686 predicate (predicate_id *p_, location_t loc)
687 : operand (OP_PREDICATE, loc), p (p_) {}
688 predicate_id *p;
691 /* An operand that constitutes an expression. Expressions include
692 function calls and user-defined predicate invocations. */
694 class expr : public operand
696 public:
697 expr (id_base *operation_, location_t loc, bool is_commutative_ = false)
698 : operand (OP_EXPR, loc), operation (operation_),
699 ops (vNULL), expr_type (NULL), 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);
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. */
735 class c_expr : public operand
737 public:
738 /* A mapping of an identifier and its replacement. Used to apply
739 'for' lowering. */
740 class id_tab {
741 public:
742 const char *id;
743 const char *oper;
744 id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
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);
765 /* A wrapper around another operand that captures its value. */
767 class capture : public operand
769 public:
770 capture (location_t loc, unsigned where_, operand *what_, bool value_)
771 : operand (OP_CAPTURE, loc), where (where_), value_match (value_),
772 what (what_) {}
773 /* Identifier index for the value. */
774 unsigned where;
775 /* Whether in a match of two operands the compare should be for
776 equal values rather than equal atoms (boils down to a type
777 check or not). */
778 bool value_match;
779 /* The captured value. */
780 operand *what;
781 virtual void gen_transform (FILE *f, int, const char *, bool, int,
782 const char *, capture_info *,
783 dt_operand ** = 0, int = 0);
786 /* if expression. */
788 class if_expr : public operand
790 public:
791 if_expr (location_t loc)
792 : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
793 c_expr *cond;
794 operand *trueexpr;
795 operand *falseexpr;
798 /* with expression. */
800 class with_expr : public operand
802 public:
803 with_expr (location_t loc)
804 : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
805 c_expr *with;
806 operand *subexpr;
809 template<>
810 template<>
811 inline bool
812 is_a_helper <capture *>::test (operand *op)
814 return op->type == operand::OP_CAPTURE;
817 template<>
818 template<>
819 inline bool
820 is_a_helper <predicate *>::test (operand *op)
822 return op->type == operand::OP_PREDICATE;
825 template<>
826 template<>
827 inline bool
828 is_a_helper <c_expr *>::test (operand *op)
830 return op->type == operand::OP_C_EXPR;
833 template<>
834 template<>
835 inline bool
836 is_a_helper <expr *>::test (operand *op)
838 return op->type == operand::OP_EXPR;
841 template<>
842 template<>
843 inline bool
844 is_a_helper <if_expr *>::test (operand *op)
846 return op->type == operand::OP_IF;
849 template<>
850 template<>
851 inline bool
852 is_a_helper <with_expr *>::test (operand *op)
854 return op->type == operand::OP_WITH;
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. */
862 class simplify
864 public:
865 enum simplify_kind { SIMPLIFY, MATCH };
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) {}
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;
894 /* Debugging routines for dumping the AST. */
896 DEBUG_FUNCTION void
897 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
899 if (capture *c = dyn_cast<capture *> (o))
901 if (c->what && flattened == false)
902 print_operand (c->what, f, flattened);
903 fprintf (f, "@%u", c->where);
906 else if (predicate *p = dyn_cast<predicate *> (o))
907 fprintf (f, "%s", p->p->id);
909 else if (is_a<c_expr *> (o))
910 fprintf (f, "c_expr");
912 else if (expr *e = dyn_cast<expr *> (o))
914 if (e->ops.length () == 0)
915 fprintf (f, "%s", e->operation->id);
916 else
918 fprintf (f, "(%s", e->operation->id);
920 if (flattened == false)
922 for (unsigned i = 0; i < e->ops.length (); ++i)
924 putc (' ', f);
925 print_operand (e->ops[i], f, flattened);
928 putc (')', f);
932 else
933 gcc_unreachable ();
936 DEBUG_FUNCTION void
937 print_matches (class simplify *s, FILE *f = stderr)
939 fprintf (f, "for expression: ");
940 print_operand (s->match, f);
941 putc ('\n', f);
945 /* AST lowering. */
947 /* Lowering of commutative operators. */
949 static void
950 cartesian_product (const vec< vec<operand *> >& ops_vector,
951 vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
953 if (n == ops_vector.length ())
955 vec<operand *> xv = v.copy ();
956 result.safe_push (xv);
957 return;
960 for (unsigned i = 0; i < ops_vector[n].length (); ++i)
962 v[n] = ops_vector[n][i];
963 cartesian_product (ops_vector, result, v, n + 1);
967 /* Lower OP to two operands in case it is marked as commutative. */
969 static vec<operand *>
970 commutate (operand *op, vec<vec<user_id *> > &for_vec)
972 vec<operand *> ret = vNULL;
974 if (capture *c = dyn_cast <capture *> (op))
976 if (!c->what)
978 ret.safe_push (op);
979 return ret;
981 vec<operand *> v = commutate (c->what, for_vec);
982 for (unsigned i = 0; i < v.length (); ++i)
984 capture *nc = new capture (c->location, c->where, v[i],
985 c->value_match);
986 ret.safe_push (nc);
988 return ret;
991 expr *e = dyn_cast <expr *> (op);
992 if (!e || e->ops.length () == 0)
994 ret.safe_push (op);
995 return ret;
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));
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);
1008 for (unsigned i = 0; i < result.length (); ++i)
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);
1017 if (!e->is_commutative)
1018 return ret;
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)
1025 expr *ne = new expr (e);
1026 if (operator_id *r = dyn_cast <operator_id *> (ne->operation))
1028 if (comparison_code_p (r->code))
1029 ne->operation = swap_tree_comparison (r);
1031 else if (user_id *p = dyn_cast <user_id *> (ne->operation))
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]))
1037 if (comparison_code_p (q->code)
1038 && swap_tree_comparison (q) != q)
1040 found_compare = true;
1041 break;
1044 if (found_compare)
1046 user_id *newop = new user_id ("<internal>");
1047 for (unsigned j = 0; j < p->substitutes.length (); ++j)
1049 id_base *subst = p->substitutes[j];
1050 if (operator_id *q = dyn_cast <operator_id *> (subst))
1052 if (comparison_code_p (q->code))
1053 subst = swap_tree_comparison (q);
1055 newop->substitutes.safe_push (subst);
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)
1064 for_vec[j].safe_push (newop);
1065 newop = NULL;
1066 break;
1070 ne->is_commutative = false;
1071 for (unsigned j = 0; j < result[i].length (); ++j)
1073 int old_j = (j == opno ? opno + 1 : j == opno + 1 ? opno : j);
1074 ne->append_op (result[i][old_j]);
1076 ret.safe_push (ne);
1079 return ret;
1082 /* Lower operations marked as commutative in the AST of S and push
1083 the resulting patterns to SIMPLIFIERS. */
1085 static void
1086 lower_commutative (simplify *s, vec<simplify *>& simplifiers)
1088 vec<operand *> matchers = commutate (s->match, s->for_vec);
1089 for (unsigned i = 0; i < matchers.length (); ++i)
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);
1097 /* Strip conditional operations using group GRP from O and its
1098 children if STRIP, else replace them with an unconditional operation. */
1100 operand *
1101 lower_opt (operand *o, unsigned char grp, bool strip)
1103 if (capture *c = dyn_cast<capture *> (o))
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;
1113 expr *e = dyn_cast<expr *> (o);
1114 if (!e)
1115 return o;
1117 if (e->opt_grp == grp)
1119 if (strip)
1120 return lower_opt (e->ops[0], grp, strip);
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;
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));
1132 return ne;
1135 /* Determine whether O or its children uses the conditional operation
1136 group GRP. */
1138 static bool
1139 has_opt (operand *o, unsigned char grp)
1141 if (capture *c = dyn_cast<capture *> (o))
1143 if (c->what)
1144 return has_opt (c->what, grp);
1145 else
1146 return false;
1149 expr *e = dyn_cast<expr *> (o);
1150 if (!e)
1151 return false;
1153 if (e->opt_grp == grp)
1154 return true;
1156 for (unsigned i = 0; i < e->ops.length (); ++i)
1157 if (has_opt (e->ops[i], grp))
1158 return true;
1160 return false;
1163 /* Lower conditional convert operators in O, expanding it to a vector
1164 if required. */
1166 static vec<operand *>
1167 lower_opt (operand *o)
1169 vec<operand *> v1 = vNULL, v2;
1171 v1.safe_push (o);
1173 /* Conditional operations are lowered to a pattern with the
1174 operation and one without. All different conditional operation
1175 groups are lowered separately. */
1177 for (unsigned i = 1; i <= 10; ++i)
1179 v2 = vNULL;
1180 for (unsigned j = 0; j < v1.length (); ++j)
1181 if (has_opt (v1[j], i))
1183 v2.safe_push (lower_opt (v1[j], i, false));
1184 v2.safe_push (lower_opt (v1[j], i, true));
1187 if (v2 != vNULL)
1189 v1 = vNULL;
1190 for (unsigned j = 0; j < v2.length (); ++j)
1191 v1.safe_push (v2[j]);
1195 return v1;
1198 /* Lower conditional convert operators in the AST of S and push
1199 the resulting multiple patterns to SIMPLIFIERS. */
1201 static void
1202 lower_opt (simplify *s, vec<simplify *>& simplifiers)
1204 vec<operand *> matchers = lower_opt (s->match);
1205 for (unsigned i = 0; i < matchers.length (); ++i)
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);
1213 /* Lower the compare operand of COND_EXPRs to a
1214 GENERIC and a GIMPLE variant. */
1216 static vec<operand *>
1217 lower_cond (operand *o)
1219 vec<operand *> ro = vNULL;
1221 if (capture *c = dyn_cast<capture *> (o))
1223 if (c->what)
1225 vec<operand *> lop = vNULL;
1226 lop = lower_cond (c->what);
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;
1235 expr *e = dyn_cast<expr *> (o);
1236 if (!e || e->ops.length () == 0)
1238 ro.safe_push (o);
1239 return ro;
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]));
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);
1251 for (unsigned i = 0; i < result.length (); ++i)
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)))
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]))
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);
1282 else
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;
1291 ro.safe_push (ne);
1295 return ro;
1298 /* Lower the compare operand of COND_EXPRs to a
1299 GENERIC and a GIMPLE variant. */
1301 static void
1302 lower_cond (simplify *s, vec<simplify *>& simplifiers)
1304 vec<operand *> matchers = lower_cond (s->match);
1305 for (unsigned i = 0; i < matchers.length (); ++i)
1307 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1308 s->for_vec, s->capture_ids);
1309 simplifiers.safe_push (ns);
1313 /* Return true if O refers to ID. */
1315 bool
1316 contains_id (operand *o, user_id *id)
1318 if (capture *c = dyn_cast<capture *> (o))
1319 return c->what && contains_id (c->what, id);
1321 if (expr *e = dyn_cast<expr *> (o))
1323 if (e->operation == id)
1324 return true;
1325 for (unsigned i = 0; i < e->ops.length (); ++i)
1326 if (contains_id (e->ops[i], id))
1327 return true;
1328 return false;
1331 if (with_expr *w = dyn_cast <with_expr *> (o))
1332 return (contains_id (w->with, id)
1333 || contains_id (w->subexpr, id));
1335 if (if_expr *ife = dyn_cast <if_expr *> (o))
1336 return (contains_id (ife->cond, id)
1337 || contains_id (ife->trueexpr, id)
1338 || (ife->falseexpr && contains_id (ife->falseexpr, id)));
1340 if (c_expr *ce = dyn_cast<c_expr *> (o))
1341 return ce->capture_ids && ce->capture_ids->get (id->id);
1343 return false;
1347 /* In AST operand O replace operator ID with operator WITH. */
1349 operand *
1350 replace_id (operand *o, user_id *id, id_base *with)
1352 /* Deep-copy captures and expressions, replacing operations as
1353 needed. */
1354 if (capture *c = dyn_cast<capture *> (o))
1356 if (!c->what)
1357 return c;
1358 return new capture (c->location, c->where,
1359 replace_id (c->what, id, with), c->value_match);
1361 else if (expr *e = dyn_cast<expr *> (o))
1363 expr *ne = new expr (e);
1364 if (e->operation == id)
1365 ne->operation = with;
1366 for (unsigned i = 0; i < e->ops.length (); ++i)
1367 ne->append_op (replace_id (e->ops[i], id, with));
1368 return ne;
1370 else if (with_expr *w = dyn_cast <with_expr *> (o))
1372 with_expr *nw = new with_expr (w->location);
1373 nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1374 nw->subexpr = replace_id (w->subexpr, id, with);
1375 return nw;
1377 else if (if_expr *ife = dyn_cast <if_expr *> (o))
1379 if_expr *nife = new if_expr (ife->location);
1380 nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1381 nife->trueexpr = replace_id (ife->trueexpr, id, with);
1382 if (ife->falseexpr)
1383 nife->falseexpr = replace_id (ife->falseexpr, id, with);
1384 return nife;
1387 /* For c_expr we simply record a string replacement table which is
1388 applied at code-generation time. */
1389 if (c_expr *ce = dyn_cast<c_expr *> (o))
1391 vec<c_expr::id_tab> ids = ce->ids.copy ();
1392 ids.safe_push (c_expr::id_tab (id->id, with->id));
1393 return new c_expr (ce->r, ce->location,
1394 ce->code, ce->nr_stmts, ids, ce->capture_ids);
1397 return o;
1400 /* Return true if the binary operator OP is ok for delayed substitution
1401 during for lowering. */
1403 static bool
1404 binary_ok (operator_id *op)
1406 switch (op->code)
1408 case PLUS_EXPR:
1409 case MINUS_EXPR:
1410 case MULT_EXPR:
1411 case TRUNC_DIV_EXPR:
1412 case CEIL_DIV_EXPR:
1413 case FLOOR_DIV_EXPR:
1414 case ROUND_DIV_EXPR:
1415 case TRUNC_MOD_EXPR:
1416 case CEIL_MOD_EXPR:
1417 case FLOOR_MOD_EXPR:
1418 case ROUND_MOD_EXPR:
1419 case RDIV_EXPR:
1420 case EXACT_DIV_EXPR:
1421 case MIN_EXPR:
1422 case MAX_EXPR:
1423 case BIT_IOR_EXPR:
1424 case BIT_XOR_EXPR:
1425 case BIT_AND_EXPR:
1426 return true;
1427 default:
1428 return false;
1432 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1434 static void
1435 lower_for (simplify *sin, vec<simplify *>& simplifiers)
1437 vec<vec<user_id *> >& for_vec = sin->for_vec;
1438 unsigned worklist_start = 0;
1439 auto_vec<simplify *> worklist;
1440 worklist.safe_push (sin);
1442 /* Lower each recorded for separately, operating on the
1443 set of simplifiers created by the previous one.
1444 Lower inner-to-outer so inner for substitutes can refer
1445 to operators replaced by outer fors. */
1446 for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1448 vec<user_id *>& ids = for_vec[fi];
1449 unsigned n_ids = ids.length ();
1450 unsigned max_n_opers = 0;
1451 bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
1452 for (unsigned i = 0; i < n_ids; ++i)
1454 if (ids[i]->substitutes.length () > max_n_opers)
1455 max_n_opers = ids[i]->substitutes.length ();
1456 /* Require that all substitutes are of the same kind so that
1457 if we delay substitution to the result op code generation
1458 can look at the first substitute for deciding things like
1459 types of operands. */
1460 enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1461 for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1462 if (ids[i]->substitutes[j]->kind != kind)
1463 can_delay_subst = false;
1464 else if (operator_id *op
1465 = dyn_cast <operator_id *> (ids[i]->substitutes[j]))
1467 operator_id *op0
1468 = as_a <operator_id *> (ids[i]->substitutes[0]);
1469 if (strcmp (op->tcc, "tcc_comparison") == 0
1470 && strcmp (op0->tcc, "tcc_comparison") == 0)
1472 /* Unfortunately we can't just allow all tcc_binary. */
1473 else if (strcmp (op->tcc, "tcc_binary") == 0
1474 && strcmp (op0->tcc, "tcc_binary") == 0
1475 && binary_ok (op)
1476 && binary_ok (op0))
1478 else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
1479 || strcmp (op->id + 1, "ROTATE_EXPR") == 0)
1480 && (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
1481 || strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
1483 else
1484 can_delay_subst = false;
1486 else if (is_a <fn_id *> (ids[i]->substitutes[j]))
1488 else
1489 can_delay_subst = false;
1492 unsigned worklist_end = worklist.length ();
1493 for (unsigned si = worklist_start; si < worklist_end; ++si)
1495 simplify *s = worklist[si];
1496 for (unsigned j = 0; j < max_n_opers; ++j)
1498 operand *match_op = s->match;
1499 operand *result_op = s->result;
1500 auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
1501 bool skip = false;
1502 for (unsigned i = 0; i < n_ids; ++i)
1504 user_id *id = ids[i];
1505 id_base *oper = id->substitutes[j % id->substitutes.length ()];
1506 if (oper == null_id
1507 && (contains_id (match_op, id)
1508 || contains_id (result_op, id)))
1510 skip = true;
1511 break;
1513 subst.quick_push (std::make_pair (id, oper));
1514 match_op = replace_id (match_op, id, oper);
1515 if (result_op
1516 && !can_delay_subst)
1517 result_op = replace_id (result_op, id, oper);
1519 if (skip)
1520 continue;
1522 simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
1523 vNULL, s->capture_ids);
1524 ns->for_subst_vec.safe_splice (s->for_subst_vec);
1525 if (result_op
1526 && can_delay_subst)
1527 ns->for_subst_vec.safe_splice (subst);
1529 worklist.safe_push (ns);
1532 worklist_start = worklist_end;
1535 /* Copy out the result from the last for lowering. */
1536 for (unsigned i = worklist_start; i < worklist.length (); ++i)
1537 simplifiers.safe_push (worklist[i]);
1540 /* Lower the AST for everything in SIMPLIFIERS. */
1542 static void
1543 lower (vec<simplify *>& simplifiers, bool gimple)
1545 auto_vec<simplify *> out_simplifiers;
1546 for (unsigned i = 0; i < simplifiers.length (); ++i)
1547 lower_opt (simplifiers[i], out_simplifiers);
1549 simplifiers.truncate (0);
1550 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1551 lower_commutative (out_simplifiers[i], simplifiers);
1553 out_simplifiers.truncate (0);
1554 if (gimple)
1555 for (unsigned i = 0; i < simplifiers.length (); ++i)
1556 lower_cond (simplifiers[i], out_simplifiers);
1557 else
1558 out_simplifiers.safe_splice (simplifiers);
1561 simplifiers.truncate (0);
1562 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1563 lower_for (out_simplifiers[i], simplifiers);
1569 /* The decision tree built for generating GIMPLE and GENERIC pattern
1570 matching code. It represents the 'match' expression of all
1571 simplifies and has those as its leafs. */
1573 class dt_simplify;
1575 /* A hash-map collecting semantically equivalent leafs in the decision
1576 tree for splitting out to separate functions. */
1577 struct sinfo
1579 dt_simplify *s;
1581 const char *fname;
1582 unsigned cnt;
1585 struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1586 sinfo *>
1588 static inline hashval_t hash (const key_type &);
1589 static inline bool equal_keys (const key_type &, const key_type &);
1590 template <typename T> static inline void remove (T &) {}
1593 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1594 sinfo_map_t;
1596 /* Current simplifier ID we are processing during insertion into the
1597 decision tree. */
1598 static unsigned current_id;
1600 /* Decision tree base class, used for DT_NODE. */
1602 class dt_node
1604 public:
1605 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1607 enum dt_type type;
1608 unsigned level;
1609 dt_node *parent;
1610 vec<dt_node *> kids;
1612 /* Statistics. */
1613 unsigned num_leafs;
1614 unsigned total_size;
1615 unsigned max_level;
1617 dt_node (enum dt_type type_, dt_node *parent_)
1618 : type (type_), level (0), parent (parent_), kids (vNULL) {}
1620 dt_node *append_node (dt_node *);
1621 dt_node *append_op (operand *, dt_node *parent, unsigned pos);
1622 dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
1623 dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
1624 unsigned pos);
1625 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1627 virtual void gen (FILE *, int, bool, int) {}
1629 void gen_kids (FILE *, int, bool, int);
1630 void gen_kids_1 (FILE *, int, bool, int,
1631 vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1632 vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1634 void analyze (sinfo_map_t &);
1637 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1639 class dt_operand : public dt_node
1641 public:
1642 operand *op;
1643 dt_operand *match_dop;
1644 unsigned pos;
1645 bool value_match;
1646 unsigned for_id;
1648 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1649 dt_operand *parent_, unsigned pos_)
1650 : dt_node (type, parent_), op (op_), match_dop (match_dop_),
1651 pos (pos_), value_match (false), for_id (current_id) {}
1653 void gen (FILE *, int, bool, int);
1654 unsigned gen_predicate (FILE *, int, const char *, bool);
1655 unsigned gen_match_op (FILE *, int, const char *, bool);
1657 unsigned gen_gimple_expr (FILE *, int, int);
1658 unsigned gen_generic_expr (FILE *, int, const char *);
1660 char *get_name (char *);
1661 void gen_opname (char *, unsigned);
1664 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1666 class dt_simplify : public dt_node
1668 public:
1669 simplify *s;
1670 unsigned pattern_no;
1671 dt_operand **indexes;
1672 sinfo *info;
1674 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1675 : dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
1676 indexes (indexes_), info (NULL) {}
1678 void gen_1 (FILE *, int, bool, operand *);
1679 void gen (FILE *f, int, bool, int);
1682 template<>
1683 template<>
1684 inline bool
1685 is_a_helper <dt_operand *>::test (dt_node *n)
1687 return (n->type == dt_node::DT_OPERAND
1688 || n->type == dt_node::DT_MATCH
1689 || n->type == dt_node::DT_TRUE);
1692 template<>
1693 template<>
1694 inline bool
1695 is_a_helper <dt_simplify *>::test (dt_node *n)
1697 return n->type == dt_node::DT_SIMPLIFY;
1702 /* A container for the actual decision tree. */
1704 class decision_tree
1706 public:
1707 dt_node *root;
1709 void insert (class simplify *, unsigned);
1710 void gen (FILE *f, bool gimple);
1711 void print (FILE *f = stderr);
1713 decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
1715 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1716 unsigned pos = 0, dt_node *parent = 0);
1717 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1718 static bool cmp_node (dt_node *, dt_node *);
1719 static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1722 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1724 bool
1725 cmp_operand (operand *o1, operand *o2)
1727 if (!o1 || !o2 || o1->type != o2->type)
1728 return false;
1730 if (o1->type == operand::OP_PREDICATE)
1732 predicate *p1 = as_a<predicate *>(o1);
1733 predicate *p2 = as_a<predicate *>(o2);
1734 return p1->p == p2->p;
1736 else if (o1->type == operand::OP_EXPR)
1738 expr *e1 = static_cast<expr *>(o1);
1739 expr *e2 = static_cast<expr *>(o2);
1740 return (e1->operation == e2->operation
1741 && e1->is_generic == e2->is_generic);
1743 else
1744 return false;
1747 /* Compare two decision tree nodes N1 and N2 and return true if they
1748 are equal. */
1750 bool
1751 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1753 if (!n1 || !n2 || n1->type != n2->type)
1754 return false;
1756 if (n1 == n2)
1757 return true;
1759 if (n1->type == dt_node::DT_TRUE)
1760 return false;
1762 if (n1->type == dt_node::DT_OPERAND)
1763 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1764 (as_a<dt_operand *> (n2))->op);
1765 else if (n1->type == dt_node::DT_MATCH)
1766 return (((as_a<dt_operand *> (n1))->match_dop
1767 == (as_a<dt_operand *> (n2))->match_dop)
1768 && ((as_a<dt_operand *> (n1))->value_match
1769 == (as_a<dt_operand *> (n2))->value_match));
1770 return false;
1773 /* Search OPS for a decision tree node like P and return it if found. */
1775 dt_node *
1776 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1778 /* We can merge adjacent DT_TRUE. */
1779 if (p->type == dt_node::DT_TRUE
1780 && !ops.is_empty ()
1781 && ops.last ()->type == dt_node::DT_TRUE)
1782 return ops.last ();
1783 dt_operand *true_node = NULL;
1784 for (int i = ops.length () - 1; i >= 0; --i)
1786 /* But we can't merge across DT_TRUE nodes as they serve as
1787 pattern order barriers to make sure that patterns apply
1788 in order of appearance in case multiple matches are possible. */
1789 if (ops[i]->type == dt_node::DT_TRUE)
1791 if (! true_node
1792 || as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
1793 true_node = as_a <dt_operand *> (ops[i]);
1795 if (decision_tree::cmp_node (ops[i], p))
1797 /* Unless we are processing the same pattern or the blocking
1798 pattern is before the one we are going to merge with. */
1799 if (true_node
1800 && true_node->for_id != current_id
1801 && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
1803 if (verbose >= 1)
1805 location_t p_loc = 0;
1806 if (p->type == dt_node::DT_OPERAND)
1807 p_loc = as_a <dt_operand *> (p)->op->location;
1808 location_t op_loc = 0;
1809 if (ops[i]->type == dt_node::DT_OPERAND)
1810 op_loc = as_a <dt_operand *> (ops[i])->op->location;
1811 location_t true_loc = 0;
1812 true_loc = true_node->op->location;
1813 warning_at (p_loc,
1814 "failed to merge decision tree node");
1815 warning_at (op_loc,
1816 "with the following");
1817 warning_at (true_loc,
1818 "because of the following which serves as ordering "
1819 "barrier");
1821 return NULL;
1823 return ops[i];
1826 return NULL;
1829 /* Append N to the decision tree if it there is not already an existing
1830 identical child. */
1832 dt_node *
1833 dt_node::append_node (dt_node *n)
1835 dt_node *kid;
1837 kid = decision_tree::find_node (kids, n);
1838 if (kid)
1839 return kid;
1841 kids.safe_push (n);
1842 n->level = this->level + 1;
1844 return n;
1847 /* Append OP to the decision tree. */
1849 dt_node *
1850 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1852 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1853 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1854 return append_node (n);
1857 /* Append a DT_TRUE decision tree node. */
1859 dt_node *
1860 dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
1862 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1863 dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
1864 return append_node (n);
1867 /* Append a DT_MATCH decision tree node. */
1869 dt_node *
1870 dt_node::append_match_op (operand *op, dt_operand *match_dop,
1871 dt_node *parent, unsigned pos)
1873 dt_operand *parent_ = as_a<dt_operand *> (parent);
1874 dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
1875 return append_node (n);
1878 /* Append S to the decision tree. */
1880 dt_node *
1881 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1882 dt_operand **indexes)
1884 dt_simplify *s2;
1885 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1886 for (unsigned i = 0; i < kids.length (); ++i)
1887 if ((s2 = dyn_cast <dt_simplify *> (kids[i]))
1888 && (verbose >= 1
1889 || s->match->location != s2->s->match->location))
1891 /* With a nested patters, it's hard to avoid these in order
1892 to keep match.pd rules relatively small. */
1893 warning_at (s->match->location, "duplicate pattern");
1894 warning_at (s2->s->match->location, "previous pattern defined here");
1895 print_operand (s->match, stderr);
1896 fprintf (stderr, "\n");
1898 return append_node (n);
1901 /* Analyze the node and its children. */
1903 void
1904 dt_node::analyze (sinfo_map_t &map)
1906 num_leafs = 0;
1907 total_size = 1;
1908 max_level = level;
1910 if (type == DT_SIMPLIFY)
1912 /* Populate the map of equivalent simplifies. */
1913 dt_simplify *s = as_a <dt_simplify *> (this);
1914 bool existed;
1915 sinfo *&si = map.get_or_insert (s, &existed);
1916 if (!existed)
1918 si = new sinfo;
1919 si->s = s;
1920 si->cnt = 1;
1921 si->fname = NULL;
1923 else
1924 si->cnt++;
1925 s->info = si;
1926 num_leafs = 1;
1927 return;
1930 for (unsigned i = 0; i < kids.length (); ++i)
1932 kids[i]->analyze (map);
1933 num_leafs += kids[i]->num_leafs;
1934 total_size += kids[i]->total_size;
1935 max_level = MAX (max_level, kids[i]->max_level);
1939 /* Insert O into the decision tree and return the decision tree node found
1940 or created. */
1942 dt_node *
1943 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1944 unsigned pos, dt_node *parent)
1946 dt_node *q, *elm = 0;
1948 if (capture *c = dyn_cast<capture *> (o))
1950 unsigned capt_index = c->where;
1952 if (indexes[capt_index] == 0)
1954 if (c->what)
1955 q = insert_operand (p, c->what, indexes, pos, parent);
1956 else
1958 q = elm = p->append_true_op (o, parent, pos);
1959 goto at_assert_elm;
1961 // get to the last capture
1962 for (operand *what = c->what;
1963 what && is_a<capture *> (what);
1964 c = as_a<capture *> (what), what = c->what)
1967 if (!c->what)
1969 unsigned cc_index = c->where;
1970 dt_operand *match_op = indexes[cc_index];
1972 dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
1973 elm = decision_tree::find_node (p->kids, &temp);
1975 if (elm == 0)
1977 dt_operand match (dt_node::DT_MATCH, 0, match_op, 0, 0);
1978 match.value_match = c->value_match;
1979 elm = decision_tree::find_node (p->kids, &match);
1982 else
1984 dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
1985 elm = decision_tree::find_node (p->kids, &temp);
1988 at_assert_elm:
1989 gcc_assert (elm->type == dt_node::DT_TRUE
1990 || elm->type == dt_node::DT_OPERAND
1991 || elm->type == dt_node::DT_MATCH);
1992 indexes[capt_index] = static_cast<dt_operand *> (elm);
1993 return q;
1995 else
1997 p = p->append_match_op (o, indexes[capt_index], parent, pos);
1998 as_a <dt_operand *>(p)->value_match = c->value_match;
1999 if (c->what)
2000 return insert_operand (p, c->what, indexes, 0, p);
2001 else
2002 return p;
2005 p = p->append_op (o, parent, pos);
2006 q = p;
2008 if (expr *e = dyn_cast <expr *>(o))
2010 for (unsigned i = 0; i < e->ops.length (); ++i)
2011 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
2014 return q;
2017 /* Insert S into the decision tree. */
2019 void
2020 decision_tree::insert (class simplify *s, unsigned pattern_no)
2022 current_id = s->id;
2023 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
2024 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
2025 p->append_simplify (s, pattern_no, indexes);
2028 /* Debug functions to dump the decision tree. */
2030 DEBUG_FUNCTION void
2031 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
2033 if (p->type == dt_node::DT_NODE)
2034 fprintf (f, "root");
2035 else
2037 fprintf (f, "|");
2038 for (unsigned i = 0; i < indent; i++)
2039 fprintf (f, "-");
2041 if (p->type == dt_node::DT_OPERAND)
2043 dt_operand *dop = static_cast<dt_operand *>(p);
2044 print_operand (dop->op, f, true);
2046 else if (p->type == dt_node::DT_TRUE)
2047 fprintf (f, "true");
2048 else if (p->type == dt_node::DT_MATCH)
2049 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
2050 else if (p->type == dt_node::DT_SIMPLIFY)
2052 dt_simplify *s = static_cast<dt_simplify *> (p);
2053 fprintf (f, "simplify_%u { ", s->pattern_no);
2054 for (int i = 0; i <= s->s->capture_max; ++i)
2055 fprintf (f, "%p, ", (void *) s->indexes[i]);
2056 fprintf (f, " } ");
2058 if (is_a <dt_operand *> (p))
2059 fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
2062 fprintf (stderr, " (%p, %p), %u, %u\n",
2063 (void *) p, (void *) p->parent, p->level, p->kids.length ());
2065 for (unsigned i = 0; i < p->kids.length (); ++i)
2066 decision_tree::print_node (p->kids[i], f, indent + 2);
2069 DEBUG_FUNCTION void
2070 decision_tree::print (FILE *f)
2072 return decision_tree::print_node (root, f);
2076 /* For GENERIC we have to take care of wrapping multiple-used
2077 expressions with side-effects in save_expr and preserve side-effects
2078 of expressions with omit_one_operand. Analyze captures in
2079 match, result and with expressions and perform early-outs
2080 on the outermost match expression operands for cases we cannot
2081 handle. */
2083 class capture_info
2085 public:
2086 capture_info (simplify *s, operand *, bool);
2087 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
2088 bool walk_result (operand *o, bool, operand *);
2089 void walk_c_expr (c_expr *);
2091 struct cinfo
2093 bool expr_p;
2094 bool cse_p;
2095 bool force_no_side_effects_p;
2096 bool force_single_use;
2097 bool cond_expr_cond_p;
2098 unsigned long toplevel_msk;
2099 unsigned match_use_count;
2100 unsigned result_use_count;
2101 unsigned same_as;
2102 capture *c;
2105 auto_vec<cinfo> info;
2106 unsigned long force_no_side_effects;
2107 bool gimple;
2110 /* Analyze captures in S. */
2112 capture_info::capture_info (simplify *s, operand *result, bool gimple_)
2114 gimple = gimple_;
2116 expr *e;
2117 if (s->kind == simplify::MATCH)
2119 force_no_side_effects = -1;
2120 return;
2123 force_no_side_effects = 0;
2124 info.safe_grow_cleared (s->capture_max + 1, true);
2125 for (int i = 0; i <= s->capture_max; ++i)
2126 info[i].same_as = i;
2128 e = as_a <expr *> (s->match);
2129 for (unsigned i = 0; i < e->ops.length (); ++i)
2130 walk_match (e->ops[i], i,
2131 (i != 0 && *e->operation == COND_EXPR)
2132 || *e->operation == TRUTH_ANDIF_EXPR
2133 || *e->operation == TRUTH_ORIF_EXPR,
2134 i == 0 && *e->operation == COND_EXPR);
2136 walk_result (s->result, false, result);
2139 /* Analyze captures in the match expression piece O. */
2141 void
2142 capture_info::walk_match (operand *o, unsigned toplevel_arg,
2143 bool conditional_p, bool cond_expr_cond_p)
2145 if (capture *c = dyn_cast <capture *> (o))
2147 unsigned where = c->where;
2148 info[where].match_use_count++;
2149 info[where].toplevel_msk |= 1 << toplevel_arg;
2150 info[where].force_no_side_effects_p |= conditional_p;
2151 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2152 if (!info[where].c)
2153 info[where].c = c;
2154 if (!c->what)
2155 return;
2156 /* Recurse to exprs and captures. */
2157 if (is_a <capture *> (c->what)
2158 || is_a <expr *> (c->what))
2159 walk_match (c->what, toplevel_arg, conditional_p, false);
2160 /* We need to look past multiple captures to find a captured
2161 expression as with conditional converts two captures
2162 can be collapsed onto the same expression. Also collect
2163 what captures capture the same thing. */
2164 while (c->what && is_a <capture *> (c->what))
2166 c = as_a <capture *> (c->what);
2167 if (info[c->where].same_as != c->where
2168 && info[c->where].same_as != info[where].same_as)
2169 fatal_at (c->location, "cannot handle this collapsed capture");
2170 info[c->where].same_as = info[where].same_as;
2172 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2173 expr *e;
2174 if (c->what
2175 && (e = dyn_cast <expr *> (c->what)))
2177 /* Zero-operand expression captures like ADDR_EXPR@0 are
2178 similar as predicates -- if they are not mentioned in
2179 the result we have to force them to have no side-effects. */
2180 if (e->ops.length () != 0)
2181 info[where].expr_p = true;
2182 info[where].force_single_use |= e->force_single_use;
2185 else if (expr *e = dyn_cast <expr *> (o))
2187 for (unsigned i = 0; i < e->ops.length (); ++i)
2189 bool cond_p = conditional_p;
2190 bool expr_cond_p = false;
2191 if (i != 0 && *e->operation == COND_EXPR)
2192 cond_p = true;
2193 else if (*e->operation == TRUTH_ANDIF_EXPR
2194 || *e->operation == TRUTH_ORIF_EXPR)
2195 cond_p = true;
2196 if (i == 0
2197 && *e->operation == COND_EXPR)
2198 expr_cond_p = true;
2199 walk_match (e->ops[i], toplevel_arg, cond_p, expr_cond_p);
2202 else if (is_a <predicate *> (o))
2204 /* Mark non-captured leafs toplevel arg for checking. */
2205 force_no_side_effects |= 1 << toplevel_arg;
2206 if (verbose >= 1
2207 && !gimple)
2208 warning_at (o->location,
2209 "forcing no side-effects on possibly lost leaf");
2211 else
2212 gcc_unreachable ();
2215 /* Analyze captures in the result expression piece O. Return true
2216 if RESULT was visited in one of the children. Only visit
2217 non-if/with children if they are rooted on RESULT. */
2219 bool
2220 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2222 if (capture *c = dyn_cast <capture *> (o))
2224 unsigned where = info[c->where].same_as;
2225 info[where].result_use_count++;
2226 /* If we substitute an expression capture we don't know
2227 which captures this will end up using (well, we don't
2228 compute that). Force the uses to be side-effect free
2229 which means forcing the toplevels that reach the
2230 expression side-effect free. */
2231 if (info[where].expr_p)
2232 force_no_side_effects |= info[where].toplevel_msk;
2233 /* Mark CSE capture uses as forced to have no side-effects. */
2234 if (c->what
2235 && is_a <expr *> (c->what))
2237 info[where].cse_p = true;
2238 walk_result (c->what, true, result);
2241 else if (expr *e = dyn_cast <expr *> (o))
2243 id_base *opr = e->operation;
2244 if (user_id *uid = dyn_cast <user_id *> (opr))
2245 opr = uid->substitutes[0];
2246 for (unsigned i = 0; i < e->ops.length (); ++i)
2248 bool cond_p = conditional_p;
2249 if (i != 0 && *e->operation == COND_EXPR)
2250 cond_p = true;
2251 else if (*e->operation == TRUTH_ANDIF_EXPR
2252 || *e->operation == TRUTH_ORIF_EXPR)
2253 cond_p = true;
2254 walk_result (e->ops[i], cond_p, result);
2257 else if (if_expr *ie = dyn_cast <if_expr *> (o))
2259 /* 'if' conditions should be all fine. */
2260 if (ie->trueexpr == result)
2262 walk_result (ie->trueexpr, false, result);
2263 return true;
2265 if (ie->falseexpr == result)
2267 walk_result (ie->falseexpr, false, result);
2268 return true;
2270 bool res = false;
2271 if (is_a <if_expr *> (ie->trueexpr)
2272 || is_a <with_expr *> (ie->trueexpr))
2273 res |= walk_result (ie->trueexpr, false, result);
2274 if (ie->falseexpr
2275 && (is_a <if_expr *> (ie->falseexpr)
2276 || is_a <with_expr *> (ie->falseexpr)))
2277 res |= walk_result (ie->falseexpr, false, result);
2278 return res;
2280 else if (with_expr *we = dyn_cast <with_expr *> (o))
2282 bool res = (we->subexpr == result);
2283 if (res
2284 || is_a <if_expr *> (we->subexpr)
2285 || is_a <with_expr *> (we->subexpr))
2286 res |= walk_result (we->subexpr, false, result);
2287 if (res)
2288 walk_c_expr (we->with);
2289 return res;
2291 else if (c_expr *ce = dyn_cast <c_expr *> (o))
2292 walk_c_expr (ce);
2293 else
2294 gcc_unreachable ();
2296 return false;
2299 /* Look for captures in the C expr E. */
2301 void
2302 capture_info::walk_c_expr (c_expr *e)
2304 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2305 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2306 really escape through. */
2307 unsigned p_depth = 0;
2308 for (unsigned i = 0; i < e->code.length (); ++i)
2310 const cpp_token *t = &e->code[i];
2311 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2312 id_base *id;
2313 if (t->type == CPP_NAME
2314 && (strcmp ((const char *)CPP_HASHNODE
2315 (t->val.node.node)->ident.str, "TREE_TYPE") == 0
2316 || strcmp ((const char *)CPP_HASHNODE
2317 (t->val.node.node)->ident.str, "TREE_CODE") == 0
2318 || strcmp ((const char *)CPP_HASHNODE
2319 (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
2320 || ((id = get_operator ((const char *)CPP_HASHNODE
2321 (t->val.node.node)->ident.str))
2322 && is_a <predicate_id *> (id)))
2323 && n->type == CPP_OPEN_PAREN)
2324 p_depth++;
2325 else if (t->type == CPP_CLOSE_PAREN
2326 && p_depth > 0)
2327 p_depth--;
2328 else if (p_depth == 0
2329 && t->type == CPP_ATSIGN
2330 && (n->type == CPP_NUMBER
2331 || n->type == CPP_NAME)
2332 && !(n->flags & PREV_WHITE))
2334 const char *id1;
2335 if (n->type == CPP_NUMBER)
2336 id1 = (const char *)n->val.str.text;
2337 else
2338 id1 = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2339 unsigned *where = e->capture_ids->get(id1);
2340 if (! where)
2341 fatal_at (n, "unknown capture id '%s'", id1);
2342 info[info[*where].same_as].force_no_side_effects_p = true;
2343 if (verbose >= 1
2344 && !gimple)
2345 warning_at (t, "capture escapes");
2351 /* The current label failing the current matched pattern during
2352 code generation. */
2353 static char *fail_label;
2355 /* Code generation off the decision tree and the refered AST nodes. */
2357 bool
2358 is_conversion (id_base *op)
2360 return (*op == CONVERT_EXPR
2361 || *op == NOP_EXPR
2362 || *op == FLOAT_EXPR
2363 || *op == FIX_TRUNC_EXPR
2364 || *op == VIEW_CONVERT_EXPR);
2367 /* Get the type to be used for generating operand POS of OP from the
2368 various sources. */
2370 static const char *
2371 get_operand_type (id_base *op, unsigned pos,
2372 const char *in_type,
2373 const char *expr_type,
2374 const char *other_oprnd_type)
2376 /* Generally operands whose type does not match the type of the
2377 expression generated need to know their types but match and
2378 thus can fall back to 'other_oprnd_type'. */
2379 if (is_conversion (op))
2380 return other_oprnd_type;
2381 else if (*op == REALPART_EXPR
2382 || *op == IMAGPART_EXPR)
2383 return other_oprnd_type;
2384 else if (is_a <operator_id *> (op)
2385 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2386 return other_oprnd_type;
2387 else if (*op == COND_EXPR
2388 && pos == 0)
2389 return "boolean_type_node";
2390 else if (startswith (op->id, "CFN_COND_"))
2392 /* IFN_COND_* operands 1 and later by default have the same type
2393 as the result. The type of operand 0 needs to be specified
2394 explicitly. */
2395 if (pos > 0 && expr_type)
2396 return expr_type;
2397 else if (pos > 0 && in_type)
2398 return in_type;
2399 else
2400 return NULL;
2402 else
2404 /* Otherwise all types should match - choose one in order of
2405 preference. */
2406 if (expr_type)
2407 return expr_type;
2408 else if (in_type)
2409 return in_type;
2410 else
2411 return other_oprnd_type;
2415 /* Generate transform code for an expression. */
2417 void
2418 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2419 int depth, const char *in_type, capture_info *cinfo,
2420 dt_operand **indexes, int)
2422 id_base *opr = operation;
2423 /* When we delay operator substituting during lowering of fors we
2424 make sure that for code-gen purposes the effects of each substitute
2425 are the same. Thus just look at that. */
2426 if (user_id *uid = dyn_cast <user_id *> (opr))
2427 opr = uid->substitutes[0];
2429 bool conversion_p = is_conversion (opr);
2430 const char *type = expr_type;
2431 char optype[64];
2432 if (type)
2433 /* If there was a type specification in the pattern use it. */
2435 else if (conversion_p)
2436 /* For conversions we need to build the expression using the
2437 outer type passed in. */
2438 type = in_type;
2439 else if (*opr == REALPART_EXPR
2440 || *opr == IMAGPART_EXPR)
2442 /* __real and __imag use the component type of its operand. */
2443 snprintf (optype, sizeof (optype), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2444 depth);
2445 type = optype;
2447 else if (is_a <operator_id *> (opr)
2448 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2450 /* comparisons use boolean_type_node (or what gets in), but
2451 their operands need to figure out the types themselves. */
2452 if (in_type)
2453 type = in_type;
2454 else
2456 snprintf (optype, sizeof (optype), "boolean_type_node");
2457 type = optype;
2459 in_type = NULL;
2461 else if (*opr == COND_EXPR
2462 || *opr == VEC_COND_EXPR
2463 || startswith (opr->id, "CFN_COND_"))
2465 /* Conditions are of the same type as their first alternative. */
2466 snprintf (optype, sizeof (optype), "TREE_TYPE (_o%d[1])", depth);
2467 type = optype;
2469 else
2471 /* Other operations are of the same type as their first operand. */
2472 snprintf (optype, sizeof (optype), "TREE_TYPE (_o%d[0])", depth);
2473 type = optype;
2475 if (!type)
2476 fatal_at (location, "cannot determine type of operand");
2478 fprintf_indent (f, indent, "{\n");
2479 indent += 2;
2480 fprintf_indent (f, indent,
2481 "tree _o%d[%u], _r%d;\n", depth, ops.length (), depth);
2482 char op0type[64];
2483 snprintf (op0type, sizeof (op0type), "TREE_TYPE (_o%d[0])", depth);
2484 for (unsigned i = 0; i < ops.length (); ++i)
2486 char dest1[32];
2487 snprintf (dest1, sizeof (dest1), "_o%d[%u]", depth, i);
2488 const char *optype1
2489 = get_operand_type (opr, i, in_type, expr_type,
2490 i == 0 ? NULL : op0type);
2491 ops[i]->gen_transform (f, indent, dest1, gimple, depth + 1, optype1,
2492 cinfo, indexes,
2493 *opr == COND_EXPR && i == 0 ? 1 : 2);
2496 const char *opr_name;
2497 if (*operation == CONVERT_EXPR)
2498 opr_name = "NOP_EXPR";
2499 else
2500 opr_name = operation->id;
2502 if (gimple)
2504 if (*opr == CONVERT_EXPR)
2506 fprintf_indent (f, indent,
2507 "if (%s != TREE_TYPE (_o%d[0])\n",
2508 type, depth);
2509 fprintf_indent (f, indent,
2510 " && !useless_type_conversion_p (%s, TREE_TYPE "
2511 "(_o%d[0])))\n",
2512 type, depth);
2513 fprintf_indent (f, indent + 2, "{\n");
2514 indent += 4;
2516 /* ??? Building a stmt can fail for various reasons here, seq being
2517 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2518 So if we fail here we should continue matching other patterns. */
2519 fprintf_indent (f, indent, "gimple_match_op tem_op "
2520 "(res_op->cond.any_else (), %s, %s", opr_name, type);
2521 for (unsigned i = 0; i < ops.length (); ++i)
2522 fprintf (f, ", _o%d[%u]", depth, i);
2523 fprintf (f, ");\n");
2524 fprintf_indent (f, indent, "tem_op.resimplify (lseq, valueize);\n");
2525 fprintf_indent (f, indent,
2526 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth,
2527 !force_leaf ? "lseq" : "NULL");
2528 fprintf_indent (f, indent,
2529 "if (!_r%d) goto %s;\n",
2530 depth, fail_label);
2531 if (*opr == CONVERT_EXPR)
2533 indent -= 4;
2534 fprintf_indent (f, indent, " }\n");
2535 fprintf_indent (f, indent, "else\n");
2536 fprintf_indent (f, indent, " _r%d = _o%d[0];\n", depth, depth);
2539 else
2541 if (*opr == CONVERT_EXPR)
2543 fprintf_indent (f, indent, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2544 depth, type);
2545 indent += 2;
2547 if (opr->kind == id_base::CODE)
2548 fprintf_indent (f, indent, "_r%d = fold_build%d_loc (loc, %s, %s",
2549 depth, ops.length(), opr_name, type);
2550 else
2552 fprintf_indent (f, indent, "{\n");
2553 fprintf_indent (f, indent, " _r%d = maybe_build_call_expr_loc (loc, "
2554 "%s, %s, %d", depth, opr_name, type, ops.length());
2556 for (unsigned i = 0; i < ops.length (); ++i)
2557 fprintf (f, ", _o%d[%u]", depth, i);
2558 fprintf (f, ");\n");
2559 if (opr->kind != id_base::CODE)
2561 fprintf_indent (f, indent, " if (!_r%d)\n", depth);
2562 fprintf_indent (f, indent, " goto %s;\n", fail_label);
2563 fprintf_indent (f, indent, "}\n");
2565 if (*opr == CONVERT_EXPR)
2567 indent -= 2;
2568 fprintf_indent (f, indent, "else\n");
2569 fprintf_indent (f, indent, " _r%d = _o%d[0];\n", depth, depth);
2572 fprintf_indent (f, indent, "%s = _r%d;\n", dest, depth);
2573 indent -= 2;
2574 fprintf_indent (f, indent, "}\n");
2577 /* Generate code for a c_expr which is either the expression inside
2578 an if statement or a sequence of statements which computes a
2579 result to be stored to DEST. */
2581 void
2582 c_expr::gen_transform (FILE *f, int indent, const char *dest,
2583 bool, int, const char *, capture_info *,
2584 dt_operand **, int)
2586 if (dest && nr_stmts == 1)
2587 fprintf_indent (f, indent, "%s = ", dest);
2589 unsigned stmt_nr = 1;
2590 int prev_line = -1;
2591 for (unsigned i = 0; i < code.length (); ++i)
2593 const cpp_token *token = &code[i];
2595 /* We can't recover from all lexing losses but we can roughly restore line
2596 breaks from location info. */
2597 const line_map_ordinary *map;
2598 linemap_resolve_location (line_table, token->src_loc,
2599 LRK_SPELLING_LOCATION, &map);
2600 expanded_location loc = linemap_expand_location (line_table, map,
2601 token->src_loc);
2602 if (prev_line != -1 && loc.line != prev_line)
2603 fputc ('\n', f);
2604 prev_line = loc.line;
2606 /* Replace captures for code-gen. */
2607 if (token->type == CPP_ATSIGN)
2609 const cpp_token *n = &code[i+1];
2610 if ((n->type == CPP_NUMBER
2611 || n->type == CPP_NAME)
2612 && !(n->flags & PREV_WHITE))
2614 if (token->flags & PREV_WHITE)
2615 fputc (' ', f);
2616 const char *id;
2617 if (n->type == CPP_NUMBER)
2618 id = (const char *)n->val.str.text;
2619 else
2620 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2621 unsigned *cid = capture_ids->get (id);
2622 if (!cid)
2623 fatal_at (token, "unknown capture id");
2624 fprintf (f, "captures[%u]", *cid);
2625 ++i;
2626 continue;
2630 if (token->flags & PREV_WHITE)
2631 fputc (' ', f);
2633 if (token->type == CPP_NAME)
2635 const char *id = (const char *) NODE_NAME (token->val.node.node);
2636 unsigned j;
2637 for (j = 0; j < ids.length (); ++j)
2639 if (strcmp (id, ids[j].id) == 0)
2641 fprintf (f, "%s", ids[j].oper);
2642 break;
2645 if (j < ids.length ())
2646 continue;
2649 /* Output the token as string. */
2650 char *tk = (char *)cpp_token_as_text (r, token);
2651 fputs (tk, f);
2653 if (token->type == CPP_SEMICOLON)
2655 stmt_nr++;
2656 if (dest && stmt_nr == nr_stmts)
2657 fprintf_indent (f, indent, "%s = ", dest);
2660 fputc ('\n', f);
2663 /* Generate transform code for a capture. */
2665 void
2666 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2667 int depth, const char *in_type, capture_info *cinfo,
2668 dt_operand **indexes, int cond_handling)
2670 if (what && is_a<expr *> (what))
2672 if (indexes[where] == 0)
2674 char buf[20];
2675 snprintf (buf, sizeof (buf), "captures[%u]", where);
2676 what->gen_transform (f, indent, buf, gimple, depth, in_type,
2677 cinfo, NULL);
2681 /* If in GENERIC some capture is used multiple times, unshare it except
2682 when emitting the last use. */
2683 if (!gimple
2684 && cinfo->info.exists ()
2685 && cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
2687 fprintf_indent (f, indent, "%s = unshare_expr (captures[%u]);\n",
2688 dest, where);
2689 cinfo->info[cinfo->info[where].same_as].result_use_count--;
2691 else
2692 fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2694 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2695 with substituting a capture of that. */
2696 if (gimple
2697 && cond_handling != 0
2698 && cinfo->info[where].cond_expr_cond_p)
2700 /* If substituting into a cond_expr condition, unshare. */
2701 if (cond_handling == 1)
2702 fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
2703 /* If substituting elsewhere we might need to decompose it. */
2704 else if (cond_handling == 2)
2706 /* ??? Returning false here will also not allow any other patterns
2707 to match unless this generator was split out. */
2708 fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2709 fprintf_indent (f, indent, " {\n");
2710 fprintf_indent (f, indent, " if (!seq) return false;\n");
2711 fprintf_indent (f, indent, " %s = gimple_build (seq,"
2712 " TREE_CODE (%s),"
2713 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2714 " TREE_OPERAND (%s, 1));\n",
2715 dest, dest, dest, dest, dest);
2716 fprintf_indent (f, indent, " }\n");
2721 /* Return the name of the operand representing the decision tree node.
2722 Use NAME as space to generate it. */
2724 char *
2725 dt_operand::get_name (char *name)
2727 if (! parent)
2728 sprintf (name, "t");
2729 else if (parent->level == 1)
2730 sprintf (name, "_p%u", pos);
2731 else if (parent->type == dt_node::DT_MATCH)
2732 return as_a <dt_operand *> (parent)->get_name (name);
2733 else
2734 sprintf (name, "_q%u%u", parent->level, pos);
2735 return name;
2738 /* Fill NAME with the operand name at position POS. */
2740 void
2741 dt_operand::gen_opname (char *name, unsigned pos)
2743 if (! parent)
2744 sprintf (name, "_p%u", pos);
2745 else
2746 sprintf (name, "_q%u%u", level, pos);
2749 /* Generate matching code for the decision tree operand which is
2750 a predicate. */
2752 unsigned
2753 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2755 predicate *p = as_a <predicate *> (op);
2757 if (p->p->matchers.exists ())
2759 /* If this is a predicate generated from a pattern mangle its
2760 name and pass on the valueize hook. */
2761 if (gimple)
2762 fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2763 p->p->id, opname);
2764 else
2765 fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2767 else
2768 fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2769 fprintf_indent (f, indent + 2, "{\n");
2770 return 1;
2773 /* Generate matching code for the decision tree operand which is
2774 a capture-match. */
2776 unsigned
2777 dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
2779 char match_opname[20];
2780 match_dop->get_name (match_opname);
2781 if (value_match)
2782 fprintf_indent (f, indent, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2783 "|| operand_equal_p (%s, %s, 0))\n",
2784 opname, match_opname, opname, opname, match_opname);
2785 else
2786 fprintf_indent (f, indent, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2787 "|| (operand_equal_p (%s, %s, 0) "
2788 "&& types_match (%s, %s)))\n",
2789 opname, match_opname, opname, opname, match_opname,
2790 opname, match_opname);
2791 fprintf_indent (f, indent + 2, "{\n");
2792 return 1;
2795 /* Generate GIMPLE matching code for the decision tree operand. */
2797 unsigned
2798 dt_operand::gen_gimple_expr (FILE *f, int indent, int depth)
2800 expr *e = static_cast<expr *> (op);
2801 id_base *id = e->operation;
2802 unsigned n_ops = e->ops.length ();
2803 unsigned n_braces = 0;
2805 for (unsigned i = 0; i < n_ops; ++i)
2807 char child_opname[20];
2808 gen_opname (child_opname, i);
2810 if (id->kind == id_base::CODE)
2812 if (e->is_generic
2813 || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2814 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2816 /* ??? If this is a memory operation we can't (and should not)
2817 match this. The only sensible operand types are
2818 SSA names and invariants. */
2819 if (e->is_generic)
2821 char opname[20];
2822 get_name (opname);
2823 fprintf_indent (f, indent,
2824 "tree %s = TREE_OPERAND (%s, %i);\n",
2825 child_opname, opname, i);
2827 else
2828 fprintf_indent (f, indent,
2829 "tree %s = TREE_OPERAND "
2830 "(gimple_assign_rhs1 (_a%d), %i);\n",
2831 child_opname, depth, i);
2832 fprintf_indent (f, indent,
2833 "if ((TREE_CODE (%s) == SSA_NAME\n",
2834 child_opname);
2835 fprintf_indent (f, indent,
2836 " || is_gimple_min_invariant (%s)))\n",
2837 child_opname);
2838 fprintf_indent (f, indent,
2839 " {\n");
2840 indent += 4;
2841 n_braces++;
2842 fprintf_indent (f, indent,
2843 "%s = do_valueize (valueize, %s);\n",
2844 child_opname, child_opname);
2845 continue;
2847 else
2848 fprintf_indent (f, indent,
2849 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2850 child_opname, i + 1, depth);
2852 else
2853 fprintf_indent (f, indent,
2854 "tree %s = gimple_call_arg (_c%d, %u);\n",
2855 child_opname, depth, i);
2856 fprintf_indent (f, indent,
2857 "%s = do_valueize (valueize, %s);\n",
2858 child_opname, child_opname);
2860 /* While the toplevel operands are canonicalized by the caller
2861 after valueizing operands of sub-expressions we have to
2862 re-canonicalize operand order. */
2863 int opno = commutative_op (id);
2864 if (opno >= 0)
2866 char child_opname0[20], child_opname1[20];
2867 gen_opname (child_opname0, opno);
2868 gen_opname (child_opname1, opno + 1);
2869 fprintf_indent (f, indent,
2870 "if (tree_swap_operands_p (%s, %s))\n",
2871 child_opname0, child_opname1);
2872 fprintf_indent (f, indent,
2873 " std::swap (%s, %s);\n",
2874 child_opname0, child_opname1);
2877 return n_braces;
2880 /* Generate GENERIC matching code for the decision tree operand. */
2882 unsigned
2883 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2885 expr *e = static_cast<expr *> (op);
2886 unsigned n_ops = e->ops.length ();
2888 for (unsigned i = 0; i < n_ops; ++i)
2890 char child_opname[20];
2891 gen_opname (child_opname, i);
2893 if (e->operation->kind == id_base::CODE)
2894 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2895 child_opname, opname, i);
2896 else
2897 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2898 child_opname, opname, i);
2901 return 0;
2904 /* Generate matching code for the children of the decision tree node. */
2906 void
2907 dt_node::gen_kids (FILE *f, int indent, bool gimple, int depth)
2909 auto_vec<dt_operand *> gimple_exprs;
2910 auto_vec<dt_operand *> generic_exprs;
2911 auto_vec<dt_operand *> fns;
2912 auto_vec<dt_operand *> generic_fns;
2913 auto_vec<dt_operand *> preds;
2914 auto_vec<dt_node *> others;
2916 for (unsigned i = 0; i < kids.length (); ++i)
2918 if (kids[i]->type == dt_node::DT_OPERAND)
2920 dt_operand *op = as_a<dt_operand *> (kids[i]);
2921 if (expr *e = dyn_cast <expr *> (op->op))
2923 if (e->ops.length () == 0
2924 && (!gimple || !(*e->operation == CONSTRUCTOR)))
2925 generic_exprs.safe_push (op);
2926 else if (e->operation->kind == id_base::FN)
2928 if (gimple)
2929 fns.safe_push (op);
2930 else
2931 generic_fns.safe_push (op);
2933 else if (e->operation->kind == id_base::PREDICATE)
2934 preds.safe_push (op);
2935 else
2937 if (gimple && !e->is_generic)
2938 gimple_exprs.safe_push (op);
2939 else
2940 generic_exprs.safe_push (op);
2943 else if (op->op->type == operand::OP_PREDICATE)
2944 others.safe_push (kids[i]);
2945 else
2946 gcc_unreachable ();
2948 else if (kids[i]->type == dt_node::DT_SIMPLIFY)
2949 others.safe_push (kids[i]);
2950 else if (kids[i]->type == dt_node::DT_MATCH
2951 || kids[i]->type == dt_node::DT_TRUE)
2953 /* A DT_TRUE operand serves as a barrier - generate code now
2954 for what we have collected sofar.
2955 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2956 dependent matches to get out-of-order. Generate code now
2957 for what we have collected sofar. */
2958 gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
2959 fns, generic_fns, preds, others);
2960 /* And output the true operand itself. */
2961 kids[i]->gen (f, indent, gimple, depth);
2962 gimple_exprs.truncate (0);
2963 generic_exprs.truncate (0);
2964 fns.truncate (0);
2965 generic_fns.truncate (0);
2966 preds.truncate (0);
2967 others.truncate (0);
2969 else
2970 gcc_unreachable ();
2973 /* Generate code for the remains. */
2974 gen_kids_1 (f, indent, gimple, depth, gimple_exprs, generic_exprs,
2975 fns, generic_fns, preds, others);
2978 /* Generate matching code for the children of the decision tree node. */
2980 void
2981 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, int depth,
2982 vec<dt_operand *> gimple_exprs,
2983 vec<dt_operand *> generic_exprs,
2984 vec<dt_operand *> fns,
2985 vec<dt_operand *> generic_fns,
2986 vec<dt_operand *> preds,
2987 vec<dt_node *> others)
2989 char buf[128];
2990 char *kid_opname = buf;
2992 unsigned exprs_len = gimple_exprs.length ();
2993 unsigned gexprs_len = generic_exprs.length ();
2994 unsigned fns_len = fns.length ();
2995 unsigned gfns_len = generic_fns.length ();
2997 if (exprs_len || fns_len || gexprs_len || gfns_len)
2999 if (exprs_len)
3000 gimple_exprs[0]->get_name (kid_opname);
3001 else if (fns_len)
3002 fns[0]->get_name (kid_opname);
3003 else if (gfns_len)
3004 generic_fns[0]->get_name (kid_opname);
3005 else
3006 generic_exprs[0]->get_name (kid_opname);
3008 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
3009 fprintf_indent (f, indent, " {\n");
3010 indent += 2;
3013 if (exprs_len || fns_len)
3015 depth++;
3016 fprintf_indent (f, indent,
3017 "case SSA_NAME:\n");
3018 fprintf_indent (f, indent,
3019 " if (gimple *_d%d = get_def (valueize, %s))\n",
3020 depth, kid_opname);
3021 fprintf_indent (f, indent,
3022 " {\n");
3023 indent += 6;
3024 if (exprs_len)
3026 fprintf_indent (f, indent,
3027 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3028 depth, depth);
3029 fprintf_indent (f, indent,
3030 " switch (gimple_assign_rhs_code (_a%d))\n",
3031 depth);
3032 indent += 4;
3033 fprintf_indent (f, indent, "{\n");
3034 for (unsigned i = 0; i < exprs_len; ++i)
3036 expr *e = as_a <expr *> (gimple_exprs[i]->op);
3037 id_base *op = e->operation;
3038 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3039 fprintf_indent (f, indent, "CASE_CONVERT:\n");
3040 else
3041 fprintf_indent (f, indent, "case %s:\n", op->id);
3042 fprintf_indent (f, indent, " {\n");
3043 gimple_exprs[i]->gen (f, indent + 4, true, depth);
3044 fprintf_indent (f, indent, " break;\n");
3045 fprintf_indent (f, indent, " }\n");
3047 fprintf_indent (f, indent, "default:;\n");
3048 fprintf_indent (f, indent, "}\n");
3049 indent -= 4;
3052 if (fns_len)
3054 fprintf_indent (f, indent,
3055 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3056 exprs_len ? "else " : "", depth, depth);
3057 fprintf_indent (f, indent,
3058 " switch (gimple_call_combined_fn (_c%d))\n",
3059 depth);
3061 indent += 4;
3062 fprintf_indent (f, indent, "{\n");
3063 for (unsigned i = 0; i < fns_len; ++i)
3065 expr *e = as_a <expr *>(fns[i]->op);
3066 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
3067 /* We need to be defensive against bogus prototypes allowing
3068 calls with not enough arguments. */
3069 fprintf_indent (f, indent,
3070 " if (gimple_call_num_args (_c%d) == %d)\n",
3071 depth, e->ops.length ());
3072 fprintf_indent (f, indent, " {\n");
3073 fns[i]->gen (f, indent + 6, true, depth);
3074 fprintf_indent (f, indent, " }\n");
3075 fprintf_indent (f, indent, " break;\n");
3078 fprintf_indent (f, indent, "default:;\n");
3079 fprintf_indent (f, indent, "}\n");
3080 indent -= 4;
3083 indent -= 6;
3084 depth--;
3085 fprintf_indent (f, indent, " }\n");
3086 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3087 here rather than in the next loop. */
3088 for (unsigned i = 0; i < generic_exprs.length (); ++i)
3090 expr *e = as_a <expr *>(generic_exprs[i]->op);
3091 id_base *op = e->operation;
3092 if (*op == SSA_NAME && (exprs_len || fns_len))
3094 fprintf_indent (f, indent + 4, "{\n");
3095 generic_exprs[i]->gen (f, indent + 6, gimple, depth);
3096 fprintf_indent (f, indent + 4, "}\n");
3100 fprintf_indent (f, indent, " break;\n");
3103 for (unsigned i = 0; i < generic_exprs.length (); ++i)
3105 expr *e = as_a <expr *>(generic_exprs[i]->op);
3106 id_base *op = e->operation;
3107 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3108 fprintf_indent (f, indent, "CASE_CONVERT:\n");
3109 else if (*op == SSA_NAME && (exprs_len || fns_len))
3110 /* Already handled above. */
3111 continue;
3112 else
3113 fprintf_indent (f, indent, "case %s:\n", op->id);
3114 fprintf_indent (f, indent, " {\n");
3115 generic_exprs[i]->gen (f, indent + 4, gimple, depth);
3116 fprintf_indent (f, indent, " break;\n");
3117 fprintf_indent (f, indent, " }\n");
3120 if (gfns_len)
3122 fprintf_indent (f, indent,
3123 "case CALL_EXPR:\n");
3124 fprintf_indent (f, indent,
3125 " switch (get_call_combined_fn (%s))\n",
3126 kid_opname);
3127 fprintf_indent (f, indent,
3128 " {\n");
3129 indent += 4;
3131 for (unsigned j = 0; j < generic_fns.length (); ++j)
3133 expr *e = as_a <expr *>(generic_fns[j]->op);
3134 gcc_assert (e->operation->kind == id_base::FN);
3136 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
3137 fprintf_indent (f, indent, " if (call_expr_nargs (%s) == %d)\n"
3138 " {\n", kid_opname, e->ops.length ());
3139 generic_fns[j]->gen (f, indent + 6, false, depth);
3140 fprintf_indent (f, indent, " }\n"
3141 " break;\n");
3143 fprintf_indent (f, indent, "default:;\n");
3145 indent -= 4;
3146 fprintf_indent (f, indent, " }\n");
3147 fprintf_indent (f, indent, " break;\n");
3150 /* Close switch (TREE_CODE ()). */
3151 if (exprs_len || fns_len || gexprs_len || gfns_len)
3153 indent -= 4;
3154 fprintf_indent (f, indent, " default:;\n");
3155 fprintf_indent (f, indent, " }\n");
3158 for (unsigned i = 0; i < preds.length (); ++i)
3160 expr *e = as_a <expr *> (preds[i]->op);
3161 predicate_id *p = as_a <predicate_id *> (e->operation);
3162 preds[i]->get_name (kid_opname);
3163 fprintf_indent (f, indent, "{\n");
3164 indent += 2;
3165 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
3166 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
3167 gimple ? "gimple" : "tree",
3168 p->id, kid_opname, kid_opname,
3169 gimple ? ", valueize" : "");
3170 fprintf_indent (f, indent, " {\n");
3171 for (int j = 0; j < p->nargs; ++j)
3173 char child_opname[20];
3174 preds[i]->gen_opname (child_opname, j);
3175 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
3176 child_opname, kid_opname, j);
3178 preds[i]->gen_kids (f, indent + 4, gimple, depth);
3179 fprintf (f, "}\n");
3180 indent -= 2;
3181 fprintf_indent (f, indent, "}\n");
3184 for (unsigned i = 0; i < others.length (); ++i)
3185 others[i]->gen (f, indent, gimple, depth);
3188 /* Generate matching code for the decision tree operand. */
3190 void
3191 dt_operand::gen (FILE *f, int indent, bool gimple, int depth)
3193 char opname[20];
3194 get_name (opname);
3196 unsigned n_braces = 0;
3198 if (type == DT_OPERAND)
3199 switch (op->type)
3201 case operand::OP_PREDICATE:
3202 n_braces = gen_predicate (f, indent, opname, gimple);
3203 break;
3205 case operand::OP_EXPR:
3206 if (gimple)
3207 n_braces = gen_gimple_expr (f, indent, depth);
3208 else
3209 n_braces = gen_generic_expr (f, indent, opname);
3210 break;
3212 default:
3213 gcc_unreachable ();
3215 else if (type == DT_TRUE)
3217 else if (type == DT_MATCH)
3218 n_braces = gen_match_op (f, indent, opname, gimple);
3219 else
3220 gcc_unreachable ();
3222 indent += 4 * n_braces;
3223 gen_kids (f, indent, gimple, depth);
3225 for (unsigned i = 0; i < n_braces; ++i)
3227 indent -= 4;
3228 if (indent < 0)
3229 indent = 0;
3230 fprintf_indent (f, indent, " }\n");
3235 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3236 step of a '(simplify ...)' or '(match ...)'. This handles everything
3237 that is not part of the decision tree (simplify->match).
3238 Main recursive worker. */
3240 void
3241 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3243 if (result)
3245 if (with_expr *w = dyn_cast <with_expr *> (result))
3247 fprintf_indent (f, indent, "{\n");
3248 indent += 4;
3249 output_line_directive (f, w->location);
3250 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3251 gen_1 (f, indent, gimple, w->subexpr);
3252 indent -= 4;
3253 fprintf_indent (f, indent, "}\n");
3254 return;
3256 else if (if_expr *ife = dyn_cast <if_expr *> (result))
3258 output_line_directive (f, ife->location);
3259 fprintf_indent (f, indent, "if (");
3260 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3261 fprintf (f, ")\n");
3262 fprintf_indent (f, indent + 2, "{\n");
3263 indent += 4;
3264 gen_1 (f, indent, gimple, ife->trueexpr);
3265 indent -= 4;
3266 fprintf_indent (f, indent + 2, "}\n");
3267 if (ife->falseexpr)
3269 fprintf_indent (f, indent, "else\n");
3270 fprintf_indent (f, indent + 2, "{\n");
3271 indent += 4;
3272 gen_1 (f, indent, gimple, ife->falseexpr);
3273 indent -= 4;
3274 fprintf_indent (f, indent + 2, "}\n");
3276 return;
3280 static unsigned fail_label_cnt;
3281 char local_fail_label[256];
3282 snprintf (local_fail_label, 256, "next_after_fail%u", ++fail_label_cnt);
3283 fail_label = local_fail_label;
3285 /* Analyze captures and perform early-outs on the incoming arguments
3286 that cover cases we cannot handle. */
3287 capture_info cinfo (s, result, gimple);
3288 if (s->kind == simplify::SIMPLIFY)
3290 if (!gimple)
3292 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3293 if (cinfo.force_no_side_effects & (1 << i))
3295 fprintf_indent (f, indent,
3296 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3297 i, fail_label);
3298 if (verbose >= 1)
3299 warning_at (as_a <expr *> (s->match)->ops[i]->location,
3300 "forcing toplevel operand to have no "
3301 "side-effects");
3303 for (int i = 0; i <= s->capture_max; ++i)
3304 if (cinfo.info[i].cse_p)
3306 else if (cinfo.info[i].force_no_side_effects_p
3307 && (cinfo.info[i].toplevel_msk
3308 & cinfo.force_no_side_effects) == 0)
3310 fprintf_indent (f, indent,
3311 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3312 "goto %s;\n", i, fail_label);
3313 if (verbose >= 1)
3314 warning_at (cinfo.info[i].c->location,
3315 "forcing captured operand to have no "
3316 "side-effects");
3318 else if ((cinfo.info[i].toplevel_msk
3319 & cinfo.force_no_side_effects) != 0)
3320 /* Mark capture as having no side-effects if we had to verify
3321 that via forced toplevel operand checks. */
3322 cinfo.info[i].force_no_side_effects_p = true;
3324 if (gimple)
3326 /* Force single-use restriction by only allowing simple
3327 results via setting seq to NULL. */
3328 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
3329 bool first_p = true;
3330 for (int i = 0; i <= s->capture_max; ++i)
3331 if (cinfo.info[i].force_single_use)
3333 if (first_p)
3335 fprintf_indent (f, indent, "if (lseq\n");
3336 fprintf_indent (f, indent, " && (");
3337 first_p = false;
3339 else
3341 fprintf (f, "\n");
3342 fprintf_indent (f, indent, " || ");
3344 fprintf (f, "!single_use (captures[%d])", i);
3346 if (!first_p)
3348 fprintf (f, "))\n");
3349 fprintf_indent (f, indent, " lseq = NULL;\n");
3354 if (s->kind == simplify::SIMPLIFY)
3355 fprintf_indent (f, indent, "if (__builtin_expect (!dbg_cnt (match), 0)) goto %s;\n", fail_label);
3357 fprintf_indent (f, indent, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3358 "fprintf (dump_file, \"%s ",
3359 s->kind == simplify::SIMPLIFY
3360 ? "Applying pattern" : "Matching expression");
3361 fprintf (f, "%%s:%%d, %%s:%%d\\n\", ");
3362 output_line_directive (f,
3363 result ? result->location : s->match->location, true,
3364 true);
3365 fprintf (f, ", __FILE__, __LINE__);\n");
3367 fprintf_indent (f, indent, "{\n");
3368 indent += 2;
3369 if (!result)
3371 /* If there is no result then this is a predicate implementation. */
3372 fprintf_indent (f, indent, "return true;\n");
3374 else if (gimple)
3376 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3377 in outermost position). */
3378 if (result->type == operand::OP_EXPR
3379 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
3380 result = as_a <expr *> (result)->ops[0];
3381 if (result->type == operand::OP_EXPR)
3383 expr *e = as_a <expr *> (result);
3384 id_base *opr = e->operation;
3385 bool is_predicate = false;
3386 /* When we delay operator substituting during lowering of fors we
3387 make sure that for code-gen purposes the effects of each substitute
3388 are the same. Thus just look at that. */
3389 if (user_id *uid = dyn_cast <user_id *> (opr))
3390 opr = uid->substitutes[0];
3391 else if (is_a <predicate_id *> (opr))
3392 is_predicate = true;
3393 if (!is_predicate)
3394 fprintf_indent (f, indent, "res_op->set_op (%s, type, %d);\n",
3395 *e->operation == CONVERT_EXPR
3396 ? "NOP_EXPR" : e->operation->id,
3397 e->ops.length ());
3398 for (unsigned j = 0; j < e->ops.length (); ++j)
3400 char dest[32];
3401 if (is_predicate)
3402 snprintf (dest, sizeof (dest), "res_ops[%d]", j);
3403 else
3404 snprintf (dest, sizeof (dest), "res_op->ops[%d]", j);
3405 const char *optype
3406 = get_operand_type (opr, j,
3407 "type", e->expr_type,
3408 j == 0 ? NULL
3409 : "TREE_TYPE (res_op->ops[0])");
3410 /* We need to expand GENERIC conditions we captured from
3411 COND_EXPRs and we need to unshare them when substituting
3412 into COND_EXPRs. */
3413 int cond_handling = 0;
3414 if (!is_predicate)
3415 cond_handling = (*opr == COND_EXPR && j == 0) ? 1 : 2;
3416 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3417 &cinfo, indexes, cond_handling);
3420 /* Re-fold the toplevel result. It's basically an embedded
3421 gimple_build w/o actually building the stmt. */
3422 if (!is_predicate)
3424 fprintf_indent (f, indent,
3425 "res_op->resimplify (lseq, valueize);\n");
3426 if (e->force_leaf)
3427 fprintf_indent (f, indent,
3428 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3429 "goto %s;\n", fail_label);
3432 else if (result->type == operand::OP_CAPTURE
3433 || result->type == operand::OP_C_EXPR)
3435 fprintf_indent (f, indent, "tree tem;\n");
3436 result->gen_transform (f, indent, "tem", true, 1, "type",
3437 &cinfo, indexes);
3438 fprintf_indent (f, indent, "res_op->set_value (tem);\n");
3439 if (is_a <capture *> (result)
3440 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3442 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3443 with substituting a capture of that. */
3444 fprintf_indent (f, indent,
3445 "if (COMPARISON_CLASS_P (tem))\n");
3446 fprintf_indent (f, indent,
3447 " {\n");
3448 fprintf_indent (f, indent,
3449 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3450 fprintf_indent (f, indent,
3451 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3452 fprintf_indent (f, indent,
3453 " }\n");
3456 else
3457 gcc_unreachable ();
3458 fprintf_indent (f, indent, "return true;\n");
3460 else /* GENERIC */
3462 bool is_predicate = false;
3463 if (result->type == operand::OP_EXPR)
3465 expr *e = as_a <expr *> (result);
3466 id_base *opr = e->operation;
3467 /* When we delay operator substituting during lowering of fors we
3468 make sure that for code-gen purposes the effects of each substitute
3469 are the same. Thus just look at that. */
3470 if (user_id *uid = dyn_cast <user_id *> (opr))
3471 opr = uid->substitutes[0];
3472 else if (is_a <predicate_id *> (opr))
3473 is_predicate = true;
3474 /* Search for captures used multiple times in the result expression
3475 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3476 original expression. */
3477 if (!is_predicate)
3478 for (int i = 0; i < s->capture_max + 1; ++i)
3480 if (cinfo.info[i].same_as != (unsigned)i
3481 || cinfo.info[i].cse_p)
3482 continue;
3483 if (cinfo.info[i].result_use_count
3484 > cinfo.info[i].match_use_count)
3485 fprintf_indent (f, indent,
3486 "if (! tree_invariant_p (captures[%d])) "
3487 "goto %s;\n", i, fail_label);
3489 for (unsigned j = 0; j < e->ops.length (); ++j)
3491 char dest[32];
3492 if (is_predicate)
3493 snprintf (dest, sizeof (dest), "res_ops[%d]", j);
3494 else
3496 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3497 snprintf (dest, sizeof (dest), "res_op%d", j);
3499 const char *optype
3500 = get_operand_type (opr, j,
3501 "type", e->expr_type,
3502 j == 0
3503 ? NULL : "TREE_TYPE (res_op0)");
3504 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3505 &cinfo, indexes);
3507 if (is_predicate)
3508 fprintf_indent (f, indent, "return true;\n");
3509 else
3511 fprintf_indent (f, indent, "tree _r;\n");
3512 /* Re-fold the toplevel result. Use non_lvalue to
3513 build NON_LVALUE_EXPRs so they get properly
3514 ignored when in GIMPLE form. */
3515 if (*opr == NON_LVALUE_EXPR)
3516 fprintf_indent (f, indent,
3517 "_r = non_lvalue_loc (loc, res_op0);\n");
3518 else
3520 if (is_a <operator_id *> (opr))
3521 fprintf_indent (f, indent,
3522 "_r = fold_build%d_loc (loc, %s, type",
3523 e->ops.length (),
3524 *e->operation == CONVERT_EXPR
3525 ? "NOP_EXPR" : e->operation->id);
3526 else
3527 fprintf_indent (f, indent,
3528 "_r = maybe_build_call_expr_loc (loc, "
3529 "%s, type, %d", e->operation->id,
3530 e->ops.length());
3531 for (unsigned j = 0; j < e->ops.length (); ++j)
3532 fprintf (f, ", res_op%d", j);
3533 fprintf (f, ");\n");
3534 if (!is_a <operator_id *> (opr))
3536 fprintf_indent (f, indent, "if (!_r)\n");
3537 fprintf_indent (f, indent, " goto %s;\n", fail_label);
3542 else if (result->type == operand::OP_CAPTURE
3543 || result->type == operand::OP_C_EXPR)
3546 fprintf_indent (f, indent, "tree _r;\n");
3547 result->gen_transform (f, indent, "_r", false, 1, "type",
3548 &cinfo, indexes);
3550 else
3551 gcc_unreachable ();
3552 if (!is_predicate)
3554 /* Search for captures not used in the result expression and dependent
3555 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3556 for (int i = 0; i < s->capture_max + 1; ++i)
3558 if (cinfo.info[i].same_as != (unsigned)i)
3559 continue;
3560 if (!cinfo.info[i].force_no_side_effects_p
3561 && !cinfo.info[i].expr_p
3562 && cinfo.info[i].result_use_count == 0)
3564 fprintf_indent (f, indent,
3565 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3567 fprintf_indent (f, indent + 2,
3568 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3569 "fold_ignored_result (captures[%d]), _r);\n",
3573 fprintf_indent (f, indent, "return _r;\n");
3576 indent -= 2;
3577 fprintf_indent (f, indent, "}\n");
3578 fprintf (f, "%s:;\n", fail_label);
3579 fail_label = NULL;
3582 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3583 step of a '(simplify ...)' or '(match ...)'. This handles everything
3584 that is not part of the decision tree (simplify->match). */
3586 void
3587 dt_simplify::gen (FILE *f, int indent, bool gimple, int depth ATTRIBUTE_UNUSED)
3589 fprintf_indent (f, indent, "{\n");
3590 indent += 2;
3591 output_line_directive (f,
3592 s->result ? s->result->location : s->match->location);
3593 if (s->capture_max >= 0)
3595 char opname[20];
3596 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3597 s->capture_max + 1, indexes[0]->get_name (opname));
3599 for (int i = 1; i <= s->capture_max; ++i)
3601 if (!indexes[i])
3602 break;
3603 fprintf (f, ", %s", indexes[i]->get_name (opname));
3605 fprintf (f, " };\n");
3608 /* If we have a split-out function for the actual transform, call it. */
3609 if (info && info->fname)
3611 if (gimple)
3613 fprintf_indent (f, indent, "if (%s (res_op, seq, "
3614 "valueize, type, captures", info->fname);
3615 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3616 if (s->for_subst_vec[i].first->used)
3617 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3618 fprintf (f, "))\n");
3619 fprintf_indent (f, indent, " return true;\n");
3621 else
3623 fprintf_indent (f, indent, "tree res = %s (loc, type",
3624 info->fname);
3625 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3626 fprintf (f, ", _p%d", i);
3627 fprintf (f, ", captures");
3628 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3630 if (s->for_subst_vec[i].first->used)
3631 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3633 fprintf (f, ");\n");
3634 fprintf_indent (f, indent, "if (res) return res;\n");
3637 else
3639 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3641 if (! s->for_subst_vec[i].first->used)
3642 continue;
3643 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3644 fprintf_indent (f, indent, "const enum tree_code %s = %s;\n",
3645 s->for_subst_vec[i].first->id,
3646 s->for_subst_vec[i].second->id);
3647 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3648 fprintf_indent (f, indent, "const combined_fn %s = %s;\n",
3649 s->for_subst_vec[i].first->id,
3650 s->for_subst_vec[i].second->id);
3651 else
3652 gcc_unreachable ();
3654 gen_1 (f, indent, gimple, s->result);
3657 indent -= 2;
3658 fprintf_indent (f, indent, "}\n");
3662 /* Hash function for finding equivalent transforms. */
3664 hashval_t
3665 sinfo_hashmap_traits::hash (const key_type &v)
3667 /* Only bother to compare those originating from the same source pattern. */
3668 return v->s->result->location;
3671 /* Compare function for finding equivalent transforms. */
3673 static bool
3674 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3676 if (o1->type != o2->type)
3677 return false;
3679 switch (o1->type)
3681 case operand::OP_IF:
3683 if_expr *if1 = as_a <if_expr *> (o1);
3684 if_expr *if2 = as_a <if_expr *> (o2);
3685 /* ??? Properly compare c-exprs. */
3686 if (if1->cond != if2->cond)
3687 return false;
3688 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3689 return false;
3690 if (if1->falseexpr != if2->falseexpr
3691 || (if1->falseexpr
3692 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3693 return false;
3694 return true;
3696 case operand::OP_WITH:
3698 with_expr *with1 = as_a <with_expr *> (o1);
3699 with_expr *with2 = as_a <with_expr *> (o2);
3700 if (with1->with != with2->with)
3701 return false;
3702 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3704 default:;
3707 /* We've hit a result. Time to compare capture-infos - this is required
3708 in addition to the conservative pointer-equivalency of the result IL. */
3709 capture_info cinfo1 (s1, o1, true);
3710 capture_info cinfo2 (s2, o2, true);
3712 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3713 || cinfo1.info.length () != cinfo2.info.length ())
3714 return false;
3716 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3718 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3719 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3720 || (cinfo1.info[i].force_no_side_effects_p
3721 != cinfo2.info[i].force_no_side_effects_p)
3722 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3723 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3724 /* toplevel_msk is an optimization */
3725 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3726 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3727 /* the pointer back to the capture is for diagnostics only */)
3728 return false;
3731 /* ??? Deep-compare the actual result. */
3732 return o1 == o2;
3735 bool
3736 sinfo_hashmap_traits::equal_keys (const key_type &v,
3737 const key_type &candidate)
3739 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3743 /* Main entry to generate code for matching GIMPLE IL off the decision
3744 tree. */
3746 void
3747 decision_tree::gen (FILE *f, bool gimple)
3749 sinfo_map_t si;
3751 root->analyze (si);
3753 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3754 "a total number of %u nodes\n",
3755 gimple ? "GIMPLE" : "GENERIC",
3756 root->num_leafs, root->max_level, root->total_size);
3758 /* First split out the transform part of equal leafs. */
3759 unsigned rcnt = 0;
3760 unsigned fcnt = 1;
3761 for (sinfo_map_t::iterator iter = si.begin ();
3762 iter != si.end (); ++iter)
3764 sinfo *s = (*iter).second;
3765 /* Do not split out single uses. */
3766 if (s->cnt <= 1)
3767 continue;
3769 rcnt += s->cnt - 1;
3770 if (verbose >= 1)
3772 fprintf (stderr, "found %u uses of", s->cnt);
3773 output_line_directive (stderr, s->s->s->result->location);
3776 /* Generate a split out function with the leaf transform code. */
3777 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3778 fcnt++);
3779 if (gimple)
3780 fprintf (f, "\nstatic bool\n"
3781 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3782 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3783 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3784 "(captures)\n",
3785 s->fname);
3786 else
3788 fprintf (f, "\nstatic tree\n"
3789 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3790 (*iter).second->fname);
3791 for (unsigned i = 0;
3792 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3793 fprintf (f, " tree ARG_UNUSED (_p%d),", i);
3794 fprintf (f, " tree *captures\n");
3796 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3798 if (! s->s->s->for_subst_vec[i].first->used)
3799 continue;
3800 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3801 fprintf (f, ", const enum tree_code ARG_UNUSED (%s)",
3802 s->s->s->for_subst_vec[i].first->id);
3803 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3804 fprintf (f, ", const combined_fn ARG_UNUSED (%s)",
3805 s->s->s->for_subst_vec[i].first->id);
3808 fprintf (f, ")\n{\n");
3809 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3810 if (gimple)
3811 fprintf (f, " return false;\n");
3812 else
3813 fprintf (f, " return NULL_TREE;\n");
3814 fprintf (f, "}\n");
3816 fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3818 for (unsigned n = 1; n <= 5; ++n)
3820 bool has_kids_p = false;
3822 /* First generate split-out functions. */
3823 for (unsigned j = 0; j < root->kids.length (); j++)
3825 dt_operand *dop = static_cast<dt_operand *>(root->kids[j]);
3826 expr *e = static_cast<expr *>(dop->op);
3827 if (e->ops.length () != n
3828 /* Builtin simplifications are somewhat premature on
3829 GENERIC. The following drops patterns with outermost
3830 calls. It's easy to emit overloads for function code
3831 though if necessary. */
3832 || (!gimple
3833 && e->operation->kind != id_base::CODE))
3834 continue;
3836 if (gimple)
3837 fprintf (f, "\nstatic bool\n"
3838 "gimple_simplify_%s (gimple_match_op *res_op,"
3839 " gimple_seq *seq,\n"
3840 " tree (*valueize)(tree) "
3841 "ATTRIBUTE_UNUSED,\n"
3842 " code_helper ARG_UNUSED (code), tree "
3843 "ARG_UNUSED (type)\n",
3844 e->operation->id);
3845 else
3846 fprintf (f, "\nstatic tree\n"
3847 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3848 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3849 e->operation->id);
3850 for (unsigned i = 0; i < n; ++i)
3851 fprintf (f, ", tree _p%d", i);
3852 fprintf (f, ")\n");
3853 fprintf (f, "{\n");
3854 dop->gen_kids (f, 2, gimple, 0);
3855 if (gimple)
3856 fprintf (f, " return false;\n");
3857 else
3858 fprintf (f, " return NULL_TREE;\n");
3859 fprintf (f, "}\n");
3860 has_kids_p = true;
3863 /* If this main entry has no children, avoid generating code
3864 with compiler warnings, by generating a simple stub. */
3865 if (! has_kids_p)
3867 if (gimple)
3868 fprintf (f, "\nstatic bool\n"
3869 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3870 " tree (*)(tree), code_helper,\n"
3871 " const tree");
3872 else
3873 fprintf (f, "\ntree\n"
3874 "generic_simplify (location_t, enum tree_code,\n"
3875 " const tree");
3876 for (unsigned i = 0; i < n; ++i)
3877 fprintf (f, ", tree");
3878 fprintf (f, ")\n");
3879 fprintf (f, "{\n");
3880 if (gimple)
3881 fprintf (f, " return false;\n");
3882 else
3883 fprintf (f, " return NULL_TREE;\n");
3884 fprintf (f, "}\n");
3885 continue;
3888 /* Then generate the main entry with the outermost switch and
3889 tail-calls to the split-out functions. */
3890 if (gimple)
3891 fprintf (f, "\nstatic bool\n"
3892 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3893 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3894 " code_helper code, const tree type");
3895 else
3896 fprintf (f, "\ntree\n"
3897 "generic_simplify (location_t loc, enum tree_code code, "
3898 "const tree type ATTRIBUTE_UNUSED");
3899 for (unsigned i = 0; i < n; ++i)
3900 fprintf (f, ", tree _p%d", i);
3901 fprintf (f, ")\n");
3902 fprintf (f, "{\n");
3904 if (gimple)
3905 fprintf (f, " switch (code.get_rep())\n"
3906 " {\n");
3907 else
3908 fprintf (f, " switch (code)\n"
3909 " {\n");
3910 for (unsigned i = 0; i < root->kids.length (); i++)
3912 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3913 expr *e = static_cast<expr *>(dop->op);
3914 if (e->ops.length () != n
3915 /* Builtin simplifications are somewhat premature on
3916 GENERIC. The following drops patterns with outermost
3917 calls. It's easy to emit overloads for function code
3918 though if necessary. */
3919 || (!gimple
3920 && e->operation->kind != id_base::CODE))
3921 continue;
3923 if (*e->operation == CONVERT_EXPR
3924 || *e->operation == NOP_EXPR)
3925 fprintf (f, " CASE_CONVERT:\n");
3926 else
3927 fprintf (f, " case %s%s:\n",
3928 is_a <fn_id *> (e->operation) ? "-" : "",
3929 e->operation->id);
3930 if (gimple)
3931 fprintf (f, " return gimple_simplify_%s (res_op, "
3932 "seq, valueize, code, type", e->operation->id);
3933 else
3934 fprintf (f, " return generic_simplify_%s (loc, code, type",
3935 e->operation->id);
3936 for (unsigned j = 0; j < n; ++j)
3937 fprintf (f, ", _p%d", j);
3938 fprintf (f, ");\n");
3940 fprintf (f, " default:;\n"
3941 " }\n");
3943 if (gimple)
3944 fprintf (f, " return false;\n");
3945 else
3946 fprintf (f, " return NULL_TREE;\n");
3947 fprintf (f, "}\n");
3951 /* Output code to implement the predicate P from the decision tree DT. */
3953 void
3954 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3956 fprintf (f, "\nbool\n"
3957 "%s%s (tree t%s%s)\n"
3958 "{\n", gimple ? "gimple_" : "tree_", p->id,
3959 p->nargs > 0 ? ", tree *res_ops" : "",
3960 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3961 /* Conveniently make 'type' available. */
3962 fprintf_indent (f, 2, "const tree type = TREE_TYPE (t);\n");
3964 if (!gimple)
3965 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3966 dt.root->gen_kids (f, 2, gimple, 0);
3968 fprintf_indent (f, 2, "return false;\n"
3969 "}\n");
3972 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3974 static void
3975 write_header (FILE *f, const char *head)
3977 fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3978 fprintf (f, " a IL pattern matching and simplification description. */\n");
3980 /* Include the header instead of writing it awkwardly quoted here. */
3981 fprintf (f, "\n#include \"%s\"\n", head);
3986 /* AST parsing. */
3988 class parser
3990 public:
3991 parser (cpp_reader *, bool gimple);
3993 private:
3994 const cpp_token *next ();
3995 const cpp_token *peek (unsigned = 1);
3996 const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3997 const cpp_token *expect (enum cpp_ttype);
3998 const cpp_token *eat_token (enum cpp_ttype);
3999 const char *get_string ();
4000 const char *get_ident ();
4001 const cpp_token *eat_ident (const char *);
4002 const char *get_number ();
4004 unsigned get_internal_capture_id ();
4006 id_base *parse_operation (unsigned char &);
4007 operand *parse_capture (operand *, bool);
4008 operand *parse_expr ();
4009 c_expr *parse_c_expr (cpp_ttype);
4010 operand *parse_op ();
4012 void record_operlist (location_t, user_id *);
4014 void parse_pattern ();
4015 operand *parse_result (operand *, predicate_id *);
4016 void push_simplify (simplify::simplify_kind,
4017 vec<simplify *>&, operand *, operand *);
4018 void parse_simplify (simplify::simplify_kind,
4019 vec<simplify *>&, predicate_id *, operand *);
4020 void parse_for (location_t);
4021 void parse_if (location_t);
4022 void parse_predicates (location_t);
4023 void parse_operator_list (location_t);
4025 void finish_match_operand (operand *);
4027 cpp_reader *r;
4028 bool gimple;
4029 vec<c_expr *> active_ifs;
4030 vec<vec<user_id *> > active_fors;
4031 hash_set<user_id *> *oper_lists_set;
4032 vec<user_id *> oper_lists;
4034 cid_map_t *capture_ids;
4035 unsigned last_id;
4037 public:
4038 vec<simplify *> simplifiers;
4039 vec<predicate_id *> user_predicates;
4040 bool parsing_match_operand;
4043 /* Lexing helpers. */
4045 /* Read the next non-whitespace token from R. */
4047 const cpp_token *
4048 parser::next ()
4050 const cpp_token *token;
4053 token = cpp_get_token (r);
4055 while (token->type == CPP_PADDING);
4056 return token;
4059 /* Peek at the next non-whitespace token from R. */
4061 const cpp_token *
4062 parser::peek (unsigned num)
4064 const cpp_token *token;
4065 unsigned i = 0;
4068 token = cpp_peek_token (r, i++);
4070 while (token->type == CPP_PADDING
4071 || (--num > 0));
4072 /* If we peek at EOF this is a fatal error as it leaves the
4073 cpp_reader in unusable state. Assume we really wanted a
4074 token and thus this EOF is unexpected. */
4075 if (token->type == CPP_EOF)
4076 fatal_at (token, "unexpected end of file");
4077 return token;
4080 /* Peek at the next identifier token (or return NULL if the next
4081 token is not an identifier or equal to ID if supplied). */
4083 const cpp_token *
4084 parser::peek_ident (const char *id, unsigned num)
4086 const cpp_token *token = peek (num);
4087 if (token->type != CPP_NAME)
4088 return 0;
4090 if (id == 0)
4091 return token;
4093 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
4094 if (strcmp (id, t) == 0)
4095 return token;
4097 return 0;
4100 /* Read the next token from R and assert it is of type TK. */
4102 const cpp_token *
4103 parser::expect (enum cpp_ttype tk)
4105 const cpp_token *token = next ();
4106 if (token->type != tk)
4107 fatal_at (token, "expected %s, got %s",
4108 cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
4110 return token;
4113 /* Consume the next token from R and assert it is of type TK. */
4115 const cpp_token *
4116 parser::eat_token (enum cpp_ttype tk)
4118 return expect (tk);
4121 /* Read the next token from R and assert it is of type CPP_STRING and
4122 return its value. */
4124 const char *
4125 parser::get_string ()
4127 const cpp_token *token = expect (CPP_STRING);
4128 return (const char *)token->val.str.text;
4131 /* Read the next token from R and assert it is of type CPP_NAME and
4132 return its value. */
4134 const char *
4135 parser::get_ident ()
4137 const cpp_token *token = expect (CPP_NAME);
4138 return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
4141 /* Eat an identifier token with value S from R. */
4143 const cpp_token *
4144 parser::eat_ident (const char *s)
4146 const cpp_token *token = peek ();
4147 const char *t = get_ident ();
4148 if (strcmp (s, t) != 0)
4149 fatal_at (token, "expected '%s' got '%s'\n", s, t);
4150 return token;
4153 /* Read the next token from R and assert it is of type CPP_NUMBER and
4154 return its value. */
4156 const char *
4157 parser::get_number ()
4159 const cpp_token *token = expect (CPP_NUMBER);
4160 return (const char *)token->val.str.text;
4163 /* Return a capture ID that can be used internally. */
4165 unsigned
4166 parser::get_internal_capture_id ()
4168 unsigned newid = capture_ids->elements ();
4169 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4170 char id[13];
4171 bool existed;
4172 snprintf (id, sizeof (id), "__%u", newid);
4173 capture_ids->get_or_insert (xstrdup (id), &existed);
4174 if (existed)
4175 fatal ("reserved capture id '%s' already used", id);
4176 return newid;
4179 /* Record an operator-list use for transparent for handling. */
4181 void
4182 parser::record_operlist (location_t loc, user_id *p)
4184 if (!oper_lists_set->add (p))
4186 if (!oper_lists.is_empty ()
4187 && oper_lists[0]->substitutes.length () != p->substitutes.length ())
4188 fatal_at (loc, "User-defined operator list does not have the "
4189 "same number of entries as others used in the pattern");
4190 oper_lists.safe_push (p);
4194 /* Parse the operator ID, special-casing convert?, convert1? and
4195 convert2? */
4197 id_base *
4198 parser::parse_operation (unsigned char &opt_grp)
4200 const cpp_token *id_tok = peek ();
4201 char *alt_id = NULL;
4202 const char *id = get_ident ();
4203 const cpp_token *token = peek ();
4204 opt_grp = 0;
4205 if (token->type == CPP_QUERY
4206 && !(token->flags & PREV_WHITE))
4208 if (!parsing_match_operand)
4209 fatal_at (id_tok, "conditional convert can only be used in "
4210 "match expression");
4211 if (ISDIGIT (id[strlen (id) - 1]))
4213 opt_grp = id[strlen (id) - 1] - '0' + 1;
4214 alt_id = xstrdup (id);
4215 alt_id[strlen (id) - 1] = '\0';
4216 if (opt_grp == 1)
4217 fatal_at (id_tok, "use '%s?' here", alt_id);
4219 else
4220 opt_grp = 1;
4221 eat_token (CPP_QUERY);
4223 id_base *op = get_operator (alt_id ? alt_id : id);
4224 if (!op)
4225 fatal_at (id_tok, "unknown operator %s", alt_id ? alt_id : id);
4226 if (alt_id)
4227 free (alt_id);
4228 user_id *p = dyn_cast<user_id *> (op);
4229 if (p && p->is_oper_list)
4231 if (active_fors.length() == 0)
4232 record_operlist (id_tok->src_loc, p);
4233 else
4234 fatal_at (id_tok, "operator-list %s cannot be expanded inside 'for'", id);
4236 return op;
4239 /* Parse a capture.
4240 capture = '@'<number> */
4242 class operand *
4243 parser::parse_capture (operand *op, bool require_existing)
4245 location_t src_loc = eat_token (CPP_ATSIGN)->src_loc;
4246 const cpp_token *token = peek ();
4247 const char *id = NULL;
4248 bool value_match = false;
4249 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4250 if (token->type == CPP_ATSIGN
4251 && ! (token->flags & PREV_WHITE)
4252 && parsing_match_operand)
4254 eat_token (CPP_ATSIGN);
4255 token = peek ();
4256 value_match = true;
4258 if (token->type == CPP_NUMBER)
4259 id = get_number ();
4260 else if (token->type == CPP_NAME)
4261 id = get_ident ();
4262 else
4263 fatal_at (token, "expected number or identifier");
4264 unsigned next_id = capture_ids->elements ();
4265 bool existed;
4266 unsigned &num = capture_ids->get_or_insert (id, &existed);
4267 if (!existed)
4269 if (require_existing)
4270 fatal_at (src_loc, "unknown capture id");
4271 num = next_id;
4273 return new capture (src_loc, num, op, value_match);
4276 /* Parse an expression
4277 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4279 class operand *
4280 parser::parse_expr ()
4282 const cpp_token *token = peek ();
4283 unsigned char opt_grp;
4284 expr *e = new expr (parse_operation (opt_grp), token->src_loc);
4285 token = peek ();
4286 operand *op;
4287 bool is_commutative = false;
4288 bool force_capture = false;
4289 const char *expr_type = NULL;
4291 if (!parsing_match_operand
4292 && token->type == CPP_NOT
4293 && !(token->flags & PREV_WHITE))
4295 if (!gimple)
4296 fatal_at (token, "forcing simplification to a leaf is not supported "
4297 "for GENERIC");
4298 eat_token (CPP_NOT);
4299 e->force_leaf = true;
4302 if (token->type == CPP_COLON
4303 && !(token->flags & PREV_WHITE))
4305 eat_token (CPP_COLON);
4306 token = peek ();
4307 if (token->type == CPP_NAME
4308 && !(token->flags & PREV_WHITE))
4310 const char *s = get_ident ();
4311 if (!parsing_match_operand)
4312 expr_type = s;
4313 else
4315 const char *sp = s;
4316 while (*sp)
4318 if (*sp == 'c')
4320 if (operator_id *o
4321 = dyn_cast<operator_id *> (e->operation))
4323 if (!commutative_tree_code (o->code)
4324 && !comparison_code_p (o->code))
4325 fatal_at (token, "operation is not commutative");
4327 else if (user_id *p = dyn_cast<user_id *> (e->operation))
4328 for (unsigned i = 0;
4329 i < p->substitutes.length (); ++i)
4331 if (operator_id *q
4332 = dyn_cast<operator_id *> (p->substitutes[i]))
4334 if (!commutative_tree_code (q->code)
4335 && !comparison_code_p (q->code))
4336 fatal_at (token, "operation %s is not "
4337 "commutative", q->id);
4340 is_commutative = true;
4342 else if (*sp == 'C')
4343 is_commutative = true;
4344 else if (*sp == 's')
4346 e->force_single_use = true;
4347 force_capture = true;
4349 else
4350 fatal_at (token, "flag %c not recognized", *sp);
4351 sp++;
4354 token = peek ();
4356 else
4357 fatal_at (token, "expected flag or type specifying identifier");
4360 if (token->type == CPP_ATSIGN
4361 && !(token->flags & PREV_WHITE))
4362 op = parse_capture (e, false);
4363 else if (force_capture)
4365 unsigned num = get_internal_capture_id ();
4366 op = new capture (token->src_loc, num, e, false);
4368 else
4369 op = e;
4372 token = peek ();
4373 if (token->type == CPP_CLOSE_PAREN)
4375 if (e->operation->nargs != -1
4376 && e->operation->nargs != (int) e->ops.length ())
4377 fatal_at (token, "'%s' expects %u operands, not %u",
4378 e->operation->id, e->operation->nargs, e->ops.length ());
4379 if (is_commutative)
4381 if (e->ops.length () == 2
4382 || commutative_op (e->operation) >= 0)
4383 e->is_commutative = true;
4384 else
4385 fatal_at (token, "only binary operators or functions with "
4386 "two arguments can be marked commutative, "
4387 "unless the operation is known to be inherently "
4388 "commutative");
4390 e->expr_type = expr_type;
4391 if (opt_grp != 0)
4393 if (e->ops.length () != 1)
4394 fatal_at (token, "only unary operations can be conditional");
4395 e->opt_grp = opt_grp;
4397 return op;
4399 else if (!(token->flags & PREV_WHITE))
4400 fatal_at (token, "expected expression operand");
4402 e->append_op (parse_op ());
4404 while (1);
4407 /* Lex native C code delimited by START recording the preprocessing tokens
4408 for later processing.
4409 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4411 c_expr *
4412 parser::parse_c_expr (cpp_ttype start)
4414 const cpp_token *token;
4415 cpp_ttype end;
4416 unsigned opencnt;
4417 vec<cpp_token> code = vNULL;
4418 unsigned nr_stmts = 0;
4419 location_t loc = eat_token (start)->src_loc;
4420 if (start == CPP_OPEN_PAREN)
4421 end = CPP_CLOSE_PAREN;
4422 else if (start == CPP_OPEN_BRACE)
4423 end = CPP_CLOSE_BRACE;
4424 else
4425 gcc_unreachable ();
4426 opencnt = 1;
4429 token = next ();
4431 /* Count brace pairs to find the end of the expr to match. */
4432 if (token->type == start)
4433 opencnt++;
4434 else if (token->type == end
4435 && --opencnt == 0)
4436 break;
4437 else if (token->type == CPP_EOF)
4438 fatal_at (token, "unexpected end of file");
4440 /* This is a lame way of counting the number of statements. */
4441 if (token->type == CPP_SEMICOLON)
4442 nr_stmts++;
4444 /* If this is possibly a user-defined identifier mark it used. */
4445 if (token->type == CPP_NAME)
4447 id_base *idb = get_operator ((const char *)CPP_HASHNODE
4448 (token->val.node.node)->ident.str);
4449 user_id *p;
4450 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
4451 record_operlist (token->src_loc, p);
4454 /* Record the token. */
4455 code.safe_push (*token);
4457 while (1);
4458 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4461 /* Parse an operand which is either an expression, a predicate or
4462 a standalone capture.
4463 op = predicate | expr | c_expr | capture */
4465 class operand *
4466 parser::parse_op ()
4468 const cpp_token *token = peek ();
4469 class operand *op = NULL;
4470 if (token->type == CPP_OPEN_PAREN)
4472 eat_token (CPP_OPEN_PAREN);
4473 op = parse_expr ();
4474 eat_token (CPP_CLOSE_PAREN);
4476 else if (token->type == CPP_OPEN_BRACE)
4478 op = parse_c_expr (CPP_OPEN_BRACE);
4480 else
4482 /* Remaining ops are either empty or predicates */
4483 if (token->type == CPP_NAME)
4485 const char *id = get_ident ();
4486 id_base *opr = get_operator (id);
4487 if (!opr)
4488 fatal_at (token, "expected predicate name");
4489 if (operator_id *code1 = dyn_cast <operator_id *> (opr))
4491 if (code1->nargs != 0)
4492 fatal_at (token, "using an operator with operands as predicate");
4493 /* Parse the zero-operand operator "predicates" as
4494 expression. */
4495 op = new expr (opr, token->src_loc);
4497 else if (user_id *code2 = dyn_cast <user_id *> (opr))
4499 if (code2->nargs != 0)
4500 fatal_at (token, "using an operator with operands as predicate");
4501 /* Parse the zero-operand operator "predicates" as
4502 expression. */
4503 op = new expr (opr, token->src_loc);
4505 else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
4506 op = new predicate (p, token->src_loc);
4507 else
4508 fatal_at (token, "using an unsupported operator as predicate");
4509 if (!parsing_match_operand)
4510 fatal_at (token, "predicates are only allowed in match expression");
4511 token = peek ();
4512 if (token->flags & PREV_WHITE)
4513 return op;
4515 else if (token->type != CPP_COLON
4516 && token->type != CPP_ATSIGN)
4517 fatal_at (token, "expected expression or predicate");
4518 /* optionally followed by a capture and a predicate. */
4519 if (token->type == CPP_COLON)
4520 fatal_at (token, "not implemented: predicate on leaf operand");
4521 if (token->type == CPP_ATSIGN)
4522 op = parse_capture (op, !parsing_match_operand);
4525 return op;
4528 /* Create a new simplify from the current parsing state and MATCH,
4529 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4531 void
4532 parser::push_simplify (simplify::simplify_kind kind,
4533 vec<simplify *>& simplifiers,
4534 operand *match, operand *result)
4536 /* Build and push a temporary for operator list uses in expressions. */
4537 if (!oper_lists.is_empty ())
4538 active_fors.safe_push (oper_lists);
4540 simplifiers.safe_push
4541 (new simplify (kind, last_id++, match, result,
4542 active_fors.copy (), capture_ids));
4544 if (!oper_lists.is_empty ())
4545 active_fors.pop ();
4548 /* Parse
4549 <result-op> = <op> | <if> | <with>
4550 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4551 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4552 and return it. */
4554 operand *
4555 parser::parse_result (operand *result, predicate_id *matcher)
4557 const cpp_token *token = peek ();
4558 if (token->type != CPP_OPEN_PAREN)
4559 return parse_op ();
4561 eat_token (CPP_OPEN_PAREN);
4562 if (peek_ident ("if"))
4564 eat_ident ("if");
4565 if_expr *ife = new if_expr (token->src_loc);
4566 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4567 if (peek ()->type == CPP_OPEN_PAREN)
4569 ife->trueexpr = parse_result (result, matcher);
4570 if (peek ()->type == CPP_OPEN_PAREN)
4571 ife->falseexpr = parse_result (result, matcher);
4572 else if (peek ()->type != CPP_CLOSE_PAREN)
4573 ife->falseexpr = parse_op ();
4575 else if (peek ()->type != CPP_CLOSE_PAREN)
4577 ife->trueexpr = parse_op ();
4578 if (peek ()->type == CPP_OPEN_PAREN)
4579 ife->falseexpr = parse_result (result, matcher);
4580 else if (peek ()->type != CPP_CLOSE_PAREN)
4581 ife->falseexpr = parse_op ();
4583 /* If this if is immediately closed then it contains a
4584 manual matcher or is part of a predicate definition. */
4585 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4587 if (!matcher)
4588 fatal_at (peek (), "manual transform not implemented");
4589 ife->trueexpr = result;
4591 eat_token (CPP_CLOSE_PAREN);
4592 return ife;
4594 else if (peek_ident ("with"))
4596 eat_ident ("with");
4597 with_expr *withe = new with_expr (token->src_loc);
4598 /* Parse (with c-expr expr) as (if-with (true) expr). */
4599 withe->with = parse_c_expr (CPP_OPEN_BRACE);
4600 withe->with->nr_stmts = 0;
4601 withe->subexpr = parse_result (result, matcher);
4602 eat_token (CPP_CLOSE_PAREN);
4603 return withe;
4605 else if (peek_ident ("switch"))
4607 token = eat_ident ("switch");
4608 location_t ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4609 eat_ident ("if");
4610 if_expr *ife = new if_expr (ifloc);
4611 operand *res = ife;
4612 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4613 if (peek ()->type == CPP_OPEN_PAREN)
4614 ife->trueexpr = parse_result (result, matcher);
4615 else
4616 ife->trueexpr = parse_op ();
4617 eat_token (CPP_CLOSE_PAREN);
4618 if (peek ()->type != CPP_OPEN_PAREN
4619 || !peek_ident ("if", 2))
4620 fatal_at (token, "switch can be implemented with a single if");
4621 while (peek ()->type != CPP_CLOSE_PAREN)
4623 if (peek ()->type == CPP_OPEN_PAREN)
4625 if (peek_ident ("if", 2))
4627 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4628 eat_ident ("if");
4629 ife->falseexpr = new if_expr (ifloc);
4630 ife = as_a <if_expr *> (ife->falseexpr);
4631 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4632 if (peek ()->type == CPP_OPEN_PAREN)
4633 ife->trueexpr = parse_result (result, matcher);
4634 else
4635 ife->trueexpr = parse_op ();
4636 eat_token (CPP_CLOSE_PAREN);
4638 else
4640 /* switch default clause */
4641 ife->falseexpr = parse_result (result, matcher);
4642 eat_token (CPP_CLOSE_PAREN);
4643 return res;
4646 else
4648 /* switch default clause */
4649 ife->falseexpr = parse_op ();
4650 eat_token (CPP_CLOSE_PAREN);
4651 return res;
4654 eat_token (CPP_CLOSE_PAREN);
4655 return res;
4657 else
4659 operand *op = result;
4660 if (!matcher)
4661 op = parse_expr ();
4662 eat_token (CPP_CLOSE_PAREN);
4663 return op;
4667 /* Parse
4668 simplify = 'simplify' <expr> <result-op>
4670 match = 'match' <ident> <expr> [<result-op>]
4671 and fill SIMPLIFIERS with the results. */
4673 void
4674 parser::parse_simplify (simplify::simplify_kind kind,
4675 vec<simplify *>& simplifiers, predicate_id *matcher,
4676 operand *result)
4678 /* Reset the capture map. */
4679 if (!capture_ids)
4680 capture_ids = new cid_map_t;
4681 /* Reset oper_lists and set. */
4682 hash_set <user_id *> olist;
4683 oper_lists_set = &olist;
4684 oper_lists = vNULL;
4686 const cpp_token *loc = peek ();
4687 parsing_match_operand = true;
4688 class operand *match = parse_op ();
4689 finish_match_operand (match);
4690 parsing_match_operand = false;
4691 if (match->type == operand::OP_CAPTURE && !matcher)
4692 fatal_at (loc, "outermost expression cannot be captured");
4693 if (match->type == operand::OP_EXPR
4694 && is_a <predicate_id *> (as_a <expr *> (match)->operation))
4695 fatal_at (loc, "outermost expression cannot be a predicate");
4697 /* Splice active_ifs onto result and continue parsing the
4698 "then" expr. */
4699 if_expr *active_if = NULL;
4700 for (int i = active_ifs.length (); i > 0; --i)
4702 if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4703 ifc->cond = active_ifs[i-1];
4704 ifc->trueexpr = active_if;
4705 active_if = ifc;
4707 if_expr *outermost_if = active_if;
4708 while (active_if && active_if->trueexpr)
4709 active_if = as_a <if_expr *> (active_if->trueexpr);
4711 const cpp_token *token = peek ();
4713 /* If this if is immediately closed then it is part of a predicate
4714 definition. Push it. */
4715 if (token->type == CPP_CLOSE_PAREN)
4717 if (!matcher)
4718 fatal_at (token, "expected transform expression");
4719 if (active_if)
4721 active_if->trueexpr = result;
4722 result = outermost_if;
4724 push_simplify (kind, simplifiers, match, result);
4725 return;
4728 operand *tem = parse_result (result, matcher);
4729 if (active_if)
4731 active_if->trueexpr = tem;
4732 result = outermost_if;
4734 else
4735 result = tem;
4737 push_simplify (kind, simplifiers, match, result);
4740 /* Parsing of the outer control structures. */
4742 /* Parse a for expression
4743 for = '(' 'for' <subst>... <pattern> ')'
4744 subst = <ident> '(' <ident>... ')' */
4746 void
4747 parser::parse_for (location_t)
4749 auto_vec<const cpp_token *> user_id_tokens;
4750 vec<user_id *> user_ids = vNULL;
4751 const cpp_token *token;
4752 unsigned min_n_opers = 0, max_n_opers = 0;
4754 while (1)
4756 token = peek ();
4757 if (token->type != CPP_NAME)
4758 break;
4760 /* Insert the user defined operators into the operator hash. */
4761 const char *id = get_ident ();
4762 if (get_operator (id, true) != NULL)
4763 fatal_at (token, "operator already defined");
4764 user_id *op = new user_id (id);
4765 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4766 *slot = op;
4767 user_ids.safe_push (op);
4768 user_id_tokens.safe_push (token);
4770 eat_token (CPP_OPEN_PAREN);
4772 int arity = -1;
4773 while ((token = peek_ident ()) != 0)
4775 const char *oper = get_ident ();
4776 id_base *idb = get_operator (oper, true);
4777 if (idb == NULL)
4778 fatal_at (token, "no such operator '%s'", oper);
4780 if (arity == -1)
4781 arity = idb->nargs;
4782 else if (idb->nargs == -1)
4784 else if (idb->nargs != arity)
4785 fatal_at (token, "operator '%s' with arity %d does not match "
4786 "others with arity %d", oper, idb->nargs, arity);
4788 user_id *p = dyn_cast<user_id *> (idb);
4789 if (p)
4791 if (p->is_oper_list)
4792 op->substitutes.safe_splice (p->substitutes);
4793 else
4794 fatal_at (token, "iterator cannot be used as operator-list");
4796 else
4797 op->substitutes.safe_push (idb);
4799 op->nargs = arity;
4800 token = expect (CPP_CLOSE_PAREN);
4802 unsigned nsubstitutes = op->substitutes.length ();
4803 if (nsubstitutes == 0)
4804 fatal_at (token, "A user-defined operator must have at least "
4805 "one substitution");
4806 if (max_n_opers == 0)
4808 min_n_opers = nsubstitutes;
4809 max_n_opers = nsubstitutes;
4811 else
4813 if (nsubstitutes % min_n_opers != 0
4814 && min_n_opers % nsubstitutes != 0)
4815 fatal_at (token, "All user-defined identifiers must have a "
4816 "multiple number of operator substitutions of the "
4817 "smallest number of substitutions");
4818 if (nsubstitutes < min_n_opers)
4819 min_n_opers = nsubstitutes;
4820 else if (nsubstitutes > max_n_opers)
4821 max_n_opers = nsubstitutes;
4825 unsigned n_ids = user_ids.length ();
4826 if (n_ids == 0)
4827 fatal_at (token, "for requires at least one user-defined identifier");
4829 token = peek ();
4830 if (token->type == CPP_CLOSE_PAREN)
4831 fatal_at (token, "no pattern defined in for");
4833 active_fors.safe_push (user_ids);
4834 while (1)
4836 token = peek ();
4837 if (token->type == CPP_CLOSE_PAREN)
4838 break;
4839 parse_pattern ();
4841 active_fors.pop ();
4843 /* Remove user-defined operators from the hash again. */
4844 for (unsigned i = 0; i < user_ids.length (); ++i)
4846 if (!user_ids[i]->used)
4847 warning_at (user_id_tokens[i],
4848 "operator %s defined but not used", user_ids[i]->id);
4849 operators->remove_elt (user_ids[i]);
4853 /* Parse an identifier associated with a list of operators.
4854 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4856 void
4857 parser::parse_operator_list (location_t)
4859 const cpp_token *token = peek ();
4860 const char *id = get_ident ();
4862 if (get_operator (id, true) != 0)
4863 fatal_at (token, "operator %s already defined", id);
4865 user_id *op = new user_id (id, true);
4866 int arity = -1;
4868 while ((token = peek_ident ()) != 0)
4870 token = peek ();
4871 const char *oper = get_ident ();
4872 id_base *idb = get_operator (oper, true);
4874 if (idb == 0)
4875 fatal_at (token, "no such operator '%s'", oper);
4877 if (arity == -1)
4878 arity = idb->nargs;
4879 else if (idb->nargs == -1)
4881 else if (arity != idb->nargs)
4882 fatal_at (token, "operator '%s' with arity %d does not match "
4883 "others with arity %d", oper, idb->nargs, arity);
4885 /* We allow composition of multiple operator lists. */
4886 if (user_id *p = dyn_cast<user_id *> (idb))
4887 op->substitutes.safe_splice (p->substitutes);
4888 else
4889 op->substitutes.safe_push (idb);
4892 // Check that there is no junk after id-list
4893 token = peek();
4894 if (token->type != CPP_CLOSE_PAREN)
4895 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4897 if (op->substitutes.length () == 0)
4898 fatal_at (token, "operator-list cannot be empty");
4900 op->nargs = arity;
4901 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4902 *slot = op;
4905 /* Parse an outer if expression.
4906 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4908 void
4909 parser::parse_if (location_t)
4911 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4913 const cpp_token *token = peek ();
4914 if (token->type == CPP_CLOSE_PAREN)
4915 fatal_at (token, "no pattern defined in if");
4917 active_ifs.safe_push (ifexpr);
4918 while (1)
4920 token = peek ();
4921 if (token->type == CPP_CLOSE_PAREN)
4922 break;
4924 parse_pattern ();
4926 active_ifs.pop ();
4929 /* Parse a list of predefined predicate identifiers.
4930 preds = '(' 'define_predicates' <ident>... ')' */
4932 void
4933 parser::parse_predicates (location_t)
4937 const cpp_token *token = peek ();
4938 if (token->type != CPP_NAME)
4939 break;
4941 add_predicate (get_ident ());
4943 while (1);
4946 /* Parse outer control structures.
4947 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4949 void
4950 parser::parse_pattern ()
4952 /* All clauses start with '('. */
4953 eat_token (CPP_OPEN_PAREN);
4954 const cpp_token *token = peek ();
4955 const char *id = get_ident ();
4956 if (strcmp (id, "simplify") == 0)
4958 parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
4959 capture_ids = NULL;
4961 else if (strcmp (id, "match") == 0)
4963 bool with_args = false;
4964 location_t e_loc = peek ()->src_loc;
4965 if (peek ()->type == CPP_OPEN_PAREN)
4967 eat_token (CPP_OPEN_PAREN);
4968 with_args = true;
4970 const char *name = get_ident ();
4971 id_base *id1 = get_operator (name);
4972 predicate_id *p;
4973 if (!id1)
4975 p = add_predicate (name);
4976 user_predicates.safe_push (p);
4978 else if ((p = dyn_cast <predicate_id *> (id1)))
4980 else
4981 fatal_at (token, "cannot add a match to a non-predicate ID");
4982 /* Parse (match <id> <arg>... (match-expr)) here. */
4983 expr *e = NULL;
4984 if (with_args)
4986 capture_ids = new cid_map_t;
4987 e = new expr (p, e_loc);
4988 while (peek ()->type == CPP_ATSIGN)
4989 e->append_op (parse_capture (NULL, false));
4990 eat_token (CPP_CLOSE_PAREN);
4992 if (p->nargs != -1
4993 && ((e && e->ops.length () != (unsigned)p->nargs)
4994 || (!e && p->nargs != 0)))
4995 fatal_at (token, "non-matching number of match operands");
4996 p->nargs = e ? e->ops.length () : 0;
4997 parse_simplify (simplify::MATCH, p->matchers, p, e);
4998 capture_ids = NULL;
5000 else if (strcmp (id, "for") == 0)
5001 parse_for (token->src_loc);
5002 else if (strcmp (id, "if") == 0)
5003 parse_if (token->src_loc);
5004 else if (strcmp (id, "define_predicates") == 0)
5006 if (active_ifs.length () > 0
5007 || active_fors.length () > 0)
5008 fatal_at (token, "define_predicates inside if or for is not supported");
5009 parse_predicates (token->src_loc);
5011 else if (strcmp (id, "define_operator_list") == 0)
5013 if (active_ifs.length () > 0
5014 || active_fors.length () > 0)
5015 fatal_at (token, "operator-list inside if or for is not supported");
5016 parse_operator_list (token->src_loc);
5018 else
5019 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
5020 active_ifs.length () == 0 && active_fors.length () == 0
5021 ? "'define_predicates', " : "");
5023 eat_token (CPP_CLOSE_PAREN);
5026 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5027 recursively. */
5029 static void
5030 walk_captures (operand *op, vec<vec<capture *> > cpts)
5032 if (! op)
5033 return;
5035 if (capture *c = dyn_cast <capture *> (op))
5037 cpts[c->where].safe_push (c);
5038 walk_captures (c->what, cpts);
5040 else if (expr *e = dyn_cast <expr *> (op))
5041 for (unsigned i = 0; i < e->ops.length (); ++i)
5042 walk_captures (e->ops[i], cpts);
5045 /* Finish up OP which is a match operand. */
5047 void
5048 parser::finish_match_operand (operand *op)
5050 /* Look for matching captures, diagnose mis-uses of @@ and apply
5051 early lowering and distribution of value_match. */
5052 auto_vec<vec<capture *> > cpts;
5053 cpts.safe_grow_cleared (capture_ids->elements (), true);
5054 walk_captures (op, cpts);
5055 for (unsigned i = 0; i < cpts.length (); ++i)
5057 capture *value_match = NULL;
5058 for (unsigned j = 0; j < cpts[i].length (); ++j)
5060 if (cpts[i][j]->value_match)
5062 if (value_match)
5063 fatal_at (cpts[i][j]->location, "duplicate @@");
5064 value_match = cpts[i][j];
5067 if (cpts[i].length () == 1 && value_match)
5068 fatal_at (value_match->location, "@@ without a matching capture");
5069 if (value_match)
5071 /* Duplicate prevailing capture with the existing ID, create
5072 a fake ID and rewrite all captures to use it. This turns
5073 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5074 value_match->what = new capture (value_match->location,
5075 value_match->where,
5076 value_match->what, false);
5077 /* Create a fake ID and rewrite all captures to use it. */
5078 unsigned newid = get_internal_capture_id ();
5079 for (unsigned j = 0; j < cpts[i].length (); ++j)
5081 cpts[i][j]->where = newid;
5082 cpts[i][j]->value_match = true;
5085 cpts[i].release ();
5089 /* Main entry of the parser. Repeatedly parse outer control structures. */
5091 parser::parser (cpp_reader *r_, bool gimple_)
5093 r = r_;
5094 gimple = gimple_;
5095 active_ifs = vNULL;
5096 active_fors = vNULL;
5097 simplifiers = vNULL;
5098 oper_lists_set = NULL;
5099 oper_lists = vNULL;
5100 capture_ids = NULL;
5101 user_predicates = vNULL;
5102 parsing_match_operand = false;
5103 last_id = 0;
5105 const cpp_token *token = next ();
5106 while (token->type != CPP_EOF)
5108 _cpp_backup_tokens (r, 1);
5109 parse_pattern ();
5110 token = next ();
5115 /* Helper for the linemap code. */
5117 static size_t
5118 round_alloc_size (size_t s)
5120 return s;
5124 /* The genmatch generator program. It reads from a pattern description
5125 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5128 main (int argc, char **argv)
5130 cpp_reader *r;
5132 progname = "genmatch";
5134 if (argc < 2)
5135 return 1;
5137 bool gimple = true;
5138 char *input = argv[argc-1];
5139 for (int i = 1; i < argc - 1; ++i)
5141 if (strcmp (argv[i], "--gimple") == 0)
5142 gimple = true;
5143 else if (strcmp (argv[i], "--generic") == 0)
5144 gimple = false;
5145 else if (strcmp (argv[i], "-v") == 0)
5146 verbose = 1;
5147 else if (strcmp (argv[i], "-vv") == 0)
5148 verbose = 2;
5149 else
5151 fprintf (stderr, "Usage: genmatch "
5152 "[--gimple] [--generic] [-v[v]] input\n");
5153 return 1;
5157 line_table = XCNEW (class line_maps);
5158 linemap_init (line_table, 0);
5159 line_table->reallocator = xrealloc;
5160 line_table->round_alloc_size = round_alloc_size;
5162 r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
5163 cpp_callbacks *cb = cpp_get_callbacks (r);
5164 cb->diagnostic = diagnostic_cb;
5166 /* Add the build directory to the #include "" search path. */
5167 cpp_dir *dir = XCNEW (cpp_dir);
5168 dir->name = getpwd ();
5169 if (!dir->name)
5170 dir->name = ASTRDUP (".");
5171 cpp_set_include_chains (r, dir, NULL, false);
5173 if (!cpp_read_main_file (r, input))
5174 return 1;
5175 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
5176 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
5178 null_id = new id_base (id_base::NULL_ID, "null");
5180 /* Pre-seed operators. */
5181 operators = new hash_table<id_base> (1024);
5182 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5183 add_operator (SYM, # SYM, # TYPE, NARGS);
5184 #define END_OF_BASE_TREE_CODES
5185 #include "tree.def"
5186 #undef END_OF_BASE_TREE_CODES
5187 #undef DEFTREECODE
5189 /* Pre-seed builtin functions.
5190 ??? Cannot use N (name) as that is targetm.emultls.get_address
5191 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5192 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5193 add_function (ENUM, "CFN_" # ENUM);
5194 #include "builtins.def"
5196 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5197 add_function (IFN_##CODE, "CFN_" #CODE);
5198 #include "internal-fn.def"
5200 /* Parse ahead! */
5201 parser p (r, gimple);
5203 if (gimple)
5204 write_header (stdout, "gimple-match-head.c");
5205 else
5206 write_header (stdout, "generic-match-head.c");
5208 /* Go over all predicates defined with patterns and perform
5209 lowering and code generation. */
5210 for (unsigned i = 0; i < p.user_predicates.length (); ++i)
5212 predicate_id *pred = p.user_predicates[i];
5213 lower (pred->matchers, gimple);
5215 if (verbose == 2)
5216 for (unsigned j = 0; j < pred->matchers.length (); ++j)
5217 print_matches (pred->matchers[j]);
5219 decision_tree dt;
5220 for (unsigned j = 0; j < pred->matchers.length (); ++j)
5221 dt.insert (pred->matchers[j], j);
5223 if (verbose == 2)
5224 dt.print (stderr);
5226 write_predicate (stdout, pred, dt, gimple);
5229 /* Lower the main simplifiers and generate code for them. */
5230 lower (p.simplifiers, gimple);
5232 if (verbose == 2)
5233 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5234 print_matches (p.simplifiers[i]);
5236 decision_tree dt;
5237 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5238 dt.insert (p.simplifiers[i], i);
5240 if (verbose == 2)
5241 dt.print (stderr);
5243 dt.gen (stdout, gimple);
5245 /* Finalize. */
5246 cpp_finish (r, NULL);
5247 cpp_destroy (r);
5249 delete operators;
5251 return 0;