1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2016 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
);
199 fprintf (f
, "%s:%d", file
, loc
.line
);
202 /* Other gen programs really output line directives here, at least for
203 development it's right now more convenient to have line information
204 from the generated file. Still keep the directives as comment for now
205 to easily back-point to the meta-description. */
206 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
210 /* Pull in tree codes and builtin function codes from their
213 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
226 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
227 enum built_in_function
{
228 #include "builtins.def"
232 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
234 #include "internal-fn.def"
238 /* Return true if CODE represents a commutative tree code. Otherwise
241 commutative_tree_code (enum tree_code code
)
247 case MULT_HIGHPART_EXPR
:
262 case WIDEN_MULT_EXPR
:
263 case VEC_WIDEN_MULT_HI_EXPR
:
264 case VEC_WIDEN_MULT_LO_EXPR
:
265 case VEC_WIDEN_MULT_EVEN_EXPR
:
266 case VEC_WIDEN_MULT_ODD_EXPR
:
275 /* Return true if CODE represents a ternary tree code for which the
276 first two operands are commutative. Otherwise return false. */
278 commutative_ternary_tree_code (enum tree_code code
)
282 case WIDEN_MULT_PLUS_EXPR
:
283 case WIDEN_MULT_MINUS_EXPR
:
294 /* Return true if CODE is a comparison. */
297 comparison_code_p (enum tree_code code
)
324 /* Base class for all identifiers the parser knows. */
326 struct id_base
: nofree_ptr_hash
<id_base
>
328 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
330 id_base (id_kind
, const char *, int = -1);
336 /* hash_table support. */
337 static inline hashval_t
hash (const id_base
*);
338 static inline int equal (const id_base
*, const id_base
*);
342 id_base::hash (const id_base
*op
)
348 id_base::equal (const id_base
*op1
,
351 return (op1
->hashval
== op2
->hashval
352 && strcmp (op1
->id
, op2
->id
) == 0);
355 /* The special id "null", which matches nothing. */
356 static id_base
*null_id
;
358 /* Hashtable of known pattern operators. This is pre-seeded from
359 all known tree codes and all known builtin function ids. */
360 static hash_table
<id_base
> *operators
;
362 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
367 hashval
= htab_hash_string (id
);
370 /* Identifier that maps to a tree code. */
372 struct operator_id
: public id_base
374 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
376 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
381 /* Identifier that maps to a builtin or internal function code. */
383 struct fn_id
: public id_base
385 fn_id (enum built_in_function fn_
, const char *id_
)
386 : id_base (id_base::FN
, id_
), fn (fn_
) {}
387 fn_id (enum internal_fn fn_
, const char *id_
)
388 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
394 /* Identifier that maps to a user-defined predicate. */
396 struct predicate_id
: public id_base
398 predicate_id (const char *id_
)
399 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
400 vec
<simplify
*> matchers
;
403 /* Identifier that maps to a operator defined by a 'for' directive. */
405 struct user_id
: public id_base
407 user_id (const char *id_
, bool is_oper_list_
= false)
408 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
409 used (false), is_oper_list (is_oper_list_
) {}
410 vec
<id_base
*> substitutes
;
418 is_a_helper
<fn_id
*>::test (id_base
*id
)
420 return id
->kind
== id_base::FN
;
426 is_a_helper
<operator_id
*>::test (id_base
*id
)
428 return id
->kind
== id_base::CODE
;
434 is_a_helper
<predicate_id
*>::test (id_base
*id
)
436 return id
->kind
== id_base::PREDICATE
;
442 is_a_helper
<user_id
*>::test (id_base
*id
)
444 return id
->kind
== id_base::USER
;
447 /* Add a predicate identifier to the hash. */
449 static predicate_id
*
450 add_predicate (const char *id
)
452 predicate_id
*p
= new predicate_id (id
);
453 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
455 fatal ("duplicate id definition");
460 /* Add a tree code identifier to the hash. */
463 add_operator (enum tree_code code
, const char *id
,
464 const char *tcc
, unsigned nargs
)
466 if (strcmp (tcc
, "tcc_unary") != 0
467 && strcmp (tcc
, "tcc_binary") != 0
468 && strcmp (tcc
, "tcc_comparison") != 0
469 && strcmp (tcc
, "tcc_expression") != 0
470 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
471 && strcmp (tcc
, "tcc_reference") != 0
472 /* To have INTEGER_CST and friends as "predicate operators". */
473 && strcmp (tcc
, "tcc_constant") != 0
474 /* And allow CONSTRUCTOR for vector initializers. */
475 && !(code
== CONSTRUCTOR
)
476 /* Allow SSA_NAME as predicate operator. */
477 && !(code
== SSA_NAME
))
479 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
480 if (code
== ADDR_EXPR
)
482 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
483 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
485 fatal ("duplicate id definition");
489 /* Add a built-in or internal function identifier to the hash. ID is
490 the name of its CFN_* enumeration value. */
492 template <typename T
>
494 add_function (T code
, const char *id
)
496 fn_id
*fn
= new fn_id (code
, id
);
497 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
499 fatal ("duplicate id definition");
503 /* Helper for easy comparing ID with tree code CODE. */
506 operator==(id_base
&id
, enum tree_code code
)
508 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
509 return oid
->code
== code
;
513 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
516 get_operator (const char *id
, bool allow_null
= false)
518 if (allow_null
&& strcmp (id
, "null") == 0)
521 id_base
tem (id_base::CODE
, id
);
523 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
526 /* If this is a user-defined identifier track whether it was used. */
527 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
533 bool all_upper
= true;
534 bool all_lower
= true;
535 for (unsigned int i
= 0; id
[i
]; ++i
)
538 else if (ISLOWER (id
[i
]))
542 /* Try in caps with _EXPR appended. */
543 id2
= ACONCAT ((id
, "_EXPR", NULL
));
544 for (unsigned int i
= 0; id2
[i
]; ++i
)
545 id2
[i
] = TOUPPER (id2
[i
]);
547 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
548 /* Try CFN_ instead of IFN_. */
549 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
550 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
551 /* Try prepending CFN_. */
552 id2
= ACONCAT (("CFN_", id
, NULL
));
556 new (&tem
) id_base (id_base::CODE
, id2
);
557 return operators
->find_with_hash (&tem
, tem
.hashval
);
560 /* Return the comparison operators that results if the operands are
561 swapped. This is safe for floating-point. */
564 swap_tree_comparison (operator_id
*p
)
576 return get_operator ("LT_EXPR");
578 return get_operator ("LE_EXPR");
580 return get_operator ("GT_EXPR");
582 return get_operator ("GE_EXPR");
584 return get_operator ("UNLT_EXPR");
586 return get_operator ("UNLE_EXPR");
588 return get_operator ("UNGT_EXPR");
590 return get_operator ("UNGE_EXPR");
596 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
599 /* The AST produced by parsing of the pattern definitions. */
604 /* The base class for operands. */
607 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
608 operand (enum op_type type_
, source_location loc_
)
609 : type (type_
), location (loc_
) {}
611 source_location location
;
612 virtual void gen_transform (FILE *, int, const char *, bool, int,
613 const char *, capture_info
*,
616 { gcc_unreachable (); }
619 /* A predicate operand. Predicates are leafs in the AST. */
621 struct predicate
: public operand
623 predicate (predicate_id
*p_
, source_location loc
)
624 : operand (OP_PREDICATE
, loc
), p (p_
) {}
628 /* An operand that constitutes an expression. Expressions include
629 function calls and user-defined predicate invocations. */
631 struct expr
: public operand
633 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
634 : operand (OP_EXPR
, loc
), operation (operation_
),
635 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
636 is_generic (false), force_single_use (false) {}
638 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
639 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
640 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
641 void append_op (operand
*op
) { ops
.safe_push (op
); }
642 /* The operator and its operands. */
645 /* An explicitely specified type - used exclusively for conversions. */
646 const char *expr_type
;
647 /* Whether the operation is to be applied commutatively. This is
648 later lowered to two separate patterns. */
650 /* Whether the expression is expected to be in GENERIC form. */
652 /* Whether pushing any stmt to the sequence should be conditional
653 on this expression having a single-use. */
654 bool force_single_use
;
655 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
656 const char *, capture_info
*,
657 dt_operand
** = 0, int = 0);
660 /* An operator that is represented by native C code. This is always
661 a leaf operand in the AST. This class is also used to represent
662 the code to be generated for 'if' and 'with' expressions. */
664 struct c_expr
: public operand
666 /* A mapping of an identifier and its replacement. Used to apply
671 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
674 c_expr (cpp_reader
*r_
, source_location loc
,
675 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
676 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
677 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
678 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
679 /* cpplib tokens and state to transform this back to source. */
682 cid_map_t
*capture_ids
;
683 /* The number of statements parsed (well, the number of ';'s). */
685 /* The identifier replacement vector. */
687 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
688 const char *, capture_info
*,
689 dt_operand
** = 0, int = 0);
692 /* A wrapper around another operand that captures its value. */
694 struct capture
: public operand
696 capture (source_location loc
, unsigned where_
, operand
*what_
, bool value_
)
697 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
699 /* Identifier index for the value. */
701 /* Whether in a match of two operands the compare should be for
702 equal values rather than equal atoms (boils down to a type
705 /* The captured value. */
707 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
708 const char *, capture_info
*,
709 dt_operand
** = 0, int = 0);
714 struct if_expr
: public operand
716 if_expr (source_location loc
)
717 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
723 /* with expression. */
725 struct with_expr
: public operand
727 with_expr (source_location loc
)
728 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
736 is_a_helper
<capture
*>::test (operand
*op
)
738 return op
->type
== operand::OP_CAPTURE
;
744 is_a_helper
<predicate
*>::test (operand
*op
)
746 return op
->type
== operand::OP_PREDICATE
;
752 is_a_helper
<c_expr
*>::test (operand
*op
)
754 return op
->type
== operand::OP_C_EXPR
;
760 is_a_helper
<expr
*>::test (operand
*op
)
762 return op
->type
== operand::OP_EXPR
;
768 is_a_helper
<if_expr
*>::test (operand
*op
)
770 return op
->type
== operand::OP_IF
;
776 is_a_helper
<with_expr
*>::test (operand
*op
)
778 return op
->type
== operand::OP_WITH
;
781 /* The main class of a pattern and its transform. This is used to
782 represent both (simplify ...) and (match ...) kinds. The AST
783 duplicates all outer 'if' and 'for' expressions here so each
784 simplify can exist in isolation. */
788 enum simplify_kind
{ SIMPLIFY
, MATCH
};
790 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
791 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
792 : kind (kind_
), match (match_
), result (result_
),
793 for_vec (for_vec_
), for_subst_vec (vNULL
),
794 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
797 /* The expression that is matched against the GENERIC or GIMPLE IL. */
799 /* For a (simplify ...) an expression with ifs and withs with the expression
800 produced when the pattern applies in the leafs.
801 For a (match ...) the leafs are either empty if it is a simple predicate
802 or the single expression specifying the matched operands. */
803 struct operand
*result
;
804 /* Collected 'for' expression operators that have to be replaced
805 in the lowering phase. */
806 vec
<vec
<user_id
*> > for_vec
;
807 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
808 /* A map of capture identifiers to indexes. */
809 cid_map_t
*capture_ids
;
813 /* Debugging routines for dumping the AST. */
816 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
818 if (capture
*c
= dyn_cast
<capture
*> (o
))
820 if (c
->what
&& flattened
== false)
821 print_operand (c
->what
, f
, flattened
);
822 fprintf (f
, "@%u", c
->where
);
825 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
826 fprintf (f
, "%s", p
->p
->id
);
828 else if (is_a
<c_expr
*> (o
))
829 fprintf (f
, "c_expr");
831 else if (expr
*e
= dyn_cast
<expr
*> (o
))
833 if (e
->ops
.length () == 0)
834 fprintf (f
, "%s", e
->operation
->id
);
837 fprintf (f
, "(%s", e
->operation
->id
);
839 if (flattened
== false)
841 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
844 print_operand (e
->ops
[i
], f
, flattened
);
856 print_matches (struct simplify
*s
, FILE *f
= stderr
)
858 fprintf (f
, "for expression: ");
859 print_operand (s
->match
, f
);
866 /* Lowering of commutative operators. */
869 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
870 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
872 if (n
== ops_vector
.length ())
874 vec
<operand
*> xv
= v
.copy ();
875 result
.safe_push (xv
);
879 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
881 v
[n
] = ops_vector
[n
][i
];
882 cartesian_product (ops_vector
, result
, v
, n
+ 1);
886 /* Lower OP to two operands in case it is marked as commutative. */
888 static vec
<operand
*>
889 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
891 vec
<operand
*> ret
= vNULL
;
893 if (capture
*c
= dyn_cast
<capture
*> (op
))
900 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
901 for (unsigned i
= 0; i
< v
.length (); ++i
)
903 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
910 expr
*e
= dyn_cast
<expr
*> (op
);
911 if (!e
|| e
->ops
.length () == 0)
917 vec
< vec
<operand
*> > ops_vector
= vNULL
;
918 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
919 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
921 auto_vec
< vec
<operand
*> > result
;
922 auto_vec
<operand
*> v (e
->ops
.length ());
923 v
.quick_grow_cleared (e
->ops
.length ());
924 cartesian_product (ops_vector
, result
, v
, 0);
927 for (unsigned i
= 0; i
< result
.length (); ++i
)
929 expr
*ne
= new expr (e
);
930 ne
->is_commutative
= false;
931 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
932 ne
->append_op (result
[i
][j
]);
936 if (!e
->is_commutative
)
939 for (unsigned i
= 0; i
< result
.length (); ++i
)
941 expr
*ne
= new expr (e
);
942 if (operator_id
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
944 if (comparison_code_p (p
->code
))
945 ne
->operation
= swap_tree_comparison (p
);
947 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
949 bool found_compare
= false;
950 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
951 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
953 if (comparison_code_p (q
->code
)
954 && swap_tree_comparison (q
) != q
)
956 found_compare
= true;
962 user_id
*newop
= new user_id ("<internal>");
963 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
965 id_base
*subst
= p
->substitutes
[j
];
966 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
968 if (comparison_code_p (q
->code
))
969 subst
= swap_tree_comparison (q
);
971 newop
->substitutes
.safe_push (subst
);
973 ne
->operation
= newop
;
974 /* Search for 'p' inside the for vector and push 'newop'
975 to the same level. */
976 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
977 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
978 if (for_vec
[j
][k
] == p
)
980 for_vec
[j
].safe_push (newop
);
986 ne
->is_commutative
= false;
987 // result[i].length () is 2 since e->operation is binary
988 for (unsigned j
= result
[i
].length (); j
; --j
)
989 ne
->append_op (result
[i
][j
-1]);
996 /* Lower operations marked as commutative in the AST of S and push
997 the resulting patterns to SIMPLIFIERS. */
1000 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1002 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1003 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1005 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1006 s
->for_vec
, s
->capture_ids
);
1007 simplifiers
.safe_push (ns
);
1011 /* Strip conditional conversios using operator OPER from O and its
1012 children if STRIP, else replace them with an unconditional convert. */
1015 lower_opt_convert (operand
*o
, enum tree_code oper
,
1016 enum tree_code to_oper
, bool strip
)
1018 if (capture
*c
= dyn_cast
<capture
*> (o
))
1021 return new capture (c
->location
, c
->where
,
1022 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1028 expr
*e
= dyn_cast
<expr
*> (o
);
1032 if (*e
->operation
== oper
)
1035 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1037 expr
*ne
= new expr (e
);
1038 ne
->operation
= (to_oper
== CONVERT_EXPR
1039 ? get_operator ("CONVERT_EXPR")
1040 : get_operator ("VIEW_CONVERT_EXPR"));
1041 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1045 expr
*ne
= new expr (e
);
1046 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1047 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1052 /* Determine whether O or its children uses the conditional conversion
1056 has_opt_convert (operand
*o
, enum tree_code oper
)
1058 if (capture
*c
= dyn_cast
<capture
*> (o
))
1061 return has_opt_convert (c
->what
, oper
);
1066 expr
*e
= dyn_cast
<expr
*> (o
);
1070 if (*e
->operation
== oper
)
1073 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1074 if (has_opt_convert (e
->ops
[i
], oper
))
1080 /* Lower conditional convert operators in O, expanding it to a vector
1083 static vec
<operand
*>
1084 lower_opt_convert (operand
*o
)
1086 vec
<operand
*> v1
= vNULL
, v2
;
1090 enum tree_code opers
[]
1091 = { CONVERT0
, CONVERT_EXPR
,
1092 CONVERT1
, CONVERT_EXPR
,
1093 CONVERT2
, CONVERT_EXPR
,
1094 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1095 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1096 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1098 /* Conditional converts are lowered to a pattern with the
1099 conversion and one without. The three different conditional
1100 convert codes are lowered separately. */
1102 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1105 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1106 if (has_opt_convert (v1
[j
], opers
[i
]))
1108 v2
.safe_push (lower_opt_convert (v1
[j
],
1109 opers
[i
], opers
[i
+1], false));
1110 v2
.safe_push (lower_opt_convert (v1
[j
],
1111 opers
[i
], opers
[i
+1], true));
1117 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1118 v1
.safe_push (v2
[j
]);
1125 /* Lower conditional convert operators in the AST of S and push
1126 the resulting multiple patterns to SIMPLIFIERS. */
1129 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1131 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1132 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1134 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1135 s
->for_vec
, s
->capture_ids
);
1136 simplifiers
.safe_push (ns
);
1140 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1141 GENERIC and a GIMPLE variant. */
1143 static vec
<operand
*>
1144 lower_cond (operand
*o
)
1146 vec
<operand
*> ro
= vNULL
;
1148 if (capture
*c
= dyn_cast
<capture
*> (o
))
1152 vec
<operand
*> lop
= vNULL
;
1153 lop
= lower_cond (c
->what
);
1155 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1156 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1162 expr
*e
= dyn_cast
<expr
*> (o
);
1163 if (!e
|| e
->ops
.length () == 0)
1169 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1170 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1171 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1173 auto_vec
< vec
<operand
*> > result
;
1174 auto_vec
<operand
*> v (e
->ops
.length ());
1175 v
.quick_grow_cleared (e
->ops
.length ());
1176 cartesian_product (ops_vector
, result
, v
, 0);
1178 for (unsigned i
= 0; i
< result
.length (); ++i
)
1180 expr
*ne
= new expr (e
);
1181 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1182 ne
->append_op (result
[i
][j
]);
1184 /* If this is a COND with a captured expression or an
1185 expression with two operands then also match a GENERIC
1186 form on the compare. */
1187 if ((*e
->operation
== COND_EXPR
1188 || *e
->operation
== VEC_COND_EXPR
)
1189 && ((is_a
<capture
*> (e
->ops
[0])
1190 && as_a
<capture
*> (e
->ops
[0])->what
1191 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1193 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1194 || (is_a
<expr
*> (e
->ops
[0])
1195 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1197 expr
*ne
= new expr (e
);
1198 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1199 ne
->append_op (result
[i
][j
]);
1200 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1202 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1203 expr
*cmp
= new expr (ocmp
);
1204 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1205 cmp
->append_op (ocmp
->ops
[j
]);
1206 cmp
->is_generic
= true;
1207 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1212 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1213 expr
*cmp
= new expr (ocmp
);
1214 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1215 cmp
->append_op (ocmp
->ops
[j
]);
1216 cmp
->is_generic
= true;
1226 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1227 GENERIC and a GIMPLE variant. */
1230 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1232 vec
<operand
*> matchers
= lower_cond (s
->match
);
1233 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1235 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1236 s
->for_vec
, s
->capture_ids
);
1237 simplifiers
.safe_push (ns
);
1241 /* Return true if O refers to ID. */
1244 contains_id (operand
*o
, user_id
*id
)
1246 if (capture
*c
= dyn_cast
<capture
*> (o
))
1247 return c
->what
&& contains_id (c
->what
, id
);
1249 if (expr
*e
= dyn_cast
<expr
*> (o
))
1251 if (e
->operation
== id
)
1253 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1254 if (contains_id (e
->ops
[i
], id
))
1259 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1260 return (contains_id (w
->with
, id
)
1261 || contains_id (w
->subexpr
, id
));
1263 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1264 return (contains_id (ife
->cond
, id
)
1265 || contains_id (ife
->trueexpr
, id
)
1266 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1268 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1269 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1275 /* In AST operand O replace operator ID with operator WITH. */
1278 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1280 /* Deep-copy captures and expressions, replacing operations as
1282 if (capture
*c
= dyn_cast
<capture
*> (o
))
1286 return new capture (c
->location
, c
->where
,
1287 replace_id (c
->what
, id
, with
), c
->value_match
);
1289 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1291 expr
*ne
= new expr (e
);
1292 if (e
->operation
== id
)
1293 ne
->operation
= with
;
1294 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1295 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1298 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1300 with_expr
*nw
= new with_expr (w
->location
);
1301 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1302 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1305 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1307 if_expr
*nife
= new if_expr (ife
->location
);
1308 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1309 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1311 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1315 /* For c_expr we simply record a string replacement table which is
1316 applied at code-generation time. */
1317 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1319 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1320 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1321 return new c_expr (ce
->r
, ce
->location
,
1322 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1328 /* Return true if the binary operator OP is ok for delayed substitution
1329 during for lowering. */
1332 binary_ok (operator_id
*op
)
1339 case TRUNC_DIV_EXPR
:
1341 case FLOOR_DIV_EXPR
:
1342 case ROUND_DIV_EXPR
:
1343 case TRUNC_MOD_EXPR
:
1345 case FLOOR_MOD_EXPR
:
1346 case ROUND_MOD_EXPR
:
1348 case EXACT_DIV_EXPR
:
1360 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1363 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1365 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1366 unsigned worklist_start
= 0;
1367 auto_vec
<simplify
*> worklist
;
1368 worklist
.safe_push (sin
);
1370 /* Lower each recorded for separately, operating on the
1371 set of simplifiers created by the previous one.
1372 Lower inner-to-outer so inner for substitutes can refer
1373 to operators replaced by outer fors. */
1374 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1376 vec
<user_id
*>& ids
= for_vec
[fi
];
1377 unsigned n_ids
= ids
.length ();
1378 unsigned max_n_opers
= 0;
1379 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1380 for (unsigned i
= 0; i
< n_ids
; ++i
)
1382 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1383 max_n_opers
= ids
[i
]->substitutes
.length ();
1384 /* Require that all substitutes are of the same kind so that
1385 if we delay substitution to the result op code generation
1386 can look at the first substitute for deciding things like
1387 types of operands. */
1388 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1389 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1390 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1391 can_delay_subst
= false;
1392 else if (operator_id
*op
1393 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1396 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1397 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1398 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1400 /* Unfortunately we can't just allow all tcc_binary. */
1401 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1402 && strcmp (op0
->tcc
, "tcc_binary") == 0
1406 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1407 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1408 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1409 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1412 can_delay_subst
= false;
1414 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1417 can_delay_subst
= false;
1420 unsigned worklist_end
= worklist
.length ();
1421 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1423 simplify
*s
= worklist
[si
];
1424 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1426 operand
*match_op
= s
->match
;
1427 operand
*result_op
= s
->result
;
1428 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1430 for (unsigned i
= 0; i
< n_ids
; ++i
)
1432 user_id
*id
= ids
[i
];
1433 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1435 && (contains_id (match_op
, id
)
1436 || contains_id (result_op
, id
)))
1441 subst
.quick_push (std::make_pair (id
, oper
));
1442 match_op
= replace_id (match_op
, id
, oper
);
1444 && !can_delay_subst
)
1445 result_op
= replace_id (result_op
, id
, oper
);
1450 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1451 vNULL
, s
->capture_ids
);
1452 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1455 ns
->for_subst_vec
.safe_splice (subst
);
1457 worklist
.safe_push (ns
);
1460 worklist_start
= worklist_end
;
1463 /* Copy out the result from the last for lowering. */
1464 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1465 simplifiers
.safe_push (worklist
[i
]);
1468 /* Lower the AST for everything in SIMPLIFIERS. */
1471 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1473 auto_vec
<simplify
*> out_simplifiers
;
1474 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1475 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1477 simplifiers
.truncate (0);
1478 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1479 lower_commutative (out_simplifiers
[i
], simplifiers
);
1481 out_simplifiers
.truncate (0);
1483 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1484 lower_cond (simplifiers
[i
], out_simplifiers
);
1486 out_simplifiers
.safe_splice (simplifiers
);
1489 simplifiers
.truncate (0);
1490 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1491 lower_for (out_simplifiers
[i
], simplifiers
);
1497 /* The decision tree built for generating GIMPLE and GENERIC pattern
1498 matching code. It represents the 'match' expression of all
1499 simplifies and has those as its leafs. */
1503 /* A hash-map collecting semantically equivalent leafs in the decision
1504 tree for splitting out to separate functions. */
1513 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1516 static inline hashval_t
hash (const key_type
&);
1517 static inline bool equal_keys (const key_type
&, const key_type
&);
1518 template <typename T
> static inline void remove (T
&) {}
1521 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1525 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1529 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1533 vec
<dt_node
*> kids
;
1537 unsigned total_size
;
1540 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1542 dt_node
*append_node (dt_node
*);
1543 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1544 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1545 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1546 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1548 virtual void gen (FILE *, int, bool) {}
1550 void gen_kids (FILE *, int, bool);
1551 void gen_kids_1 (FILE *, int, bool,
1552 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1553 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1555 void analyze (sinfo_map_t
&);
1558 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1560 struct dt_operand
: public dt_node
1563 dt_operand
*match_dop
;
1568 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1569 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1570 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1571 parent (parent_
), pos (pos_
), value_match (false) {}
1573 void gen (FILE *, int, bool);
1574 unsigned gen_predicate (FILE *, int, const char *, bool);
1575 unsigned gen_match_op (FILE *, int, const char *, bool);
1577 unsigned gen_gimple_expr (FILE *, int);
1578 unsigned gen_generic_expr (FILE *, int, const char *);
1580 char *get_name (char *);
1581 void gen_opname (char *, unsigned);
1584 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1586 struct dt_simplify
: public dt_node
1589 unsigned pattern_no
;
1590 dt_operand
**indexes
;
1593 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1594 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1595 indexes (indexes_
), info (NULL
) {}
1597 void gen_1 (FILE *, int, bool, operand
*);
1598 void gen (FILE *f
, int, bool);
1604 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1606 return (n
->type
== dt_node::DT_OPERAND
1607 || n
->type
== dt_node::DT_MATCH
);
1613 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1615 return n
->type
== dt_node::DT_SIMPLIFY
;
1620 /* A container for the actual decision tree. */
1622 struct decision_tree
1626 void insert (struct simplify
*, unsigned);
1627 void gen (FILE *f
, bool gimple
);
1628 void print (FILE *f
= stderr
);
1630 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1632 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1633 unsigned pos
= 0, dt_node
*parent
= 0);
1634 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1635 static bool cmp_node (dt_node
*, dt_node
*);
1636 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1639 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1642 cmp_operand (operand
*o1
, operand
*o2
)
1644 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1647 if (o1
->type
== operand::OP_PREDICATE
)
1649 predicate
*p1
= as_a
<predicate
*>(o1
);
1650 predicate
*p2
= as_a
<predicate
*>(o2
);
1651 return p1
->p
== p2
->p
;
1653 else if (o1
->type
== operand::OP_EXPR
)
1655 expr
*e1
= static_cast<expr
*>(o1
);
1656 expr
*e2
= static_cast<expr
*>(o2
);
1657 return (e1
->operation
== e2
->operation
1658 && e1
->is_generic
== e2
->is_generic
);
1664 /* Compare two decision tree nodes N1 and N2 and return true if they
1668 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1670 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1676 if (n1
->type
== dt_node::DT_TRUE
)
1679 if (n1
->type
== dt_node::DT_OPERAND
)
1680 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1681 (as_a
<dt_operand
*> (n2
))->op
);
1682 else if (n1
->type
== dt_node::DT_MATCH
)
1683 return (((as_a
<dt_operand
*> (n1
))->match_dop
1684 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1685 && ((as_a
<dt_operand
*> (n1
))->value_match
1686 == (as_a
<dt_operand
*> (n2
))->value_match
));
1690 /* Search OPS for a decision tree node like P and return it if found. */
1693 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1695 /* We can merge adjacent DT_TRUE. */
1696 if (p
->type
== dt_node::DT_TRUE
1698 && ops
.last ()->type
== dt_node::DT_TRUE
)
1700 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1702 /* But we can't merge across DT_TRUE nodes as they serve as
1703 pattern order barriers to make sure that patterns apply
1704 in order of appearance in case multiple matches are possible. */
1705 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1707 if (decision_tree::cmp_node (ops
[i
], p
))
1713 /* Append N to the decision tree if it there is not already an existing
1717 dt_node::append_node (dt_node
*n
)
1721 kid
= decision_tree::find_node (kids
, n
);
1726 n
->level
= this->level
+ 1;
1731 /* Append OP to the decision tree. */
1734 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1736 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1737 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1738 return append_node (n
);
1741 /* Append a DT_TRUE decision tree node. */
1744 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1746 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1747 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1748 return append_node (n
);
1751 /* Append a DT_MATCH decision tree node. */
1754 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1756 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1757 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1758 return append_node (n
);
1761 /* Append S to the decision tree. */
1764 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1765 dt_operand
**indexes
)
1767 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1768 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1769 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1771 warning_at (s
->match
->location
, "duplicate pattern");
1772 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1773 print_operand (s
->match
, stderr
);
1774 fprintf (stderr
, "\n");
1776 return append_node (n
);
1779 /* Analyze the node and its children. */
1782 dt_node::analyze (sinfo_map_t
&map
)
1788 if (type
== DT_SIMPLIFY
)
1790 /* Populate the map of equivalent simplifies. */
1791 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1793 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1808 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1810 kids
[i
]->analyze (map
);
1811 num_leafs
+= kids
[i
]->num_leafs
;
1812 total_size
+= kids
[i
]->total_size
;
1813 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1817 /* Insert O into the decision tree and return the decision tree node found
1821 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1822 unsigned pos
, dt_node
*parent
)
1824 dt_node
*q
, *elm
= 0;
1826 if (capture
*c
= dyn_cast
<capture
*> (o
))
1828 unsigned capt_index
= c
->where
;
1830 if (indexes
[capt_index
] == 0)
1833 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1836 q
= elm
= p
->append_true_op (parent
, pos
);
1839 // get to the last capture
1840 for (operand
*what
= c
->what
;
1841 what
&& is_a
<capture
*> (what
);
1842 c
= as_a
<capture
*> (what
), what
= c
->what
)
1847 unsigned cc_index
= c
->where
;
1848 dt_operand
*match_op
= indexes
[cc_index
];
1850 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1851 elm
= decision_tree::find_node (p
->kids
, &temp
);
1855 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1856 temp
.value_match
= c
->value_match
;
1857 elm
= decision_tree::find_node (p
->kids
, &temp
);
1862 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1863 elm
= decision_tree::find_node (p
->kids
, &temp
);
1867 gcc_assert (elm
->type
== dt_node::DT_TRUE
1868 || elm
->type
== dt_node::DT_OPERAND
1869 || elm
->type
== dt_node::DT_MATCH
);
1870 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1875 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1876 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
1878 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1883 p
= p
->append_op (o
, parent
, pos
);
1886 if (expr
*e
= dyn_cast
<expr
*>(o
))
1888 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1889 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1895 /* Insert S into the decision tree. */
1898 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1900 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1901 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1902 p
->append_simplify (s
, pattern_no
, indexes
);
1905 /* Debug functions to dump the decision tree. */
1908 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1910 if (p
->type
== dt_node::DT_NODE
)
1911 fprintf (f
, "root");
1915 for (unsigned i
= 0; i
< indent
; i
++)
1918 if (p
->type
== dt_node::DT_OPERAND
)
1920 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1921 print_operand (dop
->op
, f
, true);
1923 else if (p
->type
== dt_node::DT_TRUE
)
1924 fprintf (f
, "true");
1925 else if (p
->type
== dt_node::DT_MATCH
)
1926 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1927 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1929 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1930 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1931 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1932 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1937 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1939 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1940 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1944 decision_tree::print (FILE *f
)
1946 return decision_tree::print_node (root
, f
);
1950 /* For GENERIC we have to take care of wrapping multiple-used
1951 expressions with side-effects in save_expr and preserve side-effects
1952 of expressions with omit_one_operand. Analyze captures in
1953 match, result and with expressions and perform early-outs
1954 on the outermost match expression operands for cases we cannot
1959 capture_info (simplify
*s
, operand
*, bool);
1960 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1961 bool walk_result (operand
*o
, bool, operand
*);
1962 void walk_c_expr (c_expr
*);
1968 bool force_no_side_effects_p
;
1969 bool force_single_use
;
1970 bool cond_expr_cond_p
;
1971 unsigned long toplevel_msk
;
1972 unsigned match_use_count
;
1973 unsigned result_use_count
;
1978 auto_vec
<cinfo
> info
;
1979 unsigned long force_no_side_effects
;
1983 /* Analyze captures in S. */
1985 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
1990 if (s
->kind
== simplify::MATCH
)
1992 force_no_side_effects
= -1;
1996 force_no_side_effects
= 0;
1997 info
.safe_grow_cleared (s
->capture_max
+ 1);
1998 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1999 info
[i
].same_as
= i
;
2001 e
= as_a
<expr
*> (s
->match
);
2002 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2003 walk_match (e
->ops
[i
], i
,
2004 (i
!= 0 && *e
->operation
== COND_EXPR
)
2005 || *e
->operation
== TRUTH_ANDIF_EXPR
2006 || *e
->operation
== TRUTH_ORIF_EXPR
,
2008 && (*e
->operation
== COND_EXPR
2009 || *e
->operation
== VEC_COND_EXPR
));
2011 walk_result (s
->result
, false, result
);
2014 /* Analyze captures in the match expression piece O. */
2017 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2018 bool conditional_p
, bool cond_expr_cond_p
)
2020 if (capture
*c
= dyn_cast
<capture
*> (o
))
2022 unsigned where
= c
->where
;
2023 info
[where
].match_use_count
++;
2024 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2025 info
[where
].force_no_side_effects_p
|= conditional_p
;
2026 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2031 /* Recurse to exprs and captures. */
2032 if (is_a
<capture
*> (c
->what
)
2033 || is_a
<expr
*> (c
->what
))
2034 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2035 /* We need to look past multiple captures to find a captured
2036 expression as with conditional converts two captures
2037 can be collapsed onto the same expression. Also collect
2038 what captures capture the same thing. */
2039 while (c
->what
&& is_a
<capture
*> (c
->what
))
2041 c
= as_a
<capture
*> (c
->what
);
2042 if (info
[c
->where
].same_as
!= c
->where
2043 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2044 fatal_at (c
->location
, "cannot handle this collapsed capture");
2045 info
[c
->where
].same_as
= info
[where
].same_as
;
2047 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2050 && (e
= dyn_cast
<expr
*> (c
->what
)))
2052 info
[where
].expr_p
= true;
2053 info
[where
].force_single_use
|= e
->force_single_use
;
2056 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2058 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2060 bool cond_p
= conditional_p
;
2061 bool cond_expr_cond_p
= false;
2062 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2064 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2065 || *e
->operation
== TRUTH_ORIF_EXPR
)
2068 && (*e
->operation
== COND_EXPR
2069 || *e
->operation
== VEC_COND_EXPR
))
2070 cond_expr_cond_p
= true;
2071 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2074 else if (is_a
<predicate
*> (o
))
2076 /* Mark non-captured leafs toplevel arg for checking. */
2077 force_no_side_effects
|= 1 << toplevel_arg
;
2080 warning_at (o
->location
,
2081 "forcing no side-effects on possibly lost leaf");
2087 /* Analyze captures in the result expression piece O. Return true
2088 if RESULT was visited in one of the children. Only visit
2089 non-if/with children if they are rooted on RESULT. */
2092 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2094 if (capture
*c
= dyn_cast
<capture
*> (o
))
2096 unsigned where
= info
[c
->where
].same_as
;
2097 info
[where
].result_use_count
++;
2098 /* If we substitute an expression capture we don't know
2099 which captures this will end up using (well, we don't
2100 compute that). Force the uses to be side-effect free
2101 which means forcing the toplevels that reach the
2102 expression side-effect free. */
2103 if (info
[where
].expr_p
)
2104 force_no_side_effects
|= info
[where
].toplevel_msk
;
2105 /* Mark CSE capture uses as forced to have no side-effects. */
2107 && is_a
<expr
*> (c
->what
))
2109 info
[where
].cse_p
= true;
2110 walk_result (c
->what
, true, result
);
2113 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2115 id_base
*opr
= e
->operation
;
2116 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2117 opr
= uid
->substitutes
[0];
2118 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2120 bool cond_p
= conditional_p
;
2121 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2123 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2124 || *e
->operation
== TRUTH_ORIF_EXPR
)
2126 walk_result (e
->ops
[i
], cond_p
, result
);
2129 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2131 /* 'if' conditions should be all fine. */
2132 if (e
->trueexpr
== result
)
2134 walk_result (e
->trueexpr
, false, result
);
2137 if (e
->falseexpr
== result
)
2139 walk_result (e
->falseexpr
, false, result
);
2143 if (is_a
<if_expr
*> (e
->trueexpr
)
2144 || is_a
<with_expr
*> (e
->trueexpr
))
2145 res
|= walk_result (e
->trueexpr
, false, result
);
2147 && (is_a
<if_expr
*> (e
->falseexpr
)
2148 || is_a
<with_expr
*> (e
->falseexpr
)))
2149 res
|= walk_result (e
->falseexpr
, false, result
);
2152 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2154 bool res
= (e
->subexpr
== result
);
2156 || is_a
<if_expr
*> (e
->subexpr
)
2157 || is_a
<with_expr
*> (e
->subexpr
))
2158 res
|= walk_result (e
->subexpr
, false, result
);
2160 walk_c_expr (e
->with
);
2163 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2171 /* Look for captures in the C expr E. */
2174 capture_info::walk_c_expr (c_expr
*e
)
2176 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2177 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2178 really escape through. */
2179 unsigned p_depth
= 0;
2180 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2182 const cpp_token
*t
= &e
->code
[i
];
2183 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2185 if (t
->type
== CPP_NAME
2186 && (strcmp ((const char *)CPP_HASHNODE
2187 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2188 || strcmp ((const char *)CPP_HASHNODE
2189 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2190 || strcmp ((const char *)CPP_HASHNODE
2191 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2192 || ((id
= get_operator ((const char *)CPP_HASHNODE
2193 (t
->val
.node
.node
)->ident
.str
))
2194 && is_a
<predicate_id
*> (id
)))
2195 && n
->type
== CPP_OPEN_PAREN
)
2197 else if (t
->type
== CPP_CLOSE_PAREN
2200 else if (p_depth
== 0
2201 && t
->type
== CPP_ATSIGN
2202 && (n
->type
== CPP_NUMBER
2203 || n
->type
== CPP_NAME
)
2204 && !(n
->flags
& PREV_WHITE
))
2207 if (n
->type
== CPP_NUMBER
)
2208 id
= (const char *)n
->val
.str
.text
;
2210 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2211 unsigned *where
= e
->capture_ids
->get(id
);
2213 fatal_at (n
, "unknown capture id '%s'", id
);
2214 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2217 warning_at (t
, "capture escapes");
2223 /* Code generation off the decision tree and the refered AST nodes. */
2226 is_conversion (id_base
*op
)
2228 return (*op
== CONVERT_EXPR
2230 || *op
== FLOAT_EXPR
2231 || *op
== FIX_TRUNC_EXPR
2232 || *op
== VIEW_CONVERT_EXPR
);
2235 /* Get the type to be used for generating operand POS of OP from the
2239 get_operand_type (id_base
*op
, unsigned pos
,
2240 const char *in_type
,
2241 const char *expr_type
,
2242 const char *other_oprnd_type
)
2244 /* Generally operands whose type does not match the type of the
2245 expression generated need to know their types but match and
2246 thus can fall back to 'other_oprnd_type'. */
2247 if (is_conversion (op
))
2248 return other_oprnd_type
;
2249 else if (*op
== REALPART_EXPR
2250 || *op
== IMAGPART_EXPR
)
2251 return other_oprnd_type
;
2252 else if (is_a
<operator_id
*> (op
)
2253 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2254 return other_oprnd_type
;
2255 else if (*op
== COND_EXPR
2257 return "boolean_type_node";
2260 /* Otherwise all types should match - choose one in order of
2267 return other_oprnd_type
;
2271 /* Generate transform code for an expression. */
2274 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2275 int depth
, const char *in_type
, capture_info
*cinfo
,
2276 dt_operand
**indexes
, int)
2278 id_base
*opr
= operation
;
2279 /* When we delay operator substituting during lowering of fors we
2280 make sure that for code-gen purposes the effects of each substitute
2281 are the same. Thus just look at that. */
2282 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2283 opr
= uid
->substitutes
[0];
2285 bool conversion_p
= is_conversion (opr
);
2286 const char *type
= expr_type
;
2289 /* If there was a type specification in the pattern use it. */
2291 else if (conversion_p
)
2292 /* For conversions we need to build the expression using the
2293 outer type passed in. */
2295 else if (*opr
== REALPART_EXPR
2296 || *opr
== IMAGPART_EXPR
)
2298 /* __real and __imag use the component type of its operand. */
2299 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2302 else if (is_a
<operator_id
*> (opr
)
2303 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2305 /* comparisons use boolean_type_node (or what gets in), but
2306 their operands need to figure out the types themselves. */
2311 sprintf (optype
, "boolean_type_node");
2316 else if (*opr
== COND_EXPR
2317 || *opr
== VEC_COND_EXPR
)
2319 /* Conditions are of the same type as their first alternative. */
2320 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2325 /* Other operations are of the same type as their first operand. */
2326 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2330 fatal_at (location
, "cannot determine type of operand");
2332 fprintf_indent (f
, indent
, "{\n");
2334 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2336 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2337 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2340 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2342 = get_operand_type (opr
, i
, in_type
, expr_type
,
2343 i
== 0 ? NULL
: op0type
);
2344 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2347 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2350 const char *opr_name
;
2351 if (*operation
== CONVERT_EXPR
)
2352 opr_name
= "NOP_EXPR";
2354 opr_name
= operation
->id
;
2358 if (*opr
== CONVERT_EXPR
)
2360 fprintf_indent (f
, indent
,
2361 "if (%s != TREE_TYPE (ops%d[0])\n",
2363 fprintf_indent (f
, indent
,
2364 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2366 fprintf_indent (f
, indent
+ 2, "{\n");
2369 /* ??? Building a stmt can fail for various reasons here, seq being
2370 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2371 So if we fail here we should continue matching other patterns. */
2372 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2373 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2374 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2375 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2376 i
== ops
.length () - 1 ? " };\n" : ", ");
2377 fprintf_indent (f
, indent
,
2378 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2379 ops
.length (), type
);
2380 fprintf_indent (f
, indent
,
2381 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2383 fprintf_indent (f
, indent
,
2384 "if (!res) return false;\n");
2385 if (*opr
== CONVERT_EXPR
)
2388 fprintf_indent (f
, indent
, " }\n");
2389 fprintf_indent (f
, indent
, "else\n");
2390 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2395 if (*opr
== CONVERT_EXPR
)
2397 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2401 if (opr
->kind
== id_base::CODE
)
2402 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2403 ops
.length(), opr_name
, type
);
2406 fprintf_indent (f
, indent
, "{\n");
2407 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2408 "%s, %s, %d", opr_name
, type
, ops
.length());
2410 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2411 fprintf (f
, ", ops%d[%u]", depth
, i
);
2412 fprintf (f
, ");\n");
2413 if (opr
->kind
!= id_base::CODE
)
2415 fprintf_indent (f
, indent
, " if (!res)\n");
2416 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2417 fprintf_indent (f
, indent
, "}\n");
2419 if (*opr
== CONVERT_EXPR
)
2422 fprintf_indent (f
, indent
, "else\n");
2423 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2426 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2428 fprintf_indent (f
, indent
, "}\n");
2431 /* Generate code for a c_expr which is either the expression inside
2432 an if statement or a sequence of statements which computes a
2433 result to be stored to DEST. */
2436 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2437 bool, int, const char *, capture_info
*,
2440 if (dest
&& nr_stmts
== 1)
2441 fprintf_indent (f
, indent
, "%s = ", dest
);
2443 unsigned stmt_nr
= 1;
2444 for (unsigned i
= 0; i
< code
.length (); ++i
)
2446 const cpp_token
*token
= &code
[i
];
2448 /* Replace captures for code-gen. */
2449 if (token
->type
== CPP_ATSIGN
)
2451 const cpp_token
*n
= &code
[i
+1];
2452 if ((n
->type
== CPP_NUMBER
2453 || n
->type
== CPP_NAME
)
2454 && !(n
->flags
& PREV_WHITE
))
2456 if (token
->flags
& PREV_WHITE
)
2459 if (n
->type
== CPP_NUMBER
)
2460 id
= (const char *)n
->val
.str
.text
;
2462 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2463 unsigned *cid
= capture_ids
->get (id
);
2465 fatal_at (token
, "unknown capture id");
2466 fprintf (f
, "captures[%u]", *cid
);
2472 if (token
->flags
& PREV_WHITE
)
2475 if (token
->type
== CPP_NAME
)
2477 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2479 for (j
= 0; j
< ids
.length (); ++j
)
2481 if (strcmp (id
, ids
[j
].id
) == 0)
2483 fprintf (f
, "%s", ids
[j
].oper
);
2487 if (j
< ids
.length ())
2491 /* Output the token as string. */
2492 char *tk
= (char *)cpp_token_as_text (r
, token
);
2495 if (token
->type
== CPP_SEMICOLON
)
2499 if (dest
&& stmt_nr
== nr_stmts
)
2500 fprintf_indent (f
, indent
, "%s = ", dest
);
2505 /* Generate transform code for a capture. */
2508 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2509 int depth
, const char *in_type
, capture_info
*cinfo
,
2510 dt_operand
**indexes
, int cond_handling
)
2512 if (what
&& is_a
<expr
*> (what
))
2514 if (indexes
[where
] == 0)
2517 sprintf (buf
, "captures[%u]", where
);
2518 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2523 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2525 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2526 with substituting a capture of that. */
2528 && cond_handling
!= 0
2529 && cinfo
->info
[where
].cond_expr_cond_p
)
2531 /* If substituting into a cond_expr condition, unshare. */
2532 if (cond_handling
== 1)
2533 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2534 /* If substituting elsewhere we might need to decompose it. */
2535 else if (cond_handling
== 2)
2537 /* ??? Returning false here will also not allow any other patterns
2538 to match unless this generator was split out. */
2539 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2540 fprintf_indent (f
, indent
, " {\n");
2541 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2542 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2544 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2545 " TREE_OPERAND (%s, 1));\n",
2546 dest
, dest
, dest
, dest
, dest
);
2547 fprintf_indent (f
, indent
, " }\n");
2552 /* Return the name of the operand representing the decision tree node.
2553 Use NAME as space to generate it. */
2556 dt_operand::get_name (char *name
)
2559 sprintf (name
, "t");
2560 else if (parent
->level
== 1)
2561 sprintf (name
, "op%u", pos
);
2562 else if (parent
->type
== dt_node::DT_MATCH
)
2563 return parent
->get_name (name
);
2565 sprintf (name
, "o%u%u", parent
->level
, pos
);
2569 /* Fill NAME with the operand name at position POS. */
2572 dt_operand::gen_opname (char *name
, unsigned pos
)
2575 sprintf (name
, "op%u", pos
);
2577 sprintf (name
, "o%u%u", level
, pos
);
2580 /* Generate matching code for the decision tree operand which is
2584 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2586 predicate
*p
= as_a
<predicate
*> (op
);
2588 if (p
->p
->matchers
.exists ())
2590 /* If this is a predicate generated from a pattern mangle its
2591 name and pass on the valueize hook. */
2593 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2596 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2599 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2600 fprintf_indent (f
, indent
+ 2, "{\n");
2604 /* Generate matching code for the decision tree operand which is
2608 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2610 char match_opname
[20];
2611 match_dop
->get_name (match_opname
);
2613 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2614 opname
, match_opname
, opname
, match_opname
);
2616 fprintf_indent (f
, indent
, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
2617 "&& types_match (%s, %s)))\n",
2618 opname
, match_opname
, opname
, match_opname
,
2619 opname
, match_opname
);
2620 fprintf_indent (f
, indent
+ 2, "{\n");
2624 /* Generate GIMPLE matching code for the decision tree operand. */
2627 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2629 expr
*e
= static_cast<expr
*> (op
);
2630 id_base
*id
= e
->operation
;
2631 unsigned n_ops
= e
->ops
.length ();
2633 for (unsigned i
= 0; i
< n_ops
; ++i
)
2635 char child_opname
[20];
2636 gen_opname (child_opname
, i
);
2638 if (id
->kind
== id_base::CODE
)
2641 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2642 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2644 /* ??? If this is a memory operation we can't (and should not)
2645 match this. The only sensible operand types are
2646 SSA names and invariants. */
2647 fprintf_indent (f
, indent
,
2648 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def), %i);\n",
2650 fprintf_indent (f
, indent
,
2651 "if ((TREE_CODE (%s) == SSA_NAME\n",
2653 fprintf_indent (f
, indent
,
2654 " || is_gimple_min_invariant (%s))\n",
2656 fprintf_indent (f
, indent
,
2657 " && (%s = do_valueize (valueize, %s)))\n",
2658 child_opname
, child_opname
);
2659 fprintf_indent (f
, indent
,
2665 fprintf_indent (f
, indent
,
2666 "tree %s = gimple_assign_rhs%u (def);\n",
2667 child_opname
, i
+ 1);
2670 fprintf_indent (f
, indent
,
2671 "tree %s = gimple_call_arg (def, %u);\n",
2673 fprintf_indent (f
, indent
,
2674 "if ((%s = do_valueize (valueize, %s)))\n",
2675 child_opname
, child_opname
);
2676 fprintf_indent (f
, indent
, " {\n");
2679 /* While the toplevel operands are canonicalized by the caller
2680 after valueizing operands of sub-expressions we have to
2681 re-canonicalize operand order. */
2682 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2684 /* ??? We can't canonicalize tcc_comparison operands here
2685 because that requires changing the comparison code which
2686 we already matched... */
2687 if (commutative_tree_code (code
->code
)
2688 || commutative_ternary_tree_code (code
->code
))
2690 char child_opname0
[20], child_opname1
[20];
2691 gen_opname (child_opname0
, 0);
2692 gen_opname (child_opname1
, 1);
2693 fprintf_indent (f
, indent
,
2694 "if (tree_swap_operands_p (%s, %s, false))\n",
2695 child_opname0
, child_opname1
);
2696 fprintf_indent (f
, indent
,
2697 " std::swap (%s, %s);\n",
2698 child_opname0
, child_opname1
);
2705 /* Generate GENERIC matching code for the decision tree operand. */
2708 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2710 expr
*e
= static_cast<expr
*> (op
);
2711 unsigned n_ops
= e
->ops
.length ();
2713 for (unsigned i
= 0; i
< n_ops
; ++i
)
2715 char child_opname
[20];
2716 gen_opname (child_opname
, i
);
2718 if (e
->operation
->kind
== id_base::CODE
)
2719 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2720 child_opname
, opname
, i
);
2722 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2723 child_opname
, opname
, i
);
2729 /* Generate matching code for the children of the decision tree node. */
2732 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2734 auto_vec
<dt_operand
*> gimple_exprs
;
2735 auto_vec
<dt_operand
*> generic_exprs
;
2736 auto_vec
<dt_operand
*> fns
;
2737 auto_vec
<dt_operand
*> generic_fns
;
2738 auto_vec
<dt_operand
*> preds
;
2739 auto_vec
<dt_node
*> others
;
2741 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2743 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2745 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2746 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2748 if (e
->ops
.length () == 0
2749 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2750 generic_exprs
.safe_push (op
);
2751 else if (e
->operation
->kind
== id_base::FN
)
2756 generic_fns
.safe_push (op
);
2758 else if (e
->operation
->kind
== id_base::PREDICATE
)
2759 preds
.safe_push (op
);
2762 if (gimple
&& !e
->is_generic
)
2763 gimple_exprs
.safe_push (op
);
2765 generic_exprs
.safe_push (op
);
2768 else if (op
->op
->type
== operand::OP_PREDICATE
)
2769 others
.safe_push (kids
[i
]);
2773 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2774 others
.safe_push (kids
[i
]);
2775 else if (kids
[i
]->type
== dt_node::DT_MATCH
2776 || kids
[i
]->type
== dt_node::DT_TRUE
)
2778 /* A DT_TRUE operand serves as a barrier - generate code now
2779 for what we have collected sofar.
2780 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2781 dependent matches to get out-of-order. Generate code now
2782 for what we have collected sofar. */
2783 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2784 fns
, generic_fns
, preds
, others
);
2785 /* And output the true operand itself. */
2786 kids
[i
]->gen (f
, indent
, gimple
);
2787 gimple_exprs
.truncate (0);
2788 generic_exprs
.truncate (0);
2790 generic_fns
.truncate (0);
2792 others
.truncate (0);
2798 /* Generate code for the remains. */
2799 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2800 fns
, generic_fns
, preds
, others
);
2803 /* Generate matching code for the children of the decision tree node. */
2806 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2807 vec
<dt_operand
*> gimple_exprs
,
2808 vec
<dt_operand
*> generic_exprs
,
2809 vec
<dt_operand
*> fns
,
2810 vec
<dt_operand
*> generic_fns
,
2811 vec
<dt_operand
*> preds
,
2812 vec
<dt_node
*> others
)
2815 char *kid_opname
= buf
;
2817 unsigned exprs_len
= gimple_exprs
.length ();
2818 unsigned gexprs_len
= generic_exprs
.length ();
2819 unsigned fns_len
= fns
.length ();
2820 unsigned gfns_len
= generic_fns
.length ();
2822 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2825 gimple_exprs
[0]->get_name (kid_opname
);
2827 fns
[0]->get_name (kid_opname
);
2829 generic_fns
[0]->get_name (kid_opname
);
2831 generic_exprs
[0]->get_name (kid_opname
);
2833 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2834 fprintf_indent (f
, indent
, " {\n");
2838 if (exprs_len
|| fns_len
)
2840 fprintf_indent (f
, indent
,
2841 "case SSA_NAME:\n");
2842 fprintf_indent (f
, indent
,
2843 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2845 fprintf_indent (f
, indent
,
2847 fprintf_indent (f
, indent
,
2848 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2854 fprintf_indent (f
, indent
,
2855 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2856 fprintf_indent (f
, indent
,
2857 " switch (gimple_assign_rhs_code (def))\n");
2859 fprintf_indent (f
, indent
, "{\n");
2860 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2862 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2863 id_base
*op
= e
->operation
;
2864 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2865 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2867 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2868 fprintf_indent (f
, indent
, " {\n");
2869 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2870 fprintf_indent (f
, indent
, " break;\n");
2871 fprintf_indent (f
, indent
, " }\n");
2873 fprintf_indent (f
, indent
, "default:;\n");
2874 fprintf_indent (f
, indent
, "}\n");
2880 fprintf_indent (f
, indent
,
2881 "%sif (gcall *def = dyn_cast <gcall *>"
2883 exprs_len
? "else " : "");
2884 fprintf_indent (f
, indent
,
2885 " switch (gimple_call_combined_fn (def))\n");
2888 fprintf_indent (f
, indent
, "{\n");
2889 for (unsigned i
= 0; i
< fns_len
; ++i
)
2891 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2892 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2893 fprintf_indent (f
, indent
, " {\n");
2894 fns
[i
]->gen (f
, indent
+ 4, true);
2895 fprintf_indent (f
, indent
, " break;\n");
2896 fprintf_indent (f
, indent
, " }\n");
2899 fprintf_indent (f
, indent
, "default:;\n");
2900 fprintf_indent (f
, indent
, "}\n");
2905 fprintf_indent (f
, indent
, " }\n");
2906 fprintf_indent (f
, indent
, " break;\n");
2909 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2911 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2912 id_base
*op
= e
->operation
;
2913 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2914 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2916 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2917 fprintf_indent (f
, indent
, " {\n");
2918 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2919 fprintf_indent (f
, indent
, " break;\n");
2920 fprintf_indent (f
, indent
, " }\n");
2925 fprintf_indent (f
, indent
,
2926 "case CALL_EXPR:\n");
2927 fprintf_indent (f
, indent
,
2928 " switch (get_call_combined_fn (%s))\n",
2930 fprintf_indent (f
, indent
,
2934 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2936 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2937 gcc_assert (e
->operation
->kind
== id_base::FN
);
2939 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2940 fprintf_indent (f
, indent
, " {\n");
2941 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2942 fprintf_indent (f
, indent
, " break;\n");
2943 fprintf_indent (f
, indent
, " }\n");
2945 fprintf_indent (f
, indent
, "default:;\n");
2948 fprintf_indent (f
, indent
, " }\n");
2949 fprintf_indent (f
, indent
, " break;\n");
2952 /* Close switch (TREE_CODE ()). */
2953 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2956 fprintf_indent (f
, indent
, " default:;\n");
2957 fprintf_indent (f
, indent
, " }\n");
2960 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2962 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2963 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2964 preds
[i
]->get_name (kid_opname
);
2965 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2966 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2967 gimple
? "gimple" : "tree",
2968 p
->id
, kid_opname
, kid_opname
,
2969 gimple
? ", valueize" : "");
2970 fprintf_indent (f
, indent
, " {\n");
2971 for (int j
= 0; j
< p
->nargs
; ++j
)
2973 char child_opname
[20];
2974 preds
[i
]->gen_opname (child_opname
, j
);
2975 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2976 child_opname
, kid_opname
, j
);
2978 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2982 for (unsigned i
= 0; i
< others
.length (); ++i
)
2983 others
[i
]->gen (f
, indent
, gimple
);
2986 /* Generate matching code for the decision tree operand. */
2989 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2994 unsigned n_braces
= 0;
2996 if (type
== DT_OPERAND
)
2999 case operand::OP_PREDICATE
:
3000 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3003 case operand::OP_EXPR
:
3005 n_braces
= gen_gimple_expr (f
, indent
);
3007 n_braces
= gen_generic_expr (f
, indent
, opname
);
3013 else if (type
== DT_TRUE
)
3015 else if (type
== DT_MATCH
)
3016 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3020 indent
+= 4 * n_braces
;
3021 gen_kids (f
, indent
, gimple
);
3023 for (unsigned i
= 0; i
< n_braces
; ++i
)
3028 fprintf_indent (f
, indent
, " }\n");
3033 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3034 step of a '(simplify ...)' or '(match ...)'. This handles everything
3035 that is not part of the decision tree (simplify->match).
3036 Main recursive worker. */
3039 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3043 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3045 fprintf_indent (f
, indent
, "{\n");
3047 output_line_directive (f
, w
->location
);
3048 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3049 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3051 fprintf_indent (f
, indent
, "}\n");
3054 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3056 output_line_directive (f
, ife
->location
);
3057 fprintf_indent (f
, indent
, "if (");
3058 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3060 fprintf_indent (f
, indent
+ 2, "{\n");
3062 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3064 fprintf_indent (f
, indent
+ 2, "}\n");
3067 fprintf_indent (f
, indent
, "else\n");
3068 fprintf_indent (f
, indent
+ 2, "{\n");
3070 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3072 fprintf_indent (f
, indent
+ 2, "}\n");
3078 /* Analyze captures and perform early-outs on the incoming arguments
3079 that cover cases we cannot handle. */
3080 capture_info
cinfo (s
, result
, gimple
);
3081 if (s
->kind
== simplify::SIMPLIFY
)
3085 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3086 if (cinfo
.force_no_side_effects
& (1 << i
))
3088 fprintf_indent (f
, indent
,
3089 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3092 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3093 "forcing toplevel operand to have no "
3096 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3097 if (cinfo
.info
[i
].cse_p
)
3099 else if (cinfo
.info
[i
].force_no_side_effects_p
3100 && (cinfo
.info
[i
].toplevel_msk
3101 & cinfo
.force_no_side_effects
) == 0)
3103 fprintf_indent (f
, indent
,
3104 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3105 "return NULL_TREE;\n", i
);
3107 warning_at (cinfo
.info
[i
].c
->location
,
3108 "forcing captured operand to have no "
3111 else if ((cinfo
.info
[i
].toplevel_msk
3112 & cinfo
.force_no_side_effects
) != 0)
3113 /* Mark capture as having no side-effects if we had to verify
3114 that via forced toplevel operand checks. */
3115 cinfo
.info
[i
].force_no_side_effects_p
= true;
3119 /* Force single-use restriction by only allowing simple
3120 results via setting seq to NULL. */
3121 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3122 bool first_p
= true;
3123 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3124 if (cinfo
.info
[i
].force_single_use
)
3128 fprintf_indent (f
, indent
, "if (lseq\n");
3129 fprintf_indent (f
, indent
, " && (");
3135 fprintf_indent (f
, indent
, " || ");
3137 fprintf (f
, "!single_use (captures[%d])", i
);
3141 fprintf (f
, "))\n");
3142 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3147 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
3148 "fprintf (dump_file, \"Applying pattern ");
3149 output_line_directive (f
,
3150 result
? result
->location
: s
->match
->location
, true);
3151 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3155 /* If there is no result then this is a predicate implementation. */
3156 fprintf_indent (f
, indent
, "return true;\n");
3160 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3161 in outermost position). */
3162 if (result
->type
== operand::OP_EXPR
3163 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3164 result
= as_a
<expr
*> (result
)->ops
[0];
3165 if (result
->type
== operand::OP_EXPR
)
3167 expr
*e
= as_a
<expr
*> (result
);
3168 id_base
*opr
= e
->operation
;
3169 bool is_predicate
= false;
3170 /* When we delay operator substituting during lowering of fors we
3171 make sure that for code-gen purposes the effects of each substitute
3172 are the same. Thus just look at that. */
3173 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3174 opr
= uid
->substitutes
[0];
3175 else if (is_a
<predicate_id
*> (opr
))
3176 is_predicate
= true;
3178 fprintf_indent (f
, indent
, "*res_code = %s;\n",
3179 *e
->operation
== CONVERT_EXPR
3180 ? "NOP_EXPR" : e
->operation
->id
);
3181 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3184 snprintf (dest
, 32, "res_ops[%d]", j
);
3186 = get_operand_type (opr
, j
,
3187 "type", e
->expr_type
,
3188 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
3189 /* We need to expand GENERIC conditions we captured from
3190 COND_EXPRs and we need to unshare them when substituting
3192 int cond_handling
= 0;
3194 cond_handling
= ((*opr
== COND_EXPR
3195 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3196 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3197 &cinfo
, indexes
, cond_handling
);
3200 /* Re-fold the toplevel result. It's basically an embedded
3201 gimple_build w/o actually building the stmt. */
3203 fprintf_indent (f
, indent
,
3204 "gimple_resimplify%d (lseq, res_code, type, "
3205 "res_ops, valueize);\n", e
->ops
.length ());
3207 else if (result
->type
== operand::OP_CAPTURE
3208 || result
->type
== operand::OP_C_EXPR
)
3210 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
3212 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
3213 if (is_a
<capture
*> (result
)
3214 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3216 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3217 with substituting a capture of that. */
3218 fprintf_indent (f
, indent
,
3219 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3220 fprintf_indent (f
, indent
,
3222 fprintf_indent (f
, indent
,
3223 " tree tem = res_ops[0];\n");
3224 fprintf_indent (f
, indent
,
3225 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3226 fprintf_indent (f
, indent
,
3227 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3228 fprintf_indent (f
, indent
,
3234 fprintf_indent (f
, indent
, "return true;\n");
3238 bool is_predicate
= false;
3239 if (result
->type
== operand::OP_EXPR
)
3241 expr
*e
= as_a
<expr
*> (result
);
3242 id_base
*opr
= e
->operation
;
3243 /* When we delay operator substituting during lowering of fors we
3244 make sure that for code-gen purposes the effects of each substitute
3245 are the same. Thus just look at that. */
3246 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3247 opr
= uid
->substitutes
[0];
3248 else if (is_a
<predicate_id
*> (opr
))
3249 is_predicate
= true;
3250 /* Search for captures used multiple times in the result expression
3251 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3252 original expression. */
3254 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3256 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3257 || cinfo
.info
[i
].cse_p
)
3259 if (cinfo
.info
[i
].result_use_count
3260 > cinfo
.info
[i
].match_use_count
)
3261 fprintf_indent (f
, indent
,
3262 "if (! tree_invariant_p (captures[%d])) "
3263 "return NULL_TREE;\n", i
);
3265 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3269 snprintf (dest
, 32, "res_ops[%d]", j
);
3272 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3273 snprintf (dest
, 32, "res_op%d", j
);
3276 = get_operand_type (opr
, j
,
3277 "type", e
->expr_type
,
3279 ? NULL
: "TREE_TYPE (res_op0)");
3280 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3284 fprintf_indent (f
, indent
, "return true;\n");
3287 fprintf_indent (f
, indent
, "tree res;\n");
3288 /* Re-fold the toplevel result. Use non_lvalue to
3289 build NON_LVALUE_EXPRs so they get properly
3290 ignored when in GIMPLE form. */
3291 if (*opr
== NON_LVALUE_EXPR
)
3292 fprintf_indent (f
, indent
,
3293 "res = non_lvalue_loc (loc, res_op0);\n");
3296 if (is_a
<operator_id
*> (opr
))
3297 fprintf_indent (f
, indent
,
3298 "res = fold_build%d_loc (loc, %s, type",
3300 *e
->operation
== CONVERT_EXPR
3301 ? "NOP_EXPR" : e
->operation
->id
);
3303 fprintf_indent (f
, indent
,
3304 "res = maybe_build_call_expr_loc (loc, "
3305 "%s, type, %d", e
->operation
->id
,
3307 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3308 fprintf (f
, ", res_op%d", j
);
3309 fprintf (f
, ");\n");
3310 if (!is_a
<operator_id
*> (opr
))
3312 fprintf_indent (f
, indent
, "if (!res)\n");
3313 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3318 else if (result
->type
== operand::OP_CAPTURE
3319 || result
->type
== operand::OP_C_EXPR
)
3322 fprintf_indent (f
, indent
, "tree res;\n");
3323 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3330 /* Search for captures not used in the result expression and dependent
3331 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3332 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3334 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3336 if (!cinfo
.info
[i
].force_no_side_effects_p
3337 && !cinfo
.info
[i
].expr_p
3338 && cinfo
.info
[i
].result_use_count
== 0)
3340 fprintf_indent (f
, indent
,
3341 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3343 fprintf_indent (f
, indent
+ 2,
3344 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3345 "fold_ignored_result (captures[%d]), res);\n",
3349 fprintf_indent (f
, indent
, "return res;\n");
3354 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3355 step of a '(simplify ...)' or '(match ...)'. This handles everything
3356 that is not part of the decision tree (simplify->match). */
3359 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3361 fprintf_indent (f
, indent
, "{\n");
3363 output_line_directive (f
,
3364 s
->result
? s
->result
->location
: s
->match
->location
);
3365 if (s
->capture_max
>= 0)
3368 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3369 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3371 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3375 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3377 fprintf (f
, " };\n");
3380 /* If we have a split-out function for the actual transform, call it. */
3381 if (info
&& info
->fname
)
3385 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3386 "valueize, type, captures", info
->fname
);
3387 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3388 if (s
->for_subst_vec
[i
].first
->used
)
3389 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3390 fprintf (f
, "))\n");
3391 fprintf_indent (f
, indent
, " return true;\n");
3395 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3397 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3398 fprintf (f
, ", op%d", i
);
3399 fprintf (f
, ", captures");
3400 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3402 if (s
->for_subst_vec
[i
].first
->used
)
3403 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3405 fprintf (f
, ");\n");
3406 fprintf_indent (f
, indent
, "if (res) return res;\n");
3411 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3413 if (! s
->for_subst_vec
[i
].first
->used
)
3415 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3416 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3417 s
->for_subst_vec
[i
].first
->id
,
3418 s
->for_subst_vec
[i
].second
->id
);
3419 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3420 fprintf_indent (f
, indent
, "combined_fn %s = %s;\n",
3421 s
->for_subst_vec
[i
].first
->id
,
3422 s
->for_subst_vec
[i
].second
->id
);
3426 gen_1 (f
, indent
, gimple
, s
->result
);
3430 fprintf_indent (f
, indent
, "}\n");
3434 /* Hash function for finding equivalent transforms. */
3437 sinfo_hashmap_traits::hash (const key_type
&v
)
3439 /* Only bother to compare those originating from the same source pattern. */
3440 return v
->s
->result
->location
;
3443 /* Compare function for finding equivalent transforms. */
3446 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3448 if (o1
->type
!= o2
->type
)
3453 case operand::OP_IF
:
3455 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3456 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3457 /* ??? Properly compare c-exprs. */
3458 if (if1
->cond
!= if2
->cond
)
3460 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3462 if (if1
->falseexpr
!= if2
->falseexpr
3464 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3468 case operand::OP_WITH
:
3470 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3471 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3472 if (with1
->with
!= with2
->with
)
3474 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3479 /* We've hit a result. Time to compare capture-infos - this is required
3480 in addition to the conservative pointer-equivalency of the result IL. */
3481 capture_info
cinfo1 (s1
, o1
, true);
3482 capture_info
cinfo2 (s2
, o2
, true);
3484 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3485 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3488 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3490 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3491 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3492 || (cinfo1
.info
[i
].force_no_side_effects_p
3493 != cinfo2
.info
[i
].force_no_side_effects_p
)
3494 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3495 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3496 /* toplevel_msk is an optimization */
3497 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3498 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3499 /* the pointer back to the capture is for diagnostics only */)
3503 /* ??? Deep-compare the actual result. */
3508 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3509 const key_type
&candidate
)
3511 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3515 /* Main entry to generate code for matching GIMPLE IL off the decision
3519 decision_tree::gen (FILE *f
, bool gimple
)
3525 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3526 "a total number of %u nodes\n",
3527 gimple
? "GIMPLE" : "GENERIC",
3528 root
->num_leafs
, root
->max_level
, root
->total_size
);
3530 /* First split out the transform part of equal leafs. */
3533 for (sinfo_map_t::iterator iter
= si
.begin ();
3534 iter
!= si
.end (); ++iter
)
3536 sinfo
*s
= (*iter
).second
;
3537 /* Do not split out single uses. */
3544 fprintf (stderr
, "found %u uses of", s
->cnt
);
3545 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3548 /* Generate a split out function with the leaf transform code. */
3549 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3552 fprintf (f
, "\nstatic bool\n"
3553 "%s (code_helper *res_code, tree *res_ops,\n"
3554 " gimple_seq *seq, tree (*valueize)(tree) "
3555 "ATTRIBUTE_UNUSED,\n"
3556 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3561 fprintf (f
, "\nstatic tree\n"
3562 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3563 (*iter
).second
->fname
);
3564 for (unsigned i
= 0;
3565 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3566 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3567 fprintf (f
, " tree *captures\n");
3569 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3571 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3573 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3574 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3575 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3576 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3577 fprintf (f
, ", combined_fn ARG_UNUSED (%s)",
3578 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3581 fprintf (f
, ")\n{\n");
3582 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3584 fprintf (f
, " return false;\n");
3586 fprintf (f
, " return NULL_TREE;\n");
3589 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3591 for (unsigned n
= 1; n
<= 3; ++n
)
3593 /* First generate split-out functions. */
3594 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3596 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3597 expr
*e
= static_cast<expr
*>(dop
->op
);
3598 if (e
->ops
.length () != n
3599 /* Builtin simplifications are somewhat premature on
3600 GENERIC. The following drops patterns with outermost
3601 calls. It's easy to emit overloads for function code
3602 though if necessary. */
3604 && e
->operation
->kind
!= id_base::CODE
))
3608 fprintf (f
, "\nstatic bool\n"
3609 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3610 " gimple_seq *seq, tree (*valueize)(tree) "
3611 "ATTRIBUTE_UNUSED,\n"
3612 " code_helper ARG_UNUSED (code), tree "
3613 "ARG_UNUSED (type)\n",
3616 fprintf (f
, "\nstatic tree\n"
3617 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3618 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3620 for (unsigned i
= 0; i
< n
; ++i
)
3621 fprintf (f
, ", tree op%d", i
);
3624 dop
->gen_kids (f
, 2, gimple
);
3626 fprintf (f
, " return false;\n");
3628 fprintf (f
, " return NULL_TREE;\n");
3632 /* Then generate the main entry with the outermost switch and
3633 tail-calls to the split-out functions. */
3635 fprintf (f
, "\nstatic bool\n"
3636 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3637 " gimple_seq *seq, tree (*valueize)(tree),\n"
3638 " code_helper code, tree type");
3640 fprintf (f
, "\ntree\n"
3641 "generic_simplify (location_t loc, enum tree_code code, "
3642 "tree type ATTRIBUTE_UNUSED");
3643 for (unsigned i
= 0; i
< n
; ++i
)
3644 fprintf (f
, ", tree op%d", i
);
3649 fprintf (f
, " switch (code.get_rep())\n"
3652 fprintf (f
, " switch (code)\n"
3654 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3656 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3657 expr
*e
= static_cast<expr
*>(dop
->op
);
3658 if (e
->ops
.length () != n
3659 /* Builtin simplifications are somewhat premature on
3660 GENERIC. The following drops patterns with outermost
3661 calls. It's easy to emit overloads for function code
3662 though if necessary. */
3664 && e
->operation
->kind
!= id_base::CODE
))
3667 if (*e
->operation
== CONVERT_EXPR
3668 || *e
->operation
== NOP_EXPR
)
3669 fprintf (f
, " CASE_CONVERT:\n");
3671 fprintf (f
, " case %s%s:\n",
3672 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3675 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3676 "seq, valueize, code, type", e
->operation
->id
);
3678 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3680 for (unsigned i
= 0; i
< n
; ++i
)
3681 fprintf (f
, ", op%d", i
);
3682 fprintf (f
, ");\n");
3684 fprintf (f
, " default:;\n"
3688 fprintf (f
, " return false;\n");
3690 fprintf (f
, " return NULL_TREE;\n");
3695 /* Output code to implement the predicate P from the decision tree DT. */
3698 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3700 fprintf (f
, "\nbool\n"
3701 "%s%s (tree t%s%s)\n"
3702 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3703 p
->nargs
> 0 ? ", tree *res_ops" : "",
3704 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3705 /* Conveniently make 'type' available. */
3706 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3709 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3710 dt
.root
->gen_kids (f
, 2, gimple
);
3712 fprintf_indent (f
, 2, "return false;\n"
3716 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3719 write_header (FILE *f
, const char *head
)
3721 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3722 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3724 /* Include the header instead of writing it awkwardly quoted here. */
3725 fprintf (f
, "\n#include \"%s\"\n", head
);
3735 parser (cpp_reader
*);
3738 const cpp_token
*next ();
3739 const cpp_token
*peek (unsigned = 1);
3740 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3741 const cpp_token
*expect (enum cpp_ttype
);
3742 const cpp_token
*eat_token (enum cpp_ttype
);
3743 const char *get_string ();
3744 const char *get_ident ();
3745 const cpp_token
*eat_ident (const char *);
3746 const char *get_number ();
3748 unsigned get_internal_capture_id ();
3750 id_base
*parse_operation ();
3751 operand
*parse_capture (operand
*, bool);
3752 operand
*parse_expr ();
3753 c_expr
*parse_c_expr (cpp_ttype
);
3754 operand
*parse_op ();
3756 void record_operlist (source_location
, user_id
*);
3758 void parse_pattern ();
3759 operand
*parse_result (operand
*, predicate_id
*);
3760 void push_simplify (simplify::simplify_kind
,
3761 vec
<simplify
*>&, operand
*, operand
*);
3762 void parse_simplify (simplify::simplify_kind
,
3763 vec
<simplify
*>&, predicate_id
*, operand
*);
3764 void parse_for (source_location
);
3765 void parse_if (source_location
);
3766 void parse_predicates (source_location
);
3767 void parse_operator_list (source_location
);
3769 void finish_match_operand (operand
*);
3772 vec
<c_expr
*> active_ifs
;
3773 vec
<vec
<user_id
*> > active_fors
;
3774 hash_set
<user_id
*> *oper_lists_set
;
3775 vec
<user_id
*> oper_lists
;
3777 cid_map_t
*capture_ids
;
3780 vec
<simplify
*> simplifiers
;
3781 vec
<predicate_id
*> user_predicates
;
3782 bool parsing_match_operand
;
3785 /* Lexing helpers. */
3787 /* Read the next non-whitespace token from R. */
3792 const cpp_token
*token
;
3795 token
= cpp_get_token (r
);
3797 while (token
->type
== CPP_PADDING
3798 && token
->type
!= CPP_EOF
);
3802 /* Peek at the next non-whitespace token from R. */
3805 parser::peek (unsigned num
)
3807 const cpp_token
*token
;
3811 token
= cpp_peek_token (r
, i
++);
3813 while ((token
->type
== CPP_PADDING
3814 && token
->type
!= CPP_EOF
)
3816 /* If we peek at EOF this is a fatal error as it leaves the
3817 cpp_reader in unusable state. Assume we really wanted a
3818 token and thus this EOF is unexpected. */
3819 if (token
->type
== CPP_EOF
)
3820 fatal_at (token
, "unexpected end of file");
3824 /* Peek at the next identifier token (or return NULL if the next
3825 token is not an identifier or equal to ID if supplied). */
3828 parser::peek_ident (const char *id
, unsigned num
)
3830 const cpp_token
*token
= peek (num
);
3831 if (token
->type
!= CPP_NAME
)
3837 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3838 if (strcmp (id
, t
) == 0)
3844 /* Read the next token from R and assert it is of type TK. */
3847 parser::expect (enum cpp_ttype tk
)
3849 const cpp_token
*token
= next ();
3850 if (token
->type
!= tk
)
3851 fatal_at (token
, "expected %s, got %s",
3852 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3857 /* Consume the next token from R and assert it is of type TK. */
3860 parser::eat_token (enum cpp_ttype tk
)
3865 /* Read the next token from R and assert it is of type CPP_STRING and
3866 return its value. */
3869 parser::get_string ()
3871 const cpp_token
*token
= expect (CPP_STRING
);
3872 return (const char *)token
->val
.str
.text
;
3875 /* Read the next token from R and assert it is of type CPP_NAME and
3876 return its value. */
3879 parser::get_ident ()
3881 const cpp_token
*token
= expect (CPP_NAME
);
3882 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3885 /* Eat an identifier token with value S from R. */
3888 parser::eat_ident (const char *s
)
3890 const cpp_token
*token
= peek ();
3891 const char *t
= get_ident ();
3892 if (strcmp (s
, t
) != 0)
3893 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3897 /* Read the next token from R and assert it is of type CPP_NUMBER and
3898 return its value. */
3901 parser::get_number ()
3903 const cpp_token
*token
= expect (CPP_NUMBER
);
3904 return (const char *)token
->val
.str
.text
;
3907 /* Return a capture ID that can be used internally. */
3910 parser::get_internal_capture_id ()
3912 unsigned newid
= capture_ids
->elements ();
3913 /* Big enough for a 32-bit UINT_MAX plus prefix. */
3916 sprintf (id
, "__%u", newid
);
3917 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3919 fatal ("reserved capture id '%s' already used", id
);
3923 /* Record an operator-list use for transparent for handling. */
3926 parser::record_operlist (source_location loc
, user_id
*p
)
3928 if (!oper_lists_set
->add (p
))
3930 if (!oper_lists
.is_empty ()
3931 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3932 fatal_at (loc
, "User-defined operator list does not have the "
3933 "same number of entries as others used in the pattern");
3934 oper_lists
.safe_push (p
);
3938 /* Parse the operator ID, special-casing convert?, convert1? and
3942 parser::parse_operation ()
3944 const cpp_token
*id_tok
= peek ();
3945 const char *id
= get_ident ();
3946 const cpp_token
*token
= peek ();
3947 if (strcmp (id
, "convert0") == 0)
3948 fatal_at (id_tok
, "use 'convert?' here");
3949 else if (strcmp (id
, "view_convert0") == 0)
3950 fatal_at (id_tok
, "use 'view_convert?' here");
3951 if (token
->type
== CPP_QUERY
3952 && !(token
->flags
& PREV_WHITE
))
3954 if (strcmp (id
, "convert") == 0)
3956 else if (strcmp (id
, "convert1") == 0)
3958 else if (strcmp (id
, "convert2") == 0)
3960 else if (strcmp (id
, "view_convert") == 0)
3961 id
= "view_convert0";
3962 else if (strcmp (id
, "view_convert1") == 0)
3964 else if (strcmp (id
, "view_convert2") == 0)
3967 fatal_at (id_tok
, "non-convert operator conditionalized");
3969 if (!parsing_match_operand
)
3970 fatal_at (id_tok
, "conditional convert can only be used in "
3971 "match expression");
3972 eat_token (CPP_QUERY
);
3974 else if (strcmp (id
, "convert1") == 0
3975 || strcmp (id
, "convert2") == 0
3976 || strcmp (id
, "view_convert1") == 0
3977 || strcmp (id
, "view_convert2") == 0)
3978 fatal_at (id_tok
, "expected '?' after conditional operator");
3979 id_base
*op
= get_operator (id
);
3981 fatal_at (id_tok
, "unknown operator %s", id
);
3983 user_id
*p
= dyn_cast
<user_id
*> (op
);
3984 if (p
&& p
->is_oper_list
)
3986 if (active_fors
.length() == 0)
3987 record_operlist (id_tok
->src_loc
, p
);
3989 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3995 capture = '@'<number> */
3998 parser::parse_capture (operand
*op
, bool require_existing
)
4000 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4001 const cpp_token
*token
= peek ();
4002 const char *id
= NULL
;
4003 bool value_match
= false;
4004 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4005 if (token
->type
== CPP_ATSIGN
4006 && ! (token
->flags
& PREV_WHITE
)
4007 && parsing_match_operand
)
4009 eat_token (CPP_ATSIGN
);
4013 if (token
->type
== CPP_NUMBER
)
4015 else if (token
->type
== CPP_NAME
)
4018 fatal_at (token
, "expected number or identifier");
4019 unsigned next_id
= capture_ids
->elements ();
4021 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4024 if (require_existing
)
4025 fatal_at (src_loc
, "unknown capture id");
4028 return new capture (src_loc
, num
, op
, value_match
);
4031 /* Parse an expression
4032 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4035 parser::parse_expr ()
4037 const cpp_token
*token
= peek ();
4038 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4041 bool is_commutative
= false;
4042 bool force_capture
= false;
4043 const char *expr_type
= NULL
;
4045 if (token
->type
== CPP_COLON
4046 && !(token
->flags
& PREV_WHITE
))
4048 eat_token (CPP_COLON
);
4050 if (token
->type
== CPP_NAME
4051 && !(token
->flags
& PREV_WHITE
))
4053 const char *s
= get_ident ();
4054 if (!parsing_match_operand
)
4064 = dyn_cast
<operator_id
*> (e
->operation
))
4066 if (!commutative_tree_code (p
->code
)
4067 && !comparison_code_p (p
->code
))
4068 fatal_at (token
, "operation is not commutative");
4070 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4071 for (unsigned i
= 0;
4072 i
< p
->substitutes
.length (); ++i
)
4075 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4077 if (!commutative_tree_code (q
->code
)
4078 && !comparison_code_p (q
->code
))
4079 fatal_at (token
, "operation %s is not "
4080 "commutative", q
->id
);
4083 is_commutative
= true;
4085 else if (*sp
== 'C')
4086 is_commutative
= true;
4087 else if (*sp
== 's')
4089 e
->force_single_use
= true;
4090 force_capture
= true;
4093 fatal_at (token
, "flag %c not recognized", *sp
);
4100 fatal_at (token
, "expected flag or type specifying identifier");
4103 if (token
->type
== CPP_ATSIGN
4104 && !(token
->flags
& PREV_WHITE
))
4105 op
= parse_capture (e
, false);
4106 else if (force_capture
)
4108 unsigned num
= get_internal_capture_id ();
4109 op
= new capture (token
->src_loc
, num
, e
, false);
4115 const cpp_token
*token
= peek ();
4116 if (token
->type
== CPP_CLOSE_PAREN
)
4118 if (e
->operation
->nargs
!= -1
4119 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4120 fatal_at (token
, "'%s' expects %u operands, not %u",
4121 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4124 if (e
->ops
.length () == 2)
4125 e
->is_commutative
= true;
4127 fatal_at (token
, "only binary operators or function with "
4128 "two arguments can be marked commutative");
4130 e
->expr_type
= expr_type
;
4133 else if (!(token
->flags
& PREV_WHITE
))
4134 fatal_at (token
, "expected expression operand");
4136 e
->append_op (parse_op ());
4141 /* Lex native C code delimited by START recording the preprocessing tokens
4142 for later processing.
4143 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4146 parser::parse_c_expr (cpp_ttype start
)
4148 const cpp_token
*token
;
4151 vec
<cpp_token
> code
= vNULL
;
4152 unsigned nr_stmts
= 0;
4153 source_location loc
= eat_token (start
)->src_loc
;
4154 if (start
== CPP_OPEN_PAREN
)
4155 end
= CPP_CLOSE_PAREN
;
4156 else if (start
== CPP_OPEN_BRACE
)
4157 end
= CPP_CLOSE_BRACE
;
4165 /* Count brace pairs to find the end of the expr to match. */
4166 if (token
->type
== start
)
4168 else if (token
->type
== end
4171 else if (token
->type
== CPP_EOF
)
4172 fatal_at (token
, "unexpected end of file");
4174 /* This is a lame way of counting the number of statements. */
4175 if (token
->type
== CPP_SEMICOLON
)
4178 /* If this is possibly a user-defined identifier mark it used. */
4179 if (token
->type
== CPP_NAME
)
4181 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4182 (token
->val
.node
.node
)->ident
.str
);
4184 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4185 record_operlist (token
->src_loc
, p
);
4188 /* Record the token. */
4189 code
.safe_push (*token
);
4192 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4195 /* Parse an operand which is either an expression, a predicate or
4196 a standalone capture.
4197 op = predicate | expr | c_expr | capture */
4202 const cpp_token
*token
= peek ();
4203 struct operand
*op
= NULL
;
4204 if (token
->type
== CPP_OPEN_PAREN
)
4206 eat_token (CPP_OPEN_PAREN
);
4208 eat_token (CPP_CLOSE_PAREN
);
4210 else if (token
->type
== CPP_OPEN_BRACE
)
4212 op
= parse_c_expr (CPP_OPEN_BRACE
);
4216 /* Remaining ops are either empty or predicates */
4217 if (token
->type
== CPP_NAME
)
4219 const char *id
= get_ident ();
4220 id_base
*opr
= get_operator (id
);
4222 fatal_at (token
, "expected predicate name");
4223 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4225 if (code
->nargs
!= 0)
4226 fatal_at (token
, "using an operator with operands as predicate");
4227 /* Parse the zero-operand operator "predicates" as
4229 op
= new expr (opr
, token
->src_loc
);
4231 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4233 if (code
->nargs
!= 0)
4234 fatal_at (token
, "using an operator with operands as predicate");
4235 /* Parse the zero-operand operator "predicates" as
4237 op
= new expr (opr
, token
->src_loc
);
4239 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4240 op
= new predicate (p
, token
->src_loc
);
4242 fatal_at (token
, "using an unsupported operator as predicate");
4243 if (!parsing_match_operand
)
4244 fatal_at (token
, "predicates are only allowed in match expression");
4246 if (token
->flags
& PREV_WHITE
)
4249 else if (token
->type
!= CPP_COLON
4250 && token
->type
!= CPP_ATSIGN
)
4251 fatal_at (token
, "expected expression or predicate");
4252 /* optionally followed by a capture and a predicate. */
4253 if (token
->type
== CPP_COLON
)
4254 fatal_at (token
, "not implemented: predicate on leaf operand");
4255 if (token
->type
== CPP_ATSIGN
)
4256 op
= parse_capture (op
, !parsing_match_operand
);
4262 /* Create a new simplify from the current parsing state and MATCH,
4263 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4266 parser::push_simplify (simplify::simplify_kind kind
,
4267 vec
<simplify
*>& simplifiers
,
4268 operand
*match
, operand
*result
)
4270 /* Build and push a temporary for operator list uses in expressions. */
4271 if (!oper_lists
.is_empty ())
4272 active_fors
.safe_push (oper_lists
);
4274 simplifiers
.safe_push
4275 (new simplify (kind
, match
, result
,
4276 active_fors
.copy (), capture_ids
));
4278 if (!oper_lists
.is_empty ())
4283 <result-op> = <op> | <if> | <with>
4284 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4285 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4289 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4291 const cpp_token
*token
= peek ();
4292 if (token
->type
!= CPP_OPEN_PAREN
)
4295 eat_token (CPP_OPEN_PAREN
);
4296 if (peek_ident ("if"))
4299 if_expr
*ife
= new if_expr (token
->src_loc
);
4300 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4301 if (peek ()->type
== CPP_OPEN_PAREN
)
4303 ife
->trueexpr
= parse_result (result
, matcher
);
4304 if (peek ()->type
== CPP_OPEN_PAREN
)
4305 ife
->falseexpr
= parse_result (result
, matcher
);
4306 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4307 ife
->falseexpr
= parse_op ();
4309 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4311 ife
->trueexpr
= parse_op ();
4312 if (peek ()->type
== CPP_OPEN_PAREN
)
4313 ife
->falseexpr
= parse_result (result
, matcher
);
4314 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4315 ife
->falseexpr
= parse_op ();
4317 /* If this if is immediately closed then it contains a
4318 manual matcher or is part of a predicate definition. */
4319 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4322 fatal_at (peek (), "manual transform not implemented");
4323 ife
->trueexpr
= result
;
4325 eat_token (CPP_CLOSE_PAREN
);
4328 else if (peek_ident ("with"))
4331 with_expr
*withe
= new with_expr (token
->src_loc
);
4332 /* Parse (with c-expr expr) as (if-with (true) expr). */
4333 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4334 withe
->with
->nr_stmts
= 0;
4335 withe
->subexpr
= parse_result (result
, matcher
);
4336 eat_token (CPP_CLOSE_PAREN
);
4339 else if (peek_ident ("switch"))
4341 token
= eat_ident ("switch");
4342 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4344 if_expr
*ife
= new if_expr (ifloc
);
4346 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4347 if (peek ()->type
== CPP_OPEN_PAREN
)
4348 ife
->trueexpr
= parse_result (result
, matcher
);
4350 ife
->trueexpr
= parse_op ();
4351 eat_token (CPP_CLOSE_PAREN
);
4352 if (peek ()->type
!= CPP_OPEN_PAREN
4353 || !peek_ident ("if", 2))
4354 fatal_at (token
, "switch can be implemented with a single if");
4355 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4357 if (peek ()->type
== CPP_OPEN_PAREN
)
4359 if (peek_ident ("if", 2))
4361 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4363 ife
->falseexpr
= new if_expr (ifloc
);
4364 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4365 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4366 if (peek ()->type
== CPP_OPEN_PAREN
)
4367 ife
->trueexpr
= parse_result (result
, matcher
);
4369 ife
->trueexpr
= parse_op ();
4370 eat_token (CPP_CLOSE_PAREN
);
4374 /* switch default clause */
4375 ife
->falseexpr
= parse_result (result
, matcher
);
4376 eat_token (CPP_CLOSE_PAREN
);
4382 /* switch default clause */
4383 ife
->falseexpr
= parse_op ();
4384 eat_token (CPP_CLOSE_PAREN
);
4388 eat_token (CPP_CLOSE_PAREN
);
4393 operand
*op
= result
;
4396 eat_token (CPP_CLOSE_PAREN
);
4402 simplify = 'simplify' <expr> <result-op>
4404 match = 'match' <ident> <expr> [<result-op>]
4405 and fill SIMPLIFIERS with the results. */
4408 parser::parse_simplify (simplify::simplify_kind kind
,
4409 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4412 /* Reset the capture map. */
4414 capture_ids
= new cid_map_t
;
4415 /* Reset oper_lists and set. */
4416 hash_set
<user_id
*> olist
;
4417 oper_lists_set
= &olist
;
4420 const cpp_token
*loc
= peek ();
4421 parsing_match_operand
= true;
4422 struct operand
*match
= parse_op ();
4423 finish_match_operand (match
);
4424 parsing_match_operand
= false;
4425 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4426 fatal_at (loc
, "outermost expression cannot be captured");
4427 if (match
->type
== operand::OP_EXPR
4428 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4429 fatal_at (loc
, "outermost expression cannot be a predicate");
4431 /* Splice active_ifs onto result and continue parsing the
4433 if_expr
*active_if
= NULL
;
4434 for (int i
= active_ifs
.length (); i
> 0; --i
)
4436 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4437 ifc
->cond
= active_ifs
[i
-1];
4438 ifc
->trueexpr
= active_if
;
4441 if_expr
*outermost_if
= active_if
;
4442 while (active_if
&& active_if
->trueexpr
)
4443 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4445 const cpp_token
*token
= peek ();
4447 /* If this if is immediately closed then it is part of a predicate
4448 definition. Push it. */
4449 if (token
->type
== CPP_CLOSE_PAREN
)
4452 fatal_at (token
, "expected transform expression");
4455 active_if
->trueexpr
= result
;
4456 result
= outermost_if
;
4458 push_simplify (kind
, simplifiers
, match
, result
);
4462 operand
*tem
= parse_result (result
, matcher
);
4465 active_if
->trueexpr
= tem
;
4466 result
= outermost_if
;
4471 push_simplify (kind
, simplifiers
, match
, result
);
4474 /* Parsing of the outer control structures. */
4476 /* Parse a for expression
4477 for = '(' 'for' <subst>... <pattern> ')'
4478 subst = <ident> '(' <ident>... ')' */
4481 parser::parse_for (source_location
)
4483 auto_vec
<const cpp_token
*> user_id_tokens
;
4484 vec
<user_id
*> user_ids
= vNULL
;
4485 const cpp_token
*token
;
4486 unsigned min_n_opers
= 0, max_n_opers
= 0;
4491 if (token
->type
!= CPP_NAME
)
4494 /* Insert the user defined operators into the operator hash. */
4495 const char *id
= get_ident ();
4496 if (get_operator (id
, true) != NULL
)
4497 fatal_at (token
, "operator already defined");
4498 user_id
*op
= new user_id (id
);
4499 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4501 user_ids
.safe_push (op
);
4502 user_id_tokens
.safe_push (token
);
4504 eat_token (CPP_OPEN_PAREN
);
4507 while ((token
= peek_ident ()) != 0)
4509 const char *oper
= get_ident ();
4510 id_base
*idb
= get_operator (oper
, true);
4512 fatal_at (token
, "no such operator '%s'", oper
);
4513 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4514 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4515 || *idb
== VIEW_CONVERT2
)
4516 fatal_at (token
, "conditional operators cannot be used inside for");
4520 else if (idb
->nargs
== -1)
4522 else if (idb
->nargs
!= arity
)
4523 fatal_at (token
, "operator '%s' with arity %d does not match "
4524 "others with arity %d", oper
, idb
->nargs
, arity
);
4526 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4529 if (p
->is_oper_list
)
4530 op
->substitutes
.safe_splice (p
->substitutes
);
4532 fatal_at (token
, "iterator cannot be used as operator-list");
4535 op
->substitutes
.safe_push (idb
);
4538 token
= expect (CPP_CLOSE_PAREN
);
4540 unsigned nsubstitutes
= op
->substitutes
.length ();
4541 if (nsubstitutes
== 0)
4542 fatal_at (token
, "A user-defined operator must have at least "
4543 "one substitution");
4544 if (max_n_opers
== 0)
4546 min_n_opers
= nsubstitutes
;
4547 max_n_opers
= nsubstitutes
;
4551 if (nsubstitutes
% min_n_opers
!= 0
4552 && min_n_opers
% nsubstitutes
!= 0)
4553 fatal_at (token
, "All user-defined identifiers must have a "
4554 "multiple number of operator substitutions of the "
4555 "smallest number of substitutions");
4556 if (nsubstitutes
< min_n_opers
)
4557 min_n_opers
= nsubstitutes
;
4558 else if (nsubstitutes
> max_n_opers
)
4559 max_n_opers
= nsubstitutes
;
4563 unsigned n_ids
= user_ids
.length ();
4565 fatal_at (token
, "for requires at least one user-defined identifier");
4568 if (token
->type
== CPP_CLOSE_PAREN
)
4569 fatal_at (token
, "no pattern defined in for");
4571 active_fors
.safe_push (user_ids
);
4575 if (token
->type
== CPP_CLOSE_PAREN
)
4581 /* Remove user-defined operators from the hash again. */
4582 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4584 if (!user_ids
[i
]->used
)
4585 warning_at (user_id_tokens
[i
],
4586 "operator %s defined but not used", user_ids
[i
]->id
);
4587 operators
->remove_elt (user_ids
[i
]);
4591 /* Parse an identifier associated with a list of operators.
4592 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4595 parser::parse_operator_list (source_location
)
4597 const cpp_token
*token
= peek ();
4598 const char *id
= get_ident ();
4600 if (get_operator (id
, true) != 0)
4601 fatal_at (token
, "operator %s already defined", id
);
4603 user_id
*op
= new user_id (id
, true);
4606 while ((token
= peek_ident ()) != 0)
4609 const char *oper
= get_ident ();
4610 id_base
*idb
= get_operator (oper
, true);
4613 fatal_at (token
, "no such operator '%s'", oper
);
4617 else if (idb
->nargs
== -1)
4619 else if (arity
!= idb
->nargs
)
4620 fatal_at (token
, "operator '%s' with arity %d does not match "
4621 "others with arity %d", oper
, idb
->nargs
, arity
);
4623 /* We allow composition of multiple operator lists. */
4624 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4625 op
->substitutes
.safe_splice (p
->substitutes
);
4627 op
->substitutes
.safe_push (idb
);
4630 // Check that there is no junk after id-list
4632 if (token
->type
!= CPP_CLOSE_PAREN
)
4633 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4635 if (op
->substitutes
.length () == 0)
4636 fatal_at (token
, "operator-list cannot be empty");
4639 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4643 /* Parse an outer if expression.
4644 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4647 parser::parse_if (source_location
)
4649 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4651 const cpp_token
*token
= peek ();
4652 if (token
->type
== CPP_CLOSE_PAREN
)
4653 fatal_at (token
, "no pattern defined in if");
4655 active_ifs
.safe_push (ifexpr
);
4658 const cpp_token
*token
= peek ();
4659 if (token
->type
== CPP_CLOSE_PAREN
)
4667 /* Parse a list of predefined predicate identifiers.
4668 preds = '(' 'define_predicates' <ident>... ')' */
4671 parser::parse_predicates (source_location
)
4675 const cpp_token
*token
= peek ();
4676 if (token
->type
!= CPP_NAME
)
4679 add_predicate (get_ident ());
4684 /* Parse outer control structures.
4685 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4688 parser::parse_pattern ()
4690 /* All clauses start with '('. */
4691 eat_token (CPP_OPEN_PAREN
);
4692 const cpp_token
*token
= peek ();
4693 const char *id
= get_ident ();
4694 if (strcmp (id
, "simplify") == 0)
4696 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4699 else if (strcmp (id
, "match") == 0)
4701 bool with_args
= false;
4702 source_location e_loc
= peek ()->src_loc
;
4703 if (peek ()->type
== CPP_OPEN_PAREN
)
4705 eat_token (CPP_OPEN_PAREN
);
4708 const char *name
= get_ident ();
4709 id_base
*id
= get_operator (name
);
4713 p
= add_predicate (name
);
4714 user_predicates
.safe_push (p
);
4716 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4719 fatal_at (token
, "cannot add a match to a non-predicate ID");
4720 /* Parse (match <id> <arg>... (match-expr)) here. */
4724 capture_ids
= new cid_map_t
;
4725 e
= new expr (p
, e_loc
);
4726 while (peek ()->type
== CPP_ATSIGN
)
4727 e
->append_op (parse_capture (NULL
, false));
4728 eat_token (CPP_CLOSE_PAREN
);
4731 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4732 || (!e
&& p
->nargs
!= 0)))
4733 fatal_at (token
, "non-matching number of match operands");
4734 p
->nargs
= e
? e
->ops
.length () : 0;
4735 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4738 else if (strcmp (id
, "for") == 0)
4739 parse_for (token
->src_loc
);
4740 else if (strcmp (id
, "if") == 0)
4741 parse_if (token
->src_loc
);
4742 else if (strcmp (id
, "define_predicates") == 0)
4744 if (active_ifs
.length () > 0
4745 || active_fors
.length () > 0)
4746 fatal_at (token
, "define_predicates inside if or for is not supported");
4747 parse_predicates (token
->src_loc
);
4749 else if (strcmp (id
, "define_operator_list") == 0)
4751 if (active_ifs
.length () > 0
4752 || active_fors
.length () > 0)
4753 fatal_at (token
, "operator-list inside if or for is not supported");
4754 parse_operator_list (token
->src_loc
);
4757 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4758 active_ifs
.length () == 0 && active_fors
.length () == 0
4759 ? "'define_predicates', " : "");
4761 eat_token (CPP_CLOSE_PAREN
);
4764 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4768 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4773 if (capture
*c
= dyn_cast
<capture
*> (op
))
4775 cpts
[c
->where
].safe_push (c
);
4776 walk_captures (c
->what
, cpts
);
4778 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4779 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4780 walk_captures (e
->ops
[i
], cpts
);
4783 /* Finish up OP which is a match operand. */
4786 parser::finish_match_operand (operand
*op
)
4788 /* Look for matching captures, diagnose mis-uses of @@ and apply
4789 early lowering and distribution of value_match. */
4790 auto_vec
<vec
<capture
*> > cpts
;
4791 cpts
.safe_grow_cleared (capture_ids
->elements ());
4792 walk_captures (op
, cpts
);
4793 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4795 capture
*value_match
= NULL
;
4796 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4798 if (cpts
[i
][j
]->value_match
)
4801 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4802 value_match
= cpts
[i
][j
];
4805 if (cpts
[i
].length () == 1 && value_match
)
4806 fatal_at (value_match
->location
, "@@ without a matching capture");
4809 /* Duplicate prevailing capture with the existing ID, create
4810 a fake ID and rewrite all captures to use it. This turns
4811 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4812 value_match
->what
= new capture (value_match
->location
,
4814 value_match
->what
, false);
4815 /* Create a fake ID and rewrite all captures to use it. */
4816 unsigned newid
= get_internal_capture_id ();
4817 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4819 cpts
[i
][j
]->where
= newid
;
4820 cpts
[i
][j
]->value_match
= true;
4827 /* Main entry of the parser. Repeatedly parse outer control structures. */
4829 parser::parser (cpp_reader
*r_
)
4833 active_fors
= vNULL
;
4834 simplifiers
= vNULL
;
4835 oper_lists_set
= NULL
;
4838 user_predicates
= vNULL
;
4839 parsing_match_operand
= false;
4841 const cpp_token
*token
= next ();
4842 while (token
->type
!= CPP_EOF
)
4844 _cpp_backup_tokens (r
, 1);
4851 /* Helper for the linemap code. */
4854 round_alloc_size (size_t s
)
4860 /* The genmatch generator progam. It reads from a pattern description
4861 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4864 main (int argc
, char **argv
)
4868 progname
= "genmatch";
4874 char *input
= argv
[argc
-1];
4875 for (int i
= 1; i
< argc
- 1; ++i
)
4877 if (strcmp (argv
[i
], "--gimple") == 0)
4879 else if (strcmp (argv
[i
], "--generic") == 0)
4881 else if (strcmp (argv
[i
], "-v") == 0)
4883 else if (strcmp (argv
[i
], "-vv") == 0)
4887 fprintf (stderr
, "Usage: genmatch "
4888 "[--gimple] [--generic] [-v[v]] input\n");
4893 line_table
= XCNEW (struct line_maps
);
4894 linemap_init (line_table
, 0);
4895 line_table
->reallocator
= xrealloc
;
4896 line_table
->round_alloc_size
= round_alloc_size
;
4898 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4899 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4900 cb
->error
= error_cb
;
4902 /* Add the build directory to the #include "" search path. */
4903 cpp_dir
*dir
= XCNEW (cpp_dir
);
4904 dir
->name
= getpwd ();
4906 dir
->name
= ASTRDUP (".");
4907 cpp_set_include_chains (r
, dir
, NULL
, false);
4909 if (!cpp_read_main_file (r
, input
))
4911 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4912 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4914 null_id
= new id_base (id_base::NULL_ID
, "null");
4916 /* Pre-seed operators. */
4917 operators
= new hash_table
<id_base
> (1024);
4918 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4919 add_operator (SYM, # SYM, # TYPE, NARGS);
4920 #define END_OF_BASE_TREE_CODES
4922 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
4923 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
4924 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
4925 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
4926 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
4927 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
4928 #undef END_OF_BASE_TREE_CODES
4931 /* Pre-seed builtin functions.
4932 ??? Cannot use N (name) as that is targetm.emultls.get_address
4933 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4934 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4935 add_function (ENUM, "CFN_" # ENUM);
4936 #include "builtins.def"
4938 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
4939 add_function (IFN_##CODE, "CFN_" #CODE);
4940 #include "internal-fn.def"
4946 write_header (stdout
, "gimple-match-head.c");
4948 write_header (stdout
, "generic-match-head.c");
4950 /* Go over all predicates defined with patterns and perform
4951 lowering and code generation. */
4952 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4954 predicate_id
*pred
= p
.user_predicates
[i
];
4955 lower (pred
->matchers
, gimple
);
4958 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4959 print_matches (pred
->matchers
[i
]);
4962 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4963 dt
.insert (pred
->matchers
[i
], i
);
4968 write_predicate (stdout
, pred
, dt
, gimple
);
4971 /* Lower the main simplifiers and generate code for them. */
4972 lower (p
.simplifiers
, gimple
);
4975 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4976 print_matches (p
.simplifiers
[i
]);
4979 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4980 dt
.insert (p
.simplifiers
[i
], i
);
4985 dt
.gen (stdout
, gimple
);
4988 cpp_finish (r
, NULL
);