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_
, const char *name_
= 0)
512 : operand (OP_CAPTURE
), where (where_
), what (what_
), name (name_
) {}
513 /* Identifier index for the value. */
515 /* The captured value. */
517 /* The original capture name */
520 virtual void gen_transform (FILE *f
, const char *, bool, int,
521 const char *, capture_info
*,
522 dt_operand
** = 0, bool = true);
528 is_a_helper
<capture
*>::test (operand
*op
)
530 return op
->type
== operand::OP_CAPTURE
;
536 is_a_helper
<predicate
*>::test (operand
*op
)
538 return op
->type
== operand::OP_PREDICATE
;
544 is_a_helper
<c_expr
*>::test (operand
*op
)
546 return op
->type
== operand::OP_C_EXPR
;
552 is_a_helper
<expr
*>::test (operand
*op
)
554 return op
->type
== operand::OP_EXPR
;
557 /* Helper to distinguish 'if' from 'with' expressions. */
561 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
562 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
563 source_location location
;
568 /* The main class of a pattern and its transform. This is used to
569 represent both (simplify ...) and (match ...) kinds. The AST
570 duplicates all outer 'if' and 'for' expressions here so each
571 simplify can exist in isolation. */
575 simplify (operand
*match_
, source_location match_location_
,
576 struct operand
*result_
, source_location result_location_
,
577 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
578 cid_map_t
*capture_ids_
)
579 : match (match_
), match_location (match_location_
),
580 result (result_
), result_location (result_location_
),
581 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
582 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
584 /* The expression that is matched against the GENERIC or GIMPLE IL. */
586 source_location match_location
;
587 /* For a (simplify ...) the expression produced when the pattern applies.
588 For a (match ...) either NULL if it is a simple predicate or the
589 single expression specifying the matched operands. */
590 struct operand
*result
;
591 source_location result_location
;
592 /* Collected 'if' expressions that need to evaluate to true to make
593 the pattern apply. */
594 vec
<if_or_with
> ifexpr_vec
;
595 /* Collected 'for' expression operators that have to be replaced
596 in the lowering phase. */
597 vec
<vec
<user_id
*> > for_vec
;
598 /* A map of capture identifiers to indexes. */
599 cid_map_t
*capture_ids
;
603 /* Debugging routines for dumping the AST. */
606 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
608 if (capture
*c
= dyn_cast
<capture
*> (o
))
610 fprintf (f
, "@%u", c
->where
);
612 fprintf (f
, "(%s)", c
->name
);
613 if (c
->what
&& flattened
== false)
616 print_operand (c
->what
, f
, flattened
);
621 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
622 fprintf (f
, "%s", p
->p
->id
);
624 else if (is_a
<c_expr
*> (o
))
625 fprintf (f
, "c_expr");
627 else if (expr
*e
= dyn_cast
<expr
*> (o
))
629 fprintf (f
, "(%s", e
->operation
->id
);
631 if (flattened
== false)
634 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
636 print_operand (e
->ops
[i
], f
, flattened
);
649 /* Lowering of commutative operators. */
652 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
653 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
655 if (n
== ops_vector
.length ())
657 vec
<operand
*> xv
= v
.copy ();
658 result
.safe_push (xv
);
662 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
664 v
[n
] = ops_vector
[n
][i
];
665 cartesian_product (ops_vector
, result
, v
, n
+ 1);
669 /* Lower OP to two operands in case it is marked as commutative. */
671 static vec
<operand
*>
672 commutate (operand
*op
)
674 vec
<operand
*> ret
= vNULL
;
676 if (capture
*c
= dyn_cast
<capture
*> (op
))
683 vec
<operand
*> v
= commutate (c
->what
);
684 for (unsigned i
= 0; i
< v
.length (); ++i
)
686 capture
*nc
= new capture (c
->where
, v
[i
]);
692 expr
*e
= dyn_cast
<expr
*> (op
);
693 if (!e
|| e
->ops
.length () == 0)
699 vec
< vec
<operand
*> > ops_vector
= vNULL
;
700 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
701 ops_vector
.safe_push (commutate (e
->ops
[i
]));
703 auto_vec
< vec
<operand
*> > result
;
704 auto_vec
<operand
*> v (e
->ops
.length ());
705 v
.quick_grow_cleared (e
->ops
.length ());
706 cartesian_product (ops_vector
, result
, v
, 0);
709 for (unsigned i
= 0; i
< result
.length (); ++i
)
711 expr
*ne
= new expr (e
->operation
);
712 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
713 ne
->append_op (result
[i
][j
]);
717 if (!e
->is_commutative
)
720 for (unsigned i
= 0; i
< result
.length (); ++i
)
722 expr
*ne
= new expr (e
->operation
);
723 // result[i].length () is 2 since e->operation is binary
724 for (unsigned j
= result
[i
].length (); j
; --j
)
725 ne
->append_op (result
[i
][j
-1]);
732 /* Lower operations marked as commutative in the AST of S and push
733 the resulting patterns to SIMPLIFIERS. */
736 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
738 vec
<operand
*> matchers
= commutate (s
->match
);
739 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
741 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
742 s
->result
, s
->result_location
, s
->ifexpr_vec
,
743 s
->for_vec
, s
->capture_ids
);
744 simplifiers
.safe_push (ns
);
748 /* Strip conditional conversios using operator OPER from O and its
749 children if STRIP, else replace them with an unconditional convert. */
752 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
754 if (capture
*c
= dyn_cast
<capture
*> (o
))
757 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
762 expr
*e
= dyn_cast
<expr
*> (o
);
766 if (*e
->operation
== oper
)
769 return lower_opt_convert (e
->ops
[0], oper
, strip
);
771 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
772 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
776 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
777 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
778 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
783 /* Determine whether O or its children uses the conditional conversion
787 has_opt_convert (operand
*o
, enum tree_code oper
)
789 if (capture
*c
= dyn_cast
<capture
*> (o
))
792 return has_opt_convert (c
->what
, oper
);
797 expr
*e
= dyn_cast
<expr
*> (o
);
801 if (*e
->operation
== oper
)
804 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
805 if (has_opt_convert (e
->ops
[i
], oper
))
811 /* Lower conditional convert operators in O, expanding it to a vector
814 static vec
<operand
*>
815 lower_opt_convert (operand
*o
)
817 vec
<operand
*> v1
= vNULL
, v2
;
821 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
823 /* Conditional converts are lowered to a pattern with the
824 conversion and one without. The three different conditional
825 convert codes are lowered separately. */
827 for (unsigned i
= 0; i
< 3; ++i
)
830 for (unsigned j
= 0; j
< v1
.length (); ++j
)
831 if (has_opt_convert (v1
[j
], opers
[i
]))
833 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
834 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
840 for (unsigned j
= 0; j
< v2
.length (); ++j
)
841 v1
.safe_push (v2
[j
]);
848 /* Lower conditional convert operators in the AST of S and push
849 the resulting multiple patterns to SIMPLIFIERS. */
852 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
854 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
855 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
857 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
858 s
->result
, s
->result_location
, s
->ifexpr_vec
,
859 s
->for_vec
, s
->capture_ids
);
860 simplifiers
.safe_push (ns
);
864 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
865 GENERIC and a GIMPLE variant. */
867 static vec
<operand
*>
868 lower_cond (operand
*o
)
870 vec
<operand
*> ro
= vNULL
;
872 if (capture
*c
= dyn_cast
<capture
*> (o
))
876 vec
<operand
*> lop
= vNULL
;
877 lop
= lower_cond (c
->what
);
879 for (unsigned i
= 0; i
< lop
.length (); ++i
)
880 ro
.safe_push (new capture (c
->where
, lop
[i
]));
885 expr
*e
= dyn_cast
<expr
*> (o
);
886 if (!e
|| e
->ops
.length () == 0)
892 vec
< vec
<operand
*> > ops_vector
= vNULL
;
893 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
894 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
896 auto_vec
< vec
<operand
*> > result
;
897 auto_vec
<operand
*> v (e
->ops
.length ());
898 v
.quick_grow_cleared (e
->ops
.length ());
899 cartesian_product (ops_vector
, result
, v
, 0);
901 for (unsigned i
= 0; i
< result
.length (); ++i
)
903 expr
*ne
= new expr (e
->operation
);
904 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
905 ne
->append_op (result
[i
][j
]);
907 /* If this is a COND with a captured expression or an
908 expression with two operands then also match a GENERIC
909 form on the compare. */
910 if ((*e
->operation
== COND_EXPR
911 || *e
->operation
== VEC_COND_EXPR
)
912 && ((is_a
<capture
*> (e
->ops
[0])
913 && as_a
<capture
*> (e
->ops
[0])->what
914 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
916 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
917 || (is_a
<expr
*> (e
->ops
[0])
918 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
920 expr
*ne
= new expr (e
->operation
);
921 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
922 ne
->append_op (result
[i
][j
]);
923 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
925 expr
*ocmp
= as_a
<expr
*> (c
->what
);
926 expr
*cmp
= new expr (ocmp
->operation
);
927 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
928 cmp
->append_op (ocmp
->ops
[j
]);
929 cmp
->is_generic
= true;
930 ne
->ops
[0] = new capture (c
->where
, cmp
);
934 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
935 expr
*cmp
= new expr (ocmp
->operation
);
936 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
937 cmp
->append_op (ocmp
->ops
[j
]);
938 cmp
->is_generic
= true;
948 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
949 GENERIC and a GIMPLE variant. */
952 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
954 vec
<operand
*> matchers
= lower_cond (s
->match
);
955 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
957 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
958 s
->result
, s
->result_location
, s
->ifexpr_vec
,
959 s
->for_vec
, s
->capture_ids
);
960 simplifiers
.safe_push (ns
);
964 /* In AST operand O replace operator ID with operator WITH. */
967 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
969 /* Deep-copy captures and expressions, replacing operations as
971 if (capture
*c
= dyn_cast
<capture
*> (o
))
975 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
977 else if (expr
*e
= dyn_cast
<expr
*> (o
))
979 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
981 ne
->expr_type
= e
->expr_type
;
982 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
983 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
987 /* For c_expr we simply record a string replacement table which is
988 applied at code-generation time. */
989 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
991 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
992 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
993 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
999 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1002 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1004 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1005 unsigned worklist_start
= 0;
1006 auto_vec
<simplify
*> worklist
;
1007 worklist
.safe_push (sin
);
1009 /* Lower each recorded for separately, operating on the
1010 set of simplifiers created by the previous one.
1011 Lower inner-to-outer so inner for substitutes can refer
1012 to operators replaced by outer fors. */
1013 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1015 vec
<user_id
*>& ids
= for_vec
[fi
];
1016 unsigned n_ids
= ids
.length ();
1017 unsigned max_n_opers
= 0;
1018 for (unsigned i
= 0; i
< n_ids
; ++i
)
1019 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1020 max_n_opers
= ids
[i
]->substitutes
.length ();
1022 unsigned worklist_end
= worklist
.length ();
1023 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1025 simplify
*s
= worklist
[si
];
1026 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1028 operand
*match_op
= s
->match
;
1029 operand
*result_op
= s
->result
;
1030 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1032 for (unsigned i
= 0; i
< n_ids
; ++i
)
1034 user_id
*id
= ids
[i
];
1035 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1036 match_op
= replace_id (match_op
, id
, oper
);
1038 result_op
= replace_id (result_op
, id
, oper
);
1039 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1040 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1043 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1044 result_op
, s
->result_location
,
1045 ifexpr_vec
, vNULL
, s
->capture_ids
);
1046 worklist
.safe_push (ns
);
1049 worklist_start
= worklist_end
;
1052 /* Copy out the result from the last for lowering. */
1053 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1054 simplifiers
.safe_push (worklist
[i
]);
1057 /* Lower the AST for everything in SIMPLIFIERS. */
1060 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1062 auto_vec
<simplify
*> out_simplifiers
;
1063 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1064 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1066 simplifiers
.truncate (0);
1067 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1068 lower_commutative (out_simplifiers
[i
], simplifiers
);
1070 out_simplifiers
.truncate (0);
1072 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1073 lower_cond (simplifiers
[i
], out_simplifiers
);
1075 out_simplifiers
.safe_splice (simplifiers
);
1078 simplifiers
.truncate (0);
1079 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1080 lower_for (out_simplifiers
[i
], simplifiers
);
1086 /* The decision tree built for generating GIMPLE and GENERIC pattern
1087 matching code. It represents the 'match' expression of all
1088 simplifies and has those as its leafs. */
1090 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1094 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1098 vec
<dt_node
*> kids
;
1100 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1102 dt_node
*append_node (dt_node
*);
1103 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1104 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1105 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1106 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1108 virtual void gen (FILE *, bool) {}
1110 void gen_kids (FILE *, bool);
1111 void gen_kids_1 (FILE *, bool,
1112 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1113 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1116 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1118 struct dt_operand
: public dt_node
1121 dt_operand
*match_dop
;
1125 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1126 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1127 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1128 parent (parent_
), pos (pos_
) {}
1130 void gen (FILE *, bool);
1131 unsigned gen_predicate (FILE *, const char *, bool);
1132 unsigned gen_match_op (FILE *, const char *);
1134 unsigned gen_gimple_expr (FILE *);
1135 unsigned gen_generic_expr (FILE *, const char *);
1137 char *get_name (char *);
1138 void gen_opname (char *, unsigned);
1141 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1143 struct dt_simplify
: public dt_node
1146 unsigned pattern_no
;
1147 dt_operand
**indexes
;
1149 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1150 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1151 indexes (indexes_
) {}
1153 void gen (FILE *f
, bool);
1159 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1161 return (n
->type
== dt_node::DT_OPERAND
1162 || n
->type
== dt_node::DT_MATCH
);
1165 /* A container for the actual decision tree. */
1167 struct decision_tree
1171 void insert (struct simplify
*, unsigned);
1172 void gen_gimple (FILE *f
= stderr
);
1173 void gen_generic (FILE *f
= stderr
);
1174 void print (FILE *f
= stderr
);
1176 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1178 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1179 unsigned pos
= 0, dt_node
*parent
= 0);
1180 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1181 static bool cmp_node (dt_node
*, dt_node
*);
1182 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1185 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1188 cmp_operand (operand
*o1
, operand
*o2
)
1190 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1193 if (o1
->type
== operand::OP_PREDICATE
)
1195 predicate
*p1
= as_a
<predicate
*>(o1
);
1196 predicate
*p2
= as_a
<predicate
*>(o2
);
1197 return p1
->p
== p2
->p
;
1199 else if (o1
->type
== operand::OP_EXPR
)
1201 expr
*e1
= static_cast<expr
*>(o1
);
1202 expr
*e2
= static_cast<expr
*>(o2
);
1203 return (e1
->operation
== e2
->operation
1204 && e1
->is_generic
== e2
->is_generic
);
1210 /* Compare two decision tree nodes N1 and N2 and return true if they
1214 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1216 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1222 if (n1
->type
== dt_node::DT_TRUE
)
1225 if (n1
->type
== dt_node::DT_OPERAND
)
1226 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1227 (as_a
<dt_operand
*> (n2
))->op
);
1228 else if (n1
->type
== dt_node::DT_MATCH
)
1229 return ((as_a
<dt_operand
*> (n1
))->match_dop
1230 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1234 /* Search OPS for a decision tree node like P and return it if found. */
1237 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1239 /* We can merge adjacent DT_TRUE. */
1240 if (p
->type
== dt_node::DT_TRUE
1242 && ops
.last ()->type
== dt_node::DT_TRUE
)
1244 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1246 /* But we can't merge across DT_TRUE nodes as they serve as
1247 pattern order barriers to make sure that patterns apply
1248 in order of appearance in case multiple matches are possible. */
1249 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1251 if (decision_tree::cmp_node (ops
[i
], p
))
1257 /* Append N to the decision tree if it there is not already an existing
1261 dt_node::append_node (dt_node
*n
)
1265 kid
= decision_tree::find_node (kids
, n
);
1270 n
->level
= this->level
+ 1;
1275 /* Append OP to the decision tree. */
1278 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1280 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1281 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1282 return append_node (n
);
1285 /* Append a DT_TRUE decision tree node. */
1288 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1290 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1291 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1292 return append_node (n
);
1295 /* Append a DT_MATCH decision tree node. */
1298 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1300 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1301 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1302 return append_node (n
);
1305 /* Append S to the decision tree. */
1308 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1309 dt_operand
**indexes
)
1311 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1312 return append_node (n
);
1315 /* Insert O into the decision tree and return the decision tree node found
1319 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1320 unsigned pos
, dt_node
*parent
)
1322 dt_node
*q
, *elm
= 0;
1324 if (capture
*c
= dyn_cast
<capture
*> (o
))
1326 unsigned capt_index
= c
->where
;
1328 if (indexes
[capt_index
] == 0)
1331 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1334 q
= elm
= p
->append_true_op (parent
, pos
);
1337 // get to the last capture
1338 for (operand
*what
= c
->what
;
1339 what
&& is_a
<capture
*> (what
);
1340 c
= as_a
<capture
*> (what
), what
= c
->what
)
1345 unsigned cc_index
= c
->where
;
1346 dt_operand
*match_op
= indexes
[cc_index
];
1348 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1349 elm
= decision_tree::find_node (p
->kids
, &temp
);
1353 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1354 elm
= decision_tree::find_node (p
->kids
, &temp
);
1359 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1360 elm
= decision_tree::find_node (p
->kids
, &temp
);
1364 gcc_assert (elm
->type
== dt_node::DT_TRUE
1365 || elm
->type
== dt_node::DT_OPERAND
1366 || elm
->type
== dt_node::DT_MATCH
);
1367 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1372 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1374 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1379 p
= p
->append_op (o
, parent
, pos
);
1382 if (expr
*e
= dyn_cast
<expr
*>(o
))
1384 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1385 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1391 /* Insert S into the decision tree. */
1394 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1396 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1397 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1398 p
->append_simplify (s
, pattern_no
, indexes
);
1401 /* Debug functions to dump the decision tree. */
1404 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1406 if (p
->type
== dt_node::DT_NODE
)
1407 fprintf (f
, "root");
1411 for (unsigned i
= 0; i
< indent
; i
++)
1414 if (p
->type
== dt_node::DT_OPERAND
)
1416 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1417 print_operand (dop
->op
, f
, true);
1419 else if (p
->type
== dt_node::DT_TRUE
)
1420 fprintf (f
, "true");
1421 else if (p
->type
== dt_node::DT_MATCH
)
1422 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1423 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1425 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1426 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1427 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1428 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1433 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1435 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1436 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1440 decision_tree::print (FILE *f
)
1442 return decision_tree::print_node (root
, f
);
1446 /* For GENERIC we have to take care of wrapping multiple-used
1447 expressions with side-effects in save_expr and preserve side-effects
1448 of expressions with omit_one_operand. Analyze captures in
1449 match, result and with expressions and perform early-outs
1450 on the outermost match expression operands for cases we cannot
1455 capture_info (simplify
*s
);
1456 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1457 void walk_result (operand
*o
, bool);
1458 void walk_c_expr (c_expr
*);
1464 bool force_no_side_effects_p
;
1465 bool cond_expr_cond_p
;
1466 unsigned long toplevel_msk
;
1467 int result_use_count
;
1470 auto_vec
<cinfo
> info
;
1471 unsigned long force_no_side_effects
;
1474 /* Analyze captures in S. */
1476 capture_info::capture_info (simplify
*s
)
1480 || ((e
= dyn_cast
<expr
*> (s
->result
))
1481 && is_a
<predicate_id
*> (e
->operation
)))
1483 force_no_side_effects
= -1;
1487 force_no_side_effects
= 0;
1488 info
.safe_grow_cleared (s
->capture_max
+ 1);
1489 e
= as_a
<expr
*> (s
->match
);
1490 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1491 walk_match (e
->ops
[i
], i
,
1492 (i
!= 0 && *e
->operation
== COND_EXPR
)
1493 || *e
->operation
== TRUTH_ANDIF_EXPR
1494 || *e
->operation
== TRUTH_ORIF_EXPR
,
1496 && (*e
->operation
== COND_EXPR
1497 || *e
->operation
== VEC_COND_EXPR
));
1499 walk_result (s
->result
, false);
1501 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1502 if (s
->ifexpr_vec
[i
].is_with
)
1503 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1506 /* Analyze captures in the match expression piece O. */
1509 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1510 bool conditional_p
, bool cond_expr_cond_p
)
1512 if (capture
*c
= dyn_cast
<capture
*> (o
))
1514 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1515 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1516 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1517 /* Mark expr (non-leaf) captures and recurse. */
1519 && is_a
<expr
*> (c
->what
))
1521 info
[c
->where
].expr_p
= true;
1522 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1525 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1527 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1529 bool cond_p
= conditional_p
;
1530 bool cond_expr_cond_p
= false;
1531 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1533 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1534 || *e
->operation
== TRUTH_ORIF_EXPR
)
1537 && (*e
->operation
== COND_EXPR
1538 || *e
->operation
== VEC_COND_EXPR
))
1539 cond_expr_cond_p
= true;
1540 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1543 else if (is_a
<predicate
*> (o
))
1545 /* Mark non-captured leafs toplevel arg for checking. */
1546 force_no_side_effects
|= 1 << toplevel_arg
;
1552 /* Analyze captures in the result expression piece O. */
1555 capture_info::walk_result (operand
*o
, bool conditional_p
)
1557 if (capture
*c
= dyn_cast
<capture
*> (o
))
1559 info
[c
->where
].result_use_count
++;
1560 /* If we substitute an expression capture we don't know
1561 which captures this will end up using (well, we don't
1562 compute that). Force the uses to be side-effect free
1563 which means forcing the toplevels that reach the
1564 expression side-effect free. */
1565 if (info
[c
->where
].expr_p
)
1566 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1567 /* Mark CSE capture capture uses as forced to have
1570 && is_a
<expr
*> (c
->what
))
1572 info
[c
->where
].cse_p
= true;
1573 walk_result (c
->what
, true);
1576 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1578 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1580 bool cond_p
= conditional_p
;
1581 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1583 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1584 || *e
->operation
== TRUTH_ORIF_EXPR
)
1586 walk_result (e
->ops
[i
], cond_p
);
1589 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1595 /* Look for captures in the C expr E. */
1598 capture_info::walk_c_expr (c_expr
*e
)
1600 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1601 unsigned p_depth
= 0;
1602 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1604 const cpp_token
*t
= &e
->code
[i
];
1605 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1606 if (t
->type
== CPP_NAME
1607 && strcmp ((const char *)CPP_HASHNODE
1608 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1609 && n
->type
== CPP_OPEN_PAREN
)
1611 else if (t
->type
== CPP_CLOSE_PAREN
1614 else if (p_depth
== 0
1615 && t
->type
== CPP_ATSIGN
1616 && (n
->type
== CPP_NUMBER
1617 || n
->type
== CPP_NAME
)
1618 && !(n
->flags
& PREV_WHITE
))
1621 if (n
->type
== CPP_NUMBER
)
1622 id
= (const char *)n
->val
.str
.text
;
1624 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1625 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1631 /* Code generation off the decision tree and the refered AST nodes. */
1634 is_conversion (id_base
*op
)
1636 return (*op
== CONVERT_EXPR
1638 || *op
== FLOAT_EXPR
1639 || *op
== FIX_TRUNC_EXPR
1640 || *op
== VIEW_CONVERT_EXPR
);
1643 /* Get the type to be used for generating operands of OP from the
1647 get_operand_type (id_base
*op
, const char *in_type
,
1648 const char *expr_type
,
1649 const char *other_oprnd_type
)
1651 /* Generally operands whose type does not match the type of the
1652 expression generated need to know their types but match and
1653 thus can fall back to 'other_oprnd_type'. */
1654 if (is_conversion (op
))
1655 return other_oprnd_type
;
1656 else if (*op
== REALPART_EXPR
1657 || *op
== IMAGPART_EXPR
)
1658 return other_oprnd_type
;
1659 else if (is_a
<operator_id
*> (op
)
1660 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1661 return other_oprnd_type
;
1664 /* Otherwise all types should match - choose one in order of
1671 return other_oprnd_type
;
1675 /* Generate transform code for an expression. */
1678 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1679 const char *in_type
, capture_info
*cinfo
,
1680 dt_operand
**indexes
, bool)
1682 bool conversion_p
= is_conversion (operation
);
1683 const char *type
= expr_type
;
1686 /* If there was a type specification in the pattern use it. */
1688 else if (conversion_p
)
1689 /* For conversions we need to build the expression using the
1690 outer type passed in. */
1692 else if (*operation
== REALPART_EXPR
1693 || *operation
== IMAGPART_EXPR
)
1695 /* __real and __imag use the component type of its operand. */
1696 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1699 else if (is_a
<operator_id
*> (operation
)
1700 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1702 /* comparisons use boolean_type_node (or what gets in), but
1703 their operands need to figure out the types themselves. */
1704 sprintf (optype
, "boolean_type_node");
1709 /* Other operations are of the same type as their first operand. */
1710 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1714 fatal ("two conversions in a row");
1717 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1719 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1720 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1723 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1725 = get_operand_type (operation
, in_type
, expr_type
,
1726 i
== 0 ? NULL
: op0type
);
1727 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1728 ((!(*operation
== COND_EXPR
)
1729 && !(*operation
== VEC_COND_EXPR
))
1734 if (*operation
== CONVERT_EXPR
)
1737 opr
= operation
->id
;
1741 /* ??? Building a stmt can fail for various reasons here, seq being
1742 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
1743 So if we fail here we should continue matching other patterns. */
1744 fprintf (f
, " code_helper tem_code = %s;\n"
1745 " tree tem_ops[3] = { ", opr
);
1746 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1747 fprintf (f
, "ops%d[%u]%s", depth
, i
,
1748 i
== ops
.length () - 1 ? " };\n" : ", ");
1749 fprintf (f
, " gimple_resimplify%d (seq, &tem_code, %s, tem_ops, valueize);\n",
1750 ops
.length (), type
);
1751 fprintf (f
, " res = maybe_push_res_to_seq (tem_code, %s, tem_ops, seq);\n"
1752 " if (!res) return false;\n", type
);
1756 if (operation
->kind
== id_base::CODE
)
1757 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1758 ops
.length(), opr
, type
);
1760 fprintf (f
, " res = build_call_expr_loc (loc, "
1761 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1762 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1763 fprintf (f
, ", ops%d[%u]", depth
, i
);
1764 fprintf (f
, ");\n");
1766 fprintf (f
, "%s = res;\n", dest
);
1770 /* Generate code for a c_expr which is either the expression inside
1771 an if statement or a sequence of statements which computes a
1772 result to be stored to DEST. */
1775 c_expr::gen_transform (FILE *f
, const char *dest
,
1776 bool, int, const char *, capture_info
*,
1777 dt_operand
**, bool)
1779 if (dest
&& nr_stmts
== 1)
1780 fprintf (f
, "%s = ", dest
);
1782 unsigned stmt_nr
= 1;
1783 for (unsigned i
= 0; i
< code
.length (); ++i
)
1785 const cpp_token
*token
= &code
[i
];
1787 /* Replace captures for code-gen. */
1788 if (token
->type
== CPP_ATSIGN
)
1790 const cpp_token
*n
= &code
[i
+1];
1791 if ((n
->type
== CPP_NUMBER
1792 || n
->type
== CPP_NAME
)
1793 && !(n
->flags
& PREV_WHITE
))
1795 if (token
->flags
& PREV_WHITE
)
1798 if (n
->type
== CPP_NUMBER
)
1799 id
= (const char *)n
->val
.str
.text
;
1801 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1802 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1808 if (token
->flags
& PREV_WHITE
)
1811 if (token
->type
== CPP_NAME
)
1813 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1815 for (j
= 0; j
< ids
.length (); ++j
)
1817 if (strcmp (id
, ids
[j
].id
) == 0)
1819 fprintf (f
, "%s", ids
[j
].oper
);
1823 if (j
< ids
.length ())
1827 /* Output the token as string. */
1828 char *tk
= (char *)cpp_token_as_text (r
, token
);
1831 if (token
->type
== CPP_SEMICOLON
)
1834 if (dest
&& stmt_nr
== nr_stmts
)
1835 fprintf (f
, "\n %s = ", dest
);
1842 /* Generate transform code for a capture. */
1845 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1846 const char *in_type
, capture_info
*cinfo
,
1847 dt_operand
**indexes
, bool expand_compares
)
1849 if (what
&& is_a
<expr
*> (what
))
1851 if (indexes
[where
] == 0)
1854 sprintf (buf
, "captures[%u]", where
);
1855 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1859 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1861 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1862 with substituting a capture of that.
1863 ??? Returning false here will also not allow any other patterns
1865 if (gimple
&& expand_compares
1866 && cinfo
->info
[where
].cond_expr_cond_p
)
1867 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1869 " if (!seq) return false;\n"
1870 " %s = gimple_build (seq, TREE_CODE (%s),"
1871 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1872 " TREE_OPERAND (%s, 1));\n"
1873 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1876 /* Return the name of the operand representing the decision tree node.
1877 Use NAME as space to generate it. */
1880 dt_operand::get_name (char *name
)
1883 sprintf (name
, "t");
1884 else if (parent
->level
== 1)
1885 sprintf (name
, "op%u", pos
);
1886 else if (parent
->type
== dt_node::DT_MATCH
)
1887 return parent
->get_name (name
);
1889 sprintf (name
, "o%u%u", parent
->level
, pos
);
1893 /* Fill NAME with the operand name at position POS. */
1896 dt_operand::gen_opname (char *name
, unsigned pos
)
1899 sprintf (name
, "op%u", pos
);
1901 sprintf (name
, "o%u%u", level
, pos
);
1904 /* Generate matching code for the decision tree operand which is
1908 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1910 predicate
*p
= as_a
<predicate
*> (op
);
1912 if (p
->p
->matchers
.exists ())
1914 /* If this is a predicate generated from a pattern mangle its
1915 name and pass on the valueize hook. */
1917 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1919 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1922 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1927 /* Generate matching code for the decision tree operand which is
1931 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1933 char match_opname
[20];
1934 match_dop
->get_name (match_opname
);
1935 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1936 opname
, match_opname
, opname
, match_opname
);
1941 /* Generate GIMPLE matching code for the decision tree operand. */
1944 dt_operand::gen_gimple_expr (FILE *f
)
1946 expr
*e
= static_cast<expr
*> (op
);
1947 id_base
*id
= e
->operation
;
1948 unsigned n_ops
= e
->ops
.length ();
1950 for (unsigned i
= 0; i
< n_ops
; ++i
)
1952 char child_opname
[20];
1953 gen_opname (child_opname
, i
);
1955 if (id
->kind
== id_base::CODE
)
1958 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1959 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1961 /* ??? If this is a memory operation we can't (and should not)
1962 match this. The only sensible operand types are
1963 SSA names and invariants. */
1964 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1966 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1967 "|| is_gimple_min_invariant (%s))\n"
1968 "&& (%s = do_valueize (valueize, %s)))\n"
1969 "{\n", child_opname
, child_opname
, child_opname
,
1974 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1975 child_opname
, i
+ 1);
1978 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1980 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1981 child_opname
, child_opname
);
1988 /* Generate GENERIC matching code for the decision tree operand. */
1991 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1993 expr
*e
= static_cast<expr
*> (op
);
1994 unsigned n_ops
= e
->ops
.length ();
1996 for (unsigned i
= 0; i
< n_ops
; ++i
)
1998 char child_opname
[20];
1999 gen_opname (child_opname
, i
);
2001 if (e
->operation
->kind
== id_base::CODE
)
2002 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2003 child_opname
, opname
, i
);
2005 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2006 child_opname
, opname
, i
);
2012 /* Generate matching code for the children of the decision tree node. */
2015 dt_node::gen_kids (FILE *f
, bool gimple
)
2017 auto_vec
<dt_operand
*> gimple_exprs
;
2018 auto_vec
<dt_operand
*> generic_exprs
;
2019 auto_vec
<dt_operand
*> fns
;
2020 auto_vec
<dt_operand
*> generic_fns
;
2021 auto_vec
<dt_operand
*> preds
;
2022 auto_vec
<dt_node
*> others
;
2024 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2026 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2028 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2029 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2031 if (e
->ops
.length () == 0
2032 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2033 generic_exprs
.safe_push (op
);
2034 else if (e
->operation
->kind
== id_base::FN
)
2039 generic_fns
.safe_push (op
);
2041 else if (e
->operation
->kind
== id_base::PREDICATE
)
2042 preds
.safe_push (op
);
2046 gimple_exprs
.safe_push (op
);
2048 generic_exprs
.safe_push (op
);
2051 else if (op
->op
->type
== operand::OP_PREDICATE
)
2052 others
.safe_push (kids
[i
]);
2056 else if (kids
[i
]->type
== dt_node::DT_MATCH
2057 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2058 others
.safe_push (kids
[i
]);
2059 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2061 /* A DT_TRUE operand serves as a barrier - generate code now
2062 for what we have collected sofar. */
2063 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2064 fns
, generic_fns
, preds
, others
);
2065 /* And output the true operand itself. */
2066 kids
[i
]->gen (f
, gimple
);
2067 gimple_exprs
.truncate (0);
2068 generic_exprs
.truncate (0);
2070 generic_fns
.truncate (0);
2072 others
.truncate (0);
2078 /* Generate code for the remains. */
2079 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2080 fns
, generic_fns
, preds
, others
);
2083 /* Generate matching code for the children of the decision tree node. */
2086 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2087 vec
<dt_operand
*> gimple_exprs
,
2088 vec
<dt_operand
*> generic_exprs
,
2089 vec
<dt_operand
*> fns
,
2090 vec
<dt_operand
*> generic_fns
,
2091 vec
<dt_operand
*> preds
,
2092 vec
<dt_node
*> others
)
2095 char *kid_opname
= buf
;
2097 unsigned exprs_len
= gimple_exprs
.length ();
2098 unsigned gexprs_len
= generic_exprs
.length ();
2099 unsigned fns_len
= fns
.length ();
2100 unsigned gfns_len
= generic_fns
.length ();
2102 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2105 gimple_exprs
[0]->get_name (kid_opname
);
2107 fns
[0]->get_name (kid_opname
);
2109 generic_fns
[0]->get_name (kid_opname
);
2111 generic_exprs
[0]->get_name (kid_opname
);
2113 fprintf (f
, "switch (TREE_CODE (%s))\n"
2117 if (exprs_len
|| fns_len
)
2119 fprintf (f
, "case SSA_NAME:\n");
2120 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2122 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2126 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2127 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2129 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2131 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2132 id_base
*op
= e
->operation
;
2133 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2134 fprintf (f
, "CASE_CONVERT:\n");
2136 fprintf (f
, "case %s:\n", op
->id
);
2138 gimple_exprs
[i
]->gen (f
, true);
2139 fprintf (f
, "break;\n"
2142 fprintf (f
, "default:;\n"
2149 fprintf (f
, "else ");
2151 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2153 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2154 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2157 for (unsigned i
= 0; i
< fns_len
; ++i
)
2159 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2160 fprintf (f
, "case %s:\n"
2161 "{\n", e
->operation
->id
);
2162 fns
[i
]->gen (f
, true);
2163 fprintf (f
, "break;\n"
2167 fprintf (f
, "default:;\n"
2176 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2178 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2179 id_base
*op
= e
->operation
;
2180 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2181 fprintf (f
, "CASE_CONVERT:\n");
2183 fprintf (f
, "case %s:\n", op
->id
);
2185 generic_exprs
[i
]->gen (f
, gimple
);
2186 fprintf (f
, "break;\n"
2192 fprintf (f
, "case CALL_EXPR:\n"
2194 "tree fndecl = get_callee_fndecl (%s);\n"
2195 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2196 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2199 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2201 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2202 gcc_assert (e
->operation
->kind
== id_base::FN
);
2204 fprintf (f
, "case %s:\n"
2205 "{\n", e
->operation
->id
);
2206 generic_fns
[j
]->gen (f
, false);
2207 fprintf (f
, "break;\n"
2211 fprintf (f
, "default:;\n"
2217 /* Close switch (TREE_CODE ()). */
2218 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2219 fprintf (f
, "default:;\n"
2222 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2224 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2225 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2226 preds
[i
]->get_name (kid_opname
);
2227 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2228 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2229 gimple
? "gimple" : "tree",
2230 p
->id
, kid_opname
, kid_opname
,
2231 gimple
? ", valueize" : "");
2233 for (int j
= 0; j
< p
->nargs
; ++j
)
2235 char child_opname
[20];
2236 preds
[i
]->gen_opname (child_opname
, j
);
2237 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2239 preds
[i
]->gen_kids (f
, gimple
);
2243 for (unsigned i
= 0; i
< others
.length (); ++i
)
2244 others
[i
]->gen (f
, gimple
);
2247 /* Generate matching code for the decision tree operand. */
2250 dt_operand::gen (FILE *f
, bool gimple
)
2255 unsigned n_braces
= 0;
2257 if (type
== DT_OPERAND
)
2260 case operand::OP_PREDICATE
:
2261 n_braces
= gen_predicate (f
, opname
, gimple
);
2264 case operand::OP_EXPR
:
2266 n_braces
= gen_gimple_expr (f
);
2268 n_braces
= gen_generic_expr (f
, opname
);
2274 else if (type
== DT_TRUE
)
2276 else if (type
== DT_MATCH
)
2277 n_braces
= gen_match_op (f
, opname
);
2281 gen_kids (f
, gimple
);
2283 for (unsigned i
= 0; i
< n_braces
; ++i
)
2289 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2290 step of a '(simplify ...)' or '(match ...)'. This handles everything
2291 that is not part of the decision tree (simplify->match). */
2294 dt_simplify::gen (FILE *f
, bool gimple
)
2297 output_line_directive (f
, s
->result_location
);
2298 if (s
->capture_max
>= 0)
2299 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2300 s
->capture_max
+ 1);
2302 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2306 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2309 unsigned n_braces
= 0;
2310 if (s
->ifexpr_vec
!= vNULL
)
2312 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2314 if_or_with
&w
= s
->ifexpr_vec
[i
];
2318 output_line_directive (f
, w
.location
);
2319 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2324 output_line_directive (f
, w
.location
);
2325 fprintf (f
, "if (");
2326 if (i
== s
->ifexpr_vec
.length () - 1
2327 || s
->ifexpr_vec
[i
+1].is_with
)
2328 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2337 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2341 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2347 while (j
< s
->ifexpr_vec
.length ()
2348 && !s
->ifexpr_vec
[j
].is_with
);
2358 /* Analyze captures and perform early-outs on the incoming arguments
2359 that cover cases we cannot handle. */
2360 capture_info
cinfo (s
);
2364 && !((e
= dyn_cast
<expr
*> (s
->result
))
2365 && is_a
<predicate_id
*> (e
->operation
)))
2367 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2368 if (cinfo
.force_no_side_effects
& (1 << i
))
2369 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2370 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2371 if (cinfo
.info
[i
].cse_p
)
2373 else if (cinfo
.info
[i
].force_no_side_effects_p
2374 && (cinfo
.info
[i
].toplevel_msk
2375 & cinfo
.force_no_side_effects
) == 0)
2376 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2377 "return NULL_TREE;\n", i
);
2378 else if ((cinfo
.info
[i
].toplevel_msk
2379 & cinfo
.force_no_side_effects
) != 0)
2380 /* Mark capture as having no side-effects if we had to verify
2381 that via forced toplevel operand checks. */
2382 cinfo
.info
[i
].force_no_side_effects_p
= true;
2385 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2386 "fprintf (dump_file, \"Applying pattern ");
2387 output_line_directive (f
, s
->result_location
, true);
2388 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2390 operand
*result
= s
->result
;
2393 /* If there is no result then this is a predicate implementation. */
2394 fprintf (f
, "return true;\n");
2398 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2399 in outermost position). */
2400 if (result
->type
== operand::OP_EXPR
2401 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2402 result
= as_a
<expr
*> (result
)->ops
[0];
2403 if (result
->type
== operand::OP_EXPR
)
2405 expr
*e
= as_a
<expr
*> (result
);
2406 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2408 fprintf (f
, "*res_code = %s;\n",
2409 *e
->operation
== CONVERT_EXPR
2410 ? "NOP_EXPR" : e
->operation
->id
);
2411 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2414 snprintf (dest
, 32, " res_ops[%d]", j
);
2416 = get_operand_type (e
->operation
,
2417 "type", e
->expr_type
,
2419 ? NULL
: "TREE_TYPE (res_ops[0])");
2420 /* We need to expand GENERIC conditions we captured from
2422 bool expand_generic_cond_exprs_p
2424 /* But avoid doing that if the GENERIC condition is
2425 valid - which it is in the first operand of COND_EXPRs
2426 and VEC_COND_EXRPs. */
2427 && ((!(*e
->operation
== COND_EXPR
)
2428 && !(*e
->operation
== VEC_COND_EXPR
))
2430 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2431 indexes
, expand_generic_cond_exprs_p
);
2434 /* Re-fold the toplevel result. It's basically an embedded
2435 gimple_build w/o actually building the stmt. */
2437 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2438 "res_ops, valueize);\n", e
->ops
.length ());
2440 else if (result
->type
== operand::OP_CAPTURE
2441 || result
->type
== operand::OP_C_EXPR
)
2443 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2444 &cinfo
, indexes
, false);
2445 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2446 if (is_a
<capture
*> (result
)
2447 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2449 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2450 with substituting a capture of that. */
2451 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2453 " tree tem = res_ops[0];\n"
2454 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2455 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2461 fprintf (f
, "return true;\n");
2465 bool is_predicate
= false;
2466 if (result
->type
== operand::OP_EXPR
)
2468 expr
*e
= as_a
<expr
*> (result
);
2469 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2470 /* Search for captures used multiple times in the result expression
2471 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2473 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2475 if (!cinfo
.info
[i
].force_no_side_effects_p
2476 && cinfo
.info
[i
].result_use_count
> 1)
2477 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2478 " captures[%d] = save_expr (captures[%d]);\n",
2481 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2485 snprintf (dest
, 32, "res_ops[%d]", j
);
2488 fprintf (f
, " tree res_op%d;\n", j
);
2489 snprintf (dest
, 32, " res_op%d", j
);
2492 = get_operand_type (e
->operation
,
2493 "type", e
->expr_type
,
2495 ? NULL
: "TREE_TYPE (res_op0)");
2496 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2500 fprintf (f
, "return true;\n");
2503 fprintf (f
, " tree res;\n");
2504 /* Re-fold the toplevel result. Use non_lvalue to
2505 build NON_LVALUE_EXPRs so they get properly
2506 ignored when in GIMPLE form. */
2507 if (*e
->operation
== NON_LVALUE_EXPR
)
2508 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2511 if (e
->operation
->kind
== id_base::CODE
)
2512 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2514 *e
->operation
== CONVERT_EXPR
2515 ? "NOP_EXPR" : e
->operation
->id
);
2517 fprintf (f
, " res = build_call_expr_loc "
2518 "(loc, builtin_decl_implicit (%s), %d",
2519 e
->operation
->id
, e
->ops
.length());
2520 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2521 fprintf (f
, ", res_op%d", j
);
2522 fprintf (f
, ");\n");
2526 else if (result
->type
== operand::OP_CAPTURE
2527 || result
->type
== operand::OP_C_EXPR
)
2530 fprintf (f
, " tree res;\n");
2531 s
->result
->gen_transform (f
, " res", false, 1, "type",
2538 /* Search for captures not used in the result expression and dependent
2539 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2540 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2542 if (!cinfo
.info
[i
].force_no_side_effects_p
2543 && !cinfo
.info
[i
].expr_p
2544 && cinfo
.info
[i
].result_use_count
== 0)
2545 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2546 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2547 " fold_ignored_result (captures[%d]), res);\n",
2550 fprintf (f
, " return res;\n");
2554 for (unsigned i
= 0; i
< n_braces
; ++i
)
2560 /* Main entry to generate code for matching GIMPLE IL off the decision
2564 decision_tree::gen_gimple (FILE *f
)
2566 for (unsigned n
= 1; n
<= 3; ++n
)
2568 fprintf (f
, "\nstatic bool\n"
2569 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2570 " gimple_seq *seq, tree (*valueize)(tree),\n"
2571 " code_helper code, tree type");
2572 for (unsigned i
= 0; i
< n
; ++i
)
2573 fprintf (f
, ", tree op%d", i
);
2577 fprintf (f
, "switch (code.get_rep())\n"
2579 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2581 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2582 expr
*e
= static_cast<expr
*>(dop
->op
);
2583 if (e
->ops
.length () != n
)
2586 if (*e
->operation
== CONVERT_EXPR
2587 || *e
->operation
== NOP_EXPR
)
2588 fprintf (f
, "CASE_CONVERT:\n");
2590 fprintf (f
, "case %s%s:\n",
2591 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2594 dop
->gen_kids (f
, true);
2595 fprintf (f
, "break;\n");
2598 fprintf (f
, "default:;\n"
2601 fprintf (f
, "return false;\n");
2606 /* Main entry to generate code for matching GENERIC IL off the decision
2610 decision_tree::gen_generic (FILE *f
)
2612 for (unsigned n
= 1; n
<= 3; ++n
)
2614 fprintf (f
, "\ntree\n"
2615 "generic_simplify (location_t loc, enum tree_code code, "
2616 "tree type ATTRIBUTE_UNUSED");
2617 for (unsigned i
= 0; i
< n
; ++i
)
2618 fprintf (f
, ", tree op%d", i
);
2622 fprintf (f
, "switch (code)\n"
2624 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2626 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2627 expr
*e
= static_cast<expr
*>(dop
->op
);
2628 if (e
->ops
.length () != n
2629 /* Builtin simplifications are somewhat premature on
2630 GENERIC. The following drops patterns with outermost
2631 calls. It's easy to emit overloads for function code
2632 though if necessary. */
2633 || e
->operation
->kind
!= id_base::CODE
)
2636 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2637 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2638 fprintf (f
, "CASE_CONVERT:\n");
2640 fprintf (f
, "case %s:\n", e
->operation
->id
);
2642 dop
->gen_kids (f
, false);
2643 fprintf (f
, "break;\n"
2646 fprintf (f
, "default:;\n"
2649 fprintf (f
, "return NULL_TREE;\n");
2654 /* Output code to implement the predicate P from the decision tree DT. */
2657 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2659 fprintf (f
, "\nbool\n"
2660 "%s%s (tree t%s%s)\n"
2661 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2662 p
->nargs
> 0 ? ", tree *res_ops" : "",
2663 gimple
? ", tree (*valueize)(tree)" : "");
2664 /* Conveniently make 'type' available. */
2665 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2668 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2669 dt
.root
->gen_kids (f
, gimple
);
2671 fprintf (f
, "return false;\n"
2675 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2678 write_header (FILE *f
, const char *head
)
2680 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2681 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2683 /* Include the header instead of writing it awkwardly quoted here. */
2684 fprintf (f
, "\n#include \"%s\"\n", head
);
2694 parser (cpp_reader
*);
2697 const cpp_token
*next ();
2698 const cpp_token
*peek ();
2699 const cpp_token
*peek_ident (const char * = NULL
);
2700 const cpp_token
*expect (enum cpp_ttype
);
2701 void eat_token (enum cpp_ttype
);
2702 const char *get_string ();
2703 const char *get_ident ();
2704 void eat_ident (const char *);
2705 const char *get_number ();
2707 id_base
*parse_operation ();
2708 operand
*parse_capture (operand
*);
2709 operand
*parse_expr ();
2710 c_expr
*parse_c_expr (cpp_ttype
);
2711 operand
*parse_op ();
2713 void record_operlist (source_location
, user_id
*);
2715 void parse_pattern ();
2716 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2717 operand
*, source_location
);
2718 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
* = 0,
2720 void parse_for (source_location
);
2721 void parse_if (source_location
);
2722 void parse_predicates (source_location
);
2723 void parse_operator_list (source_location
);
2726 vec
<if_or_with
> active_ifs
;
2727 vec
<vec
<user_id
*> > active_fors
;
2728 hash_set
<user_id
*> *oper_lists_set
;
2729 vec
<user_id
*> oper_lists
;
2731 cid_map_t
*capture_ids
;
2734 vec
<simplify
*> simplifiers
;
2735 vec
<predicate_id
*> user_predicates
;
2736 bool parsing_match_operand
;
2739 /* Lexing helpers. */
2741 /* Read the next non-whitespace token from R. */
2746 const cpp_token
*token
;
2749 token
= cpp_get_token (r
);
2751 while (token
->type
== CPP_PADDING
2752 && token
->type
!= CPP_EOF
);
2756 /* Peek at the next non-whitespace token from R. */
2761 const cpp_token
*token
;
2765 token
= cpp_peek_token (r
, i
++);
2767 while (token
->type
== CPP_PADDING
2768 && token
->type
!= CPP_EOF
);
2769 /* If we peek at EOF this is a fatal error as it leaves the
2770 cpp_reader in unusable state. Assume we really wanted a
2771 token and thus this EOF is unexpected. */
2772 if (token
->type
== CPP_EOF
)
2773 fatal_at (token
, "unexpected end of file");
2777 /* Peek at the next identifier token (or return NULL if the next
2778 token is not an identifier or equal to ID if supplied). */
2781 parser::peek_ident (const char *id
)
2783 const cpp_token
*token
= peek ();
2784 if (token
->type
!= CPP_NAME
)
2790 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2791 if (strcmp (id
, t
) == 0)
2797 /* Read the next token from R and assert it is of type TK. */
2800 parser::expect (enum cpp_ttype tk
)
2802 const cpp_token
*token
= next ();
2803 if (token
->type
!= tk
)
2804 fatal_at (token
, "expected %s, got %s",
2805 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2810 /* Consume the next token from R and assert it is of type TK. */
2813 parser::eat_token (enum cpp_ttype tk
)
2818 /* Read the next token from R and assert it is of type CPP_STRING and
2819 return its value. */
2822 parser::get_string ()
2824 const cpp_token
*token
= expect (CPP_STRING
);
2825 return (const char *)token
->val
.str
.text
;
2828 /* Read the next token from R and assert it is of type CPP_NAME and
2829 return its value. */
2832 parser::get_ident ()
2834 const cpp_token
*token
= expect (CPP_NAME
);
2835 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2838 /* Eat an identifier token with value S from R. */
2841 parser::eat_ident (const char *s
)
2843 const cpp_token
*token
= peek ();
2844 const char *t
= get_ident ();
2845 if (strcmp (s
, t
) != 0)
2846 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2849 /* Read the next token from R and assert it is of type CPP_NUMBER and
2850 return its value. */
2853 parser::get_number ()
2855 const cpp_token
*token
= expect (CPP_NUMBER
);
2856 return (const char *)token
->val
.str
.text
;
2860 /* Record an operator-list use for transparent for handling. */
2863 parser::record_operlist (source_location loc
, user_id
*p
)
2865 if (!oper_lists_set
->add (p
))
2867 if (!oper_lists
.is_empty ()
2868 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2869 fatal_at (loc
, "User-defined operator list does not have the "
2870 "same number of entries as others used in the pattern");
2871 oper_lists
.safe_push (p
);
2875 /* Parse the operator ID, special-casing convert?, convert1? and
2879 parser::parse_operation ()
2881 const cpp_token
*id_tok
= peek ();
2882 const char *id
= get_ident ();
2883 const cpp_token
*token
= peek ();
2884 if (strcmp (id
, "convert0") == 0)
2885 fatal_at (id_tok
, "use 'convert?' here");
2886 if (token
->type
== CPP_QUERY
2887 && !(token
->flags
& PREV_WHITE
))
2889 if (strcmp (id
, "convert") == 0)
2891 else if (strcmp (id
, "convert1") == 0)
2893 else if (strcmp (id
, "convert2") == 0)
2896 fatal_at (id_tok
, "non-convert operator conditionalized");
2898 if (!parsing_match_operand
)
2899 fatal_at (id_tok
, "conditional convert can only be used in "
2900 "match expression");
2901 eat_token (CPP_QUERY
);
2903 else if (strcmp (id
, "convert1") == 0
2904 || strcmp (id
, "convert2") == 0)
2905 fatal_at (id_tok
, "expected '?' after conditional operator");
2906 id_base
*op
= get_operator (id
);
2908 fatal_at (id_tok
, "unknown operator %s", id
);
2910 user_id
*p
= dyn_cast
<user_id
*> (op
);
2911 if (p
&& p
->is_oper_list
)
2912 record_operlist (id_tok
->src_loc
, p
);
2917 capture = '@'<number> */
2920 parser::parse_capture (operand
*op
)
2922 eat_token (CPP_ATSIGN
);
2923 const cpp_token
*token
= peek ();
2924 const char *id
= NULL
;
2925 if (token
->type
== CPP_NUMBER
)
2927 else if (token
->type
== CPP_NAME
)
2930 fatal_at (token
, "expected number or identifier");
2931 unsigned next_id
= capture_ids
->elements ();
2933 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2936 return new capture (num
, op
, id
);
2939 /* Parse an expression
2940 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2943 parser::parse_expr ()
2945 expr
*e
= new expr (parse_operation ());
2946 const cpp_token
*token
= peek ();
2948 bool is_commutative
= false;
2949 const char *expr_type
= NULL
;
2951 if (token
->type
== CPP_COLON
2952 && !(token
->flags
& PREV_WHITE
))
2954 eat_token (CPP_COLON
);
2956 if (token
->type
== CPP_NAME
2957 && !(token
->flags
& PREV_WHITE
))
2959 const char *s
= get_ident ();
2960 if (s
[0] == 'c' && !s
[1])
2962 if (!parsing_match_operand
)
2964 "flag 'c' can only be used in match expression");
2965 is_commutative
= true;
2967 else if (s
[1] != '\0')
2969 if (parsing_match_operand
)
2970 fatal_at (token
, "type can only be used in result expression");
2974 fatal_at (token
, "flag %s not recognized", s
);
2979 fatal_at (token
, "expected flag or type specifying identifier");
2982 if (token
->type
== CPP_ATSIGN
2983 && !(token
->flags
& PREV_WHITE
))
2984 op
= parse_capture (e
);
2989 const cpp_token
*token
= peek ();
2990 if (token
->type
== CPP_CLOSE_PAREN
)
2992 if (e
->operation
->nargs
!= -1
2993 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2994 fatal_at (token
, "'%s' expects %u operands, not %u",
2995 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2998 if (e
->ops
.length () == 2)
2999 e
->is_commutative
= true;
3001 fatal_at (token
, "only binary operators or function with "
3002 "two arguments can be marked commutative");
3004 e
->expr_type
= expr_type
;
3007 e
->append_op (parse_op ());
3012 /* Lex native C code delimited by START recording the preprocessing tokens
3013 for later processing.
3014 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3017 parser::parse_c_expr (cpp_ttype start
)
3019 const cpp_token
*token
;
3022 vec
<cpp_token
> code
= vNULL
;
3023 unsigned nr_stmts
= 0;
3025 if (start
== CPP_OPEN_PAREN
)
3026 end
= CPP_CLOSE_PAREN
;
3027 else if (start
== CPP_OPEN_BRACE
)
3028 end
= CPP_CLOSE_BRACE
;
3036 /* Count brace pairs to find the end of the expr to match. */
3037 if (token
->type
== start
)
3039 else if (token
->type
== end
3043 /* This is a lame way of counting the number of statements. */
3044 if (token
->type
== CPP_SEMICOLON
)
3047 /* If this is possibly a user-defined identifier mark it used. */
3048 if (token
->type
== CPP_NAME
)
3050 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3051 (token
->val
.node
.node
)->ident
.str
);
3053 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3054 record_operlist (token
->src_loc
, p
);
3057 /* Record the token. */
3058 code
.safe_push (*token
);
3061 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3064 /* Parse an operand which is either an expression, a predicate or
3065 a standalone capture.
3066 op = predicate | expr | c_expr | capture */
3071 const cpp_token
*token
= peek ();
3072 struct operand
*op
= NULL
;
3073 if (token
->type
== CPP_OPEN_PAREN
)
3075 eat_token (CPP_OPEN_PAREN
);
3077 eat_token (CPP_CLOSE_PAREN
);
3079 else if (token
->type
== CPP_OPEN_BRACE
)
3081 op
= parse_c_expr (CPP_OPEN_BRACE
);
3085 /* Remaining ops are either empty or predicates */
3086 if (token
->type
== CPP_NAME
)
3088 const char *id
= get_ident ();
3089 id_base
*opr
= get_operator (id
);
3091 fatal_at (token
, "expected predicate name");
3092 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3094 if (code
->nargs
!= 0)
3095 fatal_at (token
, "using an operator with operands as predicate");
3096 /* Parse the zero-operand operator "predicates" as
3098 op
= new expr (opr
);
3100 else if (user_id
*code
= dyn_cast
<user_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 (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3109 op
= new predicate (p
);
3111 fatal_at (token
, "using an unsupported operator as predicate");
3112 if (!parsing_match_operand
)
3113 fatal_at (token
, "predicates are only allowed in match expression");
3115 if (token
->flags
& PREV_WHITE
)
3118 else if (token
->type
!= CPP_COLON
3119 && token
->type
!= CPP_ATSIGN
)
3120 fatal_at (token
, "expected expression or predicate");
3121 /* optionally followed by a capture and a predicate. */
3122 if (token
->type
== CPP_COLON
)
3123 fatal_at (token
, "not implemented: predicate on leaf operand");
3124 if (token
->type
== CPP_ATSIGN
)
3125 op
= parse_capture (op
);
3131 /* Create a new simplify from the current parsing state and MATCH,
3132 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3135 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3136 operand
*match
, source_location match_loc
,
3137 operand
*result
, source_location result_loc
)
3139 /* Build and push a temporary for for operator list uses in expressions. */
3140 if (!oper_lists
.is_empty ())
3141 active_fors
.safe_push (oper_lists
);
3143 simplifiers
.safe_push
3144 (new simplify (match
, match_loc
, result
, result_loc
,
3145 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3147 if (!oper_lists
.is_empty ())
3152 simplify = 'simplify' <expr> <result-op>
3154 match = 'match' <ident> <expr> [<result-op>]
3156 <result-op> = <op> | <if> | <with>
3157 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3158 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3159 and fill SIMPLIFIERS with the results. */
3162 parser::parse_simplify (source_location match_location
,
3163 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3166 /* Reset the capture map. */
3168 capture_ids
= new cid_map_t
;
3169 /* Reset oper_lists and set. */
3170 hash_set
<user_id
*> olist
;
3171 oper_lists_set
= &olist
;
3174 const cpp_token
*loc
= peek ();
3175 parsing_match_operand
= true;
3176 struct operand
*match
= parse_op ();
3177 parsing_match_operand
= false;
3178 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3179 fatal_at (loc
, "outermost expression cannot be captured");
3180 if (match
->type
== operand::OP_EXPR
3181 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3182 fatal_at (loc
, "outermost expression cannot be a predicate");
3184 const cpp_token
*token
= peek ();
3186 /* If this if is immediately closed then it is part of a predicate
3187 definition. Push it. */
3188 if (token
->type
== CPP_CLOSE_PAREN
)
3191 fatal_at (token
, "expected transform expression");
3192 push_simplify (simplifiers
, match
, match_location
,
3193 result
, token
->src_loc
);
3197 unsigned active_ifs_len
= active_ifs
.length ();
3200 if (token
->type
== CPP_OPEN_PAREN
)
3202 source_location paren_loc
= token
->src_loc
;
3203 eat_token (CPP_OPEN_PAREN
);
3204 if (peek_ident ("if"))
3207 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3208 token
->src_loc
, false));
3209 /* If this if is immediately closed then it contains a
3210 manual matcher or is part of a predicate definition.
3212 if (peek ()->type
== CPP_CLOSE_PAREN
)
3215 fatal_at (token
, "manual transform not implemented");
3216 push_simplify (simplifiers
, match
, match_location
,
3220 else if (peek_ident ("with"))
3223 /* Parse (with c-expr expr) as (if-with (true) expr). */
3224 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3226 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3230 operand
*op
= result
;
3233 push_simplify (simplifiers
, match
, match_location
,
3234 op
, token
->src_loc
);
3235 eat_token (CPP_CLOSE_PAREN
);
3236 /* A "default" result closes the enclosing scope. */
3237 if (active_ifs
.length () > active_ifs_len
)
3239 eat_token (CPP_CLOSE_PAREN
);
3246 else if (token
->type
== CPP_CLOSE_PAREN
)
3248 /* Close a scope if requested. */
3249 if (active_ifs
.length () > active_ifs_len
)
3251 eat_token (CPP_CLOSE_PAREN
);
3261 fatal_at (token
, "expected match operand expression");
3262 push_simplify (simplifiers
, match
, match_location
,
3263 matcher
? result
: parse_op (), token
->src_loc
);
3264 /* A "default" result closes the enclosing scope. */
3265 if (active_ifs
.length () > active_ifs_len
)
3267 eat_token (CPP_CLOSE_PAREN
);
3277 /* Parsing of the outer control structures. */
3279 /* Parse a for expression
3280 for = '(' 'for' <subst>... <pattern> ')'
3281 subst = <ident> '(' <ident>... ')' */
3284 parser::parse_for (source_location
)
3286 auto_vec
<const cpp_token
*> user_id_tokens
;
3287 vec
<user_id
*> user_ids
= vNULL
;
3288 const cpp_token
*token
;
3289 unsigned min_n_opers
= 0, max_n_opers
= 0;
3294 if (token
->type
!= CPP_NAME
)
3297 /* Insert the user defined operators into the operator hash. */
3298 const char *id
= get_ident ();
3299 if (get_operator (id
) != NULL
)
3300 fatal_at (token
, "operator already defined");
3301 user_id
*op
= new user_id (id
);
3302 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3304 user_ids
.safe_push (op
);
3305 user_id_tokens
.safe_push (token
);
3307 eat_token (CPP_OPEN_PAREN
);
3310 while ((token
= peek_ident ()) != 0)
3312 const char *oper
= get_ident ();
3313 id_base
*idb
= get_operator (oper
);
3315 fatal_at (token
, "no such operator '%s'", oper
);
3316 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
3317 fatal_at (token
, "conditional operators cannot be used inside for");
3321 else if (idb
->nargs
== -1)
3323 else if (idb
->nargs
!= arity
)
3324 fatal_at (token
, "operator '%s' with arity %d does not match "
3325 "others with arity %d", oper
, idb
->nargs
, arity
);
3327 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3328 if (p
&& p
->is_oper_list
)
3329 op
->substitutes
.safe_splice (p
->substitutes
);
3331 op
->substitutes
.safe_push (idb
);
3334 token
= expect (CPP_CLOSE_PAREN
);
3336 unsigned nsubstitutes
= op
->substitutes
.length ();
3337 if (nsubstitutes
== 0)
3338 fatal_at (token
, "A user-defined operator must have at least "
3339 "one substitution");
3340 if (max_n_opers
== 0)
3342 min_n_opers
= nsubstitutes
;
3343 max_n_opers
= nsubstitutes
;
3347 if (nsubstitutes
% min_n_opers
!= 0
3348 && min_n_opers
% nsubstitutes
!= 0)
3349 fatal_at (token
, "All user-defined identifiers must have a "
3350 "multiple number of operator substitutions of the "
3351 "smallest number of substitutions");
3352 if (nsubstitutes
< min_n_opers
)
3353 min_n_opers
= nsubstitutes
;
3354 else if (nsubstitutes
> max_n_opers
)
3355 max_n_opers
= nsubstitutes
;
3359 unsigned n_ids
= user_ids
.length ();
3361 fatal_at (token
, "for requires at least one user-defined identifier");
3364 if (token
->type
== CPP_CLOSE_PAREN
)
3365 fatal_at (token
, "no pattern defined in for");
3367 active_fors
.safe_push (user_ids
);
3371 if (token
->type
== CPP_CLOSE_PAREN
)
3377 /* Remove user-defined operators from the hash again. */
3378 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3380 if (!user_ids
[i
]->used
)
3381 warning_at (user_id_tokens
[i
],
3382 "operator %s defined but not used", user_ids
[i
]->id
);
3383 operators
->remove_elt (user_ids
[i
]);
3387 /* Parse an identifier associated with a list of operators.
3388 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3391 parser::parse_operator_list (source_location
)
3393 const cpp_token
*token
= peek ();
3394 const char *id
= get_ident ();
3396 if (get_operator (id
) != 0)
3397 fatal_at (token
, "operator %s already defined", id
);
3399 user_id
*op
= new user_id (id
, true);
3402 while ((token
= peek_ident ()) != 0)
3405 const char *oper
= get_ident ();
3406 id_base
*idb
= get_operator (oper
);
3409 fatal_at (token
, "no such operator '%s'", oper
);
3413 else if (idb
->nargs
== -1)
3415 else if (arity
!= idb
->nargs
)
3416 fatal_at (token
, "operator '%s' with arity %d does not match "
3417 "others with arity %d", oper
, idb
->nargs
, arity
);
3419 /* We allow composition of multiple operator lists. */
3420 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3421 op
->substitutes
.safe_splice (p
->substitutes
);
3423 op
->substitutes
.safe_push (idb
);
3426 if (op
->substitutes
.length () == 0)
3427 fatal_at (token
, "operator-list cannot be empty");
3430 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3434 /* Parse an outer if expression.
3435 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3438 parser::parse_if (source_location loc
)
3440 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3442 const cpp_token
*token
= peek ();
3443 if (token
->type
== CPP_CLOSE_PAREN
)
3444 fatal_at (token
, "no pattern defined in if");
3446 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3449 const cpp_token
*token
= peek ();
3450 if (token
->type
== CPP_CLOSE_PAREN
)
3458 /* Parse a list of predefined predicate identifiers.
3459 preds = '(' 'define_predicates' <ident>... ')' */
3462 parser::parse_predicates (source_location
)
3466 const cpp_token
*token
= peek ();
3467 if (token
->type
!= CPP_NAME
)
3470 add_predicate (get_ident ());
3475 /* Parse outer control structures.
3476 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3479 parser::parse_pattern ()
3481 /* All clauses start with '('. */
3482 eat_token (CPP_OPEN_PAREN
);
3483 const cpp_token
*token
= peek ();
3484 const char *id
= get_ident ();
3485 if (strcmp (id
, "simplify") == 0)
3487 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3490 else if (strcmp (id
, "match") == 0)
3492 bool with_args
= false;
3493 if (peek ()->type
== CPP_OPEN_PAREN
)
3495 eat_token (CPP_OPEN_PAREN
);
3498 const char *name
= get_ident ();
3499 id_base
*id
= get_operator (name
);
3503 p
= add_predicate (name
);
3504 user_predicates
.safe_push (p
);
3506 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3509 fatal_at (token
, "cannot add a match to a non-predicate ID");
3510 /* Parse (match <id> <arg>... (match-expr)) here. */
3514 capture_ids
= new cid_map_t
;
3516 while (peek ()->type
== CPP_ATSIGN
)
3517 e
->append_op (parse_capture (NULL
));
3518 eat_token (CPP_CLOSE_PAREN
);
3521 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3522 || (!e
&& p
->nargs
!= 0)))
3523 fatal_at (token
, "non-matching number of match operands");
3524 p
->nargs
= e
? e
->ops
.length () : 0;
3525 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3528 else if (strcmp (id
, "for") == 0)
3529 parse_for (token
->src_loc
);
3530 else if (strcmp (id
, "if") == 0)
3531 parse_if (token
->src_loc
);
3532 else if (strcmp (id
, "define_predicates") == 0)
3534 if (active_ifs
.length () > 0
3535 || active_fors
.length () > 0)
3536 fatal_at (token
, "define_predicates inside if or for is not supported");
3537 parse_predicates (token
->src_loc
);
3539 else if (strcmp (id
, "define_operator_list") == 0)
3541 if (active_ifs
.length () > 0
3542 || active_fors
.length () > 0)
3543 fatal_at (token
, "operator-list inside if or for is not supported");
3544 parse_operator_list (token
->src_loc
);
3547 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3548 active_ifs
.length () == 0 && active_fors
.length () == 0
3549 ? "'define_predicates', " : "");
3551 eat_token (CPP_CLOSE_PAREN
);
3554 /* Main entry of the parser. Repeatedly parse outer control structures. */
3556 parser::parser (cpp_reader
*r_
)
3560 active_fors
= vNULL
;
3561 simplifiers
= vNULL
;
3562 oper_lists_set
= NULL
;
3565 user_predicates
= vNULL
;
3566 parsing_match_operand
= false;
3568 const cpp_token
*token
= next ();
3569 while (token
->type
!= CPP_EOF
)
3571 _cpp_backup_tokens (r
, 1);
3578 /* Helper for the linemap code. */
3581 round_alloc_size (size_t s
)
3587 /* The genmatch generator progam. It reads from a pattern description
3588 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3591 main (int argc
, char **argv
)
3595 progname
= "genmatch";
3601 bool verbose
= false;
3602 char *input
= argv
[argc
-1];
3603 for (int i
= 1; i
< argc
- 1; ++i
)
3605 if (strcmp (argv
[i
], "--gimple") == 0)
3607 else if (strcmp (argv
[i
], "--generic") == 0)
3609 else if (strcmp (argv
[i
], "-v") == 0)
3613 fprintf (stderr
, "Usage: genmatch "
3614 "[--gimple] [--generic] [-v] input\n");
3619 line_table
= XCNEW (struct line_maps
);
3620 linemap_init (line_table
, 0);
3621 line_table
->reallocator
= xrealloc
;
3622 line_table
->round_alloc_size
= round_alloc_size
;
3624 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3625 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3626 cb
->error
= error_cb
;
3628 if (!cpp_read_main_file (r
, input
))
3630 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3631 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3633 /* Pre-seed operators. */
3634 operators
= new hash_table
<id_base
> (1024);
3635 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3636 add_operator (SYM, # SYM, # TYPE, NARGS);
3637 #define END_OF_BASE_TREE_CODES
3639 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3640 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3641 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3642 #undef END_OF_BASE_TREE_CODES
3645 /* Pre-seed builtin functions.
3646 ??? Cannot use N (name) as that is targetm.emultls.get_address
3647 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3648 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3649 add_builtin (ENUM, # ENUM);
3650 #include "builtins.def"
3657 write_header (stdout
, "gimple-match-head.c");
3659 write_header (stdout
, "generic-match-head.c");
3661 /* Go over all predicates defined with patterns and perform
3662 lowering and code generation. */
3663 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3665 predicate_id
*pred
= p
.user_predicates
[i
];
3666 lower (pred
->matchers
, gimple
);
3669 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3671 print_operand (pred
->matchers
[i
]->match
);
3672 putc ('\n', stderr
);
3675 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3676 dt
.insert (pred
->matchers
[i
], i
);
3681 write_predicate (stdout
, pred
, dt
, gimple
);
3684 /* Lower the main simplifiers and generate code for them. */
3685 lower (p
.simplifiers
, gimple
);
3688 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3690 print_operand (p
.simplifiers
[i
]->match
);
3691 putc ('\n', stderr
);
3695 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3696 dt
.insert (p
.simplifiers
[i
], i
);
3702 dt
.gen_gimple (stdout
);
3704 dt
.gen_generic (stdout
);
3707 cpp_finish (r
, NULL
);