1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
32 #include "hash-table.h"
38 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
39 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
40 size_t, size_t MEM_STAT_DECL
)
44 void ggc_free (void *)
51 static struct line_maps
*line_table
;
54 #if GCC_VERSION >= 4001
55 __attribute__((format (printf
, 6, 0)))
57 error_cb (cpp_reader
*, int, int, source_location location
,
58 unsigned int, const char *msg
, va_list *ap
)
61 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
62 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
63 fprintf (stderr
, "%s:%d:%d error: ", loc
.file
, loc
.line
, loc
.column
);
64 vfprintf (stderr
, msg
, *ap
);
65 fprintf (stderr
, "\n");
66 FILE *f
= fopen (loc
.file
, "r");
72 if (!fgets (buf
, 128, f
))
74 if (buf
[strlen (buf
) - 1] != '\n')
81 fprintf (stderr
, "%s", buf
);
82 for (int i
= 0; i
< loc
.column
- 1; ++i
)
93 #if GCC_VERSION >= 4001
94 __attribute__((format (printf
, 2, 3)))
96 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
100 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
105 output_line_directive (FILE *f
, source_location location
,
106 bool dumpfile
= false)
109 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
110 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
113 /* When writing to a dumpfile only dump the filename. */
114 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
119 fprintf (f
, "%s:%d", file
, loc
.line
);
122 /* Other gen programs really output line directives here, at least for
123 development it's right now more convenient to have line information
124 from the generated file. Still keep the directives as comment for now
125 to easily back-point to the meta-description. */
126 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
130 /* Pull in tree codes and builtin function codes from their
133 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
143 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
144 enum built_in_function
{
145 #include "builtins.def"
151 /* Base class for all identifiers the parser knows. */
153 struct id_base
: typed_noop_remove
<id_base
>
155 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
157 id_base (id_kind
, const char *, int = -1);
163 /* hash_table support. */
164 typedef id_base value_type
;
165 typedef id_base compare_type
;
166 static inline hashval_t
hash (const value_type
*);
167 static inline int equal (const value_type
*, const compare_type
*);
171 id_base::hash (const value_type
*op
)
177 id_base::equal (const value_type
*op1
,
178 const compare_type
*op2
)
180 return (op1
->hashval
== op2
->hashval
181 && strcmp (op1
->id
, op2
->id
) == 0);
184 /* Hashtable of known pattern operators. This is pre-seeded from
185 all known tree codes and all known builtin function ids. */
186 static hash_table
<id_base
> *operators
;
188 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
193 hashval
= htab_hash_string (id
);
196 /* Identifier that maps to a tree code. */
198 struct operator_id
: public id_base
200 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
202 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
207 /* Identifier that maps to a builtin function code. */
209 struct fn_id
: public id_base
211 fn_id (enum built_in_function fn_
, const char *id_
)
212 : id_base (id_base::FN
, id_
), fn (fn_
) {}
213 enum built_in_function fn
;
218 /* Identifier that maps to a user-defined predicate. */
220 struct predicate_id
: public id_base
222 predicate_id (const char *id_
)
223 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
224 vec
<simplify
*> matchers
;
227 /* Identifier that maps to a operator defined by a 'for' directive. */
229 struct user_id
: public id_base
231 user_id (const char *id_
)
232 : id_base (id_base::USER
, id_
), substitutes (vNULL
) {}
233 vec
<id_base
*> substitutes
;
239 is_a_helper
<fn_id
*>::test (id_base
*id
)
241 return id
->kind
== id_base::FN
;
247 is_a_helper
<operator_id
*>::test (id_base
*id
)
249 return id
->kind
== id_base::CODE
;
255 is_a_helper
<predicate_id
*>::test (id_base
*id
)
257 return id
->kind
== id_base::PREDICATE
;
263 is_a_helper
<user_id
*>::test (id_base
*id
)
265 return id
->kind
== id_base::USER
;
268 /* Add a predicate identifier to the hash. */
270 static predicate_id
*
271 add_predicate (const char *id
)
273 predicate_id
*p
= new predicate_id (id
);
274 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
276 fatal ("duplicate id definition");
281 /* Add a tree code identifier to the hash. */
284 add_operator (enum tree_code code
, const char *id
,
285 const char *tcc
, unsigned nargs
)
287 if (strcmp (tcc
, "tcc_unary") != 0
288 && strcmp (tcc
, "tcc_binary") != 0
289 && strcmp (tcc
, "tcc_comparison") != 0
290 && strcmp (tcc
, "tcc_expression") != 0
291 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
292 && strcmp (tcc
, "tcc_reference") != 0
293 /* To have INTEGER_CST and friends as "predicate operators". */
294 && strcmp (tcc
, "tcc_constant") != 0)
296 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
297 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
299 fatal ("duplicate id definition");
303 /* Add a builtin identifier to the hash. */
306 add_builtin (enum built_in_function code
, const char *id
)
308 fn_id
*fn
= new fn_id (code
, id
);
309 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
311 fatal ("duplicate id definition");
315 /* Helper for easy comparing ID with tree code CODE. */
318 operator==(id_base
&id
, enum tree_code code
)
320 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
321 return oid
->code
== code
;
325 /* Lookup the identifier ID. */
328 get_operator (const char *id
)
330 id_base
tem (id_base::CODE
, id
);
332 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
336 /* Try all-uppercase. */
337 char *id2
= xstrdup (id
);
338 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
339 id2
[i
] = TOUPPER (id2
[i
]);
340 new (&tem
) id_base (id_base::CODE
, id2
);
341 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
348 /* Try _EXPR appended. */
349 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
350 strcat (id2
, "_EXPR");
351 new (&tem
) id_base (id_base::CODE
, id2
);
352 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
363 /* Helper for the capture-id map. */
365 struct capture_id_map_hasher
: default_hashmap_traits
367 static inline hashval_t
hash (const char *);
368 static inline bool equal_keys (const char *, const char *);
372 capture_id_map_hasher::hash (const char *id
)
374 return htab_hash_string (id
);
378 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
380 return strcmp (id1
, id2
) == 0;
383 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
386 /* The AST produced by parsing of the pattern definitions. */
390 /* The base class for operands. */
393 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
394 operand (enum op_type type_
) : type (type_
) {}
396 virtual void gen_transform (FILE *, const char *, bool, int,
397 const char *, dt_operand
** = 0)
398 { gcc_unreachable (); }
401 /* A predicate operand. Predicates are leafs in the AST. */
403 struct predicate
: public operand
405 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
409 /* An operand that constitutes an expression. Expressions include
410 function calls and user-defined predicate invocations. */
412 struct expr
: public operand
414 expr (id_base
*operation_
, bool is_commutative_
= false)
415 : operand (OP_EXPR
), operation (operation_
),
416 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
) {}
417 void append_op (operand
*op
) { ops
.safe_push (op
); }
418 /* The operator and its operands. */
421 /* An explicitely specified type - used exclusively for conversions. */
422 const char *expr_type
;
423 /* Whether the operation is to be applied commutatively. This is
424 later lowered to two separate patterns. */
426 virtual void gen_transform (FILE *f
, const char *, bool, int,
427 const char *, dt_operand
** = 0);
430 /* An operator that is represented by native C code. This is always
431 a leaf operand in the AST. This class is also used to represent
432 the code to be generated for 'if' and 'with' expressions. */
434 struct c_expr
: public operand
436 /* A mapping of an identifier and its replacement. Used to apply
441 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
444 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
445 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
446 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
447 nr_stmts (nr_stmts_
), ids (ids_
) {}
448 /* cpplib tokens and state to transform this back to source. */
451 cid_map_t
*capture_ids
;
452 /* The number of statements parsed (well, the number of ';'s). */
454 /* The identifier replacement vector. */
456 virtual void gen_transform (FILE *f
, const char *, bool, int,
457 const char *, dt_operand
**);
460 /* A wrapper around another operand that captures its value. */
462 struct capture
: public operand
464 capture (unsigned where_
, operand
*what_
)
465 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
466 /* Identifier index for the value. */
468 /* The captured value. */
470 virtual void gen_transform (FILE *f
, const char *, bool, int,
471 const char *, dt_operand
** = 0);
477 is_a_helper
<capture
*>::test (operand
*op
)
479 return op
->type
== operand::OP_CAPTURE
;
485 is_a_helper
<predicate
*>::test (operand
*op
)
487 return op
->type
== operand::OP_PREDICATE
;
493 is_a_helper
<c_expr
*>::test (operand
*op
)
495 return op
->type
== operand::OP_C_EXPR
;
501 is_a_helper
<expr
*>::test (operand
*op
)
503 return op
->type
== operand::OP_EXPR
;
506 /* Helper to distinguish 'if' from 'with' expressions. */
510 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
511 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
512 source_location location
;
517 /* The main class of a pattern and its transform. This is used to
518 represent both (simplify ...) and (match ...) kinds. The AST
519 duplicates all outer 'if' and 'for' expressions here so each
520 simplify can exist in isolation. */
524 simplify (operand
*match_
, source_location match_location_
,
525 struct operand
*result_
, source_location result_location_
,
526 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
527 cid_map_t
*capture_ids_
)
528 : match (match_
), match_location (match_location_
),
529 result (result_
), result_location (result_location_
),
530 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
531 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
533 /* The expression that is matched against the GENERIC or GIMPLE IL. */
535 source_location match_location
;
536 /* For a (simplify ...) the expression produced when the pattern applies.
537 For a (match ...) either NULL if it is a simple predicate or the
538 single expression specifying the matched operands. */
539 struct operand
*result
;
540 source_location result_location
;
541 /* Collected 'if' expressions that need to evaluate to true to make
542 the pattern apply. */
543 vec
<if_or_with
> ifexpr_vec
;
544 /* Collected 'for' expression operators that have to be replaced
545 in the lowering phase. */
546 vec
<vec
<user_id
*> > for_vec
;
547 /* A map of capture identifiers to indexes. */
548 cid_map_t
*capture_ids
;
552 /* Debugging routines for dumping the AST. */
555 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
557 if (capture
*c
= dyn_cast
<capture
*> (o
))
559 fprintf (f
, "@%u", c
->where
);
560 if (c
->what
&& flattened
== false)
563 print_operand (c
->what
, f
, flattened
);
568 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
569 fprintf (f
, "%s", p
->p
->id
);
571 else if (is_a
<c_expr
*> (o
))
572 fprintf (f
, "c_expr");
574 else if (expr
*e
= dyn_cast
<expr
*> (o
))
576 fprintf (f
, "(%s", e
->operation
->id
);
578 if (flattened
== false)
581 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
583 print_operand (e
->ops
[i
], f
, flattened
);
595 print_matches (struct simplify
*s
, FILE *f
= stderr
)
597 fprintf (f
, "for expression: ");
598 print_operand (s
->match
, f
);
605 /* Lowering of commutative operators. */
608 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
609 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
611 if (n
== ops_vector
.length ())
613 vec
<operand
*> xv
= v
.copy ();
614 result
.safe_push (xv
);
618 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
620 v
[n
] = ops_vector
[n
][i
];
621 cartesian_product (ops_vector
, result
, v
, n
+ 1);
625 /* Lower OP to two operands in case it is marked as commutative. */
627 static vec
<operand
*>
628 commutate (operand
*op
)
630 vec
<operand
*> ret
= vNULL
;
632 if (capture
*c
= dyn_cast
<capture
*> (op
))
639 vec
<operand
*> v
= commutate (c
->what
);
640 for (unsigned i
= 0; i
< v
.length (); ++i
)
642 capture
*nc
= new capture (c
->where
, v
[i
]);
648 expr
*e
= dyn_cast
<expr
*> (op
);
649 if (!e
|| e
->ops
.length () == 0)
655 vec
< vec
<operand
*> > ops_vector
= vNULL
;
656 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
657 ops_vector
.safe_push (commutate (e
->ops
[i
]));
659 auto_vec
< vec
<operand
*> > result
;
660 auto_vec
<operand
*> v (e
->ops
.length ());
661 v
.quick_grow_cleared (e
->ops
.length ());
662 cartesian_product (ops_vector
, result
, v
, 0);
665 for (unsigned i
= 0; i
< result
.length (); ++i
)
667 expr
*ne
= new expr (e
->operation
);
668 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
669 ne
->append_op (result
[i
][j
]);
673 if (!e
->is_commutative
)
676 for (unsigned i
= 0; i
< result
.length (); ++i
)
678 expr
*ne
= new expr (e
->operation
);
679 // result[i].length () is 2 since e->operation is binary
680 for (unsigned j
= result
[i
].length (); j
; --j
)
681 ne
->append_op (result
[i
][j
-1]);
688 /* Lower operations marked as commutative in the AST of S and push
689 the resulting patterns to SIMPLIFIERS. */
692 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
694 vec
<operand
*> matchers
= commutate (s
->match
);
695 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
697 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
698 s
->result
, s
->result_location
, s
->ifexpr_vec
,
699 s
->for_vec
, s
->capture_ids
);
700 simplifiers
.safe_push (ns
);
704 /* Strip conditional conversios using operator OPER from O and its
705 children if STRIP, else replace them with an unconditional convert. */
708 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
710 if (capture
*c
= dyn_cast
<capture
*> (o
))
713 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
718 expr
*e
= dyn_cast
<expr
*> (o
);
722 if (*e
->operation
== oper
)
725 return lower_opt_convert (e
->ops
[0], oper
, strip
);
727 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
728 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
732 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
733 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
734 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
739 /* Determine whether O or its children uses the conditional conversion
743 has_opt_convert (operand
*o
, enum tree_code oper
)
745 if (capture
*c
= dyn_cast
<capture
*> (o
))
748 return has_opt_convert (c
->what
, oper
);
753 expr
*e
= dyn_cast
<expr
*> (o
);
757 if (*e
->operation
== oper
)
760 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
761 if (has_opt_convert (e
->ops
[i
], oper
))
767 /* Lower conditional convert operators in O, expanding it to a vector
770 static vec
<operand
*>
771 lower_opt_convert (operand
*o
)
773 vec
<operand
*> v1
= vNULL
, v2
;
777 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
779 /* Conditional converts are lowered to a pattern with the
780 conversion and one without. The three different conditional
781 convert codes are lowered separately. */
783 for (unsigned i
= 0; i
< 3; ++i
)
786 for (unsigned j
= 0; j
< v1
.length (); ++j
)
787 if (has_opt_convert (v1
[j
], opers
[i
]))
789 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
790 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
796 for (unsigned j
= 0; j
< v2
.length (); ++j
)
797 v1
.safe_push (v2
[j
]);
804 /* Lower conditional convert operators in the AST of S and push
805 the resulting multiple patterns to SIMPLIFIERS. */
808 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
810 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
811 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
813 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
814 s
->result
, s
->result_location
, s
->ifexpr_vec
,
815 s
->for_vec
, s
->capture_ids
);
816 simplifiers
.safe_push (ns
);
820 /* In AST operand O replace operator ID with operator WITH. */
823 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
825 /* Deep-copy captures and expressions, replacing operations as
827 if (capture
*c
= dyn_cast
<capture
*> (o
))
831 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
833 else if (expr
*e
= dyn_cast
<expr
*> (o
))
835 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
837 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
838 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
842 /* For c_expr we simply record a string replacement table which is
843 applied at code-generation time. */
844 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
846 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
847 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
848 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
854 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
857 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
859 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
860 unsigned worklist_start
= 0;
861 auto_vec
<simplify
*> worklist
;
862 worklist
.safe_push (sin
);
864 /* Lower each recorded for separately, operating on the
865 set of simplifiers created by the previous one.
866 Lower inner-to-outer so inner for substitutes can refer
867 to operators replaced by outer fors. */
868 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
870 vec
<user_id
*>& ids
= for_vec
[fi
];
871 unsigned n_ids
= ids
.length ();
872 unsigned max_n_opers
= 0;
873 for (unsigned i
= 0; i
< n_ids
; ++i
)
874 if (ids
[i
]->substitutes
.length () > max_n_opers
)
875 max_n_opers
= ids
[i
]->substitutes
.length ();
877 unsigned worklist_end
= worklist
.length ();
878 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
880 simplify
*s
= worklist
[si
];
881 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
883 operand
*match_op
= s
->match
;
884 operand
*result_op
= s
->result
;
885 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
887 for (unsigned i
= 0; i
< n_ids
; ++i
)
889 user_id
*id
= ids
[i
];
890 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
891 match_op
= replace_id (match_op
, id
, oper
);
893 result_op
= replace_id (result_op
, id
, oper
);
894 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
895 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
898 simplify
*ns
= new simplify (match_op
, s
->match_location
,
899 result_op
, s
->result_location
,
900 ifexpr_vec
, vNULL
, s
->capture_ids
);
901 worklist
.safe_push (ns
);
904 worklist_start
= worklist_end
;
907 /* Copy out the result from the last for lowering. */
908 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
909 simplifiers
.safe_push (worklist
[i
]);
912 /* Lower the AST for everything in SIMPLIFIERS. */
915 lower (vec
<simplify
*>& simplifiers
)
917 auto_vec
<simplify
*> out_simplifiers0
;
918 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
919 lower_opt_convert (simplifiers
[i
], out_simplifiers0
);
921 auto_vec
<simplify
*> out_simplifiers1
;
922 for (unsigned i
= 0; i
< out_simplifiers0
.length (); ++i
)
923 lower_commutative (out_simplifiers0
[i
], out_simplifiers1
);
925 simplifiers
.truncate (0);
926 for (unsigned i
= 0; i
< out_simplifiers1
.length (); ++i
)
927 lower_for (out_simplifiers1
[i
], simplifiers
);
933 /* The decision tree built for generating GIMPLE and GENERIC pattern
934 matching code. It represents the 'match' expression of all
935 simplifies and has those as its leafs. */
937 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
941 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
947 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
949 dt_node
*append_node (dt_node
*);
950 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
951 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
952 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
953 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
955 virtual void gen (FILE *, bool) {}
957 void gen_kids (FILE *, bool);
960 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
962 struct dt_operand
: public dt_node
965 dt_operand
*match_dop
;
969 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
970 dt_operand
*parent_
= 0, unsigned pos_
= 0)
971 : dt_node (type
), op (op_
), match_dop (match_dop_
),
972 parent (parent_
), pos (pos_
) {}
974 void gen (FILE *, bool);
975 unsigned gen_predicate (FILE *, const char *, bool);
976 unsigned gen_match_op (FILE *, const char *);
978 unsigned gen_gimple_expr (FILE *);
979 unsigned gen_generic_expr (FILE *, const char *);
981 char *get_name (char *);
982 void gen_opname (char *, unsigned);
985 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
987 struct dt_simplify
: public dt_node
991 dt_operand
**indexes
;
993 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
994 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
995 indexes (indexes_
) {}
997 void gen (FILE *f
, bool);
1003 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1005 return (n
->type
== dt_node::DT_OPERAND
1006 || n
->type
== dt_node::DT_MATCH
);
1009 /* A container for the actual decision tree. */
1011 struct decision_tree
1015 void insert (struct simplify
*, unsigned);
1016 void gen_gimple (FILE *f
= stderr
);
1017 void gen_generic (FILE *f
= stderr
);
1018 void print (FILE *f
= stderr
);
1020 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1022 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1023 unsigned pos
= 0, dt_node
*parent
= 0);
1024 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1025 static bool cmp_node (dt_node
*, dt_node
*);
1026 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1029 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1032 cmp_operand (operand
*o1
, operand
*o2
)
1034 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1037 if (o1
->type
== operand::OP_PREDICATE
)
1039 predicate
*p1
= as_a
<predicate
*>(o1
);
1040 predicate
*p2
= as_a
<predicate
*>(o2
);
1041 return p1
->p
== p2
->p
;
1043 else if (o1
->type
== operand::OP_EXPR
)
1045 expr
*e1
= static_cast<expr
*>(o1
);
1046 expr
*e2
= static_cast<expr
*>(o2
);
1047 return e1
->operation
== e2
->operation
;
1053 /* Compare two decision tree nodes N1 and N2 and return true if they
1057 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1059 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1062 if (n1
== n2
|| n1
->type
== dt_node::DT_TRUE
)
1065 if (n1
->type
== dt_node::DT_OPERAND
)
1066 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1067 (as_a
<dt_operand
*> (n2
))->op
);
1068 else if (n1
->type
== dt_node::DT_MATCH
)
1069 return ((as_a
<dt_operand
*> (n1
))->match_dop
1070 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1074 /* Search OPS for a decision tree node like P and return it if found. */
1077 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1079 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1080 if (decision_tree::cmp_node (ops
[i
], p
))
1086 /* Append N to the decision tree if it there is not already an existing
1090 dt_node::append_node (dt_node
*n
)
1094 kid
= decision_tree::find_node (kids
, n
);
1099 n
->level
= this->level
+ 1;
1101 unsigned len
= kids
.length ();
1103 if (len
> 1 && kids
[len
- 2]->type
== dt_node::DT_TRUE
)
1105 dt_node
*p
= kids
[len
- 2];
1106 kids
[len
- 2] = kids
[len
- 1];
1113 /* Append OP to the decision tree. */
1116 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1118 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1119 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1120 return append_node (n
);
1123 /* Append a DT_TRUE decision tree node. */
1126 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1128 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1129 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1130 return append_node (n
);
1133 /* Append a DT_MATCH decision tree node. */
1136 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1138 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1139 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1140 return append_node (n
);
1143 /* Append S to the decision tree. */
1146 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1147 dt_operand
**indexes
)
1149 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1150 return append_node (n
);
1153 /* Insert O into the decision tree and return the decision tree node found
1157 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1158 unsigned pos
, dt_node
*parent
)
1160 dt_node
*q
, *elm
= 0;
1162 if (capture
*c
= dyn_cast
<capture
*> (o
))
1164 unsigned capt_index
= c
->where
;
1166 if (indexes
[capt_index
] == 0)
1169 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1172 q
= elm
= p
->append_true_op (parent
, pos
);
1175 // get to the last capture
1176 for (operand
*what
= c
->what
;
1177 what
&& is_a
<capture
*> (what
);
1178 c
= as_a
<capture
*> (what
), what
= c
->what
)
1183 unsigned cc_index
= c
->where
;
1184 dt_operand
*match_op
= indexes
[cc_index
];
1186 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1187 elm
= decision_tree::find_node (p
->kids
, &temp
);
1191 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1192 elm
= decision_tree::find_node (p
->kids
, &temp
);
1197 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1198 elm
= decision_tree::find_node (p
->kids
, &temp
);
1202 gcc_assert (elm
->type
== dt_node::DT_TRUE
1203 || elm
->type
== dt_node::DT_OPERAND
1204 || elm
->type
== dt_node::DT_MATCH
);
1205 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1210 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1212 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1217 p
= p
->append_op (o
, parent
, pos
);
1220 if (expr
*e
= dyn_cast
<expr
*>(o
))
1222 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1223 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1229 /* Insert S into the decision tree. */
1232 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1234 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1235 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1236 p
->append_simplify (s
, pattern_no
, indexes
);
1239 /* Debug functions to dump the decision tree. */
1242 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1244 if (p
->type
== dt_node::DT_NODE
)
1245 fprintf (f
, "root");
1249 for (unsigned i
= 0; i
< indent
; i
++)
1252 if (p
->type
== dt_node::DT_OPERAND
)
1254 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1255 print_operand (dop
->op
, f
, true);
1257 else if (p
->type
== dt_node::DT_TRUE
)
1258 fprintf (f
, "true");
1259 else if (p
->type
== dt_node::DT_MATCH
)
1260 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1261 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1263 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1264 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1265 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1266 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1271 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1273 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1274 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1278 decision_tree::print (FILE *f
)
1280 return decision_tree::print_node (root
, f
);
1285 /* Code generation off the decision tree and the refered AST nodes. */
1288 is_conversion (id_base
*op
)
1290 return (*op
== CONVERT_EXPR
1292 || *op
== FLOAT_EXPR
1293 || *op
== FIX_TRUNC_EXPR
1294 || *op
== VIEW_CONVERT_EXPR
);
1297 /* Get the type to be used for generating operands of OP from the
1301 get_operand_type (id_base
*op
, const char *in_type
,
1302 const char *expr_type
,
1303 const char *other_oprnd_type
)
1305 /* Generally operands whose type does not match the type of the
1306 expression generated need to know their types but match and
1307 thus can fall back to 'other_oprnd_type'. */
1308 if (is_conversion (op
))
1309 return other_oprnd_type
;
1310 else if (*op
== REALPART_EXPR
1311 || *op
== IMAGPART_EXPR
)
1312 return other_oprnd_type
;
1313 else if (is_a
<operator_id
*> (op
)
1314 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1315 return other_oprnd_type
;
1318 /* Otherwise all types should match - choose one in order of
1325 return other_oprnd_type
;
1329 /* Generate transform code for an expression. */
1332 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1333 const char *in_type
, dt_operand
**indexes
)
1335 bool conversion_p
= is_conversion (operation
);
1336 const char *type
= expr_type
;
1339 /* If there was a type specification in the pattern use it. */
1341 else if (conversion_p
)
1342 /* For conversions we need to build the expression using the
1343 outer type passed in. */
1345 else if (*operation
== REALPART_EXPR
1346 || *operation
== IMAGPART_EXPR
)
1348 /* __real and __imag use the component type of its operand. */
1349 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1352 else if (is_a
<operator_id
*> (operation
)
1353 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1355 /* comparisons use boolean_type_node (or what gets in), but
1356 their operands need to figure out the types themselves. */
1357 sprintf (optype
, "boolean_type_node");
1362 /* Other operations are of the same type as their first operand. */
1363 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1367 fatal ("two conversions in a row");
1370 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1372 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1373 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1376 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1378 = get_operand_type (operation
, in_type
, expr_type
,
1379 i
== 0 ? NULL
: op0type
);
1380 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, indexes
);
1384 if (*operation
== CONVERT_EXPR
)
1387 opr
= operation
->id
;
1391 /* ??? Have another helper that is like gimple_build but may
1392 fail if seq == NULL. */
1393 fprintf (f
, " if (!seq)\n"
1395 " res = gimple_simplify (%s, %s", opr
, type
);
1396 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1397 fprintf (f
, ", ops%d[%u]", depth
, i
);
1398 fprintf (f
, ", seq, valueize);\n");
1399 fprintf (f
, " if (!res) return false;\n");
1400 fprintf (f
, " }\n");
1401 fprintf (f
, " else\n");
1402 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1404 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1405 fprintf (f
, ", ops%d[%u]", depth
, i
);
1406 fprintf (f
, ", valueize);\n");
1410 if (operation
->kind
== id_base::CODE
)
1411 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1412 ops
.length(), opr
, type
);
1414 fprintf (f
, " res = build_call_expr_loc (loc, "
1415 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1416 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1417 fprintf (f
, ", ops%d[%u]", depth
, i
);
1418 fprintf (f
, ");\n");
1420 fprintf (f
, " %s = res;\n", dest
);
1424 /* Generate code for a c_expr which is either the expression inside
1425 an if statement or a sequence of statements which computes a
1426 result to be stored to DEST. */
1429 c_expr::gen_transform (FILE *f
, const char *dest
,
1430 bool, int, const char *, dt_operand
**)
1432 if (dest
&& nr_stmts
== 1)
1433 fprintf (f
, "%s = ", dest
);
1435 unsigned stmt_nr
= 1;
1436 for (unsigned i
= 0; i
< code
.length (); ++i
)
1438 const cpp_token
*token
= &code
[i
];
1440 /* Replace captures for code-gen. */
1441 if (token
->type
== CPP_ATSIGN
)
1443 const cpp_token
*n
= &code
[i
+1];
1444 if ((n
->type
== CPP_NUMBER
1445 || n
->type
== CPP_NAME
)
1446 && !(n
->flags
& PREV_WHITE
))
1448 if (token
->flags
& PREV_WHITE
)
1451 if (n
->type
== CPP_NUMBER
)
1452 id
= (const char *)n
->val
.str
.text
;
1454 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1455 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1461 if (token
->flags
& PREV_WHITE
)
1464 if (token
->type
== CPP_NAME
)
1466 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1468 for (j
= 0; j
< ids
.length (); ++j
)
1470 if (strcmp (id
, ids
[j
].id
) == 0)
1472 fprintf (f
, "%s", ids
[j
].oper
);
1476 if (j
< ids
.length ())
1480 /* Output the token as string. */
1481 char *tk
= (char *)cpp_token_as_text (r
, token
);
1484 if (token
->type
== CPP_SEMICOLON
)
1487 if (dest
&& stmt_nr
== nr_stmts
)
1488 fprintf (f
, "\n %s = ", dest
);
1495 /* Generate transform code for a capture. */
1498 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1499 const char *in_type
, dt_operand
**indexes
)
1501 if (what
&& is_a
<expr
*> (what
))
1503 if (indexes
[where
] == 0)
1506 sprintf (buf
, "captures[%u]", where
);
1507 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1511 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1514 /* Return the name of the operand representing the decision tree node.
1515 Use NAME as space to generate it. */
1518 dt_operand::get_name (char *name
)
1521 sprintf (name
, "t");
1522 else if (parent
->level
== 1)
1523 sprintf (name
, "op%u", pos
);
1524 else if (parent
->type
== dt_node::DT_MATCH
)
1525 return parent
->get_name (name
);
1527 sprintf (name
, "o%u%u", parent
->level
, pos
);
1531 /* Fill NAME with the operand name at position POS. */
1534 dt_operand::gen_opname (char *name
, unsigned pos
)
1537 sprintf (name
, "op%u", pos
);
1539 sprintf (name
, "o%u%u", level
, pos
);
1542 /* Generate matching code for the decision tree operand which is
1546 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1548 predicate
*p
= as_a
<predicate
*> (op
);
1550 if (p
->p
->matchers
.exists ())
1552 /* If this is a predicate generated from a pattern mangle its
1553 name and pass on the valueize hook. */
1555 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1557 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1560 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1565 /* Generate matching code for the decision tree operand which is
1569 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1571 char match_opname
[20];
1572 match_dop
->get_name (match_opname
);
1573 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1574 opname
, match_opname
, opname
, match_opname
);
1579 /* Generate GIMPLE matching code for the decision tree operand. */
1582 dt_operand::gen_gimple_expr (FILE *f
)
1584 expr
*e
= static_cast<expr
*> (op
);
1585 id_base
*id
= e
->operation
;
1586 unsigned n_ops
= e
->ops
.length ();
1588 for (unsigned i
= 0; i
< n_ops
; ++i
)
1590 char child_opname
[20];
1591 gen_opname (child_opname
, i
);
1593 if (id
->kind
== id_base::CODE
)
1595 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1596 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1598 /* ??? If this is a memory operation we can't (and should not)
1599 match this. The only sensible operand types are
1600 SSA names and invariants. */
1601 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1603 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1604 "|| is_gimple_min_invariant (%s))\n"
1605 "&& (%s = do_valueize (valueize, %s)))\n"
1606 "{\n", child_opname
, child_opname
, child_opname
,
1611 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1612 child_opname
, i
+ 1);
1615 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1617 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1618 child_opname
, child_opname
);
1625 /* Generate GENERIC matching code for the decision tree operand. */
1628 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1630 expr
*e
= static_cast<expr
*> (op
);
1631 unsigned n_ops
= e
->ops
.length ();
1633 for (unsigned i
= 0; i
< n_ops
; ++i
)
1635 char child_opname
[20];
1636 gen_opname (child_opname
, i
);
1638 if (e
->operation
->kind
== id_base::CODE
)
1639 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1640 child_opname
, opname
, i
);
1642 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1643 child_opname
, opname
, i
);
1649 /* Generate matching code for the children of the decision tree node. */
1652 dt_node::gen_kids (FILE *f
, bool gimple
)
1654 auto_vec
<dt_operand
*> gimple_exprs
;
1655 auto_vec
<dt_operand
*> generic_exprs
;
1656 auto_vec
<dt_operand
*> fns
;
1657 auto_vec
<dt_operand
*> generic_fns
;
1658 auto_vec
<dt_operand
*> preds
;
1659 auto_vec
<dt_node
*> others
;
1660 dt_node
*true_operand
= NULL
;
1662 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1664 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1666 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1667 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1669 if (e
->ops
.length () == 0)
1670 generic_exprs
.safe_push (op
);
1671 else if (e
->operation
->kind
== id_base::FN
)
1676 generic_fns
.safe_push (op
);
1678 else if (e
->operation
->kind
== id_base::PREDICATE
)
1679 preds
.safe_push (op
);
1683 gimple_exprs
.safe_push (op
);
1685 generic_exprs
.safe_push (op
);
1688 else if (op
->op
->type
== operand::OP_PREDICATE
)
1689 others
.safe_push (kids
[i
]);
1693 else if (kids
[i
]->type
== dt_node::DT_MATCH
1694 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1695 others
.safe_push (kids
[i
]);
1696 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1697 true_operand
= kids
[i
];
1703 char *kid_opname
= buf
;
1705 unsigned exprs_len
= gimple_exprs
.length ();
1706 unsigned gexprs_len
= generic_exprs
.length ();
1707 unsigned fns_len
= fns
.length ();
1708 unsigned gfns_len
= generic_fns
.length ();
1710 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1713 gimple_exprs
[0]->get_name (kid_opname
);
1715 fns
[0]->get_name (kid_opname
);
1717 generic_fns
[0]->get_name (kid_opname
);
1719 generic_exprs
[0]->get_name (kid_opname
);
1721 fprintf (f
, "switch (TREE_CODE (%s))\n"
1725 if (exprs_len
|| fns_len
)
1727 fprintf (f
, "case SSA_NAME:\n");
1728 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
1730 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1734 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1735 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1737 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1739 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1740 id_base
*op
= e
->operation
;
1741 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1742 fprintf (f
, "CASE_CONVERT:\n");
1744 fprintf (f
, "case %s:\n", op
->id
);
1746 gimple_exprs
[i
]->gen (f
, true);
1747 fprintf (f
, "break;\n"
1750 fprintf (f
, "default:;\n"
1757 fprintf (f
, "else ");
1759 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1761 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1762 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1765 for (unsigned i
= 0; i
< fns_len
; ++i
)
1767 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1768 fprintf (f
, "case %s:\n"
1769 "{\n", e
->operation
->id
);
1770 fns
[i
]->gen (f
, true);
1771 fprintf (f
, "break;\n"
1775 fprintf (f
, "default:;\n"
1780 fprintf (f
, "break;\n"
1784 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1786 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1787 id_base
*op
= e
->operation
;
1788 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1789 fprintf (f
, "CASE_CONVERT:\n");
1791 fprintf (f
, "case %s:\n", op
->id
);
1793 generic_exprs
[i
]->gen (f
, gimple
);
1794 fprintf (f
, "break;\n"
1800 fprintf (f
, "case CALL_EXPR:\n"
1802 "tree fndecl = get_callee_fndecl (%s);\n"
1803 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1804 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1807 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1809 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1810 gcc_assert (e
->operation
->kind
== id_base::FN
);
1812 fprintf (f
, "case %s:\n"
1813 "{\n", e
->operation
->id
);
1814 generic_fns
[j
]->gen (f
, false);
1815 fprintf (f
, "break;\n"
1819 fprintf (f
, "default:;\n"
1825 /* Close switch (TREE_CODE ()). */
1826 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1827 fprintf (f
, "default:;\n"
1830 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1832 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1833 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1834 preds
[i
]->get_name (kid_opname
);
1835 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1836 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1837 gimple
? "gimple" : "tree",
1838 p
->id
, kid_opname
, kid_opname
,
1839 gimple
? ", valueize" : "");
1841 for (int j
= 0; j
< p
->nargs
; ++j
)
1843 char child_opname
[20];
1844 preds
[i
]->gen_opname (child_opname
, j
);
1845 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1847 preds
[i
]->gen_kids (f
, gimple
);
1851 for (unsigned i
= 0; i
< others
.length (); ++i
)
1852 others
[i
]->gen (f
, gimple
);
1855 true_operand
->gen (f
, gimple
);
1858 /* Generate matching code for the decision tree operand. */
1861 dt_operand::gen (FILE *f
, bool gimple
)
1866 unsigned n_braces
= 0;
1868 if (type
== DT_OPERAND
)
1871 case operand::OP_PREDICATE
:
1872 n_braces
= gen_predicate (f
, opname
, gimple
);
1875 case operand::OP_EXPR
:
1877 n_braces
= gen_gimple_expr (f
);
1879 n_braces
= gen_generic_expr (f
, opname
);
1885 else if (type
== DT_TRUE
)
1887 else if (type
== DT_MATCH
)
1888 n_braces
= gen_match_op (f
, opname
);
1892 gen_kids (f
, gimple
);
1894 for (unsigned i
= 0; i
< n_braces
; ++i
)
1899 /* For GENERIC we have to take care of wrapping multiple-used
1900 expressions with side-effects in save_expr and preserve side-effects
1901 of expressions with omit_one_operand. Analyze captures in
1902 match, result and with expressions and perform early-outs
1903 on the outermost match expression operands for cases we cannot
1908 capture_info (simplify
*s
);
1909 void walk_match (operand
*o
, unsigned toplevel_arg
, bool);
1910 void walk_result (operand
*o
, bool);
1911 void walk_c_expr (c_expr
*);
1917 bool force_no_side_effects_p
;
1918 unsigned long toplevel_msk
;
1919 int result_use_count
;
1922 auto_vec
<cinfo
> info
;
1923 unsigned long force_no_side_effects
;
1926 /* Analyze captures in S. */
1928 capture_info::capture_info (simplify
*s
)
1932 || ((e
= dyn_cast
<expr
*> (s
->result
))
1933 && is_a
<predicate_id
*> (e
->operation
)))
1935 force_no_side_effects
= -1;
1939 force_no_side_effects
= 0;
1940 info
.safe_grow_cleared (s
->capture_max
+ 1);
1941 e
= as_a
<expr
*> (s
->match
);
1942 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1943 walk_match (e
->ops
[i
], i
, false);
1945 walk_result (s
->result
, false);
1947 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1948 if (s
->ifexpr_vec
[i
].is_with
)
1949 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1952 /* Analyze captures in the match expression piece O. */
1955 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
, bool conditional_p
)
1957 if (capture
*c
= dyn_cast
<capture
*> (o
))
1959 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1960 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1961 /* Mark expr (non-leaf) captures and recurse. */
1963 && is_a
<expr
*> (c
->what
))
1965 info
[c
->where
].expr_p
= true;
1966 walk_match (c
->what
, toplevel_arg
, conditional_p
);
1969 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1971 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1973 bool cond_p
= conditional_p
;
1975 && *e
->operation
== COND_EXPR
)
1977 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1978 || *e
->operation
== TRUTH_ORIF_EXPR
)
1980 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
);
1983 else if (is_a
<predicate
*> (o
))
1985 /* Mark non-captured leafs toplevel arg for checking. */
1986 force_no_side_effects
|= 1 << toplevel_arg
;
1992 /* Analyze captures in the result expression piece O. */
1995 capture_info::walk_result (operand
*o
, bool conditional_p
)
1997 if (capture
*c
= dyn_cast
<capture
*> (o
))
1999 info
[c
->where
].result_use_count
++;
2000 /* If we substitute an expression capture we don't know
2001 which captures this will end up using (well, we don't
2002 compute that). Force the uses to be side-effect free
2003 which means forcing the toplevels that reach the
2004 expression side-effect free. */
2005 if (info
[c
->where
].expr_p
)
2006 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
2007 /* Mark CSE capture capture uses as forced to have
2010 && is_a
<expr
*> (c
->what
))
2012 info
[c
->where
].cse_p
= true;
2013 walk_result (c
->what
, true);
2016 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2018 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2020 bool cond_p
= conditional_p
;
2022 && *e
->operation
== COND_EXPR
)
2024 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2025 || *e
->operation
== TRUTH_ORIF_EXPR
)
2027 walk_result (e
->ops
[i
], cond_p
);
2030 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2036 /* Look for captures in the C expr E. */
2039 capture_info::walk_c_expr (c_expr
*e
)
2041 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
2042 unsigned p_depth
= 0;
2043 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2045 const cpp_token
*t
= &e
->code
[i
];
2046 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2047 if (t
->type
== CPP_NAME
2048 && strcmp ((const char *)CPP_HASHNODE
2049 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2050 && n
->type
== CPP_OPEN_PAREN
)
2052 else if (t
->type
== CPP_CLOSE_PAREN
2055 else if (p_depth
== 0
2056 && t
->type
== CPP_ATSIGN
2057 && (n
->type
== CPP_NUMBER
2058 || n
->type
== CPP_NAME
)
2059 && !(n
->flags
& PREV_WHITE
))
2062 if (n
->type
== CPP_NUMBER
)
2063 id
= (const char *)n
->val
.str
.text
;
2065 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2066 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
2072 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2073 step of a '(simplify ...)' or '(match ...)'. This handles everything
2074 that is not part of the decision tree (simplify->match). */
2077 dt_simplify::gen (FILE *f
, bool gimple
)
2080 output_line_directive (f
, s
->result_location
);
2081 if (s
->capture_max
>= 0)
2082 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2083 s
->capture_max
+ 1);
2085 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2089 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2092 unsigned n_braces
= 0;
2093 if (s
->ifexpr_vec
!= vNULL
)
2095 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2097 if_or_with
&w
= s
->ifexpr_vec
[i
];
2101 output_line_directive (f
, w
.location
);
2102 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2107 output_line_directive (f
, w
.location
);
2108 fprintf (f
, "if (");
2109 if (i
== s
->ifexpr_vec
.length () - 1
2110 || s
->ifexpr_vec
[i
+1].is_with
)
2111 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2120 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2124 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2129 while (j
< s
->ifexpr_vec
.length ()
2130 && !s
->ifexpr_vec
[j
].is_with
);
2140 /* Analyze captures and perform early-outs on the incoming arguments
2141 that cover cases we cannot handle. */
2142 capture_info
cinfo (s
);
2146 && !((e
= dyn_cast
<expr
*> (s
->result
))
2147 && is_a
<predicate_id
*> (e
->operation
)))
2149 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2150 if (cinfo
.force_no_side_effects
& (1 << i
))
2151 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2152 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2153 if (cinfo
.info
[i
].cse_p
)
2155 else if (cinfo
.info
[i
].force_no_side_effects_p
2156 && (cinfo
.info
[i
].toplevel_msk
2157 & cinfo
.force_no_side_effects
) == 0)
2158 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2159 "return NULL_TREE;\n", i
);
2160 else if ((cinfo
.info
[i
].toplevel_msk
2161 & cinfo
.force_no_side_effects
) != 0)
2162 /* Mark capture as having no side-effects if we had to verify
2163 that via forced toplevel operand checks. */
2164 cinfo
.info
[i
].force_no_side_effects_p
= true;
2167 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2168 "fprintf (dump_file, \"Applying pattern ");
2169 output_line_directive (f
, s
->result_location
, true);
2170 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2172 operand
*result
= s
->result
;
2175 /* If there is no result then this is a predicate implementation. */
2176 fprintf (f
, "return true;\n");
2180 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2181 in outermost position). */
2182 if (result
->type
== operand::OP_EXPR
2183 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2184 result
= as_a
<expr
*> (result
)->ops
[0];
2185 if (result
->type
== operand::OP_EXPR
)
2187 expr
*e
= as_a
<expr
*> (result
);
2188 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2190 fprintf (f
, "*res_code = %s;\n",
2191 *e
->operation
== CONVERT_EXPR
2192 ? "NOP_EXPR" : e
->operation
->id
);
2193 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2196 snprintf (dest
, 32, " res_ops[%d]", j
);
2198 = get_operand_type (e
->operation
,
2199 "type", e
->expr_type
,
2201 ? NULL
: "TREE_TYPE (res_ops[0])");
2202 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
2205 /* Re-fold the toplevel result. It's basically an embedded
2206 gimple_build w/o actually building the stmt. */
2208 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2209 "res_ops, valueize);\n", e
->ops
.length ());
2211 else if (result
->type
== operand::OP_CAPTURE
2212 || result
->type
== operand::OP_C_EXPR
)
2214 result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
2215 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2219 fprintf (f
, "return true;\n");
2223 bool is_predicate
= false;
2224 if (result
->type
== operand::OP_EXPR
)
2226 expr
*e
= as_a
<expr
*> (result
);
2227 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2228 /* Search for captures used multiple times in the result expression
2229 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2231 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2233 if (!cinfo
.info
[i
].force_no_side_effects_p
2234 && cinfo
.info
[i
].result_use_count
> 1)
2235 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2236 " captures[%d] = save_expr (captures[%d]);\n",
2239 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2243 snprintf (dest
, 32, "res_ops[%d]", j
);
2246 fprintf (f
, " tree res_op%d;\n", j
);
2247 snprintf (dest
, 32, " res_op%d", j
);
2250 = get_operand_type (e
->operation
,
2251 "type", e
->expr_type
,
2253 ? NULL
: "TREE_TYPE (res_op0)");
2254 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2257 fprintf (f
, "return true;\n");
2260 fprintf (f
, " tree res;\n");
2261 /* Re-fold the toplevel result. Use non_lvalue to
2262 build NON_LVALUE_EXPRs so they get properly
2263 ignored when in GIMPLE form. */
2264 if (*e
->operation
== NON_LVALUE_EXPR
)
2265 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2268 if (e
->operation
->kind
== id_base::CODE
)
2269 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2271 *e
->operation
== CONVERT_EXPR
2272 ? "NOP_EXPR" : e
->operation
->id
);
2274 fprintf (f
, " res = build_call_expr_loc "
2275 "(loc, builtin_decl_implicit (%s), %d",
2276 e
->operation
->id
, e
->ops
.length());
2277 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2278 fprintf (f
, ", res_op%d", j
);
2279 fprintf (f
, ");\n");
2283 else if (result
->type
== operand::OP_CAPTURE
2284 || result
->type
== operand::OP_C_EXPR
)
2287 fprintf (f
, " tree res;\n");
2288 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2294 /* Search for captures not used in the result expression and dependent
2295 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2296 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2298 if (!cinfo
.info
[i
].force_no_side_effects_p
2299 && !cinfo
.info
[i
].expr_p
2300 && cinfo
.info
[i
].result_use_count
== 0)
2301 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2302 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2303 " fold_ignored_result (captures[%d]), res);\n",
2306 fprintf (f
, " return res;\n");
2310 for (unsigned i
= 0; i
< n_braces
; ++i
)
2316 /* Main entry to generate code for matching GIMPLE IL off the decision
2320 decision_tree::gen_gimple (FILE *f
)
2322 for (unsigned n
= 1; n
<= 3; ++n
)
2324 fprintf (f
, "\nstatic bool\n"
2325 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2326 " gimple_seq *seq, tree (*valueize)(tree),\n"
2327 " code_helper code, tree type");
2328 for (unsigned i
= 0; i
< n
; ++i
)
2329 fprintf (f
, ", tree op%d", i
);
2333 fprintf (f
, "switch (code.get_rep())\n"
2335 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2337 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2338 expr
*e
= static_cast<expr
*>(dop
->op
);
2339 if (e
->ops
.length () != n
)
2342 if (*e
->operation
== CONVERT_EXPR
2343 || *e
->operation
== NOP_EXPR
)
2344 fprintf (f
, "CASE_CONVERT:\n");
2346 fprintf (f
, "case %s%s:\n",
2347 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2350 dop
->gen_kids (f
, true);
2351 fprintf (f
, "break;\n");
2354 fprintf (f
, "default:;\n"
2357 fprintf (f
, "return false;\n");
2362 /* Main entry to generate code for matching GENERIC IL off the decision
2366 decision_tree::gen_generic (FILE *f
)
2368 for (unsigned n
= 1; n
<= 3; ++n
)
2370 fprintf (f
, "\ntree\n"
2371 "generic_simplify (location_t loc, enum tree_code code, "
2372 "tree type ATTRIBUTE_UNUSED");
2373 for (unsigned i
= 0; i
< n
; ++i
)
2374 fprintf (f
, ", tree op%d", i
);
2378 fprintf (f
, "switch (code)\n"
2380 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2382 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2383 expr
*e
= static_cast<expr
*>(dop
->op
);
2384 if (e
->ops
.length () != n
2385 /* Builtin simplifications are somewhat premature on
2386 GENERIC. The following drops patterns with outermost
2387 calls. It's easy to emit overloads for function code
2388 though if necessary. */
2389 || e
->operation
->kind
!= id_base::CODE
)
2392 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2393 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2394 fprintf (f
, "CASE_CONVERT:\n");
2396 fprintf (f
, "case %s:\n", e
->operation
->id
);
2398 dop
->gen_kids (f
, false);
2399 fprintf (f
, "break;\n"
2402 fprintf (f
, "default:;\n"
2405 fprintf (f
, "return NULL_TREE;\n");
2410 /* Output code to implement the predicate P from the decision tree DT. */
2413 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2415 fprintf (f
, "\nbool\n"
2416 "%s%s (tree t%s%s)\n"
2417 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2418 p
->nargs
> 0 ? ", tree *res_ops" : "",
2419 gimple
? ", tree (*valueize)(tree)" : "");
2420 /* Conveniently make 'type' available. */
2421 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2424 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2425 dt
.root
->gen_kids (f
, gimple
);
2427 fprintf (f
, "return false;\n"
2431 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2434 write_header (FILE *f
, const char *head
)
2436 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2437 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2439 /* Include the header instead of writing it awkwardly quoted here. */
2440 fprintf (f
, "\n#include \"%s\"\n", head
);
2450 parser (cpp_reader
*);
2453 const cpp_token
*next ();
2454 const cpp_token
*peek ();
2455 const cpp_token
*peek_ident (const char * = NULL
);
2456 const cpp_token
*expect (enum cpp_ttype
);
2457 void eat_token (enum cpp_ttype
);
2458 const char *get_string ();
2459 const char *get_ident ();
2460 void eat_ident (const char *);
2461 const char *get_number ();
2463 id_base
*parse_operation ();
2464 operand
*parse_capture (operand
*);
2465 operand
*parse_expr ();
2466 c_expr
*parse_c_expr (cpp_ttype
);
2467 operand
*parse_op ();
2469 void parse_pattern ();
2470 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2472 void parse_for (source_location
);
2473 void parse_if (source_location
);
2474 void parse_predicates (source_location
);
2477 vec
<if_or_with
> active_ifs
;
2478 vec
<vec
<user_id
*> > active_fors
;
2480 cid_map_t
*capture_ids
;
2483 vec
<simplify
*> simplifiers
;
2484 vec
<predicate_id
*> user_predicates
;
2487 /* Lexing helpers. */
2489 /* Read the next non-whitespace token from R. */
2494 const cpp_token
*token
;
2497 token
= cpp_get_token (r
);
2499 while (token
->type
== CPP_PADDING
2500 && token
->type
!= CPP_EOF
);
2504 /* Peek at the next non-whitespace token from R. */
2509 const cpp_token
*token
;
2513 token
= cpp_peek_token (r
, i
++);
2515 while (token
->type
== CPP_PADDING
2516 && token
->type
!= CPP_EOF
);
2517 /* If we peek at EOF this is a fatal error as it leaves the
2518 cpp_reader in unusable state. Assume we really wanted a
2519 token and thus this EOF is unexpected. */
2520 if (token
->type
== CPP_EOF
)
2521 fatal_at (token
, "unexpected end of file");
2525 /* Peek at the next identifier token (or return NULL if the next
2526 token is not an identifier or equal to ID if supplied). */
2529 parser::peek_ident (const char *id
)
2531 const cpp_token
*token
= peek ();
2532 if (token
->type
!= CPP_NAME
)
2538 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2539 if (strcmp (id
, t
) == 0)
2545 /* Read the next token from R and assert it is of type TK. */
2548 parser::expect (enum cpp_ttype tk
)
2550 const cpp_token
*token
= next ();
2551 if (token
->type
!= tk
)
2552 fatal_at (token
, "expected %s, got %s",
2553 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2558 /* Consume the next token from R and assert it is of type TK. */
2561 parser::eat_token (enum cpp_ttype tk
)
2566 /* Read the next token from R and assert it is of type CPP_STRING and
2567 return its value. */
2570 parser::get_string ()
2572 const cpp_token
*token
= expect (CPP_STRING
);
2573 return (const char *)token
->val
.str
.text
;
2576 /* Read the next token from R and assert it is of type CPP_NAME and
2577 return its value. */
2580 parser::get_ident ()
2582 const cpp_token
*token
= expect (CPP_NAME
);
2583 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2586 /* Eat an identifier token with value S from R. */
2589 parser::eat_ident (const char *s
)
2591 const cpp_token
*token
= peek ();
2592 const char *t
= get_ident ();
2593 if (strcmp (s
, t
) != 0)
2594 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2597 /* Read the next token from R and assert it is of type CPP_NUMBER and
2598 return its value. */
2601 parser::get_number ()
2603 const cpp_token
*token
= expect (CPP_NUMBER
);
2604 return (const char *)token
->val
.str
.text
;
2608 /* Parse the operator ID, special-casing convert?, convert1? and
2612 parser::parse_operation ()
2614 const cpp_token
*id_tok
= peek ();
2615 const char *id
= get_ident ();
2616 const cpp_token
*token
= peek ();
2617 if (strcmp (id
, "convert0") == 0)
2618 fatal_at (id_tok
, "use 'convert?' here");
2619 if (token
->type
== CPP_QUERY
2620 && !(token
->flags
& PREV_WHITE
))
2622 if (strcmp (id
, "convert") == 0)
2624 else if (strcmp (id
, "convert1") == 0)
2626 else if (strcmp (id
, "convert2") == 0)
2629 fatal_at (id_tok
, "non-convert operator conditionalized");
2630 eat_token (CPP_QUERY
);
2632 else if (strcmp (id
, "convert1") == 0
2633 || strcmp (id
, "convert2") == 0)
2634 fatal_at (id_tok
, "expected '?' after conditional operator");
2635 id_base
*op
= get_operator (id
);
2637 fatal_at (id_tok
, "unknown operator %s", id
);
2642 capture = '@'<number> */
2645 parser::parse_capture (operand
*op
)
2647 eat_token (CPP_ATSIGN
);
2648 const cpp_token
*token
= peek ();
2650 if (token
->type
== CPP_NUMBER
)
2652 else if (token
->type
== CPP_NAME
)
2655 fatal_at (token
, "expected number or identifier");
2656 unsigned next_id
= capture_ids
->elements ();
2658 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2661 return new capture (num
, op
);
2664 /* Parse an expression
2665 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2668 parser::parse_expr ()
2670 expr
*e
= new expr (parse_operation ());
2671 const cpp_token
*token
= peek ();
2673 bool is_commutative
= false;
2674 const char *expr_type
= NULL
;
2676 if (token
->type
== CPP_COLON
2677 && !(token
->flags
& PREV_WHITE
))
2679 eat_token (CPP_COLON
);
2681 if (token
->type
== CPP_NAME
2682 && !(token
->flags
& PREV_WHITE
))
2684 const char *s
= get_ident ();
2685 if (s
[0] == 'c' && !s
[1])
2686 is_commutative
= true;
2687 else if (s
[1] != '\0')
2690 fatal_at (token
, "flag %s not recognized", s
);
2694 fatal_at (token
, "expected flag or type specifying identifier");
2697 if (token
->type
== CPP_ATSIGN
2698 && !(token
->flags
& PREV_WHITE
))
2699 op
= parse_capture (e
);
2704 const cpp_token
*token
= peek ();
2705 if (token
->type
== CPP_CLOSE_PAREN
)
2707 if (e
->operation
->nargs
!= -1
2708 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2709 fatal_at (token
, "'%s' expects %u operands, not %u",
2710 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2713 if (e
->ops
.length () == 2)
2714 e
->is_commutative
= true;
2716 fatal_at (token
, "only binary operators or function with "
2717 "two arguments can be marked commutative");
2719 e
->expr_type
= expr_type
;
2722 e
->append_op (parse_op ());
2727 /* Lex native C code delimited by START recording the preprocessing tokens
2728 for later processing.
2729 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2732 parser::parse_c_expr (cpp_ttype start
)
2734 const cpp_token
*token
;
2737 vec
<cpp_token
> code
= vNULL
;
2738 unsigned nr_stmts
= 0;
2740 if (start
== CPP_OPEN_PAREN
)
2741 end
= CPP_CLOSE_PAREN
;
2742 else if (start
== CPP_OPEN_BRACE
)
2743 end
= CPP_CLOSE_BRACE
;
2751 /* Count brace pairs to find the end of the expr to match. */
2752 if (token
->type
== start
)
2754 else if (token
->type
== end
2758 /* This is a lame way of counting the number of statements. */
2759 if (token
->type
== CPP_SEMICOLON
)
2762 /* Record the token. */
2763 code
.safe_push (*token
);
2766 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2769 /* Parse an operand which is either an expression, a predicate or
2770 a standalone capture.
2771 op = predicate | expr | c_expr | capture */
2776 const cpp_token
*token
= peek ();
2777 struct operand
*op
= NULL
;
2778 if (token
->type
== CPP_OPEN_PAREN
)
2780 eat_token (CPP_OPEN_PAREN
);
2782 eat_token (CPP_CLOSE_PAREN
);
2784 else if (token
->type
== CPP_OPEN_BRACE
)
2786 op
= parse_c_expr (CPP_OPEN_BRACE
);
2790 /* Remaining ops are either empty or predicates */
2791 if (token
->type
== CPP_NAME
)
2793 const char *id
= get_ident ();
2794 id_base
*opr
= get_operator (id
);
2796 fatal_at (token
, "expected predicate name");
2797 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2799 if (code
->nargs
!= 0)
2800 fatal_at (token
, "using an operator with operands as predicate");
2801 /* Parse the zero-operand operator "predicates" as
2803 op
= new expr (opr
);
2805 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2806 op
= new predicate (p
);
2808 fatal_at (token
, "using an unsupported operator as predicate");
2810 if (token
->flags
& PREV_WHITE
)
2813 else if (token
->type
!= CPP_COLON
2814 && token
->type
!= CPP_ATSIGN
)
2815 fatal_at (token
, "expected expression or predicate");
2816 /* optionally followed by a capture and a predicate. */
2817 if (token
->type
== CPP_COLON
)
2818 fatal_at (token
, "not implemented: predicate on leaf operand");
2819 if (token
->type
== CPP_ATSIGN
)
2820 op
= parse_capture (op
);
2827 simplify = 'simplify' <expr> <result-op>
2829 match = 'match' <ident> <expr> [<result-op>]
2831 <result-op> = <op> | <if> | <with>
2832 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2833 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2834 and fill SIMPLIFIERS with the results. */
2837 parser::parse_simplify (source_location match_location
,
2838 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2841 /* Reset the capture map. */
2842 capture_ids
= new cid_map_t
;
2844 const cpp_token
*loc
= peek ();
2845 struct operand
*match
= parse_op ();
2846 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2847 fatal_at (loc
, "outermost expression cannot be captured");
2848 if (match
->type
== operand::OP_EXPR
2849 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2850 fatal_at (loc
, "outermost expression cannot be a predicate");
2852 const cpp_token
*token
= peek ();
2854 /* If this if is immediately closed then it is part of a predicate
2855 definition. Push it. */
2856 if (token
->type
== CPP_CLOSE_PAREN
)
2859 fatal_at (token
, "expected transform expression");
2860 simplifiers
.safe_push
2861 (new simplify (match
, match_location
, result
, token
->src_loc
,
2862 active_ifs
.copy (), active_fors
.copy (),
2867 unsigned active_ifs_len
= active_ifs
.length ();
2870 if (token
->type
== CPP_OPEN_PAREN
)
2872 source_location paren_loc
= token
->src_loc
;
2873 eat_token (CPP_OPEN_PAREN
);
2874 if (peek_ident ("if"))
2877 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2878 token
->src_loc
, false));
2879 /* If this if is immediately closed then it contains a
2880 manual matcher or is part of a predicate definition.
2882 if (peek ()->type
== CPP_CLOSE_PAREN
)
2885 fatal_at (token
, "manual transform not implemented");
2886 simplifiers
.safe_push
2887 (new simplify (match
, match_location
, result
,
2888 paren_loc
, active_ifs
.copy (),
2889 active_fors
.copy (), capture_ids
));
2892 else if (peek_ident ("with"))
2895 /* Parse (with c-expr expr) as (if-with (true) expr). */
2896 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2898 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2902 operand
*op
= result
;
2905 simplifiers
.safe_push
2906 (new simplify (match
, match_location
, op
,
2907 token
->src_loc
, active_ifs
.copy (),
2908 active_fors
.copy (), capture_ids
));
2909 eat_token (CPP_CLOSE_PAREN
);
2910 /* A "default" result closes the enclosing scope. */
2911 if (active_ifs
.length () > active_ifs_len
)
2913 eat_token (CPP_CLOSE_PAREN
);
2920 else if (token
->type
== CPP_CLOSE_PAREN
)
2922 /* Close a scope if requested. */
2923 if (active_ifs
.length () > active_ifs_len
)
2925 eat_token (CPP_CLOSE_PAREN
);
2935 fatal_at (token
, "expected match operand expression");
2936 simplifiers
.safe_push
2937 (new simplify (match
, match_location
,
2938 matcher
? result
: parse_op (),
2939 token
->src_loc
, active_ifs
.copy (),
2940 active_fors
.copy (), capture_ids
));
2941 /* A "default" result closes the enclosing scope. */
2942 if (active_ifs
.length () > active_ifs_len
)
2944 eat_token (CPP_CLOSE_PAREN
);
2954 /* Parsing of the outer control structures. */
2956 /* Parse a for expression
2957 for = '(' 'for' <subst>... <pattern> ')'
2958 subst = <ident> '(' <ident>... ')' */
2961 parser::parse_for (source_location
)
2963 vec
<user_id
*> user_ids
= vNULL
;
2964 const cpp_token
*token
;
2965 unsigned min_n_opers
= 0, max_n_opers
= 0;
2969 token
= peek_ident ();
2973 /* Insert the user defined operators into the operator hash. */
2974 const char *id
= get_ident ();
2975 user_id
*op
= new user_id (id
);
2976 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2978 fatal_at (token
, "operator already defined");
2980 user_ids
.safe_push (op
);
2982 eat_token (CPP_OPEN_PAREN
);
2985 while ((token
= peek_ident ()) != 0)
2987 const char *oper
= get_ident ();
2988 id_base
*idb
= get_operator (oper
);
2990 fatal_at (token
, "no such operator '%s'", oper
);
2991 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2992 fatal_at (token
, "conditional operators cannot be used inside for");
2996 else if (idb
->nargs
== -1)
2998 else if (idb
->nargs
!= arity
)
2999 fatal_at (token
, "operator '%s' with arity %d does not match "
3000 "others with arity %d", oper
, idb
->nargs
, arity
);
3002 op
->substitutes
.safe_push (idb
);
3005 token
= expect (CPP_CLOSE_PAREN
);
3007 unsigned nsubstitutes
= op
->substitutes
.length ();
3008 if (nsubstitutes
== 0)
3009 fatal_at (token
, "A user-defined operator must have at least "
3010 "one substitution");
3011 if (max_n_opers
== 0)
3013 min_n_opers
= nsubstitutes
;
3014 max_n_opers
= nsubstitutes
;
3018 if (nsubstitutes
% min_n_opers
!= 0
3019 && min_n_opers
% nsubstitutes
!= 0)
3020 fatal_at (token
, "All user-defined identifiers must have a "
3021 "multiple number of operator substitutions of the "
3022 "smallest number of substitutions");
3023 if (nsubstitutes
< min_n_opers
)
3024 min_n_opers
= nsubstitutes
;
3025 else if (nsubstitutes
> max_n_opers
)
3026 max_n_opers
= nsubstitutes
;
3030 unsigned n_ids
= user_ids
.length ();
3032 fatal_at (token
, "for requires at least one user-defined identifier");
3035 if (token
->type
== CPP_CLOSE_PAREN
)
3036 fatal_at (token
, "no pattern defined in for");
3038 active_fors
.safe_push (user_ids
);
3042 if (token
->type
== CPP_CLOSE_PAREN
)
3048 /* Remove user-defined operators from the hash again. */
3049 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3050 operators
->remove_elt (user_ids
[i
]);
3053 /* Parse an outer if expression.
3054 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3057 parser::parse_if (source_location loc
)
3059 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3061 const cpp_token
*token
= peek ();
3062 if (token
->type
== CPP_CLOSE_PAREN
)
3063 fatal_at (token
, "no pattern defined in if");
3065 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3068 const cpp_token
*token
= peek ();
3069 if (token
->type
== CPP_CLOSE_PAREN
)
3077 /* Parse a list of predefined predicate identifiers.
3078 preds = '(' 'define_predicates' <ident>... ')' */
3081 parser::parse_predicates (source_location
)
3085 const cpp_token
*token
= peek ();
3086 if (token
->type
!= CPP_NAME
)
3089 add_predicate (get_ident ());
3094 /* Parse outer control structures.
3095 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3098 parser::parse_pattern ()
3100 /* All clauses start with '('. */
3101 eat_token (CPP_OPEN_PAREN
);
3102 const cpp_token
*token
= peek ();
3103 const char *id
= get_ident ();
3104 if (strcmp (id
, "simplify") == 0)
3105 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3106 else if (strcmp (id
, "match") == 0)
3108 bool with_args
= false;
3109 if (peek ()->type
== CPP_OPEN_PAREN
)
3111 eat_token (CPP_OPEN_PAREN
);
3114 const char *name
= get_ident ();
3115 id_base
*id
= get_operator (name
);
3119 p
= add_predicate (name
);
3120 user_predicates
.safe_push (p
);
3122 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3125 fatal_at (token
, "cannot add a match to a non-predicate ID");
3126 /* Parse (match <id> <arg>... (match-expr)) here. */
3131 while (peek ()->type
== CPP_ATSIGN
)
3132 e
->append_op (parse_capture (NULL
));
3133 eat_token (CPP_CLOSE_PAREN
);
3136 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3137 || (!e
&& p
->nargs
!= 0)))
3138 fatal_at (token
, "non-matching number of match operands");
3139 p
->nargs
= e
? e
->ops
.length () : 0;
3140 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3142 else if (strcmp (id
, "for") == 0)
3143 parse_for (token
->src_loc
);
3144 else if (strcmp (id
, "if") == 0)
3145 parse_if (token
->src_loc
);
3146 else if (strcmp (id
, "define_predicates") == 0)
3148 if (active_ifs
.length () > 0
3149 || active_fors
.length () > 0)
3150 fatal_at (token
, "define_predicates inside if or for is not supported");
3151 parse_predicates (token
->src_loc
);
3154 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3155 active_ifs
.length () == 0 && active_fors
.length () == 0
3156 ? "'define_predicates', " : "");
3158 eat_token (CPP_CLOSE_PAREN
);
3161 /* Main entry of the parser. Repeatedly parse outer control structures. */
3163 parser::parser (cpp_reader
*r_
)
3167 active_fors
= vNULL
;
3168 simplifiers
= vNULL
;
3169 user_predicates
= vNULL
;
3171 const cpp_token
*token
= next ();
3172 while (token
->type
!= CPP_EOF
)
3174 _cpp_backup_tokens (r
, 1);
3181 /* Helper for the linemap code. */
3184 round_alloc_size (size_t s
)
3190 /* The genmatch generator progam. It reads from a pattern description
3191 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3194 main (int argc
, char **argv
)
3198 progname
= "genmatch";
3204 bool verbose
= false;
3205 char *input
= argv
[argc
-1];
3206 for (int i
= 1; i
< argc
- 1; ++i
)
3208 if (strcmp (argv
[i
], "--gimple") == 0)
3210 else if (strcmp (argv
[i
], "--generic") == 0)
3212 else if (strcmp (argv
[i
], "-v") == 0)
3216 fprintf (stderr
, "Usage: genmatch "
3217 "[--gimple] [--generic] [-v] input\n");
3222 line_table
= XCNEW (struct line_maps
);
3223 linemap_init (line_table
, 0);
3224 line_table
->reallocator
= xrealloc
;
3225 line_table
->round_alloc_size
= round_alloc_size
;
3227 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3228 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3229 cb
->error
= error_cb
;
3231 if (!cpp_read_main_file (r
, input
))
3233 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3234 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3236 /* Pre-seed operators. */
3237 operators
= new hash_table
<id_base
> (1024);
3238 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3239 add_operator (SYM, # SYM, # TYPE, NARGS);
3240 #define END_OF_BASE_TREE_CODES
3242 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3243 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3244 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3245 #undef END_OF_BASE_TREE_CODES
3248 /* Pre-seed builtin functions.
3249 ??? Cannot use N (name) as that is targetm.emultls.get_address
3250 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3251 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3252 add_builtin (ENUM, # ENUM);
3253 #include "builtins.def"
3260 write_header (stdout
, "gimple-match-head.c");
3262 write_header (stdout
, "generic-match-head.c");
3264 /* Go over all predicates defined with patterns and perform
3265 lowering and code generation. */
3266 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3268 predicate_id
*pred
= p
.user_predicates
[i
];
3269 lower (pred
->matchers
);
3272 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3273 print_matches (pred
->matchers
[i
]);
3276 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3277 dt
.insert (pred
->matchers
[i
], i
);
3282 write_predicate (stdout
, pred
, dt
, gimple
);
3285 /* Lower the main simplifiers and generate code for them. */
3286 lower (p
.simplifiers
);
3289 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3290 print_matches (p
.simplifiers
[i
]);
3293 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3294 dt
.insert (p
.simplifiers
[i
], i
);
3300 dt
.gen_gimple (stdout
);
3302 dt
.gen_generic (stdout
);
3305 cpp_finish (r
, NULL
);