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 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
328 if (code
== ADDR_EXPR
)
330 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
331 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
333 fatal ("duplicate id definition");
337 /* Add a builtin identifier to the hash. */
340 add_builtin (enum built_in_function code
, const char *id
)
342 fn_id
*fn
= new fn_id (code
, id
);
343 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
345 fatal ("duplicate id definition");
349 /* Helper for easy comparing ID with tree code CODE. */
352 operator==(id_base
&id
, enum tree_code code
)
354 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
355 return oid
->code
== code
;
359 /* Lookup the identifier ID. */
362 get_operator (const char *id
)
364 id_base
tem (id_base::CODE
, id
);
366 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
369 /* If this is a user-defined identifier track whether it was used. */
370 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
375 /* Try all-uppercase. */
376 char *id2
= xstrdup (id
);
377 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
378 id2
[i
] = TOUPPER (id2
[i
]);
379 new (&tem
) id_base (id_base::CODE
, id2
);
380 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
387 /* Try _EXPR appended. */
388 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
389 strcat (id2
, "_EXPR");
390 new (&tem
) id_base (id_base::CODE
, id2
);
391 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
401 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
404 /* The AST produced by parsing of the pattern definitions. */
409 /* The base class for operands. */
412 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
413 operand (enum op_type type_
) : type (type_
) {}
415 virtual void gen_transform (FILE *, const char *, bool, int,
416 const char *, capture_info
*,
419 { gcc_unreachable (); }
422 /* A predicate operand. Predicates are leafs in the AST. */
424 struct predicate
: public operand
426 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
430 /* An operand that constitutes an expression. Expressions include
431 function calls and user-defined predicate invocations. */
433 struct expr
: public operand
435 expr (id_base
*operation_
, bool is_commutative_
= false)
436 : operand (OP_EXPR
), operation (operation_
),
437 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
438 is_generic (false) {}
439 void append_op (operand
*op
) { ops
.safe_push (op
); }
440 /* The operator and its operands. */
443 /* An explicitely specified type - used exclusively for conversions. */
444 const char *expr_type
;
445 /* Whether the operation is to be applied commutatively. This is
446 later lowered to two separate patterns. */
448 /* Whether the expression is expected to be in GENERIC form. */
450 virtual void gen_transform (FILE *f
, const char *, bool, int,
451 const char *, capture_info
*,
452 dt_operand
** = 0, bool = true);
455 /* An operator that is represented by native C code. This is always
456 a leaf operand in the AST. This class is also used to represent
457 the code to be generated for 'if' and 'with' expressions. */
459 struct c_expr
: public operand
461 /* A mapping of an identifier and its replacement. Used to apply
466 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
469 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
470 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
471 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
472 nr_stmts (nr_stmts_
), ids (ids_
) {}
473 /* cpplib tokens and state to transform this back to source. */
476 cid_map_t
*capture_ids
;
477 /* The number of statements parsed (well, the number of ';'s). */
479 /* The identifier replacement vector. */
481 virtual void gen_transform (FILE *f
, const char *, bool, int,
482 const char *, capture_info
*,
483 dt_operand
** = 0, bool = true);
486 /* A wrapper around another operand that captures its value. */
488 struct capture
: public operand
490 capture (unsigned where_
, operand
*what_
)
491 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
492 /* Identifier index for the value. */
494 /* The captured value. */
496 virtual void gen_transform (FILE *f
, const char *, bool, int,
497 const char *, capture_info
*,
498 dt_operand
** = 0, bool = true);
504 is_a_helper
<capture
*>::test (operand
*op
)
506 return op
->type
== operand::OP_CAPTURE
;
512 is_a_helper
<predicate
*>::test (operand
*op
)
514 return op
->type
== operand::OP_PREDICATE
;
520 is_a_helper
<c_expr
*>::test (operand
*op
)
522 return op
->type
== operand::OP_C_EXPR
;
528 is_a_helper
<expr
*>::test (operand
*op
)
530 return op
->type
== operand::OP_EXPR
;
533 /* Helper to distinguish 'if' from 'with' expressions. */
537 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
538 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
539 source_location location
;
544 /* The main class of a pattern and its transform. This is used to
545 represent both (simplify ...) and (match ...) kinds. The AST
546 duplicates all outer 'if' and 'for' expressions here so each
547 simplify can exist in isolation. */
551 simplify (operand
*match_
, source_location match_location_
,
552 struct operand
*result_
, source_location result_location_
,
553 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
554 cid_map_t
*capture_ids_
)
555 : match (match_
), match_location (match_location_
),
556 result (result_
), result_location (result_location_
),
557 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
558 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
560 /* The expression that is matched against the GENERIC or GIMPLE IL. */
562 source_location match_location
;
563 /* For a (simplify ...) the expression produced when the pattern applies.
564 For a (match ...) either NULL if it is a simple predicate or the
565 single expression specifying the matched operands. */
566 struct operand
*result
;
567 source_location result_location
;
568 /* Collected 'if' expressions that need to evaluate to true to make
569 the pattern apply. */
570 vec
<if_or_with
> ifexpr_vec
;
571 /* Collected 'for' expression operators that have to be replaced
572 in the lowering phase. */
573 vec
<vec
<user_id
*> > for_vec
;
574 /* A map of capture identifiers to indexes. */
575 cid_map_t
*capture_ids
;
579 /* Debugging routines for dumping the AST. */
582 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
584 if (capture
*c
= dyn_cast
<capture
*> (o
))
586 fprintf (f
, "@%u", c
->where
);
587 if (c
->what
&& flattened
== false)
590 print_operand (c
->what
, f
, flattened
);
595 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
596 fprintf (f
, "%s", p
->p
->id
);
598 else if (is_a
<c_expr
*> (o
))
599 fprintf (f
, "c_expr");
601 else if (expr
*e
= dyn_cast
<expr
*> (o
))
603 fprintf (f
, "(%s", e
->operation
->id
);
605 if (flattened
== false)
608 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
610 print_operand (e
->ops
[i
], f
, flattened
);
622 print_matches (struct simplify
*s
, FILE *f
= stderr
)
624 fprintf (f
, "for expression: ");
625 print_operand (s
->match
, f
);
632 /* Lowering of commutative operators. */
635 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
636 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
638 if (n
== ops_vector
.length ())
640 vec
<operand
*> xv
= v
.copy ();
641 result
.safe_push (xv
);
645 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
647 v
[n
] = ops_vector
[n
][i
];
648 cartesian_product (ops_vector
, result
, v
, n
+ 1);
652 /* Lower OP to two operands in case it is marked as commutative. */
654 static vec
<operand
*>
655 commutate (operand
*op
)
657 vec
<operand
*> ret
= vNULL
;
659 if (capture
*c
= dyn_cast
<capture
*> (op
))
666 vec
<operand
*> v
= commutate (c
->what
);
667 for (unsigned i
= 0; i
< v
.length (); ++i
)
669 capture
*nc
= new capture (c
->where
, v
[i
]);
675 expr
*e
= dyn_cast
<expr
*> (op
);
676 if (!e
|| e
->ops
.length () == 0)
682 vec
< vec
<operand
*> > ops_vector
= vNULL
;
683 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
684 ops_vector
.safe_push (commutate (e
->ops
[i
]));
686 auto_vec
< vec
<operand
*> > result
;
687 auto_vec
<operand
*> v (e
->ops
.length ());
688 v
.quick_grow_cleared (e
->ops
.length ());
689 cartesian_product (ops_vector
, result
, v
, 0);
692 for (unsigned i
= 0; i
< result
.length (); ++i
)
694 expr
*ne
= new expr (e
->operation
);
695 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
696 ne
->append_op (result
[i
][j
]);
700 if (!e
->is_commutative
)
703 for (unsigned i
= 0; i
< result
.length (); ++i
)
705 expr
*ne
= new expr (e
->operation
);
706 // result[i].length () is 2 since e->operation is binary
707 for (unsigned j
= result
[i
].length (); j
; --j
)
708 ne
->append_op (result
[i
][j
-1]);
715 /* Lower operations marked as commutative in the AST of S and push
716 the resulting patterns to SIMPLIFIERS. */
719 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
721 vec
<operand
*> matchers
= commutate (s
->match
);
722 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
724 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
725 s
->result
, s
->result_location
, s
->ifexpr_vec
,
726 s
->for_vec
, s
->capture_ids
);
727 simplifiers
.safe_push (ns
);
731 /* Strip conditional conversios using operator OPER from O and its
732 children if STRIP, else replace them with an unconditional convert. */
735 lower_opt_convert (operand
*o
, enum tree_code oper
,
736 enum tree_code to_oper
, bool strip
)
738 if (capture
*c
= dyn_cast
<capture
*> (o
))
741 return new capture (c
->where
,
742 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
747 expr
*e
= dyn_cast
<expr
*> (o
);
751 if (*e
->operation
== oper
)
754 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
756 expr
*ne
= new expr (to_oper
== CONVERT_EXPR
757 ? get_operator ("CONVERT_EXPR")
758 : get_operator ("VIEW_CONVERT_EXPR"));
759 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
763 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
764 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
765 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
770 /* Determine whether O or its children uses the conditional conversion
774 has_opt_convert (operand
*o
, enum tree_code oper
)
776 if (capture
*c
= dyn_cast
<capture
*> (o
))
779 return has_opt_convert (c
->what
, oper
);
784 expr
*e
= dyn_cast
<expr
*> (o
);
788 if (*e
->operation
== oper
)
791 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
792 if (has_opt_convert (e
->ops
[i
], oper
))
798 /* Lower conditional convert operators in O, expanding it to a vector
801 static vec
<operand
*>
802 lower_opt_convert (operand
*o
)
804 vec
<operand
*> v1
= vNULL
, v2
;
808 enum tree_code opers
[]
809 = { CONVERT0
, CONVERT_EXPR
,
810 CONVERT1
, CONVERT_EXPR
,
811 CONVERT2
, CONVERT_EXPR
,
812 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
813 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
814 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
816 /* Conditional converts are lowered to a pattern with the
817 conversion and one without. The three different conditional
818 convert codes are lowered separately. */
820 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
823 for (unsigned j
= 0; j
< v1
.length (); ++j
)
824 if (has_opt_convert (v1
[j
], opers
[i
]))
826 v2
.safe_push (lower_opt_convert (v1
[j
],
827 opers
[i
], opers
[i
+1], false));
828 v2
.safe_push (lower_opt_convert (v1
[j
],
829 opers
[i
], opers
[i
+1], true));
835 for (unsigned j
= 0; j
< v2
.length (); ++j
)
836 v1
.safe_push (v2
[j
]);
843 /* Lower conditional convert operators in the AST of S and push
844 the resulting multiple patterns to SIMPLIFIERS. */
847 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
849 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
850 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
852 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
853 s
->result
, s
->result_location
, s
->ifexpr_vec
,
854 s
->for_vec
, s
->capture_ids
);
855 simplifiers
.safe_push (ns
);
859 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
860 GENERIC and a GIMPLE variant. */
862 static vec
<operand
*>
863 lower_cond (operand
*o
)
865 vec
<operand
*> ro
= vNULL
;
867 if (capture
*c
= dyn_cast
<capture
*> (o
))
871 vec
<operand
*> lop
= vNULL
;
872 lop
= lower_cond (c
->what
);
874 for (unsigned i
= 0; i
< lop
.length (); ++i
)
875 ro
.safe_push (new capture (c
->where
, lop
[i
]));
880 expr
*e
= dyn_cast
<expr
*> (o
);
881 if (!e
|| e
->ops
.length () == 0)
887 vec
< vec
<operand
*> > ops_vector
= vNULL
;
888 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
889 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
891 auto_vec
< vec
<operand
*> > result
;
892 auto_vec
<operand
*> v (e
->ops
.length ());
893 v
.quick_grow_cleared (e
->ops
.length ());
894 cartesian_product (ops_vector
, result
, v
, 0);
896 for (unsigned i
= 0; i
< result
.length (); ++i
)
898 expr
*ne
= new expr (e
->operation
);
899 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
900 ne
->append_op (result
[i
][j
]);
902 /* If this is a COND with a captured expression or an
903 expression with two operands then also match a GENERIC
904 form on the compare. */
905 if ((*e
->operation
== COND_EXPR
906 || *e
->operation
== VEC_COND_EXPR
)
907 && ((is_a
<capture
*> (e
->ops
[0])
908 && as_a
<capture
*> (e
->ops
[0])->what
909 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
911 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
912 || (is_a
<expr
*> (e
->ops
[0])
913 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
915 expr
*ne
= new expr (e
->operation
);
916 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
917 ne
->append_op (result
[i
][j
]);
918 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
920 expr
*ocmp
= as_a
<expr
*> (c
->what
);
921 expr
*cmp
= new expr (ocmp
->operation
);
922 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
923 cmp
->append_op (ocmp
->ops
[j
]);
924 cmp
->is_generic
= true;
925 ne
->ops
[0] = new capture (c
->where
, cmp
);
929 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
930 expr
*cmp
= new expr (ocmp
->operation
);
931 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
932 cmp
->append_op (ocmp
->ops
[j
]);
933 cmp
->is_generic
= true;
943 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
944 GENERIC and a GIMPLE variant. */
947 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
949 vec
<operand
*> matchers
= lower_cond (s
->match
);
950 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
952 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
953 s
->result
, s
->result_location
, s
->ifexpr_vec
,
954 s
->for_vec
, s
->capture_ids
);
955 simplifiers
.safe_push (ns
);
959 /* In AST operand O replace operator ID with operator WITH. */
962 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
964 /* Deep-copy captures and expressions, replacing operations as
966 if (capture
*c
= dyn_cast
<capture
*> (o
))
970 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
972 else if (expr
*e
= dyn_cast
<expr
*> (o
))
974 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
976 ne
->expr_type
= e
->expr_type
;
977 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
978 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
982 /* For c_expr we simply record a string replacement table which is
983 applied at code-generation time. */
984 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
986 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
987 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
988 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
994 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
997 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
999 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1000 unsigned worklist_start
= 0;
1001 auto_vec
<simplify
*> worklist
;
1002 worklist
.safe_push (sin
);
1004 /* Lower each recorded for separately, operating on the
1005 set of simplifiers created by the previous one.
1006 Lower inner-to-outer so inner for substitutes can refer
1007 to operators replaced by outer fors. */
1008 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1010 vec
<user_id
*>& ids
= for_vec
[fi
];
1011 unsigned n_ids
= ids
.length ();
1012 unsigned max_n_opers
= 0;
1013 for (unsigned i
= 0; i
< n_ids
; ++i
)
1014 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1015 max_n_opers
= ids
[i
]->substitutes
.length ();
1017 unsigned worklist_end
= worklist
.length ();
1018 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1020 simplify
*s
= worklist
[si
];
1021 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1023 operand
*match_op
= s
->match
;
1024 operand
*result_op
= s
->result
;
1025 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1027 for (unsigned i
= 0; i
< n_ids
; ++i
)
1029 user_id
*id
= ids
[i
];
1030 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1031 match_op
= replace_id (match_op
, id
, oper
);
1033 result_op
= replace_id (result_op
, id
, oper
);
1034 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1035 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1038 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1039 result_op
, s
->result_location
,
1040 ifexpr_vec
, vNULL
, s
->capture_ids
);
1041 worklist
.safe_push (ns
);
1044 worklist_start
= worklist_end
;
1047 /* Copy out the result from the last for lowering. */
1048 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1049 simplifiers
.safe_push (worklist
[i
]);
1052 /* Lower the AST for everything in SIMPLIFIERS. */
1055 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1057 auto_vec
<simplify
*> out_simplifiers
;
1058 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1059 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1061 simplifiers
.truncate (0);
1062 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1063 lower_commutative (out_simplifiers
[i
], simplifiers
);
1065 out_simplifiers
.truncate (0);
1067 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1068 lower_cond (simplifiers
[i
], out_simplifiers
);
1070 out_simplifiers
.safe_splice (simplifiers
);
1073 simplifiers
.truncate (0);
1074 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1075 lower_for (out_simplifiers
[i
], simplifiers
);
1081 /* The decision tree built for generating GIMPLE and GENERIC pattern
1082 matching code. It represents the 'match' expression of all
1083 simplifies and has those as its leafs. */
1085 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1089 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1093 vec
<dt_node
*> kids
;
1095 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1097 dt_node
*append_node (dt_node
*);
1098 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1099 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1100 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1101 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1103 virtual void gen (FILE *, bool) {}
1105 void gen_kids (FILE *, bool);
1106 void gen_kids_1 (FILE *, bool,
1107 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1108 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1111 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1113 struct dt_operand
: public dt_node
1116 dt_operand
*match_dop
;
1120 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1121 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1122 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1123 parent (parent_
), pos (pos_
) {}
1125 void gen (FILE *, bool);
1126 unsigned gen_predicate (FILE *, const char *, bool);
1127 unsigned gen_match_op (FILE *, const char *);
1129 unsigned gen_gimple_expr (FILE *);
1130 unsigned gen_generic_expr (FILE *, const char *);
1132 char *get_name (char *);
1133 void gen_opname (char *, unsigned);
1136 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1138 struct dt_simplify
: public dt_node
1141 unsigned pattern_no
;
1142 dt_operand
**indexes
;
1144 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1145 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1146 indexes (indexes_
) {}
1148 void gen (FILE *f
, bool);
1154 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1156 return (n
->type
== dt_node::DT_OPERAND
1157 || n
->type
== dt_node::DT_MATCH
);
1160 /* A container for the actual decision tree. */
1162 struct decision_tree
1166 void insert (struct simplify
*, unsigned);
1167 void gen_gimple (FILE *f
= stderr
);
1168 void gen_generic (FILE *f
= stderr
);
1169 void print (FILE *f
= stderr
);
1171 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1173 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1174 unsigned pos
= 0, dt_node
*parent
= 0);
1175 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1176 static bool cmp_node (dt_node
*, dt_node
*);
1177 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1180 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1183 cmp_operand (operand
*o1
, operand
*o2
)
1185 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1188 if (o1
->type
== operand::OP_PREDICATE
)
1190 predicate
*p1
= as_a
<predicate
*>(o1
);
1191 predicate
*p2
= as_a
<predicate
*>(o2
);
1192 return p1
->p
== p2
->p
;
1194 else if (o1
->type
== operand::OP_EXPR
)
1196 expr
*e1
= static_cast<expr
*>(o1
);
1197 expr
*e2
= static_cast<expr
*>(o2
);
1198 return (e1
->operation
== e2
->operation
1199 && e1
->is_generic
== e2
->is_generic
);
1205 /* Compare two decision tree nodes N1 and N2 and return true if they
1209 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1211 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1217 if (n1
->type
== dt_node::DT_TRUE
)
1220 if (n1
->type
== dt_node::DT_OPERAND
)
1221 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1222 (as_a
<dt_operand
*> (n2
))->op
);
1223 else if (n1
->type
== dt_node::DT_MATCH
)
1224 return ((as_a
<dt_operand
*> (n1
))->match_dop
1225 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1229 /* Search OPS for a decision tree node like P and return it if found. */
1232 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1234 /* We can merge adjacent DT_TRUE. */
1235 if (p
->type
== dt_node::DT_TRUE
1237 && ops
.last ()->type
== dt_node::DT_TRUE
)
1239 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1241 /* But we can't merge across DT_TRUE nodes as they serve as
1242 pattern order barriers to make sure that patterns apply
1243 in order of appearance in case multiple matches are possible. */
1244 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1246 if (decision_tree::cmp_node (ops
[i
], p
))
1252 /* Append N to the decision tree if it there is not already an existing
1256 dt_node::append_node (dt_node
*n
)
1260 kid
= decision_tree::find_node (kids
, n
);
1265 n
->level
= this->level
+ 1;
1270 /* Append OP to the decision tree. */
1273 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1275 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1276 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1277 return append_node (n
);
1280 /* Append a DT_TRUE decision tree node. */
1283 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1285 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1286 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1287 return append_node (n
);
1290 /* Append a DT_MATCH decision tree node. */
1293 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1295 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1296 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1297 return append_node (n
);
1300 /* Append S to the decision tree. */
1303 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1304 dt_operand
**indexes
)
1306 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1307 return append_node (n
);
1310 /* Insert O into the decision tree and return the decision tree node found
1314 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1315 unsigned pos
, dt_node
*parent
)
1317 dt_node
*q
, *elm
= 0;
1319 if (capture
*c
= dyn_cast
<capture
*> (o
))
1321 unsigned capt_index
= c
->where
;
1323 if (indexes
[capt_index
] == 0)
1326 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1329 q
= elm
= p
->append_true_op (parent
, pos
);
1332 // get to the last capture
1333 for (operand
*what
= c
->what
;
1334 what
&& is_a
<capture
*> (what
);
1335 c
= as_a
<capture
*> (what
), what
= c
->what
)
1340 unsigned cc_index
= c
->where
;
1341 dt_operand
*match_op
= indexes
[cc_index
];
1343 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1344 elm
= decision_tree::find_node (p
->kids
, &temp
);
1348 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1349 elm
= decision_tree::find_node (p
->kids
, &temp
);
1354 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1355 elm
= decision_tree::find_node (p
->kids
, &temp
);
1359 gcc_assert (elm
->type
== dt_node::DT_TRUE
1360 || elm
->type
== dt_node::DT_OPERAND
1361 || elm
->type
== dt_node::DT_MATCH
);
1362 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1367 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1369 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1374 p
= p
->append_op (o
, parent
, pos
);
1377 if (expr
*e
= dyn_cast
<expr
*>(o
))
1379 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1380 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1386 /* Insert S into the decision tree. */
1389 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1391 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1392 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1393 p
->append_simplify (s
, pattern_no
, indexes
);
1396 /* Debug functions to dump the decision tree. */
1399 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1401 if (p
->type
== dt_node::DT_NODE
)
1402 fprintf (f
, "root");
1406 for (unsigned i
= 0; i
< indent
; i
++)
1409 if (p
->type
== dt_node::DT_OPERAND
)
1411 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1412 print_operand (dop
->op
, f
, true);
1414 else if (p
->type
== dt_node::DT_TRUE
)
1415 fprintf (f
, "true");
1416 else if (p
->type
== dt_node::DT_MATCH
)
1417 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1418 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1420 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1421 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1422 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1423 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1428 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1430 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1431 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1435 decision_tree::print (FILE *f
)
1437 return decision_tree::print_node (root
, f
);
1441 /* For GENERIC we have to take care of wrapping multiple-used
1442 expressions with side-effects in save_expr and preserve side-effects
1443 of expressions with omit_one_operand. Analyze captures in
1444 match, result and with expressions and perform early-outs
1445 on the outermost match expression operands for cases we cannot
1450 capture_info (simplify
*s
);
1451 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1452 void walk_result (operand
*o
, bool);
1453 void walk_c_expr (c_expr
*);
1459 bool force_no_side_effects_p
;
1460 bool cond_expr_cond_p
;
1461 unsigned long toplevel_msk
;
1462 int result_use_count
;
1465 auto_vec
<cinfo
> info
;
1466 unsigned long force_no_side_effects
;
1469 /* Analyze captures in S. */
1471 capture_info::capture_info (simplify
*s
)
1475 || ((e
= dyn_cast
<expr
*> (s
->result
))
1476 && is_a
<predicate_id
*> (e
->operation
)))
1478 force_no_side_effects
= -1;
1482 force_no_side_effects
= 0;
1483 info
.safe_grow_cleared (s
->capture_max
+ 1);
1484 e
= as_a
<expr
*> (s
->match
);
1485 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1486 walk_match (e
->ops
[i
], i
,
1487 (i
!= 0 && *e
->operation
== COND_EXPR
)
1488 || *e
->operation
== TRUTH_ANDIF_EXPR
1489 || *e
->operation
== TRUTH_ORIF_EXPR
,
1491 && (*e
->operation
== COND_EXPR
1492 || *e
->operation
== VEC_COND_EXPR
));
1494 walk_result (s
->result
, false);
1496 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1497 if (s
->ifexpr_vec
[i
].is_with
)
1498 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1501 /* Analyze captures in the match expression piece O. */
1504 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1505 bool conditional_p
, bool cond_expr_cond_p
)
1507 if (capture
*c
= dyn_cast
<capture
*> (o
))
1509 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1510 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1511 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1512 /* Mark expr (non-leaf) captures and recurse. */
1514 && is_a
<expr
*> (c
->what
))
1516 info
[c
->where
].expr_p
= true;
1517 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1520 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1522 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1524 bool cond_p
= conditional_p
;
1525 bool cond_expr_cond_p
= false;
1526 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1528 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1529 || *e
->operation
== TRUTH_ORIF_EXPR
)
1532 && (*e
->operation
== COND_EXPR
1533 || *e
->operation
== VEC_COND_EXPR
))
1534 cond_expr_cond_p
= true;
1535 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1538 else if (is_a
<predicate
*> (o
))
1540 /* Mark non-captured leafs toplevel arg for checking. */
1541 force_no_side_effects
|= 1 << toplevel_arg
;
1547 /* Analyze captures in the result expression piece O. */
1550 capture_info::walk_result (operand
*o
, bool conditional_p
)
1552 if (capture
*c
= dyn_cast
<capture
*> (o
))
1554 info
[c
->where
].result_use_count
++;
1555 /* If we substitute an expression capture we don't know
1556 which captures this will end up using (well, we don't
1557 compute that). Force the uses to be side-effect free
1558 which means forcing the toplevels that reach the
1559 expression side-effect free. */
1560 if (info
[c
->where
].expr_p
)
1561 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1562 /* Mark CSE capture capture uses as forced to have
1565 && is_a
<expr
*> (c
->what
))
1567 info
[c
->where
].cse_p
= true;
1568 walk_result (c
->what
, true);
1571 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1573 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1575 bool cond_p
= conditional_p
;
1576 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1578 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1579 || *e
->operation
== TRUTH_ORIF_EXPR
)
1581 walk_result (e
->ops
[i
], cond_p
);
1584 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1590 /* Look for captures in the C expr E. */
1593 capture_info::walk_c_expr (c_expr
*e
)
1595 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1596 unsigned p_depth
= 0;
1597 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1599 const cpp_token
*t
= &e
->code
[i
];
1600 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1601 if (t
->type
== CPP_NAME
1602 && strcmp ((const char *)CPP_HASHNODE
1603 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1604 && n
->type
== CPP_OPEN_PAREN
)
1606 else if (t
->type
== CPP_CLOSE_PAREN
1609 else if (p_depth
== 0
1610 && t
->type
== CPP_ATSIGN
1611 && (n
->type
== CPP_NUMBER
1612 || n
->type
== CPP_NAME
)
1613 && !(n
->flags
& PREV_WHITE
))
1616 if (n
->type
== CPP_NUMBER
)
1617 id
= (const char *)n
->val
.str
.text
;
1619 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1620 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1626 /* Code generation off the decision tree and the refered AST nodes. */
1629 is_conversion (id_base
*op
)
1631 return (*op
== CONVERT_EXPR
1633 || *op
== FLOAT_EXPR
1634 || *op
== FIX_TRUNC_EXPR
1635 || *op
== VIEW_CONVERT_EXPR
);
1638 /* Get the type to be used for generating operands of OP from the
1642 get_operand_type (id_base
*op
, const char *in_type
,
1643 const char *expr_type
,
1644 const char *other_oprnd_type
)
1646 /* Generally operands whose type does not match the type of the
1647 expression generated need to know their types but match and
1648 thus can fall back to 'other_oprnd_type'. */
1649 if (is_conversion (op
))
1650 return other_oprnd_type
;
1651 else if (*op
== REALPART_EXPR
1652 || *op
== IMAGPART_EXPR
)
1653 return other_oprnd_type
;
1654 else if (is_a
<operator_id
*> (op
)
1655 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1656 return other_oprnd_type
;
1659 /* Otherwise all types should match - choose one in order of
1666 return other_oprnd_type
;
1670 /* Generate transform code for an expression. */
1673 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1674 const char *in_type
, capture_info
*cinfo
,
1675 dt_operand
**indexes
, bool)
1677 bool conversion_p
= is_conversion (operation
);
1678 const char *type
= expr_type
;
1681 /* If there was a type specification in the pattern use it. */
1683 else if (conversion_p
)
1684 /* For conversions we need to build the expression using the
1685 outer type passed in. */
1687 else if (*operation
== REALPART_EXPR
1688 || *operation
== IMAGPART_EXPR
)
1690 /* __real and __imag use the component type of its operand. */
1691 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1694 else if (is_a
<operator_id
*> (operation
)
1695 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1697 /* comparisons use boolean_type_node (or what gets in), but
1698 their operands need to figure out the types themselves. */
1699 sprintf (optype
, "boolean_type_node");
1702 else if (*operation
== COND_EXPR
1703 || *operation
== VEC_COND_EXPR
)
1705 /* Conditions are of the same type as their first alternative. */
1706 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1711 /* Other operations are of the same type as their first operand. */
1712 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1716 fatal ("two conversions in a row");
1719 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1721 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1722 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1725 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1727 = get_operand_type (operation
, in_type
, expr_type
,
1728 i
== 0 ? NULL
: op0type
);
1729 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1730 ((!(*operation
== COND_EXPR
)
1731 && !(*operation
== VEC_COND_EXPR
))
1736 if (*operation
== CONVERT_EXPR
)
1739 opr
= operation
->id
;
1743 /* ??? Building a stmt can fail for various reasons here, seq being
1744 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1745 So if we fail here we should continue matching other patterns. */
1746 fprintf (f
, " code_helper tem_code = %s;\n"
1747 " tree tem_ops[3] = { ", opr
);
1748 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1749 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1750 i
== ops
.length () - 1 ? " };\n" : ", ");
1751 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1752 ops
.length (), type
);
1753 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1754 " if (!res) return false;\n", type
);
1758 if (operation
->kind
== id_base::CODE
)
1759 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1760 ops
.length(), opr
, type
);
1762 fprintf (f
, " res = build_call_expr_loc (loc, "
1763 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1764 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1765 fprintf (f
, ", ops%d[%u]", depth
, i
);
1766 fprintf (f
, ");\n");
1768 fprintf (f
, "%s = res;\n", dest
);
1772 /* Generate code for a c_expr which is either the expression inside
1773 an if statement or a sequence of statements which computes a
1774 result to be stored to DEST. */
1777 c_expr::gen_transform (FILE *f
, const char *dest
,
1778 bool, int, const char *, capture_info
*,
1779 dt_operand
**, bool)
1781 if (dest
&& nr_stmts
== 1)
1782 fprintf (f
, "%s = ", dest
);
1784 unsigned stmt_nr
= 1;
1785 for (unsigned i
= 0; i
< code
.length (); ++i
)
1787 const cpp_token
*token
= &code
[i
];
1789 /* Replace captures for code-gen. */
1790 if (token
->type
== CPP_ATSIGN
)
1792 const cpp_token
*n
= &code
[i
+1];
1793 if ((n
->type
== CPP_NUMBER
1794 || n
->type
== CPP_NAME
)
1795 && !(n
->flags
& PREV_WHITE
))
1797 if (token
->flags
& PREV_WHITE
)
1800 if (n
->type
== CPP_NUMBER
)
1801 id
= (const char *)n
->val
.str
.text
;
1803 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1804 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1810 if (token
->flags
& PREV_WHITE
)
1813 if (token
->type
== CPP_NAME
)
1815 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1817 for (j
= 0; j
< ids
.length (); ++j
)
1819 if (strcmp (id
, ids
[j
].id
) == 0)
1821 fprintf (f
, "%s", ids
[j
].oper
);
1825 if (j
< ids
.length ())
1829 /* Output the token as string. */
1830 char *tk
= (char *)cpp_token_as_text (r
, token
);
1833 if (token
->type
== CPP_SEMICOLON
)
1836 if (dest
&& stmt_nr
== nr_stmts
)
1837 fprintf (f
, "\n %s = ", dest
);
1844 /* Generate transform code for a capture. */
1847 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1848 const char *in_type
, capture_info
*cinfo
,
1849 dt_operand
**indexes
, bool expand_compares
)
1851 if (what
&& is_a
<expr
*> (what
))
1853 if (indexes
[where
] == 0)
1856 sprintf (buf
, "captures[%u]", where
);
1857 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1861 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1863 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1864 with substituting a capture of that.
1865 ??? Returning false here will also not allow any other patterns
1867 if (gimple
&& expand_compares
1868 && cinfo
->info
[where
].cond_expr_cond_p
)
1869 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1871 " if (!seq) return false;\n"
1872 " %s = gimple_build (seq, TREE_CODE (%s),"
1873 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1874 " TREE_OPERAND (%s, 1));\n"
1875 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1878 /* Return the name of the operand representing the decision tree node.
1879 Use NAME as space to generate it. */
1882 dt_operand::get_name (char *name
)
1885 sprintf (name
, "t");
1886 else if (parent
->level
== 1)
1887 sprintf (name
, "op%u", pos
);
1888 else if (parent
->type
== dt_node::DT_MATCH
)
1889 return parent
->get_name (name
);
1891 sprintf (name
, "o%u%u", parent
->level
, pos
);
1895 /* Fill NAME with the operand name at position POS. */
1898 dt_operand::gen_opname (char *name
, unsigned pos
)
1901 sprintf (name
, "op%u", pos
);
1903 sprintf (name
, "o%u%u", level
, pos
);
1906 /* Generate matching code for the decision tree operand which is
1910 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1912 predicate
*p
= as_a
<predicate
*> (op
);
1914 if (p
->p
->matchers
.exists ())
1916 /* If this is a predicate generated from a pattern mangle its
1917 name and pass on the valueize hook. */
1919 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1921 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1924 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1929 /* Generate matching code for the decision tree operand which is
1933 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1935 char match_opname
[20];
1936 match_dop
->get_name (match_opname
);
1937 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1938 opname
, match_opname
, opname
, match_opname
);
1943 /* Generate GIMPLE matching code for the decision tree operand. */
1946 dt_operand::gen_gimple_expr (FILE *f
)
1948 expr
*e
= static_cast<expr
*> (op
);
1949 id_base
*id
= e
->operation
;
1950 unsigned n_ops
= e
->ops
.length ();
1952 for (unsigned i
= 0; i
< n_ops
; ++i
)
1954 char child_opname
[20];
1955 gen_opname (child_opname
, i
);
1957 if (id
->kind
== id_base::CODE
)
1960 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1961 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1963 /* ??? If this is a memory operation we can't (and should not)
1964 match this. The only sensible operand types are
1965 SSA names and invariants. */
1966 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1968 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1969 "|| is_gimple_min_invariant (%s))\n"
1970 "&& (%s = do_valueize (valueize, %s)))\n"
1971 "{\n", child_opname
, child_opname
, child_opname
,
1976 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1977 child_opname
, i
+ 1);
1980 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1982 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1983 child_opname
, child_opname
);
1990 /* Generate GENERIC matching code for the decision tree operand. */
1993 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1995 expr
*e
= static_cast<expr
*> (op
);
1996 unsigned n_ops
= e
->ops
.length ();
1998 for (unsigned i
= 0; i
< n_ops
; ++i
)
2000 char child_opname
[20];
2001 gen_opname (child_opname
, i
);
2003 if (e
->operation
->kind
== id_base::CODE
)
2004 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2005 child_opname
, opname
, i
);
2007 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2008 child_opname
, opname
, i
);
2014 /* Generate matching code for the children of the decision tree node. */
2017 dt_node::gen_kids (FILE *f
, bool gimple
)
2019 auto_vec
<dt_operand
*> gimple_exprs
;
2020 auto_vec
<dt_operand
*> generic_exprs
;
2021 auto_vec
<dt_operand
*> fns
;
2022 auto_vec
<dt_operand
*> generic_fns
;
2023 auto_vec
<dt_operand
*> preds
;
2024 auto_vec
<dt_node
*> others
;
2026 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2028 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2030 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2031 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2033 if (e
->ops
.length () == 0
2034 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2035 generic_exprs
.safe_push (op
);
2036 else if (e
->operation
->kind
== id_base::FN
)
2041 generic_fns
.safe_push (op
);
2043 else if (e
->operation
->kind
== id_base::PREDICATE
)
2044 preds
.safe_push (op
);
2048 gimple_exprs
.safe_push (op
);
2050 generic_exprs
.safe_push (op
);
2053 else if (op
->op
->type
== operand::OP_PREDICATE
)
2054 others
.safe_push (kids
[i
]);
2058 else if (kids
[i
]->type
== dt_node::DT_MATCH
2059 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2060 others
.safe_push (kids
[i
]);
2061 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2063 /* A DT_TRUE operand serves as a barrier - generate code now
2064 for what we have collected sofar. */
2065 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2066 fns
, generic_fns
, preds
, others
);
2067 /* And output the true operand itself. */
2068 kids
[i
]->gen (f
, gimple
);
2069 gimple_exprs
.truncate (0);
2070 generic_exprs
.truncate (0);
2072 generic_fns
.truncate (0);
2074 others
.truncate (0);
2080 /* Generate code for the remains. */
2081 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2082 fns
, generic_fns
, preds
, others
);
2085 /* Generate matching code for the children of the decision tree node. */
2088 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2089 vec
<dt_operand
*> gimple_exprs
,
2090 vec
<dt_operand
*> generic_exprs
,
2091 vec
<dt_operand
*> fns
,
2092 vec
<dt_operand
*> generic_fns
,
2093 vec
<dt_operand
*> preds
,
2094 vec
<dt_node
*> others
)
2097 char *kid_opname
= buf
;
2099 unsigned exprs_len
= gimple_exprs
.length ();
2100 unsigned gexprs_len
= generic_exprs
.length ();
2101 unsigned fns_len
= fns
.length ();
2102 unsigned gfns_len
= generic_fns
.length ();
2104 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2107 gimple_exprs
[0]->get_name (kid_opname
);
2109 fns
[0]->get_name (kid_opname
);
2111 generic_fns
[0]->get_name (kid_opname
);
2113 generic_exprs
[0]->get_name (kid_opname
);
2115 fprintf (f
, "switch (TREE_CODE (%s))\n"
2119 if (exprs_len
|| fns_len
)
2121 fprintf (f
, "case SSA_NAME:\n");
2122 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2124 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2128 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2129 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2131 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2133 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2134 id_base
*op
= e
->operation
;
2135 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2136 fprintf (f
, "CASE_CONVERT:\n");
2138 fprintf (f
, "case %s:\n", op
->id
);
2140 gimple_exprs
[i
]->gen (f
, true);
2141 fprintf (f
, "break;\n"
2144 fprintf (f
, "default:;\n"
2151 fprintf (f
, "else ");
2153 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2155 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2156 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2159 for (unsigned i
= 0; i
< fns_len
; ++i
)
2161 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2162 fprintf (f
, "case %s:\n"
2163 "{\n", e
->operation
->id
);
2164 fns
[i
]->gen (f
, true);
2165 fprintf (f
, "break;\n"
2169 fprintf (f
, "default:;\n"
2178 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2180 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2181 id_base
*op
= e
->operation
;
2182 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2183 fprintf (f
, "CASE_CONVERT:\n");
2185 fprintf (f
, "case %s:\n", op
->id
);
2187 generic_exprs
[i
]->gen (f
, gimple
);
2188 fprintf (f
, "break;\n"
2194 fprintf (f
, "case CALL_EXPR:\n"
2196 "tree fndecl = get_callee_fndecl (%s);\n"
2197 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2198 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2201 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2203 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2204 gcc_assert (e
->operation
->kind
== id_base::FN
);
2206 fprintf (f
, "case %s:\n"
2207 "{\n", e
->operation
->id
);
2208 generic_fns
[j
]->gen (f
, false);
2209 fprintf (f
, "break;\n"
2213 fprintf (f
, "default:;\n"
2219 /* Close switch (TREE_CODE ()). */
2220 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2221 fprintf (f
, "default:;\n"
2224 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2226 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2227 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2228 preds
[i
]->get_name (kid_opname
);
2229 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2230 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2231 gimple
? "gimple" : "tree",
2232 p
->id
, kid_opname
, kid_opname
,
2233 gimple
? ", valueize" : "");
2235 for (int j
= 0; j
< p
->nargs
; ++j
)
2237 char child_opname
[20];
2238 preds
[i
]->gen_opname (child_opname
, j
);
2239 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2241 preds
[i
]->gen_kids (f
, gimple
);
2245 for (unsigned i
= 0; i
< others
.length (); ++i
)
2246 others
[i
]->gen (f
, gimple
);
2249 /* Generate matching code for the decision tree operand. */
2252 dt_operand::gen (FILE *f
, bool gimple
)
2257 unsigned n_braces
= 0;
2259 if (type
== DT_OPERAND
)
2262 case operand::OP_PREDICATE
:
2263 n_braces
= gen_predicate (f
, opname
, gimple
);
2266 case operand::OP_EXPR
:
2268 n_braces
= gen_gimple_expr (f
);
2270 n_braces
= gen_generic_expr (f
, opname
);
2276 else if (type
== DT_TRUE
)
2278 else if (type
== DT_MATCH
)
2279 n_braces
= gen_match_op (f
, opname
);
2283 gen_kids (f
, gimple
);
2285 for (unsigned i
= 0; i
< n_braces
; ++i
)
2291 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2292 step of a '(simplify ...)' or '(match ...)'. This handles everything
2293 that is not part of the decision tree (simplify->match). */
2296 dt_simplify::gen (FILE *f
, bool gimple
)
2299 output_line_directive (f
, s
->result_location
);
2300 if (s
->capture_max
>= 0)
2301 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2302 s
->capture_max
+ 1);
2304 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2308 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2311 unsigned n_braces
= 0;
2312 if (s
->ifexpr_vec
!= vNULL
)
2314 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2316 if_or_with
&w
= s
->ifexpr_vec
[i
];
2320 output_line_directive (f
, w
.location
);
2321 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2326 output_line_directive (f
, w
.location
);
2327 fprintf (f
, "if (");
2328 if (i
== s
->ifexpr_vec
.length () - 1
2329 || s
->ifexpr_vec
[i
+1].is_with
)
2330 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2339 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2343 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2349 while (j
< s
->ifexpr_vec
.length ()
2350 && !s
->ifexpr_vec
[j
].is_with
);
2360 /* Analyze captures and perform early-outs on the incoming arguments
2361 that cover cases we cannot handle. */
2362 capture_info
cinfo (s
);
2366 && !((e
= dyn_cast
<expr
*> (s
->result
))
2367 && is_a
<predicate_id
*> (e
->operation
)))
2369 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2370 if (cinfo
.force_no_side_effects
& (1 << i
))
2371 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2372 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2373 if (cinfo
.info
[i
].cse_p
)
2375 else if (cinfo
.info
[i
].force_no_side_effects_p
2376 && (cinfo
.info
[i
].toplevel_msk
2377 & cinfo
.force_no_side_effects
) == 0)
2378 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2379 "return NULL_TREE;\n", i
);
2380 else if ((cinfo
.info
[i
].toplevel_msk
2381 & cinfo
.force_no_side_effects
) != 0)
2382 /* Mark capture as having no side-effects if we had to verify
2383 that via forced toplevel operand checks. */
2384 cinfo
.info
[i
].force_no_side_effects_p
= true;
2387 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2388 "fprintf (dump_file, \"Applying pattern ");
2389 output_line_directive (f
, s
->result_location
, true);
2390 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2392 operand
*result
= s
->result
;
2395 /* If there is no result then this is a predicate implementation. */
2396 fprintf (f
, "return true;\n");
2400 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2401 in outermost position). */
2402 if (result
->type
== operand::OP_EXPR
2403 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2404 result
= as_a
<expr
*> (result
)->ops
[0];
2405 if (result
->type
== operand::OP_EXPR
)
2407 expr
*e
= as_a
<expr
*> (result
);
2408 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2410 fprintf (f
, "*res_code = %s;\n",
2411 *e
->operation
== CONVERT_EXPR
2412 ? "NOP_EXPR" : e
->operation
->id
);
2413 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2416 snprintf (dest
, 32, " res_ops[%d]", j
);
2418 = get_operand_type (e
->operation
,
2419 "type", e
->expr_type
,
2421 ? NULL
: "TREE_TYPE (res_ops[0])");
2422 /* We need to expand GENERIC conditions we captured from
2424 bool expand_generic_cond_exprs_p
2426 /* But avoid doing that if the GENERIC condition is
2427 valid - which it is in the first operand of COND_EXPRs
2428 and VEC_COND_EXRPs. */
2429 && ((!(*e
->operation
== COND_EXPR
)
2430 && !(*e
->operation
== VEC_COND_EXPR
))
2432 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2433 indexes
, expand_generic_cond_exprs_p
);
2436 /* Re-fold the toplevel result. It's basically an embedded
2437 gimple_build w/o actually building the stmt. */
2439 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2440 "res_ops, valueize);\n", e
->ops
.length ());
2442 else if (result
->type
== operand::OP_CAPTURE
2443 || result
->type
== operand::OP_C_EXPR
)
2445 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2446 &cinfo
, indexes
, false);
2447 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2448 if (is_a
<capture
*> (result
)
2449 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2451 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2452 with substituting a capture of that. */
2453 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2455 " tree tem = res_ops[0];\n"
2456 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2457 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2463 fprintf (f
, "return true;\n");
2467 bool is_predicate
= false;
2468 if (result
->type
== operand::OP_EXPR
)
2470 expr
*e
= as_a
<expr
*> (result
);
2471 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2472 /* Search for captures used multiple times in the result expression
2473 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2475 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2477 if (!cinfo
.info
[i
].force_no_side_effects_p
2478 && cinfo
.info
[i
].result_use_count
> 1)
2479 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2480 " captures[%d] = save_expr (captures[%d]);\n",
2483 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2487 snprintf (dest
, 32, "res_ops[%d]", j
);
2490 fprintf (f
, " tree res_op%d;\n", j
);
2491 snprintf (dest
, 32, " res_op%d", j
);
2494 = get_operand_type (e
->operation
,
2495 "type", e
->expr_type
,
2497 ? NULL
: "TREE_TYPE (res_op0)");
2498 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2502 fprintf (f
, "return true;\n");
2505 fprintf (f
, " tree res;\n");
2506 /* Re-fold the toplevel result. Use non_lvalue to
2507 build NON_LVALUE_EXPRs so they get properly
2508 ignored when in GIMPLE form. */
2509 if (*e
->operation
== NON_LVALUE_EXPR
)
2510 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2513 if (e
->operation
->kind
== id_base::CODE
)
2514 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2516 *e
->operation
== CONVERT_EXPR
2517 ? "NOP_EXPR" : e
->operation
->id
);
2519 fprintf (f
, " res = build_call_expr_loc "
2520 "(loc, builtin_decl_implicit (%s), %d",
2521 e
->operation
->id
, e
->ops
.length());
2522 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2523 fprintf (f
, ", res_op%d", j
);
2524 fprintf (f
, ");\n");
2528 else if (result
->type
== operand::OP_CAPTURE
2529 || result
->type
== operand::OP_C_EXPR
)
2532 fprintf (f
, " tree res;\n");
2533 s
->result
->gen_transform (f
, " res", false, 1, "type",
2540 /* Search for captures not used in the result expression and dependent
2541 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2542 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2544 if (!cinfo
.info
[i
].force_no_side_effects_p
2545 && !cinfo
.info
[i
].expr_p
2546 && cinfo
.info
[i
].result_use_count
== 0)
2547 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2548 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2549 " fold_ignored_result (captures[%d]), res);\n",
2552 fprintf (f
, " return res;\n");
2556 for (unsigned i
= 0; i
< n_braces
; ++i
)
2562 /* Main entry to generate code for matching GIMPLE IL off the decision
2566 decision_tree::gen_gimple (FILE *f
)
2568 for (unsigned n
= 1; n
<= 3; ++n
)
2570 fprintf (f
, "\nstatic bool\n"
2571 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2572 " gimple_seq *seq, tree (*valueize)(tree),\n"
2573 " code_helper code, tree type");
2574 for (unsigned i
= 0; i
< n
; ++i
)
2575 fprintf (f
, ", tree op%d", i
);
2579 fprintf (f
, "switch (code.get_rep())\n"
2581 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2583 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2584 expr
*e
= static_cast<expr
*>(dop
->op
);
2585 if (e
->ops
.length () != n
)
2588 if (*e
->operation
== CONVERT_EXPR
2589 || *e
->operation
== NOP_EXPR
)
2590 fprintf (f
, "CASE_CONVERT:\n");
2592 fprintf (f
, "case %s%s:\n",
2593 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2596 dop
->gen_kids (f
, true);
2597 fprintf (f
, "break;\n");
2600 fprintf (f
, "default:;\n"
2603 fprintf (f
, "return false;\n");
2608 /* Main entry to generate code for matching GENERIC IL off the decision
2612 decision_tree::gen_generic (FILE *f
)
2614 for (unsigned n
= 1; n
<= 3; ++n
)
2616 fprintf (f
, "\ntree\n"
2617 "generic_simplify (location_t loc, enum tree_code code, "
2618 "tree type ATTRIBUTE_UNUSED");
2619 for (unsigned i
= 0; i
< n
; ++i
)
2620 fprintf (f
, ", tree op%d", i
);
2624 fprintf (f
, "switch (code)\n"
2626 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2628 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2629 expr
*e
= static_cast<expr
*>(dop
->op
);
2630 if (e
->ops
.length () != n
2631 /* Builtin simplifications are somewhat premature on
2632 GENERIC. The following drops patterns with outermost
2633 calls. It's easy to emit overloads for function code
2634 though if necessary. */
2635 || e
->operation
->kind
!= id_base::CODE
)
2638 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2639 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2640 fprintf (f
, "CASE_CONVERT:\n");
2642 fprintf (f
, "case %s:\n", e
->operation
->id
);
2644 dop
->gen_kids (f
, false);
2645 fprintf (f
, "break;\n"
2648 fprintf (f
, "default:;\n"
2651 fprintf (f
, "return NULL_TREE;\n");
2656 /* Output code to implement the predicate P from the decision tree DT. */
2659 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2661 fprintf (f
, "\nbool\n"
2662 "%s%s (tree t%s%s)\n"
2663 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2664 p
->nargs
> 0 ? ", tree *res_ops" : "",
2665 gimple
? ", tree (*valueize)(tree)" : "");
2666 /* Conveniently make 'type' available. */
2667 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2670 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2671 dt
.root
->gen_kids (f
, gimple
);
2673 fprintf (f
, "return false;\n"
2677 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2680 write_header (FILE *f
, const char *head
)
2682 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2683 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2685 /* Include the header instead of writing it awkwardly quoted here. */
2686 fprintf (f
, "\n#include \"%s\"\n", head
);
2696 parser (cpp_reader
*);
2699 const cpp_token
*next ();
2700 const cpp_token
*peek ();
2701 const cpp_token
*peek_ident (const char * = NULL
);
2702 const cpp_token
*expect (enum cpp_ttype
);
2703 void eat_token (enum cpp_ttype
);
2704 const char *get_string ();
2705 const char *get_ident ();
2706 void eat_ident (const char *);
2707 const char *get_number ();
2709 id_base
*parse_operation ();
2710 operand
*parse_capture (operand
*);
2711 operand
*parse_expr ();
2712 c_expr
*parse_c_expr (cpp_ttype
);
2713 operand
*parse_op ();
2715 void record_operlist (source_location
, user_id
*);
2717 void parse_pattern ();
2718 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2719 operand
*, source_location
);
2720 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2722 void parse_for (source_location
);
2723 void parse_if (source_location
);
2724 void parse_predicates (source_location
);
2725 void parse_operator_list (source_location
);
2728 vec
<if_or_with
> active_ifs
;
2729 vec
<vec
<user_id
*> > active_fors
;
2730 hash_set
<user_id
*> *oper_lists_set
;
2731 vec
<user_id
*> oper_lists
;
2733 cid_map_t
*capture_ids
;
2736 vec
<simplify
*> simplifiers
;
2737 vec
<predicate_id
*> user_predicates
;
2738 bool parsing_match_operand
;
2741 /* Lexing helpers. */
2743 /* Read the next non-whitespace token from R. */
2748 const cpp_token
*token
;
2751 token
= cpp_get_token (r
);
2753 while (token
->type
== CPP_PADDING
2754 && token
->type
!= CPP_EOF
);
2758 /* Peek at the next non-whitespace token from R. */
2763 const cpp_token
*token
;
2767 token
= cpp_peek_token (r
, i
++);
2769 while (token
->type
== CPP_PADDING
2770 && token
->type
!= CPP_EOF
);
2771 /* If we peek at EOF this is a fatal error as it leaves the
2772 cpp_reader in unusable state. Assume we really wanted a
2773 token and thus this EOF is unexpected. */
2774 if (token
->type
== CPP_EOF
)
2775 fatal_at (token
, "unexpected end of file");
2779 /* Peek at the next identifier token (or return NULL if the next
2780 token is not an identifier or equal to ID if supplied). */
2783 parser::peek_ident (const char *id
)
2785 const cpp_token
*token
= peek ();
2786 if (token
->type
!= CPP_NAME
)
2792 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2793 if (strcmp (id
, t
) == 0)
2799 /* Read the next token from R and assert it is of type TK. */
2802 parser::expect (enum cpp_ttype tk
)
2804 const cpp_token
*token
= next ();
2805 if (token
->type
!= tk
)
2806 fatal_at (token
, "expected %s, got %s",
2807 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2812 /* Consume the next token from R and assert it is of type TK. */
2815 parser::eat_token (enum cpp_ttype tk
)
2820 /* Read the next token from R and assert it is of type CPP_STRING and
2821 return its value. */
2824 parser::get_string ()
2826 const cpp_token
*token
= expect (CPP_STRING
);
2827 return (const char *)token
->val
.str
.text
;
2830 /* Read the next token from R and assert it is of type CPP_NAME and
2831 return its value. */
2834 parser::get_ident ()
2836 const cpp_token
*token
= expect (CPP_NAME
);
2837 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2840 /* Eat an identifier token with value S from R. */
2843 parser::eat_ident (const char *s
)
2845 const cpp_token
*token
= peek ();
2846 const char *t
= get_ident ();
2847 if (strcmp (s
, t
) != 0)
2848 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2851 /* Read the next token from R and assert it is of type CPP_NUMBER and
2852 return its value. */
2855 parser::get_number ()
2857 const cpp_token
*token
= expect (CPP_NUMBER
);
2858 return (const char *)token
->val
.str
.text
;
2862 /* Record an operator-list use for transparent for handling. */
2865 parser::record_operlist (source_location loc
, user_id
*p
)
2867 if (!oper_lists_set
->add (p
))
2869 if (!oper_lists
.is_empty ()
2870 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2871 fatal_at (loc
, "User-defined operator list does not have the "
2872 "same number of entries as others used in the pattern");
2873 oper_lists
.safe_push (p
);
2877 /* Parse the operator ID, special-casing convert?, convert1? and
2881 parser::parse_operation ()
2883 const cpp_token
*id_tok
= peek ();
2884 const char *id
= get_ident ();
2885 const cpp_token
*token
= peek ();
2886 if (strcmp (id
, "convert0") == 0)
2887 fatal_at (id_tok
, "use 'convert?' here");
2888 else if (strcmp (id
, "view_convert0") == 0)
2889 fatal_at (id_tok
, "use 'view_convert?' here");
2890 if (token
->type
== CPP_QUERY
2891 && !(token
->flags
& PREV_WHITE
))
2893 if (strcmp (id
, "convert") == 0)
2895 else if (strcmp (id
, "convert1") == 0)
2897 else if (strcmp (id
, "convert2") == 0)
2899 else if (strcmp (id
, "view_convert") == 0)
2900 id
= "view_convert0";
2901 else if (strcmp (id
, "view_convert1") == 0)
2903 else if (strcmp (id
, "view_convert2") == 0)
2906 fatal_at (id_tok
, "non-convert operator conditionalized");
2908 if (!parsing_match_operand
)
2909 fatal_at (id_tok
, "conditional convert can only be used in "
2910 "match expression");
2911 eat_token (CPP_QUERY
);
2913 else if (strcmp (id
, "convert1") == 0
2914 || strcmp (id
, "convert2") == 0
2915 || strcmp (id
, "view_convert1") == 0
2916 || strcmp (id
, "view_convert2") == 0)
2917 fatal_at (id_tok
, "expected '?' after conditional operator");
2918 id_base
*op
= get_operator (id
);
2920 fatal_at (id_tok
, "unknown operator %s", id
);
2922 user_id
*p
= dyn_cast
<user_id
*> (op
);
2923 if (p
&& p
->is_oper_list
)
2925 if (active_fors
.length() == 0)
2926 record_operlist (id_tok
->src_loc
, p
);
2928 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
2934 capture = '@'<number> */
2937 parser::parse_capture (operand
*op
)
2939 eat_token (CPP_ATSIGN
);
2940 const cpp_token
*token
= peek ();
2941 const char *id
= NULL
;
2942 if (token
->type
== CPP_NUMBER
)
2944 else if (token
->type
== CPP_NAME
)
2947 fatal_at (token
, "expected number or identifier");
2948 unsigned next_id
= capture_ids
->elements ();
2950 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2953 return new capture (num
, op
);
2956 /* Parse an expression
2957 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2960 parser::parse_expr ()
2962 expr
*e
= new expr (parse_operation ());
2963 const cpp_token
*token
= peek ();
2965 bool is_commutative
= false;
2966 const char *expr_type
= NULL
;
2968 if (token
->type
== CPP_COLON
2969 && !(token
->flags
& PREV_WHITE
))
2971 eat_token (CPP_COLON
);
2973 if (token
->type
== CPP_NAME
2974 && !(token
->flags
& PREV_WHITE
))
2976 const char *s
= get_ident ();
2977 if (s
[0] == 'c' && !s
[1])
2979 if (!parsing_match_operand
)
2981 "flag 'c' can only be used in match expression");
2982 is_commutative
= true;
2984 else if (s
[1] != '\0')
2986 if (parsing_match_operand
)
2987 fatal_at (token
, "type can only be used in result expression");
2991 fatal_at (token
, "flag %s not recognized", s
);
2996 fatal_at (token
, "expected flag or type specifying identifier");
2999 if (token
->type
== CPP_ATSIGN
3000 && !(token
->flags
& PREV_WHITE
))
3001 op
= parse_capture (e
);
3006 const cpp_token
*token
= peek ();
3007 if (token
->type
== CPP_CLOSE_PAREN
)
3009 if (e
->operation
->nargs
!= -1
3010 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3011 fatal_at (token
, "'%s' expects %u operands, not %u",
3012 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3015 if (e
->ops
.length () == 2)
3016 e
->is_commutative
= true;
3018 fatal_at (token
, "only binary operators or function with "
3019 "two arguments can be marked commutative");
3021 e
->expr_type
= expr_type
;
3024 e
->append_op (parse_op ());
3029 /* Lex native C code delimited by START recording the preprocessing tokens
3030 for later processing.
3031 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3034 parser::parse_c_expr (cpp_ttype start
)
3036 const cpp_token
*token
;
3039 vec
<cpp_token
> code
= vNULL
;
3040 unsigned nr_stmts
= 0;
3042 if (start
== CPP_OPEN_PAREN
)
3043 end
= CPP_CLOSE_PAREN
;
3044 else if (start
== CPP_OPEN_BRACE
)
3045 end
= CPP_CLOSE_BRACE
;
3053 /* Count brace pairs to find the end of the expr to match. */
3054 if (token
->type
== start
)
3056 else if (token
->type
== end
3060 /* This is a lame way of counting the number of statements. */
3061 if (token
->type
== CPP_SEMICOLON
)
3064 /* If this is possibly a user-defined identifier mark it used. */
3065 if (token
->type
== CPP_NAME
)
3067 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3068 (token
->val
.node
.node
)->ident
.str
);
3070 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3071 record_operlist (token
->src_loc
, p
);
3074 /* Record the token. */
3075 code
.safe_push (*token
);
3078 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3081 /* Parse an operand which is either an expression, a predicate or
3082 a standalone capture.
3083 op = predicate | expr | c_expr | capture */
3088 const cpp_token
*token
= peek ();
3089 struct operand
*op
= NULL
;
3090 if (token
->type
== CPP_OPEN_PAREN
)
3092 eat_token (CPP_OPEN_PAREN
);
3094 eat_token (CPP_CLOSE_PAREN
);
3096 else if (token
->type
== CPP_OPEN_BRACE
)
3098 op
= parse_c_expr (CPP_OPEN_BRACE
);
3102 /* Remaining ops are either empty or predicates */
3103 if (token
->type
== CPP_NAME
)
3105 const char *id
= get_ident ();
3106 id_base
*opr
= get_operator (id
);
3108 fatal_at (token
, "expected predicate name");
3109 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3111 if (code
->nargs
!= 0)
3112 fatal_at (token
, "using an operator with operands as predicate");
3113 /* Parse the zero-operand operator "predicates" as
3115 op
= new expr (opr
);
3117 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3119 if (code
->nargs
!= 0)
3120 fatal_at (token
, "using an operator with operands as predicate");
3121 /* Parse the zero-operand operator "predicates" as
3123 op
= new expr (opr
);
3125 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3126 op
= new predicate (p
);
3128 fatal_at (token
, "using an unsupported operator as predicate");
3129 if (!parsing_match_operand
)
3130 fatal_at (token
, "predicates are only allowed in match expression");
3132 if (token
->flags
& PREV_WHITE
)
3135 else if (token
->type
!= CPP_COLON
3136 && token
->type
!= CPP_ATSIGN
)
3137 fatal_at (token
, "expected expression or predicate");
3138 /* optionally followed by a capture and a predicate. */
3139 if (token
->type
== CPP_COLON
)
3140 fatal_at (token
, "not implemented: predicate on leaf operand");
3141 if (token
->type
== CPP_ATSIGN
)
3142 op
= parse_capture (op
);
3148 /* Create a new simplify from the current parsing state and MATCH,
3149 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3152 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3153 operand
*match
, source_location match_loc
,
3154 operand
*result
, source_location result_loc
)
3156 /* Build and push a temporary for for operator list uses in expressions. */
3157 if (!oper_lists
.is_empty ())
3158 active_fors
.safe_push (oper_lists
);
3160 simplifiers
.safe_push
3161 (new simplify (match
, match_loc
, result
, result_loc
,
3162 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3164 if (!oper_lists
.is_empty ())
3169 simplify = 'simplify' <expr> <result-op>
3171 match = 'match' <ident> <expr> [<result-op>]
3173 <result-op> = <op> | <if> | <with>
3174 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3175 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3176 and fill SIMPLIFIERS with the results. */
3179 parser::parse_simplify (source_location match_location
,
3180 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3183 /* Reset the capture map. */
3185 capture_ids
= new cid_map_t
;
3186 /* Reset oper_lists and set. */
3187 hash_set
<user_id
*> olist
;
3188 oper_lists_set
= &olist
;
3191 const cpp_token
*loc
= peek ();
3192 parsing_match_operand
= true;
3193 struct operand
*match
= parse_op ();
3194 parsing_match_operand
= false;
3195 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3196 fatal_at (loc
, "outermost expression cannot be captured");
3197 if (match
->type
== operand::OP_EXPR
3198 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3199 fatal_at (loc
, "outermost expression cannot be a predicate");
3201 const cpp_token
*token
= peek ();
3203 /* If this if is immediately closed then it is part of a predicate
3204 definition. Push it. */
3205 if (token
->type
== CPP_CLOSE_PAREN
)
3208 fatal_at (token
, "expected transform expression");
3209 push_simplify (simplifiers
, match
, match_location
,
3210 result
, token
->src_loc
);
3214 unsigned active_ifs_len
= active_ifs
.length ();
3217 if (token
->type
== CPP_OPEN_PAREN
)
3219 source_location paren_loc
= token
->src_loc
;
3220 eat_token (CPP_OPEN_PAREN
);
3221 if (peek_ident ("if"))
3224 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3225 token
->src_loc
, false));
3226 /* If this if is immediately closed then it contains a
3227 manual matcher or is part of a predicate definition.
3229 if (peek ()->type
== CPP_CLOSE_PAREN
)
3232 fatal_at (token
, "manual transform not implemented");
3233 push_simplify (simplifiers
, match
, match_location
,
3237 else if (peek_ident ("with"))
3240 /* Parse (with c-expr expr) as (if-with (true) expr). */
3241 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3243 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3247 operand
*op
= result
;
3250 push_simplify (simplifiers
, match
, match_location
,
3251 op
, token
->src_loc
);
3252 eat_token (CPP_CLOSE_PAREN
);
3253 /* A "default" result closes the enclosing scope. */
3254 if (active_ifs
.length () > active_ifs_len
)
3256 eat_token (CPP_CLOSE_PAREN
);
3263 else if (token
->type
== CPP_CLOSE_PAREN
)
3265 /* Close a scope if requested. */
3266 if (active_ifs
.length () > active_ifs_len
)
3268 eat_token (CPP_CLOSE_PAREN
);
3278 fatal_at (token
, "expected match operand expression");
3279 push_simplify (simplifiers
, match
, match_location
,
3280 matcher
? result
: parse_op (), token
->src_loc
);
3281 /* A "default" result closes the enclosing scope. */
3282 if (active_ifs
.length () > active_ifs_len
)
3284 eat_token (CPP_CLOSE_PAREN
);
3294 /* Parsing of the outer control structures. */
3296 /* Parse a for expression
3297 for = '(' 'for' <subst>... <pattern> ')'
3298 subst = <ident> '(' <ident>... ')' */
3301 parser::parse_for (source_location
)
3303 auto_vec
<const cpp_token
*> user_id_tokens
;
3304 vec
<user_id
*> user_ids
= vNULL
;
3305 const cpp_token
*token
;
3306 unsigned min_n_opers
= 0, max_n_opers
= 0;
3311 if (token
->type
!= CPP_NAME
)
3314 /* Insert the user defined operators into the operator hash. */
3315 const char *id
= get_ident ();
3316 if (get_operator (id
) != NULL
)
3317 fatal_at (token
, "operator already defined");
3318 user_id
*op
= new user_id (id
);
3319 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3321 user_ids
.safe_push (op
);
3322 user_id_tokens
.safe_push (token
);
3324 eat_token (CPP_OPEN_PAREN
);
3327 while ((token
= peek_ident ()) != 0)
3329 const char *oper
= get_ident ();
3330 id_base
*idb
= get_operator (oper
);
3332 fatal_at (token
, "no such operator '%s'", oper
);
3333 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3334 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3335 || *idb
== VIEW_CONVERT2
)
3336 fatal_at (token
, "conditional operators cannot be used inside for");
3340 else if (idb
->nargs
== -1)
3342 else if (idb
->nargs
!= arity
)
3343 fatal_at (token
, "operator '%s' with arity %d does not match "
3344 "others with arity %d", oper
, idb
->nargs
, arity
);
3346 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3349 if (p
->is_oper_list
)
3350 op
->substitutes
.safe_splice (p
->substitutes
);
3352 fatal_at (token
, "iterator cannot be used as operator-list");
3355 op
->substitutes
.safe_push (idb
);
3358 token
= expect (CPP_CLOSE_PAREN
);
3360 unsigned nsubstitutes
= op
->substitutes
.length ();
3361 if (nsubstitutes
== 0)
3362 fatal_at (token
, "A user-defined operator must have at least "
3363 "one substitution");
3364 if (max_n_opers
== 0)
3366 min_n_opers
= nsubstitutes
;
3367 max_n_opers
= nsubstitutes
;
3371 if (nsubstitutes
% min_n_opers
!= 0
3372 && min_n_opers
% nsubstitutes
!= 0)
3373 fatal_at (token
, "All user-defined identifiers must have a "
3374 "multiple number of operator substitutions of the "
3375 "smallest number of substitutions");
3376 if (nsubstitutes
< min_n_opers
)
3377 min_n_opers
= nsubstitutes
;
3378 else if (nsubstitutes
> max_n_opers
)
3379 max_n_opers
= nsubstitutes
;
3383 unsigned n_ids
= user_ids
.length ();
3385 fatal_at (token
, "for requires at least one user-defined identifier");
3388 if (token
->type
== CPP_CLOSE_PAREN
)
3389 fatal_at (token
, "no pattern defined in for");
3391 active_fors
.safe_push (user_ids
);
3395 if (token
->type
== CPP_CLOSE_PAREN
)
3401 /* Remove user-defined operators from the hash again. */
3402 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3404 if (!user_ids
[i
]->used
)
3405 warning_at (user_id_tokens
[i
],
3406 "operator %s defined but not used", user_ids
[i
]->id
);
3407 operators
->remove_elt (user_ids
[i
]);
3411 /* Parse an identifier associated with a list of operators.
3412 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3415 parser::parse_operator_list (source_location
)
3417 const cpp_token
*token
= peek ();
3418 const char *id
= get_ident ();
3420 if (get_operator (id
) != 0)
3421 fatal_at (token
, "operator %s already defined", id
);
3423 user_id
*op
= new user_id (id
, true);
3426 while ((token
= peek_ident ()) != 0)
3429 const char *oper
= get_ident ();
3430 id_base
*idb
= get_operator (oper
);
3433 fatal_at (token
, "no such operator '%s'", oper
);
3437 else if (idb
->nargs
== -1)
3439 else if (arity
!= idb
->nargs
)
3440 fatal_at (token
, "operator '%s' with arity %d does not match "
3441 "others with arity %d", oper
, idb
->nargs
, arity
);
3443 /* We allow composition of multiple operator lists. */
3444 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3445 op
->substitutes
.safe_splice (p
->substitutes
);
3447 op
->substitutes
.safe_push (idb
);
3450 // Check that there is no junk after id-list
3452 if (token
->type
!= CPP_CLOSE_PAREN
)
3453 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3455 if (op
->substitutes
.length () == 0)
3456 fatal_at (token
, "operator-list cannot be empty");
3459 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3463 /* Parse an outer if expression.
3464 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3467 parser::parse_if (source_location loc
)
3469 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3471 const cpp_token
*token
= peek ();
3472 if (token
->type
== CPP_CLOSE_PAREN
)
3473 fatal_at (token
, "no pattern defined in if");
3475 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3478 const cpp_token
*token
= peek ();
3479 if (token
->type
== CPP_CLOSE_PAREN
)
3487 /* Parse a list of predefined predicate identifiers.
3488 preds = '(' 'define_predicates' <ident>... ')' */
3491 parser::parse_predicates (source_location
)
3495 const cpp_token
*token
= peek ();
3496 if (token
->type
!= CPP_NAME
)
3499 add_predicate (get_ident ());
3504 /* Parse outer control structures.
3505 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3508 parser::parse_pattern ()
3510 /* All clauses start with '('. */
3511 eat_token (CPP_OPEN_PAREN
);
3512 const cpp_token
*token
= peek ();
3513 const char *id
= get_ident ();
3514 if (strcmp (id
, "simplify") == 0)
3516 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3519 else if (strcmp (id
, "match") == 0)
3521 bool with_args
= false;
3522 if (peek ()->type
== CPP_OPEN_PAREN
)
3524 eat_token (CPP_OPEN_PAREN
);
3527 const char *name
= get_ident ();
3528 id_base
*id
= get_operator (name
);
3532 p
= add_predicate (name
);
3533 user_predicates
.safe_push (p
);
3535 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3538 fatal_at (token
, "cannot add a match to a non-predicate ID");
3539 /* Parse (match <id> <arg>... (match-expr)) here. */
3543 capture_ids
= new cid_map_t
;
3545 while (peek ()->type
== CPP_ATSIGN
)
3546 e
->append_op (parse_capture (NULL
));
3547 eat_token (CPP_CLOSE_PAREN
);
3550 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3551 || (!e
&& p
->nargs
!= 0)))
3552 fatal_at (token
, "non-matching number of match operands");
3553 p
->nargs
= e
? e
->ops
.length () : 0;
3554 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3557 else if (strcmp (id
, "for") == 0)
3558 parse_for (token
->src_loc
);
3559 else if (strcmp (id
, "if") == 0)
3560 parse_if (token
->src_loc
);
3561 else if (strcmp (id
, "define_predicates") == 0)
3563 if (active_ifs
.length () > 0
3564 || active_fors
.length () > 0)
3565 fatal_at (token
, "define_predicates inside if or for is not supported");
3566 parse_predicates (token
->src_loc
);
3568 else if (strcmp (id
, "define_operator_list") == 0)
3570 if (active_ifs
.length () > 0
3571 || active_fors
.length () > 0)
3572 fatal_at (token
, "operator-list inside if or for is not supported");
3573 parse_operator_list (token
->src_loc
);
3576 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3577 active_ifs
.length () == 0 && active_fors
.length () == 0
3578 ? "'define_predicates', " : "");
3580 eat_token (CPP_CLOSE_PAREN
);
3583 /* Main entry of the parser. Repeatedly parse outer control structures. */
3585 parser::parser (cpp_reader
*r_
)
3589 active_fors
= vNULL
;
3590 simplifiers
= vNULL
;
3591 oper_lists_set
= NULL
;
3594 user_predicates
= vNULL
;
3595 parsing_match_operand
= false;
3597 const cpp_token
*token
= next ();
3598 while (token
->type
!= CPP_EOF
)
3600 _cpp_backup_tokens (r
, 1);
3607 /* Helper for the linemap code. */
3610 round_alloc_size (size_t s
)
3616 /* The genmatch generator progam. It reads from a pattern description
3617 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3620 main (int argc
, char **argv
)
3624 progname
= "genmatch";
3630 bool verbose
= false;
3631 char *input
= argv
[argc
-1];
3632 for (int i
= 1; i
< argc
- 1; ++i
)
3634 if (strcmp (argv
[i
], "--gimple") == 0)
3636 else if (strcmp (argv
[i
], "--generic") == 0)
3638 else if (strcmp (argv
[i
], "-v") == 0)
3642 fprintf (stderr
, "Usage: genmatch "
3643 "[--gimple] [--generic] [-v] input\n");
3648 line_table
= XCNEW (struct line_maps
);
3649 linemap_init (line_table
, 0);
3650 line_table
->reallocator
= xrealloc
;
3651 line_table
->round_alloc_size
= round_alloc_size
;
3653 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3654 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3655 cb
->error
= error_cb
;
3657 if (!cpp_read_main_file (r
, input
))
3659 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3660 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3662 /* Pre-seed operators. */
3663 operators
= new hash_table
<id_base
> (1024);
3664 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3665 add_operator (SYM, # SYM, # TYPE, NARGS);
3666 #define END_OF_BASE_TREE_CODES
3668 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3669 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3670 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3671 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
3672 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
3673 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
3674 #undef END_OF_BASE_TREE_CODES
3677 /* Pre-seed builtin functions.
3678 ??? Cannot use N (name) as that is targetm.emultls.get_address
3679 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3680 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3681 add_builtin (ENUM, # ENUM);
3682 #include "builtins.def"
3689 write_header (stdout
, "gimple-match-head.c");
3691 write_header (stdout
, "generic-match-head.c");
3693 /* Go over all predicates defined with patterns and perform
3694 lowering and code generation. */
3695 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3697 predicate_id
*pred
= p
.user_predicates
[i
];
3698 lower (pred
->matchers
, gimple
);
3701 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3702 print_matches (pred
->matchers
[i
]);
3705 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3706 dt
.insert (pred
->matchers
[i
], i
);
3711 write_predicate (stdout
, pred
, dt
, gimple
);
3714 /* Lower the main simplifiers and generate code for them. */
3715 lower (p
.simplifiers
, gimple
);
3718 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3719 print_matches (p
.simplifiers
[i
]);
3722 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3723 dt
.insert (p
.simplifiers
[i
], i
);
3729 dt
.gen_gimple (stdout
);
3731 dt
.gen_generic (stdout
);
3734 cpp_finish (r
, NULL
);