1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2024 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"
28 #include "rich-location.h"
30 #include "hash-table.h"
33 #include "ordered-hash-map.h"
36 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
37 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
38 size_t, size_t MEM_STAT_DECL
)
42 void ggc_free (void *)
49 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
55 static class line_maps
*line_table
;
57 /* The rich_location class within libcpp requires a way to expand
58 location_t instances, and relies on the client code
59 providing a symbol named
60 linemap_client_expand_location_to_spelling_point
63 This is the implementation for genmatch. */
66 linemap_client_expand_location_to_spelling_point (const line_maps
*set
,
70 const struct line_map_ordinary
*map
;
71 loc
= linemap_resolve_location (set
, loc
, LRK_SPELLING_LOCATION
, &map
);
72 return linemap_expand_location (set
, map
, loc
);
76 #if GCC_VERSION >= 4001
77 __attribute__((format (printf
, 5, 0)))
79 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
80 enum cpp_warning_reason
, rich_location
*richloc
,
81 const char *msg
, va_list *ap
)
83 const line_map_ordinary
*map
;
84 location_t location
= richloc
->get_loc ();
85 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
86 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
87 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
88 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
89 vfprintf (stderr
, msg
, *ap
);
90 fprintf (stderr
, "\n");
91 FILE *f
= fopen (loc
.file
, "r");
97 if (!fgets (buf
, 128, f
))
99 if (buf
[strlen (buf
) - 1] != '\n')
106 fprintf (stderr
, "%s", buf
);
107 for (int i
= 0; i
< loc
.column
- 1; ++i
)
110 fputc ('\n', stderr
);
115 if (errtype
== CPP_DL_FATAL
)
121 #if GCC_VERSION >= 4001
122 __attribute__((format (printf
, 2, 3)))
124 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
126 rich_location
richloc (line_table
, tk
->src_loc
);
129 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
134 #if GCC_VERSION >= 4001
135 __attribute__((format (printf
, 2, 3)))
137 fatal_at (location_t loc
, const char *msg
, ...)
139 rich_location
richloc (line_table
, loc
);
142 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
147 #if GCC_VERSION >= 4001
148 __attribute__((format (printf
, 2, 3)))
150 warning_at (const cpp_token
*tk
, const char *msg
, ...)
152 rich_location
richloc (line_table
, tk
->src_loc
);
155 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
160 #if GCC_VERSION >= 4001
161 __attribute__((format (printf
, 2, 3)))
163 warning_at (location_t loc
, const char *msg
, ...)
165 rich_location
richloc (line_table
, loc
);
168 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
172 /* Like fprintf, but print INDENT spaces at the beginning. */
175 #if GCC_VERSION >= 4001
176 __attribute__((format (printf
, 3, 4)))
178 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
181 for (; indent
>= 8; indent
-= 8)
183 fprintf (f
, "%*s", indent
, "");
184 va_start (ap
, format
);
185 vfprintf (f
, format
, ap
);
189 /* Secondary stream for fp_decl. */
190 static FILE *header_file
;
192 /* Start or continue emitting a declaration in fprintf-like manner,
193 printing both to F and global header_file, if non-null. */
195 #if GCC_VERSION >= 4001
196 __attribute__((format (printf
, 2, 3)))
198 fp_decl (FILE *f
, const char *format
, ...)
201 va_start (ap
, format
);
202 vfprintf (f
, format
, ap
);
208 va_start (ap
, format
);
209 vfprintf (header_file
, format
, ap
);
213 /* Finish a declaration being emitted by fp_decl. */
215 fp_decl_done (FILE *f
, const char *trailer
)
217 fprintf (f
, "%s\n", trailer
);
219 fprintf (header_file
, "%s;", trailer
);
222 /* Line numbers for use by indirect line directives. */
223 static vec
<int> dbg_line_numbers
;
226 write_header_declarations (bool gimple
, FILE *f
)
228 fprintf (f
, "\nextern void\n%s_dump_logs (const char *file1, int line1_id, "
229 "const char *file2, int line2, bool simplify);\n",
230 gimple
? "gimple" : "generic");
234 define_dump_logs (bool gimple
, FILE *f
)
236 if (dbg_line_numbers
.is_empty ())
239 fprintf (f
, "void\n%s_dump_logs (const char *file1, int line1_id, "
240 "const char *file2, int line2, bool simplify)\n{\n",
241 gimple
? "gimple" : "generic");
243 fprintf_indent (f
, 2, "static int dbg_line_numbers[%d] = {",
244 dbg_line_numbers
.length ());
246 for (unsigned i
= 0; i
< dbg_line_numbers
.length () - 1; i
++)
251 fprintf (f
, "%d, ", dbg_line_numbers
[i
]);
253 fprintf (f
, "%d\n };\n\n", dbg_line_numbers
.last ());
256 fprintf_indent (f
, 2, "fprintf (dump_file, \"%%s "
257 "%%s:%%d, %%s:%%d\\n\",\n");
258 fprintf_indent (f
, 10, "simplify ? \"Applying pattern\" : "
259 "\"Matching expression\", file1, "
260 "dbg_line_numbers[line1_id], file2, line2);");
262 fprintf (f
, "\n}\n\n");
266 output_line_directive (FILE *f
, location_t location
,
267 bool dumpfile
= false, bool fnargs
= false,
268 bool indirect_line_numbers
= false)
270 typedef pair_hash
<nofree_string_hash
, int_hash
<int, -1>> location_hash
;
271 static hash_map
<location_hash
, int> loc_id_map
;
272 const line_map_ordinary
*map
;
273 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
274 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
277 /* When writing to a dumpfile only dump the filename. */
278 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
279 #if defined(DIR_SEPARATOR_2)
280 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
281 if (pos2
&& (!file
|| (pos2
> file
)))
291 if (indirect_line_numbers
)
294 int &loc_id
= loc_id_map
.get_or_insert (
295 std::make_pair (file
, loc
.line
), &existed
);
298 loc_id
= dbg_line_numbers
.length ();
299 dbg_line_numbers
.safe_push (loc
.line
);
302 fprintf (f
, "\"%s\", %d", file
, loc_id
);
305 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
308 fprintf (f
, "%s:%d", file
, loc
.line
);
310 else if (verbose
>= 2)
311 /* Other gen programs really output line directives here, at least for
312 development it's right now more convenient to have line information
313 from the generated file. Still keep the directives as comment for now
314 to easily back-point to the meta-description. */
315 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
318 /* Find the file to write into next. We try to evenly distribute the contents
319 over the different files. */
321 #define SIZED_BASED_CHUNKS 1
324 choose_output (const vec
<FILE *> &parts
)
326 #ifdef SIZED_BASED_CHUNKS
327 FILE *shortest
= NULL
;
329 for (FILE *part
: parts
)
331 long len
= ftell (part
);
332 if (!shortest
|| min
> len
)
333 shortest
= part
, min
= len
;
337 static int current_file
;
338 return parts
[current_file
++ % parts
.length ()];
343 /* Pull in tree codes and builtin function codes from their
346 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
353 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
354 enum built_in_function
{
355 #include "builtins.def"
359 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
361 #include "internal-fn.def"
366 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
367 CFN_##ENUM = int (ENUM),
368 #include "builtins.def"
370 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
371 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
372 #include "internal-fn.def"
377 #include "case-cfn-macros.h"
379 /* Return true if CODE represents a commutative tree code. Otherwise
382 commutative_tree_code (enum tree_code code
)
388 case MULT_HIGHPART_EXPR
:
403 case WIDEN_MULT_EXPR
:
404 case VEC_WIDEN_MULT_HI_EXPR
:
405 case VEC_WIDEN_MULT_LO_EXPR
:
406 case VEC_WIDEN_MULT_EVEN_EXPR
:
407 case VEC_WIDEN_MULT_ODD_EXPR
:
416 /* Return true if CODE represents a ternary tree code for which the
417 first two operands are commutative. Otherwise return false. */
419 commutative_ternary_tree_code (enum tree_code code
)
423 case WIDEN_MULT_PLUS_EXPR
:
424 case WIDEN_MULT_MINUS_EXPR
:
434 /* Return true if CODE is a comparison. */
437 comparison_code_p (enum tree_code code
)
464 /* Base class for all identifiers the parser knows. */
466 class id_base
: public nofree_ptr_hash
<id_base
>
469 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
471 id_base (id_kind
, const char *, int = -1);
477 /* hash_table support. */
478 static inline hashval_t
hash (const id_base
*);
479 static inline int equal (const id_base
*, const id_base
*);
483 id_base::hash (const id_base
*op
)
489 id_base::equal (const id_base
*op1
,
492 return (op1
->hashval
== op2
->hashval
493 && strcmp (op1
->id
, op2
->id
) == 0);
496 /* The special id "null", which matches nothing. */
497 static id_base
*null_id
;
499 /* Hashtable of known pattern operators. This is pre-seeded from
500 all known tree codes and all known builtin function ids. */
501 static hash_table
<id_base
> *operators
;
503 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
508 hashval
= htab_hash_string (id
);
511 /* Identifier that maps to a tree code. */
513 class operator_id
: public id_base
516 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
518 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
523 /* Identifier that maps to a builtin or internal function code. */
525 class fn_id
: public id_base
528 fn_id (enum built_in_function fn_
, const char *id_
)
529 : id_base (id_base::FN
, id_
), fn (fn_
) {}
530 fn_id (enum internal_fn fn_
, const char *id_
)
531 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
537 /* Identifier that maps to a user-defined predicate. */
539 class predicate_id
: public id_base
542 predicate_id (const char *id_
)
543 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
544 vec
<simplify
*> matchers
;
547 /* Identifier that maps to a operator defined by a 'for' directive. */
549 class user_id
: public id_base
552 user_id (const char *id_
, bool is_oper_list_
= false)
553 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
554 used (false), is_oper_list (is_oper_list_
) {}
555 vec
<id_base
*> substitutes
;
563 is_a_helper
<fn_id
*>::test (id_base
*id
)
565 return id
->kind
== id_base::FN
;
571 is_a_helper
<operator_id
*>::test (id_base
*id
)
573 return id
->kind
== id_base::CODE
;
579 is_a_helper
<predicate_id
*>::test (id_base
*id
)
581 return id
->kind
== id_base::PREDICATE
;
587 is_a_helper
<user_id
*>::test (id_base
*id
)
589 return id
->kind
== id_base::USER
;
592 /* If ID has a pair of consecutive, commutative operands, return the
593 index of the first, otherwise return -1. */
596 commutative_op (id_base
*id
)
598 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
600 if (commutative_tree_code (code
->code
)
601 || commutative_ternary_tree_code (code
->code
))
605 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
627 case CFN_COND_LEN_ADD
:
628 case CFN_COND_LEN_MUL
:
629 case CFN_COND_LEN_MIN
:
630 case CFN_COND_LEN_MAX
:
631 case CFN_COND_LEN_FMIN
:
632 case CFN_COND_LEN_FMAX
:
633 case CFN_COND_LEN_AND
:
634 case CFN_COND_LEN_IOR
:
635 case CFN_COND_LEN_XOR
:
636 case CFN_COND_LEN_FMA
:
637 case CFN_COND_LEN_FMS
:
638 case CFN_COND_LEN_FNMA
:
639 case CFN_COND_LEN_FNMS
:
645 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
647 int res
= commutative_op (uid
->substitutes
[0]);
650 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
651 if (res
!= commutative_op (uid
->substitutes
[i
]))
658 /* Add a predicate identifier to the hash. */
660 static predicate_id
*
661 add_predicate (const char *id
)
663 predicate_id
*p
= new predicate_id (id
);
664 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
666 fatal ("duplicate id definition");
671 /* Add a tree code identifier to the hash. */
674 add_operator (enum tree_code code
, const char *id
,
675 const char *tcc
, unsigned nargs
)
677 if (strcmp (tcc
, "tcc_unary") != 0
678 && strcmp (tcc
, "tcc_binary") != 0
679 && strcmp (tcc
, "tcc_comparison") != 0
680 && strcmp (tcc
, "tcc_expression") != 0
681 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
682 && strcmp (tcc
, "tcc_reference") != 0
683 /* To have INTEGER_CST and friends as "predicate operators". */
684 && strcmp (tcc
, "tcc_constant") != 0
685 /* And allow CONSTRUCTOR for vector initializers. */
686 && !(code
== CONSTRUCTOR
)
687 /* Allow SSA_NAME as predicate operator. */
688 && !(code
== SSA_NAME
))
690 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
691 if (code
== ADDR_EXPR
)
693 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
694 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
696 fatal ("duplicate id definition");
700 /* Add a built-in or internal function identifier to the hash. ID is
701 the name of its CFN_* enumeration value. */
703 template <typename T
>
705 add_function (T code
, const char *id
)
707 fn_id
*fn
= new fn_id (code
, id
);
708 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
710 fatal ("duplicate id definition");
714 /* Helper for easy comparing ID with tree code CODE. */
717 operator==(id_base
&id
, enum tree_code code
)
719 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
720 return oid
->code
== code
;
724 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
727 get_operator (const char *id
, bool allow_null
= false)
729 if (allow_null
&& strcmp (id
, "null") == 0)
732 id_base
tem (id_base::CODE
, id
);
734 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
737 /* If this is a user-defined identifier track whether it was used. */
738 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
744 bool all_upper
= true;
745 bool all_lower
= true;
746 for (unsigned int i
= 0; id
[i
]; ++i
)
749 else if (ISLOWER (id
[i
]))
753 /* Try in caps with _EXPR appended. */
754 id2
= ACONCAT ((id
, "_EXPR", NULL
));
755 for (unsigned int i
= 0; id2
[i
]; ++i
)
756 id2
[i
] = TOUPPER (id2
[i
]);
758 else if (all_upper
&& startswith (id
, "IFN_"))
759 /* Try CFN_ instead of IFN_. */
760 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
761 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
762 /* Try prepending CFN_. */
763 id2
= ACONCAT (("CFN_", id
, NULL
));
767 new (&tem
) id_base (id_base::CODE
, id2
);
768 return operators
->find_with_hash (&tem
, tem
.hashval
);
771 /* Return the comparison operators that results if the operands are
772 swapped. This is safe for floating-point. */
775 swap_tree_comparison (operator_id
*p
)
787 return get_operator ("LT_EXPR");
789 return get_operator ("LE_EXPR");
791 return get_operator ("GT_EXPR");
793 return get_operator ("GE_EXPR");
795 return get_operator ("UNLT_EXPR");
797 return get_operator ("UNLE_EXPR");
799 return get_operator ("UNGT_EXPR");
801 return get_operator ("UNGE_EXPR");
807 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
810 /* The AST produced by parsing of the pattern definitions. */
815 /* The base class for operands. */
819 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
820 operand (enum op_type type_
, location_t loc_
)
821 : type (type_
), location (loc_
) {}
824 virtual void gen_transform (FILE *, int, const char *, bool, int,
825 const char *, capture_info
*,
828 { gcc_unreachable (); }
831 /* A predicate operand. Predicates are leafs in the AST. */
833 class predicate
: public operand
836 predicate (predicate_id
*p_
, location_t loc
)
837 : operand (OP_PREDICATE
, loc
), p (p_
) {}
841 /* An operand that constitutes an expression. Expressions include
842 function calls and user-defined predicate invocations. */
844 class expr
: public operand
847 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
848 : operand (OP_EXPR
, loc
), operation (operation_
),
849 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
850 is_generic (false), force_single_use (false), force_leaf (false),
851 match_phi (false), opt_grp (0) {}
853 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
854 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
855 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
856 force_leaf (e
->force_leaf
), match_phi (e
->match_phi
),
857 opt_grp (e
->opt_grp
) {}
858 void append_op (operand
*op
) { ops
.safe_push (op
); }
859 /* The operator and its operands. */
862 /* An explicitely specified type - used exclusively for conversions. */
863 const char *expr_type
;
864 /* Whether the operation is to be applied commutatively. This is
865 later lowered to two separate patterns. */
867 /* Whether the expression is expected to be in GENERIC form. */
869 /* Whether pushing any stmt to the sequence should be conditional
870 on this expression having a single-use. */
871 bool force_single_use
;
872 /* Whether in the result expression this should be a leaf node
873 with any children simplified down to simple operands. */
875 /* Whether the COND_EXPR is matching PHI gimple, default false. */
877 /* If non-zero, the group for optional handling. */
878 unsigned char opt_grp
;
879 void gen_transform (FILE *f
, int, const char *, bool, int,
880 const char *, capture_info
*,
881 dt_operand
** = 0, int = 0) override
;
884 /* An operator that is represented by native C code. This is always
885 a leaf operand in the AST. This class is also used to represent
886 the code to be generated for 'if' and 'with' expressions. */
888 class c_expr
: public operand
891 /* A mapping of an identifier and its replacement. Used to apply
897 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
900 c_expr (cpp_reader
*r_
, location_t loc
,
901 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
902 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
903 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
904 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
905 /* cpplib tokens and state to transform this back to source. */
908 cid_map_t
*capture_ids
;
909 /* The number of statements parsed (well, the number of ';'s). */
911 /* The identifier replacement vector. */
913 void gen_transform (FILE *f
, int, const char *, bool, int,
914 const char *, capture_info
*,
915 dt_operand
** = 0, int = 0) final override
;
918 /* A wrapper around another operand that captures its value. */
920 class capture
: public operand
923 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
924 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
926 /* Identifier index for the value. */
928 /* Whether in a match of two operands the compare should be for
929 equal values rather than equal atoms (boils down to a type
932 /* The captured value. */
934 void gen_transform (FILE *f
, int, const char *, bool, int,
935 const char *, capture_info
*,
936 dt_operand
** = 0, int = 0) final override
;
941 class if_expr
: public operand
944 if_expr (location_t loc
)
945 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
951 /* with expression. */
953 class with_expr
: public operand
956 with_expr (location_t loc
)
957 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
965 is_a_helper
<capture
*>::test (operand
*op
)
967 return op
->type
== operand::OP_CAPTURE
;
973 is_a_helper
<predicate
*>::test (operand
*op
)
975 return op
->type
== operand::OP_PREDICATE
;
981 is_a_helper
<c_expr
*>::test (operand
*op
)
983 return op
->type
== operand::OP_C_EXPR
;
989 is_a_helper
<expr
*>::test (operand
*op
)
991 return op
->type
== operand::OP_EXPR
;
997 is_a_helper
<if_expr
*>::test (operand
*op
)
999 return op
->type
== operand::OP_IF
;
1005 is_a_helper
<with_expr
*>::test (operand
*op
)
1007 return op
->type
== operand::OP_WITH
;
1010 /* The main class of a pattern and its transform. This is used to
1011 represent both (simplify ...) and (match ...) kinds. The AST
1012 duplicates all outer 'if' and 'for' expressions here so each
1013 simplify can exist in isolation. */
1018 enum simplify_kind
{ SIMPLIFY
, MATCH
};
1020 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
1021 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
1022 cid_map_t
*capture_ids_
)
1023 : kind (kind_
), id (id_
), match (match_
), result (result_
),
1024 for_vec (for_vec_
), for_subst_vec (vNULL
),
1025 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
1028 /* ID. This is kept to easily associate related simplifies expanded
1029 from the same original one. */
1031 /* The expression that is matched against the GENERIC or GIMPLE IL. */
1033 /* For a (simplify ...) an expression with ifs and withs with the expression
1034 produced when the pattern applies in the leafs.
1035 For a (match ...) the leafs are either empty if it is a simple predicate
1036 or the single expression specifying the matched operands. */
1037 class operand
*result
;
1038 /* Collected 'for' expression operators that have to be replaced
1039 in the lowering phase. */
1040 vec
<vec
<user_id
*> > for_vec
;
1041 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
1042 /* A map of capture identifiers to indexes. */
1043 cid_map_t
*capture_ids
;
1047 /* Debugging routines for dumping the AST. */
1050 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
1052 if (capture
*c
= dyn_cast
<capture
*> (o
))
1054 if (c
->what
&& flattened
== false)
1055 print_operand (c
->what
, f
, flattened
);
1056 fprintf (f
, "@%u", c
->where
);
1059 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
1060 fprintf (f
, "%s", p
->p
->id
);
1062 else if (is_a
<c_expr
*> (o
))
1063 fprintf (f
, "c_expr");
1065 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1067 if (e
->ops
.length () == 0)
1068 fprintf (f
, "%s", e
->operation
->id
);
1071 fprintf (f
, "(%s", e
->operation
->id
);
1073 if (flattened
== false)
1075 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1078 print_operand (e
->ops
[i
], f
, flattened
);
1090 print_matches (class simplify
*s
, FILE *f
= stderr
)
1092 fprintf (f
, "for expression: ");
1093 print_operand (s
->match
, f
);
1100 /* Lowering of commutative operators. */
1103 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
1104 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
1106 if (n
== ops_vector
.length ())
1108 vec
<operand
*> xv
= v
.copy ();
1109 result
.safe_push (xv
);
1113 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
1115 v
[n
] = ops_vector
[n
][i
];
1116 cartesian_product (ops_vector
, result
, v
, n
+ 1);
1120 /* Lower OP to two operands in case it is marked as commutative. */
1122 static vec
<operand
*>
1123 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
1125 vec
<operand
*> ret
= vNULL
;
1127 if (capture
*c
= dyn_cast
<capture
*> (op
))
1134 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
1135 for (unsigned i
= 0; i
< v
.length (); ++i
)
1137 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
1144 expr
*e
= dyn_cast
<expr
*> (op
);
1145 if (!e
|| e
->ops
.length () == 0)
1151 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1152 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1153 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1155 auto_vec
< vec
<operand
*> > result
;
1156 auto_vec
<operand
*> v (e
->ops
.length ());
1157 v
.quick_grow_cleared (e
->ops
.length ());
1158 cartesian_product (ops_vector
, result
, v
, 0);
1161 for (unsigned i
= 0; i
< result
.length (); ++i
)
1163 expr
*ne
= new expr (e
);
1164 ne
->is_commutative
= false;
1165 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1166 ne
->append_op (result
[i
][j
]);
1170 if (!e
->is_commutative
)
1173 /* The operation is always binary if it isn't inherently commutative. */
1174 int natural_opno
= commutative_op (e
->operation
);
1175 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1176 for (unsigned i
= 0; i
< result
.length (); ++i
)
1178 expr
*ne
= new expr (e
);
1179 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1181 if (comparison_code_p (r
->code
))
1182 ne
->operation
= swap_tree_comparison (r
);
1184 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1186 bool found_compare
= false;
1187 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1188 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1190 if (comparison_code_p (q
->code
)
1191 && swap_tree_comparison (q
) != q
)
1193 found_compare
= true;
1199 user_id
*newop
= new user_id ("<internal>");
1200 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1202 id_base
*subst
= p
->substitutes
[j
];
1203 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1205 if (comparison_code_p (q
->code
))
1206 subst
= swap_tree_comparison (q
);
1208 newop
->substitutes
.safe_push (subst
);
1210 ne
->operation
= newop
;
1211 /* Search for 'p' inside the for vector and push 'newop'
1212 to the same level. */
1213 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1214 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1215 if (for_vec
[j
][k
] == p
)
1217 for_vec
[j
].safe_push (newop
);
1223 ne
->is_commutative
= false;
1224 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1226 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1227 ne
->append_op (result
[i
][old_j
]);
1235 /* Lower operations marked as commutative in the AST of S and push
1236 the resulting patterns to SIMPLIFIERS. */
1239 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1241 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1242 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1244 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1245 s
->for_vec
, s
->capture_ids
);
1246 simplifiers
.safe_push (ns
);
1250 /* Strip conditional operations using group GRP from O and its
1251 children if STRIP, else replace them with an unconditional operation. */
1254 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1256 if (capture
*c
= dyn_cast
<capture
*> (o
))
1259 return new capture (c
->location
, c
->where
,
1260 lower_opt (c
->what
, grp
, strip
),
1266 expr
*e
= dyn_cast
<expr
*> (o
);
1270 if (e
->opt_grp
== grp
)
1273 return lower_opt (e
->ops
[0], grp
, strip
);
1275 expr
*ne
= new expr (e
);
1277 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1281 expr
*ne
= new expr (e
);
1282 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1283 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1288 /* Determine whether O or its children uses the conditional operation
1292 has_opt (operand
*o
, unsigned char grp
)
1294 if (capture
*c
= dyn_cast
<capture
*> (o
))
1297 return has_opt (c
->what
, grp
);
1302 expr
*e
= dyn_cast
<expr
*> (o
);
1306 if (e
->opt_grp
== grp
)
1309 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1310 if (has_opt (e
->ops
[i
], grp
))
1316 /* Lower conditional convert operators in O, expanding it to a vector
1319 static vec
<operand
*>
1320 lower_opt (operand
*o
)
1322 vec
<operand
*> v1
= vNULL
, v2
;
1326 /* Conditional operations are lowered to a pattern with the
1327 operation and one without. All different conditional operation
1328 groups are lowered separately. */
1330 for (unsigned i
= 1; i
<= 10; ++i
)
1333 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1334 if (has_opt (v1
[j
], i
))
1336 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1337 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1343 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1344 v1
.safe_push (v2
[j
]);
1351 /* Lower conditional convert operators in the AST of S and push
1352 the resulting multiple patterns to SIMPLIFIERS. */
1355 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1357 vec
<operand
*> matchers
= lower_opt (s
->match
);
1358 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1360 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1361 s
->for_vec
, s
->capture_ids
);
1362 simplifiers
.safe_push (ns
);
1366 /* Lower the compare operand of COND_EXPRs to a
1367 GENERIC and a GIMPLE variant. */
1369 static vec
<operand
*>
1370 lower_cond (operand
*o
)
1372 vec
<operand
*> ro
= vNULL
;
1374 if (capture
*c
= dyn_cast
<capture
*> (o
))
1378 vec
<operand
*> lop
= vNULL
;
1379 lop
= lower_cond (c
->what
);
1381 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1382 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1388 expr
*e
= dyn_cast
<expr
*> (o
);
1389 if (!e
|| e
->ops
.length () == 0)
1395 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1396 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1397 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1399 auto_vec
< vec
<operand
*> > result
;
1400 auto_vec
<operand
*> v (e
->ops
.length ());
1401 v
.quick_grow_cleared (e
->ops
.length ());
1402 cartesian_product (ops_vector
, result
, v
, 0);
1404 for (unsigned i
= 0; i
< result
.length (); ++i
)
1406 expr
*ne
= new expr (e
);
1407 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1408 ne
->append_op (result
[i
][j
]);
1410 /* If this is a COND with a captured expression or an
1411 expression with two operands then also match a GENERIC
1412 form on the compare. */
1413 if (*e
->operation
== COND_EXPR
1414 && ((is_a
<capture
*> (e
->ops
[0])
1415 && as_a
<capture
*> (e
->ops
[0])->what
1416 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1418 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1419 || (is_a
<expr
*> (e
->ops
[0])
1420 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1423 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1424 ne
->append_op (result
[i
][j
]);
1425 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1427 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1428 expr
*cmp
= new expr (ocmp
);
1429 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1430 cmp
->append_op (ocmp
->ops
[j
]);
1431 cmp
->is_generic
= true;
1432 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1437 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1438 expr
*cmp
= new expr (ocmp
);
1439 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1440 cmp
->append_op (ocmp
->ops
[j
]);
1441 cmp
->is_generic
= true;
1451 /* Lower the compare operand of COND_EXPRs to a
1452 GENERIC and a GIMPLE variant. */
1455 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1457 vec
<operand
*> matchers
= lower_cond (s
->match
);
1458 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1460 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1461 s
->for_vec
, s
->capture_ids
);
1462 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1463 simplifiers
.safe_push (ns
);
1467 /* Return true if O refers to ID. */
1470 contains_id (operand
*o
, user_id
*id
)
1472 if (capture
*c
= dyn_cast
<capture
*> (o
))
1473 return c
->what
&& contains_id (c
->what
, id
);
1475 if (expr
*e
= dyn_cast
<expr
*> (o
))
1477 if (e
->operation
== id
)
1479 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1480 if (contains_id (e
->ops
[i
], id
))
1485 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1486 return (contains_id (w
->with
, id
)
1487 || contains_id (w
->subexpr
, id
));
1489 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1490 return (contains_id (ife
->cond
, id
)
1491 || contains_id (ife
->trueexpr
, id
)
1492 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1494 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1495 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1501 /* In AST operand O replace operator ID with operator WITH. */
1504 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1506 /* Deep-copy captures and expressions, replacing operations as
1508 if (capture
*c
= dyn_cast
<capture
*> (o
))
1512 return new capture (c
->location
, c
->where
,
1513 replace_id (c
->what
, id
, with
), c
->value_match
);
1515 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1517 expr
*ne
= new expr (e
);
1518 if (e
->operation
== id
)
1519 ne
->operation
= with
;
1520 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1521 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1524 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1526 with_expr
*nw
= new with_expr (w
->location
);
1527 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1528 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1531 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1533 if_expr
*nife
= new if_expr (ife
->location
);
1534 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1535 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1537 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1541 /* For c_expr we simply record a string replacement table which is
1542 applied at code-generation time. */
1543 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1545 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1546 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1547 return new c_expr (ce
->r
, ce
->location
,
1548 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1554 /* Return true if the binary operator OP is ok for delayed substitution
1555 during for lowering. */
1558 binary_ok (operator_id
*op
)
1565 case TRUNC_DIV_EXPR
:
1567 case FLOOR_DIV_EXPR
:
1568 case ROUND_DIV_EXPR
:
1569 case TRUNC_MOD_EXPR
:
1571 case FLOOR_MOD_EXPR
:
1572 case ROUND_MOD_EXPR
:
1574 case EXACT_DIV_EXPR
:
1586 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1589 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1591 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1592 unsigned worklist_start
= 0;
1593 auto_vec
<simplify
*> worklist
;
1594 worklist
.safe_push (sin
);
1596 /* Lower each recorded for separately, operating on the
1597 set of simplifiers created by the previous one.
1598 Lower inner-to-outer so inner for substitutes can refer
1599 to operators replaced by outer fors. */
1600 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1602 vec
<user_id
*>& ids
= for_vec
[fi
];
1603 unsigned n_ids
= ids
.length ();
1604 unsigned max_n_opers
= 0;
1605 bool can_delay_subst
= true;
1606 for (unsigned i
= 0; i
< n_ids
; ++i
)
1608 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1609 max_n_opers
= ids
[i
]->substitutes
.length ();
1610 /* Require that all substitutes are of the same kind so that
1611 if we delay substitution to the result op code generation
1612 can look at the first substitute for deciding things like
1613 types of operands. */
1614 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1615 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1616 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1617 can_delay_subst
= false;
1618 else if (operator_id
*op
1619 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1622 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1623 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1624 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1626 /* Unfortunately we can't just allow all tcc_binary. */
1627 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1628 && strcmp (op0
->tcc
, "tcc_binary") == 0
1632 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1633 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1634 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1635 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1638 can_delay_subst
= false;
1640 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1643 can_delay_subst
= false;
1645 if (sin
->kind
== simplify::MATCH
1649 unsigned worklist_end
= worklist
.length ();
1650 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1652 simplify
*s
= worklist
[si
];
1653 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1655 operand
*match_op
= s
->match
;
1656 operand
*result_op
= s
->result
;
1657 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1659 for (unsigned i
= 0; i
< n_ids
; ++i
)
1661 user_id
*id
= ids
[i
];
1662 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1664 && (contains_id (match_op
, id
)
1665 || contains_id (result_op
, id
)))
1670 subst
.quick_push (std::make_pair (id
, oper
));
1671 if (sin
->kind
== simplify::SIMPLIFY
1672 || !can_delay_subst
)
1673 match_op
= replace_id (match_op
, id
, oper
);
1675 && !can_delay_subst
)
1676 result_op
= replace_id (result_op
, id
, oper
);
1681 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1682 vNULL
, s
->capture_ids
);
1683 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1686 ns
->for_subst_vec
.safe_splice (subst
);
1688 worklist
.safe_push (ns
);
1691 worklist_start
= worklist_end
;
1694 /* Copy out the result from the last for lowering. */
1695 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1696 simplifiers
.safe_push (worklist
[i
]);
1699 /* Lower the AST for everything in SIMPLIFIERS. */
1702 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1704 auto_vec
<simplify
*> out_simplifiers
;
1705 for (auto s
: simplifiers
)
1706 lower_opt (s
, out_simplifiers
);
1708 simplifiers
.truncate (0);
1709 for (auto s
: out_simplifiers
)
1710 lower_commutative (s
, simplifiers
);
1712 /* Lower for needs to happen before lowering cond
1713 to support (for cnd (cond vec_cond)). This is
1714 safe as substitution delay does not happen for
1715 cond or vec_cond. */
1716 out_simplifiers
.truncate (0);
1717 for (auto s
: simplifiers
)
1718 lower_for (s
, out_simplifiers
);
1720 simplifiers
.truncate (0);
1722 for (auto s
: out_simplifiers
)
1723 lower_cond (s
, simplifiers
);
1725 simplifiers
.safe_splice (out_simplifiers
);
1731 /* The decision tree built for generating GIMPLE and GENERIC pattern
1732 matching code. It represents the 'match' expression of all
1733 simplifies and has those as its leafs. */
1737 /* A hash-map collecting semantically equivalent leafs in the decision
1738 tree for splitting out to separate functions. */
1747 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1750 static inline hashval_t
hash (const key_type
&);
1751 static inline bool equal_keys (const key_type
&, const key_type
&);
1752 template <typename T
> static inline void remove (T
&) {}
1755 typedef ordered_hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1758 /* Current simplifier ID we are processing during insertion into the
1760 static unsigned current_id
;
1762 /* Decision tree base class, used for DT_NODE. */
1767 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1772 vec
<dt_node
*> kids
;
1776 unsigned total_size
;
1779 dt_node (enum dt_type type_
, dt_node
*parent_
)
1780 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1782 dt_node
*append_node (dt_node
*);
1783 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1784 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1785 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1787 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1789 virtual void gen (FILE *, int, bool, int) {}
1791 void gen_kids (FILE *, int, bool, int);
1792 void gen_kids_1 (FILE *, int, bool, int,
1793 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1794 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1795 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1797 void analyze (sinfo_map_t
&);
1800 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1802 class dt_operand
: public dt_node
1806 dt_operand
*match_dop
;
1811 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1812 dt_operand
*parent_
, unsigned pos_
)
1813 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1814 pos (pos_
), value_match (false), for_id (current_id
) {}
1816 void gen (FILE *, int, bool, int) final override
;
1817 unsigned gen_predicate (FILE *, int, const char *, bool);
1818 unsigned gen_match_op (FILE *, int, const char *, bool);
1820 unsigned gen_gimple_expr (FILE *, int, int);
1821 unsigned gen_generic_expr (FILE *, int, const char *);
1823 char *get_name (char *);
1824 void gen_opname (char *, unsigned);
1825 void gen_phi_on_cond (FILE *, int, int);
1828 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1830 class dt_simplify
: public dt_node
1834 unsigned pattern_no
;
1835 dt_operand
**indexes
;
1838 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1839 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1840 indexes (indexes_
), info (NULL
) {}
1842 void gen_1 (FILE *, int, bool, operand
*);
1843 void gen (FILE *f
, int, bool, int) final override
;
1849 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1851 return (n
->type
== dt_node::DT_OPERAND
1852 || n
->type
== dt_node::DT_MATCH
1853 || n
->type
== dt_node::DT_TRUE
);
1859 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1861 return n
->type
== dt_node::DT_SIMPLIFY
;
1866 /* A container for the actual decision tree. */
1873 void insert (class simplify
*, unsigned);
1874 void gen (vec
<FILE *> &f
, bool gimple
);
1875 void print (FILE *f
= stderr
);
1877 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1879 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1880 unsigned pos
= 0, dt_node
*parent
= 0);
1881 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1882 static bool cmp_node (dt_node
*, dt_node
*);
1883 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1886 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1889 cmp_operand (operand
*o1
, operand
*o2
)
1891 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1894 if (o1
->type
== operand::OP_PREDICATE
)
1896 predicate
*p1
= as_a
<predicate
*>(o1
);
1897 predicate
*p2
= as_a
<predicate
*>(o2
);
1898 return p1
->p
== p2
->p
;
1900 else if (o1
->type
== operand::OP_EXPR
)
1902 expr
*e1
= static_cast<expr
*>(o1
);
1903 expr
*e2
= static_cast<expr
*>(o2
);
1904 if (e1
->operation
!= e2
->operation
1905 || e1
->is_generic
!= e2
->is_generic
1906 || e1
->match_phi
!= e2
->match_phi
)
1908 if (e1
->operation
->kind
== id_base::FN
1909 /* For function calls also compare number of arguments. */
1910 && e1
->ops
.length () != e2
->ops
.length ())
1918 /* Compare two decision tree nodes N1 and N2 and return true if they
1922 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1924 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1930 if (n1
->type
== dt_node::DT_TRUE
)
1933 if (n1
->type
== dt_node::DT_OPERAND
)
1934 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1935 (as_a
<dt_operand
*> (n2
))->op
);
1936 else if (n1
->type
== dt_node::DT_MATCH
)
1937 return (((as_a
<dt_operand
*> (n1
))->match_dop
1938 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1939 && ((as_a
<dt_operand
*> (n1
))->value_match
1940 == (as_a
<dt_operand
*> (n2
))->value_match
));
1944 /* Search OPS for a decision tree node like P and return it if found. */
1947 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1949 /* We can merge adjacent DT_TRUE. */
1950 if (p
->type
== dt_node::DT_TRUE
1952 && ops
.last ()->type
== dt_node::DT_TRUE
)
1954 dt_operand
*true_node
= NULL
;
1955 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1957 /* But we can't merge across DT_TRUE nodes as they serve as
1958 pattern order barriers to make sure that patterns apply
1959 in order of appearance in case multiple matches are possible. */
1960 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1963 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1964 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1966 if (decision_tree::cmp_node (ops
[i
], p
))
1968 /* Unless we are processing the same pattern or the blocking
1969 pattern is before the one we are going to merge with. */
1971 && true_node
->for_id
!= current_id
1972 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1976 location_t p_loc
= 0;
1977 if (p
->type
== dt_node::DT_OPERAND
)
1978 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1979 location_t op_loc
= 0;
1980 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1981 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1982 location_t true_loc
= 0;
1983 true_loc
= true_node
->op
->location
;
1985 "failed to merge decision tree node");
1987 "with the following");
1988 warning_at (true_loc
,
1989 "because of the following which serves as ordering "
2000 /* Append N to the decision tree if it there is not already an existing
2004 dt_node::append_node (dt_node
*n
)
2008 kid
= decision_tree::find_node (kids
, n
);
2013 n
->level
= this->level
+ 1;
2018 /* Append OP to the decision tree. */
2021 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
2023 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
2024 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
2025 return append_node (n
);
2028 /* Append a DT_TRUE decision tree node. */
2031 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
2033 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
2034 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
2035 return append_node (n
);
2038 /* Append a DT_MATCH decision tree node. */
2041 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
2042 dt_node
*parent
, unsigned pos
)
2044 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
2045 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
2046 return append_node (n
);
2049 /* Append S to the decision tree. */
2052 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
2053 dt_operand
**indexes
)
2056 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
2057 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2058 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
2060 || s
->match
->location
!= s2
->s
->match
->location
))
2062 /* With a nested patters, it's hard to avoid these in order
2063 to keep match.pd rules relatively small. */
2064 warning_at (s
->match
->location
, "duplicate pattern");
2065 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
2066 print_operand (s
->match
, stderr
);
2067 fprintf (stderr
, "\n");
2069 return append_node (n
);
2072 /* Analyze the node and its children. */
2075 dt_node::analyze (sinfo_map_t
&map
)
2081 if (type
== DT_SIMPLIFY
)
2083 /* Populate the map of equivalent simplifies. */
2084 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
2086 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
2101 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2103 kids
[i
]->analyze (map
);
2104 num_leafs
+= kids
[i
]->num_leafs
;
2105 total_size
+= kids
[i
]->total_size
;
2106 max_level
= MAX (max_level
, kids
[i
]->max_level
);
2110 /* Insert O into the decision tree and return the decision tree node found
2114 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
2115 unsigned pos
, dt_node
*parent
)
2117 dt_node
*q
, *elm
= 0;
2119 if (capture
*c
= dyn_cast
<capture
*> (o
))
2121 unsigned capt_index
= c
->where
;
2123 if (indexes
[capt_index
] == 0)
2126 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
2129 q
= elm
= p
->append_true_op (o
, parent
, pos
);
2132 // get to the last capture
2133 for (operand
*what
= c
->what
;
2134 what
&& is_a
<capture
*> (what
);
2135 c
= as_a
<capture
*> (what
), what
= c
->what
)
2140 unsigned cc_index
= c
->where
;
2141 dt_operand
*match_op
= indexes
[cc_index
];
2143 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
2144 elm
= decision_tree::find_node (p
->kids
, &temp
);
2148 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
2149 match
.value_match
= c
->value_match
;
2150 elm
= decision_tree::find_node (p
->kids
, &match
);
2155 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
2156 elm
= decision_tree::find_node (p
->kids
, &temp
);
2160 gcc_assert (elm
->type
== dt_node::DT_TRUE
2161 || elm
->type
== dt_node::DT_OPERAND
2162 || elm
->type
== dt_node::DT_MATCH
);
2163 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2168 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2169 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2171 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2176 p
= p
->append_op (o
, parent
, pos
);
2179 if (expr
*e
= dyn_cast
<expr
*>(o
))
2181 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2182 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2188 /* Insert S into the decision tree. */
2191 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2194 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2195 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2196 p
->append_simplify (s
, pattern_no
, indexes
);
2199 /* Debug functions to dump the decision tree. */
2202 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2204 if (p
->type
== dt_node::DT_NODE
)
2205 fprintf (f
, "root");
2209 for (unsigned i
= 0; i
< indent
; i
++)
2212 if (p
->type
== dt_node::DT_OPERAND
)
2214 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2215 print_operand (dop
->op
, f
, true);
2217 else if (p
->type
== dt_node::DT_TRUE
)
2218 fprintf (f
, "true");
2219 else if (p
->type
== dt_node::DT_MATCH
)
2220 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2221 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2223 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2224 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2225 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2226 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2229 if (is_a
<dt_operand
*> (p
))
2230 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2233 fprintf (stderr
, " (%p, %p), %u, %u\n",
2234 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2236 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2237 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2241 decision_tree::print (FILE *f
)
2243 return decision_tree::print_node (root
, f
);
2247 /* For GENERIC we have to take care of wrapping multiple-used
2248 expressions with side-effects in save_expr and preserve side-effects
2249 of expressions with omit_one_operand. Analyze captures in
2250 match, result and with expressions and perform early-outs
2251 on the outermost match expression operands for cases we cannot
2257 capture_info (simplify
*s
, operand
*, bool);
2258 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2259 bool walk_result (operand
*o
, bool, operand
*);
2260 void walk_c_expr (c_expr
*);
2266 bool force_no_side_effects_p
;
2267 bool force_single_use
;
2268 bool cond_expr_cond_p
;
2269 unsigned long toplevel_msk
;
2270 unsigned match_use_count
;
2271 unsigned result_use_count
;
2276 auto_vec
<cinfo
> info
;
2277 unsigned long force_no_side_effects
;
2281 /* Analyze captures in S. */
2283 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2288 if (s
->kind
== simplify::MATCH
)
2290 force_no_side_effects
= -1;
2294 force_no_side_effects
= 0;
2295 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2296 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2297 info
[i
].same_as
= i
;
2299 e
= as_a
<expr
*> (s
->match
);
2300 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2301 walk_match (e
->ops
[i
], i
,
2302 (i
!= 0 && *e
->operation
== COND_EXPR
)
2303 || *e
->operation
== TRUTH_ANDIF_EXPR
2304 || *e
->operation
== TRUTH_ORIF_EXPR
,
2305 i
== 0 && *e
->operation
== COND_EXPR
);
2307 walk_result (s
->result
, false, result
);
2310 /* Analyze captures in the match expression piece O. */
2313 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2314 bool conditional_p
, bool cond_expr_cond_p
)
2316 if (capture
*c
= dyn_cast
<capture
*> (o
))
2318 unsigned where
= c
->where
;
2319 info
[where
].match_use_count
++;
2320 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2321 info
[where
].force_no_side_effects_p
|= conditional_p
;
2322 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2327 /* Recurse to exprs and captures. */
2328 if (is_a
<capture
*> (c
->what
)
2329 || is_a
<expr
*> (c
->what
))
2330 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2331 /* We need to look past multiple captures to find a captured
2332 expression as with conditional converts two captures
2333 can be collapsed onto the same expression. Also collect
2334 what captures capture the same thing. */
2335 while (c
->what
&& is_a
<capture
*> (c
->what
))
2337 c
= as_a
<capture
*> (c
->what
);
2338 if (info
[c
->where
].same_as
!= c
->where
2339 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2340 fatal_at (c
->location
, "cannot handle this collapsed capture");
2341 info
[c
->where
].same_as
= info
[where
].same_as
;
2343 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2346 && (e
= dyn_cast
<expr
*> (c
->what
)))
2348 /* Zero-operand expression captures like ADDR_EXPR@0 are
2349 similar as predicates -- if they are not mentioned in
2350 the result we have to force them to have no side-effects. */
2351 if (e
->ops
.length () != 0)
2352 info
[where
].expr_p
= true;
2353 info
[where
].force_single_use
|= e
->force_single_use
;
2356 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2358 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2360 bool cond_p
= conditional_p
;
2361 bool expr_cond_p
= false;
2362 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2364 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2365 || *e
->operation
== TRUTH_ORIF_EXPR
)
2368 && *e
->operation
== COND_EXPR
)
2370 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2373 else if (is_a
<predicate
*> (o
))
2375 /* Mark non-captured leafs toplevel arg for checking. */
2376 force_no_side_effects
|= 1 << toplevel_arg
;
2379 warning_at (o
->location
,
2380 "forcing no side-effects on possibly lost leaf");
2386 /* Analyze captures in the result expression piece O. Return true
2387 if RESULT was visited in one of the children. Only visit
2388 non-if/with children if they are rooted on RESULT. */
2391 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2393 if (capture
*c
= dyn_cast
<capture
*> (o
))
2395 unsigned where
= info
[c
->where
].same_as
;
2396 info
[where
].result_use_count
++;
2397 /* If we substitute an expression capture we don't know
2398 which captures this will end up using (well, we don't
2399 compute that). Force the uses to be side-effect free
2400 which means forcing the toplevels that reach the
2401 expression side-effect free. */
2402 if (info
[where
].expr_p
)
2403 force_no_side_effects
|= info
[where
].toplevel_msk
;
2404 /* Mark CSE capture uses as forced to have no side-effects. */
2406 && is_a
<expr
*> (c
->what
))
2408 info
[where
].cse_p
= true;
2409 walk_result (c
->what
, true, result
);
2412 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2414 id_base
*opr
= e
->operation
;
2415 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2416 opr
= uid
->substitutes
[0];
2417 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2419 bool cond_p
= conditional_p
;
2420 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2422 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2423 || *e
->operation
== TRUTH_ORIF_EXPR
)
2425 walk_result (e
->ops
[i
], cond_p
, result
);
2428 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2430 /* 'if' conditions should be all fine. */
2431 if (ie
->trueexpr
== result
)
2433 walk_result (ie
->trueexpr
, false, result
);
2436 if (ie
->falseexpr
== result
)
2438 walk_result (ie
->falseexpr
, false, result
);
2442 if (is_a
<if_expr
*> (ie
->trueexpr
)
2443 || is_a
<with_expr
*> (ie
->trueexpr
))
2444 res
|= walk_result (ie
->trueexpr
, false, result
);
2446 && (is_a
<if_expr
*> (ie
->falseexpr
)
2447 || is_a
<with_expr
*> (ie
->falseexpr
)))
2448 res
|= walk_result (ie
->falseexpr
, false, result
);
2451 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2453 bool res
= (we
->subexpr
== result
);
2455 || is_a
<if_expr
*> (we
->subexpr
)
2456 || is_a
<with_expr
*> (we
->subexpr
))
2457 res
|= walk_result (we
->subexpr
, false, result
);
2459 walk_c_expr (we
->with
);
2462 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2470 /* Look for captures in the C expr E. */
2473 capture_info::walk_c_expr (c_expr
*e
)
2475 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2476 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2477 really escape through. */
2478 unsigned p_depth
= 0;
2479 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2481 const cpp_token
*t
= &e
->code
[i
];
2482 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2484 if (t
->type
== CPP_NAME
2485 && (strcmp ((const char *)CPP_HASHNODE
2486 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2487 || strcmp ((const char *)CPP_HASHNODE
2488 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2489 || strcmp ((const char *)CPP_HASHNODE
2490 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2491 || ((id
= get_operator ((const char *)CPP_HASHNODE
2492 (t
->val
.node
.node
)->ident
.str
))
2493 && is_a
<predicate_id
*> (id
)))
2494 && n
->type
== CPP_OPEN_PAREN
)
2496 else if (t
->type
== CPP_CLOSE_PAREN
2499 else if (p_depth
== 0
2500 && t
->type
== CPP_ATSIGN
2501 && (n
->type
== CPP_NUMBER
2502 || n
->type
== CPP_NAME
)
2503 && !(n
->flags
& PREV_WHITE
))
2506 if (n
->type
== CPP_NUMBER
)
2507 id1
= (const char *)n
->val
.str
.text
;
2509 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2510 unsigned *where
= e
->capture_ids
->get(id1
);
2512 fatal_at (n
, "unknown capture id '%s'", id1
);
2513 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2516 warning_at (t
, "capture escapes");
2522 /* The current label failing the current matched pattern during
2524 static char *fail_label
;
2526 /* Code generation off the decision tree and the refered AST nodes. */
2529 is_conversion (id_base
*op
)
2531 return (*op
== CONVERT_EXPR
2533 || *op
== FLOAT_EXPR
2534 || *op
== FIX_TRUNC_EXPR
2535 || *op
== VIEW_CONVERT_EXPR
);
2538 /* Get the type to be used for generating operand POS of OP from the
2542 get_operand_type (id_base
*op
, unsigned pos
,
2543 const char *in_type
,
2544 const char *expr_type
,
2545 const char *other_oprnd_type
)
2547 /* Generally operands whose type does not match the type of the
2548 expression generated need to know their types but match and
2549 thus can fall back to 'other_oprnd_type'. */
2550 if (is_conversion (op
))
2551 return other_oprnd_type
;
2552 else if (*op
== REALPART_EXPR
2553 || *op
== IMAGPART_EXPR
)
2554 return other_oprnd_type
;
2555 else if (is_a
<operator_id
*> (op
)
2556 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2557 return other_oprnd_type
;
2558 else if (*op
== COND_EXPR
2560 return "boolean_type_node";
2561 else if (startswith (op
->id
, "CFN_COND_"))
2563 /* IFN_COND_* operands 1 and later by default have the same type
2564 as the result. The type of operand 0 needs to be specified
2566 if (pos
> 0 && expr_type
)
2568 else if (pos
> 0 && in_type
)
2575 /* Otherwise all types should match - choose one in order of
2582 return other_oprnd_type
;
2586 /* Generate transform code for an expression. */
2589 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2590 int depth
, const char *in_type
, capture_info
*cinfo
,
2591 dt_operand
**indexes
, int)
2593 id_base
*opr
= operation
;
2594 /* When we delay operator substituting during lowering of fors we
2595 make sure that for code-gen purposes the effects of each substitute
2596 are the same. Thus just look at that. */
2597 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2598 opr
= uid
->substitutes
[0];
2600 bool conversion_p
= is_conversion (opr
);
2601 const char *type
= expr_type
;
2604 /* If there was a type specification in the pattern use it. */
2606 else if (conversion_p
)
2607 /* For conversions we need to build the expression using the
2608 outer type passed in. */
2610 else if (*opr
== REALPART_EXPR
2611 || *opr
== IMAGPART_EXPR
)
2613 /* __real and __imag use the component type of its operand. */
2614 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2618 else if (is_a
<operator_id
*> (opr
)
2619 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2621 /* comparisons use boolean_type_node (or what gets in), but
2622 their operands need to figure out the types themselves. */
2627 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2632 else if (*opr
== COND_EXPR
2633 || *opr
== VEC_COND_EXPR
2634 || startswith (opr
->id
, "CFN_COND_"))
2636 /* Conditions are of the same type as their first alternative. */
2637 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2642 /* Other operations are of the same type as their first operand. */
2643 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2647 fatal_at (location
, "cannot determine type of operand");
2649 fprintf_indent (f
, indent
, "{\n");
2651 fprintf_indent (f
, indent
,
2652 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2654 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2655 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2658 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2660 = get_operand_type (opr
, i
, in_type
, expr_type
,
2661 i
== 0 ? NULL
: op0type
);
2662 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2664 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2667 const char *opr_name
;
2668 if (*operation
== CONVERT_EXPR
)
2669 opr_name
= "NOP_EXPR";
2671 opr_name
= operation
->id
;
2675 if (*opr
== CONVERT_EXPR
)
2677 fprintf_indent (f
, indent
,
2678 "if (%s != TREE_TYPE (_o%d[0])\n",
2680 fprintf_indent (f
, indent
,
2681 " && !useless_type_conversion_p (%s, TREE_TYPE "
2684 fprintf_indent (f
, indent
+ 2, "{\n");
2687 /* ??? Building a stmt can fail for various reasons here, seq being
2688 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2689 So if we fail here we should continue matching other patterns. */
2690 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2691 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2692 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2693 fprintf (f
, ", _o%d[%u]", depth
, i
);
2694 fprintf (f
, ");\n");
2695 fprintf_indent (f
, indent
, "tem_op.resimplify (%s, valueize);\n",
2696 !force_leaf
? "lseq" : "NULL");
2697 fprintf_indent (f
, indent
,
2698 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2699 !force_leaf
? "lseq" : "NULL");
2700 fprintf_indent (f
, indent
,
2701 "if (!_r%d) goto %s;\n",
2703 if (*opr
== CONVERT_EXPR
)
2706 fprintf_indent (f
, indent
, " }\n");
2707 fprintf_indent (f
, indent
, "else\n");
2708 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2713 if (*opr
== CONVERT_EXPR
)
2715 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2717 fprintf_indent (f
, indent
+ 2, "{\n");
2720 if (opr
->kind
== id_base::CODE
)
2721 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2722 depth
, ops
.length(), opr_name
, type
);
2724 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2725 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2726 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2727 fprintf (f
, ", _o%d[%u]", depth
, i
);
2728 fprintf (f
, ");\n");
2729 if (opr
->kind
!= id_base::CODE
)
2731 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2732 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2736 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2737 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2739 if (*opr
== CONVERT_EXPR
)
2741 fprintf_indent (f
, indent
- 2, "}\n");
2743 fprintf_indent (f
, indent
, "else\n");
2744 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2747 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2749 fprintf_indent (f
, indent
, "}\n");
2752 /* Generate code for a c_expr which is either the expression inside
2753 an if statement or a sequence of statements which computes a
2754 result to be stored to DEST. */
2757 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2758 bool, int, const char *, capture_info
*,
2761 if (dest
&& nr_stmts
== 1)
2762 fprintf_indent (f
, indent
, "%s = ", dest
);
2764 unsigned stmt_nr
= 1;
2766 for (unsigned i
= 0; i
< code
.length (); ++i
)
2768 const cpp_token
*token
= &code
[i
];
2770 /* We can't recover from all lexing losses but we can roughly restore line
2771 breaks from location info. */
2772 const line_map_ordinary
*map
;
2773 linemap_resolve_location (line_table
, token
->src_loc
,
2774 LRK_SPELLING_LOCATION
, &map
);
2775 expanded_location loc
= linemap_expand_location (line_table
, map
,
2777 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2779 prev_line
= loc
.line
;
2781 /* Replace captures for code-gen. */
2782 if (token
->type
== CPP_ATSIGN
)
2784 const cpp_token
*n
= &code
[i
+1];
2785 if ((n
->type
== CPP_NUMBER
2786 || n
->type
== CPP_NAME
)
2787 && !(n
->flags
& PREV_WHITE
))
2789 if (token
->flags
& PREV_WHITE
)
2792 if (n
->type
== CPP_NUMBER
)
2793 id
= (const char *)n
->val
.str
.text
;
2795 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2796 unsigned *cid
= capture_ids
->get (id
);
2798 fatal_at (token
, "unknown capture id");
2799 fprintf (f
, "captures[%u]", *cid
);
2805 if (token
->flags
& PREV_WHITE
)
2808 if (token
->type
== CPP_NAME
)
2810 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2812 for (j
= 0; j
< ids
.length (); ++j
)
2814 if (strcmp (id
, ids
[j
].id
) == 0)
2816 fprintf (f
, "%s", ids
[j
].oper
);
2820 if (j
< ids
.length ())
2824 /* Output the token as string. */
2825 char *tk
= (char *)cpp_token_as_text (r
, token
);
2828 if (token
->type
== CPP_SEMICOLON
)
2831 if (dest
&& stmt_nr
== nr_stmts
)
2832 fprintf_indent (f
, indent
, "%s = ", dest
);
2838 /* Generate transform code for a capture. */
2841 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2842 int depth
, const char *in_type
, capture_info
*cinfo
,
2843 dt_operand
**indexes
, int cond_handling
)
2845 if (what
&& is_a
<expr
*> (what
))
2847 if (indexes
[where
] == 0)
2850 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2851 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2856 /* If in GENERIC some capture is used multiple times, unshare it except
2857 when emitting the last use. */
2859 && cinfo
->info
.exists ()
2860 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2862 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2864 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2867 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2869 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2870 with substituting a capture of that. */
2872 && cond_handling
!= 0
2873 && cinfo
->info
[where
].cond_expr_cond_p
)
2875 /* If substituting into a cond_expr condition, unshare. */
2876 if (cond_handling
== 1)
2877 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2878 /* If substituting elsewhere we might need to decompose it. */
2879 else if (cond_handling
== 2)
2881 /* ??? Returning false here will also not allow any other patterns
2882 to match unless this generator was split out. */
2883 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2884 fprintf_indent (f
, indent
, " {\n");
2885 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2886 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2888 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2889 " TREE_OPERAND (%s, 1));\n",
2890 dest
, dest
, dest
, dest
, dest
);
2891 fprintf_indent (f
, indent
, " }\n");
2896 /* Return the name of the operand representing the decision tree node.
2897 Use NAME as space to generate it. */
2900 dt_operand::get_name (char *name
)
2903 sprintf (name
, "t");
2904 else if (parent
->level
== 1)
2905 sprintf (name
, "_p%u", pos
);
2906 else if (parent
->type
== dt_node::DT_MATCH
)
2907 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2909 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2913 /* Fill NAME with the operand name at position POS. */
2916 dt_operand::gen_opname (char *name
, unsigned pos
)
2919 sprintf (name
, "_p%u", pos
);
2921 sprintf (name
, "_q%u%u", level
, pos
);
2924 /* Generate matching code for the decision tree operand which is
2928 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2930 predicate
*p
= as_a
<predicate
*> (op
);
2932 if (p
->p
->matchers
.exists ())
2934 /* If this is a predicate generated from a pattern mangle its
2935 name and pass on the valueize hook. */
2937 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2940 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2943 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2944 fprintf_indent (f
, indent
+ 2, "{\n");
2948 /* Generate matching code for the decision tree operand which is
2952 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2954 char match_opname
[20];
2955 match_dop
->get_name (match_opname
);
2957 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2958 "|| operand_equal_p (%s, %s, 0))\n",
2959 opname
, match_opname
, opname
, opname
, match_opname
);
2961 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2962 "|| (operand_equal_p (%s, %s, 0) "
2963 "&& types_match (%s, %s)))\n",
2964 opname
, match_opname
, opname
, opname
, match_opname
,
2965 opname
, match_opname
);
2966 fprintf_indent (f
, indent
+ 2, "{\n");
2970 /* Generate GIMPLE matching code for the decision tree operand. */
2973 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2975 expr
*e
= static_cast<expr
*> (op
);
2976 id_base
*id
= e
->operation
;
2977 unsigned n_ops
= e
->ops
.length ();
2978 unsigned n_braces
= 0;
2980 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2981 id
= u
->substitutes
[0];
2983 for (unsigned i
= 0; i
< n_ops
; ++i
)
2985 char child_opname
[20];
2986 gen_opname (child_opname
, i
);
2988 if (id
->kind
== id_base::CODE
)
2991 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2992 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2994 /* ??? If this is a memory operation we can't (and should not)
2995 match this. The only sensible operand types are
2996 SSA names and invariants. */
3001 fprintf_indent (f
, indent
,
3002 "tree %s = TREE_OPERAND (%s, %i);\n",
3003 child_opname
, opname
, i
);
3006 fprintf_indent (f
, indent
,
3007 "tree %s = TREE_OPERAND "
3008 "(gimple_assign_rhs1 (_a%d), %i);\n",
3009 child_opname
, depth
, i
);
3010 fprintf_indent (f
, indent
,
3011 "if ((TREE_CODE (%s) == SSA_NAME\n",
3013 fprintf_indent (f
, indent
,
3014 " || is_gimple_min_invariant (%s)))\n",
3016 fprintf_indent (f
, indent
,
3020 fprintf_indent (f
, indent
,
3021 "%s = do_valueize (valueize, %s);\n",
3022 child_opname
, child_opname
);
3026 fprintf_indent (f
, indent
,
3027 "tree %s = gimple_assign_rhs%u (_a%d);\n",
3028 child_opname
, i
+ 1, depth
);
3031 fprintf_indent (f
, indent
,
3032 "tree %s = gimple_call_arg (_c%d, %u);\n",
3033 child_opname
, depth
, i
);
3034 fprintf_indent (f
, indent
,
3035 "%s = do_valueize (valueize, %s);\n",
3036 child_opname
, child_opname
);
3038 /* While the toplevel operands are canonicalized by the caller
3039 after valueizing operands of sub-expressions we have to
3040 re-canonicalize operand order. */
3041 int opno
= commutative_op (id
);
3044 char child_opname0
[20], child_opname1
[20];
3045 gen_opname (child_opname0
, opno
);
3046 gen_opname (child_opname1
, opno
+ 1);
3047 fprintf_indent (f
, indent
,
3048 "if (tree_swap_operands_p (%s, %s))\n",
3049 child_opname0
, child_opname1
);
3050 fprintf_indent (f
, indent
,
3051 " std::swap (%s, %s);\n",
3052 child_opname0
, child_opname1
);
3058 /* Generate GENERIC matching code for the decision tree operand. */
3061 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
3063 expr
*e
= static_cast<expr
*> (op
);
3064 id_base
*id
= e
->operation
;
3065 unsigned n_ops
= e
->ops
.length ();
3067 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
3068 id
= u
->substitutes
[0];
3070 for (unsigned i
= 0; i
< n_ops
; ++i
)
3072 char child_opname
[20];
3073 gen_opname (child_opname
, i
);
3075 if (id
->kind
== id_base::CODE
)
3076 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
3077 child_opname
, opname
, i
);
3079 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
3080 child_opname
, opname
, i
);
3086 /* Compare 2 fns or generic_fns vector entries for vector sorting.
3087 Same operation entries with different number of arguments should
3091 fns_cmp (const void *p1
, const void *p2
)
3093 dt_operand
*op1
= *(dt_operand
*const *) p1
;
3094 dt_operand
*op2
= *(dt_operand
*const *) p2
;
3095 expr
*e1
= as_a
<expr
*> (op1
->op
);
3096 expr
*e2
= as_a
<expr
*> (op2
->op
);
3097 id_base
*b1
= e1
->operation
;
3098 id_base
*b2
= e2
->operation
;
3099 if (b1
->hashval
< b2
->hashval
)
3101 if (b1
->hashval
> b2
->hashval
)
3103 return strcmp (b1
->id
, b2
->id
);
3106 /* Generate matching code for the children of the decision tree node. */
3109 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
3111 auto_vec
<dt_operand
*> gimple_exprs
;
3112 auto_vec
<dt_operand
*> generic_exprs
;
3113 auto_vec
<dt_operand
*> fns
;
3114 auto_vec
<dt_operand
*> generic_fns
;
3115 auto_vec
<dt_operand
*> preds
;
3116 auto_vec
<dt_node
*> others
;
3118 for (unsigned i
= 0; i
< kids
.length (); ++i
)
3120 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
3122 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
3123 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
3125 if (e
->ops
.length () == 0
3126 /* In GIMPLE a CONSTRUCTOR always appears in a
3127 separate definition. */
3128 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
3130 generic_exprs
.safe_push (op
);
3131 /* But ADDR_EXPRs can appear directly when invariant
3132 and in a separate definition when not. */
3133 if (gimple
&& *e
->operation
== ADDR_EXPR
)
3134 gimple_exprs
.safe_push (op
);
3136 else if (e
->operation
->kind
== id_base::FN
)
3141 generic_fns
.safe_push (op
);
3143 else if (e
->operation
->kind
== id_base::PREDICATE
)
3144 preds
.safe_push (op
);
3147 user_id
*u
= dyn_cast
<user_id
*> (e
->operation
);
3148 if (u
&& u
->substitutes
[0]->kind
== id_base::FN
)
3153 generic_fns
.safe_push (op
);
3157 if (gimple
&& !e
->is_generic
)
3158 gimple_exprs
.safe_push (op
);
3160 generic_exprs
.safe_push (op
);
3164 else if (op
->op
->type
== operand::OP_PREDICATE
)
3165 others
.safe_push (kids
[i
]);
3169 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
3170 others
.safe_push (kids
[i
]);
3171 else if (kids
[i
]->type
== dt_node::DT_MATCH
3172 || kids
[i
]->type
== dt_node::DT_TRUE
)
3174 /* A DT_TRUE operand serves as a barrier - generate code now
3175 for what we have collected sofar.
3176 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3177 dependent matches to get out-of-order. Generate code now
3178 for what we have collected sofar. */
3179 fns
.qsort (fns_cmp
);
3180 generic_fns
.qsort (fns_cmp
);
3181 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3182 fns
, generic_fns
, preds
, others
);
3183 /* And output the true operand itself. */
3184 kids
[i
]->gen (f
, indent
, gimple
, depth
);
3185 gimple_exprs
.truncate (0);
3186 generic_exprs
.truncate (0);
3188 generic_fns
.truncate (0);
3190 others
.truncate (0);
3196 /* Generate code for the remains. */
3197 fns
.qsort (fns_cmp
);
3198 generic_fns
.qsort (fns_cmp
);
3199 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3200 fns
, generic_fns
, preds
, others
);
3203 /* Generate matching code for the children of the decision tree node. */
3206 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
3207 const vec
<dt_operand
*> &gimple_exprs
,
3208 const vec
<dt_operand
*> &generic_exprs
,
3209 const vec
<dt_operand
*> &fns
,
3210 const vec
<dt_operand
*> &generic_fns
,
3211 const vec
<dt_operand
*> &preds
,
3212 const vec
<dt_node
*> &others
)
3215 char *kid_opname
= buf
;
3217 unsigned exprs_len
= gimple_exprs
.length ();
3218 unsigned gexprs_len
= generic_exprs
.length ();
3219 unsigned fns_len
= fns
.length ();
3220 unsigned gfns_len
= generic_fns
.length ();
3222 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3225 gimple_exprs
[0]->get_name (kid_opname
);
3227 fns
[0]->get_name (kid_opname
);
3229 generic_fns
[0]->get_name (kid_opname
);
3231 generic_exprs
[0]->get_name (kid_opname
);
3233 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3234 fprintf_indent (f
, indent
, " {\n");
3238 if (exprs_len
|| fns_len
)
3241 fprintf_indent (f
, indent
,
3242 "case SSA_NAME:\n");
3243 fprintf_indent (f
, indent
,
3244 " if (gimple *_d%d = get_def (valueize, %s))\n",
3246 fprintf_indent (f
, indent
,
3251 fprintf_indent (f
, indent
,
3252 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3254 fprintf_indent (f
, indent
,
3255 " switch (gimple_assign_rhs_code (_a%d))\n",
3258 fprintf_indent (f
, indent
, "{\n");
3259 bool cond_expr_p
= false;
3260 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3262 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3263 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3265 for (auto id
: u
->substitutes
)
3266 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3270 id_base
*op
= e
->operation
;
3271 cond_expr_p
|= (*op
== COND_EXPR
&& e
->match_phi
);
3272 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3273 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3275 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3277 fprintf_indent (f
, indent
, " {\n");
3278 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3279 fprintf_indent (f
, indent
, " break;\n");
3280 fprintf_indent (f
, indent
, " }\n");
3282 fprintf_indent (f
, indent
, "default:;\n");
3283 fprintf_indent (f
, indent
, "}\n");
3288 fprintf_indent (f
, indent
,
3289 "else if (gphi *_a%d = dyn_cast <gphi *> (_d%d))\n",
3292 fprintf_indent (f
, indent
, "{\n");
3295 for (unsigned i
= 0; i
< exprs_len
; i
++)
3297 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3298 if (*e
->operation
== COND_EXPR
&& e
->match_phi
)
3299 gimple_exprs
[i
]->gen_phi_on_cond (f
, indent
, depth
);
3303 fprintf_indent (f
, indent
, "}\n");
3310 fprintf_indent (f
, indent
,
3311 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3312 exprs_len
? "else " : "", depth
, depth
);
3313 fprintf_indent (f
, indent
,
3314 " switch (gimple_call_combined_fn (_c%d))\n",
3318 fprintf_indent (f
, indent
, "{\n");
3319 id_base
*last_op
= NULL
;
3320 for (unsigned i
= 0; i
< fns_len
; ++i
)
3322 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3323 if (e
->operation
!= last_op
)
3326 fprintf_indent (f
, indent
, " break;\n");
3327 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3328 for (auto id
: u
->substitutes
)
3329 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3331 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3333 last_op
= e
->operation
;
3334 /* We need to be defensive against bogus prototypes allowing
3335 calls with not enough arguments. */
3336 fprintf_indent (f
, indent
,
3337 " if (gimple_call_num_args (_c%d) == %d)\n",
3338 depth
, e
->ops
.length ());
3339 fprintf_indent (f
, indent
, " {\n");
3340 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3341 fprintf_indent (f
, indent
, " }\n");
3344 fprintf_indent (f
, indent
, " break;\n");
3345 fprintf_indent (f
, indent
, "default:;\n");
3346 fprintf_indent (f
, indent
, "}\n");
3352 fprintf_indent (f
, indent
, " }\n");
3353 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3354 here rather than in the next loop. */
3355 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3357 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3358 id_base
*op
= e
->operation
;
3359 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3361 fprintf_indent (f
, indent
+ 4, "{\n");
3362 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3363 fprintf_indent (f
, indent
+ 4, "}\n");
3367 fprintf_indent (f
, indent
, " break;\n");
3370 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3372 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3373 id_base
*op
= e
->operation
;
3374 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3375 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3376 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3377 /* Already handled above. */
3381 if (user_id
*u
= dyn_cast
<user_id
*> (op
))
3382 for (auto id
: u
->substitutes
)
3383 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3385 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3387 fprintf_indent (f
, indent
, " {\n");
3388 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3389 fprintf_indent (f
, indent
, " break;\n");
3390 fprintf_indent (f
, indent
, " }\n");
3395 fprintf_indent (f
, indent
,
3396 "case CALL_EXPR:\n");
3397 fprintf_indent (f
, indent
,
3398 " switch (get_call_combined_fn (%s))\n",
3400 fprintf_indent (f
, indent
,
3404 id_base
*last_op
= NULL
;
3405 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3407 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3408 gcc_assert (e
->operation
->kind
== id_base::FN
);
3410 if (e
->operation
!= last_op
)
3413 fprintf_indent (f
, indent
, " break;\n");
3414 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3416 last_op
= e
->operation
;
3417 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3418 " {\n", kid_opname
, e
->ops
.length ());
3419 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3420 fprintf_indent (f
, indent
, " }\n");
3422 fprintf_indent (f
, indent
, " break;\n");
3423 fprintf_indent (f
, indent
, "default:;\n");
3426 fprintf_indent (f
, indent
, " }\n");
3427 fprintf_indent (f
, indent
, " break;\n");
3430 /* Close switch (TREE_CODE ()). */
3431 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3434 fprintf_indent (f
, indent
, " default:;\n");
3435 fprintf_indent (f
, indent
, " }\n");
3438 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3440 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3441 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3442 preds
[i
]->get_name (kid_opname
);
3443 fprintf_indent (f
, indent
, "{\n");
3445 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3446 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3447 gimple
? "gimple" : "tree",
3448 p
->id
, kid_opname
, kid_opname
,
3449 gimple
? ", valueize" : "");
3450 fprintf_indent (f
, indent
, " {\n");
3451 for (int j
= 0; j
< p
->nargs
; ++j
)
3453 char child_opname
[20];
3454 preds
[i
]->gen_opname (child_opname
, j
);
3455 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3456 child_opname
, kid_opname
, j
);
3458 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3459 fprintf_indent (f
, indent
, " }\n");
3461 fprintf_indent (f
, indent
, "}\n");
3464 for (unsigned i
= 0; i
< others
.length (); ++i
)
3465 others
[i
]->gen (f
, indent
, gimple
, depth
);
3468 /* Generate matching code for the decision tree operand. */
3471 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3476 unsigned n_braces
= 0;
3478 if (type
== DT_OPERAND
)
3481 case operand::OP_PREDICATE
:
3482 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3485 case operand::OP_EXPR
:
3487 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3489 n_braces
= gen_generic_expr (f
, indent
, opname
);
3495 else if (type
== DT_TRUE
)
3497 else if (type
== DT_MATCH
)
3498 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3502 indent
+= 4 * n_braces
;
3503 gen_kids (f
, indent
, gimple
, depth
);
3505 for (unsigned i
= 0; i
< n_braces
; ++i
)
3510 fprintf_indent (f
, indent
, " }\n");
3514 /* Generate matching code for the phi when meet COND_EXPR. */
3517 dt_operand::gen_phi_on_cond (FILE *f
, int indent
, int depth
)
3519 fprintf_indent (f
, indent
,
3520 "basic_block _b%d = gimple_bb (_a%d);\n", depth
, depth
);
3522 fprintf_indent (f
, indent
, "if (gimple_phi_num_args (_a%d) == 2)\n", depth
);
3525 fprintf_indent (f
, indent
, "{\n");
3528 fprintf_indent (f
, indent
,
3529 "basic_block _pb_0_%d = EDGE_PRED (_b%d, 0)->src;\n", depth
, depth
);
3530 fprintf_indent (f
, indent
,
3531 "basic_block _pb_1_%d = EDGE_PRED (_b%d, 1)->src;\n", depth
, depth
);
3532 fprintf_indent (f
, indent
,
3533 "basic_block _db_%d = safe_dyn_cast <gcond *> (*gsi_last_bb (_pb_0_%d)) ? "
3534 "_pb_0_%d : _pb_1_%d;\n", depth
, depth
, depth
, depth
);
3535 fprintf_indent (f
, indent
,
3536 "basic_block _other_db_%d = safe_dyn_cast <gcond *> "
3537 "(*gsi_last_bb (_pb_0_%d)) ? _pb_1_%d : _pb_0_%d;\n",
3538 depth
, depth
, depth
, depth
);
3540 fprintf_indent (f
, indent
,
3541 "gcond *_ct_%d = safe_dyn_cast <gcond *> (*gsi_last_bb (_db_%d));\n",
3543 fprintf_indent (f
, indent
, "if (_ct_%d"
3544 " && EDGE_COUNT (_other_db_%d->preds) == 1\n", depth
, depth
);
3545 fprintf_indent (f
, indent
,
3546 " && EDGE_COUNT (_other_db_%d->succs) == 1\n", depth
);
3547 fprintf_indent (f
, indent
,
3548 " && EDGE_PRED (_other_db_%d, 0)->src == _db_%d)\n", depth
, depth
);
3551 fprintf_indent (f
, indent
, "{\n");
3554 fprintf_indent (f
, indent
,
3555 "tree _cond_lhs_%d = gimple_cond_lhs (_ct_%d);\n", depth
, depth
);
3556 fprintf_indent (f
, indent
,
3557 "tree _cond_rhs_%d = gimple_cond_rhs (_ct_%d);\n", depth
, depth
);
3562 gen_opname (opname_0
, 0);
3564 fprintf_indent (f
, indent
,
3565 "tree %s = build2 (gimple_cond_code (_ct_%d), "
3566 "boolean_type_node, _cond_lhs_%d, _cond_rhs_%d);\n",
3567 opname_0
, depth
, depth
, depth
);
3569 fprintf_indent (f
, indent
,
3570 "bool _arg_0_is_true_%d = gimple_phi_arg_edge (_a%d, 0)->flags"
3571 " & EDGE_TRUE_VALUE;\n", depth
, depth
);
3573 gen_opname (opname_1
, 1);
3574 fprintf_indent (f
, indent
,
3575 "tree %s = gimple_phi_arg_def (_a%d, _arg_0_is_true_%d ? 0 : 1);\n",
3576 opname_1
, depth
, depth
);
3578 gen_opname (opname_2
, 2);
3579 fprintf_indent (f
, indent
,
3580 "tree %s = gimple_phi_arg_def (_a%d, _arg_0_is_true_%d ? 1 : 0);\n",
3581 opname_2
, depth
, depth
);
3583 gen_kids (f
, indent
, true, depth
);
3586 fprintf_indent (f
, indent
, "}\n");
3590 fprintf_indent (f
, indent
, "}\n");
3594 /* Emit a logging call to the debug file to the file F, with the INDENT from
3595 either the RESULT location or the S's match location if RESULT is null. */
3597 emit_logging_call (FILE *f
, int indent
, class simplify
*s
, operand
*result
,
3600 fprintf_indent (f
, indent
, "if (UNLIKELY (debug_dump)) "
3601 "%s_dump_logs (", gimple
? "gimple" : "generic");
3602 output_line_directive (f
,
3603 result
? result
->location
: s
->match
->location
,
3605 fprintf (f
, ", __FILE__, __LINE__, %s);\n",
3606 s
->kind
== simplify::SIMPLIFY
? "true" : "false");
3609 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3610 step of a '(simplify ...)' or '(match ...)'. This handles everything
3611 that is not part of the decision tree (simplify->match).
3612 Main recursive worker. */
3615 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3619 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3621 fprintf_indent (f
, indent
, "{\n");
3623 output_line_directive (f
, w
->location
);
3624 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3625 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3627 fprintf_indent (f
, indent
, "}\n");
3630 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3632 output_line_directive (f
, ife
->location
);
3633 fprintf_indent (f
, indent
, "if (");
3634 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3636 fprintf_indent (f
, indent
+ 2, "{\n");
3638 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3640 fprintf_indent (f
, indent
+ 2, "}\n");
3643 fprintf_indent (f
, indent
, "else\n");
3644 fprintf_indent (f
, indent
+ 2, "{\n");
3646 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3648 fprintf_indent (f
, indent
+ 2, "}\n");
3654 static unsigned fail_label_cnt
;
3655 char local_fail_label
[256];
3656 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3657 fail_label
= local_fail_label
;
3658 bool needs_label
= false;
3660 /* Analyze captures and perform early-outs on the incoming arguments
3661 that cover cases we cannot handle. */
3662 capture_info
cinfo (s
, result
, gimple
);
3663 if (s
->kind
== simplify::SIMPLIFY
)
3667 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3668 if (cinfo
.force_no_side_effects
& (1 << i
))
3670 fprintf_indent (f
, indent
,
3671 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3675 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3676 "forcing toplevel operand to have no "
3679 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3680 if (cinfo
.info
[i
].cse_p
)
3682 else if (cinfo
.info
[i
].force_no_side_effects_p
3683 && (cinfo
.info
[i
].toplevel_msk
3684 & cinfo
.force_no_side_effects
) == 0)
3686 fprintf_indent (f
, indent
,
3687 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3688 "goto %s;\n", i
, fail_label
);
3691 warning_at (cinfo
.info
[i
].c
->location
,
3692 "forcing captured operand to have no "
3695 else if ((cinfo
.info
[i
].toplevel_msk
3696 & cinfo
.force_no_side_effects
) != 0)
3697 /* Mark capture as having no side-effects if we had to verify
3698 that via forced toplevel operand checks. */
3699 cinfo
.info
[i
].force_no_side_effects_p
= true;
3703 /* Force single-use restriction by only allowing simple
3704 results via setting seq to NULL. */
3705 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3706 bool first_p
= true;
3707 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3708 if (cinfo
.info
[i
].force_single_use
)
3712 fprintf_indent (f
, indent
, "if (lseq\n");
3713 fprintf_indent (f
, indent
, " && (");
3719 fprintf_indent (f
, indent
, " || ");
3721 fprintf (f
, "!single_use (captures[%d])", i
);
3725 fprintf (f
, "))\n");
3726 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3731 if (s
->kind
== simplify::SIMPLIFY
)
3733 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3737 fprintf_indent (f
, indent
, "{\n");
3741 /* If there is no result then this is a predicate implementation. */
3742 emit_logging_call (f
, indent
, s
, result
, gimple
);
3743 fprintf_indent (f
, indent
, "return true;\n");
3747 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3748 in outermost position). */
3749 if (result
->type
== operand::OP_EXPR
3750 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3751 result
= as_a
<expr
*> (result
)->ops
[0];
3752 if (result
->type
== operand::OP_EXPR
)
3754 expr
*e
= as_a
<expr
*> (result
);
3755 id_base
*opr
= e
->operation
;
3756 bool is_predicate
= false;
3757 /* When we delay operator substituting during lowering of fors we
3758 make sure that for code-gen purposes the effects of each substitute
3759 are the same. Thus just look at that. */
3760 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3761 opr
= uid
->substitutes
[0];
3762 else if (is_a
<predicate_id
*> (opr
))
3763 is_predicate
= true;
3765 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3766 *e
->operation
== CONVERT_EXPR
3767 ? "NOP_EXPR" : e
->operation
->id
,
3769 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3773 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3775 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3777 = get_operand_type (opr
, j
,
3778 "type", e
->expr_type
,
3780 : "TREE_TYPE (res_op->ops[0])");
3781 /* We need to expand GENERIC conditions we captured from
3782 COND_EXPRs and we need to unshare them when substituting
3784 int cond_handling
= 0;
3786 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3787 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3788 &cinfo
, indexes
, cond_handling
);
3791 /* Re-fold the toplevel result. It's basically an embedded
3792 gimple_build w/o actually building the stmt. */
3795 fprintf_indent (f
, indent
,
3796 "res_op->resimplify (%s, valueize);\n",
3797 !e
->force_leaf
? "lseq" : "NULL");
3800 fprintf_indent (f
, indent
,
3801 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3802 "goto %s;\n", fail_label
);
3807 else if (result
->type
== operand::OP_CAPTURE
3808 || result
->type
== operand::OP_C_EXPR
)
3810 fprintf_indent (f
, indent
, "tree tem;\n");
3811 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3813 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3814 if (is_a
<capture
*> (result
)
3815 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3817 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3818 with substituting a capture of that. */
3819 fprintf_indent (f
, indent
,
3820 "if (COMPARISON_CLASS_P (tem))\n");
3821 fprintf_indent (f
, indent
,
3823 fprintf_indent (f
, indent
,
3824 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3825 fprintf_indent (f
, indent
,
3826 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3827 fprintf_indent (f
, indent
,
3833 emit_logging_call (f
, indent
, s
, result
, gimple
);
3834 fprintf_indent (f
, indent
, "return true;\n");
3838 bool is_predicate
= false;
3839 if (result
->type
== operand::OP_EXPR
)
3841 expr
*e
= as_a
<expr
*> (result
);
3842 id_base
*opr
= e
->operation
;
3843 /* When we delay operator substituting during lowering of fors we
3844 make sure that for code-gen purposes the effects of each substitute
3845 are the same. Thus just look at that. */
3846 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3847 opr
= uid
->substitutes
[0];
3848 else if (is_a
<predicate_id
*> (opr
))
3849 is_predicate
= true;
3850 /* Search for captures used multiple times in the result expression
3851 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3852 original expression. */
3854 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3856 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3857 || cinfo
.info
[i
].cse_p
)
3859 if (cinfo
.info
[i
].result_use_count
3860 > cinfo
.info
[i
].match_use_count
)
3862 fprintf_indent (f
, indent
,
3863 "if (! tree_invariant_p (captures[%d])) "
3864 "goto %s;\n", i
, fail_label
);
3868 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3872 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3875 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3876 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3879 = get_operand_type (opr
, j
,
3880 "type", e
->expr_type
,
3882 ? NULL
: "TREE_TYPE (res_op0)");
3883 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3888 emit_logging_call (f
, indent
, s
, result
, gimple
);
3889 fprintf_indent (f
, indent
, "return true;\n");
3893 fprintf_indent (f
, indent
, "tree _r;\n");
3894 /* Re-fold the toplevel result. Use non_lvalue to
3895 build NON_LVALUE_EXPRs so they get properly
3896 ignored when in GIMPLE form. */
3897 if (*opr
== NON_LVALUE_EXPR
)
3898 fprintf_indent (f
, indent
,
3899 "_r = non_lvalue_loc (loc, res_op0);\n");
3902 if (is_a
<operator_id
*> (opr
))
3903 fprintf_indent (f
, indent
,
3904 "_r = fold_build%d_loc (loc, %s, type",
3906 *e
->operation
== CONVERT_EXPR
3907 ? "NOP_EXPR" : e
->operation
->id
);
3909 fprintf_indent (f
, indent
,
3910 "_r = maybe_build_call_expr_loc (loc, "
3911 "%s, type, %d", e
->operation
->id
,
3913 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3914 fprintf (f
, ", res_op%d", j
);
3915 fprintf (f
, ");\n");
3916 if (!is_a
<operator_id
*> (opr
))
3918 fprintf_indent (f
, indent
, "if (!_r)\n");
3919 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3925 else if (result
->type
== operand::OP_CAPTURE
3926 || result
->type
== operand::OP_C_EXPR
)
3929 fprintf_indent (f
, indent
, "tree _r;\n");
3930 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3937 /* Search for captures not used in the result expression and dependent
3938 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3939 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3941 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3943 if (!cinfo
.info
[i
].force_no_side_effects_p
3944 && !cinfo
.info
[i
].expr_p
3945 && cinfo
.info
[i
].result_use_count
== 0)
3947 fprintf_indent (f
, indent
,
3948 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3950 fprintf_indent (f
, indent
+ 2,
3951 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3952 "fold_ignored_result (captures[%d]), _r);\n",
3956 emit_logging_call (f
, indent
, s
, result
, gimple
);
3957 fprintf_indent (f
, indent
, "return _r;\n");
3961 fprintf_indent (f
, indent
, "}\n");
3963 fprintf (f
, "%s:;\n", fail_label
);
3967 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3968 step of a '(simplify ...)' or '(match ...)'. This handles everything
3969 that is not part of the decision tree (simplify->match). */
3972 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3974 fprintf_indent (f
, indent
, "{\n");
3976 output_line_directive (f
,
3977 s
->result
? s
->result
->location
: s
->match
->location
);
3978 if (s
->capture_max
>= 0)
3981 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3982 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3984 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3988 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3990 fprintf (f
, " };\n");
3993 /* If we have a split-out function for the actual transform, call it. */
3994 if (info
&& info
->fname
)
3998 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3999 "valueize, type, captures", info
->fname
);
4000 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
4001 if (s
->for_subst_vec
[i
].first
->used
)
4002 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
4003 fprintf (f
, "))\n");
4004 fprintf_indent (f
, indent
, " return true;\n");
4008 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
4010 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
4011 fprintf (f
, ", _p%d", i
);
4012 fprintf (f
, ", captures");
4013 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
4015 if (s
->for_subst_vec
[i
].first
->used
)
4016 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
4018 fprintf (f
, ");\n");
4019 fprintf_indent (f
, indent
, "if (res) return res;\n");
4024 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
4026 if (! s
->for_subst_vec
[i
].first
->used
)
4028 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
4029 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
4030 s
->for_subst_vec
[i
].first
->id
,
4031 s
->for_subst_vec
[i
].second
->id
);
4032 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
4033 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
4034 s
->for_subst_vec
[i
].first
->id
,
4035 s
->for_subst_vec
[i
].second
->id
);
4039 gen_1 (f
, indent
, gimple
, s
->result
);
4043 fprintf_indent (f
, indent
, "}\n");
4047 /* Hash function for finding equivalent transforms. */
4050 sinfo_hashmap_traits::hash (const key_type
&v
)
4052 /* Only bother to compare those originating from the same source pattern. */
4053 return v
->s
->result
->location
;
4056 /* Compare function for finding equivalent transforms. */
4059 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
4061 if (o1
->type
!= o2
->type
)
4066 case operand::OP_IF
:
4068 if_expr
*if1
= as_a
<if_expr
*> (o1
);
4069 if_expr
*if2
= as_a
<if_expr
*> (o2
);
4070 /* ??? Properly compare c-exprs. */
4071 if (if1
->cond
!= if2
->cond
)
4073 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
4075 if (if1
->falseexpr
!= if2
->falseexpr
4077 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
4081 case operand::OP_WITH
:
4083 with_expr
*with1
= as_a
<with_expr
*> (o1
);
4084 with_expr
*with2
= as_a
<with_expr
*> (o2
);
4085 if (with1
->with
!= with2
->with
)
4087 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
4092 /* We've hit a result. Time to compare capture-infos - this is required
4093 in addition to the conservative pointer-equivalency of the result IL. */
4094 capture_info
cinfo1 (s1
, o1
, true);
4095 capture_info
cinfo2 (s2
, o2
, true);
4097 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
4098 || cinfo1
.info
.length () != cinfo2
.info
.length ())
4101 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
4103 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
4104 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
4105 || (cinfo1
.info
[i
].force_no_side_effects_p
4106 != cinfo2
.info
[i
].force_no_side_effects_p
)
4107 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
4108 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
4109 /* toplevel_msk is an optimization */
4110 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
4111 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
4112 /* the pointer back to the capture is for diagnostics only */)
4116 /* ??? Deep-compare the actual result. */
4121 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
4122 const key_type
&candidate
)
4124 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
4128 /* Main entry to generate code for matching GIMPLE IL off the decision
4132 decision_tree::gen (vec
<FILE *> &files
, bool gimple
)
4138 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
4139 "a total number of %u nodes\n",
4140 gimple
? "GIMPLE" : "GENERIC",
4141 root
->num_leafs
, root
->max_level
, root
->total_size
);
4143 /* First split out the transform part of equal leafs. */
4146 for (sinfo_map_t::iterator iter
= si
.begin ();
4147 iter
!= si
.end (); ++iter
)
4149 sinfo
*s
= (*iter
).second
;
4150 /* Do not split out single uses. */
4157 fprintf (stderr
, "found %u uses of", s
->cnt
);
4158 output_line_directive (stderr
, s
->s
->s
->result
->location
);
4161 /* Cycle the file buffers. */
4162 FILE *f
= choose_output (files
);
4164 /* Generate a split out function with the leaf transform code. */
4165 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
4168 fp_decl (f
, "\nbool\n"
4169 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
4170 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4171 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
4176 fp_decl (f
, "\ntree\n"
4177 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
4178 (*iter
).second
->fname
);
4179 for (unsigned i
= 0;
4180 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
4181 fp_decl (f
, " tree ARG_UNUSED (_p%d),", i
);
4182 fp_decl (f
, " tree *ARG_UNUSED (captures)");
4184 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
4186 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
4188 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
4189 fp_decl (f
, ",\n const enum tree_code ARG_UNUSED (%s)",
4190 s
->s
->s
->for_subst_vec
[i
].first
->id
);
4191 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
4192 fp_decl (f
, ",\n const combined_fn ARG_UNUSED (%s)",
4193 s
->s
->s
->for_subst_vec
[i
].first
->id
);
4196 fp_decl_done (f
, ")");
4198 fprintf_indent (f
, 2, "const bool debug_dump = "
4199 "dump_file && (dump_flags & TDF_FOLDING);\n");
4200 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
4202 fprintf (f
, " return false;\n");
4204 fprintf (f
, " return NULL_TREE;\n");
4207 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
4209 for (unsigned n
= 1; n
<= 7; ++n
)
4211 bool has_kids_p
= false;
4213 /* First generate split-out functions. */
4214 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
4216 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
4217 expr
*e
= static_cast<expr
*>(dop
->op
);
4218 if (e
->ops
.length () != n
4219 /* Builtin simplifications are somewhat premature on
4220 GENERIC. The following drops patterns with outermost
4221 calls. It's easy to emit overloads for function code
4222 though if necessary. */
4224 && e
->operation
->kind
!= id_base::CODE
))
4228 /* Cycle the file buffers. */
4229 FILE *f
= choose_output (files
);
4232 fp_decl (f
, "\nbool\n"
4233 "gimple_simplify_%s (gimple_match_op *res_op,"
4234 " gimple_seq *seq,\n"
4235 " tree (*valueize)(tree) "
4236 "ATTRIBUTE_UNUSED,\n"
4237 " code_helper ARG_UNUSED (code), tree "
4238 "ARG_UNUSED (type)",
4241 fp_decl (f
, "\ntree\n"
4242 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
4243 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
4245 for (unsigned i
= 0; i
< n
; ++i
)
4246 fp_decl (f
, ", tree _p%d", i
);
4247 fp_decl_done (f
, ")");
4249 fprintf_indent (f
, 2, "const bool debug_dump = "
4250 "dump_file && (dump_flags & TDF_FOLDING);\n");
4251 dop
->gen_kids (f
, 2, gimple
, 0);
4253 fprintf (f
, " return false;\n");
4255 fprintf (f
, " return NULL_TREE;\n");
4260 /* If this main entry has no children, avoid generating code
4261 with compiler warnings, by generating a simple stub. */
4265 /* Cycle the file buffers. */
4266 FILE *f
= choose_output (files
);
4269 fp_decl (f
, "\nbool\n"
4270 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
4271 " tree (*)(tree), code_helper,\n"
4274 fp_decl (f
, "\ntree\n"
4275 "generic_simplify (location_t, enum tree_code,\n"
4277 for (unsigned i
= 0; i
< n
; ++i
)
4278 fp_decl (f
, ", tree");
4279 fp_decl_done (f
, ")");
4282 fprintf (f
, " return false;\n");
4284 fprintf (f
, " return NULL_TREE;\n");
4290 /* Cycle the file buffers. */
4291 FILE *f
= choose_output (files
);
4293 /* Then generate the main entry with the outermost switch and
4294 tail-calls to the split-out functions. */
4296 fp_decl (f
, "\nbool\n"
4297 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
4298 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
4299 " code_helper code, const tree type");
4301 fp_decl (f
, "\ntree\n"
4302 "generic_simplify (location_t loc, enum tree_code code, "
4303 "const tree type ATTRIBUTE_UNUSED");
4304 for (unsigned i
= 0; i
< n
; ++i
)
4305 fp_decl (f
, ", tree _p%d", i
);
4306 fp_decl_done (f
, ")");
4310 fprintf (f
, " switch (code.get_rep())\n"
4313 fprintf (f
, " switch (code)\n"
4315 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
4317 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
4318 expr
*e
= static_cast<expr
*>(dop
->op
);
4319 if (e
->ops
.length () != n
4320 /* Builtin simplifications are somewhat premature on
4321 GENERIC. The following drops patterns with outermost
4322 calls. It's easy to emit overloads for function code
4323 though if necessary. */
4325 && e
->operation
->kind
!= id_base::CODE
))
4328 if (*e
->operation
== CONVERT_EXPR
4329 || *e
->operation
== NOP_EXPR
)
4330 fprintf (f
, " CASE_CONVERT:\n");
4332 fprintf (f
, " case %s%s:\n",
4333 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
4336 fprintf (f
, " return gimple_simplify_%s (res_op, "
4337 "seq, valueize, code, type", e
->operation
->id
);
4339 fprintf (f
, " return generic_simplify_%s (loc, code, type",
4341 for (unsigned j
= 0; j
< n
; ++j
)
4342 fprintf (f
, ", _p%d", j
);
4343 fprintf (f
, ");\n");
4345 fprintf (f
, " default:;\n"
4349 fprintf (f
, " return false;\n");
4351 fprintf (f
, " return NULL_TREE;\n");
4356 /* Output code to implement the predicate P from the decision tree DT. */
4359 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
4361 fp_decl (f
, "\nbool\n%s%s (tree t%s%s)",
4362 gimple
? "gimple_" : "tree_", p
->id
,
4363 p
->nargs
> 0 ? ", tree *res_ops" : "",
4364 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4365 fp_decl_done (f
, "");
4367 /* Conveniently make 'type' available. */
4368 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
4369 fprintf_indent (f
, 2, "const bool debug_dump = "
4370 "dump_file && (dump_flags & TDF_FOLDING);\n");
4373 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4374 dt
.root
->gen_kids (f
, 2, gimple
, 0);
4376 fprintf_indent (f
, 2, "return false;\n"
4380 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4383 write_header (FILE *f
, const char *head
)
4385 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4386 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4387 fprintf (f
, "#pragma GCC diagnostic push\n");
4388 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-variable\"\n");
4389 fprintf (f
, "#pragma GCC diagnostic ignored \"-Wunused-function\"\n");
4391 /* Include the header instead of writing it awkwardly quoted here. */
4393 fprintf (f
, "\n#include \"%s\"\n", head
);
4403 parser (cpp_reader
*, bool gimple
);
4406 const cpp_token
*next ();
4407 const cpp_token
*peek (unsigned = 1);
4408 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4409 const cpp_token
*expect (enum cpp_ttype
);
4410 const cpp_token
*eat_token (enum cpp_ttype
);
4411 const char *get_string ();
4412 const char *get_ident ();
4413 const cpp_token
*eat_ident (const char *);
4414 const char *get_number ();
4416 unsigned get_internal_capture_id ();
4418 id_base
*parse_operation (unsigned char &);
4419 operand
*parse_capture (operand
*, bool);
4420 operand
*parse_expr ();
4421 c_expr
*parse_c_expr (cpp_ttype
);
4422 operand
*parse_op ();
4424 void record_operlist (location_t
, user_id
*);
4426 void parse_pattern ();
4427 operand
*parse_result (operand
*, predicate_id
*);
4428 void push_simplify (simplify::simplify_kind
,
4429 vec
<simplify
*>&, operand
*, operand
*);
4430 void parse_simplify (simplify::simplify_kind
,
4431 vec
<simplify
*>&, predicate_id
*, operand
*);
4432 void parse_for (location_t
);
4433 void parse_if (location_t
);
4434 void parse_predicates (location_t
);
4435 void parse_operator_list (location_t
);
4437 void finish_match_operand (operand
*);
4441 vec
<c_expr
*> active_ifs
;
4442 vec
<vec
<user_id
*> > active_fors
;
4443 hash_set
<user_id
*> *oper_lists_set
;
4444 vec
<user_id
*> oper_lists
;
4446 cid_map_t
*capture_ids
;
4450 vec
<simplify
*> simplifiers
;
4451 vec
<predicate_id
*> user_predicates
;
4452 bool parsing_match_operand
;
4455 /* Lexing helpers. */
4457 /* Read the next non-whitespace token from R. */
4462 const cpp_token
*token
;
4465 token
= cpp_get_token (r
);
4467 while (token
->type
== CPP_PADDING
);
4471 /* Peek at the next non-whitespace token from R. */
4474 parser::peek (unsigned num
)
4476 const cpp_token
*token
;
4480 token
= cpp_peek_token (r
, i
++);
4482 while (token
->type
== CPP_PADDING
4484 /* If we peek at EOF this is a fatal error as it leaves the
4485 cpp_reader in unusable state. Assume we really wanted a
4486 token and thus this EOF is unexpected. */
4487 if (token
->type
== CPP_EOF
)
4488 fatal_at (token
, "unexpected end of file");
4492 /* Peek at the next identifier token (or return NULL if the next
4493 token is not an identifier or equal to ID if supplied). */
4496 parser::peek_ident (const char *id
, unsigned num
)
4498 const cpp_token
*token
= peek (num
);
4499 if (token
->type
!= CPP_NAME
)
4505 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4506 if (strcmp (id
, t
) == 0)
4512 /* Read the next token from R and assert it is of type TK. */
4515 parser::expect (enum cpp_ttype tk
)
4517 const cpp_token
*token
= next ();
4518 if (token
->type
!= tk
)
4519 fatal_at (token
, "expected %s, got %s",
4520 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4525 /* Consume the next token from R and assert it is of type TK. */
4528 parser::eat_token (enum cpp_ttype tk
)
4533 /* Read the next token from R and assert it is of type CPP_STRING and
4534 return its value. */
4537 parser::get_string ()
4539 const cpp_token
*token
= expect (CPP_STRING
);
4540 return (const char *)token
->val
.str
.text
;
4543 /* Read the next token from R and assert it is of type CPP_NAME and
4544 return its value. */
4547 parser::get_ident ()
4549 const cpp_token
*token
= expect (CPP_NAME
);
4550 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4553 /* Eat an identifier token with value S from R. */
4556 parser::eat_ident (const char *s
)
4558 const cpp_token
*token
= peek ();
4559 const char *t
= get_ident ();
4560 if (strcmp (s
, t
) != 0)
4561 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4565 /* Read the next token from R and assert it is of type CPP_NUMBER and
4566 return its value. */
4569 parser::get_number ()
4571 const cpp_token
*token
= expect (CPP_NUMBER
);
4572 return (const char *)token
->val
.str
.text
;
4575 /* Return a capture ID that can be used internally. */
4578 parser::get_internal_capture_id ()
4580 unsigned newid
= capture_ids
->elements ();
4581 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4584 snprintf (id
, sizeof (id
), "__%u", newid
);
4585 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4587 fatal ("reserved capture id '%s' already used", id
);
4591 /* Record an operator-list use for transparent for handling. */
4594 parser::record_operlist (location_t loc
, user_id
*p
)
4596 if (!oper_lists_set
->add (p
))
4598 if (!oper_lists
.is_empty ()
4599 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4600 fatal_at (loc
, "User-defined operator list does not have the "
4601 "same number of entries as others used in the pattern");
4602 oper_lists
.safe_push (p
);
4606 /* Parse the operator ID, special-casing convert?, convert1? and
4610 parser::parse_operation (unsigned char &opt_grp
)
4612 const cpp_token
*id_tok
= peek ();
4613 char *alt_id
= NULL
;
4614 const char *id
= get_ident ();
4615 const cpp_token
*token
= peek ();
4617 if (token
->type
== CPP_QUERY
4618 && !(token
->flags
& PREV_WHITE
))
4620 if (!parsing_match_operand
)
4621 fatal_at (id_tok
, "conditional convert can only be used in "
4622 "match expression");
4623 if (ISDIGIT (id
[strlen (id
) - 1]))
4625 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4626 alt_id
= xstrdup (id
);
4627 alt_id
[strlen (id
) - 1] = '\0';
4629 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4633 eat_token (CPP_QUERY
);
4635 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4637 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4640 user_id
*p
= dyn_cast
<user_id
*> (op
);
4641 if (p
&& p
->is_oper_list
)
4643 if (active_fors
.length() == 0)
4644 record_operlist (id_tok
->src_loc
, p
);
4646 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4652 capture = '@'<number> */
4655 parser::parse_capture (operand
*op
, bool require_existing
)
4657 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4658 const cpp_token
*token
= peek ();
4659 const char *id
= NULL
;
4660 bool value_match
= false;
4661 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4662 if (token
->type
== CPP_ATSIGN
4663 && ! (token
->flags
& PREV_WHITE
)
4664 && parsing_match_operand
)
4666 eat_token (CPP_ATSIGN
);
4670 if (token
->type
== CPP_NUMBER
)
4672 else if (token
->type
== CPP_NAME
)
4675 fatal_at (token
, "expected number or identifier");
4676 unsigned next_id
= capture_ids
->elements ();
4678 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4681 if (require_existing
)
4682 fatal_at (src_loc
, "unknown capture id");
4685 return new capture (src_loc
, num
, op
, value_match
);
4688 /* Parse an expression
4689 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4692 parser::parse_expr ()
4694 const cpp_token
*token
= peek ();
4695 unsigned char opt_grp
;
4696 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4699 bool is_commutative
= false;
4700 bool force_capture
= false;
4701 const char *expr_type
= NULL
;
4703 if (!parsing_match_operand
4704 && token
->type
== CPP_NOT
4705 && !(token
->flags
& PREV_WHITE
))
4707 eat_token (CPP_NOT
);
4708 e
->force_leaf
= true;
4711 if (token
->type
== CPP_XOR
&& !(token
->flags
& PREV_WHITE
))
4713 if (!parsing_match_operand
)
4714 fatal_at (token
, "modifier '^' is only valid in a match expression");
4716 if (!(*e
->operation
== COND_EXPR
))
4717 fatal_at (token
, "modifier '^' can only act on operation COND_EXPR");
4719 eat_token (CPP_XOR
);
4720 e
->match_phi
= true;
4723 if (token
->type
== CPP_COLON
4724 && !(token
->flags
& PREV_WHITE
))
4726 eat_token (CPP_COLON
);
4728 if (token
->type
== CPP_NAME
4729 && !(token
->flags
& PREV_WHITE
))
4731 const char *s
= get_ident ();
4732 if (!parsing_match_operand
)
4742 = dyn_cast
<operator_id
*> (e
->operation
))
4744 if (!commutative_tree_code (o
->code
)
4745 && !comparison_code_p (o
->code
))
4746 fatal_at (token
, "operation is not commutative");
4748 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4749 for (unsigned i
= 0;
4750 i
< p
->substitutes
.length (); ++i
)
4753 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4755 if (!commutative_tree_code (q
->code
)
4756 && !comparison_code_p (q
->code
))
4757 fatal_at (token
, "operation %s is not "
4758 "commutative", q
->id
);
4761 is_commutative
= true;
4763 else if (*sp
== 'C')
4764 is_commutative
= true;
4765 else if (*sp
== 's')
4767 e
->force_single_use
= true;
4768 force_capture
= true;
4771 fatal_at (token
, "flag %c not recognized", *sp
);
4778 fatal_at (token
, "expected flag or type specifying identifier");
4781 if (token
->type
== CPP_ATSIGN
4782 && !(token
->flags
& PREV_WHITE
))
4783 op
= parse_capture (e
, false);
4784 else if (force_capture
)
4786 unsigned num
= get_internal_capture_id ();
4787 op
= new capture (token
->src_loc
, num
, e
, false);
4794 if (token
->type
== CPP_CLOSE_PAREN
)
4796 if (e
->operation
->nargs
!= -1
4797 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4798 fatal_at (token
, "'%s' expects %u operands, not %u",
4799 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4802 if (e
->ops
.length () == 2
4803 || commutative_op (e
->operation
) >= 0)
4804 e
->is_commutative
= true;
4806 fatal_at (token
, "only binary operators or functions with "
4807 "two arguments can be marked commutative, "
4808 "unless the operation is known to be inherently "
4811 e
->expr_type
= expr_type
;
4814 if (e
->ops
.length () != 1)
4815 fatal_at (token
, "only unary operations can be conditional");
4816 e
->opt_grp
= opt_grp
;
4820 else if (!(token
->flags
& PREV_WHITE
))
4821 fatal_at (token
, "expected expression operand");
4823 e
->append_op (parse_op ());
4828 /* Lex native C code delimited by START recording the preprocessing tokens
4829 for later processing.
4830 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4833 parser::parse_c_expr (cpp_ttype start
)
4835 const cpp_token
*token
;
4838 vec
<cpp_token
> code
= vNULL
;
4839 unsigned nr_stmts
= 0;
4840 location_t loc
= eat_token (start
)->src_loc
;
4841 if (start
== CPP_OPEN_PAREN
)
4842 end
= CPP_CLOSE_PAREN
;
4843 else if (start
== CPP_OPEN_BRACE
)
4844 end
= CPP_CLOSE_BRACE
;
4852 /* Count brace pairs to find the end of the expr to match. */
4853 if (token
->type
== start
)
4855 else if (token
->type
== end
4858 else if (token
->type
== CPP_EOF
)
4859 fatal_at (token
, "unexpected end of file");
4861 /* This is a lame way of counting the number of statements. */
4862 if (token
->type
== CPP_SEMICOLON
)
4865 /* If this is possibly a user-defined identifier mark it used. */
4866 if (token
->type
== CPP_NAME
)
4869 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4870 if (strcmp (str
, "return") == 0)
4871 fatal_at (token
, "return statement not allowed in C expression");
4872 /* Mark user operators corresponding to 'str' as used. */
4876 /* Record the token. */
4877 code
.safe_push (*token
);
4880 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4883 /* Parse an operand which is either an expression, a predicate or
4884 a standalone capture.
4885 op = predicate | expr | c_expr | capture */
4890 const cpp_token
*token
= peek ();
4891 class operand
*op
= NULL
;
4892 if (token
->type
== CPP_OPEN_PAREN
)
4894 eat_token (CPP_OPEN_PAREN
);
4896 eat_token (CPP_CLOSE_PAREN
);
4898 else if (token
->type
== CPP_OPEN_BRACE
)
4900 op
= parse_c_expr (CPP_OPEN_BRACE
);
4904 /* Remaining ops are either empty or predicates */
4905 if (token
->type
== CPP_NAME
)
4907 const char *id
= get_ident ();
4908 id_base
*opr
= get_operator (id
);
4910 fatal_at (token
, "expected predicate name");
4911 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4913 if (code1
->nargs
!= 0)
4914 fatal_at (token
, "using an operator with operands as predicate");
4915 /* Parse the zero-operand operator "predicates" as
4917 op
= new expr (opr
, token
->src_loc
);
4919 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4921 if (code2
->nargs
!= 0)
4922 fatal_at (token
, "using an operator with operands as predicate");
4923 /* Parse the zero-operand operator "predicates" as
4925 op
= new expr (opr
, token
->src_loc
);
4927 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4928 op
= new predicate (p
, token
->src_loc
);
4930 fatal_at (token
, "using an unsupported operator as predicate");
4931 if (!parsing_match_operand
)
4932 fatal_at (token
, "predicates are only allowed in match expression");
4934 if (token
->flags
& PREV_WHITE
)
4937 else if (token
->type
!= CPP_COLON
4938 && token
->type
!= CPP_ATSIGN
)
4939 fatal_at (token
, "expected expression or predicate");
4940 /* optionally followed by a capture and a predicate. */
4941 if (token
->type
== CPP_COLON
)
4942 fatal_at (token
, "not implemented: predicate on leaf operand");
4943 if (token
->type
== CPP_ATSIGN
)
4944 op
= parse_capture (op
, !parsing_match_operand
);
4950 /* Create a new simplify from the current parsing state and MATCH,
4951 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4954 parser::push_simplify (simplify::simplify_kind kind
,
4955 vec
<simplify
*>& simplifiers
,
4956 operand
*match
, operand
*result
)
4958 /* Build and push a temporary for operator list uses in expressions. */
4959 if (!oper_lists
.is_empty ())
4960 active_fors
.safe_push (oper_lists
);
4962 simplifiers
.safe_push
4963 (new simplify (kind
, last_id
++, match
, result
,
4964 active_fors
.copy (), capture_ids
));
4966 if (!oper_lists
.is_empty ())
4971 <result-op> = <op> | <if> | <with>
4972 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4973 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4977 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4979 const cpp_token
*token
= peek ();
4980 if (token
->type
!= CPP_OPEN_PAREN
)
4983 eat_token (CPP_OPEN_PAREN
);
4984 if (peek_ident ("if"))
4987 if_expr
*ife
= new if_expr (token
->src_loc
);
4988 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4989 if (peek ()->type
== CPP_OPEN_PAREN
)
4991 ife
->trueexpr
= parse_result (result
, matcher
);
4992 if (peek ()->type
== CPP_OPEN_PAREN
)
4993 ife
->falseexpr
= parse_result (result
, matcher
);
4994 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4995 ife
->falseexpr
= parse_op ();
4997 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4999 ife
->trueexpr
= parse_op ();
5000 if (peek ()->type
== CPP_OPEN_PAREN
)
5001 ife
->falseexpr
= parse_result (result
, matcher
);
5002 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
5003 ife
->falseexpr
= parse_op ();
5005 /* If this if is immediately closed then it contains a
5006 manual matcher or is part of a predicate definition. */
5007 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
5010 fatal_at (peek (), "manual transform not implemented");
5011 ife
->trueexpr
= result
;
5013 eat_token (CPP_CLOSE_PAREN
);
5016 else if (peek_ident ("with"))
5019 with_expr
*withe
= new with_expr (token
->src_loc
);
5020 /* Parse (with c-expr expr) as (if-with (true) expr). */
5021 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
5022 withe
->with
->nr_stmts
= 0;
5023 withe
->subexpr
= parse_result (result
, matcher
);
5024 eat_token (CPP_CLOSE_PAREN
);
5027 else if (peek_ident ("switch"))
5029 token
= eat_ident ("switch");
5030 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
5032 if_expr
*ife
= new if_expr (ifloc
);
5034 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
5035 if (peek ()->type
== CPP_OPEN_PAREN
)
5036 ife
->trueexpr
= parse_result (result
, matcher
);
5038 ife
->trueexpr
= parse_op ();
5039 eat_token (CPP_CLOSE_PAREN
);
5040 if (peek ()->type
!= CPP_OPEN_PAREN
5041 || !peek_ident ("if", 2))
5042 fatal_at (token
, "switch can be implemented with a single if");
5043 while (peek ()->type
!= CPP_CLOSE_PAREN
)
5045 if (peek ()->type
== CPP_OPEN_PAREN
)
5047 if (peek_ident ("if", 2))
5049 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
5051 ife
->falseexpr
= new if_expr (ifloc
);
5052 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
5053 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
5054 if (peek ()->type
== CPP_OPEN_PAREN
)
5055 ife
->trueexpr
= parse_result (result
, matcher
);
5057 ife
->trueexpr
= parse_op ();
5058 if (peek ()->type
== CPP_OPEN_PAREN
)
5059 fatal_at (peek(), "if inside switch cannot have an else");
5060 eat_token (CPP_CLOSE_PAREN
);
5064 /* switch default clause */
5065 ife
->falseexpr
= parse_result (result
, matcher
);
5066 eat_token (CPP_CLOSE_PAREN
);
5072 /* switch default clause */
5073 ife
->falseexpr
= parse_op ();
5074 eat_token (CPP_CLOSE_PAREN
);
5078 eat_token (CPP_CLOSE_PAREN
);
5083 operand
*op
= result
;
5086 eat_token (CPP_CLOSE_PAREN
);
5092 simplify = 'simplify' <expr> <result-op>
5094 match = 'match' <ident> <expr> [<result-op>]
5095 and fill SIMPLIFIERS with the results. */
5098 parser::parse_simplify (simplify::simplify_kind kind
,
5099 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
5102 /* Reset the capture map. */
5104 capture_ids
= new cid_map_t
;
5105 /* Reset oper_lists and set. */
5106 hash_set
<user_id
*> olist
;
5107 oper_lists_set
= &olist
;
5110 const cpp_token
*loc
= peek ();
5111 parsing_match_operand
= true;
5112 class operand
*match
= parse_op ();
5113 finish_match_operand (match
);
5114 parsing_match_operand
= false;
5115 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
5116 fatal_at (loc
, "outermost expression cannot be captured");
5117 if (match
->type
== operand::OP_EXPR
5118 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
5119 fatal_at (loc
, "outermost expression cannot be a predicate");
5121 /* Splice active_ifs onto result and continue parsing the
5123 if_expr
*active_if
= NULL
;
5124 for (int i
= active_ifs
.length (); i
> 0; --i
)
5126 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
5127 ifc
->cond
= active_ifs
[i
-1];
5128 ifc
->trueexpr
= active_if
;
5131 if_expr
*outermost_if
= active_if
;
5132 while (active_if
&& active_if
->trueexpr
)
5133 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
5135 const cpp_token
*token
= peek ();
5137 /* If this if is immediately closed then it is part of a predicate
5138 definition. Push it. */
5139 if (token
->type
== CPP_CLOSE_PAREN
)
5142 fatal_at (token
, "expected transform expression");
5145 active_if
->trueexpr
= result
;
5146 result
= outermost_if
;
5148 push_simplify (kind
, simplifiers
, match
, result
);
5152 operand
*tem
= parse_result (result
, matcher
);
5155 active_if
->trueexpr
= tem
;
5156 result
= outermost_if
;
5161 push_simplify (kind
, simplifiers
, match
, result
);
5164 /* Parsing of the outer control structures. */
5166 /* Parse a for expression
5167 for = '(' 'for' <subst>... <pattern> ')'
5168 subst = <ident> '(' <ident>... ')' */
5171 parser::parse_for (location_t
)
5173 auto_vec
<const cpp_token
*> user_id_tokens
;
5174 vec
<user_id
*> user_ids
= vNULL
;
5175 const cpp_token
*token
;
5176 unsigned min_n_opers
= 0, max_n_opers
= 0;
5181 if (token
->type
!= CPP_NAME
)
5184 /* Insert the user defined operators into the operator hash. */
5185 const char *id
= get_ident ();
5186 if (get_operator (id
, true) != NULL
)
5187 fatal_at (token
, "operator already defined");
5188 user_id
*op
= new user_id (id
);
5189 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
5191 user_ids
.safe_push (op
);
5192 user_id_tokens
.safe_push (token
);
5194 eat_token (CPP_OPEN_PAREN
);
5197 while ((token
= peek_ident ()) != 0)
5199 const char *oper
= get_ident ();
5200 id_base
*idb
= get_operator (oper
, true);
5202 fatal_at (token
, "no such operator '%s'", oper
);
5206 else if (idb
->nargs
== -1)
5208 else if (idb
->nargs
!= arity
)
5209 fatal_at (token
, "operator '%s' with arity %d does not match "
5210 "others with arity %d", oper
, idb
->nargs
, arity
);
5212 user_id
*p
= dyn_cast
<user_id
*> (idb
);
5215 if (p
->is_oper_list
)
5216 op
->substitutes
.safe_splice (p
->substitutes
);
5218 fatal_at (token
, "iterator cannot be used as operator-list");
5221 op
->substitutes
.safe_push (idb
);
5224 token
= expect (CPP_CLOSE_PAREN
);
5226 unsigned nsubstitutes
= op
->substitutes
.length ();
5227 if (nsubstitutes
== 0)
5228 fatal_at (token
, "A user-defined operator must have at least "
5229 "one substitution");
5230 if (max_n_opers
== 0)
5232 min_n_opers
= nsubstitutes
;
5233 max_n_opers
= nsubstitutes
;
5237 if (nsubstitutes
% min_n_opers
!= 0
5238 && min_n_opers
% nsubstitutes
!= 0)
5239 fatal_at (token
, "All user-defined identifiers must have a "
5240 "multiple number of operator substitutions of the "
5241 "smallest number of substitutions");
5242 if (nsubstitutes
< min_n_opers
)
5243 min_n_opers
= nsubstitutes
;
5244 else if (nsubstitutes
> max_n_opers
)
5245 max_n_opers
= nsubstitutes
;
5249 unsigned n_ids
= user_ids
.length ();
5251 fatal_at (token
, "for requires at least one user-defined identifier");
5254 if (token
->type
== CPP_CLOSE_PAREN
)
5255 fatal_at (token
, "no pattern defined in for");
5257 active_fors
.safe_push (user_ids
);
5261 if (token
->type
== CPP_CLOSE_PAREN
)
5267 /* Remove user-defined operators from the hash again. */
5268 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
5270 if (!user_ids
[i
]->used
)
5271 warning_at (user_id_tokens
[i
],
5272 "operator %s defined but not used", user_ids
[i
]->id
);
5273 operators
->remove_elt (user_ids
[i
]);
5277 /* Parse an identifier associated with a list of operators.
5278 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
5281 parser::parse_operator_list (location_t
)
5283 const cpp_token
*token
= peek ();
5284 const char *id
= get_ident ();
5286 if (get_operator (id
, true) != 0)
5287 fatal_at (token
, "operator %s already defined", id
);
5289 user_id
*op
= new user_id (id
, true);
5292 while ((token
= peek_ident ()) != 0)
5295 const char *oper
= get_ident ();
5296 id_base
*idb
= get_operator (oper
, true);
5299 fatal_at (token
, "no such operator '%s'", oper
);
5303 else if (idb
->nargs
== -1)
5305 else if (arity
!= idb
->nargs
)
5306 fatal_at (token
, "operator '%s' with arity %d does not match "
5307 "others with arity %d", oper
, idb
->nargs
, arity
);
5309 /* We allow composition of multiple operator lists. */
5310 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
5311 op
->substitutes
.safe_splice (p
->substitutes
);
5313 op
->substitutes
.safe_push (idb
);
5316 // Check that there is no junk after id-list
5318 if (token
->type
!= CPP_CLOSE_PAREN
)
5319 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
5321 if (op
->substitutes
.length () == 0)
5322 fatal_at (token
, "operator-list cannot be empty");
5325 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
5329 /* Parse an outer if expression.
5330 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
5333 parser::parse_if (location_t
)
5335 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
5337 const cpp_token
*token
= peek ();
5338 if (token
->type
== CPP_CLOSE_PAREN
)
5339 fatal_at (token
, "no pattern defined in if");
5341 active_ifs
.safe_push (ifexpr
);
5345 if (token
->type
== CPP_CLOSE_PAREN
)
5353 /* Parse a list of predefined predicate identifiers.
5354 preds = '(' 'define_predicates' <ident>... ')' */
5357 parser::parse_predicates (location_t
)
5361 const cpp_token
*token
= peek ();
5362 if (token
->type
!= CPP_NAME
)
5365 add_predicate (get_ident ());
5370 /* Parse outer control structures.
5371 pattern = <preds>|<for>|<if>|<simplify>|<match> */
5374 parser::parse_pattern ()
5376 /* All clauses start with '('. */
5377 eat_token (CPP_OPEN_PAREN
);
5378 const cpp_token
*token
= peek ();
5379 const char *id
= get_ident ();
5380 if (strcmp (id
, "simplify") == 0)
5382 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
5385 else if (strcmp (id
, "match") == 0)
5387 bool with_args
= false;
5388 location_t e_loc
= peek ()->src_loc
;
5389 if (peek ()->type
== CPP_OPEN_PAREN
)
5391 eat_token (CPP_OPEN_PAREN
);
5394 const char *name
= get_ident ();
5395 id_base
*id1
= get_operator (name
);
5399 p
= add_predicate (name
);
5400 user_predicates
.safe_push (p
);
5402 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5405 fatal_at (token
, "cannot add a match to a non-predicate ID");
5406 /* Parse (match <id> <arg>... (match-expr)) here. */
5410 capture_ids
= new cid_map_t
;
5411 e
= new expr (p
, e_loc
);
5412 while (peek ()->type
== CPP_ATSIGN
)
5413 e
->append_op (parse_capture (NULL
, false));
5414 eat_token (CPP_CLOSE_PAREN
);
5417 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5418 || (!e
&& p
->nargs
!= 0)))
5419 fatal_at (token
, "non-matching number of match operands");
5420 p
->nargs
= e
? e
->ops
.length () : 0;
5421 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5424 else if (strcmp (id
, "for") == 0)
5425 parse_for (token
->src_loc
);
5426 else if (strcmp (id
, "if") == 0)
5427 parse_if (token
->src_loc
);
5428 else if (strcmp (id
, "define_predicates") == 0)
5430 if (active_ifs
.length () > 0
5431 || active_fors
.length () > 0)
5432 fatal_at (token
, "define_predicates inside if or for is not supported");
5433 parse_predicates (token
->src_loc
);
5435 else if (strcmp (id
, "define_operator_list") == 0)
5437 if (active_ifs
.length () > 0
5438 || active_fors
.length () > 0)
5439 fatal_at (token
, "operator-list inside if or for is not supported");
5440 parse_operator_list (token
->src_loc
);
5443 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5444 active_ifs
.length () == 0 && active_fors
.length () == 0
5445 ? "'define_predicates', " : "");
5447 eat_token (CPP_CLOSE_PAREN
);
5450 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5454 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5459 if (capture
*c
= dyn_cast
<capture
*> (op
))
5461 cpts
[c
->where
].safe_push (c
);
5462 walk_captures (c
->what
, cpts
);
5464 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5465 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5466 walk_captures (e
->ops
[i
], cpts
);
5469 /* Finish up OP which is a match operand. */
5472 parser::finish_match_operand (operand
*op
)
5474 /* Look for matching captures, diagnose mis-uses of @@ and apply
5475 early lowering and distribution of value_match. */
5476 auto_vec
<vec
<capture
*> > cpts
;
5477 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5478 walk_captures (op
, cpts
);
5479 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5481 capture
*value_match
= NULL
;
5482 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5484 if (cpts
[i
][j
]->value_match
)
5487 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5488 value_match
= cpts
[i
][j
];
5491 if (cpts
[i
].length () == 1 && value_match
)
5492 fatal_at (value_match
->location
, "@@ without a matching capture");
5495 /* Duplicate prevailing capture with the existing ID, create
5496 a fake ID and rewrite all captures to use it. This turns
5497 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5498 value_match
->what
= new capture (value_match
->location
,
5500 value_match
->what
, false);
5501 /* Create a fake ID and rewrite all captures to use it. */
5502 unsigned newid
= get_internal_capture_id ();
5503 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5505 cpts
[i
][j
]->where
= newid
;
5506 cpts
[i
][j
]->value_match
= true;
5513 /* Main entry of the parser. Repeatedly parse outer control structures. */
5515 parser::parser (cpp_reader
*r_
, bool gimple_
)
5520 active_fors
= vNULL
;
5521 simplifiers
= vNULL
;
5522 oper_lists_set
= NULL
;
5525 user_predicates
= vNULL
;
5526 parsing_match_operand
= false;
5529 const cpp_token
*token
= next ();
5530 while (token
->type
!= CPP_EOF
)
5532 _cpp_backup_tokens (r
, 1);
5539 /* Helper for the linemap code. */
5542 round_alloc_size (size_t s
)
5548 /* Construct and display the help menu. */
5553 const char *usage
= "Usage:\n"
5554 " %s [--gimple|--generic] [-v[v]] <input>\n"
5555 " %s [options] [--include=FILE] --header=FILE <input> <output>...\n";
5556 fprintf (stderr
, usage
, progname
, progname
);
5559 /* Write out the correct include to the match-head fle containing the helper
5563 write_header_includes (bool gimple
, FILE *header_file
)
5566 fprintf (header_file
, "#include \"gimple-match-head.cc\"\n");
5568 fprintf (header_file
, "#include \"generic-match-head.cc\"\n");
5571 /* The genmatch generator program. It reads from a pattern description
5572 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5575 main (int argc
, char **argv
)
5579 progname
= "genmatch";
5582 char *s_header_file
= NULL
;
5583 char *s_include_file
= NULL
;
5584 auto_vec
<char *> files
;
5586 int last_file
= argc
- 1;
5587 for (int i
= argc
- 1; i
>= 1; --i
)
5589 if (strcmp (argv
[i
], "--gimple") == 0)
5591 else if (strcmp (argv
[i
], "--generic") == 0)
5593 else if (strncmp (argv
[i
], "--header=", 9) == 0)
5594 s_header_file
= &argv
[i
][9];
5595 else if (strncmp (argv
[i
], "--include=", 10) == 0)
5596 s_include_file
= &argv
[i
][10];
5597 else if (strcmp (argv
[i
], "-v") == 0)
5599 else if (strcmp (argv
[i
], "-vv") == 0)
5601 else if (strncmp (argv
[i
], "--", 2) != 0 && last_file
-- == i
)
5602 files
.safe_push (argv
[i
]);
5610 /* Validate if the combinations are valid. */
5611 if ((files
.length () > 1 && !s_header_file
) || files
.is_empty ())
5617 if (!s_include_file
)
5618 s_include_file
= s_header_file
;
5620 /* Input file is the last in the reverse list. */
5621 input
= files
.pop ();
5623 line_table
= XCNEW (class line_maps
);
5624 linemap_init (line_table
, 0);
5625 line_table
->m_reallocator
= xrealloc
;
5626 line_table
->m_round_alloc_size
= round_alloc_size
;
5628 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5629 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5630 cb
->diagnostic
= diagnostic_cb
;
5632 /* Add the build directory to the #include "" search path. */
5633 cpp_dir
*dir
= XCNEW (cpp_dir
);
5634 dir
->name
= getpwd ();
5636 dir
->name
= ASTRDUP (".");
5637 cpp_set_include_chains (r
, dir
, NULL
, false);
5639 if (!cpp_read_main_file (r
, input
))
5641 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5642 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5644 null_id
= new id_base (id_base::NULL_ID
, "null");
5646 /* Pre-seed operators. */
5647 operators
= new hash_table
<id_base
> (1024);
5648 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5649 add_operator (SYM, # SYM, # TYPE, NARGS);
5650 #define END_OF_BASE_TREE_CODES
5652 #undef END_OF_BASE_TREE_CODES
5655 /* Pre-seed builtin functions.
5656 ??? Cannot use N (name) as that is targetm.emultls.get_address
5657 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5658 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5659 add_function (ENUM, "CFN_" # ENUM);
5660 #include "builtins.def"
5662 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5663 add_function (IFN_##CODE, "CFN_" #CODE);
5664 #include "internal-fn.def"
5667 parser
p (r
, gimple
);
5669 /* Create file buffers. */
5670 int n_parts
= files
.is_empty () ? 1 : files
.length ();
5671 auto_vec
<FILE *> parts (n_parts
);
5672 if (files
.is_empty ())
5674 parts
.quick_push (stdout
);
5675 write_header (stdout
, s_include_file
);
5676 write_header_includes (gimple
, stdout
);
5677 write_header_declarations (gimple
, stdout
);
5681 for (char *s_file
: files
)
5683 parts
.quick_push (fopen (s_file
, "w"));
5684 write_header (parts
.last (), s_include_file
);
5687 header_file
= fopen (s_header_file
, "w");
5688 fprintf (header_file
, "#ifndef GCC_GIMPLE_MATCH_AUTO_H\n"
5689 "#define GCC_GIMPLE_MATCH_AUTO_H\n");
5690 write_header_includes (gimple
, header_file
);
5691 write_header_declarations (gimple
, header_file
);
5694 /* Go over all predicates defined with patterns and perform
5695 lowering and code generation. */
5696 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5698 predicate_id
*pred
= p
.user_predicates
[i
];
5699 lower (pred
->matchers
, gimple
);
5702 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5703 print_matches (pred
->matchers
[j
]);
5706 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5707 dt
.insert (pred
->matchers
[j
], j
);
5712 /* Cycle the file buffers. */
5713 FILE *f
= choose_output (parts
);
5715 write_predicate (f
, pred
, dt
, gimple
);
5718 /* Lower the main simplifiers and generate code for them. */
5719 lower (p
.simplifiers
, gimple
);
5722 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5723 print_matches (p
.simplifiers
[i
]);
5726 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5727 dt
.insert (p
.simplifiers
[i
], i
);
5732 dt
.gen (parts
, gimple
);
5734 define_dump_logs (gimple
, choose_output (parts
));
5736 for (FILE *f
: parts
)
5738 fprintf (f
, "#pragma GCC diagnostic pop\n");
5744 fprintf (header_file
, "\n#endif /* GCC_GIMPLE_MATCH_AUTO_H. */\n");
5745 fclose (header_file
);
5749 cpp_finish (r
, NULL
);