re PR c++/68578 (ICE on invalid template declaration and instantiation)
[official-gcc.git] / gcc / genmatch.c
blob2c3183b25af5bc0990957640d52f9f7e05e0b1e7
1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2017 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 struct line_maps *line_table;
55 /* The rich_location class within libcpp requires a way to expand
56 source_location 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 (source_location loc)
66 const struct line_map_ordinary *map;
67 loc = linemap_resolve_location (line_table, loc, LRK_SPELLING_LOCATION, &map);
68 return linemap_expand_location (line_table, map, loc);
71 static bool
72 #if GCC_VERSION >= 4001
73 __attribute__((format (printf, 5, 0)))
74 #endif
75 error_cb (cpp_reader *, int errtype, int, rich_location *richloc,
76 const char *msg, va_list *ap)
78 const line_map_ordinary *map;
79 source_location location = richloc->get_loc ();
80 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
81 expanded_location loc = linemap_expand_location (line_table, map, location);
82 fprintf (stderr, "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
83 (errtype == CPP_DL_WARNING) ? "warning" : "error");
84 vfprintf (stderr, msg, *ap);
85 fprintf (stderr, "\n");
86 FILE *f = fopen (loc.file, "r");
87 if (f)
89 char buf[128];
90 while (loc.line > 0)
92 if (!fgets (buf, 128, f))
93 goto notfound;
94 if (buf[strlen (buf) - 1] != '\n')
96 if (loc.line > 1)
97 loc.line++;
99 loc.line--;
101 fprintf (stderr, "%s", buf);
102 for (int i = 0; i < loc.column - 1; ++i)
103 fputc (' ', stderr);
104 fputc ('^', stderr);
105 fputc ('\n', stderr);
106 notfound:
107 fclose (f);
110 if (errtype == CPP_DL_FATAL)
111 exit (1);
112 return false;
115 static void
116 #if GCC_VERSION >= 4001
117 __attribute__((format (printf, 2, 3)))
118 #endif
119 fatal_at (const cpp_token *tk, const char *msg, ...)
121 rich_location richloc (line_table, tk->src_loc);
122 va_list ap;
123 va_start (ap, msg);
124 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
125 va_end (ap);
128 static void
129 #if GCC_VERSION >= 4001
130 __attribute__((format (printf, 2, 3)))
131 #endif
132 fatal_at (source_location loc, const char *msg, ...)
134 rich_location richloc (line_table, loc);
135 va_list ap;
136 va_start (ap, msg);
137 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
138 va_end (ap);
141 static void
142 #if GCC_VERSION >= 4001
143 __attribute__((format (printf, 2, 3)))
144 #endif
145 warning_at (const cpp_token *tk, const char *msg, ...)
147 rich_location richloc (line_table, tk->src_loc);
148 va_list ap;
149 va_start (ap, msg);
150 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
151 va_end (ap);
154 static void
155 #if GCC_VERSION >= 4001
156 __attribute__((format (printf, 2, 3)))
157 #endif
158 warning_at (source_location loc, const char *msg, ...)
160 rich_location richloc (line_table, loc);
161 va_list ap;
162 va_start (ap, msg);
163 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
164 va_end (ap);
167 /* Like fprintf, but print INDENT spaces at the beginning. */
169 static void
170 #if GCC_VERSION >= 4001
171 __attribute__((format (printf, 3, 4)))
172 #endif
173 fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
175 va_list ap;
176 for (; indent >= 8; indent -= 8)
177 fputc ('\t', f);
178 fprintf (f, "%*s", indent, "");
179 va_start (ap, format);
180 vfprintf (f, format, ap);
181 va_end (ap);
184 static void
185 output_line_directive (FILE *f, source_location location,
186 bool dumpfile = false)
188 const line_map_ordinary *map;
189 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
190 expanded_location loc = linemap_expand_location (line_table, map, location);
191 if (dumpfile)
193 /* When writing to a dumpfile only dump the filename. */
194 const char *file = strrchr (loc.file, DIR_SEPARATOR);
195 #if defined(DIR_SEPARATOR_2)
196 const char *pos2 = strrchr (loc.file, DIR_SEPARATOR_2);
197 if (pos2 && (!file || (pos2 > file)))
198 file = pos2;
199 #endif
200 if (!file)
201 file = loc.file;
202 else
203 ++file;
204 fprintf (f, "%s:%d", file, loc.line);
206 else
207 /* Other gen programs really output line directives here, at least for
208 development it's right now more convenient to have line information
209 from the generated file. Still keep the directives as comment for now
210 to easily back-point to the meta-description. */
211 fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
215 /* Pull in tree codes and builtin function codes from their
216 definition files. */
218 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
219 enum tree_code {
220 #include "tree.def"
221 CONVERT0,
222 CONVERT1,
223 CONVERT2,
224 VIEW_CONVERT0,
225 VIEW_CONVERT1,
226 VIEW_CONVERT2,
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 /* Return true if CODE represents a commutative tree code. Otherwise
244 return false. */
245 bool
246 commutative_tree_code (enum tree_code code)
248 switch (code)
250 case PLUS_EXPR:
251 case MULT_EXPR:
252 case MULT_HIGHPART_EXPR:
253 case MIN_EXPR:
254 case MAX_EXPR:
255 case BIT_IOR_EXPR:
256 case BIT_XOR_EXPR:
257 case BIT_AND_EXPR:
258 case NE_EXPR:
259 case EQ_EXPR:
260 case UNORDERED_EXPR:
261 case ORDERED_EXPR:
262 case UNEQ_EXPR:
263 case LTGT_EXPR:
264 case TRUTH_AND_EXPR:
265 case TRUTH_XOR_EXPR:
266 case TRUTH_OR_EXPR:
267 case WIDEN_MULT_EXPR:
268 case VEC_WIDEN_MULT_HI_EXPR:
269 case VEC_WIDEN_MULT_LO_EXPR:
270 case VEC_WIDEN_MULT_EVEN_EXPR:
271 case VEC_WIDEN_MULT_ODD_EXPR:
272 return true;
274 default:
275 break;
277 return false;
280 /* Return true if CODE represents a ternary tree code for which the
281 first two operands are commutative. Otherwise return false. */
282 bool
283 commutative_ternary_tree_code (enum tree_code code)
285 switch (code)
287 case WIDEN_MULT_PLUS_EXPR:
288 case WIDEN_MULT_MINUS_EXPR:
289 case DOT_PROD_EXPR:
290 case FMA_EXPR:
291 return true;
293 default:
294 break;
296 return false;
299 /* Return true if CODE is a comparison. */
301 bool
302 comparison_code_p (enum tree_code code)
304 switch (code)
306 case EQ_EXPR:
307 case NE_EXPR:
308 case ORDERED_EXPR:
309 case UNORDERED_EXPR:
310 case LTGT_EXPR:
311 case UNEQ_EXPR:
312 case GT_EXPR:
313 case GE_EXPR:
314 case LT_EXPR:
315 case LE_EXPR:
316 case UNGT_EXPR:
317 case UNGE_EXPR:
318 case UNLT_EXPR:
319 case UNLE_EXPR:
320 return true;
322 default:
323 break;
325 return false;
329 /* Base class for all identifiers the parser knows. */
331 struct id_base : nofree_ptr_hash<id_base>
333 enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
335 id_base (id_kind, const char *, int = -1);
337 hashval_t hashval;
338 int nargs;
339 const char *id;
341 /* hash_table support. */
342 static inline hashval_t hash (const id_base *);
343 static inline int equal (const id_base *, const id_base *);
346 inline hashval_t
347 id_base::hash (const id_base *op)
349 return op->hashval;
352 inline int
353 id_base::equal (const id_base *op1,
354 const id_base *op2)
356 return (op1->hashval == op2->hashval
357 && strcmp (op1->id, op2->id) == 0);
360 /* The special id "null", which matches nothing. */
361 static id_base *null_id;
363 /* Hashtable of known pattern operators. This is pre-seeded from
364 all known tree codes and all known builtin function ids. */
365 static hash_table<id_base> *operators;
367 id_base::id_base (id_kind kind_, const char *id_, int nargs_)
369 kind = kind_;
370 id = id_;
371 nargs = nargs_;
372 hashval = htab_hash_string (id);
375 /* Identifier that maps to a tree code. */
377 struct operator_id : public id_base
379 operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
380 const char *tcc_)
381 : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
382 enum tree_code code;
383 const char *tcc;
386 /* Identifier that maps to a builtin or internal function code. */
388 struct fn_id : public id_base
390 fn_id (enum built_in_function fn_, const char *id_)
391 : id_base (id_base::FN, id_), fn (fn_) {}
392 fn_id (enum internal_fn fn_, const char *id_)
393 : id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
394 unsigned int fn;
397 struct simplify;
399 /* Identifier that maps to a user-defined predicate. */
401 struct predicate_id : public id_base
403 predicate_id (const char *id_)
404 : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
405 vec<simplify *> matchers;
408 /* Identifier that maps to a operator defined by a 'for' directive. */
410 struct user_id : public id_base
412 user_id (const char *id_, bool is_oper_list_ = false)
413 : id_base (id_base::USER, id_), substitutes (vNULL),
414 used (false), is_oper_list (is_oper_list_) {}
415 vec<id_base *> substitutes;
416 bool used;
417 bool is_oper_list;
420 template<>
421 template<>
422 inline bool
423 is_a_helper <fn_id *>::test (id_base *id)
425 return id->kind == id_base::FN;
428 template<>
429 template<>
430 inline bool
431 is_a_helper <operator_id *>::test (id_base *id)
433 return id->kind == id_base::CODE;
436 template<>
437 template<>
438 inline bool
439 is_a_helper <predicate_id *>::test (id_base *id)
441 return id->kind == id_base::PREDICATE;
444 template<>
445 template<>
446 inline bool
447 is_a_helper <user_id *>::test (id_base *id)
449 return id->kind == id_base::USER;
452 /* Add a predicate identifier to the hash. */
454 static predicate_id *
455 add_predicate (const char *id)
457 predicate_id *p = new predicate_id (id);
458 id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
459 if (*slot)
460 fatal ("duplicate id definition");
461 *slot = p;
462 return p;
465 /* Add a tree code identifier to the hash. */
467 static void
468 add_operator (enum tree_code code, const char *id,
469 const char *tcc, unsigned nargs)
471 if (strcmp (tcc, "tcc_unary") != 0
472 && strcmp (tcc, "tcc_binary") != 0
473 && strcmp (tcc, "tcc_comparison") != 0
474 && strcmp (tcc, "tcc_expression") != 0
475 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
476 && strcmp (tcc, "tcc_reference") != 0
477 /* To have INTEGER_CST and friends as "predicate operators". */
478 && strcmp (tcc, "tcc_constant") != 0
479 /* And allow CONSTRUCTOR for vector initializers. */
480 && !(code == CONSTRUCTOR)
481 /* Allow SSA_NAME as predicate operator. */
482 && !(code == SSA_NAME))
483 return;
484 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
485 if (code == ADDR_EXPR)
486 nargs = 0;
487 operator_id *op = new operator_id (code, id, nargs, tcc);
488 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
489 if (*slot)
490 fatal ("duplicate id definition");
491 *slot = op;
494 /* Add a built-in or internal function identifier to the hash. ID is
495 the name of its CFN_* enumeration value. */
497 template <typename T>
498 static void
499 add_function (T code, const char *id)
501 fn_id *fn = new fn_id (code, id);
502 id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
503 if (*slot)
504 fatal ("duplicate id definition");
505 *slot = fn;
508 /* Helper for easy comparing ID with tree code CODE. */
510 static bool
511 operator==(id_base &id, enum tree_code code)
513 if (operator_id *oid = dyn_cast <operator_id *> (&id))
514 return oid->code == code;
515 return false;
518 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
520 id_base *
521 get_operator (const char *id, bool allow_null = false)
523 if (allow_null && strcmp (id, "null") == 0)
524 return null_id;
526 id_base tem (id_base::CODE, id);
528 id_base *op = operators->find_with_hash (&tem, tem.hashval);
529 if (op)
531 /* If this is a user-defined identifier track whether it was used. */
532 if (user_id *uid = dyn_cast<user_id *> (op))
533 uid->used = true;
534 return op;
537 char *id2;
538 bool all_upper = true;
539 bool all_lower = true;
540 for (unsigned int i = 0; id[i]; ++i)
541 if (ISUPPER (id[i]))
542 all_lower = false;
543 else if (ISLOWER (id[i]))
544 all_upper = false;
545 if (all_lower)
547 /* Try in caps with _EXPR appended. */
548 id2 = ACONCAT ((id, "_EXPR", NULL));
549 for (unsigned int i = 0; id2[i]; ++i)
550 id2[i] = TOUPPER (id2[i]);
552 else if (all_upper && strncmp (id, "IFN_", 4) == 0)
553 /* Try CFN_ instead of IFN_. */
554 id2 = ACONCAT (("CFN_", id + 4, NULL));
555 else if (all_upper && strncmp (id, "BUILT_IN_", 9) == 0)
556 /* Try prepending CFN_. */
557 id2 = ACONCAT (("CFN_", id, NULL));
558 else
559 return NULL;
561 new (&tem) id_base (id_base::CODE, id2);
562 return operators->find_with_hash (&tem, tem.hashval);
565 /* Return the comparison operators that results if the operands are
566 swapped. This is safe for floating-point. */
568 id_base *
569 swap_tree_comparison (operator_id *p)
571 switch (p->code)
573 case EQ_EXPR:
574 case NE_EXPR:
575 case ORDERED_EXPR:
576 case UNORDERED_EXPR:
577 case LTGT_EXPR:
578 case UNEQ_EXPR:
579 return p;
580 case GT_EXPR:
581 return get_operator ("LT_EXPR");
582 case GE_EXPR:
583 return get_operator ("LE_EXPR");
584 case LT_EXPR:
585 return get_operator ("GT_EXPR");
586 case LE_EXPR:
587 return get_operator ("GE_EXPR");
588 case UNGT_EXPR:
589 return get_operator ("UNLT_EXPR");
590 case UNGE_EXPR:
591 return get_operator ("UNLE_EXPR");
592 case UNLT_EXPR:
593 return get_operator ("UNGT_EXPR");
594 case UNLE_EXPR:
595 return get_operator ("UNGE_EXPR");
596 default:
597 gcc_unreachable ();
601 typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
604 /* The AST produced by parsing of the pattern definitions. */
606 struct dt_operand;
607 struct capture_info;
609 /* The base class for operands. */
611 struct operand {
612 enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
613 operand (enum op_type type_, source_location loc_)
614 : type (type_), location (loc_) {}
615 enum op_type type;
616 source_location location;
617 virtual void gen_transform (FILE *, int, const char *, bool, int,
618 const char *, capture_info *,
619 dt_operand ** = 0,
620 int = 0)
621 { gcc_unreachable (); }
624 /* A predicate operand. Predicates are leafs in the AST. */
626 struct predicate : public operand
628 predicate (predicate_id *p_, source_location loc)
629 : operand (OP_PREDICATE, loc), p (p_) {}
630 predicate_id *p;
633 /* An operand that constitutes an expression. Expressions include
634 function calls and user-defined predicate invocations. */
636 struct expr : public operand
638 expr (id_base *operation_, source_location loc, bool is_commutative_ = false)
639 : operand (OP_EXPR, loc), operation (operation_),
640 ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
641 is_generic (false), force_single_use (false) {}
642 expr (expr *e)
643 : operand (OP_EXPR, e->location), operation (e->operation),
644 ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
645 is_generic (e->is_generic), force_single_use (e->force_single_use) {}
646 void append_op (operand *op) { ops.safe_push (op); }
647 /* The operator and its operands. */
648 id_base *operation;
649 vec<operand *> ops;
650 /* An explicitely specified type - used exclusively for conversions. */
651 const char *expr_type;
652 /* Whether the operation is to be applied commutatively. This is
653 later lowered to two separate patterns. */
654 bool is_commutative;
655 /* Whether the expression is expected to be in GENERIC form. */
656 bool is_generic;
657 /* Whether pushing any stmt to the sequence should be conditional
658 on this expression having a single-use. */
659 bool force_single_use;
660 virtual void gen_transform (FILE *f, int, const char *, bool, int,
661 const char *, capture_info *,
662 dt_operand ** = 0, int = 0);
665 /* An operator that is represented by native C code. This is always
666 a leaf operand in the AST. This class is also used to represent
667 the code to be generated for 'if' and 'with' expressions. */
669 struct c_expr : public operand
671 /* A mapping of an identifier and its replacement. Used to apply
672 'for' lowering. */
673 struct id_tab {
674 const char *id;
675 const char *oper;
676 id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
679 c_expr (cpp_reader *r_, source_location loc,
680 vec<cpp_token> code_, unsigned nr_stmts_,
681 vec<id_tab> ids_, cid_map_t *capture_ids_)
682 : operand (OP_C_EXPR, loc), r (r_), code (code_),
683 capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
684 /* cpplib tokens and state to transform this back to source. */
685 cpp_reader *r;
686 vec<cpp_token> code;
687 cid_map_t *capture_ids;
688 /* The number of statements parsed (well, the number of ';'s). */
689 unsigned nr_stmts;
690 /* The identifier replacement vector. */
691 vec<id_tab> ids;
692 virtual void gen_transform (FILE *f, int, const char *, bool, int,
693 const char *, capture_info *,
694 dt_operand ** = 0, int = 0);
697 /* A wrapper around another operand that captures its value. */
699 struct capture : public operand
701 capture (source_location loc, unsigned where_, operand *what_, bool value_)
702 : operand (OP_CAPTURE, loc), where (where_), value_match (value_),
703 what (what_) {}
704 /* Identifier index for the value. */
705 unsigned where;
706 /* Whether in a match of two operands the compare should be for
707 equal values rather than equal atoms (boils down to a type
708 check or not). */
709 bool value_match;
710 /* The captured value. */
711 operand *what;
712 virtual void gen_transform (FILE *f, int, const char *, bool, int,
713 const char *, capture_info *,
714 dt_operand ** = 0, int = 0);
717 /* if expression. */
719 struct if_expr : public operand
721 if_expr (source_location loc)
722 : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
723 c_expr *cond;
724 operand *trueexpr;
725 operand *falseexpr;
728 /* with expression. */
730 struct with_expr : public operand
732 with_expr (source_location loc)
733 : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
734 c_expr *with;
735 operand *subexpr;
738 template<>
739 template<>
740 inline bool
741 is_a_helper <capture *>::test (operand *op)
743 return op->type == operand::OP_CAPTURE;
746 template<>
747 template<>
748 inline bool
749 is_a_helper <predicate *>::test (operand *op)
751 return op->type == operand::OP_PREDICATE;
754 template<>
755 template<>
756 inline bool
757 is_a_helper <c_expr *>::test (operand *op)
759 return op->type == operand::OP_C_EXPR;
762 template<>
763 template<>
764 inline bool
765 is_a_helper <expr *>::test (operand *op)
767 return op->type == operand::OP_EXPR;
770 template<>
771 template<>
772 inline bool
773 is_a_helper <if_expr *>::test (operand *op)
775 return op->type == operand::OP_IF;
778 template<>
779 template<>
780 inline bool
781 is_a_helper <with_expr *>::test (operand *op)
783 return op->type == operand::OP_WITH;
786 /* The main class of a pattern and its transform. This is used to
787 represent both (simplify ...) and (match ...) kinds. The AST
788 duplicates all outer 'if' and 'for' expressions here so each
789 simplify can exist in isolation. */
791 struct simplify
793 enum simplify_kind { SIMPLIFY, MATCH };
795 simplify (simplify_kind kind_, operand *match_, operand *result_,
796 vec<vec<user_id *> > for_vec_, cid_map_t *capture_ids_)
797 : kind (kind_), match (match_), result (result_),
798 for_vec (for_vec_), for_subst_vec (vNULL),
799 capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
801 simplify_kind kind;
802 /* The expression that is matched against the GENERIC or GIMPLE IL. */
803 operand *match;
804 /* For a (simplify ...) an expression with ifs and withs with the expression
805 produced when the pattern applies in the leafs.
806 For a (match ...) the leafs are either empty if it is a simple predicate
807 or the single expression specifying the matched operands. */
808 struct operand *result;
809 /* Collected 'for' expression operators that have to be replaced
810 in the lowering phase. */
811 vec<vec<user_id *> > for_vec;
812 vec<std::pair<user_id *, id_base *> > for_subst_vec;
813 /* A map of capture identifiers to indexes. */
814 cid_map_t *capture_ids;
815 int capture_max;
818 /* Debugging routines for dumping the AST. */
820 DEBUG_FUNCTION void
821 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
823 if (capture *c = dyn_cast<capture *> (o))
825 if (c->what && flattened == false)
826 print_operand (c->what, f, flattened);
827 fprintf (f, "@%u", c->where);
830 else if (predicate *p = dyn_cast<predicate *> (o))
831 fprintf (f, "%s", p->p->id);
833 else if (is_a<c_expr *> (o))
834 fprintf (f, "c_expr");
836 else if (expr *e = dyn_cast<expr *> (o))
838 if (e->ops.length () == 0)
839 fprintf (f, "%s", e->operation->id);
840 else
842 fprintf (f, "(%s", e->operation->id);
844 if (flattened == false)
846 for (unsigned i = 0; i < e->ops.length (); ++i)
848 putc (' ', f);
849 print_operand (e->ops[i], f, flattened);
852 putc (')', f);
856 else
857 gcc_unreachable ();
860 DEBUG_FUNCTION void
861 print_matches (struct simplify *s, FILE *f = stderr)
863 fprintf (f, "for expression: ");
864 print_operand (s->match, f);
865 putc ('\n', f);
869 /* AST lowering. */
871 /* Lowering of commutative operators. */
873 static void
874 cartesian_product (const vec< vec<operand *> >& ops_vector,
875 vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
877 if (n == ops_vector.length ())
879 vec<operand *> xv = v.copy ();
880 result.safe_push (xv);
881 return;
884 for (unsigned i = 0; i < ops_vector[n].length (); ++i)
886 v[n] = ops_vector[n][i];
887 cartesian_product (ops_vector, result, v, n + 1);
891 /* Lower OP to two operands in case it is marked as commutative. */
893 static vec<operand *>
894 commutate (operand *op, vec<vec<user_id *> > &for_vec)
896 vec<operand *> ret = vNULL;
898 if (capture *c = dyn_cast <capture *> (op))
900 if (!c->what)
902 ret.safe_push (op);
903 return ret;
905 vec<operand *> v = commutate (c->what, for_vec);
906 for (unsigned i = 0; i < v.length (); ++i)
908 capture *nc = new capture (c->location, c->where, v[i],
909 c->value_match);
910 ret.safe_push (nc);
912 return ret;
915 expr *e = dyn_cast <expr *> (op);
916 if (!e || e->ops.length () == 0)
918 ret.safe_push (op);
919 return ret;
922 vec< vec<operand *> > ops_vector = vNULL;
923 for (unsigned i = 0; i < e->ops.length (); ++i)
924 ops_vector.safe_push (commutate (e->ops[i], for_vec));
926 auto_vec< vec<operand *> > result;
927 auto_vec<operand *> v (e->ops.length ());
928 v.quick_grow_cleared (e->ops.length ());
929 cartesian_product (ops_vector, result, v, 0);
932 for (unsigned i = 0; i < result.length (); ++i)
934 expr *ne = new expr (e);
935 ne->is_commutative = false;
936 for (unsigned j = 0; j < result[i].length (); ++j)
937 ne->append_op (result[i][j]);
938 ret.safe_push (ne);
941 if (!e->is_commutative)
942 return ret;
944 for (unsigned i = 0; i < result.length (); ++i)
946 expr *ne = new expr (e);
947 if (operator_id *p = dyn_cast <operator_id *> (ne->operation))
949 if (comparison_code_p (p->code))
950 ne->operation = swap_tree_comparison (p);
952 else if (user_id *p = dyn_cast <user_id *> (ne->operation))
954 bool found_compare = false;
955 for (unsigned j = 0; j < p->substitutes.length (); ++j)
956 if (operator_id *q = dyn_cast <operator_id *> (p->substitutes[j]))
958 if (comparison_code_p (q->code)
959 && swap_tree_comparison (q) != q)
961 found_compare = true;
962 break;
965 if (found_compare)
967 user_id *newop = new user_id ("<internal>");
968 for (unsigned j = 0; j < p->substitutes.length (); ++j)
970 id_base *subst = p->substitutes[j];
971 if (operator_id *q = dyn_cast <operator_id *> (subst))
973 if (comparison_code_p (q->code))
974 subst = swap_tree_comparison (q);
976 newop->substitutes.safe_push (subst);
978 ne->operation = newop;
979 /* Search for 'p' inside the for vector and push 'newop'
980 to the same level. */
981 for (unsigned j = 0; newop && j < for_vec.length (); ++j)
982 for (unsigned k = 0; k < for_vec[j].length (); ++k)
983 if (for_vec[j][k] == p)
985 for_vec[j].safe_push (newop);
986 newop = NULL;
987 break;
991 ne->is_commutative = false;
992 // result[i].length () is 2 since e->operation is binary
993 for (unsigned j = result[i].length (); j; --j)
994 ne->append_op (result[i][j-1]);
995 ret.safe_push (ne);
998 return ret;
1001 /* Lower operations marked as commutative in the AST of S and push
1002 the resulting patterns to SIMPLIFIERS. */
1004 static void
1005 lower_commutative (simplify *s, vec<simplify *>& simplifiers)
1007 vec<operand *> matchers = commutate (s->match, s->for_vec);
1008 for (unsigned i = 0; i < matchers.length (); ++i)
1010 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1011 s->for_vec, s->capture_ids);
1012 simplifiers.safe_push (ns);
1016 /* Strip conditional conversios using operator OPER from O and its
1017 children if STRIP, else replace them with an unconditional convert. */
1019 operand *
1020 lower_opt_convert (operand *o, enum tree_code oper,
1021 enum tree_code to_oper, bool strip)
1023 if (capture *c = dyn_cast<capture *> (o))
1025 if (c->what)
1026 return new capture (c->location, c->where,
1027 lower_opt_convert (c->what, oper, to_oper, strip),
1028 c->value_match);
1029 else
1030 return c;
1033 expr *e = dyn_cast<expr *> (o);
1034 if (!e)
1035 return o;
1037 if (*e->operation == oper)
1039 if (strip)
1040 return lower_opt_convert (e->ops[0], oper, to_oper, strip);
1042 expr *ne = new expr (e);
1043 ne->operation = (to_oper == CONVERT_EXPR
1044 ? get_operator ("CONVERT_EXPR")
1045 : get_operator ("VIEW_CONVERT_EXPR"));
1046 ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
1047 return ne;
1050 expr *ne = new expr (e);
1051 for (unsigned i = 0; i < e->ops.length (); ++i)
1052 ne->append_op (lower_opt_convert (e->ops[i], oper, to_oper, strip));
1054 return ne;
1057 /* Determine whether O or its children uses the conditional conversion
1058 operator OPER. */
1060 static bool
1061 has_opt_convert (operand *o, enum tree_code oper)
1063 if (capture *c = dyn_cast<capture *> (o))
1065 if (c->what)
1066 return has_opt_convert (c->what, oper);
1067 else
1068 return false;
1071 expr *e = dyn_cast<expr *> (o);
1072 if (!e)
1073 return false;
1075 if (*e->operation == oper)
1076 return true;
1078 for (unsigned i = 0; i < e->ops.length (); ++i)
1079 if (has_opt_convert (e->ops[i], oper))
1080 return true;
1082 return false;
1085 /* Lower conditional convert operators in O, expanding it to a vector
1086 if required. */
1088 static vec<operand *>
1089 lower_opt_convert (operand *o)
1091 vec<operand *> v1 = vNULL, v2;
1093 v1.safe_push (o);
1095 enum tree_code opers[]
1096 = { CONVERT0, CONVERT_EXPR,
1097 CONVERT1, CONVERT_EXPR,
1098 CONVERT2, CONVERT_EXPR,
1099 VIEW_CONVERT0, VIEW_CONVERT_EXPR,
1100 VIEW_CONVERT1, VIEW_CONVERT_EXPR,
1101 VIEW_CONVERT2, VIEW_CONVERT_EXPR };
1103 /* Conditional converts are lowered to a pattern with the
1104 conversion and one without. The three different conditional
1105 convert codes are lowered separately. */
1107 for (unsigned i = 0; i < sizeof (opers) / sizeof (enum tree_code); i += 2)
1109 v2 = vNULL;
1110 for (unsigned j = 0; j < v1.length (); ++j)
1111 if (has_opt_convert (v1[j], opers[i]))
1113 v2.safe_push (lower_opt_convert (v1[j],
1114 opers[i], opers[i+1], false));
1115 v2.safe_push (lower_opt_convert (v1[j],
1116 opers[i], opers[i+1], true));
1119 if (v2 != vNULL)
1121 v1 = vNULL;
1122 for (unsigned j = 0; j < v2.length (); ++j)
1123 v1.safe_push (v2[j]);
1127 return v1;
1130 /* Lower conditional convert operators in the AST of S and push
1131 the resulting multiple patterns to SIMPLIFIERS. */
1133 static void
1134 lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
1136 vec<operand *> matchers = lower_opt_convert (s->match);
1137 for (unsigned i = 0; i < matchers.length (); ++i)
1139 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1140 s->for_vec, s->capture_ids);
1141 simplifiers.safe_push (ns);
1145 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1146 GENERIC and a GIMPLE variant. */
1148 static vec<operand *>
1149 lower_cond (operand *o)
1151 vec<operand *> ro = vNULL;
1153 if (capture *c = dyn_cast<capture *> (o))
1155 if (c->what)
1157 vec<operand *> lop = vNULL;
1158 lop = lower_cond (c->what);
1160 for (unsigned i = 0; i < lop.length (); ++i)
1161 ro.safe_push (new capture (c->location, c->where, lop[i],
1162 c->value_match));
1163 return ro;
1167 expr *e = dyn_cast<expr *> (o);
1168 if (!e || e->ops.length () == 0)
1170 ro.safe_push (o);
1171 return ro;
1174 vec< vec<operand *> > ops_vector = vNULL;
1175 for (unsigned i = 0; i < e->ops.length (); ++i)
1176 ops_vector.safe_push (lower_cond (e->ops[i]));
1178 auto_vec< vec<operand *> > result;
1179 auto_vec<operand *> v (e->ops.length ());
1180 v.quick_grow_cleared (e->ops.length ());
1181 cartesian_product (ops_vector, result, v, 0);
1183 for (unsigned i = 0; i < result.length (); ++i)
1185 expr *ne = new expr (e);
1186 for (unsigned j = 0; j < result[i].length (); ++j)
1187 ne->append_op (result[i][j]);
1188 ro.safe_push (ne);
1189 /* If this is a COND with a captured expression or an
1190 expression with two operands then also match a GENERIC
1191 form on the compare. */
1192 if ((*e->operation == COND_EXPR
1193 || *e->operation == VEC_COND_EXPR)
1194 && ((is_a <capture *> (e->ops[0])
1195 && as_a <capture *> (e->ops[0])->what
1196 && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1197 && as_a <expr *>
1198 (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1199 || (is_a <expr *> (e->ops[0])
1200 && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1202 expr *ne = new expr (e);
1203 for (unsigned j = 0; j < result[i].length (); ++j)
1204 ne->append_op (result[i][j]);
1205 if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1207 expr *ocmp = as_a <expr *> (c->what);
1208 expr *cmp = new expr (ocmp);
1209 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1210 cmp->append_op (ocmp->ops[j]);
1211 cmp->is_generic = true;
1212 ne->ops[0] = new capture (c->location, c->where, cmp,
1213 c->value_match);
1215 else
1217 expr *ocmp = as_a <expr *> (ne->ops[0]);
1218 expr *cmp = new expr (ocmp);
1219 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1220 cmp->append_op (ocmp->ops[j]);
1221 cmp->is_generic = true;
1222 ne->ops[0] = cmp;
1224 ro.safe_push (ne);
1228 return ro;
1231 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1232 GENERIC and a GIMPLE variant. */
1234 static void
1235 lower_cond (simplify *s, vec<simplify *>& simplifiers)
1237 vec<operand *> matchers = lower_cond (s->match);
1238 for (unsigned i = 0; i < matchers.length (); ++i)
1240 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1241 s->for_vec, s->capture_ids);
1242 simplifiers.safe_push (ns);
1246 /* Return true if O refers to ID. */
1248 bool
1249 contains_id (operand *o, user_id *id)
1251 if (capture *c = dyn_cast<capture *> (o))
1252 return c->what && contains_id (c->what, id);
1254 if (expr *e = dyn_cast<expr *> (o))
1256 if (e->operation == id)
1257 return true;
1258 for (unsigned i = 0; i < e->ops.length (); ++i)
1259 if (contains_id (e->ops[i], id))
1260 return true;
1261 return false;
1264 if (with_expr *w = dyn_cast <with_expr *> (o))
1265 return (contains_id (w->with, id)
1266 || contains_id (w->subexpr, id));
1268 if (if_expr *ife = dyn_cast <if_expr *> (o))
1269 return (contains_id (ife->cond, id)
1270 || contains_id (ife->trueexpr, id)
1271 || (ife->falseexpr && contains_id (ife->falseexpr, id)));
1273 if (c_expr *ce = dyn_cast<c_expr *> (o))
1274 return ce->capture_ids && ce->capture_ids->get (id->id);
1276 return false;
1280 /* In AST operand O replace operator ID with operator WITH. */
1282 operand *
1283 replace_id (operand *o, user_id *id, id_base *with)
1285 /* Deep-copy captures and expressions, replacing operations as
1286 needed. */
1287 if (capture *c = dyn_cast<capture *> (o))
1289 if (!c->what)
1290 return c;
1291 return new capture (c->location, c->where,
1292 replace_id (c->what, id, with), c->value_match);
1294 else if (expr *e = dyn_cast<expr *> (o))
1296 expr *ne = new expr (e);
1297 if (e->operation == id)
1298 ne->operation = with;
1299 for (unsigned i = 0; i < e->ops.length (); ++i)
1300 ne->append_op (replace_id (e->ops[i], id, with));
1301 return ne;
1303 else if (with_expr *w = dyn_cast <with_expr *> (o))
1305 with_expr *nw = new with_expr (w->location);
1306 nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1307 nw->subexpr = replace_id (w->subexpr, id, with);
1308 return nw;
1310 else if (if_expr *ife = dyn_cast <if_expr *> (o))
1312 if_expr *nife = new if_expr (ife->location);
1313 nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1314 nife->trueexpr = replace_id (ife->trueexpr, id, with);
1315 if (ife->falseexpr)
1316 nife->falseexpr = replace_id (ife->falseexpr, id, with);
1317 return nife;
1320 /* For c_expr we simply record a string replacement table which is
1321 applied at code-generation time. */
1322 if (c_expr *ce = dyn_cast<c_expr *> (o))
1324 vec<c_expr::id_tab> ids = ce->ids.copy ();
1325 ids.safe_push (c_expr::id_tab (id->id, with->id));
1326 return new c_expr (ce->r, ce->location,
1327 ce->code, ce->nr_stmts, ids, ce->capture_ids);
1330 return o;
1333 /* Return true if the binary operator OP is ok for delayed substitution
1334 during for lowering. */
1336 static bool
1337 binary_ok (operator_id *op)
1339 switch (op->code)
1341 case PLUS_EXPR:
1342 case MINUS_EXPR:
1343 case MULT_EXPR:
1344 case TRUNC_DIV_EXPR:
1345 case CEIL_DIV_EXPR:
1346 case FLOOR_DIV_EXPR:
1347 case ROUND_DIV_EXPR:
1348 case TRUNC_MOD_EXPR:
1349 case CEIL_MOD_EXPR:
1350 case FLOOR_MOD_EXPR:
1351 case ROUND_MOD_EXPR:
1352 case RDIV_EXPR:
1353 case EXACT_DIV_EXPR:
1354 case MIN_EXPR:
1355 case MAX_EXPR:
1356 case BIT_IOR_EXPR:
1357 case BIT_XOR_EXPR:
1358 case BIT_AND_EXPR:
1359 return true;
1360 default:
1361 return false;
1365 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1367 static void
1368 lower_for (simplify *sin, vec<simplify *>& simplifiers)
1370 vec<vec<user_id *> >& for_vec = sin->for_vec;
1371 unsigned worklist_start = 0;
1372 auto_vec<simplify *> worklist;
1373 worklist.safe_push (sin);
1375 /* Lower each recorded for separately, operating on the
1376 set of simplifiers created by the previous one.
1377 Lower inner-to-outer so inner for substitutes can refer
1378 to operators replaced by outer fors. */
1379 for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1381 vec<user_id *>& ids = for_vec[fi];
1382 unsigned n_ids = ids.length ();
1383 unsigned max_n_opers = 0;
1384 bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
1385 for (unsigned i = 0; i < n_ids; ++i)
1387 if (ids[i]->substitutes.length () > max_n_opers)
1388 max_n_opers = ids[i]->substitutes.length ();
1389 /* Require that all substitutes are of the same kind so that
1390 if we delay substitution to the result op code generation
1391 can look at the first substitute for deciding things like
1392 types of operands. */
1393 enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1394 for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1395 if (ids[i]->substitutes[j]->kind != kind)
1396 can_delay_subst = false;
1397 else if (operator_id *op
1398 = dyn_cast <operator_id *> (ids[i]->substitutes[j]))
1400 operator_id *op0
1401 = as_a <operator_id *> (ids[i]->substitutes[0]);
1402 if (strcmp (op->tcc, "tcc_comparison") == 0
1403 && strcmp (op0->tcc, "tcc_comparison") == 0)
1405 /* Unfortunately we can't just allow all tcc_binary. */
1406 else if (strcmp (op->tcc, "tcc_binary") == 0
1407 && strcmp (op0->tcc, "tcc_binary") == 0
1408 && binary_ok (op)
1409 && binary_ok (op0))
1411 else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
1412 || strcmp (op->id + 1, "ROTATE_EXPR") == 0)
1413 && (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
1414 || strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
1416 else
1417 can_delay_subst = false;
1419 else if (is_a <fn_id *> (ids[i]->substitutes[j]))
1421 else
1422 can_delay_subst = false;
1425 unsigned worklist_end = worklist.length ();
1426 for (unsigned si = worklist_start; si < worklist_end; ++si)
1428 simplify *s = worklist[si];
1429 for (unsigned j = 0; j < max_n_opers; ++j)
1431 operand *match_op = s->match;
1432 operand *result_op = s->result;
1433 auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
1434 bool skip = false;
1435 for (unsigned i = 0; i < n_ids; ++i)
1437 user_id *id = ids[i];
1438 id_base *oper = id->substitutes[j % id->substitutes.length ()];
1439 if (oper == null_id
1440 && (contains_id (match_op, id)
1441 || contains_id (result_op, id)))
1443 skip = true;
1444 break;
1446 subst.quick_push (std::make_pair (id, oper));
1447 match_op = replace_id (match_op, id, oper);
1448 if (result_op
1449 && !can_delay_subst)
1450 result_op = replace_id (result_op, id, oper);
1452 if (skip)
1453 continue;
1455 simplify *ns = new simplify (s->kind, match_op, result_op,
1456 vNULL, s->capture_ids);
1457 ns->for_subst_vec.safe_splice (s->for_subst_vec);
1458 if (result_op
1459 && can_delay_subst)
1460 ns->for_subst_vec.safe_splice (subst);
1462 worklist.safe_push (ns);
1465 worklist_start = worklist_end;
1468 /* Copy out the result from the last for lowering. */
1469 for (unsigned i = worklist_start; i < worklist.length (); ++i)
1470 simplifiers.safe_push (worklist[i]);
1473 /* Lower the AST for everything in SIMPLIFIERS. */
1475 static void
1476 lower (vec<simplify *>& simplifiers, bool gimple)
1478 auto_vec<simplify *> out_simplifiers;
1479 for (unsigned i = 0; i < simplifiers.length (); ++i)
1480 lower_opt_convert (simplifiers[i], out_simplifiers);
1482 simplifiers.truncate (0);
1483 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1484 lower_commutative (out_simplifiers[i], simplifiers);
1486 out_simplifiers.truncate (0);
1487 if (gimple)
1488 for (unsigned i = 0; i < simplifiers.length (); ++i)
1489 lower_cond (simplifiers[i], out_simplifiers);
1490 else
1491 out_simplifiers.safe_splice (simplifiers);
1494 simplifiers.truncate (0);
1495 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1496 lower_for (out_simplifiers[i], simplifiers);
1502 /* The decision tree built for generating GIMPLE and GENERIC pattern
1503 matching code. It represents the 'match' expression of all
1504 simplifies and has those as its leafs. */
1506 struct dt_simplify;
1508 /* A hash-map collecting semantically equivalent leafs in the decision
1509 tree for splitting out to separate functions. */
1510 struct sinfo
1512 dt_simplify *s;
1514 const char *fname;
1515 unsigned cnt;
1518 struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1519 sinfo *>
1521 static inline hashval_t hash (const key_type &);
1522 static inline bool equal_keys (const key_type &, const key_type &);
1523 template <typename T> static inline void remove (T &) {}
1526 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1527 sinfo_map_t;
1530 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1532 struct dt_node
1534 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1536 enum dt_type type;
1537 unsigned level;
1538 vec<dt_node *> kids;
1540 /* Statistics. */
1541 unsigned num_leafs;
1542 unsigned total_size;
1543 unsigned max_level;
1545 dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
1547 dt_node *append_node (dt_node *);
1548 dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
1549 dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
1550 dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
1551 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1553 virtual void gen (FILE *, int, bool) {}
1555 void gen_kids (FILE *, int, bool);
1556 void gen_kids_1 (FILE *, int, bool,
1557 vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1558 vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1560 void analyze (sinfo_map_t &);
1563 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1565 struct dt_operand : public dt_node
1567 operand *op;
1568 dt_operand *match_dop;
1569 dt_operand *parent;
1570 unsigned pos;
1571 bool value_match;
1573 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1574 dt_operand *parent_ = 0, unsigned pos_ = 0)
1575 : dt_node (type), op (op_), match_dop (match_dop_),
1576 parent (parent_), pos (pos_), value_match (false) {}
1578 void gen (FILE *, int, bool);
1579 unsigned gen_predicate (FILE *, int, const char *, bool);
1580 unsigned gen_match_op (FILE *, int, const char *, bool);
1582 unsigned gen_gimple_expr (FILE *, int);
1583 unsigned gen_generic_expr (FILE *, int, const char *);
1585 char *get_name (char *);
1586 void gen_opname (char *, unsigned);
1589 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1591 struct dt_simplify : public dt_node
1593 simplify *s;
1594 unsigned pattern_no;
1595 dt_operand **indexes;
1596 sinfo *info;
1598 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1599 : dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
1600 indexes (indexes_), info (NULL) {}
1602 void gen_1 (FILE *, int, bool, operand *);
1603 void gen (FILE *f, int, bool);
1606 template<>
1607 template<>
1608 inline bool
1609 is_a_helper <dt_operand *>::test (dt_node *n)
1611 return (n->type == dt_node::DT_OPERAND
1612 || n->type == dt_node::DT_MATCH);
1615 template<>
1616 template<>
1617 inline bool
1618 is_a_helper <dt_simplify *>::test (dt_node *n)
1620 return n->type == dt_node::DT_SIMPLIFY;
1625 /* A container for the actual decision tree. */
1627 struct decision_tree
1629 dt_node *root;
1631 void insert (struct simplify *, unsigned);
1632 void gen (FILE *f, bool gimple);
1633 void print (FILE *f = stderr);
1635 decision_tree () { root = new dt_node (dt_node::DT_NODE); }
1637 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1638 unsigned pos = 0, dt_node *parent = 0);
1639 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1640 static bool cmp_node (dt_node *, dt_node *);
1641 static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1644 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1646 bool
1647 cmp_operand (operand *o1, operand *o2)
1649 if (!o1 || !o2 || o1->type != o2->type)
1650 return false;
1652 if (o1->type == operand::OP_PREDICATE)
1654 predicate *p1 = as_a<predicate *>(o1);
1655 predicate *p2 = as_a<predicate *>(o2);
1656 return p1->p == p2->p;
1658 else if (o1->type == operand::OP_EXPR)
1660 expr *e1 = static_cast<expr *>(o1);
1661 expr *e2 = static_cast<expr *>(o2);
1662 return (e1->operation == e2->operation
1663 && e1->is_generic == e2->is_generic);
1665 else
1666 return false;
1669 /* Compare two decision tree nodes N1 and N2 and return true if they
1670 are equal. */
1672 bool
1673 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1675 if (!n1 || !n2 || n1->type != n2->type)
1676 return false;
1678 if (n1 == n2)
1679 return true;
1681 if (n1->type == dt_node::DT_TRUE)
1682 return false;
1684 if (n1->type == dt_node::DT_OPERAND)
1685 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1686 (as_a<dt_operand *> (n2))->op);
1687 else if (n1->type == dt_node::DT_MATCH)
1688 return (((as_a<dt_operand *> (n1))->match_dop
1689 == (as_a<dt_operand *> (n2))->match_dop)
1690 && ((as_a<dt_operand *> (n1))->value_match
1691 == (as_a<dt_operand *> (n2))->value_match));
1692 return false;
1695 /* Search OPS for a decision tree node like P and return it if found. */
1697 dt_node *
1698 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1700 /* We can merge adjacent DT_TRUE. */
1701 if (p->type == dt_node::DT_TRUE
1702 && !ops.is_empty ()
1703 && ops.last ()->type == dt_node::DT_TRUE)
1704 return ops.last ();
1705 for (int i = ops.length () - 1; i >= 0; --i)
1707 /* But we can't merge across DT_TRUE nodes as they serve as
1708 pattern order barriers to make sure that patterns apply
1709 in order of appearance in case multiple matches are possible. */
1710 if (ops[i]->type == dt_node::DT_TRUE)
1711 return NULL;
1712 if (decision_tree::cmp_node (ops[i], p))
1713 return ops[i];
1715 return NULL;
1718 /* Append N to the decision tree if it there is not already an existing
1719 identical child. */
1721 dt_node *
1722 dt_node::append_node (dt_node *n)
1724 dt_node *kid;
1726 kid = decision_tree::find_node (kids, n);
1727 if (kid)
1728 return kid;
1730 kids.safe_push (n);
1731 n->level = this->level + 1;
1733 return n;
1736 /* Append OP to the decision tree. */
1738 dt_node *
1739 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1741 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1742 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1743 return append_node (n);
1746 /* Append a DT_TRUE decision tree node. */
1748 dt_node *
1749 dt_node::append_true_op (dt_node *parent, unsigned pos)
1751 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1752 dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
1753 return append_node (n);
1756 /* Append a DT_MATCH decision tree node. */
1758 dt_node *
1759 dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
1761 dt_operand *parent_ = as_a<dt_operand *> (parent);
1762 dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
1763 return append_node (n);
1766 /* Append S to the decision tree. */
1768 dt_node *
1769 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1770 dt_operand **indexes)
1772 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1773 for (unsigned i = 0; i < kids.length (); ++i)
1774 if (dt_simplify *s2 = dyn_cast <dt_simplify *> (kids[i]))
1776 warning_at (s->match->location, "duplicate pattern");
1777 warning_at (s2->s->match->location, "previous pattern defined here");
1778 print_operand (s->match, stderr);
1779 fprintf (stderr, "\n");
1781 return append_node (n);
1784 /* Analyze the node and its children. */
1786 void
1787 dt_node::analyze (sinfo_map_t &map)
1789 num_leafs = 0;
1790 total_size = 1;
1791 max_level = level;
1793 if (type == DT_SIMPLIFY)
1795 /* Populate the map of equivalent simplifies. */
1796 dt_simplify *s = as_a <dt_simplify *> (this);
1797 bool existed;
1798 sinfo *&si = map.get_or_insert (s, &existed);
1799 if (!existed)
1801 si = new sinfo;
1802 si->s = s;
1803 si->cnt = 1;
1804 si->fname = NULL;
1806 else
1807 si->cnt++;
1808 s->info = si;
1809 num_leafs = 1;
1810 return;
1813 for (unsigned i = 0; i < kids.length (); ++i)
1815 kids[i]->analyze (map);
1816 num_leafs += kids[i]->num_leafs;
1817 total_size += kids[i]->total_size;
1818 max_level = MAX (max_level, kids[i]->max_level);
1822 /* Insert O into the decision tree and return the decision tree node found
1823 or created. */
1825 dt_node *
1826 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1827 unsigned pos, dt_node *parent)
1829 dt_node *q, *elm = 0;
1831 if (capture *c = dyn_cast<capture *> (o))
1833 unsigned capt_index = c->where;
1835 if (indexes[capt_index] == 0)
1837 if (c->what)
1838 q = insert_operand (p, c->what, indexes, pos, parent);
1839 else
1841 q = elm = p->append_true_op (parent, pos);
1842 goto at_assert_elm;
1844 // get to the last capture
1845 for (operand *what = c->what;
1846 what && is_a<capture *> (what);
1847 c = as_a<capture *> (what), what = c->what)
1850 if (!c->what)
1852 unsigned cc_index = c->where;
1853 dt_operand *match_op = indexes[cc_index];
1855 dt_operand temp (dt_node::DT_TRUE, 0, 0);
1856 elm = decision_tree::find_node (p->kids, &temp);
1858 if (elm == 0)
1860 dt_operand temp (dt_node::DT_MATCH, 0, match_op);
1861 temp.value_match = c->value_match;
1862 elm = decision_tree::find_node (p->kids, &temp);
1865 else
1867 dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
1868 elm = decision_tree::find_node (p->kids, &temp);
1871 at_assert_elm:
1872 gcc_assert (elm->type == dt_node::DT_TRUE
1873 || elm->type == dt_node::DT_OPERAND
1874 || elm->type == dt_node::DT_MATCH);
1875 indexes[capt_index] = static_cast<dt_operand *> (elm);
1876 return q;
1878 else
1880 p = p->append_match_op (indexes[capt_index], parent, pos);
1881 as_a <dt_operand *>(p)->value_match = c->value_match;
1882 if (c->what)
1883 return insert_operand (p, c->what, indexes, 0, p);
1884 else
1885 return p;
1888 p = p->append_op (o, parent, pos);
1889 q = p;
1891 if (expr *e = dyn_cast <expr *>(o))
1893 for (unsigned i = 0; i < e->ops.length (); ++i)
1894 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1897 return q;
1900 /* Insert S into the decision tree. */
1902 void
1903 decision_tree::insert (struct simplify *s, unsigned pattern_no)
1905 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1906 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1907 p->append_simplify (s, pattern_no, indexes);
1910 /* Debug functions to dump the decision tree. */
1912 DEBUG_FUNCTION void
1913 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1915 if (p->type == dt_node::DT_NODE)
1916 fprintf (f, "root");
1917 else
1919 fprintf (f, "|");
1920 for (unsigned i = 0; i < indent; i++)
1921 fprintf (f, "-");
1923 if (p->type == dt_node::DT_OPERAND)
1925 dt_operand *dop = static_cast<dt_operand *>(p);
1926 print_operand (dop->op, f, true);
1928 else if (p->type == dt_node::DT_TRUE)
1929 fprintf (f, "true");
1930 else if (p->type == dt_node::DT_MATCH)
1931 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1932 else if (p->type == dt_node::DT_SIMPLIFY)
1934 dt_simplify *s = static_cast<dt_simplify *> (p);
1935 fprintf (f, "simplify_%u { ", s->pattern_no);
1936 for (int i = 0; i <= s->s->capture_max; ++i)
1937 fprintf (f, "%p, ", (void *) s->indexes[i]);
1938 fprintf (f, " } ");
1942 fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
1944 for (unsigned i = 0; i < p->kids.length (); ++i)
1945 decision_tree::print_node (p->kids[i], f, indent + 2);
1948 DEBUG_FUNCTION void
1949 decision_tree::print (FILE *f)
1951 return decision_tree::print_node (root, f);
1955 /* For GENERIC we have to take care of wrapping multiple-used
1956 expressions with side-effects in save_expr and preserve side-effects
1957 of expressions with omit_one_operand. Analyze captures in
1958 match, result and with expressions and perform early-outs
1959 on the outermost match expression operands for cases we cannot
1960 handle. */
1962 struct capture_info
1964 capture_info (simplify *s, operand *, bool);
1965 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
1966 bool walk_result (operand *o, bool, operand *);
1967 void walk_c_expr (c_expr *);
1969 struct cinfo
1971 bool expr_p;
1972 bool cse_p;
1973 bool force_no_side_effects_p;
1974 bool force_single_use;
1975 bool cond_expr_cond_p;
1976 unsigned long toplevel_msk;
1977 unsigned match_use_count;
1978 unsigned result_use_count;
1979 unsigned same_as;
1980 capture *c;
1983 auto_vec<cinfo> info;
1984 unsigned long force_no_side_effects;
1985 bool gimple;
1988 /* Analyze captures in S. */
1990 capture_info::capture_info (simplify *s, operand *result, bool gimple_)
1992 gimple = gimple_;
1994 expr *e;
1995 if (s->kind == simplify::MATCH)
1997 force_no_side_effects = -1;
1998 return;
2001 force_no_side_effects = 0;
2002 info.safe_grow_cleared (s->capture_max + 1);
2003 for (int i = 0; i <= s->capture_max; ++i)
2004 info[i].same_as = i;
2006 e = as_a <expr *> (s->match);
2007 for (unsigned i = 0; i < e->ops.length (); ++i)
2008 walk_match (e->ops[i], i,
2009 (i != 0 && *e->operation == COND_EXPR)
2010 || *e->operation == TRUTH_ANDIF_EXPR
2011 || *e->operation == TRUTH_ORIF_EXPR,
2012 i == 0
2013 && (*e->operation == COND_EXPR
2014 || *e->operation == VEC_COND_EXPR));
2016 walk_result (s->result, false, result);
2019 /* Analyze captures in the match expression piece O. */
2021 void
2022 capture_info::walk_match (operand *o, unsigned toplevel_arg,
2023 bool conditional_p, bool cond_expr_cond_p)
2025 if (capture *c = dyn_cast <capture *> (o))
2027 unsigned where = c->where;
2028 info[where].match_use_count++;
2029 info[where].toplevel_msk |= 1 << toplevel_arg;
2030 info[where].force_no_side_effects_p |= conditional_p;
2031 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2032 if (!info[where].c)
2033 info[where].c = c;
2034 if (!c->what)
2035 return;
2036 /* Recurse to exprs and captures. */
2037 if (is_a <capture *> (c->what)
2038 || is_a <expr *> (c->what))
2039 walk_match (c->what, toplevel_arg, conditional_p, false);
2040 /* We need to look past multiple captures to find a captured
2041 expression as with conditional converts two captures
2042 can be collapsed onto the same expression. Also collect
2043 what captures capture the same thing. */
2044 while (c->what && is_a <capture *> (c->what))
2046 c = as_a <capture *> (c->what);
2047 if (info[c->where].same_as != c->where
2048 && info[c->where].same_as != info[where].same_as)
2049 fatal_at (c->location, "cannot handle this collapsed capture");
2050 info[c->where].same_as = info[where].same_as;
2052 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2053 expr *e;
2054 if (c->what
2055 && (e = dyn_cast <expr *> (c->what)))
2057 info[where].expr_p = true;
2058 info[where].force_single_use |= e->force_single_use;
2061 else if (expr *e = dyn_cast <expr *> (o))
2063 for (unsigned i = 0; i < e->ops.length (); ++i)
2065 bool cond_p = conditional_p;
2066 bool cond_expr_cond_p = false;
2067 if (i != 0 && *e->operation == COND_EXPR)
2068 cond_p = true;
2069 else if (*e->operation == TRUTH_ANDIF_EXPR
2070 || *e->operation == TRUTH_ORIF_EXPR)
2071 cond_p = true;
2072 if (i == 0
2073 && (*e->operation == COND_EXPR
2074 || *e->operation == VEC_COND_EXPR))
2075 cond_expr_cond_p = true;
2076 walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
2079 else if (is_a <predicate *> (o))
2081 /* Mark non-captured leafs toplevel arg for checking. */
2082 force_no_side_effects |= 1 << toplevel_arg;
2083 if (verbose >= 1
2084 && !gimple)
2085 warning_at (o->location,
2086 "forcing no side-effects on possibly lost leaf");
2088 else
2089 gcc_unreachable ();
2092 /* Analyze captures in the result expression piece O. Return true
2093 if RESULT was visited in one of the children. Only visit
2094 non-if/with children if they are rooted on RESULT. */
2096 bool
2097 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2099 if (capture *c = dyn_cast <capture *> (o))
2101 unsigned where = info[c->where].same_as;
2102 info[where].result_use_count++;
2103 /* If we substitute an expression capture we don't know
2104 which captures this will end up using (well, we don't
2105 compute that). Force the uses to be side-effect free
2106 which means forcing the toplevels that reach the
2107 expression side-effect free. */
2108 if (info[where].expr_p)
2109 force_no_side_effects |= info[where].toplevel_msk;
2110 /* Mark CSE capture uses as forced to have no side-effects. */
2111 if (c->what
2112 && is_a <expr *> (c->what))
2114 info[where].cse_p = true;
2115 walk_result (c->what, true, result);
2118 else if (expr *e = dyn_cast <expr *> (o))
2120 id_base *opr = e->operation;
2121 if (user_id *uid = dyn_cast <user_id *> (opr))
2122 opr = uid->substitutes[0];
2123 for (unsigned i = 0; i < e->ops.length (); ++i)
2125 bool cond_p = conditional_p;
2126 if (i != 0 && *e->operation == COND_EXPR)
2127 cond_p = true;
2128 else if (*e->operation == TRUTH_ANDIF_EXPR
2129 || *e->operation == TRUTH_ORIF_EXPR)
2130 cond_p = true;
2131 walk_result (e->ops[i], cond_p, result);
2134 else if (if_expr *e = dyn_cast <if_expr *> (o))
2136 /* 'if' conditions should be all fine. */
2137 if (e->trueexpr == result)
2139 walk_result (e->trueexpr, false, result);
2140 return true;
2142 if (e->falseexpr == result)
2144 walk_result (e->falseexpr, false, result);
2145 return true;
2147 bool res = false;
2148 if (is_a <if_expr *> (e->trueexpr)
2149 || is_a <with_expr *> (e->trueexpr))
2150 res |= walk_result (e->trueexpr, false, result);
2151 if (e->falseexpr
2152 && (is_a <if_expr *> (e->falseexpr)
2153 || is_a <with_expr *> (e->falseexpr)))
2154 res |= walk_result (e->falseexpr, false, result);
2155 return res;
2157 else if (with_expr *e = dyn_cast <with_expr *> (o))
2159 bool res = (e->subexpr == result);
2160 if (res
2161 || is_a <if_expr *> (e->subexpr)
2162 || is_a <with_expr *> (e->subexpr))
2163 res |= walk_result (e->subexpr, false, result);
2164 if (res)
2165 walk_c_expr (e->with);
2166 return res;
2168 else if (c_expr *e = dyn_cast <c_expr *> (o))
2169 walk_c_expr (e);
2170 else
2171 gcc_unreachable ();
2173 return false;
2176 /* Look for captures in the C expr E. */
2178 void
2179 capture_info::walk_c_expr (c_expr *e)
2181 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2182 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2183 really escape through. */
2184 unsigned p_depth = 0;
2185 for (unsigned i = 0; i < e->code.length (); ++i)
2187 const cpp_token *t = &e->code[i];
2188 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2189 id_base *id;
2190 if (t->type == CPP_NAME
2191 && (strcmp ((const char *)CPP_HASHNODE
2192 (t->val.node.node)->ident.str, "TREE_TYPE") == 0
2193 || strcmp ((const char *)CPP_HASHNODE
2194 (t->val.node.node)->ident.str, "TREE_CODE") == 0
2195 || strcmp ((const char *)CPP_HASHNODE
2196 (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
2197 || ((id = get_operator ((const char *)CPP_HASHNODE
2198 (t->val.node.node)->ident.str))
2199 && is_a <predicate_id *> (id)))
2200 && n->type == CPP_OPEN_PAREN)
2201 p_depth++;
2202 else if (t->type == CPP_CLOSE_PAREN
2203 && p_depth > 0)
2204 p_depth--;
2205 else if (p_depth == 0
2206 && t->type == CPP_ATSIGN
2207 && (n->type == CPP_NUMBER
2208 || n->type == CPP_NAME)
2209 && !(n->flags & PREV_WHITE))
2211 const char *id;
2212 if (n->type == CPP_NUMBER)
2213 id = (const char *)n->val.str.text;
2214 else
2215 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2216 unsigned *where = e->capture_ids->get(id);
2217 if (! where)
2218 fatal_at (n, "unknown capture id '%s'", id);
2219 info[info[*where].same_as].force_no_side_effects_p = true;
2220 if (verbose >= 1
2221 && !gimple)
2222 warning_at (t, "capture escapes");
2228 /* Code generation off the decision tree and the refered AST nodes. */
2230 bool
2231 is_conversion (id_base *op)
2233 return (*op == CONVERT_EXPR
2234 || *op == NOP_EXPR
2235 || *op == FLOAT_EXPR
2236 || *op == FIX_TRUNC_EXPR
2237 || *op == VIEW_CONVERT_EXPR);
2240 /* Get the type to be used for generating operand POS of OP from the
2241 various sources. */
2243 static const char *
2244 get_operand_type (id_base *op, unsigned pos,
2245 const char *in_type,
2246 const char *expr_type,
2247 const char *other_oprnd_type)
2249 /* Generally operands whose type does not match the type of the
2250 expression generated need to know their types but match and
2251 thus can fall back to 'other_oprnd_type'. */
2252 if (is_conversion (op))
2253 return other_oprnd_type;
2254 else if (*op == REALPART_EXPR
2255 || *op == IMAGPART_EXPR)
2256 return other_oprnd_type;
2257 else if (is_a <operator_id *> (op)
2258 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2259 return other_oprnd_type;
2260 else if (*op == COND_EXPR
2261 && pos == 0)
2262 return "boolean_type_node";
2263 else
2265 /* Otherwise all types should match - choose one in order of
2266 preference. */
2267 if (expr_type)
2268 return expr_type;
2269 else if (in_type)
2270 return in_type;
2271 else
2272 return other_oprnd_type;
2276 /* Generate transform code for an expression. */
2278 void
2279 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2280 int depth, const char *in_type, capture_info *cinfo,
2281 dt_operand **indexes, int)
2283 id_base *opr = operation;
2284 /* When we delay operator substituting during lowering of fors we
2285 make sure that for code-gen purposes the effects of each substitute
2286 are the same. Thus just look at that. */
2287 if (user_id *uid = dyn_cast <user_id *> (opr))
2288 opr = uid->substitutes[0];
2290 bool conversion_p = is_conversion (opr);
2291 const char *type = expr_type;
2292 char optype[64];
2293 if (type)
2294 /* If there was a type specification in the pattern use it. */
2296 else if (conversion_p)
2297 /* For conversions we need to build the expression using the
2298 outer type passed in. */
2299 type = in_type;
2300 else if (*opr == REALPART_EXPR
2301 || *opr == IMAGPART_EXPR)
2303 /* __real and __imag use the component type of its operand. */
2304 sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
2305 type = optype;
2307 else if (is_a <operator_id *> (opr)
2308 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2310 /* comparisons use boolean_type_node (or what gets in), but
2311 their operands need to figure out the types themselves. */
2312 if (in_type)
2313 type = in_type;
2314 else
2316 sprintf (optype, "boolean_type_node");
2317 type = optype;
2319 in_type = NULL;
2321 else if (*opr == COND_EXPR
2322 || *opr == VEC_COND_EXPR)
2324 /* Conditions are of the same type as their first alternative. */
2325 sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
2326 type = optype;
2328 else
2330 /* Other operations are of the same type as their first operand. */
2331 sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
2332 type = optype;
2334 if (!type)
2335 fatal_at (location, "cannot determine type of operand");
2337 fprintf_indent (f, indent, "{\n");
2338 indent += 2;
2339 fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
2340 char op0type[64];
2341 snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
2342 for (unsigned i = 0; i < ops.length (); ++i)
2344 char dest[32];
2345 snprintf (dest, 32, "ops%d[%u]", depth, i);
2346 const char *optype
2347 = get_operand_type (opr, i, in_type, expr_type,
2348 i == 0 ? NULL : op0type);
2349 ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
2350 cinfo, indexes,
2351 (*opr == COND_EXPR
2352 || *opr == VEC_COND_EXPR) && i == 0 ? 1 : 2);
2355 const char *opr_name;
2356 if (*operation == CONVERT_EXPR)
2357 opr_name = "NOP_EXPR";
2358 else
2359 opr_name = operation->id;
2361 if (gimple)
2363 if (*opr == CONVERT_EXPR)
2365 fprintf_indent (f, indent,
2366 "if (%s != TREE_TYPE (ops%d[0])\n",
2367 type, depth);
2368 fprintf_indent (f, indent,
2369 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2370 type, depth);
2371 fprintf_indent (f, indent + 2, "{\n");
2372 indent += 4;
2374 /* ??? Building a stmt can fail for various reasons here, seq being
2375 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2376 So if we fail here we should continue matching other patterns. */
2377 fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr_name);
2378 fprintf_indent (f, indent, "tree tem_ops[3] = { ");
2379 for (unsigned i = 0; i < ops.length (); ++i)
2380 fprintf (f, "ops%d[%u]%s", depth, i,
2381 i == ops.length () - 1 ? " };\n" : ", ");
2382 fprintf_indent (f, indent,
2383 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2384 ops.length (), type);
2385 fprintf_indent (f, indent,
2386 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2387 type);
2388 fprintf_indent (f, indent,
2389 "if (!res) return false;\n");
2390 if (*opr == CONVERT_EXPR)
2392 indent -= 4;
2393 fprintf_indent (f, indent, " }\n");
2394 fprintf_indent (f, indent, "else\n");
2395 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2398 else
2400 if (*opr == CONVERT_EXPR)
2402 fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2403 depth, type);
2404 indent += 2;
2406 if (opr->kind == id_base::CODE)
2407 fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
2408 ops.length(), opr_name, type);
2409 else
2411 fprintf_indent (f, indent, "{\n");
2412 fprintf_indent (f, indent, " res = maybe_build_call_expr_loc (loc, "
2413 "%s, %s, %d", opr_name, type, ops.length());
2415 for (unsigned i = 0; i < ops.length (); ++i)
2416 fprintf (f, ", ops%d[%u]", depth, i);
2417 fprintf (f, ");\n");
2418 if (opr->kind != id_base::CODE)
2420 fprintf_indent (f, indent, " if (!res)\n");
2421 fprintf_indent (f, indent, " return NULL_TREE;\n");
2422 fprintf_indent (f, indent, "}\n");
2424 if (*opr == CONVERT_EXPR)
2426 indent -= 2;
2427 fprintf_indent (f, indent, "else\n");
2428 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2431 fprintf_indent (f, indent, "%s = res;\n", dest);
2432 indent -= 2;
2433 fprintf_indent (f, indent, "}\n");
2436 /* Generate code for a c_expr which is either the expression inside
2437 an if statement or a sequence of statements which computes a
2438 result to be stored to DEST. */
2440 void
2441 c_expr::gen_transform (FILE *f, int indent, const char *dest,
2442 bool, int, const char *, capture_info *,
2443 dt_operand **, int)
2445 if (dest && nr_stmts == 1)
2446 fprintf_indent (f, indent, "%s = ", dest);
2448 unsigned stmt_nr = 1;
2449 for (unsigned i = 0; i < code.length (); ++i)
2451 const cpp_token *token = &code[i];
2453 /* Replace captures for code-gen. */
2454 if (token->type == CPP_ATSIGN)
2456 const cpp_token *n = &code[i+1];
2457 if ((n->type == CPP_NUMBER
2458 || n->type == CPP_NAME)
2459 && !(n->flags & PREV_WHITE))
2461 if (token->flags & PREV_WHITE)
2462 fputc (' ', f);
2463 const char *id;
2464 if (n->type == CPP_NUMBER)
2465 id = (const char *)n->val.str.text;
2466 else
2467 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2468 unsigned *cid = capture_ids->get (id);
2469 if (!cid)
2470 fatal_at (token, "unknown capture id");
2471 fprintf (f, "captures[%u]", *cid);
2472 ++i;
2473 continue;
2477 if (token->flags & PREV_WHITE)
2478 fputc (' ', f);
2480 if (token->type == CPP_NAME)
2482 const char *id = (const char *) NODE_NAME (token->val.node.node);
2483 unsigned j;
2484 for (j = 0; j < ids.length (); ++j)
2486 if (strcmp (id, ids[j].id) == 0)
2488 fprintf (f, "%s", ids[j].oper);
2489 break;
2492 if (j < ids.length ())
2493 continue;
2496 /* Output the token as string. */
2497 char *tk = (char *)cpp_token_as_text (r, token);
2498 fputs (tk, f);
2500 if (token->type == CPP_SEMICOLON)
2502 stmt_nr++;
2503 fputc ('\n', f);
2504 if (dest && stmt_nr == nr_stmts)
2505 fprintf_indent (f, indent, "%s = ", dest);
2510 /* Generate transform code for a capture. */
2512 void
2513 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2514 int depth, const char *in_type, capture_info *cinfo,
2515 dt_operand **indexes, int cond_handling)
2517 if (what && is_a<expr *> (what))
2519 if (indexes[where] == 0)
2521 char buf[20];
2522 sprintf (buf, "captures[%u]", where);
2523 what->gen_transform (f, indent, buf, gimple, depth, in_type,
2524 cinfo, NULL);
2528 /* If in GENERIC some capture is used multiple times, unshare it except
2529 when emitting the last use. */
2530 if (!gimple
2531 && cinfo->info.exists ()
2532 && cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
2534 fprintf_indent (f, indent, "%s = unshare_expr (captures[%u]);\n",
2535 dest, where);
2536 cinfo->info[cinfo->info[where].same_as].result_use_count--;
2538 else
2539 fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2541 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2542 with substituting a capture of that. */
2543 if (gimple
2544 && cond_handling != 0
2545 && cinfo->info[where].cond_expr_cond_p)
2547 /* If substituting into a cond_expr condition, unshare. */
2548 if (cond_handling == 1)
2549 fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
2550 /* If substituting elsewhere we might need to decompose it. */
2551 else if (cond_handling == 2)
2553 /* ??? Returning false here will also not allow any other patterns
2554 to match unless this generator was split out. */
2555 fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2556 fprintf_indent (f, indent, " {\n");
2557 fprintf_indent (f, indent, " if (!seq) return false;\n");
2558 fprintf_indent (f, indent, " %s = gimple_build (seq,"
2559 " TREE_CODE (%s),"
2560 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2561 " TREE_OPERAND (%s, 1));\n",
2562 dest, dest, dest, dest, dest);
2563 fprintf_indent (f, indent, " }\n");
2568 /* Return the name of the operand representing the decision tree node.
2569 Use NAME as space to generate it. */
2571 char *
2572 dt_operand::get_name (char *name)
2574 if (!parent)
2575 sprintf (name, "t");
2576 else if (parent->level == 1)
2577 sprintf (name, "op%u", pos);
2578 else if (parent->type == dt_node::DT_MATCH)
2579 return parent->get_name (name);
2580 else
2581 sprintf (name, "o%u%u", parent->level, pos);
2582 return name;
2585 /* Fill NAME with the operand name at position POS. */
2587 void
2588 dt_operand::gen_opname (char *name, unsigned pos)
2590 if (!parent)
2591 sprintf (name, "op%u", pos);
2592 else
2593 sprintf (name, "o%u%u", level, pos);
2596 /* Generate matching code for the decision tree operand which is
2597 a predicate. */
2599 unsigned
2600 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2602 predicate *p = as_a <predicate *> (op);
2604 if (p->p->matchers.exists ())
2606 /* If this is a predicate generated from a pattern mangle its
2607 name and pass on the valueize hook. */
2608 if (gimple)
2609 fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2610 p->p->id, opname);
2611 else
2612 fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2614 else
2615 fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2616 fprintf_indent (f, indent + 2, "{\n");
2617 return 1;
2620 /* Generate matching code for the decision tree operand which is
2621 a capture-match. */
2623 unsigned
2624 dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
2626 char match_opname[20];
2627 match_dop->get_name (match_opname);
2628 if (value_match)
2629 fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2630 opname, match_opname, opname, match_opname);
2631 else
2632 fprintf_indent (f, indent, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
2633 "&& types_match (%s, %s)))\n",
2634 opname, match_opname, opname, match_opname,
2635 opname, match_opname);
2636 fprintf_indent (f, indent + 2, "{\n");
2637 return 1;
2640 /* Generate GIMPLE matching code for the decision tree operand. */
2642 unsigned
2643 dt_operand::gen_gimple_expr (FILE *f, int indent)
2645 expr *e = static_cast<expr *> (op);
2646 id_base *id = e->operation;
2647 unsigned n_ops = e->ops.length ();
2649 for (unsigned i = 0; i < n_ops; ++i)
2651 char child_opname[20];
2652 gen_opname (child_opname, i);
2654 if (id->kind == id_base::CODE)
2656 if (e->is_generic
2657 || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2658 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2660 /* ??? If this is a memory operation we can't (and should not)
2661 match this. The only sensible operand types are
2662 SSA names and invariants. */
2663 if (e->is_generic)
2665 char opname[20];
2666 get_name (opname);
2667 fprintf_indent (f, indent,
2668 "tree %s = TREE_OPERAND (%s, %i);\n",
2669 child_opname, opname, i);
2671 else
2672 fprintf_indent (f, indent,
2673 "tree %s = TREE_OPERAND "
2674 "(gimple_assign_rhs1 (def), %i);\n",
2675 child_opname, i);
2676 fprintf_indent (f, indent,
2677 "if ((TREE_CODE (%s) == SSA_NAME\n",
2678 child_opname);
2679 fprintf_indent (f, indent,
2680 " || is_gimple_min_invariant (%s))\n",
2681 child_opname);
2682 fprintf_indent (f, indent,
2683 " && (%s = do_valueize (valueize, %s)))\n",
2684 child_opname, child_opname);
2685 fprintf_indent (f, indent,
2686 " {\n");
2687 indent += 4;
2688 continue;
2690 else
2691 fprintf_indent (f, indent,
2692 "tree %s = gimple_assign_rhs%u (def);\n",
2693 child_opname, i + 1);
2695 else
2696 fprintf_indent (f, indent,
2697 "tree %s = gimple_call_arg (def, %u);\n",
2698 child_opname, i);
2699 fprintf_indent (f, indent,
2700 "if ((%s = do_valueize (valueize, %s)))\n",
2701 child_opname, child_opname);
2702 fprintf_indent (f, indent, " {\n");
2703 indent += 4;
2705 /* While the toplevel operands are canonicalized by the caller
2706 after valueizing operands of sub-expressions we have to
2707 re-canonicalize operand order. */
2708 if (operator_id *code = dyn_cast <operator_id *> (id))
2710 /* ??? We can't canonicalize tcc_comparison operands here
2711 because that requires changing the comparison code which
2712 we already matched... */
2713 if (commutative_tree_code (code->code)
2714 || commutative_ternary_tree_code (code->code))
2716 char child_opname0[20], child_opname1[20];
2717 gen_opname (child_opname0, 0);
2718 gen_opname (child_opname1, 1);
2719 fprintf_indent (f, indent,
2720 "if (tree_swap_operands_p (%s, %s))\n",
2721 child_opname0, child_opname1);
2722 fprintf_indent (f, indent,
2723 " std::swap (%s, %s);\n",
2724 child_opname0, child_opname1);
2728 return n_ops;
2731 /* Generate GENERIC matching code for the decision tree operand. */
2733 unsigned
2734 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2736 expr *e = static_cast<expr *> (op);
2737 unsigned n_ops = e->ops.length ();
2739 for (unsigned i = 0; i < n_ops; ++i)
2741 char child_opname[20];
2742 gen_opname (child_opname, i);
2744 if (e->operation->kind == id_base::CODE)
2745 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2746 child_opname, opname, i);
2747 else
2748 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2749 child_opname, opname, i);
2752 return 0;
2755 /* Generate matching code for the children of the decision tree node. */
2757 void
2758 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2760 auto_vec<dt_operand *> gimple_exprs;
2761 auto_vec<dt_operand *> generic_exprs;
2762 auto_vec<dt_operand *> fns;
2763 auto_vec<dt_operand *> generic_fns;
2764 auto_vec<dt_operand *> preds;
2765 auto_vec<dt_node *> others;
2767 for (unsigned i = 0; i < kids.length (); ++i)
2769 if (kids[i]->type == dt_node::DT_OPERAND)
2771 dt_operand *op = as_a<dt_operand *> (kids[i]);
2772 if (expr *e = dyn_cast <expr *> (op->op))
2774 if (e->ops.length () == 0
2775 && (!gimple || !(*e->operation == CONSTRUCTOR)))
2776 generic_exprs.safe_push (op);
2777 else if (e->operation->kind == id_base::FN)
2779 if (gimple)
2780 fns.safe_push (op);
2781 else
2782 generic_fns.safe_push (op);
2784 else if (e->operation->kind == id_base::PREDICATE)
2785 preds.safe_push (op);
2786 else
2788 if (gimple && !e->is_generic)
2789 gimple_exprs.safe_push (op);
2790 else
2791 generic_exprs.safe_push (op);
2794 else if (op->op->type == operand::OP_PREDICATE)
2795 others.safe_push (kids[i]);
2796 else
2797 gcc_unreachable ();
2799 else if (kids[i]->type == dt_node::DT_SIMPLIFY)
2800 others.safe_push (kids[i]);
2801 else if (kids[i]->type == dt_node::DT_MATCH
2802 || kids[i]->type == dt_node::DT_TRUE)
2804 /* A DT_TRUE operand serves as a barrier - generate code now
2805 for what we have collected sofar.
2806 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2807 dependent matches to get out-of-order. Generate code now
2808 for what we have collected sofar. */
2809 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2810 fns, generic_fns, preds, others);
2811 /* And output the true operand itself. */
2812 kids[i]->gen (f, indent, gimple);
2813 gimple_exprs.truncate (0);
2814 generic_exprs.truncate (0);
2815 fns.truncate (0);
2816 generic_fns.truncate (0);
2817 preds.truncate (0);
2818 others.truncate (0);
2820 else
2821 gcc_unreachable ();
2824 /* Generate code for the remains. */
2825 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2826 fns, generic_fns, preds, others);
2829 /* Generate matching code for the children of the decision tree node. */
2831 void
2832 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2833 vec<dt_operand *> gimple_exprs,
2834 vec<dt_operand *> generic_exprs,
2835 vec<dt_operand *> fns,
2836 vec<dt_operand *> generic_fns,
2837 vec<dt_operand *> preds,
2838 vec<dt_node *> others)
2840 char buf[128];
2841 char *kid_opname = buf;
2843 unsigned exprs_len = gimple_exprs.length ();
2844 unsigned gexprs_len = generic_exprs.length ();
2845 unsigned fns_len = fns.length ();
2846 unsigned gfns_len = generic_fns.length ();
2848 if (exprs_len || fns_len || gexprs_len || gfns_len)
2850 if (exprs_len)
2851 gimple_exprs[0]->get_name (kid_opname);
2852 else if (fns_len)
2853 fns[0]->get_name (kid_opname);
2854 else if (gfns_len)
2855 generic_fns[0]->get_name (kid_opname);
2856 else
2857 generic_exprs[0]->get_name (kid_opname);
2859 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2860 fprintf_indent (f, indent, " {\n");
2861 indent += 2;
2864 if (exprs_len || fns_len)
2866 fprintf_indent (f, indent,
2867 "case SSA_NAME:\n");
2868 fprintf_indent (f, indent,
2869 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2870 kid_opname);
2871 fprintf_indent (f, indent,
2872 " {\n");
2873 fprintf_indent (f, indent,
2874 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2875 kid_opname);
2877 indent += 6;
2878 if (exprs_len)
2880 fprintf_indent (f, indent,
2881 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2882 fprintf_indent (f, indent,
2883 " switch (gimple_assign_rhs_code (def))\n");
2884 indent += 4;
2885 fprintf_indent (f, indent, "{\n");
2886 for (unsigned i = 0; i < exprs_len; ++i)
2888 expr *e = as_a <expr *> (gimple_exprs[i]->op);
2889 id_base *op = e->operation;
2890 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2891 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2892 else
2893 fprintf_indent (f, indent, "case %s:\n", op->id);
2894 fprintf_indent (f, indent, " {\n");
2895 gimple_exprs[i]->gen (f, indent + 4, true);
2896 fprintf_indent (f, indent, " break;\n");
2897 fprintf_indent (f, indent, " }\n");
2899 fprintf_indent (f, indent, "default:;\n");
2900 fprintf_indent (f, indent, "}\n");
2901 indent -= 4;
2904 if (fns_len)
2906 fprintf_indent (f, indent,
2907 "%sif (gcall *def = dyn_cast <gcall *>"
2908 " (def_stmt))\n",
2909 exprs_len ? "else " : "");
2910 fprintf_indent (f, indent,
2911 " switch (gimple_call_combined_fn (def))\n");
2913 indent += 4;
2914 fprintf_indent (f, indent, "{\n");
2915 for (unsigned i = 0; i < fns_len; ++i)
2917 expr *e = as_a <expr *>(fns[i]->op);
2918 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2919 fprintf_indent (f, indent, " {\n");
2920 fns[i]->gen (f, indent + 4, true);
2921 fprintf_indent (f, indent, " break;\n");
2922 fprintf_indent (f, indent, " }\n");
2925 fprintf_indent (f, indent, "default:;\n");
2926 fprintf_indent (f, indent, "}\n");
2927 indent -= 4;
2930 indent -= 6;
2931 fprintf_indent (f, indent, " }\n");
2932 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
2933 here rather than in the next loop. */
2934 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2936 expr *e = as_a <expr *>(generic_exprs[i]->op);
2937 id_base *op = e->operation;
2938 if (*op == SSA_NAME && (exprs_len || fns_len))
2940 fprintf_indent (f, indent + 4, "{\n");
2941 generic_exprs[i]->gen (f, indent + 6, gimple);
2942 fprintf_indent (f, indent + 4, "}\n");
2946 fprintf_indent (f, indent, " break;\n");
2949 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2951 expr *e = as_a <expr *>(generic_exprs[i]->op);
2952 id_base *op = e->operation;
2953 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2954 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2955 else if (*op == SSA_NAME && (exprs_len || fns_len))
2956 /* Already handled above. */
2957 continue;
2958 else
2959 fprintf_indent (f, indent, "case %s:\n", op->id);
2960 fprintf_indent (f, indent, " {\n");
2961 generic_exprs[i]->gen (f, indent + 4, gimple);
2962 fprintf_indent (f, indent, " break;\n");
2963 fprintf_indent (f, indent, " }\n");
2966 if (gfns_len)
2968 fprintf_indent (f, indent,
2969 "case CALL_EXPR:\n");
2970 fprintf_indent (f, indent,
2971 " switch (get_call_combined_fn (%s))\n",
2972 kid_opname);
2973 fprintf_indent (f, indent,
2974 " {\n");
2975 indent += 4;
2977 for (unsigned j = 0; j < generic_fns.length (); ++j)
2979 expr *e = as_a <expr *>(generic_fns[j]->op);
2980 gcc_assert (e->operation->kind == id_base::FN);
2982 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2983 fprintf_indent (f, indent, " {\n");
2984 generic_fns[j]->gen (f, indent + 4, false);
2985 fprintf_indent (f, indent, " break;\n");
2986 fprintf_indent (f, indent, " }\n");
2988 fprintf_indent (f, indent, "default:;\n");
2990 indent -= 4;
2991 fprintf_indent (f, indent, " }\n");
2992 fprintf_indent (f, indent, " break;\n");
2995 /* Close switch (TREE_CODE ()). */
2996 if (exprs_len || fns_len || gexprs_len || gfns_len)
2998 indent -= 4;
2999 fprintf_indent (f, indent, " default:;\n");
3000 fprintf_indent (f, indent, " }\n");
3003 for (unsigned i = 0; i < preds.length (); ++i)
3005 expr *e = as_a <expr *> (preds[i]->op);
3006 predicate_id *p = as_a <predicate_id *> (e->operation);
3007 preds[i]->get_name (kid_opname);
3008 fprintf_indent (f, indent, "{\n");
3009 indent += 2;
3010 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
3011 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
3012 gimple ? "gimple" : "tree",
3013 p->id, kid_opname, kid_opname,
3014 gimple ? ", valueize" : "");
3015 fprintf_indent (f, indent, " {\n");
3016 for (int j = 0; j < p->nargs; ++j)
3018 char child_opname[20];
3019 preds[i]->gen_opname (child_opname, j);
3020 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
3021 child_opname, kid_opname, j);
3023 preds[i]->gen_kids (f, indent + 4, gimple);
3024 fprintf (f, "}\n");
3025 indent -= 2;
3026 fprintf_indent (f, indent, "}\n");
3029 for (unsigned i = 0; i < others.length (); ++i)
3030 others[i]->gen (f, indent, gimple);
3033 /* Generate matching code for the decision tree operand. */
3035 void
3036 dt_operand::gen (FILE *f, int indent, bool gimple)
3038 char opname[20];
3039 get_name (opname);
3041 unsigned n_braces = 0;
3043 if (type == DT_OPERAND)
3044 switch (op->type)
3046 case operand::OP_PREDICATE:
3047 n_braces = gen_predicate (f, indent, opname, gimple);
3048 break;
3050 case operand::OP_EXPR:
3051 if (gimple)
3052 n_braces = gen_gimple_expr (f, indent);
3053 else
3054 n_braces = gen_generic_expr (f, indent, opname);
3055 break;
3057 default:
3058 gcc_unreachable ();
3060 else if (type == DT_TRUE)
3062 else if (type == DT_MATCH)
3063 n_braces = gen_match_op (f, indent, opname, gimple);
3064 else
3065 gcc_unreachable ();
3067 indent += 4 * n_braces;
3068 gen_kids (f, indent, gimple);
3070 for (unsigned i = 0; i < n_braces; ++i)
3072 indent -= 4;
3073 if (indent < 0)
3074 indent = 0;
3075 fprintf_indent (f, indent, " }\n");
3080 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3081 step of a '(simplify ...)' or '(match ...)'. This handles everything
3082 that is not part of the decision tree (simplify->match).
3083 Main recursive worker. */
3085 void
3086 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3088 if (result)
3090 if (with_expr *w = dyn_cast <with_expr *> (result))
3092 fprintf_indent (f, indent, "{\n");
3093 indent += 4;
3094 output_line_directive (f, w->location);
3095 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3096 gen_1 (f, indent, gimple, w->subexpr);
3097 indent -= 4;
3098 fprintf_indent (f, indent, "}\n");
3099 return;
3101 else if (if_expr *ife = dyn_cast <if_expr *> (result))
3103 output_line_directive (f, ife->location);
3104 fprintf_indent (f, indent, "if (");
3105 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3106 fprintf (f, ")\n");
3107 fprintf_indent (f, indent + 2, "{\n");
3108 indent += 4;
3109 gen_1 (f, indent, gimple, ife->trueexpr);
3110 indent -= 4;
3111 fprintf_indent (f, indent + 2, "}\n");
3112 if (ife->falseexpr)
3114 fprintf_indent (f, indent, "else\n");
3115 fprintf_indent (f, indent + 2, "{\n");
3116 indent += 4;
3117 gen_1 (f, indent, gimple, ife->falseexpr);
3118 indent -= 4;
3119 fprintf_indent (f, indent + 2, "}\n");
3121 return;
3125 /* Analyze captures and perform early-outs on the incoming arguments
3126 that cover cases we cannot handle. */
3127 capture_info cinfo (s, result, gimple);
3128 if (s->kind == simplify::SIMPLIFY)
3130 if (!gimple)
3132 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3133 if (cinfo.force_no_side_effects & (1 << i))
3135 fprintf_indent (f, indent,
3136 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3138 if (verbose >= 1)
3139 warning_at (as_a <expr *> (s->match)->ops[i]->location,
3140 "forcing toplevel operand to have no "
3141 "side-effects");
3143 for (int i = 0; i <= s->capture_max; ++i)
3144 if (cinfo.info[i].cse_p)
3146 else if (cinfo.info[i].force_no_side_effects_p
3147 && (cinfo.info[i].toplevel_msk
3148 & cinfo.force_no_side_effects) == 0)
3150 fprintf_indent (f, indent,
3151 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3152 "return NULL_TREE;\n", i);
3153 if (verbose >= 1)
3154 warning_at (cinfo.info[i].c->location,
3155 "forcing captured operand to have no "
3156 "side-effects");
3158 else if ((cinfo.info[i].toplevel_msk
3159 & cinfo.force_no_side_effects) != 0)
3160 /* Mark capture as having no side-effects if we had to verify
3161 that via forced toplevel operand checks. */
3162 cinfo.info[i].force_no_side_effects_p = true;
3164 if (gimple)
3166 /* Force single-use restriction by only allowing simple
3167 results via setting seq to NULL. */
3168 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
3169 bool first_p = true;
3170 for (int i = 0; i <= s->capture_max; ++i)
3171 if (cinfo.info[i].force_single_use)
3173 if (first_p)
3175 fprintf_indent (f, indent, "if (lseq\n");
3176 fprintf_indent (f, indent, " && (");
3177 first_p = false;
3179 else
3181 fprintf (f, "\n");
3182 fprintf_indent (f, indent, " || ");
3184 fprintf (f, "!single_use (captures[%d])", i);
3186 if (!first_p)
3188 fprintf (f, "))\n");
3189 fprintf_indent (f, indent, " lseq = NULL;\n");
3194 fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_DETAILS)) "
3195 "fprintf (dump_file, \"Applying pattern ");
3196 output_line_directive (f,
3197 result ? result->location : s->match->location, true);
3198 fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3200 if (!result)
3202 /* If there is no result then this is a predicate implementation. */
3203 fprintf_indent (f, indent, "return true;\n");
3205 else if (gimple)
3207 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3208 in outermost position). */
3209 if (result->type == operand::OP_EXPR
3210 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
3211 result = as_a <expr *> (result)->ops[0];
3212 if (result->type == operand::OP_EXPR)
3214 expr *e = as_a <expr *> (result);
3215 id_base *opr = e->operation;
3216 bool is_predicate = false;
3217 /* When we delay operator substituting during lowering of fors we
3218 make sure that for code-gen purposes the effects of each substitute
3219 are the same. Thus just look at that. */
3220 if (user_id *uid = dyn_cast <user_id *> (opr))
3221 opr = uid->substitutes[0];
3222 else if (is_a <predicate_id *> (opr))
3223 is_predicate = true;
3224 if (!is_predicate)
3225 fprintf_indent (f, indent, "*res_code = %s;\n",
3226 *e->operation == CONVERT_EXPR
3227 ? "NOP_EXPR" : e->operation->id);
3228 for (unsigned j = 0; j < e->ops.length (); ++j)
3230 char dest[32];
3231 snprintf (dest, 32, "res_ops[%d]", j);
3232 const char *optype
3233 = get_operand_type (opr, j,
3234 "type", e->expr_type,
3235 j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
3236 /* We need to expand GENERIC conditions we captured from
3237 COND_EXPRs and we need to unshare them when substituting
3238 into COND_EXPRs. */
3239 int cond_handling = 0;
3240 if (!is_predicate)
3241 cond_handling = ((*opr == COND_EXPR
3242 || *opr == VEC_COND_EXPR) && j == 0) ? 1 : 2;
3243 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3244 &cinfo, indexes, cond_handling);
3247 /* Re-fold the toplevel result. It's basically an embedded
3248 gimple_build w/o actually building the stmt. */
3249 if (!is_predicate)
3250 fprintf_indent (f, indent,
3251 "gimple_resimplify%d (lseq, res_code, type, "
3252 "res_ops, valueize);\n", e->ops.length ());
3254 else if (result->type == operand::OP_CAPTURE
3255 || result->type == operand::OP_C_EXPR)
3257 result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
3258 &cinfo, indexes);
3259 fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
3260 if (is_a <capture *> (result)
3261 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3263 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3264 with substituting a capture of that. */
3265 fprintf_indent (f, indent,
3266 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3267 fprintf_indent (f, indent,
3268 " {\n");
3269 fprintf_indent (f, indent,
3270 " tree tem = res_ops[0];\n");
3271 fprintf_indent (f, indent,
3272 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3273 fprintf_indent (f, indent,
3274 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3275 fprintf_indent (f, indent,
3276 " }\n");
3279 else
3280 gcc_unreachable ();
3281 fprintf_indent (f, indent, "return true;\n");
3283 else /* GENERIC */
3285 bool is_predicate = false;
3286 if (result->type == operand::OP_EXPR)
3288 expr *e = as_a <expr *> (result);
3289 id_base *opr = e->operation;
3290 /* When we delay operator substituting during lowering of fors we
3291 make sure that for code-gen purposes the effects of each substitute
3292 are the same. Thus just look at that. */
3293 if (user_id *uid = dyn_cast <user_id *> (opr))
3294 opr = uid->substitutes[0];
3295 else if (is_a <predicate_id *> (opr))
3296 is_predicate = true;
3297 /* Search for captures used multiple times in the result expression
3298 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3299 original expression. */
3300 if (!is_predicate)
3301 for (int i = 0; i < s->capture_max + 1; ++i)
3303 if (cinfo.info[i].same_as != (unsigned)i
3304 || cinfo.info[i].cse_p)
3305 continue;
3306 if (cinfo.info[i].result_use_count
3307 > cinfo.info[i].match_use_count)
3308 fprintf_indent (f, indent,
3309 "if (! tree_invariant_p (captures[%d])) "
3310 "return NULL_TREE;\n", i);
3312 for (unsigned j = 0; j < e->ops.length (); ++j)
3314 char dest[32];
3315 if (is_predicate)
3316 snprintf (dest, 32, "res_ops[%d]", j);
3317 else
3319 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3320 snprintf (dest, 32, "res_op%d", j);
3322 const char *optype
3323 = get_operand_type (opr, j,
3324 "type", e->expr_type,
3325 j == 0
3326 ? NULL : "TREE_TYPE (res_op0)");
3327 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3328 &cinfo, indexes);
3330 if (is_predicate)
3331 fprintf_indent (f, indent, "return true;\n");
3332 else
3334 fprintf_indent (f, indent, "tree res;\n");
3335 /* Re-fold the toplevel result. Use non_lvalue to
3336 build NON_LVALUE_EXPRs so they get properly
3337 ignored when in GIMPLE form. */
3338 if (*opr == NON_LVALUE_EXPR)
3339 fprintf_indent (f, indent,
3340 "res = non_lvalue_loc (loc, res_op0);\n");
3341 else
3343 if (is_a <operator_id *> (opr))
3344 fprintf_indent (f, indent,
3345 "res = fold_build%d_loc (loc, %s, type",
3346 e->ops.length (),
3347 *e->operation == CONVERT_EXPR
3348 ? "NOP_EXPR" : e->operation->id);
3349 else
3350 fprintf_indent (f, indent,
3351 "res = maybe_build_call_expr_loc (loc, "
3352 "%s, type, %d", e->operation->id,
3353 e->ops.length());
3354 for (unsigned j = 0; j < e->ops.length (); ++j)
3355 fprintf (f, ", res_op%d", j);
3356 fprintf (f, ");\n");
3357 if (!is_a <operator_id *> (opr))
3359 fprintf_indent (f, indent, "if (!res)\n");
3360 fprintf_indent (f, indent, " return NULL_TREE;\n");
3365 else if (result->type == operand::OP_CAPTURE
3366 || result->type == operand::OP_C_EXPR)
3369 fprintf_indent (f, indent, "tree res;\n");
3370 result->gen_transform (f, indent, "res", false, 1, "type",
3371 &cinfo, indexes);
3373 else
3374 gcc_unreachable ();
3375 if (!is_predicate)
3377 /* Search for captures not used in the result expression and dependent
3378 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3379 for (int i = 0; i < s->capture_max + 1; ++i)
3381 if (cinfo.info[i].same_as != (unsigned)i)
3382 continue;
3383 if (!cinfo.info[i].force_no_side_effects_p
3384 && !cinfo.info[i].expr_p
3385 && cinfo.info[i].result_use_count == 0)
3387 fprintf_indent (f, indent,
3388 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3390 fprintf_indent (f, indent + 2,
3391 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3392 "fold_ignored_result (captures[%d]), res);\n",
3396 fprintf_indent (f, indent, "return res;\n");
3401 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3402 step of a '(simplify ...)' or '(match ...)'. This handles everything
3403 that is not part of the decision tree (simplify->match). */
3405 void
3406 dt_simplify::gen (FILE *f, int indent, bool gimple)
3408 fprintf_indent (f, indent, "{\n");
3409 indent += 2;
3410 output_line_directive (f,
3411 s->result ? s->result->location : s->match->location);
3412 if (s->capture_max >= 0)
3414 char opname[20];
3415 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3416 s->capture_max + 1, indexes[0]->get_name (opname));
3418 for (int i = 1; i <= s->capture_max; ++i)
3420 if (!indexes[i])
3421 break;
3422 fprintf (f, ", %s", indexes[i]->get_name (opname));
3424 fprintf (f, " };\n");
3427 /* If we have a split-out function for the actual transform, call it. */
3428 if (info && info->fname)
3430 if (gimple)
3432 fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
3433 "valueize, type, captures", info->fname);
3434 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3435 if (s->for_subst_vec[i].first->used)
3436 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3437 fprintf (f, "))\n");
3438 fprintf_indent (f, indent, " return true;\n");
3440 else
3442 fprintf_indent (f, indent, "tree res = %s (loc, type",
3443 info->fname);
3444 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3445 fprintf (f, ", op%d", i);
3446 fprintf (f, ", captures");
3447 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3449 if (s->for_subst_vec[i].first->used)
3450 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3452 fprintf (f, ");\n");
3453 fprintf_indent (f, indent, "if (res) return res;\n");
3456 else
3458 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3460 if (! s->for_subst_vec[i].first->used)
3461 continue;
3462 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3463 fprintf_indent (f, indent, "enum tree_code %s = %s;\n",
3464 s->for_subst_vec[i].first->id,
3465 s->for_subst_vec[i].second->id);
3466 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3467 fprintf_indent (f, indent, "combined_fn %s = %s;\n",
3468 s->for_subst_vec[i].first->id,
3469 s->for_subst_vec[i].second->id);
3470 else
3471 gcc_unreachable ();
3473 gen_1 (f, indent, gimple, s->result);
3476 indent -= 2;
3477 fprintf_indent (f, indent, "}\n");
3481 /* Hash function for finding equivalent transforms. */
3483 hashval_t
3484 sinfo_hashmap_traits::hash (const key_type &v)
3486 /* Only bother to compare those originating from the same source pattern. */
3487 return v->s->result->location;
3490 /* Compare function for finding equivalent transforms. */
3492 static bool
3493 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3495 if (o1->type != o2->type)
3496 return false;
3498 switch (o1->type)
3500 case operand::OP_IF:
3502 if_expr *if1 = as_a <if_expr *> (o1);
3503 if_expr *if2 = as_a <if_expr *> (o2);
3504 /* ??? Properly compare c-exprs. */
3505 if (if1->cond != if2->cond)
3506 return false;
3507 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3508 return false;
3509 if (if1->falseexpr != if2->falseexpr
3510 || (if1->falseexpr
3511 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3512 return false;
3513 return true;
3515 case operand::OP_WITH:
3517 with_expr *with1 = as_a <with_expr *> (o1);
3518 with_expr *with2 = as_a <with_expr *> (o2);
3519 if (with1->with != with2->with)
3520 return false;
3521 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3523 default:;
3526 /* We've hit a result. Time to compare capture-infos - this is required
3527 in addition to the conservative pointer-equivalency of the result IL. */
3528 capture_info cinfo1 (s1, o1, true);
3529 capture_info cinfo2 (s2, o2, true);
3531 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3532 || cinfo1.info.length () != cinfo2.info.length ())
3533 return false;
3535 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3537 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3538 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3539 || (cinfo1.info[i].force_no_side_effects_p
3540 != cinfo2.info[i].force_no_side_effects_p)
3541 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3542 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3543 /* toplevel_msk is an optimization */
3544 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3545 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3546 /* the pointer back to the capture is for diagnostics only */)
3547 return false;
3550 /* ??? Deep-compare the actual result. */
3551 return o1 == o2;
3554 bool
3555 sinfo_hashmap_traits::equal_keys (const key_type &v,
3556 const key_type &candidate)
3558 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3562 /* Main entry to generate code for matching GIMPLE IL off the decision
3563 tree. */
3565 void
3566 decision_tree::gen (FILE *f, bool gimple)
3568 sinfo_map_t si;
3570 root->analyze (si);
3572 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3573 "a total number of %u nodes\n",
3574 gimple ? "GIMPLE" : "GENERIC",
3575 root->num_leafs, root->max_level, root->total_size);
3577 /* First split out the transform part of equal leafs. */
3578 unsigned rcnt = 0;
3579 unsigned fcnt = 1;
3580 for (sinfo_map_t::iterator iter = si.begin ();
3581 iter != si.end (); ++iter)
3583 sinfo *s = (*iter).second;
3584 /* Do not split out single uses. */
3585 if (s->cnt <= 1)
3586 continue;
3588 rcnt += s->cnt - 1;
3589 if (verbose >= 1)
3591 fprintf (stderr, "found %u uses of", s->cnt);
3592 output_line_directive (stderr, s->s->s->result->location);
3595 /* Generate a split out function with the leaf transform code. */
3596 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3597 fcnt++);
3598 if (gimple)
3599 fprintf (f, "\nstatic bool\n"
3600 "%s (code_helper *res_code, tree *res_ops,\n"
3601 " gimple_seq *seq, tree (*valueize)(tree) "
3602 "ATTRIBUTE_UNUSED,\n"
3603 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3604 "(captures)\n",
3605 s->fname);
3606 else
3608 fprintf (f, "\nstatic tree\n"
3609 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3610 (*iter).second->fname);
3611 for (unsigned i = 0;
3612 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3613 fprintf (f, " tree ARG_UNUSED (op%d),", i);
3614 fprintf (f, " tree *captures\n");
3616 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3618 if (! s->s->s->for_subst_vec[i].first->used)
3619 continue;
3620 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3621 fprintf (f, ", enum tree_code ARG_UNUSED (%s)",
3622 s->s->s->for_subst_vec[i].first->id);
3623 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3624 fprintf (f, ", combined_fn ARG_UNUSED (%s)",
3625 s->s->s->for_subst_vec[i].first->id);
3628 fprintf (f, ")\n{\n");
3629 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3630 if (gimple)
3631 fprintf (f, " return false;\n");
3632 else
3633 fprintf (f, " return NULL_TREE;\n");
3634 fprintf (f, "}\n");
3636 fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3638 for (unsigned n = 1; n <= 3; ++n)
3640 /* First generate split-out functions. */
3641 for (unsigned i = 0; i < root->kids.length (); i++)
3643 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3644 expr *e = static_cast<expr *>(dop->op);
3645 if (e->ops.length () != n
3646 /* Builtin simplifications are somewhat premature on
3647 GENERIC. The following drops patterns with outermost
3648 calls. It's easy to emit overloads for function code
3649 though if necessary. */
3650 || (!gimple
3651 && e->operation->kind != id_base::CODE))
3652 continue;
3654 if (gimple)
3655 fprintf (f, "\nstatic bool\n"
3656 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3657 " gimple_seq *seq, tree (*valueize)(tree) "
3658 "ATTRIBUTE_UNUSED,\n"
3659 " code_helper ARG_UNUSED (code), tree "
3660 "ARG_UNUSED (type)\n",
3661 e->operation->id);
3662 else
3663 fprintf (f, "\nstatic tree\n"
3664 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3665 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3666 e->operation->id);
3667 for (unsigned i = 0; i < n; ++i)
3668 fprintf (f, ", tree op%d", i);
3669 fprintf (f, ")\n");
3670 fprintf (f, "{\n");
3671 dop->gen_kids (f, 2, gimple);
3672 if (gimple)
3673 fprintf (f, " return false;\n");
3674 else
3675 fprintf (f, " return NULL_TREE;\n");
3676 fprintf (f, "}\n");
3679 /* Then generate the main entry with the outermost switch and
3680 tail-calls to the split-out functions. */
3681 if (gimple)
3682 fprintf (f, "\nstatic bool\n"
3683 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3684 " gimple_seq *seq, tree (*valueize)(tree),\n"
3685 " code_helper code, tree type");
3686 else
3687 fprintf (f, "\ntree\n"
3688 "generic_simplify (location_t loc, enum tree_code code, "
3689 "tree type ATTRIBUTE_UNUSED");
3690 for (unsigned i = 0; i < n; ++i)
3691 fprintf (f, ", tree op%d", i);
3692 fprintf (f, ")\n");
3693 fprintf (f, "{\n");
3695 if (gimple)
3696 fprintf (f, " switch (code.get_rep())\n"
3697 " {\n");
3698 else
3699 fprintf (f, " switch (code)\n"
3700 " {\n");
3701 for (unsigned i = 0; i < root->kids.length (); i++)
3703 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3704 expr *e = static_cast<expr *>(dop->op);
3705 if (e->ops.length () != n
3706 /* Builtin simplifications are somewhat premature on
3707 GENERIC. The following drops patterns with outermost
3708 calls. It's easy to emit overloads for function code
3709 though if necessary. */
3710 || (!gimple
3711 && e->operation->kind != id_base::CODE))
3712 continue;
3714 if (*e->operation == CONVERT_EXPR
3715 || *e->operation == NOP_EXPR)
3716 fprintf (f, " CASE_CONVERT:\n");
3717 else
3718 fprintf (f, " case %s%s:\n",
3719 is_a <fn_id *> (e->operation) ? "-" : "",
3720 e->operation->id);
3721 if (gimple)
3722 fprintf (f, " return gimple_simplify_%s (res_code, res_ops, "
3723 "seq, valueize, code, type", e->operation->id);
3724 else
3725 fprintf (f, " return generic_simplify_%s (loc, code, type",
3726 e->operation->id);
3727 for (unsigned i = 0; i < n; ++i)
3728 fprintf (f, ", op%d", i);
3729 fprintf (f, ");\n");
3731 fprintf (f, " default:;\n"
3732 " }\n");
3734 if (gimple)
3735 fprintf (f, " return false;\n");
3736 else
3737 fprintf (f, " return NULL_TREE;\n");
3738 fprintf (f, "}\n");
3742 /* Output code to implement the predicate P from the decision tree DT. */
3744 void
3745 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3747 fprintf (f, "\nbool\n"
3748 "%s%s (tree t%s%s)\n"
3749 "{\n", gimple ? "gimple_" : "tree_", p->id,
3750 p->nargs > 0 ? ", tree *res_ops" : "",
3751 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3752 /* Conveniently make 'type' available. */
3753 fprintf_indent (f, 2, "tree type = TREE_TYPE (t);\n");
3755 if (!gimple)
3756 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3757 dt.root->gen_kids (f, 2, gimple);
3759 fprintf_indent (f, 2, "return false;\n"
3760 "}\n");
3763 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3765 static void
3766 write_header (FILE *f, const char *head)
3768 fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3769 fprintf (f, " a IL pattern matching and simplification description. */\n");
3771 /* Include the header instead of writing it awkwardly quoted here. */
3772 fprintf (f, "\n#include \"%s\"\n", head);
3777 /* AST parsing. */
3779 class parser
3781 public:
3782 parser (cpp_reader *);
3784 private:
3785 const cpp_token *next ();
3786 const cpp_token *peek (unsigned = 1);
3787 const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3788 const cpp_token *expect (enum cpp_ttype);
3789 const cpp_token *eat_token (enum cpp_ttype);
3790 const char *get_string ();
3791 const char *get_ident ();
3792 const cpp_token *eat_ident (const char *);
3793 const char *get_number ();
3795 unsigned get_internal_capture_id ();
3797 id_base *parse_operation ();
3798 operand *parse_capture (operand *, bool);
3799 operand *parse_expr ();
3800 c_expr *parse_c_expr (cpp_ttype);
3801 operand *parse_op ();
3803 void record_operlist (source_location, user_id *);
3805 void parse_pattern ();
3806 operand *parse_result (operand *, predicate_id *);
3807 void push_simplify (simplify::simplify_kind,
3808 vec<simplify *>&, operand *, operand *);
3809 void parse_simplify (simplify::simplify_kind,
3810 vec<simplify *>&, predicate_id *, operand *);
3811 void parse_for (source_location);
3812 void parse_if (source_location);
3813 void parse_predicates (source_location);
3814 void parse_operator_list (source_location);
3816 void finish_match_operand (operand *);
3818 cpp_reader *r;
3819 vec<c_expr *> active_ifs;
3820 vec<vec<user_id *> > active_fors;
3821 hash_set<user_id *> *oper_lists_set;
3822 vec<user_id *> oper_lists;
3824 cid_map_t *capture_ids;
3826 public:
3827 vec<simplify *> simplifiers;
3828 vec<predicate_id *> user_predicates;
3829 bool parsing_match_operand;
3832 /* Lexing helpers. */
3834 /* Read the next non-whitespace token from R. */
3836 const cpp_token *
3837 parser::next ()
3839 const cpp_token *token;
3842 token = cpp_get_token (r);
3844 while (token->type == CPP_PADDING);
3845 return token;
3848 /* Peek at the next non-whitespace token from R. */
3850 const cpp_token *
3851 parser::peek (unsigned num)
3853 const cpp_token *token;
3854 unsigned i = 0;
3857 token = cpp_peek_token (r, i++);
3859 while (token->type == CPP_PADDING
3860 || (--num > 0));
3861 /* If we peek at EOF this is a fatal error as it leaves the
3862 cpp_reader in unusable state. Assume we really wanted a
3863 token and thus this EOF is unexpected. */
3864 if (token->type == CPP_EOF)
3865 fatal_at (token, "unexpected end of file");
3866 return token;
3869 /* Peek at the next identifier token (or return NULL if the next
3870 token is not an identifier or equal to ID if supplied). */
3872 const cpp_token *
3873 parser::peek_ident (const char *id, unsigned num)
3875 const cpp_token *token = peek (num);
3876 if (token->type != CPP_NAME)
3877 return 0;
3879 if (id == 0)
3880 return token;
3882 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3883 if (strcmp (id, t) == 0)
3884 return token;
3886 return 0;
3889 /* Read the next token from R and assert it is of type TK. */
3891 const cpp_token *
3892 parser::expect (enum cpp_ttype tk)
3894 const cpp_token *token = next ();
3895 if (token->type != tk)
3896 fatal_at (token, "expected %s, got %s",
3897 cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3899 return token;
3902 /* Consume the next token from R and assert it is of type TK. */
3904 const cpp_token *
3905 parser::eat_token (enum cpp_ttype tk)
3907 return expect (tk);
3910 /* Read the next token from R and assert it is of type CPP_STRING and
3911 return its value. */
3913 const char *
3914 parser::get_string ()
3916 const cpp_token *token = expect (CPP_STRING);
3917 return (const char *)token->val.str.text;
3920 /* Read the next token from R and assert it is of type CPP_NAME and
3921 return its value. */
3923 const char *
3924 parser::get_ident ()
3926 const cpp_token *token = expect (CPP_NAME);
3927 return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3930 /* Eat an identifier token with value S from R. */
3932 const cpp_token *
3933 parser::eat_ident (const char *s)
3935 const cpp_token *token = peek ();
3936 const char *t = get_ident ();
3937 if (strcmp (s, t) != 0)
3938 fatal_at (token, "expected '%s' got '%s'\n", s, t);
3939 return token;
3942 /* Read the next token from R and assert it is of type CPP_NUMBER and
3943 return its value. */
3945 const char *
3946 parser::get_number ()
3948 const cpp_token *token = expect (CPP_NUMBER);
3949 return (const char *)token->val.str.text;
3952 /* Return a capture ID that can be used internally. */
3954 unsigned
3955 parser::get_internal_capture_id ()
3957 unsigned newid = capture_ids->elements ();
3958 /* Big enough for a 32-bit UINT_MAX plus prefix. */
3959 char id[13];
3960 bool existed;
3961 sprintf (id, "__%u", newid);
3962 capture_ids->get_or_insert (xstrdup (id), &existed);
3963 if (existed)
3964 fatal ("reserved capture id '%s' already used", id);
3965 return newid;
3968 /* Record an operator-list use for transparent for handling. */
3970 void
3971 parser::record_operlist (source_location loc, user_id *p)
3973 if (!oper_lists_set->add (p))
3975 if (!oper_lists.is_empty ()
3976 && oper_lists[0]->substitutes.length () != p->substitutes.length ())
3977 fatal_at (loc, "User-defined operator list does not have the "
3978 "same number of entries as others used in the pattern");
3979 oper_lists.safe_push (p);
3983 /* Parse the operator ID, special-casing convert?, convert1? and
3984 convert2? */
3986 id_base *
3987 parser::parse_operation ()
3989 const cpp_token *id_tok = peek ();
3990 const char *id = get_ident ();
3991 const cpp_token *token = peek ();
3992 if (strcmp (id, "convert0") == 0)
3993 fatal_at (id_tok, "use 'convert?' here");
3994 else if (strcmp (id, "view_convert0") == 0)
3995 fatal_at (id_tok, "use 'view_convert?' here");
3996 if (token->type == CPP_QUERY
3997 && !(token->flags & PREV_WHITE))
3999 if (strcmp (id, "convert") == 0)
4000 id = "convert0";
4001 else if (strcmp (id, "convert1") == 0)
4003 else if (strcmp (id, "convert2") == 0)
4005 else if (strcmp (id, "view_convert") == 0)
4006 id = "view_convert0";
4007 else if (strcmp (id, "view_convert1") == 0)
4009 else if (strcmp (id, "view_convert2") == 0)
4011 else
4012 fatal_at (id_tok, "non-convert operator conditionalized");
4014 if (!parsing_match_operand)
4015 fatal_at (id_tok, "conditional convert can only be used in "
4016 "match expression");
4017 eat_token (CPP_QUERY);
4019 else if (strcmp (id, "convert1") == 0
4020 || strcmp (id, "convert2") == 0
4021 || strcmp (id, "view_convert1") == 0
4022 || strcmp (id, "view_convert2") == 0)
4023 fatal_at (id_tok, "expected '?' after conditional operator");
4024 id_base *op = get_operator (id);
4025 if (!op)
4026 fatal_at (id_tok, "unknown operator %s", id);
4028 user_id *p = dyn_cast<user_id *> (op);
4029 if (p && p->is_oper_list)
4031 if (active_fors.length() == 0)
4032 record_operlist (id_tok->src_loc, p);
4033 else
4034 fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
4036 return op;
4039 /* Parse a capture.
4040 capture = '@'<number> */
4042 struct operand *
4043 parser::parse_capture (operand *op, bool require_existing)
4045 source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
4046 const cpp_token *token = peek ();
4047 const char *id = NULL;
4048 bool value_match = false;
4049 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4050 if (token->type == CPP_ATSIGN
4051 && ! (token->flags & PREV_WHITE)
4052 && parsing_match_operand)
4054 eat_token (CPP_ATSIGN);
4055 token = peek ();
4056 value_match = true;
4058 if (token->type == CPP_NUMBER)
4059 id = get_number ();
4060 else if (token->type == CPP_NAME)
4061 id = get_ident ();
4062 else
4063 fatal_at (token, "expected number or identifier");
4064 unsigned next_id = capture_ids->elements ();
4065 bool existed;
4066 unsigned &num = capture_ids->get_or_insert (id, &existed);
4067 if (!existed)
4069 if (require_existing)
4070 fatal_at (src_loc, "unknown capture id");
4071 num = next_id;
4073 return new capture (src_loc, num, op, value_match);
4076 /* Parse an expression
4077 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4079 struct operand *
4080 parser::parse_expr ()
4082 const cpp_token *token = peek ();
4083 expr *e = new expr (parse_operation (), token->src_loc);
4084 token = peek ();
4085 operand *op;
4086 bool is_commutative = false;
4087 bool force_capture = false;
4088 const char *expr_type = NULL;
4090 if (token->type == CPP_COLON
4091 && !(token->flags & PREV_WHITE))
4093 eat_token (CPP_COLON);
4094 token = peek ();
4095 if (token->type == CPP_NAME
4096 && !(token->flags & PREV_WHITE))
4098 const char *s = get_ident ();
4099 if (!parsing_match_operand)
4100 expr_type = s;
4101 else
4103 const char *sp = s;
4104 while (*sp)
4106 if (*sp == 'c')
4108 if (operator_id *p
4109 = dyn_cast<operator_id *> (e->operation))
4111 if (!commutative_tree_code (p->code)
4112 && !comparison_code_p (p->code))
4113 fatal_at (token, "operation is not commutative");
4115 else if (user_id *p = dyn_cast<user_id *> (e->operation))
4116 for (unsigned i = 0;
4117 i < p->substitutes.length (); ++i)
4119 if (operator_id *q
4120 = dyn_cast<operator_id *> (p->substitutes[i]))
4122 if (!commutative_tree_code (q->code)
4123 && !comparison_code_p (q->code))
4124 fatal_at (token, "operation %s is not "
4125 "commutative", q->id);
4128 is_commutative = true;
4130 else if (*sp == 'C')
4131 is_commutative = true;
4132 else if (*sp == 's')
4134 e->force_single_use = true;
4135 force_capture = true;
4137 else
4138 fatal_at (token, "flag %c not recognized", *sp);
4139 sp++;
4142 token = peek ();
4144 else
4145 fatal_at (token, "expected flag or type specifying identifier");
4148 if (token->type == CPP_ATSIGN
4149 && !(token->flags & PREV_WHITE))
4150 op = parse_capture (e, false);
4151 else if (force_capture)
4153 unsigned num = get_internal_capture_id ();
4154 op = new capture (token->src_loc, num, e, false);
4156 else
4157 op = e;
4160 const cpp_token *token = peek ();
4161 if (token->type == CPP_CLOSE_PAREN)
4163 if (e->operation->nargs != -1
4164 && e->operation->nargs != (int) e->ops.length ())
4165 fatal_at (token, "'%s' expects %u operands, not %u",
4166 e->operation->id, e->operation->nargs, e->ops.length ());
4167 if (is_commutative)
4169 if (e->ops.length () == 2)
4170 e->is_commutative = true;
4171 else
4172 fatal_at (token, "only binary operators or function with "
4173 "two arguments can be marked commutative");
4175 e->expr_type = expr_type;
4176 return op;
4178 else if (!(token->flags & PREV_WHITE))
4179 fatal_at (token, "expected expression operand");
4181 e->append_op (parse_op ());
4183 while (1);
4186 /* Lex native C code delimited by START recording the preprocessing tokens
4187 for later processing.
4188 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4190 c_expr *
4191 parser::parse_c_expr (cpp_ttype start)
4193 const cpp_token *token;
4194 cpp_ttype end;
4195 unsigned opencnt;
4196 vec<cpp_token> code = vNULL;
4197 unsigned nr_stmts = 0;
4198 source_location loc = eat_token (start)->src_loc;
4199 if (start == CPP_OPEN_PAREN)
4200 end = CPP_CLOSE_PAREN;
4201 else if (start == CPP_OPEN_BRACE)
4202 end = CPP_CLOSE_BRACE;
4203 else
4204 gcc_unreachable ();
4205 opencnt = 1;
4208 token = next ();
4210 /* Count brace pairs to find the end of the expr to match. */
4211 if (token->type == start)
4212 opencnt++;
4213 else if (token->type == end
4214 && --opencnt == 0)
4215 break;
4216 else if (token->type == CPP_EOF)
4217 fatal_at (token, "unexpected end of file");
4219 /* This is a lame way of counting the number of statements. */
4220 if (token->type == CPP_SEMICOLON)
4221 nr_stmts++;
4223 /* If this is possibly a user-defined identifier mark it used. */
4224 if (token->type == CPP_NAME)
4226 id_base *idb = get_operator ((const char *)CPP_HASHNODE
4227 (token->val.node.node)->ident.str);
4228 user_id *p;
4229 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
4230 record_operlist (token->src_loc, p);
4233 /* Record the token. */
4234 code.safe_push (*token);
4236 while (1);
4237 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4240 /* Parse an operand which is either an expression, a predicate or
4241 a standalone capture.
4242 op = predicate | expr | c_expr | capture */
4244 struct operand *
4245 parser::parse_op ()
4247 const cpp_token *token = peek ();
4248 struct operand *op = NULL;
4249 if (token->type == CPP_OPEN_PAREN)
4251 eat_token (CPP_OPEN_PAREN);
4252 op = parse_expr ();
4253 eat_token (CPP_CLOSE_PAREN);
4255 else if (token->type == CPP_OPEN_BRACE)
4257 op = parse_c_expr (CPP_OPEN_BRACE);
4259 else
4261 /* Remaining ops are either empty or predicates */
4262 if (token->type == CPP_NAME)
4264 const char *id = get_ident ();
4265 id_base *opr = get_operator (id);
4266 if (!opr)
4267 fatal_at (token, "expected predicate name");
4268 if (operator_id *code = dyn_cast <operator_id *> (opr))
4270 if (code->nargs != 0)
4271 fatal_at (token, "using an operator with operands as predicate");
4272 /* Parse the zero-operand operator "predicates" as
4273 expression. */
4274 op = new expr (opr, token->src_loc);
4276 else if (user_id *code = dyn_cast <user_id *> (opr))
4278 if (code->nargs != 0)
4279 fatal_at (token, "using an operator with operands as predicate");
4280 /* Parse the zero-operand operator "predicates" as
4281 expression. */
4282 op = new expr (opr, token->src_loc);
4284 else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
4285 op = new predicate (p, token->src_loc);
4286 else
4287 fatal_at (token, "using an unsupported operator as predicate");
4288 if (!parsing_match_operand)
4289 fatal_at (token, "predicates are only allowed in match expression");
4290 token = peek ();
4291 if (token->flags & PREV_WHITE)
4292 return op;
4294 else if (token->type != CPP_COLON
4295 && token->type != CPP_ATSIGN)
4296 fatal_at (token, "expected expression or predicate");
4297 /* optionally followed by a capture and a predicate. */
4298 if (token->type == CPP_COLON)
4299 fatal_at (token, "not implemented: predicate on leaf operand");
4300 if (token->type == CPP_ATSIGN)
4301 op = parse_capture (op, !parsing_match_operand);
4304 return op;
4307 /* Create a new simplify from the current parsing state and MATCH,
4308 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4310 void
4311 parser::push_simplify (simplify::simplify_kind kind,
4312 vec<simplify *>& simplifiers,
4313 operand *match, operand *result)
4315 /* Build and push a temporary for operator list uses in expressions. */
4316 if (!oper_lists.is_empty ())
4317 active_fors.safe_push (oper_lists);
4319 simplifiers.safe_push
4320 (new simplify (kind, match, result,
4321 active_fors.copy (), capture_ids));
4323 if (!oper_lists.is_empty ())
4324 active_fors.pop ();
4327 /* Parse
4328 <result-op> = <op> | <if> | <with>
4329 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4330 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4331 and return it. */
4333 operand *
4334 parser::parse_result (operand *result, predicate_id *matcher)
4336 const cpp_token *token = peek ();
4337 if (token->type != CPP_OPEN_PAREN)
4338 return parse_op ();
4340 eat_token (CPP_OPEN_PAREN);
4341 if (peek_ident ("if"))
4343 eat_ident ("if");
4344 if_expr *ife = new if_expr (token->src_loc);
4345 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4346 if (peek ()->type == CPP_OPEN_PAREN)
4348 ife->trueexpr = parse_result (result, matcher);
4349 if (peek ()->type == CPP_OPEN_PAREN)
4350 ife->falseexpr = parse_result (result, matcher);
4351 else if (peek ()->type != CPP_CLOSE_PAREN)
4352 ife->falseexpr = parse_op ();
4354 else if (peek ()->type != CPP_CLOSE_PAREN)
4356 ife->trueexpr = parse_op ();
4357 if (peek ()->type == CPP_OPEN_PAREN)
4358 ife->falseexpr = parse_result (result, matcher);
4359 else if (peek ()->type != CPP_CLOSE_PAREN)
4360 ife->falseexpr = parse_op ();
4362 /* If this if is immediately closed then it contains a
4363 manual matcher or is part of a predicate definition. */
4364 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4366 if (!matcher)
4367 fatal_at (peek (), "manual transform not implemented");
4368 ife->trueexpr = result;
4370 eat_token (CPP_CLOSE_PAREN);
4371 return ife;
4373 else if (peek_ident ("with"))
4375 eat_ident ("with");
4376 with_expr *withe = new with_expr (token->src_loc);
4377 /* Parse (with c-expr expr) as (if-with (true) expr). */
4378 withe->with = parse_c_expr (CPP_OPEN_BRACE);
4379 withe->with->nr_stmts = 0;
4380 withe->subexpr = parse_result (result, matcher);
4381 eat_token (CPP_CLOSE_PAREN);
4382 return withe;
4384 else if (peek_ident ("switch"))
4386 token = eat_ident ("switch");
4387 source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4388 eat_ident ("if");
4389 if_expr *ife = new if_expr (ifloc);
4390 operand *res = ife;
4391 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4392 if (peek ()->type == CPP_OPEN_PAREN)
4393 ife->trueexpr = parse_result (result, matcher);
4394 else
4395 ife->trueexpr = parse_op ();
4396 eat_token (CPP_CLOSE_PAREN);
4397 if (peek ()->type != CPP_OPEN_PAREN
4398 || !peek_ident ("if", 2))
4399 fatal_at (token, "switch can be implemented with a single if");
4400 while (peek ()->type != CPP_CLOSE_PAREN)
4402 if (peek ()->type == CPP_OPEN_PAREN)
4404 if (peek_ident ("if", 2))
4406 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4407 eat_ident ("if");
4408 ife->falseexpr = new if_expr (ifloc);
4409 ife = as_a <if_expr *> (ife->falseexpr);
4410 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4411 if (peek ()->type == CPP_OPEN_PAREN)
4412 ife->trueexpr = parse_result (result, matcher);
4413 else
4414 ife->trueexpr = parse_op ();
4415 eat_token (CPP_CLOSE_PAREN);
4417 else
4419 /* switch default clause */
4420 ife->falseexpr = parse_result (result, matcher);
4421 eat_token (CPP_CLOSE_PAREN);
4422 return res;
4425 else
4427 /* switch default clause */
4428 ife->falseexpr = parse_op ();
4429 eat_token (CPP_CLOSE_PAREN);
4430 return res;
4433 eat_token (CPP_CLOSE_PAREN);
4434 return res;
4436 else
4438 operand *op = result;
4439 if (!matcher)
4440 op = parse_expr ();
4441 eat_token (CPP_CLOSE_PAREN);
4442 return op;
4446 /* Parse
4447 simplify = 'simplify' <expr> <result-op>
4449 match = 'match' <ident> <expr> [<result-op>]
4450 and fill SIMPLIFIERS with the results. */
4452 void
4453 parser::parse_simplify (simplify::simplify_kind kind,
4454 vec<simplify *>& simplifiers, predicate_id *matcher,
4455 operand *result)
4457 /* Reset the capture map. */
4458 if (!capture_ids)
4459 capture_ids = new cid_map_t;
4460 /* Reset oper_lists and set. */
4461 hash_set <user_id *> olist;
4462 oper_lists_set = &olist;
4463 oper_lists = vNULL;
4465 const cpp_token *loc = peek ();
4466 parsing_match_operand = true;
4467 struct operand *match = parse_op ();
4468 finish_match_operand (match);
4469 parsing_match_operand = false;
4470 if (match->type == operand::OP_CAPTURE && !matcher)
4471 fatal_at (loc, "outermost expression cannot be captured");
4472 if (match->type == operand::OP_EXPR
4473 && is_a <predicate_id *> (as_a <expr *> (match)->operation))
4474 fatal_at (loc, "outermost expression cannot be a predicate");
4476 /* Splice active_ifs onto result and continue parsing the
4477 "then" expr. */
4478 if_expr *active_if = NULL;
4479 for (int i = active_ifs.length (); i > 0; --i)
4481 if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4482 ifc->cond = active_ifs[i-1];
4483 ifc->trueexpr = active_if;
4484 active_if = ifc;
4486 if_expr *outermost_if = active_if;
4487 while (active_if && active_if->trueexpr)
4488 active_if = as_a <if_expr *> (active_if->trueexpr);
4490 const cpp_token *token = peek ();
4492 /* If this if is immediately closed then it is part of a predicate
4493 definition. Push it. */
4494 if (token->type == CPP_CLOSE_PAREN)
4496 if (!matcher)
4497 fatal_at (token, "expected transform expression");
4498 if (active_if)
4500 active_if->trueexpr = result;
4501 result = outermost_if;
4503 push_simplify (kind, simplifiers, match, result);
4504 return;
4507 operand *tem = parse_result (result, matcher);
4508 if (active_if)
4510 active_if->trueexpr = tem;
4511 result = outermost_if;
4513 else
4514 result = tem;
4516 push_simplify (kind, simplifiers, match, result);
4519 /* Parsing of the outer control structures. */
4521 /* Parse a for expression
4522 for = '(' 'for' <subst>... <pattern> ')'
4523 subst = <ident> '(' <ident>... ')' */
4525 void
4526 parser::parse_for (source_location)
4528 auto_vec<const cpp_token *> user_id_tokens;
4529 vec<user_id *> user_ids = vNULL;
4530 const cpp_token *token;
4531 unsigned min_n_opers = 0, max_n_opers = 0;
4533 while (1)
4535 token = peek ();
4536 if (token->type != CPP_NAME)
4537 break;
4539 /* Insert the user defined operators into the operator hash. */
4540 const char *id = get_ident ();
4541 if (get_operator (id, true) != NULL)
4542 fatal_at (token, "operator already defined");
4543 user_id *op = new user_id (id);
4544 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4545 *slot = op;
4546 user_ids.safe_push (op);
4547 user_id_tokens.safe_push (token);
4549 eat_token (CPP_OPEN_PAREN);
4551 int arity = -1;
4552 while ((token = peek_ident ()) != 0)
4554 const char *oper = get_ident ();
4555 id_base *idb = get_operator (oper, true);
4556 if (idb == NULL)
4557 fatal_at (token, "no such operator '%s'", oper);
4558 if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
4559 || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
4560 || *idb == VIEW_CONVERT2)
4561 fatal_at (token, "conditional operators cannot be used inside for");
4563 if (arity == -1)
4564 arity = idb->nargs;
4565 else if (idb->nargs == -1)
4567 else if (idb->nargs != arity)
4568 fatal_at (token, "operator '%s' with arity %d does not match "
4569 "others with arity %d", oper, idb->nargs, arity);
4571 user_id *p = dyn_cast<user_id *> (idb);
4572 if (p)
4574 if (p->is_oper_list)
4575 op->substitutes.safe_splice (p->substitutes);
4576 else
4577 fatal_at (token, "iterator cannot be used as operator-list");
4579 else
4580 op->substitutes.safe_push (idb);
4582 op->nargs = arity;
4583 token = expect (CPP_CLOSE_PAREN);
4585 unsigned nsubstitutes = op->substitutes.length ();
4586 if (nsubstitutes == 0)
4587 fatal_at (token, "A user-defined operator must have at least "
4588 "one substitution");
4589 if (max_n_opers == 0)
4591 min_n_opers = nsubstitutes;
4592 max_n_opers = nsubstitutes;
4594 else
4596 if (nsubstitutes % min_n_opers != 0
4597 && min_n_opers % nsubstitutes != 0)
4598 fatal_at (token, "All user-defined identifiers must have a "
4599 "multiple number of operator substitutions of the "
4600 "smallest number of substitutions");
4601 if (nsubstitutes < min_n_opers)
4602 min_n_opers = nsubstitutes;
4603 else if (nsubstitutes > max_n_opers)
4604 max_n_opers = nsubstitutes;
4608 unsigned n_ids = user_ids.length ();
4609 if (n_ids == 0)
4610 fatal_at (token, "for requires at least one user-defined identifier");
4612 token = peek ();
4613 if (token->type == CPP_CLOSE_PAREN)
4614 fatal_at (token, "no pattern defined in for");
4616 active_fors.safe_push (user_ids);
4617 while (1)
4619 token = peek ();
4620 if (token->type == CPP_CLOSE_PAREN)
4621 break;
4622 parse_pattern ();
4624 active_fors.pop ();
4626 /* Remove user-defined operators from the hash again. */
4627 for (unsigned i = 0; i < user_ids.length (); ++i)
4629 if (!user_ids[i]->used)
4630 warning_at (user_id_tokens[i],
4631 "operator %s defined but not used", user_ids[i]->id);
4632 operators->remove_elt (user_ids[i]);
4636 /* Parse an identifier associated with a list of operators.
4637 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4639 void
4640 parser::parse_operator_list (source_location)
4642 const cpp_token *token = peek ();
4643 const char *id = get_ident ();
4645 if (get_operator (id, true) != 0)
4646 fatal_at (token, "operator %s already defined", id);
4648 user_id *op = new user_id (id, true);
4649 int arity = -1;
4651 while ((token = peek_ident ()) != 0)
4653 token = peek ();
4654 const char *oper = get_ident ();
4655 id_base *idb = get_operator (oper, true);
4657 if (idb == 0)
4658 fatal_at (token, "no such operator '%s'", oper);
4660 if (arity == -1)
4661 arity = idb->nargs;
4662 else if (idb->nargs == -1)
4664 else if (arity != idb->nargs)
4665 fatal_at (token, "operator '%s' with arity %d does not match "
4666 "others with arity %d", oper, idb->nargs, arity);
4668 /* We allow composition of multiple operator lists. */
4669 if (user_id *p = dyn_cast<user_id *> (idb))
4670 op->substitutes.safe_splice (p->substitutes);
4671 else
4672 op->substitutes.safe_push (idb);
4675 // Check that there is no junk after id-list
4676 token = peek();
4677 if (token->type != CPP_CLOSE_PAREN)
4678 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4680 if (op->substitutes.length () == 0)
4681 fatal_at (token, "operator-list cannot be empty");
4683 op->nargs = arity;
4684 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4685 *slot = op;
4688 /* Parse an outer if expression.
4689 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4691 void
4692 parser::parse_if (source_location)
4694 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4696 const cpp_token *token = peek ();
4697 if (token->type == CPP_CLOSE_PAREN)
4698 fatal_at (token, "no pattern defined in if");
4700 active_ifs.safe_push (ifexpr);
4701 while (1)
4703 const cpp_token *token = peek ();
4704 if (token->type == CPP_CLOSE_PAREN)
4705 break;
4707 parse_pattern ();
4709 active_ifs.pop ();
4712 /* Parse a list of predefined predicate identifiers.
4713 preds = '(' 'define_predicates' <ident>... ')' */
4715 void
4716 parser::parse_predicates (source_location)
4720 const cpp_token *token = peek ();
4721 if (token->type != CPP_NAME)
4722 break;
4724 add_predicate (get_ident ());
4726 while (1);
4729 /* Parse outer control structures.
4730 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4732 void
4733 parser::parse_pattern ()
4735 /* All clauses start with '('. */
4736 eat_token (CPP_OPEN_PAREN);
4737 const cpp_token *token = peek ();
4738 const char *id = get_ident ();
4739 if (strcmp (id, "simplify") == 0)
4741 parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
4742 capture_ids = NULL;
4744 else if (strcmp (id, "match") == 0)
4746 bool with_args = false;
4747 source_location e_loc = peek ()->src_loc;
4748 if (peek ()->type == CPP_OPEN_PAREN)
4750 eat_token (CPP_OPEN_PAREN);
4751 with_args = true;
4753 const char *name = get_ident ();
4754 id_base *id = get_operator (name);
4755 predicate_id *p;
4756 if (!id)
4758 p = add_predicate (name);
4759 user_predicates.safe_push (p);
4761 else if ((p = dyn_cast <predicate_id *> (id)))
4763 else
4764 fatal_at (token, "cannot add a match to a non-predicate ID");
4765 /* Parse (match <id> <arg>... (match-expr)) here. */
4766 expr *e = NULL;
4767 if (with_args)
4769 capture_ids = new cid_map_t;
4770 e = new expr (p, e_loc);
4771 while (peek ()->type == CPP_ATSIGN)
4772 e->append_op (parse_capture (NULL, false));
4773 eat_token (CPP_CLOSE_PAREN);
4775 if (p->nargs != -1
4776 && ((e && e->ops.length () != (unsigned)p->nargs)
4777 || (!e && p->nargs != 0)))
4778 fatal_at (token, "non-matching number of match operands");
4779 p->nargs = e ? e->ops.length () : 0;
4780 parse_simplify (simplify::MATCH, p->matchers, p, e);
4781 capture_ids = NULL;
4783 else if (strcmp (id, "for") == 0)
4784 parse_for (token->src_loc);
4785 else if (strcmp (id, "if") == 0)
4786 parse_if (token->src_loc);
4787 else if (strcmp (id, "define_predicates") == 0)
4789 if (active_ifs.length () > 0
4790 || active_fors.length () > 0)
4791 fatal_at (token, "define_predicates inside if or for is not supported");
4792 parse_predicates (token->src_loc);
4794 else if (strcmp (id, "define_operator_list") == 0)
4796 if (active_ifs.length () > 0
4797 || active_fors.length () > 0)
4798 fatal_at (token, "operator-list inside if or for is not supported");
4799 parse_operator_list (token->src_loc);
4801 else
4802 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
4803 active_ifs.length () == 0 && active_fors.length () == 0
4804 ? "'define_predicates', " : "");
4806 eat_token (CPP_CLOSE_PAREN);
4809 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4810 recursively. */
4812 static void
4813 walk_captures (operand *op, vec<vec<capture *> > cpts)
4815 if (! op)
4816 return;
4818 if (capture *c = dyn_cast <capture *> (op))
4820 cpts[c->where].safe_push (c);
4821 walk_captures (c->what, cpts);
4823 else if (expr *e = dyn_cast <expr *> (op))
4824 for (unsigned i = 0; i < e->ops.length (); ++i)
4825 walk_captures (e->ops[i], cpts);
4828 /* Finish up OP which is a match operand. */
4830 void
4831 parser::finish_match_operand (operand *op)
4833 /* Look for matching captures, diagnose mis-uses of @@ and apply
4834 early lowering and distribution of value_match. */
4835 auto_vec<vec<capture *> > cpts;
4836 cpts.safe_grow_cleared (capture_ids->elements ());
4837 walk_captures (op, cpts);
4838 for (unsigned i = 0; i < cpts.length (); ++i)
4840 capture *value_match = NULL;
4841 for (unsigned j = 0; j < cpts[i].length (); ++j)
4843 if (cpts[i][j]->value_match)
4845 if (value_match)
4846 fatal_at (cpts[i][j]->location, "duplicate @@");
4847 value_match = cpts[i][j];
4850 if (cpts[i].length () == 1 && value_match)
4851 fatal_at (value_match->location, "@@ without a matching capture");
4852 if (value_match)
4854 /* Duplicate prevailing capture with the existing ID, create
4855 a fake ID and rewrite all captures to use it. This turns
4856 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4857 value_match->what = new capture (value_match->location,
4858 value_match->where,
4859 value_match->what, false);
4860 /* Create a fake ID and rewrite all captures to use it. */
4861 unsigned newid = get_internal_capture_id ();
4862 for (unsigned j = 0; j < cpts[i].length (); ++j)
4864 cpts[i][j]->where = newid;
4865 cpts[i][j]->value_match = true;
4868 cpts[i].release ();
4872 /* Main entry of the parser. Repeatedly parse outer control structures. */
4874 parser::parser (cpp_reader *r_)
4876 r = r_;
4877 active_ifs = vNULL;
4878 active_fors = vNULL;
4879 simplifiers = vNULL;
4880 oper_lists_set = NULL;
4881 oper_lists = vNULL;
4882 capture_ids = NULL;
4883 user_predicates = vNULL;
4884 parsing_match_operand = false;
4886 const cpp_token *token = next ();
4887 while (token->type != CPP_EOF)
4889 _cpp_backup_tokens (r, 1);
4890 parse_pattern ();
4891 token = next ();
4896 /* Helper for the linemap code. */
4898 static size_t
4899 round_alloc_size (size_t s)
4901 return s;
4905 /* The genmatch generator progam. It reads from a pattern description
4906 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4909 main (int argc, char **argv)
4911 cpp_reader *r;
4913 progname = "genmatch";
4915 if (argc < 2)
4916 return 1;
4918 bool gimple = true;
4919 char *input = argv[argc-1];
4920 for (int i = 1; i < argc - 1; ++i)
4922 if (strcmp (argv[i], "--gimple") == 0)
4923 gimple = true;
4924 else if (strcmp (argv[i], "--generic") == 0)
4925 gimple = false;
4926 else if (strcmp (argv[i], "-v") == 0)
4927 verbose = 1;
4928 else if (strcmp (argv[i], "-vv") == 0)
4929 verbose = 2;
4930 else
4932 fprintf (stderr, "Usage: genmatch "
4933 "[--gimple] [--generic] [-v[v]] input\n");
4934 return 1;
4938 line_table = XCNEW (struct line_maps);
4939 linemap_init (line_table, 0);
4940 line_table->reallocator = xrealloc;
4941 line_table->round_alloc_size = round_alloc_size;
4943 r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
4944 cpp_callbacks *cb = cpp_get_callbacks (r);
4945 cb->error = error_cb;
4947 /* Add the build directory to the #include "" search path. */
4948 cpp_dir *dir = XCNEW (cpp_dir);
4949 dir->name = getpwd ();
4950 if (!dir->name)
4951 dir->name = ASTRDUP (".");
4952 cpp_set_include_chains (r, dir, NULL, false);
4954 if (!cpp_read_main_file (r, input))
4955 return 1;
4956 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
4957 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
4959 null_id = new id_base (id_base::NULL_ID, "null");
4961 /* Pre-seed operators. */
4962 operators = new hash_table<id_base> (1024);
4963 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4964 add_operator (SYM, # SYM, # TYPE, NARGS);
4965 #define END_OF_BASE_TREE_CODES
4966 #include "tree.def"
4967 add_operator (CONVERT0, "convert0", "tcc_unary", 1);
4968 add_operator (CONVERT1, "convert1", "tcc_unary", 1);
4969 add_operator (CONVERT2, "convert2", "tcc_unary", 1);
4970 add_operator (VIEW_CONVERT0, "view_convert0", "tcc_unary", 1);
4971 add_operator (VIEW_CONVERT1, "view_convert1", "tcc_unary", 1);
4972 add_operator (VIEW_CONVERT2, "view_convert2", "tcc_unary", 1);
4973 #undef END_OF_BASE_TREE_CODES
4974 #undef DEFTREECODE
4976 /* Pre-seed builtin functions.
4977 ??? Cannot use N (name) as that is targetm.emultls.get_address
4978 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4979 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4980 add_function (ENUM, "CFN_" # ENUM);
4981 #include "builtins.def"
4983 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
4984 add_function (IFN_##CODE, "CFN_" #CODE);
4985 #include "internal-fn.def"
4987 /* Parse ahead! */
4988 parser p (r);
4990 if (gimple)
4991 write_header (stdout, "gimple-match-head.c");
4992 else
4993 write_header (stdout, "generic-match-head.c");
4995 /* Go over all predicates defined with patterns and perform
4996 lowering and code generation. */
4997 for (unsigned i = 0; i < p.user_predicates.length (); ++i)
4999 predicate_id *pred = p.user_predicates[i];
5000 lower (pred->matchers, gimple);
5002 if (verbose == 2)
5003 for (unsigned i = 0; i < pred->matchers.length (); ++i)
5004 print_matches (pred->matchers[i]);
5006 decision_tree dt;
5007 for (unsigned i = 0; i < pred->matchers.length (); ++i)
5008 dt.insert (pred->matchers[i], i);
5010 if (verbose == 2)
5011 dt.print (stderr);
5013 write_predicate (stdout, pred, dt, gimple);
5016 /* Lower the main simplifiers and generate code for them. */
5017 lower (p.simplifiers, gimple);
5019 if (verbose == 2)
5020 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5021 print_matches (p.simplifiers[i]);
5023 decision_tree dt;
5024 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5025 dt.insert (p.simplifiers[i], i);
5027 if (verbose == 2)
5028 dt.print (stderr);
5030 dt.gen (stdout, gimple);
5032 /* Finalize. */
5033 cpp_finish (r, NULL);
5034 cpp_destroy (r);
5036 delete operators;
5038 return 0;