1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2020 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
&& strncmp (id
, "IFN_", 4) == 0)
609 /* Try CFN_ instead of IFN_. */
610 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
611 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
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), opt_grp (0) {}
702 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
703 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
704 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
705 opt_grp (e
->opt_grp
) {}
706 void append_op (operand
*op
) { ops
.safe_push (op
); }
707 /* The operator and its operands. */
710 /* An explicitely specified type - used exclusively for conversions. */
711 const char *expr_type
;
712 /* Whether the operation is to be applied commutatively. This is
713 later lowered to two separate patterns. */
715 /* Whether the expression is expected to be in GENERIC form. */
717 /* Whether pushing any stmt to the sequence should be conditional
718 on this expression having a single-use. */
719 bool force_single_use
;
720 /* If non-zero, the group for optional handling. */
721 unsigned char opt_grp
;
722 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
723 const char *, capture_info
*,
724 dt_operand
** = 0, int = 0);
727 /* An operator that is represented by native C code. This is always
728 a leaf operand in the AST. This class is also used to represent
729 the code to be generated for 'if' and 'with' expressions. */
731 class c_expr
: public operand
734 /* A mapping of an identifier and its replacement. Used to apply
740 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
743 c_expr (cpp_reader
*r_
, location_t loc
,
744 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
745 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
746 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
747 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
748 /* cpplib tokens and state to transform this back to source. */
751 cid_map_t
*capture_ids
;
752 /* The number of statements parsed (well, the number of ';'s). */
754 /* The identifier replacement vector. */
756 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
757 const char *, capture_info
*,
758 dt_operand
** = 0, int = 0);
761 /* A wrapper around another operand that captures its value. */
763 class capture
: public operand
766 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
767 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
769 /* Identifier index for the value. */
771 /* Whether in a match of two operands the compare should be for
772 equal values rather than equal atoms (boils down to a type
775 /* The captured value. */
777 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
778 const char *, capture_info
*,
779 dt_operand
** = 0, int = 0);
784 class if_expr
: public operand
787 if_expr (location_t loc
)
788 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
794 /* with expression. */
796 class with_expr
: public operand
799 with_expr (location_t loc
)
800 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
808 is_a_helper
<capture
*>::test (operand
*op
)
810 return op
->type
== operand::OP_CAPTURE
;
816 is_a_helper
<predicate
*>::test (operand
*op
)
818 return op
->type
== operand::OP_PREDICATE
;
824 is_a_helper
<c_expr
*>::test (operand
*op
)
826 return op
->type
== operand::OP_C_EXPR
;
832 is_a_helper
<expr
*>::test (operand
*op
)
834 return op
->type
== operand::OP_EXPR
;
840 is_a_helper
<if_expr
*>::test (operand
*op
)
842 return op
->type
== operand::OP_IF
;
848 is_a_helper
<with_expr
*>::test (operand
*op
)
850 return op
->type
== operand::OP_WITH
;
853 /* The main class of a pattern and its transform. This is used to
854 represent both (simplify ...) and (match ...) kinds. The AST
855 duplicates all outer 'if' and 'for' expressions here so each
856 simplify can exist in isolation. */
861 enum simplify_kind
{ SIMPLIFY
, MATCH
};
863 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
864 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
865 cid_map_t
*capture_ids_
)
866 : kind (kind_
), id (id_
), match (match_
), result (result_
),
867 for_vec (for_vec_
), for_subst_vec (vNULL
),
868 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
871 /* ID. This is kept to easily associate related simplifies expanded
872 from the same original one. */
874 /* The expression that is matched against the GENERIC or GIMPLE IL. */
876 /* For a (simplify ...) an expression with ifs and withs with the expression
877 produced when the pattern applies in the leafs.
878 For a (match ...) the leafs are either empty if it is a simple predicate
879 or the single expression specifying the matched operands. */
880 class operand
*result
;
881 /* Collected 'for' expression operators that have to be replaced
882 in the lowering phase. */
883 vec
<vec
<user_id
*> > for_vec
;
884 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
885 /* A map of capture identifiers to indexes. */
886 cid_map_t
*capture_ids
;
890 /* Debugging routines for dumping the AST. */
893 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
895 if (capture
*c
= dyn_cast
<capture
*> (o
))
897 if (c
->what
&& flattened
== false)
898 print_operand (c
->what
, f
, flattened
);
899 fprintf (f
, "@%u", c
->where
);
902 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
903 fprintf (f
, "%s", p
->p
->id
);
905 else if (is_a
<c_expr
*> (o
))
906 fprintf (f
, "c_expr");
908 else if (expr
*e
= dyn_cast
<expr
*> (o
))
910 if (e
->ops
.length () == 0)
911 fprintf (f
, "%s", e
->operation
->id
);
914 fprintf (f
, "(%s", e
->operation
->id
);
916 if (flattened
== false)
918 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
921 print_operand (e
->ops
[i
], f
, flattened
);
933 print_matches (class simplify
*s
, FILE *f
= stderr
)
935 fprintf (f
, "for expression: ");
936 print_operand (s
->match
, f
);
943 /* Lowering of commutative operators. */
946 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
947 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
949 if (n
== ops_vector
.length ())
951 vec
<operand
*> xv
= v
.copy ();
952 result
.safe_push (xv
);
956 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
958 v
[n
] = ops_vector
[n
][i
];
959 cartesian_product (ops_vector
, result
, v
, n
+ 1);
963 /* Lower OP to two operands in case it is marked as commutative. */
965 static vec
<operand
*>
966 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
968 vec
<operand
*> ret
= vNULL
;
970 if (capture
*c
= dyn_cast
<capture
*> (op
))
977 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
978 for (unsigned i
= 0; i
< v
.length (); ++i
)
980 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
987 expr
*e
= dyn_cast
<expr
*> (op
);
988 if (!e
|| e
->ops
.length () == 0)
994 vec
< vec
<operand
*> > ops_vector
= vNULL
;
995 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
996 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
998 auto_vec
< vec
<operand
*> > result
;
999 auto_vec
<operand
*> v (e
->ops
.length ());
1000 v
.quick_grow_cleared (e
->ops
.length ());
1001 cartesian_product (ops_vector
, result
, v
, 0);
1004 for (unsigned i
= 0; i
< result
.length (); ++i
)
1006 expr
*ne
= new expr (e
);
1007 ne
->is_commutative
= false;
1008 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1009 ne
->append_op (result
[i
][j
]);
1013 if (!e
->is_commutative
)
1016 /* The operation is always binary if it isn't inherently commutative. */
1017 int natural_opno
= commutative_op (e
->operation
);
1018 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1019 for (unsigned i
= 0; i
< result
.length (); ++i
)
1021 expr
*ne
= new expr (e
);
1022 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1024 if (comparison_code_p (r
->code
))
1025 ne
->operation
= swap_tree_comparison (r
);
1027 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1029 bool found_compare
= false;
1030 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1031 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1033 if (comparison_code_p (q
->code
)
1034 && swap_tree_comparison (q
) != q
)
1036 found_compare
= true;
1042 user_id
*newop
= new user_id ("<internal>");
1043 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1045 id_base
*subst
= p
->substitutes
[j
];
1046 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1048 if (comparison_code_p (q
->code
))
1049 subst
= swap_tree_comparison (q
);
1051 newop
->substitutes
.safe_push (subst
);
1053 ne
->operation
= newop
;
1054 /* Search for 'p' inside the for vector and push 'newop'
1055 to the same level. */
1056 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1057 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1058 if (for_vec
[j
][k
] == p
)
1060 for_vec
[j
].safe_push (newop
);
1066 ne
->is_commutative
= false;
1067 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1069 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1070 ne
->append_op (result
[i
][old_j
]);
1078 /* Lower operations marked as commutative in the AST of S and push
1079 the resulting patterns to SIMPLIFIERS. */
1082 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1084 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1085 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1087 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1088 s
->for_vec
, s
->capture_ids
);
1089 simplifiers
.safe_push (ns
);
1093 /* Strip conditional operations using group GRP from O and its
1094 children if STRIP, else replace them with an unconditional operation. */
1097 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1099 if (capture
*c
= dyn_cast
<capture
*> (o
))
1102 return new capture (c
->location
, c
->where
,
1103 lower_opt (c
->what
, grp
, strip
),
1109 expr
*e
= dyn_cast
<expr
*> (o
);
1113 if (e
->opt_grp
== grp
)
1116 return lower_opt (e
->ops
[0], grp
, strip
);
1118 expr
*ne
= new expr (e
);
1120 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1124 expr
*ne
= new expr (e
);
1125 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1126 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1131 /* Determine whether O or its children uses the conditional operation
1135 has_opt (operand
*o
, unsigned char grp
)
1137 if (capture
*c
= dyn_cast
<capture
*> (o
))
1140 return has_opt (c
->what
, grp
);
1145 expr
*e
= dyn_cast
<expr
*> (o
);
1149 if (e
->opt_grp
== grp
)
1152 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1153 if (has_opt (e
->ops
[i
], grp
))
1159 /* Lower conditional convert operators in O, expanding it to a vector
1162 static vec
<operand
*>
1163 lower_opt (operand
*o
)
1165 vec
<operand
*> v1
= vNULL
, v2
;
1169 /* Conditional operations are lowered to a pattern with the
1170 operation and one without. All different conditional operation
1171 groups are lowered separately. */
1173 for (unsigned i
= 1; i
<= 10; ++i
)
1176 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1177 if (has_opt (v1
[j
], i
))
1179 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1180 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1186 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1187 v1
.safe_push (v2
[j
]);
1194 /* Lower conditional convert operators in the AST of S and push
1195 the resulting multiple patterns to SIMPLIFIERS. */
1198 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1200 vec
<operand
*> matchers
= lower_opt (s
->match
);
1201 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1203 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1204 s
->for_vec
, s
->capture_ids
);
1205 simplifiers
.safe_push (ns
);
1209 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1210 GENERIC and a GIMPLE variant. */
1212 static vec
<operand
*>
1213 lower_cond (operand
*o
)
1215 vec
<operand
*> ro
= vNULL
;
1217 if (capture
*c
= dyn_cast
<capture
*> (o
))
1221 vec
<operand
*> lop
= vNULL
;
1222 lop
= lower_cond (c
->what
);
1224 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1225 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1231 expr
*e
= dyn_cast
<expr
*> (o
);
1232 if (!e
|| e
->ops
.length () == 0)
1238 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1239 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1240 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1242 auto_vec
< vec
<operand
*> > result
;
1243 auto_vec
<operand
*> v (e
->ops
.length ());
1244 v
.quick_grow_cleared (e
->ops
.length ());
1245 cartesian_product (ops_vector
, result
, v
, 0);
1247 for (unsigned i
= 0; i
< result
.length (); ++i
)
1249 expr
*ne
= new expr (e
);
1250 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1251 ne
->append_op (result
[i
][j
]);
1253 /* If this is a COND with a captured expression or an
1254 expression with two operands then also match a GENERIC
1255 form on the compare. */
1256 if ((*e
->operation
== COND_EXPR
1257 || *e
->operation
== VEC_COND_EXPR
)
1258 && ((is_a
<capture
*> (e
->ops
[0])
1259 && as_a
<capture
*> (e
->ops
[0])->what
1260 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1262 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1263 || (is_a
<expr
*> (e
->ops
[0])
1264 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1267 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1268 ne
->append_op (result
[i
][j
]);
1269 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1271 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1272 expr
*cmp
= new expr (ocmp
);
1273 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1274 cmp
->append_op (ocmp
->ops
[j
]);
1275 cmp
->is_generic
= true;
1276 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1281 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1282 expr
*cmp
= new expr (ocmp
);
1283 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1284 cmp
->append_op (ocmp
->ops
[j
]);
1285 cmp
->is_generic
= true;
1295 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1296 GENERIC and a GIMPLE variant. */
1299 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1301 vec
<operand
*> matchers
= lower_cond (s
->match
);
1302 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1304 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1305 s
->for_vec
, s
->capture_ids
);
1306 simplifiers
.safe_push (ns
);
1310 /* Return true if O refers to ID. */
1313 contains_id (operand
*o
, user_id
*id
)
1315 if (capture
*c
= dyn_cast
<capture
*> (o
))
1316 return c
->what
&& contains_id (c
->what
, id
);
1318 if (expr
*e
= dyn_cast
<expr
*> (o
))
1320 if (e
->operation
== id
)
1322 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1323 if (contains_id (e
->ops
[i
], id
))
1328 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1329 return (contains_id (w
->with
, id
)
1330 || contains_id (w
->subexpr
, id
));
1332 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1333 return (contains_id (ife
->cond
, id
)
1334 || contains_id (ife
->trueexpr
, id
)
1335 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1337 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1338 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1344 /* In AST operand O replace operator ID with operator WITH. */
1347 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1349 /* Deep-copy captures and expressions, replacing operations as
1351 if (capture
*c
= dyn_cast
<capture
*> (o
))
1355 return new capture (c
->location
, c
->where
,
1356 replace_id (c
->what
, id
, with
), c
->value_match
);
1358 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1360 expr
*ne
= new expr (e
);
1361 if (e
->operation
== id
)
1362 ne
->operation
= with
;
1363 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1364 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1367 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1369 with_expr
*nw
= new with_expr (w
->location
);
1370 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1371 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1374 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1376 if_expr
*nife
= new if_expr (ife
->location
);
1377 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1378 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1380 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1384 /* For c_expr we simply record a string replacement table which is
1385 applied at code-generation time. */
1386 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1388 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1389 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1390 return new c_expr (ce
->r
, ce
->location
,
1391 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1397 /* Return true if the binary operator OP is ok for delayed substitution
1398 during for lowering. */
1401 binary_ok (operator_id
*op
)
1408 case TRUNC_DIV_EXPR
:
1410 case FLOOR_DIV_EXPR
:
1411 case ROUND_DIV_EXPR
:
1412 case TRUNC_MOD_EXPR
:
1414 case FLOOR_MOD_EXPR
:
1415 case ROUND_MOD_EXPR
:
1417 case EXACT_DIV_EXPR
:
1429 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1432 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1434 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1435 unsigned worklist_start
= 0;
1436 auto_vec
<simplify
*> worklist
;
1437 worklist
.safe_push (sin
);
1439 /* Lower each recorded for separately, operating on the
1440 set of simplifiers created by the previous one.
1441 Lower inner-to-outer so inner for substitutes can refer
1442 to operators replaced by outer fors. */
1443 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1445 vec
<user_id
*>& ids
= for_vec
[fi
];
1446 unsigned n_ids
= ids
.length ();
1447 unsigned max_n_opers
= 0;
1448 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1449 for (unsigned i
= 0; i
< n_ids
; ++i
)
1451 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1452 max_n_opers
= ids
[i
]->substitutes
.length ();
1453 /* Require that all substitutes are of the same kind so that
1454 if we delay substitution to the result op code generation
1455 can look at the first substitute for deciding things like
1456 types of operands. */
1457 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1458 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1459 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1460 can_delay_subst
= false;
1461 else if (operator_id
*op
1462 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1465 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1466 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1467 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1469 /* Unfortunately we can't just allow all tcc_binary. */
1470 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1471 && strcmp (op0
->tcc
, "tcc_binary") == 0
1475 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1476 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1477 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1478 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1481 can_delay_subst
= false;
1483 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1486 can_delay_subst
= false;
1489 unsigned worklist_end
= worklist
.length ();
1490 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1492 simplify
*s
= worklist
[si
];
1493 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1495 operand
*match_op
= s
->match
;
1496 operand
*result_op
= s
->result
;
1497 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1499 for (unsigned i
= 0; i
< n_ids
; ++i
)
1501 user_id
*id
= ids
[i
];
1502 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1504 && (contains_id (match_op
, id
)
1505 || contains_id (result_op
, id
)))
1510 subst
.quick_push (std::make_pair (id
, oper
));
1511 match_op
= replace_id (match_op
, id
, oper
);
1513 && !can_delay_subst
)
1514 result_op
= replace_id (result_op
, id
, oper
);
1519 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1520 vNULL
, s
->capture_ids
);
1521 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1524 ns
->for_subst_vec
.safe_splice (subst
);
1526 worklist
.safe_push (ns
);
1529 worklist_start
= worklist_end
;
1532 /* Copy out the result from the last for lowering. */
1533 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1534 simplifiers
.safe_push (worklist
[i
]);
1537 /* Lower the AST for everything in SIMPLIFIERS. */
1540 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1542 auto_vec
<simplify
*> out_simplifiers
;
1543 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1544 lower_opt (simplifiers
[i
], out_simplifiers
);
1546 simplifiers
.truncate (0);
1547 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1548 lower_commutative (out_simplifiers
[i
], simplifiers
);
1550 out_simplifiers
.truncate (0);
1552 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1553 lower_cond (simplifiers
[i
], out_simplifiers
);
1555 out_simplifiers
.safe_splice (simplifiers
);
1558 simplifiers
.truncate (0);
1559 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1560 lower_for (out_simplifiers
[i
], simplifiers
);
1566 /* The decision tree built for generating GIMPLE and GENERIC pattern
1567 matching code. It represents the 'match' expression of all
1568 simplifies and has those as its leafs. */
1572 /* A hash-map collecting semantically equivalent leafs in the decision
1573 tree for splitting out to separate functions. */
1582 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1585 static inline hashval_t
hash (const key_type
&);
1586 static inline bool equal_keys (const key_type
&, const key_type
&);
1587 template <typename T
> static inline void remove (T
&) {}
1590 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1593 /* Current simplifier ID we are processing during insertion into the
1595 static unsigned current_id
;
1597 /* Decision tree base class, used for DT_NODE. */
1602 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1607 vec
<dt_node
*> kids
;
1611 unsigned total_size
;
1614 dt_node (enum dt_type type_
, dt_node
*parent_
)
1615 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1617 dt_node
*append_node (dt_node
*);
1618 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1619 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1620 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1622 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1624 virtual void gen (FILE *, int, bool, int) {}
1626 void gen_kids (FILE *, int, bool, int);
1627 void gen_kids_1 (FILE *, int, bool, int,
1628 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1629 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1631 void analyze (sinfo_map_t
&);
1634 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1636 class dt_operand
: public dt_node
1640 dt_operand
*match_dop
;
1645 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1646 dt_operand
*parent_
, unsigned pos_
)
1647 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1648 pos (pos_
), value_match (false), for_id (current_id
) {}
1650 void gen (FILE *, int, bool, int);
1651 unsigned gen_predicate (FILE *, int, const char *, bool);
1652 unsigned gen_match_op (FILE *, int, const char *, bool);
1654 unsigned gen_gimple_expr (FILE *, int, int);
1655 unsigned gen_generic_expr (FILE *, int, const char *);
1657 char *get_name (char *);
1658 void gen_opname (char *, unsigned);
1661 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1663 class dt_simplify
: public dt_node
1667 unsigned pattern_no
;
1668 dt_operand
**indexes
;
1671 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1672 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1673 indexes (indexes_
), info (NULL
) {}
1675 void gen_1 (FILE *, int, bool, operand
*);
1676 void gen (FILE *f
, int, bool, int);
1682 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1684 return (n
->type
== dt_node::DT_OPERAND
1685 || n
->type
== dt_node::DT_MATCH
1686 || n
->type
== dt_node::DT_TRUE
);
1692 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1694 return n
->type
== dt_node::DT_SIMPLIFY
;
1699 /* A container for the actual decision tree. */
1706 void insert (class simplify
*, unsigned);
1707 void gen (FILE *f
, bool gimple
);
1708 void print (FILE *f
= stderr
);
1710 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1712 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1713 unsigned pos
= 0, dt_node
*parent
= 0);
1714 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1715 static bool cmp_node (dt_node
*, dt_node
*);
1716 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1719 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1722 cmp_operand (operand
*o1
, operand
*o2
)
1724 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1727 if (o1
->type
== operand::OP_PREDICATE
)
1729 predicate
*p1
= as_a
<predicate
*>(o1
);
1730 predicate
*p2
= as_a
<predicate
*>(o2
);
1731 return p1
->p
== p2
->p
;
1733 else if (o1
->type
== operand::OP_EXPR
)
1735 expr
*e1
= static_cast<expr
*>(o1
);
1736 expr
*e2
= static_cast<expr
*>(o2
);
1737 return (e1
->operation
== e2
->operation
1738 && e1
->is_generic
== e2
->is_generic
);
1744 /* Compare two decision tree nodes N1 and N2 and return true if they
1748 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1750 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1756 if (n1
->type
== dt_node::DT_TRUE
)
1759 if (n1
->type
== dt_node::DT_OPERAND
)
1760 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1761 (as_a
<dt_operand
*> (n2
))->op
);
1762 else if (n1
->type
== dt_node::DT_MATCH
)
1763 return (((as_a
<dt_operand
*> (n1
))->match_dop
1764 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1765 && ((as_a
<dt_operand
*> (n1
))->value_match
1766 == (as_a
<dt_operand
*> (n2
))->value_match
));
1770 /* Search OPS for a decision tree node like P and return it if found. */
1773 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1775 /* We can merge adjacent DT_TRUE. */
1776 if (p
->type
== dt_node::DT_TRUE
1778 && ops
.last ()->type
== dt_node::DT_TRUE
)
1780 dt_operand
*true_node
= NULL
;
1781 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1783 /* But we can't merge across DT_TRUE nodes as they serve as
1784 pattern order barriers to make sure that patterns apply
1785 in order of appearance in case multiple matches are possible. */
1786 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1789 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1790 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1792 if (decision_tree::cmp_node (ops
[i
], p
))
1794 /* Unless we are processing the same pattern or the blocking
1795 pattern is before the one we are going to merge with. */
1797 && true_node
->for_id
!= current_id
1798 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1802 location_t p_loc
= 0;
1803 if (p
->type
== dt_node::DT_OPERAND
)
1804 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1805 location_t op_loc
= 0;
1806 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1807 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1808 location_t true_loc
= 0;
1809 true_loc
= true_node
->op
->location
;
1811 "failed to merge decision tree node");
1813 "with the following");
1814 warning_at (true_loc
,
1815 "because of the following which serves as ordering "
1826 /* Append N to the decision tree if it there is not already an existing
1830 dt_node::append_node (dt_node
*n
)
1834 kid
= decision_tree::find_node (kids
, n
);
1839 n
->level
= this->level
+ 1;
1844 /* Append OP to the decision tree. */
1847 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1849 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1850 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1851 return append_node (n
);
1854 /* Append a DT_TRUE decision tree node. */
1857 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1859 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1860 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1861 return append_node (n
);
1864 /* Append a DT_MATCH decision tree node. */
1867 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1868 dt_node
*parent
, unsigned pos
)
1870 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1871 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1872 return append_node (n
);
1875 /* Append S to the decision tree. */
1878 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1879 dt_operand
**indexes
)
1882 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1883 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1884 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1886 || s
->match
->location
!= s2
->s
->match
->location
))
1888 /* With a nested patters, it's hard to avoid these in order
1889 to keep match.pd rules relatively small. */
1890 warning_at (s
->match
->location
, "duplicate pattern");
1891 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1892 print_operand (s
->match
, stderr
);
1893 fprintf (stderr
, "\n");
1895 return append_node (n
);
1898 /* Analyze the node and its children. */
1901 dt_node::analyze (sinfo_map_t
&map
)
1907 if (type
== DT_SIMPLIFY
)
1909 /* Populate the map of equivalent simplifies. */
1910 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1912 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1927 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1929 kids
[i
]->analyze (map
);
1930 num_leafs
+= kids
[i
]->num_leafs
;
1931 total_size
+= kids
[i
]->total_size
;
1932 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1936 /* Insert O into the decision tree and return the decision tree node found
1940 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1941 unsigned pos
, dt_node
*parent
)
1943 dt_node
*q
, *elm
= 0;
1945 if (capture
*c
= dyn_cast
<capture
*> (o
))
1947 unsigned capt_index
= c
->where
;
1949 if (indexes
[capt_index
] == 0)
1952 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1955 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1958 // get to the last capture
1959 for (operand
*what
= c
->what
;
1960 what
&& is_a
<capture
*> (what
);
1961 c
= as_a
<capture
*> (what
), what
= c
->what
)
1966 unsigned cc_index
= c
->where
;
1967 dt_operand
*match_op
= indexes
[cc_index
];
1969 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1970 elm
= decision_tree::find_node (p
->kids
, &temp
);
1974 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1975 match
.value_match
= c
->value_match
;
1976 elm
= decision_tree::find_node (p
->kids
, &match
);
1981 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1982 elm
= decision_tree::find_node (p
->kids
, &temp
);
1986 gcc_assert (elm
->type
== dt_node::DT_TRUE
1987 || elm
->type
== dt_node::DT_OPERAND
1988 || elm
->type
== dt_node::DT_MATCH
);
1989 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1994 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
1995 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1997 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2002 p
= p
->append_op (o
, parent
, pos
);
2005 if (expr
*e
= dyn_cast
<expr
*>(o
))
2007 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2008 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2014 /* Insert S into the decision tree. */
2017 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2020 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2021 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2022 p
->append_simplify (s
, pattern_no
, indexes
);
2025 /* Debug functions to dump the decision tree. */
2028 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2030 if (p
->type
== dt_node::DT_NODE
)
2031 fprintf (f
, "root");
2035 for (unsigned i
= 0; i
< indent
; i
++)
2038 if (p
->type
== dt_node::DT_OPERAND
)
2040 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2041 print_operand (dop
->op
, f
, true);
2043 else if (p
->type
== dt_node::DT_TRUE
)
2044 fprintf (f
, "true");
2045 else if (p
->type
== dt_node::DT_MATCH
)
2046 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2047 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2049 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2050 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2051 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2052 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2055 if (is_a
<dt_operand
*> (p
))
2056 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2059 fprintf (stderr
, " (%p, %p), %u, %u\n",
2060 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2062 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2063 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2067 decision_tree::print (FILE *f
)
2069 return decision_tree::print_node (root
, f
);
2073 /* For GENERIC we have to take care of wrapping multiple-used
2074 expressions with side-effects in save_expr and preserve side-effects
2075 of expressions with omit_one_operand. Analyze captures in
2076 match, result and with expressions and perform early-outs
2077 on the outermost match expression operands for cases we cannot
2083 capture_info (simplify
*s
, operand
*, bool);
2084 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2085 bool walk_result (operand
*o
, bool, operand
*);
2086 void walk_c_expr (c_expr
*);
2092 bool force_no_side_effects_p
;
2093 bool force_single_use
;
2094 bool cond_expr_cond_p
;
2095 unsigned long toplevel_msk
;
2096 unsigned match_use_count
;
2097 unsigned result_use_count
;
2102 auto_vec
<cinfo
> info
;
2103 unsigned long force_no_side_effects
;
2107 /* Analyze captures in S. */
2109 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2114 if (s
->kind
== simplify::MATCH
)
2116 force_no_side_effects
= -1;
2120 force_no_side_effects
= 0;
2121 info
.safe_grow_cleared (s
->capture_max
+ 1);
2122 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2123 info
[i
].same_as
= i
;
2125 e
= as_a
<expr
*> (s
->match
);
2126 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2127 walk_match (e
->ops
[i
], i
,
2128 (i
!= 0 && *e
->operation
== COND_EXPR
)
2129 || *e
->operation
== TRUTH_ANDIF_EXPR
2130 || *e
->operation
== TRUTH_ORIF_EXPR
,
2132 && (*e
->operation
== COND_EXPR
2133 || *e
->operation
== VEC_COND_EXPR
));
2135 walk_result (s
->result
, false, result
);
2138 /* Analyze captures in the match expression piece O. */
2141 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2142 bool conditional_p
, bool cond_expr_cond_p
)
2144 if (capture
*c
= dyn_cast
<capture
*> (o
))
2146 unsigned where
= c
->where
;
2147 info
[where
].match_use_count
++;
2148 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2149 info
[where
].force_no_side_effects_p
|= conditional_p
;
2150 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2155 /* Recurse to exprs and captures. */
2156 if (is_a
<capture
*> (c
->what
)
2157 || is_a
<expr
*> (c
->what
))
2158 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2159 /* We need to look past multiple captures to find a captured
2160 expression as with conditional converts two captures
2161 can be collapsed onto the same expression. Also collect
2162 what captures capture the same thing. */
2163 while (c
->what
&& is_a
<capture
*> (c
->what
))
2165 c
= as_a
<capture
*> (c
->what
);
2166 if (info
[c
->where
].same_as
!= c
->where
2167 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2168 fatal_at (c
->location
, "cannot handle this collapsed capture");
2169 info
[c
->where
].same_as
= info
[where
].same_as
;
2171 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2174 && (e
= dyn_cast
<expr
*> (c
->what
)))
2176 /* Zero-operand expression captures like ADDR_EXPR@0 are
2177 similar as predicates -- if they are not mentioned in
2178 the result we have to force them to have no side-effects. */
2179 if (e
->ops
.length () != 0)
2180 info
[where
].expr_p
= true;
2181 info
[where
].force_single_use
|= e
->force_single_use
;
2184 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2186 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2188 bool cond_p
= conditional_p
;
2189 bool expr_cond_p
= false;
2190 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2192 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2193 || *e
->operation
== TRUTH_ORIF_EXPR
)
2196 && (*e
->operation
== COND_EXPR
2197 || *e
->operation
== VEC_COND_EXPR
))
2199 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2202 else if (is_a
<predicate
*> (o
))
2204 /* Mark non-captured leafs toplevel arg for checking. */
2205 force_no_side_effects
|= 1 << toplevel_arg
;
2208 warning_at (o
->location
,
2209 "forcing no side-effects on possibly lost leaf");
2215 /* Analyze captures in the result expression piece O. Return true
2216 if RESULT was visited in one of the children. Only visit
2217 non-if/with children if they are rooted on RESULT. */
2220 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2222 if (capture
*c
= dyn_cast
<capture
*> (o
))
2224 unsigned where
= info
[c
->where
].same_as
;
2225 info
[where
].result_use_count
++;
2226 /* If we substitute an expression capture we don't know
2227 which captures this will end up using (well, we don't
2228 compute that). Force the uses to be side-effect free
2229 which means forcing the toplevels that reach the
2230 expression side-effect free. */
2231 if (info
[where
].expr_p
)
2232 force_no_side_effects
|= info
[where
].toplevel_msk
;
2233 /* Mark CSE capture uses as forced to have no side-effects. */
2235 && is_a
<expr
*> (c
->what
))
2237 info
[where
].cse_p
= true;
2238 walk_result (c
->what
, true, result
);
2241 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2243 id_base
*opr
= e
->operation
;
2244 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2245 opr
= uid
->substitutes
[0];
2246 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2248 bool cond_p
= conditional_p
;
2249 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2251 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2252 || *e
->operation
== TRUTH_ORIF_EXPR
)
2254 walk_result (e
->ops
[i
], cond_p
, result
);
2257 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2259 /* 'if' conditions should be all fine. */
2260 if (ie
->trueexpr
== result
)
2262 walk_result (ie
->trueexpr
, false, result
);
2265 if (ie
->falseexpr
== result
)
2267 walk_result (ie
->falseexpr
, false, result
);
2271 if (is_a
<if_expr
*> (ie
->trueexpr
)
2272 || is_a
<with_expr
*> (ie
->trueexpr
))
2273 res
|= walk_result (ie
->trueexpr
, false, result
);
2275 && (is_a
<if_expr
*> (ie
->falseexpr
)
2276 || is_a
<with_expr
*> (ie
->falseexpr
)))
2277 res
|= walk_result (ie
->falseexpr
, false, result
);
2280 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2282 bool res
= (we
->subexpr
== result
);
2284 || is_a
<if_expr
*> (we
->subexpr
)
2285 || is_a
<with_expr
*> (we
->subexpr
))
2286 res
|= walk_result (we
->subexpr
, false, result
);
2288 walk_c_expr (we
->with
);
2291 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2299 /* Look for captures in the C expr E. */
2302 capture_info::walk_c_expr (c_expr
*e
)
2304 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2305 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2306 really escape through. */
2307 unsigned p_depth
= 0;
2308 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2310 const cpp_token
*t
= &e
->code
[i
];
2311 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2313 if (t
->type
== CPP_NAME
2314 && (strcmp ((const char *)CPP_HASHNODE
2315 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2316 || strcmp ((const char *)CPP_HASHNODE
2317 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2318 || strcmp ((const char *)CPP_HASHNODE
2319 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2320 || ((id
= get_operator ((const char *)CPP_HASHNODE
2321 (t
->val
.node
.node
)->ident
.str
))
2322 && is_a
<predicate_id
*> (id
)))
2323 && n
->type
== CPP_OPEN_PAREN
)
2325 else if (t
->type
== CPP_CLOSE_PAREN
2328 else if (p_depth
== 0
2329 && t
->type
== CPP_ATSIGN
2330 && (n
->type
== CPP_NUMBER
2331 || n
->type
== CPP_NAME
)
2332 && !(n
->flags
& PREV_WHITE
))
2335 if (n
->type
== CPP_NUMBER
)
2336 id1
= (const char *)n
->val
.str
.text
;
2338 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2339 unsigned *where
= e
->capture_ids
->get(id1
);
2341 fatal_at (n
, "unknown capture id '%s'", id1
);
2342 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2345 warning_at (t
, "capture escapes");
2351 /* Code generation off the decision tree and the refered AST nodes. */
2354 is_conversion (id_base
*op
)
2356 return (*op
== CONVERT_EXPR
2358 || *op
== FLOAT_EXPR
2359 || *op
== FIX_TRUNC_EXPR
2360 || *op
== VIEW_CONVERT_EXPR
);
2363 /* Get the type to be used for generating operand POS of OP from the
2367 get_operand_type (id_base
*op
, unsigned pos
,
2368 const char *in_type
,
2369 const char *expr_type
,
2370 const char *other_oprnd_type
)
2372 /* Generally operands whose type does not match the type of the
2373 expression generated need to know their types but match and
2374 thus can fall back to 'other_oprnd_type'. */
2375 if (is_conversion (op
))
2376 return other_oprnd_type
;
2377 else if (*op
== REALPART_EXPR
2378 || *op
== IMAGPART_EXPR
)
2379 return other_oprnd_type
;
2380 else if (is_a
<operator_id
*> (op
)
2381 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2382 return other_oprnd_type
;
2383 else if (*op
== COND_EXPR
2385 return "boolean_type_node";
2386 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2388 /* IFN_COND_* operands 1 and later by default have the same type
2389 as the result. The type of operand 0 needs to be specified
2391 if (pos
> 0 && expr_type
)
2393 else if (pos
> 0 && in_type
)
2400 /* Otherwise all types should match - choose one in order of
2407 return other_oprnd_type
;
2411 /* Generate transform code for an expression. */
2414 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2415 int depth
, const char *in_type
, capture_info
*cinfo
,
2416 dt_operand
**indexes
, int)
2418 id_base
*opr
= operation
;
2419 /* When we delay operator substituting during lowering of fors we
2420 make sure that for code-gen purposes the effects of each substitute
2421 are the same. Thus just look at that. */
2422 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2423 opr
= uid
->substitutes
[0];
2425 bool conversion_p
= is_conversion (opr
);
2426 const char *type
= expr_type
;
2429 /* If there was a type specification in the pattern use it. */
2431 else if (conversion_p
)
2432 /* For conversions we need to build the expression using the
2433 outer type passed in. */
2435 else if (*opr
== REALPART_EXPR
2436 || *opr
== IMAGPART_EXPR
)
2438 /* __real and __imag use the component type of its operand. */
2439 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2443 else if (is_a
<operator_id
*> (opr
)
2444 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2446 /* comparisons use boolean_type_node (or what gets in), but
2447 their operands need to figure out the types themselves. */
2452 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2457 else if (*opr
== COND_EXPR
2458 || *opr
== VEC_COND_EXPR
2459 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2461 /* Conditions are of the same type as their first alternative. */
2462 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2467 /* Other operations are of the same type as their first operand. */
2468 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2472 fatal_at (location
, "cannot determine type of operand");
2474 fprintf_indent (f
, indent
, "{\n");
2476 fprintf_indent (f
, indent
,
2477 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2479 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2480 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2483 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2485 = get_operand_type (opr
, i
, in_type
, expr_type
,
2486 i
== 0 ? NULL
: op0type
);
2487 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2490 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2493 const char *opr_name
;
2494 if (*operation
== CONVERT_EXPR
)
2495 opr_name
= "NOP_EXPR";
2497 opr_name
= operation
->id
;
2501 if (*opr
== CONVERT_EXPR
)
2503 fprintf_indent (f
, indent
,
2504 "if (%s != TREE_TYPE (_o%d[0])\n",
2506 fprintf_indent (f
, indent
,
2507 " && !useless_type_conversion_p (%s, TREE_TYPE "
2510 fprintf_indent (f
, indent
+ 2, "{\n");
2513 /* ??? Building a stmt can fail for various reasons here, seq being
2514 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2515 So if we fail here we should continue matching other patterns. */
2516 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2517 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2518 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2519 fprintf (f
, ", _o%d[%u]", depth
, i
);
2520 fprintf (f
, ");\n");
2521 fprintf_indent (f
, indent
, "tem_op.resimplify (lseq, valueize);\n");
2522 fprintf_indent (f
, indent
,
2523 "_r%d = maybe_push_res_to_seq (&tem_op, lseq);\n", depth
);
2524 fprintf_indent (f
, indent
,
2525 "if (!_r%d) return false;\n",
2527 if (*opr
== CONVERT_EXPR
)
2530 fprintf_indent (f
, indent
, " }\n");
2531 fprintf_indent (f
, indent
, "else\n");
2532 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2537 if (*opr
== CONVERT_EXPR
)
2539 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2543 if (opr
->kind
== id_base::CODE
)
2544 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2545 depth
, ops
.length(), opr_name
, type
);
2548 fprintf_indent (f
, indent
, "{\n");
2549 fprintf_indent (f
, indent
, " _r%d = maybe_build_call_expr_loc (loc, "
2550 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2552 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2553 fprintf (f
, ", _o%d[%u]", depth
, i
);
2554 fprintf (f
, ");\n");
2555 if (opr
->kind
!= id_base::CODE
)
2557 fprintf_indent (f
, indent
, " if (!_r%d)\n", depth
);
2558 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2559 fprintf_indent (f
, indent
, "}\n");
2561 if (*opr
== CONVERT_EXPR
)
2564 fprintf_indent (f
, indent
, "else\n");
2565 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2568 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2570 fprintf_indent (f
, indent
, "}\n");
2573 /* Generate code for a c_expr which is either the expression inside
2574 an if statement or a sequence of statements which computes a
2575 result to be stored to DEST. */
2578 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2579 bool, int, const char *, capture_info
*,
2582 if (dest
&& nr_stmts
== 1)
2583 fprintf_indent (f
, indent
, "%s = ", dest
);
2585 unsigned stmt_nr
= 1;
2587 for (unsigned i
= 0; i
< code
.length (); ++i
)
2589 const cpp_token
*token
= &code
[i
];
2591 /* We can't recover from all lexing losses but we can roughly restore line
2592 breaks from location info. */
2593 const line_map_ordinary
*map
;
2594 linemap_resolve_location (line_table
, token
->src_loc
,
2595 LRK_SPELLING_LOCATION
, &map
);
2596 expanded_location loc
= linemap_expand_location (line_table
, map
,
2598 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2600 prev_line
= loc
.line
;
2602 /* Replace captures for code-gen. */
2603 if (token
->type
== CPP_ATSIGN
)
2605 const cpp_token
*n
= &code
[i
+1];
2606 if ((n
->type
== CPP_NUMBER
2607 || n
->type
== CPP_NAME
)
2608 && !(n
->flags
& PREV_WHITE
))
2610 if (token
->flags
& PREV_WHITE
)
2613 if (n
->type
== CPP_NUMBER
)
2614 id
= (const char *)n
->val
.str
.text
;
2616 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2617 unsigned *cid
= capture_ids
->get (id
);
2619 fatal_at (token
, "unknown capture id");
2620 fprintf (f
, "captures[%u]", *cid
);
2626 if (token
->flags
& PREV_WHITE
)
2629 if (token
->type
== CPP_NAME
)
2631 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2633 for (j
= 0; j
< ids
.length (); ++j
)
2635 if (strcmp (id
, ids
[j
].id
) == 0)
2637 fprintf (f
, "%s", ids
[j
].oper
);
2641 if (j
< ids
.length ())
2645 /* Output the token as string. */
2646 char *tk
= (char *)cpp_token_as_text (r
, token
);
2649 if (token
->type
== CPP_SEMICOLON
)
2652 if (dest
&& stmt_nr
== nr_stmts
)
2653 fprintf_indent (f
, indent
, "%s = ", dest
);
2659 /* Generate transform code for a capture. */
2662 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2663 int depth
, const char *in_type
, capture_info
*cinfo
,
2664 dt_operand
**indexes
, int cond_handling
)
2666 if (what
&& is_a
<expr
*> (what
))
2668 if (indexes
[where
] == 0)
2671 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2672 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2677 /* If in GENERIC some capture is used multiple times, unshare it except
2678 when emitting the last use. */
2680 && cinfo
->info
.exists ()
2681 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2683 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2685 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2688 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2690 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2691 with substituting a capture of that. */
2693 && cond_handling
!= 0
2694 && cinfo
->info
[where
].cond_expr_cond_p
)
2696 /* If substituting into a cond_expr condition, unshare. */
2697 if (cond_handling
== 1)
2698 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2699 /* If substituting elsewhere we might need to decompose it. */
2700 else if (cond_handling
== 2)
2702 /* ??? Returning false here will also not allow any other patterns
2703 to match unless this generator was split out. */
2704 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2705 fprintf_indent (f
, indent
, " {\n");
2706 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2707 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2709 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2710 " TREE_OPERAND (%s, 1));\n",
2711 dest
, dest
, dest
, dest
, dest
);
2712 fprintf_indent (f
, indent
, " }\n");
2717 /* Return the name of the operand representing the decision tree node.
2718 Use NAME as space to generate it. */
2721 dt_operand::get_name (char *name
)
2724 sprintf (name
, "t");
2725 else if (parent
->level
== 1)
2726 sprintf (name
, "_p%u", pos
);
2727 else if (parent
->type
== dt_node::DT_MATCH
)
2728 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2730 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2734 /* Fill NAME with the operand name at position POS. */
2737 dt_operand::gen_opname (char *name
, unsigned pos
)
2740 sprintf (name
, "_p%u", pos
);
2742 sprintf (name
, "_q%u%u", level
, pos
);
2745 /* Generate matching code for the decision tree operand which is
2749 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2751 predicate
*p
= as_a
<predicate
*> (op
);
2753 if (p
->p
->matchers
.exists ())
2755 /* If this is a predicate generated from a pattern mangle its
2756 name and pass on the valueize hook. */
2758 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2761 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2764 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2765 fprintf_indent (f
, indent
+ 2, "{\n");
2769 /* Generate matching code for the decision tree operand which is
2773 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2775 char match_opname
[20];
2776 match_dop
->get_name (match_opname
);
2778 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2779 "|| operand_equal_p (%s, %s, 0))\n",
2780 opname
, match_opname
, opname
, opname
, match_opname
);
2782 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2783 "|| (operand_equal_p (%s, %s, 0) "
2784 "&& types_match (%s, %s)))\n",
2785 opname
, match_opname
, opname
, opname
, match_opname
,
2786 opname
, match_opname
);
2787 fprintf_indent (f
, indent
+ 2, "{\n");
2791 /* Generate GIMPLE matching code for the decision tree operand. */
2794 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2796 expr
*e
= static_cast<expr
*> (op
);
2797 id_base
*id
= e
->operation
;
2798 unsigned n_ops
= e
->ops
.length ();
2799 unsigned n_braces
= 0;
2801 for (unsigned i
= 0; i
< n_ops
; ++i
)
2803 char child_opname
[20];
2804 gen_opname (child_opname
, i
);
2806 if (id
->kind
== id_base::CODE
)
2809 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2810 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2812 /* ??? If this is a memory operation we can't (and should not)
2813 match this. The only sensible operand types are
2814 SSA names and invariants. */
2819 fprintf_indent (f
, indent
,
2820 "tree %s = TREE_OPERAND (%s, %i);\n",
2821 child_opname
, opname
, i
);
2824 fprintf_indent (f
, indent
,
2825 "tree %s = TREE_OPERAND "
2826 "(gimple_assign_rhs1 (_a%d), %i);\n",
2827 child_opname
, depth
, i
);
2828 fprintf_indent (f
, indent
,
2829 "if ((TREE_CODE (%s) == SSA_NAME\n",
2831 fprintf_indent (f
, indent
,
2832 " || is_gimple_min_invariant (%s)))\n",
2834 fprintf_indent (f
, indent
,
2838 fprintf_indent (f
, indent
,
2839 "%s = do_valueize (valueize, %s);\n",
2840 child_opname
, child_opname
);
2844 fprintf_indent (f
, indent
,
2845 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2846 child_opname
, i
+ 1, depth
);
2849 fprintf_indent (f
, indent
,
2850 "tree %s = gimple_call_arg (_c%d, %u);\n",
2851 child_opname
, depth
, i
);
2852 fprintf_indent (f
, indent
,
2853 "%s = do_valueize (valueize, %s);\n",
2854 child_opname
, child_opname
);
2856 /* While the toplevel operands are canonicalized by the caller
2857 after valueizing operands of sub-expressions we have to
2858 re-canonicalize operand order. */
2859 int opno
= commutative_op (id
);
2862 char child_opname0
[20], child_opname1
[20];
2863 gen_opname (child_opname0
, opno
);
2864 gen_opname (child_opname1
, opno
+ 1);
2865 fprintf_indent (f
, indent
,
2866 "if (tree_swap_operands_p (%s, %s))\n",
2867 child_opname0
, child_opname1
);
2868 fprintf_indent (f
, indent
,
2869 " std::swap (%s, %s);\n",
2870 child_opname0
, child_opname1
);
2876 /* Generate GENERIC matching code for the decision tree operand. */
2879 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2881 expr
*e
= static_cast<expr
*> (op
);
2882 unsigned n_ops
= e
->ops
.length ();
2884 for (unsigned i
= 0; i
< n_ops
; ++i
)
2886 char child_opname
[20];
2887 gen_opname (child_opname
, i
);
2889 if (e
->operation
->kind
== id_base::CODE
)
2890 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2891 child_opname
, opname
, i
);
2893 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2894 child_opname
, opname
, i
);
2900 /* Generate matching code for the children of the decision tree node. */
2903 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2905 auto_vec
<dt_operand
*> gimple_exprs
;
2906 auto_vec
<dt_operand
*> generic_exprs
;
2907 auto_vec
<dt_operand
*> fns
;
2908 auto_vec
<dt_operand
*> generic_fns
;
2909 auto_vec
<dt_operand
*> preds
;
2910 auto_vec
<dt_node
*> others
;
2912 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2914 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2916 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2917 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2919 if (e
->ops
.length () == 0
2920 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2921 generic_exprs
.safe_push (op
);
2922 else if (e
->operation
->kind
== id_base::FN
)
2927 generic_fns
.safe_push (op
);
2929 else if (e
->operation
->kind
== id_base::PREDICATE
)
2930 preds
.safe_push (op
);
2933 if (gimple
&& !e
->is_generic
)
2934 gimple_exprs
.safe_push (op
);
2936 generic_exprs
.safe_push (op
);
2939 else if (op
->op
->type
== operand::OP_PREDICATE
)
2940 others
.safe_push (kids
[i
]);
2944 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2945 others
.safe_push (kids
[i
]);
2946 else if (kids
[i
]->type
== dt_node::DT_MATCH
2947 || kids
[i
]->type
== dt_node::DT_TRUE
)
2949 /* A DT_TRUE operand serves as a barrier - generate code now
2950 for what we have collected sofar.
2951 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2952 dependent matches to get out-of-order. Generate code now
2953 for what we have collected sofar. */
2954 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2955 fns
, generic_fns
, preds
, others
);
2956 /* And output the true operand itself. */
2957 kids
[i
]->gen (f
, indent
, gimple
, depth
);
2958 gimple_exprs
.truncate (0);
2959 generic_exprs
.truncate (0);
2961 generic_fns
.truncate (0);
2963 others
.truncate (0);
2969 /* Generate code for the remains. */
2970 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2971 fns
, generic_fns
, preds
, others
);
2974 /* Generate matching code for the children of the decision tree node. */
2977 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
2978 vec
<dt_operand
*> gimple_exprs
,
2979 vec
<dt_operand
*> generic_exprs
,
2980 vec
<dt_operand
*> fns
,
2981 vec
<dt_operand
*> generic_fns
,
2982 vec
<dt_operand
*> preds
,
2983 vec
<dt_node
*> others
)
2986 char *kid_opname
= buf
;
2988 unsigned exprs_len
= gimple_exprs
.length ();
2989 unsigned gexprs_len
= generic_exprs
.length ();
2990 unsigned fns_len
= fns
.length ();
2991 unsigned gfns_len
= generic_fns
.length ();
2993 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2996 gimple_exprs
[0]->get_name (kid_opname
);
2998 fns
[0]->get_name (kid_opname
);
3000 generic_fns
[0]->get_name (kid_opname
);
3002 generic_exprs
[0]->get_name (kid_opname
);
3004 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3005 fprintf_indent (f
, indent
, " {\n");
3009 if (exprs_len
|| fns_len
)
3012 fprintf_indent (f
, indent
,
3013 "case SSA_NAME:\n");
3014 fprintf_indent (f
, indent
,
3015 " if (gimple *_d%d = get_def (valueize, %s))\n",
3017 fprintf_indent (f
, indent
,
3022 fprintf_indent (f
, indent
,
3023 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3025 fprintf_indent (f
, indent
,
3026 " switch (gimple_assign_rhs_code (_a%d))\n",
3029 fprintf_indent (f
, indent
, "{\n");
3030 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3032 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3033 id_base
*op
= e
->operation
;
3034 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3035 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3037 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3038 fprintf_indent (f
, indent
, " {\n");
3039 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3040 fprintf_indent (f
, indent
, " break;\n");
3041 fprintf_indent (f
, indent
, " }\n");
3043 fprintf_indent (f
, indent
, "default:;\n");
3044 fprintf_indent (f
, indent
, "}\n");
3050 fprintf_indent (f
, indent
,
3051 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3052 exprs_len
? "else " : "", depth
, depth
);
3053 fprintf_indent (f
, indent
,
3054 " switch (gimple_call_combined_fn (_c%d))\n",
3058 fprintf_indent (f
, indent
, "{\n");
3059 for (unsigned i
= 0; i
< fns_len
; ++i
)
3061 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3062 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3063 fprintf_indent (f
, indent
, " {\n");
3064 fns
[i
]->gen (f
, indent
+ 4, true, depth
);
3065 fprintf_indent (f
, indent
, " break;\n");
3066 fprintf_indent (f
, indent
, " }\n");
3069 fprintf_indent (f
, indent
, "default:;\n");
3070 fprintf_indent (f
, indent
, "}\n");
3076 fprintf_indent (f
, indent
, " }\n");
3077 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3078 here rather than in the next loop. */
3079 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3081 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3082 id_base
*op
= e
->operation
;
3083 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3085 fprintf_indent (f
, indent
+ 4, "{\n");
3086 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3087 fprintf_indent (f
, indent
+ 4, "}\n");
3091 fprintf_indent (f
, indent
, " break;\n");
3094 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3096 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3097 id_base
*op
= e
->operation
;
3098 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3099 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3100 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3101 /* Already handled above. */
3104 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3105 fprintf_indent (f
, indent
, " {\n");
3106 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3107 fprintf_indent (f
, indent
, " break;\n");
3108 fprintf_indent (f
, indent
, " }\n");
3113 fprintf_indent (f
, indent
,
3114 "case CALL_EXPR:\n");
3115 fprintf_indent (f
, indent
,
3116 " switch (get_call_combined_fn (%s))\n",
3118 fprintf_indent (f
, indent
,
3122 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3124 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3125 gcc_assert (e
->operation
->kind
== id_base::FN
);
3127 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3128 fprintf_indent (f
, indent
, " {\n");
3129 generic_fns
[j
]->gen (f
, indent
+ 4, false, depth
);
3130 fprintf_indent (f
, indent
, " break;\n");
3131 fprintf_indent (f
, indent
, " }\n");
3133 fprintf_indent (f
, indent
, "default:;\n");
3136 fprintf_indent (f
, indent
, " }\n");
3137 fprintf_indent (f
, indent
, " break;\n");
3140 /* Close switch (TREE_CODE ()). */
3141 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3144 fprintf_indent (f
, indent
, " default:;\n");
3145 fprintf_indent (f
, indent
, " }\n");
3148 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3150 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3151 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3152 preds
[i
]->get_name (kid_opname
);
3153 fprintf_indent (f
, indent
, "{\n");
3155 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3156 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3157 gimple
? "gimple" : "tree",
3158 p
->id
, kid_opname
, kid_opname
,
3159 gimple
? ", valueize" : "");
3160 fprintf_indent (f
, indent
, " {\n");
3161 for (int j
= 0; j
< p
->nargs
; ++j
)
3163 char child_opname
[20];
3164 preds
[i
]->gen_opname (child_opname
, j
);
3165 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3166 child_opname
, kid_opname
, j
);
3168 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3171 fprintf_indent (f
, indent
, "}\n");
3174 for (unsigned i
= 0; i
< others
.length (); ++i
)
3175 others
[i
]->gen (f
, indent
, gimple
, depth
);
3178 /* Generate matching code for the decision tree operand. */
3181 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3186 unsigned n_braces
= 0;
3188 if (type
== DT_OPERAND
)
3191 case operand::OP_PREDICATE
:
3192 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3195 case operand::OP_EXPR
:
3197 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3199 n_braces
= gen_generic_expr (f
, indent
, opname
);
3205 else if (type
== DT_TRUE
)
3207 else if (type
== DT_MATCH
)
3208 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3212 indent
+= 4 * n_braces
;
3213 gen_kids (f
, indent
, gimple
, depth
);
3215 for (unsigned i
= 0; i
< n_braces
; ++i
)
3220 fprintf_indent (f
, indent
, " }\n");
3225 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3226 step of a '(simplify ...)' or '(match ...)'. This handles everything
3227 that is not part of the decision tree (simplify->match).
3228 Main recursive worker. */
3231 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3235 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3237 fprintf_indent (f
, indent
, "{\n");
3239 output_line_directive (f
, w
->location
);
3240 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3241 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3243 fprintf_indent (f
, indent
, "}\n");
3246 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3248 output_line_directive (f
, ife
->location
);
3249 fprintf_indent (f
, indent
, "if (");
3250 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3252 fprintf_indent (f
, indent
+ 2, "{\n");
3254 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3256 fprintf_indent (f
, indent
+ 2, "}\n");
3259 fprintf_indent (f
, indent
, "else\n");
3260 fprintf_indent (f
, indent
+ 2, "{\n");
3262 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3264 fprintf_indent (f
, indent
+ 2, "}\n");
3270 /* Analyze captures and perform early-outs on the incoming arguments
3271 that cover cases we cannot handle. */
3272 capture_info
cinfo (s
, result
, gimple
);
3273 if (s
->kind
== simplify::SIMPLIFY
)
3277 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3278 if (cinfo
.force_no_side_effects
& (1 << i
))
3280 fprintf_indent (f
, indent
,
3281 "if (TREE_SIDE_EFFECTS (_p%d)) return NULL_TREE;\n",
3284 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3285 "forcing toplevel operand to have no "
3288 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3289 if (cinfo
.info
[i
].cse_p
)
3291 else if (cinfo
.info
[i
].force_no_side_effects_p
3292 && (cinfo
.info
[i
].toplevel_msk
3293 & cinfo
.force_no_side_effects
) == 0)
3295 fprintf_indent (f
, indent
,
3296 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3297 "return NULL_TREE;\n", i
);
3299 warning_at (cinfo
.info
[i
].c
->location
,
3300 "forcing captured operand to have no "
3303 else if ((cinfo
.info
[i
].toplevel_msk
3304 & cinfo
.force_no_side_effects
) != 0)
3305 /* Mark capture as having no side-effects if we had to verify
3306 that via forced toplevel operand checks. */
3307 cinfo
.info
[i
].force_no_side_effects_p
= true;
3311 /* Force single-use restriction by only allowing simple
3312 results via setting seq to NULL. */
3313 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3314 bool first_p
= true;
3315 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3316 if (cinfo
.info
[i
].force_single_use
)
3320 fprintf_indent (f
, indent
, "if (lseq\n");
3321 fprintf_indent (f
, indent
, " && (");
3327 fprintf_indent (f
, indent
, " || ");
3329 fprintf (f
, "!single_use (captures[%d])", i
);
3333 fprintf (f
, "))\n");
3334 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3339 if (s
->kind
== simplify::SIMPLIFY
)
3340 fprintf_indent (f
, indent
, "if (__builtin_expect (!dbg_cnt (match), 0)) return %s;\n",
3341 gimple
? "false" : "NULL_TREE");
3343 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3344 "fprintf (dump_file, \"%s ",
3345 s
->kind
== simplify::SIMPLIFY
3346 ? "Applying pattern" : "Matching expression");
3347 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3348 output_line_directive (f
,
3349 result
? result
->location
: s
->match
->location
, true,
3351 fprintf (f
, ", __FILE__, __LINE__);\n");
3355 /* If there is no result then this is a predicate implementation. */
3356 fprintf_indent (f
, indent
, "return true;\n");
3360 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3361 in outermost position). */
3362 if (result
->type
== operand::OP_EXPR
3363 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3364 result
= as_a
<expr
*> (result
)->ops
[0];
3365 if (result
->type
== operand::OP_EXPR
)
3367 expr
*e
= as_a
<expr
*> (result
);
3368 id_base
*opr
= e
->operation
;
3369 bool is_predicate
= false;
3370 /* When we delay operator substituting during lowering of fors we
3371 make sure that for code-gen purposes the effects of each substitute
3372 are the same. Thus just look at that. */
3373 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3374 opr
= uid
->substitutes
[0];
3375 else if (is_a
<predicate_id
*> (opr
))
3376 is_predicate
= true;
3378 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3379 *e
->operation
== CONVERT_EXPR
3380 ? "NOP_EXPR" : e
->operation
->id
,
3382 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3386 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3388 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3390 = get_operand_type (opr
, j
,
3391 "type", e
->expr_type
,
3393 : "TREE_TYPE (res_op->ops[0])");
3394 /* We need to expand GENERIC conditions we captured from
3395 COND_EXPRs and we need to unshare them when substituting
3397 int cond_handling
= 0;
3399 cond_handling
= ((*opr
== COND_EXPR
3400 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3401 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3402 &cinfo
, indexes
, cond_handling
);
3405 /* Re-fold the toplevel result. It's basically an embedded
3406 gimple_build w/o actually building the stmt. */
3408 fprintf_indent (f
, indent
,
3409 "res_op->resimplify (lseq, valueize);\n");
3411 else if (result
->type
== operand::OP_CAPTURE
3412 || result
->type
== operand::OP_C_EXPR
)
3414 fprintf_indent (f
, indent
, "tree tem;\n");
3415 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3417 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3418 if (is_a
<capture
*> (result
)
3419 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3421 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3422 with substituting a capture of that. */
3423 fprintf_indent (f
, indent
,
3424 "if (COMPARISON_CLASS_P (tem))\n");
3425 fprintf_indent (f
, indent
,
3427 fprintf_indent (f
, indent
,
3428 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3429 fprintf_indent (f
, indent
,
3430 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3431 fprintf_indent (f
, indent
,
3437 fprintf_indent (f
, indent
, "return true;\n");
3441 bool is_predicate
= false;
3442 if (result
->type
== operand::OP_EXPR
)
3444 expr
*e
= as_a
<expr
*> (result
);
3445 id_base
*opr
= e
->operation
;
3446 /* When we delay operator substituting during lowering of fors we
3447 make sure that for code-gen purposes the effects of each substitute
3448 are the same. Thus just look at that. */
3449 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3450 opr
= uid
->substitutes
[0];
3451 else if (is_a
<predicate_id
*> (opr
))
3452 is_predicate
= true;
3453 /* Search for captures used multiple times in the result expression
3454 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3455 original expression. */
3457 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3459 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3460 || cinfo
.info
[i
].cse_p
)
3462 if (cinfo
.info
[i
].result_use_count
3463 > cinfo
.info
[i
].match_use_count
)
3464 fprintf_indent (f
, indent
,
3465 "if (! tree_invariant_p (captures[%d])) "
3466 "return NULL_TREE;\n", i
);
3468 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3472 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3475 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3476 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3479 = get_operand_type (opr
, j
,
3480 "type", e
->expr_type
,
3482 ? NULL
: "TREE_TYPE (res_op0)");
3483 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3487 fprintf_indent (f
, indent
, "return true;\n");
3490 fprintf_indent (f
, indent
, "tree _r;\n");
3491 /* Re-fold the toplevel result. Use non_lvalue to
3492 build NON_LVALUE_EXPRs so they get properly
3493 ignored when in GIMPLE form. */
3494 if (*opr
== NON_LVALUE_EXPR
)
3495 fprintf_indent (f
, indent
,
3496 "_r = non_lvalue_loc (loc, res_op0);\n");
3499 if (is_a
<operator_id
*> (opr
))
3500 fprintf_indent (f
, indent
,
3501 "_r = fold_build%d_loc (loc, %s, type",
3503 *e
->operation
== CONVERT_EXPR
3504 ? "NOP_EXPR" : e
->operation
->id
);
3506 fprintf_indent (f
, indent
,
3507 "_r = maybe_build_call_expr_loc (loc, "
3508 "%s, type, %d", e
->operation
->id
,
3510 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3511 fprintf (f
, ", res_op%d", j
);
3512 fprintf (f
, ");\n");
3513 if (!is_a
<operator_id
*> (opr
))
3515 fprintf_indent (f
, indent
, "if (!_r)\n");
3516 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3521 else if (result
->type
== operand::OP_CAPTURE
3522 || result
->type
== operand::OP_C_EXPR
)
3525 fprintf_indent (f
, indent
, "tree _r;\n");
3526 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3533 /* Search for captures not used in the result expression and dependent
3534 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3535 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3537 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3539 if (!cinfo
.info
[i
].force_no_side_effects_p
3540 && !cinfo
.info
[i
].expr_p
3541 && cinfo
.info
[i
].result_use_count
== 0)
3543 fprintf_indent (f
, indent
,
3544 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3546 fprintf_indent (f
, indent
+ 2,
3547 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3548 "fold_ignored_result (captures[%d]), _r);\n",
3552 fprintf_indent (f
, indent
, "return _r;\n");
3557 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3558 step of a '(simplify ...)' or '(match ...)'. This handles everything
3559 that is not part of the decision tree (simplify->match). */
3562 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3564 fprintf_indent (f
, indent
, "{\n");
3566 output_line_directive (f
,
3567 s
->result
? s
->result
->location
: s
->match
->location
);
3568 if (s
->capture_max
>= 0)
3571 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3572 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3574 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3578 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3580 fprintf (f
, " };\n");
3583 /* If we have a split-out function for the actual transform, call it. */
3584 if (info
&& info
->fname
)
3588 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3589 "valueize, type, captures", info
->fname
);
3590 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3591 if (s
->for_subst_vec
[i
].first
->used
)
3592 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3593 fprintf (f
, "))\n");
3594 fprintf_indent (f
, indent
, " return true;\n");
3598 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3600 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3601 fprintf (f
, ", _p%d", i
);
3602 fprintf (f
, ", captures");
3603 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3605 if (s
->for_subst_vec
[i
].first
->used
)
3606 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3608 fprintf (f
, ");\n");
3609 fprintf_indent (f
, indent
, "if (res) return res;\n");
3614 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3616 if (! s
->for_subst_vec
[i
].first
->used
)
3618 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3619 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3620 s
->for_subst_vec
[i
].first
->id
,
3621 s
->for_subst_vec
[i
].second
->id
);
3622 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3623 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3624 s
->for_subst_vec
[i
].first
->id
,
3625 s
->for_subst_vec
[i
].second
->id
);
3629 gen_1 (f
, indent
, gimple
, s
->result
);
3633 fprintf_indent (f
, indent
, "}\n");
3637 /* Hash function for finding equivalent transforms. */
3640 sinfo_hashmap_traits::hash (const key_type
&v
)
3642 /* Only bother to compare those originating from the same source pattern. */
3643 return v
->s
->result
->location
;
3646 /* Compare function for finding equivalent transforms. */
3649 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3651 if (o1
->type
!= o2
->type
)
3656 case operand::OP_IF
:
3658 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3659 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3660 /* ??? Properly compare c-exprs. */
3661 if (if1
->cond
!= if2
->cond
)
3663 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3665 if (if1
->falseexpr
!= if2
->falseexpr
3667 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3671 case operand::OP_WITH
:
3673 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3674 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3675 if (with1
->with
!= with2
->with
)
3677 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3682 /* We've hit a result. Time to compare capture-infos - this is required
3683 in addition to the conservative pointer-equivalency of the result IL. */
3684 capture_info
cinfo1 (s1
, o1
, true);
3685 capture_info
cinfo2 (s2
, o2
, true);
3687 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3688 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3691 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3693 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3694 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3695 || (cinfo1
.info
[i
].force_no_side_effects_p
3696 != cinfo2
.info
[i
].force_no_side_effects_p
)
3697 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3698 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3699 /* toplevel_msk is an optimization */
3700 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3701 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3702 /* the pointer back to the capture is for diagnostics only */)
3706 /* ??? Deep-compare the actual result. */
3711 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3712 const key_type
&candidate
)
3714 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3718 /* Main entry to generate code for matching GIMPLE IL off the decision
3722 decision_tree::gen (FILE *f
, bool gimple
)
3728 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3729 "a total number of %u nodes\n",
3730 gimple
? "GIMPLE" : "GENERIC",
3731 root
->num_leafs
, root
->max_level
, root
->total_size
);
3733 /* First split out the transform part of equal leafs. */
3736 for (sinfo_map_t::iterator iter
= si
.begin ();
3737 iter
!= si
.end (); ++iter
)
3739 sinfo
*s
= (*iter
).second
;
3740 /* Do not split out single uses. */
3747 fprintf (stderr
, "found %u uses of", s
->cnt
);
3748 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3751 /* Generate a split out function with the leaf transform code. */
3752 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3755 fprintf (f
, "\nstatic bool\n"
3756 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3757 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3758 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3763 fprintf (f
, "\nstatic tree\n"
3764 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3765 (*iter
).second
->fname
);
3766 for (unsigned i
= 0;
3767 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3768 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3769 fprintf (f
, " tree *captures\n");
3771 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3773 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3775 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3776 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3777 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3778 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3779 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3780 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3783 fprintf (f
, ")\n{\n");
3784 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3786 fprintf (f
, " return false;\n");
3788 fprintf (f
, " return NULL_TREE;\n");
3791 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3793 for (unsigned n
= 1; n
<= 5; ++n
)
3795 /* First generate split-out functions. */
3796 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3798 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3799 expr
*e
= static_cast<expr
*>(dop
->op
);
3800 if (e
->ops
.length () != n
3801 /* Builtin simplifications are somewhat premature on
3802 GENERIC. The following drops patterns with outermost
3803 calls. It's easy to emit overloads for function code
3804 though if necessary. */
3806 && e
->operation
->kind
!= id_base::CODE
))
3810 fprintf (f
, "\nstatic bool\n"
3811 "gimple_simplify_%s (gimple_match_op *res_op,"
3812 " gimple_seq *seq,\n"
3813 " tree (*valueize)(tree) "
3814 "ATTRIBUTE_UNUSED,\n"
3815 " code_helper ARG_UNUSED (code), tree "
3816 "ARG_UNUSED (type)\n",
3819 fprintf (f
, "\nstatic tree\n"
3820 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3821 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3823 for (unsigned i
= 0; i
< n
; ++i
)
3824 fprintf (f
, ", tree _p%d", i
);
3827 dop
->gen_kids (f
, 2, gimple
, 0);
3829 fprintf (f
, " return false;\n");
3831 fprintf (f
, " return NULL_TREE;\n");
3835 /* Then generate the main entry with the outermost switch and
3836 tail-calls to the split-out functions. */
3838 fprintf (f
, "\nstatic bool\n"
3839 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3840 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3841 " code_helper code, const tree type");
3843 fprintf (f
, "\ntree\n"
3844 "generic_simplify (location_t loc, enum tree_code code, "
3845 "const tree type ATTRIBUTE_UNUSED");
3846 for (unsigned i
= 0; i
< n
; ++i
)
3847 fprintf (f
, ", tree _p%d", i
);
3852 fprintf (f
, " switch (code.get_rep())\n"
3855 fprintf (f
, " switch (code)\n"
3857 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3859 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3860 expr
*e
= static_cast<expr
*>(dop
->op
);
3861 if (e
->ops
.length () != n
3862 /* Builtin simplifications are somewhat premature on
3863 GENERIC. The following drops patterns with outermost
3864 calls. It's easy to emit overloads for function code
3865 though if necessary. */
3867 && e
->operation
->kind
!= id_base::CODE
))
3870 if (*e
->operation
== CONVERT_EXPR
3871 || *e
->operation
== NOP_EXPR
)
3872 fprintf (f
, " CASE_CONVERT:\n");
3874 fprintf (f
, " case %s%s:\n",
3875 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3878 fprintf (f
, " return gimple_simplify_%s (res_op, "
3879 "seq, valueize, code, type", e
->operation
->id
);
3881 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3883 for (unsigned j
= 0; j
< n
; ++j
)
3884 fprintf (f
, ", _p%d", j
);
3885 fprintf (f
, ");\n");
3887 fprintf (f
, " default:;\n"
3891 fprintf (f
, " return false;\n");
3893 fprintf (f
, " return NULL_TREE;\n");
3898 /* Output code to implement the predicate P from the decision tree DT. */
3901 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3903 fprintf (f
, "\nbool\n"
3904 "%s%s (tree t%s%s)\n"
3905 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3906 p
->nargs
> 0 ? ", tree *res_ops" : "",
3907 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3908 /* Conveniently make 'type' available. */
3909 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3912 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3913 dt
.root
->gen_kids (f
, 2, gimple
, 0);
3915 fprintf_indent (f
, 2, "return false;\n"
3919 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3922 write_header (FILE *f
, const char *head
)
3924 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3925 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3927 /* Include the header instead of writing it awkwardly quoted here. */
3928 fprintf (f
, "\n#include \"%s\"\n", head
);
3938 parser (cpp_reader
*);
3941 const cpp_token
*next ();
3942 const cpp_token
*peek (unsigned = 1);
3943 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3944 const cpp_token
*expect (enum cpp_ttype
);
3945 const cpp_token
*eat_token (enum cpp_ttype
);
3946 const char *get_string ();
3947 const char *get_ident ();
3948 const cpp_token
*eat_ident (const char *);
3949 const char *get_number ();
3951 unsigned get_internal_capture_id ();
3953 id_base
*parse_operation (unsigned char &);
3954 operand
*parse_capture (operand
*, bool);
3955 operand
*parse_expr ();
3956 c_expr
*parse_c_expr (cpp_ttype
);
3957 operand
*parse_op ();
3959 void record_operlist (location_t
, user_id
*);
3961 void parse_pattern ();
3962 operand
*parse_result (operand
*, predicate_id
*);
3963 void push_simplify (simplify::simplify_kind
,
3964 vec
<simplify
*>&, operand
*, operand
*);
3965 void parse_simplify (simplify::simplify_kind
,
3966 vec
<simplify
*>&, predicate_id
*, operand
*);
3967 void parse_for (location_t
);
3968 void parse_if (location_t
);
3969 void parse_predicates (location_t
);
3970 void parse_operator_list (location_t
);
3972 void finish_match_operand (operand
*);
3975 vec
<c_expr
*> active_ifs
;
3976 vec
<vec
<user_id
*> > active_fors
;
3977 hash_set
<user_id
*> *oper_lists_set
;
3978 vec
<user_id
*> oper_lists
;
3980 cid_map_t
*capture_ids
;
3984 vec
<simplify
*> simplifiers
;
3985 vec
<predicate_id
*> user_predicates
;
3986 bool parsing_match_operand
;
3989 /* Lexing helpers. */
3991 /* Read the next non-whitespace token from R. */
3996 const cpp_token
*token
;
3999 token
= cpp_get_token (r
);
4001 while (token
->type
== CPP_PADDING
);
4005 /* Peek at the next non-whitespace token from R. */
4008 parser::peek (unsigned num
)
4010 const cpp_token
*token
;
4014 token
= cpp_peek_token (r
, i
++);
4016 while (token
->type
== CPP_PADDING
4018 /* If we peek at EOF this is a fatal error as it leaves the
4019 cpp_reader in unusable state. Assume we really wanted a
4020 token and thus this EOF is unexpected. */
4021 if (token
->type
== CPP_EOF
)
4022 fatal_at (token
, "unexpected end of file");
4026 /* Peek at the next identifier token (or return NULL if the next
4027 token is not an identifier or equal to ID if supplied). */
4030 parser::peek_ident (const char *id
, unsigned num
)
4032 const cpp_token
*token
= peek (num
);
4033 if (token
->type
!= CPP_NAME
)
4039 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4040 if (strcmp (id
, t
) == 0)
4046 /* Read the next token from R and assert it is of type TK. */
4049 parser::expect (enum cpp_ttype tk
)
4051 const cpp_token
*token
= next ();
4052 if (token
->type
!= tk
)
4053 fatal_at (token
, "expected %s, got %s",
4054 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4059 /* Consume the next token from R and assert it is of type TK. */
4062 parser::eat_token (enum cpp_ttype tk
)
4067 /* Read the next token from R and assert it is of type CPP_STRING and
4068 return its value. */
4071 parser::get_string ()
4073 const cpp_token
*token
= expect (CPP_STRING
);
4074 return (const char *)token
->val
.str
.text
;
4077 /* Read the next token from R and assert it is of type CPP_NAME and
4078 return its value. */
4081 parser::get_ident ()
4083 const cpp_token
*token
= expect (CPP_NAME
);
4084 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4087 /* Eat an identifier token with value S from R. */
4090 parser::eat_ident (const char *s
)
4092 const cpp_token
*token
= peek ();
4093 const char *t
= get_ident ();
4094 if (strcmp (s
, t
) != 0)
4095 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4099 /* Read the next token from R and assert it is of type CPP_NUMBER and
4100 return its value. */
4103 parser::get_number ()
4105 const cpp_token
*token
= expect (CPP_NUMBER
);
4106 return (const char *)token
->val
.str
.text
;
4109 /* Return a capture ID that can be used internally. */
4112 parser::get_internal_capture_id ()
4114 unsigned newid
= capture_ids
->elements ();
4115 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4118 snprintf (id
, sizeof (id
), "__%u", newid
);
4119 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4121 fatal ("reserved capture id '%s' already used", id
);
4125 /* Record an operator-list use for transparent for handling. */
4128 parser::record_operlist (location_t loc
, user_id
*p
)
4130 if (!oper_lists_set
->add (p
))
4132 if (!oper_lists
.is_empty ()
4133 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4134 fatal_at (loc
, "User-defined operator list does not have the "
4135 "same number of entries as others used in the pattern");
4136 oper_lists
.safe_push (p
);
4140 /* Parse the operator ID, special-casing convert?, convert1? and
4144 parser::parse_operation (unsigned char &opt_grp
)
4146 const cpp_token
*id_tok
= peek ();
4147 char *alt_id
= NULL
;
4148 const char *id
= get_ident ();
4149 const cpp_token
*token
= peek ();
4151 if (token
->type
== CPP_QUERY
4152 && !(token
->flags
& PREV_WHITE
))
4154 if (!parsing_match_operand
)
4155 fatal_at (id_tok
, "conditional convert can only be used in "
4156 "match expression");
4157 if (ISDIGIT (id
[strlen (id
) - 1]))
4159 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4160 alt_id
= xstrdup (id
);
4161 alt_id
[strlen (id
) - 1] = '\0';
4163 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4167 eat_token (CPP_QUERY
);
4169 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4171 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4174 user_id
*p
= dyn_cast
<user_id
*> (op
);
4175 if (p
&& p
->is_oper_list
)
4177 if (active_fors
.length() == 0)
4178 record_operlist (id_tok
->src_loc
, p
);
4180 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4186 capture = '@'<number> */
4189 parser::parse_capture (operand
*op
, bool require_existing
)
4191 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4192 const cpp_token
*token
= peek ();
4193 const char *id
= NULL
;
4194 bool value_match
= false;
4195 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4196 if (token
->type
== CPP_ATSIGN
4197 && ! (token
->flags
& PREV_WHITE
)
4198 && parsing_match_operand
)
4200 eat_token (CPP_ATSIGN
);
4204 if (token
->type
== CPP_NUMBER
)
4206 else if (token
->type
== CPP_NAME
)
4209 fatal_at (token
, "expected number or identifier");
4210 unsigned next_id
= capture_ids
->elements ();
4212 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4215 if (require_existing
)
4216 fatal_at (src_loc
, "unknown capture id");
4219 return new capture (src_loc
, num
, op
, value_match
);
4222 /* Parse an expression
4223 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4226 parser::parse_expr ()
4228 const cpp_token
*token
= peek ();
4229 unsigned char opt_grp
;
4230 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4233 bool is_commutative
= false;
4234 bool force_capture
= false;
4235 const char *expr_type
= NULL
;
4237 if (token
->type
== CPP_COLON
4238 && !(token
->flags
& PREV_WHITE
))
4240 eat_token (CPP_COLON
);
4242 if (token
->type
== CPP_NAME
4243 && !(token
->flags
& PREV_WHITE
))
4245 const char *s
= get_ident ();
4246 if (!parsing_match_operand
)
4256 = dyn_cast
<operator_id
*> (e
->operation
))
4258 if (!commutative_tree_code (o
->code
)
4259 && !comparison_code_p (o
->code
))
4260 fatal_at (token
, "operation is not commutative");
4262 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4263 for (unsigned i
= 0;
4264 i
< p
->substitutes
.length (); ++i
)
4267 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4269 if (!commutative_tree_code (q
->code
)
4270 && !comparison_code_p (q
->code
))
4271 fatal_at (token
, "operation %s is not "
4272 "commutative", q
->id
);
4275 is_commutative
= true;
4277 else if (*sp
== 'C')
4278 is_commutative
= true;
4279 else if (*sp
== 's')
4281 e
->force_single_use
= true;
4282 force_capture
= true;
4285 fatal_at (token
, "flag %c not recognized", *sp
);
4292 fatal_at (token
, "expected flag or type specifying identifier");
4295 if (token
->type
== CPP_ATSIGN
4296 && !(token
->flags
& PREV_WHITE
))
4297 op
= parse_capture (e
, false);
4298 else if (force_capture
)
4300 unsigned num
= get_internal_capture_id ();
4301 op
= new capture (token
->src_loc
, num
, e
, false);
4308 if (token
->type
== CPP_CLOSE_PAREN
)
4310 if (e
->operation
->nargs
!= -1
4311 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4312 fatal_at (token
, "'%s' expects %u operands, not %u",
4313 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4316 if (e
->ops
.length () == 2
4317 || commutative_op (e
->operation
) >= 0)
4318 e
->is_commutative
= true;
4320 fatal_at (token
, "only binary operators or functions with "
4321 "two arguments can be marked commutative, "
4322 "unless the operation is known to be inherently "
4325 e
->expr_type
= expr_type
;
4328 if (e
->ops
.length () != 1)
4329 fatal_at (token
, "only unary operations can be conditional");
4330 e
->opt_grp
= opt_grp
;
4334 else if (!(token
->flags
& PREV_WHITE
))
4335 fatal_at (token
, "expected expression operand");
4337 e
->append_op (parse_op ());
4342 /* Lex native C code delimited by START recording the preprocessing tokens
4343 for later processing.
4344 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4347 parser::parse_c_expr (cpp_ttype start
)
4349 const cpp_token
*token
;
4352 vec
<cpp_token
> code
= vNULL
;
4353 unsigned nr_stmts
= 0;
4354 location_t loc
= eat_token (start
)->src_loc
;
4355 if (start
== CPP_OPEN_PAREN
)
4356 end
= CPP_CLOSE_PAREN
;
4357 else if (start
== CPP_OPEN_BRACE
)
4358 end
= CPP_CLOSE_BRACE
;
4366 /* Count brace pairs to find the end of the expr to match. */
4367 if (token
->type
== start
)
4369 else if (token
->type
== end
4372 else if (token
->type
== CPP_EOF
)
4373 fatal_at (token
, "unexpected end of file");
4375 /* This is a lame way of counting the number of statements. */
4376 if (token
->type
== CPP_SEMICOLON
)
4379 /* If this is possibly a user-defined identifier mark it used. */
4380 if (token
->type
== CPP_NAME
)
4382 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4383 (token
->val
.node
.node
)->ident
.str
);
4385 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4386 record_operlist (token
->src_loc
, p
);
4389 /* Record the token. */
4390 code
.safe_push (*token
);
4393 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4396 /* Parse an operand which is either an expression, a predicate or
4397 a standalone capture.
4398 op = predicate | expr | c_expr | capture */
4403 const cpp_token
*token
= peek ();
4404 class operand
*op
= NULL
;
4405 if (token
->type
== CPP_OPEN_PAREN
)
4407 eat_token (CPP_OPEN_PAREN
);
4409 eat_token (CPP_CLOSE_PAREN
);
4411 else if (token
->type
== CPP_OPEN_BRACE
)
4413 op
= parse_c_expr (CPP_OPEN_BRACE
);
4417 /* Remaining ops are either empty or predicates */
4418 if (token
->type
== CPP_NAME
)
4420 const char *id
= get_ident ();
4421 id_base
*opr
= get_operator (id
);
4423 fatal_at (token
, "expected predicate name");
4424 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4426 if (code1
->nargs
!= 0)
4427 fatal_at (token
, "using an operator with operands as predicate");
4428 /* Parse the zero-operand operator "predicates" as
4430 op
= new expr (opr
, token
->src_loc
);
4432 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4434 if (code2
->nargs
!= 0)
4435 fatal_at (token
, "using an operator with operands as predicate");
4436 /* Parse the zero-operand operator "predicates" as
4438 op
= new expr (opr
, token
->src_loc
);
4440 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4441 op
= new predicate (p
, token
->src_loc
);
4443 fatal_at (token
, "using an unsupported operator as predicate");
4444 if (!parsing_match_operand
)
4445 fatal_at (token
, "predicates are only allowed in match expression");
4447 if (token
->flags
& PREV_WHITE
)
4450 else if (token
->type
!= CPP_COLON
4451 && token
->type
!= CPP_ATSIGN
)
4452 fatal_at (token
, "expected expression or predicate");
4453 /* optionally followed by a capture and a predicate. */
4454 if (token
->type
== CPP_COLON
)
4455 fatal_at (token
, "not implemented: predicate on leaf operand");
4456 if (token
->type
== CPP_ATSIGN
)
4457 op
= parse_capture (op
, !parsing_match_operand
);
4463 /* Create a new simplify from the current parsing state and MATCH,
4464 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4467 parser::push_simplify (simplify::simplify_kind kind
,
4468 vec
<simplify
*>& simplifiers
,
4469 operand
*match
, operand
*result
)
4471 /* Build and push a temporary for operator list uses in expressions. */
4472 if (!oper_lists
.is_empty ())
4473 active_fors
.safe_push (oper_lists
);
4475 simplifiers
.safe_push
4476 (new simplify (kind
, last_id
++, match
, result
,
4477 active_fors
.copy (), capture_ids
));
4479 if (!oper_lists
.is_empty ())
4484 <result-op> = <op> | <if> | <with>
4485 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4486 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4490 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4492 const cpp_token
*token
= peek ();
4493 if (token
->type
!= CPP_OPEN_PAREN
)
4496 eat_token (CPP_OPEN_PAREN
);
4497 if (peek_ident ("if"))
4500 if_expr
*ife
= new if_expr (token
->src_loc
);
4501 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4502 if (peek ()->type
== CPP_OPEN_PAREN
)
4504 ife
->trueexpr
= parse_result (result
, matcher
);
4505 if (peek ()->type
== CPP_OPEN_PAREN
)
4506 ife
->falseexpr
= parse_result (result
, matcher
);
4507 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4508 ife
->falseexpr
= parse_op ();
4510 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4512 ife
->trueexpr
= parse_op ();
4513 if (peek ()->type
== CPP_OPEN_PAREN
)
4514 ife
->falseexpr
= parse_result (result
, matcher
);
4515 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4516 ife
->falseexpr
= parse_op ();
4518 /* If this if is immediately closed then it contains a
4519 manual matcher or is part of a predicate definition. */
4520 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4523 fatal_at (peek (), "manual transform not implemented");
4524 ife
->trueexpr
= result
;
4526 eat_token (CPP_CLOSE_PAREN
);
4529 else if (peek_ident ("with"))
4532 with_expr
*withe
= new with_expr (token
->src_loc
);
4533 /* Parse (with c-expr expr) as (if-with (true) expr). */
4534 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4535 withe
->with
->nr_stmts
= 0;
4536 withe
->subexpr
= parse_result (result
, matcher
);
4537 eat_token (CPP_CLOSE_PAREN
);
4540 else if (peek_ident ("switch"))
4542 token
= eat_ident ("switch");
4543 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4545 if_expr
*ife
= new if_expr (ifloc
);
4547 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4548 if (peek ()->type
== CPP_OPEN_PAREN
)
4549 ife
->trueexpr
= parse_result (result
, matcher
);
4551 ife
->trueexpr
= parse_op ();
4552 eat_token (CPP_CLOSE_PAREN
);
4553 if (peek ()->type
!= CPP_OPEN_PAREN
4554 || !peek_ident ("if", 2))
4555 fatal_at (token
, "switch can be implemented with a single if");
4556 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4558 if (peek ()->type
== CPP_OPEN_PAREN
)
4560 if (peek_ident ("if", 2))
4562 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4564 ife
->falseexpr
= new if_expr (ifloc
);
4565 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4566 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4567 if (peek ()->type
== CPP_OPEN_PAREN
)
4568 ife
->trueexpr
= parse_result (result
, matcher
);
4570 ife
->trueexpr
= parse_op ();
4571 eat_token (CPP_CLOSE_PAREN
);
4575 /* switch default clause */
4576 ife
->falseexpr
= parse_result (result
, matcher
);
4577 eat_token (CPP_CLOSE_PAREN
);
4583 /* switch default clause */
4584 ife
->falseexpr
= parse_op ();
4585 eat_token (CPP_CLOSE_PAREN
);
4589 eat_token (CPP_CLOSE_PAREN
);
4594 operand
*op
= result
;
4597 eat_token (CPP_CLOSE_PAREN
);
4603 simplify = 'simplify' <expr> <result-op>
4605 match = 'match' <ident> <expr> [<result-op>]
4606 and fill SIMPLIFIERS with the results. */
4609 parser::parse_simplify (simplify::simplify_kind kind
,
4610 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4613 /* Reset the capture map. */
4615 capture_ids
= new cid_map_t
;
4616 /* Reset oper_lists and set. */
4617 hash_set
<user_id
*> olist
;
4618 oper_lists_set
= &olist
;
4621 const cpp_token
*loc
= peek ();
4622 parsing_match_operand
= true;
4623 class operand
*match
= parse_op ();
4624 finish_match_operand (match
);
4625 parsing_match_operand
= false;
4626 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4627 fatal_at (loc
, "outermost expression cannot be captured");
4628 if (match
->type
== operand::OP_EXPR
4629 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4630 fatal_at (loc
, "outermost expression cannot be a predicate");
4632 /* Splice active_ifs onto result and continue parsing the
4634 if_expr
*active_if
= NULL
;
4635 for (int i
= active_ifs
.length (); i
> 0; --i
)
4637 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4638 ifc
->cond
= active_ifs
[i
-1];
4639 ifc
->trueexpr
= active_if
;
4642 if_expr
*outermost_if
= active_if
;
4643 while (active_if
&& active_if
->trueexpr
)
4644 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4646 const cpp_token
*token
= peek ();
4648 /* If this if is immediately closed then it is part of a predicate
4649 definition. Push it. */
4650 if (token
->type
== CPP_CLOSE_PAREN
)
4653 fatal_at (token
, "expected transform expression");
4656 active_if
->trueexpr
= result
;
4657 result
= outermost_if
;
4659 push_simplify (kind
, simplifiers
, match
, result
);
4663 operand
*tem
= parse_result (result
, matcher
);
4666 active_if
->trueexpr
= tem
;
4667 result
= outermost_if
;
4672 push_simplify (kind
, simplifiers
, match
, result
);
4675 /* Parsing of the outer control structures. */
4677 /* Parse a for expression
4678 for = '(' 'for' <subst>... <pattern> ')'
4679 subst = <ident> '(' <ident>... ')' */
4682 parser::parse_for (location_t
)
4684 auto_vec
<const cpp_token
*> user_id_tokens
;
4685 vec
<user_id
*> user_ids
= vNULL
;
4686 const cpp_token
*token
;
4687 unsigned min_n_opers
= 0, max_n_opers
= 0;
4692 if (token
->type
!= CPP_NAME
)
4695 /* Insert the user defined operators into the operator hash. */
4696 const char *id
= get_ident ();
4697 if (get_operator (id
, true) != NULL
)
4698 fatal_at (token
, "operator already defined");
4699 user_id
*op
= new user_id (id
);
4700 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4702 user_ids
.safe_push (op
);
4703 user_id_tokens
.safe_push (token
);
4705 eat_token (CPP_OPEN_PAREN
);
4708 while ((token
= peek_ident ()) != 0)
4710 const char *oper
= get_ident ();
4711 id_base
*idb
= get_operator (oper
, true);
4713 fatal_at (token
, "no such operator '%s'", oper
);
4717 else if (idb
->nargs
== -1)
4719 else if (idb
->nargs
!= arity
)
4720 fatal_at (token
, "operator '%s' with arity %d does not match "
4721 "others with arity %d", oper
, idb
->nargs
, arity
);
4723 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4726 if (p
->is_oper_list
)
4727 op
->substitutes
.safe_splice (p
->substitutes
);
4729 fatal_at (token
, "iterator cannot be used as operator-list");
4732 op
->substitutes
.safe_push (idb
);
4735 token
= expect (CPP_CLOSE_PAREN
);
4737 unsigned nsubstitutes
= op
->substitutes
.length ();
4738 if (nsubstitutes
== 0)
4739 fatal_at (token
, "A user-defined operator must have at least "
4740 "one substitution");
4741 if (max_n_opers
== 0)
4743 min_n_opers
= nsubstitutes
;
4744 max_n_opers
= nsubstitutes
;
4748 if (nsubstitutes
% min_n_opers
!= 0
4749 && min_n_opers
% nsubstitutes
!= 0)
4750 fatal_at (token
, "All user-defined identifiers must have a "
4751 "multiple number of operator substitutions of the "
4752 "smallest number of substitutions");
4753 if (nsubstitutes
< min_n_opers
)
4754 min_n_opers
= nsubstitutes
;
4755 else if (nsubstitutes
> max_n_opers
)
4756 max_n_opers
= nsubstitutes
;
4760 unsigned n_ids
= user_ids
.length ();
4762 fatal_at (token
, "for requires at least one user-defined identifier");
4765 if (token
->type
== CPP_CLOSE_PAREN
)
4766 fatal_at (token
, "no pattern defined in for");
4768 active_fors
.safe_push (user_ids
);
4772 if (token
->type
== CPP_CLOSE_PAREN
)
4778 /* Remove user-defined operators from the hash again. */
4779 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4781 if (!user_ids
[i
]->used
)
4782 warning_at (user_id_tokens
[i
],
4783 "operator %s defined but not used", user_ids
[i
]->id
);
4784 operators
->remove_elt (user_ids
[i
]);
4788 /* Parse an identifier associated with a list of operators.
4789 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4792 parser::parse_operator_list (location_t
)
4794 const cpp_token
*token
= peek ();
4795 const char *id
= get_ident ();
4797 if (get_operator (id
, true) != 0)
4798 fatal_at (token
, "operator %s already defined", id
);
4800 user_id
*op
= new user_id (id
, true);
4803 while ((token
= peek_ident ()) != 0)
4806 const char *oper
= get_ident ();
4807 id_base
*idb
= get_operator (oper
, true);
4810 fatal_at (token
, "no such operator '%s'", oper
);
4814 else if (idb
->nargs
== -1)
4816 else if (arity
!= idb
->nargs
)
4817 fatal_at (token
, "operator '%s' with arity %d does not match "
4818 "others with arity %d", oper
, idb
->nargs
, arity
);
4820 /* We allow composition of multiple operator lists. */
4821 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4822 op
->substitutes
.safe_splice (p
->substitutes
);
4824 op
->substitutes
.safe_push (idb
);
4827 // Check that there is no junk after id-list
4829 if (token
->type
!= CPP_CLOSE_PAREN
)
4830 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4832 if (op
->substitutes
.length () == 0)
4833 fatal_at (token
, "operator-list cannot be empty");
4836 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4840 /* Parse an outer if expression.
4841 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4844 parser::parse_if (location_t
)
4846 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4848 const cpp_token
*token
= peek ();
4849 if (token
->type
== CPP_CLOSE_PAREN
)
4850 fatal_at (token
, "no pattern defined in if");
4852 active_ifs
.safe_push (ifexpr
);
4856 if (token
->type
== CPP_CLOSE_PAREN
)
4864 /* Parse a list of predefined predicate identifiers.
4865 preds = '(' 'define_predicates' <ident>... ')' */
4868 parser::parse_predicates (location_t
)
4872 const cpp_token
*token
= peek ();
4873 if (token
->type
!= CPP_NAME
)
4876 add_predicate (get_ident ());
4881 /* Parse outer control structures.
4882 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4885 parser::parse_pattern ()
4887 /* All clauses start with '('. */
4888 eat_token (CPP_OPEN_PAREN
);
4889 const cpp_token
*token
= peek ();
4890 const char *id
= get_ident ();
4891 if (strcmp (id
, "simplify") == 0)
4893 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4896 else if (strcmp (id
, "match") == 0)
4898 bool with_args
= false;
4899 location_t e_loc
= peek ()->src_loc
;
4900 if (peek ()->type
== CPP_OPEN_PAREN
)
4902 eat_token (CPP_OPEN_PAREN
);
4905 const char *name
= get_ident ();
4906 id_base
*id1
= get_operator (name
);
4910 p
= add_predicate (name
);
4911 user_predicates
.safe_push (p
);
4913 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
4916 fatal_at (token
, "cannot add a match to a non-predicate ID");
4917 /* Parse (match <id> <arg>... (match-expr)) here. */
4921 capture_ids
= new cid_map_t
;
4922 e
= new expr (p
, e_loc
);
4923 while (peek ()->type
== CPP_ATSIGN
)
4924 e
->append_op (parse_capture (NULL
, false));
4925 eat_token (CPP_CLOSE_PAREN
);
4928 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4929 || (!e
&& p
->nargs
!= 0)))
4930 fatal_at (token
, "non-matching number of match operands");
4931 p
->nargs
= e
? e
->ops
.length () : 0;
4932 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4935 else if (strcmp (id
, "for") == 0)
4936 parse_for (token
->src_loc
);
4937 else if (strcmp (id
, "if") == 0)
4938 parse_if (token
->src_loc
);
4939 else if (strcmp (id
, "define_predicates") == 0)
4941 if (active_ifs
.length () > 0
4942 || active_fors
.length () > 0)
4943 fatal_at (token
, "define_predicates inside if or for is not supported");
4944 parse_predicates (token
->src_loc
);
4946 else if (strcmp (id
, "define_operator_list") == 0)
4948 if (active_ifs
.length () > 0
4949 || active_fors
.length () > 0)
4950 fatal_at (token
, "operator-list inside if or for is not supported");
4951 parse_operator_list (token
->src_loc
);
4954 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4955 active_ifs
.length () == 0 && active_fors
.length () == 0
4956 ? "'define_predicates', " : "");
4958 eat_token (CPP_CLOSE_PAREN
);
4961 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4965 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4970 if (capture
*c
= dyn_cast
<capture
*> (op
))
4972 cpts
[c
->where
].safe_push (c
);
4973 walk_captures (c
->what
, cpts
);
4975 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4976 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4977 walk_captures (e
->ops
[i
], cpts
);
4980 /* Finish up OP which is a match operand. */
4983 parser::finish_match_operand (operand
*op
)
4985 /* Look for matching captures, diagnose mis-uses of @@ and apply
4986 early lowering and distribution of value_match. */
4987 auto_vec
<vec
<capture
*> > cpts
;
4988 cpts
.safe_grow_cleared (capture_ids
->elements ());
4989 walk_captures (op
, cpts
);
4990 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4992 capture
*value_match
= NULL
;
4993 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4995 if (cpts
[i
][j
]->value_match
)
4998 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4999 value_match
= cpts
[i
][j
];
5002 if (cpts
[i
].length () == 1 && value_match
)
5003 fatal_at (value_match
->location
, "@@ without a matching capture");
5006 /* Duplicate prevailing capture with the existing ID, create
5007 a fake ID and rewrite all captures to use it. This turns
5008 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5009 value_match
->what
= new capture (value_match
->location
,
5011 value_match
->what
, false);
5012 /* Create a fake ID and rewrite all captures to use it. */
5013 unsigned newid
= get_internal_capture_id ();
5014 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5016 cpts
[i
][j
]->where
= newid
;
5017 cpts
[i
][j
]->value_match
= true;
5024 /* Main entry of the parser. Repeatedly parse outer control structures. */
5026 parser::parser (cpp_reader
*r_
)
5030 active_fors
= vNULL
;
5031 simplifiers
= vNULL
;
5032 oper_lists_set
= NULL
;
5035 user_predicates
= vNULL
;
5036 parsing_match_operand
= false;
5039 const cpp_token
*token
= next ();
5040 while (token
->type
!= CPP_EOF
)
5042 _cpp_backup_tokens (r
, 1);
5049 /* Helper for the linemap code. */
5052 round_alloc_size (size_t s
)
5058 /* The genmatch generator progam. It reads from a pattern description
5059 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5062 main (int argc
, char **argv
)
5066 progname
= "genmatch";
5072 char *input
= argv
[argc
-1];
5073 for (int i
= 1; i
< argc
- 1; ++i
)
5075 if (strcmp (argv
[i
], "--gimple") == 0)
5077 else if (strcmp (argv
[i
], "--generic") == 0)
5079 else if (strcmp (argv
[i
], "-v") == 0)
5081 else if (strcmp (argv
[i
], "-vv") == 0)
5085 fprintf (stderr
, "Usage: genmatch "
5086 "[--gimple] [--generic] [-v[v]] input\n");
5091 line_table
= XCNEW (class line_maps
);
5092 linemap_init (line_table
, 0);
5093 line_table
->reallocator
= xrealloc
;
5094 line_table
->round_alloc_size
= round_alloc_size
;
5096 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5097 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5098 cb
->diagnostic
= diagnostic_cb
;
5100 /* Add the build directory to the #include "" search path. */
5101 cpp_dir
*dir
= XCNEW (cpp_dir
);
5102 dir
->name
= getpwd ();
5104 dir
->name
= ASTRDUP (".");
5105 cpp_set_include_chains (r
, dir
, NULL
, false);
5107 if (!cpp_read_main_file (r
, input
))
5109 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5110 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5112 null_id
= new id_base (id_base::NULL_ID
, "null");
5114 /* Pre-seed operators. */
5115 operators
= new hash_table
<id_base
> (1024);
5116 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5117 add_operator (SYM, # SYM, # TYPE, NARGS);
5118 #define END_OF_BASE_TREE_CODES
5120 #undef END_OF_BASE_TREE_CODES
5123 /* Pre-seed builtin functions.
5124 ??? Cannot use N (name) as that is targetm.emultls.get_address
5125 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5126 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5127 add_function (ENUM, "CFN_" # ENUM);
5128 #include "builtins.def"
5130 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5131 add_function (IFN_##CODE, "CFN_" #CODE);
5132 #include "internal-fn.def"
5138 write_header (stdout
, "gimple-match-head.c");
5140 write_header (stdout
, "generic-match-head.c");
5142 /* Go over all predicates defined with patterns and perform
5143 lowering and code generation. */
5144 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5146 predicate_id
*pred
= p
.user_predicates
[i
];
5147 lower (pred
->matchers
, gimple
);
5150 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5151 print_matches (pred
->matchers
[j
]);
5154 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5155 dt
.insert (pred
->matchers
[j
], j
);
5160 write_predicate (stdout
, pred
, dt
, gimple
);
5163 /* Lower the main simplifiers and generate code for them. */
5164 lower (p
.simplifiers
, gimple
);
5167 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5168 print_matches (p
.simplifiers
[i
]);
5171 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5172 dt
.insert (p
.simplifiers
[i
], i
);
5177 dt
.gen (stdout
, gimple
);
5180 cpp_finish (r
, NULL
);