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
);
129 /* Like fprintf, but print INDENT spaces at the beginning. */
132 #if GCC_VERSION >= 4001
133 __attribute__((format (printf
, 3, 4)))
135 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
138 for (; indent
>= 8; indent
-= 8)
140 fprintf (f
, "%*s", indent
, "");
141 va_start (ap
, format
);
142 vfprintf (f
, format
, ap
);
147 output_line_directive (FILE *f
, source_location location
,
148 bool dumpfile
= false)
150 const line_map_ordinary
*map
;
151 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
152 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
155 /* When writing to a dumpfile only dump the filename. */
156 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
161 fprintf (f
, "%s:%d", file
, loc
.line
);
164 /* Other gen programs really output line directives here, at least for
165 development it's right now more convenient to have line information
166 from the generated file. Still keep the directives as comment for now
167 to easily back-point to the meta-description. */
168 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
172 /* Pull in tree codes and builtin function codes from their
175 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
188 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
189 enum built_in_function
{
190 #include "builtins.def"
195 /* Return true if CODE represents a commutative tree code. Otherwise
198 commutative_tree_code (enum tree_code code
)
204 case MULT_HIGHPART_EXPR
:
219 case WIDEN_MULT_EXPR
:
220 case VEC_WIDEN_MULT_HI_EXPR
:
221 case VEC_WIDEN_MULT_LO_EXPR
:
222 case VEC_WIDEN_MULT_EVEN_EXPR
:
223 case VEC_WIDEN_MULT_ODD_EXPR
:
232 /* Return true if CODE represents a ternary tree code for which the
233 first two operands are commutative. Otherwise return false. */
235 commutative_ternary_tree_code (enum tree_code code
)
239 case WIDEN_MULT_PLUS_EXPR
:
240 case WIDEN_MULT_MINUS_EXPR
:
252 /* Base class for all identifiers the parser knows. */
254 struct id_base
: nofree_ptr_hash
<id_base
>
256 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
258 id_base (id_kind
, const char *, int = -1);
264 /* hash_table support. */
265 static inline hashval_t
hash (const id_base
*);
266 static inline int equal (const id_base
*, const id_base
*);
270 id_base::hash (const id_base
*op
)
276 id_base::equal (const id_base
*op1
,
279 return (op1
->hashval
== op2
->hashval
280 && strcmp (op1
->id
, op2
->id
) == 0);
283 /* Hashtable of known pattern operators. This is pre-seeded from
284 all known tree codes and all known builtin function ids. */
285 static hash_table
<id_base
> *operators
;
287 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
292 hashval
= htab_hash_string (id
);
295 /* Identifier that maps to a tree code. */
297 struct operator_id
: public id_base
299 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
301 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
306 /* Identifier that maps to a builtin function code. */
308 struct fn_id
: public id_base
310 fn_id (enum built_in_function fn_
, const char *id_
)
311 : id_base (id_base::FN
, id_
), fn (fn_
) {}
312 enum built_in_function fn
;
317 /* Identifier that maps to a user-defined predicate. */
319 struct predicate_id
: public id_base
321 predicate_id (const char *id_
)
322 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
323 vec
<simplify
*> matchers
;
326 /* Identifier that maps to a operator defined by a 'for' directive. */
328 struct user_id
: public id_base
330 user_id (const char *id_
, bool is_oper_list_
= false)
331 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
332 used (false), is_oper_list (is_oper_list_
) {}
333 vec
<id_base
*> substitutes
;
341 is_a_helper
<fn_id
*>::test (id_base
*id
)
343 return id
->kind
== id_base::FN
;
349 is_a_helper
<operator_id
*>::test (id_base
*id
)
351 return id
->kind
== id_base::CODE
;
357 is_a_helper
<predicate_id
*>::test (id_base
*id
)
359 return id
->kind
== id_base::PREDICATE
;
365 is_a_helper
<user_id
*>::test (id_base
*id
)
367 return id
->kind
== id_base::USER
;
370 /* Add a predicate identifier to the hash. */
372 static predicate_id
*
373 add_predicate (const char *id
)
375 predicate_id
*p
= new predicate_id (id
);
376 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
378 fatal ("duplicate id definition");
383 /* Add a tree code identifier to the hash. */
386 add_operator (enum tree_code code
, const char *id
,
387 const char *tcc
, unsigned nargs
)
389 if (strcmp (tcc
, "tcc_unary") != 0
390 && strcmp (tcc
, "tcc_binary") != 0
391 && strcmp (tcc
, "tcc_comparison") != 0
392 && strcmp (tcc
, "tcc_expression") != 0
393 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
394 && strcmp (tcc
, "tcc_reference") != 0
395 /* To have INTEGER_CST and friends as "predicate operators". */
396 && strcmp (tcc
, "tcc_constant") != 0
397 /* And allow CONSTRUCTOR for vector initializers. */
398 && !(code
== CONSTRUCTOR
))
400 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
401 if (code
== ADDR_EXPR
)
403 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
404 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
406 fatal ("duplicate id definition");
410 /* Add a builtin identifier to the hash. */
413 add_builtin (enum built_in_function code
, const char *id
)
415 fn_id
*fn
= new fn_id (code
, id
);
416 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
418 fatal ("duplicate id definition");
422 /* Helper for easy comparing ID with tree code CODE. */
425 operator==(id_base
&id
, enum tree_code code
)
427 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
428 return oid
->code
== code
;
432 /* Lookup the identifier ID. */
435 get_operator (const char *id
)
437 id_base
tem (id_base::CODE
, id
);
439 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
442 /* If this is a user-defined identifier track whether it was used. */
443 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
448 /* Try all-uppercase. */
449 char *id2
= xstrdup (id
);
450 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
451 id2
[i
] = TOUPPER (id2
[i
]);
452 new (&tem
) id_base (id_base::CODE
, id2
);
453 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
460 /* Try _EXPR appended. */
461 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
462 strcat (id2
, "_EXPR");
463 new (&tem
) id_base (id_base::CODE
, id2
);
464 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
474 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
477 /* The AST produced by parsing of the pattern definitions. */
482 /* The base class for operands. */
485 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
486 operand (enum op_type type_
, source_location loc_
)
487 : type (type_
), location (loc_
) {}
489 source_location location
;
490 virtual void gen_transform (FILE *, int, const char *, bool, int,
491 const char *, capture_info
*,
494 { gcc_unreachable (); }
497 /* A predicate operand. Predicates are leafs in the AST. */
499 struct predicate
: public operand
501 predicate (predicate_id
*p_
, source_location loc
)
502 : operand (OP_PREDICATE
, loc
), p (p_
) {}
506 /* An operand that constitutes an expression. Expressions include
507 function calls and user-defined predicate invocations. */
509 struct expr
: public operand
511 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
512 : operand (OP_EXPR
, loc
), operation (operation_
),
513 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
514 is_generic (false), force_single_use (false) {}
516 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
517 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
518 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
519 void append_op (operand
*op
) { ops
.safe_push (op
); }
520 /* The operator and its operands. */
523 /* An explicitely specified type - used exclusively for conversions. */
524 const char *expr_type
;
525 /* Whether the operation is to be applied commutatively. This is
526 later lowered to two separate patterns. */
528 /* Whether the expression is expected to be in GENERIC form. */
530 /* Whether pushing any stmt to the sequence should be conditional
531 on this expression having a single-use. */
532 bool force_single_use
;
533 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
534 const char *, capture_info
*,
535 dt_operand
** = 0, bool = true);
538 /* An operator that is represented by native C code. This is always
539 a leaf operand in the AST. This class is also used to represent
540 the code to be generated for 'if' and 'with' expressions. */
542 struct c_expr
: public operand
544 /* A mapping of an identifier and its replacement. Used to apply
549 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
552 c_expr (cpp_reader
*r_
, source_location loc
,
553 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
554 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
555 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
556 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
557 /* cpplib tokens and state to transform this back to source. */
560 cid_map_t
*capture_ids
;
561 /* The number of statements parsed (well, the number of ';'s). */
563 /* The identifier replacement vector. */
565 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
566 const char *, capture_info
*,
567 dt_operand
** = 0, bool = true);
570 /* A wrapper around another operand that captures its value. */
572 struct capture
: public operand
574 capture (source_location loc
, unsigned where_
, operand
*what_
)
575 : operand (OP_CAPTURE
, loc
), where (where_
), what (what_
) {}
576 /* Identifier index for the value. */
578 /* The captured value. */
580 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
581 const char *, capture_info
*,
582 dt_operand
** = 0, bool = true);
587 struct if_expr
: public operand
589 if_expr (source_location loc
)
590 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
596 /* with expression. */
598 struct with_expr
: public operand
600 with_expr (source_location loc
)
601 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
609 is_a_helper
<capture
*>::test (operand
*op
)
611 return op
->type
== operand::OP_CAPTURE
;
617 is_a_helper
<predicate
*>::test (operand
*op
)
619 return op
->type
== operand::OP_PREDICATE
;
625 is_a_helper
<c_expr
*>::test (operand
*op
)
627 return op
->type
== operand::OP_C_EXPR
;
633 is_a_helper
<expr
*>::test (operand
*op
)
635 return op
->type
== operand::OP_EXPR
;
641 is_a_helper
<if_expr
*>::test (operand
*op
)
643 return op
->type
== operand::OP_IF
;
649 is_a_helper
<with_expr
*>::test (operand
*op
)
651 return op
->type
== operand::OP_WITH
;
654 /* The main class of a pattern and its transform. This is used to
655 represent both (simplify ...) and (match ...) kinds. The AST
656 duplicates all outer 'if' and 'for' expressions here so each
657 simplify can exist in isolation. */
661 enum simplify_kind
{ SIMPLIFY
, MATCH
};
663 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
664 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
665 : kind (kind_
), match (match_
), result (result_
),
667 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
670 /* The expression that is matched against the GENERIC or GIMPLE IL. */
672 /* For a (simplify ...) an expression with ifs and withs with the expression
673 produced when the pattern applies in the leafs.
674 For a (match ...) the leafs are either empty if it is a simple predicate
675 or the single expression specifying the matched operands. */
676 struct operand
*result
;
677 /* Collected 'for' expression operators that have to be replaced
678 in the lowering phase. */
679 vec
<vec
<user_id
*> > for_vec
;
680 /* A map of capture identifiers to indexes. */
681 cid_map_t
*capture_ids
;
685 /* Debugging routines for dumping the AST. */
688 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
690 if (capture
*c
= dyn_cast
<capture
*> (o
))
692 fprintf (f
, "@%u", c
->where
);
693 if (c
->what
&& flattened
== false)
696 print_operand (c
->what
, f
, flattened
);
701 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
702 fprintf (f
, "%s", p
->p
->id
);
704 else if (is_a
<c_expr
*> (o
))
705 fprintf (f
, "c_expr");
707 else if (expr
*e
= dyn_cast
<expr
*> (o
))
709 fprintf (f
, "(%s", e
->operation
->id
);
711 if (flattened
== false)
714 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
716 print_operand (e
->ops
[i
], f
, flattened
);
728 print_matches (struct simplify
*s
, FILE *f
= stderr
)
730 fprintf (f
, "for expression: ");
731 print_operand (s
->match
, f
);
738 /* Lowering of commutative operators. */
741 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
742 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
744 if (n
== ops_vector
.length ())
746 vec
<operand
*> xv
= v
.copy ();
747 result
.safe_push (xv
);
751 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
753 v
[n
] = ops_vector
[n
][i
];
754 cartesian_product (ops_vector
, result
, v
, n
+ 1);
758 /* Lower OP to two operands in case it is marked as commutative. */
760 static vec
<operand
*>
761 commutate (operand
*op
)
763 vec
<operand
*> ret
= vNULL
;
765 if (capture
*c
= dyn_cast
<capture
*> (op
))
772 vec
<operand
*> v
= commutate (c
->what
);
773 for (unsigned i
= 0; i
< v
.length (); ++i
)
775 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
]);
781 expr
*e
= dyn_cast
<expr
*> (op
);
782 if (!e
|| e
->ops
.length () == 0)
788 vec
< vec
<operand
*> > ops_vector
= vNULL
;
789 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
790 ops_vector
.safe_push (commutate (e
->ops
[i
]));
792 auto_vec
< vec
<operand
*> > result
;
793 auto_vec
<operand
*> v (e
->ops
.length ());
794 v
.quick_grow_cleared (e
->ops
.length ());
795 cartesian_product (ops_vector
, result
, v
, 0);
798 for (unsigned i
= 0; i
< result
.length (); ++i
)
800 expr
*ne
= new expr (e
);
801 ne
->is_commutative
= false;
802 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
803 ne
->append_op (result
[i
][j
]);
807 if (!e
->is_commutative
)
810 for (unsigned i
= 0; i
< result
.length (); ++i
)
812 expr
*ne
= new expr (e
);
813 ne
->is_commutative
= false;
814 // result[i].length () is 2 since e->operation is binary
815 for (unsigned j
= result
[i
].length (); j
; --j
)
816 ne
->append_op (result
[i
][j
-1]);
823 /* Lower operations marked as commutative in the AST of S and push
824 the resulting patterns to SIMPLIFIERS. */
827 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
829 vec
<operand
*> matchers
= commutate (s
->match
);
830 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
832 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
833 s
->for_vec
, s
->capture_ids
);
834 simplifiers
.safe_push (ns
);
838 /* Strip conditional conversios using operator OPER from O and its
839 children if STRIP, else replace them with an unconditional convert. */
842 lower_opt_convert (operand
*o
, enum tree_code oper
,
843 enum tree_code to_oper
, bool strip
)
845 if (capture
*c
= dyn_cast
<capture
*> (o
))
848 return new capture (c
->location
, c
->where
,
849 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
854 expr
*e
= dyn_cast
<expr
*> (o
);
858 if (*e
->operation
== oper
)
861 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
863 expr
*ne
= new expr (e
);
864 ne
->operation
= (to_oper
== CONVERT_EXPR
865 ? get_operator ("CONVERT_EXPR")
866 : get_operator ("VIEW_CONVERT_EXPR"));
867 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
871 expr
*ne
= new expr (e
);
872 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
873 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
878 /* Determine whether O or its children uses the conditional conversion
882 has_opt_convert (operand
*o
, enum tree_code oper
)
884 if (capture
*c
= dyn_cast
<capture
*> (o
))
887 return has_opt_convert (c
->what
, oper
);
892 expr
*e
= dyn_cast
<expr
*> (o
);
896 if (*e
->operation
== oper
)
899 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
900 if (has_opt_convert (e
->ops
[i
], oper
))
906 /* Lower conditional convert operators in O, expanding it to a vector
909 static vec
<operand
*>
910 lower_opt_convert (operand
*o
)
912 vec
<operand
*> v1
= vNULL
, v2
;
916 enum tree_code opers
[]
917 = { CONVERT0
, CONVERT_EXPR
,
918 CONVERT1
, CONVERT_EXPR
,
919 CONVERT2
, CONVERT_EXPR
,
920 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
921 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
922 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
924 /* Conditional converts are lowered to a pattern with the
925 conversion and one without. The three different conditional
926 convert codes are lowered separately. */
928 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
931 for (unsigned j
= 0; j
< v1
.length (); ++j
)
932 if (has_opt_convert (v1
[j
], opers
[i
]))
934 v2
.safe_push (lower_opt_convert (v1
[j
],
935 opers
[i
], opers
[i
+1], false));
936 v2
.safe_push (lower_opt_convert (v1
[j
],
937 opers
[i
], opers
[i
+1], true));
943 for (unsigned j
= 0; j
< v2
.length (); ++j
)
944 v1
.safe_push (v2
[j
]);
951 /* Lower conditional convert operators in the AST of S and push
952 the resulting multiple patterns to SIMPLIFIERS. */
955 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
957 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
958 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
960 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
961 s
->for_vec
, s
->capture_ids
);
962 simplifiers
.safe_push (ns
);
966 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
967 GENERIC and a GIMPLE variant. */
969 static vec
<operand
*>
970 lower_cond (operand
*o
)
972 vec
<operand
*> ro
= vNULL
;
974 if (capture
*c
= dyn_cast
<capture
*> (o
))
978 vec
<operand
*> lop
= vNULL
;
979 lop
= lower_cond (c
->what
);
981 for (unsigned i
= 0; i
< lop
.length (); ++i
)
982 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
]));
987 expr
*e
= dyn_cast
<expr
*> (o
);
988 if (!e
|| e
->ops
.length () == 0)
994 vec
< vec
<operand
*> > ops_vector
= vNULL
;
995 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
996 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
998 auto_vec
< vec
<operand
*> > result
;
999 auto_vec
<operand
*> v (e
->ops
.length ());
1000 v
.quick_grow_cleared (e
->ops
.length ());
1001 cartesian_product (ops_vector
, result
, v
, 0);
1003 for (unsigned i
= 0; i
< result
.length (); ++i
)
1005 expr
*ne
= new expr (e
);
1006 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1007 ne
->append_op (result
[i
][j
]);
1009 /* If this is a COND with a captured expression or an
1010 expression with two operands then also match a GENERIC
1011 form on the compare. */
1012 if ((*e
->operation
== COND_EXPR
1013 || *e
->operation
== VEC_COND_EXPR
)
1014 && ((is_a
<capture
*> (e
->ops
[0])
1015 && as_a
<capture
*> (e
->ops
[0])->what
1016 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1018 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1019 || (is_a
<expr
*> (e
->ops
[0])
1020 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1022 expr
*ne
= new expr (e
);
1023 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1024 ne
->append_op (result
[i
][j
]);
1025 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1027 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1028 expr
*cmp
= new expr (ocmp
);
1029 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1030 cmp
->append_op (ocmp
->ops
[j
]);
1031 cmp
->is_generic
= true;
1032 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
);
1036 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1037 expr
*cmp
= new expr (ocmp
);
1038 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1039 cmp
->append_op (ocmp
->ops
[j
]);
1040 cmp
->is_generic
= true;
1050 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1051 GENERIC and a GIMPLE variant. */
1054 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1056 vec
<operand
*> matchers
= lower_cond (s
->match
);
1057 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1059 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1060 s
->for_vec
, s
->capture_ids
);
1061 simplifiers
.safe_push (ns
);
1065 /* In AST operand O replace operator ID with operator WITH. */
1068 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1070 /* Deep-copy captures and expressions, replacing operations as
1072 if (capture
*c
= dyn_cast
<capture
*> (o
))
1076 return new capture (c
->location
, c
->where
,
1077 replace_id (c
->what
, id
, with
));
1079 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1081 expr
*ne
= new expr (e
);
1082 if (e
->operation
== id
)
1083 ne
->operation
= with
;
1084 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1085 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1088 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1090 with_expr
*nw
= new with_expr (w
->location
);
1091 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1092 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1095 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1097 if_expr
*nife
= new if_expr (ife
->location
);
1098 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1099 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1101 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1105 /* For c_expr we simply record a string replacement table which is
1106 applied at code-generation time. */
1107 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1109 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1110 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1111 return new c_expr (ce
->r
, ce
->location
,
1112 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1118 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1121 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1123 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1124 unsigned worklist_start
= 0;
1125 auto_vec
<simplify
*> worklist
;
1126 worklist
.safe_push (sin
);
1128 /* Lower each recorded for separately, operating on the
1129 set of simplifiers created by the previous one.
1130 Lower inner-to-outer so inner for substitutes can refer
1131 to operators replaced by outer fors. */
1132 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1134 vec
<user_id
*>& ids
= for_vec
[fi
];
1135 unsigned n_ids
= ids
.length ();
1136 unsigned max_n_opers
= 0;
1137 for (unsigned i
= 0; i
< n_ids
; ++i
)
1138 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1139 max_n_opers
= ids
[i
]->substitutes
.length ();
1141 unsigned worklist_end
= worklist
.length ();
1142 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1144 simplify
*s
= worklist
[si
];
1145 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1147 operand
*match_op
= s
->match
;
1148 operand
*result_op
= s
->result
;
1149 for (unsigned i
= 0; i
< n_ids
; ++i
)
1151 user_id
*id
= ids
[i
];
1152 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1153 match_op
= replace_id (match_op
, id
, oper
);
1155 result_op
= replace_id (result_op
, id
, oper
);
1157 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1158 vNULL
, s
->capture_ids
);
1159 worklist
.safe_push (ns
);
1162 worklist_start
= worklist_end
;
1165 /* Copy out the result from the last for lowering. */
1166 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1167 simplifiers
.safe_push (worklist
[i
]);
1170 /* Lower the AST for everything in SIMPLIFIERS. */
1173 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1175 auto_vec
<simplify
*> out_simplifiers
;
1176 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1177 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1179 simplifiers
.truncate (0);
1180 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1181 lower_commutative (out_simplifiers
[i
], simplifiers
);
1183 out_simplifiers
.truncate (0);
1185 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1186 lower_cond (simplifiers
[i
], out_simplifiers
);
1188 out_simplifiers
.safe_splice (simplifiers
);
1191 simplifiers
.truncate (0);
1192 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1193 lower_for (out_simplifiers
[i
], simplifiers
);
1199 /* The decision tree built for generating GIMPLE and GENERIC pattern
1200 matching code. It represents the 'match' expression of all
1201 simplifies and has those as its leafs. */
1203 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1207 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1211 vec
<dt_node
*> kids
;
1213 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1215 dt_node
*append_node (dt_node
*);
1216 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1217 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1218 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1219 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1221 virtual void gen (FILE *, int, bool) {}
1223 void gen_kids (FILE *, int, bool);
1224 void gen_kids_1 (FILE *, int, bool,
1225 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1226 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1229 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1231 struct dt_operand
: public dt_node
1234 dt_operand
*match_dop
;
1238 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1239 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1240 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1241 parent (parent_
), pos (pos_
) {}
1243 void gen (FILE *, int, bool);
1244 unsigned gen_predicate (FILE *, int, const char *, bool);
1245 unsigned gen_match_op (FILE *, int, const char *);
1247 unsigned gen_gimple_expr (FILE *, int);
1248 unsigned gen_generic_expr (FILE *, int, const char *);
1250 char *get_name (char *);
1251 void gen_opname (char *, unsigned);
1254 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1256 struct dt_simplify
: public dt_node
1259 unsigned pattern_no
;
1260 dt_operand
**indexes
;
1262 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1263 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1264 indexes (indexes_
) {}
1266 void gen_1 (FILE *, int, bool, operand
*);
1267 void gen (FILE *f
, int, bool);
1273 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1275 return (n
->type
== dt_node::DT_OPERAND
1276 || n
->type
== dt_node::DT_MATCH
);
1279 /* A container for the actual decision tree. */
1281 struct decision_tree
1285 void insert (struct simplify
*, unsigned);
1286 void gen_gimple (FILE *f
= stderr
);
1287 void gen_generic (FILE *f
= stderr
);
1288 void print (FILE *f
= stderr
);
1290 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1292 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1293 unsigned pos
= 0, dt_node
*parent
= 0);
1294 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1295 static bool cmp_node (dt_node
*, dt_node
*);
1296 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1299 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1302 cmp_operand (operand
*o1
, operand
*o2
)
1304 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1307 if (o1
->type
== operand::OP_PREDICATE
)
1309 predicate
*p1
= as_a
<predicate
*>(o1
);
1310 predicate
*p2
= as_a
<predicate
*>(o2
);
1311 return p1
->p
== p2
->p
;
1313 else if (o1
->type
== operand::OP_EXPR
)
1315 expr
*e1
= static_cast<expr
*>(o1
);
1316 expr
*e2
= static_cast<expr
*>(o2
);
1317 return (e1
->operation
== e2
->operation
1318 && e1
->is_generic
== e2
->is_generic
);
1324 /* Compare two decision tree nodes N1 and N2 and return true if they
1328 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1330 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1336 if (n1
->type
== dt_node::DT_TRUE
)
1339 if (n1
->type
== dt_node::DT_OPERAND
)
1340 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1341 (as_a
<dt_operand
*> (n2
))->op
);
1342 else if (n1
->type
== dt_node::DT_MATCH
)
1343 return ((as_a
<dt_operand
*> (n1
))->match_dop
1344 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1348 /* Search OPS for a decision tree node like P and return it if found. */
1351 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1353 /* We can merge adjacent DT_TRUE. */
1354 if (p
->type
== dt_node::DT_TRUE
1356 && ops
.last ()->type
== dt_node::DT_TRUE
)
1358 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1360 /* But we can't merge across DT_TRUE nodes as they serve as
1361 pattern order barriers to make sure that patterns apply
1362 in order of appearance in case multiple matches are possible. */
1363 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1365 if (decision_tree::cmp_node (ops
[i
], p
))
1371 /* Append N to the decision tree if it there is not already an existing
1375 dt_node::append_node (dt_node
*n
)
1379 kid
= decision_tree::find_node (kids
, n
);
1384 n
->level
= this->level
+ 1;
1389 /* Append OP to the decision tree. */
1392 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1394 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1395 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1396 return append_node (n
);
1399 /* Append a DT_TRUE decision tree node. */
1402 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1404 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1405 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1406 return append_node (n
);
1409 /* Append a DT_MATCH decision tree node. */
1412 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1414 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1415 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1416 return append_node (n
);
1419 /* Append S to the decision tree. */
1422 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1423 dt_operand
**indexes
)
1425 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1426 return append_node (n
);
1429 /* Insert O into the decision tree and return the decision tree node found
1433 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1434 unsigned pos
, dt_node
*parent
)
1436 dt_node
*q
, *elm
= 0;
1438 if (capture
*c
= dyn_cast
<capture
*> (o
))
1440 unsigned capt_index
= c
->where
;
1442 if (indexes
[capt_index
] == 0)
1445 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1448 q
= elm
= p
->append_true_op (parent
, pos
);
1451 // get to the last capture
1452 for (operand
*what
= c
->what
;
1453 what
&& is_a
<capture
*> (what
);
1454 c
= as_a
<capture
*> (what
), what
= c
->what
)
1459 unsigned cc_index
= c
->where
;
1460 dt_operand
*match_op
= indexes
[cc_index
];
1462 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1463 elm
= decision_tree::find_node (p
->kids
, &temp
);
1467 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1468 elm
= decision_tree::find_node (p
->kids
, &temp
);
1473 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1474 elm
= decision_tree::find_node (p
->kids
, &temp
);
1478 gcc_assert (elm
->type
== dt_node::DT_TRUE
1479 || elm
->type
== dt_node::DT_OPERAND
1480 || elm
->type
== dt_node::DT_MATCH
);
1481 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1486 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1488 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1493 p
= p
->append_op (o
, parent
, pos
);
1496 if (expr
*e
= dyn_cast
<expr
*>(o
))
1498 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1499 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1505 /* Insert S into the decision tree. */
1508 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1510 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1511 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1512 p
->append_simplify (s
, pattern_no
, indexes
);
1515 /* Debug functions to dump the decision tree. */
1518 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1520 if (p
->type
== dt_node::DT_NODE
)
1521 fprintf (f
, "root");
1525 for (unsigned i
= 0; i
< indent
; i
++)
1528 if (p
->type
== dt_node::DT_OPERAND
)
1530 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1531 print_operand (dop
->op
, f
, true);
1533 else if (p
->type
== dt_node::DT_TRUE
)
1534 fprintf (f
, "true");
1535 else if (p
->type
== dt_node::DT_MATCH
)
1536 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1537 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1539 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1540 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1541 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1542 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1547 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1549 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1550 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1554 decision_tree::print (FILE *f
)
1556 return decision_tree::print_node (root
, f
);
1560 /* For GENERIC we have to take care of wrapping multiple-used
1561 expressions with side-effects in save_expr and preserve side-effects
1562 of expressions with omit_one_operand. Analyze captures in
1563 match, result and with expressions and perform early-outs
1564 on the outermost match expression operands for cases we cannot
1569 capture_info (simplify
*s
, operand
*);
1570 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1571 bool walk_result (operand
*o
, bool, operand
*);
1572 void walk_c_expr (c_expr
*);
1578 bool force_no_side_effects_p
;
1579 bool force_single_use
;
1580 bool cond_expr_cond_p
;
1581 unsigned long toplevel_msk
;
1582 int result_use_count
;
1585 auto_vec
<cinfo
> info
;
1586 unsigned long force_no_side_effects
;
1589 /* Analyze captures in S. */
1591 capture_info::capture_info (simplify
*s
, operand
*result
)
1594 if (s
->kind
== simplify::MATCH
)
1596 force_no_side_effects
= -1;
1600 force_no_side_effects
= 0;
1601 info
.safe_grow_cleared (s
->capture_max
+ 1);
1602 e
= as_a
<expr
*> (s
->match
);
1603 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1604 walk_match (e
->ops
[i
], i
,
1605 (i
!= 0 && *e
->operation
== COND_EXPR
)
1606 || *e
->operation
== TRUTH_ANDIF_EXPR
1607 || *e
->operation
== TRUTH_ORIF_EXPR
,
1609 && (*e
->operation
== COND_EXPR
1610 || *e
->operation
== VEC_COND_EXPR
));
1612 walk_result (s
->result
, false, result
);
1615 /* Analyze captures in the match expression piece O. */
1618 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1619 bool conditional_p
, bool cond_expr_cond_p
)
1621 if (capture
*c
= dyn_cast
<capture
*> (o
))
1623 unsigned where
= c
->where
;
1624 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
1625 info
[where
].force_no_side_effects_p
|= conditional_p
;
1626 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1629 /* Recurse to exprs and captures. */
1630 if (is_a
<capture
*> (c
->what
)
1631 || is_a
<expr
*> (c
->what
))
1632 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1633 /* We need to look past multiple captures to find a captured
1634 expression as with conditional converts two captures
1635 can be collapsed onto the same expression. */
1636 while (c
->what
&& is_a
<capture
*> (c
->what
))
1637 c
= as_a
<capture
*> (c
->what
);
1638 /* Mark expr (non-leaf) captures and forced single-use exprs. */
1641 && (e
= dyn_cast
<expr
*> (c
->what
)))
1643 info
[where
].expr_p
= true;
1644 info
[where
].force_single_use
|= e
->force_single_use
;
1647 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1649 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1651 bool cond_p
= conditional_p
;
1652 bool cond_expr_cond_p
= false;
1653 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1655 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1656 || *e
->operation
== TRUTH_ORIF_EXPR
)
1659 && (*e
->operation
== COND_EXPR
1660 || *e
->operation
== VEC_COND_EXPR
))
1661 cond_expr_cond_p
= true;
1662 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1665 else if (is_a
<predicate
*> (o
))
1667 /* Mark non-captured leafs toplevel arg for checking. */
1668 force_no_side_effects
|= 1 << toplevel_arg
;
1674 /* Analyze captures in the result expression piece O. Return true
1675 if RESULT was visited in one of the children. Only visit
1676 non-if/with children if they are rooted on RESULT. */
1679 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
1681 if (capture
*c
= dyn_cast
<capture
*> (o
))
1683 info
[c
->where
].result_use_count
++;
1684 /* If we substitute an expression capture we don't know
1685 which captures this will end up using (well, we don't
1686 compute that). Force the uses to be side-effect free
1687 which means forcing the toplevels that reach the
1688 expression side-effect free. */
1689 if (info
[c
->where
].expr_p
)
1690 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1691 /* Mark CSE capture uses as forced to have no side-effects. */
1693 && is_a
<expr
*> (c
->what
))
1695 info
[c
->where
].cse_p
= true;
1696 walk_result (c
->what
, true, result
);
1699 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1701 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1703 bool cond_p
= conditional_p
;
1704 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1706 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1707 || *e
->operation
== TRUTH_ORIF_EXPR
)
1709 walk_result (e
->ops
[i
], cond_p
, result
);
1712 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
1714 /* 'if' conditions should be all fine. */
1715 if (e
->trueexpr
== result
)
1717 walk_result (e
->trueexpr
, false, result
);
1720 if (e
->falseexpr
== result
)
1722 walk_result (e
->falseexpr
, false, result
);
1726 if (is_a
<if_expr
*> (e
->trueexpr
)
1727 || is_a
<with_expr
*> (e
->trueexpr
))
1728 res
|= walk_result (e
->trueexpr
, false, result
);
1730 && (is_a
<if_expr
*> (e
->falseexpr
)
1731 || is_a
<with_expr
*> (e
->falseexpr
)))
1732 res
|= walk_result (e
->falseexpr
, false, result
);
1735 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
1737 bool res
= (e
->subexpr
== result
);
1739 || is_a
<if_expr
*> (e
->subexpr
)
1740 || is_a
<with_expr
*> (e
->subexpr
))
1741 res
|= walk_result (e
->subexpr
, false, result
);
1743 walk_c_expr (e
->with
);
1746 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1754 /* Look for captures in the C expr E. */
1757 capture_info::walk_c_expr (c_expr
*e
)
1759 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1760 unsigned p_depth
= 0;
1761 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1763 const cpp_token
*t
= &e
->code
[i
];
1764 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1765 if (t
->type
== CPP_NAME
1766 && strcmp ((const char *)CPP_HASHNODE
1767 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1768 && n
->type
== CPP_OPEN_PAREN
)
1770 else if (t
->type
== CPP_CLOSE_PAREN
1773 else if (p_depth
== 0
1774 && t
->type
== CPP_ATSIGN
1775 && (n
->type
== CPP_NUMBER
1776 || n
->type
== CPP_NAME
)
1777 && !(n
->flags
& PREV_WHITE
))
1780 if (n
->type
== CPP_NUMBER
)
1781 id
= (const char *)n
->val
.str
.text
;
1783 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1784 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1790 /* Code generation off the decision tree and the refered AST nodes. */
1793 is_conversion (id_base
*op
)
1795 return (*op
== CONVERT_EXPR
1797 || *op
== FLOAT_EXPR
1798 || *op
== FIX_TRUNC_EXPR
1799 || *op
== VIEW_CONVERT_EXPR
);
1802 /* Get the type to be used for generating operands of OP from the
1806 get_operand_type (id_base
*op
, const char *in_type
,
1807 const char *expr_type
,
1808 const char *other_oprnd_type
)
1810 /* Generally operands whose type does not match the type of the
1811 expression generated need to know their types but match and
1812 thus can fall back to 'other_oprnd_type'. */
1813 if (is_conversion (op
))
1814 return other_oprnd_type
;
1815 else if (*op
== REALPART_EXPR
1816 || *op
== IMAGPART_EXPR
)
1817 return other_oprnd_type
;
1818 else if (is_a
<operator_id
*> (op
)
1819 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1820 return other_oprnd_type
;
1823 /* Otherwise all types should match - choose one in order of
1830 return other_oprnd_type
;
1834 /* Generate transform code for an expression. */
1837 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
1838 int depth
, const char *in_type
, capture_info
*cinfo
,
1839 dt_operand
**indexes
, bool)
1841 bool conversion_p
= is_conversion (operation
);
1842 const char *type
= expr_type
;
1845 /* If there was a type specification in the pattern use it. */
1847 else if (conversion_p
)
1848 /* For conversions we need to build the expression using the
1849 outer type passed in. */
1851 else if (*operation
== REALPART_EXPR
1852 || *operation
== IMAGPART_EXPR
)
1854 /* __real and __imag use the component type of its operand. */
1855 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1858 else if (is_a
<operator_id
*> (operation
)
1859 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1861 /* comparisons use boolean_type_node (or what gets in), but
1862 their operands need to figure out the types themselves. */
1863 sprintf (optype
, "boolean_type_node");
1866 else if (*operation
== COND_EXPR
1867 || *operation
== VEC_COND_EXPR
)
1869 /* Conditions are of the same type as their first alternative. */
1870 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1875 /* Other operations are of the same type as their first operand. */
1876 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1880 fatal_at (location
, "cannot determine type of operand");
1882 fprintf_indent (f
, indent
, "{\n");
1884 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
1886 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1887 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1890 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
1892 = get_operand_type (operation
, in_type
, expr_type
,
1893 i
== 0 ? NULL
: op0type
);
1894 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
1896 ((!(*operation
== COND_EXPR
)
1897 && !(*operation
== VEC_COND_EXPR
))
1902 if (*operation
== CONVERT_EXPR
)
1905 opr
= operation
->id
;
1909 if (*operation
== CONVERT_EXPR
)
1911 fprintf_indent (f
, indent
,
1912 "if (%s != TREE_TYPE (ops%d[0])\n",
1914 fprintf_indent (f
, indent
,
1915 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
1917 fprintf_indent (f
, indent
+ 2, "{\n");
1920 /* ??? Building a stmt can fail for various reasons here, seq being
1921 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1922 So if we fail here we should continue matching other patterns. */
1923 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr
);
1924 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
1925 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1926 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1927 i
== ops
.length () - 1 ? " };\n" : ", ");
1928 fprintf_indent (f
, indent
,
1929 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
1930 ops
.length (), type
);
1931 fprintf_indent (f
, indent
,
1932 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
1934 fprintf_indent (f
, indent
,
1935 "if (!res) return false;\n");
1936 if (*operation
== CONVERT_EXPR
)
1939 fprintf_indent (f
, indent
, " }\n");
1940 fprintf_indent (f
, indent
, "else\n");
1941 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
1946 if (*operation
== CONVERT_EXPR
)
1948 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
1952 if (operation
->kind
== id_base::CODE
)
1953 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
1954 ops
.length(), opr
, type
);
1956 fprintf_indent (f
, indent
, "res = build_call_expr_loc (loc, "
1957 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1958 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1959 fprintf (f
, ", ops%d[%u]", depth
, i
);
1960 fprintf (f
, ");\n");
1961 if (*operation
== CONVERT_EXPR
)
1964 fprintf_indent (f
, indent
, "else\n");
1965 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
1968 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
1970 fprintf_indent (f
, indent
, "}\n");
1973 /* Generate code for a c_expr which is either the expression inside
1974 an if statement or a sequence of statements which computes a
1975 result to be stored to DEST. */
1978 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
1979 bool, int, const char *, capture_info
*,
1980 dt_operand
**, bool)
1982 if (dest
&& nr_stmts
== 1)
1983 fprintf_indent (f
, indent
, "%s = ", dest
);
1985 unsigned stmt_nr
= 1;
1986 for (unsigned i
= 0; i
< code
.length (); ++i
)
1988 const cpp_token
*token
= &code
[i
];
1990 /* Replace captures for code-gen. */
1991 if (token
->type
== CPP_ATSIGN
)
1993 const cpp_token
*n
= &code
[i
+1];
1994 if ((n
->type
== CPP_NUMBER
1995 || n
->type
== CPP_NAME
)
1996 && !(n
->flags
& PREV_WHITE
))
1998 if (token
->flags
& PREV_WHITE
)
2001 if (n
->type
== CPP_NUMBER
)
2002 id
= (const char *)n
->val
.str
.text
;
2004 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2005 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
2011 if (token
->flags
& PREV_WHITE
)
2014 if (token
->type
== CPP_NAME
)
2016 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2018 for (j
= 0; j
< ids
.length (); ++j
)
2020 if (strcmp (id
, ids
[j
].id
) == 0)
2022 fprintf (f
, "%s", ids
[j
].oper
);
2026 if (j
< ids
.length ())
2030 /* Output the token as string. */
2031 char *tk
= (char *)cpp_token_as_text (r
, token
);
2034 if (token
->type
== CPP_SEMICOLON
)
2038 if (dest
&& stmt_nr
== nr_stmts
)
2039 fprintf_indent (f
, indent
, "%s = ", dest
);
2044 /* Generate transform code for a capture. */
2047 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2048 int depth
, const char *in_type
, capture_info
*cinfo
,
2049 dt_operand
**indexes
, bool expand_compares
)
2051 if (what
&& is_a
<expr
*> (what
))
2053 if (indexes
[where
] == 0)
2056 sprintf (buf
, "captures[%u]", where
);
2057 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2062 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2064 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2065 with substituting a capture of that.
2066 ??? Returning false here will also not allow any other patterns
2068 if (gimple
&& expand_compares
2069 && cinfo
->info
[where
].cond_expr_cond_p
)
2071 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2072 fprintf_indent (f
, indent
, " {\n");
2073 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2074 fprintf_indent (f
, indent
, " %s = gimple_build (seq, TREE_CODE (%s),"
2075 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2076 " TREE_OPERAND (%s, 1));\n",
2077 dest
, dest
, dest
, dest
, dest
);
2078 fprintf_indent (f
, indent
, " }\n");
2082 /* Return the name of the operand representing the decision tree node.
2083 Use NAME as space to generate it. */
2086 dt_operand::get_name (char *name
)
2089 sprintf (name
, "t");
2090 else if (parent
->level
== 1)
2091 sprintf (name
, "op%u", pos
);
2092 else if (parent
->type
== dt_node::DT_MATCH
)
2093 return parent
->get_name (name
);
2095 sprintf (name
, "o%u%u", parent
->level
, pos
);
2099 /* Fill NAME with the operand name at position POS. */
2102 dt_operand::gen_opname (char *name
, unsigned pos
)
2105 sprintf (name
, "op%u", pos
);
2107 sprintf (name
, "o%u%u", level
, pos
);
2110 /* Generate matching code for the decision tree operand which is
2114 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2116 predicate
*p
= as_a
<predicate
*> (op
);
2118 if (p
->p
->matchers
.exists ())
2120 /* If this is a predicate generated from a pattern mangle its
2121 name and pass on the valueize hook. */
2123 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2126 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2129 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2130 fprintf_indent (f
, indent
+ 2, "{\n");
2134 /* Generate matching code for the decision tree operand which is
2138 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
)
2140 char match_opname
[20];
2141 match_dop
->get_name (match_opname
);
2142 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2143 opname
, match_opname
, opname
, match_opname
);
2144 fprintf_indent (f
, indent
+ 2, "{\n");
2148 /* Generate GIMPLE matching code for the decision tree operand. */
2151 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2153 expr
*e
= static_cast<expr
*> (op
);
2154 id_base
*id
= e
->operation
;
2155 unsigned n_ops
= e
->ops
.length ();
2157 for (unsigned i
= 0; i
< n_ops
; ++i
)
2159 char child_opname
[20];
2160 gen_opname (child_opname
, i
);
2162 if (id
->kind
== id_base::CODE
)
2165 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2166 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2168 /* ??? If this is a memory operation we can't (and should not)
2169 match this. The only sensible operand types are
2170 SSA names and invariants. */
2171 fprintf_indent (f
, indent
,
2172 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
2174 fprintf_indent (f
, indent
,
2175 "if ((TREE_CODE (%s) == SSA_NAME\n",
2177 fprintf_indent (f
, indent
,
2178 " || is_gimple_min_invariant (%s))\n",
2180 fprintf_indent (f
, indent
,
2181 " && (%s = do_valueize (valueize, %s)))\n",
2182 child_opname
, child_opname
);
2183 fprintf_indent (f
, indent
,
2189 fprintf_indent (f
, indent
,
2190 "tree %s = gimple_assign_rhs%u (def_stmt);\n",
2191 child_opname
, i
+ 1);
2194 fprintf_indent (f
, indent
,
2195 "tree %s = gimple_call_arg (def_stmt, %u);\n",
2197 fprintf_indent (f
, indent
,
2198 "if ((%s = do_valueize (valueize, %s)))\n",
2199 child_opname
, child_opname
);
2200 fprintf_indent (f
, indent
, " {\n");
2203 /* While the toplevel operands are canonicalized by the caller
2204 after valueizing operands of sub-expressions we have to
2205 re-canonicalize operand order. */
2206 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2208 /* ??? We can't canonicalize tcc_comparison operands here
2209 because that requires changing the comparison code which
2210 we already matched... */
2211 if (commutative_tree_code (code
->code
)
2212 || commutative_ternary_tree_code (code
->code
))
2214 char child_opname0
[20], child_opname1
[20];
2215 gen_opname (child_opname0
, 0);
2216 gen_opname (child_opname1
, 1);
2217 fprintf_indent (f
, indent
,
2218 "if (tree_swap_operands_p (%s, %s, false))\n",
2219 child_opname0
, child_opname1
);
2220 fprintf_indent (f
, indent
,
2221 " std::swap (%s, %s);\n",
2222 child_opname0
, child_opname1
);
2229 /* Generate GENERIC matching code for the decision tree operand. */
2232 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2234 expr
*e
= static_cast<expr
*> (op
);
2235 unsigned n_ops
= e
->ops
.length ();
2237 for (unsigned i
= 0; i
< n_ops
; ++i
)
2239 char child_opname
[20];
2240 gen_opname (child_opname
, i
);
2242 if (e
->operation
->kind
== id_base::CODE
)
2243 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2244 child_opname
, opname
, i
);
2246 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2247 child_opname
, opname
, i
);
2253 /* Generate matching code for the children of the decision tree node. */
2256 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2258 auto_vec
<dt_operand
*> gimple_exprs
;
2259 auto_vec
<dt_operand
*> generic_exprs
;
2260 auto_vec
<dt_operand
*> fns
;
2261 auto_vec
<dt_operand
*> generic_fns
;
2262 auto_vec
<dt_operand
*> preds
;
2263 auto_vec
<dt_node
*> others
;
2265 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2267 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2269 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2270 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2272 if (e
->ops
.length () == 0
2273 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2274 generic_exprs
.safe_push (op
);
2275 else if (e
->operation
->kind
== id_base::FN
)
2280 generic_fns
.safe_push (op
);
2282 else if (e
->operation
->kind
== id_base::PREDICATE
)
2283 preds
.safe_push (op
);
2287 gimple_exprs
.safe_push (op
);
2289 generic_exprs
.safe_push (op
);
2292 else if (op
->op
->type
== operand::OP_PREDICATE
)
2293 others
.safe_push (kids
[i
]);
2297 else if (kids
[i
]->type
== dt_node::DT_MATCH
2298 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2299 others
.safe_push (kids
[i
]);
2300 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2302 /* A DT_TRUE operand serves as a barrier - generate code now
2303 for what we have collected sofar. */
2304 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2305 fns
, generic_fns
, preds
, others
);
2306 /* And output the true operand itself. */
2307 kids
[i
]->gen (f
, indent
, gimple
);
2308 gimple_exprs
.truncate (0);
2309 generic_exprs
.truncate (0);
2311 generic_fns
.truncate (0);
2313 others
.truncate (0);
2319 /* Generate code for the remains. */
2320 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2321 fns
, generic_fns
, preds
, others
);
2324 /* Generate matching code for the children of the decision tree node. */
2327 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2328 vec
<dt_operand
*> gimple_exprs
,
2329 vec
<dt_operand
*> generic_exprs
,
2330 vec
<dt_operand
*> fns
,
2331 vec
<dt_operand
*> generic_fns
,
2332 vec
<dt_operand
*> preds
,
2333 vec
<dt_node
*> others
)
2336 char *kid_opname
= buf
;
2338 unsigned exprs_len
= gimple_exprs
.length ();
2339 unsigned gexprs_len
= generic_exprs
.length ();
2340 unsigned fns_len
= fns
.length ();
2341 unsigned gfns_len
= generic_fns
.length ();
2343 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2346 gimple_exprs
[0]->get_name (kid_opname
);
2348 fns
[0]->get_name (kid_opname
);
2350 generic_fns
[0]->get_name (kid_opname
);
2352 generic_exprs
[0]->get_name (kid_opname
);
2354 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2355 fprintf_indent (f
, indent
, " {\n");
2359 if (exprs_len
|| fns_len
)
2361 fprintf_indent (f
, indent
,
2362 "case SSA_NAME:\n");
2363 fprintf_indent (f
, indent
,
2364 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2366 fprintf_indent (f
, indent
,
2368 fprintf_indent (f
, indent
,
2369 " gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2375 fprintf_indent (f
, indent
,
2376 "if (is_gimple_assign (def_stmt))\n");
2377 fprintf_indent (f
, indent
,
2378 " switch (gimple_assign_rhs_code (def_stmt))\n");
2380 fprintf_indent (f
, indent
, "{\n");
2381 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2383 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2384 id_base
*op
= e
->operation
;
2385 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2386 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2388 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2389 fprintf_indent (f
, indent
, " {\n");
2390 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2391 fprintf_indent (f
, indent
, " break;\n");
2392 fprintf_indent (f
, indent
, " }\n");
2394 fprintf_indent (f
, indent
, "default:;\n");
2395 fprintf_indent (f
, indent
, "}\n");
2402 fprintf_indent (f
, indent
, "else ");
2404 fprintf_indent (f
, indent
, " ");
2406 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n");
2407 fprintf_indent (f
, indent
,
2409 fprintf_indent (f
, indent
,
2410 " tree fndecl = gimple_call_fndecl (def_stmt);\n");
2411 fprintf_indent (f
, indent
,
2412 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2413 fprintf_indent (f
, indent
,
2417 for (unsigned i
= 0; i
< fns_len
; ++i
)
2419 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2420 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2421 fprintf_indent (f
, indent
, " {\n");
2422 fns
[i
]->gen (f
, indent
+ 4, true);
2423 fprintf_indent (f
, indent
, " break;\n");
2424 fprintf_indent (f
, indent
, " }\n");
2427 fprintf_indent (f
, indent
, "default:;\n");
2428 fprintf_indent (f
, indent
, "}\n");
2430 fprintf_indent (f
, indent
, " }\n");
2434 fprintf_indent (f
, indent
, " }\n");
2435 fprintf_indent (f
, indent
, " break;\n");
2438 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2440 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2441 id_base
*op
= e
->operation
;
2442 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2443 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2445 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2446 fprintf_indent (f
, indent
, " {\n");
2447 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2448 fprintf_indent (f
, indent
, " break;\n");
2449 fprintf_indent (f
, indent
, " }\n");
2454 fprintf_indent (f
, indent
,
2455 "case CALL_EXPR:\n");
2456 fprintf_indent (f
, indent
,
2458 fprintf_indent (f
, indent
,
2459 " tree fndecl = get_callee_fndecl (%s);\n",
2461 fprintf_indent (f
, indent
,
2462 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2463 fprintf_indent (f
, indent
,
2464 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2465 fprintf_indent (f
, indent
,
2469 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2471 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2472 gcc_assert (e
->operation
->kind
== id_base::FN
);
2474 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2475 fprintf_indent (f
, indent
, " {\n");
2476 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2477 fprintf_indent (f
, indent
, " break;\n");
2478 fprintf_indent (f
, indent
, " }\n");
2482 fprintf_indent (f
, indent
, " default:;\n");
2483 fprintf_indent (f
, indent
, " }\n");
2484 fprintf_indent (f
, indent
, " break;\n");
2485 fprintf_indent (f
, indent
, " }\n");
2488 /* Close switch (TREE_CODE ()). */
2489 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2492 fprintf_indent (f
, indent
, " default:;\n");
2493 fprintf_indent (f
, indent
, " }\n");
2496 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2498 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2499 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2500 preds
[i
]->get_name (kid_opname
);
2501 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2502 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2503 gimple
? "gimple" : "tree",
2504 p
->id
, kid_opname
, kid_opname
,
2505 gimple
? ", valueize" : "");
2506 fprintf_indent (f
, indent
, " {\n");
2507 for (int j
= 0; j
< p
->nargs
; ++j
)
2509 char child_opname
[20];
2510 preds
[i
]->gen_opname (child_opname
, j
);
2511 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2512 child_opname
, kid_opname
, j
);
2514 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2518 for (unsigned i
= 0; i
< others
.length (); ++i
)
2519 others
[i
]->gen (f
, indent
, gimple
);
2522 /* Generate matching code for the decision tree operand. */
2525 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2530 unsigned n_braces
= 0;
2532 if (type
== DT_OPERAND
)
2535 case operand::OP_PREDICATE
:
2536 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2539 case operand::OP_EXPR
:
2541 n_braces
= gen_gimple_expr (f
, indent
);
2543 n_braces
= gen_generic_expr (f
, indent
, opname
);
2549 else if (type
== DT_TRUE
)
2551 else if (type
== DT_MATCH
)
2552 n_braces
= gen_match_op (f
, indent
, opname
);
2556 indent
+= 4 * n_braces
;
2557 gen_kids (f
, indent
, gimple
);
2559 for (unsigned i
= 0; i
< n_braces
; ++i
)
2564 fprintf_indent (f
, indent
, " }\n");
2569 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2570 step of a '(simplify ...)' or '(match ...)'. This handles everything
2571 that is not part of the decision tree (simplify->match).
2572 Main recursive worker. */
2575 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2579 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2581 fprintf_indent (f
, indent
, "{\n");
2583 output_line_directive (f
, w
->location
);
2584 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2585 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2587 fprintf_indent (f
, indent
, "}\n");
2590 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2592 output_line_directive (f
, ife
->location
);
2593 fprintf_indent (f
, indent
, "if (");
2594 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2596 fprintf_indent (f
, indent
+ 2, "{\n");
2598 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2600 fprintf_indent (f
, indent
+ 2, "}\n");
2603 fprintf_indent (f
, indent
, "else\n");
2604 fprintf_indent (f
, indent
+ 2, "{\n");
2606 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2608 fprintf_indent (f
, indent
+ 2, "}\n");
2614 /* Analyze captures and perform early-outs on the incoming arguments
2615 that cover cases we cannot handle. */
2616 capture_info
cinfo (s
, result
);
2617 if (s
->kind
== simplify::SIMPLIFY
)
2621 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2622 if (cinfo
.force_no_side_effects
& (1 << i
))
2623 fprintf_indent (f
, indent
,
2624 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2626 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2627 if (cinfo
.info
[i
].cse_p
)
2629 else if (cinfo
.info
[i
].force_no_side_effects_p
2630 && (cinfo
.info
[i
].toplevel_msk
2631 & cinfo
.force_no_side_effects
) == 0)
2632 fprintf_indent (f
, indent
,
2633 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2634 "return NULL_TREE;\n", i
);
2635 else if ((cinfo
.info
[i
].toplevel_msk
2636 & cinfo
.force_no_side_effects
) != 0)
2637 /* Mark capture as having no side-effects if we had to verify
2638 that via forced toplevel operand checks. */
2639 cinfo
.info
[i
].force_no_side_effects_p
= true;
2643 /* Force single-use restriction by only allowing simple
2644 results via setting seq to NULL. */
2645 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2646 bool first_p
= true;
2647 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2648 if (cinfo
.info
[i
].force_single_use
)
2652 fprintf_indent (f
, indent
, "if (lseq\n");
2653 fprintf_indent (f
, indent
, " && (");
2659 fprintf_indent (f
, indent
, " || ");
2661 fprintf (f
, "!single_use (captures[%d])", i
);
2665 fprintf (f
, "))\n");
2666 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2671 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2672 "fprintf (dump_file, \"Applying pattern ");
2673 output_line_directive (f
,
2674 result
? result
->location
: s
->match
->location
, true);
2675 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2679 /* If there is no result then this is a predicate implementation. */
2680 fprintf_indent (f
, indent
, "return true;\n");
2684 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2685 in outermost position). */
2686 if (result
->type
== operand::OP_EXPR
2687 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2688 result
= as_a
<expr
*> (result
)->ops
[0];
2689 if (result
->type
== operand::OP_EXPR
)
2691 expr
*e
= as_a
<expr
*> (result
);
2692 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2694 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2695 *e
->operation
== CONVERT_EXPR
2696 ? "NOP_EXPR" : e
->operation
->id
);
2697 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2700 snprintf (dest
, 32, "res_ops[%d]", j
);
2702 = get_operand_type (e
->operation
,
2703 "type", e
->expr_type
,
2704 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2705 /* We need to expand GENERIC conditions we captured from
2707 bool expand_generic_cond_exprs_p
2709 /* But avoid doing that if the GENERIC condition is
2710 valid - which it is in the first operand of COND_EXPRs
2711 and VEC_COND_EXRPs. */
2712 && ((!(*e
->operation
== COND_EXPR
)
2713 && !(*e
->operation
== VEC_COND_EXPR
))
2715 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
2717 indexes
, expand_generic_cond_exprs_p
);
2720 /* Re-fold the toplevel result. It's basically an embedded
2721 gimple_build w/o actually building the stmt. */
2723 fprintf_indent (f
, indent
,
2724 "gimple_resimplify%d (lseq, res_code, type, "
2725 "res_ops, valueize);\n", e
->ops
.length ());
2727 else if (result
->type
== operand::OP_CAPTURE
2728 || result
->type
== operand::OP_C_EXPR
)
2730 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
2731 &cinfo
, indexes
, false);
2732 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
2733 if (is_a
<capture
*> (result
)
2734 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2736 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2737 with substituting a capture of that. */
2738 fprintf_indent (f
, indent
,
2739 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2740 fprintf_indent (f
, indent
,
2742 fprintf_indent (f
, indent
,
2743 " tree tem = res_ops[0];\n");
2744 fprintf_indent (f
, indent
,
2745 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
2746 fprintf_indent (f
, indent
,
2747 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
2748 fprintf_indent (f
, indent
,
2754 fprintf_indent (f
, indent
, "return true;\n");
2758 bool is_predicate
= false;
2759 if (result
->type
== operand::OP_EXPR
)
2761 expr
*e
= as_a
<expr
*> (result
);
2762 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2763 /* Search for captures used multiple times in the result expression
2764 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2766 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2768 if (!cinfo
.info
[i
].force_no_side_effects_p
2769 && cinfo
.info
[i
].result_use_count
> 1)
2771 fprintf_indent (f
, indent
,
2772 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2774 fprintf_indent (f
, indent
,
2775 " captures[%d] = save_expr (captures[%d]);\n",
2779 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2783 snprintf (dest
, 32, "res_ops[%d]", j
);
2786 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
2787 snprintf (dest
, 32, "res_op%d", j
);
2790 = get_operand_type (e
->operation
,
2791 "type", e
->expr_type
,
2793 ? NULL
: "TREE_TYPE (res_op0)");
2794 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
2798 fprintf_indent (f
, indent
, "return true;\n");
2801 fprintf_indent (f
, indent
, "tree res;\n");
2802 /* Re-fold the toplevel result. Use non_lvalue to
2803 build NON_LVALUE_EXPRs so they get properly
2804 ignored when in GIMPLE form. */
2805 if (*e
->operation
== NON_LVALUE_EXPR
)
2806 fprintf_indent (f
, indent
,
2807 "res = non_lvalue_loc (loc, res_op0);\n");
2810 if (e
->operation
->kind
== id_base::CODE
)
2811 fprintf_indent (f
, indent
,
2812 "res = fold_build%d_loc (loc, %s, type",
2814 *e
->operation
== CONVERT_EXPR
2815 ? "NOP_EXPR" : e
->operation
->id
);
2817 fprintf_indent (f
, indent
,
2818 "res = build_call_expr_loc "
2819 "(loc, builtin_decl_implicit (%s), %d",
2820 e
->operation
->id
, e
->ops
.length());
2821 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2822 fprintf (f
, ", res_op%d", j
);
2823 fprintf (f
, ");\n");
2827 else if (result
->type
== operand::OP_CAPTURE
2828 || result
->type
== operand::OP_C_EXPR
)
2831 fprintf_indent (f
, indent
, "tree res;\n");
2832 result
->gen_transform (f
, indent
, "res", false, 1, "type",
2839 /* Search for captures not used in the result expression and dependent
2840 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2841 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2843 if (!cinfo
.info
[i
].force_no_side_effects_p
2844 && !cinfo
.info
[i
].expr_p
2845 && cinfo
.info
[i
].result_use_count
== 0)
2847 fprintf_indent (f
, indent
,
2848 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2850 fprintf_indent (f
, indent
+ 2,
2851 "res = build2_loc (loc, COMPOUND_EXPR, type, "
2852 "fold_ignored_result (captures[%d]), res);\n",
2856 fprintf_indent (f
, indent
, "return res;\n");
2861 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2862 step of a '(simplify ...)' or '(match ...)'. This handles everything
2863 that is not part of the decision tree (simplify->match). */
2866 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
2868 fprintf_indent (f
, indent
, "{\n");
2870 output_line_directive (f
,
2871 s
->result
? s
->result
->location
: s
->match
->location
);
2872 if (s
->capture_max
>= 0)
2873 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2874 s
->capture_max
+ 1);
2876 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2880 fprintf_indent (f
, indent
, "captures[%u] = %s;\n",
2881 i
, indexes
[i
]->get_name (opname
));
2884 gen_1 (f
, indent
, gimple
, s
->result
);
2887 fprintf_indent (f
, indent
, "}\n");
2890 /* Main entry to generate code for matching GIMPLE IL off the decision
2894 decision_tree::gen_gimple (FILE *f
)
2896 for (unsigned n
= 1; n
<= 3; ++n
)
2898 fprintf (f
, "\nstatic bool\n"
2899 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2900 " gimple_seq *seq, tree (*valueize)(tree),\n"
2901 " code_helper code, tree type");
2902 for (unsigned i
= 0; i
< n
; ++i
)
2903 fprintf (f
, ", tree op%d", i
);
2907 fprintf (f
, " switch (code.get_rep())\n"
2909 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2911 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2912 expr
*e
= static_cast<expr
*>(dop
->op
);
2913 if (e
->ops
.length () != n
)
2916 if (*e
->operation
== CONVERT_EXPR
2917 || *e
->operation
== NOP_EXPR
)
2918 fprintf (f
, " CASE_CONVERT:\n");
2920 fprintf (f
, " case %s%s:\n",
2921 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2923 fprintf (f
, " {\n");
2924 dop
->gen_kids (f
, 8, true);
2925 fprintf (f
, " break;\n");
2926 fprintf (f
, " }\n");
2928 fprintf (f
, " default:;\n"
2931 fprintf (f
, " return false;\n");
2936 /* Main entry to generate code for matching GENERIC IL off the decision
2940 decision_tree::gen_generic (FILE *f
)
2942 for (unsigned n
= 1; n
<= 3; ++n
)
2944 fprintf (f
, "\ntree\n"
2945 "generic_simplify (location_t loc, enum tree_code code, "
2946 "tree type ATTRIBUTE_UNUSED");
2947 for (unsigned i
= 0; i
< n
; ++i
)
2948 fprintf (f
, ", tree op%d", i
);
2952 fprintf (f
, " switch (code)\n"
2954 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2956 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2957 expr
*e
= static_cast<expr
*>(dop
->op
);
2958 if (e
->ops
.length () != n
2959 /* Builtin simplifications are somewhat premature on
2960 GENERIC. The following drops patterns with outermost
2961 calls. It's easy to emit overloads for function code
2962 though if necessary. */
2963 || e
->operation
->kind
!= id_base::CODE
)
2966 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2967 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2968 fprintf (f
, " CASE_CONVERT:\n");
2970 fprintf (f
, " case %s:\n", e
->operation
->id
);
2971 fprintf (f
, " {\n");
2972 dop
->gen_kids (f
, 8, false);
2973 fprintf (f
, " break;\n"
2976 fprintf (f
, " default:;\n"
2979 fprintf (f
, " return NULL_TREE;\n");
2984 /* Output code to implement the predicate P from the decision tree DT. */
2987 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2989 fprintf (f
, "\nbool\n"
2990 "%s%s (tree t%s%s)\n"
2991 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2992 p
->nargs
> 0 ? ", tree *res_ops" : "",
2993 gimple
? ", tree (*valueize)(tree)" : "");
2994 /* Conveniently make 'type' available. */
2995 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
2998 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2999 dt
.root
->gen_kids (f
, 2, gimple
);
3001 fprintf_indent (f
, 2, "return false;\n"
3005 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3008 write_header (FILE *f
, const char *head
)
3010 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3011 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3013 /* Include the header instead of writing it awkwardly quoted here. */
3014 fprintf (f
, "\n#include \"%s\"\n", head
);
3024 parser (cpp_reader
*);
3027 const cpp_token
*next ();
3028 const cpp_token
*peek (unsigned = 1);
3029 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3030 const cpp_token
*expect (enum cpp_ttype
);
3031 const cpp_token
*eat_token (enum cpp_ttype
);
3032 const char *get_string ();
3033 const char *get_ident ();
3034 const cpp_token
*eat_ident (const char *);
3035 const char *get_number ();
3037 id_base
*parse_operation ();
3038 operand
*parse_capture (operand
*);
3039 operand
*parse_expr ();
3040 c_expr
*parse_c_expr (cpp_ttype
);
3041 operand
*parse_op ();
3043 void record_operlist (source_location
, user_id
*);
3045 void parse_pattern ();
3046 operand
*parse_result (operand
*, predicate_id
*);
3047 void push_simplify (simplify::simplify_kind
,
3048 vec
<simplify
*>&, operand
*, operand
*);
3049 void parse_simplify (simplify::simplify_kind
,
3050 vec
<simplify
*>&, predicate_id
*, operand
*);
3051 void parse_for (source_location
);
3052 void parse_if (source_location
);
3053 void parse_predicates (source_location
);
3054 void parse_operator_list (source_location
);
3057 vec
<c_expr
*> active_ifs
;
3058 vec
<vec
<user_id
*> > active_fors
;
3059 hash_set
<user_id
*> *oper_lists_set
;
3060 vec
<user_id
*> oper_lists
;
3062 cid_map_t
*capture_ids
;
3065 vec
<simplify
*> simplifiers
;
3066 vec
<predicate_id
*> user_predicates
;
3067 bool parsing_match_operand
;
3070 /* Lexing helpers. */
3072 /* Read the next non-whitespace token from R. */
3077 const cpp_token
*token
;
3080 token
= cpp_get_token (r
);
3082 while (token
->type
== CPP_PADDING
3083 && token
->type
!= CPP_EOF
);
3087 /* Peek at the next non-whitespace token from R. */
3090 parser::peek (unsigned num
)
3092 const cpp_token
*token
;
3096 token
= cpp_peek_token (r
, i
++);
3098 while ((token
->type
== CPP_PADDING
3099 && token
->type
!= CPP_EOF
)
3101 /* If we peek at EOF this is a fatal error as it leaves the
3102 cpp_reader in unusable state. Assume we really wanted a
3103 token and thus this EOF is unexpected. */
3104 if (token
->type
== CPP_EOF
)
3105 fatal_at (token
, "unexpected end of file");
3109 /* Peek at the next identifier token (or return NULL if the next
3110 token is not an identifier or equal to ID if supplied). */
3113 parser::peek_ident (const char *id
, unsigned num
)
3115 const cpp_token
*token
= peek (num
);
3116 if (token
->type
!= CPP_NAME
)
3122 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3123 if (strcmp (id
, t
) == 0)
3129 /* Read the next token from R and assert it is of type TK. */
3132 parser::expect (enum cpp_ttype tk
)
3134 const cpp_token
*token
= next ();
3135 if (token
->type
!= tk
)
3136 fatal_at (token
, "expected %s, got %s",
3137 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3142 /* Consume the next token from R and assert it is of type TK. */
3145 parser::eat_token (enum cpp_ttype tk
)
3150 /* Read the next token from R and assert it is of type CPP_STRING and
3151 return its value. */
3154 parser::get_string ()
3156 const cpp_token
*token
= expect (CPP_STRING
);
3157 return (const char *)token
->val
.str
.text
;
3160 /* Read the next token from R and assert it is of type CPP_NAME and
3161 return its value. */
3164 parser::get_ident ()
3166 const cpp_token
*token
= expect (CPP_NAME
);
3167 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3170 /* Eat an identifier token with value S from R. */
3173 parser::eat_ident (const char *s
)
3175 const cpp_token
*token
= peek ();
3176 const char *t
= get_ident ();
3177 if (strcmp (s
, t
) != 0)
3178 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3182 /* Read the next token from R and assert it is of type CPP_NUMBER and
3183 return its value. */
3186 parser::get_number ()
3188 const cpp_token
*token
= expect (CPP_NUMBER
);
3189 return (const char *)token
->val
.str
.text
;
3193 /* Record an operator-list use for transparent for handling. */
3196 parser::record_operlist (source_location loc
, user_id
*p
)
3198 if (!oper_lists_set
->add (p
))
3200 if (!oper_lists
.is_empty ()
3201 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3202 fatal_at (loc
, "User-defined operator list does not have the "
3203 "same number of entries as others used in the pattern");
3204 oper_lists
.safe_push (p
);
3208 /* Parse the operator ID, special-casing convert?, convert1? and
3212 parser::parse_operation ()
3214 const cpp_token
*id_tok
= peek ();
3215 const char *id
= get_ident ();
3216 const cpp_token
*token
= peek ();
3217 if (strcmp (id
, "convert0") == 0)
3218 fatal_at (id_tok
, "use 'convert?' here");
3219 else if (strcmp (id
, "view_convert0") == 0)
3220 fatal_at (id_tok
, "use 'view_convert?' here");
3221 if (token
->type
== CPP_QUERY
3222 && !(token
->flags
& PREV_WHITE
))
3224 if (strcmp (id
, "convert") == 0)
3226 else if (strcmp (id
, "convert1") == 0)
3228 else if (strcmp (id
, "convert2") == 0)
3230 else if (strcmp (id
, "view_convert") == 0)
3231 id
= "view_convert0";
3232 else if (strcmp (id
, "view_convert1") == 0)
3234 else if (strcmp (id
, "view_convert2") == 0)
3237 fatal_at (id_tok
, "non-convert operator conditionalized");
3239 if (!parsing_match_operand
)
3240 fatal_at (id_tok
, "conditional convert can only be used in "
3241 "match expression");
3242 eat_token (CPP_QUERY
);
3244 else if (strcmp (id
, "convert1") == 0
3245 || strcmp (id
, "convert2") == 0
3246 || strcmp (id
, "view_convert1") == 0
3247 || strcmp (id
, "view_convert2") == 0)
3248 fatal_at (id_tok
, "expected '?' after conditional operator");
3249 id_base
*op
= get_operator (id
);
3251 fatal_at (id_tok
, "unknown operator %s", id
);
3253 user_id
*p
= dyn_cast
<user_id
*> (op
);
3254 if (p
&& p
->is_oper_list
)
3256 if (active_fors
.length() == 0)
3257 record_operlist (id_tok
->src_loc
, p
);
3259 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3265 capture = '@'<number> */
3268 parser::parse_capture (operand
*op
)
3270 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3271 const cpp_token
*token
= peek ();
3272 const char *id
= NULL
;
3273 if (token
->type
== CPP_NUMBER
)
3275 else if (token
->type
== CPP_NAME
)
3278 fatal_at (token
, "expected number or identifier");
3279 unsigned next_id
= capture_ids
->elements ();
3281 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3284 return new capture (src_loc
, num
, op
);
3287 /* Parse an expression
3288 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3291 parser::parse_expr ()
3293 const cpp_token
*token
= peek ();
3294 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3297 bool is_commutative
= false;
3298 bool force_capture
= false;
3299 const char *expr_type
= NULL
;
3301 if (token
->type
== CPP_COLON
3302 && !(token
->flags
& PREV_WHITE
))
3304 eat_token (CPP_COLON
);
3306 if (token
->type
== CPP_NAME
3307 && !(token
->flags
& PREV_WHITE
))
3309 const char *s
= get_ident ();
3310 if (!parsing_match_operand
)
3318 is_commutative
= true;
3319 else if (*sp
== 's')
3321 e
->force_single_use
= true;
3322 force_capture
= true;
3325 fatal_at (token
, "flag %c not recognized", *sp
);
3332 fatal_at (token
, "expected flag or type specifying identifier");
3335 if (token
->type
== CPP_ATSIGN
3336 && !(token
->flags
& PREV_WHITE
))
3337 op
= parse_capture (e
);
3338 else if (force_capture
)
3340 unsigned num
= capture_ids
->elements ();
3343 sprintf (id
, "__%u", num
);
3344 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3346 fatal_at (token
, "reserved capture id '%s' already used", id
);
3347 op
= new capture (token
->src_loc
, num
, e
);
3353 const cpp_token
*token
= peek ();
3354 if (token
->type
== CPP_CLOSE_PAREN
)
3356 if (e
->operation
->nargs
!= -1
3357 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3358 fatal_at (token
, "'%s' expects %u operands, not %u",
3359 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3362 if (e
->ops
.length () == 2)
3363 e
->is_commutative
= true;
3365 fatal_at (token
, "only binary operators or function with "
3366 "two arguments can be marked commutative");
3368 e
->expr_type
= expr_type
;
3371 e
->append_op (parse_op ());
3376 /* Lex native C code delimited by START recording the preprocessing tokens
3377 for later processing.
3378 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3381 parser::parse_c_expr (cpp_ttype start
)
3383 const cpp_token
*token
;
3386 vec
<cpp_token
> code
= vNULL
;
3387 unsigned nr_stmts
= 0;
3388 source_location loc
= eat_token (start
)->src_loc
;
3389 if (start
== CPP_OPEN_PAREN
)
3390 end
= CPP_CLOSE_PAREN
;
3391 else if (start
== CPP_OPEN_BRACE
)
3392 end
= CPP_CLOSE_BRACE
;
3400 /* Count brace pairs to find the end of the expr to match. */
3401 if (token
->type
== start
)
3403 else if (token
->type
== end
3407 /* This is a lame way of counting the number of statements. */
3408 if (token
->type
== CPP_SEMICOLON
)
3411 /* If this is possibly a user-defined identifier mark it used. */
3412 if (token
->type
== CPP_NAME
)
3414 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3415 (token
->val
.node
.node
)->ident
.str
);
3417 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3418 record_operlist (token
->src_loc
, p
);
3421 /* Record the token. */
3422 code
.safe_push (*token
);
3425 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3428 /* Parse an operand which is either an expression, a predicate or
3429 a standalone capture.
3430 op = predicate | expr | c_expr | capture */
3435 const cpp_token
*token
= peek ();
3436 struct operand
*op
= NULL
;
3437 if (token
->type
== CPP_OPEN_PAREN
)
3439 eat_token (CPP_OPEN_PAREN
);
3441 eat_token (CPP_CLOSE_PAREN
);
3443 else if (token
->type
== CPP_OPEN_BRACE
)
3445 op
= parse_c_expr (CPP_OPEN_BRACE
);
3449 /* Remaining ops are either empty or predicates */
3450 if (token
->type
== CPP_NAME
)
3452 const char *id
= get_ident ();
3453 id_base
*opr
= get_operator (id
);
3455 fatal_at (token
, "expected predicate name");
3456 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3458 if (code
->nargs
!= 0)
3459 fatal_at (token
, "using an operator with operands as predicate");
3460 /* Parse the zero-operand operator "predicates" as
3462 op
= new expr (opr
, token
->src_loc
);
3464 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3466 if (code
->nargs
!= 0)
3467 fatal_at (token
, "using an operator with operands as predicate");
3468 /* Parse the zero-operand operator "predicates" as
3470 op
= new expr (opr
, token
->src_loc
);
3472 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3473 op
= new predicate (p
, token
->src_loc
);
3475 fatal_at (token
, "using an unsupported operator as predicate");
3476 if (!parsing_match_operand
)
3477 fatal_at (token
, "predicates are only allowed in match expression");
3479 if (token
->flags
& PREV_WHITE
)
3482 else if (token
->type
!= CPP_COLON
3483 && token
->type
!= CPP_ATSIGN
)
3484 fatal_at (token
, "expected expression or predicate");
3485 /* optionally followed by a capture and a predicate. */
3486 if (token
->type
== CPP_COLON
)
3487 fatal_at (token
, "not implemented: predicate on leaf operand");
3488 if (token
->type
== CPP_ATSIGN
)
3489 op
= parse_capture (op
);
3495 /* Create a new simplify from the current parsing state and MATCH,
3496 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3499 parser::push_simplify (simplify::simplify_kind kind
,
3500 vec
<simplify
*>& simplifiers
,
3501 operand
*match
, operand
*result
)
3503 /* Build and push a temporary for operator list uses in expressions. */
3504 if (!oper_lists
.is_empty ())
3505 active_fors
.safe_push (oper_lists
);
3507 simplifiers
.safe_push
3508 (new simplify (kind
, match
, result
,
3509 active_fors
.copy (), capture_ids
));
3511 if (!oper_lists
.is_empty ())
3516 <result-op> = <op> | <if> | <with>
3517 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3518 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3522 parser::parse_result (operand
*result
, predicate_id
*matcher
)
3524 const cpp_token
*token
= peek ();
3525 if (token
->type
!= CPP_OPEN_PAREN
)
3528 eat_token (CPP_OPEN_PAREN
);
3529 if (peek_ident ("if"))
3532 if_expr
*ife
= new if_expr (token
->src_loc
);
3533 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3534 if (peek ()->type
== CPP_OPEN_PAREN
)
3536 ife
->trueexpr
= parse_result (result
, matcher
);
3537 if (peek ()->type
== CPP_OPEN_PAREN
)
3538 ife
->falseexpr
= parse_result (result
, matcher
);
3539 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3540 ife
->falseexpr
= parse_op ();
3542 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3544 ife
->trueexpr
= parse_op ();
3545 if (peek ()->type
== CPP_OPEN_PAREN
)
3546 ife
->falseexpr
= parse_result (result
, matcher
);
3547 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3548 ife
->falseexpr
= parse_op ();
3550 /* If this if is immediately closed then it contains a
3551 manual matcher or is part of a predicate definition. */
3552 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
3555 fatal_at (peek (), "manual transform not implemented");
3556 ife
->trueexpr
= result
;
3558 eat_token (CPP_CLOSE_PAREN
);
3561 else if (peek_ident ("with"))
3564 with_expr
*withe
= new with_expr (token
->src_loc
);
3565 /* Parse (with c-expr expr) as (if-with (true) expr). */
3566 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
3567 withe
->with
->nr_stmts
= 0;
3568 withe
->subexpr
= parse_result (result
, matcher
);
3569 eat_token (CPP_CLOSE_PAREN
);
3572 else if (peek_ident ("switch"))
3574 token
= eat_ident ("switch");
3575 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
3577 if_expr
*ife
= new if_expr (ifloc
);
3579 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3580 if (peek ()->type
== CPP_OPEN_PAREN
)
3581 ife
->trueexpr
= parse_result (result
, matcher
);
3583 ife
->trueexpr
= parse_op ();
3584 eat_token (CPP_CLOSE_PAREN
);
3585 if (peek ()->type
!= CPP_OPEN_PAREN
3586 || !peek_ident ("if", 2))
3587 fatal_at (token
, "switch can be implemented with a single if");
3588 while (peek ()->type
!= CPP_CLOSE_PAREN
)
3590 if (peek ()->type
== CPP_OPEN_PAREN
)
3592 if (peek_ident ("if", 2))
3594 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
3596 ife
->falseexpr
= new if_expr (ifloc
);
3597 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
3598 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3599 if (peek ()->type
== CPP_OPEN_PAREN
)
3600 ife
->trueexpr
= parse_result (result
, matcher
);
3602 ife
->trueexpr
= parse_op ();
3603 eat_token (CPP_CLOSE_PAREN
);
3607 /* switch default clause */
3608 ife
->falseexpr
= parse_result (result
, matcher
);
3609 eat_token (CPP_CLOSE_PAREN
);
3615 /* switch default clause */
3616 ife
->falseexpr
= parse_op ();
3617 eat_token (CPP_CLOSE_PAREN
);
3621 eat_token (CPP_CLOSE_PAREN
);
3626 operand
*op
= result
;
3629 eat_token (CPP_CLOSE_PAREN
);
3635 simplify = 'simplify' <expr> <result-op>
3637 match = 'match' <ident> <expr> [<result-op>]
3638 and fill SIMPLIFIERS with the results. */
3641 parser::parse_simplify (simplify::simplify_kind kind
,
3642 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3645 /* Reset the capture map. */
3647 capture_ids
= new cid_map_t
;
3648 /* Reset oper_lists and set. */
3649 hash_set
<user_id
*> olist
;
3650 oper_lists_set
= &olist
;
3653 const cpp_token
*loc
= peek ();
3654 parsing_match_operand
= true;
3655 struct operand
*match
= parse_op ();
3656 parsing_match_operand
= false;
3657 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3658 fatal_at (loc
, "outermost expression cannot be captured");
3659 if (match
->type
== operand::OP_EXPR
3660 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3661 fatal_at (loc
, "outermost expression cannot be a predicate");
3663 /* Splice active_ifs onto result and continue parsing the
3665 if_expr
*active_if
= NULL
;
3666 for (int i
= active_ifs
.length (); i
> 0; --i
)
3668 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
3669 ifc
->cond
= active_ifs
[i
-1];
3670 ifc
->trueexpr
= active_if
;
3673 if_expr
*outermost_if
= active_if
;
3674 while (active_if
&& active_if
->trueexpr
)
3675 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
3677 const cpp_token
*token
= peek ();
3679 /* If this if is immediately closed then it is part of a predicate
3680 definition. Push it. */
3681 if (token
->type
== CPP_CLOSE_PAREN
)
3684 fatal_at (token
, "expected transform expression");
3687 active_if
->trueexpr
= result
;
3688 result
= outermost_if
;
3690 push_simplify (kind
, simplifiers
, match
, result
);
3694 operand
*tem
= parse_result (result
, matcher
);
3697 active_if
->trueexpr
= tem
;
3698 result
= outermost_if
;
3703 push_simplify (kind
, simplifiers
, match
, result
);
3706 /* Parsing of the outer control structures. */
3708 /* Parse a for expression
3709 for = '(' 'for' <subst>... <pattern> ')'
3710 subst = <ident> '(' <ident>... ')' */
3713 parser::parse_for (source_location
)
3715 auto_vec
<const cpp_token
*> user_id_tokens
;
3716 vec
<user_id
*> user_ids
= vNULL
;
3717 const cpp_token
*token
;
3718 unsigned min_n_opers
= 0, max_n_opers
= 0;
3723 if (token
->type
!= CPP_NAME
)
3726 /* Insert the user defined operators into the operator hash. */
3727 const char *id
= get_ident ();
3728 if (get_operator (id
) != NULL
)
3729 fatal_at (token
, "operator already defined");
3730 user_id
*op
= new user_id (id
);
3731 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3733 user_ids
.safe_push (op
);
3734 user_id_tokens
.safe_push (token
);
3736 eat_token (CPP_OPEN_PAREN
);
3739 while ((token
= peek_ident ()) != 0)
3741 const char *oper
= get_ident ();
3742 id_base
*idb
= get_operator (oper
);
3744 fatal_at (token
, "no such operator '%s'", oper
);
3745 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3746 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3747 || *idb
== VIEW_CONVERT2
)
3748 fatal_at (token
, "conditional operators cannot be used inside for");
3752 else if (idb
->nargs
== -1)
3754 else if (idb
->nargs
!= arity
)
3755 fatal_at (token
, "operator '%s' with arity %d does not match "
3756 "others with arity %d", oper
, idb
->nargs
, arity
);
3758 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3761 if (p
->is_oper_list
)
3762 op
->substitutes
.safe_splice (p
->substitutes
);
3764 fatal_at (token
, "iterator cannot be used as operator-list");
3767 op
->substitutes
.safe_push (idb
);
3770 token
= expect (CPP_CLOSE_PAREN
);
3772 unsigned nsubstitutes
= op
->substitutes
.length ();
3773 if (nsubstitutes
== 0)
3774 fatal_at (token
, "A user-defined operator must have at least "
3775 "one substitution");
3776 if (max_n_opers
== 0)
3778 min_n_opers
= nsubstitutes
;
3779 max_n_opers
= nsubstitutes
;
3783 if (nsubstitutes
% min_n_opers
!= 0
3784 && min_n_opers
% nsubstitutes
!= 0)
3785 fatal_at (token
, "All user-defined identifiers must have a "
3786 "multiple number of operator substitutions of the "
3787 "smallest number of substitutions");
3788 if (nsubstitutes
< min_n_opers
)
3789 min_n_opers
= nsubstitutes
;
3790 else if (nsubstitutes
> max_n_opers
)
3791 max_n_opers
= nsubstitutes
;
3795 unsigned n_ids
= user_ids
.length ();
3797 fatal_at (token
, "for requires at least one user-defined identifier");
3800 if (token
->type
== CPP_CLOSE_PAREN
)
3801 fatal_at (token
, "no pattern defined in for");
3803 active_fors
.safe_push (user_ids
);
3807 if (token
->type
== CPP_CLOSE_PAREN
)
3813 /* Remove user-defined operators from the hash again. */
3814 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3816 if (!user_ids
[i
]->used
)
3817 warning_at (user_id_tokens
[i
],
3818 "operator %s defined but not used", user_ids
[i
]->id
);
3819 operators
->remove_elt (user_ids
[i
]);
3823 /* Parse an identifier associated with a list of operators.
3824 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3827 parser::parse_operator_list (source_location
)
3829 const cpp_token
*token
= peek ();
3830 const char *id
= get_ident ();
3832 if (get_operator (id
) != 0)
3833 fatal_at (token
, "operator %s already defined", id
);
3835 user_id
*op
= new user_id (id
, true);
3838 while ((token
= peek_ident ()) != 0)
3841 const char *oper
= get_ident ();
3842 id_base
*idb
= get_operator (oper
);
3845 fatal_at (token
, "no such operator '%s'", oper
);
3849 else if (idb
->nargs
== -1)
3851 else if (arity
!= idb
->nargs
)
3852 fatal_at (token
, "operator '%s' with arity %d does not match "
3853 "others with arity %d", oper
, idb
->nargs
, arity
);
3855 /* We allow composition of multiple operator lists. */
3856 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3857 op
->substitutes
.safe_splice (p
->substitutes
);
3859 op
->substitutes
.safe_push (idb
);
3862 // Check that there is no junk after id-list
3864 if (token
->type
!= CPP_CLOSE_PAREN
)
3865 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3867 if (op
->substitutes
.length () == 0)
3868 fatal_at (token
, "operator-list cannot be empty");
3871 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3875 /* Parse an outer if expression.
3876 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3879 parser::parse_if (source_location
)
3881 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3883 const cpp_token
*token
= peek ();
3884 if (token
->type
== CPP_CLOSE_PAREN
)
3885 fatal_at (token
, "no pattern defined in if");
3887 active_ifs
.safe_push (ifexpr
);
3890 const cpp_token
*token
= peek ();
3891 if (token
->type
== CPP_CLOSE_PAREN
)
3899 /* Parse a list of predefined predicate identifiers.
3900 preds = '(' 'define_predicates' <ident>... ')' */
3903 parser::parse_predicates (source_location
)
3907 const cpp_token
*token
= peek ();
3908 if (token
->type
!= CPP_NAME
)
3911 add_predicate (get_ident ());
3916 /* Parse outer control structures.
3917 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3920 parser::parse_pattern ()
3922 /* All clauses start with '('. */
3923 eat_token (CPP_OPEN_PAREN
);
3924 const cpp_token
*token
= peek ();
3925 const char *id
= get_ident ();
3926 if (strcmp (id
, "simplify") == 0)
3928 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
3931 else if (strcmp (id
, "match") == 0)
3933 bool with_args
= false;
3934 source_location e_loc
= peek ()->src_loc
;
3935 if (peek ()->type
== CPP_OPEN_PAREN
)
3937 eat_token (CPP_OPEN_PAREN
);
3940 const char *name
= get_ident ();
3941 id_base
*id
= get_operator (name
);
3945 p
= add_predicate (name
);
3946 user_predicates
.safe_push (p
);
3948 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3951 fatal_at (token
, "cannot add a match to a non-predicate ID");
3952 /* Parse (match <id> <arg>... (match-expr)) here. */
3956 capture_ids
= new cid_map_t
;
3957 e
= new expr (p
, e_loc
);
3958 while (peek ()->type
== CPP_ATSIGN
)
3959 e
->append_op (parse_capture (NULL
));
3960 eat_token (CPP_CLOSE_PAREN
);
3963 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3964 || (!e
&& p
->nargs
!= 0)))
3965 fatal_at (token
, "non-matching number of match operands");
3966 p
->nargs
= e
? e
->ops
.length () : 0;
3967 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
3970 else if (strcmp (id
, "for") == 0)
3971 parse_for (token
->src_loc
);
3972 else if (strcmp (id
, "if") == 0)
3973 parse_if (token
->src_loc
);
3974 else if (strcmp (id
, "define_predicates") == 0)
3976 if (active_ifs
.length () > 0
3977 || active_fors
.length () > 0)
3978 fatal_at (token
, "define_predicates inside if or for is not supported");
3979 parse_predicates (token
->src_loc
);
3981 else if (strcmp (id
, "define_operator_list") == 0)
3983 if (active_ifs
.length () > 0
3984 || active_fors
.length () > 0)
3985 fatal_at (token
, "operator-list inside if or for is not supported");
3986 parse_operator_list (token
->src_loc
);
3989 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3990 active_ifs
.length () == 0 && active_fors
.length () == 0
3991 ? "'define_predicates', " : "");
3993 eat_token (CPP_CLOSE_PAREN
);
3996 /* Main entry of the parser. Repeatedly parse outer control structures. */
3998 parser::parser (cpp_reader
*r_
)
4002 active_fors
= vNULL
;
4003 simplifiers
= vNULL
;
4004 oper_lists_set
= NULL
;
4007 user_predicates
= vNULL
;
4008 parsing_match_operand
= false;
4010 const cpp_token
*token
= next ();
4011 while (token
->type
!= CPP_EOF
)
4013 _cpp_backup_tokens (r
, 1);
4020 /* Helper for the linemap code. */
4023 round_alloc_size (size_t s
)
4029 /* The genmatch generator progam. It reads from a pattern description
4030 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4033 main (int argc
, char **argv
)
4037 progname
= "genmatch";
4043 bool verbose
= false;
4044 char *input
= argv
[argc
-1];
4045 for (int i
= 1; i
< argc
- 1; ++i
)
4047 if (strcmp (argv
[i
], "--gimple") == 0)
4049 else if (strcmp (argv
[i
], "--generic") == 0)
4051 else if (strcmp (argv
[i
], "-v") == 0)
4055 fprintf (stderr
, "Usage: genmatch "
4056 "[--gimple] [--generic] [-v] input\n");
4061 line_table
= XCNEW (struct line_maps
);
4062 linemap_init (line_table
, 0);
4063 line_table
->reallocator
= xrealloc
;
4064 line_table
->round_alloc_size
= round_alloc_size
;
4066 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4067 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4068 cb
->error
= error_cb
;
4070 if (!cpp_read_main_file (r
, input
))
4072 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4073 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4075 /* Pre-seed operators. */
4076 operators
= new hash_table
<id_base
> (1024);
4077 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4078 add_operator (SYM, # SYM, # TYPE, NARGS);
4079 #define END_OF_BASE_TREE_CODES
4081 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4082 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4083 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4084 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4085 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4086 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4087 #undef END_OF_BASE_TREE_CODES
4090 /* Pre-seed builtin functions.
4091 ??? Cannot use N (name) as that is targetm.emultls.get_address
4092 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4093 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4094 add_builtin (ENUM, # ENUM);
4095 #include "builtins.def"
4102 write_header (stdout
, "gimple-match-head.c");
4104 write_header (stdout
, "generic-match-head.c");
4106 /* Go over all predicates defined with patterns and perform
4107 lowering and code generation. */
4108 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4110 predicate_id
*pred
= p
.user_predicates
[i
];
4111 lower (pred
->matchers
, gimple
);
4114 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4115 print_matches (pred
->matchers
[i
]);
4118 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4119 dt
.insert (pred
->matchers
[i
], i
);
4124 write_predicate (stdout
, pred
, dt
, gimple
);
4127 /* Lower the main simplifiers and generate code for them. */
4128 lower (p
.simplifiers
, gimple
);
4131 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4132 print_matches (p
.simplifiers
[i
]);
4135 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4136 dt
.insert (p
.simplifiers
[i
], i
);
4142 dt
.gen_gimple (stdout
);
4144 dt
.gen_generic (stdout
);
4147 cpp_finish (r
, NULL
);