1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2022 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
187 output_line_directive (FILE *f
, location_t location
,
188 bool dumpfile
= false, bool fnargs
= false)
190 const line_map_ordinary
*map
;
191 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
192 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
195 /* When writing to a dumpfile only dump the filename. */
196 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
197 #if defined(DIR_SEPARATOR_2)
198 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
199 if (pos2
&& (!file
|| (pos2
> file
)))
208 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
210 fprintf (f
, "%s:%d", file
, loc
.line
);
213 /* Other gen programs really output line directives here, at least for
214 development it's right now more convenient to have line information
215 from the generated file. Still keep the directives as comment for now
216 to easily back-point to the meta-description. */
217 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
221 /* Pull in tree codes and builtin function codes from their
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
231 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
232 enum built_in_function
{
233 #include "builtins.def"
237 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239 #include "internal-fn.def"
244 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
245 CFN_##ENUM = int (ENUM),
246 #include "builtins.def"
248 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
249 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
250 #include "internal-fn.def"
255 #include "case-cfn-macros.h"
257 /* Return true if CODE represents a commutative tree code. Otherwise
260 commutative_tree_code (enum tree_code code
)
266 case MULT_HIGHPART_EXPR
:
281 case WIDEN_MULT_EXPR
:
282 case VEC_WIDEN_MULT_HI_EXPR
:
283 case VEC_WIDEN_MULT_LO_EXPR
:
284 case VEC_WIDEN_MULT_EVEN_EXPR
:
285 case VEC_WIDEN_MULT_ODD_EXPR
:
294 /* Return true if CODE represents a ternary tree code for which the
295 first two operands are commutative. Otherwise return false. */
297 commutative_ternary_tree_code (enum tree_code code
)
301 case WIDEN_MULT_PLUS_EXPR
:
302 case WIDEN_MULT_MINUS_EXPR
:
312 /* Return true if CODE is a comparison. */
315 comparison_code_p (enum tree_code code
)
342 /* Base class for all identifiers the parser knows. */
344 class id_base
: public nofree_ptr_hash
<id_base
>
347 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
349 id_base (id_kind
, const char *, int = -1);
355 /* hash_table support. */
356 static inline hashval_t
hash (const id_base
*);
357 static inline int equal (const id_base
*, const id_base
*);
361 id_base::hash (const id_base
*op
)
367 id_base::equal (const id_base
*op1
,
370 return (op1
->hashval
== op2
->hashval
371 && strcmp (op1
->id
, op2
->id
) == 0);
374 /* The special id "null", which matches nothing. */
375 static id_base
*null_id
;
377 /* Hashtable of known pattern operators. This is pre-seeded from
378 all known tree codes and all known builtin function ids. */
379 static hash_table
<id_base
> *operators
;
381 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
386 hashval
= htab_hash_string (id
);
389 /* Identifier that maps to a tree code. */
391 class operator_id
: public id_base
394 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
396 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
401 /* Identifier that maps to a builtin or internal function code. */
403 class fn_id
: public id_base
406 fn_id (enum built_in_function fn_
, const char *id_
)
407 : id_base (id_base::FN
, id_
), fn (fn_
) {}
408 fn_id (enum internal_fn fn_
, const char *id_
)
409 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
415 /* Identifier that maps to a user-defined predicate. */
417 class predicate_id
: public id_base
420 predicate_id (const char *id_
)
421 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
422 vec
<simplify
*> matchers
;
425 /* Identifier that maps to a operator defined by a 'for' directive. */
427 class user_id
: public id_base
430 user_id (const char *id_
, bool is_oper_list_
= false)
431 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
432 used (false), is_oper_list (is_oper_list_
) {}
433 vec
<id_base
*> substitutes
;
441 is_a_helper
<fn_id
*>::test (id_base
*id
)
443 return id
->kind
== id_base::FN
;
449 is_a_helper
<operator_id
*>::test (id_base
*id
)
451 return id
->kind
== id_base::CODE
;
457 is_a_helper
<predicate_id
*>::test (id_base
*id
)
459 return id
->kind
== id_base::PREDICATE
;
465 is_a_helper
<user_id
*>::test (id_base
*id
)
467 return id
->kind
== id_base::USER
;
470 /* If ID has a pair of consecutive, commutative operands, return the
471 index of the first, otherwise return -1. */
474 commutative_op (id_base
*id
)
476 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
478 if (commutative_tree_code (code
->code
)
479 || commutative_ternary_tree_code (code
->code
))
483 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
495 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
497 int res
= commutative_op (uid
->substitutes
[0]);
500 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
501 if (res
!= commutative_op (uid
->substitutes
[i
]))
508 /* Add a predicate identifier to the hash. */
510 static predicate_id
*
511 add_predicate (const char *id
)
513 predicate_id
*p
= new predicate_id (id
);
514 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
516 fatal ("duplicate id definition");
521 /* Add a tree code identifier to the hash. */
524 add_operator (enum tree_code code
, const char *id
,
525 const char *tcc
, unsigned nargs
)
527 if (strcmp (tcc
, "tcc_unary") != 0
528 && strcmp (tcc
, "tcc_binary") != 0
529 && strcmp (tcc
, "tcc_comparison") != 0
530 && strcmp (tcc
, "tcc_expression") != 0
531 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
532 && strcmp (tcc
, "tcc_reference") != 0
533 /* To have INTEGER_CST and friends as "predicate operators". */
534 && strcmp (tcc
, "tcc_constant") != 0
535 /* And allow CONSTRUCTOR for vector initializers. */
536 && !(code
== CONSTRUCTOR
)
537 /* Allow SSA_NAME as predicate operator. */
538 && !(code
== SSA_NAME
))
540 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
541 if (code
== ADDR_EXPR
)
543 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
544 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
546 fatal ("duplicate id definition");
550 /* Add a built-in or internal function identifier to the hash. ID is
551 the name of its CFN_* enumeration value. */
553 template <typename T
>
555 add_function (T code
, const char *id
)
557 fn_id
*fn
= new fn_id (code
, id
);
558 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
560 fatal ("duplicate id definition");
564 /* Helper for easy comparing ID with tree code CODE. */
567 operator==(id_base
&id
, enum tree_code code
)
569 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
570 return oid
->code
== code
;
574 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
577 get_operator (const char *id
, bool allow_null
= false)
579 if (allow_null
&& strcmp (id
, "null") == 0)
582 id_base
tem (id_base::CODE
, id
);
584 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
587 /* If this is a user-defined identifier track whether it was used. */
588 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
594 bool all_upper
= true;
595 bool all_lower
= true;
596 for (unsigned int i
= 0; id
[i
]; ++i
)
599 else if (ISLOWER (id
[i
]))
603 /* Try in caps with _EXPR appended. */
604 id2
= ACONCAT ((id
, "_EXPR", NULL
));
605 for (unsigned int i
= 0; id2
[i
]; ++i
)
606 id2
[i
] = TOUPPER (id2
[i
]);
608 else if (all_upper
&& startswith (id
, "IFN_"))
609 /* Try CFN_ instead of IFN_. */
610 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
611 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
612 /* Try prepending CFN_. */
613 id2
= ACONCAT (("CFN_", id
, NULL
));
617 new (&tem
) id_base (id_base::CODE
, id2
);
618 return operators
->find_with_hash (&tem
, tem
.hashval
);
621 /* Return the comparison operators that results if the operands are
622 swapped. This is safe for floating-point. */
625 swap_tree_comparison (operator_id
*p
)
637 return get_operator ("LT_EXPR");
639 return get_operator ("LE_EXPR");
641 return get_operator ("GT_EXPR");
643 return get_operator ("GE_EXPR");
645 return get_operator ("UNLT_EXPR");
647 return get_operator ("UNLE_EXPR");
649 return get_operator ("UNGT_EXPR");
651 return get_operator ("UNGE_EXPR");
657 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
660 /* The AST produced by parsing of the pattern definitions. */
665 /* The base class for operands. */
669 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
670 operand (enum op_type type_
, location_t loc_
)
671 : type (type_
), location (loc_
) {}
674 virtual void gen_transform (FILE *, int, const char *, bool, int,
675 const char *, capture_info
*,
678 { gcc_unreachable (); }
681 /* A predicate operand. Predicates are leafs in the AST. */
683 class predicate
: public operand
686 predicate (predicate_id
*p_
, location_t loc
)
687 : operand (OP_PREDICATE
, loc
), p (p_
) {}
691 /* An operand that constitutes an expression. Expressions include
692 function calls and user-defined predicate invocations. */
694 class expr
: public operand
697 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
698 : operand (OP_EXPR
, loc
), operation (operation_
),
699 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
700 is_generic (false), force_single_use (false), force_leaf (false),
703 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
704 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
705 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
706 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
707 void append_op (operand
*op
) { ops
.safe_push (op
); }
708 /* The operator and its operands. */
711 /* An explicitely specified type - used exclusively for conversions. */
712 const char *expr_type
;
713 /* Whether the operation is to be applied commutatively. This is
714 later lowered to two separate patterns. */
716 /* Whether the expression is expected to be in GENERIC form. */
718 /* Whether pushing any stmt to the sequence should be conditional
719 on this expression having a single-use. */
720 bool force_single_use
;
721 /* Whether in the result expression this should be a leaf node
722 with any children simplified down to simple operands. */
724 /* If non-zero, the group for optional handling. */
725 unsigned char opt_grp
;
726 void gen_transform (FILE *f
, int, const char *, bool, int,
727 const char *, capture_info
*,
728 dt_operand
** = 0, int = 0) override
;
731 /* An operator that is represented by native C code. This is always
732 a leaf operand in the AST. This class is also used to represent
733 the code to be generated for 'if' and 'with' expressions. */
735 class c_expr
: public operand
738 /* A mapping of an identifier and its replacement. Used to apply
744 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
747 c_expr (cpp_reader
*r_
, location_t loc
,
748 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
749 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
750 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
751 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
752 /* cpplib tokens and state to transform this back to source. */
755 cid_map_t
*capture_ids
;
756 /* The number of statements parsed (well, the number of ';'s). */
758 /* The identifier replacement vector. */
760 void gen_transform (FILE *f
, int, const char *, bool, int,
761 const char *, capture_info
*,
762 dt_operand
** = 0, int = 0) final override
;
765 /* A wrapper around another operand that captures its value. */
767 class capture
: public operand
770 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
771 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
773 /* Identifier index for the value. */
775 /* Whether in a match of two operands the compare should be for
776 equal values rather than equal atoms (boils down to a type
779 /* The captured value. */
781 void gen_transform (FILE *f
, int, const char *, bool, int,
782 const char *, capture_info
*,
783 dt_operand
** = 0, int = 0) final override
;
788 class if_expr
: public operand
791 if_expr (location_t loc
)
792 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
798 /* with expression. */
800 class with_expr
: public operand
803 with_expr (location_t loc
)
804 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
812 is_a_helper
<capture
*>::test (operand
*op
)
814 return op
->type
== operand::OP_CAPTURE
;
820 is_a_helper
<predicate
*>::test (operand
*op
)
822 return op
->type
== operand::OP_PREDICATE
;
828 is_a_helper
<c_expr
*>::test (operand
*op
)
830 return op
->type
== operand::OP_C_EXPR
;
836 is_a_helper
<expr
*>::test (operand
*op
)
838 return op
->type
== operand::OP_EXPR
;
844 is_a_helper
<if_expr
*>::test (operand
*op
)
846 return op
->type
== operand::OP_IF
;
852 is_a_helper
<with_expr
*>::test (operand
*op
)
854 return op
->type
== operand::OP_WITH
;
857 /* The main class of a pattern and its transform. This is used to
858 represent both (simplify ...) and (match ...) kinds. The AST
859 duplicates all outer 'if' and 'for' expressions here so each
860 simplify can exist in isolation. */
865 enum simplify_kind
{ SIMPLIFY
, MATCH
};
867 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
868 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
869 cid_map_t
*capture_ids_
)
870 : kind (kind_
), id (id_
), match (match_
), result (result_
),
871 for_vec (for_vec_
), for_subst_vec (vNULL
),
872 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
875 /* ID. This is kept to easily associate related simplifies expanded
876 from the same original one. */
878 /* The expression that is matched against the GENERIC or GIMPLE IL. */
880 /* For a (simplify ...) an expression with ifs and withs with the expression
881 produced when the pattern applies in the leafs.
882 For a (match ...) the leafs are either empty if it is a simple predicate
883 or the single expression specifying the matched operands. */
884 class operand
*result
;
885 /* Collected 'for' expression operators that have to be replaced
886 in the lowering phase. */
887 vec
<vec
<user_id
*> > for_vec
;
888 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
889 /* A map of capture identifiers to indexes. */
890 cid_map_t
*capture_ids
;
894 /* Debugging routines for dumping the AST. */
897 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
899 if (capture
*c
= dyn_cast
<capture
*> (o
))
901 if (c
->what
&& flattened
== false)
902 print_operand (c
->what
, f
, flattened
);
903 fprintf (f
, "@%u", c
->where
);
906 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
907 fprintf (f
, "%s", p
->p
->id
);
909 else if (is_a
<c_expr
*> (o
))
910 fprintf (f
, "c_expr");
912 else if (expr
*e
= dyn_cast
<expr
*> (o
))
914 if (e
->ops
.length () == 0)
915 fprintf (f
, "%s", e
->operation
->id
);
918 fprintf (f
, "(%s", e
->operation
->id
);
920 if (flattened
== false)
922 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
925 print_operand (e
->ops
[i
], f
, flattened
);
937 print_matches (class simplify
*s
, FILE *f
= stderr
)
939 fprintf (f
, "for expression: ");
940 print_operand (s
->match
, f
);
947 /* Lowering of commutative operators. */
950 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
951 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
953 if (n
== ops_vector
.length ())
955 vec
<operand
*> xv
= v
.copy ();
956 result
.safe_push (xv
);
960 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
962 v
[n
] = ops_vector
[n
][i
];
963 cartesian_product (ops_vector
, result
, v
, n
+ 1);
967 /* Lower OP to two operands in case it is marked as commutative. */
969 static vec
<operand
*>
970 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
972 vec
<operand
*> ret
= vNULL
;
974 if (capture
*c
= dyn_cast
<capture
*> (op
))
981 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
982 for (unsigned i
= 0; i
< v
.length (); ++i
)
984 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
991 expr
*e
= dyn_cast
<expr
*> (op
);
992 if (!e
|| e
->ops
.length () == 0)
998 vec
< vec
<operand
*> > ops_vector
= vNULL
;
999 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1000 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1002 auto_vec
< vec
<operand
*> > result
;
1003 auto_vec
<operand
*> v (e
->ops
.length ());
1004 v
.quick_grow_cleared (e
->ops
.length ());
1005 cartesian_product (ops_vector
, result
, v
, 0);
1008 for (unsigned i
= 0; i
< result
.length (); ++i
)
1010 expr
*ne
= new expr (e
);
1011 ne
->is_commutative
= false;
1012 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1013 ne
->append_op (result
[i
][j
]);
1017 if (!e
->is_commutative
)
1020 /* The operation is always binary if it isn't inherently commutative. */
1021 int natural_opno
= commutative_op (e
->operation
);
1022 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1023 for (unsigned i
= 0; i
< result
.length (); ++i
)
1025 expr
*ne
= new expr (e
);
1026 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1028 if (comparison_code_p (r
->code
))
1029 ne
->operation
= swap_tree_comparison (r
);
1031 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1033 bool found_compare
= false;
1034 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1035 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1037 if (comparison_code_p (q
->code
)
1038 && swap_tree_comparison (q
) != q
)
1040 found_compare
= true;
1046 user_id
*newop
= new user_id ("<internal>");
1047 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1049 id_base
*subst
= p
->substitutes
[j
];
1050 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1052 if (comparison_code_p (q
->code
))
1053 subst
= swap_tree_comparison (q
);
1055 newop
->substitutes
.safe_push (subst
);
1057 ne
->operation
= newop
;
1058 /* Search for 'p' inside the for vector and push 'newop'
1059 to the same level. */
1060 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1061 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1062 if (for_vec
[j
][k
] == p
)
1064 for_vec
[j
].safe_push (newop
);
1070 ne
->is_commutative
= false;
1071 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1073 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1074 ne
->append_op (result
[i
][old_j
]);
1082 /* Lower operations marked as commutative in the AST of S and push
1083 the resulting patterns to SIMPLIFIERS. */
1086 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1088 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1089 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1091 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1092 s
->for_vec
, s
->capture_ids
);
1093 simplifiers
.safe_push (ns
);
1097 /* Strip conditional operations using group GRP from O and its
1098 children if STRIP, else replace them with an unconditional operation. */
1101 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1103 if (capture
*c
= dyn_cast
<capture
*> (o
))
1106 return new capture (c
->location
, c
->where
,
1107 lower_opt (c
->what
, grp
, strip
),
1113 expr
*e
= dyn_cast
<expr
*> (o
);
1117 if (e
->opt_grp
== grp
)
1120 return lower_opt (e
->ops
[0], grp
, strip
);
1122 expr
*ne
= new expr (e
);
1124 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1128 expr
*ne
= new expr (e
);
1129 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1130 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1135 /* Determine whether O or its children uses the conditional operation
1139 has_opt (operand
*o
, unsigned char grp
)
1141 if (capture
*c
= dyn_cast
<capture
*> (o
))
1144 return has_opt (c
->what
, grp
);
1149 expr
*e
= dyn_cast
<expr
*> (o
);
1153 if (e
->opt_grp
== grp
)
1156 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1157 if (has_opt (e
->ops
[i
], grp
))
1163 /* Lower conditional convert operators in O, expanding it to a vector
1166 static vec
<operand
*>
1167 lower_opt (operand
*o
)
1169 vec
<operand
*> v1
= vNULL
, v2
;
1173 /* Conditional operations are lowered to a pattern with the
1174 operation and one without. All different conditional operation
1175 groups are lowered separately. */
1177 for (unsigned i
= 1; i
<= 10; ++i
)
1180 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1181 if (has_opt (v1
[j
], i
))
1183 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1184 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1190 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1191 v1
.safe_push (v2
[j
]);
1198 /* Lower conditional convert operators in the AST of S and push
1199 the resulting multiple patterns to SIMPLIFIERS. */
1202 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1204 vec
<operand
*> matchers
= lower_opt (s
->match
);
1205 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1207 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1208 s
->for_vec
, s
->capture_ids
);
1209 simplifiers
.safe_push (ns
);
1213 /* Lower the compare operand of COND_EXPRs to a
1214 GENERIC and a GIMPLE variant. */
1216 static vec
<operand
*>
1217 lower_cond (operand
*o
)
1219 vec
<operand
*> ro
= vNULL
;
1221 if (capture
*c
= dyn_cast
<capture
*> (o
))
1225 vec
<operand
*> lop
= vNULL
;
1226 lop
= lower_cond (c
->what
);
1228 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1229 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1235 expr
*e
= dyn_cast
<expr
*> (o
);
1236 if (!e
|| e
->ops
.length () == 0)
1242 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1243 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1244 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1246 auto_vec
< vec
<operand
*> > result
;
1247 auto_vec
<operand
*> v (e
->ops
.length ());
1248 v
.quick_grow_cleared (e
->ops
.length ());
1249 cartesian_product (ops_vector
, result
, v
, 0);
1251 for (unsigned i
= 0; i
< result
.length (); ++i
)
1253 expr
*ne
= new expr (e
);
1254 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1255 ne
->append_op (result
[i
][j
]);
1257 /* If this is a COND with a captured expression or an
1258 expression with two operands then also match a GENERIC
1259 form on the compare. */
1260 if (*e
->operation
== COND_EXPR
1261 && ((is_a
<capture
*> (e
->ops
[0])
1262 && as_a
<capture
*> (e
->ops
[0])->what
1263 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1265 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1266 || (is_a
<expr
*> (e
->ops
[0])
1267 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1270 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1271 ne
->append_op (result
[i
][j
]);
1272 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1274 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1275 expr
*cmp
= new expr (ocmp
);
1276 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1277 cmp
->append_op (ocmp
->ops
[j
]);
1278 cmp
->is_generic
= true;
1279 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1284 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1285 expr
*cmp
= new expr (ocmp
);
1286 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1287 cmp
->append_op (ocmp
->ops
[j
]);
1288 cmp
->is_generic
= true;
1298 /* Lower the compare operand of COND_EXPRs to a
1299 GENERIC and a GIMPLE variant. */
1302 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1304 vec
<operand
*> matchers
= lower_cond (s
->match
);
1305 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1307 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1308 s
->for_vec
, s
->capture_ids
);
1309 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1310 simplifiers
.safe_push (ns
);
1314 /* Return true if O refers to ID. */
1317 contains_id (operand
*o
, user_id
*id
)
1319 if (capture
*c
= dyn_cast
<capture
*> (o
))
1320 return c
->what
&& contains_id (c
->what
, id
);
1322 if (expr
*e
= dyn_cast
<expr
*> (o
))
1324 if (e
->operation
== id
)
1326 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1327 if (contains_id (e
->ops
[i
], id
))
1332 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1333 return (contains_id (w
->with
, id
)
1334 || contains_id (w
->subexpr
, id
));
1336 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1337 return (contains_id (ife
->cond
, id
)
1338 || contains_id (ife
->trueexpr
, id
)
1339 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1341 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1342 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1348 /* In AST operand O replace operator ID with operator WITH. */
1351 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1353 /* Deep-copy captures and expressions, replacing operations as
1355 if (capture
*c
= dyn_cast
<capture
*> (o
))
1359 return new capture (c
->location
, c
->where
,
1360 replace_id (c
->what
, id
, with
), c
->value_match
);
1362 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1364 expr
*ne
= new expr (e
);
1365 if (e
->operation
== id
)
1366 ne
->operation
= with
;
1367 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1368 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1371 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1373 with_expr
*nw
= new with_expr (w
->location
);
1374 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1375 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1378 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1380 if_expr
*nife
= new if_expr (ife
->location
);
1381 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1382 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1384 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1388 /* For c_expr we simply record a string replacement table which is
1389 applied at code-generation time. */
1390 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1392 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1393 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1394 return new c_expr (ce
->r
, ce
->location
,
1395 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1401 /* Return true if the binary operator OP is ok for delayed substitution
1402 during for lowering. */
1405 binary_ok (operator_id
*op
)
1412 case TRUNC_DIV_EXPR
:
1414 case FLOOR_DIV_EXPR
:
1415 case ROUND_DIV_EXPR
:
1416 case TRUNC_MOD_EXPR
:
1418 case FLOOR_MOD_EXPR
:
1419 case ROUND_MOD_EXPR
:
1421 case EXACT_DIV_EXPR
:
1433 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1436 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1438 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1439 unsigned worklist_start
= 0;
1440 auto_vec
<simplify
*> worklist
;
1441 worklist
.safe_push (sin
);
1443 /* Lower each recorded for separately, operating on the
1444 set of simplifiers created by the previous one.
1445 Lower inner-to-outer so inner for substitutes can refer
1446 to operators replaced by outer fors. */
1447 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1449 vec
<user_id
*>& ids
= for_vec
[fi
];
1450 unsigned n_ids
= ids
.length ();
1451 unsigned max_n_opers
= 0;
1452 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1453 for (unsigned i
= 0; i
< n_ids
; ++i
)
1455 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1456 max_n_opers
= ids
[i
]->substitutes
.length ();
1457 /* Require that all substitutes are of the same kind so that
1458 if we delay substitution to the result op code generation
1459 can look at the first substitute for deciding things like
1460 types of operands. */
1461 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1462 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1463 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1464 can_delay_subst
= false;
1465 else if (operator_id
*op
1466 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1469 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1470 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1471 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1473 /* Unfortunately we can't just allow all tcc_binary. */
1474 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1475 && strcmp (op0
->tcc
, "tcc_binary") == 0
1479 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1480 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1481 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1482 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1485 can_delay_subst
= false;
1487 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1490 can_delay_subst
= false;
1493 unsigned worklist_end
= worklist
.length ();
1494 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1496 simplify
*s
= worklist
[si
];
1497 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1499 operand
*match_op
= s
->match
;
1500 operand
*result_op
= s
->result
;
1501 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1503 for (unsigned i
= 0; i
< n_ids
; ++i
)
1505 user_id
*id
= ids
[i
];
1506 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1508 && (contains_id (match_op
, id
)
1509 || contains_id (result_op
, id
)))
1514 subst
.quick_push (std::make_pair (id
, oper
));
1515 match_op
= replace_id (match_op
, id
, oper
);
1517 && !can_delay_subst
)
1518 result_op
= replace_id (result_op
, id
, oper
);
1523 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1524 vNULL
, s
->capture_ids
);
1525 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1528 ns
->for_subst_vec
.safe_splice (subst
);
1530 worklist
.safe_push (ns
);
1533 worklist_start
= worklist_end
;
1536 /* Copy out the result from the last for lowering. */
1537 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1538 simplifiers
.safe_push (worklist
[i
]);
1541 /* Lower the AST for everything in SIMPLIFIERS. */
1544 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1546 auto_vec
<simplify
*> out_simplifiers
;
1547 for (auto s
: simplifiers
)
1548 lower_opt (s
, out_simplifiers
);
1550 simplifiers
.truncate (0);
1551 for (auto s
: out_simplifiers
)
1552 lower_commutative (s
, simplifiers
);
1554 /* Lower for needs to happen before lowering cond
1555 to support (for cnd (cond vec_cond)). This is
1556 safe as substitution delay does not happen for
1557 cond or vec_cond. */
1558 out_simplifiers
.truncate (0);
1559 for (auto s
: simplifiers
)
1560 lower_for (s
, out_simplifiers
);
1562 simplifiers
.truncate (0);
1564 for (auto s
: out_simplifiers
)
1565 lower_cond (s
, simplifiers
);
1567 simplifiers
.safe_splice (out_simplifiers
);
1573 /* The decision tree built for generating GIMPLE and GENERIC pattern
1574 matching code. It represents the 'match' expression of all
1575 simplifies and has those as its leafs. */
1579 /* A hash-map collecting semantically equivalent leafs in the decision
1580 tree for splitting out to separate functions. */
1589 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1592 static inline hashval_t
hash (const key_type
&);
1593 static inline bool equal_keys (const key_type
&, const key_type
&);
1594 template <typename T
> static inline void remove (T
&) {}
1597 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1600 /* Current simplifier ID we are processing during insertion into the
1602 static unsigned current_id
;
1604 /* Decision tree base class, used for DT_NODE. */
1609 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1614 vec
<dt_node
*> kids
;
1618 unsigned total_size
;
1621 dt_node (enum dt_type type_
, dt_node
*parent_
)
1622 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1624 dt_node
*append_node (dt_node
*);
1625 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1626 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1627 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1629 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1631 virtual void gen (FILE *, int, bool, int) {}
1633 void gen_kids (FILE *, int, bool, int);
1634 void gen_kids_1 (FILE *, int, bool, int,
1635 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1636 const vec
<dt_operand
*> &, const vec
<dt_operand
*> &,
1637 const vec
<dt_operand
*> &, const vec
<dt_node
*> &);
1639 void analyze (sinfo_map_t
&);
1642 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1644 class dt_operand
: public dt_node
1648 dt_operand
*match_dop
;
1653 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1654 dt_operand
*parent_
, unsigned pos_
)
1655 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1656 pos (pos_
), value_match (false), for_id (current_id
) {}
1658 void gen (FILE *, int, bool, int) final override
;
1659 unsigned gen_predicate (FILE *, int, const char *, bool);
1660 unsigned gen_match_op (FILE *, int, const char *, bool);
1662 unsigned gen_gimple_expr (FILE *, int, int);
1663 unsigned gen_generic_expr (FILE *, int, const char *);
1665 char *get_name (char *);
1666 void gen_opname (char *, unsigned);
1669 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1671 class dt_simplify
: public dt_node
1675 unsigned pattern_no
;
1676 dt_operand
**indexes
;
1679 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1680 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1681 indexes (indexes_
), info (NULL
) {}
1683 void gen_1 (FILE *, int, bool, operand
*);
1684 void gen (FILE *f
, int, bool, int) final override
;
1690 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1692 return (n
->type
== dt_node::DT_OPERAND
1693 || n
->type
== dt_node::DT_MATCH
1694 || n
->type
== dt_node::DT_TRUE
);
1700 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1702 return n
->type
== dt_node::DT_SIMPLIFY
;
1707 /* A container for the actual decision tree. */
1714 void insert (class simplify
*, unsigned);
1715 void gen (FILE *f
, bool gimple
);
1716 void print (FILE *f
= stderr
);
1718 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1720 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1721 unsigned pos
= 0, dt_node
*parent
= 0);
1722 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1723 static bool cmp_node (dt_node
*, dt_node
*);
1724 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1727 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1730 cmp_operand (operand
*o1
, operand
*o2
)
1732 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1735 if (o1
->type
== operand::OP_PREDICATE
)
1737 predicate
*p1
= as_a
<predicate
*>(o1
);
1738 predicate
*p2
= as_a
<predicate
*>(o2
);
1739 return p1
->p
== p2
->p
;
1741 else if (o1
->type
== operand::OP_EXPR
)
1743 expr
*e1
= static_cast<expr
*>(o1
);
1744 expr
*e2
= static_cast<expr
*>(o2
);
1745 return (e1
->operation
== e2
->operation
1746 && e1
->is_generic
== e2
->is_generic
);
1752 /* Compare two decision tree nodes N1 and N2 and return true if they
1756 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1758 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1764 if (n1
->type
== dt_node::DT_TRUE
)
1767 if (n1
->type
== dt_node::DT_OPERAND
)
1768 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1769 (as_a
<dt_operand
*> (n2
))->op
);
1770 else if (n1
->type
== dt_node::DT_MATCH
)
1771 return (((as_a
<dt_operand
*> (n1
))->match_dop
1772 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1773 && ((as_a
<dt_operand
*> (n1
))->value_match
1774 == (as_a
<dt_operand
*> (n2
))->value_match
));
1778 /* Search OPS for a decision tree node like P and return it if found. */
1781 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1783 /* We can merge adjacent DT_TRUE. */
1784 if (p
->type
== dt_node::DT_TRUE
1786 && ops
.last ()->type
== dt_node::DT_TRUE
)
1788 dt_operand
*true_node
= NULL
;
1789 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1791 /* But we can't merge across DT_TRUE nodes as they serve as
1792 pattern order barriers to make sure that patterns apply
1793 in order of appearance in case multiple matches are possible. */
1794 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1797 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1798 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1800 if (decision_tree::cmp_node (ops
[i
], p
))
1802 /* Unless we are processing the same pattern or the blocking
1803 pattern is before the one we are going to merge with. */
1805 && true_node
->for_id
!= current_id
1806 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1810 location_t p_loc
= 0;
1811 if (p
->type
== dt_node::DT_OPERAND
)
1812 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1813 location_t op_loc
= 0;
1814 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1815 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1816 location_t true_loc
= 0;
1817 true_loc
= true_node
->op
->location
;
1819 "failed to merge decision tree node");
1821 "with the following");
1822 warning_at (true_loc
,
1823 "because of the following which serves as ordering "
1834 /* Append N to the decision tree if it there is not already an existing
1838 dt_node::append_node (dt_node
*n
)
1842 kid
= decision_tree::find_node (kids
, n
);
1847 n
->level
= this->level
+ 1;
1852 /* Append OP to the decision tree. */
1855 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1857 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1858 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1859 return append_node (n
);
1862 /* Append a DT_TRUE decision tree node. */
1865 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1867 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1868 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1869 return append_node (n
);
1872 /* Append a DT_MATCH decision tree node. */
1875 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1876 dt_node
*parent
, unsigned pos
)
1878 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1879 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1880 return append_node (n
);
1883 /* Append S to the decision tree. */
1886 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1887 dt_operand
**indexes
)
1890 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1891 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1892 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1894 || s
->match
->location
!= s2
->s
->match
->location
))
1896 /* With a nested patters, it's hard to avoid these in order
1897 to keep match.pd rules relatively small. */
1898 warning_at (s
->match
->location
, "duplicate pattern");
1899 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1900 print_operand (s
->match
, stderr
);
1901 fprintf (stderr
, "\n");
1903 return append_node (n
);
1906 /* Analyze the node and its children. */
1909 dt_node::analyze (sinfo_map_t
&map
)
1915 if (type
== DT_SIMPLIFY
)
1917 /* Populate the map of equivalent simplifies. */
1918 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1920 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1935 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1937 kids
[i
]->analyze (map
);
1938 num_leafs
+= kids
[i
]->num_leafs
;
1939 total_size
+= kids
[i
]->total_size
;
1940 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1944 /* Insert O into the decision tree and return the decision tree node found
1948 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1949 unsigned pos
, dt_node
*parent
)
1951 dt_node
*q
, *elm
= 0;
1953 if (capture
*c
= dyn_cast
<capture
*> (o
))
1955 unsigned capt_index
= c
->where
;
1957 if (indexes
[capt_index
] == 0)
1960 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1963 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1966 // get to the last capture
1967 for (operand
*what
= c
->what
;
1968 what
&& is_a
<capture
*> (what
);
1969 c
= as_a
<capture
*> (what
), what
= c
->what
)
1974 unsigned cc_index
= c
->where
;
1975 dt_operand
*match_op
= indexes
[cc_index
];
1977 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1978 elm
= decision_tree::find_node (p
->kids
, &temp
);
1982 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1983 match
.value_match
= c
->value_match
;
1984 elm
= decision_tree::find_node (p
->kids
, &match
);
1989 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1990 elm
= decision_tree::find_node (p
->kids
, &temp
);
1994 gcc_assert (elm
->type
== dt_node::DT_TRUE
1995 || elm
->type
== dt_node::DT_OPERAND
1996 || elm
->type
== dt_node::DT_MATCH
);
1997 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2002 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2003 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2005 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2010 p
= p
->append_op (o
, parent
, pos
);
2013 if (expr
*e
= dyn_cast
<expr
*>(o
))
2015 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2016 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2022 /* Insert S into the decision tree. */
2025 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2028 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2029 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2030 p
->append_simplify (s
, pattern_no
, indexes
);
2033 /* Debug functions to dump the decision tree. */
2036 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2038 if (p
->type
== dt_node::DT_NODE
)
2039 fprintf (f
, "root");
2043 for (unsigned i
= 0; i
< indent
; i
++)
2046 if (p
->type
== dt_node::DT_OPERAND
)
2048 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2049 print_operand (dop
->op
, f
, true);
2051 else if (p
->type
== dt_node::DT_TRUE
)
2052 fprintf (f
, "true");
2053 else if (p
->type
== dt_node::DT_MATCH
)
2054 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2055 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2057 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2058 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2059 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2060 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2063 if (is_a
<dt_operand
*> (p
))
2064 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2067 fprintf (stderr
, " (%p, %p), %u, %u\n",
2068 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2070 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2071 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2075 decision_tree::print (FILE *f
)
2077 return decision_tree::print_node (root
, f
);
2081 /* For GENERIC we have to take care of wrapping multiple-used
2082 expressions with side-effects in save_expr and preserve side-effects
2083 of expressions with omit_one_operand. Analyze captures in
2084 match, result and with expressions and perform early-outs
2085 on the outermost match expression operands for cases we cannot
2091 capture_info (simplify
*s
, operand
*, bool);
2092 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2093 bool walk_result (operand
*o
, bool, operand
*);
2094 void walk_c_expr (c_expr
*);
2100 bool force_no_side_effects_p
;
2101 bool force_single_use
;
2102 bool cond_expr_cond_p
;
2103 unsigned long toplevel_msk
;
2104 unsigned match_use_count
;
2105 unsigned result_use_count
;
2110 auto_vec
<cinfo
> info
;
2111 unsigned long force_no_side_effects
;
2115 /* Analyze captures in S. */
2117 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2122 if (s
->kind
== simplify::MATCH
)
2124 force_no_side_effects
= -1;
2128 force_no_side_effects
= 0;
2129 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2130 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2131 info
[i
].same_as
= i
;
2133 e
= as_a
<expr
*> (s
->match
);
2134 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2135 walk_match (e
->ops
[i
], i
,
2136 (i
!= 0 && *e
->operation
== COND_EXPR
)
2137 || *e
->operation
== TRUTH_ANDIF_EXPR
2138 || *e
->operation
== TRUTH_ORIF_EXPR
,
2139 i
== 0 && *e
->operation
== COND_EXPR
);
2141 walk_result (s
->result
, false, result
);
2144 /* Analyze captures in the match expression piece O. */
2147 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2148 bool conditional_p
, bool cond_expr_cond_p
)
2150 if (capture
*c
= dyn_cast
<capture
*> (o
))
2152 unsigned where
= c
->where
;
2153 info
[where
].match_use_count
++;
2154 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2155 info
[where
].force_no_side_effects_p
|= conditional_p
;
2156 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2161 /* Recurse to exprs and captures. */
2162 if (is_a
<capture
*> (c
->what
)
2163 || is_a
<expr
*> (c
->what
))
2164 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2165 /* We need to look past multiple captures to find a captured
2166 expression as with conditional converts two captures
2167 can be collapsed onto the same expression. Also collect
2168 what captures capture the same thing. */
2169 while (c
->what
&& is_a
<capture
*> (c
->what
))
2171 c
= as_a
<capture
*> (c
->what
);
2172 if (info
[c
->where
].same_as
!= c
->where
2173 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2174 fatal_at (c
->location
, "cannot handle this collapsed capture");
2175 info
[c
->where
].same_as
= info
[where
].same_as
;
2177 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2180 && (e
= dyn_cast
<expr
*> (c
->what
)))
2182 /* Zero-operand expression captures like ADDR_EXPR@0 are
2183 similar as predicates -- if they are not mentioned in
2184 the result we have to force them to have no side-effects. */
2185 if (e
->ops
.length () != 0)
2186 info
[where
].expr_p
= true;
2187 info
[where
].force_single_use
|= e
->force_single_use
;
2190 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2192 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2194 bool cond_p
= conditional_p
;
2195 bool expr_cond_p
= false;
2196 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2198 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2199 || *e
->operation
== TRUTH_ORIF_EXPR
)
2202 && *e
->operation
== COND_EXPR
)
2204 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2207 else if (is_a
<predicate
*> (o
))
2209 /* Mark non-captured leafs toplevel arg for checking. */
2210 force_no_side_effects
|= 1 << toplevel_arg
;
2213 warning_at (o
->location
,
2214 "forcing no side-effects on possibly lost leaf");
2220 /* Analyze captures in the result expression piece O. Return true
2221 if RESULT was visited in one of the children. Only visit
2222 non-if/with children if they are rooted on RESULT. */
2225 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2227 if (capture
*c
= dyn_cast
<capture
*> (o
))
2229 unsigned where
= info
[c
->where
].same_as
;
2230 info
[where
].result_use_count
++;
2231 /* If we substitute an expression capture we don't know
2232 which captures this will end up using (well, we don't
2233 compute that). Force the uses to be side-effect free
2234 which means forcing the toplevels that reach the
2235 expression side-effect free. */
2236 if (info
[where
].expr_p
)
2237 force_no_side_effects
|= info
[where
].toplevel_msk
;
2238 /* Mark CSE capture uses as forced to have no side-effects. */
2240 && is_a
<expr
*> (c
->what
))
2242 info
[where
].cse_p
= true;
2243 walk_result (c
->what
, true, result
);
2246 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2248 id_base
*opr
= e
->operation
;
2249 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2250 opr
= uid
->substitutes
[0];
2251 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2253 bool cond_p
= conditional_p
;
2254 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2256 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2257 || *e
->operation
== TRUTH_ORIF_EXPR
)
2259 walk_result (e
->ops
[i
], cond_p
, result
);
2262 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2264 /* 'if' conditions should be all fine. */
2265 if (ie
->trueexpr
== result
)
2267 walk_result (ie
->trueexpr
, false, result
);
2270 if (ie
->falseexpr
== result
)
2272 walk_result (ie
->falseexpr
, false, result
);
2276 if (is_a
<if_expr
*> (ie
->trueexpr
)
2277 || is_a
<with_expr
*> (ie
->trueexpr
))
2278 res
|= walk_result (ie
->trueexpr
, false, result
);
2280 && (is_a
<if_expr
*> (ie
->falseexpr
)
2281 || is_a
<with_expr
*> (ie
->falseexpr
)))
2282 res
|= walk_result (ie
->falseexpr
, false, result
);
2285 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2287 bool res
= (we
->subexpr
== result
);
2289 || is_a
<if_expr
*> (we
->subexpr
)
2290 || is_a
<with_expr
*> (we
->subexpr
))
2291 res
|= walk_result (we
->subexpr
, false, result
);
2293 walk_c_expr (we
->with
);
2296 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2304 /* Look for captures in the C expr E. */
2307 capture_info::walk_c_expr (c_expr
*e
)
2309 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2310 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2311 really escape through. */
2312 unsigned p_depth
= 0;
2313 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2315 const cpp_token
*t
= &e
->code
[i
];
2316 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2318 if (t
->type
== CPP_NAME
2319 && (strcmp ((const char *)CPP_HASHNODE
2320 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2321 || strcmp ((const char *)CPP_HASHNODE
2322 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2323 || strcmp ((const char *)CPP_HASHNODE
2324 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2325 || ((id
= get_operator ((const char *)CPP_HASHNODE
2326 (t
->val
.node
.node
)->ident
.str
))
2327 && is_a
<predicate_id
*> (id
)))
2328 && n
->type
== CPP_OPEN_PAREN
)
2330 else if (t
->type
== CPP_CLOSE_PAREN
2333 else if (p_depth
== 0
2334 && t
->type
== CPP_ATSIGN
2335 && (n
->type
== CPP_NUMBER
2336 || n
->type
== CPP_NAME
)
2337 && !(n
->flags
& PREV_WHITE
))
2340 if (n
->type
== CPP_NUMBER
)
2341 id1
= (const char *)n
->val
.str
.text
;
2343 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2344 unsigned *where
= e
->capture_ids
->get(id1
);
2346 fatal_at (n
, "unknown capture id '%s'", id1
);
2347 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2350 warning_at (t
, "capture escapes");
2356 /* The current label failing the current matched pattern during
2358 static char *fail_label
;
2360 /* Code generation off the decision tree and the refered AST nodes. */
2363 is_conversion (id_base
*op
)
2365 return (*op
== CONVERT_EXPR
2367 || *op
== FLOAT_EXPR
2368 || *op
== FIX_TRUNC_EXPR
2369 || *op
== VIEW_CONVERT_EXPR
);
2372 /* Get the type to be used for generating operand POS of OP from the
2376 get_operand_type (id_base
*op
, unsigned pos
,
2377 const char *in_type
,
2378 const char *expr_type
,
2379 const char *other_oprnd_type
)
2381 /* Generally operands whose type does not match the type of the
2382 expression generated need to know their types but match and
2383 thus can fall back to 'other_oprnd_type'. */
2384 if (is_conversion (op
))
2385 return other_oprnd_type
;
2386 else if (*op
== REALPART_EXPR
2387 || *op
== IMAGPART_EXPR
)
2388 return other_oprnd_type
;
2389 else if (is_a
<operator_id
*> (op
)
2390 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2391 return other_oprnd_type
;
2392 else if (*op
== COND_EXPR
2394 return "boolean_type_node";
2395 else if (startswith (op
->id
, "CFN_COND_"))
2397 /* IFN_COND_* operands 1 and later by default have the same type
2398 as the result. The type of operand 0 needs to be specified
2400 if (pos
> 0 && expr_type
)
2402 else if (pos
> 0 && in_type
)
2409 /* Otherwise all types should match - choose one in order of
2416 return other_oprnd_type
;
2420 /* Generate transform code for an expression. */
2423 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2424 int depth
, const char *in_type
, capture_info
*cinfo
,
2425 dt_operand
**indexes
, int)
2427 id_base
*opr
= operation
;
2428 /* When we delay operator substituting during lowering of fors we
2429 make sure that for code-gen purposes the effects of each substitute
2430 are the same. Thus just look at that. */
2431 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2432 opr
= uid
->substitutes
[0];
2434 bool conversion_p
= is_conversion (opr
);
2435 const char *type
= expr_type
;
2438 /* If there was a type specification in the pattern use it. */
2440 else if (conversion_p
)
2441 /* For conversions we need to build the expression using the
2442 outer type passed in. */
2444 else if (*opr
== REALPART_EXPR
2445 || *opr
== IMAGPART_EXPR
)
2447 /* __real and __imag use the component type of its operand. */
2448 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2452 else if (is_a
<operator_id
*> (opr
)
2453 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2455 /* comparisons use boolean_type_node (or what gets in), but
2456 their operands need to figure out the types themselves. */
2461 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2466 else if (*opr
== COND_EXPR
2467 || *opr
== VEC_COND_EXPR
2468 || startswith (opr
->id
, "CFN_COND_"))
2470 /* Conditions are of the same type as their first alternative. */
2471 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2476 /* Other operations are of the same type as their first operand. */
2477 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2481 fatal_at (location
, "cannot determine type of operand");
2483 fprintf_indent (f
, indent
, "{\n");
2485 fprintf_indent (f
, indent
,
2486 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2488 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2489 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2492 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2494 = get_operand_type (opr
, i
, in_type
, expr_type
,
2495 i
== 0 ? NULL
: op0type
);
2496 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2498 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2501 const char *opr_name
;
2502 if (*operation
== CONVERT_EXPR
)
2503 opr_name
= "NOP_EXPR";
2505 opr_name
= operation
->id
;
2509 if (*opr
== CONVERT_EXPR
)
2511 fprintf_indent (f
, indent
,
2512 "if (%s != TREE_TYPE (_o%d[0])\n",
2514 fprintf_indent (f
, indent
,
2515 " && !useless_type_conversion_p (%s, TREE_TYPE "
2518 fprintf_indent (f
, indent
+ 2, "{\n");
2521 /* ??? Building a stmt can fail for various reasons here, seq being
2522 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2523 So if we fail here we should continue matching other patterns. */
2524 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2525 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2526 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2527 fprintf (f
, ", _o%d[%u]", depth
, i
);
2528 fprintf (f
, ");\n");
2529 fprintf_indent (f
, indent
, "tem_op.resimplify (lseq, valueize);\n");
2530 fprintf_indent (f
, indent
,
2531 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2532 !force_leaf
? "lseq" : "NULL");
2533 fprintf_indent (f
, indent
,
2534 "if (!_r%d) goto %s;\n",
2536 if (*opr
== CONVERT_EXPR
)
2539 fprintf_indent (f
, indent
, " }\n");
2540 fprintf_indent (f
, indent
, "else\n");
2541 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2546 if (*opr
== CONVERT_EXPR
)
2548 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2552 if (opr
->kind
== id_base::CODE
)
2553 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2554 depth
, ops
.length(), opr_name
, type
);
2556 fprintf_indent (f
, indent
, "_r%d = maybe_build_call_expr_loc (loc, "
2557 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2558 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2559 fprintf (f
, ", _o%d[%u]", depth
, i
);
2560 fprintf (f
, ");\n");
2561 if (opr
->kind
!= id_base::CODE
)
2563 fprintf_indent (f
, indent
, "if (!_r%d)\n", depth
);
2564 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2568 fprintf_indent (f
, indent
, "if (EXPR_P (_r%d))\n", depth
);
2569 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2571 if (*opr
== CONVERT_EXPR
)
2574 fprintf_indent (f
, indent
, "else\n");
2575 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2578 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2580 fprintf_indent (f
, indent
, "}\n");
2583 /* Generate code for a c_expr which is either the expression inside
2584 an if statement or a sequence of statements which computes a
2585 result to be stored to DEST. */
2588 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2589 bool, int, const char *, capture_info
*,
2592 if (dest
&& nr_stmts
== 1)
2593 fprintf_indent (f
, indent
, "%s = ", dest
);
2595 unsigned stmt_nr
= 1;
2597 for (unsigned i
= 0; i
< code
.length (); ++i
)
2599 const cpp_token
*token
= &code
[i
];
2601 /* We can't recover from all lexing losses but we can roughly restore line
2602 breaks from location info. */
2603 const line_map_ordinary
*map
;
2604 linemap_resolve_location (line_table
, token
->src_loc
,
2605 LRK_SPELLING_LOCATION
, &map
);
2606 expanded_location loc
= linemap_expand_location (line_table
, map
,
2608 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2610 prev_line
= loc
.line
;
2612 /* Replace captures for code-gen. */
2613 if (token
->type
== CPP_ATSIGN
)
2615 const cpp_token
*n
= &code
[i
+1];
2616 if ((n
->type
== CPP_NUMBER
2617 || n
->type
== CPP_NAME
)
2618 && !(n
->flags
& PREV_WHITE
))
2620 if (token
->flags
& PREV_WHITE
)
2623 if (n
->type
== CPP_NUMBER
)
2624 id
= (const char *)n
->val
.str
.text
;
2626 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2627 unsigned *cid
= capture_ids
->get (id
);
2629 fatal_at (token
, "unknown capture id");
2630 fprintf (f
, "captures[%u]", *cid
);
2636 if (token
->flags
& PREV_WHITE
)
2639 if (token
->type
== CPP_NAME
)
2641 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2643 for (j
= 0; j
< ids
.length (); ++j
)
2645 if (strcmp (id
, ids
[j
].id
) == 0)
2647 fprintf (f
, "%s", ids
[j
].oper
);
2651 if (j
< ids
.length ())
2655 /* Output the token as string. */
2656 char *tk
= (char *)cpp_token_as_text (r
, token
);
2659 if (token
->type
== CPP_SEMICOLON
)
2662 if (dest
&& stmt_nr
== nr_stmts
)
2663 fprintf_indent (f
, indent
, "%s = ", dest
);
2669 /* Generate transform code for a capture. */
2672 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2673 int depth
, const char *in_type
, capture_info
*cinfo
,
2674 dt_operand
**indexes
, int cond_handling
)
2676 if (what
&& is_a
<expr
*> (what
))
2678 if (indexes
[where
] == 0)
2681 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2682 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2687 /* If in GENERIC some capture is used multiple times, unshare it except
2688 when emitting the last use. */
2690 && cinfo
->info
.exists ()
2691 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2693 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2695 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2698 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2700 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2701 with substituting a capture of that. */
2703 && cond_handling
!= 0
2704 && cinfo
->info
[where
].cond_expr_cond_p
)
2706 /* If substituting into a cond_expr condition, unshare. */
2707 if (cond_handling
== 1)
2708 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2709 /* If substituting elsewhere we might need to decompose it. */
2710 else if (cond_handling
== 2)
2712 /* ??? Returning false here will also not allow any other patterns
2713 to match unless this generator was split out. */
2714 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2715 fprintf_indent (f
, indent
, " {\n");
2716 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2717 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2719 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2720 " TREE_OPERAND (%s, 1));\n",
2721 dest
, dest
, dest
, dest
, dest
);
2722 fprintf_indent (f
, indent
, " }\n");
2727 /* Return the name of the operand representing the decision tree node.
2728 Use NAME as space to generate it. */
2731 dt_operand::get_name (char *name
)
2734 sprintf (name
, "t");
2735 else if (parent
->level
== 1)
2736 sprintf (name
, "_p%u", pos
);
2737 else if (parent
->type
== dt_node::DT_MATCH
)
2738 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2740 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2744 /* Fill NAME with the operand name at position POS. */
2747 dt_operand::gen_opname (char *name
, unsigned pos
)
2750 sprintf (name
, "_p%u", pos
);
2752 sprintf (name
, "_q%u%u", level
, pos
);
2755 /* Generate matching code for the decision tree operand which is
2759 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2761 predicate
*p
= as_a
<predicate
*> (op
);
2763 if (p
->p
->matchers
.exists ())
2765 /* If this is a predicate generated from a pattern mangle its
2766 name and pass on the valueize hook. */
2768 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2771 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2774 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2775 fprintf_indent (f
, indent
+ 2, "{\n");
2779 /* Generate matching code for the decision tree operand which is
2783 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2785 char match_opname
[20];
2786 match_dop
->get_name (match_opname
);
2788 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2789 "|| operand_equal_p (%s, %s, 0))\n",
2790 opname
, match_opname
, opname
, opname
, match_opname
);
2792 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2793 "|| (operand_equal_p (%s, %s, 0) "
2794 "&& types_match (%s, %s)))\n",
2795 opname
, match_opname
, opname
, opname
, match_opname
,
2796 opname
, match_opname
);
2797 fprintf_indent (f
, indent
+ 2, "{\n");
2801 /* Generate GIMPLE matching code for the decision tree operand. */
2804 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2806 expr
*e
= static_cast<expr
*> (op
);
2807 id_base
*id
= e
->operation
;
2808 unsigned n_ops
= e
->ops
.length ();
2809 unsigned n_braces
= 0;
2811 for (unsigned i
= 0; i
< n_ops
; ++i
)
2813 char child_opname
[20];
2814 gen_opname (child_opname
, i
);
2816 if (id
->kind
== id_base::CODE
)
2819 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2820 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2822 /* ??? If this is a memory operation we can't (and should not)
2823 match this. The only sensible operand types are
2824 SSA names and invariants. */
2829 fprintf_indent (f
, indent
,
2830 "tree %s = TREE_OPERAND (%s, %i);\n",
2831 child_opname
, opname
, i
);
2834 fprintf_indent (f
, indent
,
2835 "tree %s = TREE_OPERAND "
2836 "(gimple_assign_rhs1 (_a%d), %i);\n",
2837 child_opname
, depth
, i
);
2838 fprintf_indent (f
, indent
,
2839 "if ((TREE_CODE (%s) == SSA_NAME\n",
2841 fprintf_indent (f
, indent
,
2842 " || is_gimple_min_invariant (%s)))\n",
2844 fprintf_indent (f
, indent
,
2848 fprintf_indent (f
, indent
,
2849 "%s = do_valueize (valueize, %s);\n",
2850 child_opname
, child_opname
);
2854 fprintf_indent (f
, indent
,
2855 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2856 child_opname
, i
+ 1, depth
);
2859 fprintf_indent (f
, indent
,
2860 "tree %s = gimple_call_arg (_c%d, %u);\n",
2861 child_opname
, depth
, i
);
2862 fprintf_indent (f
, indent
,
2863 "%s = do_valueize (valueize, %s);\n",
2864 child_opname
, child_opname
);
2866 /* While the toplevel operands are canonicalized by the caller
2867 after valueizing operands of sub-expressions we have to
2868 re-canonicalize operand order. */
2869 int opno
= commutative_op (id
);
2872 char child_opname0
[20], child_opname1
[20];
2873 gen_opname (child_opname0
, opno
);
2874 gen_opname (child_opname1
, opno
+ 1);
2875 fprintf_indent (f
, indent
,
2876 "if (tree_swap_operands_p (%s, %s))\n",
2877 child_opname0
, child_opname1
);
2878 fprintf_indent (f
, indent
,
2879 " std::swap (%s, %s);\n",
2880 child_opname0
, child_opname1
);
2886 /* Generate GENERIC matching code for the decision tree operand. */
2889 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2891 expr
*e
= static_cast<expr
*> (op
);
2892 unsigned n_ops
= e
->ops
.length ();
2894 for (unsigned i
= 0; i
< n_ops
; ++i
)
2896 char child_opname
[20];
2897 gen_opname (child_opname
, i
);
2899 if (e
->operation
->kind
== id_base::CODE
)
2900 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2901 child_opname
, opname
, i
);
2903 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2904 child_opname
, opname
, i
);
2910 /* Generate matching code for the children of the decision tree node. */
2913 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2915 auto_vec
<dt_operand
*> gimple_exprs
;
2916 auto_vec
<dt_operand
*> generic_exprs
;
2917 auto_vec
<dt_operand
*> fns
;
2918 auto_vec
<dt_operand
*> generic_fns
;
2919 auto_vec
<dt_operand
*> preds
;
2920 auto_vec
<dt_node
*> others
;
2922 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2924 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2926 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2927 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2929 if (e
->ops
.length () == 0
2930 /* In GIMPLE a CONSTRUCTOR always appears in a
2931 separate definition. */
2932 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2934 generic_exprs
.safe_push (op
);
2935 /* But ADDR_EXPRs can appear directly when invariant
2936 and in a separate definition when not. */
2937 if (gimple
&& *e
->operation
== ADDR_EXPR
)
2938 gimple_exprs
.safe_push (op
);
2940 else if (e
->operation
->kind
== id_base::FN
)
2945 generic_fns
.safe_push (op
);
2947 else if (e
->operation
->kind
== id_base::PREDICATE
)
2948 preds
.safe_push (op
);
2951 if (gimple
&& !e
->is_generic
)
2952 gimple_exprs
.safe_push (op
);
2954 generic_exprs
.safe_push (op
);
2957 else if (op
->op
->type
== operand::OP_PREDICATE
)
2958 others
.safe_push (kids
[i
]);
2962 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2963 others
.safe_push (kids
[i
]);
2964 else if (kids
[i
]->type
== dt_node::DT_MATCH
2965 || kids
[i
]->type
== dt_node::DT_TRUE
)
2967 /* A DT_TRUE operand serves as a barrier - generate code now
2968 for what we have collected sofar.
2969 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2970 dependent matches to get out-of-order. Generate code now
2971 for what we have collected sofar. */
2972 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2973 fns
, generic_fns
, preds
, others
);
2974 /* And output the true operand itself. */
2975 kids
[i
]->gen (f
, indent
, gimple
, depth
);
2976 gimple_exprs
.truncate (0);
2977 generic_exprs
.truncate (0);
2979 generic_fns
.truncate (0);
2981 others
.truncate (0);
2987 /* Generate code for the remains. */
2988 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2989 fns
, generic_fns
, preds
, others
);
2992 /* Generate matching code for the children of the decision tree node. */
2995 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
2996 const vec
<dt_operand
*> &gimple_exprs
,
2997 const vec
<dt_operand
*> &generic_exprs
,
2998 const vec
<dt_operand
*> &fns
,
2999 const vec
<dt_operand
*> &generic_fns
,
3000 const vec
<dt_operand
*> &preds
,
3001 const vec
<dt_node
*> &others
)
3004 char *kid_opname
= buf
;
3006 unsigned exprs_len
= gimple_exprs
.length ();
3007 unsigned gexprs_len
= generic_exprs
.length ();
3008 unsigned fns_len
= fns
.length ();
3009 unsigned gfns_len
= generic_fns
.length ();
3011 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3014 gimple_exprs
[0]->get_name (kid_opname
);
3016 fns
[0]->get_name (kid_opname
);
3018 generic_fns
[0]->get_name (kid_opname
);
3020 generic_exprs
[0]->get_name (kid_opname
);
3022 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3023 fprintf_indent (f
, indent
, " {\n");
3027 if (exprs_len
|| fns_len
)
3030 fprintf_indent (f
, indent
,
3031 "case SSA_NAME:\n");
3032 fprintf_indent (f
, indent
,
3033 " if (gimple *_d%d = get_def (valueize, %s))\n",
3035 fprintf_indent (f
, indent
,
3040 fprintf_indent (f
, indent
,
3041 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3043 fprintf_indent (f
, indent
,
3044 " switch (gimple_assign_rhs_code (_a%d))\n",
3047 fprintf_indent (f
, indent
, "{\n");
3048 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3050 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3051 id_base
*op
= e
->operation
;
3052 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3053 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3055 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3056 fprintf_indent (f
, indent
, " {\n");
3057 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3058 fprintf_indent (f
, indent
, " break;\n");
3059 fprintf_indent (f
, indent
, " }\n");
3061 fprintf_indent (f
, indent
, "default:;\n");
3062 fprintf_indent (f
, indent
, "}\n");
3068 fprintf_indent (f
, indent
,
3069 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3070 exprs_len
? "else " : "", depth
, depth
);
3071 fprintf_indent (f
, indent
,
3072 " switch (gimple_call_combined_fn (_c%d))\n",
3076 fprintf_indent (f
, indent
, "{\n");
3077 for (unsigned i
= 0; i
< fns_len
; ++i
)
3079 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3080 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3081 /* We need to be defensive against bogus prototypes allowing
3082 calls with not enough arguments. */
3083 fprintf_indent (f
, indent
,
3084 " if (gimple_call_num_args (_c%d) == %d)\n",
3085 depth
, e
->ops
.length ());
3086 fprintf_indent (f
, indent
, " {\n");
3087 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3088 fprintf_indent (f
, indent
, " }\n");
3089 fprintf_indent (f
, indent
, " break;\n");
3092 fprintf_indent (f
, indent
, "default:;\n");
3093 fprintf_indent (f
, indent
, "}\n");
3099 fprintf_indent (f
, indent
, " }\n");
3100 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3101 here rather than in the next loop. */
3102 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3104 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3105 id_base
*op
= e
->operation
;
3106 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3108 fprintf_indent (f
, indent
+ 4, "{\n");
3109 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3110 fprintf_indent (f
, indent
+ 4, "}\n");
3114 fprintf_indent (f
, indent
, " break;\n");
3117 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3119 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3120 id_base
*op
= e
->operation
;
3121 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3122 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3123 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3124 /* Already handled above. */
3127 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3128 fprintf_indent (f
, indent
, " {\n");
3129 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3130 fprintf_indent (f
, indent
, " break;\n");
3131 fprintf_indent (f
, indent
, " }\n");
3136 fprintf_indent (f
, indent
,
3137 "case CALL_EXPR:\n");
3138 fprintf_indent (f
, indent
,
3139 " switch (get_call_combined_fn (%s))\n",
3141 fprintf_indent (f
, indent
,
3145 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3147 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3148 gcc_assert (e
->operation
->kind
== id_base::FN
);
3150 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3151 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3152 " {\n", kid_opname
, e
->ops
.length ());
3153 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3154 fprintf_indent (f
, indent
, " }\n"
3157 fprintf_indent (f
, indent
, "default:;\n");
3160 fprintf_indent (f
, indent
, " }\n");
3161 fprintf_indent (f
, indent
, " break;\n");
3164 /* Close switch (TREE_CODE ()). */
3165 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3168 fprintf_indent (f
, indent
, " default:;\n");
3169 fprintf_indent (f
, indent
, " }\n");
3172 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3174 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3175 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3176 preds
[i
]->get_name (kid_opname
);
3177 fprintf_indent (f
, indent
, "{\n");
3179 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3180 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3181 gimple
? "gimple" : "tree",
3182 p
->id
, kid_opname
, kid_opname
,
3183 gimple
? ", valueize" : "");
3184 fprintf_indent (f
, indent
, " {\n");
3185 for (int j
= 0; j
< p
->nargs
; ++j
)
3187 char child_opname
[20];
3188 preds
[i
]->gen_opname (child_opname
, j
);
3189 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3190 child_opname
, kid_opname
, j
);
3192 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3195 fprintf_indent (f
, indent
, "}\n");
3198 for (unsigned i
= 0; i
< others
.length (); ++i
)
3199 others
[i
]->gen (f
, indent
, gimple
, depth
);
3202 /* Generate matching code for the decision tree operand. */
3205 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3210 unsigned n_braces
= 0;
3212 if (type
== DT_OPERAND
)
3215 case operand::OP_PREDICATE
:
3216 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3219 case operand::OP_EXPR
:
3221 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3223 n_braces
= gen_generic_expr (f
, indent
, opname
);
3229 else if (type
== DT_TRUE
)
3231 else if (type
== DT_MATCH
)
3232 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3236 indent
+= 4 * n_braces
;
3237 gen_kids (f
, indent
, gimple
, depth
);
3239 for (unsigned i
= 0; i
< n_braces
; ++i
)
3244 fprintf_indent (f
, indent
, " }\n");
3249 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3250 step of a '(simplify ...)' or '(match ...)'. This handles everything
3251 that is not part of the decision tree (simplify->match).
3252 Main recursive worker. */
3255 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3259 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3261 fprintf_indent (f
, indent
, "{\n");
3263 output_line_directive (f
, w
->location
);
3264 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3265 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3267 fprintf_indent (f
, indent
, "}\n");
3270 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3272 output_line_directive (f
, ife
->location
);
3273 fprintf_indent (f
, indent
, "if (");
3274 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3276 fprintf_indent (f
, indent
+ 2, "{\n");
3278 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3280 fprintf_indent (f
, indent
+ 2, "}\n");
3283 fprintf_indent (f
, indent
, "else\n");
3284 fprintf_indent (f
, indent
+ 2, "{\n");
3286 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3288 fprintf_indent (f
, indent
+ 2, "}\n");
3294 static unsigned fail_label_cnt
;
3295 char local_fail_label
[256];
3296 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3297 fail_label
= local_fail_label
;
3299 /* Analyze captures and perform early-outs on the incoming arguments
3300 that cover cases we cannot handle. */
3301 capture_info
cinfo (s
, result
, gimple
);
3302 if (s
->kind
== simplify::SIMPLIFY
)
3306 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3307 if (cinfo
.force_no_side_effects
& (1 << i
))
3309 fprintf_indent (f
, indent
,
3310 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3313 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3314 "forcing toplevel operand to have no "
3317 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3318 if (cinfo
.info
[i
].cse_p
)
3320 else if (cinfo
.info
[i
].force_no_side_effects_p
3321 && (cinfo
.info
[i
].toplevel_msk
3322 & cinfo
.force_no_side_effects
) == 0)
3324 fprintf_indent (f
, indent
,
3325 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3326 "goto %s;\n", i
, fail_label
);
3328 warning_at (cinfo
.info
[i
].c
->location
,
3329 "forcing captured operand to have no "
3332 else if ((cinfo
.info
[i
].toplevel_msk
3333 & cinfo
.force_no_side_effects
) != 0)
3334 /* Mark capture as having no side-effects if we had to verify
3335 that via forced toplevel operand checks. */
3336 cinfo
.info
[i
].force_no_side_effects_p
= true;
3340 /* Force single-use restriction by only allowing simple
3341 results via setting seq to NULL. */
3342 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3343 bool first_p
= true;
3344 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3345 if (cinfo
.info
[i
].force_single_use
)
3349 fprintf_indent (f
, indent
, "if (lseq\n");
3350 fprintf_indent (f
, indent
, " && (");
3356 fprintf_indent (f
, indent
, " || ");
3358 fprintf (f
, "!single_use (captures[%d])", i
);
3362 fprintf (f
, "))\n");
3363 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3368 if (s
->kind
== simplify::SIMPLIFY
)
3369 fprintf_indent (f
, indent
, "if (UNLIKELY (!dbg_cnt (match))) goto %s;\n", fail_label
);
3371 fprintf_indent (f
, indent
, "if (UNLIKELY (dump_file && (dump_flags & TDF_FOLDING))) "
3372 "fprintf (dump_file, \"%s ",
3373 s
->kind
== simplify::SIMPLIFY
3374 ? "Applying pattern" : "Matching expression");
3375 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3376 output_line_directive (f
,
3377 result
? result
->location
: s
->match
->location
, true,
3379 fprintf (f
, ", __FILE__, __LINE__);\n");
3381 fprintf_indent (f
, indent
, "{\n");
3385 /* If there is no result then this is a predicate implementation. */
3386 fprintf_indent (f
, indent
, "return true;\n");
3390 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3391 in outermost position). */
3392 if (result
->type
== operand::OP_EXPR
3393 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3394 result
= as_a
<expr
*> (result
)->ops
[0];
3395 if (result
->type
== operand::OP_EXPR
)
3397 expr
*e
= as_a
<expr
*> (result
);
3398 id_base
*opr
= e
->operation
;
3399 bool is_predicate
= false;
3400 /* When we delay operator substituting during lowering of fors we
3401 make sure that for code-gen purposes the effects of each substitute
3402 are the same. Thus just look at that. */
3403 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3404 opr
= uid
->substitutes
[0];
3405 else if (is_a
<predicate_id
*> (opr
))
3406 is_predicate
= true;
3408 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3409 *e
->operation
== CONVERT_EXPR
3410 ? "NOP_EXPR" : e
->operation
->id
,
3412 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3416 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3418 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3420 = get_operand_type (opr
, j
,
3421 "type", e
->expr_type
,
3423 : "TREE_TYPE (res_op->ops[0])");
3424 /* We need to expand GENERIC conditions we captured from
3425 COND_EXPRs and we need to unshare them when substituting
3427 int cond_handling
= 0;
3429 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3430 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3431 &cinfo
, indexes
, cond_handling
);
3434 /* Re-fold the toplevel result. It's basically an embedded
3435 gimple_build w/o actually building the stmt. */
3438 fprintf_indent (f
, indent
,
3439 "res_op->resimplify (lseq, valueize);\n");
3441 fprintf_indent (f
, indent
,
3442 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3443 "goto %s;\n", fail_label
);
3446 else if (result
->type
== operand::OP_CAPTURE
3447 || result
->type
== operand::OP_C_EXPR
)
3449 fprintf_indent (f
, indent
, "tree tem;\n");
3450 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3452 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3453 if (is_a
<capture
*> (result
)
3454 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3456 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3457 with substituting a capture of that. */
3458 fprintf_indent (f
, indent
,
3459 "if (COMPARISON_CLASS_P (tem))\n");
3460 fprintf_indent (f
, indent
,
3462 fprintf_indent (f
, indent
,
3463 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3464 fprintf_indent (f
, indent
,
3465 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3466 fprintf_indent (f
, indent
,
3472 fprintf_indent (f
, indent
, "return true;\n");
3476 bool is_predicate
= false;
3477 if (result
->type
== operand::OP_EXPR
)
3479 expr
*e
= as_a
<expr
*> (result
);
3480 id_base
*opr
= e
->operation
;
3481 /* When we delay operator substituting during lowering of fors we
3482 make sure that for code-gen purposes the effects of each substitute
3483 are the same. Thus just look at that. */
3484 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3485 opr
= uid
->substitutes
[0];
3486 else if (is_a
<predicate_id
*> (opr
))
3487 is_predicate
= true;
3488 /* Search for captures used multiple times in the result expression
3489 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3490 original expression. */
3492 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3494 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3495 || cinfo
.info
[i
].cse_p
)
3497 if (cinfo
.info
[i
].result_use_count
3498 > cinfo
.info
[i
].match_use_count
)
3499 fprintf_indent (f
, indent
,
3500 "if (! tree_invariant_p (captures[%d])) "
3501 "goto %s;\n", i
, fail_label
);
3503 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3507 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3510 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3511 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3514 = get_operand_type (opr
, j
,
3515 "type", e
->expr_type
,
3517 ? NULL
: "TREE_TYPE (res_op0)");
3518 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3522 fprintf_indent (f
, indent
, "return true;\n");
3525 fprintf_indent (f
, indent
, "tree _r;\n");
3526 /* Re-fold the toplevel result. Use non_lvalue to
3527 build NON_LVALUE_EXPRs so they get properly
3528 ignored when in GIMPLE form. */
3529 if (*opr
== NON_LVALUE_EXPR
)
3530 fprintf_indent (f
, indent
,
3531 "_r = non_lvalue_loc (loc, res_op0);\n");
3534 if (is_a
<operator_id
*> (opr
))
3535 fprintf_indent (f
, indent
,
3536 "_r = fold_build%d_loc (loc, %s, type",
3538 *e
->operation
== CONVERT_EXPR
3539 ? "NOP_EXPR" : e
->operation
->id
);
3541 fprintf_indent (f
, indent
,
3542 "_r = maybe_build_call_expr_loc (loc, "
3543 "%s, type, %d", e
->operation
->id
,
3545 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3546 fprintf (f
, ", res_op%d", j
);
3547 fprintf (f
, ");\n");
3548 if (!is_a
<operator_id
*> (opr
))
3550 fprintf_indent (f
, indent
, "if (!_r)\n");
3551 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3556 else if (result
->type
== operand::OP_CAPTURE
3557 || result
->type
== operand::OP_C_EXPR
)
3560 fprintf_indent (f
, indent
, "tree _r;\n");
3561 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3568 /* Search for captures not used in the result expression and dependent
3569 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3570 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3572 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3574 if (!cinfo
.info
[i
].force_no_side_effects_p
3575 && !cinfo
.info
[i
].expr_p
3576 && cinfo
.info
[i
].result_use_count
== 0)
3578 fprintf_indent (f
, indent
,
3579 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3581 fprintf_indent (f
, indent
+ 2,
3582 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3583 "fold_ignored_result (captures[%d]), _r);\n",
3587 fprintf_indent (f
, indent
, "return _r;\n");
3591 fprintf_indent (f
, indent
, "}\n");
3592 fprintf (f
, "%s:;\n", fail_label
);
3596 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3597 step of a '(simplify ...)' or '(match ...)'. This handles everything
3598 that is not part of the decision tree (simplify->match). */
3601 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3603 fprintf_indent (f
, indent
, "{\n");
3605 output_line_directive (f
,
3606 s
->result
? s
->result
->location
: s
->match
->location
);
3607 if (s
->capture_max
>= 0)
3610 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = {",
3611 s
->capture_max
+ 1);
3613 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3617 const char *opstr
= indexes
[i
]->get_name (opname
);
3618 expr
*e
= dyn_cast
<expr
*> (indexes
[i
]->op
);
3619 fputs (i
== 0 ? " " : ", ", f
);
3621 /* Transparently handle picking up CONSTRUCTOR and ADDR_EXPR
3622 leafs if they appear in a separate definition. */
3623 && (*e
->operation
== CONSTRUCTOR
3624 || *e
->operation
== ADDR_EXPR
))
3625 fprintf (f
, "(TREE_CODE (%s) == SSA_NAME "
3626 "? gimple_assign_rhs1 (SSA_NAME_DEF_STMT (%s)) : %s)",
3627 opstr
, opstr
, opstr
);
3629 fprintf (f
, "%s", opstr
);
3631 fprintf (f
, " };\n");
3634 /* If we have a split-out function for the actual transform, call it. */
3635 if (info
&& info
->fname
)
3639 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3640 "valueize, type, captures", info
->fname
);
3641 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3642 if (s
->for_subst_vec
[i
].first
->used
)
3643 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3644 fprintf (f
, "))\n");
3645 fprintf_indent (f
, indent
, " return true;\n");
3649 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3651 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3652 fprintf (f
, ", _p%d", i
);
3653 fprintf (f
, ", captures");
3654 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3656 if (s
->for_subst_vec
[i
].first
->used
)
3657 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3659 fprintf (f
, ");\n");
3660 fprintf_indent (f
, indent
, "if (res) return res;\n");
3665 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3667 if (! s
->for_subst_vec
[i
].first
->used
)
3669 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3670 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3671 s
->for_subst_vec
[i
].first
->id
,
3672 s
->for_subst_vec
[i
].second
->id
);
3673 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3674 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3675 s
->for_subst_vec
[i
].first
->id
,
3676 s
->for_subst_vec
[i
].second
->id
);
3680 gen_1 (f
, indent
, gimple
, s
->result
);
3684 fprintf_indent (f
, indent
, "}\n");
3688 /* Hash function for finding equivalent transforms. */
3691 sinfo_hashmap_traits::hash (const key_type
&v
)
3693 /* Only bother to compare those originating from the same source pattern. */
3694 return v
->s
->result
->location
;
3697 /* Compare function for finding equivalent transforms. */
3700 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3702 if (o1
->type
!= o2
->type
)
3707 case operand::OP_IF
:
3709 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3710 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3711 /* ??? Properly compare c-exprs. */
3712 if (if1
->cond
!= if2
->cond
)
3714 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3716 if (if1
->falseexpr
!= if2
->falseexpr
3718 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3722 case operand::OP_WITH
:
3724 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3725 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3726 if (with1
->with
!= with2
->with
)
3728 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3733 /* We've hit a result. Time to compare capture-infos - this is required
3734 in addition to the conservative pointer-equivalency of the result IL. */
3735 capture_info
cinfo1 (s1
, o1
, true);
3736 capture_info
cinfo2 (s2
, o2
, true);
3738 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3739 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3742 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3744 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3745 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3746 || (cinfo1
.info
[i
].force_no_side_effects_p
3747 != cinfo2
.info
[i
].force_no_side_effects_p
)
3748 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3749 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3750 /* toplevel_msk is an optimization */
3751 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3752 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3753 /* the pointer back to the capture is for diagnostics only */)
3757 /* ??? Deep-compare the actual result. */
3762 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3763 const key_type
&candidate
)
3765 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3769 /* Main entry to generate code for matching GIMPLE IL off the decision
3773 decision_tree::gen (FILE *f
, bool gimple
)
3779 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3780 "a total number of %u nodes\n",
3781 gimple
? "GIMPLE" : "GENERIC",
3782 root
->num_leafs
, root
->max_level
, root
->total_size
);
3784 /* First split out the transform part of equal leafs. */
3787 for (sinfo_map_t::iterator iter
= si
.begin ();
3788 iter
!= si
.end (); ++iter
)
3790 sinfo
*s
= (*iter
).second
;
3791 /* Do not split out single uses. */
3798 fprintf (stderr
, "found %u uses of", s
->cnt
);
3799 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3802 /* Generate a split out function with the leaf transform code. */
3803 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3806 fprintf (f
, "\nstatic bool\n"
3807 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3808 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3809 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3814 fprintf (f
, "\nstatic tree\n"
3815 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3816 (*iter
).second
->fname
);
3817 for (unsigned i
= 0;
3818 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3819 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3820 fprintf (f
, " tree *captures\n");
3822 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3824 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3826 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3827 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3828 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3829 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3830 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3831 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3834 fprintf (f
, ")\n{\n");
3835 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3837 fprintf (f
, " return false;\n");
3839 fprintf (f
, " return NULL_TREE;\n");
3842 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3844 for (unsigned n
= 1; n
<= 5; ++n
)
3846 bool has_kids_p
= false;
3848 /* First generate split-out functions. */
3849 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3851 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3852 expr
*e
= static_cast<expr
*>(dop
->op
);
3853 if (e
->ops
.length () != n
3854 /* Builtin simplifications are somewhat premature on
3855 GENERIC. The following drops patterns with outermost
3856 calls. It's easy to emit overloads for function code
3857 though if necessary. */
3859 && e
->operation
->kind
!= id_base::CODE
))
3863 fprintf (f
, "\nstatic bool\n"
3864 "gimple_simplify_%s (gimple_match_op *res_op,"
3865 " gimple_seq *seq,\n"
3866 " tree (*valueize)(tree) "
3867 "ATTRIBUTE_UNUSED,\n"
3868 " code_helper ARG_UNUSED (code), tree "
3869 "ARG_UNUSED (type)\n",
3872 fprintf (f
, "\nstatic tree\n"
3873 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3874 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3876 for (unsigned i
= 0; i
< n
; ++i
)
3877 fprintf (f
, ", tree _p%d", i
);
3880 dop
->gen_kids (f
, 2, gimple
, 0);
3882 fprintf (f
, " return false;\n");
3884 fprintf (f
, " return NULL_TREE;\n");
3889 /* If this main entry has no children, avoid generating code
3890 with compiler warnings, by generating a simple stub. */
3894 fprintf (f
, "\nstatic bool\n"
3895 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3896 " tree (*)(tree), code_helper,\n"
3899 fprintf (f
, "\ntree\n"
3900 "generic_simplify (location_t, enum tree_code,\n"
3902 for (unsigned i
= 0; i
< n
; ++i
)
3903 fprintf (f
, ", tree");
3907 fprintf (f
, " return false;\n");
3909 fprintf (f
, " return NULL_TREE;\n");
3914 /* Then generate the main entry with the outermost switch and
3915 tail-calls to the split-out functions. */
3917 fprintf (f
, "\nstatic bool\n"
3918 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3919 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3920 " code_helper code, const tree type");
3922 fprintf (f
, "\ntree\n"
3923 "generic_simplify (location_t loc, enum tree_code code, "
3924 "const tree type ATTRIBUTE_UNUSED");
3925 for (unsigned i
= 0; i
< n
; ++i
)
3926 fprintf (f
, ", tree _p%d", i
);
3931 fprintf (f
, " switch (code.get_rep())\n"
3934 fprintf (f
, " switch (code)\n"
3936 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3938 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3939 expr
*e
= static_cast<expr
*>(dop
->op
);
3940 if (e
->ops
.length () != n
3941 /* Builtin simplifications are somewhat premature on
3942 GENERIC. The following drops patterns with outermost
3943 calls. It's easy to emit overloads for function code
3944 though if necessary. */
3946 && e
->operation
->kind
!= id_base::CODE
))
3949 if (*e
->operation
== CONVERT_EXPR
3950 || *e
->operation
== NOP_EXPR
)
3951 fprintf (f
, " CASE_CONVERT:\n");
3953 fprintf (f
, " case %s%s:\n",
3954 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3957 fprintf (f
, " return gimple_simplify_%s (res_op, "
3958 "seq, valueize, code, type", e
->operation
->id
);
3960 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3962 for (unsigned j
= 0; j
< n
; ++j
)
3963 fprintf (f
, ", _p%d", j
);
3964 fprintf (f
, ");\n");
3966 fprintf (f
, " default:;\n"
3970 fprintf (f
, " return false;\n");
3972 fprintf (f
, " return NULL_TREE;\n");
3977 /* Output code to implement the predicate P from the decision tree DT. */
3980 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3982 fprintf (f
, "\nbool\n"
3983 "%s%s (tree t%s%s)\n"
3984 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3985 p
->nargs
> 0 ? ", tree *res_ops" : "",
3986 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3987 /* Conveniently make 'type' available. */
3988 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3991 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3992 dt
.root
->gen_kids (f
, 2, gimple
, 0);
3994 fprintf_indent (f
, 2, "return false;\n"
3998 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
4001 write_header (FILE *f
, const char *head
)
4003 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
4004 fprintf (f
, " a IL pattern matching and simplification description. */\n");
4006 /* Include the header instead of writing it awkwardly quoted here. */
4007 fprintf (f
, "\n#include \"%s\"\n", head
);
4017 parser (cpp_reader
*, bool gimple
);
4020 const cpp_token
*next ();
4021 const cpp_token
*peek (unsigned = 1);
4022 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
4023 const cpp_token
*expect (enum cpp_ttype
);
4024 const cpp_token
*eat_token (enum cpp_ttype
);
4025 const char *get_string ();
4026 const char *get_ident ();
4027 const cpp_token
*eat_ident (const char *);
4028 const char *get_number ();
4030 unsigned get_internal_capture_id ();
4032 id_base
*parse_operation (unsigned char &);
4033 operand
*parse_capture (operand
*, bool);
4034 operand
*parse_expr ();
4035 c_expr
*parse_c_expr (cpp_ttype
);
4036 operand
*parse_op ();
4038 void record_operlist (location_t
, user_id
*);
4040 void parse_pattern ();
4041 operand
*parse_result (operand
*, predicate_id
*);
4042 void push_simplify (simplify::simplify_kind
,
4043 vec
<simplify
*>&, operand
*, operand
*);
4044 void parse_simplify (simplify::simplify_kind
,
4045 vec
<simplify
*>&, predicate_id
*, operand
*);
4046 void parse_for (location_t
);
4047 void parse_if (location_t
);
4048 void parse_predicates (location_t
);
4049 void parse_operator_list (location_t
);
4051 void finish_match_operand (operand
*);
4055 vec
<c_expr
*> active_ifs
;
4056 vec
<vec
<user_id
*> > active_fors
;
4057 hash_set
<user_id
*> *oper_lists_set
;
4058 vec
<user_id
*> oper_lists
;
4060 cid_map_t
*capture_ids
;
4064 vec
<simplify
*> simplifiers
;
4065 vec
<predicate_id
*> user_predicates
;
4066 bool parsing_match_operand
;
4069 /* Lexing helpers. */
4071 /* Read the next non-whitespace token from R. */
4076 const cpp_token
*token
;
4079 token
= cpp_get_token (r
);
4081 while (token
->type
== CPP_PADDING
);
4085 /* Peek at the next non-whitespace token from R. */
4088 parser::peek (unsigned num
)
4090 const cpp_token
*token
;
4094 token
= cpp_peek_token (r
, i
++);
4096 while (token
->type
== CPP_PADDING
4098 /* If we peek at EOF this is a fatal error as it leaves the
4099 cpp_reader in unusable state. Assume we really wanted a
4100 token and thus this EOF is unexpected. */
4101 if (token
->type
== CPP_EOF
)
4102 fatal_at (token
, "unexpected end of file");
4106 /* Peek at the next identifier token (or return NULL if the next
4107 token is not an identifier or equal to ID if supplied). */
4110 parser::peek_ident (const char *id
, unsigned num
)
4112 const cpp_token
*token
= peek (num
);
4113 if (token
->type
!= CPP_NAME
)
4119 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4120 if (strcmp (id
, t
) == 0)
4126 /* Read the next token from R and assert it is of type TK. */
4129 parser::expect (enum cpp_ttype tk
)
4131 const cpp_token
*token
= next ();
4132 if (token
->type
!= tk
)
4133 fatal_at (token
, "expected %s, got %s",
4134 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4139 /* Consume the next token from R and assert it is of type TK. */
4142 parser::eat_token (enum cpp_ttype tk
)
4147 /* Read the next token from R and assert it is of type CPP_STRING and
4148 return its value. */
4151 parser::get_string ()
4153 const cpp_token
*token
= expect (CPP_STRING
);
4154 return (const char *)token
->val
.str
.text
;
4157 /* Read the next token from R and assert it is of type CPP_NAME and
4158 return its value. */
4161 parser::get_ident ()
4163 const cpp_token
*token
= expect (CPP_NAME
);
4164 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4167 /* Eat an identifier token with value S from R. */
4170 parser::eat_ident (const char *s
)
4172 const cpp_token
*token
= peek ();
4173 const char *t
= get_ident ();
4174 if (strcmp (s
, t
) != 0)
4175 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4179 /* Read the next token from R and assert it is of type CPP_NUMBER and
4180 return its value. */
4183 parser::get_number ()
4185 const cpp_token
*token
= expect (CPP_NUMBER
);
4186 return (const char *)token
->val
.str
.text
;
4189 /* Return a capture ID that can be used internally. */
4192 parser::get_internal_capture_id ()
4194 unsigned newid
= capture_ids
->elements ();
4195 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4198 snprintf (id
, sizeof (id
), "__%u", newid
);
4199 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4201 fatal ("reserved capture id '%s' already used", id
);
4205 /* Record an operator-list use for transparent for handling. */
4208 parser::record_operlist (location_t loc
, user_id
*p
)
4210 if (!oper_lists_set
->add (p
))
4212 if (!oper_lists
.is_empty ()
4213 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4214 fatal_at (loc
, "User-defined operator list does not have the "
4215 "same number of entries as others used in the pattern");
4216 oper_lists
.safe_push (p
);
4220 /* Parse the operator ID, special-casing convert?, convert1? and
4224 parser::parse_operation (unsigned char &opt_grp
)
4226 const cpp_token
*id_tok
= peek ();
4227 char *alt_id
= NULL
;
4228 const char *id
= get_ident ();
4229 const cpp_token
*token
= peek ();
4231 if (token
->type
== CPP_QUERY
4232 && !(token
->flags
& PREV_WHITE
))
4234 if (!parsing_match_operand
)
4235 fatal_at (id_tok
, "conditional convert can only be used in "
4236 "match expression");
4237 if (ISDIGIT (id
[strlen (id
) - 1]))
4239 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4240 alt_id
= xstrdup (id
);
4241 alt_id
[strlen (id
) - 1] = '\0';
4243 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4247 eat_token (CPP_QUERY
);
4249 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4251 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4254 user_id
*p
= dyn_cast
<user_id
*> (op
);
4255 if (p
&& p
->is_oper_list
)
4257 if (active_fors
.length() == 0)
4258 record_operlist (id_tok
->src_loc
, p
);
4260 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4266 capture = '@'<number> */
4269 parser::parse_capture (operand
*op
, bool require_existing
)
4271 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4272 const cpp_token
*token
= peek ();
4273 const char *id
= NULL
;
4274 bool value_match
= false;
4275 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4276 if (token
->type
== CPP_ATSIGN
4277 && ! (token
->flags
& PREV_WHITE
)
4278 && parsing_match_operand
)
4280 eat_token (CPP_ATSIGN
);
4284 if (token
->type
== CPP_NUMBER
)
4286 else if (token
->type
== CPP_NAME
)
4289 fatal_at (token
, "expected number or identifier");
4290 unsigned next_id
= capture_ids
->elements ();
4292 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4295 if (require_existing
)
4296 fatal_at (src_loc
, "unknown capture id");
4299 return new capture (src_loc
, num
, op
, value_match
);
4302 /* Parse an expression
4303 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4306 parser::parse_expr ()
4308 const cpp_token
*token
= peek ();
4309 unsigned char opt_grp
;
4310 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4313 bool is_commutative
= false;
4314 bool force_capture
= false;
4315 const char *expr_type
= NULL
;
4317 if (!parsing_match_operand
4318 && token
->type
== CPP_NOT
4319 && !(token
->flags
& PREV_WHITE
))
4321 eat_token (CPP_NOT
);
4322 e
->force_leaf
= true;
4325 if (token
->type
== CPP_COLON
4326 && !(token
->flags
& PREV_WHITE
))
4328 eat_token (CPP_COLON
);
4330 if (token
->type
== CPP_NAME
4331 && !(token
->flags
& PREV_WHITE
))
4333 const char *s
= get_ident ();
4334 if (!parsing_match_operand
)
4344 = dyn_cast
<operator_id
*> (e
->operation
))
4346 if (!commutative_tree_code (o
->code
)
4347 && !comparison_code_p (o
->code
))
4348 fatal_at (token
, "operation is not commutative");
4350 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4351 for (unsigned i
= 0;
4352 i
< p
->substitutes
.length (); ++i
)
4355 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4357 if (!commutative_tree_code (q
->code
)
4358 && !comparison_code_p (q
->code
))
4359 fatal_at (token
, "operation %s is not "
4360 "commutative", q
->id
);
4363 is_commutative
= true;
4365 else if (*sp
== 'C')
4366 is_commutative
= true;
4367 else if (*sp
== 's')
4369 e
->force_single_use
= true;
4370 force_capture
= true;
4373 fatal_at (token
, "flag %c not recognized", *sp
);
4380 fatal_at (token
, "expected flag or type specifying identifier");
4383 if (token
->type
== CPP_ATSIGN
4384 && !(token
->flags
& PREV_WHITE
))
4385 op
= parse_capture (e
, false);
4386 else if (force_capture
)
4388 unsigned num
= get_internal_capture_id ();
4389 op
= new capture (token
->src_loc
, num
, e
, false);
4396 if (token
->type
== CPP_CLOSE_PAREN
)
4398 if (e
->operation
->nargs
!= -1
4399 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4400 fatal_at (token
, "'%s' expects %u operands, not %u",
4401 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4404 if (e
->ops
.length () == 2
4405 || commutative_op (e
->operation
) >= 0)
4406 e
->is_commutative
= true;
4408 fatal_at (token
, "only binary operators or functions with "
4409 "two arguments can be marked commutative, "
4410 "unless the operation is known to be inherently "
4413 e
->expr_type
= expr_type
;
4416 if (e
->ops
.length () != 1)
4417 fatal_at (token
, "only unary operations can be conditional");
4418 e
->opt_grp
= opt_grp
;
4422 else if (!(token
->flags
& PREV_WHITE
))
4423 fatal_at (token
, "expected expression operand");
4425 e
->append_op (parse_op ());
4430 /* Lex native C code delimited by START recording the preprocessing tokens
4431 for later processing.
4432 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4435 parser::parse_c_expr (cpp_ttype start
)
4437 const cpp_token
*token
;
4440 vec
<cpp_token
> code
= vNULL
;
4441 unsigned nr_stmts
= 0;
4442 location_t loc
= eat_token (start
)->src_loc
;
4443 if (start
== CPP_OPEN_PAREN
)
4444 end
= CPP_CLOSE_PAREN
;
4445 else if (start
== CPP_OPEN_BRACE
)
4446 end
= CPP_CLOSE_BRACE
;
4454 /* Count brace pairs to find the end of the expr to match. */
4455 if (token
->type
== start
)
4457 else if (token
->type
== end
4460 else if (token
->type
== CPP_EOF
)
4461 fatal_at (token
, "unexpected end of file");
4463 /* This is a lame way of counting the number of statements. */
4464 if (token
->type
== CPP_SEMICOLON
)
4467 /* If this is possibly a user-defined identifier mark it used. */
4468 if (token
->type
== CPP_NAME
)
4471 = (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4472 if (strcmp (str
, "return") == 0)
4473 fatal_at (token
, "return statement not allowed in C expression");
4474 id_base
*idb
= get_operator (str
);
4476 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4477 record_operlist (token
->src_loc
, p
);
4480 /* Record the token. */
4481 code
.safe_push (*token
);
4484 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4487 /* Parse an operand which is either an expression, a predicate or
4488 a standalone capture.
4489 op = predicate | expr | c_expr | capture */
4494 const cpp_token
*token
= peek ();
4495 class operand
*op
= NULL
;
4496 if (token
->type
== CPP_OPEN_PAREN
)
4498 eat_token (CPP_OPEN_PAREN
);
4500 eat_token (CPP_CLOSE_PAREN
);
4502 else if (token
->type
== CPP_OPEN_BRACE
)
4504 op
= parse_c_expr (CPP_OPEN_BRACE
);
4508 /* Remaining ops are either empty or predicates */
4509 if (token
->type
== CPP_NAME
)
4511 const char *id
= get_ident ();
4512 id_base
*opr
= get_operator (id
);
4514 fatal_at (token
, "expected predicate name");
4515 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4517 if (code1
->nargs
!= 0)
4518 fatal_at (token
, "using an operator with operands as predicate");
4519 /* Parse the zero-operand operator "predicates" as
4521 op
= new expr (opr
, token
->src_loc
);
4523 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4525 if (code2
->nargs
!= 0)
4526 fatal_at (token
, "using an operator with operands as predicate");
4527 /* Parse the zero-operand operator "predicates" as
4529 op
= new expr (opr
, token
->src_loc
);
4531 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4532 op
= new predicate (p
, token
->src_loc
);
4534 fatal_at (token
, "using an unsupported operator as predicate");
4535 if (!parsing_match_operand
)
4536 fatal_at (token
, "predicates are only allowed in match expression");
4538 if (token
->flags
& PREV_WHITE
)
4541 else if (token
->type
!= CPP_COLON
4542 && token
->type
!= CPP_ATSIGN
)
4543 fatal_at (token
, "expected expression or predicate");
4544 /* optionally followed by a capture and a predicate. */
4545 if (token
->type
== CPP_COLON
)
4546 fatal_at (token
, "not implemented: predicate on leaf operand");
4547 if (token
->type
== CPP_ATSIGN
)
4548 op
= parse_capture (op
, !parsing_match_operand
);
4554 /* Create a new simplify from the current parsing state and MATCH,
4555 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4558 parser::push_simplify (simplify::simplify_kind kind
,
4559 vec
<simplify
*>& simplifiers
,
4560 operand
*match
, operand
*result
)
4562 /* Build and push a temporary for operator list uses in expressions. */
4563 if (!oper_lists
.is_empty ())
4564 active_fors
.safe_push (oper_lists
);
4566 simplifiers
.safe_push
4567 (new simplify (kind
, last_id
++, match
, result
,
4568 active_fors
.copy (), capture_ids
));
4570 if (!oper_lists
.is_empty ())
4575 <result-op> = <op> | <if> | <with>
4576 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4577 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4581 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4583 const cpp_token
*token
= peek ();
4584 if (token
->type
!= CPP_OPEN_PAREN
)
4587 eat_token (CPP_OPEN_PAREN
);
4588 if (peek_ident ("if"))
4591 if_expr
*ife
= new if_expr (token
->src_loc
);
4592 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4593 if (peek ()->type
== CPP_OPEN_PAREN
)
4595 ife
->trueexpr
= parse_result (result
, matcher
);
4596 if (peek ()->type
== CPP_OPEN_PAREN
)
4597 ife
->falseexpr
= parse_result (result
, matcher
);
4598 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4599 ife
->falseexpr
= parse_op ();
4601 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4603 ife
->trueexpr
= parse_op ();
4604 if (peek ()->type
== CPP_OPEN_PAREN
)
4605 ife
->falseexpr
= parse_result (result
, matcher
);
4606 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4607 ife
->falseexpr
= parse_op ();
4609 /* If this if is immediately closed then it contains a
4610 manual matcher or is part of a predicate definition. */
4611 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4614 fatal_at (peek (), "manual transform not implemented");
4615 ife
->trueexpr
= result
;
4617 eat_token (CPP_CLOSE_PAREN
);
4620 else if (peek_ident ("with"))
4623 with_expr
*withe
= new with_expr (token
->src_loc
);
4624 /* Parse (with c-expr expr) as (if-with (true) expr). */
4625 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4626 withe
->with
->nr_stmts
= 0;
4627 withe
->subexpr
= parse_result (result
, matcher
);
4628 eat_token (CPP_CLOSE_PAREN
);
4631 else if (peek_ident ("switch"))
4633 token
= eat_ident ("switch");
4634 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4636 if_expr
*ife
= new if_expr (ifloc
);
4638 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4639 if (peek ()->type
== CPP_OPEN_PAREN
)
4640 ife
->trueexpr
= parse_result (result
, matcher
);
4642 ife
->trueexpr
= parse_op ();
4643 eat_token (CPP_CLOSE_PAREN
);
4644 if (peek ()->type
!= CPP_OPEN_PAREN
4645 || !peek_ident ("if", 2))
4646 fatal_at (token
, "switch can be implemented with a single if");
4647 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4649 if (peek ()->type
== CPP_OPEN_PAREN
)
4651 if (peek_ident ("if", 2))
4653 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4655 ife
->falseexpr
= new if_expr (ifloc
);
4656 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4657 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4658 if (peek ()->type
== CPP_OPEN_PAREN
)
4659 ife
->trueexpr
= parse_result (result
, matcher
);
4661 ife
->trueexpr
= parse_op ();
4662 eat_token (CPP_CLOSE_PAREN
);
4666 /* switch default clause */
4667 ife
->falseexpr
= parse_result (result
, matcher
);
4668 eat_token (CPP_CLOSE_PAREN
);
4674 /* switch default clause */
4675 ife
->falseexpr
= parse_op ();
4676 eat_token (CPP_CLOSE_PAREN
);
4680 eat_token (CPP_CLOSE_PAREN
);
4685 operand
*op
= result
;
4688 eat_token (CPP_CLOSE_PAREN
);
4694 simplify = 'simplify' <expr> <result-op>
4696 match = 'match' <ident> <expr> [<result-op>]
4697 and fill SIMPLIFIERS with the results. */
4700 parser::parse_simplify (simplify::simplify_kind kind
,
4701 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4704 /* Reset the capture map. */
4706 capture_ids
= new cid_map_t
;
4707 /* Reset oper_lists and set. */
4708 hash_set
<user_id
*> olist
;
4709 oper_lists_set
= &olist
;
4712 const cpp_token
*loc
= peek ();
4713 parsing_match_operand
= true;
4714 class operand
*match
= parse_op ();
4715 finish_match_operand (match
);
4716 parsing_match_operand
= false;
4717 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4718 fatal_at (loc
, "outermost expression cannot be captured");
4719 if (match
->type
== operand::OP_EXPR
4720 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4721 fatal_at (loc
, "outermost expression cannot be a predicate");
4723 /* Splice active_ifs onto result and continue parsing the
4725 if_expr
*active_if
= NULL
;
4726 for (int i
= active_ifs
.length (); i
> 0; --i
)
4728 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4729 ifc
->cond
= active_ifs
[i
-1];
4730 ifc
->trueexpr
= active_if
;
4733 if_expr
*outermost_if
= active_if
;
4734 while (active_if
&& active_if
->trueexpr
)
4735 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4737 const cpp_token
*token
= peek ();
4739 /* If this if is immediately closed then it is part of a predicate
4740 definition. Push it. */
4741 if (token
->type
== CPP_CLOSE_PAREN
)
4744 fatal_at (token
, "expected transform expression");
4747 active_if
->trueexpr
= result
;
4748 result
= outermost_if
;
4750 push_simplify (kind
, simplifiers
, match
, result
);
4754 operand
*tem
= parse_result (result
, matcher
);
4757 active_if
->trueexpr
= tem
;
4758 result
= outermost_if
;
4763 push_simplify (kind
, simplifiers
, match
, result
);
4766 /* Parsing of the outer control structures. */
4768 /* Parse a for expression
4769 for = '(' 'for' <subst>... <pattern> ')'
4770 subst = <ident> '(' <ident>... ')' */
4773 parser::parse_for (location_t
)
4775 auto_vec
<const cpp_token
*> user_id_tokens
;
4776 vec
<user_id
*> user_ids
= vNULL
;
4777 const cpp_token
*token
;
4778 unsigned min_n_opers
= 0, max_n_opers
= 0;
4783 if (token
->type
!= CPP_NAME
)
4786 /* Insert the user defined operators into the operator hash. */
4787 const char *id
= get_ident ();
4788 if (get_operator (id
, true) != NULL
)
4789 fatal_at (token
, "operator already defined");
4790 user_id
*op
= new user_id (id
);
4791 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4793 user_ids
.safe_push (op
);
4794 user_id_tokens
.safe_push (token
);
4796 eat_token (CPP_OPEN_PAREN
);
4799 while ((token
= peek_ident ()) != 0)
4801 const char *oper
= get_ident ();
4802 id_base
*idb
= get_operator (oper
, true);
4804 fatal_at (token
, "no such operator '%s'", oper
);
4808 else if (idb
->nargs
== -1)
4810 else if (idb
->nargs
!= arity
)
4811 fatal_at (token
, "operator '%s' with arity %d does not match "
4812 "others with arity %d", oper
, idb
->nargs
, arity
);
4814 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4817 if (p
->is_oper_list
)
4818 op
->substitutes
.safe_splice (p
->substitutes
);
4820 fatal_at (token
, "iterator cannot be used as operator-list");
4823 op
->substitutes
.safe_push (idb
);
4826 token
= expect (CPP_CLOSE_PAREN
);
4828 unsigned nsubstitutes
= op
->substitutes
.length ();
4829 if (nsubstitutes
== 0)
4830 fatal_at (token
, "A user-defined operator must have at least "
4831 "one substitution");
4832 if (max_n_opers
== 0)
4834 min_n_opers
= nsubstitutes
;
4835 max_n_opers
= nsubstitutes
;
4839 if (nsubstitutes
% min_n_opers
!= 0
4840 && min_n_opers
% nsubstitutes
!= 0)
4841 fatal_at (token
, "All user-defined identifiers must have a "
4842 "multiple number of operator substitutions of the "
4843 "smallest number of substitutions");
4844 if (nsubstitutes
< min_n_opers
)
4845 min_n_opers
= nsubstitutes
;
4846 else if (nsubstitutes
> max_n_opers
)
4847 max_n_opers
= nsubstitutes
;
4851 unsigned n_ids
= user_ids
.length ();
4853 fatal_at (token
, "for requires at least one user-defined identifier");
4856 if (token
->type
== CPP_CLOSE_PAREN
)
4857 fatal_at (token
, "no pattern defined in for");
4859 active_fors
.safe_push (user_ids
);
4863 if (token
->type
== CPP_CLOSE_PAREN
)
4869 /* Remove user-defined operators from the hash again. */
4870 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4872 if (!user_ids
[i
]->used
)
4873 warning_at (user_id_tokens
[i
],
4874 "operator %s defined but not used", user_ids
[i
]->id
);
4875 operators
->remove_elt (user_ids
[i
]);
4879 /* Parse an identifier associated with a list of operators.
4880 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4883 parser::parse_operator_list (location_t
)
4885 const cpp_token
*token
= peek ();
4886 const char *id
= get_ident ();
4888 if (get_operator (id
, true) != 0)
4889 fatal_at (token
, "operator %s already defined", id
);
4891 user_id
*op
= new user_id (id
, true);
4894 while ((token
= peek_ident ()) != 0)
4897 const char *oper
= get_ident ();
4898 id_base
*idb
= get_operator (oper
, true);
4901 fatal_at (token
, "no such operator '%s'", oper
);
4905 else if (idb
->nargs
== -1)
4907 else if (arity
!= idb
->nargs
)
4908 fatal_at (token
, "operator '%s' with arity %d does not match "
4909 "others with arity %d", oper
, idb
->nargs
, arity
);
4911 /* We allow composition of multiple operator lists. */
4912 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4913 op
->substitutes
.safe_splice (p
->substitutes
);
4915 op
->substitutes
.safe_push (idb
);
4918 // Check that there is no junk after id-list
4920 if (token
->type
!= CPP_CLOSE_PAREN
)
4921 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4923 if (op
->substitutes
.length () == 0)
4924 fatal_at (token
, "operator-list cannot be empty");
4927 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4931 /* Parse an outer if expression.
4932 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4935 parser::parse_if (location_t
)
4937 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4939 const cpp_token
*token
= peek ();
4940 if (token
->type
== CPP_CLOSE_PAREN
)
4941 fatal_at (token
, "no pattern defined in if");
4943 active_ifs
.safe_push (ifexpr
);
4947 if (token
->type
== CPP_CLOSE_PAREN
)
4955 /* Parse a list of predefined predicate identifiers.
4956 preds = '(' 'define_predicates' <ident>... ')' */
4959 parser::parse_predicates (location_t
)
4963 const cpp_token
*token
= peek ();
4964 if (token
->type
!= CPP_NAME
)
4967 add_predicate (get_ident ());
4972 /* Parse outer control structures.
4973 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4976 parser::parse_pattern ()
4978 /* All clauses start with '('. */
4979 eat_token (CPP_OPEN_PAREN
);
4980 const cpp_token
*token
= peek ();
4981 const char *id
= get_ident ();
4982 if (strcmp (id
, "simplify") == 0)
4984 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4987 else if (strcmp (id
, "match") == 0)
4989 bool with_args
= false;
4990 location_t e_loc
= peek ()->src_loc
;
4991 if (peek ()->type
== CPP_OPEN_PAREN
)
4993 eat_token (CPP_OPEN_PAREN
);
4996 const char *name
= get_ident ();
4997 id_base
*id1
= get_operator (name
);
5001 p
= add_predicate (name
);
5002 user_predicates
.safe_push (p
);
5004 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
5007 fatal_at (token
, "cannot add a match to a non-predicate ID");
5008 /* Parse (match <id> <arg>... (match-expr)) here. */
5012 capture_ids
= new cid_map_t
;
5013 e
= new expr (p
, e_loc
);
5014 while (peek ()->type
== CPP_ATSIGN
)
5015 e
->append_op (parse_capture (NULL
, false));
5016 eat_token (CPP_CLOSE_PAREN
);
5019 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
5020 || (!e
&& p
->nargs
!= 0)))
5021 fatal_at (token
, "non-matching number of match operands");
5022 p
->nargs
= e
? e
->ops
.length () : 0;
5023 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5026 else if (strcmp (id
, "for") == 0)
5027 parse_for (token
->src_loc
);
5028 else if (strcmp (id
, "if") == 0)
5029 parse_if (token
->src_loc
);
5030 else if (strcmp (id
, "define_predicates") == 0)
5032 if (active_ifs
.length () > 0
5033 || active_fors
.length () > 0)
5034 fatal_at (token
, "define_predicates inside if or for is not supported");
5035 parse_predicates (token
->src_loc
);
5037 else if (strcmp (id
, "define_operator_list") == 0)
5039 if (active_ifs
.length () > 0
5040 || active_fors
.length () > 0)
5041 fatal_at (token
, "operator-list inside if or for is not supported");
5042 parse_operator_list (token
->src_loc
);
5045 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5046 active_ifs
.length () == 0 && active_fors
.length () == 0
5047 ? "'define_predicates', " : "");
5049 eat_token (CPP_CLOSE_PAREN
);
5052 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5056 walk_captures (operand
*op
, vec
<vec
<capture
*> > &cpts
)
5061 if (capture
*c
= dyn_cast
<capture
*> (op
))
5063 cpts
[c
->where
].safe_push (c
);
5064 walk_captures (c
->what
, cpts
);
5066 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5067 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5068 walk_captures (e
->ops
[i
], cpts
);
5071 /* Finish up OP which is a match operand. */
5074 parser::finish_match_operand (operand
*op
)
5076 /* Look for matching captures, diagnose mis-uses of @@ and apply
5077 early lowering and distribution of value_match. */
5078 auto_vec
<vec
<capture
*> > cpts
;
5079 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5080 walk_captures (op
, cpts
);
5081 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5083 capture
*value_match
= NULL
;
5084 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5086 if (cpts
[i
][j
]->value_match
)
5089 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5090 value_match
= cpts
[i
][j
];
5093 if (cpts
[i
].length () == 1 && value_match
)
5094 fatal_at (value_match
->location
, "@@ without a matching capture");
5097 /* Duplicate prevailing capture with the existing ID, create
5098 a fake ID and rewrite all captures to use it. This turns
5099 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5100 value_match
->what
= new capture (value_match
->location
,
5102 value_match
->what
, false);
5103 /* Create a fake ID and rewrite all captures to use it. */
5104 unsigned newid
= get_internal_capture_id ();
5105 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5107 cpts
[i
][j
]->where
= newid
;
5108 cpts
[i
][j
]->value_match
= true;
5115 /* Main entry of the parser. Repeatedly parse outer control structures. */
5117 parser::parser (cpp_reader
*r_
, bool gimple_
)
5122 active_fors
= vNULL
;
5123 simplifiers
= vNULL
;
5124 oper_lists_set
= NULL
;
5127 user_predicates
= vNULL
;
5128 parsing_match_operand
= false;
5131 const cpp_token
*token
= next ();
5132 while (token
->type
!= CPP_EOF
)
5134 _cpp_backup_tokens (r
, 1);
5141 /* Helper for the linemap code. */
5144 round_alloc_size (size_t s
)
5150 /* The genmatch generator program. It reads from a pattern description
5151 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5154 main (int argc
, char **argv
)
5158 progname
= "genmatch";
5164 char *input
= argv
[argc
-1];
5165 for (int i
= 1; i
< argc
- 1; ++i
)
5167 if (strcmp (argv
[i
], "--gimple") == 0)
5169 else if (strcmp (argv
[i
], "--generic") == 0)
5171 else if (strcmp (argv
[i
], "-v") == 0)
5173 else if (strcmp (argv
[i
], "-vv") == 0)
5177 fprintf (stderr
, "Usage: genmatch "
5178 "[--gimple] [--generic] [-v[v]] input\n");
5183 line_table
= XCNEW (class line_maps
);
5184 linemap_init (line_table
, 0);
5185 line_table
->reallocator
= xrealloc
;
5186 line_table
->round_alloc_size
= round_alloc_size
;
5188 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5189 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5190 cb
->diagnostic
= diagnostic_cb
;
5192 /* Add the build directory to the #include "" search path. */
5193 cpp_dir
*dir
= XCNEW (cpp_dir
);
5194 dir
->name
= getpwd ();
5196 dir
->name
= ASTRDUP (".");
5197 cpp_set_include_chains (r
, dir
, NULL
, false);
5199 if (!cpp_read_main_file (r
, input
))
5201 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5202 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5204 null_id
= new id_base (id_base::NULL_ID
, "null");
5206 /* Pre-seed operators. */
5207 operators
= new hash_table
<id_base
> (1024);
5208 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5209 add_operator (SYM, # SYM, # TYPE, NARGS);
5210 #define END_OF_BASE_TREE_CODES
5212 #undef END_OF_BASE_TREE_CODES
5215 /* Pre-seed builtin functions.
5216 ??? Cannot use N (name) as that is targetm.emultls.get_address
5217 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5218 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5219 add_function (ENUM, "CFN_" # ENUM);
5220 #include "builtins.def"
5222 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5223 add_function (IFN_##CODE, "CFN_" #CODE);
5224 #include "internal-fn.def"
5227 parser
p (r
, gimple
);
5230 write_header (stdout
, "gimple-match-head.cc");
5232 write_header (stdout
, "generic-match-head.cc");
5234 /* Go over all predicates defined with patterns and perform
5235 lowering and code generation. */
5236 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5238 predicate_id
*pred
= p
.user_predicates
[i
];
5239 lower (pred
->matchers
, gimple
);
5242 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5243 print_matches (pred
->matchers
[j
]);
5246 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5247 dt
.insert (pred
->matchers
[j
], j
);
5252 write_predicate (stdout
, pred
, dt
, gimple
);
5255 /* Lower the main simplifiers and generate code for them. */
5256 lower (p
.simplifiers
, gimple
);
5259 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5260 print_matches (p
.simplifiers
[i
]);
5263 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5264 dt
.insert (p
.simplifiers
[i
], i
);
5269 dt
.gen (stdout
, gimple
);
5272 cpp_finish (r
, NULL
);