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, bool fnargs
= 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
)))
207 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
209 fprintf (f
, "%s:%d", file
, loc
.line
);
212 /* Other gen programs really output line directives here, at least for
213 development it's right now more convenient to have line information
214 from the generated file. Still keep the directives as comment for now
215 to easily back-point to the meta-description. */
216 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
220 /* Pull in tree codes and builtin function codes from their
223 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
236 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
237 enum built_in_function
{
238 #include "builtins.def"
242 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
244 #include "internal-fn.def"
249 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
250 CFN_##ENUM = int (ENUM),
251 #include "builtins.def"
253 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
254 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
255 #include "internal-fn.def"
260 #include "case-cfn-macros.h"
262 /* Return true if CODE represents a commutative tree code. Otherwise
265 commutative_tree_code (enum tree_code code
)
271 case MULT_HIGHPART_EXPR
:
286 case WIDEN_MULT_EXPR
:
287 case VEC_WIDEN_MULT_HI_EXPR
:
288 case VEC_WIDEN_MULT_LO_EXPR
:
289 case VEC_WIDEN_MULT_EVEN_EXPR
:
290 case VEC_WIDEN_MULT_ODD_EXPR
:
299 /* Return true if CODE represents a ternary tree code for which the
300 first two operands are commutative. Otherwise return false. */
302 commutative_ternary_tree_code (enum tree_code code
)
306 case WIDEN_MULT_PLUS_EXPR
:
307 case WIDEN_MULT_MINUS_EXPR
:
317 /* Return true if CODE is a comparison. */
320 comparison_code_p (enum tree_code code
)
347 /* Base class for all identifiers the parser knows. */
349 struct id_base
: nofree_ptr_hash
<id_base
>
351 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
353 id_base (id_kind
, const char *, int = -1);
359 /* hash_table support. */
360 static inline hashval_t
hash (const id_base
*);
361 static inline int equal (const id_base
*, const id_base
*);
365 id_base::hash (const id_base
*op
)
371 id_base::equal (const id_base
*op1
,
374 return (op1
->hashval
== op2
->hashval
375 && strcmp (op1
->id
, op2
->id
) == 0);
378 /* The special id "null", which matches nothing. */
379 static id_base
*null_id
;
381 /* Hashtable of known pattern operators. This is pre-seeded from
382 all known tree codes and all known builtin function ids. */
383 static hash_table
<id_base
> *operators
;
385 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
390 hashval
= htab_hash_string (id
);
393 /* Identifier that maps to a tree code. */
395 struct operator_id
: public id_base
397 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
399 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
404 /* Identifier that maps to a builtin or internal function code. */
406 struct fn_id
: public id_base
408 fn_id (enum built_in_function fn_
, const char *id_
)
409 : id_base (id_base::FN
, id_
), fn (fn_
) {}
410 fn_id (enum internal_fn fn_
, const char *id_
)
411 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
417 /* Identifier that maps to a user-defined predicate. */
419 struct predicate_id
: public id_base
421 predicate_id (const char *id_
)
422 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
423 vec
<simplify
*> matchers
;
426 /* Identifier that maps to a operator defined by a 'for' directive. */
428 struct user_id
: public id_base
430 user_id (const char *id_
, bool is_oper_list_
= false)
431 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
432 used (false), is_oper_list (is_oper_list_
) {}
433 vec
<id_base
*> substitutes
;
441 is_a_helper
<fn_id
*>::test (id_base
*id
)
443 return id
->kind
== id_base::FN
;
449 is_a_helper
<operator_id
*>::test (id_base
*id
)
451 return id
->kind
== id_base::CODE
;
457 is_a_helper
<predicate_id
*>::test (id_base
*id
)
459 return id
->kind
== id_base::PREDICATE
;
465 is_a_helper
<user_id
*>::test (id_base
*id
)
467 return id
->kind
== id_base::USER
;
470 /* If ID has a pair of consecutive, commutative operands, return the
471 index of the first, otherwise return -1. */
474 commutative_op (id_base
*id
)
476 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
478 if (commutative_tree_code (code
->code
)
479 || commutative_ternary_tree_code (code
->code
))
483 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
495 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
497 int res
= commutative_op (uid
->substitutes
[0]);
500 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
501 if (res
!= commutative_op (uid
->substitutes
[i
]))
508 /* Add a predicate identifier to the hash. */
510 static predicate_id
*
511 add_predicate (const char *id
)
513 predicate_id
*p
= new predicate_id (id
);
514 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
516 fatal ("duplicate id definition");
521 /* Add a tree code identifier to the hash. */
524 add_operator (enum tree_code code
, const char *id
,
525 const char *tcc
, unsigned nargs
)
527 if (strcmp (tcc
, "tcc_unary") != 0
528 && strcmp (tcc
, "tcc_binary") != 0
529 && strcmp (tcc
, "tcc_comparison") != 0
530 && strcmp (tcc
, "tcc_expression") != 0
531 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
532 && strcmp (tcc
, "tcc_reference") != 0
533 /* To have INTEGER_CST and friends as "predicate operators". */
534 && strcmp (tcc
, "tcc_constant") != 0
535 /* And allow CONSTRUCTOR for vector initializers. */
536 && !(code
== CONSTRUCTOR
)
537 /* Allow SSA_NAME as predicate operator. */
538 && !(code
== SSA_NAME
))
540 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
541 if (code
== ADDR_EXPR
)
543 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
544 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
546 fatal ("duplicate id definition");
550 /* Add a built-in or internal function identifier to the hash. ID is
551 the name of its CFN_* enumeration value. */
553 template <typename T
>
555 add_function (T code
, const char *id
)
557 fn_id
*fn
= new fn_id (code
, id
);
558 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
560 fatal ("duplicate id definition");
564 /* Helper for easy comparing ID with tree code CODE. */
567 operator==(id_base
&id
, enum tree_code code
)
569 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
570 return oid
->code
== code
;
574 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
577 get_operator (const char *id
, bool allow_null
= false)
579 if (allow_null
&& strcmp (id
, "null") == 0)
582 id_base
tem (id_base::CODE
, id
);
584 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
587 /* If this is a user-defined identifier track whether it was used. */
588 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
594 bool all_upper
= true;
595 bool all_lower
= true;
596 for (unsigned int i
= 0; id
[i
]; ++i
)
599 else if (ISLOWER (id
[i
]))
603 /* Try in caps with _EXPR appended. */
604 id2
= ACONCAT ((id
, "_EXPR", NULL
));
605 for (unsigned int i
= 0; id2
[i
]; ++i
)
606 id2
[i
] = TOUPPER (id2
[i
]);
608 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
609 /* Try CFN_ instead of IFN_. */
610 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
611 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
612 /* Try prepending CFN_. */
613 id2
= ACONCAT (("CFN_", id
, NULL
));
617 new (&tem
) id_base (id_base::CODE
, id2
);
618 return operators
->find_with_hash (&tem
, tem
.hashval
);
621 /* Return the comparison operators that results if the operands are
622 swapped. This is safe for floating-point. */
625 swap_tree_comparison (operator_id
*p
)
637 return get_operator ("LT_EXPR");
639 return get_operator ("LE_EXPR");
641 return get_operator ("GT_EXPR");
643 return get_operator ("GE_EXPR");
645 return get_operator ("UNLT_EXPR");
647 return get_operator ("UNLE_EXPR");
649 return get_operator ("UNGT_EXPR");
651 return get_operator ("UNGE_EXPR");
657 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
660 /* The AST produced by parsing of the pattern definitions. */
665 /* The base class for operands. */
668 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
669 operand (enum op_type type_
, source_location loc_
)
670 : type (type_
), location (loc_
) {}
672 source_location location
;
673 virtual void gen_transform (FILE *, int, const char *, bool, int,
674 const char *, capture_info
*,
677 { gcc_unreachable (); }
680 /* A predicate operand. Predicates are leafs in the AST. */
682 struct predicate
: public operand
684 predicate (predicate_id
*p_
, source_location loc
)
685 : operand (OP_PREDICATE
, loc
), p (p_
) {}
689 /* An operand that constitutes an expression. Expressions include
690 function calls and user-defined predicate invocations. */
692 struct expr
: public operand
694 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
695 : operand (OP_EXPR
, loc
), operation (operation_
),
696 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
697 is_generic (false), force_single_use (false) {}
699 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
700 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
701 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
702 void append_op (operand
*op
) { ops
.safe_push (op
); }
703 /* The operator and its operands. */
706 /* An explicitely specified type - used exclusively for conversions. */
707 const char *expr_type
;
708 /* Whether the operation is to be applied commutatively. This is
709 later lowered to two separate patterns. */
711 /* Whether the expression is expected to be in GENERIC form. */
713 /* Whether pushing any stmt to the sequence should be conditional
714 on this expression having a single-use. */
715 bool force_single_use
;
716 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
717 const char *, capture_info
*,
718 dt_operand
** = 0, int = 0);
721 /* An operator that is represented by native C code. This is always
722 a leaf operand in the AST. This class is also used to represent
723 the code to be generated for 'if' and 'with' expressions. */
725 struct c_expr
: public operand
727 /* A mapping of an identifier and its replacement. Used to apply
732 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
735 c_expr (cpp_reader
*r_
, source_location loc
,
736 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
737 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
738 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
739 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
740 /* cpplib tokens and state to transform this back to source. */
743 cid_map_t
*capture_ids
;
744 /* The number of statements parsed (well, the number of ';'s). */
746 /* The identifier replacement vector. */
748 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
749 const char *, capture_info
*,
750 dt_operand
** = 0, int = 0);
753 /* A wrapper around another operand that captures its value. */
755 struct capture
: public operand
757 capture (source_location loc
, unsigned where_
, operand
*what_
, bool value_
)
758 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
760 /* Identifier index for the value. */
762 /* Whether in a match of two operands the compare should be for
763 equal values rather than equal atoms (boils down to a type
766 /* The captured value. */
768 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
769 const char *, capture_info
*,
770 dt_operand
** = 0, int = 0);
775 struct if_expr
: public operand
777 if_expr (source_location loc
)
778 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
784 /* with expression. */
786 struct with_expr
: public operand
788 with_expr (source_location loc
)
789 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
797 is_a_helper
<capture
*>::test (operand
*op
)
799 return op
->type
== operand::OP_CAPTURE
;
805 is_a_helper
<predicate
*>::test (operand
*op
)
807 return op
->type
== operand::OP_PREDICATE
;
813 is_a_helper
<c_expr
*>::test (operand
*op
)
815 return op
->type
== operand::OP_C_EXPR
;
821 is_a_helper
<expr
*>::test (operand
*op
)
823 return op
->type
== operand::OP_EXPR
;
829 is_a_helper
<if_expr
*>::test (operand
*op
)
831 return op
->type
== operand::OP_IF
;
837 is_a_helper
<with_expr
*>::test (operand
*op
)
839 return op
->type
== operand::OP_WITH
;
842 /* The main class of a pattern and its transform. This is used to
843 represent both (simplify ...) and (match ...) kinds. The AST
844 duplicates all outer 'if' and 'for' expressions here so each
845 simplify can exist in isolation. */
849 enum simplify_kind
{ SIMPLIFY
, MATCH
};
851 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
852 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
853 cid_map_t
*capture_ids_
)
854 : kind (kind_
), id (id_
), match (match_
), result (result_
),
855 for_vec (for_vec_
), for_subst_vec (vNULL
),
856 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
859 /* ID. This is kept to easily associate related simplifies expanded
860 from the same original one. */
862 /* The expression that is matched against the GENERIC or GIMPLE IL. */
864 /* For a (simplify ...) an expression with ifs and withs with the expression
865 produced when the pattern applies in the leafs.
866 For a (match ...) the leafs are either empty if it is a simple predicate
867 or the single expression specifying the matched operands. */
868 struct operand
*result
;
869 /* Collected 'for' expression operators that have to be replaced
870 in the lowering phase. */
871 vec
<vec
<user_id
*> > for_vec
;
872 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
873 /* A map of capture identifiers to indexes. */
874 cid_map_t
*capture_ids
;
878 /* Debugging routines for dumping the AST. */
881 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
883 if (capture
*c
= dyn_cast
<capture
*> (o
))
885 if (c
->what
&& flattened
== false)
886 print_operand (c
->what
, f
, flattened
);
887 fprintf (f
, "@%u", c
->where
);
890 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
891 fprintf (f
, "%s", p
->p
->id
);
893 else if (is_a
<c_expr
*> (o
))
894 fprintf (f
, "c_expr");
896 else if (expr
*e
= dyn_cast
<expr
*> (o
))
898 if (e
->ops
.length () == 0)
899 fprintf (f
, "%s", e
->operation
->id
);
902 fprintf (f
, "(%s", e
->operation
->id
);
904 if (flattened
== false)
906 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
909 print_operand (e
->ops
[i
], f
, flattened
);
921 print_matches (struct simplify
*s
, FILE *f
= stderr
)
923 fprintf (f
, "for expression: ");
924 print_operand (s
->match
, f
);
931 /* Lowering of commutative operators. */
934 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
935 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
937 if (n
== ops_vector
.length ())
939 vec
<operand
*> xv
= v
.copy ();
940 result
.safe_push (xv
);
944 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
946 v
[n
] = ops_vector
[n
][i
];
947 cartesian_product (ops_vector
, result
, v
, n
+ 1);
951 /* Lower OP to two operands in case it is marked as commutative. */
953 static vec
<operand
*>
954 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
956 vec
<operand
*> ret
= vNULL
;
958 if (capture
*c
= dyn_cast
<capture
*> (op
))
965 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
966 for (unsigned i
= 0; i
< v
.length (); ++i
)
968 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
975 expr
*e
= dyn_cast
<expr
*> (op
);
976 if (!e
|| e
->ops
.length () == 0)
982 vec
< vec
<operand
*> > ops_vector
= vNULL
;
983 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
984 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
986 auto_vec
< vec
<operand
*> > result
;
987 auto_vec
<operand
*> v (e
->ops
.length ());
988 v
.quick_grow_cleared (e
->ops
.length ());
989 cartesian_product (ops_vector
, result
, v
, 0);
992 for (unsigned i
= 0; i
< result
.length (); ++i
)
994 expr
*ne
= new expr (e
);
995 ne
->is_commutative
= false;
996 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
997 ne
->append_op (result
[i
][j
]);
1001 if (!e
->is_commutative
)
1004 /* The operation is always binary if it isn't inherently commutative. */
1005 int natural_opno
= commutative_op (e
->operation
);
1006 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1007 for (unsigned i
= 0; i
< result
.length (); ++i
)
1009 expr
*ne
= new expr (e
);
1010 if (operator_id
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
1012 if (comparison_code_p (p
->code
))
1013 ne
->operation
= swap_tree_comparison (p
);
1015 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1017 bool found_compare
= false;
1018 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1019 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1021 if (comparison_code_p (q
->code
)
1022 && swap_tree_comparison (q
) != q
)
1024 found_compare
= true;
1030 user_id
*newop
= new user_id ("<internal>");
1031 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1033 id_base
*subst
= p
->substitutes
[j
];
1034 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1036 if (comparison_code_p (q
->code
))
1037 subst
= swap_tree_comparison (q
);
1039 newop
->substitutes
.safe_push (subst
);
1041 ne
->operation
= newop
;
1042 /* Search for 'p' inside the for vector and push 'newop'
1043 to the same level. */
1044 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1045 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1046 if (for_vec
[j
][k
] == p
)
1048 for_vec
[j
].safe_push (newop
);
1054 ne
->is_commutative
= false;
1055 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1057 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1058 ne
->append_op (result
[i
][old_j
]);
1066 /* Lower operations marked as commutative in the AST of S and push
1067 the resulting patterns to SIMPLIFIERS. */
1070 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1072 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1073 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1075 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1076 s
->for_vec
, s
->capture_ids
);
1077 simplifiers
.safe_push (ns
);
1081 /* Strip conditional conversios using operator OPER from O and its
1082 children if STRIP, else replace them with an unconditional convert. */
1085 lower_opt_convert (operand
*o
, enum tree_code oper
,
1086 enum tree_code to_oper
, bool strip
)
1088 if (capture
*c
= dyn_cast
<capture
*> (o
))
1091 return new capture (c
->location
, c
->where
,
1092 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1098 expr
*e
= dyn_cast
<expr
*> (o
);
1102 if (*e
->operation
== oper
)
1105 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1107 expr
*ne
= new expr (e
);
1108 ne
->operation
= (to_oper
== CONVERT_EXPR
1109 ? get_operator ("CONVERT_EXPR")
1110 : get_operator ("VIEW_CONVERT_EXPR"));
1111 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1115 expr
*ne
= new expr (e
);
1116 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1117 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1122 /* Determine whether O or its children uses the conditional conversion
1126 has_opt_convert (operand
*o
, enum tree_code oper
)
1128 if (capture
*c
= dyn_cast
<capture
*> (o
))
1131 return has_opt_convert (c
->what
, oper
);
1136 expr
*e
= dyn_cast
<expr
*> (o
);
1140 if (*e
->operation
== oper
)
1143 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1144 if (has_opt_convert (e
->ops
[i
], oper
))
1150 /* Lower conditional convert operators in O, expanding it to a vector
1153 static vec
<operand
*>
1154 lower_opt_convert (operand
*o
)
1156 vec
<operand
*> v1
= vNULL
, v2
;
1160 enum tree_code opers
[]
1161 = { CONVERT0
, CONVERT_EXPR
,
1162 CONVERT1
, CONVERT_EXPR
,
1163 CONVERT2
, CONVERT_EXPR
,
1164 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1165 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1166 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1168 /* Conditional converts are lowered to a pattern with the
1169 conversion and one without. The three different conditional
1170 convert codes are lowered separately. */
1172 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1175 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1176 if (has_opt_convert (v1
[j
], opers
[i
]))
1178 v2
.safe_push (lower_opt_convert (v1
[j
],
1179 opers
[i
], opers
[i
+1], false));
1180 v2
.safe_push (lower_opt_convert (v1
[j
],
1181 opers
[i
], opers
[i
+1], true));
1187 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1188 v1
.safe_push (v2
[j
]);
1195 /* Lower conditional convert operators in the AST of S and push
1196 the resulting multiple patterns to SIMPLIFIERS. */
1199 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1201 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1202 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1204 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1205 s
->for_vec
, s
->capture_ids
);
1206 simplifiers
.safe_push (ns
);
1210 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1211 GENERIC and a GIMPLE variant. */
1213 static vec
<operand
*>
1214 lower_cond (operand
*o
)
1216 vec
<operand
*> ro
= vNULL
;
1218 if (capture
*c
= dyn_cast
<capture
*> (o
))
1222 vec
<operand
*> lop
= vNULL
;
1223 lop
= lower_cond (c
->what
);
1225 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1226 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1232 expr
*e
= dyn_cast
<expr
*> (o
);
1233 if (!e
|| e
->ops
.length () == 0)
1239 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1240 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1241 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1243 auto_vec
< vec
<operand
*> > result
;
1244 auto_vec
<operand
*> v (e
->ops
.length ());
1245 v
.quick_grow_cleared (e
->ops
.length ());
1246 cartesian_product (ops_vector
, result
, v
, 0);
1248 for (unsigned i
= 0; i
< result
.length (); ++i
)
1250 expr
*ne
= new expr (e
);
1251 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1252 ne
->append_op (result
[i
][j
]);
1254 /* If this is a COND with a captured expression or an
1255 expression with two operands then also match a GENERIC
1256 form on the compare. */
1257 if ((*e
->operation
== COND_EXPR
1258 || *e
->operation
== VEC_COND_EXPR
)
1259 && ((is_a
<capture
*> (e
->ops
[0])
1260 && as_a
<capture
*> (e
->ops
[0])->what
1261 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1263 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1264 || (is_a
<expr
*> (e
->ops
[0])
1265 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1267 expr
*ne
= new expr (e
);
1268 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1269 ne
->append_op (result
[i
][j
]);
1270 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1272 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1273 expr
*cmp
= new expr (ocmp
);
1274 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1275 cmp
->append_op (ocmp
->ops
[j
]);
1276 cmp
->is_generic
= true;
1277 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1282 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1283 expr
*cmp
= new expr (ocmp
);
1284 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1285 cmp
->append_op (ocmp
->ops
[j
]);
1286 cmp
->is_generic
= true;
1296 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1297 GENERIC and a GIMPLE variant. */
1300 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1302 vec
<operand
*> matchers
= lower_cond (s
->match
);
1303 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1305 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1306 s
->for_vec
, s
->capture_ids
);
1307 simplifiers
.safe_push (ns
);
1311 /* Return true if O refers to ID. */
1314 contains_id (operand
*o
, user_id
*id
)
1316 if (capture
*c
= dyn_cast
<capture
*> (o
))
1317 return c
->what
&& contains_id (c
->what
, id
);
1319 if (expr
*e
= dyn_cast
<expr
*> (o
))
1321 if (e
->operation
== id
)
1323 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1324 if (contains_id (e
->ops
[i
], id
))
1329 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1330 return (contains_id (w
->with
, id
)
1331 || contains_id (w
->subexpr
, id
));
1333 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1334 return (contains_id (ife
->cond
, id
)
1335 || contains_id (ife
->trueexpr
, id
)
1336 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1338 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1339 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1345 /* In AST operand O replace operator ID with operator WITH. */
1348 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1350 /* Deep-copy captures and expressions, replacing operations as
1352 if (capture
*c
= dyn_cast
<capture
*> (o
))
1356 return new capture (c
->location
, c
->where
,
1357 replace_id (c
->what
, id
, with
), c
->value_match
);
1359 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1361 expr
*ne
= new expr (e
);
1362 if (e
->operation
== id
)
1363 ne
->operation
= with
;
1364 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1365 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1368 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1370 with_expr
*nw
= new with_expr (w
->location
);
1371 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1372 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1375 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1377 if_expr
*nife
= new if_expr (ife
->location
);
1378 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1379 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1381 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1385 /* For c_expr we simply record a string replacement table which is
1386 applied at code-generation time. */
1387 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1389 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1390 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1391 return new c_expr (ce
->r
, ce
->location
,
1392 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1398 /* Return true if the binary operator OP is ok for delayed substitution
1399 during for lowering. */
1402 binary_ok (operator_id
*op
)
1409 case TRUNC_DIV_EXPR
:
1411 case FLOOR_DIV_EXPR
:
1412 case ROUND_DIV_EXPR
:
1413 case TRUNC_MOD_EXPR
:
1415 case FLOOR_MOD_EXPR
:
1416 case ROUND_MOD_EXPR
:
1418 case EXACT_DIV_EXPR
:
1430 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1433 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1435 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1436 unsigned worklist_start
= 0;
1437 auto_vec
<simplify
*> worklist
;
1438 worklist
.safe_push (sin
);
1440 /* Lower each recorded for separately, operating on the
1441 set of simplifiers created by the previous one.
1442 Lower inner-to-outer so inner for substitutes can refer
1443 to operators replaced by outer fors. */
1444 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1446 vec
<user_id
*>& ids
= for_vec
[fi
];
1447 unsigned n_ids
= ids
.length ();
1448 unsigned max_n_opers
= 0;
1449 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1450 for (unsigned i
= 0; i
< n_ids
; ++i
)
1452 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1453 max_n_opers
= ids
[i
]->substitutes
.length ();
1454 /* Require that all substitutes are of the same kind so that
1455 if we delay substitution to the result op code generation
1456 can look at the first substitute for deciding things like
1457 types of operands. */
1458 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1459 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1460 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1461 can_delay_subst
= false;
1462 else if (operator_id
*op
1463 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1466 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1467 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1468 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1470 /* Unfortunately we can't just allow all tcc_binary. */
1471 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1472 && strcmp (op0
->tcc
, "tcc_binary") == 0
1476 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1477 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1478 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1479 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1482 can_delay_subst
= false;
1484 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1487 can_delay_subst
= false;
1490 unsigned worklist_end
= worklist
.length ();
1491 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1493 simplify
*s
= worklist
[si
];
1494 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1496 operand
*match_op
= s
->match
;
1497 operand
*result_op
= s
->result
;
1498 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1500 for (unsigned i
= 0; i
< n_ids
; ++i
)
1502 user_id
*id
= ids
[i
];
1503 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1505 && (contains_id (match_op
, id
)
1506 || contains_id (result_op
, id
)))
1511 subst
.quick_push (std::make_pair (id
, oper
));
1512 match_op
= replace_id (match_op
, id
, oper
);
1514 && !can_delay_subst
)
1515 result_op
= replace_id (result_op
, id
, oper
);
1520 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1521 vNULL
, s
->capture_ids
);
1522 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1525 ns
->for_subst_vec
.safe_splice (subst
);
1527 worklist
.safe_push (ns
);
1530 worklist_start
= worklist_end
;
1533 /* Copy out the result from the last for lowering. */
1534 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1535 simplifiers
.safe_push (worklist
[i
]);
1538 /* Lower the AST for everything in SIMPLIFIERS. */
1541 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1543 auto_vec
<simplify
*> out_simplifiers
;
1544 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1545 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1547 simplifiers
.truncate (0);
1548 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1549 lower_commutative (out_simplifiers
[i
], simplifiers
);
1551 out_simplifiers
.truncate (0);
1553 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1554 lower_cond (simplifiers
[i
], out_simplifiers
);
1556 out_simplifiers
.safe_splice (simplifiers
);
1559 simplifiers
.truncate (0);
1560 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1561 lower_for (out_simplifiers
[i
], simplifiers
);
1567 /* The decision tree built for generating GIMPLE and GENERIC pattern
1568 matching code. It represents the 'match' expression of all
1569 simplifies and has those as its leafs. */
1573 /* A hash-map collecting semantically equivalent leafs in the decision
1574 tree for splitting out to separate functions. */
1583 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1586 static inline hashval_t
hash (const key_type
&);
1587 static inline bool equal_keys (const key_type
&, const key_type
&);
1588 template <typename T
> static inline void remove (T
&) {}
1591 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1594 /* Current simplifier ID we are processing during insertion into the
1596 static unsigned current_id
;
1598 /* Decision tree base class, used for DT_NODE. */
1602 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1607 vec
<dt_node
*> kids
;
1611 unsigned total_size
;
1614 dt_node (enum dt_type type_
, dt_node
*parent_
)
1615 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1617 dt_node
*append_node (dt_node
*);
1618 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1619 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1620 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1622 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1624 virtual void gen (FILE *, int, bool) {}
1626 void gen_kids (FILE *, int, bool);
1627 void gen_kids_1 (FILE *, int, bool,
1628 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1629 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1631 void analyze (sinfo_map_t
&);
1634 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1636 struct dt_operand
: public dt_node
1639 dt_operand
*match_dop
;
1644 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1645 dt_operand
*parent_
, unsigned pos_
)
1646 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1647 pos (pos_
), value_match (false), for_id (current_id
) {}
1649 void gen (FILE *, int, bool);
1650 unsigned gen_predicate (FILE *, int, const char *, bool);
1651 unsigned gen_match_op (FILE *, int, const char *, bool);
1653 unsigned gen_gimple_expr (FILE *, int);
1654 unsigned gen_generic_expr (FILE *, int, const char *);
1656 char *get_name (char *);
1657 void gen_opname (char *, unsigned);
1660 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1662 struct dt_simplify
: public dt_node
1665 unsigned pattern_no
;
1666 dt_operand
**indexes
;
1669 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1670 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1671 indexes (indexes_
), info (NULL
) {}
1673 void gen_1 (FILE *, int, bool, operand
*);
1674 void gen (FILE *f
, int, bool);
1680 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1682 return (n
->type
== dt_node::DT_OPERAND
1683 || n
->type
== dt_node::DT_MATCH
1684 || n
->type
== dt_node::DT_TRUE
);
1690 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1692 return n
->type
== dt_node::DT_SIMPLIFY
;
1697 /* A container for the actual decision tree. */
1699 struct decision_tree
1703 void insert (struct simplify
*, unsigned);
1704 void gen (FILE *f
, bool gimple
);
1705 void print (FILE *f
= stderr
);
1707 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1709 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1710 unsigned pos
= 0, dt_node
*parent
= 0);
1711 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1712 static bool cmp_node (dt_node
*, dt_node
*);
1713 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1716 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1719 cmp_operand (operand
*o1
, operand
*o2
)
1721 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1724 if (o1
->type
== operand::OP_PREDICATE
)
1726 predicate
*p1
= as_a
<predicate
*>(o1
);
1727 predicate
*p2
= as_a
<predicate
*>(o2
);
1728 return p1
->p
== p2
->p
;
1730 else if (o1
->type
== operand::OP_EXPR
)
1732 expr
*e1
= static_cast<expr
*>(o1
);
1733 expr
*e2
= static_cast<expr
*>(o2
);
1734 return (e1
->operation
== e2
->operation
1735 && e1
->is_generic
== e2
->is_generic
);
1741 /* Compare two decision tree nodes N1 and N2 and return true if they
1745 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1747 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1753 if (n1
->type
== dt_node::DT_TRUE
)
1756 if (n1
->type
== dt_node::DT_OPERAND
)
1757 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1758 (as_a
<dt_operand
*> (n2
))->op
);
1759 else if (n1
->type
== dt_node::DT_MATCH
)
1760 return (((as_a
<dt_operand
*> (n1
))->match_dop
1761 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1762 && ((as_a
<dt_operand
*> (n1
))->value_match
1763 == (as_a
<dt_operand
*> (n2
))->value_match
));
1767 /* Search OPS for a decision tree node like P and return it if found. */
1770 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1772 /* We can merge adjacent DT_TRUE. */
1773 if (p
->type
== dt_node::DT_TRUE
1775 && ops
.last ()->type
== dt_node::DT_TRUE
)
1777 dt_operand
*true_node
= NULL
;
1778 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1780 /* But we can't merge across DT_TRUE nodes as they serve as
1781 pattern order barriers to make sure that patterns apply
1782 in order of appearance in case multiple matches are possible. */
1783 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1786 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1787 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1789 if (decision_tree::cmp_node (ops
[i
], p
))
1791 /* Unless we are processing the same pattern or the blocking
1792 pattern is before the one we are going to merge with. */
1794 && true_node
->for_id
!= current_id
1795 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1799 source_location p_loc
= 0;
1800 if (p
->type
== dt_node::DT_OPERAND
)
1801 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1802 source_location op_loc
= 0;
1803 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1804 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1805 source_location true_loc
= 0;
1806 true_loc
= true_node
->op
->location
;
1808 "failed to merge decision tree node");
1810 "with the following");
1811 warning_at (true_loc
,
1812 "because of the following which serves as ordering "
1823 /* Append N to the decision tree if it there is not already an existing
1827 dt_node::append_node (dt_node
*n
)
1831 kid
= decision_tree::find_node (kids
, n
);
1836 n
->level
= this->level
+ 1;
1841 /* Append OP to the decision tree. */
1844 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1846 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1847 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1848 return append_node (n
);
1851 /* Append a DT_TRUE decision tree node. */
1854 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1856 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1857 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1858 return append_node (n
);
1861 /* Append a DT_MATCH decision tree node. */
1864 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1865 dt_node
*parent
, unsigned pos
)
1867 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1868 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1869 return append_node (n
);
1872 /* Append S to the decision tree. */
1875 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1876 dt_operand
**indexes
)
1878 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1879 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1880 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1882 warning_at (s
->match
->location
, "duplicate pattern");
1883 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1884 print_operand (s
->match
, stderr
);
1885 fprintf (stderr
, "\n");
1887 return append_node (n
);
1890 /* Analyze the node and its children. */
1893 dt_node::analyze (sinfo_map_t
&map
)
1899 if (type
== DT_SIMPLIFY
)
1901 /* Populate the map of equivalent simplifies. */
1902 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1904 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1919 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1921 kids
[i
]->analyze (map
);
1922 num_leafs
+= kids
[i
]->num_leafs
;
1923 total_size
+= kids
[i
]->total_size
;
1924 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1928 /* Insert O into the decision tree and return the decision tree node found
1932 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1933 unsigned pos
, dt_node
*parent
)
1935 dt_node
*q
, *elm
= 0;
1937 if (capture
*c
= dyn_cast
<capture
*> (o
))
1939 unsigned capt_index
= c
->where
;
1941 if (indexes
[capt_index
] == 0)
1944 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1947 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1950 // get to the last capture
1951 for (operand
*what
= c
->what
;
1952 what
&& is_a
<capture
*> (what
);
1953 c
= as_a
<capture
*> (what
), what
= c
->what
)
1958 unsigned cc_index
= c
->where
;
1959 dt_operand
*match_op
= indexes
[cc_index
];
1961 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1962 elm
= decision_tree::find_node (p
->kids
, &temp
);
1966 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1967 temp
.value_match
= c
->value_match
;
1968 elm
= decision_tree::find_node (p
->kids
, &temp
);
1973 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1974 elm
= decision_tree::find_node (p
->kids
, &temp
);
1978 gcc_assert (elm
->type
== dt_node::DT_TRUE
1979 || elm
->type
== dt_node::DT_OPERAND
1980 || elm
->type
== dt_node::DT_MATCH
);
1981 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1986 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
1987 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1989 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1994 p
= p
->append_op (o
, parent
, pos
);
1997 if (expr
*e
= dyn_cast
<expr
*>(o
))
1999 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2000 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2006 /* Insert S into the decision tree. */
2009 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
2012 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2013 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2014 p
->append_simplify (s
, pattern_no
, indexes
);
2017 /* Debug functions to dump the decision tree. */
2020 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2022 if (p
->type
== dt_node::DT_NODE
)
2023 fprintf (f
, "root");
2027 for (unsigned i
= 0; i
< indent
; i
++)
2030 if (p
->type
== dt_node::DT_OPERAND
)
2032 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2033 print_operand (dop
->op
, f
, true);
2035 else if (p
->type
== dt_node::DT_TRUE
)
2036 fprintf (f
, "true");
2037 else if (p
->type
== dt_node::DT_MATCH
)
2038 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2039 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2041 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2042 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2043 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2044 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2047 if (is_a
<dt_operand
*> (p
))
2048 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2051 fprintf (stderr
, " (%p, %p), %u, %u\n",
2052 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2054 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2055 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2059 decision_tree::print (FILE *f
)
2061 return decision_tree::print_node (root
, f
);
2065 /* For GENERIC we have to take care of wrapping multiple-used
2066 expressions with side-effects in save_expr and preserve side-effects
2067 of expressions with omit_one_operand. Analyze captures in
2068 match, result and with expressions and perform early-outs
2069 on the outermost match expression operands for cases we cannot
2074 capture_info (simplify
*s
, operand
*, bool);
2075 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2076 bool walk_result (operand
*o
, bool, operand
*);
2077 void walk_c_expr (c_expr
*);
2083 bool force_no_side_effects_p
;
2084 bool force_single_use
;
2085 bool cond_expr_cond_p
;
2086 unsigned long toplevel_msk
;
2087 unsigned match_use_count
;
2088 unsigned result_use_count
;
2093 auto_vec
<cinfo
> info
;
2094 unsigned long force_no_side_effects
;
2098 /* Analyze captures in S. */
2100 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2105 if (s
->kind
== simplify::MATCH
)
2107 force_no_side_effects
= -1;
2111 force_no_side_effects
= 0;
2112 info
.safe_grow_cleared (s
->capture_max
+ 1);
2113 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2114 info
[i
].same_as
= i
;
2116 e
= as_a
<expr
*> (s
->match
);
2117 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2118 walk_match (e
->ops
[i
], i
,
2119 (i
!= 0 && *e
->operation
== COND_EXPR
)
2120 || *e
->operation
== TRUTH_ANDIF_EXPR
2121 || *e
->operation
== TRUTH_ORIF_EXPR
,
2123 && (*e
->operation
== COND_EXPR
2124 || *e
->operation
== VEC_COND_EXPR
));
2126 walk_result (s
->result
, false, result
);
2129 /* Analyze captures in the match expression piece O. */
2132 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2133 bool conditional_p
, bool cond_expr_cond_p
)
2135 if (capture
*c
= dyn_cast
<capture
*> (o
))
2137 unsigned where
= c
->where
;
2138 info
[where
].match_use_count
++;
2139 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2140 info
[where
].force_no_side_effects_p
|= conditional_p
;
2141 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2146 /* Recurse to exprs and captures. */
2147 if (is_a
<capture
*> (c
->what
)
2148 || is_a
<expr
*> (c
->what
))
2149 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2150 /* We need to look past multiple captures to find a captured
2151 expression as with conditional converts two captures
2152 can be collapsed onto the same expression. Also collect
2153 what captures capture the same thing. */
2154 while (c
->what
&& is_a
<capture
*> (c
->what
))
2156 c
= as_a
<capture
*> (c
->what
);
2157 if (info
[c
->where
].same_as
!= c
->where
2158 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2159 fatal_at (c
->location
, "cannot handle this collapsed capture");
2160 info
[c
->where
].same_as
= info
[where
].same_as
;
2162 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2165 && (e
= dyn_cast
<expr
*> (c
->what
)))
2167 /* Zero-operand expression captures like ADDR_EXPR@0 are
2168 similar as predicates -- if they are not mentioned in
2169 the result we have to force them to have no side-effects. */
2170 if (e
->ops
.length () != 0)
2171 info
[where
].expr_p
= true;
2172 info
[where
].force_single_use
|= e
->force_single_use
;
2175 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2177 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2179 bool cond_p
= conditional_p
;
2180 bool cond_expr_cond_p
= false;
2181 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2183 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2184 || *e
->operation
== TRUTH_ORIF_EXPR
)
2187 && (*e
->operation
== COND_EXPR
2188 || *e
->operation
== VEC_COND_EXPR
))
2189 cond_expr_cond_p
= true;
2190 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2193 else if (is_a
<predicate
*> (o
))
2195 /* Mark non-captured leafs toplevel arg for checking. */
2196 force_no_side_effects
|= 1 << toplevel_arg
;
2199 warning_at (o
->location
,
2200 "forcing no side-effects on possibly lost leaf");
2206 /* Analyze captures in the result expression piece O. Return true
2207 if RESULT was visited in one of the children. Only visit
2208 non-if/with children if they are rooted on RESULT. */
2211 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2213 if (capture
*c
= dyn_cast
<capture
*> (o
))
2215 unsigned where
= info
[c
->where
].same_as
;
2216 info
[where
].result_use_count
++;
2217 /* If we substitute an expression capture we don't know
2218 which captures this will end up using (well, we don't
2219 compute that). Force the uses to be side-effect free
2220 which means forcing the toplevels that reach the
2221 expression side-effect free. */
2222 if (info
[where
].expr_p
)
2223 force_no_side_effects
|= info
[where
].toplevel_msk
;
2224 /* Mark CSE capture uses as forced to have no side-effects. */
2226 && is_a
<expr
*> (c
->what
))
2228 info
[where
].cse_p
= true;
2229 walk_result (c
->what
, true, result
);
2232 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2234 id_base
*opr
= e
->operation
;
2235 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2236 opr
= uid
->substitutes
[0];
2237 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2239 bool cond_p
= conditional_p
;
2240 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2242 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2243 || *e
->operation
== TRUTH_ORIF_EXPR
)
2245 walk_result (e
->ops
[i
], cond_p
, result
);
2248 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2250 /* 'if' conditions should be all fine. */
2251 if (e
->trueexpr
== result
)
2253 walk_result (e
->trueexpr
, false, result
);
2256 if (e
->falseexpr
== result
)
2258 walk_result (e
->falseexpr
, false, result
);
2262 if (is_a
<if_expr
*> (e
->trueexpr
)
2263 || is_a
<with_expr
*> (e
->trueexpr
))
2264 res
|= walk_result (e
->trueexpr
, false, result
);
2266 && (is_a
<if_expr
*> (e
->falseexpr
)
2267 || is_a
<with_expr
*> (e
->falseexpr
)))
2268 res
|= walk_result (e
->falseexpr
, false, result
);
2271 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2273 bool res
= (e
->subexpr
== result
);
2275 || is_a
<if_expr
*> (e
->subexpr
)
2276 || is_a
<with_expr
*> (e
->subexpr
))
2277 res
|= walk_result (e
->subexpr
, false, result
);
2279 walk_c_expr (e
->with
);
2282 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2290 /* Look for captures in the C expr E. */
2293 capture_info::walk_c_expr (c_expr
*e
)
2295 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2296 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2297 really escape through. */
2298 unsigned p_depth
= 0;
2299 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2301 const cpp_token
*t
= &e
->code
[i
];
2302 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2304 if (t
->type
== CPP_NAME
2305 && (strcmp ((const char *)CPP_HASHNODE
2306 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2307 || strcmp ((const char *)CPP_HASHNODE
2308 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2309 || strcmp ((const char *)CPP_HASHNODE
2310 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2311 || ((id
= get_operator ((const char *)CPP_HASHNODE
2312 (t
->val
.node
.node
)->ident
.str
))
2313 && is_a
<predicate_id
*> (id
)))
2314 && n
->type
== CPP_OPEN_PAREN
)
2316 else if (t
->type
== CPP_CLOSE_PAREN
2319 else if (p_depth
== 0
2320 && t
->type
== CPP_ATSIGN
2321 && (n
->type
== CPP_NUMBER
2322 || n
->type
== CPP_NAME
)
2323 && !(n
->flags
& PREV_WHITE
))
2326 if (n
->type
== CPP_NUMBER
)
2327 id
= (const char *)n
->val
.str
.text
;
2329 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2330 unsigned *where
= e
->capture_ids
->get(id
);
2332 fatal_at (n
, "unknown capture id '%s'", id
);
2333 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2336 warning_at (t
, "capture escapes");
2342 /* Code generation off the decision tree and the refered AST nodes. */
2345 is_conversion (id_base
*op
)
2347 return (*op
== CONVERT_EXPR
2349 || *op
== FLOAT_EXPR
2350 || *op
== FIX_TRUNC_EXPR
2351 || *op
== VIEW_CONVERT_EXPR
);
2354 /* Get the type to be used for generating operand POS of OP from the
2358 get_operand_type (id_base
*op
, unsigned pos
,
2359 const char *in_type
,
2360 const char *expr_type
,
2361 const char *other_oprnd_type
)
2363 /* Generally operands whose type does not match the type of the
2364 expression generated need to know their types but match and
2365 thus can fall back to 'other_oprnd_type'. */
2366 if (is_conversion (op
))
2367 return other_oprnd_type
;
2368 else if (*op
== REALPART_EXPR
2369 || *op
== IMAGPART_EXPR
)
2370 return other_oprnd_type
;
2371 else if (is_a
<operator_id
*> (op
)
2372 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2373 return other_oprnd_type
;
2374 else if (*op
== COND_EXPR
2376 return "boolean_type_node";
2377 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2379 /* IFN_COND_* operands 1 and later by default have the same type
2380 as the result. The type of operand 0 needs to be specified
2382 if (pos
> 0 && expr_type
)
2384 else if (pos
> 0 && in_type
)
2391 /* Otherwise all types should match - choose one in order of
2398 return other_oprnd_type
;
2402 /* Generate transform code for an expression. */
2405 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2406 int depth
, const char *in_type
, capture_info
*cinfo
,
2407 dt_operand
**indexes
, int)
2409 id_base
*opr
= operation
;
2410 /* When we delay operator substituting during lowering of fors we
2411 make sure that for code-gen purposes the effects of each substitute
2412 are the same. Thus just look at that. */
2413 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2414 opr
= uid
->substitutes
[0];
2416 bool conversion_p
= is_conversion (opr
);
2417 const char *type
= expr_type
;
2420 /* If there was a type specification in the pattern use it. */
2422 else if (conversion_p
)
2423 /* For conversions we need to build the expression using the
2424 outer type passed in. */
2426 else if (*opr
== REALPART_EXPR
2427 || *opr
== IMAGPART_EXPR
)
2429 /* __real and __imag use the component type of its operand. */
2430 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2433 else if (is_a
<operator_id
*> (opr
)
2434 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2436 /* comparisons use boolean_type_node (or what gets in), but
2437 their operands need to figure out the types themselves. */
2442 sprintf (optype
, "boolean_type_node");
2447 else if (*opr
== COND_EXPR
2448 || *opr
== VEC_COND_EXPR
2449 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2451 /* Conditions are of the same type as their first alternative. */
2452 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2457 /* Other operations are of the same type as their first operand. */
2458 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2462 fatal_at (location
, "cannot determine type of operand");
2464 fprintf_indent (f
, indent
, "{\n");
2466 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2468 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2469 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2472 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2474 = get_operand_type (opr
, i
, in_type
, expr_type
,
2475 i
== 0 ? NULL
: op0type
);
2476 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2479 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2482 const char *opr_name
;
2483 if (*operation
== CONVERT_EXPR
)
2484 opr_name
= "NOP_EXPR";
2486 opr_name
= operation
->id
;
2490 if (*opr
== CONVERT_EXPR
)
2492 fprintf_indent (f
, indent
,
2493 "if (%s != TREE_TYPE (ops%d[0])\n",
2495 fprintf_indent (f
, indent
,
2496 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2498 fprintf_indent (f
, indent
+ 2, "{\n");
2501 /* ??? Building a stmt can fail for various reasons here, seq being
2502 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2503 So if we fail here we should continue matching other patterns. */
2504 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2505 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2506 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2507 fprintf (f
, ", ops%d[%u]", depth
, i
);
2508 fprintf (f
, ");\n");
2509 fprintf_indent (f
, indent
,
2510 "gimple_resimplify%d (lseq, &tem_op, valueize);\n",
2512 fprintf_indent (f
, indent
,
2513 "res = maybe_push_res_to_seq (&tem_op, lseq);\n");
2514 fprintf_indent (f
, indent
,
2515 "if (!res) return false;\n");
2516 if (*opr
== CONVERT_EXPR
)
2519 fprintf_indent (f
, indent
, " }\n");
2520 fprintf_indent (f
, indent
, "else\n");
2521 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2526 if (*opr
== CONVERT_EXPR
)
2528 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2532 if (opr
->kind
== id_base::CODE
)
2533 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2534 ops
.length(), opr_name
, type
);
2537 fprintf_indent (f
, indent
, "{\n");
2538 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2539 "%s, %s, %d", opr_name
, type
, ops
.length());
2541 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2542 fprintf (f
, ", ops%d[%u]", depth
, i
);
2543 fprintf (f
, ");\n");
2544 if (opr
->kind
!= id_base::CODE
)
2546 fprintf_indent (f
, indent
, " if (!res)\n");
2547 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2548 fprintf_indent (f
, indent
, "}\n");
2550 if (*opr
== CONVERT_EXPR
)
2553 fprintf_indent (f
, indent
, "else\n");
2554 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2557 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2559 fprintf_indent (f
, indent
, "}\n");
2562 /* Generate code for a c_expr which is either the expression inside
2563 an if statement or a sequence of statements which computes a
2564 result to be stored to DEST. */
2567 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2568 bool, int, const char *, capture_info
*,
2571 if (dest
&& nr_stmts
== 1)
2572 fprintf_indent (f
, indent
, "%s = ", dest
);
2574 unsigned stmt_nr
= 1;
2575 for (unsigned i
= 0; i
< code
.length (); ++i
)
2577 const cpp_token
*token
= &code
[i
];
2579 /* Replace captures for code-gen. */
2580 if (token
->type
== CPP_ATSIGN
)
2582 const cpp_token
*n
= &code
[i
+1];
2583 if ((n
->type
== CPP_NUMBER
2584 || n
->type
== CPP_NAME
)
2585 && !(n
->flags
& PREV_WHITE
))
2587 if (token
->flags
& PREV_WHITE
)
2590 if (n
->type
== CPP_NUMBER
)
2591 id
= (const char *)n
->val
.str
.text
;
2593 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2594 unsigned *cid
= capture_ids
->get (id
);
2596 fatal_at (token
, "unknown capture id");
2597 fprintf (f
, "captures[%u]", *cid
);
2603 if (token
->flags
& PREV_WHITE
)
2606 if (token
->type
== CPP_NAME
)
2608 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2610 for (j
= 0; j
< ids
.length (); ++j
)
2612 if (strcmp (id
, ids
[j
].id
) == 0)
2614 fprintf (f
, "%s", ids
[j
].oper
);
2618 if (j
< ids
.length ())
2622 /* Output the token as string. */
2623 char *tk
= (char *)cpp_token_as_text (r
, token
);
2626 if (token
->type
== CPP_SEMICOLON
)
2630 if (dest
&& stmt_nr
== nr_stmts
)
2631 fprintf_indent (f
, indent
, "%s = ", dest
);
2636 /* Generate transform code for a capture. */
2639 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2640 int depth
, const char *in_type
, capture_info
*cinfo
,
2641 dt_operand
**indexes
, int cond_handling
)
2643 if (what
&& is_a
<expr
*> (what
))
2645 if (indexes
[where
] == 0)
2648 sprintf (buf
, "captures[%u]", where
);
2649 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2654 /* If in GENERIC some capture is used multiple times, unshare it except
2655 when emitting the last use. */
2657 && cinfo
->info
.exists ()
2658 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2660 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2662 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2665 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2667 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2668 with substituting a capture of that. */
2670 && cond_handling
!= 0
2671 && cinfo
->info
[where
].cond_expr_cond_p
)
2673 /* If substituting into a cond_expr condition, unshare. */
2674 if (cond_handling
== 1)
2675 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2676 /* If substituting elsewhere we might need to decompose it. */
2677 else if (cond_handling
== 2)
2679 /* ??? Returning false here will also not allow any other patterns
2680 to match unless this generator was split out. */
2681 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2682 fprintf_indent (f
, indent
, " {\n");
2683 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2684 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2686 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2687 " TREE_OPERAND (%s, 1));\n",
2688 dest
, dest
, dest
, dest
, dest
);
2689 fprintf_indent (f
, indent
, " }\n");
2694 /* Return the name of the operand representing the decision tree node.
2695 Use NAME as space to generate it. */
2698 dt_operand::get_name (char *name
)
2701 sprintf (name
, "t");
2702 else if (parent
->level
== 1)
2703 sprintf (name
, "op%u", pos
);
2704 else if (parent
->type
== dt_node::DT_MATCH
)
2705 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2707 sprintf (name
, "o%u%u", parent
->level
, pos
);
2711 /* Fill NAME with the operand name at position POS. */
2714 dt_operand::gen_opname (char *name
, unsigned pos
)
2717 sprintf (name
, "op%u", pos
);
2719 sprintf (name
, "o%u%u", level
, pos
);
2722 /* Generate matching code for the decision tree operand which is
2726 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2728 predicate
*p
= as_a
<predicate
*> (op
);
2730 if (p
->p
->matchers
.exists ())
2732 /* If this is a predicate generated from a pattern mangle its
2733 name and pass on the valueize hook. */
2735 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2738 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2741 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2742 fprintf_indent (f
, indent
+ 2, "{\n");
2746 /* Generate matching code for the decision tree operand which is
2750 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2752 char match_opname
[20];
2753 match_dop
->get_name (match_opname
);
2755 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2756 "|| operand_equal_p (%s, %s, 0))\n",
2757 opname
, match_opname
, opname
, opname
, match_opname
);
2759 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2760 "|| (operand_equal_p (%s, %s, 0) "
2761 "&& types_match (%s, %s)))\n",
2762 opname
, match_opname
, opname
, opname
, match_opname
,
2763 opname
, match_opname
);
2764 fprintf_indent (f
, indent
+ 2, "{\n");
2768 /* Generate GIMPLE matching code for the decision tree operand. */
2771 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2773 expr
*e
= static_cast<expr
*> (op
);
2774 id_base
*id
= e
->operation
;
2775 unsigned n_ops
= e
->ops
.length ();
2776 unsigned n_braces
= 0;
2778 for (unsigned i
= 0; i
< n_ops
; ++i
)
2780 char child_opname
[20];
2781 gen_opname (child_opname
, i
);
2783 if (id
->kind
== id_base::CODE
)
2786 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2787 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2789 /* ??? If this is a memory operation we can't (and should not)
2790 match this. The only sensible operand types are
2791 SSA names and invariants. */
2796 fprintf_indent (f
, indent
,
2797 "tree %s = TREE_OPERAND (%s, %i);\n",
2798 child_opname
, opname
, i
);
2801 fprintf_indent (f
, indent
,
2802 "tree %s = TREE_OPERAND "
2803 "(gimple_assign_rhs1 (def), %i);\n",
2805 fprintf_indent (f
, indent
,
2806 "if ((TREE_CODE (%s) == SSA_NAME\n",
2808 fprintf_indent (f
, indent
,
2809 " || is_gimple_min_invariant (%s)))\n",
2811 fprintf_indent (f
, indent
,
2815 fprintf_indent (f
, indent
,
2816 "%s = do_valueize (valueize, %s);\n",
2817 child_opname
, child_opname
);
2821 fprintf_indent (f
, indent
,
2822 "tree %s = gimple_assign_rhs%u (def);\n",
2823 child_opname
, i
+ 1);
2826 fprintf_indent (f
, indent
,
2827 "tree %s = gimple_call_arg (def, %u);\n",
2829 fprintf_indent (f
, indent
,
2830 "%s = do_valueize (valueize, %s);\n",
2831 child_opname
, child_opname
);
2833 /* While the toplevel operands are canonicalized by the caller
2834 after valueizing operands of sub-expressions we have to
2835 re-canonicalize operand order. */
2836 int opno
= commutative_op (id
);
2839 char child_opname0
[20], child_opname1
[20];
2840 gen_opname (child_opname0
, opno
);
2841 gen_opname (child_opname1
, opno
+ 1);
2842 fprintf_indent (f
, indent
,
2843 "if (tree_swap_operands_p (%s, %s))\n",
2844 child_opname0
, child_opname1
);
2845 fprintf_indent (f
, indent
,
2846 " std::swap (%s, %s);\n",
2847 child_opname0
, child_opname1
);
2853 /* Generate GENERIC matching code for the decision tree operand. */
2856 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2858 expr
*e
= static_cast<expr
*> (op
);
2859 unsigned n_ops
= e
->ops
.length ();
2861 for (unsigned i
= 0; i
< n_ops
; ++i
)
2863 char child_opname
[20];
2864 gen_opname (child_opname
, i
);
2866 if (e
->operation
->kind
== id_base::CODE
)
2867 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2868 child_opname
, opname
, i
);
2870 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2871 child_opname
, opname
, i
);
2877 /* Generate matching code for the children of the decision tree node. */
2880 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2882 auto_vec
<dt_operand
*> gimple_exprs
;
2883 auto_vec
<dt_operand
*> generic_exprs
;
2884 auto_vec
<dt_operand
*> fns
;
2885 auto_vec
<dt_operand
*> generic_fns
;
2886 auto_vec
<dt_operand
*> preds
;
2887 auto_vec
<dt_node
*> others
;
2889 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2891 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2893 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2894 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2896 if (e
->ops
.length () == 0
2897 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2898 generic_exprs
.safe_push (op
);
2899 else if (e
->operation
->kind
== id_base::FN
)
2904 generic_fns
.safe_push (op
);
2906 else if (e
->operation
->kind
== id_base::PREDICATE
)
2907 preds
.safe_push (op
);
2910 if (gimple
&& !e
->is_generic
)
2911 gimple_exprs
.safe_push (op
);
2913 generic_exprs
.safe_push (op
);
2916 else if (op
->op
->type
== operand::OP_PREDICATE
)
2917 others
.safe_push (kids
[i
]);
2921 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2922 others
.safe_push (kids
[i
]);
2923 else if (kids
[i
]->type
== dt_node::DT_MATCH
2924 || kids
[i
]->type
== dt_node::DT_TRUE
)
2926 /* A DT_TRUE operand serves as a barrier - generate code now
2927 for what we have collected sofar.
2928 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2929 dependent matches to get out-of-order. Generate code now
2930 for what we have collected sofar. */
2931 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2932 fns
, generic_fns
, preds
, others
);
2933 /* And output the true operand itself. */
2934 kids
[i
]->gen (f
, indent
, gimple
);
2935 gimple_exprs
.truncate (0);
2936 generic_exprs
.truncate (0);
2938 generic_fns
.truncate (0);
2940 others
.truncate (0);
2946 /* Generate code for the remains. */
2947 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2948 fns
, generic_fns
, preds
, others
);
2951 /* Generate matching code for the children of the decision tree node. */
2954 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2955 vec
<dt_operand
*> gimple_exprs
,
2956 vec
<dt_operand
*> generic_exprs
,
2957 vec
<dt_operand
*> fns
,
2958 vec
<dt_operand
*> generic_fns
,
2959 vec
<dt_operand
*> preds
,
2960 vec
<dt_node
*> others
)
2963 char *kid_opname
= buf
;
2965 unsigned exprs_len
= gimple_exprs
.length ();
2966 unsigned gexprs_len
= generic_exprs
.length ();
2967 unsigned fns_len
= fns
.length ();
2968 unsigned gfns_len
= generic_fns
.length ();
2970 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2973 gimple_exprs
[0]->get_name (kid_opname
);
2975 fns
[0]->get_name (kid_opname
);
2977 generic_fns
[0]->get_name (kid_opname
);
2979 generic_exprs
[0]->get_name (kid_opname
);
2981 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2982 fprintf_indent (f
, indent
, " {\n");
2986 if (exprs_len
|| fns_len
)
2988 fprintf_indent (f
, indent
,
2989 "case SSA_NAME:\n");
2990 fprintf_indent (f
, indent
,
2991 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2993 fprintf_indent (f
, indent
,
2998 fprintf_indent (f
, indent
,
2999 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
3000 fprintf_indent (f
, indent
,
3001 " switch (gimple_assign_rhs_code (def))\n");
3003 fprintf_indent (f
, indent
, "{\n");
3004 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3006 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3007 id_base
*op
= e
->operation
;
3008 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3009 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3011 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3012 fprintf_indent (f
, indent
, " {\n");
3013 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
3014 fprintf_indent (f
, indent
, " break;\n");
3015 fprintf_indent (f
, indent
, " }\n");
3017 fprintf_indent (f
, indent
, "default:;\n");
3018 fprintf_indent (f
, indent
, "}\n");
3024 fprintf_indent (f
, indent
,
3025 "%sif (gcall *def = dyn_cast <gcall *>"
3027 exprs_len
? "else " : "");
3028 fprintf_indent (f
, indent
,
3029 " switch (gimple_call_combined_fn (def))\n");
3032 fprintf_indent (f
, indent
, "{\n");
3033 for (unsigned i
= 0; i
< fns_len
; ++i
)
3035 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3036 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3037 fprintf_indent (f
, indent
, " {\n");
3038 fns
[i
]->gen (f
, indent
+ 4, true);
3039 fprintf_indent (f
, indent
, " break;\n");
3040 fprintf_indent (f
, indent
, " }\n");
3043 fprintf_indent (f
, indent
, "default:;\n");
3044 fprintf_indent (f
, indent
, "}\n");
3049 fprintf_indent (f
, indent
, " }\n");
3050 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3051 here rather than in the next loop. */
3052 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3054 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3055 id_base
*op
= e
->operation
;
3056 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3058 fprintf_indent (f
, indent
+ 4, "{\n");
3059 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
3060 fprintf_indent (f
, indent
+ 4, "}\n");
3064 fprintf_indent (f
, indent
, " break;\n");
3067 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3069 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3070 id_base
*op
= e
->operation
;
3071 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3072 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3073 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3074 /* Already handled above. */
3077 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3078 fprintf_indent (f
, indent
, " {\n");
3079 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
3080 fprintf_indent (f
, indent
, " break;\n");
3081 fprintf_indent (f
, indent
, " }\n");
3086 fprintf_indent (f
, indent
,
3087 "case CALL_EXPR:\n");
3088 fprintf_indent (f
, indent
,
3089 " switch (get_call_combined_fn (%s))\n",
3091 fprintf_indent (f
, indent
,
3095 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3097 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3098 gcc_assert (e
->operation
->kind
== id_base::FN
);
3100 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3101 fprintf_indent (f
, indent
, " {\n");
3102 generic_fns
[j
]->gen (f
, indent
+ 4, false);
3103 fprintf_indent (f
, indent
, " break;\n");
3104 fprintf_indent (f
, indent
, " }\n");
3106 fprintf_indent (f
, indent
, "default:;\n");
3109 fprintf_indent (f
, indent
, " }\n");
3110 fprintf_indent (f
, indent
, " break;\n");
3113 /* Close switch (TREE_CODE ()). */
3114 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3117 fprintf_indent (f
, indent
, " default:;\n");
3118 fprintf_indent (f
, indent
, " }\n");
3121 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3123 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3124 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3125 preds
[i
]->get_name (kid_opname
);
3126 fprintf_indent (f
, indent
, "{\n");
3128 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3129 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3130 gimple
? "gimple" : "tree",
3131 p
->id
, kid_opname
, kid_opname
,
3132 gimple
? ", valueize" : "");
3133 fprintf_indent (f
, indent
, " {\n");
3134 for (int j
= 0; j
< p
->nargs
; ++j
)
3136 char child_opname
[20];
3137 preds
[i
]->gen_opname (child_opname
, j
);
3138 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3139 child_opname
, kid_opname
, j
);
3141 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3144 fprintf_indent (f
, indent
, "}\n");
3147 for (unsigned i
= 0; i
< others
.length (); ++i
)
3148 others
[i
]->gen (f
, indent
, gimple
);
3151 /* Generate matching code for the decision tree operand. */
3154 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3159 unsigned n_braces
= 0;
3161 if (type
== DT_OPERAND
)
3164 case operand::OP_PREDICATE
:
3165 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3168 case operand::OP_EXPR
:
3170 n_braces
= gen_gimple_expr (f
, indent
);
3172 n_braces
= gen_generic_expr (f
, indent
, opname
);
3178 else if (type
== DT_TRUE
)
3180 else if (type
== DT_MATCH
)
3181 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3185 indent
+= 4 * n_braces
;
3186 gen_kids (f
, indent
, gimple
);
3188 for (unsigned i
= 0; i
< n_braces
; ++i
)
3193 fprintf_indent (f
, indent
, " }\n");
3198 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3199 step of a '(simplify ...)' or '(match ...)'. This handles everything
3200 that is not part of the decision tree (simplify->match).
3201 Main recursive worker. */
3204 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3208 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3210 fprintf_indent (f
, indent
, "{\n");
3212 output_line_directive (f
, w
->location
);
3213 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3214 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3216 fprintf_indent (f
, indent
, "}\n");
3219 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3221 output_line_directive (f
, ife
->location
);
3222 fprintf_indent (f
, indent
, "if (");
3223 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3225 fprintf_indent (f
, indent
+ 2, "{\n");
3227 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3229 fprintf_indent (f
, indent
+ 2, "}\n");
3232 fprintf_indent (f
, indent
, "else\n");
3233 fprintf_indent (f
, indent
+ 2, "{\n");
3235 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3237 fprintf_indent (f
, indent
+ 2, "}\n");
3243 /* Analyze captures and perform early-outs on the incoming arguments
3244 that cover cases we cannot handle. */
3245 capture_info
cinfo (s
, result
, gimple
);
3246 if (s
->kind
== simplify::SIMPLIFY
)
3250 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3251 if (cinfo
.force_no_side_effects
& (1 << i
))
3253 fprintf_indent (f
, indent
,
3254 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3257 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3258 "forcing toplevel operand to have no "
3261 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3262 if (cinfo
.info
[i
].cse_p
)
3264 else if (cinfo
.info
[i
].force_no_side_effects_p
3265 && (cinfo
.info
[i
].toplevel_msk
3266 & cinfo
.force_no_side_effects
) == 0)
3268 fprintf_indent (f
, indent
,
3269 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3270 "return NULL_TREE;\n", i
);
3272 warning_at (cinfo
.info
[i
].c
->location
,
3273 "forcing captured operand to have no "
3276 else if ((cinfo
.info
[i
].toplevel_msk
3277 & cinfo
.force_no_side_effects
) != 0)
3278 /* Mark capture as having no side-effects if we had to verify
3279 that via forced toplevel operand checks. */
3280 cinfo
.info
[i
].force_no_side_effects_p
= true;
3284 /* Force single-use restriction by only allowing simple
3285 results via setting seq to NULL. */
3286 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3287 bool first_p
= true;
3288 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3289 if (cinfo
.info
[i
].force_single_use
)
3293 fprintf_indent (f
, indent
, "if (lseq\n");
3294 fprintf_indent (f
, indent
, " && (");
3300 fprintf_indent (f
, indent
, " || ");
3302 fprintf (f
, "!single_use (captures[%d])", i
);
3306 fprintf (f
, "))\n");
3307 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3312 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3313 "fprintf (dump_file, \"Applying pattern ");
3314 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3315 output_line_directive (f
,
3316 result
? result
->location
: s
->match
->location
, true,
3318 fprintf (f
, ", __FILE__, __LINE__);\n");
3322 /* If there is no result then this is a predicate implementation. */
3323 fprintf_indent (f
, indent
, "return true;\n");
3327 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3328 in outermost position). */
3329 if (result
->type
== operand::OP_EXPR
3330 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3331 result
= as_a
<expr
*> (result
)->ops
[0];
3332 if (result
->type
== operand::OP_EXPR
)
3334 expr
*e
= as_a
<expr
*> (result
);
3335 id_base
*opr
= e
->operation
;
3336 bool is_predicate
= false;
3337 /* When we delay operator substituting during lowering of fors we
3338 make sure that for code-gen purposes the effects of each substitute
3339 are the same. Thus just look at that. */
3340 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3341 opr
= uid
->substitutes
[0];
3342 else if (is_a
<predicate_id
*> (opr
))
3343 is_predicate
= true;
3345 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3346 *e
->operation
== CONVERT_EXPR
3347 ? "NOP_EXPR" : e
->operation
->id
,
3349 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3353 snprintf (dest
, 32, "res_ops[%d]", j
);
3355 snprintf (dest
, 32, "res_op->ops[%d]", j
);
3357 = get_operand_type (opr
, j
,
3358 "type", e
->expr_type
,
3360 : "TREE_TYPE (res_op->ops[0])");
3361 /* We need to expand GENERIC conditions we captured from
3362 COND_EXPRs and we need to unshare them when substituting
3364 int cond_handling
= 0;
3366 cond_handling
= ((*opr
== COND_EXPR
3367 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3368 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3369 &cinfo
, indexes
, cond_handling
);
3372 /* Re-fold the toplevel result. It's basically an embedded
3373 gimple_build w/o actually building the stmt. */
3375 fprintf_indent (f
, indent
,
3376 "gimple_resimplify%d (lseq, res_op,"
3377 " valueize);\n", e
->ops
.length ());
3379 else if (result
->type
== operand::OP_CAPTURE
3380 || result
->type
== operand::OP_C_EXPR
)
3382 fprintf_indent (f
, indent
, "tree tem;\n");
3383 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3385 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3386 if (is_a
<capture
*> (result
)
3387 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3389 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3390 with substituting a capture of that. */
3391 fprintf_indent (f
, indent
,
3392 "if (COMPARISON_CLASS_P (tem))\n");
3393 fprintf_indent (f
, indent
,
3395 fprintf_indent (f
, indent
,
3396 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3397 fprintf_indent (f
, indent
,
3398 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3399 fprintf_indent (f
, indent
,
3405 fprintf_indent (f
, indent
, "return true;\n");
3409 bool is_predicate
= false;
3410 if (result
->type
== operand::OP_EXPR
)
3412 expr
*e
= as_a
<expr
*> (result
);
3413 id_base
*opr
= e
->operation
;
3414 /* When we delay operator substituting during lowering of fors we
3415 make sure that for code-gen purposes the effects of each substitute
3416 are the same. Thus just look at that. */
3417 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3418 opr
= uid
->substitutes
[0];
3419 else if (is_a
<predicate_id
*> (opr
))
3420 is_predicate
= true;
3421 /* Search for captures used multiple times in the result expression
3422 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3423 original expression. */
3425 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3427 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3428 || cinfo
.info
[i
].cse_p
)
3430 if (cinfo
.info
[i
].result_use_count
3431 > cinfo
.info
[i
].match_use_count
)
3432 fprintf_indent (f
, indent
,
3433 "if (! tree_invariant_p (captures[%d])) "
3434 "return NULL_TREE;\n", i
);
3436 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3440 snprintf (dest
, 32, "res_ops[%d]", j
);
3443 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3444 snprintf (dest
, 32, "res_op%d", j
);
3447 = get_operand_type (opr
, j
,
3448 "type", e
->expr_type
,
3450 ? NULL
: "TREE_TYPE (res_op0)");
3451 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3455 fprintf_indent (f
, indent
, "return true;\n");
3458 fprintf_indent (f
, indent
, "tree res;\n");
3459 /* Re-fold the toplevel result. Use non_lvalue to
3460 build NON_LVALUE_EXPRs so they get properly
3461 ignored when in GIMPLE form. */
3462 if (*opr
== NON_LVALUE_EXPR
)
3463 fprintf_indent (f
, indent
,
3464 "res = non_lvalue_loc (loc, res_op0);\n");
3467 if (is_a
<operator_id
*> (opr
))
3468 fprintf_indent (f
, indent
,
3469 "res = fold_build%d_loc (loc, %s, type",
3471 *e
->operation
== CONVERT_EXPR
3472 ? "NOP_EXPR" : e
->operation
->id
);
3474 fprintf_indent (f
, indent
,
3475 "res = maybe_build_call_expr_loc (loc, "
3476 "%s, type, %d", e
->operation
->id
,
3478 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3479 fprintf (f
, ", res_op%d", j
);
3480 fprintf (f
, ");\n");
3481 if (!is_a
<operator_id
*> (opr
))
3483 fprintf_indent (f
, indent
, "if (!res)\n");
3484 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3489 else if (result
->type
== operand::OP_CAPTURE
3490 || result
->type
== operand::OP_C_EXPR
)
3493 fprintf_indent (f
, indent
, "tree res;\n");
3494 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3501 /* Search for captures not used in the result expression and dependent
3502 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3503 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3505 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3507 if (!cinfo
.info
[i
].force_no_side_effects_p
3508 && !cinfo
.info
[i
].expr_p
3509 && cinfo
.info
[i
].result_use_count
== 0)
3511 fprintf_indent (f
, indent
,
3512 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3514 fprintf_indent (f
, indent
+ 2,
3515 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3516 "fold_ignored_result (captures[%d]), res);\n",
3520 fprintf_indent (f
, indent
, "return res;\n");
3525 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3526 step of a '(simplify ...)' or '(match ...)'. This handles everything
3527 that is not part of the decision tree (simplify->match). */
3530 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3532 fprintf_indent (f
, indent
, "{\n");
3534 output_line_directive (f
,
3535 s
->result
? s
->result
->location
: s
->match
->location
);
3536 if (s
->capture_max
>= 0)
3539 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3540 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3542 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3546 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3548 fprintf (f
, " };\n");
3551 /* If we have a split-out function for the actual transform, call it. */
3552 if (info
&& info
->fname
)
3556 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3557 "valueize, type, captures", info
->fname
);
3558 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3559 if (s
->for_subst_vec
[i
].first
->used
)
3560 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3561 fprintf (f
, "))\n");
3562 fprintf_indent (f
, indent
, " return true;\n");
3566 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3568 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3569 fprintf (f
, ", op%d", i
);
3570 fprintf (f
, ", captures");
3571 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3573 if (s
->for_subst_vec
[i
].first
->used
)
3574 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3576 fprintf (f
, ");\n");
3577 fprintf_indent (f
, indent
, "if (res) return res;\n");
3582 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3584 if (! s
->for_subst_vec
[i
].first
->used
)
3586 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3587 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3588 s
->for_subst_vec
[i
].first
->id
,
3589 s
->for_subst_vec
[i
].second
->id
);
3590 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3591 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3592 s
->for_subst_vec
[i
].first
->id
,
3593 s
->for_subst_vec
[i
].second
->id
);
3597 gen_1 (f
, indent
, gimple
, s
->result
);
3601 fprintf_indent (f
, indent
, "}\n");
3605 /* Hash function for finding equivalent transforms. */
3608 sinfo_hashmap_traits::hash (const key_type
&v
)
3610 /* Only bother to compare those originating from the same source pattern. */
3611 return v
->s
->result
->location
;
3614 /* Compare function for finding equivalent transforms. */
3617 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3619 if (o1
->type
!= o2
->type
)
3624 case operand::OP_IF
:
3626 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3627 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3628 /* ??? Properly compare c-exprs. */
3629 if (if1
->cond
!= if2
->cond
)
3631 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3633 if (if1
->falseexpr
!= if2
->falseexpr
3635 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3639 case operand::OP_WITH
:
3641 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3642 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3643 if (with1
->with
!= with2
->with
)
3645 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3650 /* We've hit a result. Time to compare capture-infos - this is required
3651 in addition to the conservative pointer-equivalency of the result IL. */
3652 capture_info
cinfo1 (s1
, o1
, true);
3653 capture_info
cinfo2 (s2
, o2
, true);
3655 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3656 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3659 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3661 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3662 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3663 || (cinfo1
.info
[i
].force_no_side_effects_p
3664 != cinfo2
.info
[i
].force_no_side_effects_p
)
3665 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3666 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3667 /* toplevel_msk is an optimization */
3668 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3669 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3670 /* the pointer back to the capture is for diagnostics only */)
3674 /* ??? Deep-compare the actual result. */
3679 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3680 const key_type
&candidate
)
3682 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3686 /* Main entry to generate code for matching GIMPLE IL off the decision
3690 decision_tree::gen (FILE *f
, bool gimple
)
3696 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3697 "a total number of %u nodes\n",
3698 gimple
? "GIMPLE" : "GENERIC",
3699 root
->num_leafs
, root
->max_level
, root
->total_size
);
3701 /* First split out the transform part of equal leafs. */
3704 for (sinfo_map_t::iterator iter
= si
.begin ();
3705 iter
!= si
.end (); ++iter
)
3707 sinfo
*s
= (*iter
).second
;
3708 /* Do not split out single uses. */
3715 fprintf (stderr
, "found %u uses of", s
->cnt
);
3716 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3719 /* Generate a split out function with the leaf transform code. */
3720 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3723 fprintf (f
, "\nstatic bool\n"
3724 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3725 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3726 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3731 fprintf (f
, "\nstatic tree\n"
3732 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3733 (*iter
).second
->fname
);
3734 for (unsigned i
= 0;
3735 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3736 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3737 fprintf (f
, " tree *captures\n");
3739 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3741 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3743 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3744 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3745 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3746 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3747 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3748 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3751 fprintf (f
, ")\n{\n");
3752 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3754 fprintf (f
, " return false;\n");
3756 fprintf (f
, " return NULL_TREE;\n");
3759 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3761 for (unsigned n
= 1; n
<= 5; ++n
)
3763 /* First generate split-out functions. */
3764 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3766 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3767 expr
*e
= static_cast<expr
*>(dop
->op
);
3768 if (e
->ops
.length () != n
3769 /* Builtin simplifications are somewhat premature on
3770 GENERIC. The following drops patterns with outermost
3771 calls. It's easy to emit overloads for function code
3772 though if necessary. */
3774 && e
->operation
->kind
!= id_base::CODE
))
3778 fprintf (f
, "\nstatic bool\n"
3779 "gimple_simplify_%s (gimple_match_op *res_op,"
3780 " gimple_seq *seq,\n"
3781 " tree (*valueize)(tree) "
3782 "ATTRIBUTE_UNUSED,\n"
3783 " code_helper ARG_UNUSED (code), tree "
3784 "ARG_UNUSED (type)\n",
3787 fprintf (f
, "\nstatic tree\n"
3788 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3789 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3791 for (unsigned i
= 0; i
< n
; ++i
)
3792 fprintf (f
, ", tree op%d", i
);
3795 dop
->gen_kids (f
, 2, gimple
);
3797 fprintf (f
, " return false;\n");
3799 fprintf (f
, " return NULL_TREE;\n");
3803 /* Then generate the main entry with the outermost switch and
3804 tail-calls to the split-out functions. */
3806 fprintf (f
, "\nstatic bool\n"
3807 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3808 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3809 " code_helper code, const tree type");
3811 fprintf (f
, "\ntree\n"
3812 "generic_simplify (location_t loc, enum tree_code code, "
3813 "const tree type ATTRIBUTE_UNUSED");
3814 for (unsigned i
= 0; i
< n
; ++i
)
3815 fprintf (f
, ", tree op%d", i
);
3820 fprintf (f
, " switch (code.get_rep())\n"
3823 fprintf (f
, " switch (code)\n"
3825 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3827 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3828 expr
*e
= static_cast<expr
*>(dop
->op
);
3829 if (e
->ops
.length () != n
3830 /* Builtin simplifications are somewhat premature on
3831 GENERIC. The following drops patterns with outermost
3832 calls. It's easy to emit overloads for function code
3833 though if necessary. */
3835 && e
->operation
->kind
!= id_base::CODE
))
3838 if (*e
->operation
== CONVERT_EXPR
3839 || *e
->operation
== NOP_EXPR
)
3840 fprintf (f
, " CASE_CONVERT:\n");
3842 fprintf (f
, " case %s%s:\n",
3843 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3846 fprintf (f
, " return gimple_simplify_%s (res_op, "
3847 "seq, valueize, code, type", e
->operation
->id
);
3849 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3851 for (unsigned i
= 0; i
< n
; ++i
)
3852 fprintf (f
, ", op%d", i
);
3853 fprintf (f
, ");\n");
3855 fprintf (f
, " default:;\n"
3859 fprintf (f
, " return false;\n");
3861 fprintf (f
, " return NULL_TREE;\n");
3866 /* Output code to implement the predicate P from the decision tree DT. */
3869 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3871 fprintf (f
, "\nbool\n"
3872 "%s%s (tree t%s%s)\n"
3873 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3874 p
->nargs
> 0 ? ", tree *res_ops" : "",
3875 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3876 /* Conveniently make 'type' available. */
3877 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3880 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3881 dt
.root
->gen_kids (f
, 2, gimple
);
3883 fprintf_indent (f
, 2, "return false;\n"
3887 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3890 write_header (FILE *f
, const char *head
)
3892 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3893 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3895 /* Include the header instead of writing it awkwardly quoted here. */
3896 fprintf (f
, "\n#include \"%s\"\n", head
);
3906 parser (cpp_reader
*);
3909 const cpp_token
*next ();
3910 const cpp_token
*peek (unsigned = 1);
3911 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3912 const cpp_token
*expect (enum cpp_ttype
);
3913 const cpp_token
*eat_token (enum cpp_ttype
);
3914 const char *get_string ();
3915 const char *get_ident ();
3916 const cpp_token
*eat_ident (const char *);
3917 const char *get_number ();
3919 unsigned get_internal_capture_id ();
3921 id_base
*parse_operation ();
3922 operand
*parse_capture (operand
*, bool);
3923 operand
*parse_expr ();
3924 c_expr
*parse_c_expr (cpp_ttype
);
3925 operand
*parse_op ();
3927 void record_operlist (source_location
, user_id
*);
3929 void parse_pattern ();
3930 operand
*parse_result (operand
*, predicate_id
*);
3931 void push_simplify (simplify::simplify_kind
,
3932 vec
<simplify
*>&, operand
*, operand
*);
3933 void parse_simplify (simplify::simplify_kind
,
3934 vec
<simplify
*>&, predicate_id
*, operand
*);
3935 void parse_for (source_location
);
3936 void parse_if (source_location
);
3937 void parse_predicates (source_location
);
3938 void parse_operator_list (source_location
);
3940 void finish_match_operand (operand
*);
3943 vec
<c_expr
*> active_ifs
;
3944 vec
<vec
<user_id
*> > active_fors
;
3945 hash_set
<user_id
*> *oper_lists_set
;
3946 vec
<user_id
*> oper_lists
;
3948 cid_map_t
*capture_ids
;
3952 vec
<simplify
*> simplifiers
;
3953 vec
<predicate_id
*> user_predicates
;
3954 bool parsing_match_operand
;
3957 /* Lexing helpers. */
3959 /* Read the next non-whitespace token from R. */
3964 const cpp_token
*token
;
3967 token
= cpp_get_token (r
);
3969 while (token
->type
== CPP_PADDING
);
3973 /* Peek at the next non-whitespace token from R. */
3976 parser::peek (unsigned num
)
3978 const cpp_token
*token
;
3982 token
= cpp_peek_token (r
, i
++);
3984 while (token
->type
== CPP_PADDING
3986 /* If we peek at EOF this is a fatal error as it leaves the
3987 cpp_reader in unusable state. Assume we really wanted a
3988 token and thus this EOF is unexpected. */
3989 if (token
->type
== CPP_EOF
)
3990 fatal_at (token
, "unexpected end of file");
3994 /* Peek at the next identifier token (or return NULL if the next
3995 token is not an identifier or equal to ID if supplied). */
3998 parser::peek_ident (const char *id
, unsigned num
)
4000 const cpp_token
*token
= peek (num
);
4001 if (token
->type
!= CPP_NAME
)
4007 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4008 if (strcmp (id
, t
) == 0)
4014 /* Read the next token from R and assert it is of type TK. */
4017 parser::expect (enum cpp_ttype tk
)
4019 const cpp_token
*token
= next ();
4020 if (token
->type
!= tk
)
4021 fatal_at (token
, "expected %s, got %s",
4022 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4027 /* Consume the next token from R and assert it is of type TK. */
4030 parser::eat_token (enum cpp_ttype tk
)
4035 /* Read the next token from R and assert it is of type CPP_STRING and
4036 return its value. */
4039 parser::get_string ()
4041 const cpp_token
*token
= expect (CPP_STRING
);
4042 return (const char *)token
->val
.str
.text
;
4045 /* Read the next token from R and assert it is of type CPP_NAME and
4046 return its value. */
4049 parser::get_ident ()
4051 const cpp_token
*token
= expect (CPP_NAME
);
4052 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4055 /* Eat an identifier token with value S from R. */
4058 parser::eat_ident (const char *s
)
4060 const cpp_token
*token
= peek ();
4061 const char *t
= get_ident ();
4062 if (strcmp (s
, t
) != 0)
4063 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4067 /* Read the next token from R and assert it is of type CPP_NUMBER and
4068 return its value. */
4071 parser::get_number ()
4073 const cpp_token
*token
= expect (CPP_NUMBER
);
4074 return (const char *)token
->val
.str
.text
;
4077 /* Return a capture ID that can be used internally. */
4080 parser::get_internal_capture_id ()
4082 unsigned newid
= capture_ids
->elements ();
4083 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4086 sprintf (id
, "__%u", newid
);
4087 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4089 fatal ("reserved capture id '%s' already used", id
);
4093 /* Record an operator-list use for transparent for handling. */
4096 parser::record_operlist (source_location loc
, user_id
*p
)
4098 if (!oper_lists_set
->add (p
))
4100 if (!oper_lists
.is_empty ()
4101 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4102 fatal_at (loc
, "User-defined operator list does not have the "
4103 "same number of entries as others used in the pattern");
4104 oper_lists
.safe_push (p
);
4108 /* Parse the operator ID, special-casing convert?, convert1? and
4112 parser::parse_operation ()
4114 const cpp_token
*id_tok
= peek ();
4115 const char *id
= get_ident ();
4116 const cpp_token
*token
= peek ();
4117 if (strcmp (id
, "convert0") == 0)
4118 fatal_at (id_tok
, "use 'convert?' here");
4119 else if (strcmp (id
, "view_convert0") == 0)
4120 fatal_at (id_tok
, "use 'view_convert?' here");
4121 if (token
->type
== CPP_QUERY
4122 && !(token
->flags
& PREV_WHITE
))
4124 if (strcmp (id
, "convert") == 0)
4126 else if (strcmp (id
, "convert1") == 0)
4128 else if (strcmp (id
, "convert2") == 0)
4130 else if (strcmp (id
, "view_convert") == 0)
4131 id
= "view_convert0";
4132 else if (strcmp (id
, "view_convert1") == 0)
4134 else if (strcmp (id
, "view_convert2") == 0)
4137 fatal_at (id_tok
, "non-convert operator conditionalized");
4139 if (!parsing_match_operand
)
4140 fatal_at (id_tok
, "conditional convert can only be used in "
4141 "match expression");
4142 eat_token (CPP_QUERY
);
4144 else if (strcmp (id
, "convert1") == 0
4145 || strcmp (id
, "convert2") == 0
4146 || strcmp (id
, "view_convert1") == 0
4147 || strcmp (id
, "view_convert2") == 0)
4148 fatal_at (id_tok
, "expected '?' after conditional operator");
4149 id_base
*op
= get_operator (id
);
4151 fatal_at (id_tok
, "unknown operator %s", id
);
4153 user_id
*p
= dyn_cast
<user_id
*> (op
);
4154 if (p
&& p
->is_oper_list
)
4156 if (active_fors
.length() == 0)
4157 record_operlist (id_tok
->src_loc
, p
);
4159 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4165 capture = '@'<number> */
4168 parser::parse_capture (operand
*op
, bool require_existing
)
4170 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4171 const cpp_token
*token
= peek ();
4172 const char *id
= NULL
;
4173 bool value_match
= false;
4174 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4175 if (token
->type
== CPP_ATSIGN
4176 && ! (token
->flags
& PREV_WHITE
)
4177 && parsing_match_operand
)
4179 eat_token (CPP_ATSIGN
);
4183 if (token
->type
== CPP_NUMBER
)
4185 else if (token
->type
== CPP_NAME
)
4188 fatal_at (token
, "expected number or identifier");
4189 unsigned next_id
= capture_ids
->elements ();
4191 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4194 if (require_existing
)
4195 fatal_at (src_loc
, "unknown capture id");
4198 return new capture (src_loc
, num
, op
, value_match
);
4201 /* Parse an expression
4202 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4205 parser::parse_expr ()
4207 const cpp_token
*token
= peek ();
4208 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4211 bool is_commutative
= false;
4212 bool force_capture
= false;
4213 const char *expr_type
= NULL
;
4215 if (token
->type
== CPP_COLON
4216 && !(token
->flags
& PREV_WHITE
))
4218 eat_token (CPP_COLON
);
4220 if (token
->type
== CPP_NAME
4221 && !(token
->flags
& PREV_WHITE
))
4223 const char *s
= get_ident ();
4224 if (!parsing_match_operand
)
4234 = dyn_cast
<operator_id
*> (e
->operation
))
4236 if (!commutative_tree_code (p
->code
)
4237 && !comparison_code_p (p
->code
))
4238 fatal_at (token
, "operation is not commutative");
4240 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4241 for (unsigned i
= 0;
4242 i
< p
->substitutes
.length (); ++i
)
4245 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4247 if (!commutative_tree_code (q
->code
)
4248 && !comparison_code_p (q
->code
))
4249 fatal_at (token
, "operation %s is not "
4250 "commutative", q
->id
);
4253 is_commutative
= true;
4255 else if (*sp
== 'C')
4256 is_commutative
= true;
4257 else if (*sp
== 's')
4259 e
->force_single_use
= true;
4260 force_capture
= true;
4263 fatal_at (token
, "flag %c not recognized", *sp
);
4270 fatal_at (token
, "expected flag or type specifying identifier");
4273 if (token
->type
== CPP_ATSIGN
4274 && !(token
->flags
& PREV_WHITE
))
4275 op
= parse_capture (e
, false);
4276 else if (force_capture
)
4278 unsigned num
= get_internal_capture_id ();
4279 op
= new capture (token
->src_loc
, num
, e
, false);
4285 const cpp_token
*token
= peek ();
4286 if (token
->type
== CPP_CLOSE_PAREN
)
4288 if (e
->operation
->nargs
!= -1
4289 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4290 fatal_at (token
, "'%s' expects %u operands, not %u",
4291 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4294 if (e
->ops
.length () == 2
4295 || commutative_op (e
->operation
) >= 0)
4296 e
->is_commutative
= true;
4298 fatal_at (token
, "only binary operators or functions with "
4299 "two arguments can be marked commutative, "
4300 "unless the operation is known to be inherently "
4303 e
->expr_type
= expr_type
;
4306 else if (!(token
->flags
& PREV_WHITE
))
4307 fatal_at (token
, "expected expression operand");
4309 e
->append_op (parse_op ());
4314 /* Lex native C code delimited by START recording the preprocessing tokens
4315 for later processing.
4316 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4319 parser::parse_c_expr (cpp_ttype start
)
4321 const cpp_token
*token
;
4324 vec
<cpp_token
> code
= vNULL
;
4325 unsigned nr_stmts
= 0;
4326 source_location loc
= eat_token (start
)->src_loc
;
4327 if (start
== CPP_OPEN_PAREN
)
4328 end
= CPP_CLOSE_PAREN
;
4329 else if (start
== CPP_OPEN_BRACE
)
4330 end
= CPP_CLOSE_BRACE
;
4338 /* Count brace pairs to find the end of the expr to match. */
4339 if (token
->type
== start
)
4341 else if (token
->type
== end
4344 else if (token
->type
== CPP_EOF
)
4345 fatal_at (token
, "unexpected end of file");
4347 /* This is a lame way of counting the number of statements. */
4348 if (token
->type
== CPP_SEMICOLON
)
4351 /* If this is possibly a user-defined identifier mark it used. */
4352 if (token
->type
== CPP_NAME
)
4354 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4355 (token
->val
.node
.node
)->ident
.str
);
4357 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4358 record_operlist (token
->src_loc
, p
);
4361 /* Record the token. */
4362 code
.safe_push (*token
);
4365 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4368 /* Parse an operand which is either an expression, a predicate or
4369 a standalone capture.
4370 op = predicate | expr | c_expr | capture */
4375 const cpp_token
*token
= peek ();
4376 struct operand
*op
= NULL
;
4377 if (token
->type
== CPP_OPEN_PAREN
)
4379 eat_token (CPP_OPEN_PAREN
);
4381 eat_token (CPP_CLOSE_PAREN
);
4383 else if (token
->type
== CPP_OPEN_BRACE
)
4385 op
= parse_c_expr (CPP_OPEN_BRACE
);
4389 /* Remaining ops are either empty or predicates */
4390 if (token
->type
== CPP_NAME
)
4392 const char *id
= get_ident ();
4393 id_base
*opr
= get_operator (id
);
4395 fatal_at (token
, "expected predicate name");
4396 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4398 if (code
->nargs
!= 0)
4399 fatal_at (token
, "using an operator with operands as predicate");
4400 /* Parse the zero-operand operator "predicates" as
4402 op
= new expr (opr
, token
->src_loc
);
4404 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4406 if (code
->nargs
!= 0)
4407 fatal_at (token
, "using an operator with operands as predicate");
4408 /* Parse the zero-operand operator "predicates" as
4410 op
= new expr (opr
, token
->src_loc
);
4412 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4413 op
= new predicate (p
, token
->src_loc
);
4415 fatal_at (token
, "using an unsupported operator as predicate");
4416 if (!parsing_match_operand
)
4417 fatal_at (token
, "predicates are only allowed in match expression");
4419 if (token
->flags
& PREV_WHITE
)
4422 else if (token
->type
!= CPP_COLON
4423 && token
->type
!= CPP_ATSIGN
)
4424 fatal_at (token
, "expected expression or predicate");
4425 /* optionally followed by a capture and a predicate. */
4426 if (token
->type
== CPP_COLON
)
4427 fatal_at (token
, "not implemented: predicate on leaf operand");
4428 if (token
->type
== CPP_ATSIGN
)
4429 op
= parse_capture (op
, !parsing_match_operand
);
4435 /* Create a new simplify from the current parsing state and MATCH,
4436 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4439 parser::push_simplify (simplify::simplify_kind kind
,
4440 vec
<simplify
*>& simplifiers
,
4441 operand
*match
, operand
*result
)
4443 /* Build and push a temporary for operator list uses in expressions. */
4444 if (!oper_lists
.is_empty ())
4445 active_fors
.safe_push (oper_lists
);
4447 simplifiers
.safe_push
4448 (new simplify (kind
, last_id
++, match
, result
,
4449 active_fors
.copy (), capture_ids
));
4451 if (!oper_lists
.is_empty ())
4456 <result-op> = <op> | <if> | <with>
4457 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4458 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4462 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4464 const cpp_token
*token
= peek ();
4465 if (token
->type
!= CPP_OPEN_PAREN
)
4468 eat_token (CPP_OPEN_PAREN
);
4469 if (peek_ident ("if"))
4472 if_expr
*ife
= new if_expr (token
->src_loc
);
4473 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4474 if (peek ()->type
== CPP_OPEN_PAREN
)
4476 ife
->trueexpr
= parse_result (result
, matcher
);
4477 if (peek ()->type
== CPP_OPEN_PAREN
)
4478 ife
->falseexpr
= parse_result (result
, matcher
);
4479 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4480 ife
->falseexpr
= parse_op ();
4482 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4484 ife
->trueexpr
= parse_op ();
4485 if (peek ()->type
== CPP_OPEN_PAREN
)
4486 ife
->falseexpr
= parse_result (result
, matcher
);
4487 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4488 ife
->falseexpr
= parse_op ();
4490 /* If this if is immediately closed then it contains a
4491 manual matcher or is part of a predicate definition. */
4492 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4495 fatal_at (peek (), "manual transform not implemented");
4496 ife
->trueexpr
= result
;
4498 eat_token (CPP_CLOSE_PAREN
);
4501 else if (peek_ident ("with"))
4504 with_expr
*withe
= new with_expr (token
->src_loc
);
4505 /* Parse (with c-expr expr) as (if-with (true) expr). */
4506 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4507 withe
->with
->nr_stmts
= 0;
4508 withe
->subexpr
= parse_result (result
, matcher
);
4509 eat_token (CPP_CLOSE_PAREN
);
4512 else if (peek_ident ("switch"))
4514 token
= eat_ident ("switch");
4515 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4517 if_expr
*ife
= new if_expr (ifloc
);
4519 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4520 if (peek ()->type
== CPP_OPEN_PAREN
)
4521 ife
->trueexpr
= parse_result (result
, matcher
);
4523 ife
->trueexpr
= parse_op ();
4524 eat_token (CPP_CLOSE_PAREN
);
4525 if (peek ()->type
!= CPP_OPEN_PAREN
4526 || !peek_ident ("if", 2))
4527 fatal_at (token
, "switch can be implemented with a single if");
4528 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4530 if (peek ()->type
== CPP_OPEN_PAREN
)
4532 if (peek_ident ("if", 2))
4534 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4536 ife
->falseexpr
= new if_expr (ifloc
);
4537 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4538 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4539 if (peek ()->type
== CPP_OPEN_PAREN
)
4540 ife
->trueexpr
= parse_result (result
, matcher
);
4542 ife
->trueexpr
= parse_op ();
4543 eat_token (CPP_CLOSE_PAREN
);
4547 /* switch default clause */
4548 ife
->falseexpr
= parse_result (result
, matcher
);
4549 eat_token (CPP_CLOSE_PAREN
);
4555 /* switch default clause */
4556 ife
->falseexpr
= parse_op ();
4557 eat_token (CPP_CLOSE_PAREN
);
4561 eat_token (CPP_CLOSE_PAREN
);
4566 operand
*op
= result
;
4569 eat_token (CPP_CLOSE_PAREN
);
4575 simplify = 'simplify' <expr> <result-op>
4577 match = 'match' <ident> <expr> [<result-op>]
4578 and fill SIMPLIFIERS with the results. */
4581 parser::parse_simplify (simplify::simplify_kind kind
,
4582 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4585 /* Reset the capture map. */
4587 capture_ids
= new cid_map_t
;
4588 /* Reset oper_lists and set. */
4589 hash_set
<user_id
*> olist
;
4590 oper_lists_set
= &olist
;
4593 const cpp_token
*loc
= peek ();
4594 parsing_match_operand
= true;
4595 struct operand
*match
= parse_op ();
4596 finish_match_operand (match
);
4597 parsing_match_operand
= false;
4598 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4599 fatal_at (loc
, "outermost expression cannot be captured");
4600 if (match
->type
== operand::OP_EXPR
4601 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4602 fatal_at (loc
, "outermost expression cannot be a predicate");
4604 /* Splice active_ifs onto result and continue parsing the
4606 if_expr
*active_if
= NULL
;
4607 for (int i
= active_ifs
.length (); i
> 0; --i
)
4609 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4610 ifc
->cond
= active_ifs
[i
-1];
4611 ifc
->trueexpr
= active_if
;
4614 if_expr
*outermost_if
= active_if
;
4615 while (active_if
&& active_if
->trueexpr
)
4616 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4618 const cpp_token
*token
= peek ();
4620 /* If this if is immediately closed then it is part of a predicate
4621 definition. Push it. */
4622 if (token
->type
== CPP_CLOSE_PAREN
)
4625 fatal_at (token
, "expected transform expression");
4628 active_if
->trueexpr
= result
;
4629 result
= outermost_if
;
4631 push_simplify (kind
, simplifiers
, match
, result
);
4635 operand
*tem
= parse_result (result
, matcher
);
4638 active_if
->trueexpr
= tem
;
4639 result
= outermost_if
;
4644 push_simplify (kind
, simplifiers
, match
, result
);
4647 /* Parsing of the outer control structures. */
4649 /* Parse a for expression
4650 for = '(' 'for' <subst>... <pattern> ')'
4651 subst = <ident> '(' <ident>... ')' */
4654 parser::parse_for (source_location
)
4656 auto_vec
<const cpp_token
*> user_id_tokens
;
4657 vec
<user_id
*> user_ids
= vNULL
;
4658 const cpp_token
*token
;
4659 unsigned min_n_opers
= 0, max_n_opers
= 0;
4664 if (token
->type
!= CPP_NAME
)
4667 /* Insert the user defined operators into the operator hash. */
4668 const char *id
= get_ident ();
4669 if (get_operator (id
, true) != NULL
)
4670 fatal_at (token
, "operator already defined");
4671 user_id
*op
= new user_id (id
);
4672 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4674 user_ids
.safe_push (op
);
4675 user_id_tokens
.safe_push (token
);
4677 eat_token (CPP_OPEN_PAREN
);
4680 while ((token
= peek_ident ()) != 0)
4682 const char *oper
= get_ident ();
4683 id_base
*idb
= get_operator (oper
, true);
4685 fatal_at (token
, "no such operator '%s'", oper
);
4686 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4687 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4688 || *idb
== VIEW_CONVERT2
)
4689 fatal_at (token
, "conditional operators cannot be used inside for");
4693 else if (idb
->nargs
== -1)
4695 else if (idb
->nargs
!= arity
)
4696 fatal_at (token
, "operator '%s' with arity %d does not match "
4697 "others with arity %d", oper
, idb
->nargs
, arity
);
4699 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4702 if (p
->is_oper_list
)
4703 op
->substitutes
.safe_splice (p
->substitutes
);
4705 fatal_at (token
, "iterator cannot be used as operator-list");
4708 op
->substitutes
.safe_push (idb
);
4711 token
= expect (CPP_CLOSE_PAREN
);
4713 unsigned nsubstitutes
= op
->substitutes
.length ();
4714 if (nsubstitutes
== 0)
4715 fatal_at (token
, "A user-defined operator must have at least "
4716 "one substitution");
4717 if (max_n_opers
== 0)
4719 min_n_opers
= nsubstitutes
;
4720 max_n_opers
= nsubstitutes
;
4724 if (nsubstitutes
% min_n_opers
!= 0
4725 && min_n_opers
% nsubstitutes
!= 0)
4726 fatal_at (token
, "All user-defined identifiers must have a "
4727 "multiple number of operator substitutions of the "
4728 "smallest number of substitutions");
4729 if (nsubstitutes
< min_n_opers
)
4730 min_n_opers
= nsubstitutes
;
4731 else if (nsubstitutes
> max_n_opers
)
4732 max_n_opers
= nsubstitutes
;
4736 unsigned n_ids
= user_ids
.length ();
4738 fatal_at (token
, "for requires at least one user-defined identifier");
4741 if (token
->type
== CPP_CLOSE_PAREN
)
4742 fatal_at (token
, "no pattern defined in for");
4744 active_fors
.safe_push (user_ids
);
4748 if (token
->type
== CPP_CLOSE_PAREN
)
4754 /* Remove user-defined operators from the hash again. */
4755 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4757 if (!user_ids
[i
]->used
)
4758 warning_at (user_id_tokens
[i
],
4759 "operator %s defined but not used", user_ids
[i
]->id
);
4760 operators
->remove_elt (user_ids
[i
]);
4764 /* Parse an identifier associated with a list of operators.
4765 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4768 parser::parse_operator_list (source_location
)
4770 const cpp_token
*token
= peek ();
4771 const char *id
= get_ident ();
4773 if (get_operator (id
, true) != 0)
4774 fatal_at (token
, "operator %s already defined", id
);
4776 user_id
*op
= new user_id (id
, true);
4779 while ((token
= peek_ident ()) != 0)
4782 const char *oper
= get_ident ();
4783 id_base
*idb
= get_operator (oper
, true);
4786 fatal_at (token
, "no such operator '%s'", oper
);
4790 else if (idb
->nargs
== -1)
4792 else if (arity
!= idb
->nargs
)
4793 fatal_at (token
, "operator '%s' with arity %d does not match "
4794 "others with arity %d", oper
, idb
->nargs
, arity
);
4796 /* We allow composition of multiple operator lists. */
4797 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4798 op
->substitutes
.safe_splice (p
->substitutes
);
4800 op
->substitutes
.safe_push (idb
);
4803 // Check that there is no junk after id-list
4805 if (token
->type
!= CPP_CLOSE_PAREN
)
4806 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4808 if (op
->substitutes
.length () == 0)
4809 fatal_at (token
, "operator-list cannot be empty");
4812 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4816 /* Parse an outer if expression.
4817 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4820 parser::parse_if (source_location
)
4822 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4824 const cpp_token
*token
= peek ();
4825 if (token
->type
== CPP_CLOSE_PAREN
)
4826 fatal_at (token
, "no pattern defined in if");
4828 active_ifs
.safe_push (ifexpr
);
4831 const cpp_token
*token
= peek ();
4832 if (token
->type
== CPP_CLOSE_PAREN
)
4840 /* Parse a list of predefined predicate identifiers.
4841 preds = '(' 'define_predicates' <ident>... ')' */
4844 parser::parse_predicates (source_location
)
4848 const cpp_token
*token
= peek ();
4849 if (token
->type
!= CPP_NAME
)
4852 add_predicate (get_ident ());
4857 /* Parse outer control structures.
4858 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4861 parser::parse_pattern ()
4863 /* All clauses start with '('. */
4864 eat_token (CPP_OPEN_PAREN
);
4865 const cpp_token
*token
= peek ();
4866 const char *id
= get_ident ();
4867 if (strcmp (id
, "simplify") == 0)
4869 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4872 else if (strcmp (id
, "match") == 0)
4874 bool with_args
= false;
4875 source_location e_loc
= peek ()->src_loc
;
4876 if (peek ()->type
== CPP_OPEN_PAREN
)
4878 eat_token (CPP_OPEN_PAREN
);
4881 const char *name
= get_ident ();
4882 id_base
*id
= get_operator (name
);
4886 p
= add_predicate (name
);
4887 user_predicates
.safe_push (p
);
4889 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4892 fatal_at (token
, "cannot add a match to a non-predicate ID");
4893 /* Parse (match <id> <arg>... (match-expr)) here. */
4897 capture_ids
= new cid_map_t
;
4898 e
= new expr (p
, e_loc
);
4899 while (peek ()->type
== CPP_ATSIGN
)
4900 e
->append_op (parse_capture (NULL
, false));
4901 eat_token (CPP_CLOSE_PAREN
);
4904 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4905 || (!e
&& p
->nargs
!= 0)))
4906 fatal_at (token
, "non-matching number of match operands");
4907 p
->nargs
= e
? e
->ops
.length () : 0;
4908 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4911 else if (strcmp (id
, "for") == 0)
4912 parse_for (token
->src_loc
);
4913 else if (strcmp (id
, "if") == 0)
4914 parse_if (token
->src_loc
);
4915 else if (strcmp (id
, "define_predicates") == 0)
4917 if (active_ifs
.length () > 0
4918 || active_fors
.length () > 0)
4919 fatal_at (token
, "define_predicates inside if or for is not supported");
4920 parse_predicates (token
->src_loc
);
4922 else if (strcmp (id
, "define_operator_list") == 0)
4924 if (active_ifs
.length () > 0
4925 || active_fors
.length () > 0)
4926 fatal_at (token
, "operator-list inside if or for is not supported");
4927 parse_operator_list (token
->src_loc
);
4930 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4931 active_ifs
.length () == 0 && active_fors
.length () == 0
4932 ? "'define_predicates', " : "");
4934 eat_token (CPP_CLOSE_PAREN
);
4937 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4941 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4946 if (capture
*c
= dyn_cast
<capture
*> (op
))
4948 cpts
[c
->where
].safe_push (c
);
4949 walk_captures (c
->what
, cpts
);
4951 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4952 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4953 walk_captures (e
->ops
[i
], cpts
);
4956 /* Finish up OP which is a match operand. */
4959 parser::finish_match_operand (operand
*op
)
4961 /* Look for matching captures, diagnose mis-uses of @@ and apply
4962 early lowering and distribution of value_match. */
4963 auto_vec
<vec
<capture
*> > cpts
;
4964 cpts
.safe_grow_cleared (capture_ids
->elements ());
4965 walk_captures (op
, cpts
);
4966 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4968 capture
*value_match
= NULL
;
4969 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4971 if (cpts
[i
][j
]->value_match
)
4974 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4975 value_match
= cpts
[i
][j
];
4978 if (cpts
[i
].length () == 1 && value_match
)
4979 fatal_at (value_match
->location
, "@@ without a matching capture");
4982 /* Duplicate prevailing capture with the existing ID, create
4983 a fake ID and rewrite all captures to use it. This turns
4984 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4985 value_match
->what
= new capture (value_match
->location
,
4987 value_match
->what
, false);
4988 /* Create a fake ID and rewrite all captures to use it. */
4989 unsigned newid
= get_internal_capture_id ();
4990 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4992 cpts
[i
][j
]->where
= newid
;
4993 cpts
[i
][j
]->value_match
= true;
5000 /* Main entry of the parser. Repeatedly parse outer control structures. */
5002 parser::parser (cpp_reader
*r_
)
5006 active_fors
= vNULL
;
5007 simplifiers
= vNULL
;
5008 oper_lists_set
= NULL
;
5011 user_predicates
= vNULL
;
5012 parsing_match_operand
= false;
5015 const cpp_token
*token
= next ();
5016 while (token
->type
!= CPP_EOF
)
5018 _cpp_backup_tokens (r
, 1);
5025 /* Helper for the linemap code. */
5028 round_alloc_size (size_t s
)
5034 /* The genmatch generator progam. It reads from a pattern description
5035 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5038 main (int argc
, char **argv
)
5042 progname
= "genmatch";
5048 char *input
= argv
[argc
-1];
5049 for (int i
= 1; i
< argc
- 1; ++i
)
5051 if (strcmp (argv
[i
], "--gimple") == 0)
5053 else if (strcmp (argv
[i
], "--generic") == 0)
5055 else if (strcmp (argv
[i
], "-v") == 0)
5057 else if (strcmp (argv
[i
], "-vv") == 0)
5061 fprintf (stderr
, "Usage: genmatch "
5062 "[--gimple] [--generic] [-v[v]] input\n");
5067 line_table
= XCNEW (struct line_maps
);
5068 linemap_init (line_table
, 0);
5069 line_table
->reallocator
= xrealloc
;
5070 line_table
->round_alloc_size
= round_alloc_size
;
5072 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5073 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5074 cb
->error
= error_cb
;
5076 /* Add the build directory to the #include "" search path. */
5077 cpp_dir
*dir
= XCNEW (cpp_dir
);
5078 dir
->name
= getpwd ();
5080 dir
->name
= ASTRDUP (".");
5081 cpp_set_include_chains (r
, dir
, NULL
, false);
5083 if (!cpp_read_main_file (r
, input
))
5085 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5086 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5088 null_id
= new id_base (id_base::NULL_ID
, "null");
5090 /* Pre-seed operators. */
5091 operators
= new hash_table
<id_base
> (1024);
5092 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5093 add_operator (SYM, # SYM, # TYPE, NARGS);
5094 #define END_OF_BASE_TREE_CODES
5096 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5097 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5098 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5099 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5100 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5101 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5102 #undef END_OF_BASE_TREE_CODES
5105 /* Pre-seed builtin functions.
5106 ??? Cannot use N (name) as that is targetm.emultls.get_address
5107 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5108 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5109 add_function (ENUM, "CFN_" # ENUM);
5110 #include "builtins.def"
5112 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5113 add_function (IFN_##CODE, "CFN_" #CODE);
5114 #include "internal-fn.def"
5120 write_header (stdout
, "gimple-match-head.c");
5122 write_header (stdout
, "generic-match-head.c");
5124 /* Go over all predicates defined with patterns and perform
5125 lowering and code generation. */
5126 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5128 predicate_id
*pred
= p
.user_predicates
[i
];
5129 lower (pred
->matchers
, gimple
);
5132 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5133 print_matches (pred
->matchers
[i
]);
5136 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5137 dt
.insert (pred
->matchers
[i
], i
);
5142 write_predicate (stdout
, pred
, dt
, gimple
);
5145 /* Lower the main simplifiers and generate code for them. */
5146 lower (p
.simplifiers
, gimple
);
5149 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5150 print_matches (p
.simplifiers
[i
]);
5153 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5154 dt
.insert (p
.simplifiers
[i
], i
);
5159 dt
.gen (stdout
, gimple
);
5162 cpp_finish (r
, NULL
);