1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2022 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
187 output_line_directive (FILE *f
, location_t location
,
188 bool dumpfile
= false, bool fnargs
= false)
190 const line_map_ordinary
*map
;
191 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
192 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
195 /* When writing to a dumpfile only dump the filename. */
196 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
197 #if defined(DIR_SEPARATOR_2)
198 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
199 if (pos2
&& (!file
|| (pos2
> file
)))
208 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
210 fprintf (f
, "%s:%d", file
, loc
.line
);
213 /* Other gen programs really output line directives here, at least for
214 development it's right now more convenient to have line information
215 from the generated file. Still keep the directives as comment for now
216 to easily back-point to the meta-description. */
217 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
221 /* Pull in tree codes and builtin function codes from their
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
231 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
232 enum built_in_function
{
233 #include "builtins.def"
237 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239 #include "internal-fn.def"
244 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
245 CFN_##ENUM = int (ENUM),
246 #include "builtins.def"
248 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
249 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
250 #include "internal-fn.def"
255 #include "case-cfn-macros.h"
257 /* Return true if CODE represents a commutative tree code. Otherwise
260 commutative_tree_code (enum tree_code code
)
266 case MULT_HIGHPART_EXPR
:
281 case WIDEN_MULT_EXPR
:
282 case VEC_WIDEN_MULT_HI_EXPR
:
283 case VEC_WIDEN_MULT_LO_EXPR
:
284 case VEC_WIDEN_MULT_EVEN_EXPR
:
285 case VEC_WIDEN_MULT_ODD_EXPR
:
294 /* Return true if CODE represents a ternary tree code for which the
295 first two operands are commutative. Otherwise return false. */
297 commutative_ternary_tree_code (enum tree_code code
)
301 case WIDEN_MULT_PLUS_EXPR
:
302 case WIDEN_MULT_MINUS_EXPR
:
312 /* Return true if CODE is a comparison. */
315 comparison_code_p (enum tree_code code
)
342 /* Base class for all identifiers the parser knows. */
344 class id_base
: public nofree_ptr_hash
<id_base
>
347 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
349 id_base (id_kind
, const char *, int = -1);
355 /* hash_table support. */
356 static inline hashval_t
hash (const id_base
*);
357 static inline int equal (const id_base
*, const id_base
*);
361 id_base::hash (const id_base
*op
)
367 id_base::equal (const id_base
*op1
,
370 return (op1
->hashval
== op2
->hashval
371 && strcmp (op1
->id
, op2
->id
) == 0);
374 /* The special id "null", which matches nothing. */
375 static id_base
*null_id
;
377 /* Hashtable of known pattern operators. This is pre-seeded from
378 all known tree codes and all known builtin function ids. */
379 static hash_table
<id_base
> *operators
;
381 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
386 hashval
= htab_hash_string (id
);
389 /* Identifier that maps to a tree code. */
391 class operator_id
: public id_base
394 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
396 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
401 /* Identifier that maps to a builtin or internal function code. */
403 class fn_id
: public id_base
406 fn_id (enum built_in_function fn_
, const char *id_
)
407 : id_base (id_base::FN
, id_
), fn (fn_
) {}
408 fn_id (enum internal_fn fn_
, const char *id_
)
409 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
415 /* Identifier that maps to a user-defined predicate. */
417 class predicate_id
: public id_base
420 predicate_id (const char *id_
)
421 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
422 vec
<simplify
*> matchers
;
425 /* Identifier that maps to a operator defined by a 'for' directive. */
427 class user_id
: public id_base
430 user_id (const char *id_
, bool is_oper_list_
= false)
431 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
432 used (false), is_oper_list (is_oper_list_
) {}
433 vec
<id_base
*> substitutes
;
441 is_a_helper
<fn_id
*>::test (id_base
*id
)
443 return id
->kind
== id_base::FN
;
449 is_a_helper
<operator_id
*>::test (id_base
*id
)
451 return id
->kind
== id_base::CODE
;
457 is_a_helper
<predicate_id
*>::test (id_base
*id
)
459 return id
->kind
== id_base::PREDICATE
;
465 is_a_helper
<user_id
*>::test (id_base
*id
)
467 return id
->kind
== id_base::USER
;
470 /* If ID has a pair of consecutive, commutative operands, return the
471 index of the first, otherwise return -1. */
474 commutative_op (id_base
*id
)
476 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
478 if (commutative_tree_code (code
->code
)
479 || commutative_ternary_tree_code (code
->code
))
483 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
495 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
497 int res
= commutative_op (uid
->substitutes
[0]);
500 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
501 if (res
!= commutative_op (uid
->substitutes
[i
]))
508 /* Add a predicate identifier to the hash. */
510 static predicate_id
*
511 add_predicate (const char *id
)
513 predicate_id
*p
= new predicate_id (id
);
514 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
516 fatal ("duplicate id definition");
521 /* Add a tree code identifier to the hash. */
524 add_operator (enum tree_code code
, const char *id
,
525 const char *tcc
, unsigned nargs
)
527 if (strcmp (tcc
, "tcc_unary") != 0
528 && strcmp (tcc
, "tcc_binary") != 0
529 && strcmp (tcc
, "tcc_comparison") != 0
530 && strcmp (tcc
, "tcc_expression") != 0
531 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
532 && strcmp (tcc
, "tcc_reference") != 0
533 /* To have INTEGER_CST and friends as "predicate operators". */
534 && strcmp (tcc
, "tcc_constant") != 0
535 /* And allow CONSTRUCTOR for vector initializers. */
536 && !(code
== CONSTRUCTOR
)
537 /* Allow SSA_NAME as predicate operator. */
538 && !(code
== SSA_NAME
))
540 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
541 if (code
== ADDR_EXPR
)
543 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
544 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
546 fatal ("duplicate id definition");
550 /* Add a built-in or internal function identifier to the hash. ID is
551 the name of its CFN_* enumeration value. */
553 template <typename T
>
555 add_function (T code
, const char *id
)
557 fn_id
*fn
= new fn_id (code
, id
);
558 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
560 fatal ("duplicate id definition");
564 /* Helper for easy comparing ID with tree code CODE. */
567 operator==(id_base
&id
, enum tree_code code
)
569 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
570 return oid
->code
== code
;
574 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
577 get_operator (const char *id
, bool allow_null
= false)
579 if (allow_null
&& strcmp (id
, "null") == 0)
582 id_base
tem (id_base::CODE
, id
);
584 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
587 /* If this is a user-defined identifier track whether it was used. */
588 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
594 bool all_upper
= true;
595 bool all_lower
= true;
596 for (unsigned int i
= 0; id
[i
]; ++i
)
599 else if (ISLOWER (id
[i
]))
603 /* Try in caps with _EXPR appended. */
604 id2
= ACONCAT ((id
, "_EXPR", NULL
));
605 for (unsigned int i
= 0; id2
[i
]; ++i
)
606 id2
[i
] = TOUPPER (id2
[i
]);
608 else if (all_upper
&& startswith (id
, "IFN_"))
609 /* Try CFN_ instead of IFN_. */
610 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
611 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
612 /* Try prepending CFN_. */
613 id2
= ACONCAT (("CFN_", id
, NULL
));
617 new (&tem
) id_base (id_base::CODE
, id2
);
618 return operators
->find_with_hash (&tem
, tem
.hashval
);
621 /* Return the comparison operators that results if the operands are
622 swapped. This is safe for floating-point. */
625 swap_tree_comparison (operator_id
*p
)
637 return get_operator ("LT_EXPR");
639 return get_operator ("LE_EXPR");
641 return get_operator ("GT_EXPR");
643 return get_operator ("GE_EXPR");
645 return get_operator ("UNLT_EXPR");
647 return get_operator ("UNLE_EXPR");
649 return get_operator ("UNGT_EXPR");
651 return get_operator ("UNGE_EXPR");
657 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
660 /* The AST produced by parsing of the pattern definitions. */
665 /* The base class for operands. */
669 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
670 operand (enum op_type type_
, location_t loc_
)
671 : type (type_
), location (loc_
) {}
674 virtual void gen_transform (FILE *, int, const char *, bool, int,
675 const char *, capture_info
*,
678 { gcc_unreachable (); }
681 /* A predicate operand. Predicates are leafs in the AST. */
683 class predicate
: public operand
686 predicate (predicate_id
*p_
, location_t loc
)
687 : operand (OP_PREDICATE
, loc
), p (p_
) {}
691 /* An operand that constitutes an expression. Expressions include
692 function calls and user-defined predicate invocations. */
694 class expr
: public operand
697 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
698 : operand (OP_EXPR
, loc
), operation (operation_
),
699 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
700 is_generic (false), force_single_use (false), force_leaf (false),
703 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
704 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
705 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
706 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
707 void append_op (operand
*op
) { ops
.safe_push (op
); }
708 /* The operator and its operands. */
711 /* An explicitely specified type - used exclusively for conversions. */
712 const char *expr_type
;
713 /* Whether the operation is to be applied commutatively. This is
714 later lowered to two separate patterns. */
716 /* Whether the expression is expected to be in GENERIC form. */
718 /* Whether pushing any stmt to the sequence should be conditional
719 on this expression having a single-use. */
720 bool force_single_use
;
721 /* Whether in the result expression this should be a leaf node
722 with any children simplified down to simple operands. */
724 /* If non-zero, the group for optional handling. */
725 unsigned char opt_grp
;
726 void gen_transform (FILE *f
, int, const char *, bool, int,
727 const char *, capture_info
*,
728 dt_operand
** = 0, int = 0) override
;
731 /* An operator that is represented by native C code. This is always
732 a leaf operand in the AST. This class is also used to represent
733 the code to be generated for 'if' and 'with' expressions. */
735 class c_expr
: public operand
738 /* A mapping of an identifier and its replacement. Used to apply
744 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
747 c_expr (cpp_reader
*r_
, location_t loc
,
748 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
749 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
750 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
751 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
752 /* cpplib tokens and state to transform this back to source. */
755 cid_map_t
*capture_ids
;
756 /* The number of statements parsed (well, the number of ';'s). */
758 /* The identifier replacement vector. */
760 void gen_transform (FILE *f
, int, const char *, bool, int,
761 const char *, capture_info
*,
762 dt_operand
** = 0, int = 0) final override
;
765 /* A wrapper around another operand that captures its value. */
767 class capture
: public operand
770 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
771 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
773 /* Identifier index for the value. */
775 /* Whether in a match of two operands the compare should be for
776 equal values rather than equal atoms (boils down to a type
779 /* The captured value. */
781 void gen_transform (FILE *f
, int, const char *, bool, int,
782 const char *, capture_info
*,
783 dt_operand
** = 0, int = 0) final override
;
788 class if_expr
: public operand
791 if_expr (location_t loc
)
792 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
798 /* with expression. */
800 class with_expr
: public operand
803 with_expr (location_t loc
)
804 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
812 is_a_helper
<capture
*>::test (operand
*op
)
814 return op
->type
== operand::OP_CAPTURE
;
820 is_a_helper
<predicate
*>::test (operand
*op
)
822 return op
->type
== operand::OP_PREDICATE
;
828 is_a_helper
<c_expr
*>::test (operand
*op
)
830 return op
->type
== operand::OP_C_EXPR
;
836 is_a_helper
<expr
*>::test (operand
*op
)
838 return op
->type
== operand::OP_EXPR
;
844 is_a_helper
<if_expr
*>::test (operand
*op
)
846 return op
->type
== operand::OP_IF
;
852 is_a_helper
<with_expr
*>::test (operand
*op
)
854 return op
->type
== operand::OP_WITH
;
857 /* The main class of a pattern and its transform. This is used to
858 represent both (simplify ...) and (match ...) kinds. The AST
859 duplicates all outer 'if' and 'for' expressions here so each
860 simplify can exist in isolation. */
865 enum simplify_kind
{ SIMPLIFY
, MATCH
};
867 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
868 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
869 cid_map_t
*capture_ids_
)
870 : kind (kind_
), id (id_
), match (match_
), result (result_
),
871 for_vec (for_vec_
), for_subst_vec (vNULL
),
872 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
875 /* ID. This is kept to easily associate related simplifies expanded
876 from the same original one. */
878 /* The expression that is matched against the GENERIC or GIMPLE IL. */
880 /* For a (simplify ...) an expression with ifs and withs with the expression
881 produced when the pattern applies in the leafs.
882 For a (match ...) the leafs are either empty if it is a simple predicate
883 or the single expression specifying the matched operands. */
884 class operand
*result
;
885 /* Collected 'for' expression operators that have to be replaced
886 in the lowering phase. */
887 vec
<vec
<user_id
*> > for_vec
;
888 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
889 /* A map of capture identifiers to indexes. */
890 cid_map_t
*capture_ids
;
894 /* Debugging routines for dumping the AST. */
897 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
899 if (capture
*c
= dyn_cast
<capture
*> (o
))
901 if (c
->what
&& flattened
== false)
902 print_operand (c
->what
, f
, flattened
);
903 fprintf (f
, "@%u", c
->where
);
906 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
907 fprintf (f
, "%s", p
->p
->id
);
909 else if (is_a
<c_expr
*> (o
))
910 fprintf (f
, "c_expr");
912 else if (expr
*e
= dyn_cast
<expr
*> (o
))
914 if (e
->ops
.length () == 0)
915 fprintf (f
, "%s", e
->operation
->id
);
918 fprintf (f
, "(%s", e
->operation
->id
);
920 if (flattened
== false)
922 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
925 print_operand (e
->ops
[i
], f
, flattened
);
937 print_matches (class simplify
*s
, FILE *f
= stderr
)
939 fprintf (f
, "for expression: ");
940 print_operand (s
->match
, f
);
947 /* Lowering of commutative operators. */
950 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
951 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
953 if (n
== ops_vector
.length ())
955 vec
<operand
*> xv
= v
.copy ();
956 result
.safe_push (xv
);
960 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
962 v
[n
] = ops_vector
[n
][i
];
963 cartesian_product (ops_vector
, result
, v
, n
+ 1);
967 /* Lower OP to two operands in case it is marked as commutative. */
969 static vec
<operand
*>
970 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
972 vec
<operand
*> ret
= vNULL
;
974 if (capture
*c
= dyn_cast
<capture
*> (op
))
981 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
982 for (unsigned i
= 0; i
< v
.length (); ++i
)
984 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
991 expr
*e
= dyn_cast
<expr
*> (op
);
992 if (!e
|| e
->ops
.length () == 0)
998 vec
< vec
<operand
*> > ops_vector
= vNULL
;
999 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1000 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1002 auto_vec
< vec
<operand
*> > result
;
1003 auto_vec
<operand
*> v (e
->ops
.length ());
1004 v
.quick_grow_cleared (e
->ops
.length ());
1005 cartesian_product (ops_vector
, result
, v
, 0);
1008 for (unsigned i
= 0; i
< result
.length (); ++i
)
1010 expr
*ne
= new expr (e
);
1011 ne
->is_commutative
= false;
1012 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1013 ne
->append_op (result
[i
][j
]);
1017 if (!e
->is_commutative
)
1020 /* The operation is always binary if it isn't inherently commutative. */
1021 int natural_opno
= commutative_op (e
->operation
);
1022 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1023 for (unsigned i
= 0; i
< result
.length (); ++i
)
1025 expr
*ne
= new expr (e
);
1026 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1028 if (comparison_code_p (r
->code
))
1029 ne
->operation
= swap_tree_comparison (r
);
1031 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1033 bool found_compare
= false;
1034 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1035 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1037 if (comparison_code_p (q
->code
)
1038 && swap_tree_comparison (q
) != q
)
1040 found_compare
= true;
1046 user_id
*newop
= new user_id ("<internal>");
1047 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1049 id_base
*subst
= p
->substitutes
[j
];
1050 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1052 if (comparison_code_p (q
->code
))
1053 subst
= swap_tree_comparison (q
);
1055 newop
->substitutes
.safe_push (subst
);
1057 ne
->operation
= newop
;
1058 /* Search for 'p' inside the for vector and push 'newop'
1059 to the same level. */
1060 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1061 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1062 if (for_vec
[j
][k
] == p
)
1064 for_vec
[j
].safe_push (newop
);
1070 ne
->is_commutative
= false;
1071 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1073 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1074 ne
->append_op (result
[i
][old_j
]);
1082 /* Lower operations marked as commutative in the AST of S and push
1083 the resulting patterns to SIMPLIFIERS. */
1086 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1088 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1089 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1091 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1092 s
->for_vec
, s
->capture_ids
);
1093 simplifiers
.safe_push (ns
);
1097 /* Strip conditional operations using group GRP from O and its
1098 children if STRIP, else replace them with an unconditional operation. */
1101 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1103 if (capture
*c
= dyn_cast
<capture
*> (o
))
1106 return new capture (c
->location
, c
->where
,
1107 lower_opt (c
->what
, grp
, strip
),
1113 expr
*e
= dyn_cast
<expr
*> (o
);
1117 if (e
->opt_grp
== grp
)
1120 return lower_opt (e
->ops
[0], grp
, strip
);
1122 expr
*ne
= new expr (e
);
1124 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1128 expr
*ne
= new expr (e
);
1129 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1130 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1135 /* Determine whether O or its children uses the conditional operation
1139 has_opt (operand
*o
, unsigned char grp
)
1141 if (capture
*c
= dyn_cast
<capture
*> (o
))
1144 return has_opt (c
->what
, grp
);
1149 expr
*e
= dyn_cast
<expr
*> (o
);
1153 if (e
->opt_grp
== grp
)
1156 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1157 if (has_opt (e
->ops
[i
], grp
))
1163 /* Lower conditional convert operators in O, expanding it to a vector
1166 static vec
<operand
*>
1167 lower_opt (operand
*o
)
1169 vec
<operand
*> v1
= vNULL
, v2
;
1173 /* Conditional operations are lowered to a pattern with the
1174 operation and one without. All different conditional operation
1175 groups are lowered separately. */
1177 for (unsigned i
= 1; i
<= 10; ++i
)
1180 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1181 if (has_opt (v1
[j
], i
))
1183 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1184 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1190 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1191 v1
.safe_push (v2
[j
]);
1198 /* Lower conditional convert operators in the AST of S and push
1199 the resulting multiple patterns to SIMPLIFIERS. */
1202 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1204 vec
<operand
*> matchers
= lower_opt (s
->match
);
1205 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1207 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1208 s
->for_vec
, s
->capture_ids
);
1209 simplifiers
.safe_push (ns
);
1213 /* Lower the compare operand of COND_EXPRs to a
1214 GENERIC and a GIMPLE variant. */
1216 static vec
<operand
*>
1217 lower_cond (operand
*o
)
1219 vec
<operand
*> ro
= vNULL
;
1221 if (capture
*c
= dyn_cast
<capture
*> (o
))
1225 vec
<operand
*> lop
= vNULL
;
1226 lop
= lower_cond (c
->what
);
1228 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1229 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1235 expr
*e
= dyn_cast
<expr
*> (o
);
1236 if (!e
|| e
->ops
.length () == 0)
1242 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1243 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1244 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1246 auto_vec
< vec
<operand
*> > result
;
1247 auto_vec
<operand
*> v (e
->ops
.length ());
1248 v
.quick_grow_cleared (e
->ops
.length ());
1249 cartesian_product (ops_vector
, result
, v
, 0);
1251 for (unsigned i
= 0; i
< result
.length (); ++i
)
1253 expr
*ne
= new expr (e
);
1254 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1255 ne
->append_op (result
[i
][j
]);
1257 /* If this is a COND with a captured expression or an
1258 expression with two operands then also match a GENERIC
1259 form on the compare. */
1260 if (*e
->operation
== COND_EXPR
1261 && ((is_a
<capture
*> (e
->ops
[0])
1262 && as_a
<capture
*> (e
->ops
[0])->what
1263 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1265 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1266 || (is_a
<expr
*> (e
->ops
[0])
1267 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1270 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1271 ne
->append_op (result
[i
][j
]);
1272 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1274 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1275 expr
*cmp
= new expr (ocmp
);
1276 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1277 cmp
->append_op (ocmp
->ops
[j
]);
1278 cmp
->is_generic
= true;
1279 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1284 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1285 expr
*cmp
= new expr (ocmp
);
1286 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1287 cmp
->append_op (ocmp
->ops
[j
]);
1288 cmp
->is_generic
= true;
1298 /* Lower the compare operand of COND_EXPRs to a
1299 GENERIC and a GIMPLE variant. */
1302 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1304 vec
<operand
*> matchers
= lower_cond (s
->match
);
1305 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1307 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1308 s
->for_vec
, s
->capture_ids
);
1309 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1310 simplifiers
.safe_push (ns
);
1314 /* Return true if O refers to ID. */
1317 contains_id (operand
*o
, user_id
*id
)
1319 if (capture
*c
= dyn_cast
<capture
*> (o
))
1320 return c
->what
&& contains_id (c
->what
, id
);
1322 if (expr
*e
= dyn_cast
<expr
*> (o
))
1324 if (e
->operation
== id
)
1326 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1327 if (contains_id (e
->ops
[i
], id
))
1332 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1333 return (contains_id (w
->with
, id
)
1334 || contains_id (w
->subexpr
, id
));
1336 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1337 return (contains_id (ife
->cond
, id
)
1338 || contains_id (ife
->trueexpr
, id
)
1339 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1341 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1342 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1348 /* In AST operand O replace operator ID with operator WITH. */
1351 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1353 /* Deep-copy captures and expressions, replacing operations as
1355 if (capture
*c
= dyn_cast
<capture
*> (o
))
1359 return new capture (c
->location
, c
->where
,
1360 replace_id (c
->what
, id
, with
), c
->value_match
);
1362 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1364 expr
*ne
= new expr (e
);
1365 if (e
->operation
== id
)
1366 ne
->operation
= with
;
1367 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1368 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1371 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1373 with_expr
*nw
= new with_expr (w
->location
);
1374 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1375 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1378 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1380 if_expr
*nife
= new if_expr (ife
->location
);
1381 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1382 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1384 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1388 /* For c_expr we simply record a string replacement table which is
1389 applied at code-generation time. */
1390 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1392 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1393 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1394 return new c_expr (ce
->r
, ce
->location
,
1395 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1401 /* Return true if the binary operator OP is ok for delayed substitution
1402 during for lowering. */
1405 binary_ok (operator_id
*op
)
1412 case TRUNC_DIV_EXPR
:
1414 case FLOOR_DIV_EXPR
:
1415 case ROUND_DIV_EXPR
:
1416 case TRUNC_MOD_EXPR
:
1418 case FLOOR_MOD_EXPR
:
1419 case ROUND_MOD_EXPR
:
1421 case EXACT_DIV_EXPR
:
1433 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1436 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1438 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1439 unsigned worklist_start
= 0;
1440 auto_vec
<simplify
*> worklist
;
1441 worklist
.safe_push (sin
);
1443 /* Lower each recorded for separately, operating on the
1444 set of simplifiers created by the previous one.
1445 Lower inner-to-outer so inner for substitutes can refer
1446 to operators replaced by outer fors. */
1447 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1449 vec
<user_id
*>& ids
= for_vec
[fi
];
1450 unsigned n_ids
= ids
.length ();
1451 unsigned max_n_opers
= 0;
1452 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1453 for (unsigned i
= 0; i
< n_ids
; ++i
)
1455 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1456 max_n_opers
= ids
[i
]->substitutes
.length ();
1457 /* Require that all substitutes are of the same kind so that
1458 if we delay substitution to the result op code generation
1459 can look at the first substitute for deciding things like
1460 types of operands. */
1461 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1462 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1463 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1464 can_delay_subst
= false;
1465 else if (operator_id
*op
1466 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1469 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1470 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1471 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1473 /* Unfortunately we can't just allow all tcc_binary. */
1474 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1475 && strcmp (op0
->tcc
, "tcc_binary") == 0
1479 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1480 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1481 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1482 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1485 can_delay_subst
= false;
1487 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1490 can_delay_subst
= false;
1493 unsigned worklist_end
= worklist
.length ();
1494 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1496 simplify
*s
= worklist
[si
];
1497 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1499 operand
*match_op
= s
->match
;
1500 operand
*result_op
= s
->result
;
1501 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1503 for (unsigned i
= 0; i
< n_ids
; ++i
)
1505 user_id
*id
= ids
[i
];
1506 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1508 && (contains_id (match_op
, id
)
1509 || contains_id (result_op
, id
)))
1514 subst
.quick_push (std::make_pair (id
, oper
));
1515 match_op
= replace_id (match_op
, id
, oper
);
1517 && !can_delay_subst
)
1518 result_op
= replace_id (result_op
, id
, oper
);
1523 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1524 vNULL
, s
->capture_ids
);
1525 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1528 ns
->for_subst_vec
.safe_splice (subst
);
1530 worklist
.safe_push (ns
);
1533 worklist_start
= worklist_end
;
1536 /* Copy out the result from the last for lowering. */
1537 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1538 simplifiers
.safe_push (worklist
[i
]);
1541 /* Lower the AST for everything in SIMPLIFIERS. */
1544 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1546 auto_vec
<simplify
*> out_simplifiers
;
1547 for (auto s
: simplifiers
)
1548 lower_opt (s
, out_simplifiers
);
1550 simplifiers
.truncate (0);
1551 for (auto s
: out_simplifiers
)
1552 lower_commutative (s
, simplifiers
);
1554 /* Lower for needs to happen before lowering cond
1555 to support (for cnd (cond vec_cond)). This is
1556 safe as substitution delay does not happen for
1557 cond or vec_cond. */
1558 out_simplifiers
.truncate (0);
1559 for (auto s
: simplifiers
)
1560 lower_for (s
, out_simplifiers
);
1562 simplifiers
.truncate (0);
1564 for (auto s
: out_simplifiers
)
1565 lower_cond (s
, simplifiers
);
1567 simplifiers
.safe_splice (out_simplifiers
);
1573 /* The decision tree built for generating GIMPLE and GENERIC pattern
1574 matching code. It represents the 'match' expression of all
1575 simplifies and has those as its leafs. */
1579 /* A hash-map collecting semantically equivalent leafs in the decision
1580 tree for splitting out to separate functions. */
1589 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1592 static inline hashval_t
hash (const key_type
&);
1593 static inline bool equal_keys (const key_type
&, const key_type
&);
1594 template <typename T
> static inline void remove (T
&) {}
1597 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1600 /* Current simplifier ID we are processing during insertion into the
1602 static unsigned current_id
;
1604 /* Decision tree base class, used for DT_NODE. */
1609 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1614 vec
<dt_node
*> kids
;
1618 unsigned total_size
;
1621 dt_node (enum dt_type type_
, dt_node
*parent_
)
1622 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1624 dt_node
*append_node (dt_node
*);
1625 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1626 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1627 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1629 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1631 virtual void gen (FILE *, int, bool, int) {}
1633 void gen_kids (FILE *, int, bool, int);
1634 void gen_kids_1 (FILE *, int, bool, int,
1635 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1636 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1637 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1639 void analyze (sinfo_map_t
&);
1642 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1644 class dt_operand
: public dt_node
1648 dt_operand
*match_dop
;
1653 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1654 dt_operand
*parent_
, unsigned pos_
)
1655 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1656 pos (pos_
), value_match (false), for_id (current_id
) {}
1658 void gen (FILE *, int, bool, int) final override
;
1659 unsigned gen_predicate (FILE *, int, const char *, bool);
1660 unsigned gen_match_op (FILE *, int, const char *, bool);
1662 unsigned gen_gimple_expr (FILE *, int, int);
1663 unsigned gen_generic_expr (FILE *, int, const char *);
1665 char *get_name (char *);
1666 void gen_opname (char *, unsigned);
1669 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1671 class dt_simplify
: public dt_node
1675 unsigned pattern_no
;
1676 dt_operand
**indexes
;
1679 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1680 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1681 indexes (indexes_
), info (NULL
) {}
1683 void gen_1 (FILE *, int, bool, operand
*);
1684 void gen (FILE *f
, int, bool, int) final override
;
1690 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1692 return (n
->type
== dt_node::DT_OPERAND
1693 || n
->type
== dt_node::DT_MATCH
1694 || n
->type
== dt_node::DT_TRUE
);
1700 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1702 return n
->type
== dt_node::DT_SIMPLIFY
;
1707 /* A container for the actual decision tree. */
1714 void insert (class simplify
*, unsigned);
1715 void gen (FILE *f
, bool gimple
);
1716 void print (FILE *f
= stderr
);
1718 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1720 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1721 unsigned pos
= 0, dt_node
*parent
= 0);
1722 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1723 static bool cmp_node (dt_node
*, dt_node
*);
1724 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1727 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1730 cmp_operand (operand
*o1
, operand
*o2
)
1732 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1735 if (o1
->type
== operand::OP_PREDICATE
)
1737 predicate
*p1
= as_a
<predicate
*>(o1
);
1738 predicate
*p2
= as_a
<predicate
*>(o2
);
1739 return p1
->p
== p2
->p
;
1741 else if (o1
->type
== operand::OP_EXPR
)
1743 expr
*e1
= static_cast<expr
*>(o1
);
1744 expr
*e2
= static_cast<expr
*>(o2
);
1745 return (e1
->operation
== e2
->operation
1746 && e1
->is_generic
== e2
->is_generic
);
1752 /* Compare two decision tree nodes N1 and N2 and return true if they
1756 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1758 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1764 if (n1
->type
== dt_node::DT_TRUE
)
1767 if (n1
->type
== dt_node::DT_OPERAND
)
1768 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1769 (as_a
<dt_operand
*> (n2
))->op
);
1770 else if (n1
->type
== dt_node::DT_MATCH
)
1771 return (((as_a
<dt_operand
*> (n1
))->match_dop
1772 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1773 && ((as_a
<dt_operand
*> (n1
))->value_match
1774 == (as_a
<dt_operand
*> (n2
))->value_match
));
1778 /* Search OPS for a decision tree node like P and return it if found. */
1781 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1783 /* We can merge adjacent DT_TRUE. */
1784 if (p
->type
== dt_node::DT_TRUE
1786 && ops
.last ()->type
== dt_node::DT_TRUE
)
1788 dt_operand
*true_node
= NULL
;
1789 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1791 /* But we can't merge across DT_TRUE nodes as they serve as
1792 pattern order barriers to make sure that patterns apply
1793 in order of appearance in case multiple matches are possible. */
1794 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1797 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1798 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1800 if (decision_tree::cmp_node (ops
[i
], p
))
1802 /* Unless we are processing the same pattern or the blocking
1803 pattern is before the one we are going to merge with. */
1805 && true_node
->for_id
!= current_id
1806 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1810 location_t p_loc
= 0;
1811 if (p
->type
== dt_node::DT_OPERAND
)
1812 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1813 location_t op_loc
= 0;
1814 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1815 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1816 location_t true_loc
= 0;
1817 true_loc
= true_node
->op
->location
;
1819 "failed to merge decision tree node");
1821 "with the following");
1822 warning_at (true_loc
,
1823 "because of the following which serves as ordering "
1834 /* Append N to the decision tree if it there is not already an existing
1838 dt_node::append_node (dt_node
*n
)
1842 kid
= decision_tree::find_node (kids
, n
);
1847 n
->level
= this->level
+ 1;
1852 /* Append OP to the decision tree. */
1855 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1857 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1858 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1859 return append_node (n
);
1862 /* Append a DT_TRUE decision tree node. */
1865 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1867 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1868 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1869 return append_node (n
);
1872 /* Append a DT_MATCH decision tree node. */
1875 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1876 dt_node
*parent
, unsigned pos
)
1878 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1879 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1880 return append_node (n
);
1883 /* Append S to the decision tree. */
1886 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1887 dt_operand
**indexes
)
1890 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1891 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1892 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1894 || s
->match
->location
!= s2
->s
->match
->location
))
1896 /* With a nested patters, it's hard to avoid these in order
1897 to keep match.pd rules relatively small. */
1898 warning_at (s
->match
->location
, "duplicate pattern");
1899 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1900 print_operand (s
->match
, stderr
);
1901 fprintf (stderr
, "\n");
1903 return append_node (n
);
1906 /* Analyze the node and its children. */
1909 dt_node::analyze (sinfo_map_t
&map
)
1915 if (type
== DT_SIMPLIFY
)
1917 /* Populate the map of equivalent simplifies. */
1918 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1920 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1935 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1937 kids
[i
]->analyze (map
);
1938 num_leafs
+= kids
[i
]->num_leafs
;
1939 total_size
+= kids
[i
]->total_size
;
1940 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1944 /* Insert O into the decision tree and return the decision tree node found
1948 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1949 unsigned pos
, dt_node
*parent
)
1951 dt_node
*q
, *elm
= 0;
1953 if (capture
*c
= dyn_cast
<capture
*> (o
))
1955 unsigned capt_index
= c
->where
;
1957 if (indexes
[capt_index
] == 0)
1960 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1963 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1966 // get to the last capture
1967 for (operand
*what
= c
->what
;
1968 what
&& is_a
<capture
*> (what
);
1969 c
= as_a
<capture
*> (what
), what
= c
->what
)
1974 unsigned cc_index
= c
->where
;
1975 dt_operand
*match_op
= indexes
[cc_index
];
1977 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1978 elm
= decision_tree::find_node (p
->kids
, &temp
);
1982 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1983 match
.value_match
= c
->value_match
;
1984 elm
= decision_tree::find_node (p
->kids
, &match
);
1989 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1990 elm
= decision_tree::find_node (p
->kids
, &temp
);
1994 gcc_assert (elm
->type
== dt_node::DT_TRUE
1995 || elm
->type
== dt_node::DT_OPERAND
1996 || elm
->type
== dt_node::DT_MATCH
);
1997 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2002 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2003 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2005 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2010 p
= p
->append_op (o
, parent
, pos
);
2013 if (expr
*e
= dyn_cast
<expr
*>(o
))
2015 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2016 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2022 /* Insert S into the decision tree. */
2025 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2028 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2029 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2030 p
->append_simplify (s
, pattern_no
, indexes
);
2033 /* Debug functions to dump the decision tree. */
2036 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2038 if (p
->type
== dt_node::DT_NODE
)
2039 fprintf (f
, "root");
2043 for (unsigned i
= 0; i
< indent
; i
++)
2046 if (p
->type
== dt_node::DT_OPERAND
)
2048 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2049 print_operand (dop
->op
, f
, true);
2051 else if (p
->type
== dt_node::DT_TRUE
)
2052 fprintf (f
, "true");
2053 else if (p
->type
== dt_node::DT_MATCH
)
2054 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2055 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2057 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2058 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2059 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2060 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2063 if (is_a
<dt_operand
*> (p
))
2064 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2067 fprintf (stderr
, " (%p, %p), %u, %u\n",
2068 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2070 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2071 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2075 decision_tree::print (FILE *f
)
2077 return decision_tree::print_node (root
, f
);
2081 /* For GENERIC we have to take care of wrapping multiple-used
2082 expressions with side-effects in save_expr and preserve side-effects
2083 of expressions with omit_one_operand. Analyze captures in
2084 match, result and with expressions and perform early-outs
2085 on the outermost match expression operands for cases we cannot
2091 capture_info (simplify
*s
, operand
*, bool);
2092 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2093 bool walk_result (operand
*o
, bool, operand
*);
2094 void walk_c_expr (c_expr
*);
2100 bool force_no_side_effects_p
;
2101 bool force_single_use
;
2102 bool cond_expr_cond_p
;
2103 unsigned long toplevel_msk
;
2104 unsigned match_use_count
;
2105 unsigned result_use_count
;
2110 auto_vec
<cinfo
> info
;
2111 unsigned long force_no_side_effects
;
2115 /* Analyze captures in S. */
2117 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2122 if (s
->kind
== simplify::MATCH
)
2124 force_no_side_effects
= -1;
2128 force_no_side_effects
= 0;
2129 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2130 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2131 info
[i
].same_as
= i
;
2133 e
= as_a
<expr
*> (s
->match
);
2134 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2135 walk_match (e
->ops
[i
], i
,
2136 (i
!= 0 && *e
->operation
== COND_EXPR
)
2137 || *e
->operation
== TRUTH_ANDIF_EXPR
2138 || *e
->operation
== TRUTH_ORIF_EXPR
,
2139 i
== 0 && *e
->operation
== COND_EXPR
);
2141 walk_result (s
->result
, false, result
);
2144 /* Analyze captures in the match expression piece O. */
2147 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2148 bool conditional_p
, bool cond_expr_cond_p
)
2150 if (capture
*c
= dyn_cast
<capture
*> (o
))
2152 unsigned where
= c
->where
;
2153 info
[where
].match_use_count
++;
2154 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2155 info
[where
].force_no_side_effects_p
|= conditional_p
;
2156 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2161 /* Recurse to exprs and captures. */
2162 if (is_a
<capture
*> (c
->what
)
2163 || is_a
<expr
*> (c
->what
))
2164 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2165 /* We need to look past multiple captures to find a captured
2166 expression as with conditional converts two captures
2167 can be collapsed onto the same expression. Also collect
2168 what captures capture the same thing. */
2169 while (c
->what
&& is_a
<capture
*> (c
->what
))
2171 c
= as_a
<capture
*> (c
->what
);
2172 if (info
[c
->where
].same_as
!= c
->where
2173 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2174 fatal_at (c
->location
, "cannot handle this collapsed capture");
2175 info
[c
->where
].same_as
= info
[where
].same_as
;
2177 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2180 && (e
= dyn_cast
<expr
*> (c
->what
)))
2182 /* Zero-operand expression captures like ADDR_EXPR@0 are
2183 similar as predicates -- if they are not mentioned in
2184 the result we have to force them to have no side-effects. */
2185 if (e
->ops
.length () != 0)
2186 info
[where
].expr_p
= true;
2187 info
[where
].force_single_use
|= e
->force_single_use
;
2190 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2192 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2194 bool cond_p
= conditional_p
;
2195 bool expr_cond_p
= false;
2196 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2198 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2199 || *e
->operation
== TRUTH_ORIF_EXPR
)
2202 && *e
->operation
== COND_EXPR
)
2204 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2207 else if (is_a
<predicate
*> (o
))
2209 /* Mark non-captured leafs toplevel arg for checking. */
2210 force_no_side_effects
|= 1 << toplevel_arg
;
2213 warning_at (o
->location
,
2214 "forcing no side-effects on possibly lost leaf");
2220 /* Analyze captures in the result expression piece O. Return true
2221 if RESULT was visited in one of the children. Only visit
2222 non-if/with children if they are rooted on RESULT. */
2225 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2227 if (capture
*c
= dyn_cast
<capture
*> (o
))
2229 unsigned where
= info
[c
->where
].same_as
;
2230 info
[where
].result_use_count
++;
2231 /* If we substitute an expression capture we don't know
2232 which captures this will end up using (well, we don't
2233 compute that). Force the uses to be side-effect free
2234 which means forcing the toplevels that reach the
2235 expression side-effect free. */
2236 if (info
[where
].expr_p
)
2237 force_no_side_effects
|= info
[where
].toplevel_msk
;
2238 /* Mark CSE capture uses as forced to have no side-effects. */
2240 && is_a
<expr
*> (c
->what
))
2242 info
[where
].cse_p
= true;
2243 walk_result (c
->what
, true, result
);
2246 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2248 id_base
*opr
= e
->operation
;
2249 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2250 opr
= uid
->substitutes
[0];
2251 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2253 bool cond_p
= conditional_p
;
2254 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2256 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2257 || *e
->operation
== TRUTH_ORIF_EXPR
)
2259 walk_result (e
->ops
[i
], cond_p
, result
);
2262 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2264 /* 'if' conditions should be all fine. */
2265 if (ie
->trueexpr
== result
)
2267 walk_result (ie
->trueexpr
, false, result
);
2270 if (ie
->falseexpr
== result
)
2272 walk_result (ie
->falseexpr
, false, result
);
2276 if (is_a
<if_expr
*> (ie
->trueexpr
)
2277 || is_a
<with_expr
*> (ie
->trueexpr
))
2278 res
|= walk_result (ie
->trueexpr
, false, result
);
2280 && (is_a
<if_expr
*> (ie
->falseexpr
)
2281 || is_a
<with_expr
*> (ie
->falseexpr
)))
2282 res
|= walk_result (ie
->falseexpr
, false, result
);
2285 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2287 bool res
= (we
->subexpr
== result
);
2289 || is_a
<if_expr
*> (we
->subexpr
)
2290 || is_a
<with_expr
*> (we
->subexpr
))
2291 res
|= walk_result (we
->subexpr
, false, result
);
2293 walk_c_expr (we
->with
);
2296 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2304 /* Look for captures in the C expr E. */
2307 capture_info::walk_c_expr (c_expr
*e
)
2309 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2310 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2311 really escape through. */
2312 unsigned p_depth
= 0;
2313 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2315 const cpp_token
*t
= &e
->code
[i
];
2316 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2318 if (t
->type
== CPP_NAME
2319 && (strcmp ((const char *)CPP_HASHNODE
2320 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2321 || strcmp ((const char *)CPP_HASHNODE
2322 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2323 || strcmp ((const char *)CPP_HASHNODE
2324 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2325 || ((id
= get_operator ((const char *)CPP_HASHNODE
2326 (t
->val
.node
.node
)->ident
.str
))
2327 && is_a
<predicate_id
*> (id
)))
2328 && n
->type
== CPP_OPEN_PAREN
)
2330 else if (t
->type
== CPP_CLOSE_PAREN
2333 else if (p_depth
== 0
2334 && t
->type
== CPP_ATSIGN
2335 && (n
->type
== CPP_NUMBER
2336 || n
->type
== CPP_NAME
)
2337 && !(n
->flags
& PREV_WHITE
))
2340 if (n
->type
== CPP_NUMBER
)
2341 id1
= (const char *)n
->val
.str
.text
;
2343 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2344 unsigned *where
= e
->capture_ids
->get(id1
);
2346 fatal_at (n
, "unknown capture id '%s'", id1
);
2347 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2350 warning_at (t
, "capture escapes");
2356 /* The current label failing the current matched pattern during
2358 static char *fail_label
;
2360 /* Code generation off the decision tree and the refered AST nodes. */
2363 is_conversion (id_base
*op
)
2365 return (*op
== CONVERT_EXPR
2367 || *op
== FLOAT_EXPR
2368 || *op
== FIX_TRUNC_EXPR
2369 || *op
== VIEW_CONVERT_EXPR
);
2372 /* Get the type to be used for generating operand POS of OP from the
2376 get_operand_type (id_base
*op
, unsigned pos
,
2377 const char *in_type
,
2378 const char *expr_type
,
2379 const char *other_oprnd_type
)
2381 /* Generally operands whose type does not match the type of the
2382 expression generated need to know their types but match and
2383 thus can fall back to 'other_oprnd_type'. */
2384 if (is_conversion (op
))
2385 return other_oprnd_type
;
2386 else if (*op
== REALPART_EXPR
2387 || *op
== IMAGPART_EXPR
)
2388 return other_oprnd_type
;
2389 else if (is_a
<operator_id
*> (op
)
2390 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2391 return other_oprnd_type
;
2392 else if (*op
== COND_EXPR
2394 return "boolean_type_node";
2395 else if (startswith (op
->id
, "CFN_COND_"))
2397 /* IFN_COND_* operands 1 and later by default have the same type
2398 as the result. The type of operand 0 needs to be specified
2400 if (pos
> 0 && expr_type
)
2402 else if (pos
> 0 && in_type
)
2409 /* Otherwise all types should match - choose one in order of
2416 return other_oprnd_type
;
2420 /* Generate transform code for an expression. */
2423 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2424 int depth
, const char *in_type
, capture_info
*cinfo
,
2425 dt_operand
**indexes
, int)
2427 id_base
*opr
= operation
;
2428 /* When we delay operator substituting during lowering of fors we
2429 make sure that for code-gen purposes the effects of each substitute
2430 are the same. Thus just look at that. */
2431 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2432 opr
= uid
->substitutes
[0];
2434 bool conversion_p
= is_conversion (opr
);
2435 const char *type
= expr_type
;
2438 /* If there was a type specification in the pattern use it. */
2440 else if (conversion_p
)
2441 /* For conversions we need to build the expression using the
2442 outer type passed in. */
2444 else if (*opr
== REALPART_EXPR
2445 || *opr
== IMAGPART_EXPR
)
2447 /* __real and __imag use the component type of its operand. */
2448 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2452 else if (is_a
<operator_id
*> (opr
)
2453 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2455 /* comparisons use boolean_type_node (or what gets in), but
2456 their operands need to figure out the types themselves. */
2461 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2466 else if (*opr
== COND_EXPR
2467 || *opr
== VEC_COND_EXPR
2468 || startswith (opr
->id
, "CFN_COND_"))
2470 /* Conditions are of the same type as their first alternative. */
2471 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2476 /* Other operations are of the same type as their first operand. */
2477 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2481 fatal_at (location
, "cannot determine type of operand");
2483 fprintf_indent (f
, indent
, "{\n");
2485 fprintf_indent (f
, indent
,
2486 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2488 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2489 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2492 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2494 = get_operand_type (opr
, i
, in_type
, expr_type
,
2495 i
== 0 ? NULL
: op0type
);
2496 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2498 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2501 const char *opr_name
;
2502 if (*operation
== CONVERT_EXPR
)
2503 opr_name
= "NOP_EXPR";
2505 opr_name
= operation
->id
;
2509 if (*opr
== CONVERT_EXPR
)
2511 fprintf_indent (f
, indent
,
2512 "if (%s != TREE_TYPE (_o%d[0])\n",
2514 fprintf_indent (f
, indent
,
2515 " && !useless_type_conversion_p (%s, TREE_TYPE "
2518 fprintf_indent (f
, indent
+ 2, "{\n");
2521 /* ??? Building a stmt can fail for various reasons here, seq being
2522 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2523 So if we fail here we should continue matching other patterns. */
2524 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2525 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2526 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2527 fprintf (f
, ", _o%d[%u]", depth
, i
);
2528 fprintf (f
, ");\n");
2529 fprintf_indent (f
, indent
, "tem_op.resimplify (lseq, valueize);\n");
2530 fprintf_indent (f
, indent
,
2531 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2532 !force_leaf
? "lseq" : "NULL");
2533 fprintf_indent (f
, indent
,
2534 "if (!_r%d) goto %s;\n",
2536 if (*opr
== CONVERT_EXPR
)
2539 fprintf_indent (f
, indent
, " }\n");
2540 fprintf_indent (f
, indent
, "else\n");
2541 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2546 if (*opr
== CONVERT_EXPR
)
2548 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2552 if (opr
->kind
== id_base::CODE
)
2553 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2554 depth
, ops
.length(), opr_name
, type
);
2556 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2557 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2558 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2559 fprintf (f
, ", _o%d[%u]", depth
, i
);
2560 fprintf (f
, ");\n");
2561 if (opr
->kind
!= id_base::CODE
)
2563 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2564 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2568 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2569 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2571 if (*opr
== CONVERT_EXPR
)
2574 fprintf_indent (f
, indent
, "else\n");
2575 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2578 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2580 fprintf_indent (f
, indent
, "}\n");
2583 /* Generate code for a c_expr which is either the expression inside
2584 an if statement or a sequence of statements which computes a
2585 result to be stored to DEST. */
2588 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2589 bool, int, const char *, capture_info
*,
2592 if (dest
&& nr_stmts
== 1)
2593 fprintf_indent (f
, indent
, "%s = ", dest
);
2595 unsigned stmt_nr
= 1;
2597 for (unsigned i
= 0; i
< code
.length (); ++i
)
2599 const cpp_token
*token
= &code
[i
];
2601 /* We can't recover from all lexing losses but we can roughly restore line
2602 breaks from location info. */
2603 const line_map_ordinary
*map
;
2604 linemap_resolve_location (line_table
, token
->src_loc
,
2605 LRK_SPELLING_LOCATION
, &map
);
2606 expanded_location loc
= linemap_expand_location (line_table
, map
,
2608 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2610 prev_line
= loc
.line
;
2612 /* Replace captures for code-gen. */
2613 if (token
->type
== CPP_ATSIGN
)
2615 const cpp_token
*n
= &code
[i
+1];
2616 if ((n
->type
== CPP_NUMBER
2617 || n
->type
== CPP_NAME
)
2618 && !(n
->flags
& PREV_WHITE
))
2620 if (token
->flags
& PREV_WHITE
)
2623 if (n
->type
== CPP_NUMBER
)
2624 id
= (const char *)n
->val
.str
.text
;
2626 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2627 unsigned *cid
= capture_ids
->get (id
);
2629 fatal_at (token
, "unknown capture id");
2630 fprintf (f
, "captures[%u]", *cid
);
2636 if (token
->flags
& PREV_WHITE
)
2639 if (token
->type
== CPP_NAME
)
2641 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2643 for (j
= 0; j
< ids
.length (); ++j
)
2645 if (strcmp (id
, ids
[j
].id
) == 0)
2647 fprintf (f
, "%s", ids
[j
].oper
);
2651 if (j
< ids
.length ())
2655 /* Output the token as string. */
2656 char *tk
= (char *)cpp_token_as_text (r
, token
);
2659 if (token
->type
== CPP_SEMICOLON
)
2662 if (dest
&& stmt_nr
== nr_stmts
)
2663 fprintf_indent (f
, indent
, "%s = ", dest
);
2669 /* Generate transform code for a capture. */
2672 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2673 int depth
, const char *in_type
, capture_info
*cinfo
,
2674 dt_operand
**indexes
, int cond_handling
)
2676 if (what
&& is_a
<expr
*> (what
))
2678 if (indexes
[where
] == 0)
2681 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2682 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2687 /* If in GENERIC some capture is used multiple times, unshare it except
2688 when emitting the last use. */
2690 && cinfo
->info
.exists ()
2691 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2693 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2695 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2698 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2700 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2701 with substituting a capture of that. */
2703 && cond_handling
!= 0
2704 && cinfo
->info
[where
].cond_expr_cond_p
)
2706 /* If substituting into a cond_expr condition, unshare. */
2707 if (cond_handling
== 1)
2708 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2709 /* If substituting elsewhere we might need to decompose it. */
2710 else if (cond_handling
== 2)
2712 /* ??? Returning false here will also not allow any other patterns
2713 to match unless this generator was split out. */
2714 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2715 fprintf_indent (f
, indent
, " {\n");
2716 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2717 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2719 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2720 " TREE_OPERAND (%s, 1));\n",
2721 dest
, dest
, dest
, dest
, dest
);
2722 fprintf_indent (f
, indent
, " }\n");
2727 /* Return the name of the operand representing the decision tree node.
2728 Use NAME as space to generate it. */
2731 dt_operand::get_name (char *name
)
2734 sprintf (name
, "t");
2735 else if (parent
->level
== 1)
2736 sprintf (name
, "_p%u", pos
);
2737 else if (parent
->type
== dt_node::DT_MATCH
)
2738 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2740 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2744 /* Fill NAME with the operand name at position POS. */
2747 dt_operand::gen_opname (char *name
, unsigned pos
)
2750 sprintf (name
, "_p%u", pos
);
2752 sprintf (name
, "_q%u%u", level
, pos
);
2755 /* Generate matching code for the decision tree operand which is
2759 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2761 predicate
*p
= as_a
<predicate
*> (op
);
2763 if (p
->p
->matchers
.exists ())
2765 /* If this is a predicate generated from a pattern mangle its
2766 name and pass on the valueize hook. */
2768 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2771 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2774 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2775 fprintf_indent (f
, indent
+ 2, "{\n");
2779 /* Generate matching code for the decision tree operand which is
2783 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2785 char match_opname
[20];
2786 match_dop
->get_name (match_opname
);
2788 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2789 "|| operand_equal_p (%s, %s, 0))\n",
2790 opname
, match_opname
, opname
, opname
, match_opname
);
2792 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2793 "|| (operand_equal_p (%s, %s, 0) "
2794 "&& types_match (%s, %s)))\n",
2795 opname
, match_opname
, opname
, opname
, match_opname
,
2796 opname
, match_opname
);
2797 fprintf_indent (f
, indent
+ 2, "{\n");
2801 /* Generate GIMPLE matching code for the decision tree operand. */
2804 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2806 expr
*e
= static_cast<expr
*> (op
);
2807 id_base
*id
= e
->operation
;
2808 unsigned n_ops
= e
->ops
.length ();
2809 unsigned n_braces
= 0;
2811 for (unsigned i
= 0; i
< n_ops
; ++i
)
2813 char child_opname
[20];
2814 gen_opname (child_opname
, i
);
2816 if (id
->kind
== id_base::CODE
)
2819 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2820 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2822 /* ??? If this is a memory operation we can't (and should not)
2823 match this. The only sensible operand types are
2824 SSA names and invariants. */
2829 fprintf_indent (f
, indent
,
2830 "tree %s = TREE_OPERAND (%s, %i);\n",
2831 child_opname
, opname
, i
);
2834 fprintf_indent (f
, indent
,
2835 "tree %s = TREE_OPERAND "
2836 "(gimple_assign_rhs1 (_a%d), %i);\n",
2837 child_opname
, depth
, i
);
2838 fprintf_indent (f
, indent
,
2839 "if ((TREE_CODE (%s) == SSA_NAME\n",
2841 fprintf_indent (f
, indent
,
2842 " || is_gimple_min_invariant (%s)))\n",
2844 fprintf_indent (f
, indent
,
2848 fprintf_indent (f
, indent
,
2849 "%s = do_valueize (valueize, %s);\n",
2850 child_opname
, child_opname
);
2854 fprintf_indent (f
, indent
,
2855 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2856 child_opname
, i
+ 1, depth
);
2859 fprintf_indent (f
, indent
,
2860 "tree %s = gimple_call_arg (_c%d, %u);\n",
2861 child_opname
, depth
, i
);
2862 fprintf_indent (f
, indent
,
2863 "%s = do_valueize (valueize, %s);\n",
2864 child_opname
, child_opname
);
2866 /* While the toplevel operands are canonicalized by the caller
2867 after valueizing operands of sub-expressions we have to
2868 re-canonicalize operand order. */
2869 int opno
= commutative_op (id
);
2872 char child_opname0
[20], child_opname1
[20];
2873 gen_opname (child_opname0
, opno
);
2874 gen_opname (child_opname1
, opno
+ 1);
2875 fprintf_indent (f
, indent
,
2876 "if (tree_swap_operands_p (%s, %s))\n",
2877 child_opname0
, child_opname1
);
2878 fprintf_indent (f
, indent
,
2879 " std::swap (%s, %s);\n",
2880 child_opname0
, child_opname1
);
2886 /* Generate GENERIC matching code for the decision tree operand. */
2889 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2891 expr
*e
= static_cast<expr
*> (op
);
2892 unsigned n_ops
= e
->ops
.length ();
2894 for (unsigned i
= 0; i
< n_ops
; ++i
)
2896 char child_opname
[20];
2897 gen_opname (child_opname
, i
);
2899 if (e
->operation
->kind
== id_base::CODE
)
2900 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2901 child_opname
, opname
, i
);
2903 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2904 child_opname
, opname
, i
);
2910 /* Generate matching code for the children of the decision tree node. */
2913 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2915 auto_vec
<dt_operand
*> gimple_exprs
;
2916 auto_vec
<dt_operand
*> generic_exprs
;
2917 auto_vec
<dt_operand
*> fns
;
2918 auto_vec
<dt_operand
*> generic_fns
;
2919 auto_vec
<dt_operand
*> preds
;
2920 auto_vec
<dt_node
*> others
;
2922 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2924 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2926 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2927 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2929 if (e
->ops
.length () == 0
2930 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2931 generic_exprs
.safe_push (op
);
2932 else if (e
->operation
->kind
== id_base::FN
)
2937 generic_fns
.safe_push (op
);
2939 else if (e
->operation
->kind
== id_base::PREDICATE
)
2940 preds
.safe_push (op
);
2943 if (gimple
&& !e
->is_generic
)
2944 gimple_exprs
.safe_push (op
);
2946 generic_exprs
.safe_push (op
);
2949 else if (op
->op
->type
== operand::OP_PREDICATE
)
2950 others
.safe_push (kids
[i
]);
2954 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2955 others
.safe_push (kids
[i
]);
2956 else if (kids
[i
]->type
== dt_node::DT_MATCH
2957 || kids
[i
]->type
== dt_node::DT_TRUE
)
2959 /* A DT_TRUE operand serves as a barrier - generate code now
2960 for what we have collected sofar.
2961 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2962 dependent matches to get out-of-order. Generate code now
2963 for what we have collected sofar. */
2964 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2965 fns
, generic_fns
, preds
, others
);
2966 /* And output the true operand itself. */
2967 kids
[i
]->gen (f
, indent
, gimple
, depth
);
2968 gimple_exprs
.truncate (0);
2969 generic_exprs
.truncate (0);
2971 generic_fns
.truncate (0);
2973 others
.truncate (0);
2979 /* Generate code for the remains. */
2980 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2981 fns
, generic_fns
, preds
, others
);
2984 /* Generate matching code for the children of the decision tree node. */
2987 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
2988 const vec
<dt_operand
*> &gimple_exprs
,
2989 const vec
<dt_operand
*> &generic_exprs
,
2990 const vec
<dt_operand
*> &fns
,
2991 const vec
<dt_operand
*> &generic_fns
,
2992 const vec
<dt_operand
*> &preds
,
2993 const vec
<dt_node
*> &others
)
2996 char *kid_opname
= buf
;
2998 unsigned exprs_len
= gimple_exprs
.length ();
2999 unsigned gexprs_len
= generic_exprs
.length ();
3000 unsigned fns_len
= fns
.length ();
3001 unsigned gfns_len
= generic_fns
.length ();
3003 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3006 gimple_exprs
[0]->get_name (kid_opname
);
3008 fns
[0]->get_name (kid_opname
);
3010 generic_fns
[0]->get_name (kid_opname
);
3012 generic_exprs
[0]->get_name (kid_opname
);
3014 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3015 fprintf_indent (f
, indent
, " {\n");
3019 if (exprs_len
|| fns_len
)
3022 fprintf_indent (f
, indent
,
3023 "case SSA_NAME:\n");
3024 fprintf_indent (f
, indent
,
3025 " if (gimple *_d%d = get_def (valueize, %s))\n",
3027 fprintf_indent (f
, indent
,
3032 fprintf_indent (f
, indent
,
3033 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3035 fprintf_indent (f
, indent
,
3036 " switch (gimple_assign_rhs_code (_a%d))\n",
3039 fprintf_indent (f
, indent
, "{\n");
3040 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3042 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3043 id_base
*op
= e
->operation
;
3044 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3045 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3047 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3048 fprintf_indent (f
, indent
, " {\n");
3049 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3050 fprintf_indent (f
, indent
, " break;\n");
3051 fprintf_indent (f
, indent
, " }\n");
3053 fprintf_indent (f
, indent
, "default:;\n");
3054 fprintf_indent (f
, indent
, "}\n");
3060 fprintf_indent (f
, indent
,
3061 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3062 exprs_len
? "else " : "", depth
, depth
);
3063 fprintf_indent (f
, indent
,
3064 " switch (gimple_call_combined_fn (_c%d))\n",
3068 fprintf_indent (f
, indent
, "{\n");
3069 for (unsigned i
= 0; i
< fns_len
; ++i
)
3071 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3072 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3073 /* We need to be defensive against bogus prototypes allowing
3074 calls with not enough arguments. */
3075 fprintf_indent (f
, indent
,
3076 " if (gimple_call_num_args (_c%d) == %d)\n",
3077 depth
, e
->ops
.length ());
3078 fprintf_indent (f
, indent
, " {\n");
3079 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3080 fprintf_indent (f
, indent
, " }\n");
3081 fprintf_indent (f
, indent
, " break;\n");
3084 fprintf_indent (f
, indent
, "default:;\n");
3085 fprintf_indent (f
, indent
, "}\n");
3091 fprintf_indent (f
, indent
, " }\n");
3092 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3093 here rather than in the next loop. */
3094 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3096 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3097 id_base
*op
= e
->operation
;
3098 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3100 fprintf_indent (f
, indent
+ 4, "{\n");
3101 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3102 fprintf_indent (f
, indent
+ 4, "}\n");
3106 fprintf_indent (f
, indent
, " break;\n");
3109 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3111 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3112 id_base
*op
= e
->operation
;
3113 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3114 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3115 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3116 /* Already handled above. */
3119 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3120 fprintf_indent (f
, indent
, " {\n");
3121 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3122 fprintf_indent (f
, indent
, " break;\n");
3123 fprintf_indent (f
, indent
, " }\n");
3128 fprintf_indent (f
, indent
,
3129 "case CALL_EXPR:\n");
3130 fprintf_indent (f
, indent
,
3131 " switch (get_call_combined_fn (%s))\n",
3133 fprintf_indent (f
, indent
,
3137 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3139 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3140 gcc_assert (e
->operation
->kind
== id_base::FN
);
3142 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3143 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3144 " {\n", kid_opname
, e
->ops
.length ());
3145 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3146 fprintf_indent (f
, indent
, " }\n"
3149 fprintf_indent (f
, indent
, "default:;\n");
3152 fprintf_indent (f
, indent
, " }\n");
3153 fprintf_indent (f
, indent
, " break;\n");
3156 /* Close switch (TREE_CODE ()). */
3157 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3160 fprintf_indent (f
, indent
, " default:;\n");
3161 fprintf_indent (f
, indent
, " }\n");
3164 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3166 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3167 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3168 preds
[i
]->get_name (kid_opname
);
3169 fprintf_indent (f
, indent
, "{\n");
3171 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3172 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3173 gimple
? "gimple" : "tree",
3174 p
->id
, kid_opname
, kid_opname
,
3175 gimple
? ", valueize" : "");
3176 fprintf_indent (f
, indent
, " {\n");
3177 for (int j
= 0; j
< p
->nargs
; ++j
)
3179 char child_opname
[20];
3180 preds
[i
]->gen_opname (child_opname
, j
);
3181 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3182 child_opname
, kid_opname
, j
);
3184 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3187 fprintf_indent (f
, indent
, "}\n");
3190 for (unsigned i
= 0; i
< others
.length (); ++i
)
3191 others
[i
]->gen (f
, indent
, gimple
, depth
);
3194 /* Generate matching code for the decision tree operand. */
3197 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3202 unsigned n_braces
= 0;
3204 if (type
== DT_OPERAND
)
3207 case operand::OP_PREDICATE
:
3208 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3211 case operand::OP_EXPR
:
3213 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3215 n_braces
= gen_generic_expr (f
, indent
, opname
);
3221 else if (type
== DT_TRUE
)
3223 else if (type
== DT_MATCH
)
3224 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3228 indent
+= 4 * n_braces
;
3229 gen_kids (f
, indent
, gimple
, depth
);
3231 for (unsigned i
= 0; i
< n_braces
; ++i
)
3236 fprintf_indent (f
, indent
, " }\n");
3241 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3242 step of a '(simplify ...)' or '(match ...)'. This handles everything
3243 that is not part of the decision tree (simplify->match).
3244 Main recursive worker. */
3247 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3251 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3253 fprintf_indent (f
, indent
, "{\n");
3255 output_line_directive (f
, w
->location
);
3256 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3257 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3259 fprintf_indent (f
, indent
, "}\n");
3262 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3264 output_line_directive (f
, ife
->location
);
3265 fprintf_indent (f
, indent
, "if (");
3266 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3268 fprintf_indent (f
, indent
+ 2, "{\n");
3270 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3272 fprintf_indent (f
, indent
+ 2, "}\n");
3275 fprintf_indent (f
, indent
, "else\n");
3276 fprintf_indent (f
, indent
+ 2, "{\n");
3278 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3280 fprintf_indent (f
, indent
+ 2, "}\n");
3286 static unsigned fail_label_cnt
;
3287 char local_fail_label
[256];
3288 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3289 fail_label
= local_fail_label
;
3291 /* Analyze captures and perform early-outs on the incoming arguments
3292 that cover cases we cannot handle. */
3293 capture_info
cinfo (s
, result
, gimple
);
3294 if (s
->kind
== simplify::SIMPLIFY
)
3298 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3299 if (cinfo
.force_no_side_effects
& (1 << i
))
3301 fprintf_indent (f
, indent
,
3302 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3305 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3306 "forcing toplevel operand to have no "
3309 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3310 if (cinfo
.info
[i
].cse_p
)
3312 else if (cinfo
.info
[i
].force_no_side_effects_p
3313 && (cinfo
.info
[i
].toplevel_msk
3314 & cinfo
.force_no_side_effects
) == 0)
3316 fprintf_indent (f
, indent
,
3317 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3318 "goto %s;\n", i
, fail_label
);
3320 warning_at (cinfo
.info
[i
].c
->location
,
3321 "forcing captured operand to have no "
3324 else if ((cinfo
.info
[i
].toplevel_msk
3325 & cinfo
.force_no_side_effects
) != 0)
3326 /* Mark capture as having no side-effects if we had to verify
3327 that via forced toplevel operand checks. */
3328 cinfo
.info
[i
].force_no_side_effects_p
= true;
3332 /* Force single-use restriction by only allowing simple
3333 results via setting seq to NULL. */
3334 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3335 bool first_p
= true;
3336 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3337 if (cinfo
.info
[i
].force_single_use
)
3341 fprintf_indent (f
, indent
, "if (lseq\n");
3342 fprintf_indent (f
, indent
, " && (");
3348 fprintf_indent (f
, indent
, " || ");
3350 fprintf (f
, "!single_use (captures[%d])", i
);
3354 fprintf (f
, "))\n");
3355 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3360 if (s
->kind
== simplify::SIMPLIFY
)
3361 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3363 fprintf_indent (f
, indent
, "if (UNLIKELY (dump_file && (dump_flags & TDF_FOLDING))) "
3364 "fprintf (dump_file, \"%s ",
3365 s
->kind
== simplify::SIMPLIFY
3366 ? "Applying pattern" : "Matching expression");
3367 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3368 output_line_directive (f
,
3369 result
? result
->location
: s
->match
->location
, true,
3371 fprintf (f
, ", __FILE__, __LINE__);\n");
3373 fprintf_indent (f
, indent
, "{\n");
3377 /* If there is no result then this is a predicate implementation. */
3378 fprintf_indent (f
, indent
, "return true;\n");
3382 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3383 in outermost position). */
3384 if (result
->type
== operand::OP_EXPR
3385 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3386 result
= as_a
<expr
*> (result
)->ops
[0];
3387 if (result
->type
== operand::OP_EXPR
)
3389 expr
*e
= as_a
<expr
*> (result
);
3390 id_base
*opr
= e
->operation
;
3391 bool is_predicate
= false;
3392 /* When we delay operator substituting during lowering of fors we
3393 make sure that for code-gen purposes the effects of each substitute
3394 are the same. Thus just look at that. */
3395 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3396 opr
= uid
->substitutes
[0];
3397 else if (is_a
<predicate_id
*> (opr
))
3398 is_predicate
= true;
3400 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3401 *e
->operation
== CONVERT_EXPR
3402 ? "NOP_EXPR" : e
->operation
->id
,
3404 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3408 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3410 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3412 = get_operand_type (opr
, j
,
3413 "type", e
->expr_type
,
3415 : "TREE_TYPE (res_op->ops[0])");
3416 /* We need to expand GENERIC conditions we captured from
3417 COND_EXPRs and we need to unshare them when substituting
3419 int cond_handling
= 0;
3421 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3422 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3423 &cinfo
, indexes
, cond_handling
);
3426 /* Re-fold the toplevel result. It's basically an embedded
3427 gimple_build w/o actually building the stmt. */
3430 fprintf_indent (f
, indent
,
3431 "res_op->resimplify (lseq, valueize);\n");
3433 fprintf_indent (f
, indent
,
3434 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3435 "goto %s;\n", fail_label
);
3438 else if (result
->type
== operand::OP_CAPTURE
3439 || result
->type
== operand::OP_C_EXPR
)
3441 fprintf_indent (f
, indent
, "tree tem;\n");
3442 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3444 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3445 if (is_a
<capture
*> (result
)
3446 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3448 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3449 with substituting a capture of that. */
3450 fprintf_indent (f
, indent
,
3451 "if (COMPARISON_CLASS_P (tem))\n");
3452 fprintf_indent (f
, indent
,
3454 fprintf_indent (f
, indent
,
3455 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3456 fprintf_indent (f
, indent
,
3457 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3458 fprintf_indent (f
, indent
,
3464 fprintf_indent (f
, indent
, "return true;\n");
3468 bool is_predicate
= false;
3469 if (result
->type
== operand::OP_EXPR
)
3471 expr
*e
= as_a
<expr
*> (result
);
3472 id_base
*opr
= e
->operation
;
3473 /* When we delay operator substituting during lowering of fors we
3474 make sure that for code-gen purposes the effects of each substitute
3475 are the same. Thus just look at that. */
3476 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3477 opr
= uid
->substitutes
[0];
3478 else if (is_a
<predicate_id
*> (opr
))
3479 is_predicate
= true;
3480 /* Search for captures used multiple times in the result expression
3481 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3482 original expression. */
3484 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3486 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3487 || cinfo
.info
[i
].cse_p
)
3489 if (cinfo
.info
[i
].result_use_count
3490 > cinfo
.info
[i
].match_use_count
)
3491 fprintf_indent (f
, indent
,
3492 "if (! tree_invariant_p (captures[%d])) "
3493 "goto %s;\n", i
, fail_label
);
3495 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3499 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3502 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3503 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3506 = get_operand_type (opr
, j
,
3507 "type", e
->expr_type
,
3509 ? NULL
: "TREE_TYPE (res_op0)");
3510 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3514 fprintf_indent (f
, indent
, "return true;\n");
3517 fprintf_indent (f
, indent
, "tree _r;\n");
3518 /* Re-fold the toplevel result. Use non_lvalue to
3519 build NON_LVALUE_EXPRs so they get properly
3520 ignored when in GIMPLE form. */
3521 if (*opr
== NON_LVALUE_EXPR
)
3522 fprintf_indent (f
, indent
,
3523 "_r = non_lvalue_loc (loc, res_op0);\n");
3526 if (is_a
<operator_id
*> (opr
))
3527 fprintf_indent (f
, indent
,
3528 "_r = fold_build%d_loc (loc, %s, type",
3530 *e
->operation
== CONVERT_EXPR
3531 ? "NOP_EXPR" : e
->operation
->id
);
3533 fprintf_indent (f
, indent
,
3534 "_r = maybe_build_call_expr_loc (loc, "
3535 "%s, type, %d", e
->operation
->id
,
3537 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3538 fprintf (f
, ", res_op%d", j
);
3539 fprintf (f
, ");\n");
3540 if (!is_a
<operator_id
*> (opr
))
3542 fprintf_indent (f
, indent
, "if (!_r)\n");
3543 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3548 else if (result
->type
== operand::OP_CAPTURE
3549 || result
->type
== operand::OP_C_EXPR
)
3552 fprintf_indent (f
, indent
, "tree _r;\n");
3553 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3560 /* Search for captures not used in the result expression and dependent
3561 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3562 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3564 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3566 if (!cinfo
.info
[i
].force_no_side_effects_p
3567 && !cinfo
.info
[i
].expr_p
3568 && cinfo
.info
[i
].result_use_count
== 0)
3570 fprintf_indent (f
, indent
,
3571 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3573 fprintf_indent (f
, indent
+ 2,
3574 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3575 "fold_ignored_result (captures[%d]), _r);\n",
3579 fprintf_indent (f
, indent
, "return _r;\n");
3583 fprintf_indent (f
, indent
, "}\n");
3584 fprintf (f
, "%s:;\n", fail_label
);
3588 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3589 step of a '(simplify ...)' or '(match ...)'. This handles everything
3590 that is not part of the decision tree (simplify->match). */
3593 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3595 fprintf_indent (f
, indent
, "{\n");
3597 output_line_directive (f
,
3598 s
->result
? s
->result
->location
: s
->match
->location
);
3599 if (s
->capture_max
>= 0)
3602 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3603 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3605 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3609 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3611 fprintf (f
, " };\n");
3614 /* If we have a split-out function for the actual transform, call it. */
3615 if (info
&& info
->fname
)
3619 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3620 "valueize, type, captures", info
->fname
);
3621 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3622 if (s
->for_subst_vec
[i
].first
->used
)
3623 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3624 fprintf (f
, "))\n");
3625 fprintf_indent (f
, indent
, " return true;\n");
3629 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3631 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3632 fprintf (f
, ", _p%d", i
);
3633 fprintf (f
, ", captures");
3634 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3636 if (s
->for_subst_vec
[i
].first
->used
)
3637 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3639 fprintf (f
, ");\n");
3640 fprintf_indent (f
, indent
, "if (res) return res;\n");
3645 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3647 if (! s
->for_subst_vec
[i
].first
->used
)
3649 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3650 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3651 s
->for_subst_vec
[i
].first
->id
,
3652 s
->for_subst_vec
[i
].second
->id
);
3653 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3654 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3655 s
->for_subst_vec
[i
].first
->id
,
3656 s
->for_subst_vec
[i
].second
->id
);
3660 gen_1 (f
, indent
, gimple
, s
->result
);
3664 fprintf_indent (f
, indent
, "}\n");
3668 /* Hash function for finding equivalent transforms. */
3671 sinfo_hashmap_traits::hash (const key_type
&v
)
3673 /* Only bother to compare those originating from the same source pattern. */
3674 return v
->s
->result
->location
;
3677 /* Compare function for finding equivalent transforms. */
3680 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3682 if (o1
->type
!= o2
->type
)
3687 case operand::OP_IF
:
3689 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3690 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3691 /* ??? Properly compare c-exprs. */
3692 if (if1
->cond
!= if2
->cond
)
3694 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3696 if (if1
->falseexpr
!= if2
->falseexpr
3698 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3702 case operand::OP_WITH
:
3704 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3705 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3706 if (with1
->with
!= with2
->with
)
3708 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3713 /* We've hit a result. Time to compare capture-infos - this is required
3714 in addition to the conservative pointer-equivalency of the result IL. */
3715 capture_info
cinfo1 (s1
, o1
, true);
3716 capture_info
cinfo2 (s2
, o2
, true);
3718 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3719 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3722 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3724 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3725 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3726 || (cinfo1
.info
[i
].force_no_side_effects_p
3727 != cinfo2
.info
[i
].force_no_side_effects_p
)
3728 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3729 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3730 /* toplevel_msk is an optimization */
3731 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3732 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3733 /* the pointer back to the capture is for diagnostics only */)
3737 /* ??? Deep-compare the actual result. */
3742 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3743 const key_type
&candidate
)
3745 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3749 /* Main entry to generate code for matching GIMPLE IL off the decision
3753 decision_tree::gen (FILE *f
, bool gimple
)
3759 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3760 "a total number of %u nodes\n",
3761 gimple
? "GIMPLE" : "GENERIC",
3762 root
->num_leafs
, root
->max_level
, root
->total_size
);
3764 /* First split out the transform part of equal leafs. */
3767 for (sinfo_map_t::iterator iter
= si
.begin ();
3768 iter
!= si
.end (); ++iter
)
3770 sinfo
*s
= (*iter
).second
;
3771 /* Do not split out single uses. */
3778 fprintf (stderr
, "found %u uses of", s
->cnt
);
3779 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3782 /* Generate a split out function with the leaf transform code. */
3783 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3786 fprintf (f
, "\nstatic bool\n"
3787 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3788 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3789 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3794 fprintf (f
, "\nstatic tree\n"
3795 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3796 (*iter
).second
->fname
);
3797 for (unsigned i
= 0;
3798 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3799 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3800 fprintf (f
, " tree *captures\n");
3802 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3804 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3806 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3807 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3808 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3809 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3810 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3811 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3814 fprintf (f
, ")\n{\n");
3815 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3817 fprintf (f
, " return false;\n");
3819 fprintf (f
, " return NULL_TREE;\n");
3822 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3824 for (unsigned n
= 1; n
<= 5; ++n
)
3826 bool has_kids_p
= false;
3828 /* First generate split-out functions. */
3829 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3831 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3832 expr
*e
= static_cast<expr
*>(dop
->op
);
3833 if (e
->ops
.length () != n
3834 /* Builtin simplifications are somewhat premature on
3835 GENERIC. The following drops patterns with outermost
3836 calls. It's easy to emit overloads for function code
3837 though if necessary. */
3839 && e
->operation
->kind
!= id_base::CODE
))
3843 fprintf (f
, "\nstatic bool\n"
3844 "gimple_simplify_%s (gimple_match_op *res_op,"
3845 " gimple_seq *seq,\n"
3846 " tree (*valueize)(tree) "
3847 "ATTRIBUTE_UNUSED,\n"
3848 " code_helper ARG_UNUSED (code), tree "
3849 "ARG_UNUSED (type)\n",
3852 fprintf (f
, "\nstatic tree\n"
3853 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3854 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3856 for (unsigned i
= 0; i
< n
; ++i
)
3857 fprintf (f
, ", tree _p%d", i
);
3860 dop
->gen_kids (f
, 2, gimple
, 0);
3862 fprintf (f
, " return false;\n");
3864 fprintf (f
, " return NULL_TREE;\n");
3869 /* If this main entry has no children, avoid generating code
3870 with compiler warnings, by generating a simple stub. */
3874 fprintf (f
, "\nstatic bool\n"
3875 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3876 " tree (*)(tree), code_helper,\n"
3879 fprintf (f
, "\ntree\n"
3880 "generic_simplify (location_t, enum tree_code,\n"
3882 for (unsigned i
= 0; i
< n
; ++i
)
3883 fprintf (f
, ", tree");
3887 fprintf (f
, " return false;\n");
3889 fprintf (f
, " return NULL_TREE;\n");
3894 /* Then generate the main entry with the outermost switch and
3895 tail-calls to the split-out functions. */
3897 fprintf (f
, "\nstatic bool\n"
3898 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3899 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3900 " code_helper code, const tree type");
3902 fprintf (f
, "\ntree\n"
3903 "generic_simplify (location_t loc, enum tree_code code, "
3904 "const tree type ATTRIBUTE_UNUSED");
3905 for (unsigned i
= 0; i
< n
; ++i
)
3906 fprintf (f
, ", tree _p%d", i
);
3911 fprintf (f
, " switch (code.get_rep())\n"
3914 fprintf (f
, " switch (code)\n"
3916 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3918 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3919 expr
*e
= static_cast<expr
*>(dop
->op
);
3920 if (e
->ops
.length () != n
3921 /* Builtin simplifications are somewhat premature on
3922 GENERIC. The following drops patterns with outermost
3923 calls. It's easy to emit overloads for function code
3924 though if necessary. */
3926 && e
->operation
->kind
!= id_base::CODE
))
3929 if (*e
->operation
== CONVERT_EXPR
3930 || *e
->operation
== NOP_EXPR
)
3931 fprintf (f
, " CASE_CONVERT:\n");
3933 fprintf (f
, " case %s%s:\n",
3934 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3937 fprintf (f
, " return gimple_simplify_%s (res_op, "
3938 "seq, valueize, code, type", e
->operation
->id
);
3940 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3942 for (unsigned j
= 0; j
< n
; ++j
)
3943 fprintf (f
, ", _p%d", j
);
3944 fprintf (f
, ");\n");
3946 fprintf (f
, " default:;\n"
3950 fprintf (f
, " return false;\n");
3952 fprintf (f
, " return NULL_TREE;\n");
3957 /* Output code to implement the predicate P from the decision tree DT. */
3960 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3962 fprintf (f
, "\nbool\n"
3963 "%s%s (tree t%s%s)\n"
3964 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3965 p
->nargs
> 0 ? ", tree *res_ops" : "",
3966 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3967 /* Conveniently make 'type' available. */
3968 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3971 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3972 dt
.root
->gen_kids (f
, 2, gimple
, 0);
3974 fprintf_indent (f
, 2, "return false;\n"
3978 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3981 write_header (FILE *f
, const char *head
)
3983 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3984 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3986 /* Include the header instead of writing it awkwardly quoted here. */
3987 fprintf (f
, "\n#include \"%s\"\n", head
);
3997 parser (cpp_reader
*, bool gimple
);
4000 const cpp_token
*next ();
4001 const cpp_token
*peek (unsigned = 1);
4002 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4003 const cpp_token
*expect (enum cpp_ttype
);
4004 const cpp_token
*eat_token (enum cpp_ttype
);
4005 const char *get_string ();
4006 const char *get_ident ();
4007 const cpp_token
*eat_ident (const char *);
4008 const char *get_number ();
4010 unsigned get_internal_capture_id ();
4012 id_base
*parse_operation (unsigned char &);
4013 operand
*parse_capture (operand
*, bool);
4014 operand
*parse_expr ();
4015 c_expr
*parse_c_expr (cpp_ttype
);
4016 operand
*parse_op ();
4018 void record_operlist (location_t
, user_id
*);
4020 void parse_pattern ();
4021 operand
*parse_result (operand
*, predicate_id
*);
4022 void push_simplify (simplify::simplify_kind
,
4023 vec
<simplify
*>&, operand
*, operand
*);
4024 void parse_simplify (simplify::simplify_kind
,
4025 vec
<simplify
*>&, predicate_id
*, operand
*);
4026 void parse_for (location_t
);
4027 void parse_if (location_t
);
4028 void parse_predicates (location_t
);
4029 void parse_operator_list (location_t
);
4031 void finish_match_operand (operand
*);
4035 vec
<c_expr
*> active_ifs
;
4036 vec
<vec
<user_id
*> > active_fors
;
4037 hash_set
<user_id
*> *oper_lists_set
;
4038 vec
<user_id
*> oper_lists
;
4040 cid_map_t
*capture_ids
;
4044 vec
<simplify
*> simplifiers
;
4045 vec
<predicate_id
*> user_predicates
;
4046 bool parsing_match_operand
;
4049 /* Lexing helpers. */
4051 /* Read the next non-whitespace token from R. */
4056 const cpp_token
*token
;
4059 token
= cpp_get_token (r
);
4061 while (token
->type
== CPP_PADDING
);
4065 /* Peek at the next non-whitespace token from R. */
4068 parser::peek (unsigned num
)
4070 const cpp_token
*token
;
4074 token
= cpp_peek_token (r
, i
++);
4076 while (token
->type
== CPP_PADDING
4078 /* If we peek at EOF this is a fatal error as it leaves the
4079 cpp_reader in unusable state. Assume we really wanted a
4080 token and thus this EOF is unexpected. */
4081 if (token
->type
== CPP_EOF
)
4082 fatal_at (token
, "unexpected end of file");
4086 /* Peek at the next identifier token (or return NULL if the next
4087 token is not an identifier or equal to ID if supplied). */
4090 parser::peek_ident (const char *id
, unsigned num
)
4092 const cpp_token
*token
= peek (num
);
4093 if (token
->type
!= CPP_NAME
)
4099 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4100 if (strcmp (id
, t
) == 0)
4106 /* Read the next token from R and assert it is of type TK. */
4109 parser::expect (enum cpp_ttype tk
)
4111 const cpp_token
*token
= next ();
4112 if (token
->type
!= tk
)
4113 fatal_at (token
, "expected %s, got %s",
4114 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4119 /* Consume the next token from R and assert it is of type TK. */
4122 parser::eat_token (enum cpp_ttype tk
)
4127 /* Read the next token from R and assert it is of type CPP_STRING and
4128 return its value. */
4131 parser::get_string ()
4133 const cpp_token
*token
= expect (CPP_STRING
);
4134 return (const char *)token
->val
.str
.text
;
4137 /* Read the next token from R and assert it is of type CPP_NAME and
4138 return its value. */
4141 parser::get_ident ()
4143 const cpp_token
*token
= expect (CPP_NAME
);
4144 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4147 /* Eat an identifier token with value S from R. */
4150 parser::eat_ident (const char *s
)
4152 const cpp_token
*token
= peek ();
4153 const char *t
= get_ident ();
4154 if (strcmp (s
, t
) != 0)
4155 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4159 /* Read the next token from R and assert it is of type CPP_NUMBER and
4160 return its value. */
4163 parser::get_number ()
4165 const cpp_token
*token
= expect (CPP_NUMBER
);
4166 return (const char *)token
->val
.str
.text
;
4169 /* Return a capture ID that can be used internally. */
4172 parser::get_internal_capture_id ()
4174 unsigned newid
= capture_ids
->elements ();
4175 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4178 snprintf (id
, sizeof (id
), "__%u", newid
);
4179 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4181 fatal ("reserved capture id '%s' already used", id
);
4185 /* Record an operator-list use for transparent for handling. */
4188 parser::record_operlist (location_t loc
, user_id
*p
)
4190 if (!oper_lists_set
->add (p
))
4192 if (!oper_lists
.is_empty ()
4193 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4194 fatal_at (loc
, "User-defined operator list does not have the "
4195 "same number of entries as others used in the pattern");
4196 oper_lists
.safe_push (p
);
4200 /* Parse the operator ID, special-casing convert?, convert1? and
4204 parser::parse_operation (unsigned char &opt_grp
)
4206 const cpp_token
*id_tok
= peek ();
4207 char *alt_id
= NULL
;
4208 const char *id
= get_ident ();
4209 const cpp_token
*token
= peek ();
4211 if (token
->type
== CPP_QUERY
4212 && !(token
->flags
& PREV_WHITE
))
4214 if (!parsing_match_operand
)
4215 fatal_at (id_tok
, "conditional convert can only be used in "
4216 "match expression");
4217 if (ISDIGIT (id
[strlen (id
) - 1]))
4219 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4220 alt_id
= xstrdup (id
);
4221 alt_id
[strlen (id
) - 1] = '\0';
4223 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4227 eat_token (CPP_QUERY
);
4229 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4231 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4234 user_id
*p
= dyn_cast
<user_id
*> (op
);
4235 if (p
&& p
->is_oper_list
)
4237 if (active_fors
.length() == 0)
4238 record_operlist (id_tok
->src_loc
, p
);
4240 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4246 capture = '@'<number> */
4249 parser::parse_capture (operand
*op
, bool require_existing
)
4251 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4252 const cpp_token
*token
= peek ();
4253 const char *id
= NULL
;
4254 bool value_match
= false;
4255 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4256 if (token
->type
== CPP_ATSIGN
4257 && ! (token
->flags
& PREV_WHITE
)
4258 && parsing_match_operand
)
4260 eat_token (CPP_ATSIGN
);
4264 if (token
->type
== CPP_NUMBER
)
4266 else if (token
->type
== CPP_NAME
)
4269 fatal_at (token
, "expected number or identifier");
4270 unsigned next_id
= capture_ids
->elements ();
4272 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4275 if (require_existing
)
4276 fatal_at (src_loc
, "unknown capture id");
4279 return new capture (src_loc
, num
, op
, value_match
);
4282 /* Parse an expression
4283 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4286 parser::parse_expr ()
4288 const cpp_token
*token
= peek ();
4289 unsigned char opt_grp
;
4290 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4293 bool is_commutative
= false;
4294 bool force_capture
= false;
4295 const char *expr_type
= NULL
;
4297 if (!parsing_match_operand
4298 && token
->type
== CPP_NOT
4299 && !(token
->flags
& PREV_WHITE
))
4301 eat_token (CPP_NOT
);
4302 e
->force_leaf
= true;
4305 if (token
->type
== CPP_COLON
4306 && !(token
->flags
& PREV_WHITE
))
4308 eat_token (CPP_COLON
);
4310 if (token
->type
== CPP_NAME
4311 && !(token
->flags
& PREV_WHITE
))
4313 const char *s
= get_ident ();
4314 if (!parsing_match_operand
)
4324 = dyn_cast
<operator_id
*> (e
->operation
))
4326 if (!commutative_tree_code (o
->code
)
4327 && !comparison_code_p (o
->code
))
4328 fatal_at (token
, "operation is not commutative");
4330 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4331 for (unsigned i
= 0;
4332 i
< p
->substitutes
.length (); ++i
)
4335 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4337 if (!commutative_tree_code (q
->code
)
4338 && !comparison_code_p (q
->code
))
4339 fatal_at (token
, "operation %s is not "
4340 "commutative", q
->id
);
4343 is_commutative
= true;
4345 else if (*sp
== 'C')
4346 is_commutative
= true;
4347 else if (*sp
== 's')
4349 e
->force_single_use
= true;
4350 force_capture
= true;
4353 fatal_at (token
, "flag %c not recognized", *sp
);
4360 fatal_at (token
, "expected flag or type specifying identifier");
4363 if (token
->type
== CPP_ATSIGN
4364 && !(token
->flags
& PREV_WHITE
))
4365 op
= parse_capture (e
, false);
4366 else if (force_capture
)
4368 unsigned num
= get_internal_capture_id ();
4369 op
= new capture (token
->src_loc
, num
, e
, false);
4376 if (token
->type
== CPP_CLOSE_PAREN
)
4378 if (e
->operation
->nargs
!= -1
4379 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4380 fatal_at (token
, "'%s' expects %u operands, not %u",
4381 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4384 if (e
->ops
.length () == 2
4385 || commutative_op (e
->operation
) >= 0)
4386 e
->is_commutative
= true;
4388 fatal_at (token
, "only binary operators or functions with "
4389 "two arguments can be marked commutative, "
4390 "unless the operation is known to be inherently "
4393 e
->expr_type
= expr_type
;
4396 if (e
->ops
.length () != 1)
4397 fatal_at (token
, "only unary operations can be conditional");
4398 e
->opt_grp
= opt_grp
;
4402 else if (!(token
->flags
& PREV_WHITE
))
4403 fatal_at (token
, "expected expression operand");
4405 e
->append_op (parse_op ());
4410 /* Lex native C code delimited by START recording the preprocessing tokens
4411 for later processing.
4412 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4415 parser::parse_c_expr (cpp_ttype start
)
4417 const cpp_token
*token
;
4420 vec
<cpp_token
> code
= vNULL
;
4421 unsigned nr_stmts
= 0;
4422 location_t loc
= eat_token (start
)->src_loc
;
4423 if (start
== CPP_OPEN_PAREN
)
4424 end
= CPP_CLOSE_PAREN
;
4425 else if (start
== CPP_OPEN_BRACE
)
4426 end
= CPP_CLOSE_BRACE
;
4434 /* Count brace pairs to find the end of the expr to match. */
4435 if (token
->type
== start
)
4437 else if (token
->type
== end
4440 else if (token
->type
== CPP_EOF
)
4441 fatal_at (token
, "unexpected end of file");
4443 /* This is a lame way of counting the number of statements. */
4444 if (token
->type
== CPP_SEMICOLON
)
4447 /* If this is possibly a user-defined identifier mark it used. */
4448 if (token
->type
== CPP_NAME
)
4451 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4452 if (strcmp (str
, "return") == 0)
4453 fatal_at (token
, "return statement not allowed in C expression");
4454 id_base
*idb
= get_operator (str
);
4456 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4457 record_operlist (token
->src_loc
, p
);
4460 /* Record the token. */
4461 code
.safe_push (*token
);
4464 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4467 /* Parse an operand which is either an expression, a predicate or
4468 a standalone capture.
4469 op = predicate | expr | c_expr | capture */
4474 const cpp_token
*token
= peek ();
4475 class operand
*op
= NULL
;
4476 if (token
->type
== CPP_OPEN_PAREN
)
4478 eat_token (CPP_OPEN_PAREN
);
4480 eat_token (CPP_CLOSE_PAREN
);
4482 else if (token
->type
== CPP_OPEN_BRACE
)
4484 op
= parse_c_expr (CPP_OPEN_BRACE
);
4488 /* Remaining ops are either empty or predicates */
4489 if (token
->type
== CPP_NAME
)
4491 const char *id
= get_ident ();
4492 id_base
*opr
= get_operator (id
);
4494 fatal_at (token
, "expected predicate name");
4495 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4497 if (code1
->nargs
!= 0)
4498 fatal_at (token
, "using an operator with operands as predicate");
4499 /* Parse the zero-operand operator "predicates" as
4501 op
= new expr (opr
, token
->src_loc
);
4503 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4505 if (code2
->nargs
!= 0)
4506 fatal_at (token
, "using an operator with operands as predicate");
4507 /* Parse the zero-operand operator "predicates" as
4509 op
= new expr (opr
, token
->src_loc
);
4511 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4512 op
= new predicate (p
, token
->src_loc
);
4514 fatal_at (token
, "using an unsupported operator as predicate");
4515 if (!parsing_match_operand
)
4516 fatal_at (token
, "predicates are only allowed in match expression");
4518 if (token
->flags
& PREV_WHITE
)
4521 else if (token
->type
!= CPP_COLON
4522 && token
->type
!= CPP_ATSIGN
)
4523 fatal_at (token
, "expected expression or predicate");
4524 /* optionally followed by a capture and a predicate. */
4525 if (token
->type
== CPP_COLON
)
4526 fatal_at (token
, "not implemented: predicate on leaf operand");
4527 if (token
->type
== CPP_ATSIGN
)
4528 op
= parse_capture (op
, !parsing_match_operand
);
4534 /* Create a new simplify from the current parsing state and MATCH,
4535 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4538 parser::push_simplify (simplify::simplify_kind kind
,
4539 vec
<simplify
*>& simplifiers
,
4540 operand
*match
, operand
*result
)
4542 /* Build and push a temporary for operator list uses in expressions. */
4543 if (!oper_lists
.is_empty ())
4544 active_fors
.safe_push (oper_lists
);
4546 simplifiers
.safe_push
4547 (new simplify (kind
, last_id
++, match
, result
,
4548 active_fors
.copy (), capture_ids
));
4550 if (!oper_lists
.is_empty ())
4555 <result-op> = <op> | <if> | <with>
4556 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4557 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4561 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4563 const cpp_token
*token
= peek ();
4564 if (token
->type
!= CPP_OPEN_PAREN
)
4567 eat_token (CPP_OPEN_PAREN
);
4568 if (peek_ident ("if"))
4571 if_expr
*ife
= new if_expr (token
->src_loc
);
4572 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4573 if (peek ()->type
== CPP_OPEN_PAREN
)
4575 ife
->trueexpr
= parse_result (result
, matcher
);
4576 if (peek ()->type
== CPP_OPEN_PAREN
)
4577 ife
->falseexpr
= parse_result (result
, matcher
);
4578 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4579 ife
->falseexpr
= parse_op ();
4581 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4583 ife
->trueexpr
= parse_op ();
4584 if (peek ()->type
== CPP_OPEN_PAREN
)
4585 ife
->falseexpr
= parse_result (result
, matcher
);
4586 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4587 ife
->falseexpr
= parse_op ();
4589 /* If this if is immediately closed then it contains a
4590 manual matcher or is part of a predicate definition. */
4591 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4594 fatal_at (peek (), "manual transform not implemented");
4595 ife
->trueexpr
= result
;
4597 eat_token (CPP_CLOSE_PAREN
);
4600 else if (peek_ident ("with"))
4603 with_expr
*withe
= new with_expr (token
->src_loc
);
4604 /* Parse (with c-expr expr) as (if-with (true) expr). */
4605 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4606 withe
->with
->nr_stmts
= 0;
4607 withe
->subexpr
= parse_result (result
, matcher
);
4608 eat_token (CPP_CLOSE_PAREN
);
4611 else if (peek_ident ("switch"))
4613 token
= eat_ident ("switch");
4614 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4616 if_expr
*ife
= new if_expr (ifloc
);
4618 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4619 if (peek ()->type
== CPP_OPEN_PAREN
)
4620 ife
->trueexpr
= parse_result (result
, matcher
);
4622 ife
->trueexpr
= parse_op ();
4623 eat_token (CPP_CLOSE_PAREN
);
4624 if (peek ()->type
!= CPP_OPEN_PAREN
4625 || !peek_ident ("if", 2))
4626 fatal_at (token
, "switch can be implemented with a single if");
4627 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4629 if (peek ()->type
== CPP_OPEN_PAREN
)
4631 if (peek_ident ("if", 2))
4633 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4635 ife
->falseexpr
= new if_expr (ifloc
);
4636 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4637 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4638 if (peek ()->type
== CPP_OPEN_PAREN
)
4639 ife
->trueexpr
= parse_result (result
, matcher
);
4641 ife
->trueexpr
= parse_op ();
4642 eat_token (CPP_CLOSE_PAREN
);
4646 /* switch default clause */
4647 ife
->falseexpr
= parse_result (result
, matcher
);
4648 eat_token (CPP_CLOSE_PAREN
);
4654 /* switch default clause */
4655 ife
->falseexpr
= parse_op ();
4656 eat_token (CPP_CLOSE_PAREN
);
4660 eat_token (CPP_CLOSE_PAREN
);
4665 operand
*op
= result
;
4668 eat_token (CPP_CLOSE_PAREN
);
4674 simplify = 'simplify' <expr> <result-op>
4676 match = 'match' <ident> <expr> [<result-op>]
4677 and fill SIMPLIFIERS with the results. */
4680 parser::parse_simplify (simplify::simplify_kind kind
,
4681 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4684 /* Reset the capture map. */
4686 capture_ids
= new cid_map_t
;
4687 /* Reset oper_lists and set. */
4688 hash_set
<user_id
*> olist
;
4689 oper_lists_set
= &olist
;
4692 const cpp_token
*loc
= peek ();
4693 parsing_match_operand
= true;
4694 class operand
*match
= parse_op ();
4695 finish_match_operand (match
);
4696 parsing_match_operand
= false;
4697 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4698 fatal_at (loc
, "outermost expression cannot be captured");
4699 if (match
->type
== operand::OP_EXPR
4700 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4701 fatal_at (loc
, "outermost expression cannot be a predicate");
4703 /* Splice active_ifs onto result and continue parsing the
4705 if_expr
*active_if
= NULL
;
4706 for (int i
= active_ifs
.length (); i
> 0; --i
)
4708 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4709 ifc
->cond
= active_ifs
[i
-1];
4710 ifc
->trueexpr
= active_if
;
4713 if_expr
*outermost_if
= active_if
;
4714 while (active_if
&& active_if
->trueexpr
)
4715 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4717 const cpp_token
*token
= peek ();
4719 /* If this if is immediately closed then it is part of a predicate
4720 definition. Push it. */
4721 if (token
->type
== CPP_CLOSE_PAREN
)
4724 fatal_at (token
, "expected transform expression");
4727 active_if
->trueexpr
= result
;
4728 result
= outermost_if
;
4730 push_simplify (kind
, simplifiers
, match
, result
);
4734 operand
*tem
= parse_result (result
, matcher
);
4737 active_if
->trueexpr
= tem
;
4738 result
= outermost_if
;
4743 push_simplify (kind
, simplifiers
, match
, result
);
4746 /* Parsing of the outer control structures. */
4748 /* Parse a for expression
4749 for = '(' 'for' <subst>... <pattern> ')'
4750 subst = <ident> '(' <ident>... ')' */
4753 parser::parse_for (location_t
)
4755 auto_vec
<const cpp_token
*> user_id_tokens
;
4756 vec
<user_id
*> user_ids
= vNULL
;
4757 const cpp_token
*token
;
4758 unsigned min_n_opers
= 0, max_n_opers
= 0;
4763 if (token
->type
!= CPP_NAME
)
4766 /* Insert the user defined operators into the operator hash. */
4767 const char *id
= get_ident ();
4768 if (get_operator (id
, true) != NULL
)
4769 fatal_at (token
, "operator already defined");
4770 user_id
*op
= new user_id (id
);
4771 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4773 user_ids
.safe_push (op
);
4774 user_id_tokens
.safe_push (token
);
4776 eat_token (CPP_OPEN_PAREN
);
4779 while ((token
= peek_ident ()) != 0)
4781 const char *oper
= get_ident ();
4782 id_base
*idb
= get_operator (oper
, true);
4784 fatal_at (token
, "no such operator '%s'", oper
);
4788 else if (idb
->nargs
== -1)
4790 else if (idb
->nargs
!= arity
)
4791 fatal_at (token
, "operator '%s' with arity %d does not match "
4792 "others with arity %d", oper
, idb
->nargs
, arity
);
4794 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4797 if (p
->is_oper_list
)
4798 op
->substitutes
.safe_splice (p
->substitutes
);
4800 fatal_at (token
, "iterator cannot be used as operator-list");
4803 op
->substitutes
.safe_push (idb
);
4806 token
= expect (CPP_CLOSE_PAREN
);
4808 unsigned nsubstitutes
= op
->substitutes
.length ();
4809 if (nsubstitutes
== 0)
4810 fatal_at (token
, "A user-defined operator must have at least "
4811 "one substitution");
4812 if (max_n_opers
== 0)
4814 min_n_opers
= nsubstitutes
;
4815 max_n_opers
= nsubstitutes
;
4819 if (nsubstitutes
% min_n_opers
!= 0
4820 && min_n_opers
% nsubstitutes
!= 0)
4821 fatal_at (token
, "All user-defined identifiers must have a "
4822 "multiple number of operator substitutions of the "
4823 "smallest number of substitutions");
4824 if (nsubstitutes
< min_n_opers
)
4825 min_n_opers
= nsubstitutes
;
4826 else if (nsubstitutes
> max_n_opers
)
4827 max_n_opers
= nsubstitutes
;
4831 unsigned n_ids
= user_ids
.length ();
4833 fatal_at (token
, "for requires at least one user-defined identifier");
4836 if (token
->type
== CPP_CLOSE_PAREN
)
4837 fatal_at (token
, "no pattern defined in for");
4839 active_fors
.safe_push (user_ids
);
4843 if (token
->type
== CPP_CLOSE_PAREN
)
4849 /* Remove user-defined operators from the hash again. */
4850 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4852 if (!user_ids
[i
]->used
)
4853 warning_at (user_id_tokens
[i
],
4854 "operator %s defined but not used", user_ids
[i
]->id
);
4855 operators
->remove_elt (user_ids
[i
]);
4859 /* Parse an identifier associated with a list of operators.
4860 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4863 parser::parse_operator_list (location_t
)
4865 const cpp_token
*token
= peek ();
4866 const char *id
= get_ident ();
4868 if (get_operator (id
, true) != 0)
4869 fatal_at (token
, "operator %s already defined", id
);
4871 user_id
*op
= new user_id (id
, true);
4874 while ((token
= peek_ident ()) != 0)
4877 const char *oper
= get_ident ();
4878 id_base
*idb
= get_operator (oper
, true);
4881 fatal_at (token
, "no such operator '%s'", oper
);
4885 else if (idb
->nargs
== -1)
4887 else if (arity
!= idb
->nargs
)
4888 fatal_at (token
, "operator '%s' with arity %d does not match "
4889 "others with arity %d", oper
, idb
->nargs
, arity
);
4891 /* We allow composition of multiple operator lists. */
4892 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4893 op
->substitutes
.safe_splice (p
->substitutes
);
4895 op
->substitutes
.safe_push (idb
);
4898 // Check that there is no junk after id-list
4900 if (token
->type
!= CPP_CLOSE_PAREN
)
4901 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4903 if (op
->substitutes
.length () == 0)
4904 fatal_at (token
, "operator-list cannot be empty");
4907 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4911 /* Parse an outer if expression.
4912 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4915 parser::parse_if (location_t
)
4917 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4919 const cpp_token
*token
= peek ();
4920 if (token
->type
== CPP_CLOSE_PAREN
)
4921 fatal_at (token
, "no pattern defined in if");
4923 active_ifs
.safe_push (ifexpr
);
4927 if (token
->type
== CPP_CLOSE_PAREN
)
4935 /* Parse a list of predefined predicate identifiers.
4936 preds = '(' 'define_predicates' <ident>... ')' */
4939 parser::parse_predicates (location_t
)
4943 const cpp_token
*token
= peek ();
4944 if (token
->type
!= CPP_NAME
)
4947 add_predicate (get_ident ());
4952 /* Parse outer control structures.
4953 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4956 parser::parse_pattern ()
4958 /* All clauses start with '('. */
4959 eat_token (CPP_OPEN_PAREN
);
4960 const cpp_token
*token
= peek ();
4961 const char *id
= get_ident ();
4962 if (strcmp (id
, "simplify") == 0)
4964 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4967 else if (strcmp (id
, "match") == 0)
4969 bool with_args
= false;
4970 location_t e_loc
= peek ()->src_loc
;
4971 if (peek ()->type
== CPP_OPEN_PAREN
)
4973 eat_token (CPP_OPEN_PAREN
);
4976 const char *name
= get_ident ();
4977 id_base
*id1
= get_operator (name
);
4981 p
= add_predicate (name
);
4982 user_predicates
.safe_push (p
);
4984 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
4987 fatal_at (token
, "cannot add a match to a non-predicate ID");
4988 /* Parse (match <id> <arg>... (match-expr)) here. */
4992 capture_ids
= new cid_map_t
;
4993 e
= new expr (p
, e_loc
);
4994 while (peek ()->type
== CPP_ATSIGN
)
4995 e
->append_op (parse_capture (NULL
, false));
4996 eat_token (CPP_CLOSE_PAREN
);
4999 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5000 || (!e
&& p
->nargs
!= 0)))
5001 fatal_at (token
, "non-matching number of match operands");
5002 p
->nargs
= e
? e
->ops
.length () : 0;
5003 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5006 else if (strcmp (id
, "for") == 0)
5007 parse_for (token
->src_loc
);
5008 else if (strcmp (id
, "if") == 0)
5009 parse_if (token
->src_loc
);
5010 else if (strcmp (id
, "define_predicates") == 0)
5012 if (active_ifs
.length () > 0
5013 || active_fors
.length () > 0)
5014 fatal_at (token
, "define_predicates inside if or for is not supported");
5015 parse_predicates (token
->src_loc
);
5017 else if (strcmp (id
, "define_operator_list") == 0)
5019 if (active_ifs
.length () > 0
5020 || active_fors
.length () > 0)
5021 fatal_at (token
, "operator-list inside if or for is not supported");
5022 parse_operator_list (token
->src_loc
);
5025 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5026 active_ifs
.length () == 0 && active_fors
.length () == 0
5027 ? "'define_predicates', " : "");
5029 eat_token (CPP_CLOSE_PAREN
);
5032 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5036 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5041 if (capture
*c
= dyn_cast
<capture
*> (op
))
5043 cpts
[c
->where
].safe_push (c
);
5044 walk_captures (c
->what
, cpts
);
5046 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5047 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5048 walk_captures (e
->ops
[i
], cpts
);
5051 /* Finish up OP which is a match operand. */
5054 parser::finish_match_operand (operand
*op
)
5056 /* Look for matching captures, diagnose mis-uses of @@ and apply
5057 early lowering and distribution of value_match. */
5058 auto_vec
<vec
<capture
*> > cpts
;
5059 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5060 walk_captures (op
, cpts
);
5061 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5063 capture
*value_match
= NULL
;
5064 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5066 if (cpts
[i
][j
]->value_match
)
5069 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5070 value_match
= cpts
[i
][j
];
5073 if (cpts
[i
].length () == 1 && value_match
)
5074 fatal_at (value_match
->location
, "@@ without a matching capture");
5077 /* Duplicate prevailing capture with the existing ID, create
5078 a fake ID and rewrite all captures to use it. This turns
5079 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5080 value_match
->what
= new capture (value_match
->location
,
5082 value_match
->what
, false);
5083 /* Create a fake ID and rewrite all captures to use it. */
5084 unsigned newid
= get_internal_capture_id ();
5085 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5087 cpts
[i
][j
]->where
= newid
;
5088 cpts
[i
][j
]->value_match
= true;
5095 /* Main entry of the parser. Repeatedly parse outer control structures. */
5097 parser::parser (cpp_reader
*r_
, bool gimple_
)
5102 active_fors
= vNULL
;
5103 simplifiers
= vNULL
;
5104 oper_lists_set
= NULL
;
5107 user_predicates
= vNULL
;
5108 parsing_match_operand
= false;
5111 const cpp_token
*token
= next ();
5112 while (token
->type
!= CPP_EOF
)
5114 _cpp_backup_tokens (r
, 1);
5121 /* Helper for the linemap code. */
5124 round_alloc_size (size_t s
)
5130 /* The genmatch generator program. It reads from a pattern description
5131 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5134 main (int argc
, char **argv
)
5138 progname
= "genmatch";
5144 char *input
= argv
[argc
-1];
5145 for (int i
= 1; i
< argc
- 1; ++i
)
5147 if (strcmp (argv
[i
], "--gimple") == 0)
5149 else if (strcmp (argv
[i
], "--generic") == 0)
5151 else if (strcmp (argv
[i
], "-v") == 0)
5153 else if (strcmp (argv
[i
], "-vv") == 0)
5157 fprintf (stderr
, "Usage: genmatch "
5158 "[--gimple] [--generic] [-v[v]] input\n");
5163 line_table
= XCNEW (class line_maps
);
5164 linemap_init (line_table
, 0);
5165 line_table
->reallocator
= xrealloc
;
5166 line_table
->round_alloc_size
= round_alloc_size
;
5168 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5169 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5170 cb
->diagnostic
= diagnostic_cb
;
5172 /* Add the build directory to the #include "" search path. */
5173 cpp_dir
*dir
= XCNEW (cpp_dir
);
5174 dir
->name
= getpwd ();
5176 dir
->name
= ASTRDUP (".");
5177 cpp_set_include_chains (r
, dir
, NULL
, false);
5179 if (!cpp_read_main_file (r
, input
))
5181 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5182 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5184 null_id
= new id_base (id_base::NULL_ID
, "null");
5186 /* Pre-seed operators. */
5187 operators
= new hash_table
<id_base
> (1024);
5188 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5189 add_operator (SYM, # SYM, # TYPE, NARGS);
5190 #define END_OF_BASE_TREE_CODES
5192 #undef END_OF_BASE_TREE_CODES
5195 /* Pre-seed builtin functions.
5196 ??? Cannot use N (name) as that is targetm.emultls.get_address
5197 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5198 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5199 add_function (ENUM, "CFN_" # ENUM);
5200 #include "builtins.def"
5202 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5203 add_function (IFN_##CODE, "CFN_" #CODE);
5204 #include "internal-fn.def"
5207 parser
p (r
, gimple
);
5210 write_header (stdout
, "gimple-match-head.cc");
5212 write_header (stdout
, "generic-match-head.cc");
5214 /* Go over all predicates defined with patterns and perform
5215 lowering and code generation. */
5216 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5218 predicate_id
*pred
= p
.user_predicates
[i
];
5219 lower (pred
->matchers
, gimple
);
5222 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5223 print_matches (pred
->matchers
[j
]);
5226 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5227 dt
.insert (pred
->matchers
[j
], j
);
5232 write_predicate (stdout
, pred
, dt
, gimple
);
5235 /* Lower the main simplifiers and generate code for them. */
5236 lower (p
.simplifiers
, gimple
);
5239 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5240 print_matches (p
.simplifiers
[i
]);
5243 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5244 dt
.insert (p
.simplifiers
[i
], i
);
5249 dt
.gen (stdout
, gimple
);
5252 cpp_finish (r
, NULL
);