1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2015 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/>. */
27 #include "coretypes.h"
30 #include "hash-table.h"
35 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
36 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
37 size_t, size_t MEM_STAT_DECL
)
41 void ggc_free (void *)
48 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
54 static struct line_maps
*line_table
;
56 /* The rich_location class within libcpp requires a way to expand
57 source_location instances, and relies on the client code
58 providing a symbol named
59 linemap_client_expand_location_to_spelling_point
62 This is the implementation for genmatch. */
65 linemap_client_expand_location_to_spelling_point (source_location loc
)
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 error_cb (cpp_reader
*, int errtype
, int, rich_location
*richloc
,
77 const char *msg
, va_list *ap
)
79 const line_map_ordinary
*map
;
80 source_location location
= richloc
->get_loc ();
81 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
82 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
83 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
84 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
85 vfprintf (stderr
, msg
, *ap
);
86 fprintf (stderr
, "\n");
87 FILE *f
= fopen (loc
.file
, "r");
93 if (!fgets (buf
, 128, f
))
95 if (buf
[strlen (buf
) - 1] != '\n')
102 fprintf (stderr
, "%s", buf
);
103 for (int i
= 0; i
< loc
.column
- 1; ++i
)
106 fputc ('\n', stderr
);
111 if (errtype
== CPP_DL_FATAL
)
117 #if GCC_VERSION >= 4001
118 __attribute__((format (printf
, 2, 3)))
120 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
122 rich_location
richloc (tk
->src_loc
);
125 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
130 #if GCC_VERSION >= 4001
131 __attribute__((format (printf
, 2, 3)))
133 fatal_at (source_location loc
, const char *msg
, ...)
135 rich_location
richloc (loc
);
138 error_cb (NULL
, CPP_DL_FATAL
, 0, &richloc
, msg
, &ap
);
143 #if GCC_VERSION >= 4001
144 __attribute__((format (printf
, 2, 3)))
146 warning_at (const cpp_token
*tk
, const char *msg
, ...)
148 rich_location
richloc (tk
->src_loc
);
151 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
156 #if GCC_VERSION >= 4001
157 __attribute__((format (printf
, 2, 3)))
159 warning_at (source_location loc
, const char *msg
, ...)
161 rich_location
richloc (loc
);
164 error_cb (NULL
, CPP_DL_WARNING
, 0, &richloc
, msg
, &ap
);
168 /* Like fprintf, but print INDENT spaces at the beginning. */
171 #if GCC_VERSION >= 4001
172 __attribute__((format (printf
, 3, 4)))
174 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
177 for (; indent
>= 8; indent
-= 8)
179 fprintf (f
, "%*s", indent
, "");
180 va_start (ap
, format
);
181 vfprintf (f
, format
, ap
);
186 output_line_directive (FILE *f
, source_location location
,
187 bool dumpfile
= false)
189 const line_map_ordinary
*map
;
190 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
191 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
194 /* When writing to a dumpfile only dump the filename. */
195 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
200 fprintf (f
, "%s:%d", file
, loc
.line
);
203 /* Other gen programs really output line directives here, at least for
204 development it's right now more convenient to have line information
205 from the generated file. Still keep the directives as comment for now
206 to easily back-point to the meta-description. */
207 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
211 /* Pull in tree codes and builtin function codes from their
214 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
227 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
228 enum built_in_function
{
229 #include "builtins.def"
234 /* Return true if CODE represents a commutative tree code. Otherwise
237 commutative_tree_code (enum tree_code code
)
243 case MULT_HIGHPART_EXPR
:
258 case WIDEN_MULT_EXPR
:
259 case VEC_WIDEN_MULT_HI_EXPR
:
260 case VEC_WIDEN_MULT_LO_EXPR
:
261 case VEC_WIDEN_MULT_EVEN_EXPR
:
262 case VEC_WIDEN_MULT_ODD_EXPR
:
271 /* Return true if CODE represents a ternary tree code for which the
272 first two operands are commutative. Otherwise return false. */
274 commutative_ternary_tree_code (enum tree_code code
)
278 case WIDEN_MULT_PLUS_EXPR
:
279 case WIDEN_MULT_MINUS_EXPR
:
291 /* Base class for all identifiers the parser knows. */
293 struct id_base
: nofree_ptr_hash
<id_base
>
295 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
297 id_base (id_kind
, const char *, int = -1);
303 /* hash_table support. */
304 static inline hashval_t
hash (const id_base
*);
305 static inline int equal (const id_base
*, const id_base
*);
309 id_base::hash (const id_base
*op
)
315 id_base::equal (const id_base
*op1
,
318 return (op1
->hashval
== op2
->hashval
319 && strcmp (op1
->id
, op2
->id
) == 0);
322 /* Hashtable of known pattern operators. This is pre-seeded from
323 all known tree codes and all known builtin function ids. */
324 static hash_table
<id_base
> *operators
;
326 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
331 hashval
= htab_hash_string (id
);
334 /* Identifier that maps to a tree code. */
336 struct operator_id
: public id_base
338 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
340 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
345 /* Identifier that maps to a builtin function code. */
347 struct fn_id
: public id_base
349 fn_id (enum built_in_function fn_
, const char *id_
)
350 : id_base (id_base::FN
, id_
), fn (fn_
) {}
351 enum built_in_function fn
;
356 /* Identifier that maps to a user-defined predicate. */
358 struct predicate_id
: public id_base
360 predicate_id (const char *id_
)
361 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
362 vec
<simplify
*> matchers
;
365 /* Identifier that maps to a operator defined by a 'for' directive. */
367 struct user_id
: public id_base
369 user_id (const char *id_
, bool is_oper_list_
= false)
370 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
371 used (false), is_oper_list (is_oper_list_
) {}
372 vec
<id_base
*> substitutes
;
380 is_a_helper
<fn_id
*>::test (id_base
*id
)
382 return id
->kind
== id_base::FN
;
388 is_a_helper
<operator_id
*>::test (id_base
*id
)
390 return id
->kind
== id_base::CODE
;
396 is_a_helper
<predicate_id
*>::test (id_base
*id
)
398 return id
->kind
== id_base::PREDICATE
;
404 is_a_helper
<user_id
*>::test (id_base
*id
)
406 return id
->kind
== id_base::USER
;
409 /* Add a predicate identifier to the hash. */
411 static predicate_id
*
412 add_predicate (const char *id
)
414 predicate_id
*p
= new predicate_id (id
);
415 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
417 fatal ("duplicate id definition");
422 /* Add a tree code identifier to the hash. */
425 add_operator (enum tree_code code
, const char *id
,
426 const char *tcc
, unsigned nargs
)
428 if (strcmp (tcc
, "tcc_unary") != 0
429 && strcmp (tcc
, "tcc_binary") != 0
430 && strcmp (tcc
, "tcc_comparison") != 0
431 && strcmp (tcc
, "tcc_expression") != 0
432 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
433 && strcmp (tcc
, "tcc_reference") != 0
434 /* To have INTEGER_CST and friends as "predicate operators". */
435 && strcmp (tcc
, "tcc_constant") != 0
436 /* And allow CONSTRUCTOR for vector initializers. */
437 && !(code
== CONSTRUCTOR
)
438 /* Allow SSA_NAME as predicate operator. */
439 && !(code
== SSA_NAME
))
441 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
442 if (code
== ADDR_EXPR
)
444 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
445 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
447 fatal ("duplicate id definition");
451 /* Add a builtin identifier to the hash. */
454 add_builtin (enum built_in_function code
, const char *id
)
456 fn_id
*fn
= new fn_id (code
, id
);
457 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
459 fatal ("duplicate id definition");
463 /* Helper for easy comparing ID with tree code CODE. */
466 operator==(id_base
&id
, enum tree_code code
)
468 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
469 return oid
->code
== code
;
473 /* Lookup the identifier ID. */
476 get_operator (const char *id
)
478 id_base
tem (id_base::CODE
, id
);
480 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
483 /* If this is a user-defined identifier track whether it was used. */
484 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
489 /* Try all-uppercase. */
490 char *id2
= xstrdup (id
);
491 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
492 id2
[i
] = TOUPPER (id2
[i
]);
493 new (&tem
) id_base (id_base::CODE
, id2
);
494 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
501 /* Try _EXPR appended. */
502 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
503 strcat (id2
, "_EXPR");
504 new (&tem
) id_base (id_base::CODE
, id2
);
505 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
515 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
518 /* The AST produced by parsing of the pattern definitions. */
523 /* The base class for operands. */
526 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
527 operand (enum op_type type_
, source_location loc_
)
528 : type (type_
), location (loc_
) {}
530 source_location location
;
531 virtual void gen_transform (FILE *, int, const char *, bool, int,
532 const char *, capture_info
*,
535 { gcc_unreachable (); }
538 /* A predicate operand. Predicates are leafs in the AST. */
540 struct predicate
: public operand
542 predicate (predicate_id
*p_
, source_location loc
)
543 : operand (OP_PREDICATE
, loc
), p (p_
) {}
547 /* An operand that constitutes an expression. Expressions include
548 function calls and user-defined predicate invocations. */
550 struct expr
: public operand
552 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
553 : operand (OP_EXPR
, loc
), operation (operation_
),
554 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
555 is_generic (false), force_single_use (false) {}
557 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
558 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
559 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
560 void append_op (operand
*op
) { ops
.safe_push (op
); }
561 /* The operator and its operands. */
564 /* An explicitely specified type - used exclusively for conversions. */
565 const char *expr_type
;
566 /* Whether the operation is to be applied commutatively. This is
567 later lowered to two separate patterns. */
569 /* Whether the expression is expected to be in GENERIC form. */
571 /* Whether pushing any stmt to the sequence should be conditional
572 on this expression having a single-use. */
573 bool force_single_use
;
574 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
575 const char *, capture_info
*,
576 dt_operand
** = 0, bool = true);
579 /* An operator that is represented by native C code. This is always
580 a leaf operand in the AST. This class is also used to represent
581 the code to be generated for 'if' and 'with' expressions. */
583 struct c_expr
: public operand
585 /* A mapping of an identifier and its replacement. Used to apply
590 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
593 c_expr (cpp_reader
*r_
, source_location loc
,
594 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
595 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
596 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
597 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
598 /* cpplib tokens and state to transform this back to source. */
601 cid_map_t
*capture_ids
;
602 /* The number of statements parsed (well, the number of ';'s). */
604 /* The identifier replacement vector. */
606 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
607 const char *, capture_info
*,
608 dt_operand
** = 0, bool = true);
611 /* A wrapper around another operand that captures its value. */
613 struct capture
: public operand
615 capture (source_location loc
, unsigned where_
, operand
*what_
)
616 : operand (OP_CAPTURE
, loc
), where (where_
), what (what_
) {}
617 /* Identifier index for the value. */
619 /* The captured value. */
621 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
622 const char *, capture_info
*,
623 dt_operand
** = 0, bool = true);
628 struct if_expr
: public operand
630 if_expr (source_location loc
)
631 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
637 /* with expression. */
639 struct with_expr
: public operand
641 with_expr (source_location loc
)
642 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
650 is_a_helper
<capture
*>::test (operand
*op
)
652 return op
->type
== operand::OP_CAPTURE
;
658 is_a_helper
<predicate
*>::test (operand
*op
)
660 return op
->type
== operand::OP_PREDICATE
;
666 is_a_helper
<c_expr
*>::test (operand
*op
)
668 return op
->type
== operand::OP_C_EXPR
;
674 is_a_helper
<expr
*>::test (operand
*op
)
676 return op
->type
== operand::OP_EXPR
;
682 is_a_helper
<if_expr
*>::test (operand
*op
)
684 return op
->type
== operand::OP_IF
;
690 is_a_helper
<with_expr
*>::test (operand
*op
)
692 return op
->type
== operand::OP_WITH
;
695 /* The main class of a pattern and its transform. This is used to
696 represent both (simplify ...) and (match ...) kinds. The AST
697 duplicates all outer 'if' and 'for' expressions here so each
698 simplify can exist in isolation. */
702 enum simplify_kind
{ SIMPLIFY
, MATCH
};
704 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
705 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
706 : kind (kind_
), match (match_
), result (result_
),
707 for_vec (for_vec_
), for_subst_vec (vNULL
),
708 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
711 /* The expression that is matched against the GENERIC or GIMPLE IL. */
713 /* For a (simplify ...) an expression with ifs and withs with the expression
714 produced when the pattern applies in the leafs.
715 For a (match ...) the leafs are either empty if it is a simple predicate
716 or the single expression specifying the matched operands. */
717 struct operand
*result
;
718 /* Collected 'for' expression operators that have to be replaced
719 in the lowering phase. */
720 vec
<vec
<user_id
*> > for_vec
;
721 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
722 /* A map of capture identifiers to indexes. */
723 cid_map_t
*capture_ids
;
727 /* Debugging routines for dumping the AST. */
730 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
732 if (capture
*c
= dyn_cast
<capture
*> (o
))
734 if (c
->what
&& flattened
== false)
735 print_operand (c
->what
, f
, flattened
);
736 fprintf (f
, "@%u", c
->where
);
739 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
740 fprintf (f
, "%s", p
->p
->id
);
742 else if (is_a
<c_expr
*> (o
))
743 fprintf (f
, "c_expr");
745 else if (expr
*e
= dyn_cast
<expr
*> (o
))
747 if (e
->ops
.length () == 0)
748 fprintf (f
, "%s", e
->operation
->id
);
751 fprintf (f
, "(%s", e
->operation
->id
);
753 if (flattened
== false)
755 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
758 print_operand (e
->ops
[i
], f
, flattened
);
770 print_matches (struct simplify
*s
, FILE *f
= stderr
)
772 fprintf (f
, "for expression: ");
773 print_operand (s
->match
, f
);
780 /* Lowering of commutative operators. */
783 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
784 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
786 if (n
== ops_vector
.length ())
788 vec
<operand
*> xv
= v
.copy ();
789 result
.safe_push (xv
);
793 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
795 v
[n
] = ops_vector
[n
][i
];
796 cartesian_product (ops_vector
, result
, v
, n
+ 1);
800 /* Lower OP to two operands in case it is marked as commutative. */
802 static vec
<operand
*>
803 commutate (operand
*op
)
805 vec
<operand
*> ret
= vNULL
;
807 if (capture
*c
= dyn_cast
<capture
*> (op
))
814 vec
<operand
*> v
= commutate (c
->what
);
815 for (unsigned i
= 0; i
< v
.length (); ++i
)
817 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
]);
823 expr
*e
= dyn_cast
<expr
*> (op
);
824 if (!e
|| e
->ops
.length () == 0)
830 vec
< vec
<operand
*> > ops_vector
= vNULL
;
831 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
832 ops_vector
.safe_push (commutate (e
->ops
[i
]));
834 auto_vec
< vec
<operand
*> > result
;
835 auto_vec
<operand
*> v (e
->ops
.length ());
836 v
.quick_grow_cleared (e
->ops
.length ());
837 cartesian_product (ops_vector
, result
, v
, 0);
840 for (unsigned i
= 0; i
< result
.length (); ++i
)
842 expr
*ne
= new expr (e
);
843 ne
->is_commutative
= false;
844 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
845 ne
->append_op (result
[i
][j
]);
849 if (!e
->is_commutative
)
852 for (unsigned i
= 0; i
< result
.length (); ++i
)
854 expr
*ne
= new expr (e
);
855 ne
->is_commutative
= false;
856 // result[i].length () is 2 since e->operation is binary
857 for (unsigned j
= result
[i
].length (); j
; --j
)
858 ne
->append_op (result
[i
][j
-1]);
865 /* Lower operations marked as commutative in the AST of S and push
866 the resulting patterns to SIMPLIFIERS. */
869 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
871 vec
<operand
*> matchers
= commutate (s
->match
);
872 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
874 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
875 s
->for_vec
, s
->capture_ids
);
876 simplifiers
.safe_push (ns
);
880 /* Strip conditional conversios using operator OPER from O and its
881 children if STRIP, else replace them with an unconditional convert. */
884 lower_opt_convert (operand
*o
, enum tree_code oper
,
885 enum tree_code to_oper
, bool strip
)
887 if (capture
*c
= dyn_cast
<capture
*> (o
))
890 return new capture (c
->location
, c
->where
,
891 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
896 expr
*e
= dyn_cast
<expr
*> (o
);
900 if (*e
->operation
== oper
)
903 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
905 expr
*ne
= new expr (e
);
906 ne
->operation
= (to_oper
== CONVERT_EXPR
907 ? get_operator ("CONVERT_EXPR")
908 : get_operator ("VIEW_CONVERT_EXPR"));
909 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
913 expr
*ne
= new expr (e
);
914 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
915 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
920 /* Determine whether O or its children uses the conditional conversion
924 has_opt_convert (operand
*o
, enum tree_code oper
)
926 if (capture
*c
= dyn_cast
<capture
*> (o
))
929 return has_opt_convert (c
->what
, oper
);
934 expr
*e
= dyn_cast
<expr
*> (o
);
938 if (*e
->operation
== oper
)
941 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
942 if (has_opt_convert (e
->ops
[i
], oper
))
948 /* Lower conditional convert operators in O, expanding it to a vector
951 static vec
<operand
*>
952 lower_opt_convert (operand
*o
)
954 vec
<operand
*> v1
= vNULL
, v2
;
958 enum tree_code opers
[]
959 = { CONVERT0
, CONVERT_EXPR
,
960 CONVERT1
, CONVERT_EXPR
,
961 CONVERT2
, CONVERT_EXPR
,
962 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
963 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
964 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
966 /* Conditional converts are lowered to a pattern with the
967 conversion and one without. The three different conditional
968 convert codes are lowered separately. */
970 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
973 for (unsigned j
= 0; j
< v1
.length (); ++j
)
974 if (has_opt_convert (v1
[j
], opers
[i
]))
976 v2
.safe_push (lower_opt_convert (v1
[j
],
977 opers
[i
], opers
[i
+1], false));
978 v2
.safe_push (lower_opt_convert (v1
[j
],
979 opers
[i
], opers
[i
+1], true));
985 for (unsigned j
= 0; j
< v2
.length (); ++j
)
986 v1
.safe_push (v2
[j
]);
993 /* Lower conditional convert operators in the AST of S and push
994 the resulting multiple patterns to SIMPLIFIERS. */
997 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
999 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1000 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1002 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1003 s
->for_vec
, s
->capture_ids
);
1004 simplifiers
.safe_push (ns
);
1008 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1009 GENERIC and a GIMPLE variant. */
1011 static vec
<operand
*>
1012 lower_cond (operand
*o
)
1014 vec
<operand
*> ro
= vNULL
;
1016 if (capture
*c
= dyn_cast
<capture
*> (o
))
1020 vec
<operand
*> lop
= vNULL
;
1021 lop
= lower_cond (c
->what
);
1023 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1024 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
]));
1029 expr
*e
= dyn_cast
<expr
*> (o
);
1030 if (!e
|| e
->ops
.length () == 0)
1036 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1037 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1038 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1040 auto_vec
< vec
<operand
*> > result
;
1041 auto_vec
<operand
*> v (e
->ops
.length ());
1042 v
.quick_grow_cleared (e
->ops
.length ());
1043 cartesian_product (ops_vector
, result
, v
, 0);
1045 for (unsigned i
= 0; i
< result
.length (); ++i
)
1047 expr
*ne
= new expr (e
);
1048 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1049 ne
->append_op (result
[i
][j
]);
1051 /* If this is a COND with a captured expression or an
1052 expression with two operands then also match a GENERIC
1053 form on the compare. */
1054 if ((*e
->operation
== COND_EXPR
1055 || *e
->operation
== VEC_COND_EXPR
)
1056 && ((is_a
<capture
*> (e
->ops
[0])
1057 && as_a
<capture
*> (e
->ops
[0])->what
1058 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1060 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1061 || (is_a
<expr
*> (e
->ops
[0])
1062 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1064 expr
*ne
= new expr (e
);
1065 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1066 ne
->append_op (result
[i
][j
]);
1067 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1069 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1070 expr
*cmp
= new expr (ocmp
);
1071 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1072 cmp
->append_op (ocmp
->ops
[j
]);
1073 cmp
->is_generic
= true;
1074 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
);
1078 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1079 expr
*cmp
= new expr (ocmp
);
1080 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1081 cmp
->append_op (ocmp
->ops
[j
]);
1082 cmp
->is_generic
= true;
1092 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1093 GENERIC and a GIMPLE variant. */
1096 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1098 vec
<operand
*> matchers
= lower_cond (s
->match
);
1099 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1101 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1102 s
->for_vec
, s
->capture_ids
);
1103 simplifiers
.safe_push (ns
);
1107 /* In AST operand O replace operator ID with operator WITH. */
1110 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1112 /* Deep-copy captures and expressions, replacing operations as
1114 if (capture
*c
= dyn_cast
<capture
*> (o
))
1118 return new capture (c
->location
, c
->where
,
1119 replace_id (c
->what
, id
, with
));
1121 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1123 expr
*ne
= new expr (e
);
1124 if (e
->operation
== id
)
1125 ne
->operation
= with
;
1126 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1127 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1130 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1132 with_expr
*nw
= new with_expr (w
->location
);
1133 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1134 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1137 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1139 if_expr
*nife
= new if_expr (ife
->location
);
1140 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1141 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1143 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1147 /* For c_expr we simply record a string replacement table which is
1148 applied at code-generation time. */
1149 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1151 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1152 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1153 return new c_expr (ce
->r
, ce
->location
,
1154 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1160 /* Return true if the binary operator OP is ok for delayed substitution
1161 during for lowering. */
1164 binary_ok (operator_id
*op
)
1171 case TRUNC_DIV_EXPR
:
1173 case FLOOR_DIV_EXPR
:
1174 case ROUND_DIV_EXPR
:
1175 case TRUNC_MOD_EXPR
:
1177 case FLOOR_MOD_EXPR
:
1178 case ROUND_MOD_EXPR
:
1180 case EXACT_DIV_EXPR
:
1192 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1195 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1197 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1198 unsigned worklist_start
= 0;
1199 auto_vec
<simplify
*> worklist
;
1200 worklist
.safe_push (sin
);
1202 /* Lower each recorded for separately, operating on the
1203 set of simplifiers created by the previous one.
1204 Lower inner-to-outer so inner for substitutes can refer
1205 to operators replaced by outer fors. */
1206 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1208 vec
<user_id
*>& ids
= for_vec
[fi
];
1209 unsigned n_ids
= ids
.length ();
1210 unsigned max_n_opers
= 0;
1211 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1212 for (unsigned i
= 0; i
< n_ids
; ++i
)
1214 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1215 max_n_opers
= ids
[i
]->substitutes
.length ();
1216 /* Require that all substitutes are of the same kind so that
1217 if we delay substitution to the result op code generation
1218 can look at the first substitute for deciding things like
1219 types of operands. */
1220 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1221 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1222 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1223 can_delay_subst
= false;
1224 else if (operator_id
*op
1225 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1228 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1229 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1230 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1232 /* Unfortunately we can't just allow all tcc_binary. */
1233 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1234 && strcmp (op0
->tcc
, "tcc_binary") == 0
1238 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1239 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1240 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1241 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1244 can_delay_subst
= false;
1246 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1249 can_delay_subst
= false;
1252 unsigned worklist_end
= worklist
.length ();
1253 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1255 simplify
*s
= worklist
[si
];
1256 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1258 operand
*match_op
= s
->match
;
1259 operand
*result_op
= s
->result
;
1260 vec
<std::pair
<user_id
*, id_base
*> > subst
;
1261 subst
.create (n_ids
);
1262 for (unsigned i
= 0; i
< n_ids
; ++i
)
1264 user_id
*id
= ids
[i
];
1265 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1266 subst
.quick_push (std::make_pair (id
, oper
));
1267 match_op
= replace_id (match_op
, id
, oper
);
1269 && !can_delay_subst
)
1270 result_op
= replace_id (result_op
, id
, oper
);
1272 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1273 vNULL
, s
->capture_ids
);
1274 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1277 ns
->for_subst_vec
.safe_splice (subst
);
1280 worklist
.safe_push (ns
);
1283 worklist_start
= worklist_end
;
1286 /* Copy out the result from the last for lowering. */
1287 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1288 simplifiers
.safe_push (worklist
[i
]);
1291 /* Lower the AST for everything in SIMPLIFIERS. */
1294 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1296 auto_vec
<simplify
*> out_simplifiers
;
1297 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1298 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1300 simplifiers
.truncate (0);
1301 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1302 lower_commutative (out_simplifiers
[i
], simplifiers
);
1304 out_simplifiers
.truncate (0);
1306 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1307 lower_cond (simplifiers
[i
], out_simplifiers
);
1309 out_simplifiers
.safe_splice (simplifiers
);
1312 simplifiers
.truncate (0);
1313 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1314 lower_for (out_simplifiers
[i
], simplifiers
);
1320 /* The decision tree built for generating GIMPLE and GENERIC pattern
1321 matching code. It represents the 'match' expression of all
1322 simplifies and has those as its leafs. */
1326 /* A hash-map collecting semantically equivalent leafs in the decision
1327 tree for splitting out to separate functions. */
1336 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
> >
1338 static inline hashval_t
hash (const key_type
&);
1339 static inline bool equal_keys (const key_type
&, const key_type
&);
1340 template <typename T
> static inline void remove (T
&) {}
1343 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1347 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1351 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1355 vec
<dt_node
*> kids
;
1359 unsigned total_size
;
1362 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1364 dt_node
*append_node (dt_node
*);
1365 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1366 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1367 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1368 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1370 virtual void gen (FILE *, int, bool) {}
1372 void gen_kids (FILE *, int, bool);
1373 void gen_kids_1 (FILE *, int, bool,
1374 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1375 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1377 void analyze (sinfo_map_t
&);
1380 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1382 struct dt_operand
: public dt_node
1385 dt_operand
*match_dop
;
1389 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1390 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1391 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1392 parent (parent_
), pos (pos_
) {}
1394 void gen (FILE *, int, bool);
1395 unsigned gen_predicate (FILE *, int, const char *, bool);
1396 unsigned gen_match_op (FILE *, int, const char *);
1398 unsigned gen_gimple_expr (FILE *, int);
1399 unsigned gen_generic_expr (FILE *, int, const char *);
1401 char *get_name (char *);
1402 void gen_opname (char *, unsigned);
1405 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1407 struct dt_simplify
: public dt_node
1410 unsigned pattern_no
;
1411 dt_operand
**indexes
;
1414 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1415 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1416 indexes (indexes_
), info (NULL
) {}
1418 void gen_1 (FILE *, int, bool, operand
*);
1419 void gen (FILE *f
, int, bool);
1425 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1427 return (n
->type
== dt_node::DT_OPERAND
1428 || n
->type
== dt_node::DT_MATCH
);
1434 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1436 return n
->type
== dt_node::DT_SIMPLIFY
;
1441 /* A container for the actual decision tree. */
1443 struct decision_tree
1447 void insert (struct simplify
*, unsigned);
1448 void gen (FILE *f
, bool gimple
);
1449 void print (FILE *f
= stderr
);
1451 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1453 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1454 unsigned pos
= 0, dt_node
*parent
= 0);
1455 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1456 static bool cmp_node (dt_node
*, dt_node
*);
1457 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1460 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1463 cmp_operand (operand
*o1
, operand
*o2
)
1465 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1468 if (o1
->type
== operand::OP_PREDICATE
)
1470 predicate
*p1
= as_a
<predicate
*>(o1
);
1471 predicate
*p2
= as_a
<predicate
*>(o2
);
1472 return p1
->p
== p2
->p
;
1474 else if (o1
->type
== operand::OP_EXPR
)
1476 expr
*e1
= static_cast<expr
*>(o1
);
1477 expr
*e2
= static_cast<expr
*>(o2
);
1478 return (e1
->operation
== e2
->operation
1479 && e1
->is_generic
== e2
->is_generic
);
1485 /* Compare two decision tree nodes N1 and N2 and return true if they
1489 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1491 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1497 if (n1
->type
== dt_node::DT_TRUE
)
1500 if (n1
->type
== dt_node::DT_OPERAND
)
1501 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1502 (as_a
<dt_operand
*> (n2
))->op
);
1503 else if (n1
->type
== dt_node::DT_MATCH
)
1504 return ((as_a
<dt_operand
*> (n1
))->match_dop
1505 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1509 /* Search OPS for a decision tree node like P and return it if found. */
1512 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1514 /* We can merge adjacent DT_TRUE. */
1515 if (p
->type
== dt_node::DT_TRUE
1517 && ops
.last ()->type
== dt_node::DT_TRUE
)
1519 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1521 /* But we can't merge across DT_TRUE nodes as they serve as
1522 pattern order barriers to make sure that patterns apply
1523 in order of appearance in case multiple matches are possible. */
1524 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1526 if (decision_tree::cmp_node (ops
[i
], p
))
1532 /* Append N to the decision tree if it there is not already an existing
1536 dt_node::append_node (dt_node
*n
)
1540 kid
= decision_tree::find_node (kids
, n
);
1545 n
->level
= this->level
+ 1;
1550 /* Append OP to the decision tree. */
1553 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1555 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1556 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1557 return append_node (n
);
1560 /* Append a DT_TRUE decision tree node. */
1563 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1565 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1566 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1567 return append_node (n
);
1570 /* Append a DT_MATCH decision tree node. */
1573 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1575 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1576 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1577 return append_node (n
);
1580 /* Append S to the decision tree. */
1583 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1584 dt_operand
**indexes
)
1586 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1587 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1588 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1590 warning_at (s
->match
->location
, "duplicate pattern");
1591 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1592 print_operand (s
->match
, stderr
);
1593 fprintf (stderr
, "\n");
1595 return append_node (n
);
1598 /* Analyze the node and its children. */
1601 dt_node::analyze (sinfo_map_t
&map
)
1607 if (type
== DT_SIMPLIFY
)
1609 /* Populate the map of equivalent simplifies. */
1610 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1612 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1627 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1629 kids
[i
]->analyze (map
);
1630 num_leafs
+= kids
[i
]->num_leafs
;
1631 total_size
+= kids
[i
]->total_size
;
1632 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1636 /* Insert O into the decision tree and return the decision tree node found
1640 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1641 unsigned pos
, dt_node
*parent
)
1643 dt_node
*q
, *elm
= 0;
1645 if (capture
*c
= dyn_cast
<capture
*> (o
))
1647 unsigned capt_index
= c
->where
;
1649 if (indexes
[capt_index
] == 0)
1652 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1655 q
= elm
= p
->append_true_op (parent
, pos
);
1658 // get to the last capture
1659 for (operand
*what
= c
->what
;
1660 what
&& is_a
<capture
*> (what
);
1661 c
= as_a
<capture
*> (what
), what
= c
->what
)
1666 unsigned cc_index
= c
->where
;
1667 dt_operand
*match_op
= indexes
[cc_index
];
1669 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1670 elm
= decision_tree::find_node (p
->kids
, &temp
);
1674 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1675 elm
= decision_tree::find_node (p
->kids
, &temp
);
1680 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1681 elm
= decision_tree::find_node (p
->kids
, &temp
);
1685 gcc_assert (elm
->type
== dt_node::DT_TRUE
1686 || elm
->type
== dt_node::DT_OPERAND
1687 || elm
->type
== dt_node::DT_MATCH
);
1688 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1693 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1695 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1700 p
= p
->append_op (o
, parent
, pos
);
1703 if (expr
*e
= dyn_cast
<expr
*>(o
))
1705 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1706 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1712 /* Insert S into the decision tree. */
1715 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1717 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1718 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1719 p
->append_simplify (s
, pattern_no
, indexes
);
1722 /* Debug functions to dump the decision tree. */
1725 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1727 if (p
->type
== dt_node::DT_NODE
)
1728 fprintf (f
, "root");
1732 for (unsigned i
= 0; i
< indent
; i
++)
1735 if (p
->type
== dt_node::DT_OPERAND
)
1737 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1738 print_operand (dop
->op
, f
, true);
1740 else if (p
->type
== dt_node::DT_TRUE
)
1741 fprintf (f
, "true");
1742 else if (p
->type
== dt_node::DT_MATCH
)
1743 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1744 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1746 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1747 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1748 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1749 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1754 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1756 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1757 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1761 decision_tree::print (FILE *f
)
1763 return decision_tree::print_node (root
, f
);
1767 /* For GENERIC we have to take care of wrapping multiple-used
1768 expressions with side-effects in save_expr and preserve side-effects
1769 of expressions with omit_one_operand. Analyze captures in
1770 match, result and with expressions and perform early-outs
1771 on the outermost match expression operands for cases we cannot
1776 capture_info (simplify
*s
, operand
*, bool);
1777 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1778 bool walk_result (operand
*o
, bool, operand
*);
1779 void walk_c_expr (c_expr
*);
1785 bool force_no_side_effects_p
;
1786 bool force_single_use
;
1787 bool cond_expr_cond_p
;
1788 unsigned long toplevel_msk
;
1789 int result_use_count
;
1794 auto_vec
<cinfo
> info
;
1795 unsigned long force_no_side_effects
;
1799 /* Analyze captures in S. */
1801 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
1806 if (s
->kind
== simplify::MATCH
)
1808 force_no_side_effects
= -1;
1812 force_no_side_effects
= 0;
1813 info
.safe_grow_cleared (s
->capture_max
+ 1);
1814 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1815 info
[i
].same_as
= i
;
1817 e
= as_a
<expr
*> (s
->match
);
1818 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1819 walk_match (e
->ops
[i
], i
,
1820 (i
!= 0 && *e
->operation
== COND_EXPR
)
1821 || *e
->operation
== TRUTH_ANDIF_EXPR
1822 || *e
->operation
== TRUTH_ORIF_EXPR
,
1824 && (*e
->operation
== COND_EXPR
1825 || *e
->operation
== VEC_COND_EXPR
));
1827 walk_result (s
->result
, false, result
);
1830 /* Analyze captures in the match expression piece O. */
1833 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1834 bool conditional_p
, bool cond_expr_cond_p
)
1836 if (capture
*c
= dyn_cast
<capture
*> (o
))
1838 unsigned where
= c
->where
;
1839 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
1840 info
[where
].force_no_side_effects_p
|= conditional_p
;
1841 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1846 /* Recurse to exprs and captures. */
1847 if (is_a
<capture
*> (c
->what
)
1848 || is_a
<expr
*> (c
->what
))
1849 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1850 /* We need to look past multiple captures to find a captured
1851 expression as with conditional converts two captures
1852 can be collapsed onto the same expression. Also collect
1853 what captures capture the same thing. */
1854 while (c
->what
&& is_a
<capture
*> (c
->what
))
1856 c
= as_a
<capture
*> (c
->what
);
1857 if (info
[c
->where
].same_as
!= c
->where
1858 && info
[c
->where
].same_as
!= info
[where
].same_as
)
1859 fatal_at (c
->location
, "cannot handle this collapsed capture");
1860 info
[c
->where
].same_as
= info
[where
].same_as
;
1862 /* Mark expr (non-leaf) captures and forced single-use exprs. */
1865 && (e
= dyn_cast
<expr
*> (c
->what
)))
1867 info
[where
].expr_p
= true;
1868 info
[where
].force_single_use
|= e
->force_single_use
;
1871 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1873 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1875 bool cond_p
= conditional_p
;
1876 bool cond_expr_cond_p
= false;
1877 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1879 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1880 || *e
->operation
== TRUTH_ORIF_EXPR
)
1883 && (*e
->operation
== COND_EXPR
1884 || *e
->operation
== VEC_COND_EXPR
))
1885 cond_expr_cond_p
= true;
1886 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1889 else if (is_a
<predicate
*> (o
))
1891 /* Mark non-captured leafs toplevel arg for checking. */
1892 force_no_side_effects
|= 1 << toplevel_arg
;
1895 warning_at (o
->location
,
1896 "forcing no side-effects on possibly lost leaf");
1902 /* Analyze captures in the result expression piece O. Return true
1903 if RESULT was visited in one of the children. Only visit
1904 non-if/with children if they are rooted on RESULT. */
1907 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
1909 if (capture
*c
= dyn_cast
<capture
*> (o
))
1911 unsigned where
= info
[c
->where
].same_as
;
1912 info
[where
].result_use_count
++;
1913 /* If we substitute an expression capture we don't know
1914 which captures this will end up using (well, we don't
1915 compute that). Force the uses to be side-effect free
1916 which means forcing the toplevels that reach the
1917 expression side-effect free. */
1918 if (info
[where
].expr_p
)
1919 force_no_side_effects
|= info
[where
].toplevel_msk
;
1920 /* Mark CSE capture uses as forced to have no side-effects. */
1922 && is_a
<expr
*> (c
->what
))
1924 info
[where
].cse_p
= true;
1925 walk_result (c
->what
, true, result
);
1928 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1930 id_base
*opr
= e
->operation
;
1931 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
1932 opr
= uid
->substitutes
[0];
1933 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1935 bool cond_p
= conditional_p
;
1936 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1938 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1939 || *e
->operation
== TRUTH_ORIF_EXPR
)
1941 walk_result (e
->ops
[i
], cond_p
, result
);
1944 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
1946 /* 'if' conditions should be all fine. */
1947 if (e
->trueexpr
== result
)
1949 walk_result (e
->trueexpr
, false, result
);
1952 if (e
->falseexpr
== result
)
1954 walk_result (e
->falseexpr
, false, result
);
1958 if (is_a
<if_expr
*> (e
->trueexpr
)
1959 || is_a
<with_expr
*> (e
->trueexpr
))
1960 res
|= walk_result (e
->trueexpr
, false, result
);
1962 && (is_a
<if_expr
*> (e
->falseexpr
)
1963 || is_a
<with_expr
*> (e
->falseexpr
)))
1964 res
|= walk_result (e
->falseexpr
, false, result
);
1967 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
1969 bool res
= (e
->subexpr
== result
);
1971 || is_a
<if_expr
*> (e
->subexpr
)
1972 || is_a
<with_expr
*> (e
->subexpr
))
1973 res
|= walk_result (e
->subexpr
, false, result
);
1975 walk_c_expr (e
->with
);
1978 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1986 /* Look for captures in the C expr E. */
1989 capture_info::walk_c_expr (c_expr
*e
)
1991 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
1992 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
1993 really escape through. */
1994 unsigned p_depth
= 0;
1995 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1997 const cpp_token
*t
= &e
->code
[i
];
1998 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2000 if (t
->type
== CPP_NAME
2001 && (strcmp ((const char *)CPP_HASHNODE
2002 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2003 || strcmp ((const char *)CPP_HASHNODE
2004 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2005 || strcmp ((const char *)CPP_HASHNODE
2006 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2007 || ((id
= get_operator ((const char *)CPP_HASHNODE
2008 (t
->val
.node
.node
)->ident
.str
))
2009 && is_a
<predicate_id
*> (id
)))
2010 && n
->type
== CPP_OPEN_PAREN
)
2012 else if (t
->type
== CPP_CLOSE_PAREN
2015 else if (p_depth
== 0
2016 && t
->type
== CPP_ATSIGN
2017 && (n
->type
== CPP_NUMBER
2018 || n
->type
== CPP_NAME
)
2019 && !(n
->flags
& PREV_WHITE
))
2022 if (n
->type
== CPP_NUMBER
)
2023 id
= (const char *)n
->val
.str
.text
;
2025 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2026 unsigned where
= *e
->capture_ids
->get(id
);
2027 info
[info
[where
].same_as
].force_no_side_effects_p
= true;
2030 warning_at (t
, "capture escapes");
2036 /* Code generation off the decision tree and the refered AST nodes. */
2039 is_conversion (id_base
*op
)
2041 return (*op
== CONVERT_EXPR
2043 || *op
== FLOAT_EXPR
2044 || *op
== FIX_TRUNC_EXPR
2045 || *op
== VIEW_CONVERT_EXPR
);
2048 /* Get the type to be used for generating operands of OP from the
2052 get_operand_type (id_base
*op
, const char *in_type
,
2053 const char *expr_type
,
2054 const char *other_oprnd_type
)
2056 /* Generally operands whose type does not match the type of the
2057 expression generated need to know their types but match and
2058 thus can fall back to 'other_oprnd_type'. */
2059 if (is_conversion (op
))
2060 return other_oprnd_type
;
2061 else if (*op
== REALPART_EXPR
2062 || *op
== IMAGPART_EXPR
)
2063 return other_oprnd_type
;
2064 else if (is_a
<operator_id
*> (op
)
2065 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2066 return other_oprnd_type
;
2069 /* Otherwise all types should match - choose one in order of
2076 return other_oprnd_type
;
2080 /* Generate transform code for an expression. */
2083 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2084 int depth
, const char *in_type
, capture_info
*cinfo
,
2085 dt_operand
**indexes
, bool)
2087 id_base
*opr
= operation
;
2088 /* When we delay operator substituting during lowering of fors we
2089 make sure that for code-gen purposes the effects of each substitute
2090 are the same. Thus just look at that. */
2091 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2092 opr
= uid
->substitutes
[0];
2094 bool conversion_p
= is_conversion (opr
);
2095 const char *type
= expr_type
;
2098 /* If there was a type specification in the pattern use it. */
2100 else if (conversion_p
)
2101 /* For conversions we need to build the expression using the
2102 outer type passed in. */
2104 else if (*opr
== REALPART_EXPR
2105 || *opr
== IMAGPART_EXPR
)
2107 /* __real and __imag use the component type of its operand. */
2108 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2111 else if (is_a
<operator_id
*> (opr
)
2112 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2114 /* comparisons use boolean_type_node (or what gets in), but
2115 their operands need to figure out the types themselves. */
2116 sprintf (optype
, "boolean_type_node");
2119 else if (*opr
== COND_EXPR
2120 || *opr
== VEC_COND_EXPR
)
2122 /* Conditions are of the same type as their first alternative. */
2123 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2128 /* Other operations are of the same type as their first operand. */
2129 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2133 fatal_at (location
, "cannot determine type of operand");
2135 fprintf_indent (f
, indent
, "{\n");
2137 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2139 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2140 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2143 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2145 = get_operand_type (opr
, in_type
, expr_type
,
2146 i
== 0 ? NULL
: op0type
);
2147 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2149 ((!(*opr
== COND_EXPR
)
2150 && !(*opr
== VEC_COND_EXPR
))
2154 const char *opr_name
;
2155 if (*operation
== CONVERT_EXPR
)
2156 opr_name
= "NOP_EXPR";
2158 opr_name
= operation
->id
;
2162 if (*opr
== CONVERT_EXPR
)
2164 fprintf_indent (f
, indent
,
2165 "if (%s != TREE_TYPE (ops%d[0])\n",
2167 fprintf_indent (f
, indent
,
2168 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2170 fprintf_indent (f
, indent
+ 2, "{\n");
2173 /* ??? Building a stmt can fail for various reasons here, seq being
2174 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2175 So if we fail here we should continue matching other patterns. */
2176 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2177 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2178 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2179 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2180 i
== ops
.length () - 1 ? " };\n" : ", ");
2181 fprintf_indent (f
, indent
,
2182 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2183 ops
.length (), type
);
2184 fprintf_indent (f
, indent
,
2185 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2187 fprintf_indent (f
, indent
,
2188 "if (!res) return false;\n");
2189 if (*opr
== CONVERT_EXPR
)
2192 fprintf_indent (f
, indent
, " }\n");
2193 fprintf_indent (f
, indent
, "else\n");
2194 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2199 if (*opr
== CONVERT_EXPR
)
2201 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2205 if (opr
->kind
== id_base::CODE
)
2206 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2207 ops
.length(), opr_name
, type
);
2210 fprintf_indent (f
, indent
, "{\n");
2211 fprintf_indent (f
, indent
, " tree decl = builtin_decl_implicit (%s);\n",
2213 fprintf_indent (f
, indent
, " if (!decl) return NULL_TREE;\n");
2214 fprintf_indent (f
, indent
, " res = build_call_expr_loc (loc, "
2215 "decl, %d", ops
.length());
2217 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2218 fprintf (f
, ", ops%d[%u]", depth
, i
);
2219 fprintf (f
, ");\n");
2220 if (opr
->kind
!= id_base::CODE
)
2221 fprintf_indent (f
, indent
, "}\n");
2222 if (*opr
== CONVERT_EXPR
)
2225 fprintf_indent (f
, indent
, "else\n");
2226 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2229 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2231 fprintf_indent (f
, indent
, "}\n");
2234 /* Generate code for a c_expr which is either the expression inside
2235 an if statement or a sequence of statements which computes a
2236 result to be stored to DEST. */
2239 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2240 bool, int, const char *, capture_info
*,
2241 dt_operand
**, bool)
2243 if (dest
&& nr_stmts
== 1)
2244 fprintf_indent (f
, indent
, "%s = ", dest
);
2246 unsigned stmt_nr
= 1;
2247 for (unsigned i
= 0; i
< code
.length (); ++i
)
2249 const cpp_token
*token
= &code
[i
];
2251 /* Replace captures for code-gen. */
2252 if (token
->type
== CPP_ATSIGN
)
2254 const cpp_token
*n
= &code
[i
+1];
2255 if ((n
->type
== CPP_NUMBER
2256 || n
->type
== CPP_NAME
)
2257 && !(n
->flags
& PREV_WHITE
))
2259 if (token
->flags
& PREV_WHITE
)
2262 if (n
->type
== CPP_NUMBER
)
2263 id
= (const char *)n
->val
.str
.text
;
2265 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2266 unsigned *cid
= capture_ids
->get (id
);
2268 fatal_at (token
, "unknown capture id");
2269 fprintf (f
, "captures[%u]", *cid
);
2275 if (token
->flags
& PREV_WHITE
)
2278 if (token
->type
== CPP_NAME
)
2280 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2282 for (j
= 0; j
< ids
.length (); ++j
)
2284 if (strcmp (id
, ids
[j
].id
) == 0)
2286 fprintf (f
, "%s", ids
[j
].oper
);
2290 if (j
< ids
.length ())
2294 /* Output the token as string. */
2295 char *tk
= (char *)cpp_token_as_text (r
, token
);
2298 if (token
->type
== CPP_SEMICOLON
)
2302 if (dest
&& stmt_nr
== nr_stmts
)
2303 fprintf_indent (f
, indent
, "%s = ", dest
);
2308 /* Generate transform code for a capture. */
2311 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2312 int depth
, const char *in_type
, capture_info
*cinfo
,
2313 dt_operand
**indexes
, bool expand_compares
)
2315 if (what
&& is_a
<expr
*> (what
))
2317 if (indexes
[where
] == 0)
2320 sprintf (buf
, "captures[%u]", where
);
2321 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2326 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2328 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2329 with substituting a capture of that.
2330 ??? Returning false here will also not allow any other patterns
2332 if (gimple
&& expand_compares
2333 && cinfo
->info
[where
].cond_expr_cond_p
)
2335 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2336 fprintf_indent (f
, indent
, " {\n");
2337 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2338 fprintf_indent (f
, indent
, " %s = gimple_build (seq, TREE_CODE (%s),"
2339 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2340 " TREE_OPERAND (%s, 1));\n",
2341 dest
, dest
, dest
, dest
, dest
);
2342 fprintf_indent (f
, indent
, " }\n");
2346 /* Return the name of the operand representing the decision tree node.
2347 Use NAME as space to generate it. */
2350 dt_operand::get_name (char *name
)
2353 sprintf (name
, "t");
2354 else if (parent
->level
== 1)
2355 sprintf (name
, "op%u", pos
);
2356 else if (parent
->type
== dt_node::DT_MATCH
)
2357 return parent
->get_name (name
);
2359 sprintf (name
, "o%u%u", parent
->level
, pos
);
2363 /* Fill NAME with the operand name at position POS. */
2366 dt_operand::gen_opname (char *name
, unsigned pos
)
2369 sprintf (name
, "op%u", pos
);
2371 sprintf (name
, "o%u%u", level
, pos
);
2374 /* Generate matching code for the decision tree operand which is
2378 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2380 predicate
*p
= as_a
<predicate
*> (op
);
2382 if (p
->p
->matchers
.exists ())
2384 /* If this is a predicate generated from a pattern mangle its
2385 name and pass on the valueize hook. */
2387 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2390 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2393 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2394 fprintf_indent (f
, indent
+ 2, "{\n");
2398 /* Generate matching code for the decision tree operand which is
2402 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
)
2404 char match_opname
[20];
2405 match_dop
->get_name (match_opname
);
2406 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2407 opname
, match_opname
, opname
, match_opname
);
2408 fprintf_indent (f
, indent
+ 2, "{\n");
2412 /* Generate GIMPLE matching code for the decision tree operand. */
2415 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2417 expr
*e
= static_cast<expr
*> (op
);
2418 id_base
*id
= e
->operation
;
2419 unsigned n_ops
= e
->ops
.length ();
2421 for (unsigned i
= 0; i
< n_ops
; ++i
)
2423 char child_opname
[20];
2424 gen_opname (child_opname
, i
);
2426 if (id
->kind
== id_base::CODE
)
2429 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2430 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2432 /* ??? If this is a memory operation we can't (and should not)
2433 match this. The only sensible operand types are
2434 SSA names and invariants. */
2435 fprintf_indent (f
, indent
,
2436 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def), %i);\n",
2438 fprintf_indent (f
, indent
,
2439 "if ((TREE_CODE (%s) == SSA_NAME\n",
2441 fprintf_indent (f
, indent
,
2442 " || is_gimple_min_invariant (%s))\n",
2444 fprintf_indent (f
, indent
,
2445 " && (%s = do_valueize (valueize, %s)))\n",
2446 child_opname
, child_opname
);
2447 fprintf_indent (f
, indent
,
2453 fprintf_indent (f
, indent
,
2454 "tree %s = gimple_assign_rhs%u (def);\n",
2455 child_opname
, i
+ 1);
2458 fprintf_indent (f
, indent
,
2459 "tree %s = gimple_call_arg (def, %u);\n",
2461 fprintf_indent (f
, indent
,
2462 "if ((%s = do_valueize (valueize, %s)))\n",
2463 child_opname
, child_opname
);
2464 fprintf_indent (f
, indent
, " {\n");
2467 /* While the toplevel operands are canonicalized by the caller
2468 after valueizing operands of sub-expressions we have to
2469 re-canonicalize operand order. */
2470 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2472 /* ??? We can't canonicalize tcc_comparison operands here
2473 because that requires changing the comparison code which
2474 we already matched... */
2475 if (commutative_tree_code (code
->code
)
2476 || commutative_ternary_tree_code (code
->code
))
2478 char child_opname0
[20], child_opname1
[20];
2479 gen_opname (child_opname0
, 0);
2480 gen_opname (child_opname1
, 1);
2481 fprintf_indent (f
, indent
,
2482 "if (tree_swap_operands_p (%s, %s, false))\n",
2483 child_opname0
, child_opname1
);
2484 fprintf_indent (f
, indent
,
2485 " std::swap (%s, %s);\n",
2486 child_opname0
, child_opname1
);
2493 /* Generate GENERIC matching code for the decision tree operand. */
2496 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2498 expr
*e
= static_cast<expr
*> (op
);
2499 unsigned n_ops
= e
->ops
.length ();
2501 for (unsigned i
= 0; i
< n_ops
; ++i
)
2503 char child_opname
[20];
2504 gen_opname (child_opname
, i
);
2506 if (e
->operation
->kind
== id_base::CODE
)
2507 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2508 child_opname
, opname
, i
);
2510 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2511 child_opname
, opname
, i
);
2517 /* Generate matching code for the children of the decision tree node. */
2520 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2522 auto_vec
<dt_operand
*> gimple_exprs
;
2523 auto_vec
<dt_operand
*> generic_exprs
;
2524 auto_vec
<dt_operand
*> fns
;
2525 auto_vec
<dt_operand
*> generic_fns
;
2526 auto_vec
<dt_operand
*> preds
;
2527 auto_vec
<dt_node
*> others
;
2529 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2531 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2533 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2534 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2536 if (e
->ops
.length () == 0
2537 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2538 generic_exprs
.safe_push (op
);
2539 else if (e
->operation
->kind
== id_base::FN
)
2544 generic_fns
.safe_push (op
);
2546 else if (e
->operation
->kind
== id_base::PREDICATE
)
2547 preds
.safe_push (op
);
2551 gimple_exprs
.safe_push (op
);
2553 generic_exprs
.safe_push (op
);
2556 else if (op
->op
->type
== operand::OP_PREDICATE
)
2557 others
.safe_push (kids
[i
]);
2561 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2562 others
.safe_push (kids
[i
]);
2563 else if (kids
[i
]->type
== dt_node::DT_MATCH
2564 || kids
[i
]->type
== dt_node::DT_TRUE
)
2566 /* A DT_TRUE operand serves as a barrier - generate code now
2567 for what we have collected sofar.
2568 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2569 dependent matches to get out-of-order. Generate code now
2570 for what we have collected sofar. */
2571 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2572 fns
, generic_fns
, preds
, others
);
2573 /* And output the true operand itself. */
2574 kids
[i
]->gen (f
, indent
, gimple
);
2575 gimple_exprs
.truncate (0);
2576 generic_exprs
.truncate (0);
2578 generic_fns
.truncate (0);
2580 others
.truncate (0);
2586 /* Generate code for the remains. */
2587 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2588 fns
, generic_fns
, preds
, others
);
2591 /* Generate matching code for the children of the decision tree node. */
2594 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2595 vec
<dt_operand
*> gimple_exprs
,
2596 vec
<dt_operand
*> generic_exprs
,
2597 vec
<dt_operand
*> fns
,
2598 vec
<dt_operand
*> generic_fns
,
2599 vec
<dt_operand
*> preds
,
2600 vec
<dt_node
*> others
)
2603 char *kid_opname
= buf
;
2605 unsigned exprs_len
= gimple_exprs
.length ();
2606 unsigned gexprs_len
= generic_exprs
.length ();
2607 unsigned fns_len
= fns
.length ();
2608 unsigned gfns_len
= generic_fns
.length ();
2610 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2613 gimple_exprs
[0]->get_name (kid_opname
);
2615 fns
[0]->get_name (kid_opname
);
2617 generic_fns
[0]->get_name (kid_opname
);
2619 generic_exprs
[0]->get_name (kid_opname
);
2621 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2622 fprintf_indent (f
, indent
, " {\n");
2626 if (exprs_len
|| fns_len
)
2628 fprintf_indent (f
, indent
,
2629 "case SSA_NAME:\n");
2630 fprintf_indent (f
, indent
,
2631 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2633 fprintf_indent (f
, indent
,
2635 fprintf_indent (f
, indent
,
2636 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2642 fprintf_indent (f
, indent
,
2643 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2644 fprintf_indent (f
, indent
,
2645 " switch (gimple_assign_rhs_code (def))\n");
2647 fprintf_indent (f
, indent
, "{\n");
2648 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2650 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2651 id_base
*op
= e
->operation
;
2652 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2653 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2655 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2656 fprintf_indent (f
, indent
, " {\n");
2657 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2658 fprintf_indent (f
, indent
, " break;\n");
2659 fprintf_indent (f
, indent
, " }\n");
2661 fprintf_indent (f
, indent
, "default:;\n");
2662 fprintf_indent (f
, indent
, "}\n");
2668 fprintf_indent (f
, indent
,
2669 "%sif (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n",
2670 exprs_len
? "else " : "");
2671 fprintf_indent (f
, indent
,
2673 fprintf_indent (f
, indent
,
2674 " gcall *def = as_a <gcall *> (def_stmt);\n");
2675 fprintf_indent (f
, indent
,
2676 " tree fndecl = gimple_call_fndecl (def);\n");
2677 fprintf_indent (f
, indent
,
2678 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2679 fprintf_indent (f
, indent
,
2683 for (unsigned i
= 0; i
< fns_len
; ++i
)
2685 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2686 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2687 fprintf_indent (f
, indent
, " {\n");
2688 fns
[i
]->gen (f
, indent
+ 4, true);
2689 fprintf_indent (f
, indent
, " break;\n");
2690 fprintf_indent (f
, indent
, " }\n");
2693 fprintf_indent (f
, indent
, "default:;\n");
2694 fprintf_indent (f
, indent
, "}\n");
2696 fprintf_indent (f
, indent
, " }\n");
2700 fprintf_indent (f
, indent
, " }\n");
2701 fprintf_indent (f
, indent
, " break;\n");
2704 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2706 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2707 id_base
*op
= e
->operation
;
2708 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2709 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2711 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2712 fprintf_indent (f
, indent
, " {\n");
2713 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2714 fprintf_indent (f
, indent
, " break;\n");
2715 fprintf_indent (f
, indent
, " }\n");
2720 fprintf_indent (f
, indent
,
2721 "case CALL_EXPR:\n");
2722 fprintf_indent (f
, indent
,
2724 fprintf_indent (f
, indent
,
2725 " tree fndecl = get_callee_fndecl (%s);\n",
2727 fprintf_indent (f
, indent
,
2728 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2729 fprintf_indent (f
, indent
,
2730 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2731 fprintf_indent (f
, indent
,
2735 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2737 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2738 gcc_assert (e
->operation
->kind
== id_base::FN
);
2740 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2741 fprintf_indent (f
, indent
, " {\n");
2742 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2743 fprintf_indent (f
, indent
, " break;\n");
2744 fprintf_indent (f
, indent
, " }\n");
2748 fprintf_indent (f
, indent
, " default:;\n");
2749 fprintf_indent (f
, indent
, " }\n");
2750 fprintf_indent (f
, indent
, " break;\n");
2751 fprintf_indent (f
, indent
, " }\n");
2754 /* Close switch (TREE_CODE ()). */
2755 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2758 fprintf_indent (f
, indent
, " default:;\n");
2759 fprintf_indent (f
, indent
, " }\n");
2762 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2764 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2765 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2766 preds
[i
]->get_name (kid_opname
);
2767 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2768 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2769 gimple
? "gimple" : "tree",
2770 p
->id
, kid_opname
, kid_opname
,
2771 gimple
? ", valueize" : "");
2772 fprintf_indent (f
, indent
, " {\n");
2773 for (int j
= 0; j
< p
->nargs
; ++j
)
2775 char child_opname
[20];
2776 preds
[i
]->gen_opname (child_opname
, j
);
2777 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2778 child_opname
, kid_opname
, j
);
2780 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2784 for (unsigned i
= 0; i
< others
.length (); ++i
)
2785 others
[i
]->gen (f
, indent
, gimple
);
2788 /* Generate matching code for the decision tree operand. */
2791 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2796 unsigned n_braces
= 0;
2798 if (type
== DT_OPERAND
)
2801 case operand::OP_PREDICATE
:
2802 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2805 case operand::OP_EXPR
:
2807 n_braces
= gen_gimple_expr (f
, indent
);
2809 n_braces
= gen_generic_expr (f
, indent
, opname
);
2815 else if (type
== DT_TRUE
)
2817 else if (type
== DT_MATCH
)
2818 n_braces
= gen_match_op (f
, indent
, opname
);
2822 indent
+= 4 * n_braces
;
2823 gen_kids (f
, indent
, gimple
);
2825 for (unsigned i
= 0; i
< n_braces
; ++i
)
2830 fprintf_indent (f
, indent
, " }\n");
2835 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2836 step of a '(simplify ...)' or '(match ...)'. This handles everything
2837 that is not part of the decision tree (simplify->match).
2838 Main recursive worker. */
2841 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2845 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2847 fprintf_indent (f
, indent
, "{\n");
2849 output_line_directive (f
, w
->location
);
2850 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2851 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2853 fprintf_indent (f
, indent
, "}\n");
2856 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2858 output_line_directive (f
, ife
->location
);
2859 fprintf_indent (f
, indent
, "if (");
2860 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2862 fprintf_indent (f
, indent
+ 2, "{\n");
2864 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2866 fprintf_indent (f
, indent
+ 2, "}\n");
2869 fprintf_indent (f
, indent
, "else\n");
2870 fprintf_indent (f
, indent
+ 2, "{\n");
2872 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2874 fprintf_indent (f
, indent
+ 2, "}\n");
2880 /* Analyze captures and perform early-outs on the incoming arguments
2881 that cover cases we cannot handle. */
2882 capture_info
cinfo (s
, result
, gimple
);
2883 if (s
->kind
== simplify::SIMPLIFY
)
2887 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2888 if (cinfo
.force_no_side_effects
& (1 << i
))
2890 fprintf_indent (f
, indent
,
2891 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2894 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
2895 "forcing toplevel operand to have no "
2898 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2899 if (cinfo
.info
[i
].cse_p
)
2901 else if (cinfo
.info
[i
].force_no_side_effects_p
2902 && (cinfo
.info
[i
].toplevel_msk
2903 & cinfo
.force_no_side_effects
) == 0)
2905 fprintf_indent (f
, indent
,
2906 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2907 "return NULL_TREE;\n", i
);
2909 warning_at (cinfo
.info
[i
].c
->location
,
2910 "forcing captured operand to have no "
2913 else if ((cinfo
.info
[i
].toplevel_msk
2914 & cinfo
.force_no_side_effects
) != 0)
2915 /* Mark capture as having no side-effects if we had to verify
2916 that via forced toplevel operand checks. */
2917 cinfo
.info
[i
].force_no_side_effects_p
= true;
2921 /* Force single-use restriction by only allowing simple
2922 results via setting seq to NULL. */
2923 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2924 bool first_p
= true;
2925 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2926 if (cinfo
.info
[i
].force_single_use
)
2930 fprintf_indent (f
, indent
, "if (lseq\n");
2931 fprintf_indent (f
, indent
, " && (");
2937 fprintf_indent (f
, indent
, " || ");
2939 fprintf (f
, "!single_use (captures[%d])", i
);
2943 fprintf (f
, "))\n");
2944 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2949 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2950 "fprintf (dump_file, \"Applying pattern ");
2951 output_line_directive (f
,
2952 result
? result
->location
: s
->match
->location
, true);
2953 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2957 /* If there is no result then this is a predicate implementation. */
2958 fprintf_indent (f
, indent
, "return true;\n");
2962 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2963 in outermost position). */
2964 if (result
->type
== operand::OP_EXPR
2965 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2966 result
= as_a
<expr
*> (result
)->ops
[0];
2967 if (result
->type
== operand::OP_EXPR
)
2969 expr
*e
= as_a
<expr
*> (result
);
2970 id_base
*opr
= e
->operation
;
2971 bool is_predicate
= false;
2972 /* When we delay operator substituting during lowering of fors we
2973 make sure that for code-gen purposes the effects of each substitute
2974 are the same. Thus just look at that. */
2975 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2976 opr
= uid
->substitutes
[0];
2977 else if (is_a
<predicate_id
*> (opr
))
2978 is_predicate
= true;
2980 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2981 *e
->operation
== CONVERT_EXPR
2982 ? "NOP_EXPR" : e
->operation
->id
);
2983 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2986 snprintf (dest
, 32, "res_ops[%d]", j
);
2988 = get_operand_type (opr
,
2989 "type", e
->expr_type
,
2990 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2991 /* We need to expand GENERIC conditions we captured from
2993 bool expand_generic_cond_exprs_p
2995 /* But avoid doing that if the GENERIC condition is
2996 valid - which it is in the first operand of COND_EXPRs
2997 and VEC_COND_EXRPs. */
2998 && ((!(*opr
== COND_EXPR
)
2999 && !(*opr
== VEC_COND_EXPR
))
3001 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3003 indexes
, expand_generic_cond_exprs_p
);
3006 /* Re-fold the toplevel result. It's basically an embedded
3007 gimple_build w/o actually building the stmt. */
3009 fprintf_indent (f
, indent
,
3010 "gimple_resimplify%d (lseq, res_code, type, "
3011 "res_ops, valueize);\n", e
->ops
.length ());
3013 else if (result
->type
== operand::OP_CAPTURE
3014 || result
->type
== operand::OP_C_EXPR
)
3016 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
3017 &cinfo
, indexes
, false);
3018 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
3019 if (is_a
<capture
*> (result
)
3020 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3022 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3023 with substituting a capture of that. */
3024 fprintf_indent (f
, indent
,
3025 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3026 fprintf_indent (f
, indent
,
3028 fprintf_indent (f
, indent
,
3029 " tree tem = res_ops[0];\n");
3030 fprintf_indent (f
, indent
,
3031 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3032 fprintf_indent (f
, indent
,
3033 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3034 fprintf_indent (f
, indent
,
3040 fprintf_indent (f
, indent
, "return true;\n");
3044 bool is_predicate
= false;
3045 if (result
->type
== operand::OP_EXPR
)
3047 expr
*e
= as_a
<expr
*> (result
);
3048 id_base
*opr
= e
->operation
;
3049 /* When we delay operator substituting during lowering of fors we
3050 make sure that for code-gen purposes the effects of each substitute
3051 are the same. Thus just look at that. */
3052 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3053 opr
= uid
->substitutes
[0];
3054 else if (is_a
<predicate_id
*> (opr
))
3055 is_predicate
= true;
3056 /* Search for captures used multiple times in the result expression
3057 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
3059 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3061 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3063 if (!cinfo
.info
[i
].force_no_side_effects_p
3064 && cinfo
.info
[i
].result_use_count
> 1)
3066 fprintf_indent (f
, indent
,
3067 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3069 fprintf_indent (f
, indent
,
3070 " captures[%d] = save_expr (captures[%d]);\n",
3074 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3078 snprintf (dest
, 32, "res_ops[%d]", j
);
3081 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3082 snprintf (dest
, 32, "res_op%d", j
);
3085 = get_operand_type (opr
,
3086 "type", e
->expr_type
,
3088 ? NULL
: "TREE_TYPE (res_op0)");
3089 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3093 fprintf_indent (f
, indent
, "return true;\n");
3096 fprintf_indent (f
, indent
, "tree res;\n");
3097 /* Re-fold the toplevel result. Use non_lvalue to
3098 build NON_LVALUE_EXPRs so they get properly
3099 ignored when in GIMPLE form. */
3100 if (*opr
== NON_LVALUE_EXPR
)
3101 fprintf_indent (f
, indent
,
3102 "res = non_lvalue_loc (loc, res_op0);\n");
3105 if (is_a
<operator_id
*> (opr
))
3106 fprintf_indent (f
, indent
,
3107 "res = fold_build%d_loc (loc, %s, type",
3109 *e
->operation
== CONVERT_EXPR
3110 ? "NOP_EXPR" : e
->operation
->id
);
3113 fprintf_indent (f
, indent
,
3115 fprintf_indent (f
, indent
,
3116 " tree decl = builtin_decl_implicit (%s);\n",
3118 fprintf_indent (f
, indent
,
3119 " if (!decl) return NULL_TREE;\n");
3120 fprintf_indent (f
, indent
,
3121 " res = build_call_expr_loc "
3125 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3126 fprintf (f
, ", res_op%d", j
);
3127 fprintf (f
, ");\n");
3128 if (!is_a
<operator_id
*> (opr
))
3129 fprintf_indent (f
, indent
, "}\n");
3133 else if (result
->type
== operand::OP_CAPTURE
3134 || result
->type
== operand::OP_C_EXPR
)
3137 fprintf_indent (f
, indent
, "tree res;\n");
3138 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3145 /* Search for captures not used in the result expression and dependent
3146 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3147 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3149 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3151 if (!cinfo
.info
[i
].force_no_side_effects_p
3152 && !cinfo
.info
[i
].expr_p
3153 && cinfo
.info
[i
].result_use_count
== 0)
3155 fprintf_indent (f
, indent
,
3156 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3158 fprintf_indent (f
, indent
+ 2,
3159 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3160 "fold_ignored_result (captures[%d]), res);\n",
3164 fprintf_indent (f
, indent
, "return res;\n");
3169 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3170 step of a '(simplify ...)' or '(match ...)'. This handles everything
3171 that is not part of the decision tree (simplify->match). */
3174 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3176 fprintf_indent (f
, indent
, "{\n");
3178 output_line_directive (f
,
3179 s
->result
? s
->result
->location
: s
->match
->location
);
3180 if (s
->capture_max
>= 0)
3183 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3184 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3186 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3190 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3192 fprintf (f
, " };\n");
3195 /* If we have a split-out function for the actual transform, call it. */
3196 if (info
&& info
->fname
)
3200 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3201 "valueize, type, captures", info
->fname
);
3202 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3203 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3204 fprintf (f
, "))\n");
3205 fprintf_indent (f
, indent
, " return true;\n");
3209 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3211 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3212 fprintf (f
, ", op%d", i
);
3213 fprintf (f
, ", captures");
3214 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3215 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3216 fprintf (f
, ");\n");
3217 fprintf_indent (f
, indent
, "if (res) return res;\n");
3222 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3224 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3225 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3226 s
->for_subst_vec
[i
].first
->id
,
3227 s
->for_subst_vec
[i
].second
->id
);
3228 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3229 fprintf_indent (f
, indent
, "enum built_in_function %s = %s;\n",
3230 s
->for_subst_vec
[i
].first
->id
,
3231 s
->for_subst_vec
[i
].second
->id
);
3235 gen_1 (f
, indent
, gimple
, s
->result
);
3239 fprintf_indent (f
, indent
, "}\n");
3243 /* Hash function for finding equivalent transforms. */
3246 sinfo_hashmap_traits::hash (const key_type
&v
)
3248 /* Only bother to compare those originating from the same source pattern. */
3249 return v
->s
->result
->location
;
3252 /* Compare function for finding equivalent transforms. */
3255 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3257 if (o1
->type
!= o2
->type
)
3262 case operand::OP_IF
:
3264 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3265 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3266 /* ??? Properly compare c-exprs. */
3267 if (if1
->cond
!= if2
->cond
)
3269 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3271 if (if1
->falseexpr
!= if2
->falseexpr
3273 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3277 case operand::OP_WITH
:
3279 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3280 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3281 if (with1
->with
!= with2
->with
)
3283 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3288 /* We've hit a result. Time to compare capture-infos - this is required
3289 in addition to the conservative pointer-equivalency of the result IL. */
3290 capture_info
cinfo1 (s1
, o1
, true);
3291 capture_info
cinfo2 (s2
, o2
, true);
3293 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3294 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3297 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3299 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3300 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3301 || (cinfo1
.info
[i
].force_no_side_effects_p
3302 != cinfo2
.info
[i
].force_no_side_effects_p
)
3303 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3304 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3305 /* toplevel_msk is an optimization */
3306 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3307 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3308 /* the pointer back to the capture is for diagnostics only */)
3312 /* ??? Deep-compare the actual result. */
3317 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3318 const key_type
&candidate
)
3320 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3324 /* Main entry to generate code for matching GIMPLE IL off the decision
3328 decision_tree::gen (FILE *f
, bool gimple
)
3334 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3335 "a total number of %u nodes\n",
3336 gimple
? "GIMPLE" : "GENERIC",
3337 root
->num_leafs
, root
->max_level
, root
->total_size
);
3339 /* First split out the transform part of equal leafs. */
3342 for (sinfo_map_t::iterator iter
= si
.begin ();
3343 iter
!= si
.end (); ++iter
)
3345 sinfo
*s
= (*iter
).second
;
3346 /* Do not split out single uses. */
3353 fprintf (stderr
, "found %u uses of", s
->cnt
);
3354 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3357 /* Generate a split out function with the leaf transform code. */
3358 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3361 fprintf (f
, "\nstatic bool\n"
3362 "%s (code_helper *res_code, tree *res_ops,\n"
3363 " gimple_seq *seq, tree (*valueize)(tree) "
3364 "ATTRIBUTE_UNUSED,\n"
3365 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3370 fprintf (f
, "\nstatic tree\n"
3371 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3372 (*iter
).second
->fname
);
3373 for (unsigned i
= 0;
3374 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3375 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3376 fprintf (f
, " tree *captures\n");
3378 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3380 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3381 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3382 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3383 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3384 fprintf (f
, ", enum built_in_function ARG_UNUSED (%s)",
3385 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3388 fprintf (f
, ")\n{\n");
3389 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3391 fprintf (f
, " return false;\n");
3393 fprintf (f
, " return NULL_TREE;\n");
3396 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3398 for (unsigned n
= 1; n
<= 3; ++n
)
3400 /* First generate split-out functions. */
3401 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3403 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3404 expr
*e
= static_cast<expr
*>(dop
->op
);
3405 if (e
->ops
.length () != n
3406 /* Builtin simplifications are somewhat premature on
3407 GENERIC. The following drops patterns with outermost
3408 calls. It's easy to emit overloads for function code
3409 though if necessary. */
3411 && e
->operation
->kind
!= id_base::CODE
))
3415 fprintf (f
, "\nstatic bool\n"
3416 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3417 " gimple_seq *seq, tree (*valueize)(tree) "
3418 "ATTRIBUTE_UNUSED,\n"
3419 " code_helper ARG_UNUSED (code), tree "
3420 "ARG_UNUSED (type)\n",
3423 fprintf (f
, "\nstatic tree\n"
3424 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3425 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3427 for (unsigned i
= 0; i
< n
; ++i
)
3428 fprintf (f
, ", tree op%d", i
);
3431 dop
->gen_kids (f
, 2, gimple
);
3433 fprintf (f
, " return false;\n");
3435 fprintf (f
, " return NULL_TREE;\n");
3439 /* Then generate the main entry with the outermost switch and
3440 tail-calls to the split-out functions. */
3442 fprintf (f
, "\nstatic bool\n"
3443 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3444 " gimple_seq *seq, tree (*valueize)(tree),\n"
3445 " code_helper code, tree type");
3447 fprintf (f
, "\ntree\n"
3448 "generic_simplify (location_t loc, enum tree_code code, "
3449 "tree type ATTRIBUTE_UNUSED");
3450 for (unsigned i
= 0; i
< n
; ++i
)
3451 fprintf (f
, ", tree op%d", i
);
3456 fprintf (f
, " switch (code.get_rep())\n"
3459 fprintf (f
, " switch (code)\n"
3461 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3463 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3464 expr
*e
= static_cast<expr
*>(dop
->op
);
3465 if (e
->ops
.length () != n
3466 /* Builtin simplifications are somewhat premature on
3467 GENERIC. The following drops patterns with outermost
3468 calls. It's easy to emit overloads for function code
3469 though if necessary. */
3471 && e
->operation
->kind
!= id_base::CODE
))
3474 if (*e
->operation
== CONVERT_EXPR
3475 || *e
->operation
== NOP_EXPR
)
3476 fprintf (f
, " CASE_CONVERT:\n");
3478 fprintf (f
, " case %s%s:\n",
3479 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3482 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3483 "seq, valueize, code, type", e
->operation
->id
);
3485 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3487 for (unsigned i
= 0; i
< n
; ++i
)
3488 fprintf (f
, ", op%d", i
);
3489 fprintf (f
, ");\n");
3491 fprintf (f
, " default:;\n"
3495 fprintf (f
, " return false;\n");
3497 fprintf (f
, " return NULL_TREE;\n");
3502 /* Output code to implement the predicate P from the decision tree DT. */
3505 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3507 fprintf (f
, "\nbool\n"
3508 "%s%s (tree t%s%s)\n"
3509 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3510 p
->nargs
> 0 ? ", tree *res_ops" : "",
3511 gimple
? ", tree (*valueize)(tree)" : "");
3512 /* Conveniently make 'type' available. */
3513 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3516 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3517 dt
.root
->gen_kids (f
, 2, gimple
);
3519 fprintf_indent (f
, 2, "return false;\n"
3523 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3526 write_header (FILE *f
, const char *head
)
3528 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3529 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3531 /* Include the header instead of writing it awkwardly quoted here. */
3532 fprintf (f
, "\n#include \"%s\"\n", head
);
3542 parser (cpp_reader
*);
3545 const cpp_token
*next ();
3546 const cpp_token
*peek (unsigned = 1);
3547 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3548 const cpp_token
*expect (enum cpp_ttype
);
3549 const cpp_token
*eat_token (enum cpp_ttype
);
3550 const char *get_string ();
3551 const char *get_ident ();
3552 const cpp_token
*eat_ident (const char *);
3553 const char *get_number ();
3555 id_base
*parse_operation ();
3556 operand
*parse_capture (operand
*, bool);
3557 operand
*parse_expr ();
3558 c_expr
*parse_c_expr (cpp_ttype
);
3559 operand
*parse_op ();
3561 void record_operlist (source_location
, user_id
*);
3563 void parse_pattern ();
3564 operand
*parse_result (operand
*, predicate_id
*);
3565 void push_simplify (simplify::simplify_kind
,
3566 vec
<simplify
*>&, operand
*, operand
*);
3567 void parse_simplify (simplify::simplify_kind
,
3568 vec
<simplify
*>&, predicate_id
*, operand
*);
3569 void parse_for (source_location
);
3570 void parse_if (source_location
);
3571 void parse_predicates (source_location
);
3572 void parse_operator_list (source_location
);
3575 vec
<c_expr
*> active_ifs
;
3576 vec
<vec
<user_id
*> > active_fors
;
3577 hash_set
<user_id
*> *oper_lists_set
;
3578 vec
<user_id
*> oper_lists
;
3580 cid_map_t
*capture_ids
;
3583 vec
<simplify
*> simplifiers
;
3584 vec
<predicate_id
*> user_predicates
;
3585 bool parsing_match_operand
;
3588 /* Lexing helpers. */
3590 /* Read the next non-whitespace token from R. */
3595 const cpp_token
*token
;
3598 token
= cpp_get_token (r
);
3600 while (token
->type
== CPP_PADDING
3601 && token
->type
!= CPP_EOF
);
3605 /* Peek at the next non-whitespace token from R. */
3608 parser::peek (unsigned num
)
3610 const cpp_token
*token
;
3614 token
= cpp_peek_token (r
, i
++);
3616 while ((token
->type
== CPP_PADDING
3617 && token
->type
!= CPP_EOF
)
3619 /* If we peek at EOF this is a fatal error as it leaves the
3620 cpp_reader in unusable state. Assume we really wanted a
3621 token and thus this EOF is unexpected. */
3622 if (token
->type
== CPP_EOF
)
3623 fatal_at (token
, "unexpected end of file");
3627 /* Peek at the next identifier token (or return NULL if the next
3628 token is not an identifier or equal to ID if supplied). */
3631 parser::peek_ident (const char *id
, unsigned num
)
3633 const cpp_token
*token
= peek (num
);
3634 if (token
->type
!= CPP_NAME
)
3640 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3641 if (strcmp (id
, t
) == 0)
3647 /* Read the next token from R and assert it is of type TK. */
3650 parser::expect (enum cpp_ttype tk
)
3652 const cpp_token
*token
= next ();
3653 if (token
->type
!= tk
)
3654 fatal_at (token
, "expected %s, got %s",
3655 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3660 /* Consume the next token from R and assert it is of type TK. */
3663 parser::eat_token (enum cpp_ttype tk
)
3668 /* Read the next token from R and assert it is of type CPP_STRING and
3669 return its value. */
3672 parser::get_string ()
3674 const cpp_token
*token
= expect (CPP_STRING
);
3675 return (const char *)token
->val
.str
.text
;
3678 /* Read the next token from R and assert it is of type CPP_NAME and
3679 return its value. */
3682 parser::get_ident ()
3684 const cpp_token
*token
= expect (CPP_NAME
);
3685 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3688 /* Eat an identifier token with value S from R. */
3691 parser::eat_ident (const char *s
)
3693 const cpp_token
*token
= peek ();
3694 const char *t
= get_ident ();
3695 if (strcmp (s
, t
) != 0)
3696 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3700 /* Read the next token from R and assert it is of type CPP_NUMBER and
3701 return its value. */
3704 parser::get_number ()
3706 const cpp_token
*token
= expect (CPP_NUMBER
);
3707 return (const char *)token
->val
.str
.text
;
3711 /* Record an operator-list use for transparent for handling. */
3714 parser::record_operlist (source_location loc
, user_id
*p
)
3716 if (!oper_lists_set
->add (p
))
3718 if (!oper_lists
.is_empty ()
3719 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3720 fatal_at (loc
, "User-defined operator list does not have the "
3721 "same number of entries as others used in the pattern");
3722 oper_lists
.safe_push (p
);
3726 /* Parse the operator ID, special-casing convert?, convert1? and
3730 parser::parse_operation ()
3732 const cpp_token
*id_tok
= peek ();
3733 const char *id
= get_ident ();
3734 const cpp_token
*token
= peek ();
3735 if (strcmp (id
, "convert0") == 0)
3736 fatal_at (id_tok
, "use 'convert?' here");
3737 else if (strcmp (id
, "view_convert0") == 0)
3738 fatal_at (id_tok
, "use 'view_convert?' here");
3739 if (token
->type
== CPP_QUERY
3740 && !(token
->flags
& PREV_WHITE
))
3742 if (strcmp (id
, "convert") == 0)
3744 else if (strcmp (id
, "convert1") == 0)
3746 else if (strcmp (id
, "convert2") == 0)
3748 else if (strcmp (id
, "view_convert") == 0)
3749 id
= "view_convert0";
3750 else if (strcmp (id
, "view_convert1") == 0)
3752 else if (strcmp (id
, "view_convert2") == 0)
3755 fatal_at (id_tok
, "non-convert operator conditionalized");
3757 if (!parsing_match_operand
)
3758 fatal_at (id_tok
, "conditional convert can only be used in "
3759 "match expression");
3760 eat_token (CPP_QUERY
);
3762 else if (strcmp (id
, "convert1") == 0
3763 || strcmp (id
, "convert2") == 0
3764 || strcmp (id
, "view_convert1") == 0
3765 || strcmp (id
, "view_convert2") == 0)
3766 fatal_at (id_tok
, "expected '?' after conditional operator");
3767 id_base
*op
= get_operator (id
);
3769 fatal_at (id_tok
, "unknown operator %s", id
);
3771 user_id
*p
= dyn_cast
<user_id
*> (op
);
3772 if (p
&& p
->is_oper_list
)
3774 if (active_fors
.length() == 0)
3775 record_operlist (id_tok
->src_loc
, p
);
3777 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3783 capture = '@'<number> */
3786 parser::parse_capture (operand
*op
, bool require_existing
)
3788 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3789 const cpp_token
*token
= peek ();
3790 const char *id
= NULL
;
3791 if (token
->type
== CPP_NUMBER
)
3793 else if (token
->type
== CPP_NAME
)
3796 fatal_at (token
, "expected number or identifier");
3797 unsigned next_id
= capture_ids
->elements ();
3799 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3802 if (require_existing
)
3803 fatal_at (src_loc
, "unknown capture id");
3806 return new capture (src_loc
, num
, op
);
3809 /* Parse an expression
3810 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3813 parser::parse_expr ()
3815 const cpp_token
*token
= peek ();
3816 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3819 bool is_commutative
= false;
3820 bool force_capture
= false;
3821 const char *expr_type
= NULL
;
3823 if (token
->type
== CPP_COLON
3824 && !(token
->flags
& PREV_WHITE
))
3826 eat_token (CPP_COLON
);
3828 if (token
->type
== CPP_NAME
3829 && !(token
->flags
& PREV_WHITE
))
3831 const char *s
= get_ident ();
3832 if (!parsing_match_operand
)
3840 is_commutative
= true;
3841 else if (*sp
== 's')
3843 e
->force_single_use
= true;
3844 force_capture
= true;
3847 fatal_at (token
, "flag %c not recognized", *sp
);
3854 fatal_at (token
, "expected flag or type specifying identifier");
3857 if (token
->type
== CPP_ATSIGN
3858 && !(token
->flags
& PREV_WHITE
))
3859 op
= parse_capture (e
, false);
3860 else if (force_capture
)
3862 unsigned num
= capture_ids
->elements ();
3865 sprintf (id
, "__%u", num
);
3866 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3868 fatal_at (token
, "reserved capture id '%s' already used", id
);
3869 op
= new capture (token
->src_loc
, num
, e
);
3875 const cpp_token
*token
= peek ();
3876 if (token
->type
== CPP_CLOSE_PAREN
)
3878 if (e
->operation
->nargs
!= -1
3879 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3880 fatal_at (token
, "'%s' expects %u operands, not %u",
3881 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3884 if (e
->ops
.length () == 2)
3885 e
->is_commutative
= true;
3887 fatal_at (token
, "only binary operators or function with "
3888 "two arguments can be marked commutative");
3890 e
->expr_type
= expr_type
;
3893 else if (!(token
->flags
& PREV_WHITE
))
3894 fatal_at (token
, "expected expression operand");
3896 e
->append_op (parse_op ());
3901 /* Lex native C code delimited by START recording the preprocessing tokens
3902 for later processing.
3903 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3906 parser::parse_c_expr (cpp_ttype start
)
3908 const cpp_token
*token
;
3911 vec
<cpp_token
> code
= vNULL
;
3912 unsigned nr_stmts
= 0;
3913 source_location loc
= eat_token (start
)->src_loc
;
3914 if (start
== CPP_OPEN_PAREN
)
3915 end
= CPP_CLOSE_PAREN
;
3916 else if (start
== CPP_OPEN_BRACE
)
3917 end
= CPP_CLOSE_BRACE
;
3925 /* Count brace pairs to find the end of the expr to match. */
3926 if (token
->type
== start
)
3928 else if (token
->type
== end
3932 /* This is a lame way of counting the number of statements. */
3933 if (token
->type
== CPP_SEMICOLON
)
3936 /* If this is possibly a user-defined identifier mark it used. */
3937 if (token
->type
== CPP_NAME
)
3939 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3940 (token
->val
.node
.node
)->ident
.str
);
3942 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3943 record_operlist (token
->src_loc
, p
);
3946 /* Record the token. */
3947 code
.safe_push (*token
);
3950 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3953 /* Parse an operand which is either an expression, a predicate or
3954 a standalone capture.
3955 op = predicate | expr | c_expr | capture */
3960 const cpp_token
*token
= peek ();
3961 struct operand
*op
= NULL
;
3962 if (token
->type
== CPP_OPEN_PAREN
)
3964 eat_token (CPP_OPEN_PAREN
);
3966 eat_token (CPP_CLOSE_PAREN
);
3968 else if (token
->type
== CPP_OPEN_BRACE
)
3970 op
= parse_c_expr (CPP_OPEN_BRACE
);
3974 /* Remaining ops are either empty or predicates */
3975 if (token
->type
== CPP_NAME
)
3977 const char *id
= get_ident ();
3978 id_base
*opr
= get_operator (id
);
3980 fatal_at (token
, "expected predicate name");
3981 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3983 if (code
->nargs
!= 0)
3984 fatal_at (token
, "using an operator with operands as predicate");
3985 /* Parse the zero-operand operator "predicates" as
3987 op
= new expr (opr
, token
->src_loc
);
3989 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3991 if (code
->nargs
!= 0)
3992 fatal_at (token
, "using an operator with operands as predicate");
3993 /* Parse the zero-operand operator "predicates" as
3995 op
= new expr (opr
, token
->src_loc
);
3997 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3998 op
= new predicate (p
, token
->src_loc
);
4000 fatal_at (token
, "using an unsupported operator as predicate");
4001 if (!parsing_match_operand
)
4002 fatal_at (token
, "predicates are only allowed in match expression");
4004 if (token
->flags
& PREV_WHITE
)
4007 else if (token
->type
!= CPP_COLON
4008 && token
->type
!= CPP_ATSIGN
)
4009 fatal_at (token
, "expected expression or predicate");
4010 /* optionally followed by a capture and a predicate. */
4011 if (token
->type
== CPP_COLON
)
4012 fatal_at (token
, "not implemented: predicate on leaf operand");
4013 if (token
->type
== CPP_ATSIGN
)
4014 op
= parse_capture (op
, !parsing_match_operand
);
4020 /* Create a new simplify from the current parsing state and MATCH,
4021 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4024 parser::push_simplify (simplify::simplify_kind kind
,
4025 vec
<simplify
*>& simplifiers
,
4026 operand
*match
, operand
*result
)
4028 /* Build and push a temporary for operator list uses in expressions. */
4029 if (!oper_lists
.is_empty ())
4030 active_fors
.safe_push (oper_lists
);
4032 simplifiers
.safe_push
4033 (new simplify (kind
, match
, result
,
4034 active_fors
.copy (), capture_ids
));
4036 if (!oper_lists
.is_empty ())
4041 <result-op> = <op> | <if> | <with>
4042 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4043 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4047 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4049 const cpp_token
*token
= peek ();
4050 if (token
->type
!= CPP_OPEN_PAREN
)
4053 eat_token (CPP_OPEN_PAREN
);
4054 if (peek_ident ("if"))
4057 if_expr
*ife
= new if_expr (token
->src_loc
);
4058 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4059 if (peek ()->type
== CPP_OPEN_PAREN
)
4061 ife
->trueexpr
= parse_result (result
, matcher
);
4062 if (peek ()->type
== CPP_OPEN_PAREN
)
4063 ife
->falseexpr
= parse_result (result
, matcher
);
4064 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4065 ife
->falseexpr
= parse_op ();
4067 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4069 ife
->trueexpr
= parse_op ();
4070 if (peek ()->type
== CPP_OPEN_PAREN
)
4071 ife
->falseexpr
= parse_result (result
, matcher
);
4072 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4073 ife
->falseexpr
= parse_op ();
4075 /* If this if is immediately closed then it contains a
4076 manual matcher or is part of a predicate definition. */
4077 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4080 fatal_at (peek (), "manual transform not implemented");
4081 ife
->trueexpr
= result
;
4083 eat_token (CPP_CLOSE_PAREN
);
4086 else if (peek_ident ("with"))
4089 with_expr
*withe
= new with_expr (token
->src_loc
);
4090 /* Parse (with c-expr expr) as (if-with (true) expr). */
4091 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4092 withe
->with
->nr_stmts
= 0;
4093 withe
->subexpr
= parse_result (result
, matcher
);
4094 eat_token (CPP_CLOSE_PAREN
);
4097 else if (peek_ident ("switch"))
4099 token
= eat_ident ("switch");
4100 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4102 if_expr
*ife
= new if_expr (ifloc
);
4104 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4105 if (peek ()->type
== CPP_OPEN_PAREN
)
4106 ife
->trueexpr
= parse_result (result
, matcher
);
4108 ife
->trueexpr
= parse_op ();
4109 eat_token (CPP_CLOSE_PAREN
);
4110 if (peek ()->type
!= CPP_OPEN_PAREN
4111 || !peek_ident ("if", 2))
4112 fatal_at (token
, "switch can be implemented with a single if");
4113 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4115 if (peek ()->type
== CPP_OPEN_PAREN
)
4117 if (peek_ident ("if", 2))
4119 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4121 ife
->falseexpr
= new if_expr (ifloc
);
4122 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4123 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4124 if (peek ()->type
== CPP_OPEN_PAREN
)
4125 ife
->trueexpr
= parse_result (result
, matcher
);
4127 ife
->trueexpr
= parse_op ();
4128 eat_token (CPP_CLOSE_PAREN
);
4132 /* switch default clause */
4133 ife
->falseexpr
= parse_result (result
, matcher
);
4134 eat_token (CPP_CLOSE_PAREN
);
4140 /* switch default clause */
4141 ife
->falseexpr
= parse_op ();
4142 eat_token (CPP_CLOSE_PAREN
);
4146 eat_token (CPP_CLOSE_PAREN
);
4151 operand
*op
= result
;
4154 eat_token (CPP_CLOSE_PAREN
);
4160 simplify = 'simplify' <expr> <result-op>
4162 match = 'match' <ident> <expr> [<result-op>]
4163 and fill SIMPLIFIERS with the results. */
4166 parser::parse_simplify (simplify::simplify_kind kind
,
4167 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4170 /* Reset the capture map. */
4172 capture_ids
= new cid_map_t
;
4173 /* Reset oper_lists and set. */
4174 hash_set
<user_id
*> olist
;
4175 oper_lists_set
= &olist
;
4178 const cpp_token
*loc
= peek ();
4179 parsing_match_operand
= true;
4180 struct operand
*match
= parse_op ();
4181 parsing_match_operand
= false;
4182 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4183 fatal_at (loc
, "outermost expression cannot be captured");
4184 if (match
->type
== operand::OP_EXPR
4185 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4186 fatal_at (loc
, "outermost expression cannot be a predicate");
4188 /* Splice active_ifs onto result and continue parsing the
4190 if_expr
*active_if
= NULL
;
4191 for (int i
= active_ifs
.length (); i
> 0; --i
)
4193 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4194 ifc
->cond
= active_ifs
[i
-1];
4195 ifc
->trueexpr
= active_if
;
4198 if_expr
*outermost_if
= active_if
;
4199 while (active_if
&& active_if
->trueexpr
)
4200 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4202 const cpp_token
*token
= peek ();
4204 /* If this if is immediately closed then it is part of a predicate
4205 definition. Push it. */
4206 if (token
->type
== CPP_CLOSE_PAREN
)
4209 fatal_at (token
, "expected transform expression");
4212 active_if
->trueexpr
= result
;
4213 result
= outermost_if
;
4215 push_simplify (kind
, simplifiers
, match
, result
);
4219 operand
*tem
= parse_result (result
, matcher
);
4222 active_if
->trueexpr
= tem
;
4223 result
= outermost_if
;
4228 push_simplify (kind
, simplifiers
, match
, result
);
4231 /* Parsing of the outer control structures. */
4233 /* Parse a for expression
4234 for = '(' 'for' <subst>... <pattern> ')'
4235 subst = <ident> '(' <ident>... ')' */
4238 parser::parse_for (source_location
)
4240 auto_vec
<const cpp_token
*> user_id_tokens
;
4241 vec
<user_id
*> user_ids
= vNULL
;
4242 const cpp_token
*token
;
4243 unsigned min_n_opers
= 0, max_n_opers
= 0;
4248 if (token
->type
!= CPP_NAME
)
4251 /* Insert the user defined operators into the operator hash. */
4252 const char *id
= get_ident ();
4253 if (get_operator (id
) != NULL
)
4254 fatal_at (token
, "operator already defined");
4255 user_id
*op
= new user_id (id
);
4256 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4258 user_ids
.safe_push (op
);
4259 user_id_tokens
.safe_push (token
);
4261 eat_token (CPP_OPEN_PAREN
);
4264 while ((token
= peek_ident ()) != 0)
4266 const char *oper
= get_ident ();
4267 id_base
*idb
= get_operator (oper
);
4269 fatal_at (token
, "no such operator '%s'", oper
);
4270 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4271 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4272 || *idb
== VIEW_CONVERT2
)
4273 fatal_at (token
, "conditional operators cannot be used inside for");
4277 else if (idb
->nargs
== -1)
4279 else if (idb
->nargs
!= arity
)
4280 fatal_at (token
, "operator '%s' with arity %d does not match "
4281 "others with arity %d", oper
, idb
->nargs
, arity
);
4283 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4286 if (p
->is_oper_list
)
4287 op
->substitutes
.safe_splice (p
->substitutes
);
4289 fatal_at (token
, "iterator cannot be used as operator-list");
4292 op
->substitutes
.safe_push (idb
);
4295 token
= expect (CPP_CLOSE_PAREN
);
4297 unsigned nsubstitutes
= op
->substitutes
.length ();
4298 if (nsubstitutes
== 0)
4299 fatal_at (token
, "A user-defined operator must have at least "
4300 "one substitution");
4301 if (max_n_opers
== 0)
4303 min_n_opers
= nsubstitutes
;
4304 max_n_opers
= nsubstitutes
;
4308 if (nsubstitutes
% min_n_opers
!= 0
4309 && min_n_opers
% nsubstitutes
!= 0)
4310 fatal_at (token
, "All user-defined identifiers must have a "
4311 "multiple number of operator substitutions of the "
4312 "smallest number of substitutions");
4313 if (nsubstitutes
< min_n_opers
)
4314 min_n_opers
= nsubstitutes
;
4315 else if (nsubstitutes
> max_n_opers
)
4316 max_n_opers
= nsubstitutes
;
4320 unsigned n_ids
= user_ids
.length ();
4322 fatal_at (token
, "for requires at least one user-defined identifier");
4325 if (token
->type
== CPP_CLOSE_PAREN
)
4326 fatal_at (token
, "no pattern defined in for");
4328 active_fors
.safe_push (user_ids
);
4332 if (token
->type
== CPP_CLOSE_PAREN
)
4338 /* Remove user-defined operators from the hash again. */
4339 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4341 if (!user_ids
[i
]->used
)
4342 warning_at (user_id_tokens
[i
],
4343 "operator %s defined but not used", user_ids
[i
]->id
);
4344 operators
->remove_elt (user_ids
[i
]);
4348 /* Parse an identifier associated with a list of operators.
4349 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4352 parser::parse_operator_list (source_location
)
4354 const cpp_token
*token
= peek ();
4355 const char *id
= get_ident ();
4357 if (get_operator (id
) != 0)
4358 fatal_at (token
, "operator %s already defined", id
);
4360 user_id
*op
= new user_id (id
, true);
4363 while ((token
= peek_ident ()) != 0)
4366 const char *oper
= get_ident ();
4367 id_base
*idb
= get_operator (oper
);
4370 fatal_at (token
, "no such operator '%s'", oper
);
4374 else if (idb
->nargs
== -1)
4376 else if (arity
!= idb
->nargs
)
4377 fatal_at (token
, "operator '%s' with arity %d does not match "
4378 "others with arity %d", oper
, idb
->nargs
, arity
);
4380 /* We allow composition of multiple operator lists. */
4381 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4382 op
->substitutes
.safe_splice (p
->substitutes
);
4384 op
->substitutes
.safe_push (idb
);
4387 // Check that there is no junk after id-list
4389 if (token
->type
!= CPP_CLOSE_PAREN
)
4390 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4392 if (op
->substitutes
.length () == 0)
4393 fatal_at (token
, "operator-list cannot be empty");
4396 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4400 /* Parse an outer if expression.
4401 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4404 parser::parse_if (source_location
)
4406 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4408 const cpp_token
*token
= peek ();
4409 if (token
->type
== CPP_CLOSE_PAREN
)
4410 fatal_at (token
, "no pattern defined in if");
4412 active_ifs
.safe_push (ifexpr
);
4415 const cpp_token
*token
= peek ();
4416 if (token
->type
== CPP_CLOSE_PAREN
)
4424 /* Parse a list of predefined predicate identifiers.
4425 preds = '(' 'define_predicates' <ident>... ')' */
4428 parser::parse_predicates (source_location
)
4432 const cpp_token
*token
= peek ();
4433 if (token
->type
!= CPP_NAME
)
4436 add_predicate (get_ident ());
4441 /* Parse outer control structures.
4442 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4445 parser::parse_pattern ()
4447 /* All clauses start with '('. */
4448 eat_token (CPP_OPEN_PAREN
);
4449 const cpp_token
*token
= peek ();
4450 const char *id
= get_ident ();
4451 if (strcmp (id
, "simplify") == 0)
4453 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4456 else if (strcmp (id
, "match") == 0)
4458 bool with_args
= false;
4459 source_location e_loc
= peek ()->src_loc
;
4460 if (peek ()->type
== CPP_OPEN_PAREN
)
4462 eat_token (CPP_OPEN_PAREN
);
4465 const char *name
= get_ident ();
4466 id_base
*id
= get_operator (name
);
4470 p
= add_predicate (name
);
4471 user_predicates
.safe_push (p
);
4473 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4476 fatal_at (token
, "cannot add a match to a non-predicate ID");
4477 /* Parse (match <id> <arg>... (match-expr)) here. */
4481 capture_ids
= new cid_map_t
;
4482 e
= new expr (p
, e_loc
);
4483 while (peek ()->type
== CPP_ATSIGN
)
4484 e
->append_op (parse_capture (NULL
, false));
4485 eat_token (CPP_CLOSE_PAREN
);
4488 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4489 || (!e
&& p
->nargs
!= 0)))
4490 fatal_at (token
, "non-matching number of match operands");
4491 p
->nargs
= e
? e
->ops
.length () : 0;
4492 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4495 else if (strcmp (id
, "for") == 0)
4496 parse_for (token
->src_loc
);
4497 else if (strcmp (id
, "if") == 0)
4498 parse_if (token
->src_loc
);
4499 else if (strcmp (id
, "define_predicates") == 0)
4501 if (active_ifs
.length () > 0
4502 || active_fors
.length () > 0)
4503 fatal_at (token
, "define_predicates inside if or for is not supported");
4504 parse_predicates (token
->src_loc
);
4506 else if (strcmp (id
, "define_operator_list") == 0)
4508 if (active_ifs
.length () > 0
4509 || active_fors
.length () > 0)
4510 fatal_at (token
, "operator-list inside if or for is not supported");
4511 parse_operator_list (token
->src_loc
);
4514 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4515 active_ifs
.length () == 0 && active_fors
.length () == 0
4516 ? "'define_predicates', " : "");
4518 eat_token (CPP_CLOSE_PAREN
);
4521 /* Main entry of the parser. Repeatedly parse outer control structures. */
4523 parser::parser (cpp_reader
*r_
)
4527 active_fors
= vNULL
;
4528 simplifiers
= vNULL
;
4529 oper_lists_set
= NULL
;
4532 user_predicates
= vNULL
;
4533 parsing_match_operand
= false;
4535 const cpp_token
*token
= next ();
4536 while (token
->type
!= CPP_EOF
)
4538 _cpp_backup_tokens (r
, 1);
4545 /* Helper for the linemap code. */
4548 round_alloc_size (size_t s
)
4554 /* The genmatch generator progam. It reads from a pattern description
4555 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4558 main (int argc
, char **argv
)
4562 progname
= "genmatch";
4568 char *input
= argv
[argc
-1];
4569 for (int i
= 1; i
< argc
- 1; ++i
)
4571 if (strcmp (argv
[i
], "--gimple") == 0)
4573 else if (strcmp (argv
[i
], "--generic") == 0)
4575 else if (strcmp (argv
[i
], "-v") == 0)
4577 else if (strcmp (argv
[i
], "-vv") == 0)
4581 fprintf (stderr
, "Usage: genmatch "
4582 "[--gimple] [--generic] [-v[v]] input\n");
4587 line_table
= XCNEW (struct line_maps
);
4588 linemap_init (line_table
, 0);
4589 line_table
->reallocator
= xrealloc
;
4590 line_table
->round_alloc_size
= round_alloc_size
;
4592 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4593 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4594 cb
->error
= error_cb
;
4596 if (!cpp_read_main_file (r
, input
))
4598 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4599 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4601 /* Pre-seed operators. */
4602 operators
= new hash_table
<id_base
> (1024);
4603 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4604 add_operator (SYM, # SYM, # TYPE, NARGS);
4605 #define END_OF_BASE_TREE_CODES
4607 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4608 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4609 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4610 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4611 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4612 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4613 #undef END_OF_BASE_TREE_CODES
4616 /* Pre-seed builtin functions.
4617 ??? Cannot use N (name) as that is targetm.emultls.get_address
4618 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4619 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4620 add_builtin (ENUM, # ENUM);
4621 #include "builtins.def"
4628 write_header (stdout
, "gimple-match-head.c");
4630 write_header (stdout
, "generic-match-head.c");
4632 /* Go over all predicates defined with patterns and perform
4633 lowering and code generation. */
4634 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4636 predicate_id
*pred
= p
.user_predicates
[i
];
4637 lower (pred
->matchers
, gimple
);
4640 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4641 print_matches (pred
->matchers
[i
]);
4644 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4645 dt
.insert (pred
->matchers
[i
], i
);
4650 write_predicate (stdout
, pred
, dt
, gimple
);
4653 /* Lower the main simplifiers and generate code for them. */
4654 lower (p
.simplifiers
, gimple
);
4657 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4658 print_matches (p
.simplifiers
[i
]);
4661 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4662 dt
.insert (p
.simplifiers
[i
], i
);
4667 dt
.gen (stdout
, gimple
);
4670 cpp_finish (r
, NULL
);