1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014 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"
32 #include "hash-table.h"
38 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
39 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
40 size_t, size_t MEM_STAT_DECL
)
44 void ggc_free (void *)
51 static struct line_maps
*line_table
;
54 #if GCC_VERSION >= 4001
55 __attribute__((format (printf
, 6, 0)))
57 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
58 unsigned int, const char *msg
, va_list *ap
)
61 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
62 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
63 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
64 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
65 vfprintf (stderr
, msg
, *ap
);
66 fprintf (stderr
, "\n");
67 FILE *f
= fopen (loc
.file
, "r");
73 if (!fgets (buf
, 128, f
))
75 if (buf
[strlen (buf
) - 1] != '\n')
82 fprintf (stderr
, "%s", buf
);
83 for (int i
= 0; i
< loc
.column
- 1; ++i
)
91 if (errtype
== CPP_DL_FATAL
)
97 #if GCC_VERSION >= 4001
98 __attribute__((format (printf
, 2, 3)))
100 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
104 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
109 #if GCC_VERSION >= 4001
110 __attribute__((format (printf
, 2, 3)))
112 warning_at (const cpp_token
*tk
, const char *msg
, ...)
116 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
121 output_line_directive (FILE *f
, source_location location
,
122 bool dumpfile
= false)
125 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
126 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
129 /* When writing to a dumpfile only dump the filename. */
130 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
135 fprintf (f
, "%s:%d", file
, loc
.line
);
138 /* Other gen programs really output line directives here, at least for
139 development it's right now more convenient to have line information
140 from the generated file. Still keep the directives as comment for now
141 to easily back-point to the meta-description. */
142 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
146 /* Pull in tree codes and builtin function codes from their
149 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
159 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
160 enum built_in_function
{
161 #include "builtins.def"
167 /* Base class for all identifiers the parser knows. */
169 struct id_base
: typed_noop_remove
<id_base
>
171 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
173 id_base (id_kind
, const char *, int = -1);
179 /* hash_table support. */
180 typedef id_base value_type
;
181 typedef id_base compare_type
;
182 static inline hashval_t
hash (const value_type
*);
183 static inline int equal (const value_type
*, const compare_type
*);
187 id_base::hash (const value_type
*op
)
193 id_base::equal (const value_type
*op1
,
194 const compare_type
*op2
)
196 return (op1
->hashval
== op2
->hashval
197 && strcmp (op1
->id
, op2
->id
) == 0);
200 /* Hashtable of known pattern operators. This is pre-seeded from
201 all known tree codes and all known builtin function ids. */
202 static hash_table
<id_base
> *operators
;
204 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
209 hashval
= htab_hash_string (id
);
212 /* Identifier that maps to a tree code. */
214 struct operator_id
: public id_base
216 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
218 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
223 /* Identifier that maps to a builtin function code. */
225 struct fn_id
: public id_base
227 fn_id (enum built_in_function fn_
, const char *id_
)
228 : id_base (id_base::FN
, id_
), fn (fn_
) {}
229 enum built_in_function fn
;
234 /* Identifier that maps to a user-defined predicate. */
236 struct predicate_id
: public id_base
238 predicate_id (const char *id_
)
239 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
240 vec
<simplify
*> matchers
;
243 /* Identifier that maps to a operator defined by a 'for' directive. */
245 struct user_id
: public id_base
247 user_id (const char *id_
, bool is_oper_list_
= false)
248 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
249 used (false), is_oper_list (is_oper_list_
) {}
250 vec
<id_base
*> substitutes
;
258 is_a_helper
<fn_id
*>::test (id_base
*id
)
260 return id
->kind
== id_base::FN
;
266 is_a_helper
<operator_id
*>::test (id_base
*id
)
268 return id
->kind
== id_base::CODE
;
274 is_a_helper
<predicate_id
*>::test (id_base
*id
)
276 return id
->kind
== id_base::PREDICATE
;
282 is_a_helper
<user_id
*>::test (id_base
*id
)
284 return id
->kind
== id_base::USER
;
287 /* Add a predicate identifier to the hash. */
289 static predicate_id
*
290 add_predicate (const char *id
)
292 predicate_id
*p
= new predicate_id (id
);
293 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
295 fatal ("duplicate id definition");
300 /* Add a tree code identifier to the hash. */
303 add_operator (enum tree_code code
, const char *id
,
304 const char *tcc
, unsigned nargs
)
306 if (strcmp (tcc
, "tcc_unary") != 0
307 && strcmp (tcc
, "tcc_binary") != 0
308 && strcmp (tcc
, "tcc_comparison") != 0
309 && strcmp (tcc
, "tcc_expression") != 0
310 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
311 && strcmp (tcc
, "tcc_reference") != 0
312 /* To have INTEGER_CST and friends as "predicate operators". */
313 && strcmp (tcc
, "tcc_constant") != 0)
315 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
316 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
318 fatal ("duplicate id definition");
322 /* Add a builtin identifier to the hash. */
325 add_builtin (enum built_in_function code
, const char *id
)
327 fn_id
*fn
= new fn_id (code
, id
);
328 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
330 fatal ("duplicate id definition");
334 /* Helper for easy comparing ID with tree code CODE. */
337 operator==(id_base
&id
, enum tree_code code
)
339 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
340 return oid
->code
== code
;
344 /* Lookup the identifier ID. */
347 get_operator (const char *id
)
349 id_base
tem (id_base::CODE
, id
);
351 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
354 /* If this is a user-defined identifier track whether it was used. */
355 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
360 /* Try all-uppercase. */
361 char *id2
= xstrdup (id
);
362 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
363 id2
[i
] = TOUPPER (id2
[i
]);
364 new (&tem
) id_base (id_base::CODE
, id2
);
365 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
372 /* Try _EXPR appended. */
373 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
374 strcat (id2
, "_EXPR");
375 new (&tem
) id_base (id_base::CODE
, id2
);
376 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
387 /* Helper for the capture-id map. */
389 struct capture_id_map_hasher
: default_hashmap_traits
391 static inline hashval_t
hash (const char *);
392 static inline bool equal_keys (const char *, const char *);
396 capture_id_map_hasher::hash (const char *id
)
398 return htab_hash_string (id
);
402 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
404 return strcmp (id1
, id2
) == 0;
407 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
410 /* The AST produced by parsing of the pattern definitions. */
415 /* The base class for operands. */
418 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
419 operand (enum op_type type_
) : type (type_
) {}
421 virtual void gen_transform (FILE *, const char *, bool, int,
422 const char *, capture_info
*,
425 { gcc_unreachable (); }
428 /* A predicate operand. Predicates are leafs in the AST. */
430 struct predicate
: public operand
432 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
436 /* An operand that constitutes an expression. Expressions include
437 function calls and user-defined predicate invocations. */
439 struct expr
: public operand
441 expr (id_base
*operation_
, bool is_commutative_
= false)
442 : operand (OP_EXPR
), operation (operation_
),
443 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
444 is_generic (false) {}
445 void append_op (operand
*op
) { ops
.safe_push (op
); }
446 /* The operator and its operands. */
449 /* An explicitely specified type - used exclusively for conversions. */
450 const char *expr_type
;
451 /* Whether the operation is to be applied commutatively. This is
452 later lowered to two separate patterns. */
454 /* Whether the expression is expected to be in GENERIC form. */
456 virtual void gen_transform (FILE *f
, const char *, bool, int,
457 const char *, capture_info
*,
458 dt_operand
** = 0, bool = true);
461 /* An operator that is represented by native C code. This is always
462 a leaf operand in the AST. This class is also used to represent
463 the code to be generated for 'if' and 'with' expressions. */
465 struct c_expr
: public operand
467 /* A mapping of an identifier and its replacement. Used to apply
472 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
475 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
476 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
477 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
478 nr_stmts (nr_stmts_
), ids (ids_
) {}
479 /* cpplib tokens and state to transform this back to source. */
482 cid_map_t
*capture_ids
;
483 /* The number of statements parsed (well, the number of ';'s). */
485 /* The identifier replacement vector. */
487 virtual void gen_transform (FILE *f
, const char *, bool, int,
488 const char *, capture_info
*,
489 dt_operand
** = 0, bool = true);
492 /* A wrapper around another operand that captures its value. */
494 struct capture
: public operand
496 capture (unsigned where_
, operand
*what_
)
497 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
498 /* Identifier index for the value. */
500 /* The captured value. */
502 virtual void gen_transform (FILE *f
, const char *, bool, int,
503 const char *, capture_info
*,
504 dt_operand
** = 0, bool = true);
510 is_a_helper
<capture
*>::test (operand
*op
)
512 return op
->type
== operand::OP_CAPTURE
;
518 is_a_helper
<predicate
*>::test (operand
*op
)
520 return op
->type
== operand::OP_PREDICATE
;
526 is_a_helper
<c_expr
*>::test (operand
*op
)
528 return op
->type
== operand::OP_C_EXPR
;
534 is_a_helper
<expr
*>::test (operand
*op
)
536 return op
->type
== operand::OP_EXPR
;
539 /* Helper to distinguish 'if' from 'with' expressions. */
543 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
544 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
545 source_location location
;
550 /* The main class of a pattern and its transform. This is used to
551 represent both (simplify ...) and (match ...) kinds. The AST
552 duplicates all outer 'if' and 'for' expressions here so each
553 simplify can exist in isolation. */
557 simplify (operand
*match_
, source_location match_location_
,
558 struct operand
*result_
, source_location result_location_
,
559 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
560 cid_map_t
*capture_ids_
)
561 : match (match_
), match_location (match_location_
),
562 result (result_
), result_location (result_location_
),
563 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
564 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
566 /* The expression that is matched against the GENERIC or GIMPLE IL. */
568 source_location match_location
;
569 /* For a (simplify ...) the expression produced when the pattern applies.
570 For a (match ...) either NULL if it is a simple predicate or the
571 single expression specifying the matched operands. */
572 struct operand
*result
;
573 source_location result_location
;
574 /* Collected 'if' expressions that need to evaluate to true to make
575 the pattern apply. */
576 vec
<if_or_with
> ifexpr_vec
;
577 /* Collected 'for' expression operators that have to be replaced
578 in the lowering phase. */
579 vec
<vec
<user_id
*> > for_vec
;
580 /* A map of capture identifiers to indexes. */
581 cid_map_t
*capture_ids
;
585 /* Debugging routines for dumping the AST. */
588 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
590 if (capture
*c
= dyn_cast
<capture
*> (o
))
592 fprintf (f
, "@%u", c
->where
);
593 if (c
->what
&& flattened
== false)
596 print_operand (c
->what
, f
, flattened
);
601 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
602 fprintf (f
, "%s", p
->p
->id
);
604 else if (is_a
<c_expr
*> (o
))
605 fprintf (f
, "c_expr");
607 else if (expr
*e
= dyn_cast
<expr
*> (o
))
609 fprintf (f
, "(%s", e
->operation
->id
);
611 if (flattened
== false)
614 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
616 print_operand (e
->ops
[i
], f
, flattened
);
628 print_matches (struct simplify
*s
, FILE *f
= stderr
)
630 fprintf (f
, "for expression: ");
631 print_operand (s
->match
, f
);
638 /* Lowering of commutative operators. */
641 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
642 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
644 if (n
== ops_vector
.length ())
646 vec
<operand
*> xv
= v
.copy ();
647 result
.safe_push (xv
);
651 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
653 v
[n
] = ops_vector
[n
][i
];
654 cartesian_product (ops_vector
, result
, v
, n
+ 1);
658 /* Lower OP to two operands in case it is marked as commutative. */
660 static vec
<operand
*>
661 commutate (operand
*op
)
663 vec
<operand
*> ret
= vNULL
;
665 if (capture
*c
= dyn_cast
<capture
*> (op
))
672 vec
<operand
*> v
= commutate (c
->what
);
673 for (unsigned i
= 0; i
< v
.length (); ++i
)
675 capture
*nc
= new capture (c
->where
, v
[i
]);
681 expr
*e
= dyn_cast
<expr
*> (op
);
682 if (!e
|| e
->ops
.length () == 0)
688 vec
< vec
<operand
*> > ops_vector
= vNULL
;
689 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
690 ops_vector
.safe_push (commutate (e
->ops
[i
]));
692 auto_vec
< vec
<operand
*> > result
;
693 auto_vec
<operand
*> v (e
->ops
.length ());
694 v
.quick_grow_cleared (e
->ops
.length ());
695 cartesian_product (ops_vector
, result
, v
, 0);
698 for (unsigned i
= 0; i
< result
.length (); ++i
)
700 expr
*ne
= new expr (e
->operation
);
701 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
702 ne
->append_op (result
[i
][j
]);
706 if (!e
->is_commutative
)
709 for (unsigned i
= 0; i
< result
.length (); ++i
)
711 expr
*ne
= new expr (e
->operation
);
712 // result[i].length () is 2 since e->operation is binary
713 for (unsigned j
= result
[i
].length (); j
; --j
)
714 ne
->append_op (result
[i
][j
-1]);
721 /* Lower operations marked as commutative in the AST of S and push
722 the resulting patterns to SIMPLIFIERS. */
725 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
727 vec
<operand
*> matchers
= commutate (s
->match
);
728 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
730 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
731 s
->result
, s
->result_location
, s
->ifexpr_vec
,
732 s
->for_vec
, s
->capture_ids
);
733 simplifiers
.safe_push (ns
);
737 /* Strip conditional conversios using operator OPER from O and its
738 children if STRIP, else replace them with an unconditional convert. */
741 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
743 if (capture
*c
= dyn_cast
<capture
*> (o
))
746 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
751 expr
*e
= dyn_cast
<expr
*> (o
);
755 if (*e
->operation
== oper
)
758 return lower_opt_convert (e
->ops
[0], oper
, strip
);
760 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
761 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
765 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
766 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
767 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
772 /* Determine whether O or its children uses the conditional conversion
776 has_opt_convert (operand
*o
, enum tree_code oper
)
778 if (capture
*c
= dyn_cast
<capture
*> (o
))
781 return has_opt_convert (c
->what
, oper
);
786 expr
*e
= dyn_cast
<expr
*> (o
);
790 if (*e
->operation
== oper
)
793 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
794 if (has_opt_convert (e
->ops
[i
], oper
))
800 /* Lower conditional convert operators in O, expanding it to a vector
803 static vec
<operand
*>
804 lower_opt_convert (operand
*o
)
806 vec
<operand
*> v1
= vNULL
, v2
;
810 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
812 /* Conditional converts are lowered to a pattern with the
813 conversion and one without. The three different conditional
814 convert codes are lowered separately. */
816 for (unsigned i
= 0; i
< 3; ++i
)
819 for (unsigned j
= 0; j
< v1
.length (); ++j
)
820 if (has_opt_convert (v1
[j
], opers
[i
]))
822 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
823 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
829 for (unsigned j
= 0; j
< v2
.length (); ++j
)
830 v1
.safe_push (v2
[j
]);
837 /* Lower conditional convert operators in the AST of S and push
838 the resulting multiple patterns to SIMPLIFIERS. */
841 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
843 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
844 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
846 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
847 s
->result
, s
->result_location
, s
->ifexpr_vec
,
848 s
->for_vec
, s
->capture_ids
);
849 simplifiers
.safe_push (ns
);
853 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
854 GENERIC and a GIMPLE variant. */
856 static vec
<operand
*>
857 lower_cond (operand
*o
)
859 vec
<operand
*> ro
= vNULL
;
861 if (capture
*c
= dyn_cast
<capture
*> (o
))
865 vec
<operand
*> lop
= vNULL
;
866 lop
= lower_cond (c
->what
);
868 for (unsigned i
= 0; i
< lop
.length (); ++i
)
869 ro
.safe_push (new capture (c
->where
, lop
[i
]));
874 expr
*e
= dyn_cast
<expr
*> (o
);
875 if (!e
|| e
->ops
.length () == 0)
881 vec
< vec
<operand
*> > ops_vector
= vNULL
;
882 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
883 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
885 auto_vec
< vec
<operand
*> > result
;
886 auto_vec
<operand
*> v (e
->ops
.length ());
887 v
.quick_grow_cleared (e
->ops
.length ());
888 cartesian_product (ops_vector
, result
, v
, 0);
890 for (unsigned i
= 0; i
< result
.length (); ++i
)
892 expr
*ne
= new expr (e
->operation
);
893 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
894 ne
->append_op (result
[i
][j
]);
896 /* If this is a COND with a captured expression or an
897 expression with two operands then also match a GENERIC
898 form on the compare. */
899 if ((*e
->operation
== COND_EXPR
900 || *e
->operation
== VEC_COND_EXPR
)
901 && ((is_a
<capture
*> (e
->ops
[0])
902 && as_a
<capture
*> (e
->ops
[0])->what
903 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
905 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
906 || (is_a
<expr
*> (e
->ops
[0])
907 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
909 expr
*ne
= new expr (e
->operation
);
910 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
911 ne
->append_op (result
[i
][j
]);
912 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
914 expr
*ocmp
= as_a
<expr
*> (c
->what
);
915 expr
*cmp
= new expr (ocmp
->operation
);
916 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
917 cmp
->append_op (ocmp
->ops
[j
]);
918 cmp
->is_generic
= true;
919 ne
->ops
[0] = new capture (c
->where
, cmp
);
923 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
924 expr
*cmp
= new expr (ocmp
->operation
);
925 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
926 cmp
->append_op (ocmp
->ops
[j
]);
927 cmp
->is_generic
= true;
937 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
938 GENERIC and a GIMPLE variant. */
941 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
943 vec
<operand
*> matchers
= lower_cond (s
->match
);
944 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
946 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
947 s
->result
, s
->result_location
, s
->ifexpr_vec
,
948 s
->for_vec
, s
->capture_ids
);
949 simplifiers
.safe_push (ns
);
953 /* In AST operand O replace operator ID with operator WITH. */
956 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
958 /* Deep-copy captures and expressions, replacing operations as
960 if (capture
*c
= dyn_cast
<capture
*> (o
))
964 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
966 else if (expr
*e
= dyn_cast
<expr
*> (o
))
968 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
970 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
971 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
975 /* For c_expr we simply record a string replacement table which is
976 applied at code-generation time. */
977 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
979 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
980 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
981 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
987 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
990 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
992 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
993 unsigned worklist_start
= 0;
994 auto_vec
<simplify
*> worklist
;
995 worklist
.safe_push (sin
);
997 /* Lower each recorded for separately, operating on the
998 set of simplifiers created by the previous one.
999 Lower inner-to-outer so inner for substitutes can refer
1000 to operators replaced by outer fors. */
1001 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1003 vec
<user_id
*>& ids
= for_vec
[fi
];
1004 unsigned n_ids
= ids
.length ();
1005 unsigned max_n_opers
= 0;
1006 for (unsigned i
= 0; i
< n_ids
; ++i
)
1007 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1008 max_n_opers
= ids
[i
]->substitutes
.length ();
1010 unsigned worklist_end
= worklist
.length ();
1011 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1013 simplify
*s
= worklist
[si
];
1014 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1016 operand
*match_op
= s
->match
;
1017 operand
*result_op
= s
->result
;
1018 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1020 for (unsigned i
= 0; i
< n_ids
; ++i
)
1022 user_id
*id
= ids
[i
];
1023 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1024 match_op
= replace_id (match_op
, id
, oper
);
1026 result_op
= replace_id (result_op
, id
, oper
);
1027 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1028 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1031 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1032 result_op
, s
->result_location
,
1033 ifexpr_vec
, vNULL
, s
->capture_ids
);
1034 worklist
.safe_push (ns
);
1037 worklist_start
= worklist_end
;
1040 /* Copy out the result from the last for lowering. */
1041 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1042 simplifiers
.safe_push (worklist
[i
]);
1045 /* Lower the AST for everything in SIMPLIFIERS. */
1048 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1050 auto_vec
<simplify
*> out_simplifiers
;
1051 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1052 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1054 simplifiers
.truncate (0);
1055 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1056 lower_commutative (out_simplifiers
[i
], simplifiers
);
1058 out_simplifiers
.truncate (0);
1060 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1061 lower_cond (simplifiers
[i
], out_simplifiers
);
1063 out_simplifiers
.safe_splice (simplifiers
);
1066 simplifiers
.truncate (0);
1067 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1068 lower_for (out_simplifiers
[i
], simplifiers
);
1074 /* The decision tree built for generating GIMPLE and GENERIC pattern
1075 matching code. It represents the 'match' expression of all
1076 simplifies and has those as its leafs. */
1078 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1082 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1086 vec
<dt_node
*> kids
;
1088 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1090 dt_node
*append_node (dt_node
*);
1091 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1092 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1093 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1094 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1096 virtual void gen (FILE *, bool) {}
1098 void gen_kids (FILE *, bool);
1101 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1103 struct dt_operand
: public dt_node
1106 dt_operand
*match_dop
;
1110 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1111 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1112 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1113 parent (parent_
), pos (pos_
) {}
1115 void gen (FILE *, bool);
1116 unsigned gen_predicate (FILE *, const char *, bool);
1117 unsigned gen_match_op (FILE *, const char *);
1119 unsigned gen_gimple_expr (FILE *);
1120 unsigned gen_generic_expr (FILE *, const char *);
1122 char *get_name (char *);
1123 void gen_opname (char *, unsigned);
1126 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1128 struct dt_simplify
: public dt_node
1131 unsigned pattern_no
;
1132 dt_operand
**indexes
;
1134 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1135 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1136 indexes (indexes_
) {}
1138 void gen (FILE *f
, bool);
1144 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1146 return (n
->type
== dt_node::DT_OPERAND
1147 || n
->type
== dt_node::DT_MATCH
);
1150 /* A container for the actual decision tree. */
1152 struct decision_tree
1156 void insert (struct simplify
*, unsigned);
1157 void gen_gimple (FILE *f
= stderr
);
1158 void gen_generic (FILE *f
= stderr
);
1159 void print (FILE *f
= stderr
);
1161 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1163 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1164 unsigned pos
= 0, dt_node
*parent
= 0);
1165 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1166 static bool cmp_node (dt_node
*, dt_node
*);
1167 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1170 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1173 cmp_operand (operand
*o1
, operand
*o2
)
1175 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1178 if (o1
->type
== operand::OP_PREDICATE
)
1180 predicate
*p1
= as_a
<predicate
*>(o1
);
1181 predicate
*p2
= as_a
<predicate
*>(o2
);
1182 return p1
->p
== p2
->p
;
1184 else if (o1
->type
== operand::OP_EXPR
)
1186 expr
*e1
= static_cast<expr
*>(o1
);
1187 expr
*e2
= static_cast<expr
*>(o2
);
1188 return (e1
->operation
== e2
->operation
1189 && e1
->is_generic
== e2
->is_generic
);
1195 /* Compare two decision tree nodes N1 and N2 and return true if they
1199 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1201 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1204 if (n1
== n2
|| n1
->type
== dt_node::DT_TRUE
)
1207 if (n1
->type
== dt_node::DT_OPERAND
)
1208 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1209 (as_a
<dt_operand
*> (n2
))->op
);
1210 else if (n1
->type
== dt_node::DT_MATCH
)
1211 return ((as_a
<dt_operand
*> (n1
))->match_dop
1212 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1216 /* Search OPS for a decision tree node like P and return it if found. */
1219 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1221 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1222 if (decision_tree::cmp_node (ops
[i
], p
))
1228 /* Append N to the decision tree if it there is not already an existing
1232 dt_node::append_node (dt_node
*n
)
1236 kid
= decision_tree::find_node (kids
, n
);
1241 n
->level
= this->level
+ 1;
1243 unsigned len
= kids
.length ();
1245 if (len
> 1 && kids
[len
- 2]->type
== dt_node::DT_TRUE
)
1247 dt_node
*p
= kids
[len
- 2];
1248 kids
[len
- 2] = kids
[len
- 1];
1255 /* Append OP to the decision tree. */
1258 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1260 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1261 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1262 return append_node (n
);
1265 /* Append a DT_TRUE decision tree node. */
1268 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1270 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1271 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1272 return append_node (n
);
1275 /* Append a DT_MATCH decision tree node. */
1278 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1280 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1281 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1282 return append_node (n
);
1285 /* Append S to the decision tree. */
1288 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1289 dt_operand
**indexes
)
1291 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1292 return append_node (n
);
1295 /* Insert O into the decision tree and return the decision tree node found
1299 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1300 unsigned pos
, dt_node
*parent
)
1302 dt_node
*q
, *elm
= 0;
1304 if (capture
*c
= dyn_cast
<capture
*> (o
))
1306 unsigned capt_index
= c
->where
;
1308 if (indexes
[capt_index
] == 0)
1311 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1314 q
= elm
= p
->append_true_op (parent
, pos
);
1317 // get to the last capture
1318 for (operand
*what
= c
->what
;
1319 what
&& is_a
<capture
*> (what
);
1320 c
= as_a
<capture
*> (what
), what
= c
->what
)
1325 unsigned cc_index
= c
->where
;
1326 dt_operand
*match_op
= indexes
[cc_index
];
1328 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1329 elm
= decision_tree::find_node (p
->kids
, &temp
);
1333 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1334 elm
= decision_tree::find_node (p
->kids
, &temp
);
1339 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1340 elm
= decision_tree::find_node (p
->kids
, &temp
);
1344 gcc_assert (elm
->type
== dt_node::DT_TRUE
1345 || elm
->type
== dt_node::DT_OPERAND
1346 || elm
->type
== dt_node::DT_MATCH
);
1347 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1352 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1354 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1359 p
= p
->append_op (o
, parent
, pos
);
1362 if (expr
*e
= dyn_cast
<expr
*>(o
))
1364 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1365 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1371 /* Insert S into the decision tree. */
1374 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1376 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1377 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1378 p
->append_simplify (s
, pattern_no
, indexes
);
1381 /* Debug functions to dump the decision tree. */
1384 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1386 if (p
->type
== dt_node::DT_NODE
)
1387 fprintf (f
, "root");
1391 for (unsigned i
= 0; i
< indent
; i
++)
1394 if (p
->type
== dt_node::DT_OPERAND
)
1396 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1397 print_operand (dop
->op
, f
, true);
1399 else if (p
->type
== dt_node::DT_TRUE
)
1400 fprintf (f
, "true");
1401 else if (p
->type
== dt_node::DT_MATCH
)
1402 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1403 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1405 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1406 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1407 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1408 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1413 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1415 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1416 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1420 decision_tree::print (FILE *f
)
1422 return decision_tree::print_node (root
, f
);
1426 /* For GENERIC we have to take care of wrapping multiple-used
1427 expressions with side-effects in save_expr and preserve side-effects
1428 of expressions with omit_one_operand. Analyze captures in
1429 match, result and with expressions and perform early-outs
1430 on the outermost match expression operands for cases we cannot
1435 capture_info (simplify
*s
);
1436 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1437 void walk_result (operand
*o
, bool);
1438 void walk_c_expr (c_expr
*);
1444 bool force_no_side_effects_p
;
1445 bool cond_expr_cond_p
;
1446 unsigned long toplevel_msk
;
1447 int result_use_count
;
1450 auto_vec
<cinfo
> info
;
1451 unsigned long force_no_side_effects
;
1454 /* Analyze captures in S. */
1456 capture_info::capture_info (simplify
*s
)
1460 || ((e
= dyn_cast
<expr
*> (s
->result
))
1461 && is_a
<predicate_id
*> (e
->operation
)))
1463 force_no_side_effects
= -1;
1467 force_no_side_effects
= 0;
1468 info
.safe_grow_cleared (s
->capture_max
+ 1);
1469 e
= as_a
<expr
*> (s
->match
);
1470 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1471 walk_match (e
->ops
[i
], i
,
1472 (i
!= 0 && *e
->operation
== COND_EXPR
)
1473 || *e
->operation
== TRUTH_ANDIF_EXPR
1474 || *e
->operation
== TRUTH_ORIF_EXPR
,
1476 && (*e
->operation
== COND_EXPR
1477 || *e
->operation
== VEC_COND_EXPR
));
1479 walk_result (s
->result
, false);
1481 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1482 if (s
->ifexpr_vec
[i
].is_with
)
1483 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1486 /* Analyze captures in the match expression piece O. */
1489 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1490 bool conditional_p
, bool cond_expr_cond_p
)
1492 if (capture
*c
= dyn_cast
<capture
*> (o
))
1494 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1495 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1496 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1497 /* Mark expr (non-leaf) captures and recurse. */
1499 && is_a
<expr
*> (c
->what
))
1501 info
[c
->where
].expr_p
= true;
1502 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1505 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1507 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1509 bool cond_p
= conditional_p
;
1510 bool cond_expr_cond_p
= false;
1511 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1513 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1514 || *e
->operation
== TRUTH_ORIF_EXPR
)
1517 && (*e
->operation
== COND_EXPR
1518 || *e
->operation
== VEC_COND_EXPR
))
1519 cond_expr_cond_p
= true;
1520 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1523 else if (is_a
<predicate
*> (o
))
1525 /* Mark non-captured leafs toplevel arg for checking. */
1526 force_no_side_effects
|= 1 << toplevel_arg
;
1532 /* Analyze captures in the result expression piece O. */
1535 capture_info::walk_result (operand
*o
, bool conditional_p
)
1537 if (capture
*c
= dyn_cast
<capture
*> (o
))
1539 info
[c
->where
].result_use_count
++;
1540 /* If we substitute an expression capture we don't know
1541 which captures this will end up using (well, we don't
1542 compute that). Force the uses to be side-effect free
1543 which means forcing the toplevels that reach the
1544 expression side-effect free. */
1545 if (info
[c
->where
].expr_p
)
1546 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1547 /* Mark CSE capture capture uses as forced to have
1550 && is_a
<expr
*> (c
->what
))
1552 info
[c
->where
].cse_p
= true;
1553 walk_result (c
->what
, true);
1556 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1558 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1560 bool cond_p
= conditional_p
;
1561 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1563 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1564 || *e
->operation
== TRUTH_ORIF_EXPR
)
1566 walk_result (e
->ops
[i
], cond_p
);
1569 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1575 /* Look for captures in the C expr E. */
1578 capture_info::walk_c_expr (c_expr
*e
)
1580 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1581 unsigned p_depth
= 0;
1582 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1584 const cpp_token
*t
= &e
->code
[i
];
1585 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1586 if (t
->type
== CPP_NAME
1587 && strcmp ((const char *)CPP_HASHNODE
1588 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1589 && n
->type
== CPP_OPEN_PAREN
)
1591 else if (t
->type
== CPP_CLOSE_PAREN
1594 else if (p_depth
== 0
1595 && t
->type
== CPP_ATSIGN
1596 && (n
->type
== CPP_NUMBER
1597 || n
->type
== CPP_NAME
)
1598 && !(n
->flags
& PREV_WHITE
))
1601 if (n
->type
== CPP_NUMBER
)
1602 id
= (const char *)n
->val
.str
.text
;
1604 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1605 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1611 /* Code generation off the decision tree and the refered AST nodes. */
1614 is_conversion (id_base
*op
)
1616 return (*op
== CONVERT_EXPR
1618 || *op
== FLOAT_EXPR
1619 || *op
== FIX_TRUNC_EXPR
1620 || *op
== VIEW_CONVERT_EXPR
);
1623 /* Get the type to be used for generating operands of OP from the
1627 get_operand_type (id_base
*op
, const char *in_type
,
1628 const char *expr_type
,
1629 const char *other_oprnd_type
)
1631 /* Generally operands whose type does not match the type of the
1632 expression generated need to know their types but match and
1633 thus can fall back to 'other_oprnd_type'. */
1634 if (is_conversion (op
))
1635 return other_oprnd_type
;
1636 else if (*op
== REALPART_EXPR
1637 || *op
== IMAGPART_EXPR
)
1638 return other_oprnd_type
;
1639 else if (is_a
<operator_id
*> (op
)
1640 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1641 return other_oprnd_type
;
1644 /* Otherwise all types should match - choose one in order of
1651 return other_oprnd_type
;
1655 /* Generate transform code for an expression. */
1658 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1659 const char *in_type
, capture_info
*cinfo
,
1660 dt_operand
**indexes
, bool)
1662 bool conversion_p
= is_conversion (operation
);
1663 const char *type
= expr_type
;
1666 /* If there was a type specification in the pattern use it. */
1668 else if (conversion_p
)
1669 /* For conversions we need to build the expression using the
1670 outer type passed in. */
1672 else if (*operation
== REALPART_EXPR
1673 || *operation
== IMAGPART_EXPR
)
1675 /* __real and __imag use the component type of its operand. */
1676 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1679 else if (is_a
<operator_id
*> (operation
)
1680 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1682 /* comparisons use boolean_type_node (or what gets in), but
1683 their operands need to figure out the types themselves. */
1684 sprintf (optype
, "boolean_type_node");
1689 /* Other operations are of the same type as their first operand. */
1690 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1694 fatal ("two conversions in a row");
1697 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1699 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1700 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1703 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1705 = get_operand_type (operation
, in_type
, expr_type
,
1706 i
== 0 ? NULL
: op0type
);
1707 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1708 ((!(*operation
== COND_EXPR
)
1709 && !(*operation
== VEC_COND_EXPR
))
1714 if (*operation
== CONVERT_EXPR
)
1717 opr
= operation
->id
;
1721 /* ??? Have another helper that is like gimple_build but may
1722 fail if seq == NULL. */
1723 fprintf (f
, " if (!seq)\n"
1725 " res = gimple_simplify (%s, %s", opr
, type
);
1726 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1727 fprintf (f
, ", ops%d[%u]", depth
, i
);
1728 fprintf (f
, ", seq, valueize);\n");
1729 fprintf (f
, " if (!res) return false;\n");
1730 fprintf (f
, " }\n");
1731 fprintf (f
, " else\n");
1732 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1734 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1735 fprintf (f
, ", ops%d[%u]", depth
, i
);
1736 fprintf (f
, ", valueize);\n");
1740 if (operation
->kind
== id_base::CODE
)
1741 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1742 ops
.length(), opr
, type
);
1744 fprintf (f
, " res = build_call_expr_loc (loc, "
1745 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1746 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1747 fprintf (f
, ", ops%d[%u]", depth
, i
);
1748 fprintf (f
, ");\n");
1750 fprintf (f
, " %s = res;\n", dest
);
1754 /* Generate code for a c_expr which is either the expression inside
1755 an if statement or a sequence of statements which computes a
1756 result to be stored to DEST. */
1759 c_expr::gen_transform (FILE *f
, const char *dest
,
1760 bool, int, const char *, capture_info
*,
1761 dt_operand
**, bool)
1763 if (dest
&& nr_stmts
== 1)
1764 fprintf (f
, "%s = ", dest
);
1766 unsigned stmt_nr
= 1;
1767 for (unsigned i
= 0; i
< code
.length (); ++i
)
1769 const cpp_token
*token
= &code
[i
];
1771 /* Replace captures for code-gen. */
1772 if (token
->type
== CPP_ATSIGN
)
1774 const cpp_token
*n
= &code
[i
+1];
1775 if ((n
->type
== CPP_NUMBER
1776 || n
->type
== CPP_NAME
)
1777 && !(n
->flags
& PREV_WHITE
))
1779 if (token
->flags
& PREV_WHITE
)
1782 if (n
->type
== CPP_NUMBER
)
1783 id
= (const char *)n
->val
.str
.text
;
1785 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1786 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1792 if (token
->flags
& PREV_WHITE
)
1795 if (token
->type
== CPP_NAME
)
1797 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1799 for (j
= 0; j
< ids
.length (); ++j
)
1801 if (strcmp (id
, ids
[j
].id
) == 0)
1803 fprintf (f
, "%s", ids
[j
].oper
);
1807 if (j
< ids
.length ())
1811 /* Output the token as string. */
1812 char *tk
= (char *)cpp_token_as_text (r
, token
);
1815 if (token
->type
== CPP_SEMICOLON
)
1818 if (dest
&& stmt_nr
== nr_stmts
)
1819 fprintf (f
, "\n %s = ", dest
);
1826 /* Generate transform code for a capture. */
1829 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1830 const char *in_type
, capture_info
*cinfo
,
1831 dt_operand
**indexes
, bool expand_compares
)
1833 if (what
&& is_a
<expr
*> (what
))
1835 if (indexes
[where
] == 0)
1838 sprintf (buf
, "captures[%u]", where
);
1839 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1843 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1845 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1846 with substituting a capture of that.
1847 ??? Returning false here will also not allow any other patterns
1849 if (gimple
&& expand_compares
1850 && cinfo
->info
[where
].cond_expr_cond_p
)
1851 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1853 " if (!seq) return false;\n"
1854 " %s = gimple_build (seq, TREE_CODE (%s),"
1855 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1856 " TREE_OPERAND (%s, 1));\n"
1857 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1860 /* Return the name of the operand representing the decision tree node.
1861 Use NAME as space to generate it. */
1864 dt_operand::get_name (char *name
)
1867 sprintf (name
, "t");
1868 else if (parent
->level
== 1)
1869 sprintf (name
, "op%u", pos
);
1870 else if (parent
->type
== dt_node::DT_MATCH
)
1871 return parent
->get_name (name
);
1873 sprintf (name
, "o%u%u", parent
->level
, pos
);
1877 /* Fill NAME with the operand name at position POS. */
1880 dt_operand::gen_opname (char *name
, unsigned pos
)
1883 sprintf (name
, "op%u", pos
);
1885 sprintf (name
, "o%u%u", level
, pos
);
1888 /* Generate matching code for the decision tree operand which is
1892 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1894 predicate
*p
= as_a
<predicate
*> (op
);
1896 if (p
->p
->matchers
.exists ())
1898 /* If this is a predicate generated from a pattern mangle its
1899 name and pass on the valueize hook. */
1901 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1903 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1906 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1911 /* Generate matching code for the decision tree operand which is
1915 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1917 char match_opname
[20];
1918 match_dop
->get_name (match_opname
);
1919 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1920 opname
, match_opname
, opname
, match_opname
);
1925 /* Generate GIMPLE matching code for the decision tree operand. */
1928 dt_operand::gen_gimple_expr (FILE *f
)
1930 expr
*e
= static_cast<expr
*> (op
);
1931 id_base
*id
= e
->operation
;
1932 unsigned n_ops
= e
->ops
.length ();
1934 for (unsigned i
= 0; i
< n_ops
; ++i
)
1936 char child_opname
[20];
1937 gen_opname (child_opname
, i
);
1939 if (id
->kind
== id_base::CODE
)
1942 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1943 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1945 /* ??? If this is a memory operation we can't (and should not)
1946 match this. The only sensible operand types are
1947 SSA names and invariants. */
1948 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1950 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1951 "|| is_gimple_min_invariant (%s))\n"
1952 "&& (%s = do_valueize (valueize, %s)))\n"
1953 "{\n", child_opname
, child_opname
, child_opname
,
1958 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1959 child_opname
, i
+ 1);
1962 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1964 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1965 child_opname
, child_opname
);
1972 /* Generate GENERIC matching code for the decision tree operand. */
1975 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1977 expr
*e
= static_cast<expr
*> (op
);
1978 unsigned n_ops
= e
->ops
.length ();
1980 for (unsigned i
= 0; i
< n_ops
; ++i
)
1982 char child_opname
[20];
1983 gen_opname (child_opname
, i
);
1985 if (e
->operation
->kind
== id_base::CODE
)
1986 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1987 child_opname
, opname
, i
);
1989 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1990 child_opname
, opname
, i
);
1996 /* Generate matching code for the children of the decision tree node. */
1999 dt_node::gen_kids (FILE *f
, bool gimple
)
2001 auto_vec
<dt_operand
*> gimple_exprs
;
2002 auto_vec
<dt_operand
*> generic_exprs
;
2003 auto_vec
<dt_operand
*> fns
;
2004 auto_vec
<dt_operand
*> generic_fns
;
2005 auto_vec
<dt_operand
*> preds
;
2006 auto_vec
<dt_node
*> others
;
2007 dt_node
*true_operand
= NULL
;
2009 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2011 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2013 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2014 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2016 if (e
->ops
.length () == 0)
2017 generic_exprs
.safe_push (op
);
2018 else if (e
->operation
->kind
== id_base::FN
)
2023 generic_fns
.safe_push (op
);
2025 else if (e
->operation
->kind
== id_base::PREDICATE
)
2026 preds
.safe_push (op
);
2030 gimple_exprs
.safe_push (op
);
2032 generic_exprs
.safe_push (op
);
2035 else if (op
->op
->type
== operand::OP_PREDICATE
)
2036 others
.safe_push (kids
[i
]);
2040 else if (kids
[i
]->type
== dt_node::DT_MATCH
2041 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2042 others
.safe_push (kids
[i
]);
2043 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2044 true_operand
= kids
[i
];
2050 char *kid_opname
= buf
;
2052 unsigned exprs_len
= gimple_exprs
.length ();
2053 unsigned gexprs_len
= generic_exprs
.length ();
2054 unsigned fns_len
= fns
.length ();
2055 unsigned gfns_len
= generic_fns
.length ();
2057 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2060 gimple_exprs
[0]->get_name (kid_opname
);
2062 fns
[0]->get_name (kid_opname
);
2064 generic_fns
[0]->get_name (kid_opname
);
2066 generic_exprs
[0]->get_name (kid_opname
);
2068 fprintf (f
, "switch (TREE_CODE (%s))\n"
2072 if (exprs_len
|| fns_len
)
2074 fprintf (f
, "case SSA_NAME:\n");
2075 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2077 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2081 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2082 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2084 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2086 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2087 id_base
*op
= e
->operation
;
2088 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2089 fprintf (f
, "CASE_CONVERT:\n");
2091 fprintf (f
, "case %s:\n", op
->id
);
2093 gimple_exprs
[i
]->gen (f
, true);
2094 fprintf (f
, "break;\n"
2097 fprintf (f
, "default:;\n"
2104 fprintf (f
, "else ");
2106 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2108 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2109 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2112 for (unsigned i
= 0; i
< fns_len
; ++i
)
2114 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2115 fprintf (f
, "case %s:\n"
2116 "{\n", e
->operation
->id
);
2117 fns
[i
]->gen (f
, true);
2118 fprintf (f
, "break;\n"
2122 fprintf (f
, "default:;\n"
2131 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2133 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2134 id_base
*op
= e
->operation
;
2135 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2136 fprintf (f
, "CASE_CONVERT:\n");
2138 fprintf (f
, "case %s:\n", op
->id
);
2140 generic_exprs
[i
]->gen (f
, gimple
);
2141 fprintf (f
, "break;\n"
2147 fprintf (f
, "case CALL_EXPR:\n"
2149 "tree fndecl = get_callee_fndecl (%s);\n"
2150 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2151 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2154 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2156 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2157 gcc_assert (e
->operation
->kind
== id_base::FN
);
2159 fprintf (f
, "case %s:\n"
2160 "{\n", e
->operation
->id
);
2161 generic_fns
[j
]->gen (f
, false);
2162 fprintf (f
, "break;\n"
2166 fprintf (f
, "default:;\n"
2172 /* Close switch (TREE_CODE ()). */
2173 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2174 fprintf (f
, "default:;\n"
2177 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2179 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2180 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2181 preds
[i
]->get_name (kid_opname
);
2182 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2183 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2184 gimple
? "gimple" : "tree",
2185 p
->id
, kid_opname
, kid_opname
,
2186 gimple
? ", valueize" : "");
2188 for (int j
= 0; j
< p
->nargs
; ++j
)
2190 char child_opname
[20];
2191 preds
[i
]->gen_opname (child_opname
, j
);
2192 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2194 preds
[i
]->gen_kids (f
, gimple
);
2198 for (unsigned i
= 0; i
< others
.length (); ++i
)
2199 others
[i
]->gen (f
, gimple
);
2202 true_operand
->gen (f
, gimple
);
2205 /* Generate matching code for the decision tree operand. */
2208 dt_operand::gen (FILE *f
, bool gimple
)
2213 unsigned n_braces
= 0;
2215 if (type
== DT_OPERAND
)
2218 case operand::OP_PREDICATE
:
2219 n_braces
= gen_predicate (f
, opname
, gimple
);
2222 case operand::OP_EXPR
:
2224 n_braces
= gen_gimple_expr (f
);
2226 n_braces
= gen_generic_expr (f
, opname
);
2232 else if (type
== DT_TRUE
)
2234 else if (type
== DT_MATCH
)
2235 n_braces
= gen_match_op (f
, opname
);
2239 gen_kids (f
, gimple
);
2241 for (unsigned i
= 0; i
< n_braces
; ++i
)
2247 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2248 step of a '(simplify ...)' or '(match ...)'. This handles everything
2249 that is not part of the decision tree (simplify->match). */
2252 dt_simplify::gen (FILE *f
, bool gimple
)
2255 output_line_directive (f
, s
->result_location
);
2256 if (s
->capture_max
>= 0)
2257 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2258 s
->capture_max
+ 1);
2260 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2264 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2267 unsigned n_braces
= 0;
2268 if (s
->ifexpr_vec
!= vNULL
)
2270 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2272 if_or_with
&w
= s
->ifexpr_vec
[i
];
2276 output_line_directive (f
, w
.location
);
2277 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2282 output_line_directive (f
, w
.location
);
2283 fprintf (f
, "if (");
2284 if (i
== s
->ifexpr_vec
.length () - 1
2285 || s
->ifexpr_vec
[i
+1].is_with
)
2286 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2295 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2299 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2305 while (j
< s
->ifexpr_vec
.length ()
2306 && !s
->ifexpr_vec
[j
].is_with
);
2316 /* Analyze captures and perform early-outs on the incoming arguments
2317 that cover cases we cannot handle. */
2318 capture_info
cinfo (s
);
2322 && !((e
= dyn_cast
<expr
*> (s
->result
))
2323 && is_a
<predicate_id
*> (e
->operation
)))
2325 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2326 if (cinfo
.force_no_side_effects
& (1 << i
))
2327 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2328 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2329 if (cinfo
.info
[i
].cse_p
)
2331 else if (cinfo
.info
[i
].force_no_side_effects_p
2332 && (cinfo
.info
[i
].toplevel_msk
2333 & cinfo
.force_no_side_effects
) == 0)
2334 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2335 "return NULL_TREE;\n", i
);
2336 else if ((cinfo
.info
[i
].toplevel_msk
2337 & cinfo
.force_no_side_effects
) != 0)
2338 /* Mark capture as having no side-effects if we had to verify
2339 that via forced toplevel operand checks. */
2340 cinfo
.info
[i
].force_no_side_effects_p
= true;
2343 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2344 "fprintf (dump_file, \"Applying pattern ");
2345 output_line_directive (f
, s
->result_location
, true);
2346 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2348 operand
*result
= s
->result
;
2351 /* If there is no result then this is a predicate implementation. */
2352 fprintf (f
, "return true;\n");
2356 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2357 in outermost position). */
2358 if (result
->type
== operand::OP_EXPR
2359 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2360 result
= as_a
<expr
*> (result
)->ops
[0];
2361 if (result
->type
== operand::OP_EXPR
)
2363 expr
*e
= as_a
<expr
*> (result
);
2364 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2366 fprintf (f
, "*res_code = %s;\n",
2367 *e
->operation
== CONVERT_EXPR
2368 ? "NOP_EXPR" : e
->operation
->id
);
2369 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2372 snprintf (dest
, 32, " res_ops[%d]", j
);
2374 = get_operand_type (e
->operation
,
2375 "type", e
->expr_type
,
2377 ? NULL
: "TREE_TYPE (res_ops[0])");
2378 /* We need to expand GENERIC conditions we captured from
2380 bool expand_generic_cond_exprs_p
2382 /* But avoid doing that if the GENERIC condition is
2383 valid - which it is in the first operand of COND_EXPRs
2384 and VEC_COND_EXRPs. */
2385 && ((!(*e
->operation
== COND_EXPR
)
2386 && !(*e
->operation
== VEC_COND_EXPR
))
2388 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2389 indexes
, expand_generic_cond_exprs_p
);
2392 /* Re-fold the toplevel result. It's basically an embedded
2393 gimple_build w/o actually building the stmt. */
2395 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2396 "res_ops, valueize);\n", e
->ops
.length ());
2398 else if (result
->type
== operand::OP_CAPTURE
2399 || result
->type
== operand::OP_C_EXPR
)
2401 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2402 &cinfo
, indexes
, false);
2403 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2404 if (is_a
<capture
*> (result
)
2405 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2407 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2408 with substituting a capture of that. */
2409 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2411 " tree tem = res_ops[0];\n"
2412 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2413 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2419 fprintf (f
, "return true;\n");
2423 bool is_predicate
= false;
2424 if (result
->type
== operand::OP_EXPR
)
2426 expr
*e
= as_a
<expr
*> (result
);
2427 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2428 /* Search for captures used multiple times in the result expression
2429 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2431 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2433 if (!cinfo
.info
[i
].force_no_side_effects_p
2434 && cinfo
.info
[i
].result_use_count
> 1)
2435 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2436 " captures[%d] = save_expr (captures[%d]);\n",
2439 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2443 snprintf (dest
, 32, "res_ops[%d]", j
);
2446 fprintf (f
, " tree res_op%d;\n", j
);
2447 snprintf (dest
, 32, " res_op%d", j
);
2450 = get_operand_type (e
->operation
,
2451 "type", e
->expr_type
,
2453 ? NULL
: "TREE_TYPE (res_op0)");
2454 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2458 fprintf (f
, "return true;\n");
2461 fprintf (f
, " tree res;\n");
2462 /* Re-fold the toplevel result. Use non_lvalue to
2463 build NON_LVALUE_EXPRs so they get properly
2464 ignored when in GIMPLE form. */
2465 if (*e
->operation
== NON_LVALUE_EXPR
)
2466 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2469 if (e
->operation
->kind
== id_base::CODE
)
2470 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2472 *e
->operation
== CONVERT_EXPR
2473 ? "NOP_EXPR" : e
->operation
->id
);
2475 fprintf (f
, " res = build_call_expr_loc "
2476 "(loc, builtin_decl_implicit (%s), %d",
2477 e
->operation
->id
, e
->ops
.length());
2478 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2479 fprintf (f
, ", res_op%d", j
);
2480 fprintf (f
, ");\n");
2484 else if (result
->type
== operand::OP_CAPTURE
2485 || result
->type
== operand::OP_C_EXPR
)
2488 fprintf (f
, " tree res;\n");
2489 s
->result
->gen_transform (f
, " res", false, 1, "type",
2496 /* Search for captures not used in the result expression and dependent
2497 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2498 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2500 if (!cinfo
.info
[i
].force_no_side_effects_p
2501 && !cinfo
.info
[i
].expr_p
2502 && cinfo
.info
[i
].result_use_count
== 0)
2503 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2504 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2505 " fold_ignored_result (captures[%d]), res);\n",
2508 fprintf (f
, " return res;\n");
2512 for (unsigned i
= 0; i
< n_braces
; ++i
)
2518 /* Main entry to generate code for matching GIMPLE IL off the decision
2522 decision_tree::gen_gimple (FILE *f
)
2524 for (unsigned n
= 1; n
<= 3; ++n
)
2526 fprintf (f
, "\nstatic bool\n"
2527 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2528 " gimple_seq *seq, tree (*valueize)(tree),\n"
2529 " code_helper code, tree type");
2530 for (unsigned i
= 0; i
< n
; ++i
)
2531 fprintf (f
, ", tree op%d", i
);
2535 fprintf (f
, "switch (code.get_rep())\n"
2537 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2539 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2540 expr
*e
= static_cast<expr
*>(dop
->op
);
2541 if (e
->ops
.length () != n
)
2544 if (*e
->operation
== CONVERT_EXPR
2545 || *e
->operation
== NOP_EXPR
)
2546 fprintf (f
, "CASE_CONVERT:\n");
2548 fprintf (f
, "case %s%s:\n",
2549 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2552 dop
->gen_kids (f
, true);
2553 fprintf (f
, "break;\n");
2556 fprintf (f
, "default:;\n"
2559 fprintf (f
, "return false;\n");
2564 /* Main entry to generate code for matching GENERIC IL off the decision
2568 decision_tree::gen_generic (FILE *f
)
2570 for (unsigned n
= 1; n
<= 3; ++n
)
2572 fprintf (f
, "\ntree\n"
2573 "generic_simplify (location_t loc, enum tree_code code, "
2574 "tree type ATTRIBUTE_UNUSED");
2575 for (unsigned i
= 0; i
< n
; ++i
)
2576 fprintf (f
, ", tree op%d", i
);
2580 fprintf (f
, "switch (code)\n"
2582 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2584 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2585 expr
*e
= static_cast<expr
*>(dop
->op
);
2586 if (e
->ops
.length () != n
2587 /* Builtin simplifications are somewhat premature on
2588 GENERIC. The following drops patterns with outermost
2589 calls. It's easy to emit overloads for function code
2590 though if necessary. */
2591 || e
->operation
->kind
!= id_base::CODE
)
2594 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2595 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2596 fprintf (f
, "CASE_CONVERT:\n");
2598 fprintf (f
, "case %s:\n", e
->operation
->id
);
2600 dop
->gen_kids (f
, false);
2601 fprintf (f
, "break;\n"
2604 fprintf (f
, "default:;\n"
2607 fprintf (f
, "return NULL_TREE;\n");
2612 /* Output code to implement the predicate P from the decision tree DT. */
2615 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2617 fprintf (f
, "\nbool\n"
2618 "%s%s (tree t%s%s)\n"
2619 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2620 p
->nargs
> 0 ? ", tree *res_ops" : "",
2621 gimple
? ", tree (*valueize)(tree)" : "");
2622 /* Conveniently make 'type' available. */
2623 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2626 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2627 dt
.root
->gen_kids (f
, gimple
);
2629 fprintf (f
, "return false;\n"
2633 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2636 write_header (FILE *f
, const char *head
)
2638 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2639 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2641 /* Include the header instead of writing it awkwardly quoted here. */
2642 fprintf (f
, "\n#include \"%s\"\n", head
);
2652 parser (cpp_reader
*);
2655 const cpp_token
*next ();
2656 const cpp_token
*peek ();
2657 const cpp_token
*peek_ident (const char * = NULL
);
2658 const cpp_token
*expect (enum cpp_ttype
);
2659 void eat_token (enum cpp_ttype
);
2660 const char *get_string ();
2661 const char *get_ident ();
2662 void eat_ident (const char *);
2663 const char *get_number ();
2665 id_base
*parse_operation ();
2666 operand
*parse_capture (operand
*);
2667 operand
*parse_expr ();
2668 c_expr
*parse_c_expr (cpp_ttype
);
2669 operand
*parse_op ();
2671 void parse_pattern ();
2672 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2674 void parse_for (source_location
);
2675 void parse_if (source_location
);
2676 void parse_predicates (source_location
);
2677 void parse_operator_list (source_location
);
2680 vec
<if_or_with
> active_ifs
;
2681 vec
<vec
<user_id
*> > active_fors
;
2683 cid_map_t
*capture_ids
;
2686 vec
<simplify
*> simplifiers
;
2687 vec
<predicate_id
*> user_predicates
;
2688 bool parsing_match_operand
;
2691 /* Lexing helpers. */
2693 /* Read the next non-whitespace token from R. */
2698 const cpp_token
*token
;
2701 token
= cpp_get_token (r
);
2703 while (token
->type
== CPP_PADDING
2704 && token
->type
!= CPP_EOF
);
2708 /* Peek at the next non-whitespace token from R. */
2713 const cpp_token
*token
;
2717 token
= cpp_peek_token (r
, i
++);
2719 while (token
->type
== CPP_PADDING
2720 && token
->type
!= CPP_EOF
);
2721 /* If we peek at EOF this is a fatal error as it leaves the
2722 cpp_reader in unusable state. Assume we really wanted a
2723 token and thus this EOF is unexpected. */
2724 if (token
->type
== CPP_EOF
)
2725 fatal_at (token
, "unexpected end of file");
2729 /* Peek at the next identifier token (or return NULL if the next
2730 token is not an identifier or equal to ID if supplied). */
2733 parser::peek_ident (const char *id
)
2735 const cpp_token
*token
= peek ();
2736 if (token
->type
!= CPP_NAME
)
2742 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2743 if (strcmp (id
, t
) == 0)
2749 /* Read the next token from R and assert it is of type TK. */
2752 parser::expect (enum cpp_ttype tk
)
2754 const cpp_token
*token
= next ();
2755 if (token
->type
!= tk
)
2756 fatal_at (token
, "expected %s, got %s",
2757 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2762 /* Consume the next token from R and assert it is of type TK. */
2765 parser::eat_token (enum cpp_ttype tk
)
2770 /* Read the next token from R and assert it is of type CPP_STRING and
2771 return its value. */
2774 parser::get_string ()
2776 const cpp_token
*token
= expect (CPP_STRING
);
2777 return (const char *)token
->val
.str
.text
;
2780 /* Read the next token from R and assert it is of type CPP_NAME and
2781 return its value. */
2784 parser::get_ident ()
2786 const cpp_token
*token
= expect (CPP_NAME
);
2787 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2790 /* Eat an identifier token with value S from R. */
2793 parser::eat_ident (const char *s
)
2795 const cpp_token
*token
= peek ();
2796 const char *t
= get_ident ();
2797 if (strcmp (s
, t
) != 0)
2798 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2801 /* Read the next token from R and assert it is of type CPP_NUMBER and
2802 return its value. */
2805 parser::get_number ()
2807 const cpp_token
*token
= expect (CPP_NUMBER
);
2808 return (const char *)token
->val
.str
.text
;
2812 /* Parse the operator ID, special-casing convert?, convert1? and
2816 parser::parse_operation ()
2818 const cpp_token
*id_tok
= peek ();
2819 const char *id
= get_ident ();
2820 const cpp_token
*token
= peek ();
2821 if (strcmp (id
, "convert0") == 0)
2822 fatal_at (id_tok
, "use 'convert?' here");
2823 if (token
->type
== CPP_QUERY
2824 && !(token
->flags
& PREV_WHITE
))
2826 if (strcmp (id
, "convert") == 0)
2828 else if (strcmp (id
, "convert1") == 0)
2830 else if (strcmp (id
, "convert2") == 0)
2833 fatal_at (id_tok
, "non-convert operator conditionalized");
2835 if (!parsing_match_operand
)
2836 fatal_at (id_tok
, "conditional convert can only be used in "
2837 "match expression");
2838 eat_token (CPP_QUERY
);
2840 else if (strcmp (id
, "convert1") == 0
2841 || strcmp (id
, "convert2") == 0)
2842 fatal_at (id_tok
, "expected '?' after conditional operator");
2843 id_base
*op
= get_operator (id
);
2845 fatal_at (id_tok
, "unknown operator %s", id
);
2847 user_id
*p
= dyn_cast
<user_id
*> (op
);
2848 if (p
&& p
->is_oper_list
)
2849 fatal_at (id_tok
, "operator-list not allowed in expression");
2855 capture = '@'<number> */
2858 parser::parse_capture (operand
*op
)
2860 eat_token (CPP_ATSIGN
);
2861 const cpp_token
*token
= peek ();
2862 const char *id
= NULL
;
2863 if (token
->type
== CPP_NUMBER
)
2865 else if (token
->type
== CPP_NAME
)
2868 fatal_at (token
, "expected number or identifier");
2869 unsigned next_id
= capture_ids
->elements ();
2871 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2874 return new capture (num
, op
);
2877 /* Parse an expression
2878 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2881 parser::parse_expr ()
2883 expr
*e
= new expr (parse_operation ());
2884 const cpp_token
*token
= peek ();
2886 bool is_commutative
= false;
2887 const char *expr_type
= NULL
;
2889 if (token
->type
== CPP_COLON
2890 && !(token
->flags
& PREV_WHITE
))
2892 eat_token (CPP_COLON
);
2894 if (token
->type
== CPP_NAME
2895 && !(token
->flags
& PREV_WHITE
))
2897 const char *s
= get_ident ();
2898 if (s
[0] == 'c' && !s
[1])
2900 if (!parsing_match_operand
)
2902 "flag 'c' can only be used in match expression");
2903 is_commutative
= true;
2905 else if (s
[1] != '\0')
2907 if (parsing_match_operand
)
2908 fatal_at (token
, "type can only be used in result expression");
2912 fatal_at (token
, "flag %s not recognized", s
);
2917 fatal_at (token
, "expected flag or type specifying identifier");
2920 if (token
->type
== CPP_ATSIGN
2921 && !(token
->flags
& PREV_WHITE
))
2922 op
= parse_capture (e
);
2927 const cpp_token
*token
= peek ();
2928 if (token
->type
== CPP_CLOSE_PAREN
)
2930 if (e
->operation
->nargs
!= -1
2931 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2932 fatal_at (token
, "'%s' expects %u operands, not %u",
2933 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2936 if (e
->ops
.length () == 2)
2937 e
->is_commutative
= true;
2939 fatal_at (token
, "only binary operators or function with "
2940 "two arguments can be marked commutative");
2942 e
->expr_type
= expr_type
;
2945 e
->append_op (parse_op ());
2950 /* Lex native C code delimited by START recording the preprocessing tokens
2951 for later processing.
2952 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2955 parser::parse_c_expr (cpp_ttype start
)
2957 const cpp_token
*token
;
2960 vec
<cpp_token
> code
= vNULL
;
2961 unsigned nr_stmts
= 0;
2963 if (start
== CPP_OPEN_PAREN
)
2964 end
= CPP_CLOSE_PAREN
;
2965 else if (start
== CPP_OPEN_BRACE
)
2966 end
= CPP_CLOSE_BRACE
;
2974 /* Count brace pairs to find the end of the expr to match. */
2975 if (token
->type
== start
)
2977 else if (token
->type
== end
2981 /* This is a lame way of counting the number of statements. */
2982 if (token
->type
== CPP_SEMICOLON
)
2985 /* If this is possibly a user-defined identifier mark it used. */
2986 if (token
->type
== CPP_NAME
)
2987 get_operator ((const char *)CPP_HASHNODE
2988 (token
->val
.node
.node
)->ident
.str
);
2990 /* Record the token. */
2991 code
.safe_push (*token
);
2994 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2997 /* Parse an operand which is either an expression, a predicate or
2998 a standalone capture.
2999 op = predicate | expr | c_expr | capture */
3004 const cpp_token
*token
= peek ();
3005 struct operand
*op
= NULL
;
3006 if (token
->type
== CPP_OPEN_PAREN
)
3008 eat_token (CPP_OPEN_PAREN
);
3010 eat_token (CPP_CLOSE_PAREN
);
3012 else if (token
->type
== CPP_OPEN_BRACE
)
3014 op
= parse_c_expr (CPP_OPEN_BRACE
);
3018 /* Remaining ops are either empty or predicates */
3019 if (token
->type
== CPP_NAME
)
3021 const char *id
= get_ident ();
3022 id_base
*opr
= get_operator (id
);
3024 fatal_at (token
, "expected predicate name");
3025 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3027 if (code
->nargs
!= 0)
3028 fatal_at (token
, "using an operator with operands as predicate");
3029 /* Parse the zero-operand operator "predicates" as
3031 op
= new expr (opr
);
3033 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3034 op
= new predicate (p
);
3036 fatal_at (token
, "using an unsupported operator as predicate");
3037 if (!parsing_match_operand
)
3038 fatal_at (token
, "predicates are only allowed in match expression");
3040 if (token
->flags
& PREV_WHITE
)
3043 else if (token
->type
!= CPP_COLON
3044 && token
->type
!= CPP_ATSIGN
)
3045 fatal_at (token
, "expected expression or predicate");
3046 /* optionally followed by a capture and a predicate. */
3047 if (token
->type
== CPP_COLON
)
3048 fatal_at (token
, "not implemented: predicate on leaf operand");
3049 if (token
->type
== CPP_ATSIGN
)
3050 op
= parse_capture (op
);
3057 simplify = 'simplify' <expr> <result-op>
3059 match = 'match' <ident> <expr> [<result-op>]
3061 <result-op> = <op> | <if> | <with>
3062 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3063 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3064 and fill SIMPLIFIERS with the results. */
3067 parser::parse_simplify (source_location match_location
,
3068 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3071 /* Reset the capture map. */
3072 capture_ids
= new cid_map_t
;
3074 const cpp_token
*loc
= peek ();
3075 parsing_match_operand
= true;
3076 struct operand
*match
= parse_op ();
3077 parsing_match_operand
= false;
3078 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3079 fatal_at (loc
, "outermost expression cannot be captured");
3080 if (match
->type
== operand::OP_EXPR
3081 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3082 fatal_at (loc
, "outermost expression cannot be a predicate");
3084 const cpp_token
*token
= peek ();
3086 /* If this if is immediately closed then it is part of a predicate
3087 definition. Push it. */
3088 if (token
->type
== CPP_CLOSE_PAREN
)
3091 fatal_at (token
, "expected transform expression");
3092 simplifiers
.safe_push
3093 (new simplify (match
, match_location
, result
, token
->src_loc
,
3094 active_ifs
.copy (), active_fors
.copy (),
3099 unsigned active_ifs_len
= active_ifs
.length ();
3102 if (token
->type
== CPP_OPEN_PAREN
)
3104 source_location paren_loc
= token
->src_loc
;
3105 eat_token (CPP_OPEN_PAREN
);
3106 if (peek_ident ("if"))
3109 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3110 token
->src_loc
, false));
3111 /* If this if is immediately closed then it contains a
3112 manual matcher or is part of a predicate definition.
3114 if (peek ()->type
== CPP_CLOSE_PAREN
)
3117 fatal_at (token
, "manual transform not implemented");
3118 simplifiers
.safe_push
3119 (new simplify (match
, match_location
, result
,
3120 paren_loc
, active_ifs
.copy (),
3121 active_fors
.copy (), capture_ids
));
3124 else if (peek_ident ("with"))
3127 /* Parse (with c-expr expr) as (if-with (true) expr). */
3128 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3130 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3134 operand
*op
= result
;
3137 simplifiers
.safe_push
3138 (new simplify (match
, match_location
, op
,
3139 token
->src_loc
, active_ifs
.copy (),
3140 active_fors
.copy (), capture_ids
));
3141 eat_token (CPP_CLOSE_PAREN
);
3142 /* A "default" result closes the enclosing scope. */
3143 if (active_ifs
.length () > active_ifs_len
)
3145 eat_token (CPP_CLOSE_PAREN
);
3152 else if (token
->type
== CPP_CLOSE_PAREN
)
3154 /* Close a scope if requested. */
3155 if (active_ifs
.length () > active_ifs_len
)
3157 eat_token (CPP_CLOSE_PAREN
);
3167 fatal_at (token
, "expected match operand expression");
3168 simplifiers
.safe_push
3169 (new simplify (match
, match_location
,
3170 matcher
? result
: parse_op (),
3171 token
->src_loc
, active_ifs
.copy (),
3172 active_fors
.copy (), capture_ids
));
3173 /* A "default" result closes the enclosing scope. */
3174 if (active_ifs
.length () > active_ifs_len
)
3176 eat_token (CPP_CLOSE_PAREN
);
3186 /* Parsing of the outer control structures. */
3188 /* Parse a for expression
3189 for = '(' 'for' <subst>... <pattern> ')'
3190 subst = <ident> '(' <ident>... ')' */
3193 parser::parse_for (source_location
)
3195 auto_vec
<const cpp_token
*> user_id_tokens
;
3196 vec
<user_id
*> user_ids
= vNULL
;
3197 const cpp_token
*token
;
3198 unsigned min_n_opers
= 0, max_n_opers
= 0;
3203 if (token
->type
!= CPP_NAME
)
3206 /* Insert the user defined operators into the operator hash. */
3207 const char *id
= get_ident ();
3208 if (get_operator (id
) != NULL
)
3209 fatal_at (token
, "operator already defined");
3210 user_id
*op
= new user_id (id
);
3211 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3213 user_ids
.safe_push (op
);
3214 user_id_tokens
.safe_push (token
);
3216 eat_token (CPP_OPEN_PAREN
);
3219 while ((token
= peek_ident ()) != 0)
3221 const char *oper
= get_ident ();
3222 id_base
*idb
= get_operator (oper
);
3224 fatal_at (token
, "no such operator '%s'", oper
);
3225 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
3226 fatal_at (token
, "conditional operators cannot be used inside for");
3230 else if (idb
->nargs
== -1)
3232 else if (idb
->nargs
!= arity
)
3233 fatal_at (token
, "operator '%s' with arity %d does not match "
3234 "others with arity %d", oper
, idb
->nargs
, arity
);
3236 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3237 if (p
&& p
->is_oper_list
)
3238 op
->substitutes
.safe_splice (p
->substitutes
);
3240 op
->substitutes
.safe_push (idb
);
3243 token
= expect (CPP_CLOSE_PAREN
);
3245 unsigned nsubstitutes
= op
->substitutes
.length ();
3246 if (nsubstitutes
== 0)
3247 fatal_at (token
, "A user-defined operator must have at least "
3248 "one substitution");
3249 if (max_n_opers
== 0)
3251 min_n_opers
= nsubstitutes
;
3252 max_n_opers
= nsubstitutes
;
3256 if (nsubstitutes
% min_n_opers
!= 0
3257 && min_n_opers
% nsubstitutes
!= 0)
3258 fatal_at (token
, "All user-defined identifiers must have a "
3259 "multiple number of operator substitutions of the "
3260 "smallest number of substitutions");
3261 if (nsubstitutes
< min_n_opers
)
3262 min_n_opers
= nsubstitutes
;
3263 else if (nsubstitutes
> max_n_opers
)
3264 max_n_opers
= nsubstitutes
;
3268 unsigned n_ids
= user_ids
.length ();
3270 fatal_at (token
, "for requires at least one user-defined identifier");
3273 if (token
->type
== CPP_CLOSE_PAREN
)
3274 fatal_at (token
, "no pattern defined in for");
3276 active_fors
.safe_push (user_ids
);
3280 if (token
->type
== CPP_CLOSE_PAREN
)
3286 /* Remove user-defined operators from the hash again. */
3287 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3289 if (!user_ids
[i
]->used
)
3290 warning_at (user_id_tokens
[i
],
3291 "operator %s defined but not used", user_ids
[i
]->id
);
3292 operators
->remove_elt (user_ids
[i
]);
3296 /* Parse an identifier associated with a list of operators.
3297 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3300 parser::parse_operator_list (source_location
)
3302 const cpp_token
*token
= peek ();
3303 const char *id
= get_ident ();
3305 if (get_operator (id
) != 0)
3306 fatal_at (token
, "operator %s already defined", id
);
3308 user_id
*op
= new user_id (id
, true);
3311 while ((token
= peek_ident ()) != 0)
3314 const char *oper
= get_ident ();
3315 id_base
*idb
= get_operator (oper
);
3318 fatal_at (token
, "no such operator '%s'", oper
);
3322 else if (idb
->nargs
== -1)
3324 else if (arity
!= idb
->nargs
)
3325 fatal_at (token
, "operator '%s' with arity %d does not match "
3326 "others with arity %d", oper
, idb
->nargs
, arity
);
3328 /* We allow composition of multiple operator lists. */
3329 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3330 op
->substitutes
.safe_splice (p
->substitutes
);
3332 op
->substitutes
.safe_push (idb
);
3335 if (op
->substitutes
.length () == 0)
3336 fatal_at (token
, "operator-list cannot be empty");
3339 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3343 /* Parse an outer if expression.
3344 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3347 parser::parse_if (source_location loc
)
3349 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3351 const cpp_token
*token
= peek ();
3352 if (token
->type
== CPP_CLOSE_PAREN
)
3353 fatal_at (token
, "no pattern defined in if");
3355 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3358 const cpp_token
*token
= peek ();
3359 if (token
->type
== CPP_CLOSE_PAREN
)
3367 /* Parse a list of predefined predicate identifiers.
3368 preds = '(' 'define_predicates' <ident>... ')' */
3371 parser::parse_predicates (source_location
)
3375 const cpp_token
*token
= peek ();
3376 if (token
->type
!= CPP_NAME
)
3379 add_predicate (get_ident ());
3384 /* Parse outer control structures.
3385 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3388 parser::parse_pattern ()
3390 /* All clauses start with '('. */
3391 eat_token (CPP_OPEN_PAREN
);
3392 const cpp_token
*token
= peek ();
3393 const char *id
= get_ident ();
3394 if (strcmp (id
, "simplify") == 0)
3395 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3396 else if (strcmp (id
, "match") == 0)
3398 bool with_args
= false;
3399 if (peek ()->type
== CPP_OPEN_PAREN
)
3401 eat_token (CPP_OPEN_PAREN
);
3404 const char *name
= get_ident ();
3405 id_base
*id
= get_operator (name
);
3409 p
= add_predicate (name
);
3410 user_predicates
.safe_push (p
);
3412 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3415 fatal_at (token
, "cannot add a match to a non-predicate ID");
3416 /* Parse (match <id> <arg>... (match-expr)) here. */
3421 while (peek ()->type
== CPP_ATSIGN
)
3422 e
->append_op (parse_capture (NULL
));
3423 eat_token (CPP_CLOSE_PAREN
);
3426 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3427 || (!e
&& p
->nargs
!= 0)))
3428 fatal_at (token
, "non-matching number of match operands");
3429 p
->nargs
= e
? e
->ops
.length () : 0;
3430 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3432 else if (strcmp (id
, "for") == 0)
3433 parse_for (token
->src_loc
);
3434 else if (strcmp (id
, "if") == 0)
3435 parse_if (token
->src_loc
);
3436 else if (strcmp (id
, "define_predicates") == 0)
3438 if (active_ifs
.length () > 0
3439 || active_fors
.length () > 0)
3440 fatal_at (token
, "define_predicates inside if or for is not supported");
3441 parse_predicates (token
->src_loc
);
3443 else if (strcmp (id
, "define_operator_list") == 0)
3445 if (active_ifs
.length () > 0
3446 || active_fors
.length () > 0)
3447 fatal_at (token
, "operator-list inside if or for is not supported");
3448 parse_operator_list (token
->src_loc
);
3451 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3452 active_ifs
.length () == 0 && active_fors
.length () == 0
3453 ? "'define_predicates', " : "");
3455 eat_token (CPP_CLOSE_PAREN
);
3458 /* Main entry of the parser. Repeatedly parse outer control structures. */
3460 parser::parser (cpp_reader
*r_
)
3464 active_fors
= vNULL
;
3465 simplifiers
= vNULL
;
3466 user_predicates
= vNULL
;
3467 parsing_match_operand
= false;
3469 const cpp_token
*token
= next ();
3470 while (token
->type
!= CPP_EOF
)
3472 _cpp_backup_tokens (r
, 1);
3479 /* Helper for the linemap code. */
3482 round_alloc_size (size_t s
)
3488 /* The genmatch generator progam. It reads from a pattern description
3489 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3492 main (int argc
, char **argv
)
3496 progname
= "genmatch";
3502 bool verbose
= false;
3503 char *input
= argv
[argc
-1];
3504 for (int i
= 1; i
< argc
- 1; ++i
)
3506 if (strcmp (argv
[i
], "--gimple") == 0)
3508 else if (strcmp (argv
[i
], "--generic") == 0)
3510 else if (strcmp (argv
[i
], "-v") == 0)
3514 fprintf (stderr
, "Usage: genmatch "
3515 "[--gimple] [--generic] [-v] input\n");
3520 line_table
= XCNEW (struct line_maps
);
3521 linemap_init (line_table
, 0);
3522 line_table
->reallocator
= xrealloc
;
3523 line_table
->round_alloc_size
= round_alloc_size
;
3525 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3526 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3527 cb
->error
= error_cb
;
3529 if (!cpp_read_main_file (r
, input
))
3531 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3532 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3534 /* Pre-seed operators. */
3535 operators
= new hash_table
<id_base
> (1024);
3536 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3537 add_operator (SYM, # SYM, # TYPE, NARGS);
3538 #define END_OF_BASE_TREE_CODES
3540 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3541 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3542 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3543 #undef END_OF_BASE_TREE_CODES
3546 /* Pre-seed builtin functions.
3547 ??? Cannot use N (name) as that is targetm.emultls.get_address
3548 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3549 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3550 add_builtin (ENUM, # ENUM);
3551 #include "builtins.def"
3558 write_header (stdout
, "gimple-match-head.c");
3560 write_header (stdout
, "generic-match-head.c");
3562 /* Go over all predicates defined with patterns and perform
3563 lowering and code generation. */
3564 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3566 predicate_id
*pred
= p
.user_predicates
[i
];
3567 lower (pred
->matchers
, gimple
);
3570 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3571 print_matches (pred
->matchers
[i
]);
3574 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3575 dt
.insert (pred
->matchers
[i
], i
);
3580 write_predicate (stdout
, pred
, dt
, gimple
);
3583 /* Lower the main simplifiers and generate code for them. */
3584 lower (p
.simplifiers
, gimple
);
3587 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3588 print_matches (p
.simplifiers
[i
]);
3591 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3592 dt
.insert (p
.simplifiers
[i
], i
);
3598 dt
.gen_gimple (stdout
);
3600 dt
.gen_generic (stdout
);
3603 cpp_finish (r
, NULL
);