1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2023 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
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
))
510 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
512 int res
= commutative_op (uid
->substitutes
[0]);
515 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
516 if (res
!= commutative_op (uid
->substitutes
[i
]))
523 /* Add a predicate identifier to the hash. */
525 static predicate_id
*
526 add_predicate (const char *id
)
528 predicate_id
*p
= new predicate_id (id
);
529 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
531 fatal ("duplicate id definition");
536 /* Add a tree code identifier to the hash. */
539 add_operator (enum tree_code code
, const char *id
,
540 const char *tcc
, unsigned nargs
)
542 if (strcmp (tcc
, "tcc_unary") != 0
543 && strcmp (tcc
, "tcc_binary") != 0
544 && strcmp (tcc
, "tcc_comparison") != 0
545 && strcmp (tcc
, "tcc_expression") != 0
546 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
547 && strcmp (tcc
, "tcc_reference") != 0
548 /* To have INTEGER_CST and friends as "predicate operators". */
549 && strcmp (tcc
, "tcc_constant") != 0
550 /* And allow CONSTRUCTOR for vector initializers. */
551 && !(code
== CONSTRUCTOR
)
552 /* Allow SSA_NAME as predicate operator. */
553 && !(code
== SSA_NAME
))
555 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
556 if (code
== ADDR_EXPR
)
558 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
559 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
561 fatal ("duplicate id definition");
565 /* Add a built-in or internal function identifier to the hash. ID is
566 the name of its CFN_* enumeration value. */
568 template <typename T
>
570 add_function (T code
, const char *id
)
572 fn_id
*fn
= new fn_id (code
, id
);
573 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
575 fatal ("duplicate id definition");
579 /* Helper for easy comparing ID with tree code CODE. */
582 operator==(id_base
&id
, enum tree_code code
)
584 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
585 return oid
->code
== code
;
589 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
592 get_operator (const char *id
, bool allow_null
= false)
594 if (allow_null
&& strcmp (id
, "null") == 0)
597 id_base
tem (id_base::CODE
, id
);
599 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
602 /* If this is a user-defined identifier track whether it was used. */
603 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
609 bool all_upper
= true;
610 bool all_lower
= true;
611 for (unsigned int i
= 0; id
[i
]; ++i
)
614 else if (ISLOWER (id
[i
]))
618 /* Try in caps with _EXPR appended. */
619 id2
= ACONCAT ((id
, "_EXPR", NULL
));
620 for (unsigned int i
= 0; id2
[i
]; ++i
)
621 id2
[i
] = TOUPPER (id2
[i
]);
623 else if (all_upper
&& startswith (id
, "IFN_"))
624 /* Try CFN_ instead of IFN_. */
625 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
626 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
627 /* Try prepending CFN_. */
628 id2
= ACONCAT (("CFN_", id
, NULL
));
632 new (&tem
) id_base (id_base::CODE
, id2
);
633 return operators
->find_with_hash (&tem
, tem
.hashval
);
636 /* Return the comparison operators that results if the operands are
637 swapped. This is safe for floating-point. */
640 swap_tree_comparison (operator_id
*p
)
652 return get_operator ("LT_EXPR");
654 return get_operator ("LE_EXPR");
656 return get_operator ("GT_EXPR");
658 return get_operator ("GE_EXPR");
660 return get_operator ("UNLT_EXPR");
662 return get_operator ("UNLE_EXPR");
664 return get_operator ("UNGT_EXPR");
666 return get_operator ("UNGE_EXPR");
672 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
675 /* The AST produced by parsing of the pattern definitions. */
680 /* The base class for operands. */
684 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
685 operand (enum op_type type_
, location_t loc_
)
686 : type (type_
), location (loc_
) {}
689 virtual void gen_transform (FILE *, int, const char *, bool, int,
690 const char *, capture_info
*,
693 { gcc_unreachable (); }
696 /* A predicate operand. Predicates are leafs in the AST. */
698 class predicate
: public operand
701 predicate (predicate_id
*p_
, location_t loc
)
702 : operand (OP_PREDICATE
, loc
), p (p_
) {}
706 /* An operand that constitutes an expression. Expressions include
707 function calls and user-defined predicate invocations. */
709 class expr
: public operand
712 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
713 : operand (OP_EXPR
, loc
), operation (operation_
),
714 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
715 is_generic (false), force_single_use (false), force_leaf (false),
718 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
719 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
720 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
721 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
722 void append_op (operand
*op
) { ops
.safe_push (op
); }
723 /* The operator and its operands. */
726 /* An explicitely specified type - used exclusively for conversions. */
727 const char *expr_type
;
728 /* Whether the operation is to be applied commutatively. This is
729 later lowered to two separate patterns. */
731 /* Whether the expression is expected to be in GENERIC form. */
733 /* Whether pushing any stmt to the sequence should be conditional
734 on this expression having a single-use. */
735 bool force_single_use
;
736 /* Whether in the result expression this should be a leaf node
737 with any children simplified down to simple operands. */
739 /* If non-zero, the group for optional handling. */
740 unsigned char opt_grp
;
741 void gen_transform (FILE *f
, int, const char *, bool, int,
742 const char *, capture_info
*,
743 dt_operand
** = 0, int = 0) override
;
746 /* An operator that is represented by native C code. This is always
747 a leaf operand in the AST. This class is also used to represent
748 the code to be generated for 'if' and 'with' expressions. */
750 class c_expr
: public operand
753 /* A mapping of an identifier and its replacement. Used to apply
759 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
762 c_expr (cpp_reader
*r_
, location_t loc
,
763 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
764 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
765 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
766 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
767 /* cpplib tokens and state to transform this back to source. */
770 cid_map_t
*capture_ids
;
771 /* The number of statements parsed (well, the number of ';'s). */
773 /* The identifier replacement vector. */
775 void gen_transform (FILE *f
, int, const char *, bool, int,
776 const char *, capture_info
*,
777 dt_operand
** = 0, int = 0) final override
;
780 /* A wrapper around another operand that captures its value. */
782 class capture
: public operand
785 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
786 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
788 /* Identifier index for the value. */
790 /* Whether in a match of two operands the compare should be for
791 equal values rather than equal atoms (boils down to a type
794 /* The captured value. */
796 void gen_transform (FILE *f
, int, const char *, bool, int,
797 const char *, capture_info
*,
798 dt_operand
** = 0, int = 0) final override
;
803 class if_expr
: public operand
806 if_expr (location_t loc
)
807 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
813 /* with expression. */
815 class with_expr
: public operand
818 with_expr (location_t loc
)
819 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
827 is_a_helper
<capture
*>::test (operand
*op
)
829 return op
->type
== operand::OP_CAPTURE
;
835 is_a_helper
<predicate
*>::test (operand
*op
)
837 return op
->type
== operand::OP_PREDICATE
;
843 is_a_helper
<c_expr
*>::test (operand
*op
)
845 return op
->type
== operand::OP_C_EXPR
;
851 is_a_helper
<expr
*>::test (operand
*op
)
853 return op
->type
== operand::OP_EXPR
;
859 is_a_helper
<if_expr
*>::test (operand
*op
)
861 return op
->type
== operand::OP_IF
;
867 is_a_helper
<with_expr
*>::test (operand
*op
)
869 return op
->type
== operand::OP_WITH
;
872 /* The main class of a pattern and its transform. This is used to
873 represent both (simplify ...) and (match ...) kinds. The AST
874 duplicates all outer 'if' and 'for' expressions here so each
875 simplify can exist in isolation. */
880 enum simplify_kind
{ SIMPLIFY
, MATCH
};
882 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
883 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
884 cid_map_t
*capture_ids_
)
885 : kind (kind_
), id (id_
), match (match_
), result (result_
),
886 for_vec (for_vec_
), for_subst_vec (vNULL
),
887 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
890 /* ID. This is kept to easily associate related simplifies expanded
891 from the same original one. */
893 /* The expression that is matched against the GENERIC or GIMPLE IL. */
895 /* For a (simplify ...) an expression with ifs and withs with the expression
896 produced when the pattern applies in the leafs.
897 For a (match ...) the leafs are either empty if it is a simple predicate
898 or the single expression specifying the matched operands. */
899 class operand
*result
;
900 /* Collected 'for' expression operators that have to be replaced
901 in the lowering phase. */
902 vec
<vec
<user_id
*> > for_vec
;
903 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
904 /* A map of capture identifiers to indexes. */
905 cid_map_t
*capture_ids
;
909 /* Debugging routines for dumping the AST. */
912 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
914 if (capture
*c
= dyn_cast
<capture
*> (o
))
916 if (c
->what
&& flattened
== false)
917 print_operand (c
->what
, f
, flattened
);
918 fprintf (f
, "@%u", c
->where
);
921 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
922 fprintf (f
, "%s", p
->p
->id
);
924 else if (is_a
<c_expr
*> (o
))
925 fprintf (f
, "c_expr");
927 else if (expr
*e
= dyn_cast
<expr
*> (o
))
929 if (e
->ops
.length () == 0)
930 fprintf (f
, "%s", e
->operation
->id
);
933 fprintf (f
, "(%s", e
->operation
->id
);
935 if (flattened
== false)
937 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
940 print_operand (e
->ops
[i
], f
, flattened
);
952 print_matches (class simplify
*s
, FILE *f
= stderr
)
954 fprintf (f
, "for expression: ");
955 print_operand (s
->match
, f
);
962 /* Lowering of commutative operators. */
965 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
966 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
968 if (n
== ops_vector
.length ())
970 vec
<operand
*> xv
= v
.copy ();
971 result
.safe_push (xv
);
975 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
977 v
[n
] = ops_vector
[n
][i
];
978 cartesian_product (ops_vector
, result
, v
, n
+ 1);
982 /* Lower OP to two operands in case it is marked as commutative. */
984 static vec
<operand
*>
985 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
987 vec
<operand
*> ret
= vNULL
;
989 if (capture
*c
= dyn_cast
<capture
*> (op
))
996 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
997 for (unsigned i
= 0; i
< v
.length (); ++i
)
999 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
1006 expr
*e
= dyn_cast
<expr
*> (op
);
1007 if (!e
|| e
->ops
.length () == 0)
1013 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1014 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1015 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1017 auto_vec
< vec
<operand
*> > result
;
1018 auto_vec
<operand
*> v (e
->ops
.length ());
1019 v
.quick_grow_cleared (e
->ops
.length ());
1020 cartesian_product (ops_vector
, result
, v
, 0);
1023 for (unsigned i
= 0; i
< result
.length (); ++i
)
1025 expr
*ne
= new expr (e
);
1026 ne
->is_commutative
= false;
1027 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1028 ne
->append_op (result
[i
][j
]);
1032 if (!e
->is_commutative
)
1035 /* The operation is always binary if it isn't inherently commutative. */
1036 int natural_opno
= commutative_op (e
->operation
);
1037 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1038 for (unsigned i
= 0; i
< result
.length (); ++i
)
1040 expr
*ne
= new expr (e
);
1041 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1043 if (comparison_code_p (r
->code
))
1044 ne
->operation
= swap_tree_comparison (r
);
1046 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1048 bool found_compare
= false;
1049 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1050 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1052 if (comparison_code_p (q
->code
)
1053 && swap_tree_comparison (q
) != q
)
1055 found_compare
= true;
1061 user_id
*newop
= new user_id ("<internal>");
1062 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1064 id_base
*subst
= p
->substitutes
[j
];
1065 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1067 if (comparison_code_p (q
->code
))
1068 subst
= swap_tree_comparison (q
);
1070 newop
->substitutes
.safe_push (subst
);
1072 ne
->operation
= newop
;
1073 /* Search for 'p' inside the for vector and push 'newop'
1074 to the same level. */
1075 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1076 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1077 if (for_vec
[j
][k
] == p
)
1079 for_vec
[j
].safe_push (newop
);
1085 ne
->is_commutative
= false;
1086 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1088 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1089 ne
->append_op (result
[i
][old_j
]);
1097 /* Lower operations marked as commutative in the AST of S and push
1098 the resulting patterns to SIMPLIFIERS. */
1101 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1103 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1104 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1106 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1107 s
->for_vec
, s
->capture_ids
);
1108 simplifiers
.safe_push (ns
);
1112 /* Strip conditional operations using group GRP from O and its
1113 children if STRIP, else replace them with an unconditional operation. */
1116 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1118 if (capture
*c
= dyn_cast
<capture
*> (o
))
1121 return new capture (c
->location
, c
->where
,
1122 lower_opt (c
->what
, grp
, strip
),
1128 expr
*e
= dyn_cast
<expr
*> (o
);
1132 if (e
->opt_grp
== grp
)
1135 return lower_opt (e
->ops
[0], grp
, strip
);
1137 expr
*ne
= new expr (e
);
1139 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1143 expr
*ne
= new expr (e
);
1144 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1145 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1150 /* Determine whether O or its children uses the conditional operation
1154 has_opt (operand
*o
, unsigned char grp
)
1156 if (capture
*c
= dyn_cast
<capture
*> (o
))
1159 return has_opt (c
->what
, grp
);
1164 expr
*e
= dyn_cast
<expr
*> (o
);
1168 if (e
->opt_grp
== grp
)
1171 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1172 if (has_opt (e
->ops
[i
], grp
))
1178 /* Lower conditional convert operators in O, expanding it to a vector
1181 static vec
<operand
*>
1182 lower_opt (operand
*o
)
1184 vec
<operand
*> v1
= vNULL
, v2
;
1188 /* Conditional operations are lowered to a pattern with the
1189 operation and one without. All different conditional operation
1190 groups are lowered separately. */
1192 for (unsigned i
= 1; i
<= 10; ++i
)
1195 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1196 if (has_opt (v1
[j
], i
))
1198 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1199 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1205 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1206 v1
.safe_push (v2
[j
]);
1213 /* Lower conditional convert operators in the AST of S and push
1214 the resulting multiple patterns to SIMPLIFIERS. */
1217 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1219 vec
<operand
*> matchers
= lower_opt (s
->match
);
1220 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1222 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1223 s
->for_vec
, s
->capture_ids
);
1224 simplifiers
.safe_push (ns
);
1228 /* Lower the compare operand of COND_EXPRs to a
1229 GENERIC and a GIMPLE variant. */
1231 static vec
<operand
*>
1232 lower_cond (operand
*o
)
1234 vec
<operand
*> ro
= vNULL
;
1236 if (capture
*c
= dyn_cast
<capture
*> (o
))
1240 vec
<operand
*> lop
= vNULL
;
1241 lop
= lower_cond (c
->what
);
1243 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1244 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1250 expr
*e
= dyn_cast
<expr
*> (o
);
1251 if (!e
|| e
->ops
.length () == 0)
1257 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1258 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1259 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1261 auto_vec
< vec
<operand
*> > result
;
1262 auto_vec
<operand
*> v (e
->ops
.length ());
1263 v
.quick_grow_cleared (e
->ops
.length ());
1264 cartesian_product (ops_vector
, result
, v
, 0);
1266 for (unsigned i
= 0; i
< result
.length (); ++i
)
1268 expr
*ne
= new expr (e
);
1269 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1270 ne
->append_op (result
[i
][j
]);
1272 /* If this is a COND with a captured expression or an
1273 expression with two operands then also match a GENERIC
1274 form on the compare. */
1275 if (*e
->operation
== COND_EXPR
1276 && ((is_a
<capture
*> (e
->ops
[0])
1277 && as_a
<capture
*> (e
->ops
[0])->what
1278 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1280 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1281 || (is_a
<expr
*> (e
->ops
[0])
1282 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1285 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1286 ne
->append_op (result
[i
][j
]);
1287 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1289 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1290 expr
*cmp
= new expr (ocmp
);
1291 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1292 cmp
->append_op (ocmp
->ops
[j
]);
1293 cmp
->is_generic
= true;
1294 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1299 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1300 expr
*cmp
= new expr (ocmp
);
1301 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1302 cmp
->append_op (ocmp
->ops
[j
]);
1303 cmp
->is_generic
= true;
1313 /* Lower the compare operand of COND_EXPRs to a
1314 GENERIC and a GIMPLE variant. */
1317 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1319 vec
<operand
*> matchers
= lower_cond (s
->match
);
1320 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1322 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1323 s
->for_vec
, s
->capture_ids
);
1324 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1325 simplifiers
.safe_push (ns
);
1329 /* Return true if O refers to ID. */
1332 contains_id (operand
*o
, user_id
*id
)
1334 if (capture
*c
= dyn_cast
<capture
*> (o
))
1335 return c
->what
&& contains_id (c
->what
, id
);
1337 if (expr
*e
= dyn_cast
<expr
*> (o
))
1339 if (e
->operation
== id
)
1341 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1342 if (contains_id (e
->ops
[i
], id
))
1347 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1348 return (contains_id (w
->with
, id
)
1349 || contains_id (w
->subexpr
, id
));
1351 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1352 return (contains_id (ife
->cond
, id
)
1353 || contains_id (ife
->trueexpr
, id
)
1354 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1356 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1357 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1363 /* In AST operand O replace operator ID with operator WITH. */
1366 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1368 /* Deep-copy captures and expressions, replacing operations as
1370 if (capture
*c
= dyn_cast
<capture
*> (o
))
1374 return new capture (c
->location
, c
->where
,
1375 replace_id (c
->what
, id
, with
), c
->value_match
);
1377 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1379 expr
*ne
= new expr (e
);
1380 if (e
->operation
== id
)
1381 ne
->operation
= with
;
1382 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1383 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1386 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1388 with_expr
*nw
= new with_expr (w
->location
);
1389 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1390 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1393 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1395 if_expr
*nife
= new if_expr (ife
->location
);
1396 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1397 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1399 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1403 /* For c_expr we simply record a string replacement table which is
1404 applied at code-generation time. */
1405 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1407 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1408 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1409 return new c_expr (ce
->r
, ce
->location
,
1410 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1416 /* Return true if the binary operator OP is ok for delayed substitution
1417 during for lowering. */
1420 binary_ok (operator_id
*op
)
1427 case TRUNC_DIV_EXPR
:
1429 case FLOOR_DIV_EXPR
:
1430 case ROUND_DIV_EXPR
:
1431 case TRUNC_MOD_EXPR
:
1433 case FLOOR_MOD_EXPR
:
1434 case ROUND_MOD_EXPR
:
1436 case EXACT_DIV_EXPR
:
1448 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1451 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1453 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1454 unsigned worklist_start
= 0;
1455 auto_vec
<simplify
*> worklist
;
1456 worklist
.safe_push (sin
);
1458 /* Lower each recorded for separately, operating on the
1459 set of simplifiers created by the previous one.
1460 Lower inner-to-outer so inner for substitutes can refer
1461 to operators replaced by outer fors. */
1462 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1464 vec
<user_id
*>& ids
= for_vec
[fi
];
1465 unsigned n_ids
= ids
.length ();
1466 unsigned max_n_opers
= 0;
1467 bool can_delay_subst
= true;
1468 for (unsigned i
= 0; i
< n_ids
; ++i
)
1470 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1471 max_n_opers
= ids
[i
]->substitutes
.length ();
1472 /* Require that all substitutes are of the same kind so that
1473 if we delay substitution to the result op code generation
1474 can look at the first substitute for deciding things like
1475 types of operands. */
1476 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1477 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1478 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1479 can_delay_subst
= false;
1480 else if (operator_id
*op
1481 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1484 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1485 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1486 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1488 /* Unfortunately we can't just allow all tcc_binary. */
1489 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1490 && strcmp (op0
->tcc
, "tcc_binary") == 0
1494 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1495 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1496 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1497 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1500 can_delay_subst
= false;
1502 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1505 can_delay_subst
= false;
1507 if (sin
->kind
== simplify::MATCH
1511 unsigned worklist_end
= worklist
.length ();
1512 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1514 simplify
*s
= worklist
[si
];
1515 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1517 operand
*match_op
= s
->match
;
1518 operand
*result_op
= s
->result
;
1519 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1521 for (unsigned i
= 0; i
< n_ids
; ++i
)
1523 user_id
*id
= ids
[i
];
1524 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1526 && (contains_id (match_op
, id
)
1527 || contains_id (result_op
, id
)))
1532 subst
.quick_push (std::make_pair (id
, oper
));
1533 if (sin
->kind
== simplify::SIMPLIFY
1534 || !can_delay_subst
)
1535 match_op
= replace_id (match_op
, id
, oper
);
1537 && !can_delay_subst
)
1538 result_op
= replace_id (result_op
, id
, oper
);
1543 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1544 vNULL
, s
->capture_ids
);
1545 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1548 ns
->for_subst_vec
.safe_splice (subst
);
1550 worklist
.safe_push (ns
);
1553 worklist_start
= worklist_end
;
1556 /* Copy out the result from the last for lowering. */
1557 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1558 simplifiers
.safe_push (worklist
[i
]);
1561 /* Lower the AST for everything in SIMPLIFIERS. */
1564 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1566 auto_vec
<simplify
*> out_simplifiers
;
1567 for (auto s
: simplifiers
)
1568 lower_opt (s
, out_simplifiers
);
1570 simplifiers
.truncate (0);
1571 for (auto s
: out_simplifiers
)
1572 lower_commutative (s
, simplifiers
);
1574 /* Lower for needs to happen before lowering cond
1575 to support (for cnd (cond vec_cond)). This is
1576 safe as substitution delay does not happen for
1577 cond or vec_cond. */
1578 out_simplifiers
.truncate (0);
1579 for (auto s
: simplifiers
)
1580 lower_for (s
, out_simplifiers
);
1582 simplifiers
.truncate (0);
1584 for (auto s
: out_simplifiers
)
1585 lower_cond (s
, simplifiers
);
1587 simplifiers
.safe_splice (out_simplifiers
);
1593 /* The decision tree built for generating GIMPLE and GENERIC pattern
1594 matching code. It represents the 'match' expression of all
1595 simplifies and has those as its leafs. */
1599 /* A hash-map collecting semantically equivalent leafs in the decision
1600 tree for splitting out to separate functions. */
1609 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1612 static inline hashval_t
hash (const key_type
&);
1613 static inline bool equal_keys (const key_type
&, const key_type
&);
1614 template <typename T
> static inline void remove (T
&) {}
1617 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1620 /* Current simplifier ID we are processing during insertion into the
1622 static unsigned current_id
;
1624 /* Decision tree base class, used for DT_NODE. */
1629 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1634 vec
<dt_node
*> kids
;
1638 unsigned total_size
;
1641 dt_node (enum dt_type type_
, dt_node
*parent_
)
1642 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1644 dt_node
*append_node (dt_node
*);
1645 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1646 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1647 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1649 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1651 virtual void gen (FILE *, int, bool, int) {}
1653 void gen_kids (FILE *, int, bool, int);
1654 void gen_kids_1 (FILE *, int, bool, int,
1655 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1656 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1657 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1659 void analyze (sinfo_map_t
&);
1662 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1664 class dt_operand
: public dt_node
1668 dt_operand
*match_dop
;
1673 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1674 dt_operand
*parent_
, unsigned pos_
)
1675 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1676 pos (pos_
), value_match (false), for_id (current_id
) {}
1678 void gen (FILE *, int, bool, int) final override
;
1679 unsigned gen_predicate (FILE *, int, const char *, bool);
1680 unsigned gen_match_op (FILE *, int, const char *, bool);
1682 unsigned gen_gimple_expr (FILE *, int, int);
1683 unsigned gen_generic_expr (FILE *, int, const char *);
1685 char *get_name (char *);
1686 void gen_opname (char *, unsigned);
1689 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1691 class dt_simplify
: public dt_node
1695 unsigned pattern_no
;
1696 dt_operand
**indexes
;
1699 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1700 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1701 indexes (indexes_
), info (NULL
) {}
1703 void gen_1 (FILE *, int, bool, operand
*);
1704 void gen (FILE *f
, int, bool, int) final override
;
1710 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1712 return (n
->type
== dt_node::DT_OPERAND
1713 || n
->type
== dt_node::DT_MATCH
1714 || n
->type
== dt_node::DT_TRUE
);
1720 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1722 return n
->type
== dt_node::DT_SIMPLIFY
;
1727 /* A container for the actual decision tree. */
1734 void insert (class simplify
*, unsigned);
1735 void gen (FILE *f
, bool gimple
);
1736 void print (FILE *f
= stderr
);
1738 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1740 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1741 unsigned pos
= 0, dt_node
*parent
= 0);
1742 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1743 static bool cmp_node (dt_node
*, dt_node
*);
1744 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1747 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1750 cmp_operand (operand
*o1
, operand
*o2
)
1752 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1755 if (o1
->type
== operand::OP_PREDICATE
)
1757 predicate
*p1
= as_a
<predicate
*>(o1
);
1758 predicate
*p2
= as_a
<predicate
*>(o2
);
1759 return p1
->p
== p2
->p
;
1761 else if (o1
->type
== operand::OP_EXPR
)
1763 expr
*e1
= static_cast<expr
*>(o1
);
1764 expr
*e2
= static_cast<expr
*>(o2
);
1765 return (e1
->operation
== e2
->operation
1766 && e1
->is_generic
== e2
->is_generic
);
1772 /* Compare two decision tree nodes N1 and N2 and return true if they
1776 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1778 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1784 if (n1
->type
== dt_node::DT_TRUE
)
1787 if (n1
->type
== dt_node::DT_OPERAND
)
1788 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1789 (as_a
<dt_operand
*> (n2
))->op
);
1790 else if (n1
->type
== dt_node::DT_MATCH
)
1791 return (((as_a
<dt_operand
*> (n1
))->match_dop
1792 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1793 && ((as_a
<dt_operand
*> (n1
))->value_match
1794 == (as_a
<dt_operand
*> (n2
))->value_match
));
1798 /* Search OPS for a decision tree node like P and return it if found. */
1801 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1803 /* We can merge adjacent DT_TRUE. */
1804 if (p
->type
== dt_node::DT_TRUE
1806 && ops
.last ()->type
== dt_node::DT_TRUE
)
1808 dt_operand
*true_node
= NULL
;
1809 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1811 /* But we can't merge across DT_TRUE nodes as they serve as
1812 pattern order barriers to make sure that patterns apply
1813 in order of appearance in case multiple matches are possible. */
1814 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1817 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1818 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1820 if (decision_tree::cmp_node (ops
[i
], p
))
1822 /* Unless we are processing the same pattern or the blocking
1823 pattern is before the one we are going to merge with. */
1825 && true_node
->for_id
!= current_id
1826 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1830 location_t p_loc
= 0;
1831 if (p
->type
== dt_node::DT_OPERAND
)
1832 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1833 location_t op_loc
= 0;
1834 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1835 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1836 location_t true_loc
= 0;
1837 true_loc
= true_node
->op
->location
;
1839 "failed to merge decision tree node");
1841 "with the following");
1842 warning_at (true_loc
,
1843 "because of the following which serves as ordering "
1854 /* Append N to the decision tree if it there is not already an existing
1858 dt_node::append_node (dt_node
*n
)
1862 kid
= decision_tree::find_node (kids
, n
);
1867 n
->level
= this->level
+ 1;
1872 /* Append OP to the decision tree. */
1875 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1877 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1878 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1879 return append_node (n
);
1882 /* Append a DT_TRUE decision tree node. */
1885 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1887 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1888 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1889 return append_node (n
);
1892 /* Append a DT_MATCH decision tree node. */
1895 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1896 dt_node
*parent
, unsigned pos
)
1898 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1899 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1900 return append_node (n
);
1903 /* Append S to the decision tree. */
1906 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1907 dt_operand
**indexes
)
1910 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1911 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1912 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1914 || s
->match
->location
!= s2
->s
->match
->location
))
1916 /* With a nested patters, it's hard to avoid these in order
1917 to keep match.pd rules relatively small. */
1918 warning_at (s
->match
->location
, "duplicate pattern");
1919 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1920 print_operand (s
->match
, stderr
);
1921 fprintf (stderr
, "\n");
1923 return append_node (n
);
1926 /* Analyze the node and its children. */
1929 dt_node::analyze (sinfo_map_t
&map
)
1935 if (type
== DT_SIMPLIFY
)
1937 /* Populate the map of equivalent simplifies. */
1938 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1940 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1955 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1957 kids
[i
]->analyze (map
);
1958 num_leafs
+= kids
[i
]->num_leafs
;
1959 total_size
+= kids
[i
]->total_size
;
1960 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1964 /* Insert O into the decision tree and return the decision tree node found
1968 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1969 unsigned pos
, dt_node
*parent
)
1971 dt_node
*q
, *elm
= 0;
1973 if (capture
*c
= dyn_cast
<capture
*> (o
))
1975 unsigned capt_index
= c
->where
;
1977 if (indexes
[capt_index
] == 0)
1980 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1983 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1986 // get to the last capture
1987 for (operand
*what
= c
->what
;
1988 what
&& is_a
<capture
*> (what
);
1989 c
= as_a
<capture
*> (what
), what
= c
->what
)
1994 unsigned cc_index
= c
->where
;
1995 dt_operand
*match_op
= indexes
[cc_index
];
1997 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1998 elm
= decision_tree::find_node (p
->kids
, &temp
);
2002 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
2003 match
.value_match
= c
->value_match
;
2004 elm
= decision_tree::find_node (p
->kids
, &match
);
2009 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
2010 elm
= decision_tree::find_node (p
->kids
, &temp
);
2014 gcc_assert (elm
->type
== dt_node::DT_TRUE
2015 || elm
->type
== dt_node::DT_OPERAND
2016 || elm
->type
== dt_node::DT_MATCH
);
2017 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2022 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2023 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2025 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2030 p
= p
->append_op (o
, parent
, pos
);
2033 if (expr
*e
= dyn_cast
<expr
*>(o
))
2035 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2036 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2042 /* Insert S into the decision tree. */
2045 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2048 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2049 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2050 p
->append_simplify (s
, pattern_no
, indexes
);
2053 /* Debug functions to dump the decision tree. */
2056 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2058 if (p
->type
== dt_node::DT_NODE
)
2059 fprintf (f
, "root");
2063 for (unsigned i
= 0; i
< indent
; i
++)
2066 if (p
->type
== dt_node::DT_OPERAND
)
2068 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2069 print_operand (dop
->op
, f
, true);
2071 else if (p
->type
== dt_node::DT_TRUE
)
2072 fprintf (f
, "true");
2073 else if (p
->type
== dt_node::DT_MATCH
)
2074 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2075 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2077 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2078 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2079 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2080 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2083 if (is_a
<dt_operand
*> (p
))
2084 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2087 fprintf (stderr
, " (%p, %p), %u, %u\n",
2088 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2090 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2091 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2095 decision_tree::print (FILE *f
)
2097 return decision_tree::print_node (root
, f
);
2101 /* For GENERIC we have to take care of wrapping multiple-used
2102 expressions with side-effects in save_expr and preserve side-effects
2103 of expressions with omit_one_operand. Analyze captures in
2104 match, result and with expressions and perform early-outs
2105 on the outermost match expression operands for cases we cannot
2111 capture_info (simplify
*s
, operand
*, bool);
2112 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2113 bool walk_result (operand
*o
, bool, operand
*);
2114 void walk_c_expr (c_expr
*);
2120 bool force_no_side_effects_p
;
2121 bool force_single_use
;
2122 bool cond_expr_cond_p
;
2123 unsigned long toplevel_msk
;
2124 unsigned match_use_count
;
2125 unsigned result_use_count
;
2130 auto_vec
<cinfo
> info
;
2131 unsigned long force_no_side_effects
;
2135 /* Analyze captures in S. */
2137 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2142 if (s
->kind
== simplify::MATCH
)
2144 force_no_side_effects
= -1;
2148 force_no_side_effects
= 0;
2149 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2150 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2151 info
[i
].same_as
= i
;
2153 e
= as_a
<expr
*> (s
->match
);
2154 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2155 walk_match (e
->ops
[i
], i
,
2156 (i
!= 0 && *e
->operation
== COND_EXPR
)
2157 || *e
->operation
== TRUTH_ANDIF_EXPR
2158 || *e
->operation
== TRUTH_ORIF_EXPR
,
2159 i
== 0 && *e
->operation
== COND_EXPR
);
2161 walk_result (s
->result
, false, result
);
2164 /* Analyze captures in the match expression piece O. */
2167 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2168 bool conditional_p
, bool cond_expr_cond_p
)
2170 if (capture
*c
= dyn_cast
<capture
*> (o
))
2172 unsigned where
= c
->where
;
2173 info
[where
].match_use_count
++;
2174 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2175 info
[where
].force_no_side_effects_p
|= conditional_p
;
2176 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2181 /* Recurse to exprs and captures. */
2182 if (is_a
<capture
*> (c
->what
)
2183 || is_a
<expr
*> (c
->what
))
2184 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2185 /* We need to look past multiple captures to find a captured
2186 expression as with conditional converts two captures
2187 can be collapsed onto the same expression. Also collect
2188 what captures capture the same thing. */
2189 while (c
->what
&& is_a
<capture
*> (c
->what
))
2191 c
= as_a
<capture
*> (c
->what
);
2192 if (info
[c
->where
].same_as
!= c
->where
2193 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2194 fatal_at (c
->location
, "cannot handle this collapsed capture");
2195 info
[c
->where
].same_as
= info
[where
].same_as
;
2197 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2200 && (e
= dyn_cast
<expr
*> (c
->what
)))
2202 /* Zero-operand expression captures like ADDR_EXPR@0 are
2203 similar as predicates -- if they are not mentioned in
2204 the result we have to force them to have no side-effects. */
2205 if (e
->ops
.length () != 0)
2206 info
[where
].expr_p
= true;
2207 info
[where
].force_single_use
|= e
->force_single_use
;
2210 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2212 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2214 bool cond_p
= conditional_p
;
2215 bool expr_cond_p
= false;
2216 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2218 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2219 || *e
->operation
== TRUTH_ORIF_EXPR
)
2222 && *e
->operation
== COND_EXPR
)
2224 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2227 else if (is_a
<predicate
*> (o
))
2229 /* Mark non-captured leafs toplevel arg for checking. */
2230 force_no_side_effects
|= 1 << toplevel_arg
;
2233 warning_at (o
->location
,
2234 "forcing no side-effects on possibly lost leaf");
2240 /* Analyze captures in the result expression piece O. Return true
2241 if RESULT was visited in one of the children. Only visit
2242 non-if/with children if they are rooted on RESULT. */
2245 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2247 if (capture
*c
= dyn_cast
<capture
*> (o
))
2249 unsigned where
= info
[c
->where
].same_as
;
2250 info
[where
].result_use_count
++;
2251 /* If we substitute an expression capture we don't know
2252 which captures this will end up using (well, we don't
2253 compute that). Force the uses to be side-effect free
2254 which means forcing the toplevels that reach the
2255 expression side-effect free. */
2256 if (info
[where
].expr_p
)
2257 force_no_side_effects
|= info
[where
].toplevel_msk
;
2258 /* Mark CSE capture uses as forced to have no side-effects. */
2260 && is_a
<expr
*> (c
->what
))
2262 info
[where
].cse_p
= true;
2263 walk_result (c
->what
, true, result
);
2266 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2268 id_base
*opr
= e
->operation
;
2269 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2270 opr
= uid
->substitutes
[0];
2271 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2273 bool cond_p
= conditional_p
;
2274 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2276 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2277 || *e
->operation
== TRUTH_ORIF_EXPR
)
2279 walk_result (e
->ops
[i
], cond_p
, result
);
2282 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2284 /* 'if' conditions should be all fine. */
2285 if (ie
->trueexpr
== result
)
2287 walk_result (ie
->trueexpr
, false, result
);
2290 if (ie
->falseexpr
== result
)
2292 walk_result (ie
->falseexpr
, false, result
);
2296 if (is_a
<if_expr
*> (ie
->trueexpr
)
2297 || is_a
<with_expr
*> (ie
->trueexpr
))
2298 res
|= walk_result (ie
->trueexpr
, false, result
);
2300 && (is_a
<if_expr
*> (ie
->falseexpr
)
2301 || is_a
<with_expr
*> (ie
->falseexpr
)))
2302 res
|= walk_result (ie
->falseexpr
, false, result
);
2305 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2307 bool res
= (we
->subexpr
== result
);
2309 || is_a
<if_expr
*> (we
->subexpr
)
2310 || is_a
<with_expr
*> (we
->subexpr
))
2311 res
|= walk_result (we
->subexpr
, false, result
);
2313 walk_c_expr (we
->with
);
2316 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2324 /* Look for captures in the C expr E. */
2327 capture_info::walk_c_expr (c_expr
*e
)
2329 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2330 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2331 really escape through. */
2332 unsigned p_depth
= 0;
2333 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2335 const cpp_token
*t
= &e
->code
[i
];
2336 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2338 if (t
->type
== CPP_NAME
2339 && (strcmp ((const char *)CPP_HASHNODE
2340 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2341 || strcmp ((const char *)CPP_HASHNODE
2342 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2343 || strcmp ((const char *)CPP_HASHNODE
2344 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2345 || ((id
= get_operator ((const char *)CPP_HASHNODE
2346 (t
->val
.node
.node
)->ident
.str
))
2347 && is_a
<predicate_id
*> (id
)))
2348 && n
->type
== CPP_OPEN_PAREN
)
2350 else if (t
->type
== CPP_CLOSE_PAREN
2353 else if (p_depth
== 0
2354 && t
->type
== CPP_ATSIGN
2355 && (n
->type
== CPP_NUMBER
2356 || n
->type
== CPP_NAME
)
2357 && !(n
->flags
& PREV_WHITE
))
2360 if (n
->type
== CPP_NUMBER
)
2361 id1
= (const char *)n
->val
.str
.text
;
2363 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2364 unsigned *where
= e
->capture_ids
->get(id1
);
2366 fatal_at (n
, "unknown capture id '%s'", id1
);
2367 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2370 warning_at (t
, "capture escapes");
2376 /* The current label failing the current matched pattern during
2378 static char *fail_label
;
2380 /* Code generation off the decision tree and the refered AST nodes. */
2383 is_conversion (id_base
*op
)
2385 return (*op
== CONVERT_EXPR
2387 || *op
== FLOAT_EXPR
2388 || *op
== FIX_TRUNC_EXPR
2389 || *op
== VIEW_CONVERT_EXPR
);
2392 /* Get the type to be used for generating operand POS of OP from the
2396 get_operand_type (id_base
*op
, unsigned pos
,
2397 const char *in_type
,
2398 const char *expr_type
,
2399 const char *other_oprnd_type
)
2401 /* Generally operands whose type does not match the type of the
2402 expression generated need to know their types but match and
2403 thus can fall back to 'other_oprnd_type'. */
2404 if (is_conversion (op
))
2405 return other_oprnd_type
;
2406 else if (*op
== REALPART_EXPR
2407 || *op
== IMAGPART_EXPR
)
2408 return other_oprnd_type
;
2409 else if (is_a
<operator_id
*> (op
)
2410 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2411 return other_oprnd_type
;
2412 else if (*op
== COND_EXPR
2414 return "boolean_type_node";
2415 else if (startswith (op
->id
, "CFN_COND_"))
2417 /* IFN_COND_* operands 1 and later by default have the same type
2418 as the result. The type of operand 0 needs to be specified
2420 if (pos
> 0 && expr_type
)
2422 else if (pos
> 0 && in_type
)
2429 /* Otherwise all types should match - choose one in order of
2436 return other_oprnd_type
;
2440 /* Generate transform code for an expression. */
2443 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2444 int depth
, const char *in_type
, capture_info
*cinfo
,
2445 dt_operand
**indexes
, int)
2447 id_base
*opr
= operation
;
2448 /* When we delay operator substituting during lowering of fors we
2449 make sure that for code-gen purposes the effects of each substitute
2450 are the same. Thus just look at that. */
2451 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2452 opr
= uid
->substitutes
[0];
2454 bool conversion_p
= is_conversion (opr
);
2455 const char *type
= expr_type
;
2458 /* If there was a type specification in the pattern use it. */
2460 else if (conversion_p
)
2461 /* For conversions we need to build the expression using the
2462 outer type passed in. */
2464 else if (*opr
== REALPART_EXPR
2465 || *opr
== IMAGPART_EXPR
)
2467 /* __real and __imag use the component type of its operand. */
2468 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2472 else if (is_a
<operator_id
*> (opr
)
2473 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2475 /* comparisons use boolean_type_node (or what gets in), but
2476 their operands need to figure out the types themselves. */
2481 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2486 else if (*opr
== COND_EXPR
2487 || *opr
== VEC_COND_EXPR
2488 || startswith (opr
->id
, "CFN_COND_"))
2490 /* Conditions are of the same type as their first alternative. */
2491 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2496 /* Other operations are of the same type as their first operand. */
2497 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2501 fatal_at (location
, "cannot determine type of operand");
2503 fprintf_indent (f
, indent
, "{\n");
2505 fprintf_indent (f
, indent
,
2506 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2508 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2509 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2512 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2514 = get_operand_type (opr
, i
, in_type
, expr_type
,
2515 i
== 0 ? NULL
: op0type
);
2516 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2518 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2521 const char *opr_name
;
2522 if (*operation
== CONVERT_EXPR
)
2523 opr_name
= "NOP_EXPR";
2525 opr_name
= operation
->id
;
2529 if (*opr
== CONVERT_EXPR
)
2531 fprintf_indent (f
, indent
,
2532 "if (%s != TREE_TYPE (_o%d[0])\n",
2534 fprintf_indent (f
, indent
,
2535 " && !useless_type_conversion_p (%s, TREE_TYPE "
2538 fprintf_indent (f
, indent
+ 2, "{\n");
2541 /* ??? Building a stmt can fail for various reasons here, seq being
2542 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2543 So if we fail here we should continue matching other patterns. */
2544 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2545 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2546 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2547 fprintf (f
, ", _o%d[%u]", depth
, i
);
2548 fprintf (f
, ");\n");
2549 fprintf_indent (f
, indent
, "tem_op.resimplify (%s, valueize);\n",
2550 !force_leaf
? "lseq" : "NULL");
2551 fprintf_indent (f
, indent
,
2552 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2553 !force_leaf
? "lseq" : "NULL");
2554 fprintf_indent (f
, indent
,
2555 "if (!_r%d) goto %s;\n",
2557 if (*opr
== CONVERT_EXPR
)
2560 fprintf_indent (f
, indent
, " }\n");
2561 fprintf_indent (f
, indent
, "else\n");
2562 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2567 if (*opr
== CONVERT_EXPR
)
2569 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2573 if (opr
->kind
== id_base::CODE
)
2574 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2575 depth
, ops
.length(), opr_name
, type
);
2577 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2578 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2579 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2580 fprintf (f
, ", _o%d[%u]", depth
, i
);
2581 fprintf (f
, ");\n");
2582 if (opr
->kind
!= id_base::CODE
)
2584 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2585 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2589 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2590 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2592 if (*opr
== CONVERT_EXPR
)
2595 fprintf_indent (f
, indent
, "else\n");
2596 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2599 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2601 fprintf_indent (f
, indent
, "}\n");
2604 /* Generate code for a c_expr which is either the expression inside
2605 an if statement or a sequence of statements which computes a
2606 result to be stored to DEST. */
2609 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2610 bool, int, const char *, capture_info
*,
2613 if (dest
&& nr_stmts
== 1)
2614 fprintf_indent (f
, indent
, "%s = ", dest
);
2616 unsigned stmt_nr
= 1;
2618 for (unsigned i
= 0; i
< code
.length (); ++i
)
2620 const cpp_token
*token
= &code
[i
];
2622 /* We can't recover from all lexing losses but we can roughly restore line
2623 breaks from location info. */
2624 const line_map_ordinary
*map
;
2625 linemap_resolve_location (line_table
, token
->src_loc
,
2626 LRK_SPELLING_LOCATION
, &map
);
2627 expanded_location loc
= linemap_expand_location (line_table
, map
,
2629 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2631 prev_line
= loc
.line
;
2633 /* Replace captures for code-gen. */
2634 if (token
->type
== CPP_ATSIGN
)
2636 const cpp_token
*n
= &code
[i
+1];
2637 if ((n
->type
== CPP_NUMBER
2638 || n
->type
== CPP_NAME
)
2639 && !(n
->flags
& PREV_WHITE
))
2641 if (token
->flags
& PREV_WHITE
)
2644 if (n
->type
== CPP_NUMBER
)
2645 id
= (const char *)n
->val
.str
.text
;
2647 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2648 unsigned *cid
= capture_ids
->get (id
);
2650 fatal_at (token
, "unknown capture id");
2651 fprintf (f
, "captures[%u]", *cid
);
2657 if (token
->flags
& PREV_WHITE
)
2660 if (token
->type
== CPP_NAME
)
2662 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2664 for (j
= 0; j
< ids
.length (); ++j
)
2666 if (strcmp (id
, ids
[j
].id
) == 0)
2668 fprintf (f
, "%s", ids
[j
].oper
);
2672 if (j
< ids
.length ())
2676 /* Output the token as string. */
2677 char *tk
= (char *)cpp_token_as_text (r
, token
);
2680 if (token
->type
== CPP_SEMICOLON
)
2683 if (dest
&& stmt_nr
== nr_stmts
)
2684 fprintf_indent (f
, indent
, "%s = ", dest
);
2690 /* Generate transform code for a capture. */
2693 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2694 int depth
, const char *in_type
, capture_info
*cinfo
,
2695 dt_operand
**indexes
, int cond_handling
)
2697 if (what
&& is_a
<expr
*> (what
))
2699 if (indexes
[where
] == 0)
2702 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2703 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2708 /* If in GENERIC some capture is used multiple times, unshare it except
2709 when emitting the last use. */
2711 && cinfo
->info
.exists ()
2712 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2714 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2716 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2719 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2721 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2722 with substituting a capture of that. */
2724 && cond_handling
!= 0
2725 && cinfo
->info
[where
].cond_expr_cond_p
)
2727 /* If substituting into a cond_expr condition, unshare. */
2728 if (cond_handling
== 1)
2729 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2730 /* If substituting elsewhere we might need to decompose it. */
2731 else if (cond_handling
== 2)
2733 /* ??? Returning false here will also not allow any other patterns
2734 to match unless this generator was split out. */
2735 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2736 fprintf_indent (f
, indent
, " {\n");
2737 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2738 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2740 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2741 " TREE_OPERAND (%s, 1));\n",
2742 dest
, dest
, dest
, dest
, dest
);
2743 fprintf_indent (f
, indent
, " }\n");
2748 /* Return the name of the operand representing the decision tree node.
2749 Use NAME as space to generate it. */
2752 dt_operand::get_name (char *name
)
2755 sprintf (name
, "t");
2756 else if (parent
->level
== 1)
2757 sprintf (name
, "_p%u", pos
);
2758 else if (parent
->type
== dt_node::DT_MATCH
)
2759 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2761 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2765 /* Fill NAME with the operand name at position POS. */
2768 dt_operand::gen_opname (char *name
, unsigned pos
)
2771 sprintf (name
, "_p%u", pos
);
2773 sprintf (name
, "_q%u%u", level
, pos
);
2776 /* Generate matching code for the decision tree operand which is
2780 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2782 predicate
*p
= as_a
<predicate
*> (op
);
2784 if (p
->p
->matchers
.exists ())
2786 /* If this is a predicate generated from a pattern mangle its
2787 name and pass on the valueize hook. */
2789 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2792 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2795 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2796 fprintf_indent (f
, indent
+ 2, "{\n");
2800 /* Generate matching code for the decision tree operand which is
2804 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2806 char match_opname
[20];
2807 match_dop
->get_name (match_opname
);
2809 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2810 "|| operand_equal_p (%s, %s, 0))\n",
2811 opname
, match_opname
, opname
, opname
, match_opname
);
2813 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2814 "|| (operand_equal_p (%s, %s, 0) "
2815 "&& types_match (%s, %s)))\n",
2816 opname
, match_opname
, opname
, opname
, match_opname
,
2817 opname
, match_opname
);
2818 fprintf_indent (f
, indent
+ 2, "{\n");
2822 /* Generate GIMPLE matching code for the decision tree operand. */
2825 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2827 expr
*e
= static_cast<expr
*> (op
);
2828 id_base
*id
= e
->operation
;
2829 unsigned n_ops
= e
->ops
.length ();
2830 unsigned n_braces
= 0;
2832 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2833 id
= u
->substitutes
[0];
2835 for (unsigned i
= 0; i
< n_ops
; ++i
)
2837 char child_opname
[20];
2838 gen_opname (child_opname
, i
);
2840 if (id
->kind
== id_base::CODE
)
2843 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2844 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2846 /* ??? If this is a memory operation we can't (and should not)
2847 match this. The only sensible operand types are
2848 SSA names and invariants. */
2853 fprintf_indent (f
, indent
,
2854 "tree %s = TREE_OPERAND (%s, %i);\n",
2855 child_opname
, opname
, i
);
2858 fprintf_indent (f
, indent
,
2859 "tree %s = TREE_OPERAND "
2860 "(gimple_assign_rhs1 (_a%d), %i);\n",
2861 child_opname
, depth
, i
);
2862 fprintf_indent (f
, indent
,
2863 "if ((TREE_CODE (%s) == SSA_NAME\n",
2865 fprintf_indent (f
, indent
,
2866 " || is_gimple_min_invariant (%s)))\n",
2868 fprintf_indent (f
, indent
,
2872 fprintf_indent (f
, indent
,
2873 "%s = do_valueize (valueize, %s);\n",
2874 child_opname
, child_opname
);
2878 fprintf_indent (f
, indent
,
2879 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2880 child_opname
, i
+ 1, depth
);
2883 fprintf_indent (f
, indent
,
2884 "tree %s = gimple_call_arg (_c%d, %u);\n",
2885 child_opname
, depth
, i
);
2886 fprintf_indent (f
, indent
,
2887 "%s = do_valueize (valueize, %s);\n",
2888 child_opname
, child_opname
);
2890 /* While the toplevel operands are canonicalized by the caller
2891 after valueizing operands of sub-expressions we have to
2892 re-canonicalize operand order. */
2893 int opno
= commutative_op (id
);
2896 char child_opname0
[20], child_opname1
[20];
2897 gen_opname (child_opname0
, opno
);
2898 gen_opname (child_opname1
, opno
+ 1);
2899 fprintf_indent (f
, indent
,
2900 "if (tree_swap_operands_p (%s, %s))\n",
2901 child_opname0
, child_opname1
);
2902 fprintf_indent (f
, indent
,
2903 " std::swap (%s, %s);\n",
2904 child_opname0
, child_opname1
);
2910 /* Generate GENERIC matching code for the decision tree operand. */
2913 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2915 expr
*e
= static_cast<expr
*> (op
);
2916 id_base
*id
= e
->operation
;
2917 unsigned n_ops
= e
->ops
.length ();
2919 if (user_id
*u
= dyn_cast
<user_id
*> (id
))
2920 id
= u
->substitutes
[0];
2922 for (unsigned i
= 0; i
< n_ops
; ++i
)
2924 char child_opname
[20];
2925 gen_opname (child_opname
, i
);
2927 if (id
->kind
== id_base::CODE
)
2928 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2929 child_opname
, opname
, i
);
2931 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2932 child_opname
, opname
, i
);
2938 /* Generate matching code for the children of the decision tree node. */
2941 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2943 auto_vec
<dt_operand
*> gimple_exprs
;
2944 auto_vec
<dt_operand
*> generic_exprs
;
2945 auto_vec
<dt_operand
*> fns
;
2946 auto_vec
<dt_operand
*> generic_fns
;
2947 auto_vec
<dt_operand
*> preds
;
2948 auto_vec
<dt_node
*> others
;
2950 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2952 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2954 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2955 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2957 if (e
->ops
.length () == 0
2958 /* In GIMPLE a CONSTRUCTOR always appears in a
2959 separate definition. */
2960 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2962 generic_exprs
.safe_push (op
);
2963 /* But ADDR_EXPRs can appear directly when invariant
2964 and in a separate definition when not. */
2965 if (gimple
&& *e
->operation
== ADDR_EXPR
)
2966 gimple_exprs
.safe_push (op
);
2968 else if (e
->operation
->kind
== id_base::FN
)
2973 generic_fns
.safe_push (op
);
2975 else if (e
->operation
->kind
== id_base::PREDICATE
)
2976 preds
.safe_push (op
);
2979 user_id
*u
= dyn_cast
<user_id
*> (e
->operation
);
2980 if (u
&& u
->substitutes
[0]->kind
== id_base::FN
)
2985 generic_fns
.safe_push (op
);
2989 if (gimple
&& !e
->is_generic
)
2990 gimple_exprs
.safe_push (op
);
2992 generic_exprs
.safe_push (op
);
2996 else if (op
->op
->type
== operand::OP_PREDICATE
)
2997 others
.safe_push (kids
[i
]);
3001 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
3002 others
.safe_push (kids
[i
]);
3003 else if (kids
[i
]->type
== dt_node::DT_MATCH
3004 || kids
[i
]->type
== dt_node::DT_TRUE
)
3006 /* A DT_TRUE operand serves as a barrier - generate code now
3007 for what we have collected sofar.
3008 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
3009 dependent matches to get out-of-order. Generate code now
3010 for what we have collected sofar. */
3011 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3012 fns
, generic_fns
, preds
, others
);
3013 /* And output the true operand itself. */
3014 kids
[i
]->gen (f
, indent
, gimple
, depth
);
3015 gimple_exprs
.truncate (0);
3016 generic_exprs
.truncate (0);
3018 generic_fns
.truncate (0);
3020 others
.truncate (0);
3026 /* Generate code for the remains. */
3027 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
3028 fns
, generic_fns
, preds
, others
);
3031 /* Generate matching code for the children of the decision tree node. */
3034 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
3035 const vec
<dt_operand
*> &gimple_exprs
,
3036 const vec
<dt_operand
*> &generic_exprs
,
3037 const vec
<dt_operand
*> &fns
,
3038 const vec
<dt_operand
*> &generic_fns
,
3039 const vec
<dt_operand
*> &preds
,
3040 const vec
<dt_node
*> &others
)
3043 char *kid_opname
= buf
;
3045 unsigned exprs_len
= gimple_exprs
.length ();
3046 unsigned gexprs_len
= generic_exprs
.length ();
3047 unsigned fns_len
= fns
.length ();
3048 unsigned gfns_len
= generic_fns
.length ();
3050 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3053 gimple_exprs
[0]->get_name (kid_opname
);
3055 fns
[0]->get_name (kid_opname
);
3057 generic_fns
[0]->get_name (kid_opname
);
3059 generic_exprs
[0]->get_name (kid_opname
);
3061 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3062 fprintf_indent (f
, indent
, " {\n");
3066 if (exprs_len
|| fns_len
)
3069 fprintf_indent (f
, indent
,
3070 "case SSA_NAME:\n");
3071 fprintf_indent (f
, indent
,
3072 " if (gimple *_d%d = get_def (valueize, %s))\n",
3074 fprintf_indent (f
, indent
,
3079 fprintf_indent (f
, indent
,
3080 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3082 fprintf_indent (f
, indent
,
3083 " switch (gimple_assign_rhs_code (_a%d))\n",
3086 fprintf_indent (f
, indent
, "{\n");
3087 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3089 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3090 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3092 for (auto id
: u
->substitutes
)
3093 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3097 id_base
*op
= e
->operation
;
3098 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3099 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3101 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3103 fprintf_indent (f
, indent
, " {\n");
3104 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3105 fprintf_indent (f
, indent
, " break;\n");
3106 fprintf_indent (f
, indent
, " }\n");
3108 fprintf_indent (f
, indent
, "default:;\n");
3109 fprintf_indent (f
, indent
, "}\n");
3115 fprintf_indent (f
, indent
,
3116 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3117 exprs_len
? "else " : "", depth
, depth
);
3118 fprintf_indent (f
, indent
,
3119 " switch (gimple_call_combined_fn (_c%d))\n",
3123 fprintf_indent (f
, indent
, "{\n");
3124 for (unsigned i
= 0; i
< fns_len
; ++i
)
3126 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3127 if (user_id
*u
= dyn_cast
<user_id
*> (e
->operation
))
3128 for (auto id
: u
->substitutes
)
3129 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3131 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3132 /* We need to be defensive against bogus prototypes allowing
3133 calls with not enough arguments. */
3134 fprintf_indent (f
, indent
,
3135 " if (gimple_call_num_args (_c%d) == %d)\n",
3136 depth
, e
->ops
.length ());
3137 fprintf_indent (f
, indent
, " {\n");
3138 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3139 fprintf_indent (f
, indent
, " }\n");
3140 fprintf_indent (f
, indent
, " break;\n");
3143 fprintf_indent (f
, indent
, "default:;\n");
3144 fprintf_indent (f
, indent
, "}\n");
3150 fprintf_indent (f
, indent
, " }\n");
3151 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3152 here rather than in the next loop. */
3153 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3155 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3156 id_base
*op
= e
->operation
;
3157 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3159 fprintf_indent (f
, indent
+ 4, "{\n");
3160 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3161 fprintf_indent (f
, indent
+ 4, "}\n");
3165 fprintf_indent (f
, indent
, " break;\n");
3168 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3170 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3171 id_base
*op
= e
->operation
;
3172 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3173 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3174 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3175 /* Already handled above. */
3179 if (user_id
*u
= dyn_cast
<user_id
*> (op
))
3180 for (auto id
: u
->substitutes
)
3181 fprintf_indent (f
, indent
, "case %s:\n", id
->id
);
3183 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3185 fprintf_indent (f
, indent
, " {\n");
3186 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3187 fprintf_indent (f
, indent
, " break;\n");
3188 fprintf_indent (f
, indent
, " }\n");
3193 fprintf_indent (f
, indent
,
3194 "case CALL_EXPR:\n");
3195 fprintf_indent (f
, indent
,
3196 " switch (get_call_combined_fn (%s))\n",
3198 fprintf_indent (f
, indent
,
3202 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3204 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3205 gcc_assert (e
->operation
->kind
== id_base::FN
);
3207 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3208 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3209 " {\n", kid_opname
, e
->ops
.length ());
3210 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3211 fprintf_indent (f
, indent
, " }\n"
3214 fprintf_indent (f
, indent
, "default:;\n");
3217 fprintf_indent (f
, indent
, " }\n");
3218 fprintf_indent (f
, indent
, " break;\n");
3221 /* Close switch (TREE_CODE ()). */
3222 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3225 fprintf_indent (f
, indent
, " default:;\n");
3226 fprintf_indent (f
, indent
, " }\n");
3229 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3231 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3232 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3233 preds
[i
]->get_name (kid_opname
);
3234 fprintf_indent (f
, indent
, "{\n");
3236 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3237 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3238 gimple
? "gimple" : "tree",
3239 p
->id
, kid_opname
, kid_opname
,
3240 gimple
? ", valueize" : "");
3241 fprintf_indent (f
, indent
, " {\n");
3242 for (int j
= 0; j
< p
->nargs
; ++j
)
3244 char child_opname
[20];
3245 preds
[i
]->gen_opname (child_opname
, j
);
3246 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3247 child_opname
, kid_opname
, j
);
3249 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3252 fprintf_indent (f
, indent
, "}\n");
3255 for (unsigned i
= 0; i
< others
.length (); ++i
)
3256 others
[i
]->gen (f
, indent
, gimple
, depth
);
3259 /* Generate matching code for the decision tree operand. */
3262 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3267 unsigned n_braces
= 0;
3269 if (type
== DT_OPERAND
)
3272 case operand::OP_PREDICATE
:
3273 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3276 case operand::OP_EXPR
:
3278 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3280 n_braces
= gen_generic_expr (f
, indent
, opname
);
3286 else if (type
== DT_TRUE
)
3288 else if (type
== DT_MATCH
)
3289 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3293 indent
+= 4 * n_braces
;
3294 gen_kids (f
, indent
, gimple
, depth
);
3296 for (unsigned i
= 0; i
< n_braces
; ++i
)
3301 fprintf_indent (f
, indent
, " }\n");
3306 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3307 step of a '(simplify ...)' or '(match ...)'. This handles everything
3308 that is not part of the decision tree (simplify->match).
3309 Main recursive worker. */
3312 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3316 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3318 fprintf_indent (f
, indent
, "{\n");
3320 output_line_directive (f
, w
->location
);
3321 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3322 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3324 fprintf_indent (f
, indent
, "}\n");
3327 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3329 output_line_directive (f
, ife
->location
);
3330 fprintf_indent (f
, indent
, "if (");
3331 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3333 fprintf_indent (f
, indent
+ 2, "{\n");
3335 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3337 fprintf_indent (f
, indent
+ 2, "}\n");
3340 fprintf_indent (f
, indent
, "else\n");
3341 fprintf_indent (f
, indent
+ 2, "{\n");
3343 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3345 fprintf_indent (f
, indent
+ 2, "}\n");
3351 static unsigned fail_label_cnt
;
3352 char local_fail_label
[256];
3353 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3354 fail_label
= local_fail_label
;
3356 /* Analyze captures and perform early-outs on the incoming arguments
3357 that cover cases we cannot handle. */
3358 capture_info
cinfo (s
, result
, gimple
);
3359 if (s
->kind
== simplify::SIMPLIFY
)
3363 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3364 if (cinfo
.force_no_side_effects
& (1 << i
))
3366 fprintf_indent (f
, indent
,
3367 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3370 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3371 "forcing toplevel operand to have no "
3374 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3375 if (cinfo
.info
[i
].cse_p
)
3377 else if (cinfo
.info
[i
].force_no_side_effects_p
3378 && (cinfo
.info
[i
].toplevel_msk
3379 & cinfo
.force_no_side_effects
) == 0)
3381 fprintf_indent (f
, indent
,
3382 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3383 "goto %s;\n", i
, fail_label
);
3385 warning_at (cinfo
.info
[i
].c
->location
,
3386 "forcing captured operand to have no "
3389 else if ((cinfo
.info
[i
].toplevel_msk
3390 & cinfo
.force_no_side_effects
) != 0)
3391 /* Mark capture as having no side-effects if we had to verify
3392 that via forced toplevel operand checks. */
3393 cinfo
.info
[i
].force_no_side_effects_p
= true;
3397 /* Force single-use restriction by only allowing simple
3398 results via setting seq to NULL. */
3399 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3400 bool first_p
= true;
3401 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3402 if (cinfo
.info
[i
].force_single_use
)
3406 fprintf_indent (f
, indent
, "if (lseq\n");
3407 fprintf_indent (f
, indent
, " && (");
3413 fprintf_indent (f
, indent
, " || ");
3415 fprintf (f
, "!single_use (captures[%d])", i
);
3419 fprintf (f
, "))\n");
3420 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3425 if (s
->kind
== simplify::SIMPLIFY
)
3426 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3428 fprintf_indent (f
, indent
, "if (UNLIKELY (dump_file && (dump_flags & TDF_FOLDING))) "
3429 "fprintf (dump_file, \"%s ",
3430 s
->kind
== simplify::SIMPLIFY
3431 ? "Applying pattern" : "Matching expression");
3432 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3433 output_line_directive (f
,
3434 result
? result
->location
: s
->match
->location
, true,
3436 fprintf (f
, ", __FILE__, __LINE__);\n");
3438 fprintf_indent (f
, indent
, "{\n");
3442 /* If there is no result then this is a predicate implementation. */
3443 fprintf_indent (f
, indent
, "return true;\n");
3447 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3448 in outermost position). */
3449 if (result
->type
== operand::OP_EXPR
3450 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3451 result
= as_a
<expr
*> (result
)->ops
[0];
3452 if (result
->type
== operand::OP_EXPR
)
3454 expr
*e
= as_a
<expr
*> (result
);
3455 id_base
*opr
= e
->operation
;
3456 bool is_predicate
= false;
3457 /* When we delay operator substituting during lowering of fors we
3458 make sure that for code-gen purposes the effects of each substitute
3459 are the same. Thus just look at that. */
3460 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3461 opr
= uid
->substitutes
[0];
3462 else if (is_a
<predicate_id
*> (opr
))
3463 is_predicate
= true;
3465 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3466 *e
->operation
== CONVERT_EXPR
3467 ? "NOP_EXPR" : e
->operation
->id
,
3469 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3473 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3475 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3477 = get_operand_type (opr
, j
,
3478 "type", e
->expr_type
,
3480 : "TREE_TYPE (res_op->ops[0])");
3481 /* We need to expand GENERIC conditions we captured from
3482 COND_EXPRs and we need to unshare them when substituting
3484 int cond_handling
= 0;
3486 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3487 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3488 &cinfo
, indexes
, cond_handling
);
3491 /* Re-fold the toplevel result. It's basically an embedded
3492 gimple_build w/o actually building the stmt. */
3495 fprintf_indent (f
, indent
,
3496 "res_op->resimplify (%s, valueize);\n",
3497 !e
->force_leaf
? "lseq" : "NULL");
3499 fprintf_indent (f
, indent
,
3500 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3501 "goto %s;\n", fail_label
);
3504 else if (result
->type
== operand::OP_CAPTURE
3505 || result
->type
== operand::OP_C_EXPR
)
3507 fprintf_indent (f
, indent
, "tree tem;\n");
3508 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3510 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3511 if (is_a
<capture
*> (result
)
3512 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3514 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3515 with substituting a capture of that. */
3516 fprintf_indent (f
, indent
,
3517 "if (COMPARISON_CLASS_P (tem))\n");
3518 fprintf_indent (f
, indent
,
3520 fprintf_indent (f
, indent
,
3521 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3522 fprintf_indent (f
, indent
,
3523 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3524 fprintf_indent (f
, indent
,
3530 fprintf_indent (f
, indent
, "return true;\n");
3534 bool is_predicate
= false;
3535 if (result
->type
== operand::OP_EXPR
)
3537 expr
*e
= as_a
<expr
*> (result
);
3538 id_base
*opr
= e
->operation
;
3539 /* When we delay operator substituting during lowering of fors we
3540 make sure that for code-gen purposes the effects of each substitute
3541 are the same. Thus just look at that. */
3542 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3543 opr
= uid
->substitutes
[0];
3544 else if (is_a
<predicate_id
*> (opr
))
3545 is_predicate
= true;
3546 /* Search for captures used multiple times in the result expression
3547 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3548 original expression. */
3550 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3552 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3553 || cinfo
.info
[i
].cse_p
)
3555 if (cinfo
.info
[i
].result_use_count
3556 > cinfo
.info
[i
].match_use_count
)
3557 fprintf_indent (f
, indent
,
3558 "if (! tree_invariant_p (captures[%d])) "
3559 "goto %s;\n", i
, fail_label
);
3561 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3565 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3568 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3569 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3572 = get_operand_type (opr
, j
,
3573 "type", e
->expr_type
,
3575 ? NULL
: "TREE_TYPE (res_op0)");
3576 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3580 fprintf_indent (f
, indent
, "return true;\n");
3583 fprintf_indent (f
, indent
, "tree _r;\n");
3584 /* Re-fold the toplevel result. Use non_lvalue to
3585 build NON_LVALUE_EXPRs so they get properly
3586 ignored when in GIMPLE form. */
3587 if (*opr
== NON_LVALUE_EXPR
)
3588 fprintf_indent (f
, indent
,
3589 "_r = non_lvalue_loc (loc, res_op0);\n");
3592 if (is_a
<operator_id
*> (opr
))
3593 fprintf_indent (f
, indent
,
3594 "_r = fold_build%d_loc (loc, %s, type",
3596 *e
->operation
== CONVERT_EXPR
3597 ? "NOP_EXPR" : e
->operation
->id
);
3599 fprintf_indent (f
, indent
,
3600 "_r = maybe_build_call_expr_loc (loc, "
3601 "%s, type, %d", e
->operation
->id
,
3603 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3604 fprintf (f
, ", res_op%d", j
);
3605 fprintf (f
, ");\n");
3606 if (!is_a
<operator_id
*> (opr
))
3608 fprintf_indent (f
, indent
, "if (!_r)\n");
3609 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3614 else if (result
->type
== operand::OP_CAPTURE
3615 || result
->type
== operand::OP_C_EXPR
)
3618 fprintf_indent (f
, indent
, "tree _r;\n");
3619 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3626 /* Search for captures not used in the result expression and dependent
3627 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3628 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3630 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3632 if (!cinfo
.info
[i
].force_no_side_effects_p
3633 && !cinfo
.info
[i
].expr_p
3634 && cinfo
.info
[i
].result_use_count
== 0)
3636 fprintf_indent (f
, indent
,
3637 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3639 fprintf_indent (f
, indent
+ 2,
3640 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3641 "fold_ignored_result (captures[%d]), _r);\n",
3645 fprintf_indent (f
, indent
, "return _r;\n");
3649 fprintf_indent (f
, indent
, "}\n");
3650 fprintf (f
, "%s:;\n", fail_label
);
3654 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3655 step of a '(simplify ...)' or '(match ...)'. This handles everything
3656 that is not part of the decision tree (simplify->match). */
3659 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3661 fprintf_indent (f
, indent
, "{\n");
3663 output_line_directive (f
,
3664 s
->result
? s
->result
->location
: s
->match
->location
);
3665 if (s
->capture_max
>= 0)
3668 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3669 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3671 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3675 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3677 fprintf (f
, " };\n");
3680 /* If we have a split-out function for the actual transform, call it. */
3681 if (info
&& info
->fname
)
3685 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3686 "valueize, type, captures", info
->fname
);
3687 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3688 if (s
->for_subst_vec
[i
].first
->used
)
3689 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3690 fprintf (f
, "))\n");
3691 fprintf_indent (f
, indent
, " return true;\n");
3695 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3697 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3698 fprintf (f
, ", _p%d", i
);
3699 fprintf (f
, ", captures");
3700 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3702 if (s
->for_subst_vec
[i
].first
->used
)
3703 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3705 fprintf (f
, ");\n");
3706 fprintf_indent (f
, indent
, "if (res) return res;\n");
3711 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3713 if (! s
->for_subst_vec
[i
].first
->used
)
3715 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3716 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3717 s
->for_subst_vec
[i
].first
->id
,
3718 s
->for_subst_vec
[i
].second
->id
);
3719 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3720 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3721 s
->for_subst_vec
[i
].first
->id
,
3722 s
->for_subst_vec
[i
].second
->id
);
3726 gen_1 (f
, indent
, gimple
, s
->result
);
3730 fprintf_indent (f
, indent
, "}\n");
3734 /* Hash function for finding equivalent transforms. */
3737 sinfo_hashmap_traits::hash (const key_type
&v
)
3739 /* Only bother to compare those originating from the same source pattern. */
3740 return v
->s
->result
->location
;
3743 /* Compare function for finding equivalent transforms. */
3746 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3748 if (o1
->type
!= o2
->type
)
3753 case operand::OP_IF
:
3755 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3756 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3757 /* ??? Properly compare c-exprs. */
3758 if (if1
->cond
!= if2
->cond
)
3760 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3762 if (if1
->falseexpr
!= if2
->falseexpr
3764 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3768 case operand::OP_WITH
:
3770 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3771 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3772 if (with1
->with
!= with2
->with
)
3774 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3779 /* We've hit a result. Time to compare capture-infos - this is required
3780 in addition to the conservative pointer-equivalency of the result IL. */
3781 capture_info
cinfo1 (s1
, o1
, true);
3782 capture_info
cinfo2 (s2
, o2
, true);
3784 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3785 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3788 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3790 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3791 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3792 || (cinfo1
.info
[i
].force_no_side_effects_p
3793 != cinfo2
.info
[i
].force_no_side_effects_p
)
3794 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3795 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3796 /* toplevel_msk is an optimization */
3797 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3798 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3799 /* the pointer back to the capture is for diagnostics only */)
3803 /* ??? Deep-compare the actual result. */
3808 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3809 const key_type
&candidate
)
3811 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3815 /* Main entry to generate code for matching GIMPLE IL off the decision
3819 decision_tree::gen (FILE *f
, bool gimple
)
3825 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3826 "a total number of %u nodes\n",
3827 gimple
? "GIMPLE" : "GENERIC",
3828 root
->num_leafs
, root
->max_level
, root
->total_size
);
3830 /* First split out the transform part of equal leafs. */
3833 for (sinfo_map_t::iterator iter
= si
.begin ();
3834 iter
!= si
.end (); ++iter
)
3836 sinfo
*s
= (*iter
).second
;
3837 /* Do not split out single uses. */
3844 fprintf (stderr
, "found %u uses of", s
->cnt
);
3845 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3848 /* Generate a split out function with the leaf transform code. */
3849 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3852 fprintf (f
, "\nstatic bool\n"
3853 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3854 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3855 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3860 fprintf (f
, "\nstatic tree\n"
3861 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3862 (*iter
).second
->fname
);
3863 for (unsigned i
= 0;
3864 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3865 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3866 fprintf (f
, " tree *captures\n");
3868 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3870 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3872 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3873 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3874 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3875 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3876 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3877 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3880 fprintf (f
, ")\n{\n");
3881 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3883 fprintf (f
, " return false;\n");
3885 fprintf (f
, " return NULL_TREE;\n");
3888 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3890 for (unsigned n
= 1; n
<= 5; ++n
)
3892 bool has_kids_p
= false;
3894 /* First generate split-out functions. */
3895 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3897 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3898 expr
*e
= static_cast<expr
*>(dop
->op
);
3899 if (e
->ops
.length () != n
3900 /* Builtin simplifications are somewhat premature on
3901 GENERIC. The following drops patterns with outermost
3902 calls. It's easy to emit overloads for function code
3903 though if necessary. */
3905 && e
->operation
->kind
!= id_base::CODE
))
3909 fprintf (f
, "\nstatic bool\n"
3910 "gimple_simplify_%s (gimple_match_op *res_op,"
3911 " gimple_seq *seq,\n"
3912 " tree (*valueize)(tree) "
3913 "ATTRIBUTE_UNUSED,\n"
3914 " code_helper ARG_UNUSED (code), tree "
3915 "ARG_UNUSED (type)\n",
3918 fprintf (f
, "\nstatic tree\n"
3919 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3920 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3922 for (unsigned i
= 0; i
< n
; ++i
)
3923 fprintf (f
, ", tree _p%d", i
);
3926 dop
->gen_kids (f
, 2, gimple
, 0);
3928 fprintf (f
, " return false;\n");
3930 fprintf (f
, " return NULL_TREE;\n");
3935 /* If this main entry has no children, avoid generating code
3936 with compiler warnings, by generating a simple stub. */
3940 fprintf (f
, "\nstatic bool\n"
3941 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3942 " tree (*)(tree), code_helper,\n"
3945 fprintf (f
, "\ntree\n"
3946 "generic_simplify (location_t, enum tree_code,\n"
3948 for (unsigned i
= 0; i
< n
; ++i
)
3949 fprintf (f
, ", tree");
3953 fprintf (f
, " return false;\n");
3955 fprintf (f
, " return NULL_TREE;\n");
3960 /* Then generate the main entry with the outermost switch and
3961 tail-calls to the split-out functions. */
3963 fprintf (f
, "\nstatic bool\n"
3964 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3965 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3966 " code_helper code, const tree type");
3968 fprintf (f
, "\ntree\n"
3969 "generic_simplify (location_t loc, enum tree_code code, "
3970 "const tree type ATTRIBUTE_UNUSED");
3971 for (unsigned i
= 0; i
< n
; ++i
)
3972 fprintf (f
, ", tree _p%d", i
);
3977 fprintf (f
, " switch (code.get_rep())\n"
3980 fprintf (f
, " switch (code)\n"
3982 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3984 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3985 expr
*e
= static_cast<expr
*>(dop
->op
);
3986 if (e
->ops
.length () != n
3987 /* Builtin simplifications are somewhat premature on
3988 GENERIC. The following drops patterns with outermost
3989 calls. It's easy to emit overloads for function code
3990 though if necessary. */
3992 && e
->operation
->kind
!= id_base::CODE
))
3995 if (*e
->operation
== CONVERT_EXPR
3996 || *e
->operation
== NOP_EXPR
)
3997 fprintf (f
, " CASE_CONVERT:\n");
3999 fprintf (f
, " case %s%s:\n",
4000 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
4003 fprintf (f
, " return gimple_simplify_%s (res_op, "
4004 "seq, valueize, code, type", e
->operation
->id
);
4006 fprintf (f
, " return generic_simplify_%s (loc, code, type",
4008 for (unsigned j
= 0; j
< n
; ++j
)
4009 fprintf (f
, ", _p%d", j
);
4010 fprintf (f
, ");\n");
4012 fprintf (f
, " default:;\n"
4016 fprintf (f
, " return false;\n");
4018 fprintf (f
, " return NULL_TREE;\n");
4023 /* Output code to implement the predicate P from the decision tree DT. */
4026 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
4028 fprintf (f
, "\nbool\n"
4029 "%s%s (tree t%s%s)\n"
4030 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
4031 p
->nargs
> 0 ? ", tree *res_ops" : "",
4032 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
4033 /* Conveniently make 'type' available. */
4034 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
4037 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
4038 dt
.root
->gen_kids (f
, 2, gimple
, 0);
4040 fprintf_indent (f
, 2, "return false;\n"
4044 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4047 write_header (FILE *f
, const char *head
)
4049 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4050 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4052 /* Include the header instead of writing it awkwardly quoted here. */
4053 fprintf (f
, "\n#include \"%s\"\n", head
);
4063 parser (cpp_reader
*, bool gimple
);
4066 const cpp_token
*next ();
4067 const cpp_token
*peek (unsigned = 1);
4068 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4069 const cpp_token
*expect (enum cpp_ttype
);
4070 const cpp_token
*eat_token (enum cpp_ttype
);
4071 const char *get_string ();
4072 const char *get_ident ();
4073 const cpp_token
*eat_ident (const char *);
4074 const char *get_number ();
4076 unsigned get_internal_capture_id ();
4078 id_base
*parse_operation (unsigned char &);
4079 operand
*parse_capture (operand
*, bool);
4080 operand
*parse_expr ();
4081 c_expr
*parse_c_expr (cpp_ttype
);
4082 operand
*parse_op ();
4084 void record_operlist (location_t
, user_id
*);
4086 void parse_pattern ();
4087 operand
*parse_result (operand
*, predicate_id
*);
4088 void push_simplify (simplify::simplify_kind
,
4089 vec
<simplify
*>&, operand
*, operand
*);
4090 void parse_simplify (simplify::simplify_kind
,
4091 vec
<simplify
*>&, predicate_id
*, operand
*);
4092 void parse_for (location_t
);
4093 void parse_if (location_t
);
4094 void parse_predicates (location_t
);
4095 void parse_operator_list (location_t
);
4097 void finish_match_operand (operand
*);
4101 vec
<c_expr
*> active_ifs
;
4102 vec
<vec
<user_id
*> > active_fors
;
4103 hash_set
<user_id
*> *oper_lists_set
;
4104 vec
<user_id
*> oper_lists
;
4106 cid_map_t
*capture_ids
;
4110 vec
<simplify
*> simplifiers
;
4111 vec
<predicate_id
*> user_predicates
;
4112 bool parsing_match_operand
;
4115 /* Lexing helpers. */
4117 /* Read the next non-whitespace token from R. */
4122 const cpp_token
*token
;
4125 token
= cpp_get_token (r
);
4127 while (token
->type
== CPP_PADDING
);
4131 /* Peek at the next non-whitespace token from R. */
4134 parser::peek (unsigned num
)
4136 const cpp_token
*token
;
4140 token
= cpp_peek_token (r
, i
++);
4142 while (token
->type
== CPP_PADDING
4144 /* If we peek at EOF this is a fatal error as it leaves the
4145 cpp_reader in unusable state. Assume we really wanted a
4146 token and thus this EOF is unexpected. */
4147 if (token
->type
== CPP_EOF
)
4148 fatal_at (token
, "unexpected end of file");
4152 /* Peek at the next identifier token (or return NULL if the next
4153 token is not an identifier or equal to ID if supplied). */
4156 parser::peek_ident (const char *id
, unsigned num
)
4158 const cpp_token
*token
= peek (num
);
4159 if (token
->type
!= CPP_NAME
)
4165 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4166 if (strcmp (id
, t
) == 0)
4172 /* Read the next token from R and assert it is of type TK. */
4175 parser::expect (enum cpp_ttype tk
)
4177 const cpp_token
*token
= next ();
4178 if (token
->type
!= tk
)
4179 fatal_at (token
, "expected %s, got %s",
4180 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4185 /* Consume the next token from R and assert it is of type TK. */
4188 parser::eat_token (enum cpp_ttype tk
)
4193 /* Read the next token from R and assert it is of type CPP_STRING and
4194 return its value. */
4197 parser::get_string ()
4199 const cpp_token
*token
= expect (CPP_STRING
);
4200 return (const char *)token
->val
.str
.text
;
4203 /* Read the next token from R and assert it is of type CPP_NAME and
4204 return its value. */
4207 parser::get_ident ()
4209 const cpp_token
*token
= expect (CPP_NAME
);
4210 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4213 /* Eat an identifier token with value S from R. */
4216 parser::eat_ident (const char *s
)
4218 const cpp_token
*token
= peek ();
4219 const char *t
= get_ident ();
4220 if (strcmp (s
, t
) != 0)
4221 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4225 /* Read the next token from R and assert it is of type CPP_NUMBER and
4226 return its value. */
4229 parser::get_number ()
4231 const cpp_token
*token
= expect (CPP_NUMBER
);
4232 return (const char *)token
->val
.str
.text
;
4235 /* Return a capture ID that can be used internally. */
4238 parser::get_internal_capture_id ()
4240 unsigned newid
= capture_ids
->elements ();
4241 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4244 snprintf (id
, sizeof (id
), "__%u", newid
);
4245 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4247 fatal ("reserved capture id '%s' already used", id
);
4251 /* Record an operator-list use for transparent for handling. */
4254 parser::record_operlist (location_t loc
, user_id
*p
)
4256 if (!oper_lists_set
->add (p
))
4258 if (!oper_lists
.is_empty ()
4259 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4260 fatal_at (loc
, "User-defined operator list does not have the "
4261 "same number of entries as others used in the pattern");
4262 oper_lists
.safe_push (p
);
4266 /* Parse the operator ID, special-casing convert?, convert1? and
4270 parser::parse_operation (unsigned char &opt_grp
)
4272 const cpp_token
*id_tok
= peek ();
4273 char *alt_id
= NULL
;
4274 const char *id
= get_ident ();
4275 const cpp_token
*token
= peek ();
4277 if (token
->type
== CPP_QUERY
4278 && !(token
->flags
& PREV_WHITE
))
4280 if (!parsing_match_operand
)
4281 fatal_at (id_tok
, "conditional convert can only be used in "
4282 "match expression");
4283 if (ISDIGIT (id
[strlen (id
) - 1]))
4285 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4286 alt_id
= xstrdup (id
);
4287 alt_id
[strlen (id
) - 1] = '\0';
4289 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4293 eat_token (CPP_QUERY
);
4295 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4297 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4300 user_id
*p
= dyn_cast
<user_id
*> (op
);
4301 if (p
&& p
->is_oper_list
)
4303 if (active_fors
.length() == 0)
4304 record_operlist (id_tok
->src_loc
, p
);
4306 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4312 capture = '@'<number> */
4315 parser::parse_capture (operand
*op
, bool require_existing
)
4317 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4318 const cpp_token
*token
= peek ();
4319 const char *id
= NULL
;
4320 bool value_match
= false;
4321 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4322 if (token
->type
== CPP_ATSIGN
4323 && ! (token
->flags
& PREV_WHITE
)
4324 && parsing_match_operand
)
4326 eat_token (CPP_ATSIGN
);
4330 if (token
->type
== CPP_NUMBER
)
4332 else if (token
->type
== CPP_NAME
)
4335 fatal_at (token
, "expected number or identifier");
4336 unsigned next_id
= capture_ids
->elements ();
4338 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4341 if (require_existing
)
4342 fatal_at (src_loc
, "unknown capture id");
4345 return new capture (src_loc
, num
, op
, value_match
);
4348 /* Parse an expression
4349 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4352 parser::parse_expr ()
4354 const cpp_token
*token
= peek ();
4355 unsigned char opt_grp
;
4356 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4359 bool is_commutative
= false;
4360 bool force_capture
= false;
4361 const char *expr_type
= NULL
;
4363 if (!parsing_match_operand
4364 && token
->type
== CPP_NOT
4365 && !(token
->flags
& PREV_WHITE
))
4367 eat_token (CPP_NOT
);
4368 e
->force_leaf
= true;
4371 if (token
->type
== CPP_COLON
4372 && !(token
->flags
& PREV_WHITE
))
4374 eat_token (CPP_COLON
);
4376 if (token
->type
== CPP_NAME
4377 && !(token
->flags
& PREV_WHITE
))
4379 const char *s
= get_ident ();
4380 if (!parsing_match_operand
)
4390 = dyn_cast
<operator_id
*> (e
->operation
))
4392 if (!commutative_tree_code (o
->code
)
4393 && !comparison_code_p (o
->code
))
4394 fatal_at (token
, "operation is not commutative");
4396 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4397 for (unsigned i
= 0;
4398 i
< p
->substitutes
.length (); ++i
)
4401 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4403 if (!commutative_tree_code (q
->code
)
4404 && !comparison_code_p (q
->code
))
4405 fatal_at (token
, "operation %s is not "
4406 "commutative", q
->id
);
4409 is_commutative
= true;
4411 else if (*sp
== 'C')
4412 is_commutative
= true;
4413 else if (*sp
== 's')
4415 e
->force_single_use
= true;
4416 force_capture
= true;
4419 fatal_at (token
, "flag %c not recognized", *sp
);
4426 fatal_at (token
, "expected flag or type specifying identifier");
4429 if (token
->type
== CPP_ATSIGN
4430 && !(token
->flags
& PREV_WHITE
))
4431 op
= parse_capture (e
, false);
4432 else if (force_capture
)
4434 unsigned num
= get_internal_capture_id ();
4435 op
= new capture (token
->src_loc
, num
, e
, false);
4442 if (token
->type
== CPP_CLOSE_PAREN
)
4444 if (e
->operation
->nargs
!= -1
4445 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4446 fatal_at (token
, "'%s' expects %u operands, not %u",
4447 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4450 if (e
->ops
.length () == 2
4451 || commutative_op (e
->operation
) >= 0)
4452 e
->is_commutative
= true;
4454 fatal_at (token
, "only binary operators or functions with "
4455 "two arguments can be marked commutative, "
4456 "unless the operation is known to be inherently "
4459 e
->expr_type
= expr_type
;
4462 if (e
->ops
.length () != 1)
4463 fatal_at (token
, "only unary operations can be conditional");
4464 e
->opt_grp
= opt_grp
;
4468 else if (!(token
->flags
& PREV_WHITE
))
4469 fatal_at (token
, "expected expression operand");
4471 e
->append_op (parse_op ());
4476 /* Lex native C code delimited by START recording the preprocessing tokens
4477 for later processing.
4478 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4481 parser::parse_c_expr (cpp_ttype start
)
4483 const cpp_token
*token
;
4486 vec
<cpp_token
> code
= vNULL
;
4487 unsigned nr_stmts
= 0;
4488 location_t loc
= eat_token (start
)->src_loc
;
4489 if (start
== CPP_OPEN_PAREN
)
4490 end
= CPP_CLOSE_PAREN
;
4491 else if (start
== CPP_OPEN_BRACE
)
4492 end
= CPP_CLOSE_BRACE
;
4500 /* Count brace pairs to find the end of the expr to match. */
4501 if (token
->type
== start
)
4503 else if (token
->type
== end
4506 else if (token
->type
== CPP_EOF
)
4507 fatal_at (token
, "unexpected end of file");
4509 /* This is a lame way of counting the number of statements. */
4510 if (token
->type
== CPP_SEMICOLON
)
4513 /* If this is possibly a user-defined identifier mark it used. */
4514 if (token
->type
== CPP_NAME
)
4517 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4518 if (strcmp (str
, "return") == 0)
4519 fatal_at (token
, "return statement not allowed in C expression");
4520 id_base
*idb
= get_operator (str
);
4522 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4523 record_operlist (token
->src_loc
, p
);
4526 /* Record the token. */
4527 code
.safe_push (*token
);
4530 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4533 /* Parse an operand which is either an expression, a predicate or
4534 a standalone capture.
4535 op = predicate | expr | c_expr | capture */
4540 const cpp_token
*token
= peek ();
4541 class operand
*op
= NULL
;
4542 if (token
->type
== CPP_OPEN_PAREN
)
4544 eat_token (CPP_OPEN_PAREN
);
4546 eat_token (CPP_CLOSE_PAREN
);
4548 else if (token
->type
== CPP_OPEN_BRACE
)
4550 op
= parse_c_expr (CPP_OPEN_BRACE
);
4554 /* Remaining ops are either empty or predicates */
4555 if (token
->type
== CPP_NAME
)
4557 const char *id
= get_ident ();
4558 id_base
*opr
= get_operator (id
);
4560 fatal_at (token
, "expected predicate name");
4561 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4563 if (code1
->nargs
!= 0)
4564 fatal_at (token
, "using an operator with operands as predicate");
4565 /* Parse the zero-operand operator "predicates" as
4567 op
= new expr (opr
, token
->src_loc
);
4569 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4571 if (code2
->nargs
!= 0)
4572 fatal_at (token
, "using an operator with operands as predicate");
4573 /* Parse the zero-operand operator "predicates" as
4575 op
= new expr (opr
, token
->src_loc
);
4577 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4578 op
= new predicate (p
, token
->src_loc
);
4580 fatal_at (token
, "using an unsupported operator as predicate");
4581 if (!parsing_match_operand
)
4582 fatal_at (token
, "predicates are only allowed in match expression");
4584 if (token
->flags
& PREV_WHITE
)
4587 else if (token
->type
!= CPP_COLON
4588 && token
->type
!= CPP_ATSIGN
)
4589 fatal_at (token
, "expected expression or predicate");
4590 /* optionally followed by a capture and a predicate. */
4591 if (token
->type
== CPP_COLON
)
4592 fatal_at (token
, "not implemented: predicate on leaf operand");
4593 if (token
->type
== CPP_ATSIGN
)
4594 op
= parse_capture (op
, !parsing_match_operand
);
4600 /* Create a new simplify from the current parsing state and MATCH,
4601 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4604 parser::push_simplify (simplify::simplify_kind kind
,
4605 vec
<simplify
*>& simplifiers
,
4606 operand
*match
, operand
*result
)
4608 /* Build and push a temporary for operator list uses in expressions. */
4609 if (!oper_lists
.is_empty ())
4610 active_fors
.safe_push (oper_lists
);
4612 simplifiers
.safe_push
4613 (new simplify (kind
, last_id
++, match
, result
,
4614 active_fors
.copy (), capture_ids
));
4616 if (!oper_lists
.is_empty ())
4621 <result-op> = <op> | <if> | <with>
4622 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4623 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4627 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4629 const cpp_token
*token
= peek ();
4630 if (token
->type
!= CPP_OPEN_PAREN
)
4633 eat_token (CPP_OPEN_PAREN
);
4634 if (peek_ident ("if"))
4637 if_expr
*ife
= new if_expr (token
->src_loc
);
4638 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4639 if (peek ()->type
== CPP_OPEN_PAREN
)
4641 ife
->trueexpr
= parse_result (result
, matcher
);
4642 if (peek ()->type
== CPP_OPEN_PAREN
)
4643 ife
->falseexpr
= parse_result (result
, matcher
);
4644 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4645 ife
->falseexpr
= parse_op ();
4647 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4649 ife
->trueexpr
= parse_op ();
4650 if (peek ()->type
== CPP_OPEN_PAREN
)
4651 ife
->falseexpr
= parse_result (result
, matcher
);
4652 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4653 ife
->falseexpr
= parse_op ();
4655 /* If this if is immediately closed then it contains a
4656 manual matcher or is part of a predicate definition. */
4657 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4660 fatal_at (peek (), "manual transform not implemented");
4661 ife
->trueexpr
= result
;
4663 eat_token (CPP_CLOSE_PAREN
);
4666 else if (peek_ident ("with"))
4669 with_expr
*withe
= new with_expr (token
->src_loc
);
4670 /* Parse (with c-expr expr) as (if-with (true) expr). */
4671 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4672 withe
->with
->nr_stmts
= 0;
4673 withe
->subexpr
= parse_result (result
, matcher
);
4674 eat_token (CPP_CLOSE_PAREN
);
4677 else if (peek_ident ("switch"))
4679 token
= eat_ident ("switch");
4680 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4682 if_expr
*ife
= new if_expr (ifloc
);
4684 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4685 if (peek ()->type
== CPP_OPEN_PAREN
)
4686 ife
->trueexpr
= parse_result (result
, matcher
);
4688 ife
->trueexpr
= parse_op ();
4689 eat_token (CPP_CLOSE_PAREN
);
4690 if (peek ()->type
!= CPP_OPEN_PAREN
4691 || !peek_ident ("if", 2))
4692 fatal_at (token
, "switch can be implemented with a single if");
4693 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4695 if (peek ()->type
== CPP_OPEN_PAREN
)
4697 if (peek_ident ("if", 2))
4699 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4701 ife
->falseexpr
= new if_expr (ifloc
);
4702 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4703 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4704 if (peek ()->type
== CPP_OPEN_PAREN
)
4705 ife
->trueexpr
= parse_result (result
, matcher
);
4707 ife
->trueexpr
= parse_op ();
4708 eat_token (CPP_CLOSE_PAREN
);
4712 /* switch default clause */
4713 ife
->falseexpr
= parse_result (result
, matcher
);
4714 eat_token (CPP_CLOSE_PAREN
);
4720 /* switch default clause */
4721 ife
->falseexpr
= parse_op ();
4722 eat_token (CPP_CLOSE_PAREN
);
4726 eat_token (CPP_CLOSE_PAREN
);
4731 operand
*op
= result
;
4734 eat_token (CPP_CLOSE_PAREN
);
4740 simplify = 'simplify' <expr> <result-op>
4742 match = 'match' <ident> <expr> [<result-op>]
4743 and fill SIMPLIFIERS with the results. */
4746 parser::parse_simplify (simplify::simplify_kind kind
,
4747 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4750 /* Reset the capture map. */
4752 capture_ids
= new cid_map_t
;
4753 /* Reset oper_lists and set. */
4754 hash_set
<user_id
*> olist
;
4755 oper_lists_set
= &olist
;
4758 const cpp_token
*loc
= peek ();
4759 parsing_match_operand
= true;
4760 class operand
*match
= parse_op ();
4761 finish_match_operand (match
);
4762 parsing_match_operand
= false;
4763 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4764 fatal_at (loc
, "outermost expression cannot be captured");
4765 if (match
->type
== operand::OP_EXPR
4766 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4767 fatal_at (loc
, "outermost expression cannot be a predicate");
4769 /* Splice active_ifs onto result and continue parsing the
4771 if_expr
*active_if
= NULL
;
4772 for (int i
= active_ifs
.length (); i
> 0; --i
)
4774 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4775 ifc
->cond
= active_ifs
[i
-1];
4776 ifc
->trueexpr
= active_if
;
4779 if_expr
*outermost_if
= active_if
;
4780 while (active_if
&& active_if
->trueexpr
)
4781 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4783 const cpp_token
*token
= peek ();
4785 /* If this if is immediately closed then it is part of a predicate
4786 definition. Push it. */
4787 if (token
->type
== CPP_CLOSE_PAREN
)
4790 fatal_at (token
, "expected transform expression");
4793 active_if
->trueexpr
= result
;
4794 result
= outermost_if
;
4796 push_simplify (kind
, simplifiers
, match
, result
);
4800 operand
*tem
= parse_result (result
, matcher
);
4803 active_if
->trueexpr
= tem
;
4804 result
= outermost_if
;
4809 push_simplify (kind
, simplifiers
, match
, result
);
4812 /* Parsing of the outer control structures. */
4814 /* Parse a for expression
4815 for = '(' 'for' <subst>... <pattern> ')'
4816 subst = <ident> '(' <ident>... ')' */
4819 parser::parse_for (location_t
)
4821 auto_vec
<const cpp_token
*> user_id_tokens
;
4822 vec
<user_id
*> user_ids
= vNULL
;
4823 const cpp_token
*token
;
4824 unsigned min_n_opers
= 0, max_n_opers
= 0;
4829 if (token
->type
!= CPP_NAME
)
4832 /* Insert the user defined operators into the operator hash. */
4833 const char *id
= get_ident ();
4834 if (get_operator (id
, true) != NULL
)
4835 fatal_at (token
, "operator already defined");
4836 user_id
*op
= new user_id (id
);
4837 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4839 user_ids
.safe_push (op
);
4840 user_id_tokens
.safe_push (token
);
4842 eat_token (CPP_OPEN_PAREN
);
4845 while ((token
= peek_ident ()) != 0)
4847 const char *oper
= get_ident ();
4848 id_base
*idb
= get_operator (oper
, true);
4850 fatal_at (token
, "no such operator '%s'", oper
);
4854 else if (idb
->nargs
== -1)
4856 else if (idb
->nargs
!= arity
)
4857 fatal_at (token
, "operator '%s' with arity %d does not match "
4858 "others with arity %d", oper
, idb
->nargs
, arity
);
4860 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4863 if (p
->is_oper_list
)
4864 op
->substitutes
.safe_splice (p
->substitutes
);
4866 fatal_at (token
, "iterator cannot be used as operator-list");
4869 op
->substitutes
.safe_push (idb
);
4872 token
= expect (CPP_CLOSE_PAREN
);
4874 unsigned nsubstitutes
= op
->substitutes
.length ();
4875 if (nsubstitutes
== 0)
4876 fatal_at (token
, "A user-defined operator must have at least "
4877 "one substitution");
4878 if (max_n_opers
== 0)
4880 min_n_opers
= nsubstitutes
;
4881 max_n_opers
= nsubstitutes
;
4885 if (nsubstitutes
% min_n_opers
!= 0
4886 && min_n_opers
% nsubstitutes
!= 0)
4887 fatal_at (token
, "All user-defined identifiers must have a "
4888 "multiple number of operator substitutions of the "
4889 "smallest number of substitutions");
4890 if (nsubstitutes
< min_n_opers
)
4891 min_n_opers
= nsubstitutes
;
4892 else if (nsubstitutes
> max_n_opers
)
4893 max_n_opers
= nsubstitutes
;
4897 unsigned n_ids
= user_ids
.length ();
4899 fatal_at (token
, "for requires at least one user-defined identifier");
4902 if (token
->type
== CPP_CLOSE_PAREN
)
4903 fatal_at (token
, "no pattern defined in for");
4905 active_fors
.safe_push (user_ids
);
4909 if (token
->type
== CPP_CLOSE_PAREN
)
4915 /* Remove user-defined operators from the hash again. */
4916 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4918 if (!user_ids
[i
]->used
)
4919 warning_at (user_id_tokens
[i
],
4920 "operator %s defined but not used", user_ids
[i
]->id
);
4921 operators
->remove_elt (user_ids
[i
]);
4925 /* Parse an identifier associated with a list of operators.
4926 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4929 parser::parse_operator_list (location_t
)
4931 const cpp_token
*token
= peek ();
4932 const char *id
= get_ident ();
4934 if (get_operator (id
, true) != 0)
4935 fatal_at (token
, "operator %s already defined", id
);
4937 user_id
*op
= new user_id (id
, true);
4940 while ((token
= peek_ident ()) != 0)
4943 const char *oper
= get_ident ();
4944 id_base
*idb
= get_operator (oper
, true);
4947 fatal_at (token
, "no such operator '%s'", oper
);
4951 else if (idb
->nargs
== -1)
4953 else if (arity
!= idb
->nargs
)
4954 fatal_at (token
, "operator '%s' with arity %d does not match "
4955 "others with arity %d", oper
, idb
->nargs
, arity
);
4957 /* We allow composition of multiple operator lists. */
4958 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4959 op
->substitutes
.safe_splice (p
->substitutes
);
4961 op
->substitutes
.safe_push (idb
);
4964 // Check that there is no junk after id-list
4966 if (token
->type
!= CPP_CLOSE_PAREN
)
4967 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4969 if (op
->substitutes
.length () == 0)
4970 fatal_at (token
, "operator-list cannot be empty");
4973 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4977 /* Parse an outer if expression.
4978 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4981 parser::parse_if (location_t
)
4983 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4985 const cpp_token
*token
= peek ();
4986 if (token
->type
== CPP_CLOSE_PAREN
)
4987 fatal_at (token
, "no pattern defined in if");
4989 active_ifs
.safe_push (ifexpr
);
4993 if (token
->type
== CPP_CLOSE_PAREN
)
5001 /* Parse a list of predefined predicate identifiers.
5002 preds = '(' 'define_predicates' <ident>... ')' */
5005 parser::parse_predicates (location_t
)
5009 const cpp_token
*token
= peek ();
5010 if (token
->type
!= CPP_NAME
)
5013 add_predicate (get_ident ());
5018 /* Parse outer control structures.
5019 pattern = <preds>|<for>|<if>|<simplify>|<match> */
5022 parser::parse_pattern ()
5024 /* All clauses start with '('. */
5025 eat_token (CPP_OPEN_PAREN
);
5026 const cpp_token
*token
= peek ();
5027 const char *id
= get_ident ();
5028 if (strcmp (id
, "simplify") == 0)
5030 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
5033 else if (strcmp (id
, "match") == 0)
5035 bool with_args
= false;
5036 location_t e_loc
= peek ()->src_loc
;
5037 if (peek ()->type
== CPP_OPEN_PAREN
)
5039 eat_token (CPP_OPEN_PAREN
);
5042 const char *name
= get_ident ();
5043 id_base
*id1
= get_operator (name
);
5047 p
= add_predicate (name
);
5048 user_predicates
.safe_push (p
);
5050 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5053 fatal_at (token
, "cannot add a match to a non-predicate ID");
5054 /* Parse (match <id> <arg>... (match-expr)) here. */
5058 capture_ids
= new cid_map_t
;
5059 e
= new expr (p
, e_loc
);
5060 while (peek ()->type
== CPP_ATSIGN
)
5061 e
->append_op (parse_capture (NULL
, false));
5062 eat_token (CPP_CLOSE_PAREN
);
5065 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5066 || (!e
&& p
->nargs
!= 0)))
5067 fatal_at (token
, "non-matching number of match operands");
5068 p
->nargs
= e
? e
->ops
.length () : 0;
5069 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5072 else if (strcmp (id
, "for") == 0)
5073 parse_for (token
->src_loc
);
5074 else if (strcmp (id
, "if") == 0)
5075 parse_if (token
->src_loc
);
5076 else if (strcmp (id
, "define_predicates") == 0)
5078 if (active_ifs
.length () > 0
5079 || active_fors
.length () > 0)
5080 fatal_at (token
, "define_predicates inside if or for is not supported");
5081 parse_predicates (token
->src_loc
);
5083 else if (strcmp (id
, "define_operator_list") == 0)
5085 if (active_ifs
.length () > 0
5086 || active_fors
.length () > 0)
5087 fatal_at (token
, "operator-list inside if or for is not supported");
5088 parse_operator_list (token
->src_loc
);
5091 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5092 active_ifs
.length () == 0 && active_fors
.length () == 0
5093 ? "'define_predicates', " : "");
5095 eat_token (CPP_CLOSE_PAREN
);
5098 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5102 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5107 if (capture
*c
= dyn_cast
<capture
*> (op
))
5109 cpts
[c
->where
].safe_push (c
);
5110 walk_captures (c
->what
, cpts
);
5112 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5113 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5114 walk_captures (e
->ops
[i
], cpts
);
5117 /* Finish up OP which is a match operand. */
5120 parser::finish_match_operand (operand
*op
)
5122 /* Look for matching captures, diagnose mis-uses of @@ and apply
5123 early lowering and distribution of value_match. */
5124 auto_vec
<vec
<capture
*> > cpts
;
5125 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5126 walk_captures (op
, cpts
);
5127 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5129 capture
*value_match
= NULL
;
5130 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5132 if (cpts
[i
][j
]->value_match
)
5135 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5136 value_match
= cpts
[i
][j
];
5139 if (cpts
[i
].length () == 1 && value_match
)
5140 fatal_at (value_match
->location
, "@@ without a matching capture");
5143 /* Duplicate prevailing capture with the existing ID, create
5144 a fake ID and rewrite all captures to use it. This turns
5145 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5146 value_match
->what
= new capture (value_match
->location
,
5148 value_match
->what
, false);
5149 /* Create a fake ID and rewrite all captures to use it. */
5150 unsigned newid
= get_internal_capture_id ();
5151 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5153 cpts
[i
][j
]->where
= newid
;
5154 cpts
[i
][j
]->value_match
= true;
5161 /* Main entry of the parser. Repeatedly parse outer control structures. */
5163 parser::parser (cpp_reader
*r_
, bool gimple_
)
5168 active_fors
= vNULL
;
5169 simplifiers
= vNULL
;
5170 oper_lists_set
= NULL
;
5173 user_predicates
= vNULL
;
5174 parsing_match_operand
= false;
5177 const cpp_token
*token
= next ();
5178 while (token
->type
!= CPP_EOF
)
5180 _cpp_backup_tokens (r
, 1);
5187 /* Helper for the linemap code. */
5190 round_alloc_size (size_t s
)
5196 /* The genmatch generator program. It reads from a pattern description
5197 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5200 main (int argc
, char **argv
)
5204 progname
= "genmatch";
5210 char *input
= argv
[argc
-1];
5211 for (int i
= 1; i
< argc
- 1; ++i
)
5213 if (strcmp (argv
[i
], "--gimple") == 0)
5215 else if (strcmp (argv
[i
], "--generic") == 0)
5217 else if (strcmp (argv
[i
], "-v") == 0)
5219 else if (strcmp (argv
[i
], "-vv") == 0)
5223 fprintf (stderr
, "Usage: genmatch "
5224 "[--gimple] [--generic] [-v[v]] input\n");
5229 line_table
= XCNEW (class line_maps
);
5230 linemap_init (line_table
, 0);
5231 line_table
->reallocator
= xrealloc
;
5232 line_table
->round_alloc_size
= round_alloc_size
;
5234 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5235 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5236 cb
->diagnostic
= diagnostic_cb
;
5238 /* Add the build directory to the #include "" search path. */
5239 cpp_dir
*dir
= XCNEW (cpp_dir
);
5240 dir
->name
= getpwd ();
5242 dir
->name
= ASTRDUP (".");
5243 cpp_set_include_chains (r
, dir
, NULL
, false);
5245 if (!cpp_read_main_file (r
, input
))
5247 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5248 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5250 null_id
= new id_base (id_base::NULL_ID
, "null");
5252 /* Pre-seed operators. */
5253 operators
= new hash_table
<id_base
> (1024);
5254 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5255 add_operator (SYM, # SYM, # TYPE, NARGS);
5256 #define END_OF_BASE_TREE_CODES
5258 #undef END_OF_BASE_TREE_CODES
5261 /* Pre-seed builtin functions.
5262 ??? Cannot use N (name) as that is targetm.emultls.get_address
5263 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5264 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5265 add_function (ENUM, "CFN_" # ENUM);
5266 #include "builtins.def"
5268 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5269 add_function (IFN_##CODE, "CFN_" #CODE);
5270 #include "internal-fn.def"
5273 parser
p (r
, gimple
);
5276 write_header (stdout
, "gimple-match-head.cc");
5278 write_header (stdout
, "generic-match-head.cc");
5280 /* Go over all predicates defined with patterns and perform
5281 lowering and code generation. */
5282 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5284 predicate_id
*pred
= p
.user_predicates
[i
];
5285 lower (pred
->matchers
, gimple
);
5288 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5289 print_matches (pred
->matchers
[j
]);
5292 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5293 dt
.insert (pred
->matchers
[j
], j
);
5298 write_predicate (stdout
, pred
, dt
, gimple
);
5301 /* Lower the main simplifiers and generate code for them. */
5302 lower (p
.simplifiers
, gimple
);
5305 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5306 print_matches (p
.simplifiers
[i
]);
5309 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5310 dt
.insert (p
.simplifiers
[i
], i
);
5315 dt
.gen (stdout
, gimple
);
5318 cpp_finish (r
, NULL
);