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 hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
401 /* The AST produced by parsing of the pattern definitions. */
406 /* The base class for operands. */
409 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
410 operand (enum op_type type_
) : type (type_
) {}
412 virtual void gen_transform (FILE *, const char *, bool, int,
413 const char *, capture_info
*,
416 { gcc_unreachable (); }
419 /* A predicate operand. Predicates are leafs in the AST. */
421 struct predicate
: public operand
423 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
427 /* An operand that constitutes an expression. Expressions include
428 function calls and user-defined predicate invocations. */
430 struct expr
: public operand
432 expr (id_base
*operation_
, bool is_commutative_
= false)
433 : operand (OP_EXPR
), operation (operation_
),
434 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
435 is_generic (false) {}
436 void append_op (operand
*op
) { ops
.safe_push (op
); }
437 /* The operator and its operands. */
440 /* An explicitely specified type - used exclusively for conversions. */
441 const char *expr_type
;
442 /* Whether the operation is to be applied commutatively. This is
443 later lowered to two separate patterns. */
445 /* Whether the expression is expected to be in GENERIC form. */
447 virtual void gen_transform (FILE *f
, const char *, bool, int,
448 const char *, capture_info
*,
449 dt_operand
** = 0, bool = true);
452 /* An operator that is represented by native C code. This is always
453 a leaf operand in the AST. This class is also used to represent
454 the code to be generated for 'if' and 'with' expressions. */
456 struct c_expr
: public operand
458 /* A mapping of an identifier and its replacement. Used to apply
463 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
466 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
467 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
468 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
469 nr_stmts (nr_stmts_
), ids (ids_
) {}
470 /* cpplib tokens and state to transform this back to source. */
473 cid_map_t
*capture_ids
;
474 /* The number of statements parsed (well, the number of ';'s). */
476 /* The identifier replacement vector. */
478 virtual void gen_transform (FILE *f
, const char *, bool, int,
479 const char *, capture_info
*,
480 dt_operand
** = 0, bool = true);
483 /* A wrapper around another operand that captures its value. */
485 struct capture
: public operand
487 capture (unsigned where_
, operand
*what_
)
488 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
489 /* Identifier index for the value. */
491 /* The captured value. */
493 virtual void gen_transform (FILE *f
, const char *, bool, int,
494 const char *, capture_info
*,
495 dt_operand
** = 0, bool = true);
501 is_a_helper
<capture
*>::test (operand
*op
)
503 return op
->type
== operand::OP_CAPTURE
;
509 is_a_helper
<predicate
*>::test (operand
*op
)
511 return op
->type
== operand::OP_PREDICATE
;
517 is_a_helper
<c_expr
*>::test (operand
*op
)
519 return op
->type
== operand::OP_C_EXPR
;
525 is_a_helper
<expr
*>::test (operand
*op
)
527 return op
->type
== operand::OP_EXPR
;
530 /* Helper to distinguish 'if' from 'with' expressions. */
534 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
535 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
536 source_location location
;
541 /* The main class of a pattern and its transform. This is used to
542 represent both (simplify ...) and (match ...) kinds. The AST
543 duplicates all outer 'if' and 'for' expressions here so each
544 simplify can exist in isolation. */
548 simplify (operand
*match_
, source_location match_location_
,
549 struct operand
*result_
, source_location result_location_
,
550 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
551 cid_map_t
*capture_ids_
)
552 : match (match_
), match_location (match_location_
),
553 result (result_
), result_location (result_location_
),
554 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
555 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
557 /* The expression that is matched against the GENERIC or GIMPLE IL. */
559 source_location match_location
;
560 /* For a (simplify ...) the expression produced when the pattern applies.
561 For a (match ...) either NULL if it is a simple predicate or the
562 single expression specifying the matched operands. */
563 struct operand
*result
;
564 source_location result_location
;
565 /* Collected 'if' expressions that need to evaluate to true to make
566 the pattern apply. */
567 vec
<if_or_with
> ifexpr_vec
;
568 /* Collected 'for' expression operators that have to be replaced
569 in the lowering phase. */
570 vec
<vec
<user_id
*> > for_vec
;
571 /* A map of capture identifiers to indexes. */
572 cid_map_t
*capture_ids
;
576 /* Debugging routines for dumping the AST. */
579 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
581 if (capture
*c
= dyn_cast
<capture
*> (o
))
583 fprintf (f
, "@%u", c
->where
);
584 if (c
->what
&& flattened
== false)
587 print_operand (c
->what
, f
, flattened
);
592 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
593 fprintf (f
, "%s", p
->p
->id
);
595 else if (is_a
<c_expr
*> (o
))
596 fprintf (f
, "c_expr");
598 else if (expr
*e
= dyn_cast
<expr
*> (o
))
600 fprintf (f
, "(%s", e
->operation
->id
);
602 if (flattened
== false)
605 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
607 print_operand (e
->ops
[i
], f
, flattened
);
619 print_matches (struct simplify
*s
, FILE *f
= stderr
)
621 fprintf (f
, "for expression: ");
622 print_operand (s
->match
, f
);
629 /* Lowering of commutative operators. */
632 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
633 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
635 if (n
== ops_vector
.length ())
637 vec
<operand
*> xv
= v
.copy ();
638 result
.safe_push (xv
);
642 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
644 v
[n
] = ops_vector
[n
][i
];
645 cartesian_product (ops_vector
, result
, v
, n
+ 1);
649 /* Lower OP to two operands in case it is marked as commutative. */
651 static vec
<operand
*>
652 commutate (operand
*op
)
654 vec
<operand
*> ret
= vNULL
;
656 if (capture
*c
= dyn_cast
<capture
*> (op
))
663 vec
<operand
*> v
= commutate (c
->what
);
664 for (unsigned i
= 0; i
< v
.length (); ++i
)
666 capture
*nc
= new capture (c
->where
, v
[i
]);
672 expr
*e
= dyn_cast
<expr
*> (op
);
673 if (!e
|| e
->ops
.length () == 0)
679 vec
< vec
<operand
*> > ops_vector
= vNULL
;
680 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
681 ops_vector
.safe_push (commutate (e
->ops
[i
]));
683 auto_vec
< vec
<operand
*> > result
;
684 auto_vec
<operand
*> v (e
->ops
.length ());
685 v
.quick_grow_cleared (e
->ops
.length ());
686 cartesian_product (ops_vector
, result
, v
, 0);
689 for (unsigned i
= 0; i
< result
.length (); ++i
)
691 expr
*ne
= new expr (e
->operation
);
692 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
693 ne
->append_op (result
[i
][j
]);
697 if (!e
->is_commutative
)
700 for (unsigned i
= 0; i
< result
.length (); ++i
)
702 expr
*ne
= new expr (e
->operation
);
703 // result[i].length () is 2 since e->operation is binary
704 for (unsigned j
= result
[i
].length (); j
; --j
)
705 ne
->append_op (result
[i
][j
-1]);
712 /* Lower operations marked as commutative in the AST of S and push
713 the resulting patterns to SIMPLIFIERS. */
716 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
718 vec
<operand
*> matchers
= commutate (s
->match
);
719 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
721 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
722 s
->result
, s
->result_location
, s
->ifexpr_vec
,
723 s
->for_vec
, s
->capture_ids
);
724 simplifiers
.safe_push (ns
);
728 /* Strip conditional conversios using operator OPER from O and its
729 children if STRIP, else replace them with an unconditional convert. */
732 lower_opt_convert (operand
*o
, enum tree_code oper
,
733 enum tree_code to_oper
, bool strip
)
735 if (capture
*c
= dyn_cast
<capture
*> (o
))
738 return new capture (c
->where
,
739 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
744 expr
*e
= dyn_cast
<expr
*> (o
);
748 if (*e
->operation
== oper
)
751 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
753 expr
*ne
= new expr (to_oper
== CONVERT_EXPR
754 ? get_operator ("CONVERT_EXPR")
755 : get_operator ("VIEW_CONVERT_EXPR"));
756 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
760 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
761 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
762 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
767 /* Determine whether O or its children uses the conditional conversion
771 has_opt_convert (operand
*o
, enum tree_code oper
)
773 if (capture
*c
= dyn_cast
<capture
*> (o
))
776 return has_opt_convert (c
->what
, oper
);
781 expr
*e
= dyn_cast
<expr
*> (o
);
785 if (*e
->operation
== oper
)
788 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
789 if (has_opt_convert (e
->ops
[i
], oper
))
795 /* Lower conditional convert operators in O, expanding it to a vector
798 static vec
<operand
*>
799 lower_opt_convert (operand
*o
)
801 vec
<operand
*> v1
= vNULL
, v2
;
805 enum tree_code opers
[]
806 = { CONVERT0
, CONVERT_EXPR
,
807 CONVERT1
, CONVERT_EXPR
,
808 CONVERT2
, CONVERT_EXPR
,
809 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
810 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
811 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
813 /* Conditional converts are lowered to a pattern with the
814 conversion and one without. The three different conditional
815 convert codes are lowered separately. */
817 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
820 for (unsigned j
= 0; j
< v1
.length (); ++j
)
821 if (has_opt_convert (v1
[j
], opers
[i
]))
823 v2
.safe_push (lower_opt_convert (v1
[j
],
824 opers
[i
], opers
[i
+1], false));
825 v2
.safe_push (lower_opt_convert (v1
[j
],
826 opers
[i
], opers
[i
+1], true));
832 for (unsigned j
= 0; j
< v2
.length (); ++j
)
833 v1
.safe_push (v2
[j
]);
840 /* Lower conditional convert operators in the AST of S and push
841 the resulting multiple patterns to SIMPLIFIERS. */
844 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
846 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
847 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
849 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
850 s
->result
, s
->result_location
, s
->ifexpr_vec
,
851 s
->for_vec
, s
->capture_ids
);
852 simplifiers
.safe_push (ns
);
856 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
857 GENERIC and a GIMPLE variant. */
859 static vec
<operand
*>
860 lower_cond (operand
*o
)
862 vec
<operand
*> ro
= vNULL
;
864 if (capture
*c
= dyn_cast
<capture
*> (o
))
868 vec
<operand
*> lop
= vNULL
;
869 lop
= lower_cond (c
->what
);
871 for (unsigned i
= 0; i
< lop
.length (); ++i
)
872 ro
.safe_push (new capture (c
->where
, lop
[i
]));
877 expr
*e
= dyn_cast
<expr
*> (o
);
878 if (!e
|| e
->ops
.length () == 0)
884 vec
< vec
<operand
*> > ops_vector
= vNULL
;
885 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
886 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
888 auto_vec
< vec
<operand
*> > result
;
889 auto_vec
<operand
*> v (e
->ops
.length ());
890 v
.quick_grow_cleared (e
->ops
.length ());
891 cartesian_product (ops_vector
, result
, v
, 0);
893 for (unsigned i
= 0; i
< result
.length (); ++i
)
895 expr
*ne
= new expr (e
->operation
);
896 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
897 ne
->append_op (result
[i
][j
]);
899 /* If this is a COND with a captured expression or an
900 expression with two operands then also match a GENERIC
901 form on the compare. */
902 if ((*e
->operation
== COND_EXPR
903 || *e
->operation
== VEC_COND_EXPR
)
904 && ((is_a
<capture
*> (e
->ops
[0])
905 && as_a
<capture
*> (e
->ops
[0])->what
906 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
908 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
909 || (is_a
<expr
*> (e
->ops
[0])
910 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
912 expr
*ne
= new expr (e
->operation
);
913 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
914 ne
->append_op (result
[i
][j
]);
915 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
917 expr
*ocmp
= as_a
<expr
*> (c
->what
);
918 expr
*cmp
= new expr (ocmp
->operation
);
919 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
920 cmp
->append_op (ocmp
->ops
[j
]);
921 cmp
->is_generic
= true;
922 ne
->ops
[0] = new capture (c
->where
, cmp
);
926 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
927 expr
*cmp
= new expr (ocmp
->operation
);
928 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
929 cmp
->append_op (ocmp
->ops
[j
]);
930 cmp
->is_generic
= true;
940 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
941 GENERIC and a GIMPLE variant. */
944 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
946 vec
<operand
*> matchers
= lower_cond (s
->match
);
947 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
949 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
950 s
->result
, s
->result_location
, s
->ifexpr_vec
,
951 s
->for_vec
, s
->capture_ids
);
952 simplifiers
.safe_push (ns
);
956 /* In AST operand O replace operator ID with operator WITH. */
959 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
961 /* Deep-copy captures and expressions, replacing operations as
963 if (capture
*c
= dyn_cast
<capture
*> (o
))
967 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
969 else if (expr
*e
= dyn_cast
<expr
*> (o
))
971 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
973 ne
->expr_type
= e
->expr_type
;
974 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
975 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
979 /* For c_expr we simply record a string replacement table which is
980 applied at code-generation time. */
981 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
983 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
984 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
985 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
991 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
994 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
996 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
997 unsigned worklist_start
= 0;
998 auto_vec
<simplify
*> worklist
;
999 worklist
.safe_push (sin
);
1001 /* Lower each recorded for separately, operating on the
1002 set of simplifiers created by the previous one.
1003 Lower inner-to-outer so inner for substitutes can refer
1004 to operators replaced by outer fors. */
1005 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1007 vec
<user_id
*>& ids
= for_vec
[fi
];
1008 unsigned n_ids
= ids
.length ();
1009 unsigned max_n_opers
= 0;
1010 for (unsigned i
= 0; i
< n_ids
; ++i
)
1011 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1012 max_n_opers
= ids
[i
]->substitutes
.length ();
1014 unsigned worklist_end
= worklist
.length ();
1015 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1017 simplify
*s
= worklist
[si
];
1018 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1020 operand
*match_op
= s
->match
;
1021 operand
*result_op
= s
->result
;
1022 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1024 for (unsigned i
= 0; i
< n_ids
; ++i
)
1026 user_id
*id
= ids
[i
];
1027 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1028 match_op
= replace_id (match_op
, id
, oper
);
1030 result_op
= replace_id (result_op
, id
, oper
);
1031 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1032 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1035 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1036 result_op
, s
->result_location
,
1037 ifexpr_vec
, vNULL
, s
->capture_ids
);
1038 worklist
.safe_push (ns
);
1041 worklist_start
= worklist_end
;
1044 /* Copy out the result from the last for lowering. */
1045 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1046 simplifiers
.safe_push (worklist
[i
]);
1049 /* Lower the AST for everything in SIMPLIFIERS. */
1052 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1054 auto_vec
<simplify
*> out_simplifiers
;
1055 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1056 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1058 simplifiers
.truncate (0);
1059 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1060 lower_commutative (out_simplifiers
[i
], simplifiers
);
1062 out_simplifiers
.truncate (0);
1064 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1065 lower_cond (simplifiers
[i
], out_simplifiers
);
1067 out_simplifiers
.safe_splice (simplifiers
);
1070 simplifiers
.truncate (0);
1071 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1072 lower_for (out_simplifiers
[i
], simplifiers
);
1078 /* The decision tree built for generating GIMPLE and GENERIC pattern
1079 matching code. It represents the 'match' expression of all
1080 simplifies and has those as its leafs. */
1082 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1086 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1090 vec
<dt_node
*> kids
;
1092 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1094 dt_node
*append_node (dt_node
*);
1095 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1096 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1097 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1098 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1100 virtual void gen (FILE *, bool) {}
1102 void gen_kids (FILE *, bool);
1103 void gen_kids_1 (FILE *, bool,
1104 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1105 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1108 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1110 struct dt_operand
: public dt_node
1113 dt_operand
*match_dop
;
1117 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1118 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1119 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1120 parent (parent_
), pos (pos_
) {}
1122 void gen (FILE *, bool);
1123 unsigned gen_predicate (FILE *, const char *, bool);
1124 unsigned gen_match_op (FILE *, const char *);
1126 unsigned gen_gimple_expr (FILE *);
1127 unsigned gen_generic_expr (FILE *, const char *);
1129 char *get_name (char *);
1130 void gen_opname (char *, unsigned);
1133 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1135 struct dt_simplify
: public dt_node
1138 unsigned pattern_no
;
1139 dt_operand
**indexes
;
1141 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1142 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1143 indexes (indexes_
) {}
1145 void gen (FILE *f
, bool);
1151 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1153 return (n
->type
== dt_node::DT_OPERAND
1154 || n
->type
== dt_node::DT_MATCH
);
1157 /* A container for the actual decision tree. */
1159 struct decision_tree
1163 void insert (struct simplify
*, unsigned);
1164 void gen_gimple (FILE *f
= stderr
);
1165 void gen_generic (FILE *f
= stderr
);
1166 void print (FILE *f
= stderr
);
1168 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1170 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1171 unsigned pos
= 0, dt_node
*parent
= 0);
1172 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1173 static bool cmp_node (dt_node
*, dt_node
*);
1174 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1177 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1180 cmp_operand (operand
*o1
, operand
*o2
)
1182 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1185 if (o1
->type
== operand::OP_PREDICATE
)
1187 predicate
*p1
= as_a
<predicate
*>(o1
);
1188 predicate
*p2
= as_a
<predicate
*>(o2
);
1189 return p1
->p
== p2
->p
;
1191 else if (o1
->type
== operand::OP_EXPR
)
1193 expr
*e1
= static_cast<expr
*>(o1
);
1194 expr
*e2
= static_cast<expr
*>(o2
);
1195 return (e1
->operation
== e2
->operation
1196 && e1
->is_generic
== e2
->is_generic
);
1202 /* Compare two decision tree nodes N1 and N2 and return true if they
1206 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1208 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1214 if (n1
->type
== dt_node::DT_TRUE
)
1217 if (n1
->type
== dt_node::DT_OPERAND
)
1218 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1219 (as_a
<dt_operand
*> (n2
))->op
);
1220 else if (n1
->type
== dt_node::DT_MATCH
)
1221 return ((as_a
<dt_operand
*> (n1
))->match_dop
1222 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1226 /* Search OPS for a decision tree node like P and return it if found. */
1229 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1231 /* We can merge adjacent DT_TRUE. */
1232 if (p
->type
== dt_node::DT_TRUE
1234 && ops
.last ()->type
== dt_node::DT_TRUE
)
1236 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1238 /* But we can't merge across DT_TRUE nodes as they serve as
1239 pattern order barriers to make sure that patterns apply
1240 in order of appearance in case multiple matches are possible. */
1241 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1243 if (decision_tree::cmp_node (ops
[i
], p
))
1249 /* Append N to the decision tree if it there is not already an existing
1253 dt_node::append_node (dt_node
*n
)
1257 kid
= decision_tree::find_node (kids
, n
);
1262 n
->level
= this->level
+ 1;
1267 /* Append OP to the decision tree. */
1270 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1272 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1273 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1274 return append_node (n
);
1277 /* Append a DT_TRUE decision tree node. */
1280 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1282 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1283 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1284 return append_node (n
);
1287 /* Append a DT_MATCH decision tree node. */
1290 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1292 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1293 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1294 return append_node (n
);
1297 /* Append S to the decision tree. */
1300 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1301 dt_operand
**indexes
)
1303 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1304 return append_node (n
);
1307 /* Insert O into the decision tree and return the decision tree node found
1311 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1312 unsigned pos
, dt_node
*parent
)
1314 dt_node
*q
, *elm
= 0;
1316 if (capture
*c
= dyn_cast
<capture
*> (o
))
1318 unsigned capt_index
= c
->where
;
1320 if (indexes
[capt_index
] == 0)
1323 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1326 q
= elm
= p
->append_true_op (parent
, pos
);
1329 // get to the last capture
1330 for (operand
*what
= c
->what
;
1331 what
&& is_a
<capture
*> (what
);
1332 c
= as_a
<capture
*> (what
), what
= c
->what
)
1337 unsigned cc_index
= c
->where
;
1338 dt_operand
*match_op
= indexes
[cc_index
];
1340 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1341 elm
= decision_tree::find_node (p
->kids
, &temp
);
1345 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1346 elm
= decision_tree::find_node (p
->kids
, &temp
);
1351 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1352 elm
= decision_tree::find_node (p
->kids
, &temp
);
1356 gcc_assert (elm
->type
== dt_node::DT_TRUE
1357 || elm
->type
== dt_node::DT_OPERAND
1358 || elm
->type
== dt_node::DT_MATCH
);
1359 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1364 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1366 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1371 p
= p
->append_op (o
, parent
, pos
);
1374 if (expr
*e
= dyn_cast
<expr
*>(o
))
1376 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1377 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1383 /* Insert S into the decision tree. */
1386 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1388 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1389 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1390 p
->append_simplify (s
, pattern_no
, indexes
);
1393 /* Debug functions to dump the decision tree. */
1396 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1398 if (p
->type
== dt_node::DT_NODE
)
1399 fprintf (f
, "root");
1403 for (unsigned i
= 0; i
< indent
; i
++)
1406 if (p
->type
== dt_node::DT_OPERAND
)
1408 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1409 print_operand (dop
->op
, f
, true);
1411 else if (p
->type
== dt_node::DT_TRUE
)
1412 fprintf (f
, "true");
1413 else if (p
->type
== dt_node::DT_MATCH
)
1414 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1415 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1417 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1418 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1419 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1420 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1425 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1427 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1428 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1432 decision_tree::print (FILE *f
)
1434 return decision_tree::print_node (root
, f
);
1438 /* For GENERIC we have to take care of wrapping multiple-used
1439 expressions with side-effects in save_expr and preserve side-effects
1440 of expressions with omit_one_operand. Analyze captures in
1441 match, result and with expressions and perform early-outs
1442 on the outermost match expression operands for cases we cannot
1447 capture_info (simplify
*s
);
1448 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1449 void walk_result (operand
*o
, bool);
1450 void walk_c_expr (c_expr
*);
1456 bool force_no_side_effects_p
;
1457 bool cond_expr_cond_p
;
1458 unsigned long toplevel_msk
;
1459 int result_use_count
;
1462 auto_vec
<cinfo
> info
;
1463 unsigned long force_no_side_effects
;
1466 /* Analyze captures in S. */
1468 capture_info::capture_info (simplify
*s
)
1472 || ((e
= dyn_cast
<expr
*> (s
->result
))
1473 && is_a
<predicate_id
*> (e
->operation
)))
1475 force_no_side_effects
= -1;
1479 force_no_side_effects
= 0;
1480 info
.safe_grow_cleared (s
->capture_max
+ 1);
1481 e
= as_a
<expr
*> (s
->match
);
1482 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1483 walk_match (e
->ops
[i
], i
,
1484 (i
!= 0 && *e
->operation
== COND_EXPR
)
1485 || *e
->operation
== TRUTH_ANDIF_EXPR
1486 || *e
->operation
== TRUTH_ORIF_EXPR
,
1488 && (*e
->operation
== COND_EXPR
1489 || *e
->operation
== VEC_COND_EXPR
));
1491 walk_result (s
->result
, false);
1493 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1494 if (s
->ifexpr_vec
[i
].is_with
)
1495 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1498 /* Analyze captures in the match expression piece O. */
1501 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1502 bool conditional_p
, bool cond_expr_cond_p
)
1504 if (capture
*c
= dyn_cast
<capture
*> (o
))
1506 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1507 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1508 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1509 /* Mark expr (non-leaf) captures and recurse. */
1511 && is_a
<expr
*> (c
->what
))
1513 info
[c
->where
].expr_p
= true;
1514 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1517 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1519 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1521 bool cond_p
= conditional_p
;
1522 bool cond_expr_cond_p
= false;
1523 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1525 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1526 || *e
->operation
== TRUTH_ORIF_EXPR
)
1529 && (*e
->operation
== COND_EXPR
1530 || *e
->operation
== VEC_COND_EXPR
))
1531 cond_expr_cond_p
= true;
1532 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1535 else if (is_a
<predicate
*> (o
))
1537 /* Mark non-captured leafs toplevel arg for checking. */
1538 force_no_side_effects
|= 1 << toplevel_arg
;
1544 /* Analyze captures in the result expression piece O. */
1547 capture_info::walk_result (operand
*o
, bool conditional_p
)
1549 if (capture
*c
= dyn_cast
<capture
*> (o
))
1551 info
[c
->where
].result_use_count
++;
1552 /* If we substitute an expression capture we don't know
1553 which captures this will end up using (well, we don't
1554 compute that). Force the uses to be side-effect free
1555 which means forcing the toplevels that reach the
1556 expression side-effect free. */
1557 if (info
[c
->where
].expr_p
)
1558 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1559 /* Mark CSE capture capture uses as forced to have
1562 && is_a
<expr
*> (c
->what
))
1564 info
[c
->where
].cse_p
= true;
1565 walk_result (c
->what
, true);
1568 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1570 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1572 bool cond_p
= conditional_p
;
1573 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1575 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1576 || *e
->operation
== TRUTH_ORIF_EXPR
)
1578 walk_result (e
->ops
[i
], cond_p
);
1581 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1587 /* Look for captures in the C expr E. */
1590 capture_info::walk_c_expr (c_expr
*e
)
1592 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1593 unsigned p_depth
= 0;
1594 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1596 const cpp_token
*t
= &e
->code
[i
];
1597 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1598 if (t
->type
== CPP_NAME
1599 && strcmp ((const char *)CPP_HASHNODE
1600 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1601 && n
->type
== CPP_OPEN_PAREN
)
1603 else if (t
->type
== CPP_CLOSE_PAREN
1606 else if (p_depth
== 0
1607 && t
->type
== CPP_ATSIGN
1608 && (n
->type
== CPP_NUMBER
1609 || n
->type
== CPP_NAME
)
1610 && !(n
->flags
& PREV_WHITE
))
1613 if (n
->type
== CPP_NUMBER
)
1614 id
= (const char *)n
->val
.str
.text
;
1616 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1617 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1623 /* Code generation off the decision tree and the refered AST nodes. */
1626 is_conversion (id_base
*op
)
1628 return (*op
== CONVERT_EXPR
1630 || *op
== FLOAT_EXPR
1631 || *op
== FIX_TRUNC_EXPR
1632 || *op
== VIEW_CONVERT_EXPR
);
1635 /* Get the type to be used for generating operands of OP from the
1639 get_operand_type (id_base
*op
, const char *in_type
,
1640 const char *expr_type
,
1641 const char *other_oprnd_type
)
1643 /* Generally operands whose type does not match the type of the
1644 expression generated need to know their types but match and
1645 thus can fall back to 'other_oprnd_type'. */
1646 if (is_conversion (op
))
1647 return other_oprnd_type
;
1648 else if (*op
== REALPART_EXPR
1649 || *op
== IMAGPART_EXPR
)
1650 return other_oprnd_type
;
1651 else if (is_a
<operator_id
*> (op
)
1652 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1653 return other_oprnd_type
;
1656 /* Otherwise all types should match - choose one in order of
1663 return other_oprnd_type
;
1667 /* Generate transform code for an expression. */
1670 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1671 const char *in_type
, capture_info
*cinfo
,
1672 dt_operand
**indexes
, bool)
1674 bool conversion_p
= is_conversion (operation
);
1675 const char *type
= expr_type
;
1678 /* If there was a type specification in the pattern use it. */
1680 else if (conversion_p
)
1681 /* For conversions we need to build the expression using the
1682 outer type passed in. */
1684 else if (*operation
== REALPART_EXPR
1685 || *operation
== IMAGPART_EXPR
)
1687 /* __real and __imag use the component type of its operand. */
1688 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1691 else if (is_a
<operator_id
*> (operation
)
1692 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1694 /* comparisons use boolean_type_node (or what gets in), but
1695 their operands need to figure out the types themselves. */
1696 sprintf (optype
, "boolean_type_node");
1699 else if (*operation
== COND_EXPR
1700 || *operation
== VEC_COND_EXPR
)
1702 /* Conditions are of the same type as their first alternative. */
1703 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1708 /* Other operations are of the same type as their first operand. */
1709 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1713 fatal ("two conversions in a row");
1716 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1718 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1719 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1722 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1724 = get_operand_type (operation
, in_type
, expr_type
,
1725 i
== 0 ? NULL
: op0type
);
1726 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1727 ((!(*operation
== COND_EXPR
)
1728 && !(*operation
== VEC_COND_EXPR
))
1733 if (*operation
== CONVERT_EXPR
)
1736 opr
= operation
->id
;
1740 /* ??? Building a stmt can fail for various reasons here, seq being
1741 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1742 So if we fail here we should continue matching other patterns. */
1743 fprintf (f
, " code_helper tem_code = %s;\n"
1744 " tree tem_ops[3] = { ", opr
);
1745 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1746 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1747 i
== ops
.length () - 1 ? " };\n" : ", ");
1748 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1749 ops
.length (), type
);
1750 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1751 " if (!res) return false;\n", type
);
1755 if (operation
->kind
== id_base::CODE
)
1756 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1757 ops
.length(), opr
, type
);
1759 fprintf (f
, " res = build_call_expr_loc (loc, "
1760 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1761 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1762 fprintf (f
, ", ops%d[%u]", depth
, i
);
1763 fprintf (f
, ");\n");
1765 fprintf (f
, "%s = res;\n", dest
);
1769 /* Generate code for a c_expr which is either the expression inside
1770 an if statement or a sequence of statements which computes a
1771 result to be stored to DEST. */
1774 c_expr::gen_transform (FILE *f
, const char *dest
,
1775 bool, int, const char *, capture_info
*,
1776 dt_operand
**, bool)
1778 if (dest
&& nr_stmts
== 1)
1779 fprintf (f
, "%s = ", dest
);
1781 unsigned stmt_nr
= 1;
1782 for (unsigned i
= 0; i
< code
.length (); ++i
)
1784 const cpp_token
*token
= &code
[i
];
1786 /* Replace captures for code-gen. */
1787 if (token
->type
== CPP_ATSIGN
)
1789 const cpp_token
*n
= &code
[i
+1];
1790 if ((n
->type
== CPP_NUMBER
1791 || n
->type
== CPP_NAME
)
1792 && !(n
->flags
& PREV_WHITE
))
1794 if (token
->flags
& PREV_WHITE
)
1797 if (n
->type
== CPP_NUMBER
)
1798 id
= (const char *)n
->val
.str
.text
;
1800 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1801 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1807 if (token
->flags
& PREV_WHITE
)
1810 if (token
->type
== CPP_NAME
)
1812 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1814 for (j
= 0; j
< ids
.length (); ++j
)
1816 if (strcmp (id
, ids
[j
].id
) == 0)
1818 fprintf (f
, "%s", ids
[j
].oper
);
1822 if (j
< ids
.length ())
1826 /* Output the token as string. */
1827 char *tk
= (char *)cpp_token_as_text (r
, token
);
1830 if (token
->type
== CPP_SEMICOLON
)
1833 if (dest
&& stmt_nr
== nr_stmts
)
1834 fprintf (f
, "\n %s = ", dest
);
1841 /* Generate transform code for a capture. */
1844 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1845 const char *in_type
, capture_info
*cinfo
,
1846 dt_operand
**indexes
, bool expand_compares
)
1848 if (what
&& is_a
<expr
*> (what
))
1850 if (indexes
[where
] == 0)
1853 sprintf (buf
, "captures[%u]", where
);
1854 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1858 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1860 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1861 with substituting a capture of that.
1862 ??? Returning false here will also not allow any other patterns
1864 if (gimple
&& expand_compares
1865 && cinfo
->info
[where
].cond_expr_cond_p
)
1866 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1868 " if (!seq) return false;\n"
1869 " %s = gimple_build (seq, TREE_CODE (%s),"
1870 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1871 " TREE_OPERAND (%s, 1));\n"
1872 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1875 /* Return the name of the operand representing the decision tree node.
1876 Use NAME as space to generate it. */
1879 dt_operand::get_name (char *name
)
1882 sprintf (name
, "t");
1883 else if (parent
->level
== 1)
1884 sprintf (name
, "op%u", pos
);
1885 else if (parent
->type
== dt_node::DT_MATCH
)
1886 return parent
->get_name (name
);
1888 sprintf (name
, "o%u%u", parent
->level
, pos
);
1892 /* Fill NAME with the operand name at position POS. */
1895 dt_operand::gen_opname (char *name
, unsigned pos
)
1898 sprintf (name
, "op%u", pos
);
1900 sprintf (name
, "o%u%u", level
, pos
);
1903 /* Generate matching code for the decision tree operand which is
1907 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1909 predicate
*p
= as_a
<predicate
*> (op
);
1911 if (p
->p
->matchers
.exists ())
1913 /* If this is a predicate generated from a pattern mangle its
1914 name and pass on the valueize hook. */
1916 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1918 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1921 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1926 /* Generate matching code for the decision tree operand which is
1930 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1932 char match_opname
[20];
1933 match_dop
->get_name (match_opname
);
1934 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1935 opname
, match_opname
, opname
, match_opname
);
1940 /* Generate GIMPLE matching code for the decision tree operand. */
1943 dt_operand::gen_gimple_expr (FILE *f
)
1945 expr
*e
= static_cast<expr
*> (op
);
1946 id_base
*id
= e
->operation
;
1947 unsigned n_ops
= e
->ops
.length ();
1949 for (unsigned i
= 0; i
< n_ops
; ++i
)
1951 char child_opname
[20];
1952 gen_opname (child_opname
, i
);
1954 if (id
->kind
== id_base::CODE
)
1957 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1958 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1960 /* ??? If this is a memory operation we can't (and should not)
1961 match this. The only sensible operand types are
1962 SSA names and invariants. */
1963 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1965 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1966 "|| is_gimple_min_invariant (%s))\n"
1967 "&& (%s = do_valueize (valueize, %s)))\n"
1968 "{\n", child_opname
, child_opname
, child_opname
,
1973 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1974 child_opname
, i
+ 1);
1977 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1979 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1980 child_opname
, child_opname
);
1987 /* Generate GENERIC matching code for the decision tree operand. */
1990 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1992 expr
*e
= static_cast<expr
*> (op
);
1993 unsigned n_ops
= e
->ops
.length ();
1995 for (unsigned i
= 0; i
< n_ops
; ++i
)
1997 char child_opname
[20];
1998 gen_opname (child_opname
, i
);
2000 if (e
->operation
->kind
== id_base::CODE
)
2001 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2002 child_opname
, opname
, i
);
2004 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2005 child_opname
, opname
, i
);
2011 /* Generate matching code for the children of the decision tree node. */
2014 dt_node::gen_kids (FILE *f
, bool gimple
)
2016 auto_vec
<dt_operand
*> gimple_exprs
;
2017 auto_vec
<dt_operand
*> generic_exprs
;
2018 auto_vec
<dt_operand
*> fns
;
2019 auto_vec
<dt_operand
*> generic_fns
;
2020 auto_vec
<dt_operand
*> preds
;
2021 auto_vec
<dt_node
*> others
;
2023 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2025 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2027 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2028 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2030 if (e
->ops
.length () == 0
2031 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2032 generic_exprs
.safe_push (op
);
2033 else if (e
->operation
->kind
== id_base::FN
)
2038 generic_fns
.safe_push (op
);
2040 else if (e
->operation
->kind
== id_base::PREDICATE
)
2041 preds
.safe_push (op
);
2045 gimple_exprs
.safe_push (op
);
2047 generic_exprs
.safe_push (op
);
2050 else if (op
->op
->type
== operand::OP_PREDICATE
)
2051 others
.safe_push (kids
[i
]);
2055 else if (kids
[i
]->type
== dt_node::DT_MATCH
2056 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2057 others
.safe_push (kids
[i
]);
2058 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2060 /* A DT_TRUE operand serves as a barrier - generate code now
2061 for what we have collected sofar. */
2062 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2063 fns
, generic_fns
, preds
, others
);
2064 /* And output the true operand itself. */
2065 kids
[i
]->gen (f
, gimple
);
2066 gimple_exprs
.truncate (0);
2067 generic_exprs
.truncate (0);
2069 generic_fns
.truncate (0);
2071 others
.truncate (0);
2077 /* Generate code for the remains. */
2078 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2079 fns
, generic_fns
, preds
, others
);
2082 /* Generate matching code for the children of the decision tree node. */
2085 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2086 vec
<dt_operand
*> gimple_exprs
,
2087 vec
<dt_operand
*> generic_exprs
,
2088 vec
<dt_operand
*> fns
,
2089 vec
<dt_operand
*> generic_fns
,
2090 vec
<dt_operand
*> preds
,
2091 vec
<dt_node
*> others
)
2094 char *kid_opname
= buf
;
2096 unsigned exprs_len
= gimple_exprs
.length ();
2097 unsigned gexprs_len
= generic_exprs
.length ();
2098 unsigned fns_len
= fns
.length ();
2099 unsigned gfns_len
= generic_fns
.length ();
2101 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2104 gimple_exprs
[0]->get_name (kid_opname
);
2106 fns
[0]->get_name (kid_opname
);
2108 generic_fns
[0]->get_name (kid_opname
);
2110 generic_exprs
[0]->get_name (kid_opname
);
2112 fprintf (f
, "switch (TREE_CODE (%s))\n"
2116 if (exprs_len
|| fns_len
)
2118 fprintf (f
, "case SSA_NAME:\n");
2119 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2121 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2125 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2126 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2128 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2130 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2131 id_base
*op
= e
->operation
;
2132 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2133 fprintf (f
, "CASE_CONVERT:\n");
2135 fprintf (f
, "case %s:\n", op
->id
);
2137 gimple_exprs
[i
]->gen (f
, true);
2138 fprintf (f
, "break;\n"
2141 fprintf (f
, "default:;\n"
2148 fprintf (f
, "else ");
2150 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2152 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2153 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2156 for (unsigned i
= 0; i
< fns_len
; ++i
)
2158 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2159 fprintf (f
, "case %s:\n"
2160 "{\n", e
->operation
->id
);
2161 fns
[i
]->gen (f
, true);
2162 fprintf (f
, "break;\n"
2166 fprintf (f
, "default:;\n"
2175 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2177 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2178 id_base
*op
= e
->operation
;
2179 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2180 fprintf (f
, "CASE_CONVERT:\n");
2182 fprintf (f
, "case %s:\n", op
->id
);
2184 generic_exprs
[i
]->gen (f
, gimple
);
2185 fprintf (f
, "break;\n"
2191 fprintf (f
, "case CALL_EXPR:\n"
2193 "tree fndecl = get_callee_fndecl (%s);\n"
2194 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2195 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2198 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2200 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2201 gcc_assert (e
->operation
->kind
== id_base::FN
);
2203 fprintf (f
, "case %s:\n"
2204 "{\n", e
->operation
->id
);
2205 generic_fns
[j
]->gen (f
, false);
2206 fprintf (f
, "break;\n"
2210 fprintf (f
, "default:;\n"
2216 /* Close switch (TREE_CODE ()). */
2217 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2218 fprintf (f
, "default:;\n"
2221 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2223 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2224 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2225 preds
[i
]->get_name (kid_opname
);
2226 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2227 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2228 gimple
? "gimple" : "tree",
2229 p
->id
, kid_opname
, kid_opname
,
2230 gimple
? ", valueize" : "");
2232 for (int j
= 0; j
< p
->nargs
; ++j
)
2234 char child_opname
[20];
2235 preds
[i
]->gen_opname (child_opname
, j
);
2236 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2238 preds
[i
]->gen_kids (f
, gimple
);
2242 for (unsigned i
= 0; i
< others
.length (); ++i
)
2243 others
[i
]->gen (f
, gimple
);
2246 /* Generate matching code for the decision tree operand. */
2249 dt_operand::gen (FILE *f
, bool gimple
)
2254 unsigned n_braces
= 0;
2256 if (type
== DT_OPERAND
)
2259 case operand::OP_PREDICATE
:
2260 n_braces
= gen_predicate (f
, opname
, gimple
);
2263 case operand::OP_EXPR
:
2265 n_braces
= gen_gimple_expr (f
);
2267 n_braces
= gen_generic_expr (f
, opname
);
2273 else if (type
== DT_TRUE
)
2275 else if (type
== DT_MATCH
)
2276 n_braces
= gen_match_op (f
, opname
);
2280 gen_kids (f
, gimple
);
2282 for (unsigned i
= 0; i
< n_braces
; ++i
)
2288 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2289 step of a '(simplify ...)' or '(match ...)'. This handles everything
2290 that is not part of the decision tree (simplify->match). */
2293 dt_simplify::gen (FILE *f
, bool gimple
)
2296 output_line_directive (f
, s
->result_location
);
2297 if (s
->capture_max
>= 0)
2298 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2299 s
->capture_max
+ 1);
2301 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2305 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2308 unsigned n_braces
= 0;
2309 if (s
->ifexpr_vec
!= vNULL
)
2311 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2313 if_or_with
&w
= s
->ifexpr_vec
[i
];
2317 output_line_directive (f
, w
.location
);
2318 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2323 output_line_directive (f
, w
.location
);
2324 fprintf (f
, "if (");
2325 if (i
== s
->ifexpr_vec
.length () - 1
2326 || s
->ifexpr_vec
[i
+1].is_with
)
2327 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2336 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2340 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2346 while (j
< s
->ifexpr_vec
.length ()
2347 && !s
->ifexpr_vec
[j
].is_with
);
2357 /* Analyze captures and perform early-outs on the incoming arguments
2358 that cover cases we cannot handle. */
2359 capture_info
cinfo (s
);
2363 && !((e
= dyn_cast
<expr
*> (s
->result
))
2364 && is_a
<predicate_id
*> (e
->operation
)))
2366 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2367 if (cinfo
.force_no_side_effects
& (1 << i
))
2368 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2369 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2370 if (cinfo
.info
[i
].cse_p
)
2372 else if (cinfo
.info
[i
].force_no_side_effects_p
2373 && (cinfo
.info
[i
].toplevel_msk
2374 & cinfo
.force_no_side_effects
) == 0)
2375 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2376 "return NULL_TREE;\n", i
);
2377 else if ((cinfo
.info
[i
].toplevel_msk
2378 & cinfo
.force_no_side_effects
) != 0)
2379 /* Mark capture as having no side-effects if we had to verify
2380 that via forced toplevel operand checks. */
2381 cinfo
.info
[i
].force_no_side_effects_p
= true;
2384 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2385 "fprintf (dump_file, \"Applying pattern ");
2386 output_line_directive (f
, s
->result_location
, true);
2387 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2389 operand
*result
= s
->result
;
2392 /* If there is no result then this is a predicate implementation. */
2393 fprintf (f
, "return true;\n");
2397 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2398 in outermost position). */
2399 if (result
->type
== operand::OP_EXPR
2400 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2401 result
= as_a
<expr
*> (result
)->ops
[0];
2402 if (result
->type
== operand::OP_EXPR
)
2404 expr
*e
= as_a
<expr
*> (result
);
2405 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2407 fprintf (f
, "*res_code = %s;\n",
2408 *e
->operation
== CONVERT_EXPR
2409 ? "NOP_EXPR" : e
->operation
->id
);
2410 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2413 snprintf (dest
, 32, " res_ops[%d]", j
);
2415 = get_operand_type (e
->operation
,
2416 "type", e
->expr_type
,
2418 ? NULL
: "TREE_TYPE (res_ops[0])");
2419 /* We need to expand GENERIC conditions we captured from
2421 bool expand_generic_cond_exprs_p
2423 /* But avoid doing that if the GENERIC condition is
2424 valid - which it is in the first operand of COND_EXPRs
2425 and VEC_COND_EXRPs. */
2426 && ((!(*e
->operation
== COND_EXPR
)
2427 && !(*e
->operation
== VEC_COND_EXPR
))
2429 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2430 indexes
, expand_generic_cond_exprs_p
);
2433 /* Re-fold the toplevel result. It's basically an embedded
2434 gimple_build w/o actually building the stmt. */
2436 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2437 "res_ops, valueize);\n", e
->ops
.length ());
2439 else if (result
->type
== operand::OP_CAPTURE
2440 || result
->type
== operand::OP_C_EXPR
)
2442 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2443 &cinfo
, indexes
, false);
2444 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2445 if (is_a
<capture
*> (result
)
2446 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2448 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2449 with substituting a capture of that. */
2450 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2452 " tree tem = res_ops[0];\n"
2453 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2454 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2460 fprintf (f
, "return true;\n");
2464 bool is_predicate
= false;
2465 if (result
->type
== operand::OP_EXPR
)
2467 expr
*e
= as_a
<expr
*> (result
);
2468 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2469 /* Search for captures used multiple times in the result expression
2470 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2472 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2474 if (!cinfo
.info
[i
].force_no_side_effects_p
2475 && cinfo
.info
[i
].result_use_count
> 1)
2476 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2477 " captures[%d] = save_expr (captures[%d]);\n",
2480 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2484 snprintf (dest
, 32, "res_ops[%d]", j
);
2487 fprintf (f
, " tree res_op%d;\n", j
);
2488 snprintf (dest
, 32, " res_op%d", j
);
2491 = get_operand_type (e
->operation
,
2492 "type", e
->expr_type
,
2494 ? NULL
: "TREE_TYPE (res_op0)");
2495 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2499 fprintf (f
, "return true;\n");
2502 fprintf (f
, " tree res;\n");
2503 /* Re-fold the toplevel result. Use non_lvalue to
2504 build NON_LVALUE_EXPRs so they get properly
2505 ignored when in GIMPLE form. */
2506 if (*e
->operation
== NON_LVALUE_EXPR
)
2507 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2510 if (e
->operation
->kind
== id_base::CODE
)
2511 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2513 *e
->operation
== CONVERT_EXPR
2514 ? "NOP_EXPR" : e
->operation
->id
);
2516 fprintf (f
, " res = build_call_expr_loc "
2517 "(loc, builtin_decl_implicit (%s), %d",
2518 e
->operation
->id
, e
->ops
.length());
2519 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2520 fprintf (f
, ", res_op%d", j
);
2521 fprintf (f
, ");\n");
2525 else if (result
->type
== operand::OP_CAPTURE
2526 || result
->type
== operand::OP_C_EXPR
)
2529 fprintf (f
, " tree res;\n");
2530 s
->result
->gen_transform (f
, " res", false, 1, "type",
2537 /* Search for captures not used in the result expression and dependent
2538 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2539 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2541 if (!cinfo
.info
[i
].force_no_side_effects_p
2542 && !cinfo
.info
[i
].expr_p
2543 && cinfo
.info
[i
].result_use_count
== 0)
2544 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2545 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2546 " fold_ignored_result (captures[%d]), res);\n",
2549 fprintf (f
, " return res;\n");
2553 for (unsigned i
= 0; i
< n_braces
; ++i
)
2559 /* Main entry to generate code for matching GIMPLE IL off the decision
2563 decision_tree::gen_gimple (FILE *f
)
2565 for (unsigned n
= 1; n
<= 3; ++n
)
2567 fprintf (f
, "\nstatic bool\n"
2568 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2569 " gimple_seq *seq, tree (*valueize)(tree),\n"
2570 " code_helper code, tree type");
2571 for (unsigned i
= 0; i
< n
; ++i
)
2572 fprintf (f
, ", tree op%d", i
);
2576 fprintf (f
, "switch (code.get_rep())\n"
2578 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2580 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2581 expr
*e
= static_cast<expr
*>(dop
->op
);
2582 if (e
->ops
.length () != n
)
2585 if (*e
->operation
== CONVERT_EXPR
2586 || *e
->operation
== NOP_EXPR
)
2587 fprintf (f
, "CASE_CONVERT:\n");
2589 fprintf (f
, "case %s%s:\n",
2590 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2593 dop
->gen_kids (f
, true);
2594 fprintf (f
, "break;\n");
2597 fprintf (f
, "default:;\n"
2600 fprintf (f
, "return false;\n");
2605 /* Main entry to generate code for matching GENERIC IL off the decision
2609 decision_tree::gen_generic (FILE *f
)
2611 for (unsigned n
= 1; n
<= 3; ++n
)
2613 fprintf (f
, "\ntree\n"
2614 "generic_simplify (location_t loc, enum tree_code code, "
2615 "tree type ATTRIBUTE_UNUSED");
2616 for (unsigned i
= 0; i
< n
; ++i
)
2617 fprintf (f
, ", tree op%d", i
);
2621 fprintf (f
, "switch (code)\n"
2623 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2625 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2626 expr
*e
= static_cast<expr
*>(dop
->op
);
2627 if (e
->ops
.length () != n
2628 /* Builtin simplifications are somewhat premature on
2629 GENERIC. The following drops patterns with outermost
2630 calls. It's easy to emit overloads for function code
2631 though if necessary. */
2632 || e
->operation
->kind
!= id_base::CODE
)
2635 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2636 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2637 fprintf (f
, "CASE_CONVERT:\n");
2639 fprintf (f
, "case %s:\n", e
->operation
->id
);
2641 dop
->gen_kids (f
, false);
2642 fprintf (f
, "break;\n"
2645 fprintf (f
, "default:;\n"
2648 fprintf (f
, "return NULL_TREE;\n");
2653 /* Output code to implement the predicate P from the decision tree DT. */
2656 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2658 fprintf (f
, "\nbool\n"
2659 "%s%s (tree t%s%s)\n"
2660 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2661 p
->nargs
> 0 ? ", tree *res_ops" : "",
2662 gimple
? ", tree (*valueize)(tree)" : "");
2663 /* Conveniently make 'type' available. */
2664 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2667 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2668 dt
.root
->gen_kids (f
, gimple
);
2670 fprintf (f
, "return false;\n"
2674 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2677 write_header (FILE *f
, const char *head
)
2679 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2680 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2682 /* Include the header instead of writing it awkwardly quoted here. */
2683 fprintf (f
, "\n#include \"%s\"\n", head
);
2693 parser (cpp_reader
*);
2696 const cpp_token
*next ();
2697 const cpp_token
*peek ();
2698 const cpp_token
*peek_ident (const char * = NULL
);
2699 const cpp_token
*expect (enum cpp_ttype
);
2700 void eat_token (enum cpp_ttype
);
2701 const char *get_string ();
2702 const char *get_ident ();
2703 void eat_ident (const char *);
2704 const char *get_number ();
2706 id_base
*parse_operation ();
2707 operand
*parse_capture (operand
*);
2708 operand
*parse_expr ();
2709 c_expr
*parse_c_expr (cpp_ttype
);
2710 operand
*parse_op ();
2712 void record_operlist (source_location
, user_id
*);
2714 void parse_pattern ();
2715 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2716 operand
*, source_location
);
2717 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2719 void parse_for (source_location
);
2720 void parse_if (source_location
);
2721 void parse_predicates (source_location
);
2722 void parse_operator_list (source_location
);
2725 vec
<if_or_with
> active_ifs
;
2726 vec
<vec
<user_id
*> > active_fors
;
2727 hash_set
<user_id
*> *oper_lists_set
;
2728 vec
<user_id
*> oper_lists
;
2730 cid_map_t
*capture_ids
;
2733 vec
<simplify
*> simplifiers
;
2734 vec
<predicate_id
*> user_predicates
;
2735 bool parsing_match_operand
;
2738 /* Lexing helpers. */
2740 /* Read the next non-whitespace token from R. */
2745 const cpp_token
*token
;
2748 token
= cpp_get_token (r
);
2750 while (token
->type
== CPP_PADDING
2751 && token
->type
!= CPP_EOF
);
2755 /* Peek at the next non-whitespace token from R. */
2760 const cpp_token
*token
;
2764 token
= cpp_peek_token (r
, i
++);
2766 while (token
->type
== CPP_PADDING
2767 && token
->type
!= CPP_EOF
);
2768 /* If we peek at EOF this is a fatal error as it leaves the
2769 cpp_reader in unusable state. Assume we really wanted a
2770 token and thus this EOF is unexpected. */
2771 if (token
->type
== CPP_EOF
)
2772 fatal_at (token
, "unexpected end of file");
2776 /* Peek at the next identifier token (or return NULL if the next
2777 token is not an identifier or equal to ID if supplied). */
2780 parser::peek_ident (const char *id
)
2782 const cpp_token
*token
= peek ();
2783 if (token
->type
!= CPP_NAME
)
2789 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2790 if (strcmp (id
, t
) == 0)
2796 /* Read the next token from R and assert it is of type TK. */
2799 parser::expect (enum cpp_ttype tk
)
2801 const cpp_token
*token
= next ();
2802 if (token
->type
!= tk
)
2803 fatal_at (token
, "expected %s, got %s",
2804 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2809 /* Consume the next token from R and assert it is of type TK. */
2812 parser::eat_token (enum cpp_ttype tk
)
2817 /* Read the next token from R and assert it is of type CPP_STRING and
2818 return its value. */
2821 parser::get_string ()
2823 const cpp_token
*token
= expect (CPP_STRING
);
2824 return (const char *)token
->val
.str
.text
;
2827 /* Read the next token from R and assert it is of type CPP_NAME and
2828 return its value. */
2831 parser::get_ident ()
2833 const cpp_token
*token
= expect (CPP_NAME
);
2834 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2837 /* Eat an identifier token with value S from R. */
2840 parser::eat_ident (const char *s
)
2842 const cpp_token
*token
= peek ();
2843 const char *t
= get_ident ();
2844 if (strcmp (s
, t
) != 0)
2845 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2848 /* Read the next token from R and assert it is of type CPP_NUMBER and
2849 return its value. */
2852 parser::get_number ()
2854 const cpp_token
*token
= expect (CPP_NUMBER
);
2855 return (const char *)token
->val
.str
.text
;
2859 /* Record an operator-list use for transparent for handling. */
2862 parser::record_operlist (source_location loc
, user_id
*p
)
2864 if (!oper_lists_set
->add (p
))
2866 if (!oper_lists
.is_empty ()
2867 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2868 fatal_at (loc
, "User-defined operator list does not have the "
2869 "same number of entries as others used in the pattern");
2870 oper_lists
.safe_push (p
);
2874 /* Parse the operator ID, special-casing convert?, convert1? and
2878 parser::parse_operation ()
2880 const cpp_token
*id_tok
= peek ();
2881 const char *id
= get_ident ();
2882 const cpp_token
*token
= peek ();
2883 if (strcmp (id
, "convert0") == 0)
2884 fatal_at (id_tok
, "use 'convert?' here");
2885 else if (strcmp (id
, "view_convert0") == 0)
2886 fatal_at (id_tok
, "use 'view_convert?' here");
2887 if (token
->type
== CPP_QUERY
2888 && !(token
->flags
& PREV_WHITE
))
2890 if (strcmp (id
, "convert") == 0)
2892 else if (strcmp (id
, "convert1") == 0)
2894 else if (strcmp (id
, "convert2") == 0)
2896 else if (strcmp (id
, "view_convert") == 0)
2897 id
= "view_convert0";
2898 else if (strcmp (id
, "view_convert1") == 0)
2900 else if (strcmp (id
, "view_convert2") == 0)
2903 fatal_at (id_tok
, "non-convert operator conditionalized");
2905 if (!parsing_match_operand
)
2906 fatal_at (id_tok
, "conditional convert can only be used in "
2907 "match expression");
2908 eat_token (CPP_QUERY
);
2910 else if (strcmp (id
, "convert1") == 0
2911 || strcmp (id
, "convert2") == 0
2912 || strcmp (id
, "view_convert1") == 0
2913 || strcmp (id
, "view_convert2") == 0)
2914 fatal_at (id_tok
, "expected '?' after conditional operator");
2915 id_base
*op
= get_operator (id
);
2917 fatal_at (id_tok
, "unknown operator %s", id
);
2919 user_id
*p
= dyn_cast
<user_id
*> (op
);
2920 if (p
&& p
->is_oper_list
)
2922 if (active_fors
.length() == 0)
2923 record_operlist (id_tok
->src_loc
, p
);
2925 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
2931 capture = '@'<number> */
2934 parser::parse_capture (operand
*op
)
2936 eat_token (CPP_ATSIGN
);
2937 const cpp_token
*token
= peek ();
2938 const char *id
= NULL
;
2939 if (token
->type
== CPP_NUMBER
)
2941 else if (token
->type
== CPP_NAME
)
2944 fatal_at (token
, "expected number or identifier");
2945 unsigned next_id
= capture_ids
->elements ();
2947 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2950 return new capture (num
, op
);
2953 /* Parse an expression
2954 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2957 parser::parse_expr ()
2959 expr
*e
= new expr (parse_operation ());
2960 const cpp_token
*token
= peek ();
2962 bool is_commutative
= false;
2963 const char *expr_type
= NULL
;
2965 if (token
->type
== CPP_COLON
2966 && !(token
->flags
& PREV_WHITE
))
2968 eat_token (CPP_COLON
);
2970 if (token
->type
== CPP_NAME
2971 && !(token
->flags
& PREV_WHITE
))
2973 const char *s
= get_ident ();
2974 if (s
[0] == 'c' && !s
[1])
2976 if (!parsing_match_operand
)
2978 "flag 'c' can only be used in match expression");
2979 is_commutative
= true;
2981 else if (s
[1] != '\0')
2983 if (parsing_match_operand
)
2984 fatal_at (token
, "type can only be used in result expression");
2988 fatal_at (token
, "flag %s not recognized", s
);
2993 fatal_at (token
, "expected flag or type specifying identifier");
2996 if (token
->type
== CPP_ATSIGN
2997 && !(token
->flags
& PREV_WHITE
))
2998 op
= parse_capture (e
);
3003 const cpp_token
*token
= peek ();
3004 if (token
->type
== CPP_CLOSE_PAREN
)
3006 if (e
->operation
->nargs
!= -1
3007 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3008 fatal_at (token
, "'%s' expects %u operands, not %u",
3009 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3012 if (e
->ops
.length () == 2)
3013 e
->is_commutative
= true;
3015 fatal_at (token
, "only binary operators or function with "
3016 "two arguments can be marked commutative");
3018 e
->expr_type
= expr_type
;
3021 e
->append_op (parse_op ());
3026 /* Lex native C code delimited by START recording the preprocessing tokens
3027 for later processing.
3028 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3031 parser::parse_c_expr (cpp_ttype start
)
3033 const cpp_token
*token
;
3036 vec
<cpp_token
> code
= vNULL
;
3037 unsigned nr_stmts
= 0;
3039 if (start
== CPP_OPEN_PAREN
)
3040 end
= CPP_CLOSE_PAREN
;
3041 else if (start
== CPP_OPEN_BRACE
)
3042 end
= CPP_CLOSE_BRACE
;
3050 /* Count brace pairs to find the end of the expr to match. */
3051 if (token
->type
== start
)
3053 else if (token
->type
== end
3057 /* This is a lame way of counting the number of statements. */
3058 if (token
->type
== CPP_SEMICOLON
)
3061 /* If this is possibly a user-defined identifier mark it used. */
3062 if (token
->type
== CPP_NAME
)
3064 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3065 (token
->val
.node
.node
)->ident
.str
);
3067 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3068 record_operlist (token
->src_loc
, p
);
3071 /* Record the token. */
3072 code
.safe_push (*token
);
3075 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3078 /* Parse an operand which is either an expression, a predicate or
3079 a standalone capture.
3080 op = predicate | expr | c_expr | capture */
3085 const cpp_token
*token
= peek ();
3086 struct operand
*op
= NULL
;
3087 if (token
->type
== CPP_OPEN_PAREN
)
3089 eat_token (CPP_OPEN_PAREN
);
3091 eat_token (CPP_CLOSE_PAREN
);
3093 else if (token
->type
== CPP_OPEN_BRACE
)
3095 op
= parse_c_expr (CPP_OPEN_BRACE
);
3099 /* Remaining ops are either empty or predicates */
3100 if (token
->type
== CPP_NAME
)
3102 const char *id
= get_ident ();
3103 id_base
*opr
= get_operator (id
);
3105 fatal_at (token
, "expected predicate name");
3106 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3108 if (code
->nargs
!= 0)
3109 fatal_at (token
, "using an operator with operands as predicate");
3110 /* Parse the zero-operand operator "predicates" as
3112 op
= new expr (opr
);
3114 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3116 if (code
->nargs
!= 0)
3117 fatal_at (token
, "using an operator with operands as predicate");
3118 /* Parse the zero-operand operator "predicates" as
3120 op
= new expr (opr
);
3122 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3123 op
= new predicate (p
);
3125 fatal_at (token
, "using an unsupported operator as predicate");
3126 if (!parsing_match_operand
)
3127 fatal_at (token
, "predicates are only allowed in match expression");
3129 if (token
->flags
& PREV_WHITE
)
3132 else if (token
->type
!= CPP_COLON
3133 && token
->type
!= CPP_ATSIGN
)
3134 fatal_at (token
, "expected expression or predicate");
3135 /* optionally followed by a capture and a predicate. */
3136 if (token
->type
== CPP_COLON
)
3137 fatal_at (token
, "not implemented: predicate on leaf operand");
3138 if (token
->type
== CPP_ATSIGN
)
3139 op
= parse_capture (op
);
3145 /* Create a new simplify from the current parsing state and MATCH,
3146 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3149 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3150 operand
*match
, source_location match_loc
,
3151 operand
*result
, source_location result_loc
)
3153 /* Build and push a temporary for for operator list uses in expressions. */
3154 if (!oper_lists
.is_empty ())
3155 active_fors
.safe_push (oper_lists
);
3157 simplifiers
.safe_push
3158 (new simplify (match
, match_loc
, result
, result_loc
,
3159 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3161 if (!oper_lists
.is_empty ())
3166 simplify = 'simplify' <expr> <result-op>
3168 match = 'match' <ident> <expr> [<result-op>]
3170 <result-op> = <op> | <if> | <with>
3171 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3172 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3173 and fill SIMPLIFIERS with the results. */
3176 parser::parse_simplify (source_location match_location
,
3177 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3180 /* Reset the capture map. */
3182 capture_ids
= new cid_map_t
;
3183 /* Reset oper_lists and set. */
3184 hash_set
<user_id
*> olist
;
3185 oper_lists_set
= &olist
;
3188 const cpp_token
*loc
= peek ();
3189 parsing_match_operand
= true;
3190 struct operand
*match
= parse_op ();
3191 parsing_match_operand
= false;
3192 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3193 fatal_at (loc
, "outermost expression cannot be captured");
3194 if (match
->type
== operand::OP_EXPR
3195 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3196 fatal_at (loc
, "outermost expression cannot be a predicate");
3198 const cpp_token
*token
= peek ();
3200 /* If this if is immediately closed then it is part of a predicate
3201 definition. Push it. */
3202 if (token
->type
== CPP_CLOSE_PAREN
)
3205 fatal_at (token
, "expected transform expression");
3206 push_simplify (simplifiers
, match
, match_location
,
3207 result
, token
->src_loc
);
3211 unsigned active_ifs_len
= active_ifs
.length ();
3214 if (token
->type
== CPP_OPEN_PAREN
)
3216 source_location paren_loc
= token
->src_loc
;
3217 eat_token (CPP_OPEN_PAREN
);
3218 if (peek_ident ("if"))
3221 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3222 token
->src_loc
, false));
3223 /* If this if is immediately closed then it contains a
3224 manual matcher or is part of a predicate definition.
3226 if (peek ()->type
== CPP_CLOSE_PAREN
)
3229 fatal_at (token
, "manual transform not implemented");
3230 push_simplify (simplifiers
, match
, match_location
,
3234 else if (peek_ident ("with"))
3237 /* Parse (with c-expr expr) as (if-with (true) expr). */
3238 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3240 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3244 operand
*op
= result
;
3247 push_simplify (simplifiers
, match
, match_location
,
3248 op
, token
->src_loc
);
3249 eat_token (CPP_CLOSE_PAREN
);
3250 /* A "default" result closes the enclosing scope. */
3251 if (active_ifs
.length () > active_ifs_len
)
3253 eat_token (CPP_CLOSE_PAREN
);
3260 else if (token
->type
== CPP_CLOSE_PAREN
)
3262 /* Close a scope if requested. */
3263 if (active_ifs
.length () > active_ifs_len
)
3265 eat_token (CPP_CLOSE_PAREN
);
3275 fatal_at (token
, "expected match operand expression");
3276 push_simplify (simplifiers
, match
, match_location
,
3277 matcher
? result
: parse_op (), token
->src_loc
);
3278 /* A "default" result closes the enclosing scope. */
3279 if (active_ifs
.length () > active_ifs_len
)
3281 eat_token (CPP_CLOSE_PAREN
);
3291 /* Parsing of the outer control structures. */
3293 /* Parse a for expression
3294 for = '(' 'for' <subst>... <pattern> ')'
3295 subst = <ident> '(' <ident>... ')' */
3298 parser::parse_for (source_location
)
3300 auto_vec
<const cpp_token
*> user_id_tokens
;
3301 vec
<user_id
*> user_ids
= vNULL
;
3302 const cpp_token
*token
;
3303 unsigned min_n_opers
= 0, max_n_opers
= 0;
3308 if (token
->type
!= CPP_NAME
)
3311 /* Insert the user defined operators into the operator hash. */
3312 const char *id
= get_ident ();
3313 if (get_operator (id
) != NULL
)
3314 fatal_at (token
, "operator already defined");
3315 user_id
*op
= new user_id (id
);
3316 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3318 user_ids
.safe_push (op
);
3319 user_id_tokens
.safe_push (token
);
3321 eat_token (CPP_OPEN_PAREN
);
3324 while ((token
= peek_ident ()) != 0)
3326 const char *oper
= get_ident ();
3327 id_base
*idb
= get_operator (oper
);
3329 fatal_at (token
, "no such operator '%s'", oper
);
3330 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3331 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3332 || *idb
== VIEW_CONVERT2
)
3333 fatal_at (token
, "conditional operators cannot be used inside for");
3337 else if (idb
->nargs
== -1)
3339 else if (idb
->nargs
!= arity
)
3340 fatal_at (token
, "operator '%s' with arity %d does not match "
3341 "others with arity %d", oper
, idb
->nargs
, arity
);
3343 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3346 if (p
->is_oper_list
)
3347 op
->substitutes
.safe_splice (p
->substitutes
);
3349 fatal_at (token
, "iterator cannot be used as operator-list");
3352 op
->substitutes
.safe_push (idb
);
3355 token
= expect (CPP_CLOSE_PAREN
);
3357 unsigned nsubstitutes
= op
->substitutes
.length ();
3358 if (nsubstitutes
== 0)
3359 fatal_at (token
, "A user-defined operator must have at least "
3360 "one substitution");
3361 if (max_n_opers
== 0)
3363 min_n_opers
= nsubstitutes
;
3364 max_n_opers
= nsubstitutes
;
3368 if (nsubstitutes
% min_n_opers
!= 0
3369 && min_n_opers
% nsubstitutes
!= 0)
3370 fatal_at (token
, "All user-defined identifiers must have a "
3371 "multiple number of operator substitutions of the "
3372 "smallest number of substitutions");
3373 if (nsubstitutes
< min_n_opers
)
3374 min_n_opers
= nsubstitutes
;
3375 else if (nsubstitutes
> max_n_opers
)
3376 max_n_opers
= nsubstitutes
;
3380 unsigned n_ids
= user_ids
.length ();
3382 fatal_at (token
, "for requires at least one user-defined identifier");
3385 if (token
->type
== CPP_CLOSE_PAREN
)
3386 fatal_at (token
, "no pattern defined in for");
3388 active_fors
.safe_push (user_ids
);
3392 if (token
->type
== CPP_CLOSE_PAREN
)
3398 /* Remove user-defined operators from the hash again. */
3399 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3401 if (!user_ids
[i
]->used
)
3402 warning_at (user_id_tokens
[i
],
3403 "operator %s defined but not used", user_ids
[i
]->id
);
3404 operators
->remove_elt (user_ids
[i
]);
3408 /* Parse an identifier associated with a list of operators.
3409 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3412 parser::parse_operator_list (source_location
)
3414 const cpp_token
*token
= peek ();
3415 const char *id
= get_ident ();
3417 if (get_operator (id
) != 0)
3418 fatal_at (token
, "operator %s already defined", id
);
3420 user_id
*op
= new user_id (id
, true);
3423 while ((token
= peek_ident ()) != 0)
3426 const char *oper
= get_ident ();
3427 id_base
*idb
= get_operator (oper
);
3430 fatal_at (token
, "no such operator '%s'", oper
);
3434 else if (idb
->nargs
== -1)
3436 else if (arity
!= idb
->nargs
)
3437 fatal_at (token
, "operator '%s' with arity %d does not match "
3438 "others with arity %d", oper
, idb
->nargs
, arity
);
3440 /* We allow composition of multiple operator lists. */
3441 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3442 op
->substitutes
.safe_splice (p
->substitutes
);
3444 op
->substitutes
.safe_push (idb
);
3447 // Check that there is no junk after id-list
3449 if (token
->type
!= CPP_CLOSE_PAREN
)
3450 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3452 if (op
->substitutes
.length () == 0)
3453 fatal_at (token
, "operator-list cannot be empty");
3456 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3460 /* Parse an outer if expression.
3461 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3464 parser::parse_if (source_location loc
)
3466 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3468 const cpp_token
*token
= peek ();
3469 if (token
->type
== CPP_CLOSE_PAREN
)
3470 fatal_at (token
, "no pattern defined in if");
3472 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3475 const cpp_token
*token
= peek ();
3476 if (token
->type
== CPP_CLOSE_PAREN
)
3484 /* Parse a list of predefined predicate identifiers.
3485 preds = '(' 'define_predicates' <ident>... ')' */
3488 parser::parse_predicates (source_location
)
3492 const cpp_token
*token
= peek ();
3493 if (token
->type
!= CPP_NAME
)
3496 add_predicate (get_ident ());
3501 /* Parse outer control structures.
3502 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3505 parser::parse_pattern ()
3507 /* All clauses start with '('. */
3508 eat_token (CPP_OPEN_PAREN
);
3509 const cpp_token
*token
= peek ();
3510 const char *id
= get_ident ();
3511 if (strcmp (id
, "simplify") == 0)
3513 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3516 else if (strcmp (id
, "match") == 0)
3518 bool with_args
= false;
3519 if (peek ()->type
== CPP_OPEN_PAREN
)
3521 eat_token (CPP_OPEN_PAREN
);
3524 const char *name
= get_ident ();
3525 id_base
*id
= get_operator (name
);
3529 p
= add_predicate (name
);
3530 user_predicates
.safe_push (p
);
3532 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3535 fatal_at (token
, "cannot add a match to a non-predicate ID");
3536 /* Parse (match <id> <arg>... (match-expr)) here. */
3540 capture_ids
= new cid_map_t
;
3542 while (peek ()->type
== CPP_ATSIGN
)
3543 e
->append_op (parse_capture (NULL
));
3544 eat_token (CPP_CLOSE_PAREN
);
3547 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3548 || (!e
&& p
->nargs
!= 0)))
3549 fatal_at (token
, "non-matching number of match operands");
3550 p
->nargs
= e
? e
->ops
.length () : 0;
3551 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3554 else if (strcmp (id
, "for") == 0)
3555 parse_for (token
->src_loc
);
3556 else if (strcmp (id
, "if") == 0)
3557 parse_if (token
->src_loc
);
3558 else if (strcmp (id
, "define_predicates") == 0)
3560 if (active_ifs
.length () > 0
3561 || active_fors
.length () > 0)
3562 fatal_at (token
, "define_predicates inside if or for is not supported");
3563 parse_predicates (token
->src_loc
);
3565 else if (strcmp (id
, "define_operator_list") == 0)
3567 if (active_ifs
.length () > 0
3568 || active_fors
.length () > 0)
3569 fatal_at (token
, "operator-list inside if or for is not supported");
3570 parse_operator_list (token
->src_loc
);
3573 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3574 active_ifs
.length () == 0 && active_fors
.length () == 0
3575 ? "'define_predicates', " : "");
3577 eat_token (CPP_CLOSE_PAREN
);
3580 /* Main entry of the parser. Repeatedly parse outer control structures. */
3582 parser::parser (cpp_reader
*r_
)
3586 active_fors
= vNULL
;
3587 simplifiers
= vNULL
;
3588 oper_lists_set
= NULL
;
3591 user_predicates
= vNULL
;
3592 parsing_match_operand
= false;
3594 const cpp_token
*token
= next ();
3595 while (token
->type
!= CPP_EOF
)
3597 _cpp_backup_tokens (r
, 1);
3604 /* Helper for the linemap code. */
3607 round_alloc_size (size_t s
)
3613 /* The genmatch generator progam. It reads from a pattern description
3614 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3617 main (int argc
, char **argv
)
3621 progname
= "genmatch";
3627 bool verbose
= false;
3628 char *input
= argv
[argc
-1];
3629 for (int i
= 1; i
< argc
- 1; ++i
)
3631 if (strcmp (argv
[i
], "--gimple") == 0)
3633 else if (strcmp (argv
[i
], "--generic") == 0)
3635 else if (strcmp (argv
[i
], "-v") == 0)
3639 fprintf (stderr
, "Usage: genmatch "
3640 "[--gimple] [--generic] [-v] input\n");
3645 line_table
= XCNEW (struct line_maps
);
3646 linemap_init (line_table
, 0);
3647 line_table
->reallocator
= xrealloc
;
3648 line_table
->round_alloc_size
= round_alloc_size
;
3650 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3651 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3652 cb
->error
= error_cb
;
3654 if (!cpp_read_main_file (r
, input
))
3656 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3657 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3659 /* Pre-seed operators. */
3660 operators
= new hash_table
<id_base
> (1024);
3661 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3662 add_operator (SYM, # SYM, # TYPE, NARGS);
3663 #define END_OF_BASE_TREE_CODES
3665 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3666 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3667 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3668 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
3669 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
3670 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
3671 #undef END_OF_BASE_TREE_CODES
3674 /* Pre-seed builtin functions.
3675 ??? Cannot use N (name) as that is targetm.emultls.get_address
3676 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3677 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3678 add_builtin (ENUM, # ENUM);
3679 #include "builtins.def"
3686 write_header (stdout
, "gimple-match-head.c");
3688 write_header (stdout
, "generic-match-head.c");
3690 /* Go over all predicates defined with patterns and perform
3691 lowering and code generation. */
3692 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3694 predicate_id
*pred
= p
.user_predicates
[i
];
3695 lower (pred
->matchers
, gimple
);
3698 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3699 print_matches (pred
->matchers
[i
]);
3702 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3703 dt
.insert (pred
->matchers
[i
], i
);
3708 write_predicate (stdout
, pred
, dt
, gimple
);
3711 /* Lower the main simplifiers and generate code for them. */
3712 lower (p
.simplifiers
, gimple
);
3715 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3716 print_matches (p
.simplifiers
[i
]);
3719 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3720 dt
.insert (p
.simplifiers
[i
], i
);
3726 dt
.gen_gimple (stdout
);
3728 dt
.gen_generic (stdout
);
3731 cpp_finish (r
, NULL
);