]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/genmatch.c
1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2018 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 struct line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 source_location 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 (source_location 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 error_cb (cpp_reader
*, int errtype
, int, rich_location
*richloc
,
77 const char *msg
, va_list *ap
)
79 const line_map_ordinary
*map
;
80 source_location location
= richloc
->get_loc ();
81 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
82 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
83 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
84 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
85 vfprintf (stderr
, msg
, *ap
);
86 fprintf (stderr
, "\n");
87 FILE *f
= fopen (loc
.file
, "r");
93 if (!fgets (buf
, 128, f
))
95 if (buf
[strlen (buf
) - 1] != '\n')
102 fprintf (stderr
, "%s", buf
);
103 for (int i
= 0; i
< loc
.column
- 1; ++i
)
106 fputc ('\n', stderr
);
111 if (errtype
== CPP_DL_FATAL
)
117 #if GCC_VERSION >= 4001
118 __attribute__((format (printf
, 2, 3)))
120 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
122 rich_location
richloc (line_table
, tk
->src_loc
);
125 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
130 #if GCC_VERSION >= 4001
131 __attribute__((format (printf
, 2, 3)))
133 fatal_at (source_location loc
, const char *msg
, ...)
135 rich_location
richloc (line_table
, loc
);
138 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
143 #if GCC_VERSION >= 4001
144 __attribute__((format (printf
, 2, 3)))
146 warning_at (const cpp_token
*tk
, const char *msg
, ...)
148 rich_location
richloc (line_table
, tk
->src_loc
);
151 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
156 #if GCC_VERSION >= 4001
157 __attribute__((format (printf
, 2, 3)))
159 warning_at (source_location loc
, const char *msg
, ...)
161 rich_location
richloc (line_table
, loc
);
164 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
168 /* Like fprintf, but print INDENT spaces at the beginning. */
171 #if GCC_VERSION >= 4001
172 __attribute__((format (printf
, 3, 4)))
174 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
177 for (; indent
>= 8; indent
-= 8)
179 fprintf (f
, "%*s", indent
, "");
180 va_start (ap
, format
);
181 vfprintf (f
, format
, ap
);
186 output_line_directive (FILE *f
, source_location location
,
187 bool dumpfile
= false)
189 const line_map_ordinary
*map
;
190 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
191 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
194 /* When writing to a dumpfile only dump the filename. */
195 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
196 #if defined(DIR_SEPARATOR_2)
197 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
198 if (pos2
&& (!file
|| (pos2
> file
)))
205 fprintf (f
, "%s:%d", file
, loc
.line
);
208 /* Other gen programs really output line directives here, at least for
209 development it's right now more convenient to have line information
210 from the generated file. Still keep the directives as comment for now
211 to easily back-point to the meta-description. */
212 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
216 /* Pull in tree codes and builtin function codes from their
219 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
232 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
233 enum built_in_function
{
234 #include "builtins.def"
238 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
240 #include "internal-fn.def"
245 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
246 CFN_##ENUM = int (ENUM),
247 #include "builtins.def"
249 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
250 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
251 #include "internal-fn.def"
256 #include "case-cfn-macros.h"
258 /* Return true if CODE represents a commutative tree code. Otherwise
261 commutative_tree_code (enum tree_code code
)
267 case MULT_HIGHPART_EXPR
:
282 case WIDEN_MULT_EXPR
:
283 case VEC_WIDEN_MULT_HI_EXPR
:
284 case VEC_WIDEN_MULT_LO_EXPR
:
285 case VEC_WIDEN_MULT_EVEN_EXPR
:
286 case VEC_WIDEN_MULT_ODD_EXPR
:
295 /* Return true if CODE represents a ternary tree code for which the
296 first two operands are commutative. Otherwise return false. */
298 commutative_ternary_tree_code (enum tree_code code
)
302 case WIDEN_MULT_PLUS_EXPR
:
303 case WIDEN_MULT_MINUS_EXPR
:
313 /* Return true if CODE is a comparison. */
316 comparison_code_p (enum tree_code code
)
343 /* Base class for all identifiers the parser knows. */
345 struct id_base
: 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 struct operator_id
: public id_base
393 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
395 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
400 /* Identifier that maps to a builtin or internal function code. */
402 struct fn_id
: public id_base
404 fn_id (enum built_in_function fn_
, const char *id_
)
405 : id_base (id_base::FN
, id_
), fn (fn_
) {}
406 fn_id (enum internal_fn fn_
, const char *id_
)
407 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
413 /* Identifier that maps to a user-defined predicate. */
415 struct predicate_id
: public id_base
417 predicate_id (const char *id_
)
418 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
419 vec
<simplify
*> matchers
;
422 /* Identifier that maps to a operator defined by a 'for' directive. */
424 struct user_id
: public id_base
426 user_id (const char *id_
, bool is_oper_list_
= false)
427 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
428 used (false), is_oper_list (is_oper_list_
) {}
429 vec
<id_base
*> substitutes
;
437 is_a_helper
<fn_id
*>::test (id_base
*id
)
439 return id
->kind
== id_base::FN
;
445 is_a_helper
<operator_id
*>::test (id_base
*id
)
447 return id
->kind
== id_base::CODE
;
453 is_a_helper
<predicate_id
*>::test (id_base
*id
)
455 return id
->kind
== id_base::PREDICATE
;
461 is_a_helper
<user_id
*>::test (id_base
*id
)
463 return id
->kind
== id_base::USER
;
466 /* If ID has a pair of consecutive, commutative operands, return the
467 index of the first, otherwise return -1. */
470 commutative_op (id_base
*id
)
472 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
474 if (commutative_tree_code (code
->code
)
475 || commutative_ternary_tree_code (code
->code
))
479 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
491 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
493 int res
= commutative_op (uid
->substitutes
[0]);
496 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
497 if (res
!= commutative_op (uid
->substitutes
[i
]))
504 /* Add a predicate identifier to the hash. */
506 static predicate_id
*
507 add_predicate (const char *id
)
509 predicate_id
*p
= new predicate_id (id
);
510 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
512 fatal ("duplicate id definition");
517 /* Add a tree code identifier to the hash. */
520 add_operator (enum tree_code code
, const char *id
,
521 const char *tcc
, unsigned nargs
)
523 if (strcmp (tcc
, "tcc_unary") != 0
524 && strcmp (tcc
, "tcc_binary") != 0
525 && strcmp (tcc
, "tcc_comparison") != 0
526 && strcmp (tcc
, "tcc_expression") != 0
527 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
528 && strcmp (tcc
, "tcc_reference") != 0
529 /* To have INTEGER_CST and friends as "predicate operators". */
530 && strcmp (tcc
, "tcc_constant") != 0
531 /* And allow CONSTRUCTOR for vector initializers. */
532 && !(code
== CONSTRUCTOR
)
533 /* Allow SSA_NAME as predicate operator. */
534 && !(code
== SSA_NAME
))
536 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
537 if (code
== ADDR_EXPR
)
539 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
540 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
542 fatal ("duplicate id definition");
546 /* Add a built-in or internal function identifier to the hash. ID is
547 the name of its CFN_* enumeration value. */
549 template <typename T
>
551 add_function (T code
, const char *id
)
553 fn_id
*fn
= new fn_id (code
, id
);
554 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
556 fatal ("duplicate id definition");
560 /* Helper for easy comparing ID with tree code CODE. */
563 operator==(id_base
&id
, enum tree_code code
)
565 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
566 return oid
->code
== code
;
570 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
573 get_operator (const char *id
, bool allow_null
= false)
575 if (allow_null
&& strcmp (id
, "null") == 0)
578 id_base
tem (id_base::CODE
, id
);
580 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
583 /* If this is a user-defined identifier track whether it was used. */
584 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
590 bool all_upper
= true;
591 bool all_lower
= true;
592 for (unsigned int i
= 0; id
[i
]; ++i
)
595 else if (ISLOWER (id
[i
]))
599 /* Try in caps with _EXPR appended. */
600 id2
= ACONCAT ((id
, "_EXPR", NULL
));
601 for (unsigned int i
= 0; id2
[i
]; ++i
)
602 id2
[i
] = TOUPPER (id2
[i
]);
604 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
605 /* Try CFN_ instead of IFN_. */
606 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
607 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
608 /* Try prepending CFN_. */
609 id2
= ACONCAT (("CFN_", id
, NULL
));
613 new (&tem
) id_base (id_base::CODE
, id2
);
614 return operators
->find_with_hash (&tem
, tem
.hashval
);
617 /* Return the comparison operators that results if the operands are
618 swapped. This is safe for floating-point. */
621 swap_tree_comparison (operator_id
*p
)
633 return get_operator ("LT_EXPR");
635 return get_operator ("LE_EXPR");
637 return get_operator ("GT_EXPR");
639 return get_operator ("GE_EXPR");
641 return get_operator ("UNLT_EXPR");
643 return get_operator ("UNLE_EXPR");
645 return get_operator ("UNGT_EXPR");
647 return get_operator ("UNGE_EXPR");
653 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
656 /* The AST produced by parsing of the pattern definitions. */
661 /* The base class for operands. */
664 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
665 operand (enum op_type type_
, source_location loc_
)
666 : type (type_
), location (loc_
) {}
668 source_location location
;
669 virtual void gen_transform (FILE *, int, const char *, bool, int,
670 const char *, capture_info
*,
673 { gcc_unreachable (); }
676 /* A predicate operand. Predicates are leafs in the AST. */
678 struct predicate
: public operand
680 predicate (predicate_id
*p_
, source_location loc
)
681 : operand (OP_PREDICATE
, loc
), p (p_
) {}
685 /* An operand that constitutes an expression. Expressions include
686 function calls and user-defined predicate invocations. */
688 struct expr
: public operand
690 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
691 : operand (OP_EXPR
, loc
), operation (operation_
),
692 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
693 is_generic (false), force_single_use (false) {}
695 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
696 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
697 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
698 void append_op (operand
*op
) { ops
.safe_push (op
); }
699 /* The operator and its operands. */
702 /* An explicitely specified type - used exclusively for conversions. */
703 const char *expr_type
;
704 /* Whether the operation is to be applied commutatively. This is
705 later lowered to two separate patterns. */
707 /* Whether the expression is expected to be in GENERIC form. */
709 /* Whether pushing any stmt to the sequence should be conditional
710 on this expression having a single-use. */
711 bool force_single_use
;
712 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
713 const char *, capture_info
*,
714 dt_operand
** = 0, int = 0);
717 /* An operator that is represented by native C code. This is always
718 a leaf operand in the AST. This class is also used to represent
719 the code to be generated for 'if' and 'with' expressions. */
721 struct c_expr
: public operand
723 /* A mapping of an identifier and its replacement. Used to apply
728 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
731 c_expr (cpp_reader
*r_
, source_location loc
,
732 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
733 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
734 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
735 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
736 /* cpplib tokens and state to transform this back to source. */
739 cid_map_t
*capture_ids
;
740 /* The number of statements parsed (well, the number of ';'s). */
742 /* The identifier replacement vector. */
744 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
745 const char *, capture_info
*,
746 dt_operand
** = 0, int = 0);
749 /* A wrapper around another operand that captures its value. */
751 struct capture
: public operand
753 capture (source_location loc
, unsigned where_
, operand
*what_
, bool value_
)
754 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
756 /* Identifier index for the value. */
758 /* Whether in a match of two operands the compare should be for
759 equal values rather than equal atoms (boils down to a type
762 /* The captured value. */
764 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
765 const char *, capture_info
*,
766 dt_operand
** = 0, int = 0);
771 struct if_expr
: public operand
773 if_expr (source_location loc
)
774 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
780 /* with expression. */
782 struct with_expr
: public operand
784 with_expr (source_location loc
)
785 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
793 is_a_helper
<capture
*>::test (operand
*op
)
795 return op
->type
== operand::OP_CAPTURE
;
801 is_a_helper
<predicate
*>::test (operand
*op
)
803 return op
->type
== operand::OP_PREDICATE
;
809 is_a_helper
<c_expr
*>::test (operand
*op
)
811 return op
->type
== operand::OP_C_EXPR
;
817 is_a_helper
<expr
*>::test (operand
*op
)
819 return op
->type
== operand::OP_EXPR
;
825 is_a_helper
<if_expr
*>::test (operand
*op
)
827 return op
->type
== operand::OP_IF
;
833 is_a_helper
<with_expr
*>::test (operand
*op
)
835 return op
->type
== operand::OP_WITH
;
838 /* The main class of a pattern and its transform. This is used to
839 represent both (simplify ...) and (match ...) kinds. The AST
840 duplicates all outer 'if' and 'for' expressions here so each
841 simplify can exist in isolation. */
845 enum simplify_kind
{ SIMPLIFY
, MATCH
};
847 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
848 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
849 cid_map_t
*capture_ids_
)
850 : kind (kind_
), id (id_
), match (match_
), result (result_
),
851 for_vec (for_vec_
), for_subst_vec (vNULL
),
852 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
855 /* ID. This is kept to easily associate related simplifies expanded
856 from the same original one. */
858 /* The expression that is matched against the GENERIC or GIMPLE IL. */
860 /* For a (simplify ...) an expression with ifs and withs with the expression
861 produced when the pattern applies in the leafs.
862 For a (match ...) the leafs are either empty if it is a simple predicate
863 or the single expression specifying the matched operands. */
864 struct operand
*result
;
865 /* Collected 'for' expression operators that have to be replaced
866 in the lowering phase. */
867 vec
<vec
<user_id
*> > for_vec
;
868 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
869 /* A map of capture identifiers to indexes. */
870 cid_map_t
*capture_ids
;
874 /* Debugging routines for dumping the AST. */
877 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
879 if (capture
*c
= dyn_cast
<capture
*> (o
))
881 if (c
->what
&& flattened
== false)
882 print_operand (c
->what
, f
, flattened
);
883 fprintf (f
, "@%u", c
->where
);
886 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
887 fprintf (f
, "%s", p
->p
->id
);
889 else if (is_a
<c_expr
*> (o
))
890 fprintf (f
, "c_expr");
892 else if (expr
*e
= dyn_cast
<expr
*> (o
))
894 if (e
->ops
.length () == 0)
895 fprintf (f
, "%s", e
->operation
->id
);
898 fprintf (f
, "(%s", e
->operation
->id
);
900 if (flattened
== false)
902 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
905 print_operand (e
->ops
[i
], f
, flattened
);
917 print_matches (struct simplify
*s
, FILE *f
= stderr
)
919 fprintf (f
, "for expression: ");
920 print_operand (s
->match
, f
);
927 /* Lowering of commutative operators. */
930 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
931 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
933 if (n
== ops_vector
.length ())
935 vec
<operand
*> xv
= v
.copy ();
936 result
.safe_push (xv
);
940 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
942 v
[n
] = ops_vector
[n
][i
];
943 cartesian_product (ops_vector
, result
, v
, n
+ 1);
947 /* Lower OP to two operands in case it is marked as commutative. */
949 static vec
<operand
*>
950 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
952 vec
<operand
*> ret
= vNULL
;
954 if (capture
*c
= dyn_cast
<capture
*> (op
))
961 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
962 for (unsigned i
= 0; i
< v
.length (); ++i
)
964 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
971 expr
*e
= dyn_cast
<expr
*> (op
);
972 if (!e
|| e
->ops
.length () == 0)
978 vec
< vec
<operand
*> > ops_vector
= vNULL
;
979 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
980 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
982 auto_vec
< vec
<operand
*> > result
;
983 auto_vec
<operand
*> v (e
->ops
.length ());
984 v
.quick_grow_cleared (e
->ops
.length ());
985 cartesian_product (ops_vector
, result
, v
, 0);
988 for (unsigned i
= 0; i
< result
.length (); ++i
)
990 expr
*ne
= new expr (e
);
991 ne
->is_commutative
= false;
992 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
993 ne
->append_op (result
[i
][j
]);
997 if (!e
->is_commutative
)
1000 /* The operation is always binary if it isn't inherently commutative. */
1001 int natural_opno
= commutative_op (e
->operation
);
1002 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1003 for (unsigned i
= 0; i
< result
.length (); ++i
)
1005 expr
*ne
= new expr (e
);
1006 if (operator_id
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
1008 if (comparison_code_p (p
->code
))
1009 ne
->operation
= swap_tree_comparison (p
);
1011 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1013 bool found_compare
= false;
1014 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1015 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1017 if (comparison_code_p (q
->code
)
1018 && swap_tree_comparison (q
) != q
)
1020 found_compare
= true;
1026 user_id
*newop
= new user_id ("<internal>");
1027 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1029 id_base
*subst
= p
->substitutes
[j
];
1030 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1032 if (comparison_code_p (q
->code
))
1033 subst
= swap_tree_comparison (q
);
1035 newop
->substitutes
.safe_push (subst
);
1037 ne
->operation
= newop
;
1038 /* Search for 'p' inside the for vector and push 'newop'
1039 to the same level. */
1040 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1041 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1042 if (for_vec
[j
][k
] == p
)
1044 for_vec
[j
].safe_push (newop
);
1050 ne
->is_commutative
= false;
1051 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1053 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1054 ne
->append_op (result
[i
][old_j
]);
1062 /* Lower operations marked as commutative in the AST of S and push
1063 the resulting patterns to SIMPLIFIERS. */
1066 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1068 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1069 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1071 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1072 s
->for_vec
, s
->capture_ids
);
1073 simplifiers
.safe_push (ns
);
1077 /* Strip conditional conversios using operator OPER from O and its
1078 children if STRIP, else replace them with an unconditional convert. */
1081 lower_opt_convert (operand
*o
, enum tree_code oper
,
1082 enum tree_code to_oper
, bool strip
)
1084 if (capture
*c
= dyn_cast
<capture
*> (o
))
1087 return new capture (c
->location
, c
->where
,
1088 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1094 expr
*e
= dyn_cast
<expr
*> (o
);
1098 if (*e
->operation
== oper
)
1101 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1103 expr
*ne
= new expr (e
);
1104 ne
->operation
= (to_oper
== CONVERT_EXPR
1105 ? get_operator ("CONVERT_EXPR")
1106 : get_operator ("VIEW_CONVERT_EXPR"));
1107 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1111 expr
*ne
= new expr (e
);
1112 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1113 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1118 /* Determine whether O or its children uses the conditional conversion
1122 has_opt_convert (operand
*o
, enum tree_code oper
)
1124 if (capture
*c
= dyn_cast
<capture
*> (o
))
1127 return has_opt_convert (c
->what
, oper
);
1132 expr
*e
= dyn_cast
<expr
*> (o
);
1136 if (*e
->operation
== oper
)
1139 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1140 if (has_opt_convert (e
->ops
[i
], oper
))
1146 /* Lower conditional convert operators in O, expanding it to a vector
1149 static vec
<operand
*>
1150 lower_opt_convert (operand
*o
)
1152 vec
<operand
*> v1
= vNULL
, v2
;
1156 enum tree_code opers
[]
1157 = { CONVERT0
, CONVERT_EXPR
,
1158 CONVERT1
, CONVERT_EXPR
,
1159 CONVERT2
, CONVERT_EXPR
,
1160 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1161 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1162 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1164 /* Conditional converts are lowered to a pattern with the
1165 conversion and one without. The three different conditional
1166 convert codes are lowered separately. */
1168 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1171 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1172 if (has_opt_convert (v1
[j
], opers
[i
]))
1174 v2
.safe_push (lower_opt_convert (v1
[j
],
1175 opers
[i
], opers
[i
+1], false));
1176 v2
.safe_push (lower_opt_convert (v1
[j
],
1177 opers
[i
], opers
[i
+1], true));
1183 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1184 v1
.safe_push (v2
[j
]);
1191 /* Lower conditional convert operators in the AST of S and push
1192 the resulting multiple patterns to SIMPLIFIERS. */
1195 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1197 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1198 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1200 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1201 s
->for_vec
, s
->capture_ids
);
1202 simplifiers
.safe_push (ns
);
1206 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1207 GENERIC and a GIMPLE variant. */
1209 static vec
<operand
*>
1210 lower_cond (operand
*o
)
1212 vec
<operand
*> ro
= vNULL
;
1214 if (capture
*c
= dyn_cast
<capture
*> (o
))
1218 vec
<operand
*> lop
= vNULL
;
1219 lop
= lower_cond (c
->what
);
1221 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1222 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1228 expr
*e
= dyn_cast
<expr
*> (o
);
1229 if (!e
|| e
->ops
.length () == 0)
1235 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1236 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1237 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1239 auto_vec
< vec
<operand
*> > result
;
1240 auto_vec
<operand
*> v (e
->ops
.length ());
1241 v
.quick_grow_cleared (e
->ops
.length ());
1242 cartesian_product (ops_vector
, result
, v
, 0);
1244 for (unsigned i
= 0; i
< result
.length (); ++i
)
1246 expr
*ne
= new expr (e
);
1247 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1248 ne
->append_op (result
[i
][j
]);
1250 /* If this is a COND with a captured expression or an
1251 expression with two operands then also match a GENERIC
1252 form on the compare. */
1253 if ((*e
->operation
== COND_EXPR
1254 || *e
->operation
== VEC_COND_EXPR
)
1255 && ((is_a
<capture
*> (e
->ops
[0])
1256 && as_a
<capture
*> (e
->ops
[0])->what
1257 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1259 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1260 || (is_a
<expr
*> (e
->ops
[0])
1261 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1263 expr
*ne
= new expr (e
);
1264 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1265 ne
->append_op (result
[i
][j
]);
1266 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1268 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1269 expr
*cmp
= new expr (ocmp
);
1270 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1271 cmp
->append_op (ocmp
->ops
[j
]);
1272 cmp
->is_generic
= true;
1273 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1278 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1279 expr
*cmp
= new expr (ocmp
);
1280 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1281 cmp
->append_op (ocmp
->ops
[j
]);
1282 cmp
->is_generic
= true;
1292 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1293 GENERIC and a GIMPLE variant. */
1296 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1298 vec
<operand
*> matchers
= lower_cond (s
->match
);
1299 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1301 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1302 s
->for_vec
, s
->capture_ids
);
1303 simplifiers
.safe_push (ns
);
1307 /* Return true if O refers to ID. */
1310 contains_id (operand
*o
, user_id
*id
)
1312 if (capture
*c
= dyn_cast
<capture
*> (o
))
1313 return c
->what
&& contains_id (c
->what
, id
);
1315 if (expr
*e
= dyn_cast
<expr
*> (o
))
1317 if (e
->operation
== id
)
1319 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1320 if (contains_id (e
->ops
[i
], id
))
1325 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1326 return (contains_id (w
->with
, id
)
1327 || contains_id (w
->subexpr
, id
));
1329 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1330 return (contains_id (ife
->cond
, id
)
1331 || contains_id (ife
->trueexpr
, id
)
1332 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1334 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1335 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1341 /* In AST operand O replace operator ID with operator WITH. */
1344 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1346 /* Deep-copy captures and expressions, replacing operations as
1348 if (capture
*c
= dyn_cast
<capture
*> (o
))
1352 return new capture (c
->location
, c
->where
,
1353 replace_id (c
->what
, id
, with
), c
->value_match
);
1355 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1357 expr
*ne
= new expr (e
);
1358 if (e
->operation
== id
)
1359 ne
->operation
= with
;
1360 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1361 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1364 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1366 with_expr
*nw
= new with_expr (w
->location
);
1367 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1368 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1371 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1373 if_expr
*nife
= new if_expr (ife
->location
);
1374 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1375 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1377 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1381 /* For c_expr we simply record a string replacement table which is
1382 applied at code-generation time. */
1383 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1385 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1386 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1387 return new c_expr (ce
->r
, ce
->location
,
1388 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1394 /* Return true if the binary operator OP is ok for delayed substitution
1395 during for lowering. */
1398 binary_ok (operator_id
*op
)
1405 case TRUNC_DIV_EXPR
:
1407 case FLOOR_DIV_EXPR
:
1408 case ROUND_DIV_EXPR
:
1409 case TRUNC_MOD_EXPR
:
1411 case FLOOR_MOD_EXPR
:
1412 case ROUND_MOD_EXPR
:
1414 case EXACT_DIV_EXPR
:
1426 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1429 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1431 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1432 unsigned worklist_start
= 0;
1433 auto_vec
<simplify
*> worklist
;
1434 worklist
.safe_push (sin
);
1436 /* Lower each recorded for separately, operating on the
1437 set of simplifiers created by the previous one.
1438 Lower inner-to-outer so inner for substitutes can refer
1439 to operators replaced by outer fors. */
1440 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1442 vec
<user_id
*>& ids
= for_vec
[fi
];
1443 unsigned n_ids
= ids
.length ();
1444 unsigned max_n_opers
= 0;
1445 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1446 for (unsigned i
= 0; i
< n_ids
; ++i
)
1448 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1449 max_n_opers
= ids
[i
]->substitutes
.length ();
1450 /* Require that all substitutes are of the same kind so that
1451 if we delay substitution to the result op code generation
1452 can look at the first substitute for deciding things like
1453 types of operands. */
1454 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1455 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1456 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1457 can_delay_subst
= false;
1458 else if (operator_id
*op
1459 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1462 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1463 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1464 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1466 /* Unfortunately we can't just allow all tcc_binary. */
1467 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1468 && strcmp (op0
->tcc
, "tcc_binary") == 0
1472 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1473 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1474 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1475 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1478 can_delay_subst
= false;
1480 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1483 can_delay_subst
= false;
1486 unsigned worklist_end
= worklist
.length ();
1487 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1489 simplify
*s
= worklist
[si
];
1490 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1492 operand
*match_op
= s
->match
;
1493 operand
*result_op
= s
->result
;
1494 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1496 for (unsigned i
= 0; i
< n_ids
; ++i
)
1498 user_id
*id
= ids
[i
];
1499 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1501 && (contains_id (match_op
, id
)
1502 || contains_id (result_op
, id
)))
1507 subst
.quick_push (std::make_pair (id
, oper
));
1508 match_op
= replace_id (match_op
, id
, oper
);
1510 && !can_delay_subst
)
1511 result_op
= replace_id (result_op
, id
, oper
);
1516 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1517 vNULL
, s
->capture_ids
);
1518 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1521 ns
->for_subst_vec
.safe_splice (subst
);
1523 worklist
.safe_push (ns
);
1526 worklist_start
= worklist_end
;
1529 /* Copy out the result from the last for lowering. */
1530 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1531 simplifiers
.safe_push (worklist
[i
]);
1534 /* Lower the AST for everything in SIMPLIFIERS. */
1537 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1539 auto_vec
<simplify
*> out_simplifiers
;
1540 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1541 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1543 simplifiers
.truncate (0);
1544 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1545 lower_commutative (out_simplifiers
[i
], simplifiers
);
1547 out_simplifiers
.truncate (0);
1549 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1550 lower_cond (simplifiers
[i
], out_simplifiers
);
1552 out_simplifiers
.safe_splice (simplifiers
);
1555 simplifiers
.truncate (0);
1556 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1557 lower_for (out_simplifiers
[i
], simplifiers
);
1563 /* The decision tree built for generating GIMPLE and GENERIC pattern
1564 matching code. It represents the 'match' expression of all
1565 simplifies and has those as its leafs. */
1569 /* A hash-map collecting semantically equivalent leafs in the decision
1570 tree for splitting out to separate functions. */
1579 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1582 static inline hashval_t
hash (const key_type
&);
1583 static inline bool equal_keys (const key_type
&, const key_type
&);
1584 template <typename T
> static inline void remove (T
&) {}
1587 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1590 /* Current simplifier ID we are processing during insertion into the
1592 static unsigned current_id
;
1594 /* Decision tree base class, used for DT_NODE. */
1598 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1603 vec
<dt_node
*> kids
;
1607 unsigned total_size
;
1610 dt_node (enum dt_type type_
, dt_node
*parent_
)
1611 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1613 dt_node
*append_node (dt_node
*);
1614 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1615 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1616 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1618 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1620 virtual void gen (FILE *, int, bool) {}
1622 void gen_kids (FILE *, int, bool);
1623 void gen_kids_1 (FILE *, int, bool,
1624 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1625 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1627 void analyze (sinfo_map_t
&);
1630 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1632 struct dt_operand
: public dt_node
1635 dt_operand
*match_dop
;
1640 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1641 dt_operand
*parent_
, unsigned pos_
)
1642 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1643 pos (pos_
), value_match (false), for_id (current_id
) {}
1645 void gen (FILE *, int, bool);
1646 unsigned gen_predicate (FILE *, int, const char *, bool);
1647 unsigned gen_match_op (FILE *, int, const char *, bool);
1649 unsigned gen_gimple_expr (FILE *, int);
1650 unsigned gen_generic_expr (FILE *, int, const char *);
1652 char *get_name (char *);
1653 void gen_opname (char *, unsigned);
1656 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1658 struct dt_simplify
: public dt_node
1661 unsigned pattern_no
;
1662 dt_operand
**indexes
;
1665 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1666 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1667 indexes (indexes_
), info (NULL
) {}
1669 void gen_1 (FILE *, int, bool, operand
*);
1670 void gen (FILE *f
, int, bool);
1676 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1678 return (n
->type
== dt_node::DT_OPERAND
1679 || n
->type
== dt_node::DT_MATCH
1680 || n
->type
== dt_node::DT_TRUE
);
1686 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1688 return n
->type
== dt_node::DT_SIMPLIFY
;
1693 /* A container for the actual decision tree. */
1695 struct decision_tree
1699 void insert (struct simplify
*, unsigned);
1700 void gen (FILE *f
, bool gimple
);
1701 void print (FILE *f
= stderr
);
1703 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1705 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1706 unsigned pos
= 0, dt_node
*parent
= 0);
1707 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1708 static bool cmp_node (dt_node
*, dt_node
*);
1709 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1712 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1715 cmp_operand (operand
*o1
, operand
*o2
)
1717 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1720 if (o1
->type
== operand::OP_PREDICATE
)
1722 predicate
*p1
= as_a
<predicate
*>(o1
);
1723 predicate
*p2
= as_a
<predicate
*>(o2
);
1724 return p1
->p
== p2
->p
;
1726 else if (o1
->type
== operand::OP_EXPR
)
1728 expr
*e1
= static_cast<expr
*>(o1
);
1729 expr
*e2
= static_cast<expr
*>(o2
);
1730 return (e1
->operation
== e2
->operation
1731 && e1
->is_generic
== e2
->is_generic
);
1737 /* Compare two decision tree nodes N1 and N2 and return true if they
1741 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1743 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1749 if (n1
->type
== dt_node::DT_TRUE
)
1752 if (n1
->type
== dt_node::DT_OPERAND
)
1753 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1754 (as_a
<dt_operand
*> (n2
))->op
);
1755 else if (n1
->type
== dt_node::DT_MATCH
)
1756 return (((as_a
<dt_operand
*> (n1
))->match_dop
1757 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1758 && ((as_a
<dt_operand
*> (n1
))->value_match
1759 == (as_a
<dt_operand
*> (n2
))->value_match
));
1763 /* Search OPS for a decision tree node like P and return it if found. */
1766 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1768 /* We can merge adjacent DT_TRUE. */
1769 if (p
->type
== dt_node::DT_TRUE
1771 && ops
.last ()->type
== dt_node::DT_TRUE
)
1773 dt_operand
*true_node
= NULL
;
1774 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1776 /* But we can't merge across DT_TRUE nodes as they serve as
1777 pattern order barriers to make sure that patterns apply
1778 in order of appearance in case multiple matches are possible. */
1779 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1782 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1783 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1785 if (decision_tree::cmp_node (ops
[i
], p
))
1787 /* Unless we are processing the same pattern or the blocking
1788 pattern is before the one we are going to merge with. */
1790 && true_node
->for_id
!= current_id
1791 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1795 source_location p_loc
= 0;
1796 if (p
->type
== dt_node::DT_OPERAND
)
1797 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1798 source_location op_loc
= 0;
1799 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1800 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1801 source_location true_loc
= 0;
1802 true_loc
= true_node
->op
->location
;
1804 "failed to merge decision tree node");
1806 "with the following");
1807 warning_at (true_loc
,
1808 "because of the following which serves as ordering "
1819 /* Append N to the decision tree if it there is not already an existing
1823 dt_node::append_node (dt_node
*n
)
1827 kid
= decision_tree::find_node (kids
, n
);
1832 n
->level
= this->level
+ 1;
1837 /* Append OP to the decision tree. */
1840 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1842 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1843 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1844 return append_node (n
);
1847 /* Append a DT_TRUE decision tree node. */
1850 dt_node::append_true_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_TRUE
, op
, 0, parent_
, pos
);
1854 return append_node (n
);
1857 /* Append a DT_MATCH decision tree node. */
1860 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1861 dt_node
*parent
, unsigned pos
)
1863 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1864 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1865 return append_node (n
);
1868 /* Append S to the decision tree. */
1871 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1872 dt_operand
**indexes
)
1874 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1875 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1876 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1878 warning_at (s
->match
->location
, "duplicate pattern");
1879 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1880 print_operand (s
->match
, stderr
);
1881 fprintf (stderr
, "\n");
1883 return append_node (n
);
1886 /* Analyze the node and its children. */
1889 dt_node::analyze (sinfo_map_t
&map
)
1895 if (type
== DT_SIMPLIFY
)
1897 /* Populate the map of equivalent simplifies. */
1898 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1900 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1915 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1917 kids
[i
]->analyze (map
);
1918 num_leafs
+= kids
[i
]->num_leafs
;
1919 total_size
+= kids
[i
]->total_size
;
1920 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1924 /* Insert O into the decision tree and return the decision tree node found
1928 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1929 unsigned pos
, dt_node
*parent
)
1931 dt_node
*q
, *elm
= 0;
1933 if (capture
*c
= dyn_cast
<capture
*> (o
))
1935 unsigned capt_index
= c
->where
;
1937 if (indexes
[capt_index
] == 0)
1940 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1943 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1946 // get to the last capture
1947 for (operand
*what
= c
->what
;
1948 what
&& is_a
<capture
*> (what
);
1949 c
= as_a
<capture
*> (what
), what
= c
->what
)
1954 unsigned cc_index
= c
->where
;
1955 dt_operand
*match_op
= indexes
[cc_index
];
1957 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1958 elm
= decision_tree::find_node (p
->kids
, &temp
);
1962 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1963 temp
.value_match
= c
->value_match
;
1964 elm
= decision_tree::find_node (p
->kids
, &temp
);
1969 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1970 elm
= decision_tree::find_node (p
->kids
, &temp
);
1974 gcc_assert (elm
->type
== dt_node::DT_TRUE
1975 || elm
->type
== dt_node::DT_OPERAND
1976 || elm
->type
== dt_node::DT_MATCH
);
1977 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1982 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
1983 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1985 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1990 p
= p
->append_op (o
, parent
, pos
);
1993 if (expr
*e
= dyn_cast
<expr
*>(o
))
1995 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1996 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2002 /* Insert S into the decision tree. */
2005 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
2008 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2009 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2010 p
->append_simplify (s
, pattern_no
, indexes
);
2013 /* Debug functions to dump the decision tree. */
2016 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2018 if (p
->type
== dt_node::DT_NODE
)
2019 fprintf (f
, "root");
2023 for (unsigned i
= 0; i
< indent
; i
++)
2026 if (p
->type
== dt_node::DT_OPERAND
)
2028 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2029 print_operand (dop
->op
, f
, true);
2031 else if (p
->type
== dt_node::DT_TRUE
)
2032 fprintf (f
, "true");
2033 else if (p
->type
== dt_node::DT_MATCH
)
2034 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2035 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2037 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2038 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2039 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2040 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2043 if (is_a
<dt_operand
*> (p
))
2044 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2047 fprintf (stderr
, " (%p, %p), %u, %u\n",
2048 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2050 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2051 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2055 decision_tree::print (FILE *f
)
2057 return decision_tree::print_node (root
, f
);
2061 /* For GENERIC we have to take care of wrapping multiple-used
2062 expressions with side-effects in save_expr and preserve side-effects
2063 of expressions with omit_one_operand. Analyze captures in
2064 match, result and with expressions and perform early-outs
2065 on the outermost match expression operands for cases we cannot
2070 capture_info (simplify
*s
, operand
*, bool);
2071 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2072 bool walk_result (operand
*o
, bool, operand
*);
2073 void walk_c_expr (c_expr
*);
2079 bool force_no_side_effects_p
;
2080 bool force_single_use
;
2081 bool cond_expr_cond_p
;
2082 unsigned long toplevel_msk
;
2083 unsigned match_use_count
;
2084 unsigned result_use_count
;
2089 auto_vec
<cinfo
> info
;
2090 unsigned long force_no_side_effects
;
2094 /* Analyze captures in S. */
2096 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2101 if (s
->kind
== simplify::MATCH
)
2103 force_no_side_effects
= -1;
2107 force_no_side_effects
= 0;
2108 info
.safe_grow_cleared (s
->capture_max
+ 1);
2109 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2110 info
[i
].same_as
= i
;
2112 e
= as_a
<expr
*> (s
->match
);
2113 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2114 walk_match (e
->ops
[i
], i
,
2115 (i
!= 0 && *e
->operation
== COND_EXPR
)
2116 || *e
->operation
== TRUTH_ANDIF_EXPR
2117 || *e
->operation
== TRUTH_ORIF_EXPR
,
2119 && (*e
->operation
== COND_EXPR
2120 || *e
->operation
== VEC_COND_EXPR
));
2122 walk_result (s
->result
, false, result
);
2125 /* Analyze captures in the match expression piece O. */
2128 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2129 bool conditional_p
, bool cond_expr_cond_p
)
2131 if (capture
*c
= dyn_cast
<capture
*> (o
))
2133 unsigned where
= c
->where
;
2134 info
[where
].match_use_count
++;
2135 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2136 info
[where
].force_no_side_effects_p
|= conditional_p
;
2137 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2142 /* Recurse to exprs and captures. */
2143 if (is_a
<capture
*> (c
->what
)
2144 || is_a
<expr
*> (c
->what
))
2145 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2146 /* We need to look past multiple captures to find a captured
2147 expression as with conditional converts two captures
2148 can be collapsed onto the same expression. Also collect
2149 what captures capture the same thing. */
2150 while (c
->what
&& is_a
<capture
*> (c
->what
))
2152 c
= as_a
<capture
*> (c
->what
);
2153 if (info
[c
->where
].same_as
!= c
->where
2154 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2155 fatal_at (c
->location
, "cannot handle this collapsed capture");
2156 info
[c
->where
].same_as
= info
[where
].same_as
;
2158 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2161 && (e
= dyn_cast
<expr
*> (c
->what
)))
2163 /* Zero-operand expression captures like ADDR_EXPR@0 are
2164 similar as predicates -- if they are not mentioned in
2165 the result we have to force them to have no side-effects. */
2166 if (e
->ops
.length () != 0)
2167 info
[where
].expr_p
= true;
2168 info
[where
].force_single_use
|= e
->force_single_use
;
2171 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2173 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2175 bool cond_p
= conditional_p
;
2176 bool cond_expr_cond_p
= false;
2177 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2179 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2180 || *e
->operation
== TRUTH_ORIF_EXPR
)
2183 && (*e
->operation
== COND_EXPR
2184 || *e
->operation
== VEC_COND_EXPR
))
2185 cond_expr_cond_p
= true;
2186 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2189 else if (is_a
<predicate
*> (o
))
2191 /* Mark non-captured leafs toplevel arg for checking. */
2192 force_no_side_effects
|= 1 << toplevel_arg
;
2195 warning_at (o
->location
,
2196 "forcing no side-effects on possibly lost leaf");
2202 /* Analyze captures in the result expression piece O. Return true
2203 if RESULT was visited in one of the children. Only visit
2204 non-if/with children if they are rooted on RESULT. */
2207 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2209 if (capture
*c
= dyn_cast
<capture
*> (o
))
2211 unsigned where
= info
[c
->where
].same_as
;
2212 info
[where
].result_use_count
++;
2213 /* If we substitute an expression capture we don't know
2214 which captures this will end up using (well, we don't
2215 compute that). Force the uses to be side-effect free
2216 which means forcing the toplevels that reach the
2217 expression side-effect free. */
2218 if (info
[where
].expr_p
)
2219 force_no_side_effects
|= info
[where
].toplevel_msk
;
2220 /* Mark CSE capture uses as forced to have no side-effects. */
2222 && is_a
<expr
*> (c
->what
))
2224 info
[where
].cse_p
= true;
2225 walk_result (c
->what
, true, result
);
2228 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2230 id_base
*opr
= e
->operation
;
2231 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2232 opr
= uid
->substitutes
[0];
2233 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2235 bool cond_p
= conditional_p
;
2236 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2238 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2239 || *e
->operation
== TRUTH_ORIF_EXPR
)
2241 walk_result (e
->ops
[i
], cond_p
, result
);
2244 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2246 /* 'if' conditions should be all fine. */
2247 if (e
->trueexpr
== result
)
2249 walk_result (e
->trueexpr
, false, result
);
2252 if (e
->falseexpr
== result
)
2254 walk_result (e
->falseexpr
, false, result
);
2258 if (is_a
<if_expr
*> (e
->trueexpr
)
2259 || is_a
<with_expr
*> (e
->trueexpr
))
2260 res
|= walk_result (e
->trueexpr
, false, result
);
2262 && (is_a
<if_expr
*> (e
->falseexpr
)
2263 || is_a
<with_expr
*> (e
->falseexpr
)))
2264 res
|= walk_result (e
->falseexpr
, false, result
);
2267 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2269 bool res
= (e
->subexpr
== result
);
2271 || is_a
<if_expr
*> (e
->subexpr
)
2272 || is_a
<with_expr
*> (e
->subexpr
))
2273 res
|= walk_result (e
->subexpr
, false, result
);
2275 walk_c_expr (e
->with
);
2278 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2286 /* Look for captures in the C expr E. */
2289 capture_info::walk_c_expr (c_expr
*e
)
2291 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2292 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2293 really escape through. */
2294 unsigned p_depth
= 0;
2295 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2297 const cpp_token
*t
= &e
->code
[i
];
2298 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2300 if (t
->type
== CPP_NAME
2301 && (strcmp ((const char *)CPP_HASHNODE
2302 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2303 || strcmp ((const char *)CPP_HASHNODE
2304 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2305 || strcmp ((const char *)CPP_HASHNODE
2306 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2307 || ((id
= get_operator ((const char *)CPP_HASHNODE
2308 (t
->val
.node
.node
)->ident
.str
))
2309 && is_a
<predicate_id
*> (id
)))
2310 && n
->type
== CPP_OPEN_PAREN
)
2312 else if (t
->type
== CPP_CLOSE_PAREN
2315 else if (p_depth
== 0
2316 && t
->type
== CPP_ATSIGN
2317 && (n
->type
== CPP_NUMBER
2318 || n
->type
== CPP_NAME
)
2319 && !(n
->flags
& PREV_WHITE
))
2322 if (n
->type
== CPP_NUMBER
)
2323 id
= (const char *)n
->val
.str
.text
;
2325 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2326 unsigned *where
= e
->capture_ids
->get(id
);
2328 fatal_at (n
, "unknown capture id '%s'", id
);
2329 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2332 warning_at (t
, "capture escapes");
2338 /* Code generation off the decision tree and the refered AST nodes. */
2341 is_conversion (id_base
*op
)
2343 return (*op
== CONVERT_EXPR
2345 || *op
== FLOAT_EXPR
2346 || *op
== FIX_TRUNC_EXPR
2347 || *op
== VIEW_CONVERT_EXPR
);
2350 /* Get the type to be used for generating operand POS of OP from the
2354 get_operand_type (id_base
*op
, unsigned pos
,
2355 const char *in_type
,
2356 const char *expr_type
,
2357 const char *other_oprnd_type
)
2359 /* Generally operands whose type does not match the type of the
2360 expression generated need to know their types but match and
2361 thus can fall back to 'other_oprnd_type'. */
2362 if (is_conversion (op
))
2363 return other_oprnd_type
;
2364 else if (*op
== REALPART_EXPR
2365 || *op
== IMAGPART_EXPR
)
2366 return other_oprnd_type
;
2367 else if (is_a
<operator_id
*> (op
)
2368 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2369 return other_oprnd_type
;
2370 else if (*op
== COND_EXPR
2372 return "boolean_type_node";
2375 /* Otherwise all types should match - choose one in order of
2382 return other_oprnd_type
;
2386 /* Generate transform code for an expression. */
2389 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2390 int depth
, const char *in_type
, capture_info
*cinfo
,
2391 dt_operand
**indexes
, int)
2393 id_base
*opr
= operation
;
2394 /* When we delay operator substituting during lowering of fors we
2395 make sure that for code-gen purposes the effects of each substitute
2396 are the same. Thus just look at that. */
2397 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2398 opr
= uid
->substitutes
[0];
2400 bool conversion_p
= is_conversion (opr
);
2401 const char *type
= expr_type
;
2404 /* If there was a type specification in the pattern use it. */
2406 else if (conversion_p
)
2407 /* For conversions we need to build the expression using the
2408 outer type passed in. */
2410 else if (*opr
== REALPART_EXPR
2411 || *opr
== IMAGPART_EXPR
)
2413 /* __real and __imag use the component type of its operand. */
2414 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2417 else if (is_a
<operator_id
*> (opr
)
2418 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2420 /* comparisons use boolean_type_node (or what gets in), but
2421 their operands need to figure out the types themselves. */
2426 sprintf (optype
, "boolean_type_node");
2431 else if (*opr
== COND_EXPR
2432 || *opr
== VEC_COND_EXPR
)
2434 /* Conditions are of the same type as their first alternative. */
2435 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2440 /* Other operations are of the same type as their first operand. */
2441 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2445 fatal_at (location
, "cannot determine type of operand");
2447 fprintf_indent (f
, indent
, "{\n");
2449 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2451 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2452 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2455 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2457 = get_operand_type (opr
, i
, in_type
, expr_type
,
2458 i
== 0 ? NULL
: op0type
);
2459 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2462 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2465 const char *opr_name
;
2466 if (*operation
== CONVERT_EXPR
)
2467 opr_name
= "NOP_EXPR";
2469 opr_name
= operation
->id
;
2473 if (*opr
== CONVERT_EXPR
)
2475 fprintf_indent (f
, indent
,
2476 "if (%s != TREE_TYPE (ops%d[0])\n",
2478 fprintf_indent (f
, indent
,
2479 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2481 fprintf_indent (f
, indent
+ 2, "{\n");
2484 /* ??? Building a stmt can fail for various reasons here, seq being
2485 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2486 So if we fail here we should continue matching other patterns. */
2487 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2488 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2489 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2490 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2491 i
== ops
.length () - 1 ? " };\n" : ", ");
2492 fprintf_indent (f
, indent
,
2493 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2494 ops
.length (), type
);
2495 fprintf_indent (f
, indent
,
2496 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2498 fprintf_indent (f
, indent
,
2499 "if (!res) return false;\n");
2500 if (*opr
== CONVERT_EXPR
)
2503 fprintf_indent (f
, indent
, " }\n");
2504 fprintf_indent (f
, indent
, "else\n");
2505 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2510 if (*opr
== CONVERT_EXPR
)
2512 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2516 if (opr
->kind
== id_base::CODE
)
2517 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2518 ops
.length(), opr_name
, type
);
2521 fprintf_indent (f
, indent
, "{\n");
2522 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2523 "%s, %s, %d", opr_name
, type
, ops
.length());
2525 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2526 fprintf (f
, ", ops%d[%u]", depth
, i
);
2527 fprintf (f
, ");\n");
2528 if (opr
->kind
!= id_base::CODE
)
2530 fprintf_indent (f
, indent
, " if (!res)\n");
2531 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2532 fprintf_indent (f
, indent
, "}\n");
2534 if (*opr
== CONVERT_EXPR
)
2537 fprintf_indent (f
, indent
, "else\n");
2538 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2541 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2543 fprintf_indent (f
, indent
, "}\n");
2546 /* Generate code for a c_expr which is either the expression inside
2547 an if statement or a sequence of statements which computes a
2548 result to be stored to DEST. */
2551 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2552 bool, int, const char *, capture_info
*,
2555 if (dest
&& nr_stmts
== 1)
2556 fprintf_indent (f
, indent
, "%s = ", dest
);
2558 unsigned stmt_nr
= 1;
2559 for (unsigned i
= 0; i
< code
.length (); ++i
)
2561 const cpp_token
*token
= &code
[i
];
2563 /* Replace captures for code-gen. */
2564 if (token
->type
== CPP_ATSIGN
)
2566 const cpp_token
*n
= &code
[i
+1];
2567 if ((n
->type
== CPP_NUMBER
2568 || n
->type
== CPP_NAME
)
2569 && !(n
->flags
& PREV_WHITE
))
2571 if (token
->flags
& PREV_WHITE
)
2574 if (n
->type
== CPP_NUMBER
)
2575 id
= (const char *)n
->val
.str
.text
;
2577 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2578 unsigned *cid
= capture_ids
->get (id
);
2580 fatal_at (token
, "unknown capture id");
2581 fprintf (f
, "captures[%u]", *cid
);
2587 if (token
->flags
& PREV_WHITE
)
2590 if (token
->type
== CPP_NAME
)
2592 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2594 for (j
= 0; j
< ids
.length (); ++j
)
2596 if (strcmp (id
, ids
[j
].id
) == 0)
2598 fprintf (f
, "%s", ids
[j
].oper
);
2602 if (j
< ids
.length ())
2606 /* Output the token as string. */
2607 char *tk
= (char *)cpp_token_as_text (r
, token
);
2610 if (token
->type
== CPP_SEMICOLON
)
2614 if (dest
&& stmt_nr
== nr_stmts
)
2615 fprintf_indent (f
, indent
, "%s = ", dest
);
2620 /* Generate transform code for a capture. */
2623 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2624 int depth
, const char *in_type
, capture_info
*cinfo
,
2625 dt_operand
**indexes
, int cond_handling
)
2627 if (what
&& is_a
<expr
*> (what
))
2629 if (indexes
[where
] == 0)
2632 sprintf (buf
, "captures[%u]", where
);
2633 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2638 /* If in GENERIC some capture is used multiple times, unshare it except
2639 when emitting the last use. */
2641 && cinfo
->info
.exists ()
2642 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2644 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2646 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2649 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2651 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2652 with substituting a capture of that. */
2654 && cond_handling
!= 0
2655 && cinfo
->info
[where
].cond_expr_cond_p
)
2657 /* If substituting into a cond_expr condition, unshare. */
2658 if (cond_handling
== 1)
2659 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2660 /* If substituting elsewhere we might need to decompose it. */
2661 else if (cond_handling
== 2)
2663 /* ??? Returning false here will also not allow any other patterns
2664 to match unless this generator was split out. */
2665 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2666 fprintf_indent (f
, indent
, " {\n");
2667 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2668 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2670 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2671 " TREE_OPERAND (%s, 1));\n",
2672 dest
, dest
, dest
, dest
, dest
);
2673 fprintf_indent (f
, indent
, " }\n");
2678 /* Return the name of the operand representing the decision tree node.
2679 Use NAME as space to generate it. */
2682 dt_operand::get_name (char *name
)
2685 sprintf (name
, "t");
2686 else if (parent
->level
== 1)
2687 sprintf (name
, "op%u", pos
);
2688 else if (parent
->type
== dt_node::DT_MATCH
)
2689 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2691 sprintf (name
, "o%u%u", parent
->level
, pos
);
2695 /* Fill NAME with the operand name at position POS. */
2698 dt_operand::gen_opname (char *name
, unsigned pos
)
2701 sprintf (name
, "op%u", pos
);
2703 sprintf (name
, "o%u%u", level
, pos
);
2706 /* Generate matching code for the decision tree operand which is
2710 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2712 predicate
*p
= as_a
<predicate
*> (op
);
2714 if (p
->p
->matchers
.exists ())
2716 /* If this is a predicate generated from a pattern mangle its
2717 name and pass on the valueize hook. */
2719 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2722 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2725 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2726 fprintf_indent (f
, indent
+ 2, "{\n");
2730 /* Generate matching code for the decision tree operand which is
2734 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2736 char match_opname
[20];
2737 match_dop
->get_name (match_opname
);
2739 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2740 opname
, match_opname
, opname
, match_opname
);
2742 fprintf_indent (f
, indent
, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
2743 "&& types_match (%s, %s)))\n",
2744 opname
, match_opname
, opname
, match_opname
,
2745 opname
, match_opname
);
2746 fprintf_indent (f
, indent
+ 2, "{\n");
2750 /* Generate GIMPLE matching code for the decision tree operand. */
2753 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2755 expr
*e
= static_cast<expr
*> (op
);
2756 id_base
*id
= e
->operation
;
2757 unsigned n_ops
= e
->ops
.length ();
2758 unsigned n_braces
= 0;
2760 for (unsigned i
= 0; i
< n_ops
; ++i
)
2762 char child_opname
[20];
2763 gen_opname (child_opname
, i
);
2765 if (id
->kind
== id_base::CODE
)
2768 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2769 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2771 /* ??? If this is a memory operation we can't (and should not)
2772 match this. The only sensible operand types are
2773 SSA names and invariants. */
2778 fprintf_indent (f
, indent
,
2779 "tree %s = TREE_OPERAND (%s, %i);\n",
2780 child_opname
, opname
, i
);
2783 fprintf_indent (f
, indent
,
2784 "tree %s = TREE_OPERAND "
2785 "(gimple_assign_rhs1 (def), %i);\n",
2787 fprintf_indent (f
, indent
,
2788 "if ((TREE_CODE (%s) == SSA_NAME\n",
2790 fprintf_indent (f
, indent
,
2791 " || is_gimple_min_invariant (%s)))\n",
2793 fprintf_indent (f
, indent
,
2797 fprintf_indent (f
, indent
,
2798 "%s = do_valueize (valueize, %s);\n",
2799 child_opname
, child_opname
);
2803 fprintf_indent (f
, indent
,
2804 "tree %s = gimple_assign_rhs%u (def);\n",
2805 child_opname
, i
+ 1);
2808 fprintf_indent (f
, indent
,
2809 "tree %s = gimple_call_arg (def, %u);\n",
2811 fprintf_indent (f
, indent
,
2812 "%s = do_valueize (valueize, %s);\n",
2813 child_opname
, child_opname
);
2815 /* While the toplevel operands are canonicalized by the caller
2816 after valueizing operands of sub-expressions we have to
2817 re-canonicalize operand order. */
2818 int opno
= commutative_op (id
);
2821 char child_opname0
[20], child_opname1
[20];
2822 gen_opname (child_opname0
, opno
);
2823 gen_opname (child_opname1
, opno
+ 1);
2824 fprintf_indent (f
, indent
,
2825 "if (tree_swap_operands_p (%s, %s))\n",
2826 child_opname0
, child_opname1
);
2827 fprintf_indent (f
, indent
,
2828 " std::swap (%s, %s);\n",
2829 child_opname0
, child_opname1
);
2835 /* Generate GENERIC matching code for the decision tree operand. */
2838 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2840 expr
*e
= static_cast<expr
*> (op
);
2841 unsigned n_ops
= e
->ops
.length ();
2843 for (unsigned i
= 0; i
< n_ops
; ++i
)
2845 char child_opname
[20];
2846 gen_opname (child_opname
, i
);
2848 if (e
->operation
->kind
== id_base::CODE
)
2849 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2850 child_opname
, opname
, i
);
2852 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2853 child_opname
, opname
, i
);
2859 /* Generate matching code for the children of the decision tree node. */
2862 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2864 auto_vec
<dt_operand
*> gimple_exprs
;
2865 auto_vec
<dt_operand
*> generic_exprs
;
2866 auto_vec
<dt_operand
*> fns
;
2867 auto_vec
<dt_operand
*> generic_fns
;
2868 auto_vec
<dt_operand
*> preds
;
2869 auto_vec
<dt_node
*> others
;
2871 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2873 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2875 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2876 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2878 if (e
->ops
.length () == 0
2879 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2880 generic_exprs
.safe_push (op
);
2881 else if (e
->operation
->kind
== id_base::FN
)
2886 generic_fns
.safe_push (op
);
2888 else if (e
->operation
->kind
== id_base::PREDICATE
)
2889 preds
.safe_push (op
);
2892 if (gimple
&& !e
->is_generic
)
2893 gimple_exprs
.safe_push (op
);
2895 generic_exprs
.safe_push (op
);
2898 else if (op
->op
->type
== operand::OP_PREDICATE
)
2899 others
.safe_push (kids
[i
]);
2903 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2904 others
.safe_push (kids
[i
]);
2905 else if (kids
[i
]->type
== dt_node::DT_MATCH
2906 || kids
[i
]->type
== dt_node::DT_TRUE
)
2908 /* A DT_TRUE operand serves as a barrier - generate code now
2909 for what we have collected sofar.
2910 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2911 dependent matches to get out-of-order. Generate code now
2912 for what we have collected sofar. */
2913 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2914 fns
, generic_fns
, preds
, others
);
2915 /* And output the true operand itself. */
2916 kids
[i
]->gen (f
, indent
, gimple
);
2917 gimple_exprs
.truncate (0);
2918 generic_exprs
.truncate (0);
2920 generic_fns
.truncate (0);
2922 others
.truncate (0);
2928 /* Generate code for the remains. */
2929 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2930 fns
, generic_fns
, preds
, others
);
2933 /* Generate matching code for the children of the decision tree node. */
2936 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2937 vec
<dt_operand
*> gimple_exprs
,
2938 vec
<dt_operand
*> generic_exprs
,
2939 vec
<dt_operand
*> fns
,
2940 vec
<dt_operand
*> generic_fns
,
2941 vec
<dt_operand
*> preds
,
2942 vec
<dt_node
*> others
)
2945 char *kid_opname
= buf
;
2947 unsigned exprs_len
= gimple_exprs
.length ();
2948 unsigned gexprs_len
= generic_exprs
.length ();
2949 unsigned fns_len
= fns
.length ();
2950 unsigned gfns_len
= generic_fns
.length ();
2952 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2955 gimple_exprs
[0]->get_name (kid_opname
);
2957 fns
[0]->get_name (kid_opname
);
2959 generic_fns
[0]->get_name (kid_opname
);
2961 generic_exprs
[0]->get_name (kid_opname
);
2963 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2964 fprintf_indent (f
, indent
, " {\n");
2968 if (exprs_len
|| fns_len
)
2970 fprintf_indent (f
, indent
,
2971 "case SSA_NAME:\n");
2972 fprintf_indent (f
, indent
,
2973 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2975 fprintf_indent (f
, indent
,
2980 fprintf_indent (f
, indent
,
2981 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2982 fprintf_indent (f
, indent
,
2983 " switch (gimple_assign_rhs_code (def))\n");
2985 fprintf_indent (f
, indent
, "{\n");
2986 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2988 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2989 id_base
*op
= e
->operation
;
2990 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2991 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2993 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2994 fprintf_indent (f
, indent
, " {\n");
2995 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2996 fprintf_indent (f
, indent
, " break;\n");
2997 fprintf_indent (f
, indent
, " }\n");
2999 fprintf_indent (f
, indent
, "default:;\n");
3000 fprintf_indent (f
, indent
, "}\n");
3006 fprintf_indent (f
, indent
,
3007 "%sif (gcall *def = dyn_cast <gcall *>"
3009 exprs_len
? "else " : "");
3010 fprintf_indent (f
, indent
,
3011 " switch (gimple_call_combined_fn (def))\n");
3014 fprintf_indent (f
, indent
, "{\n");
3015 for (unsigned i
= 0; i
< fns_len
; ++i
)
3017 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3018 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3019 fprintf_indent (f
, indent
, " {\n");
3020 fns
[i
]->gen (f
, indent
+ 4, true);
3021 fprintf_indent (f
, indent
, " break;\n");
3022 fprintf_indent (f
, indent
, " }\n");
3025 fprintf_indent (f
, indent
, "default:;\n");
3026 fprintf_indent (f
, indent
, "}\n");
3031 fprintf_indent (f
, indent
, " }\n");
3032 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3033 here rather than in the next loop. */
3034 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3036 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3037 id_base
*op
= e
->operation
;
3038 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3040 fprintf_indent (f
, indent
+ 4, "{\n");
3041 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
3042 fprintf_indent (f
, indent
+ 4, "}\n");
3046 fprintf_indent (f
, indent
, " break;\n");
3049 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3051 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3052 id_base
*op
= e
->operation
;
3053 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3054 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3055 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3056 /* Already handled above. */
3059 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3060 fprintf_indent (f
, indent
, " {\n");
3061 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
3062 fprintf_indent (f
, indent
, " break;\n");
3063 fprintf_indent (f
, indent
, " }\n");
3068 fprintf_indent (f
, indent
,
3069 "case CALL_EXPR:\n");
3070 fprintf_indent (f
, indent
,
3071 " switch (get_call_combined_fn (%s))\n",
3073 fprintf_indent (f
, indent
,
3077 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3079 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3080 gcc_assert (e
->operation
->kind
== id_base::FN
);
3082 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3083 fprintf_indent (f
, indent
, " {\n");
3084 generic_fns
[j
]->gen (f
, indent
+ 4, false);
3085 fprintf_indent (f
, indent
, " break;\n");
3086 fprintf_indent (f
, indent
, " }\n");
3088 fprintf_indent (f
, indent
, "default:;\n");
3091 fprintf_indent (f
, indent
, " }\n");
3092 fprintf_indent (f
, indent
, " break;\n");
3095 /* Close switch (TREE_CODE ()). */
3096 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3099 fprintf_indent (f
, indent
, " default:;\n");
3100 fprintf_indent (f
, indent
, " }\n");
3103 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3105 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3106 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3107 preds
[i
]->get_name (kid_opname
);
3108 fprintf_indent (f
, indent
, "{\n");
3110 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3111 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3112 gimple
? "gimple" : "tree",
3113 p
->id
, kid_opname
, kid_opname
,
3114 gimple
? ", valueize" : "");
3115 fprintf_indent (f
, indent
, " {\n");
3116 for (int j
= 0; j
< p
->nargs
; ++j
)
3118 char child_opname
[20];
3119 preds
[i
]->gen_opname (child_opname
, j
);
3120 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3121 child_opname
, kid_opname
, j
);
3123 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3126 fprintf_indent (f
, indent
, "}\n");
3129 for (unsigned i
= 0; i
< others
.length (); ++i
)
3130 others
[i
]->gen (f
, indent
, gimple
);
3133 /* Generate matching code for the decision tree operand. */
3136 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3141 unsigned n_braces
= 0;
3143 if (type
== DT_OPERAND
)
3146 case operand::OP_PREDICATE
:
3147 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3150 case operand::OP_EXPR
:
3152 n_braces
= gen_gimple_expr (f
, indent
);
3154 n_braces
= gen_generic_expr (f
, indent
, opname
);
3160 else if (type
== DT_TRUE
)
3162 else if (type
== DT_MATCH
)
3163 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3167 indent
+= 4 * n_braces
;
3168 gen_kids (f
, indent
, gimple
);
3170 for (unsigned i
= 0; i
< n_braces
; ++i
)
3175 fprintf_indent (f
, indent
, " }\n");
3180 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3181 step of a '(simplify ...)' or '(match ...)'. This handles everything
3182 that is not part of the decision tree (simplify->match).
3183 Main recursive worker. */
3186 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3190 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3192 fprintf_indent (f
, indent
, "{\n");
3194 output_line_directive (f
, w
->location
);
3195 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3196 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3198 fprintf_indent (f
, indent
, "}\n");
3201 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3203 output_line_directive (f
, ife
->location
);
3204 fprintf_indent (f
, indent
, "if (");
3205 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3207 fprintf_indent (f
, indent
+ 2, "{\n");
3209 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3211 fprintf_indent (f
, indent
+ 2, "}\n");
3214 fprintf_indent (f
, indent
, "else\n");
3215 fprintf_indent (f
, indent
+ 2, "{\n");
3217 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3219 fprintf_indent (f
, indent
+ 2, "}\n");
3225 /* Analyze captures and perform early-outs on the incoming arguments
3226 that cover cases we cannot handle. */
3227 capture_info
cinfo (s
, result
, gimple
);
3228 if (s
->kind
== simplify::SIMPLIFY
)
3232 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3233 if (cinfo
.force_no_side_effects
& (1 << i
))
3235 fprintf_indent (f
, indent
,
3236 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3239 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3240 "forcing toplevel operand to have no "
3243 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3244 if (cinfo
.info
[i
].cse_p
)
3246 else if (cinfo
.info
[i
].force_no_side_effects_p
3247 && (cinfo
.info
[i
].toplevel_msk
3248 & cinfo
.force_no_side_effects
) == 0)
3250 fprintf_indent (f
, indent
,
3251 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3252 "return NULL_TREE;\n", i
);
3254 warning_at (cinfo
.info
[i
].c
->location
,
3255 "forcing captured operand to have no "
3258 else if ((cinfo
.info
[i
].toplevel_msk
3259 & cinfo
.force_no_side_effects
) != 0)
3260 /* Mark capture as having no side-effects if we had to verify
3261 that via forced toplevel operand checks. */
3262 cinfo
.info
[i
].force_no_side_effects_p
= true;
3266 /* Force single-use restriction by only allowing simple
3267 results via setting seq to NULL. */
3268 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3269 bool first_p
= true;
3270 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3271 if (cinfo
.info
[i
].force_single_use
)
3275 fprintf_indent (f
, indent
, "if (lseq\n");
3276 fprintf_indent (f
, indent
, " && (");
3282 fprintf_indent (f
, indent
, " || ");
3284 fprintf (f
, "!single_use (captures[%d])", i
);
3288 fprintf (f
, "))\n");
3289 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3294 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_FOLDING)) "
3295 "fprintf (dump_file, \"Applying pattern ");
3296 output_line_directive (f
,
3297 result
? result
->location
: s
->match
->location
, true);
3298 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3302 /* If there is no result then this is a predicate implementation. */
3303 fprintf_indent (f
, indent
, "return true;\n");
3307 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3308 in outermost position). */
3309 if (result
->type
== operand::OP_EXPR
3310 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3311 result
= as_a
<expr
*> (result
)->ops
[0];
3312 if (result
->type
== operand::OP_EXPR
)
3314 expr
*e
= as_a
<expr
*> (result
);
3315 id_base
*opr
= e
->operation
;
3316 bool is_predicate
= false;
3317 /* When we delay operator substituting during lowering of fors we
3318 make sure that for code-gen purposes the effects of each substitute
3319 are the same. Thus just look at that. */
3320 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3321 opr
= uid
->substitutes
[0];
3322 else if (is_a
<predicate_id
*> (opr
))
3323 is_predicate
= true;
3325 fprintf_indent (f
, indent
, "*res_code = %s;\n",
3326 *e
->operation
== CONVERT_EXPR
3327 ? "NOP_EXPR" : e
->operation
->id
);
3328 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3331 snprintf (dest
, 32, "res_ops[%d]", j
);
3333 = get_operand_type (opr
, j
,
3334 "type", e
->expr_type
,
3335 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
3336 /* We need to expand GENERIC conditions we captured from
3337 COND_EXPRs and we need to unshare them when substituting
3339 int cond_handling
= 0;
3341 cond_handling
= ((*opr
== COND_EXPR
3342 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3343 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3344 &cinfo
, indexes
, cond_handling
);
3347 /* Re-fold the toplevel result. It's basically an embedded
3348 gimple_build w/o actually building the stmt. */
3350 fprintf_indent (f
, indent
,
3351 "gimple_resimplify%d (lseq, res_code, type, "
3352 "res_ops, valueize);\n", e
->ops
.length ());
3354 else if (result
->type
== operand::OP_CAPTURE
3355 || result
->type
== operand::OP_C_EXPR
)
3357 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
3359 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
3360 if (is_a
<capture
*> (result
)
3361 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3363 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3364 with substituting a capture of that. */
3365 fprintf_indent (f
, indent
,
3366 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3367 fprintf_indent (f
, indent
,
3369 fprintf_indent (f
, indent
,
3370 " tree tem = res_ops[0];\n");
3371 fprintf_indent (f
, indent
,
3372 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3373 fprintf_indent (f
, indent
,
3374 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3375 fprintf_indent (f
, indent
,
3381 fprintf_indent (f
, indent
, "return true;\n");
3385 bool is_predicate
= false;
3386 if (result
->type
== operand::OP_EXPR
)
3388 expr
*e
= as_a
<expr
*> (result
);
3389 id_base
*opr
= e
->operation
;
3390 /* When we delay operator substituting during lowering of fors we
3391 make sure that for code-gen purposes the effects of each substitute
3392 are the same. Thus just look at that. */
3393 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3394 opr
= uid
->substitutes
[0];
3395 else if (is_a
<predicate_id
*> (opr
))
3396 is_predicate
= true;
3397 /* Search for captures used multiple times in the result expression
3398 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3399 original expression. */
3401 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3403 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3404 || cinfo
.info
[i
].cse_p
)
3406 if (cinfo
.info
[i
].result_use_count
3407 > cinfo
.info
[i
].match_use_count
)
3408 fprintf_indent (f
, indent
,
3409 "if (! tree_invariant_p (captures[%d])) "
3410 "return NULL_TREE;\n", i
);
3412 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3416 snprintf (dest
, 32, "res_ops[%d]", j
);
3419 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3420 snprintf (dest
, 32, "res_op%d", j
);
3423 = get_operand_type (opr
, j
,
3424 "type", e
->expr_type
,
3426 ? NULL
: "TREE_TYPE (res_op0)");
3427 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3431 fprintf_indent (f
, indent
, "return true;\n");
3434 fprintf_indent (f
, indent
, "tree res;\n");
3435 /* Re-fold the toplevel result. Use non_lvalue to
3436 build NON_LVALUE_EXPRs so they get properly
3437 ignored when in GIMPLE form. */
3438 if (*opr
== NON_LVALUE_EXPR
)
3439 fprintf_indent (f
, indent
,
3440 "res = non_lvalue_loc (loc, res_op0);\n");
3443 if (is_a
<operator_id
*> (opr
))
3444 fprintf_indent (f
, indent
,
3445 "res = fold_build%d_loc (loc, %s, type",
3447 *e
->operation
== CONVERT_EXPR
3448 ? "NOP_EXPR" : e
->operation
->id
);
3450 fprintf_indent (f
, indent
,
3451 "res = maybe_build_call_expr_loc (loc, "
3452 "%s, type, %d", e
->operation
->id
,
3454 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3455 fprintf (f
, ", res_op%d", j
);
3456 fprintf (f
, ");\n");
3457 if (!is_a
<operator_id
*> (opr
))
3459 fprintf_indent (f
, indent
, "if (!res)\n");
3460 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3465 else if (result
->type
== operand::OP_CAPTURE
3466 || result
->type
== operand::OP_C_EXPR
)
3469 fprintf_indent (f
, indent
, "tree res;\n");
3470 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3477 /* Search for captures not used in the result expression and dependent
3478 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3479 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3481 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3483 if (!cinfo
.info
[i
].force_no_side_effects_p
3484 && !cinfo
.info
[i
].expr_p
3485 && cinfo
.info
[i
].result_use_count
== 0)
3487 fprintf_indent (f
, indent
,
3488 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3490 fprintf_indent (f
, indent
+ 2,
3491 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3492 "fold_ignored_result (captures[%d]), res);\n",
3496 fprintf_indent (f
, indent
, "return res;\n");
3501 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3502 step of a '(simplify ...)' or '(match ...)'. This handles everything
3503 that is not part of the decision tree (simplify->match). */
3506 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3508 fprintf_indent (f
, indent
, "{\n");
3510 output_line_directive (f
,
3511 s
->result
? s
->result
->location
: s
->match
->location
);
3512 if (s
->capture_max
>= 0)
3515 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3516 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3518 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3522 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3524 fprintf (f
, " };\n");
3527 /* If we have a split-out function for the actual transform, call it. */
3528 if (info
&& info
->fname
)
3532 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3533 "valueize, type, captures", info
->fname
);
3534 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3535 if (s
->for_subst_vec
[i
].first
->used
)
3536 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3537 fprintf (f
, "))\n");
3538 fprintf_indent (f
, indent
, " return true;\n");
3542 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3544 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3545 fprintf (f
, ", op%d", i
);
3546 fprintf (f
, ", captures");
3547 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3549 if (s
->for_subst_vec
[i
].first
->used
)
3550 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3552 fprintf (f
, ");\n");
3553 fprintf_indent (f
, indent
, "if (res) return res;\n");
3558 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3560 if (! s
->for_subst_vec
[i
].first
->used
)
3562 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3563 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3564 s
->for_subst_vec
[i
].first
->id
,
3565 s
->for_subst_vec
[i
].second
->id
);
3566 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3567 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3568 s
->for_subst_vec
[i
].first
->id
,
3569 s
->for_subst_vec
[i
].second
->id
);
3573 gen_1 (f
, indent
, gimple
, s
->result
);
3577 fprintf_indent (f
, indent
, "}\n");
3581 /* Hash function for finding equivalent transforms. */
3584 sinfo_hashmap_traits::hash (const key_type
&v
)
3586 /* Only bother to compare those originating from the same source pattern. */
3587 return v
->s
->result
->location
;
3590 /* Compare function for finding equivalent transforms. */
3593 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3595 if (o1
->type
!= o2
->type
)
3600 case operand::OP_IF
:
3602 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3603 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3604 /* ??? Properly compare c-exprs. */
3605 if (if1
->cond
!= if2
->cond
)
3607 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3609 if (if1
->falseexpr
!= if2
->falseexpr
3611 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3615 case operand::OP_WITH
:
3617 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3618 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3619 if (with1
->with
!= with2
->with
)
3621 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3626 /* We've hit a result. Time to compare capture-infos - this is required
3627 in addition to the conservative pointer-equivalency of the result IL. */
3628 capture_info
cinfo1 (s1
, o1
, true);
3629 capture_info
cinfo2 (s2
, o2
, true);
3631 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3632 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3635 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3637 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3638 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3639 || (cinfo1
.info
[i
].force_no_side_effects_p
3640 != cinfo2
.info
[i
].force_no_side_effects_p
)
3641 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3642 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3643 /* toplevel_msk is an optimization */
3644 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3645 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3646 /* the pointer back to the capture is for diagnostics only */)
3650 /* ??? Deep-compare the actual result. */
3655 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3656 const key_type
&candidate
)
3658 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3662 /* Main entry to generate code for matching GIMPLE IL off the decision
3666 decision_tree::gen (FILE *f
, bool gimple
)
3672 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3673 "a total number of %u nodes\n",
3674 gimple
? "GIMPLE" : "GENERIC",
3675 root
->num_leafs
, root
->max_level
, root
->total_size
);
3677 /* First split out the transform part of equal leafs. */
3680 for (sinfo_map_t::iterator iter
= si
.begin ();
3681 iter
!= si
.end (); ++iter
)
3683 sinfo
*s
= (*iter
).second
;
3684 /* Do not split out single uses. */
3691 fprintf (stderr
, "found %u uses of", s
->cnt
);
3692 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3695 /* Generate a split out function with the leaf transform code. */
3696 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3699 fprintf (f
, "\nstatic bool\n"
3700 "%s (code_helper *res_code, tree *res_ops,\n"
3701 " gimple_seq *seq, tree (*valueize)(tree) "
3702 "ATTRIBUTE_UNUSED,\n"
3703 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3708 fprintf (f
, "\nstatic tree\n"
3709 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3710 (*iter
).second
->fname
);
3711 for (unsigned i
= 0;
3712 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3713 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3714 fprintf (f
, " tree *captures\n");
3716 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3718 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3720 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3721 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3722 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3723 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3724 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3725 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3728 fprintf (f
, ")\n{\n");
3729 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3731 fprintf (f
, " return false;\n");
3733 fprintf (f
, " return NULL_TREE;\n");
3736 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3738 for (unsigned n
= 1; n
<= 3; ++n
)
3740 /* First generate split-out functions. */
3741 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3743 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3744 expr
*e
= static_cast<expr
*>(dop
->op
);
3745 if (e
->ops
.length () != n
3746 /* Builtin simplifications are somewhat premature on
3747 GENERIC. The following drops patterns with outermost
3748 calls. It's easy to emit overloads for function code
3749 though if necessary. */
3751 && e
->operation
->kind
!= id_base::CODE
))
3755 fprintf (f
, "\nstatic bool\n"
3756 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3757 " gimple_seq *seq, tree (*valueize)(tree) "
3758 "ATTRIBUTE_UNUSED,\n"
3759 " code_helper ARG_UNUSED (code), tree "
3760 "ARG_UNUSED (type)\n",
3763 fprintf (f
, "\nstatic tree\n"
3764 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3765 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3767 for (unsigned i
= 0; i
< n
; ++i
)
3768 fprintf (f
, ", tree op%d", i
);
3771 dop
->gen_kids (f
, 2, gimple
);
3773 fprintf (f
, " return false;\n");
3775 fprintf (f
, " return NULL_TREE;\n");
3779 /* Then generate the main entry with the outermost switch and
3780 tail-calls to the split-out functions. */
3782 fprintf (f
, "\nstatic bool\n"
3783 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3784 " gimple_seq *seq, tree (*valueize)(tree),\n"
3785 " code_helper code, const tree type");
3787 fprintf (f
, "\ntree\n"
3788 "generic_simplify (location_t loc, enum tree_code code, "
3789 "const tree type ATTRIBUTE_UNUSED");
3790 for (unsigned i
= 0; i
< n
; ++i
)
3791 fprintf (f
, ", tree op%d", i
);
3796 fprintf (f
, " switch (code.get_rep())\n"
3799 fprintf (f
, " switch (code)\n"
3801 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3803 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3804 expr
*e
= static_cast<expr
*>(dop
->op
);
3805 if (e
->ops
.length () != n
3806 /* Builtin simplifications are somewhat premature on
3807 GENERIC. The following drops patterns with outermost
3808 calls. It's easy to emit overloads for function code
3809 though if necessary. */
3811 && e
->operation
->kind
!= id_base::CODE
))
3814 if (*e
->operation
== CONVERT_EXPR
3815 || *e
->operation
== NOP_EXPR
)
3816 fprintf (f
, " CASE_CONVERT:\n");
3818 fprintf (f
, " case %s%s:\n",
3819 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3822 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3823 "seq, valueize, code, type", e
->operation
->id
);
3825 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3827 for (unsigned i
= 0; i
< n
; ++i
)
3828 fprintf (f
, ", op%d", i
);
3829 fprintf (f
, ");\n");
3831 fprintf (f
, " default:;\n"
3835 fprintf (f
, " return false;\n");
3837 fprintf (f
, " return NULL_TREE;\n");
3842 /* Output code to implement the predicate P from the decision tree DT. */
3845 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3847 fprintf (f
, "\nbool\n"
3848 "%s%s (tree t%s%s)\n"
3849 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3850 p
->nargs
> 0 ? ", tree *res_ops" : "",
3851 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3852 /* Conveniently make 'type' available. */
3853 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3856 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3857 dt
.root
->gen_kids (f
, 2, gimple
);
3859 fprintf_indent (f
, 2, "return false;\n"
3863 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3866 write_header (FILE *f
, const char *head
)
3868 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3869 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3871 /* Include the header instead of writing it awkwardly quoted here. */
3872 fprintf (f
, "\n#include \"%s\"\n", head
);
3882 parser (cpp_reader
*);
3885 const cpp_token
*next ();
3886 const cpp_token
*peek (unsigned = 1);
3887 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3888 const cpp_token
*expect (enum cpp_ttype
);
3889 const cpp_token
*eat_token (enum cpp_ttype
);
3890 const char *get_string ();
3891 const char *get_ident ();
3892 const cpp_token
*eat_ident (const char *);
3893 const char *get_number ();
3895 unsigned get_internal_capture_id ();
3897 id_base
*parse_operation ();
3898 operand
*parse_capture (operand
*, bool);
3899 operand
*parse_expr ();
3900 c_expr
*parse_c_expr (cpp_ttype
);
3901 operand
*parse_op ();
3903 void record_operlist (source_location
, user_id
*);
3905 void parse_pattern ();
3906 operand
*parse_result (operand
*, predicate_id
*);
3907 void push_simplify (simplify::simplify_kind
,
3908 vec
<simplify
*>&, operand
*, operand
*);
3909 void parse_simplify (simplify::simplify_kind
,
3910 vec
<simplify
*>&, predicate_id
*, operand
*);
3911 void parse_for (source_location
);
3912 void parse_if (source_location
);
3913 void parse_predicates (source_location
);
3914 void parse_operator_list (source_location
);
3916 void finish_match_operand (operand
*);
3919 vec
<c_expr
*> active_ifs
;
3920 vec
<vec
<user_id
*> > active_fors
;
3921 hash_set
<user_id
*> *oper_lists_set
;
3922 vec
<user_id
*> oper_lists
;
3924 cid_map_t
*capture_ids
;
3928 vec
<simplify
*> simplifiers
;
3929 vec
<predicate_id
*> user_predicates
;
3930 bool parsing_match_operand
;
3933 /* Lexing helpers. */
3935 /* Read the next non-whitespace token from R. */
3940 const cpp_token
*token
;
3943 token
= cpp_get_token (r
);
3945 while (token
->type
== CPP_PADDING
);
3949 /* Peek at the next non-whitespace token from R. */
3952 parser::peek (unsigned num
)
3954 const cpp_token
*token
;
3958 token
= cpp_peek_token (r
, i
++);
3960 while (token
->type
== CPP_PADDING
3962 /* If we peek at EOF this is a fatal error as it leaves the
3963 cpp_reader in unusable state. Assume we really wanted a
3964 token and thus this EOF is unexpected. */
3965 if (token
->type
== CPP_EOF
)
3966 fatal_at (token
, "unexpected end of file");
3970 /* Peek at the next identifier token (or return NULL if the next
3971 token is not an identifier or equal to ID if supplied). */
3974 parser::peek_ident (const char *id
, unsigned num
)
3976 const cpp_token
*token
= peek (num
);
3977 if (token
->type
!= CPP_NAME
)
3983 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3984 if (strcmp (id
, t
) == 0)
3990 /* Read the next token from R and assert it is of type TK. */
3993 parser::expect (enum cpp_ttype tk
)
3995 const cpp_token
*token
= next ();
3996 if (token
->type
!= tk
)
3997 fatal_at (token
, "expected %s, got %s",
3998 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4003 /* Consume the next token from R and assert it is of type TK. */
4006 parser::eat_token (enum cpp_ttype tk
)
4011 /* Read the next token from R and assert it is of type CPP_STRING and
4012 return its value. */
4015 parser::get_string ()
4017 const cpp_token
*token
= expect (CPP_STRING
);
4018 return (const char *)token
->val
.str
.text
;
4021 /* Read the next token from R and assert it is of type CPP_NAME and
4022 return its value. */
4025 parser::get_ident ()
4027 const cpp_token
*token
= expect (CPP_NAME
);
4028 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4031 /* Eat an identifier token with value S from R. */
4034 parser::eat_ident (const char *s
)
4036 const cpp_token
*token
= peek ();
4037 const char *t
= get_ident ();
4038 if (strcmp (s
, t
) != 0)
4039 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4043 /* Read the next token from R and assert it is of type CPP_NUMBER and
4044 return its value. */
4047 parser::get_number ()
4049 const cpp_token
*token
= expect (CPP_NUMBER
);
4050 return (const char *)token
->val
.str
.text
;
4053 /* Return a capture ID that can be used internally. */
4056 parser::get_internal_capture_id ()
4058 unsigned newid
= capture_ids
->elements ();
4059 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4062 sprintf (id
, "__%u", newid
);
4063 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4065 fatal ("reserved capture id '%s' already used", id
);
4069 /* Record an operator-list use for transparent for handling. */
4072 parser::record_operlist (source_location loc
, user_id
*p
)
4074 if (!oper_lists_set
->add (p
))
4076 if (!oper_lists
.is_empty ()
4077 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4078 fatal_at (loc
, "User-defined operator list does not have the "
4079 "same number of entries as others used in the pattern");
4080 oper_lists
.safe_push (p
);
4084 /* Parse the operator ID, special-casing convert?, convert1? and
4088 parser::parse_operation ()
4090 const cpp_token
*id_tok
= peek ();
4091 const char *id
= get_ident ();
4092 const cpp_token
*token
= peek ();
4093 if (strcmp (id
, "convert0") == 0)
4094 fatal_at (id_tok
, "use 'convert?' here");
4095 else if (strcmp (id
, "view_convert0") == 0)
4096 fatal_at (id_tok
, "use 'view_convert?' here");
4097 if (token
->type
== CPP_QUERY
4098 && !(token
->flags
& PREV_WHITE
))
4100 if (strcmp (id
, "convert") == 0)
4102 else if (strcmp (id
, "convert1") == 0)
4104 else if (strcmp (id
, "convert2") == 0)
4106 else if (strcmp (id
, "view_convert") == 0)
4107 id
= "view_convert0";
4108 else if (strcmp (id
, "view_convert1") == 0)
4110 else if (strcmp (id
, "view_convert2") == 0)
4113 fatal_at (id_tok
, "non-convert operator conditionalized");
4115 if (!parsing_match_operand
)
4116 fatal_at (id_tok
, "conditional convert can only be used in "
4117 "match expression");
4118 eat_token (CPP_QUERY
);
4120 else if (strcmp (id
, "convert1") == 0
4121 || strcmp (id
, "convert2") == 0
4122 || strcmp (id
, "view_convert1") == 0
4123 || strcmp (id
, "view_convert2") == 0)
4124 fatal_at (id_tok
, "expected '?' after conditional operator");
4125 id_base
*op
= get_operator (id
);
4127 fatal_at (id_tok
, "unknown operator %s", id
);
4129 user_id
*p
= dyn_cast
<user_id
*> (op
);
4130 if (p
&& p
->is_oper_list
)
4132 if (active_fors
.length() == 0)
4133 record_operlist (id_tok
->src_loc
, p
);
4135 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
4141 capture = '@'<number> */
4144 parser::parse_capture (operand
*op
, bool require_existing
)
4146 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4147 const cpp_token
*token
= peek ();
4148 const char *id
= NULL
;
4149 bool value_match
= false;
4150 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4151 if (token
->type
== CPP_ATSIGN
4152 && ! (token
->flags
& PREV_WHITE
)
4153 && parsing_match_operand
)
4155 eat_token (CPP_ATSIGN
);
4159 if (token
->type
== CPP_NUMBER
)
4161 else if (token
->type
== CPP_NAME
)
4164 fatal_at (token
, "expected number or identifier");
4165 unsigned next_id
= capture_ids
->elements ();
4167 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4170 if (require_existing
)
4171 fatal_at (src_loc
, "unknown capture id");
4174 return new capture (src_loc
, num
, op
, value_match
);
4177 /* Parse an expression
4178 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4181 parser::parse_expr ()
4183 const cpp_token
*token
= peek ();
4184 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4187 bool is_commutative
= false;
4188 bool force_capture
= false;
4189 const char *expr_type
= NULL
;
4191 if (token
->type
== CPP_COLON
4192 && !(token
->flags
& PREV_WHITE
))
4194 eat_token (CPP_COLON
);
4196 if (token
->type
== CPP_NAME
4197 && !(token
->flags
& PREV_WHITE
))
4199 const char *s
= get_ident ();
4200 if (!parsing_match_operand
)
4210 = dyn_cast
<operator_id
*> (e
->operation
))
4212 if (!commutative_tree_code (p
->code
)
4213 && !comparison_code_p (p
->code
))
4214 fatal_at (token
, "operation is not commutative");
4216 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4217 for (unsigned i
= 0;
4218 i
< p
->substitutes
.length (); ++i
)
4221 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4223 if (!commutative_tree_code (q
->code
)
4224 && !comparison_code_p (q
->code
))
4225 fatal_at (token
, "operation %s is not "
4226 "commutative", q
->id
);
4229 is_commutative
= true;
4231 else if (*sp
== 'C')
4232 is_commutative
= true;
4233 else if (*sp
== 's')
4235 e
->force_single_use
= true;
4236 force_capture
= true;
4239 fatal_at (token
, "flag %c not recognized", *sp
);
4246 fatal_at (token
, "expected flag or type specifying identifier");
4249 if (token
->type
== CPP_ATSIGN
4250 && !(token
->flags
& PREV_WHITE
))
4251 op
= parse_capture (e
, false);
4252 else if (force_capture
)
4254 unsigned num
= get_internal_capture_id ();
4255 op
= new capture (token
->src_loc
, num
, e
, false);
4261 const cpp_token
*token
= peek ();
4262 if (token
->type
== CPP_CLOSE_PAREN
)
4264 if (e
->operation
->nargs
!= -1
4265 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4266 fatal_at (token
, "'%s' expects %u operands, not %u",
4267 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4270 if (e
->ops
.length () == 2
4271 || commutative_op (e
->operation
) >= 0)
4272 e
->is_commutative
= true;
4274 fatal_at (token
, "only binary operators or functions with "
4275 "two arguments can be marked commutative, "
4276 "unless the operation is known to be inherently "
4279 e
->expr_type
= expr_type
;
4282 else if (!(token
->flags
& PREV_WHITE
))
4283 fatal_at (token
, "expected expression operand");
4285 e
->append_op (parse_op ());
4290 /* Lex native C code delimited by START recording the preprocessing tokens
4291 for later processing.
4292 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4295 parser::parse_c_expr (cpp_ttype start
)
4297 const cpp_token
*token
;
4300 vec
<cpp_token
> code
= vNULL
;
4301 unsigned nr_stmts
= 0;
4302 source_location loc
= eat_token (start
)->src_loc
;
4303 if (start
== CPP_OPEN_PAREN
)
4304 end
= CPP_CLOSE_PAREN
;
4305 else if (start
== CPP_OPEN_BRACE
)
4306 end
= CPP_CLOSE_BRACE
;
4314 /* Count brace pairs to find the end of the expr to match. */
4315 if (token
->type
== start
)
4317 else if (token
->type
== end
4320 else if (token
->type
== CPP_EOF
)
4321 fatal_at (token
, "unexpected end of file");
4323 /* This is a lame way of counting the number of statements. */
4324 if (token
->type
== CPP_SEMICOLON
)
4327 /* If this is possibly a user-defined identifier mark it used. */
4328 if (token
->type
== CPP_NAME
)
4330 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4331 (token
->val
.node
.node
)->ident
.str
);
4333 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4334 record_operlist (token
->src_loc
, p
);
4337 /* Record the token. */
4338 code
.safe_push (*token
);
4341 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4344 /* Parse an operand which is either an expression, a predicate or
4345 a standalone capture.
4346 op = predicate | expr | c_expr | capture */
4351 const cpp_token
*token
= peek ();
4352 struct operand
*op
= NULL
;
4353 if (token
->type
== CPP_OPEN_PAREN
)
4355 eat_token (CPP_OPEN_PAREN
);
4357 eat_token (CPP_CLOSE_PAREN
);
4359 else if (token
->type
== CPP_OPEN_BRACE
)
4361 op
= parse_c_expr (CPP_OPEN_BRACE
);
4365 /* Remaining ops are either empty or predicates */
4366 if (token
->type
== CPP_NAME
)
4368 const char *id
= get_ident ();
4369 id_base
*opr
= get_operator (id
);
4371 fatal_at (token
, "expected predicate name");
4372 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4374 if (code
->nargs
!= 0)
4375 fatal_at (token
, "using an operator with operands as predicate");
4376 /* Parse the zero-operand operator "predicates" as
4378 op
= new expr (opr
, token
->src_loc
);
4380 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4382 if (code
->nargs
!= 0)
4383 fatal_at (token
, "using an operator with operands as predicate");
4384 /* Parse the zero-operand operator "predicates" as
4386 op
= new expr (opr
, token
->src_loc
);
4388 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4389 op
= new predicate (p
, token
->src_loc
);
4391 fatal_at (token
, "using an unsupported operator as predicate");
4392 if (!parsing_match_operand
)
4393 fatal_at (token
, "predicates are only allowed in match expression");
4395 if (token
->flags
& PREV_WHITE
)
4398 else if (token
->type
!= CPP_COLON
4399 && token
->type
!= CPP_ATSIGN
)
4400 fatal_at (token
, "expected expression or predicate");
4401 /* optionally followed by a capture and a predicate. */
4402 if (token
->type
== CPP_COLON
)
4403 fatal_at (token
, "not implemented: predicate on leaf operand");
4404 if (token
->type
== CPP_ATSIGN
)
4405 op
= parse_capture (op
, !parsing_match_operand
);
4411 /* Create a new simplify from the current parsing state and MATCH,
4412 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4415 parser::push_simplify (simplify::simplify_kind kind
,
4416 vec
<simplify
*>& simplifiers
,
4417 operand
*match
, operand
*result
)
4419 /* Build and push a temporary for operator list uses in expressions. */
4420 if (!oper_lists
.is_empty ())
4421 active_fors
.safe_push (oper_lists
);
4423 simplifiers
.safe_push
4424 (new simplify (kind
, last_id
++, match
, result
,
4425 active_fors
.copy (), capture_ids
));
4427 if (!oper_lists
.is_empty ())
4432 <result-op> = <op> | <if> | <with>
4433 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4434 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4438 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4440 const cpp_token
*token
= peek ();
4441 if (token
->type
!= CPP_OPEN_PAREN
)
4444 eat_token (CPP_OPEN_PAREN
);
4445 if (peek_ident ("if"))
4448 if_expr
*ife
= new if_expr (token
->src_loc
);
4449 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4450 if (peek ()->type
== CPP_OPEN_PAREN
)
4452 ife
->trueexpr
= parse_result (result
, matcher
);
4453 if (peek ()->type
== CPP_OPEN_PAREN
)
4454 ife
->falseexpr
= parse_result (result
, matcher
);
4455 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4456 ife
->falseexpr
= parse_op ();
4458 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4460 ife
->trueexpr
= parse_op ();
4461 if (peek ()->type
== CPP_OPEN_PAREN
)
4462 ife
->falseexpr
= parse_result (result
, matcher
);
4463 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4464 ife
->falseexpr
= parse_op ();
4466 /* If this if is immediately closed then it contains a
4467 manual matcher or is part of a predicate definition. */
4468 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4471 fatal_at (peek (), "manual transform not implemented");
4472 ife
->trueexpr
= result
;
4474 eat_token (CPP_CLOSE_PAREN
);
4477 else if (peek_ident ("with"))
4480 with_expr
*withe
= new with_expr (token
->src_loc
);
4481 /* Parse (with c-expr expr) as (if-with (true) expr). */
4482 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4483 withe
->with
->nr_stmts
= 0;
4484 withe
->subexpr
= parse_result (result
, matcher
);
4485 eat_token (CPP_CLOSE_PAREN
);
4488 else if (peek_ident ("switch"))
4490 token
= eat_ident ("switch");
4491 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4493 if_expr
*ife
= new if_expr (ifloc
);
4495 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4496 if (peek ()->type
== CPP_OPEN_PAREN
)
4497 ife
->trueexpr
= parse_result (result
, matcher
);
4499 ife
->trueexpr
= parse_op ();
4500 eat_token (CPP_CLOSE_PAREN
);
4501 if (peek ()->type
!= CPP_OPEN_PAREN
4502 || !peek_ident ("if", 2))
4503 fatal_at (token
, "switch can be implemented with a single if");
4504 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4506 if (peek ()->type
== CPP_OPEN_PAREN
)
4508 if (peek_ident ("if", 2))
4510 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4512 ife
->falseexpr
= new if_expr (ifloc
);
4513 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4514 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4515 if (peek ()->type
== CPP_OPEN_PAREN
)
4516 ife
->trueexpr
= parse_result (result
, matcher
);
4518 ife
->trueexpr
= parse_op ();
4519 eat_token (CPP_CLOSE_PAREN
);
4523 /* switch default clause */
4524 ife
->falseexpr
= parse_result (result
, matcher
);
4525 eat_token (CPP_CLOSE_PAREN
);
4531 /* switch default clause */
4532 ife
->falseexpr
= parse_op ();
4533 eat_token (CPP_CLOSE_PAREN
);
4537 eat_token (CPP_CLOSE_PAREN
);
4542 operand
*op
= result
;
4545 eat_token (CPP_CLOSE_PAREN
);
4551 simplify = 'simplify' <expr> <result-op>
4553 match = 'match' <ident> <expr> [<result-op>]
4554 and fill SIMPLIFIERS with the results. */
4557 parser::parse_simplify (simplify::simplify_kind kind
,
4558 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4561 /* Reset the capture map. */
4563 capture_ids
= new cid_map_t
;
4564 /* Reset oper_lists and set. */
4565 hash_set
<user_id
*> olist
;
4566 oper_lists_set
= &olist
;
4569 const cpp_token
*loc
= peek ();
4570 parsing_match_operand
= true;
4571 struct operand
*match
= parse_op ();
4572 finish_match_operand (match
);
4573 parsing_match_operand
= false;
4574 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4575 fatal_at (loc
, "outermost expression cannot be captured");
4576 if (match
->type
== operand::OP_EXPR
4577 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4578 fatal_at (loc
, "outermost expression cannot be a predicate");
4580 /* Splice active_ifs onto result and continue parsing the
4582 if_expr
*active_if
= NULL
;
4583 for (int i
= active_ifs
.length (); i
> 0; --i
)
4585 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4586 ifc
->cond
= active_ifs
[i
-1];
4587 ifc
->trueexpr
= active_if
;
4590 if_expr
*outermost_if
= active_if
;
4591 while (active_if
&& active_if
->trueexpr
)
4592 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4594 const cpp_token
*token
= peek ();
4596 /* If this if is immediately closed then it is part of a predicate
4597 definition. Push it. */
4598 if (token
->type
== CPP_CLOSE_PAREN
)
4601 fatal_at (token
, "expected transform expression");
4604 active_if
->trueexpr
= result
;
4605 result
= outermost_if
;
4607 push_simplify (kind
, simplifiers
, match
, result
);
4611 operand
*tem
= parse_result (result
, matcher
);
4614 active_if
->trueexpr
= tem
;
4615 result
= outermost_if
;
4620 push_simplify (kind
, simplifiers
, match
, result
);
4623 /* Parsing of the outer control structures. */
4625 /* Parse a for expression
4626 for = '(' 'for' <subst>... <pattern> ')'
4627 subst = <ident> '(' <ident>... ')' */
4630 parser::parse_for (source_location
)
4632 auto_vec
<const cpp_token
*> user_id_tokens
;
4633 vec
<user_id
*> user_ids
= vNULL
;
4634 const cpp_token
*token
;
4635 unsigned min_n_opers
= 0, max_n_opers
= 0;
4640 if (token
->type
!= CPP_NAME
)
4643 /* Insert the user defined operators into the operator hash. */
4644 const char *id
= get_ident ();
4645 if (get_operator (id
, true) != NULL
)
4646 fatal_at (token
, "operator already defined");
4647 user_id
*op
= new user_id (id
);
4648 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4650 user_ids
.safe_push (op
);
4651 user_id_tokens
.safe_push (token
);
4653 eat_token (CPP_OPEN_PAREN
);
4656 while ((token
= peek_ident ()) != 0)
4658 const char *oper
= get_ident ();
4659 id_base
*idb
= get_operator (oper
, true);
4661 fatal_at (token
, "no such operator '%s'", oper
);
4662 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4663 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4664 || *idb
== VIEW_CONVERT2
)
4665 fatal_at (token
, "conditional operators cannot be used inside for");
4669 else if (idb
->nargs
== -1)
4671 else if (idb
->nargs
!= arity
)
4672 fatal_at (token
, "operator '%s' with arity %d does not match "
4673 "others with arity %d", oper
, idb
->nargs
, arity
);
4675 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4678 if (p
->is_oper_list
)
4679 op
->substitutes
.safe_splice (p
->substitutes
);
4681 fatal_at (token
, "iterator cannot be used as operator-list");
4684 op
->substitutes
.safe_push (idb
);
4687 token
= expect (CPP_CLOSE_PAREN
);
4689 unsigned nsubstitutes
= op
->substitutes
.length ();
4690 if (nsubstitutes
== 0)
4691 fatal_at (token
, "A user-defined operator must have at least "
4692 "one substitution");
4693 if (max_n_opers
== 0)
4695 min_n_opers
= nsubstitutes
;
4696 max_n_opers
= nsubstitutes
;
4700 if (nsubstitutes
% min_n_opers
!= 0
4701 && min_n_opers
% nsubstitutes
!= 0)
4702 fatal_at (token
, "All user-defined identifiers must have a "
4703 "multiple number of operator substitutions of the "
4704 "smallest number of substitutions");
4705 if (nsubstitutes
< min_n_opers
)
4706 min_n_opers
= nsubstitutes
;
4707 else if (nsubstitutes
> max_n_opers
)
4708 max_n_opers
= nsubstitutes
;
4712 unsigned n_ids
= user_ids
.length ();
4714 fatal_at (token
, "for requires at least one user-defined identifier");
4717 if (token
->type
== CPP_CLOSE_PAREN
)
4718 fatal_at (token
, "no pattern defined in for");
4720 active_fors
.safe_push (user_ids
);
4724 if (token
->type
== CPP_CLOSE_PAREN
)
4730 /* Remove user-defined operators from the hash again. */
4731 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4733 if (!user_ids
[i
]->used
)
4734 warning_at (user_id_tokens
[i
],
4735 "operator %s defined but not used", user_ids
[i
]->id
);
4736 operators
->remove_elt (user_ids
[i
]);
4740 /* Parse an identifier associated with a list of operators.
4741 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4744 parser::parse_operator_list (source_location
)
4746 const cpp_token
*token
= peek ();
4747 const char *id
= get_ident ();
4749 if (get_operator (id
, true) != 0)
4750 fatal_at (token
, "operator %s already defined", id
);
4752 user_id
*op
= new user_id (id
, true);
4755 while ((token
= peek_ident ()) != 0)
4758 const char *oper
= get_ident ();
4759 id_base
*idb
= get_operator (oper
, true);
4762 fatal_at (token
, "no such operator '%s'", oper
);
4766 else if (idb
->nargs
== -1)
4768 else if (arity
!= idb
->nargs
)
4769 fatal_at (token
, "operator '%s' with arity %d does not match "
4770 "others with arity %d", oper
, idb
->nargs
, arity
);
4772 /* We allow composition of multiple operator lists. */
4773 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4774 op
->substitutes
.safe_splice (p
->substitutes
);
4776 op
->substitutes
.safe_push (idb
);
4779 // Check that there is no junk after id-list
4781 if (token
->type
!= CPP_CLOSE_PAREN
)
4782 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4784 if (op
->substitutes
.length () == 0)
4785 fatal_at (token
, "operator-list cannot be empty");
4788 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4792 /* Parse an outer if expression.
4793 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4796 parser::parse_if (source_location
)
4798 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4800 const cpp_token
*token
= peek ();
4801 if (token
->type
== CPP_CLOSE_PAREN
)
4802 fatal_at (token
, "no pattern defined in if");
4804 active_ifs
.safe_push (ifexpr
);
4807 const cpp_token
*token
= peek ();
4808 if (token
->type
== CPP_CLOSE_PAREN
)
4816 /* Parse a list of predefined predicate identifiers.
4817 preds = '(' 'define_predicates' <ident>... ')' */
4820 parser::parse_predicates (source_location
)
4824 const cpp_token
*token
= peek ();
4825 if (token
->type
!= CPP_NAME
)
4828 add_predicate (get_ident ());
4833 /* Parse outer control structures.
4834 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4837 parser::parse_pattern ()
4839 /* All clauses start with '('. */
4840 eat_token (CPP_OPEN_PAREN
);
4841 const cpp_token
*token
= peek ();
4842 const char *id
= get_ident ();
4843 if (strcmp (id
, "simplify") == 0)
4845 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4848 else if (strcmp (id
, "match") == 0)
4850 bool with_args
= false;
4851 source_location e_loc
= peek ()->src_loc
;
4852 if (peek ()->type
== CPP_OPEN_PAREN
)
4854 eat_token (CPP_OPEN_PAREN
);
4857 const char *name
= get_ident ();
4858 id_base
*id
= get_operator (name
);
4862 p
= add_predicate (name
);
4863 user_predicates
.safe_push (p
);
4865 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4868 fatal_at (token
, "cannot add a match to a non-predicate ID");
4869 /* Parse (match <id> <arg>... (match-expr)) here. */
4873 capture_ids
= new cid_map_t
;
4874 e
= new expr (p
, e_loc
);
4875 while (peek ()->type
== CPP_ATSIGN
)
4876 e
->append_op (parse_capture (NULL
, false));
4877 eat_token (CPP_CLOSE_PAREN
);
4880 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4881 || (!e
&& p
->nargs
!= 0)))
4882 fatal_at (token
, "non-matching number of match operands");
4883 p
->nargs
= e
? e
->ops
.length () : 0;
4884 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4887 else if (strcmp (id
, "for") == 0)
4888 parse_for (token
->src_loc
);
4889 else if (strcmp (id
, "if") == 0)
4890 parse_if (token
->src_loc
);
4891 else if (strcmp (id
, "define_predicates") == 0)
4893 if (active_ifs
.length () > 0
4894 || active_fors
.length () > 0)
4895 fatal_at (token
, "define_predicates inside if or for is not supported");
4896 parse_predicates (token
->src_loc
);
4898 else if (strcmp (id
, "define_operator_list") == 0)
4900 if (active_ifs
.length () > 0
4901 || active_fors
.length () > 0)
4902 fatal_at (token
, "operator-list inside if or for is not supported");
4903 parse_operator_list (token
->src_loc
);
4906 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4907 active_ifs
.length () == 0 && active_fors
.length () == 0
4908 ? "'define_predicates', " : "");
4910 eat_token (CPP_CLOSE_PAREN
);
4913 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4917 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4922 if (capture
*c
= dyn_cast
<capture
*> (op
))
4924 cpts
[c
->where
].safe_push (c
);
4925 walk_captures (c
->what
, cpts
);
4927 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4928 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4929 walk_captures (e
->ops
[i
], cpts
);
4932 /* Finish up OP which is a match operand. */
4935 parser::finish_match_operand (operand
*op
)
4937 /* Look for matching captures, diagnose mis-uses of @@ and apply
4938 early lowering and distribution of value_match. */
4939 auto_vec
<vec
<capture
*> > cpts
;
4940 cpts
.safe_grow_cleared (capture_ids
->elements ());
4941 walk_captures (op
, cpts
);
4942 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4944 capture
*value_match
= NULL
;
4945 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4947 if (cpts
[i
][j
]->value_match
)
4950 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4951 value_match
= cpts
[i
][j
];
4954 if (cpts
[i
].length () == 1 && value_match
)
4955 fatal_at (value_match
->location
, "@@ without a matching capture");
4958 /* Duplicate prevailing capture with the existing ID, create
4959 a fake ID and rewrite all captures to use it. This turns
4960 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4961 value_match
->what
= new capture (value_match
->location
,
4963 value_match
->what
, false);
4964 /* Create a fake ID and rewrite all captures to use it. */
4965 unsigned newid
= get_internal_capture_id ();
4966 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4968 cpts
[i
][j
]->where
= newid
;
4969 cpts
[i
][j
]->value_match
= true;
4976 /* Main entry of the parser. Repeatedly parse outer control structures. */
4978 parser::parser (cpp_reader
*r_
)
4982 active_fors
= vNULL
;
4983 simplifiers
= vNULL
;
4984 oper_lists_set
= NULL
;
4987 user_predicates
= vNULL
;
4988 parsing_match_operand
= false;
4991 const cpp_token
*token
= next ();
4992 while (token
->type
!= CPP_EOF
)
4994 _cpp_backup_tokens (r
, 1);
5001 /* Helper for the linemap code. */
5004 round_alloc_size (size_t s
)
5010 /* The genmatch generator progam. It reads from a pattern description
5011 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5014 main (int argc
, char **argv
)
5018 progname
= "genmatch";
5024 char *input
= argv
[argc
-1];
5025 for (int i
= 1; i
< argc
- 1; ++i
)
5027 if (strcmp (argv
[i
], "--gimple") == 0)
5029 else if (strcmp (argv
[i
], "--generic") == 0)
5031 else if (strcmp (argv
[i
], "-v") == 0)
5033 else if (strcmp (argv
[i
], "-vv") == 0)
5037 fprintf (stderr
, "Usage: genmatch "
5038 "[--gimple] [--generic] [-v[v]] input\n");
5043 line_table
= XCNEW (struct line_maps
);
5044 linemap_init (line_table
, 0);
5045 line_table
->reallocator
= xrealloc
;
5046 line_table
->round_alloc_size
= round_alloc_size
;
5048 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5049 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5050 cb
->error
= error_cb
;
5052 /* Add the build directory to the #include "" search path. */
5053 cpp_dir
*dir
= XCNEW (cpp_dir
);
5054 dir
->name
= getpwd ();
5056 dir
->name
= ASTRDUP (".");
5057 cpp_set_include_chains (r
, dir
, NULL
, false);
5059 if (!cpp_read_main_file (r
, input
))
5061 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5062 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5064 null_id
= new id_base (id_base::NULL_ID
, "null");
5066 /* Pre-seed operators. */
5067 operators
= new hash_table
<id_base
> (1024);
5068 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5069 add_operator (SYM, # SYM, # TYPE, NARGS);
5070 #define END_OF_BASE_TREE_CODES
5072 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5073 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5074 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5075 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5076 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5077 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5078 #undef END_OF_BASE_TREE_CODES
5081 /* Pre-seed builtin functions.
5082 ??? Cannot use N (name) as that is targetm.emultls.get_address
5083 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5084 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5085 add_function (ENUM, "CFN_" # ENUM);
5086 #include "builtins.def"
5088 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5089 add_function (IFN_##CODE, "CFN_" #CODE);
5090 #include "internal-fn.def"
5096 write_header (stdout
, "gimple-match-head.c");
5098 write_header (stdout
, "generic-match-head.c");
5100 /* Go over all predicates defined with patterns and perform
5101 lowering and code generation. */
5102 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5104 predicate_id
*pred
= p
.user_predicates
[i
];
5105 lower (pred
->matchers
, gimple
);
5108 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5109 print_matches (pred
->matchers
[i
]);
5112 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5113 dt
.insert (pred
->matchers
[i
], i
);
5118 write_predicate (stdout
, pred
, dt
, gimple
);
5121 /* Lower the main simplifiers and generate code for them. */
5122 lower (p
.simplifiers
, gimple
);
5125 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5126 print_matches (p
.simplifiers
[i
]);
5129 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5130 dt
.insert (p
.simplifiers
[i
], i
);
5135 dt
.gen (stdout
, gimple
);
5138 cpp_finish (r
, NULL
);