1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2016 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
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
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/>. */
26 #include "coretypes.h"
29 #include "hash-table.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)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
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
61 This is the implementation for genmatch. */
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);
72 #if GCC_VERSION >= 4001
73 __attribute__((format (printf, 5, 0)))
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");
92 if (!fgets (buf, 128, f))
94 if (buf[strlen (buf) - 1] != '\n')
101 fprintf (stderr, "%s", buf);
102 for (int i = 0; i < loc.column - 1; ++i)
105 fputc ('\n', stderr);
110 if (errtype == CPP_DL_FATAL)
116 #if GCC_VERSION >= 4001
117 __attribute__((format (printf, 2, 3)))
119 fatal_at (const cpp_token *tk, const char *msg, ...)
121 rich_location richloc (line_table, tk->src_loc);
124 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
129 #if GCC_VERSION >= 4001
130 __attribute__((format (printf, 2, 3)))
132 fatal_at (source_location loc, const char *msg, ...)
134 rich_location richloc (line_table, loc);
137 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
142 #if GCC_VERSION >= 4001
143 __attribute__((format (printf, 2, 3)))
145 warning_at (const cpp_token *tk, const char *msg, ...)
147 rich_location richloc (line_table, tk->src_loc);
150 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
155 #if GCC_VERSION >= 4001
156 __attribute__((format (printf, 2, 3)))
158 warning_at (source_location loc, const char *msg, ...)
160 rich_location richloc (line_table, loc);
163 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
167 /* Like fprintf, but print INDENT spaces at the beginning. */
170 #if GCC_VERSION >= 4001
171 __attribute__((format (printf, 3, 4)))
173 fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
176 for (; indent >= 8; indent -= 8)
178 fprintf (f, "%*s", indent, "");
179 va_start (ap, format);
180 vfprintf (f, format, ap);
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);
193 /* When writing to a dumpfile only dump the filename. */
194 const char *file = strrchr (loc.file, DIR_SEPARATOR);
199 fprintf (f, "%s:%d", file, loc.line);
202 /* Other gen programs really output line directives here, at least for
203 development it's right now more convenient to have line information
204 from the generated file. Still keep the directives as comment for now
205 to easily back-point to the meta-description. */
206 fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
210 /* Pull in tree codes and builtin function codes from their
213 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
226 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
227 enum built_in_function {
228 #include "builtins.def"
232 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
234 #include "internal-fn.def"
238 /* Return true if CODE represents a commutative tree code. Otherwise
241 commutative_tree_code (enum tree_code code)
247 case MULT_HIGHPART_EXPR:
262 case WIDEN_MULT_EXPR:
263 case VEC_WIDEN_MULT_HI_EXPR:
264 case VEC_WIDEN_MULT_LO_EXPR:
265 case VEC_WIDEN_MULT_EVEN_EXPR:
266 case VEC_WIDEN_MULT_ODD_EXPR:
275 /* Return true if CODE represents a ternary tree code for which the
276 first two operands are commutative. Otherwise return false. */
278 commutative_ternary_tree_code (enum tree_code code)
282 case WIDEN_MULT_PLUS_EXPR:
283 case WIDEN_MULT_MINUS_EXPR:
294 /* Return true if CODE is a comparison. */
297 comparison_code_p (enum tree_code code)
324 /* Base class for all identifiers the parser knows. */
326 struct id_base : nofree_ptr_hash<id_base>
328 enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
330 id_base (id_kind, const char *, int = -1);
336 /* hash_table support. */
337 static inline hashval_t hash (const id_base *);
338 static inline int equal (const id_base *, const id_base *);
342 id_base::hash (const id_base *op)
348 id_base::equal (const id_base *op1,
351 return (op1->hashval == op2->hashval
352 && strcmp (op1->id, op2->id) == 0);
355 /* The special id "null", which matches nothing. */
356 static id_base *null_id;
358 /* Hashtable of known pattern operators. This is pre-seeded from
359 all known tree codes and all known builtin function ids. */
360 static hash_table<id_base> *operators;
362 id_base::id_base (id_kind kind_, const char *id_, int nargs_)
367 hashval = htab_hash_string (id);
370 /* Identifier that maps to a tree code. */
372 struct operator_id : public id_base
374 operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
376 : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
381 /* Identifier that maps to a builtin or internal function code. */
383 struct fn_id : public id_base
385 fn_id (enum built_in_function fn_, const char *id_)
386 : id_base (id_base::FN, id_), fn (fn_) {}
387 fn_id (enum internal_fn fn_, const char *id_)
388 : id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
394 /* Identifier that maps to a user-defined predicate. */
396 struct predicate_id : public id_base
398 predicate_id (const char *id_)
399 : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
400 vec<simplify *> matchers;
403 /* Identifier that maps to a operator defined by a 'for' directive. */
405 struct user_id : public id_base
407 user_id (const char *id_, bool is_oper_list_ = false)
408 : id_base (id_base::USER, id_), substitutes (vNULL),
409 used (false), is_oper_list (is_oper_list_) {}
410 vec<id_base *> substitutes;
418 is_a_helper <fn_id *>::test (id_base *id)
420 return id->kind == id_base::FN;
426 is_a_helper <operator_id *>::test (id_base *id)
428 return id->kind == id_base::CODE;
434 is_a_helper <predicate_id *>::test (id_base *id)
436 return id->kind == id_base::PREDICATE;
442 is_a_helper <user_id *>::test (id_base *id)
444 return id->kind == id_base::USER;
447 /* Add a predicate identifier to the hash. */
449 static predicate_id *
450 add_predicate (const char *id)
452 predicate_id *p = new predicate_id (id);
453 id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
455 fatal ("duplicate id definition");
460 /* Add a tree code identifier to the hash. */
463 add_operator (enum tree_code code, const char *id,
464 const char *tcc, unsigned nargs)
466 if (strcmp (tcc, "tcc_unary") != 0
467 && strcmp (tcc, "tcc_binary") != 0
468 && strcmp (tcc, "tcc_comparison") != 0
469 && strcmp (tcc, "tcc_expression") != 0
470 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
471 && strcmp (tcc, "tcc_reference") != 0
472 /* To have INTEGER_CST and friends as "predicate operators". */
473 && strcmp (tcc, "tcc_constant") != 0
474 /* And allow CONSTRUCTOR for vector initializers. */
475 && !(code == CONSTRUCTOR)
476 /* Allow SSA_NAME as predicate operator. */
477 && !(code == SSA_NAME))
479 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
480 if (code == ADDR_EXPR)
482 operator_id *op = new operator_id (code, id, nargs, tcc);
483 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
485 fatal ("duplicate id definition");
489 /* Add a built-in or internal function identifier to the hash. ID is
490 the name of its CFN_* enumeration value. */
492 template <typename T>
494 add_function (T code, const char *id)
496 fn_id *fn = new fn_id (code, id);
497 id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
499 fatal ("duplicate id definition");
503 /* Helper for easy comparing ID with tree code CODE. */
506 operator==(id_base &id, enum tree_code code)
508 if (operator_id *oid = dyn_cast <operator_id *> (&id))
509 return oid->code == code;
513 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
516 get_operator (const char *id, bool allow_null = false)
518 if (allow_null && strcmp (id, "null") == 0)
521 id_base tem (id_base::CODE, id);
523 id_base *op = operators->find_with_hash (&tem, tem.hashval);
526 /* If this is a user-defined identifier track whether it was used. */
527 if (user_id *uid = dyn_cast<user_id *> (op))
533 bool all_upper = true;
534 bool all_lower = true;
535 for (unsigned int i = 0; id[i]; ++i)
538 else if (ISLOWER (id[i]))
542 /* Try in caps with _EXPR appended. */
543 id2 = ACONCAT ((id, "_EXPR", NULL));
544 for (unsigned int i = 0; id2[i]; ++i)
545 id2[i] = TOUPPER (id2[i]);
547 else if (all_upper && strncmp (id, "IFN_", 4) == 0)
548 /* Try CFN_ instead of IFN_. */
549 id2 = ACONCAT (("CFN_", id + 4, NULL));
550 else if (all_upper && strncmp (id, "BUILT_IN_", 9) == 0)
551 /* Try prepending CFN_. */
552 id2 = ACONCAT (("CFN_", id, NULL));
556 new (&tem) id_base (id_base::CODE, id2);
557 return operators->find_with_hash (&tem, tem.hashval);
560 /* Return the comparison operators that results if the operands are
561 swapped. This is safe for floating-point. */
564 swap_tree_comparison (operator_id *p)
576 return get_operator ("LT_EXPR");
578 return get_operator ("LE_EXPR");
580 return get_operator ("GT_EXPR");
582 return get_operator ("GE_EXPR");
584 return get_operator ("UNLT_EXPR");
586 return get_operator ("UNLE_EXPR");
588 return get_operator ("UNGT_EXPR");
590 return get_operator ("UNGE_EXPR");
596 typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
599 /* The AST produced by parsing of the pattern definitions. */
604 /* The base class for operands. */
607 enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
608 operand (enum op_type type_, source_location loc_)
609 : type (type_), location (loc_) {}
611 source_location location;
612 virtual void gen_transform (FILE *, int, const char *, bool, int,
613 const char *, capture_info *,
616 { gcc_unreachable (); }
619 /* A predicate operand. Predicates are leafs in the AST. */
621 struct predicate : public operand
623 predicate (predicate_id *p_, source_location loc)
624 : operand (OP_PREDICATE, loc), p (p_) {}
628 /* An operand that constitutes an expression. Expressions include
629 function calls and user-defined predicate invocations. */
631 struct expr : public operand
633 expr (id_base *operation_, source_location loc, bool is_commutative_ = false)
634 : operand (OP_EXPR, loc), operation (operation_),
635 ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
636 is_generic (false), force_single_use (false) {}
638 : operand (OP_EXPR, e->location), operation (e->operation),
639 ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
640 is_generic (e->is_generic), force_single_use (e->force_single_use) {}
641 void append_op (operand *op) { ops.safe_push (op); }
642 /* The operator and its operands. */
645 /* An explicitely specified type - used exclusively for conversions. */
646 const char *expr_type;
647 /* Whether the operation is to be applied commutatively. This is
648 later lowered to two separate patterns. */
650 /* Whether the expression is expected to be in GENERIC form. */
652 /* Whether pushing any stmt to the sequence should be conditional
653 on this expression having a single-use. */
654 bool force_single_use;
655 virtual void gen_transform (FILE *f, int, const char *, bool, int,
656 const char *, capture_info *,
657 dt_operand ** = 0, int = 0);
660 /* An operator that is represented by native C code. This is always
661 a leaf operand in the AST. This class is also used to represent
662 the code to be generated for 'if' and 'with' expressions. */
664 struct c_expr : public operand
666 /* A mapping of an identifier and its replacement. Used to apply
671 id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
674 c_expr (cpp_reader *r_, source_location loc,
675 vec<cpp_token> code_, unsigned nr_stmts_,
676 vec<id_tab> ids_, cid_map_t *capture_ids_)
677 : operand (OP_C_EXPR, loc), r (r_), code (code_),
678 capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
679 /* cpplib tokens and state to transform this back to source. */
682 cid_map_t *capture_ids;
683 /* The number of statements parsed (well, the number of ';'s). */
685 /* The identifier replacement vector. */
687 virtual void gen_transform (FILE *f, int, const char *, bool, int,
688 const char *, capture_info *,
689 dt_operand ** = 0, int = 0);
692 /* A wrapper around another operand that captures its value. */
694 struct capture : public operand
696 capture (source_location loc, unsigned where_, operand *what_)
697 : operand (OP_CAPTURE, loc), where (where_), what (what_) {}
698 /* Identifier index for the value. */
700 /* The captured value. */
702 virtual void gen_transform (FILE *f, int, const char *, bool, int,
703 const char *, capture_info *,
704 dt_operand ** = 0, int = 0);
709 struct if_expr : public operand
711 if_expr (source_location loc)
712 : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
718 /* with expression. */
720 struct with_expr : public operand
722 with_expr (source_location loc)
723 : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
731 is_a_helper <capture *>::test (operand *op)
733 return op->type == operand::OP_CAPTURE;
739 is_a_helper <predicate *>::test (operand *op)
741 return op->type == operand::OP_PREDICATE;
747 is_a_helper <c_expr *>::test (operand *op)
749 return op->type == operand::OP_C_EXPR;
755 is_a_helper <expr *>::test (operand *op)
757 return op->type == operand::OP_EXPR;
763 is_a_helper <if_expr *>::test (operand *op)
765 return op->type == operand::OP_IF;
771 is_a_helper <with_expr *>::test (operand *op)
773 return op->type == operand::OP_WITH;
776 /* The main class of a pattern and its transform. This is used to
777 represent both (simplify ...) and (match ...) kinds. The AST
778 duplicates all outer 'if' and 'for' expressions here so each
779 simplify can exist in isolation. */
783 enum simplify_kind { SIMPLIFY, MATCH };
785 simplify (simplify_kind kind_, operand *match_, operand *result_,
786 vec<vec<user_id *> > for_vec_, cid_map_t *capture_ids_)
787 : kind (kind_), match (match_), result (result_),
788 for_vec (for_vec_), for_subst_vec (vNULL),
789 capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
792 /* The expression that is matched against the GENERIC or GIMPLE IL. */
794 /* For a (simplify ...) an expression with ifs and withs with the expression
795 produced when the pattern applies in the leafs.
796 For a (match ...) the leafs are either empty if it is a simple predicate
797 or the single expression specifying the matched operands. */
798 struct operand *result;
799 /* Collected 'for' expression operators that have to be replaced
800 in the lowering phase. */
801 vec<vec<user_id *> > for_vec;
802 vec<std::pair<user_id *, id_base *> > for_subst_vec;
803 /* A map of capture identifiers to indexes. */
804 cid_map_t *capture_ids;
808 /* Debugging routines for dumping the AST. */
811 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
813 if (capture *c = dyn_cast<capture *> (o))
815 if (c->what && flattened == false)
816 print_operand (c->what, f, flattened);
817 fprintf (f, "@%u", c->where);
820 else if (predicate *p = dyn_cast<predicate *> (o))
821 fprintf (f, "%s", p->p->id);
823 else if (is_a<c_expr *> (o))
824 fprintf (f, "c_expr");
826 else if (expr *e = dyn_cast<expr *> (o))
828 if (e->ops.length () == 0)
829 fprintf (f, "%s", e->operation->id);
832 fprintf (f, "(%s", e->operation->id);
834 if (flattened == false)
836 for (unsigned i = 0; i < e->ops.length (); ++i)
839 print_operand (e->ops[i], f, flattened);
851 print_matches (struct simplify *s, FILE *f = stderr)
853 fprintf (f, "for expression: ");
854 print_operand (s->match, f);
861 /* Lowering of commutative operators. */
864 cartesian_product (const vec< vec<operand *> >& ops_vector,
865 vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
867 if (n == ops_vector.length ())
869 vec<operand *> xv = v.copy ();
870 result.safe_push (xv);
874 for (unsigned i = 0; i < ops_vector[n].length (); ++i)
876 v[n] = ops_vector[n][i];
877 cartesian_product (ops_vector, result, v, n + 1);
881 /* Lower OP to two operands in case it is marked as commutative. */
883 static vec<operand *>
884 commutate (operand *op, vec<vec<user_id *> > &for_vec)
886 vec<operand *> ret = vNULL;
888 if (capture *c = dyn_cast <capture *> (op))
895 vec<operand *> v = commutate (c->what, for_vec);
896 for (unsigned i = 0; i < v.length (); ++i)
898 capture *nc = new capture (c->location, c->where, v[i]);
904 expr *e = dyn_cast <expr *> (op);
905 if (!e || e->ops.length () == 0)
911 vec< vec<operand *> > ops_vector = vNULL;
912 for (unsigned i = 0; i < e->ops.length (); ++i)
913 ops_vector.safe_push (commutate (e->ops[i], for_vec));
915 auto_vec< vec<operand *> > result;
916 auto_vec<operand *> v (e->ops.length ());
917 v.quick_grow_cleared (e->ops.length ());
918 cartesian_product (ops_vector, result, v, 0);
921 for (unsigned i = 0; i < result.length (); ++i)
923 expr *ne = new expr (e);
924 ne->is_commutative = false;
925 for (unsigned j = 0; j < result[i].length (); ++j)
926 ne->append_op (result[i][j]);
930 if (!e->is_commutative)
933 for (unsigned i = 0; i < result.length (); ++i)
935 expr *ne = new expr (e);
936 if (operator_id *p = dyn_cast <operator_id *> (ne->operation))
938 if (comparison_code_p (p->code))
939 ne->operation = swap_tree_comparison (p);
941 else if (user_id *p = dyn_cast <user_id *> (ne->operation))
943 bool found_compare = false;
944 for (unsigned j = 0; j < p->substitutes.length (); ++j)
945 if (operator_id *q = dyn_cast <operator_id *> (p->substitutes[j]))
947 if (comparison_code_p (q->code)
948 && swap_tree_comparison (q) != q)
950 found_compare = true;
956 user_id *newop = new user_id ("<internal>");
957 for (unsigned j = 0; j < p->substitutes.length (); ++j)
959 id_base *subst = p->substitutes[j];
960 if (operator_id *q = dyn_cast <operator_id *> (subst))
962 if (comparison_code_p (q->code))
963 subst = swap_tree_comparison (q);
965 newop->substitutes.safe_push (subst);
967 ne->operation = newop;
968 /* Search for 'p' inside the for vector and push 'newop'
969 to the same level. */
970 for (unsigned j = 0; newop && j < for_vec.length (); ++j)
971 for (unsigned k = 0; k < for_vec[j].length (); ++k)
972 if (for_vec[j][k] == p)
974 for_vec[j].safe_push (newop);
980 ne->is_commutative = false;
981 // result[i].length () is 2 since e->operation is binary
982 for (unsigned j = result[i].length (); j; --j)
983 ne->append_op (result[i][j-1]);
990 /* Lower operations marked as commutative in the AST of S and push
991 the resulting patterns to SIMPLIFIERS. */
994 lower_commutative (simplify *s, vec<simplify *>& simplifiers)
996 vec<operand *> matchers = commutate (s->match, s->for_vec);
997 for (unsigned i = 0; i < matchers.length (); ++i)
999 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1000 s->for_vec, s->capture_ids);
1001 simplifiers.safe_push (ns);
1005 /* Strip conditional conversios using operator OPER from O and its
1006 children if STRIP, else replace them with an unconditional convert. */
1009 lower_opt_convert (operand *o, enum tree_code oper,
1010 enum tree_code to_oper, bool strip)
1012 if (capture *c = dyn_cast<capture *> (o))
1015 return new capture (c->location, c->where,
1016 lower_opt_convert (c->what, oper, to_oper, strip));
1021 expr *e = dyn_cast<expr *> (o);
1025 if (*e->operation == oper)
1028 return lower_opt_convert (e->ops[0], oper, to_oper, strip);
1030 expr *ne = new expr (e);
1031 ne->operation = (to_oper == CONVERT_EXPR
1032 ? get_operator ("CONVERT_EXPR")
1033 : get_operator ("VIEW_CONVERT_EXPR"));
1034 ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
1038 expr *ne = new expr (e);
1039 for (unsigned i = 0; i < e->ops.length (); ++i)
1040 ne->append_op (lower_opt_convert (e->ops[i], oper, to_oper, strip));
1045 /* Determine whether O or its children uses the conditional conversion
1049 has_opt_convert (operand *o, enum tree_code oper)
1051 if (capture *c = dyn_cast<capture *> (o))
1054 return has_opt_convert (c->what, oper);
1059 expr *e = dyn_cast<expr *> (o);
1063 if (*e->operation == oper)
1066 for (unsigned i = 0; i < e->ops.length (); ++i)
1067 if (has_opt_convert (e->ops[i], oper))
1073 /* Lower conditional convert operators in O, expanding it to a vector
1076 static vec<operand *>
1077 lower_opt_convert (operand *o)
1079 vec<operand *> v1 = vNULL, v2;
1083 enum tree_code opers[]
1084 = { CONVERT0, CONVERT_EXPR,
1085 CONVERT1, CONVERT_EXPR,
1086 CONVERT2, CONVERT_EXPR,
1087 VIEW_CONVERT0, VIEW_CONVERT_EXPR,
1088 VIEW_CONVERT1, VIEW_CONVERT_EXPR,
1089 VIEW_CONVERT2, VIEW_CONVERT_EXPR };
1091 /* Conditional converts are lowered to a pattern with the
1092 conversion and one without. The three different conditional
1093 convert codes are lowered separately. */
1095 for (unsigned i = 0; i < sizeof (opers) / sizeof (enum tree_code); i += 2)
1098 for (unsigned j = 0; j < v1.length (); ++j)
1099 if (has_opt_convert (v1[j], opers[i]))
1101 v2.safe_push (lower_opt_convert (v1[j],
1102 opers[i], opers[i+1], false));
1103 v2.safe_push (lower_opt_convert (v1[j],
1104 opers[i], opers[i+1], true));
1110 for (unsigned j = 0; j < v2.length (); ++j)
1111 v1.safe_push (v2[j]);
1118 /* Lower conditional convert operators in the AST of S and push
1119 the resulting multiple patterns to SIMPLIFIERS. */
1122 lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
1124 vec<operand *> matchers = lower_opt_convert (s->match);
1125 for (unsigned i = 0; i < matchers.length (); ++i)
1127 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1128 s->for_vec, s->capture_ids);
1129 simplifiers.safe_push (ns);
1133 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1134 GENERIC and a GIMPLE variant. */
1136 static vec<operand *>
1137 lower_cond (operand *o)
1139 vec<operand *> ro = vNULL;
1141 if (capture *c = dyn_cast<capture *> (o))
1145 vec<operand *> lop = vNULL;
1146 lop = lower_cond (c->what);
1148 for (unsigned i = 0; i < lop.length (); ++i)
1149 ro.safe_push (new capture (c->location, c->where, lop[i]));
1154 expr *e = dyn_cast<expr *> (o);
1155 if (!e || e->ops.length () == 0)
1161 vec< vec<operand *> > ops_vector = vNULL;
1162 for (unsigned i = 0; i < e->ops.length (); ++i)
1163 ops_vector.safe_push (lower_cond (e->ops[i]));
1165 auto_vec< vec<operand *> > result;
1166 auto_vec<operand *> v (e->ops.length ());
1167 v.quick_grow_cleared (e->ops.length ());
1168 cartesian_product (ops_vector, result, v, 0);
1170 for (unsigned i = 0; i < result.length (); ++i)
1172 expr *ne = new expr (e);
1173 for (unsigned j = 0; j < result[i].length (); ++j)
1174 ne->append_op (result[i][j]);
1176 /* If this is a COND with a captured expression or an
1177 expression with two operands then also match a GENERIC
1178 form on the compare. */
1179 if ((*e->operation == COND_EXPR
1180 || *e->operation == VEC_COND_EXPR)
1181 && ((is_a <capture *> (e->ops[0])
1182 && as_a <capture *> (e->ops[0])->what
1183 && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1185 (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1186 || (is_a <expr *> (e->ops[0])
1187 && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1189 expr *ne = new expr (e);
1190 for (unsigned j = 0; j < result[i].length (); ++j)
1191 ne->append_op (result[i][j]);
1192 if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1194 expr *ocmp = as_a <expr *> (c->what);
1195 expr *cmp = new expr (ocmp);
1196 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1197 cmp->append_op (ocmp->ops[j]);
1198 cmp->is_generic = true;
1199 ne->ops[0] = new capture (c->location, c->where, cmp);
1203 expr *ocmp = as_a <expr *> (ne->ops[0]);
1204 expr *cmp = new expr (ocmp);
1205 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1206 cmp->append_op (ocmp->ops[j]);
1207 cmp->is_generic = true;
1217 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1218 GENERIC and a GIMPLE variant. */
1221 lower_cond (simplify *s, vec<simplify *>& simplifiers)
1223 vec<operand *> matchers = lower_cond (s->match);
1224 for (unsigned i = 0; i < matchers.length (); ++i)
1226 simplify *ns = new simplify (s->kind, matchers[i], s->result,
1227 s->for_vec, s->capture_ids);
1228 simplifiers.safe_push (ns);
1232 /* Return true if O refers to ID. */
1235 contains_id (operand *o, user_id *id)
1237 if (capture *c = dyn_cast<capture *> (o))
1238 return c->what && contains_id (c->what, id);
1240 if (expr *e = dyn_cast<expr *> (o))
1242 if (e->operation == id)
1244 for (unsigned i = 0; i < e->ops.length (); ++i)
1245 if (contains_id (e->ops[i], id))
1250 if (with_expr *w = dyn_cast <with_expr *> (o))
1251 return (contains_id (w->with, id)
1252 || contains_id (w->subexpr, id));
1254 if (if_expr *ife = dyn_cast <if_expr *> (o))
1255 return (contains_id (ife->cond, id)
1256 || contains_id (ife->trueexpr, id)
1257 || (ife->falseexpr && contains_id (ife->falseexpr, id)));
1259 if (c_expr *ce = dyn_cast<c_expr *> (o))
1260 return ce->capture_ids && ce->capture_ids->get (id->id);
1266 /* In AST operand O replace operator ID with operator WITH. */
1269 replace_id (operand *o, user_id *id, id_base *with)
1271 /* Deep-copy captures and expressions, replacing operations as
1273 if (capture *c = dyn_cast<capture *> (o))
1277 return new capture (c->location, c->where,
1278 replace_id (c->what, id, with));
1280 else if (expr *e = dyn_cast<expr *> (o))
1282 expr *ne = new expr (e);
1283 if (e->operation == id)
1284 ne->operation = with;
1285 for (unsigned i = 0; i < e->ops.length (); ++i)
1286 ne->append_op (replace_id (e->ops[i], id, with));
1289 else if (with_expr *w = dyn_cast <with_expr *> (o))
1291 with_expr *nw = new with_expr (w->location);
1292 nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1293 nw->subexpr = replace_id (w->subexpr, id, with);
1296 else if (if_expr *ife = dyn_cast <if_expr *> (o))
1298 if_expr *nife = new if_expr (ife->location);
1299 nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1300 nife->trueexpr = replace_id (ife->trueexpr, id, with);
1302 nife->falseexpr = replace_id (ife->falseexpr, id, with);
1306 /* For c_expr we simply record a string replacement table which is
1307 applied at code-generation time. */
1308 if (c_expr *ce = dyn_cast<c_expr *> (o))
1310 vec<c_expr::id_tab> ids = ce->ids.copy ();
1311 ids.safe_push (c_expr::id_tab (id->id, with->id));
1312 return new c_expr (ce->r, ce->location,
1313 ce->code, ce->nr_stmts, ids, ce->capture_ids);
1319 /* Return true if the binary operator OP is ok for delayed substitution
1320 during for lowering. */
1323 binary_ok (operator_id *op)
1330 case TRUNC_DIV_EXPR:
1332 case FLOOR_DIV_EXPR:
1333 case ROUND_DIV_EXPR:
1334 case TRUNC_MOD_EXPR:
1336 case FLOOR_MOD_EXPR:
1337 case ROUND_MOD_EXPR:
1339 case EXACT_DIV_EXPR:
1351 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1354 lower_for (simplify *sin, vec<simplify *>& simplifiers)
1356 vec<vec<user_id *> >& for_vec = sin->for_vec;
1357 unsigned worklist_start = 0;
1358 auto_vec<simplify *> worklist;
1359 worklist.safe_push (sin);
1361 /* Lower each recorded for separately, operating on the
1362 set of simplifiers created by the previous one.
1363 Lower inner-to-outer so inner for substitutes can refer
1364 to operators replaced by outer fors. */
1365 for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1367 vec<user_id *>& ids = for_vec[fi];
1368 unsigned n_ids = ids.length ();
1369 unsigned max_n_opers = 0;
1370 bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
1371 for (unsigned i = 0; i < n_ids; ++i)
1373 if (ids[i]->substitutes.length () > max_n_opers)
1374 max_n_opers = ids[i]->substitutes.length ();
1375 /* Require that all substitutes are of the same kind so that
1376 if we delay substitution to the result op code generation
1377 can look at the first substitute for deciding things like
1378 types of operands. */
1379 enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1380 for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1381 if (ids[i]->substitutes[j]->kind != kind)
1382 can_delay_subst = false;
1383 else if (operator_id *op
1384 = dyn_cast <operator_id *> (ids[i]->substitutes[j]))
1387 = as_a <operator_id *> (ids[i]->substitutes[0]);
1388 if (strcmp (op->tcc, "tcc_comparison") == 0
1389 && strcmp (op0->tcc, "tcc_comparison") == 0)
1391 /* Unfortunately we can't just allow all tcc_binary. */
1392 else if (strcmp (op->tcc, "tcc_binary") == 0
1393 && strcmp (op0->tcc, "tcc_binary") == 0
1397 else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
1398 || strcmp (op->id + 1, "ROTATE_EXPR") == 0)
1399 && (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
1400 || strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
1403 can_delay_subst = false;
1405 else if (is_a <fn_id *> (ids[i]->substitutes[j]))
1408 can_delay_subst = false;
1411 unsigned worklist_end = worklist.length ();
1412 for (unsigned si = worklist_start; si < worklist_end; ++si)
1414 simplify *s = worklist[si];
1415 for (unsigned j = 0; j < max_n_opers; ++j)
1417 operand *match_op = s->match;
1418 operand *result_op = s->result;
1419 vec<std::pair<user_id *, id_base *> > subst;
1420 subst.create (n_ids);
1422 for (unsigned i = 0; i < n_ids; ++i)
1424 user_id *id = ids[i];
1425 id_base *oper = id->substitutes[j % id->substitutes.length ()];
1427 && (contains_id (match_op, id)
1428 || contains_id (result_op, id)))
1433 subst.quick_push (std::make_pair (id, oper));
1434 match_op = replace_id (match_op, id, oper);
1436 && !can_delay_subst)
1437 result_op = replace_id (result_op, id, oper);
1444 simplify *ns = new simplify (s->kind, match_op, result_op,
1445 vNULL, s->capture_ids);
1446 ns->for_subst_vec.safe_splice (s->for_subst_vec);
1449 ns->for_subst_vec.safe_splice (subst);
1452 worklist.safe_push (ns);
1455 worklist_start = worklist_end;
1458 /* Copy out the result from the last for lowering. */
1459 for (unsigned i = worklist_start; i < worklist.length (); ++i)
1460 simplifiers.safe_push (worklist[i]);
1463 /* Lower the AST for everything in SIMPLIFIERS. */
1466 lower (vec<simplify *>& simplifiers, bool gimple)
1468 auto_vec<simplify *> out_simplifiers;
1469 for (unsigned i = 0; i < simplifiers.length (); ++i)
1470 lower_opt_convert (simplifiers[i], out_simplifiers);
1472 simplifiers.truncate (0);
1473 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1474 lower_commutative (out_simplifiers[i], simplifiers);
1476 out_simplifiers.truncate (0);
1478 for (unsigned i = 0; i < simplifiers.length (); ++i)
1479 lower_cond (simplifiers[i], out_simplifiers);
1481 out_simplifiers.safe_splice (simplifiers);
1484 simplifiers.truncate (0);
1485 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1486 lower_for (out_simplifiers[i], simplifiers);
1492 /* The decision tree built for generating GIMPLE and GENERIC pattern
1493 matching code. It represents the 'match' expression of all
1494 simplifies and has those as its leafs. */
1498 /* A hash-map collecting semantically equivalent leafs in the decision
1499 tree for splitting out to separate functions. */
1508 struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1511 static inline hashval_t hash (const key_type &);
1512 static inline bool equal_keys (const key_type &, const key_type &);
1513 template <typename T> static inline void remove (T &) {}
1516 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1520 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1524 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1528 vec<dt_node *> kids;
1532 unsigned total_size;
1535 dt_node (enum dt_type type_): type (type_), level (0), kids (vNULL) {}
1537 dt_node *append_node (dt_node *);
1538 dt_node *append_op (operand *, dt_node *parent = 0, unsigned pos = 0);
1539 dt_node *append_true_op (dt_node *parent = 0, unsigned pos = 0);
1540 dt_node *append_match_op (dt_operand *, dt_node *parent = 0, unsigned pos = 0);
1541 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1543 virtual void gen (FILE *, int, bool) {}
1545 void gen_kids (FILE *, int, bool);
1546 void gen_kids_1 (FILE *, int, bool,
1547 vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1548 vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1550 void analyze (sinfo_map_t &);
1553 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1555 struct dt_operand : public dt_node
1558 dt_operand *match_dop;
1562 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1563 dt_operand *parent_ = 0, unsigned pos_ = 0)
1564 : dt_node (type), op (op_), match_dop (match_dop_),
1565 parent (parent_), pos (pos_) {}
1567 void gen (FILE *, int, bool);
1568 unsigned gen_predicate (FILE *, int, const char *, bool);
1569 unsigned gen_match_op (FILE *, int, const char *);
1571 unsigned gen_gimple_expr (FILE *, int);
1572 unsigned gen_generic_expr (FILE *, int, const char *);
1574 char *get_name (char *);
1575 void gen_opname (char *, unsigned);
1578 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1580 struct dt_simplify : public dt_node
1583 unsigned pattern_no;
1584 dt_operand **indexes;
1587 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1588 : dt_node (DT_SIMPLIFY), s (s_), pattern_no (pattern_no_),
1589 indexes (indexes_), info (NULL) {}
1591 void gen_1 (FILE *, int, bool, operand *);
1592 void gen (FILE *f, int, bool);
1598 is_a_helper <dt_operand *>::test (dt_node *n)
1600 return (n->type == dt_node::DT_OPERAND
1601 || n->type == dt_node::DT_MATCH);
1607 is_a_helper <dt_simplify *>::test (dt_node *n)
1609 return n->type == dt_node::DT_SIMPLIFY;
1614 /* A container for the actual decision tree. */
1616 struct decision_tree
1620 void insert (struct simplify *, unsigned);
1621 void gen (FILE *f, bool gimple);
1622 void print (FILE *f = stderr);
1624 decision_tree () { root = new dt_node (dt_node::DT_NODE); }
1626 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1627 unsigned pos = 0, dt_node *parent = 0);
1628 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1629 static bool cmp_node (dt_node *, dt_node *);
1630 static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1633 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1636 cmp_operand (operand *o1, operand *o2)
1638 if (!o1 || !o2 || o1->type != o2->type)
1641 if (o1->type == operand::OP_PREDICATE)
1643 predicate *p1 = as_a<predicate *>(o1);
1644 predicate *p2 = as_a<predicate *>(o2);
1645 return p1->p == p2->p;
1647 else if (o1->type == operand::OP_EXPR)
1649 expr *e1 = static_cast<expr *>(o1);
1650 expr *e2 = static_cast<expr *>(o2);
1651 return (e1->operation == e2->operation
1652 && e1->is_generic == e2->is_generic);
1658 /* Compare two decision tree nodes N1 and N2 and return true if they
1662 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1664 if (!n1 || !n2 || n1->type != n2->type)
1670 if (n1->type == dt_node::DT_TRUE)
1673 if (n1->type == dt_node::DT_OPERAND)
1674 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1675 (as_a<dt_operand *> (n2))->op);
1676 else if (n1->type == dt_node::DT_MATCH)
1677 return ((as_a<dt_operand *> (n1))->match_dop
1678 == (as_a<dt_operand *> (n2))->match_dop);
1682 /* Search OPS for a decision tree node like P and return it if found. */
1685 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1687 /* We can merge adjacent DT_TRUE. */
1688 if (p->type == dt_node::DT_TRUE
1690 && ops.last ()->type == dt_node::DT_TRUE)
1692 for (int i = ops.length () - 1; i >= 0; --i)
1694 /* But we can't merge across DT_TRUE nodes as they serve as
1695 pattern order barriers to make sure that patterns apply
1696 in order of appearance in case multiple matches are possible. */
1697 if (ops[i]->type == dt_node::DT_TRUE)
1699 if (decision_tree::cmp_node (ops[i], p))
1705 /* Append N to the decision tree if it there is not already an existing
1709 dt_node::append_node (dt_node *n)
1713 kid = decision_tree::find_node (kids, n);
1718 n->level = this->level + 1;
1723 /* Append OP to the decision tree. */
1726 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1728 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1729 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1730 return append_node (n);
1733 /* Append a DT_TRUE decision tree node. */
1736 dt_node::append_true_op (dt_node *parent, unsigned pos)
1738 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1739 dt_operand *n = new dt_operand (DT_TRUE, 0, 0, parent_, pos);
1740 return append_node (n);
1743 /* Append a DT_MATCH decision tree node. */
1746 dt_node::append_match_op (dt_operand *match_dop, dt_node *parent, unsigned pos)
1748 dt_operand *parent_ = as_a<dt_operand *> (parent);
1749 dt_operand *n = new dt_operand (DT_MATCH, 0, match_dop, parent_, pos);
1750 return append_node (n);
1753 /* Append S to the decision tree. */
1756 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1757 dt_operand **indexes)
1759 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1760 for (unsigned i = 0; i < kids.length (); ++i)
1761 if (dt_simplify *s2 = dyn_cast <dt_simplify *> (kids[i]))
1763 warning_at (s->match->location, "duplicate pattern");
1764 warning_at (s2->s->match->location, "previous pattern defined here");
1765 print_operand (s->match, stderr);
1766 fprintf (stderr, "\n");
1768 return append_node (n);
1771 /* Analyze the node and its children. */
1774 dt_node::analyze (sinfo_map_t &map)
1780 if (type == DT_SIMPLIFY)
1782 /* Populate the map of equivalent simplifies. */
1783 dt_simplify *s = as_a <dt_simplify *> (this);
1785 sinfo *&si = map.get_or_insert (s, &existed);
1800 for (unsigned i = 0; i < kids.length (); ++i)
1802 kids[i]->analyze (map);
1803 num_leafs += kids[i]->num_leafs;
1804 total_size += kids[i]->total_size;
1805 max_level = MAX (max_level, kids[i]->max_level);
1809 /* Insert O into the decision tree and return the decision tree node found
1813 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1814 unsigned pos, dt_node *parent)
1816 dt_node *q, *elm = 0;
1818 if (capture *c = dyn_cast<capture *> (o))
1820 unsigned capt_index = c->where;
1822 if (indexes[capt_index] == 0)
1825 q = insert_operand (p, c->what, indexes, pos, parent);
1828 q = elm = p->append_true_op (parent, pos);
1831 // get to the last capture
1832 for (operand *what = c->what;
1833 what && is_a<capture *> (what);
1834 c = as_a<capture *> (what), what = c->what)
1839 unsigned cc_index = c->where;
1840 dt_operand *match_op = indexes[cc_index];
1842 dt_operand temp (dt_node::DT_TRUE, 0, 0);
1843 elm = decision_tree::find_node (p->kids, &temp);
1847 dt_operand temp (dt_node::DT_MATCH, 0, match_op);
1848 elm = decision_tree::find_node (p->kids, &temp);
1853 dt_operand temp (dt_node::DT_OPERAND, c->what, 0);
1854 elm = decision_tree::find_node (p->kids, &temp);
1858 gcc_assert (elm->type == dt_node::DT_TRUE
1859 || elm->type == dt_node::DT_OPERAND
1860 || elm->type == dt_node::DT_MATCH);
1861 indexes[capt_index] = static_cast<dt_operand *> (elm);
1866 p = p->append_match_op (indexes[capt_index], parent, pos);
1868 return insert_operand (p, c->what, indexes, 0, p);
1873 p = p->append_op (o, parent, pos);
1876 if (expr *e = dyn_cast <expr *>(o))
1878 for (unsigned i = 0; i < e->ops.length (); ++i)
1879 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1885 /* Insert S into the decision tree. */
1888 decision_tree::insert (struct simplify *s, unsigned pattern_no)
1890 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1891 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1892 p->append_simplify (s, pattern_no, indexes);
1895 /* Debug functions to dump the decision tree. */
1898 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1900 if (p->type == dt_node::DT_NODE)
1901 fprintf (f, "root");
1905 for (unsigned i = 0; i < indent; i++)
1908 if (p->type == dt_node::DT_OPERAND)
1910 dt_operand *dop = static_cast<dt_operand *>(p);
1911 print_operand (dop->op, f, true);
1913 else if (p->type == dt_node::DT_TRUE)
1914 fprintf (f, "true");
1915 else if (p->type == dt_node::DT_MATCH)
1916 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1917 else if (p->type == dt_node::DT_SIMPLIFY)
1919 dt_simplify *s = static_cast<dt_simplify *> (p);
1920 fprintf (f, "simplify_%u { ", s->pattern_no);
1921 for (int i = 0; i <= s->s->capture_max; ++i)
1922 fprintf (f, "%p, ", (void *) s->indexes[i]);
1927 fprintf (stderr, " (%p), %u, %u\n", (void *) p, p->level, p->kids.length ());
1929 for (unsigned i = 0; i < p->kids.length (); ++i)
1930 decision_tree::print_node (p->kids[i], f, indent + 2);
1934 decision_tree::print (FILE *f)
1936 return decision_tree::print_node (root, f);
1940 /* For GENERIC we have to take care of wrapping multiple-used
1941 expressions with side-effects in save_expr and preserve side-effects
1942 of expressions with omit_one_operand. Analyze captures in
1943 match, result and with expressions and perform early-outs
1944 on the outermost match expression operands for cases we cannot
1949 capture_info (simplify *s, operand *, bool);
1950 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
1951 bool walk_result (operand *o, bool, operand *);
1952 void walk_c_expr (c_expr *);
1958 bool force_no_side_effects_p;
1959 bool force_single_use;
1960 bool cond_expr_cond_p;
1961 unsigned long toplevel_msk;
1962 unsigned match_use_count;
1963 unsigned result_use_count;
1968 auto_vec<cinfo> info;
1969 unsigned long force_no_side_effects;
1973 /* Analyze captures in S. */
1975 capture_info::capture_info (simplify *s, operand *result, bool gimple_)
1980 if (s->kind == simplify::MATCH)
1982 force_no_side_effects = -1;
1986 force_no_side_effects = 0;
1987 info.safe_grow_cleared (s->capture_max + 1);
1988 for (int i = 0; i <= s->capture_max; ++i)
1989 info[i].same_as = i;
1991 e = as_a <expr *> (s->match);
1992 for (unsigned i = 0; i < e->ops.length (); ++i)
1993 walk_match (e->ops[i], i,
1994 (i != 0 && *e->operation == COND_EXPR)
1995 || *e->operation == TRUTH_ANDIF_EXPR
1996 || *e->operation == TRUTH_ORIF_EXPR,
1998 && (*e->operation == COND_EXPR
1999 || *e->operation == VEC_COND_EXPR));
2001 walk_result (s->result, false, result);
2004 /* Analyze captures in the match expression piece O. */
2007 capture_info::walk_match (operand *o, unsigned toplevel_arg,
2008 bool conditional_p, bool cond_expr_cond_p)
2010 if (capture *c = dyn_cast <capture *> (o))
2012 unsigned where = c->where;
2013 info[where].match_use_count++;
2014 info[where].toplevel_msk |= 1 << toplevel_arg;
2015 info[where].force_no_side_effects_p |= conditional_p;
2016 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2021 /* Recurse to exprs and captures. */
2022 if (is_a <capture *> (c->what)
2023 || is_a <expr *> (c->what))
2024 walk_match (c->what, toplevel_arg, conditional_p, false);
2025 /* We need to look past multiple captures to find a captured
2026 expression as with conditional converts two captures
2027 can be collapsed onto the same expression. Also collect
2028 what captures capture the same thing. */
2029 while (c->what && is_a <capture *> (c->what))
2031 c = as_a <capture *> (c->what);
2032 if (info[c->where].same_as != c->where
2033 && info[c->where].same_as != info[where].same_as)
2034 fatal_at (c->location, "cannot handle this collapsed capture");
2035 info[c->where].same_as = info[where].same_as;
2037 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2040 && (e = dyn_cast <expr *> (c->what)))
2042 info[where].expr_p = true;
2043 info[where].force_single_use |= e->force_single_use;
2046 else if (expr *e = dyn_cast <expr *> (o))
2048 for (unsigned i = 0; i < e->ops.length (); ++i)
2050 bool cond_p = conditional_p;
2051 bool cond_expr_cond_p = false;
2052 if (i != 0 && *e->operation == COND_EXPR)
2054 else if (*e->operation == TRUTH_ANDIF_EXPR
2055 || *e->operation == TRUTH_ORIF_EXPR)
2058 && (*e->operation == COND_EXPR
2059 || *e->operation == VEC_COND_EXPR))
2060 cond_expr_cond_p = true;
2061 walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
2064 else if (is_a <predicate *> (o))
2066 /* Mark non-captured leafs toplevel arg for checking. */
2067 force_no_side_effects |= 1 << toplevel_arg;
2070 warning_at (o->location,
2071 "forcing no side-effects on possibly lost leaf");
2077 /* Analyze captures in the result expression piece O. Return true
2078 if RESULT was visited in one of the children. Only visit
2079 non-if/with children if they are rooted on RESULT. */
2082 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2084 if (capture *c = dyn_cast <capture *> (o))
2086 unsigned where = info[c->where].same_as;
2087 info[where].result_use_count++;
2088 /* If we substitute an expression capture we don't know
2089 which captures this will end up using (well, we don't
2090 compute that). Force the uses to be side-effect free
2091 which means forcing the toplevels that reach the
2092 expression side-effect free. */
2093 if (info[where].expr_p)
2094 force_no_side_effects |= info[where].toplevel_msk;
2095 /* Mark CSE capture uses as forced to have no side-effects. */
2097 && is_a <expr *> (c->what))
2099 info[where].cse_p = true;
2100 walk_result (c->what, true, result);
2103 else if (expr *e = dyn_cast <expr *> (o))
2105 id_base *opr = e->operation;
2106 if (user_id *uid = dyn_cast <user_id *> (opr))
2107 opr = uid->substitutes[0];
2108 for (unsigned i = 0; i < e->ops.length (); ++i)
2110 bool cond_p = conditional_p;
2111 if (i != 0 && *e->operation == COND_EXPR)
2113 else if (*e->operation == TRUTH_ANDIF_EXPR
2114 || *e->operation == TRUTH_ORIF_EXPR)
2116 walk_result (e->ops[i], cond_p, result);
2119 else if (if_expr *e = dyn_cast <if_expr *> (o))
2121 /* 'if' conditions should be all fine. */
2122 if (e->trueexpr == result)
2124 walk_result (e->trueexpr, false, result);
2127 if (e->falseexpr == result)
2129 walk_result (e->falseexpr, false, result);
2133 if (is_a <if_expr *> (e->trueexpr)
2134 || is_a <with_expr *> (e->trueexpr))
2135 res |= walk_result (e->trueexpr, false, result);
2137 && (is_a <if_expr *> (e->falseexpr)
2138 || is_a <with_expr *> (e->falseexpr)))
2139 res |= walk_result (e->falseexpr, false, result);
2142 else if (with_expr *e = dyn_cast <with_expr *> (o))
2144 bool res = (e->subexpr == result);
2146 || is_a <if_expr *> (e->subexpr)
2147 || is_a <with_expr *> (e->subexpr))
2148 res |= walk_result (e->subexpr, false, result);
2150 walk_c_expr (e->with);
2153 else if (c_expr *e = dyn_cast <c_expr *> (o))
2161 /* Look for captures in the C expr E. */
2164 capture_info::walk_c_expr (c_expr *e)
2166 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2167 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2168 really escape through. */
2169 unsigned p_depth = 0;
2170 for (unsigned i = 0; i < e->code.length (); ++i)
2172 const cpp_token *t = &e->code[i];
2173 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2175 if (t->type == CPP_NAME
2176 && (strcmp ((const char *)CPP_HASHNODE
2177 (t->val.node.node)->ident.str, "TREE_TYPE") == 0
2178 || strcmp ((const char *)CPP_HASHNODE
2179 (t->val.node.node)->ident.str, "TREE_CODE") == 0
2180 || strcmp ((const char *)CPP_HASHNODE
2181 (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
2182 || ((id = get_operator ((const char *)CPP_HASHNODE
2183 (t->val.node.node)->ident.str))
2184 && is_a <predicate_id *> (id)))
2185 && n->type == CPP_OPEN_PAREN)
2187 else if (t->type == CPP_CLOSE_PAREN
2190 else if (p_depth == 0
2191 && t->type == CPP_ATSIGN
2192 && (n->type == CPP_NUMBER
2193 || n->type == CPP_NAME)
2194 && !(n->flags & PREV_WHITE))
2197 if (n->type == CPP_NUMBER)
2198 id = (const char *)n->val.str.text;
2200 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2201 unsigned where = *e->capture_ids->get(id);
2202 info[info[where].same_as].force_no_side_effects_p = true;
2205 warning_at (t, "capture escapes");
2211 /* Code generation off the decision tree and the refered AST nodes. */
2214 is_conversion (id_base *op)
2216 return (*op == CONVERT_EXPR
2218 || *op == FLOAT_EXPR
2219 || *op == FIX_TRUNC_EXPR
2220 || *op == VIEW_CONVERT_EXPR);
2223 /* Get the type to be used for generating operands of OP from the
2227 get_operand_type (id_base *op, const char *in_type,
2228 const char *expr_type,
2229 const char *other_oprnd_type)
2231 /* Generally operands whose type does not match the type of the
2232 expression generated need to know their types but match and
2233 thus can fall back to 'other_oprnd_type'. */
2234 if (is_conversion (op))
2235 return other_oprnd_type;
2236 else if (*op == REALPART_EXPR
2237 || *op == IMAGPART_EXPR)
2238 return other_oprnd_type;
2239 else if (is_a <operator_id *> (op)
2240 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2241 return other_oprnd_type;
2244 /* Otherwise all types should match - choose one in order of
2251 return other_oprnd_type;
2255 /* Generate transform code for an expression. */
2258 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2259 int depth, const char *in_type, capture_info *cinfo,
2260 dt_operand **indexes, int)
2262 id_base *opr = operation;
2263 /* When we delay operator substituting during lowering of fors we
2264 make sure that for code-gen purposes the effects of each substitute
2265 are the same. Thus just look at that. */
2266 if (user_id *uid = dyn_cast <user_id *> (opr))
2267 opr = uid->substitutes[0];
2269 bool conversion_p = is_conversion (opr);
2270 const char *type = expr_type;
2273 /* If there was a type specification in the pattern use it. */
2275 else if (conversion_p)
2276 /* For conversions we need to build the expression using the
2277 outer type passed in. */
2279 else if (*opr == REALPART_EXPR
2280 || *opr == IMAGPART_EXPR)
2282 /* __real and __imag use the component type of its operand. */
2283 sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
2286 else if (is_a <operator_id *> (opr)
2287 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2289 /* comparisons use boolean_type_node (or what gets in), but
2290 their operands need to figure out the types themselves. */
2291 sprintf (optype, "boolean_type_node");
2294 else if (*opr == COND_EXPR
2295 || *opr == VEC_COND_EXPR)
2297 /* Conditions are of the same type as their first alternative. */
2298 sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
2303 /* Other operations are of the same type as their first operand. */
2304 sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
2308 fatal_at (location, "cannot determine type of operand");
2310 fprintf_indent (f, indent, "{\n");
2312 fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
2314 snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
2315 for (unsigned i = 0; i < ops.length (); ++i)
2318 snprintf (dest, 32, "ops%d[%u]", depth, i);
2320 = get_operand_type (opr, in_type, expr_type,
2321 i == 0 ? NULL : op0type);
2322 ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
2325 || *opr == VEC_COND_EXPR) && i == 0 ? 1 : 2);
2328 const char *opr_name;
2329 if (*operation == CONVERT_EXPR)
2330 opr_name = "NOP_EXPR";
2332 opr_name = operation->id;
2336 if (*opr == CONVERT_EXPR)
2338 fprintf_indent (f, indent,
2339 "if (%s != TREE_TYPE (ops%d[0])\n",
2341 fprintf_indent (f, indent,
2342 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2344 fprintf_indent (f, indent + 2, "{\n");
2347 /* ??? Building a stmt can fail for various reasons here, seq being
2348 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2349 So if we fail here we should continue matching other patterns. */
2350 fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr_name);
2351 fprintf_indent (f, indent, "tree tem_ops[3] = { ");
2352 for (unsigned i = 0; i < ops.length (); ++i)
2353 fprintf (f, "ops%d[%u]%s", depth, i,
2354 i == ops.length () - 1 ? " };\n" : ", ");
2355 fprintf_indent (f, indent,
2356 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2357 ops.length (), type);
2358 fprintf_indent (f, indent,
2359 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2361 fprintf_indent (f, indent,
2362 "if (!res) return false;\n");
2363 if (*opr == CONVERT_EXPR)
2366 fprintf_indent (f, indent, " }\n");
2367 fprintf_indent (f, indent, "else\n");
2368 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2373 if (*opr == CONVERT_EXPR)
2375 fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2379 if (opr->kind == id_base::CODE)
2380 fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
2381 ops.length(), opr_name, type);
2384 fprintf_indent (f, indent, "{\n");
2385 fprintf_indent (f, indent, " res = maybe_build_call_expr_loc (loc, "
2386 "%s, %s, %d", opr_name, type, ops.length());
2388 for (unsigned i = 0; i < ops.length (); ++i)
2389 fprintf (f, ", ops%d[%u]", depth, i);
2390 fprintf (f, ");\n");
2391 if (opr->kind != id_base::CODE)
2393 fprintf_indent (f, indent, " if (!res)\n");
2394 fprintf_indent (f, indent, " return NULL_TREE;\n");
2395 fprintf_indent (f, indent, "}\n");
2397 if (*opr == CONVERT_EXPR)
2400 fprintf_indent (f, indent, "else\n");
2401 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2404 fprintf_indent (f, indent, "%s = res;\n", dest);
2406 fprintf_indent (f, indent, "}\n");
2409 /* Generate code for a c_expr which is either the expression inside
2410 an if statement or a sequence of statements which computes a
2411 result to be stored to DEST. */
2414 c_expr::gen_transform (FILE *f, int indent, const char *dest,
2415 bool, int, const char *, capture_info *,
2418 if (dest && nr_stmts == 1)
2419 fprintf_indent (f, indent, "%s = ", dest);
2421 unsigned stmt_nr = 1;
2422 for (unsigned i = 0; i < code.length (); ++i)
2424 const cpp_token *token = &code[i];
2426 /* Replace captures for code-gen. */
2427 if (token->type == CPP_ATSIGN)
2429 const cpp_token *n = &code[i+1];
2430 if ((n->type == CPP_NUMBER
2431 || n->type == CPP_NAME)
2432 && !(n->flags & PREV_WHITE))
2434 if (token->flags & PREV_WHITE)
2437 if (n->type == CPP_NUMBER)
2438 id = (const char *)n->val.str.text;
2440 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2441 unsigned *cid = capture_ids->get (id);
2443 fatal_at (token, "unknown capture id");
2444 fprintf (f, "captures[%u]", *cid);
2450 if (token->flags & PREV_WHITE)
2453 if (token->type == CPP_NAME)
2455 const char *id = (const char *) NODE_NAME (token->val.node.node);
2457 for (j = 0; j < ids.length (); ++j)
2459 if (strcmp (id, ids[j].id) == 0)
2461 fprintf (f, "%s", ids[j].oper);
2465 if (j < ids.length ())
2469 /* Output the token as string. */
2470 char *tk = (char *)cpp_token_as_text (r, token);
2473 if (token->type == CPP_SEMICOLON)
2477 if (dest && stmt_nr == nr_stmts)
2478 fprintf_indent (f, indent, "%s = ", dest);
2483 /* Generate transform code for a capture. */
2486 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2487 int depth, const char *in_type, capture_info *cinfo,
2488 dt_operand **indexes, int cond_handling)
2490 if (what && is_a<expr *> (what))
2492 if (indexes[where] == 0)
2495 sprintf (buf, "captures[%u]", where);
2496 what->gen_transform (f, indent, buf, gimple, depth, in_type,
2501 fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2503 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2504 with substituting a capture of that. */
2506 && cond_handling != 0
2507 && cinfo->info[where].cond_expr_cond_p)
2509 /* If substituting into a cond_expr condition, unshare. */
2510 if (cond_handling == 1)
2511 fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
2512 /* If substituting elsewhere we might need to decompose it. */
2513 else if (cond_handling == 2)
2515 /* ??? Returning false here will also not allow any other patterns
2516 to match unless this generator was split out. */
2517 fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2518 fprintf_indent (f, indent, " {\n");
2519 fprintf_indent (f, indent, " if (!seq) return false;\n");
2520 fprintf_indent (f, indent, " %s = gimple_build (seq,"
2522 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2523 " TREE_OPERAND (%s, 1));\n",
2524 dest, dest, dest, dest, dest);
2525 fprintf_indent (f, indent, " }\n");
2530 /* Return the name of the operand representing the decision tree node.
2531 Use NAME as space to generate it. */
2534 dt_operand::get_name (char *name)
2537 sprintf (name, "t");
2538 else if (parent->level == 1)
2539 sprintf (name, "op%u", pos);
2540 else if (parent->type == dt_node::DT_MATCH)
2541 return parent->get_name (name);
2543 sprintf (name, "o%u%u", parent->level, pos);
2547 /* Fill NAME with the operand name at position POS. */
2550 dt_operand::gen_opname (char *name, unsigned pos)
2553 sprintf (name, "op%u", pos);
2555 sprintf (name, "o%u%u", level, pos);
2558 /* Generate matching code for the decision tree operand which is
2562 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2564 predicate *p = as_a <predicate *> (op);
2566 if (p->p->matchers.exists ())
2568 /* If this is a predicate generated from a pattern mangle its
2569 name and pass on the valueize hook. */
2571 fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2574 fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2577 fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2578 fprintf_indent (f, indent + 2, "{\n");
2582 /* Generate matching code for the decision tree operand which is
2586 dt_operand::gen_match_op (FILE *f, int indent, const char *opname)
2588 char match_opname[20];
2589 match_dop->get_name (match_opname);
2590 fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2591 opname, match_opname, opname, match_opname);
2592 fprintf_indent (f, indent + 2, "{\n");
2596 /* Generate GIMPLE matching code for the decision tree operand. */
2599 dt_operand::gen_gimple_expr (FILE *f, int indent)
2601 expr *e = static_cast<expr *> (op);
2602 id_base *id = e->operation;
2603 unsigned n_ops = e->ops.length ();
2605 for (unsigned i = 0; i < n_ops; ++i)
2607 char child_opname[20];
2608 gen_opname (child_opname, i);
2610 if (id->kind == id_base::CODE)
2613 || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2614 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2616 /* ??? If this is a memory operation we can't (and should not)
2617 match this. The only sensible operand types are
2618 SSA names and invariants. */
2619 fprintf_indent (f, indent,
2620 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def), %i);\n",
2622 fprintf_indent (f, indent,
2623 "if ((TREE_CODE (%s) == SSA_NAME\n",
2625 fprintf_indent (f, indent,
2626 " || is_gimple_min_invariant (%s))\n",
2628 fprintf_indent (f, indent,
2629 " && (%s = do_valueize (valueize, %s)))\n",
2630 child_opname, child_opname);
2631 fprintf_indent (f, indent,
2637 fprintf_indent (f, indent,
2638 "tree %s = gimple_assign_rhs%u (def);\n",
2639 child_opname, i + 1);
2642 fprintf_indent (f, indent,
2643 "tree %s = gimple_call_arg (def, %u);\n",
2645 fprintf_indent (f, indent,
2646 "if ((%s = do_valueize (valueize, %s)))\n",
2647 child_opname, child_opname);
2648 fprintf_indent (f, indent, " {\n");
2651 /* While the toplevel operands are canonicalized by the caller
2652 after valueizing operands of sub-expressions we have to
2653 re-canonicalize operand order. */
2654 if (operator_id *code = dyn_cast <operator_id *> (id))
2656 /* ??? We can't canonicalize tcc_comparison operands here
2657 because that requires changing the comparison code which
2658 we already matched... */
2659 if (commutative_tree_code (code->code)
2660 || commutative_ternary_tree_code (code->code))
2662 char child_opname0[20], child_opname1[20];
2663 gen_opname (child_opname0, 0);
2664 gen_opname (child_opname1, 1);
2665 fprintf_indent (f, indent,
2666 "if (tree_swap_operands_p (%s, %s, false))\n",
2667 child_opname0, child_opname1);
2668 fprintf_indent (f, indent,
2669 " std::swap (%s, %s);\n",
2670 child_opname0, child_opname1);
2677 /* Generate GENERIC matching code for the decision tree operand. */
2680 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2682 expr *e = static_cast<expr *> (op);
2683 unsigned n_ops = e->ops.length ();
2685 for (unsigned i = 0; i < n_ops; ++i)
2687 char child_opname[20];
2688 gen_opname (child_opname, i);
2690 if (e->operation->kind == id_base::CODE)
2691 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2692 child_opname, opname, i);
2694 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2695 child_opname, opname, i);
2701 /* Generate matching code for the children of the decision tree node. */
2704 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2706 auto_vec<dt_operand *> gimple_exprs;
2707 auto_vec<dt_operand *> generic_exprs;
2708 auto_vec<dt_operand *> fns;
2709 auto_vec<dt_operand *> generic_fns;
2710 auto_vec<dt_operand *> preds;
2711 auto_vec<dt_node *> others;
2713 for (unsigned i = 0; i < kids.length (); ++i)
2715 if (kids[i]->type == dt_node::DT_OPERAND)
2717 dt_operand *op = as_a<dt_operand *> (kids[i]);
2718 if (expr *e = dyn_cast <expr *> (op->op))
2720 if (e->ops.length () == 0
2721 && (!gimple || !(*e->operation == CONSTRUCTOR)))
2722 generic_exprs.safe_push (op);
2723 else if (e->operation->kind == id_base::FN)
2728 generic_fns.safe_push (op);
2730 else if (e->operation->kind == id_base::PREDICATE)
2731 preds.safe_push (op);
2734 if (gimple && !e->is_generic)
2735 gimple_exprs.safe_push (op);
2737 generic_exprs.safe_push (op);
2740 else if (op->op->type == operand::OP_PREDICATE)
2741 others.safe_push (kids[i]);
2745 else if (kids[i]->type == dt_node::DT_SIMPLIFY)
2746 others.safe_push (kids[i]);
2747 else if (kids[i]->type == dt_node::DT_MATCH
2748 || kids[i]->type == dt_node::DT_TRUE)
2750 /* A DT_TRUE operand serves as a barrier - generate code now
2751 for what we have collected sofar.
2752 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2753 dependent matches to get out-of-order. Generate code now
2754 for what we have collected sofar. */
2755 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2756 fns, generic_fns, preds, others);
2757 /* And output the true operand itself. */
2758 kids[i]->gen (f, indent, gimple);
2759 gimple_exprs.truncate (0);
2760 generic_exprs.truncate (0);
2762 generic_fns.truncate (0);
2764 others.truncate (0);
2770 /* Generate code for the remains. */
2771 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2772 fns, generic_fns, preds, others);
2775 /* Generate matching code for the children of the decision tree node. */
2778 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2779 vec<dt_operand *> gimple_exprs,
2780 vec<dt_operand *> generic_exprs,
2781 vec<dt_operand *> fns,
2782 vec<dt_operand *> generic_fns,
2783 vec<dt_operand *> preds,
2784 vec<dt_node *> others)
2787 char *kid_opname = buf;
2789 unsigned exprs_len = gimple_exprs.length ();
2790 unsigned gexprs_len = generic_exprs.length ();
2791 unsigned fns_len = fns.length ();
2792 unsigned gfns_len = generic_fns.length ();
2794 if (exprs_len || fns_len || gexprs_len || gfns_len)
2797 gimple_exprs[0]->get_name (kid_opname);
2799 fns[0]->get_name (kid_opname);
2801 generic_fns[0]->get_name (kid_opname);
2803 generic_exprs[0]->get_name (kid_opname);
2805 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2806 fprintf_indent (f, indent, " {\n");
2810 if (exprs_len || fns_len)
2812 fprintf_indent (f, indent,
2813 "case SSA_NAME:\n");
2814 fprintf_indent (f, indent,
2815 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2817 fprintf_indent (f, indent,
2819 fprintf_indent (f, indent,
2820 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2826 fprintf_indent (f, indent,
2827 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2828 fprintf_indent (f, indent,
2829 " switch (gimple_assign_rhs_code (def))\n");
2831 fprintf_indent (f, indent, "{\n");
2832 for (unsigned i = 0; i < exprs_len; ++i)
2834 expr *e = as_a <expr *> (gimple_exprs[i]->op);
2835 id_base *op = e->operation;
2836 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2837 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2839 fprintf_indent (f, indent, "case %s:\n", op->id);
2840 fprintf_indent (f, indent, " {\n");
2841 gimple_exprs[i]->gen (f, indent + 4, true);
2842 fprintf_indent (f, indent, " break;\n");
2843 fprintf_indent (f, indent, " }\n");
2845 fprintf_indent (f, indent, "default:;\n");
2846 fprintf_indent (f, indent, "}\n");
2852 fprintf_indent (f, indent,
2853 "%sif (gcall *def = dyn_cast <gcall *>"
2855 exprs_len ? "else " : "");
2856 fprintf_indent (f, indent,
2857 " switch (gimple_call_combined_fn (def))\n");
2860 fprintf_indent (f, indent, "{\n");
2861 for (unsigned i = 0; i < fns_len; ++i)
2863 expr *e = as_a <expr *>(fns[i]->op);
2864 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2865 fprintf_indent (f, indent, " {\n");
2866 fns[i]->gen (f, indent + 4, true);
2867 fprintf_indent (f, indent, " break;\n");
2868 fprintf_indent (f, indent, " }\n");
2871 fprintf_indent (f, indent, "default:;\n");
2872 fprintf_indent (f, indent, "}\n");
2877 fprintf_indent (f, indent, " }\n");
2878 fprintf_indent (f, indent, " break;\n");
2881 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2883 expr *e = as_a <expr *>(generic_exprs[i]->op);
2884 id_base *op = e->operation;
2885 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2886 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2888 fprintf_indent (f, indent, "case %s:\n", op->id);
2889 fprintf_indent (f, indent, " {\n");
2890 generic_exprs[i]->gen (f, indent + 4, gimple);
2891 fprintf_indent (f, indent, " break;\n");
2892 fprintf_indent (f, indent, " }\n");
2897 fprintf_indent (f, indent,
2898 "case CALL_EXPR:\n");
2899 fprintf_indent (f, indent,
2900 " switch (get_call_combined_fn (%s))\n",
2902 fprintf_indent (f, indent,
2906 for (unsigned j = 0; j < generic_fns.length (); ++j)
2908 expr *e = as_a <expr *>(generic_fns[j]->op);
2909 gcc_assert (e->operation->kind == id_base::FN);
2911 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2912 fprintf_indent (f, indent, " {\n");
2913 generic_fns[j]->gen (f, indent + 4, false);
2914 fprintf_indent (f, indent, " break;\n");
2915 fprintf_indent (f, indent, " }\n");
2917 fprintf_indent (f, indent, "default:;\n");
2920 fprintf_indent (f, indent, " }\n");
2921 fprintf_indent (f, indent, " break;\n");
2924 /* Close switch (TREE_CODE ()). */
2925 if (exprs_len || fns_len || gexprs_len || gfns_len)
2928 fprintf_indent (f, indent, " default:;\n");
2929 fprintf_indent (f, indent, " }\n");
2932 for (unsigned i = 0; i < preds.length (); ++i)
2934 expr *e = as_a <expr *> (preds[i]->op);
2935 predicate_id *p = as_a <predicate_id *> (e->operation);
2936 preds[i]->get_name (kid_opname);
2937 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
2938 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
2939 gimple ? "gimple" : "tree",
2940 p->id, kid_opname, kid_opname,
2941 gimple ? ", valueize" : "");
2942 fprintf_indent (f, indent, " {\n");
2943 for (int j = 0; j < p->nargs; ++j)
2945 char child_opname[20];
2946 preds[i]->gen_opname (child_opname, j);
2947 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
2948 child_opname, kid_opname, j);
2950 preds[i]->gen_kids (f, indent + 4, gimple);
2954 for (unsigned i = 0; i < others.length (); ++i)
2955 others[i]->gen (f, indent, gimple);
2958 /* Generate matching code for the decision tree operand. */
2961 dt_operand::gen (FILE *f, int indent, bool gimple)
2966 unsigned n_braces = 0;
2968 if (type == DT_OPERAND)
2971 case operand::OP_PREDICATE:
2972 n_braces = gen_predicate (f, indent, opname, gimple);
2975 case operand::OP_EXPR:
2977 n_braces = gen_gimple_expr (f, indent);
2979 n_braces = gen_generic_expr (f, indent, opname);
2985 else if (type == DT_TRUE)
2987 else if (type == DT_MATCH)
2988 n_braces = gen_match_op (f, indent, opname);
2992 indent += 4 * n_braces;
2993 gen_kids (f, indent, gimple);
2995 for (unsigned i = 0; i < n_braces; ++i)
3000 fprintf_indent (f, indent, " }\n");
3005 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3006 step of a '(simplify ...)' or '(match ...)'. This handles everything
3007 that is not part of the decision tree (simplify->match).
3008 Main recursive worker. */
3011 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3015 if (with_expr *w = dyn_cast <with_expr *> (result))
3017 fprintf_indent (f, indent, "{\n");
3019 output_line_directive (f, w->location);
3020 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3021 gen_1 (f, indent, gimple, w->subexpr);
3023 fprintf_indent (f, indent, "}\n");
3026 else if (if_expr *ife = dyn_cast <if_expr *> (result))
3028 output_line_directive (f, ife->location);
3029 fprintf_indent (f, indent, "if (");
3030 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3032 fprintf_indent (f, indent + 2, "{\n");
3034 gen_1 (f, indent, gimple, ife->trueexpr);
3036 fprintf_indent (f, indent + 2, "}\n");
3039 fprintf_indent (f, indent, "else\n");
3040 fprintf_indent (f, indent + 2, "{\n");
3042 gen_1 (f, indent, gimple, ife->falseexpr);
3044 fprintf_indent (f, indent + 2, "}\n");
3050 /* Analyze captures and perform early-outs on the incoming arguments
3051 that cover cases we cannot handle. */
3052 capture_info cinfo (s, result, gimple);
3053 if (s->kind == simplify::SIMPLIFY)
3057 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3058 if (cinfo.force_no_side_effects & (1 << i))
3060 fprintf_indent (f, indent,
3061 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3064 warning_at (as_a <expr *> (s->match)->ops[i]->location,
3065 "forcing toplevel operand to have no "
3068 for (int i = 0; i <= s->capture_max; ++i)
3069 if (cinfo.info[i].cse_p)
3071 else if (cinfo.info[i].force_no_side_effects_p
3072 && (cinfo.info[i].toplevel_msk
3073 & cinfo.force_no_side_effects) == 0)
3075 fprintf_indent (f, indent,
3076 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3077 "return NULL_TREE;\n", i);
3079 warning_at (cinfo.info[i].c->location,
3080 "forcing captured operand to have no "
3083 else if ((cinfo.info[i].toplevel_msk
3084 & cinfo.force_no_side_effects) != 0)
3085 /* Mark capture as having no side-effects if we had to verify
3086 that via forced toplevel operand checks. */
3087 cinfo.info[i].force_no_side_effects_p = true;
3091 /* Force single-use restriction by only allowing simple
3092 results via setting seq to NULL. */
3093 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
3094 bool first_p = true;
3095 for (int i = 0; i <= s->capture_max; ++i)
3096 if (cinfo.info[i].force_single_use)
3100 fprintf_indent (f, indent, "if (lseq\n");
3101 fprintf_indent (f, indent, " && (");
3107 fprintf_indent (f, indent, " || ");
3109 fprintf (f, "!single_use (captures[%d])", i);
3113 fprintf (f, "))\n");
3114 fprintf_indent (f, indent, " lseq = NULL;\n");
3119 fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_DETAILS)) "
3120 "fprintf (dump_file, \"Applying pattern ");
3121 output_line_directive (f,
3122 result ? result->location : s->match->location, true);
3123 fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3127 /* If there is no result then this is a predicate implementation. */
3128 fprintf_indent (f, indent, "return true;\n");
3132 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3133 in outermost position). */
3134 if (result->type == operand::OP_EXPR
3135 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
3136 result = as_a <expr *> (result)->ops[0];
3137 if (result->type == operand::OP_EXPR)
3139 expr *e = as_a <expr *> (result);
3140 id_base *opr = e->operation;
3141 bool is_predicate = false;
3142 /* When we delay operator substituting during lowering of fors we
3143 make sure that for code-gen purposes the effects of each substitute
3144 are the same. Thus just look at that. */
3145 if (user_id *uid = dyn_cast <user_id *> (opr))
3146 opr = uid->substitutes[0];
3147 else if (is_a <predicate_id *> (opr))
3148 is_predicate = true;
3150 fprintf_indent (f, indent, "*res_code = %s;\n",
3151 *e->operation == CONVERT_EXPR
3152 ? "NOP_EXPR" : e->operation->id);
3153 for (unsigned j = 0; j < e->ops.length (); ++j)
3156 snprintf (dest, 32, "res_ops[%d]", j);
3158 = get_operand_type (opr,
3159 "type", e->expr_type,
3160 j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
3161 /* We need to expand GENERIC conditions we captured from
3162 COND_EXPRs and we need to unshare them when substituting
3164 int cond_handling = 0;
3166 cond_handling = ((*opr == COND_EXPR
3167 || *opr == VEC_COND_EXPR) && j == 0) ? 1 : 2;
3168 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3169 &cinfo, indexes, cond_handling);
3172 /* Re-fold the toplevel result. It's basically an embedded
3173 gimple_build w/o actually building the stmt. */
3175 fprintf_indent (f, indent,
3176 "gimple_resimplify%d (lseq, res_code, type, "
3177 "res_ops, valueize);\n", e->ops.length ());
3179 else if (result->type == operand::OP_CAPTURE
3180 || result->type == operand::OP_C_EXPR)
3182 result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
3184 fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
3185 if (is_a <capture *> (result)
3186 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3188 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3189 with substituting a capture of that. */
3190 fprintf_indent (f, indent,
3191 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3192 fprintf_indent (f, indent,
3194 fprintf_indent (f, indent,
3195 " tree tem = res_ops[0];\n");
3196 fprintf_indent (f, indent,
3197 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3198 fprintf_indent (f, indent,
3199 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3200 fprintf_indent (f, indent,
3206 fprintf_indent (f, indent, "return true;\n");
3210 bool is_predicate = false;
3211 if (result->type == operand::OP_EXPR)
3213 expr *e = as_a <expr *> (result);
3214 id_base *opr = e->operation;
3215 /* When we delay operator substituting during lowering of fors we
3216 make sure that for code-gen purposes the effects of each substitute
3217 are the same. Thus just look at that. */
3218 if (user_id *uid = dyn_cast <user_id *> (opr))
3219 opr = uid->substitutes[0];
3220 else if (is_a <predicate_id *> (opr))
3221 is_predicate = true;
3222 /* Search for captures used multiple times in the result expression
3223 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3224 original expression. */
3226 for (int i = 0; i < s->capture_max + 1; ++i)
3228 if (cinfo.info[i].same_as != (unsigned)i
3229 || cinfo.info[i].cse_p)
3231 if (cinfo.info[i].result_use_count
3232 > cinfo.info[i].match_use_count)
3233 fprintf_indent (f, indent,
3234 "if (! tree_invariant_p (captures[%d])) "
3235 "return NULL_TREE;\n", i);
3237 for (unsigned j = 0; j < e->ops.length (); ++j)
3241 snprintf (dest, 32, "res_ops[%d]", j);
3244 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3245 snprintf (dest, 32, "res_op%d", j);
3248 = get_operand_type (opr,
3249 "type", e->expr_type,
3251 ? NULL : "TREE_TYPE (res_op0)");
3252 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3256 fprintf_indent (f, indent, "return true;\n");
3259 fprintf_indent (f, indent, "tree res;\n");
3260 /* Re-fold the toplevel result. Use non_lvalue to
3261 build NON_LVALUE_EXPRs so they get properly
3262 ignored when in GIMPLE form. */
3263 if (*opr == NON_LVALUE_EXPR)
3264 fprintf_indent (f, indent,
3265 "res = non_lvalue_loc (loc, res_op0);\n");
3268 if (is_a <operator_id *> (opr))
3269 fprintf_indent (f, indent,
3270 "res = fold_build%d_loc (loc, %s, type",
3272 *e->operation == CONVERT_EXPR
3273 ? "NOP_EXPR" : e->operation->id);
3275 fprintf_indent (f, indent,
3276 "res = maybe_build_call_expr_loc (loc, "
3277 "%s, type, %d", e->operation->id,
3279 for (unsigned j = 0; j < e->ops.length (); ++j)
3280 fprintf (f, ", res_op%d", j);
3281 fprintf (f, ");\n");
3282 if (!is_a <operator_id *> (opr))
3284 fprintf_indent (f, indent, "if (!res)\n");
3285 fprintf_indent (f, indent, " return NULL_TREE;\n");
3290 else if (result->type == operand::OP_CAPTURE
3291 || result->type == operand::OP_C_EXPR)
3294 fprintf_indent (f, indent, "tree res;\n");
3295 result->gen_transform (f, indent, "res", false, 1, "type",
3302 /* Search for captures not used in the result expression and dependent
3303 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3304 for (int i = 0; i < s->capture_max + 1; ++i)
3306 if (cinfo.info[i].same_as != (unsigned)i)
3308 if (!cinfo.info[i].force_no_side_effects_p
3309 && !cinfo.info[i].expr_p
3310 && cinfo.info[i].result_use_count == 0)
3312 fprintf_indent (f, indent,
3313 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3315 fprintf_indent (f, indent + 2,
3316 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3317 "fold_ignored_result (captures[%d]), res);\n",
3321 fprintf_indent (f, indent, "return res;\n");
3326 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3327 step of a '(simplify ...)' or '(match ...)'. This handles everything
3328 that is not part of the decision tree (simplify->match). */
3331 dt_simplify::gen (FILE *f, int indent, bool gimple)
3333 fprintf_indent (f, indent, "{\n");
3335 output_line_directive (f,
3336 s->result ? s->result->location : s->match->location);
3337 if (s->capture_max >= 0)
3340 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3341 s->capture_max + 1, indexes[0]->get_name (opname));
3343 for (int i = 1; i <= s->capture_max; ++i)
3347 fprintf (f, ", %s", indexes[i]->get_name (opname));
3349 fprintf (f, " };\n");
3352 /* If we have a split-out function for the actual transform, call it. */
3353 if (info && info->fname)
3357 fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
3358 "valueize, type, captures", info->fname);
3359 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3360 if (s->for_subst_vec[i].first->used)
3361 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3362 fprintf (f, "))\n");
3363 fprintf_indent (f, indent, " return true;\n");
3367 fprintf_indent (f, indent, "tree res = %s (loc, type",
3369 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3370 fprintf (f, ", op%d", i);
3371 fprintf (f, ", captures");
3372 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3374 if (s->for_subst_vec[i].first->used)
3375 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3377 fprintf (f, ");\n");
3378 fprintf_indent (f, indent, "if (res) return res;\n");
3383 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3385 if (! s->for_subst_vec[i].first->used)
3387 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3388 fprintf_indent (f, indent, "enum tree_code %s = %s;\n",
3389 s->for_subst_vec[i].first->id,
3390 s->for_subst_vec[i].second->id);
3391 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3392 fprintf_indent (f, indent, "combined_fn %s = %s;\n",
3393 s->for_subst_vec[i].first->id,
3394 s->for_subst_vec[i].second->id);
3398 gen_1 (f, indent, gimple, s->result);
3402 fprintf_indent (f, indent, "}\n");
3406 /* Hash function for finding equivalent transforms. */
3409 sinfo_hashmap_traits::hash (const key_type &v)
3411 /* Only bother to compare those originating from the same source pattern. */
3412 return v->s->result->location;
3415 /* Compare function for finding equivalent transforms. */
3418 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3420 if (o1->type != o2->type)
3425 case operand::OP_IF:
3427 if_expr *if1 = as_a <if_expr *> (o1);
3428 if_expr *if2 = as_a <if_expr *> (o2);
3429 /* ??? Properly compare c-exprs. */
3430 if (if1->cond != if2->cond)
3432 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3434 if (if1->falseexpr != if2->falseexpr
3436 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3440 case operand::OP_WITH:
3442 with_expr *with1 = as_a <with_expr *> (o1);
3443 with_expr *with2 = as_a <with_expr *> (o2);
3444 if (with1->with != with2->with)
3446 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3451 /* We've hit a result. Time to compare capture-infos - this is required
3452 in addition to the conservative pointer-equivalency of the result IL. */
3453 capture_info cinfo1 (s1, o1, true);
3454 capture_info cinfo2 (s2, o2, true);
3456 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3457 || cinfo1.info.length () != cinfo2.info.length ())
3460 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3462 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3463 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3464 || (cinfo1.info[i].force_no_side_effects_p
3465 != cinfo2.info[i].force_no_side_effects_p)
3466 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3467 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3468 /* toplevel_msk is an optimization */
3469 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3470 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3471 /* the pointer back to the capture is for diagnostics only */)
3475 /* ??? Deep-compare the actual result. */
3480 sinfo_hashmap_traits::equal_keys (const key_type &v,
3481 const key_type &candidate)
3483 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3487 /* Main entry to generate code for matching GIMPLE IL off the decision
3491 decision_tree::gen (FILE *f, bool gimple)
3497 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3498 "a total number of %u nodes\n",
3499 gimple ? "GIMPLE" : "GENERIC",
3500 root->num_leafs, root->max_level, root->total_size);
3502 /* First split out the transform part of equal leafs. */
3505 for (sinfo_map_t::iterator iter = si.begin ();
3506 iter != si.end (); ++iter)
3508 sinfo *s = (*iter).second;
3509 /* Do not split out single uses. */
3516 fprintf (stderr, "found %u uses of", s->cnt);
3517 output_line_directive (stderr, s->s->s->result->location);
3520 /* Generate a split out function with the leaf transform code. */
3521 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3524 fprintf (f, "\nstatic bool\n"
3525 "%s (code_helper *res_code, tree *res_ops,\n"
3526 " gimple_seq *seq, tree (*valueize)(tree) "
3527 "ATTRIBUTE_UNUSED,\n"
3528 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3533 fprintf (f, "\nstatic tree\n"
3534 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3535 (*iter).second->fname);
3536 for (unsigned i = 0;
3537 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3538 fprintf (f, " tree ARG_UNUSED (op%d),", i);
3539 fprintf (f, " tree *captures\n");
3541 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3543 if (! s->s->s->for_subst_vec[i].first->used)
3545 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3546 fprintf (f, ", enum tree_code ARG_UNUSED (%s)",
3547 s->s->s->for_subst_vec[i].first->id);
3548 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3549 fprintf (f, ", combined_fn ARG_UNUSED (%s)",
3550 s->s->s->for_subst_vec[i].first->id);
3553 fprintf (f, ")\n{\n");
3554 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3556 fprintf (f, " return false;\n");
3558 fprintf (f, " return NULL_TREE;\n");
3561 fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3563 for (unsigned n = 1; n <= 3; ++n)
3565 /* First generate split-out functions. */
3566 for (unsigned i = 0; i < root->kids.length (); i++)
3568 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3569 expr *e = static_cast<expr *>(dop->op);
3570 if (e->ops.length () != n
3571 /* Builtin simplifications are somewhat premature on
3572 GENERIC. The following drops patterns with outermost
3573 calls. It's easy to emit overloads for function code
3574 though if necessary. */
3576 && e->operation->kind != id_base::CODE))
3580 fprintf (f, "\nstatic bool\n"
3581 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3582 " gimple_seq *seq, tree (*valueize)(tree) "
3583 "ATTRIBUTE_UNUSED,\n"
3584 " code_helper ARG_UNUSED (code), tree "
3585 "ARG_UNUSED (type)\n",
3588 fprintf (f, "\nstatic tree\n"
3589 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3590 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3592 for (unsigned i = 0; i < n; ++i)
3593 fprintf (f, ", tree op%d", i);
3596 dop->gen_kids (f, 2, gimple);
3598 fprintf (f, " return false;\n");
3600 fprintf (f, " return NULL_TREE;\n");
3604 /* Then generate the main entry with the outermost switch and
3605 tail-calls to the split-out functions. */
3607 fprintf (f, "\nstatic bool\n"
3608 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3609 " gimple_seq *seq, tree (*valueize)(tree),\n"
3610 " code_helper code, tree type");
3612 fprintf (f, "\ntree\n"
3613 "generic_simplify (location_t loc, enum tree_code code, "
3614 "tree type ATTRIBUTE_UNUSED");
3615 for (unsigned i = 0; i < n; ++i)
3616 fprintf (f, ", tree op%d", i);
3621 fprintf (f, " switch (code.get_rep())\n"
3624 fprintf (f, " switch (code)\n"
3626 for (unsigned i = 0; i < root->kids.length (); i++)
3628 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3629 expr *e = static_cast<expr *>(dop->op);
3630 if (e->ops.length () != n
3631 /* Builtin simplifications are somewhat premature on
3632 GENERIC. The following drops patterns with outermost
3633 calls. It's easy to emit overloads for function code
3634 though if necessary. */
3636 && e->operation->kind != id_base::CODE))
3639 if (*e->operation == CONVERT_EXPR
3640 || *e->operation == NOP_EXPR)
3641 fprintf (f, " CASE_CONVERT:\n");
3643 fprintf (f, " case %s%s:\n",
3644 is_a <fn_id *> (e->operation) ? "-" : "",
3647 fprintf (f, " return gimple_simplify_%s (res_code, res_ops, "
3648 "seq, valueize, code, type", e->operation->id);
3650 fprintf (f, " return generic_simplify_%s (loc, code, type",
3652 for (unsigned i = 0; i < n; ++i)
3653 fprintf (f, ", op%d", i);
3654 fprintf (f, ");\n");
3656 fprintf (f, " default:;\n"
3660 fprintf (f, " return false;\n");
3662 fprintf (f, " return NULL_TREE;\n");
3667 /* Output code to implement the predicate P from the decision tree DT. */
3670 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3672 fprintf (f, "\nbool\n"
3673 "%s%s (tree t%s%s)\n"
3674 "{\n", gimple ? "gimple_" : "tree_", p->id,
3675 p->nargs > 0 ? ", tree *res_ops" : "",
3676 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3677 /* Conveniently make 'type' available. */
3678 fprintf_indent (f, 2, "tree type = TREE_TYPE (t);\n");
3681 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3682 dt.root->gen_kids (f, 2, gimple);
3684 fprintf_indent (f, 2, "return false;\n"
3688 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3691 write_header (FILE *f, const char *head)
3693 fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3694 fprintf (f, " a IL pattern matching and simplification description. */\n");
3696 /* Include the header instead of writing it awkwardly quoted here. */
3697 fprintf (f, "\n#include \"%s\"\n", head);
3707 parser (cpp_reader *);
3710 const cpp_token *next ();
3711 const cpp_token *peek (unsigned = 1);
3712 const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3713 const cpp_token *expect (enum cpp_ttype);
3714 const cpp_token *eat_token (enum cpp_ttype);
3715 const char *get_string ();
3716 const char *get_ident ();
3717 const cpp_token *eat_ident (const char *);
3718 const char *get_number ();
3720 id_base *parse_operation ();
3721 operand *parse_capture (operand *, bool);
3722 operand *parse_expr ();
3723 c_expr *parse_c_expr (cpp_ttype);
3724 operand *parse_op ();
3726 void record_operlist (source_location, user_id *);
3728 void parse_pattern ();
3729 operand *parse_result (operand *, predicate_id *);
3730 void push_simplify (simplify::simplify_kind,
3731 vec<simplify *>&, operand *, operand *);
3732 void parse_simplify (simplify::simplify_kind,
3733 vec<simplify *>&, predicate_id *, operand *);
3734 void parse_for (source_location);
3735 void parse_if (source_location);
3736 void parse_predicates (source_location);
3737 void parse_operator_list (source_location);
3740 vec<c_expr *> active_ifs;
3741 vec<vec<user_id *> > active_fors;
3742 hash_set<user_id *> *oper_lists_set;
3743 vec<user_id *> oper_lists;
3745 cid_map_t *capture_ids;
3748 vec<simplify *> simplifiers;
3749 vec<predicate_id *> user_predicates;
3750 bool parsing_match_operand;
3753 /* Lexing helpers. */
3755 /* Read the next non-whitespace token from R. */
3760 const cpp_token *token;
3763 token = cpp_get_token (r);
3765 while (token->type == CPP_PADDING
3766 && token->type != CPP_EOF);
3770 /* Peek at the next non-whitespace token from R. */
3773 parser::peek (unsigned num)
3775 const cpp_token *token;
3779 token = cpp_peek_token (r, i++);
3781 while ((token->type == CPP_PADDING
3782 && token->type != CPP_EOF)
3784 /* If we peek at EOF this is a fatal error as it leaves the
3785 cpp_reader in unusable state. Assume we really wanted a
3786 token and thus this EOF is unexpected. */
3787 if (token->type == CPP_EOF)
3788 fatal_at (token, "unexpected end of file");
3792 /* Peek at the next identifier token (or return NULL if the next
3793 token is not an identifier or equal to ID if supplied). */
3796 parser::peek_ident (const char *id, unsigned num)
3798 const cpp_token *token = peek (num);
3799 if (token->type != CPP_NAME)
3805 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3806 if (strcmp (id, t) == 0)
3812 /* Read the next token from R and assert it is of type TK. */
3815 parser::expect (enum cpp_ttype tk)
3817 const cpp_token *token = next ();
3818 if (token->type != tk)
3819 fatal_at (token, "expected %s, got %s",
3820 cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3825 /* Consume the next token from R and assert it is of type TK. */
3828 parser::eat_token (enum cpp_ttype tk)
3833 /* Read the next token from R and assert it is of type CPP_STRING and
3834 return its value. */
3837 parser::get_string ()
3839 const cpp_token *token = expect (CPP_STRING);
3840 return (const char *)token->val.str.text;
3843 /* Read the next token from R and assert it is of type CPP_NAME and
3844 return its value. */
3847 parser::get_ident ()
3849 const cpp_token *token = expect (CPP_NAME);
3850 return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3853 /* Eat an identifier token with value S from R. */
3856 parser::eat_ident (const char *s)
3858 const cpp_token *token = peek ();
3859 const char *t = get_ident ();
3860 if (strcmp (s, t) != 0)
3861 fatal_at (token, "expected '%s' got '%s'\n", s, t);
3865 /* Read the next token from R and assert it is of type CPP_NUMBER and
3866 return its value. */
3869 parser::get_number ()
3871 const cpp_token *token = expect (CPP_NUMBER);
3872 return (const char *)token->val.str.text;
3876 /* Record an operator-list use for transparent for handling. */
3879 parser::record_operlist (source_location loc, user_id *p)
3881 if (!oper_lists_set->add (p))
3883 if (!oper_lists.is_empty ()
3884 && oper_lists[0]->substitutes.length () != p->substitutes.length ())
3885 fatal_at (loc, "User-defined operator list does not have the "
3886 "same number of entries as others used in the pattern");
3887 oper_lists.safe_push (p);
3891 /* Parse the operator ID, special-casing convert?, convert1? and
3895 parser::parse_operation ()
3897 const cpp_token *id_tok = peek ();
3898 const char *id = get_ident ();
3899 const cpp_token *token = peek ();
3900 if (strcmp (id, "convert0") == 0)
3901 fatal_at (id_tok, "use 'convert?' here");
3902 else if (strcmp (id, "view_convert0") == 0)
3903 fatal_at (id_tok, "use 'view_convert?' here");
3904 if (token->type == CPP_QUERY
3905 && !(token->flags & PREV_WHITE))
3907 if (strcmp (id, "convert") == 0)
3909 else if (strcmp (id, "convert1") == 0)
3911 else if (strcmp (id, "convert2") == 0)
3913 else if (strcmp (id, "view_convert") == 0)
3914 id = "view_convert0";
3915 else if (strcmp (id, "view_convert1") == 0)
3917 else if (strcmp (id, "view_convert2") == 0)
3920 fatal_at (id_tok, "non-convert operator conditionalized");
3922 if (!parsing_match_operand)
3923 fatal_at (id_tok, "conditional convert can only be used in "
3924 "match expression");
3925 eat_token (CPP_QUERY);
3927 else if (strcmp (id, "convert1") == 0
3928 || strcmp (id, "convert2") == 0
3929 || strcmp (id, "view_convert1") == 0
3930 || strcmp (id, "view_convert2") == 0)
3931 fatal_at (id_tok, "expected '?' after conditional operator");
3932 id_base *op = get_operator (id);
3934 fatal_at (id_tok, "unknown operator %s", id);
3936 user_id *p = dyn_cast<user_id *> (op);
3937 if (p && p->is_oper_list)
3939 if (active_fors.length() == 0)
3940 record_operlist (id_tok->src_loc, p);
3942 fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
3948 capture = '@'<number> */
3951 parser::parse_capture (operand *op, bool require_existing)
3953 source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
3954 const cpp_token *token = peek ();
3955 const char *id = NULL;
3956 if (token->type == CPP_NUMBER)
3958 else if (token->type == CPP_NAME)
3961 fatal_at (token, "expected number or identifier");
3962 unsigned next_id = capture_ids->elements ();
3964 unsigned &num = capture_ids->get_or_insert (id, &existed);
3967 if (require_existing)
3968 fatal_at (src_loc, "unknown capture id");
3971 return new capture (src_loc, num, op);
3974 /* Parse an expression
3975 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3978 parser::parse_expr ()
3980 const cpp_token *token = peek ();
3981 expr *e = new expr (parse_operation (), token->src_loc);
3984 bool is_commutative = false;
3985 bool force_capture = false;
3986 const char *expr_type = NULL;
3988 if (token->type == CPP_COLON
3989 && !(token->flags & PREV_WHITE))
3991 eat_token (CPP_COLON);
3993 if (token->type == CPP_NAME
3994 && !(token->flags & PREV_WHITE))
3996 const char *s = get_ident ();
3997 if (!parsing_match_operand)
4007 = dyn_cast<operator_id *> (e->operation))
4009 if (!commutative_tree_code (p->code)
4010 && !comparison_code_p (p->code))
4011 fatal_at (token, "operation is not commutative");
4013 else if (user_id *p = dyn_cast<user_id *> (e->operation))
4014 for (unsigned i = 0;
4015 i < p->substitutes.length (); ++i)
4018 = dyn_cast<operator_id *> (p->substitutes[i]))
4020 if (!commutative_tree_code (q->code)
4021 && !comparison_code_p (q->code))
4022 fatal_at (token, "operation %s is not "
4023 "commutative", q->id);
4026 is_commutative = true;
4028 else if (*sp == 'C')
4029 is_commutative = true;
4030 else if (*sp == 's')
4032 e->force_single_use = true;
4033 force_capture = true;
4036 fatal_at (token, "flag %c not recognized", *sp);
4043 fatal_at (token, "expected flag or type specifying identifier");
4046 if (token->type == CPP_ATSIGN
4047 && !(token->flags & PREV_WHITE))
4048 op = parse_capture (e, false);
4049 else if (force_capture)
4051 unsigned num = capture_ids->elements ();
4054 sprintf (id, "__%u", num);
4055 capture_ids->get_or_insert (xstrdup (id), &existed);
4057 fatal_at (token, "reserved capture id '%s' already used", id);
4058 op = new capture (token->src_loc, num, e);
4064 const cpp_token *token = peek ();
4065 if (token->type == CPP_CLOSE_PAREN)
4067 if (e->operation->nargs != -1
4068 && e->operation->nargs != (int) e->ops.length ())
4069 fatal_at (token, "'%s' expects %u operands, not %u",
4070 e->operation->id, e->operation->nargs, e->ops.length ());
4073 if (e->ops.length () == 2)
4074 e->is_commutative = true;
4076 fatal_at (token, "only binary operators or function with "
4077 "two arguments can be marked commutative");
4079 e->expr_type = expr_type;
4082 else if (!(token->flags & PREV_WHITE))
4083 fatal_at (token, "expected expression operand");
4085 e->append_op (parse_op ());
4090 /* Lex native C code delimited by START recording the preprocessing tokens
4091 for later processing.
4092 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4095 parser::parse_c_expr (cpp_ttype start)
4097 const cpp_token *token;
4100 vec<cpp_token> code = vNULL;
4101 unsigned nr_stmts = 0;
4102 source_location loc = eat_token (start)->src_loc;
4103 if (start == CPP_OPEN_PAREN)
4104 end = CPP_CLOSE_PAREN;
4105 else if (start == CPP_OPEN_BRACE)
4106 end = CPP_CLOSE_BRACE;
4114 /* Count brace pairs to find the end of the expr to match. */
4115 if (token->type == start)
4117 else if (token->type == end
4121 /* This is a lame way of counting the number of statements. */
4122 if (token->type == CPP_SEMICOLON)
4125 /* If this is possibly a user-defined identifier mark it used. */
4126 if (token->type == CPP_NAME)
4128 id_base *idb = get_operator ((const char *)CPP_HASHNODE
4129 (token->val.node.node)->ident.str);
4131 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
4132 record_operlist (token->src_loc, p);
4135 /* Record the token. */
4136 code.safe_push (*token);
4139 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4142 /* Parse an operand which is either an expression, a predicate or
4143 a standalone capture.
4144 op = predicate | expr | c_expr | capture */
4149 const cpp_token *token = peek ();
4150 struct operand *op = NULL;
4151 if (token->type == CPP_OPEN_PAREN)
4153 eat_token (CPP_OPEN_PAREN);
4155 eat_token (CPP_CLOSE_PAREN);
4157 else if (token->type == CPP_OPEN_BRACE)
4159 op = parse_c_expr (CPP_OPEN_BRACE);
4163 /* Remaining ops are either empty or predicates */
4164 if (token->type == CPP_NAME)
4166 const char *id = get_ident ();
4167 id_base *opr = get_operator (id);
4169 fatal_at (token, "expected predicate name");
4170 if (operator_id *code = dyn_cast <operator_id *> (opr))
4172 if (code->nargs != 0)
4173 fatal_at (token, "using an operator with operands as predicate");
4174 /* Parse the zero-operand operator "predicates" as
4176 op = new expr (opr, token->src_loc);
4178 else if (user_id *code = dyn_cast <user_id *> (opr))
4180 if (code->nargs != 0)
4181 fatal_at (token, "using an operator with operands as predicate");
4182 /* Parse the zero-operand operator "predicates" as
4184 op = new expr (opr, token->src_loc);
4186 else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
4187 op = new predicate (p, token->src_loc);
4189 fatal_at (token, "using an unsupported operator as predicate");
4190 if (!parsing_match_operand)
4191 fatal_at (token, "predicates are only allowed in match expression");
4193 if (token->flags & PREV_WHITE)
4196 else if (token->type != CPP_COLON
4197 && token->type != CPP_ATSIGN)
4198 fatal_at (token, "expected expression or predicate");
4199 /* optionally followed by a capture and a predicate. */
4200 if (token->type == CPP_COLON)
4201 fatal_at (token, "not implemented: predicate on leaf operand");
4202 if (token->type == CPP_ATSIGN)
4203 op = parse_capture (op, !parsing_match_operand);
4209 /* Create a new simplify from the current parsing state and MATCH,
4210 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4213 parser::push_simplify (simplify::simplify_kind kind,
4214 vec<simplify *>& simplifiers,
4215 operand *match, operand *result)
4217 /* Build and push a temporary for operator list uses in expressions. */
4218 if (!oper_lists.is_empty ())
4219 active_fors.safe_push (oper_lists);
4221 simplifiers.safe_push
4222 (new simplify (kind, match, result,
4223 active_fors.copy (), capture_ids));
4225 if (!oper_lists.is_empty ())
4230 <result-op> = <op> | <if> | <with>
4231 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4232 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4236 parser::parse_result (operand *result, predicate_id *matcher)
4238 const cpp_token *token = peek ();
4239 if (token->type != CPP_OPEN_PAREN)
4242 eat_token (CPP_OPEN_PAREN);
4243 if (peek_ident ("if"))
4246 if_expr *ife = new if_expr (token->src_loc);
4247 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4248 if (peek ()->type == CPP_OPEN_PAREN)
4250 ife->trueexpr = parse_result (result, matcher);
4251 if (peek ()->type == CPP_OPEN_PAREN)
4252 ife->falseexpr = parse_result (result, matcher);
4253 else if (peek ()->type != CPP_CLOSE_PAREN)
4254 ife->falseexpr = parse_op ();
4256 else if (peek ()->type != CPP_CLOSE_PAREN)
4258 ife->trueexpr = parse_op ();
4259 if (peek ()->type == CPP_OPEN_PAREN)
4260 ife->falseexpr = parse_result (result, matcher);
4261 else if (peek ()->type != CPP_CLOSE_PAREN)
4262 ife->falseexpr = parse_op ();
4264 /* If this if is immediately closed then it contains a
4265 manual matcher or is part of a predicate definition. */
4266 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4269 fatal_at (peek (), "manual transform not implemented");
4270 ife->trueexpr = result;
4272 eat_token (CPP_CLOSE_PAREN);
4275 else if (peek_ident ("with"))
4278 with_expr *withe = new with_expr (token->src_loc);
4279 /* Parse (with c-expr expr) as (if-with (true) expr). */
4280 withe->with = parse_c_expr (CPP_OPEN_BRACE);
4281 withe->with->nr_stmts = 0;
4282 withe->subexpr = parse_result (result, matcher);
4283 eat_token (CPP_CLOSE_PAREN);
4286 else if (peek_ident ("switch"))
4288 token = eat_ident ("switch");
4289 source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4291 if_expr *ife = new if_expr (ifloc);
4293 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4294 if (peek ()->type == CPP_OPEN_PAREN)
4295 ife->trueexpr = parse_result (result, matcher);
4297 ife->trueexpr = parse_op ();
4298 eat_token (CPP_CLOSE_PAREN);
4299 if (peek ()->type != CPP_OPEN_PAREN
4300 || !peek_ident ("if", 2))
4301 fatal_at (token, "switch can be implemented with a single if");
4302 while (peek ()->type != CPP_CLOSE_PAREN)
4304 if (peek ()->type == CPP_OPEN_PAREN)
4306 if (peek_ident ("if", 2))
4308 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4310 ife->falseexpr = new if_expr (ifloc);
4311 ife = as_a <if_expr *> (ife->falseexpr);
4312 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4313 if (peek ()->type == CPP_OPEN_PAREN)
4314 ife->trueexpr = parse_result (result, matcher);
4316 ife->trueexpr = parse_op ();
4317 eat_token (CPP_CLOSE_PAREN);
4321 /* switch default clause */
4322 ife->falseexpr = parse_result (result, matcher);
4323 eat_token (CPP_CLOSE_PAREN);
4329 /* switch default clause */
4330 ife->falseexpr = parse_op ();
4331 eat_token (CPP_CLOSE_PAREN);
4335 eat_token (CPP_CLOSE_PAREN);
4340 operand *op = result;
4343 eat_token (CPP_CLOSE_PAREN);
4349 simplify = 'simplify' <expr> <result-op>
4351 match = 'match' <ident> <expr> [<result-op>]
4352 and fill SIMPLIFIERS with the results. */
4355 parser::parse_simplify (simplify::simplify_kind kind,
4356 vec<simplify *>& simplifiers, predicate_id *matcher,
4359 /* Reset the capture map. */
4361 capture_ids = new cid_map_t;
4362 /* Reset oper_lists and set. */
4363 hash_set <user_id *> olist;
4364 oper_lists_set = &olist;
4367 const cpp_token *loc = peek ();
4368 parsing_match_operand = true;
4369 struct operand *match = parse_op ();
4370 parsing_match_operand = false;
4371 if (match->type == operand::OP_CAPTURE && !matcher)
4372 fatal_at (loc, "outermost expression cannot be captured");
4373 if (match->type == operand::OP_EXPR
4374 && is_a <predicate_id *> (as_a <expr *> (match)->operation))
4375 fatal_at (loc, "outermost expression cannot be a predicate");
4377 /* Splice active_ifs onto result and continue parsing the
4379 if_expr *active_if = NULL;
4380 for (int i = active_ifs.length (); i > 0; --i)
4382 if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4383 ifc->cond = active_ifs[i-1];
4384 ifc->trueexpr = active_if;
4387 if_expr *outermost_if = active_if;
4388 while (active_if && active_if->trueexpr)
4389 active_if = as_a <if_expr *> (active_if->trueexpr);
4391 const cpp_token *token = peek ();
4393 /* If this if is immediately closed then it is part of a predicate
4394 definition. Push it. */
4395 if (token->type == CPP_CLOSE_PAREN)
4398 fatal_at (token, "expected transform expression");
4401 active_if->trueexpr = result;
4402 result = outermost_if;
4404 push_simplify (kind, simplifiers, match, result);
4408 operand *tem = parse_result (result, matcher);
4411 active_if->trueexpr = tem;
4412 result = outermost_if;
4417 push_simplify (kind, simplifiers, match, result);
4420 /* Parsing of the outer control structures. */
4422 /* Parse a for expression
4423 for = '(' 'for' <subst>... <pattern> ')'
4424 subst = <ident> '(' <ident>... ')' */
4427 parser::parse_for (source_location)
4429 auto_vec<const cpp_token *> user_id_tokens;
4430 vec<user_id *> user_ids = vNULL;
4431 const cpp_token *token;
4432 unsigned min_n_opers = 0, max_n_opers = 0;
4437 if (token->type != CPP_NAME)
4440 /* Insert the user defined operators into the operator hash. */
4441 const char *id = get_ident ();
4442 if (get_operator (id, true) != NULL)
4443 fatal_at (token, "operator already defined");
4444 user_id *op = new user_id (id);
4445 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4447 user_ids.safe_push (op);
4448 user_id_tokens.safe_push (token);
4450 eat_token (CPP_OPEN_PAREN);
4453 while ((token = peek_ident ()) != 0)
4455 const char *oper = get_ident ();
4456 id_base *idb = get_operator (oper, true);
4458 fatal_at (token, "no such operator '%s'", oper);
4459 if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
4460 || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
4461 || *idb == VIEW_CONVERT2)
4462 fatal_at (token, "conditional operators cannot be used inside for");
4466 else if (idb->nargs == -1)
4468 else if (idb->nargs != arity)
4469 fatal_at (token, "operator '%s' with arity %d does not match "
4470 "others with arity %d", oper, idb->nargs, arity);
4472 user_id *p = dyn_cast<user_id *> (idb);
4475 if (p->is_oper_list)
4476 op->substitutes.safe_splice (p->substitutes);
4478 fatal_at (token, "iterator cannot be used as operator-list");
4481 op->substitutes.safe_push (idb);
4484 token = expect (CPP_CLOSE_PAREN);
4486 unsigned nsubstitutes = op->substitutes.length ();
4487 if (nsubstitutes == 0)
4488 fatal_at (token, "A user-defined operator must have at least "
4489 "one substitution");
4490 if (max_n_opers == 0)
4492 min_n_opers = nsubstitutes;
4493 max_n_opers = nsubstitutes;
4497 if (nsubstitutes % min_n_opers != 0
4498 && min_n_opers % nsubstitutes != 0)
4499 fatal_at (token, "All user-defined identifiers must have a "
4500 "multiple number of operator substitutions of the "
4501 "smallest number of substitutions");
4502 if (nsubstitutes < min_n_opers)
4503 min_n_opers = nsubstitutes;
4504 else if (nsubstitutes > max_n_opers)
4505 max_n_opers = nsubstitutes;
4509 unsigned n_ids = user_ids.length ();
4511 fatal_at (token, "for requires at least one user-defined identifier");
4514 if (token->type == CPP_CLOSE_PAREN)
4515 fatal_at (token, "no pattern defined in for");
4517 active_fors.safe_push (user_ids);
4521 if (token->type == CPP_CLOSE_PAREN)
4527 /* Remove user-defined operators from the hash again. */
4528 for (unsigned i = 0; i < user_ids.length (); ++i)
4530 if (!user_ids[i]->used)
4531 warning_at (user_id_tokens[i],
4532 "operator %s defined but not used", user_ids[i]->id);
4533 operators->remove_elt (user_ids[i]);
4537 /* Parse an identifier associated with a list of operators.
4538 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4541 parser::parse_operator_list (source_location)
4543 const cpp_token *token = peek ();
4544 const char *id = get_ident ();
4546 if (get_operator (id, true) != 0)
4547 fatal_at (token, "operator %s already defined", id);
4549 user_id *op = new user_id (id, true);
4552 while ((token = peek_ident ()) != 0)
4555 const char *oper = get_ident ();
4556 id_base *idb = get_operator (oper, true);
4559 fatal_at (token, "no such operator '%s'", oper);
4563 else if (idb->nargs == -1)
4565 else if (arity != idb->nargs)
4566 fatal_at (token, "operator '%s' with arity %d does not match "
4567 "others with arity %d", oper, idb->nargs, arity);
4569 /* We allow composition of multiple operator lists. */
4570 if (user_id *p = dyn_cast<user_id *> (idb))
4571 op->substitutes.safe_splice (p->substitutes);
4573 op->substitutes.safe_push (idb);
4576 // Check that there is no junk after id-list
4578 if (token->type != CPP_CLOSE_PAREN)
4579 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4581 if (op->substitutes.length () == 0)
4582 fatal_at (token, "operator-list cannot be empty");
4585 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4589 /* Parse an outer if expression.
4590 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4593 parser::parse_if (source_location)
4595 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4597 const cpp_token *token = peek ();
4598 if (token->type == CPP_CLOSE_PAREN)
4599 fatal_at (token, "no pattern defined in if");
4601 active_ifs.safe_push (ifexpr);
4604 const cpp_token *token = peek ();
4605 if (token->type == CPP_CLOSE_PAREN)
4613 /* Parse a list of predefined predicate identifiers.
4614 preds = '(' 'define_predicates' <ident>... ')' */
4617 parser::parse_predicates (source_location)
4621 const cpp_token *token = peek ();
4622 if (token->type != CPP_NAME)
4625 add_predicate (get_ident ());
4630 /* Parse outer control structures.
4631 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4634 parser::parse_pattern ()
4636 /* All clauses start with '('. */
4637 eat_token (CPP_OPEN_PAREN);
4638 const cpp_token *token = peek ();
4639 const char *id = get_ident ();
4640 if (strcmp (id, "simplify") == 0)
4642 parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
4645 else if (strcmp (id, "match") == 0)
4647 bool with_args = false;
4648 source_location e_loc = peek ()->src_loc;
4649 if (peek ()->type == CPP_OPEN_PAREN)
4651 eat_token (CPP_OPEN_PAREN);
4654 const char *name = get_ident ();
4655 id_base *id = get_operator (name);
4659 p = add_predicate (name);
4660 user_predicates.safe_push (p);
4662 else if ((p = dyn_cast <predicate_id *> (id)))
4665 fatal_at (token, "cannot add a match to a non-predicate ID");
4666 /* Parse (match <id> <arg>... (match-expr)) here. */
4670 capture_ids = new cid_map_t;
4671 e = new expr (p, e_loc);
4672 while (peek ()->type == CPP_ATSIGN)
4673 e->append_op (parse_capture (NULL, false));
4674 eat_token (CPP_CLOSE_PAREN);
4677 && ((e && e->ops.length () != (unsigned)p->nargs)
4678 || (!e && p->nargs != 0)))
4679 fatal_at (token, "non-matching number of match operands");
4680 p->nargs = e ? e->ops.length () : 0;
4681 parse_simplify (simplify::MATCH, p->matchers, p, e);
4684 else if (strcmp (id, "for") == 0)
4685 parse_for (token->src_loc);
4686 else if (strcmp (id, "if") == 0)
4687 parse_if (token->src_loc);
4688 else if (strcmp (id, "define_predicates") == 0)
4690 if (active_ifs.length () > 0
4691 || active_fors.length () > 0)
4692 fatal_at (token, "define_predicates inside if or for is not supported");
4693 parse_predicates (token->src_loc);
4695 else if (strcmp (id, "define_operator_list") == 0)
4697 if (active_ifs.length () > 0
4698 || active_fors.length () > 0)
4699 fatal_at (token, "operator-list inside if or for is not supported");
4700 parse_operator_list (token->src_loc);
4703 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
4704 active_ifs.length () == 0 && active_fors.length () == 0
4705 ? "'define_predicates', " : "");
4707 eat_token (CPP_CLOSE_PAREN);
4710 /* Main entry of the parser. Repeatedly parse outer control structures. */
4712 parser::parser (cpp_reader *r_)
4716 active_fors = vNULL;
4717 simplifiers = vNULL;
4718 oper_lists_set = NULL;
4721 user_predicates = vNULL;
4722 parsing_match_operand = false;
4724 const cpp_token *token = next ();
4725 while (token->type != CPP_EOF)
4727 _cpp_backup_tokens (r, 1);
4734 /* Helper for the linemap code. */
4737 round_alloc_size (size_t s)
4743 /* The genmatch generator progam. It reads from a pattern description
4744 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4747 main (int argc, char **argv)
4751 progname = "genmatch";
4757 char *input = argv[argc-1];
4758 for (int i = 1; i < argc - 1; ++i)
4760 if (strcmp (argv[i], "--gimple") == 0)
4762 else if (strcmp (argv[i], "--generic") == 0)
4764 else if (strcmp (argv[i], "-v") == 0)
4766 else if (strcmp (argv[i], "-vv") == 0)
4770 fprintf (stderr, "Usage: genmatch "
4771 "[--gimple] [--generic] [-v[v]] input\n");
4776 line_table = XCNEW (struct line_maps);
4777 linemap_init (line_table, 0);
4778 line_table->reallocator = xrealloc;
4779 line_table->round_alloc_size = round_alloc_size;
4781 r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
4782 cpp_callbacks *cb = cpp_get_callbacks (r);
4783 cb->error = error_cb;
4785 /* Add the build directory to the #include "" search path. */
4786 cpp_dir *dir = XCNEW (cpp_dir);
4787 dir->name = getpwd ();
4789 dir->name = ASTRDUP (".");
4790 cpp_set_include_chains (r, dir, NULL, false);
4792 if (!cpp_read_main_file (r, input))
4794 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
4795 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
4797 null_id = new id_base (id_base::NULL_ID, "null");
4799 /* Pre-seed operators. */
4800 operators = new hash_table<id_base> (1024);
4801 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4802 add_operator (SYM, # SYM, # TYPE, NARGS);
4803 #define END_OF_BASE_TREE_CODES
4805 add_operator (CONVERT0, "convert0", "tcc_unary", 1);
4806 add_operator (CONVERT1, "convert1", "tcc_unary", 1);
4807 add_operator (CONVERT2, "convert2", "tcc_unary", 1);
4808 add_operator (VIEW_CONVERT0, "view_convert0", "tcc_unary", 1);
4809 add_operator (VIEW_CONVERT1, "view_convert1", "tcc_unary", 1);
4810 add_operator (VIEW_CONVERT2, "view_convert2", "tcc_unary", 1);
4811 #undef END_OF_BASE_TREE_CODES
4814 /* Pre-seed builtin functions.
4815 ??? Cannot use N (name) as that is targetm.emultls.get_address
4816 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4817 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4818 add_function (ENUM, "CFN_" # ENUM);
4819 #include "builtins.def"
4821 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
4822 add_function (IFN_##CODE, "CFN_" #CODE);
4823 #include "internal-fn.def"
4829 write_header (stdout, "gimple-match-head.c");
4831 write_header (stdout, "generic-match-head.c");
4833 /* Go over all predicates defined with patterns and perform
4834 lowering and code generation. */
4835 for (unsigned i = 0; i < p.user_predicates.length (); ++i)
4837 predicate_id *pred = p.user_predicates[i];
4838 lower (pred->matchers, gimple);
4841 for (unsigned i = 0; i < pred->matchers.length (); ++i)
4842 print_matches (pred->matchers[i]);
4845 for (unsigned i = 0; i < pred->matchers.length (); ++i)
4846 dt.insert (pred->matchers[i], i);
4851 write_predicate (stdout, pred, dt, gimple);
4854 /* Lower the main simplifiers and generate code for them. */
4855 lower (p.simplifiers, gimple);
4858 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4859 print_matches (p.simplifiers[i]);
4862 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
4863 dt.insert (p.simplifiers[i], i);
4868 dt.gen (stdout, gimple);
4871 cpp_finish (r, NULL);