1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2017 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static struct line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 source_location instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (source_location loc
)
66 const struct line_map_ordinary
*map
;
67 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
68 return linemap_expand_location (line_table
, map
, loc
);
72 #if GCC_VERSION >= 4001
73 __attribute__((format (printf
, 5, 0)))
75 error_cb (cpp_reader
*, int errtype
, int, rich_location
*richloc
,
76 const char *msg
, va_list *ap
)
78 const line_map_ordinary
*map
;
79 source_location location
= richloc
->get_loc ();
80 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
81 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
82 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
83 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
84 vfprintf (stderr
, msg
, *ap
);
85 fprintf (stderr
, "\n");
86 FILE *f
= fopen (loc
.file
, "r");
92 if (!fgets (buf
, 128, f
))
94 if (buf
[strlen (buf
) - 1] != '\n')
101 fprintf (stderr
, "%s", buf
);
102 for (int i
= 0; i
< loc
.column
- 1; ++i
)
105 fputc ('\n', stderr
);
110 if (errtype
== CPP_DL_FATAL
)
116 #if GCC_VERSION >= 4001
117 __attribute__((format (printf
, 2, 3)))
119 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
121 rich_location
richloc (line_table
, tk
->src_loc
);
124 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
129 #if GCC_VERSION >= 4001
130 __attribute__((format (printf
, 2, 3)))
132 fatal_at (source_location loc
, const char *msg
, ...)
134 rich_location
richloc (line_table
, loc
);
137 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
142 #if GCC_VERSION >= 4001
143 __attribute__((format (printf
, 2, 3)))
145 warning_at (const cpp_token
*tk
, const char *msg
, ...)
147 rich_location
richloc (line_table
, tk
->src_loc
);
150 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
155 #if GCC_VERSION >= 4001
156 __attribute__((format (printf
, 2, 3)))
158 warning_at (source_location loc
, const char *msg
, ...)
160 rich_location
richloc (line_table
, loc
);
163 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
167 /* Like fprintf, but print INDENT spaces at the beginning. */
170 #if GCC_VERSION >= 4001
171 __attribute__((format (printf
, 3, 4)))
173 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
176 for (; indent
>= 8; indent
-= 8)
178 fprintf (f
, "%*s", indent
, "");
179 va_start (ap
, format
);
180 vfprintf (f
, format
, ap
);
185 output_line_directive (FILE *f
, source_location location
,
186 bool dumpfile
= false)
188 const line_map_ordinary
*map
;
189 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
190 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
193 /* When writing to a dumpfile only dump the filename. */
194 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
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. */
2651 fprintf_indent (f
, indent
,
2652 "tree %s = TREE_OPERAND (%s, %i);\n",
2653 child_opname
, opname
, i
);
2656 fprintf_indent (f
, indent
,
2657 "tree %s = TREE_OPERAND "
2658 "(gimple_assign_rhs1 (def), %i);\n",
2660 fprintf_indent (f
, indent
,
2661 "if ((TREE_CODE (%s) == SSA_NAME\n",
2663 fprintf_indent (f
, indent
,
2664 " || is_gimple_min_invariant (%s))\n",
2666 fprintf_indent (f
, indent
,
2667 " && (%s = do_valueize (valueize, %s)))\n",
2668 child_opname
, child_opname
);
2669 fprintf_indent (f
, indent
,
2675 fprintf_indent (f
, indent
,
2676 "tree %s = gimple_assign_rhs%u (def);\n",
2677 child_opname
, i
+ 1);
2680 fprintf_indent (f
, indent
,
2681 "tree %s = gimple_call_arg (def, %u);\n",
2683 fprintf_indent (f
, indent
,
2684 "if ((%s = do_valueize (valueize, %s)))\n",
2685 child_opname
, child_opname
);
2686 fprintf_indent (f
, indent
, " {\n");
2689 /* While the toplevel operands are canonicalized by the caller
2690 after valueizing operands of sub-expressions we have to
2691 re-canonicalize operand order. */
2692 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2694 /* ??? We can't canonicalize tcc_comparison operands here
2695 because that requires changing the comparison code which
2696 we already matched... */
2697 if (commutative_tree_code (code
->code
)
2698 || commutative_ternary_tree_code (code
->code
))
2700 char child_opname0
[20], child_opname1
[20];
2701 gen_opname (child_opname0
, 0);
2702 gen_opname (child_opname1
, 1);
2703 fprintf_indent (f
, indent
,
2704 "if (tree_swap_operands_p (%s, %s))\n",
2705 child_opname0
, child_opname1
);
2706 fprintf_indent (f
, indent
,
2707 " std::swap (%s, %s);\n",
2708 child_opname0
, child_opname1
);
2715 /* Generate GENERIC matching code for the decision tree operand. */
2718 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2720 expr
*e
= static_cast<expr
*> (op
);
2721 unsigned n_ops
= e
->ops
.length ();
2723 for (unsigned i
= 0; i
< n_ops
; ++i
)
2725 char child_opname
[20];
2726 gen_opname (child_opname
, i
);
2728 if (e
->operation
->kind
== id_base::CODE
)
2729 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2730 child_opname
, opname
, i
);
2732 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2733 child_opname
, opname
, i
);
2739 /* Generate matching code for the children of the decision tree node. */
2742 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2744 auto_vec
<dt_operand
*> gimple_exprs
;
2745 auto_vec
<dt_operand
*> generic_exprs
;
2746 auto_vec
<dt_operand
*> fns
;
2747 auto_vec
<dt_operand
*> generic_fns
;
2748 auto_vec
<dt_operand
*> preds
;
2749 auto_vec
<dt_node
*> others
;
2751 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2753 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2755 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2756 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2758 if (e
->ops
.length () == 0
2759 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2760 generic_exprs
.safe_push (op
);
2761 else if (e
->operation
->kind
== id_base::FN
)
2766 generic_fns
.safe_push (op
);
2768 else if (e
->operation
->kind
== id_base::PREDICATE
)
2769 preds
.safe_push (op
);
2772 if (gimple
&& !e
->is_generic
)
2773 gimple_exprs
.safe_push (op
);
2775 generic_exprs
.safe_push (op
);
2778 else if (op
->op
->type
== operand::OP_PREDICATE
)
2779 others
.safe_push (kids
[i
]);
2783 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2784 others
.safe_push (kids
[i
]);
2785 else if (kids
[i
]->type
== dt_node::DT_MATCH
2786 || kids
[i
]->type
== dt_node::DT_TRUE
)
2788 /* A DT_TRUE operand serves as a barrier - generate code now
2789 for what we have collected sofar.
2790 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2791 dependent matches to get out-of-order. Generate code now
2792 for what we have collected sofar. */
2793 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2794 fns
, generic_fns
, preds
, others
);
2795 /* And output the true operand itself. */
2796 kids
[i
]->gen (f
, indent
, gimple
);
2797 gimple_exprs
.truncate (0);
2798 generic_exprs
.truncate (0);
2800 generic_fns
.truncate (0);
2802 others
.truncate (0);
2808 /* Generate code for the remains. */
2809 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2810 fns
, generic_fns
, preds
, others
);
2813 /* Generate matching code for the children of the decision tree node. */
2816 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2817 vec
<dt_operand
*> gimple_exprs
,
2818 vec
<dt_operand
*> generic_exprs
,
2819 vec
<dt_operand
*> fns
,
2820 vec
<dt_operand
*> generic_fns
,
2821 vec
<dt_operand
*> preds
,
2822 vec
<dt_node
*> others
)
2825 char *kid_opname
= buf
;
2827 unsigned exprs_len
= gimple_exprs
.length ();
2828 unsigned gexprs_len
= generic_exprs
.length ();
2829 unsigned fns_len
= fns
.length ();
2830 unsigned gfns_len
= generic_fns
.length ();
2832 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2835 gimple_exprs
[0]->get_name (kid_opname
);
2837 fns
[0]->get_name (kid_opname
);
2839 generic_fns
[0]->get_name (kid_opname
);
2841 generic_exprs
[0]->get_name (kid_opname
);
2843 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2844 fprintf_indent (f
, indent
, " {\n");
2848 if (exprs_len
|| fns_len
)
2850 fprintf_indent (f
, indent
,
2851 "case SSA_NAME:\n");
2852 fprintf_indent (f
, indent
,
2853 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2855 fprintf_indent (f
, indent
,
2857 fprintf_indent (f
, indent
,
2858 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2864 fprintf_indent (f
, indent
,
2865 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2866 fprintf_indent (f
, indent
,
2867 " switch (gimple_assign_rhs_code (def))\n");
2869 fprintf_indent (f
, indent
, "{\n");
2870 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2872 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2873 id_base
*op
= e
->operation
;
2874 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2875 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2877 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2878 fprintf_indent (f
, indent
, " {\n");
2879 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2880 fprintf_indent (f
, indent
, " break;\n");
2881 fprintf_indent (f
, indent
, " }\n");
2883 fprintf_indent (f
, indent
, "default:;\n");
2884 fprintf_indent (f
, indent
, "}\n");
2890 fprintf_indent (f
, indent
,
2891 "%sif (gcall *def = dyn_cast <gcall *>"
2893 exprs_len
? "else " : "");
2894 fprintf_indent (f
, indent
,
2895 " switch (gimple_call_combined_fn (def))\n");
2898 fprintf_indent (f
, indent
, "{\n");
2899 for (unsigned i
= 0; i
< fns_len
; ++i
)
2901 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2902 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2903 fprintf_indent (f
, indent
, " {\n");
2904 fns
[i
]->gen (f
, indent
+ 4, true);
2905 fprintf_indent (f
, indent
, " break;\n");
2906 fprintf_indent (f
, indent
, " }\n");
2909 fprintf_indent (f
, indent
, "default:;\n");
2910 fprintf_indent (f
, indent
, "}\n");
2915 fprintf_indent (f
, indent
, " }\n");
2916 fprintf_indent (f
, indent
, " break;\n");
2919 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2921 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2922 id_base
*op
= e
->operation
;
2923 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2924 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2926 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2927 fprintf_indent (f
, indent
, " {\n");
2928 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2929 fprintf_indent (f
, indent
, " break;\n");
2930 fprintf_indent (f
, indent
, " }\n");
2935 fprintf_indent (f
, indent
,
2936 "case CALL_EXPR:\n");
2937 fprintf_indent (f
, indent
,
2938 " switch (get_call_combined_fn (%s))\n",
2940 fprintf_indent (f
, indent
,
2944 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2946 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2947 gcc_assert (e
->operation
->kind
== id_base::FN
);
2949 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2950 fprintf_indent (f
, indent
, " {\n");
2951 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2952 fprintf_indent (f
, indent
, " break;\n");
2953 fprintf_indent (f
, indent
, " }\n");
2955 fprintf_indent (f
, indent
, "default:;\n");
2958 fprintf_indent (f
, indent
, " }\n");
2959 fprintf_indent (f
, indent
, " break;\n");
2962 /* Close switch (TREE_CODE ()). */
2963 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2966 fprintf_indent (f
, indent
, " default:;\n");
2967 fprintf_indent (f
, indent
, " }\n");
2970 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2972 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2973 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2974 preds
[i
]->get_name (kid_opname
);
2975 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2976 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2977 gimple
? "gimple" : "tree",
2978 p
->id
, kid_opname
, kid_opname
,
2979 gimple
? ", valueize" : "");
2980 fprintf_indent (f
, indent
, " {\n");
2981 for (int j
= 0; j
< p
->nargs
; ++j
)
2983 char child_opname
[20];
2984 preds
[i
]->gen_opname (child_opname
, j
);
2985 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2986 child_opname
, kid_opname
, j
);
2988 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2992 for (unsigned i
= 0; i
< others
.length (); ++i
)
2993 others
[i
]->gen (f
, indent
, gimple
);
2996 /* Generate matching code for the decision tree operand. */
2999 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3004 unsigned n_braces
= 0;
3006 if (type
== DT_OPERAND
)
3009 case operand::OP_PREDICATE
:
3010 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3013 case operand::OP_EXPR
:
3015 n_braces
= gen_gimple_expr (f
, indent
);
3017 n_braces
= gen_generic_expr (f
, indent
, opname
);
3023 else if (type
== DT_TRUE
)
3025 else if (type
== DT_MATCH
)
3026 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3030 indent
+= 4 * n_braces
;
3031 gen_kids (f
, indent
, gimple
);
3033 for (unsigned i
= 0; i
< n_braces
; ++i
)
3038 fprintf_indent (f
, indent
, " }\n");
3043 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3044 step of a '(simplify ...)' or '(match ...)'. This handles everything
3045 that is not part of the decision tree (simplify->match).
3046 Main recursive worker. */
3049 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3053 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3055 fprintf_indent (f
, indent
, "{\n");
3057 output_line_directive (f
, w
->location
);
3058 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3059 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3061 fprintf_indent (f
, indent
, "}\n");
3064 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3066 output_line_directive (f
, ife
->location
);
3067 fprintf_indent (f
, indent
, "if (");
3068 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3070 fprintf_indent (f
, indent
+ 2, "{\n");
3072 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3074 fprintf_indent (f
, indent
+ 2, "}\n");
3077 fprintf_indent (f
, indent
, "else\n");
3078 fprintf_indent (f
, indent
+ 2, "{\n");
3080 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3082 fprintf_indent (f
, indent
+ 2, "}\n");
3088 /* Analyze captures and perform early-outs on the incoming arguments
3089 that cover cases we cannot handle. */
3090 capture_info
cinfo (s
, result
, gimple
);
3091 if (s
->kind
== simplify::SIMPLIFY
)
3095 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3096 if (cinfo
.force_no_side_effects
& (1 << i
))
3098 fprintf_indent (f
, indent
,
3099 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3102 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3103 "forcing toplevel operand to have no "
3106 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3107 if (cinfo
.info
[i
].cse_p
)
3109 else if (cinfo
.info
[i
].force_no_side_effects_p
3110 && (cinfo
.info
[i
].toplevel_msk
3111 & cinfo
.force_no_side_effects
) == 0)
3113 fprintf_indent (f
, indent
,
3114 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3115 "return NULL_TREE;\n", i
);
3117 warning_at (cinfo
.info
[i
].c
->location
,
3118 "forcing captured operand to have no "
3121 else if ((cinfo
.info
[i
].toplevel_msk
3122 & cinfo
.force_no_side_effects
) != 0)
3123 /* Mark capture as having no side-effects if we had to verify
3124 that via forced toplevel operand checks. */
3125 cinfo
.info
[i
].force_no_side_effects_p
= true;
3129 /* Force single-use restriction by only allowing simple
3130 results via setting seq to NULL. */
3131 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3132 bool first_p
= true;
3133 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3134 if (cinfo
.info
[i
].force_single_use
)
3138 fprintf_indent (f
, indent
, "if (lseq\n");
3139 fprintf_indent (f
, indent
, " && (");
3145 fprintf_indent (f
, indent
, " || ");
3147 fprintf (f
, "!single_use (captures[%d])", i
);
3151 fprintf (f
, "))\n");
3152 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3157 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
3158 "fprintf (dump_file, \"Applying pattern ");
3159 output_line_directive (f
,
3160 result
? result
->location
: s
->match
->location
, true);
3161 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3165 /* If there is no result then this is a predicate implementation. */
3166 fprintf_indent (f
, indent
, "return true;\n");
3170 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3171 in outermost position). */
3172 if (result
->type
== operand::OP_EXPR
3173 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3174 result
= as_a
<expr
*> (result
)->ops
[0];
3175 if (result
->type
== operand::OP_EXPR
)
3177 expr
*e
= as_a
<expr
*> (result
);
3178 id_base
*opr
= e
->operation
;
3179 bool is_predicate
= false;
3180 /* When we delay operator substituting during lowering of fors we
3181 make sure that for code-gen purposes the effects of each substitute
3182 are the same. Thus just look at that. */
3183 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3184 opr
= uid
->substitutes
[0];
3185 else if (is_a
<predicate_id
*> (opr
))
3186 is_predicate
= true;
3188 fprintf_indent (f
, indent
, "*res_code = %s;\n",
3189 *e
->operation
== CONVERT_EXPR
3190 ? "NOP_EXPR" : e
->operation
->id
);
3191 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3194 snprintf (dest
, 32, "res_ops[%d]", j
);
3196 = get_operand_type (opr
, j
,
3197 "type", e
->expr_type
,
3198 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
3199 /* We need to expand GENERIC conditions we captured from
3200 COND_EXPRs and we need to unshare them when substituting
3202 int cond_handling
= 0;
3204 cond_handling
= ((*opr
== COND_EXPR
3205 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3206 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3207 &cinfo
, indexes
, cond_handling
);
3210 /* Re-fold the toplevel result. It's basically an embedded
3211 gimple_build w/o actually building the stmt. */
3213 fprintf_indent (f
, indent
,
3214 "gimple_resimplify%d (lseq, res_code, type, "
3215 "res_ops, valueize);\n", e
->ops
.length ());
3217 else if (result
->type
== operand::OP_CAPTURE
3218 || result
->type
== operand::OP_C_EXPR
)
3220 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
3222 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
3223 if (is_a
<capture
*> (result
)
3224 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3226 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3227 with substituting a capture of that. */
3228 fprintf_indent (f
, indent
,
3229 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3230 fprintf_indent (f
, indent
,
3232 fprintf_indent (f
, indent
,
3233 " tree tem = res_ops[0];\n");
3234 fprintf_indent (f
, indent
,
3235 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3236 fprintf_indent (f
, indent
,
3237 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3238 fprintf_indent (f
, indent
,
3244 fprintf_indent (f
, indent
, "return true;\n");
3248 bool is_predicate
= false;
3249 if (result
->type
== operand::OP_EXPR
)
3251 expr
*e
= as_a
<expr
*> (result
);
3252 id_base
*opr
= e
->operation
;
3253 /* When we delay operator substituting during lowering of fors we
3254 make sure that for code-gen purposes the effects of each substitute
3255 are the same. Thus just look at that. */
3256 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3257 opr
= uid
->substitutes
[0];
3258 else if (is_a
<predicate_id
*> (opr
))
3259 is_predicate
= true;
3260 /* Search for captures used multiple times in the result expression
3261 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3262 original expression. */
3264 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3266 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3267 || cinfo
.info
[i
].cse_p
)
3269 if (cinfo
.info
[i
].result_use_count
3270 > cinfo
.info
[i
].match_use_count
)
3271 fprintf_indent (f
, indent
,
3272 "if (! tree_invariant_p (captures[%d])) "
3273 "return NULL_TREE;\n", i
);
3275 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3279 snprintf (dest
, 32, "res_ops[%d]", j
);
3282 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3283 snprintf (dest
, 32, "res_op%d", j
);
3286 = get_operand_type (opr
, j
,
3287 "type", e
->expr_type
,
3289 ? NULL
: "TREE_TYPE (res_op0)");
3290 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3294 fprintf_indent (f
, indent
, "return true;\n");
3297 fprintf_indent (f
, indent
, "tree res;\n");
3298 /* Re-fold the toplevel result. Use non_lvalue to
3299 build NON_LVALUE_EXPRs so they get properly
3300 ignored when in GIMPLE form. */
3301 if (*opr
== NON_LVALUE_EXPR
)
3302 fprintf_indent (f
, indent
,
3303 "res = non_lvalue_loc (loc, res_op0);\n");
3306 if (is_a
<operator_id
*> (opr
))
3307 fprintf_indent (f
, indent
,
3308 "res = fold_build%d_loc (loc, %s, type",
3310 *e
->operation
== CONVERT_EXPR
3311 ? "NOP_EXPR" : e
->operation
->id
);
3313 fprintf_indent (f
, indent
,
3314 "res = maybe_build_call_expr_loc (loc, "
3315 "%s, type, %d", e
->operation
->id
,
3317 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3318 fprintf (f
, ", res_op%d", j
);
3319 fprintf (f
, ");\n");
3320 if (!is_a
<operator_id
*> (opr
))
3322 fprintf_indent (f
, indent
, "if (!res)\n");
3323 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3328 else if (result
->type
== operand::OP_CAPTURE
3329 || result
->type
== operand::OP_C_EXPR
)
3332 fprintf_indent (f
, indent
, "tree res;\n");
3333 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3340 /* Search for captures not used in the result expression and dependent
3341 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3342 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3344 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3346 if (!cinfo
.info
[i
].force_no_side_effects_p
3347 && !cinfo
.info
[i
].expr_p
3348 && cinfo
.info
[i
].result_use_count
== 0)
3350 fprintf_indent (f
, indent
,
3351 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3353 fprintf_indent (f
, indent
+ 2,
3354 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3355 "fold_ignored_result (captures[%d]), res);\n",
3359 fprintf_indent (f
, indent
, "return res;\n");
3364 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3365 step of a '(simplify ...)' or '(match ...)'. This handles everything
3366 that is not part of the decision tree (simplify->match). */
3369 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3371 fprintf_indent (f
, indent
, "{\n");
3373 output_line_directive (f
,
3374 s
->result
? s
->result
->location
: s
->match
->location
);
3375 if (s
->capture_max
>= 0)
3378 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3379 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3381 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3385 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3387 fprintf (f
, " };\n");
3390 /* If we have a split-out function for the actual transform, call it. */
3391 if (info
&& info
->fname
)
3395 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3396 "valueize, type, captures", info
->fname
);
3397 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3398 if (s
->for_subst_vec
[i
].first
->used
)
3399 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3400 fprintf (f
, "))\n");
3401 fprintf_indent (f
, indent
, " return true;\n");
3405 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3407 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3408 fprintf (f
, ", op%d", i
);
3409 fprintf (f
, ", captures");
3410 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3412 if (s
->for_subst_vec
[i
].first
->used
)
3413 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3415 fprintf (f
, ");\n");
3416 fprintf_indent (f
, indent
, "if (res) return res;\n");
3421 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3423 if (! s
->for_subst_vec
[i
].first
->used
)
3425 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3426 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3427 s
->for_subst_vec
[i
].first
->id
,
3428 s
->for_subst_vec
[i
].second
->id
);
3429 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3430 fprintf_indent (f
, indent
, "combined_fn %s = %s;\n",
3431 s
->for_subst_vec
[i
].first
->id
,
3432 s
->for_subst_vec
[i
].second
->id
);
3436 gen_1 (f
, indent
, gimple
, s
->result
);
3440 fprintf_indent (f
, indent
, "}\n");
3444 /* Hash function for finding equivalent transforms. */
3447 sinfo_hashmap_traits::hash (const key_type
&v
)
3449 /* Only bother to compare those originating from the same source pattern. */
3450 return v
->s
->result
->location
;
3453 /* Compare function for finding equivalent transforms. */
3456 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3458 if (o1
->type
!= o2
->type
)
3463 case operand::OP_IF
:
3465 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3466 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3467 /* ??? Properly compare c-exprs. */
3468 if (if1
->cond
!= if2
->cond
)
3470 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3472 if (if1
->falseexpr
!= if2
->falseexpr
3474 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3478 case operand::OP_WITH
:
3480 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3481 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3482 if (with1
->with
!= with2
->with
)
3484 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3489 /* We've hit a result. Time to compare capture-infos - this is required
3490 in addition to the conservative pointer-equivalency of the result IL. */
3491 capture_info
cinfo1 (s1
, o1
, true);
3492 capture_info
cinfo2 (s2
, o2
, true);
3494 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3495 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3498 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3500 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3501 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3502 || (cinfo1
.info
[i
].force_no_side_effects_p
3503 != cinfo2
.info
[i
].force_no_side_effects_p
)
3504 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3505 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3506 /* toplevel_msk is an optimization */
3507 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3508 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3509 /* the pointer back to the capture is for diagnostics only */)
3513 /* ??? Deep-compare the actual result. */
3518 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3519 const key_type
&candidate
)
3521 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3525 /* Main entry to generate code for matching GIMPLE IL off the decision
3529 decision_tree::gen (FILE *f
, bool gimple
)
3535 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3536 "a total number of %u nodes\n",
3537 gimple
? "GIMPLE" : "GENERIC",
3538 root
->num_leafs
, root
->max_level
, root
->total_size
);
3540 /* First split out the transform part of equal leafs. */
3543 for (sinfo_map_t::iterator iter
= si
.begin ();
3544 iter
!= si
.end (); ++iter
)
3546 sinfo
*s
= (*iter
).second
;
3547 /* Do not split out single uses. */
3554 fprintf (stderr
, "found %u uses of", s
->cnt
);
3555 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3558 /* Generate a split out function with the leaf transform code. */
3559 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3562 fprintf (f
, "\nstatic bool\n"
3563 "%s (code_helper *res_code, tree *res_ops,\n"
3564 " gimple_seq *seq, tree (*valueize)(tree) "
3565 "ATTRIBUTE_UNUSED,\n"
3566 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3571 fprintf (f
, "\nstatic tree\n"
3572 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3573 (*iter
).second
->fname
);
3574 for (unsigned i
= 0;
3575 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3576 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3577 fprintf (f
, " tree *captures\n");
3579 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3581 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3583 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3584 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3585 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3586 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3587 fprintf (f
, ", combined_fn ARG_UNUSED (%s)",
3588 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3591 fprintf (f
, ")\n{\n");
3592 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3594 fprintf (f
, " return false;\n");
3596 fprintf (f
, " return NULL_TREE;\n");
3599 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3601 for (unsigned n
= 1; n
<= 3; ++n
)
3603 /* First generate split-out functions. */
3604 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3606 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3607 expr
*e
= static_cast<expr
*>(dop
->op
);
3608 if (e
->ops
.length () != n
3609 /* Builtin simplifications are somewhat premature on
3610 GENERIC. The following drops patterns with outermost
3611 calls. It's easy to emit overloads for function code
3612 though if necessary. */
3614 && e
->operation
->kind
!= id_base::CODE
))
3618 fprintf (f
, "\nstatic bool\n"
3619 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3620 " gimple_seq *seq, tree (*valueize)(tree) "
3621 "ATTRIBUTE_UNUSED,\n"
3622 " code_helper ARG_UNUSED (code), tree "
3623 "ARG_UNUSED (type)\n",
3626 fprintf (f
, "\nstatic tree\n"
3627 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3628 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3630 for (unsigned i
= 0; i
< n
; ++i
)
3631 fprintf (f
, ", tree op%d", i
);
3634 dop
->gen_kids (f
, 2, gimple
);
3636 fprintf (f
, " return false;\n");
3638 fprintf (f
, " return NULL_TREE;\n");
3642 /* Then generate the main entry with the outermost switch and
3643 tail-calls to the split-out functions. */
3645 fprintf (f
, "\nstatic bool\n"
3646 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3647 " gimple_seq *seq, tree (*valueize)(tree),\n"
3648 " code_helper code, tree type");
3650 fprintf (f
, "\ntree\n"
3651 "generic_simplify (location_t loc, enum tree_code code, "
3652 "tree type ATTRIBUTE_UNUSED");
3653 for (unsigned i
= 0; i
< n
; ++i
)
3654 fprintf (f
, ", tree op%d", i
);
3659 fprintf (f
, " switch (code.get_rep())\n"
3662 fprintf (f
, " switch (code)\n"
3664 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3666 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3667 expr
*e
= static_cast<expr
*>(dop
->op
);
3668 if (e
->ops
.length () != n
3669 /* Builtin simplifications are somewhat premature on
3670 GENERIC. The following drops patterns with outermost
3671 calls. It's easy to emit overloads for function code
3672 though if necessary. */
3674 && e
->operation
->kind
!= id_base::CODE
))
3677 if (*e
->operation
== CONVERT_EXPR
3678 || *e
->operation
== NOP_EXPR
)
3679 fprintf (f
, " CASE_CONVERT:\n");
3681 fprintf (f
, " case %s%s:\n",
3682 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3685 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3686 "seq, valueize, code, type", e
->operation
->id
);
3688 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3690 for (unsigned i
= 0; i
< n
; ++i
)
3691 fprintf (f
, ", op%d", i
);
3692 fprintf (f
, ");\n");
3694 fprintf (f
, " default:;\n"
3698 fprintf (f
, " return false;\n");
3700 fprintf (f
, " return NULL_TREE;\n");
3705 /* Output code to implement the predicate P from the decision tree DT. */
3708 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3710 fprintf (f
, "\nbool\n"
3711 "%s%s (tree t%s%s)\n"
3712 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3713 p
->nargs
> 0 ? ", tree *res_ops" : "",
3714 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3715 /* Conveniently make 'type' available. */
3716 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3719 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3720 dt
.root
->gen_kids (f
, 2, gimple
);
3722 fprintf_indent (f
, 2, "return false;\n"
3726 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3729 write_header (FILE *f
, const char *head
)
3731 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3732 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3734 /* Include the header instead of writing it awkwardly quoted here. */
3735 fprintf (f
, "\n#include \"%s\"\n", head
);
3745 parser (cpp_reader
*);
3748 const cpp_token
*next ();
3749 const cpp_token
*peek (unsigned = 1);
3750 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3751 const cpp_token
*expect (enum cpp_ttype
);
3752 const cpp_token
*eat_token (enum cpp_ttype
);
3753 const char *get_string ();
3754 const char *get_ident ();
3755 const cpp_token
*eat_ident (const char *);
3756 const char *get_number ();
3758 unsigned get_internal_capture_id ();
3760 id_base
*parse_operation ();
3761 operand
*parse_capture (operand
*, bool);
3762 operand
*parse_expr ();
3763 c_expr
*parse_c_expr (cpp_ttype
);
3764 operand
*parse_op ();
3766 void record_operlist (source_location
, user_id
*);
3768 void parse_pattern ();
3769 operand
*parse_result (operand
*, predicate_id
*);
3770 void push_simplify (simplify::simplify_kind
,
3771 vec
<simplify
*>&, operand
*, operand
*);
3772 void parse_simplify (simplify::simplify_kind
,
3773 vec
<simplify
*>&, predicate_id
*, operand
*);
3774 void parse_for (source_location
);
3775 void parse_if (source_location
);
3776 void parse_predicates (source_location
);
3777 void parse_operator_list (source_location
);
3779 void finish_match_operand (operand
*);
3782 vec
<c_expr
*> active_ifs
;
3783 vec
<vec
<user_id
*> > active_fors
;
3784 hash_set
<user_id
*> *oper_lists_set
;
3785 vec
<user_id
*> oper_lists
;
3787 cid_map_t
*capture_ids
;
3790 vec
<simplify
*> simplifiers
;
3791 vec
<predicate_id
*> user_predicates
;
3792 bool parsing_match_operand
;
3795 /* Lexing helpers. */
3797 /* Read the next non-whitespace token from R. */
3802 const cpp_token
*token
;
3805 token
= cpp_get_token (r
);
3807 while (token
->type
== CPP_PADDING
3808 && token
->type
!= CPP_EOF
);
3812 /* Peek at the next non-whitespace token from R. */
3815 parser::peek (unsigned num
)
3817 const cpp_token
*token
;
3821 token
= cpp_peek_token (r
, i
++);
3823 while ((token
->type
== CPP_PADDING
3824 && token
->type
!= CPP_EOF
)
3826 /* If we peek at EOF this is a fatal error as it leaves the
3827 cpp_reader in unusable state. Assume we really wanted a
3828 token and thus this EOF is unexpected. */
3829 if (token
->type
== CPP_EOF
)
3830 fatal_at (token
, "unexpected end of file");
3834 /* Peek at the next identifier token (or return NULL if the next
3835 token is not an identifier or equal to ID if supplied). */
3838 parser::peek_ident (const char *id
, unsigned num
)
3840 const cpp_token
*token
= peek (num
);
3841 if (token
->type
!= CPP_NAME
)
3847 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3848 if (strcmp (id
, t
) == 0)
3854 /* Read the next token from R and assert it is of type TK. */
3857 parser::expect (enum cpp_ttype tk
)
3859 const cpp_token
*token
= next ();
3860 if (token
->type
!= tk
)
3861 fatal_at (token
, "expected %s, got %s",
3862 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3867 /* Consume the next token from R and assert it is of type TK. */
3870 parser::eat_token (enum cpp_ttype tk
)
3875 /* Read the next token from R and assert it is of type CPP_STRING and
3876 return its value. */
3879 parser::get_string ()
3881 const cpp_token
*token
= expect (CPP_STRING
);
3882 return (const char *)token
->val
.str
.text
;
3885 /* Read the next token from R and assert it is of type CPP_NAME and
3886 return its value. */
3889 parser::get_ident ()
3891 const cpp_token
*token
= expect (CPP_NAME
);
3892 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3895 /* Eat an identifier token with value S from R. */
3898 parser::eat_ident (const char *s
)
3900 const cpp_token
*token
= peek ();
3901 const char *t
= get_ident ();
3902 if (strcmp (s
, t
) != 0)
3903 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3907 /* Read the next token from R and assert it is of type CPP_NUMBER and
3908 return its value. */
3911 parser::get_number ()
3913 const cpp_token
*token
= expect (CPP_NUMBER
);
3914 return (const char *)token
->val
.str
.text
;
3917 /* Return a capture ID that can be used internally. */
3920 parser::get_internal_capture_id ()
3922 unsigned newid
= capture_ids
->elements ();
3923 /* Big enough for a 32-bit UINT_MAX plus prefix. */
3926 sprintf (id
, "__%u", newid
);
3927 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3929 fatal ("reserved capture id '%s' already used", id
);
3933 /* Record an operator-list use for transparent for handling. */
3936 parser::record_operlist (source_location loc
, user_id
*p
)
3938 if (!oper_lists_set
->add (p
))
3940 if (!oper_lists
.is_empty ()
3941 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3942 fatal_at (loc
, "User-defined operator list does not have the "
3943 "same number of entries as others used in the pattern");
3944 oper_lists
.safe_push (p
);
3948 /* Parse the operator ID, special-casing convert?, convert1? and
3952 parser::parse_operation ()
3954 const cpp_token
*id_tok
= peek ();
3955 const char *id
= get_ident ();
3956 const cpp_token
*token
= peek ();
3957 if (strcmp (id
, "convert0") == 0)
3958 fatal_at (id_tok
, "use 'convert?' here");
3959 else if (strcmp (id
, "view_convert0") == 0)
3960 fatal_at (id_tok
, "use 'view_convert?' here");
3961 if (token
->type
== CPP_QUERY
3962 && !(token
->flags
& PREV_WHITE
))
3964 if (strcmp (id
, "convert") == 0)
3966 else if (strcmp (id
, "convert1") == 0)
3968 else if (strcmp (id
, "convert2") == 0)
3970 else if (strcmp (id
, "view_convert") == 0)
3971 id
= "view_convert0";
3972 else if (strcmp (id
, "view_convert1") == 0)
3974 else if (strcmp (id
, "view_convert2") == 0)
3977 fatal_at (id_tok
, "non-convert operator conditionalized");
3979 if (!parsing_match_operand
)
3980 fatal_at (id_tok
, "conditional convert can only be used in "
3981 "match expression");
3982 eat_token (CPP_QUERY
);
3984 else if (strcmp (id
, "convert1") == 0
3985 || strcmp (id
, "convert2") == 0
3986 || strcmp (id
, "view_convert1") == 0
3987 || strcmp (id
, "view_convert2") == 0)
3988 fatal_at (id_tok
, "expected '?' after conditional operator");
3989 id_base
*op
= get_operator (id
);
3991 fatal_at (id_tok
, "unknown operator %s", id
);
3993 user_id
*p
= dyn_cast
<user_id
*> (op
);
3994 if (p
&& p
->is_oper_list
)
3996 if (active_fors
.length() == 0)
3997 record_operlist (id_tok
->src_loc
, p
);
3999 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
4005 capture = '@'<number> */
4008 parser::parse_capture (operand
*op
, bool require_existing
)
4010 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4011 const cpp_token
*token
= peek ();
4012 const char *id
= NULL
;
4013 bool value_match
= false;
4014 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4015 if (token
->type
== CPP_ATSIGN
4016 && ! (token
->flags
& PREV_WHITE
)
4017 && parsing_match_operand
)
4019 eat_token (CPP_ATSIGN
);
4023 if (token
->type
== CPP_NUMBER
)
4025 else if (token
->type
== CPP_NAME
)
4028 fatal_at (token
, "expected number or identifier");
4029 unsigned next_id
= capture_ids
->elements ();
4031 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4034 if (require_existing
)
4035 fatal_at (src_loc
, "unknown capture id");
4038 return new capture (src_loc
, num
, op
, value_match
);
4041 /* Parse an expression
4042 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4045 parser::parse_expr ()
4047 const cpp_token
*token
= peek ();
4048 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4051 bool is_commutative
= false;
4052 bool force_capture
= false;
4053 const char *expr_type
= NULL
;
4055 if (token
->type
== CPP_COLON
4056 && !(token
->flags
& PREV_WHITE
))
4058 eat_token (CPP_COLON
);
4060 if (token
->type
== CPP_NAME
4061 && !(token
->flags
& PREV_WHITE
))
4063 const char *s
= get_ident ();
4064 if (!parsing_match_operand
)
4074 = dyn_cast
<operator_id
*> (e
->operation
))
4076 if (!commutative_tree_code (p
->code
)
4077 && !comparison_code_p (p
->code
))
4078 fatal_at (token
, "operation is not commutative");
4080 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4081 for (unsigned i
= 0;
4082 i
< p
->substitutes
.length (); ++i
)
4085 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4087 if (!commutative_tree_code (q
->code
)
4088 && !comparison_code_p (q
->code
))
4089 fatal_at (token
, "operation %s is not "
4090 "commutative", q
->id
);
4093 is_commutative
= true;
4095 else if (*sp
== 'C')
4096 is_commutative
= true;
4097 else if (*sp
== 's')
4099 e
->force_single_use
= true;
4100 force_capture
= true;
4103 fatal_at (token
, "flag %c not recognized", *sp
);
4110 fatal_at (token
, "expected flag or type specifying identifier");
4113 if (token
->type
== CPP_ATSIGN
4114 && !(token
->flags
& PREV_WHITE
))
4115 op
= parse_capture (e
, false);
4116 else if (force_capture
)
4118 unsigned num
= get_internal_capture_id ();
4119 op
= new capture (token
->src_loc
, num
, e
, false);
4125 const cpp_token
*token
= peek ();
4126 if (token
->type
== CPP_CLOSE_PAREN
)
4128 if (e
->operation
->nargs
!= -1
4129 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4130 fatal_at (token
, "'%s' expects %u operands, not %u",
4131 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4134 if (e
->ops
.length () == 2)
4135 e
->is_commutative
= true;
4137 fatal_at (token
, "only binary operators or function with "
4138 "two arguments can be marked commutative");
4140 e
->expr_type
= expr_type
;
4143 else if (!(token
->flags
& PREV_WHITE
))
4144 fatal_at (token
, "expected expression operand");
4146 e
->append_op (parse_op ());
4151 /* Lex native C code delimited by START recording the preprocessing tokens
4152 for later processing.
4153 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4156 parser::parse_c_expr (cpp_ttype start
)
4158 const cpp_token
*token
;
4161 vec
<cpp_token
> code
= vNULL
;
4162 unsigned nr_stmts
= 0;
4163 source_location loc
= eat_token (start
)->src_loc
;
4164 if (start
== CPP_OPEN_PAREN
)
4165 end
= CPP_CLOSE_PAREN
;
4166 else if (start
== CPP_OPEN_BRACE
)
4167 end
= CPP_CLOSE_BRACE
;
4175 /* Count brace pairs to find the end of the expr to match. */
4176 if (token
->type
== start
)
4178 else if (token
->type
== end
4181 else if (token
->type
== CPP_EOF
)
4182 fatal_at (token
, "unexpected end of file");
4184 /* This is a lame way of counting the number of statements. */
4185 if (token
->type
== CPP_SEMICOLON
)
4188 /* If this is possibly a user-defined identifier mark it used. */
4189 if (token
->type
== CPP_NAME
)
4191 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4192 (token
->val
.node
.node
)->ident
.str
);
4194 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4195 record_operlist (token
->src_loc
, p
);
4198 /* Record the token. */
4199 code
.safe_push (*token
);
4202 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4205 /* Parse an operand which is either an expression, a predicate or
4206 a standalone capture.
4207 op = predicate | expr | c_expr | capture */
4212 const cpp_token
*token
= peek ();
4213 struct operand
*op
= NULL
;
4214 if (token
->type
== CPP_OPEN_PAREN
)
4216 eat_token (CPP_OPEN_PAREN
);
4218 eat_token (CPP_CLOSE_PAREN
);
4220 else if (token
->type
== CPP_OPEN_BRACE
)
4222 op
= parse_c_expr (CPP_OPEN_BRACE
);
4226 /* Remaining ops are either empty or predicates */
4227 if (token
->type
== CPP_NAME
)
4229 const char *id
= get_ident ();
4230 id_base
*opr
= get_operator (id
);
4232 fatal_at (token
, "expected predicate name");
4233 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4235 if (code
->nargs
!= 0)
4236 fatal_at (token
, "using an operator with operands as predicate");
4237 /* Parse the zero-operand operator "predicates" as
4239 op
= new expr (opr
, token
->src_loc
);
4241 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4243 if (code
->nargs
!= 0)
4244 fatal_at (token
, "using an operator with operands as predicate");
4245 /* Parse the zero-operand operator "predicates" as
4247 op
= new expr (opr
, token
->src_loc
);
4249 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4250 op
= new predicate (p
, token
->src_loc
);
4252 fatal_at (token
, "using an unsupported operator as predicate");
4253 if (!parsing_match_operand
)
4254 fatal_at (token
, "predicates are only allowed in match expression");
4256 if (token
->flags
& PREV_WHITE
)
4259 else if (token
->type
!= CPP_COLON
4260 && token
->type
!= CPP_ATSIGN
)
4261 fatal_at (token
, "expected expression or predicate");
4262 /* optionally followed by a capture and a predicate. */
4263 if (token
->type
== CPP_COLON
)
4264 fatal_at (token
, "not implemented: predicate on leaf operand");
4265 if (token
->type
== CPP_ATSIGN
)
4266 op
= parse_capture (op
, !parsing_match_operand
);
4272 /* Create a new simplify from the current parsing state and MATCH,
4273 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4276 parser::push_simplify (simplify::simplify_kind kind
,
4277 vec
<simplify
*>& simplifiers
,
4278 operand
*match
, operand
*result
)
4280 /* Build and push a temporary for operator list uses in expressions. */
4281 if (!oper_lists
.is_empty ())
4282 active_fors
.safe_push (oper_lists
);
4284 simplifiers
.safe_push
4285 (new simplify (kind
, match
, result
,
4286 active_fors
.copy (), capture_ids
));
4288 if (!oper_lists
.is_empty ())
4293 <result-op> = <op> | <if> | <with>
4294 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4295 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4299 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4301 const cpp_token
*token
= peek ();
4302 if (token
->type
!= CPP_OPEN_PAREN
)
4305 eat_token (CPP_OPEN_PAREN
);
4306 if (peek_ident ("if"))
4309 if_expr
*ife
= new if_expr (token
->src_loc
);
4310 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4311 if (peek ()->type
== CPP_OPEN_PAREN
)
4313 ife
->trueexpr
= parse_result (result
, matcher
);
4314 if (peek ()->type
== CPP_OPEN_PAREN
)
4315 ife
->falseexpr
= parse_result (result
, matcher
);
4316 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4317 ife
->falseexpr
= parse_op ();
4319 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4321 ife
->trueexpr
= parse_op ();
4322 if (peek ()->type
== CPP_OPEN_PAREN
)
4323 ife
->falseexpr
= parse_result (result
, matcher
);
4324 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4325 ife
->falseexpr
= parse_op ();
4327 /* If this if is immediately closed then it contains a
4328 manual matcher or is part of a predicate definition. */
4329 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4332 fatal_at (peek (), "manual transform not implemented");
4333 ife
->trueexpr
= result
;
4335 eat_token (CPP_CLOSE_PAREN
);
4338 else if (peek_ident ("with"))
4341 with_expr
*withe
= new with_expr (token
->src_loc
);
4342 /* Parse (with c-expr expr) as (if-with (true) expr). */
4343 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4344 withe
->with
->nr_stmts
= 0;
4345 withe
->subexpr
= parse_result (result
, matcher
);
4346 eat_token (CPP_CLOSE_PAREN
);
4349 else if (peek_ident ("switch"))
4351 token
= eat_ident ("switch");
4352 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4354 if_expr
*ife
= new if_expr (ifloc
);
4356 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4357 if (peek ()->type
== CPP_OPEN_PAREN
)
4358 ife
->trueexpr
= parse_result (result
, matcher
);
4360 ife
->trueexpr
= parse_op ();
4361 eat_token (CPP_CLOSE_PAREN
);
4362 if (peek ()->type
!= CPP_OPEN_PAREN
4363 || !peek_ident ("if", 2))
4364 fatal_at (token
, "switch can be implemented with a single if");
4365 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4367 if (peek ()->type
== CPP_OPEN_PAREN
)
4369 if (peek_ident ("if", 2))
4371 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4373 ife
->falseexpr
= new if_expr (ifloc
);
4374 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4375 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4376 if (peek ()->type
== CPP_OPEN_PAREN
)
4377 ife
->trueexpr
= parse_result (result
, matcher
);
4379 ife
->trueexpr
= parse_op ();
4380 eat_token (CPP_CLOSE_PAREN
);
4384 /* switch default clause */
4385 ife
->falseexpr
= parse_result (result
, matcher
);
4386 eat_token (CPP_CLOSE_PAREN
);
4392 /* switch default clause */
4393 ife
->falseexpr
= parse_op ();
4394 eat_token (CPP_CLOSE_PAREN
);
4398 eat_token (CPP_CLOSE_PAREN
);
4403 operand
*op
= result
;
4406 eat_token (CPP_CLOSE_PAREN
);
4412 simplify = 'simplify' <expr> <result-op>
4414 match = 'match' <ident> <expr> [<result-op>]
4415 and fill SIMPLIFIERS with the results. */
4418 parser::parse_simplify (simplify::simplify_kind kind
,
4419 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4422 /* Reset the capture map. */
4424 capture_ids
= new cid_map_t
;
4425 /* Reset oper_lists and set. */
4426 hash_set
<user_id
*> olist
;
4427 oper_lists_set
= &olist
;
4430 const cpp_token
*loc
= peek ();
4431 parsing_match_operand
= true;
4432 struct operand
*match
= parse_op ();
4433 finish_match_operand (match
);
4434 parsing_match_operand
= false;
4435 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4436 fatal_at (loc
, "outermost expression cannot be captured");
4437 if (match
->type
== operand::OP_EXPR
4438 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4439 fatal_at (loc
, "outermost expression cannot be a predicate");
4441 /* Splice active_ifs onto result and continue parsing the
4443 if_expr
*active_if
= NULL
;
4444 for (int i
= active_ifs
.length (); i
> 0; --i
)
4446 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4447 ifc
->cond
= active_ifs
[i
-1];
4448 ifc
->trueexpr
= active_if
;
4451 if_expr
*outermost_if
= active_if
;
4452 while (active_if
&& active_if
->trueexpr
)
4453 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4455 const cpp_token
*token
= peek ();
4457 /* If this if is immediately closed then it is part of a predicate
4458 definition. Push it. */
4459 if (token
->type
== CPP_CLOSE_PAREN
)
4462 fatal_at (token
, "expected transform expression");
4465 active_if
->trueexpr
= result
;
4466 result
= outermost_if
;
4468 push_simplify (kind
, simplifiers
, match
, result
);
4472 operand
*tem
= parse_result (result
, matcher
);
4475 active_if
->trueexpr
= tem
;
4476 result
= outermost_if
;
4481 push_simplify (kind
, simplifiers
, match
, result
);
4484 /* Parsing of the outer control structures. */
4486 /* Parse a for expression
4487 for = '(' 'for' <subst>... <pattern> ')'
4488 subst = <ident> '(' <ident>... ')' */
4491 parser::parse_for (source_location
)
4493 auto_vec
<const cpp_token
*> user_id_tokens
;
4494 vec
<user_id
*> user_ids
= vNULL
;
4495 const cpp_token
*token
;
4496 unsigned min_n_opers
= 0, max_n_opers
= 0;
4501 if (token
->type
!= CPP_NAME
)
4504 /* Insert the user defined operators into the operator hash. */
4505 const char *id
= get_ident ();
4506 if (get_operator (id
, true) != NULL
)
4507 fatal_at (token
, "operator already defined");
4508 user_id
*op
= new user_id (id
);
4509 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4511 user_ids
.safe_push (op
);
4512 user_id_tokens
.safe_push (token
);
4514 eat_token (CPP_OPEN_PAREN
);
4517 while ((token
= peek_ident ()) != 0)
4519 const char *oper
= get_ident ();
4520 id_base
*idb
= get_operator (oper
, true);
4522 fatal_at (token
, "no such operator '%s'", oper
);
4523 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4524 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4525 || *idb
== VIEW_CONVERT2
)
4526 fatal_at (token
, "conditional operators cannot be used inside for");
4530 else if (idb
->nargs
== -1)
4532 else if (idb
->nargs
!= arity
)
4533 fatal_at (token
, "operator '%s' with arity %d does not match "
4534 "others with arity %d", oper
, idb
->nargs
, arity
);
4536 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4539 if (p
->is_oper_list
)
4540 op
->substitutes
.safe_splice (p
->substitutes
);
4542 fatal_at (token
, "iterator cannot be used as operator-list");
4545 op
->substitutes
.safe_push (idb
);
4548 token
= expect (CPP_CLOSE_PAREN
);
4550 unsigned nsubstitutes
= op
->substitutes
.length ();
4551 if (nsubstitutes
== 0)
4552 fatal_at (token
, "A user-defined operator must have at least "
4553 "one substitution");
4554 if (max_n_opers
== 0)
4556 min_n_opers
= nsubstitutes
;
4557 max_n_opers
= nsubstitutes
;
4561 if (nsubstitutes
% min_n_opers
!= 0
4562 && min_n_opers
% nsubstitutes
!= 0)
4563 fatal_at (token
, "All user-defined identifiers must have a "
4564 "multiple number of operator substitutions of the "
4565 "smallest number of substitutions");
4566 if (nsubstitutes
< min_n_opers
)
4567 min_n_opers
= nsubstitutes
;
4568 else if (nsubstitutes
> max_n_opers
)
4569 max_n_opers
= nsubstitutes
;
4573 unsigned n_ids
= user_ids
.length ();
4575 fatal_at (token
, "for requires at least one user-defined identifier");
4578 if (token
->type
== CPP_CLOSE_PAREN
)
4579 fatal_at (token
, "no pattern defined in for");
4581 active_fors
.safe_push (user_ids
);
4585 if (token
->type
== CPP_CLOSE_PAREN
)
4591 /* Remove user-defined operators from the hash again. */
4592 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4594 if (!user_ids
[i
]->used
)
4595 warning_at (user_id_tokens
[i
],
4596 "operator %s defined but not used", user_ids
[i
]->id
);
4597 operators
->remove_elt (user_ids
[i
]);
4601 /* Parse an identifier associated with a list of operators.
4602 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4605 parser::parse_operator_list (source_location
)
4607 const cpp_token
*token
= peek ();
4608 const char *id
= get_ident ();
4610 if (get_operator (id
, true) != 0)
4611 fatal_at (token
, "operator %s already defined", id
);
4613 user_id
*op
= new user_id (id
, true);
4616 while ((token
= peek_ident ()) != 0)
4619 const char *oper
= get_ident ();
4620 id_base
*idb
= get_operator (oper
, true);
4623 fatal_at (token
, "no such operator '%s'", oper
);
4627 else if (idb
->nargs
== -1)
4629 else if (arity
!= idb
->nargs
)
4630 fatal_at (token
, "operator '%s' with arity %d does not match "
4631 "others with arity %d", oper
, idb
->nargs
, arity
);
4633 /* We allow composition of multiple operator lists. */
4634 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4635 op
->substitutes
.safe_splice (p
->substitutes
);
4637 op
->substitutes
.safe_push (idb
);
4640 // Check that there is no junk after id-list
4642 if (token
->type
!= CPP_CLOSE_PAREN
)
4643 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4645 if (op
->substitutes
.length () == 0)
4646 fatal_at (token
, "operator-list cannot be empty");
4649 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4653 /* Parse an outer if expression.
4654 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4657 parser::parse_if (source_location
)
4659 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4661 const cpp_token
*token
= peek ();
4662 if (token
->type
== CPP_CLOSE_PAREN
)
4663 fatal_at (token
, "no pattern defined in if");
4665 active_ifs
.safe_push (ifexpr
);
4668 const cpp_token
*token
= peek ();
4669 if (token
->type
== CPP_CLOSE_PAREN
)
4677 /* Parse a list of predefined predicate identifiers.
4678 preds = '(' 'define_predicates' <ident>... ')' */
4681 parser::parse_predicates (source_location
)
4685 const cpp_token
*token
= peek ();
4686 if (token
->type
!= CPP_NAME
)
4689 add_predicate (get_ident ());
4694 /* Parse outer control structures.
4695 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4698 parser::parse_pattern ()
4700 /* All clauses start with '('. */
4701 eat_token (CPP_OPEN_PAREN
);
4702 const cpp_token
*token
= peek ();
4703 const char *id
= get_ident ();
4704 if (strcmp (id
, "simplify") == 0)
4706 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4709 else if (strcmp (id
, "match") == 0)
4711 bool with_args
= false;
4712 source_location e_loc
= peek ()->src_loc
;
4713 if (peek ()->type
== CPP_OPEN_PAREN
)
4715 eat_token (CPP_OPEN_PAREN
);
4718 const char *name
= get_ident ();
4719 id_base
*id
= get_operator (name
);
4723 p
= add_predicate (name
);
4724 user_predicates
.safe_push (p
);
4726 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4729 fatal_at (token
, "cannot add a match to a non-predicate ID");
4730 /* Parse (match <id> <arg>... (match-expr)) here. */
4734 capture_ids
= new cid_map_t
;
4735 e
= new expr (p
, e_loc
);
4736 while (peek ()->type
== CPP_ATSIGN
)
4737 e
->append_op (parse_capture (NULL
, false));
4738 eat_token (CPP_CLOSE_PAREN
);
4741 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4742 || (!e
&& p
->nargs
!= 0)))
4743 fatal_at (token
, "non-matching number of match operands");
4744 p
->nargs
= e
? e
->ops
.length () : 0;
4745 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4748 else if (strcmp (id
, "for") == 0)
4749 parse_for (token
->src_loc
);
4750 else if (strcmp (id
, "if") == 0)
4751 parse_if (token
->src_loc
);
4752 else if (strcmp (id
, "define_predicates") == 0)
4754 if (active_ifs
.length () > 0
4755 || active_fors
.length () > 0)
4756 fatal_at (token
, "define_predicates inside if or for is not supported");
4757 parse_predicates (token
->src_loc
);
4759 else if (strcmp (id
, "define_operator_list") == 0)
4761 if (active_ifs
.length () > 0
4762 || active_fors
.length () > 0)
4763 fatal_at (token
, "operator-list inside if or for is not supported");
4764 parse_operator_list (token
->src_loc
);
4767 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4768 active_ifs
.length () == 0 && active_fors
.length () == 0
4769 ? "'define_predicates', " : "");
4771 eat_token (CPP_CLOSE_PAREN
);
4774 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4778 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4783 if (capture
*c
= dyn_cast
<capture
*> (op
))
4785 cpts
[c
->where
].safe_push (c
);
4786 walk_captures (c
->what
, cpts
);
4788 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4789 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4790 walk_captures (e
->ops
[i
], cpts
);
4793 /* Finish up OP which is a match operand. */
4796 parser::finish_match_operand (operand
*op
)
4798 /* Look for matching captures, diagnose mis-uses of @@ and apply
4799 early lowering and distribution of value_match. */
4800 auto_vec
<vec
<capture
*> > cpts
;
4801 cpts
.safe_grow_cleared (capture_ids
->elements ());
4802 walk_captures (op
, cpts
);
4803 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4805 capture
*value_match
= NULL
;
4806 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4808 if (cpts
[i
][j
]->value_match
)
4811 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
4812 value_match
= cpts
[i
][j
];
4815 if (cpts
[i
].length () == 1 && value_match
)
4816 fatal_at (value_match
->location
, "@@ without a matching capture");
4819 /* Duplicate prevailing capture with the existing ID, create
4820 a fake ID and rewrite all captures to use it. This turns
4821 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4822 value_match
->what
= new capture (value_match
->location
,
4824 value_match
->what
, false);
4825 /* Create a fake ID and rewrite all captures to use it. */
4826 unsigned newid
= get_internal_capture_id ();
4827 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4829 cpts
[i
][j
]->where
= newid
;
4830 cpts
[i
][j
]->value_match
= true;
4837 /* Main entry of the parser. Repeatedly parse outer control structures. */
4839 parser::parser (cpp_reader
*r_
)
4843 active_fors
= vNULL
;
4844 simplifiers
= vNULL
;
4845 oper_lists_set
= NULL
;
4848 user_predicates
= vNULL
;
4849 parsing_match_operand
= false;
4851 const cpp_token
*token
= next ();
4852 while (token
->type
!= CPP_EOF
)
4854 _cpp_backup_tokens (r
, 1);
4861 /* Helper for the linemap code. */
4864 round_alloc_size (size_t s
)
4870 /* The genmatch generator progam. It reads from a pattern description
4871 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4874 main (int argc
, char **argv
)
4878 progname
= "genmatch";
4884 char *input
= argv
[argc
-1];
4885 for (int i
= 1; i
< argc
- 1; ++i
)
4887 if (strcmp (argv
[i
], "--gimple") == 0)
4889 else if (strcmp (argv
[i
], "--generic") == 0)
4891 else if (strcmp (argv
[i
], "-v") == 0)
4893 else if (strcmp (argv
[i
], "-vv") == 0)
4897 fprintf (stderr
, "Usage: genmatch "
4898 "[--gimple] [--generic] [-v[v]] input\n");
4903 line_table
= XCNEW (struct line_maps
);
4904 linemap_init (line_table
, 0);
4905 line_table
->reallocator
= xrealloc
;
4906 line_table
->round_alloc_size
= round_alloc_size
;
4908 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4909 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4910 cb
->error
= error_cb
;
4912 /* Add the build directory to the #include "" search path. */
4913 cpp_dir
*dir
= XCNEW (cpp_dir
);
4914 dir
->name
= getpwd ();
4916 dir
->name
= ASTRDUP (".");
4917 cpp_set_include_chains (r
, dir
, NULL
, false);
4919 if (!cpp_read_main_file (r
, input
))
4921 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4922 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4924 null_id
= new id_base (id_base::NULL_ID
, "null");
4926 /* Pre-seed operators. */
4927 operators
= new hash_table
<id_base
> (1024);
4928 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4929 add_operator (SYM, # SYM, # TYPE, NARGS);
4930 #define END_OF_BASE_TREE_CODES
4932 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
4933 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
4934 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
4935 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
4936 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
4937 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
4938 #undef END_OF_BASE_TREE_CODES
4941 /* Pre-seed builtin functions.
4942 ??? Cannot use N (name) as that is targetm.emultls.get_address
4943 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4944 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4945 add_function (ENUM, "CFN_" # ENUM);
4946 #include "builtins.def"
4948 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
4949 add_function (IFN_##CODE, "CFN_" #CODE);
4950 #include "internal-fn.def"
4956 write_header (stdout
, "gimple-match-head.c");
4958 write_header (stdout
, "generic-match-head.c");
4960 /* Go over all predicates defined with patterns and perform
4961 lowering and code generation. */
4962 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4964 predicate_id
*pred
= p
.user_predicates
[i
];
4965 lower (pred
->matchers
, gimple
);
4968 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4969 print_matches (pred
->matchers
[i
]);
4972 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4973 dt
.insert (pred
->matchers
[i
], i
);
4978 write_predicate (stdout
, pred
, dt
, gimple
);
4981 /* Lower the main simplifiers and generate code for them. */
4982 lower (p
.simplifiers
, gimple
);
4985 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4986 print_matches (p
.simplifiers
[i
]);
4989 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4990 dt
.insert (p
.simplifiers
[i
], i
);
4995 dt
.gen (stdout
, gimple
);
4998 cpp_finish (r
, NULL
);