1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2019 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 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
187 output_line_directive (FILE *f
, location_t location
,
188 bool dumpfile
= false, bool fnargs
= false)
190 const line_map_ordinary
*map
;
191 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
192 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
195 /* When writing to a dumpfile only dump the filename. */
196 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
197 #if defined(DIR_SEPARATOR_2)
198 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
199 if (pos2
&& (!file
|| (pos2
> file
)))
208 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
210 fprintf (f
, "%s:%d", file
, loc
.line
);
213 /* Other gen programs really output line directives here, at least for
214 development it's right now more convenient to have line information
215 from the generated file. Still keep the directives as comment for now
216 to easily back-point to the meta-description. */
217 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
221 /* Pull in tree codes and builtin function codes from their
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
237 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
238 enum built_in_function
{
239 #include "builtins.def"
243 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
245 #include "internal-fn.def"
250 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
251 CFN_##ENUM = int (ENUM),
252 #include "builtins.def"
254 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
255 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
256 #include "internal-fn.def"
261 #include "case-cfn-macros.h"
263 /* Return true if CODE represents a commutative tree code. Otherwise
266 commutative_tree_code (enum tree_code code
)
272 case MULT_HIGHPART_EXPR
:
287 case WIDEN_MULT_EXPR
:
288 case VEC_WIDEN_MULT_HI_EXPR
:
289 case VEC_WIDEN_MULT_LO_EXPR
:
290 case VEC_WIDEN_MULT_EVEN_EXPR
:
291 case VEC_WIDEN_MULT_ODD_EXPR
:
300 /* Return true if CODE represents a ternary tree code for which the
301 first two operands are commutative. Otherwise return false. */
303 commutative_ternary_tree_code (enum tree_code code
)
307 case WIDEN_MULT_PLUS_EXPR
:
308 case WIDEN_MULT_MINUS_EXPR
:
318 /* Return true if CODE is a comparison. */
321 comparison_code_p (enum tree_code code
)
348 /* Base class for all identifiers the parser knows. */
350 struct id_base
: nofree_ptr_hash
<id_base
>
352 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
354 id_base (id_kind
, const char *, int = -1);
360 /* hash_table support. */
361 static inline hashval_t
hash (const id_base
*);
362 static inline int equal (const id_base
*, const id_base
*);
366 id_base::hash (const id_base
*op
)
372 id_base::equal (const id_base
*op1
,
375 return (op1
->hashval
== op2
->hashval
376 && strcmp (op1
->id
, op2
->id
) == 0);
379 /* The special id "null", which matches nothing. */
380 static id_base
*null_id
;
382 /* Hashtable of known pattern operators. This is pre-seeded from
383 all known tree codes and all known builtin function ids. */
384 static hash_table
<id_base
> *operators
;
386 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
391 hashval
= htab_hash_string (id
);
394 /* Identifier that maps to a tree code. */
396 struct operator_id
: public id_base
398 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
400 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
405 /* Identifier that maps to a builtin or internal function code. */
407 struct fn_id
: public id_base
409 fn_id (enum built_in_function fn_
, const char *id_
)
410 : id_base (id_base::FN
, id_
), fn (fn_
) {}
411 fn_id (enum internal_fn fn_
, const char *id_
)
412 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
418 /* Identifier that maps to a user-defined predicate. */
420 struct predicate_id
: public id_base
422 predicate_id (const char *id_
)
423 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
424 vec
<simplify
*> matchers
;
427 /* Identifier that maps to a operator defined by a 'for' directive. */
429 struct user_id
: public id_base
431 user_id (const char *id_
, bool is_oper_list_
= false)
432 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
433 used (false), is_oper_list (is_oper_list_
) {}
434 vec
<id_base
*> substitutes
;
442 is_a_helper
<fn_id
*>::test (id_base
*id
)
444 return id
->kind
== id_base::FN
;
450 is_a_helper
<operator_id
*>::test (id_base
*id
)
452 return id
->kind
== id_base::CODE
;
458 is_a_helper
<predicate_id
*>::test (id_base
*id
)
460 return id
->kind
== id_base::PREDICATE
;
466 is_a_helper
<user_id
*>::test (id_base
*id
)
468 return id
->kind
== id_base::USER
;
471 /* If ID has a pair of consecutive, commutative operands, return the
472 index of the first, otherwise return -1. */
475 commutative_op (id_base
*id
)
477 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
479 if (commutative_tree_code (code
->code
)
480 || commutative_ternary_tree_code (code
->code
))
484 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
496 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
498 int res
= commutative_op (uid
->substitutes
[0]);
501 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
502 if (res
!= commutative_op (uid
->substitutes
[i
]))
509 /* Add a predicate identifier to the hash. */
511 static predicate_id
*
512 add_predicate (const char *id
)
514 predicate_id
*p
= new predicate_id (id
);
515 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
517 fatal ("duplicate id definition");
522 /* Add a tree code identifier to the hash. */
525 add_operator (enum tree_code code
, const char *id
,
526 const char *tcc
, unsigned nargs
)
528 if (strcmp (tcc
, "tcc_unary") != 0
529 && strcmp (tcc
, "tcc_binary") != 0
530 && strcmp (tcc
, "tcc_comparison") != 0
531 && strcmp (tcc
, "tcc_expression") != 0
532 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
533 && strcmp (tcc
, "tcc_reference") != 0
534 /* To have INTEGER_CST and friends as "predicate operators". */
535 && strcmp (tcc
, "tcc_constant") != 0
536 /* And allow CONSTRUCTOR for vector initializers. */
537 && !(code
== CONSTRUCTOR
)
538 /* Allow SSA_NAME as predicate operator. */
539 && !(code
== SSA_NAME
))
541 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
542 if (code
== ADDR_EXPR
)
544 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
545 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
547 fatal ("duplicate id definition");
551 /* Add a built-in or internal function identifier to the hash. ID is
552 the name of its CFN_* enumeration value. */
554 template <typename T
>
556 add_function (T code
, const char *id
)
558 fn_id
*fn
= new fn_id (code
, id
);
559 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
561 fatal ("duplicate id definition");
565 /* Helper for easy comparing ID with tree code CODE. */
568 operator==(id_base
&id
, enum tree_code code
)
570 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
571 return oid
->code
== code
;
575 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
578 get_operator (const char *id
, bool allow_null
= false)
580 if (allow_null
&& strcmp (id
, "null") == 0)
583 id_base
tem (id_base::CODE
, id
);
585 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
588 /* If this is a user-defined identifier track whether it was used. */
589 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
595 bool all_upper
= true;
596 bool all_lower
= true;
597 for (unsigned int i
= 0; id
[i
]; ++i
)
600 else if (ISLOWER (id
[i
]))
604 /* Try in caps with _EXPR appended. */
605 id2
= ACONCAT ((id
, "_EXPR", NULL
));
606 for (unsigned int i
= 0; id2
[i
]; ++i
)
607 id2
[i
] = TOUPPER (id2
[i
]);
609 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
610 /* Try CFN_ instead of IFN_. */
611 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
612 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
613 /* Try prepending CFN_. */
614 id2
= ACONCAT (("CFN_", id
, NULL
));
618 new (&tem
) id_base (id_base::CODE
, id2
);
619 return operators
->find_with_hash (&tem
, tem
.hashval
);
622 /* Return the comparison operators that results if the operands are
623 swapped. This is safe for floating-point. */
626 swap_tree_comparison (operator_id
*p
)
638 return get_operator ("LT_EXPR");
640 return get_operator ("LE_EXPR");
642 return get_operator ("GT_EXPR");
644 return get_operator ("GE_EXPR");
646 return get_operator ("UNLT_EXPR");
648 return get_operator ("UNLE_EXPR");
650 return get_operator ("UNGT_EXPR");
652 return get_operator ("UNGE_EXPR");
658 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
661 /* The AST produced by parsing of the pattern definitions. */
666 /* The base class for operands. */
669 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
670 operand (enum op_type type_
, location_t loc_
)
671 : type (type_
), location (loc_
) {}
674 virtual void gen_transform (FILE *, int, const char *, bool, int,
675 const char *, capture_info
*,
678 { gcc_unreachable (); }
681 /* A predicate operand. Predicates are leafs in the AST. */
683 struct predicate
: public operand
685 predicate (predicate_id
*p_
, location_t loc
)
686 : operand (OP_PREDICATE
, loc
), p (p_
) {}
690 /* An operand that constitutes an expression. Expressions include
691 function calls and user-defined predicate invocations. */
693 struct expr
: public operand
695 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
696 : operand (OP_EXPR
, loc
), operation (operation_
),
697 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
698 is_generic (false), force_single_use (false) {}
700 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
701 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
702 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
703 void append_op (operand
*op
) { ops
.safe_push (op
); }
704 /* The operator and its operands. */
707 /* An explicitely specified type - used exclusively for conversions. */
708 const char *expr_type
;
709 /* Whether the operation is to be applied commutatively. This is
710 later lowered to two separate patterns. */
712 /* Whether the expression is expected to be in GENERIC form. */
714 /* Whether pushing any stmt to the sequence should be conditional
715 on this expression having a single-use. */
716 bool force_single_use
;
717 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
718 const char *, capture_info
*,
719 dt_operand
** = 0, int = 0);
722 /* An operator that is represented by native C code. This is always
723 a leaf operand in the AST. This class is also used to represent
724 the code to be generated for 'if' and 'with' expressions. */
726 struct c_expr
: public operand
728 /* A mapping of an identifier and its replacement. Used to apply
733 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
736 c_expr (cpp_reader
*r_
, location_t loc
,
737 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
738 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
739 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
740 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
741 /* cpplib tokens and state to transform this back to source. */
744 cid_map_t
*capture_ids
;
745 /* The number of statements parsed (well, the number of ';'s). */
747 /* The identifier replacement vector. */
749 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
750 const char *, capture_info
*,
751 dt_operand
** = 0, int = 0);
754 /* A wrapper around another operand that captures its value. */
756 struct capture
: public operand
758 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
759 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
761 /* Identifier index for the value. */
763 /* Whether in a match of two operands the compare should be for
764 equal values rather than equal atoms (boils down to a type
767 /* The captured value. */
769 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
770 const char *, capture_info
*,
771 dt_operand
** = 0, int = 0);
776 struct if_expr
: public operand
778 if_expr (location_t loc
)
779 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
785 /* with expression. */
787 struct with_expr
: public operand
789 with_expr (location_t loc
)
790 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
798 is_a_helper
<capture
*>::test (operand
*op
)
800 return op
->type
== operand::OP_CAPTURE
;
806 is_a_helper
<predicate
*>::test (operand
*op
)
808 return op
->type
== operand::OP_PREDICATE
;
814 is_a_helper
<c_expr
*>::test (operand
*op
)
816 return op
->type
== operand::OP_C_EXPR
;
822 is_a_helper
<expr
*>::test (operand
*op
)
824 return op
->type
== operand::OP_EXPR
;
830 is_a_helper
<if_expr
*>::test (operand
*op
)
832 return op
->type
== operand::OP_IF
;
838 is_a_helper
<with_expr
*>::test (operand
*op
)
840 return op
->type
== operand::OP_WITH
;
843 /* The main class of a pattern and its transform. This is used to
844 represent both (simplify ...) and (match ...) kinds. The AST
845 duplicates all outer 'if' and 'for' expressions here so each
846 simplify can exist in isolation. */
850 enum simplify_kind
{ SIMPLIFY
, MATCH
};
852 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
853 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
854 cid_map_t
*capture_ids_
)
855 : kind (kind_
), id (id_
), match (match_
), result (result_
),
856 for_vec (for_vec_
), for_subst_vec (vNULL
),
857 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
860 /* ID. This is kept to easily associate related simplifies expanded
861 from the same original one. */
863 /* The expression that is matched against the GENERIC or GIMPLE IL. */
865 /* For a (simplify ...) an expression with ifs and withs with the expression
866 produced when the pattern applies in the leafs.
867 For a (match ...) the leafs are either empty if it is a simple predicate
868 or the single expression specifying the matched operands. */
869 struct operand
*result
;
870 /* Collected 'for' expression operators that have to be replaced
871 in the lowering phase. */
872 vec
<vec
<user_id
*> > for_vec
;
873 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
874 /* A map of capture identifiers to indexes. */
875 cid_map_t
*capture_ids
;
879 /* Debugging routines for dumping the AST. */
882 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
884 if (capture
*c
= dyn_cast
<capture
*> (o
))
886 if (c
->what
&& flattened
== false)
887 print_operand (c
->what
, f
, flattened
);
888 fprintf (f
, "@%u", c
->where
);
891 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
892 fprintf (f
, "%s", p
->p
->id
);
894 else if (is_a
<c_expr
*> (o
))
895 fprintf (f
, "c_expr");
897 else if (expr
*e
= dyn_cast
<expr
*> (o
))
899 if (e
->ops
.length () == 0)
900 fprintf (f
, "%s", e
->operation
->id
);
903 fprintf (f
, "(%s", e
->operation
->id
);
905 if (flattened
== false)
907 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
910 print_operand (e
->ops
[i
], f
, flattened
);
922 print_matches (struct simplify
*s
, FILE *f
= stderr
)
924 fprintf (f
, "for expression: ");
925 print_operand (s
->match
, f
);
932 /* Lowering of commutative operators. */
935 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
936 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
938 if (n
== ops_vector
.length ())
940 vec
<operand
*> xv
= v
.copy ();
941 result
.safe_push (xv
);
945 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
947 v
[n
] = ops_vector
[n
][i
];
948 cartesian_product (ops_vector
, result
, v
, n
+ 1);
952 /* Lower OP to two operands in case it is marked as commutative. */
954 static vec
<operand
*>
955 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
957 vec
<operand
*> ret
= vNULL
;
959 if (capture
*c
= dyn_cast
<capture
*> (op
))
966 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
967 for (unsigned i
= 0; i
< v
.length (); ++i
)
969 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
976 expr
*e
= dyn_cast
<expr
*> (op
);
977 if (!e
|| e
->ops
.length () == 0)
983 vec
< vec
<operand
*> > ops_vector
= vNULL
;
984 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
985 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
987 auto_vec
< vec
<operand
*> > result
;
988 auto_vec
<operand
*> v (e
->ops
.length ());
989 v
.quick_grow_cleared (e
->ops
.length ());
990 cartesian_product (ops_vector
, result
, v
, 0);
993 for (unsigned i
= 0; i
< result
.length (); ++i
)
995 expr
*ne
= new expr (e
);
996 ne
->is_commutative
= false;
997 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
998 ne
->append_op (result
[i
][j
]);
1002 if (!e
->is_commutative
)
1005 /* The operation is always binary if it isn't inherently commutative. */
1006 int natural_opno
= commutative_op (e
->operation
);
1007 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1008 for (unsigned i
= 0; i
< result
.length (); ++i
)
1010 expr
*ne
= new expr (e
);
1011 if (operator_id
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
1013 if (comparison_code_p (p
->code
))
1014 ne
->operation
= swap_tree_comparison (p
);
1016 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1018 bool found_compare
= false;
1019 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1020 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1022 if (comparison_code_p (q
->code
)
1023 && swap_tree_comparison (q
) != q
)
1025 found_compare
= true;
1031 user_id
*newop
= new user_id ("<internal>");
1032 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1034 id_base
*subst
= p
->substitutes
[j
];
1035 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1037 if (comparison_code_p (q
->code
))
1038 subst
= swap_tree_comparison (q
);
1040 newop
->substitutes
.safe_push (subst
);
1042 ne
->operation
= newop
;
1043 /* Search for 'p' inside the for vector and push 'newop'
1044 to the same level. */
1045 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1046 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1047 if (for_vec
[j
][k
] == p
)
1049 for_vec
[j
].safe_push (newop
);
1055 ne
->is_commutative
= false;
1056 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1058 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1059 ne
->append_op (result
[i
][old_j
]);
1067 /* Lower operations marked as commutative in the AST of S and push
1068 the resulting patterns to SIMPLIFIERS. */
1071 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1073 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1074 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1076 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1077 s
->for_vec
, s
->capture_ids
);
1078 simplifiers
.safe_push (ns
);
1082 /* Strip conditional conversios using operator OPER from O and its
1083 children if STRIP, else replace them with an unconditional convert. */
1086 lower_opt_convert (operand
*o
, enum tree_code oper
,
1087 enum tree_code to_oper
, bool strip
)
1089 if (capture
*c
= dyn_cast
<capture
*> (o
))
1092 return new capture (c
->location
, c
->where
,
1093 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1099 expr
*e
= dyn_cast
<expr
*> (o
);
1103 if (*e
->operation
== oper
)
1106 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1108 expr
*ne
= new expr (e
);
1109 ne
->operation
= (to_oper
== CONVERT_EXPR
1110 ? get_operator ("CONVERT_EXPR")
1111 : get_operator ("VIEW_CONVERT_EXPR"));
1112 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1116 expr
*ne
= new expr (e
);
1117 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1118 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1123 /* Determine whether O or its children uses the conditional conversion
1127 has_opt_convert (operand
*o
, enum tree_code oper
)
1129 if (capture
*c
= dyn_cast
<capture
*> (o
))
1132 return has_opt_convert (c
->what
, oper
);
1137 expr
*e
= dyn_cast
<expr
*> (o
);
1141 if (*e
->operation
== oper
)
1144 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1145 if (has_opt_convert (e
->ops
[i
], oper
))
1151 /* Lower conditional convert operators in O, expanding it to a vector
1154 static vec
<operand
*>
1155 lower_opt_convert (operand
*o
)
1157 vec
<operand
*> v1
= vNULL
, v2
;
1161 enum tree_code opers
[]
1162 = { CONVERT0
, CONVERT_EXPR
,
1163 CONVERT1
, CONVERT_EXPR
,
1164 CONVERT2
, CONVERT_EXPR
,
1165 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1166 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1167 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1169 /* Conditional converts are lowered to a pattern with the
1170 conversion and one without. The three different conditional
1171 convert codes are lowered separately. */
1173 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1176 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1177 if (has_opt_convert (v1
[j
], opers
[i
]))
1179 v2
.safe_push (lower_opt_convert (v1
[j
],
1180 opers
[i
], opers
[i
+1], false));
1181 v2
.safe_push (lower_opt_convert (v1
[j
],
1182 opers
[i
], opers
[i
+1], true));
1188 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1189 v1
.safe_push (v2
[j
]);
1196 /* Lower conditional convert operators in the AST of S and push
1197 the resulting multiple patterns to SIMPLIFIERS. */
1200 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1202 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1203 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1205 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1206 s
->for_vec
, s
->capture_ids
);
1207 simplifiers
.safe_push (ns
);
1211 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1212 GENERIC and a GIMPLE variant. */
1214 static vec
<operand
*>
1215 lower_cond (operand
*o
)
1217 vec
<operand
*> ro
= vNULL
;
1219 if (capture
*c
= dyn_cast
<capture
*> (o
))
1223 vec
<operand
*> lop
= vNULL
;
1224 lop
= lower_cond (c
->what
);
1226 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1227 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1233 expr
*e
= dyn_cast
<expr
*> (o
);
1234 if (!e
|| e
->ops
.length () == 0)
1240 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1241 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1242 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1244 auto_vec
< vec
<operand
*> > result
;
1245 auto_vec
<operand
*> v (e
->ops
.length ());
1246 v
.quick_grow_cleared (e
->ops
.length ());
1247 cartesian_product (ops_vector
, result
, v
, 0);
1249 for (unsigned i
= 0; i
< result
.length (); ++i
)
1251 expr
*ne
= new expr (e
);
1252 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1253 ne
->append_op (result
[i
][j
]);
1255 /* If this is a COND with a captured expression or an
1256 expression with two operands then also match a GENERIC
1257 form on the compare. */
1258 if ((*e
->operation
== COND_EXPR
1259 || *e
->operation
== VEC_COND_EXPR
)
1260 && ((is_a
<capture
*> (e
->ops
[0])
1261 && as_a
<capture
*> (e
->ops
[0])->what
1262 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1264 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1265 || (is_a
<expr
*> (e
->ops
[0])
1266 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1268 expr
*ne
= new expr (e
);
1269 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1270 ne
->append_op (result
[i
][j
]);
1271 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1273 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1274 expr
*cmp
= new expr (ocmp
);
1275 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1276 cmp
->append_op (ocmp
->ops
[j
]);
1277 cmp
->is_generic
= true;
1278 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1283 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1284 expr
*cmp
= new expr (ocmp
);
1285 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1286 cmp
->append_op (ocmp
->ops
[j
]);
1287 cmp
->is_generic
= true;
1297 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1298 GENERIC and a GIMPLE variant. */
1301 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1303 vec
<operand
*> matchers
= lower_cond (s
->match
);
1304 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1306 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1307 s
->for_vec
, s
->capture_ids
);
1308 simplifiers
.safe_push (ns
);
1312 /* Return true if O refers to ID. */
1315 contains_id (operand
*o
, user_id
*id
)
1317 if (capture
*c
= dyn_cast
<capture
*> (o
))
1318 return c
->what
&& contains_id (c
->what
, id
);
1320 if (expr
*e
= dyn_cast
<expr
*> (o
))
1322 if (e
->operation
== id
)
1324 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1325 if (contains_id (e
->ops
[i
], id
))
1330 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1331 return (contains_id (w
->with
, id
)
1332 || contains_id (w
->subexpr
, id
));
1334 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1335 return (contains_id (ife
->cond
, id
)
1336 || contains_id (ife
->trueexpr
, id
)
1337 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1339 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1340 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1346 /* In AST operand O replace operator ID with operator WITH. */
1349 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1351 /* Deep-copy captures and expressions, replacing operations as
1353 if (capture
*c
= dyn_cast
<capture
*> (o
))
1357 return new capture (c
->location
, c
->where
,
1358 replace_id (c
->what
, id
, with
), c
->value_match
);
1360 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1362 expr
*ne
= new expr (e
);
1363 if (e
->operation
== id
)
1364 ne
->operation
= with
;
1365 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1366 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1369 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1371 with_expr
*nw
= new with_expr (w
->location
);
1372 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1373 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1376 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1378 if_expr
*nife
= new if_expr (ife
->location
);
1379 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1380 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1382 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1386 /* For c_expr we simply record a string replacement table which is
1387 applied at code-generation time. */
1388 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1390 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1391 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1392 return new c_expr (ce
->r
, ce
->location
,
1393 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1399 /* Return true if the binary operator OP is ok for delayed substitution
1400 during for lowering. */
1403 binary_ok (operator_id
*op
)
1410 case TRUNC_DIV_EXPR
:
1412 case FLOOR_DIV_EXPR
:
1413 case ROUND_DIV_EXPR
:
1414 case TRUNC_MOD_EXPR
:
1416 case FLOOR_MOD_EXPR
:
1417 case ROUND_MOD_EXPR
:
1419 case EXACT_DIV_EXPR
:
1431 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1434 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1436 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1437 unsigned worklist_start
= 0;
1438 auto_vec
<simplify
*> worklist
;
1439 worklist
.safe_push (sin
);
1441 /* Lower each recorded for separately, operating on the
1442 set of simplifiers created by the previous one.
1443 Lower inner-to-outer so inner for substitutes can refer
1444 to operators replaced by outer fors. */
1445 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1447 vec
<user_id
*>& ids
= for_vec
[fi
];
1448 unsigned n_ids
= ids
.length ();
1449 unsigned max_n_opers
= 0;
1450 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1451 for (unsigned i
= 0; i
< n_ids
; ++i
)
1453 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1454 max_n_opers
= ids
[i
]->substitutes
.length ();
1455 /* Require that all substitutes are of the same kind so that
1456 if we delay substitution to the result op code generation
1457 can look at the first substitute for deciding things like
1458 types of operands. */
1459 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1460 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1461 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1462 can_delay_subst
= false;
1463 else if (operator_id
*op
1464 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1467 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1468 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1469 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1471 /* Unfortunately we can't just allow all tcc_binary. */
1472 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1473 && strcmp (op0
->tcc
, "tcc_binary") == 0
1477 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1478 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1479 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1480 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1483 can_delay_subst
= false;
1485 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1488 can_delay_subst
= false;
1491 unsigned worklist_end
= worklist
.length ();
1492 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1494 simplify
*s
= worklist
[si
];
1495 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1497 operand
*match_op
= s
->match
;
1498 operand
*result_op
= s
->result
;
1499 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1501 for (unsigned i
= 0; i
< n_ids
; ++i
)
1503 user_id
*id
= ids
[i
];
1504 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1506 && (contains_id (match_op
, id
)
1507 || contains_id (result_op
, id
)))
1512 subst
.quick_push (std::make_pair (id
, oper
));
1513 match_op
= replace_id (match_op
, id
, oper
);
1515 && !can_delay_subst
)
1516 result_op
= replace_id (result_op
, id
, oper
);
1521 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1522 vNULL
, s
->capture_ids
);
1523 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1526 ns
->for_subst_vec
.safe_splice (subst
);
1528 worklist
.safe_push (ns
);
1531 worklist_start
= worklist_end
;
1534 /* Copy out the result from the last for lowering. */
1535 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1536 simplifiers
.safe_push (worklist
[i
]);
1539 /* Lower the AST for everything in SIMPLIFIERS. */
1542 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1544 auto_vec
<simplify
*> out_simplifiers
;
1545 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1546 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1548 simplifiers
.truncate (0);
1549 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1550 lower_commutative (out_simplifiers
[i
], simplifiers
);
1552 out_simplifiers
.truncate (0);
1554 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1555 lower_cond (simplifiers
[i
], out_simplifiers
);
1557 out_simplifiers
.safe_splice (simplifiers
);
1560 simplifiers
.truncate (0);
1561 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1562 lower_for (out_simplifiers
[i
], simplifiers
);
1568 /* The decision tree built for generating GIMPLE and GENERIC pattern
1569 matching code. It represents the 'match' expression of all
1570 simplifies and has those as its leafs. */
1574 /* A hash-map collecting semantically equivalent leafs in the decision
1575 tree for splitting out to separate functions. */
1584 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1587 static inline hashval_t
hash (const key_type
&);
1588 static inline bool equal_keys (const key_type
&, const key_type
&);
1589 template <typename T
> static inline void remove (T
&) {}
1592 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1595 /* Current simplifier ID we are processing during insertion into the
1597 static unsigned current_id
;
1599 /* Decision tree base class, used for DT_NODE. */
1603 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1608 vec
<dt_node
*> kids
;
1612 unsigned total_size
;
1615 dt_node (enum dt_type type_
, dt_node
*parent_
)
1616 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1618 dt_node
*append_node (dt_node
*);
1619 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1620 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1621 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1623 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1625 virtual void gen (FILE *, int, bool) {}
1627 void gen_kids (FILE *, int, bool);
1628 void gen_kids_1 (FILE *, int, bool,
1629 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1630 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1632 void analyze (sinfo_map_t
&);
1635 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1637 struct dt_operand
: public dt_node
1640 dt_operand
*match_dop
;
1645 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1646 dt_operand
*parent_
, unsigned pos_
)
1647 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1648 pos (pos_
), value_match (false), for_id (current_id
) {}
1650 void gen (FILE *, int, bool);
1651 unsigned gen_predicate (FILE *, int, const char *, bool);
1652 unsigned gen_match_op (FILE *, int, const char *, bool);
1654 unsigned gen_gimple_expr (FILE *, int);
1655 unsigned gen_generic_expr (FILE *, int, const char *);
1657 char *get_name (char *);
1658 void gen_opname (char *, unsigned);
1661 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1663 struct dt_simplify
: public dt_node
1666 unsigned pattern_no
;
1667 dt_operand
**indexes
;
1670 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1671 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1672 indexes (indexes_
), info (NULL
) {}
1674 void gen_1 (FILE *, int, bool, operand
*);
1675 void gen (FILE *f
, int, bool);
1681 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1683 return (n
->type
== dt_node::DT_OPERAND
1684 || n
->type
== dt_node::DT_MATCH
1685 || n
->type
== dt_node::DT_TRUE
);
1691 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1693 return n
->type
== dt_node::DT_SIMPLIFY
;
1698 /* A container for the actual decision tree. */
1700 struct decision_tree
1704 void insert (struct simplify
*, unsigned);
1705 void gen (FILE *f
, bool gimple
);
1706 void print (FILE *f
= stderr
);
1708 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1710 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1711 unsigned pos
= 0, dt_node
*parent
= 0);
1712 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1713 static bool cmp_node (dt_node
*, dt_node
*);
1714 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1717 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1720 cmp_operand (operand
*o1
, operand
*o2
)
1722 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1725 if (o1
->type
== operand::OP_PREDICATE
)
1727 predicate
*p1
= as_a
<predicate
*>(o1
);
1728 predicate
*p2
= as_a
<predicate
*>(o2
);
1729 return p1
->p
== p2
->p
;
1731 else if (o1
->type
== operand::OP_EXPR
)
1733 expr
*e1
= static_cast<expr
*>(o1
);
1734 expr
*e2
= static_cast<expr
*>(o2
);
1735 return (e1
->operation
== e2
->operation
1736 && e1
->is_generic
== e2
->is_generic
);
1742 /* Compare two decision tree nodes N1 and N2 and return true if they
1746 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1748 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1754 if (n1
->type
== dt_node::DT_TRUE
)
1757 if (n1
->type
== dt_node::DT_OPERAND
)
1758 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1759 (as_a
<dt_operand
*> (n2
))->op
);
1760 else if (n1
->type
== dt_node::DT_MATCH
)
1761 return (((as_a
<dt_operand
*> (n1
))->match_dop
1762 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1763 && ((as_a
<dt_operand
*> (n1
))->value_match
1764 == (as_a
<dt_operand
*> (n2
))->value_match
));
1768 /* Search OPS for a decision tree node like P and return it if found. */
1771 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1773 /* We can merge adjacent DT_TRUE. */
1774 if (p
->type
== dt_node::DT_TRUE
1776 && ops
.last ()->type
== dt_node::DT_TRUE
)
1778 dt_operand
*true_node
= NULL
;
1779 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1781 /* But we can't merge across DT_TRUE nodes as they serve as
1782 pattern order barriers to make sure that patterns apply
1783 in order of appearance in case multiple matches are possible. */
1784 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1787 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1788 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1790 if (decision_tree::cmp_node (ops
[i
], p
))
1792 /* Unless we are processing the same pattern or the blocking
1793 pattern is before the one we are going to merge with. */
1795 && true_node
->for_id
!= current_id
1796 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1800 location_t p_loc
= 0;
1801 if (p
->type
== dt_node::DT_OPERAND
)
1802 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1803 location_t op_loc
= 0;
1804 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1805 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1806 location_t true_loc
= 0;
1807 true_loc
= true_node
->op
->location
;
1809 "failed to merge decision tree node");
1811 "with the following");
1812 warning_at (true_loc
,
1813 "because of the following which serves as ordering "
1824 /* Append N to the decision tree if it there is not already an existing
1828 dt_node::append_node (dt_node
*n
)
1832 kid
= decision_tree::find_node (kids
, n
);
1837 n
->level
= this->level
+ 1;
1842 /* Append OP to the decision tree. */
1845 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1847 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1848 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1849 return append_node (n
);
1852 /* Append a DT_TRUE decision tree node. */
1855 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1857 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1858 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1859 return append_node (n
);
1862 /* Append a DT_MATCH decision tree node. */
1865 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1866 dt_node
*parent
, unsigned pos
)
1868 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1869 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1870 return append_node (n
);
1873 /* Append S to the decision tree. */
1876 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1877 dt_operand
**indexes
)
1879 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1880 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1881 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1883 warning_at (s
->match
->location
, "duplicate pattern");
1884 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1885 print_operand (s
->match
, stderr
);
1886 fprintf (stderr
, "\n");
1888 return append_node (n
);
1891 /* Analyze the node and its children. */
1894 dt_node::analyze (sinfo_map_t
&map
)
1900 if (type
== DT_SIMPLIFY
)
1902 /* Populate the map of equivalent simplifies. */
1903 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1905 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1920 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1922 kids
[i
]->analyze (map
);
1923 num_leafs
+= kids
[i
]->num_leafs
;
1924 total_size
+= kids
[i
]->total_size
;
1925 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1929 /* Insert O into the decision tree and return the decision tree node found
1933 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1934 unsigned pos
, dt_node
*parent
)
1936 dt_node
*q
, *elm
= 0;
1938 if (capture
*c
= dyn_cast
<capture
*> (o
))
1940 unsigned capt_index
= c
->where
;
1942 if (indexes
[capt_index
] == 0)
1945 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1948 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1951 // get to the last capture
1952 for (operand
*what
= c
->what
;
1953 what
&& is_a
<capture
*> (what
);
1954 c
= as_a
<capture
*> (what
), what
= c
->what
)
1959 unsigned cc_index
= c
->where
;
1960 dt_operand
*match_op
= indexes
[cc_index
];
1962 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1963 elm
= decision_tree::find_node (p
->kids
, &temp
);
1967 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1968 temp
.value_match
= c
->value_match
;
1969 elm
= decision_tree::find_node (p
->kids
, &temp
);
1974 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1975 elm
= decision_tree::find_node (p
->kids
, &temp
);
1979 gcc_assert (elm
->type
== dt_node::DT_TRUE
1980 || elm
->type
== dt_node::DT_OPERAND
1981 || elm
->type
== dt_node::DT_MATCH
);
1982 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1987 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
1988 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1990 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1995 p
= p
->append_op (o
, parent
, pos
);
1998 if (expr
*e
= dyn_cast
<expr
*>(o
))
2000 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2001 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2007 /* Insert S into the decision tree. */
2010 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
2013 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2014 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2015 p
->append_simplify (s
, pattern_no
, indexes
);
2018 /* Debug functions to dump the decision tree. */
2021 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2023 if (p
->type
== dt_node::DT_NODE
)
2024 fprintf (f
, "root");
2028 for (unsigned i
= 0; i
< indent
; i
++)
2031 if (p
->type
== dt_node::DT_OPERAND
)
2033 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2034 print_operand (dop
->op
, f
, true);
2036 else if (p
->type
== dt_node::DT_TRUE
)
2037 fprintf (f
, "true");
2038 else if (p
->type
== dt_node::DT_MATCH
)
2039 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2040 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2042 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2043 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2044 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2045 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2048 if (is_a
<dt_operand
*> (p
))
2049 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2052 fprintf (stderr
, " (%p, %p), %u, %u\n",
2053 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2055 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2056 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2060 decision_tree::print (FILE *f
)
2062 return decision_tree::print_node (root
, f
);
2066 /* For GENERIC we have to take care of wrapping multiple-used
2067 expressions with side-effects in save_expr and preserve side-effects
2068 of expressions with omit_one_operand. Analyze captures in
2069 match, result and with expressions and perform early-outs
2070 on the outermost match expression operands for cases we cannot
2075 capture_info (simplify
*s
, operand
*, bool);
2076 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2077 bool walk_result (operand
*o
, bool, operand
*);
2078 void walk_c_expr (c_expr
*);
2084 bool force_no_side_effects_p
;
2085 bool force_single_use
;
2086 bool cond_expr_cond_p
;
2087 unsigned long toplevel_msk
;
2088 unsigned match_use_count
;
2089 unsigned result_use_count
;
2094 auto_vec
<cinfo
> info
;
2095 unsigned long force_no_side_effects
;
2099 /* Analyze captures in S. */
2101 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2106 if (s
->kind
== simplify::MATCH
)
2108 force_no_side_effects
= -1;
2112 force_no_side_effects
= 0;
2113 info
.safe_grow_cleared (s
->capture_max
+ 1);
2114 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2115 info
[i
].same_as
= i
;
2117 e
= as_a
<expr
*> (s
->match
);
2118 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2119 walk_match (e
->ops
[i
], i
,
2120 (i
!= 0 && *e
->operation
== COND_EXPR
)
2121 || *e
->operation
== TRUTH_ANDIF_EXPR
2122 || *e
->operation
== TRUTH_ORIF_EXPR
,
2124 && (*e
->operation
== COND_EXPR
2125 || *e
->operation
== VEC_COND_EXPR
));
2127 walk_result (s
->result
, false, result
);
2130 /* Analyze captures in the match expression piece O. */
2133 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2134 bool conditional_p
, bool cond_expr_cond_p
)
2136 if (capture
*c
= dyn_cast
<capture
*> (o
))
2138 unsigned where
= c
->where
;
2139 info
[where
].match_use_count
++;
2140 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2141 info
[where
].force_no_side_effects_p
|= conditional_p
;
2142 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2147 /* Recurse to exprs and captures. */
2148 if (is_a
<capture
*> (c
->what
)
2149 || is_a
<expr
*> (c
->what
))
2150 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2151 /* We need to look past multiple captures to find a captured
2152 expression as with conditional converts two captures
2153 can be collapsed onto the same expression. Also collect
2154 what captures capture the same thing. */
2155 while (c
->what
&& is_a
<capture
*> (c
->what
))
2157 c
= as_a
<capture
*> (c
->what
);
2158 if (info
[c
->where
].same_as
!= c
->where
2159 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2160 fatal_at (c
->location
, "cannot handle this collapsed capture");
2161 info
[c
->where
].same_as
= info
[where
].same_as
;
2163 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2166 && (e
= dyn_cast
<expr
*> (c
->what
)))
2168 /* Zero-operand expression captures like ADDR_EXPR@0 are
2169 similar as predicates -- if they are not mentioned in
2170 the result we have to force them to have no side-effects. */
2171 if (e
->ops
.length () != 0)
2172 info
[where
].expr_p
= true;
2173 info
[where
].force_single_use
|= e
->force_single_use
;
2176 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2178 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2180 bool cond_p
= conditional_p
;
2181 bool cond_expr_cond_p
= false;
2182 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2184 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2185 || *e
->operation
== TRUTH_ORIF_EXPR
)
2188 && (*e
->operation
== COND_EXPR
2189 || *e
->operation
== VEC_COND_EXPR
))
2190 cond_expr_cond_p
= true;
2191 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2194 else if (is_a
<predicate
*> (o
))
2196 /* Mark non-captured leafs toplevel arg for checking. */
2197 force_no_side_effects
|= 1 << toplevel_arg
;
2200 warning_at (o
->location
,
2201 "forcing no side-effects on possibly lost leaf");
2207 /* Analyze captures in the result expression piece O. Return true
2208 if RESULT was visited in one of the children. Only visit
2209 non-if/with children if they are rooted on RESULT. */
2212 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2214 if (capture
*c
= dyn_cast
<capture
*> (o
))
2216 unsigned where
= info
[c
->where
].same_as
;
2217 info
[where
].result_use_count
++;
2218 /* If we substitute an expression capture we don't know
2219 which captures this will end up using (well, we don't
2220 compute that). Force the uses to be side-effect free
2221 which means forcing the toplevels that reach the
2222 expression side-effect free. */
2223 if (info
[where
].expr_p
)
2224 force_no_side_effects
|= info
[where
].toplevel_msk
;
2225 /* Mark CSE capture uses as forced to have no side-effects. */
2227 && is_a
<expr
*> (c
->what
))
2229 info
[where
].cse_p
= true;
2230 walk_result (c
->what
, true, result
);
2233 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2235 id_base
*opr
= e
->operation
;
2236 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2237 opr
= uid
->substitutes
[0];
2238 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2240 bool cond_p
= conditional_p
;
2241 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2243 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2244 || *e
->operation
== TRUTH_ORIF_EXPR
)
2246 walk_result (e
->ops
[i
], cond_p
, result
);
2249 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2251 /* 'if' conditions should be all fine. */
2252 if (e
->trueexpr
== result
)
2254 walk_result (e
->trueexpr
, false, result
);
2257 if (e
->falseexpr
== result
)
2259 walk_result (e
->falseexpr
, false, result
);
2263 if (is_a
<if_expr
*> (e
->trueexpr
)
2264 || is_a
<with_expr
*> (e
->trueexpr
))
2265 res
|= walk_result (e
->trueexpr
, false, result
);
2267 && (is_a
<if_expr
*> (e
->falseexpr
)
2268 || is_a
<with_expr
*> (e
->falseexpr
)))
2269 res
|= walk_result (e
->falseexpr
, false, result
);
2272 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2274 bool res
= (e
->subexpr
== result
);
2276 || is_a
<if_expr
*> (e
->subexpr
)
2277 || is_a
<with_expr
*> (e
->subexpr
))
2278 res
|= walk_result (e
->subexpr
, false, result
);
2280 walk_c_expr (e
->with
);
2283 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2291 /* Look for captures in the C expr E. */
2294 capture_info::walk_c_expr (c_expr
*e
)
2296 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2297 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2298 really escape through. */
2299 unsigned p_depth
= 0;
2300 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2302 const cpp_token
*t
= &e
->code
[i
];
2303 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2305 if (t
->type
== CPP_NAME
2306 && (strcmp ((const char *)CPP_HASHNODE
2307 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2308 || strcmp ((const char *)CPP_HASHNODE
2309 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2310 || strcmp ((const char *)CPP_HASHNODE
2311 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2312 || ((id
= get_operator ((const char *)CPP_HASHNODE
2313 (t
->val
.node
.node
)->ident
.str
))
2314 && is_a
<predicate_id
*> (id
)))
2315 && n
->type
== CPP_OPEN_PAREN
)
2317 else if (t
->type
== CPP_CLOSE_PAREN
2320 else if (p_depth
== 0
2321 && t
->type
== CPP_ATSIGN
2322 && (n
->type
== CPP_NUMBER
2323 || n
->type
== CPP_NAME
)
2324 && !(n
->flags
& PREV_WHITE
))
2327 if (n
->type
== CPP_NUMBER
)
2328 id
= (const char *)n
->val
.str
.text
;
2330 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2331 unsigned *where
= e
->capture_ids
->get(id
);
2333 fatal_at (n
, "unknown capture id '%s'", id
);
2334 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2337 warning_at (t
, "capture escapes");
2343 /* Code generation off the decision tree and the refered AST nodes. */
2346 is_conversion (id_base
*op
)
2348 return (*op
== CONVERT_EXPR
2350 || *op
== FLOAT_EXPR
2351 || *op
== FIX_TRUNC_EXPR
2352 || *op
== VIEW_CONVERT_EXPR
);
2355 /* Get the type to be used for generating operand POS of OP from the
2359 get_operand_type (id_base
*op
, unsigned pos
,
2360 const char *in_type
,
2361 const char *expr_type
,
2362 const char *other_oprnd_type
)
2364 /* Generally operands whose type does not match the type of the
2365 expression generated need to know their types but match and
2366 thus can fall back to 'other_oprnd_type'. */
2367 if (is_conversion (op
))
2368 return other_oprnd_type
;
2369 else if (*op
== REALPART_EXPR
2370 || *op
== IMAGPART_EXPR
)
2371 return other_oprnd_type
;
2372 else if (is_a
<operator_id
*> (op
)
2373 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2374 return other_oprnd_type
;
2375 else if (*op
== COND_EXPR
2377 return "boolean_type_node";
2378 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2380 /* IFN_COND_* operands 1 and later by default have the same type
2381 as the result. The type of operand 0 needs to be specified
2383 if (pos
> 0 && expr_type
)
2385 else if (pos
> 0 && in_type
)
2392 /* Otherwise all types should match - choose one in order of
2399 return other_oprnd_type
;
2403 /* Generate transform code for an expression. */
2406 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2407 int depth
, const char *in_type
, capture_info
*cinfo
,
2408 dt_operand
**indexes
, int)
2410 id_base
*opr
= operation
;
2411 /* When we delay operator substituting during lowering of fors we
2412 make sure that for code-gen purposes the effects of each substitute
2413 are the same. Thus just look at that. */
2414 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2415 opr
= uid
->substitutes
[0];
2417 bool conversion_p
= is_conversion (opr
);
2418 const char *type
= expr_type
;
2421 /* If there was a type specification in the pattern use it. */
2423 else if (conversion_p
)
2424 /* For conversions we need to build the expression using the
2425 outer type passed in. */
2427 else if (*opr
== REALPART_EXPR
2428 || *opr
== IMAGPART_EXPR
)
2430 /* __real and __imag use the component type of its operand. */
2431 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2434 else if (is_a
<operator_id
*> (opr
)
2435 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2437 /* comparisons use boolean_type_node (or what gets in), but
2438 their operands need to figure out the types themselves. */
2443 sprintf (optype
, "boolean_type_node");
2448 else if (*opr
== COND_EXPR
2449 || *opr
== VEC_COND_EXPR
2450 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2452 /* Conditions are of the same type as their first alternative. */
2453 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2458 /* Other operations are of the same type as their first operand. */
2459 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2463 fatal_at (location
, "cannot determine type of operand");
2465 fprintf_indent (f
, indent
, "{\n");
2467 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2469 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2470 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2473 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2475 = get_operand_type (opr
, i
, in_type
, expr_type
,
2476 i
== 0 ? NULL
: op0type
);
2477 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2480 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2483 const char *opr_name
;
2484 if (*operation
== CONVERT_EXPR
)
2485 opr_name
= "NOP_EXPR";
2487 opr_name
= operation
->id
;
2491 if (*opr
== CONVERT_EXPR
)
2493 fprintf_indent (f
, indent
,
2494 "if (%s != TREE_TYPE (ops%d[0])\n",
2496 fprintf_indent (f
, indent
,
2497 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2499 fprintf_indent (f
, indent
+ 2, "{\n");
2502 /* ??? Building a stmt can fail for various reasons here, seq being
2503 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2504 So if we fail here we should continue matching other patterns. */
2505 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2506 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2507 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2508 fprintf (f
, ", ops%d[%u]", depth
, i
);
2509 fprintf (f
, ");\n");
2510 fprintf_indent (f
, indent
,
2511 "gimple_resimplify%d (lseq, &tem_op, valueize);\n",
2513 fprintf_indent (f
, indent
,
2514 "res = maybe_push_res_to_seq (&tem_op, lseq);\n");
2515 fprintf_indent (f
, indent
,
2516 "if (!res) return false;\n");
2517 if (*opr
== CONVERT_EXPR
)
2520 fprintf_indent (f
, indent
, " }\n");
2521 fprintf_indent (f
, indent
, "else\n");
2522 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2527 if (*opr
== CONVERT_EXPR
)
2529 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2533 if (opr
->kind
== id_base::CODE
)
2534 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2535 ops
.length(), opr_name
, type
);
2538 fprintf_indent (f
, indent
, "{\n");
2539 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2540 "%s, %s, %d", opr_name
, type
, ops
.length());
2542 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2543 fprintf (f
, ", ops%d[%u]", depth
, i
);
2544 fprintf (f
, ");\n");
2545 if (opr
->kind
!= id_base::CODE
)
2547 fprintf_indent (f
, indent
, " if (!res)\n");
2548 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2549 fprintf_indent (f
, indent
, "}\n");
2551 if (*opr
== CONVERT_EXPR
)
2554 fprintf_indent (f
, indent
, "else\n");
2555 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2558 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2560 fprintf_indent (f
, indent
, "}\n");
2563 /* Generate code for a c_expr which is either the expression inside
2564 an if statement or a sequence of statements which computes a
2565 result to be stored to DEST. */
2568 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2569 bool, int, const char *, capture_info
*,
2572 if (dest
&& nr_stmts
== 1)
2573 fprintf_indent (f
, indent
, "%s = ", dest
);
2575 unsigned stmt_nr
= 1;
2576 for (unsigned i
= 0; i
< code
.length (); ++i
)
2578 const cpp_token
*token
= &code
[i
];
2580 /* Replace captures for code-gen. */
2581 if (token
->type
== CPP_ATSIGN
)
2583 const cpp_token
*n
= &code
[i
+1];
2584 if ((n
->type
== CPP_NUMBER
2585 || n
->type
== CPP_NAME
)
2586 && !(n
->flags
& PREV_WHITE
))
2588 if (token
->flags
& PREV_WHITE
)
2591 if (n
->type
== CPP_NUMBER
)
2592 id
= (const char *)n
->val
.str
.text
;
2594 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2595 unsigned *cid
= capture_ids
->get (id
);
2597 fatal_at (token
, "unknown capture id");
2598 fprintf (f
, "captures[%u]", *cid
);
2604 if (token
->flags
& PREV_WHITE
)
2607 if (token
->type
== CPP_NAME
)
2609 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2611 for (j
= 0; j
< ids
.length (); ++j
)
2613 if (strcmp (id
, ids
[j
].id
) == 0)
2615 fprintf (f
, "%s", ids
[j
].oper
);
2619 if (j
< ids
.length ())
2623 /* Output the token as string. */
2624 char *tk
= (char *)cpp_token_as_text (r
, token
);
2627 if (token
->type
== CPP_SEMICOLON
)
2631 if (dest
&& stmt_nr
== nr_stmts
)
2632 fprintf_indent (f
, indent
, "%s = ", dest
);
2637 /* Generate transform code for a capture. */
2640 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2641 int depth
, const char *in_type
, capture_info
*cinfo
,
2642 dt_operand
**indexes
, int cond_handling
)
2644 if (what
&& is_a
<expr
*> (what
))
2646 if (indexes
[where
] == 0)
2649 sprintf (buf
, "captures[%u]", where
);
2650 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2655 /* If in GENERIC some capture is used multiple times, unshare it except
2656 when emitting the last use. */
2658 && cinfo
->info
.exists ()
2659 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2661 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2663 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2666 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2668 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2669 with substituting a capture of that. */
2671 && cond_handling
!= 0
2672 && cinfo
->info
[where
].cond_expr_cond_p
)
2674 /* If substituting into a cond_expr condition, unshare. */
2675 if (cond_handling
== 1)
2676 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2677 /* If substituting elsewhere we might need to decompose it. */
2678 else if (cond_handling
== 2)
2680 /* ??? Returning false here will also not allow any other patterns
2681 to match unless this generator was split out. */
2682 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2683 fprintf_indent (f
, indent
, " {\n");
2684 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2685 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2687 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2688 " TREE_OPERAND (%s, 1));\n",
2689 dest
, dest
, dest
, dest
, dest
);
2690 fprintf_indent (f
, indent
, " }\n");
2695 /* Return the name of the operand representing the decision tree node.
2696 Use NAME as space to generate it. */
2699 dt_operand::get_name (char *name
)
2702 sprintf (name
, "t");
2703 else if (parent
->level
== 1)
2704 sprintf (name
, "op%u", pos
);
2705 else if (parent
->type
== dt_node::DT_MATCH
)
2706 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2708 sprintf (name
, "o%u%u", parent
->level
, pos
);
2712 /* Fill NAME with the operand name at position POS. */
2715 dt_operand::gen_opname (char *name
, unsigned pos
)
2718 sprintf (name
, "op%u", pos
);
2720 sprintf (name
, "o%u%u", level
, pos
);
2723 /* Generate matching code for the decision tree operand which is
2727 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2729 predicate
*p
= as_a
<predicate
*> (op
);
2731 if (p
->p
->matchers
.exists ())
2733 /* If this is a predicate generated from a pattern mangle its
2734 name and pass on the valueize hook. */
2736 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2739 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2742 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2743 fprintf_indent (f
, indent
+ 2, "{\n");
2747 /* Generate matching code for the decision tree operand which is
2751 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2753 char match_opname
[20];
2754 match_dop
->get_name (match_opname
);
2756 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2757 "|| operand_equal_p (%s, %s, 0))\n",
2758 opname
, match_opname
, opname
, opname
, match_opname
);
2760 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2761 "|| (operand_equal_p (%s, %s, 0) "
2762 "&& types_match (%s, %s)))\n",
2763 opname
, match_opname
, opname
, opname
, match_opname
,
2764 opname
, match_opname
);
2765 fprintf_indent (f
, indent
+ 2, "{\n");
2769 /* Generate GIMPLE matching code for the decision tree operand. */
2772 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2774 expr
*e
= static_cast<expr
*> (op
);
2775 id_base
*id
= e
->operation
;
2776 unsigned n_ops
= e
->ops
.length ();
2777 unsigned n_braces
= 0;
2779 for (unsigned i
= 0; i
< n_ops
; ++i
)
2781 char child_opname
[20];
2782 gen_opname (child_opname
, i
);
2784 if (id
->kind
== id_base::CODE
)
2787 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2788 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2790 /* ??? If this is a memory operation we can't (and should not)
2791 match this. The only sensible operand types are
2792 SSA names and invariants. */
2797 fprintf_indent (f
, indent
,
2798 "tree %s = TREE_OPERAND (%s, %i);\n",
2799 child_opname
, opname
, i
);
2802 fprintf_indent (f
, indent
,
2803 "tree %s = TREE_OPERAND "
2804 "(gimple_assign_rhs1 (def), %i);\n",
2806 fprintf_indent (f
, indent
,
2807 "if ((TREE_CODE (%s) == SSA_NAME\n",
2809 fprintf_indent (f
, indent
,
2810 " || is_gimple_min_invariant (%s)))\n",
2812 fprintf_indent (f
, indent
,
2816 fprintf_indent (f
, indent
,
2817 "%s = do_valueize (valueize, %s);\n",
2818 child_opname
, child_opname
);
2822 fprintf_indent (f
, indent
,
2823 "tree %s = gimple_assign_rhs%u (def);\n",
2824 child_opname
, i
+ 1);
2827 fprintf_indent (f
, indent
,
2828 "tree %s = gimple_call_arg (def, %u);\n",
2830 fprintf_indent (f
, indent
,
2831 "%s = do_valueize (valueize, %s);\n",
2832 child_opname
, child_opname
);
2834 /* While the toplevel operands are canonicalized by the caller
2835 after valueizing operands of sub-expressions we have to
2836 re-canonicalize operand order. */
2837 int opno
= commutative_op (id
);
2840 char child_opname0
[20], child_opname1
[20];
2841 gen_opname (child_opname0
, opno
);
2842 gen_opname (child_opname1
, opno
+ 1);
2843 fprintf_indent (f
, indent
,
2844 "if (tree_swap_operands_p (%s, %s))\n",
2845 child_opname0
, child_opname1
);
2846 fprintf_indent (f
, indent
,
2847 " std::swap (%s, %s);\n",
2848 child_opname0
, child_opname1
);
2854 /* Generate GENERIC matching code for the decision tree operand. */
2857 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2859 expr
*e
= static_cast<expr
*> (op
);
2860 unsigned n_ops
= e
->ops
.length ();
2862 for (unsigned i
= 0; i
< n_ops
; ++i
)
2864 char child_opname
[20];
2865 gen_opname (child_opname
, i
);
2867 if (e
->operation
->kind
== id_base::CODE
)
2868 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2869 child_opname
, opname
, i
);
2871 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2872 child_opname
, opname
, i
);
2878 /* Generate matching code for the children of the decision tree node. */
2881 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2883 auto_vec
<dt_operand
*> gimple_exprs
;
2884 auto_vec
<dt_operand
*> generic_exprs
;
2885 auto_vec
<dt_operand
*> fns
;
2886 auto_vec
<dt_operand
*> generic_fns
;
2887 auto_vec
<dt_operand
*> preds
;
2888 auto_vec
<dt_node
*> others
;
2890 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2892 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2894 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2895 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2897 if (e
->ops
.length () == 0
2898 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2899 generic_exprs
.safe_push (op
);
2900 else if (e
->operation
->kind
== id_base::FN
)
2905 generic_fns
.safe_push (op
);
2907 else if (e
->operation
->kind
== id_base::PREDICATE
)
2908 preds
.safe_push (op
);
2911 if (gimple
&& !e
->is_generic
)
2912 gimple_exprs
.safe_push (op
);
2914 generic_exprs
.safe_push (op
);
2917 else if (op
->op
->type
== operand::OP_PREDICATE
)
2918 others
.safe_push (kids
[i
]);
2922 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2923 others
.safe_push (kids
[i
]);
2924 else if (kids
[i
]->type
== dt_node::DT_MATCH
2925 || kids
[i
]->type
== dt_node::DT_TRUE
)
2927 /* A DT_TRUE operand serves as a barrier - generate code now
2928 for what we have collected sofar.
2929 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2930 dependent matches to get out-of-order. Generate code now
2931 for what we have collected sofar. */
2932 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2933 fns
, generic_fns
, preds
, others
);
2934 /* And output the true operand itself. */
2935 kids
[i
]->gen (f
, indent
, gimple
);
2936 gimple_exprs
.truncate (0);
2937 generic_exprs
.truncate (0);
2939 generic_fns
.truncate (0);
2941 others
.truncate (0);
2947 /* Generate code for the remains. */
2948 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2949 fns
, generic_fns
, preds
, others
);
2952 /* Generate matching code for the children of the decision tree node. */
2955 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2956 vec
<dt_operand
*> gimple_exprs
,
2957 vec
<dt_operand
*> generic_exprs
,
2958 vec
<dt_operand
*> fns
,
2959 vec
<dt_operand
*> generic_fns
,
2960 vec
<dt_operand
*> preds
,
2961 vec
<dt_node
*> others
)
2964 char *kid_opname
= buf
;
2966 unsigned exprs_len
= gimple_exprs
.length ();
2967 unsigned gexprs_len
= generic_exprs
.length ();
2968 unsigned fns_len
= fns
.length ();
2969 unsigned gfns_len
= generic_fns
.length ();
2971 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2974 gimple_exprs
[0]->get_name (kid_opname
);
2976 fns
[0]->get_name (kid_opname
);
2978 generic_fns
[0]->get_name (kid_opname
);
2980 generic_exprs
[0]->get_name (kid_opname
);
2982 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2983 fprintf_indent (f
, indent
, " {\n");
2987 if (exprs_len
|| fns_len
)
2989 fprintf_indent (f
, indent
,
2990 "case SSA_NAME:\n");
2991 fprintf_indent (f
, indent
,
2992 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2994 fprintf_indent (f
, indent
,
2999 fprintf_indent (f
, indent
,
3000 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
3001 fprintf_indent (f
, indent
,
3002 " switch (gimple_assign_rhs_code (def))\n");
3004 fprintf_indent (f
, indent
, "{\n");
3005 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3007 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3008 id_base
*op
= e
->operation
;
3009 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3010 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3012 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3013 fprintf_indent (f
, indent
, " {\n");
3014 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
3015 fprintf_indent (f
, indent
, " break;\n");
3016 fprintf_indent (f
, indent
, " }\n");
3018 fprintf_indent (f
, indent
, "default:;\n");
3019 fprintf_indent (f
, indent
, "}\n");
3025 fprintf_indent (f
, indent
,
3026 "%sif (gcall *def = dyn_cast <gcall *>"
3028 exprs_len
? "else " : "");
3029 fprintf_indent (f
, indent
,
3030 " switch (gimple_call_combined_fn (def))\n");
3033 fprintf_indent (f
, indent
, "{\n");
3034 for (unsigned i
= 0; i
< fns_len
; ++i
)
3036 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3037 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3038 fprintf_indent (f
, indent
, " {\n");
3039 fns
[i
]->gen (f
, indent
+ 4, true);
3040 fprintf_indent (f
, indent
, " break;\n");
3041 fprintf_indent (f
, indent
, " }\n");
3044 fprintf_indent (f
, indent
, "default:;\n");
3045 fprintf_indent (f
, indent
, "}\n");
3050 fprintf_indent (f
, indent
, " }\n");
3051 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3052 here rather than in the next loop. */
3053 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3055 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3056 id_base
*op
= e
->operation
;
3057 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3059 fprintf_indent (f
, indent
+ 4, "{\n");
3060 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
3061 fprintf_indent (f
, indent
+ 4, "}\n");
3065 fprintf_indent (f
, indent
, " break;\n");
3068 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3070 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3071 id_base
*op
= e
->operation
;
3072 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3073 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3074 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3075 /* Already handled above. */
3078 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3079 fprintf_indent (f
, indent
, " {\n");
3080 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
3081 fprintf_indent (f
, indent
, " break;\n");
3082 fprintf_indent (f
, indent
, " }\n");
3087 fprintf_indent (f
, indent
,
3088 "case CALL_EXPR:\n");
3089 fprintf_indent (f
, indent
,
3090 " switch (get_call_combined_fn (%s))\n",
3092 fprintf_indent (f
, indent
,
3096 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3098 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3099 gcc_assert (e
->operation
->kind
== id_base::FN
);
3101 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3102 fprintf_indent (f
, indent
, " {\n");
3103 generic_fns
[j
]->gen (f
, indent
+ 4, false);
3104 fprintf_indent (f
, indent
, " break;\n");
3105 fprintf_indent (f
, indent
, " }\n");
3107 fprintf_indent (f
, indent
, "default:;\n");
3110 fprintf_indent (f
, indent
, " }\n");
3111 fprintf_indent (f
, indent
, " break;\n");
3114 /* Close switch (TREE_CODE ()). */
3115 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3118 fprintf_indent (f
, indent
, " default:;\n");
3119 fprintf_indent (f
, indent
, " }\n");
3122 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3124 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3125 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3126 preds
[i
]->get_name (kid_opname
);
3127 fprintf_indent (f
, indent
, "{\n");
3129 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3130 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3131 gimple
? "gimple" : "tree",
3132 p
->id
, kid_opname
, kid_opname
,
3133 gimple
? ", valueize" : "");
3134 fprintf_indent (f
, indent
, " {\n");
3135 for (int j
= 0; j
< p
->nargs
; ++j
)
3137 char child_opname
[20];
3138 preds
[i
]->gen_opname (child_opname
, j
);
3139 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3140 child_opname
, kid_opname
, j
);
3142 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3145 fprintf_indent (f
, indent
, "}\n");
3148 for (unsigned i
= 0; i
< others
.length (); ++i
)
3149 others
[i
]->gen (f
, indent
, gimple
);
3152 /* Generate matching code for the decision tree operand. */
3155 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3160 unsigned n_braces
= 0;
3162 if (type
== DT_OPERAND
)
3165 case operand::OP_PREDICATE
:
3166 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3169 case operand::OP_EXPR
:
3171 n_braces
= gen_gimple_expr (f
, indent
);
3173 n_braces
= gen_generic_expr (f
, indent
, opname
);
3179 else if (type
== DT_TRUE
)
3181 else if (type
== DT_MATCH
)
3182 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3186 indent
+= 4 * n_braces
;
3187 gen_kids (f
, indent
, gimple
);
3189 for (unsigned i
= 0; i
< n_braces
; ++i
)
3194 fprintf_indent (f
, indent
, " }\n");
3199 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3200 step of a '(simplify ...)' or '(match ...)'. This handles everything
3201 that is not part of the decision tree (simplify->match).
3202 Main recursive worker. */
3205 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3209 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3211 fprintf_indent (f
, indent
, "{\n");
3213 output_line_directive (f
, w
->location
);
3214 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3215 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3217 fprintf_indent (f
, indent
, "}\n");
3220 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3222 output_line_directive (f
, ife
->location
);
3223 fprintf_indent (f
, indent
, "if (");
3224 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3226 fprintf_indent (f
, indent
+ 2, "{\n");
3228 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3230 fprintf_indent (f
, indent
+ 2, "}\n");
3233 fprintf_indent (f
, indent
, "else\n");
3234 fprintf_indent (f
, indent
+ 2, "{\n");
3236 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3238 fprintf_indent (f
, indent
+ 2, "}\n");
3244 /* Analyze captures and perform early-outs on the incoming arguments
3245 that cover cases we cannot handle. */
3246 capture_info
cinfo (s
, result
, gimple
);
3247 if (s
->kind
== simplify::SIMPLIFY
)
3251 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3252 if (cinfo
.force_no_side_effects
& (1 << i
))
3254 fprintf_indent (f
, indent
,
3255 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3258 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3259 "forcing toplevel operand to have no "
3262 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3263 if (cinfo
.info
[i
].cse_p
)
3265 else if (cinfo
.info
[i
].force_no_side_effects_p
3266 && (cinfo
.info
[i
].toplevel_msk
3267 & cinfo
.force_no_side_effects
) == 0)
3269 fprintf_indent (f
, indent
,
3270 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3271 "return NULL_TREE;\n", i
);
3273 warning_at (cinfo
.info
[i
].c
->location
,
3274 "forcing captured operand to have no "
3277 else if ((cinfo
.info
[i
].toplevel_msk
3278 & cinfo
.force_no_side_effects
) != 0)
3279 /* Mark capture as having no side-effects if we had to verify
3280 that via forced toplevel operand checks. */
3281 cinfo
.info
[i
].force_no_side_effects_p
= true;
3285 /* Force single-use restriction by only allowing simple
3286 results via setting seq to NULL. */
3287 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3288 bool first_p
= true;
3289 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3290 if (cinfo
.info
[i
].force_single_use
)
3294 fprintf_indent (f
, indent
, "if (lseq\n");
3295 fprintf_indent (f
, indent
, " && (");
3301 fprintf_indent (f
, indent
, " || ");
3303 fprintf (f
, "!single_use (captures[%d])", i
);
3307 fprintf (f
, "))\n");
3308 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3313 if (s
->kind
== simplify::SIMPLIFY
)
3314 fprintf_indent (f
, indent
, "if (__builtin_expect (!dbg_cnt (match), 0)) return %s;\n",
3315 gimple
? "false" : "NULL_TREE");
3317 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3318 "fprintf (dump_file, \"%s ",
3319 s
->kind
== simplify::SIMPLIFY
3320 ? "Applying pattern" : "Matching expression");
3321 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3322 output_line_directive (f
,
3323 result
? result
->location
: s
->match
->location
, true,
3325 fprintf (f
, ", __FILE__, __LINE__);\n");
3329 /* If there is no result then this is a predicate implementation. */
3330 fprintf_indent (f
, indent
, "return true;\n");
3334 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3335 in outermost position). */
3336 if (result
->type
== operand::OP_EXPR
3337 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3338 result
= as_a
<expr
*> (result
)->ops
[0];
3339 if (result
->type
== operand::OP_EXPR
)
3341 expr
*e
= as_a
<expr
*> (result
);
3342 id_base
*opr
= e
->operation
;
3343 bool is_predicate
= false;
3344 /* When we delay operator substituting during lowering of fors we
3345 make sure that for code-gen purposes the effects of each substitute
3346 are the same. Thus just look at that. */
3347 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3348 opr
= uid
->substitutes
[0];
3349 else if (is_a
<predicate_id
*> (opr
))
3350 is_predicate
= true;
3352 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3353 *e
->operation
== CONVERT_EXPR
3354 ? "NOP_EXPR" : e
->operation
->id
,
3356 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3360 snprintf (dest
, 32, "res_ops[%d]", j
);
3362 snprintf (dest
, 32, "res_op->ops[%d]", j
);
3364 = get_operand_type (opr
, j
,
3365 "type", e
->expr_type
,
3367 : "TREE_TYPE (res_op->ops[0])");
3368 /* We need to expand GENERIC conditions we captured from
3369 COND_EXPRs and we need to unshare them when substituting
3371 int cond_handling
= 0;
3373 cond_handling
= ((*opr
== COND_EXPR
3374 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3375 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3376 &cinfo
, indexes
, cond_handling
);
3379 /* Re-fold the toplevel result. It's basically an embedded
3380 gimple_build w/o actually building the stmt. */
3382 fprintf_indent (f
, indent
,
3383 "gimple_resimplify%d (lseq, res_op,"
3384 " valueize);\n", e
->ops
.length ());
3386 else if (result
->type
== operand::OP_CAPTURE
3387 || result
->type
== operand::OP_C_EXPR
)
3389 fprintf_indent (f
, indent
, "tree tem;\n");
3390 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3392 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3393 if (is_a
<capture
*> (result
)
3394 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3396 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3397 with substituting a capture of that. */
3398 fprintf_indent (f
, indent
,
3399 "if (COMPARISON_CLASS_P (tem))\n");
3400 fprintf_indent (f
, indent
,
3402 fprintf_indent (f
, indent
,
3403 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3404 fprintf_indent (f
, indent
,
3405 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3406 fprintf_indent (f
, indent
,
3412 fprintf_indent (f
, indent
, "return true;\n");
3416 bool is_predicate
= false;
3417 if (result
->type
== operand::OP_EXPR
)
3419 expr
*e
= as_a
<expr
*> (result
);
3420 id_base
*opr
= e
->operation
;
3421 /* When we delay operator substituting during lowering of fors we
3422 make sure that for code-gen purposes the effects of each substitute
3423 are the same. Thus just look at that. */
3424 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3425 opr
= uid
->substitutes
[0];
3426 else if (is_a
<predicate_id
*> (opr
))
3427 is_predicate
= true;
3428 /* Search for captures used multiple times in the result expression
3429 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3430 original expression. */
3432 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3434 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3435 || cinfo
.info
[i
].cse_p
)
3437 if (cinfo
.info
[i
].result_use_count
3438 > cinfo
.info
[i
].match_use_count
)
3439 fprintf_indent (f
, indent
,
3440 "if (! tree_invariant_p (captures[%d])) "
3441 "return NULL_TREE;\n", i
);
3443 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3447 snprintf (dest
, 32, "res_ops[%d]", j
);
3450 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3451 snprintf (dest
, 32, "res_op%d", j
);
3454 = get_operand_type (opr
, j
,
3455 "type", e
->expr_type
,
3457 ? NULL
: "TREE_TYPE (res_op0)");
3458 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3462 fprintf_indent (f
, indent
, "return true;\n");
3465 fprintf_indent (f
, indent
, "tree res;\n");
3466 /* Re-fold the toplevel result. Use non_lvalue to
3467 build NON_LVALUE_EXPRs so they get properly
3468 ignored when in GIMPLE form. */
3469 if (*opr
== NON_LVALUE_EXPR
)
3470 fprintf_indent (f
, indent
,
3471 "res = non_lvalue_loc (loc, res_op0);\n");
3474 if (is_a
<operator_id
*> (opr
))
3475 fprintf_indent (f
, indent
,
3476 "res = fold_build%d_loc (loc, %s, type",
3478 *e
->operation
== CONVERT_EXPR
3479 ? "NOP_EXPR" : e
->operation
->id
);
3481 fprintf_indent (f
, indent
,
3482 "res = maybe_build_call_expr_loc (loc, "
3483 "%s, type, %d", e
->operation
->id
,
3485 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3486 fprintf (f
, ", res_op%d", j
);
3487 fprintf (f
, ");\n");
3488 if (!is_a
<operator_id
*> (opr
))
3490 fprintf_indent (f
, indent
, "if (!res)\n");
3491 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3496 else if (result
->type
== operand::OP_CAPTURE
3497 || result
->type
== operand::OP_C_EXPR
)
3500 fprintf_indent (f
, indent
, "tree res;\n");
3501 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3508 /* Search for captures not used in the result expression and dependent
3509 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3510 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3512 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3514 if (!cinfo
.info
[i
].force_no_side_effects_p
3515 && !cinfo
.info
[i
].expr_p
3516 && cinfo
.info
[i
].result_use_count
== 0)
3518 fprintf_indent (f
, indent
,
3519 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3521 fprintf_indent (f
, indent
+ 2,
3522 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3523 "fold_ignored_result (captures[%d]), res);\n",
3527 fprintf_indent (f
, indent
, "return res;\n");
3532 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3533 step of a '(simplify ...)' or '(match ...)'. This handles everything
3534 that is not part of the decision tree (simplify->match). */
3537 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3539 fprintf_indent (f
, indent
, "{\n");
3541 output_line_directive (f
,
3542 s
->result
? s
->result
->location
: s
->match
->location
);
3543 if (s
->capture_max
>= 0)
3546 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3547 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3549 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3553 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3555 fprintf (f
, " };\n");
3558 /* If we have a split-out function for the actual transform, call it. */
3559 if (info
&& info
->fname
)
3563 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3564 "valueize, type, captures", info
->fname
);
3565 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3566 if (s
->for_subst_vec
[i
].first
->used
)
3567 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3568 fprintf (f
, "))\n");
3569 fprintf_indent (f
, indent
, " return true;\n");
3573 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3575 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3576 fprintf (f
, ", op%d", i
);
3577 fprintf (f
, ", captures");
3578 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3580 if (s
->for_subst_vec
[i
].first
->used
)
3581 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3583 fprintf (f
, ");\n");
3584 fprintf_indent (f
, indent
, "if (res) return res;\n");
3589 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3591 if (! s
->for_subst_vec
[i
].first
->used
)
3593 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3594 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3595 s
->for_subst_vec
[i
].first
->id
,
3596 s
->for_subst_vec
[i
].second
->id
);
3597 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3598 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3599 s
->for_subst_vec
[i
].first
->id
,
3600 s
->for_subst_vec
[i
].second
->id
);
3604 gen_1 (f
, indent
, gimple
, s
->result
);
3608 fprintf_indent (f
, indent
, "}\n");
3612 /* Hash function for finding equivalent transforms. */
3615 sinfo_hashmap_traits::hash (const key_type
&v
)
3617 /* Only bother to compare those originating from the same source pattern. */
3618 return v
->s
->result
->location
;
3621 /* Compare function for finding equivalent transforms. */
3624 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3626 if (o1
->type
!= o2
->type
)
3631 case operand::OP_IF
:
3633 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3634 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3635 /* ??? Properly compare c-exprs. */
3636 if (if1
->cond
!= if2
->cond
)
3638 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3640 if (if1
->falseexpr
!= if2
->falseexpr
3642 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3646 case operand::OP_WITH
:
3648 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3649 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3650 if (with1
->with
!= with2
->with
)
3652 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3657 /* We've hit a result. Time to compare capture-infos - this is required
3658 in addition to the conservative pointer-equivalency of the result IL. */
3659 capture_info
cinfo1 (s1
, o1
, true);
3660 capture_info
cinfo2 (s2
, o2
, true);
3662 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3663 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3666 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3668 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3669 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3670 || (cinfo1
.info
[i
].force_no_side_effects_p
3671 != cinfo2
.info
[i
].force_no_side_effects_p
)
3672 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3673 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3674 /* toplevel_msk is an optimization */
3675 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3676 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3677 /* the pointer back to the capture is for diagnostics only */)
3681 /* ??? Deep-compare the actual result. */
3686 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3687 const key_type
&candidate
)
3689 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3693 /* Main entry to generate code for matching GIMPLE IL off the decision
3697 decision_tree::gen (FILE *f
, bool gimple
)
3703 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3704 "a total number of %u nodes\n",
3705 gimple
? "GIMPLE" : "GENERIC",
3706 root
->num_leafs
, root
->max_level
, root
->total_size
);
3708 /* First split out the transform part of equal leafs. */
3711 for (sinfo_map_t::iterator iter
= si
.begin ();
3712 iter
!= si
.end (); ++iter
)
3714 sinfo
*s
= (*iter
).second
;
3715 /* Do not split out single uses. */
3722 fprintf (stderr
, "found %u uses of", s
->cnt
);
3723 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3726 /* Generate a split out function with the leaf transform code. */
3727 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3730 fprintf (f
, "\nstatic bool\n"
3731 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3732 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3733 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3738 fprintf (f
, "\nstatic tree\n"
3739 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3740 (*iter
).second
->fname
);
3741 for (unsigned i
= 0;
3742 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3743 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3744 fprintf (f
, " tree *captures\n");
3746 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3748 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3750 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3751 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3752 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3753 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3754 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3755 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3758 fprintf (f
, ")\n{\n");
3759 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3761 fprintf (f
, " return false;\n");
3763 fprintf (f
, " return NULL_TREE;\n");
3766 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3768 for (unsigned n
= 1; n
<= 5; ++n
)
3770 /* First generate split-out functions. */
3771 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3773 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3774 expr
*e
= static_cast<expr
*>(dop
->op
);
3775 if (e
->ops
.length () != n
3776 /* Builtin simplifications are somewhat premature on
3777 GENERIC. The following drops patterns with outermost
3778 calls. It's easy to emit overloads for function code
3779 though if necessary. */
3781 && e
->operation
->kind
!= id_base::CODE
))
3785 fprintf (f
, "\nstatic bool\n"
3786 "gimple_simplify_%s (gimple_match_op *res_op,"
3787 " gimple_seq *seq,\n"
3788 " tree (*valueize)(tree) "
3789 "ATTRIBUTE_UNUSED,\n"
3790 " code_helper ARG_UNUSED (code), tree "
3791 "ARG_UNUSED (type)\n",
3794 fprintf (f
, "\nstatic tree\n"
3795 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3796 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3798 for (unsigned i
= 0; i
< n
; ++i
)
3799 fprintf (f
, ", tree op%d", i
);
3802 dop
->gen_kids (f
, 2, gimple
);
3804 fprintf (f
, " return false;\n");
3806 fprintf (f
, " return NULL_TREE;\n");
3810 /* Then generate the main entry with the outermost switch and
3811 tail-calls to the split-out functions. */
3813 fprintf (f
, "\nstatic bool\n"
3814 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3815 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3816 " code_helper code, const tree type");
3818 fprintf (f
, "\ntree\n"
3819 "generic_simplify (location_t loc, enum tree_code code, "
3820 "const tree type ATTRIBUTE_UNUSED");
3821 for (unsigned i
= 0; i
< n
; ++i
)
3822 fprintf (f
, ", tree op%d", i
);
3827 fprintf (f
, " switch (code.get_rep())\n"
3830 fprintf (f
, " switch (code)\n"
3832 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3834 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3835 expr
*e
= static_cast<expr
*>(dop
->op
);
3836 if (e
->ops
.length () != n
3837 /* Builtin simplifications are somewhat premature on
3838 GENERIC. The following drops patterns with outermost
3839 calls. It's easy to emit overloads for function code
3840 though if necessary. */
3842 && e
->operation
->kind
!= id_base::CODE
))
3845 if (*e
->operation
== CONVERT_EXPR
3846 || *e
->operation
== NOP_EXPR
)
3847 fprintf (f
, " CASE_CONVERT:\n");
3849 fprintf (f
, " case %s%s:\n",
3850 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3853 fprintf (f
, " return gimple_simplify_%s (res_op, "
3854 "seq, valueize, code, type", e
->operation
->id
);
3856 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3858 for (unsigned i
= 0; i
< n
; ++i
)
3859 fprintf (f
, ", op%d", i
);
3860 fprintf (f
, ");\n");
3862 fprintf (f
, " default:;\n"
3866 fprintf (f
, " return false;\n");
3868 fprintf (f
, " return NULL_TREE;\n");
3873 /* Output code to implement the predicate P from the decision tree DT. */
3876 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3878 fprintf (f
, "\nbool\n"
3879 "%s%s (tree t%s%s)\n"
3880 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3881 p
->nargs
> 0 ? ", tree *res_ops" : "",
3882 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3883 /* Conveniently make 'type' available. */
3884 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3887 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3888 dt
.root
->gen_kids (f
, 2, gimple
);
3890 fprintf_indent (f
, 2, "return false;\n"
3894 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3897 write_header (FILE *f
, const char *head
)
3899 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3900 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3902 /* Include the header instead of writing it awkwardly quoted here. */
3903 fprintf (f
, "\n#include \"%s\"\n", head
);
3913 parser (cpp_reader
*);
3916 const cpp_token
*next ();
3917 const cpp_token
*peek (unsigned = 1);
3918 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3919 const cpp_token
*expect (enum cpp_ttype
);
3920 const cpp_token
*eat_token (enum cpp_ttype
);
3921 const char *get_string ();
3922 const char *get_ident ();
3923 const cpp_token
*eat_ident (const char *);
3924 const char *get_number ();
3926 unsigned get_internal_capture_id ();
3928 id_base
*parse_operation ();
3929 operand
*parse_capture (operand
*, bool);
3930 operand
*parse_expr ();
3931 c_expr
*parse_c_expr (cpp_ttype
);
3932 operand
*parse_op ();
3934 void record_operlist (location_t
, user_id
*);
3936 void parse_pattern ();
3937 operand
*parse_result (operand
*, predicate_id
*);
3938 void push_simplify (simplify::simplify_kind
,
3939 vec
<simplify
*>&, operand
*, operand
*);
3940 void parse_simplify (simplify::simplify_kind
,
3941 vec
<simplify
*>&, predicate_id
*, operand
*);
3942 void parse_for (location_t
);
3943 void parse_if (location_t
);
3944 void parse_predicates (location_t
);
3945 void parse_operator_list (location_t
);
3947 void finish_match_operand (operand
*);
3950 vec
<c_expr
*> active_ifs
;
3951 vec
<vec
<user_id
*> > active_fors
;
3952 hash_set
<user_id
*> *oper_lists_set
;
3953 vec
<user_id
*> oper_lists
;
3955 cid_map_t
*capture_ids
;
3959 vec
<simplify
*> simplifiers
;
3960 vec
<predicate_id
*> user_predicates
;
3961 bool parsing_match_operand
;
3964 /* Lexing helpers. */
3966 /* Read the next non-whitespace token from R. */
3971 const cpp_token
*token
;
3974 token
= cpp_get_token (r
);
3976 while (token
->type
== CPP_PADDING
);
3980 /* Peek at the next non-whitespace token from R. */
3983 parser::peek (unsigned num
)
3985 const cpp_token
*token
;
3989 token
= cpp_peek_token (r
, i
++);
3991 while (token
->type
== CPP_PADDING
3993 /* If we peek at EOF this is a fatal error as it leaves the
3994 cpp_reader in unusable state. Assume we really wanted a
3995 token and thus this EOF is unexpected. */
3996 if (token
->type
== CPP_EOF
)
3997 fatal_at (token
, "unexpected end of file");
4001 /* Peek at the next identifier token (or return NULL if the next
4002 token is not an identifier or equal to ID if supplied). */
4005 parser::peek_ident (const char *id
, unsigned num
)
4007 const cpp_token
*token
= peek (num
);
4008 if (token
->type
!= CPP_NAME
)
4014 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4015 if (strcmp (id
, t
) == 0)
4021 /* Read the next token from R and assert it is of type TK. */
4024 parser::expect (enum cpp_ttype tk
)
4026 const cpp_token
*token
= next ();
4027 if (token
->type
!= tk
)
4028 fatal_at (token
, "expected %s, got %s",
4029 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4034 /* Consume the next token from R and assert it is of type TK. */
4037 parser::eat_token (enum cpp_ttype tk
)
4042 /* Read the next token from R and assert it is of type CPP_STRING and
4043 return its value. */
4046 parser::get_string ()
4048 const cpp_token
*token
= expect (CPP_STRING
);
4049 return (const char *)token
->val
.str
.text
;
4052 /* Read the next token from R and assert it is of type CPP_NAME and
4053 return its value. */
4056 parser::get_ident ()
4058 const cpp_token
*token
= expect (CPP_NAME
);
4059 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4062 /* Eat an identifier token with value S from R. */
4065 parser::eat_ident (const char *s
)
4067 const cpp_token
*token
= peek ();
4068 const char *t
= get_ident ();
4069 if (strcmp (s
, t
) != 0)
4070 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4074 /* Read the next token from R and assert it is of type CPP_NUMBER and
4075 return its value. */
4078 parser::get_number ()
4080 const cpp_token
*token
= expect (CPP_NUMBER
);
4081 return (const char *)token
->val
.str
.text
;
4084 /* Return a capture ID that can be used internally. */
4087 parser::get_internal_capture_id ()
4089 unsigned newid
= capture_ids
->elements ();
4090 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4093 sprintf (id
, "__%u", newid
);
4094 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4096 fatal ("reserved capture id '%s' already used", id
);
4100 /* Record an operator-list use for transparent for handling. */
4103 parser::record_operlist (location_t loc
, user_id
*p
)
4105 if (!oper_lists_set
->add (p
))
4107 if (!oper_lists
.is_empty ()
4108 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4109 fatal_at (loc
, "User-defined operator list does not have the "
4110 "same number of entries as others used in the pattern");
4111 oper_lists
.safe_push (p
);
4115 /* Parse the operator ID, special-casing convert?, convert1? and
4119 parser::parse_operation ()
4121 const cpp_token
*id_tok
= peek ();
4122 const char *id
= get_ident ();
4123 const cpp_token
*token
= peek ();
4124 if (strcmp (id
, "convert0") == 0)
4125 fatal_at (id_tok
, "use 'convert?' here");
4126 else if (strcmp (id
, "view_convert0") == 0)
4127 fatal_at (id_tok
, "use 'view_convert?' here");
4128 if (token
->type
== CPP_QUERY
4129 && !(token
->flags
& PREV_WHITE
))
4131 if (strcmp (id
, "convert") == 0)
4133 else if (strcmp (id
, "convert1") == 0)
4135 else if (strcmp (id
, "convert2") == 0)
4137 else if (strcmp (id
, "view_convert") == 0)
4138 id
= "view_convert0";
4139 else if (strcmp (id
, "view_convert1") == 0)
4141 else if (strcmp (id
, "view_convert2") == 0)
4144 fatal_at (id_tok
, "non-convert operator conditionalized");
4146 if (!parsing_match_operand
)
4147 fatal_at (id_tok
, "conditional convert can only be used in "
4148 "match expression");
4149 eat_token (CPP_QUERY
);
4151 else if (strcmp (id
, "convert1") == 0
4152 || strcmp (id
, "convert2") == 0
4153 || strcmp (id
, "view_convert1") == 0
4154 || strcmp (id
, "view_convert2") == 0)
4155 fatal_at (id_tok
, "expected '?' after conditional operator");
4156 id_base
*op
= get_operator (id
);
4158 fatal_at (id_tok
, "unknown operator %s", id
);
4160 user_id
*p
= dyn_cast
<user_id
*> (op
);
4161 if (p
&& p
->is_oper_list
)
4163 if (active_fors
.length() == 0)
4164 record_operlist (id_tok
->src_loc
, p
);
4166 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4172 capture = '@'<number> */
4175 parser::parse_capture (operand
*op
, bool require_existing
)
4177 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4178 const cpp_token
*token
= peek ();
4179 const char *id
= NULL
;
4180 bool value_match
= false;
4181 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4182 if (token
->type
== CPP_ATSIGN
4183 && ! (token
->flags
& PREV_WHITE
)
4184 && parsing_match_operand
)
4186 eat_token (CPP_ATSIGN
);
4190 if (token
->type
== CPP_NUMBER
)
4192 else if (token
->type
== CPP_NAME
)
4195 fatal_at (token
, "expected number or identifier");
4196 unsigned next_id
= capture_ids
->elements ();
4198 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4201 if (require_existing
)
4202 fatal_at (src_loc
, "unknown capture id");
4205 return new capture (src_loc
, num
, op
, value_match
);
4208 /* Parse an expression
4209 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4212 parser::parse_expr ()
4214 const cpp_token
*token
= peek ();
4215 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4218 bool is_commutative
= false;
4219 bool force_capture
= false;
4220 const char *expr_type
= NULL
;
4222 if (token
->type
== CPP_COLON
4223 && !(token
->flags
& PREV_WHITE
))
4225 eat_token (CPP_COLON
);
4227 if (token
->type
== CPP_NAME
4228 && !(token
->flags
& PREV_WHITE
))
4230 const char *s
= get_ident ();
4231 if (!parsing_match_operand
)
4241 = dyn_cast
<operator_id
*> (e
->operation
))
4243 if (!commutative_tree_code (p
->code
)
4244 && !comparison_code_p (p
->code
))
4245 fatal_at (token
, "operation is not commutative");
4247 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4248 for (unsigned i
= 0;
4249 i
< p
->substitutes
.length (); ++i
)
4252 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4254 if (!commutative_tree_code (q
->code
)
4255 && !comparison_code_p (q
->code
))
4256 fatal_at (token
, "operation %s is not "
4257 "commutative", q
->id
);
4260 is_commutative
= true;
4262 else if (*sp
== 'C')
4263 is_commutative
= true;
4264 else if (*sp
== 's')
4266 e
->force_single_use
= true;
4267 force_capture
= true;
4270 fatal_at (token
, "flag %c not recognized", *sp
);
4277 fatal_at (token
, "expected flag or type specifying identifier");
4280 if (token
->type
== CPP_ATSIGN
4281 && !(token
->flags
& PREV_WHITE
))
4282 op
= parse_capture (e
, false);
4283 else if (force_capture
)
4285 unsigned num
= get_internal_capture_id ();
4286 op
= new capture (token
->src_loc
, num
, e
, false);
4292 const cpp_token
*token
= peek ();
4293 if (token
->type
== CPP_CLOSE_PAREN
)
4295 if (e
->operation
->nargs
!= -1
4296 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4297 fatal_at (token
, "'%s' expects %u operands, not %u",
4298 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4301 if (e
->ops
.length () == 2
4302 || commutative_op (e
->operation
) >= 0)
4303 e
->is_commutative
= true;
4305 fatal_at (token
, "only binary operators or functions with "
4306 "two arguments can be marked commutative, "
4307 "unless the operation is known to be inherently "
4310 e
->expr_type
= expr_type
;
4313 else if (!(token
->flags
& PREV_WHITE
))
4314 fatal_at (token
, "expected expression operand");
4316 e
->append_op (parse_op ());
4321 /* Lex native C code delimited by START recording the preprocessing tokens
4322 for later processing.
4323 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4326 parser::parse_c_expr (cpp_ttype start
)
4328 const cpp_token
*token
;
4331 vec
<cpp_token
> code
= vNULL
;
4332 unsigned nr_stmts
= 0;
4333 location_t loc
= eat_token (start
)->src_loc
;
4334 if (start
== CPP_OPEN_PAREN
)
4335 end
= CPP_CLOSE_PAREN
;
4336 else if (start
== CPP_OPEN_BRACE
)
4337 end
= CPP_CLOSE_BRACE
;
4345 /* Count brace pairs to find the end of the expr to match. */
4346 if (token
->type
== start
)
4348 else if (token
->type
== end
4351 else if (token
->type
== CPP_EOF
)
4352 fatal_at (token
, "unexpected end of file");
4354 /* This is a lame way of counting the number of statements. */
4355 if (token
->type
== CPP_SEMICOLON
)
4358 /* If this is possibly a user-defined identifier mark it used. */
4359 if (token
->type
== CPP_NAME
)
4361 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4362 (token
->val
.node
.node
)->ident
.str
);
4364 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4365 record_operlist (token
->src_loc
, p
);
4368 /* Record the token. */
4369 code
.safe_push (*token
);
4372 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4375 /* Parse an operand which is either an expression, a predicate or
4376 a standalone capture.
4377 op = predicate | expr | c_expr | capture */
4382 const cpp_token
*token
= peek ();
4383 struct operand
*op
= NULL
;
4384 if (token
->type
== CPP_OPEN_PAREN
)
4386 eat_token (CPP_OPEN_PAREN
);
4388 eat_token (CPP_CLOSE_PAREN
);
4390 else if (token
->type
== CPP_OPEN_BRACE
)
4392 op
= parse_c_expr (CPP_OPEN_BRACE
);
4396 /* Remaining ops are either empty or predicates */
4397 if (token
->type
== CPP_NAME
)
4399 const char *id
= get_ident ();
4400 id_base
*opr
= get_operator (id
);
4402 fatal_at (token
, "expected predicate name");
4403 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4405 if (code
->nargs
!= 0)
4406 fatal_at (token
, "using an operator with operands as predicate");
4407 /* Parse the zero-operand operator "predicates" as
4409 op
= new expr (opr
, token
->src_loc
);
4411 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4413 if (code
->nargs
!= 0)
4414 fatal_at (token
, "using an operator with operands as predicate");
4415 /* Parse the zero-operand operator "predicates" as
4417 op
= new expr (opr
, token
->src_loc
);
4419 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4420 op
= new predicate (p
, token
->src_loc
);
4422 fatal_at (token
, "using an unsupported operator as predicate");
4423 if (!parsing_match_operand
)
4424 fatal_at (token
, "predicates are only allowed in match expression");
4426 if (token
->flags
& PREV_WHITE
)
4429 else if (token
->type
!= CPP_COLON
4430 && token
->type
!= CPP_ATSIGN
)
4431 fatal_at (token
, "expected expression or predicate");
4432 /* optionally followed by a capture and a predicate. */
4433 if (token
->type
== CPP_COLON
)
4434 fatal_at (token
, "not implemented: predicate on leaf operand");
4435 if (token
->type
== CPP_ATSIGN
)
4436 op
= parse_capture (op
, !parsing_match_operand
);
4442 /* Create a new simplify from the current parsing state and MATCH,
4443 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4446 parser::push_simplify (simplify::simplify_kind kind
,
4447 vec
<simplify
*>& simplifiers
,
4448 operand
*match
, operand
*result
)
4450 /* Build and push a temporary for operator list uses in expressions. */
4451 if (!oper_lists
.is_empty ())
4452 active_fors
.safe_push (oper_lists
);
4454 simplifiers
.safe_push
4455 (new simplify (kind
, last_id
++, match
, result
,
4456 active_fors
.copy (), capture_ids
));
4458 if (!oper_lists
.is_empty ())
4463 <result-op> = <op> | <if> | <with>
4464 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4465 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4469 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4471 const cpp_token
*token
= peek ();
4472 if (token
->type
!= CPP_OPEN_PAREN
)
4475 eat_token (CPP_OPEN_PAREN
);
4476 if (peek_ident ("if"))
4479 if_expr
*ife
= new if_expr (token
->src_loc
);
4480 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4481 if (peek ()->type
== CPP_OPEN_PAREN
)
4483 ife
->trueexpr
= parse_result (result
, matcher
);
4484 if (peek ()->type
== CPP_OPEN_PAREN
)
4485 ife
->falseexpr
= parse_result (result
, matcher
);
4486 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4487 ife
->falseexpr
= parse_op ();
4489 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4491 ife
->trueexpr
= parse_op ();
4492 if (peek ()->type
== CPP_OPEN_PAREN
)
4493 ife
->falseexpr
= parse_result (result
, matcher
);
4494 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4495 ife
->falseexpr
= parse_op ();
4497 /* If this if is immediately closed then it contains a
4498 manual matcher or is part of a predicate definition. */
4499 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4502 fatal_at (peek (), "manual transform not implemented");
4503 ife
->trueexpr
= result
;
4505 eat_token (CPP_CLOSE_PAREN
);
4508 else if (peek_ident ("with"))
4511 with_expr
*withe
= new with_expr (token
->src_loc
);
4512 /* Parse (with c-expr expr) as (if-with (true) expr). */
4513 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4514 withe
->with
->nr_stmts
= 0;
4515 withe
->subexpr
= parse_result (result
, matcher
);
4516 eat_token (CPP_CLOSE_PAREN
);
4519 else if (peek_ident ("switch"))
4521 token
= eat_ident ("switch");
4522 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4524 if_expr
*ife
= new if_expr (ifloc
);
4526 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4527 if (peek ()->type
== CPP_OPEN_PAREN
)
4528 ife
->trueexpr
= parse_result (result
, matcher
);
4530 ife
->trueexpr
= parse_op ();
4531 eat_token (CPP_CLOSE_PAREN
);
4532 if (peek ()->type
!= CPP_OPEN_PAREN
4533 || !peek_ident ("if", 2))
4534 fatal_at (token
, "switch can be implemented with a single if");
4535 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4537 if (peek ()->type
== CPP_OPEN_PAREN
)
4539 if (peek_ident ("if", 2))
4541 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4543 ife
->falseexpr
= new if_expr (ifloc
);
4544 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4545 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4546 if (peek ()->type
== CPP_OPEN_PAREN
)
4547 ife
->trueexpr
= parse_result (result
, matcher
);
4549 ife
->trueexpr
= parse_op ();
4550 eat_token (CPP_CLOSE_PAREN
);
4554 /* switch default clause */
4555 ife
->falseexpr
= parse_result (result
, matcher
);
4556 eat_token (CPP_CLOSE_PAREN
);
4562 /* switch default clause */
4563 ife
->falseexpr
= parse_op ();
4564 eat_token (CPP_CLOSE_PAREN
);
4568 eat_token (CPP_CLOSE_PAREN
);
4573 operand
*op
= result
;
4576 eat_token (CPP_CLOSE_PAREN
);
4582 simplify = 'simplify' <expr> <result-op>
4584 match = 'match' <ident> <expr> [<result-op>]
4585 and fill SIMPLIFIERS with the results. */
4588 parser::parse_simplify (simplify::simplify_kind kind
,
4589 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4592 /* Reset the capture map. */
4594 capture_ids
= new cid_map_t
;
4595 /* Reset oper_lists and set. */
4596 hash_set
<user_id
*> olist
;
4597 oper_lists_set
= &olist
;
4600 const cpp_token
*loc
= peek ();
4601 parsing_match_operand
= true;
4602 struct operand
*match
= parse_op ();
4603 finish_match_operand (match
);
4604 parsing_match_operand
= false;
4605 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4606 fatal_at (loc
, "outermost expression cannot be captured");
4607 if (match
->type
== operand::OP_EXPR
4608 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4609 fatal_at (loc
, "outermost expression cannot be a predicate");
4611 /* Splice active_ifs onto result and continue parsing the
4613 if_expr
*active_if
= NULL
;
4614 for (int i
= active_ifs
.length (); i
> 0; --i
)
4616 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4617 ifc
->cond
= active_ifs
[i
-1];
4618 ifc
->trueexpr
= active_if
;
4621 if_expr
*outermost_if
= active_if
;
4622 while (active_if
&& active_if
->trueexpr
)
4623 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4625 const cpp_token
*token
= peek ();
4627 /* If this if is immediately closed then it is part of a predicate
4628 definition. Push it. */
4629 if (token
->type
== CPP_CLOSE_PAREN
)
4632 fatal_at (token
, "expected transform expression");
4635 active_if
->trueexpr
= result
;
4636 result
= outermost_if
;
4638 push_simplify (kind
, simplifiers
, match
, result
);
4642 operand
*tem
= parse_result (result
, matcher
);
4645 active_if
->trueexpr
= tem
;
4646 result
= outermost_if
;
4651 push_simplify (kind
, simplifiers
, match
, result
);
4654 /* Parsing of the outer control structures. */
4656 /* Parse a for expression
4657 for = '(' 'for' <subst>... <pattern> ')'
4658 subst = <ident> '(' <ident>... ')' */
4661 parser::parse_for (location_t
)
4663 auto_vec
<const cpp_token
*> user_id_tokens
;
4664 vec
<user_id
*> user_ids
= vNULL
;
4665 const cpp_token
*token
;
4666 unsigned min_n_opers
= 0, max_n_opers
= 0;
4671 if (token
->type
!= CPP_NAME
)
4674 /* Insert the user defined operators into the operator hash. */
4675 const char *id
= get_ident ();
4676 if (get_operator (id
, true) != NULL
)
4677 fatal_at (token
, "operator already defined");
4678 user_id
*op
= new user_id (id
);
4679 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4681 user_ids
.safe_push (op
);
4682 user_id_tokens
.safe_push (token
);
4684 eat_token (CPP_OPEN_PAREN
);
4687 while ((token
= peek_ident ()) != 0)
4689 const char *oper
= get_ident ();
4690 id_base
*idb
= get_operator (oper
, true);
4692 fatal_at (token
, "no such operator '%s'", oper
);
4693 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4694 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4695 || *idb
== VIEW_CONVERT2
)
4696 fatal_at (token
, "conditional operators cannot be used inside for");
4700 else if (idb
->nargs
== -1)
4702 else if (idb
->nargs
!= arity
)
4703 fatal_at (token
, "operator '%s' with arity %d does not match "
4704 "others with arity %d", oper
, idb
->nargs
, arity
);
4706 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4709 if (p
->is_oper_list
)
4710 op
->substitutes
.safe_splice (p
->substitutes
);
4712 fatal_at (token
, "iterator cannot be used as operator-list");
4715 op
->substitutes
.safe_push (idb
);
4718 token
= expect (CPP_CLOSE_PAREN
);
4720 unsigned nsubstitutes
= op
->substitutes
.length ();
4721 if (nsubstitutes
== 0)
4722 fatal_at (token
, "A user-defined operator must have at least "
4723 "one substitution");
4724 if (max_n_opers
== 0)
4726 min_n_opers
= nsubstitutes
;
4727 max_n_opers
= nsubstitutes
;
4731 if (nsubstitutes
% min_n_opers
!= 0
4732 && min_n_opers
% nsubstitutes
!= 0)
4733 fatal_at (token
, "All user-defined identifiers must have a "
4734 "multiple number of operator substitutions of the "
4735 "smallest number of substitutions");
4736 if (nsubstitutes
< min_n_opers
)
4737 min_n_opers
= nsubstitutes
;
4738 else if (nsubstitutes
> max_n_opers
)
4739 max_n_opers
= nsubstitutes
;
4743 unsigned n_ids
= user_ids
.length ();
4745 fatal_at (token
, "for requires at least one user-defined identifier");
4748 if (token
->type
== CPP_CLOSE_PAREN
)
4749 fatal_at (token
, "no pattern defined in for");
4751 active_fors
.safe_push (user_ids
);
4755 if (token
->type
== CPP_CLOSE_PAREN
)
4761 /* Remove user-defined operators from the hash again. */
4762 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4764 if (!user_ids
[i
]->used
)
4765 warning_at (user_id_tokens
[i
],
4766 "operator %s defined but not used", user_ids
[i
]->id
);
4767 operators
->remove_elt (user_ids
[i
]);
4771 /* Parse an identifier associated with a list of operators.
4772 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4775 parser::parse_operator_list (location_t
)
4777 const cpp_token
*token
= peek ();
4778 const char *id
= get_ident ();
4780 if (get_operator (id
, true) != 0)
4781 fatal_at (token
, "operator %s already defined", id
);
4783 user_id
*op
= new user_id (id
, true);
4786 while ((token
= peek_ident ()) != 0)
4789 const char *oper
= get_ident ();
4790 id_base
*idb
= get_operator (oper
, true);
4793 fatal_at (token
, "no such operator '%s'", oper
);
4797 else if (idb
->nargs
== -1)
4799 else if (arity
!= idb
->nargs
)
4800 fatal_at (token
, "operator '%s' with arity %d does not match "
4801 "others with arity %d", oper
, idb
->nargs
, arity
);
4803 /* We allow composition of multiple operator lists. */
4804 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4805 op
->substitutes
.safe_splice (p
->substitutes
);
4807 op
->substitutes
.safe_push (idb
);
4810 // Check that there is no junk after id-list
4812 if (token
->type
!= CPP_CLOSE_PAREN
)
4813 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4815 if (op
->substitutes
.length () == 0)
4816 fatal_at (token
, "operator-list cannot be empty");
4819 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4823 /* Parse an outer if expression.
4824 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4827 parser::parse_if (location_t
)
4829 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4831 const cpp_token
*token
= peek ();
4832 if (token
->type
== CPP_CLOSE_PAREN
)
4833 fatal_at (token
, "no pattern defined in if");
4835 active_ifs
.safe_push (ifexpr
);
4838 const cpp_token
*token
= peek ();
4839 if (token
->type
== CPP_CLOSE_PAREN
)
4847 /* Parse a list of predefined predicate identifiers.
4848 preds = '(' 'define_predicates' <ident>... ')' */
4851 parser::parse_predicates (location_t
)
4855 const cpp_token
*token
= peek ();
4856 if (token
->type
!= CPP_NAME
)
4859 add_predicate (get_ident ());
4864 /* Parse outer control structures.
4865 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4868 parser::parse_pattern ()
4870 /* All clauses start with '('. */
4871 eat_token (CPP_OPEN_PAREN
);
4872 const cpp_token
*token
= peek ();
4873 const char *id
= get_ident ();
4874 if (strcmp (id
, "simplify") == 0)
4876 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4879 else if (strcmp (id
, "match") == 0)
4881 bool with_args
= false;
4882 location_t e_loc
= peek ()->src_loc
;
4883 if (peek ()->type
== CPP_OPEN_PAREN
)
4885 eat_token (CPP_OPEN_PAREN
);
4888 const char *name
= get_ident ();
4889 id_base
*id
= get_operator (name
);
4893 p
= add_predicate (name
);
4894 user_predicates
.safe_push (p
);
4896 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4899 fatal_at (token
, "cannot add a match to a non-predicate ID");
4900 /* Parse (match <id> <arg>... (match-expr)) here. */
4904 capture_ids
= new cid_map_t
;
4905 e
= new expr (p
, e_loc
);
4906 while (peek ()->type
== CPP_ATSIGN
)
4907 e
->append_op (parse_capture (NULL
, false));
4908 eat_token (CPP_CLOSE_PAREN
);
4911 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4912 || (!e
&& p
->nargs
!= 0)))
4913 fatal_at (token
, "non-matching number of match operands");
4914 p
->nargs
= e
? e
->ops
.length () : 0;
4915 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4918 else if (strcmp (id
, "for") == 0)
4919 parse_for (token
->src_loc
);
4920 else if (strcmp (id
, "if") == 0)
4921 parse_if (token
->src_loc
);
4922 else if (strcmp (id
, "define_predicates") == 0)
4924 if (active_ifs
.length () > 0
4925 || active_fors
.length () > 0)
4926 fatal_at (token
, "define_predicates inside if or for is not supported");
4927 parse_predicates (token
->src_loc
);
4929 else if (strcmp (id
, "define_operator_list") == 0)
4931 if (active_ifs
.length () > 0
4932 || active_fors
.length () > 0)
4933 fatal_at (token
, "operator-list inside if or for is not supported");
4934 parse_operator_list (token
->src_loc
);
4937 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4938 active_ifs
.length () == 0 && active_fors
.length () == 0
4939 ? "'define_predicates', " : "");
4941 eat_token (CPP_CLOSE_PAREN
);
4944 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4948 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4953 if (capture
*c
= dyn_cast
<capture
*> (op
))
4955 cpts
[c
->where
].safe_push (c
);
4956 walk_captures (c
->what
, cpts
);
4958 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4959 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4960 walk_captures (e
->ops
[i
], cpts
);
4963 /* Finish up OP which is a match operand. */
4966 parser::finish_match_operand (operand
*op
)
4968 /* Look for matching captures, diagnose mis-uses of @@ and apply
4969 early lowering and distribution of value_match. */
4970 auto_vec
<vec
<capture
*> > cpts
;
4971 cpts
.safe_grow_cleared (capture_ids
->elements ());
4972 walk_captures (op
, cpts
);
4973 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4975 capture
*value_match
= NULL
;
4976 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4978 if (cpts
[i
][j
]->value_match
)
4981 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4982 value_match
= cpts
[i
][j
];
4985 if (cpts
[i
].length () == 1 && value_match
)
4986 fatal_at (value_match
->location
, "@@ without a matching capture");
4989 /* Duplicate prevailing capture with the existing ID, create
4990 a fake ID and rewrite all captures to use it. This turns
4991 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4992 value_match
->what
= new capture (value_match
->location
,
4994 value_match
->what
, false);
4995 /* Create a fake ID and rewrite all captures to use it. */
4996 unsigned newid
= get_internal_capture_id ();
4997 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4999 cpts
[i
][j
]->where
= newid
;
5000 cpts
[i
][j
]->value_match
= true;
5007 /* Main entry of the parser. Repeatedly parse outer control structures. */
5009 parser::parser (cpp_reader
*r_
)
5013 active_fors
= vNULL
;
5014 simplifiers
= vNULL
;
5015 oper_lists_set
= NULL
;
5018 user_predicates
= vNULL
;
5019 parsing_match_operand
= false;
5022 const cpp_token
*token
= next ();
5023 while (token
->type
!= CPP_EOF
)
5025 _cpp_backup_tokens (r
, 1);
5032 /* Helper for the linemap code. */
5035 round_alloc_size (size_t s
)
5041 /* The genmatch generator progam. It reads from a pattern description
5042 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5045 main (int argc
, char **argv
)
5049 progname
= "genmatch";
5055 char *input
= argv
[argc
-1];
5056 for (int i
= 1; i
< argc
- 1; ++i
)
5058 if (strcmp (argv
[i
], "--gimple") == 0)
5060 else if (strcmp (argv
[i
], "--generic") == 0)
5062 else if (strcmp (argv
[i
], "-v") == 0)
5064 else if (strcmp (argv
[i
], "-vv") == 0)
5068 fprintf (stderr
, "Usage: genmatch "
5069 "[--gimple] [--generic] [-v[v]] input\n");
5074 line_table
= XCNEW (struct line_maps
);
5075 linemap_init (line_table
, 0);
5076 line_table
->reallocator
= xrealloc
;
5077 line_table
->round_alloc_size
= round_alloc_size
;
5079 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5080 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5081 cb
->diagnostic
= diagnostic_cb
;
5083 /* Add the build directory to the #include "" search path. */
5084 cpp_dir
*dir
= XCNEW (cpp_dir
);
5085 dir
->name
= getpwd ();
5087 dir
->name
= ASTRDUP (".");
5088 cpp_set_include_chains (r
, dir
, NULL
, false);
5090 if (!cpp_read_main_file (r
, input
))
5092 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5093 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5095 null_id
= new id_base (id_base::NULL_ID
, "null");
5097 /* Pre-seed operators. */
5098 operators
= new hash_table
<id_base
> (1024);
5099 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5100 add_operator (SYM, # SYM, # TYPE, NARGS);
5101 #define END_OF_BASE_TREE_CODES
5103 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5104 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5105 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5106 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5107 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5108 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5109 #undef END_OF_BASE_TREE_CODES
5112 /* Pre-seed builtin functions.
5113 ??? Cannot use N (name) as that is targetm.emultls.get_address
5114 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5115 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5116 add_function (ENUM, "CFN_" # ENUM);
5117 #include "builtins.def"
5119 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5120 add_function (IFN_##CODE, "CFN_" #CODE);
5121 #include "internal-fn.def"
5127 write_header (stdout
, "gimple-match-head.c");
5129 write_header (stdout
, "generic-match-head.c");
5131 /* Go over all predicates defined with patterns and perform
5132 lowering and code generation. */
5133 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5135 predicate_id
*pred
= p
.user_predicates
[i
];
5136 lower (pred
->matchers
, gimple
);
5139 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5140 print_matches (pred
->matchers
[i
]);
5143 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5144 dt
.insert (pred
->matchers
[i
], i
);
5149 write_predicate (stdout
, pred
, dt
, gimple
);
5152 /* Lower the main simplifiers and generate code for them. */
5153 lower (p
.simplifiers
, gimple
);
5156 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5157 print_matches (p
.simplifiers
[i
]);
5160 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5161 dt
.insert (p
.simplifiers
[i
], i
);
5166 dt
.gen (stdout
, gimple
);
5169 cpp_finish (r
, NULL
);