1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2023 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 class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
186 /* Secondary stream for fp_decl. */
187 static FILE *header_file
;
189 /* Start or continue emitting a declaration in fprintf-like manner,
190 printing both to F and global header_file, if non-null. */
192 #if GCC_VERSION >= 4001
193 __attribute__((format (printf
, 2, 3)))
195 fp_decl (FILE *f
, const char *format
, ...)
198 va_start (ap
, format
);
199 vfprintf (f
, format
, ap
);
205 va_start (ap
, format
);
206 vfprintf (header_file
, format
, ap
);
210 /* Finish a declaration being emitted by fp_decl. */
212 fp_decl_done (FILE *f
, const char *trailer
)
214 fprintf (f
, "%s\n", trailer
);
216 fprintf (header_file
, "%s;", trailer
);
220 output_line_directive (FILE *f
, location_t location
,
221 bool dumpfile
= false, bool fnargs
= false)
223 const line_map_ordinary
*map
;
224 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
225 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
228 /* When writing to a dumpfile only dump the filename. */
229 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
230 #if defined(DIR_SEPARATOR_2)
231 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
232 if (pos2
&& (!file
|| (pos2
> file
)))
241 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
243 fprintf (f
, "%s:%d", file
, loc
.line
);
245 else if (verbose
>= 2)
246 /* Other gen programs really output line directives here, at least for
247 development it's right now more convenient to have line information
248 from the generated file. Still keep the directives as comment for now
249 to easily back-point to the meta-description. */
250 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
253 /* Find the file to write into next. We try to evenly distribute the contents
254 over the different files. */
256 #define SIZED_BASED_CHUNKS 1
259 choose_output (const vec
<FILE *> &parts
)
261 #ifdef SIZED_BASED_CHUNKS
262 FILE *shortest
= NULL
;
264 for (FILE *part
: parts
)
266 long len
= ftell (part
);
267 if (!shortest
|| min
> len
)
268 shortest
= part
, min
= len
;
272 static int current_file
;
273 return parts
[current_file
++ % parts
.length ()];
278 /* Pull in tree codes and builtin function codes from their
281 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
288 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
289 enum built_in_function
{
290 #include "builtins.def"
294 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
296 #include "internal-fn.def"
301 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
302 CFN_##ENUM = int (ENUM),
303 #include "builtins.def"
305 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
306 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
307 #include "internal-fn.def"
312 #include "case-cfn-macros.h"
314 /* Return true if CODE represents a commutative tree code. Otherwise
317 commutative_tree_code (enum tree_code code
)
323 case MULT_HIGHPART_EXPR
:
338 case WIDEN_MULT_EXPR
:
339 case VEC_WIDEN_MULT_HI_EXPR
:
340 case VEC_WIDEN_MULT_LO_EXPR
:
341 case VEC_WIDEN_MULT_EVEN_EXPR
:
342 case VEC_WIDEN_MULT_ODD_EXPR
:
351 /* Return true if CODE represents a ternary tree code for which the
352 first two operands are commutative. Otherwise return false. */
354 commutative_ternary_tree_code (enum tree_code code
)
358 case WIDEN_MULT_PLUS_EXPR
:
359 case WIDEN_MULT_MINUS_EXPR
:
369 /* Return true if CODE is a comparison. */
372 comparison_code_p (enum tree_code code
)
399 /* Base class for all identifiers the parser knows. */
401 class id_base
: public nofree_ptr_hash
<id_base
>
404 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
406 id_base (id_kind
, const char *, int = -1);
412 /* hash_table support. */
413 static inline hashval_t
hash (const id_base
*);
414 static inline int equal (const id_base
*, const id_base
*);
418 id_base::hash (const id_base
*op
)
424 id_base::equal (const id_base
*op1
,
427 return (op1
->hashval
== op2
->hashval
428 && strcmp (op1
->id
, op2
->id
) == 0);
431 /* The special id "null", which matches nothing. */
432 static id_base
*null_id
;
434 /* Hashtable of known pattern operators. This is pre-seeded from
435 all known tree codes and all known builtin function ids. */
436 static hash_table
<id_base
> *operators
;
438 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
443 hashval
= htab_hash_string (id
);
446 /* Identifier that maps to a tree code. */
448 class operator_id
: public id_base
451 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
453 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
458 /* Identifier that maps to a builtin or internal function code. */
460 class fn_id
: public id_base
463 fn_id (enum built_in_function fn_
, const char *id_
)
464 : id_base (id_base::FN
, id_
), fn (fn_
) {}
465 fn_id (enum internal_fn fn_
, const char *id_
)
466 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
472 /* Identifier that maps to a user-defined predicate. */
474 class predicate_id
: public id_base
477 predicate_id (const char *id_
)
478 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
479 vec
<simplify
*> matchers
;
482 /* Identifier that maps to a operator defined by a 'for' directive. */
484 class user_id
: public id_base
487 user_id (const char *id_
, bool is_oper_list_
= false)
488 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
489 used (false), is_oper_list (is_oper_list_
) {}
490 vec
<id_base
*> substitutes
;
498 is_a_helper
<fn_id
*>::test (id_base
*id
)
500 return id
->kind
== id_base::FN
;
506 is_a_helper
<operator_id
*>::test (id_base
*id
)
508 return id
->kind
== id_base::CODE
;
514 is_a_helper
<predicate_id
*>::test (id_base
*id
)
516 return id
->kind
== id_base::PREDICATE
;
522 is_a_helper
<user_id
*>::test (id_base
*id
)
524 return id
->kind
== id_base::USER
;
527 /* If ID has a pair of consecutive, commutative operands, return the
528 index of the first, otherwise return -1. */
531 commutative_op (id_base
*id
)
533 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
535 if (commutative_tree_code (code
->code
)
536 || commutative_ternary_tree_code (code
->code
))
540 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
567 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
569 int res
= commutative_op (uid
->substitutes
[0]);
572 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
573 if (res
!= commutative_op (uid
->substitutes
[i
]))
580 /* Add a predicate identifier to the hash. */
582 static predicate_id
*
583 add_predicate (const char *id
)
585 predicate_id
*p
= new predicate_id (id
);
586 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
588 fatal ("duplicate id definition");
593 /* Add a tree code identifier to the hash. */
596 add_operator (enum tree_code code
, const char *id
,
597 const char *tcc
, unsigned nargs
)
599 if (strcmp (tcc
, "tcc_unary") != 0
600 && strcmp (tcc
, "tcc_binary") != 0
601 && strcmp (tcc
, "tcc_comparison") != 0
602 && strcmp (tcc
, "tcc_expression") != 0
603 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
604 && strcmp (tcc
, "tcc_reference") != 0
605 /* To have INTEGER_CST and friends as "predicate operators". */
606 && strcmp (tcc
, "tcc_constant") != 0
607 /* And allow CONSTRUCTOR for vector initializers. */
608 && !(code
== CONSTRUCTOR
)
609 /* Allow SSA_NAME as predicate operator. */
610 && !(code
== SSA_NAME
))
612 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
613 if (code
== ADDR_EXPR
)
615 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
616 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
618 fatal ("duplicate id definition");
622 /* Add a built-in or internal function identifier to the hash. ID is
623 the name of its CFN_* enumeration value. */
625 template <typename T
>
627 add_function (T code
, const char *id
)
629 fn_id
*fn
= new fn_id (code
, id
);
630 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
632 fatal ("duplicate id definition");
636 /* Helper for easy comparing ID with tree code CODE. */
639 operator==(id_base
&id
, enum tree_code code
)
641 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
642 return oid
->code
== code
;
646 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
649 get_operator (const char *id
, bool allow_null
= false)
651 if (allow_null
&& strcmp (id
, "null") == 0)
654 id_base
tem (id_base::CODE
, id
);
656 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
659 /* If this is a user-defined identifier track whether it was used. */
660 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
666 bool all_upper
= true;
667 bool all_lower
= true;
668 for (unsigned int i
= 0; id
[i
]; ++i
)
671 else if (ISLOWER (id
[i
]))
675 /* Try in caps with _EXPR appended. */
676 id2
= ACONCAT ((id
, "_EXPR", NULL
));
677 for (unsigned int i
= 0; id2
[i
]; ++i
)
678 id2
[i
] = TOUPPER (id2
[i
]);
680 else if (all_upper
&& startswith (id
, "IFN_"))
681 /* Try CFN_ instead of IFN_. */
682 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
683 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
684 /* Try prepending CFN_. */
685 id2
= ACONCAT (("CFN_", id
, NULL
));
689 new (&tem
) id_base (id_base::CODE
, id2
);
690 return operators
->find_with_hash (&tem
, tem
.hashval
);
693 /* Return the comparison operators that results if the operands are
694 swapped. This is safe for floating-point. */
697 swap_tree_comparison (operator_id
*p
)
709 return get_operator ("LT_EXPR");
711 return get_operator ("LE_EXPR");
713 return get_operator ("GT_EXPR");
715 return get_operator ("GE_EXPR");
717 return get_operator ("UNLT_EXPR");
719 return get_operator ("UNLE_EXPR");
721 return get_operator ("UNGT_EXPR");
723 return get_operator ("UNGE_EXPR");
729 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
732 /* The AST produced by parsing of the pattern definitions. */
737 /* The base class for operands. */
741 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
742 operand (enum op_type type_
, location_t loc_
)
743 : type (type_
), location (loc_
) {}
746 virtual void gen_transform (FILE *, int, const char *, bool, int,
747 const char *, capture_info
*,
750 { gcc_unreachable (); }
753 /* A predicate operand. Predicates are leafs in the AST. */
755 class predicate
: public operand
758 predicate (predicate_id
*p_
, location_t loc
)
759 : operand (OP_PREDICATE
, loc
), p (p_
) {}
763 /* An operand that constitutes an expression. Expressions include
764 function calls and user-defined predicate invocations. */
766 class expr
: public operand
769 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
770 : operand (OP_EXPR
, loc
), operation (operation_
),
771 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
772 is_generic (false), force_single_use (false), force_leaf (false),
775 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
776 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
777 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
778 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
779 void append_op (operand
*op
) { ops
.safe_push (op
); }
780 /* The operator and its operands. */
783 /* An explicitely specified type - used exclusively for conversions. */
784 const char *expr_type
;
785 /* Whether the operation is to be applied commutatively. This is
786 later lowered to two separate patterns. */
788 /* Whether the expression is expected to be in GENERIC form. */
790 /* Whether pushing any stmt to the sequence should be conditional
791 on this expression having a single-use. */
792 bool force_single_use
;
793 /* Whether in the result expression this should be a leaf node
794 with any children simplified down to simple operands. */
796 /* If non-zero, the group for optional handling. */
797 unsigned char opt_grp
;
798 void gen_transform (FILE *f
, int, const char *, bool, int,
799 const char *, capture_info
*,
800 dt_operand
** = 0, int = 0) override
;
803 /* An operator that is represented by native C code. This is always
804 a leaf operand in the AST. This class is also used to represent
805 the code to be generated for 'if' and 'with' expressions. */
807 class c_expr
: public operand
810 /* A mapping of an identifier and its replacement. Used to apply
816 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
819 c_expr (cpp_reader
*r_
, location_t loc
,
820 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
821 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
822 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
823 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
824 /* cpplib tokens and state to transform this back to source. */
827 cid_map_t
*capture_ids
;
828 /* The number of statements parsed (well, the number of ';'s). */
830 /* The identifier replacement vector. */
832 void gen_transform (FILE *f
, int, const char *, bool, int,
833 const char *, capture_info
*,
834 dt_operand
** = 0, int = 0) final override
;
837 /* A wrapper around another operand that captures its value. */
839 class capture
: public operand
842 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
843 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
845 /* Identifier index for the value. */
847 /* Whether in a match of two operands the compare should be for
848 equal values rather than equal atoms (boils down to a type
851 /* The captured value. */
853 void gen_transform (FILE *f
, int, const char *, bool, int,
854 const char *, capture_info
*,
855 dt_operand
** = 0, int = 0) final override
;
860 class if_expr
: public operand
863 if_expr (location_t loc
)
864 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
870 /* with expression. */
872 class with_expr
: public operand
875 with_expr (location_t loc
)
876 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
884 is_a_helper
<capture
*>::test (operand
*op
)
886 return op
->type
== operand::OP_CAPTURE
;
892 is_a_helper
<predicate
*>::test (operand
*op
)
894 return op
->type
== operand::OP_PREDICATE
;
900 is_a_helper
<c_expr
*>::test (operand
*op
)
902 return op
->type
== operand::OP_C_EXPR
;
908 is_a_helper
<expr
*>::test (operand
*op
)
910 return op
->type
== operand::OP_EXPR
;
916 is_a_helper
<if_expr
*>::test (operand
*op
)
918 return op
->type
== operand::OP_IF
;
924 is_a_helper
<with_expr
*>::test (operand
*op
)
926 return op
->type
== operand::OP_WITH
;
929 /* The main class of a pattern and its transform. This is used to
930 represent both (simplify ...) and (match ...) kinds. The AST
931 duplicates all outer 'if' and 'for' expressions here so each
932 simplify can exist in isolation. */
937 enum simplify_kind
{ SIMPLIFY
, MATCH
};
939 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
940 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
941 cid_map_t
*capture_ids_
)
942 : kind (kind_
), id (id_
), match (match_
), result (result_
),
943 for_vec (for_vec_
), for_subst_vec (vNULL
),
944 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
947 /* ID. This is kept to easily associate related simplifies expanded
948 from the same original one. */
950 /* The expression that is matched against the GENERIC or GIMPLE IL. */
952 /* For a (simplify ...) an expression with ifs and withs with the expression
953 produced when the pattern applies in the leafs.
954 For a (match ...) the leafs are either empty if it is a simple predicate
955 or the single expression specifying the matched operands. */
956 class operand
*result
;
957 /* Collected 'for' expression operators that have to be replaced
958 in the lowering phase. */
959 vec
<vec
<user_id
*> > for_vec
;
960 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
961 /* A map of capture identifiers to indexes. */
962 cid_map_t
*capture_ids
;
966 /* Debugging routines for dumping the AST. */
969 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
971 if (capture
*c
= dyn_cast
<capture
*> (o
))
973 if (c
->what
&& flattened
== false)
974 print_operand (c
->what
, f
, flattened
);
975 fprintf (f
, "@%u", c
->where
);
978 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
979 fprintf (f
, "%s", p
->p
->id
);
981 else if (is_a
<c_expr
*> (o
))
982 fprintf (f
, "c_expr");
984 else if (expr
*e
= dyn_cast
<expr
*> (o
))
986 if (e
->ops
.length () == 0)
987 fprintf (f
, "%s", e
->operation
->id
);
990 fprintf (f
, "(%s", e
->operation
->id
);
992 if (flattened
== false)
994 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
997 print_operand (e
->ops
[i
], f
, flattened
);
1009 print_matches (class simplify
*s
, FILE *f
= stderr
)
1011 fprintf (f
, "for expression: ");
1012 print_operand (s
->match
, f
);
1019 /* Lowering of commutative operators. */
1022 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
1023 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
1025 if (n
== ops_vector
.length ())
1027 vec
<operand
*> xv
= v
.copy ();
1028 result
.safe_push (xv
);
1032 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
1034 v
[n
] = ops_vector
[n
][i
];
1035 cartesian_product (ops_vector
, result
, v
, n
+ 1);
1039 /* Lower OP to two operands in case it is marked as commutative. */
1041 static vec
<operand
*>
1042 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
1044 vec
<operand
*> ret
= vNULL
;
1046 if (capture
*c
= dyn_cast
<capture
*> (op
))
1053 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
1054 for (unsigned i
= 0; i
< v
.length (); ++i
)
1056 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
1063 expr
*e
= dyn_cast
<expr
*> (op
);
1064 if (!e
|| e
->ops
.length () == 0)
1070 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1071 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1072 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1074 auto_vec
< vec
<operand
*> > result
;
1075 auto_vec
<operand
*> v (e
->ops
.length ());
1076 v
.quick_grow_cleared (e
->ops
.length ());
1077 cartesian_product (ops_vector
, result
, v
, 0);
1080 for (unsigned i
= 0; i
< result
.length (); ++i
)
1082 expr
*ne
= new expr (e
);
1083 ne
->is_commutative
= false;
1084 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1085 ne
->append_op (result
[i
][j
]);
1089 if (!e
->is_commutative
)
1092 /* The operation is always binary if it isn't inherently commutative. */
1093 int natural_opno
= commutative_op (e
->operation
);
1094 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1095 for (unsigned i
= 0; i
< result
.length (); ++i
)
1097 expr
*ne
= new expr (e
);
1098 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1100 if (comparison_code_p (r
->code
))
1101 ne
->operation
= swap_tree_comparison (r
);
1103 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1105 bool found_compare
= false;
1106 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1107 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1109 if (comparison_code_p (q
->code
)
1110 && swap_tree_comparison (q
) != q
)
1112 found_compare
= true;
1118 user_id
*newop
= new user_id ("<internal>");
1119 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1121 id_base
*subst
= p
->substitutes
[j
];
1122 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1124 if (comparison_code_p (q
->code
))
1125 subst
= swap_tree_comparison (q
);
1127 newop
->substitutes
.safe_push (subst
);
1129 ne
->operation
= newop
;
1130 /* Search for 'p' inside the for vector and push 'newop'
1131 to the same level. */
1132 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1133 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1134 if (for_vec
[j
][k
] == p
)
1136 for_vec
[j
].safe_push (newop
);
1142 ne
->is_commutative
= false;
1143 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1145 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1146 ne
->append_op (result
[i
][old_j
]);
1154 /* Lower operations marked as commutative in the AST of S and push
1155 the resulting patterns to SIMPLIFIERS. */
1158 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1160 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1161 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1163 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1164 s
->for_vec
, s
->capture_ids
);
1165 simplifiers
.safe_push (ns
);
1169 /* Strip conditional operations using group GRP from O and its
1170 children if STRIP, else replace them with an unconditional operation. */
1173 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1175 if (capture
*c
= dyn_cast
<capture
*> (o
))
1178 return new capture (c
->location
, c
->where
,
1179 lower_opt (c
->what
, grp
, strip
),
1185 expr
*e
= dyn_cast
<expr
*> (o
);
1189 if (e
->opt_grp
== grp
)
1192 return lower_opt (e
->ops
[0], grp
, strip
);
1194 expr
*ne
= new expr (e
);
1196 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1200 expr
*ne
= new expr (e
);
1201 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1202 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1207 /* Determine whether O or its children uses the conditional operation
1211 has_opt (operand
*o
, unsigned char grp
)
1213 if (capture
*c
= dyn_cast
<capture
*> (o
))
1216 return has_opt (c
->what
, grp
);
1221 expr
*e
= dyn_cast
<expr
*> (o
);
1225 if (e
->opt_grp
== grp
)
1228 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1229 if (has_opt (e
->ops
[i
], grp
))
1235 /* Lower conditional convert operators in O, expanding it to a vector
1238 static vec
<operand
*>
1239 lower_opt (operand
*o
)
1241 vec
<operand
*> v1
= vNULL
, v2
;
1245 /* Conditional operations are lowered to a pattern with the
1246 operation and one without. All different conditional operation
1247 groups are lowered separately. */
1249 for (unsigned i
= 1; i
<= 10; ++i
)
1252 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1253 if (has_opt (v1
[j
], i
))
1255 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1256 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1262 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1263 v1
.safe_push (v2
[j
]);
1270 /* Lower conditional convert operators in the AST of S and push
1271 the resulting multiple patterns to SIMPLIFIERS. */
1274 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1276 vec
<operand
*> matchers
= lower_opt (s
->match
);
1277 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1279 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1280 s
->for_vec
, s
->capture_ids
);
1281 simplifiers
.safe_push (ns
);
1285 /* Lower the compare operand of COND_EXPRs to a
1286 GENERIC and a GIMPLE variant. */
1288 static vec
<operand
*>
1289 lower_cond (operand
*o
)
1291 vec
<operand
*> ro
= vNULL
;
1293 if (capture
*c
= dyn_cast
<capture
*> (o
))
1297 vec
<operand
*> lop
= vNULL
;
1298 lop
= lower_cond (c
->what
);
1300 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1301 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1307 expr
*e
= dyn_cast
<expr
*> (o
);
1308 if (!e
|| e
->ops
.length () == 0)
1314 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1315 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1316 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1318 auto_vec
< vec
<operand
*> > result
;
1319 auto_vec
<operand
*> v (e
->ops
.length ());
1320 v
.quick_grow_cleared (e
->ops
.length ());
1321 cartesian_product (ops_vector
, result
, v
, 0);
1323 for (unsigned i
= 0; i
< result
.length (); ++i
)
1325 expr
*ne
= new expr (e
);
1326 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1327 ne
->append_op (result
[i
][j
]);
1329 /* If this is a COND with a captured expression or an
1330 expression with two operands then also match a GENERIC
1331 form on the compare. */
1332 if (*e
->operation
== COND_EXPR
1333 && ((is_a
<capture
*> (e
->ops
[0])
1334 && as_a
<capture
*> (e
->ops
[0])->what
1335 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1337 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1338 || (is_a
<expr
*> (e
->ops
[0])
1339 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1342 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1343 ne
->append_op (result
[i
][j
]);
1344 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1346 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1347 expr
*cmp
= new expr (ocmp
);
1348 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1349 cmp
->append_op (ocmp
->ops
[j
]);
1350 cmp
->is_generic
= true;
1351 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1356 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1357 expr
*cmp
= new expr (ocmp
);
1358 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1359 cmp
->append_op (ocmp
->ops
[j
]);
1360 cmp
->is_generic
= true;
1370 /* Lower the compare operand of COND_EXPRs to a
1371 GENERIC and a GIMPLE variant. */
1374 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1376 vec
<operand
*> matchers
= lower_cond (s
->match
);
1377 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1379 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1380 s
->for_vec
, s
->capture_ids
);
1381 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1382 simplifiers
.safe_push (ns
);
1386 /* Return true if O refers to ID. */
1389 contains_id (operand
*o
, user_id
*id
)
1391 if (capture
*c
= dyn_cast
<capture
*> (o
))
1392 return c
->what
&& contains_id (c
->what
, id
);
1394 if (expr
*e
= dyn_cast
<expr
*> (o
))
1396 if (e
->operation
== id
)
1398 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1399 if (contains_id (e
->ops
[i
], id
))
1404 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1405 return (contains_id (w
->with
, id
)
1406 || contains_id (w
->subexpr
, id
));
1408 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1409 return (contains_id (ife
->cond
, id
)
1410 || contains_id (ife
->trueexpr
, id
)
1411 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1413 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1414 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1420 /* In AST operand O replace operator ID with operator WITH. */
1423 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1425 /* Deep-copy captures and expressions, replacing operations as
1427 if (capture
*c
= dyn_cast
<capture
*> (o
))
1431 return new capture (c
->location
, c
->where
,
1432 replace_id (c
->what
, id
, with
), c
->value_match
);
1434 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1436 expr
*ne
= new expr (e
);
1437 if (e
->operation
== id
)
1438 ne
->operation
= with
;
1439 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1440 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1443 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1445 with_expr
*nw
= new with_expr (w
->location
);
1446 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1447 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1450 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1452 if_expr
*nife
= new if_expr (ife
->location
);
1453 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1454 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1456 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1460 /* For c_expr we simply record a string replacement table which is
1461 applied at code-generation time. */
1462 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1464 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1465 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1466 return new c_expr (ce
->r
, ce
->location
,
1467 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1473 /* Return true if the binary operator OP is ok for delayed substitution
1474 during for lowering. */
1477 binary_ok (operator_id
*op
)
1484 case TRUNC_DIV_EXPR
:
1486 case FLOOR_DIV_EXPR
:
1487 case ROUND_DIV_EXPR
:
1488 case TRUNC_MOD_EXPR
:
1490 case FLOOR_MOD_EXPR
:
1491 case ROUND_MOD_EXPR
:
1493 case EXACT_DIV_EXPR
:
1505 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1508 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1510 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1511 unsigned worklist_start
= 0;
1512 auto_vec
<simplify
*> worklist
;
1513 worklist
.safe_push (sin
);
1515 /* Lower each recorded for separately, operating on the
1516 set of simplifiers created by the previous one.
1517 Lower inner-to-outer so inner for substitutes can refer
1518 to operators replaced by outer fors. */
1519 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1521 vec
<user_id
*>& ids
= for_vec
[fi
];
1522 unsigned n_ids
= ids
.length ();
1523 unsigned max_n_opers
= 0;
1524 bool can_delay_subst
= true;
1525 for (unsigned i
= 0; i
< n_ids
; ++i
)
1527 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1528 max_n_opers
= ids
[i
]->substitutes
.length ();
1529 /* Require that all substitutes are of the same kind so that
1530 if we delay substitution to the result op code generation
1531 can look at the first substitute for deciding things like
1532 types of operands. */
1533 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1534 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1535 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1536 can_delay_subst
= false;
1537 else if (operator_id
*op
1538 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1541 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1542 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1543 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1545 /* Unfortunately we can't just allow all tcc_binary. */
1546 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1547 && strcmp (op0
->tcc
, "tcc_binary") == 0
1551 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1552 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1553 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1554 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1557 can_delay_subst
= false;
1559 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1562 can_delay_subst
= false;
1564 if (sin
->kind
== simplify::MATCH
1568 unsigned worklist_end
= worklist
.length ();
1569 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1571 simplify
*s
= worklist
[si
];
1572 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1574 operand
*match_op
= s
->match
;
1575 operand
*result_op
= s
->result
;
1576 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1578 for (unsigned i
= 0; i
< n_ids
; ++i
)
1580 user_id
*id
= ids
[i
];
1581 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1583 && (contains_id (match_op
, id
)
1584 || contains_id (result_op
, id
)))
1589 subst
.quick_push (std::make_pair (id
, oper
));
1590 if (sin
->kind
== simplify::SIMPLIFY
1591 || !can_delay_subst
)
1592 match_op
= replace_id (match_op
, id
, oper
);
1594 && !can_delay_subst
)
1595 result_op
= replace_id (result_op
, id
, oper
);
1600 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1601 vNULL
, s
->capture_ids
);
1602 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1605 ns
->for_subst_vec
.safe_splice (subst
);
1607 worklist
.safe_push (ns
);
1610 worklist_start
= worklist_end
;
1613 /* Copy out the result from the last for lowering. */
1614 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1615 simplifiers
.safe_push (worklist
[i
]);
1618 /* Lower the AST for everything in SIMPLIFIERS. */
1621 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1623 auto_vec
<simplify
*> out_simplifiers
;
1624 for (auto s
: simplifiers
)
1625 lower_opt (s
, out_simplifiers
);
1627 simplifiers
.truncate (0);
1628 for (auto s
: out_simplifiers
)
1629 lower_commutative (s
, simplifiers
);
1631 /* Lower for needs to happen before lowering cond
1632 to support (for cnd (cond vec_cond)). This is
1633 safe as substitution delay does not happen for
1634 cond or vec_cond. */
1635 out_simplifiers
.truncate (0);
1636 for (auto s
: simplifiers
)
1637 lower_for (s
, out_simplifiers
);
1639 simplifiers
.truncate (0);
1641 for (auto s
: out_simplifiers
)
1642 lower_cond (s
, simplifiers
);
1644 simplifiers
.safe_splice (out_simplifiers
);
1650 /* The decision tree built for generating GIMPLE and GENERIC pattern
1651 matching code. It represents the 'match' expression of all
1652 simplifies and has those as its leafs. */
1656 /* A hash-map collecting semantically equivalent leafs in the decision
1657 tree for splitting out to separate functions. */
1666 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1669 static inline hashval_t
hash (const key_type
&);
1670 static inline bool equal_keys (const key_type
&, const key_type
&);
1671 template <typename T
> static inline void remove (T
&) {}
1674 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1677 /* Current simplifier ID we are processing during insertion into the
1679 static unsigned current_id
;
1681 /* Decision tree base class, used for DT_NODE. */
1686 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1691 vec
<dt_node
*> kids
;
1695 unsigned total_size
;
1698 dt_node (enum dt_type type_
, dt_node
*parent_
)
1699 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1701 dt_node
*append_node (dt_node
*);
1702 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1703 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1704 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1706 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1708 virtual void gen (FILE *, int, bool, int) {}
1710 void gen_kids (FILE *, int, bool, int);
1711 void gen_kids_1 (FILE *, int, bool, int,
1712 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1713 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1714 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1716 void analyze (sinfo_map_t
&);
1719 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1721 class dt_operand
: public dt_node
1725 dt_operand
*match_dop
;
1730 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1731 dt_operand
*parent_
, unsigned pos_
)
1732 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1733 pos (pos_
), value_match (false), for_id (current_id
) {}
1735 void gen (FILE *, int, bool, int) final override
;
1736 unsigned gen_predicate (FILE *, int, const char *, bool);
1737 unsigned gen_match_op (FILE *, int, const char *, bool);
1739 unsigned gen_gimple_expr (FILE *, int, int);
1740 unsigned gen_generic_expr (FILE *, int, const char *);
1742 char *get_name (char *);
1743 void gen_opname (char *, unsigned);
1746 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1748 class dt_simplify
: public dt_node
1752 unsigned pattern_no
;
1753 dt_operand
**indexes
;
1756 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1757 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1758 indexes (indexes_
), info (NULL
) {}
1760 void gen_1 (FILE *, int, bool, operand
*);
1761 void gen (FILE *f
, int, bool, int) final override
;
1767 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1769 return (n
->type
== dt_node::DT_OPERAND
1770 || n
->type
== dt_node::DT_MATCH
1771 || n
->type
== dt_node::DT_TRUE
);
1777 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1779 return n
->type
== dt_node::DT_SIMPLIFY
;
1784 /* A container for the actual decision tree. */
1791 void insert (class simplify
*, unsigned);
1792 void gen (vec
<FILE *> &f
, bool gimple
);
1793 void print (FILE *f
= stderr
);
1795 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1797 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1798 unsigned pos
= 0, dt_node
*parent
= 0);
1799 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1800 static bool cmp_node (dt_node
*, dt_node
*);
1801 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1804 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1807 cmp_operand (operand
*o1
, operand
*o2
)
1809 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1812 if (o1
->type
== operand::OP_PREDICATE
)
1814 predicate
*p1
= as_a
<predicate
*>(o1
);
1815 predicate
*p2
= as_a
<predicate
*>(o2
);
1816 return p1
->p
== p2
->p
;
1818 else if (o1
->type
== operand::OP_EXPR
)
1820 expr
*e1
= static_cast<expr
*>(o1
);
1821 expr
*e2
= static_cast<expr
*>(o2
);
1822 return (e1
->operation
== e2
->operation
1823 && e1
->is_generic
== e2
->is_generic
);
1829 /* Compare two decision tree nodes N1 and N2 and return true if they
1833 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1835 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1841 if (n1
->type
== dt_node::DT_TRUE
)
1844 if (n1
->type
== dt_node::DT_OPERAND
)
1845 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1846 (as_a
<dt_operand
*> (n2
))->op
);
1847 else if (n1
->type
== dt_node::DT_MATCH
)
1848 return (((as_a
<dt_operand
*> (n1
))->match_dop
1849 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1850 && ((as_a
<dt_operand
*> (n1
))->value_match
1851 == (as_a
<dt_operand
*> (n2
))->value_match
));
1855 /* Search OPS for a decision tree node like P and return it if found. */
1858 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1860 /* We can merge adjacent DT_TRUE. */
1861 if (p
->type
== dt_node::DT_TRUE
1863 && ops
.last ()->type
== dt_node::DT_TRUE
)
1865 dt_operand
*true_node
= NULL
;
1866 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1868 /* But we can't merge across DT_TRUE nodes as they serve as
1869 pattern order barriers to make sure that patterns apply
1870 in order of appearance in case multiple matches are possible. */
1871 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1874 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1875 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1877 if (decision_tree::cmp_node (ops
[i
], p
))
1879 /* Unless we are processing the same pattern or the blocking
1880 pattern is before the one we are going to merge with. */
1882 && true_node
->for_id
!= current_id
1883 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1887 location_t p_loc
= 0;
1888 if (p
->type
== dt_node::DT_OPERAND
)
1889 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1890 location_t op_loc
= 0;
1891 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1892 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1893 location_t true_loc
= 0;
1894 true_loc
= true_node
->op
->location
;
1896 "failed to merge decision tree node");
1898 "with the following");
1899 warning_at (true_loc
,
1900 "because of the following which serves as ordering "
1911 /* Append N to the decision tree if it there is not already an existing
1915 dt_node::append_node (dt_node
*n
)
1919 kid
= decision_tree::find_node (kids
, n
);
1924 n
->level
= this->level
+ 1;
1929 /* Append OP to the decision tree. */
1932 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1934 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1935 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1936 return append_node (n
);
1939 /* Append a DT_TRUE decision tree node. */
1942 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1944 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1945 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1946 return append_node (n
);
1949 /* Append a DT_MATCH decision tree node. */
1952 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1953 dt_node
*parent
, unsigned pos
)
1955 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1956 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1957 return append_node (n
);
1960 /* Append S to the decision tree. */
1963 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1964 dt_operand
**indexes
)
1967 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1968 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1969 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1971 || s
->match
->location
!= s2
->s
->match
->location
))
1973 /* With a nested patters, it's hard to avoid these in order
1974 to keep match.pd rules relatively small. */
1975 warning_at (s
->match
->location
, "duplicate pattern");
1976 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1977 print_operand (s
->match
, stderr
);
1978 fprintf (stderr
, "\n");
1980 return append_node (n
);
1983 /* Analyze the node and its children. */
1986 dt_node::analyze (sinfo_map_t
&map
)
1992 if (type
== DT_SIMPLIFY
)
1994 /* Populate the map of equivalent simplifies. */
1995 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1997 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
2012 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2014 kids
[i
]->analyze (map
);
2015 num_leafs
+= kids
[i
]->num_leafs
;
2016 total_size
+= kids
[i
]->total_size
;
2017 max_level
= MAX (max_level
, kids
[i
]->max_level
);
2021 /* Insert O into the decision tree and return the decision tree node found
2025 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
2026 unsigned pos
, dt_node
*parent
)
2028 dt_node
*q
, *elm
= 0;
2030 if (capture
*c
= dyn_cast
<capture
*> (o
))
2032 unsigned capt_index
= c
->where
;
2034 if (indexes
[capt_index
] == 0)
2037 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
2040 q
= elm
= p
->append_true_op (o
, parent
, pos
);
2043 // get to the last capture
2044 for (operand
*what
= c
->what
;
2045 what
&& is_a
<capture
*> (what
);
2046 c
= as_a
<capture
*> (what
), what
= c
->what
)
2051 unsigned cc_index
= c
->where
;
2052 dt_operand
*match_op
= indexes
[cc_index
];
2054 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
2055 elm
= decision_tree::find_node (p
->kids
, &temp
);
2059 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
2060 match
.value_match
= c
->value_match
;
2061 elm
= decision_tree::find_node (p
->kids
, &match
);
2066 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
2067 elm
= decision_tree::find_node (p
->kids
, &temp
);
2071 gcc_assert (elm
->type
== dt_node::DT_TRUE
2072 || elm
->type
== dt_node::DT_OPERAND
2073 || elm
->type
== dt_node::DT_MATCH
);
2074 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2079 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2080 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2082 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2087 p
= p
->append_op (o
, parent
, pos
);
2090 if (expr
*e
= dyn_cast
<expr
*>(o
))
2092 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2093 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2099 /* Insert S into the decision tree. */
2102 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2105 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2106 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2107 p
->append_simplify (s
, pattern_no
, indexes
);
2110 /* Debug functions to dump the decision tree. */
2113 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2115 if (p
->type
== dt_node::DT_NODE
)
2116 fprintf (f
, "root");
2120 for (unsigned i
= 0; i
< indent
; i
++)
2123 if (p
->type
== dt_node::DT_OPERAND
)
2125 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2126 print_operand (dop
->op
, f
, true);
2128 else if (p
->type
== dt_node::DT_TRUE
)
2129 fprintf (f
, "true");
2130 else if (p
->type
== dt_node::DT_MATCH
)
2131 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2132 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2134 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2135 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2136 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2137 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2140 if (is_a
<dt_operand
*> (p
))
2141 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2144 fprintf (stderr
, " (%p, %p), %u, %u\n",
2145 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2147 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2148 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2152 decision_tree::print (FILE *f
)
2154 return decision_tree::print_node (root
, f
);
2158 /* For GENERIC we have to take care of wrapping multiple-used
2159 expressions with side-effects in save_expr and preserve side-effects
2160 of expressions with omit_one_operand. Analyze captures in
2161 match, result and with expressions and perform early-outs
2162 on the outermost match expression operands for cases we cannot
2168 capture_info (simplify
*s
, operand
*, bool);
2169 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2170 bool walk_result (operand
*o
, bool, operand
*);
2171 void walk_c_expr (c_expr
*);
2177 bool force_no_side_effects_p
;
2178 bool force_single_use
;
2179 bool cond_expr_cond_p
;
2180 unsigned long toplevel_msk
;
2181 unsigned match_use_count
;
2182 unsigned result_use_count
;
2187 auto_vec
<cinfo
> info
;
2188 unsigned long force_no_side_effects
;
2192 /* Analyze captures in S. */
2194 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2199 if (s
->kind
== simplify::MATCH
)
2201 force_no_side_effects
= -1;
2205 force_no_side_effects
= 0;
2206 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2207 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2208 info
[i
].same_as
= i
;
2210 e
= as_a
<expr
*> (s
->match
);
2211 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2212 walk_match (e
->ops
[i
], i
,
2213 (i
!= 0 && *e
->operation
== COND_EXPR
)
2214 || *e
->operation
== TRUTH_ANDIF_EXPR
2215 || *e
->operation
== TRUTH_ORIF_EXPR
,
2216 i
== 0 && *e
->operation
== COND_EXPR
);
2218 walk_result (s
->result
, false, result
);
2221 /* Analyze captures in the match expression piece O. */
2224 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2225 bool conditional_p
, bool cond_expr_cond_p
)
2227 if (capture
*c
= dyn_cast
<capture
*> (o
))
2229 unsigned where
= c
->where
;
2230 info
[where
].match_use_count
++;
2231 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2232 info
[where
].force_no_side_effects_p
|= conditional_p
;
2233 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2238 /* Recurse to exprs and captures. */
2239 if (is_a
<capture
*> (c
->what
)
2240 || is_a
<expr
*> (c
->what
))
2241 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2242 /* We need to look past multiple captures to find a captured
2243 expression as with conditional converts two captures
2244 can be collapsed onto the same expression. Also collect
2245 what captures capture the same thing. */
2246 while (c
->what
&& is_a
<capture
*> (c
->what
))
2248 c
= as_a
<capture
*> (c
->what
);
2249 if (info
[c
->where
].same_as
!= c
->where
2250 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2251 fatal_at (c
->location
, "cannot handle this collapsed capture");
2252 info
[c
->where
].same_as
= info
[where
].same_as
;
2254 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2257 && (e
= dyn_cast
<expr
*> (c
->what
)))
2259 /* Zero-operand expression captures like ADDR_EXPR@0 are
2260 similar as predicates -- if they are not mentioned in
2261 the result we have to force them to have no side-effects. */
2262 if (e
->ops
.length () != 0)
2263 info
[where
].expr_p
= true;
2264 info
[where
].force_single_use
|= e
->force_single_use
;
2267 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2269 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2271 bool cond_p
= conditional_p
;
2272 bool expr_cond_p
= false;
2273 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2275 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2276 || *e
->operation
== TRUTH_ORIF_EXPR
)
2279 && *e
->operation
== COND_EXPR
)
2281 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2284 else if (is_a
<predicate
*> (o
))
2286 /* Mark non-captured leafs toplevel arg for checking. */
2287 force_no_side_effects
|= 1 << toplevel_arg
;
2290 warning_at (o
->location
,
2291 "forcing no side-effects on possibly lost leaf");
2297 /* Analyze captures in the result expression piece O. Return true
2298 if RESULT was visited in one of the children. Only visit
2299 non-if/with children if they are rooted on RESULT. */
2302 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2304 if (capture
*c
= dyn_cast
<capture
*> (o
))
2306 unsigned where
= info
[c
->where
].same_as
;
2307 info
[where
].result_use_count
++;
2308 /* If we substitute an expression capture we don't know
2309 which captures this will end up using (well, we don't
2310 compute that). Force the uses to be side-effect free
2311 which means forcing the toplevels that reach the
2312 expression side-effect free. */
2313 if (info
[where
].expr_p
)
2314 force_no_side_effects
|= info
[where
].toplevel_msk
;
2315 /* Mark CSE capture uses as forced to have no side-effects. */
2317 && is_a
<expr
*> (c
->what
))
2319 info
[where
].cse_p
= true;
2320 walk_result (c
->what
, true, result
);
2323 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2325 id_base
*opr
= e
->operation
;
2326 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2327 opr
= uid
->substitutes
[0];
2328 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2330 bool cond_p
= conditional_p
;
2331 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2333 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2334 || *e
->operation
== TRUTH_ORIF_EXPR
)
2336 walk_result (e
->ops
[i
], cond_p
, result
);
2339 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2341 /* 'if' conditions should be all fine. */
2342 if (ie
->trueexpr
== result
)
2344 walk_result (ie
->trueexpr
, false, result
);
2347 if (ie
->falseexpr
== result
)
2349 walk_result (ie
->falseexpr
, false, result
);
2353 if (is_a
<if_expr
*> (ie
->trueexpr
)
2354 || is_a
<with_expr
*> (ie
->trueexpr
))
2355 res
|= walk_result (ie
->trueexpr
, false, result
);
2357 && (is_a
<if_expr
*> (ie
->falseexpr
)
2358 || is_a
<with_expr
*> (ie
->falseexpr
)))
2359 res
|= walk_result (ie
->falseexpr
, false, result
);
2362 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2364 bool res
= (we
->subexpr
== result
);
2366 || is_a
<if_expr
*> (we
->subexpr
)
2367 || is_a
<with_expr
*> (we
->subexpr
))
2368 res
|= walk_result (we
->subexpr
, false, result
);
2370 walk_c_expr (we
->with
);
2373 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2381 /* Look for captures in the C expr E. */
2384 capture_info::walk_c_expr (c_expr
*e
)
2386 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2387 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2388 really escape through. */
2389 unsigned p_depth
= 0;
2390 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2392 const cpp_token
*t
= &e
->code
[i
];
2393 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2395 if (t
->type
== CPP_NAME
2396 && (strcmp ((const char *)CPP_HASHNODE
2397 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2398 || strcmp ((const char *)CPP_HASHNODE
2399 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2400 || strcmp ((const char *)CPP_HASHNODE
2401 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2402 || ((id
= get_operator ((const char *)CPP_HASHNODE
2403 (t
->val
.node
.node
)->ident
.str
))
2404 && is_a
<predicate_id
*> (id
)))
2405 && n
->type
== CPP_OPEN_PAREN
)
2407 else if (t
->type
== CPP_CLOSE_PAREN
2410 else if (p_depth
== 0
2411 && t
->type
== CPP_ATSIGN
2412 && (n
->type
== CPP_NUMBER
2413 || n
->type
== CPP_NAME
)
2414 && !(n
->flags
& PREV_WHITE
))
2417 if (n
->type
== CPP_NUMBER
)
2418 id1
= (const char *)n
->val
.str
.text
;
2420 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2421 unsigned *where
= e
->capture_ids
->get(id1
);
2423 fatal_at (n
, "unknown capture id '%s'", id1
);
2424 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2427 warning_at (t
, "capture escapes");
2433 /* The current label failing the current matched pattern during
2435 static char *fail_label
;
2437 /* Code generation off the decision tree and the refered AST nodes. */
2440 is_conversion (id_base
*op
)
2442 return (*op
== CONVERT_EXPR
2444 || *op
== FLOAT_EXPR
2445 || *op
== FIX_TRUNC_EXPR
2446 || *op
== VIEW_CONVERT_EXPR
);
2449 /* Get the type to be used for generating operand POS of OP from the
2453 get_operand_type (id_base
*op
, unsigned pos
,
2454 const char *in_type
,
2455 const char *expr_type
,
2456 const char *other_oprnd_type
)
2458 /* Generally operands whose type does not match the type of the
2459 expression generated need to know their types but match and
2460 thus can fall back to 'other_oprnd_type'. */
2461 if (is_conversion (op
))
2462 return other_oprnd_type
;
2463 else if (*op
== REALPART_EXPR
2464 || *op
== IMAGPART_EXPR
)
2465 return other_oprnd_type
;
2466 else if (is_a
<operator_id
*> (op
)
2467 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2468 return other_oprnd_type
;
2469 else if (*op
== COND_EXPR
2471 return "boolean_type_node";
2472 else if (startswith (op
->id
, "CFN_COND_"))
2474 /* IFN_COND_* operands 1 and later by default have the same type
2475 as the result. The type of operand 0 needs to be specified
2477 if (pos
> 0 && expr_type
)
2479 else if (pos
> 0 && in_type
)
2486 /* Otherwise all types should match - choose one in order of
2493 return other_oprnd_type
;
2497 /* Generate transform code for an expression. */
2500 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2501 int depth
, const char *in_type
, capture_info
*cinfo
,
2502 dt_operand
**indexes
, int)
2504 id_base
*opr
= operation
;
2505 /* When we delay operator substituting during lowering of fors we
2506 make sure that for code-gen purposes the effects of each substitute
2507 are the same. Thus just look at that. */
2508 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2509 opr
= uid
->substitutes
[0];
2511 bool conversion_p
= is_conversion (opr
);
2512 const char *type
= expr_type
;
2515 /* If there was a type specification in the pattern use it. */
2517 else if (conversion_p
)
2518 /* For conversions we need to build the expression using the
2519 outer type passed in. */
2521 else if (*opr
== REALPART_EXPR
2522 || *opr
== IMAGPART_EXPR
)
2524 /* __real and __imag use the component type of its operand. */
2525 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2529 else if (is_a
<operator_id
*> (opr
)
2530 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2532 /* comparisons use boolean_type_node (or what gets in), but
2533 their operands need to figure out the types themselves. */
2538 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2543 else if (*opr
== COND_EXPR
2544 || *opr
== VEC_COND_EXPR
2545 || startswith (opr
->id
, "CFN_COND_"))
2547 /* Conditions are of the same type as their first alternative. */
2548 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2553 /* Other operations are of the same type as their first operand. */
2554 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2558 fatal_at (location
, "cannot determine type of operand");
2560 fprintf_indent (f
, indent
, "{\n");
2562 fprintf_indent (f
, indent
,
2563 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2565 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2566 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2569 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2571 = get_operand_type (opr
, i
, in_type
, expr_type
,
2572 i
== 0 ? NULL
: op0type
);
2573 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2575 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2578 const char *opr_name
;
2579 if (*operation
== CONVERT_EXPR
)
2580 opr_name
= "NOP_EXPR";
2582 opr_name
= operation
->id
;
2586 if (*opr
== CONVERT_EXPR
)
2588 fprintf_indent (f
, indent
,
2589 "if (%s != TREE_TYPE (_o%d[0])\n",
2591 fprintf_indent (f
, indent
,
2592 " && !useless_type_conversion_p (%s, TREE_TYPE "
2595 fprintf_indent (f
, indent
+ 2, "{\n");
2598 /* ??? Building a stmt can fail for various reasons here, seq being
2599 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2600 So if we fail here we should continue matching other patterns. */
2601 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2602 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2603 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2604 fprintf (f
, ", _o%d[%u]", depth
, i
);
2605 fprintf (f
, ");\n");
2606 fprintf_indent (f
, indent
, "tem_op.resimplify (%s, valueize);\n",
2607 !force_leaf
? "lseq" : "NULL");
2608 fprintf_indent (f
, indent
,
2609 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2610 !force_leaf
? "lseq" : "NULL");
2611 fprintf_indent (f
, indent
,
2612 "if (!_r%d) goto %s;\n",
2614 if (*opr
== CONVERT_EXPR
)
2617 fprintf_indent (f
, indent
, " }\n");
2618 fprintf_indent (f
, indent
, "else\n");
2619 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2624 if (*opr
== CONVERT_EXPR
)
2626 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2630 if (opr
->kind
== id_base::CODE
)
2631 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2632 depth
, ops
.length(), opr_name
, type
);
2634 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2635 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2636 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2637 fprintf (f
, ", _o%d[%u]", depth
, i
);
2638 fprintf (f
, ");\n");
2639 if (opr
->kind
!= id_base::CODE
)
2641 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2642 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2646 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2647 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2649 if (*opr
== CONVERT_EXPR
)
2652 fprintf_indent (f
, indent
, "else\n");
2653 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2656 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2658 fprintf_indent (f
, indent
, "}\n");
2661 /* Generate code for a c_expr which is either the expression inside
2662 an if statement or a sequence of statements which computes a
2663 result to be stored to DEST. */
2666 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2667 bool, int, const char *, capture_info
*,
2670 if (dest
&& nr_stmts
== 1)
2671 fprintf_indent (f
, indent
, "%s = ", dest
);
2673 unsigned stmt_nr
= 1;
2675 for (unsigned i
= 0; i
< code
.length (); ++i
)
2677 const cpp_token
*token
= &code
[i
];
2679 /* We can't recover from all lexing losses but we can roughly restore line
2680 breaks from location info. */
2681 const line_map_ordinary
*map
;
2682 linemap_resolve_location (line_table
, token
->src_loc
,
2683 LRK_SPELLING_LOCATION
, &map
);
2684 expanded_location loc
= linemap_expand_location (line_table
, map
,
2686 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2688 prev_line
= loc
.line
;
2690 /* Replace captures for code-gen. */
2691 if (token
->type
== CPP_ATSIGN
)
2693 const cpp_token
*n
= &code
[i
+1];
2694 if ((n
->type
== CPP_NUMBER
2695 || n
->type
== CPP_NAME
)
2696 && !(n
->flags
& PREV_WHITE
))
2698 if (token
->flags
& PREV_WHITE
)
2701 if (n
->type
== CPP_NUMBER
)
2702 id
= (const char *)n
->val
.str
.text
;
2704 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2705 unsigned *cid
= capture_ids
->get (id
);
2707 fatal_at (token
, "unknown capture id");
2708 fprintf (f
, "captures[%u]", *cid
);
2714 if (token
->flags
& PREV_WHITE
)
2717 if (token
->type
== CPP_NAME
)
2719 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2721 for (j
= 0; j
< ids
.length (); ++j
)
2723 if (strcmp (id
, ids
[j
].id
) == 0)
2725 fprintf (f
, "%s", ids
[j
].oper
);
2729 if (j
< ids
.length ())
2733 /* Output the token as string. */
2734 char *tk
= (char *)cpp_token_as_text (r
, token
);
2737 if (token
->type
== CPP_SEMICOLON
)
2740 if (dest
&& stmt_nr
== nr_stmts
)
2741 fprintf_indent (f
, indent
, "%s = ", dest
);
2747 /* Generate transform code for a capture. */
2750 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2751 int depth
, const char *in_type
, capture_info
*cinfo
,
2752 dt_operand
**indexes
, int cond_handling
)
2754 if (what
&& is_a
<expr
*> (what
))
2756 if (indexes
[where
] == 0)
2759 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2760 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2765 /* If in GENERIC some capture is used multiple times, unshare it except
2766 when emitting the last use. */
2768 && cinfo
->info
.exists ()
2769 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2771 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2773 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2776 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2778 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2779 with substituting a capture of that. */
2781 && cond_handling
!= 0
2782 && cinfo
->info
[where
].cond_expr_cond_p
)
2784 /* If substituting into a cond_expr condition, unshare. */
2785 if (cond_handling
== 1)
2786 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2787 /* If substituting elsewhere we might need to decompose it. */
2788 else if (cond_handling
== 2)
2790 /* ??? Returning false here will also not allow any other patterns
2791 to match unless this generator was split out. */
2792 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2793 fprintf_indent (f
, indent
, " {\n");
2794 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2795 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2797 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2798 " TREE_OPERAND (%s, 1));\n",
2799 dest
, dest
, dest
, dest
, dest
);
2800 fprintf_indent (f
, indent
, " }\n");
2805 /* Return the name of the operand representing the decision tree node.
2806 Use NAME as space to generate it. */
2809 dt_operand::get_name (char *name
)
2812 sprintf (name
, "t");
2813 else if (parent
->level
== 1)
2814 sprintf (name
, "_p%u", pos
);
2815 else if (parent
->type
== dt_node::DT_MATCH
)
2816 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2818 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2822 /* Fill NAME with the operand name at position POS. */
2825 dt_operand::gen_opname (char *name
, unsigned pos
)
2828 sprintf (name
, "_p%u", pos
);
2830 sprintf (name
, "_q%u%u", level
, pos
);
2833 /* Generate matching code for the decision tree operand which is
2837 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2839 predicate
*p
= as_a
<predicate
*> (op
);
2841 if (p
->p
->matchers
.exists ())
2843 /* If this is a predicate generated from a pattern mangle its
2844 name and pass on the valueize hook. */
2846 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2849 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2852 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2853 fprintf_indent (f
, indent
+ 2, "{\n");
2857 /* Generate matching code for the decision tree operand which is
2861 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2863 char match_opname
[20];
2864 match_dop
->get_name (match_opname
);
2866 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2867 "|| operand_equal_p (%s, %s, 0))\n",
2868 opname
, match_opname
, opname
, opname
, match_opname
);
2870 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2871 "|| (operand_equal_p (%s, %s, 0) "
2872 "&& types_match (%s, %s)))\n",
2873 opname
, match_opname
, opname
, opname
, match_opname
,
2874 opname
, match_opname
);
2875 fprintf_indent (f
, indent
+ 2, "{\n");
2879 /* Generate GIMPLE matching code for the decision tree operand. */
2882 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2884 expr
*e
= static_cast<expr
*> (op
);
2885 id_base
*id
= e
->operation
;
2886 unsigned n_ops
= e
->ops
.length ();
2887 unsigned n_braces
= 0;
2889 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2890 id
= u
->substitutes
[0];
2892 for (unsigned i
= 0; i
< n_ops
; ++i
)
2894 char child_opname
[20];
2895 gen_opname (child_opname
, i
);
2897 if (id
->kind
== id_base::CODE
)
2900 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2901 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2903 /* ??? If this is a memory operation we can't (and should not)
2904 match this. The only sensible operand types are
2905 SSA names and invariants. */
2910 fprintf_indent (f
, indent
,
2911 "tree %s = TREE_OPERAND (%s, %i);\n",
2912 child_opname
, opname
, i
);
2915 fprintf_indent (f
, indent
,
2916 "tree %s = TREE_OPERAND "
2917 "(gimple_assign_rhs1 (_a%d), %i);\n",
2918 child_opname
, depth
, i
);
2919 fprintf_indent (f
, indent
,
2920 "if ((TREE_CODE (%s) == SSA_NAME\n",
2922 fprintf_indent (f
, indent
,
2923 " || is_gimple_min_invariant (%s)))\n",
2925 fprintf_indent (f
, indent
,
2929 fprintf_indent (f
, indent
,
2930 "%s = do_valueize (valueize, %s);\n",
2931 child_opname
, child_opname
);
2935 fprintf_indent (f
, indent
,
2936 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2937 child_opname
, i
+ 1, depth
);
2940 fprintf_indent (f
, indent
,
2941 "tree %s = gimple_call_arg (_c%d, %u);\n",
2942 child_opname
, depth
, i
);
2943 fprintf_indent (f
, indent
,
2944 "%s = do_valueize (valueize, %s);\n",
2945 child_opname
, child_opname
);
2947 /* While the toplevel operands are canonicalized by the caller
2948 after valueizing operands of sub-expressions we have to
2949 re-canonicalize operand order. */
2950 int opno
= commutative_op (id
);
2953 char child_opname0
[20], child_opname1
[20];
2954 gen_opname (child_opname0
, opno
);
2955 gen_opname (child_opname1
, opno
+ 1);
2956 fprintf_indent (f
, indent
,
2957 "if (tree_swap_operands_p (%s, %s))\n",
2958 child_opname0
, child_opname1
);
2959 fprintf_indent (f
, indent
,
2960 " std::swap (%s, %s);\n",
2961 child_opname0
, child_opname1
);
2967 /* Generate GENERIC matching code for the decision tree operand. */
2970 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2972 expr
*e
= static_cast<expr
*> (op
);
2973 id_base
*id
= e
->operation
;
2974 unsigned n_ops
= e
->ops
.length ();
2976 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2977 id
= u
->substitutes
[0];
2979 for (unsigned i
= 0; i
< n_ops
; ++i
)
2981 char child_opname
[20];
2982 gen_opname (child_opname
, i
);
2984 if (id
->kind
== id_base::CODE
)
2985 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2986 child_opname
, opname
, i
);
2988 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2989 child_opname
, opname
, i
);
2995 /* Generate matching code for the children of the decision tree node. */
2998 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
3000 auto_vec
<dt_operand
*> gimple_exprs
;
3001 auto_vec
<dt_operand
*> generic_exprs
;
3002 auto_vec
<dt_operand
*> fns
;
3003 auto_vec
<dt_operand
*> generic_fns
;
3004 auto_vec
<dt_operand
*> preds
;
3005 auto_vec
<dt_node
*> others
;
3007 for (unsigned i
= 0; i
< kids
.length (); ++i
)
3009 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
3011 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
3012 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
3014 if (e
->ops
.length () == 0
3015 /* In GIMPLE a CONSTRUCTOR always appears in a
3016 separate definition. */
3017 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
3019 generic_exprs
.safe_push (op
);
3020 /* But ADDR_EXPRs can appear directly when invariant
3021 and in a separate definition when not. */
3022 if (gimple
&& *e
->operation
== ADDR_EXPR
)
3023 gimple_exprs
.safe_push (op
);
3025 else if (e
->operation
->kind
== id_base::FN
)
3030 generic_fns
.safe_push (op
);
3032 else if (e
->operation
->kind
== id_base::PREDICATE
)
3033 preds
.safe_push (op
);
3036 user_id
*u
= dyn_cast
<user_id
*> (e
->operation
);
3037 if (u
&& u
->substitutes
[0]->kind
== id_base::FN
)
3042 generic_fns
.safe_push (op
);
3046 if (gimple
&& !e
->is_generic
)
3047 gimple_exprs
.safe_push (op
);
3049 generic_exprs
.safe_push (op
);
3053 else if (op
->op
->type
== operand::OP_PREDICATE
)
3054 others
.safe_push (kids
[i
]);
3058 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
3059 others
.safe_push (kids
[i
]);
3060 else if (kids
[i
]->type
== dt_node::DT_MATCH
3061 || kids
[i
]->type
== dt_node::DT_TRUE
)
3063 /* A DT_TRUE operand serves as a barrier - generate code now
3064 for what we have collected sofar.
3065 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3066 dependent matches to get out-of-order. Generate code now
3067 for what we have collected sofar. */
3068 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3069 fns
, generic_fns
, preds
, others
);
3070 /* And output the true operand itself. */
3071 kids
[i
]->gen (f
, indent
, gimple
, depth
);
3072 gimple_exprs
.truncate (0);
3073 generic_exprs
.truncate (0);
3075 generic_fns
.truncate (0);
3077 others
.truncate (0);
3083 /* Generate code for the remains. */
3084 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3085 fns
, generic_fns
, preds
, others
);
3088 /* Generate matching code for the children of the decision tree node. */
3091 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
3092 const vec
<dt_operand
*> &gimple_exprs
,
3093 const vec
<dt_operand
*> &generic_exprs
,
3094 const vec
<dt_operand
*> &fns
,
3095 const vec
<dt_operand
*> &generic_fns
,
3096 const vec
<dt_operand
*> &preds
,
3097 const vec
<dt_node
*> &others
)
3100 char *kid_opname
= buf
;
3102 unsigned exprs_len
= gimple_exprs
.length ();
3103 unsigned gexprs_len
= generic_exprs
.length ();
3104 unsigned fns_len
= fns
.length ();
3105 unsigned gfns_len
= generic_fns
.length ();
3107 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3110 gimple_exprs
[0]->get_name (kid_opname
);
3112 fns
[0]->get_name (kid_opname
);
3114 generic_fns
[0]->get_name (kid_opname
);
3116 generic_exprs
[0]->get_name (kid_opname
);
3118 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3119 fprintf_indent (f
, indent
, " {\n");
3123 if (exprs_len
|| fns_len
)
3126 fprintf_indent (f
, indent
,
3127 "case SSA_NAME:\n");
3128 fprintf_indent (f
, indent
,
3129 " if (gimple *_d%d = get_def (valueize, %s))\n",
3131 fprintf_indent (f
, indent
,
3136 fprintf_indent (f
, indent
,
3137 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3139 fprintf_indent (f
, indent
,
3140 " switch (gimple_assign_rhs_code (_a%d))\n",
3143 fprintf_indent (f
, indent
, "{\n");
3144 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3146 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3147 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3149 for (auto id
: u
->substitutes
)
3150 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3154 id_base
*op
= e
->operation
;
3155 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3156 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3158 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3160 fprintf_indent (f
, indent
, " {\n");
3161 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3162 fprintf_indent (f
, indent
, " break;\n");
3163 fprintf_indent (f
, indent
, " }\n");
3165 fprintf_indent (f
, indent
, "default:;\n");
3166 fprintf_indent (f
, indent
, "}\n");
3172 fprintf_indent (f
, indent
,
3173 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3174 exprs_len
? "else " : "", depth
, depth
);
3175 fprintf_indent (f
, indent
,
3176 " switch (gimple_call_combined_fn (_c%d))\n",
3180 fprintf_indent (f
, indent
, "{\n");
3181 for (unsigned i
= 0; i
< fns_len
; ++i
)
3183 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3184 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3185 for (auto id
: u
->substitutes
)
3186 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3188 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3189 /* We need to be defensive against bogus prototypes allowing
3190 calls with not enough arguments. */
3191 fprintf_indent (f
, indent
,
3192 " if (gimple_call_num_args (_c%d) == %d)\n",
3193 depth
, e
->ops
.length ());
3194 fprintf_indent (f
, indent
, " {\n");
3195 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3196 fprintf_indent (f
, indent
, " }\n");
3197 fprintf_indent (f
, indent
, " break;\n");
3200 fprintf_indent (f
, indent
, "default:;\n");
3201 fprintf_indent (f
, indent
, "}\n");
3207 fprintf_indent (f
, indent
, " }\n");
3208 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3209 here rather than in the next loop. */
3210 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3212 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3213 id_base
*op
= e
->operation
;
3214 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3216 fprintf_indent (f
, indent
+ 4, "{\n");
3217 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3218 fprintf_indent (f
, indent
+ 4, "}\n");
3222 fprintf_indent (f
, indent
, " break;\n");
3225 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3227 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3228 id_base
*op
= e
->operation
;
3229 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3230 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3231 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3232 /* Already handled above. */
3236 if (user_id
*u
= dyn_cast
<user_id
*> (op
))
3237 for (auto id
: u
->substitutes
)
3238 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3240 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3242 fprintf_indent (f
, indent
, " {\n");
3243 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3244 fprintf_indent (f
, indent
, " break;\n");
3245 fprintf_indent (f
, indent
, " }\n");
3250 fprintf_indent (f
, indent
,
3251 "case CALL_EXPR:\n");
3252 fprintf_indent (f
, indent
,
3253 " switch (get_call_combined_fn (%s))\n",
3255 fprintf_indent (f
, indent
,
3259 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3261 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3262 gcc_assert (e
->operation
->kind
== id_base::FN
);
3264 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3265 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3266 " {\n", kid_opname
, e
->ops
.length ());
3267 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3268 fprintf_indent (f
, indent
, " }\n"
3271 fprintf_indent (f
, indent
, "default:;\n");
3274 fprintf_indent (f
, indent
, " }\n");
3275 fprintf_indent (f
, indent
, " break;\n");
3278 /* Close switch (TREE_CODE ()). */
3279 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3282 fprintf_indent (f
, indent
, " default:;\n");
3283 fprintf_indent (f
, indent
, " }\n");
3286 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3288 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3289 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3290 preds
[i
]->get_name (kid_opname
);
3291 fprintf_indent (f
, indent
, "{\n");
3293 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3294 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3295 gimple
? "gimple" : "tree",
3296 p
->id
, kid_opname
, kid_opname
,
3297 gimple
? ", valueize" : "");
3298 fprintf_indent (f
, indent
, " {\n");
3299 for (int j
= 0; j
< p
->nargs
; ++j
)
3301 char child_opname
[20];
3302 preds
[i
]->gen_opname (child_opname
, j
);
3303 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3304 child_opname
, kid_opname
, j
);
3306 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3309 fprintf_indent (f
, indent
, "}\n");
3312 for (unsigned i
= 0; i
< others
.length (); ++i
)
3313 others
[i
]->gen (f
, indent
, gimple
, depth
);
3316 /* Generate matching code for the decision tree operand. */
3319 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3324 unsigned n_braces
= 0;
3326 if (type
== DT_OPERAND
)
3329 case operand::OP_PREDICATE
:
3330 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3333 case operand::OP_EXPR
:
3335 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3337 n_braces
= gen_generic_expr (f
, indent
, opname
);
3343 else if (type
== DT_TRUE
)
3345 else if (type
== DT_MATCH
)
3346 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3350 indent
+= 4 * n_braces
;
3351 gen_kids (f
, indent
, gimple
, depth
);
3353 for (unsigned i
= 0; i
< n_braces
; ++i
)
3358 fprintf_indent (f
, indent
, " }\n");
3362 /* Emit a fprintf to the debug file to the file F, with the INDENT from
3363 either the RESULT location or the S's match location if RESULT is null. */
3365 emit_debug_printf (FILE *f
, int indent
, class simplify
*s
, operand
*result
)
3367 fprintf_indent (f
, indent
, "if (UNLIKELY (debug_dump)) "
3368 "fprintf (dump_file, \"%s ",
3369 s
->kind
== simplify::SIMPLIFY
3370 ? "Applying pattern" : "Matching expression");
3371 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3372 output_line_directive (f
,
3373 result
? result
->location
: s
->match
->location
, true,
3375 fprintf (f
, ", __FILE__, __LINE__);\n");
3378 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3379 step of a '(simplify ...)' or '(match ...)'. This handles everything
3380 that is not part of the decision tree (simplify->match).
3381 Main recursive worker. */
3384 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3388 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3390 fprintf_indent (f
, indent
, "{\n");
3392 output_line_directive (f
, w
->location
);
3393 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3394 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3396 fprintf_indent (f
, indent
, "}\n");
3399 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3401 output_line_directive (f
, ife
->location
);
3402 fprintf_indent (f
, indent
, "if (");
3403 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3405 fprintf_indent (f
, indent
+ 2, "{\n");
3407 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3409 fprintf_indent (f
, indent
+ 2, "}\n");
3412 fprintf_indent (f
, indent
, "else\n");
3413 fprintf_indent (f
, indent
+ 2, "{\n");
3415 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3417 fprintf_indent (f
, indent
+ 2, "}\n");
3423 static unsigned fail_label_cnt
;
3424 char local_fail_label
[256];
3425 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3426 fail_label
= local_fail_label
;
3427 bool needs_label
= false;
3429 /* Analyze captures and perform early-outs on the incoming arguments
3430 that cover cases we cannot handle. */
3431 capture_info
cinfo (s
, result
, gimple
);
3432 if (s
->kind
== simplify::SIMPLIFY
)
3436 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3437 if (cinfo
.force_no_side_effects
& (1 << i
))
3439 fprintf_indent (f
, indent
,
3440 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3444 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3445 "forcing toplevel operand to have no "
3448 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3449 if (cinfo
.info
[i
].cse_p
)
3451 else if (cinfo
.info
[i
].force_no_side_effects_p
3452 && (cinfo
.info
[i
].toplevel_msk
3453 & cinfo
.force_no_side_effects
) == 0)
3455 fprintf_indent (f
, indent
,
3456 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3457 "goto %s;\n", i
, fail_label
);
3460 warning_at (cinfo
.info
[i
].c
->location
,
3461 "forcing captured operand to have no "
3464 else if ((cinfo
.info
[i
].toplevel_msk
3465 & cinfo
.force_no_side_effects
) != 0)
3466 /* Mark capture as having no side-effects if we had to verify
3467 that via forced toplevel operand checks. */
3468 cinfo
.info
[i
].force_no_side_effects_p
= true;
3472 /* Force single-use restriction by only allowing simple
3473 results via setting seq to NULL. */
3474 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3475 bool first_p
= true;
3476 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3477 if (cinfo
.info
[i
].force_single_use
)
3481 fprintf_indent (f
, indent
, "if (lseq\n");
3482 fprintf_indent (f
, indent
, " && (");
3488 fprintf_indent (f
, indent
, " || ");
3490 fprintf (f
, "!single_use (captures[%d])", i
);
3494 fprintf (f
, "))\n");
3495 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3500 if (s
->kind
== simplify::SIMPLIFY
)
3502 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3506 fprintf_indent (f
, indent
, "{\n");
3510 /* If there is no result then this is a predicate implementation. */
3511 emit_debug_printf (f
, indent
, s
, result
);
3512 fprintf_indent (f
, indent
, "return true;\n");
3516 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3517 in outermost position). */
3518 if (result
->type
== operand::OP_EXPR
3519 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3520 result
= as_a
<expr
*> (result
)->ops
[0];
3521 if (result
->type
== operand::OP_EXPR
)
3523 expr
*e
= as_a
<expr
*> (result
);
3524 id_base
*opr
= e
->operation
;
3525 bool is_predicate
= false;
3526 /* When we delay operator substituting during lowering of fors we
3527 make sure that for code-gen purposes the effects of each substitute
3528 are the same. Thus just look at that. */
3529 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3530 opr
= uid
->substitutes
[0];
3531 else if (is_a
<predicate_id
*> (opr
))
3532 is_predicate
= true;
3534 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3535 *e
->operation
== CONVERT_EXPR
3536 ? "NOP_EXPR" : e
->operation
->id
,
3538 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3542 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3544 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3546 = get_operand_type (opr
, j
,
3547 "type", e
->expr_type
,
3549 : "TREE_TYPE (res_op->ops[0])");
3550 /* We need to expand GENERIC conditions we captured from
3551 COND_EXPRs and we need to unshare them when substituting
3553 int cond_handling
= 0;
3555 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3556 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3557 &cinfo
, indexes
, cond_handling
);
3560 /* Re-fold the toplevel result. It's basically an embedded
3561 gimple_build w/o actually building the stmt. */
3564 fprintf_indent (f
, indent
,
3565 "res_op->resimplify (%s, valueize);\n",
3566 !e
->force_leaf
? "lseq" : "NULL");
3569 fprintf_indent (f
, indent
,
3570 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3571 "goto %s;\n", fail_label
);
3576 else if (result
->type
== operand::OP_CAPTURE
3577 || result
->type
== operand::OP_C_EXPR
)
3579 fprintf_indent (f
, indent
, "tree tem;\n");
3580 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3582 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3583 if (is_a
<capture
*> (result
)
3584 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3586 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3587 with substituting a capture of that. */
3588 fprintf_indent (f
, indent
,
3589 "if (COMPARISON_CLASS_P (tem))\n");
3590 fprintf_indent (f
, indent
,
3592 fprintf_indent (f
, indent
,
3593 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3594 fprintf_indent (f
, indent
,
3595 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3596 fprintf_indent (f
, indent
,
3602 emit_debug_printf (f
, indent
, s
, result
);
3603 fprintf_indent (f
, indent
, "return true;\n");
3607 bool is_predicate
= false;
3608 if (result
->type
== operand::OP_EXPR
)
3610 expr
*e
= as_a
<expr
*> (result
);
3611 id_base
*opr
= e
->operation
;
3612 /* When we delay operator substituting during lowering of fors we
3613 make sure that for code-gen purposes the effects of each substitute
3614 are the same. Thus just look at that. */
3615 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3616 opr
= uid
->substitutes
[0];
3617 else if (is_a
<predicate_id
*> (opr
))
3618 is_predicate
= true;
3619 /* Search for captures used multiple times in the result expression
3620 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3621 original expression. */
3623 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3625 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3626 || cinfo
.info
[i
].cse_p
)
3628 if (cinfo
.info
[i
].result_use_count
3629 > cinfo
.info
[i
].match_use_count
)
3631 fprintf_indent (f
, indent
,
3632 "if (! tree_invariant_p (captures[%d])) "
3633 "goto %s;\n", i
, fail_label
);
3637 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3641 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3644 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3645 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3648 = get_operand_type (opr
, j
,
3649 "type", e
->expr_type
,
3651 ? NULL
: "TREE_TYPE (res_op0)");
3652 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3657 emit_debug_printf (f
, indent
, s
, result
);
3658 fprintf_indent (f
, indent
, "return true;\n");
3662 fprintf_indent (f
, indent
, "tree _r;\n");
3663 /* Re-fold the toplevel result. Use non_lvalue to
3664 build NON_LVALUE_EXPRs so they get properly
3665 ignored when in GIMPLE form. */
3666 if (*opr
== NON_LVALUE_EXPR
)
3667 fprintf_indent (f
, indent
,
3668 "_r = non_lvalue_loc (loc, res_op0);\n");
3671 if (is_a
<operator_id
*> (opr
))
3672 fprintf_indent (f
, indent
,
3673 "_r = fold_build%d_loc (loc, %s, type",
3675 *e
->operation
== CONVERT_EXPR
3676 ? "NOP_EXPR" : e
->operation
->id
);
3678 fprintf_indent (f
, indent
,
3679 "_r = maybe_build_call_expr_loc (loc, "
3680 "%s, type, %d", e
->operation
->id
,
3682 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3683 fprintf (f
, ", res_op%d", j
);
3684 fprintf (f
, ");\n");
3685 if (!is_a
<operator_id
*> (opr
))
3687 fprintf_indent (f
, indent
, "if (!_r)\n");
3688 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3694 else if (result
->type
== operand::OP_CAPTURE
3695 || result
->type
== operand::OP_C_EXPR
)
3698 fprintf_indent (f
, indent
, "tree _r;\n");
3699 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3706 /* Search for captures not used in the result expression and dependent
3707 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3708 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3710 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3712 if (!cinfo
.info
[i
].force_no_side_effects_p
3713 && !cinfo
.info
[i
].expr_p
3714 && cinfo
.info
[i
].result_use_count
== 0)
3716 fprintf_indent (f
, indent
,
3717 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3719 fprintf_indent (f
, indent
+ 2,
3720 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3721 "fold_ignored_result (captures[%d]), _r);\n",
3725 emit_debug_printf (f
, indent
, s
, result
);
3726 fprintf_indent (f
, indent
, "return _r;\n");
3730 fprintf_indent (f
, indent
, "}\n");
3732 fprintf (f
, "%s:;\n", fail_label
);
3736 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3737 step of a '(simplify ...)' or '(match ...)'. This handles everything
3738 that is not part of the decision tree (simplify->match). */
3741 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3743 fprintf_indent (f
, indent
, "{\n");
3745 output_line_directive (f
,
3746 s
->result
? s
->result
->location
: s
->match
->location
);
3747 if (s
->capture_max
>= 0)
3750 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3751 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3753 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3757 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3759 fprintf (f
, " };\n");
3762 /* If we have a split-out function for the actual transform, call it. */
3763 if (info
&& info
->fname
)
3767 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3768 "valueize, type, captures", info
->fname
);
3769 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3770 if (s
->for_subst_vec
[i
].first
->used
)
3771 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3772 fprintf (f
, "))\n");
3773 fprintf_indent (f
, indent
, " return true;\n");
3777 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3779 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3780 fprintf (f
, ", _p%d", i
);
3781 fprintf (f
, ", captures");
3782 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3784 if (s
->for_subst_vec
[i
].first
->used
)
3785 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3787 fprintf (f
, ");\n");
3788 fprintf_indent (f
, indent
, "if (res) return res;\n");
3793 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3795 if (! s
->for_subst_vec
[i
].first
->used
)
3797 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3798 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3799 s
->for_subst_vec
[i
].first
->id
,
3800 s
->for_subst_vec
[i
].second
->id
);
3801 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3802 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3803 s
->for_subst_vec
[i
].first
->id
,
3804 s
->for_subst_vec
[i
].second
->id
);
3808 gen_1 (f
, indent
, gimple
, s
->result
);
3812 fprintf_indent (f
, indent
, "}\n");
3816 /* Hash function for finding equivalent transforms. */
3819 sinfo_hashmap_traits::hash (const key_type
&v
)
3821 /* Only bother to compare those originating from the same source pattern. */
3822 return v
->s
->result
->location
;
3825 /* Compare function for finding equivalent transforms. */
3828 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3830 if (o1
->type
!= o2
->type
)
3835 case operand::OP_IF
:
3837 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3838 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3839 /* ??? Properly compare c-exprs. */
3840 if (if1
->cond
!= if2
->cond
)
3842 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3844 if (if1
->falseexpr
!= if2
->falseexpr
3846 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3850 case operand::OP_WITH
:
3852 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3853 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3854 if (with1
->with
!= with2
->with
)
3856 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3861 /* We've hit a result. Time to compare capture-infos - this is required
3862 in addition to the conservative pointer-equivalency of the result IL. */
3863 capture_info
cinfo1 (s1
, o1
, true);
3864 capture_info
cinfo2 (s2
, o2
, true);
3866 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3867 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3870 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3872 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3873 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3874 || (cinfo1
.info
[i
].force_no_side_effects_p
3875 != cinfo2
.info
[i
].force_no_side_effects_p
)
3876 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3877 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3878 /* toplevel_msk is an optimization */
3879 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3880 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3881 /* the pointer back to the capture is for diagnostics only */)
3885 /* ??? Deep-compare the actual result. */
3890 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3891 const key_type
&candidate
)
3893 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3897 /* Main entry to generate code for matching GIMPLE IL off the decision
3901 decision_tree::gen (vec
<FILE *> &files
, bool gimple
)
3907 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3908 "a total number of %u nodes\n",
3909 gimple
? "GIMPLE" : "GENERIC",
3910 root
->num_leafs
, root
->max_level
, root
->total_size
);
3912 /* First split out the transform part of equal leafs. */
3915 for (sinfo_map_t::iterator iter
= si
.begin ();
3916 iter
!= si
.end (); ++iter
)
3918 sinfo
*s
= (*iter
).second
;
3919 /* Do not split out single uses. */
3926 fprintf (stderr
, "found %u uses of", s
->cnt
);
3927 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3930 /* Cycle the file buffers. */
3931 FILE *f
= choose_output (files
);
3933 /* Generate a split out function with the leaf transform code. */
3934 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3937 fp_decl (f
, "\nbool\n"
3938 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3939 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3940 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3945 fp_decl (f
, "\ntree\n"
3946 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3947 (*iter
).second
->fname
);
3948 for (unsigned i
= 0;
3949 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3950 fp_decl (f
, " tree ARG_UNUSED (_p%d),", i
);
3951 fp_decl (f
, " tree *captures");
3953 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3955 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3957 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3958 fp_decl (f
, ",\n const enum tree_code ARG_UNUSED (%s)",
3959 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3960 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3961 fp_decl (f
, ",\n const combined_fn ARG_UNUSED (%s)",
3962 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3965 fp_decl_done (f
, ")");
3967 fprintf_indent (f
, 2, "const bool debug_dump = "
3968 "dump_file && (dump_flags & TDF_FOLDING);\n");
3969 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3971 fprintf (f
, " return false;\n");
3973 fprintf (f
, " return NULL_TREE;\n");
3976 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3978 for (unsigned n
= 1; n
<= 5; ++n
)
3980 bool has_kids_p
= false;
3982 /* First generate split-out functions. */
3983 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3985 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3986 expr
*e
= static_cast<expr
*>(dop
->op
);
3987 if (e
->ops
.length () != n
3988 /* Builtin simplifications are somewhat premature on
3989 GENERIC. The following drops patterns with outermost
3990 calls. It's easy to emit overloads for function code
3991 though if necessary. */
3993 && e
->operation
->kind
!= id_base::CODE
))
3997 /* Cycle the file buffers. */
3998 FILE *f
= choose_output (files
);
4001 fp_decl (f
, "\nbool\n"
4002 "gimple_simplify_%s (gimple_match_op *res_op,"
4003 " gimple_seq *seq,\n"
4004 " tree (*valueize)(tree) "
4005 "ATTRIBUTE_UNUSED,\n"
4006 " code_helper ARG_UNUSED (code), tree "
4007 "ARG_UNUSED (type)",
4010 fp_decl (f
, "\ntree\n"
4011 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
4012 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
4014 for (unsigned i
= 0; i
< n
; ++i
)
4015 fp_decl (f
, ", tree _p%d", i
);
4016 fp_decl_done (f
, ")");
4018 fprintf_indent (f
, 2, "const bool debug_dump = "
4019 "dump_file && (dump_flags & TDF_FOLDING);\n");
4020 dop
->gen_kids (f
, 2, gimple
, 0);
4022 fprintf (f
, " return false;\n");
4024 fprintf (f
, " return NULL_TREE;\n");
4029 /* If this main entry has no children, avoid generating code
4030 with compiler warnings, by generating a simple stub. */
4034 /* Cycle the file buffers. */
4035 FILE *f
= choose_output (files
);
4038 fp_decl (f
, "\nbool\n"
4039 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
4040 " tree (*)(tree), code_helper,\n"
4043 fp_decl (f
, "\ntree\n"
4044 "generic_simplify (location_t, enum tree_code,\n"
4046 for (unsigned i
= 0; i
< n
; ++i
)
4047 fp_decl (f
, ", tree");
4048 fp_decl_done (f
, ")");
4051 fprintf (f
, " return false;\n");
4053 fprintf (f
, " return NULL_TREE;\n");
4059 /* Cycle the file buffers. */
4060 FILE *f
= choose_output (files
);
4062 /* Then generate the main entry with the outermost switch and
4063 tail-calls to the split-out functions. */
4065 fp_decl (f
, "\nbool\n"
4066 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
4067 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4068 " code_helper code, const tree type");
4070 fp_decl (f
, "\ntree\n"
4071 "generic_simplify (location_t loc, enum tree_code code, "
4072 "const tree type ATTRIBUTE_UNUSED");
4073 for (unsigned i
= 0; i
< n
; ++i
)
4074 fp_decl (f
, ", tree _p%d", i
);
4075 fp_decl_done (f
, ")");
4079 fprintf (f
, " switch (code.get_rep())\n"
4082 fprintf (f
, " switch (code)\n"
4084 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
4086 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
4087 expr
*e
= static_cast<expr
*>(dop
->op
);
4088 if (e
->ops
.length () != n
4089 /* Builtin simplifications are somewhat premature on
4090 GENERIC. The following drops patterns with outermost
4091 calls. It's easy to emit overloads for function code
4092 though if necessary. */
4094 && e
->operation
->kind
!= id_base::CODE
))
4097 if (*e
->operation
== CONVERT_EXPR
4098 || *e
->operation
== NOP_EXPR
)
4099 fprintf (f
, " CASE_CONVERT:\n");
4101 fprintf (f
, " case %s%s:\n",
4102 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
4105 fprintf (f
, " return gimple_simplify_%s (res_op, "
4106 "seq, valueize, code, type", e
->operation
->id
);
4108 fprintf (f
, " return generic_simplify_%s (loc, code, type",
4110 for (unsigned j
= 0; j
< n
; ++j
)
4111 fprintf (f
, ", _p%d", j
);
4112 fprintf (f
, ");\n");
4114 fprintf (f
, " default:;\n"
4118 fprintf (f
, " return false;\n");
4120 fprintf (f
, " return NULL_TREE;\n");
4125 /* Output code to implement the predicate P from the decision tree DT. */
4128 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
4130 fp_decl (f
, "\nbool\n%s%s (tree t%s%s)",
4131 gimple
? "gimple_" : "tree_", p
->id
,
4132 p
->nargs
> 0 ? ", tree *res_ops" : "",
4133 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4134 fp_decl_done (f
, "");
4136 /* Conveniently make 'type' available. */
4137 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
4138 fprintf_indent (f
, 2, "const bool debug_dump = "
4139 "dump_file && (dump_flags & TDF_FOLDING);\n");
4142 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4143 dt
.root
->gen_kids (f
, 2, gimple
, 0);
4145 fprintf_indent (f
, 2, "return false;\n"
4149 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4152 write_header (FILE *f
, const char *head
)
4154 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4155 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4156 fprintf (f
, "#pragma GCC diagnostic push\n");
4157 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-variable\"\n");
4158 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-function\"\n");
4160 /* Include the header instead of writing it awkwardly quoted here. */
4162 fprintf (f
, "\n#include \"%s\"\n", head
);
4172 parser (cpp_reader
*, bool gimple
);
4175 const cpp_token
*next ();
4176 const cpp_token
*peek (unsigned = 1);
4177 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4178 const cpp_token
*expect (enum cpp_ttype
);
4179 const cpp_token
*eat_token (enum cpp_ttype
);
4180 const char *get_string ();
4181 const char *get_ident ();
4182 const cpp_token
*eat_ident (const char *);
4183 const char *get_number ();
4185 unsigned get_internal_capture_id ();
4187 id_base
*parse_operation (unsigned char &);
4188 operand
*parse_capture (operand
*, bool);
4189 operand
*parse_expr ();
4190 c_expr
*parse_c_expr (cpp_ttype
);
4191 operand
*parse_op ();
4193 void record_operlist (location_t
, user_id
*);
4195 void parse_pattern ();
4196 operand
*parse_result (operand
*, predicate_id
*);
4197 void push_simplify (simplify::simplify_kind
,
4198 vec
<simplify
*>&, operand
*, operand
*);
4199 void parse_simplify (simplify::simplify_kind
,
4200 vec
<simplify
*>&, predicate_id
*, operand
*);
4201 void parse_for (location_t
);
4202 void parse_if (location_t
);
4203 void parse_predicates (location_t
);
4204 void parse_operator_list (location_t
);
4206 void finish_match_operand (operand
*);
4210 vec
<c_expr
*> active_ifs
;
4211 vec
<vec
<user_id
*> > active_fors
;
4212 hash_set
<user_id
*> *oper_lists_set
;
4213 vec
<user_id
*> oper_lists
;
4215 cid_map_t
*capture_ids
;
4219 vec
<simplify
*> simplifiers
;
4220 vec
<predicate_id
*> user_predicates
;
4221 bool parsing_match_operand
;
4224 /* Lexing helpers. */
4226 /* Read the next non-whitespace token from R. */
4231 const cpp_token
*token
;
4234 token
= cpp_get_token (r
);
4236 while (token
->type
== CPP_PADDING
);
4240 /* Peek at the next non-whitespace token from R. */
4243 parser::peek (unsigned num
)
4245 const cpp_token
*token
;
4249 token
= cpp_peek_token (r
, i
++);
4251 while (token
->type
== CPP_PADDING
4253 /* If we peek at EOF this is a fatal error as it leaves the
4254 cpp_reader in unusable state. Assume we really wanted a
4255 token and thus this EOF is unexpected. */
4256 if (token
->type
== CPP_EOF
)
4257 fatal_at (token
, "unexpected end of file");
4261 /* Peek at the next identifier token (or return NULL if the next
4262 token is not an identifier or equal to ID if supplied). */
4265 parser::peek_ident (const char *id
, unsigned num
)
4267 const cpp_token
*token
= peek (num
);
4268 if (token
->type
!= CPP_NAME
)
4274 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4275 if (strcmp (id
, t
) == 0)
4281 /* Read the next token from R and assert it is of type TK. */
4284 parser::expect (enum cpp_ttype tk
)
4286 const cpp_token
*token
= next ();
4287 if (token
->type
!= tk
)
4288 fatal_at (token
, "expected %s, got %s",
4289 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4294 /* Consume the next token from R and assert it is of type TK. */
4297 parser::eat_token (enum cpp_ttype tk
)
4302 /* Read the next token from R and assert it is of type CPP_STRING and
4303 return its value. */
4306 parser::get_string ()
4308 const cpp_token
*token
= expect (CPP_STRING
);
4309 return (const char *)token
->val
.str
.text
;
4312 /* Read the next token from R and assert it is of type CPP_NAME and
4313 return its value. */
4316 parser::get_ident ()
4318 const cpp_token
*token
= expect (CPP_NAME
);
4319 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4322 /* Eat an identifier token with value S from R. */
4325 parser::eat_ident (const char *s
)
4327 const cpp_token
*token
= peek ();
4328 const char *t
= get_ident ();
4329 if (strcmp (s
, t
) != 0)
4330 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4334 /* Read the next token from R and assert it is of type CPP_NUMBER and
4335 return its value. */
4338 parser::get_number ()
4340 const cpp_token
*token
= expect (CPP_NUMBER
);
4341 return (const char *)token
->val
.str
.text
;
4344 /* Return a capture ID that can be used internally. */
4347 parser::get_internal_capture_id ()
4349 unsigned newid
= capture_ids
->elements ();
4350 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4353 snprintf (id
, sizeof (id
), "__%u", newid
);
4354 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4356 fatal ("reserved capture id '%s' already used", id
);
4360 /* Record an operator-list use for transparent for handling. */
4363 parser::record_operlist (location_t loc
, user_id
*p
)
4365 if (!oper_lists_set
->add (p
))
4367 if (!oper_lists
.is_empty ()
4368 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4369 fatal_at (loc
, "User-defined operator list does not have the "
4370 "same number of entries as others used in the pattern");
4371 oper_lists
.safe_push (p
);
4375 /* Parse the operator ID, special-casing convert?, convert1? and
4379 parser::parse_operation (unsigned char &opt_grp
)
4381 const cpp_token
*id_tok
= peek ();
4382 char *alt_id
= NULL
;
4383 const char *id
= get_ident ();
4384 const cpp_token
*token
= peek ();
4386 if (token
->type
== CPP_QUERY
4387 && !(token
->flags
& PREV_WHITE
))
4389 if (!parsing_match_operand
)
4390 fatal_at (id_tok
, "conditional convert can only be used in "
4391 "match expression");
4392 if (ISDIGIT (id
[strlen (id
) - 1]))
4394 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4395 alt_id
= xstrdup (id
);
4396 alt_id
[strlen (id
) - 1] = '\0';
4398 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4402 eat_token (CPP_QUERY
);
4404 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4406 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4409 user_id
*p
= dyn_cast
<user_id
*> (op
);
4410 if (p
&& p
->is_oper_list
)
4412 if (active_fors
.length() == 0)
4413 record_operlist (id_tok
->src_loc
, p
);
4415 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4421 capture = '@'<number> */
4424 parser::parse_capture (operand
*op
, bool require_existing
)
4426 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4427 const cpp_token
*token
= peek ();
4428 const char *id
= NULL
;
4429 bool value_match
= false;
4430 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4431 if (token
->type
== CPP_ATSIGN
4432 && ! (token
->flags
& PREV_WHITE
)
4433 && parsing_match_operand
)
4435 eat_token (CPP_ATSIGN
);
4439 if (token
->type
== CPP_NUMBER
)
4441 else if (token
->type
== CPP_NAME
)
4444 fatal_at (token
, "expected number or identifier");
4445 unsigned next_id
= capture_ids
->elements ();
4447 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4450 if (require_existing
)
4451 fatal_at (src_loc
, "unknown capture id");
4454 return new capture (src_loc
, num
, op
, value_match
);
4457 /* Parse an expression
4458 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4461 parser::parse_expr ()
4463 const cpp_token
*token
= peek ();
4464 unsigned char opt_grp
;
4465 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4468 bool is_commutative
= false;
4469 bool force_capture
= false;
4470 const char *expr_type
= NULL
;
4472 if (!parsing_match_operand
4473 && token
->type
== CPP_NOT
4474 && !(token
->flags
& PREV_WHITE
))
4476 eat_token (CPP_NOT
);
4477 e
->force_leaf
= true;
4480 if (token
->type
== CPP_COLON
4481 && !(token
->flags
& PREV_WHITE
))
4483 eat_token (CPP_COLON
);
4485 if (token
->type
== CPP_NAME
4486 && !(token
->flags
& PREV_WHITE
))
4488 const char *s
= get_ident ();
4489 if (!parsing_match_operand
)
4499 = dyn_cast
<operator_id
*> (e
->operation
))
4501 if (!commutative_tree_code (o
->code
)
4502 && !comparison_code_p (o
->code
))
4503 fatal_at (token
, "operation is not commutative");
4505 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4506 for (unsigned i
= 0;
4507 i
< p
->substitutes
.length (); ++i
)
4510 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4512 if (!commutative_tree_code (q
->code
)
4513 && !comparison_code_p (q
->code
))
4514 fatal_at (token
, "operation %s is not "
4515 "commutative", q
->id
);
4518 is_commutative
= true;
4520 else if (*sp
== 'C')
4521 is_commutative
= true;
4522 else if (*sp
== 's')
4524 e
->force_single_use
= true;
4525 force_capture
= true;
4528 fatal_at (token
, "flag %c not recognized", *sp
);
4535 fatal_at (token
, "expected flag or type specifying identifier");
4538 if (token
->type
== CPP_ATSIGN
4539 && !(token
->flags
& PREV_WHITE
))
4540 op
= parse_capture (e
, false);
4541 else if (force_capture
)
4543 unsigned num
= get_internal_capture_id ();
4544 op
= new capture (token
->src_loc
, num
, e
, false);
4551 if (token
->type
== CPP_CLOSE_PAREN
)
4553 if (e
->operation
->nargs
!= -1
4554 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4555 fatal_at (token
, "'%s' expects %u operands, not %u",
4556 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4559 if (e
->ops
.length () == 2
4560 || commutative_op (e
->operation
) >= 0)
4561 e
->is_commutative
= true;
4563 fatal_at (token
, "only binary operators or functions with "
4564 "two arguments can be marked commutative, "
4565 "unless the operation is known to be inherently "
4568 e
->expr_type
= expr_type
;
4571 if (e
->ops
.length () != 1)
4572 fatal_at (token
, "only unary operations can be conditional");
4573 e
->opt_grp
= opt_grp
;
4577 else if (!(token
->flags
& PREV_WHITE
))
4578 fatal_at (token
, "expected expression operand");
4580 e
->append_op (parse_op ());
4585 /* Lex native C code delimited by START recording the preprocessing tokens
4586 for later processing.
4587 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4590 parser::parse_c_expr (cpp_ttype start
)
4592 const cpp_token
*token
;
4595 vec
<cpp_token
> code
= vNULL
;
4596 unsigned nr_stmts
= 0;
4597 location_t loc
= eat_token (start
)->src_loc
;
4598 if (start
== CPP_OPEN_PAREN
)
4599 end
= CPP_CLOSE_PAREN
;
4600 else if (start
== CPP_OPEN_BRACE
)
4601 end
= CPP_CLOSE_BRACE
;
4609 /* Count brace pairs to find the end of the expr to match. */
4610 if (token
->type
== start
)
4612 else if (token
->type
== end
4615 else if (token
->type
== CPP_EOF
)
4616 fatal_at (token
, "unexpected end of file");
4618 /* This is a lame way of counting the number of statements. */
4619 if (token
->type
== CPP_SEMICOLON
)
4622 /* If this is possibly a user-defined identifier mark it used. */
4623 if (token
->type
== CPP_NAME
)
4626 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4627 if (strcmp (str
, "return") == 0)
4628 fatal_at (token
, "return statement not allowed in C expression");
4629 id_base
*idb
= get_operator (str
);
4631 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4632 record_operlist (token
->src_loc
, p
);
4635 /* Record the token. */
4636 code
.safe_push (*token
);
4639 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4642 /* Parse an operand which is either an expression, a predicate or
4643 a standalone capture.
4644 op = predicate | expr | c_expr | capture */
4649 const cpp_token
*token
= peek ();
4650 class operand
*op
= NULL
;
4651 if (token
->type
== CPP_OPEN_PAREN
)
4653 eat_token (CPP_OPEN_PAREN
);
4655 eat_token (CPP_CLOSE_PAREN
);
4657 else if (token
->type
== CPP_OPEN_BRACE
)
4659 op
= parse_c_expr (CPP_OPEN_BRACE
);
4663 /* Remaining ops are either empty or predicates */
4664 if (token
->type
== CPP_NAME
)
4666 const char *id
= get_ident ();
4667 id_base
*opr
= get_operator (id
);
4669 fatal_at (token
, "expected predicate name");
4670 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4672 if (code1
->nargs
!= 0)
4673 fatal_at (token
, "using an operator with operands as predicate");
4674 /* Parse the zero-operand operator "predicates" as
4676 op
= new expr (opr
, token
->src_loc
);
4678 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4680 if (code2
->nargs
!= 0)
4681 fatal_at (token
, "using an operator with operands as predicate");
4682 /* Parse the zero-operand operator "predicates" as
4684 op
= new expr (opr
, token
->src_loc
);
4686 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4687 op
= new predicate (p
, token
->src_loc
);
4689 fatal_at (token
, "using an unsupported operator as predicate");
4690 if (!parsing_match_operand
)
4691 fatal_at (token
, "predicates are only allowed in match expression");
4693 if (token
->flags
& PREV_WHITE
)
4696 else if (token
->type
!= CPP_COLON
4697 && token
->type
!= CPP_ATSIGN
)
4698 fatal_at (token
, "expected expression or predicate");
4699 /* optionally followed by a capture and a predicate. */
4700 if (token
->type
== CPP_COLON
)
4701 fatal_at (token
, "not implemented: predicate on leaf operand");
4702 if (token
->type
== CPP_ATSIGN
)
4703 op
= parse_capture (op
, !parsing_match_operand
);
4709 /* Create a new simplify from the current parsing state and MATCH,
4710 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4713 parser::push_simplify (simplify::simplify_kind kind
,
4714 vec
<simplify
*>& simplifiers
,
4715 operand
*match
, operand
*result
)
4717 /* Build and push a temporary for operator list uses in expressions. */
4718 if (!oper_lists
.is_empty ())
4719 active_fors
.safe_push (oper_lists
);
4721 simplifiers
.safe_push
4722 (new simplify (kind
, last_id
++, match
, result
,
4723 active_fors
.copy (), capture_ids
));
4725 if (!oper_lists
.is_empty ())
4730 <result-op> = <op> | <if> | <with>
4731 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4732 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4736 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4738 const cpp_token
*token
= peek ();
4739 if (token
->type
!= CPP_OPEN_PAREN
)
4742 eat_token (CPP_OPEN_PAREN
);
4743 if (peek_ident ("if"))
4746 if_expr
*ife
= new if_expr (token
->src_loc
);
4747 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4748 if (peek ()->type
== CPP_OPEN_PAREN
)
4750 ife
->trueexpr
= parse_result (result
, matcher
);
4751 if (peek ()->type
== CPP_OPEN_PAREN
)
4752 ife
->falseexpr
= parse_result (result
, matcher
);
4753 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4754 ife
->falseexpr
= parse_op ();
4756 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4758 ife
->trueexpr
= parse_op ();
4759 if (peek ()->type
== CPP_OPEN_PAREN
)
4760 ife
->falseexpr
= parse_result (result
, matcher
);
4761 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4762 ife
->falseexpr
= parse_op ();
4764 /* If this if is immediately closed then it contains a
4765 manual matcher or is part of a predicate definition. */
4766 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4769 fatal_at (peek (), "manual transform not implemented");
4770 ife
->trueexpr
= result
;
4772 eat_token (CPP_CLOSE_PAREN
);
4775 else if (peek_ident ("with"))
4778 with_expr
*withe
= new with_expr (token
->src_loc
);
4779 /* Parse (with c-expr expr) as (if-with (true) expr). */
4780 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4781 withe
->with
->nr_stmts
= 0;
4782 withe
->subexpr
= parse_result (result
, matcher
);
4783 eat_token (CPP_CLOSE_PAREN
);
4786 else if (peek_ident ("switch"))
4788 token
= eat_ident ("switch");
4789 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4791 if_expr
*ife
= new if_expr (ifloc
);
4793 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4794 if (peek ()->type
== CPP_OPEN_PAREN
)
4795 ife
->trueexpr
= parse_result (result
, matcher
);
4797 ife
->trueexpr
= parse_op ();
4798 eat_token (CPP_CLOSE_PAREN
);
4799 if (peek ()->type
!= CPP_OPEN_PAREN
4800 || !peek_ident ("if", 2))
4801 fatal_at (token
, "switch can be implemented with a single if");
4802 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4804 if (peek ()->type
== CPP_OPEN_PAREN
)
4806 if (peek_ident ("if", 2))
4808 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4810 ife
->falseexpr
= new if_expr (ifloc
);
4811 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4812 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4813 if (peek ()->type
== CPP_OPEN_PAREN
)
4814 ife
->trueexpr
= parse_result (result
, matcher
);
4816 ife
->trueexpr
= parse_op ();
4817 eat_token (CPP_CLOSE_PAREN
);
4821 /* switch default clause */
4822 ife
->falseexpr
= parse_result (result
, matcher
);
4823 eat_token (CPP_CLOSE_PAREN
);
4829 /* switch default clause */
4830 ife
->falseexpr
= parse_op ();
4831 eat_token (CPP_CLOSE_PAREN
);
4835 eat_token (CPP_CLOSE_PAREN
);
4840 operand
*op
= result
;
4843 eat_token (CPP_CLOSE_PAREN
);
4849 simplify = 'simplify' <expr> <result-op>
4851 match = 'match' <ident> <expr> [<result-op>]
4852 and fill SIMPLIFIERS with the results. */
4855 parser::parse_simplify (simplify::simplify_kind kind
,
4856 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4859 /* Reset the capture map. */
4861 capture_ids
= new cid_map_t
;
4862 /* Reset oper_lists and set. */
4863 hash_set
<user_id
*> olist
;
4864 oper_lists_set
= &olist
;
4867 const cpp_token
*loc
= peek ();
4868 parsing_match_operand
= true;
4869 class operand
*match
= parse_op ();
4870 finish_match_operand (match
);
4871 parsing_match_operand
= false;
4872 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4873 fatal_at (loc
, "outermost expression cannot be captured");
4874 if (match
->type
== operand::OP_EXPR
4875 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4876 fatal_at (loc
, "outermost expression cannot be a predicate");
4878 /* Splice active_ifs onto result and continue parsing the
4880 if_expr
*active_if
= NULL
;
4881 for (int i
= active_ifs
.length (); i
> 0; --i
)
4883 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4884 ifc
->cond
= active_ifs
[i
-1];
4885 ifc
->trueexpr
= active_if
;
4888 if_expr
*outermost_if
= active_if
;
4889 while (active_if
&& active_if
->trueexpr
)
4890 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4892 const cpp_token
*token
= peek ();
4894 /* If this if is immediately closed then it is part of a predicate
4895 definition. Push it. */
4896 if (token
->type
== CPP_CLOSE_PAREN
)
4899 fatal_at (token
, "expected transform expression");
4902 active_if
->trueexpr
= result
;
4903 result
= outermost_if
;
4905 push_simplify (kind
, simplifiers
, match
, result
);
4909 operand
*tem
= parse_result (result
, matcher
);
4912 active_if
->trueexpr
= tem
;
4913 result
= outermost_if
;
4918 push_simplify (kind
, simplifiers
, match
, result
);
4921 /* Parsing of the outer control structures. */
4923 /* Parse a for expression
4924 for = '(' 'for' <subst>... <pattern> ')'
4925 subst = <ident> '(' <ident>... ')' */
4928 parser::parse_for (location_t
)
4930 auto_vec
<const cpp_token
*> user_id_tokens
;
4931 vec
<user_id
*> user_ids
= vNULL
;
4932 const cpp_token
*token
;
4933 unsigned min_n_opers
= 0, max_n_opers
= 0;
4938 if (token
->type
!= CPP_NAME
)
4941 /* Insert the user defined operators into the operator hash. */
4942 const char *id
= get_ident ();
4943 if (get_operator (id
, true) != NULL
)
4944 fatal_at (token
, "operator already defined");
4945 user_id
*op
= new user_id (id
);
4946 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4948 user_ids
.safe_push (op
);
4949 user_id_tokens
.safe_push (token
);
4951 eat_token (CPP_OPEN_PAREN
);
4954 while ((token
= peek_ident ()) != 0)
4956 const char *oper
= get_ident ();
4957 id_base
*idb
= get_operator (oper
, true);
4959 fatal_at (token
, "no such operator '%s'", oper
);
4963 else if (idb
->nargs
== -1)
4965 else if (idb
->nargs
!= arity
)
4966 fatal_at (token
, "operator '%s' with arity %d does not match "
4967 "others with arity %d", oper
, idb
->nargs
, arity
);
4969 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4972 if (p
->is_oper_list
)
4973 op
->substitutes
.safe_splice (p
->substitutes
);
4975 fatal_at (token
, "iterator cannot be used as operator-list");
4978 op
->substitutes
.safe_push (idb
);
4981 token
= expect (CPP_CLOSE_PAREN
);
4983 unsigned nsubstitutes
= op
->substitutes
.length ();
4984 if (nsubstitutes
== 0)
4985 fatal_at (token
, "A user-defined operator must have at least "
4986 "one substitution");
4987 if (max_n_opers
== 0)
4989 min_n_opers
= nsubstitutes
;
4990 max_n_opers
= nsubstitutes
;
4994 if (nsubstitutes
% min_n_opers
!= 0
4995 && min_n_opers
% nsubstitutes
!= 0)
4996 fatal_at (token
, "All user-defined identifiers must have a "
4997 "multiple number of operator substitutions of the "
4998 "smallest number of substitutions");
4999 if (nsubstitutes
< min_n_opers
)
5000 min_n_opers
= nsubstitutes
;
5001 else if (nsubstitutes
> max_n_opers
)
5002 max_n_opers
= nsubstitutes
;
5006 unsigned n_ids
= user_ids
.length ();
5008 fatal_at (token
, "for requires at least one user-defined identifier");
5011 if (token
->type
== CPP_CLOSE_PAREN
)
5012 fatal_at (token
, "no pattern defined in for");
5014 active_fors
.safe_push (user_ids
);
5018 if (token
->type
== CPP_CLOSE_PAREN
)
5024 /* Remove user-defined operators from the hash again. */
5025 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
5027 if (!user_ids
[i
]->used
)
5028 warning_at (user_id_tokens
[i
],
5029 "operator %s defined but not used", user_ids
[i
]->id
);
5030 operators
->remove_elt (user_ids
[i
]);
5034 /* Parse an identifier associated with a list of operators.
5035 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
5038 parser::parse_operator_list (location_t
)
5040 const cpp_token
*token
= peek ();
5041 const char *id
= get_ident ();
5043 if (get_operator (id
, true) != 0)
5044 fatal_at (token
, "operator %s already defined", id
);
5046 user_id
*op
= new user_id (id
, true);
5049 while ((token
= peek_ident ()) != 0)
5052 const char *oper
= get_ident ();
5053 id_base
*idb
= get_operator (oper
, true);
5056 fatal_at (token
, "no such operator '%s'", oper
);
5060 else if (idb
->nargs
== -1)
5062 else if (arity
!= idb
->nargs
)
5063 fatal_at (token
, "operator '%s' with arity %d does not match "
5064 "others with arity %d", oper
, idb
->nargs
, arity
);
5066 /* We allow composition of multiple operator lists. */
5067 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
5068 op
->substitutes
.safe_splice (p
->substitutes
);
5070 op
->substitutes
.safe_push (idb
);
5073 // Check that there is no junk after id-list
5075 if (token
->type
!= CPP_CLOSE_PAREN
)
5076 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
5078 if (op
->substitutes
.length () == 0)
5079 fatal_at (token
, "operator-list cannot be empty");
5082 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
5086 /* Parse an outer if expression.
5087 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
5090 parser::parse_if (location_t
)
5092 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
5094 const cpp_token
*token
= peek ();
5095 if (token
->type
== CPP_CLOSE_PAREN
)
5096 fatal_at (token
, "no pattern defined in if");
5098 active_ifs
.safe_push (ifexpr
);
5102 if (token
->type
== CPP_CLOSE_PAREN
)
5110 /* Parse a list of predefined predicate identifiers.
5111 preds = '(' 'define_predicates' <ident>... ')' */
5114 parser::parse_predicates (location_t
)
5118 const cpp_token
*token
= peek ();
5119 if (token
->type
!= CPP_NAME
)
5122 add_predicate (get_ident ());
5127 /* Parse outer control structures.
5128 pattern = <preds>|<for>|<if>|<simplify>|<match> */
5131 parser::parse_pattern ()
5133 /* All clauses start with '('. */
5134 eat_token (CPP_OPEN_PAREN
);
5135 const cpp_token
*token
= peek ();
5136 const char *id
= get_ident ();
5137 if (strcmp (id
, "simplify") == 0)
5139 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
5142 else if (strcmp (id
, "match") == 0)
5144 bool with_args
= false;
5145 location_t e_loc
= peek ()->src_loc
;
5146 if (peek ()->type
== CPP_OPEN_PAREN
)
5148 eat_token (CPP_OPEN_PAREN
);
5151 const char *name
= get_ident ();
5152 id_base
*id1
= get_operator (name
);
5156 p
= add_predicate (name
);
5157 user_predicates
.safe_push (p
);
5159 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5162 fatal_at (token
, "cannot add a match to a non-predicate ID");
5163 /* Parse (match <id> <arg>... (match-expr)) here. */
5167 capture_ids
= new cid_map_t
;
5168 e
= new expr (p
, e_loc
);
5169 while (peek ()->type
== CPP_ATSIGN
)
5170 e
->append_op (parse_capture (NULL
, false));
5171 eat_token (CPP_CLOSE_PAREN
);
5174 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5175 || (!e
&& p
->nargs
!= 0)))
5176 fatal_at (token
, "non-matching number of match operands");
5177 p
->nargs
= e
? e
->ops
.length () : 0;
5178 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5181 else if (strcmp (id
, "for") == 0)
5182 parse_for (token
->src_loc
);
5183 else if (strcmp (id
, "if") == 0)
5184 parse_if (token
->src_loc
);
5185 else if (strcmp (id
, "define_predicates") == 0)
5187 if (active_ifs
.length () > 0
5188 || active_fors
.length () > 0)
5189 fatal_at (token
, "define_predicates inside if or for is not supported");
5190 parse_predicates (token
->src_loc
);
5192 else if (strcmp (id
, "define_operator_list") == 0)
5194 if (active_ifs
.length () > 0
5195 || active_fors
.length () > 0)
5196 fatal_at (token
, "operator-list inside if or for is not supported");
5197 parse_operator_list (token
->src_loc
);
5200 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5201 active_ifs
.length () == 0 && active_fors
.length () == 0
5202 ? "'define_predicates', " : "");
5204 eat_token (CPP_CLOSE_PAREN
);
5207 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5211 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5216 if (capture
*c
= dyn_cast
<capture
*> (op
))
5218 cpts
[c
->where
].safe_push (c
);
5219 walk_captures (c
->what
, cpts
);
5221 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5222 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5223 walk_captures (e
->ops
[i
], cpts
);
5226 /* Finish up OP which is a match operand. */
5229 parser::finish_match_operand (operand
*op
)
5231 /* Look for matching captures, diagnose mis-uses of @@ and apply
5232 early lowering and distribution of value_match. */
5233 auto_vec
<vec
<capture
*> > cpts
;
5234 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5235 walk_captures (op
, cpts
);
5236 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5238 capture
*value_match
= NULL
;
5239 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5241 if (cpts
[i
][j
]->value_match
)
5244 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5245 value_match
= cpts
[i
][j
];
5248 if (cpts
[i
].length () == 1 && value_match
)
5249 fatal_at (value_match
->location
, "@@ without a matching capture");
5252 /* Duplicate prevailing capture with the existing ID, create
5253 a fake ID and rewrite all captures to use it. This turns
5254 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5255 value_match
->what
= new capture (value_match
->location
,
5257 value_match
->what
, false);
5258 /* Create a fake ID and rewrite all captures to use it. */
5259 unsigned newid
= get_internal_capture_id ();
5260 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5262 cpts
[i
][j
]->where
= newid
;
5263 cpts
[i
][j
]->value_match
= true;
5270 /* Main entry of the parser. Repeatedly parse outer control structures. */
5272 parser::parser (cpp_reader
*r_
, bool gimple_
)
5277 active_fors
= vNULL
;
5278 simplifiers
= vNULL
;
5279 oper_lists_set
= NULL
;
5282 user_predicates
= vNULL
;
5283 parsing_match_operand
= false;
5286 const cpp_token
*token
= next ();
5287 while (token
->type
!= CPP_EOF
)
5289 _cpp_backup_tokens (r
, 1);
5296 /* Helper for the linemap code. */
5299 round_alloc_size (size_t s
)
5305 /* Construct and display the help menu. */
5310 const char *usage
= "Usage:\n"
5311 " %s [--gimple|--generic] [-v[v]] <input>\n"
5312 " %s [options] [--include=FILE] --header=FILE <input> <output>...\n";
5313 fprintf (stderr
, usage
, progname
, progname
);
5316 /* Write out the correct include to the match-head fle containing the helper
5320 write_header_includes (bool gimple
, FILE *header_file
)
5323 fprintf (header_file
, "#include \"gimple-match-head.cc\"\n");
5325 fprintf (header_file
, "#include \"generic-match-head.cc\"\n");
5328 /* The genmatch generator program. It reads from a pattern description
5329 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5332 main (int argc
, char **argv
)
5336 progname
= "genmatch";
5339 char *s_header_file
= NULL
;
5340 char *s_include_file
= NULL
;
5341 auto_vec
<char *> files
;
5343 int last_file
= argc
- 1;
5344 for (int i
= argc
- 1; i
>= 1; --i
)
5346 if (strcmp (argv
[i
], "--gimple") == 0)
5348 else if (strcmp (argv
[i
], "--generic") == 0)
5350 else if (strncmp (argv
[i
], "--header=", 9) == 0)
5351 s_header_file
= &argv
[i
][9];
5352 else if (strncmp (argv
[i
], "--include=", 10) == 0)
5353 s_include_file
= &argv
[i
][10];
5354 else if (strcmp (argv
[i
], "-v") == 0)
5356 else if (strcmp (argv
[i
], "-vv") == 0)
5358 else if (strncmp (argv
[i
], "--", 2) != 0 && last_file
-- == i
)
5359 files
.safe_push (argv
[i
]);
5367 /* Validate if the combinations are valid. */
5368 if ((files
.length () > 1 && !s_header_file
) || files
.is_empty ())
5374 if (!s_include_file
)
5375 s_include_file
= s_header_file
;
5377 /* Input file is the last in the reverse list. */
5378 input
= files
.pop ();
5380 line_table
= XCNEW (class line_maps
);
5381 linemap_init (line_table
, 0);
5382 line_table
->reallocator
= xrealloc
;
5383 line_table
->round_alloc_size
= round_alloc_size
;
5385 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5386 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5387 cb
->diagnostic
= diagnostic_cb
;
5389 /* Add the build directory to the #include "" search path. */
5390 cpp_dir
*dir
= XCNEW (cpp_dir
);
5391 dir
->name
= getpwd ();
5393 dir
->name
= ASTRDUP (".");
5394 cpp_set_include_chains (r
, dir
, NULL
, false);
5396 if (!cpp_read_main_file (r
, input
))
5398 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5399 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5401 null_id
= new id_base (id_base::NULL_ID
, "null");
5403 /* Pre-seed operators. */
5404 operators
= new hash_table
<id_base
> (1024);
5405 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5406 add_operator (SYM, # SYM, # TYPE, NARGS);
5407 #define END_OF_BASE_TREE_CODES
5409 #undef END_OF_BASE_TREE_CODES
5412 /* Pre-seed builtin functions.
5413 ??? Cannot use N (name) as that is targetm.emultls.get_address
5414 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5415 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5416 add_function (ENUM, "CFN_" # ENUM);
5417 #include "builtins.def"
5419 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5420 add_function (IFN_##CODE, "CFN_" #CODE);
5421 #include "internal-fn.def"
5424 parser
p (r
, gimple
);
5426 /* Create file buffers. */
5427 int n_parts
= files
.is_empty () ? 1 : files
.length ();
5428 auto_vec
<FILE *> parts (n_parts
);
5429 if (files
.is_empty ())
5431 parts
.quick_push (stdout
);
5432 write_header (stdout
, s_include_file
);
5433 write_header_includes (gimple
, stdout
);
5437 for (char *s_file
: files
)
5439 parts
.quick_push (fopen (s_file
, "w"));
5440 write_header (parts
.last (), s_include_file
);
5443 header_file
= fopen (s_header_file
, "w");
5444 fprintf (header_file
, "#ifndef GCC_GIMPLE_MATCH_AUTO_H\n"
5445 "#define GCC_GIMPLE_MATCH_AUTO_H\n");
5446 write_header_includes (gimple
, header_file
);
5449 /* Go over all predicates defined with patterns and perform
5450 lowering and code generation. */
5451 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5453 predicate_id
*pred
= p
.user_predicates
[i
];
5454 lower (pred
->matchers
, gimple
);
5457 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5458 print_matches (pred
->matchers
[j
]);
5461 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5462 dt
.insert (pred
->matchers
[j
], j
);
5467 /* Cycle the file buffers. */
5468 FILE *f
= choose_output (parts
);
5470 write_predicate (f
, pred
, dt
, gimple
);
5473 /* Lower the main simplifiers and generate code for them. */
5474 lower (p
.simplifiers
, gimple
);
5477 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5478 print_matches (p
.simplifiers
[i
]);
5481 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5482 dt
.insert (p
.simplifiers
[i
], i
);
5487 dt
.gen (parts
, gimple
);
5489 for (FILE *f
: parts
)
5491 fprintf (f
, "#pragma GCC diagnostic pop\n");
5497 fprintf (header_file
, "\n#endif /* GCC_GIMPLE_MATCH_AUTO_H. */\n");
5498 fclose (header_file
);
5502 cpp_finish (r
, NULL
);