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",
2628 fprintf_indent (f
, indent
+ 2, "{\n");
2631 if (opr
->kind
== id_base::CODE
)
2632 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2633 depth
, ops
.length(), opr_name
, type
);
2635 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2636 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2637 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2638 fprintf (f
, ", _o%d[%u]", depth
, i
);
2639 fprintf (f
, ");\n");
2640 if (opr
->kind
!= id_base::CODE
)
2642 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2643 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2647 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2648 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2650 if (*opr
== CONVERT_EXPR
)
2652 fprintf_indent (f
, indent
- 2, "}\n");
2654 fprintf_indent (f
, indent
, "else\n");
2655 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2658 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2660 fprintf_indent (f
, indent
, "}\n");
2663 /* Generate code for a c_expr which is either the expression inside
2664 an if statement or a sequence of statements which computes a
2665 result to be stored to DEST. */
2668 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2669 bool, int, const char *, capture_info
*,
2672 if (dest
&& nr_stmts
== 1)
2673 fprintf_indent (f
, indent
, "%s = ", dest
);
2675 unsigned stmt_nr
= 1;
2677 for (unsigned i
= 0; i
< code
.length (); ++i
)
2679 const cpp_token
*token
= &code
[i
];
2681 /* We can't recover from all lexing losses but we can roughly restore line
2682 breaks from location info. */
2683 const line_map_ordinary
*map
;
2684 linemap_resolve_location (line_table
, token
->src_loc
,
2685 LRK_SPELLING_LOCATION
, &map
);
2686 expanded_location loc
= linemap_expand_location (line_table
, map
,
2688 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2690 prev_line
= loc
.line
;
2692 /* Replace captures for code-gen. */
2693 if (token
->type
== CPP_ATSIGN
)
2695 const cpp_token
*n
= &code
[i
+1];
2696 if ((n
->type
== CPP_NUMBER
2697 || n
->type
== CPP_NAME
)
2698 && !(n
->flags
& PREV_WHITE
))
2700 if (token
->flags
& PREV_WHITE
)
2703 if (n
->type
== CPP_NUMBER
)
2704 id
= (const char *)n
->val
.str
.text
;
2706 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2707 unsigned *cid
= capture_ids
->get (id
);
2709 fatal_at (token
, "unknown capture id");
2710 fprintf (f
, "captures[%u]", *cid
);
2716 if (token
->flags
& PREV_WHITE
)
2719 if (token
->type
== CPP_NAME
)
2721 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2723 for (j
= 0; j
< ids
.length (); ++j
)
2725 if (strcmp (id
, ids
[j
].id
) == 0)
2727 fprintf (f
, "%s", ids
[j
].oper
);
2731 if (j
< ids
.length ())
2735 /* Output the token as string. */
2736 char *tk
= (char *)cpp_token_as_text (r
, token
);
2739 if (token
->type
== CPP_SEMICOLON
)
2742 if (dest
&& stmt_nr
== nr_stmts
)
2743 fprintf_indent (f
, indent
, "%s = ", dest
);
2749 /* Generate transform code for a capture. */
2752 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2753 int depth
, const char *in_type
, capture_info
*cinfo
,
2754 dt_operand
**indexes
, int cond_handling
)
2756 if (what
&& is_a
<expr
*> (what
))
2758 if (indexes
[where
] == 0)
2761 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2762 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2767 /* If in GENERIC some capture is used multiple times, unshare it except
2768 when emitting the last use. */
2770 && cinfo
->info
.exists ()
2771 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2773 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2775 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2778 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2780 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2781 with substituting a capture of that. */
2783 && cond_handling
!= 0
2784 && cinfo
->info
[where
].cond_expr_cond_p
)
2786 /* If substituting into a cond_expr condition, unshare. */
2787 if (cond_handling
== 1)
2788 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2789 /* If substituting elsewhere we might need to decompose it. */
2790 else if (cond_handling
== 2)
2792 /* ??? Returning false here will also not allow any other patterns
2793 to match unless this generator was split out. */
2794 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2795 fprintf_indent (f
, indent
, " {\n");
2796 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2797 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2799 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2800 " TREE_OPERAND (%s, 1));\n",
2801 dest
, dest
, dest
, dest
, dest
);
2802 fprintf_indent (f
, indent
, " }\n");
2807 /* Return the name of the operand representing the decision tree node.
2808 Use NAME as space to generate it. */
2811 dt_operand::get_name (char *name
)
2814 sprintf (name
, "t");
2815 else if (parent
->level
== 1)
2816 sprintf (name
, "_p%u", pos
);
2817 else if (parent
->type
== dt_node::DT_MATCH
)
2818 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2820 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2824 /* Fill NAME with the operand name at position POS. */
2827 dt_operand::gen_opname (char *name
, unsigned pos
)
2830 sprintf (name
, "_p%u", pos
);
2832 sprintf (name
, "_q%u%u", level
, pos
);
2835 /* Generate matching code for the decision tree operand which is
2839 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2841 predicate
*p
= as_a
<predicate
*> (op
);
2843 if (p
->p
->matchers
.exists ())
2845 /* If this is a predicate generated from a pattern mangle its
2846 name and pass on the valueize hook. */
2848 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2851 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2854 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2855 fprintf_indent (f
, indent
+ 2, "{\n");
2859 /* Generate matching code for the decision tree operand which is
2863 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2865 char match_opname
[20];
2866 match_dop
->get_name (match_opname
);
2868 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2869 "|| operand_equal_p (%s, %s, 0))\n",
2870 opname
, match_opname
, opname
, opname
, match_opname
);
2872 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2873 "|| (operand_equal_p (%s, %s, 0) "
2874 "&& types_match (%s, %s)))\n",
2875 opname
, match_opname
, opname
, opname
, match_opname
,
2876 opname
, match_opname
);
2877 fprintf_indent (f
, indent
+ 2, "{\n");
2881 /* Generate GIMPLE matching code for the decision tree operand. */
2884 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2886 expr
*e
= static_cast<expr
*> (op
);
2887 id_base
*id
= e
->operation
;
2888 unsigned n_ops
= e
->ops
.length ();
2889 unsigned n_braces
= 0;
2891 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2892 id
= u
->substitutes
[0];
2894 for (unsigned i
= 0; i
< n_ops
; ++i
)
2896 char child_opname
[20];
2897 gen_opname (child_opname
, i
);
2899 if (id
->kind
== id_base::CODE
)
2902 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2903 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2905 /* ??? If this is a memory operation we can't (and should not)
2906 match this. The only sensible operand types are
2907 SSA names and invariants. */
2912 fprintf_indent (f
, indent
,
2913 "tree %s = TREE_OPERAND (%s, %i);\n",
2914 child_opname
, opname
, i
);
2917 fprintf_indent (f
, indent
,
2918 "tree %s = TREE_OPERAND "
2919 "(gimple_assign_rhs1 (_a%d), %i);\n",
2920 child_opname
, depth
, i
);
2921 fprintf_indent (f
, indent
,
2922 "if ((TREE_CODE (%s) == SSA_NAME\n",
2924 fprintf_indent (f
, indent
,
2925 " || is_gimple_min_invariant (%s)))\n",
2927 fprintf_indent (f
, indent
,
2931 fprintf_indent (f
, indent
,
2932 "%s = do_valueize (valueize, %s);\n",
2933 child_opname
, child_opname
);
2937 fprintf_indent (f
, indent
,
2938 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2939 child_opname
, i
+ 1, depth
);
2942 fprintf_indent (f
, indent
,
2943 "tree %s = gimple_call_arg (_c%d, %u);\n",
2944 child_opname
, depth
, i
);
2945 fprintf_indent (f
, indent
,
2946 "%s = do_valueize (valueize, %s);\n",
2947 child_opname
, child_opname
);
2949 /* While the toplevel operands are canonicalized by the caller
2950 after valueizing operands of sub-expressions we have to
2951 re-canonicalize operand order. */
2952 int opno
= commutative_op (id
);
2955 char child_opname0
[20], child_opname1
[20];
2956 gen_opname (child_opname0
, opno
);
2957 gen_opname (child_opname1
, opno
+ 1);
2958 fprintf_indent (f
, indent
,
2959 "if (tree_swap_operands_p (%s, %s))\n",
2960 child_opname0
, child_opname1
);
2961 fprintf_indent (f
, indent
,
2962 " std::swap (%s, %s);\n",
2963 child_opname0
, child_opname1
);
2969 /* Generate GENERIC matching code for the decision tree operand. */
2972 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2974 expr
*e
= static_cast<expr
*> (op
);
2975 id_base
*id
= e
->operation
;
2976 unsigned n_ops
= e
->ops
.length ();
2978 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2979 id
= u
->substitutes
[0];
2981 for (unsigned i
= 0; i
< n_ops
; ++i
)
2983 char child_opname
[20];
2984 gen_opname (child_opname
, i
);
2986 if (id
->kind
== id_base::CODE
)
2987 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2988 child_opname
, opname
, i
);
2990 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2991 child_opname
, opname
, i
);
2997 /* Generate matching code for the children of the decision tree node. */
3000 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
3002 auto_vec
<dt_operand
*> gimple_exprs
;
3003 auto_vec
<dt_operand
*> generic_exprs
;
3004 auto_vec
<dt_operand
*> fns
;
3005 auto_vec
<dt_operand
*> generic_fns
;
3006 auto_vec
<dt_operand
*> preds
;
3007 auto_vec
<dt_node
*> others
;
3009 for (unsigned i
= 0; i
< kids
.length (); ++i
)
3011 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
3013 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
3014 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
3016 if (e
->ops
.length () == 0
3017 /* In GIMPLE a CONSTRUCTOR always appears in a
3018 separate definition. */
3019 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
3021 generic_exprs
.safe_push (op
);
3022 /* But ADDR_EXPRs can appear directly when invariant
3023 and in a separate definition when not. */
3024 if (gimple
&& *e
->operation
== ADDR_EXPR
)
3025 gimple_exprs
.safe_push (op
);
3027 else if (e
->operation
->kind
== id_base::FN
)
3032 generic_fns
.safe_push (op
);
3034 else if (e
->operation
->kind
== id_base::PREDICATE
)
3035 preds
.safe_push (op
);
3038 user_id
*u
= dyn_cast
<user_id
*> (e
->operation
);
3039 if (u
&& u
->substitutes
[0]->kind
== id_base::FN
)
3044 generic_fns
.safe_push (op
);
3048 if (gimple
&& !e
->is_generic
)
3049 gimple_exprs
.safe_push (op
);
3051 generic_exprs
.safe_push (op
);
3055 else if (op
->op
->type
== operand::OP_PREDICATE
)
3056 others
.safe_push (kids
[i
]);
3060 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
3061 others
.safe_push (kids
[i
]);
3062 else if (kids
[i
]->type
== dt_node::DT_MATCH
3063 || kids
[i
]->type
== dt_node::DT_TRUE
)
3065 /* A DT_TRUE operand serves as a barrier - generate code now
3066 for what we have collected sofar.
3067 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3068 dependent matches to get out-of-order. Generate code now
3069 for what we have collected sofar. */
3070 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3071 fns
, generic_fns
, preds
, others
);
3072 /* And output the true operand itself. */
3073 kids
[i
]->gen (f
, indent
, gimple
, depth
);
3074 gimple_exprs
.truncate (0);
3075 generic_exprs
.truncate (0);
3077 generic_fns
.truncate (0);
3079 others
.truncate (0);
3085 /* Generate code for the remains. */
3086 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3087 fns
, generic_fns
, preds
, others
);
3090 /* Generate matching code for the children of the decision tree node. */
3093 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
3094 const vec
<dt_operand
*> &gimple_exprs
,
3095 const vec
<dt_operand
*> &generic_exprs
,
3096 const vec
<dt_operand
*> &fns
,
3097 const vec
<dt_operand
*> &generic_fns
,
3098 const vec
<dt_operand
*> &preds
,
3099 const vec
<dt_node
*> &others
)
3102 char *kid_opname
= buf
;
3104 unsigned exprs_len
= gimple_exprs
.length ();
3105 unsigned gexprs_len
= generic_exprs
.length ();
3106 unsigned fns_len
= fns
.length ();
3107 unsigned gfns_len
= generic_fns
.length ();
3109 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3112 gimple_exprs
[0]->get_name (kid_opname
);
3114 fns
[0]->get_name (kid_opname
);
3116 generic_fns
[0]->get_name (kid_opname
);
3118 generic_exprs
[0]->get_name (kid_opname
);
3120 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3121 fprintf_indent (f
, indent
, " {\n");
3125 if (exprs_len
|| fns_len
)
3128 fprintf_indent (f
, indent
,
3129 "case SSA_NAME:\n");
3130 fprintf_indent (f
, indent
,
3131 " if (gimple *_d%d = get_def (valueize, %s))\n",
3133 fprintf_indent (f
, indent
,
3138 fprintf_indent (f
, indent
,
3139 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3141 fprintf_indent (f
, indent
,
3142 " switch (gimple_assign_rhs_code (_a%d))\n",
3145 fprintf_indent (f
, indent
, "{\n");
3146 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3148 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3149 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3151 for (auto id
: u
->substitutes
)
3152 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3156 id_base
*op
= e
->operation
;
3157 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3158 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3160 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3162 fprintf_indent (f
, indent
, " {\n");
3163 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3164 fprintf_indent (f
, indent
, " break;\n");
3165 fprintf_indent (f
, indent
, " }\n");
3167 fprintf_indent (f
, indent
, "default:;\n");
3168 fprintf_indent (f
, indent
, "}\n");
3174 fprintf_indent (f
, indent
,
3175 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3176 exprs_len
? "else " : "", depth
, depth
);
3177 fprintf_indent (f
, indent
,
3178 " switch (gimple_call_combined_fn (_c%d))\n",
3182 fprintf_indent (f
, indent
, "{\n");
3183 for (unsigned i
= 0; i
< fns_len
; ++i
)
3185 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3186 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3187 for (auto id
: u
->substitutes
)
3188 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3190 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3191 /* We need to be defensive against bogus prototypes allowing
3192 calls with not enough arguments. */
3193 fprintf_indent (f
, indent
,
3194 " if (gimple_call_num_args (_c%d) == %d)\n",
3195 depth
, e
->ops
.length ());
3196 fprintf_indent (f
, indent
, " {\n");
3197 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3198 fprintf_indent (f
, indent
, " }\n");
3199 fprintf_indent (f
, indent
, " break;\n");
3202 fprintf_indent (f
, indent
, "default:;\n");
3203 fprintf_indent (f
, indent
, "}\n");
3209 fprintf_indent (f
, indent
, " }\n");
3210 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3211 here rather than in the next loop. */
3212 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3214 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3215 id_base
*op
= e
->operation
;
3216 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3218 fprintf_indent (f
, indent
+ 4, "{\n");
3219 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3220 fprintf_indent (f
, indent
+ 4, "}\n");
3224 fprintf_indent (f
, indent
, " break;\n");
3227 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3229 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3230 id_base
*op
= e
->operation
;
3231 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3232 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3233 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3234 /* Already handled above. */
3238 if (user_id
*u
= dyn_cast
<user_id
*> (op
))
3239 for (auto id
: u
->substitutes
)
3240 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3242 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3244 fprintf_indent (f
, indent
, " {\n");
3245 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3246 fprintf_indent (f
, indent
, " break;\n");
3247 fprintf_indent (f
, indent
, " }\n");
3252 fprintf_indent (f
, indent
,
3253 "case CALL_EXPR:\n");
3254 fprintf_indent (f
, indent
,
3255 " switch (get_call_combined_fn (%s))\n",
3257 fprintf_indent (f
, indent
,
3261 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3263 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3264 gcc_assert (e
->operation
->kind
== id_base::FN
);
3266 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3267 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3268 " {\n", kid_opname
, e
->ops
.length ());
3269 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3270 fprintf_indent (f
, indent
, " }\n"
3273 fprintf_indent (f
, indent
, "default:;\n");
3276 fprintf_indent (f
, indent
, " }\n");
3277 fprintf_indent (f
, indent
, " break;\n");
3280 /* Close switch (TREE_CODE ()). */
3281 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3284 fprintf_indent (f
, indent
, " default:;\n");
3285 fprintf_indent (f
, indent
, " }\n");
3288 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3290 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3291 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3292 preds
[i
]->get_name (kid_opname
);
3293 fprintf_indent (f
, indent
, "{\n");
3295 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3296 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3297 gimple
? "gimple" : "tree",
3298 p
->id
, kid_opname
, kid_opname
,
3299 gimple
? ", valueize" : "");
3300 fprintf_indent (f
, indent
, " {\n");
3301 for (int j
= 0; j
< p
->nargs
; ++j
)
3303 char child_opname
[20];
3304 preds
[i
]->gen_opname (child_opname
, j
);
3305 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3306 child_opname
, kid_opname
, j
);
3308 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3311 fprintf_indent (f
, indent
, "}\n");
3314 for (unsigned i
= 0; i
< others
.length (); ++i
)
3315 others
[i
]->gen (f
, indent
, gimple
, depth
);
3318 /* Generate matching code for the decision tree operand. */
3321 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3326 unsigned n_braces
= 0;
3328 if (type
== DT_OPERAND
)
3331 case operand::OP_PREDICATE
:
3332 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3335 case operand::OP_EXPR
:
3337 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3339 n_braces
= gen_generic_expr (f
, indent
, opname
);
3345 else if (type
== DT_TRUE
)
3347 else if (type
== DT_MATCH
)
3348 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3352 indent
+= 4 * n_braces
;
3353 gen_kids (f
, indent
, gimple
, depth
);
3355 for (unsigned i
= 0; i
< n_braces
; ++i
)
3360 fprintf_indent (f
, indent
, " }\n");
3364 /* Emit a fprintf to the debug file to the file F, with the INDENT from
3365 either the RESULT location or the S's match location if RESULT is null. */
3367 emit_debug_printf (FILE *f
, int indent
, class simplify
*s
, operand
*result
)
3369 fprintf_indent (f
, indent
, "if (UNLIKELY (debug_dump)) "
3370 "fprintf (dump_file, \"%s ",
3371 s
->kind
== simplify::SIMPLIFY
3372 ? "Applying pattern" : "Matching expression");
3373 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3374 output_line_directive (f
,
3375 result
? result
->location
: s
->match
->location
, true,
3377 fprintf (f
, ", __FILE__, __LINE__);\n");
3380 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3381 step of a '(simplify ...)' or '(match ...)'. This handles everything
3382 that is not part of the decision tree (simplify->match).
3383 Main recursive worker. */
3386 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3390 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3392 fprintf_indent (f
, indent
, "{\n");
3394 output_line_directive (f
, w
->location
);
3395 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3396 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3398 fprintf_indent (f
, indent
, "}\n");
3401 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3403 output_line_directive (f
, ife
->location
);
3404 fprintf_indent (f
, indent
, "if (");
3405 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3407 fprintf_indent (f
, indent
+ 2, "{\n");
3409 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3411 fprintf_indent (f
, indent
+ 2, "}\n");
3414 fprintf_indent (f
, indent
, "else\n");
3415 fprintf_indent (f
, indent
+ 2, "{\n");
3417 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3419 fprintf_indent (f
, indent
+ 2, "}\n");
3425 static unsigned fail_label_cnt
;
3426 char local_fail_label
[256];
3427 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3428 fail_label
= local_fail_label
;
3429 bool needs_label
= false;
3431 /* Analyze captures and perform early-outs on the incoming arguments
3432 that cover cases we cannot handle. */
3433 capture_info
cinfo (s
, result
, gimple
);
3434 if (s
->kind
== simplify::SIMPLIFY
)
3438 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3439 if (cinfo
.force_no_side_effects
& (1 << i
))
3441 fprintf_indent (f
, indent
,
3442 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3446 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3447 "forcing toplevel operand to have no "
3450 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3451 if (cinfo
.info
[i
].cse_p
)
3453 else if (cinfo
.info
[i
].force_no_side_effects_p
3454 && (cinfo
.info
[i
].toplevel_msk
3455 & cinfo
.force_no_side_effects
) == 0)
3457 fprintf_indent (f
, indent
,
3458 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3459 "goto %s;\n", i
, fail_label
);
3462 warning_at (cinfo
.info
[i
].c
->location
,
3463 "forcing captured operand to have no "
3466 else if ((cinfo
.info
[i
].toplevel_msk
3467 & cinfo
.force_no_side_effects
) != 0)
3468 /* Mark capture as having no side-effects if we had to verify
3469 that via forced toplevel operand checks. */
3470 cinfo
.info
[i
].force_no_side_effects_p
= true;
3474 /* Force single-use restriction by only allowing simple
3475 results via setting seq to NULL. */
3476 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3477 bool first_p
= true;
3478 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3479 if (cinfo
.info
[i
].force_single_use
)
3483 fprintf_indent (f
, indent
, "if (lseq\n");
3484 fprintf_indent (f
, indent
, " && (");
3490 fprintf_indent (f
, indent
, " || ");
3492 fprintf (f
, "!single_use (captures[%d])", i
);
3496 fprintf (f
, "))\n");
3497 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3502 if (s
->kind
== simplify::SIMPLIFY
)
3504 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3508 fprintf_indent (f
, indent
, "{\n");
3512 /* If there is no result then this is a predicate implementation. */
3513 emit_debug_printf (f
, indent
, s
, result
);
3514 fprintf_indent (f
, indent
, "return true;\n");
3518 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3519 in outermost position). */
3520 if (result
->type
== operand::OP_EXPR
3521 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3522 result
= as_a
<expr
*> (result
)->ops
[0];
3523 if (result
->type
== operand::OP_EXPR
)
3525 expr
*e
= as_a
<expr
*> (result
);
3526 id_base
*opr
= e
->operation
;
3527 bool is_predicate
= false;
3528 /* When we delay operator substituting during lowering of fors we
3529 make sure that for code-gen purposes the effects of each substitute
3530 are the same. Thus just look at that. */
3531 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3532 opr
= uid
->substitutes
[0];
3533 else if (is_a
<predicate_id
*> (opr
))
3534 is_predicate
= true;
3536 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3537 *e
->operation
== CONVERT_EXPR
3538 ? "NOP_EXPR" : e
->operation
->id
,
3540 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3544 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3546 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3548 = get_operand_type (opr
, j
,
3549 "type", e
->expr_type
,
3551 : "TREE_TYPE (res_op->ops[0])");
3552 /* We need to expand GENERIC conditions we captured from
3553 COND_EXPRs and we need to unshare them when substituting
3555 int cond_handling
= 0;
3557 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3558 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3559 &cinfo
, indexes
, cond_handling
);
3562 /* Re-fold the toplevel result. It's basically an embedded
3563 gimple_build w/o actually building the stmt. */
3566 fprintf_indent (f
, indent
,
3567 "res_op->resimplify (%s, valueize);\n",
3568 !e
->force_leaf
? "lseq" : "NULL");
3571 fprintf_indent (f
, indent
,
3572 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3573 "goto %s;\n", fail_label
);
3578 else if (result
->type
== operand::OP_CAPTURE
3579 || result
->type
== operand::OP_C_EXPR
)
3581 fprintf_indent (f
, indent
, "tree tem;\n");
3582 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3584 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3585 if (is_a
<capture
*> (result
)
3586 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3588 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3589 with substituting a capture of that. */
3590 fprintf_indent (f
, indent
,
3591 "if (COMPARISON_CLASS_P (tem))\n");
3592 fprintf_indent (f
, indent
,
3594 fprintf_indent (f
, indent
,
3595 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3596 fprintf_indent (f
, indent
,
3597 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3598 fprintf_indent (f
, indent
,
3604 emit_debug_printf (f
, indent
, s
, result
);
3605 fprintf_indent (f
, indent
, "return true;\n");
3609 bool is_predicate
= false;
3610 if (result
->type
== operand::OP_EXPR
)
3612 expr
*e
= as_a
<expr
*> (result
);
3613 id_base
*opr
= e
->operation
;
3614 /* When we delay operator substituting during lowering of fors we
3615 make sure that for code-gen purposes the effects of each substitute
3616 are the same. Thus just look at that. */
3617 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3618 opr
= uid
->substitutes
[0];
3619 else if (is_a
<predicate_id
*> (opr
))
3620 is_predicate
= true;
3621 /* Search for captures used multiple times in the result expression
3622 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3623 original expression. */
3625 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3627 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3628 || cinfo
.info
[i
].cse_p
)
3630 if (cinfo
.info
[i
].result_use_count
3631 > cinfo
.info
[i
].match_use_count
)
3633 fprintf_indent (f
, indent
,
3634 "if (! tree_invariant_p (captures[%d])) "
3635 "goto %s;\n", i
, fail_label
);
3639 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3643 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3646 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3647 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3650 = get_operand_type (opr
, j
,
3651 "type", e
->expr_type
,
3653 ? NULL
: "TREE_TYPE (res_op0)");
3654 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3659 emit_debug_printf (f
, indent
, s
, result
);
3660 fprintf_indent (f
, indent
, "return true;\n");
3664 fprintf_indent (f
, indent
, "tree _r;\n");
3665 /* Re-fold the toplevel result. Use non_lvalue to
3666 build NON_LVALUE_EXPRs so they get properly
3667 ignored when in GIMPLE form. */
3668 if (*opr
== NON_LVALUE_EXPR
)
3669 fprintf_indent (f
, indent
,
3670 "_r = non_lvalue_loc (loc, res_op0);\n");
3673 if (is_a
<operator_id
*> (opr
))
3674 fprintf_indent (f
, indent
,
3675 "_r = fold_build%d_loc (loc, %s, type",
3677 *e
->operation
== CONVERT_EXPR
3678 ? "NOP_EXPR" : e
->operation
->id
);
3680 fprintf_indent (f
, indent
,
3681 "_r = maybe_build_call_expr_loc (loc, "
3682 "%s, type, %d", e
->operation
->id
,
3684 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3685 fprintf (f
, ", res_op%d", j
);
3686 fprintf (f
, ");\n");
3687 if (!is_a
<operator_id
*> (opr
))
3689 fprintf_indent (f
, indent
, "if (!_r)\n");
3690 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3696 else if (result
->type
== operand::OP_CAPTURE
3697 || result
->type
== operand::OP_C_EXPR
)
3700 fprintf_indent (f
, indent
, "tree _r;\n");
3701 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3708 /* Search for captures not used in the result expression and dependent
3709 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3710 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3712 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3714 if (!cinfo
.info
[i
].force_no_side_effects_p
3715 && !cinfo
.info
[i
].expr_p
3716 && cinfo
.info
[i
].result_use_count
== 0)
3718 fprintf_indent (f
, indent
,
3719 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3721 fprintf_indent (f
, indent
+ 2,
3722 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3723 "fold_ignored_result (captures[%d]), _r);\n",
3727 emit_debug_printf (f
, indent
, s
, result
);
3728 fprintf_indent (f
, indent
, "return _r;\n");
3732 fprintf_indent (f
, indent
, "}\n");
3734 fprintf (f
, "%s:;\n", fail_label
);
3738 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3739 step of a '(simplify ...)' or '(match ...)'. This handles everything
3740 that is not part of the decision tree (simplify->match). */
3743 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3745 fprintf_indent (f
, indent
, "{\n");
3747 output_line_directive (f
,
3748 s
->result
? s
->result
->location
: s
->match
->location
);
3749 if (s
->capture_max
>= 0)
3752 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3753 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3755 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3759 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3761 fprintf (f
, " };\n");
3764 /* If we have a split-out function for the actual transform, call it. */
3765 if (info
&& info
->fname
)
3769 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3770 "valueize, type, captures", info
->fname
);
3771 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3772 if (s
->for_subst_vec
[i
].first
->used
)
3773 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3774 fprintf (f
, "))\n");
3775 fprintf_indent (f
, indent
, " return true;\n");
3779 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3781 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3782 fprintf (f
, ", _p%d", i
);
3783 fprintf (f
, ", captures");
3784 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3786 if (s
->for_subst_vec
[i
].first
->used
)
3787 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3789 fprintf (f
, ");\n");
3790 fprintf_indent (f
, indent
, "if (res) return res;\n");
3795 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3797 if (! s
->for_subst_vec
[i
].first
->used
)
3799 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3800 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3801 s
->for_subst_vec
[i
].first
->id
,
3802 s
->for_subst_vec
[i
].second
->id
);
3803 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3804 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3805 s
->for_subst_vec
[i
].first
->id
,
3806 s
->for_subst_vec
[i
].second
->id
);
3810 gen_1 (f
, indent
, gimple
, s
->result
);
3814 fprintf_indent (f
, indent
, "}\n");
3818 /* Hash function for finding equivalent transforms. */
3821 sinfo_hashmap_traits::hash (const key_type
&v
)
3823 /* Only bother to compare those originating from the same source pattern. */
3824 return v
->s
->result
->location
;
3827 /* Compare function for finding equivalent transforms. */
3830 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3832 if (o1
->type
!= o2
->type
)
3837 case operand::OP_IF
:
3839 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3840 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3841 /* ??? Properly compare c-exprs. */
3842 if (if1
->cond
!= if2
->cond
)
3844 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3846 if (if1
->falseexpr
!= if2
->falseexpr
3848 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3852 case operand::OP_WITH
:
3854 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3855 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3856 if (with1
->with
!= with2
->with
)
3858 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3863 /* We've hit a result. Time to compare capture-infos - this is required
3864 in addition to the conservative pointer-equivalency of the result IL. */
3865 capture_info
cinfo1 (s1
, o1
, true);
3866 capture_info
cinfo2 (s2
, o2
, true);
3868 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3869 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3872 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3874 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3875 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3876 || (cinfo1
.info
[i
].force_no_side_effects_p
3877 != cinfo2
.info
[i
].force_no_side_effects_p
)
3878 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3879 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3880 /* toplevel_msk is an optimization */
3881 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3882 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3883 /* the pointer back to the capture is for diagnostics only */)
3887 /* ??? Deep-compare the actual result. */
3892 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3893 const key_type
&candidate
)
3895 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3899 /* Main entry to generate code for matching GIMPLE IL off the decision
3903 decision_tree::gen (vec
<FILE *> &files
, bool gimple
)
3909 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3910 "a total number of %u nodes\n",
3911 gimple
? "GIMPLE" : "GENERIC",
3912 root
->num_leafs
, root
->max_level
, root
->total_size
);
3914 /* First split out the transform part of equal leafs. */
3917 for (sinfo_map_t::iterator iter
= si
.begin ();
3918 iter
!= si
.end (); ++iter
)
3920 sinfo
*s
= (*iter
).second
;
3921 /* Do not split out single uses. */
3928 fprintf (stderr
, "found %u uses of", s
->cnt
);
3929 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3932 /* Cycle the file buffers. */
3933 FILE *f
= choose_output (files
);
3935 /* Generate a split out function with the leaf transform code. */
3936 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3939 fp_decl (f
, "\nbool\n"
3940 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3941 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3942 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3947 fp_decl (f
, "\ntree\n"
3948 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3949 (*iter
).second
->fname
);
3950 for (unsigned i
= 0;
3951 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3952 fp_decl (f
, " tree ARG_UNUSED (_p%d),", i
);
3953 fp_decl (f
, " tree *captures");
3955 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3957 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3959 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3960 fp_decl (f
, ",\n const enum tree_code ARG_UNUSED (%s)",
3961 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3962 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3963 fp_decl (f
, ",\n const combined_fn ARG_UNUSED (%s)",
3964 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3967 fp_decl_done (f
, ")");
3969 fprintf_indent (f
, 2, "const bool debug_dump = "
3970 "dump_file && (dump_flags & TDF_FOLDING);\n");
3971 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3973 fprintf (f
, " return false;\n");
3975 fprintf (f
, " return NULL_TREE;\n");
3978 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3980 for (unsigned n
= 1; n
<= 5; ++n
)
3982 bool has_kids_p
= false;
3984 /* First generate split-out functions. */
3985 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3987 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3988 expr
*e
= static_cast<expr
*>(dop
->op
);
3989 if (e
->ops
.length () != n
3990 /* Builtin simplifications are somewhat premature on
3991 GENERIC. The following drops patterns with outermost
3992 calls. It's easy to emit overloads for function code
3993 though if necessary. */
3995 && e
->operation
->kind
!= id_base::CODE
))
3999 /* Cycle the file buffers. */
4000 FILE *f
= choose_output (files
);
4003 fp_decl (f
, "\nbool\n"
4004 "gimple_simplify_%s (gimple_match_op *res_op,"
4005 " gimple_seq *seq,\n"
4006 " tree (*valueize)(tree) "
4007 "ATTRIBUTE_UNUSED,\n"
4008 " code_helper ARG_UNUSED (code), tree "
4009 "ARG_UNUSED (type)",
4012 fp_decl (f
, "\ntree\n"
4013 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
4014 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
4016 for (unsigned i
= 0; i
< n
; ++i
)
4017 fp_decl (f
, ", tree _p%d", i
);
4018 fp_decl_done (f
, ")");
4020 fprintf_indent (f
, 2, "const bool debug_dump = "
4021 "dump_file && (dump_flags & TDF_FOLDING);\n");
4022 dop
->gen_kids (f
, 2, gimple
, 0);
4024 fprintf (f
, " return false;\n");
4026 fprintf (f
, " return NULL_TREE;\n");
4031 /* If this main entry has no children, avoid generating code
4032 with compiler warnings, by generating a simple stub. */
4036 /* Cycle the file buffers. */
4037 FILE *f
= choose_output (files
);
4040 fp_decl (f
, "\nbool\n"
4041 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
4042 " tree (*)(tree), code_helper,\n"
4045 fp_decl (f
, "\ntree\n"
4046 "generic_simplify (location_t, enum tree_code,\n"
4048 for (unsigned i
= 0; i
< n
; ++i
)
4049 fp_decl (f
, ", tree");
4050 fp_decl_done (f
, ")");
4053 fprintf (f
, " return false;\n");
4055 fprintf (f
, " return NULL_TREE;\n");
4061 /* Cycle the file buffers. */
4062 FILE *f
= choose_output (files
);
4064 /* Then generate the main entry with the outermost switch and
4065 tail-calls to the split-out functions. */
4067 fp_decl (f
, "\nbool\n"
4068 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
4069 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4070 " code_helper code, const tree type");
4072 fp_decl (f
, "\ntree\n"
4073 "generic_simplify (location_t loc, enum tree_code code, "
4074 "const tree type ATTRIBUTE_UNUSED");
4075 for (unsigned i
= 0; i
< n
; ++i
)
4076 fp_decl (f
, ", tree _p%d", i
);
4077 fp_decl_done (f
, ")");
4081 fprintf (f
, " switch (code.get_rep())\n"
4084 fprintf (f
, " switch (code)\n"
4086 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
4088 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
4089 expr
*e
= static_cast<expr
*>(dop
->op
);
4090 if (e
->ops
.length () != n
4091 /* Builtin simplifications are somewhat premature on
4092 GENERIC. The following drops patterns with outermost
4093 calls. It's easy to emit overloads for function code
4094 though if necessary. */
4096 && e
->operation
->kind
!= id_base::CODE
))
4099 if (*e
->operation
== CONVERT_EXPR
4100 || *e
->operation
== NOP_EXPR
)
4101 fprintf (f
, " CASE_CONVERT:\n");
4103 fprintf (f
, " case %s%s:\n",
4104 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
4107 fprintf (f
, " return gimple_simplify_%s (res_op, "
4108 "seq, valueize, code, type", e
->operation
->id
);
4110 fprintf (f
, " return generic_simplify_%s (loc, code, type",
4112 for (unsigned j
= 0; j
< n
; ++j
)
4113 fprintf (f
, ", _p%d", j
);
4114 fprintf (f
, ");\n");
4116 fprintf (f
, " default:;\n"
4120 fprintf (f
, " return false;\n");
4122 fprintf (f
, " return NULL_TREE;\n");
4127 /* Output code to implement the predicate P from the decision tree DT. */
4130 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
4132 fp_decl (f
, "\nbool\n%s%s (tree t%s%s)",
4133 gimple
? "gimple_" : "tree_", p
->id
,
4134 p
->nargs
> 0 ? ", tree *res_ops" : "",
4135 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4136 fp_decl_done (f
, "");
4138 /* Conveniently make 'type' available. */
4139 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
4140 fprintf_indent (f
, 2, "const bool debug_dump = "
4141 "dump_file && (dump_flags & TDF_FOLDING);\n");
4144 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4145 dt
.root
->gen_kids (f
, 2, gimple
, 0);
4147 fprintf_indent (f
, 2, "return false;\n"
4151 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4154 write_header (FILE *f
, const char *head
)
4156 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4157 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4158 fprintf (f
, "#pragma GCC diagnostic push\n");
4159 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-variable\"\n");
4160 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-function\"\n");
4162 /* Include the header instead of writing it awkwardly quoted here. */
4164 fprintf (f
, "\n#include \"%s\"\n", head
);
4174 parser (cpp_reader
*, bool gimple
);
4177 const cpp_token
*next ();
4178 const cpp_token
*peek (unsigned = 1);
4179 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4180 const cpp_token
*expect (enum cpp_ttype
);
4181 const cpp_token
*eat_token (enum cpp_ttype
);
4182 const char *get_string ();
4183 const char *get_ident ();
4184 const cpp_token
*eat_ident (const char *);
4185 const char *get_number ();
4187 unsigned get_internal_capture_id ();
4189 id_base
*parse_operation (unsigned char &);
4190 operand
*parse_capture (operand
*, bool);
4191 operand
*parse_expr ();
4192 c_expr
*parse_c_expr (cpp_ttype
);
4193 operand
*parse_op ();
4195 void record_operlist (location_t
, user_id
*);
4197 void parse_pattern ();
4198 operand
*parse_result (operand
*, predicate_id
*);
4199 void push_simplify (simplify::simplify_kind
,
4200 vec
<simplify
*>&, operand
*, operand
*);
4201 void parse_simplify (simplify::simplify_kind
,
4202 vec
<simplify
*>&, predicate_id
*, operand
*);
4203 void parse_for (location_t
);
4204 void parse_if (location_t
);
4205 void parse_predicates (location_t
);
4206 void parse_operator_list (location_t
);
4208 void finish_match_operand (operand
*);
4212 vec
<c_expr
*> active_ifs
;
4213 vec
<vec
<user_id
*> > active_fors
;
4214 hash_set
<user_id
*> *oper_lists_set
;
4215 vec
<user_id
*> oper_lists
;
4217 cid_map_t
*capture_ids
;
4221 vec
<simplify
*> simplifiers
;
4222 vec
<predicate_id
*> user_predicates
;
4223 bool parsing_match_operand
;
4226 /* Lexing helpers. */
4228 /* Read the next non-whitespace token from R. */
4233 const cpp_token
*token
;
4236 token
= cpp_get_token (r
);
4238 while (token
->type
== CPP_PADDING
);
4242 /* Peek at the next non-whitespace token from R. */
4245 parser::peek (unsigned num
)
4247 const cpp_token
*token
;
4251 token
= cpp_peek_token (r
, i
++);
4253 while (token
->type
== CPP_PADDING
4255 /* If we peek at EOF this is a fatal error as it leaves the
4256 cpp_reader in unusable state. Assume we really wanted a
4257 token and thus this EOF is unexpected. */
4258 if (token
->type
== CPP_EOF
)
4259 fatal_at (token
, "unexpected end of file");
4263 /* Peek at the next identifier token (or return NULL if the next
4264 token is not an identifier or equal to ID if supplied). */
4267 parser::peek_ident (const char *id
, unsigned num
)
4269 const cpp_token
*token
= peek (num
);
4270 if (token
->type
!= CPP_NAME
)
4276 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4277 if (strcmp (id
, t
) == 0)
4283 /* Read the next token from R and assert it is of type TK. */
4286 parser::expect (enum cpp_ttype tk
)
4288 const cpp_token
*token
= next ();
4289 if (token
->type
!= tk
)
4290 fatal_at (token
, "expected %s, got %s",
4291 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4296 /* Consume the next token from R and assert it is of type TK. */
4299 parser::eat_token (enum cpp_ttype tk
)
4304 /* Read the next token from R and assert it is of type CPP_STRING and
4305 return its value. */
4308 parser::get_string ()
4310 const cpp_token
*token
= expect (CPP_STRING
);
4311 return (const char *)token
->val
.str
.text
;
4314 /* Read the next token from R and assert it is of type CPP_NAME and
4315 return its value. */
4318 parser::get_ident ()
4320 const cpp_token
*token
= expect (CPP_NAME
);
4321 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4324 /* Eat an identifier token with value S from R. */
4327 parser::eat_ident (const char *s
)
4329 const cpp_token
*token
= peek ();
4330 const char *t
= get_ident ();
4331 if (strcmp (s
, t
) != 0)
4332 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4336 /* Read the next token from R and assert it is of type CPP_NUMBER and
4337 return its value. */
4340 parser::get_number ()
4342 const cpp_token
*token
= expect (CPP_NUMBER
);
4343 return (const char *)token
->val
.str
.text
;
4346 /* Return a capture ID that can be used internally. */
4349 parser::get_internal_capture_id ()
4351 unsigned newid
= capture_ids
->elements ();
4352 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4355 snprintf (id
, sizeof (id
), "__%u", newid
);
4356 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4358 fatal ("reserved capture id '%s' already used", id
);
4362 /* Record an operator-list use for transparent for handling. */
4365 parser::record_operlist (location_t loc
, user_id
*p
)
4367 if (!oper_lists_set
->add (p
))
4369 if (!oper_lists
.is_empty ()
4370 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4371 fatal_at (loc
, "User-defined operator list does not have the "
4372 "same number of entries as others used in the pattern");
4373 oper_lists
.safe_push (p
);
4377 /* Parse the operator ID, special-casing convert?, convert1? and
4381 parser::parse_operation (unsigned char &opt_grp
)
4383 const cpp_token
*id_tok
= peek ();
4384 char *alt_id
= NULL
;
4385 const char *id
= get_ident ();
4386 const cpp_token
*token
= peek ();
4388 if (token
->type
== CPP_QUERY
4389 && !(token
->flags
& PREV_WHITE
))
4391 if (!parsing_match_operand
)
4392 fatal_at (id_tok
, "conditional convert can only be used in "
4393 "match expression");
4394 if (ISDIGIT (id
[strlen (id
) - 1]))
4396 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4397 alt_id
= xstrdup (id
);
4398 alt_id
[strlen (id
) - 1] = '\0';
4400 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4404 eat_token (CPP_QUERY
);
4406 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4408 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4411 user_id
*p
= dyn_cast
<user_id
*> (op
);
4412 if (p
&& p
->is_oper_list
)
4414 if (active_fors
.length() == 0)
4415 record_operlist (id_tok
->src_loc
, p
);
4417 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4423 capture = '@'<number> */
4426 parser::parse_capture (operand
*op
, bool require_existing
)
4428 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4429 const cpp_token
*token
= peek ();
4430 const char *id
= NULL
;
4431 bool value_match
= false;
4432 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4433 if (token
->type
== CPP_ATSIGN
4434 && ! (token
->flags
& PREV_WHITE
)
4435 && parsing_match_operand
)
4437 eat_token (CPP_ATSIGN
);
4441 if (token
->type
== CPP_NUMBER
)
4443 else if (token
->type
== CPP_NAME
)
4446 fatal_at (token
, "expected number or identifier");
4447 unsigned next_id
= capture_ids
->elements ();
4449 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4452 if (require_existing
)
4453 fatal_at (src_loc
, "unknown capture id");
4456 return new capture (src_loc
, num
, op
, value_match
);
4459 /* Parse an expression
4460 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4463 parser::parse_expr ()
4465 const cpp_token
*token
= peek ();
4466 unsigned char opt_grp
;
4467 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4470 bool is_commutative
= false;
4471 bool force_capture
= false;
4472 const char *expr_type
= NULL
;
4474 if (!parsing_match_operand
4475 && token
->type
== CPP_NOT
4476 && !(token
->flags
& PREV_WHITE
))
4478 eat_token (CPP_NOT
);
4479 e
->force_leaf
= true;
4482 if (token
->type
== CPP_COLON
4483 && !(token
->flags
& PREV_WHITE
))
4485 eat_token (CPP_COLON
);
4487 if (token
->type
== CPP_NAME
4488 && !(token
->flags
& PREV_WHITE
))
4490 const char *s
= get_ident ();
4491 if (!parsing_match_operand
)
4501 = dyn_cast
<operator_id
*> (e
->operation
))
4503 if (!commutative_tree_code (o
->code
)
4504 && !comparison_code_p (o
->code
))
4505 fatal_at (token
, "operation is not commutative");
4507 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4508 for (unsigned i
= 0;
4509 i
< p
->substitutes
.length (); ++i
)
4512 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4514 if (!commutative_tree_code (q
->code
)
4515 && !comparison_code_p (q
->code
))
4516 fatal_at (token
, "operation %s is not "
4517 "commutative", q
->id
);
4520 is_commutative
= true;
4522 else if (*sp
== 'C')
4523 is_commutative
= true;
4524 else if (*sp
== 's')
4526 e
->force_single_use
= true;
4527 force_capture
= true;
4530 fatal_at (token
, "flag %c not recognized", *sp
);
4537 fatal_at (token
, "expected flag or type specifying identifier");
4540 if (token
->type
== CPP_ATSIGN
4541 && !(token
->flags
& PREV_WHITE
))
4542 op
= parse_capture (e
, false);
4543 else if (force_capture
)
4545 unsigned num
= get_internal_capture_id ();
4546 op
= new capture (token
->src_loc
, num
, e
, false);
4553 if (token
->type
== CPP_CLOSE_PAREN
)
4555 if (e
->operation
->nargs
!= -1
4556 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4557 fatal_at (token
, "'%s' expects %u operands, not %u",
4558 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4561 if (e
->ops
.length () == 2
4562 || commutative_op (e
->operation
) >= 0)
4563 e
->is_commutative
= true;
4565 fatal_at (token
, "only binary operators or functions with "
4566 "two arguments can be marked commutative, "
4567 "unless the operation is known to be inherently "
4570 e
->expr_type
= expr_type
;
4573 if (e
->ops
.length () != 1)
4574 fatal_at (token
, "only unary operations can be conditional");
4575 e
->opt_grp
= opt_grp
;
4579 else if (!(token
->flags
& PREV_WHITE
))
4580 fatal_at (token
, "expected expression operand");
4582 e
->append_op (parse_op ());
4587 /* Lex native C code delimited by START recording the preprocessing tokens
4588 for later processing.
4589 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4592 parser::parse_c_expr (cpp_ttype start
)
4594 const cpp_token
*token
;
4597 vec
<cpp_token
> code
= vNULL
;
4598 unsigned nr_stmts
= 0;
4599 location_t loc
= eat_token (start
)->src_loc
;
4600 if (start
== CPP_OPEN_PAREN
)
4601 end
= CPP_CLOSE_PAREN
;
4602 else if (start
== CPP_OPEN_BRACE
)
4603 end
= CPP_CLOSE_BRACE
;
4611 /* Count brace pairs to find the end of the expr to match. */
4612 if (token
->type
== start
)
4614 else if (token
->type
== end
4617 else if (token
->type
== CPP_EOF
)
4618 fatal_at (token
, "unexpected end of file");
4620 /* This is a lame way of counting the number of statements. */
4621 if (token
->type
== CPP_SEMICOLON
)
4624 /* If this is possibly a user-defined identifier mark it used. */
4625 if (token
->type
== CPP_NAME
)
4628 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4629 if (strcmp (str
, "return") == 0)
4630 fatal_at (token
, "return statement not allowed in C expression");
4631 id_base
*idb
= get_operator (str
);
4633 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4634 record_operlist (token
->src_loc
, p
);
4637 /* Record the token. */
4638 code
.safe_push (*token
);
4641 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4644 /* Parse an operand which is either an expression, a predicate or
4645 a standalone capture.
4646 op = predicate | expr | c_expr | capture */
4651 const cpp_token
*token
= peek ();
4652 class operand
*op
= NULL
;
4653 if (token
->type
== CPP_OPEN_PAREN
)
4655 eat_token (CPP_OPEN_PAREN
);
4657 eat_token (CPP_CLOSE_PAREN
);
4659 else if (token
->type
== CPP_OPEN_BRACE
)
4661 op
= parse_c_expr (CPP_OPEN_BRACE
);
4665 /* Remaining ops are either empty or predicates */
4666 if (token
->type
== CPP_NAME
)
4668 const char *id
= get_ident ();
4669 id_base
*opr
= get_operator (id
);
4671 fatal_at (token
, "expected predicate name");
4672 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4674 if (code1
->nargs
!= 0)
4675 fatal_at (token
, "using an operator with operands as predicate");
4676 /* Parse the zero-operand operator "predicates" as
4678 op
= new expr (opr
, token
->src_loc
);
4680 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4682 if (code2
->nargs
!= 0)
4683 fatal_at (token
, "using an operator with operands as predicate");
4684 /* Parse the zero-operand operator "predicates" as
4686 op
= new expr (opr
, token
->src_loc
);
4688 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4689 op
= new predicate (p
, token
->src_loc
);
4691 fatal_at (token
, "using an unsupported operator as predicate");
4692 if (!parsing_match_operand
)
4693 fatal_at (token
, "predicates are only allowed in match expression");
4695 if (token
->flags
& PREV_WHITE
)
4698 else if (token
->type
!= CPP_COLON
4699 && token
->type
!= CPP_ATSIGN
)
4700 fatal_at (token
, "expected expression or predicate");
4701 /* optionally followed by a capture and a predicate. */
4702 if (token
->type
== CPP_COLON
)
4703 fatal_at (token
, "not implemented: predicate on leaf operand");
4704 if (token
->type
== CPP_ATSIGN
)
4705 op
= parse_capture (op
, !parsing_match_operand
);
4711 /* Create a new simplify from the current parsing state and MATCH,
4712 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4715 parser::push_simplify (simplify::simplify_kind kind
,
4716 vec
<simplify
*>& simplifiers
,
4717 operand
*match
, operand
*result
)
4719 /* Build and push a temporary for operator list uses in expressions. */
4720 if (!oper_lists
.is_empty ())
4721 active_fors
.safe_push (oper_lists
);
4723 simplifiers
.safe_push
4724 (new simplify (kind
, last_id
++, match
, result
,
4725 active_fors
.copy (), capture_ids
));
4727 if (!oper_lists
.is_empty ())
4732 <result-op> = <op> | <if> | <with>
4733 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4734 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4738 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4740 const cpp_token
*token
= peek ();
4741 if (token
->type
!= CPP_OPEN_PAREN
)
4744 eat_token (CPP_OPEN_PAREN
);
4745 if (peek_ident ("if"))
4748 if_expr
*ife
= new if_expr (token
->src_loc
);
4749 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4750 if (peek ()->type
== CPP_OPEN_PAREN
)
4752 ife
->trueexpr
= parse_result (result
, matcher
);
4753 if (peek ()->type
== CPP_OPEN_PAREN
)
4754 ife
->falseexpr
= parse_result (result
, matcher
);
4755 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4756 ife
->falseexpr
= parse_op ();
4758 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4760 ife
->trueexpr
= parse_op ();
4761 if (peek ()->type
== CPP_OPEN_PAREN
)
4762 ife
->falseexpr
= parse_result (result
, matcher
);
4763 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4764 ife
->falseexpr
= parse_op ();
4766 /* If this if is immediately closed then it contains a
4767 manual matcher or is part of a predicate definition. */
4768 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4771 fatal_at (peek (), "manual transform not implemented");
4772 ife
->trueexpr
= result
;
4774 eat_token (CPP_CLOSE_PAREN
);
4777 else if (peek_ident ("with"))
4780 with_expr
*withe
= new with_expr (token
->src_loc
);
4781 /* Parse (with c-expr expr) as (if-with (true) expr). */
4782 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4783 withe
->with
->nr_stmts
= 0;
4784 withe
->subexpr
= parse_result (result
, matcher
);
4785 eat_token (CPP_CLOSE_PAREN
);
4788 else if (peek_ident ("switch"))
4790 token
= eat_ident ("switch");
4791 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4793 if_expr
*ife
= new if_expr (ifloc
);
4795 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4796 if (peek ()->type
== CPP_OPEN_PAREN
)
4797 ife
->trueexpr
= parse_result (result
, matcher
);
4799 ife
->trueexpr
= parse_op ();
4800 eat_token (CPP_CLOSE_PAREN
);
4801 if (peek ()->type
!= CPP_OPEN_PAREN
4802 || !peek_ident ("if", 2))
4803 fatal_at (token
, "switch can be implemented with a single if");
4804 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4806 if (peek ()->type
== CPP_OPEN_PAREN
)
4808 if (peek_ident ("if", 2))
4810 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4812 ife
->falseexpr
= new if_expr (ifloc
);
4813 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4814 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4815 if (peek ()->type
== CPP_OPEN_PAREN
)
4816 ife
->trueexpr
= parse_result (result
, matcher
);
4818 ife
->trueexpr
= parse_op ();
4819 eat_token (CPP_CLOSE_PAREN
);
4823 /* switch default clause */
4824 ife
->falseexpr
= parse_result (result
, matcher
);
4825 eat_token (CPP_CLOSE_PAREN
);
4831 /* switch default clause */
4832 ife
->falseexpr
= parse_op ();
4833 eat_token (CPP_CLOSE_PAREN
);
4837 eat_token (CPP_CLOSE_PAREN
);
4842 operand
*op
= result
;
4845 eat_token (CPP_CLOSE_PAREN
);
4851 simplify = 'simplify' <expr> <result-op>
4853 match = 'match' <ident> <expr> [<result-op>]
4854 and fill SIMPLIFIERS with the results. */
4857 parser::parse_simplify (simplify::simplify_kind kind
,
4858 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4861 /* Reset the capture map. */
4863 capture_ids
= new cid_map_t
;
4864 /* Reset oper_lists and set. */
4865 hash_set
<user_id
*> olist
;
4866 oper_lists_set
= &olist
;
4869 const cpp_token
*loc
= peek ();
4870 parsing_match_operand
= true;
4871 class operand
*match
= parse_op ();
4872 finish_match_operand (match
);
4873 parsing_match_operand
= false;
4874 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4875 fatal_at (loc
, "outermost expression cannot be captured");
4876 if (match
->type
== operand::OP_EXPR
4877 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4878 fatal_at (loc
, "outermost expression cannot be a predicate");
4880 /* Splice active_ifs onto result and continue parsing the
4882 if_expr
*active_if
= NULL
;
4883 for (int i
= active_ifs
.length (); i
> 0; --i
)
4885 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4886 ifc
->cond
= active_ifs
[i
-1];
4887 ifc
->trueexpr
= active_if
;
4890 if_expr
*outermost_if
= active_if
;
4891 while (active_if
&& active_if
->trueexpr
)
4892 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4894 const cpp_token
*token
= peek ();
4896 /* If this if is immediately closed then it is part of a predicate
4897 definition. Push it. */
4898 if (token
->type
== CPP_CLOSE_PAREN
)
4901 fatal_at (token
, "expected transform expression");
4904 active_if
->trueexpr
= result
;
4905 result
= outermost_if
;
4907 push_simplify (kind
, simplifiers
, match
, result
);
4911 operand
*tem
= parse_result (result
, matcher
);
4914 active_if
->trueexpr
= tem
;
4915 result
= outermost_if
;
4920 push_simplify (kind
, simplifiers
, match
, result
);
4923 /* Parsing of the outer control structures. */
4925 /* Parse a for expression
4926 for = '(' 'for' <subst>... <pattern> ')'
4927 subst = <ident> '(' <ident>... ')' */
4930 parser::parse_for (location_t
)
4932 auto_vec
<const cpp_token
*> user_id_tokens
;
4933 vec
<user_id
*> user_ids
= vNULL
;
4934 const cpp_token
*token
;
4935 unsigned min_n_opers
= 0, max_n_opers
= 0;
4940 if (token
->type
!= CPP_NAME
)
4943 /* Insert the user defined operators into the operator hash. */
4944 const char *id
= get_ident ();
4945 if (get_operator (id
, true) != NULL
)
4946 fatal_at (token
, "operator already defined");
4947 user_id
*op
= new user_id (id
);
4948 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4950 user_ids
.safe_push (op
);
4951 user_id_tokens
.safe_push (token
);
4953 eat_token (CPP_OPEN_PAREN
);
4956 while ((token
= peek_ident ()) != 0)
4958 const char *oper
= get_ident ();
4959 id_base
*idb
= get_operator (oper
, true);
4961 fatal_at (token
, "no such operator '%s'", oper
);
4965 else if (idb
->nargs
== -1)
4967 else if (idb
->nargs
!= arity
)
4968 fatal_at (token
, "operator '%s' with arity %d does not match "
4969 "others with arity %d", oper
, idb
->nargs
, arity
);
4971 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4974 if (p
->is_oper_list
)
4975 op
->substitutes
.safe_splice (p
->substitutes
);
4977 fatal_at (token
, "iterator cannot be used as operator-list");
4980 op
->substitutes
.safe_push (idb
);
4983 token
= expect (CPP_CLOSE_PAREN
);
4985 unsigned nsubstitutes
= op
->substitutes
.length ();
4986 if (nsubstitutes
== 0)
4987 fatal_at (token
, "A user-defined operator must have at least "
4988 "one substitution");
4989 if (max_n_opers
== 0)
4991 min_n_opers
= nsubstitutes
;
4992 max_n_opers
= nsubstitutes
;
4996 if (nsubstitutes
% min_n_opers
!= 0
4997 && min_n_opers
% nsubstitutes
!= 0)
4998 fatal_at (token
, "All user-defined identifiers must have a "
4999 "multiple number of operator substitutions of the "
5000 "smallest number of substitutions");
5001 if (nsubstitutes
< min_n_opers
)
5002 min_n_opers
= nsubstitutes
;
5003 else if (nsubstitutes
> max_n_opers
)
5004 max_n_opers
= nsubstitutes
;
5008 unsigned n_ids
= user_ids
.length ();
5010 fatal_at (token
, "for requires at least one user-defined identifier");
5013 if (token
->type
== CPP_CLOSE_PAREN
)
5014 fatal_at (token
, "no pattern defined in for");
5016 active_fors
.safe_push (user_ids
);
5020 if (token
->type
== CPP_CLOSE_PAREN
)
5026 /* Remove user-defined operators from the hash again. */
5027 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
5029 if (!user_ids
[i
]->used
)
5030 warning_at (user_id_tokens
[i
],
5031 "operator %s defined but not used", user_ids
[i
]->id
);
5032 operators
->remove_elt (user_ids
[i
]);
5036 /* Parse an identifier associated with a list of operators.
5037 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
5040 parser::parse_operator_list (location_t
)
5042 const cpp_token
*token
= peek ();
5043 const char *id
= get_ident ();
5045 if (get_operator (id
, true) != 0)
5046 fatal_at (token
, "operator %s already defined", id
);
5048 user_id
*op
= new user_id (id
, true);
5051 while ((token
= peek_ident ()) != 0)
5054 const char *oper
= get_ident ();
5055 id_base
*idb
= get_operator (oper
, true);
5058 fatal_at (token
, "no such operator '%s'", oper
);
5062 else if (idb
->nargs
== -1)
5064 else if (arity
!= idb
->nargs
)
5065 fatal_at (token
, "operator '%s' with arity %d does not match "
5066 "others with arity %d", oper
, idb
->nargs
, arity
);
5068 /* We allow composition of multiple operator lists. */
5069 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
5070 op
->substitutes
.safe_splice (p
->substitutes
);
5072 op
->substitutes
.safe_push (idb
);
5075 // Check that there is no junk after id-list
5077 if (token
->type
!= CPP_CLOSE_PAREN
)
5078 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
5080 if (op
->substitutes
.length () == 0)
5081 fatal_at (token
, "operator-list cannot be empty");
5084 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
5088 /* Parse an outer if expression.
5089 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
5092 parser::parse_if (location_t
)
5094 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
5096 const cpp_token
*token
= peek ();
5097 if (token
->type
== CPP_CLOSE_PAREN
)
5098 fatal_at (token
, "no pattern defined in if");
5100 active_ifs
.safe_push (ifexpr
);
5104 if (token
->type
== CPP_CLOSE_PAREN
)
5112 /* Parse a list of predefined predicate identifiers.
5113 preds = '(' 'define_predicates' <ident>... ')' */
5116 parser::parse_predicates (location_t
)
5120 const cpp_token
*token
= peek ();
5121 if (token
->type
!= CPP_NAME
)
5124 add_predicate (get_ident ());
5129 /* Parse outer control structures.
5130 pattern = <preds>|<for>|<if>|<simplify>|<match> */
5133 parser::parse_pattern ()
5135 /* All clauses start with '('. */
5136 eat_token (CPP_OPEN_PAREN
);
5137 const cpp_token
*token
= peek ();
5138 const char *id
= get_ident ();
5139 if (strcmp (id
, "simplify") == 0)
5141 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
5144 else if (strcmp (id
, "match") == 0)
5146 bool with_args
= false;
5147 location_t e_loc
= peek ()->src_loc
;
5148 if (peek ()->type
== CPP_OPEN_PAREN
)
5150 eat_token (CPP_OPEN_PAREN
);
5153 const char *name
= get_ident ();
5154 id_base
*id1
= get_operator (name
);
5158 p
= add_predicate (name
);
5159 user_predicates
.safe_push (p
);
5161 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5164 fatal_at (token
, "cannot add a match to a non-predicate ID");
5165 /* Parse (match <id> <arg>... (match-expr)) here. */
5169 capture_ids
= new cid_map_t
;
5170 e
= new expr (p
, e_loc
);
5171 while (peek ()->type
== CPP_ATSIGN
)
5172 e
->append_op (parse_capture (NULL
, false));
5173 eat_token (CPP_CLOSE_PAREN
);
5176 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5177 || (!e
&& p
->nargs
!= 0)))
5178 fatal_at (token
, "non-matching number of match operands");
5179 p
->nargs
= e
? e
->ops
.length () : 0;
5180 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5183 else if (strcmp (id
, "for") == 0)
5184 parse_for (token
->src_loc
);
5185 else if (strcmp (id
, "if") == 0)
5186 parse_if (token
->src_loc
);
5187 else if (strcmp (id
, "define_predicates") == 0)
5189 if (active_ifs
.length () > 0
5190 || active_fors
.length () > 0)
5191 fatal_at (token
, "define_predicates inside if or for is not supported");
5192 parse_predicates (token
->src_loc
);
5194 else if (strcmp (id
, "define_operator_list") == 0)
5196 if (active_ifs
.length () > 0
5197 || active_fors
.length () > 0)
5198 fatal_at (token
, "operator-list inside if or for is not supported");
5199 parse_operator_list (token
->src_loc
);
5202 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5203 active_ifs
.length () == 0 && active_fors
.length () == 0
5204 ? "'define_predicates', " : "");
5206 eat_token (CPP_CLOSE_PAREN
);
5209 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5213 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5218 if (capture
*c
= dyn_cast
<capture
*> (op
))
5220 cpts
[c
->where
].safe_push (c
);
5221 walk_captures (c
->what
, cpts
);
5223 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5224 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5225 walk_captures (e
->ops
[i
], cpts
);
5228 /* Finish up OP which is a match operand. */
5231 parser::finish_match_operand (operand
*op
)
5233 /* Look for matching captures, diagnose mis-uses of @@ and apply
5234 early lowering and distribution of value_match. */
5235 auto_vec
<vec
<capture
*> > cpts
;
5236 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5237 walk_captures (op
, cpts
);
5238 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5240 capture
*value_match
= NULL
;
5241 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5243 if (cpts
[i
][j
]->value_match
)
5246 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5247 value_match
= cpts
[i
][j
];
5250 if (cpts
[i
].length () == 1 && value_match
)
5251 fatal_at (value_match
->location
, "@@ without a matching capture");
5254 /* Duplicate prevailing capture with the existing ID, create
5255 a fake ID and rewrite all captures to use it. This turns
5256 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5257 value_match
->what
= new capture (value_match
->location
,
5259 value_match
->what
, false);
5260 /* Create a fake ID and rewrite all captures to use it. */
5261 unsigned newid
= get_internal_capture_id ();
5262 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5264 cpts
[i
][j
]->where
= newid
;
5265 cpts
[i
][j
]->value_match
= true;
5272 /* Main entry of the parser. Repeatedly parse outer control structures. */
5274 parser::parser (cpp_reader
*r_
, bool gimple_
)
5279 active_fors
= vNULL
;
5280 simplifiers
= vNULL
;
5281 oper_lists_set
= NULL
;
5284 user_predicates
= vNULL
;
5285 parsing_match_operand
= false;
5288 const cpp_token
*token
= next ();
5289 while (token
->type
!= CPP_EOF
)
5291 _cpp_backup_tokens (r
, 1);
5298 /* Helper for the linemap code. */
5301 round_alloc_size (size_t s
)
5307 /* Construct and display the help menu. */
5312 const char *usage
= "Usage:\n"
5313 " %s [--gimple|--generic] [-v[v]] <input>\n"
5314 " %s [options] [--include=FILE] --header=FILE <input> <output>...\n";
5315 fprintf (stderr
, usage
, progname
, progname
);
5318 /* Write out the correct include to the match-head fle containing the helper
5322 write_header_includes (bool gimple
, FILE *header_file
)
5325 fprintf (header_file
, "#include \"gimple-match-head.cc\"\n");
5327 fprintf (header_file
, "#include \"generic-match-head.cc\"\n");
5330 /* The genmatch generator program. It reads from a pattern description
5331 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5334 main (int argc
, char **argv
)
5338 progname
= "genmatch";
5341 char *s_header_file
= NULL
;
5342 char *s_include_file
= NULL
;
5343 auto_vec
<char *> files
;
5345 int last_file
= argc
- 1;
5346 for (int i
= argc
- 1; i
>= 1; --i
)
5348 if (strcmp (argv
[i
], "--gimple") == 0)
5350 else if (strcmp (argv
[i
], "--generic") == 0)
5352 else if (strncmp (argv
[i
], "--header=", 9) == 0)
5353 s_header_file
= &argv
[i
][9];
5354 else if (strncmp (argv
[i
], "--include=", 10) == 0)
5355 s_include_file
= &argv
[i
][10];
5356 else if (strcmp (argv
[i
], "-v") == 0)
5358 else if (strcmp (argv
[i
], "-vv") == 0)
5360 else if (strncmp (argv
[i
], "--", 2) != 0 && last_file
-- == i
)
5361 files
.safe_push (argv
[i
]);
5369 /* Validate if the combinations are valid. */
5370 if ((files
.length () > 1 && !s_header_file
) || files
.is_empty ())
5376 if (!s_include_file
)
5377 s_include_file
= s_header_file
;
5379 /* Input file is the last in the reverse list. */
5380 input
= files
.pop ();
5382 line_table
= XCNEW (class line_maps
);
5383 linemap_init (line_table
, 0);
5384 line_table
->reallocator
= xrealloc
;
5385 line_table
->round_alloc_size
= round_alloc_size
;
5387 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5388 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5389 cb
->diagnostic
= diagnostic_cb
;
5391 /* Add the build directory to the #include "" search path. */
5392 cpp_dir
*dir
= XCNEW (cpp_dir
);
5393 dir
->name
= getpwd ();
5395 dir
->name
= ASTRDUP (".");
5396 cpp_set_include_chains (r
, dir
, NULL
, false);
5398 if (!cpp_read_main_file (r
, input
))
5400 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5401 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5403 null_id
= new id_base (id_base::NULL_ID
, "null");
5405 /* Pre-seed operators. */
5406 operators
= new hash_table
<id_base
> (1024);
5407 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5408 add_operator (SYM, # SYM, # TYPE, NARGS);
5409 #define END_OF_BASE_TREE_CODES
5411 #undef END_OF_BASE_TREE_CODES
5414 /* Pre-seed builtin functions.
5415 ??? Cannot use N (name) as that is targetm.emultls.get_address
5416 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5417 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5418 add_function (ENUM, "CFN_" # ENUM);
5419 #include "builtins.def"
5421 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5422 add_function (IFN_##CODE, "CFN_" #CODE);
5423 #include "internal-fn.def"
5426 parser
p (r
, gimple
);
5428 /* Create file buffers. */
5429 int n_parts
= files
.is_empty () ? 1 : files
.length ();
5430 auto_vec
<FILE *> parts (n_parts
);
5431 if (files
.is_empty ())
5433 parts
.quick_push (stdout
);
5434 write_header (stdout
, s_include_file
);
5435 write_header_includes (gimple
, stdout
);
5439 for (char *s_file
: files
)
5441 parts
.quick_push (fopen (s_file
, "w"));
5442 write_header (parts
.last (), s_include_file
);
5445 header_file
= fopen (s_header_file
, "w");
5446 fprintf (header_file
, "#ifndef GCC_GIMPLE_MATCH_AUTO_H\n"
5447 "#define GCC_GIMPLE_MATCH_AUTO_H\n");
5448 write_header_includes (gimple
, header_file
);
5451 /* Go over all predicates defined with patterns and perform
5452 lowering and code generation. */
5453 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5455 predicate_id
*pred
= p
.user_predicates
[i
];
5456 lower (pred
->matchers
, gimple
);
5459 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5460 print_matches (pred
->matchers
[j
]);
5463 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5464 dt
.insert (pred
->matchers
[j
], j
);
5469 /* Cycle the file buffers. */
5470 FILE *f
= choose_output (parts
);
5472 write_predicate (f
, pred
, dt
, gimple
);
5475 /* Lower the main simplifiers and generate code for them. */
5476 lower (p
.simplifiers
, gimple
);
5479 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5480 print_matches (p
.simplifiers
[i
]);
5483 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5484 dt
.insert (p
.simplifiers
[i
], i
);
5489 dt
.gen (parts
, gimple
);
5491 for (FILE *f
: parts
)
5493 fprintf (f
, "#pragma GCC diagnostic pop\n");
5499 fprintf (header_file
, "\n#endif /* GCC_GIMPLE_MATCH_AUTO_H. */\n");
5500 fclose (header_file
);
5504 cpp_finish (r
, NULL
);