1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014 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"
38 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
39 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
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, 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 error: ", loc
.file
, loc
.line
, loc
.column
);
65 vfprintf (stderr
, msg
, *ap
);
66 fprintf (stderr
, "\n");
67 FILE *f
= fopen (loc
.file
, "r");
73 if (!fgets (buf
, 128, f
))
75 if (buf
[strlen (buf
) - 1] != '\n')
82 fprintf (stderr
, "%s", buf
);
83 for (int i
= 0; i
< loc
.column
- 1; ++i
)
94 #if GCC_VERSION >= 4001
95 __attribute__((format (printf
, 2, 3)))
97 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
101 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
106 output_line_directive (FILE *f
, source_location location
,
107 bool dumpfile
= false)
110 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
111 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
114 /* When writing to a dumpfile only dump the filename. */
115 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
120 fprintf (f
, "%s:%d", file
, loc
.line
);
123 /* Other gen programs really output line directives here, at least for
124 development it's right now more convenient to have line information
125 from the generated file. Still keep the directives as comment for now
126 to easily back-point to the meta-description. */
127 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
131 /* Pull in tree codes and builtin function codes from their
134 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
144 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
145 enum built_in_function
{
146 #include "builtins.def"
152 /* Base class for all identifiers the parser knows. */
154 struct id_base
: typed_noop_remove
<id_base
>
156 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
158 id_base (id_kind
, const char *, int = -1);
164 /* hash_table support. */
165 typedef id_base value_type
;
166 typedef id_base compare_type
;
167 static inline hashval_t
hash (const value_type
*);
168 static inline int equal (const value_type
*, const compare_type
*);
172 id_base::hash (const value_type
*op
)
178 id_base::equal (const value_type
*op1
,
179 const compare_type
*op2
)
181 return (op1
->hashval
== op2
->hashval
182 && strcmp (op1
->id
, op2
->id
) == 0);
185 /* Hashtable of known pattern operators. This is pre-seeded from
186 all known tree codes and all known builtin function ids. */
187 static hash_table
<id_base
> *operators
;
189 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
194 hashval
= htab_hash_string (id
);
197 /* Identifier that maps to a tree code. */
199 struct operator_id
: public id_base
201 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
203 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
208 /* Identifier that maps to a builtin function code. */
210 struct fn_id
: public id_base
212 fn_id (enum built_in_function fn_
, const char *id_
)
213 : id_base (id_base::FN
, id_
), fn (fn_
) {}
214 enum built_in_function fn
;
219 /* Identifier that maps to a user-defined predicate. */
221 struct predicate_id
: public id_base
223 predicate_id (const char *id_
)
224 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
225 vec
<simplify
*> matchers
;
228 /* Identifier that maps to a operator defined by a 'for' directive. */
230 struct user_id
: public id_base
232 user_id (const char *id_
)
233 : id_base (id_base::USER
, id_
), substitutes (vNULL
) {}
234 vec
<id_base
*> substitutes
;
240 is_a_helper
<fn_id
*>::test (id_base
*id
)
242 return id
->kind
== id_base::FN
;
248 is_a_helper
<operator_id
*>::test (id_base
*id
)
250 return id
->kind
== id_base::CODE
;
256 is_a_helper
<predicate_id
*>::test (id_base
*id
)
258 return id
->kind
== id_base::PREDICATE
;
264 is_a_helper
<user_id
*>::test (id_base
*id
)
266 return id
->kind
== id_base::USER
;
269 /* Add a predicate identifier to the hash. */
271 static predicate_id
*
272 add_predicate (const char *id
)
274 predicate_id
*p
= new predicate_id (id
);
275 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
277 fatal ("duplicate id definition");
282 /* Add a tree code identifier to the hash. */
285 add_operator (enum tree_code code
, const char *id
,
286 const char *tcc
, unsigned nargs
)
288 if (strcmp (tcc
, "tcc_unary") != 0
289 && strcmp (tcc
, "tcc_binary") != 0
290 && strcmp (tcc
, "tcc_comparison") != 0
291 && strcmp (tcc
, "tcc_expression") != 0
292 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
293 && strcmp (tcc
, "tcc_reference") != 0
294 /* To have INTEGER_CST and friends as "predicate operators". */
295 && strcmp (tcc
, "tcc_constant") != 0)
297 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
298 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
300 fatal ("duplicate id definition");
304 /* Add a builtin identifier to the hash. */
307 add_builtin (enum built_in_function code
, const char *id
)
309 fn_id
*fn
= new fn_id (code
, id
);
310 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
312 fatal ("duplicate id definition");
316 /* Helper for easy comparing ID with tree code CODE. */
319 operator==(id_base
&id
, enum tree_code code
)
321 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
322 return oid
->code
== code
;
326 /* Lookup the identifier ID. */
329 get_operator (const char *id
)
331 id_base
tem (id_base::CODE
, id
);
333 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
337 /* Try all-uppercase. */
338 char *id2
= xstrdup (id
);
339 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
340 id2
[i
] = TOUPPER (id2
[i
]);
341 new (&tem
) id_base (id_base::CODE
, id2
);
342 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
349 /* Try _EXPR appended. */
350 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
351 strcat (id2
, "_EXPR");
352 new (&tem
) id_base (id_base::CODE
, id2
);
353 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
364 /* Helper for the capture-id map. */
366 struct capture_id_map_hasher
: default_hashmap_traits
368 static inline hashval_t
hash (const char *);
369 static inline bool equal_keys (const char *, const char *);
373 capture_id_map_hasher::hash (const char *id
)
375 return htab_hash_string (id
);
379 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
381 return strcmp (id1
, id2
) == 0;
384 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
387 /* The AST produced by parsing of the pattern definitions. */
391 /* The base class for operands. */
394 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
395 operand (enum op_type type_
) : type (type_
) {}
397 virtual void gen_transform (FILE *, const char *, bool, int,
398 const char *, dt_operand
** = 0)
399 { gcc_unreachable (); }
402 /* A predicate operand. Predicates are leafs in the AST. */
404 struct predicate
: public operand
406 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
410 /* An operand that constitutes an expression. Expressions include
411 function calls and user-defined predicate invocations. */
413 struct expr
: public operand
415 expr (id_base
*operation_
, bool is_commutative_
= false)
416 : operand (OP_EXPR
), operation (operation_
),
417 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
) {}
418 void append_op (operand
*op
) { ops
.safe_push (op
); }
419 /* The operator and its operands. */
422 /* An explicitely specified type - used exclusively for conversions. */
423 const char *expr_type
;
424 /* Whether the operation is to be applied commutatively. This is
425 later lowered to two separate patterns. */
427 virtual void gen_transform (FILE *f
, const char *, bool, int,
428 const char *, dt_operand
** = 0);
431 /* An operator that is represented by native C code. This is always
432 a leaf operand in the AST. This class is also used to represent
433 the code to be generated for 'if' and 'with' expressions. */
435 struct c_expr
: public operand
437 /* A mapping of an identifier and its replacement. Used to apply
442 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
445 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
446 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
447 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
448 nr_stmts (nr_stmts_
), ids (ids_
) {}
449 /* cpplib tokens and state to transform this back to source. */
452 cid_map_t
*capture_ids
;
453 /* The number of statements parsed (well, the number of ';'s). */
455 /* The identifier replacement vector. */
457 virtual void gen_transform (FILE *f
, const char *, bool, int,
458 const char *, dt_operand
**);
461 /* A wrapper around another operand that captures its value. */
463 struct capture
: public operand
465 capture (unsigned where_
, operand
*what_
)
466 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
467 /* Identifier index for the value. */
469 /* The captured value. */
471 virtual void gen_transform (FILE *f
, const char *, bool, int,
472 const char *, dt_operand
** = 0);
478 is_a_helper
<capture
*>::test (operand
*op
)
480 return op
->type
== operand::OP_CAPTURE
;
486 is_a_helper
<predicate
*>::test (operand
*op
)
488 return op
->type
== operand::OP_PREDICATE
;
494 is_a_helper
<c_expr
*>::test (operand
*op
)
496 return op
->type
== operand::OP_C_EXPR
;
502 is_a_helper
<expr
*>::test (operand
*op
)
504 return op
->type
== operand::OP_EXPR
;
507 /* Helper to distinguish 'if' from 'with' expressions. */
511 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
512 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
513 source_location location
;
518 /* The main class of a pattern and its transform. This is used to
519 represent both (simplify ...) and (match ...) kinds. The AST
520 duplicates all outer 'if' and 'for' expressions here so each
521 simplify can exist in isolation. */
525 simplify (operand
*match_
, source_location match_location_
,
526 struct operand
*result_
, source_location result_location_
,
527 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
528 cid_map_t
*capture_ids_
)
529 : match (match_
), match_location (match_location_
),
530 result (result_
), result_location (result_location_
),
531 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
532 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
534 /* The expression that is matched against the GENERIC or GIMPLE IL. */
536 source_location match_location
;
537 /* For a (simplify ...) the expression produced when the pattern applies.
538 For a (match ...) either NULL if it is a simple predicate or the
539 single expression specifying the matched operands. */
540 struct operand
*result
;
541 source_location result_location
;
542 /* Collected 'if' expressions that need to evaluate to true to make
543 the pattern apply. */
544 vec
<if_or_with
> ifexpr_vec
;
545 /* Collected 'for' expression operators that have to be replaced
546 in the lowering phase. */
547 vec
<vec
<user_id
*> > for_vec
;
548 /* A map of capture identifiers to indexes. */
549 cid_map_t
*capture_ids
;
553 /* Debugging routines for dumping the AST. */
556 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
558 if (capture
*c
= dyn_cast
<capture
*> (o
))
560 fprintf (f
, "@%u", c
->where
);
561 if (c
->what
&& flattened
== false)
564 print_operand (c
->what
, f
, flattened
);
569 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
570 fprintf (f
, "%s", p
->p
->id
);
572 else if (is_a
<c_expr
*> (o
))
573 fprintf (f
, "c_expr");
575 else if (expr
*e
= dyn_cast
<expr
*> (o
))
577 fprintf (f
, "(%s", e
->operation
->id
);
579 if (flattened
== false)
582 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
584 print_operand (e
->ops
[i
], f
, flattened
);
596 print_matches (struct simplify
*s
, FILE *f
= stderr
)
598 fprintf (f
, "for expression: ");
599 print_operand (s
->match
, f
);
606 /* Lowering of commutative operators. */
609 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
610 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
612 if (n
== ops_vector
.length ())
614 vec
<operand
*> xv
= v
.copy ();
615 result
.safe_push (xv
);
619 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
621 v
[n
] = ops_vector
[n
][i
];
622 cartesian_product (ops_vector
, result
, v
, n
+ 1);
626 /* Lower OP to two operands in case it is marked as commutative. */
628 static vec
<operand
*>
629 commutate (operand
*op
)
631 vec
<operand
*> ret
= vNULL
;
633 if (capture
*c
= dyn_cast
<capture
*> (op
))
640 vec
<operand
*> v
= commutate (c
->what
);
641 for (unsigned i
= 0; i
< v
.length (); ++i
)
643 capture
*nc
= new capture (c
->where
, v
[i
]);
649 expr
*e
= dyn_cast
<expr
*> (op
);
650 if (!e
|| e
->ops
.length () == 0)
656 vec
< vec
<operand
*> > ops_vector
= vNULL
;
657 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
658 ops_vector
.safe_push (commutate (e
->ops
[i
]));
660 auto_vec
< vec
<operand
*> > result
;
661 auto_vec
<operand
*> v (e
->ops
.length ());
662 v
.quick_grow_cleared (e
->ops
.length ());
663 cartesian_product (ops_vector
, result
, v
, 0);
666 for (unsigned i
= 0; i
< result
.length (); ++i
)
668 expr
*ne
= new expr (e
->operation
);
669 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
670 ne
->append_op (result
[i
][j
]);
674 if (!e
->is_commutative
)
677 for (unsigned i
= 0; i
< result
.length (); ++i
)
679 expr
*ne
= new expr (e
->operation
);
680 // result[i].length () is 2 since e->operation is binary
681 for (unsigned j
= result
[i
].length (); j
; --j
)
682 ne
->append_op (result
[i
][j
-1]);
689 /* Lower operations marked as commutative in the AST of S and push
690 the resulting patterns to SIMPLIFIERS. */
693 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
695 vec
<operand
*> matchers
= commutate (s
->match
);
696 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
698 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
699 s
->result
, s
->result_location
, s
->ifexpr_vec
,
700 s
->for_vec
, s
->capture_ids
);
701 simplifiers
.safe_push (ns
);
705 /* Strip conditional conversios using operator OPER from O and its
706 children if STRIP, else replace them with an unconditional convert. */
709 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
711 if (capture
*c
= dyn_cast
<capture
*> (o
))
714 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
719 expr
*e
= dyn_cast
<expr
*> (o
);
723 if (*e
->operation
== oper
)
726 return lower_opt_convert (e
->ops
[0], oper
, strip
);
728 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
729 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
733 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
734 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
735 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
740 /* Determine whether O or its children uses the conditional conversion
744 has_opt_convert (operand
*o
, enum tree_code oper
)
746 if (capture
*c
= dyn_cast
<capture
*> (o
))
749 return has_opt_convert (c
->what
, oper
);
754 expr
*e
= dyn_cast
<expr
*> (o
);
758 if (*e
->operation
== oper
)
761 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
762 if (has_opt_convert (e
->ops
[i
], oper
))
768 /* Lower conditional convert operators in O, expanding it to a vector
771 static vec
<operand
*>
772 lower_opt_convert (operand
*o
)
774 vec
<operand
*> v1
= vNULL
, v2
;
778 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
780 /* Conditional converts are lowered to a pattern with the
781 conversion and one without. The three different conditional
782 convert codes are lowered separately. */
784 for (unsigned i
= 0; i
< 3; ++i
)
787 for (unsigned j
= 0; j
< v1
.length (); ++j
)
788 if (has_opt_convert (v1
[j
], opers
[i
]))
790 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
791 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
797 for (unsigned j
= 0; j
< v2
.length (); ++j
)
798 v1
.safe_push (v2
[j
]);
805 /* Lower conditional convert operators in the AST of S and push
806 the resulting multiple patterns to SIMPLIFIERS. */
809 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
811 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
812 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
814 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
815 s
->result
, s
->result_location
, s
->ifexpr_vec
,
816 s
->for_vec
, s
->capture_ids
);
817 simplifiers
.safe_push (ns
);
821 /* In AST operand O replace operator ID with operator WITH. */
824 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
826 /* Deep-copy captures and expressions, replacing operations as
828 if (capture
*c
= dyn_cast
<capture
*> (o
))
832 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
834 else if (expr
*e
= dyn_cast
<expr
*> (o
))
836 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
838 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
839 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
843 /* For c_expr we simply record a string replacement table which is
844 applied at code-generation time. */
845 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
847 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
848 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
849 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
855 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
858 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
860 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
861 unsigned worklist_start
= 0;
862 auto_vec
<simplify
*> worklist
;
863 worklist
.safe_push (sin
);
865 /* Lower each recorded for separately, operating on the
866 set of simplifiers created by the previous one.
867 Lower inner-to-outer so inner for substitutes can refer
868 to operators replaced by outer fors. */
869 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
871 vec
<user_id
*>& ids
= for_vec
[fi
];
872 unsigned n_ids
= ids
.length ();
873 unsigned max_n_opers
= 0;
874 for (unsigned i
= 0; i
< n_ids
; ++i
)
875 if (ids
[i
]->substitutes
.length () > max_n_opers
)
876 max_n_opers
= ids
[i
]->substitutes
.length ();
878 unsigned worklist_end
= worklist
.length ();
879 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
881 simplify
*s
= worklist
[si
];
882 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
884 operand
*match_op
= s
->match
;
885 operand
*result_op
= s
->result
;
886 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
888 for (unsigned i
= 0; i
< n_ids
; ++i
)
890 user_id
*id
= ids
[i
];
891 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
892 match_op
= replace_id (match_op
, id
, oper
);
894 result_op
= replace_id (result_op
, id
, oper
);
895 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
896 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
899 simplify
*ns
= new simplify (match_op
, s
->match_location
,
900 result_op
, s
->result_location
,
901 ifexpr_vec
, vNULL
, s
->capture_ids
);
902 worklist
.safe_push (ns
);
905 worklist_start
= worklist_end
;
908 /* Copy out the result from the last for lowering. */
909 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
910 simplifiers
.safe_push (worklist
[i
]);
913 /* Lower the AST for everything in SIMPLIFIERS. */
916 lower (vec
<simplify
*>& simplifiers
)
918 auto_vec
<simplify
*> out_simplifiers0
;
919 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
920 lower_opt_convert (simplifiers
[i
], out_simplifiers0
);
922 auto_vec
<simplify
*> out_simplifiers1
;
923 for (unsigned i
= 0; i
< out_simplifiers0
.length (); ++i
)
924 lower_commutative (out_simplifiers0
[i
], out_simplifiers1
);
926 simplifiers
.truncate (0);
927 for (unsigned i
= 0; i
< out_simplifiers1
.length (); ++i
)
928 lower_for (out_simplifiers1
[i
], simplifiers
);
934 /* The decision tree built for generating GIMPLE and GENERIC pattern
935 matching code. It represents the 'match' expression of all
936 simplifies and has those as its leafs. */
938 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
942 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
948 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
950 dt_node
*append_node (dt_node
*);
951 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
952 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
953 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
954 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
956 virtual void gen (FILE *, bool) {}
958 void gen_kids (FILE *, bool);
961 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
963 struct dt_operand
: public dt_node
966 dt_operand
*match_dop
;
970 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
971 dt_operand
*parent_
= 0, unsigned pos_
= 0)
972 : dt_node (type
), op (op_
), match_dop (match_dop_
),
973 parent (parent_
), pos (pos_
) {}
975 void gen (FILE *, bool);
976 unsigned gen_predicate (FILE *, const char *, bool);
977 unsigned gen_match_op (FILE *, const char *);
979 unsigned gen_gimple_expr (FILE *);
980 unsigned gen_generic_expr (FILE *, const char *);
982 char *get_name (char *);
983 void gen_opname (char *, unsigned);
986 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
988 struct dt_simplify
: public dt_node
992 dt_operand
**indexes
;
994 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
995 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
996 indexes (indexes_
) {}
998 void gen (FILE *f
, bool);
1004 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1006 return (n
->type
== dt_node::DT_OPERAND
1007 || n
->type
== dt_node::DT_MATCH
);
1010 /* A container for the actual decision tree. */
1012 struct decision_tree
1016 void insert (struct simplify
*, unsigned);
1017 void gen_gimple (FILE *f
= stderr
);
1018 void gen_generic (FILE *f
= stderr
);
1019 void print (FILE *f
= stderr
);
1021 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1023 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1024 unsigned pos
= 0, dt_node
*parent
= 0);
1025 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1026 static bool cmp_node (dt_node
*, dt_node
*);
1027 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1030 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1033 cmp_operand (operand
*o1
, operand
*o2
)
1035 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1038 if (o1
->type
== operand::OP_PREDICATE
)
1040 predicate
*p1
= as_a
<predicate
*>(o1
);
1041 predicate
*p2
= as_a
<predicate
*>(o2
);
1042 return p1
->p
== p2
->p
;
1044 else if (o1
->type
== operand::OP_EXPR
)
1046 expr
*e1
= static_cast<expr
*>(o1
);
1047 expr
*e2
= static_cast<expr
*>(o2
);
1048 return e1
->operation
== e2
->operation
;
1054 /* Compare two decision tree nodes N1 and N2 and return true if they
1058 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1060 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1063 if (n1
== n2
|| n1
->type
== dt_node::DT_TRUE
)
1066 if (n1
->type
== dt_node::DT_OPERAND
)
1067 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1068 (as_a
<dt_operand
*> (n2
))->op
);
1069 else if (n1
->type
== dt_node::DT_MATCH
)
1070 return ((as_a
<dt_operand
*> (n1
))->match_dop
1071 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1075 /* Search OPS for a decision tree node like P and return it if found. */
1078 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1080 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1081 if (decision_tree::cmp_node (ops
[i
], p
))
1087 /* Append N to the decision tree if it there is not already an existing
1091 dt_node::append_node (dt_node
*n
)
1095 kid
= decision_tree::find_node (kids
, n
);
1100 n
->level
= this->level
+ 1;
1102 unsigned len
= kids
.length ();
1104 if (len
> 1 && kids
[len
- 2]->type
== dt_node::DT_TRUE
)
1106 dt_node
*p
= kids
[len
- 2];
1107 kids
[len
- 2] = kids
[len
- 1];
1114 /* Append OP to the decision tree. */
1117 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1119 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1120 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1121 return append_node (n
);
1124 /* Append a DT_TRUE decision tree node. */
1127 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1129 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1130 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1131 return append_node (n
);
1134 /* Append a DT_MATCH decision tree node. */
1137 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1139 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1140 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1141 return append_node (n
);
1144 /* Append S to the decision tree. */
1147 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1148 dt_operand
**indexes
)
1150 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1151 return append_node (n
);
1154 /* Insert O into the decision tree and return the decision tree node found
1158 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1159 unsigned pos
, dt_node
*parent
)
1161 dt_node
*q
, *elm
= 0;
1163 if (capture
*c
= dyn_cast
<capture
*> (o
))
1165 unsigned capt_index
= c
->where
;
1167 if (indexes
[capt_index
] == 0)
1170 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1173 q
= elm
= p
->append_true_op (parent
, pos
);
1176 // get to the last capture
1177 for (operand
*what
= c
->what
;
1178 what
&& is_a
<capture
*> (what
);
1179 c
= as_a
<capture
*> (what
), what
= c
->what
)
1184 unsigned cc_index
= c
->where
;
1185 dt_operand
*match_op
= indexes
[cc_index
];
1187 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1188 elm
= decision_tree::find_node (p
->kids
, &temp
);
1192 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1193 elm
= decision_tree::find_node (p
->kids
, &temp
);
1198 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1199 elm
= decision_tree::find_node (p
->kids
, &temp
);
1203 gcc_assert (elm
->type
== dt_node::DT_TRUE
1204 || elm
->type
== dt_node::DT_OPERAND
1205 || elm
->type
== dt_node::DT_MATCH
);
1206 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1211 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1213 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1218 p
= p
->append_op (o
, parent
, pos
);
1221 if (expr
*e
= dyn_cast
<expr
*>(o
))
1223 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1224 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1230 /* Insert S into the decision tree. */
1233 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1235 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1236 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1237 p
->append_simplify (s
, pattern_no
, indexes
);
1240 /* Debug functions to dump the decision tree. */
1243 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1245 if (p
->type
== dt_node::DT_NODE
)
1246 fprintf (f
, "root");
1250 for (unsigned i
= 0; i
< indent
; i
++)
1253 if (p
->type
== dt_node::DT_OPERAND
)
1255 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1256 print_operand (dop
->op
, f
, true);
1258 else if (p
->type
== dt_node::DT_TRUE
)
1259 fprintf (f
, "true");
1260 else if (p
->type
== dt_node::DT_MATCH
)
1261 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1262 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1264 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1265 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1266 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1267 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1272 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1274 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1275 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1279 decision_tree::print (FILE *f
)
1281 return decision_tree::print_node (root
, f
);
1286 /* Code generation off the decision tree and the refered AST nodes. */
1289 is_conversion (id_base
*op
)
1291 return (*op
== CONVERT_EXPR
1293 || *op
== FLOAT_EXPR
1294 || *op
== FIX_TRUNC_EXPR
1295 || *op
== VIEW_CONVERT_EXPR
);
1298 /* Get the type to be used for generating operands of OP from the
1302 get_operand_type (id_base
*op
, const char *in_type
,
1303 const char *expr_type
,
1304 const char *other_oprnd_type
)
1306 /* Generally operands whose type does not match the type of the
1307 expression generated need to know their types but match and
1308 thus can fall back to 'other_oprnd_type'. */
1309 if (is_conversion (op
))
1310 return other_oprnd_type
;
1311 else if (*op
== REALPART_EXPR
1312 || *op
== IMAGPART_EXPR
)
1313 return other_oprnd_type
;
1314 else if (is_a
<operator_id
*> (op
)
1315 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1316 return other_oprnd_type
;
1319 /* Otherwise all types should match - choose one in order of
1326 return other_oprnd_type
;
1330 /* Generate transform code for an expression. */
1333 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1334 const char *in_type
, dt_operand
**indexes
)
1336 bool conversion_p
= is_conversion (operation
);
1337 const char *type
= expr_type
;
1340 /* If there was a type specification in the pattern use it. */
1342 else if (conversion_p
)
1343 /* For conversions we need to build the expression using the
1344 outer type passed in. */
1346 else if (*operation
== REALPART_EXPR
1347 || *operation
== IMAGPART_EXPR
)
1349 /* __real and __imag use the component type of its operand. */
1350 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1353 else if (is_a
<operator_id
*> (operation
)
1354 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1356 /* comparisons use boolean_type_node (or what gets in), but
1357 their operands need to figure out the types themselves. */
1358 sprintf (optype
, "boolean_type_node");
1363 /* Other operations are of the same type as their first operand. */
1364 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1368 fatal ("two conversions in a row");
1371 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1373 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1374 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1377 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1379 = get_operand_type (operation
, in_type
, expr_type
,
1380 i
== 0 ? NULL
: op0type
);
1381 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, indexes
);
1385 if (*operation
== CONVERT_EXPR
)
1388 opr
= operation
->id
;
1392 /* ??? Have another helper that is like gimple_build but may
1393 fail if seq == NULL. */
1394 fprintf (f
, " if (!seq)\n"
1396 " res = gimple_simplify (%s, %s", opr
, type
);
1397 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1398 fprintf (f
, ", ops%d[%u]", depth
, i
);
1399 fprintf (f
, ", seq, valueize);\n");
1400 fprintf (f
, " if (!res) return false;\n");
1401 fprintf (f
, " }\n");
1402 fprintf (f
, " else\n");
1403 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1405 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1406 fprintf (f
, ", ops%d[%u]", depth
, i
);
1407 fprintf (f
, ", valueize);\n");
1411 if (operation
->kind
== id_base::CODE
)
1412 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1413 ops
.length(), opr
, type
);
1415 fprintf (f
, " res = build_call_expr_loc (loc, "
1416 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1417 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1418 fprintf (f
, ", ops%d[%u]", depth
, i
);
1419 fprintf (f
, ");\n");
1421 fprintf (f
, " %s = res;\n", dest
);
1425 /* Generate code for a c_expr which is either the expression inside
1426 an if statement or a sequence of statements which computes a
1427 result to be stored to DEST. */
1430 c_expr::gen_transform (FILE *f
, const char *dest
,
1431 bool, int, const char *, dt_operand
**)
1433 if (dest
&& nr_stmts
== 1)
1434 fprintf (f
, "%s = ", dest
);
1436 unsigned stmt_nr
= 1;
1437 for (unsigned i
= 0; i
< code
.length (); ++i
)
1439 const cpp_token
*token
= &code
[i
];
1441 /* Replace captures for code-gen. */
1442 if (token
->type
== CPP_ATSIGN
)
1444 const cpp_token
*n
= &code
[i
+1];
1445 if ((n
->type
== CPP_NUMBER
1446 || n
->type
== CPP_NAME
)
1447 && !(n
->flags
& PREV_WHITE
))
1449 if (token
->flags
& PREV_WHITE
)
1452 if (n
->type
== CPP_NUMBER
)
1453 id
= (const char *)n
->val
.str
.text
;
1455 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1456 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1462 if (token
->flags
& PREV_WHITE
)
1465 if (token
->type
== CPP_NAME
)
1467 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1469 for (j
= 0; j
< ids
.length (); ++j
)
1471 if (strcmp (id
, ids
[j
].id
) == 0)
1473 fprintf (f
, "%s", ids
[j
].oper
);
1477 if (j
< ids
.length ())
1481 /* Output the token as string. */
1482 char *tk
= (char *)cpp_token_as_text (r
, token
);
1485 if (token
->type
== CPP_SEMICOLON
)
1488 if (dest
&& stmt_nr
== nr_stmts
)
1489 fprintf (f
, "\n %s = ", dest
);
1496 /* Generate transform code for a capture. */
1499 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1500 const char *in_type
, dt_operand
**indexes
)
1502 if (what
&& is_a
<expr
*> (what
))
1504 if (indexes
[where
] == 0)
1507 sprintf (buf
, "captures[%u]", where
);
1508 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1512 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1515 /* Return the name of the operand representing the decision tree node.
1516 Use NAME as space to generate it. */
1519 dt_operand::get_name (char *name
)
1522 sprintf (name
, "t");
1523 else if (parent
->level
== 1)
1524 sprintf (name
, "op%u", pos
);
1525 else if (parent
->type
== dt_node::DT_MATCH
)
1526 return parent
->get_name (name
);
1528 sprintf (name
, "o%u%u", parent
->level
, pos
);
1532 /* Fill NAME with the operand name at position POS. */
1535 dt_operand::gen_opname (char *name
, unsigned pos
)
1538 sprintf (name
, "op%u", pos
);
1540 sprintf (name
, "o%u%u", level
, pos
);
1543 /* Generate matching code for the decision tree operand which is
1547 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1549 predicate
*p
= as_a
<predicate
*> (op
);
1551 if (p
->p
->matchers
.exists ())
1553 /* If this is a predicate generated from a pattern mangle its
1554 name and pass on the valueize hook. */
1556 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1558 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1561 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1566 /* Generate matching code for the decision tree operand which is
1570 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1572 char match_opname
[20];
1573 match_dop
->get_name (match_opname
);
1574 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1575 opname
, match_opname
, opname
, match_opname
);
1580 /* Generate GIMPLE matching code for the decision tree operand. */
1583 dt_operand::gen_gimple_expr (FILE *f
)
1585 expr
*e
= static_cast<expr
*> (op
);
1586 id_base
*id
= e
->operation
;
1587 unsigned n_ops
= e
->ops
.length ();
1589 for (unsigned i
= 0; i
< n_ops
; ++i
)
1591 char child_opname
[20];
1592 gen_opname (child_opname
, i
);
1594 if (id
->kind
== id_base::CODE
)
1596 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1597 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1599 /* ??? If this is a memory operation we can't (and should not)
1600 match this. The only sensible operand types are
1601 SSA names and invariants. */
1602 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1604 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1605 "|| is_gimple_min_invariant (%s))\n"
1606 "&& (%s = do_valueize (valueize, %s)))\n"
1607 "{\n", child_opname
, child_opname
, child_opname
,
1612 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1613 child_opname
, i
+ 1);
1616 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1618 fprintf (f
, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
1619 child_opname
, child_opname
);
1626 /* Generate GENERIC matching code for the decision tree operand. */
1629 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1631 expr
*e
= static_cast<expr
*> (op
);
1632 unsigned n_ops
= e
->ops
.length ();
1634 for (unsigned i
= 0; i
< n_ops
; ++i
)
1636 char child_opname
[20];
1637 gen_opname (child_opname
, i
);
1639 if (e
->operation
->kind
== id_base::CODE
)
1640 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1641 child_opname
, opname
, i
);
1643 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1644 child_opname
, opname
, i
);
1650 /* Generate matching code for the children of the decision tree node. */
1653 dt_node::gen_kids (FILE *f
, bool gimple
)
1655 auto_vec
<dt_operand
*> gimple_exprs
;
1656 auto_vec
<dt_operand
*> generic_exprs
;
1657 auto_vec
<dt_operand
*> fns
;
1658 auto_vec
<dt_operand
*> generic_fns
;
1659 auto_vec
<dt_operand
*> preds
;
1660 auto_vec
<dt_node
*> others
;
1661 dt_node
*true_operand
= NULL
;
1663 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1665 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1667 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1668 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1670 if (e
->ops
.length () == 0)
1671 generic_exprs
.safe_push (op
);
1672 else if (e
->operation
->kind
== id_base::FN
)
1677 generic_fns
.safe_push (op
);
1679 else if (e
->operation
->kind
== id_base::PREDICATE
)
1680 preds
.safe_push (op
);
1684 gimple_exprs
.safe_push (op
);
1686 generic_exprs
.safe_push (op
);
1689 else if (op
->op
->type
== operand::OP_PREDICATE
)
1690 others
.safe_push (kids
[i
]);
1694 else if (kids
[i
]->type
== dt_node::DT_MATCH
1695 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1696 others
.safe_push (kids
[i
]);
1697 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1698 true_operand
= kids
[i
];
1704 char *kid_opname
= buf
;
1706 unsigned exprs_len
= gimple_exprs
.length ();
1707 unsigned gexprs_len
= generic_exprs
.length ();
1708 unsigned fns_len
= fns
.length ();
1709 unsigned gfns_len
= generic_fns
.length ();
1711 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1714 gimple_exprs
[0]->get_name (kid_opname
);
1716 fns
[0]->get_name (kid_opname
);
1718 generic_fns
[0]->get_name (kid_opname
);
1720 generic_exprs
[0]->get_name (kid_opname
);
1722 fprintf (f
, "switch (TREE_CODE (%s))\n"
1726 if (exprs_len
|| fns_len
)
1728 fprintf (f
, "case SSA_NAME:\n");
1730 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1734 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1735 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1737 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1739 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1740 id_base
*op
= e
->operation
;
1741 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1742 fprintf (f
, "CASE_CONVERT:\n");
1744 fprintf (f
, "case %s:\n", op
->id
);
1746 gimple_exprs
[i
]->gen (f
, true);
1747 fprintf (f
, "break;\n"
1750 fprintf (f
, "default:;\n"
1757 fprintf (f
, "else ");
1759 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1761 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1762 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1765 for (unsigned i
= 0; i
< fns_len
; ++i
)
1767 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1768 fprintf (f
, "case %s:\n"
1769 "{\n", e
->operation
->id
);
1770 fns
[i
]->gen (f
, true);
1771 fprintf (f
, "break;\n"
1775 fprintf (f
, "default:;\n"
1780 fprintf (f
, "break;\n"
1784 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1786 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1787 id_base
*op
= e
->operation
;
1788 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1789 fprintf (f
, "CASE_CONVERT:\n");
1791 fprintf (f
, "case %s:\n", op
->id
);
1793 generic_exprs
[i
]->gen (f
, gimple
);
1794 fprintf (f
, "break;\n"
1800 fprintf (f
, "case CALL_EXPR:\n"
1802 "tree fndecl = get_callee_fndecl (%s);\n"
1803 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1804 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1807 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1809 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1810 gcc_assert (e
->operation
->kind
== id_base::FN
);
1812 fprintf (f
, "case %s:\n"
1813 "{\n", e
->operation
->id
);
1814 generic_fns
[j
]->gen (f
, false);
1815 fprintf (f
, "break;\n"
1819 fprintf (f
, "default:;\n"
1825 /* Close switch (TREE_CODE ()). */
1826 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1827 fprintf (f
, "default:;\n"
1830 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1832 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1833 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1834 preds
[i
]->get_name (kid_opname
);
1835 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1836 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1837 gimple
? "gimple" : "tree",
1838 p
->id
, kid_opname
, kid_opname
,
1839 gimple
? ", valueize" : "");
1841 for (int j
= 0; j
< p
->nargs
; ++j
)
1843 char child_opname
[20];
1844 preds
[i
]->gen_opname (child_opname
, j
);
1845 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1847 preds
[i
]->gen_kids (f
, gimple
);
1851 for (unsigned i
= 0; i
< others
.length (); ++i
)
1852 others
[i
]->gen (f
, gimple
);
1855 true_operand
->gen (f
, gimple
);
1858 /* Generate matching code for the decision tree operand. */
1861 dt_operand::gen (FILE *f
, bool gimple
)
1866 unsigned n_braces
= 0;
1868 if (type
== DT_OPERAND
)
1871 case operand::OP_PREDICATE
:
1872 n_braces
= gen_predicate (f
, opname
, gimple
);
1875 case operand::OP_EXPR
:
1877 n_braces
= gen_gimple_expr (f
);
1879 n_braces
= gen_generic_expr (f
, opname
);
1885 else if (type
== DT_TRUE
)
1887 else if (type
== DT_MATCH
)
1888 n_braces
= gen_match_op (f
, opname
);
1892 gen_kids (f
, gimple
);
1894 for (unsigned i
= 0; i
< n_braces
; ++i
)
1899 /* For GENERIC we have to take care of wrapping multiple-used
1900 expressions with side-effects in save_expr and preserve side-effects
1901 of expressions with omit_one_operand. Analyze captures in
1902 match, result and with expressions and perform early-outs
1903 on the outermost match expression operands for cases we cannot
1908 capture_info (simplify
*s
);
1909 void walk_match (operand
*o
, unsigned toplevel_arg
, bool);
1910 void walk_result (operand
*o
, bool);
1911 void walk_c_expr (c_expr
*);
1917 bool force_no_side_effects_p
;
1918 unsigned long toplevel_msk
;
1919 int result_use_count
;
1922 auto_vec
<cinfo
> info
;
1923 unsigned long force_no_side_effects
;
1926 /* Analyze captures in S. */
1928 capture_info::capture_info (simplify
*s
)
1932 || ((e
= dyn_cast
<expr
*> (s
->result
))
1933 && is_a
<predicate_id
*> (e
->operation
)))
1935 force_no_side_effects
= -1;
1939 force_no_side_effects
= 0;
1940 info
.safe_grow_cleared (s
->capture_max
+ 1);
1941 e
= as_a
<expr
*> (s
->match
);
1942 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1943 walk_match (e
->ops
[i
], i
, false);
1945 walk_result (s
->result
, false);
1947 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1948 if (s
->ifexpr_vec
[i
].is_with
)
1949 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1952 /* Analyze captures in the match expression piece O. */
1955 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
, bool conditional_p
)
1957 if (capture
*c
= dyn_cast
<capture
*> (o
))
1959 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1960 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1961 /* Mark expr (non-leaf) captures and recurse. */
1963 && is_a
<expr
*> (c
->what
))
1965 info
[c
->where
].expr_p
= true;
1966 walk_match (c
->what
, toplevel_arg
, conditional_p
);
1969 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1971 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1973 bool cond_p
= conditional_p
;
1975 && *e
->operation
== COND_EXPR
)
1977 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1978 || *e
->operation
== TRUTH_ORIF_EXPR
)
1980 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
);
1983 else if (is_a
<predicate
*> (o
))
1985 /* Mark non-captured leafs toplevel arg for checking. */
1986 force_no_side_effects
|= 1 << toplevel_arg
;
1992 /* Analyze captures in the result expression piece O. */
1995 capture_info::walk_result (operand
*o
, bool conditional_p
)
1997 if (capture
*c
= dyn_cast
<capture
*> (o
))
1999 info
[c
->where
].result_use_count
++;
2000 /* If we substitute an expression capture we don't know
2001 which captures this will end up using (well, we don't
2002 compute that). Force the uses to be side-effect free
2003 which means forcing the toplevels that reach the
2004 expression side-effect free. */
2005 if (info
[c
->where
].expr_p
)
2006 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
2007 /* Mark CSE capture capture uses as forced to have
2010 && is_a
<expr
*> (c
->what
))
2012 info
[c
->where
].cse_p
= true;
2013 walk_result (c
->what
, true);
2016 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2018 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2020 bool cond_p
= conditional_p
;
2022 && *e
->operation
== COND_EXPR
)
2024 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2025 || *e
->operation
== TRUTH_ORIF_EXPR
)
2027 walk_result (e
->ops
[i
], cond_p
);
2030 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2036 /* Look for captures in the C expr E. */
2039 capture_info::walk_c_expr (c_expr
*e
)
2041 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
2042 unsigned p_depth
= 0;
2043 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2045 const cpp_token
*t
= &e
->code
[i
];
2046 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2047 if (t
->type
== CPP_NAME
2048 && strcmp ((const char *)CPP_HASHNODE
2049 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2050 && n
->type
== CPP_OPEN_PAREN
)
2052 else if (t
->type
== CPP_CLOSE_PAREN
2055 else if (p_depth
== 0
2056 && t
->type
== CPP_ATSIGN
2057 && (n
->type
== CPP_NUMBER
2058 || n
->type
== CPP_NAME
)
2059 && !(n
->flags
& PREV_WHITE
))
2062 if (n
->type
== CPP_NUMBER
)
2063 id
= (const char *)n
->val
.str
.text
;
2065 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2066 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
2072 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2073 step of a '(simplify ...)' or '(match ...)'. This handles everything
2074 that is not part of the decision tree (simplify->match). */
2077 dt_simplify::gen (FILE *f
, bool gimple
)
2080 output_line_directive (f
, s
->result_location
);
2081 if (s
->capture_max
>= 0)
2082 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2083 s
->capture_max
+ 1);
2085 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2089 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2092 unsigned n_braces
= 0;
2093 if (s
->ifexpr_vec
!= vNULL
)
2095 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2097 if_or_with
&w
= s
->ifexpr_vec
[i
];
2101 output_line_directive (f
, w
.location
);
2102 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2107 output_line_directive (f
, w
.location
);
2108 fprintf (f
, "if (");
2109 if (i
== s
->ifexpr_vec
.length () - 1
2110 || s
->ifexpr_vec
[i
+1].is_with
)
2111 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2120 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2124 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2129 while (j
< s
->ifexpr_vec
.length ()
2130 && !s
->ifexpr_vec
[j
].is_with
);
2140 /* Analyze captures and perform early-outs on the incoming arguments
2141 that cover cases we cannot handle. */
2142 capture_info
cinfo (s
);
2146 && !((e
= dyn_cast
<expr
*> (s
->result
))
2147 && is_a
<predicate_id
*> (e
->operation
)))
2149 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2150 if (cinfo
.force_no_side_effects
& (1 << i
))
2151 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2152 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2153 if (cinfo
.info
[i
].cse_p
)
2155 else if (cinfo
.info
[i
].force_no_side_effects_p
2156 && (cinfo
.info
[i
].toplevel_msk
2157 & cinfo
.force_no_side_effects
) == 0)
2158 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2159 "return NULL_TREE;\n", i
);
2160 else if ((cinfo
.info
[i
].toplevel_msk
2161 & cinfo
.force_no_side_effects
) != 0)
2162 /* Mark capture as having no side-effects if we had to verify
2163 that via forced toplevel operand checks. */
2164 cinfo
.info
[i
].force_no_side_effects_p
= true;
2167 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2168 "fprintf (dump_file, \"Applying pattern ");
2169 output_line_directive (f
, s
->result_location
, true);
2170 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2172 operand
*result
= s
->result
;
2175 /* If there is no result then this is a predicate implementation. */
2176 fprintf (f
, "return true;\n");
2180 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2181 in outermost position). */
2182 if (result
->type
== operand::OP_EXPR
2183 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2184 result
= as_a
<expr
*> (result
)->ops
[0];
2185 if (result
->type
== operand::OP_EXPR
)
2187 expr
*e
= as_a
<expr
*> (result
);
2188 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2190 fprintf (f
, "*res_code = %s;\n",
2191 *e
->operation
== CONVERT_EXPR
2192 ? "NOP_EXPR" : e
->operation
->id
);
2193 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2196 snprintf (dest
, 32, " res_ops[%d]", j
);
2198 = get_operand_type (e
->operation
,
2199 "type", e
->expr_type
,
2201 ? NULL
: "TREE_TYPE (res_ops[0])");
2202 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
2205 /* Re-fold the toplevel result. It's basically an embedded
2206 gimple_build w/o actually building the stmt. */
2208 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2209 "res_ops, valueize);\n", e
->ops
.length ());
2211 else if (result
->type
== operand::OP_CAPTURE
2212 || result
->type
== operand::OP_C_EXPR
)
2214 result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
2215 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2219 fprintf (f
, "return true;\n");
2223 bool is_predicate
= false;
2224 if (result
->type
== operand::OP_EXPR
)
2226 expr
*e
= as_a
<expr
*> (result
);
2227 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2228 /* Search for captures used multiple times in the result expression
2229 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2231 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2233 if (!cinfo
.info
[i
].force_no_side_effects_p
2234 && cinfo
.info
[i
].result_use_count
> 1)
2235 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2236 " captures[%d] = save_expr (captures[%d]);\n",
2239 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2243 snprintf (dest
, 32, "res_ops[%d]", j
);
2246 fprintf (f
, " tree res_op%d;\n", j
);
2247 snprintf (dest
, 32, " res_op%d", j
);
2250 = get_operand_type (e
->operation
,
2251 "type", e
->expr_type
,
2253 ? NULL
: "TREE_TYPE (res_op0)");
2254 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2257 fprintf (f
, "return true;\n");
2260 fprintf (f
, " tree res;\n");
2261 /* Re-fold the toplevel result. Use non_lvalue to
2262 build NON_LVALUE_EXPRs so they get properly
2263 ignored when in GIMPLE form. */
2264 if (*e
->operation
== NON_LVALUE_EXPR
)
2265 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2268 if (e
->operation
->kind
== id_base::CODE
)
2269 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2271 *e
->operation
== CONVERT_EXPR
2272 ? "NOP_EXPR" : e
->operation
->id
);
2274 fprintf (f
, " res = build_call_expr_loc "
2275 "(loc, builtin_decl_implicit (%s), %d",
2276 e
->operation
->id
, e
->ops
.length());
2277 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2278 fprintf (f
, ", res_op%d", j
);
2279 fprintf (f
, ");\n");
2283 else if (result
->type
== operand::OP_CAPTURE
2284 || result
->type
== operand::OP_C_EXPR
)
2287 fprintf (f
, " tree res;\n");
2288 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2294 /* Search for captures not used in the result expression and dependent
2295 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2296 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2298 if (!cinfo
.info
[i
].force_no_side_effects_p
2299 && !cinfo
.info
[i
].expr_p
2300 && cinfo
.info
[i
].result_use_count
== 0)
2301 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2302 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2303 " fold_ignored_result (captures[%d]), res);\n",
2306 fprintf (f
, " return res;\n");
2310 for (unsigned i
= 0; i
< n_braces
; ++i
)
2316 /* Main entry to generate code for matching GIMPLE IL off the decision
2320 decision_tree::gen_gimple (FILE *f
)
2322 for (unsigned n
= 1; n
<= 3; ++n
)
2324 fprintf (f
, "\nstatic bool\n"
2325 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2326 " gimple_seq *seq, tree (*valueize)(tree),\n"
2327 " code_helper code, tree type");
2328 for (unsigned i
= 0; i
< n
; ++i
)
2329 fprintf (f
, ", tree op%d", i
);
2333 fprintf (f
, "switch (code.get_rep())\n"
2335 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2337 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2338 expr
*e
= static_cast<expr
*>(dop
->op
);
2339 if (e
->ops
.length () != n
)
2342 if (*e
->operation
== CONVERT_EXPR
2343 || *e
->operation
== NOP_EXPR
)
2344 fprintf (f
, "CASE_CONVERT:\n");
2346 fprintf (f
, "case %s%s:\n",
2347 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2350 dop
->gen_kids (f
, true);
2351 fprintf (f
, "break;\n");
2354 fprintf (f
, "default:;\n"
2357 fprintf (f
, "return false;\n");
2362 /* Main entry to generate code for matching GENERIC IL off the decision
2366 decision_tree::gen_generic (FILE *f
)
2368 for (unsigned n
= 1; n
<= 3; ++n
)
2370 fprintf (f
, "\ntree\n"
2371 "generic_simplify (location_t loc, enum tree_code code, "
2372 "tree type ATTRIBUTE_UNUSED");
2373 for (unsigned i
= 0; i
< n
; ++i
)
2374 fprintf (f
, ", tree op%d", i
);
2378 fprintf (f
, "switch (code)\n"
2380 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2382 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2383 expr
*e
= static_cast<expr
*>(dop
->op
);
2384 if (e
->ops
.length () != n
2385 /* Builtin simplifications are somewhat premature on
2386 GENERIC. The following drops patterns with outermost
2387 calls. It's easy to emit overloads for function code
2388 though if necessary. */
2389 || e
->operation
->kind
!= id_base::CODE
)
2392 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2393 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2394 fprintf (f
, "CASE_CONVERT:\n");
2396 fprintf (f
, "case %s:\n", e
->operation
->id
);
2398 dop
->gen_kids (f
, false);
2399 fprintf (f
, "break;\n"
2402 fprintf (f
, "default:;\n"
2405 fprintf (f
, "return NULL_TREE;\n");
2410 /* Output code to implement the predicate P from the decision tree DT. */
2413 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2415 fprintf (f
, "\nbool\n"
2416 "%s%s (tree t%s%s)\n"
2417 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2418 p
->nargs
> 0 ? ", tree *res_ops" : "",
2419 gimple
? ", tree (*valueize)(tree)" : "");
2420 /* Conveniently make 'type' available. */
2421 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2424 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2425 dt
.root
->gen_kids (f
, gimple
);
2427 fprintf (f
, "return false;\n"
2431 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2434 write_header (FILE *f
, const char *head
)
2436 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2437 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2439 /* Include the header instead of writing it awkwardly quoted here. */
2440 fprintf (f
, "\n#include \"%s\"\n", head
);
2450 parser (cpp_reader
*);
2453 const cpp_token
*next ();
2454 const cpp_token
*peek ();
2455 const cpp_token
*peek_ident (const char * = NULL
);
2456 const cpp_token
*expect (enum cpp_ttype
);
2457 void eat_token (enum cpp_ttype
);
2458 const char *get_string ();
2459 const char *get_ident ();
2460 void eat_ident (const char *);
2461 const char *get_number ();
2463 id_base
*parse_operation ();
2464 operand
*parse_capture (operand
*);
2465 operand
*parse_expr ();
2466 c_expr
*parse_c_expr (cpp_ttype
);
2467 operand
*parse_op ();
2469 void parse_pattern ();
2470 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2472 void parse_for (source_location
);
2473 void parse_if (source_location
);
2474 void parse_predicates (source_location
);
2477 vec
<if_or_with
> active_ifs
;
2478 vec
<vec
<user_id
*> > active_fors
;
2480 cid_map_t
*capture_ids
;
2483 vec
<simplify
*> simplifiers
;
2484 vec
<predicate_id
*> user_predicates
;
2487 /* Lexing helpers. */
2489 /* Read the next non-whitespace token from R. */
2494 const cpp_token
*token
;
2497 token
= cpp_get_token (r
);
2499 while (token
->type
== CPP_PADDING
2500 && token
->type
!= CPP_EOF
);
2504 /* Peek at the next non-whitespace token from R. */
2509 const cpp_token
*token
;
2513 token
= cpp_peek_token (r
, i
++);
2515 while (token
->type
== CPP_PADDING
2516 && token
->type
!= CPP_EOF
);
2517 /* If we peek at EOF this is a fatal error as it leaves the
2518 cpp_reader in unusable state. Assume we really wanted a
2519 token and thus this EOF is unexpected. */
2520 if (token
->type
== CPP_EOF
)
2521 fatal_at (token
, "unexpected end of file");
2525 /* Peek at the next identifier token (or return NULL if the next
2526 token is not an identifier or equal to ID if supplied). */
2529 parser::peek_ident (const char *id
)
2531 const cpp_token
*token
= peek ();
2532 if (token
->type
!= CPP_NAME
)
2538 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2539 if (strcmp (id
, t
) == 0)
2545 /* Read the next token from R and assert it is of type TK. */
2548 parser::expect (enum cpp_ttype tk
)
2550 const cpp_token
*token
= next ();
2551 if (token
->type
!= tk
)
2552 fatal_at (token
, "expected %s, got %s",
2553 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2558 /* Consume the next token from R and assert it is of type TK. */
2561 parser::eat_token (enum cpp_ttype tk
)
2566 /* Read the next token from R and assert it is of type CPP_STRING and
2567 return its value. */
2570 parser::get_string ()
2572 const cpp_token
*token
= expect (CPP_STRING
);
2573 return (const char *)token
->val
.str
.text
;
2576 /* Read the next token from R and assert it is of type CPP_NAME and
2577 return its value. */
2580 parser::get_ident ()
2582 const cpp_token
*token
= expect (CPP_NAME
);
2583 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2586 /* Eat an identifier token with value S from R. */
2589 parser::eat_ident (const char *s
)
2591 const cpp_token
*token
= peek ();
2592 const char *t
= get_ident ();
2593 if (strcmp (s
, t
) != 0)
2594 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2597 /* Read the next token from R and assert it is of type CPP_NUMBER and
2598 return its value. */
2601 parser::get_number ()
2603 const cpp_token
*token
= expect (CPP_NUMBER
);
2604 return (const char *)token
->val
.str
.text
;
2608 /* Parse the operator ID, special-casing convert?, convert1? and
2612 parser::parse_operation ()
2614 const cpp_token
*id_tok
= peek ();
2615 const char *id
= get_ident ();
2616 const cpp_token
*token
= peek ();
2617 if (strcmp (id
, "convert0") == 0)
2618 fatal_at (id_tok
, "use 'convert?' here");
2619 if (token
->type
== CPP_QUERY
2620 && !(token
->flags
& PREV_WHITE
))
2622 if (strcmp (id
, "convert") == 0)
2624 else if (strcmp (id
, "convert1") == 0)
2626 else if (strcmp (id
, "convert2") == 0)
2629 fatal_at (id_tok
, "non-convert operator conditionalized");
2630 eat_token (CPP_QUERY
);
2632 else if (strcmp (id
, "convert1") == 0
2633 || strcmp (id
, "convert2") == 0)
2634 fatal_at (id_tok
, "expected '?' after conditional operator");
2635 id_base
*op
= get_operator (id
);
2637 fatal_at (id_tok
, "unknown operator %s", id
);
2642 capture = '@'<number> */
2645 parser::parse_capture (operand
*op
)
2647 eat_token (CPP_ATSIGN
);
2648 const cpp_token
*token
= peek ();
2650 if (token
->type
== CPP_NUMBER
)
2652 else if (token
->type
== CPP_NAME
)
2655 fatal_at (token
, "expected number or identifier");
2656 unsigned next_id
= capture_ids
->elements ();
2658 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2661 return new capture (num
, op
);
2664 /* Parse an expression
2665 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2668 parser::parse_expr ()
2670 expr
*e
= new expr (parse_operation ());
2671 const cpp_token
*token
= peek ();
2673 bool is_commutative
= false;
2674 const char *expr_type
= NULL
;
2676 if (token
->type
== CPP_COLON
2677 && !(token
->flags
& PREV_WHITE
))
2679 eat_token (CPP_COLON
);
2681 if (token
->type
== CPP_NAME
2682 && !(token
->flags
& PREV_WHITE
))
2684 const char *s
= get_ident ();
2685 if (s
[0] == 'c' && !s
[1])
2686 is_commutative
= true;
2687 else if (s
[1] != '\0')
2690 fatal_at (token
, "flag %s not recognized", s
);
2694 fatal_at (token
, "expected flag or type specifying identifier");
2697 if (token
->type
== CPP_ATSIGN
2698 && !(token
->flags
& PREV_WHITE
))
2699 op
= parse_capture (e
);
2704 const cpp_token
*token
= peek ();
2705 if (token
->type
== CPP_CLOSE_PAREN
)
2707 if (e
->operation
->nargs
!= -1
2708 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2709 fatal_at (token
, "'%s' expects %u operands, not %u",
2710 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2713 if (e
->ops
.length () == 2)
2714 e
->is_commutative
= true;
2716 fatal_at (token
, "only binary operators or function with "
2717 "two arguments can be marked commutative");
2719 e
->expr_type
= expr_type
;
2722 e
->append_op (parse_op ());
2727 /* Lex native C code delimited by START recording the preprocessing tokens
2728 for later processing.
2729 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2732 parser::parse_c_expr (cpp_ttype start
)
2734 const cpp_token
*token
;
2737 vec
<cpp_token
> code
= vNULL
;
2738 unsigned nr_stmts
= 0;
2740 if (start
== CPP_OPEN_PAREN
)
2741 end
= CPP_CLOSE_PAREN
;
2742 else if (start
== CPP_OPEN_BRACE
)
2743 end
= CPP_CLOSE_BRACE
;
2751 /* Count brace pairs to find the end of the expr to match. */
2752 if (token
->type
== start
)
2754 else if (token
->type
== end
2758 /* This is a lame way of counting the number of statements. */
2759 if (token
->type
== CPP_SEMICOLON
)
2762 /* Record the token. */
2763 code
.safe_push (*token
);
2766 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2769 /* Parse an operand which is either an expression, a predicate or
2770 a standalone capture.
2771 op = predicate | expr | c_expr | capture */
2776 const cpp_token
*token
= peek ();
2777 struct operand
*op
= NULL
;
2778 if (token
->type
== CPP_OPEN_PAREN
)
2780 eat_token (CPP_OPEN_PAREN
);
2782 eat_token (CPP_CLOSE_PAREN
);
2784 else if (token
->type
== CPP_OPEN_BRACE
)
2786 op
= parse_c_expr (CPP_OPEN_BRACE
);
2790 /* Remaining ops are either empty or predicates */
2791 if (token
->type
== CPP_NAME
)
2793 const char *id
= get_ident ();
2794 id_base
*opr
= get_operator (id
);
2796 fatal_at (token
, "expected predicate name");
2797 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2799 if (code
->nargs
!= 0)
2800 fatal_at (token
, "using an operator with operands as predicate");
2801 /* Parse the zero-operand operator "predicates" as
2803 op
= new expr (opr
);
2805 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2806 op
= new predicate (p
);
2808 fatal_at (token
, "using an unsupported operator as predicate");
2810 if (token
->flags
& PREV_WHITE
)
2813 else if (token
->type
!= CPP_COLON
2814 && token
->type
!= CPP_ATSIGN
)
2815 fatal_at (token
, "expected expression or predicate");
2816 /* optionally followed by a capture and a predicate. */
2817 if (token
->type
== CPP_COLON
)
2818 fatal_at (token
, "not implemented: predicate on leaf operand");
2819 if (token
->type
== CPP_ATSIGN
)
2820 op
= parse_capture (op
);
2827 simplify = 'simplify' <expr> <result-op>
2829 match = 'match' <ident> <expr> [<result-op>]
2831 <result-op> = <op> | <if> | <with>
2832 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2833 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2834 and fill SIMPLIFIERS with the results. */
2837 parser::parse_simplify (source_location match_location
,
2838 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2841 /* Reset the capture map. */
2842 capture_ids
= new cid_map_t
;
2844 const cpp_token
*loc
= peek ();
2845 struct operand
*match
= parse_op ();
2846 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2847 fatal_at (loc
, "outermost expression cannot be captured");
2848 if (match
->type
== operand::OP_EXPR
2849 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2850 fatal_at (loc
, "outermost expression cannot be a predicate");
2852 const cpp_token
*token
= peek ();
2854 /* If this if is immediately closed then it is part of a predicate
2855 definition. Push it. */
2856 if (token
->type
== CPP_CLOSE_PAREN
)
2859 fatal_at (token
, "expected transform expression");
2860 simplifiers
.safe_push
2861 (new simplify (match
, match_location
, result
, token
->src_loc
,
2862 active_ifs
.copy (), active_fors
.copy (),
2867 unsigned active_ifs_len
= active_ifs
.length ();
2870 if (token
->type
== CPP_OPEN_PAREN
)
2872 source_location paren_loc
= token
->src_loc
;
2873 eat_token (CPP_OPEN_PAREN
);
2874 if (peek_ident ("if"))
2877 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2878 token
->src_loc
, false));
2879 /* If this if is immediately closed then it contains a
2880 manual matcher or is part of a predicate definition.
2882 if (peek ()->type
== CPP_CLOSE_PAREN
)
2885 fatal_at (token
, "manual transform not implemented");
2886 simplifiers
.safe_push
2887 (new simplify (match
, match_location
, result
,
2888 paren_loc
, active_ifs
.copy (),
2889 active_fors
.copy (), capture_ids
));
2892 else if (peek_ident ("with"))
2895 /* Parse (with c-expr expr) as (if-with (true) expr). */
2896 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2898 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2902 operand
*op
= result
;
2905 simplifiers
.safe_push
2906 (new simplify (match
, match_location
, op
,
2907 token
->src_loc
, active_ifs
.copy (),
2908 active_fors
.copy (), capture_ids
));
2909 eat_token (CPP_CLOSE_PAREN
);
2910 /* A "default" result closes the enclosing scope. */
2911 if (active_ifs
.length () > active_ifs_len
)
2913 eat_token (CPP_CLOSE_PAREN
);
2920 else if (token
->type
== CPP_CLOSE_PAREN
)
2922 /* Close a scope if requested. */
2923 if (active_ifs
.length () > active_ifs_len
)
2925 eat_token (CPP_CLOSE_PAREN
);
2935 fatal_at (token
, "expected match operand expression");
2936 simplifiers
.safe_push
2937 (new simplify (match
, match_location
,
2938 matcher
? result
: parse_op (),
2939 token
->src_loc
, active_ifs
.copy (),
2940 active_fors
.copy (), capture_ids
));
2941 /* A "default" result closes the enclosing scope. */
2942 if (active_ifs
.length () > active_ifs_len
)
2944 eat_token (CPP_CLOSE_PAREN
);
2954 /* Parsing of the outer control structures. */
2956 /* Parse a for expression
2957 for = '(' 'for' <subst>... <pattern> ')'
2958 subst = <ident> '(' <ident>... ')' */
2961 parser::parse_for (source_location
)
2963 vec
<user_id
*> user_ids
= vNULL
;
2964 const cpp_token
*token
;
2965 unsigned min_n_opers
= 0, max_n_opers
= 0;
2969 token
= peek_ident ();
2973 /* Insert the user defined operators into the operator hash. */
2974 const char *id
= get_ident ();
2975 user_id
*op
= new user_id (id
);
2976 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2978 fatal_at (token
, "operator already defined");
2980 user_ids
.safe_push (op
);
2982 eat_token (CPP_OPEN_PAREN
);
2985 while ((token
= peek_ident ()) != 0)
2987 const char *oper
= get_ident ();
2988 id_base
*idb
= get_operator (oper
);
2990 fatal_at (token
, "no such operator '%s'", oper
);
2991 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2992 fatal_at (token
, "conditional operators cannot be used inside for");
2996 else if (idb
->nargs
== -1)
2998 else if (idb
->nargs
!= arity
)
2999 fatal_at (token
, "operator '%s' with arity %d does not match "
3000 "others with arity %d", oper
, idb
->nargs
, arity
);
3002 op
->substitutes
.safe_push (idb
);
3005 token
= expect (CPP_CLOSE_PAREN
);
3007 unsigned nsubstitutes
= op
->substitutes
.length ();
3008 if (nsubstitutes
== 0)
3009 fatal_at (token
, "A user-defined operator must have at least "
3010 "one substitution");
3011 if (max_n_opers
== 0)
3013 min_n_opers
= nsubstitutes
;
3014 max_n_opers
= nsubstitutes
;
3018 if (nsubstitutes
% min_n_opers
!= 0
3019 && min_n_opers
% nsubstitutes
!= 0)
3020 fatal_at (token
, "All user-defined identifiers must have a "
3021 "multiple number of operator substitutions of the "
3022 "smallest number of substitutions");
3023 if (nsubstitutes
< min_n_opers
)
3024 min_n_opers
= nsubstitutes
;
3025 else if (nsubstitutes
> max_n_opers
)
3026 max_n_opers
= nsubstitutes
;
3030 unsigned n_ids
= user_ids
.length ();
3032 fatal_at (token
, "for requires at least one user-defined identifier");
3035 if (token
->type
== CPP_CLOSE_PAREN
)
3036 fatal_at (token
, "no pattern defined in for");
3038 active_fors
.safe_push (user_ids
);
3042 if (token
->type
== CPP_CLOSE_PAREN
)
3048 /* Remove user-defined operators from the hash again. */
3049 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3050 operators
->remove_elt (user_ids
[i
]);
3053 /* Parse an outer if expression.
3054 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3057 parser::parse_if (source_location loc
)
3059 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3061 const cpp_token
*token
= peek ();
3062 if (token
->type
== CPP_CLOSE_PAREN
)
3063 fatal_at (token
, "no pattern defined in if");
3065 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3068 const cpp_token
*token
= peek ();
3069 if (token
->type
== CPP_CLOSE_PAREN
)
3077 /* Parse a list of predefined predicate identifiers.
3078 preds = '(' 'define_predicates' <ident>... ')' */
3081 parser::parse_predicates (source_location
)
3085 const cpp_token
*token
= peek ();
3086 if (token
->type
!= CPP_NAME
)
3089 add_predicate (get_ident ());
3094 /* Parse outer control structures.
3095 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3098 parser::parse_pattern ()
3100 /* All clauses start with '('. */
3101 eat_token (CPP_OPEN_PAREN
);
3102 const cpp_token
*token
= peek ();
3103 const char *id
= get_ident ();
3104 if (strcmp (id
, "simplify") == 0)
3105 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3106 else if (strcmp (id
, "match") == 0)
3108 bool with_args
= false;
3109 if (peek ()->type
== CPP_OPEN_PAREN
)
3111 eat_token (CPP_OPEN_PAREN
);
3114 const char *name
= get_ident ();
3115 id_base
*id
= get_operator (name
);
3119 p
= add_predicate (name
);
3120 user_predicates
.safe_push (p
);
3122 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3125 fatal_at (token
, "cannot add a match to a non-predicate ID");
3126 /* Parse (match <id> <arg>... (match-expr)) here. */
3131 while (peek ()->type
== CPP_ATSIGN
)
3132 e
->append_op (parse_capture (NULL
));
3133 eat_token (CPP_CLOSE_PAREN
);
3136 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3137 || (!e
&& p
->nargs
!= 0)))
3138 fatal_at (token
, "non-matching number of match operands");
3139 p
->nargs
= e
? e
->ops
.length () : 0;
3140 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3142 else if (strcmp (id
, "for") == 0)
3143 parse_for (token
->src_loc
);
3144 else if (strcmp (id
, "if") == 0)
3145 parse_if (token
->src_loc
);
3146 else if (strcmp (id
, "define_predicates") == 0)
3148 if (active_ifs
.length () > 0
3149 || active_fors
.length () > 0)
3150 fatal_at (token
, "define_predicates inside if or for is not supported");
3151 parse_predicates (token
->src_loc
);
3154 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3155 active_ifs
.length () == 0 && active_fors
.length () == 0
3156 ? "'define_predicates', " : "");
3158 eat_token (CPP_CLOSE_PAREN
);
3161 /* Main entry of the parser. Repeatedly parse outer control structures. */
3163 parser::parser (cpp_reader
*r_
)
3167 active_fors
= vNULL
;
3168 simplifiers
= vNULL
;
3169 user_predicates
= vNULL
;
3171 const cpp_token
*token
= next ();
3172 while (token
->type
!= CPP_EOF
)
3174 _cpp_backup_tokens (r
, 1);
3181 /* Helper for the linemap code. */
3184 round_alloc_size (size_t s
)
3190 /* The genmatch generator progam. It reads from a pattern description
3191 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3194 main (int argc
, char **argv
)
3198 progname
= "genmatch";
3204 bool verbose
= false;
3205 char *input
= argv
[argc
-1];
3206 for (int i
= 1; i
< argc
- 1; ++i
)
3208 if (strcmp (argv
[i
], "--gimple") == 0)
3210 else if (strcmp (argv
[i
], "--generic") == 0)
3212 else if (strcmp (argv
[i
], "-v") == 0)
3216 fprintf (stderr
, "Usage: genmatch "
3217 "[--gimple] [--generic] [-v] input\n");
3222 line_table
= XCNEW (struct line_maps
);
3223 linemap_init (line_table
, 0);
3224 line_table
->reallocator
= xrealloc
;
3225 line_table
->round_alloc_size
= round_alloc_size
;
3227 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3228 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3229 cb
->error
= error_cb
;
3231 if (!cpp_read_main_file (r
, input
))
3233 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3234 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3236 /* Pre-seed operators. */
3237 operators
= new hash_table
<id_base
> (1024);
3238 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3239 add_operator (SYM, # SYM, # TYPE, NARGS);
3240 #define END_OF_BASE_TREE_CODES
3242 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3243 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3244 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3245 #undef END_OF_BASE_TREE_CODES
3248 /* Pre-seed builtin functions.
3249 ??? Cannot use N (name) as that is targetm.emultls.get_address
3250 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3251 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3252 add_builtin (ENUM, # ENUM);
3253 #include "builtins.def"
3260 write_header (stdout
, "gimple-match-head.c");
3262 write_header (stdout
, "generic-match-head.c");
3264 /* Go over all predicates defined with patterns and perform
3265 lowering and code generation. */
3266 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3268 predicate_id
*pred
= p
.user_predicates
[i
];
3269 lower (pred
->matchers
);
3272 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3273 print_matches (pred
->matchers
[i
]);
3276 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3277 dt
.insert (pred
->matchers
[i
], i
);
3282 write_predicate (stdout
, pred
, dt
, gimple
);
3285 /* Lower the main simplifiers and generate code for them. */
3286 lower (p
.simplifiers
);
3289 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3290 print_matches (p
.simplifiers
[i
]);
3293 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3294 dt
.insert (p
.simplifiers
[i
], i
);
3300 dt
.gen_gimple (stdout
);
3302 dt
.gen_generic (stdout
);
3305 cpp_finish (r
, NULL
);