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"
32 #include "hash-table.h"
39 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
40 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
41 size_t, size_t MEM_STAT_DECL
)
45 void ggc_free (void *)
52 static struct line_maps
*line_table
;
55 #if GCC_VERSION >= 4001
56 __attribute__((format (printf
, 6, 0)))
58 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
59 unsigned int, const char *msg
, va_list *ap
)
62 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
63 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
64 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
65 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
66 vfprintf (stderr
, msg
, *ap
);
67 fprintf (stderr
, "\n");
68 FILE *f
= fopen (loc
.file
, "r");
74 if (!fgets (buf
, 128, f
))
76 if (buf
[strlen (buf
) - 1] != '\n')
83 fprintf (stderr
, "%s", buf
);
84 for (int i
= 0; i
< loc
.column
- 1; ++i
)
92 if (errtype
== CPP_DL_FATAL
)
98 #if GCC_VERSION >= 4001
99 __attribute__((format (printf
, 2, 3)))
101 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
105 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
110 #if GCC_VERSION >= 4001
111 __attribute__((format (printf
, 2, 3)))
113 fatal_at (source_location loc
, const char *msg
, ...)
117 error_cb (NULL
, CPP_DL_FATAL
, 0, loc
, 0, msg
, &ap
);
122 #if GCC_VERSION >= 4001
123 __attribute__((format (printf
, 2, 3)))
125 warning_at (const cpp_token
*tk
, const char *msg
, ...)
129 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
134 output_line_directive (FILE *f
, source_location location
,
135 bool dumpfile
= false)
138 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
139 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
142 /* When writing to a dumpfile only dump the filename. */
143 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
148 fprintf (f
, "%s:%d", file
, loc
.line
);
151 /* Other gen programs really output line directives here, at least for
152 development it's right now more convenient to have line information
153 from the generated file. Still keep the directives as comment for now
154 to easily back-point to the meta-description. */
155 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
159 /* Pull in tree codes and builtin function codes from their
162 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
172 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
173 enum built_in_function
{
174 #include "builtins.def"
180 /* Base class for all identifiers the parser knows. */
182 struct id_base
: typed_noop_remove
<id_base
>
184 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
186 id_base (id_kind
, const char *, int = -1);
192 /* hash_table support. */
193 typedef id_base value_type
;
194 typedef id_base compare_type
;
195 static inline hashval_t
hash (const value_type
*);
196 static inline int equal (const value_type
*, const compare_type
*);
200 id_base::hash (const value_type
*op
)
206 id_base::equal (const value_type
*op1
,
207 const compare_type
*op2
)
209 return (op1
->hashval
== op2
->hashval
210 && strcmp (op1
->id
, op2
->id
) == 0);
213 /* Hashtable of known pattern operators. This is pre-seeded from
214 all known tree codes and all known builtin function ids. */
215 static hash_table
<id_base
> *operators
;
217 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
222 hashval
= htab_hash_string (id
);
225 /* Identifier that maps to a tree code. */
227 struct operator_id
: public id_base
229 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
231 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
236 /* Identifier that maps to a builtin function code. */
238 struct fn_id
: public id_base
240 fn_id (enum built_in_function fn_
, const char *id_
)
241 : id_base (id_base::FN
, id_
), fn (fn_
) {}
242 enum built_in_function fn
;
247 /* Identifier that maps to a user-defined predicate. */
249 struct predicate_id
: public id_base
251 predicate_id (const char *id_
)
252 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
253 vec
<simplify
*> matchers
;
256 /* Identifier that maps to a operator defined by a 'for' directive. */
258 struct user_id
: public id_base
260 user_id (const char *id_
, bool is_oper_list_
= false)
261 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
262 used (false), is_oper_list (is_oper_list_
) {}
263 vec
<id_base
*> substitutes
;
271 is_a_helper
<fn_id
*>::test (id_base
*id
)
273 return id
->kind
== id_base::FN
;
279 is_a_helper
<operator_id
*>::test (id_base
*id
)
281 return id
->kind
== id_base::CODE
;
287 is_a_helper
<predicate_id
*>::test (id_base
*id
)
289 return id
->kind
== id_base::PREDICATE
;
295 is_a_helper
<user_id
*>::test (id_base
*id
)
297 return id
->kind
== id_base::USER
;
300 /* Add a predicate identifier to the hash. */
302 static predicate_id
*
303 add_predicate (const char *id
)
305 predicate_id
*p
= new predicate_id (id
);
306 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
308 fatal ("duplicate id definition");
313 /* Add a tree code identifier to the hash. */
316 add_operator (enum tree_code code
, const char *id
,
317 const char *tcc
, unsigned nargs
)
319 if (strcmp (tcc
, "tcc_unary") != 0
320 && strcmp (tcc
, "tcc_binary") != 0
321 && strcmp (tcc
, "tcc_comparison") != 0
322 && strcmp (tcc
, "tcc_expression") != 0
323 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
324 && strcmp (tcc
, "tcc_reference") != 0
325 /* To have INTEGER_CST and friends as "predicate operators". */
326 && strcmp (tcc
, "tcc_constant") != 0
327 /* And allow CONSTRUCTOR for vector initializers. */
328 && !(code
== CONSTRUCTOR
))
330 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
331 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
333 fatal ("duplicate id definition");
337 /* Add a builtin identifier to the hash. */
340 add_builtin (enum built_in_function code
, const char *id
)
342 fn_id
*fn
= new fn_id (code
, id
);
343 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
345 fatal ("duplicate id definition");
349 /* Helper for easy comparing ID with tree code CODE. */
352 operator==(id_base
&id
, enum tree_code code
)
354 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
355 return oid
->code
== code
;
359 /* Lookup the identifier ID. */
362 get_operator (const char *id
)
364 id_base
tem (id_base::CODE
, id
);
366 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
369 /* If this is a user-defined identifier track whether it was used. */
370 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
375 /* Try all-uppercase. */
376 char *id2
= xstrdup (id
);
377 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
378 id2
[i
] = TOUPPER (id2
[i
]);
379 new (&tem
) id_base (id_base::CODE
, id2
);
380 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
387 /* Try _EXPR appended. */
388 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
389 strcat (id2
, "_EXPR");
390 new (&tem
) id_base (id_base::CODE
, id2
);
391 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
402 /* Helper for the capture-id map. */
404 struct capture_id_map_hasher
: default_hashmap_traits
406 static inline hashval_t
hash (const char *);
407 static inline bool equal_keys (const char *, const char *);
411 capture_id_map_hasher::hash (const char *id
)
413 return htab_hash_string (id
);
417 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
419 return strcmp (id1
, id2
) == 0;
422 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
425 /* The AST produced by parsing of the pattern definitions. */
430 /* The base class for operands. */
433 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
434 operand (enum op_type type_
) : type (type_
) {}
436 virtual void gen_transform (FILE *, const char *, bool, int,
437 const char *, capture_info
*,
440 { gcc_unreachable (); }
443 /* A predicate operand. Predicates are leafs in the AST. */
445 struct predicate
: public operand
447 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
451 /* An operand that constitutes an expression. Expressions include
452 function calls and user-defined predicate invocations. */
454 struct expr
: public operand
456 expr (id_base
*operation_
, bool is_commutative_
= false)
457 : operand (OP_EXPR
), operation (operation_
),
458 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
459 is_generic (false) {}
460 void append_op (operand
*op
) { ops
.safe_push (op
); }
461 /* The operator and its operands. */
464 /* An explicitely specified type - used exclusively for conversions. */
465 const char *expr_type
;
466 /* Whether the operation is to be applied commutatively. This is
467 later lowered to two separate patterns. */
469 /* Whether the expression is expected to be in GENERIC form. */
471 virtual void gen_transform (FILE *f
, const char *, bool, int,
472 const char *, capture_info
*,
473 dt_operand
** = 0, bool = true);
476 /* An operator that is represented by native C code. This is always
477 a leaf operand in the AST. This class is also used to represent
478 the code to be generated for 'if' and 'with' expressions. */
480 struct c_expr
: public operand
482 /* A mapping of an identifier and its replacement. Used to apply
487 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
490 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
491 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
492 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
493 nr_stmts (nr_stmts_
), ids (ids_
) {}
494 /* cpplib tokens and state to transform this back to source. */
497 cid_map_t
*capture_ids
;
498 /* The number of statements parsed (well, the number of ';'s). */
500 /* The identifier replacement vector. */
502 virtual void gen_transform (FILE *f
, const char *, bool, int,
503 const char *, capture_info
*,
504 dt_operand
** = 0, bool = true);
507 /* A wrapper around another operand that captures its value. */
509 struct capture
: public operand
511 capture (unsigned where_
, operand
*what_
)
512 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
513 /* Identifier index for the value. */
515 /* The captured value. */
517 virtual void gen_transform (FILE *f
, const char *, bool, int,
518 const char *, capture_info
*,
519 dt_operand
** = 0, bool = true);
525 is_a_helper
<capture
*>::test (operand
*op
)
527 return op
->type
== operand::OP_CAPTURE
;
533 is_a_helper
<predicate
*>::test (operand
*op
)
535 return op
->type
== operand::OP_PREDICATE
;
541 is_a_helper
<c_expr
*>::test (operand
*op
)
543 return op
->type
== operand::OP_C_EXPR
;
549 is_a_helper
<expr
*>::test (operand
*op
)
551 return op
->type
== operand::OP_EXPR
;
554 /* Helper to distinguish 'if' from 'with' expressions. */
558 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
559 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
560 source_location location
;
565 /* The main class of a pattern and its transform. This is used to
566 represent both (simplify ...) and (match ...) kinds. The AST
567 duplicates all outer 'if' and 'for' expressions here so each
568 simplify can exist in isolation. */
572 simplify (operand
*match_
, source_location match_location_
,
573 struct operand
*result_
, source_location result_location_
,
574 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
575 cid_map_t
*capture_ids_
)
576 : match (match_
), match_location (match_location_
),
577 result (result_
), result_location (result_location_
),
578 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
579 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
581 /* The expression that is matched against the GENERIC or GIMPLE IL. */
583 source_location match_location
;
584 /* For a (simplify ...) the expression produced when the pattern applies.
585 For a (match ...) either NULL if it is a simple predicate or the
586 single expression specifying the matched operands. */
587 struct operand
*result
;
588 source_location result_location
;
589 /* Collected 'if' expressions that need to evaluate to true to make
590 the pattern apply. */
591 vec
<if_or_with
> ifexpr_vec
;
592 /* Collected 'for' expression operators that have to be replaced
593 in the lowering phase. */
594 vec
<vec
<user_id
*> > for_vec
;
595 /* A map of capture identifiers to indexes. */
596 cid_map_t
*capture_ids
;
600 /* Debugging routines for dumping the AST. */
603 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
605 if (capture
*c
= dyn_cast
<capture
*> (o
))
607 fprintf (f
, "@%u", c
->where
);
608 if (c
->what
&& flattened
== false)
611 print_operand (c
->what
, f
, flattened
);
616 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
617 fprintf (f
, "%s", p
->p
->id
);
619 else if (is_a
<c_expr
*> (o
))
620 fprintf (f
, "c_expr");
622 else if (expr
*e
= dyn_cast
<expr
*> (o
))
624 fprintf (f
, "(%s", e
->operation
->id
);
626 if (flattened
== false)
629 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
631 print_operand (e
->ops
[i
], f
, flattened
);
643 print_matches (struct simplify
*s
, FILE *f
= stderr
)
645 fprintf (f
, "for expression: ");
646 print_operand (s
->match
, f
);
653 /* Lowering of commutative operators. */
656 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
657 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
659 if (n
== ops_vector
.length ())
661 vec
<operand
*> xv
= v
.copy ();
662 result
.safe_push (xv
);
666 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
668 v
[n
] = ops_vector
[n
][i
];
669 cartesian_product (ops_vector
, result
, v
, n
+ 1);
673 /* Lower OP to two operands in case it is marked as commutative. */
675 static vec
<operand
*>
676 commutate (operand
*op
)
678 vec
<operand
*> ret
= vNULL
;
680 if (capture
*c
= dyn_cast
<capture
*> (op
))
687 vec
<operand
*> v
= commutate (c
->what
);
688 for (unsigned i
= 0; i
< v
.length (); ++i
)
690 capture
*nc
= new capture (c
->where
, v
[i
]);
696 expr
*e
= dyn_cast
<expr
*> (op
);
697 if (!e
|| e
->ops
.length () == 0)
703 vec
< vec
<operand
*> > ops_vector
= vNULL
;
704 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
705 ops_vector
.safe_push (commutate (e
->ops
[i
]));
707 auto_vec
< vec
<operand
*> > result
;
708 auto_vec
<operand
*> v (e
->ops
.length ());
709 v
.quick_grow_cleared (e
->ops
.length ());
710 cartesian_product (ops_vector
, result
, v
, 0);
713 for (unsigned i
= 0; i
< result
.length (); ++i
)
715 expr
*ne
= new expr (e
->operation
);
716 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
717 ne
->append_op (result
[i
][j
]);
721 if (!e
->is_commutative
)
724 for (unsigned i
= 0; i
< result
.length (); ++i
)
726 expr
*ne
= new expr (e
->operation
);
727 // result[i].length () is 2 since e->operation is binary
728 for (unsigned j
= result
[i
].length (); j
; --j
)
729 ne
->append_op (result
[i
][j
-1]);
736 /* Lower operations marked as commutative in the AST of S and push
737 the resulting patterns to SIMPLIFIERS. */
740 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
742 vec
<operand
*> matchers
= commutate (s
->match
);
743 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
745 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
746 s
->result
, s
->result_location
, s
->ifexpr_vec
,
747 s
->for_vec
, s
->capture_ids
);
748 simplifiers
.safe_push (ns
);
752 /* Strip conditional conversios using operator OPER from O and its
753 children if STRIP, else replace them with an unconditional convert. */
756 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
758 if (capture
*c
= dyn_cast
<capture
*> (o
))
761 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
766 expr
*e
= dyn_cast
<expr
*> (o
);
770 if (*e
->operation
== oper
)
773 return lower_opt_convert (e
->ops
[0], oper
, strip
);
775 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
776 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
780 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
781 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
782 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
787 /* Determine whether O or its children uses the conditional conversion
791 has_opt_convert (operand
*o
, enum tree_code oper
)
793 if (capture
*c
= dyn_cast
<capture
*> (o
))
796 return has_opt_convert (c
->what
, oper
);
801 expr
*e
= dyn_cast
<expr
*> (o
);
805 if (*e
->operation
== oper
)
808 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
809 if (has_opt_convert (e
->ops
[i
], oper
))
815 /* Lower conditional convert operators in O, expanding it to a vector
818 static vec
<operand
*>
819 lower_opt_convert (operand
*o
)
821 vec
<operand
*> v1
= vNULL
, v2
;
825 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
827 /* Conditional converts are lowered to a pattern with the
828 conversion and one without. The three different conditional
829 convert codes are lowered separately. */
831 for (unsigned i
= 0; i
< 3; ++i
)
834 for (unsigned j
= 0; j
< v1
.length (); ++j
)
835 if (has_opt_convert (v1
[j
], opers
[i
]))
837 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
838 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
844 for (unsigned j
= 0; j
< v2
.length (); ++j
)
845 v1
.safe_push (v2
[j
]);
852 /* Lower conditional convert operators in the AST of S and push
853 the resulting multiple patterns to SIMPLIFIERS. */
856 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
858 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
859 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
861 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
862 s
->result
, s
->result_location
, s
->ifexpr_vec
,
863 s
->for_vec
, s
->capture_ids
);
864 simplifiers
.safe_push (ns
);
868 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
869 GENERIC and a GIMPLE variant. */
871 static vec
<operand
*>
872 lower_cond (operand
*o
)
874 vec
<operand
*> ro
= vNULL
;
876 if (capture
*c
= dyn_cast
<capture
*> (o
))
880 vec
<operand
*> lop
= vNULL
;
881 lop
= lower_cond (c
->what
);
883 for (unsigned i
= 0; i
< lop
.length (); ++i
)
884 ro
.safe_push (new capture (c
->where
, lop
[i
]));
889 expr
*e
= dyn_cast
<expr
*> (o
);
890 if (!e
|| e
->ops
.length () == 0)
896 vec
< vec
<operand
*> > ops_vector
= vNULL
;
897 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
898 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
900 auto_vec
< vec
<operand
*> > result
;
901 auto_vec
<operand
*> v (e
->ops
.length ());
902 v
.quick_grow_cleared (e
->ops
.length ());
903 cartesian_product (ops_vector
, result
, v
, 0);
905 for (unsigned i
= 0; i
< result
.length (); ++i
)
907 expr
*ne
= new expr (e
->operation
);
908 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
909 ne
->append_op (result
[i
][j
]);
911 /* If this is a COND with a captured expression or an
912 expression with two operands then also match a GENERIC
913 form on the compare. */
914 if ((*e
->operation
== COND_EXPR
915 || *e
->operation
== VEC_COND_EXPR
)
916 && ((is_a
<capture
*> (e
->ops
[0])
917 && as_a
<capture
*> (e
->ops
[0])->what
918 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
920 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
921 || (is_a
<expr
*> (e
->ops
[0])
922 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
924 expr
*ne
= new expr (e
->operation
);
925 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
926 ne
->append_op (result
[i
][j
]);
927 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
929 expr
*ocmp
= as_a
<expr
*> (c
->what
);
930 expr
*cmp
= new expr (ocmp
->operation
);
931 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
932 cmp
->append_op (ocmp
->ops
[j
]);
933 cmp
->is_generic
= true;
934 ne
->ops
[0] = new capture (c
->where
, cmp
);
938 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
939 expr
*cmp
= new expr (ocmp
->operation
);
940 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
941 cmp
->append_op (ocmp
->ops
[j
]);
942 cmp
->is_generic
= true;
952 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
953 GENERIC and a GIMPLE variant. */
956 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
958 vec
<operand
*> matchers
= lower_cond (s
->match
);
959 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
961 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
962 s
->result
, s
->result_location
, s
->ifexpr_vec
,
963 s
->for_vec
, s
->capture_ids
);
964 simplifiers
.safe_push (ns
);
968 /* In AST operand O replace operator ID with operator WITH. */
971 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
973 /* Deep-copy captures and expressions, replacing operations as
975 if (capture
*c
= dyn_cast
<capture
*> (o
))
979 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
981 else if (expr
*e
= dyn_cast
<expr
*> (o
))
983 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
985 ne
->expr_type
= e
->expr_type
;
986 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
987 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
991 /* For c_expr we simply record a string replacement table which is
992 applied at code-generation time. */
993 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
995 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
996 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
997 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1003 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1006 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1008 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1009 unsigned worklist_start
= 0;
1010 auto_vec
<simplify
*> worklist
;
1011 worklist
.safe_push (sin
);
1013 /* Lower each recorded for separately, operating on the
1014 set of simplifiers created by the previous one.
1015 Lower inner-to-outer so inner for substitutes can refer
1016 to operators replaced by outer fors. */
1017 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1019 vec
<user_id
*>& ids
= for_vec
[fi
];
1020 unsigned n_ids
= ids
.length ();
1021 unsigned max_n_opers
= 0;
1022 for (unsigned i
= 0; i
< n_ids
; ++i
)
1023 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1024 max_n_opers
= ids
[i
]->substitutes
.length ();
1026 unsigned worklist_end
= worklist
.length ();
1027 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1029 simplify
*s
= worklist
[si
];
1030 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1032 operand
*match_op
= s
->match
;
1033 operand
*result_op
= s
->result
;
1034 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1036 for (unsigned i
= 0; i
< n_ids
; ++i
)
1038 user_id
*id
= ids
[i
];
1039 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1040 match_op
= replace_id (match_op
, id
, oper
);
1042 result_op
= replace_id (result_op
, id
, oper
);
1043 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1044 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1047 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1048 result_op
, s
->result_location
,
1049 ifexpr_vec
, vNULL
, s
->capture_ids
);
1050 worklist
.safe_push (ns
);
1053 worklist_start
= worklist_end
;
1056 /* Copy out the result from the last for lowering. */
1057 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1058 simplifiers
.safe_push (worklist
[i
]);
1061 /* Lower the AST for everything in SIMPLIFIERS. */
1064 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1066 auto_vec
<simplify
*> out_simplifiers
;
1067 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1068 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1070 simplifiers
.truncate (0);
1071 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1072 lower_commutative (out_simplifiers
[i
], simplifiers
);
1074 out_simplifiers
.truncate (0);
1076 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1077 lower_cond (simplifiers
[i
], out_simplifiers
);
1079 out_simplifiers
.safe_splice (simplifiers
);
1082 simplifiers
.truncate (0);
1083 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1084 lower_for (out_simplifiers
[i
], simplifiers
);
1090 /* The decision tree built for generating GIMPLE and GENERIC pattern
1091 matching code. It represents the 'match' expression of all
1092 simplifies and has those as its leafs. */
1094 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1098 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1102 vec
<dt_node
*> kids
;
1104 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1106 dt_node
*append_node (dt_node
*);
1107 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1108 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1109 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1110 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1112 virtual void gen (FILE *, bool) {}
1114 void gen_kids (FILE *, bool);
1115 void gen_kids_1 (FILE *, bool,
1116 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1117 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1120 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1122 struct dt_operand
: public dt_node
1125 dt_operand
*match_dop
;
1129 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1130 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1131 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1132 parent (parent_
), pos (pos_
) {}
1134 void gen (FILE *, bool);
1135 unsigned gen_predicate (FILE *, const char *, bool);
1136 unsigned gen_match_op (FILE *, const char *);
1138 unsigned gen_gimple_expr (FILE *);
1139 unsigned gen_generic_expr (FILE *, const char *);
1141 char *get_name (char *);
1142 void gen_opname (char *, unsigned);
1145 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1147 struct dt_simplify
: public dt_node
1150 unsigned pattern_no
;
1151 dt_operand
**indexes
;
1153 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1154 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1155 indexes (indexes_
) {}
1157 void gen (FILE *f
, bool);
1163 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1165 return (n
->type
== dt_node::DT_OPERAND
1166 || n
->type
== dt_node::DT_MATCH
);
1169 /* A container for the actual decision tree. */
1171 struct decision_tree
1175 void insert (struct simplify
*, unsigned);
1176 void gen_gimple (FILE *f
= stderr
);
1177 void gen_generic (FILE *f
= stderr
);
1178 void print (FILE *f
= stderr
);
1180 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1182 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1183 unsigned pos
= 0, dt_node
*parent
= 0);
1184 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1185 static bool cmp_node (dt_node
*, dt_node
*);
1186 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1189 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1192 cmp_operand (operand
*o1
, operand
*o2
)
1194 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1197 if (o1
->type
== operand::OP_PREDICATE
)
1199 predicate
*p1
= as_a
<predicate
*>(o1
);
1200 predicate
*p2
= as_a
<predicate
*>(o2
);
1201 return p1
->p
== p2
->p
;
1203 else if (o1
->type
== operand::OP_EXPR
)
1205 expr
*e1
= static_cast<expr
*>(o1
);
1206 expr
*e2
= static_cast<expr
*>(o2
);
1207 return (e1
->operation
== e2
->operation
1208 && e1
->is_generic
== e2
->is_generic
);
1214 /* Compare two decision tree nodes N1 and N2 and return true if they
1218 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1220 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1226 if (n1
->type
== dt_node::DT_TRUE
)
1229 if (n1
->type
== dt_node::DT_OPERAND
)
1230 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1231 (as_a
<dt_operand
*> (n2
))->op
);
1232 else if (n1
->type
== dt_node::DT_MATCH
)
1233 return ((as_a
<dt_operand
*> (n1
))->match_dop
1234 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1238 /* Search OPS for a decision tree node like P and return it if found. */
1241 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1243 /* We can merge adjacent DT_TRUE. */
1244 if (p
->type
== dt_node::DT_TRUE
1246 && ops
.last ()->type
== dt_node::DT_TRUE
)
1248 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1250 /* But we can't merge across DT_TRUE nodes as they serve as
1251 pattern order barriers to make sure that patterns apply
1252 in order of appearance in case multiple matches are possible. */
1253 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1255 if (decision_tree::cmp_node (ops
[i
], p
))
1261 /* Append N to the decision tree if it there is not already an existing
1265 dt_node::append_node (dt_node
*n
)
1269 kid
= decision_tree::find_node (kids
, n
);
1274 n
->level
= this->level
+ 1;
1279 /* Append OP to the decision tree. */
1282 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1284 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1285 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1286 return append_node (n
);
1289 /* Append a DT_TRUE decision tree node. */
1292 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1294 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1295 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1296 return append_node (n
);
1299 /* Append a DT_MATCH decision tree node. */
1302 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1304 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1305 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1306 return append_node (n
);
1309 /* Append S to the decision tree. */
1312 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1313 dt_operand
**indexes
)
1315 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1316 return append_node (n
);
1319 /* Insert O into the decision tree and return the decision tree node found
1323 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1324 unsigned pos
, dt_node
*parent
)
1326 dt_node
*q
, *elm
= 0;
1328 if (capture
*c
= dyn_cast
<capture
*> (o
))
1330 unsigned capt_index
= c
->where
;
1332 if (indexes
[capt_index
] == 0)
1335 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1338 q
= elm
= p
->append_true_op (parent
, pos
);
1341 // get to the last capture
1342 for (operand
*what
= c
->what
;
1343 what
&& is_a
<capture
*> (what
);
1344 c
= as_a
<capture
*> (what
), what
= c
->what
)
1349 unsigned cc_index
= c
->where
;
1350 dt_operand
*match_op
= indexes
[cc_index
];
1352 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1353 elm
= decision_tree::find_node (p
->kids
, &temp
);
1357 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1358 elm
= decision_tree::find_node (p
->kids
, &temp
);
1363 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1364 elm
= decision_tree::find_node (p
->kids
, &temp
);
1368 gcc_assert (elm
->type
== dt_node::DT_TRUE
1369 || elm
->type
== dt_node::DT_OPERAND
1370 || elm
->type
== dt_node::DT_MATCH
);
1371 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1376 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1378 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1383 p
= p
->append_op (o
, parent
, pos
);
1386 if (expr
*e
= dyn_cast
<expr
*>(o
))
1388 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1389 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1395 /* Insert S into the decision tree. */
1398 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1400 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1401 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1402 p
->append_simplify (s
, pattern_no
, indexes
);
1405 /* Debug functions to dump the decision tree. */
1408 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1410 if (p
->type
== dt_node::DT_NODE
)
1411 fprintf (f
, "root");
1415 for (unsigned i
= 0; i
< indent
; i
++)
1418 if (p
->type
== dt_node::DT_OPERAND
)
1420 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1421 print_operand (dop
->op
, f
, true);
1423 else if (p
->type
== dt_node::DT_TRUE
)
1424 fprintf (f
, "true");
1425 else if (p
->type
== dt_node::DT_MATCH
)
1426 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1427 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1429 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1430 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1431 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1432 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1437 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1439 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1440 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1444 decision_tree::print (FILE *f
)
1446 return decision_tree::print_node (root
, f
);
1450 /* For GENERIC we have to take care of wrapping multiple-used
1451 expressions with side-effects in save_expr and preserve side-effects
1452 of expressions with omit_one_operand. Analyze captures in
1453 match, result and with expressions and perform early-outs
1454 on the outermost match expression operands for cases we cannot
1459 capture_info (simplify
*s
);
1460 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1461 void walk_result (operand
*o
, bool);
1462 void walk_c_expr (c_expr
*);
1468 bool force_no_side_effects_p
;
1469 bool cond_expr_cond_p
;
1470 unsigned long toplevel_msk
;
1471 int result_use_count
;
1474 auto_vec
<cinfo
> info
;
1475 unsigned long force_no_side_effects
;
1478 /* Analyze captures in S. */
1480 capture_info::capture_info (simplify
*s
)
1484 || ((e
= dyn_cast
<expr
*> (s
->result
))
1485 && is_a
<predicate_id
*> (e
->operation
)))
1487 force_no_side_effects
= -1;
1491 force_no_side_effects
= 0;
1492 info
.safe_grow_cleared (s
->capture_max
+ 1);
1493 e
= as_a
<expr
*> (s
->match
);
1494 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1495 walk_match (e
->ops
[i
], i
,
1496 (i
!= 0 && *e
->operation
== COND_EXPR
)
1497 || *e
->operation
== TRUTH_ANDIF_EXPR
1498 || *e
->operation
== TRUTH_ORIF_EXPR
,
1500 && (*e
->operation
== COND_EXPR
1501 || *e
->operation
== VEC_COND_EXPR
));
1503 walk_result (s
->result
, false);
1505 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1506 if (s
->ifexpr_vec
[i
].is_with
)
1507 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1510 /* Analyze captures in the match expression piece O. */
1513 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1514 bool conditional_p
, bool cond_expr_cond_p
)
1516 if (capture
*c
= dyn_cast
<capture
*> (o
))
1518 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1519 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1520 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1521 /* Mark expr (non-leaf) captures and recurse. */
1523 && is_a
<expr
*> (c
->what
))
1525 info
[c
->where
].expr_p
= true;
1526 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1529 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1531 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1533 bool cond_p
= conditional_p
;
1534 bool cond_expr_cond_p
= false;
1535 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1537 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1538 || *e
->operation
== TRUTH_ORIF_EXPR
)
1541 && (*e
->operation
== COND_EXPR
1542 || *e
->operation
== VEC_COND_EXPR
))
1543 cond_expr_cond_p
= true;
1544 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1547 else if (is_a
<predicate
*> (o
))
1549 /* Mark non-captured leafs toplevel arg for checking. */
1550 force_no_side_effects
|= 1 << toplevel_arg
;
1556 /* Analyze captures in the result expression piece O. */
1559 capture_info::walk_result (operand
*o
, bool conditional_p
)
1561 if (capture
*c
= dyn_cast
<capture
*> (o
))
1563 info
[c
->where
].result_use_count
++;
1564 /* If we substitute an expression capture we don't know
1565 which captures this will end up using (well, we don't
1566 compute that). Force the uses to be side-effect free
1567 which means forcing the toplevels that reach the
1568 expression side-effect free. */
1569 if (info
[c
->where
].expr_p
)
1570 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1571 /* Mark CSE capture capture uses as forced to have
1574 && is_a
<expr
*> (c
->what
))
1576 info
[c
->where
].cse_p
= true;
1577 walk_result (c
->what
, true);
1580 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1582 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1584 bool cond_p
= conditional_p
;
1585 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1587 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1588 || *e
->operation
== TRUTH_ORIF_EXPR
)
1590 walk_result (e
->ops
[i
], cond_p
);
1593 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1599 /* Look for captures in the C expr E. */
1602 capture_info::walk_c_expr (c_expr
*e
)
1604 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1605 unsigned p_depth
= 0;
1606 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1608 const cpp_token
*t
= &e
->code
[i
];
1609 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1610 if (t
->type
== CPP_NAME
1611 && strcmp ((const char *)CPP_HASHNODE
1612 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1613 && n
->type
== CPP_OPEN_PAREN
)
1615 else if (t
->type
== CPP_CLOSE_PAREN
1618 else if (p_depth
== 0
1619 && t
->type
== CPP_ATSIGN
1620 && (n
->type
== CPP_NUMBER
1621 || n
->type
== CPP_NAME
)
1622 && !(n
->flags
& PREV_WHITE
))
1625 if (n
->type
== CPP_NUMBER
)
1626 id
= (const char *)n
->val
.str
.text
;
1628 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1629 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1635 /* Code generation off the decision tree and the refered AST nodes. */
1638 is_conversion (id_base
*op
)
1640 return (*op
== CONVERT_EXPR
1642 || *op
== FLOAT_EXPR
1643 || *op
== FIX_TRUNC_EXPR
1644 || *op
== VIEW_CONVERT_EXPR
);
1647 /* Get the type to be used for generating operands of OP from the
1651 get_operand_type (id_base
*op
, const char *in_type
,
1652 const char *expr_type
,
1653 const char *other_oprnd_type
)
1655 /* Generally operands whose type does not match the type of the
1656 expression generated need to know their types but match and
1657 thus can fall back to 'other_oprnd_type'. */
1658 if (is_conversion (op
))
1659 return other_oprnd_type
;
1660 else if (*op
== REALPART_EXPR
1661 || *op
== IMAGPART_EXPR
)
1662 return other_oprnd_type
;
1663 else if (is_a
<operator_id
*> (op
)
1664 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1665 return other_oprnd_type
;
1668 /* Otherwise all types should match - choose one in order of
1675 return other_oprnd_type
;
1679 /* Generate transform code for an expression. */
1682 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1683 const char *in_type
, capture_info
*cinfo
,
1684 dt_operand
**indexes
, bool)
1686 bool conversion_p
= is_conversion (operation
);
1687 const char *type
= expr_type
;
1690 /* If there was a type specification in the pattern use it. */
1692 else if (conversion_p
)
1693 /* For conversions we need to build the expression using the
1694 outer type passed in. */
1696 else if (*operation
== REALPART_EXPR
1697 || *operation
== IMAGPART_EXPR
)
1699 /* __real and __imag use the component type of its operand. */
1700 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1703 else if (is_a
<operator_id
*> (operation
)
1704 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1706 /* comparisons use boolean_type_node (or what gets in), but
1707 their operands need to figure out the types themselves. */
1708 sprintf (optype
, "boolean_type_node");
1713 /* Other operations are of the same type as their first operand. */
1714 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1718 fatal ("two conversions in a row");
1721 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1723 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1724 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1727 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1729 = get_operand_type (operation
, in_type
, expr_type
,
1730 i
== 0 ? NULL
: op0type
);
1731 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1732 ((!(*operation
== COND_EXPR
)
1733 && !(*operation
== VEC_COND_EXPR
))
1738 if (*operation
== CONVERT_EXPR
)
1741 opr
= operation
->id
;
1745 /* ??? Have another helper that is like gimple_build but may
1746 fail if seq == NULL. */
1747 fprintf (f
, " if (!seq)\n"
1749 " res = gimple_simplify (%s, %s", opr
, type
);
1750 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1751 fprintf (f
, ", ops%d[%u]", depth
, i
);
1752 fprintf (f
, ", seq, valueize);\n");
1753 fprintf (f
, " if (!res) return false;\n");
1754 fprintf (f
, " }\n");
1755 fprintf (f
, " else\n");
1756 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1758 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1759 fprintf (f
, ", ops%d[%u]", depth
, i
);
1760 fprintf (f
, ", valueize);\n");
1764 if (operation
->kind
== id_base::CODE
)
1765 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1766 ops
.length(), opr
, type
);
1768 fprintf (f
, " res = build_call_expr_loc (loc, "
1769 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1770 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1771 fprintf (f
, ", ops%d[%u]", depth
, i
);
1772 fprintf (f
, ");\n");
1774 fprintf (f
, " %s = res;\n", dest
);
1778 /* Generate code for a c_expr which is either the expression inside
1779 an if statement or a sequence of statements which computes a
1780 result to be stored to DEST. */
1783 c_expr::gen_transform (FILE *f
, const char *dest
,
1784 bool, int, const char *, capture_info
*,
1785 dt_operand
**, bool)
1787 if (dest
&& nr_stmts
== 1)
1788 fprintf (f
, "%s = ", dest
);
1790 unsigned stmt_nr
= 1;
1791 for (unsigned i
= 0; i
< code
.length (); ++i
)
1793 const cpp_token
*token
= &code
[i
];
1795 /* Replace captures for code-gen. */
1796 if (token
->type
== CPP_ATSIGN
)
1798 const cpp_token
*n
= &code
[i
+1];
1799 if ((n
->type
== CPP_NUMBER
1800 || n
->type
== CPP_NAME
)
1801 && !(n
->flags
& PREV_WHITE
))
1803 if (token
->flags
& PREV_WHITE
)
1806 if (n
->type
== CPP_NUMBER
)
1807 id
= (const char *)n
->val
.str
.text
;
1809 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1810 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1816 if (token
->flags
& PREV_WHITE
)
1819 if (token
->type
== CPP_NAME
)
1821 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1823 for (j
= 0; j
< ids
.length (); ++j
)
1825 if (strcmp (id
, ids
[j
].id
) == 0)
1827 fprintf (f
, "%s", ids
[j
].oper
);
1831 if (j
< ids
.length ())
1835 /* Output the token as string. */
1836 char *tk
= (char *)cpp_token_as_text (r
, token
);
1839 if (token
->type
== CPP_SEMICOLON
)
1842 if (dest
&& stmt_nr
== nr_stmts
)
1843 fprintf (f
, "\n %s = ", dest
);
1850 /* Generate transform code for a capture. */
1853 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1854 const char *in_type
, capture_info
*cinfo
,
1855 dt_operand
**indexes
, bool expand_compares
)
1857 if (what
&& is_a
<expr
*> (what
))
1859 if (indexes
[where
] == 0)
1862 sprintf (buf
, "captures[%u]", where
);
1863 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1867 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1869 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1870 with substituting a capture of that.
1871 ??? Returning false here will also not allow any other patterns
1873 if (gimple
&& expand_compares
1874 && cinfo
->info
[where
].cond_expr_cond_p
)
1875 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1877 " if (!seq) return false;\n"
1878 " %s = gimple_build (seq, TREE_CODE (%s),"
1879 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1880 " TREE_OPERAND (%s, 1));\n"
1881 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1884 /* Return the name of the operand representing the decision tree node.
1885 Use NAME as space to generate it. */
1888 dt_operand::get_name (char *name
)
1891 sprintf (name
, "t");
1892 else if (parent
->level
== 1)
1893 sprintf (name
, "op%u", pos
);
1894 else if (parent
->type
== dt_node::DT_MATCH
)
1895 return parent
->get_name (name
);
1897 sprintf (name
, "o%u%u", parent
->level
, pos
);
1901 /* Fill NAME with the operand name at position POS. */
1904 dt_operand::gen_opname (char *name
, unsigned pos
)
1907 sprintf (name
, "op%u", pos
);
1909 sprintf (name
, "o%u%u", level
, pos
);
1912 /* Generate matching code for the decision tree operand which is
1916 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1918 predicate
*p
= as_a
<predicate
*> (op
);
1920 if (p
->p
->matchers
.exists ())
1922 /* If this is a predicate generated from a pattern mangle its
1923 name and pass on the valueize hook. */
1925 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1927 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1930 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1935 /* Generate matching code for the decision tree operand which is
1939 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1941 char match_opname
[20];
1942 match_dop
->get_name (match_opname
);
1943 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1944 opname
, match_opname
, opname
, match_opname
);
1949 /* Generate GIMPLE matching code for the decision tree operand. */
1952 dt_operand::gen_gimple_expr (FILE *f
)
1954 expr
*e
= static_cast<expr
*> (op
);
1955 id_base
*id
= e
->operation
;
1956 unsigned n_ops
= e
->ops
.length ();
1958 for (unsigned i
= 0; i
< n_ops
; ++i
)
1960 char child_opname
[20];
1961 gen_opname (child_opname
, i
);
1963 if (id
->kind
== id_base::CODE
)
1966 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1967 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1969 /* ??? If this is a memory operation we can't (and should not)
1970 match this. The only sensible operand types are
1971 SSA names and invariants. */
1972 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1974 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1975 "|| is_gimple_min_invariant (%s))\n"
1976 "&& (%s = do_valueize (valueize, %s)))\n"
1977 "{\n", child_opname
, child_opname
, child_opname
,
1982 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1983 child_opname
, i
+ 1);
1986 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1988 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1989 child_opname
, child_opname
);
1996 /* Generate GENERIC matching code for the decision tree operand. */
1999 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
2001 expr
*e
= static_cast<expr
*> (op
);
2002 unsigned n_ops
= e
->ops
.length ();
2004 for (unsigned i
= 0; i
< n_ops
; ++i
)
2006 char child_opname
[20];
2007 gen_opname (child_opname
, i
);
2009 if (e
->operation
->kind
== id_base::CODE
)
2010 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2011 child_opname
, opname
, i
);
2013 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2014 child_opname
, opname
, i
);
2020 /* Generate matching code for the children of the decision tree node. */
2023 dt_node::gen_kids (FILE *f
, bool gimple
)
2025 auto_vec
<dt_operand
*> gimple_exprs
;
2026 auto_vec
<dt_operand
*> generic_exprs
;
2027 auto_vec
<dt_operand
*> fns
;
2028 auto_vec
<dt_operand
*> generic_fns
;
2029 auto_vec
<dt_operand
*> preds
;
2030 auto_vec
<dt_node
*> others
;
2032 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2034 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2036 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2037 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2039 if (e
->ops
.length () == 0
2040 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2041 generic_exprs
.safe_push (op
);
2042 else if (e
->operation
->kind
== id_base::FN
)
2047 generic_fns
.safe_push (op
);
2049 else if (e
->operation
->kind
== id_base::PREDICATE
)
2050 preds
.safe_push (op
);
2054 gimple_exprs
.safe_push (op
);
2056 generic_exprs
.safe_push (op
);
2059 else if (op
->op
->type
== operand::OP_PREDICATE
)
2060 others
.safe_push (kids
[i
]);
2064 else if (kids
[i
]->type
== dt_node::DT_MATCH
2065 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2066 others
.safe_push (kids
[i
]);
2067 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2069 /* A DT_TRUE operand serves as a barrier - generate code now
2070 for what we have collected sofar. */
2071 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2072 fns
, generic_fns
, preds
, others
);
2073 /* And output the true operand itself. */
2074 kids
[i
]->gen (f
, gimple
);
2075 gimple_exprs
.truncate (0);
2076 generic_exprs
.truncate (0);
2078 generic_fns
.truncate (0);
2080 others
.truncate (0);
2086 /* Generate code for the remains. */
2087 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2088 fns
, generic_fns
, preds
, others
);
2091 /* Generate matching code for the children of the decision tree node. */
2094 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2095 vec
<dt_operand
*> gimple_exprs
,
2096 vec
<dt_operand
*> generic_exprs
,
2097 vec
<dt_operand
*> fns
,
2098 vec
<dt_operand
*> generic_fns
,
2099 vec
<dt_operand
*> preds
,
2100 vec
<dt_node
*> others
)
2103 char *kid_opname
= buf
;
2105 unsigned exprs_len
= gimple_exprs
.length ();
2106 unsigned gexprs_len
= generic_exprs
.length ();
2107 unsigned fns_len
= fns
.length ();
2108 unsigned gfns_len
= generic_fns
.length ();
2110 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2113 gimple_exprs
[0]->get_name (kid_opname
);
2115 fns
[0]->get_name (kid_opname
);
2117 generic_fns
[0]->get_name (kid_opname
);
2119 generic_exprs
[0]->get_name (kid_opname
);
2121 fprintf (f
, "switch (TREE_CODE (%s))\n"
2125 if (exprs_len
|| fns_len
)
2127 fprintf (f
, "case SSA_NAME:\n");
2128 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2130 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2134 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2135 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2137 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2139 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2140 id_base
*op
= e
->operation
;
2141 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2142 fprintf (f
, "CASE_CONVERT:\n");
2144 fprintf (f
, "case %s:\n", op
->id
);
2146 gimple_exprs
[i
]->gen (f
, true);
2147 fprintf (f
, "break;\n"
2150 fprintf (f
, "default:;\n"
2157 fprintf (f
, "else ");
2159 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2161 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2162 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2165 for (unsigned i
= 0; i
< fns_len
; ++i
)
2167 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2168 fprintf (f
, "case %s:\n"
2169 "{\n", e
->operation
->id
);
2170 fns
[i
]->gen (f
, true);
2171 fprintf (f
, "break;\n"
2175 fprintf (f
, "default:;\n"
2184 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2186 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2187 id_base
*op
= e
->operation
;
2188 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2189 fprintf (f
, "CASE_CONVERT:\n");
2191 fprintf (f
, "case %s:\n", op
->id
);
2193 generic_exprs
[i
]->gen (f
, gimple
);
2194 fprintf (f
, "break;\n"
2200 fprintf (f
, "case CALL_EXPR:\n"
2202 "tree fndecl = get_callee_fndecl (%s);\n"
2203 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2204 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2207 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2209 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2210 gcc_assert (e
->operation
->kind
== id_base::FN
);
2212 fprintf (f
, "case %s:\n"
2213 "{\n", e
->operation
->id
);
2214 generic_fns
[j
]->gen (f
, false);
2215 fprintf (f
, "break;\n"
2219 fprintf (f
, "default:;\n"
2225 /* Close switch (TREE_CODE ()). */
2226 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2227 fprintf (f
, "default:;\n"
2230 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2232 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2233 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2234 preds
[i
]->get_name (kid_opname
);
2235 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2236 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2237 gimple
? "gimple" : "tree",
2238 p
->id
, kid_opname
, kid_opname
,
2239 gimple
? ", valueize" : "");
2241 for (int j
= 0; j
< p
->nargs
; ++j
)
2243 char child_opname
[20];
2244 preds
[i
]->gen_opname (child_opname
, j
);
2245 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2247 preds
[i
]->gen_kids (f
, gimple
);
2251 for (unsigned i
= 0; i
< others
.length (); ++i
)
2252 others
[i
]->gen (f
, gimple
);
2255 /* Generate matching code for the decision tree operand. */
2258 dt_operand::gen (FILE *f
, bool gimple
)
2263 unsigned n_braces
= 0;
2265 if (type
== DT_OPERAND
)
2268 case operand::OP_PREDICATE
:
2269 n_braces
= gen_predicate (f
, opname
, gimple
);
2272 case operand::OP_EXPR
:
2274 n_braces
= gen_gimple_expr (f
);
2276 n_braces
= gen_generic_expr (f
, opname
);
2282 else if (type
== DT_TRUE
)
2284 else if (type
== DT_MATCH
)
2285 n_braces
= gen_match_op (f
, opname
);
2289 gen_kids (f
, gimple
);
2291 for (unsigned i
= 0; i
< n_braces
; ++i
)
2297 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2298 step of a '(simplify ...)' or '(match ...)'. This handles everything
2299 that is not part of the decision tree (simplify->match). */
2302 dt_simplify::gen (FILE *f
, bool gimple
)
2305 output_line_directive (f
, s
->result_location
);
2306 if (s
->capture_max
>= 0)
2307 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2308 s
->capture_max
+ 1);
2310 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2314 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2317 unsigned n_braces
= 0;
2318 if (s
->ifexpr_vec
!= vNULL
)
2320 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2322 if_or_with
&w
= s
->ifexpr_vec
[i
];
2326 output_line_directive (f
, w
.location
);
2327 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2332 output_line_directive (f
, w
.location
);
2333 fprintf (f
, "if (");
2334 if (i
== s
->ifexpr_vec
.length () - 1
2335 || s
->ifexpr_vec
[i
+1].is_with
)
2336 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2345 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2349 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2355 while (j
< s
->ifexpr_vec
.length ()
2356 && !s
->ifexpr_vec
[j
].is_with
);
2366 /* Analyze captures and perform early-outs on the incoming arguments
2367 that cover cases we cannot handle. */
2368 capture_info
cinfo (s
);
2372 && !((e
= dyn_cast
<expr
*> (s
->result
))
2373 && is_a
<predicate_id
*> (e
->operation
)))
2375 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2376 if (cinfo
.force_no_side_effects
& (1 << i
))
2377 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2378 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2379 if (cinfo
.info
[i
].cse_p
)
2381 else if (cinfo
.info
[i
].force_no_side_effects_p
2382 && (cinfo
.info
[i
].toplevel_msk
2383 & cinfo
.force_no_side_effects
) == 0)
2384 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2385 "return NULL_TREE;\n", i
);
2386 else if ((cinfo
.info
[i
].toplevel_msk
2387 & cinfo
.force_no_side_effects
) != 0)
2388 /* Mark capture as having no side-effects if we had to verify
2389 that via forced toplevel operand checks. */
2390 cinfo
.info
[i
].force_no_side_effects_p
= true;
2393 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2394 "fprintf (dump_file, \"Applying pattern ");
2395 output_line_directive (f
, s
->result_location
, true);
2396 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2398 operand
*result
= s
->result
;
2401 /* If there is no result then this is a predicate implementation. */
2402 fprintf (f
, "return true;\n");
2406 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2407 in outermost position). */
2408 if (result
->type
== operand::OP_EXPR
2409 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2410 result
= as_a
<expr
*> (result
)->ops
[0];
2411 if (result
->type
== operand::OP_EXPR
)
2413 expr
*e
= as_a
<expr
*> (result
);
2414 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2416 fprintf (f
, "*res_code = %s;\n",
2417 *e
->operation
== CONVERT_EXPR
2418 ? "NOP_EXPR" : e
->operation
->id
);
2419 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2422 snprintf (dest
, 32, " res_ops[%d]", j
);
2424 = get_operand_type (e
->operation
,
2425 "type", e
->expr_type
,
2427 ? NULL
: "TREE_TYPE (res_ops[0])");
2428 /* We need to expand GENERIC conditions we captured from
2430 bool expand_generic_cond_exprs_p
2432 /* But avoid doing that if the GENERIC condition is
2433 valid - which it is in the first operand of COND_EXPRs
2434 and VEC_COND_EXRPs. */
2435 && ((!(*e
->operation
== COND_EXPR
)
2436 && !(*e
->operation
== VEC_COND_EXPR
))
2438 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2439 indexes
, expand_generic_cond_exprs_p
);
2442 /* Re-fold the toplevel result. It's basically an embedded
2443 gimple_build w/o actually building the stmt. */
2445 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2446 "res_ops, valueize);\n", e
->ops
.length ());
2448 else if (result
->type
== operand::OP_CAPTURE
2449 || result
->type
== operand::OP_C_EXPR
)
2451 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2452 &cinfo
, indexes
, false);
2453 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2454 if (is_a
<capture
*> (result
)
2455 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2457 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2458 with substituting a capture of that. */
2459 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2461 " tree tem = res_ops[0];\n"
2462 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2463 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2469 fprintf (f
, "return true;\n");
2473 bool is_predicate
= false;
2474 if (result
->type
== operand::OP_EXPR
)
2476 expr
*e
= as_a
<expr
*> (result
);
2477 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2478 /* Search for captures used multiple times in the result expression
2479 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2481 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2483 if (!cinfo
.info
[i
].force_no_side_effects_p
2484 && cinfo
.info
[i
].result_use_count
> 1)
2485 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2486 " captures[%d] = save_expr (captures[%d]);\n",
2489 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2493 snprintf (dest
, 32, "res_ops[%d]", j
);
2496 fprintf (f
, " tree res_op%d;\n", j
);
2497 snprintf (dest
, 32, " res_op%d", j
);
2500 = get_operand_type (e
->operation
,
2501 "type", e
->expr_type
,
2503 ? NULL
: "TREE_TYPE (res_op0)");
2504 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2508 fprintf (f
, "return true;\n");
2511 fprintf (f
, " tree res;\n");
2512 /* Re-fold the toplevel result. Use non_lvalue to
2513 build NON_LVALUE_EXPRs so they get properly
2514 ignored when in GIMPLE form. */
2515 if (*e
->operation
== NON_LVALUE_EXPR
)
2516 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2519 if (e
->operation
->kind
== id_base::CODE
)
2520 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2522 *e
->operation
== CONVERT_EXPR
2523 ? "NOP_EXPR" : e
->operation
->id
);
2525 fprintf (f
, " res = build_call_expr_loc "
2526 "(loc, builtin_decl_implicit (%s), %d",
2527 e
->operation
->id
, e
->ops
.length());
2528 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2529 fprintf (f
, ", res_op%d", j
);
2530 fprintf (f
, ");\n");
2534 else if (result
->type
== operand::OP_CAPTURE
2535 || result
->type
== operand::OP_C_EXPR
)
2538 fprintf (f
, " tree res;\n");
2539 s
->result
->gen_transform (f
, " res", false, 1, "type",
2546 /* Search for captures not used in the result expression and dependent
2547 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2548 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2550 if (!cinfo
.info
[i
].force_no_side_effects_p
2551 && !cinfo
.info
[i
].expr_p
2552 && cinfo
.info
[i
].result_use_count
== 0)
2553 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2554 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2555 " fold_ignored_result (captures[%d]), res);\n",
2558 fprintf (f
, " return res;\n");
2562 for (unsigned i
= 0; i
< n_braces
; ++i
)
2568 /* Main entry to generate code for matching GIMPLE IL off the decision
2572 decision_tree::gen_gimple (FILE *f
)
2574 for (unsigned n
= 1; n
<= 3; ++n
)
2576 fprintf (f
, "\nstatic bool\n"
2577 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2578 " gimple_seq *seq, tree (*valueize)(tree),\n"
2579 " code_helper code, tree type");
2580 for (unsigned i
= 0; i
< n
; ++i
)
2581 fprintf (f
, ", tree op%d", i
);
2585 fprintf (f
, "switch (code.get_rep())\n"
2587 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2589 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2590 expr
*e
= static_cast<expr
*>(dop
->op
);
2591 if (e
->ops
.length () != n
)
2594 if (*e
->operation
== CONVERT_EXPR
2595 || *e
->operation
== NOP_EXPR
)
2596 fprintf (f
, "CASE_CONVERT:\n");
2598 fprintf (f
, "case %s%s:\n",
2599 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2602 dop
->gen_kids (f
, true);
2603 fprintf (f
, "break;\n");
2606 fprintf (f
, "default:;\n"
2609 fprintf (f
, "return false;\n");
2614 /* Main entry to generate code for matching GENERIC IL off the decision
2618 decision_tree::gen_generic (FILE *f
)
2620 for (unsigned n
= 1; n
<= 3; ++n
)
2622 fprintf (f
, "\ntree\n"
2623 "generic_simplify (location_t loc, enum tree_code code, "
2624 "tree type ATTRIBUTE_UNUSED");
2625 for (unsigned i
= 0; i
< n
; ++i
)
2626 fprintf (f
, ", tree op%d", i
);
2630 fprintf (f
, "switch (code)\n"
2632 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2634 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2635 expr
*e
= static_cast<expr
*>(dop
->op
);
2636 if (e
->ops
.length () != n
2637 /* Builtin simplifications are somewhat premature on
2638 GENERIC. The following drops patterns with outermost
2639 calls. It's easy to emit overloads for function code
2640 though if necessary. */
2641 || e
->operation
->kind
!= id_base::CODE
)
2644 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2645 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2646 fprintf (f
, "CASE_CONVERT:\n");
2648 fprintf (f
, "case %s:\n", e
->operation
->id
);
2650 dop
->gen_kids (f
, false);
2651 fprintf (f
, "break;\n"
2654 fprintf (f
, "default:;\n"
2657 fprintf (f
, "return NULL_TREE;\n");
2662 /* Output code to implement the predicate P from the decision tree DT. */
2665 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2667 fprintf (f
, "\nbool\n"
2668 "%s%s (tree t%s%s)\n"
2669 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2670 p
->nargs
> 0 ? ", tree *res_ops" : "",
2671 gimple
? ", tree (*valueize)(tree)" : "");
2672 /* Conveniently make 'type' available. */
2673 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2676 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2677 dt
.root
->gen_kids (f
, gimple
);
2679 fprintf (f
, "return false;\n"
2683 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2686 write_header (FILE *f
, const char *head
)
2688 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2689 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2691 /* Include the header instead of writing it awkwardly quoted here. */
2692 fprintf (f
, "\n#include \"%s\"\n", head
);
2702 parser (cpp_reader
*);
2705 const cpp_token
*next ();
2706 const cpp_token
*peek ();
2707 const cpp_token
*peek_ident (const char * = NULL
);
2708 const cpp_token
*expect (enum cpp_ttype
);
2709 void eat_token (enum cpp_ttype
);
2710 const char *get_string ();
2711 const char *get_ident ();
2712 void eat_ident (const char *);
2713 const char *get_number ();
2715 id_base
*parse_operation ();
2716 operand
*parse_capture (operand
*);
2717 operand
*parse_expr ();
2718 c_expr
*parse_c_expr (cpp_ttype
);
2719 operand
*parse_op ();
2721 void record_operlist (source_location
, user_id
*);
2723 void parse_pattern ();
2724 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2725 operand
*, source_location
);
2726 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2728 void parse_for (source_location
);
2729 void parse_if (source_location
);
2730 void parse_predicates (source_location
);
2731 void parse_operator_list (source_location
);
2734 vec
<if_or_with
> active_ifs
;
2735 vec
<vec
<user_id
*> > active_fors
;
2736 hash_set
<user_id
*> *oper_lists_set
;
2737 vec
<user_id
*> oper_lists
;
2739 cid_map_t
*capture_ids
;
2742 vec
<simplify
*> simplifiers
;
2743 vec
<predicate_id
*> user_predicates
;
2744 bool parsing_match_operand
;
2747 /* Lexing helpers. */
2749 /* Read the next non-whitespace token from R. */
2754 const cpp_token
*token
;
2757 token
= cpp_get_token (r
);
2759 while (token
->type
== CPP_PADDING
2760 && token
->type
!= CPP_EOF
);
2764 /* Peek at the next non-whitespace token from R. */
2769 const cpp_token
*token
;
2773 token
= cpp_peek_token (r
, i
++);
2775 while (token
->type
== CPP_PADDING
2776 && token
->type
!= CPP_EOF
);
2777 /* If we peek at EOF this is a fatal error as it leaves the
2778 cpp_reader in unusable state. Assume we really wanted a
2779 token and thus this EOF is unexpected. */
2780 if (token
->type
== CPP_EOF
)
2781 fatal_at (token
, "unexpected end of file");
2785 /* Peek at the next identifier token (or return NULL if the next
2786 token is not an identifier or equal to ID if supplied). */
2789 parser::peek_ident (const char *id
)
2791 const cpp_token
*token
= peek ();
2792 if (token
->type
!= CPP_NAME
)
2798 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2799 if (strcmp (id
, t
) == 0)
2805 /* Read the next token from R and assert it is of type TK. */
2808 parser::expect (enum cpp_ttype tk
)
2810 const cpp_token
*token
= next ();
2811 if (token
->type
!= tk
)
2812 fatal_at (token
, "expected %s, got %s",
2813 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2818 /* Consume the next token from R and assert it is of type TK. */
2821 parser::eat_token (enum cpp_ttype tk
)
2826 /* Read the next token from R and assert it is of type CPP_STRING and
2827 return its value. */
2830 parser::get_string ()
2832 const cpp_token
*token
= expect (CPP_STRING
);
2833 return (const char *)token
->val
.str
.text
;
2836 /* Read the next token from R and assert it is of type CPP_NAME and
2837 return its value. */
2840 parser::get_ident ()
2842 const cpp_token
*token
= expect (CPP_NAME
);
2843 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2846 /* Eat an identifier token with value S from R. */
2849 parser::eat_ident (const char *s
)
2851 const cpp_token
*token
= peek ();
2852 const char *t
= get_ident ();
2853 if (strcmp (s
, t
) != 0)
2854 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2857 /* Read the next token from R and assert it is of type CPP_NUMBER and
2858 return its value. */
2861 parser::get_number ()
2863 const cpp_token
*token
= expect (CPP_NUMBER
);
2864 return (const char *)token
->val
.str
.text
;
2868 /* Record an operator-list use for transparent for handling. */
2871 parser::record_operlist (source_location loc
, user_id
*p
)
2873 if (!oper_lists_set
->add (p
))
2875 if (!oper_lists
.is_empty ()
2876 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2877 fatal_at (loc
, "User-defined operator list does not have the "
2878 "same number of entries as others used in the pattern");
2879 oper_lists
.safe_push (p
);
2883 /* Parse the operator ID, special-casing convert?, convert1? and
2887 parser::parse_operation ()
2889 const cpp_token
*id_tok
= peek ();
2890 const char *id
= get_ident ();
2891 const cpp_token
*token
= peek ();
2892 if (strcmp (id
, "convert0") == 0)
2893 fatal_at (id_tok
, "use 'convert?' here");
2894 if (token
->type
== CPP_QUERY
2895 && !(token
->flags
& PREV_WHITE
))
2897 if (strcmp (id
, "convert") == 0)
2899 else if (strcmp (id
, "convert1") == 0)
2901 else if (strcmp (id
, "convert2") == 0)
2904 fatal_at (id_tok
, "non-convert operator conditionalized");
2906 if (!parsing_match_operand
)
2907 fatal_at (id_tok
, "conditional convert can only be used in "
2908 "match expression");
2909 eat_token (CPP_QUERY
);
2911 else if (strcmp (id
, "convert1") == 0
2912 || strcmp (id
, "convert2") == 0)
2913 fatal_at (id_tok
, "expected '?' after conditional operator");
2914 id_base
*op
= get_operator (id
);
2916 fatal_at (id_tok
, "unknown operator %s", id
);
2918 user_id
*p
= dyn_cast
<user_id
*> (op
);
2919 if (p
&& p
->is_oper_list
)
2920 record_operlist (id_tok
->src_loc
, p
);
2925 capture = '@'<number> */
2928 parser::parse_capture (operand
*op
)
2930 eat_token (CPP_ATSIGN
);
2931 const cpp_token
*token
= peek ();
2932 const char *id
= NULL
;
2933 if (token
->type
== CPP_NUMBER
)
2935 else if (token
->type
== CPP_NAME
)
2938 fatal_at (token
, "expected number or identifier");
2939 unsigned next_id
= capture_ids
->elements ();
2941 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2944 return new capture (num
, op
);
2947 /* Parse an expression
2948 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2951 parser::parse_expr ()
2953 expr
*e
= new expr (parse_operation ());
2954 const cpp_token
*token
= peek ();
2956 bool is_commutative
= false;
2957 const char *expr_type
= NULL
;
2959 if (token
->type
== CPP_COLON
2960 && !(token
->flags
& PREV_WHITE
))
2962 eat_token (CPP_COLON
);
2964 if (token
->type
== CPP_NAME
2965 && !(token
->flags
& PREV_WHITE
))
2967 const char *s
= get_ident ();
2968 if (s
[0] == 'c' && !s
[1])
2970 if (!parsing_match_operand
)
2972 "flag 'c' can only be used in match expression");
2973 is_commutative
= true;
2975 else if (s
[1] != '\0')
2977 if (parsing_match_operand
)
2978 fatal_at (token
, "type can only be used in result expression");
2982 fatal_at (token
, "flag %s not recognized", s
);
2987 fatal_at (token
, "expected flag or type specifying identifier");
2990 if (token
->type
== CPP_ATSIGN
2991 && !(token
->flags
& PREV_WHITE
))
2992 op
= parse_capture (e
);
2997 const cpp_token
*token
= peek ();
2998 if (token
->type
== CPP_CLOSE_PAREN
)
3000 if (e
->operation
->nargs
!= -1
3001 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3002 fatal_at (token
, "'%s' expects %u operands, not %u",
3003 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3006 if (e
->ops
.length () == 2)
3007 e
->is_commutative
= true;
3009 fatal_at (token
, "only binary operators or function with "
3010 "two arguments can be marked commutative");
3012 e
->expr_type
= expr_type
;
3015 e
->append_op (parse_op ());
3020 /* Lex native C code delimited by START recording the preprocessing tokens
3021 for later processing.
3022 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3025 parser::parse_c_expr (cpp_ttype start
)
3027 const cpp_token
*token
;
3030 vec
<cpp_token
> code
= vNULL
;
3031 unsigned nr_stmts
= 0;
3033 if (start
== CPP_OPEN_PAREN
)
3034 end
= CPP_CLOSE_PAREN
;
3035 else if (start
== CPP_OPEN_BRACE
)
3036 end
= CPP_CLOSE_BRACE
;
3044 /* Count brace pairs to find the end of the expr to match. */
3045 if (token
->type
== start
)
3047 else if (token
->type
== end
3051 /* This is a lame way of counting the number of statements. */
3052 if (token
->type
== CPP_SEMICOLON
)
3055 /* If this is possibly a user-defined identifier mark it used. */
3056 if (token
->type
== CPP_NAME
)
3058 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3059 (token
->val
.node
.node
)->ident
.str
);
3061 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3062 record_operlist (token
->src_loc
, p
);
3065 /* Record the token. */
3066 code
.safe_push (*token
);
3069 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3072 /* Parse an operand which is either an expression, a predicate or
3073 a standalone capture.
3074 op = predicate | expr | c_expr | capture */
3079 const cpp_token
*token
= peek ();
3080 struct operand
*op
= NULL
;
3081 if (token
->type
== CPP_OPEN_PAREN
)
3083 eat_token (CPP_OPEN_PAREN
);
3085 eat_token (CPP_CLOSE_PAREN
);
3087 else if (token
->type
== CPP_OPEN_BRACE
)
3089 op
= parse_c_expr (CPP_OPEN_BRACE
);
3093 /* Remaining ops are either empty or predicates */
3094 if (token
->type
== CPP_NAME
)
3096 const char *id
= get_ident ();
3097 id_base
*opr
= get_operator (id
);
3099 fatal_at (token
, "expected predicate name");
3100 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3102 if (code
->nargs
!= 0)
3103 fatal_at (token
, "using an operator with operands as predicate");
3104 /* Parse the zero-operand operator "predicates" as
3106 op
= new expr (opr
);
3108 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3110 if (code
->nargs
!= 0)
3111 fatal_at (token
, "using an operator with operands as predicate");
3112 /* Parse the zero-operand operator "predicates" as
3114 op
= new expr (opr
);
3116 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3117 op
= new predicate (p
);
3119 fatal_at (token
, "using an unsupported operator as predicate");
3120 if (!parsing_match_operand
)
3121 fatal_at (token
, "predicates are only allowed in match expression");
3123 if (token
->flags
& PREV_WHITE
)
3126 else if (token
->type
!= CPP_COLON
3127 && token
->type
!= CPP_ATSIGN
)
3128 fatal_at (token
, "expected expression or predicate");
3129 /* optionally followed by a capture and a predicate. */
3130 if (token
->type
== CPP_COLON
)
3131 fatal_at (token
, "not implemented: predicate on leaf operand");
3132 if (token
->type
== CPP_ATSIGN
)
3133 op
= parse_capture (op
);
3139 /* Create a new simplify from the current parsing state and MATCH,
3140 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3143 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3144 operand
*match
, source_location match_loc
,
3145 operand
*result
, source_location result_loc
)
3147 /* Build and push a temporary for for operator list uses in expressions. */
3148 if (!oper_lists
.is_empty ())
3149 active_fors
.safe_push (oper_lists
);
3151 simplifiers
.safe_push
3152 (new simplify (match
, match_loc
, result
, result_loc
,
3153 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3155 if (!oper_lists
.is_empty ())
3160 simplify = 'simplify' <expr> <result-op>
3162 match = 'match' <ident> <expr> [<result-op>]
3164 <result-op> = <op> | <if> | <with>
3165 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3166 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3167 and fill SIMPLIFIERS with the results. */
3170 parser::parse_simplify (source_location match_location
,
3171 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3174 /* Reset the capture map. */
3176 capture_ids
= new cid_map_t
;
3177 /* Reset oper_lists and set. */
3178 hash_set
<user_id
*> olist
;
3179 oper_lists_set
= &olist
;
3182 const cpp_token
*loc
= peek ();
3183 parsing_match_operand
= true;
3184 struct operand
*match
= parse_op ();
3185 parsing_match_operand
= false;
3186 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3187 fatal_at (loc
, "outermost expression cannot be captured");
3188 if (match
->type
== operand::OP_EXPR
3189 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3190 fatal_at (loc
, "outermost expression cannot be a predicate");
3192 const cpp_token
*token
= peek ();
3194 /* If this if is immediately closed then it is part of a predicate
3195 definition. Push it. */
3196 if (token
->type
== CPP_CLOSE_PAREN
)
3199 fatal_at (token
, "expected transform expression");
3200 push_simplify (simplifiers
, match
, match_location
,
3201 result
, token
->src_loc
);
3205 unsigned active_ifs_len
= active_ifs
.length ();
3208 if (token
->type
== CPP_OPEN_PAREN
)
3210 source_location paren_loc
= token
->src_loc
;
3211 eat_token (CPP_OPEN_PAREN
);
3212 if (peek_ident ("if"))
3215 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3216 token
->src_loc
, false));
3217 /* If this if is immediately closed then it contains a
3218 manual matcher or is part of a predicate definition.
3220 if (peek ()->type
== CPP_CLOSE_PAREN
)
3223 fatal_at (token
, "manual transform not implemented");
3224 push_simplify (simplifiers
, match
, match_location
,
3228 else if (peek_ident ("with"))
3231 /* Parse (with c-expr expr) as (if-with (true) expr). */
3232 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3234 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3238 operand
*op
= result
;
3241 push_simplify (simplifiers
, match
, match_location
,
3242 op
, token
->src_loc
);
3243 eat_token (CPP_CLOSE_PAREN
);
3244 /* A "default" result closes the enclosing scope. */
3245 if (active_ifs
.length () > active_ifs_len
)
3247 eat_token (CPP_CLOSE_PAREN
);
3254 else if (token
->type
== CPP_CLOSE_PAREN
)
3256 /* Close a scope if requested. */
3257 if (active_ifs
.length () > active_ifs_len
)
3259 eat_token (CPP_CLOSE_PAREN
);
3269 fatal_at (token
, "expected match operand expression");
3270 push_simplify (simplifiers
, match
, match_location
,
3271 matcher
? result
: parse_op (), token
->src_loc
);
3272 /* A "default" result closes the enclosing scope. */
3273 if (active_ifs
.length () > active_ifs_len
)
3275 eat_token (CPP_CLOSE_PAREN
);
3285 /* Parsing of the outer control structures. */
3287 /* Parse a for expression
3288 for = '(' 'for' <subst>... <pattern> ')'
3289 subst = <ident> '(' <ident>... ')' */
3292 parser::parse_for (source_location
)
3294 auto_vec
<const cpp_token
*> user_id_tokens
;
3295 vec
<user_id
*> user_ids
= vNULL
;
3296 const cpp_token
*token
;
3297 unsigned min_n_opers
= 0, max_n_opers
= 0;
3302 if (token
->type
!= CPP_NAME
)
3305 /* Insert the user defined operators into the operator hash. */
3306 const char *id
= get_ident ();
3307 if (get_operator (id
) != NULL
)
3308 fatal_at (token
, "operator already defined");
3309 user_id
*op
= new user_id (id
);
3310 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3312 user_ids
.safe_push (op
);
3313 user_id_tokens
.safe_push (token
);
3315 eat_token (CPP_OPEN_PAREN
);
3318 while ((token
= peek_ident ()) != 0)
3320 const char *oper
= get_ident ();
3321 id_base
*idb
= get_operator (oper
);
3323 fatal_at (token
, "no such operator '%s'", oper
);
3324 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
3325 fatal_at (token
, "conditional operators cannot be used inside for");
3329 else if (idb
->nargs
== -1)
3331 else if (idb
->nargs
!= arity
)
3332 fatal_at (token
, "operator '%s' with arity %d does not match "
3333 "others with arity %d", oper
, idb
->nargs
, arity
);
3335 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3336 if (p
&& p
->is_oper_list
)
3337 op
->substitutes
.safe_splice (p
->substitutes
);
3339 op
->substitutes
.safe_push (idb
);
3342 token
= expect (CPP_CLOSE_PAREN
);
3344 unsigned nsubstitutes
= op
->substitutes
.length ();
3345 if (nsubstitutes
== 0)
3346 fatal_at (token
, "A user-defined operator must have at least "
3347 "one substitution");
3348 if (max_n_opers
== 0)
3350 min_n_opers
= nsubstitutes
;
3351 max_n_opers
= nsubstitutes
;
3355 if (nsubstitutes
% min_n_opers
!= 0
3356 && min_n_opers
% nsubstitutes
!= 0)
3357 fatal_at (token
, "All user-defined identifiers must have a "
3358 "multiple number of operator substitutions of the "
3359 "smallest number of substitutions");
3360 if (nsubstitutes
< min_n_opers
)
3361 min_n_opers
= nsubstitutes
;
3362 else if (nsubstitutes
> max_n_opers
)
3363 max_n_opers
= nsubstitutes
;
3367 unsigned n_ids
= user_ids
.length ();
3369 fatal_at (token
, "for requires at least one user-defined identifier");
3372 if (token
->type
== CPP_CLOSE_PAREN
)
3373 fatal_at (token
, "no pattern defined in for");
3375 active_fors
.safe_push (user_ids
);
3379 if (token
->type
== CPP_CLOSE_PAREN
)
3385 /* Remove user-defined operators from the hash again. */
3386 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3388 if (!user_ids
[i
]->used
)
3389 warning_at (user_id_tokens
[i
],
3390 "operator %s defined but not used", user_ids
[i
]->id
);
3391 operators
->remove_elt (user_ids
[i
]);
3395 /* Parse an identifier associated with a list of operators.
3396 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3399 parser::parse_operator_list (source_location
)
3401 const cpp_token
*token
= peek ();
3402 const char *id
= get_ident ();
3404 if (get_operator (id
) != 0)
3405 fatal_at (token
, "operator %s already defined", id
);
3407 user_id
*op
= new user_id (id
, true);
3410 while ((token
= peek_ident ()) != 0)
3413 const char *oper
= get_ident ();
3414 id_base
*idb
= get_operator (oper
);
3417 fatal_at (token
, "no such operator '%s'", oper
);
3421 else if (idb
->nargs
== -1)
3423 else if (arity
!= idb
->nargs
)
3424 fatal_at (token
, "operator '%s' with arity %d does not match "
3425 "others with arity %d", oper
, idb
->nargs
, arity
);
3427 /* We allow composition of multiple operator lists. */
3428 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3429 op
->substitutes
.safe_splice (p
->substitutes
);
3431 op
->substitutes
.safe_push (idb
);
3434 if (op
->substitutes
.length () == 0)
3435 fatal_at (token
, "operator-list cannot be empty");
3438 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3442 /* Parse an outer if expression.
3443 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3446 parser::parse_if (source_location loc
)
3448 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3450 const cpp_token
*token
= peek ();
3451 if (token
->type
== CPP_CLOSE_PAREN
)
3452 fatal_at (token
, "no pattern defined in if");
3454 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3457 const cpp_token
*token
= peek ();
3458 if (token
->type
== CPP_CLOSE_PAREN
)
3466 /* Parse a list of predefined predicate identifiers.
3467 preds = '(' 'define_predicates' <ident>... ')' */
3470 parser::parse_predicates (source_location
)
3474 const cpp_token
*token
= peek ();
3475 if (token
->type
!= CPP_NAME
)
3478 add_predicate (get_ident ());
3483 /* Parse outer control structures.
3484 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3487 parser::parse_pattern ()
3489 /* All clauses start with '('. */
3490 eat_token (CPP_OPEN_PAREN
);
3491 const cpp_token
*token
= peek ();
3492 const char *id
= get_ident ();
3493 if (strcmp (id
, "simplify") == 0)
3495 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3498 else if (strcmp (id
, "match") == 0)
3500 bool with_args
= false;
3501 if (peek ()->type
== CPP_OPEN_PAREN
)
3503 eat_token (CPP_OPEN_PAREN
);
3506 const char *name
= get_ident ();
3507 id_base
*id
= get_operator (name
);
3511 p
= add_predicate (name
);
3512 user_predicates
.safe_push (p
);
3514 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3517 fatal_at (token
, "cannot add a match to a non-predicate ID");
3518 /* Parse (match <id> <arg>... (match-expr)) here. */
3522 capture_ids
= new cid_map_t
;
3524 while (peek ()->type
== CPP_ATSIGN
)
3525 e
->append_op (parse_capture (NULL
));
3526 eat_token (CPP_CLOSE_PAREN
);
3529 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3530 || (!e
&& p
->nargs
!= 0)))
3531 fatal_at (token
, "non-matching number of match operands");
3532 p
->nargs
= e
? e
->ops
.length () : 0;
3533 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3536 else if (strcmp (id
, "for") == 0)
3537 parse_for (token
->src_loc
);
3538 else if (strcmp (id
, "if") == 0)
3539 parse_if (token
->src_loc
);
3540 else if (strcmp (id
, "define_predicates") == 0)
3542 if (active_ifs
.length () > 0
3543 || active_fors
.length () > 0)
3544 fatal_at (token
, "define_predicates inside if or for is not supported");
3545 parse_predicates (token
->src_loc
);
3547 else if (strcmp (id
, "define_operator_list") == 0)
3549 if (active_ifs
.length () > 0
3550 || active_fors
.length () > 0)
3551 fatal_at (token
, "operator-list inside if or for is not supported");
3552 parse_operator_list (token
->src_loc
);
3555 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3556 active_ifs
.length () == 0 && active_fors
.length () == 0
3557 ? "'define_predicates', " : "");
3559 eat_token (CPP_CLOSE_PAREN
);
3562 /* Main entry of the parser. Repeatedly parse outer control structures. */
3564 parser::parser (cpp_reader
*r_
)
3568 active_fors
= vNULL
;
3569 simplifiers
= vNULL
;
3570 oper_lists_set
= NULL
;
3573 user_predicates
= vNULL
;
3574 parsing_match_operand
= false;
3576 const cpp_token
*token
= next ();
3577 while (token
->type
!= CPP_EOF
)
3579 _cpp_backup_tokens (r
, 1);
3586 /* Helper for the linemap code. */
3589 round_alloc_size (size_t s
)
3595 /* The genmatch generator progam. It reads from a pattern description
3596 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3599 main (int argc
, char **argv
)
3603 progname
= "genmatch";
3609 bool verbose
= false;
3610 char *input
= argv
[argc
-1];
3611 for (int i
= 1; i
< argc
- 1; ++i
)
3613 if (strcmp (argv
[i
], "--gimple") == 0)
3615 else if (strcmp (argv
[i
], "--generic") == 0)
3617 else if (strcmp (argv
[i
], "-v") == 0)
3621 fprintf (stderr
, "Usage: genmatch "
3622 "[--gimple] [--generic] [-v] input\n");
3627 line_table
= XCNEW (struct line_maps
);
3628 linemap_init (line_table
, 0);
3629 line_table
->reallocator
= xrealloc
;
3630 line_table
->round_alloc_size
= round_alloc_size
;
3632 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3633 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3634 cb
->error
= error_cb
;
3636 if (!cpp_read_main_file (r
, input
))
3638 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3639 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3641 /* Pre-seed operators. */
3642 operators
= new hash_table
<id_base
> (1024);
3643 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3644 add_operator (SYM, # SYM, # TYPE, NARGS);
3645 #define END_OF_BASE_TREE_CODES
3647 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3648 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3649 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3650 #undef END_OF_BASE_TREE_CODES
3653 /* Pre-seed builtin functions.
3654 ??? Cannot use N (name) as that is targetm.emultls.get_address
3655 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3656 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3657 add_builtin (ENUM, # ENUM);
3658 #include "builtins.def"
3665 write_header (stdout
, "gimple-match-head.c");
3667 write_header (stdout
, "generic-match-head.c");
3669 /* Go over all predicates defined with patterns and perform
3670 lowering and code generation. */
3671 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3673 predicate_id
*pred
= p
.user_predicates
[i
];
3674 lower (pred
->matchers
, gimple
);
3677 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3678 print_matches (pred
->matchers
[i
]);
3681 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3682 dt
.insert (pred
->matchers
[i
], i
);
3687 write_predicate (stdout
, pred
, dt
, gimple
);
3690 /* Lower the main simplifiers and generate code for them. */
3691 lower (p
.simplifiers
, gimple
);
3694 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3695 print_matches (p
.simplifiers
[i
]);
3698 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3699 dt
.insert (p
.simplifiers
[i
], i
);
3705 dt
.gen_gimple (stdout
);
3707 dt
.gen_generic (stdout
);
3710 cpp_finish (r
, NULL
);