1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2015 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
30 #include "hash-table.h"
35 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
36 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
37 size_t, size_t MEM_STAT_DECL
)
41 void ggc_free (void *)
48 static struct line_maps
*line_table
;
51 #if GCC_VERSION >= 4001
52 __attribute__((format (printf
, 6, 0)))
54 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
55 unsigned int, const char *msg
, va_list *ap
)
57 const line_map_ordinary
*map
;
58 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
59 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
60 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
61 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
62 vfprintf (stderr
, msg
, *ap
);
63 fprintf (stderr
, "\n");
64 FILE *f
= fopen (loc
.file
, "r");
70 if (!fgets (buf
, 128, f
))
72 if (buf
[strlen (buf
) - 1] != '\n')
79 fprintf (stderr
, "%s", buf
);
80 for (int i
= 0; i
< loc
.column
- 1; ++i
)
88 if (errtype
== CPP_DL_FATAL
)
94 #if GCC_VERSION >= 4001
95 __attribute__((format (printf
, 2, 3)))
97 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
101 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
106 #if GCC_VERSION >= 4001
107 __attribute__((format (printf
, 2, 3)))
109 fatal_at (source_location loc
, const char *msg
, ...)
113 error_cb (NULL
, CPP_DL_FATAL
, 0, loc
, 0, msg
, &ap
);
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 warning_at (const cpp_token
*tk
, const char *msg
, ...)
125 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
130 output_line_directive (FILE *f
, source_location location
,
131 bool dumpfile
= false)
133 const line_map_ordinary
*map
;
134 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
135 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
138 /* When writing to a dumpfile only dump the filename. */
139 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
144 fprintf (f
, "%s:%d", file
, loc
.line
);
147 /* Other gen programs really output line directives here, at least for
148 development it's right now more convenient to have line information
149 from the generated file. Still keep the directives as comment for now
150 to easily back-point to the meta-description. */
151 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
155 /* Pull in tree codes and builtin function codes from their
158 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
171 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
172 enum built_in_function
{
173 #include "builtins.def"
179 /* Base class for all identifiers the parser knows. */
181 struct id_base
: typed_noop_remove
<id_base
>
183 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
185 id_base (id_kind
, const char *, int = -1);
191 /* hash_table support. */
192 typedef id_base
*value_type
;
193 typedef id_base
*compare_type
;
194 static inline hashval_t
hash (const id_base
*);
195 static inline int equal (const id_base
*, const id_base
*);
199 id_base::hash (const id_base
*op
)
205 id_base::equal (const id_base
*op1
,
208 return (op1
->hashval
== op2
->hashval
209 && strcmp (op1
->id
, op2
->id
) == 0);
212 /* Hashtable of known pattern operators. This is pre-seeded from
213 all known tree codes and all known builtin function ids. */
214 static hash_table
<id_base
> *operators
;
216 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
221 hashval
= htab_hash_string (id
);
224 /* Identifier that maps to a tree code. */
226 struct operator_id
: public id_base
228 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
230 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
235 /* Identifier that maps to a builtin function code. */
237 struct fn_id
: public id_base
239 fn_id (enum built_in_function fn_
, const char *id_
)
240 : id_base (id_base::FN
, id_
), fn (fn_
) {}
241 enum built_in_function fn
;
246 /* Identifier that maps to a user-defined predicate. */
248 struct predicate_id
: public id_base
250 predicate_id (const char *id_
)
251 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
252 vec
<simplify
*> matchers
;
255 /* Identifier that maps to a operator defined by a 'for' directive. */
257 struct user_id
: public id_base
259 user_id (const char *id_
, bool is_oper_list_
= false)
260 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
261 used (false), is_oper_list (is_oper_list_
) {}
262 vec
<id_base
*> substitutes
;
270 is_a_helper
<fn_id
*>::test (id_base
*id
)
272 return id
->kind
== id_base::FN
;
278 is_a_helper
<operator_id
*>::test (id_base
*id
)
280 return id
->kind
== id_base::CODE
;
286 is_a_helper
<predicate_id
*>::test (id_base
*id
)
288 return id
->kind
== id_base::PREDICATE
;
294 is_a_helper
<user_id
*>::test (id_base
*id
)
296 return id
->kind
== id_base::USER
;
299 /* Add a predicate identifier to the hash. */
301 static predicate_id
*
302 add_predicate (const char *id
)
304 predicate_id
*p
= new predicate_id (id
);
305 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
307 fatal ("duplicate id definition");
312 /* Add a tree code identifier to the hash. */
315 add_operator (enum tree_code code
, const char *id
,
316 const char *tcc
, unsigned nargs
)
318 if (strcmp (tcc
, "tcc_unary") != 0
319 && strcmp (tcc
, "tcc_binary") != 0
320 && strcmp (tcc
, "tcc_comparison") != 0
321 && strcmp (tcc
, "tcc_expression") != 0
322 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
323 && strcmp (tcc
, "tcc_reference") != 0
324 /* To have INTEGER_CST and friends as "predicate operators". */
325 && strcmp (tcc
, "tcc_constant") != 0
326 /* And allow CONSTRUCTOR for vector initializers. */
327 && !(code
== CONSTRUCTOR
))
329 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
330 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
332 fatal ("duplicate id definition");
336 /* Add a builtin identifier to the hash. */
339 add_builtin (enum built_in_function code
, const char *id
)
341 fn_id
*fn
= new fn_id (code
, id
);
342 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
344 fatal ("duplicate id definition");
348 /* Helper for easy comparing ID with tree code CODE. */
351 operator==(id_base
&id
, enum tree_code code
)
353 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
354 return oid
->code
== code
;
358 /* Lookup the identifier ID. */
361 get_operator (const char *id
)
363 id_base
tem (id_base::CODE
, id
);
365 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
368 /* If this is a user-defined identifier track whether it was used. */
369 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
374 /* Try all-uppercase. */
375 char *id2
= xstrdup (id
);
376 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
377 id2
[i
] = TOUPPER (id2
[i
]);
378 new (&tem
) id_base (id_base::CODE
, id2
);
379 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
386 /* Try _EXPR appended. */
387 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
388 strcat (id2
, "_EXPR");
389 new (&tem
) id_base (id_base::CODE
, id2
);
390 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
401 /* Helper for the capture-id map. */
403 struct capture_id_map_hasher
: default_hashmap_traits
405 static inline hashval_t
hash (const char *);
406 static inline bool equal_keys (const char *, const char *);
410 capture_id_map_hasher::hash (const char *id
)
412 return htab_hash_string (id
);
416 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
418 return strcmp (id1
, id2
) == 0;
421 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
424 /* The AST produced by parsing of the pattern definitions. */
429 /* The base class for operands. */
432 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
433 operand (enum op_type type_
) : type (type_
) {}
435 virtual void gen_transform (FILE *, const char *, bool, int,
436 const char *, capture_info
*,
439 { gcc_unreachable (); }
442 /* A predicate operand. Predicates are leafs in the AST. */
444 struct predicate
: public operand
446 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
450 /* An operand that constitutes an expression. Expressions include
451 function calls and user-defined predicate invocations. */
453 struct expr
: public operand
455 expr (id_base
*operation_
, bool is_commutative_
= false)
456 : operand (OP_EXPR
), operation (operation_
),
457 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
458 is_generic (false) {}
459 void append_op (operand
*op
) { ops
.safe_push (op
); }
460 /* The operator and its operands. */
463 /* An explicitely specified type - used exclusively for conversions. */
464 const char *expr_type
;
465 /* Whether the operation is to be applied commutatively. This is
466 later lowered to two separate patterns. */
468 /* Whether the expression is expected to be in GENERIC form. */
470 virtual void gen_transform (FILE *f
, const char *, bool, int,
471 const char *, capture_info
*,
472 dt_operand
** = 0, bool = true);
475 /* An operator that is represented by native C code. This is always
476 a leaf operand in the AST. This class is also used to represent
477 the code to be generated for 'if' and 'with' expressions. */
479 struct c_expr
: public operand
481 /* A mapping of an identifier and its replacement. Used to apply
486 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
489 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
490 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
491 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
492 nr_stmts (nr_stmts_
), ids (ids_
) {}
493 /* cpplib tokens and state to transform this back to source. */
496 cid_map_t
*capture_ids
;
497 /* The number of statements parsed (well, the number of ';'s). */
499 /* The identifier replacement vector. */
501 virtual void gen_transform (FILE *f
, const char *, bool, int,
502 const char *, capture_info
*,
503 dt_operand
** = 0, bool = true);
506 /* A wrapper around another operand that captures its value. */
508 struct capture
: public operand
510 capture (unsigned where_
, operand
*what_
)
511 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
512 /* Identifier index for the value. */
514 /* The captured value. */
516 virtual void gen_transform (FILE *f
, const char *, bool, int,
517 const char *, capture_info
*,
518 dt_operand
** = 0, bool = true);
524 is_a_helper
<capture
*>::test (operand
*op
)
526 return op
->type
== operand::OP_CAPTURE
;
532 is_a_helper
<predicate
*>::test (operand
*op
)
534 return op
->type
== operand::OP_PREDICATE
;
540 is_a_helper
<c_expr
*>::test (operand
*op
)
542 return op
->type
== operand::OP_C_EXPR
;
548 is_a_helper
<expr
*>::test (operand
*op
)
550 return op
->type
== operand::OP_EXPR
;
553 /* Helper to distinguish 'if' from 'with' expressions. */
557 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
558 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
559 source_location location
;
564 /* The main class of a pattern and its transform. This is used to
565 represent both (simplify ...) and (match ...) kinds. The AST
566 duplicates all outer 'if' and 'for' expressions here so each
567 simplify can exist in isolation. */
571 simplify (operand
*match_
, source_location match_location_
,
572 struct operand
*result_
, source_location result_location_
,
573 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
574 cid_map_t
*capture_ids_
)
575 : match (match_
), match_location (match_location_
),
576 result (result_
), result_location (result_location_
),
577 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
578 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
580 /* The expression that is matched against the GENERIC or GIMPLE IL. */
582 source_location match_location
;
583 /* For a (simplify ...) the expression produced when the pattern applies.
584 For a (match ...) either NULL if it is a simple predicate or the
585 single expression specifying the matched operands. */
586 struct operand
*result
;
587 source_location result_location
;
588 /* Collected 'if' expressions that need to evaluate to true to make
589 the pattern apply. */
590 vec
<if_or_with
> ifexpr_vec
;
591 /* Collected 'for' expression operators that have to be replaced
592 in the lowering phase. */
593 vec
<vec
<user_id
*> > for_vec
;
594 /* A map of capture identifiers to indexes. */
595 cid_map_t
*capture_ids
;
599 /* Debugging routines for dumping the AST. */
602 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
604 if (capture
*c
= dyn_cast
<capture
*> (o
))
606 fprintf (f
, "@%u", c
->where
);
607 if (c
->what
&& flattened
== false)
610 print_operand (c
->what
, f
, flattened
);
615 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
616 fprintf (f
, "%s", p
->p
->id
);
618 else if (is_a
<c_expr
*> (o
))
619 fprintf (f
, "c_expr");
621 else if (expr
*e
= dyn_cast
<expr
*> (o
))
623 fprintf (f
, "(%s", e
->operation
->id
);
625 if (flattened
== false)
628 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
630 print_operand (e
->ops
[i
], f
, flattened
);
642 print_matches (struct simplify
*s
, FILE *f
= stderr
)
644 fprintf (f
, "for expression: ");
645 print_operand (s
->match
, f
);
652 /* Lowering of commutative operators. */
655 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
656 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
658 if (n
== ops_vector
.length ())
660 vec
<operand
*> xv
= v
.copy ();
661 result
.safe_push (xv
);
665 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
667 v
[n
] = ops_vector
[n
][i
];
668 cartesian_product (ops_vector
, result
, v
, n
+ 1);
672 /* Lower OP to two operands in case it is marked as commutative. */
674 static vec
<operand
*>
675 commutate (operand
*op
)
677 vec
<operand
*> ret
= vNULL
;
679 if (capture
*c
= dyn_cast
<capture
*> (op
))
686 vec
<operand
*> v
= commutate (c
->what
);
687 for (unsigned i
= 0; i
< v
.length (); ++i
)
689 capture
*nc
= new capture (c
->where
, v
[i
]);
695 expr
*e
= dyn_cast
<expr
*> (op
);
696 if (!e
|| e
->ops
.length () == 0)
702 vec
< vec
<operand
*> > ops_vector
= vNULL
;
703 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
704 ops_vector
.safe_push (commutate (e
->ops
[i
]));
706 auto_vec
< vec
<operand
*> > result
;
707 auto_vec
<operand
*> v (e
->ops
.length ());
708 v
.quick_grow_cleared (e
->ops
.length ());
709 cartesian_product (ops_vector
, result
, v
, 0);
712 for (unsigned i
= 0; i
< result
.length (); ++i
)
714 expr
*ne
= new expr (e
->operation
);
715 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
716 ne
->append_op (result
[i
][j
]);
720 if (!e
->is_commutative
)
723 for (unsigned i
= 0; i
< result
.length (); ++i
)
725 expr
*ne
= new expr (e
->operation
);
726 // result[i].length () is 2 since e->operation is binary
727 for (unsigned j
= result
[i
].length (); j
; --j
)
728 ne
->append_op (result
[i
][j
-1]);
735 /* Lower operations marked as commutative in the AST of S and push
736 the resulting patterns to SIMPLIFIERS. */
739 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
741 vec
<operand
*> matchers
= commutate (s
->match
);
742 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
744 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
745 s
->result
, s
->result_location
, s
->ifexpr_vec
,
746 s
->for_vec
, s
->capture_ids
);
747 simplifiers
.safe_push (ns
);
751 /* Strip conditional conversios using operator OPER from O and its
752 children if STRIP, else replace them with an unconditional convert. */
755 lower_opt_convert (operand
*o
, enum tree_code oper
,
756 enum tree_code to_oper
, bool strip
)
758 if (capture
*c
= dyn_cast
<capture
*> (o
))
761 return new capture (c
->where
,
762 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
767 expr
*e
= dyn_cast
<expr
*> (o
);
771 if (*e
->operation
== oper
)
774 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
776 expr
*ne
= new expr (to_oper
== CONVERT_EXPR
777 ? get_operator ("CONVERT_EXPR")
778 : get_operator ("VIEW_CONVERT_EXPR"));
779 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
783 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
784 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
785 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
790 /* Determine whether O or its children uses the conditional conversion
794 has_opt_convert (operand
*o
, enum tree_code oper
)
796 if (capture
*c
= dyn_cast
<capture
*> (o
))
799 return has_opt_convert (c
->what
, oper
);
804 expr
*e
= dyn_cast
<expr
*> (o
);
808 if (*e
->operation
== oper
)
811 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
812 if (has_opt_convert (e
->ops
[i
], oper
))
818 /* Lower conditional convert operators in O, expanding it to a vector
821 static vec
<operand
*>
822 lower_opt_convert (operand
*o
)
824 vec
<operand
*> v1
= vNULL
, v2
;
828 enum tree_code opers
[]
829 = { CONVERT0
, CONVERT_EXPR
,
830 CONVERT1
, CONVERT_EXPR
,
831 CONVERT2
, CONVERT_EXPR
,
832 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
833 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
834 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
836 /* Conditional converts are lowered to a pattern with the
837 conversion and one without. The three different conditional
838 convert codes are lowered separately. */
840 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
843 for (unsigned j
= 0; j
< v1
.length (); ++j
)
844 if (has_opt_convert (v1
[j
], opers
[i
]))
846 v2
.safe_push (lower_opt_convert (v1
[j
],
847 opers
[i
], opers
[i
+1], false));
848 v2
.safe_push (lower_opt_convert (v1
[j
],
849 opers
[i
], opers
[i
+1], true));
855 for (unsigned j
= 0; j
< v2
.length (); ++j
)
856 v1
.safe_push (v2
[j
]);
863 /* Lower conditional convert operators in the AST of S and push
864 the resulting multiple patterns to SIMPLIFIERS. */
867 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
869 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
870 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
872 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
873 s
->result
, s
->result_location
, s
->ifexpr_vec
,
874 s
->for_vec
, s
->capture_ids
);
875 simplifiers
.safe_push (ns
);
879 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
880 GENERIC and a GIMPLE variant. */
882 static vec
<operand
*>
883 lower_cond (operand
*o
)
885 vec
<operand
*> ro
= vNULL
;
887 if (capture
*c
= dyn_cast
<capture
*> (o
))
891 vec
<operand
*> lop
= vNULL
;
892 lop
= lower_cond (c
->what
);
894 for (unsigned i
= 0; i
< lop
.length (); ++i
)
895 ro
.safe_push (new capture (c
->where
, lop
[i
]));
900 expr
*e
= dyn_cast
<expr
*> (o
);
901 if (!e
|| e
->ops
.length () == 0)
907 vec
< vec
<operand
*> > ops_vector
= vNULL
;
908 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
909 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
911 auto_vec
< vec
<operand
*> > result
;
912 auto_vec
<operand
*> v (e
->ops
.length ());
913 v
.quick_grow_cleared (e
->ops
.length ());
914 cartesian_product (ops_vector
, result
, v
, 0);
916 for (unsigned i
= 0; i
< result
.length (); ++i
)
918 expr
*ne
= new expr (e
->operation
);
919 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
920 ne
->append_op (result
[i
][j
]);
922 /* If this is a COND with a captured expression or an
923 expression with two operands then also match a GENERIC
924 form on the compare. */
925 if ((*e
->operation
== COND_EXPR
926 || *e
->operation
== VEC_COND_EXPR
)
927 && ((is_a
<capture
*> (e
->ops
[0])
928 && as_a
<capture
*> (e
->ops
[0])->what
929 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
931 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
932 || (is_a
<expr
*> (e
->ops
[0])
933 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
935 expr
*ne
= new expr (e
->operation
);
936 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
937 ne
->append_op (result
[i
][j
]);
938 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
940 expr
*ocmp
= as_a
<expr
*> (c
->what
);
941 expr
*cmp
= new expr (ocmp
->operation
);
942 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
943 cmp
->append_op (ocmp
->ops
[j
]);
944 cmp
->is_generic
= true;
945 ne
->ops
[0] = new capture (c
->where
, cmp
);
949 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
950 expr
*cmp
= new expr (ocmp
->operation
);
951 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
952 cmp
->append_op (ocmp
->ops
[j
]);
953 cmp
->is_generic
= true;
963 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
964 GENERIC and a GIMPLE variant. */
967 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
969 vec
<operand
*> matchers
= lower_cond (s
->match
);
970 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
972 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
973 s
->result
, s
->result_location
, s
->ifexpr_vec
,
974 s
->for_vec
, s
->capture_ids
);
975 simplifiers
.safe_push (ns
);
979 /* In AST operand O replace operator ID with operator WITH. */
982 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
984 /* Deep-copy captures and expressions, replacing operations as
986 if (capture
*c
= dyn_cast
<capture
*> (o
))
990 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
992 else if (expr
*e
= dyn_cast
<expr
*> (o
))
994 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
996 ne
->expr_type
= e
->expr_type
;
997 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
998 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1002 /* For c_expr we simply record a string replacement table which is
1003 applied at code-generation time. */
1004 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1006 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1007 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1008 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1014 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1017 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1019 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1020 unsigned worklist_start
= 0;
1021 auto_vec
<simplify
*> worklist
;
1022 worklist
.safe_push (sin
);
1024 /* Lower each recorded for separately, operating on the
1025 set of simplifiers created by the previous one.
1026 Lower inner-to-outer so inner for substitutes can refer
1027 to operators replaced by outer fors. */
1028 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1030 vec
<user_id
*>& ids
= for_vec
[fi
];
1031 unsigned n_ids
= ids
.length ();
1032 unsigned max_n_opers
= 0;
1033 for (unsigned i
= 0; i
< n_ids
; ++i
)
1034 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1035 max_n_opers
= ids
[i
]->substitutes
.length ();
1037 unsigned worklist_end
= worklist
.length ();
1038 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1040 simplify
*s
= worklist
[si
];
1041 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1043 operand
*match_op
= s
->match
;
1044 operand
*result_op
= s
->result
;
1045 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1047 for (unsigned i
= 0; i
< n_ids
; ++i
)
1049 user_id
*id
= ids
[i
];
1050 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1051 match_op
= replace_id (match_op
, id
, oper
);
1053 result_op
= replace_id (result_op
, id
, oper
);
1054 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1055 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1058 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1059 result_op
, s
->result_location
,
1060 ifexpr_vec
, vNULL
, s
->capture_ids
);
1061 worklist
.safe_push (ns
);
1064 worklist_start
= worklist_end
;
1067 /* Copy out the result from the last for lowering. */
1068 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1069 simplifiers
.safe_push (worklist
[i
]);
1072 /* Lower the AST for everything in SIMPLIFIERS. */
1075 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1077 auto_vec
<simplify
*> out_simplifiers
;
1078 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1079 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1081 simplifiers
.truncate (0);
1082 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1083 lower_commutative (out_simplifiers
[i
], simplifiers
);
1085 out_simplifiers
.truncate (0);
1087 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1088 lower_cond (simplifiers
[i
], out_simplifiers
);
1090 out_simplifiers
.safe_splice (simplifiers
);
1093 simplifiers
.truncate (0);
1094 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1095 lower_for (out_simplifiers
[i
], simplifiers
);
1101 /* The decision tree built for generating GIMPLE and GENERIC pattern
1102 matching code. It represents the 'match' expression of all
1103 simplifies and has those as its leafs. */
1105 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1109 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1113 vec
<dt_node
*> kids
;
1115 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1117 dt_node
*append_node (dt_node
*);
1118 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1119 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1120 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1121 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1123 virtual void gen (FILE *, bool) {}
1125 void gen_kids (FILE *, bool);
1126 void gen_kids_1 (FILE *, bool,
1127 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1128 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1131 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1133 struct dt_operand
: public dt_node
1136 dt_operand
*match_dop
;
1140 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1141 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1142 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1143 parent (parent_
), pos (pos_
) {}
1145 void gen (FILE *, bool);
1146 unsigned gen_predicate (FILE *, const char *, bool);
1147 unsigned gen_match_op (FILE *, const char *);
1149 unsigned gen_gimple_expr (FILE *);
1150 unsigned gen_generic_expr (FILE *, const char *);
1152 char *get_name (char *);
1153 void gen_opname (char *, unsigned);
1156 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1158 struct dt_simplify
: public dt_node
1161 unsigned pattern_no
;
1162 dt_operand
**indexes
;
1164 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1165 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1166 indexes (indexes_
) {}
1168 void gen (FILE *f
, bool);
1174 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1176 return (n
->type
== dt_node::DT_OPERAND
1177 || n
->type
== dt_node::DT_MATCH
);
1180 /* A container for the actual decision tree. */
1182 struct decision_tree
1186 void insert (struct simplify
*, unsigned);
1187 void gen_gimple (FILE *f
= stderr
);
1188 void gen_generic (FILE *f
= stderr
);
1189 void print (FILE *f
= stderr
);
1191 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1193 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1194 unsigned pos
= 0, dt_node
*parent
= 0);
1195 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1196 static bool cmp_node (dt_node
*, dt_node
*);
1197 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1200 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1203 cmp_operand (operand
*o1
, operand
*o2
)
1205 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1208 if (o1
->type
== operand::OP_PREDICATE
)
1210 predicate
*p1
= as_a
<predicate
*>(o1
);
1211 predicate
*p2
= as_a
<predicate
*>(o2
);
1212 return p1
->p
== p2
->p
;
1214 else if (o1
->type
== operand::OP_EXPR
)
1216 expr
*e1
= static_cast<expr
*>(o1
);
1217 expr
*e2
= static_cast<expr
*>(o2
);
1218 return (e1
->operation
== e2
->operation
1219 && e1
->is_generic
== e2
->is_generic
);
1225 /* Compare two decision tree nodes N1 and N2 and return true if they
1229 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1231 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1237 if (n1
->type
== dt_node::DT_TRUE
)
1240 if (n1
->type
== dt_node::DT_OPERAND
)
1241 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1242 (as_a
<dt_operand
*> (n2
))->op
);
1243 else if (n1
->type
== dt_node::DT_MATCH
)
1244 return ((as_a
<dt_operand
*> (n1
))->match_dop
1245 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1249 /* Search OPS for a decision tree node like P and return it if found. */
1252 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1254 /* We can merge adjacent DT_TRUE. */
1255 if (p
->type
== dt_node::DT_TRUE
1257 && ops
.last ()->type
== dt_node::DT_TRUE
)
1259 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1261 /* But we can't merge across DT_TRUE nodes as they serve as
1262 pattern order barriers to make sure that patterns apply
1263 in order of appearance in case multiple matches are possible. */
1264 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1266 if (decision_tree::cmp_node (ops
[i
], p
))
1272 /* Append N to the decision tree if it there is not already an existing
1276 dt_node::append_node (dt_node
*n
)
1280 kid
= decision_tree::find_node (kids
, n
);
1285 n
->level
= this->level
+ 1;
1290 /* Append OP to the decision tree. */
1293 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1295 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1296 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1297 return append_node (n
);
1300 /* Append a DT_TRUE decision tree node. */
1303 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1305 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1306 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1307 return append_node (n
);
1310 /* Append a DT_MATCH decision tree node. */
1313 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1315 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1316 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1317 return append_node (n
);
1320 /* Append S to the decision tree. */
1323 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1324 dt_operand
**indexes
)
1326 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1327 return append_node (n
);
1330 /* Insert O into the decision tree and return the decision tree node found
1334 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1335 unsigned pos
, dt_node
*parent
)
1337 dt_node
*q
, *elm
= 0;
1339 if (capture
*c
= dyn_cast
<capture
*> (o
))
1341 unsigned capt_index
= c
->where
;
1343 if (indexes
[capt_index
] == 0)
1346 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1349 q
= elm
= p
->append_true_op (parent
, pos
);
1352 // get to the last capture
1353 for (operand
*what
= c
->what
;
1354 what
&& is_a
<capture
*> (what
);
1355 c
= as_a
<capture
*> (what
), what
= c
->what
)
1360 unsigned cc_index
= c
->where
;
1361 dt_operand
*match_op
= indexes
[cc_index
];
1363 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1364 elm
= decision_tree::find_node (p
->kids
, &temp
);
1368 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1369 elm
= decision_tree::find_node (p
->kids
, &temp
);
1374 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1375 elm
= decision_tree::find_node (p
->kids
, &temp
);
1379 gcc_assert (elm
->type
== dt_node::DT_TRUE
1380 || elm
->type
== dt_node::DT_OPERAND
1381 || elm
->type
== dt_node::DT_MATCH
);
1382 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1387 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1389 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1394 p
= p
->append_op (o
, parent
, pos
);
1397 if (expr
*e
= dyn_cast
<expr
*>(o
))
1399 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1400 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1406 /* Insert S into the decision tree. */
1409 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1411 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1412 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1413 p
->append_simplify (s
, pattern_no
, indexes
);
1416 /* Debug functions to dump the decision tree. */
1419 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1421 if (p
->type
== dt_node::DT_NODE
)
1422 fprintf (f
, "root");
1426 for (unsigned i
= 0; i
< indent
; i
++)
1429 if (p
->type
== dt_node::DT_OPERAND
)
1431 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1432 print_operand (dop
->op
, f
, true);
1434 else if (p
->type
== dt_node::DT_TRUE
)
1435 fprintf (f
, "true");
1436 else if (p
->type
== dt_node::DT_MATCH
)
1437 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1438 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1440 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1441 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1442 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1443 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1448 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1450 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1451 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1455 decision_tree::print (FILE *f
)
1457 return decision_tree::print_node (root
, f
);
1461 /* For GENERIC we have to take care of wrapping multiple-used
1462 expressions with side-effects in save_expr and preserve side-effects
1463 of expressions with omit_one_operand. Analyze captures in
1464 match, result and with expressions and perform early-outs
1465 on the outermost match expression operands for cases we cannot
1470 capture_info (simplify
*s
);
1471 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1472 void walk_result (operand
*o
, bool);
1473 void walk_c_expr (c_expr
*);
1479 bool force_no_side_effects_p
;
1480 bool cond_expr_cond_p
;
1481 unsigned long toplevel_msk
;
1482 int result_use_count
;
1485 auto_vec
<cinfo
> info
;
1486 unsigned long force_no_side_effects
;
1489 /* Analyze captures in S. */
1491 capture_info::capture_info (simplify
*s
)
1495 || ((e
= dyn_cast
<expr
*> (s
->result
))
1496 && is_a
<predicate_id
*> (e
->operation
)))
1498 force_no_side_effects
= -1;
1502 force_no_side_effects
= 0;
1503 info
.safe_grow_cleared (s
->capture_max
+ 1);
1504 e
= as_a
<expr
*> (s
->match
);
1505 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1506 walk_match (e
->ops
[i
], i
,
1507 (i
!= 0 && *e
->operation
== COND_EXPR
)
1508 || *e
->operation
== TRUTH_ANDIF_EXPR
1509 || *e
->operation
== TRUTH_ORIF_EXPR
,
1511 && (*e
->operation
== COND_EXPR
1512 || *e
->operation
== VEC_COND_EXPR
));
1514 walk_result (s
->result
, false);
1516 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1517 if (s
->ifexpr_vec
[i
].is_with
)
1518 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1521 /* Analyze captures in the match expression piece O. */
1524 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1525 bool conditional_p
, bool cond_expr_cond_p
)
1527 if (capture
*c
= dyn_cast
<capture
*> (o
))
1529 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1530 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1531 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1532 /* Mark expr (non-leaf) captures and recurse. */
1534 && is_a
<expr
*> (c
->what
))
1536 info
[c
->where
].expr_p
= true;
1537 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1540 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1542 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1544 bool cond_p
= conditional_p
;
1545 bool cond_expr_cond_p
= false;
1546 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1548 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1549 || *e
->operation
== TRUTH_ORIF_EXPR
)
1552 && (*e
->operation
== COND_EXPR
1553 || *e
->operation
== VEC_COND_EXPR
))
1554 cond_expr_cond_p
= true;
1555 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1558 else if (is_a
<predicate
*> (o
))
1560 /* Mark non-captured leafs toplevel arg for checking. */
1561 force_no_side_effects
|= 1 << toplevel_arg
;
1567 /* Analyze captures in the result expression piece O. */
1570 capture_info::walk_result (operand
*o
, bool conditional_p
)
1572 if (capture
*c
= dyn_cast
<capture
*> (o
))
1574 info
[c
->where
].result_use_count
++;
1575 /* If we substitute an expression capture we don't know
1576 which captures this will end up using (well, we don't
1577 compute that). Force the uses to be side-effect free
1578 which means forcing the toplevels that reach the
1579 expression side-effect free. */
1580 if (info
[c
->where
].expr_p
)
1581 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1582 /* Mark CSE capture capture uses as forced to have
1585 && is_a
<expr
*> (c
->what
))
1587 info
[c
->where
].cse_p
= true;
1588 walk_result (c
->what
, true);
1591 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1593 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1595 bool cond_p
= conditional_p
;
1596 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1598 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1599 || *e
->operation
== TRUTH_ORIF_EXPR
)
1601 walk_result (e
->ops
[i
], cond_p
);
1604 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1610 /* Look for captures in the C expr E. */
1613 capture_info::walk_c_expr (c_expr
*e
)
1615 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1616 unsigned p_depth
= 0;
1617 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1619 const cpp_token
*t
= &e
->code
[i
];
1620 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1621 if (t
->type
== CPP_NAME
1622 && strcmp ((const char *)CPP_HASHNODE
1623 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1624 && n
->type
== CPP_OPEN_PAREN
)
1626 else if (t
->type
== CPP_CLOSE_PAREN
1629 else if (p_depth
== 0
1630 && t
->type
== CPP_ATSIGN
1631 && (n
->type
== CPP_NUMBER
1632 || n
->type
== CPP_NAME
)
1633 && !(n
->flags
& PREV_WHITE
))
1636 if (n
->type
== CPP_NUMBER
)
1637 id
= (const char *)n
->val
.str
.text
;
1639 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1640 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1646 /* Code generation off the decision tree and the refered AST nodes. */
1649 is_conversion (id_base
*op
)
1651 return (*op
== CONVERT_EXPR
1653 || *op
== FLOAT_EXPR
1654 || *op
== FIX_TRUNC_EXPR
1655 || *op
== VIEW_CONVERT_EXPR
);
1658 /* Get the type to be used for generating operands of OP from the
1662 get_operand_type (id_base
*op
, const char *in_type
,
1663 const char *expr_type
,
1664 const char *other_oprnd_type
)
1666 /* Generally operands whose type does not match the type of the
1667 expression generated need to know their types but match and
1668 thus can fall back to 'other_oprnd_type'. */
1669 if (is_conversion (op
))
1670 return other_oprnd_type
;
1671 else if (*op
== REALPART_EXPR
1672 || *op
== IMAGPART_EXPR
)
1673 return other_oprnd_type
;
1674 else if (is_a
<operator_id
*> (op
)
1675 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1676 return other_oprnd_type
;
1679 /* Otherwise all types should match - choose one in order of
1686 return other_oprnd_type
;
1690 /* Generate transform code for an expression. */
1693 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1694 const char *in_type
, capture_info
*cinfo
,
1695 dt_operand
**indexes
, bool)
1697 bool conversion_p
= is_conversion (operation
);
1698 const char *type
= expr_type
;
1701 /* If there was a type specification in the pattern use it. */
1703 else if (conversion_p
)
1704 /* For conversions we need to build the expression using the
1705 outer type passed in. */
1707 else if (*operation
== REALPART_EXPR
1708 || *operation
== IMAGPART_EXPR
)
1710 /* __real and __imag use the component type of its operand. */
1711 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1714 else if (is_a
<operator_id
*> (operation
)
1715 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1717 /* comparisons use boolean_type_node (or what gets in), but
1718 their operands need to figure out the types themselves. */
1719 sprintf (optype
, "boolean_type_node");
1722 else if (*operation
== COND_EXPR
1723 || *operation
== VEC_COND_EXPR
)
1725 /* Conditions are of the same type as their first alternative. */
1726 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
1731 /* Other operations are of the same type as their first operand. */
1732 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1736 fatal ("two conversions in a row");
1739 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1741 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1742 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1745 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1747 = get_operand_type (operation
, in_type
, expr_type
,
1748 i
== 0 ? NULL
: op0type
);
1749 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1750 ((!(*operation
== COND_EXPR
)
1751 && !(*operation
== VEC_COND_EXPR
))
1756 if (*operation
== CONVERT_EXPR
)
1759 opr
= operation
->id
;
1763 /* ??? Building a stmt can fail for various reasons here, seq being
1764 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1765 So if we fail here we should continue matching other patterns. */
1766 fprintf (f
, " code_helper tem_code = %s;\n"
1767 " tree tem_ops[3] = { ", opr
);
1768 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1769 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1770 i
== ops
.length () - 1 ? " };\n" : ", ");
1771 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1772 ops
.length (), type
);
1773 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1774 " if (!res) return false;\n", type
);
1778 if (operation
->kind
== id_base::CODE
)
1779 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1780 ops
.length(), opr
, type
);
1782 fprintf (f
, " res = build_call_expr_loc (loc, "
1783 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1784 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1785 fprintf (f
, ", ops%d[%u]", depth
, i
);
1786 fprintf (f
, ");\n");
1788 fprintf (f
, "%s = res;\n", dest
);
1792 /* Generate code for a c_expr which is either the expression inside
1793 an if statement or a sequence of statements which computes a
1794 result to be stored to DEST. */
1797 c_expr::gen_transform (FILE *f
, const char *dest
,
1798 bool, int, const char *, capture_info
*,
1799 dt_operand
**, bool)
1801 if (dest
&& nr_stmts
== 1)
1802 fprintf (f
, "%s = ", dest
);
1804 unsigned stmt_nr
= 1;
1805 for (unsigned i
= 0; i
< code
.length (); ++i
)
1807 const cpp_token
*token
= &code
[i
];
1809 /* Replace captures for code-gen. */
1810 if (token
->type
== CPP_ATSIGN
)
1812 const cpp_token
*n
= &code
[i
+1];
1813 if ((n
->type
== CPP_NUMBER
1814 || n
->type
== CPP_NAME
)
1815 && !(n
->flags
& PREV_WHITE
))
1817 if (token
->flags
& PREV_WHITE
)
1820 if (n
->type
== CPP_NUMBER
)
1821 id
= (const char *)n
->val
.str
.text
;
1823 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1824 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1830 if (token
->flags
& PREV_WHITE
)
1833 if (token
->type
== CPP_NAME
)
1835 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1837 for (j
= 0; j
< ids
.length (); ++j
)
1839 if (strcmp (id
, ids
[j
].id
) == 0)
1841 fprintf (f
, "%s", ids
[j
].oper
);
1845 if (j
< ids
.length ())
1849 /* Output the token as string. */
1850 char *tk
= (char *)cpp_token_as_text (r
, token
);
1853 if (token
->type
== CPP_SEMICOLON
)
1856 if (dest
&& stmt_nr
== nr_stmts
)
1857 fprintf (f
, "\n %s = ", dest
);
1864 /* Generate transform code for a capture. */
1867 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1868 const char *in_type
, capture_info
*cinfo
,
1869 dt_operand
**indexes
, bool expand_compares
)
1871 if (what
&& is_a
<expr
*> (what
))
1873 if (indexes
[where
] == 0)
1876 sprintf (buf
, "captures[%u]", where
);
1877 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1881 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1883 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1884 with substituting a capture of that.
1885 ??? Returning false here will also not allow any other patterns
1887 if (gimple
&& expand_compares
1888 && cinfo
->info
[where
].cond_expr_cond_p
)
1889 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1891 " if (!seq) return false;\n"
1892 " %s = gimple_build (seq, TREE_CODE (%s),"
1893 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1894 " TREE_OPERAND (%s, 1));\n"
1895 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1898 /* Return the name of the operand representing the decision tree node.
1899 Use NAME as space to generate it. */
1902 dt_operand::get_name (char *name
)
1905 sprintf (name
, "t");
1906 else if (parent
->level
== 1)
1907 sprintf (name
, "op%u", pos
);
1908 else if (parent
->type
== dt_node::DT_MATCH
)
1909 return parent
->get_name (name
);
1911 sprintf (name
, "o%u%u", parent
->level
, pos
);
1915 /* Fill NAME with the operand name at position POS. */
1918 dt_operand::gen_opname (char *name
, unsigned pos
)
1921 sprintf (name
, "op%u", pos
);
1923 sprintf (name
, "o%u%u", level
, pos
);
1926 /* Generate matching code for the decision tree operand which is
1930 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1932 predicate
*p
= as_a
<predicate
*> (op
);
1934 if (p
->p
->matchers
.exists ())
1936 /* If this is a predicate generated from a pattern mangle its
1937 name and pass on the valueize hook. */
1939 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1941 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1944 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1949 /* Generate matching code for the decision tree operand which is
1953 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1955 char match_opname
[20];
1956 match_dop
->get_name (match_opname
);
1957 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1958 opname
, match_opname
, opname
, match_opname
);
1963 /* Generate GIMPLE matching code for the decision tree operand. */
1966 dt_operand::gen_gimple_expr (FILE *f
)
1968 expr
*e
= static_cast<expr
*> (op
);
1969 id_base
*id
= e
->operation
;
1970 unsigned n_ops
= e
->ops
.length ();
1972 for (unsigned i
= 0; i
< n_ops
; ++i
)
1974 char child_opname
[20];
1975 gen_opname (child_opname
, i
);
1977 if (id
->kind
== id_base::CODE
)
1980 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1981 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1983 /* ??? If this is a memory operation we can't (and should not)
1984 match this. The only sensible operand types are
1985 SSA names and invariants. */
1986 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1988 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1989 "|| is_gimple_min_invariant (%s))\n"
1990 "&& (%s = do_valueize (valueize, %s)))\n"
1991 "{\n", child_opname
, child_opname
, child_opname
,
1996 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1997 child_opname
, i
+ 1);
2000 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
2002 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
2003 child_opname
, child_opname
);
2010 /* Generate GENERIC matching code for the decision tree operand. */
2013 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
2015 expr
*e
= static_cast<expr
*> (op
);
2016 unsigned n_ops
= e
->ops
.length ();
2018 for (unsigned i
= 0; i
< n_ops
; ++i
)
2020 char child_opname
[20];
2021 gen_opname (child_opname
, i
);
2023 if (e
->operation
->kind
== id_base::CODE
)
2024 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2025 child_opname
, opname
, i
);
2027 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2028 child_opname
, opname
, i
);
2034 /* Generate matching code for the children of the decision tree node. */
2037 dt_node::gen_kids (FILE *f
, bool gimple
)
2039 auto_vec
<dt_operand
*> gimple_exprs
;
2040 auto_vec
<dt_operand
*> generic_exprs
;
2041 auto_vec
<dt_operand
*> fns
;
2042 auto_vec
<dt_operand
*> generic_fns
;
2043 auto_vec
<dt_operand
*> preds
;
2044 auto_vec
<dt_node
*> others
;
2046 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2048 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2050 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2051 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2053 if (e
->ops
.length () == 0
2054 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2055 generic_exprs
.safe_push (op
);
2056 else if (e
->operation
->kind
== id_base::FN
)
2061 generic_fns
.safe_push (op
);
2063 else if (e
->operation
->kind
== id_base::PREDICATE
)
2064 preds
.safe_push (op
);
2068 gimple_exprs
.safe_push (op
);
2070 generic_exprs
.safe_push (op
);
2073 else if (op
->op
->type
== operand::OP_PREDICATE
)
2074 others
.safe_push (kids
[i
]);
2078 else if (kids
[i
]->type
== dt_node::DT_MATCH
2079 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2080 others
.safe_push (kids
[i
]);
2081 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2083 /* A DT_TRUE operand serves as a barrier - generate code now
2084 for what we have collected sofar. */
2085 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2086 fns
, generic_fns
, preds
, others
);
2087 /* And output the true operand itself. */
2088 kids
[i
]->gen (f
, gimple
);
2089 gimple_exprs
.truncate (0);
2090 generic_exprs
.truncate (0);
2092 generic_fns
.truncate (0);
2094 others
.truncate (0);
2100 /* Generate code for the remains. */
2101 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2102 fns
, generic_fns
, preds
, others
);
2105 /* Generate matching code for the children of the decision tree node. */
2108 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2109 vec
<dt_operand
*> gimple_exprs
,
2110 vec
<dt_operand
*> generic_exprs
,
2111 vec
<dt_operand
*> fns
,
2112 vec
<dt_operand
*> generic_fns
,
2113 vec
<dt_operand
*> preds
,
2114 vec
<dt_node
*> others
)
2117 char *kid_opname
= buf
;
2119 unsigned exprs_len
= gimple_exprs
.length ();
2120 unsigned gexprs_len
= generic_exprs
.length ();
2121 unsigned fns_len
= fns
.length ();
2122 unsigned gfns_len
= generic_fns
.length ();
2124 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2127 gimple_exprs
[0]->get_name (kid_opname
);
2129 fns
[0]->get_name (kid_opname
);
2131 generic_fns
[0]->get_name (kid_opname
);
2133 generic_exprs
[0]->get_name (kid_opname
);
2135 fprintf (f
, "switch (TREE_CODE (%s))\n"
2139 if (exprs_len
|| fns_len
)
2141 fprintf (f
, "case SSA_NAME:\n");
2142 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2144 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2148 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2149 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2151 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2153 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2154 id_base
*op
= e
->operation
;
2155 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2156 fprintf (f
, "CASE_CONVERT:\n");
2158 fprintf (f
, "case %s:\n", op
->id
);
2160 gimple_exprs
[i
]->gen (f
, true);
2161 fprintf (f
, "break;\n"
2164 fprintf (f
, "default:;\n"
2171 fprintf (f
, "else ");
2173 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2175 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2176 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2179 for (unsigned i
= 0; i
< fns_len
; ++i
)
2181 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2182 fprintf (f
, "case %s:\n"
2183 "{\n", e
->operation
->id
);
2184 fns
[i
]->gen (f
, true);
2185 fprintf (f
, "break;\n"
2189 fprintf (f
, "default:;\n"
2198 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2200 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2201 id_base
*op
= e
->operation
;
2202 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2203 fprintf (f
, "CASE_CONVERT:\n");
2205 fprintf (f
, "case %s:\n", op
->id
);
2207 generic_exprs
[i
]->gen (f
, gimple
);
2208 fprintf (f
, "break;\n"
2214 fprintf (f
, "case CALL_EXPR:\n"
2216 "tree fndecl = get_callee_fndecl (%s);\n"
2217 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2218 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2221 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2223 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2224 gcc_assert (e
->operation
->kind
== id_base::FN
);
2226 fprintf (f
, "case %s:\n"
2227 "{\n", e
->operation
->id
);
2228 generic_fns
[j
]->gen (f
, false);
2229 fprintf (f
, "break;\n"
2233 fprintf (f
, "default:;\n"
2239 /* Close switch (TREE_CODE ()). */
2240 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2241 fprintf (f
, "default:;\n"
2244 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2246 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2247 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2248 preds
[i
]->get_name (kid_opname
);
2249 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2250 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2251 gimple
? "gimple" : "tree",
2252 p
->id
, kid_opname
, kid_opname
,
2253 gimple
? ", valueize" : "");
2255 for (int j
= 0; j
< p
->nargs
; ++j
)
2257 char child_opname
[20];
2258 preds
[i
]->gen_opname (child_opname
, j
);
2259 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2261 preds
[i
]->gen_kids (f
, gimple
);
2265 for (unsigned i
= 0; i
< others
.length (); ++i
)
2266 others
[i
]->gen (f
, gimple
);
2269 /* Generate matching code for the decision tree operand. */
2272 dt_operand::gen (FILE *f
, bool gimple
)
2277 unsigned n_braces
= 0;
2279 if (type
== DT_OPERAND
)
2282 case operand::OP_PREDICATE
:
2283 n_braces
= gen_predicate (f
, opname
, gimple
);
2286 case operand::OP_EXPR
:
2288 n_braces
= gen_gimple_expr (f
);
2290 n_braces
= gen_generic_expr (f
, opname
);
2296 else if (type
== DT_TRUE
)
2298 else if (type
== DT_MATCH
)
2299 n_braces
= gen_match_op (f
, opname
);
2303 gen_kids (f
, gimple
);
2305 for (unsigned i
= 0; i
< n_braces
; ++i
)
2311 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2312 step of a '(simplify ...)' or '(match ...)'. This handles everything
2313 that is not part of the decision tree (simplify->match). */
2316 dt_simplify::gen (FILE *f
, bool gimple
)
2319 output_line_directive (f
, s
->result_location
);
2320 if (s
->capture_max
>= 0)
2321 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2322 s
->capture_max
+ 1);
2324 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2328 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2331 unsigned n_braces
= 0;
2332 if (s
->ifexpr_vec
!= vNULL
)
2334 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2336 if_or_with
&w
= s
->ifexpr_vec
[i
];
2340 output_line_directive (f
, w
.location
);
2341 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2346 output_line_directive (f
, w
.location
);
2347 fprintf (f
, "if (");
2348 if (i
== s
->ifexpr_vec
.length () - 1
2349 || s
->ifexpr_vec
[i
+1].is_with
)
2350 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2359 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2363 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2369 while (j
< s
->ifexpr_vec
.length ()
2370 && !s
->ifexpr_vec
[j
].is_with
);
2380 /* Analyze captures and perform early-outs on the incoming arguments
2381 that cover cases we cannot handle. */
2382 capture_info
cinfo (s
);
2386 && !((e
= dyn_cast
<expr
*> (s
->result
))
2387 && is_a
<predicate_id
*> (e
->operation
)))
2389 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2390 if (cinfo
.force_no_side_effects
& (1 << i
))
2391 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2392 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2393 if (cinfo
.info
[i
].cse_p
)
2395 else if (cinfo
.info
[i
].force_no_side_effects_p
2396 && (cinfo
.info
[i
].toplevel_msk
2397 & cinfo
.force_no_side_effects
) == 0)
2398 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2399 "return NULL_TREE;\n", i
);
2400 else if ((cinfo
.info
[i
].toplevel_msk
2401 & cinfo
.force_no_side_effects
) != 0)
2402 /* Mark capture as having no side-effects if we had to verify
2403 that via forced toplevel operand checks. */
2404 cinfo
.info
[i
].force_no_side_effects_p
= true;
2407 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2408 "fprintf (dump_file, \"Applying pattern ");
2409 output_line_directive (f
, s
->result_location
, true);
2410 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2412 operand
*result
= s
->result
;
2415 /* If there is no result then this is a predicate implementation. */
2416 fprintf (f
, "return true;\n");
2420 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2421 in outermost position). */
2422 if (result
->type
== operand::OP_EXPR
2423 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2424 result
= as_a
<expr
*> (result
)->ops
[0];
2425 if (result
->type
== operand::OP_EXPR
)
2427 expr
*e
= as_a
<expr
*> (result
);
2428 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2430 fprintf (f
, "*res_code = %s;\n",
2431 *e
->operation
== CONVERT_EXPR
2432 ? "NOP_EXPR" : e
->operation
->id
);
2433 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2436 snprintf (dest
, 32, " res_ops[%d]", j
);
2438 = get_operand_type (e
->operation
,
2439 "type", e
->expr_type
,
2441 ? NULL
: "TREE_TYPE (res_ops[0])");
2442 /* We need to expand GENERIC conditions we captured from
2444 bool expand_generic_cond_exprs_p
2446 /* But avoid doing that if the GENERIC condition is
2447 valid - which it is in the first operand of COND_EXPRs
2448 and VEC_COND_EXRPs. */
2449 && ((!(*e
->operation
== COND_EXPR
)
2450 && !(*e
->operation
== VEC_COND_EXPR
))
2452 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2453 indexes
, expand_generic_cond_exprs_p
);
2456 /* Re-fold the toplevel result. It's basically an embedded
2457 gimple_build w/o actually building the stmt. */
2459 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2460 "res_ops, valueize);\n", e
->ops
.length ());
2462 else if (result
->type
== operand::OP_CAPTURE
2463 || result
->type
== operand::OP_C_EXPR
)
2465 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2466 &cinfo
, indexes
, false);
2467 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2468 if (is_a
<capture
*> (result
)
2469 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2471 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2472 with substituting a capture of that. */
2473 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2475 " tree tem = res_ops[0];\n"
2476 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2477 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2483 fprintf (f
, "return true;\n");
2487 bool is_predicate
= false;
2488 if (result
->type
== operand::OP_EXPR
)
2490 expr
*e
= as_a
<expr
*> (result
);
2491 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2492 /* Search for captures used multiple times in the result expression
2493 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2495 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2497 if (!cinfo
.info
[i
].force_no_side_effects_p
2498 && cinfo
.info
[i
].result_use_count
> 1)
2499 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2500 " captures[%d] = save_expr (captures[%d]);\n",
2503 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2507 snprintf (dest
, 32, "res_ops[%d]", j
);
2510 fprintf (f
, " tree res_op%d;\n", j
);
2511 snprintf (dest
, 32, " res_op%d", j
);
2514 = get_operand_type (e
->operation
,
2515 "type", e
->expr_type
,
2517 ? NULL
: "TREE_TYPE (res_op0)");
2518 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2522 fprintf (f
, "return true;\n");
2525 fprintf (f
, " tree res;\n");
2526 /* Re-fold the toplevel result. Use non_lvalue to
2527 build NON_LVALUE_EXPRs so they get properly
2528 ignored when in GIMPLE form. */
2529 if (*e
->operation
== NON_LVALUE_EXPR
)
2530 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2533 if (e
->operation
->kind
== id_base::CODE
)
2534 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2536 *e
->operation
== CONVERT_EXPR
2537 ? "NOP_EXPR" : e
->operation
->id
);
2539 fprintf (f
, " res = build_call_expr_loc "
2540 "(loc, builtin_decl_implicit (%s), %d",
2541 e
->operation
->id
, e
->ops
.length());
2542 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2543 fprintf (f
, ", res_op%d", j
);
2544 fprintf (f
, ");\n");
2548 else if (result
->type
== operand::OP_CAPTURE
2549 || result
->type
== operand::OP_C_EXPR
)
2552 fprintf (f
, " tree res;\n");
2553 s
->result
->gen_transform (f
, " res", false, 1, "type",
2560 /* Search for captures not used in the result expression and dependent
2561 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2562 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2564 if (!cinfo
.info
[i
].force_no_side_effects_p
2565 && !cinfo
.info
[i
].expr_p
2566 && cinfo
.info
[i
].result_use_count
== 0)
2567 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2568 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2569 " fold_ignored_result (captures[%d]), res);\n",
2572 fprintf (f
, " return res;\n");
2576 for (unsigned i
= 0; i
< n_braces
; ++i
)
2582 /* Main entry to generate code for matching GIMPLE IL off the decision
2586 decision_tree::gen_gimple (FILE *f
)
2588 for (unsigned n
= 1; n
<= 3; ++n
)
2590 fprintf (f
, "\nstatic bool\n"
2591 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2592 " gimple_seq *seq, tree (*valueize)(tree),\n"
2593 " code_helper code, tree type");
2594 for (unsigned i
= 0; i
< n
; ++i
)
2595 fprintf (f
, ", tree op%d", i
);
2599 fprintf (f
, "switch (code.get_rep())\n"
2601 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2603 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2604 expr
*e
= static_cast<expr
*>(dop
->op
);
2605 if (e
->ops
.length () != n
)
2608 if (*e
->operation
== CONVERT_EXPR
2609 || *e
->operation
== NOP_EXPR
)
2610 fprintf (f
, "CASE_CONVERT:\n");
2612 fprintf (f
, "case %s%s:\n",
2613 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2616 dop
->gen_kids (f
, true);
2617 fprintf (f
, "break;\n");
2620 fprintf (f
, "default:;\n"
2623 fprintf (f
, "return false;\n");
2628 /* Main entry to generate code for matching GENERIC IL off the decision
2632 decision_tree::gen_generic (FILE *f
)
2634 for (unsigned n
= 1; n
<= 3; ++n
)
2636 fprintf (f
, "\ntree\n"
2637 "generic_simplify (location_t loc, enum tree_code code, "
2638 "tree type ATTRIBUTE_UNUSED");
2639 for (unsigned i
= 0; i
< n
; ++i
)
2640 fprintf (f
, ", tree op%d", i
);
2644 fprintf (f
, "switch (code)\n"
2646 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2648 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2649 expr
*e
= static_cast<expr
*>(dop
->op
);
2650 if (e
->ops
.length () != n
2651 /* Builtin simplifications are somewhat premature on
2652 GENERIC. The following drops patterns with outermost
2653 calls. It's easy to emit overloads for function code
2654 though if necessary. */
2655 || e
->operation
->kind
!= id_base::CODE
)
2658 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2659 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2660 fprintf (f
, "CASE_CONVERT:\n");
2662 fprintf (f
, "case %s:\n", e
->operation
->id
);
2664 dop
->gen_kids (f
, false);
2665 fprintf (f
, "break;\n"
2668 fprintf (f
, "default:;\n"
2671 fprintf (f
, "return NULL_TREE;\n");
2676 /* Output code to implement the predicate P from the decision tree DT. */
2679 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2681 fprintf (f
, "\nbool\n"
2682 "%s%s (tree t%s%s)\n"
2683 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2684 p
->nargs
> 0 ? ", tree *res_ops" : "",
2685 gimple
? ", tree (*valueize)(tree)" : "");
2686 /* Conveniently make 'type' available. */
2687 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2690 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2691 dt
.root
->gen_kids (f
, gimple
);
2693 fprintf (f
, "return false;\n"
2697 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2700 write_header (FILE *f
, const char *head
)
2702 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2703 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2705 /* Include the header instead of writing it awkwardly quoted here. */
2706 fprintf (f
, "\n#include \"%s\"\n", head
);
2716 parser (cpp_reader
*);
2719 const cpp_token
*next ();
2720 const cpp_token
*peek ();
2721 const cpp_token
*peek_ident (const char * = NULL
);
2722 const cpp_token
*expect (enum cpp_ttype
);
2723 void eat_token (enum cpp_ttype
);
2724 const char *get_string ();
2725 const char *get_ident ();
2726 void eat_ident (const char *);
2727 const char *get_number ();
2729 id_base
*parse_operation ();
2730 operand
*parse_capture (operand
*);
2731 operand
*parse_expr ();
2732 c_expr
*parse_c_expr (cpp_ttype
);
2733 operand
*parse_op ();
2735 void record_operlist (source_location
, user_id
*);
2737 void parse_pattern ();
2738 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2739 operand
*, source_location
);
2740 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2742 void parse_for (source_location
);
2743 void parse_if (source_location
);
2744 void parse_predicates (source_location
);
2745 void parse_operator_list (source_location
);
2748 vec
<if_or_with
> active_ifs
;
2749 vec
<vec
<user_id
*> > active_fors
;
2750 hash_set
<user_id
*> *oper_lists_set
;
2751 vec
<user_id
*> oper_lists
;
2753 cid_map_t
*capture_ids
;
2756 vec
<simplify
*> simplifiers
;
2757 vec
<predicate_id
*> user_predicates
;
2758 bool parsing_match_operand
;
2761 /* Lexing helpers. */
2763 /* Read the next non-whitespace token from R. */
2768 const cpp_token
*token
;
2771 token
= cpp_get_token (r
);
2773 while (token
->type
== CPP_PADDING
2774 && token
->type
!= CPP_EOF
);
2778 /* Peek at the next non-whitespace token from R. */
2783 const cpp_token
*token
;
2787 token
= cpp_peek_token (r
, i
++);
2789 while (token
->type
== CPP_PADDING
2790 && token
->type
!= CPP_EOF
);
2791 /* If we peek at EOF this is a fatal error as it leaves the
2792 cpp_reader in unusable state. Assume we really wanted a
2793 token and thus this EOF is unexpected. */
2794 if (token
->type
== CPP_EOF
)
2795 fatal_at (token
, "unexpected end of file");
2799 /* Peek at the next identifier token (or return NULL if the next
2800 token is not an identifier or equal to ID if supplied). */
2803 parser::peek_ident (const char *id
)
2805 const cpp_token
*token
= peek ();
2806 if (token
->type
!= CPP_NAME
)
2812 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2813 if (strcmp (id
, t
) == 0)
2819 /* Read the next token from R and assert it is of type TK. */
2822 parser::expect (enum cpp_ttype tk
)
2824 const cpp_token
*token
= next ();
2825 if (token
->type
!= tk
)
2826 fatal_at (token
, "expected %s, got %s",
2827 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2832 /* Consume the next token from R and assert it is of type TK. */
2835 parser::eat_token (enum cpp_ttype tk
)
2840 /* Read the next token from R and assert it is of type CPP_STRING and
2841 return its value. */
2844 parser::get_string ()
2846 const cpp_token
*token
= expect (CPP_STRING
);
2847 return (const char *)token
->val
.str
.text
;
2850 /* Read the next token from R and assert it is of type CPP_NAME and
2851 return its value. */
2854 parser::get_ident ()
2856 const cpp_token
*token
= expect (CPP_NAME
);
2857 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2860 /* Eat an identifier token with value S from R. */
2863 parser::eat_ident (const char *s
)
2865 const cpp_token
*token
= peek ();
2866 const char *t
= get_ident ();
2867 if (strcmp (s
, t
) != 0)
2868 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2871 /* Read the next token from R and assert it is of type CPP_NUMBER and
2872 return its value. */
2875 parser::get_number ()
2877 const cpp_token
*token
= expect (CPP_NUMBER
);
2878 return (const char *)token
->val
.str
.text
;
2882 /* Record an operator-list use for transparent for handling. */
2885 parser::record_operlist (source_location loc
, user_id
*p
)
2887 if (!oper_lists_set
->add (p
))
2889 if (!oper_lists
.is_empty ()
2890 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2891 fatal_at (loc
, "User-defined operator list does not have the "
2892 "same number of entries as others used in the pattern");
2893 oper_lists
.safe_push (p
);
2897 /* Parse the operator ID, special-casing convert?, convert1? and
2901 parser::parse_operation ()
2903 const cpp_token
*id_tok
= peek ();
2904 const char *id
= get_ident ();
2905 const cpp_token
*token
= peek ();
2906 if (strcmp (id
, "convert0") == 0)
2907 fatal_at (id_tok
, "use 'convert?' here");
2908 else if (strcmp (id
, "view_convert0") == 0)
2909 fatal_at (id_tok
, "use 'view_convert?' here");
2910 if (token
->type
== CPP_QUERY
2911 && !(token
->flags
& PREV_WHITE
))
2913 if (strcmp (id
, "convert") == 0)
2915 else if (strcmp (id
, "convert1") == 0)
2917 else if (strcmp (id
, "convert2") == 0)
2919 else if (strcmp (id
, "view_convert") == 0)
2920 id
= "view_convert0";
2921 else if (strcmp (id
, "view_convert1") == 0)
2923 else if (strcmp (id
, "view_convert2") == 0)
2926 fatal_at (id_tok
, "non-convert operator conditionalized");
2928 if (!parsing_match_operand
)
2929 fatal_at (id_tok
, "conditional convert can only be used in "
2930 "match expression");
2931 eat_token (CPP_QUERY
);
2933 else if (strcmp (id
, "convert1") == 0
2934 || strcmp (id
, "convert2") == 0
2935 || strcmp (id
, "view_convert1") == 0
2936 || strcmp (id
, "view_convert2") == 0)
2937 fatal_at (id_tok
, "expected '?' after conditional operator");
2938 id_base
*op
= get_operator (id
);
2940 fatal_at (id_tok
, "unknown operator %s", id
);
2942 user_id
*p
= dyn_cast
<user_id
*> (op
);
2943 if (p
&& p
->is_oper_list
)
2945 if (active_fors
.length() == 0)
2946 record_operlist (id_tok
->src_loc
, p
);
2948 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
2954 capture = '@'<number> */
2957 parser::parse_capture (operand
*op
)
2959 eat_token (CPP_ATSIGN
);
2960 const cpp_token
*token
= peek ();
2961 const char *id
= NULL
;
2962 if (token
->type
== CPP_NUMBER
)
2964 else if (token
->type
== CPP_NAME
)
2967 fatal_at (token
, "expected number or identifier");
2968 unsigned next_id
= capture_ids
->elements ();
2970 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2973 return new capture (num
, op
);
2976 /* Parse an expression
2977 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2980 parser::parse_expr ()
2982 expr
*e
= new expr (parse_operation ());
2983 const cpp_token
*token
= peek ();
2985 bool is_commutative
= false;
2986 const char *expr_type
= NULL
;
2988 if (token
->type
== CPP_COLON
2989 && !(token
->flags
& PREV_WHITE
))
2991 eat_token (CPP_COLON
);
2993 if (token
->type
== CPP_NAME
2994 && !(token
->flags
& PREV_WHITE
))
2996 const char *s
= get_ident ();
2997 if (s
[0] == 'c' && !s
[1])
2999 if (!parsing_match_operand
)
3001 "flag 'c' can only be used in match expression");
3002 is_commutative
= true;
3004 else if (s
[1] != '\0')
3006 if (parsing_match_operand
)
3007 fatal_at (token
, "type can only be used in result expression");
3011 fatal_at (token
, "flag %s not recognized", s
);
3016 fatal_at (token
, "expected flag or type specifying identifier");
3019 if (token
->type
== CPP_ATSIGN
3020 && !(token
->flags
& PREV_WHITE
))
3021 op
= parse_capture (e
);
3026 const cpp_token
*token
= peek ();
3027 if (token
->type
== CPP_CLOSE_PAREN
)
3029 if (e
->operation
->nargs
!= -1
3030 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3031 fatal_at (token
, "'%s' expects %u operands, not %u",
3032 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3035 if (e
->ops
.length () == 2)
3036 e
->is_commutative
= true;
3038 fatal_at (token
, "only binary operators or function with "
3039 "two arguments can be marked commutative");
3041 e
->expr_type
= expr_type
;
3044 e
->append_op (parse_op ());
3049 /* Lex native C code delimited by START recording the preprocessing tokens
3050 for later processing.
3051 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3054 parser::parse_c_expr (cpp_ttype start
)
3056 const cpp_token
*token
;
3059 vec
<cpp_token
> code
= vNULL
;
3060 unsigned nr_stmts
= 0;
3062 if (start
== CPP_OPEN_PAREN
)
3063 end
= CPP_CLOSE_PAREN
;
3064 else if (start
== CPP_OPEN_BRACE
)
3065 end
= CPP_CLOSE_BRACE
;
3073 /* Count brace pairs to find the end of the expr to match. */
3074 if (token
->type
== start
)
3076 else if (token
->type
== end
3080 /* This is a lame way of counting the number of statements. */
3081 if (token
->type
== CPP_SEMICOLON
)
3084 /* If this is possibly a user-defined identifier mark it used. */
3085 if (token
->type
== CPP_NAME
)
3087 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3088 (token
->val
.node
.node
)->ident
.str
);
3090 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3091 record_operlist (token
->src_loc
, p
);
3094 /* Record the token. */
3095 code
.safe_push (*token
);
3098 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3101 /* Parse an operand which is either an expression, a predicate or
3102 a standalone capture.
3103 op = predicate | expr | c_expr | capture */
3108 const cpp_token
*token
= peek ();
3109 struct operand
*op
= NULL
;
3110 if (token
->type
== CPP_OPEN_PAREN
)
3112 eat_token (CPP_OPEN_PAREN
);
3114 eat_token (CPP_CLOSE_PAREN
);
3116 else if (token
->type
== CPP_OPEN_BRACE
)
3118 op
= parse_c_expr (CPP_OPEN_BRACE
);
3122 /* Remaining ops are either empty or predicates */
3123 if (token
->type
== CPP_NAME
)
3125 const char *id
= get_ident ();
3126 id_base
*opr
= get_operator (id
);
3128 fatal_at (token
, "expected predicate name");
3129 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3131 if (code
->nargs
!= 0)
3132 fatal_at (token
, "using an operator with operands as predicate");
3133 /* Parse the zero-operand operator "predicates" as
3135 op
= new expr (opr
);
3137 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3139 if (code
->nargs
!= 0)
3140 fatal_at (token
, "using an operator with operands as predicate");
3141 /* Parse the zero-operand operator "predicates" as
3143 op
= new expr (opr
);
3145 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3146 op
= new predicate (p
);
3148 fatal_at (token
, "using an unsupported operator as predicate");
3149 if (!parsing_match_operand
)
3150 fatal_at (token
, "predicates are only allowed in match expression");
3152 if (token
->flags
& PREV_WHITE
)
3155 else if (token
->type
!= CPP_COLON
3156 && token
->type
!= CPP_ATSIGN
)
3157 fatal_at (token
, "expected expression or predicate");
3158 /* optionally followed by a capture and a predicate. */
3159 if (token
->type
== CPP_COLON
)
3160 fatal_at (token
, "not implemented: predicate on leaf operand");
3161 if (token
->type
== CPP_ATSIGN
)
3162 op
= parse_capture (op
);
3168 /* Create a new simplify from the current parsing state and MATCH,
3169 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3172 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3173 operand
*match
, source_location match_loc
,
3174 operand
*result
, source_location result_loc
)
3176 /* Build and push a temporary for for operator list uses in expressions. */
3177 if (!oper_lists
.is_empty ())
3178 active_fors
.safe_push (oper_lists
);
3180 simplifiers
.safe_push
3181 (new simplify (match
, match_loc
, result
, result_loc
,
3182 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3184 if (!oper_lists
.is_empty ())
3189 simplify = 'simplify' <expr> <result-op>
3191 match = 'match' <ident> <expr> [<result-op>]
3193 <result-op> = <op> | <if> | <with>
3194 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3195 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3196 and fill SIMPLIFIERS with the results. */
3199 parser::parse_simplify (source_location match_location
,
3200 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3203 /* Reset the capture map. */
3205 capture_ids
= new cid_map_t
;
3206 /* Reset oper_lists and set. */
3207 hash_set
<user_id
*> olist
;
3208 oper_lists_set
= &olist
;
3211 const cpp_token
*loc
= peek ();
3212 parsing_match_operand
= true;
3213 struct operand
*match
= parse_op ();
3214 parsing_match_operand
= false;
3215 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3216 fatal_at (loc
, "outermost expression cannot be captured");
3217 if (match
->type
== operand::OP_EXPR
3218 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3219 fatal_at (loc
, "outermost expression cannot be a predicate");
3221 const cpp_token
*token
= peek ();
3223 /* If this if is immediately closed then it is part of a predicate
3224 definition. Push it. */
3225 if (token
->type
== CPP_CLOSE_PAREN
)
3228 fatal_at (token
, "expected transform expression");
3229 push_simplify (simplifiers
, match
, match_location
,
3230 result
, token
->src_loc
);
3234 unsigned active_ifs_len
= active_ifs
.length ();
3237 if (token
->type
== CPP_OPEN_PAREN
)
3239 source_location paren_loc
= token
->src_loc
;
3240 eat_token (CPP_OPEN_PAREN
);
3241 if (peek_ident ("if"))
3244 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3245 token
->src_loc
, false));
3246 /* If this if is immediately closed then it contains a
3247 manual matcher or is part of a predicate definition.
3249 if (peek ()->type
== CPP_CLOSE_PAREN
)
3252 fatal_at (token
, "manual transform not implemented");
3253 push_simplify (simplifiers
, match
, match_location
,
3257 else if (peek_ident ("with"))
3260 /* Parse (with c-expr expr) as (if-with (true) expr). */
3261 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3263 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3267 operand
*op
= result
;
3270 push_simplify (simplifiers
, match
, match_location
,
3271 op
, token
->src_loc
);
3272 eat_token (CPP_CLOSE_PAREN
);
3273 /* A "default" result closes the enclosing scope. */
3274 if (active_ifs
.length () > active_ifs_len
)
3276 eat_token (CPP_CLOSE_PAREN
);
3283 else if (token
->type
== CPP_CLOSE_PAREN
)
3285 /* Close a scope if requested. */
3286 if (active_ifs
.length () > active_ifs_len
)
3288 eat_token (CPP_CLOSE_PAREN
);
3298 fatal_at (token
, "expected match operand expression");
3299 push_simplify (simplifiers
, match
, match_location
,
3300 matcher
? result
: parse_op (), token
->src_loc
);
3301 /* A "default" result closes the enclosing scope. */
3302 if (active_ifs
.length () > active_ifs_len
)
3304 eat_token (CPP_CLOSE_PAREN
);
3314 /* Parsing of the outer control structures. */
3316 /* Parse a for expression
3317 for = '(' 'for' <subst>... <pattern> ')'
3318 subst = <ident> '(' <ident>... ')' */
3321 parser::parse_for (source_location
)
3323 auto_vec
<const cpp_token
*> user_id_tokens
;
3324 vec
<user_id
*> user_ids
= vNULL
;
3325 const cpp_token
*token
;
3326 unsigned min_n_opers
= 0, max_n_opers
= 0;
3331 if (token
->type
!= CPP_NAME
)
3334 /* Insert the user defined operators into the operator hash. */
3335 const char *id
= get_ident ();
3336 if (get_operator (id
) != NULL
)
3337 fatal_at (token
, "operator already defined");
3338 user_id
*op
= new user_id (id
);
3339 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3341 user_ids
.safe_push (op
);
3342 user_id_tokens
.safe_push (token
);
3344 eat_token (CPP_OPEN_PAREN
);
3347 while ((token
= peek_ident ()) != 0)
3349 const char *oper
= get_ident ();
3350 id_base
*idb
= get_operator (oper
);
3352 fatal_at (token
, "no such operator '%s'", oper
);
3353 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
3354 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
3355 || *idb
== VIEW_CONVERT2
)
3356 fatal_at (token
, "conditional operators cannot be used inside for");
3360 else if (idb
->nargs
== -1)
3362 else if (idb
->nargs
!= arity
)
3363 fatal_at (token
, "operator '%s' with arity %d does not match "
3364 "others with arity %d", oper
, idb
->nargs
, arity
);
3366 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3369 if (p
->is_oper_list
)
3370 op
->substitutes
.safe_splice (p
->substitutes
);
3372 fatal_at (token
, "iterator cannot be used as operator-list");
3375 op
->substitutes
.safe_push (idb
);
3378 token
= expect (CPP_CLOSE_PAREN
);
3380 unsigned nsubstitutes
= op
->substitutes
.length ();
3381 if (nsubstitutes
== 0)
3382 fatal_at (token
, "A user-defined operator must have at least "
3383 "one substitution");
3384 if (max_n_opers
== 0)
3386 min_n_opers
= nsubstitutes
;
3387 max_n_opers
= nsubstitutes
;
3391 if (nsubstitutes
% min_n_opers
!= 0
3392 && min_n_opers
% nsubstitutes
!= 0)
3393 fatal_at (token
, "All user-defined identifiers must have a "
3394 "multiple number of operator substitutions of the "
3395 "smallest number of substitutions");
3396 if (nsubstitutes
< min_n_opers
)
3397 min_n_opers
= nsubstitutes
;
3398 else if (nsubstitutes
> max_n_opers
)
3399 max_n_opers
= nsubstitutes
;
3403 unsigned n_ids
= user_ids
.length ();
3405 fatal_at (token
, "for requires at least one user-defined identifier");
3408 if (token
->type
== CPP_CLOSE_PAREN
)
3409 fatal_at (token
, "no pattern defined in for");
3411 active_fors
.safe_push (user_ids
);
3415 if (token
->type
== CPP_CLOSE_PAREN
)
3421 /* Remove user-defined operators from the hash again. */
3422 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3424 if (!user_ids
[i
]->used
)
3425 warning_at (user_id_tokens
[i
],
3426 "operator %s defined but not used", user_ids
[i
]->id
);
3427 operators
->remove_elt (user_ids
[i
]);
3431 /* Parse an identifier associated with a list of operators.
3432 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3435 parser::parse_operator_list (source_location
)
3437 const cpp_token
*token
= peek ();
3438 const char *id
= get_ident ();
3440 if (get_operator (id
) != 0)
3441 fatal_at (token
, "operator %s already defined", id
);
3443 user_id
*op
= new user_id (id
, true);
3446 while ((token
= peek_ident ()) != 0)
3449 const char *oper
= get_ident ();
3450 id_base
*idb
= get_operator (oper
);
3453 fatal_at (token
, "no such operator '%s'", oper
);
3457 else if (idb
->nargs
== -1)
3459 else if (arity
!= idb
->nargs
)
3460 fatal_at (token
, "operator '%s' with arity %d does not match "
3461 "others with arity %d", oper
, idb
->nargs
, arity
);
3463 /* We allow composition of multiple operator lists. */
3464 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3465 op
->substitutes
.safe_splice (p
->substitutes
);
3467 op
->substitutes
.safe_push (idb
);
3470 // Check that there is no junk after id-list
3472 if (token
->type
!= CPP_CLOSE_PAREN
)
3473 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3475 if (op
->substitutes
.length () == 0)
3476 fatal_at (token
, "operator-list cannot be empty");
3479 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3483 /* Parse an outer if expression.
3484 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3487 parser::parse_if (source_location loc
)
3489 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3491 const cpp_token
*token
= peek ();
3492 if (token
->type
== CPP_CLOSE_PAREN
)
3493 fatal_at (token
, "no pattern defined in if");
3495 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3498 const cpp_token
*token
= peek ();
3499 if (token
->type
== CPP_CLOSE_PAREN
)
3507 /* Parse a list of predefined predicate identifiers.
3508 preds = '(' 'define_predicates' <ident>... ')' */
3511 parser::parse_predicates (source_location
)
3515 const cpp_token
*token
= peek ();
3516 if (token
->type
!= CPP_NAME
)
3519 add_predicate (get_ident ());
3524 /* Parse outer control structures.
3525 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3528 parser::parse_pattern ()
3530 /* All clauses start with '('. */
3531 eat_token (CPP_OPEN_PAREN
);
3532 const cpp_token
*token
= peek ();
3533 const char *id
= get_ident ();
3534 if (strcmp (id
, "simplify") == 0)
3536 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3539 else if (strcmp (id
, "match") == 0)
3541 bool with_args
= false;
3542 if (peek ()->type
== CPP_OPEN_PAREN
)
3544 eat_token (CPP_OPEN_PAREN
);
3547 const char *name
= get_ident ();
3548 id_base
*id
= get_operator (name
);
3552 p
= add_predicate (name
);
3553 user_predicates
.safe_push (p
);
3555 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3558 fatal_at (token
, "cannot add a match to a non-predicate ID");
3559 /* Parse (match <id> <arg>... (match-expr)) here. */
3563 capture_ids
= new cid_map_t
;
3565 while (peek ()->type
== CPP_ATSIGN
)
3566 e
->append_op (parse_capture (NULL
));
3567 eat_token (CPP_CLOSE_PAREN
);
3570 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3571 || (!e
&& p
->nargs
!= 0)))
3572 fatal_at (token
, "non-matching number of match operands");
3573 p
->nargs
= e
? e
->ops
.length () : 0;
3574 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3577 else if (strcmp (id
, "for") == 0)
3578 parse_for (token
->src_loc
);
3579 else if (strcmp (id
, "if") == 0)
3580 parse_if (token
->src_loc
);
3581 else if (strcmp (id
, "define_predicates") == 0)
3583 if (active_ifs
.length () > 0
3584 || active_fors
.length () > 0)
3585 fatal_at (token
, "define_predicates inside if or for is not supported");
3586 parse_predicates (token
->src_loc
);
3588 else if (strcmp (id
, "define_operator_list") == 0)
3590 if (active_ifs
.length () > 0
3591 || active_fors
.length () > 0)
3592 fatal_at (token
, "operator-list inside if or for is not supported");
3593 parse_operator_list (token
->src_loc
);
3596 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3597 active_ifs
.length () == 0 && active_fors
.length () == 0
3598 ? "'define_predicates', " : "");
3600 eat_token (CPP_CLOSE_PAREN
);
3603 /* Main entry of the parser. Repeatedly parse outer control structures. */
3605 parser::parser (cpp_reader
*r_
)
3609 active_fors
= vNULL
;
3610 simplifiers
= vNULL
;
3611 oper_lists_set
= NULL
;
3614 user_predicates
= vNULL
;
3615 parsing_match_operand
= false;
3617 const cpp_token
*token
= next ();
3618 while (token
->type
!= CPP_EOF
)
3620 _cpp_backup_tokens (r
, 1);
3627 /* Helper for the linemap code. */
3630 round_alloc_size (size_t s
)
3636 /* The genmatch generator progam. It reads from a pattern description
3637 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3640 main (int argc
, char **argv
)
3644 progname
= "genmatch";
3650 bool verbose
= false;
3651 char *input
= argv
[argc
-1];
3652 for (int i
= 1; i
< argc
- 1; ++i
)
3654 if (strcmp (argv
[i
], "--gimple") == 0)
3656 else if (strcmp (argv
[i
], "--generic") == 0)
3658 else if (strcmp (argv
[i
], "-v") == 0)
3662 fprintf (stderr
, "Usage: genmatch "
3663 "[--gimple] [--generic] [-v] input\n");
3668 line_table
= XCNEW (struct line_maps
);
3669 linemap_init (line_table
, 0);
3670 line_table
->reallocator
= xrealloc
;
3671 line_table
->round_alloc_size
= round_alloc_size
;
3673 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3674 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3675 cb
->error
= error_cb
;
3677 if (!cpp_read_main_file (r
, input
))
3679 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3680 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3682 /* Pre-seed operators. */
3683 operators
= new hash_table
<id_base
> (1024);
3684 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3685 add_operator (SYM, # SYM, # TYPE, NARGS);
3686 #define END_OF_BASE_TREE_CODES
3688 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3689 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3690 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3691 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
3692 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
3693 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
3694 #undef END_OF_BASE_TREE_CODES
3697 /* Pre-seed builtin functions.
3698 ??? Cannot use N (name) as that is targetm.emultls.get_address
3699 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3700 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3701 add_builtin (ENUM, # ENUM);
3702 #include "builtins.def"
3709 write_header (stdout
, "gimple-match-head.c");
3711 write_header (stdout
, "generic-match-head.c");
3713 /* Go over all predicates defined with patterns and perform
3714 lowering and code generation. */
3715 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3717 predicate_id
*pred
= p
.user_predicates
[i
];
3718 lower (pred
->matchers
, gimple
);
3721 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3722 print_matches (pred
->matchers
[i
]);
3725 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3726 dt
.insert (pred
->matchers
[i
], i
);
3731 write_predicate (stdout
, pred
, dt
, gimple
);
3734 /* Lower the main simplifiers and generate code for them. */
3735 lower (p
.simplifiers
, gimple
);
3738 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3739 print_matches (p
.simplifiers
[i
]);
3742 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3743 dt
.insert (p
.simplifiers
[i
], i
);
3749 dt
.gen_gimple (stdout
);
3751 dt
.gen_generic (stdout
);
3754 cpp_finish (r
, NULL
);