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 static struct line_maps
*line_table
;
51 #if GCC_VERSION >= 4001
52 __attribute__((format (printf
, 6, 0)))
54 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
55 unsigned int, const char *msg
, va_list *ap
)
57 const line_map_ordinary
*map
;
58 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
59 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
60 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
61 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
62 vfprintf (stderr
, msg
, *ap
);
63 fprintf (stderr
, "\n");
64 FILE *f
= fopen (loc
.file
, "r");
70 if (!fgets (buf
, 128, f
))
72 if (buf
[strlen (buf
) - 1] != '\n')
79 fprintf (stderr
, "%s", buf
);
80 for (int i
= 0; i
< loc
.column
- 1; ++i
)
88 if (errtype
== CPP_DL_FATAL
)
94 #if GCC_VERSION >= 4001
95 __attribute__((format (printf
, 2, 3)))
97 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
101 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
106 #if GCC_VERSION >= 4001
107 __attribute__((format (printf
, 2, 3)))
109 fatal_at (source_location loc
, const char *msg
, ...)
113 error_cb (NULL
, CPP_DL_FATAL
, 0, loc
, 0, msg
, &ap
);
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 warning_at (const cpp_token
*tk
, const char *msg
, ...)
125 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
130 output_line_directive (FILE *f
, source_location location
,
131 bool dumpfile
= false)
133 const line_map_ordinary
*map
;
134 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
135 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
138 /* When writing to a dumpfile only dump the filename. */
139 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
144 fprintf (f
, "%s:%d", file
, loc
.line
);
147 /* Other gen programs really output line directives here, at least for
148 development it's right now more convenient to have line information
149 from the generated file. Still keep the directives as comment for now
150 to easily back-point to the meta-description. */
151 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
155 /* Pull in tree codes and builtin function codes from their
158 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
171 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
172 enum built_in_function
{
173 #include "builtins.def"
179 /* Base class for all identifiers the parser knows. */
181 struct id_base
: nofree_ptr_hash
<id_base
>
183 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
185 id_base (id_kind
, const char *, int = -1);
191 /* hash_table support. */
192 static inline hashval_t
hash (const id_base
*);
193 static inline int equal (const id_base
*, const id_base
*);
197 id_base::hash (const id_base
*op
)
203 id_base::equal (const id_base
*op1
,
206 return (op1
->hashval
== op2
->hashval
207 && strcmp (op1
->id
, op2
->id
) == 0);
210 /* Hashtable of known pattern operators. This is pre-seeded from
211 all known tree codes and all known builtin function ids. */
212 static hash_table
<id_base
> *operators
;
214 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
219 hashval
= htab_hash_string (id
);
222 /* Identifier that maps to a tree code. */
224 struct operator_id
: public id_base
226 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
228 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
233 /* Identifier that maps to a builtin function code. */
235 struct fn_id
: public id_base
237 fn_id (enum built_in_function fn_
, const char *id_
)
238 : id_base (id_base::FN
, id_
), fn (fn_
) {}
239 enum built_in_function fn
;
244 /* Identifier that maps to a user-defined predicate. */
246 struct predicate_id
: public id_base
248 predicate_id (const char *id_
)
249 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
250 vec
<simplify
*> matchers
;
253 /* Identifier that maps to a operator defined by a 'for' directive. */
255 struct user_id
: public id_base
257 user_id (const char *id_
, bool is_oper_list_
= false)
258 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
259 used (false), is_oper_list (is_oper_list_
) {}
260 vec
<id_base
*> substitutes
;
268 is_a_helper
<fn_id
*>::test (id_base
*id
)
270 return id
->kind
== id_base::FN
;
276 is_a_helper
<operator_id
*>::test (id_base
*id
)
278 return id
->kind
== id_base::CODE
;
284 is_a_helper
<predicate_id
*>::test (id_base
*id
)
286 return id
->kind
== id_base::PREDICATE
;
292 is_a_helper
<user_id
*>::test (id_base
*id
)
294 return id
->kind
== id_base::USER
;
297 /* Add a predicate identifier to the hash. */
299 static predicate_id
*
300 add_predicate (const char *id
)
302 predicate_id
*p
= new predicate_id (id
);
303 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
305 fatal ("duplicate id definition");
310 /* Add a tree code identifier to the hash. */
313 add_operator (enum tree_code code
, const char *id
,
314 const char *tcc
, unsigned nargs
)
316 if (strcmp (tcc
, "tcc_unary") != 0
317 && strcmp (tcc
, "tcc_binary") != 0
318 && strcmp (tcc
, "tcc_comparison") != 0
319 && strcmp (tcc
, "tcc_expression") != 0
320 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
321 && strcmp (tcc
, "tcc_reference") != 0
322 /* To have INTEGER_CST and friends as "predicate operators". */
323 && strcmp (tcc
, "tcc_constant") != 0
324 /* And allow CONSTRUCTOR for vector initializers. */
325 && !(code
== CONSTRUCTOR
))
327 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
328 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
330 fatal ("duplicate id definition");
334 /* Add a builtin identifier to the hash. */
337 add_builtin (enum built_in_function code
, const char *id
)
339 fn_id
*fn
= new fn_id (code
, id
);
340 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
342 fatal ("duplicate id definition");
346 /* Helper for easy comparing ID with tree code CODE. */
349 operator==(id_base
&id
, enum tree_code code
)
351 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
352 return oid
->code
== code
;
356 /* Lookup the identifier ID. */
359 get_operator (const char *id
)
361 id_base
tem (id_base::CODE
, id
);
363 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
366 /* If this is a user-defined identifier track whether it was used. */
367 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
372 /* Try all-uppercase. */
373 char *id2
= xstrdup (id
);
374 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
375 id2
[i
] = TOUPPER (id2
[i
]);
376 new (&tem
) id_base (id_base::CODE
, id2
);
377 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
384 /* Try _EXPR appended. */
385 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
386 strcat (id2
, "_EXPR");
387 new (&tem
) id_base (id_base::CODE
, id2
);
388 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
398 typedef simple_hashmap_traits
<nofree_string_hash
> capture_id_map_hasher
;
400 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
403 /* The AST produced by parsing of the pattern definitions. */
408 /* The base class for operands. */
411 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
412 operand (enum op_type type_
) : type (type_
) {}
414 virtual void gen_transform (FILE *, const char *, bool, int,
415 const char *, capture_info
*,
418 { gcc_unreachable (); }
421 /* A predicate operand. Predicates are leafs in the AST. */
423 struct predicate
: public operand
425 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
429 /* An operand that constitutes an expression. Expressions include
430 function calls and user-defined predicate invocations. */
432 struct expr
: public operand
434 expr (id_base
*operation_
, bool is_commutative_
= false)
435 : operand (OP_EXPR
), operation (operation_
),
436 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
437 is_generic (false) {}
438 void append_op (operand
*op
) { ops
.safe_push (op
); }
439 /* The operator and its operands. */
442 /* An explicitely specified type - used exclusively for conversions. */
443 const char *expr_type
;
444 /* Whether the operation is to be applied commutatively. This is
445 later lowered to two separate patterns. */
447 /* Whether the expression is expected to be in GENERIC form. */
449 virtual void gen_transform (FILE *f
, const char *, bool, int,
450 const char *, capture_info
*,
451 dt_operand
** = 0, bool = true);
454 /* An operator that is represented by native C code. This is always
455 a leaf operand in the AST. This class is also used to represent
456 the code to be generated for 'if' and 'with' expressions. */
458 struct c_expr
: public operand
460 /* A mapping of an identifier and its replacement. Used to apply
465 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
468 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
469 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
470 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
471 nr_stmts (nr_stmts_
), ids (ids_
) {}
472 /* cpplib tokens and state to transform this back to source. */
475 cid_map_t
*capture_ids
;
476 /* The number of statements parsed (well, the number of ';'s). */
478 /* The identifier replacement vector. */
480 virtual void gen_transform (FILE *f
, const char *, bool, int,
481 const char *, capture_info
*,
482 dt_operand
** = 0, bool = true);
485 /* A wrapper around another operand that captures its value. */
487 struct capture
: public operand
489 capture (unsigned where_
, operand
*what_
)
490 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
491 /* Identifier index for the value. */
493 /* The captured value. */
495 virtual void gen_transform (FILE *f
, const char *, bool, int,
496 const char *, capture_info
*,
497 dt_operand
** = 0, bool = true);
503 is_a_helper
<capture
*>::test (operand
*op
)
505 return op
->type
== operand::OP_CAPTURE
;
511 is_a_helper
<predicate
*>::test (operand
*op
)
513 return op
->type
== operand::OP_PREDICATE
;
519 is_a_helper
<c_expr
*>::test (operand
*op
)
521 return op
->type
== operand::OP_C_EXPR
;
527 is_a_helper
<expr
*>::test (operand
*op
)
529 return op
->type
== operand::OP_EXPR
;
532 /* Helper to distinguish 'if' from 'with' expressions. */
536 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
537 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
538 source_location location
;
543 /* The main class of a pattern and its transform. This is used to
544 represent both (simplify ...) and (match ...) kinds. The AST
545 duplicates all outer 'if' and 'for' expressions here so each
546 simplify can exist in isolation. */
550 simplify (operand
*match_
, source_location match_location_
,
551 struct operand
*result_
, source_location result_location_
,
552 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
553 cid_map_t
*capture_ids_
)
554 : match (match_
), match_location (match_location_
),
555 result (result_
), result_location (result_location_
),
556 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
557 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
559 /* The expression that is matched against the GENERIC or GIMPLE IL. */
561 source_location match_location
;
562 /* For a (simplify ...) the expression produced when the pattern applies.
563 For a (match ...) either NULL if it is a simple predicate or the
564 single expression specifying the matched operands. */
565 struct operand
*result
;
566 source_location result_location
;
567 /* Collected 'if' expressions that need to evaluate to true to make
568 the pattern apply. */
569 vec
<if_or_with
> ifexpr_vec
;
570 /* Collected 'for' expression operators that have to be replaced
571 in the lowering phase. */
572 vec
<vec
<user_id
*> > for_vec
;
573 /* A map of capture identifiers to indexes. */
574 cid_map_t
*capture_ids
;
578 /* Debugging routines for dumping the AST. */
581 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
583 if (capture
*c
= dyn_cast
<capture
*> (o
))
585 fprintf (f
, "@%u", c
->where
);
586 if (c
->what
&& flattened
== false)
589 print_operand (c
->what
, f
, flattened
);
594 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
595 fprintf (f
, "%s", p
->p
->id
);
597 else if (is_a
<c_expr
*> (o
))
598 fprintf (f
, "c_expr");
600 else if (expr
*e
= dyn_cast
<expr
*> (o
))
602 fprintf (f
, "(%s", e
->operation
->id
);
604 if (flattened
== false)
607 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
609 print_operand (e
->ops
[i
], f
, flattened
);
621 print_matches (struct simplify
*s
, FILE *f
= stderr
)
623 fprintf (f
, "for expression: ");
624 print_operand (s
->match
, f
);
631 /* Lowering of commutative operators. */
634 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
635 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
637 if (n
== ops_vector
.length ())
639 vec
<operand
*> xv
= v
.copy ();
640 result
.safe_push (xv
);
644 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
646 v
[n
] = ops_vector
[n
][i
];
647 cartesian_product (ops_vector
, result
, v
, n
+ 1);
651 /* Lower OP to two operands in case it is marked as commutative. */
653 static vec
<operand
*>
654 commutate (operand
*op
)
656 vec
<operand
*> ret
= vNULL
;
658 if (capture
*c
= dyn_cast
<capture
*> (op
))
665 vec
<operand
*> v
= commutate (c
->what
);
666 for (unsigned i
= 0; i
< v
.length (); ++i
)
668 capture
*nc
= new capture (c
->where
, v
[i
]);
674 expr
*e
= dyn_cast
<expr
*> (op
);
675 if (!e
|| e
->ops
.length () == 0)
681 vec
< vec
<operand
*> > ops_vector
= vNULL
;
682 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
683 ops_vector
.safe_push (commutate (e
->ops
[i
]));
685 auto_vec
< vec
<operand
*> > result
;
686 auto_vec
<operand
*> v (e
->ops
.length ());
687 v
.quick_grow_cleared (e
->ops
.length ());
688 cartesian_product (ops_vector
, result
, v
, 0);
691 for (unsigned i
= 0; i
< result
.length (); ++i
)
693 expr
*ne
= new expr (e
->operation
);
694 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
695 ne
->append_op (result
[i
][j
]);
699 if (!e
->is_commutative
)
702 for (unsigned i
= 0; i
< result
.length (); ++i
)
704 expr
*ne
= new expr (e
->operation
);
705 // result[i].length () is 2 since e->operation is binary
706 for (unsigned j
= result
[i
].length (); j
; --j
)
707 ne
->append_op (result
[i
][j
-1]);
714 /* Lower operations marked as commutative in the AST of S and push
715 the resulting patterns to SIMPLIFIERS. */
718 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
720 vec
<operand
*> matchers
= commutate (s
->match
);
721 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
723 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
724 s
->result
, s
->result_location
, s
->ifexpr_vec
,
725 s
->for_vec
, s
->capture_ids
);
726 simplifiers
.safe_push (ns
);
730 /* Strip conditional conversios using operator OPER from O and its
731 children if STRIP, else replace them with an unconditional convert. */
734 lower_opt_convert (operand
*o
, enum tree_code oper
,
735 enum tree_code to_oper
, bool strip
)
737 if (capture
*c
= dyn_cast
<capture
*> (o
))
740 return new capture (c
->where
,
741 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
746 expr
*e
= dyn_cast
<expr
*> (o
);
750 if (*e
->operation
== oper
)
753 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
755 expr
*ne
= new expr (to_oper
== CONVERT_EXPR
756 ? get_operator ("CONVERT_EXPR")
757 : get_operator ("VIEW_CONVERT_EXPR"));
758 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
762 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
763 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
764 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
769 /* Determine whether O or its children uses the conditional conversion
773 has_opt_convert (operand
*o
, enum tree_code oper
)
775 if (capture
*c
= dyn_cast
<capture
*> (o
))
778 return has_opt_convert (c
->what
, oper
);
783 expr
*e
= dyn_cast
<expr
*> (o
);
787 if (*e
->operation
== oper
)
790 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
791 if (has_opt_convert (e
->ops
[i
], oper
))
797 /* Lower conditional convert operators in O, expanding it to a vector
800 static vec
<operand
*>
801 lower_opt_convert (operand
*o
)
803 vec
<operand
*> v1
= vNULL
, v2
;
807 enum tree_code opers
[]
808 = { CONVERT0
, CONVERT_EXPR
,
809 CONVERT1
, CONVERT_EXPR
,
810 CONVERT2
, CONVERT_EXPR
,
811 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
812 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
813 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
815 /* Conditional converts are lowered to a pattern with the
816 conversion and one without. The three different conditional
817 convert codes are lowered separately. */
819 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
822 for (unsigned j
= 0; j
< v1
.length (); ++j
)
823 if (has_opt_convert (v1
[j
], opers
[i
]))
825 v2
.safe_push (lower_opt_convert (v1
[j
],
826 opers
[i
], opers
[i
+1], false));
827 v2
.safe_push (lower_opt_convert (v1
[j
],
828 opers
[i
], opers
[i
+1], true));
834 for (unsigned j
= 0; j
< v2
.length (); ++j
)
835 v1
.safe_push (v2
[j
]);
842 /* Lower conditional convert operators in the AST of S and push
843 the resulting multiple patterns to SIMPLIFIERS. */
846 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
848 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
849 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
851 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
852 s
->result
, s
->result_location
, s
->ifexpr_vec
,
853 s
->for_vec
, s
->capture_ids
);
854 simplifiers
.safe_push (ns
);
858 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
859 GENERIC and a GIMPLE variant. */
861 static vec
<operand
*>
862 lower_cond (operand
*o
)
864 vec
<operand
*> ro
= vNULL
;
866 if (capture
*c
= dyn_cast
<capture
*> (o
))
870 vec
<operand
*> lop
= vNULL
;
871 lop
= lower_cond (c
->what
);
873 for (unsigned i
= 0; i
< lop
.length (); ++i
)
874 ro
.safe_push (new capture (c
->where
, lop
[i
]));
879 expr
*e
= dyn_cast
<expr
*> (o
);
880 if (!e
|| e
->ops
.length () == 0)
886 vec
< vec
<operand
*> > ops_vector
= vNULL
;
887 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
888 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
890 auto_vec
< vec
<operand
*> > result
;
891 auto_vec
<operand
*> v (e
->ops
.length ());
892 v
.quick_grow_cleared (e
->ops
.length ());
893 cartesian_product (ops_vector
, result
, v
, 0);
895 for (unsigned i
= 0; i
< result
.length (); ++i
)
897 expr
*ne
= new expr (e
->operation
);
898 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
899 ne
->append_op (result
[i
][j
]);
901 /* If this is a COND with a captured expression or an
902 expression with two operands then also match a GENERIC
903 form on the compare. */
904 if ((*e
->operation
== COND_EXPR
905 || *e
->operation
== VEC_COND_EXPR
)
906 && ((is_a
<capture
*> (e
->ops
[0])
907 && as_a
<capture
*> (e
->ops
[0])->what
908 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
910 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
911 || (is_a
<expr
*> (e
->ops
[0])
912 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
914 expr
*ne
= new expr (e
->operation
);
915 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
916 ne
->append_op (result
[i
][j
]);
917 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
919 expr
*ocmp
= as_a
<expr
*> (c
->what
);
920 expr
*cmp
= new expr (ocmp
->operation
);
921 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
922 cmp
->append_op (ocmp
->ops
[j
]);
923 cmp
->is_generic
= true;
924 ne
->ops
[0] = new capture (c
->where
, cmp
);
928 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
929 expr
*cmp
= new expr (ocmp
->operation
);
930 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
931 cmp
->append_op (ocmp
->ops
[j
]);
932 cmp
->is_generic
= true;
942 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
943 GENERIC and a GIMPLE variant. */
946 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
948 vec
<operand
*> matchers
= lower_cond (s
->match
);
949 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
951 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
952 s
->result
, s
->result_location
, s
->ifexpr_vec
,
953 s
->for_vec
, s
->capture_ids
);
954 simplifiers
.safe_push (ns
);
958 /* In AST operand O replace operator ID with operator WITH. */
961 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
963 /* Deep-copy captures and expressions, replacing operations as
965 if (capture
*c
= dyn_cast
<capture
*> (o
))
969 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
971 else if (expr
*e
= dyn_cast
<expr
*> (o
))
973 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
975 ne
->expr_type
= e
->expr_type
;
976 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
977 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
981 /* For c_expr we simply record a string replacement table which is
982 applied at code-generation time. */
983 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
985 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
986 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
987 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
993 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
996 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
998 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
999 unsigned worklist_start
= 0;
1000 auto_vec
<simplify
*> worklist
;
1001 worklist
.safe_push (sin
);
1003 /* Lower each recorded for separately, operating on the
1004 set of simplifiers created by the previous one.
1005 Lower inner-to-outer so inner for substitutes can refer
1006 to operators replaced by outer fors. */
1007 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1009 vec
<user_id
*>& ids
= for_vec
[fi
];
1010 unsigned n_ids
= ids
.length ();
1011 unsigned max_n_opers
= 0;
1012 for (unsigned i
= 0; i
< n_ids
; ++i
)
1013 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1014 max_n_opers
= ids
[i
]->substitutes
.length ();
1016 unsigned worklist_end
= worklist
.length ();
1017 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1019 simplify
*s
= worklist
[si
];
1020 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1022 operand
*match_op
= s
->match
;
1023 operand
*result_op
= s
->result
;
1024 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1026 for (unsigned i
= 0; i
< n_ids
; ++i
)
1028 user_id
*id
= ids
[i
];
1029 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1030 match_op
= replace_id (match_op
, id
, oper
);
1032 result_op
= replace_id (result_op
, id
, oper
);
1033 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1034 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1037 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1038 result_op
, s
->result_location
,
1039 ifexpr_vec
, vNULL
, s
->capture_ids
);
1040 worklist
.safe_push (ns
);
1043 worklist_start
= worklist_end
;
1046 /* Copy out the result from the last for lowering. */
1047 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1048 simplifiers
.safe_push (worklist
[i
]);
1051 /* Lower the AST for everything in SIMPLIFIERS. */
1054 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1056 auto_vec
<simplify
*> out_simplifiers
;
1057 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1058 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1060 simplifiers
.truncate (0);
1061 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1062 lower_commutative (out_simplifiers
[i
], simplifiers
);
1064 out_simplifiers
.truncate (0);
1066 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1067 lower_cond (simplifiers
[i
], out_simplifiers
);
1069 out_simplifiers
.safe_splice (simplifiers
);
1072 simplifiers
.truncate (0);
1073 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1074 lower_for (out_simplifiers
[i
], simplifiers
);
1080 /* The decision tree built for generating GIMPLE and GENERIC pattern
1081 matching code. It represents the 'match' expression of all
1082 simplifies and has those as its leafs. */
1084 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1088 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1092 vec
<dt_node
*> kids
;
1094 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1096 dt_node
*append_node (dt_node
*);
1097 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1098 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1099 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1100 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1102 virtual void gen (FILE *, bool) {}
1104 void gen_kids (FILE *, bool);
1105 void gen_kids_1 (FILE *, bool,
1106 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1107 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1110 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1112 struct dt_operand
: public dt_node
1115 dt_operand
*match_dop
;
1119 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1120 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1121 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1122 parent (parent_
), pos (pos_
) {}
1124 void gen (FILE *, bool);
1125 unsigned gen_predicate (FILE *, const char *, bool);
1126 unsigned gen_match_op (FILE *, const char *);
1128 unsigned gen_gimple_expr (FILE *);
1129 unsigned gen_generic_expr (FILE *, const char *);
1131 char *get_name (char *);
1132 void gen_opname (char *, unsigned);
1135 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1137 struct dt_simplify
: public dt_node
1140 unsigned pattern_no
;
1141 dt_operand
**indexes
;
1143 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1144 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1145 indexes (indexes_
) {}
1147 void gen (FILE *f
, bool);
1153 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1155 return (n
->type
== dt_node::DT_OPERAND
1156 || n
->type
== dt_node::DT_MATCH
);
1159 /* A container for the actual decision tree. */
1161 struct decision_tree
1165 void insert (struct simplify
*, unsigned);
1166 void gen_gimple (FILE *f
= stderr
);
1167 void gen_generic (FILE *f
= stderr
);
1168 void print (FILE *f
= stderr
);
1170 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1172 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1173 unsigned pos
= 0, dt_node
*parent
= 0);
1174 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1175 static bool cmp_node (dt_node
*, dt_node
*);
1176 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1179 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1182 cmp_operand (operand
*o1
, operand
*o2
)
1184 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1187 if (o1
->type
== operand::OP_PREDICATE
)
1189 predicate
*p1
= as_a
<predicate
*>(o1
);
1190 predicate
*p2
= as_a
<predicate
*>(o2
);
1191 return p1
->p
== p2
->p
;
1193 else if (o1
->type
== operand::OP_EXPR
)
1195 expr
*e1
= static_cast<expr
*>(o1
);
1196 expr
*e2
= static_cast<expr
*>(o2
);
1197 return (e1
->operation
== e2
->operation
1198 && e1
->is_generic
== e2
->is_generic
);
1204 /* Compare two decision tree nodes N1 and N2 and return true if they
1208 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1210 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1216 if (n1
->type
== dt_node::DT_TRUE
)
1219 if (n1
->type
== dt_node::DT_OPERAND
)
1220 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1221 (as_a
<dt_operand
*> (n2
))->op
);
1222 else if (n1
->type
== dt_node::DT_MATCH
)
1223 return ((as_a
<dt_operand
*> (n1
))->match_dop
1224 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1228 /* Search OPS for a decision tree node like P and return it if found. */
1231 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1233 /* We can merge adjacent DT_TRUE. */
1234 if (p
->type
== dt_node::DT_TRUE
1236 && ops
.last ()->type
== dt_node::DT_TRUE
)
1238 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1240 /* But we can't merge across DT_TRUE nodes as they serve as
1241 pattern order barriers to make sure that patterns apply
1242 in order of appearance in case multiple matches are possible. */
1243 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1245 if (decision_tree::cmp_node (ops
[i
], p
))
1251 /* Append N to the decision tree if it there is not already an existing
1255 dt_node::append_node (dt_node
*n
)
1259 kid
= decision_tree::find_node (kids
, n
);
1264 n
->level
= this->level
+ 1;
1269 /* Append OP to the decision tree. */
1272 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1274 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1275 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1276 return append_node (n
);
1279 /* Append a DT_TRUE decision tree node. */
1282 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1284 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1285 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1286 return append_node (n
);
1289 /* Append a DT_MATCH decision tree node. */
1292 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1294 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1295 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1296 return append_node (n
);
1299 /* Append S to the decision tree. */
1302 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1303 dt_operand
**indexes
)
1305 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1306 return append_node (n
);
1309 /* Insert O into the decision tree and return the decision tree node found
1313 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1314 unsigned pos
, dt_node
*parent
)
1316 dt_node
*q
, *elm
= 0;
1318 if (capture
*c
= dyn_cast
<capture
*> (o
))
1320 unsigned capt_index
= c
->where
;
1322 if (indexes
[capt_index
] == 0)
1325 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1328 q
= elm
= p
->append_true_op (parent
, pos
);
1331 // get to the last capture
1332 for (operand
*what
= c
->what
;
1333 what
&& is_a
<capture
*> (what
);
1334 c
= as_a
<capture
*> (what
), what
= c
->what
)
1339 unsigned cc_index
= c
->where
;
1340 dt_operand
*match_op
= indexes
[cc_index
];
1342 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1343 elm
= decision_tree::find_node (p
->kids
, &temp
);
1347 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1348 elm
= decision_tree::find_node (p
->kids
, &temp
);
1353 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1354 elm
= decision_tree::find_node (p
->kids
, &temp
);
1358 gcc_assert (elm
->type
== dt_node::DT_TRUE
1359 || elm
->type
== dt_node::DT_OPERAND
1360 || elm
->type
== dt_node::DT_MATCH
);
1361 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1366 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1368 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1373 p
= p
->append_op (o
, parent
, pos
);
1376 if (expr
*e
= dyn_cast
<expr
*>(o
))
1378 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1379 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1385 /* Insert S into the decision tree. */
1388 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1390 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1391 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1392 p
->append_simplify (s
, pattern_no
, indexes
);
1395 /* Debug functions to dump the decision tree. */
1398 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1400 if (p
->type
== dt_node::DT_NODE
)
1401 fprintf (f
, "root");
1405 for (unsigned i
= 0; i
< indent
; i
++)
1408 if (p
->type
== dt_node::DT_OPERAND
)
1410 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1411 print_operand (dop
->op
, f
, true);
1413 else if (p
->type
== dt_node::DT_TRUE
)
1414 fprintf (f
, "true");
1415 else if (p
->type
== dt_node::DT_MATCH
)
1416 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1417 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1419 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1420 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1421 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1422 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1427 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1429 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1430 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1434 decision_tree::print (FILE *f
)
1436 return decision_tree::print_node (root
, f
);
1440 /* For GENERIC we have to take care of wrapping multiple-used
1441 expressions with side-effects in save_expr and preserve side-effects
1442 of expressions with omit_one_operand. Analyze captures in
1443 match, result and with expressions and perform early-outs
1444 on the outermost match expression operands for cases we cannot
1449 capture_info (simplify
*s
);
1450 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1451 void walk_result (operand
*o
, bool);
1452 void walk_c_expr (c_expr
*);
1458 bool force_no_side_effects_p
;
1459 bool cond_expr_cond_p
;
1460 unsigned long toplevel_msk
;
1461 int result_use_count
;
1464 auto_vec
<cinfo
> info
;
1465 unsigned long force_no_side_effects
;
1468 /* Analyze captures in S. */
1470 capture_info::capture_info (simplify
*s
)
1474 || ((e
= dyn_cast
<expr
*> (s
->result
))
1475 && is_a
<predicate_id
*> (e
->operation
)))
1477 force_no_side_effects
= -1;
1481 force_no_side_effects
= 0;
1482 info
.safe_grow_cleared (s
->capture_max
+ 1);
1483 e
= as_a
<expr
*> (s
->match
);
1484 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1485 walk_match (e
->ops
[i
], i
,
1486 (i
!= 0 && *e
->operation
== COND_EXPR
)
1487 || *e
->operation
== TRUTH_ANDIF_EXPR
1488 || *e
->operation
== TRUTH_ORIF_EXPR
,
1490 && (*e
->operation
== COND_EXPR
1491 || *e
->operation
== VEC_COND_EXPR
));
1493 walk_result (s
->result
, false);
1495 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1496 if (s
->ifexpr_vec
[i
].is_with
)
1497 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1500 /* Analyze captures in the match expression piece O. */
1503 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1504 bool conditional_p
, bool cond_expr_cond_p
)
1506 if (capture
*c
= dyn_cast
<capture
*> (o
))
1508 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1509 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1510 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1511 /* Mark expr (non-leaf) captures and recurse. */
1513 && is_a
<expr
*> (c
->what
))
1515 info
[c
->where
].expr_p
= true;
1516 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1519 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1521 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1523 bool cond_p
= conditional_p
;
1524 bool cond_expr_cond_p
= false;
1525 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1527 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1528 || *e
->operation
== TRUTH_ORIF_EXPR
)
1531 && (*e
->operation
== COND_EXPR
1532 || *e
->operation
== VEC_COND_EXPR
))
1533 cond_expr_cond_p
= true;
1534 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1537 else if (is_a
<predicate
*> (o
))
1539 /* Mark non-captured leafs toplevel arg for checking. */
1540 force_no_side_effects
|= 1 << toplevel_arg
;
1546 /* Analyze captures in the result expression piece O. */
1549 capture_info::walk_result (operand
*o
, bool conditional_p
)
1551 if (capture
*c
= dyn_cast
<capture
*> (o
))
1553 info
[c
->where
].result_use_count
++;
1554 /* If we substitute an expression capture we don't know
1555 which captures this will end up using (well, we don't
1556 compute that). Force the uses to be side-effect free
1557 which means forcing the toplevels that reach the
1558 expression side-effect free. */
1559 if (info
[c
->where
].expr_p
)
1560 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1561 /* Mark CSE capture capture uses as forced to have
1564 && is_a
<expr
*> (c
->what
))
1566 info
[c
->where
].cse_p
= true;
1567 walk_result (c
->what
, true);
1570 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1572 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1574 bool cond_p
= conditional_p
;
1575 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1577 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1578 || *e
->operation
== TRUTH_ORIF_EXPR
)
1580 walk_result (e
->ops
[i
], cond_p
);
1583 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1589 /* Look for captures in the C expr E. */
1592 capture_info::walk_c_expr (c_expr
*e
)
1594 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1595 unsigned p_depth
= 0;
1596 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1598 const cpp_token
*t
= &e
->code
[i
];
1599 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1600 if (t
->type
== CPP_NAME
1601 && strcmp ((const char *)CPP_HASHNODE
1602 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1603 && n
->type
== CPP_OPEN_PAREN
)
1605 else if (t
->type
== CPP_CLOSE_PAREN
1608 else if (p_depth
== 0
1609 && t
->type
== CPP_ATSIGN
1610 && (n
->type
== CPP_NUMBER
1611 || n
->type
== CPP_NAME
)
1612 && !(n
->flags
& PREV_WHITE
))
1615 if (n
->type
== CPP_NUMBER
)
1616 id
= (const char *)n
->val
.str
.text
;
1618 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1619 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1625 /* Code generation off the decision tree and the refered AST nodes. */
1628 is_conversion (id_base
*op
)
1630 return (*op
== CONVERT_EXPR
1632 || *op
== FLOAT_EXPR
1633 || *op
== FIX_TRUNC_EXPR
1634 || *op
== VIEW_CONVERT_EXPR
);
1637 /* Get the type to be used for generating operands of OP from the
1641 get_operand_type (id_base
*op
, const char *in_type
,
1642 const char *expr_type
,
1643 const char *other_oprnd_type
)
1645 /* Generally operands whose type does not match the type of the
1646 expression generated need to know their types but match and
1647 thus can fall back to 'other_oprnd_type'. */
1648 if (is_conversion (op
))
1649 return other_oprnd_type
;
1650 else if (*op
== REALPART_EXPR
1651 || *op
== IMAGPART_EXPR
)
1652 return other_oprnd_type
;
1653 else if (is_a
<operator_id
*> (op
)
1654 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1655 return other_oprnd_type
;
1658 /* Otherwise all types should match - choose one in order of
1665 return other_oprnd_type
;
1669 /* Generate transform code for an expression. */
1672 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1673 const char *in_type
, capture_info
*cinfo
,
1674 dt_operand
**indexes
, bool)
1676 bool conversion_p
= is_conversion (operation
);
1677 const char *type
= expr_type
;
1680 /* If there was a type specification in the pattern use it. */
1682 else if (conversion_p
)
1683 /* For conversions we need to build the expression using the
1684 outer type passed in. */
1686 else if (*operation
== REALPART_EXPR
1687 || *operation
== IMAGPART_EXPR
)
1689 /* __real and __imag use the component type of its operand. */
1690 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1693 else if (is_a
<operator_id
*> (operation
)
1694 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1696 /* comparisons use boolean_type_node (or what gets in), but
1697 their operands need to figure out the types themselves. */
1698 sprintf (optype
, "boolean_type_node");
1701 else if (*operation
== COND_EXPR
1702 || *operation
== VEC_COND_EXPR
)
1704 /* Conditions are of the same type as their first alternative. */
1705 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1710 /* Other operations are of the same type as their first operand. */
1711 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1715 fatal ("two conversions in a row");
1718 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1720 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1721 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1724 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1726 = get_operand_type (operation
, in_type
, expr_type
,
1727 i
== 0 ? NULL
: op0type
);
1728 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1729 ((!(*operation
== COND_EXPR
)
1730 && !(*operation
== VEC_COND_EXPR
))
1735 if (*operation
== CONVERT_EXPR
)
1738 opr
= operation
->id
;
1742 /* ??? Building a stmt can fail for various reasons here, seq being
1743 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1744 So if we fail here we should continue matching other patterns. */
1745 fprintf (f
, " code_helper tem_code = %s;\n"
1746 " tree tem_ops[3] = { ", opr
);
1747 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1748 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1749 i
== ops
.length () - 1 ? " };\n" : ", ");
1750 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1751 ops
.length (), type
);
1752 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1753 " if (!res) return false;\n", type
);
1757 if (operation
->kind
== id_base::CODE
)
1758 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1759 ops
.length(), opr
, type
);
1761 fprintf (f
, " res = build_call_expr_loc (loc, "
1762 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1763 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1764 fprintf (f
, ", ops%d[%u]", depth
, i
);
1765 fprintf (f
, ");\n");
1767 fprintf (f
, "%s = res;\n", dest
);
1771 /* Generate code for a c_expr which is either the expression inside
1772 an if statement or a sequence of statements which computes a
1773 result to be stored to DEST. */
1776 c_expr::gen_transform (FILE *f
, const char *dest
,
1777 bool, int, const char *, capture_info
*,
1778 dt_operand
**, bool)
1780 if (dest
&& nr_stmts
== 1)
1781 fprintf (f
, "%s = ", dest
);
1783 unsigned stmt_nr
= 1;
1784 for (unsigned i
= 0; i
< code
.length (); ++i
)
1786 const cpp_token
*token
= &code
[i
];
1788 /* Replace captures for code-gen. */
1789 if (token
->type
== CPP_ATSIGN
)
1791 const cpp_token
*n
= &code
[i
+1];
1792 if ((n
->type
== CPP_NUMBER
1793 || n
->type
== CPP_NAME
)
1794 && !(n
->flags
& PREV_WHITE
))
1796 if (token
->flags
& PREV_WHITE
)
1799 if (n
->type
== CPP_NUMBER
)
1800 id
= (const char *)n
->val
.str
.text
;
1802 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1803 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1809 if (token
->flags
& PREV_WHITE
)
1812 if (token
->type
== CPP_NAME
)
1814 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1816 for (j
= 0; j
< ids
.length (); ++j
)
1818 if (strcmp (id
, ids
[j
].id
) == 0)
1820 fprintf (f
, "%s", ids
[j
].oper
);
1824 if (j
< ids
.length ())
1828 /* Output the token as string. */
1829 char *tk
= (char *)cpp_token_as_text (r
, token
);
1832 if (token
->type
== CPP_SEMICOLON
)
1835 if (dest
&& stmt_nr
== nr_stmts
)
1836 fprintf (f
, "\n %s = ", dest
);
1843 /* Generate transform code for a capture. */
1846 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1847 const char *in_type
, capture_info
*cinfo
,
1848 dt_operand
**indexes
, bool expand_compares
)
1850 if (what
&& is_a
<expr
*> (what
))
1852 if (indexes
[where
] == 0)
1855 sprintf (buf
, "captures[%u]", where
);
1856 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1860 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1862 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1863 with substituting a capture of that.
1864 ??? Returning false here will also not allow any other patterns
1866 if (gimple
&& expand_compares
1867 && cinfo
->info
[where
].cond_expr_cond_p
)
1868 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1870 " if (!seq) return false;\n"
1871 " %s = gimple_build (seq, TREE_CODE (%s),"
1872 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1873 " TREE_OPERAND (%s, 1));\n"
1874 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1877 /* Return the name of the operand representing the decision tree node.
1878 Use NAME as space to generate it. */
1881 dt_operand::get_name (char *name
)
1884 sprintf (name
, "t");
1885 else if (parent
->level
== 1)
1886 sprintf (name
, "op%u", pos
);
1887 else if (parent
->type
== dt_node::DT_MATCH
)
1888 return parent
->get_name (name
);
1890 sprintf (name
, "o%u%u", parent
->level
, pos
);
1894 /* Fill NAME with the operand name at position POS. */
1897 dt_operand::gen_opname (char *name
, unsigned pos
)
1900 sprintf (name
, "op%u", pos
);
1902 sprintf (name
, "o%u%u", level
, pos
);
1905 /* Generate matching code for the decision tree operand which is
1909 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1911 predicate
*p
= as_a
<predicate
*> (op
);
1913 if (p
->p
->matchers
.exists ())
1915 /* If this is a predicate generated from a pattern mangle its
1916 name and pass on the valueize hook. */
1918 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1920 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1923 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1928 /* Generate matching code for the decision tree operand which is
1932 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1934 char match_opname
[20];
1935 match_dop
->get_name (match_opname
);
1936 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1937 opname
, match_opname
, opname
, match_opname
);
1942 /* Generate GIMPLE matching code for the decision tree operand. */
1945 dt_operand::gen_gimple_expr (FILE *f
)
1947 expr
*e
= static_cast<expr
*> (op
);
1948 id_base
*id
= e
->operation
;
1949 unsigned n_ops
= e
->ops
.length ();
1951 for (unsigned i
= 0; i
< n_ops
; ++i
)
1953 char child_opname
[20];
1954 gen_opname (child_opname
, i
);
1956 if (id
->kind
== id_base::CODE
)
1959 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1960 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1962 /* ??? If this is a memory operation we can't (and should not)
1963 match this. The only sensible operand types are
1964 SSA names and invariants. */
1965 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1967 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1968 "|| is_gimple_min_invariant (%s))\n"
1969 "&& (%s = do_valueize (valueize, %s)))\n"
1970 "{\n", child_opname
, child_opname
, child_opname
,
1975 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1976 child_opname
, i
+ 1);
1979 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1981 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1982 child_opname
, child_opname
);
1989 /* Generate GENERIC matching code for the decision tree operand. */
1992 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1994 expr
*e
= static_cast<expr
*> (op
);
1995 unsigned n_ops
= e
->ops
.length ();
1997 for (unsigned i
= 0; i
< n_ops
; ++i
)
1999 char child_opname
[20];
2000 gen_opname (child_opname
, i
);
2002 if (e
->operation
->kind
== id_base::CODE
)
2003 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2004 child_opname
, opname
, i
);
2006 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2007 child_opname
, opname
, i
);
2013 /* Generate matching code for the children of the decision tree node. */
2016 dt_node::gen_kids (FILE *f
, bool gimple
)
2018 auto_vec
<dt_operand
*> gimple_exprs
;
2019 auto_vec
<dt_operand
*> generic_exprs
;
2020 auto_vec
<dt_operand
*> fns
;
2021 auto_vec
<dt_operand
*> generic_fns
;
2022 auto_vec
<dt_operand
*> preds
;
2023 auto_vec
<dt_node
*> others
;
2025 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2027 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2029 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2030 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2032 if (e
->ops
.length () == 0
2033 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2034 generic_exprs
.safe_push (op
);
2035 else if (e
->operation
->kind
== id_base::FN
)
2040 generic_fns
.safe_push (op
);
2042 else if (e
->operation
->kind
== id_base::PREDICATE
)
2043 preds
.safe_push (op
);
2047 gimple_exprs
.safe_push (op
);
2049 generic_exprs
.safe_push (op
);
2052 else if (op
->op
->type
== operand::OP_PREDICATE
)
2053 others
.safe_push (kids
[i
]);
2057 else if (kids
[i
]->type
== dt_node::DT_MATCH
2058 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2059 others
.safe_push (kids
[i
]);
2060 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2062 /* A DT_TRUE operand serves as a barrier - generate code now
2063 for what we have collected sofar. */
2064 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2065 fns
, generic_fns
, preds
, others
);
2066 /* And output the true operand itself. */
2067 kids
[i
]->gen (f
, gimple
);
2068 gimple_exprs
.truncate (0);
2069 generic_exprs
.truncate (0);
2071 generic_fns
.truncate (0);
2073 others
.truncate (0);
2079 /* Generate code for the remains. */
2080 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2081 fns
, generic_fns
, preds
, others
);
2084 /* Generate matching code for the children of the decision tree node. */
2087 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2088 vec
<dt_operand
*> gimple_exprs
,
2089 vec
<dt_operand
*> generic_exprs
,
2090 vec
<dt_operand
*> fns
,
2091 vec
<dt_operand
*> generic_fns
,
2092 vec
<dt_operand
*> preds
,
2093 vec
<dt_node
*> others
)
2096 char *kid_opname
= buf
;
2098 unsigned exprs_len
= gimple_exprs
.length ();
2099 unsigned gexprs_len
= generic_exprs
.length ();
2100 unsigned fns_len
= fns
.length ();
2101 unsigned gfns_len
= generic_fns
.length ();
2103 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2106 gimple_exprs
[0]->get_name (kid_opname
);
2108 fns
[0]->get_name (kid_opname
);
2110 generic_fns
[0]->get_name (kid_opname
);
2112 generic_exprs
[0]->get_name (kid_opname
);
2114 fprintf (f
, "switch (TREE_CODE (%s))\n"
2118 if (exprs_len
|| fns_len
)
2120 fprintf (f
, "case SSA_NAME:\n");
2121 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2123 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2127 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2128 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2130 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2132 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2133 id_base
*op
= e
->operation
;
2134 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2135 fprintf (f
, "CASE_CONVERT:\n");
2137 fprintf (f
, "case %s:\n", op
->id
);
2139 gimple_exprs
[i
]->gen (f
, true);
2140 fprintf (f
, "break;\n"
2143 fprintf (f
, "default:;\n"
2150 fprintf (f
, "else ");
2152 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2154 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2155 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2158 for (unsigned i
= 0; i
< fns_len
; ++i
)
2160 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2161 fprintf (f
, "case %s:\n"
2162 "{\n", e
->operation
->id
);
2163 fns
[i
]->gen (f
, true);
2164 fprintf (f
, "break;\n"
2168 fprintf (f
, "default:;\n"
2177 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2179 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2180 id_base
*op
= e
->operation
;
2181 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2182 fprintf (f
, "CASE_CONVERT:\n");
2184 fprintf (f
, "case %s:\n", op
->id
);
2186 generic_exprs
[i
]->gen (f
, gimple
);
2187 fprintf (f
, "break;\n"
2193 fprintf (f
, "case CALL_EXPR:\n"
2195 "tree fndecl = get_callee_fndecl (%s);\n"
2196 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2197 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2200 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2202 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2203 gcc_assert (e
->operation
->kind
== id_base::FN
);
2205 fprintf (f
, "case %s:\n"
2206 "{\n", e
->operation
->id
);
2207 generic_fns
[j
]->gen (f
, false);
2208 fprintf (f
, "break;\n"
2212 fprintf (f
, "default:;\n"
2218 /* Close switch (TREE_CODE ()). */
2219 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2220 fprintf (f
, "default:;\n"
2223 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2225 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2226 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2227 preds
[i
]->get_name (kid_opname
);
2228 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2229 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2230 gimple
? "gimple" : "tree",
2231 p
->id
, kid_opname
, kid_opname
,
2232 gimple
? ", valueize" : "");
2234 for (int j
= 0; j
< p
->nargs
; ++j
)
2236 char child_opname
[20];
2237 preds
[i
]->gen_opname (child_opname
, j
);
2238 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2240 preds
[i
]->gen_kids (f
, gimple
);
2244 for (unsigned i
= 0; i
< others
.length (); ++i
)
2245 others
[i
]->gen (f
, gimple
);
2248 /* Generate matching code for the decision tree operand. */
2251 dt_operand::gen (FILE *f
, bool gimple
)
2256 unsigned n_braces
= 0;
2258 if (type
== DT_OPERAND
)
2261 case operand::OP_PREDICATE
:
2262 n_braces
= gen_predicate (f
, opname
, gimple
);
2265 case operand::OP_EXPR
:
2267 n_braces
= gen_gimple_expr (f
);
2269 n_braces
= gen_generic_expr (f
, opname
);
2275 else if (type
== DT_TRUE
)
2277 else if (type
== DT_MATCH
)
2278 n_braces
= gen_match_op (f
, opname
);
2282 gen_kids (f
, gimple
);
2284 for (unsigned i
= 0; i
< n_braces
; ++i
)
2290 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2291 step of a '(simplify ...)' or '(match ...)'. This handles everything
2292 that is not part of the decision tree (simplify->match). */
2295 dt_simplify::gen (FILE *f
, bool gimple
)
2298 output_line_directive (f
, s
->result_location
);
2299 if (s
->capture_max
>= 0)
2300 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2301 s
->capture_max
+ 1);
2303 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2307 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2310 unsigned n_braces
= 0;
2311 if (s
->ifexpr_vec
!= vNULL
)
2313 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2315 if_or_with
&w
= s
->ifexpr_vec
[i
];
2319 output_line_directive (f
, w
.location
);
2320 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2325 output_line_directive (f
, w
.location
);
2326 fprintf (f
, "if (");
2327 if (i
== s
->ifexpr_vec
.length () - 1
2328 || s
->ifexpr_vec
[i
+1].is_with
)
2329 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2338 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2342 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2348 while (j
< s
->ifexpr_vec
.length ()
2349 && !s
->ifexpr_vec
[j
].is_with
);
2359 /* Analyze captures and perform early-outs on the incoming arguments
2360 that cover cases we cannot handle. */
2361 capture_info
cinfo (s
);
2365 && !((e
= dyn_cast
<expr
*> (s
->result
))
2366 && is_a
<predicate_id
*> (e
->operation
)))
2368 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2369 if (cinfo
.force_no_side_effects
& (1 << i
))
2370 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2371 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2372 if (cinfo
.info
[i
].cse_p
)
2374 else if (cinfo
.info
[i
].force_no_side_effects_p
2375 && (cinfo
.info
[i
].toplevel_msk
2376 & cinfo
.force_no_side_effects
) == 0)
2377 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2378 "return NULL_TREE;\n", i
);
2379 else if ((cinfo
.info
[i
].toplevel_msk
2380 & cinfo
.force_no_side_effects
) != 0)
2381 /* Mark capture as having no side-effects if we had to verify
2382 that via forced toplevel operand checks. */
2383 cinfo
.info
[i
].force_no_side_effects_p
= true;
2386 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2387 "fprintf (dump_file, \"Applying pattern ");
2388 output_line_directive (f
, s
->result_location
, true);
2389 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2391 operand
*result
= s
->result
;
2394 /* If there is no result then this is a predicate implementation. */
2395 fprintf (f
, "return true;\n");
2399 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2400 in outermost position). */
2401 if (result
->type
== operand::OP_EXPR
2402 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2403 result
= as_a
<expr
*> (result
)->ops
[0];
2404 if (result
->type
== operand::OP_EXPR
)
2406 expr
*e
= as_a
<expr
*> (result
);
2407 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2409 fprintf (f
, "*res_code = %s;\n",
2410 *e
->operation
== CONVERT_EXPR
2411 ? "NOP_EXPR" : e
->operation
->id
);
2412 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2415 snprintf (dest
, 32, " res_ops[%d]", j
);
2417 = get_operand_type (e
->operation
,
2418 "type", e
->expr_type
,
2420 ? NULL
: "TREE_TYPE (res_ops[0])");
2421 /* We need to expand GENERIC conditions we captured from
2423 bool expand_generic_cond_exprs_p
2425 /* But avoid doing that if the GENERIC condition is
2426 valid - which it is in the first operand of COND_EXPRs
2427 and VEC_COND_EXRPs. */
2428 && ((!(*e
->operation
== COND_EXPR
)
2429 && !(*e
->operation
== VEC_COND_EXPR
))
2431 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2432 indexes
, expand_generic_cond_exprs_p
);
2435 /* Re-fold the toplevel result. It's basically an embedded
2436 gimple_build w/o actually building the stmt. */
2438 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2439 "res_ops, valueize);\n", e
->ops
.length ());
2441 else if (result
->type
== operand::OP_CAPTURE
2442 || result
->type
== operand::OP_C_EXPR
)
2444 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2445 &cinfo
, indexes
, false);
2446 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2447 if (is_a
<capture
*> (result
)
2448 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2450 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2451 with substituting a capture of that. */
2452 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2454 " tree tem = res_ops[0];\n"
2455 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2456 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2462 fprintf (f
, "return true;\n");
2466 bool is_predicate
= false;
2467 if (result
->type
== operand::OP_EXPR
)
2469 expr
*e
= as_a
<expr
*> (result
);
2470 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2471 /* Search for captures used multiple times in the result expression
2472 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2474 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2476 if (!cinfo
.info
[i
].force_no_side_effects_p
2477 && cinfo
.info
[i
].result_use_count
> 1)
2478 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2479 " captures[%d] = save_expr (captures[%d]);\n",
2482 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2486 snprintf (dest
, 32, "res_ops[%d]", j
);
2489 fprintf (f
, " tree res_op%d;\n", j
);
2490 snprintf (dest
, 32, " res_op%d", j
);
2493 = get_operand_type (e
->operation
,
2494 "type", e
->expr_type
,
2496 ? NULL
: "TREE_TYPE (res_op0)");
2497 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2501 fprintf (f
, "return true;\n");
2504 fprintf (f
, " tree res;\n");
2505 /* Re-fold the toplevel result. Use non_lvalue to
2506 build NON_LVALUE_EXPRs so they get properly
2507 ignored when in GIMPLE form. */
2508 if (*e
->operation
== NON_LVALUE_EXPR
)
2509 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2512 if (e
->operation
->kind
== id_base::CODE
)
2513 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2515 *e
->operation
== CONVERT_EXPR
2516 ? "NOP_EXPR" : e
->operation
->id
);
2518 fprintf (f
, " res = build_call_expr_loc "
2519 "(loc, builtin_decl_implicit (%s), %d",
2520 e
->operation
->id
, e
->ops
.length());
2521 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2522 fprintf (f
, ", res_op%d", j
);
2523 fprintf (f
, ");\n");
2527 else if (result
->type
== operand::OP_CAPTURE
2528 || result
->type
== operand::OP_C_EXPR
)
2531 fprintf (f
, " tree res;\n");
2532 s
->result
->gen_transform (f
, " res", false, 1, "type",
2539 /* Search for captures not used in the result expression and dependent
2540 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2541 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2543 if (!cinfo
.info
[i
].force_no_side_effects_p
2544 && !cinfo
.info
[i
].expr_p
2545 && cinfo
.info
[i
].result_use_count
== 0)
2546 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2547 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2548 " fold_ignored_result (captures[%d]), res);\n",
2551 fprintf (f
, " return res;\n");
2555 for (unsigned i
= 0; i
< n_braces
; ++i
)
2561 /* Main entry to generate code for matching GIMPLE IL off the decision
2565 decision_tree::gen_gimple (FILE *f
)
2567 for (unsigned n
= 1; n
<= 3; ++n
)
2569 fprintf (f
, "\nstatic bool\n"
2570 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2571 " gimple_seq *seq, tree (*valueize)(tree),\n"
2572 " code_helper code, tree type");
2573 for (unsigned i
= 0; i
< n
; ++i
)
2574 fprintf (f
, ", tree op%d", i
);
2578 fprintf (f
, "switch (code.get_rep())\n"
2580 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2582 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2583 expr
*e
= static_cast<expr
*>(dop
->op
);
2584 if (e
->ops
.length () != n
)
2587 if (*e
->operation
== CONVERT_EXPR
2588 || *e
->operation
== NOP_EXPR
)
2589 fprintf (f
, "CASE_CONVERT:\n");
2591 fprintf (f
, "case %s%s:\n",
2592 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2595 dop
->gen_kids (f
, true);
2596 fprintf (f
, "break;\n");
2599 fprintf (f
, "default:;\n"
2602 fprintf (f
, "return false;\n");
2607 /* Main entry to generate code for matching GENERIC IL off the decision
2611 decision_tree::gen_generic (FILE *f
)
2613 for (unsigned n
= 1; n
<= 3; ++n
)
2615 fprintf (f
, "\ntree\n"
2616 "generic_simplify (location_t loc, enum tree_code code, "
2617 "tree type ATTRIBUTE_UNUSED");
2618 for (unsigned i
= 0; i
< n
; ++i
)
2619 fprintf (f
, ", tree op%d", i
);
2623 fprintf (f
, "switch (code)\n"
2625 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2627 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2628 expr
*e
= static_cast<expr
*>(dop
->op
);
2629 if (e
->ops
.length () != n
2630 /* Builtin simplifications are somewhat premature on
2631 GENERIC. The following drops patterns with outermost
2632 calls. It's easy to emit overloads for function code
2633 though if necessary. */
2634 || e
->operation
->kind
!= id_base::CODE
)
2637 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2638 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2639 fprintf (f
, "CASE_CONVERT:\n");
2641 fprintf (f
, "case %s:\n", e
->operation
->id
);
2643 dop
->gen_kids (f
, false);
2644 fprintf (f
, "break;\n"
2647 fprintf (f
, "default:;\n"
2650 fprintf (f
, "return NULL_TREE;\n");
2655 /* Output code to implement the predicate P from the decision tree DT. */
2658 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2660 fprintf (f
, "\nbool\n"
2661 "%s%s (tree t%s%s)\n"
2662 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2663 p
->nargs
> 0 ? ", tree *res_ops" : "",
2664 gimple
? ", tree (*valueize)(tree)" : "");
2665 /* Conveniently make 'type' available. */
2666 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2669 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2670 dt
.root
->gen_kids (f
, gimple
);
2672 fprintf (f
, "return false;\n"
2676 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2679 write_header (FILE *f
, const char *head
)
2681 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2682 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2684 /* Include the header instead of writing it awkwardly quoted here. */
2685 fprintf (f
, "\n#include \"%s\"\n", head
);
2695 parser (cpp_reader
*);
2698 const cpp_token
*next ();
2699 const cpp_token
*peek ();
2700 const cpp_token
*peek_ident (const char * = NULL
);
2701 const cpp_token
*expect (enum cpp_ttype
);
2702 void eat_token (enum cpp_ttype
);
2703 const char *get_string ();
2704 const char *get_ident ();
2705 void eat_ident (const char *);
2706 const char *get_number ();
2708 id_base
*parse_operation ();
2709 operand
*parse_capture (operand
*);
2710 operand
*parse_expr ();
2711 c_expr
*parse_c_expr (cpp_ttype
);
2712 operand
*parse_op ();
2714 void record_operlist (source_location
, user_id
*);
2716 void parse_pattern ();
2717 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2718 operand
*, source_location
);
2719 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2721 void parse_for (source_location
);
2722 void parse_if (source_location
);
2723 void parse_predicates (source_location
);
2724 void parse_operator_list (source_location
);
2727 vec
<if_or_with
> active_ifs
;
2728 vec
<vec
<user_id
*> > active_fors
;
2729 hash_set
<user_id
*> *oper_lists_set
;
2730 vec
<user_id
*> oper_lists
;
2732 cid_map_t
*capture_ids
;
2735 vec
<simplify
*> simplifiers
;
2736 vec
<predicate_id
*> user_predicates
;
2737 bool parsing_match_operand
;
2740 /* Lexing helpers. */
2742 /* Read the next non-whitespace token from R. */
2747 const cpp_token
*token
;
2750 token
= cpp_get_token (r
);
2752 while (token
->type
== CPP_PADDING
2753 && token
->type
!= CPP_EOF
);
2757 /* Peek at the next non-whitespace token from R. */
2762 const cpp_token
*token
;
2766 token
= cpp_peek_token (r
, i
++);
2768 while (token
->type
== CPP_PADDING
2769 && token
->type
!= CPP_EOF
);
2770 /* If we peek at EOF this is a fatal error as it leaves the
2771 cpp_reader in unusable state. Assume we really wanted a
2772 token and thus this EOF is unexpected. */
2773 if (token
->type
== CPP_EOF
)
2774 fatal_at (token
, "unexpected end of file");
2778 /* Peek at the next identifier token (or return NULL if the next
2779 token is not an identifier or equal to ID if supplied). */
2782 parser::peek_ident (const char *id
)
2784 const cpp_token
*token
= peek ();
2785 if (token
->type
!= CPP_NAME
)
2791 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2792 if (strcmp (id
, t
) == 0)
2798 /* Read the next token from R and assert it is of type TK. */
2801 parser::expect (enum cpp_ttype tk
)
2803 const cpp_token
*token
= next ();
2804 if (token
->type
!= tk
)
2805 fatal_at (token
, "expected %s, got %s",
2806 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2811 /* Consume the next token from R and assert it is of type TK. */
2814 parser::eat_token (enum cpp_ttype tk
)
2819 /* Read the next token from R and assert it is of type CPP_STRING and
2820 return its value. */
2823 parser::get_string ()
2825 const cpp_token
*token
= expect (CPP_STRING
);
2826 return (const char *)token
->val
.str
.text
;
2829 /* Read the next token from R and assert it is of type CPP_NAME and
2830 return its value. */
2833 parser::get_ident ()
2835 const cpp_token
*token
= expect (CPP_NAME
);
2836 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2839 /* Eat an identifier token with value S from R. */
2842 parser::eat_ident (const char *s
)
2844 const cpp_token
*token
= peek ();
2845 const char *t
= get_ident ();
2846 if (strcmp (s
, t
) != 0)
2847 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2850 /* Read the next token from R and assert it is of type CPP_NUMBER and
2851 return its value. */
2854 parser::get_number ()
2856 const cpp_token
*token
= expect (CPP_NUMBER
);
2857 return (const char *)token
->val
.str
.text
;
2861 /* Record an operator-list use for transparent for handling. */
2864 parser::record_operlist (source_location loc
, user_id
*p
)
2866 if (!oper_lists_set
->add (p
))
2868 if (!oper_lists
.is_empty ()
2869 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2870 fatal_at (loc
, "User-defined operator list does not have the "
2871 "same number of entries as others used in the pattern");
2872 oper_lists
.safe_push (p
);
2876 /* Parse the operator ID, special-casing convert?, convert1? and
2880 parser::parse_operation ()
2882 const cpp_token
*id_tok
= peek ();
2883 const char *id
= get_ident ();
2884 const cpp_token
*token
= peek ();
2885 if (strcmp (id
, "convert0") == 0)
2886 fatal_at (id_tok
, "use 'convert?' here");
2887 else if (strcmp (id
, "view_convert0") == 0)
2888 fatal_at (id_tok
, "use 'view_convert?' here");
2889 if (token
->type
== CPP_QUERY
2890 && !(token
->flags
& PREV_WHITE
))
2892 if (strcmp (id
, "convert") == 0)
2894 else if (strcmp (id
, "convert1") == 0)
2896 else if (strcmp (id
, "convert2") == 0)
2898 else if (strcmp (id
, "view_convert") == 0)
2899 id
= "view_convert0";
2900 else if (strcmp (id
, "view_convert1") == 0)
2902 else if (strcmp (id
, "view_convert2") == 0)
2905 fatal_at (id_tok
, "non-convert operator conditionalized");
2907 if (!parsing_match_operand
)
2908 fatal_at (id_tok
, "conditional convert can only be used in "
2909 "match expression");
2910 eat_token (CPP_QUERY
);
2912 else if (strcmp (id
, "convert1") == 0
2913 || strcmp (id
, "convert2") == 0
2914 || strcmp (id
, "view_convert1") == 0
2915 || strcmp (id
, "view_convert2") == 0)
2916 fatal_at (id_tok
, "expected '?' after conditional operator");
2917 id_base
*op
= get_operator (id
);
2919 fatal_at (id_tok
, "unknown operator %s", id
);
2921 user_id
*p
= dyn_cast
<user_id
*> (op
);
2922 if (p
&& p
->is_oper_list
)
2924 if (active_fors
.length() == 0)
2925 record_operlist (id_tok
->src_loc
, p
);
2927 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
2933 capture = '@'<number> */
2936 parser::parse_capture (operand
*op
)
2938 eat_token (CPP_ATSIGN
);
2939 const cpp_token
*token
= peek ();
2940 const char *id
= NULL
;
2941 if (token
->type
== CPP_NUMBER
)
2943 else if (token
->type
== CPP_NAME
)
2946 fatal_at (token
, "expected number or identifier");
2947 unsigned next_id
= capture_ids
->elements ();
2949 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2952 return new capture (num
, op
);
2955 /* Parse an expression
2956 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2959 parser::parse_expr ()
2961 expr
*e
= new expr (parse_operation ());
2962 const cpp_token
*token
= peek ();
2964 bool is_commutative
= false;
2965 const char *expr_type
= NULL
;
2967 if (token
->type
== CPP_COLON
2968 && !(token
->flags
& PREV_WHITE
))
2970 eat_token (CPP_COLON
);
2972 if (token
->type
== CPP_NAME
2973 && !(token
->flags
& PREV_WHITE
))
2975 const char *s
= get_ident ();
2976 if (s
[0] == 'c' && !s
[1])
2978 if (!parsing_match_operand
)
2980 "flag 'c' can only be used in match expression");
2981 is_commutative
= true;
2983 else if (s
[1] != '\0')
2985 if (parsing_match_operand
)
2986 fatal_at (token
, "type can only be used in result expression");
2990 fatal_at (token
, "flag %s not recognized", s
);
2995 fatal_at (token
, "expected flag or type specifying identifier");
2998 if (token
->type
== CPP_ATSIGN
2999 && !(token
->flags
& PREV_WHITE
))
3000 op
= parse_capture (e
);
3005 const cpp_token
*token
= peek ();
3006 if (token
->type
== CPP_CLOSE_PAREN
)
3008 if (e
->operation
->nargs
!= -1
3009 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3010 fatal_at (token
, "'%s' expects %u operands, not %u",
3011 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3014 if (e
->ops
.length () == 2)
3015 e
->is_commutative
= true;
3017 fatal_at (token
, "only binary operators or function with "
3018 "two arguments can be marked commutative");
3020 e
->expr_type
= expr_type
;
3023 e
->append_op (parse_op ());
3028 /* Lex native C code delimited by START recording the preprocessing tokens
3029 for later processing.
3030 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3033 parser::parse_c_expr (cpp_ttype start
)
3035 const cpp_token
*token
;
3038 vec
<cpp_token
> code
= vNULL
;
3039 unsigned nr_stmts
= 0;
3041 if (start
== CPP_OPEN_PAREN
)
3042 end
= CPP_CLOSE_PAREN
;
3043 else if (start
== CPP_OPEN_BRACE
)
3044 end
= CPP_CLOSE_BRACE
;
3052 /* Count brace pairs to find the end of the expr to match. */
3053 if (token
->type
== start
)
3055 else if (token
->type
== end
3059 /* This is a lame way of counting the number of statements. */
3060 if (token
->type
== CPP_SEMICOLON
)
3063 /* If this is possibly a user-defined identifier mark it used. */
3064 if (token
->type
== CPP_NAME
)
3066 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3067 (token
->val
.node
.node
)->ident
.str
);
3069 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3070 record_operlist (token
->src_loc
, p
);
3073 /* Record the token. */
3074 code
.safe_push (*token
);
3077 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3080 /* Parse an operand which is either an expression, a predicate or
3081 a standalone capture.
3082 op = predicate | expr | c_expr | capture */
3087 const cpp_token
*token
= peek ();
3088 struct operand
*op
= NULL
;
3089 if (token
->type
== CPP_OPEN_PAREN
)
3091 eat_token (CPP_OPEN_PAREN
);
3093 eat_token (CPP_CLOSE_PAREN
);
3095 else if (token
->type
== CPP_OPEN_BRACE
)
3097 op
= parse_c_expr (CPP_OPEN_BRACE
);
3101 /* Remaining ops are either empty or predicates */
3102 if (token
->type
== CPP_NAME
)
3104 const char *id
= get_ident ();
3105 id_base
*opr
= get_operator (id
);
3107 fatal_at (token
, "expected predicate name");
3108 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3110 if (code
->nargs
!= 0)
3111 fatal_at (token
, "using an operator with operands as predicate");
3112 /* Parse the zero-operand operator "predicates" as
3114 op
= new expr (opr
);
3116 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3118 if (code
->nargs
!= 0)
3119 fatal_at (token
, "using an operator with operands as predicate");
3120 /* Parse the zero-operand operator "predicates" as
3122 op
= new expr (opr
);
3124 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3125 op
= new predicate (p
);
3127 fatal_at (token
, "using an unsupported operator as predicate");
3128 if (!parsing_match_operand
)
3129 fatal_at (token
, "predicates are only allowed in match expression");
3131 if (token
->flags
& PREV_WHITE
)
3134 else if (token
->type
!= CPP_COLON
3135 && token
->type
!= CPP_ATSIGN
)
3136 fatal_at (token
, "expected expression or predicate");
3137 /* optionally followed by a capture and a predicate. */
3138 if (token
->type
== CPP_COLON
)
3139 fatal_at (token
, "not implemented: predicate on leaf operand");
3140 if (token
->type
== CPP_ATSIGN
)
3141 op
= parse_capture (op
);
3147 /* Create a new simplify from the current parsing state and MATCH,
3148 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3151 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3152 operand
*match
, source_location match_loc
,
3153 operand
*result
, source_location result_loc
)
3155 /* Build and push a temporary for for operator list uses in expressions. */
3156 if (!oper_lists
.is_empty ())
3157 active_fors
.safe_push (oper_lists
);
3159 simplifiers
.safe_push
3160 (new simplify (match
, match_loc
, result
, result_loc
,
3161 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3163 if (!oper_lists
.is_empty ())
3168 simplify = 'simplify' <expr> <result-op>
3170 match = 'match' <ident> <expr> [<result-op>]
3172 <result-op> = <op> | <if> | <with>
3173 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3174 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3175 and fill SIMPLIFIERS with the results. */
3178 parser::parse_simplify (source_location match_location
,
3179 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3182 /* Reset the capture map. */
3184 capture_ids
= new cid_map_t
;
3185 /* Reset oper_lists and set. */
3186 hash_set
<user_id
*> olist
;
3187 oper_lists_set
= &olist
;
3190 const cpp_token
*loc
= peek ();
3191 parsing_match_operand
= true;
3192 struct operand
*match
= parse_op ();
3193 parsing_match_operand
= false;
3194 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3195 fatal_at (loc
, "outermost expression cannot be captured");
3196 if (match
->type
== operand::OP_EXPR
3197 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3198 fatal_at (loc
, "outermost expression cannot be a predicate");
3200 const cpp_token
*token
= peek ();
3202 /* If this if is immediately closed then it is part of a predicate
3203 definition. Push it. */
3204 if (token
->type
== CPP_CLOSE_PAREN
)
3207 fatal_at (token
, "expected transform expression");
3208 push_simplify (simplifiers
, match
, match_location
,
3209 result
, token
->src_loc
);
3213 unsigned active_ifs_len
= active_ifs
.length ();
3216 if (token
->type
== CPP_OPEN_PAREN
)
3218 source_location paren_loc
= token
->src_loc
;
3219 eat_token (CPP_OPEN_PAREN
);
3220 if (peek_ident ("if"))
3223 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3224 token
->src_loc
, false));
3225 /* If this if is immediately closed then it contains a
3226 manual matcher or is part of a predicate definition.
3228 if (peek ()->type
== CPP_CLOSE_PAREN
)
3231 fatal_at (token
, "manual transform not implemented");
3232 push_simplify (simplifiers
, match
, match_location
,
3236 else if (peek_ident ("with"))
3239 /* Parse (with c-expr expr) as (if-with (true) expr). */
3240 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3242 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3246 operand
*op
= result
;
3249 push_simplify (simplifiers
, match
, match_location
,
3250 op
, token
->src_loc
);
3251 eat_token (CPP_CLOSE_PAREN
);
3252 /* A "default" result closes the enclosing scope. */
3253 if (active_ifs
.length () > active_ifs_len
)
3255 eat_token (CPP_CLOSE_PAREN
);
3262 else if (token
->type
== CPP_CLOSE_PAREN
)
3264 /* Close a scope if requested. */
3265 if (active_ifs
.length () > active_ifs_len
)
3267 eat_token (CPP_CLOSE_PAREN
);
3277 fatal_at (token
, "expected match operand expression");
3278 push_simplify (simplifiers
, match
, match_location
,
3279 matcher
? result
: parse_op (), token
->src_loc
);
3280 /* A "default" result closes the enclosing scope. */
3281 if (active_ifs
.length () > active_ifs_len
)
3283 eat_token (CPP_CLOSE_PAREN
);
3293 /* Parsing of the outer control structures. */
3295 /* Parse a for expression
3296 for = '(' 'for' <subst>... <pattern> ')'
3297 subst = <ident> '(' <ident>... ')' */
3300 parser::parse_for (source_location
)
3302 auto_vec
<const cpp_token
*> user_id_tokens
;
3303 vec
<user_id
*> user_ids
= vNULL
;
3304 const cpp_token
*token
;
3305 unsigned min_n_opers
= 0, max_n_opers
= 0;
3310 if (token
->type
!= CPP_NAME
)
3313 /* Insert the user defined operators into the operator hash. */
3314 const char *id
= get_ident ();
3315 if (get_operator (id
) != NULL
)
3316 fatal_at (token
, "operator already defined");
3317 user_id
*op
= new user_id (id
);
3318 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3320 user_ids
.safe_push (op
);
3321 user_id_tokens
.safe_push (token
);
3323 eat_token (CPP_OPEN_PAREN
);
3326 while ((token
= peek_ident ()) != 0)
3328 const char *oper
= get_ident ();
3329 id_base
*idb
= get_operator (oper
);
3331 fatal_at (token
, "no such operator '%s'", oper
);
3332 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3333 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3334 || *idb
== VIEW_CONVERT2
)
3335 fatal_at (token
, "conditional operators cannot be used inside for");
3339 else if (idb
->nargs
== -1)
3341 else if (idb
->nargs
!= arity
)
3342 fatal_at (token
, "operator '%s' with arity %d does not match "
3343 "others with arity %d", oper
, idb
->nargs
, arity
);
3345 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3348 if (p
->is_oper_list
)
3349 op
->substitutes
.safe_splice (p
->substitutes
);
3351 fatal_at (token
, "iterator cannot be used as operator-list");
3354 op
->substitutes
.safe_push (idb
);
3357 token
= expect (CPP_CLOSE_PAREN
);
3359 unsigned nsubstitutes
= op
->substitutes
.length ();
3360 if (nsubstitutes
== 0)
3361 fatal_at (token
, "A user-defined operator must have at least "
3362 "one substitution");
3363 if (max_n_opers
== 0)
3365 min_n_opers
= nsubstitutes
;
3366 max_n_opers
= nsubstitutes
;
3370 if (nsubstitutes
% min_n_opers
!= 0
3371 && min_n_opers
% nsubstitutes
!= 0)
3372 fatal_at (token
, "All user-defined identifiers must have a "
3373 "multiple number of operator substitutions of the "
3374 "smallest number of substitutions");
3375 if (nsubstitutes
< min_n_opers
)
3376 min_n_opers
= nsubstitutes
;
3377 else if (nsubstitutes
> max_n_opers
)
3378 max_n_opers
= nsubstitutes
;
3382 unsigned n_ids
= user_ids
.length ();
3384 fatal_at (token
, "for requires at least one user-defined identifier");
3387 if (token
->type
== CPP_CLOSE_PAREN
)
3388 fatal_at (token
, "no pattern defined in for");
3390 active_fors
.safe_push (user_ids
);
3394 if (token
->type
== CPP_CLOSE_PAREN
)
3400 /* Remove user-defined operators from the hash again. */
3401 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3403 if (!user_ids
[i
]->used
)
3404 warning_at (user_id_tokens
[i
],
3405 "operator %s defined but not used", user_ids
[i
]->id
);
3406 operators
->remove_elt (user_ids
[i
]);
3410 /* Parse an identifier associated with a list of operators.
3411 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3414 parser::parse_operator_list (source_location
)
3416 const cpp_token
*token
= peek ();
3417 const char *id
= get_ident ();
3419 if (get_operator (id
) != 0)
3420 fatal_at (token
, "operator %s already defined", id
);
3422 user_id
*op
= new user_id (id
, true);
3425 while ((token
= peek_ident ()) != 0)
3428 const char *oper
= get_ident ();
3429 id_base
*idb
= get_operator (oper
);
3432 fatal_at (token
, "no such operator '%s'", oper
);
3436 else if (idb
->nargs
== -1)
3438 else if (arity
!= idb
->nargs
)
3439 fatal_at (token
, "operator '%s' with arity %d does not match "
3440 "others with arity %d", oper
, idb
->nargs
, arity
);
3442 /* We allow composition of multiple operator lists. */
3443 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3444 op
->substitutes
.safe_splice (p
->substitutes
);
3446 op
->substitutes
.safe_push (idb
);
3449 // Check that there is no junk after id-list
3451 if (token
->type
!= CPP_CLOSE_PAREN
)
3452 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3454 if (op
->substitutes
.length () == 0)
3455 fatal_at (token
, "operator-list cannot be empty");
3458 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3462 /* Parse an outer if expression.
3463 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3466 parser::parse_if (source_location loc
)
3468 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3470 const cpp_token
*token
= peek ();
3471 if (token
->type
== CPP_CLOSE_PAREN
)
3472 fatal_at (token
, "no pattern defined in if");
3474 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3477 const cpp_token
*token
= peek ();
3478 if (token
->type
== CPP_CLOSE_PAREN
)
3486 /* Parse a list of predefined predicate identifiers.
3487 preds = '(' 'define_predicates' <ident>... ')' */
3490 parser::parse_predicates (source_location
)
3494 const cpp_token
*token
= peek ();
3495 if (token
->type
!= CPP_NAME
)
3498 add_predicate (get_ident ());
3503 /* Parse outer control structures.
3504 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3507 parser::parse_pattern ()
3509 /* All clauses start with '('. */
3510 eat_token (CPP_OPEN_PAREN
);
3511 const cpp_token
*token
= peek ();
3512 const char *id
= get_ident ();
3513 if (strcmp (id
, "simplify") == 0)
3515 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3518 else if (strcmp (id
, "match") == 0)
3520 bool with_args
= false;
3521 if (peek ()->type
== CPP_OPEN_PAREN
)
3523 eat_token (CPP_OPEN_PAREN
);
3526 const char *name
= get_ident ();
3527 id_base
*id
= get_operator (name
);
3531 p
= add_predicate (name
);
3532 user_predicates
.safe_push (p
);
3534 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3537 fatal_at (token
, "cannot add a match to a non-predicate ID");
3538 /* Parse (match <id> <arg>... (match-expr)) here. */
3542 capture_ids
= new cid_map_t
;
3544 while (peek ()->type
== CPP_ATSIGN
)
3545 e
->append_op (parse_capture (NULL
));
3546 eat_token (CPP_CLOSE_PAREN
);
3549 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3550 || (!e
&& p
->nargs
!= 0)))
3551 fatal_at (token
, "non-matching number of match operands");
3552 p
->nargs
= e
? e
->ops
.length () : 0;
3553 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3556 else if (strcmp (id
, "for") == 0)
3557 parse_for (token
->src_loc
);
3558 else if (strcmp (id
, "if") == 0)
3559 parse_if (token
->src_loc
);
3560 else if (strcmp (id
, "define_predicates") == 0)
3562 if (active_ifs
.length () > 0
3563 || active_fors
.length () > 0)
3564 fatal_at (token
, "define_predicates inside if or for is not supported");
3565 parse_predicates (token
->src_loc
);
3567 else if (strcmp (id
, "define_operator_list") == 0)
3569 if (active_ifs
.length () > 0
3570 || active_fors
.length () > 0)
3571 fatal_at (token
, "operator-list inside if or for is not supported");
3572 parse_operator_list (token
->src_loc
);
3575 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3576 active_ifs
.length () == 0 && active_fors
.length () == 0
3577 ? "'define_predicates', " : "");
3579 eat_token (CPP_CLOSE_PAREN
);
3582 /* Main entry of the parser. Repeatedly parse outer control structures. */
3584 parser::parser (cpp_reader
*r_
)
3588 active_fors
= vNULL
;
3589 simplifiers
= vNULL
;
3590 oper_lists_set
= NULL
;
3593 user_predicates
= vNULL
;
3594 parsing_match_operand
= false;
3596 const cpp_token
*token
= next ();
3597 while (token
->type
!= CPP_EOF
)
3599 _cpp_backup_tokens (r
, 1);
3606 /* Helper for the linemap code. */
3609 round_alloc_size (size_t s
)
3615 /* The genmatch generator progam. It reads from a pattern description
3616 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3619 main (int argc
, char **argv
)
3623 progname
= "genmatch";
3629 bool verbose
= false;
3630 char *input
= argv
[argc
-1];
3631 for (int i
= 1; i
< argc
- 1; ++i
)
3633 if (strcmp (argv
[i
], "--gimple") == 0)
3635 else if (strcmp (argv
[i
], "--generic") == 0)
3637 else if (strcmp (argv
[i
], "-v") == 0)
3641 fprintf (stderr
, "Usage: genmatch "
3642 "[--gimple] [--generic] [-v] input\n");
3647 line_table
= XCNEW (struct line_maps
);
3648 linemap_init (line_table
, 0);
3649 line_table
->reallocator
= xrealloc
;
3650 line_table
->round_alloc_size
= round_alloc_size
;
3652 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3653 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3654 cb
->error
= error_cb
;
3656 if (!cpp_read_main_file (r
, input
))
3658 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3659 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3661 /* Pre-seed operators. */
3662 operators
= new hash_table
<id_base
> (1024);
3663 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3664 add_operator (SYM, # SYM, # TYPE, NARGS);
3665 #define END_OF_BASE_TREE_CODES
3667 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3668 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3669 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3670 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
3671 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
3672 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
3673 #undef END_OF_BASE_TREE_CODES
3676 /* Pre-seed builtin functions.
3677 ??? Cannot use N (name) as that is targetm.emultls.get_address
3678 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3679 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3680 add_builtin (ENUM, # ENUM);
3681 #include "builtins.def"
3688 write_header (stdout
, "gimple-match-head.c");
3690 write_header (stdout
, "generic-match-head.c");
3692 /* Go over all predicates defined with patterns and perform
3693 lowering and code generation. */
3694 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3696 predicate_id
*pred
= p
.user_predicates
[i
];
3697 lower (pred
->matchers
, gimple
);
3700 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3701 print_matches (pred
->matchers
[i
]);
3704 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3705 dt
.insert (pred
->matchers
[i
], i
);
3710 write_predicate (stdout
, pred
, dt
, gimple
);
3713 /* Lower the main simplifiers and generate code for them. */
3714 lower (p
.simplifiers
, gimple
);
3717 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3718 print_matches (p
.simplifiers
[i
]);
3721 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3722 dt
.insert (p
.simplifiers
[i
], i
);
3728 dt
.gen_gimple (stdout
);
3730 dt
.gen_generic (stdout
);
3733 cpp_finish (r
, NULL
);