1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2023 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
186 /* Secondary stream for fp_decl. */
187 static FILE *header_file
;
189 /* Start or continue emitting a declaration in fprintf-like manner,
190 printing both to F and global header_file, if non-null. */
192 #if GCC_VERSION >= 4001
193 __attribute__((format (printf
, 2, 3)))
195 fp_decl (FILE *f
, const char *format
, ...)
198 va_start (ap
, format
);
199 vfprintf (f
, format
, ap
);
205 va_start (ap
, format
);
206 vfprintf (header_file
, format
, ap
);
210 /* Finish a declaration being emitted by fp_decl. */
212 fp_decl_done (FILE *f
, const char *trailer
)
214 fprintf (f
, "%s\n", trailer
);
216 fprintf (header_file
, "%s;", trailer
);
220 output_line_directive (FILE *f
, location_t location
,
221 bool dumpfile
= false, bool fnargs
= false)
223 const line_map_ordinary
*map
;
224 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
225 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
228 /* When writing to a dumpfile only dump the filename. */
229 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
230 #if defined(DIR_SEPARATOR_2)
231 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
232 if (pos2
&& (!file
|| (pos2
> file
)))
241 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
243 fprintf (f
, "%s:%d", file
, loc
.line
);
245 else if (verbose
>= 2)
246 /* Other gen programs really output line directives here, at least for
247 development it's right now more convenient to have line information
248 from the generated file. Still keep the directives as comment for now
249 to easily back-point to the meta-description. */
250 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
253 /* Find the file to write into next. We try to evenly distribute the contents
254 over the different files. */
256 #define SIZED_BASED_CHUNKS 1
259 choose_output (const vec
<FILE *> &parts
)
261 #ifdef SIZED_BASED_CHUNKS
262 FILE *shortest
= NULL
;
264 for (FILE *part
: parts
)
266 long len
= ftell (part
);
267 if (!shortest
|| min
> len
)
268 shortest
= part
, min
= len
;
272 static int current_file
;
273 return parts
[current_file
++ % parts
.length ()];
278 /* Pull in tree codes and builtin function codes from their
281 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
288 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
289 enum built_in_function
{
290 #include "builtins.def"
294 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
296 #include "internal-fn.def"
301 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
302 CFN_##ENUM = int (ENUM),
303 #include "builtins.def"
305 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
306 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
307 #include "internal-fn.def"
312 #include "case-cfn-macros.h"
314 /* Return true if CODE represents a commutative tree code. Otherwise
317 commutative_tree_code (enum tree_code code
)
323 case MULT_HIGHPART_EXPR
:
338 case WIDEN_MULT_EXPR
:
339 case VEC_WIDEN_MULT_HI_EXPR
:
340 case VEC_WIDEN_MULT_LO_EXPR
:
341 case VEC_WIDEN_MULT_EVEN_EXPR
:
342 case VEC_WIDEN_MULT_ODD_EXPR
:
351 /* Return true if CODE represents a ternary tree code for which the
352 first two operands are commutative. Otherwise return false. */
354 commutative_ternary_tree_code (enum tree_code code
)
358 case WIDEN_MULT_PLUS_EXPR
:
359 case WIDEN_MULT_MINUS_EXPR
:
369 /* Return true if CODE is a comparison. */
372 comparison_code_p (enum tree_code code
)
399 /* Base class for all identifiers the parser knows. */
401 class id_base
: public nofree_ptr_hash
<id_base
>
404 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
406 id_base (id_kind
, const char *, int = -1);
412 /* hash_table support. */
413 static inline hashval_t
hash (const id_base
*);
414 static inline int equal (const id_base
*, const id_base
*);
418 id_base::hash (const id_base
*op
)
424 id_base::equal (const id_base
*op1
,
427 return (op1
->hashval
== op2
->hashval
428 && strcmp (op1
->id
, op2
->id
) == 0);
431 /* The special id "null", which matches nothing. */
432 static id_base
*null_id
;
434 /* Hashtable of known pattern operators. This is pre-seeded from
435 all known tree codes and all known builtin function ids. */
436 static hash_table
<id_base
> *operators
;
438 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
443 hashval
= htab_hash_string (id
);
446 /* Identifier that maps to a tree code. */
448 class operator_id
: public id_base
451 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
453 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
458 /* Identifier that maps to a builtin or internal function code. */
460 class fn_id
: public id_base
463 fn_id (enum built_in_function fn_
, const char *id_
)
464 : id_base (id_base::FN
, id_
), fn (fn_
) {}
465 fn_id (enum internal_fn fn_
, const char *id_
)
466 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
472 /* Identifier that maps to a user-defined predicate. */
474 class predicate_id
: public id_base
477 predicate_id (const char *id_
)
478 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
479 vec
<simplify
*> matchers
;
482 /* Identifier that maps to a operator defined by a 'for' directive. */
484 class user_id
: public id_base
487 user_id (const char *id_
, bool is_oper_list_
= false)
488 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
489 used (false), is_oper_list (is_oper_list_
) {}
490 vec
<id_base
*> substitutes
;
498 is_a_helper
<fn_id
*>::test (id_base
*id
)
500 return id
->kind
== id_base::FN
;
506 is_a_helper
<operator_id
*>::test (id_base
*id
)
508 return id
->kind
== id_base::CODE
;
514 is_a_helper
<predicate_id
*>::test (id_base
*id
)
516 return id
->kind
== id_base::PREDICATE
;
522 is_a_helper
<user_id
*>::test (id_base
*id
)
524 return id
->kind
== id_base::USER
;
527 /* If ID has a pair of consecutive, commutative operands, return the
528 index of the first, otherwise return -1. */
531 commutative_op (id_base
*id
)
533 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
535 if (commutative_tree_code (code
->code
)
536 || commutative_ternary_tree_code (code
->code
))
540 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
567 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
569 int res
= commutative_op (uid
->substitutes
[0]);
572 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
573 if (res
!= commutative_op (uid
->substitutes
[i
]))
580 /* Add a predicate identifier to the hash. */
582 static predicate_id
*
583 add_predicate (const char *id
)
585 predicate_id
*p
= new predicate_id (id
);
586 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
588 fatal ("duplicate id definition");
593 /* Add a tree code identifier to the hash. */
596 add_operator (enum tree_code code
, const char *id
,
597 const char *tcc
, unsigned nargs
)
599 if (strcmp (tcc
, "tcc_unary") != 0
600 && strcmp (tcc
, "tcc_binary") != 0
601 && strcmp (tcc
, "tcc_comparison") != 0
602 && strcmp (tcc
, "tcc_expression") != 0
603 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
604 && strcmp (tcc
, "tcc_reference") != 0
605 /* To have INTEGER_CST and friends as "predicate operators". */
606 && strcmp (tcc
, "tcc_constant") != 0
607 /* And allow CONSTRUCTOR for vector initializers. */
608 && !(code
== CONSTRUCTOR
)
609 /* Allow SSA_NAME as predicate operator. */
610 && !(code
== SSA_NAME
))
612 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
613 if (code
== ADDR_EXPR
)
615 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
616 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
618 fatal ("duplicate id definition");
622 /* Add a built-in or internal function identifier to the hash. ID is
623 the name of its CFN_* enumeration value. */
625 template <typename T
>
627 add_function (T code
, const char *id
)
629 fn_id
*fn
= new fn_id (code
, id
);
630 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
632 fatal ("duplicate id definition");
636 /* Helper for easy comparing ID with tree code CODE. */
639 operator==(id_base
&id
, enum tree_code code
)
641 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
642 return oid
->code
== code
;
646 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
649 get_operator (const char *id
, bool allow_null
= false)
651 if (allow_null
&& strcmp (id
, "null") == 0)
654 id_base
tem (id_base::CODE
, id
);
656 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
659 /* If this is a user-defined identifier track whether it was used. */
660 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
666 bool all_upper
= true;
667 bool all_lower
= true;
668 for (unsigned int i
= 0; id
[i
]; ++i
)
671 else if (ISLOWER (id
[i
]))
675 /* Try in caps with _EXPR appended. */
676 id2
= ACONCAT ((id
, "_EXPR", NULL
));
677 for (unsigned int i
= 0; id2
[i
]; ++i
)
678 id2
[i
] = TOUPPER (id2
[i
]);
680 else if (all_upper
&& startswith (id
, "IFN_"))
681 /* Try CFN_ instead of IFN_. */
682 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
683 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
684 /* Try prepending CFN_. */
685 id2
= ACONCAT (("CFN_", id
, NULL
));
689 new (&tem
) id_base (id_base::CODE
, id2
);
690 return operators
->find_with_hash (&tem
, tem
.hashval
);
693 /* Return the comparison operators that results if the operands are
694 swapped. This is safe for floating-point. */
697 swap_tree_comparison (operator_id
*p
)
709 return get_operator ("LT_EXPR");
711 return get_operator ("LE_EXPR");
713 return get_operator ("GT_EXPR");
715 return get_operator ("GE_EXPR");
717 return get_operator ("UNLT_EXPR");
719 return get_operator ("UNLE_EXPR");
721 return get_operator ("UNGT_EXPR");
723 return get_operator ("UNGE_EXPR");
729 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
732 /* The AST produced by parsing of the pattern definitions. */
737 /* The base class for operands. */
741 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
742 operand (enum op_type type_
, location_t loc_
)
743 : type (type_
), location (loc_
) {}
746 virtual void gen_transform (FILE *, int, const char *, bool, int,
747 const char *, capture_info
*,
750 { gcc_unreachable (); }
753 /* A predicate operand. Predicates are leafs in the AST. */
755 class predicate
: public operand
758 predicate (predicate_id
*p_
, location_t loc
)
759 : operand (OP_PREDICATE
, loc
), p (p_
) {}
763 /* An operand that constitutes an expression. Expressions include
764 function calls and user-defined predicate invocations. */
766 class expr
: public operand
769 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
770 : operand (OP_EXPR
, loc
), operation (operation_
),
771 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
772 is_generic (false), force_single_use (false), force_leaf (false),
775 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
776 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
777 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
778 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
779 void append_op (operand
*op
) { ops
.safe_push (op
); }
780 /* The operator and its operands. */
783 /* An explicitely specified type - used exclusively for conversions. */
784 const char *expr_type
;
785 /* Whether the operation is to be applied commutatively. This is
786 later lowered to two separate patterns. */
788 /* Whether the expression is expected to be in GENERIC form. */
790 /* Whether pushing any stmt to the sequence should be conditional
791 on this expression having a single-use. */
792 bool force_single_use
;
793 /* Whether in the result expression this should be a leaf node
794 with any children simplified down to simple operands. */
796 /* If non-zero, the group for optional handling. */
797 unsigned char opt_grp
;
798 void gen_transform (FILE *f
, int, const char *, bool, int,
799 const char *, capture_info
*,
800 dt_operand
** = 0, int = 0) override
;
803 /* An operator that is represented by native C code. This is always
804 a leaf operand in the AST. This class is also used to represent
805 the code to be generated for 'if' and 'with' expressions. */
807 class c_expr
: public operand
810 /* A mapping of an identifier and its replacement. Used to apply
816 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
819 c_expr (cpp_reader
*r_
, location_t loc
,
820 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
821 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
822 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
823 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
824 /* cpplib tokens and state to transform this back to source. */
827 cid_map_t
*capture_ids
;
828 /* The number of statements parsed (well, the number of ';'s). */
830 /* The identifier replacement vector. */
832 void gen_transform (FILE *f
, int, const char *, bool, int,
833 const char *, capture_info
*,
834 dt_operand
** = 0, int = 0) final override
;
837 /* A wrapper around another operand that captures its value. */
839 class capture
: public operand
842 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
843 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
845 /* Identifier index for the value. */
847 /* Whether in a match of two operands the compare should be for
848 equal values rather than equal atoms (boils down to a type
851 /* The captured value. */
853 void gen_transform (FILE *f
, int, const char *, bool, int,
854 const char *, capture_info
*,
855 dt_operand
** = 0, int = 0) final override
;
860 class if_expr
: public operand
863 if_expr (location_t loc
)
864 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
870 /* with expression. */
872 class with_expr
: public operand
875 with_expr (location_t loc
)
876 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
884 is_a_helper
<capture
*>::test (operand
*op
)
886 return op
->type
== operand::OP_CAPTURE
;
892 is_a_helper
<predicate
*>::test (operand
*op
)
894 return op
->type
== operand::OP_PREDICATE
;
900 is_a_helper
<c_expr
*>::test (operand
*op
)
902 return op
->type
== operand::OP_C_EXPR
;
908 is_a_helper
<expr
*>::test (operand
*op
)
910 return op
->type
== operand::OP_EXPR
;
916 is_a_helper
<if_expr
*>::test (operand
*op
)
918 return op
->type
== operand::OP_IF
;
924 is_a_helper
<with_expr
*>::test (operand
*op
)
926 return op
->type
== operand::OP_WITH
;
929 /* The main class of a pattern and its transform. This is used to
930 represent both (simplify ...) and (match ...) kinds. The AST
931 duplicates all outer 'if' and 'for' expressions here so each
932 simplify can exist in isolation. */
937 enum simplify_kind
{ SIMPLIFY
, MATCH
};
939 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
940 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
941 cid_map_t
*capture_ids_
)
942 : kind (kind_
), id (id_
), match (match_
), result (result_
),
943 for_vec (for_vec_
), for_subst_vec (vNULL
),
944 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
947 /* ID. This is kept to easily associate related simplifies expanded
948 from the same original one. */
950 /* The expression that is matched against the GENERIC or GIMPLE IL. */
952 /* For a (simplify ...) an expression with ifs and withs with the expression
953 produced when the pattern applies in the leafs.
954 For a (match ...) the leafs are either empty if it is a simple predicate
955 or the single expression specifying the matched operands. */
956 class operand
*result
;
957 /* Collected 'for' expression operators that have to be replaced
958 in the lowering phase. */
959 vec
<vec
<user_id
*> > for_vec
;
960 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
961 /* A map of capture identifiers to indexes. */
962 cid_map_t
*capture_ids
;
966 /* Debugging routines for dumping the AST. */
969 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
971 if (capture
*c
= dyn_cast
<capture
*> (o
))
973 if (c
->what
&& flattened
== false)
974 print_operand (c
->what
, f
, flattened
);
975 fprintf (f
, "@%u", c
->where
);
978 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
979 fprintf (f
, "%s", p
->p
->id
);
981 else if (is_a
<c_expr
*> (o
))
982 fprintf (f
, "c_expr");
984 else if (expr
*e
= dyn_cast
<expr
*> (o
))
986 if (e
->ops
.length () == 0)
987 fprintf (f
, "%s", e
->operation
->id
);
990 fprintf (f
, "(%s", e
->operation
->id
);
992 if (flattened
== false)
994 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
997 print_operand (e
->ops
[i
], f
, flattened
);
1009 print_matches (class simplify
*s
, FILE *f
= stderr
)
1011 fprintf (f
, "for expression: ");
1012 print_operand (s
->match
, f
);
1019 /* Lowering of commutative operators. */
1022 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
1023 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
1025 if (n
== ops_vector
.length ())
1027 vec
<operand
*> xv
= v
.copy ();
1028 result
.safe_push (xv
);
1032 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
1034 v
[n
] = ops_vector
[n
][i
];
1035 cartesian_product (ops_vector
, result
, v
, n
+ 1);
1039 /* Lower OP to two operands in case it is marked as commutative. */
1041 static vec
<operand
*>
1042 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
1044 vec
<operand
*> ret
= vNULL
;
1046 if (capture
*c
= dyn_cast
<capture
*> (op
))
1053 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
1054 for (unsigned i
= 0; i
< v
.length (); ++i
)
1056 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
1063 expr
*e
= dyn_cast
<expr
*> (op
);
1064 if (!e
|| e
->ops
.length () == 0)
1070 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1071 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1072 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1074 auto_vec
< vec
<operand
*> > result
;
1075 auto_vec
<operand
*> v (e
->ops
.length ());
1076 v
.quick_grow_cleared (e
->ops
.length ());
1077 cartesian_product (ops_vector
, result
, v
, 0);
1080 for (unsigned i
= 0; i
< result
.length (); ++i
)
1082 expr
*ne
= new expr (e
);
1083 ne
->is_commutative
= false;
1084 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1085 ne
->append_op (result
[i
][j
]);
1089 if (!e
->is_commutative
)
1092 /* The operation is always binary if it isn't inherently commutative. */
1093 int natural_opno
= commutative_op (e
->operation
);
1094 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1095 for (unsigned i
= 0; i
< result
.length (); ++i
)
1097 expr
*ne
= new expr (e
);
1098 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1100 if (comparison_code_p (r
->code
))
1101 ne
->operation
= swap_tree_comparison (r
);
1103 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1105 bool found_compare
= false;
1106 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1107 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1109 if (comparison_code_p (q
->code
)
1110 && swap_tree_comparison (q
) != q
)
1112 found_compare
= true;
1118 user_id
*newop
= new user_id ("<internal>");
1119 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1121 id_base
*subst
= p
->substitutes
[j
];
1122 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1124 if (comparison_code_p (q
->code
))
1125 subst
= swap_tree_comparison (q
);
1127 newop
->substitutes
.safe_push (subst
);
1129 ne
->operation
= newop
;
1130 /* Search for 'p' inside the for vector and push 'newop'
1131 to the same level. */
1132 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1133 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1134 if (for_vec
[j
][k
] == p
)
1136 for_vec
[j
].safe_push (newop
);
1142 ne
->is_commutative
= false;
1143 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1145 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1146 ne
->append_op (result
[i
][old_j
]);
1154 /* Lower operations marked as commutative in the AST of S and push
1155 the resulting patterns to SIMPLIFIERS. */
1158 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1160 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1161 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1163 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1164 s
->for_vec
, s
->capture_ids
);
1165 simplifiers
.safe_push (ns
);
1169 /* Strip conditional operations using group GRP from O and its
1170 children if STRIP, else replace them with an unconditional operation. */
1173 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1175 if (capture
*c
= dyn_cast
<capture
*> (o
))
1178 return new capture (c
->location
, c
->where
,
1179 lower_opt (c
->what
, grp
, strip
),
1185 expr
*e
= dyn_cast
<expr
*> (o
);
1189 if (e
->opt_grp
== grp
)
1192 return lower_opt (e
->ops
[0], grp
, strip
);
1194 expr
*ne
= new expr (e
);
1196 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1200 expr
*ne
= new expr (e
);
1201 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1202 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1207 /* Determine whether O or its children uses the conditional operation
1211 has_opt (operand
*o
, unsigned char grp
)
1213 if (capture
*c
= dyn_cast
<capture
*> (o
))
1216 return has_opt (c
->what
, grp
);
1221 expr
*e
= dyn_cast
<expr
*> (o
);
1225 if (e
->opt_grp
== grp
)
1228 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1229 if (has_opt (e
->ops
[i
], grp
))
1235 /* Lower conditional convert operators in O, expanding it to a vector
1238 static vec
<operand
*>
1239 lower_opt (operand
*o
)
1241 vec
<operand
*> v1
= vNULL
, v2
;
1245 /* Conditional operations are lowered to a pattern with the
1246 operation and one without. All different conditional operation
1247 groups are lowered separately. */
1249 for (unsigned i
= 1; i
<= 10; ++i
)
1252 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1253 if (has_opt (v1
[j
], i
))
1255 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1256 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1262 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1263 v1
.safe_push (v2
[j
]);
1270 /* Lower conditional convert operators in the AST of S and push
1271 the resulting multiple patterns to SIMPLIFIERS. */
1274 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1276 vec
<operand
*> matchers
= lower_opt (s
->match
);
1277 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1279 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1280 s
->for_vec
, s
->capture_ids
);
1281 simplifiers
.safe_push (ns
);
1285 /* Lower the compare operand of COND_EXPRs to a
1286 GENERIC and a GIMPLE variant. */
1288 static vec
<operand
*>
1289 lower_cond (operand
*o
)
1291 vec
<operand
*> ro
= vNULL
;
1293 if (capture
*c
= dyn_cast
<capture
*> (o
))
1297 vec
<operand
*> lop
= vNULL
;
1298 lop
= lower_cond (c
->what
);
1300 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1301 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1307 expr
*e
= dyn_cast
<expr
*> (o
);
1308 if (!e
|| e
->ops
.length () == 0)
1314 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1315 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1316 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1318 auto_vec
< vec
<operand
*> > result
;
1319 auto_vec
<operand
*> v (e
->ops
.length ());
1320 v
.quick_grow_cleared (e
->ops
.length ());
1321 cartesian_product (ops_vector
, result
, v
, 0);
1323 for (unsigned i
= 0; i
< result
.length (); ++i
)
1325 expr
*ne
= new expr (e
);
1326 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1327 ne
->append_op (result
[i
][j
]);
1329 /* If this is a COND with a captured expression or an
1330 expression with two operands then also match a GENERIC
1331 form on the compare. */
1332 if (*e
->operation
== COND_EXPR
1333 && ((is_a
<capture
*> (e
->ops
[0])
1334 && as_a
<capture
*> (e
->ops
[0])->what
1335 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1337 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1338 || (is_a
<expr
*> (e
->ops
[0])
1339 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1342 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1343 ne
->append_op (result
[i
][j
]);
1344 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1346 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1347 expr
*cmp
= new expr (ocmp
);
1348 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1349 cmp
->append_op (ocmp
->ops
[j
]);
1350 cmp
->is_generic
= true;
1351 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1356 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1357 expr
*cmp
= new expr (ocmp
);
1358 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1359 cmp
->append_op (ocmp
->ops
[j
]);
1360 cmp
->is_generic
= true;
1370 /* Lower the compare operand of COND_EXPRs to a
1371 GENERIC and a GIMPLE variant. */
1374 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1376 vec
<operand
*> matchers
= lower_cond (s
->match
);
1377 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1379 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1380 s
->for_vec
, s
->capture_ids
);
1381 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1382 simplifiers
.safe_push (ns
);
1386 /* Return true if O refers to ID. */
1389 contains_id (operand
*o
, user_id
*id
)
1391 if (capture
*c
= dyn_cast
<capture
*> (o
))
1392 return c
->what
&& contains_id (c
->what
, id
);
1394 if (expr
*e
= dyn_cast
<expr
*> (o
))
1396 if (e
->operation
== id
)
1398 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1399 if (contains_id (e
->ops
[i
], id
))
1404 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1405 return (contains_id (w
->with
, id
)
1406 || contains_id (w
->subexpr
, id
));
1408 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1409 return (contains_id (ife
->cond
, id
)
1410 || contains_id (ife
->trueexpr
, id
)
1411 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1413 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1414 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1420 /* In AST operand O replace operator ID with operator WITH. */
1423 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1425 /* Deep-copy captures and expressions, replacing operations as
1427 if (capture
*c
= dyn_cast
<capture
*> (o
))
1431 return new capture (c
->location
, c
->where
,
1432 replace_id (c
->what
, id
, with
), c
->value_match
);
1434 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1436 expr
*ne
= new expr (e
);
1437 if (e
->operation
== id
)
1438 ne
->operation
= with
;
1439 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1440 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1443 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1445 with_expr
*nw
= new with_expr (w
->location
);
1446 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1447 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1450 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1452 if_expr
*nife
= new if_expr (ife
->location
);
1453 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1454 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1456 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1460 /* For c_expr we simply record a string replacement table which is
1461 applied at code-generation time. */
1462 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1464 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1465 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1466 return new c_expr (ce
->r
, ce
->location
,
1467 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1473 /* Return true if the binary operator OP is ok for delayed substitution
1474 during for lowering. */
1477 binary_ok (operator_id
*op
)
1484 case TRUNC_DIV_EXPR
:
1486 case FLOOR_DIV_EXPR
:
1487 case ROUND_DIV_EXPR
:
1488 case TRUNC_MOD_EXPR
:
1490 case FLOOR_MOD_EXPR
:
1491 case ROUND_MOD_EXPR
:
1493 case EXACT_DIV_EXPR
:
1505 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1508 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1510 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1511 unsigned worklist_start
= 0;
1512 auto_vec
<simplify
*> worklist
;
1513 worklist
.safe_push (sin
);
1515 /* Lower each recorded for separately, operating on the
1516 set of simplifiers created by the previous one.
1517 Lower inner-to-outer so inner for substitutes can refer
1518 to operators replaced by outer fors. */
1519 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1521 vec
<user_id
*>& ids
= for_vec
[fi
];
1522 unsigned n_ids
= ids
.length ();
1523 unsigned max_n_opers
= 0;
1524 bool can_delay_subst
= true;
1525 for (unsigned i
= 0; i
< n_ids
; ++i
)
1527 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1528 max_n_opers
= ids
[i
]->substitutes
.length ();
1529 /* Require that all substitutes are of the same kind so that
1530 if we delay substitution to the result op code generation
1531 can look at the first substitute for deciding things like
1532 types of operands. */
1533 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1534 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1535 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1536 can_delay_subst
= false;
1537 else if (operator_id
*op
1538 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1541 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1542 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1543 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1545 /* Unfortunately we can't just allow all tcc_binary. */
1546 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1547 && strcmp (op0
->tcc
, "tcc_binary") == 0
1551 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1552 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1553 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1554 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1557 can_delay_subst
= false;
1559 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1562 can_delay_subst
= false;
1564 if (sin
->kind
== simplify::MATCH
1568 unsigned worklist_end
= worklist
.length ();
1569 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1571 simplify
*s
= worklist
[si
];
1572 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1574 operand
*match_op
= s
->match
;
1575 operand
*result_op
= s
->result
;
1576 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1578 for (unsigned i
= 0; i
< n_ids
; ++i
)
1580 user_id
*id
= ids
[i
];
1581 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1583 && (contains_id (match_op
, id
)
1584 || contains_id (result_op
, id
)))
1589 subst
.quick_push (std::make_pair (id
, oper
));
1590 if (sin
->kind
== simplify::SIMPLIFY
1591 || !can_delay_subst
)
1592 match_op
= replace_id (match_op
, id
, oper
);
1594 && !can_delay_subst
)
1595 result_op
= replace_id (result_op
, id
, oper
);
1600 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1601 vNULL
, s
->capture_ids
);
1602 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1605 ns
->for_subst_vec
.safe_splice (subst
);
1607 worklist
.safe_push (ns
);
1610 worklist_start
= worklist_end
;
1613 /* Copy out the result from the last for lowering. */
1614 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1615 simplifiers
.safe_push (worklist
[i
]);
1618 /* Lower the AST for everything in SIMPLIFIERS. */
1621 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1623 auto_vec
<simplify
*> out_simplifiers
;
1624 for (auto s
: simplifiers
)
1625 lower_opt (s
, out_simplifiers
);
1627 simplifiers
.truncate (0);
1628 for (auto s
: out_simplifiers
)
1629 lower_commutative (s
, simplifiers
);
1631 /* Lower for needs to happen before lowering cond
1632 to support (for cnd (cond vec_cond)). This is
1633 safe as substitution delay does not happen for
1634 cond or vec_cond. */
1635 out_simplifiers
.truncate (0);
1636 for (auto s
: simplifiers
)
1637 lower_for (s
, out_simplifiers
);
1639 simplifiers
.truncate (0);
1641 for (auto s
: out_simplifiers
)
1642 lower_cond (s
, simplifiers
);
1644 simplifiers
.safe_splice (out_simplifiers
);
1650 /* The decision tree built for generating GIMPLE and GENERIC pattern
1651 matching code. It represents the 'match' expression of all
1652 simplifies and has those as its leafs. */
1656 /* A hash-map collecting semantically equivalent leafs in the decision
1657 tree for splitting out to separate functions. */
1666 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1669 static inline hashval_t
hash (const key_type
&);
1670 static inline bool equal_keys (const key_type
&, const key_type
&);
1671 template <typename T
> static inline void remove (T
&) {}
1674 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1677 /* Current simplifier ID we are processing during insertion into the
1679 static unsigned current_id
;
1681 /* Decision tree base class, used for DT_NODE. */
1686 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1691 vec
<dt_node
*> kids
;
1695 unsigned total_size
;
1698 dt_node (enum dt_type type_
, dt_node
*parent_
)
1699 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1701 dt_node
*append_node (dt_node
*);
1702 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1703 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1704 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1706 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1708 virtual void gen (FILE *, int, bool, int) {}
1710 void gen_kids (FILE *, int, bool, int);
1711 void gen_kids_1 (FILE *, int, bool, int,
1712 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1713 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1714 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1716 void analyze (sinfo_map_t
&);
1719 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1721 class dt_operand
: public dt_node
1725 dt_operand
*match_dop
;
1730 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1731 dt_operand
*parent_
, unsigned pos_
)
1732 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1733 pos (pos_
), value_match (false), for_id (current_id
) {}
1735 void gen (FILE *, int, bool, int) final override
;
1736 unsigned gen_predicate (FILE *, int, const char *, bool);
1737 unsigned gen_match_op (FILE *, int, const char *, bool);
1739 unsigned gen_gimple_expr (FILE *, int, int);
1740 unsigned gen_generic_expr (FILE *, int, const char *);
1742 char *get_name (char *);
1743 void gen_opname (char *, unsigned);
1746 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1748 class dt_simplify
: public dt_node
1752 unsigned pattern_no
;
1753 dt_operand
**indexes
;
1756 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1757 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1758 indexes (indexes_
), info (NULL
) {}
1760 void gen_1 (FILE *, int, bool, operand
*);
1761 void gen (FILE *f
, int, bool, int) final override
;
1767 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1769 return (n
->type
== dt_node::DT_OPERAND
1770 || n
->type
== dt_node::DT_MATCH
1771 || n
->type
== dt_node::DT_TRUE
);
1777 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1779 return n
->type
== dt_node::DT_SIMPLIFY
;
1784 /* A container for the actual decision tree. */
1791 void insert (class simplify
*, unsigned);
1792 void gen (vec
<FILE *> &f
, bool gimple
);
1793 void print (FILE *f
= stderr
);
1795 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1797 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1798 unsigned pos
= 0, dt_node
*parent
= 0);
1799 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1800 static bool cmp_node (dt_node
*, dt_node
*);
1801 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1804 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1807 cmp_operand (operand
*o1
, operand
*o2
)
1809 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1812 if (o1
->type
== operand::OP_PREDICATE
)
1814 predicate
*p1
= as_a
<predicate
*>(o1
);
1815 predicate
*p2
= as_a
<predicate
*>(o2
);
1816 return p1
->p
== p2
->p
;
1818 else if (o1
->type
== operand::OP_EXPR
)
1820 expr
*e1
= static_cast<expr
*>(o1
);
1821 expr
*e2
= static_cast<expr
*>(o2
);
1822 return (e1
->operation
== e2
->operation
1823 && e1
->is_generic
== e2
->is_generic
);
1829 /* Compare two decision tree nodes N1 and N2 and return true if they
1833 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1835 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1841 if (n1
->type
== dt_node::DT_TRUE
)
1844 if (n1
->type
== dt_node::DT_OPERAND
)
1845 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1846 (as_a
<dt_operand
*> (n2
))->op
);
1847 else if (n1
->type
== dt_node::DT_MATCH
)
1848 return (((as_a
<dt_operand
*> (n1
))->match_dop
1849 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1850 && ((as_a
<dt_operand
*> (n1
))->value_match
1851 == (as_a
<dt_operand
*> (n2
))->value_match
));
1855 /* Search OPS for a decision tree node like P and return it if found. */
1858 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1860 /* We can merge adjacent DT_TRUE. */
1861 if (p
->type
== dt_node::DT_TRUE
1863 && ops
.last ()->type
== dt_node::DT_TRUE
)
1865 dt_operand
*true_node
= NULL
;
1866 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1868 /* But we can't merge across DT_TRUE nodes as they serve as
1869 pattern order barriers to make sure that patterns apply
1870 in order of appearance in case multiple matches are possible. */
1871 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1874 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1875 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1877 if (decision_tree::cmp_node (ops
[i
], p
))
1879 /* Unless we are processing the same pattern or the blocking
1880 pattern is before the one we are going to merge with. */
1882 && true_node
->for_id
!= current_id
1883 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1887 location_t p_loc
= 0;
1888 if (p
->type
== dt_node::DT_OPERAND
)
1889 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1890 location_t op_loc
= 0;
1891 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1892 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1893 location_t true_loc
= 0;
1894 true_loc
= true_node
->op
->location
;
1896 "failed to merge decision tree node");
1898 "with the following");
1899 warning_at (true_loc
,
1900 "because of the following which serves as ordering "
1911 /* Append N to the decision tree if it there is not already an existing
1915 dt_node::append_node (dt_node
*n
)
1919 kid
= decision_tree::find_node (kids
, n
);
1924 n
->level
= this->level
+ 1;
1929 /* Append OP to the decision tree. */
1932 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1934 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1935 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1936 return append_node (n
);
1939 /* Append a DT_TRUE decision tree node. */
1942 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1944 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1945 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1946 return append_node (n
);
1949 /* Append a DT_MATCH decision tree node. */
1952 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1953 dt_node
*parent
, unsigned pos
)
1955 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1956 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1957 return append_node (n
);
1960 /* Append S to the decision tree. */
1963 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1964 dt_operand
**indexes
)
1967 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1968 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1969 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1971 || s
->match
->location
!= s2
->s
->match
->location
))
1973 /* With a nested patters, it's hard to avoid these in order
1974 to keep match.pd rules relatively small. */
1975 warning_at (s
->match
->location
, "duplicate pattern");
1976 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1977 print_operand (s
->match
, stderr
);
1978 fprintf (stderr
, "\n");
1980 return append_node (n
);
1983 /* Analyze the node and its children. */
1986 dt_node::analyze (sinfo_map_t
&map
)
1992 if (type
== DT_SIMPLIFY
)
1994 /* Populate the map of equivalent simplifies. */
1995 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1997 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
2012 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2014 kids
[i
]->analyze (map
);
2015 num_leafs
+= kids
[i
]->num_leafs
;
2016 total_size
+= kids
[i
]->total_size
;
2017 max_level
= MAX (max_level
, kids
[i
]->max_level
);
2021 /* Insert O into the decision tree and return the decision tree node found
2025 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
2026 unsigned pos
, dt_node
*parent
)
2028 dt_node
*q
, *elm
= 0;
2030 if (capture
*c
= dyn_cast
<capture
*> (o
))
2032 unsigned capt_index
= c
->where
;
2034 if (indexes
[capt_index
] == 0)
2037 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
2040 q
= elm
= p
->append_true_op (o
, parent
, pos
);
2043 // get to the last capture
2044 for (operand
*what
= c
->what
;
2045 what
&& is_a
<capture
*> (what
);
2046 c
= as_a
<capture
*> (what
), what
= c
->what
)
2051 unsigned cc_index
= c
->where
;
2052 dt_operand
*match_op
= indexes
[cc_index
];
2054 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
2055 elm
= decision_tree::find_node (p
->kids
, &temp
);
2059 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
2060 match
.value_match
= c
->value_match
;
2061 elm
= decision_tree::find_node (p
->kids
, &match
);
2066 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
2067 elm
= decision_tree::find_node (p
->kids
, &temp
);
2071 gcc_assert (elm
->type
== dt_node::DT_TRUE
2072 || elm
->type
== dt_node::DT_OPERAND
2073 || elm
->type
== dt_node::DT_MATCH
);
2074 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2079 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2080 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2082 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2087 p
= p
->append_op (o
, parent
, pos
);
2090 if (expr
*e
= dyn_cast
<expr
*>(o
))
2092 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2093 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2099 /* Insert S into the decision tree. */
2102 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2105 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2106 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2107 p
->append_simplify (s
, pattern_no
, indexes
);
2110 /* Debug functions to dump the decision tree. */
2113 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2115 if (p
->type
== dt_node::DT_NODE
)
2116 fprintf (f
, "root");
2120 for (unsigned i
= 0; i
< indent
; i
++)
2123 if (p
->type
== dt_node::DT_OPERAND
)
2125 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2126 print_operand (dop
->op
, f
, true);
2128 else if (p
->type
== dt_node::DT_TRUE
)
2129 fprintf (f
, "true");
2130 else if (p
->type
== dt_node::DT_MATCH
)
2131 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2132 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2134 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2135 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2136 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2137 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2140 if (is_a
<dt_operand
*> (p
))
2141 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2144 fprintf (stderr
, " (%p, %p), %u, %u\n",
2145 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2147 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2148 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2152 decision_tree::print (FILE *f
)
2154 return decision_tree::print_node (root
, f
);
2158 /* For GENERIC we have to take care of wrapping multiple-used
2159 expressions with side-effects in save_expr and preserve side-effects
2160 of expressions with omit_one_operand. Analyze captures in
2161 match, result and with expressions and perform early-outs
2162 on the outermost match expression operands for cases we cannot
2168 capture_info (simplify
*s
, operand
*, bool);
2169 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2170 bool walk_result (operand
*o
, bool, operand
*);
2171 void walk_c_expr (c_expr
*);
2177 bool force_no_side_effects_p
;
2178 bool force_single_use
;
2179 bool cond_expr_cond_p
;
2180 unsigned long toplevel_msk
;
2181 unsigned match_use_count
;
2182 unsigned result_use_count
;
2187 auto_vec
<cinfo
> info
;
2188 unsigned long force_no_side_effects
;
2192 /* Analyze captures in S. */
2194 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2199 if (s
->kind
== simplify::MATCH
)
2201 force_no_side_effects
= -1;
2205 force_no_side_effects
= 0;
2206 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2207 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2208 info
[i
].same_as
= i
;
2210 e
= as_a
<expr
*> (s
->match
);
2211 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2212 walk_match (e
->ops
[i
], i
,
2213 (i
!= 0 && *e
->operation
== COND_EXPR
)
2214 || *e
->operation
== TRUTH_ANDIF_EXPR
2215 || *e
->operation
== TRUTH_ORIF_EXPR
,
2216 i
== 0 && *e
->operation
== COND_EXPR
);
2218 walk_result (s
->result
, false, result
);
2221 /* Analyze captures in the match expression piece O. */
2224 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2225 bool conditional_p
, bool cond_expr_cond_p
)
2227 if (capture
*c
= dyn_cast
<capture
*> (o
))
2229 unsigned where
= c
->where
;
2230 info
[where
].match_use_count
++;
2231 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2232 info
[where
].force_no_side_effects_p
|= conditional_p
;
2233 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2238 /* Recurse to exprs and captures. */
2239 if (is_a
<capture
*> (c
->what
)
2240 || is_a
<expr
*> (c
->what
))
2241 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2242 /* We need to look past multiple captures to find a captured
2243 expression as with conditional converts two captures
2244 can be collapsed onto the same expression. Also collect
2245 what captures capture the same thing. */
2246 while (c
->what
&& is_a
<capture
*> (c
->what
))
2248 c
= as_a
<capture
*> (c
->what
);
2249 if (info
[c
->where
].same_as
!= c
->where
2250 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2251 fatal_at (c
->location
, "cannot handle this collapsed capture");
2252 info
[c
->where
].same_as
= info
[where
].same_as
;
2254 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2257 && (e
= dyn_cast
<expr
*> (c
->what
)))
2259 /* Zero-operand expression captures like ADDR_EXPR@0 are
2260 similar as predicates -- if they are not mentioned in
2261 the result we have to force them to have no side-effects. */
2262 if (e
->ops
.length () != 0)
2263 info
[where
].expr_p
= true;
2264 info
[where
].force_single_use
|= e
->force_single_use
;
2267 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2269 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2271 bool cond_p
= conditional_p
;
2272 bool expr_cond_p
= false;
2273 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2275 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2276 || *e
->operation
== TRUTH_ORIF_EXPR
)
2279 && *e
->operation
== COND_EXPR
)
2281 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2284 else if (is_a
<predicate
*> (o
))
2286 /* Mark non-captured leafs toplevel arg for checking. */
2287 force_no_side_effects
|= 1 << toplevel_arg
;
2290 warning_at (o
->location
,
2291 "forcing no side-effects on possibly lost leaf");
2297 /* Analyze captures in the result expression piece O. Return true
2298 if RESULT was visited in one of the children. Only visit
2299 non-if/with children if they are rooted on RESULT. */
2302 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2304 if (capture
*c
= dyn_cast
<capture
*> (o
))
2306 unsigned where
= info
[c
->where
].same_as
;
2307 info
[where
].result_use_count
++;
2308 /* If we substitute an expression capture we don't know
2309 which captures this will end up using (well, we don't
2310 compute that). Force the uses to be side-effect free
2311 which means forcing the toplevels that reach the
2312 expression side-effect free. */
2313 if (info
[where
].expr_p
)
2314 force_no_side_effects
|= info
[where
].toplevel_msk
;
2315 /* Mark CSE capture uses as forced to have no side-effects. */
2317 && is_a
<expr
*> (c
->what
))
2319 info
[where
].cse_p
= true;
2320 walk_result (c
->what
, true, result
);
2323 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2325 id_base
*opr
= e
->operation
;
2326 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2327 opr
= uid
->substitutes
[0];
2328 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2330 bool cond_p
= conditional_p
;
2331 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2333 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2334 || *e
->operation
== TRUTH_ORIF_EXPR
)
2336 walk_result (e
->ops
[i
], cond_p
, result
);
2339 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2341 /* 'if' conditions should be all fine. */
2342 if (ie
->trueexpr
== result
)
2344 walk_result (ie
->trueexpr
, false, result
);
2347 if (ie
->falseexpr
== result
)
2349 walk_result (ie
->falseexpr
, false, result
);
2353 if (is_a
<if_expr
*> (ie
->trueexpr
)
2354 || is_a
<with_expr
*> (ie
->trueexpr
))
2355 res
|= walk_result (ie
->trueexpr
, false, result
);
2357 && (is_a
<if_expr
*> (ie
->falseexpr
)
2358 || is_a
<with_expr
*> (ie
->falseexpr
)))
2359 res
|= walk_result (ie
->falseexpr
, false, result
);
2362 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2364 bool res
= (we
->subexpr
== result
);
2366 || is_a
<if_expr
*> (we
->subexpr
)
2367 || is_a
<with_expr
*> (we
->subexpr
))
2368 res
|= walk_result (we
->subexpr
, false, result
);
2370 walk_c_expr (we
->with
);
2373 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2381 /* Look for captures in the C expr E. */
2384 capture_info::walk_c_expr (c_expr
*e
)
2386 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2387 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2388 really escape through. */
2389 unsigned p_depth
= 0;
2390 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2392 const cpp_token
*t
= &e
->code
[i
];
2393 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2395 if (t
->type
== CPP_NAME
2396 && (strcmp ((const char *)CPP_HASHNODE
2397 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2398 || strcmp ((const char *)CPP_HASHNODE
2399 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2400 || strcmp ((const char *)CPP_HASHNODE
2401 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2402 || ((id
= get_operator ((const char *)CPP_HASHNODE
2403 (t
->val
.node
.node
)->ident
.str
))
2404 && is_a
<predicate_id
*> (id
)))
2405 && n
->type
== CPP_OPEN_PAREN
)
2407 else if (t
->type
== CPP_CLOSE_PAREN
2410 else if (p_depth
== 0
2411 && t
->type
== CPP_ATSIGN
2412 && (n
->type
== CPP_NUMBER
2413 || n
->type
== CPP_NAME
)
2414 && !(n
->flags
& PREV_WHITE
))
2417 if (n
->type
== CPP_NUMBER
)
2418 id1
= (const char *)n
->val
.str
.text
;
2420 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2421 unsigned *where
= e
->capture_ids
->get(id1
);
2423 fatal_at (n
, "unknown capture id '%s'", id1
);
2424 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2427 warning_at (t
, "capture escapes");
2433 /* The current label failing the current matched pattern during
2435 static char *fail_label
;
2437 /* Code generation off the decision tree and the refered AST nodes. */
2440 is_conversion (id_base
*op
)
2442 return (*op
== CONVERT_EXPR
2444 || *op
== FLOAT_EXPR
2445 || *op
== FIX_TRUNC_EXPR
2446 || *op
== VIEW_CONVERT_EXPR
);
2449 /* Get the type to be used for generating operand POS of OP from the
2453 get_operand_type (id_base
*op
, unsigned pos
,
2454 const char *in_type
,
2455 const char *expr_type
,
2456 const char *other_oprnd_type
)
2458 /* Generally operands whose type does not match the type of the
2459 expression generated need to know their types but match and
2460 thus can fall back to 'other_oprnd_type'. */
2461 if (is_conversion (op
))
2462 return other_oprnd_type
;
2463 else if (*op
== REALPART_EXPR
2464 || *op
== IMAGPART_EXPR
)
2465 return other_oprnd_type
;
2466 else if (is_a
<operator_id
*> (op
)
2467 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2468 return other_oprnd_type
;
2469 else if (*op
== COND_EXPR
2471 return "boolean_type_node";
2472 else if (startswith (op
->id
, "CFN_COND_"))
2474 /* IFN_COND_* operands 1 and later by default have the same type
2475 as the result. The type of operand 0 needs to be specified
2477 if (pos
> 0 && expr_type
)
2479 else if (pos
> 0 && in_type
)
2486 /* Otherwise all types should match - choose one in order of
2493 return other_oprnd_type
;
2497 /* Generate transform code for an expression. */
2500 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2501 int depth
, const char *in_type
, capture_info
*cinfo
,
2502 dt_operand
**indexes
, int)
2504 id_base
*opr
= operation
;
2505 /* When we delay operator substituting during lowering of fors we
2506 make sure that for code-gen purposes the effects of each substitute
2507 are the same. Thus just look at that. */
2508 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2509 opr
= uid
->substitutes
[0];
2511 bool conversion_p
= is_conversion (opr
);
2512 const char *type
= expr_type
;
2515 /* If there was a type specification in the pattern use it. */
2517 else if (conversion_p
)
2518 /* For conversions we need to build the expression using the
2519 outer type passed in. */
2521 else if (*opr
== REALPART_EXPR
2522 || *opr
== IMAGPART_EXPR
)
2524 /* __real and __imag use the component type of its operand. */
2525 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2529 else if (is_a
<operator_id
*> (opr
)
2530 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2532 /* comparisons use boolean_type_node (or what gets in), but
2533 their operands need to figure out the types themselves. */
2538 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2543 else if (*opr
== COND_EXPR
2544 || *opr
== VEC_COND_EXPR
2545 || startswith (opr
->id
, "CFN_COND_"))
2547 /* Conditions are of the same type as their first alternative. */
2548 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2553 /* Other operations are of the same type as their first operand. */
2554 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2558 fatal_at (location
, "cannot determine type of operand");
2560 fprintf_indent (f
, indent
, "{\n");
2562 fprintf_indent (f
, indent
,
2563 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2565 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2566 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2569 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2571 = get_operand_type (opr
, i
, in_type
, expr_type
,
2572 i
== 0 ? NULL
: op0type
);
2573 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2575 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2578 const char *opr_name
;
2579 if (*operation
== CONVERT_EXPR
)
2580 opr_name
= "NOP_EXPR";
2582 opr_name
= operation
->id
;
2586 if (*opr
== CONVERT_EXPR
)
2588 fprintf_indent (f
, indent
,
2589 "if (%s != TREE_TYPE (_o%d[0])\n",
2591 fprintf_indent (f
, indent
,
2592 " && !useless_type_conversion_p (%s, TREE_TYPE "
2595 fprintf_indent (f
, indent
+ 2, "{\n");
2598 /* ??? Building a stmt can fail for various reasons here, seq being
2599 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2600 So if we fail here we should continue matching other patterns. */
2601 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2602 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2603 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2604 fprintf (f
, ", _o%d[%u]", depth
, i
);
2605 fprintf (f
, ");\n");
2606 fprintf_indent (f
, indent
, "tem_op.resimplify (%s, valueize);\n",
2607 !force_leaf
? "lseq" : "NULL");
2608 fprintf_indent (f
, indent
,
2609 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2610 !force_leaf
? "lseq" : "NULL");
2611 fprintf_indent (f
, indent
,
2612 "if (!_r%d) goto %s;\n",
2614 if (*opr
== CONVERT_EXPR
)
2617 fprintf_indent (f
, indent
, " }\n");
2618 fprintf_indent (f
, indent
, "else\n");
2619 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2624 if (*opr
== CONVERT_EXPR
)
2626 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2630 if (opr
->kind
== id_base::CODE
)
2631 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2632 depth
, ops
.length(), opr_name
, type
);
2634 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2635 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2636 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2637 fprintf (f
, ", _o%d[%u]", depth
, i
);
2638 fprintf (f
, ");\n");
2639 if (opr
->kind
!= id_base::CODE
)
2641 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2642 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2646 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2647 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2649 if (*opr
== CONVERT_EXPR
)
2652 fprintf_indent (f
, indent
, "else\n");
2653 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2656 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2658 fprintf_indent (f
, indent
, "}\n");
2661 /* Generate code for a c_expr which is either the expression inside
2662 an if statement or a sequence of statements which computes a
2663 result to be stored to DEST. */
2666 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2667 bool, int, const char *, capture_info
*,
2670 if (dest
&& nr_stmts
== 1)
2671 fprintf_indent (f
, indent
, "%s = ", dest
);
2673 unsigned stmt_nr
= 1;
2675 for (unsigned i
= 0; i
< code
.length (); ++i
)
2677 const cpp_token
*token
= &code
[i
];
2679 /* We can't recover from all lexing losses but we can roughly restore line
2680 breaks from location info. */
2681 const line_map_ordinary
*map
;
2682 linemap_resolve_location (line_table
, token
->src_loc
,
2683 LRK_SPELLING_LOCATION
, &map
);
2684 expanded_location loc
= linemap_expand_location (line_table
, map
,
2686 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2688 prev_line
= loc
.line
;
2690 /* Replace captures for code-gen. */
2691 if (token
->type
== CPP_ATSIGN
)
2693 const cpp_token
*n
= &code
[i
+1];
2694 if ((n
->type
== CPP_NUMBER
2695 || n
->type
== CPP_NAME
)
2696 && !(n
->flags
& PREV_WHITE
))
2698 if (token
->flags
& PREV_WHITE
)
2701 if (n
->type
== CPP_NUMBER
)
2702 id
= (const char *)n
->val
.str
.text
;
2704 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2705 unsigned *cid
= capture_ids
->get (id
);
2707 fatal_at (token
, "unknown capture id");
2708 fprintf (f
, "captures[%u]", *cid
);
2714 if (token
->flags
& PREV_WHITE
)
2717 if (token
->type
== CPP_NAME
)
2719 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2721 for (j
= 0; j
< ids
.length (); ++j
)
2723 if (strcmp (id
, ids
[j
].id
) == 0)
2725 fprintf (f
, "%s", ids
[j
].oper
);
2729 if (j
< ids
.length ())
2733 /* Output the token as string. */
2734 char *tk
= (char *)cpp_token_as_text (r
, token
);
2737 if (token
->type
== CPP_SEMICOLON
)
2740 if (dest
&& stmt_nr
== nr_stmts
)
2741 fprintf_indent (f
, indent
, "%s = ", dest
);
2747 /* Generate transform code for a capture. */
2750 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2751 int depth
, const char *in_type
, capture_info
*cinfo
,
2752 dt_operand
**indexes
, int cond_handling
)
2754 if (what
&& is_a
<expr
*> (what
))
2756 if (indexes
[where
] == 0)
2759 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2760 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2765 /* If in GENERIC some capture is used multiple times, unshare it except
2766 when emitting the last use. */
2768 && cinfo
->info
.exists ()
2769 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2771 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2773 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2776 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2778 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2779 with substituting a capture of that. */
2781 && cond_handling
!= 0
2782 && cinfo
->info
[where
].cond_expr_cond_p
)
2784 /* If substituting into a cond_expr condition, unshare. */
2785 if (cond_handling
== 1)
2786 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2787 /* If substituting elsewhere we might need to decompose it. */
2788 else if (cond_handling
== 2)
2790 /* ??? Returning false here will also not allow any other patterns
2791 to match unless this generator was split out. */
2792 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2793 fprintf_indent (f
, indent
, " {\n");
2794 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2795 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2797 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2798 " TREE_OPERAND (%s, 1));\n",
2799 dest
, dest
, dest
, dest
, dest
);
2800 fprintf_indent (f
, indent
, " }\n");
2805 /* Return the name of the operand representing the decision tree node.
2806 Use NAME as space to generate it. */
2809 dt_operand::get_name (char *name
)
2812 sprintf (name
, "t");
2813 else if (parent
->level
== 1)
2814 sprintf (name
, "_p%u", pos
);
2815 else if (parent
->type
== dt_node::DT_MATCH
)
2816 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2818 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2822 /* Fill NAME with the operand name at position POS. */
2825 dt_operand::gen_opname (char *name
, unsigned pos
)
2828 sprintf (name
, "_p%u", pos
);
2830 sprintf (name
, "_q%u%u", level
, pos
);
2833 /* Generate matching code for the decision tree operand which is
2837 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2839 predicate
*p
= as_a
<predicate
*> (op
);
2841 if (p
->p
->matchers
.exists ())
2843 /* If this is a predicate generated from a pattern mangle its
2844 name and pass on the valueize hook. */
2846 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2849 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2852 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2853 fprintf_indent (f
, indent
+ 2, "{\n");
2857 /* Generate matching code for the decision tree operand which is
2861 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2863 char match_opname
[20];
2864 match_dop
->get_name (match_opname
);
2866 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2867 "|| operand_equal_p (%s, %s, 0))\n",
2868 opname
, match_opname
, opname
, opname
, match_opname
);
2870 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2871 "|| (operand_equal_p (%s, %s, 0) "
2872 "&& types_match (%s, %s)))\n",
2873 opname
, match_opname
, opname
, opname
, match_opname
,
2874 opname
, match_opname
);
2875 fprintf_indent (f
, indent
+ 2, "{\n");
2879 /* Generate GIMPLE matching code for the decision tree operand. */
2882 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2884 expr
*e
= static_cast<expr
*> (op
);
2885 id_base
*id
= e
->operation
;
2886 unsigned n_ops
= e
->ops
.length ();
2887 unsigned n_braces
= 0;
2889 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2890 id
= u
->substitutes
[0];
2892 for (unsigned i
= 0; i
< n_ops
; ++i
)
2894 char child_opname
[20];
2895 gen_opname (child_opname
, i
);
2897 if (id
->kind
== id_base::CODE
)
2900 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2901 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2903 /* ??? If this is a memory operation we can't (and should not)
2904 match this. The only sensible operand types are
2905 SSA names and invariants. */
2910 fprintf_indent (f
, indent
,
2911 "tree %s = TREE_OPERAND (%s, %i);\n",
2912 child_opname
, opname
, i
);
2915 fprintf_indent (f
, indent
,
2916 "tree %s = TREE_OPERAND "
2917 "(gimple_assign_rhs1 (_a%d), %i);\n",
2918 child_opname
, depth
, i
);
2919 fprintf_indent (f
, indent
,
2920 "if ((TREE_CODE (%s) == SSA_NAME\n",
2922 fprintf_indent (f
, indent
,
2923 " || is_gimple_min_invariant (%s)))\n",
2925 fprintf_indent (f
, indent
,
2929 fprintf_indent (f
, indent
,
2930 "%s = do_valueize (valueize, %s);\n",
2931 child_opname
, child_opname
);
2935 fprintf_indent (f
, indent
,
2936 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2937 child_opname
, i
+ 1, depth
);
2940 fprintf_indent (f
, indent
,
2941 "tree %s = gimple_call_arg (_c%d, %u);\n",
2942 child_opname
, depth
, i
);
2943 fprintf_indent (f
, indent
,
2944 "%s = do_valueize (valueize, %s);\n",
2945 child_opname
, child_opname
);
2947 /* While the toplevel operands are canonicalized by the caller
2948 after valueizing operands of sub-expressions we have to
2949 re-canonicalize operand order. */
2950 int opno
= commutative_op (id
);
2953 char child_opname0
[20], child_opname1
[20];
2954 gen_opname (child_opname0
, opno
);
2955 gen_opname (child_opname1
, opno
+ 1);
2956 fprintf_indent (f
, indent
,
2957 "if (tree_swap_operands_p (%s, %s))\n",
2958 child_opname0
, child_opname1
);
2959 fprintf_indent (f
, indent
,
2960 " std::swap (%s, %s);\n",
2961 child_opname0
, child_opname1
);
2967 /* Generate GENERIC matching code for the decision tree operand. */
2970 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2972 expr
*e
= static_cast<expr
*> (op
);
2973 id_base
*id
= e
->operation
;
2974 unsigned n_ops
= e
->ops
.length ();
2976 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2977 id
= u
->substitutes
[0];
2979 for (unsigned i
= 0; i
< n_ops
; ++i
)
2981 char child_opname
[20];
2982 gen_opname (child_opname
, i
);
2984 if (id
->kind
== id_base::CODE
)
2985 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2986 child_opname
, opname
, i
);
2988 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2989 child_opname
, opname
, i
);
2995 /* Generate matching code for the children of the decision tree node. */
2998 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
3000 auto_vec
<dt_operand
*> gimple_exprs
;
3001 auto_vec
<dt_operand
*> generic_exprs
;
3002 auto_vec
<dt_operand
*> fns
;
3003 auto_vec
<dt_operand
*> generic_fns
;
3004 auto_vec
<dt_operand
*> preds
;
3005 auto_vec
<dt_node
*> others
;
3007 for (unsigned i
= 0; i
< kids
.length (); ++i
)
3009 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
3011 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
3012 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
3014 if (e
->ops
.length () == 0
3015 /* In GIMPLE a CONSTRUCTOR always appears in a
3016 separate definition. */
3017 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
3019 generic_exprs
.safe_push (op
);
3020 /* But ADDR_EXPRs can appear directly when invariant
3021 and in a separate definition when not. */
3022 if (gimple
&& *e
->operation
== ADDR_EXPR
)
3023 gimple_exprs
.safe_push (op
);
3025 else if (e
->operation
->kind
== id_base::FN
)
3030 generic_fns
.safe_push (op
);
3032 else if (e
->operation
->kind
== id_base::PREDICATE
)
3033 preds
.safe_push (op
);
3036 user_id
*u
= dyn_cast
<user_id
*> (e
->operation
);
3037 if (u
&& u
->substitutes
[0]->kind
== id_base::FN
)
3042 generic_fns
.safe_push (op
);
3046 if (gimple
&& !e
->is_generic
)
3047 gimple_exprs
.safe_push (op
);
3049 generic_exprs
.safe_push (op
);
3053 else if (op
->op
->type
== operand::OP_PREDICATE
)
3054 others
.safe_push (kids
[i
]);
3058 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
3059 others
.safe_push (kids
[i
]);
3060 else if (kids
[i
]->type
== dt_node::DT_MATCH
3061 || kids
[i
]->type
== dt_node::DT_TRUE
)
3063 /* A DT_TRUE operand serves as a barrier - generate code now
3064 for what we have collected sofar.
3065 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3066 dependent matches to get out-of-order. Generate code now
3067 for what we have collected sofar. */
3068 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3069 fns
, generic_fns
, preds
, others
);
3070 /* And output the true operand itself. */
3071 kids
[i
]->gen (f
, indent
, gimple
, depth
);
3072 gimple_exprs
.truncate (0);
3073 generic_exprs
.truncate (0);
3075 generic_fns
.truncate (0);
3077 others
.truncate (0);
3083 /* Generate code for the remains. */
3084 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3085 fns
, generic_fns
, preds
, others
);
3088 /* Generate matching code for the children of the decision tree node. */
3091 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
3092 const vec
<dt_operand
*> &gimple_exprs
,
3093 const vec
<dt_operand
*> &generic_exprs
,
3094 const vec
<dt_operand
*> &fns
,
3095 const vec
<dt_operand
*> &generic_fns
,
3096 const vec
<dt_operand
*> &preds
,
3097 const vec
<dt_node
*> &others
)
3100 char *kid_opname
= buf
;
3102 unsigned exprs_len
= gimple_exprs
.length ();
3103 unsigned gexprs_len
= generic_exprs
.length ();
3104 unsigned fns_len
= fns
.length ();
3105 unsigned gfns_len
= generic_fns
.length ();
3107 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3110 gimple_exprs
[0]->get_name (kid_opname
);
3112 fns
[0]->get_name (kid_opname
);
3114 generic_fns
[0]->get_name (kid_opname
);
3116 generic_exprs
[0]->get_name (kid_opname
);
3118 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3119 fprintf_indent (f
, indent
, " {\n");
3123 if (exprs_len
|| fns_len
)
3126 fprintf_indent (f
, indent
,
3127 "case SSA_NAME:\n");
3128 fprintf_indent (f
, indent
,
3129 " if (gimple *_d%d = get_def (valueize, %s))\n",
3131 fprintf_indent (f
, indent
,
3136 fprintf_indent (f
, indent
,
3137 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3139 fprintf_indent (f
, indent
,
3140 " switch (gimple_assign_rhs_code (_a%d))\n",
3143 fprintf_indent (f
, indent
, "{\n");
3144 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3146 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3147 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3149 for (auto id
: u
->substitutes
)
3150 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3154 id_base
*op
= e
->operation
;
3155 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3156 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3158 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3160 fprintf_indent (f
, indent
, " {\n");
3161 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3162 fprintf_indent (f
, indent
, " break;\n");
3163 fprintf_indent (f
, indent
, " }\n");
3165 fprintf_indent (f
, indent
, "default:;\n");
3166 fprintf_indent (f
, indent
, "}\n");
3172 fprintf_indent (f
, indent
,
3173 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3174 exprs_len
? "else " : "", depth
, depth
);
3175 fprintf_indent (f
, indent
,
3176 " switch (gimple_call_combined_fn (_c%d))\n",
3180 fprintf_indent (f
, indent
, "{\n");
3181 for (unsigned i
= 0; i
< fns_len
; ++i
)
3183 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3184 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3185 for (auto id
: u
->substitutes
)
3186 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3188 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3189 /* We need to be defensive against bogus prototypes allowing
3190 calls with not enough arguments. */
3191 fprintf_indent (f
, indent
,
3192 " if (gimple_call_num_args (_c%d) == %d)\n",
3193 depth
, e
->ops
.length ());
3194 fprintf_indent (f
, indent
, " {\n");
3195 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3196 fprintf_indent (f
, indent
, " }\n");
3197 fprintf_indent (f
, indent
, " break;\n");
3200 fprintf_indent (f
, indent
, "default:;\n");
3201 fprintf_indent (f
, indent
, "}\n");
3207 fprintf_indent (f
, indent
, " }\n");
3208 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3209 here rather than in the next loop. */
3210 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3212 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3213 id_base
*op
= e
->operation
;
3214 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3216 fprintf_indent (f
, indent
+ 4, "{\n");
3217 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3218 fprintf_indent (f
, indent
+ 4, "}\n");
3222 fprintf_indent (f
, indent
, " break;\n");
3225 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3227 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3228 id_base
*op
= e
->operation
;
3229 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3230 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3231 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3232 /* Already handled above. */
3236 if (user_id
*u
= dyn_cast
<user_id
*> (op
))
3237 for (auto id
: u
->substitutes
)
3238 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3240 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3242 fprintf_indent (f
, indent
, " {\n");
3243 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3244 fprintf_indent (f
, indent
, " break;\n");
3245 fprintf_indent (f
, indent
, " }\n");
3250 fprintf_indent (f
, indent
,
3251 "case CALL_EXPR:\n");
3252 fprintf_indent (f
, indent
,
3253 " switch (get_call_combined_fn (%s))\n",
3255 fprintf_indent (f
, indent
,
3259 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3261 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3262 gcc_assert (e
->operation
->kind
== id_base::FN
);
3264 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3265 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3266 " {\n", kid_opname
, e
->ops
.length ());
3267 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3268 fprintf_indent (f
, indent
, " }\n"
3271 fprintf_indent (f
, indent
, "default:;\n");
3274 fprintf_indent (f
, indent
, " }\n");
3275 fprintf_indent (f
, indent
, " break;\n");
3278 /* Close switch (TREE_CODE ()). */
3279 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3282 fprintf_indent (f
, indent
, " default:;\n");
3283 fprintf_indent (f
, indent
, " }\n");
3286 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3288 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3289 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3290 preds
[i
]->get_name (kid_opname
);
3291 fprintf_indent (f
, indent
, "{\n");
3293 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3294 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3295 gimple
? "gimple" : "tree",
3296 p
->id
, kid_opname
, kid_opname
,
3297 gimple
? ", valueize" : "");
3298 fprintf_indent (f
, indent
, " {\n");
3299 for (int j
= 0; j
< p
->nargs
; ++j
)
3301 char child_opname
[20];
3302 preds
[i
]->gen_opname (child_opname
, j
);
3303 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3304 child_opname
, kid_opname
, j
);
3306 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3309 fprintf_indent (f
, indent
, "}\n");
3312 for (unsigned i
= 0; i
< others
.length (); ++i
)
3313 others
[i
]->gen (f
, indent
, gimple
, depth
);
3316 /* Generate matching code for the decision tree operand. */
3319 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3324 unsigned n_braces
= 0;
3326 if (type
== DT_OPERAND
)
3329 case operand::OP_PREDICATE
:
3330 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3333 case operand::OP_EXPR
:
3335 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3337 n_braces
= gen_generic_expr (f
, indent
, opname
);
3343 else if (type
== DT_TRUE
)
3345 else if (type
== DT_MATCH
)
3346 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3350 indent
+= 4 * n_braces
;
3351 gen_kids (f
, indent
, gimple
, depth
);
3353 for (unsigned i
= 0; i
< n_braces
; ++i
)
3358 fprintf_indent (f
, indent
, " }\n");
3363 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3364 step of a '(simplify ...)' or '(match ...)'. This handles everything
3365 that is not part of the decision tree (simplify->match).
3366 Main recursive worker. */
3369 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3373 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3375 fprintf_indent (f
, indent
, "{\n");
3377 output_line_directive (f
, w
->location
);
3378 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3379 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3381 fprintf_indent (f
, indent
, "}\n");
3384 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3386 output_line_directive (f
, ife
->location
);
3387 fprintf_indent (f
, indent
, "if (");
3388 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3390 fprintf_indent (f
, indent
+ 2, "{\n");
3392 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3394 fprintf_indent (f
, indent
+ 2, "}\n");
3397 fprintf_indent (f
, indent
, "else\n");
3398 fprintf_indent (f
, indent
+ 2, "{\n");
3400 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3402 fprintf_indent (f
, indent
+ 2, "}\n");
3408 static unsigned fail_label_cnt
;
3409 char local_fail_label
[256];
3410 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3411 fail_label
= local_fail_label
;
3412 bool needs_label
= false;
3414 /* Analyze captures and perform early-outs on the incoming arguments
3415 that cover cases we cannot handle. */
3416 capture_info
cinfo (s
, result
, gimple
);
3417 if (s
->kind
== simplify::SIMPLIFY
)
3421 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3422 if (cinfo
.force_no_side_effects
& (1 << i
))
3424 fprintf_indent (f
, indent
,
3425 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3429 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3430 "forcing toplevel operand to have no "
3433 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3434 if (cinfo
.info
[i
].cse_p
)
3436 else if (cinfo
.info
[i
].force_no_side_effects_p
3437 && (cinfo
.info
[i
].toplevel_msk
3438 & cinfo
.force_no_side_effects
) == 0)
3440 fprintf_indent (f
, indent
,
3441 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3442 "goto %s;\n", i
, fail_label
);
3445 warning_at (cinfo
.info
[i
].c
->location
,
3446 "forcing captured operand to have no "
3449 else if ((cinfo
.info
[i
].toplevel_msk
3450 & cinfo
.force_no_side_effects
) != 0)
3451 /* Mark capture as having no side-effects if we had to verify
3452 that via forced toplevel operand checks. */
3453 cinfo
.info
[i
].force_no_side_effects_p
= true;
3457 /* Force single-use restriction by only allowing simple
3458 results via setting seq to NULL. */
3459 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3460 bool first_p
= true;
3461 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3462 if (cinfo
.info
[i
].force_single_use
)
3466 fprintf_indent (f
, indent
, "if (lseq\n");
3467 fprintf_indent (f
, indent
, " && (");
3473 fprintf_indent (f
, indent
, " || ");
3475 fprintf (f
, "!single_use (captures[%d])", i
);
3479 fprintf (f
, "))\n");
3480 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3485 if (s
->kind
== simplify::SIMPLIFY
)
3487 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3491 fprintf_indent (f
, indent
, "if (UNLIKELY (debug_dump)) "
3492 "fprintf (dump_file, \"%s ",
3493 s
->kind
== simplify::SIMPLIFY
3494 ? "Applying pattern" : "Matching expression");
3495 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3496 output_line_directive (f
,
3497 result
? result
->location
: s
->match
->location
, true,
3499 fprintf (f
, ", __FILE__, __LINE__);\n");
3501 fprintf_indent (f
, indent
, "{\n");
3505 /* If there is no result then this is a predicate implementation. */
3506 fprintf_indent (f
, indent
, "return true;\n");
3510 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3511 in outermost position). */
3512 if (result
->type
== operand::OP_EXPR
3513 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3514 result
= as_a
<expr
*> (result
)->ops
[0];
3515 if (result
->type
== operand::OP_EXPR
)
3517 expr
*e
= as_a
<expr
*> (result
);
3518 id_base
*opr
= e
->operation
;
3519 bool is_predicate
= false;
3520 /* When we delay operator substituting during lowering of fors we
3521 make sure that for code-gen purposes the effects of each substitute
3522 are the same. Thus just look at that. */
3523 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3524 opr
= uid
->substitutes
[0];
3525 else if (is_a
<predicate_id
*> (opr
))
3526 is_predicate
= true;
3528 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3529 *e
->operation
== CONVERT_EXPR
3530 ? "NOP_EXPR" : e
->operation
->id
,
3532 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3536 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3538 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3540 = get_operand_type (opr
, j
,
3541 "type", e
->expr_type
,
3543 : "TREE_TYPE (res_op->ops[0])");
3544 /* We need to expand GENERIC conditions we captured from
3545 COND_EXPRs and we need to unshare them when substituting
3547 int cond_handling
= 0;
3549 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3550 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3551 &cinfo
, indexes
, cond_handling
);
3554 /* Re-fold the toplevel result. It's basically an embedded
3555 gimple_build w/o actually building the stmt. */
3558 fprintf_indent (f
, indent
,
3559 "res_op->resimplify (%s, valueize);\n",
3560 !e
->force_leaf
? "lseq" : "NULL");
3563 fprintf_indent (f
, indent
,
3564 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3565 "goto %s;\n", fail_label
);
3570 else if (result
->type
== operand::OP_CAPTURE
3571 || result
->type
== operand::OP_C_EXPR
)
3573 fprintf_indent (f
, indent
, "tree tem;\n");
3574 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3576 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3577 if (is_a
<capture
*> (result
)
3578 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3580 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3581 with substituting a capture of that. */
3582 fprintf_indent (f
, indent
,
3583 "if (COMPARISON_CLASS_P (tem))\n");
3584 fprintf_indent (f
, indent
,
3586 fprintf_indent (f
, indent
,
3587 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3588 fprintf_indent (f
, indent
,
3589 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3590 fprintf_indent (f
, indent
,
3596 fprintf_indent (f
, indent
, "return true;\n");
3600 bool is_predicate
= false;
3601 if (result
->type
== operand::OP_EXPR
)
3603 expr
*e
= as_a
<expr
*> (result
);
3604 id_base
*opr
= e
->operation
;
3605 /* When we delay operator substituting during lowering of fors we
3606 make sure that for code-gen purposes the effects of each substitute
3607 are the same. Thus just look at that. */
3608 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3609 opr
= uid
->substitutes
[0];
3610 else if (is_a
<predicate_id
*> (opr
))
3611 is_predicate
= true;
3612 /* Search for captures used multiple times in the result expression
3613 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3614 original expression. */
3616 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3618 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3619 || cinfo
.info
[i
].cse_p
)
3621 if (cinfo
.info
[i
].result_use_count
3622 > cinfo
.info
[i
].match_use_count
)
3624 fprintf_indent (f
, indent
,
3625 "if (! tree_invariant_p (captures[%d])) "
3626 "goto %s;\n", i
, fail_label
);
3630 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3634 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3637 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3638 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3641 = get_operand_type (opr
, j
,
3642 "type", e
->expr_type
,
3644 ? NULL
: "TREE_TYPE (res_op0)");
3645 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3649 fprintf_indent (f
, indent
, "return true;\n");
3652 fprintf_indent (f
, indent
, "tree _r;\n");
3653 /* Re-fold the toplevel result. Use non_lvalue to
3654 build NON_LVALUE_EXPRs so they get properly
3655 ignored when in GIMPLE form. */
3656 if (*opr
== NON_LVALUE_EXPR
)
3657 fprintf_indent (f
, indent
,
3658 "_r = non_lvalue_loc (loc, res_op0);\n");
3661 if (is_a
<operator_id
*> (opr
))
3662 fprintf_indent (f
, indent
,
3663 "_r = fold_build%d_loc (loc, %s, type",
3665 *e
->operation
== CONVERT_EXPR
3666 ? "NOP_EXPR" : e
->operation
->id
);
3668 fprintf_indent (f
, indent
,
3669 "_r = maybe_build_call_expr_loc (loc, "
3670 "%s, type, %d", e
->operation
->id
,
3672 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3673 fprintf (f
, ", res_op%d", j
);
3674 fprintf (f
, ");\n");
3675 if (!is_a
<operator_id
*> (opr
))
3677 fprintf_indent (f
, indent
, "if (!_r)\n");
3678 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3684 else if (result
->type
== operand::OP_CAPTURE
3685 || result
->type
== operand::OP_C_EXPR
)
3688 fprintf_indent (f
, indent
, "tree _r;\n");
3689 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3696 /* Search for captures not used in the result expression and dependent
3697 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3698 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3700 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3702 if (!cinfo
.info
[i
].force_no_side_effects_p
3703 && !cinfo
.info
[i
].expr_p
3704 && cinfo
.info
[i
].result_use_count
== 0)
3706 fprintf_indent (f
, indent
,
3707 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3709 fprintf_indent (f
, indent
+ 2,
3710 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3711 "fold_ignored_result (captures[%d]), _r);\n",
3715 fprintf_indent (f
, indent
, "return _r;\n");
3719 fprintf_indent (f
, indent
, "}\n");
3721 fprintf (f
, "%s:;\n", fail_label
);
3725 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3726 step of a '(simplify ...)' or '(match ...)'. This handles everything
3727 that is not part of the decision tree (simplify->match). */
3730 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3732 fprintf_indent (f
, indent
, "{\n");
3734 output_line_directive (f
,
3735 s
->result
? s
->result
->location
: s
->match
->location
);
3736 if (s
->capture_max
>= 0)
3739 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3740 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3742 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3746 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3748 fprintf (f
, " };\n");
3751 /* If we have a split-out function for the actual transform, call it. */
3752 if (info
&& info
->fname
)
3756 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3757 "valueize, type, captures", info
->fname
);
3758 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3759 if (s
->for_subst_vec
[i
].first
->used
)
3760 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3761 fprintf (f
, "))\n");
3762 fprintf_indent (f
, indent
, " return true;\n");
3766 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3768 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3769 fprintf (f
, ", _p%d", i
);
3770 fprintf (f
, ", captures");
3771 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3773 if (s
->for_subst_vec
[i
].first
->used
)
3774 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3776 fprintf (f
, ");\n");
3777 fprintf_indent (f
, indent
, "if (res) return res;\n");
3782 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3784 if (! s
->for_subst_vec
[i
].first
->used
)
3786 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3787 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3788 s
->for_subst_vec
[i
].first
->id
,
3789 s
->for_subst_vec
[i
].second
->id
);
3790 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3791 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3792 s
->for_subst_vec
[i
].first
->id
,
3793 s
->for_subst_vec
[i
].second
->id
);
3797 gen_1 (f
, indent
, gimple
, s
->result
);
3801 fprintf_indent (f
, indent
, "}\n");
3805 /* Hash function for finding equivalent transforms. */
3808 sinfo_hashmap_traits::hash (const key_type
&v
)
3810 /* Only bother to compare those originating from the same source pattern. */
3811 return v
->s
->result
->location
;
3814 /* Compare function for finding equivalent transforms. */
3817 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3819 if (o1
->type
!= o2
->type
)
3824 case operand::OP_IF
:
3826 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3827 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3828 /* ??? Properly compare c-exprs. */
3829 if (if1
->cond
!= if2
->cond
)
3831 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3833 if (if1
->falseexpr
!= if2
->falseexpr
3835 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3839 case operand::OP_WITH
:
3841 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3842 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3843 if (with1
->with
!= with2
->with
)
3845 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3850 /* We've hit a result. Time to compare capture-infos - this is required
3851 in addition to the conservative pointer-equivalency of the result IL. */
3852 capture_info
cinfo1 (s1
, o1
, true);
3853 capture_info
cinfo2 (s2
, o2
, true);
3855 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3856 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3859 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3861 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3862 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3863 || (cinfo1
.info
[i
].force_no_side_effects_p
3864 != cinfo2
.info
[i
].force_no_side_effects_p
)
3865 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3866 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3867 /* toplevel_msk is an optimization */
3868 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3869 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3870 /* the pointer back to the capture is for diagnostics only */)
3874 /* ??? Deep-compare the actual result. */
3879 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3880 const key_type
&candidate
)
3882 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3886 /* Main entry to generate code for matching GIMPLE IL off the decision
3890 decision_tree::gen (vec
<FILE *> &files
, bool gimple
)
3896 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3897 "a total number of %u nodes\n",
3898 gimple
? "GIMPLE" : "GENERIC",
3899 root
->num_leafs
, root
->max_level
, root
->total_size
);
3901 /* First split out the transform part of equal leafs. */
3904 for (sinfo_map_t::iterator iter
= si
.begin ();
3905 iter
!= si
.end (); ++iter
)
3907 sinfo
*s
= (*iter
).second
;
3908 /* Do not split out single uses. */
3915 fprintf (stderr
, "found %u uses of", s
->cnt
);
3916 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3919 /* Cycle the file buffers. */
3920 FILE *f
= choose_output (files
);
3922 /* Generate a split out function with the leaf transform code. */
3923 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3926 fp_decl (f
, "\nbool\n"
3927 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3928 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3929 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3934 fp_decl (f
, "\ntree\n"
3935 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3936 (*iter
).second
->fname
);
3937 for (unsigned i
= 0;
3938 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3939 fp_decl (f
, " tree ARG_UNUSED (_p%d),", i
);
3940 fp_decl (f
, " tree *captures");
3942 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3944 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3946 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3947 fp_decl (f
, ",\n const enum tree_code ARG_UNUSED (%s)",
3948 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3949 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3950 fp_decl (f
, ",\n const combined_fn ARG_UNUSED (%s)",
3951 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3954 fp_decl_done (f
, ")");
3956 fprintf_indent (f
, 2, "const bool debug_dump = "
3957 "dump_file && (dump_flags & TDF_FOLDING);\n");
3958 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3960 fprintf (f
, " return false;\n");
3962 fprintf (f
, " return NULL_TREE;\n");
3965 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3967 for (unsigned n
= 1; n
<= 5; ++n
)
3969 bool has_kids_p
= false;
3971 /* First generate split-out functions. */
3972 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3974 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3975 expr
*e
= static_cast<expr
*>(dop
->op
);
3976 if (e
->ops
.length () != n
3977 /* Builtin simplifications are somewhat premature on
3978 GENERIC. The following drops patterns with outermost
3979 calls. It's easy to emit overloads for function code
3980 though if necessary. */
3982 && e
->operation
->kind
!= id_base::CODE
))
3986 /* Cycle the file buffers. */
3987 FILE *f
= choose_output (files
);
3990 fp_decl (f
, "\nbool\n"
3991 "gimple_simplify_%s (gimple_match_op *res_op,"
3992 " gimple_seq *seq,\n"
3993 " tree (*valueize)(tree) "
3994 "ATTRIBUTE_UNUSED,\n"
3995 " code_helper ARG_UNUSED (code), tree "
3996 "ARG_UNUSED (type)",
3999 fp_decl (f
, "\ntree\n"
4000 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
4001 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
4003 for (unsigned i
= 0; i
< n
; ++i
)
4004 fp_decl (f
, ", tree _p%d", i
);
4005 fp_decl_done (f
, ")");
4007 fprintf_indent (f
, 2, "const bool debug_dump = "
4008 "dump_file && (dump_flags & TDF_FOLDING);\n");
4009 dop
->gen_kids (f
, 2, gimple
, 0);
4011 fprintf (f
, " return false;\n");
4013 fprintf (f
, " return NULL_TREE;\n");
4018 /* If this main entry has no children, avoid generating code
4019 with compiler warnings, by generating a simple stub. */
4023 /* Cycle the file buffers. */
4024 FILE *f
= choose_output (files
);
4027 fp_decl (f
, "\nbool\n"
4028 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
4029 " tree (*)(tree), code_helper,\n"
4032 fp_decl (f
, "\ntree\n"
4033 "generic_simplify (location_t, enum tree_code,\n"
4035 for (unsigned i
= 0; i
< n
; ++i
)
4036 fp_decl (f
, ", tree");
4037 fp_decl_done (f
, ")");
4040 fprintf (f
, " return false;\n");
4042 fprintf (f
, " return NULL_TREE;\n");
4048 /* Cycle the file buffers. */
4049 FILE *f
= choose_output (files
);
4051 /* Then generate the main entry with the outermost switch and
4052 tail-calls to the split-out functions. */
4054 fp_decl (f
, "\nbool\n"
4055 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
4056 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4057 " code_helper code, const tree type");
4059 fp_decl (f
, "\ntree\n"
4060 "generic_simplify (location_t loc, enum tree_code code, "
4061 "const tree type ATTRIBUTE_UNUSED");
4062 for (unsigned i
= 0; i
< n
; ++i
)
4063 fp_decl (f
, ", tree _p%d", i
);
4064 fp_decl_done (f
, ")");
4068 fprintf (f
, " switch (code.get_rep())\n"
4071 fprintf (f
, " switch (code)\n"
4073 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
4075 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
4076 expr
*e
= static_cast<expr
*>(dop
->op
);
4077 if (e
->ops
.length () != n
4078 /* Builtin simplifications are somewhat premature on
4079 GENERIC. The following drops patterns with outermost
4080 calls. It's easy to emit overloads for function code
4081 though if necessary. */
4083 && e
->operation
->kind
!= id_base::CODE
))
4086 if (*e
->operation
== CONVERT_EXPR
4087 || *e
->operation
== NOP_EXPR
)
4088 fprintf (f
, " CASE_CONVERT:\n");
4090 fprintf (f
, " case %s%s:\n",
4091 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
4094 fprintf (f
, " return gimple_simplify_%s (res_op, "
4095 "seq, valueize, code, type", e
->operation
->id
);
4097 fprintf (f
, " return generic_simplify_%s (loc, code, type",
4099 for (unsigned j
= 0; j
< n
; ++j
)
4100 fprintf (f
, ", _p%d", j
);
4101 fprintf (f
, ");\n");
4103 fprintf (f
, " default:;\n"
4107 fprintf (f
, " return false;\n");
4109 fprintf (f
, " return NULL_TREE;\n");
4114 /* Output code to implement the predicate P from the decision tree DT. */
4117 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
4119 fp_decl (f
, "\nbool\n%s%s (tree t%s%s)",
4120 gimple
? "gimple_" : "tree_", p
->id
,
4121 p
->nargs
> 0 ? ", tree *res_ops" : "",
4122 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4123 fp_decl_done (f
, "");
4125 /* Conveniently make 'type' available. */
4126 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
4127 fprintf_indent (f
, 2, "const bool debug_dump = "
4128 "dump_file && (dump_flags & TDF_FOLDING);\n");
4131 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4132 dt
.root
->gen_kids (f
, 2, gimple
, 0);
4134 fprintf_indent (f
, 2, "return false;\n"
4138 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4141 write_header (FILE *f
, const char *head
)
4143 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4144 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4145 fprintf (f
, "#pragma GCC diagnostic push\n");
4146 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-variable\"\n");
4147 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-function\"\n");
4149 /* Include the header instead of writing it awkwardly quoted here. */
4151 fprintf (f
, "\n#include \"%s\"\n", head
);
4161 parser (cpp_reader
*, bool gimple
);
4164 const cpp_token
*next ();
4165 const cpp_token
*peek (unsigned = 1);
4166 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4167 const cpp_token
*expect (enum cpp_ttype
);
4168 const cpp_token
*eat_token (enum cpp_ttype
);
4169 const char *get_string ();
4170 const char *get_ident ();
4171 const cpp_token
*eat_ident (const char *);
4172 const char *get_number ();
4174 unsigned get_internal_capture_id ();
4176 id_base
*parse_operation (unsigned char &);
4177 operand
*parse_capture (operand
*, bool);
4178 operand
*parse_expr ();
4179 c_expr
*parse_c_expr (cpp_ttype
);
4180 operand
*parse_op ();
4182 void record_operlist (location_t
, user_id
*);
4184 void parse_pattern ();
4185 operand
*parse_result (operand
*, predicate_id
*);
4186 void push_simplify (simplify::simplify_kind
,
4187 vec
<simplify
*>&, operand
*, operand
*);
4188 void parse_simplify (simplify::simplify_kind
,
4189 vec
<simplify
*>&, predicate_id
*, operand
*);
4190 void parse_for (location_t
);
4191 void parse_if (location_t
);
4192 void parse_predicates (location_t
);
4193 void parse_operator_list (location_t
);
4195 void finish_match_operand (operand
*);
4199 vec
<c_expr
*> active_ifs
;
4200 vec
<vec
<user_id
*> > active_fors
;
4201 hash_set
<user_id
*> *oper_lists_set
;
4202 vec
<user_id
*> oper_lists
;
4204 cid_map_t
*capture_ids
;
4208 vec
<simplify
*> simplifiers
;
4209 vec
<predicate_id
*> user_predicates
;
4210 bool parsing_match_operand
;
4213 /* Lexing helpers. */
4215 /* Read the next non-whitespace token from R. */
4220 const cpp_token
*token
;
4223 token
= cpp_get_token (r
);
4225 while (token
->type
== CPP_PADDING
);
4229 /* Peek at the next non-whitespace token from R. */
4232 parser::peek (unsigned num
)
4234 const cpp_token
*token
;
4238 token
= cpp_peek_token (r
, i
++);
4240 while (token
->type
== CPP_PADDING
4242 /* If we peek at EOF this is a fatal error as it leaves the
4243 cpp_reader in unusable state. Assume we really wanted a
4244 token and thus this EOF is unexpected. */
4245 if (token
->type
== CPP_EOF
)
4246 fatal_at (token
, "unexpected end of file");
4250 /* Peek at the next identifier token (or return NULL if the next
4251 token is not an identifier or equal to ID if supplied). */
4254 parser::peek_ident (const char *id
, unsigned num
)
4256 const cpp_token
*token
= peek (num
);
4257 if (token
->type
!= CPP_NAME
)
4263 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4264 if (strcmp (id
, t
) == 0)
4270 /* Read the next token from R and assert it is of type TK. */
4273 parser::expect (enum cpp_ttype tk
)
4275 const cpp_token
*token
= next ();
4276 if (token
->type
!= tk
)
4277 fatal_at (token
, "expected %s, got %s",
4278 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4283 /* Consume the next token from R and assert it is of type TK. */
4286 parser::eat_token (enum cpp_ttype tk
)
4291 /* Read the next token from R and assert it is of type CPP_STRING and
4292 return its value. */
4295 parser::get_string ()
4297 const cpp_token
*token
= expect (CPP_STRING
);
4298 return (const char *)token
->val
.str
.text
;
4301 /* Read the next token from R and assert it is of type CPP_NAME and
4302 return its value. */
4305 parser::get_ident ()
4307 const cpp_token
*token
= expect (CPP_NAME
);
4308 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4311 /* Eat an identifier token with value S from R. */
4314 parser::eat_ident (const char *s
)
4316 const cpp_token
*token
= peek ();
4317 const char *t
= get_ident ();
4318 if (strcmp (s
, t
) != 0)
4319 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4323 /* Read the next token from R and assert it is of type CPP_NUMBER and
4324 return its value. */
4327 parser::get_number ()
4329 const cpp_token
*token
= expect (CPP_NUMBER
);
4330 return (const char *)token
->val
.str
.text
;
4333 /* Return a capture ID that can be used internally. */
4336 parser::get_internal_capture_id ()
4338 unsigned newid
= capture_ids
->elements ();
4339 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4342 snprintf (id
, sizeof (id
), "__%u", newid
);
4343 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4345 fatal ("reserved capture id '%s' already used", id
);
4349 /* Record an operator-list use for transparent for handling. */
4352 parser::record_operlist (location_t loc
, user_id
*p
)
4354 if (!oper_lists_set
->add (p
))
4356 if (!oper_lists
.is_empty ()
4357 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4358 fatal_at (loc
, "User-defined operator list does not have the "
4359 "same number of entries as others used in the pattern");
4360 oper_lists
.safe_push (p
);
4364 /* Parse the operator ID, special-casing convert?, convert1? and
4368 parser::parse_operation (unsigned char &opt_grp
)
4370 const cpp_token
*id_tok
= peek ();
4371 char *alt_id
= NULL
;
4372 const char *id
= get_ident ();
4373 const cpp_token
*token
= peek ();
4375 if (token
->type
== CPP_QUERY
4376 && !(token
->flags
& PREV_WHITE
))
4378 if (!parsing_match_operand
)
4379 fatal_at (id_tok
, "conditional convert can only be used in "
4380 "match expression");
4381 if (ISDIGIT (id
[strlen (id
) - 1]))
4383 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4384 alt_id
= xstrdup (id
);
4385 alt_id
[strlen (id
) - 1] = '\0';
4387 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4391 eat_token (CPP_QUERY
);
4393 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4395 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4398 user_id
*p
= dyn_cast
<user_id
*> (op
);
4399 if (p
&& p
->is_oper_list
)
4401 if (active_fors
.length() == 0)
4402 record_operlist (id_tok
->src_loc
, p
);
4404 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4410 capture = '@'<number> */
4413 parser::parse_capture (operand
*op
, bool require_existing
)
4415 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4416 const cpp_token
*token
= peek ();
4417 const char *id
= NULL
;
4418 bool value_match
= false;
4419 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4420 if (token
->type
== CPP_ATSIGN
4421 && ! (token
->flags
& PREV_WHITE
)
4422 && parsing_match_operand
)
4424 eat_token (CPP_ATSIGN
);
4428 if (token
->type
== CPP_NUMBER
)
4430 else if (token
->type
== CPP_NAME
)
4433 fatal_at (token
, "expected number or identifier");
4434 unsigned next_id
= capture_ids
->elements ();
4436 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4439 if (require_existing
)
4440 fatal_at (src_loc
, "unknown capture id");
4443 return new capture (src_loc
, num
, op
, value_match
);
4446 /* Parse an expression
4447 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4450 parser::parse_expr ()
4452 const cpp_token
*token
= peek ();
4453 unsigned char opt_grp
;
4454 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4457 bool is_commutative
= false;
4458 bool force_capture
= false;
4459 const char *expr_type
= NULL
;
4461 if (!parsing_match_operand
4462 && token
->type
== CPP_NOT
4463 && !(token
->flags
& PREV_WHITE
))
4465 eat_token (CPP_NOT
);
4466 e
->force_leaf
= true;
4469 if (token
->type
== CPP_COLON
4470 && !(token
->flags
& PREV_WHITE
))
4472 eat_token (CPP_COLON
);
4474 if (token
->type
== CPP_NAME
4475 && !(token
->flags
& PREV_WHITE
))
4477 const char *s
= get_ident ();
4478 if (!parsing_match_operand
)
4488 = dyn_cast
<operator_id
*> (e
->operation
))
4490 if (!commutative_tree_code (o
->code
)
4491 && !comparison_code_p (o
->code
))
4492 fatal_at (token
, "operation is not commutative");
4494 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4495 for (unsigned i
= 0;
4496 i
< p
->substitutes
.length (); ++i
)
4499 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4501 if (!commutative_tree_code (q
->code
)
4502 && !comparison_code_p (q
->code
))
4503 fatal_at (token
, "operation %s is not "
4504 "commutative", q
->id
);
4507 is_commutative
= true;
4509 else if (*sp
== 'C')
4510 is_commutative
= true;
4511 else if (*sp
== 's')
4513 e
->force_single_use
= true;
4514 force_capture
= true;
4517 fatal_at (token
, "flag %c not recognized", *sp
);
4524 fatal_at (token
, "expected flag or type specifying identifier");
4527 if (token
->type
== CPP_ATSIGN
4528 && !(token
->flags
& PREV_WHITE
))
4529 op
= parse_capture (e
, false);
4530 else if (force_capture
)
4532 unsigned num
= get_internal_capture_id ();
4533 op
= new capture (token
->src_loc
, num
, e
, false);
4540 if (token
->type
== CPP_CLOSE_PAREN
)
4542 if (e
->operation
->nargs
!= -1
4543 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4544 fatal_at (token
, "'%s' expects %u operands, not %u",
4545 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4548 if (e
->ops
.length () == 2
4549 || commutative_op (e
->operation
) >= 0)
4550 e
->is_commutative
= true;
4552 fatal_at (token
, "only binary operators or functions with "
4553 "two arguments can be marked commutative, "
4554 "unless the operation is known to be inherently "
4557 e
->expr_type
= expr_type
;
4560 if (e
->ops
.length () != 1)
4561 fatal_at (token
, "only unary operations can be conditional");
4562 e
->opt_grp
= opt_grp
;
4566 else if (!(token
->flags
& PREV_WHITE
))
4567 fatal_at (token
, "expected expression operand");
4569 e
->append_op (parse_op ());
4574 /* Lex native C code delimited by START recording the preprocessing tokens
4575 for later processing.
4576 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4579 parser::parse_c_expr (cpp_ttype start
)
4581 const cpp_token
*token
;
4584 vec
<cpp_token
> code
= vNULL
;
4585 unsigned nr_stmts
= 0;
4586 location_t loc
= eat_token (start
)->src_loc
;
4587 if (start
== CPP_OPEN_PAREN
)
4588 end
= CPP_CLOSE_PAREN
;
4589 else if (start
== CPP_OPEN_BRACE
)
4590 end
= CPP_CLOSE_BRACE
;
4598 /* Count brace pairs to find the end of the expr to match. */
4599 if (token
->type
== start
)
4601 else if (token
->type
== end
4604 else if (token
->type
== CPP_EOF
)
4605 fatal_at (token
, "unexpected end of file");
4607 /* This is a lame way of counting the number of statements. */
4608 if (token
->type
== CPP_SEMICOLON
)
4611 /* If this is possibly a user-defined identifier mark it used. */
4612 if (token
->type
== CPP_NAME
)
4615 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4616 if (strcmp (str
, "return") == 0)
4617 fatal_at (token
, "return statement not allowed in C expression");
4618 id_base
*idb
= get_operator (str
);
4620 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4621 record_operlist (token
->src_loc
, p
);
4624 /* Record the token. */
4625 code
.safe_push (*token
);
4628 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4631 /* Parse an operand which is either an expression, a predicate or
4632 a standalone capture.
4633 op = predicate | expr | c_expr | capture */
4638 const cpp_token
*token
= peek ();
4639 class operand
*op
= NULL
;
4640 if (token
->type
== CPP_OPEN_PAREN
)
4642 eat_token (CPP_OPEN_PAREN
);
4644 eat_token (CPP_CLOSE_PAREN
);
4646 else if (token
->type
== CPP_OPEN_BRACE
)
4648 op
= parse_c_expr (CPP_OPEN_BRACE
);
4652 /* Remaining ops are either empty or predicates */
4653 if (token
->type
== CPP_NAME
)
4655 const char *id
= get_ident ();
4656 id_base
*opr
= get_operator (id
);
4658 fatal_at (token
, "expected predicate name");
4659 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4661 if (code1
->nargs
!= 0)
4662 fatal_at (token
, "using an operator with operands as predicate");
4663 /* Parse the zero-operand operator "predicates" as
4665 op
= new expr (opr
, token
->src_loc
);
4667 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4669 if (code2
->nargs
!= 0)
4670 fatal_at (token
, "using an operator with operands as predicate");
4671 /* Parse the zero-operand operator "predicates" as
4673 op
= new expr (opr
, token
->src_loc
);
4675 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4676 op
= new predicate (p
, token
->src_loc
);
4678 fatal_at (token
, "using an unsupported operator as predicate");
4679 if (!parsing_match_operand
)
4680 fatal_at (token
, "predicates are only allowed in match expression");
4682 if (token
->flags
& PREV_WHITE
)
4685 else if (token
->type
!= CPP_COLON
4686 && token
->type
!= CPP_ATSIGN
)
4687 fatal_at (token
, "expected expression or predicate");
4688 /* optionally followed by a capture and a predicate. */
4689 if (token
->type
== CPP_COLON
)
4690 fatal_at (token
, "not implemented: predicate on leaf operand");
4691 if (token
->type
== CPP_ATSIGN
)
4692 op
= parse_capture (op
, !parsing_match_operand
);
4698 /* Create a new simplify from the current parsing state and MATCH,
4699 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4702 parser::push_simplify (simplify::simplify_kind kind
,
4703 vec
<simplify
*>& simplifiers
,
4704 operand
*match
, operand
*result
)
4706 /* Build and push a temporary for operator list uses in expressions. */
4707 if (!oper_lists
.is_empty ())
4708 active_fors
.safe_push (oper_lists
);
4710 simplifiers
.safe_push
4711 (new simplify (kind
, last_id
++, match
, result
,
4712 active_fors
.copy (), capture_ids
));
4714 if (!oper_lists
.is_empty ())
4719 <result-op> = <op> | <if> | <with>
4720 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4721 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4725 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4727 const cpp_token
*token
= peek ();
4728 if (token
->type
!= CPP_OPEN_PAREN
)
4731 eat_token (CPP_OPEN_PAREN
);
4732 if (peek_ident ("if"))
4735 if_expr
*ife
= new if_expr (token
->src_loc
);
4736 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4737 if (peek ()->type
== CPP_OPEN_PAREN
)
4739 ife
->trueexpr
= parse_result (result
, matcher
);
4740 if (peek ()->type
== CPP_OPEN_PAREN
)
4741 ife
->falseexpr
= parse_result (result
, matcher
);
4742 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4743 ife
->falseexpr
= parse_op ();
4745 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4747 ife
->trueexpr
= parse_op ();
4748 if (peek ()->type
== CPP_OPEN_PAREN
)
4749 ife
->falseexpr
= parse_result (result
, matcher
);
4750 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4751 ife
->falseexpr
= parse_op ();
4753 /* If this if is immediately closed then it contains a
4754 manual matcher or is part of a predicate definition. */
4755 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4758 fatal_at (peek (), "manual transform not implemented");
4759 ife
->trueexpr
= result
;
4761 eat_token (CPP_CLOSE_PAREN
);
4764 else if (peek_ident ("with"))
4767 with_expr
*withe
= new with_expr (token
->src_loc
);
4768 /* Parse (with c-expr expr) as (if-with (true) expr). */
4769 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4770 withe
->with
->nr_stmts
= 0;
4771 withe
->subexpr
= parse_result (result
, matcher
);
4772 eat_token (CPP_CLOSE_PAREN
);
4775 else if (peek_ident ("switch"))
4777 token
= eat_ident ("switch");
4778 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4780 if_expr
*ife
= new if_expr (ifloc
);
4782 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4783 if (peek ()->type
== CPP_OPEN_PAREN
)
4784 ife
->trueexpr
= parse_result (result
, matcher
);
4786 ife
->trueexpr
= parse_op ();
4787 eat_token (CPP_CLOSE_PAREN
);
4788 if (peek ()->type
!= CPP_OPEN_PAREN
4789 || !peek_ident ("if", 2))
4790 fatal_at (token
, "switch can be implemented with a single if");
4791 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4793 if (peek ()->type
== CPP_OPEN_PAREN
)
4795 if (peek_ident ("if", 2))
4797 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4799 ife
->falseexpr
= new if_expr (ifloc
);
4800 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4801 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4802 if (peek ()->type
== CPP_OPEN_PAREN
)
4803 ife
->trueexpr
= parse_result (result
, matcher
);
4805 ife
->trueexpr
= parse_op ();
4806 eat_token (CPP_CLOSE_PAREN
);
4810 /* switch default clause */
4811 ife
->falseexpr
= parse_result (result
, matcher
);
4812 eat_token (CPP_CLOSE_PAREN
);
4818 /* switch default clause */
4819 ife
->falseexpr
= parse_op ();
4820 eat_token (CPP_CLOSE_PAREN
);
4824 eat_token (CPP_CLOSE_PAREN
);
4829 operand
*op
= result
;
4832 eat_token (CPP_CLOSE_PAREN
);
4838 simplify = 'simplify' <expr> <result-op>
4840 match = 'match' <ident> <expr> [<result-op>]
4841 and fill SIMPLIFIERS with the results. */
4844 parser::parse_simplify (simplify::simplify_kind kind
,
4845 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4848 /* Reset the capture map. */
4850 capture_ids
= new cid_map_t
;
4851 /* Reset oper_lists and set. */
4852 hash_set
<user_id
*> olist
;
4853 oper_lists_set
= &olist
;
4856 const cpp_token
*loc
= peek ();
4857 parsing_match_operand
= true;
4858 class operand
*match
= parse_op ();
4859 finish_match_operand (match
);
4860 parsing_match_operand
= false;
4861 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4862 fatal_at (loc
, "outermost expression cannot be captured");
4863 if (match
->type
== operand::OP_EXPR
4864 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4865 fatal_at (loc
, "outermost expression cannot be a predicate");
4867 /* Splice active_ifs onto result and continue parsing the
4869 if_expr
*active_if
= NULL
;
4870 for (int i
= active_ifs
.length (); i
> 0; --i
)
4872 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4873 ifc
->cond
= active_ifs
[i
-1];
4874 ifc
->trueexpr
= active_if
;
4877 if_expr
*outermost_if
= active_if
;
4878 while (active_if
&& active_if
->trueexpr
)
4879 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4881 const cpp_token
*token
= peek ();
4883 /* If this if is immediately closed then it is part of a predicate
4884 definition. Push it. */
4885 if (token
->type
== CPP_CLOSE_PAREN
)
4888 fatal_at (token
, "expected transform expression");
4891 active_if
->trueexpr
= result
;
4892 result
= outermost_if
;
4894 push_simplify (kind
, simplifiers
, match
, result
);
4898 operand
*tem
= parse_result (result
, matcher
);
4901 active_if
->trueexpr
= tem
;
4902 result
= outermost_if
;
4907 push_simplify (kind
, simplifiers
, match
, result
);
4910 /* Parsing of the outer control structures. */
4912 /* Parse a for expression
4913 for = '(' 'for' <subst>... <pattern> ')'
4914 subst = <ident> '(' <ident>... ')' */
4917 parser::parse_for (location_t
)
4919 auto_vec
<const cpp_token
*> user_id_tokens
;
4920 vec
<user_id
*> user_ids
= vNULL
;
4921 const cpp_token
*token
;
4922 unsigned min_n_opers
= 0, max_n_opers
= 0;
4927 if (token
->type
!= CPP_NAME
)
4930 /* Insert the user defined operators into the operator hash. */
4931 const char *id
= get_ident ();
4932 if (get_operator (id
, true) != NULL
)
4933 fatal_at (token
, "operator already defined");
4934 user_id
*op
= new user_id (id
);
4935 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4937 user_ids
.safe_push (op
);
4938 user_id_tokens
.safe_push (token
);
4940 eat_token (CPP_OPEN_PAREN
);
4943 while ((token
= peek_ident ()) != 0)
4945 const char *oper
= get_ident ();
4946 id_base
*idb
= get_operator (oper
, true);
4948 fatal_at (token
, "no such operator '%s'", oper
);
4952 else if (idb
->nargs
== -1)
4954 else if (idb
->nargs
!= arity
)
4955 fatal_at (token
, "operator '%s' with arity %d does not match "
4956 "others with arity %d", oper
, idb
->nargs
, arity
);
4958 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4961 if (p
->is_oper_list
)
4962 op
->substitutes
.safe_splice (p
->substitutes
);
4964 fatal_at (token
, "iterator cannot be used as operator-list");
4967 op
->substitutes
.safe_push (idb
);
4970 token
= expect (CPP_CLOSE_PAREN
);
4972 unsigned nsubstitutes
= op
->substitutes
.length ();
4973 if (nsubstitutes
== 0)
4974 fatal_at (token
, "A user-defined operator must have at least "
4975 "one substitution");
4976 if (max_n_opers
== 0)
4978 min_n_opers
= nsubstitutes
;
4979 max_n_opers
= nsubstitutes
;
4983 if (nsubstitutes
% min_n_opers
!= 0
4984 && min_n_opers
% nsubstitutes
!= 0)
4985 fatal_at (token
, "All user-defined identifiers must have a "
4986 "multiple number of operator substitutions of the "
4987 "smallest number of substitutions");
4988 if (nsubstitutes
< min_n_opers
)
4989 min_n_opers
= nsubstitutes
;
4990 else if (nsubstitutes
> max_n_opers
)
4991 max_n_opers
= nsubstitutes
;
4995 unsigned n_ids
= user_ids
.length ();
4997 fatal_at (token
, "for requires at least one user-defined identifier");
5000 if (token
->type
== CPP_CLOSE_PAREN
)
5001 fatal_at (token
, "no pattern defined in for");
5003 active_fors
.safe_push (user_ids
);
5007 if (token
->type
== CPP_CLOSE_PAREN
)
5013 /* Remove user-defined operators from the hash again. */
5014 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
5016 if (!user_ids
[i
]->used
)
5017 warning_at (user_id_tokens
[i
],
5018 "operator %s defined but not used", user_ids
[i
]->id
);
5019 operators
->remove_elt (user_ids
[i
]);
5023 /* Parse an identifier associated with a list of operators.
5024 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
5027 parser::parse_operator_list (location_t
)
5029 const cpp_token
*token
= peek ();
5030 const char *id
= get_ident ();
5032 if (get_operator (id
, true) != 0)
5033 fatal_at (token
, "operator %s already defined", id
);
5035 user_id
*op
= new user_id (id
, true);
5038 while ((token
= peek_ident ()) != 0)
5041 const char *oper
= get_ident ();
5042 id_base
*idb
= get_operator (oper
, true);
5045 fatal_at (token
, "no such operator '%s'", oper
);
5049 else if (idb
->nargs
== -1)
5051 else if (arity
!= idb
->nargs
)
5052 fatal_at (token
, "operator '%s' with arity %d does not match "
5053 "others with arity %d", oper
, idb
->nargs
, arity
);
5055 /* We allow composition of multiple operator lists. */
5056 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
5057 op
->substitutes
.safe_splice (p
->substitutes
);
5059 op
->substitutes
.safe_push (idb
);
5062 // Check that there is no junk after id-list
5064 if (token
->type
!= CPP_CLOSE_PAREN
)
5065 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
5067 if (op
->substitutes
.length () == 0)
5068 fatal_at (token
, "operator-list cannot be empty");
5071 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
5075 /* Parse an outer if expression.
5076 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
5079 parser::parse_if (location_t
)
5081 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
5083 const cpp_token
*token
= peek ();
5084 if (token
->type
== CPP_CLOSE_PAREN
)
5085 fatal_at (token
, "no pattern defined in if");
5087 active_ifs
.safe_push (ifexpr
);
5091 if (token
->type
== CPP_CLOSE_PAREN
)
5099 /* Parse a list of predefined predicate identifiers.
5100 preds = '(' 'define_predicates' <ident>... ')' */
5103 parser::parse_predicates (location_t
)
5107 const cpp_token
*token
= peek ();
5108 if (token
->type
!= CPP_NAME
)
5111 add_predicate (get_ident ());
5116 /* Parse outer control structures.
5117 pattern = <preds>|<for>|<if>|<simplify>|<match> */
5120 parser::parse_pattern ()
5122 /* All clauses start with '('. */
5123 eat_token (CPP_OPEN_PAREN
);
5124 const cpp_token
*token
= peek ();
5125 const char *id
= get_ident ();
5126 if (strcmp (id
, "simplify") == 0)
5128 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
5131 else if (strcmp (id
, "match") == 0)
5133 bool with_args
= false;
5134 location_t e_loc
= peek ()->src_loc
;
5135 if (peek ()->type
== CPP_OPEN_PAREN
)
5137 eat_token (CPP_OPEN_PAREN
);
5140 const char *name
= get_ident ();
5141 id_base
*id1
= get_operator (name
);
5145 p
= add_predicate (name
);
5146 user_predicates
.safe_push (p
);
5148 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5151 fatal_at (token
, "cannot add a match to a non-predicate ID");
5152 /* Parse (match <id> <arg>... (match-expr)) here. */
5156 capture_ids
= new cid_map_t
;
5157 e
= new expr (p
, e_loc
);
5158 while (peek ()->type
== CPP_ATSIGN
)
5159 e
->append_op (parse_capture (NULL
, false));
5160 eat_token (CPP_CLOSE_PAREN
);
5163 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5164 || (!e
&& p
->nargs
!= 0)))
5165 fatal_at (token
, "non-matching number of match operands");
5166 p
->nargs
= e
? e
->ops
.length () : 0;
5167 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5170 else if (strcmp (id
, "for") == 0)
5171 parse_for (token
->src_loc
);
5172 else if (strcmp (id
, "if") == 0)
5173 parse_if (token
->src_loc
);
5174 else if (strcmp (id
, "define_predicates") == 0)
5176 if (active_ifs
.length () > 0
5177 || active_fors
.length () > 0)
5178 fatal_at (token
, "define_predicates inside if or for is not supported");
5179 parse_predicates (token
->src_loc
);
5181 else if (strcmp (id
, "define_operator_list") == 0)
5183 if (active_ifs
.length () > 0
5184 || active_fors
.length () > 0)
5185 fatal_at (token
, "operator-list inside if or for is not supported");
5186 parse_operator_list (token
->src_loc
);
5189 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5190 active_ifs
.length () == 0 && active_fors
.length () == 0
5191 ? "'define_predicates', " : "");
5193 eat_token (CPP_CLOSE_PAREN
);
5196 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5200 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5205 if (capture
*c
= dyn_cast
<capture
*> (op
))
5207 cpts
[c
->where
].safe_push (c
);
5208 walk_captures (c
->what
, cpts
);
5210 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5211 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5212 walk_captures (e
->ops
[i
], cpts
);
5215 /* Finish up OP which is a match operand. */
5218 parser::finish_match_operand (operand
*op
)
5220 /* Look for matching captures, diagnose mis-uses of @@ and apply
5221 early lowering and distribution of value_match. */
5222 auto_vec
<vec
<capture
*> > cpts
;
5223 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5224 walk_captures (op
, cpts
);
5225 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5227 capture
*value_match
= NULL
;
5228 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5230 if (cpts
[i
][j
]->value_match
)
5233 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5234 value_match
= cpts
[i
][j
];
5237 if (cpts
[i
].length () == 1 && value_match
)
5238 fatal_at (value_match
->location
, "@@ without a matching capture");
5241 /* Duplicate prevailing capture with the existing ID, create
5242 a fake ID and rewrite all captures to use it. This turns
5243 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5244 value_match
->what
= new capture (value_match
->location
,
5246 value_match
->what
, false);
5247 /* Create a fake ID and rewrite all captures to use it. */
5248 unsigned newid
= get_internal_capture_id ();
5249 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5251 cpts
[i
][j
]->where
= newid
;
5252 cpts
[i
][j
]->value_match
= true;
5259 /* Main entry of the parser. Repeatedly parse outer control structures. */
5261 parser::parser (cpp_reader
*r_
, bool gimple_
)
5266 active_fors
= vNULL
;
5267 simplifiers
= vNULL
;
5268 oper_lists_set
= NULL
;
5271 user_predicates
= vNULL
;
5272 parsing_match_operand
= false;
5275 const cpp_token
*token
= next ();
5276 while (token
->type
!= CPP_EOF
)
5278 _cpp_backup_tokens (r
, 1);
5285 /* Helper for the linemap code. */
5288 round_alloc_size (size_t s
)
5294 /* Construct and display the help menu. */
5299 const char *usage
= "Usage:\n"
5300 " %s [--gimple|--generic] [-v[v]] <input>\n"
5301 " %s [options] [--include=FILE] --header=FILE <input> <output>...\n";
5302 fprintf (stderr
, usage
, progname
, progname
);
5305 /* Write out the correct include to the match-head fle containing the helper
5309 write_header_includes (bool gimple
, FILE *header_file
)
5312 fprintf (header_file
, "#include \"gimple-match-head.cc\"\n");
5314 fprintf (header_file
, "#include \"generic-match-head.cc\"\n");
5317 /* The genmatch generator program. It reads from a pattern description
5318 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5321 main (int argc
, char **argv
)
5325 progname
= "genmatch";
5328 char *s_header_file
= NULL
;
5329 char *s_include_file
= NULL
;
5330 auto_vec
<char *> files
;
5332 int last_file
= argc
- 1;
5333 for (int i
= argc
- 1; i
>= 1; --i
)
5335 if (strcmp (argv
[i
], "--gimple") == 0)
5337 else if (strcmp (argv
[i
], "--generic") == 0)
5339 else if (strncmp (argv
[i
], "--header=", 9) == 0)
5340 s_header_file
= &argv
[i
][9];
5341 else if (strncmp (argv
[i
], "--include=", 10) == 0)
5342 s_include_file
= &argv
[i
][10];
5343 else if (strcmp (argv
[i
], "-v") == 0)
5345 else if (strcmp (argv
[i
], "-vv") == 0)
5347 else if (strncmp (argv
[i
], "--", 2) != 0 && last_file
-- == i
)
5348 files
.safe_push (argv
[i
]);
5356 /* Validate if the combinations are valid. */
5357 if ((files
.length () > 1 && !s_header_file
) || files
.is_empty ())
5363 if (!s_include_file
)
5364 s_include_file
= s_header_file
;
5366 /* Input file is the last in the reverse list. */
5367 input
= files
.pop ();
5369 line_table
= XCNEW (class line_maps
);
5370 linemap_init (line_table
, 0);
5371 line_table
->reallocator
= xrealloc
;
5372 line_table
->round_alloc_size
= round_alloc_size
;
5374 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5375 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5376 cb
->diagnostic
= diagnostic_cb
;
5378 /* Add the build directory to the #include "" search path. */
5379 cpp_dir
*dir
= XCNEW (cpp_dir
);
5380 dir
->name
= getpwd ();
5382 dir
->name
= ASTRDUP (".");
5383 cpp_set_include_chains (r
, dir
, NULL
, false);
5385 if (!cpp_read_main_file (r
, input
))
5387 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5388 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5390 null_id
= new id_base (id_base::NULL_ID
, "null");
5392 /* Pre-seed operators. */
5393 operators
= new hash_table
<id_base
> (1024);
5394 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5395 add_operator (SYM, # SYM, # TYPE, NARGS);
5396 #define END_OF_BASE_TREE_CODES
5398 #undef END_OF_BASE_TREE_CODES
5401 /* Pre-seed builtin functions.
5402 ??? Cannot use N (name) as that is targetm.emultls.get_address
5403 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5404 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5405 add_function (ENUM, "CFN_" # ENUM);
5406 #include "builtins.def"
5408 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5409 add_function (IFN_##CODE, "CFN_" #CODE);
5410 #include "internal-fn.def"
5413 parser
p (r
, gimple
);
5415 /* Create file buffers. */
5416 int n_parts
= files
.is_empty () ? 1 : files
.length ();
5417 auto_vec
<FILE *> parts (n_parts
);
5418 if (files
.is_empty ())
5420 parts
.quick_push (stdout
);
5421 write_header (stdout
, s_include_file
);
5422 write_header_includes (gimple
, stdout
);
5426 for (char *s_file
: files
)
5428 parts
.quick_push (fopen (s_file
, "w"));
5429 write_header (parts
.last (), s_include_file
);
5432 header_file
= fopen (s_header_file
, "w");
5433 fprintf (header_file
, "#ifndef GCC_GIMPLE_MATCH_AUTO_H\n"
5434 "#define GCC_GIMPLE_MATCH_AUTO_H\n");
5435 write_header_includes (gimple
, header_file
);
5438 /* Go over all predicates defined with patterns and perform
5439 lowering and code generation. */
5440 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5442 predicate_id
*pred
= p
.user_predicates
[i
];
5443 lower (pred
->matchers
, gimple
);
5446 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5447 print_matches (pred
->matchers
[j
]);
5450 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5451 dt
.insert (pred
->matchers
[j
], j
);
5456 /* Cycle the file buffers. */
5457 FILE *f
= choose_output (parts
);
5459 write_predicate (f
, pred
, dt
, gimple
);
5462 /* Lower the main simplifiers and generate code for them. */
5463 lower (p
.simplifiers
, gimple
);
5466 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5467 print_matches (p
.simplifiers
[i
]);
5470 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5471 dt
.insert (p
.simplifiers
[i
], i
);
5476 dt
.gen (parts
, gimple
);
5478 for (FILE *f
: parts
)
5480 fprintf (f
, "#pragma GCC diagnostic pop\n");
5486 fprintf (header_file
, "\n#endif /* GCC_GIMPLE_MATCH_AUTO_H. */\n");
5487 fclose (header_file
);
5491 cpp_finish (r
, NULL
);