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 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
982 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
986 /* For c_expr we simply record a string replacement table which is
987 applied at code-generation time. */
988 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
990 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
991 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
992 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
998 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1001 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1003 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1004 unsigned worklist_start
= 0;
1005 auto_vec
<simplify
*> worklist
;
1006 worklist
.safe_push (sin
);
1008 /* Lower each recorded for separately, operating on the
1009 set of simplifiers created by the previous one.
1010 Lower inner-to-outer so inner for substitutes can refer
1011 to operators replaced by outer fors. */
1012 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1014 vec
<user_id
*>& ids
= for_vec
[fi
];
1015 unsigned n_ids
= ids
.length ();
1016 unsigned max_n_opers
= 0;
1017 for (unsigned i
= 0; i
< n_ids
; ++i
)
1018 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1019 max_n_opers
= ids
[i
]->substitutes
.length ();
1021 unsigned worklist_end
= worklist
.length ();
1022 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1024 simplify
*s
= worklist
[si
];
1025 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1027 operand
*match_op
= s
->match
;
1028 operand
*result_op
= s
->result
;
1029 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
1031 for (unsigned i
= 0; i
< n_ids
; ++i
)
1033 user_id
*id
= ids
[i
];
1034 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1035 match_op
= replace_id (match_op
, id
, oper
);
1037 result_op
= replace_id (result_op
, id
, oper
);
1038 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
1039 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
1042 simplify
*ns
= new simplify (match_op
, s
->match_location
,
1043 result_op
, s
->result_location
,
1044 ifexpr_vec
, vNULL
, s
->capture_ids
);
1045 worklist
.safe_push (ns
);
1048 worklist_start
= worklist_end
;
1051 /* Copy out the result from the last for lowering. */
1052 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1053 simplifiers
.safe_push (worklist
[i
]);
1056 /* Lower the AST for everything in SIMPLIFIERS. */
1059 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1061 auto_vec
<simplify
*> out_simplifiers
;
1062 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1063 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1065 simplifiers
.truncate (0);
1066 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1067 lower_commutative (out_simplifiers
[i
], simplifiers
);
1069 out_simplifiers
.truncate (0);
1071 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1072 lower_cond (simplifiers
[i
], out_simplifiers
);
1074 out_simplifiers
.safe_splice (simplifiers
);
1077 simplifiers
.truncate (0);
1078 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1079 lower_for (out_simplifiers
[i
], simplifiers
);
1085 /* The decision tree built for generating GIMPLE and GENERIC pattern
1086 matching code. It represents the 'match' expression of all
1087 simplifies and has those as its leafs. */
1089 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1093 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1097 vec
<dt_node
*> kids
;
1099 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1101 dt_node
*append_node (dt_node
*);
1102 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1103 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1104 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1105 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1107 virtual void gen (FILE *, bool) {}
1109 void gen_kids (FILE *, bool);
1110 void gen_kids_1 (FILE *, bool,
1111 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1112 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1115 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1117 struct dt_operand
: public dt_node
1120 dt_operand
*match_dop
;
1124 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1125 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1126 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1127 parent (parent_
), pos (pos_
) {}
1129 void gen (FILE *, bool);
1130 unsigned gen_predicate (FILE *, const char *, bool);
1131 unsigned gen_match_op (FILE *, const char *);
1133 unsigned gen_gimple_expr (FILE *);
1134 unsigned gen_generic_expr (FILE *, const char *);
1136 char *get_name (char *);
1137 void gen_opname (char *, unsigned);
1140 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1142 struct dt_simplify
: public dt_node
1145 unsigned pattern_no
;
1146 dt_operand
**indexes
;
1148 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1149 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1150 indexes (indexes_
) {}
1152 void gen (FILE *f
, bool);
1158 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1160 return (n
->type
== dt_node::DT_OPERAND
1161 || n
->type
== dt_node::DT_MATCH
);
1164 /* A container for the actual decision tree. */
1166 struct decision_tree
1170 void insert (struct simplify
*, unsigned);
1171 void gen_gimple (FILE *f
= stderr
);
1172 void gen_generic (FILE *f
= stderr
);
1173 void print (FILE *f
= stderr
);
1175 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1177 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1178 unsigned pos
= 0, dt_node
*parent
= 0);
1179 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1180 static bool cmp_node (dt_node
*, dt_node
*);
1181 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1184 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1187 cmp_operand (operand
*o1
, operand
*o2
)
1189 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1192 if (o1
->type
== operand::OP_PREDICATE
)
1194 predicate
*p1
= as_a
<predicate
*>(o1
);
1195 predicate
*p2
= as_a
<predicate
*>(o2
);
1196 return p1
->p
== p2
->p
;
1198 else if (o1
->type
== operand::OP_EXPR
)
1200 expr
*e1
= static_cast<expr
*>(o1
);
1201 expr
*e2
= static_cast<expr
*>(o2
);
1202 return (e1
->operation
== e2
->operation
1203 && e1
->is_generic
== e2
->is_generic
);
1209 /* Compare two decision tree nodes N1 and N2 and return true if they
1213 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1215 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1221 if (n1
->type
== dt_node::DT_TRUE
)
1224 if (n1
->type
== dt_node::DT_OPERAND
)
1225 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1226 (as_a
<dt_operand
*> (n2
))->op
);
1227 else if (n1
->type
== dt_node::DT_MATCH
)
1228 return ((as_a
<dt_operand
*> (n1
))->match_dop
1229 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1233 /* Search OPS for a decision tree node like P and return it if found. */
1236 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1238 /* We can merge adjacent DT_TRUE. */
1239 if (p
->type
== dt_node::DT_TRUE
1241 && ops
.last ()->type
== dt_node::DT_TRUE
)
1243 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1245 /* But we can't merge across DT_TRUE nodes as they serve as
1246 pattern order barriers to make sure that patterns apply
1247 in order of appearance in case multiple matches are possible. */
1248 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1250 if (decision_tree::cmp_node (ops
[i
], p
))
1256 /* Append N to the decision tree if it there is not already an existing
1260 dt_node::append_node (dt_node
*n
)
1264 kid
= decision_tree::find_node (kids
, n
);
1269 n
->level
= this->level
+ 1;
1274 /* Append OP to the decision tree. */
1277 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1279 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1280 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1281 return append_node (n
);
1284 /* Append a DT_TRUE decision tree node. */
1287 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1289 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1290 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1291 return append_node (n
);
1294 /* Append a DT_MATCH decision tree node. */
1297 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1299 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1300 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1301 return append_node (n
);
1304 /* Append S to the decision tree. */
1307 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1308 dt_operand
**indexes
)
1310 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1311 return append_node (n
);
1314 /* Insert O into the decision tree and return the decision tree node found
1318 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1319 unsigned pos
, dt_node
*parent
)
1321 dt_node
*q
, *elm
= 0;
1323 if (capture
*c
= dyn_cast
<capture
*> (o
))
1325 unsigned capt_index
= c
->where
;
1327 if (indexes
[capt_index
] == 0)
1330 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1333 q
= elm
= p
->append_true_op (parent
, pos
);
1336 // get to the last capture
1337 for (operand
*what
= c
->what
;
1338 what
&& is_a
<capture
*> (what
);
1339 c
= as_a
<capture
*> (what
), what
= c
->what
)
1344 unsigned cc_index
= c
->where
;
1345 dt_operand
*match_op
= indexes
[cc_index
];
1347 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1348 elm
= decision_tree::find_node (p
->kids
, &temp
);
1352 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1353 elm
= decision_tree::find_node (p
->kids
, &temp
);
1358 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1359 elm
= decision_tree::find_node (p
->kids
, &temp
);
1363 gcc_assert (elm
->type
== dt_node::DT_TRUE
1364 || elm
->type
== dt_node::DT_OPERAND
1365 || elm
->type
== dt_node::DT_MATCH
);
1366 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1371 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1373 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1378 p
= p
->append_op (o
, parent
, pos
);
1381 if (expr
*e
= dyn_cast
<expr
*>(o
))
1383 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1384 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1390 /* Insert S into the decision tree. */
1393 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1395 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1396 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1397 p
->append_simplify (s
, pattern_no
, indexes
);
1400 /* Debug functions to dump the decision tree. */
1403 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1405 if (p
->type
== dt_node::DT_NODE
)
1406 fprintf (f
, "root");
1410 for (unsigned i
= 0; i
< indent
; i
++)
1413 if (p
->type
== dt_node::DT_OPERAND
)
1415 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1416 print_operand (dop
->op
, f
, true);
1418 else if (p
->type
== dt_node::DT_TRUE
)
1419 fprintf (f
, "true");
1420 else if (p
->type
== dt_node::DT_MATCH
)
1421 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1422 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1424 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1425 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1426 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1427 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1432 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1434 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1435 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1439 decision_tree::print (FILE *f
)
1441 return decision_tree::print_node (root
, f
);
1445 /* For GENERIC we have to take care of wrapping multiple-used
1446 expressions with side-effects in save_expr and preserve side-effects
1447 of expressions with omit_one_operand. Analyze captures in
1448 match, result and with expressions and perform early-outs
1449 on the outermost match expression operands for cases we cannot
1454 capture_info (simplify
*s
);
1455 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1456 void walk_result (operand
*o
, bool);
1457 void walk_c_expr (c_expr
*);
1463 bool force_no_side_effects_p
;
1464 bool cond_expr_cond_p
;
1465 unsigned long toplevel_msk
;
1466 int result_use_count
;
1469 auto_vec
<cinfo
> info
;
1470 unsigned long force_no_side_effects
;
1473 /* Analyze captures in S. */
1475 capture_info::capture_info (simplify
*s
)
1479 || ((e
= dyn_cast
<expr
*> (s
->result
))
1480 && is_a
<predicate_id
*> (e
->operation
)))
1482 force_no_side_effects
= -1;
1486 force_no_side_effects
= 0;
1487 info
.safe_grow_cleared (s
->capture_max
+ 1);
1488 e
= as_a
<expr
*> (s
->match
);
1489 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1490 walk_match (e
->ops
[i
], i
,
1491 (i
!= 0 && *e
->operation
== COND_EXPR
)
1492 || *e
->operation
== TRUTH_ANDIF_EXPR
1493 || *e
->operation
== TRUTH_ORIF_EXPR
,
1495 && (*e
->operation
== COND_EXPR
1496 || *e
->operation
== VEC_COND_EXPR
));
1498 walk_result (s
->result
, false);
1500 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1501 if (s
->ifexpr_vec
[i
].is_with
)
1502 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1505 /* Analyze captures in the match expression piece O. */
1508 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1509 bool conditional_p
, bool cond_expr_cond_p
)
1511 if (capture
*c
= dyn_cast
<capture
*> (o
))
1513 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1514 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1515 info
[c
->where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1516 /* Mark expr (non-leaf) captures and recurse. */
1518 && is_a
<expr
*> (c
->what
))
1520 info
[c
->where
].expr_p
= true;
1521 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1524 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1526 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1528 bool cond_p
= conditional_p
;
1529 bool cond_expr_cond_p
= false;
1530 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1532 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1533 || *e
->operation
== TRUTH_ORIF_EXPR
)
1536 && (*e
->operation
== COND_EXPR
1537 || *e
->operation
== VEC_COND_EXPR
))
1538 cond_expr_cond_p
= true;
1539 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1542 else if (is_a
<predicate
*> (o
))
1544 /* Mark non-captured leafs toplevel arg for checking. */
1545 force_no_side_effects
|= 1 << toplevel_arg
;
1551 /* Analyze captures in the result expression piece O. */
1554 capture_info::walk_result (operand
*o
, bool conditional_p
)
1556 if (capture
*c
= dyn_cast
<capture
*> (o
))
1558 info
[c
->where
].result_use_count
++;
1559 /* If we substitute an expression capture we don't know
1560 which captures this will end up using (well, we don't
1561 compute that). Force the uses to be side-effect free
1562 which means forcing the toplevels that reach the
1563 expression side-effect free. */
1564 if (info
[c
->where
].expr_p
)
1565 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1566 /* Mark CSE capture capture uses as forced to have
1569 && is_a
<expr
*> (c
->what
))
1571 info
[c
->where
].cse_p
= true;
1572 walk_result (c
->what
, true);
1575 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1577 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1579 bool cond_p
= conditional_p
;
1580 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1582 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1583 || *e
->operation
== TRUTH_ORIF_EXPR
)
1585 walk_result (e
->ops
[i
], cond_p
);
1588 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1594 /* Look for captures in the C expr E. */
1597 capture_info::walk_c_expr (c_expr
*e
)
1599 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
1600 unsigned p_depth
= 0;
1601 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1603 const cpp_token
*t
= &e
->code
[i
];
1604 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1605 if (t
->type
== CPP_NAME
1606 && strcmp ((const char *)CPP_HASHNODE
1607 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1608 && n
->type
== CPP_OPEN_PAREN
)
1610 else if (t
->type
== CPP_CLOSE_PAREN
1613 else if (p_depth
== 0
1614 && t
->type
== CPP_ATSIGN
1615 && (n
->type
== CPP_NUMBER
1616 || n
->type
== CPP_NAME
)
1617 && !(n
->flags
& PREV_WHITE
))
1620 if (n
->type
== CPP_NUMBER
)
1621 id
= (const char *)n
->val
.str
.text
;
1623 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1624 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
1630 /* Code generation off the decision tree and the refered AST nodes. */
1633 is_conversion (id_base
*op
)
1635 return (*op
== CONVERT_EXPR
1637 || *op
== FLOAT_EXPR
1638 || *op
== FIX_TRUNC_EXPR
1639 || *op
== VIEW_CONVERT_EXPR
);
1642 /* Get the type to be used for generating operands of OP from the
1646 get_operand_type (id_base
*op
, const char *in_type
,
1647 const char *expr_type
,
1648 const char *other_oprnd_type
)
1650 /* Generally operands whose type does not match the type of the
1651 expression generated need to know their types but match and
1652 thus can fall back to 'other_oprnd_type'. */
1653 if (is_conversion (op
))
1654 return other_oprnd_type
;
1655 else if (*op
== REALPART_EXPR
1656 || *op
== IMAGPART_EXPR
)
1657 return other_oprnd_type
;
1658 else if (is_a
<operator_id
*> (op
)
1659 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1660 return other_oprnd_type
;
1663 /* Otherwise all types should match - choose one in order of
1670 return other_oprnd_type
;
1674 /* Generate transform code for an expression. */
1677 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1678 const char *in_type
, capture_info
*cinfo
,
1679 dt_operand
**indexes
, bool)
1681 bool conversion_p
= is_conversion (operation
);
1682 const char *type
= expr_type
;
1685 /* If there was a type specification in the pattern use it. */
1687 else if (conversion_p
)
1688 /* For conversions we need to build the expression using the
1689 outer type passed in. */
1691 else if (*operation
== REALPART_EXPR
1692 || *operation
== IMAGPART_EXPR
)
1694 /* __real and __imag use the component type of its operand. */
1695 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1698 else if (is_a
<operator_id
*> (operation
)
1699 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1701 /* comparisons use boolean_type_node (or what gets in), but
1702 their operands need to figure out the types themselves. */
1703 sprintf (optype
, "boolean_type_node");
1708 /* Other operations are of the same type as their first operand. */
1709 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1713 fatal ("two conversions in a row");
1716 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1718 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1719 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1722 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1724 = get_operand_type (operation
, in_type
, expr_type
,
1725 i
== 0 ? NULL
: op0type
);
1726 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, cinfo
, indexes
,
1727 ((!(*operation
== COND_EXPR
)
1728 && !(*operation
== VEC_COND_EXPR
))
1733 if (*operation
== CONVERT_EXPR
)
1736 opr
= operation
->id
;
1740 /* ??? Have another helper that is like gimple_build but may
1741 fail if seq == NULL. */
1742 fprintf (f
, " if (!seq)\n"
1744 " res = gimple_simplify (%s, %s", opr
, type
);
1745 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1746 fprintf (f
, ", ops%d[%u]", depth
, i
);
1747 fprintf (f
, ", seq, valueize);\n");
1748 fprintf (f
, " if (!res) return false;\n");
1749 fprintf (f
, " }\n");
1750 fprintf (f
, " else\n");
1751 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1753 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1754 fprintf (f
, ", ops%d[%u]", depth
, i
);
1755 fprintf (f
, ", valueize);\n");
1759 if (operation
->kind
== id_base::CODE
)
1760 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1761 ops
.length(), opr
, type
);
1763 fprintf (f
, " res = build_call_expr_loc (loc, "
1764 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1765 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1766 fprintf (f
, ", ops%d[%u]", depth
, i
);
1767 fprintf (f
, ");\n");
1769 fprintf (f
, " %s = res;\n", dest
);
1773 /* Generate code for a c_expr which is either the expression inside
1774 an if statement or a sequence of statements which computes a
1775 result to be stored to DEST. */
1778 c_expr::gen_transform (FILE *f
, const char *dest
,
1779 bool, int, const char *, capture_info
*,
1780 dt_operand
**, bool)
1782 if (dest
&& nr_stmts
== 1)
1783 fprintf (f
, "%s = ", dest
);
1785 unsigned stmt_nr
= 1;
1786 for (unsigned i
= 0; i
< code
.length (); ++i
)
1788 const cpp_token
*token
= &code
[i
];
1790 /* Replace captures for code-gen. */
1791 if (token
->type
== CPP_ATSIGN
)
1793 const cpp_token
*n
= &code
[i
+1];
1794 if ((n
->type
== CPP_NUMBER
1795 || n
->type
== CPP_NAME
)
1796 && !(n
->flags
& PREV_WHITE
))
1798 if (token
->flags
& PREV_WHITE
)
1801 if (n
->type
== CPP_NUMBER
)
1802 id
= (const char *)n
->val
.str
.text
;
1804 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1805 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1811 if (token
->flags
& PREV_WHITE
)
1814 if (token
->type
== CPP_NAME
)
1816 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1818 for (j
= 0; j
< ids
.length (); ++j
)
1820 if (strcmp (id
, ids
[j
].id
) == 0)
1822 fprintf (f
, "%s", ids
[j
].oper
);
1826 if (j
< ids
.length ())
1830 /* Output the token as string. */
1831 char *tk
= (char *)cpp_token_as_text (r
, token
);
1834 if (token
->type
== CPP_SEMICOLON
)
1837 if (dest
&& stmt_nr
== nr_stmts
)
1838 fprintf (f
, "\n %s = ", dest
);
1845 /* Generate transform code for a capture. */
1848 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1849 const char *in_type
, capture_info
*cinfo
,
1850 dt_operand
**indexes
, bool expand_compares
)
1852 if (what
&& is_a
<expr
*> (what
))
1854 if (indexes
[where
] == 0)
1857 sprintf (buf
, "captures[%u]", where
);
1858 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, cinfo
, NULL
);
1862 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1864 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
1865 with substituting a capture of that.
1866 ??? Returning false here will also not allow any other patterns
1868 if (gimple
&& expand_compares
1869 && cinfo
->info
[where
].cond_expr_cond_p
)
1870 fprintf (f
, "if (COMPARISON_CLASS_P (%s))\n"
1872 " if (!seq) return false;\n"
1873 " %s = gimple_build (seq, TREE_CODE (%s),"
1874 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
1875 " TREE_OPERAND (%s, 1));\n"
1876 " }\n", dest
, dest
, dest
, dest
, dest
, dest
);
1879 /* Return the name of the operand representing the decision tree node.
1880 Use NAME as space to generate it. */
1883 dt_operand::get_name (char *name
)
1886 sprintf (name
, "t");
1887 else if (parent
->level
== 1)
1888 sprintf (name
, "op%u", pos
);
1889 else if (parent
->type
== dt_node::DT_MATCH
)
1890 return parent
->get_name (name
);
1892 sprintf (name
, "o%u%u", parent
->level
, pos
);
1896 /* Fill NAME with the operand name at position POS. */
1899 dt_operand::gen_opname (char *name
, unsigned pos
)
1902 sprintf (name
, "op%u", pos
);
1904 sprintf (name
, "o%u%u", level
, pos
);
1907 /* Generate matching code for the decision tree operand which is
1911 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1913 predicate
*p
= as_a
<predicate
*> (op
);
1915 if (p
->p
->matchers
.exists ())
1917 /* If this is a predicate generated from a pattern mangle its
1918 name and pass on the valueize hook. */
1920 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1922 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1925 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1930 /* Generate matching code for the decision tree operand which is
1934 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1936 char match_opname
[20];
1937 match_dop
->get_name (match_opname
);
1938 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1939 opname
, match_opname
, opname
, match_opname
);
1944 /* Generate GIMPLE matching code for the decision tree operand. */
1947 dt_operand::gen_gimple_expr (FILE *f
)
1949 expr
*e
= static_cast<expr
*> (op
);
1950 id_base
*id
= e
->operation
;
1951 unsigned n_ops
= e
->ops
.length ();
1953 for (unsigned i
= 0; i
< n_ops
; ++i
)
1955 char child_opname
[20];
1956 gen_opname (child_opname
, i
);
1958 if (id
->kind
== id_base::CODE
)
1961 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1962 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1964 /* ??? If this is a memory operation we can't (and should not)
1965 match this. The only sensible operand types are
1966 SSA names and invariants. */
1967 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1969 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1970 "|| is_gimple_min_invariant (%s))\n"
1971 "&& (%s = do_valueize (valueize, %s)))\n"
1972 "{\n", child_opname
, child_opname
, child_opname
,
1977 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1978 child_opname
, i
+ 1);
1981 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1983 fprintf (f
, "if ((%s = do_valueize (valueize, %s)))\n",
1984 child_opname
, child_opname
);
1991 /* Generate GENERIC matching code for the decision tree operand. */
1994 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1996 expr
*e
= static_cast<expr
*> (op
);
1997 unsigned n_ops
= e
->ops
.length ();
1999 for (unsigned i
= 0; i
< n_ops
; ++i
)
2001 char child_opname
[20];
2002 gen_opname (child_opname
, i
);
2004 if (e
->operation
->kind
== id_base::CODE
)
2005 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
2006 child_opname
, opname
, i
);
2008 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2009 child_opname
, opname
, i
);
2015 /* Generate matching code for the children of the decision tree node. */
2018 dt_node::gen_kids (FILE *f
, bool gimple
)
2020 auto_vec
<dt_operand
*> gimple_exprs
;
2021 auto_vec
<dt_operand
*> generic_exprs
;
2022 auto_vec
<dt_operand
*> fns
;
2023 auto_vec
<dt_operand
*> generic_fns
;
2024 auto_vec
<dt_operand
*> preds
;
2025 auto_vec
<dt_node
*> others
;
2027 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2029 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2031 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2032 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2034 if (e
->ops
.length () == 0
2035 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2036 generic_exprs
.safe_push (op
);
2037 else if (e
->operation
->kind
== id_base::FN
)
2042 generic_fns
.safe_push (op
);
2044 else if (e
->operation
->kind
== id_base::PREDICATE
)
2045 preds
.safe_push (op
);
2049 gimple_exprs
.safe_push (op
);
2051 generic_exprs
.safe_push (op
);
2054 else if (op
->op
->type
== operand::OP_PREDICATE
)
2055 others
.safe_push (kids
[i
]);
2059 else if (kids
[i
]->type
== dt_node::DT_MATCH
2060 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2061 others
.safe_push (kids
[i
]);
2062 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2064 /* A DT_TRUE operand serves as a barrier - generate code now
2065 for what we have collected sofar. */
2066 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2067 fns
, generic_fns
, preds
, others
);
2068 /* And output the true operand itself. */
2069 kids
[i
]->gen (f
, gimple
);
2070 gimple_exprs
.truncate (0);
2071 generic_exprs
.truncate (0);
2073 generic_fns
.truncate (0);
2075 others
.truncate (0);
2081 /* Generate code for the remains. */
2082 gen_kids_1 (f
, gimple
, gimple_exprs
, generic_exprs
,
2083 fns
, generic_fns
, preds
, others
);
2086 /* Generate matching code for the children of the decision tree node. */
2089 dt_node::gen_kids_1 (FILE *f
, bool gimple
,
2090 vec
<dt_operand
*> gimple_exprs
,
2091 vec
<dt_operand
*> generic_exprs
,
2092 vec
<dt_operand
*> fns
,
2093 vec
<dt_operand
*> generic_fns
,
2094 vec
<dt_operand
*> preds
,
2095 vec
<dt_node
*> others
)
2098 char *kid_opname
= buf
;
2100 unsigned exprs_len
= gimple_exprs
.length ();
2101 unsigned gexprs_len
= generic_exprs
.length ();
2102 unsigned fns_len
= fns
.length ();
2103 unsigned gfns_len
= generic_fns
.length ();
2105 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2108 gimple_exprs
[0]->get_name (kid_opname
);
2110 fns
[0]->get_name (kid_opname
);
2112 generic_fns
[0]->get_name (kid_opname
);
2114 generic_exprs
[0]->get_name (kid_opname
);
2116 fprintf (f
, "switch (TREE_CODE (%s))\n"
2120 if (exprs_len
|| fns_len
)
2122 fprintf (f
, "case SSA_NAME:\n");
2123 fprintf (f
, "if (do_valueize (valueize, %s) != NULL_TREE)\n", kid_opname
);
2125 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
2129 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
2130 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
2132 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2134 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2135 id_base
*op
= e
->operation
;
2136 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2137 fprintf (f
, "CASE_CONVERT:\n");
2139 fprintf (f
, "case %s:\n", op
->id
);
2141 gimple_exprs
[i
]->gen (f
, true);
2142 fprintf (f
, "break;\n"
2145 fprintf (f
, "default:;\n"
2152 fprintf (f
, "else ");
2154 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
2156 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
2157 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2160 for (unsigned i
= 0; i
< fns_len
; ++i
)
2162 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2163 fprintf (f
, "case %s:\n"
2164 "{\n", e
->operation
->id
);
2165 fns
[i
]->gen (f
, true);
2166 fprintf (f
, "break;\n"
2170 fprintf (f
, "default:;\n"
2179 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2181 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2182 id_base
*op
= e
->operation
;
2183 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2184 fprintf (f
, "CASE_CONVERT:\n");
2186 fprintf (f
, "case %s:\n", op
->id
);
2188 generic_exprs
[i
]->gen (f
, gimple
);
2189 fprintf (f
, "break;\n"
2195 fprintf (f
, "case CALL_EXPR:\n"
2197 "tree fndecl = get_callee_fndecl (%s);\n"
2198 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
2199 "switch (DECL_FUNCTION_CODE (fndecl))\n"
2202 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2204 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2205 gcc_assert (e
->operation
->kind
== id_base::FN
);
2207 fprintf (f
, "case %s:\n"
2208 "{\n", e
->operation
->id
);
2209 generic_fns
[j
]->gen (f
, false);
2210 fprintf (f
, "break;\n"
2214 fprintf (f
, "default:;\n"
2220 /* Close switch (TREE_CODE ()). */
2221 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2222 fprintf (f
, "default:;\n"
2225 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2227 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2228 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2229 preds
[i
]->get_name (kid_opname
);
2230 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2231 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
2232 gimple
? "gimple" : "tree",
2233 p
->id
, kid_opname
, kid_opname
,
2234 gimple
? ", valueize" : "");
2236 for (int j
= 0; j
< p
->nargs
; ++j
)
2238 char child_opname
[20];
2239 preds
[i
]->gen_opname (child_opname
, j
);
2240 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
2242 preds
[i
]->gen_kids (f
, gimple
);
2246 for (unsigned i
= 0; i
< others
.length (); ++i
)
2247 others
[i
]->gen (f
, gimple
);
2250 /* Generate matching code for the decision tree operand. */
2253 dt_operand::gen (FILE *f
, bool gimple
)
2258 unsigned n_braces
= 0;
2260 if (type
== DT_OPERAND
)
2263 case operand::OP_PREDICATE
:
2264 n_braces
= gen_predicate (f
, opname
, gimple
);
2267 case operand::OP_EXPR
:
2269 n_braces
= gen_gimple_expr (f
);
2271 n_braces
= gen_generic_expr (f
, opname
);
2277 else if (type
== DT_TRUE
)
2279 else if (type
== DT_MATCH
)
2280 n_braces
= gen_match_op (f
, opname
);
2284 gen_kids (f
, gimple
);
2286 for (unsigned i
= 0; i
< n_braces
; ++i
)
2292 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2293 step of a '(simplify ...)' or '(match ...)'. This handles everything
2294 that is not part of the decision tree (simplify->match). */
2297 dt_simplify::gen (FILE *f
, bool gimple
)
2300 output_line_directive (f
, s
->result_location
);
2301 if (s
->capture_max
>= 0)
2302 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2303 s
->capture_max
+ 1);
2305 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2309 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2312 unsigned n_braces
= 0;
2313 if (s
->ifexpr_vec
!= vNULL
)
2315 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2317 if_or_with
&w
= s
->ifexpr_vec
[i
];
2321 output_line_directive (f
, w
.location
);
2322 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2327 output_line_directive (f
, w
.location
);
2328 fprintf (f
, "if (");
2329 if (i
== s
->ifexpr_vec
.length () - 1
2330 || s
->ifexpr_vec
[i
+1].is_with
)
2331 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type", NULL
);
2340 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2344 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2350 while (j
< s
->ifexpr_vec
.length ()
2351 && !s
->ifexpr_vec
[j
].is_with
);
2361 /* Analyze captures and perform early-outs on the incoming arguments
2362 that cover cases we cannot handle. */
2363 capture_info
cinfo (s
);
2367 && !((e
= dyn_cast
<expr
*> (s
->result
))
2368 && is_a
<predicate_id
*> (e
->operation
)))
2370 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2371 if (cinfo
.force_no_side_effects
& (1 << i
))
2372 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2373 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2374 if (cinfo
.info
[i
].cse_p
)
2376 else if (cinfo
.info
[i
].force_no_side_effects_p
2377 && (cinfo
.info
[i
].toplevel_msk
2378 & cinfo
.force_no_side_effects
) == 0)
2379 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2380 "return NULL_TREE;\n", i
);
2381 else if ((cinfo
.info
[i
].toplevel_msk
2382 & cinfo
.force_no_side_effects
) != 0)
2383 /* Mark capture as having no side-effects if we had to verify
2384 that via forced toplevel operand checks. */
2385 cinfo
.info
[i
].force_no_side_effects_p
= true;
2388 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2389 "fprintf (dump_file, \"Applying pattern ");
2390 output_line_directive (f
, s
->result_location
, true);
2391 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2393 operand
*result
= s
->result
;
2396 /* If there is no result then this is a predicate implementation. */
2397 fprintf (f
, "return true;\n");
2401 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2402 in outermost position). */
2403 if (result
->type
== operand::OP_EXPR
2404 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2405 result
= as_a
<expr
*> (result
)->ops
[0];
2406 if (result
->type
== operand::OP_EXPR
)
2408 expr
*e
= as_a
<expr
*> (result
);
2409 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2411 fprintf (f
, "*res_code = %s;\n",
2412 *e
->operation
== CONVERT_EXPR
2413 ? "NOP_EXPR" : e
->operation
->id
);
2414 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2417 snprintf (dest
, 32, " res_ops[%d]", j
);
2419 = get_operand_type (e
->operation
,
2420 "type", e
->expr_type
,
2422 ? NULL
: "TREE_TYPE (res_ops[0])");
2423 /* We need to expand GENERIC conditions we captured from
2425 bool expand_generic_cond_exprs_p
2427 /* But avoid doing that if the GENERIC condition is
2428 valid - which it is in the first operand of COND_EXPRs
2429 and VEC_COND_EXRPs. */
2430 && ((!(*e
->operation
== COND_EXPR
)
2431 && !(*e
->operation
== VEC_COND_EXPR
))
2433 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, &cinfo
,
2434 indexes
, expand_generic_cond_exprs_p
);
2437 /* Re-fold the toplevel result. It's basically an embedded
2438 gimple_build w/o actually building the stmt. */
2440 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2441 "res_ops, valueize);\n", e
->ops
.length ());
2443 else if (result
->type
== operand::OP_CAPTURE
2444 || result
->type
== operand::OP_C_EXPR
)
2446 result
->gen_transform (f
, "res_ops[0]", true, 1, "type",
2447 &cinfo
, indexes
, false);
2448 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2449 if (is_a
<capture
*> (result
)
2450 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2452 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2453 with substituting a capture of that. */
2454 fprintf (f
, "if (COMPARISON_CLASS_P (res_ops[0]))\n"
2456 " tree tem = res_ops[0];\n"
2457 " res_ops[0] = TREE_OPERAND (tem, 0);\n"
2458 " res_ops[1] = TREE_OPERAND (tem, 1);\n"
2464 fprintf (f
, "return true;\n");
2468 bool is_predicate
= false;
2469 if (result
->type
== operand::OP_EXPR
)
2471 expr
*e
= as_a
<expr
*> (result
);
2472 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2473 /* Search for captures used multiple times in the result expression
2474 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2476 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2478 if (!cinfo
.info
[i
].force_no_side_effects_p
2479 && cinfo
.info
[i
].result_use_count
> 1)
2480 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2481 " captures[%d] = save_expr (captures[%d]);\n",
2484 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2488 snprintf (dest
, 32, "res_ops[%d]", j
);
2491 fprintf (f
, " tree res_op%d;\n", j
);
2492 snprintf (dest
, 32, " res_op%d", j
);
2495 = get_operand_type (e
->operation
,
2496 "type", e
->expr_type
,
2498 ? NULL
: "TREE_TYPE (res_op0)");
2499 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
,
2503 fprintf (f
, "return true;\n");
2506 fprintf (f
, " tree res;\n");
2507 /* Re-fold the toplevel result. Use non_lvalue to
2508 build NON_LVALUE_EXPRs so they get properly
2509 ignored when in GIMPLE form. */
2510 if (*e
->operation
== NON_LVALUE_EXPR
)
2511 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2514 if (e
->operation
->kind
== id_base::CODE
)
2515 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2517 *e
->operation
== CONVERT_EXPR
2518 ? "NOP_EXPR" : e
->operation
->id
);
2520 fprintf (f
, " res = build_call_expr_loc "
2521 "(loc, builtin_decl_implicit (%s), %d",
2522 e
->operation
->id
, e
->ops
.length());
2523 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2524 fprintf (f
, ", res_op%d", j
);
2525 fprintf (f
, ");\n");
2529 else if (result
->type
== operand::OP_CAPTURE
2530 || result
->type
== operand::OP_C_EXPR
)
2533 fprintf (f
, " tree res;\n");
2534 s
->result
->gen_transform (f
, " res", false, 1, "type",
2541 /* Search for captures not used in the result expression and dependent
2542 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2543 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2545 if (!cinfo
.info
[i
].force_no_side_effects_p
2546 && !cinfo
.info
[i
].expr_p
2547 && cinfo
.info
[i
].result_use_count
== 0)
2548 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2549 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2550 " fold_ignored_result (captures[%d]), res);\n",
2553 fprintf (f
, " return res;\n");
2557 for (unsigned i
= 0; i
< n_braces
; ++i
)
2563 /* Main entry to generate code for matching GIMPLE IL off the decision
2567 decision_tree::gen_gimple (FILE *f
)
2569 for (unsigned n
= 1; n
<= 3; ++n
)
2571 fprintf (f
, "\nstatic bool\n"
2572 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2573 " gimple_seq *seq, tree (*valueize)(tree),\n"
2574 " code_helper code, tree type");
2575 for (unsigned i
= 0; i
< n
; ++i
)
2576 fprintf (f
, ", tree op%d", i
);
2580 fprintf (f
, "switch (code.get_rep())\n"
2582 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2584 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2585 expr
*e
= static_cast<expr
*>(dop
->op
);
2586 if (e
->ops
.length () != n
)
2589 if (*e
->operation
== CONVERT_EXPR
2590 || *e
->operation
== NOP_EXPR
)
2591 fprintf (f
, "CASE_CONVERT:\n");
2593 fprintf (f
, "case %s%s:\n",
2594 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2597 dop
->gen_kids (f
, true);
2598 fprintf (f
, "break;\n");
2601 fprintf (f
, "default:;\n"
2604 fprintf (f
, "return false;\n");
2609 /* Main entry to generate code for matching GENERIC IL off the decision
2613 decision_tree::gen_generic (FILE *f
)
2615 for (unsigned n
= 1; n
<= 3; ++n
)
2617 fprintf (f
, "\ntree\n"
2618 "generic_simplify (location_t loc, enum tree_code code, "
2619 "tree type ATTRIBUTE_UNUSED");
2620 for (unsigned i
= 0; i
< n
; ++i
)
2621 fprintf (f
, ", tree op%d", i
);
2625 fprintf (f
, "switch (code)\n"
2627 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2629 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2630 expr
*e
= static_cast<expr
*>(dop
->op
);
2631 if (e
->ops
.length () != n
2632 /* Builtin simplifications are somewhat premature on
2633 GENERIC. The following drops patterns with outermost
2634 calls. It's easy to emit overloads for function code
2635 though if necessary. */
2636 || e
->operation
->kind
!= id_base::CODE
)
2639 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2640 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2641 fprintf (f
, "CASE_CONVERT:\n");
2643 fprintf (f
, "case %s:\n", e
->operation
->id
);
2645 dop
->gen_kids (f
, false);
2646 fprintf (f
, "break;\n"
2649 fprintf (f
, "default:;\n"
2652 fprintf (f
, "return NULL_TREE;\n");
2657 /* Output code to implement the predicate P from the decision tree DT. */
2660 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2662 fprintf (f
, "\nbool\n"
2663 "%s%s (tree t%s%s)\n"
2664 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2665 p
->nargs
> 0 ? ", tree *res_ops" : "",
2666 gimple
? ", tree (*valueize)(tree)" : "");
2667 /* Conveniently make 'type' available. */
2668 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2671 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2672 dt
.root
->gen_kids (f
, gimple
);
2674 fprintf (f
, "return false;\n"
2678 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2681 write_header (FILE *f
, const char *head
)
2683 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2684 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2686 /* Include the header instead of writing it awkwardly quoted here. */
2687 fprintf (f
, "\n#include \"%s\"\n", head
);
2697 parser (cpp_reader
*);
2700 const cpp_token
*next ();
2701 const cpp_token
*peek ();
2702 const cpp_token
*peek_ident (const char * = NULL
);
2703 const cpp_token
*expect (enum cpp_ttype
);
2704 void eat_token (enum cpp_ttype
);
2705 const char *get_string ();
2706 const char *get_ident ();
2707 void eat_ident (const char *);
2708 const char *get_number ();
2710 id_base
*parse_operation ();
2711 operand
*parse_capture (operand
*);
2712 operand
*parse_expr ();
2713 c_expr
*parse_c_expr (cpp_ttype
);
2714 operand
*parse_op ();
2716 void record_operlist (source_location
, user_id
*);
2718 void parse_pattern ();
2719 void push_simplify (vec
<simplify
*>&, operand
*, source_location
,
2720 operand
*, source_location
);
2721 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
* = 0,
2723 void parse_for (source_location
);
2724 void parse_if (source_location
);
2725 void parse_predicates (source_location
);
2726 void parse_operator_list (source_location
);
2729 vec
<if_or_with
> active_ifs
;
2730 vec
<vec
<user_id
*> > active_fors
;
2731 hash_set
<user_id
*> *oper_lists_set
;
2732 vec
<user_id
*> oper_lists
;
2734 cid_map_t
*capture_ids
;
2737 vec
<simplify
*> simplifiers
;
2738 vec
<predicate_id
*> user_predicates
;
2739 bool parsing_match_operand
;
2742 /* Lexing helpers. */
2744 /* Read the next non-whitespace token from R. */
2749 const cpp_token
*token
;
2752 token
= cpp_get_token (r
);
2754 while (token
->type
== CPP_PADDING
2755 && token
->type
!= CPP_EOF
);
2759 /* Peek at the next non-whitespace token from R. */
2764 const cpp_token
*token
;
2768 token
= cpp_peek_token (r
, i
++);
2770 while (token
->type
== CPP_PADDING
2771 && token
->type
!= CPP_EOF
);
2772 /* If we peek at EOF this is a fatal error as it leaves the
2773 cpp_reader in unusable state. Assume we really wanted a
2774 token and thus this EOF is unexpected. */
2775 if (token
->type
== CPP_EOF
)
2776 fatal_at (token
, "unexpected end of file");
2780 /* Peek at the next identifier token (or return NULL if the next
2781 token is not an identifier or equal to ID if supplied). */
2784 parser::peek_ident (const char *id
)
2786 const cpp_token
*token
= peek ();
2787 if (token
->type
!= CPP_NAME
)
2793 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2794 if (strcmp (id
, t
) == 0)
2800 /* Read the next token from R and assert it is of type TK. */
2803 parser::expect (enum cpp_ttype tk
)
2805 const cpp_token
*token
= next ();
2806 if (token
->type
!= tk
)
2807 fatal_at (token
, "expected %s, got %s",
2808 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2813 /* Consume the next token from R and assert it is of type TK. */
2816 parser::eat_token (enum cpp_ttype tk
)
2821 /* Read the next token from R and assert it is of type CPP_STRING and
2822 return its value. */
2825 parser::get_string ()
2827 const cpp_token
*token
= expect (CPP_STRING
);
2828 return (const char *)token
->val
.str
.text
;
2831 /* Read the next token from R and assert it is of type CPP_NAME and
2832 return its value. */
2835 parser::get_ident ()
2837 const cpp_token
*token
= expect (CPP_NAME
);
2838 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2841 /* Eat an identifier token with value S from R. */
2844 parser::eat_ident (const char *s
)
2846 const cpp_token
*token
= peek ();
2847 const char *t
= get_ident ();
2848 if (strcmp (s
, t
) != 0)
2849 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2852 /* Read the next token from R and assert it is of type CPP_NUMBER and
2853 return its value. */
2856 parser::get_number ()
2858 const cpp_token
*token
= expect (CPP_NUMBER
);
2859 return (const char *)token
->val
.str
.text
;
2863 /* Record an operator-list use for transparent for handling. */
2866 parser::record_operlist (source_location loc
, user_id
*p
)
2868 if (!oper_lists_set
->add (p
))
2870 if (!oper_lists
.is_empty ()
2871 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
2872 fatal_at (loc
, "User-defined operator list does not have the "
2873 "same number of entries as others used in the pattern");
2874 oper_lists
.safe_push (p
);
2878 /* Parse the operator ID, special-casing convert?, convert1? and
2882 parser::parse_operation ()
2884 const cpp_token
*id_tok
= peek ();
2885 const char *id
= get_ident ();
2886 const cpp_token
*token
= peek ();
2887 if (strcmp (id
, "convert0") == 0)
2888 fatal_at (id_tok
, "use 'convert?' here");
2889 if (token
->type
== CPP_QUERY
2890 && !(token
->flags
& PREV_WHITE
))
2892 if (strcmp (id
, "convert") == 0)
2894 else if (strcmp (id
, "convert1") == 0)
2896 else if (strcmp (id
, "convert2") == 0)
2899 fatal_at (id_tok
, "non-convert operator conditionalized");
2901 if (!parsing_match_operand
)
2902 fatal_at (id_tok
, "conditional convert can only be used in "
2903 "match expression");
2904 eat_token (CPP_QUERY
);
2906 else if (strcmp (id
, "convert1") == 0
2907 || strcmp (id
, "convert2") == 0)
2908 fatal_at (id_tok
, "expected '?' after conditional operator");
2909 id_base
*op
= get_operator (id
);
2911 fatal_at (id_tok
, "unknown operator %s", id
);
2913 user_id
*p
= dyn_cast
<user_id
*> (op
);
2914 if (p
&& p
->is_oper_list
)
2915 record_operlist (id_tok
->src_loc
, p
);
2920 capture = '@'<number> */
2923 parser::parse_capture (operand
*op
)
2925 eat_token (CPP_ATSIGN
);
2926 const cpp_token
*token
= peek ();
2927 const char *id
= NULL
;
2928 if (token
->type
== CPP_NUMBER
)
2930 else if (token
->type
== CPP_NAME
)
2933 fatal_at (token
, "expected number or identifier");
2934 unsigned next_id
= capture_ids
->elements ();
2936 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2939 return new capture (num
, op
, id
);
2942 /* Parse an expression
2943 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2946 parser::parse_expr ()
2948 expr
*e
= new expr (parse_operation ());
2949 const cpp_token
*token
= peek ();
2951 bool is_commutative
= false;
2952 const char *expr_type
= NULL
;
2954 if (token
->type
== CPP_COLON
2955 && !(token
->flags
& PREV_WHITE
))
2957 eat_token (CPP_COLON
);
2959 if (token
->type
== CPP_NAME
2960 && !(token
->flags
& PREV_WHITE
))
2962 const char *s
= get_ident ();
2963 if (s
[0] == 'c' && !s
[1])
2965 if (!parsing_match_operand
)
2967 "flag 'c' can only be used in match expression");
2968 is_commutative
= true;
2970 else if (s
[1] != '\0')
2972 if (parsing_match_operand
)
2973 fatal_at (token
, "type can only be used in result expression");
2977 fatal_at (token
, "flag %s not recognized", s
);
2982 fatal_at (token
, "expected flag or type specifying identifier");
2985 if (token
->type
== CPP_ATSIGN
2986 && !(token
->flags
& PREV_WHITE
))
2987 op
= parse_capture (e
);
2992 const cpp_token
*token
= peek ();
2993 if (token
->type
== CPP_CLOSE_PAREN
)
2995 if (e
->operation
->nargs
!= -1
2996 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2997 fatal_at (token
, "'%s' expects %u operands, not %u",
2998 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3001 if (e
->ops
.length () == 2)
3002 e
->is_commutative
= true;
3004 fatal_at (token
, "only binary operators or function with "
3005 "two arguments can be marked commutative");
3007 e
->expr_type
= expr_type
;
3010 e
->append_op (parse_op ());
3015 /* Lex native C code delimited by START recording the preprocessing tokens
3016 for later processing.
3017 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3020 parser::parse_c_expr (cpp_ttype start
)
3022 const cpp_token
*token
;
3025 vec
<cpp_token
> code
= vNULL
;
3026 unsigned nr_stmts
= 0;
3028 if (start
== CPP_OPEN_PAREN
)
3029 end
= CPP_CLOSE_PAREN
;
3030 else if (start
== CPP_OPEN_BRACE
)
3031 end
= CPP_CLOSE_BRACE
;
3039 /* Count brace pairs to find the end of the expr to match. */
3040 if (token
->type
== start
)
3042 else if (token
->type
== end
3046 /* This is a lame way of counting the number of statements. */
3047 if (token
->type
== CPP_SEMICOLON
)
3050 /* If this is possibly a user-defined identifier mark it used. */
3051 if (token
->type
== CPP_NAME
)
3053 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3054 (token
->val
.node
.node
)->ident
.str
);
3056 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3057 record_operlist (token
->src_loc
, p
);
3060 /* Record the token. */
3061 code
.safe_push (*token
);
3064 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
3067 /* Parse an operand which is either an expression, a predicate or
3068 a standalone capture.
3069 op = predicate | expr | c_expr | capture */
3074 const cpp_token
*token
= peek ();
3075 struct operand
*op
= NULL
;
3076 if (token
->type
== CPP_OPEN_PAREN
)
3078 eat_token (CPP_OPEN_PAREN
);
3080 eat_token (CPP_CLOSE_PAREN
);
3082 else if (token
->type
== CPP_OPEN_BRACE
)
3084 op
= parse_c_expr (CPP_OPEN_BRACE
);
3088 /* Remaining ops are either empty or predicates */
3089 if (token
->type
== CPP_NAME
)
3091 const char *id
= get_ident ();
3092 id_base
*opr
= get_operator (id
);
3094 fatal_at (token
, "expected predicate name");
3095 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3097 if (code
->nargs
!= 0)
3098 fatal_at (token
, "using an operator with operands as predicate");
3099 /* Parse the zero-operand operator "predicates" as
3101 op
= new expr (opr
);
3103 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3105 if (code
->nargs
!= 0)
3106 fatal_at (token
, "using an operator with operands as predicate");
3107 /* Parse the zero-operand operator "predicates" as
3109 op
= new expr (opr
);
3111 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3112 op
= new predicate (p
);
3114 fatal_at (token
, "using an unsupported operator as predicate");
3115 if (!parsing_match_operand
)
3116 fatal_at (token
, "predicates are only allowed in match expression");
3118 if (token
->flags
& PREV_WHITE
)
3121 else if (token
->type
!= CPP_COLON
3122 && token
->type
!= CPP_ATSIGN
)
3123 fatal_at (token
, "expected expression or predicate");
3124 /* optionally followed by a capture and a predicate. */
3125 if (token
->type
== CPP_COLON
)
3126 fatal_at (token
, "not implemented: predicate on leaf operand");
3127 if (token
->type
== CPP_ATSIGN
)
3128 op
= parse_capture (op
);
3134 /* Create a new simplify from the current parsing state and MATCH,
3135 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3138 parser::push_simplify (vec
<simplify
*>& simplifiers
,
3139 operand
*match
, source_location match_loc
,
3140 operand
*result
, source_location result_loc
)
3142 /* Build and push a temporary for for operator list uses in expressions. */
3143 if (!oper_lists
.is_empty ())
3144 active_fors
.safe_push (oper_lists
);
3146 simplifiers
.safe_push
3147 (new simplify (match
, match_loc
, result
, result_loc
,
3148 active_ifs
.copy (), active_fors
.copy (), capture_ids
));
3150 if (!oper_lists
.is_empty ())
3155 simplify = 'simplify' <expr> <result-op>
3157 match = 'match' <ident> <expr> [<result-op>]
3159 <result-op> = <op> | <if> | <with>
3160 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
3161 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
3162 and fill SIMPLIFIERS with the results. */
3165 parser::parse_simplify (source_location match_location
,
3166 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
3169 /* Reset the capture map. */
3171 capture_ids
= new cid_map_t
;
3172 /* Reset oper_lists and set. */
3173 hash_set
<user_id
*> olist
;
3174 oper_lists_set
= &olist
;
3177 const cpp_token
*loc
= peek ();
3178 parsing_match_operand
= true;
3179 struct operand
*match
= parse_op ();
3180 parsing_match_operand
= false;
3181 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
3182 fatal_at (loc
, "outermost expression cannot be captured");
3183 if (match
->type
== operand::OP_EXPR
3184 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
3185 fatal_at (loc
, "outermost expression cannot be a predicate");
3187 const cpp_token
*token
= peek ();
3189 /* If this if is immediately closed then it is part of a predicate
3190 definition. Push it. */
3191 if (token
->type
== CPP_CLOSE_PAREN
)
3194 fatal_at (token
, "expected transform expression");
3195 push_simplify (simplifiers
, match
, match_location
,
3196 result
, token
->src_loc
);
3200 unsigned active_ifs_len
= active_ifs
.length ();
3203 if (token
->type
== CPP_OPEN_PAREN
)
3205 source_location paren_loc
= token
->src_loc
;
3206 eat_token (CPP_OPEN_PAREN
);
3207 if (peek_ident ("if"))
3210 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
3211 token
->src_loc
, false));
3212 /* If this if is immediately closed then it contains a
3213 manual matcher or is part of a predicate definition.
3215 if (peek ()->type
== CPP_CLOSE_PAREN
)
3218 fatal_at (token
, "manual transform not implemented");
3219 push_simplify (simplifiers
, match
, match_location
,
3223 else if (peek_ident ("with"))
3226 /* Parse (with c-expr expr) as (if-with (true) expr). */
3227 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
3229 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
3233 operand
*op
= result
;
3236 push_simplify (simplifiers
, match
, match_location
,
3237 op
, token
->src_loc
);
3238 eat_token (CPP_CLOSE_PAREN
);
3239 /* A "default" result closes the enclosing scope. */
3240 if (active_ifs
.length () > active_ifs_len
)
3242 eat_token (CPP_CLOSE_PAREN
);
3249 else if (token
->type
== CPP_CLOSE_PAREN
)
3251 /* Close a scope if requested. */
3252 if (active_ifs
.length () > active_ifs_len
)
3254 eat_token (CPP_CLOSE_PAREN
);
3264 fatal_at (token
, "expected match operand expression");
3265 push_simplify (simplifiers
, match
, match_location
,
3266 matcher
? result
: parse_op (), token
->src_loc
);
3267 /* A "default" result closes the enclosing scope. */
3268 if (active_ifs
.length () > active_ifs_len
)
3270 eat_token (CPP_CLOSE_PAREN
);
3280 /* Parsing of the outer control structures. */
3282 /* Parse a for expression
3283 for = '(' 'for' <subst>... <pattern> ')'
3284 subst = <ident> '(' <ident>... ')' */
3287 parser::parse_for (source_location
)
3289 auto_vec
<const cpp_token
*> user_id_tokens
;
3290 vec
<user_id
*> user_ids
= vNULL
;
3291 const cpp_token
*token
;
3292 unsigned min_n_opers
= 0, max_n_opers
= 0;
3297 if (token
->type
!= CPP_NAME
)
3300 /* Insert the user defined operators into the operator hash. */
3301 const char *id
= get_ident ();
3302 if (get_operator (id
) != NULL
)
3303 fatal_at (token
, "operator already defined");
3304 user_id
*op
= new user_id (id
);
3305 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3307 user_ids
.safe_push (op
);
3308 user_id_tokens
.safe_push (token
);
3310 eat_token (CPP_OPEN_PAREN
);
3313 while ((token
= peek_ident ()) != 0)
3315 const char *oper
= get_ident ();
3316 id_base
*idb
= get_operator (oper
);
3318 fatal_at (token
, "no such operator '%s'", oper
);
3319 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
3320 fatal_at (token
, "conditional operators cannot be used inside for");
3324 else if (idb
->nargs
== -1)
3326 else if (idb
->nargs
!= arity
)
3327 fatal_at (token
, "operator '%s' with arity %d does not match "
3328 "others with arity %d", oper
, idb
->nargs
, arity
);
3330 user_id
*p
= dyn_cast
<user_id
*> (idb
);
3331 if (p
&& p
->is_oper_list
)
3332 op
->substitutes
.safe_splice (p
->substitutes
);
3334 op
->substitutes
.safe_push (idb
);
3337 token
= expect (CPP_CLOSE_PAREN
);
3339 unsigned nsubstitutes
= op
->substitutes
.length ();
3340 if (nsubstitutes
== 0)
3341 fatal_at (token
, "A user-defined operator must have at least "
3342 "one substitution");
3343 if (max_n_opers
== 0)
3345 min_n_opers
= nsubstitutes
;
3346 max_n_opers
= nsubstitutes
;
3350 if (nsubstitutes
% min_n_opers
!= 0
3351 && min_n_opers
% nsubstitutes
!= 0)
3352 fatal_at (token
, "All user-defined identifiers must have a "
3353 "multiple number of operator substitutions of the "
3354 "smallest number of substitutions");
3355 if (nsubstitutes
< min_n_opers
)
3356 min_n_opers
= nsubstitutes
;
3357 else if (nsubstitutes
> max_n_opers
)
3358 max_n_opers
= nsubstitutes
;
3362 unsigned n_ids
= user_ids
.length ();
3364 fatal_at (token
, "for requires at least one user-defined identifier");
3367 if (token
->type
== CPP_CLOSE_PAREN
)
3368 fatal_at (token
, "no pattern defined in for");
3370 active_fors
.safe_push (user_ids
);
3374 if (token
->type
== CPP_CLOSE_PAREN
)
3380 /* Remove user-defined operators from the hash again. */
3381 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3383 if (!user_ids
[i
]->used
)
3384 warning_at (user_id_tokens
[i
],
3385 "operator %s defined but not used", user_ids
[i
]->id
);
3386 operators
->remove_elt (user_ids
[i
]);
3390 /* Parse an identifier associated with a list of operators.
3391 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
3394 parser::parse_operator_list (source_location
)
3396 const cpp_token
*token
= peek ();
3397 const char *id
= get_ident ();
3399 if (get_operator (id
) != 0)
3400 fatal_at (token
, "operator %s already defined", id
);
3402 user_id
*op
= new user_id (id
, true);
3405 while ((token
= peek_ident ()) != 0)
3408 const char *oper
= get_ident ();
3409 id_base
*idb
= get_operator (oper
);
3412 fatal_at (token
, "no such operator '%s'", oper
);
3416 else if (idb
->nargs
== -1)
3418 else if (arity
!= idb
->nargs
)
3419 fatal_at (token
, "operator '%s' with arity %d does not match "
3420 "others with arity %d", oper
, idb
->nargs
, arity
);
3422 /* We allow composition of multiple operator lists. */
3423 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
3424 op
->substitutes
.safe_splice (p
->substitutes
);
3426 op
->substitutes
.safe_push (idb
);
3429 if (op
->substitutes
.length () == 0)
3430 fatal_at (token
, "operator-list cannot be empty");
3433 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
3437 /* Parse an outer if expression.
3438 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3441 parser::parse_if (source_location loc
)
3443 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3445 const cpp_token
*token
= peek ();
3446 if (token
->type
== CPP_CLOSE_PAREN
)
3447 fatal_at (token
, "no pattern defined in if");
3449 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3452 const cpp_token
*token
= peek ();
3453 if (token
->type
== CPP_CLOSE_PAREN
)
3461 /* Parse a list of predefined predicate identifiers.
3462 preds = '(' 'define_predicates' <ident>... ')' */
3465 parser::parse_predicates (source_location
)
3469 const cpp_token
*token
= peek ();
3470 if (token
->type
!= CPP_NAME
)
3473 add_predicate (get_ident ());
3478 /* Parse outer control structures.
3479 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3482 parser::parse_pattern ()
3484 /* All clauses start with '('. */
3485 eat_token (CPP_OPEN_PAREN
);
3486 const cpp_token
*token
= peek ();
3487 const char *id
= get_ident ();
3488 if (strcmp (id
, "simplify") == 0)
3490 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3493 else if (strcmp (id
, "match") == 0)
3495 bool with_args
= false;
3496 if (peek ()->type
== CPP_OPEN_PAREN
)
3498 eat_token (CPP_OPEN_PAREN
);
3501 const char *name
= get_ident ();
3502 id_base
*id
= get_operator (name
);
3506 p
= add_predicate (name
);
3507 user_predicates
.safe_push (p
);
3509 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3512 fatal_at (token
, "cannot add a match to a non-predicate ID");
3513 /* Parse (match <id> <arg>... (match-expr)) here. */
3517 capture_ids
= new cid_map_t
;
3519 while (peek ()->type
== CPP_ATSIGN
)
3520 e
->append_op (parse_capture (NULL
));
3521 eat_token (CPP_CLOSE_PAREN
);
3524 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3525 || (!e
&& p
->nargs
!= 0)))
3526 fatal_at (token
, "non-matching number of match operands");
3527 p
->nargs
= e
? e
->ops
.length () : 0;
3528 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3531 else if (strcmp (id
, "for") == 0)
3532 parse_for (token
->src_loc
);
3533 else if (strcmp (id
, "if") == 0)
3534 parse_if (token
->src_loc
);
3535 else if (strcmp (id
, "define_predicates") == 0)
3537 if (active_ifs
.length () > 0
3538 || active_fors
.length () > 0)
3539 fatal_at (token
, "define_predicates inside if or for is not supported");
3540 parse_predicates (token
->src_loc
);
3542 else if (strcmp (id
, "define_operator_list") == 0)
3544 if (active_ifs
.length () > 0
3545 || active_fors
.length () > 0)
3546 fatal_at (token
, "operator-list inside if or for is not supported");
3547 parse_operator_list (token
->src_loc
);
3550 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3551 active_ifs
.length () == 0 && active_fors
.length () == 0
3552 ? "'define_predicates', " : "");
3554 eat_token (CPP_CLOSE_PAREN
);
3557 /* Main entry of the parser. Repeatedly parse outer control structures. */
3559 parser::parser (cpp_reader
*r_
)
3563 active_fors
= vNULL
;
3564 simplifiers
= vNULL
;
3565 oper_lists_set
= NULL
;
3568 user_predicates
= vNULL
;
3569 parsing_match_operand
= false;
3571 const cpp_token
*token
= next ();
3572 while (token
->type
!= CPP_EOF
)
3574 _cpp_backup_tokens (r
, 1);
3581 /* Helper for the linemap code. */
3584 round_alloc_size (size_t s
)
3590 /* The genmatch generator progam. It reads from a pattern description
3591 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3594 main (int argc
, char **argv
)
3598 progname
= "genmatch";
3604 bool verbose
= false;
3605 char *input
= argv
[argc
-1];
3606 for (int i
= 1; i
< argc
- 1; ++i
)
3608 if (strcmp (argv
[i
], "--gimple") == 0)
3610 else if (strcmp (argv
[i
], "--generic") == 0)
3612 else if (strcmp (argv
[i
], "-v") == 0)
3616 fprintf (stderr
, "Usage: genmatch "
3617 "[--gimple] [--generic] [-v] input\n");
3622 line_table
= XCNEW (struct line_maps
);
3623 linemap_init (line_table
, 0);
3624 line_table
->reallocator
= xrealloc
;
3625 line_table
->round_alloc_size
= round_alloc_size
;
3627 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3628 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3629 cb
->error
= error_cb
;
3631 if (!cpp_read_main_file (r
, input
))
3633 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3634 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3636 /* Pre-seed operators. */
3637 operators
= new hash_table
<id_base
> (1024);
3638 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3639 add_operator (SYM, # SYM, # TYPE, NARGS);
3640 #define END_OF_BASE_TREE_CODES
3642 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3643 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3644 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3645 #undef END_OF_BASE_TREE_CODES
3648 /* Pre-seed builtin functions.
3649 ??? Cannot use N (name) as that is targetm.emultls.get_address
3650 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3651 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3652 add_builtin (ENUM, # ENUM);
3653 #include "builtins.def"
3660 write_header (stdout
, "gimple-match-head.c");
3662 write_header (stdout
, "generic-match-head.c");
3664 /* Go over all predicates defined with patterns and perform
3665 lowering and code generation. */
3666 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3668 predicate_id
*pred
= p
.user_predicates
[i
];
3669 lower (pred
->matchers
, gimple
);
3672 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3674 print_operand (pred
->matchers
[i
]->match
);
3675 putc ('\n', stderr
);
3678 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3679 dt
.insert (pred
->matchers
[i
], i
);
3684 write_predicate (stdout
, pred
, dt
, gimple
);
3687 /* Lower the main simplifiers and generate code for them. */
3688 lower (p
.simplifiers
, gimple
);
3691 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3693 print_operand (p
.simplifiers
[i
]->match
);
3694 putc ('\n', stderr
);
3698 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3699 dt
.insert (p
.simplifiers
[i
], i
);
3705 dt
.gen_gimple (stdout
);
3707 dt
.gen_generic (stdout
);
3710 cpp_finish (r
, NULL
);