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"
40 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
41 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
42 size_t, size_t MEM_STAT_DECL
)
46 void ggc_free (void *)
53 static struct line_maps
*line_table
;
56 #if GCC_VERSION >= 4001
57 __attribute__((format (printf
, 6, 0)))
59 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
60 unsigned int, const char *msg
, va_list *ap
)
62 const line_map_ordinary
*map
;
63 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
64 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
65 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
66 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
67 vfprintf (stderr
, msg
, *ap
);
68 fprintf (stderr
, "\n");
69 FILE *f
= fopen (loc
.file
, "r");
75 if (!fgets (buf
, 128, f
))
77 if (buf
[strlen (buf
) - 1] != '\n')
84 fprintf (stderr
, "%s", buf
);
85 for (int i
= 0; i
< loc
.column
- 1; ++i
)
93 if (errtype
== CPP_DL_FATAL
)
99 #if GCC_VERSION >= 4001
100 __attribute__((format (printf
, 2, 3)))
102 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
106 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
111 #if GCC_VERSION >= 4001
112 __attribute__((format (printf
, 2, 3)))
114 fatal_at (source_location loc
, const char *msg
, ...)
118 error_cb (NULL
, CPP_DL_FATAL
, 0, loc
, 0, msg
, &ap
);
123 #if GCC_VERSION >= 4001
124 __attribute__((format (printf
, 2, 3)))
126 warning_at (const cpp_token
*tk
, const char *msg
, ...)
130 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
135 output_line_directive (FILE *f
, source_location location
,
136 bool dumpfile
= false)
138 const line_map_ordinary
*map
;
139 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
140 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
143 /* When writing to a dumpfile only dump the filename. */
144 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
149 fprintf (f
, "%s:%d", file
, loc
.line
);
152 /* Other gen programs really output line directives here, at least for
153 development it's right now more convenient to have line information
154 from the generated file. Still keep the directives as comment for now
155 to easily back-point to the meta-description. */
156 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
160 /* Pull in tree codes and builtin function codes from their
163 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
173 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
174 enum built_in_function
{
175 #include "builtins.def"
181 /* Base class for all identifiers the parser knows. */
183 struct id_base
: typed_noop_remove
<id_base
>
185 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
187 id_base (id_kind
, const char *, int = -1);
193 /* hash_table support. */
194 typedef id_base
*value_type
;
195 typedef id_base
*compare_type
;
196 static inline hashval_t
hash (const id_base
*);
197 static inline int equal (const id_base
*, const id_base
*);
201 id_base::hash (const id_base
*op
)
207 id_base::equal (const id_base
*op1
,
210 return (op1
->hashval
== op2
->hashval
211 && strcmp (op1
->id
, op2
->id
) == 0);
214 /* Hashtable of known pattern operators. This is pre-seeded from
215 all known tree codes and all known builtin function ids. */
216 static hash_table
<id_base
> *operators
;
218 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
223 hashval
= htab_hash_string (id
);
226 /* Identifier that maps to a tree code. */
228 struct operator_id
: public id_base
230 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
232 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
237 /* Identifier that maps to a builtin function code. */
239 struct fn_id
: public id_base
241 fn_id (enum built_in_function fn_
, const char *id_
)
242 : id_base (id_base::FN
, id_
), fn (fn_
) {}
243 enum built_in_function fn
;
248 /* Identifier that maps to a user-defined predicate. */
250 struct predicate_id
: public id_base
252 predicate_id (const char *id_
)
253 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
254 vec
<simplify
*> matchers
;
257 /* Identifier that maps to a operator defined by a 'for' directive. */
259 struct user_id
: public id_base
261 user_id (const char *id_
, bool is_oper_list_
= false)
262 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
263 used (false), is_oper_list (is_oper_list_
) {}
264 vec
<id_base
*> substitutes
;
272 is_a_helper
<fn_id
*>::test (id_base
*id
)
274 return id
->kind
== id_base::FN
;
280 is_a_helper
<operator_id
*>::test (id_base
*id
)
282 return id
->kind
== id_base::CODE
;
288 is_a_helper
<predicate_id
*>::test (id_base
*id
)
290 return id
->kind
== id_base::PREDICATE
;
296 is_a_helper
<user_id
*>::test (id_base
*id
)
298 return id
->kind
== id_base::USER
;
301 /* Add a predicate identifier to the hash. */
303 static predicate_id
*
304 add_predicate (const char *id
)
306 predicate_id
*p
= new predicate_id (id
);
307 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
309 fatal ("duplicate id definition");
314 /* Add a tree code identifier to the hash. */
317 add_operator (enum tree_code code
, const char *id
,
318 const char *tcc
, unsigned nargs
)
320 if (strcmp (tcc
, "tcc_unary") != 0
321 && strcmp (tcc
, "tcc_binary") != 0
322 && strcmp (tcc
, "tcc_comparison") != 0
323 && strcmp (tcc
, "tcc_expression") != 0
324 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
325 && strcmp (tcc
, "tcc_reference") != 0
326 /* To have INTEGER_CST and friends as "predicate operators". */
327 && strcmp (tcc
, "tcc_constant") != 0
328 /* And allow CONSTRUCTOR for vector initializers. */
329 && !(code
== CONSTRUCTOR
))
331 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
332 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
334 fatal ("duplicate id definition");
338 /* Add a builtin identifier to the hash. */
341 add_builtin (enum built_in_function code
, const char *id
)
343 fn_id
*fn
= new fn_id (code
, id
);
344 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
346 fatal ("duplicate id definition");
350 /* Helper for easy comparing ID with tree code CODE. */
353 operator==(id_base
&id
, enum tree_code code
)
355 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
356 return oid
->code
== code
;
360 /* Lookup the identifier ID. */
363 get_operator (const char *id
)
365 id_base
tem (id_base::CODE
, id
);
367 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
370 /* If this is a user-defined identifier track whether it was used. */
371 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
376 /* Try all-uppercase. */
377 char *id2
= xstrdup (id
);
378 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
379 id2
[i
] = TOUPPER (id2
[i
]);
380 new (&tem
) id_base (id_base::CODE
, id2
);
381 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
388 /* Try _EXPR appended. */
389 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
390 strcat (id2
, "_EXPR");
391 new (&tem
) id_base (id_base::CODE
, id2
);
392 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
403 /* Helper for the capture-id map. */
405 struct capture_id_map_hasher
: default_hashmap_traits
407 static inline hashval_t
hash (const char *);
408 static inline bool equal_keys (const char *, const char *);
412 capture_id_map_hasher::hash (const char *id
)
414 return htab_hash_string (id
);
418 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
420 return strcmp (id1
, id2
) == 0;
423 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
426 /* The AST produced by parsing of the pattern definitions. */
431 /* The base class for operands. */
434 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
435 operand (enum op_type type_
) : type (type_
) {}
437 virtual void gen_transform (FILE *, const char *, bool, int,
438 const char *, capture_info
*,
441 { gcc_unreachable (); }
444 /* A predicate operand. Predicates are leafs in the AST. */
446 struct predicate
: public operand
448 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
452 /* An operand that constitutes an expression. Expressions include
453 function calls and user-defined predicate invocations. */
455 struct expr
: public operand
457 expr (id_base
*operation_
, bool is_commutative_
= false)
458 : operand (OP_EXPR
), operation (operation_
),
459 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
460 is_generic (false) {}
461 void append_op (operand
*op
) { ops
.safe_push (op
); }
462 /* The operator and its operands. */
465 /* An explicitely specified type - used exclusively for conversions. */
466 const char *expr_type
;
467 /* Whether the operation is to be applied commutatively. This is
468 later lowered to two separate patterns. */
470 /* Whether the expression is expected to be in GENERIC form. */
472 virtual void gen_transform (FILE *f
, const char *, bool, int,
473 const char *, capture_info
*,
474 dt_operand
** = 0, bool = true);
477 /* An operator that is represented by native C code. This is always
478 a leaf operand in the AST. This class is also used to represent
479 the code to be generated for 'if' and 'with' expressions. */
481 struct c_expr
: public operand
483 /* A mapping of an identifier and its replacement. Used to apply
488 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
491 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
492 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
493 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
494 nr_stmts (nr_stmts_
), ids (ids_
) {}
495 /* cpplib tokens and state to transform this back to source. */
498 cid_map_t
*capture_ids
;
499 /* The number of statements parsed (well, the number of ';'s). */
501 /* The identifier replacement vector. */
503 virtual void gen_transform (FILE *f
, const char *, bool, int,
504 const char *, capture_info
*,
505 dt_operand
** = 0, bool = true);
508 /* A wrapper around another operand that captures its value. */
510 struct capture
: public operand
512 capture (unsigned where_
, operand
*what_
)
513 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
514 /* Identifier index for the value. */
516 /* The captured value. */
518 virtual void gen_transform (FILE *f
, const char *, bool, int,
519 const char *, capture_info
*,
520 dt_operand
** = 0, bool = true);
526 is_a_helper
<capture
*>::test (operand
*op
)
528 return op
->type
== operand::OP_CAPTURE
;
534 is_a_helper
<predicate
*>::test (operand
*op
)
536 return op
->type
== operand::OP_PREDICATE
;
542 is_a_helper
<c_expr
*>::test (operand
*op
)
544 return op
->type
== operand::OP_C_EXPR
;
550 is_a_helper
<expr
*>::test (operand
*op
)
552 return op
->type
== operand::OP_EXPR
;
555 /* Helper to distinguish 'if' from 'with' expressions. */
559 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
560 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
561 source_location location
;
566 /* The main class of a pattern and its transform. This is used to
567 represent both (simplify ...) and (match ...) kinds. The AST
568 duplicates all outer 'if' and 'for' expressions here so each
569 simplify can exist in isolation. */
573 simplify (operand
*match_
, source_location match_location_
,
574 struct operand
*result_
, source_location result_location_
,
575 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
576 cid_map_t
*capture_ids_
)
577 : match (match_
), match_location (match_location_
),
578 result (result_
), result_location (result_location_
),
579 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
580 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
582 /* The expression that is matched against the GENERIC or GIMPLE IL. */
584 source_location match_location
;
585 /* For a (simplify ...) the expression produced when the pattern applies.
586 For a (match ...) either NULL if it is a simple predicate or the
587 single expression specifying the matched operands. */
588 struct operand
*result
;
589 source_location result_location
;
590 /* Collected 'if' expressions that need to evaluate to true to make
591 the pattern apply. */
592 vec
<if_or_with
> ifexpr_vec
;
593 /* Collected 'for' expression operators that have to be replaced
594 in the lowering phase. */
595 vec
<vec
<user_id
*> > for_vec
;
596 /* A map of capture identifiers to indexes. */
597 cid_map_t
*capture_ids
;
601 /* Debugging routines for dumping the AST. */
604 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
606 if (capture
*c
= dyn_cast
<capture
*> (o
))
608 fprintf (f
, "@%u", c
->where
);
609 if (c
->what
&& flattened
== false)
612 print_operand (c
->what
, f
, flattened
);
617 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
618 fprintf (f
, "%s", p
->p
->id
);
620 else if (is_a
<c_expr
*> (o
))
621 fprintf (f
, "c_expr");
623 else if (expr
*e
= dyn_cast
<expr
*> (o
))
625 fprintf (f
, "(%s", e
->operation
->id
);
627 if (flattened
== false)
630 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
632 print_operand (e
->ops
[i
], f
, flattened
);
644 print_matches (struct simplify
*s
, FILE *f
= stderr
)
646 fprintf (f
, "for expression: ");
647 print_operand (s
->match
, f
);
654 /* Lowering of commutative operators. */
657 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
658 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
660 if (n
== ops_vector
.length ())
662 vec
<operand
*> xv
= v
.copy ();
663 result
.safe_push (xv
);
667 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
669 v
[n
] = ops_vector
[n
][i
];
670 cartesian_product (ops_vector
, result
, v
, n
+ 1);
674 /* Lower OP to two operands in case it is marked as commutative. */
676 static vec
<operand
*>
677 commutate (operand
*op
)
679 vec
<operand
*> ret
= vNULL
;
681 if (capture
*c
= dyn_cast
<capture
*> (op
))
688 vec
<operand
*> v
= commutate (c
->what
);
689 for (unsigned i
= 0; i
< v
.length (); ++i
)
691 capture
*nc
= new capture (c
->where
, v
[i
]);
697 expr
*e
= dyn_cast
<expr
*> (op
);
698 if (!e
|| e
->ops
.length () == 0)
704 vec
< vec
<operand
*> > ops_vector
= vNULL
;
705 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
706 ops_vector
.safe_push (commutate (e
->ops
[i
]));
708 auto_vec
< vec
<operand
*> > result
;
709 auto_vec
<operand
*> v (e
->ops
.length ());
710 v
.quick_grow_cleared (e
->ops
.length ());
711 cartesian_product (ops_vector
, result
, v
, 0);
714 for (unsigned i
= 0; i
< result
.length (); ++i
)
716 expr
*ne
= new expr (e
->operation
);
717 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
718 ne
->append_op (result
[i
][j
]);
722 if (!e
->is_commutative
)
725 for (unsigned i
= 0; i
< result
.length (); ++i
)
727 expr
*ne
= new expr (e
->operation
);
728 // result[i].length () is 2 since e->operation is binary
729 for (unsigned j
= result
[i
].length (); j
; --j
)
730 ne
->append_op (result
[i
][j
-1]);
737 /* Lower operations marked as commutative in the AST of S and push
738 the resulting patterns to SIMPLIFIERS. */
741 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
743 vec
<operand
*> matchers
= commutate (s
->match
);
744 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
746 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
747 s
->result
, s
->result_location
, s
->ifexpr_vec
,
748 s
->for_vec
, s
->capture_ids
);
749 simplifiers
.safe_push (ns
);
753 /* Strip conditional conversios using operator OPER from O and its
754 children if STRIP, else replace them with an unconditional convert. */
757 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
759 if (capture
*c
= dyn_cast
<capture
*> (o
))
762 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
767 expr
*e
= dyn_cast
<expr
*> (o
);
771 if (*e
->operation
== oper
)
774 return lower_opt_convert (e
->ops
[0], oper
, strip
);
776 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
777 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
781 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
782 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
783 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
788 /* Determine whether O or its children uses the conditional conversion
792 has_opt_convert (operand
*o
, enum tree_code oper
)
794 if (capture
*c
= dyn_cast
<capture
*> (o
))
797 return has_opt_convert (c
->what
, oper
);
802 expr
*e
= dyn_cast
<expr
*> (o
);
806 if (*e
->operation
== oper
)
809 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
810 if (has_opt_convert (e
->ops
[i
], oper
))
816 /* Lower conditional convert operators in O, expanding it to a vector
819 static vec
<operand
*>
820 lower_opt_convert (operand
*o
)
822 vec
<operand
*> v1
= vNULL
, v2
;
826 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
828 /* Conditional converts are lowered to a pattern with the
829 conversion and one without. The three different conditional
830 convert codes are lowered separately. */
832 for (unsigned i
= 0; i
< 3; ++i
)
835 for (unsigned j
= 0; j
< v1
.length (); ++j
)
836 if (has_opt_convert (v1
[j
], opers
[i
]))
838 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
839 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
845 for (unsigned j
= 0; j
< v2
.length (); ++j
)
846 v1
.safe_push (v2
[j
]);
853 /* Lower conditional convert operators in the AST of S and push
854 the resulting multiple patterns to SIMPLIFIERS. */
857 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
859 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
860 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
862 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
863 s
->result
, s
->result_location
, s
->ifexpr_vec
,
864 s
->for_vec
, s
->capture_ids
);
865 simplifiers
.safe_push (ns
);
869 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
870 GENERIC and a GIMPLE variant. */
872 static vec
<operand
*>
873 lower_cond (operand
*o
)
875 vec
<operand
*> ro
= vNULL
;
877 if (capture
*c
= dyn_cast
<capture
*> (o
))
881 vec
<operand
*> lop
= vNULL
;
882 lop
= lower_cond (c
->what
);
884 for (unsigned i
= 0; i
< lop
.length (); ++i
)
885 ro
.safe_push (new capture (c
->where
, lop
[i
]));
890 expr
*e
= dyn_cast
<expr
*> (o
);
891 if (!e
|| e
->ops
.length () == 0)
897 vec
< vec
<operand
*> > ops_vector
= vNULL
;
898 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
899 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
901 auto_vec
< vec
<operand
*> > result
;
902 auto_vec
<operand
*> v (e
->ops
.length ());
903 v
.quick_grow_cleared (e
->ops
.length ());
904 cartesian_product (ops_vector
, result
, v
, 0);
906 for (unsigned i
= 0; i
< result
.length (); ++i
)
908 expr
*ne
= new expr (e
->operation
);
909 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
910 ne
->append_op (result
[i
][j
]);
912 /* If this is a COND with a captured expression or an
913 expression with two operands then also match a GENERIC
914 form on the compare. */
915 if ((*e
->operation
== COND_EXPR
916 || *e
->operation
== VEC_COND_EXPR
)
917 && ((is_a
<capture
*> (e
->ops
[0])
918 && as_a
<capture
*> (e
->ops
[0])->what
919 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
921 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
922 || (is_a
<expr
*> (e
->ops
[0])
923 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
925 expr
*ne
= new expr (e
->operation
);
926 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
927 ne
->append_op (result
[i
][j
]);
928 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
930 expr
*ocmp
= as_a
<expr
*> (c
->what
);
931 expr
*cmp
= new expr (ocmp
->operation
);
932 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
933 cmp
->append_op (ocmp
->ops
[j
]);
934 cmp
->is_generic
= true;
935 ne
->ops
[0] = new capture (c
->where
, cmp
);
939 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
940 expr
*cmp
= new expr (ocmp
->operation
);
941 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
942 cmp
->append_op (ocmp
->ops
[j
]);
943 cmp
->is_generic
= true;
953 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
954 GENERIC and a GIMPLE variant. */
957 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
959 vec
<operand
*> matchers
= lower_cond (s
->match
);
960 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
962 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
963 s
->result
, s
->result_location
, s
->ifexpr_vec
,
964 s
->for_vec
, s
->capture_ids
);
965 simplifiers
.safe_push (ns
);
969 /* In AST operand O replace operator ID with operator WITH. */
972 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
974 /* Deep-copy captures and expressions, replacing operations as
976 if (capture
*c
= dyn_cast
<capture
*> (o
))
980 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
982 else if (expr
*e
= dyn_cast
<expr
*> (o
))
984 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
986 ne
->expr_type
= e
->expr_type
;
987 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
988 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
992 /* For c_expr we simply record a string replacement table which is
993 applied at code-generation time. */
994 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
996 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
997 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
998 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1004 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1007 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1009 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1010 unsigned worklist_start
= 0;
1011 auto_vec
<simplify
*> worklist
;
1012 worklist
.safe_push (sin
);
1014 /* Lower each recorded for separately, operating on the
1015 set of simplifiers created by the previous one.
1016 Lower inner-to-outer so inner for substitutes can refer
1017 to operators replaced by outer fors. */
1018 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1020 vec
<user_id
*>& ids
= for_vec
[fi
];
1021 unsigned n_ids
= ids
.length ();
1022 unsigned max_n_opers
= 0;
1023 for (unsigned i
= 0; i
< n_ids
; ++i
)
1024 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1025 max_n_opers
= ids
[i
]->substitutes
.length ();
1027 unsigned worklist_end
= worklist
.length ();
1028 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1030 simplify
*s
= worklist
[si
];
1031 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1033 operand
*match_op
= s
->match
;
1034 operand
*result_op
= s
->result
;
1035 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1037 for (unsigned i
= 0; i
< n_ids
; ++i
)
1039 user_id
*id
= ids
[i
];
1040 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1041 match_op
= replace_id (match_op
, id
, oper
);
1043 result_op
= replace_id (result_op
, id
, oper
);
1044 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1045 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1048 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1049 result_op
, s
->result_location
,
1050 ifexpr_vec
, vNULL
, s
->capture_ids
);
1051 worklist
.safe_push (ns
);
1054 worklist_start
= worklist_end
;
1057 /* Copy out the result from the last for lowering. */
1058 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1059 simplifiers
.safe_push (worklist
[i
]);
1062 /* Lower the AST for everything in SIMPLIFIERS. */
1065 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1067 auto_vec
<simplify
*> out_simplifiers
;
1068 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1069 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1071 simplifiers
.truncate (0);
1072 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1073 lower_commutative (out_simplifiers
[i
], simplifiers
);
1075 out_simplifiers
.truncate (0);
1077 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1078 lower_cond (simplifiers
[i
], out_simplifiers
);
1080 out_simplifiers
.safe_splice (simplifiers
);
1083 simplifiers
.truncate (0);
1084 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1085 lower_for (out_simplifiers
[i
], simplifiers
);
1091 /* The decision tree built for generating GIMPLE and GENERIC pattern
1092 matching code. It represents the 'match' expression of all
1093 simplifies and has those as its leafs. */
1095 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1099 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1103 vec
<dt_node
*> kids
;
1105 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1107 dt_node
*append_node (dt_node
*);
1108 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1109 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1110 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1111 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1113 virtual void gen (FILE *, bool) {}
1115 void gen_kids (FILE *, bool);
1116 void gen_kids_1 (FILE *, bool,
1117 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1118 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1121 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1123 struct dt_operand
: public dt_node
1126 dt_operand
*match_dop
;
1130 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1131 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1132 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1133 parent (parent_
), pos (pos_
) {}
1135 void gen (FILE *, bool);
1136 unsigned gen_predicate (FILE *, const char *, bool);
1137 unsigned gen_match_op (FILE *, const char *);
1139 unsigned gen_gimple_expr (FILE *);
1140 unsigned gen_generic_expr (FILE *, const char *);
1142 char *get_name (char *);
1143 void gen_opname (char *, unsigned);
1146 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1148 struct dt_simplify
: public dt_node
1151 unsigned pattern_no
;
1152 dt_operand
**indexes
;
1154 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1155 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1156 indexes (indexes_
) {}
1158 void gen (FILE *f
, bool);
1164 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1166 return (n
->type
== dt_node::DT_OPERAND
1167 || n
->type
== dt_node::DT_MATCH
);
1170 /* A container for the actual decision tree. */
1172 struct decision_tree
1176 void insert (struct simplify
*, unsigned);
1177 void gen_gimple (FILE *f
= stderr
);
1178 void gen_generic (FILE *f
= stderr
);
1179 void print (FILE *f
= stderr
);
1181 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1183 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1184 unsigned pos
= 0, dt_node
*parent
= 0);
1185 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1186 static bool cmp_node (dt_node
*, dt_node
*);
1187 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1190 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1193 cmp_operand (operand
*o1
, operand
*o2
)
1195 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1198 if (o1
->type
== operand::OP_PREDICATE
)
1200 predicate
*p1
= as_a
<predicate
*>(o1
);
1201 predicate
*p2
= as_a
<predicate
*>(o2
);
1202 return p1
->p
== p2
->p
;
1204 else if (o1
->type
== operand::OP_EXPR
)
1206 expr
*e1
= static_cast<expr
*>(o1
);
1207 expr
*e2
= static_cast<expr
*>(o2
);
1208 return (e1
->operation
== e2
->operation
1209 && e1
->is_generic
== e2
->is_generic
);
1215 /* Compare two decision tree nodes N1 and N2 and return true if they
1219 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1221 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1227 if (n1
->type
== dt_node::DT_TRUE
)
1230 if (n1
->type
== dt_node::DT_OPERAND
)
1231 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1232 (as_a
<dt_operand
*> (n2
))->op
);
1233 else if (n1
->type
== dt_node::DT_MATCH
)
1234 return ((as_a
<dt_operand
*> (n1
))->match_dop
1235 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1239 /* Search OPS for a decision tree node like P and return it if found. */
1242 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1244 /* We can merge adjacent DT_TRUE. */
1245 if (p
->type
== dt_node::DT_TRUE
1247 && ops
.last ()->type
== dt_node::DT_TRUE
)
1249 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1251 /* But we can't merge across DT_TRUE nodes as they serve as
1252 pattern order barriers to make sure that patterns apply
1253 in order of appearance in case multiple matches are possible. */
1254 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1256 if (decision_tree::cmp_node (ops
[i
], p
))
1262 /* Append N to the decision tree if it there is not already an existing
1266 dt_node::append_node (dt_node
*n
)
1270 kid
= decision_tree::find_node (kids
, n
);
1275 n
->level
= this->level
+ 1;
1280 /* Append OP to the decision tree. */
1283 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1285 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1286 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1287 return append_node (n
);
1290 /* Append a DT_TRUE decision tree node. */
1293 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1295 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1296 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1297 return append_node (n
);
1300 /* Append a DT_MATCH decision tree node. */
1303 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1305 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1306 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1307 return append_node (n
);
1310 /* Append S to the decision tree. */
1313 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1314 dt_operand
**indexes
)
1316 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1317 return append_node (n
);
1320 /* Insert O into the decision tree and return the decision tree node found
1324 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1325 unsigned pos
, dt_node
*parent
)
1327 dt_node
*q
, *elm
= 0;
1329 if (capture
*c
= dyn_cast
<capture
*> (o
))
1331 unsigned capt_index
= c
->where
;
1333 if (indexes
[capt_index
] == 0)
1336 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1339 q
= elm
= p
->append_true_op (parent
, pos
);
1342 // get to the last capture
1343 for (operand
*what
= c
->what
;
1344 what
&& is_a
<capture
*> (what
);
1345 c
= as_a
<capture
*> (what
), what
= c
->what
)
1350 unsigned cc_index
= c
->where
;
1351 dt_operand
*match_op
= indexes
[cc_index
];
1353 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1354 elm
= decision_tree::find_node (p
->kids
, &temp
);
1358 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1359 elm
= decision_tree::find_node (p
->kids
, &temp
);
1364 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1365 elm
= decision_tree::find_node (p
->kids
, &temp
);
1369 gcc_assert (elm
->type
== dt_node::DT_TRUE
1370 || elm
->type
== dt_node::DT_OPERAND
1371 || elm
->type
== dt_node::DT_MATCH
);
1372 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1377 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1379 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1384 p
= p
->append_op (o
, parent
, pos
);
1387 if (expr
*e
= dyn_cast
<expr
*>(o
))
1389 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1390 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1396 /* Insert S into the decision tree. */
1399 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1401 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1402 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1403 p
->append_simplify (s
, pattern_no
, indexes
);
1406 /* Debug functions to dump the decision tree. */
1409 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1411 if (p
->type
== dt_node::DT_NODE
)
1412 fprintf (f
, "root");
1416 for (unsigned i
= 0; i
< indent
; i
++)
1419 if (p
->type
== dt_node::DT_OPERAND
)
1421 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1422 print_operand (dop
->op
, f
, true);
1424 else if (p
->type
== dt_node::DT_TRUE
)
1425 fprintf (f
, "true");
1426 else if (p
->type
== dt_node::DT_MATCH
)
1427 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1428 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1430 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1431 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1432 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1433 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1438 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1440 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1441 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1445 decision_tree::print (FILE *f
)
1447 return decision_tree::print_node (root
, f
);
1451 /* For GENERIC we have to take care of wrapping multiple-used
1452 expressions with side-effects in save_expr and preserve side-effects
1453 of expressions with omit_one_operand. Analyze captures in
1454 match, result and with expressions and perform early-outs
1455 on the outermost match expression operands for cases we cannot
1460 capture_info (simplify
*s
);
1461 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1462 void walk_result (operand
*o
, bool);
1463 void walk_c_expr (c_expr
*);
1469 bool force_no_side_effects_p
;
1470 bool cond_expr_cond_p
;
1471 unsigned long toplevel_msk
;
1472 int result_use_count
;
1475 auto_vec
<cinfo
> info
;
1476 unsigned long force_no_side_effects
;
1479 /* Analyze captures in S. */
1481 capture_info::capture_info (simplify
*s
)
1485 || ((e
= dyn_cast
<expr
*> (s
->result
))
1486 && is_a
<predicate_id
*> (e
->operation
)))
1488 force_no_side_effects
= -1;
1492 force_no_side_effects
= 0;
1493 info
.safe_grow_cleared (s
->capture_max
+ 1);
1494 e
= as_a
<expr
*> (s
->match
);
1495 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1496 walk_match (e
->ops
[i
], i
,
1497 (i
!= 0 && *e
->operation
== COND_EXPR
)
1498 || *e
->operation
== TRUTH_ANDIF_EXPR
1499 || *e
->operation
== TRUTH_ORIF_EXPR
,
1501 && (*e
->operation
== COND_EXPR
1502 || *e
->operation
== VEC_COND_EXPR
));
1504 walk_result (s
->result
, false);
1506 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1507 if (s
->ifexpr_vec
[i
].is_with
)
1508 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1511 /* Analyze captures in the match expression piece O. */
1514 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1515 bool conditional_p
, bool cond_expr_cond_p
)
1517 if (capture
*c
= dyn_cast
<capture
*> (o
))
1519 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1520 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1521 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1522 /* Mark expr (non-leaf) captures and recurse. */
1524 && is_a
<expr
*> (c
->what
))
1526 info
[c
->where
].expr_p
= true;
1527 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1530 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1532 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1534 bool cond_p
= conditional_p
;
1535 bool cond_expr_cond_p
= false;
1536 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1538 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1539 || *e
->operation
== TRUTH_ORIF_EXPR
)
1542 && (*e
->operation
== COND_EXPR
1543 || *e
->operation
== VEC_COND_EXPR
))
1544 cond_expr_cond_p
= true;
1545 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1548 else if (is_a
<predicate
*> (o
))
1550 /* Mark non-captured leafs toplevel arg for checking. */
1551 force_no_side_effects
|= 1 << toplevel_arg
;
1557 /* Analyze captures in the result expression piece O. */
1560 capture_info::walk_result (operand
*o
, bool conditional_p
)
1562 if (capture
*c
= dyn_cast
<capture
*> (o
))
1564 info
[c
->where
].result_use_count
++;
1565 /* If we substitute an expression capture we don't know
1566 which captures this will end up using (well, we don't
1567 compute that). Force the uses to be side-effect free
1568 which means forcing the toplevels that reach the
1569 expression side-effect free. */
1570 if (info
[c
->where
].expr_p
)
1571 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1572 /* Mark CSE capture capture uses as forced to have
1575 && is_a
<expr
*> (c
->what
))
1577 info
[c
->where
].cse_p
= true;
1578 walk_result (c
->what
, true);
1581 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1583 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1585 bool cond_p
= conditional_p
;
1586 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1588 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1589 || *e
->operation
== TRUTH_ORIF_EXPR
)
1591 walk_result (e
->ops
[i
], cond_p
);
1594 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1600 /* Look for captures in the C expr E. */
1603 capture_info::walk_c_expr (c_expr
*e
)
1605 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1606 unsigned p_depth
= 0;
1607 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1609 const cpp_token
*t
= &e
->code
[i
];
1610 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1611 if (t
->type
== CPP_NAME
1612 && strcmp ((const char *)CPP_HASHNODE
1613 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1614 && n
->type
== CPP_OPEN_PAREN
)
1616 else if (t
->type
== CPP_CLOSE_PAREN
1619 else if (p_depth
== 0
1620 && t
->type
== CPP_ATSIGN
1621 && (n
->type
== CPP_NUMBER
1622 || n
->type
== CPP_NAME
)
1623 && !(n
->flags
& PREV_WHITE
))
1626 if (n
->type
== CPP_NUMBER
)
1627 id
= (const char *)n
->val
.str
.text
;
1629 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1630 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1636 /* Code generation off the decision tree and the refered AST nodes. */
1639 is_conversion (id_base
*op
)
1641 return (*op
== CONVERT_EXPR
1643 || *op
== FLOAT_EXPR
1644 || *op
== FIX_TRUNC_EXPR
1645 || *op
== VIEW_CONVERT_EXPR
);
1648 /* Get the type to be used for generating operands of OP from the
1652 get_operand_type (id_base
*op
, const char *in_type
,
1653 const char *expr_type
,
1654 const char *other_oprnd_type
)
1656 /* Generally operands whose type does not match the type of the
1657 expression generated need to know their types but match and
1658 thus can fall back to 'other_oprnd_type'. */
1659 if (is_conversion (op
))
1660 return other_oprnd_type
;
1661 else if (*op
== REALPART_EXPR
1662 || *op
== IMAGPART_EXPR
)
1663 return other_oprnd_type
;
1664 else if (is_a
<operator_id
*> (op
)
1665 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1666 return other_oprnd_type
;
1669 /* Otherwise all types should match - choose one in order of
1676 return other_oprnd_type
;
1680 /* Generate transform code for an expression. */
1683 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1684 const char *in_type
, capture_info
*cinfo
,
1685 dt_operand
**indexes
, bool)
1687 bool conversion_p
= is_conversion (operation
);
1688 const char *type
= expr_type
;
1691 /* If there was a type specification in the pattern use it. */
1693 else if (conversion_p
)
1694 /* For conversions we need to build the expression using the
1695 outer type passed in. */
1697 else if (*operation
== REALPART_EXPR
1698 || *operation
== IMAGPART_EXPR
)
1700 /* __real and __imag use the component type of its operand. */
1701 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1704 else if (is_a
<operator_id
*> (operation
)
1705 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1707 /* comparisons use boolean_type_node (or what gets in), but
1708 their operands need to figure out the types themselves. */
1709 sprintf (optype
, "boolean_type_node");
1714 /* Other operations are of the same type as their first operand. */
1715 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1719 fatal ("two conversions in a row");
1722 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1724 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1725 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1728 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1730 = get_operand_type (operation
, in_type
, expr_type
,
1731 i
== 0 ? NULL
: op0type
);
1732 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1733 ((!(*operation
== COND_EXPR
)
1734 && !(*operation
== VEC_COND_EXPR
))
1739 if (*operation
== CONVERT_EXPR
)
1742 opr
= operation
->id
;
1746 /* ??? Building a stmt can fail for various reasons here, seq being
1747 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1748 So if we fail here we should continue matching other patterns. */
1749 fprintf (f
, " code_helper tem_code = %s;\n"
1750 " tree tem_ops[3] = { ", opr
);
1751 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1752 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1753 i
== ops
.length () - 1 ? " };\n" : ", ");
1754 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1755 ops
.length (), type
);
1756 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1757 " if (!res) return false;\n", type
);
1761 if (operation
->kind
== id_base::CODE
)
1762 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1763 ops
.length(), opr
, type
);
1765 fprintf (f
, " res = build_call_expr_loc (loc, "
1766 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1767 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1768 fprintf (f
, ", ops%d[%u]", depth
, i
);
1769 fprintf (f
, ");\n");
1771 fprintf (f
, "%s = res;\n", dest
);
1775 /* Generate code for a c_expr which is either the expression inside
1776 an if statement or a sequence of statements which computes a
1777 result to be stored to DEST. */
1780 c_expr::gen_transform (FILE *f
, const char *dest
,
1781 bool, int, const char *, capture_info
*,
1782 dt_operand
**, bool)
1784 if (dest
&& nr_stmts
== 1)
1785 fprintf (f
, "%s = ", dest
);
1787 unsigned stmt_nr
= 1;
1788 for (unsigned i
= 0; i
< code
.length (); ++i
)
1790 const cpp_token
*token
= &code
[i
];
1792 /* Replace captures for code-gen. */
1793 if (token
->type
== CPP_ATSIGN
)
1795 const cpp_token
*n
= &code
[i
+1];
1796 if ((n
->type
== CPP_NUMBER
1797 || n
->type
== CPP_NAME
)
1798 && !(n
->flags
& PREV_WHITE
))
1800 if (token
->flags
& PREV_WHITE
)
1803 if (n
->type
== CPP_NUMBER
)
1804 id
= (const char *)n
->val
.str
.text
;
1806 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1807 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1813 if (token
->flags
& PREV_WHITE
)
1816 if (token
->type
== CPP_NAME
)
1818 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1820 for (j
= 0; j
< ids
.length (); ++j
)
1822 if (strcmp (id
, ids
[j
].id
) == 0)
1824 fprintf (f
, "%s", ids
[j
].oper
);
1828 if (j
< ids
.length ())
1832 /* Output the token as string. */
1833 char *tk
= (char *)cpp_token_as_text (r
, token
);
1836 if (token
->type
== CPP_SEMICOLON
)
1839 if (dest
&& stmt_nr
== nr_stmts
)
1840 fprintf (f
, "\n %s = ", dest
);
1847 /* Generate transform code for a capture. */
1850 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1851 const char *in_type
, capture_info
*cinfo
,
1852 dt_operand
**indexes
, bool expand_compares
)
1854 if (what
&& is_a
<expr
*> (what
))
1856 if (indexes
[where
] == 0)
1859 sprintf (buf
, "captures[%u]", where
);
1860 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1864 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1866 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1867 with substituting a capture of that.
1868 ??? Returning false here will also not allow any other patterns
1870 if (gimple
&& expand_compares
1871 && cinfo
->info
[where
].cond_expr_cond_p
)
1872 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1874 " if (!seq) return false;\n"
1875 " %s = gimple_build (seq, TREE_CODE (%s),"
1876 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1877 " TREE_OPERAND (%s, 1));\n"
1878 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1881 /* Return the name of the operand representing the decision tree node.
1882 Use NAME as space to generate it. */
1885 dt_operand::get_name (char *name
)
1888 sprintf (name
, "t");
1889 else if (parent
->level
== 1)
1890 sprintf (name
, "op%u", pos
);
1891 else if (parent
->type
== dt_node::DT_MATCH
)
1892 return parent
->get_name (name
);
1894 sprintf (name
, "o%u%u", parent
->level
, pos
);
1898 /* Fill NAME with the operand name at position POS. */
1901 dt_operand::gen_opname (char *name
, unsigned pos
)
1904 sprintf (name
, "op%u", pos
);
1906 sprintf (name
, "o%u%u", level
, pos
);
1909 /* Generate matching code for the decision tree operand which is
1913 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1915 predicate
*p
= as_a
<predicate
*> (op
);
1917 if (p
->p
->matchers
.exists ())
1919 /* If this is a predicate generated from a pattern mangle its
1920 name and pass on the valueize hook. */
1922 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1924 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1927 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1932 /* Generate matching code for the decision tree operand which is
1936 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1938 char match_opname
[20];
1939 match_dop
->get_name (match_opname
);
1940 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1941 opname
, match_opname
, opname
, match_opname
);
1946 /* Generate GIMPLE matching code for the decision tree operand. */
1949 dt_operand::gen_gimple_expr (FILE *f
)
1951 expr
*e
= static_cast<expr
*> (op
);
1952 id_base
*id
= e
->operation
;
1953 unsigned n_ops
= e
->ops
.length ();
1955 for (unsigned i
= 0; i
< n_ops
; ++i
)
1957 char child_opname
[20];
1958 gen_opname (child_opname
, i
);
1960 if (id
->kind
== id_base::CODE
)
1963 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1964 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1966 /* ??? If this is a memory operation we can't (and should not)
1967 match this. The only sensible operand types are
1968 SSA names and invariants. */
1969 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1971 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1972 "|| is_gimple_min_invariant (%s))\n"
1973 "&& (%s = do_valueize (valueize, %s)))\n"
1974 "{\n", child_opname
, child_opname
, child_opname
,
1979 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1980 child_opname
, i
+ 1);
1983 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1985 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1986 child_opname
, child_opname
);
1993 /* Generate GENERIC matching code for the decision tree operand. */
1996 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1998 expr
*e
= static_cast<expr
*> (op
);
1999 unsigned n_ops
= e
->ops
.length ();
2001 for (unsigned i
= 0; i
< n_ops
; ++i
)
2003 char child_opname
[20];
2004 gen_opname (child_opname
, i
);
2006 if (e
->operation
->kind
== id_base::CODE
)
2007 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2008 child_opname
, opname
, i
);
2010 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2011 child_opname
, opname
, i
);
2017 /* Generate matching code for the children of the decision tree node. */
2020 dt_node::gen_kids (FILE *f
, bool gimple
)
2022 auto_vec
<dt_operand
*> gimple_exprs
;
2023 auto_vec
<dt_operand
*> generic_exprs
;
2024 auto_vec
<dt_operand
*> fns
;
2025 auto_vec
<dt_operand
*> generic_fns
;
2026 auto_vec
<dt_operand
*> preds
;
2027 auto_vec
<dt_node
*> others
;
2029 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2031 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2033 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2034 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2036 if (e
->ops
.length () == 0
2037 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2038 generic_exprs
.safe_push (op
);
2039 else if (e
->operation
->kind
== id_base::FN
)
2044 generic_fns
.safe_push (op
);
2046 else if (e
->operation
->kind
== id_base::PREDICATE
)
2047 preds
.safe_push (op
);
2051 gimple_exprs
.safe_push (op
);
2053 generic_exprs
.safe_push (op
);
2056 else if (op
->op
->type
== operand::OP_PREDICATE
)
2057 others
.safe_push (kids
[i
]);
2061 else if (kids
[i
]->type
== dt_node::DT_MATCH
2062 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2063 others
.safe_push (kids
[i
]);
2064 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2066 /* A DT_TRUE operand serves as a barrier - generate code now
2067 for what we have collected sofar. */
2068 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2069 fns
, generic_fns
, preds
, others
);
2070 /* And output the true operand itself. */
2071 kids
[i
]->gen (f
, gimple
);
2072 gimple_exprs
.truncate (0);
2073 generic_exprs
.truncate (0);
2075 generic_fns
.truncate (0);
2077 others
.truncate (0);
2083 /* Generate code for the remains. */
2084 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2085 fns
, generic_fns
, preds
, others
);
2088 /* Generate matching code for the children of the decision tree node. */
2091 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2092 vec
<dt_operand
*> gimple_exprs
,
2093 vec
<dt_operand
*> generic_exprs
,
2094 vec
<dt_operand
*> fns
,
2095 vec
<dt_operand
*> generic_fns
,
2096 vec
<dt_operand
*> preds
,
2097 vec
<dt_node
*> others
)
2100 char *kid_opname
= buf
;
2102 unsigned exprs_len
= gimple_exprs
.length ();
2103 unsigned gexprs_len
= generic_exprs
.length ();
2104 unsigned fns_len
= fns
.length ();
2105 unsigned gfns_len
= generic_fns
.length ();
2107 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2110 gimple_exprs
[0]->get_name (kid_opname
);
2112 fns
[0]->get_name (kid_opname
);
2114 generic_fns
[0]->get_name (kid_opname
);
2116 generic_exprs
[0]->get_name (kid_opname
);
2118 fprintf (f
, "switch (TREE_CODE (%s))\n"
2122 if (exprs_len
|| fns_len
)
2124 fprintf (f
, "case SSA_NAME:\n");
2125 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2127 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2131 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2132 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2134 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2136 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2137 id_base
*op
= e
->operation
;
2138 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2139 fprintf (f
, "CASE_CONVERT:\n");
2141 fprintf (f
, "case %s:\n", op
->id
);
2143 gimple_exprs
[i
]->gen (f
, true);
2144 fprintf (f
, "break;\n"
2147 fprintf (f
, "default:;\n"
2154 fprintf (f
, "else ");
2156 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2158 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2159 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2162 for (unsigned i
= 0; i
< fns_len
; ++i
)
2164 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2165 fprintf (f
, "case %s:\n"
2166 "{\n", e
->operation
->id
);
2167 fns
[i
]->gen (f
, true);
2168 fprintf (f
, "break;\n"
2172 fprintf (f
, "default:;\n"
2181 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2183 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2184 id_base
*op
= e
->operation
;
2185 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2186 fprintf (f
, "CASE_CONVERT:\n");
2188 fprintf (f
, "case %s:\n", op
->id
);
2190 generic_exprs
[i
]->gen (f
, gimple
);
2191 fprintf (f
, "break;\n"
2197 fprintf (f
, "case CALL_EXPR:\n"
2199 "tree fndecl = get_callee_fndecl (%s);\n"
2200 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2201 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2204 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2206 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2207 gcc_assert (e
->operation
->kind
== id_base::FN
);
2209 fprintf (f
, "case %s:\n"
2210 "{\n", e
->operation
->id
);
2211 generic_fns
[j
]->gen (f
, false);
2212 fprintf (f
, "break;\n"
2216 fprintf (f
, "default:;\n"
2222 /* Close switch (TREE_CODE ()). */
2223 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2224 fprintf (f
, "default:;\n"
2227 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2229 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2230 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2231 preds
[i
]->get_name (kid_opname
);
2232 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2233 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2234 gimple
? "gimple" : "tree",
2235 p
->id
, kid_opname
, kid_opname
,
2236 gimple
? ", valueize" : "");
2238 for (int j
= 0; j
< p
->nargs
; ++j
)
2240 char child_opname
[20];
2241 preds
[i
]->gen_opname (child_opname
, j
);
2242 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2244 preds
[i
]->gen_kids (f
, gimple
);
2248 for (unsigned i
= 0; i
< others
.length (); ++i
)
2249 others
[i
]->gen (f
, gimple
);
2252 /* Generate matching code for the decision tree operand. */
2255 dt_operand::gen (FILE *f
, bool gimple
)
2260 unsigned n_braces
= 0;
2262 if (type
== DT_OPERAND
)
2265 case operand::OP_PREDICATE
:
2266 n_braces
= gen_predicate (f
, opname
, gimple
);
2269 case operand::OP_EXPR
:
2271 n_braces
= gen_gimple_expr (f
);
2273 n_braces
= gen_generic_expr (f
, opname
);
2279 else if (type
== DT_TRUE
)
2281 else if (type
== DT_MATCH
)
2282 n_braces
= gen_match_op (f
, opname
);
2286 gen_kids (f
, gimple
);
2288 for (unsigned i
= 0; i
< n_braces
; ++i
)
2294 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2295 step of a '(simplify ...)' or '(match ...)'. This handles everything
2296 that is not part of the decision tree (simplify->match). */
2299 dt_simplify::gen (FILE *f
, bool gimple
)
2302 output_line_directive (f
, s
->result_location
);
2303 if (s
->capture_max
>= 0)
2304 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2305 s
->capture_max
+ 1);
2307 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2311 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2314 unsigned n_braces
= 0;
2315 if (s
->ifexpr_vec
!= vNULL
)
2317 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2319 if_or_with
&w
= s
->ifexpr_vec
[i
];
2323 output_line_directive (f
, w
.location
);
2324 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2329 output_line_directive (f
, w
.location
);
2330 fprintf (f
, "if (");
2331 if (i
== s
->ifexpr_vec
.length () - 1
2332 || s
->ifexpr_vec
[i
+1].is_with
)
2333 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2342 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2346 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2352 while (j
< s
->ifexpr_vec
.length ()
2353 && !s
->ifexpr_vec
[j
].is_with
);
2363 /* Analyze captures and perform early-outs on the incoming arguments
2364 that cover cases we cannot handle. */
2365 capture_info
cinfo (s
);
2369 && !((e
= dyn_cast
<expr
*> (s
->result
))
2370 && is_a
<predicate_id
*> (e
->operation
)))
2372 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2373 if (cinfo
.force_no_side_effects
& (1 << i
))
2374 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2375 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2376 if (cinfo
.info
[i
].cse_p
)
2378 else if (cinfo
.info
[i
].force_no_side_effects_p
2379 && (cinfo
.info
[i
].toplevel_msk
2380 & cinfo
.force_no_side_effects
) == 0)
2381 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2382 "return NULL_TREE;\n", i
);
2383 else if ((cinfo
.info
[i
].toplevel_msk
2384 & cinfo
.force_no_side_effects
) != 0)
2385 /* Mark capture as having no side-effects if we had to verify
2386 that via forced toplevel operand checks. */
2387 cinfo
.info
[i
].force_no_side_effects_p
= true;
2390 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2391 "fprintf (dump_file, \"Applying pattern ");
2392 output_line_directive (f
, s
->result_location
, true);
2393 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2395 operand
*result
= s
->result
;
2398 /* If there is no result then this is a predicate implementation. */
2399 fprintf (f
, "return true;\n");
2403 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2404 in outermost position). */
2405 if (result
->type
== operand::OP_EXPR
2406 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2407 result
= as_a
<expr
*> (result
)->ops
[0];
2408 if (result
->type
== operand::OP_EXPR
)
2410 expr
*e
= as_a
<expr
*> (result
);
2411 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2413 fprintf (f
, "*res_code = %s;\n",
2414 *e
->operation
== CONVERT_EXPR
2415 ? "NOP_EXPR" : e
->operation
->id
);
2416 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2419 snprintf (dest
, 32, " res_ops[%d]", j
);
2421 = get_operand_type (e
->operation
,
2422 "type", e
->expr_type
,
2424 ? NULL
: "TREE_TYPE (res_ops[0])");
2425 /* We need to expand GENERIC conditions we captured from
2427 bool expand_generic_cond_exprs_p
2429 /* But avoid doing that if the GENERIC condition is
2430 valid - which it is in the first operand of COND_EXPRs
2431 and VEC_COND_EXRPs. */
2432 && ((!(*e
->operation
== COND_EXPR
)
2433 && !(*e
->operation
== VEC_COND_EXPR
))
2435 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2436 indexes
, expand_generic_cond_exprs_p
);
2439 /* Re-fold the toplevel result. It's basically an embedded
2440 gimple_build w/o actually building the stmt. */
2442 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2443 "res_ops, valueize);\n", e
->ops
.length ());
2445 else if (result
->type
== operand::OP_CAPTURE
2446 || result
->type
== operand::OP_C_EXPR
)
2448 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2449 &cinfo
, indexes
, false);
2450 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2451 if (is_a
<capture
*> (result
)
2452 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2454 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2455 with substituting a capture of that. */
2456 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2458 " tree tem = res_ops[0];\n"
2459 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2460 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2466 fprintf (f
, "return true;\n");
2470 bool is_predicate
= false;
2471 if (result
->type
== operand::OP_EXPR
)
2473 expr
*e
= as_a
<expr
*> (result
);
2474 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2475 /* Search for captures used multiple times in the result expression
2476 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2478 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2480 if (!cinfo
.info
[i
].force_no_side_effects_p
2481 && cinfo
.info
[i
].result_use_count
> 1)
2482 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2483 " captures[%d] = save_expr (captures[%d]);\n",
2486 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2490 snprintf (dest
, 32, "res_ops[%d]", j
);
2493 fprintf (f
, " tree res_op%d;\n", j
);
2494 snprintf (dest
, 32, " res_op%d", j
);
2497 = get_operand_type (e
->operation
,
2498 "type", e
->expr_type
,
2500 ? NULL
: "TREE_TYPE (res_op0)");
2501 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2505 fprintf (f
, "return true;\n");
2508 fprintf (f
, " tree res;\n");
2509 /* Re-fold the toplevel result. Use non_lvalue to
2510 build NON_LVALUE_EXPRs so they get properly
2511 ignored when in GIMPLE form. */
2512 if (*e
->operation
== NON_LVALUE_EXPR
)
2513 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2516 if (e
->operation
->kind
== id_base::CODE
)
2517 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2519 *e
->operation
== CONVERT_EXPR
2520 ? "NOP_EXPR" : e
->operation
->id
);
2522 fprintf (f
, " res = build_call_expr_loc "
2523 "(loc, builtin_decl_implicit (%s), %d",
2524 e
->operation
->id
, e
->ops
.length());
2525 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2526 fprintf (f
, ", res_op%d", j
);
2527 fprintf (f
, ");\n");
2531 else if (result
->type
== operand::OP_CAPTURE
2532 || result
->type
== operand::OP_C_EXPR
)
2535 fprintf (f
, " tree res;\n");
2536 s
->result
->gen_transform (f
, " res", false, 1, "type",
2543 /* Search for captures not used in the result expression and dependent
2544 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2545 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2547 if (!cinfo
.info
[i
].force_no_side_effects_p
2548 && !cinfo
.info
[i
].expr_p
2549 && cinfo
.info
[i
].result_use_count
== 0)
2550 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2551 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2552 " fold_ignored_result (captures[%d]), res);\n",
2555 fprintf (f
, " return res;\n");
2559 for (unsigned i
= 0; i
< n_braces
; ++i
)
2565 /* Main entry to generate code for matching GIMPLE IL off the decision
2569 decision_tree::gen_gimple (FILE *f
)
2571 for (unsigned n
= 1; n
<= 3; ++n
)
2573 fprintf (f
, "\nstatic bool\n"
2574 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2575 " gimple_seq *seq, tree (*valueize)(tree),\n"
2576 " code_helper code, tree type");
2577 for (unsigned i
= 0; i
< n
; ++i
)
2578 fprintf (f
, ", tree op%d", i
);
2582 fprintf (f
, "switch (code.get_rep())\n"
2584 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2586 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2587 expr
*e
= static_cast<expr
*>(dop
->op
);
2588 if (e
->ops
.length () != n
)
2591 if (*e
->operation
== CONVERT_EXPR
2592 || *e
->operation
== NOP_EXPR
)
2593 fprintf (f
, "CASE_CONVERT:\n");
2595 fprintf (f
, "case %s%s:\n",
2596 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2599 dop
->gen_kids (f
, true);
2600 fprintf (f
, "break;\n");
2603 fprintf (f
, "default:;\n"
2606 fprintf (f
, "return false;\n");
2611 /* Main entry to generate code for matching GENERIC IL off the decision
2615 decision_tree::gen_generic (FILE *f
)
2617 for (unsigned n
= 1; n
<= 3; ++n
)
2619 fprintf (f
, "\ntree\n"
2620 "generic_simplify (location_t loc, enum tree_code code, "
2621 "tree type ATTRIBUTE_UNUSED");
2622 for (unsigned i
= 0; i
< n
; ++i
)
2623 fprintf (f
, ", tree op%d", i
);
2627 fprintf (f
, "switch (code)\n"
2629 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2631 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2632 expr
*e
= static_cast<expr
*>(dop
->op
);
2633 if (e
->ops
.length () != n
2634 /* Builtin simplifications are somewhat premature on
2635 GENERIC. The following drops patterns with outermost
2636 calls. It's easy to emit overloads for function code
2637 though if necessary. */
2638 || e
->operation
->kind
!= id_base::CODE
)
2641 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2642 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2643 fprintf (f
, "CASE_CONVERT:\n");
2645 fprintf (f
, "case %s:\n", e
->operation
->id
);
2647 dop
->gen_kids (f
, false);
2648 fprintf (f
, "break;\n"
2651 fprintf (f
, "default:;\n"
2654 fprintf (f
, "return NULL_TREE;\n");
2659 /* Output code to implement the predicate P from the decision tree DT. */
2662 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2664 fprintf (f
, "\nbool\n"
2665 "%s%s (tree t%s%s)\n"
2666 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2667 p
->nargs
> 0 ? ", tree *res_ops" : "",
2668 gimple
? ", tree (*valueize)(tree)" : "");
2669 /* Conveniently make 'type' available. */
2670 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2673 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2674 dt
.root
->gen_kids (f
, gimple
);
2676 fprintf (f
, "return false;\n"
2680 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2683 write_header (FILE *f
, const char *head
)
2685 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2686 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2688 /* Include the header instead of writing it awkwardly quoted here. */
2689 fprintf (f
, "\n#include \"%s\"\n", head
);
2699 parser (cpp_reader
*);
2702 const cpp_token
*next ();
2703 const cpp_token
*peek ();
2704 const cpp_token
*peek_ident (const char * = NULL
);
2705 const cpp_token
*expect (enum cpp_ttype
);
2706 void eat_token (enum cpp_ttype
);
2707 const char *get_string ();
2708 const char *get_ident ();
2709 void eat_ident (const char *);
2710 const char *get_number ();
2712 id_base
*parse_operation ();
2713 operand
*parse_capture (operand
*);
2714 operand
*parse_expr ();
2715 c_expr
*parse_c_expr (cpp_ttype
);
2716 operand
*parse_op ();
2718 void record_operlist (source_location
, user_id
*);
2720 void parse_pattern ();
2721 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2722 operand
*, source_location
);
2723 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2725 void parse_for (source_location
);
2726 void parse_if (source_location
);
2727 void parse_predicates (source_location
);
2728 void parse_operator_list (source_location
);
2731 vec
<if_or_with
> active_ifs
;
2732 vec
<vec
<user_id
*> > active_fors
;
2733 hash_set
<user_id
*> *oper_lists_set
;
2734 vec
<user_id
*> oper_lists
;
2736 cid_map_t
*capture_ids
;
2739 vec
<simplify
*> simplifiers
;
2740 vec
<predicate_id
*> user_predicates
;
2741 bool parsing_match_operand
;
2744 /* Lexing helpers. */
2746 /* Read the next non-whitespace token from R. */
2751 const cpp_token
*token
;
2754 token
= cpp_get_token (r
);
2756 while (token
->type
== CPP_PADDING
2757 && token
->type
!= CPP_EOF
);
2761 /* Peek at the next non-whitespace token from R. */
2766 const cpp_token
*token
;
2770 token
= cpp_peek_token (r
, i
++);
2772 while (token
->type
== CPP_PADDING
2773 && token
->type
!= CPP_EOF
);
2774 /* If we peek at EOF this is a fatal error as it leaves the
2775 cpp_reader in unusable state. Assume we really wanted a
2776 token and thus this EOF is unexpected. */
2777 if (token
->type
== CPP_EOF
)
2778 fatal_at (token
, "unexpected end of file");
2782 /* Peek at the next identifier token (or return NULL if the next
2783 token is not an identifier or equal to ID if supplied). */
2786 parser::peek_ident (const char *id
)
2788 const cpp_token
*token
= peek ();
2789 if (token
->type
!= CPP_NAME
)
2795 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2796 if (strcmp (id
, t
) == 0)
2802 /* Read the next token from R and assert it is of type TK. */
2805 parser::expect (enum cpp_ttype tk
)
2807 const cpp_token
*token
= next ();
2808 if (token
->type
!= tk
)
2809 fatal_at (token
, "expected %s, got %s",
2810 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2815 /* Consume the next token from R and assert it is of type TK. */
2818 parser::eat_token (enum cpp_ttype tk
)
2823 /* Read the next token from R and assert it is of type CPP_STRING and
2824 return its value. */
2827 parser::get_string ()
2829 const cpp_token
*token
= expect (CPP_STRING
);
2830 return (const char *)token
->val
.str
.text
;
2833 /* Read the next token from R and assert it is of type CPP_NAME and
2834 return its value. */
2837 parser::get_ident ()
2839 const cpp_token
*token
= expect (CPP_NAME
);
2840 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2843 /* Eat an identifier token with value S from R. */
2846 parser::eat_ident (const char *s
)
2848 const cpp_token
*token
= peek ();
2849 const char *t
= get_ident ();
2850 if (strcmp (s
, t
) != 0)
2851 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2854 /* Read the next token from R and assert it is of type CPP_NUMBER and
2855 return its value. */
2858 parser::get_number ()
2860 const cpp_token
*token
= expect (CPP_NUMBER
);
2861 return (const char *)token
->val
.str
.text
;
2865 /* Record an operator-list use for transparent for handling. */
2868 parser::record_operlist (source_location loc
, user_id
*p
)
2870 if (!oper_lists_set
->add (p
))
2872 if (!oper_lists
.is_empty ()
2873 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2874 fatal_at (loc
, "User-defined operator list does not have the "
2875 "same number of entries as others used in the pattern");
2876 oper_lists
.safe_push (p
);
2880 /* Parse the operator ID, special-casing convert?, convert1? and
2884 parser::parse_operation ()
2886 const cpp_token
*id_tok
= peek ();
2887 const char *id
= get_ident ();
2888 const cpp_token
*token
= peek ();
2889 if (strcmp (id
, "convert0") == 0)
2890 fatal_at (id_tok
, "use 'convert?' here");
2891 if (token
->type
== CPP_QUERY
2892 && !(token
->flags
& PREV_WHITE
))
2894 if (strcmp (id
, "convert") == 0)
2896 else if (strcmp (id
, "convert1") == 0)
2898 else if (strcmp (id
, "convert2") == 0)
2901 fatal_at (id_tok
, "non-convert operator conditionalized");
2903 if (!parsing_match_operand
)
2904 fatal_at (id_tok
, "conditional convert can only be used in "
2905 "match expression");
2906 eat_token (CPP_QUERY
);
2908 else if (strcmp (id
, "convert1") == 0
2909 || strcmp (id
, "convert2") == 0)
2910 fatal_at (id_tok
, "expected '?' after conditional operator");
2911 id_base
*op
= get_operator (id
);
2913 fatal_at (id_tok
, "unknown operator %s", id
);
2915 user_id
*p
= dyn_cast
<user_id
*> (op
);
2916 if (p
&& p
->is_oper_list
)
2918 if (active_fors
.length() == 0)
2919 record_operlist (id_tok
->src_loc
, p
);
2921 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
2927 capture = '@'<number> */
2930 parser::parse_capture (operand
*op
)
2932 eat_token (CPP_ATSIGN
);
2933 const cpp_token
*token
= peek ();
2934 const char *id
= NULL
;
2935 if (token
->type
== CPP_NUMBER
)
2937 else if (token
->type
== CPP_NAME
)
2940 fatal_at (token
, "expected number or identifier");
2941 unsigned next_id
= capture_ids
->elements ();
2943 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2946 return new capture (num
, op
);
2949 /* Parse an expression
2950 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2953 parser::parse_expr ()
2955 expr
*e
= new expr (parse_operation ());
2956 const cpp_token
*token
= peek ();
2958 bool is_commutative
= false;
2959 const char *expr_type
= NULL
;
2961 if (token
->type
== CPP_COLON
2962 && !(token
->flags
& PREV_WHITE
))
2964 eat_token (CPP_COLON
);
2966 if (token
->type
== CPP_NAME
2967 && !(token
->flags
& PREV_WHITE
))
2969 const char *s
= get_ident ();
2970 if (s
[0] == 'c' && !s
[1])
2972 if (!parsing_match_operand
)
2974 "flag 'c' can only be used in match expression");
2975 is_commutative
= true;
2977 else if (s
[1] != '\0')
2979 if (parsing_match_operand
)
2980 fatal_at (token
, "type can only be used in result expression");
2984 fatal_at (token
, "flag %s not recognized", s
);
2989 fatal_at (token
, "expected flag or type specifying identifier");
2992 if (token
->type
== CPP_ATSIGN
2993 && !(token
->flags
& PREV_WHITE
))
2994 op
= parse_capture (e
);
2999 const cpp_token
*token
= peek ();
3000 if (token
->type
== CPP_CLOSE_PAREN
)
3002 if (e
->operation
->nargs
!= -1
3003 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3004 fatal_at (token
, "'%s' expects %u operands, not %u",
3005 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3008 if (e
->ops
.length () == 2)
3009 e
->is_commutative
= true;
3011 fatal_at (token
, "only binary operators or function with "
3012 "two arguments can be marked commutative");
3014 e
->expr_type
= expr_type
;
3017 e
->append_op (parse_op ());
3022 /* Lex native C code delimited by START recording the preprocessing tokens
3023 for later processing.
3024 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3027 parser::parse_c_expr (cpp_ttype start
)
3029 const cpp_token
*token
;
3032 vec
<cpp_token
> code
= vNULL
;
3033 unsigned nr_stmts
= 0;
3035 if (start
== CPP_OPEN_PAREN
)
3036 end
= CPP_CLOSE_PAREN
;
3037 else if (start
== CPP_OPEN_BRACE
)
3038 end
= CPP_CLOSE_BRACE
;
3046 /* Count brace pairs to find the end of the expr to match. */
3047 if (token
->type
== start
)
3049 else if (token
->type
== end
3053 /* This is a lame way of counting the number of statements. */
3054 if (token
->type
== CPP_SEMICOLON
)
3057 /* If this is possibly a user-defined identifier mark it used. */
3058 if (token
->type
== CPP_NAME
)
3060 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3061 (token
->val
.node
.node
)->ident
.str
);
3063 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3064 record_operlist (token
->src_loc
, p
);
3067 /* Record the token. */
3068 code
.safe_push (*token
);
3071 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3074 /* Parse an operand which is either an expression, a predicate or
3075 a standalone capture.
3076 op = predicate | expr | c_expr | capture */
3081 const cpp_token
*token
= peek ();
3082 struct operand
*op
= NULL
;
3083 if (token
->type
== CPP_OPEN_PAREN
)
3085 eat_token (CPP_OPEN_PAREN
);
3087 eat_token (CPP_CLOSE_PAREN
);
3089 else if (token
->type
== CPP_OPEN_BRACE
)
3091 op
= parse_c_expr (CPP_OPEN_BRACE
);
3095 /* Remaining ops are either empty or predicates */
3096 if (token
->type
== CPP_NAME
)
3098 const char *id
= get_ident ();
3099 id_base
*opr
= get_operator (id
);
3101 fatal_at (token
, "expected predicate name");
3102 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3104 if (code
->nargs
!= 0)
3105 fatal_at (token
, "using an operator with operands as predicate");
3106 /* Parse the zero-operand operator "predicates" as
3108 op
= new expr (opr
);
3110 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3112 if (code
->nargs
!= 0)
3113 fatal_at (token
, "using an operator with operands as predicate");
3114 /* Parse the zero-operand operator "predicates" as
3116 op
= new expr (opr
);
3118 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3119 op
= new predicate (p
);
3121 fatal_at (token
, "using an unsupported operator as predicate");
3122 if (!parsing_match_operand
)
3123 fatal_at (token
, "predicates are only allowed in match expression");
3125 if (token
->flags
& PREV_WHITE
)
3128 else if (token
->type
!= CPP_COLON
3129 && token
->type
!= CPP_ATSIGN
)
3130 fatal_at (token
, "expected expression or predicate");
3131 /* optionally followed by a capture and a predicate. */
3132 if (token
->type
== CPP_COLON
)
3133 fatal_at (token
, "not implemented: predicate on leaf operand");
3134 if (token
->type
== CPP_ATSIGN
)
3135 op
= parse_capture (op
);
3141 /* Create a new simplify from the current parsing state and MATCH,
3142 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3145 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3146 operand
*match
, source_location match_loc
,
3147 operand
*result
, source_location result_loc
)
3149 /* Build and push a temporary for for operator list uses in expressions. */
3150 if (!oper_lists
.is_empty ())
3151 active_fors
.safe_push (oper_lists
);
3153 simplifiers
.safe_push
3154 (new simplify (match
, match_loc
, result
, result_loc
,
3155 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3157 if (!oper_lists
.is_empty ())
3162 simplify = 'simplify' <expr> <result-op>
3164 match = 'match' <ident> <expr> [<result-op>]
3166 <result-op> = <op> | <if> | <with>
3167 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3168 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3169 and fill SIMPLIFIERS with the results. */
3172 parser::parse_simplify (source_location match_location
,
3173 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3176 /* Reset the capture map. */
3178 capture_ids
= new cid_map_t
;
3179 /* Reset oper_lists and set. */
3180 hash_set
<user_id
*> olist
;
3181 oper_lists_set
= &olist
;
3184 const cpp_token
*loc
= peek ();
3185 parsing_match_operand
= true;
3186 struct operand
*match
= parse_op ();
3187 parsing_match_operand
= false;
3188 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3189 fatal_at (loc
, "outermost expression cannot be captured");
3190 if (match
->type
== operand::OP_EXPR
3191 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3192 fatal_at (loc
, "outermost expression cannot be a predicate");
3194 const cpp_token
*token
= peek ();
3196 /* If this if is immediately closed then it is part of a predicate
3197 definition. Push it. */
3198 if (token
->type
== CPP_CLOSE_PAREN
)
3201 fatal_at (token
, "expected transform expression");
3202 push_simplify (simplifiers
, match
, match_location
,
3203 result
, token
->src_loc
);
3207 unsigned active_ifs_len
= active_ifs
.length ();
3210 if (token
->type
== CPP_OPEN_PAREN
)
3212 source_location paren_loc
= token
->src_loc
;
3213 eat_token (CPP_OPEN_PAREN
);
3214 if (peek_ident ("if"))
3217 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3218 token
->src_loc
, false));
3219 /* If this if is immediately closed then it contains a
3220 manual matcher or is part of a predicate definition.
3222 if (peek ()->type
== CPP_CLOSE_PAREN
)
3225 fatal_at (token
, "manual transform not implemented");
3226 push_simplify (simplifiers
, match
, match_location
,
3230 else if (peek_ident ("with"))
3233 /* Parse (with c-expr expr) as (if-with (true) expr). */
3234 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3236 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3240 operand
*op
= result
;
3243 push_simplify (simplifiers
, match
, match_location
,
3244 op
, token
->src_loc
);
3245 eat_token (CPP_CLOSE_PAREN
);
3246 /* A "default" result closes the enclosing scope. */
3247 if (active_ifs
.length () > active_ifs_len
)
3249 eat_token (CPP_CLOSE_PAREN
);
3256 else if (token
->type
== CPP_CLOSE_PAREN
)
3258 /* Close a scope if requested. */
3259 if (active_ifs
.length () > active_ifs_len
)
3261 eat_token (CPP_CLOSE_PAREN
);
3271 fatal_at (token
, "expected match operand expression");
3272 push_simplify (simplifiers
, match
, match_location
,
3273 matcher
? result
: parse_op (), token
->src_loc
);
3274 /* A "default" result closes the enclosing scope. */
3275 if (active_ifs
.length () > active_ifs_len
)
3277 eat_token (CPP_CLOSE_PAREN
);
3287 /* Parsing of the outer control structures. */
3289 /* Parse a for expression
3290 for = '(' 'for' <subst>... <pattern> ')'
3291 subst = <ident> '(' <ident>... ')' */
3294 parser::parse_for (source_location
)
3296 auto_vec
<const cpp_token
*> user_id_tokens
;
3297 vec
<user_id
*> user_ids
= vNULL
;
3298 const cpp_token
*token
;
3299 unsigned min_n_opers
= 0, max_n_opers
= 0;
3304 if (token
->type
!= CPP_NAME
)
3307 /* Insert the user defined operators into the operator hash. */
3308 const char *id
= get_ident ();
3309 if (get_operator (id
) != NULL
)
3310 fatal_at (token
, "operator already defined");
3311 user_id
*op
= new user_id (id
);
3312 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3314 user_ids
.safe_push (op
);
3315 user_id_tokens
.safe_push (token
);
3317 eat_token (CPP_OPEN_PAREN
);
3320 while ((token
= peek_ident ()) != 0)
3322 const char *oper
= get_ident ();
3323 id_base
*idb
= get_operator (oper
);
3325 fatal_at (token
, "no such operator '%s'", oper
);
3326 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
3327 fatal_at (token
, "conditional operators cannot be used inside for");
3331 else if (idb
->nargs
== -1)
3333 else if (idb
->nargs
!= arity
)
3334 fatal_at (token
, "operator '%s' with arity %d does not match "
3335 "others with arity %d", oper
, idb
->nargs
, arity
);
3337 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3340 if (p
->is_oper_list
)
3341 op
->substitutes
.safe_splice (p
->substitutes
);
3343 fatal_at (token
, "iterator cannot be used as operator-list");
3346 op
->substitutes
.safe_push (idb
);
3349 token
= expect (CPP_CLOSE_PAREN
);
3351 unsigned nsubstitutes
= op
->substitutes
.length ();
3352 if (nsubstitutes
== 0)
3353 fatal_at (token
, "A user-defined operator must have at least "
3354 "one substitution");
3355 if (max_n_opers
== 0)
3357 min_n_opers
= nsubstitutes
;
3358 max_n_opers
= nsubstitutes
;
3362 if (nsubstitutes
% min_n_opers
!= 0
3363 && min_n_opers
% nsubstitutes
!= 0)
3364 fatal_at (token
, "All user-defined identifiers must have a "
3365 "multiple number of operator substitutions of the "
3366 "smallest number of substitutions");
3367 if (nsubstitutes
< min_n_opers
)
3368 min_n_opers
= nsubstitutes
;
3369 else if (nsubstitutes
> max_n_opers
)
3370 max_n_opers
= nsubstitutes
;
3374 unsigned n_ids
= user_ids
.length ();
3376 fatal_at (token
, "for requires at least one user-defined identifier");
3379 if (token
->type
== CPP_CLOSE_PAREN
)
3380 fatal_at (token
, "no pattern defined in for");
3382 active_fors
.safe_push (user_ids
);
3386 if (token
->type
== CPP_CLOSE_PAREN
)
3392 /* Remove user-defined operators from the hash again. */
3393 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3395 if (!user_ids
[i
]->used
)
3396 warning_at (user_id_tokens
[i
],
3397 "operator %s defined but not used", user_ids
[i
]->id
);
3398 operators
->remove_elt (user_ids
[i
]);
3402 /* Parse an identifier associated with a list of operators.
3403 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3406 parser::parse_operator_list (source_location
)
3408 const cpp_token
*token
= peek ();
3409 const char *id
= get_ident ();
3411 if (get_operator (id
) != 0)
3412 fatal_at (token
, "operator %s already defined", id
);
3414 user_id
*op
= new user_id (id
, true);
3417 while ((token
= peek_ident ()) != 0)
3420 const char *oper
= get_ident ();
3421 id_base
*idb
= get_operator (oper
);
3424 fatal_at (token
, "no such operator '%s'", oper
);
3428 else if (idb
->nargs
== -1)
3430 else if (arity
!= idb
->nargs
)
3431 fatal_at (token
, "operator '%s' with arity %d does not match "
3432 "others with arity %d", oper
, idb
->nargs
, arity
);
3434 /* We allow composition of multiple operator lists. */
3435 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3436 op
->substitutes
.safe_splice (p
->substitutes
);
3438 op
->substitutes
.safe_push (idb
);
3441 // Check that there is no junk after id-list
3443 if (token
->type
!= CPP_CLOSE_PAREN
)
3444 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
3446 if (op
->substitutes
.length () == 0)
3447 fatal_at (token
, "operator-list cannot be empty");
3450 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3454 /* Parse an outer if expression.
3455 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3458 parser::parse_if (source_location loc
)
3460 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3462 const cpp_token
*token
= peek ();
3463 if (token
->type
== CPP_CLOSE_PAREN
)
3464 fatal_at (token
, "no pattern defined in if");
3466 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3469 const cpp_token
*token
= peek ();
3470 if (token
->type
== CPP_CLOSE_PAREN
)
3478 /* Parse a list of predefined predicate identifiers.
3479 preds = '(' 'define_predicates' <ident>... ')' */
3482 parser::parse_predicates (source_location
)
3486 const cpp_token
*token
= peek ();
3487 if (token
->type
!= CPP_NAME
)
3490 add_predicate (get_ident ());
3495 /* Parse outer control structures.
3496 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3499 parser::parse_pattern ()
3501 /* All clauses start with '('. */
3502 eat_token (CPP_OPEN_PAREN
);
3503 const cpp_token
*token
= peek ();
3504 const char *id
= get_ident ();
3505 if (strcmp (id
, "simplify") == 0)
3507 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3510 else if (strcmp (id
, "match") == 0)
3512 bool with_args
= false;
3513 if (peek ()->type
== CPP_OPEN_PAREN
)
3515 eat_token (CPP_OPEN_PAREN
);
3518 const char *name
= get_ident ();
3519 id_base
*id
= get_operator (name
);
3523 p
= add_predicate (name
);
3524 user_predicates
.safe_push (p
);
3526 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3529 fatal_at (token
, "cannot add a match to a non-predicate ID");
3530 /* Parse (match <id> <arg>... (match-expr)) here. */
3534 capture_ids
= new cid_map_t
;
3536 while (peek ()->type
== CPP_ATSIGN
)
3537 e
->append_op (parse_capture (NULL
));
3538 eat_token (CPP_CLOSE_PAREN
);
3541 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3542 || (!e
&& p
->nargs
!= 0)))
3543 fatal_at (token
, "non-matching number of match operands");
3544 p
->nargs
= e
? e
->ops
.length () : 0;
3545 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3548 else if (strcmp (id
, "for") == 0)
3549 parse_for (token
->src_loc
);
3550 else if (strcmp (id
, "if") == 0)
3551 parse_if (token
->src_loc
);
3552 else if (strcmp (id
, "define_predicates") == 0)
3554 if (active_ifs
.length () > 0
3555 || active_fors
.length () > 0)
3556 fatal_at (token
, "define_predicates inside if or for is not supported");
3557 parse_predicates (token
->src_loc
);
3559 else if (strcmp (id
, "define_operator_list") == 0)
3561 if (active_ifs
.length () > 0
3562 || active_fors
.length () > 0)
3563 fatal_at (token
, "operator-list inside if or for is not supported");
3564 parse_operator_list (token
->src_loc
);
3567 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3568 active_ifs
.length () == 0 && active_fors
.length () == 0
3569 ? "'define_predicates', " : "");
3571 eat_token (CPP_CLOSE_PAREN
);
3574 /* Main entry of the parser. Repeatedly parse outer control structures. */
3576 parser::parser (cpp_reader
*r_
)
3580 active_fors
= vNULL
;
3581 simplifiers
= vNULL
;
3582 oper_lists_set
= NULL
;
3585 user_predicates
= vNULL
;
3586 parsing_match_operand
= false;
3588 const cpp_token
*token
= next ();
3589 while (token
->type
!= CPP_EOF
)
3591 _cpp_backup_tokens (r
, 1);
3598 /* Helper for the linemap code. */
3601 round_alloc_size (size_t s
)
3607 /* The genmatch generator progam. It reads from a pattern description
3608 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3611 main (int argc
, char **argv
)
3615 progname
= "genmatch";
3621 bool verbose
= false;
3622 char *input
= argv
[argc
-1];
3623 for (int i
= 1; i
< argc
- 1; ++i
)
3625 if (strcmp (argv
[i
], "--gimple") == 0)
3627 else if (strcmp (argv
[i
], "--generic") == 0)
3629 else if (strcmp (argv
[i
], "-v") == 0)
3633 fprintf (stderr
, "Usage: genmatch "
3634 "[--gimple] [--generic] [-v] input\n");
3639 line_table
= XCNEW (struct line_maps
);
3640 linemap_init (line_table
, 0);
3641 line_table
->reallocator
= xrealloc
;
3642 line_table
->round_alloc_size
= round_alloc_size
;
3644 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3645 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3646 cb
->error
= error_cb
;
3648 if (!cpp_read_main_file (r
, input
))
3650 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3651 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3653 /* Pre-seed operators. */
3654 operators
= new hash_table
<id_base
> (1024);
3655 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3656 add_operator (SYM, # SYM, # TYPE, NARGS);
3657 #define END_OF_BASE_TREE_CODES
3659 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3660 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3661 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3662 #undef END_OF_BASE_TREE_CODES
3665 /* Pre-seed builtin functions.
3666 ??? Cannot use N (name) as that is targetm.emultls.get_address
3667 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3668 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3669 add_builtin (ENUM, # ENUM);
3670 #include "builtins.def"
3677 write_header (stdout
, "gimple-match-head.c");
3679 write_header (stdout
, "generic-match-head.c");
3681 /* Go over all predicates defined with patterns and perform
3682 lowering and code generation. */
3683 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3685 predicate_id
*pred
= p
.user_predicates
[i
];
3686 lower (pred
->matchers
, gimple
);
3689 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3690 print_matches (pred
->matchers
[i
]);
3693 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3694 dt
.insert (pred
->matchers
[i
], i
);
3699 write_predicate (stdout
, pred
, dt
, gimple
);
3702 /* Lower the main simplifiers and generate code for them. */
3703 lower (p
.simplifiers
, gimple
);
3706 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3707 print_matches (p
.simplifiers
[i
]);
3710 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3711 dt
.insert (p
.simplifiers
[i
], i
);
3717 dt
.gen_gimple (stdout
);
3719 dt
.gen_generic (stdout
);
3722 cpp_finish (r
, NULL
);