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";
2373 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2375 /* IFN_COND_* operands 1 and later by default have the same type
2376 as the result. The type of operand 0 needs to be specified
2378 if (pos
> 0 && expr_type
)
2380 else if (pos
> 0 && in_type
)
2387 /* Otherwise all types should match - choose one in order of
2394 return other_oprnd_type
;
2398 /* Generate transform code for an expression. */
2401 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2402 int depth
, const char *in_type
, capture_info
*cinfo
,
2403 dt_operand
**indexes
, int)
2405 id_base
*opr
= operation
;
2406 /* When we delay operator substituting during lowering of fors we
2407 make sure that for code-gen purposes the effects of each substitute
2408 are the same. Thus just look at that. */
2409 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2410 opr
= uid
->substitutes
[0];
2412 bool conversion_p
= is_conversion (opr
);
2413 const char *type
= expr_type
;
2416 /* If there was a type specification in the pattern use it. */
2418 else if (conversion_p
)
2419 /* For conversions we need to build the expression using the
2420 outer type passed in. */
2422 else if (*opr
== REALPART_EXPR
2423 || *opr
== IMAGPART_EXPR
)
2425 /* __real and __imag use the component type of its operand. */
2426 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2429 else if (is_a
<operator_id
*> (opr
)
2430 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2432 /* comparisons use boolean_type_node (or what gets in), but
2433 their operands need to figure out the types themselves. */
2438 sprintf (optype
, "boolean_type_node");
2443 else if (*opr
== COND_EXPR
2444 || *opr
== VEC_COND_EXPR
2445 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2447 /* Conditions are of the same type as their first alternative. */
2448 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2453 /* Other operations are of the same type as their first operand. */
2454 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2458 fatal_at (location
, "cannot determine type of operand");
2460 fprintf_indent (f
, indent
, "{\n");
2462 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2464 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2465 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2468 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2470 = get_operand_type (opr
, i
, in_type
, expr_type
,
2471 i
== 0 ? NULL
: op0type
);
2472 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2475 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2478 const char *opr_name
;
2479 if (*operation
== CONVERT_EXPR
)
2480 opr_name
= "NOP_EXPR";
2482 opr_name
= operation
->id
;
2486 if (*opr
== CONVERT_EXPR
)
2488 fprintf_indent (f
, indent
,
2489 "if (%s != TREE_TYPE (ops%d[0])\n",
2491 fprintf_indent (f
, indent
,
2492 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2494 fprintf_indent (f
, indent
+ 2, "{\n");
2497 /* ??? Building a stmt can fail for various reasons here, seq being
2498 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2499 So if we fail here we should continue matching other patterns. */
2500 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2501 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2502 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2503 fprintf (f
, ", ops%d[%u]", depth
, i
);
2504 fprintf (f
, ");\n");
2505 fprintf_indent (f
, indent
,
2506 "gimple_resimplify%d (lseq, &tem_op, valueize);\n",
2508 fprintf_indent (f
, indent
,
2509 "res = maybe_push_res_to_seq (&tem_op, lseq);\n");
2510 fprintf_indent (f
, indent
,
2511 "if (!res) return false;\n");
2512 if (*opr
== CONVERT_EXPR
)
2515 fprintf_indent (f
, indent
, " }\n");
2516 fprintf_indent (f
, indent
, "else\n");
2517 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2522 if (*opr
== CONVERT_EXPR
)
2524 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2528 if (opr
->kind
== id_base::CODE
)
2529 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2530 ops
.length(), opr_name
, type
);
2533 fprintf_indent (f
, indent
, "{\n");
2534 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2535 "%s, %s, %d", opr_name
, type
, ops
.length());
2537 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2538 fprintf (f
, ", ops%d[%u]", depth
, i
);
2539 fprintf (f
, ");\n");
2540 if (opr
->kind
!= id_base::CODE
)
2542 fprintf_indent (f
, indent
, " if (!res)\n");
2543 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2544 fprintf_indent (f
, indent
, "}\n");
2546 if (*opr
== CONVERT_EXPR
)
2549 fprintf_indent (f
, indent
, "else\n");
2550 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2553 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2555 fprintf_indent (f
, indent
, "}\n");
2558 /* Generate code for a c_expr which is either the expression inside
2559 an if statement or a sequence of statements which computes a
2560 result to be stored to DEST. */
2563 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2564 bool, int, const char *, capture_info
*,
2567 if (dest
&& nr_stmts
== 1)
2568 fprintf_indent (f
, indent
, "%s = ", dest
);
2570 unsigned stmt_nr
= 1;
2571 for (unsigned i
= 0; i
< code
.length (); ++i
)
2573 const cpp_token
*token
= &code
[i
];
2575 /* Replace captures for code-gen. */
2576 if (token
->type
== CPP_ATSIGN
)
2578 const cpp_token
*n
= &code
[i
+1];
2579 if ((n
->type
== CPP_NUMBER
2580 || n
->type
== CPP_NAME
)
2581 && !(n
->flags
& PREV_WHITE
))
2583 if (token
->flags
& PREV_WHITE
)
2586 if (n
->type
== CPP_NUMBER
)
2587 id
= (const char *)n
->val
.str
.text
;
2589 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2590 unsigned *cid
= capture_ids
->get (id
);
2592 fatal_at (token
, "unknown capture id");
2593 fprintf (f
, "captures[%u]", *cid
);
2599 if (token
->flags
& PREV_WHITE
)
2602 if (token
->type
== CPP_NAME
)
2604 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2606 for (j
= 0; j
< ids
.length (); ++j
)
2608 if (strcmp (id
, ids
[j
].id
) == 0)
2610 fprintf (f
, "%s", ids
[j
].oper
);
2614 if (j
< ids
.length ())
2618 /* Output the token as string. */
2619 char *tk
= (char *)cpp_token_as_text (r
, token
);
2622 if (token
->type
== CPP_SEMICOLON
)
2626 if (dest
&& stmt_nr
== nr_stmts
)
2627 fprintf_indent (f
, indent
, "%s = ", dest
);
2632 /* Generate transform code for a capture. */
2635 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2636 int depth
, const char *in_type
, capture_info
*cinfo
,
2637 dt_operand
**indexes
, int cond_handling
)
2639 if (what
&& is_a
<expr
*> (what
))
2641 if (indexes
[where
] == 0)
2644 sprintf (buf
, "captures[%u]", where
);
2645 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2650 /* If in GENERIC some capture is used multiple times, unshare it except
2651 when emitting the last use. */
2653 && cinfo
->info
.exists ()
2654 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2656 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2658 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2661 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2663 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2664 with substituting a capture of that. */
2666 && cond_handling
!= 0
2667 && cinfo
->info
[where
].cond_expr_cond_p
)
2669 /* If substituting into a cond_expr condition, unshare. */
2670 if (cond_handling
== 1)
2671 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2672 /* If substituting elsewhere we might need to decompose it. */
2673 else if (cond_handling
== 2)
2675 /* ??? Returning false here will also not allow any other patterns
2676 to match unless this generator was split out. */
2677 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2678 fprintf_indent (f
, indent
, " {\n");
2679 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2680 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2682 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2683 " TREE_OPERAND (%s, 1));\n",
2684 dest
, dest
, dest
, dest
, dest
);
2685 fprintf_indent (f
, indent
, " }\n");
2690 /* Return the name of the operand representing the decision tree node.
2691 Use NAME as space to generate it. */
2694 dt_operand::get_name (char *name
)
2697 sprintf (name
, "t");
2698 else if (parent
->level
== 1)
2699 sprintf (name
, "op%u", pos
);
2700 else if (parent
->type
== dt_node::DT_MATCH
)
2701 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2703 sprintf (name
, "o%u%u", parent
->level
, pos
);
2707 /* Fill NAME with the operand name at position POS. */
2710 dt_operand::gen_opname (char *name
, unsigned pos
)
2713 sprintf (name
, "op%u", pos
);
2715 sprintf (name
, "o%u%u", level
, pos
);
2718 /* Generate matching code for the decision tree operand which is
2722 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2724 predicate
*p
= as_a
<predicate
*> (op
);
2726 if (p
->p
->matchers
.exists ())
2728 /* If this is a predicate generated from a pattern mangle its
2729 name and pass on the valueize hook. */
2731 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2734 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2737 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2738 fprintf_indent (f
, indent
+ 2, "{\n");
2742 /* Generate matching code for the decision tree operand which is
2746 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2748 char match_opname
[20];
2749 match_dop
->get_name (match_opname
);
2751 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2752 "|| operand_equal_p (%s, %s, 0))\n",
2753 opname
, match_opname
, opname
, opname
, match_opname
);
2755 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2756 "|| (operand_equal_p (%s, %s, 0) "
2757 "&& types_match (%s, %s)))\n",
2758 opname
, match_opname
, opname
, opname
, match_opname
,
2759 opname
, match_opname
);
2760 fprintf_indent (f
, indent
+ 2, "{\n");
2764 /* Generate GIMPLE matching code for the decision tree operand. */
2767 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2769 expr
*e
= static_cast<expr
*> (op
);
2770 id_base
*id
= e
->operation
;
2771 unsigned n_ops
= e
->ops
.length ();
2772 unsigned n_braces
= 0;
2774 for (unsigned i
= 0; i
< n_ops
; ++i
)
2776 char child_opname
[20];
2777 gen_opname (child_opname
, i
);
2779 if (id
->kind
== id_base::CODE
)
2782 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2783 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2785 /* ??? If this is a memory operation we can't (and should not)
2786 match this. The only sensible operand types are
2787 SSA names and invariants. */
2792 fprintf_indent (f
, indent
,
2793 "tree %s = TREE_OPERAND (%s, %i);\n",
2794 child_opname
, opname
, i
);
2797 fprintf_indent (f
, indent
,
2798 "tree %s = TREE_OPERAND "
2799 "(gimple_assign_rhs1 (def), %i);\n",
2801 fprintf_indent (f
, indent
,
2802 "if ((TREE_CODE (%s) == SSA_NAME\n",
2804 fprintf_indent (f
, indent
,
2805 " || is_gimple_min_invariant (%s)))\n",
2807 fprintf_indent (f
, indent
,
2811 fprintf_indent (f
, indent
,
2812 "%s = do_valueize (valueize, %s);\n",
2813 child_opname
, child_opname
);
2817 fprintf_indent (f
, indent
,
2818 "tree %s = gimple_assign_rhs%u (def);\n",
2819 child_opname
, i
+ 1);
2822 fprintf_indent (f
, indent
,
2823 "tree %s = gimple_call_arg (def, %u);\n",
2825 fprintf_indent (f
, indent
,
2826 "%s = do_valueize (valueize, %s);\n",
2827 child_opname
, child_opname
);
2829 /* While the toplevel operands are canonicalized by the caller
2830 after valueizing operands of sub-expressions we have to
2831 re-canonicalize operand order. */
2832 int opno
= commutative_op (id
);
2835 char child_opname0
[20], child_opname1
[20];
2836 gen_opname (child_opname0
, opno
);
2837 gen_opname (child_opname1
, opno
+ 1);
2838 fprintf_indent (f
, indent
,
2839 "if (tree_swap_operands_p (%s, %s))\n",
2840 child_opname0
, child_opname1
);
2841 fprintf_indent (f
, indent
,
2842 " std::swap (%s, %s);\n",
2843 child_opname0
, child_opname1
);
2849 /* Generate GENERIC matching code for the decision tree operand. */
2852 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2854 expr
*e
= static_cast<expr
*> (op
);
2855 unsigned n_ops
= e
->ops
.length ();
2857 for (unsigned i
= 0; i
< n_ops
; ++i
)
2859 char child_opname
[20];
2860 gen_opname (child_opname
, i
);
2862 if (e
->operation
->kind
== id_base::CODE
)
2863 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2864 child_opname
, opname
, i
);
2866 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2867 child_opname
, opname
, i
);
2873 /* Generate matching code for the children of the decision tree node. */
2876 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2878 auto_vec
<dt_operand
*> gimple_exprs
;
2879 auto_vec
<dt_operand
*> generic_exprs
;
2880 auto_vec
<dt_operand
*> fns
;
2881 auto_vec
<dt_operand
*> generic_fns
;
2882 auto_vec
<dt_operand
*> preds
;
2883 auto_vec
<dt_node
*> others
;
2885 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2887 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2889 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2890 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2892 if (e
->ops
.length () == 0
2893 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2894 generic_exprs
.safe_push (op
);
2895 else if (e
->operation
->kind
== id_base::FN
)
2900 generic_fns
.safe_push (op
);
2902 else if (e
->operation
->kind
== id_base::PREDICATE
)
2903 preds
.safe_push (op
);
2906 if (gimple
&& !e
->is_generic
)
2907 gimple_exprs
.safe_push (op
);
2909 generic_exprs
.safe_push (op
);
2912 else if (op
->op
->type
== operand::OP_PREDICATE
)
2913 others
.safe_push (kids
[i
]);
2917 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2918 others
.safe_push (kids
[i
]);
2919 else if (kids
[i
]->type
== dt_node::DT_MATCH
2920 || kids
[i
]->type
== dt_node::DT_TRUE
)
2922 /* A DT_TRUE operand serves as a barrier - generate code now
2923 for what we have collected sofar.
2924 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2925 dependent matches to get out-of-order. Generate code now
2926 for what we have collected sofar. */
2927 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2928 fns
, generic_fns
, preds
, others
);
2929 /* And output the true operand itself. */
2930 kids
[i
]->gen (f
, indent
, gimple
);
2931 gimple_exprs
.truncate (0);
2932 generic_exprs
.truncate (0);
2934 generic_fns
.truncate (0);
2936 others
.truncate (0);
2942 /* Generate code for the remains. */
2943 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2944 fns
, generic_fns
, preds
, others
);
2947 /* Generate matching code for the children of the decision tree node. */
2950 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2951 vec
<dt_operand
*> gimple_exprs
,
2952 vec
<dt_operand
*> generic_exprs
,
2953 vec
<dt_operand
*> fns
,
2954 vec
<dt_operand
*> generic_fns
,
2955 vec
<dt_operand
*> preds
,
2956 vec
<dt_node
*> others
)
2959 char *kid_opname
= buf
;
2961 unsigned exprs_len
= gimple_exprs
.length ();
2962 unsigned gexprs_len
= generic_exprs
.length ();
2963 unsigned fns_len
= fns
.length ();
2964 unsigned gfns_len
= generic_fns
.length ();
2966 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2969 gimple_exprs
[0]->get_name (kid_opname
);
2971 fns
[0]->get_name (kid_opname
);
2973 generic_fns
[0]->get_name (kid_opname
);
2975 generic_exprs
[0]->get_name (kid_opname
);
2977 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2978 fprintf_indent (f
, indent
, " {\n");
2982 if (exprs_len
|| fns_len
)
2984 fprintf_indent (f
, indent
,
2985 "case SSA_NAME:\n");
2986 fprintf_indent (f
, indent
,
2987 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2989 fprintf_indent (f
, indent
,
2994 fprintf_indent (f
, indent
,
2995 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2996 fprintf_indent (f
, indent
,
2997 " switch (gimple_assign_rhs_code (def))\n");
2999 fprintf_indent (f
, indent
, "{\n");
3000 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3002 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3003 id_base
*op
= e
->operation
;
3004 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3005 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3007 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3008 fprintf_indent (f
, indent
, " {\n");
3009 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
3010 fprintf_indent (f
, indent
, " break;\n");
3011 fprintf_indent (f
, indent
, " }\n");
3013 fprintf_indent (f
, indent
, "default:;\n");
3014 fprintf_indent (f
, indent
, "}\n");
3020 fprintf_indent (f
, indent
,
3021 "%sif (gcall *def = dyn_cast <gcall *>"
3023 exprs_len
? "else " : "");
3024 fprintf_indent (f
, indent
,
3025 " switch (gimple_call_combined_fn (def))\n");
3028 fprintf_indent (f
, indent
, "{\n");
3029 for (unsigned i
= 0; i
< fns_len
; ++i
)
3031 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3032 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3033 fprintf_indent (f
, indent
, " {\n");
3034 fns
[i
]->gen (f
, indent
+ 4, true);
3035 fprintf_indent (f
, indent
, " break;\n");
3036 fprintf_indent (f
, indent
, " }\n");
3039 fprintf_indent (f
, indent
, "default:;\n");
3040 fprintf_indent (f
, indent
, "}\n");
3045 fprintf_indent (f
, indent
, " }\n");
3046 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3047 here rather than in the next loop. */
3048 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3050 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3051 id_base
*op
= e
->operation
;
3052 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3054 fprintf_indent (f
, indent
+ 4, "{\n");
3055 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
3056 fprintf_indent (f
, indent
+ 4, "}\n");
3060 fprintf_indent (f
, indent
, " break;\n");
3063 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3065 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3066 id_base
*op
= e
->operation
;
3067 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3068 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3069 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3070 /* Already handled above. */
3073 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3074 fprintf_indent (f
, indent
, " {\n");
3075 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
3076 fprintf_indent (f
, indent
, " break;\n");
3077 fprintf_indent (f
, indent
, " }\n");
3082 fprintf_indent (f
, indent
,
3083 "case CALL_EXPR:\n");
3084 fprintf_indent (f
, indent
,
3085 " switch (get_call_combined_fn (%s))\n",
3087 fprintf_indent (f
, indent
,
3091 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3093 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3094 gcc_assert (e
->operation
->kind
== id_base::FN
);
3096 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3097 fprintf_indent (f
, indent
, " {\n");
3098 generic_fns
[j
]->gen (f
, indent
+ 4, false);
3099 fprintf_indent (f
, indent
, " break;\n");
3100 fprintf_indent (f
, indent
, " }\n");
3102 fprintf_indent (f
, indent
, "default:;\n");
3105 fprintf_indent (f
, indent
, " }\n");
3106 fprintf_indent (f
, indent
, " break;\n");
3109 /* Close switch (TREE_CODE ()). */
3110 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3113 fprintf_indent (f
, indent
, " default:;\n");
3114 fprintf_indent (f
, indent
, " }\n");
3117 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3119 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3120 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3121 preds
[i
]->get_name (kid_opname
);
3122 fprintf_indent (f
, indent
, "{\n");
3124 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3125 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3126 gimple
? "gimple" : "tree",
3127 p
->id
, kid_opname
, kid_opname
,
3128 gimple
? ", valueize" : "");
3129 fprintf_indent (f
, indent
, " {\n");
3130 for (int j
= 0; j
< p
->nargs
; ++j
)
3132 char child_opname
[20];
3133 preds
[i
]->gen_opname (child_opname
, j
);
3134 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3135 child_opname
, kid_opname
, j
);
3137 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3140 fprintf_indent (f
, indent
, "}\n");
3143 for (unsigned i
= 0; i
< others
.length (); ++i
)
3144 others
[i
]->gen (f
, indent
, gimple
);
3147 /* Generate matching code for the decision tree operand. */
3150 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3155 unsigned n_braces
= 0;
3157 if (type
== DT_OPERAND
)
3160 case operand::OP_PREDICATE
:
3161 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3164 case operand::OP_EXPR
:
3166 n_braces
= gen_gimple_expr (f
, indent
);
3168 n_braces
= gen_generic_expr (f
, indent
, opname
);
3174 else if (type
== DT_TRUE
)
3176 else if (type
== DT_MATCH
)
3177 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3181 indent
+= 4 * n_braces
;
3182 gen_kids (f
, indent
, gimple
);
3184 for (unsigned i
= 0; i
< n_braces
; ++i
)
3189 fprintf_indent (f
, indent
, " }\n");
3194 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3195 step of a '(simplify ...)' or '(match ...)'. This handles everything
3196 that is not part of the decision tree (simplify->match).
3197 Main recursive worker. */
3200 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3204 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3206 fprintf_indent (f
, indent
, "{\n");
3208 output_line_directive (f
, w
->location
);
3209 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3210 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3212 fprintf_indent (f
, indent
, "}\n");
3215 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3217 output_line_directive (f
, ife
->location
);
3218 fprintf_indent (f
, indent
, "if (");
3219 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3221 fprintf_indent (f
, indent
+ 2, "{\n");
3223 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3225 fprintf_indent (f
, indent
+ 2, "}\n");
3228 fprintf_indent (f
, indent
, "else\n");
3229 fprintf_indent (f
, indent
+ 2, "{\n");
3231 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3233 fprintf_indent (f
, indent
+ 2, "}\n");
3239 /* Analyze captures and perform early-outs on the incoming arguments
3240 that cover cases we cannot handle. */
3241 capture_info
cinfo (s
, result
, gimple
);
3242 if (s
->kind
== simplify::SIMPLIFY
)
3246 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3247 if (cinfo
.force_no_side_effects
& (1 << i
))
3249 fprintf_indent (f
, indent
,
3250 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3253 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3254 "forcing toplevel operand to have no "
3257 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3258 if (cinfo
.info
[i
].cse_p
)
3260 else if (cinfo
.info
[i
].force_no_side_effects_p
3261 && (cinfo
.info
[i
].toplevel_msk
3262 & cinfo
.force_no_side_effects
) == 0)
3264 fprintf_indent (f
, indent
,
3265 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3266 "return NULL_TREE;\n", i
);
3268 warning_at (cinfo
.info
[i
].c
->location
,
3269 "forcing captured operand to have no "
3272 else if ((cinfo
.info
[i
].toplevel_msk
3273 & cinfo
.force_no_side_effects
) != 0)
3274 /* Mark capture as having no side-effects if we had to verify
3275 that via forced toplevel operand checks. */
3276 cinfo
.info
[i
].force_no_side_effects_p
= true;
3280 /* Force single-use restriction by only allowing simple
3281 results via setting seq to NULL. */
3282 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3283 bool first_p
= true;
3284 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3285 if (cinfo
.info
[i
].force_single_use
)
3289 fprintf_indent (f
, indent
, "if (lseq\n");
3290 fprintf_indent (f
, indent
, " && (");
3296 fprintf_indent (f
, indent
, " || ");
3298 fprintf (f
, "!single_use (captures[%d])", i
);
3302 fprintf (f
, "))\n");
3303 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3308 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_FOLDING)) "
3309 "fprintf (dump_file, \"Applying pattern ");
3310 output_line_directive (f
,
3311 result
? result
->location
: s
->match
->location
, true);
3312 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3316 /* If there is no result then this is a predicate implementation. */
3317 fprintf_indent (f
, indent
, "return true;\n");
3321 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3322 in outermost position). */
3323 if (result
->type
== operand::OP_EXPR
3324 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3325 result
= as_a
<expr
*> (result
)->ops
[0];
3326 if (result
->type
== operand::OP_EXPR
)
3328 expr
*e
= as_a
<expr
*> (result
);
3329 id_base
*opr
= e
->operation
;
3330 bool is_predicate
= false;
3331 /* When we delay operator substituting during lowering of fors we
3332 make sure that for code-gen purposes the effects of each substitute
3333 are the same. Thus just look at that. */
3334 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3335 opr
= uid
->substitutes
[0];
3336 else if (is_a
<predicate_id
*> (opr
))
3337 is_predicate
= true;
3339 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3340 *e
->operation
== CONVERT_EXPR
3341 ? "NOP_EXPR" : e
->operation
->id
,
3343 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3347 snprintf (dest
, 32, "res_ops[%d]", j
);
3349 snprintf (dest
, 32, "res_op->ops[%d]", j
);
3351 = get_operand_type (opr
, j
,
3352 "type", e
->expr_type
,
3354 : "TREE_TYPE (res_op->ops[0])");
3355 /* We need to expand GENERIC conditions we captured from
3356 COND_EXPRs and we need to unshare them when substituting
3358 int cond_handling
= 0;
3360 cond_handling
= ((*opr
== COND_EXPR
3361 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3362 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3363 &cinfo
, indexes
, cond_handling
);
3366 /* Re-fold the toplevel result. It's basically an embedded
3367 gimple_build w/o actually building the stmt. */
3369 fprintf_indent (f
, indent
,
3370 "gimple_resimplify%d (lseq, res_op,"
3371 " valueize);\n", e
->ops
.length ());
3373 else if (result
->type
== operand::OP_CAPTURE
3374 || result
->type
== operand::OP_C_EXPR
)
3376 fprintf_indent (f
, indent
, "tree tem;\n");
3377 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3379 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3380 if (is_a
<capture
*> (result
)
3381 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3383 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3384 with substituting a capture of that. */
3385 fprintf_indent (f
, indent
,
3386 "if (COMPARISON_CLASS_P (tem))\n");
3387 fprintf_indent (f
, indent
,
3389 fprintf_indent (f
, indent
,
3390 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3391 fprintf_indent (f
, indent
,
3392 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3393 fprintf_indent (f
, indent
,
3399 fprintf_indent (f
, indent
, "return true;\n");
3403 bool is_predicate
= false;
3404 if (result
->type
== operand::OP_EXPR
)
3406 expr
*e
= as_a
<expr
*> (result
);
3407 id_base
*opr
= e
->operation
;
3408 /* When we delay operator substituting during lowering of fors we
3409 make sure that for code-gen purposes the effects of each substitute
3410 are the same. Thus just look at that. */
3411 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3412 opr
= uid
->substitutes
[0];
3413 else if (is_a
<predicate_id
*> (opr
))
3414 is_predicate
= true;
3415 /* Search for captures used multiple times in the result expression
3416 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3417 original expression. */
3419 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3421 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3422 || cinfo
.info
[i
].cse_p
)
3424 if (cinfo
.info
[i
].result_use_count
3425 > cinfo
.info
[i
].match_use_count
)
3426 fprintf_indent (f
, indent
,
3427 "if (! tree_invariant_p (captures[%d])) "
3428 "return NULL_TREE;\n", i
);
3430 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3434 snprintf (dest
, 32, "res_ops[%d]", j
);
3437 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3438 snprintf (dest
, 32, "res_op%d", j
);
3441 = get_operand_type (opr
, j
,
3442 "type", e
->expr_type
,
3444 ? NULL
: "TREE_TYPE (res_op0)");
3445 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3449 fprintf_indent (f
, indent
, "return true;\n");
3452 fprintf_indent (f
, indent
, "tree res;\n");
3453 /* Re-fold the toplevel result. Use non_lvalue to
3454 build NON_LVALUE_EXPRs so they get properly
3455 ignored when in GIMPLE form. */
3456 if (*opr
== NON_LVALUE_EXPR
)
3457 fprintf_indent (f
, indent
,
3458 "res = non_lvalue_loc (loc, res_op0);\n");
3461 if (is_a
<operator_id
*> (opr
))
3462 fprintf_indent (f
, indent
,
3463 "res = fold_build%d_loc (loc, %s, type",
3465 *e
->operation
== CONVERT_EXPR
3466 ? "NOP_EXPR" : e
->operation
->id
);
3468 fprintf_indent (f
, indent
,
3469 "res = maybe_build_call_expr_loc (loc, "
3470 "%s, type, %d", e
->operation
->id
,
3472 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3473 fprintf (f
, ", res_op%d", j
);
3474 fprintf (f
, ");\n");
3475 if (!is_a
<operator_id
*> (opr
))
3477 fprintf_indent (f
, indent
, "if (!res)\n");
3478 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3483 else if (result
->type
== operand::OP_CAPTURE
3484 || result
->type
== operand::OP_C_EXPR
)
3487 fprintf_indent (f
, indent
, "tree res;\n");
3488 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3495 /* Search for captures not used in the result expression and dependent
3496 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3497 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3499 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3501 if (!cinfo
.info
[i
].force_no_side_effects_p
3502 && !cinfo
.info
[i
].expr_p
3503 && cinfo
.info
[i
].result_use_count
== 0)
3505 fprintf_indent (f
, indent
,
3506 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3508 fprintf_indent (f
, indent
+ 2,
3509 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3510 "fold_ignored_result (captures[%d]), res);\n",
3514 fprintf_indent (f
, indent
, "return res;\n");
3519 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3520 step of a '(simplify ...)' or '(match ...)'. This handles everything
3521 that is not part of the decision tree (simplify->match). */
3524 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3526 fprintf_indent (f
, indent
, "{\n");
3528 output_line_directive (f
,
3529 s
->result
? s
->result
->location
: s
->match
->location
);
3530 if (s
->capture_max
>= 0)
3533 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3534 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3536 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3540 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3542 fprintf (f
, " };\n");
3545 /* If we have a split-out function for the actual transform, call it. */
3546 if (info
&& info
->fname
)
3550 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3551 "valueize, type, captures", info
->fname
);
3552 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3553 if (s
->for_subst_vec
[i
].first
->used
)
3554 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3555 fprintf (f
, "))\n");
3556 fprintf_indent (f
, indent
, " return true;\n");
3560 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3562 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3563 fprintf (f
, ", op%d", i
);
3564 fprintf (f
, ", captures");
3565 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3567 if (s
->for_subst_vec
[i
].first
->used
)
3568 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3570 fprintf (f
, ");\n");
3571 fprintf_indent (f
, indent
, "if (res) return res;\n");
3576 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3578 if (! s
->for_subst_vec
[i
].first
->used
)
3580 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3581 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3582 s
->for_subst_vec
[i
].first
->id
,
3583 s
->for_subst_vec
[i
].second
->id
);
3584 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3585 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3586 s
->for_subst_vec
[i
].first
->id
,
3587 s
->for_subst_vec
[i
].second
->id
);
3591 gen_1 (f
, indent
, gimple
, s
->result
);
3595 fprintf_indent (f
, indent
, "}\n");
3599 /* Hash function for finding equivalent transforms. */
3602 sinfo_hashmap_traits::hash (const key_type
&v
)
3604 /* Only bother to compare those originating from the same source pattern. */
3605 return v
->s
->result
->location
;
3608 /* Compare function for finding equivalent transforms. */
3611 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3613 if (o1
->type
!= o2
->type
)
3618 case operand::OP_IF
:
3620 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3621 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3622 /* ??? Properly compare c-exprs. */
3623 if (if1
->cond
!= if2
->cond
)
3625 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3627 if (if1
->falseexpr
!= if2
->falseexpr
3629 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3633 case operand::OP_WITH
:
3635 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3636 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3637 if (with1
->with
!= with2
->with
)
3639 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3644 /* We've hit a result. Time to compare capture-infos - this is required
3645 in addition to the conservative pointer-equivalency of the result IL. */
3646 capture_info
cinfo1 (s1
, o1
, true);
3647 capture_info
cinfo2 (s2
, o2
, true);
3649 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3650 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3653 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3655 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3656 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3657 || (cinfo1
.info
[i
].force_no_side_effects_p
3658 != cinfo2
.info
[i
].force_no_side_effects_p
)
3659 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3660 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3661 /* toplevel_msk is an optimization */
3662 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3663 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3664 /* the pointer back to the capture is for diagnostics only */)
3668 /* ??? Deep-compare the actual result. */
3673 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3674 const key_type
&candidate
)
3676 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3680 /* Main entry to generate code for matching GIMPLE IL off the decision
3684 decision_tree::gen (FILE *f
, bool gimple
)
3690 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3691 "a total number of %u nodes\n",
3692 gimple
? "GIMPLE" : "GENERIC",
3693 root
->num_leafs
, root
->max_level
, root
->total_size
);
3695 /* First split out the transform part of equal leafs. */
3698 for (sinfo_map_t::iterator iter
= si
.begin ();
3699 iter
!= si
.end (); ++iter
)
3701 sinfo
*s
= (*iter
).second
;
3702 /* Do not split out single uses. */
3709 fprintf (stderr
, "found %u uses of", s
->cnt
);
3710 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3713 /* Generate a split out function with the leaf transform code. */
3714 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3717 fprintf (f
, "\nstatic bool\n"
3718 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3719 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3720 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3725 fprintf (f
, "\nstatic tree\n"
3726 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3727 (*iter
).second
->fname
);
3728 for (unsigned i
= 0;
3729 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3730 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3731 fprintf (f
, " tree *captures\n");
3733 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3735 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3737 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3738 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3739 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3740 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3741 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3742 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3745 fprintf (f
, ")\n{\n");
3746 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3748 fprintf (f
, " return false;\n");
3750 fprintf (f
, " return NULL_TREE;\n");
3753 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3755 for (unsigned n
= 1; n
<= 5; ++n
)
3757 /* First generate split-out functions. */
3758 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3760 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3761 expr
*e
= static_cast<expr
*>(dop
->op
);
3762 if (e
->ops
.length () != n
3763 /* Builtin simplifications are somewhat premature on
3764 GENERIC. The following drops patterns with outermost
3765 calls. It's easy to emit overloads for function code
3766 though if necessary. */
3768 && e
->operation
->kind
!= id_base::CODE
))
3772 fprintf (f
, "\nstatic bool\n"
3773 "gimple_simplify_%s (gimple_match_op *res_op,"
3774 " gimple_seq *seq,\n"
3775 " tree (*valueize)(tree) "
3776 "ATTRIBUTE_UNUSED,\n"
3777 " code_helper ARG_UNUSED (code), tree "
3778 "ARG_UNUSED (type)\n",
3781 fprintf (f
, "\nstatic tree\n"
3782 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3783 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3785 for (unsigned i
= 0; i
< n
; ++i
)
3786 fprintf (f
, ", tree op%d", i
);
3789 dop
->gen_kids (f
, 2, gimple
);
3791 fprintf (f
, " return false;\n");
3793 fprintf (f
, " return NULL_TREE;\n");
3797 /* Then generate the main entry with the outermost switch and
3798 tail-calls to the split-out functions. */
3800 fprintf (f
, "\nstatic bool\n"
3801 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3802 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3803 " code_helper code, const tree type");
3805 fprintf (f
, "\ntree\n"
3806 "generic_simplify (location_t loc, enum tree_code code, "
3807 "const tree type ATTRIBUTE_UNUSED");
3808 for (unsigned i
= 0; i
< n
; ++i
)
3809 fprintf (f
, ", tree op%d", i
);
3814 fprintf (f
, " switch (code.get_rep())\n"
3817 fprintf (f
, " switch (code)\n"
3819 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3821 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3822 expr
*e
= static_cast<expr
*>(dop
->op
);
3823 if (e
->ops
.length () != n
3824 /* Builtin simplifications are somewhat premature on
3825 GENERIC. The following drops patterns with outermost
3826 calls. It's easy to emit overloads for function code
3827 though if necessary. */
3829 && e
->operation
->kind
!= id_base::CODE
))
3832 if (*e
->operation
== CONVERT_EXPR
3833 || *e
->operation
== NOP_EXPR
)
3834 fprintf (f
, " CASE_CONVERT:\n");
3836 fprintf (f
, " case %s%s:\n",
3837 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3840 fprintf (f
, " return gimple_simplify_%s (res_op, "
3841 "seq, valueize, code, type", e
->operation
->id
);
3843 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3845 for (unsigned i
= 0; i
< n
; ++i
)
3846 fprintf (f
, ", op%d", i
);
3847 fprintf (f
, ");\n");
3849 fprintf (f
, " default:;\n"
3853 fprintf (f
, " return false;\n");
3855 fprintf (f
, " return NULL_TREE;\n");
3860 /* Output code to implement the predicate P from the decision tree DT. */
3863 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3865 fprintf (f
, "\nbool\n"
3866 "%s%s (tree t%s%s)\n"
3867 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3868 p
->nargs
> 0 ? ", tree *res_ops" : "",
3869 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3870 /* Conveniently make 'type' available. */
3871 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3874 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3875 dt
.root
->gen_kids (f
, 2, gimple
);
3877 fprintf_indent (f
, 2, "return false;\n"
3881 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3884 write_header (FILE *f
, const char *head
)
3886 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3887 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3889 /* Include the header instead of writing it awkwardly quoted here. */
3890 fprintf (f
, "\n#include \"%s\"\n", head
);
3900 parser (cpp_reader
*);
3903 const cpp_token
*next ();
3904 const cpp_token
*peek (unsigned = 1);
3905 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3906 const cpp_token
*expect (enum cpp_ttype
);
3907 const cpp_token
*eat_token (enum cpp_ttype
);
3908 const char *get_string ();
3909 const char *get_ident ();
3910 const cpp_token
*eat_ident (const char *);
3911 const char *get_number ();
3913 unsigned get_internal_capture_id ();
3915 id_base
*parse_operation ();
3916 operand
*parse_capture (operand
*, bool);
3917 operand
*parse_expr ();
3918 c_expr
*parse_c_expr (cpp_ttype
);
3919 operand
*parse_op ();
3921 void record_operlist (source_location
, user_id
*);
3923 void parse_pattern ();
3924 operand
*parse_result (operand
*, predicate_id
*);
3925 void push_simplify (simplify::simplify_kind
,
3926 vec
<simplify
*>&, operand
*, operand
*);
3927 void parse_simplify (simplify::simplify_kind
,
3928 vec
<simplify
*>&, predicate_id
*, operand
*);
3929 void parse_for (source_location
);
3930 void parse_if (source_location
);
3931 void parse_predicates (source_location
);
3932 void parse_operator_list (source_location
);
3934 void finish_match_operand (operand
*);
3937 vec
<c_expr
*> active_ifs
;
3938 vec
<vec
<user_id
*> > active_fors
;
3939 hash_set
<user_id
*> *oper_lists_set
;
3940 vec
<user_id
*> oper_lists
;
3942 cid_map_t
*capture_ids
;
3946 vec
<simplify
*> simplifiers
;
3947 vec
<predicate_id
*> user_predicates
;
3948 bool parsing_match_operand
;
3951 /* Lexing helpers. */
3953 /* Read the next non-whitespace token from R. */
3958 const cpp_token
*token
;
3961 token
= cpp_get_token (r
);
3963 while (token
->type
== CPP_PADDING
);
3967 /* Peek at the next non-whitespace token from R. */
3970 parser::peek (unsigned num
)
3972 const cpp_token
*token
;
3976 token
= cpp_peek_token (r
, i
++);
3978 while (token
->type
== CPP_PADDING
3980 /* If we peek at EOF this is a fatal error as it leaves the
3981 cpp_reader in unusable state. Assume we really wanted a
3982 token and thus this EOF is unexpected. */
3983 if (token
->type
== CPP_EOF
)
3984 fatal_at (token
, "unexpected end of file");
3988 /* Peek at the next identifier token (or return NULL if the next
3989 token is not an identifier or equal to ID if supplied). */
3992 parser::peek_ident (const char *id
, unsigned num
)
3994 const cpp_token
*token
= peek (num
);
3995 if (token
->type
!= CPP_NAME
)
4001 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4002 if (strcmp (id
, t
) == 0)
4008 /* Read the next token from R and assert it is of type TK. */
4011 parser::expect (enum cpp_ttype tk
)
4013 const cpp_token
*token
= next ();
4014 if (token
->type
!= tk
)
4015 fatal_at (token
, "expected %s, got %s",
4016 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4021 /* Consume the next token from R and assert it is of type TK. */
4024 parser::eat_token (enum cpp_ttype tk
)
4029 /* Read the next token from R and assert it is of type CPP_STRING and
4030 return its value. */
4033 parser::get_string ()
4035 const cpp_token
*token
= expect (CPP_STRING
);
4036 return (const char *)token
->val
.str
.text
;
4039 /* Read the next token from R and assert it is of type CPP_NAME and
4040 return its value. */
4043 parser::get_ident ()
4045 const cpp_token
*token
= expect (CPP_NAME
);
4046 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4049 /* Eat an identifier token with value S from R. */
4052 parser::eat_ident (const char *s
)
4054 const cpp_token
*token
= peek ();
4055 const char *t
= get_ident ();
4056 if (strcmp (s
, t
) != 0)
4057 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4061 /* Read the next token from R and assert it is of type CPP_NUMBER and
4062 return its value. */
4065 parser::get_number ()
4067 const cpp_token
*token
= expect (CPP_NUMBER
);
4068 return (const char *)token
->val
.str
.text
;
4071 /* Return a capture ID that can be used internally. */
4074 parser::get_internal_capture_id ()
4076 unsigned newid
= capture_ids
->elements ();
4077 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4080 sprintf (id
, "__%u", newid
);
4081 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4083 fatal ("reserved capture id '%s' already used", id
);
4087 /* Record an operator-list use for transparent for handling. */
4090 parser::record_operlist (source_location loc
, user_id
*p
)
4092 if (!oper_lists_set
->add (p
))
4094 if (!oper_lists
.is_empty ()
4095 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4096 fatal_at (loc
, "User-defined operator list does not have the "
4097 "same number of entries as others used in the pattern");
4098 oper_lists
.safe_push (p
);
4102 /* Parse the operator ID, special-casing convert?, convert1? and
4106 parser::parse_operation ()
4108 const cpp_token
*id_tok
= peek ();
4109 const char *id
= get_ident ();
4110 const cpp_token
*token
= peek ();
4111 if (strcmp (id
, "convert0") == 0)
4112 fatal_at (id_tok
, "use 'convert?' here");
4113 else if (strcmp (id
, "view_convert0") == 0)
4114 fatal_at (id_tok
, "use 'view_convert?' here");
4115 if (token
->type
== CPP_QUERY
4116 && !(token
->flags
& PREV_WHITE
))
4118 if (strcmp (id
, "convert") == 0)
4120 else if (strcmp (id
, "convert1") == 0)
4122 else if (strcmp (id
, "convert2") == 0)
4124 else if (strcmp (id
, "view_convert") == 0)
4125 id
= "view_convert0";
4126 else if (strcmp (id
, "view_convert1") == 0)
4128 else if (strcmp (id
, "view_convert2") == 0)
4131 fatal_at (id_tok
, "non-convert operator conditionalized");
4133 if (!parsing_match_operand
)
4134 fatal_at (id_tok
, "conditional convert can only be used in "
4135 "match expression");
4136 eat_token (CPP_QUERY
);
4138 else if (strcmp (id
, "convert1") == 0
4139 || strcmp (id
, "convert2") == 0
4140 || strcmp (id
, "view_convert1") == 0
4141 || strcmp (id
, "view_convert2") == 0)
4142 fatal_at (id_tok
, "expected '?' after conditional operator");
4143 id_base
*op
= get_operator (id
);
4145 fatal_at (id_tok
, "unknown operator %s", id
);
4147 user_id
*p
= dyn_cast
<user_id
*> (op
);
4148 if (p
&& p
->is_oper_list
)
4150 if (active_fors
.length() == 0)
4151 record_operlist (id_tok
->src_loc
, p
);
4153 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
4159 capture = '@'<number> */
4162 parser::parse_capture (operand
*op
, bool require_existing
)
4164 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4165 const cpp_token
*token
= peek ();
4166 const char *id
= NULL
;
4167 bool value_match
= false;
4168 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4169 if (token
->type
== CPP_ATSIGN
4170 && ! (token
->flags
& PREV_WHITE
)
4171 && parsing_match_operand
)
4173 eat_token (CPP_ATSIGN
);
4177 if (token
->type
== CPP_NUMBER
)
4179 else if (token
->type
== CPP_NAME
)
4182 fatal_at (token
, "expected number or identifier");
4183 unsigned next_id
= capture_ids
->elements ();
4185 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4188 if (require_existing
)
4189 fatal_at (src_loc
, "unknown capture id");
4192 return new capture (src_loc
, num
, op
, value_match
);
4195 /* Parse an expression
4196 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4199 parser::parse_expr ()
4201 const cpp_token
*token
= peek ();
4202 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4205 bool is_commutative
= false;
4206 bool force_capture
= false;
4207 const char *expr_type
= NULL
;
4209 if (token
->type
== CPP_COLON
4210 && !(token
->flags
& PREV_WHITE
))
4212 eat_token (CPP_COLON
);
4214 if (token
->type
== CPP_NAME
4215 && !(token
->flags
& PREV_WHITE
))
4217 const char *s
= get_ident ();
4218 if (!parsing_match_operand
)
4228 = dyn_cast
<operator_id
*> (e
->operation
))
4230 if (!commutative_tree_code (p
->code
)
4231 && !comparison_code_p (p
->code
))
4232 fatal_at (token
, "operation is not commutative");
4234 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4235 for (unsigned i
= 0;
4236 i
< p
->substitutes
.length (); ++i
)
4239 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4241 if (!commutative_tree_code (q
->code
)
4242 && !comparison_code_p (q
->code
))
4243 fatal_at (token
, "operation %s is not "
4244 "commutative", q
->id
);
4247 is_commutative
= true;
4249 else if (*sp
== 'C')
4250 is_commutative
= true;
4251 else if (*sp
== 's')
4253 e
->force_single_use
= true;
4254 force_capture
= true;
4257 fatal_at (token
, "flag %c not recognized", *sp
);
4264 fatal_at (token
, "expected flag or type specifying identifier");
4267 if (token
->type
== CPP_ATSIGN
4268 && !(token
->flags
& PREV_WHITE
))
4269 op
= parse_capture (e
, false);
4270 else if (force_capture
)
4272 unsigned num
= get_internal_capture_id ();
4273 op
= new capture (token
->src_loc
, num
, e
, false);
4279 const cpp_token
*token
= peek ();
4280 if (token
->type
== CPP_CLOSE_PAREN
)
4282 if (e
->operation
->nargs
!= -1
4283 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4284 fatal_at (token
, "'%s' expects %u operands, not %u",
4285 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4288 if (e
->ops
.length () == 2
4289 || commutative_op (e
->operation
) >= 0)
4290 e
->is_commutative
= true;
4292 fatal_at (token
, "only binary operators or functions with "
4293 "two arguments can be marked commutative, "
4294 "unless the operation is known to be inherently "
4297 e
->expr_type
= expr_type
;
4300 else if (!(token
->flags
& PREV_WHITE
))
4301 fatal_at (token
, "expected expression operand");
4303 e
->append_op (parse_op ());
4308 /* Lex native C code delimited by START recording the preprocessing tokens
4309 for later processing.
4310 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4313 parser::parse_c_expr (cpp_ttype start
)
4315 const cpp_token
*token
;
4318 vec
<cpp_token
> code
= vNULL
;
4319 unsigned nr_stmts
= 0;
4320 source_location loc
= eat_token (start
)->src_loc
;
4321 if (start
== CPP_OPEN_PAREN
)
4322 end
= CPP_CLOSE_PAREN
;
4323 else if (start
== CPP_OPEN_BRACE
)
4324 end
= CPP_CLOSE_BRACE
;
4332 /* Count brace pairs to find the end of the expr to match. */
4333 if (token
->type
== start
)
4335 else if (token
->type
== end
4338 else if (token
->type
== CPP_EOF
)
4339 fatal_at (token
, "unexpected end of file");
4341 /* This is a lame way of counting the number of statements. */
4342 if (token
->type
== CPP_SEMICOLON
)
4345 /* If this is possibly a user-defined identifier mark it used. */
4346 if (token
->type
== CPP_NAME
)
4348 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4349 (token
->val
.node
.node
)->ident
.str
);
4351 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4352 record_operlist (token
->src_loc
, p
);
4355 /* Record the token. */
4356 code
.safe_push (*token
);
4359 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4362 /* Parse an operand which is either an expression, a predicate or
4363 a standalone capture.
4364 op = predicate | expr | c_expr | capture */
4369 const cpp_token
*token
= peek ();
4370 struct operand
*op
= NULL
;
4371 if (token
->type
== CPP_OPEN_PAREN
)
4373 eat_token (CPP_OPEN_PAREN
);
4375 eat_token (CPP_CLOSE_PAREN
);
4377 else if (token
->type
== CPP_OPEN_BRACE
)
4379 op
= parse_c_expr (CPP_OPEN_BRACE
);
4383 /* Remaining ops are either empty or predicates */
4384 if (token
->type
== CPP_NAME
)
4386 const char *id
= get_ident ();
4387 id_base
*opr
= get_operator (id
);
4389 fatal_at (token
, "expected predicate name");
4390 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4392 if (code
->nargs
!= 0)
4393 fatal_at (token
, "using an operator with operands as predicate");
4394 /* Parse the zero-operand operator "predicates" as
4396 op
= new expr (opr
, token
->src_loc
);
4398 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4400 if (code
->nargs
!= 0)
4401 fatal_at (token
, "using an operator with operands as predicate");
4402 /* Parse the zero-operand operator "predicates" as
4404 op
= new expr (opr
, token
->src_loc
);
4406 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4407 op
= new predicate (p
, token
->src_loc
);
4409 fatal_at (token
, "using an unsupported operator as predicate");
4410 if (!parsing_match_operand
)
4411 fatal_at (token
, "predicates are only allowed in match expression");
4413 if (token
->flags
& PREV_WHITE
)
4416 else if (token
->type
!= CPP_COLON
4417 && token
->type
!= CPP_ATSIGN
)
4418 fatal_at (token
, "expected expression or predicate");
4419 /* optionally followed by a capture and a predicate. */
4420 if (token
->type
== CPP_COLON
)
4421 fatal_at (token
, "not implemented: predicate on leaf operand");
4422 if (token
->type
== CPP_ATSIGN
)
4423 op
= parse_capture (op
, !parsing_match_operand
);
4429 /* Create a new simplify from the current parsing state and MATCH,
4430 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4433 parser::push_simplify (simplify::simplify_kind kind
,
4434 vec
<simplify
*>& simplifiers
,
4435 operand
*match
, operand
*result
)
4437 /* Build and push a temporary for operator list uses in expressions. */
4438 if (!oper_lists
.is_empty ())
4439 active_fors
.safe_push (oper_lists
);
4441 simplifiers
.safe_push
4442 (new simplify (kind
, last_id
++, match
, result
,
4443 active_fors
.copy (), capture_ids
));
4445 if (!oper_lists
.is_empty ())
4450 <result-op> = <op> | <if> | <with>
4451 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4452 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4456 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4458 const cpp_token
*token
= peek ();
4459 if (token
->type
!= CPP_OPEN_PAREN
)
4462 eat_token (CPP_OPEN_PAREN
);
4463 if (peek_ident ("if"))
4466 if_expr
*ife
= new if_expr (token
->src_loc
);
4467 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4468 if (peek ()->type
== CPP_OPEN_PAREN
)
4470 ife
->trueexpr
= parse_result (result
, matcher
);
4471 if (peek ()->type
== CPP_OPEN_PAREN
)
4472 ife
->falseexpr
= parse_result (result
, matcher
);
4473 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4474 ife
->falseexpr
= parse_op ();
4476 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4478 ife
->trueexpr
= parse_op ();
4479 if (peek ()->type
== CPP_OPEN_PAREN
)
4480 ife
->falseexpr
= parse_result (result
, matcher
);
4481 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4482 ife
->falseexpr
= parse_op ();
4484 /* If this if is immediately closed then it contains a
4485 manual matcher or is part of a predicate definition. */
4486 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4489 fatal_at (peek (), "manual transform not implemented");
4490 ife
->trueexpr
= result
;
4492 eat_token (CPP_CLOSE_PAREN
);
4495 else if (peek_ident ("with"))
4498 with_expr
*withe
= new with_expr (token
->src_loc
);
4499 /* Parse (with c-expr expr) as (if-with (true) expr). */
4500 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4501 withe
->with
->nr_stmts
= 0;
4502 withe
->subexpr
= parse_result (result
, matcher
);
4503 eat_token (CPP_CLOSE_PAREN
);
4506 else if (peek_ident ("switch"))
4508 token
= eat_ident ("switch");
4509 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4511 if_expr
*ife
= new if_expr (ifloc
);
4513 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4514 if (peek ()->type
== CPP_OPEN_PAREN
)
4515 ife
->trueexpr
= parse_result (result
, matcher
);
4517 ife
->trueexpr
= parse_op ();
4518 eat_token (CPP_CLOSE_PAREN
);
4519 if (peek ()->type
!= CPP_OPEN_PAREN
4520 || !peek_ident ("if", 2))
4521 fatal_at (token
, "switch can be implemented with a single if");
4522 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4524 if (peek ()->type
== CPP_OPEN_PAREN
)
4526 if (peek_ident ("if", 2))
4528 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4530 ife
->falseexpr
= new if_expr (ifloc
);
4531 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4532 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4533 if (peek ()->type
== CPP_OPEN_PAREN
)
4534 ife
->trueexpr
= parse_result (result
, matcher
);
4536 ife
->trueexpr
= parse_op ();
4537 eat_token (CPP_CLOSE_PAREN
);
4541 /* switch default clause */
4542 ife
->falseexpr
= parse_result (result
, matcher
);
4543 eat_token (CPP_CLOSE_PAREN
);
4549 /* switch default clause */
4550 ife
->falseexpr
= parse_op ();
4551 eat_token (CPP_CLOSE_PAREN
);
4555 eat_token (CPP_CLOSE_PAREN
);
4560 operand
*op
= result
;
4563 eat_token (CPP_CLOSE_PAREN
);
4569 simplify = 'simplify' <expr> <result-op>
4571 match = 'match' <ident> <expr> [<result-op>]
4572 and fill SIMPLIFIERS with the results. */
4575 parser::parse_simplify (simplify::simplify_kind kind
,
4576 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4579 /* Reset the capture map. */
4581 capture_ids
= new cid_map_t
;
4582 /* Reset oper_lists and set. */
4583 hash_set
<user_id
*> olist
;
4584 oper_lists_set
= &olist
;
4587 const cpp_token
*loc
= peek ();
4588 parsing_match_operand
= true;
4589 struct operand
*match
= parse_op ();
4590 finish_match_operand (match
);
4591 parsing_match_operand
= false;
4592 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4593 fatal_at (loc
, "outermost expression cannot be captured");
4594 if (match
->type
== operand::OP_EXPR
4595 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4596 fatal_at (loc
, "outermost expression cannot be a predicate");
4598 /* Splice active_ifs onto result and continue parsing the
4600 if_expr
*active_if
= NULL
;
4601 for (int i
= active_ifs
.length (); i
> 0; --i
)
4603 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4604 ifc
->cond
= active_ifs
[i
-1];
4605 ifc
->trueexpr
= active_if
;
4608 if_expr
*outermost_if
= active_if
;
4609 while (active_if
&& active_if
->trueexpr
)
4610 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4612 const cpp_token
*token
= peek ();
4614 /* If this if is immediately closed then it is part of a predicate
4615 definition. Push it. */
4616 if (token
->type
== CPP_CLOSE_PAREN
)
4619 fatal_at (token
, "expected transform expression");
4622 active_if
->trueexpr
= result
;
4623 result
= outermost_if
;
4625 push_simplify (kind
, simplifiers
, match
, result
);
4629 operand
*tem
= parse_result (result
, matcher
);
4632 active_if
->trueexpr
= tem
;
4633 result
= outermost_if
;
4638 push_simplify (kind
, simplifiers
, match
, result
);
4641 /* Parsing of the outer control structures. */
4643 /* Parse a for expression
4644 for = '(' 'for' <subst>... <pattern> ')'
4645 subst = <ident> '(' <ident>... ')' */
4648 parser::parse_for (source_location
)
4650 auto_vec
<const cpp_token
*> user_id_tokens
;
4651 vec
<user_id
*> user_ids
= vNULL
;
4652 const cpp_token
*token
;
4653 unsigned min_n_opers
= 0, max_n_opers
= 0;
4658 if (token
->type
!= CPP_NAME
)
4661 /* Insert the user defined operators into the operator hash. */
4662 const char *id
= get_ident ();
4663 if (get_operator (id
, true) != NULL
)
4664 fatal_at (token
, "operator already defined");
4665 user_id
*op
= new user_id (id
);
4666 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4668 user_ids
.safe_push (op
);
4669 user_id_tokens
.safe_push (token
);
4671 eat_token (CPP_OPEN_PAREN
);
4674 while ((token
= peek_ident ()) != 0)
4676 const char *oper
= get_ident ();
4677 id_base
*idb
= get_operator (oper
, true);
4679 fatal_at (token
, "no such operator '%s'", oper
);
4680 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4681 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4682 || *idb
== VIEW_CONVERT2
)
4683 fatal_at (token
, "conditional operators cannot be used inside for");
4687 else if (idb
->nargs
== -1)
4689 else if (idb
->nargs
!= arity
)
4690 fatal_at (token
, "operator '%s' with arity %d does not match "
4691 "others with arity %d", oper
, idb
->nargs
, arity
);
4693 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4696 if (p
->is_oper_list
)
4697 op
->substitutes
.safe_splice (p
->substitutes
);
4699 fatal_at (token
, "iterator cannot be used as operator-list");
4702 op
->substitutes
.safe_push (idb
);
4705 token
= expect (CPP_CLOSE_PAREN
);
4707 unsigned nsubstitutes
= op
->substitutes
.length ();
4708 if (nsubstitutes
== 0)
4709 fatal_at (token
, "A user-defined operator must have at least "
4710 "one substitution");
4711 if (max_n_opers
== 0)
4713 min_n_opers
= nsubstitutes
;
4714 max_n_opers
= nsubstitutes
;
4718 if (nsubstitutes
% min_n_opers
!= 0
4719 && min_n_opers
% nsubstitutes
!= 0)
4720 fatal_at (token
, "All user-defined identifiers must have a "
4721 "multiple number of operator substitutions of the "
4722 "smallest number of substitutions");
4723 if (nsubstitutes
< min_n_opers
)
4724 min_n_opers
= nsubstitutes
;
4725 else if (nsubstitutes
> max_n_opers
)
4726 max_n_opers
= nsubstitutes
;
4730 unsigned n_ids
= user_ids
.length ();
4732 fatal_at (token
, "for requires at least one user-defined identifier");
4735 if (token
->type
== CPP_CLOSE_PAREN
)
4736 fatal_at (token
, "no pattern defined in for");
4738 active_fors
.safe_push (user_ids
);
4742 if (token
->type
== CPP_CLOSE_PAREN
)
4748 /* Remove user-defined operators from the hash again. */
4749 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4751 if (!user_ids
[i
]->used
)
4752 warning_at (user_id_tokens
[i
],
4753 "operator %s defined but not used", user_ids
[i
]->id
);
4754 operators
->remove_elt (user_ids
[i
]);
4758 /* Parse an identifier associated with a list of operators.
4759 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4762 parser::parse_operator_list (source_location
)
4764 const cpp_token
*token
= peek ();
4765 const char *id
= get_ident ();
4767 if (get_operator (id
, true) != 0)
4768 fatal_at (token
, "operator %s already defined", id
);
4770 user_id
*op
= new user_id (id
, true);
4773 while ((token
= peek_ident ()) != 0)
4776 const char *oper
= get_ident ();
4777 id_base
*idb
= get_operator (oper
, true);
4780 fatal_at (token
, "no such operator '%s'", oper
);
4784 else if (idb
->nargs
== -1)
4786 else if (arity
!= idb
->nargs
)
4787 fatal_at (token
, "operator '%s' with arity %d does not match "
4788 "others with arity %d", oper
, idb
->nargs
, arity
);
4790 /* We allow composition of multiple operator lists. */
4791 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4792 op
->substitutes
.safe_splice (p
->substitutes
);
4794 op
->substitutes
.safe_push (idb
);
4797 // Check that there is no junk after id-list
4799 if (token
->type
!= CPP_CLOSE_PAREN
)
4800 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4802 if (op
->substitutes
.length () == 0)
4803 fatal_at (token
, "operator-list cannot be empty");
4806 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4810 /* Parse an outer if expression.
4811 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4814 parser::parse_if (source_location
)
4816 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4818 const cpp_token
*token
= peek ();
4819 if (token
->type
== CPP_CLOSE_PAREN
)
4820 fatal_at (token
, "no pattern defined in if");
4822 active_ifs
.safe_push (ifexpr
);
4825 const cpp_token
*token
= peek ();
4826 if (token
->type
== CPP_CLOSE_PAREN
)
4834 /* Parse a list of predefined predicate identifiers.
4835 preds = '(' 'define_predicates' <ident>... ')' */
4838 parser::parse_predicates (source_location
)
4842 const cpp_token
*token
= peek ();
4843 if (token
->type
!= CPP_NAME
)
4846 add_predicate (get_ident ());
4851 /* Parse outer control structures.
4852 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4855 parser::parse_pattern ()
4857 /* All clauses start with '('. */
4858 eat_token (CPP_OPEN_PAREN
);
4859 const cpp_token
*token
= peek ();
4860 const char *id
= get_ident ();
4861 if (strcmp (id
, "simplify") == 0)
4863 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4866 else if (strcmp (id
, "match") == 0)
4868 bool with_args
= false;
4869 source_location e_loc
= peek ()->src_loc
;
4870 if (peek ()->type
== CPP_OPEN_PAREN
)
4872 eat_token (CPP_OPEN_PAREN
);
4875 const char *name
= get_ident ();
4876 id_base
*id
= get_operator (name
);
4880 p
= add_predicate (name
);
4881 user_predicates
.safe_push (p
);
4883 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4886 fatal_at (token
, "cannot add a match to a non-predicate ID");
4887 /* Parse (match <id> <arg>... (match-expr)) here. */
4891 capture_ids
= new cid_map_t
;
4892 e
= new expr (p
, e_loc
);
4893 while (peek ()->type
== CPP_ATSIGN
)
4894 e
->append_op (parse_capture (NULL
, false));
4895 eat_token (CPP_CLOSE_PAREN
);
4898 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4899 || (!e
&& p
->nargs
!= 0)))
4900 fatal_at (token
, "non-matching number of match operands");
4901 p
->nargs
= e
? e
->ops
.length () : 0;
4902 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4905 else if (strcmp (id
, "for") == 0)
4906 parse_for (token
->src_loc
);
4907 else if (strcmp (id
, "if") == 0)
4908 parse_if (token
->src_loc
);
4909 else if (strcmp (id
, "define_predicates") == 0)
4911 if (active_ifs
.length () > 0
4912 || active_fors
.length () > 0)
4913 fatal_at (token
, "define_predicates inside if or for is not supported");
4914 parse_predicates (token
->src_loc
);
4916 else if (strcmp (id
, "define_operator_list") == 0)
4918 if (active_ifs
.length () > 0
4919 || active_fors
.length () > 0)
4920 fatal_at (token
, "operator-list inside if or for is not supported");
4921 parse_operator_list (token
->src_loc
);
4924 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4925 active_ifs
.length () == 0 && active_fors
.length () == 0
4926 ? "'define_predicates', " : "");
4928 eat_token (CPP_CLOSE_PAREN
);
4931 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4935 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4940 if (capture
*c
= dyn_cast
<capture
*> (op
))
4942 cpts
[c
->where
].safe_push (c
);
4943 walk_captures (c
->what
, cpts
);
4945 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4946 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4947 walk_captures (e
->ops
[i
], cpts
);
4950 /* Finish up OP which is a match operand. */
4953 parser::finish_match_operand (operand
*op
)
4955 /* Look for matching captures, diagnose mis-uses of @@ and apply
4956 early lowering and distribution of value_match. */
4957 auto_vec
<vec
<capture
*> > cpts
;
4958 cpts
.safe_grow_cleared (capture_ids
->elements ());
4959 walk_captures (op
, cpts
);
4960 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4962 capture
*value_match
= NULL
;
4963 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4965 if (cpts
[i
][j
]->value_match
)
4968 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4969 value_match
= cpts
[i
][j
];
4972 if (cpts
[i
].length () == 1 && value_match
)
4973 fatal_at (value_match
->location
, "@@ without a matching capture");
4976 /* Duplicate prevailing capture with the existing ID, create
4977 a fake ID and rewrite all captures to use it. This turns
4978 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4979 value_match
->what
= new capture (value_match
->location
,
4981 value_match
->what
, false);
4982 /* Create a fake ID and rewrite all captures to use it. */
4983 unsigned newid
= get_internal_capture_id ();
4984 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4986 cpts
[i
][j
]->where
= newid
;
4987 cpts
[i
][j
]->value_match
= true;
4994 /* Main entry of the parser. Repeatedly parse outer control structures. */
4996 parser::parser (cpp_reader
*r_
)
5000 active_fors
= vNULL
;
5001 simplifiers
= vNULL
;
5002 oper_lists_set
= NULL
;
5005 user_predicates
= vNULL
;
5006 parsing_match_operand
= false;
5009 const cpp_token
*token
= next ();
5010 while (token
->type
!= CPP_EOF
)
5012 _cpp_backup_tokens (r
, 1);
5019 /* Helper for the linemap code. */
5022 round_alloc_size (size_t s
)
5028 /* The genmatch generator progam. It reads from a pattern description
5029 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5032 main (int argc
, char **argv
)
5036 progname
= "genmatch";
5042 char *input
= argv
[argc
-1];
5043 for (int i
= 1; i
< argc
- 1; ++i
)
5045 if (strcmp (argv
[i
], "--gimple") == 0)
5047 else if (strcmp (argv
[i
], "--generic") == 0)
5049 else if (strcmp (argv
[i
], "-v") == 0)
5051 else if (strcmp (argv
[i
], "-vv") == 0)
5055 fprintf (stderr
, "Usage: genmatch "
5056 "[--gimple] [--generic] [-v[v]] input\n");
5061 line_table
= XCNEW (struct line_maps
);
5062 linemap_init (line_table
, 0);
5063 line_table
->reallocator
= xrealloc
;
5064 line_table
->round_alloc_size
= round_alloc_size
;
5066 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5067 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5068 cb
->error
= error_cb
;
5070 /* Add the build directory to the #include "" search path. */
5071 cpp_dir
*dir
= XCNEW (cpp_dir
);
5072 dir
->name
= getpwd ();
5074 dir
->name
= ASTRDUP (".");
5075 cpp_set_include_chains (r
, dir
, NULL
, false);
5077 if (!cpp_read_main_file (r
, input
))
5079 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5080 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5082 null_id
= new id_base (id_base::NULL_ID
, "null");
5084 /* Pre-seed operators. */
5085 operators
= new hash_table
<id_base
> (1024);
5086 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5087 add_operator (SYM, # SYM, # TYPE, NARGS);
5088 #define END_OF_BASE_TREE_CODES
5090 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5091 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5092 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5093 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5094 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5095 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5096 #undef END_OF_BASE_TREE_CODES
5099 /* Pre-seed builtin functions.
5100 ??? Cannot use N (name) as that is targetm.emultls.get_address
5101 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5102 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5103 add_function (ENUM, "CFN_" # ENUM);
5104 #include "builtins.def"
5106 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5107 add_function (IFN_##CODE, "CFN_" #CODE);
5108 #include "internal-fn.def"
5114 write_header (stdout
, "gimple-match-head.c");
5116 write_header (stdout
, "generic-match-head.c");
5118 /* Go over all predicates defined with patterns and perform
5119 lowering and code generation. */
5120 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5122 predicate_id
*pred
= p
.user_predicates
[i
];
5123 lower (pred
->matchers
, gimple
);
5126 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5127 print_matches (pred
->matchers
[i
]);
5130 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5131 dt
.insert (pred
->matchers
[i
], i
);
5136 write_predicate (stdout
, pred
, dt
, gimple
);
5139 /* Lower the main simplifiers and generate code for them. */
5140 lower (p
.simplifiers
, gimple
);
5143 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5144 print_matches (p
.simplifiers
[i
]);
5147 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5148 dt
.insert (p
.simplifiers
[i
], i
);
5153 dt
.gen (stdout
, gimple
);
5156 cpp_finish (r
, NULL
);