1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2017 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static struct line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 source_location instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (source_location loc
)
66 const struct line_map_ordinary
*map
;
67 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
68 return linemap_expand_location (line_table
, map
, loc
);
72 #if GCC_VERSION >= 4001
73 __attribute__((format (printf
, 5, 0)))
75 error_cb (cpp_reader
*, int errtype
, int, rich_location
*richloc
,
76 const char *msg
, va_list *ap
)
78 const line_map_ordinary
*map
;
79 source_location location
= richloc
->get_loc ();
80 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
81 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
82 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
83 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
84 vfprintf (stderr
, msg
, *ap
);
85 fprintf (stderr
, "\n");
86 FILE *f
= fopen (loc
.file
, "r");
92 if (!fgets (buf
, 128, f
))
94 if (buf
[strlen (buf
) - 1] != '\n')
101 fprintf (stderr
, "%s", buf
);
102 for (int i
= 0; i
< loc
.column
- 1; ++i
)
105 fputc ('\n', stderr
);
110 if (errtype
== CPP_DL_FATAL
)
116 #if GCC_VERSION >= 4001
117 __attribute__((format (printf
, 2, 3)))
119 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
121 rich_location
richloc (line_table
, tk
->src_loc
);
124 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
129 #if GCC_VERSION >= 4001
130 __attribute__((format (printf
, 2, 3)))
132 fatal_at (source_location loc
, const char *msg
, ...)
134 rich_location
richloc (line_table
, loc
);
137 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
142 #if GCC_VERSION >= 4001
143 __attribute__((format (printf
, 2, 3)))
145 warning_at (const cpp_token
*tk
, const char *msg
, ...)
147 rich_location
richloc (line_table
, tk
->src_loc
);
150 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
155 #if GCC_VERSION >= 4001
156 __attribute__((format (printf
, 2, 3)))
158 warning_at (source_location loc
, const char *msg
, ...)
160 rich_location
richloc (line_table
, loc
);
163 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
167 /* Like fprintf, but print INDENT spaces at the beginning. */
170 #if GCC_VERSION >= 4001
171 __attribute__((format (printf
, 3, 4)))
173 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
176 for (; indent
>= 8; indent
-= 8)
178 fprintf (f
, "%*s", indent
, "");
179 va_start (ap
, format
);
180 vfprintf (f
, format
, ap
);
185 output_line_directive (FILE *f
, source_location location
,
186 bool dumpfile
= false)
188 const line_map_ordinary
*map
;
189 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
190 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
193 /* When writing to a dumpfile only dump the filename. */
194 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
195 #if defined(DIR_SEPARATOR_2)
196 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
197 if (pos2
&& (!file
|| (pos2
> file
)))
204 fprintf (f
, "%s:%d", file
, loc
.line
);
207 /* Other gen programs really output line directives here, at least for
208 development it's right now more convenient to have line information
209 from the generated file. Still keep the directives as comment for now
210 to easily back-point to the meta-description. */
211 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
215 /* Pull in tree codes and builtin function codes from their
218 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
231 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
232 enum built_in_function
{
233 #include "builtins.def"
237 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239 #include "internal-fn.def"
243 /* Return true if CODE represents a commutative tree code. Otherwise
246 commutative_tree_code (enum tree_code code
)
252 case MULT_HIGHPART_EXPR
:
267 case WIDEN_MULT_EXPR
:
268 case VEC_WIDEN_MULT_HI_EXPR
:
269 case VEC_WIDEN_MULT_LO_EXPR
:
270 case VEC_WIDEN_MULT_EVEN_EXPR
:
271 case VEC_WIDEN_MULT_ODD_EXPR
:
280 /* Return true if CODE represents a ternary tree code for which the
281 first two operands are commutative. Otherwise return false. */
283 commutative_ternary_tree_code (enum tree_code code
)
287 case WIDEN_MULT_PLUS_EXPR
:
288 case WIDEN_MULT_MINUS_EXPR
:
299 /* Return true if CODE is a comparison. */
302 comparison_code_p (enum tree_code code
)
329 /* Base class for all identifiers the parser knows. */
331 struct id_base
: nofree_ptr_hash
<id_base
>
333 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
335 id_base (id_kind
, const char *, int = -1);
341 /* hash_table support. */
342 static inline hashval_t
hash (const id_base
*);
343 static inline int equal (const id_base
*, const id_base
*);
347 id_base::hash (const id_base
*op
)
353 id_base::equal (const id_base
*op1
,
356 return (op1
->hashval
== op2
->hashval
357 && strcmp (op1
->id
, op2
->id
) == 0);
360 /* The special id "null", which matches nothing. */
361 static id_base
*null_id
;
363 /* Hashtable of known pattern operators. This is pre-seeded from
364 all known tree codes and all known builtin function ids. */
365 static hash_table
<id_base
> *operators
;
367 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
372 hashval
= htab_hash_string (id
);
375 /* Identifier that maps to a tree code. */
377 struct operator_id
: public id_base
379 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
381 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
386 /* Identifier that maps to a builtin or internal function code. */
388 struct fn_id
: public id_base
390 fn_id (enum built_in_function fn_
, const char *id_
)
391 : id_base (id_base::FN
, id_
), fn (fn_
) {}
392 fn_id (enum internal_fn fn_
, const char *id_
)
393 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
399 /* Identifier that maps to a user-defined predicate. */
401 struct predicate_id
: public id_base
403 predicate_id (const char *id_
)
404 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
405 vec
<simplify
*> matchers
;
408 /* Identifier that maps to a operator defined by a 'for' directive. */
410 struct user_id
: public id_base
412 user_id (const char *id_
, bool is_oper_list_
= false)
413 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
414 used (false), is_oper_list (is_oper_list_
) {}
415 vec
<id_base
*> substitutes
;
423 is_a_helper
<fn_id
*>::test (id_base
*id
)
425 return id
->kind
== id_base::FN
;
431 is_a_helper
<operator_id
*>::test (id_base
*id
)
433 return id
->kind
== id_base::CODE
;
439 is_a_helper
<predicate_id
*>::test (id_base
*id
)
441 return id
->kind
== id_base::PREDICATE
;
447 is_a_helper
<user_id
*>::test (id_base
*id
)
449 return id
->kind
== id_base::USER
;
452 /* Add a predicate identifier to the hash. */
454 static predicate_id
*
455 add_predicate (const char *id
)
457 predicate_id
*p
= new predicate_id (id
);
458 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
460 fatal ("duplicate id definition");
465 /* Add a tree code identifier to the hash. */
468 add_operator (enum tree_code code
, const char *id
,
469 const char *tcc
, unsigned nargs
)
471 if (strcmp (tcc
, "tcc_unary") != 0
472 && strcmp (tcc
, "tcc_binary") != 0
473 && strcmp (tcc
, "tcc_comparison") != 0
474 && strcmp (tcc
, "tcc_expression") != 0
475 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
476 && strcmp (tcc
, "tcc_reference") != 0
477 /* To have INTEGER_CST and friends as "predicate operators". */
478 && strcmp (tcc
, "tcc_constant") != 0
479 /* And allow CONSTRUCTOR for vector initializers. */
480 && !(code
== CONSTRUCTOR
)
481 /* Allow SSA_NAME as predicate operator. */
482 && !(code
== SSA_NAME
))
484 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
485 if (code
== ADDR_EXPR
)
487 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
488 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
490 fatal ("duplicate id definition");
494 /* Add a built-in or internal function identifier to the hash. ID is
495 the name of its CFN_* enumeration value. */
497 template <typename T
>
499 add_function (T code
, const char *id
)
501 fn_id
*fn
= new fn_id (code
, id
);
502 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
504 fatal ("duplicate id definition");
508 /* Helper for easy comparing ID with tree code CODE. */
511 operator==(id_base
&id
, enum tree_code code
)
513 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
514 return oid
->code
== code
;
518 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
521 get_operator (const char *id
, bool allow_null
= false)
523 if (allow_null
&& strcmp (id
, "null") == 0)
526 id_base
tem (id_base::CODE
, id
);
528 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
531 /* If this is a user-defined identifier track whether it was used. */
532 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
538 bool all_upper
= true;
539 bool all_lower
= true;
540 for (unsigned int i
= 0; id
[i
]; ++i
)
543 else if (ISLOWER (id
[i
]))
547 /* Try in caps with _EXPR appended. */
548 id2
= ACONCAT ((id
, "_EXPR", NULL
));
549 for (unsigned int i
= 0; id2
[i
]; ++i
)
550 id2
[i
] = TOUPPER (id2
[i
]);
552 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
553 /* Try CFN_ instead of IFN_. */
554 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
555 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
556 /* Try prepending CFN_. */
557 id2
= ACONCAT (("CFN_", id
, NULL
));
561 new (&tem
) id_base (id_base::CODE
, id2
);
562 return operators
->find_with_hash (&tem
, tem
.hashval
);
565 /* Return the comparison operators that results if the operands are
566 swapped. This is safe for floating-point. */
569 swap_tree_comparison (operator_id
*p
)
581 return get_operator ("LT_EXPR");
583 return get_operator ("LE_EXPR");
585 return get_operator ("GT_EXPR");
587 return get_operator ("GE_EXPR");
589 return get_operator ("UNLT_EXPR");
591 return get_operator ("UNLE_EXPR");
593 return get_operator ("UNGT_EXPR");
595 return get_operator ("UNGE_EXPR");
601 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
604 /* The AST produced by parsing of the pattern definitions. */
609 /* The base class for operands. */
612 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
613 operand (enum op_type type_
, source_location loc_
)
614 : type (type_
), location (loc_
) {}
616 source_location location
;
617 virtual void gen_transform (FILE *, int, const char *, bool, int,
618 const char *, capture_info
*,
621 { gcc_unreachable (); }
624 /* A predicate operand. Predicates are leafs in the AST. */
626 struct predicate
: public operand
628 predicate (predicate_id
*p_
, source_location loc
)
629 : operand (OP_PREDICATE
, loc
), p (p_
) {}
633 /* An operand that constitutes an expression. Expressions include
634 function calls and user-defined predicate invocations. */
636 struct expr
: public operand
638 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
639 : operand (OP_EXPR
, loc
), operation (operation_
),
640 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
641 is_generic (false), force_single_use (false) {}
643 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
644 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
645 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
646 void append_op (operand
*op
) { ops
.safe_push (op
); }
647 /* The operator and its operands. */
650 /* An explicitely specified type - used exclusively for conversions. */
651 const char *expr_type
;
652 /* Whether the operation is to be applied commutatively. This is
653 later lowered to two separate patterns. */
655 /* Whether the expression is expected to be in GENERIC form. */
657 /* Whether pushing any stmt to the sequence should be conditional
658 on this expression having a single-use. */
659 bool force_single_use
;
660 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
661 const char *, capture_info
*,
662 dt_operand
** = 0, int = 0);
665 /* An operator that is represented by native C code. This is always
666 a leaf operand in the AST. This class is also used to represent
667 the code to be generated for 'if' and 'with' expressions. */
669 struct c_expr
: public operand
671 /* A mapping of an identifier and its replacement. Used to apply
676 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
679 c_expr (cpp_reader
*r_
, source_location loc
,
680 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
681 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
682 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
683 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
684 /* cpplib tokens and state to transform this back to source. */
687 cid_map_t
*capture_ids
;
688 /* The number of statements parsed (well, the number of ';'s). */
690 /* The identifier replacement vector. */
692 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
693 const char *, capture_info
*,
694 dt_operand
** = 0, int = 0);
697 /* A wrapper around another operand that captures its value. */
699 struct capture
: public operand
701 capture (source_location loc
, unsigned where_
, operand
*what_
, bool value_
)
702 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
704 /* Identifier index for the value. */
706 /* Whether in a match of two operands the compare should be for
707 equal values rather than equal atoms (boils down to a type
710 /* The captured value. */
712 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
713 const char *, capture_info
*,
714 dt_operand
** = 0, int = 0);
719 struct if_expr
: public operand
721 if_expr (source_location loc
)
722 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
728 /* with expression. */
730 struct with_expr
: public operand
732 with_expr (source_location loc
)
733 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
741 is_a_helper
<capture
*>::test (operand
*op
)
743 return op
->type
== operand::OP_CAPTURE
;
749 is_a_helper
<predicate
*>::test (operand
*op
)
751 return op
->type
== operand::OP_PREDICATE
;
757 is_a_helper
<c_expr
*>::test (operand
*op
)
759 return op
->type
== operand::OP_C_EXPR
;
765 is_a_helper
<expr
*>::test (operand
*op
)
767 return op
->type
== operand::OP_EXPR
;
773 is_a_helper
<if_expr
*>::test (operand
*op
)
775 return op
->type
== operand::OP_IF
;
781 is_a_helper
<with_expr
*>::test (operand
*op
)
783 return op
->type
== operand::OP_WITH
;
786 /* The main class of a pattern and its transform. This is used to
787 represent both (simplify ...) and (match ...) kinds. The AST
788 duplicates all outer 'if' and 'for' expressions here so each
789 simplify can exist in isolation. */
793 enum simplify_kind
{ SIMPLIFY
, MATCH
};
795 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
796 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
797 : kind (kind_
), match (match_
), result (result_
),
798 for_vec (for_vec_
), for_subst_vec (vNULL
),
799 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
802 /* The expression that is matched against the GENERIC or GIMPLE IL. */
804 /* For a (simplify ...) an expression with ifs and withs with the expression
805 produced when the pattern applies in the leafs.
806 For a (match ...) the leafs are either empty if it is a simple predicate
807 or the single expression specifying the matched operands. */
808 struct operand
*result
;
809 /* Collected 'for' expression operators that have to be replaced
810 in the lowering phase. */
811 vec
<vec
<user_id
*> > for_vec
;
812 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
813 /* A map of capture identifiers to indexes. */
814 cid_map_t
*capture_ids
;
818 /* Debugging routines for dumping the AST. */
821 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
823 if (capture
*c
= dyn_cast
<capture
*> (o
))
825 if (c
->what
&& flattened
== false)
826 print_operand (c
->what
, f
, flattened
);
827 fprintf (f
, "@%u", c
->where
);
830 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
831 fprintf (f
, "%s", p
->p
->id
);
833 else if (is_a
<c_expr
*> (o
))
834 fprintf (f
, "c_expr");
836 else if (expr
*e
= dyn_cast
<expr
*> (o
))
838 if (e
->ops
.length () == 0)
839 fprintf (f
, "%s", e
->operation
->id
);
842 fprintf (f
, "(%s", e
->operation
->id
);
844 if (flattened
== false)
846 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
849 print_operand (e
->ops
[i
], f
, flattened
);
861 print_matches (struct simplify
*s
, FILE *f
= stderr
)
863 fprintf (f
, "for expression: ");
864 print_operand (s
->match
, f
);
871 /* Lowering of commutative operators. */
874 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
875 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
877 if (n
== ops_vector
.length ())
879 vec
<operand
*> xv
= v
.copy ();
880 result
.safe_push (xv
);
884 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
886 v
[n
] = ops_vector
[n
][i
];
887 cartesian_product (ops_vector
, result
, v
, n
+ 1);
891 /* Lower OP to two operands in case it is marked as commutative. */
893 static vec
<operand
*>
894 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
896 vec
<operand
*> ret
= vNULL
;
898 if (capture
*c
= dyn_cast
<capture
*> (op
))
905 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
906 for (unsigned i
= 0; i
< v
.length (); ++i
)
908 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
915 expr
*e
= dyn_cast
<expr
*> (op
);
916 if (!e
|| e
->ops
.length () == 0)
922 vec
< vec
<operand
*> > ops_vector
= vNULL
;
923 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
924 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
926 auto_vec
< vec
<operand
*> > result
;
927 auto_vec
<operand
*> v (e
->ops
.length ());
928 v
.quick_grow_cleared (e
->ops
.length ());
929 cartesian_product (ops_vector
, result
, v
, 0);
932 for (unsigned i
= 0; i
< result
.length (); ++i
)
934 expr
*ne
= new expr (e
);
935 ne
->is_commutative
= false;
936 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
937 ne
->append_op (result
[i
][j
]);
941 if (!e
->is_commutative
)
944 for (unsigned i
= 0; i
< result
.length (); ++i
)
946 expr
*ne
= new expr (e
);
947 if (operator_id
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
949 if (comparison_code_p (p
->code
))
950 ne
->operation
= swap_tree_comparison (p
);
952 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
954 bool found_compare
= false;
955 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
956 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
958 if (comparison_code_p (q
->code
)
959 && swap_tree_comparison (q
) != q
)
961 found_compare
= true;
967 user_id
*newop
= new user_id ("<internal>");
968 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
970 id_base
*subst
= p
->substitutes
[j
];
971 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
973 if (comparison_code_p (q
->code
))
974 subst
= swap_tree_comparison (q
);
976 newop
->substitutes
.safe_push (subst
);
978 ne
->operation
= newop
;
979 /* Search for 'p' inside the for vector and push 'newop'
980 to the same level. */
981 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
982 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
983 if (for_vec
[j
][k
] == p
)
985 for_vec
[j
].safe_push (newop
);
991 ne
->is_commutative
= false;
992 // result[i].length () is 2 since e->operation is binary
993 for (unsigned j
= result
[i
].length (); j
; --j
)
994 ne
->append_op (result
[i
][j
-1]);
1001 /* Lower operations marked as commutative in the AST of S and push
1002 the resulting patterns to SIMPLIFIERS. */
1005 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1007 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1008 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1010 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1011 s
->for_vec
, s
->capture_ids
);
1012 simplifiers
.safe_push (ns
);
1016 /* Strip conditional conversios using operator OPER from O and its
1017 children if STRIP, else replace them with an unconditional convert. */
1020 lower_opt_convert (operand
*o
, enum tree_code oper
,
1021 enum tree_code to_oper
, bool strip
)
1023 if (capture
*c
= dyn_cast
<capture
*> (o
))
1026 return new capture (c
->location
, c
->where
,
1027 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1033 expr
*e
= dyn_cast
<expr
*> (o
);
1037 if (*e
->operation
== oper
)
1040 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1042 expr
*ne
= new expr (e
);
1043 ne
->operation
= (to_oper
== CONVERT_EXPR
1044 ? get_operator ("CONVERT_EXPR")
1045 : get_operator ("VIEW_CONVERT_EXPR"));
1046 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1050 expr
*ne
= new expr (e
);
1051 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1052 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1057 /* Determine whether O or its children uses the conditional conversion
1061 has_opt_convert (operand
*o
, enum tree_code oper
)
1063 if (capture
*c
= dyn_cast
<capture
*> (o
))
1066 return has_opt_convert (c
->what
, oper
);
1071 expr
*e
= dyn_cast
<expr
*> (o
);
1075 if (*e
->operation
== oper
)
1078 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1079 if (has_opt_convert (e
->ops
[i
], oper
))
1085 /* Lower conditional convert operators in O, expanding it to a vector
1088 static vec
<operand
*>
1089 lower_opt_convert (operand
*o
)
1091 vec
<operand
*> v1
= vNULL
, v2
;
1095 enum tree_code opers
[]
1096 = { CONVERT0
, CONVERT_EXPR
,
1097 CONVERT1
, CONVERT_EXPR
,
1098 CONVERT2
, CONVERT_EXPR
,
1099 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1100 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1101 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1103 /* Conditional converts are lowered to a pattern with the
1104 conversion and one without. The three different conditional
1105 convert codes are lowered separately. */
1107 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1110 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1111 if (has_opt_convert (v1
[j
], opers
[i
]))
1113 v2
.safe_push (lower_opt_convert (v1
[j
],
1114 opers
[i
], opers
[i
+1], false));
1115 v2
.safe_push (lower_opt_convert (v1
[j
],
1116 opers
[i
], opers
[i
+1], true));
1122 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1123 v1
.safe_push (v2
[j
]);
1130 /* Lower conditional convert operators in the AST of S and push
1131 the resulting multiple patterns to SIMPLIFIERS. */
1134 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1136 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1137 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1139 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1140 s
->for_vec
, s
->capture_ids
);
1141 simplifiers
.safe_push (ns
);
1145 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1146 GENERIC and a GIMPLE variant. */
1148 static vec
<operand
*>
1149 lower_cond (operand
*o
)
1151 vec
<operand
*> ro
= vNULL
;
1153 if (capture
*c
= dyn_cast
<capture
*> (o
))
1157 vec
<operand
*> lop
= vNULL
;
1158 lop
= lower_cond (c
->what
);
1160 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1161 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1167 expr
*e
= dyn_cast
<expr
*> (o
);
1168 if (!e
|| e
->ops
.length () == 0)
1174 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1175 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1176 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1178 auto_vec
< vec
<operand
*> > result
;
1179 auto_vec
<operand
*> v (e
->ops
.length ());
1180 v
.quick_grow_cleared (e
->ops
.length ());
1181 cartesian_product (ops_vector
, result
, v
, 0);
1183 for (unsigned i
= 0; i
< result
.length (); ++i
)
1185 expr
*ne
= new expr (e
);
1186 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1187 ne
->append_op (result
[i
][j
]);
1189 /* If this is a COND with a captured expression or an
1190 expression with two operands then also match a GENERIC
1191 form on the compare. */
1192 if ((*e
->operation
== COND_EXPR
1193 || *e
->operation
== VEC_COND_EXPR
)
1194 && ((is_a
<capture
*> (e
->ops
[0])
1195 && as_a
<capture
*> (e
->ops
[0])->what
1196 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1198 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1199 || (is_a
<expr
*> (e
->ops
[0])
1200 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1202 expr
*ne
= new expr (e
);
1203 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1204 ne
->append_op (result
[i
][j
]);
1205 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1207 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1208 expr
*cmp
= new expr (ocmp
);
1209 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1210 cmp
->append_op (ocmp
->ops
[j
]);
1211 cmp
->is_generic
= true;
1212 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1217 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1218 expr
*cmp
= new expr (ocmp
);
1219 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1220 cmp
->append_op (ocmp
->ops
[j
]);
1221 cmp
->is_generic
= true;
1231 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1232 GENERIC and a GIMPLE variant. */
1235 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1237 vec
<operand
*> matchers
= lower_cond (s
->match
);
1238 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1240 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1241 s
->for_vec
, s
->capture_ids
);
1242 simplifiers
.safe_push (ns
);
1246 /* Return true if O refers to ID. */
1249 contains_id (operand
*o
, user_id
*id
)
1251 if (capture
*c
= dyn_cast
<capture
*> (o
))
1252 return c
->what
&& contains_id (c
->what
, id
);
1254 if (expr
*e
= dyn_cast
<expr
*> (o
))
1256 if (e
->operation
== id
)
1258 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1259 if (contains_id (e
->ops
[i
], id
))
1264 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1265 return (contains_id (w
->with
, id
)
1266 || contains_id (w
->subexpr
, id
));
1268 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1269 return (contains_id (ife
->cond
, id
)
1270 || contains_id (ife
->trueexpr
, id
)
1271 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1273 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1274 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1280 /* In AST operand O replace operator ID with operator WITH. */
1283 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1285 /* Deep-copy captures and expressions, replacing operations as
1287 if (capture
*c
= dyn_cast
<capture
*> (o
))
1291 return new capture (c
->location
, c
->where
,
1292 replace_id (c
->what
, id
, with
), c
->value_match
);
1294 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1296 expr
*ne
= new expr (e
);
1297 if (e
->operation
== id
)
1298 ne
->operation
= with
;
1299 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1300 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1303 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1305 with_expr
*nw
= new with_expr (w
->location
);
1306 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1307 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1310 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1312 if_expr
*nife
= new if_expr (ife
->location
);
1313 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1314 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1316 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1320 /* For c_expr we simply record a string replacement table which is
1321 applied at code-generation time. */
1322 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1324 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1325 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1326 return new c_expr (ce
->r
, ce
->location
,
1327 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1333 /* Return true if the binary operator OP is ok for delayed substitution
1334 during for lowering. */
1337 binary_ok (operator_id
*op
)
1344 case TRUNC_DIV_EXPR
:
1346 case FLOOR_DIV_EXPR
:
1347 case ROUND_DIV_EXPR
:
1348 case TRUNC_MOD_EXPR
:
1350 case FLOOR_MOD_EXPR
:
1351 case ROUND_MOD_EXPR
:
1353 case EXACT_DIV_EXPR
:
1365 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1368 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1370 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1371 unsigned worklist_start
= 0;
1372 auto_vec
<simplify
*> worklist
;
1373 worklist
.safe_push (sin
);
1375 /* Lower each recorded for separately, operating on the
1376 set of simplifiers created by the previous one.
1377 Lower inner-to-outer so inner for substitutes can refer
1378 to operators replaced by outer fors. */
1379 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1381 vec
<user_id
*>& ids
= for_vec
[fi
];
1382 unsigned n_ids
= ids
.length ();
1383 unsigned max_n_opers
= 0;
1384 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1385 for (unsigned i
= 0; i
< n_ids
; ++i
)
1387 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1388 max_n_opers
= ids
[i
]->substitutes
.length ();
1389 /* Require that all substitutes are of the same kind so that
1390 if we delay substitution to the result op code generation
1391 can look at the first substitute for deciding things like
1392 types of operands. */
1393 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1394 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1395 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1396 can_delay_subst
= false;
1397 else if (operator_id
*op
1398 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1401 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1402 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1403 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1405 /* Unfortunately we can't just allow all tcc_binary. */
1406 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1407 && strcmp (op0
->tcc
, "tcc_binary") == 0
1411 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1412 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1413 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1414 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1417 can_delay_subst
= false;
1419 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1422 can_delay_subst
= false;
1425 unsigned worklist_end
= worklist
.length ();
1426 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1428 simplify
*s
= worklist
[si
];
1429 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1431 operand
*match_op
= s
->match
;
1432 operand
*result_op
= s
->result
;
1433 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1435 for (unsigned i
= 0; i
< n_ids
; ++i
)
1437 user_id
*id
= ids
[i
];
1438 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1440 && (contains_id (match_op
, id
)
1441 || contains_id (result_op
, id
)))
1446 subst
.quick_push (std::make_pair (id
, oper
));
1447 match_op
= replace_id (match_op
, id
, oper
);
1449 && !can_delay_subst
)
1450 result_op
= replace_id (result_op
, id
, oper
);
1455 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1456 vNULL
, s
->capture_ids
);
1457 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1460 ns
->for_subst_vec
.safe_splice (subst
);
1462 worklist
.safe_push (ns
);
1465 worklist_start
= worklist_end
;
1468 /* Copy out the result from the last for lowering. */
1469 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1470 simplifiers
.safe_push (worklist
[i
]);
1473 /* Lower the AST for everything in SIMPLIFIERS. */
1476 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1478 auto_vec
<simplify
*> out_simplifiers
;
1479 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1480 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1482 simplifiers
.truncate (0);
1483 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1484 lower_commutative (out_simplifiers
[i
], simplifiers
);
1486 out_simplifiers
.truncate (0);
1488 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1489 lower_cond (simplifiers
[i
], out_simplifiers
);
1491 out_simplifiers
.safe_splice (simplifiers
);
1494 simplifiers
.truncate (0);
1495 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1496 lower_for (out_simplifiers
[i
], simplifiers
);
1502 /* The decision tree built for generating GIMPLE and GENERIC pattern
1503 matching code. It represents the 'match' expression of all
1504 simplifies and has those as its leafs. */
1508 /* A hash-map collecting semantically equivalent leafs in the decision
1509 tree for splitting out to separate functions. */
1518 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1521 static inline hashval_t
hash (const key_type
&);
1522 static inline bool equal_keys (const key_type
&, const key_type
&);
1523 template <typename T
> static inline void remove (T
&) {}
1526 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1530 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1534 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1538 vec
<dt_node
*> kids
;
1542 unsigned total_size
;
1545 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1547 dt_node
*append_node (dt_node
*);
1548 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1549 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1550 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1551 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1553 virtual void gen (FILE *, int, bool) {}
1555 void gen_kids (FILE *, int, bool);
1556 void gen_kids_1 (FILE *, int, bool,
1557 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1558 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1560 void analyze (sinfo_map_t
&);
1563 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1565 struct dt_operand
: public dt_node
1568 dt_operand
*match_dop
;
1573 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1574 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1575 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1576 parent (parent_
), pos (pos_
), value_match (false) {}
1578 void gen (FILE *, int, bool);
1579 unsigned gen_predicate (FILE *, int, const char *, bool);
1580 unsigned gen_match_op (FILE *, int, const char *, bool);
1582 unsigned gen_gimple_expr (FILE *, int);
1583 unsigned gen_generic_expr (FILE *, int, const char *);
1585 char *get_name (char *);
1586 void gen_opname (char *, unsigned);
1589 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1591 struct dt_simplify
: public dt_node
1594 unsigned pattern_no
;
1595 dt_operand
**indexes
;
1598 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1599 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1600 indexes (indexes_
), info (NULL
) {}
1602 void gen_1 (FILE *, int, bool, operand
*);
1603 void gen (FILE *f
, int, bool);
1609 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1611 return (n
->type
== dt_node::DT_OPERAND
1612 || n
->type
== dt_node::DT_MATCH
);
1618 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1620 return n
->type
== dt_node::DT_SIMPLIFY
;
1625 /* A container for the actual decision tree. */
1627 struct decision_tree
1631 void insert (struct simplify
*, unsigned);
1632 void gen (FILE *f
, bool gimple
);
1633 void print (FILE *f
= stderr
);
1635 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1637 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1638 unsigned pos
= 0, dt_node
*parent
= 0);
1639 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1640 static bool cmp_node (dt_node
*, dt_node
*);
1641 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1644 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1647 cmp_operand (operand
*o1
, operand
*o2
)
1649 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1652 if (o1
->type
== operand::OP_PREDICATE
)
1654 predicate
*p1
= as_a
<predicate
*>(o1
);
1655 predicate
*p2
= as_a
<predicate
*>(o2
);
1656 return p1
->p
== p2
->p
;
1658 else if (o1
->type
== operand::OP_EXPR
)
1660 expr
*e1
= static_cast<expr
*>(o1
);
1661 expr
*e2
= static_cast<expr
*>(o2
);
1662 return (e1
->operation
== e2
->operation
1663 && e1
->is_generic
== e2
->is_generic
);
1669 /* Compare two decision tree nodes N1 and N2 and return true if they
1673 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1675 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1681 if (n1
->type
== dt_node::DT_TRUE
)
1684 if (n1
->type
== dt_node::DT_OPERAND
)
1685 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1686 (as_a
<dt_operand
*> (n2
))->op
);
1687 else if (n1
->type
== dt_node::DT_MATCH
)
1688 return (((as_a
<dt_operand
*> (n1
))->match_dop
1689 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1690 && ((as_a
<dt_operand
*> (n1
))->value_match
1691 == (as_a
<dt_operand
*> (n2
))->value_match
));
1695 /* Search OPS for a decision tree node like P and return it if found. */
1698 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1700 /* We can merge adjacent DT_TRUE. */
1701 if (p
->type
== dt_node::DT_TRUE
1703 && ops
.last ()->type
== dt_node::DT_TRUE
)
1705 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1707 /* But we can't merge across DT_TRUE nodes as they serve as
1708 pattern order barriers to make sure that patterns apply
1709 in order of appearance in case multiple matches are possible. */
1710 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1712 if (decision_tree::cmp_node (ops
[i
], p
))
1718 /* Append N to the decision tree if it there is not already an existing
1722 dt_node::append_node (dt_node
*n
)
1726 kid
= decision_tree::find_node (kids
, n
);
1731 n
->level
= this->level
+ 1;
1736 /* Append OP to the decision tree. */
1739 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1741 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1742 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1743 return append_node (n
);
1746 /* Append a DT_TRUE decision tree node. */
1749 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1751 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1752 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1753 return append_node (n
);
1756 /* Append a DT_MATCH decision tree node. */
1759 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1761 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1762 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1763 return append_node (n
);
1766 /* Append S to the decision tree. */
1769 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1770 dt_operand
**indexes
)
1772 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1773 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1774 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1776 warning_at (s
->match
->location
, "duplicate pattern");
1777 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1778 print_operand (s
->match
, stderr
);
1779 fprintf (stderr
, "\n");
1781 return append_node (n
);
1784 /* Analyze the node and its children. */
1787 dt_node::analyze (sinfo_map_t
&map
)
1793 if (type
== DT_SIMPLIFY
)
1795 /* Populate the map of equivalent simplifies. */
1796 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1798 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1813 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1815 kids
[i
]->analyze (map
);
1816 num_leafs
+= kids
[i
]->num_leafs
;
1817 total_size
+= kids
[i
]->total_size
;
1818 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1822 /* Insert O into the decision tree and return the decision tree node found
1826 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1827 unsigned pos
, dt_node
*parent
)
1829 dt_node
*q
, *elm
= 0;
1831 if (capture
*c
= dyn_cast
<capture
*> (o
))
1833 unsigned capt_index
= c
->where
;
1835 if (indexes
[capt_index
] == 0)
1838 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1841 q
= elm
= p
->append_true_op (parent
, pos
);
1844 // get to the last capture
1845 for (operand
*what
= c
->what
;
1846 what
&& is_a
<capture
*> (what
);
1847 c
= as_a
<capture
*> (what
), what
= c
->what
)
1852 unsigned cc_index
= c
->where
;
1853 dt_operand
*match_op
= indexes
[cc_index
];
1855 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1856 elm
= decision_tree::find_node (p
->kids
, &temp
);
1860 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1861 temp
.value_match
= c
->value_match
;
1862 elm
= decision_tree::find_node (p
->kids
, &temp
);
1867 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1868 elm
= decision_tree::find_node (p
->kids
, &temp
);
1872 gcc_assert (elm
->type
== dt_node::DT_TRUE
1873 || elm
->type
== dt_node::DT_OPERAND
1874 || elm
->type
== dt_node::DT_MATCH
);
1875 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1880 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1881 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1883 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1888 p
= p
->append_op (o
, parent
, pos
);
1891 if (expr
*e
= dyn_cast
<expr
*>(o
))
1893 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1894 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1900 /* Insert S into the decision tree. */
1903 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1905 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1906 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1907 p
->append_simplify (s
, pattern_no
, indexes
);
1910 /* Debug functions to dump the decision tree. */
1913 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1915 if (p
->type
== dt_node::DT_NODE
)
1916 fprintf (f
, "root");
1920 for (unsigned i
= 0; i
< indent
; i
++)
1923 if (p
->type
== dt_node::DT_OPERAND
)
1925 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1926 print_operand (dop
->op
, f
, true);
1928 else if (p
->type
== dt_node::DT_TRUE
)
1929 fprintf (f
, "true");
1930 else if (p
->type
== dt_node::DT_MATCH
)
1931 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1932 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1934 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1935 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1936 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1937 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1942 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1944 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1945 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1949 decision_tree::print (FILE *f
)
1951 return decision_tree::print_node (root
, f
);
1955 /* For GENERIC we have to take care of wrapping multiple-used
1956 expressions with side-effects in save_expr and preserve side-effects
1957 of expressions with omit_one_operand. Analyze captures in
1958 match, result and with expressions and perform early-outs
1959 on the outermost match expression operands for cases we cannot
1964 capture_info (simplify
*s
, operand
*, bool);
1965 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1966 bool walk_result (operand
*o
, bool, operand
*);
1967 void walk_c_expr (c_expr
*);
1973 bool force_no_side_effects_p
;
1974 bool force_single_use
;
1975 bool cond_expr_cond_p
;
1976 unsigned long toplevel_msk
;
1977 unsigned match_use_count
;
1978 unsigned result_use_count
;
1983 auto_vec
<cinfo
> info
;
1984 unsigned long force_no_side_effects
;
1988 /* Analyze captures in S. */
1990 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
1995 if (s
->kind
== simplify::MATCH
)
1997 force_no_side_effects
= -1;
2001 force_no_side_effects
= 0;
2002 info
.safe_grow_cleared (s
->capture_max
+ 1);
2003 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2004 info
[i
].same_as
= i
;
2006 e
= as_a
<expr
*> (s
->match
);
2007 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2008 walk_match (e
->ops
[i
], i
,
2009 (i
!= 0 && *e
->operation
== COND_EXPR
)
2010 || *e
->operation
== TRUTH_ANDIF_EXPR
2011 || *e
->operation
== TRUTH_ORIF_EXPR
,
2013 && (*e
->operation
== COND_EXPR
2014 || *e
->operation
== VEC_COND_EXPR
));
2016 walk_result (s
->result
, false, result
);
2019 /* Analyze captures in the match expression piece O. */
2022 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2023 bool conditional_p
, bool cond_expr_cond_p
)
2025 if (capture
*c
= dyn_cast
<capture
*> (o
))
2027 unsigned where
= c
->where
;
2028 info
[where
].match_use_count
++;
2029 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2030 info
[where
].force_no_side_effects_p
|= conditional_p
;
2031 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2036 /* Recurse to exprs and captures. */
2037 if (is_a
<capture
*> (c
->what
)
2038 || is_a
<expr
*> (c
->what
))
2039 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2040 /* We need to look past multiple captures to find a captured
2041 expression as with conditional converts two captures
2042 can be collapsed onto the same expression. Also collect
2043 what captures capture the same thing. */
2044 while (c
->what
&& is_a
<capture
*> (c
->what
))
2046 c
= as_a
<capture
*> (c
->what
);
2047 if (info
[c
->where
].same_as
!= c
->where
2048 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2049 fatal_at (c
->location
, "cannot handle this collapsed capture");
2050 info
[c
->where
].same_as
= info
[where
].same_as
;
2052 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2055 && (e
= dyn_cast
<expr
*> (c
->what
)))
2057 info
[where
].expr_p
= true;
2058 info
[where
].force_single_use
|= e
->force_single_use
;
2061 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2063 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2065 bool cond_p
= conditional_p
;
2066 bool cond_expr_cond_p
= false;
2067 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2069 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2070 || *e
->operation
== TRUTH_ORIF_EXPR
)
2073 && (*e
->operation
== COND_EXPR
2074 || *e
->operation
== VEC_COND_EXPR
))
2075 cond_expr_cond_p
= true;
2076 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2079 else if (is_a
<predicate
*> (o
))
2081 /* Mark non-captured leafs toplevel arg for checking. */
2082 force_no_side_effects
|= 1 << toplevel_arg
;
2085 warning_at (o
->location
,
2086 "forcing no side-effects on possibly lost leaf");
2092 /* Analyze captures in the result expression piece O. Return true
2093 if RESULT was visited in one of the children. Only visit
2094 non-if/with children if they are rooted on RESULT. */
2097 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2099 if (capture
*c
= dyn_cast
<capture
*> (o
))
2101 unsigned where
= info
[c
->where
].same_as
;
2102 info
[where
].result_use_count
++;
2103 /* If we substitute an expression capture we don't know
2104 which captures this will end up using (well, we don't
2105 compute that). Force the uses to be side-effect free
2106 which means forcing the toplevels that reach the
2107 expression side-effect free. */
2108 if (info
[where
].expr_p
)
2109 force_no_side_effects
|= info
[where
].toplevel_msk
;
2110 /* Mark CSE capture uses as forced to have no side-effects. */
2112 && is_a
<expr
*> (c
->what
))
2114 info
[where
].cse_p
= true;
2115 walk_result (c
->what
, true, result
);
2118 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2120 id_base
*opr
= e
->operation
;
2121 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2122 opr
= uid
->substitutes
[0];
2123 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2125 bool cond_p
= conditional_p
;
2126 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2128 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2129 || *e
->operation
== TRUTH_ORIF_EXPR
)
2131 walk_result (e
->ops
[i
], cond_p
, result
);
2134 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2136 /* 'if' conditions should be all fine. */
2137 if (e
->trueexpr
== result
)
2139 walk_result (e
->trueexpr
, false, result
);
2142 if (e
->falseexpr
== result
)
2144 walk_result (e
->falseexpr
, false, result
);
2148 if (is_a
<if_expr
*> (e
->trueexpr
)
2149 || is_a
<with_expr
*> (e
->trueexpr
))
2150 res
|= walk_result (e
->trueexpr
, false, result
);
2152 && (is_a
<if_expr
*> (e
->falseexpr
)
2153 || is_a
<with_expr
*> (e
->falseexpr
)))
2154 res
|= walk_result (e
->falseexpr
, false, result
);
2157 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2159 bool res
= (e
->subexpr
== result
);
2161 || is_a
<if_expr
*> (e
->subexpr
)
2162 || is_a
<with_expr
*> (e
->subexpr
))
2163 res
|= walk_result (e
->subexpr
, false, result
);
2165 walk_c_expr (e
->with
);
2168 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2176 /* Look for captures in the C expr E. */
2179 capture_info::walk_c_expr (c_expr
*e
)
2181 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2182 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2183 really escape through. */
2184 unsigned p_depth
= 0;
2185 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2187 const cpp_token
*t
= &e
->code
[i
];
2188 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2190 if (t
->type
== CPP_NAME
2191 && (strcmp ((const char *)CPP_HASHNODE
2192 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2193 || strcmp ((const char *)CPP_HASHNODE
2194 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2195 || strcmp ((const char *)CPP_HASHNODE
2196 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2197 || ((id
= get_operator ((const char *)CPP_HASHNODE
2198 (t
->val
.node
.node
)->ident
.str
))
2199 && is_a
<predicate_id
*> (id
)))
2200 && n
->type
== CPP_OPEN_PAREN
)
2202 else if (t
->type
== CPP_CLOSE_PAREN
2205 else if (p_depth
== 0
2206 && t
->type
== CPP_ATSIGN
2207 && (n
->type
== CPP_NUMBER
2208 || n
->type
== CPP_NAME
)
2209 && !(n
->flags
& PREV_WHITE
))
2212 if (n
->type
== CPP_NUMBER
)
2213 id
= (const char *)n
->val
.str
.text
;
2215 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2216 unsigned *where
= e
->capture_ids
->get(id
);
2218 fatal_at (n
, "unknown capture id '%s'", id
);
2219 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2222 warning_at (t
, "capture escapes");
2228 /* Code generation off the decision tree and the refered AST nodes. */
2231 is_conversion (id_base
*op
)
2233 return (*op
== CONVERT_EXPR
2235 || *op
== FLOAT_EXPR
2236 || *op
== FIX_TRUNC_EXPR
2237 || *op
== VIEW_CONVERT_EXPR
);
2240 /* Get the type to be used for generating operand POS of OP from the
2244 get_operand_type (id_base
*op
, unsigned pos
,
2245 const char *in_type
,
2246 const char *expr_type
,
2247 const char *other_oprnd_type
)
2249 /* Generally operands whose type does not match the type of the
2250 expression generated need to know their types but match and
2251 thus can fall back to 'other_oprnd_type'. */
2252 if (is_conversion (op
))
2253 return other_oprnd_type
;
2254 else if (*op
== REALPART_EXPR
2255 || *op
== IMAGPART_EXPR
)
2256 return other_oprnd_type
;
2257 else if (is_a
<operator_id
*> (op
)
2258 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2259 return other_oprnd_type
;
2260 else if (*op
== COND_EXPR
2262 return "boolean_type_node";
2265 /* Otherwise all types should match - choose one in order of
2272 return other_oprnd_type
;
2276 /* Generate transform code for an expression. */
2279 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2280 int depth
, const char *in_type
, capture_info
*cinfo
,
2281 dt_operand
**indexes
, int)
2283 id_base
*opr
= operation
;
2284 /* When we delay operator substituting during lowering of fors we
2285 make sure that for code-gen purposes the effects of each substitute
2286 are the same. Thus just look at that. */
2287 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2288 opr
= uid
->substitutes
[0];
2290 bool conversion_p
= is_conversion (opr
);
2291 const char *type
= expr_type
;
2294 /* If there was a type specification in the pattern use it. */
2296 else if (conversion_p
)
2297 /* For conversions we need to build the expression using the
2298 outer type passed in. */
2300 else if (*opr
== REALPART_EXPR
2301 || *opr
== IMAGPART_EXPR
)
2303 /* __real and __imag use the component type of its operand. */
2304 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2307 else if (is_a
<operator_id
*> (opr
)
2308 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2310 /* comparisons use boolean_type_node (or what gets in), but
2311 their operands need to figure out the types themselves. */
2316 sprintf (optype
, "boolean_type_node");
2321 else if (*opr
== COND_EXPR
2322 || *opr
== VEC_COND_EXPR
)
2324 /* Conditions are of the same type as their first alternative. */
2325 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2330 /* Other operations are of the same type as their first operand. */
2331 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2335 fatal_at (location
, "cannot determine type of operand");
2337 fprintf_indent (f
, indent
, "{\n");
2339 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2341 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2342 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2345 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2347 = get_operand_type (opr
, i
, in_type
, expr_type
,
2348 i
== 0 ? NULL
: op0type
);
2349 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2352 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2355 const char *opr_name
;
2356 if (*operation
== CONVERT_EXPR
)
2357 opr_name
= "NOP_EXPR";
2359 opr_name
= operation
->id
;
2363 if (*opr
== CONVERT_EXPR
)
2365 fprintf_indent (f
, indent
,
2366 "if (%s != TREE_TYPE (ops%d[0])\n",
2368 fprintf_indent (f
, indent
,
2369 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2371 fprintf_indent (f
, indent
+ 2, "{\n");
2374 /* ??? Building a stmt can fail for various reasons here, seq being
2375 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2376 So if we fail here we should continue matching other patterns. */
2377 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2378 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2379 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2380 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2381 i
== ops
.length () - 1 ? " };\n" : ", ");
2382 fprintf_indent (f
, indent
,
2383 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2384 ops
.length (), type
);
2385 fprintf_indent (f
, indent
,
2386 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2388 fprintf_indent (f
, indent
,
2389 "if (!res) return false;\n");
2390 if (*opr
== CONVERT_EXPR
)
2393 fprintf_indent (f
, indent
, " }\n");
2394 fprintf_indent (f
, indent
, "else\n");
2395 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2400 if (*opr
== CONVERT_EXPR
)
2402 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2406 if (opr
->kind
== id_base::CODE
)
2407 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2408 ops
.length(), opr_name
, type
);
2411 fprintf_indent (f
, indent
, "{\n");
2412 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2413 "%s, %s, %d", opr_name
, type
, ops
.length());
2415 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2416 fprintf (f
, ", ops%d[%u]", depth
, i
);
2417 fprintf (f
, ");\n");
2418 if (opr
->kind
!= id_base::CODE
)
2420 fprintf_indent (f
, indent
, " if (!res)\n");
2421 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2422 fprintf_indent (f
, indent
, "}\n");
2424 if (*opr
== CONVERT_EXPR
)
2427 fprintf_indent (f
, indent
, "else\n");
2428 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2431 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2433 fprintf_indent (f
, indent
, "}\n");
2436 /* Generate code for a c_expr which is either the expression inside
2437 an if statement or a sequence of statements which computes a
2438 result to be stored to DEST. */
2441 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2442 bool, int, const char *, capture_info
*,
2445 if (dest
&& nr_stmts
== 1)
2446 fprintf_indent (f
, indent
, "%s = ", dest
);
2448 unsigned stmt_nr
= 1;
2449 for (unsigned i
= 0; i
< code
.length (); ++i
)
2451 const cpp_token
*token
= &code
[i
];
2453 /* Replace captures for code-gen. */
2454 if (token
->type
== CPP_ATSIGN
)
2456 const cpp_token
*n
= &code
[i
+1];
2457 if ((n
->type
== CPP_NUMBER
2458 || n
->type
== CPP_NAME
)
2459 && !(n
->flags
& PREV_WHITE
))
2461 if (token
->flags
& PREV_WHITE
)
2464 if (n
->type
== CPP_NUMBER
)
2465 id
= (const char *)n
->val
.str
.text
;
2467 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2468 unsigned *cid
= capture_ids
->get (id
);
2470 fatal_at (token
, "unknown capture id");
2471 fprintf (f
, "captures[%u]", *cid
);
2477 if (token
->flags
& PREV_WHITE
)
2480 if (token
->type
== CPP_NAME
)
2482 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2484 for (j
= 0; j
< ids
.length (); ++j
)
2486 if (strcmp (id
, ids
[j
].id
) == 0)
2488 fprintf (f
, "%s", ids
[j
].oper
);
2492 if (j
< ids
.length ())
2496 /* Output the token as string. */
2497 char *tk
= (char *)cpp_token_as_text (r
, token
);
2500 if (token
->type
== CPP_SEMICOLON
)
2504 if (dest
&& stmt_nr
== nr_stmts
)
2505 fprintf_indent (f
, indent
, "%s = ", dest
);
2510 /* Generate transform code for a capture. */
2513 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2514 int depth
, const char *in_type
, capture_info
*cinfo
,
2515 dt_operand
**indexes
, int cond_handling
)
2517 if (what
&& is_a
<expr
*> (what
))
2519 if (indexes
[where
] == 0)
2522 sprintf (buf
, "captures[%u]", where
);
2523 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2528 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2530 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2531 with substituting a capture of that. */
2533 && cond_handling
!= 0
2534 && cinfo
->info
[where
].cond_expr_cond_p
)
2536 /* If substituting into a cond_expr condition, unshare. */
2537 if (cond_handling
== 1)
2538 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2539 /* If substituting elsewhere we might need to decompose it. */
2540 else if (cond_handling
== 2)
2542 /* ??? Returning false here will also not allow any other patterns
2543 to match unless this generator was split out. */
2544 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2545 fprintf_indent (f
, indent
, " {\n");
2546 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2547 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2549 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2550 " TREE_OPERAND (%s, 1));\n",
2551 dest
, dest
, dest
, dest
, dest
);
2552 fprintf_indent (f
, indent
, " }\n");
2557 /* Return the name of the operand representing the decision tree node.
2558 Use NAME as space to generate it. */
2561 dt_operand::get_name (char *name
)
2564 sprintf (name
, "t");
2565 else if (parent
->level
== 1)
2566 sprintf (name
, "op%u", pos
);
2567 else if (parent
->type
== dt_node::DT_MATCH
)
2568 return parent
->get_name (name
);
2570 sprintf (name
, "o%u%u", parent
->level
, pos
);
2574 /* Fill NAME with the operand name at position POS. */
2577 dt_operand::gen_opname (char *name
, unsigned pos
)
2580 sprintf (name
, "op%u", pos
);
2582 sprintf (name
, "o%u%u", level
, pos
);
2585 /* Generate matching code for the decision tree operand which is
2589 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2591 predicate
*p
= as_a
<predicate
*> (op
);
2593 if (p
->p
->matchers
.exists ())
2595 /* If this is a predicate generated from a pattern mangle its
2596 name and pass on the valueize hook. */
2598 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2601 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2604 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2605 fprintf_indent (f
, indent
+ 2, "{\n");
2609 /* Generate matching code for the decision tree operand which is
2613 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2615 char match_opname
[20];
2616 match_dop
->get_name (match_opname
);
2618 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2619 opname
, match_opname
, opname
, match_opname
);
2621 fprintf_indent (f
, indent
, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
2622 "&& types_match (%s, %s)))\n",
2623 opname
, match_opname
, opname
, match_opname
,
2624 opname
, match_opname
);
2625 fprintf_indent (f
, indent
+ 2, "{\n");
2629 /* Generate GIMPLE matching code for the decision tree operand. */
2632 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2634 expr
*e
= static_cast<expr
*> (op
);
2635 id_base
*id
= e
->operation
;
2636 unsigned n_ops
= e
->ops
.length ();
2638 for (unsigned i
= 0; i
< n_ops
; ++i
)
2640 char child_opname
[20];
2641 gen_opname (child_opname
, i
);
2643 if (id
->kind
== id_base::CODE
)
2646 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2647 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2649 /* ??? If this is a memory operation we can't (and should not)
2650 match this. The only sensible operand types are
2651 SSA names and invariants. */
2656 fprintf_indent (f
, indent
,
2657 "tree %s = TREE_OPERAND (%s, %i);\n",
2658 child_opname
, opname
, i
);
2661 fprintf_indent (f
, indent
,
2662 "tree %s = TREE_OPERAND "
2663 "(gimple_assign_rhs1 (def), %i);\n",
2665 fprintf_indent (f
, indent
,
2666 "if ((TREE_CODE (%s) == SSA_NAME\n",
2668 fprintf_indent (f
, indent
,
2669 " || is_gimple_min_invariant (%s))\n",
2671 fprintf_indent (f
, indent
,
2672 " && (%s = do_valueize (valueize, %s)))\n",
2673 child_opname
, child_opname
);
2674 fprintf_indent (f
, indent
,
2680 fprintf_indent (f
, indent
,
2681 "tree %s = gimple_assign_rhs%u (def);\n",
2682 child_opname
, i
+ 1);
2685 fprintf_indent (f
, indent
,
2686 "tree %s = gimple_call_arg (def, %u);\n",
2688 fprintf_indent (f
, indent
,
2689 "if ((%s = do_valueize (valueize, %s)))\n",
2690 child_opname
, child_opname
);
2691 fprintf_indent (f
, indent
, " {\n");
2694 /* While the toplevel operands are canonicalized by the caller
2695 after valueizing operands of sub-expressions we have to
2696 re-canonicalize operand order. */
2697 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2699 /* ??? We can't canonicalize tcc_comparison operands here
2700 because that requires changing the comparison code which
2701 we already matched... */
2702 if (commutative_tree_code (code
->code
)
2703 || commutative_ternary_tree_code (code
->code
))
2705 char child_opname0
[20], child_opname1
[20];
2706 gen_opname (child_opname0
, 0);
2707 gen_opname (child_opname1
, 1);
2708 fprintf_indent (f
, indent
,
2709 "if (tree_swap_operands_p (%s, %s))\n",
2710 child_opname0
, child_opname1
);
2711 fprintf_indent (f
, indent
,
2712 " std::swap (%s, %s);\n",
2713 child_opname0
, child_opname1
);
2720 /* Generate GENERIC matching code for the decision tree operand. */
2723 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2725 expr
*e
= static_cast<expr
*> (op
);
2726 unsigned n_ops
= e
->ops
.length ();
2728 for (unsigned i
= 0; i
< n_ops
; ++i
)
2730 char child_opname
[20];
2731 gen_opname (child_opname
, i
);
2733 if (e
->operation
->kind
== id_base::CODE
)
2734 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2735 child_opname
, opname
, i
);
2737 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2738 child_opname
, opname
, i
);
2744 /* Generate matching code for the children of the decision tree node. */
2747 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2749 auto_vec
<dt_operand
*> gimple_exprs
;
2750 auto_vec
<dt_operand
*> generic_exprs
;
2751 auto_vec
<dt_operand
*> fns
;
2752 auto_vec
<dt_operand
*> generic_fns
;
2753 auto_vec
<dt_operand
*> preds
;
2754 auto_vec
<dt_node
*> others
;
2756 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2758 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2760 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2761 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2763 if (e
->ops
.length () == 0
2764 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2765 generic_exprs
.safe_push (op
);
2766 else if (e
->operation
->kind
== id_base::FN
)
2771 generic_fns
.safe_push (op
);
2773 else if (e
->operation
->kind
== id_base::PREDICATE
)
2774 preds
.safe_push (op
);
2777 if (gimple
&& !e
->is_generic
)
2778 gimple_exprs
.safe_push (op
);
2780 generic_exprs
.safe_push (op
);
2783 else if (op
->op
->type
== operand::OP_PREDICATE
)
2784 others
.safe_push (kids
[i
]);
2788 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2789 others
.safe_push (kids
[i
]);
2790 else if (kids
[i
]->type
== dt_node::DT_MATCH
2791 || kids
[i
]->type
== dt_node::DT_TRUE
)
2793 /* A DT_TRUE operand serves as a barrier - generate code now
2794 for what we have collected sofar.
2795 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2796 dependent matches to get out-of-order. Generate code now
2797 for what we have collected sofar. */
2798 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2799 fns
, generic_fns
, preds
, others
);
2800 /* And output the true operand itself. */
2801 kids
[i
]->gen (f
, indent
, gimple
);
2802 gimple_exprs
.truncate (0);
2803 generic_exprs
.truncate (0);
2805 generic_fns
.truncate (0);
2807 others
.truncate (0);
2813 /* Generate code for the remains. */
2814 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2815 fns
, generic_fns
, preds
, others
);
2818 /* Generate matching code for the children of the decision tree node. */
2821 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2822 vec
<dt_operand
*> gimple_exprs
,
2823 vec
<dt_operand
*> generic_exprs
,
2824 vec
<dt_operand
*> fns
,
2825 vec
<dt_operand
*> generic_fns
,
2826 vec
<dt_operand
*> preds
,
2827 vec
<dt_node
*> others
)
2830 char *kid_opname
= buf
;
2832 unsigned exprs_len
= gimple_exprs
.length ();
2833 unsigned gexprs_len
= generic_exprs
.length ();
2834 unsigned fns_len
= fns
.length ();
2835 unsigned gfns_len
= generic_fns
.length ();
2837 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2840 gimple_exprs
[0]->get_name (kid_opname
);
2842 fns
[0]->get_name (kid_opname
);
2844 generic_fns
[0]->get_name (kid_opname
);
2846 generic_exprs
[0]->get_name (kid_opname
);
2848 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2849 fprintf_indent (f
, indent
, " {\n");
2853 if (exprs_len
|| fns_len
)
2855 fprintf_indent (f
, indent
,
2856 "case SSA_NAME:\n");
2857 fprintf_indent (f
, indent
,
2858 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2860 fprintf_indent (f
, indent
,
2862 fprintf_indent (f
, indent
,
2863 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2869 fprintf_indent (f
, indent
,
2870 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2871 fprintf_indent (f
, indent
,
2872 " switch (gimple_assign_rhs_code (def))\n");
2874 fprintf_indent (f
, indent
, "{\n");
2875 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2877 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2878 id_base
*op
= e
->operation
;
2879 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2880 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2882 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2883 fprintf_indent (f
, indent
, " {\n");
2884 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2885 fprintf_indent (f
, indent
, " break;\n");
2886 fprintf_indent (f
, indent
, " }\n");
2888 fprintf_indent (f
, indent
, "default:;\n");
2889 fprintf_indent (f
, indent
, "}\n");
2895 fprintf_indent (f
, indent
,
2896 "%sif (gcall *def = dyn_cast <gcall *>"
2898 exprs_len
? "else " : "");
2899 fprintf_indent (f
, indent
,
2900 " switch (gimple_call_combined_fn (def))\n");
2903 fprintf_indent (f
, indent
, "{\n");
2904 for (unsigned i
= 0; i
< fns_len
; ++i
)
2906 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2907 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2908 fprintf_indent (f
, indent
, " {\n");
2909 fns
[i
]->gen (f
, indent
+ 4, true);
2910 fprintf_indent (f
, indent
, " break;\n");
2911 fprintf_indent (f
, indent
, " }\n");
2914 fprintf_indent (f
, indent
, "default:;\n");
2915 fprintf_indent (f
, indent
, "}\n");
2920 fprintf_indent (f
, indent
, " }\n");
2921 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
2922 here rather than in the next loop. */
2923 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2925 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2926 id_base
*op
= e
->operation
;
2927 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
2929 fprintf_indent (f
, indent
+ 4, "{\n");
2930 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
2931 fprintf_indent (f
, indent
+ 4, "}\n");
2935 fprintf_indent (f
, indent
, " break;\n");
2938 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2940 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2941 id_base
*op
= e
->operation
;
2942 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2943 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2944 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
2945 /* Already handled above. */
2948 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2949 fprintf_indent (f
, indent
, " {\n");
2950 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2951 fprintf_indent (f
, indent
, " break;\n");
2952 fprintf_indent (f
, indent
, " }\n");
2957 fprintf_indent (f
, indent
,
2958 "case CALL_EXPR:\n");
2959 fprintf_indent (f
, indent
,
2960 " switch (get_call_combined_fn (%s))\n",
2962 fprintf_indent (f
, indent
,
2966 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2968 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2969 gcc_assert (e
->operation
->kind
== id_base::FN
);
2971 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2972 fprintf_indent (f
, indent
, " {\n");
2973 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2974 fprintf_indent (f
, indent
, " break;\n");
2975 fprintf_indent (f
, indent
, " }\n");
2977 fprintf_indent (f
, indent
, "default:;\n");
2980 fprintf_indent (f
, indent
, " }\n");
2981 fprintf_indent (f
, indent
, " break;\n");
2984 /* Close switch (TREE_CODE ()). */
2985 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2988 fprintf_indent (f
, indent
, " default:;\n");
2989 fprintf_indent (f
, indent
, " }\n");
2992 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2994 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2995 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2996 preds
[i
]->get_name (kid_opname
);
2997 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2998 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2999 gimple
? "gimple" : "tree",
3000 p
->id
, kid_opname
, kid_opname
,
3001 gimple
? ", valueize" : "");
3002 fprintf_indent (f
, indent
, " {\n");
3003 for (int j
= 0; j
< p
->nargs
; ++j
)
3005 char child_opname
[20];
3006 preds
[i
]->gen_opname (child_opname
, j
);
3007 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3008 child_opname
, kid_opname
, j
);
3010 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3014 for (unsigned i
= 0; i
< others
.length (); ++i
)
3015 others
[i
]->gen (f
, indent
, gimple
);
3018 /* Generate matching code for the decision tree operand. */
3021 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3026 unsigned n_braces
= 0;
3028 if (type
== DT_OPERAND
)
3031 case operand::OP_PREDICATE
:
3032 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3035 case operand::OP_EXPR
:
3037 n_braces
= gen_gimple_expr (f
, indent
);
3039 n_braces
= gen_generic_expr (f
, indent
, opname
);
3045 else if (type
== DT_TRUE
)
3047 else if (type
== DT_MATCH
)
3048 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3052 indent
+= 4 * n_braces
;
3053 gen_kids (f
, indent
, gimple
);
3055 for (unsigned i
= 0; i
< n_braces
; ++i
)
3060 fprintf_indent (f
, indent
, " }\n");
3065 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3066 step of a '(simplify ...)' or '(match ...)'. This handles everything
3067 that is not part of the decision tree (simplify->match).
3068 Main recursive worker. */
3071 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3075 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3077 fprintf_indent (f
, indent
, "{\n");
3079 output_line_directive (f
, w
->location
);
3080 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3081 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3083 fprintf_indent (f
, indent
, "}\n");
3086 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3088 output_line_directive (f
, ife
->location
);
3089 fprintf_indent (f
, indent
, "if (");
3090 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3092 fprintf_indent (f
, indent
+ 2, "{\n");
3094 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3096 fprintf_indent (f
, indent
+ 2, "}\n");
3099 fprintf_indent (f
, indent
, "else\n");
3100 fprintf_indent (f
, indent
+ 2, "{\n");
3102 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3104 fprintf_indent (f
, indent
+ 2, "}\n");
3110 /* Analyze captures and perform early-outs on the incoming arguments
3111 that cover cases we cannot handle. */
3112 capture_info
cinfo (s
, result
, gimple
);
3113 if (s
->kind
== simplify::SIMPLIFY
)
3117 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3118 if (cinfo
.force_no_side_effects
& (1 << i
))
3120 fprintf_indent (f
, indent
,
3121 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3124 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3125 "forcing toplevel operand to have no "
3128 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3129 if (cinfo
.info
[i
].cse_p
)
3131 else if (cinfo
.info
[i
].force_no_side_effects_p
3132 && (cinfo
.info
[i
].toplevel_msk
3133 & cinfo
.force_no_side_effects
) == 0)
3135 fprintf_indent (f
, indent
,
3136 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3137 "return NULL_TREE;\n", i
);
3139 warning_at (cinfo
.info
[i
].c
->location
,
3140 "forcing captured operand to have no "
3143 else if ((cinfo
.info
[i
].toplevel_msk
3144 & cinfo
.force_no_side_effects
) != 0)
3145 /* Mark capture as having no side-effects if we had to verify
3146 that via forced toplevel operand checks. */
3147 cinfo
.info
[i
].force_no_side_effects_p
= true;
3151 /* Force single-use restriction by only allowing simple
3152 results via setting seq to NULL. */
3153 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3154 bool first_p
= true;
3155 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3156 if (cinfo
.info
[i
].force_single_use
)
3160 fprintf_indent (f
, indent
, "if (lseq\n");
3161 fprintf_indent (f
, indent
, " && (");
3167 fprintf_indent (f
, indent
, " || ");
3169 fprintf (f
, "!single_use (captures[%d])", i
);
3173 fprintf (f
, "))\n");
3174 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3179 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
3180 "fprintf (dump_file, \"Applying pattern ");
3181 output_line_directive (f
,
3182 result
? result
->location
: s
->match
->location
, true);
3183 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3187 /* If there is no result then this is a predicate implementation. */
3188 fprintf_indent (f
, indent
, "return true;\n");
3192 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3193 in outermost position). */
3194 if (result
->type
== operand::OP_EXPR
3195 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3196 result
= as_a
<expr
*> (result
)->ops
[0];
3197 if (result
->type
== operand::OP_EXPR
)
3199 expr
*e
= as_a
<expr
*> (result
);
3200 id_base
*opr
= e
->operation
;
3201 bool is_predicate
= false;
3202 /* When we delay operator substituting during lowering of fors we
3203 make sure that for code-gen purposes the effects of each substitute
3204 are the same. Thus just look at that. */
3205 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3206 opr
= uid
->substitutes
[0];
3207 else if (is_a
<predicate_id
*> (opr
))
3208 is_predicate
= true;
3210 fprintf_indent (f
, indent
, "*res_code = %s;\n",
3211 *e
->operation
== CONVERT_EXPR
3212 ? "NOP_EXPR" : e
->operation
->id
);
3213 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3216 snprintf (dest
, 32, "res_ops[%d]", j
);
3218 = get_operand_type (opr
, j
,
3219 "type", e
->expr_type
,
3220 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
3221 /* We need to expand GENERIC conditions we captured from
3222 COND_EXPRs and we need to unshare them when substituting
3224 int cond_handling
= 0;
3226 cond_handling
= ((*opr
== COND_EXPR
3227 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3228 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3229 &cinfo
, indexes
, cond_handling
);
3232 /* Re-fold the toplevel result. It's basically an embedded
3233 gimple_build w/o actually building the stmt. */
3235 fprintf_indent (f
, indent
,
3236 "gimple_resimplify%d (lseq, res_code, type, "
3237 "res_ops, valueize);\n", e
->ops
.length ());
3239 else if (result
->type
== operand::OP_CAPTURE
3240 || result
->type
== operand::OP_C_EXPR
)
3242 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
3244 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
3245 if (is_a
<capture
*> (result
)
3246 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3248 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3249 with substituting a capture of that. */
3250 fprintf_indent (f
, indent
,
3251 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3252 fprintf_indent (f
, indent
,
3254 fprintf_indent (f
, indent
,
3255 " tree tem = res_ops[0];\n");
3256 fprintf_indent (f
, indent
,
3257 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3258 fprintf_indent (f
, indent
,
3259 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3260 fprintf_indent (f
, indent
,
3266 fprintf_indent (f
, indent
, "return true;\n");
3270 bool is_predicate
= false;
3271 if (result
->type
== operand::OP_EXPR
)
3273 expr
*e
= as_a
<expr
*> (result
);
3274 id_base
*opr
= e
->operation
;
3275 /* When we delay operator substituting during lowering of fors we
3276 make sure that for code-gen purposes the effects of each substitute
3277 are the same. Thus just look at that. */
3278 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3279 opr
= uid
->substitutes
[0];
3280 else if (is_a
<predicate_id
*> (opr
))
3281 is_predicate
= true;
3282 /* Search for captures used multiple times in the result expression
3283 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3284 original expression. */
3286 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3288 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3289 || cinfo
.info
[i
].cse_p
)
3291 if (cinfo
.info
[i
].result_use_count
3292 > cinfo
.info
[i
].match_use_count
)
3293 fprintf_indent (f
, indent
,
3294 "if (! tree_invariant_p (captures[%d])) "
3295 "return NULL_TREE;\n", i
);
3297 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3301 snprintf (dest
, 32, "res_ops[%d]", j
);
3304 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3305 snprintf (dest
, 32, "res_op%d", j
);
3308 = get_operand_type (opr
, j
,
3309 "type", e
->expr_type
,
3311 ? NULL
: "TREE_TYPE (res_op0)");
3312 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3316 fprintf_indent (f
, indent
, "return true;\n");
3319 fprintf_indent (f
, indent
, "tree res;\n");
3320 /* Re-fold the toplevel result. Use non_lvalue to
3321 build NON_LVALUE_EXPRs so they get properly
3322 ignored when in GIMPLE form. */
3323 if (*opr
== NON_LVALUE_EXPR
)
3324 fprintf_indent (f
, indent
,
3325 "res = non_lvalue_loc (loc, res_op0);\n");
3328 if (is_a
<operator_id
*> (opr
))
3329 fprintf_indent (f
, indent
,
3330 "res = fold_build%d_loc (loc, %s, type",
3332 *e
->operation
== CONVERT_EXPR
3333 ? "NOP_EXPR" : e
->operation
->id
);
3335 fprintf_indent (f
, indent
,
3336 "res = maybe_build_call_expr_loc (loc, "
3337 "%s, type, %d", e
->operation
->id
,
3339 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3340 fprintf (f
, ", res_op%d", j
);
3341 fprintf (f
, ");\n");
3342 if (!is_a
<operator_id
*> (opr
))
3344 fprintf_indent (f
, indent
, "if (!res)\n");
3345 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3350 else if (result
->type
== operand::OP_CAPTURE
3351 || result
->type
== operand::OP_C_EXPR
)
3354 fprintf_indent (f
, indent
, "tree res;\n");
3355 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3362 /* Search for captures not used in the result expression and dependent
3363 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3364 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3366 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3368 if (!cinfo
.info
[i
].force_no_side_effects_p
3369 && !cinfo
.info
[i
].expr_p
3370 && cinfo
.info
[i
].result_use_count
== 0)
3372 fprintf_indent (f
, indent
,
3373 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3375 fprintf_indent (f
, indent
+ 2,
3376 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3377 "fold_ignored_result (captures[%d]), res);\n",
3381 fprintf_indent (f
, indent
, "return res;\n");
3386 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3387 step of a '(simplify ...)' or '(match ...)'. This handles everything
3388 that is not part of the decision tree (simplify->match). */
3391 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3393 fprintf_indent (f
, indent
, "{\n");
3395 output_line_directive (f
,
3396 s
->result
? s
->result
->location
: s
->match
->location
);
3397 if (s
->capture_max
>= 0)
3400 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3401 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3403 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3407 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3409 fprintf (f
, " };\n");
3412 /* If we have a split-out function for the actual transform, call it. */
3413 if (info
&& info
->fname
)
3417 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3418 "valueize, type, captures", info
->fname
);
3419 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3420 if (s
->for_subst_vec
[i
].first
->used
)
3421 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3422 fprintf (f
, "))\n");
3423 fprintf_indent (f
, indent
, " return true;\n");
3427 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3429 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3430 fprintf (f
, ", op%d", i
);
3431 fprintf (f
, ", captures");
3432 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3434 if (s
->for_subst_vec
[i
].first
->used
)
3435 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3437 fprintf (f
, ");\n");
3438 fprintf_indent (f
, indent
, "if (res) return res;\n");
3443 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3445 if (! s
->for_subst_vec
[i
].first
->used
)
3447 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3448 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3449 s
->for_subst_vec
[i
].first
->id
,
3450 s
->for_subst_vec
[i
].second
->id
);
3451 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3452 fprintf_indent (f
, indent
, "combined_fn %s = %s;\n",
3453 s
->for_subst_vec
[i
].first
->id
,
3454 s
->for_subst_vec
[i
].second
->id
);
3458 gen_1 (f
, indent
, gimple
, s
->result
);
3462 fprintf_indent (f
, indent
, "}\n");
3466 /* Hash function for finding equivalent transforms. */
3469 sinfo_hashmap_traits::hash (const key_type
&v
)
3471 /* Only bother to compare those originating from the same source pattern. */
3472 return v
->s
->result
->location
;
3475 /* Compare function for finding equivalent transforms. */
3478 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3480 if (o1
->type
!= o2
->type
)
3485 case operand::OP_IF
:
3487 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3488 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3489 /* ??? Properly compare c-exprs. */
3490 if (if1
->cond
!= if2
->cond
)
3492 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3494 if (if1
->falseexpr
!= if2
->falseexpr
3496 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3500 case operand::OP_WITH
:
3502 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3503 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3504 if (with1
->with
!= with2
->with
)
3506 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3511 /* We've hit a result. Time to compare capture-infos - this is required
3512 in addition to the conservative pointer-equivalency of the result IL. */
3513 capture_info
cinfo1 (s1
, o1
, true);
3514 capture_info
cinfo2 (s2
, o2
, true);
3516 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3517 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3520 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3522 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3523 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3524 || (cinfo1
.info
[i
].force_no_side_effects_p
3525 != cinfo2
.info
[i
].force_no_side_effects_p
)
3526 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3527 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3528 /* toplevel_msk is an optimization */
3529 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3530 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3531 /* the pointer back to the capture is for diagnostics only */)
3535 /* ??? Deep-compare the actual result. */
3540 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3541 const key_type
&candidate
)
3543 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3547 /* Main entry to generate code for matching GIMPLE IL off the decision
3551 decision_tree::gen (FILE *f
, bool gimple
)
3557 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3558 "a total number of %u nodes\n",
3559 gimple
? "GIMPLE" : "GENERIC",
3560 root
->num_leafs
, root
->max_level
, root
->total_size
);
3562 /* First split out the transform part of equal leafs. */
3565 for (sinfo_map_t::iterator iter
= si
.begin ();
3566 iter
!= si
.end (); ++iter
)
3568 sinfo
*s
= (*iter
).second
;
3569 /* Do not split out single uses. */
3576 fprintf (stderr
, "found %u uses of", s
->cnt
);
3577 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3580 /* Generate a split out function with the leaf transform code. */
3581 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3584 fprintf (f
, "\nstatic bool\n"
3585 "%s (code_helper *res_code, tree *res_ops,\n"
3586 " gimple_seq *seq, tree (*valueize)(tree) "
3587 "ATTRIBUTE_UNUSED,\n"
3588 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3593 fprintf (f
, "\nstatic tree\n"
3594 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3595 (*iter
).second
->fname
);
3596 for (unsigned i
= 0;
3597 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3598 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3599 fprintf (f
, " tree *captures\n");
3601 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3603 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3605 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3606 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3607 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3608 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3609 fprintf (f
, ", combined_fn ARG_UNUSED (%s)",
3610 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3613 fprintf (f
, ")\n{\n");
3614 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3616 fprintf (f
, " return false;\n");
3618 fprintf (f
, " return NULL_TREE;\n");
3621 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3623 for (unsigned n
= 1; n
<= 3; ++n
)
3625 /* First generate split-out functions. */
3626 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3628 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3629 expr
*e
= static_cast<expr
*>(dop
->op
);
3630 if (e
->ops
.length () != n
3631 /* Builtin simplifications are somewhat premature on
3632 GENERIC. The following drops patterns with outermost
3633 calls. It's easy to emit overloads for function code
3634 though if necessary. */
3636 && e
->operation
->kind
!= id_base::CODE
))
3640 fprintf (f
, "\nstatic bool\n"
3641 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3642 " gimple_seq *seq, tree (*valueize)(tree) "
3643 "ATTRIBUTE_UNUSED,\n"
3644 " code_helper ARG_UNUSED (code), tree "
3645 "ARG_UNUSED (type)\n",
3648 fprintf (f
, "\nstatic tree\n"
3649 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3650 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3652 for (unsigned i
= 0; i
< n
; ++i
)
3653 fprintf (f
, ", tree op%d", i
);
3656 dop
->gen_kids (f
, 2, gimple
);
3658 fprintf (f
, " return false;\n");
3660 fprintf (f
, " return NULL_TREE;\n");
3664 /* Then generate the main entry with the outermost switch and
3665 tail-calls to the split-out functions. */
3667 fprintf (f
, "\nstatic bool\n"
3668 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3669 " gimple_seq *seq, tree (*valueize)(tree),\n"
3670 " code_helper code, tree type");
3672 fprintf (f
, "\ntree\n"
3673 "generic_simplify (location_t loc, enum tree_code code, "
3674 "tree type ATTRIBUTE_UNUSED");
3675 for (unsigned i
= 0; i
< n
; ++i
)
3676 fprintf (f
, ", tree op%d", i
);
3681 fprintf (f
, " switch (code.get_rep())\n"
3684 fprintf (f
, " switch (code)\n"
3686 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3688 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3689 expr
*e
= static_cast<expr
*>(dop
->op
);
3690 if (e
->ops
.length () != n
3691 /* Builtin simplifications are somewhat premature on
3692 GENERIC. The following drops patterns with outermost
3693 calls. It's easy to emit overloads for function code
3694 though if necessary. */
3696 && e
->operation
->kind
!= id_base::CODE
))
3699 if (*e
->operation
== CONVERT_EXPR
3700 || *e
->operation
== NOP_EXPR
)
3701 fprintf (f
, " CASE_CONVERT:\n");
3703 fprintf (f
, " case %s%s:\n",
3704 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3707 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3708 "seq, valueize, code, type", e
->operation
->id
);
3710 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3712 for (unsigned i
= 0; i
< n
; ++i
)
3713 fprintf (f
, ", op%d", i
);
3714 fprintf (f
, ");\n");
3716 fprintf (f
, " default:;\n"
3720 fprintf (f
, " return false;\n");
3722 fprintf (f
, " return NULL_TREE;\n");
3727 /* Output code to implement the predicate P from the decision tree DT. */
3730 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3732 fprintf (f
, "\nbool\n"
3733 "%s%s (tree t%s%s)\n"
3734 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3735 p
->nargs
> 0 ? ", tree *res_ops" : "",
3736 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3737 /* Conveniently make 'type' available. */
3738 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3741 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3742 dt
.root
->gen_kids (f
, 2, gimple
);
3744 fprintf_indent (f
, 2, "return false;\n"
3748 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3751 write_header (FILE *f
, const char *head
)
3753 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3754 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3756 /* Include the header instead of writing it awkwardly quoted here. */
3757 fprintf (f
, "\n#include \"%s\"\n", head
);
3767 parser (cpp_reader
*);
3770 const cpp_token
*next ();
3771 const cpp_token
*peek (unsigned = 1);
3772 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3773 const cpp_token
*expect (enum cpp_ttype
);
3774 const cpp_token
*eat_token (enum cpp_ttype
);
3775 const char *get_string ();
3776 const char *get_ident ();
3777 const cpp_token
*eat_ident (const char *);
3778 const char *get_number ();
3780 unsigned get_internal_capture_id ();
3782 id_base
*parse_operation ();
3783 operand
*parse_capture (operand
*, bool);
3784 operand
*parse_expr ();
3785 c_expr
*parse_c_expr (cpp_ttype
);
3786 operand
*parse_op ();
3788 void record_operlist (source_location
, user_id
*);
3790 void parse_pattern ();
3791 operand
*parse_result (operand
*, predicate_id
*);
3792 void push_simplify (simplify::simplify_kind
,
3793 vec
<simplify
*>&, operand
*, operand
*);
3794 void parse_simplify (simplify::simplify_kind
,
3795 vec
<simplify
*>&, predicate_id
*, operand
*);
3796 void parse_for (source_location
);
3797 void parse_if (source_location
);
3798 void parse_predicates (source_location
);
3799 void parse_operator_list (source_location
);
3801 void finish_match_operand (operand
*);
3804 vec
<c_expr
*> active_ifs
;
3805 vec
<vec
<user_id
*> > active_fors
;
3806 hash_set
<user_id
*> *oper_lists_set
;
3807 vec
<user_id
*> oper_lists
;
3809 cid_map_t
*capture_ids
;
3812 vec
<simplify
*> simplifiers
;
3813 vec
<predicate_id
*> user_predicates
;
3814 bool parsing_match_operand
;
3817 /* Lexing helpers. */
3819 /* Read the next non-whitespace token from R. */
3824 const cpp_token
*token
;
3827 token
= cpp_get_token (r
);
3829 while (token
->type
== CPP_PADDING
3830 && token
->type
!= CPP_EOF
);
3834 /* Peek at the next non-whitespace token from R. */
3837 parser::peek (unsigned num
)
3839 const cpp_token
*token
;
3843 token
= cpp_peek_token (r
, i
++);
3845 while ((token
->type
== CPP_PADDING
3846 && token
->type
!= CPP_EOF
)
3848 /* If we peek at EOF this is a fatal error as it leaves the
3849 cpp_reader in unusable state. Assume we really wanted a
3850 token and thus this EOF is unexpected. */
3851 if (token
->type
== CPP_EOF
)
3852 fatal_at (token
, "unexpected end of file");
3856 /* Peek at the next identifier token (or return NULL if the next
3857 token is not an identifier or equal to ID if supplied). */
3860 parser::peek_ident (const char *id
, unsigned num
)
3862 const cpp_token
*token
= peek (num
);
3863 if (token
->type
!= CPP_NAME
)
3869 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3870 if (strcmp (id
, t
) == 0)
3876 /* Read the next token from R and assert it is of type TK. */
3879 parser::expect (enum cpp_ttype tk
)
3881 const cpp_token
*token
= next ();
3882 if (token
->type
!= tk
)
3883 fatal_at (token
, "expected %s, got %s",
3884 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3889 /* Consume the next token from R and assert it is of type TK. */
3892 parser::eat_token (enum cpp_ttype tk
)
3897 /* Read the next token from R and assert it is of type CPP_STRING and
3898 return its value. */
3901 parser::get_string ()
3903 const cpp_token
*token
= expect (CPP_STRING
);
3904 return (const char *)token
->val
.str
.text
;
3907 /* Read the next token from R and assert it is of type CPP_NAME and
3908 return its value. */
3911 parser::get_ident ()
3913 const cpp_token
*token
= expect (CPP_NAME
);
3914 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3917 /* Eat an identifier token with value S from R. */
3920 parser::eat_ident (const char *s
)
3922 const cpp_token
*token
= peek ();
3923 const char *t
= get_ident ();
3924 if (strcmp (s
, t
) != 0)
3925 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3929 /* Read the next token from R and assert it is of type CPP_NUMBER and
3930 return its value. */
3933 parser::get_number ()
3935 const cpp_token
*token
= expect (CPP_NUMBER
);
3936 return (const char *)token
->val
.str
.text
;
3939 /* Return a capture ID that can be used internally. */
3942 parser::get_internal_capture_id ()
3944 unsigned newid
= capture_ids
->elements ();
3945 /* Big enough for a 32-bit UINT_MAX plus prefix. */
3948 sprintf (id
, "__%u", newid
);
3949 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3951 fatal ("reserved capture id '%s' already used", id
);
3955 /* Record an operator-list use for transparent for handling. */
3958 parser::record_operlist (source_location loc
, user_id
*p
)
3960 if (!oper_lists_set
->add (p
))
3962 if (!oper_lists
.is_empty ()
3963 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3964 fatal_at (loc
, "User-defined operator list does not have the "
3965 "same number of entries as others used in the pattern");
3966 oper_lists
.safe_push (p
);
3970 /* Parse the operator ID, special-casing convert?, convert1? and
3974 parser::parse_operation ()
3976 const cpp_token
*id_tok
= peek ();
3977 const char *id
= get_ident ();
3978 const cpp_token
*token
= peek ();
3979 if (strcmp (id
, "convert0") == 0)
3980 fatal_at (id_tok
, "use 'convert?' here");
3981 else if (strcmp (id
, "view_convert0") == 0)
3982 fatal_at (id_tok
, "use 'view_convert?' here");
3983 if (token
->type
== CPP_QUERY
3984 && !(token
->flags
& PREV_WHITE
))
3986 if (strcmp (id
, "convert") == 0)
3988 else if (strcmp (id
, "convert1") == 0)
3990 else if (strcmp (id
, "convert2") == 0)
3992 else if (strcmp (id
, "view_convert") == 0)
3993 id
= "view_convert0";
3994 else if (strcmp (id
, "view_convert1") == 0)
3996 else if (strcmp (id
, "view_convert2") == 0)
3999 fatal_at (id_tok
, "non-convert operator conditionalized");
4001 if (!parsing_match_operand
)
4002 fatal_at (id_tok
, "conditional convert can only be used in "
4003 "match expression");
4004 eat_token (CPP_QUERY
);
4006 else if (strcmp (id
, "convert1") == 0
4007 || strcmp (id
, "convert2") == 0
4008 || strcmp (id
, "view_convert1") == 0
4009 || strcmp (id
, "view_convert2") == 0)
4010 fatal_at (id_tok
, "expected '?' after conditional operator");
4011 id_base
*op
= get_operator (id
);
4013 fatal_at (id_tok
, "unknown operator %s", id
);
4015 user_id
*p
= dyn_cast
<user_id
*> (op
);
4016 if (p
&& p
->is_oper_list
)
4018 if (active_fors
.length() == 0)
4019 record_operlist (id_tok
->src_loc
, p
);
4021 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
4027 capture = '@'<number> */
4030 parser::parse_capture (operand
*op
, bool require_existing
)
4032 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4033 const cpp_token
*token
= peek ();
4034 const char *id
= NULL
;
4035 bool value_match
= false;
4036 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4037 if (token
->type
== CPP_ATSIGN
4038 && ! (token
->flags
& PREV_WHITE
)
4039 && parsing_match_operand
)
4041 eat_token (CPP_ATSIGN
);
4045 if (token
->type
== CPP_NUMBER
)
4047 else if (token
->type
== CPP_NAME
)
4050 fatal_at (token
, "expected number or identifier");
4051 unsigned next_id
= capture_ids
->elements ();
4053 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4056 if (require_existing
)
4057 fatal_at (src_loc
, "unknown capture id");
4060 return new capture (src_loc
, num
, op
, value_match
);
4063 /* Parse an expression
4064 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4067 parser::parse_expr ()
4069 const cpp_token
*token
= peek ();
4070 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4073 bool is_commutative
= false;
4074 bool force_capture
= false;
4075 const char *expr_type
= NULL
;
4077 if (token
->type
== CPP_COLON
4078 && !(token
->flags
& PREV_WHITE
))
4080 eat_token (CPP_COLON
);
4082 if (token
->type
== CPP_NAME
4083 && !(token
->flags
& PREV_WHITE
))
4085 const char *s
= get_ident ();
4086 if (!parsing_match_operand
)
4096 = dyn_cast
<operator_id
*> (e
->operation
))
4098 if (!commutative_tree_code (p
->code
)
4099 && !comparison_code_p (p
->code
))
4100 fatal_at (token
, "operation is not commutative");
4102 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4103 for (unsigned i
= 0;
4104 i
< p
->substitutes
.length (); ++i
)
4107 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4109 if (!commutative_tree_code (q
->code
)
4110 && !comparison_code_p (q
->code
))
4111 fatal_at (token
, "operation %s is not "
4112 "commutative", q
->id
);
4115 is_commutative
= true;
4117 else if (*sp
== 'C')
4118 is_commutative
= true;
4119 else if (*sp
== 's')
4121 e
->force_single_use
= true;
4122 force_capture
= true;
4125 fatal_at (token
, "flag %c not recognized", *sp
);
4132 fatal_at (token
, "expected flag or type specifying identifier");
4135 if (token
->type
== CPP_ATSIGN
4136 && !(token
->flags
& PREV_WHITE
))
4137 op
= parse_capture (e
, false);
4138 else if (force_capture
)
4140 unsigned num
= get_internal_capture_id ();
4141 op
= new capture (token
->src_loc
, num
, e
, false);
4147 const cpp_token
*token
= peek ();
4148 if (token
->type
== CPP_CLOSE_PAREN
)
4150 if (e
->operation
->nargs
!= -1
4151 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4152 fatal_at (token
, "'%s' expects %u operands, not %u",
4153 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4156 if (e
->ops
.length () == 2)
4157 e
->is_commutative
= true;
4159 fatal_at (token
, "only binary operators or function with "
4160 "two arguments can be marked commutative");
4162 e
->expr_type
= expr_type
;
4165 else if (!(token
->flags
& PREV_WHITE
))
4166 fatal_at (token
, "expected expression operand");
4168 e
->append_op (parse_op ());
4173 /* Lex native C code delimited by START recording the preprocessing tokens
4174 for later processing.
4175 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4178 parser::parse_c_expr (cpp_ttype start
)
4180 const cpp_token
*token
;
4183 vec
<cpp_token
> code
= vNULL
;
4184 unsigned nr_stmts
= 0;
4185 source_location loc
= eat_token (start
)->src_loc
;
4186 if (start
== CPP_OPEN_PAREN
)
4187 end
= CPP_CLOSE_PAREN
;
4188 else if (start
== CPP_OPEN_BRACE
)
4189 end
= CPP_CLOSE_BRACE
;
4197 /* Count brace pairs to find the end of the expr to match. */
4198 if (token
->type
== start
)
4200 else if (token
->type
== end
4203 else if (token
->type
== CPP_EOF
)
4204 fatal_at (token
, "unexpected end of file");
4206 /* This is a lame way of counting the number of statements. */
4207 if (token
->type
== CPP_SEMICOLON
)
4210 /* If this is possibly a user-defined identifier mark it used. */
4211 if (token
->type
== CPP_NAME
)
4213 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4214 (token
->val
.node
.node
)->ident
.str
);
4216 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4217 record_operlist (token
->src_loc
, p
);
4220 /* Record the token. */
4221 code
.safe_push (*token
);
4224 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4227 /* Parse an operand which is either an expression, a predicate or
4228 a standalone capture.
4229 op = predicate | expr | c_expr | capture */
4234 const cpp_token
*token
= peek ();
4235 struct operand
*op
= NULL
;
4236 if (token
->type
== CPP_OPEN_PAREN
)
4238 eat_token (CPP_OPEN_PAREN
);
4240 eat_token (CPP_CLOSE_PAREN
);
4242 else if (token
->type
== CPP_OPEN_BRACE
)
4244 op
= parse_c_expr (CPP_OPEN_BRACE
);
4248 /* Remaining ops are either empty or predicates */
4249 if (token
->type
== CPP_NAME
)
4251 const char *id
= get_ident ();
4252 id_base
*opr
= get_operator (id
);
4254 fatal_at (token
, "expected predicate name");
4255 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4257 if (code
->nargs
!= 0)
4258 fatal_at (token
, "using an operator with operands as predicate");
4259 /* Parse the zero-operand operator "predicates" as
4261 op
= new expr (opr
, token
->src_loc
);
4263 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4265 if (code
->nargs
!= 0)
4266 fatal_at (token
, "using an operator with operands as predicate");
4267 /* Parse the zero-operand operator "predicates" as
4269 op
= new expr (opr
, token
->src_loc
);
4271 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4272 op
= new predicate (p
, token
->src_loc
);
4274 fatal_at (token
, "using an unsupported operator as predicate");
4275 if (!parsing_match_operand
)
4276 fatal_at (token
, "predicates are only allowed in match expression");
4278 if (token
->flags
& PREV_WHITE
)
4281 else if (token
->type
!= CPP_COLON
4282 && token
->type
!= CPP_ATSIGN
)
4283 fatal_at (token
, "expected expression or predicate");
4284 /* optionally followed by a capture and a predicate. */
4285 if (token
->type
== CPP_COLON
)
4286 fatal_at (token
, "not implemented: predicate on leaf operand");
4287 if (token
->type
== CPP_ATSIGN
)
4288 op
= parse_capture (op
, !parsing_match_operand
);
4294 /* Create a new simplify from the current parsing state and MATCH,
4295 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4298 parser::push_simplify (simplify::simplify_kind kind
,
4299 vec
<simplify
*>& simplifiers
,
4300 operand
*match
, operand
*result
)
4302 /* Build and push a temporary for operator list uses in expressions. */
4303 if (!oper_lists
.is_empty ())
4304 active_fors
.safe_push (oper_lists
);
4306 simplifiers
.safe_push
4307 (new simplify (kind
, match
, result
,
4308 active_fors
.copy (), capture_ids
));
4310 if (!oper_lists
.is_empty ())
4315 <result-op> = <op> | <if> | <with>
4316 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4317 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4321 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4323 const cpp_token
*token
= peek ();
4324 if (token
->type
!= CPP_OPEN_PAREN
)
4327 eat_token (CPP_OPEN_PAREN
);
4328 if (peek_ident ("if"))
4331 if_expr
*ife
= new if_expr (token
->src_loc
);
4332 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4333 if (peek ()->type
== CPP_OPEN_PAREN
)
4335 ife
->trueexpr
= parse_result (result
, matcher
);
4336 if (peek ()->type
== CPP_OPEN_PAREN
)
4337 ife
->falseexpr
= parse_result (result
, matcher
);
4338 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4339 ife
->falseexpr
= parse_op ();
4341 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4343 ife
->trueexpr
= parse_op ();
4344 if (peek ()->type
== CPP_OPEN_PAREN
)
4345 ife
->falseexpr
= parse_result (result
, matcher
);
4346 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4347 ife
->falseexpr
= parse_op ();
4349 /* If this if is immediately closed then it contains a
4350 manual matcher or is part of a predicate definition. */
4351 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4354 fatal_at (peek (), "manual transform not implemented");
4355 ife
->trueexpr
= result
;
4357 eat_token (CPP_CLOSE_PAREN
);
4360 else if (peek_ident ("with"))
4363 with_expr
*withe
= new with_expr (token
->src_loc
);
4364 /* Parse (with c-expr expr) as (if-with (true) expr). */
4365 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4366 withe
->with
->nr_stmts
= 0;
4367 withe
->subexpr
= parse_result (result
, matcher
);
4368 eat_token (CPP_CLOSE_PAREN
);
4371 else if (peek_ident ("switch"))
4373 token
= eat_ident ("switch");
4374 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4376 if_expr
*ife
= new if_expr (ifloc
);
4378 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4379 if (peek ()->type
== CPP_OPEN_PAREN
)
4380 ife
->trueexpr
= parse_result (result
, matcher
);
4382 ife
->trueexpr
= parse_op ();
4383 eat_token (CPP_CLOSE_PAREN
);
4384 if (peek ()->type
!= CPP_OPEN_PAREN
4385 || !peek_ident ("if", 2))
4386 fatal_at (token
, "switch can be implemented with a single if");
4387 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4389 if (peek ()->type
== CPP_OPEN_PAREN
)
4391 if (peek_ident ("if", 2))
4393 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4395 ife
->falseexpr
= new if_expr (ifloc
);
4396 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4397 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4398 if (peek ()->type
== CPP_OPEN_PAREN
)
4399 ife
->trueexpr
= parse_result (result
, matcher
);
4401 ife
->trueexpr
= parse_op ();
4402 eat_token (CPP_CLOSE_PAREN
);
4406 /* switch default clause */
4407 ife
->falseexpr
= parse_result (result
, matcher
);
4408 eat_token (CPP_CLOSE_PAREN
);
4414 /* switch default clause */
4415 ife
->falseexpr
= parse_op ();
4416 eat_token (CPP_CLOSE_PAREN
);
4420 eat_token (CPP_CLOSE_PAREN
);
4425 operand
*op
= result
;
4428 eat_token (CPP_CLOSE_PAREN
);
4434 simplify = 'simplify' <expr> <result-op>
4436 match = 'match' <ident> <expr> [<result-op>]
4437 and fill SIMPLIFIERS with the results. */
4440 parser::parse_simplify (simplify::simplify_kind kind
,
4441 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4444 /* Reset the capture map. */
4446 capture_ids
= new cid_map_t
;
4447 /* Reset oper_lists and set. */
4448 hash_set
<user_id
*> olist
;
4449 oper_lists_set
= &olist
;
4452 const cpp_token
*loc
= peek ();
4453 parsing_match_operand
= true;
4454 struct operand
*match
= parse_op ();
4455 finish_match_operand (match
);
4456 parsing_match_operand
= false;
4457 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4458 fatal_at (loc
, "outermost expression cannot be captured");
4459 if (match
->type
== operand::OP_EXPR
4460 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4461 fatal_at (loc
, "outermost expression cannot be a predicate");
4463 /* Splice active_ifs onto result and continue parsing the
4465 if_expr
*active_if
= NULL
;
4466 for (int i
= active_ifs
.length (); i
> 0; --i
)
4468 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4469 ifc
->cond
= active_ifs
[i
-1];
4470 ifc
->trueexpr
= active_if
;
4473 if_expr
*outermost_if
= active_if
;
4474 while (active_if
&& active_if
->trueexpr
)
4475 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4477 const cpp_token
*token
= peek ();
4479 /* If this if is immediately closed then it is part of a predicate
4480 definition. Push it. */
4481 if (token
->type
== CPP_CLOSE_PAREN
)
4484 fatal_at (token
, "expected transform expression");
4487 active_if
->trueexpr
= result
;
4488 result
= outermost_if
;
4490 push_simplify (kind
, simplifiers
, match
, result
);
4494 operand
*tem
= parse_result (result
, matcher
);
4497 active_if
->trueexpr
= tem
;
4498 result
= outermost_if
;
4503 push_simplify (kind
, simplifiers
, match
, result
);
4506 /* Parsing of the outer control structures. */
4508 /* Parse a for expression
4509 for = '(' 'for' <subst>... <pattern> ')'
4510 subst = <ident> '(' <ident>... ')' */
4513 parser::parse_for (source_location
)
4515 auto_vec
<const cpp_token
*> user_id_tokens
;
4516 vec
<user_id
*> user_ids
= vNULL
;
4517 const cpp_token
*token
;
4518 unsigned min_n_opers
= 0, max_n_opers
= 0;
4523 if (token
->type
!= CPP_NAME
)
4526 /* Insert the user defined operators into the operator hash. */
4527 const char *id
= get_ident ();
4528 if (get_operator (id
, true) != NULL
)
4529 fatal_at (token
, "operator already defined");
4530 user_id
*op
= new user_id (id
);
4531 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4533 user_ids
.safe_push (op
);
4534 user_id_tokens
.safe_push (token
);
4536 eat_token (CPP_OPEN_PAREN
);
4539 while ((token
= peek_ident ()) != 0)
4541 const char *oper
= get_ident ();
4542 id_base
*idb
= get_operator (oper
, true);
4544 fatal_at (token
, "no such operator '%s'", oper
);
4545 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4546 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4547 || *idb
== VIEW_CONVERT2
)
4548 fatal_at (token
, "conditional operators cannot be used inside for");
4552 else if (idb
->nargs
== -1)
4554 else if (idb
->nargs
!= arity
)
4555 fatal_at (token
, "operator '%s' with arity %d does not match "
4556 "others with arity %d", oper
, idb
->nargs
, arity
);
4558 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4561 if (p
->is_oper_list
)
4562 op
->substitutes
.safe_splice (p
->substitutes
);
4564 fatal_at (token
, "iterator cannot be used as operator-list");
4567 op
->substitutes
.safe_push (idb
);
4570 token
= expect (CPP_CLOSE_PAREN
);
4572 unsigned nsubstitutes
= op
->substitutes
.length ();
4573 if (nsubstitutes
== 0)
4574 fatal_at (token
, "A user-defined operator must have at least "
4575 "one substitution");
4576 if (max_n_opers
== 0)
4578 min_n_opers
= nsubstitutes
;
4579 max_n_opers
= nsubstitutes
;
4583 if (nsubstitutes
% min_n_opers
!= 0
4584 && min_n_opers
% nsubstitutes
!= 0)
4585 fatal_at (token
, "All user-defined identifiers must have a "
4586 "multiple number of operator substitutions of the "
4587 "smallest number of substitutions");
4588 if (nsubstitutes
< min_n_opers
)
4589 min_n_opers
= nsubstitutes
;
4590 else if (nsubstitutes
> max_n_opers
)
4591 max_n_opers
= nsubstitutes
;
4595 unsigned n_ids
= user_ids
.length ();
4597 fatal_at (token
, "for requires at least one user-defined identifier");
4600 if (token
->type
== CPP_CLOSE_PAREN
)
4601 fatal_at (token
, "no pattern defined in for");
4603 active_fors
.safe_push (user_ids
);
4607 if (token
->type
== CPP_CLOSE_PAREN
)
4613 /* Remove user-defined operators from the hash again. */
4614 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4616 if (!user_ids
[i
]->used
)
4617 warning_at (user_id_tokens
[i
],
4618 "operator %s defined but not used", user_ids
[i
]->id
);
4619 operators
->remove_elt (user_ids
[i
]);
4623 /* Parse an identifier associated with a list of operators.
4624 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4627 parser::parse_operator_list (source_location
)
4629 const cpp_token
*token
= peek ();
4630 const char *id
= get_ident ();
4632 if (get_operator (id
, true) != 0)
4633 fatal_at (token
, "operator %s already defined", id
);
4635 user_id
*op
= new user_id (id
, true);
4638 while ((token
= peek_ident ()) != 0)
4641 const char *oper
= get_ident ();
4642 id_base
*idb
= get_operator (oper
, true);
4645 fatal_at (token
, "no such operator '%s'", oper
);
4649 else if (idb
->nargs
== -1)
4651 else if (arity
!= idb
->nargs
)
4652 fatal_at (token
, "operator '%s' with arity %d does not match "
4653 "others with arity %d", oper
, idb
->nargs
, arity
);
4655 /* We allow composition of multiple operator lists. */
4656 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4657 op
->substitutes
.safe_splice (p
->substitutes
);
4659 op
->substitutes
.safe_push (idb
);
4662 // Check that there is no junk after id-list
4664 if (token
->type
!= CPP_CLOSE_PAREN
)
4665 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4667 if (op
->substitutes
.length () == 0)
4668 fatal_at (token
, "operator-list cannot be empty");
4671 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4675 /* Parse an outer if expression.
4676 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4679 parser::parse_if (source_location
)
4681 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4683 const cpp_token
*token
= peek ();
4684 if (token
->type
== CPP_CLOSE_PAREN
)
4685 fatal_at (token
, "no pattern defined in if");
4687 active_ifs
.safe_push (ifexpr
);
4690 const cpp_token
*token
= peek ();
4691 if (token
->type
== CPP_CLOSE_PAREN
)
4699 /* Parse a list of predefined predicate identifiers.
4700 preds = '(' 'define_predicates' <ident>... ')' */
4703 parser::parse_predicates (source_location
)
4707 const cpp_token
*token
= peek ();
4708 if (token
->type
!= CPP_NAME
)
4711 add_predicate (get_ident ());
4716 /* Parse outer control structures.
4717 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4720 parser::parse_pattern ()
4722 /* All clauses start with '('. */
4723 eat_token (CPP_OPEN_PAREN
);
4724 const cpp_token
*token
= peek ();
4725 const char *id
= get_ident ();
4726 if (strcmp (id
, "simplify") == 0)
4728 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4731 else if (strcmp (id
, "match") == 0)
4733 bool with_args
= false;
4734 source_location e_loc
= peek ()->src_loc
;
4735 if (peek ()->type
== CPP_OPEN_PAREN
)
4737 eat_token (CPP_OPEN_PAREN
);
4740 const char *name
= get_ident ();
4741 id_base
*id
= get_operator (name
);
4745 p
= add_predicate (name
);
4746 user_predicates
.safe_push (p
);
4748 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4751 fatal_at (token
, "cannot add a match to a non-predicate ID");
4752 /* Parse (match <id> <arg>... (match-expr)) here. */
4756 capture_ids
= new cid_map_t
;
4757 e
= new expr (p
, e_loc
);
4758 while (peek ()->type
== CPP_ATSIGN
)
4759 e
->append_op (parse_capture (NULL
, false));
4760 eat_token (CPP_CLOSE_PAREN
);
4763 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4764 || (!e
&& p
->nargs
!= 0)))
4765 fatal_at (token
, "non-matching number of match operands");
4766 p
->nargs
= e
? e
->ops
.length () : 0;
4767 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4770 else if (strcmp (id
, "for") == 0)
4771 parse_for (token
->src_loc
);
4772 else if (strcmp (id
, "if") == 0)
4773 parse_if (token
->src_loc
);
4774 else if (strcmp (id
, "define_predicates") == 0)
4776 if (active_ifs
.length () > 0
4777 || active_fors
.length () > 0)
4778 fatal_at (token
, "define_predicates inside if or for is not supported");
4779 parse_predicates (token
->src_loc
);
4781 else if (strcmp (id
, "define_operator_list") == 0)
4783 if (active_ifs
.length () > 0
4784 || active_fors
.length () > 0)
4785 fatal_at (token
, "operator-list inside if or for is not supported");
4786 parse_operator_list (token
->src_loc
);
4789 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4790 active_ifs
.length () == 0 && active_fors
.length () == 0
4791 ? "'define_predicates', " : "");
4793 eat_token (CPP_CLOSE_PAREN
);
4796 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4800 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4805 if (capture
*c
= dyn_cast
<capture
*> (op
))
4807 cpts
[c
->where
].safe_push (c
);
4808 walk_captures (c
->what
, cpts
);
4810 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4811 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4812 walk_captures (e
->ops
[i
], cpts
);
4815 /* Finish up OP which is a match operand. */
4818 parser::finish_match_operand (operand
*op
)
4820 /* Look for matching captures, diagnose mis-uses of @@ and apply
4821 early lowering and distribution of value_match. */
4822 auto_vec
<vec
<capture
*> > cpts
;
4823 cpts
.safe_grow_cleared (capture_ids
->elements ());
4824 walk_captures (op
, cpts
);
4825 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4827 capture
*value_match
= NULL
;
4828 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4830 if (cpts
[i
][j
]->value_match
)
4833 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4834 value_match
= cpts
[i
][j
];
4837 if (cpts
[i
].length () == 1 && value_match
)
4838 fatal_at (value_match
->location
, "@@ without a matching capture");
4841 /* Duplicate prevailing capture with the existing ID, create
4842 a fake ID and rewrite all captures to use it. This turns
4843 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4844 value_match
->what
= new capture (value_match
->location
,
4846 value_match
->what
, false);
4847 /* Create a fake ID and rewrite all captures to use it. */
4848 unsigned newid
= get_internal_capture_id ();
4849 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4851 cpts
[i
][j
]->where
= newid
;
4852 cpts
[i
][j
]->value_match
= true;
4859 /* Main entry of the parser. Repeatedly parse outer control structures. */
4861 parser::parser (cpp_reader
*r_
)
4865 active_fors
= vNULL
;
4866 simplifiers
= vNULL
;
4867 oper_lists_set
= NULL
;
4870 user_predicates
= vNULL
;
4871 parsing_match_operand
= false;
4873 const cpp_token
*token
= next ();
4874 while (token
->type
!= CPP_EOF
)
4876 _cpp_backup_tokens (r
, 1);
4883 /* Helper for the linemap code. */
4886 round_alloc_size (size_t s
)
4892 /* The genmatch generator progam. It reads from a pattern description
4893 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4896 main (int argc
, char **argv
)
4900 progname
= "genmatch";
4906 char *input
= argv
[argc
-1];
4907 for (int i
= 1; i
< argc
- 1; ++i
)
4909 if (strcmp (argv
[i
], "--gimple") == 0)
4911 else if (strcmp (argv
[i
], "--generic") == 0)
4913 else if (strcmp (argv
[i
], "-v") == 0)
4915 else if (strcmp (argv
[i
], "-vv") == 0)
4919 fprintf (stderr
, "Usage: genmatch "
4920 "[--gimple] [--generic] [-v[v]] input\n");
4925 line_table
= XCNEW (struct line_maps
);
4926 linemap_init (line_table
, 0);
4927 line_table
->reallocator
= xrealloc
;
4928 line_table
->round_alloc_size
= round_alloc_size
;
4930 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4931 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4932 cb
->error
= error_cb
;
4934 /* Add the build directory to the #include "" search path. */
4935 cpp_dir
*dir
= XCNEW (cpp_dir
);
4936 dir
->name
= getpwd ();
4938 dir
->name
= ASTRDUP (".");
4939 cpp_set_include_chains (r
, dir
, NULL
, false);
4941 if (!cpp_read_main_file (r
, input
))
4943 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4944 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4946 null_id
= new id_base (id_base::NULL_ID
, "null");
4948 /* Pre-seed operators. */
4949 operators
= new hash_table
<id_base
> (1024);
4950 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4951 add_operator (SYM, # SYM, # TYPE, NARGS);
4952 #define END_OF_BASE_TREE_CODES
4954 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
4955 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
4956 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
4957 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
4958 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
4959 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
4960 #undef END_OF_BASE_TREE_CODES
4963 /* Pre-seed builtin functions.
4964 ??? Cannot use N (name) as that is targetm.emultls.get_address
4965 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4966 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4967 add_function (ENUM, "CFN_" # ENUM);
4968 #include "builtins.def"
4970 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
4971 add_function (IFN_##CODE, "CFN_" #CODE);
4972 #include "internal-fn.def"
4978 write_header (stdout
, "gimple-match-head.c");
4980 write_header (stdout
, "generic-match-head.c");
4982 /* Go over all predicates defined with patterns and perform
4983 lowering and code generation. */
4984 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4986 predicate_id
*pred
= p
.user_predicates
[i
];
4987 lower (pred
->matchers
, gimple
);
4990 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4991 print_matches (pred
->matchers
[i
]);
4994 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4995 dt
.insert (pred
->matchers
[i
], i
);
5000 write_predicate (stdout
, pred
, dt
, gimple
);
5003 /* Lower the main simplifiers and generate code for them. */
5004 lower (p
.simplifiers
, gimple
);
5007 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5008 print_matches (p
.simplifiers
[i
]);
5011 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5012 dt
.insert (p
.simplifiers
[i
], i
);
5017 dt
.gen (stdout
, gimple
);
5020 cpp_finish (r
, NULL
);