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
)
399 /* Allow SSA_NAME as predicate operator. */
400 && !(code
== SSA_NAME
))
402 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
403 if (code
== ADDR_EXPR
)
405 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
406 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
408 fatal ("duplicate id definition");
412 /* Add a builtin identifier to the hash. */
415 add_builtin (enum built_in_function code
, const char *id
)
417 fn_id
*fn
= new fn_id (code
, id
);
418 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
420 fatal ("duplicate id definition");
424 /* Helper for easy comparing ID with tree code CODE. */
427 operator==(id_base
&id
, enum tree_code code
)
429 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
430 return oid
->code
== code
;
434 /* Lookup the identifier ID. */
437 get_operator (const char *id
)
439 id_base
tem (id_base::CODE
, id
);
441 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
444 /* If this is a user-defined identifier track whether it was used. */
445 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
450 /* Try all-uppercase. */
451 char *id2
= xstrdup (id
);
452 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
453 id2
[i
] = TOUPPER (id2
[i
]);
454 new (&tem
) id_base (id_base::CODE
, id2
);
455 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
462 /* Try _EXPR appended. */
463 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
464 strcat (id2
, "_EXPR");
465 new (&tem
) id_base (id_base::CODE
, id2
);
466 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
476 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
479 /* The AST produced by parsing of the pattern definitions. */
484 /* The base class for operands. */
487 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
488 operand (enum op_type type_
, source_location loc_
)
489 : type (type_
), location (loc_
) {}
491 source_location location
;
492 virtual void gen_transform (FILE *, int, const char *, bool, int,
493 const char *, capture_info
*,
496 { gcc_unreachable (); }
499 /* A predicate operand. Predicates are leafs in the AST. */
501 struct predicate
: public operand
503 predicate (predicate_id
*p_
, source_location loc
)
504 : operand (OP_PREDICATE
, loc
), p (p_
) {}
508 /* An operand that constitutes an expression. Expressions include
509 function calls and user-defined predicate invocations. */
511 struct expr
: public operand
513 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
514 : operand (OP_EXPR
, loc
), operation (operation_
),
515 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
516 is_generic (false), force_single_use (false) {}
518 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
519 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
520 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
521 void append_op (operand
*op
) { ops
.safe_push (op
); }
522 /* The operator and its operands. */
525 /* An explicitely specified type - used exclusively for conversions. */
526 const char *expr_type
;
527 /* Whether the operation is to be applied commutatively. This is
528 later lowered to two separate patterns. */
530 /* Whether the expression is expected to be in GENERIC form. */
532 /* Whether pushing any stmt to the sequence should be conditional
533 on this expression having a single-use. */
534 bool force_single_use
;
535 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
536 const char *, capture_info
*,
537 dt_operand
** = 0, bool = true);
540 /* An operator that is represented by native C code. This is always
541 a leaf operand in the AST. This class is also used to represent
542 the code to be generated for 'if' and 'with' expressions. */
544 struct c_expr
: public operand
546 /* A mapping of an identifier and its replacement. Used to apply
551 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
554 c_expr (cpp_reader
*r_
, source_location loc
,
555 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
556 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
557 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
558 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
559 /* cpplib tokens and state to transform this back to source. */
562 cid_map_t
*capture_ids
;
563 /* The number of statements parsed (well, the number of ';'s). */
565 /* The identifier replacement vector. */
567 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
568 const char *, capture_info
*,
569 dt_operand
** = 0, bool = true);
572 /* A wrapper around another operand that captures its value. */
574 struct capture
: public operand
576 capture (source_location loc
, unsigned where_
, operand
*what_
)
577 : operand (OP_CAPTURE
, loc
), where (where_
), what (what_
) {}
578 /* Identifier index for the value. */
580 /* The captured value. */
582 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
583 const char *, capture_info
*,
584 dt_operand
** = 0, bool = true);
589 struct if_expr
: public operand
591 if_expr (source_location loc
)
592 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
598 /* with expression. */
600 struct with_expr
: public operand
602 with_expr (source_location loc
)
603 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
611 is_a_helper
<capture
*>::test (operand
*op
)
613 return op
->type
== operand::OP_CAPTURE
;
619 is_a_helper
<predicate
*>::test (operand
*op
)
621 return op
->type
== operand::OP_PREDICATE
;
627 is_a_helper
<c_expr
*>::test (operand
*op
)
629 return op
->type
== operand::OP_C_EXPR
;
635 is_a_helper
<expr
*>::test (operand
*op
)
637 return op
->type
== operand::OP_EXPR
;
643 is_a_helper
<if_expr
*>::test (operand
*op
)
645 return op
->type
== operand::OP_IF
;
651 is_a_helper
<with_expr
*>::test (operand
*op
)
653 return op
->type
== operand::OP_WITH
;
656 /* The main class of a pattern and its transform. This is used to
657 represent both (simplify ...) and (match ...) kinds. The AST
658 duplicates all outer 'if' and 'for' expressions here so each
659 simplify can exist in isolation. */
663 enum simplify_kind
{ SIMPLIFY
, MATCH
};
665 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
666 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
667 : kind (kind_
), match (match_
), result (result_
),
669 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
672 /* The expression that is matched against the GENERIC or GIMPLE IL. */
674 /* For a (simplify ...) an expression with ifs and withs with the expression
675 produced when the pattern applies in the leafs.
676 For a (match ...) the leafs are either empty if it is a simple predicate
677 or the single expression specifying the matched operands. */
678 struct operand
*result
;
679 /* Collected 'for' expression operators that have to be replaced
680 in the lowering phase. */
681 vec
<vec
<user_id
*> > for_vec
;
682 /* A map of capture identifiers to indexes. */
683 cid_map_t
*capture_ids
;
687 /* Debugging routines for dumping the AST. */
690 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
692 if (capture
*c
= dyn_cast
<capture
*> (o
))
694 fprintf (f
, "@%u", c
->where
);
695 if (c
->what
&& flattened
== false)
698 print_operand (c
->what
, f
, flattened
);
703 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
704 fprintf (f
, "%s", p
->p
->id
);
706 else if (is_a
<c_expr
*> (o
))
707 fprintf (f
, "c_expr");
709 else if (expr
*e
= dyn_cast
<expr
*> (o
))
711 fprintf (f
, "(%s", e
->operation
->id
);
713 if (flattened
== false)
716 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
718 print_operand (e
->ops
[i
], f
, flattened
);
730 print_matches (struct simplify
*s
, FILE *f
= stderr
)
732 fprintf (f
, "for expression: ");
733 print_operand (s
->match
, f
);
740 /* Lowering of commutative operators. */
743 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
744 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
746 if (n
== ops_vector
.length ())
748 vec
<operand
*> xv
= v
.copy ();
749 result
.safe_push (xv
);
753 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
755 v
[n
] = ops_vector
[n
][i
];
756 cartesian_product (ops_vector
, result
, v
, n
+ 1);
760 /* Lower OP to two operands in case it is marked as commutative. */
762 static vec
<operand
*>
763 commutate (operand
*op
)
765 vec
<operand
*> ret
= vNULL
;
767 if (capture
*c
= dyn_cast
<capture
*> (op
))
774 vec
<operand
*> v
= commutate (c
->what
);
775 for (unsigned i
= 0; i
< v
.length (); ++i
)
777 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
]);
783 expr
*e
= dyn_cast
<expr
*> (op
);
784 if (!e
|| e
->ops
.length () == 0)
790 vec
< vec
<operand
*> > ops_vector
= vNULL
;
791 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
792 ops_vector
.safe_push (commutate (e
->ops
[i
]));
794 auto_vec
< vec
<operand
*> > result
;
795 auto_vec
<operand
*> v (e
->ops
.length ());
796 v
.quick_grow_cleared (e
->ops
.length ());
797 cartesian_product (ops_vector
, result
, v
, 0);
800 for (unsigned i
= 0; i
< result
.length (); ++i
)
802 expr
*ne
= new expr (e
);
803 ne
->is_commutative
= false;
804 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
805 ne
->append_op (result
[i
][j
]);
809 if (!e
->is_commutative
)
812 for (unsigned i
= 0; i
< result
.length (); ++i
)
814 expr
*ne
= new expr (e
);
815 ne
->is_commutative
= false;
816 // result[i].length () is 2 since e->operation is binary
817 for (unsigned j
= result
[i
].length (); j
; --j
)
818 ne
->append_op (result
[i
][j
-1]);
825 /* Lower operations marked as commutative in the AST of S and push
826 the resulting patterns to SIMPLIFIERS. */
829 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
831 vec
<operand
*> matchers
= commutate (s
->match
);
832 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
834 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
835 s
->for_vec
, s
->capture_ids
);
836 simplifiers
.safe_push (ns
);
840 /* Strip conditional conversios using operator OPER from O and its
841 children if STRIP, else replace them with an unconditional convert. */
844 lower_opt_convert (operand
*o
, enum tree_code oper
,
845 enum tree_code to_oper
, bool strip
)
847 if (capture
*c
= dyn_cast
<capture
*> (o
))
850 return new capture (c
->location
, c
->where
,
851 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
856 expr
*e
= dyn_cast
<expr
*> (o
);
860 if (*e
->operation
== oper
)
863 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
865 expr
*ne
= new expr (e
);
866 ne
->operation
= (to_oper
== CONVERT_EXPR
867 ? get_operator ("CONVERT_EXPR")
868 : get_operator ("VIEW_CONVERT_EXPR"));
869 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
873 expr
*ne
= new expr (e
);
874 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
875 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
880 /* Determine whether O or its children uses the conditional conversion
884 has_opt_convert (operand
*o
, enum tree_code oper
)
886 if (capture
*c
= dyn_cast
<capture
*> (o
))
889 return has_opt_convert (c
->what
, oper
);
894 expr
*e
= dyn_cast
<expr
*> (o
);
898 if (*e
->operation
== oper
)
901 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
902 if (has_opt_convert (e
->ops
[i
], oper
))
908 /* Lower conditional convert operators in O, expanding it to a vector
911 static vec
<operand
*>
912 lower_opt_convert (operand
*o
)
914 vec
<operand
*> v1
= vNULL
, v2
;
918 enum tree_code opers
[]
919 = { CONVERT0
, CONVERT_EXPR
,
920 CONVERT1
, CONVERT_EXPR
,
921 CONVERT2
, CONVERT_EXPR
,
922 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
923 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
924 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
926 /* Conditional converts are lowered to a pattern with the
927 conversion and one without. The three different conditional
928 convert codes are lowered separately. */
930 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
933 for (unsigned j
= 0; j
< v1
.length (); ++j
)
934 if (has_opt_convert (v1
[j
], opers
[i
]))
936 v2
.safe_push (lower_opt_convert (v1
[j
],
937 opers
[i
], opers
[i
+1], false));
938 v2
.safe_push (lower_opt_convert (v1
[j
],
939 opers
[i
], opers
[i
+1], true));
945 for (unsigned j
= 0; j
< v2
.length (); ++j
)
946 v1
.safe_push (v2
[j
]);
953 /* Lower conditional convert operators in the AST of S and push
954 the resulting multiple patterns to SIMPLIFIERS. */
957 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
959 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
960 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
962 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
963 s
->for_vec
, s
->capture_ids
);
964 simplifiers
.safe_push (ns
);
968 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
969 GENERIC and a GIMPLE variant. */
971 static vec
<operand
*>
972 lower_cond (operand
*o
)
974 vec
<operand
*> ro
= vNULL
;
976 if (capture
*c
= dyn_cast
<capture
*> (o
))
980 vec
<operand
*> lop
= vNULL
;
981 lop
= lower_cond (c
->what
);
983 for (unsigned i
= 0; i
< lop
.length (); ++i
)
984 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
]));
989 expr
*e
= dyn_cast
<expr
*> (o
);
990 if (!e
|| e
->ops
.length () == 0)
996 vec
< vec
<operand
*> > ops_vector
= vNULL
;
997 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
998 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1000 auto_vec
< vec
<operand
*> > result
;
1001 auto_vec
<operand
*> v (e
->ops
.length ());
1002 v
.quick_grow_cleared (e
->ops
.length ());
1003 cartesian_product (ops_vector
, result
, v
, 0);
1005 for (unsigned i
= 0; i
< result
.length (); ++i
)
1007 expr
*ne
= new expr (e
);
1008 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1009 ne
->append_op (result
[i
][j
]);
1011 /* If this is a COND with a captured expression or an
1012 expression with two operands then also match a GENERIC
1013 form on the compare. */
1014 if ((*e
->operation
== COND_EXPR
1015 || *e
->operation
== VEC_COND_EXPR
)
1016 && ((is_a
<capture
*> (e
->ops
[0])
1017 && as_a
<capture
*> (e
->ops
[0])->what
1018 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1020 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1021 || (is_a
<expr
*> (e
->ops
[0])
1022 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1024 expr
*ne
= new expr (e
);
1025 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1026 ne
->append_op (result
[i
][j
]);
1027 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1029 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1030 expr
*cmp
= new expr (ocmp
);
1031 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1032 cmp
->append_op (ocmp
->ops
[j
]);
1033 cmp
->is_generic
= true;
1034 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
);
1038 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1039 expr
*cmp
= new expr (ocmp
);
1040 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1041 cmp
->append_op (ocmp
->ops
[j
]);
1042 cmp
->is_generic
= true;
1052 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1053 GENERIC and a GIMPLE variant. */
1056 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1058 vec
<operand
*> matchers
= lower_cond (s
->match
);
1059 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1061 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1062 s
->for_vec
, s
->capture_ids
);
1063 simplifiers
.safe_push (ns
);
1067 /* In AST operand O replace operator ID with operator WITH. */
1070 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1072 /* Deep-copy captures and expressions, replacing operations as
1074 if (capture
*c
= dyn_cast
<capture
*> (o
))
1078 return new capture (c
->location
, c
->where
,
1079 replace_id (c
->what
, id
, with
));
1081 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1083 expr
*ne
= new expr (e
);
1084 if (e
->operation
== id
)
1085 ne
->operation
= with
;
1086 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1087 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1090 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1092 with_expr
*nw
= new with_expr (w
->location
);
1093 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1094 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1097 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1099 if_expr
*nife
= new if_expr (ife
->location
);
1100 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1101 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1103 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1107 /* For c_expr we simply record a string replacement table which is
1108 applied at code-generation time. */
1109 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1111 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1112 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1113 return new c_expr (ce
->r
, ce
->location
,
1114 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1120 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1123 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1125 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1126 unsigned worklist_start
= 0;
1127 auto_vec
<simplify
*> worklist
;
1128 worklist
.safe_push (sin
);
1130 /* Lower each recorded for separately, operating on the
1131 set of simplifiers created by the previous one.
1132 Lower inner-to-outer so inner for substitutes can refer
1133 to operators replaced by outer fors. */
1134 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1136 vec
<user_id
*>& ids
= for_vec
[fi
];
1137 unsigned n_ids
= ids
.length ();
1138 unsigned max_n_opers
= 0;
1139 for (unsigned i
= 0; i
< n_ids
; ++i
)
1140 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1141 max_n_opers
= ids
[i
]->substitutes
.length ();
1143 unsigned worklist_end
= worklist
.length ();
1144 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1146 simplify
*s
= worklist
[si
];
1147 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1149 operand
*match_op
= s
->match
;
1150 operand
*result_op
= s
->result
;
1151 for (unsigned i
= 0; i
< n_ids
; ++i
)
1153 user_id
*id
= ids
[i
];
1154 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1155 match_op
= replace_id (match_op
, id
, oper
);
1157 result_op
= replace_id (result_op
, id
, oper
);
1159 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1160 vNULL
, s
->capture_ids
);
1161 worklist
.safe_push (ns
);
1164 worklist_start
= worklist_end
;
1167 /* Copy out the result from the last for lowering. */
1168 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1169 simplifiers
.safe_push (worklist
[i
]);
1172 /* Lower the AST for everything in SIMPLIFIERS. */
1175 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1177 auto_vec
<simplify
*> out_simplifiers
;
1178 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1179 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1181 simplifiers
.truncate (0);
1182 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1183 lower_commutative (out_simplifiers
[i
], simplifiers
);
1185 out_simplifiers
.truncate (0);
1187 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1188 lower_cond (simplifiers
[i
], out_simplifiers
);
1190 out_simplifiers
.safe_splice (simplifiers
);
1193 simplifiers
.truncate (0);
1194 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1195 lower_for (out_simplifiers
[i
], simplifiers
);
1201 /* The decision tree built for generating GIMPLE and GENERIC pattern
1202 matching code. It represents the 'match' expression of all
1203 simplifies and has those as its leafs. */
1205 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1209 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1213 vec
<dt_node
*> kids
;
1217 unsigned total_size
;
1220 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1222 dt_node
*append_node (dt_node
*);
1223 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1224 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1225 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1226 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1228 virtual void gen (FILE *, int, bool) {}
1230 void gen_kids (FILE *, int, bool);
1231 void gen_kids_1 (FILE *, int, bool,
1232 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1233 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1238 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1240 struct dt_operand
: public dt_node
1243 dt_operand
*match_dop
;
1247 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1248 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1249 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1250 parent (parent_
), pos (pos_
) {}
1252 void gen (FILE *, int, bool);
1253 unsigned gen_predicate (FILE *, int, const char *, bool);
1254 unsigned gen_match_op (FILE *, int, const char *);
1256 unsigned gen_gimple_expr (FILE *, int);
1257 unsigned gen_generic_expr (FILE *, int, const char *);
1259 char *get_name (char *);
1260 void gen_opname (char *, unsigned);
1263 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1265 struct dt_simplify
: public dt_node
1268 unsigned pattern_no
;
1269 dt_operand
**indexes
;
1271 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1272 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1273 indexes (indexes_
) {}
1275 void gen_1 (FILE *, int, bool, operand
*);
1276 void gen (FILE *f
, int, bool);
1282 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1284 return (n
->type
== dt_node::DT_OPERAND
1285 || n
->type
== dt_node::DT_MATCH
);
1288 /* A container for the actual decision tree. */
1290 struct decision_tree
1294 void insert (struct simplify
*, unsigned);
1295 void gen_gimple (FILE *f
= stderr
);
1296 void gen_generic (FILE *f
= stderr
);
1297 void print (FILE *f
= stderr
);
1299 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1301 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1302 unsigned pos
= 0, dt_node
*parent
= 0);
1303 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1304 static bool cmp_node (dt_node
*, dt_node
*);
1305 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1308 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1311 cmp_operand (operand
*o1
, operand
*o2
)
1313 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1316 if (o1
->type
== operand::OP_PREDICATE
)
1318 predicate
*p1
= as_a
<predicate
*>(o1
);
1319 predicate
*p2
= as_a
<predicate
*>(o2
);
1320 return p1
->p
== p2
->p
;
1322 else if (o1
->type
== operand::OP_EXPR
)
1324 expr
*e1
= static_cast<expr
*>(o1
);
1325 expr
*e2
= static_cast<expr
*>(o2
);
1326 return (e1
->operation
== e2
->operation
1327 && e1
->is_generic
== e2
->is_generic
);
1333 /* Compare two decision tree nodes N1 and N2 and return true if they
1337 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1339 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1345 if (n1
->type
== dt_node::DT_TRUE
)
1348 if (n1
->type
== dt_node::DT_OPERAND
)
1349 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1350 (as_a
<dt_operand
*> (n2
))->op
);
1351 else if (n1
->type
== dt_node::DT_MATCH
)
1352 return ((as_a
<dt_operand
*> (n1
))->match_dop
1353 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1357 /* Search OPS for a decision tree node like P and return it if found. */
1360 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1362 /* We can merge adjacent DT_TRUE. */
1363 if (p
->type
== dt_node::DT_TRUE
1365 && ops
.last ()->type
== dt_node::DT_TRUE
)
1367 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1369 /* But we can't merge across DT_TRUE nodes as they serve as
1370 pattern order barriers to make sure that patterns apply
1371 in order of appearance in case multiple matches are possible. */
1372 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1374 if (decision_tree::cmp_node (ops
[i
], p
))
1380 /* Append N to the decision tree if it there is not already an existing
1384 dt_node::append_node (dt_node
*n
)
1388 kid
= decision_tree::find_node (kids
, n
);
1393 n
->level
= this->level
+ 1;
1398 /* Append OP to the decision tree. */
1401 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1403 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1404 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1405 return append_node (n
);
1408 /* Append a DT_TRUE decision tree node. */
1411 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1413 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1414 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1415 return append_node (n
);
1418 /* Append a DT_MATCH decision tree node. */
1421 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1423 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1424 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1425 return append_node (n
);
1428 /* Append S to the decision tree. */
1431 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1432 dt_operand
**indexes
)
1434 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1435 return append_node (n
);
1438 /* Analyze the node and its children. */
1447 if (type
== DT_SIMPLIFY
)
1453 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1455 kids
[i
]->analyze ();
1456 num_leafs
+= kids
[i
]->num_leafs
;
1457 total_size
+= kids
[i
]->total_size
;
1458 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1462 /* Insert O into the decision tree and return the decision tree node found
1466 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1467 unsigned pos
, dt_node
*parent
)
1469 dt_node
*q
, *elm
= 0;
1471 if (capture
*c
= dyn_cast
<capture
*> (o
))
1473 unsigned capt_index
= c
->where
;
1475 if (indexes
[capt_index
] == 0)
1478 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1481 q
= elm
= p
->append_true_op (parent
, pos
);
1484 // get to the last capture
1485 for (operand
*what
= c
->what
;
1486 what
&& is_a
<capture
*> (what
);
1487 c
= as_a
<capture
*> (what
), what
= c
->what
)
1492 unsigned cc_index
= c
->where
;
1493 dt_operand
*match_op
= indexes
[cc_index
];
1495 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1496 elm
= decision_tree::find_node (p
->kids
, &temp
);
1500 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1501 elm
= decision_tree::find_node (p
->kids
, &temp
);
1506 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1507 elm
= decision_tree::find_node (p
->kids
, &temp
);
1511 gcc_assert (elm
->type
== dt_node::DT_TRUE
1512 || elm
->type
== dt_node::DT_OPERAND
1513 || elm
->type
== dt_node::DT_MATCH
);
1514 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1519 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1521 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1526 p
= p
->append_op (o
, parent
, pos
);
1529 if (expr
*e
= dyn_cast
<expr
*>(o
))
1531 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1532 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1538 /* Insert S into the decision tree. */
1541 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1543 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1544 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1545 p
->append_simplify (s
, pattern_no
, indexes
);
1548 /* Debug functions to dump the decision tree. */
1551 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1553 if (p
->type
== dt_node::DT_NODE
)
1554 fprintf (f
, "root");
1558 for (unsigned i
= 0; i
< indent
; i
++)
1561 if (p
->type
== dt_node::DT_OPERAND
)
1563 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1564 print_operand (dop
->op
, f
, true);
1566 else if (p
->type
== dt_node::DT_TRUE
)
1567 fprintf (f
, "true");
1568 else if (p
->type
== dt_node::DT_MATCH
)
1569 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1570 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1572 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1573 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1574 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1575 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1580 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1582 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1583 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1587 decision_tree::print (FILE *f
)
1589 return decision_tree::print_node (root
, f
);
1593 /* For GENERIC we have to take care of wrapping multiple-used
1594 expressions with side-effects in save_expr and preserve side-effects
1595 of expressions with omit_one_operand. Analyze captures in
1596 match, result and with expressions and perform early-outs
1597 on the outermost match expression operands for cases we cannot
1602 capture_info (simplify
*s
, operand
*);
1603 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1604 bool walk_result (operand
*o
, bool, operand
*);
1605 void walk_c_expr (c_expr
*);
1611 bool force_no_side_effects_p
;
1612 bool force_single_use
;
1613 bool cond_expr_cond_p
;
1614 unsigned long toplevel_msk
;
1615 int result_use_count
;
1619 auto_vec
<cinfo
> info
;
1620 unsigned long force_no_side_effects
;
1623 /* Analyze captures in S. */
1625 capture_info::capture_info (simplify
*s
, operand
*result
)
1628 if (s
->kind
== simplify::MATCH
)
1630 force_no_side_effects
= -1;
1634 force_no_side_effects
= 0;
1635 info
.safe_grow_cleared (s
->capture_max
+ 1);
1636 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1637 info
[i
].same_as
= i
;
1639 e
= as_a
<expr
*> (s
->match
);
1640 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1641 walk_match (e
->ops
[i
], i
,
1642 (i
!= 0 && *e
->operation
== COND_EXPR
)
1643 || *e
->operation
== TRUTH_ANDIF_EXPR
1644 || *e
->operation
== TRUTH_ORIF_EXPR
,
1646 && (*e
->operation
== COND_EXPR
1647 || *e
->operation
== VEC_COND_EXPR
));
1649 walk_result (s
->result
, false, result
);
1652 /* Analyze captures in the match expression piece O. */
1655 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1656 bool conditional_p
, bool cond_expr_cond_p
)
1658 if (capture
*c
= dyn_cast
<capture
*> (o
))
1660 unsigned where
= c
->where
;
1661 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
1662 info
[where
].force_no_side_effects_p
|= conditional_p
;
1663 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1666 /* Recurse to exprs and captures. */
1667 if (is_a
<capture
*> (c
->what
)
1668 || is_a
<expr
*> (c
->what
))
1669 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1670 /* We need to look past multiple captures to find a captured
1671 expression as with conditional converts two captures
1672 can be collapsed onto the same expression. Also collect
1673 what captures capture the same thing. */
1674 while (c
->what
&& is_a
<capture
*> (c
->what
))
1676 c
= as_a
<capture
*> (c
->what
);
1677 if (info
[c
->where
].same_as
!= c
->where
1678 && info
[c
->where
].same_as
!= info
[where
].same_as
)
1679 fatal_at (c
->location
, "cannot handle this collapsed capture");
1680 info
[c
->where
].same_as
= info
[where
].same_as
;
1682 /* Mark expr (non-leaf) captures and forced single-use exprs. */
1685 && (e
= dyn_cast
<expr
*> (c
->what
)))
1687 info
[where
].expr_p
= true;
1688 info
[where
].force_single_use
|= e
->force_single_use
;
1691 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1693 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1695 bool cond_p
= conditional_p
;
1696 bool cond_expr_cond_p
= false;
1697 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1699 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1700 || *e
->operation
== TRUTH_ORIF_EXPR
)
1703 && (*e
->operation
== COND_EXPR
1704 || *e
->operation
== VEC_COND_EXPR
))
1705 cond_expr_cond_p
= true;
1706 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1709 else if (is_a
<predicate
*> (o
))
1711 /* Mark non-captured leafs toplevel arg for checking. */
1712 force_no_side_effects
|= 1 << toplevel_arg
;
1718 /* Analyze captures in the result expression piece O. Return true
1719 if RESULT was visited in one of the children. Only visit
1720 non-if/with children if they are rooted on RESULT. */
1723 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
1725 if (capture
*c
= dyn_cast
<capture
*> (o
))
1727 unsigned where
= info
[c
->where
].same_as
;
1728 info
[where
].result_use_count
++;
1729 /* If we substitute an expression capture we don't know
1730 which captures this will end up using (well, we don't
1731 compute that). Force the uses to be side-effect free
1732 which means forcing the toplevels that reach the
1733 expression side-effect free. */
1734 if (info
[where
].expr_p
)
1735 force_no_side_effects
|= info
[where
].toplevel_msk
;
1736 /* Mark CSE capture uses as forced to have no side-effects. */
1738 && is_a
<expr
*> (c
->what
))
1740 info
[where
].cse_p
= true;
1741 walk_result (c
->what
, true, result
);
1744 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1746 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1748 bool cond_p
= conditional_p
;
1749 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1751 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1752 || *e
->operation
== TRUTH_ORIF_EXPR
)
1754 walk_result (e
->ops
[i
], cond_p
, result
);
1757 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
1759 /* 'if' conditions should be all fine. */
1760 if (e
->trueexpr
== result
)
1762 walk_result (e
->trueexpr
, false, result
);
1765 if (e
->falseexpr
== result
)
1767 walk_result (e
->falseexpr
, false, result
);
1771 if (is_a
<if_expr
*> (e
->trueexpr
)
1772 || is_a
<with_expr
*> (e
->trueexpr
))
1773 res
|= walk_result (e
->trueexpr
, false, result
);
1775 && (is_a
<if_expr
*> (e
->falseexpr
)
1776 || is_a
<with_expr
*> (e
->falseexpr
)))
1777 res
|= walk_result (e
->falseexpr
, false, result
);
1780 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
1782 bool res
= (e
->subexpr
== result
);
1784 || is_a
<if_expr
*> (e
->subexpr
)
1785 || is_a
<with_expr
*> (e
->subexpr
))
1786 res
|= walk_result (e
->subexpr
, false, result
);
1788 walk_c_expr (e
->with
);
1791 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1799 /* Look for captures in the C expr E. */
1802 capture_info::walk_c_expr (c_expr
*e
)
1804 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1805 unsigned p_depth
= 0;
1806 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1808 const cpp_token
*t
= &e
->code
[i
];
1809 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1810 if (t
->type
== CPP_NAME
1811 && strcmp ((const char *)CPP_HASHNODE
1812 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1813 && n
->type
== CPP_OPEN_PAREN
)
1815 else if (t
->type
== CPP_CLOSE_PAREN
1818 else if (p_depth
== 0
1819 && t
->type
== CPP_ATSIGN
1820 && (n
->type
== CPP_NUMBER
1821 || n
->type
== CPP_NAME
)
1822 && !(n
->flags
& PREV_WHITE
))
1825 if (n
->type
== CPP_NUMBER
)
1826 id
= (const char *)n
->val
.str
.text
;
1828 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1829 unsigned where
= *e
->capture_ids
->get(id
);
1830 info
[info
[where
].same_as
].force_no_side_effects_p
= true;
1836 /* Code generation off the decision tree and the refered AST nodes. */
1839 is_conversion (id_base
*op
)
1841 return (*op
== CONVERT_EXPR
1843 || *op
== FLOAT_EXPR
1844 || *op
== FIX_TRUNC_EXPR
1845 || *op
== VIEW_CONVERT_EXPR
);
1848 /* Get the type to be used for generating operands of OP from the
1852 get_operand_type (id_base
*op
, const char *in_type
,
1853 const char *expr_type
,
1854 const char *other_oprnd_type
)
1856 /* Generally operands whose type does not match the type of the
1857 expression generated need to know their types but match and
1858 thus can fall back to 'other_oprnd_type'. */
1859 if (is_conversion (op
))
1860 return other_oprnd_type
;
1861 else if (*op
== REALPART_EXPR
1862 || *op
== IMAGPART_EXPR
)
1863 return other_oprnd_type
;
1864 else if (is_a
<operator_id
*> (op
)
1865 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1866 return other_oprnd_type
;
1869 /* Otherwise all types should match - choose one in order of
1876 return other_oprnd_type
;
1880 /* Generate transform code for an expression. */
1883 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
1884 int depth
, const char *in_type
, capture_info
*cinfo
,
1885 dt_operand
**indexes
, bool)
1887 bool conversion_p
= is_conversion (operation
);
1888 const char *type
= expr_type
;
1891 /* If there was a type specification in the pattern use it. */
1893 else if (conversion_p
)
1894 /* For conversions we need to build the expression using the
1895 outer type passed in. */
1897 else if (*operation
== REALPART_EXPR
1898 || *operation
== IMAGPART_EXPR
)
1900 /* __real and __imag use the component type of its operand. */
1901 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1904 else if (is_a
<operator_id
*> (operation
)
1905 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1907 /* comparisons use boolean_type_node (or what gets in), but
1908 their operands need to figure out the types themselves. */
1909 sprintf (optype
, "boolean_type_node");
1912 else if (*operation
== COND_EXPR
1913 || *operation
== VEC_COND_EXPR
)
1915 /* Conditions are of the same type as their first alternative. */
1916 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1921 /* Other operations are of the same type as their first operand. */
1922 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1926 fatal_at (location
, "cannot determine type of operand");
1928 fprintf_indent (f
, indent
, "{\n");
1930 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
1932 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1933 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1936 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
1938 = get_operand_type (operation
, in_type
, expr_type
,
1939 i
== 0 ? NULL
: op0type
);
1940 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
1942 ((!(*operation
== COND_EXPR
)
1943 && !(*operation
== VEC_COND_EXPR
))
1948 if (*operation
== CONVERT_EXPR
)
1951 opr
= operation
->id
;
1955 if (*operation
== CONVERT_EXPR
)
1957 fprintf_indent (f
, indent
,
1958 "if (%s != TREE_TYPE (ops%d[0])\n",
1960 fprintf_indent (f
, indent
,
1961 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
1963 fprintf_indent (f
, indent
+ 2, "{\n");
1966 /* ??? Building a stmt can fail for various reasons here, seq being
1967 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1968 So if we fail here we should continue matching other patterns. */
1969 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr
);
1970 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
1971 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1972 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1973 i
== ops
.length () - 1 ? " };\n" : ", ");
1974 fprintf_indent (f
, indent
,
1975 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
1976 ops
.length (), type
);
1977 fprintf_indent (f
, indent
,
1978 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
1980 fprintf_indent (f
, indent
,
1981 "if (!res) return false;\n");
1982 if (*operation
== CONVERT_EXPR
)
1985 fprintf_indent (f
, indent
, " }\n");
1986 fprintf_indent (f
, indent
, "else\n");
1987 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
1992 if (*operation
== CONVERT_EXPR
)
1994 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
1998 if (operation
->kind
== id_base::CODE
)
1999 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2000 ops
.length(), opr
, type
);
2002 fprintf_indent (f
, indent
, "res = build_call_expr_loc (loc, "
2003 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
2004 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2005 fprintf (f
, ", ops%d[%u]", depth
, i
);
2006 fprintf (f
, ");\n");
2007 if (*operation
== CONVERT_EXPR
)
2010 fprintf_indent (f
, indent
, "else\n");
2011 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2014 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2016 fprintf_indent (f
, indent
, "}\n");
2019 /* Generate code for a c_expr which is either the expression inside
2020 an if statement or a sequence of statements which computes a
2021 result to be stored to DEST. */
2024 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2025 bool, int, const char *, capture_info
*,
2026 dt_operand
**, bool)
2028 if (dest
&& nr_stmts
== 1)
2029 fprintf_indent (f
, indent
, "%s = ", dest
);
2031 unsigned stmt_nr
= 1;
2032 for (unsigned i
= 0; i
< code
.length (); ++i
)
2034 const cpp_token
*token
= &code
[i
];
2036 /* Replace captures for code-gen. */
2037 if (token
->type
== CPP_ATSIGN
)
2039 const cpp_token
*n
= &code
[i
+1];
2040 if ((n
->type
== CPP_NUMBER
2041 || n
->type
== CPP_NAME
)
2042 && !(n
->flags
& PREV_WHITE
))
2044 if (token
->flags
& PREV_WHITE
)
2047 if (n
->type
== CPP_NUMBER
)
2048 id
= (const char *)n
->val
.str
.text
;
2050 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2051 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
2057 if (token
->flags
& PREV_WHITE
)
2060 if (token
->type
== CPP_NAME
)
2062 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2064 for (j
= 0; j
< ids
.length (); ++j
)
2066 if (strcmp (id
, ids
[j
].id
) == 0)
2068 fprintf (f
, "%s", ids
[j
].oper
);
2072 if (j
< ids
.length ())
2076 /* Output the token as string. */
2077 char *tk
= (char *)cpp_token_as_text (r
, token
);
2080 if (token
->type
== CPP_SEMICOLON
)
2084 if (dest
&& stmt_nr
== nr_stmts
)
2085 fprintf_indent (f
, indent
, "%s = ", dest
);
2090 /* Generate transform code for a capture. */
2093 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2094 int depth
, const char *in_type
, capture_info
*cinfo
,
2095 dt_operand
**indexes
, bool expand_compares
)
2097 if (what
&& is_a
<expr
*> (what
))
2099 if (indexes
[where
] == 0)
2102 sprintf (buf
, "captures[%u]", where
);
2103 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2108 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2110 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2111 with substituting a capture of that.
2112 ??? Returning false here will also not allow any other patterns
2114 if (gimple
&& expand_compares
2115 && cinfo
->info
[where
].cond_expr_cond_p
)
2117 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2118 fprintf_indent (f
, indent
, " {\n");
2119 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2120 fprintf_indent (f
, indent
, " %s = gimple_build (seq, TREE_CODE (%s),"
2121 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2122 " TREE_OPERAND (%s, 1));\n",
2123 dest
, dest
, dest
, dest
, dest
);
2124 fprintf_indent (f
, indent
, " }\n");
2128 /* Return the name of the operand representing the decision tree node.
2129 Use NAME as space to generate it. */
2132 dt_operand::get_name (char *name
)
2135 sprintf (name
, "t");
2136 else if (parent
->level
== 1)
2137 sprintf (name
, "op%u", pos
);
2138 else if (parent
->type
== dt_node::DT_MATCH
)
2139 return parent
->get_name (name
);
2141 sprintf (name
, "o%u%u", parent
->level
, pos
);
2145 /* Fill NAME with the operand name at position POS. */
2148 dt_operand::gen_opname (char *name
, unsigned pos
)
2151 sprintf (name
, "op%u", pos
);
2153 sprintf (name
, "o%u%u", level
, pos
);
2156 /* Generate matching code for the decision tree operand which is
2160 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2162 predicate
*p
= as_a
<predicate
*> (op
);
2164 if (p
->p
->matchers
.exists ())
2166 /* If this is a predicate generated from a pattern mangle its
2167 name and pass on the valueize hook. */
2169 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2172 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2175 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2176 fprintf_indent (f
, indent
+ 2, "{\n");
2180 /* Generate matching code for the decision tree operand which is
2184 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
)
2186 char match_opname
[20];
2187 match_dop
->get_name (match_opname
);
2188 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2189 opname
, match_opname
, opname
, match_opname
);
2190 fprintf_indent (f
, indent
+ 2, "{\n");
2194 /* Generate GIMPLE matching code for the decision tree operand. */
2197 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2199 expr
*e
= static_cast<expr
*> (op
);
2200 id_base
*id
= e
->operation
;
2201 unsigned n_ops
= e
->ops
.length ();
2203 for (unsigned i
= 0; i
< n_ops
; ++i
)
2205 char child_opname
[20];
2206 gen_opname (child_opname
, i
);
2208 if (id
->kind
== id_base::CODE
)
2211 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2212 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2214 /* ??? If this is a memory operation we can't (and should not)
2215 match this. The only sensible operand types are
2216 SSA names and invariants. */
2217 fprintf_indent (f
, indent
,
2218 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
2220 fprintf_indent (f
, indent
,
2221 "if ((TREE_CODE (%s) == SSA_NAME\n",
2223 fprintf_indent (f
, indent
,
2224 " || is_gimple_min_invariant (%s))\n",
2226 fprintf_indent (f
, indent
,
2227 " && (%s = do_valueize (valueize, %s)))\n",
2228 child_opname
, child_opname
);
2229 fprintf_indent (f
, indent
,
2235 fprintf_indent (f
, indent
,
2236 "tree %s = gimple_assign_rhs%u (def_stmt);\n",
2237 child_opname
, i
+ 1);
2240 fprintf_indent (f
, indent
,
2241 "tree %s = gimple_call_arg (def_stmt, %u);\n",
2243 fprintf_indent (f
, indent
,
2244 "if ((%s = do_valueize (valueize, %s)))\n",
2245 child_opname
, child_opname
);
2246 fprintf_indent (f
, indent
, " {\n");
2249 /* While the toplevel operands are canonicalized by the caller
2250 after valueizing operands of sub-expressions we have to
2251 re-canonicalize operand order. */
2252 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2254 /* ??? We can't canonicalize tcc_comparison operands here
2255 because that requires changing the comparison code which
2256 we already matched... */
2257 if (commutative_tree_code (code
->code
)
2258 || commutative_ternary_tree_code (code
->code
))
2260 char child_opname0
[20], child_opname1
[20];
2261 gen_opname (child_opname0
, 0);
2262 gen_opname (child_opname1
, 1);
2263 fprintf_indent (f
, indent
,
2264 "if (tree_swap_operands_p (%s, %s, false))\n",
2265 child_opname0
, child_opname1
);
2266 fprintf_indent (f
, indent
,
2267 " std::swap (%s, %s);\n",
2268 child_opname0
, child_opname1
);
2275 /* Generate GENERIC matching code for the decision tree operand. */
2278 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2280 expr
*e
= static_cast<expr
*> (op
);
2281 unsigned n_ops
= e
->ops
.length ();
2283 for (unsigned i
= 0; i
< n_ops
; ++i
)
2285 char child_opname
[20];
2286 gen_opname (child_opname
, i
);
2288 if (e
->operation
->kind
== id_base::CODE
)
2289 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2290 child_opname
, opname
, i
);
2292 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2293 child_opname
, opname
, i
);
2299 /* Generate matching code for the children of the decision tree node. */
2302 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2304 auto_vec
<dt_operand
*> gimple_exprs
;
2305 auto_vec
<dt_operand
*> generic_exprs
;
2306 auto_vec
<dt_operand
*> fns
;
2307 auto_vec
<dt_operand
*> generic_fns
;
2308 auto_vec
<dt_operand
*> preds
;
2309 auto_vec
<dt_node
*> others
;
2311 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2313 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2315 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2316 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2318 if (e
->ops
.length () == 0
2319 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2320 generic_exprs
.safe_push (op
);
2321 else if (e
->operation
->kind
== id_base::FN
)
2326 generic_fns
.safe_push (op
);
2328 else if (e
->operation
->kind
== id_base::PREDICATE
)
2329 preds
.safe_push (op
);
2333 gimple_exprs
.safe_push (op
);
2335 generic_exprs
.safe_push (op
);
2338 else if (op
->op
->type
== operand::OP_PREDICATE
)
2339 others
.safe_push (kids
[i
]);
2343 else if (kids
[i
]->type
== dt_node::DT_MATCH
2344 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2345 others
.safe_push (kids
[i
]);
2346 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2348 /* A DT_TRUE operand serves as a barrier - generate code now
2349 for what we have collected sofar. */
2350 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2351 fns
, generic_fns
, preds
, others
);
2352 /* And output the true operand itself. */
2353 kids
[i
]->gen (f
, indent
, gimple
);
2354 gimple_exprs
.truncate (0);
2355 generic_exprs
.truncate (0);
2357 generic_fns
.truncate (0);
2359 others
.truncate (0);
2365 /* Generate code for the remains. */
2366 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2367 fns
, generic_fns
, preds
, others
);
2370 /* Generate matching code for the children of the decision tree node. */
2373 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2374 vec
<dt_operand
*> gimple_exprs
,
2375 vec
<dt_operand
*> generic_exprs
,
2376 vec
<dt_operand
*> fns
,
2377 vec
<dt_operand
*> generic_fns
,
2378 vec
<dt_operand
*> preds
,
2379 vec
<dt_node
*> others
)
2382 char *kid_opname
= buf
;
2384 unsigned exprs_len
= gimple_exprs
.length ();
2385 unsigned gexprs_len
= generic_exprs
.length ();
2386 unsigned fns_len
= fns
.length ();
2387 unsigned gfns_len
= generic_fns
.length ();
2389 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2392 gimple_exprs
[0]->get_name (kid_opname
);
2394 fns
[0]->get_name (kid_opname
);
2396 generic_fns
[0]->get_name (kid_opname
);
2398 generic_exprs
[0]->get_name (kid_opname
);
2400 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2401 fprintf_indent (f
, indent
, " {\n");
2405 if (exprs_len
|| fns_len
)
2407 fprintf_indent (f
, indent
,
2408 "case SSA_NAME:\n");
2409 fprintf_indent (f
, indent
,
2410 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2412 fprintf_indent (f
, indent
,
2414 fprintf_indent (f
, indent
,
2415 " gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2421 fprintf_indent (f
, indent
,
2422 "if (is_gimple_assign (def_stmt))\n");
2423 fprintf_indent (f
, indent
,
2424 " switch (gimple_assign_rhs_code (def_stmt))\n");
2426 fprintf_indent (f
, indent
, "{\n");
2427 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2429 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2430 id_base
*op
= e
->operation
;
2431 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2432 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2434 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2435 fprintf_indent (f
, indent
, " {\n");
2436 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2437 fprintf_indent (f
, indent
, " break;\n");
2438 fprintf_indent (f
, indent
, " }\n");
2440 fprintf_indent (f
, indent
, "default:;\n");
2441 fprintf_indent (f
, indent
, "}\n");
2448 fprintf_indent (f
, indent
, "else ");
2450 fprintf_indent (f
, indent
, " ");
2452 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n");
2453 fprintf_indent (f
, indent
,
2455 fprintf_indent (f
, indent
,
2456 " tree fndecl = gimple_call_fndecl (def_stmt);\n");
2457 fprintf_indent (f
, indent
,
2458 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2459 fprintf_indent (f
, indent
,
2463 for (unsigned i
= 0; i
< fns_len
; ++i
)
2465 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2466 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2467 fprintf_indent (f
, indent
, " {\n");
2468 fns
[i
]->gen (f
, indent
+ 4, true);
2469 fprintf_indent (f
, indent
, " break;\n");
2470 fprintf_indent (f
, indent
, " }\n");
2473 fprintf_indent (f
, indent
, "default:;\n");
2474 fprintf_indent (f
, indent
, "}\n");
2476 fprintf_indent (f
, indent
, " }\n");
2480 fprintf_indent (f
, indent
, " }\n");
2481 fprintf_indent (f
, indent
, " break;\n");
2484 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2486 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2487 id_base
*op
= e
->operation
;
2488 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2489 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2491 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2492 fprintf_indent (f
, indent
, " {\n");
2493 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2494 fprintf_indent (f
, indent
, " break;\n");
2495 fprintf_indent (f
, indent
, " }\n");
2500 fprintf_indent (f
, indent
,
2501 "case CALL_EXPR:\n");
2502 fprintf_indent (f
, indent
,
2504 fprintf_indent (f
, indent
,
2505 " tree fndecl = get_callee_fndecl (%s);\n",
2507 fprintf_indent (f
, indent
,
2508 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2509 fprintf_indent (f
, indent
,
2510 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2511 fprintf_indent (f
, indent
,
2515 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2517 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2518 gcc_assert (e
->operation
->kind
== id_base::FN
);
2520 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2521 fprintf_indent (f
, indent
, " {\n");
2522 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2523 fprintf_indent (f
, indent
, " break;\n");
2524 fprintf_indent (f
, indent
, " }\n");
2528 fprintf_indent (f
, indent
, " default:;\n");
2529 fprintf_indent (f
, indent
, " }\n");
2530 fprintf_indent (f
, indent
, " break;\n");
2531 fprintf_indent (f
, indent
, " }\n");
2534 /* Close switch (TREE_CODE ()). */
2535 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2538 fprintf_indent (f
, indent
, " default:;\n");
2539 fprintf_indent (f
, indent
, " }\n");
2542 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2544 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2545 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2546 preds
[i
]->get_name (kid_opname
);
2547 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2548 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2549 gimple
? "gimple" : "tree",
2550 p
->id
, kid_opname
, kid_opname
,
2551 gimple
? ", valueize" : "");
2552 fprintf_indent (f
, indent
, " {\n");
2553 for (int j
= 0; j
< p
->nargs
; ++j
)
2555 char child_opname
[20];
2556 preds
[i
]->gen_opname (child_opname
, j
);
2557 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2558 child_opname
, kid_opname
, j
);
2560 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2564 for (unsigned i
= 0; i
< others
.length (); ++i
)
2565 others
[i
]->gen (f
, indent
, gimple
);
2568 /* Generate matching code for the decision tree operand. */
2571 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2576 unsigned n_braces
= 0;
2578 if (type
== DT_OPERAND
)
2581 case operand::OP_PREDICATE
:
2582 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2585 case operand::OP_EXPR
:
2587 n_braces
= gen_gimple_expr (f
, indent
);
2589 n_braces
= gen_generic_expr (f
, indent
, opname
);
2595 else if (type
== DT_TRUE
)
2597 else if (type
== DT_MATCH
)
2598 n_braces
= gen_match_op (f
, indent
, opname
);
2602 indent
+= 4 * n_braces
;
2603 gen_kids (f
, indent
, gimple
);
2605 for (unsigned i
= 0; i
< n_braces
; ++i
)
2610 fprintf_indent (f
, indent
, " }\n");
2615 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2616 step of a '(simplify ...)' or '(match ...)'. This handles everything
2617 that is not part of the decision tree (simplify->match).
2618 Main recursive worker. */
2621 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2625 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2627 fprintf_indent (f
, indent
, "{\n");
2629 output_line_directive (f
, w
->location
);
2630 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2631 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2633 fprintf_indent (f
, indent
, "}\n");
2636 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2638 output_line_directive (f
, ife
->location
);
2639 fprintf_indent (f
, indent
, "if (");
2640 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2642 fprintf_indent (f
, indent
+ 2, "{\n");
2644 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2646 fprintf_indent (f
, indent
+ 2, "}\n");
2649 fprintf_indent (f
, indent
, "else\n");
2650 fprintf_indent (f
, indent
+ 2, "{\n");
2652 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2654 fprintf_indent (f
, indent
+ 2, "}\n");
2660 /* Analyze captures and perform early-outs on the incoming arguments
2661 that cover cases we cannot handle. */
2662 capture_info
cinfo (s
, result
);
2663 if (s
->kind
== simplify::SIMPLIFY
)
2667 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2668 if (cinfo
.force_no_side_effects
& (1 << i
))
2669 fprintf_indent (f
, indent
,
2670 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2672 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2673 if (cinfo
.info
[i
].cse_p
)
2675 else if (cinfo
.info
[i
].force_no_side_effects_p
2676 && (cinfo
.info
[i
].toplevel_msk
2677 & cinfo
.force_no_side_effects
) == 0)
2678 fprintf_indent (f
, indent
,
2679 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2680 "return NULL_TREE;\n", i
);
2681 else if ((cinfo
.info
[i
].toplevel_msk
2682 & cinfo
.force_no_side_effects
) != 0)
2683 /* Mark capture as having no side-effects if we had to verify
2684 that via forced toplevel operand checks. */
2685 cinfo
.info
[i
].force_no_side_effects_p
= true;
2689 /* Force single-use restriction by only allowing simple
2690 results via setting seq to NULL. */
2691 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2692 bool first_p
= true;
2693 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2694 if (cinfo
.info
[i
].force_single_use
)
2698 fprintf_indent (f
, indent
, "if (lseq\n");
2699 fprintf_indent (f
, indent
, " && (");
2705 fprintf_indent (f
, indent
, " || ");
2707 fprintf (f
, "!single_use (captures[%d])", i
);
2711 fprintf (f
, "))\n");
2712 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2717 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2718 "fprintf (dump_file, \"Applying pattern ");
2719 output_line_directive (f
,
2720 result
? result
->location
: s
->match
->location
, true);
2721 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2725 /* If there is no result then this is a predicate implementation. */
2726 fprintf_indent (f
, indent
, "return true;\n");
2730 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2731 in outermost position). */
2732 if (result
->type
== operand::OP_EXPR
2733 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2734 result
= as_a
<expr
*> (result
)->ops
[0];
2735 if (result
->type
== operand::OP_EXPR
)
2737 expr
*e
= as_a
<expr
*> (result
);
2738 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2740 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2741 *e
->operation
== CONVERT_EXPR
2742 ? "NOP_EXPR" : e
->operation
->id
);
2743 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2746 snprintf (dest
, 32, "res_ops[%d]", j
);
2748 = get_operand_type (e
->operation
,
2749 "type", e
->expr_type
,
2750 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2751 /* We need to expand GENERIC conditions we captured from
2753 bool expand_generic_cond_exprs_p
2755 /* But avoid doing that if the GENERIC condition is
2756 valid - which it is in the first operand of COND_EXPRs
2757 and VEC_COND_EXRPs. */
2758 && ((!(*e
->operation
== COND_EXPR
)
2759 && !(*e
->operation
== VEC_COND_EXPR
))
2761 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
2763 indexes
, expand_generic_cond_exprs_p
);
2766 /* Re-fold the toplevel result. It's basically an embedded
2767 gimple_build w/o actually building the stmt. */
2769 fprintf_indent (f
, indent
,
2770 "gimple_resimplify%d (lseq, res_code, type, "
2771 "res_ops, valueize);\n", e
->ops
.length ());
2773 else if (result
->type
== operand::OP_CAPTURE
2774 || result
->type
== operand::OP_C_EXPR
)
2776 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
2777 &cinfo
, indexes
, false);
2778 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
2779 if (is_a
<capture
*> (result
)
2780 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2782 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2783 with substituting a capture of that. */
2784 fprintf_indent (f
, indent
,
2785 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2786 fprintf_indent (f
, indent
,
2788 fprintf_indent (f
, indent
,
2789 " tree tem = res_ops[0];\n");
2790 fprintf_indent (f
, indent
,
2791 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
2792 fprintf_indent (f
, indent
,
2793 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
2794 fprintf_indent (f
, indent
,
2800 fprintf_indent (f
, indent
, "return true;\n");
2804 bool is_predicate
= false;
2805 if (result
->type
== operand::OP_EXPR
)
2807 expr
*e
= as_a
<expr
*> (result
);
2808 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2809 /* Search for captures used multiple times in the result expression
2810 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2812 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2814 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
2816 if (!cinfo
.info
[i
].force_no_side_effects_p
2817 && cinfo
.info
[i
].result_use_count
> 1)
2819 fprintf_indent (f
, indent
,
2820 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2822 fprintf_indent (f
, indent
,
2823 " captures[%d] = save_expr (captures[%d]);\n",
2827 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2831 snprintf (dest
, 32, "res_ops[%d]", j
);
2834 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
2835 snprintf (dest
, 32, "res_op%d", j
);
2838 = get_operand_type (e
->operation
,
2839 "type", e
->expr_type
,
2841 ? NULL
: "TREE_TYPE (res_op0)");
2842 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
2846 fprintf_indent (f
, indent
, "return true;\n");
2849 fprintf_indent (f
, indent
, "tree res;\n");
2850 /* Re-fold the toplevel result. Use non_lvalue to
2851 build NON_LVALUE_EXPRs so they get properly
2852 ignored when in GIMPLE form. */
2853 if (*e
->operation
== NON_LVALUE_EXPR
)
2854 fprintf_indent (f
, indent
,
2855 "res = non_lvalue_loc (loc, res_op0);\n");
2858 if (e
->operation
->kind
== id_base::CODE
)
2859 fprintf_indent (f
, indent
,
2860 "res = fold_build%d_loc (loc, %s, type",
2862 *e
->operation
== CONVERT_EXPR
2863 ? "NOP_EXPR" : e
->operation
->id
);
2865 fprintf_indent (f
, indent
,
2866 "res = build_call_expr_loc "
2867 "(loc, builtin_decl_implicit (%s), %d",
2868 e
->operation
->id
, e
->ops
.length());
2869 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2870 fprintf (f
, ", res_op%d", j
);
2871 fprintf (f
, ");\n");
2875 else if (result
->type
== operand::OP_CAPTURE
2876 || result
->type
== operand::OP_C_EXPR
)
2879 fprintf_indent (f
, indent
, "tree res;\n");
2880 result
->gen_transform (f
, indent
, "res", false, 1, "type",
2887 /* Search for captures not used in the result expression and dependent
2888 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2889 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2891 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
2893 if (!cinfo
.info
[i
].force_no_side_effects_p
2894 && !cinfo
.info
[i
].expr_p
2895 && cinfo
.info
[i
].result_use_count
== 0)
2897 fprintf_indent (f
, indent
,
2898 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
2900 fprintf_indent (f
, indent
+ 2,
2901 "res = build2_loc (loc, COMPOUND_EXPR, type, "
2902 "fold_ignored_result (captures[%d]), res);\n",
2906 fprintf_indent (f
, indent
, "return res;\n");
2911 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2912 step of a '(simplify ...)' or '(match ...)'. This handles everything
2913 that is not part of the decision tree (simplify->match). */
2916 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
2918 fprintf_indent (f
, indent
, "{\n");
2920 output_line_directive (f
,
2921 s
->result
? s
->result
->location
: s
->match
->location
);
2922 if (s
->capture_max
>= 0)
2923 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2924 s
->capture_max
+ 1);
2926 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2930 fprintf_indent (f
, indent
, "captures[%u] = %s;\n",
2931 i
, indexes
[i
]->get_name (opname
));
2934 gen_1 (f
, indent
, gimple
, s
->result
);
2937 fprintf_indent (f
, indent
, "}\n");
2940 /* Main entry to generate code for matching GIMPLE IL off the decision
2944 decision_tree::gen_gimple (FILE *f
)
2948 fprintf (stderr
, "GIMPLE decision tree has %u leafs, maximum depth %u and "
2949 "a total number of %u nodes\n", root
->num_leafs
, root
->max_level
,
2952 for (unsigned n
= 1; n
<= 3; ++n
)
2954 fprintf (f
, "\nstatic bool\n"
2955 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2956 " gimple_seq *seq, tree (*valueize)(tree),\n"
2957 " code_helper code, tree type");
2958 for (unsigned i
= 0; i
< n
; ++i
)
2959 fprintf (f
, ", tree op%d", i
);
2963 fprintf (f
, " switch (code.get_rep())\n"
2965 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2967 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2968 expr
*e
= static_cast<expr
*>(dop
->op
);
2969 if (e
->ops
.length () != n
)
2972 if (*e
->operation
== CONVERT_EXPR
2973 || *e
->operation
== NOP_EXPR
)
2974 fprintf (f
, " CASE_CONVERT:\n");
2976 fprintf (f
, " case %s%s:\n",
2977 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2979 fprintf (f
, " {\n");
2980 dop
->gen_kids (f
, 8, true);
2981 fprintf (f
, " break;\n");
2982 fprintf (f
, " }\n");
2984 fprintf (f
, " default:;\n"
2987 fprintf (f
, " return false;\n");
2992 /* Main entry to generate code for matching GENERIC IL off the decision
2996 decision_tree::gen_generic (FILE *f
)
3000 fprintf (stderr
, "GENERIC decision tree has %u leafs, maximum depth %u and "
3001 "a total number of %u nodes\n", root
->num_leafs
, root
->max_level
,
3004 for (unsigned n
= 1; n
<= 3; ++n
)
3006 fprintf (f
, "\ntree\n"
3007 "generic_simplify (location_t loc, enum tree_code code, "
3008 "tree type ATTRIBUTE_UNUSED");
3009 for (unsigned i
= 0; i
< n
; ++i
)
3010 fprintf (f
, ", tree op%d", i
);
3014 fprintf (f
, " switch (code)\n"
3016 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3018 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3019 expr
*e
= static_cast<expr
*>(dop
->op
);
3020 if (e
->ops
.length () != n
3021 /* Builtin simplifications are somewhat premature on
3022 GENERIC. The following drops patterns with outermost
3023 calls. It's easy to emit overloads for function code
3024 though if necessary. */
3025 || e
->operation
->kind
!= id_base::CODE
)
3028 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
3029 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
3030 fprintf (f
, " CASE_CONVERT:\n");
3032 fprintf (f
, " case %s:\n", e
->operation
->id
);
3033 fprintf (f
, " {\n");
3034 dop
->gen_kids (f
, 8, false);
3035 fprintf (f
, " break;\n"
3038 fprintf (f
, " default:;\n"
3041 fprintf (f
, " return NULL_TREE;\n");
3046 /* Output code to implement the predicate P from the decision tree DT. */
3049 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3051 fprintf (f
, "\nbool\n"
3052 "%s%s (tree t%s%s)\n"
3053 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3054 p
->nargs
> 0 ? ", tree *res_ops" : "",
3055 gimple
? ", tree (*valueize)(tree)" : "");
3056 /* Conveniently make 'type' available. */
3057 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3060 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3061 dt
.root
->gen_kids (f
, 2, gimple
);
3063 fprintf_indent (f
, 2, "return false;\n"
3067 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3070 write_header (FILE *f
, const char *head
)
3072 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3073 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3075 /* Include the header instead of writing it awkwardly quoted here. */
3076 fprintf (f
, "\n#include \"%s\"\n", head
);
3086 parser (cpp_reader
*);
3089 const cpp_token
*next ();
3090 const cpp_token
*peek (unsigned = 1);
3091 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3092 const cpp_token
*expect (enum cpp_ttype
);
3093 const cpp_token
*eat_token (enum cpp_ttype
);
3094 const char *get_string ();
3095 const char *get_ident ();
3096 const cpp_token
*eat_ident (const char *);
3097 const char *get_number ();
3099 id_base
*parse_operation ();
3100 operand
*parse_capture (operand
*);
3101 operand
*parse_expr ();
3102 c_expr
*parse_c_expr (cpp_ttype
);
3103 operand
*parse_op ();
3105 void record_operlist (source_location
, user_id
*);
3107 void parse_pattern ();
3108 operand
*parse_result (operand
*, predicate_id
*);
3109 void push_simplify (simplify::simplify_kind
,
3110 vec
<simplify
*>&, operand
*, operand
*);
3111 void parse_simplify (simplify::simplify_kind
,
3112 vec
<simplify
*>&, predicate_id
*, operand
*);
3113 void parse_for (source_location
);
3114 void parse_if (source_location
);
3115 void parse_predicates (source_location
);
3116 void parse_operator_list (source_location
);
3119 vec
<c_expr
*> active_ifs
;
3120 vec
<vec
<user_id
*> > active_fors
;
3121 hash_set
<user_id
*> *oper_lists_set
;
3122 vec
<user_id
*> oper_lists
;
3124 cid_map_t
*capture_ids
;
3127 vec
<simplify
*> simplifiers
;
3128 vec
<predicate_id
*> user_predicates
;
3129 bool parsing_match_operand
;
3132 /* Lexing helpers. */
3134 /* Read the next non-whitespace token from R. */
3139 const cpp_token
*token
;
3142 token
= cpp_get_token (r
);
3144 while (token
->type
== CPP_PADDING
3145 && token
->type
!= CPP_EOF
);
3149 /* Peek at the next non-whitespace token from R. */
3152 parser::peek (unsigned num
)
3154 const cpp_token
*token
;
3158 token
= cpp_peek_token (r
, i
++);
3160 while ((token
->type
== CPP_PADDING
3161 && token
->type
!= CPP_EOF
)
3163 /* If we peek at EOF this is a fatal error as it leaves the
3164 cpp_reader in unusable state. Assume we really wanted a
3165 token and thus this EOF is unexpected. */
3166 if (token
->type
== CPP_EOF
)
3167 fatal_at (token
, "unexpected end of file");
3171 /* Peek at the next identifier token (or return NULL if the next
3172 token is not an identifier or equal to ID if supplied). */
3175 parser::peek_ident (const char *id
, unsigned num
)
3177 const cpp_token
*token
= peek (num
);
3178 if (token
->type
!= CPP_NAME
)
3184 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3185 if (strcmp (id
, t
) == 0)
3191 /* Read the next token from R and assert it is of type TK. */
3194 parser::expect (enum cpp_ttype tk
)
3196 const cpp_token
*token
= next ();
3197 if (token
->type
!= tk
)
3198 fatal_at (token
, "expected %s, got %s",
3199 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3204 /* Consume the next token from R and assert it is of type TK. */
3207 parser::eat_token (enum cpp_ttype tk
)
3212 /* Read the next token from R and assert it is of type CPP_STRING and
3213 return its value. */
3216 parser::get_string ()
3218 const cpp_token
*token
= expect (CPP_STRING
);
3219 return (const char *)token
->val
.str
.text
;
3222 /* Read the next token from R and assert it is of type CPP_NAME and
3223 return its value. */
3226 parser::get_ident ()
3228 const cpp_token
*token
= expect (CPP_NAME
);
3229 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3232 /* Eat an identifier token with value S from R. */
3235 parser::eat_ident (const char *s
)
3237 const cpp_token
*token
= peek ();
3238 const char *t
= get_ident ();
3239 if (strcmp (s
, t
) != 0)
3240 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3244 /* Read the next token from R and assert it is of type CPP_NUMBER and
3245 return its value. */
3248 parser::get_number ()
3250 const cpp_token
*token
= expect (CPP_NUMBER
);
3251 return (const char *)token
->val
.str
.text
;
3255 /* Record an operator-list use for transparent for handling. */
3258 parser::record_operlist (source_location loc
, user_id
*p
)
3260 if (!oper_lists_set
->add (p
))
3262 if (!oper_lists
.is_empty ()
3263 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3264 fatal_at (loc
, "User-defined operator list does not have the "
3265 "same number of entries as others used in the pattern");
3266 oper_lists
.safe_push (p
);
3270 /* Parse the operator ID, special-casing convert?, convert1? and
3274 parser::parse_operation ()
3276 const cpp_token
*id_tok
= peek ();
3277 const char *id
= get_ident ();
3278 const cpp_token
*token
= peek ();
3279 if (strcmp (id
, "convert0") == 0)
3280 fatal_at (id_tok
, "use 'convert?' here");
3281 else if (strcmp (id
, "view_convert0") == 0)
3282 fatal_at (id_tok
, "use 'view_convert?' here");
3283 if (token
->type
== CPP_QUERY
3284 && !(token
->flags
& PREV_WHITE
))
3286 if (strcmp (id
, "convert") == 0)
3288 else if (strcmp (id
, "convert1") == 0)
3290 else if (strcmp (id
, "convert2") == 0)
3292 else if (strcmp (id
, "view_convert") == 0)
3293 id
= "view_convert0";
3294 else if (strcmp (id
, "view_convert1") == 0)
3296 else if (strcmp (id
, "view_convert2") == 0)
3299 fatal_at (id_tok
, "non-convert operator conditionalized");
3301 if (!parsing_match_operand
)
3302 fatal_at (id_tok
, "conditional convert can only be used in "
3303 "match expression");
3304 eat_token (CPP_QUERY
);
3306 else if (strcmp (id
, "convert1") == 0
3307 || strcmp (id
, "convert2") == 0
3308 || strcmp (id
, "view_convert1") == 0
3309 || strcmp (id
, "view_convert2") == 0)
3310 fatal_at (id_tok
, "expected '?' after conditional operator");
3311 id_base
*op
= get_operator (id
);
3313 fatal_at (id_tok
, "unknown operator %s", id
);
3315 user_id
*p
= dyn_cast
<user_id
*> (op
);
3316 if (p
&& p
->is_oper_list
)
3318 if (active_fors
.length() == 0)
3319 record_operlist (id_tok
->src_loc
, p
);
3321 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3327 capture = '@'<number> */
3330 parser::parse_capture (operand
*op
)
3332 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3333 const cpp_token
*token
= peek ();
3334 const char *id
= NULL
;
3335 if (token
->type
== CPP_NUMBER
)
3337 else if (token
->type
== CPP_NAME
)
3340 fatal_at (token
, "expected number or identifier");
3341 unsigned next_id
= capture_ids
->elements ();
3343 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3346 return new capture (src_loc
, num
, op
);
3349 /* Parse an expression
3350 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3353 parser::parse_expr ()
3355 const cpp_token
*token
= peek ();
3356 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3359 bool is_commutative
= false;
3360 bool force_capture
= false;
3361 const char *expr_type
= NULL
;
3363 if (token
->type
== CPP_COLON
3364 && !(token
->flags
& PREV_WHITE
))
3366 eat_token (CPP_COLON
);
3368 if (token
->type
== CPP_NAME
3369 && !(token
->flags
& PREV_WHITE
))
3371 const char *s
= get_ident ();
3372 if (!parsing_match_operand
)
3380 is_commutative
= true;
3381 else if (*sp
== 's')
3383 e
->force_single_use
= true;
3384 force_capture
= true;
3387 fatal_at (token
, "flag %c not recognized", *sp
);
3394 fatal_at (token
, "expected flag or type specifying identifier");
3397 if (token
->type
== CPP_ATSIGN
3398 && !(token
->flags
& PREV_WHITE
))
3399 op
= parse_capture (e
);
3400 else if (force_capture
)
3402 unsigned num
= capture_ids
->elements ();
3405 sprintf (id
, "__%u", num
);
3406 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3408 fatal_at (token
, "reserved capture id '%s' already used", id
);
3409 op
= new capture (token
->src_loc
, num
, e
);
3415 const cpp_token
*token
= peek ();
3416 if (token
->type
== CPP_CLOSE_PAREN
)
3418 if (e
->operation
->nargs
!= -1
3419 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3420 fatal_at (token
, "'%s' expects %u operands, not %u",
3421 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3424 if (e
->ops
.length () == 2)
3425 e
->is_commutative
= true;
3427 fatal_at (token
, "only binary operators or function with "
3428 "two arguments can be marked commutative");
3430 e
->expr_type
= expr_type
;
3433 e
->append_op (parse_op ());
3438 /* Lex native C code delimited by START recording the preprocessing tokens
3439 for later processing.
3440 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3443 parser::parse_c_expr (cpp_ttype start
)
3445 const cpp_token
*token
;
3448 vec
<cpp_token
> code
= vNULL
;
3449 unsigned nr_stmts
= 0;
3450 source_location loc
= eat_token (start
)->src_loc
;
3451 if (start
== CPP_OPEN_PAREN
)
3452 end
= CPP_CLOSE_PAREN
;
3453 else if (start
== CPP_OPEN_BRACE
)
3454 end
= CPP_CLOSE_BRACE
;
3462 /* Count brace pairs to find the end of the expr to match. */
3463 if (token
->type
== start
)
3465 else if (token
->type
== end
3469 /* This is a lame way of counting the number of statements. */
3470 if (token
->type
== CPP_SEMICOLON
)
3473 /* If this is possibly a user-defined identifier mark it used. */
3474 if (token
->type
== CPP_NAME
)
3476 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3477 (token
->val
.node
.node
)->ident
.str
);
3479 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3480 record_operlist (token
->src_loc
, p
);
3483 /* Record the token. */
3484 code
.safe_push (*token
);
3487 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3490 /* Parse an operand which is either an expression, a predicate or
3491 a standalone capture.
3492 op = predicate | expr | c_expr | capture */
3497 const cpp_token
*token
= peek ();
3498 struct operand
*op
= NULL
;
3499 if (token
->type
== CPP_OPEN_PAREN
)
3501 eat_token (CPP_OPEN_PAREN
);
3503 eat_token (CPP_CLOSE_PAREN
);
3505 else if (token
->type
== CPP_OPEN_BRACE
)
3507 op
= parse_c_expr (CPP_OPEN_BRACE
);
3511 /* Remaining ops are either empty or predicates */
3512 if (token
->type
== CPP_NAME
)
3514 const char *id
= get_ident ();
3515 id_base
*opr
= get_operator (id
);
3517 fatal_at (token
, "expected predicate name");
3518 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3520 if (code
->nargs
!= 0)
3521 fatal_at (token
, "using an operator with operands as predicate");
3522 /* Parse the zero-operand operator "predicates" as
3524 op
= new expr (opr
, token
->src_loc
);
3526 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3528 if (code
->nargs
!= 0)
3529 fatal_at (token
, "using an operator with operands as predicate");
3530 /* Parse the zero-operand operator "predicates" as
3532 op
= new expr (opr
, token
->src_loc
);
3534 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3535 op
= new predicate (p
, token
->src_loc
);
3537 fatal_at (token
, "using an unsupported operator as predicate");
3538 if (!parsing_match_operand
)
3539 fatal_at (token
, "predicates are only allowed in match expression");
3541 if (token
->flags
& PREV_WHITE
)
3544 else if (token
->type
!= CPP_COLON
3545 && token
->type
!= CPP_ATSIGN
)
3546 fatal_at (token
, "expected expression or predicate");
3547 /* optionally followed by a capture and a predicate. */
3548 if (token
->type
== CPP_COLON
)
3549 fatal_at (token
, "not implemented: predicate on leaf operand");
3550 if (token
->type
== CPP_ATSIGN
)
3551 op
= parse_capture (op
);
3557 /* Create a new simplify from the current parsing state and MATCH,
3558 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3561 parser::push_simplify (simplify::simplify_kind kind
,
3562 vec
<simplify
*>& simplifiers
,
3563 operand
*match
, operand
*result
)
3565 /* Build and push a temporary for operator list uses in expressions. */
3566 if (!oper_lists
.is_empty ())
3567 active_fors
.safe_push (oper_lists
);
3569 simplifiers
.safe_push
3570 (new simplify (kind
, match
, result
,
3571 active_fors
.copy (), capture_ids
));
3573 if (!oper_lists
.is_empty ())
3578 <result-op> = <op> | <if> | <with>
3579 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3580 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3584 parser::parse_result (operand
*result
, predicate_id
*matcher
)
3586 const cpp_token
*token
= peek ();
3587 if (token
->type
!= CPP_OPEN_PAREN
)
3590 eat_token (CPP_OPEN_PAREN
);
3591 if (peek_ident ("if"))
3594 if_expr
*ife
= new if_expr (token
->src_loc
);
3595 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3596 if (peek ()->type
== CPP_OPEN_PAREN
)
3598 ife
->trueexpr
= parse_result (result
, matcher
);
3599 if (peek ()->type
== CPP_OPEN_PAREN
)
3600 ife
->falseexpr
= parse_result (result
, matcher
);
3601 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3602 ife
->falseexpr
= parse_op ();
3604 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3606 ife
->trueexpr
= parse_op ();
3607 if (peek ()->type
== CPP_OPEN_PAREN
)
3608 ife
->falseexpr
= parse_result (result
, matcher
);
3609 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
3610 ife
->falseexpr
= parse_op ();
3612 /* If this if is immediately closed then it contains a
3613 manual matcher or is part of a predicate definition. */
3614 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
3617 fatal_at (peek (), "manual transform not implemented");
3618 ife
->trueexpr
= result
;
3620 eat_token (CPP_CLOSE_PAREN
);
3623 else if (peek_ident ("with"))
3626 with_expr
*withe
= new with_expr (token
->src_loc
);
3627 /* Parse (with c-expr expr) as (if-with (true) expr). */
3628 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
3629 withe
->with
->nr_stmts
= 0;
3630 withe
->subexpr
= parse_result (result
, matcher
);
3631 eat_token (CPP_CLOSE_PAREN
);
3634 else if (peek_ident ("switch"))
3636 token
= eat_ident ("switch");
3637 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
3639 if_expr
*ife
= new if_expr (ifloc
);
3641 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3642 if (peek ()->type
== CPP_OPEN_PAREN
)
3643 ife
->trueexpr
= parse_result (result
, matcher
);
3645 ife
->trueexpr
= parse_op ();
3646 eat_token (CPP_CLOSE_PAREN
);
3647 if (peek ()->type
!= CPP_OPEN_PAREN
3648 || !peek_ident ("if", 2))
3649 fatal_at (token
, "switch can be implemented with a single if");
3650 while (peek ()->type
!= CPP_CLOSE_PAREN
)
3652 if (peek ()->type
== CPP_OPEN_PAREN
)
3654 if (peek_ident ("if", 2))
3656 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
3658 ife
->falseexpr
= new if_expr (ifloc
);
3659 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
3660 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
3661 if (peek ()->type
== CPP_OPEN_PAREN
)
3662 ife
->trueexpr
= parse_result (result
, matcher
);
3664 ife
->trueexpr
= parse_op ();
3665 eat_token (CPP_CLOSE_PAREN
);
3669 /* switch default clause */
3670 ife
->falseexpr
= parse_result (result
, matcher
);
3671 eat_token (CPP_CLOSE_PAREN
);
3677 /* switch default clause */
3678 ife
->falseexpr
= parse_op ();
3679 eat_token (CPP_CLOSE_PAREN
);
3683 eat_token (CPP_CLOSE_PAREN
);
3688 operand
*op
= result
;
3691 eat_token (CPP_CLOSE_PAREN
);
3697 simplify = 'simplify' <expr> <result-op>
3699 match = 'match' <ident> <expr> [<result-op>]
3700 and fill SIMPLIFIERS with the results. */
3703 parser::parse_simplify (simplify::simplify_kind kind
,
3704 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3707 /* Reset the capture map. */
3709 capture_ids
= new cid_map_t
;
3710 /* Reset oper_lists and set. */
3711 hash_set
<user_id
*> olist
;
3712 oper_lists_set
= &olist
;
3715 const cpp_token
*loc
= peek ();
3716 parsing_match_operand
= true;
3717 struct operand
*match
= parse_op ();
3718 parsing_match_operand
= false;
3719 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3720 fatal_at (loc
, "outermost expression cannot be captured");
3721 if (match
->type
== operand::OP_EXPR
3722 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3723 fatal_at (loc
, "outermost expression cannot be a predicate");
3725 /* Splice active_ifs onto result and continue parsing the
3727 if_expr
*active_if
= NULL
;
3728 for (int i
= active_ifs
.length (); i
> 0; --i
)
3730 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
3731 ifc
->cond
= active_ifs
[i
-1];
3732 ifc
->trueexpr
= active_if
;
3735 if_expr
*outermost_if
= active_if
;
3736 while (active_if
&& active_if
->trueexpr
)
3737 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
3739 const cpp_token
*token
= peek ();
3741 /* If this if is immediately closed then it is part of a predicate
3742 definition. Push it. */
3743 if (token
->type
== CPP_CLOSE_PAREN
)
3746 fatal_at (token
, "expected transform expression");
3749 active_if
->trueexpr
= result
;
3750 result
= outermost_if
;
3752 push_simplify (kind
, simplifiers
, match
, result
);
3756 operand
*tem
= parse_result (result
, matcher
);
3759 active_if
->trueexpr
= tem
;
3760 result
= outermost_if
;
3765 push_simplify (kind
, simplifiers
, match
, result
);
3768 /* Parsing of the outer control structures. */
3770 /* Parse a for expression
3771 for = '(' 'for' <subst>... <pattern> ')'
3772 subst = <ident> '(' <ident>... ')' */
3775 parser::parse_for (source_location
)
3777 auto_vec
<const cpp_token
*> user_id_tokens
;
3778 vec
<user_id
*> user_ids
= vNULL
;
3779 const cpp_token
*token
;
3780 unsigned min_n_opers
= 0, max_n_opers
= 0;
3785 if (token
->type
!= CPP_NAME
)
3788 /* Insert the user defined operators into the operator hash. */
3789 const char *id
= get_ident ();
3790 if (get_operator (id
) != NULL
)
3791 fatal_at (token
, "operator already defined");
3792 user_id
*op
= new user_id (id
);
3793 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3795 user_ids
.safe_push (op
);
3796 user_id_tokens
.safe_push (token
);
3798 eat_token (CPP_OPEN_PAREN
);
3801 while ((token
= peek_ident ()) != 0)
3803 const char *oper
= get_ident ();
3804 id_base
*idb
= get_operator (oper
);
3806 fatal_at (token
, "no such operator '%s'", oper
);
3807 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3808 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3809 || *idb
== VIEW_CONVERT2
)
3810 fatal_at (token
, "conditional operators cannot be used inside for");
3814 else if (idb
->nargs
== -1)
3816 else if (idb
->nargs
!= arity
)
3817 fatal_at (token
, "operator '%s' with arity %d does not match "
3818 "others with arity %d", oper
, idb
->nargs
, arity
);
3820 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3823 if (p
->is_oper_list
)
3824 op
->substitutes
.safe_splice (p
->substitutes
);
3826 fatal_at (token
, "iterator cannot be used as operator-list");
3829 op
->substitutes
.safe_push (idb
);
3832 token
= expect (CPP_CLOSE_PAREN
);
3834 unsigned nsubstitutes
= op
->substitutes
.length ();
3835 if (nsubstitutes
== 0)
3836 fatal_at (token
, "A user-defined operator must have at least "
3837 "one substitution");
3838 if (max_n_opers
== 0)
3840 min_n_opers
= nsubstitutes
;
3841 max_n_opers
= nsubstitutes
;
3845 if (nsubstitutes
% min_n_opers
!= 0
3846 && min_n_opers
% nsubstitutes
!= 0)
3847 fatal_at (token
, "All user-defined identifiers must have a "
3848 "multiple number of operator substitutions of the "
3849 "smallest number of substitutions");
3850 if (nsubstitutes
< min_n_opers
)
3851 min_n_opers
= nsubstitutes
;
3852 else if (nsubstitutes
> max_n_opers
)
3853 max_n_opers
= nsubstitutes
;
3857 unsigned n_ids
= user_ids
.length ();
3859 fatal_at (token
, "for requires at least one user-defined identifier");
3862 if (token
->type
== CPP_CLOSE_PAREN
)
3863 fatal_at (token
, "no pattern defined in for");
3865 active_fors
.safe_push (user_ids
);
3869 if (token
->type
== CPP_CLOSE_PAREN
)
3875 /* Remove user-defined operators from the hash again. */
3876 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3878 if (!user_ids
[i
]->used
)
3879 warning_at (user_id_tokens
[i
],
3880 "operator %s defined but not used", user_ids
[i
]->id
);
3881 operators
->remove_elt (user_ids
[i
]);
3885 /* Parse an identifier associated with a list of operators.
3886 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3889 parser::parse_operator_list (source_location
)
3891 const cpp_token
*token
= peek ();
3892 const char *id
= get_ident ();
3894 if (get_operator (id
) != 0)
3895 fatal_at (token
, "operator %s already defined", id
);
3897 user_id
*op
= new user_id (id
, true);
3900 while ((token
= peek_ident ()) != 0)
3903 const char *oper
= get_ident ();
3904 id_base
*idb
= get_operator (oper
);
3907 fatal_at (token
, "no such operator '%s'", oper
);
3911 else if (idb
->nargs
== -1)
3913 else if (arity
!= idb
->nargs
)
3914 fatal_at (token
, "operator '%s' with arity %d does not match "
3915 "others with arity %d", oper
, idb
->nargs
, arity
);
3917 /* We allow composition of multiple operator lists. */
3918 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3919 op
->substitutes
.safe_splice (p
->substitutes
);
3921 op
->substitutes
.safe_push (idb
);
3924 // Check that there is no junk after id-list
3926 if (token
->type
!= CPP_CLOSE_PAREN
)
3927 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3929 if (op
->substitutes
.length () == 0)
3930 fatal_at (token
, "operator-list cannot be empty");
3933 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3937 /* Parse an outer if expression.
3938 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3941 parser::parse_if (source_location
)
3943 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3945 const cpp_token
*token
= peek ();
3946 if (token
->type
== CPP_CLOSE_PAREN
)
3947 fatal_at (token
, "no pattern defined in if");
3949 active_ifs
.safe_push (ifexpr
);
3952 const cpp_token
*token
= peek ();
3953 if (token
->type
== CPP_CLOSE_PAREN
)
3961 /* Parse a list of predefined predicate identifiers.
3962 preds = '(' 'define_predicates' <ident>... ')' */
3965 parser::parse_predicates (source_location
)
3969 const cpp_token
*token
= peek ();
3970 if (token
->type
!= CPP_NAME
)
3973 add_predicate (get_ident ());
3978 /* Parse outer control structures.
3979 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3982 parser::parse_pattern ()
3984 /* All clauses start with '('. */
3985 eat_token (CPP_OPEN_PAREN
);
3986 const cpp_token
*token
= peek ();
3987 const char *id
= get_ident ();
3988 if (strcmp (id
, "simplify") == 0)
3990 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
3993 else if (strcmp (id
, "match") == 0)
3995 bool with_args
= false;
3996 source_location e_loc
= peek ()->src_loc
;
3997 if (peek ()->type
== CPP_OPEN_PAREN
)
3999 eat_token (CPP_OPEN_PAREN
);
4002 const char *name
= get_ident ();
4003 id_base
*id
= get_operator (name
);
4007 p
= add_predicate (name
);
4008 user_predicates
.safe_push (p
);
4010 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4013 fatal_at (token
, "cannot add a match to a non-predicate ID");
4014 /* Parse (match <id> <arg>... (match-expr)) here. */
4018 capture_ids
= new cid_map_t
;
4019 e
= new expr (p
, e_loc
);
4020 while (peek ()->type
== CPP_ATSIGN
)
4021 e
->append_op (parse_capture (NULL
));
4022 eat_token (CPP_CLOSE_PAREN
);
4025 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4026 || (!e
&& p
->nargs
!= 0)))
4027 fatal_at (token
, "non-matching number of match operands");
4028 p
->nargs
= e
? e
->ops
.length () : 0;
4029 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4032 else if (strcmp (id
, "for") == 0)
4033 parse_for (token
->src_loc
);
4034 else if (strcmp (id
, "if") == 0)
4035 parse_if (token
->src_loc
);
4036 else if (strcmp (id
, "define_predicates") == 0)
4038 if (active_ifs
.length () > 0
4039 || active_fors
.length () > 0)
4040 fatal_at (token
, "define_predicates inside if or for is not supported");
4041 parse_predicates (token
->src_loc
);
4043 else if (strcmp (id
, "define_operator_list") == 0)
4045 if (active_ifs
.length () > 0
4046 || active_fors
.length () > 0)
4047 fatal_at (token
, "operator-list inside if or for is not supported");
4048 parse_operator_list (token
->src_loc
);
4051 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4052 active_ifs
.length () == 0 && active_fors
.length () == 0
4053 ? "'define_predicates', " : "");
4055 eat_token (CPP_CLOSE_PAREN
);
4058 /* Main entry of the parser. Repeatedly parse outer control structures. */
4060 parser::parser (cpp_reader
*r_
)
4064 active_fors
= vNULL
;
4065 simplifiers
= vNULL
;
4066 oper_lists_set
= NULL
;
4069 user_predicates
= vNULL
;
4070 parsing_match_operand
= false;
4072 const cpp_token
*token
= next ();
4073 while (token
->type
!= CPP_EOF
)
4075 _cpp_backup_tokens (r
, 1);
4082 /* Helper for the linemap code. */
4085 round_alloc_size (size_t s
)
4091 /* The genmatch generator progam. It reads from a pattern description
4092 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4095 main (int argc
, char **argv
)
4099 progname
= "genmatch";
4105 bool verbose
= false;
4106 char *input
= argv
[argc
-1];
4107 for (int i
= 1; i
< argc
- 1; ++i
)
4109 if (strcmp (argv
[i
], "--gimple") == 0)
4111 else if (strcmp (argv
[i
], "--generic") == 0)
4113 else if (strcmp (argv
[i
], "-v") == 0)
4117 fprintf (stderr
, "Usage: genmatch "
4118 "[--gimple] [--generic] [-v] input\n");
4123 line_table
= XCNEW (struct line_maps
);
4124 linemap_init (line_table
, 0);
4125 line_table
->reallocator
= xrealloc
;
4126 line_table
->round_alloc_size
= round_alloc_size
;
4128 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4129 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4130 cb
->error
= error_cb
;
4132 if (!cpp_read_main_file (r
, input
))
4134 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4135 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4137 /* Pre-seed operators. */
4138 operators
= new hash_table
<id_base
> (1024);
4139 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4140 add_operator (SYM, # SYM, # TYPE, NARGS);
4141 #define END_OF_BASE_TREE_CODES
4143 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4144 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4145 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4146 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4147 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4148 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4149 #undef END_OF_BASE_TREE_CODES
4152 /* Pre-seed builtin functions.
4153 ??? Cannot use N (name) as that is targetm.emultls.get_address
4154 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4155 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4156 add_builtin (ENUM, # ENUM);
4157 #include "builtins.def"
4164 write_header (stdout
, "gimple-match-head.c");
4166 write_header (stdout
, "generic-match-head.c");
4168 /* Go over all predicates defined with patterns and perform
4169 lowering and code generation. */
4170 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4172 predicate_id
*pred
= p
.user_predicates
[i
];
4173 lower (pred
->matchers
, gimple
);
4176 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4177 print_matches (pred
->matchers
[i
]);
4180 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4181 dt
.insert (pred
->matchers
[i
], i
);
4186 write_predicate (stdout
, pred
, dt
, gimple
);
4189 /* Lower the main simplifiers and generate code for them. */
4190 lower (p
.simplifiers
, gimple
);
4193 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4194 print_matches (p
.simplifiers
[i
]);
4197 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4198 dt
.insert (p
.simplifiers
[i
], i
);
4204 dt
.gen_gimple (stdout
);
4206 dt
.gen_generic (stdout
);
4209 cpp_finish (r
, NULL
);