1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2021 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
187 output_line_directive (FILE *f
, location_t location
,
188 bool dumpfile
= false, bool fnargs
= false)
190 const line_map_ordinary
*map
;
191 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
192 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
195 /* When writing to a dumpfile only dump the filename. */
196 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
197 #if defined(DIR_SEPARATOR_2)
198 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
199 if (pos2
&& (!file
|| (pos2
> file
)))
208 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
210 fprintf (f
, "%s:%d", file
, loc
.line
);
213 /* Other gen programs really output line directives here, at least for
214 development it's right now more convenient to have line information
215 from the generated file. Still keep the directives as comment for now
216 to easily back-point to the meta-description. */
217 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
221 /* Pull in tree codes and builtin function codes from their
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
231 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
232 enum built_in_function
{
233 #include "builtins.def"
237 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239 #include "internal-fn.def"
244 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
245 CFN_##ENUM = int (ENUM),
246 #include "builtins.def"
248 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
249 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
250 #include "internal-fn.def"
255 #include "case-cfn-macros.h"
257 /* Return true if CODE represents a commutative tree code. Otherwise
260 commutative_tree_code (enum tree_code code
)
266 case MULT_HIGHPART_EXPR
:
281 case WIDEN_MULT_EXPR
:
282 case VEC_WIDEN_MULT_HI_EXPR
:
283 case VEC_WIDEN_MULT_LO_EXPR
:
284 case VEC_WIDEN_MULT_EVEN_EXPR
:
285 case VEC_WIDEN_MULT_ODD_EXPR
:
294 /* Return true if CODE represents a ternary tree code for which the
295 first two operands are commutative. Otherwise return false. */
297 commutative_ternary_tree_code (enum tree_code code
)
301 case WIDEN_MULT_PLUS_EXPR
:
302 case WIDEN_MULT_MINUS_EXPR
:
312 /* Return true if CODE is a comparison. */
315 comparison_code_p (enum tree_code code
)
342 /* Base class for all identifiers the parser knows. */
344 class id_base
: public nofree_ptr_hash
<id_base
>
347 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
349 id_base (id_kind
, const char *, int = -1);
355 /* hash_table support. */
356 static inline hashval_t
hash (const id_base
*);
357 static inline int equal (const id_base
*, const id_base
*);
361 id_base::hash (const id_base
*op
)
367 id_base::equal (const id_base
*op1
,
370 return (op1
->hashval
== op2
->hashval
371 && strcmp (op1
->id
, op2
->id
) == 0);
374 /* The special id "null", which matches nothing. */
375 static id_base
*null_id
;
377 /* Hashtable of known pattern operators. This is pre-seeded from
378 all known tree codes and all known builtin function ids. */
379 static hash_table
<id_base
> *operators
;
381 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
386 hashval
= htab_hash_string (id
);
389 /* Identifier that maps to a tree code. */
391 class operator_id
: public id_base
394 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
396 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
401 /* Identifier that maps to a builtin or internal function code. */
403 class fn_id
: public id_base
406 fn_id (enum built_in_function fn_
, const char *id_
)
407 : id_base (id_base::FN
, id_
), fn (fn_
) {}
408 fn_id (enum internal_fn fn_
, const char *id_
)
409 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
415 /* Identifier that maps to a user-defined predicate. */
417 class predicate_id
: public id_base
420 predicate_id (const char *id_
)
421 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
422 vec
<simplify
*> matchers
;
425 /* Identifier that maps to a operator defined by a 'for' directive. */
427 class user_id
: public id_base
430 user_id (const char *id_
, bool is_oper_list_
= false)
431 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
432 used (false), is_oper_list (is_oper_list_
) {}
433 vec
<id_base
*> substitutes
;
441 is_a_helper
<fn_id
*>::test (id_base
*id
)
443 return id
->kind
== id_base::FN
;
449 is_a_helper
<operator_id
*>::test (id_base
*id
)
451 return id
->kind
== id_base::CODE
;
457 is_a_helper
<predicate_id
*>::test (id_base
*id
)
459 return id
->kind
== id_base::PREDICATE
;
465 is_a_helper
<user_id
*>::test (id_base
*id
)
467 return id
->kind
== id_base::USER
;
470 /* If ID has a pair of consecutive, commutative operands, return the
471 index of the first, otherwise return -1. */
474 commutative_op (id_base
*id
)
476 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
478 if (commutative_tree_code (code
->code
)
479 || commutative_ternary_tree_code (code
->code
))
483 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
495 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
497 int res
= commutative_op (uid
->substitutes
[0]);
500 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
501 if (res
!= commutative_op (uid
->substitutes
[i
]))
508 /* Add a predicate identifier to the hash. */
510 static predicate_id
*
511 add_predicate (const char *id
)
513 predicate_id
*p
= new predicate_id (id
);
514 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
516 fatal ("duplicate id definition");
521 /* Add a tree code identifier to the hash. */
524 add_operator (enum tree_code code
, const char *id
,
525 const char *tcc
, unsigned nargs
)
527 if (strcmp (tcc
, "tcc_unary") != 0
528 && strcmp (tcc
, "tcc_binary") != 0
529 && strcmp (tcc
, "tcc_comparison") != 0
530 && strcmp (tcc
, "tcc_expression") != 0
531 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
532 && strcmp (tcc
, "tcc_reference") != 0
533 /* To have INTEGER_CST and friends as "predicate operators". */
534 && strcmp (tcc
, "tcc_constant") != 0
535 /* And allow CONSTRUCTOR for vector initializers. */
536 && !(code
== CONSTRUCTOR
)
537 /* Allow SSA_NAME as predicate operator. */
538 && !(code
== SSA_NAME
))
540 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
541 if (code
== ADDR_EXPR
)
543 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
544 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
546 fatal ("duplicate id definition");
550 /* Add a built-in or internal function identifier to the hash. ID is
551 the name of its CFN_* enumeration value. */
553 template <typename T
>
555 add_function (T code
, const char *id
)
557 fn_id
*fn
= new fn_id (code
, id
);
558 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
560 fatal ("duplicate id definition");
564 /* Helper for easy comparing ID with tree code CODE. */
567 operator==(id_base
&id
, enum tree_code code
)
569 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
570 return oid
->code
== code
;
574 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
577 get_operator (const char *id
, bool allow_null
= false)
579 if (allow_null
&& strcmp (id
, "null") == 0)
582 id_base
tem (id_base::CODE
, id
);
584 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
587 /* If this is a user-defined identifier track whether it was used. */
588 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
594 bool all_upper
= true;
595 bool all_lower
= true;
596 for (unsigned int i
= 0; id
[i
]; ++i
)
599 else if (ISLOWER (id
[i
]))
603 /* Try in caps with _EXPR appended. */
604 id2
= ACONCAT ((id
, "_EXPR", NULL
));
605 for (unsigned int i
= 0; id2
[i
]; ++i
)
606 id2
[i
] = TOUPPER (id2
[i
]);
608 else if (all_upper
&& startswith (id
, "IFN_"))
609 /* Try CFN_ instead of IFN_. */
610 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
611 else if (all_upper
&& startswith (id
, "BUILT_IN_"))
612 /* Try prepending CFN_. */
613 id2
= ACONCAT (("CFN_", id
, NULL
));
617 new (&tem
) id_base (id_base::CODE
, id2
);
618 return operators
->find_with_hash (&tem
, tem
.hashval
);
621 /* Return the comparison operators that results if the operands are
622 swapped. This is safe for floating-point. */
625 swap_tree_comparison (operator_id
*p
)
637 return get_operator ("LT_EXPR");
639 return get_operator ("LE_EXPR");
641 return get_operator ("GT_EXPR");
643 return get_operator ("GE_EXPR");
645 return get_operator ("UNLT_EXPR");
647 return get_operator ("UNLE_EXPR");
649 return get_operator ("UNGT_EXPR");
651 return get_operator ("UNGE_EXPR");
657 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
660 /* The AST produced by parsing of the pattern definitions. */
665 /* The base class for operands. */
669 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
670 operand (enum op_type type_
, location_t loc_
)
671 : type (type_
), location (loc_
) {}
674 virtual void gen_transform (FILE *, int, const char *, bool, int,
675 const char *, capture_info
*,
678 { gcc_unreachable (); }
681 /* A predicate operand. Predicates are leafs in the AST. */
683 class predicate
: public operand
686 predicate (predicate_id
*p_
, location_t loc
)
687 : operand (OP_PREDICATE
, loc
), p (p_
) {}
691 /* An operand that constitutes an expression. Expressions include
692 function calls and user-defined predicate invocations. */
694 class expr
: public operand
697 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
698 : operand (OP_EXPR
, loc
), operation (operation_
),
699 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
700 is_generic (false), force_single_use (false), force_leaf (false),
703 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
704 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
705 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
),
706 force_leaf (e
->force_leaf
), opt_grp (e
->opt_grp
) {}
707 void append_op (operand
*op
) { ops
.safe_push (op
); }
708 /* The operator and its operands. */
711 /* An explicitely specified type - used exclusively for conversions. */
712 const char *expr_type
;
713 /* Whether the operation is to be applied commutatively. This is
714 later lowered to two separate patterns. */
716 /* Whether the expression is expected to be in GENERIC form. */
718 /* Whether pushing any stmt to the sequence should be conditional
719 on this expression having a single-use. */
720 bool force_single_use
;
721 /* Whether in the result expression this should be a leaf node
722 with any children simplified down to simple operands. */
724 /* If non-zero, the group for optional handling. */
725 unsigned char opt_grp
;
726 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
727 const char *, capture_info
*,
728 dt_operand
** = 0, int = 0);
731 /* An operator that is represented by native C code. This is always
732 a leaf operand in the AST. This class is also used to represent
733 the code to be generated for 'if' and 'with' expressions. */
735 class c_expr
: public operand
738 /* A mapping of an identifier and its replacement. Used to apply
744 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
747 c_expr (cpp_reader
*r_
, location_t loc
,
748 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
749 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
750 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
751 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
752 /* cpplib tokens and state to transform this back to source. */
755 cid_map_t
*capture_ids
;
756 /* The number of statements parsed (well, the number of ';'s). */
758 /* The identifier replacement vector. */
760 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
761 const char *, capture_info
*,
762 dt_operand
** = 0, int = 0);
765 /* A wrapper around another operand that captures its value. */
767 class capture
: public operand
770 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
771 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
773 /* Identifier index for the value. */
775 /* Whether in a match of two operands the compare should be for
776 equal values rather than equal atoms (boils down to a type
779 /* The captured value. */
781 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
782 const char *, capture_info
*,
783 dt_operand
** = 0, int = 0);
788 class if_expr
: public operand
791 if_expr (location_t loc
)
792 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
798 /* with expression. */
800 class with_expr
: public operand
803 with_expr (location_t loc
)
804 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
812 is_a_helper
<capture
*>::test (operand
*op
)
814 return op
->type
== operand::OP_CAPTURE
;
820 is_a_helper
<predicate
*>::test (operand
*op
)
822 return op
->type
== operand::OP_PREDICATE
;
828 is_a_helper
<c_expr
*>::test (operand
*op
)
830 return op
->type
== operand::OP_C_EXPR
;
836 is_a_helper
<expr
*>::test (operand
*op
)
838 return op
->type
== operand::OP_EXPR
;
844 is_a_helper
<if_expr
*>::test (operand
*op
)
846 return op
->type
== operand::OP_IF
;
852 is_a_helper
<with_expr
*>::test (operand
*op
)
854 return op
->type
== operand::OP_WITH
;
857 /* The main class of a pattern and its transform. This is used to
858 represent both (simplify ...) and (match ...) kinds. The AST
859 duplicates all outer 'if' and 'for' expressions here so each
860 simplify can exist in isolation. */
865 enum simplify_kind
{ SIMPLIFY
, MATCH
};
867 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
868 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
869 cid_map_t
*capture_ids_
)
870 : kind (kind_
), id (id_
), match (match_
), result (result_
),
871 for_vec (for_vec_
), for_subst_vec (vNULL
),
872 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
875 /* ID. This is kept to easily associate related simplifies expanded
876 from the same original one. */
878 /* The expression that is matched against the GENERIC or GIMPLE IL. */
880 /* For a (simplify ...) an expression with ifs and withs with the expression
881 produced when the pattern applies in the leafs.
882 For a (match ...) the leafs are either empty if it is a simple predicate
883 or the single expression specifying the matched operands. */
884 class operand
*result
;
885 /* Collected 'for' expression operators that have to be replaced
886 in the lowering phase. */
887 vec
<vec
<user_id
*> > for_vec
;
888 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
889 /* A map of capture identifiers to indexes. */
890 cid_map_t
*capture_ids
;
894 /* Debugging routines for dumping the AST. */
897 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
899 if (capture
*c
= dyn_cast
<capture
*> (o
))
901 if (c
->what
&& flattened
== false)
902 print_operand (c
->what
, f
, flattened
);
903 fprintf (f
, "@%u", c
->where
);
906 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
907 fprintf (f
, "%s", p
->p
->id
);
909 else if (is_a
<c_expr
*> (o
))
910 fprintf (f
, "c_expr");
912 else if (expr
*e
= dyn_cast
<expr
*> (o
))
914 if (e
->ops
.length () == 0)
915 fprintf (f
, "%s", e
->operation
->id
);
918 fprintf (f
, "(%s", e
->operation
->id
);
920 if (flattened
== false)
922 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
925 print_operand (e
->ops
[i
], f
, flattened
);
937 print_matches (class simplify
*s
, FILE *f
= stderr
)
939 fprintf (f
, "for expression: ");
940 print_operand (s
->match
, f
);
947 /* Lowering of commutative operators. */
950 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
951 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
953 if (n
== ops_vector
.length ())
955 vec
<operand
*> xv
= v
.copy ();
956 result
.safe_push (xv
);
960 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
962 v
[n
] = ops_vector
[n
][i
];
963 cartesian_product (ops_vector
, result
, v
, n
+ 1);
967 /* Lower OP to two operands in case it is marked as commutative. */
969 static vec
<operand
*>
970 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
972 vec
<operand
*> ret
= vNULL
;
974 if (capture
*c
= dyn_cast
<capture
*> (op
))
981 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
982 for (unsigned i
= 0; i
< v
.length (); ++i
)
984 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
991 expr
*e
= dyn_cast
<expr
*> (op
);
992 if (!e
|| e
->ops
.length () == 0)
998 vec
< vec
<operand
*> > ops_vector
= vNULL
;
999 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1000 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1002 auto_vec
< vec
<operand
*> > result
;
1003 auto_vec
<operand
*> v (e
->ops
.length ());
1004 v
.quick_grow_cleared (e
->ops
.length ());
1005 cartesian_product (ops_vector
, result
, v
, 0);
1008 for (unsigned i
= 0; i
< result
.length (); ++i
)
1010 expr
*ne
= new expr (e
);
1011 ne
->is_commutative
= false;
1012 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1013 ne
->append_op (result
[i
][j
]);
1017 if (!e
->is_commutative
)
1020 /* The operation is always binary if it isn't inherently commutative. */
1021 int natural_opno
= commutative_op (e
->operation
);
1022 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1023 for (unsigned i
= 0; i
< result
.length (); ++i
)
1025 expr
*ne
= new expr (e
);
1026 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1028 if (comparison_code_p (r
->code
))
1029 ne
->operation
= swap_tree_comparison (r
);
1031 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1033 bool found_compare
= false;
1034 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1035 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1037 if (comparison_code_p (q
->code
)
1038 && swap_tree_comparison (q
) != q
)
1040 found_compare
= true;
1046 user_id
*newop
= new user_id ("<internal>");
1047 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1049 id_base
*subst
= p
->substitutes
[j
];
1050 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1052 if (comparison_code_p (q
->code
))
1053 subst
= swap_tree_comparison (q
);
1055 newop
->substitutes
.safe_push (subst
);
1057 ne
->operation
= newop
;
1058 /* Search for 'p' inside the for vector and push 'newop'
1059 to the same level. */
1060 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1061 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1062 if (for_vec
[j
][k
] == p
)
1064 for_vec
[j
].safe_push (newop
);
1070 ne
->is_commutative
= false;
1071 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1073 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1074 ne
->append_op (result
[i
][old_j
]);
1082 /* Lower operations marked as commutative in the AST of S and push
1083 the resulting patterns to SIMPLIFIERS. */
1086 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1088 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1089 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1091 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1092 s
->for_vec
, s
->capture_ids
);
1093 simplifiers
.safe_push (ns
);
1097 /* Strip conditional operations using group GRP from O and its
1098 children if STRIP, else replace them with an unconditional operation. */
1101 lower_opt (operand
*o
, unsigned char grp
, bool strip
)
1103 if (capture
*c
= dyn_cast
<capture
*> (o
))
1106 return new capture (c
->location
, c
->where
,
1107 lower_opt (c
->what
, grp
, strip
),
1113 expr
*e
= dyn_cast
<expr
*> (o
);
1117 if (e
->opt_grp
== grp
)
1120 return lower_opt (e
->ops
[0], grp
, strip
);
1122 expr
*ne
= new expr (e
);
1124 ne
->append_op (lower_opt (e
->ops
[0], grp
, strip
));
1128 expr
*ne
= new expr (e
);
1129 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1130 ne
->append_op (lower_opt (e
->ops
[i
], grp
, strip
));
1135 /* Determine whether O or its children uses the conditional operation
1139 has_opt (operand
*o
, unsigned char grp
)
1141 if (capture
*c
= dyn_cast
<capture
*> (o
))
1144 return has_opt (c
->what
, grp
);
1149 expr
*e
= dyn_cast
<expr
*> (o
);
1153 if (e
->opt_grp
== grp
)
1156 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1157 if (has_opt (e
->ops
[i
], grp
))
1163 /* Lower conditional convert operators in O, expanding it to a vector
1166 static vec
<operand
*>
1167 lower_opt (operand
*o
)
1169 vec
<operand
*> v1
= vNULL
, v2
;
1173 /* Conditional operations are lowered to a pattern with the
1174 operation and one without. All different conditional operation
1175 groups are lowered separately. */
1177 for (unsigned i
= 1; i
<= 10; ++i
)
1180 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1181 if (has_opt (v1
[j
], i
))
1183 v2
.safe_push (lower_opt (v1
[j
], i
, false));
1184 v2
.safe_push (lower_opt (v1
[j
], i
, true));
1190 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1191 v1
.safe_push (v2
[j
]);
1198 /* Lower conditional convert operators in the AST of S and push
1199 the resulting multiple patterns to SIMPLIFIERS. */
1202 lower_opt (simplify
*s
, vec
<simplify
*>& simplifiers
)
1204 vec
<operand
*> matchers
= lower_opt (s
->match
);
1205 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1207 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1208 s
->for_vec
, s
->capture_ids
);
1209 simplifiers
.safe_push (ns
);
1213 /* Lower the compare operand of COND_EXPRs to a
1214 GENERIC and a GIMPLE variant. */
1216 static vec
<operand
*>
1217 lower_cond (operand
*o
)
1219 vec
<operand
*> ro
= vNULL
;
1221 if (capture
*c
= dyn_cast
<capture
*> (o
))
1225 vec
<operand
*> lop
= vNULL
;
1226 lop
= lower_cond (c
->what
);
1228 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1229 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1235 expr
*e
= dyn_cast
<expr
*> (o
);
1236 if (!e
|| e
->ops
.length () == 0)
1242 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1243 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1244 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1246 auto_vec
< vec
<operand
*> > result
;
1247 auto_vec
<operand
*> v (e
->ops
.length ());
1248 v
.quick_grow_cleared (e
->ops
.length ());
1249 cartesian_product (ops_vector
, result
, v
, 0);
1251 for (unsigned i
= 0; i
< result
.length (); ++i
)
1253 expr
*ne
= new expr (e
);
1254 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1255 ne
->append_op (result
[i
][j
]);
1257 /* If this is a COND with a captured expression or an
1258 expression with two operands then also match a GENERIC
1259 form on the compare. */
1260 if (*e
->operation
== COND_EXPR
1261 && ((is_a
<capture
*> (e
->ops
[0])
1262 && as_a
<capture
*> (e
->ops
[0])->what
1263 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1265 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1266 || (is_a
<expr
*> (e
->ops
[0])
1267 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1270 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1271 ne
->append_op (result
[i
][j
]);
1272 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1274 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1275 expr
*cmp
= new expr (ocmp
);
1276 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1277 cmp
->append_op (ocmp
->ops
[j
]);
1278 cmp
->is_generic
= true;
1279 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1284 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1285 expr
*cmp
= new expr (ocmp
);
1286 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1287 cmp
->append_op (ocmp
->ops
[j
]);
1288 cmp
->is_generic
= true;
1298 /* Lower the compare operand of COND_EXPRs to a
1299 GENERIC and a GIMPLE variant. */
1302 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1304 vec
<operand
*> matchers
= lower_cond (s
->match
);
1305 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1307 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1308 s
->for_vec
, s
->capture_ids
);
1309 simplifiers
.safe_push (ns
);
1313 /* Return true if O refers to ID. */
1316 contains_id (operand
*o
, user_id
*id
)
1318 if (capture
*c
= dyn_cast
<capture
*> (o
))
1319 return c
->what
&& contains_id (c
->what
, id
);
1321 if (expr
*e
= dyn_cast
<expr
*> (o
))
1323 if (e
->operation
== id
)
1325 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1326 if (contains_id (e
->ops
[i
], id
))
1331 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1332 return (contains_id (w
->with
, id
)
1333 || contains_id (w
->subexpr
, id
));
1335 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1336 return (contains_id (ife
->cond
, id
)
1337 || contains_id (ife
->trueexpr
, id
)
1338 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1340 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1341 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1347 /* In AST operand O replace operator ID with operator WITH. */
1350 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1352 /* Deep-copy captures and expressions, replacing operations as
1354 if (capture
*c
= dyn_cast
<capture
*> (o
))
1358 return new capture (c
->location
, c
->where
,
1359 replace_id (c
->what
, id
, with
), c
->value_match
);
1361 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1363 expr
*ne
= new expr (e
);
1364 if (e
->operation
== id
)
1365 ne
->operation
= with
;
1366 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1367 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1370 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1372 with_expr
*nw
= new with_expr (w
->location
);
1373 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1374 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1377 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1379 if_expr
*nife
= new if_expr (ife
->location
);
1380 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1381 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1383 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1387 /* For c_expr we simply record a string replacement table which is
1388 applied at code-generation time. */
1389 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1391 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1392 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1393 return new c_expr (ce
->r
, ce
->location
,
1394 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1400 /* Return true if the binary operator OP is ok for delayed substitution
1401 during for lowering. */
1404 binary_ok (operator_id
*op
)
1411 case TRUNC_DIV_EXPR
:
1413 case FLOOR_DIV_EXPR
:
1414 case ROUND_DIV_EXPR
:
1415 case TRUNC_MOD_EXPR
:
1417 case FLOOR_MOD_EXPR
:
1418 case ROUND_MOD_EXPR
:
1420 case EXACT_DIV_EXPR
:
1432 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1435 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1437 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1438 unsigned worklist_start
= 0;
1439 auto_vec
<simplify
*> worklist
;
1440 worklist
.safe_push (sin
);
1442 /* Lower each recorded for separately, operating on the
1443 set of simplifiers created by the previous one.
1444 Lower inner-to-outer so inner for substitutes can refer
1445 to operators replaced by outer fors. */
1446 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1448 vec
<user_id
*>& ids
= for_vec
[fi
];
1449 unsigned n_ids
= ids
.length ();
1450 unsigned max_n_opers
= 0;
1451 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1452 for (unsigned i
= 0; i
< n_ids
; ++i
)
1454 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1455 max_n_opers
= ids
[i
]->substitutes
.length ();
1456 /* Require that all substitutes are of the same kind so that
1457 if we delay substitution to the result op code generation
1458 can look at the first substitute for deciding things like
1459 types of operands. */
1460 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1461 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1462 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1463 can_delay_subst
= false;
1464 else if (operator_id
*op
1465 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1468 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1469 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1470 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1472 /* Unfortunately we can't just allow all tcc_binary. */
1473 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1474 && strcmp (op0
->tcc
, "tcc_binary") == 0
1478 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1479 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1480 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1481 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1484 can_delay_subst
= false;
1486 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1489 can_delay_subst
= false;
1492 unsigned worklist_end
= worklist
.length ();
1493 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1495 simplify
*s
= worklist
[si
];
1496 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1498 operand
*match_op
= s
->match
;
1499 operand
*result_op
= s
->result
;
1500 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1502 for (unsigned i
= 0; i
< n_ids
; ++i
)
1504 user_id
*id
= ids
[i
];
1505 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1507 && (contains_id (match_op
, id
)
1508 || contains_id (result_op
, id
)))
1513 subst
.quick_push (std::make_pair (id
, oper
));
1514 match_op
= replace_id (match_op
, id
, oper
);
1516 && !can_delay_subst
)
1517 result_op
= replace_id (result_op
, id
, oper
);
1522 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1523 vNULL
, s
->capture_ids
);
1524 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1527 ns
->for_subst_vec
.safe_splice (subst
);
1529 worklist
.safe_push (ns
);
1532 worklist_start
= worklist_end
;
1535 /* Copy out the result from the last for lowering. */
1536 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1537 simplifiers
.safe_push (worklist
[i
]);
1540 /* Lower the AST for everything in SIMPLIFIERS. */
1543 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1545 auto_vec
<simplify
*> out_simplifiers
;
1546 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1547 lower_opt (simplifiers
[i
], out_simplifiers
);
1549 simplifiers
.truncate (0);
1550 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1551 lower_commutative (out_simplifiers
[i
], simplifiers
);
1553 out_simplifiers
.truncate (0);
1555 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1556 lower_cond (simplifiers
[i
], out_simplifiers
);
1558 out_simplifiers
.safe_splice (simplifiers
);
1561 simplifiers
.truncate (0);
1562 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1563 lower_for (out_simplifiers
[i
], simplifiers
);
1569 /* The decision tree built for generating GIMPLE and GENERIC pattern
1570 matching code. It represents the 'match' expression of all
1571 simplifies and has those as its leafs. */
1575 /* A hash-map collecting semantically equivalent leafs in the decision
1576 tree for splitting out to separate functions. */
1585 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1588 static inline hashval_t
hash (const key_type
&);
1589 static inline bool equal_keys (const key_type
&, const key_type
&);
1590 template <typename T
> static inline void remove (T
&) {}
1593 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1596 /* Current simplifier ID we are processing during insertion into the
1598 static unsigned current_id
;
1600 /* Decision tree base class, used for DT_NODE. */
1605 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1610 vec
<dt_node
*> kids
;
1614 unsigned total_size
;
1617 dt_node (enum dt_type type_
, dt_node
*parent_
)
1618 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1620 dt_node
*append_node (dt_node
*);
1621 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1622 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1623 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1625 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1627 virtual void gen (FILE *, int, bool, int) {}
1629 void gen_kids (FILE *, int, bool, int);
1630 void gen_kids_1 (FILE *, int, bool, int,
1631 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1632 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1634 void analyze (sinfo_map_t
&);
1637 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1639 class dt_operand
: public dt_node
1643 dt_operand
*match_dop
;
1648 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1649 dt_operand
*parent_
, unsigned pos_
)
1650 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1651 pos (pos_
), value_match (false), for_id (current_id
) {}
1653 void gen (FILE *, int, bool, int);
1654 unsigned gen_predicate (FILE *, int, const char *, bool);
1655 unsigned gen_match_op (FILE *, int, const char *, bool);
1657 unsigned gen_gimple_expr (FILE *, int, int);
1658 unsigned gen_generic_expr (FILE *, int, const char *);
1660 char *get_name (char *);
1661 void gen_opname (char *, unsigned);
1664 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1666 class dt_simplify
: public dt_node
1670 unsigned pattern_no
;
1671 dt_operand
**indexes
;
1674 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1675 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1676 indexes (indexes_
), info (NULL
) {}
1678 void gen_1 (FILE *, int, bool, operand
*);
1679 void gen (FILE *f
, int, bool, int);
1685 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1687 return (n
->type
== dt_node::DT_OPERAND
1688 || n
->type
== dt_node::DT_MATCH
1689 || n
->type
== dt_node::DT_TRUE
);
1695 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1697 return n
->type
== dt_node::DT_SIMPLIFY
;
1702 /* A container for the actual decision tree. */
1709 void insert (class simplify
*, unsigned);
1710 void gen (FILE *f
, bool gimple
);
1711 void print (FILE *f
= stderr
);
1713 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1715 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1716 unsigned pos
= 0, dt_node
*parent
= 0);
1717 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1718 static bool cmp_node (dt_node
*, dt_node
*);
1719 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1722 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1725 cmp_operand (operand
*o1
, operand
*o2
)
1727 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1730 if (o1
->type
== operand::OP_PREDICATE
)
1732 predicate
*p1
= as_a
<predicate
*>(o1
);
1733 predicate
*p2
= as_a
<predicate
*>(o2
);
1734 return p1
->p
== p2
->p
;
1736 else if (o1
->type
== operand::OP_EXPR
)
1738 expr
*e1
= static_cast<expr
*>(o1
);
1739 expr
*e2
= static_cast<expr
*>(o2
);
1740 return (e1
->operation
== e2
->operation
1741 && e1
->is_generic
== e2
->is_generic
);
1747 /* Compare two decision tree nodes N1 and N2 and return true if they
1751 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1753 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1759 if (n1
->type
== dt_node::DT_TRUE
)
1762 if (n1
->type
== dt_node::DT_OPERAND
)
1763 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1764 (as_a
<dt_operand
*> (n2
))->op
);
1765 else if (n1
->type
== dt_node::DT_MATCH
)
1766 return (((as_a
<dt_operand
*> (n1
))->match_dop
1767 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1768 && ((as_a
<dt_operand
*> (n1
))->value_match
1769 == (as_a
<dt_operand
*> (n2
))->value_match
));
1773 /* Search OPS for a decision tree node like P and return it if found. */
1776 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1778 /* We can merge adjacent DT_TRUE. */
1779 if (p
->type
== dt_node::DT_TRUE
1781 && ops
.last ()->type
== dt_node::DT_TRUE
)
1783 dt_operand
*true_node
= NULL
;
1784 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1786 /* But we can't merge across DT_TRUE nodes as they serve as
1787 pattern order barriers to make sure that patterns apply
1788 in order of appearance in case multiple matches are possible. */
1789 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1792 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1793 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1795 if (decision_tree::cmp_node (ops
[i
], p
))
1797 /* Unless we are processing the same pattern or the blocking
1798 pattern is before the one we are going to merge with. */
1800 && true_node
->for_id
!= current_id
1801 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1805 location_t p_loc
= 0;
1806 if (p
->type
== dt_node::DT_OPERAND
)
1807 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1808 location_t op_loc
= 0;
1809 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1810 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1811 location_t true_loc
= 0;
1812 true_loc
= true_node
->op
->location
;
1814 "failed to merge decision tree node");
1816 "with the following");
1817 warning_at (true_loc
,
1818 "because of the following which serves as ordering "
1829 /* Append N to the decision tree if it there is not already an existing
1833 dt_node::append_node (dt_node
*n
)
1837 kid
= decision_tree::find_node (kids
, n
);
1842 n
->level
= this->level
+ 1;
1847 /* Append OP to the decision tree. */
1850 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1852 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1853 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1854 return append_node (n
);
1857 /* Append a DT_TRUE decision tree node. */
1860 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1862 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1863 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1864 return append_node (n
);
1867 /* Append a DT_MATCH decision tree node. */
1870 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1871 dt_node
*parent
, unsigned pos
)
1873 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1874 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1875 return append_node (n
);
1878 /* Append S to the decision tree. */
1881 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1882 dt_operand
**indexes
)
1885 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1886 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1887 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1889 || s
->match
->location
!= s2
->s
->match
->location
))
1891 /* With a nested patters, it's hard to avoid these in order
1892 to keep match.pd rules relatively small. */
1893 warning_at (s
->match
->location
, "duplicate pattern");
1894 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1895 print_operand (s
->match
, stderr
);
1896 fprintf (stderr
, "\n");
1898 return append_node (n
);
1901 /* Analyze the node and its children. */
1904 dt_node::analyze (sinfo_map_t
&map
)
1910 if (type
== DT_SIMPLIFY
)
1912 /* Populate the map of equivalent simplifies. */
1913 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1915 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1930 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1932 kids
[i
]->analyze (map
);
1933 num_leafs
+= kids
[i
]->num_leafs
;
1934 total_size
+= kids
[i
]->total_size
;
1935 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1939 /* Insert O into the decision tree and return the decision tree node found
1943 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1944 unsigned pos
, dt_node
*parent
)
1946 dt_node
*q
, *elm
= 0;
1948 if (capture
*c
= dyn_cast
<capture
*> (o
))
1950 unsigned capt_index
= c
->where
;
1952 if (indexes
[capt_index
] == 0)
1955 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1958 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1961 // get to the last capture
1962 for (operand
*what
= c
->what
;
1963 what
&& is_a
<capture
*> (what
);
1964 c
= as_a
<capture
*> (what
), what
= c
->what
)
1969 unsigned cc_index
= c
->where
;
1970 dt_operand
*match_op
= indexes
[cc_index
];
1972 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1973 elm
= decision_tree::find_node (p
->kids
, &temp
);
1977 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1978 match
.value_match
= c
->value_match
;
1979 elm
= decision_tree::find_node (p
->kids
, &match
);
1984 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1985 elm
= decision_tree::find_node (p
->kids
, &temp
);
1989 gcc_assert (elm
->type
== dt_node::DT_TRUE
1990 || elm
->type
== dt_node::DT_OPERAND
1991 || elm
->type
== dt_node::DT_MATCH
);
1992 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1997 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
1998 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2000 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2005 p
= p
->append_op (o
, parent
, pos
);
2008 if (expr
*e
= dyn_cast
<expr
*>(o
))
2010 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2011 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2017 /* Insert S into the decision tree. */
2020 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2023 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2024 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2025 p
->append_simplify (s
, pattern_no
, indexes
);
2028 /* Debug functions to dump the decision tree. */
2031 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2033 if (p
->type
== dt_node::DT_NODE
)
2034 fprintf (f
, "root");
2038 for (unsigned i
= 0; i
< indent
; i
++)
2041 if (p
->type
== dt_node::DT_OPERAND
)
2043 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2044 print_operand (dop
->op
, f
, true);
2046 else if (p
->type
== dt_node::DT_TRUE
)
2047 fprintf (f
, "true");
2048 else if (p
->type
== dt_node::DT_MATCH
)
2049 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2050 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2052 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2053 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2054 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2055 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2058 if (is_a
<dt_operand
*> (p
))
2059 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2062 fprintf (stderr
, " (%p, %p), %u, %u\n",
2063 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2065 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2066 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2070 decision_tree::print (FILE *f
)
2072 return decision_tree::print_node (root
, f
);
2076 /* For GENERIC we have to take care of wrapping multiple-used
2077 expressions with side-effects in save_expr and preserve side-effects
2078 of expressions with omit_one_operand. Analyze captures in
2079 match, result and with expressions and perform early-outs
2080 on the outermost match expression operands for cases we cannot
2086 capture_info (simplify
*s
, operand
*, bool);
2087 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2088 bool walk_result (operand
*o
, bool, operand
*);
2089 void walk_c_expr (c_expr
*);
2095 bool force_no_side_effects_p
;
2096 bool force_single_use
;
2097 bool cond_expr_cond_p
;
2098 unsigned long toplevel_msk
;
2099 unsigned match_use_count
;
2100 unsigned result_use_count
;
2105 auto_vec
<cinfo
> info
;
2106 unsigned long force_no_side_effects
;
2110 /* Analyze captures in S. */
2112 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2117 if (s
->kind
== simplify::MATCH
)
2119 force_no_side_effects
= -1;
2123 force_no_side_effects
= 0;
2124 info
.safe_grow_cleared (s
->capture_max
+ 1, true);
2125 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2126 info
[i
].same_as
= i
;
2128 e
= as_a
<expr
*> (s
->match
);
2129 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2130 walk_match (e
->ops
[i
], i
,
2131 (i
!= 0 && *e
->operation
== COND_EXPR
)
2132 || *e
->operation
== TRUTH_ANDIF_EXPR
2133 || *e
->operation
== TRUTH_ORIF_EXPR
,
2134 i
== 0 && *e
->operation
== COND_EXPR
);
2136 walk_result (s
->result
, false, result
);
2139 /* Analyze captures in the match expression piece O. */
2142 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2143 bool conditional_p
, bool cond_expr_cond_p
)
2145 if (capture
*c
= dyn_cast
<capture
*> (o
))
2147 unsigned where
= c
->where
;
2148 info
[where
].match_use_count
++;
2149 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2150 info
[where
].force_no_side_effects_p
|= conditional_p
;
2151 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2156 /* Recurse to exprs and captures. */
2157 if (is_a
<capture
*> (c
->what
)
2158 || is_a
<expr
*> (c
->what
))
2159 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2160 /* We need to look past multiple captures to find a captured
2161 expression as with conditional converts two captures
2162 can be collapsed onto the same expression. Also collect
2163 what captures capture the same thing. */
2164 while (c
->what
&& is_a
<capture
*> (c
->what
))
2166 c
= as_a
<capture
*> (c
->what
);
2167 if (info
[c
->where
].same_as
!= c
->where
2168 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2169 fatal_at (c
->location
, "cannot handle this collapsed capture");
2170 info
[c
->where
].same_as
= info
[where
].same_as
;
2172 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2175 && (e
= dyn_cast
<expr
*> (c
->what
)))
2177 /* Zero-operand expression captures like ADDR_EXPR@0 are
2178 similar as predicates -- if they are not mentioned in
2179 the result we have to force them to have no side-effects. */
2180 if (e
->ops
.length () != 0)
2181 info
[where
].expr_p
= true;
2182 info
[where
].force_single_use
|= e
->force_single_use
;
2185 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2187 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2189 bool cond_p
= conditional_p
;
2190 bool expr_cond_p
= false;
2191 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2193 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2194 || *e
->operation
== TRUTH_ORIF_EXPR
)
2197 && *e
->operation
== 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 /* The current label failing the current matched pattern during
2353 static char *fail_label
;
2355 /* Code generation off the decision tree and the refered AST nodes. */
2358 is_conversion (id_base
*op
)
2360 return (*op
== CONVERT_EXPR
2362 || *op
== FLOAT_EXPR
2363 || *op
== FIX_TRUNC_EXPR
2364 || *op
== VIEW_CONVERT_EXPR
);
2367 /* Get the type to be used for generating operand POS of OP from the
2371 get_operand_type (id_base
*op
, unsigned pos
,
2372 const char *in_type
,
2373 const char *expr_type
,
2374 const char *other_oprnd_type
)
2376 /* Generally operands whose type does not match the type of the
2377 expression generated need to know their types but match and
2378 thus can fall back to 'other_oprnd_type'. */
2379 if (is_conversion (op
))
2380 return other_oprnd_type
;
2381 else if (*op
== REALPART_EXPR
2382 || *op
== IMAGPART_EXPR
)
2383 return other_oprnd_type
;
2384 else if (is_a
<operator_id
*> (op
)
2385 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2386 return other_oprnd_type
;
2387 else if (*op
== COND_EXPR
2389 return "boolean_type_node";
2390 else if (startswith (op
->id
, "CFN_COND_"))
2392 /* IFN_COND_* operands 1 and later by default have the same type
2393 as the result. The type of operand 0 needs to be specified
2395 if (pos
> 0 && expr_type
)
2397 else if (pos
> 0 && in_type
)
2404 /* Otherwise all types should match - choose one in order of
2411 return other_oprnd_type
;
2415 /* Generate transform code for an expression. */
2418 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2419 int depth
, const char *in_type
, capture_info
*cinfo
,
2420 dt_operand
**indexes
, int)
2422 id_base
*opr
= operation
;
2423 /* When we delay operator substituting during lowering of fors we
2424 make sure that for code-gen purposes the effects of each substitute
2425 are the same. Thus just look at that. */
2426 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2427 opr
= uid
->substitutes
[0];
2429 bool conversion_p
= is_conversion (opr
);
2430 const char *type
= expr_type
;
2433 /* If there was a type specification in the pattern use it. */
2435 else if (conversion_p
)
2436 /* For conversions we need to build the expression using the
2437 outer type passed in. */
2439 else if (*opr
== REALPART_EXPR
2440 || *opr
== IMAGPART_EXPR
)
2442 /* __real and __imag use the component type of its operand. */
2443 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2447 else if (is_a
<operator_id
*> (opr
)
2448 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2450 /* comparisons use boolean_type_node (or what gets in), but
2451 their operands need to figure out the types themselves. */
2456 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2461 else if (*opr
== COND_EXPR
2462 || *opr
== VEC_COND_EXPR
2463 || startswith (opr
->id
, "CFN_COND_"))
2465 /* Conditions are of the same type as their first alternative. */
2466 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2471 /* Other operations are of the same type as their first operand. */
2472 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2476 fatal_at (location
, "cannot determine type of operand");
2478 fprintf_indent (f
, indent
, "{\n");
2480 fprintf_indent (f
, indent
,
2481 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2483 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2484 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2487 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2489 = get_operand_type (opr
, i
, in_type
, expr_type
,
2490 i
== 0 ? NULL
: op0type
);
2491 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2493 *opr
== COND_EXPR
&& i
== 0 ? 1 : 2);
2496 const char *opr_name
;
2497 if (*operation
== CONVERT_EXPR
)
2498 opr_name
= "NOP_EXPR";
2500 opr_name
= operation
->id
;
2504 if (*opr
== CONVERT_EXPR
)
2506 fprintf_indent (f
, indent
,
2507 "if (%s != TREE_TYPE (_o%d[0])\n",
2509 fprintf_indent (f
, indent
,
2510 " && !useless_type_conversion_p (%s, TREE_TYPE "
2513 fprintf_indent (f
, indent
+ 2, "{\n");
2516 /* ??? Building a stmt can fail for various reasons here, seq being
2517 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2518 So if we fail here we should continue matching other patterns. */
2519 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2520 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2521 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2522 fprintf (f
, ", _o%d[%u]", depth
, i
);
2523 fprintf (f
, ");\n");
2524 fprintf_indent (f
, indent
, "tem_op.resimplify (lseq, valueize);\n");
2525 fprintf_indent (f
, indent
,
2526 "_r%d = maybe_push_res_to_seq (&tem_op, %s);\n", depth
,
2527 !force_leaf
? "lseq" : "NULL");
2528 fprintf_indent (f
, indent
,
2529 "if (!_r%d) goto %s;\n",
2531 if (*opr
== CONVERT_EXPR
)
2534 fprintf_indent (f
, indent
, " }\n");
2535 fprintf_indent (f
, indent
, "else\n");
2536 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2541 if (*opr
== CONVERT_EXPR
)
2543 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2547 if (opr
->kind
== id_base::CODE
)
2548 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2549 depth
, ops
.length(), opr_name
, type
);
2552 fprintf_indent (f
, indent
, "{\n");
2553 fprintf_indent (f
, indent
, " _r%d = maybe_build_call_expr_loc (loc, "
2554 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2556 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2557 fprintf (f
, ", _o%d[%u]", depth
, i
);
2558 fprintf (f
, ");\n");
2559 if (opr
->kind
!= id_base::CODE
)
2561 fprintf_indent (f
, indent
, " if (!_r%d)\n", depth
);
2562 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
2563 fprintf_indent (f
, indent
, "}\n");
2565 if (*opr
== CONVERT_EXPR
)
2568 fprintf_indent (f
, indent
, "else\n");
2569 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2572 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2574 fprintf_indent (f
, indent
, "}\n");
2577 /* Generate code for a c_expr which is either the expression inside
2578 an if statement or a sequence of statements which computes a
2579 result to be stored to DEST. */
2582 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2583 bool, int, const char *, capture_info
*,
2586 if (dest
&& nr_stmts
== 1)
2587 fprintf_indent (f
, indent
, "%s = ", dest
);
2589 unsigned stmt_nr
= 1;
2591 for (unsigned i
= 0; i
< code
.length (); ++i
)
2593 const cpp_token
*token
= &code
[i
];
2595 /* We can't recover from all lexing losses but we can roughly restore line
2596 breaks from location info. */
2597 const line_map_ordinary
*map
;
2598 linemap_resolve_location (line_table
, token
->src_loc
,
2599 LRK_SPELLING_LOCATION
, &map
);
2600 expanded_location loc
= linemap_expand_location (line_table
, map
,
2602 if (prev_line
!= -1 && loc
.line
!= prev_line
)
2604 prev_line
= loc
.line
;
2606 /* Replace captures for code-gen. */
2607 if (token
->type
== CPP_ATSIGN
)
2609 const cpp_token
*n
= &code
[i
+1];
2610 if ((n
->type
== CPP_NUMBER
2611 || n
->type
== CPP_NAME
)
2612 && !(n
->flags
& PREV_WHITE
))
2614 if (token
->flags
& PREV_WHITE
)
2617 if (n
->type
== CPP_NUMBER
)
2618 id
= (const char *)n
->val
.str
.text
;
2620 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2621 unsigned *cid
= capture_ids
->get (id
);
2623 fatal_at (token
, "unknown capture id");
2624 fprintf (f
, "captures[%u]", *cid
);
2630 if (token
->flags
& PREV_WHITE
)
2633 if (token
->type
== CPP_NAME
)
2635 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2637 for (j
= 0; j
< ids
.length (); ++j
)
2639 if (strcmp (id
, ids
[j
].id
) == 0)
2641 fprintf (f
, "%s", ids
[j
].oper
);
2645 if (j
< ids
.length ())
2649 /* Output the token as string. */
2650 char *tk
= (char *)cpp_token_as_text (r
, token
);
2653 if (token
->type
== CPP_SEMICOLON
)
2656 if (dest
&& stmt_nr
== nr_stmts
)
2657 fprintf_indent (f
, indent
, "%s = ", dest
);
2663 /* Generate transform code for a capture. */
2666 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2667 int depth
, const char *in_type
, capture_info
*cinfo
,
2668 dt_operand
**indexes
, int cond_handling
)
2670 if (what
&& is_a
<expr
*> (what
))
2672 if (indexes
[where
] == 0)
2675 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2676 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2681 /* If in GENERIC some capture is used multiple times, unshare it except
2682 when emitting the last use. */
2684 && cinfo
->info
.exists ()
2685 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2687 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2689 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2692 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2694 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2695 with substituting a capture of that. */
2697 && cond_handling
!= 0
2698 && cinfo
->info
[where
].cond_expr_cond_p
)
2700 /* If substituting into a cond_expr condition, unshare. */
2701 if (cond_handling
== 1)
2702 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2703 /* If substituting elsewhere we might need to decompose it. */
2704 else if (cond_handling
== 2)
2706 /* ??? Returning false here will also not allow any other patterns
2707 to match unless this generator was split out. */
2708 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2709 fprintf_indent (f
, indent
, " {\n");
2710 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2711 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2713 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2714 " TREE_OPERAND (%s, 1));\n",
2715 dest
, dest
, dest
, dest
, dest
);
2716 fprintf_indent (f
, indent
, " }\n");
2721 /* Return the name of the operand representing the decision tree node.
2722 Use NAME as space to generate it. */
2725 dt_operand::get_name (char *name
)
2728 sprintf (name
, "t");
2729 else if (parent
->level
== 1)
2730 sprintf (name
, "_p%u", pos
);
2731 else if (parent
->type
== dt_node::DT_MATCH
)
2732 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2734 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2738 /* Fill NAME with the operand name at position POS. */
2741 dt_operand::gen_opname (char *name
, unsigned pos
)
2744 sprintf (name
, "_p%u", pos
);
2746 sprintf (name
, "_q%u%u", level
, pos
);
2749 /* Generate matching code for the decision tree operand which is
2753 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2755 predicate
*p
= as_a
<predicate
*> (op
);
2757 if (p
->p
->matchers
.exists ())
2759 /* If this is a predicate generated from a pattern mangle its
2760 name and pass on the valueize hook. */
2762 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2765 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2768 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2769 fprintf_indent (f
, indent
+ 2, "{\n");
2773 /* Generate matching code for the decision tree operand which is
2777 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2779 char match_opname
[20];
2780 match_dop
->get_name (match_opname
);
2782 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2783 "|| operand_equal_p (%s, %s, 0))\n",
2784 opname
, match_opname
, opname
, opname
, match_opname
);
2786 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2787 "|| (operand_equal_p (%s, %s, 0) "
2788 "&& types_match (%s, %s)))\n",
2789 opname
, match_opname
, opname
, opname
, match_opname
,
2790 opname
, match_opname
);
2791 fprintf_indent (f
, indent
+ 2, "{\n");
2795 /* Generate GIMPLE matching code for the decision tree operand. */
2798 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2800 expr
*e
= static_cast<expr
*> (op
);
2801 id_base
*id
= e
->operation
;
2802 unsigned n_ops
= e
->ops
.length ();
2803 unsigned n_braces
= 0;
2805 for (unsigned i
= 0; i
< n_ops
; ++i
)
2807 char child_opname
[20];
2808 gen_opname (child_opname
, i
);
2810 if (id
->kind
== id_base::CODE
)
2813 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2814 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2816 /* ??? If this is a memory operation we can't (and should not)
2817 match this. The only sensible operand types are
2818 SSA names and invariants. */
2823 fprintf_indent (f
, indent
,
2824 "tree %s = TREE_OPERAND (%s, %i);\n",
2825 child_opname
, opname
, i
);
2828 fprintf_indent (f
, indent
,
2829 "tree %s = TREE_OPERAND "
2830 "(gimple_assign_rhs1 (_a%d), %i);\n",
2831 child_opname
, depth
, i
);
2832 fprintf_indent (f
, indent
,
2833 "if ((TREE_CODE (%s) == SSA_NAME\n",
2835 fprintf_indent (f
, indent
,
2836 " || is_gimple_min_invariant (%s)))\n",
2838 fprintf_indent (f
, indent
,
2842 fprintf_indent (f
, indent
,
2843 "%s = do_valueize (valueize, %s);\n",
2844 child_opname
, child_opname
);
2848 fprintf_indent (f
, indent
,
2849 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2850 child_opname
, i
+ 1, depth
);
2853 fprintf_indent (f
, indent
,
2854 "tree %s = gimple_call_arg (_c%d, %u);\n",
2855 child_opname
, depth
, i
);
2856 fprintf_indent (f
, indent
,
2857 "%s = do_valueize (valueize, %s);\n",
2858 child_opname
, child_opname
);
2860 /* While the toplevel operands are canonicalized by the caller
2861 after valueizing operands of sub-expressions we have to
2862 re-canonicalize operand order. */
2863 int opno
= commutative_op (id
);
2866 char child_opname0
[20], child_opname1
[20];
2867 gen_opname (child_opname0
, opno
);
2868 gen_opname (child_opname1
, opno
+ 1);
2869 fprintf_indent (f
, indent
,
2870 "if (tree_swap_operands_p (%s, %s))\n",
2871 child_opname0
, child_opname1
);
2872 fprintf_indent (f
, indent
,
2873 " std::swap (%s, %s);\n",
2874 child_opname0
, child_opname1
);
2880 /* Generate GENERIC matching code for the decision tree operand. */
2883 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2885 expr
*e
= static_cast<expr
*> (op
);
2886 unsigned n_ops
= e
->ops
.length ();
2888 for (unsigned i
= 0; i
< n_ops
; ++i
)
2890 char child_opname
[20];
2891 gen_opname (child_opname
, i
);
2893 if (e
->operation
->kind
== id_base::CODE
)
2894 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2895 child_opname
, opname
, i
);
2897 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2898 child_opname
, opname
, i
);
2904 /* Generate matching code for the children of the decision tree node. */
2907 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2909 auto_vec
<dt_operand
*> gimple_exprs
;
2910 auto_vec
<dt_operand
*> generic_exprs
;
2911 auto_vec
<dt_operand
*> fns
;
2912 auto_vec
<dt_operand
*> generic_fns
;
2913 auto_vec
<dt_operand
*> preds
;
2914 auto_vec
<dt_node
*> others
;
2916 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2918 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2920 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2921 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2923 if (e
->ops
.length () == 0
2924 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2925 generic_exprs
.safe_push (op
);
2926 else if (e
->operation
->kind
== id_base::FN
)
2931 generic_fns
.safe_push (op
);
2933 else if (e
->operation
->kind
== id_base::PREDICATE
)
2934 preds
.safe_push (op
);
2937 if (gimple
&& !e
->is_generic
)
2938 gimple_exprs
.safe_push (op
);
2940 generic_exprs
.safe_push (op
);
2943 else if (op
->op
->type
== operand::OP_PREDICATE
)
2944 others
.safe_push (kids
[i
]);
2948 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2949 others
.safe_push (kids
[i
]);
2950 else if (kids
[i
]->type
== dt_node::DT_MATCH
2951 || kids
[i
]->type
== dt_node::DT_TRUE
)
2953 /* A DT_TRUE operand serves as a barrier - generate code now
2954 for what we have collected sofar.
2955 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2956 dependent matches to get out-of-order. Generate code now
2957 for what we have collected sofar. */
2958 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2959 fns
, generic_fns
, preds
, others
);
2960 /* And output the true operand itself. */
2961 kids
[i
]->gen (f
, indent
, gimple
, depth
);
2962 gimple_exprs
.truncate (0);
2963 generic_exprs
.truncate (0);
2965 generic_fns
.truncate (0);
2967 others
.truncate (0);
2973 /* Generate code for the remains. */
2974 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2975 fns
, generic_fns
, preds
, others
);
2978 /* Generate matching code for the children of the decision tree node. */
2981 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
2982 vec
<dt_operand
*> gimple_exprs
,
2983 vec
<dt_operand
*> generic_exprs
,
2984 vec
<dt_operand
*> fns
,
2985 vec
<dt_operand
*> generic_fns
,
2986 vec
<dt_operand
*> preds
,
2987 vec
<dt_node
*> others
)
2990 char *kid_opname
= buf
;
2992 unsigned exprs_len
= gimple_exprs
.length ();
2993 unsigned gexprs_len
= generic_exprs
.length ();
2994 unsigned fns_len
= fns
.length ();
2995 unsigned gfns_len
= generic_fns
.length ();
2997 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3000 gimple_exprs
[0]->get_name (kid_opname
);
3002 fns
[0]->get_name (kid_opname
);
3004 generic_fns
[0]->get_name (kid_opname
);
3006 generic_exprs
[0]->get_name (kid_opname
);
3008 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3009 fprintf_indent (f
, indent
, " {\n");
3013 if (exprs_len
|| fns_len
)
3016 fprintf_indent (f
, indent
,
3017 "case SSA_NAME:\n");
3018 fprintf_indent (f
, indent
,
3019 " if (gimple *_d%d = get_def (valueize, %s))\n",
3021 fprintf_indent (f
, indent
,
3026 fprintf_indent (f
, indent
,
3027 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3029 fprintf_indent (f
, indent
,
3030 " switch (gimple_assign_rhs_code (_a%d))\n",
3033 fprintf_indent (f
, indent
, "{\n");
3034 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3036 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3037 id_base
*op
= e
->operation
;
3038 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3039 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3041 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3042 fprintf_indent (f
, indent
, " {\n");
3043 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3044 fprintf_indent (f
, indent
, " break;\n");
3045 fprintf_indent (f
, indent
, " }\n");
3047 fprintf_indent (f
, indent
, "default:;\n");
3048 fprintf_indent (f
, indent
, "}\n");
3054 fprintf_indent (f
, indent
,
3055 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3056 exprs_len
? "else " : "", depth
, depth
);
3057 fprintf_indent (f
, indent
,
3058 " switch (gimple_call_combined_fn (_c%d))\n",
3062 fprintf_indent (f
, indent
, "{\n");
3063 for (unsigned i
= 0; i
< fns_len
; ++i
)
3065 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3066 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3067 /* We need to be defensive against bogus prototypes allowing
3068 calls with not enough arguments. */
3069 fprintf_indent (f
, indent
,
3070 " if (gimple_call_num_args (_c%d) == %d)\n",
3071 depth
, e
->ops
.length ());
3072 fprintf_indent (f
, indent
, " {\n");
3073 fns
[i
]->gen (f
, indent
+ 6, true, depth
);
3074 fprintf_indent (f
, indent
, " }\n");
3075 fprintf_indent (f
, indent
, " break;\n");
3078 fprintf_indent (f
, indent
, "default:;\n");
3079 fprintf_indent (f
, indent
, "}\n");
3085 fprintf_indent (f
, indent
, " }\n");
3086 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3087 here rather than in the next loop. */
3088 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3090 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3091 id_base
*op
= e
->operation
;
3092 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3094 fprintf_indent (f
, indent
+ 4, "{\n");
3095 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3096 fprintf_indent (f
, indent
+ 4, "}\n");
3100 fprintf_indent (f
, indent
, " break;\n");
3103 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3105 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3106 id_base
*op
= e
->operation
;
3107 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3108 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3109 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3110 /* Already handled above. */
3113 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3114 fprintf_indent (f
, indent
, " {\n");
3115 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3116 fprintf_indent (f
, indent
, " break;\n");
3117 fprintf_indent (f
, indent
, " }\n");
3122 fprintf_indent (f
, indent
,
3123 "case CALL_EXPR:\n");
3124 fprintf_indent (f
, indent
,
3125 " switch (get_call_combined_fn (%s))\n",
3127 fprintf_indent (f
, indent
,
3131 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3133 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3134 gcc_assert (e
->operation
->kind
== id_base::FN
);
3136 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3137 fprintf_indent (f
, indent
, " if (call_expr_nargs (%s) == %d)\n"
3138 " {\n", kid_opname
, e
->ops
.length ());
3139 generic_fns
[j
]->gen (f
, indent
+ 6, false, depth
);
3140 fprintf_indent (f
, indent
, " }\n"
3143 fprintf_indent (f
, indent
, "default:;\n");
3146 fprintf_indent (f
, indent
, " }\n");
3147 fprintf_indent (f
, indent
, " break;\n");
3150 /* Close switch (TREE_CODE ()). */
3151 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3154 fprintf_indent (f
, indent
, " default:;\n");
3155 fprintf_indent (f
, indent
, " }\n");
3158 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3160 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3161 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3162 preds
[i
]->get_name (kid_opname
);
3163 fprintf_indent (f
, indent
, "{\n");
3165 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3166 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3167 gimple
? "gimple" : "tree",
3168 p
->id
, kid_opname
, kid_opname
,
3169 gimple
? ", valueize" : "");
3170 fprintf_indent (f
, indent
, " {\n");
3171 for (int j
= 0; j
< p
->nargs
; ++j
)
3173 char child_opname
[20];
3174 preds
[i
]->gen_opname (child_opname
, j
);
3175 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3176 child_opname
, kid_opname
, j
);
3178 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3181 fprintf_indent (f
, indent
, "}\n");
3184 for (unsigned i
= 0; i
< others
.length (); ++i
)
3185 others
[i
]->gen (f
, indent
, gimple
, depth
);
3188 /* Generate matching code for the decision tree operand. */
3191 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3196 unsigned n_braces
= 0;
3198 if (type
== DT_OPERAND
)
3201 case operand::OP_PREDICATE
:
3202 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3205 case operand::OP_EXPR
:
3207 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3209 n_braces
= gen_generic_expr (f
, indent
, opname
);
3215 else if (type
== DT_TRUE
)
3217 else if (type
== DT_MATCH
)
3218 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3222 indent
+= 4 * n_braces
;
3223 gen_kids (f
, indent
, gimple
, depth
);
3225 for (unsigned i
= 0; i
< n_braces
; ++i
)
3230 fprintf_indent (f
, indent
, " }\n");
3235 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3236 step of a '(simplify ...)' or '(match ...)'. This handles everything
3237 that is not part of the decision tree (simplify->match).
3238 Main recursive worker. */
3241 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3245 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3247 fprintf_indent (f
, indent
, "{\n");
3249 output_line_directive (f
, w
->location
);
3250 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3251 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3253 fprintf_indent (f
, indent
, "}\n");
3256 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3258 output_line_directive (f
, ife
->location
);
3259 fprintf_indent (f
, indent
, "if (");
3260 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3262 fprintf_indent (f
, indent
+ 2, "{\n");
3264 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3266 fprintf_indent (f
, indent
+ 2, "}\n");
3269 fprintf_indent (f
, indent
, "else\n");
3270 fprintf_indent (f
, indent
+ 2, "{\n");
3272 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3274 fprintf_indent (f
, indent
+ 2, "}\n");
3280 static unsigned fail_label_cnt
;
3281 char local_fail_label
[256];
3282 snprintf (local_fail_label
, 256, "next_after_fail%u", ++fail_label_cnt
);
3283 fail_label
= local_fail_label
;
3285 /* Analyze captures and perform early-outs on the incoming arguments
3286 that cover cases we cannot handle. */
3287 capture_info
cinfo (s
, result
, gimple
);
3288 if (s
->kind
== simplify::SIMPLIFY
)
3292 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3293 if (cinfo
.force_no_side_effects
& (1 << i
))
3295 fprintf_indent (f
, indent
,
3296 "if (TREE_SIDE_EFFECTS (_p%d)) goto %s;\n",
3299 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3300 "forcing toplevel operand to have no "
3303 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3304 if (cinfo
.info
[i
].cse_p
)
3306 else if (cinfo
.info
[i
].force_no_side_effects_p
3307 && (cinfo
.info
[i
].toplevel_msk
3308 & cinfo
.force_no_side_effects
) == 0)
3310 fprintf_indent (f
, indent
,
3311 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3312 "goto %s;\n", i
, fail_label
);
3314 warning_at (cinfo
.info
[i
].c
->location
,
3315 "forcing captured operand to have no "
3318 else if ((cinfo
.info
[i
].toplevel_msk
3319 & cinfo
.force_no_side_effects
) != 0)
3320 /* Mark capture as having no side-effects if we had to verify
3321 that via forced toplevel operand checks. */
3322 cinfo
.info
[i
].force_no_side_effects_p
= true;
3326 /* Force single-use restriction by only allowing simple
3327 results via setting seq to NULL. */
3328 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3329 bool first_p
= true;
3330 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3331 if (cinfo
.info
[i
].force_single_use
)
3335 fprintf_indent (f
, indent
, "if (lseq\n");
3336 fprintf_indent (f
, indent
, " && (");
3342 fprintf_indent (f
, indent
, " || ");
3344 fprintf (f
, "!single_use (captures[%d])", i
);
3348 fprintf (f
, "))\n");
3349 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3354 if (s
->kind
== simplify::SIMPLIFY
)
3355 fprintf_indent (f
, indent
, "if (__builtin_expect (!dbg_cnt (match), 0)) goto %s;\n", fail_label
);
3357 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3358 "fprintf (dump_file, \"%s ",
3359 s
->kind
== simplify::SIMPLIFY
3360 ? "Applying pattern" : "Matching expression");
3361 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3362 output_line_directive (f
,
3363 result
? result
->location
: s
->match
->location
, true,
3365 fprintf (f
, ", __FILE__, __LINE__);\n");
3367 fprintf_indent (f
, indent
, "{\n");
3371 /* If there is no result then this is a predicate implementation. */
3372 fprintf_indent (f
, indent
, "return true;\n");
3376 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3377 in outermost position). */
3378 if (result
->type
== operand::OP_EXPR
3379 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3380 result
= as_a
<expr
*> (result
)->ops
[0];
3381 if (result
->type
== operand::OP_EXPR
)
3383 expr
*e
= as_a
<expr
*> (result
);
3384 id_base
*opr
= e
->operation
;
3385 bool is_predicate
= false;
3386 /* When we delay operator substituting during lowering of fors we
3387 make sure that for code-gen purposes the effects of each substitute
3388 are the same. Thus just look at that. */
3389 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3390 opr
= uid
->substitutes
[0];
3391 else if (is_a
<predicate_id
*> (opr
))
3392 is_predicate
= true;
3394 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3395 *e
->operation
== CONVERT_EXPR
3396 ? "NOP_EXPR" : e
->operation
->id
,
3398 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3402 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3404 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3406 = get_operand_type (opr
, j
,
3407 "type", e
->expr_type
,
3409 : "TREE_TYPE (res_op->ops[0])");
3410 /* We need to expand GENERIC conditions we captured from
3411 COND_EXPRs and we need to unshare them when substituting
3413 int cond_handling
= 0;
3415 cond_handling
= (*opr
== COND_EXPR
&& j
== 0) ? 1 : 2;
3416 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3417 &cinfo
, indexes
, cond_handling
);
3420 /* Re-fold the toplevel result. It's basically an embedded
3421 gimple_build w/o actually building the stmt. */
3424 fprintf_indent (f
, indent
,
3425 "res_op->resimplify (lseq, valueize);\n");
3427 fprintf_indent (f
, indent
,
3428 "if (!maybe_push_res_to_seq (res_op, NULL)) "
3429 "goto %s;\n", fail_label
);
3432 else if (result
->type
== operand::OP_CAPTURE
3433 || result
->type
== operand::OP_C_EXPR
)
3435 fprintf_indent (f
, indent
, "tree tem;\n");
3436 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3438 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3439 if (is_a
<capture
*> (result
)
3440 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3442 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3443 with substituting a capture of that. */
3444 fprintf_indent (f
, indent
,
3445 "if (COMPARISON_CLASS_P (tem))\n");
3446 fprintf_indent (f
, indent
,
3448 fprintf_indent (f
, indent
,
3449 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3450 fprintf_indent (f
, indent
,
3451 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3452 fprintf_indent (f
, indent
,
3458 fprintf_indent (f
, indent
, "return true;\n");
3462 bool is_predicate
= false;
3463 if (result
->type
== operand::OP_EXPR
)
3465 expr
*e
= as_a
<expr
*> (result
);
3466 id_base
*opr
= e
->operation
;
3467 /* When we delay operator substituting during lowering of fors we
3468 make sure that for code-gen purposes the effects of each substitute
3469 are the same. Thus just look at that. */
3470 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3471 opr
= uid
->substitutes
[0];
3472 else if (is_a
<predicate_id
*> (opr
))
3473 is_predicate
= true;
3474 /* Search for captures used multiple times in the result expression
3475 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3476 original expression. */
3478 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3480 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3481 || cinfo
.info
[i
].cse_p
)
3483 if (cinfo
.info
[i
].result_use_count
3484 > cinfo
.info
[i
].match_use_count
)
3485 fprintf_indent (f
, indent
,
3486 "if (! tree_invariant_p (captures[%d])) "
3487 "goto %s;\n", i
, fail_label
);
3489 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3493 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3496 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3497 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3500 = get_operand_type (opr
, j
,
3501 "type", e
->expr_type
,
3503 ? NULL
: "TREE_TYPE (res_op0)");
3504 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3508 fprintf_indent (f
, indent
, "return true;\n");
3511 fprintf_indent (f
, indent
, "tree _r;\n");
3512 /* Re-fold the toplevel result. Use non_lvalue to
3513 build NON_LVALUE_EXPRs so they get properly
3514 ignored when in GIMPLE form. */
3515 if (*opr
== NON_LVALUE_EXPR
)
3516 fprintf_indent (f
, indent
,
3517 "_r = non_lvalue_loc (loc, res_op0);\n");
3520 if (is_a
<operator_id
*> (opr
))
3521 fprintf_indent (f
, indent
,
3522 "_r = fold_build%d_loc (loc, %s, type",
3524 *e
->operation
== CONVERT_EXPR
3525 ? "NOP_EXPR" : e
->operation
->id
);
3527 fprintf_indent (f
, indent
,
3528 "_r = maybe_build_call_expr_loc (loc, "
3529 "%s, type, %d", e
->operation
->id
,
3531 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3532 fprintf (f
, ", res_op%d", j
);
3533 fprintf (f
, ");\n");
3534 if (!is_a
<operator_id
*> (opr
))
3536 fprintf_indent (f
, indent
, "if (!_r)\n");
3537 fprintf_indent (f
, indent
, " goto %s;\n", fail_label
);
3542 else if (result
->type
== operand::OP_CAPTURE
3543 || result
->type
== operand::OP_C_EXPR
)
3546 fprintf_indent (f
, indent
, "tree _r;\n");
3547 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3554 /* Search for captures not used in the result expression and dependent
3555 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3556 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3558 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3560 if (!cinfo
.info
[i
].force_no_side_effects_p
3561 && !cinfo
.info
[i
].expr_p
3562 && cinfo
.info
[i
].result_use_count
== 0)
3564 fprintf_indent (f
, indent
,
3565 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3567 fprintf_indent (f
, indent
+ 2,
3568 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3569 "fold_ignored_result (captures[%d]), _r);\n",
3573 fprintf_indent (f
, indent
, "return _r;\n");
3577 fprintf_indent (f
, indent
, "}\n");
3578 fprintf (f
, "%s:;\n", fail_label
);
3582 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3583 step of a '(simplify ...)' or '(match ...)'. This handles everything
3584 that is not part of the decision tree (simplify->match). */
3587 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3589 fprintf_indent (f
, indent
, "{\n");
3591 output_line_directive (f
,
3592 s
->result
? s
->result
->location
: s
->match
->location
);
3593 if (s
->capture_max
>= 0)
3596 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3597 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3599 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3603 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3605 fprintf (f
, " };\n");
3608 /* If we have a split-out function for the actual transform, call it. */
3609 if (info
&& info
->fname
)
3613 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3614 "valueize, type, captures", info
->fname
);
3615 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3616 if (s
->for_subst_vec
[i
].first
->used
)
3617 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3618 fprintf (f
, "))\n");
3619 fprintf_indent (f
, indent
, " return true;\n");
3623 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3625 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3626 fprintf (f
, ", _p%d", i
);
3627 fprintf (f
, ", captures");
3628 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3630 if (s
->for_subst_vec
[i
].first
->used
)
3631 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3633 fprintf (f
, ");\n");
3634 fprintf_indent (f
, indent
, "if (res) return res;\n");
3639 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3641 if (! s
->for_subst_vec
[i
].first
->used
)
3643 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3644 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3645 s
->for_subst_vec
[i
].first
->id
,
3646 s
->for_subst_vec
[i
].second
->id
);
3647 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3648 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3649 s
->for_subst_vec
[i
].first
->id
,
3650 s
->for_subst_vec
[i
].second
->id
);
3654 gen_1 (f
, indent
, gimple
, s
->result
);
3658 fprintf_indent (f
, indent
, "}\n");
3662 /* Hash function for finding equivalent transforms. */
3665 sinfo_hashmap_traits::hash (const key_type
&v
)
3667 /* Only bother to compare those originating from the same source pattern. */
3668 return v
->s
->result
->location
;
3671 /* Compare function for finding equivalent transforms. */
3674 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3676 if (o1
->type
!= o2
->type
)
3681 case operand::OP_IF
:
3683 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3684 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3685 /* ??? Properly compare c-exprs. */
3686 if (if1
->cond
!= if2
->cond
)
3688 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3690 if (if1
->falseexpr
!= if2
->falseexpr
3692 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3696 case operand::OP_WITH
:
3698 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3699 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3700 if (with1
->with
!= with2
->with
)
3702 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3707 /* We've hit a result. Time to compare capture-infos - this is required
3708 in addition to the conservative pointer-equivalency of the result IL. */
3709 capture_info
cinfo1 (s1
, o1
, true);
3710 capture_info
cinfo2 (s2
, o2
, true);
3712 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3713 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3716 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3718 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3719 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3720 || (cinfo1
.info
[i
].force_no_side_effects_p
3721 != cinfo2
.info
[i
].force_no_side_effects_p
)
3722 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3723 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3724 /* toplevel_msk is an optimization */
3725 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3726 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3727 /* the pointer back to the capture is for diagnostics only */)
3731 /* ??? Deep-compare the actual result. */
3736 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3737 const key_type
&candidate
)
3739 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3743 /* Main entry to generate code for matching GIMPLE IL off the decision
3747 decision_tree::gen (FILE *f
, bool gimple
)
3753 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3754 "a total number of %u nodes\n",
3755 gimple
? "GIMPLE" : "GENERIC",
3756 root
->num_leafs
, root
->max_level
, root
->total_size
);
3758 /* First split out the transform part of equal leafs. */
3761 for (sinfo_map_t::iterator iter
= si
.begin ();
3762 iter
!= si
.end (); ++iter
)
3764 sinfo
*s
= (*iter
).second
;
3765 /* Do not split out single uses. */
3772 fprintf (stderr
, "found %u uses of", s
->cnt
);
3773 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3776 /* Generate a split out function with the leaf transform code. */
3777 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3780 fprintf (f
, "\nstatic bool\n"
3781 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3782 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3783 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3788 fprintf (f
, "\nstatic tree\n"
3789 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3790 (*iter
).second
->fname
);
3791 for (unsigned i
= 0;
3792 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3793 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3794 fprintf (f
, " tree *captures\n");
3796 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3798 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3800 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3801 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3802 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3803 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3804 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3805 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3808 fprintf (f
, ")\n{\n");
3809 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3811 fprintf (f
, " return false;\n");
3813 fprintf (f
, " return NULL_TREE;\n");
3816 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3818 for (unsigned n
= 1; n
<= 5; ++n
)
3820 bool has_kids_p
= false;
3822 /* First generate split-out functions. */
3823 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3825 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3826 expr
*e
= static_cast<expr
*>(dop
->op
);
3827 if (e
->ops
.length () != n
3828 /* Builtin simplifications are somewhat premature on
3829 GENERIC. The following drops patterns with outermost
3830 calls. It's easy to emit overloads for function code
3831 though if necessary. */
3833 && e
->operation
->kind
!= id_base::CODE
))
3837 fprintf (f
, "\nstatic bool\n"
3838 "gimple_simplify_%s (gimple_match_op *res_op,"
3839 " gimple_seq *seq,\n"
3840 " tree (*valueize)(tree) "
3841 "ATTRIBUTE_UNUSED,\n"
3842 " code_helper ARG_UNUSED (code), tree "
3843 "ARG_UNUSED (type)\n",
3846 fprintf (f
, "\nstatic tree\n"
3847 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3848 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3850 for (unsigned i
= 0; i
< n
; ++i
)
3851 fprintf (f
, ", tree _p%d", i
);
3854 dop
->gen_kids (f
, 2, gimple
, 0);
3856 fprintf (f
, " return false;\n");
3858 fprintf (f
, " return NULL_TREE;\n");
3863 /* If this main entry has no children, avoid generating code
3864 with compiler warnings, by generating a simple stub. */
3868 fprintf (f
, "\nstatic bool\n"
3869 "gimple_simplify (gimple_match_op*, gimple_seq*,\n"
3870 " tree (*)(tree), code_helper,\n"
3873 fprintf (f
, "\ntree\n"
3874 "generic_simplify (location_t, enum tree_code,\n"
3876 for (unsigned i
= 0; i
< n
; ++i
)
3877 fprintf (f
, ", tree");
3881 fprintf (f
, " return false;\n");
3883 fprintf (f
, " return NULL_TREE;\n");
3888 /* Then generate the main entry with the outermost switch and
3889 tail-calls to the split-out functions. */
3891 fprintf (f
, "\nstatic bool\n"
3892 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3893 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3894 " code_helper code, const tree type");
3896 fprintf (f
, "\ntree\n"
3897 "generic_simplify (location_t loc, enum tree_code code, "
3898 "const tree type ATTRIBUTE_UNUSED");
3899 for (unsigned i
= 0; i
< n
; ++i
)
3900 fprintf (f
, ", tree _p%d", i
);
3905 fprintf (f
, " switch (code.get_rep())\n"
3908 fprintf (f
, " switch (code)\n"
3910 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3912 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3913 expr
*e
= static_cast<expr
*>(dop
->op
);
3914 if (e
->ops
.length () != n
3915 /* Builtin simplifications are somewhat premature on
3916 GENERIC. The following drops patterns with outermost
3917 calls. It's easy to emit overloads for function code
3918 though if necessary. */
3920 && e
->operation
->kind
!= id_base::CODE
))
3923 if (*e
->operation
== CONVERT_EXPR
3924 || *e
->operation
== NOP_EXPR
)
3925 fprintf (f
, " CASE_CONVERT:\n");
3927 fprintf (f
, " case %s%s:\n",
3928 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3931 fprintf (f
, " return gimple_simplify_%s (res_op, "
3932 "seq, valueize, code, type", e
->operation
->id
);
3934 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3936 for (unsigned j
= 0; j
< n
; ++j
)
3937 fprintf (f
, ", _p%d", j
);
3938 fprintf (f
, ");\n");
3940 fprintf (f
, " default:;\n"
3944 fprintf (f
, " return false;\n");
3946 fprintf (f
, " return NULL_TREE;\n");
3951 /* Output code to implement the predicate P from the decision tree DT. */
3954 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3956 fprintf (f
, "\nbool\n"
3957 "%s%s (tree t%s%s)\n"
3958 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3959 p
->nargs
> 0 ? ", tree *res_ops" : "",
3960 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3961 /* Conveniently make 'type' available. */
3962 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3965 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3966 dt
.root
->gen_kids (f
, 2, gimple
, 0);
3968 fprintf_indent (f
, 2, "return false;\n"
3972 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3975 write_header (FILE *f
, const char *head
)
3977 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3978 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3980 /* Include the header instead of writing it awkwardly quoted here. */
3981 fprintf (f
, "\n#include \"%s\"\n", head
);
3991 parser (cpp_reader
*, bool gimple
);
3994 const cpp_token
*next ();
3995 const cpp_token
*peek (unsigned = 1);
3996 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3997 const cpp_token
*expect (enum cpp_ttype
);
3998 const cpp_token
*eat_token (enum cpp_ttype
);
3999 const char *get_string ();
4000 const char *get_ident ();
4001 const cpp_token
*eat_ident (const char *);
4002 const char *get_number ();
4004 unsigned get_internal_capture_id ();
4006 id_base
*parse_operation (unsigned char &);
4007 operand
*parse_capture (operand
*, bool);
4008 operand
*parse_expr ();
4009 c_expr
*parse_c_expr (cpp_ttype
);
4010 operand
*parse_op ();
4012 void record_operlist (location_t
, user_id
*);
4014 void parse_pattern ();
4015 operand
*parse_result (operand
*, predicate_id
*);
4016 void push_simplify (simplify::simplify_kind
,
4017 vec
<simplify
*>&, operand
*, operand
*);
4018 void parse_simplify (simplify::simplify_kind
,
4019 vec
<simplify
*>&, predicate_id
*, operand
*);
4020 void parse_for (location_t
);
4021 void parse_if (location_t
);
4022 void parse_predicates (location_t
);
4023 void parse_operator_list (location_t
);
4025 void finish_match_operand (operand
*);
4029 vec
<c_expr
*> active_ifs
;
4030 vec
<vec
<user_id
*> > active_fors
;
4031 hash_set
<user_id
*> *oper_lists_set
;
4032 vec
<user_id
*> oper_lists
;
4034 cid_map_t
*capture_ids
;
4038 vec
<simplify
*> simplifiers
;
4039 vec
<predicate_id
*> user_predicates
;
4040 bool parsing_match_operand
;
4043 /* Lexing helpers. */
4045 /* Read the next non-whitespace token from R. */
4050 const cpp_token
*token
;
4053 token
= cpp_get_token (r
);
4055 while (token
->type
== CPP_PADDING
);
4059 /* Peek at the next non-whitespace token from R. */
4062 parser::peek (unsigned num
)
4064 const cpp_token
*token
;
4068 token
= cpp_peek_token (r
, i
++);
4070 while (token
->type
== CPP_PADDING
4072 /* If we peek at EOF this is a fatal error as it leaves the
4073 cpp_reader in unusable state. Assume we really wanted a
4074 token and thus this EOF is unexpected. */
4075 if (token
->type
== CPP_EOF
)
4076 fatal_at (token
, "unexpected end of file");
4080 /* Peek at the next identifier token (or return NULL if the next
4081 token is not an identifier or equal to ID if supplied). */
4084 parser::peek_ident (const char *id
, unsigned num
)
4086 const cpp_token
*token
= peek (num
);
4087 if (token
->type
!= CPP_NAME
)
4093 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4094 if (strcmp (id
, t
) == 0)
4100 /* Read the next token from R and assert it is of type TK. */
4103 parser::expect (enum cpp_ttype tk
)
4105 const cpp_token
*token
= next ();
4106 if (token
->type
!= tk
)
4107 fatal_at (token
, "expected %s, got %s",
4108 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4113 /* Consume the next token from R and assert it is of type TK. */
4116 parser::eat_token (enum cpp_ttype tk
)
4121 /* Read the next token from R and assert it is of type CPP_STRING and
4122 return its value. */
4125 parser::get_string ()
4127 const cpp_token
*token
= expect (CPP_STRING
);
4128 return (const char *)token
->val
.str
.text
;
4131 /* Read the next token from R and assert it is of type CPP_NAME and
4132 return its value. */
4135 parser::get_ident ()
4137 const cpp_token
*token
= expect (CPP_NAME
);
4138 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4141 /* Eat an identifier token with value S from R. */
4144 parser::eat_ident (const char *s
)
4146 const cpp_token
*token
= peek ();
4147 const char *t
= get_ident ();
4148 if (strcmp (s
, t
) != 0)
4149 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4153 /* Read the next token from R and assert it is of type CPP_NUMBER and
4154 return its value. */
4157 parser::get_number ()
4159 const cpp_token
*token
= expect (CPP_NUMBER
);
4160 return (const char *)token
->val
.str
.text
;
4163 /* Return a capture ID that can be used internally. */
4166 parser::get_internal_capture_id ()
4168 unsigned newid
= capture_ids
->elements ();
4169 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4172 snprintf (id
, sizeof (id
), "__%u", newid
);
4173 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4175 fatal ("reserved capture id '%s' already used", id
);
4179 /* Record an operator-list use for transparent for handling. */
4182 parser::record_operlist (location_t loc
, user_id
*p
)
4184 if (!oper_lists_set
->add (p
))
4186 if (!oper_lists
.is_empty ()
4187 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4188 fatal_at (loc
, "User-defined operator list does not have the "
4189 "same number of entries as others used in the pattern");
4190 oper_lists
.safe_push (p
);
4194 /* Parse the operator ID, special-casing convert?, convert1? and
4198 parser::parse_operation (unsigned char &opt_grp
)
4200 const cpp_token
*id_tok
= peek ();
4201 char *alt_id
= NULL
;
4202 const char *id
= get_ident ();
4203 const cpp_token
*token
= peek ();
4205 if (token
->type
== CPP_QUERY
4206 && !(token
->flags
& PREV_WHITE
))
4208 if (!parsing_match_operand
)
4209 fatal_at (id_tok
, "conditional convert can only be used in "
4210 "match expression");
4211 if (ISDIGIT (id
[strlen (id
) - 1]))
4213 opt_grp
= id
[strlen (id
) - 1] - '0' + 1;
4214 alt_id
= xstrdup (id
);
4215 alt_id
[strlen (id
) - 1] = '\0';
4217 fatal_at (id_tok
, "use '%s?' here", alt_id
);
4221 eat_token (CPP_QUERY
);
4223 id_base
*op
= get_operator (alt_id
? alt_id
: id
);
4225 fatal_at (id_tok
, "unknown operator %s", alt_id
? alt_id
: id
);
4228 user_id
*p
= dyn_cast
<user_id
*> (op
);
4229 if (p
&& p
->is_oper_list
)
4231 if (active_fors
.length() == 0)
4232 record_operlist (id_tok
->src_loc
, p
);
4234 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4240 capture = '@'<number> */
4243 parser::parse_capture (operand
*op
, bool require_existing
)
4245 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4246 const cpp_token
*token
= peek ();
4247 const char *id
= NULL
;
4248 bool value_match
= false;
4249 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4250 if (token
->type
== CPP_ATSIGN
4251 && ! (token
->flags
& PREV_WHITE
)
4252 && parsing_match_operand
)
4254 eat_token (CPP_ATSIGN
);
4258 if (token
->type
== CPP_NUMBER
)
4260 else if (token
->type
== CPP_NAME
)
4263 fatal_at (token
, "expected number or identifier");
4264 unsigned next_id
= capture_ids
->elements ();
4266 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4269 if (require_existing
)
4270 fatal_at (src_loc
, "unknown capture id");
4273 return new capture (src_loc
, num
, op
, value_match
);
4276 /* Parse an expression
4277 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4280 parser::parse_expr ()
4282 const cpp_token
*token
= peek ();
4283 unsigned char opt_grp
;
4284 expr
*e
= new expr (parse_operation (opt_grp
), token
->src_loc
);
4287 bool is_commutative
= false;
4288 bool force_capture
= false;
4289 const char *expr_type
= NULL
;
4291 if (!parsing_match_operand
4292 && token
->type
== CPP_NOT
4293 && !(token
->flags
& PREV_WHITE
))
4296 fatal_at (token
, "forcing simplification to a leaf is not supported "
4298 eat_token (CPP_NOT
);
4299 e
->force_leaf
= true;
4302 if (token
->type
== CPP_COLON
4303 && !(token
->flags
& PREV_WHITE
))
4305 eat_token (CPP_COLON
);
4307 if (token
->type
== CPP_NAME
4308 && !(token
->flags
& PREV_WHITE
))
4310 const char *s
= get_ident ();
4311 if (!parsing_match_operand
)
4321 = dyn_cast
<operator_id
*> (e
->operation
))
4323 if (!commutative_tree_code (o
->code
)
4324 && !comparison_code_p (o
->code
))
4325 fatal_at (token
, "operation is not commutative");
4327 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4328 for (unsigned i
= 0;
4329 i
< p
->substitutes
.length (); ++i
)
4332 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4334 if (!commutative_tree_code (q
->code
)
4335 && !comparison_code_p (q
->code
))
4336 fatal_at (token
, "operation %s is not "
4337 "commutative", q
->id
);
4340 is_commutative
= true;
4342 else if (*sp
== 'C')
4343 is_commutative
= true;
4344 else if (*sp
== 's')
4346 e
->force_single_use
= true;
4347 force_capture
= true;
4350 fatal_at (token
, "flag %c not recognized", *sp
);
4357 fatal_at (token
, "expected flag or type specifying identifier");
4360 if (token
->type
== CPP_ATSIGN
4361 && !(token
->flags
& PREV_WHITE
))
4362 op
= parse_capture (e
, false);
4363 else if (force_capture
)
4365 unsigned num
= get_internal_capture_id ();
4366 op
= new capture (token
->src_loc
, num
, e
, false);
4373 if (token
->type
== CPP_CLOSE_PAREN
)
4375 if (e
->operation
->nargs
!= -1
4376 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4377 fatal_at (token
, "'%s' expects %u operands, not %u",
4378 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4381 if (e
->ops
.length () == 2
4382 || commutative_op (e
->operation
) >= 0)
4383 e
->is_commutative
= true;
4385 fatal_at (token
, "only binary operators or functions with "
4386 "two arguments can be marked commutative, "
4387 "unless the operation is known to be inherently "
4390 e
->expr_type
= expr_type
;
4393 if (e
->ops
.length () != 1)
4394 fatal_at (token
, "only unary operations can be conditional");
4395 e
->opt_grp
= opt_grp
;
4399 else if (!(token
->flags
& PREV_WHITE
))
4400 fatal_at (token
, "expected expression operand");
4402 e
->append_op (parse_op ());
4407 /* Lex native C code delimited by START recording the preprocessing tokens
4408 for later processing.
4409 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4412 parser::parse_c_expr (cpp_ttype start
)
4414 const cpp_token
*token
;
4417 vec
<cpp_token
> code
= vNULL
;
4418 unsigned nr_stmts
= 0;
4419 location_t loc
= eat_token (start
)->src_loc
;
4420 if (start
== CPP_OPEN_PAREN
)
4421 end
= CPP_CLOSE_PAREN
;
4422 else if (start
== CPP_OPEN_BRACE
)
4423 end
= CPP_CLOSE_BRACE
;
4431 /* Count brace pairs to find the end of the expr to match. */
4432 if (token
->type
== start
)
4434 else if (token
->type
== end
4437 else if (token
->type
== CPP_EOF
)
4438 fatal_at (token
, "unexpected end of file");
4440 /* This is a lame way of counting the number of statements. */
4441 if (token
->type
== CPP_SEMICOLON
)
4444 /* If this is possibly a user-defined identifier mark it used. */
4445 if (token
->type
== CPP_NAME
)
4447 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4448 (token
->val
.node
.node
)->ident
.str
);
4450 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4451 record_operlist (token
->src_loc
, p
);
4454 /* Record the token. */
4455 code
.safe_push (*token
);
4458 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4461 /* Parse an operand which is either an expression, a predicate or
4462 a standalone capture.
4463 op = predicate | expr | c_expr | capture */
4468 const cpp_token
*token
= peek ();
4469 class operand
*op
= NULL
;
4470 if (token
->type
== CPP_OPEN_PAREN
)
4472 eat_token (CPP_OPEN_PAREN
);
4474 eat_token (CPP_CLOSE_PAREN
);
4476 else if (token
->type
== CPP_OPEN_BRACE
)
4478 op
= parse_c_expr (CPP_OPEN_BRACE
);
4482 /* Remaining ops are either empty or predicates */
4483 if (token
->type
== CPP_NAME
)
4485 const char *id
= get_ident ();
4486 id_base
*opr
= get_operator (id
);
4488 fatal_at (token
, "expected predicate name");
4489 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4491 if (code1
->nargs
!= 0)
4492 fatal_at (token
, "using an operator with operands as predicate");
4493 /* Parse the zero-operand operator "predicates" as
4495 op
= new expr (opr
, token
->src_loc
);
4497 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4499 if (code2
->nargs
!= 0)
4500 fatal_at (token
, "using an operator with operands as predicate");
4501 /* Parse the zero-operand operator "predicates" as
4503 op
= new expr (opr
, token
->src_loc
);
4505 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4506 op
= new predicate (p
, token
->src_loc
);
4508 fatal_at (token
, "using an unsupported operator as predicate");
4509 if (!parsing_match_operand
)
4510 fatal_at (token
, "predicates are only allowed in match expression");
4512 if (token
->flags
& PREV_WHITE
)
4515 else if (token
->type
!= CPP_COLON
4516 && token
->type
!= CPP_ATSIGN
)
4517 fatal_at (token
, "expected expression or predicate");
4518 /* optionally followed by a capture and a predicate. */
4519 if (token
->type
== CPP_COLON
)
4520 fatal_at (token
, "not implemented: predicate on leaf operand");
4521 if (token
->type
== CPP_ATSIGN
)
4522 op
= parse_capture (op
, !parsing_match_operand
);
4528 /* Create a new simplify from the current parsing state and MATCH,
4529 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4532 parser::push_simplify (simplify::simplify_kind kind
,
4533 vec
<simplify
*>& simplifiers
,
4534 operand
*match
, operand
*result
)
4536 /* Build and push a temporary for operator list uses in expressions. */
4537 if (!oper_lists
.is_empty ())
4538 active_fors
.safe_push (oper_lists
);
4540 simplifiers
.safe_push
4541 (new simplify (kind
, last_id
++, match
, result
,
4542 active_fors
.copy (), capture_ids
));
4544 if (!oper_lists
.is_empty ())
4549 <result-op> = <op> | <if> | <with>
4550 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4551 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4555 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4557 const cpp_token
*token
= peek ();
4558 if (token
->type
!= CPP_OPEN_PAREN
)
4561 eat_token (CPP_OPEN_PAREN
);
4562 if (peek_ident ("if"))
4565 if_expr
*ife
= new if_expr (token
->src_loc
);
4566 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4567 if (peek ()->type
== CPP_OPEN_PAREN
)
4569 ife
->trueexpr
= parse_result (result
, matcher
);
4570 if (peek ()->type
== CPP_OPEN_PAREN
)
4571 ife
->falseexpr
= parse_result (result
, matcher
);
4572 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4573 ife
->falseexpr
= parse_op ();
4575 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4577 ife
->trueexpr
= parse_op ();
4578 if (peek ()->type
== CPP_OPEN_PAREN
)
4579 ife
->falseexpr
= parse_result (result
, matcher
);
4580 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4581 ife
->falseexpr
= parse_op ();
4583 /* If this if is immediately closed then it contains a
4584 manual matcher or is part of a predicate definition. */
4585 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4588 fatal_at (peek (), "manual transform not implemented");
4589 ife
->trueexpr
= result
;
4591 eat_token (CPP_CLOSE_PAREN
);
4594 else if (peek_ident ("with"))
4597 with_expr
*withe
= new with_expr (token
->src_loc
);
4598 /* Parse (with c-expr expr) as (if-with (true) expr). */
4599 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4600 withe
->with
->nr_stmts
= 0;
4601 withe
->subexpr
= parse_result (result
, matcher
);
4602 eat_token (CPP_CLOSE_PAREN
);
4605 else if (peek_ident ("switch"))
4607 token
= eat_ident ("switch");
4608 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4610 if_expr
*ife
= new if_expr (ifloc
);
4612 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4613 if (peek ()->type
== CPP_OPEN_PAREN
)
4614 ife
->trueexpr
= parse_result (result
, matcher
);
4616 ife
->trueexpr
= parse_op ();
4617 eat_token (CPP_CLOSE_PAREN
);
4618 if (peek ()->type
!= CPP_OPEN_PAREN
4619 || !peek_ident ("if", 2))
4620 fatal_at (token
, "switch can be implemented with a single if");
4621 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4623 if (peek ()->type
== CPP_OPEN_PAREN
)
4625 if (peek_ident ("if", 2))
4627 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4629 ife
->falseexpr
= new if_expr (ifloc
);
4630 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4631 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4632 if (peek ()->type
== CPP_OPEN_PAREN
)
4633 ife
->trueexpr
= parse_result (result
, matcher
);
4635 ife
->trueexpr
= parse_op ();
4636 eat_token (CPP_CLOSE_PAREN
);
4640 /* switch default clause */
4641 ife
->falseexpr
= parse_result (result
, matcher
);
4642 eat_token (CPP_CLOSE_PAREN
);
4648 /* switch default clause */
4649 ife
->falseexpr
= parse_op ();
4650 eat_token (CPP_CLOSE_PAREN
);
4654 eat_token (CPP_CLOSE_PAREN
);
4659 operand
*op
= result
;
4662 eat_token (CPP_CLOSE_PAREN
);
4668 simplify = 'simplify' <expr> <result-op>
4670 match = 'match' <ident> <expr> [<result-op>]
4671 and fill SIMPLIFIERS with the results. */
4674 parser::parse_simplify (simplify::simplify_kind kind
,
4675 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4678 /* Reset the capture map. */
4680 capture_ids
= new cid_map_t
;
4681 /* Reset oper_lists and set. */
4682 hash_set
<user_id
*> olist
;
4683 oper_lists_set
= &olist
;
4686 const cpp_token
*loc
= peek ();
4687 parsing_match_operand
= true;
4688 class operand
*match
= parse_op ();
4689 finish_match_operand (match
);
4690 parsing_match_operand
= false;
4691 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4692 fatal_at (loc
, "outermost expression cannot be captured");
4693 if (match
->type
== operand::OP_EXPR
4694 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4695 fatal_at (loc
, "outermost expression cannot be a predicate");
4697 /* Splice active_ifs onto result and continue parsing the
4699 if_expr
*active_if
= NULL
;
4700 for (int i
= active_ifs
.length (); i
> 0; --i
)
4702 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4703 ifc
->cond
= active_ifs
[i
-1];
4704 ifc
->trueexpr
= active_if
;
4707 if_expr
*outermost_if
= active_if
;
4708 while (active_if
&& active_if
->trueexpr
)
4709 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4711 const cpp_token
*token
= peek ();
4713 /* If this if is immediately closed then it is part of a predicate
4714 definition. Push it. */
4715 if (token
->type
== CPP_CLOSE_PAREN
)
4718 fatal_at (token
, "expected transform expression");
4721 active_if
->trueexpr
= result
;
4722 result
= outermost_if
;
4724 push_simplify (kind
, simplifiers
, match
, result
);
4728 operand
*tem
= parse_result (result
, matcher
);
4731 active_if
->trueexpr
= tem
;
4732 result
= outermost_if
;
4737 push_simplify (kind
, simplifiers
, match
, result
);
4740 /* Parsing of the outer control structures. */
4742 /* Parse a for expression
4743 for = '(' 'for' <subst>... <pattern> ')'
4744 subst = <ident> '(' <ident>... ')' */
4747 parser::parse_for (location_t
)
4749 auto_vec
<const cpp_token
*> user_id_tokens
;
4750 vec
<user_id
*> user_ids
= vNULL
;
4751 const cpp_token
*token
;
4752 unsigned min_n_opers
= 0, max_n_opers
= 0;
4757 if (token
->type
!= CPP_NAME
)
4760 /* Insert the user defined operators into the operator hash. */
4761 const char *id
= get_ident ();
4762 if (get_operator (id
, true) != NULL
)
4763 fatal_at (token
, "operator already defined");
4764 user_id
*op
= new user_id (id
);
4765 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4767 user_ids
.safe_push (op
);
4768 user_id_tokens
.safe_push (token
);
4770 eat_token (CPP_OPEN_PAREN
);
4773 while ((token
= peek_ident ()) != 0)
4775 const char *oper
= get_ident ();
4776 id_base
*idb
= get_operator (oper
, true);
4778 fatal_at (token
, "no such operator '%s'", oper
);
4782 else if (idb
->nargs
== -1)
4784 else if (idb
->nargs
!= arity
)
4785 fatal_at (token
, "operator '%s' with arity %d does not match "
4786 "others with arity %d", oper
, idb
->nargs
, arity
);
4788 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4791 if (p
->is_oper_list
)
4792 op
->substitutes
.safe_splice (p
->substitutes
);
4794 fatal_at (token
, "iterator cannot be used as operator-list");
4797 op
->substitutes
.safe_push (idb
);
4800 token
= expect (CPP_CLOSE_PAREN
);
4802 unsigned nsubstitutes
= op
->substitutes
.length ();
4803 if (nsubstitutes
== 0)
4804 fatal_at (token
, "A user-defined operator must have at least "
4805 "one substitution");
4806 if (max_n_opers
== 0)
4808 min_n_opers
= nsubstitutes
;
4809 max_n_opers
= nsubstitutes
;
4813 if (nsubstitutes
% min_n_opers
!= 0
4814 && min_n_opers
% nsubstitutes
!= 0)
4815 fatal_at (token
, "All user-defined identifiers must have a "
4816 "multiple number of operator substitutions of the "
4817 "smallest number of substitutions");
4818 if (nsubstitutes
< min_n_opers
)
4819 min_n_opers
= nsubstitutes
;
4820 else if (nsubstitutes
> max_n_opers
)
4821 max_n_opers
= nsubstitutes
;
4825 unsigned n_ids
= user_ids
.length ();
4827 fatal_at (token
, "for requires at least one user-defined identifier");
4830 if (token
->type
== CPP_CLOSE_PAREN
)
4831 fatal_at (token
, "no pattern defined in for");
4833 active_fors
.safe_push (user_ids
);
4837 if (token
->type
== CPP_CLOSE_PAREN
)
4843 /* Remove user-defined operators from the hash again. */
4844 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4846 if (!user_ids
[i
]->used
)
4847 warning_at (user_id_tokens
[i
],
4848 "operator %s defined but not used", user_ids
[i
]->id
);
4849 operators
->remove_elt (user_ids
[i
]);
4853 /* Parse an identifier associated with a list of operators.
4854 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4857 parser::parse_operator_list (location_t
)
4859 const cpp_token
*token
= peek ();
4860 const char *id
= get_ident ();
4862 if (get_operator (id
, true) != 0)
4863 fatal_at (token
, "operator %s already defined", id
);
4865 user_id
*op
= new user_id (id
, true);
4868 while ((token
= peek_ident ()) != 0)
4871 const char *oper
= get_ident ();
4872 id_base
*idb
= get_operator (oper
, true);
4875 fatal_at (token
, "no such operator '%s'", oper
);
4879 else if (idb
->nargs
== -1)
4881 else if (arity
!= idb
->nargs
)
4882 fatal_at (token
, "operator '%s' with arity %d does not match "
4883 "others with arity %d", oper
, idb
->nargs
, arity
);
4885 /* We allow composition of multiple operator lists. */
4886 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4887 op
->substitutes
.safe_splice (p
->substitutes
);
4889 op
->substitutes
.safe_push (idb
);
4892 // Check that there is no junk after id-list
4894 if (token
->type
!= CPP_CLOSE_PAREN
)
4895 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4897 if (op
->substitutes
.length () == 0)
4898 fatal_at (token
, "operator-list cannot be empty");
4901 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4905 /* Parse an outer if expression.
4906 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4909 parser::parse_if (location_t
)
4911 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4913 const cpp_token
*token
= peek ();
4914 if (token
->type
== CPP_CLOSE_PAREN
)
4915 fatal_at (token
, "no pattern defined in if");
4917 active_ifs
.safe_push (ifexpr
);
4921 if (token
->type
== CPP_CLOSE_PAREN
)
4929 /* Parse a list of predefined predicate identifiers.
4930 preds = '(' 'define_predicates' <ident>... ')' */
4933 parser::parse_predicates (location_t
)
4937 const cpp_token
*token
= peek ();
4938 if (token
->type
!= CPP_NAME
)
4941 add_predicate (get_ident ());
4946 /* Parse outer control structures.
4947 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4950 parser::parse_pattern ()
4952 /* All clauses start with '('. */
4953 eat_token (CPP_OPEN_PAREN
);
4954 const cpp_token
*token
= peek ();
4955 const char *id
= get_ident ();
4956 if (strcmp (id
, "simplify") == 0)
4958 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4961 else if (strcmp (id
, "match") == 0)
4963 bool with_args
= false;
4964 location_t e_loc
= peek ()->src_loc
;
4965 if (peek ()->type
== CPP_OPEN_PAREN
)
4967 eat_token (CPP_OPEN_PAREN
);
4970 const char *name
= get_ident ();
4971 id_base
*id1
= get_operator (name
);
4975 p
= add_predicate (name
);
4976 user_predicates
.safe_push (p
);
4978 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
4981 fatal_at (token
, "cannot add a match to a non-predicate ID");
4982 /* Parse (match <id> <arg>... (match-expr)) here. */
4986 capture_ids
= new cid_map_t
;
4987 e
= new expr (p
, e_loc
);
4988 while (peek ()->type
== CPP_ATSIGN
)
4989 e
->append_op (parse_capture (NULL
, false));
4990 eat_token (CPP_CLOSE_PAREN
);
4993 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4994 || (!e
&& p
->nargs
!= 0)))
4995 fatal_at (token
, "non-matching number of match operands");
4996 p
->nargs
= e
? e
->ops
.length () : 0;
4997 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
5000 else if (strcmp (id
, "for") == 0)
5001 parse_for (token
->src_loc
);
5002 else if (strcmp (id
, "if") == 0)
5003 parse_if (token
->src_loc
);
5004 else if (strcmp (id
, "define_predicates") == 0)
5006 if (active_ifs
.length () > 0
5007 || active_fors
.length () > 0)
5008 fatal_at (token
, "define_predicates inside if or for is not supported");
5009 parse_predicates (token
->src_loc
);
5011 else if (strcmp (id
, "define_operator_list") == 0)
5013 if (active_ifs
.length () > 0
5014 || active_fors
.length () > 0)
5015 fatal_at (token
, "operator-list inside if or for is not supported");
5016 parse_operator_list (token
->src_loc
);
5019 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
5020 active_ifs
.length () == 0 && active_fors
.length () == 0
5021 ? "'define_predicates', " : "");
5023 eat_token (CPP_CLOSE_PAREN
);
5026 /* Helper for finish_match_operand, collecting captures of OP in CPTS
5030 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
5035 if (capture
*c
= dyn_cast
<capture
*> (op
))
5037 cpts
[c
->where
].safe_push (c
);
5038 walk_captures (c
->what
, cpts
);
5040 else if (expr
*e
= dyn_cast
<expr
*> (op
))
5041 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
5042 walk_captures (e
->ops
[i
], cpts
);
5045 /* Finish up OP which is a match operand. */
5048 parser::finish_match_operand (operand
*op
)
5050 /* Look for matching captures, diagnose mis-uses of @@ and apply
5051 early lowering and distribution of value_match. */
5052 auto_vec
<vec
<capture
*> > cpts
;
5053 cpts
.safe_grow_cleared (capture_ids
->elements (), true);
5054 walk_captures (op
, cpts
);
5055 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5057 capture
*value_match
= NULL
;
5058 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5060 if (cpts
[i
][j
]->value_match
)
5063 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5064 value_match
= cpts
[i
][j
];
5067 if (cpts
[i
].length () == 1 && value_match
)
5068 fatal_at (value_match
->location
, "@@ without a matching capture");
5071 /* Duplicate prevailing capture with the existing ID, create
5072 a fake ID and rewrite all captures to use it. This turns
5073 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5074 value_match
->what
= new capture (value_match
->location
,
5076 value_match
->what
, false);
5077 /* Create a fake ID and rewrite all captures to use it. */
5078 unsigned newid
= get_internal_capture_id ();
5079 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5081 cpts
[i
][j
]->where
= newid
;
5082 cpts
[i
][j
]->value_match
= true;
5089 /* Main entry of the parser. Repeatedly parse outer control structures. */
5091 parser::parser (cpp_reader
*r_
, bool gimple_
)
5096 active_fors
= vNULL
;
5097 simplifiers
= vNULL
;
5098 oper_lists_set
= NULL
;
5101 user_predicates
= vNULL
;
5102 parsing_match_operand
= false;
5105 const cpp_token
*token
= next ();
5106 while (token
->type
!= CPP_EOF
)
5108 _cpp_backup_tokens (r
, 1);
5115 /* Helper for the linemap code. */
5118 round_alloc_size (size_t s
)
5124 /* The genmatch generator program. It reads from a pattern description
5125 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5128 main (int argc
, char **argv
)
5132 progname
= "genmatch";
5138 char *input
= argv
[argc
-1];
5139 for (int i
= 1; i
< argc
- 1; ++i
)
5141 if (strcmp (argv
[i
], "--gimple") == 0)
5143 else if (strcmp (argv
[i
], "--generic") == 0)
5145 else if (strcmp (argv
[i
], "-v") == 0)
5147 else if (strcmp (argv
[i
], "-vv") == 0)
5151 fprintf (stderr
, "Usage: genmatch "
5152 "[--gimple] [--generic] [-v[v]] input\n");
5157 line_table
= XCNEW (class line_maps
);
5158 linemap_init (line_table
, 0);
5159 line_table
->reallocator
= xrealloc
;
5160 line_table
->round_alloc_size
= round_alloc_size
;
5162 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5163 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5164 cb
->diagnostic
= diagnostic_cb
;
5166 /* Add the build directory to the #include "" search path. */
5167 cpp_dir
*dir
= XCNEW (cpp_dir
);
5168 dir
->name
= getpwd ();
5170 dir
->name
= ASTRDUP (".");
5171 cpp_set_include_chains (r
, dir
, NULL
, false);
5173 if (!cpp_read_main_file (r
, input
))
5175 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5176 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5178 null_id
= new id_base (id_base::NULL_ID
, "null");
5180 /* Pre-seed operators. */
5181 operators
= new hash_table
<id_base
> (1024);
5182 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5183 add_operator (SYM, # SYM, # TYPE, NARGS);
5184 #define END_OF_BASE_TREE_CODES
5186 #undef END_OF_BASE_TREE_CODES
5189 /* Pre-seed builtin functions.
5190 ??? Cannot use N (name) as that is targetm.emultls.get_address
5191 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5192 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5193 add_function (ENUM, "CFN_" # ENUM);
5194 #include "builtins.def"
5196 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5197 add_function (IFN_##CODE, "CFN_" #CODE);
5198 #include "internal-fn.def"
5201 parser
p (r
, gimple
);
5204 write_header (stdout
, "gimple-match-head.c");
5206 write_header (stdout
, "generic-match-head.c");
5208 /* Go over all predicates defined with patterns and perform
5209 lowering and code generation. */
5210 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5212 predicate_id
*pred
= p
.user_predicates
[i
];
5213 lower (pred
->matchers
, gimple
);
5216 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5217 print_matches (pred
->matchers
[j
]);
5220 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5221 dt
.insert (pred
->matchers
[j
], j
);
5226 write_predicate (stdout
, pred
, dt
, gimple
);
5229 /* Lower the main simplifiers and generate code for them. */
5230 lower (p
.simplifiers
, gimple
);
5233 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5234 print_matches (p
.simplifiers
[i
]);
5237 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5238 dt
.insert (p
.simplifiers
[i
], i
);
5243 dt
.gen (stdout
, gimple
);
5246 cpp_finish (r
, NULL
);