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_
= 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 if (s
->match
->type
!= operand::OP_EXPR
)
1238 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1239 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1240 p
->append_simplify (s
, pattern_no
, indexes
);
1243 /* Debug functions to dump the decision tree. */
1246 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1248 if (p
->type
== dt_node::DT_NODE
)
1249 fprintf (f
, "root");
1253 for (unsigned i
= 0; i
< indent
; i
++)
1256 if (p
->type
== dt_node::DT_OPERAND
)
1258 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1259 print_operand (dop
->op
, f
, true);
1261 else if (p
->type
== dt_node::DT_TRUE
)
1262 fprintf (f
, "true");
1263 else if (p
->type
== dt_node::DT_MATCH
)
1264 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1265 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1267 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1268 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1269 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1270 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1275 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1277 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1278 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1282 decision_tree::print (FILE *f
)
1284 return decision_tree::print_node (root
, f
);
1289 /* Code generation off the decision tree and the refered AST nodes. */
1292 is_conversion (id_base
*op
)
1294 return (*op
== CONVERT_EXPR
1296 || *op
== FLOAT_EXPR
1297 || *op
== FIX_TRUNC_EXPR
1298 || *op
== VIEW_CONVERT_EXPR
);
1301 /* Get the type to be used for generating operands of OP from the
1305 get_operand_type (id_base
*op
, const char *in_type
,
1306 const char *expr_type
,
1307 const char *other_oprnd_type
)
1309 /* Generally operands whose type does not match the type of the
1310 expression generated need to know their types but match and
1311 thus can fall back to 'other_oprnd_type'. */
1312 if (is_conversion (op
))
1313 return other_oprnd_type
;
1314 else if (*op
== REALPART_EXPR
1315 || *op
== IMAGPART_EXPR
)
1316 return other_oprnd_type
;
1317 else if (is_a
<operator_id
*> (op
)
1318 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1319 return other_oprnd_type
;
1322 /* Otherwise all types should match - choose one in order of
1329 return other_oprnd_type
;
1333 /* Generate transform code for an expression. */
1336 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1337 const char *in_type
, dt_operand
**indexes
)
1339 bool conversion_p
= is_conversion (operation
);
1340 const char *type
= expr_type
;
1343 /* If there was a type specification in the pattern use it. */
1345 else if (conversion_p
)
1346 /* For conversions we need to build the expression using the
1347 outer type passed in. */
1349 else if (*operation
== REALPART_EXPR
1350 || *operation
== IMAGPART_EXPR
)
1352 /* __real and __imag use the component type of its operand. */
1353 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1356 else if (is_a
<operator_id
*> (operation
)
1357 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1359 /* comparisons use boolean_type_node (or what gets in), but
1360 their operands need to figure out the types themselves. */
1361 sprintf (optype
, "boolean_type_node");
1366 /* Other operations are of the same type as their first operand. */
1367 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1371 fatal ("two conversions in a row");
1374 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1376 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1377 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1380 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1382 = get_operand_type (operation
, in_type
, expr_type
,
1383 i
== 0 ? NULL
: op0type
);
1384 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, indexes
);
1388 if (*operation
== CONVERT_EXPR
)
1391 opr
= operation
->id
;
1395 /* ??? Have another helper that is like gimple_build but may
1396 fail if seq == NULL. */
1397 fprintf (f
, " if (!seq)\n"
1399 " res = gimple_simplify (%s, %s", opr
, type
);
1400 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1401 fprintf (f
, ", ops%d[%u]", depth
, i
);
1402 fprintf (f
, ", seq, valueize);\n");
1403 fprintf (f
, " if (!res) return false;\n");
1404 fprintf (f
, " }\n");
1405 fprintf (f
, " else\n");
1406 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1408 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1409 fprintf (f
, ", ops%d[%u]", depth
, i
);
1410 fprintf (f
, ", valueize);\n");
1414 if (operation
->kind
== id_base::CODE
)
1415 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1416 ops
.length(), opr
, type
);
1418 fprintf (f
, " res = build_call_expr_loc (loc, "
1419 "builtin_decl_implicit (%s), %d", opr
, ops
.length());
1420 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1421 fprintf (f
, ", ops%d[%u]", depth
, i
);
1422 fprintf (f
, ");\n");
1424 fprintf (f
, " %s = res;\n", dest
);
1428 /* Generate code for a c_expr which is either the expression inside
1429 an if statement or a sequence of statements which computes a
1430 result to be stored to DEST. */
1433 c_expr::gen_transform (FILE *f
, const char *dest
,
1434 bool, int, const char *, dt_operand
**)
1436 if (dest
&& nr_stmts
== 1)
1437 fprintf (f
, "%s = ", dest
);
1439 unsigned stmt_nr
= 1;
1440 for (unsigned i
= 0; i
< code
.length (); ++i
)
1442 const cpp_token
*token
= &code
[i
];
1444 /* Replace captures for code-gen. */
1445 if (token
->type
== CPP_ATSIGN
)
1447 const cpp_token
*n
= &code
[i
+1];
1448 if ((n
->type
== CPP_NUMBER
1449 || n
->type
== CPP_NAME
)
1450 && !(n
->flags
& PREV_WHITE
))
1452 if (token
->flags
& PREV_WHITE
)
1455 if (n
->type
== CPP_NUMBER
)
1456 id
= (const char *)n
->val
.str
.text
;
1458 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1459 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1465 if (token
->flags
& PREV_WHITE
)
1468 if (token
->type
== CPP_NAME
)
1470 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1472 for (j
= 0; j
< ids
.length (); ++j
)
1474 if (strcmp (id
, ids
[j
].id
) == 0)
1476 fprintf (f
, "%s", ids
[j
].oper
);
1480 if (j
< ids
.length ())
1484 /* Output the token as string. */
1485 char *tk
= (char *)cpp_token_as_text (r
, token
);
1488 if (token
->type
== CPP_SEMICOLON
)
1491 if (dest
&& stmt_nr
== nr_stmts
)
1492 fprintf (f
, "\n %s = ", dest
);
1499 /* Generate transform code for a capture. */
1502 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1503 const char *in_type
, dt_operand
**indexes
)
1505 if (what
&& is_a
<expr
*> (what
))
1507 if (indexes
[where
] == 0)
1510 sprintf (buf
, "captures[%u]", where
);
1511 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1515 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1518 /* Return the name of the operand representing the decision tree node.
1519 Use NAME as space to generate it. */
1522 dt_operand::get_name (char *name
)
1525 sprintf (name
, "t");
1526 else if (parent
->level
== 1)
1527 sprintf (name
, "op%u", pos
);
1528 else if (parent
->type
== dt_node::DT_MATCH
)
1529 return parent
->get_name (name
);
1531 sprintf (name
, "o%u%u", parent
->level
, pos
);
1535 /* Fill NAME with the operand name at position POS. */
1538 dt_operand::gen_opname (char *name
, unsigned pos
)
1541 sprintf (name
, "op%u", pos
);
1543 sprintf (name
, "o%u%u", level
, pos
);
1546 /* Generate matching code for the decision tree operand which is
1550 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1552 predicate
*p
= as_a
<predicate
*> (op
);
1554 if (p
->p
->matchers
.exists ())
1556 /* If this is a predicate generated from a pattern mangle its
1557 name and pass on the valueize hook. */
1559 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1561 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1564 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1569 /* Generate matching code for the decision tree operand which is
1573 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1575 char match_opname
[20];
1576 match_dop
->get_name (match_opname
);
1577 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1578 opname
, match_opname
, opname
, match_opname
);
1583 /* Generate GIMPLE matching code for the decision tree operand. */
1586 dt_operand::gen_gimple_expr (FILE *f
)
1588 expr
*e
= static_cast<expr
*> (op
);
1589 id_base
*id
= e
->operation
;
1590 unsigned n_ops
= e
->ops
.length ();
1592 for (unsigned i
= 0; i
< n_ops
; ++i
)
1594 char child_opname
[20];
1595 gen_opname (child_opname
, i
);
1597 if (id
->kind
== id_base::CODE
)
1599 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1600 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1602 /* ??? If this is a memory operation we can't (and should not)
1603 match this. The only sensible operand types are
1604 SSA names and invariants. */
1605 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1607 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1608 "|| is_gimple_min_invariant (%s))\n"
1609 "&& (%s = do_valueize (valueize, %s)))\n"
1610 "{\n", child_opname
, child_opname
, child_opname
,
1615 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1616 child_opname
, i
+ 1);
1619 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1621 fprintf (f
, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
1622 child_opname
, child_opname
);
1629 /* Generate GENERIC matching code for the decision tree operand. */
1632 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1634 expr
*e
= static_cast<expr
*> (op
);
1635 unsigned n_ops
= e
->ops
.length ();
1637 for (unsigned i
= 0; i
< n_ops
; ++i
)
1639 char child_opname
[20];
1640 gen_opname (child_opname
, i
);
1642 if (e
->operation
->kind
== id_base::CODE
)
1643 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1644 child_opname
, opname
, i
);
1646 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1647 child_opname
, opname
, i
);
1653 /* Generate matching code for the children of the decision tree node. */
1656 dt_node::gen_kids (FILE *f
, bool gimple
)
1658 auto_vec
<dt_operand
*> gimple_exprs
;
1659 auto_vec
<dt_operand
*> generic_exprs
;
1660 auto_vec
<dt_operand
*> fns
;
1661 auto_vec
<dt_operand
*> generic_fns
;
1662 auto_vec
<dt_operand
*> preds
;
1663 auto_vec
<dt_node
*> others
;
1664 dt_node
*true_operand
= NULL
;
1666 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1668 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1670 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1671 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1673 if (e
->ops
.length () == 0)
1674 generic_exprs
.safe_push (op
);
1675 else if (e
->operation
->kind
== id_base::FN
)
1680 generic_fns
.safe_push (op
);
1682 else if (e
->operation
->kind
== id_base::PREDICATE
)
1683 preds
.safe_push (op
);
1687 gimple_exprs
.safe_push (op
);
1689 generic_exprs
.safe_push (op
);
1692 else if (op
->op
->type
== operand::OP_PREDICATE
)
1693 others
.safe_push (kids
[i
]);
1697 else if (kids
[i
]->type
== dt_node::DT_MATCH
1698 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1699 others
.safe_push (kids
[i
]);
1700 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1701 true_operand
= kids
[i
];
1707 char *kid_opname
= buf
;
1709 unsigned exprs_len
= gimple_exprs
.length ();
1710 unsigned gexprs_len
= generic_exprs
.length ();
1711 unsigned fns_len
= fns
.length ();
1712 unsigned gfns_len
= generic_fns
.length ();
1714 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1717 gimple_exprs
[0]->get_name (kid_opname
);
1719 fns
[0]->get_name (kid_opname
);
1721 generic_fns
[0]->get_name (kid_opname
);
1723 generic_exprs
[0]->get_name (kid_opname
);
1725 fprintf (f
, "switch (TREE_CODE (%s))\n"
1729 if (exprs_len
|| fns_len
)
1731 fprintf (f
, "case SSA_NAME:\n");
1733 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1737 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1738 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1740 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1742 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1743 id_base
*op
= e
->operation
;
1744 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1745 fprintf (f
, "CASE_CONVERT:\n");
1747 fprintf (f
, "case %s:\n", op
->id
);
1749 gimple_exprs
[i
]->gen (f
, true);
1750 fprintf (f
, "break;\n"
1753 fprintf (f
, "default:;\n"
1760 fprintf (f
, "else ");
1762 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1764 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1765 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1768 for (unsigned i
= 0; i
< fns_len
; ++i
)
1770 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1771 fprintf (f
, "case %s:\n"
1772 "{\n", e
->operation
->id
);
1773 fns
[i
]->gen (f
, true);
1774 fprintf (f
, "break;\n"
1778 fprintf (f
, "default:;\n"
1783 fprintf (f
, "break;\n"
1787 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1789 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1790 id_base
*op
= e
->operation
;
1791 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1792 fprintf (f
, "CASE_CONVERT:\n");
1794 fprintf (f
, "case %s:\n", op
->id
);
1796 generic_exprs
[i
]->gen (f
, gimple
);
1797 fprintf (f
, "break;\n"
1803 fprintf (f
, "case CALL_EXPR:\n"
1805 "tree fndecl = get_callee_fndecl (%s);\n"
1806 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1807 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1810 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1812 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1813 gcc_assert (e
->operation
->kind
== id_base::FN
);
1815 fprintf (f
, "case %s:\n"
1816 "{\n", e
->operation
->id
);
1817 generic_fns
[j
]->gen (f
, false);
1818 fprintf (f
, "break;\n"
1822 fprintf (f
, "default:;\n"
1828 /* Close switch (TREE_CODE ()). */
1829 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1830 fprintf (f
, "default:;\n"
1833 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1835 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1836 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1837 preds
[i
]->get_name (kid_opname
);
1838 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1839 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1840 gimple
? "gimple" : "tree",
1841 p
->id
, kid_opname
, kid_opname
,
1842 gimple
? ", valueize" : "");
1844 for (int j
= 0; j
< p
->nargs
; ++j
)
1846 char child_opname
[20];
1847 preds
[i
]->gen_opname (child_opname
, j
);
1848 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1850 preds
[i
]->gen_kids (f
, gimple
);
1854 for (unsigned i
= 0; i
< others
.length (); ++i
)
1855 others
[i
]->gen (f
, gimple
);
1858 true_operand
->gen (f
, gimple
);
1861 /* Generate matching code for the decision tree operand. */
1864 dt_operand::gen (FILE *f
, bool gimple
)
1869 unsigned n_braces
= 0;
1871 if (type
== DT_OPERAND
)
1874 case operand::OP_PREDICATE
:
1875 n_braces
= gen_predicate (f
, opname
, gimple
);
1878 case operand::OP_EXPR
:
1880 n_braces
= gen_gimple_expr (f
);
1882 n_braces
= gen_generic_expr (f
, opname
);
1888 else if (type
== DT_TRUE
)
1890 else if (type
== DT_MATCH
)
1891 n_braces
= gen_match_op (f
, opname
);
1895 gen_kids (f
, gimple
);
1897 for (unsigned i
= 0; i
< n_braces
; ++i
)
1902 /* For GENERIC we have to take care of wrapping multiple-used
1903 expressions with side-effects in save_expr and preserve side-effects
1904 of expressions with omit_one_operand. Analyze captures in
1905 match, result and with expressions and perform early-outs
1906 on the outermost match expression operands for cases we cannot
1911 capture_info (simplify
*s
);
1912 void walk_match (operand
*o
, unsigned toplevel_arg
, bool);
1913 void walk_result (operand
*o
, bool);
1914 void walk_c_expr (c_expr
*);
1920 bool force_no_side_effects_p
;
1921 unsigned long toplevel_msk
;
1922 int result_use_count
;
1925 auto_vec
<cinfo
> info
;
1926 unsigned long force_no_side_effects
;
1929 /* Analyze captures in S. */
1931 capture_info::capture_info (simplify
*s
)
1935 || ((e
= dyn_cast
<expr
*> (s
->result
))
1936 && is_a
<predicate_id
*> (e
->operation
)))
1938 force_no_side_effects
= -1;
1942 force_no_side_effects
= 0;
1943 info
.safe_grow_cleared (s
->capture_max
+ 1);
1944 e
= as_a
<expr
*> (s
->match
);
1945 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1946 walk_match (e
->ops
[i
], i
, false);
1948 walk_result (s
->result
, false);
1950 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1951 if (s
->ifexpr_vec
[i
].is_with
)
1952 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1955 /* Analyze captures in the match expression piece O. */
1958 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
, bool conditional_p
)
1960 if (capture
*c
= dyn_cast
<capture
*> (o
))
1962 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1963 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1964 /* Mark expr (non-leaf) captures and recurse. */
1966 && is_a
<expr
*> (c
->what
))
1968 info
[c
->where
].expr_p
= true;
1969 walk_match (c
->what
, toplevel_arg
, conditional_p
);
1972 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1974 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1976 bool cond_p
= conditional_p
;
1978 && *e
->operation
== COND_EXPR
)
1980 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1981 || *e
->operation
== TRUTH_ORIF_EXPR
)
1983 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
);
1986 else if (is_a
<predicate
*> (o
))
1988 /* Mark non-captured leafs toplevel arg for checking. */
1989 force_no_side_effects
|= 1 << toplevel_arg
;
1995 /* Analyze captures in the result expression piece O. */
1998 capture_info::walk_result (operand
*o
, bool conditional_p
)
2000 if (capture
*c
= dyn_cast
<capture
*> (o
))
2002 info
[c
->where
].result_use_count
++;
2003 /* If we substitute an expression capture we don't know
2004 which captures this will end up using (well, we don't
2005 compute that). Force the uses to be side-effect free
2006 which means forcing the toplevels that reach the
2007 expression side-effect free. */
2008 if (info
[c
->where
].expr_p
)
2009 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
2010 /* Mark CSE capture capture uses as forced to have
2013 && is_a
<expr
*> (c
->what
))
2015 info
[c
->where
].cse_p
= true;
2016 walk_result (c
->what
, true);
2019 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2021 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2023 bool cond_p
= conditional_p
;
2025 && *e
->operation
== COND_EXPR
)
2027 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2028 || *e
->operation
== TRUTH_ORIF_EXPR
)
2030 walk_result (e
->ops
[i
], cond_p
);
2033 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2039 /* Look for captures in the C expr E. */
2042 capture_info::walk_c_expr (c_expr
*e
)
2044 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
2045 unsigned p_depth
= 0;
2046 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2048 const cpp_token
*t
= &e
->code
[i
];
2049 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2050 if (t
->type
== CPP_NAME
2051 && strcmp ((const char *)CPP_HASHNODE
2052 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2053 && n
->type
== CPP_OPEN_PAREN
)
2055 else if (t
->type
== CPP_CLOSE_PAREN
2058 else if (p_depth
== 0
2059 && t
->type
== CPP_ATSIGN
2060 && (n
->type
== CPP_NUMBER
2061 || n
->type
== CPP_NAME
)
2062 && !(n
->flags
& PREV_WHITE
))
2065 if (n
->type
== CPP_NUMBER
)
2066 id
= (const char *)n
->val
.str
.text
;
2068 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2069 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
2075 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2076 step of a '(simplify ...)' or '(match ...)'. This handles everything
2077 that is not part of the decision tree (simplify->match). */
2080 dt_simplify::gen (FILE *f
, bool gimple
)
2083 output_line_directive (f
, s
->result_location
);
2084 if (s
->capture_max
>= 0)
2085 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2086 s
->capture_max
+ 1);
2088 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2092 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2095 unsigned n_braces
= 0;
2096 if (s
->ifexpr_vec
!= vNULL
)
2098 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2100 if_or_with
&w
= s
->ifexpr_vec
[i
];
2104 output_line_directive (f
, w
.location
);
2105 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2110 output_line_directive (f
, w
.location
);
2111 fprintf (f
, "if (");
2112 if (i
== s
->ifexpr_vec
.length () - 1
2113 || s
->ifexpr_vec
[i
+1].is_with
)
2114 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2123 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2127 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2132 while (j
< s
->ifexpr_vec
.length ()
2133 && !s
->ifexpr_vec
[j
].is_with
);
2143 /* Analyze captures and perform early-outs on the incoming arguments
2144 that cover cases we cannot handle. */
2145 capture_info
cinfo (s
);
2149 && !((e
= dyn_cast
<expr
*> (s
->result
))
2150 && is_a
<predicate_id
*> (e
->operation
)))
2152 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2153 if (cinfo
.force_no_side_effects
& (1 << i
))
2154 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2155 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2156 if (cinfo
.info
[i
].cse_p
)
2158 else if (cinfo
.info
[i
].force_no_side_effects_p
2159 && (cinfo
.info
[i
].toplevel_msk
2160 & cinfo
.force_no_side_effects
) == 0)
2161 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2162 "return NULL_TREE;\n", i
);
2163 else if ((cinfo
.info
[i
].toplevel_msk
2164 & cinfo
.force_no_side_effects
) != 0)
2165 /* Mark capture as having no side-effects if we had to verify
2166 that via forced toplevel operand checks. */
2167 cinfo
.info
[i
].force_no_side_effects_p
= true;
2170 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2171 "fprintf (dump_file, \"Applying pattern ");
2172 output_line_directive (f
, s
->result_location
, true);
2173 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2175 operand
*result
= s
->result
;
2178 /* If there is no result then this is a predicate implementation. */
2179 fprintf (f
, "return true;\n");
2183 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2184 in outermost position). */
2185 if (result
->type
== operand::OP_EXPR
2186 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2187 result
= as_a
<expr
*> (result
)->ops
[0];
2188 if (result
->type
== operand::OP_EXPR
)
2190 expr
*e
= as_a
<expr
*> (result
);
2191 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2193 fprintf (f
, "*res_code = %s;\n",
2194 *e
->operation
== CONVERT_EXPR
2195 ? "NOP_EXPR" : e
->operation
->id
);
2196 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2199 snprintf (dest
, 32, " res_ops[%d]", j
);
2201 = get_operand_type (e
->operation
,
2202 "type", e
->expr_type
,
2204 ? NULL
: "TREE_TYPE (res_ops[0])");
2205 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
2208 /* Re-fold the toplevel result. It's basically an embedded
2209 gimple_build w/o actually building the stmt. */
2211 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2212 "res_ops, valueize);\n", e
->ops
.length ());
2214 else if (result
->type
== operand::OP_CAPTURE
2215 || result
->type
== operand::OP_C_EXPR
)
2217 result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
2218 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2222 fprintf (f
, "return true;\n");
2226 bool is_predicate
= false;
2227 if (result
->type
== operand::OP_EXPR
)
2229 expr
*e
= as_a
<expr
*> (result
);
2230 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2231 /* Search for captures used multiple times in the result expression
2232 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2234 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2236 if (!cinfo
.info
[i
].force_no_side_effects_p
2237 && cinfo
.info
[i
].result_use_count
> 1)
2238 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2239 " captures[%d] = save_expr (captures[%d]);\n",
2242 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2246 snprintf (dest
, 32, "res_ops[%d]", j
);
2249 fprintf (f
, " tree res_op%d;\n", j
);
2250 snprintf (dest
, 32, " res_op%d", j
);
2253 = get_operand_type (e
->operation
,
2254 "type", e
->expr_type
,
2256 ? NULL
: "TREE_TYPE (res_op0)");
2257 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2260 fprintf (f
, "return true;\n");
2263 fprintf (f
, " tree res;\n");
2264 /* Re-fold the toplevel result. Use non_lvalue to
2265 build NON_LVALUE_EXPRs so they get properly
2266 ignored when in GIMPLE form. */
2267 if (*e
->operation
== NON_LVALUE_EXPR
)
2268 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2271 if (e
->operation
->kind
== id_base::CODE
)
2272 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2274 *e
->operation
== CONVERT_EXPR
2275 ? "NOP_EXPR" : e
->operation
->id
);
2277 fprintf (f
, " res = build_call_expr_loc "
2278 "(loc, builtin_decl_implicit (%s), %d",
2279 e
->operation
->id
, e
->ops
.length());
2280 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2281 fprintf (f
, ", res_op%d", j
);
2282 fprintf (f
, ");\n");
2286 else if (result
->type
== operand::OP_CAPTURE
2287 || result
->type
== operand::OP_C_EXPR
)
2290 fprintf (f
, " tree res;\n");
2291 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2297 /* Search for captures not used in the result expression and dependent
2298 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2299 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2301 if (!cinfo
.info
[i
].force_no_side_effects_p
2302 && !cinfo
.info
[i
].expr_p
2303 && cinfo
.info
[i
].result_use_count
== 0)
2304 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2305 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2306 " fold_ignored_result (captures[%d]), res);\n",
2309 fprintf (f
, " return res;\n");
2313 for (unsigned i
= 0; i
< n_braces
; ++i
)
2319 /* Main entry to generate code for matching GIMPLE IL off the decision
2323 decision_tree::gen_gimple (FILE *f
)
2325 for (unsigned n
= 1; n
<= 3; ++n
)
2327 fprintf (f
, "\nstatic bool\n"
2328 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2329 " gimple_seq *seq, tree (*valueize)(tree),\n"
2330 " code_helper code, tree type");
2331 for (unsigned i
= 0; i
< n
; ++i
)
2332 fprintf (f
, ", tree op%d", i
);
2336 fprintf (f
, "switch (code.get_rep())\n"
2338 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2340 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2341 expr
*e
= static_cast<expr
*>(dop
->op
);
2342 if (e
->ops
.length () != n
)
2345 if (*e
->operation
== CONVERT_EXPR
2346 || *e
->operation
== NOP_EXPR
)
2347 fprintf (f
, "CASE_CONVERT:\n");
2349 fprintf (f
, "case %s%s:\n",
2350 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2353 dop
->gen_kids (f
, true);
2354 fprintf (f
, "break;\n");
2357 fprintf (f
, "default:;\n"
2360 fprintf (f
, "return false;\n");
2365 /* Main entry to generate code for matching GENERIC IL off the decision
2369 decision_tree::gen_generic (FILE *f
)
2371 for (unsigned n
= 1; n
<= 3; ++n
)
2373 fprintf (f
, "\ntree\n"
2374 "generic_simplify (location_t loc, enum tree_code code, "
2375 "tree type ATTRIBUTE_UNUSED");
2376 for (unsigned i
= 0; i
< n
; ++i
)
2377 fprintf (f
, ", tree op%d", i
);
2381 fprintf (f
, "switch (code)\n"
2383 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2385 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2386 expr
*e
= static_cast<expr
*>(dop
->op
);
2387 if (e
->ops
.length () != n
2388 /* Builtin simplifications are somewhat premature on
2389 GENERIC. The following drops patterns with outermost
2390 calls. It's easy to emit overloads for function code
2391 though if necessary. */
2392 || e
->operation
->kind
!= id_base::CODE
)
2395 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2396 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2397 fprintf (f
, "CASE_CONVERT:\n");
2399 fprintf (f
, "case %s:\n", e
->operation
->id
);
2401 dop
->gen_kids (f
, false);
2402 fprintf (f
, "break;\n"
2405 fprintf (f
, "default:;\n"
2408 fprintf (f
, "return NULL_TREE;\n");
2413 /* Output code to implement the predicate P from the decision tree DT. */
2416 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2418 fprintf (f
, "\nbool\n"
2419 "%s%s (tree t%s%s)\n"
2420 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2421 p
->nargs
> 0 ? ", tree *res_ops" : "",
2422 gimple
? ", tree (*valueize)(tree)" : "");
2423 /* Conveniently make 'type' available. */
2424 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2427 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2428 dt
.root
->gen_kids (f
, gimple
);
2430 fprintf (f
, "return false;\n"
2434 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2437 write_header (FILE *f
, const char *head
)
2439 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2440 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2442 /* Include the header instead of writing it awkwardly quoted here. */
2443 fprintf (f
, "\n#include \"%s\"\n", head
);
2453 parser (cpp_reader
*);
2456 const cpp_token
*next ();
2457 const cpp_token
*peek ();
2458 const cpp_token
*peek_ident (const char * = NULL
);
2459 const cpp_token
*expect (enum cpp_ttype
);
2460 void eat_token (enum cpp_ttype
);
2461 const char *get_string ();
2462 const char *get_ident ();
2463 void eat_ident (const char *);
2464 const char *get_number ();
2466 id_base
*parse_operation ();
2467 operand
*parse_capture (operand
*);
2468 operand
*parse_expr ();
2469 c_expr
*parse_c_expr (cpp_ttype
);
2470 operand
*parse_op ();
2472 void parse_pattern ();
2473 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2475 void parse_for (source_location
);
2476 void parse_if (source_location
);
2477 void parse_predicates (source_location
);
2480 vec
<if_or_with
> active_ifs
;
2481 vec
<vec
<user_id
*> > active_fors
;
2483 cid_map_t
*capture_ids
;
2486 vec
<simplify
*> simplifiers
;
2487 vec
<predicate_id
*> user_predicates
;
2490 /* Lexing helpers. */
2492 /* Read the next non-whitespace token from R. */
2497 const cpp_token
*token
;
2500 token
= cpp_get_token (r
);
2502 while (token
->type
== CPP_PADDING
2503 && token
->type
!= CPP_EOF
);
2507 /* Peek at the next non-whitespace token from R. */
2512 const cpp_token
*token
;
2516 token
= cpp_peek_token (r
, i
++);
2518 while (token
->type
== CPP_PADDING
2519 && token
->type
!= CPP_EOF
);
2520 /* If we peek at EOF this is a fatal error as it leaves the
2521 cpp_reader in unusable state. Assume we really wanted a
2522 token and thus this EOF is unexpected. */
2523 if (token
->type
== CPP_EOF
)
2524 fatal_at (token
, "unexpected end of file");
2528 /* Peek at the next identifier token (or return NULL if the next
2529 token is not an identifier or equal to ID if supplied). */
2532 parser::peek_ident (const char *id
)
2534 const cpp_token
*token
= peek ();
2535 if (token
->type
!= CPP_NAME
)
2541 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2542 if (strcmp (id
, t
) == 0)
2548 /* Read the next token from R and assert it is of type TK. */
2551 parser::expect (enum cpp_ttype tk
)
2553 const cpp_token
*token
= next ();
2554 if (token
->type
!= tk
)
2555 fatal_at (token
, "expected %s, got %s",
2556 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2561 /* Consume the next token from R and assert it is of type TK. */
2564 parser::eat_token (enum cpp_ttype tk
)
2569 /* Read the next token from R and assert it is of type CPP_STRING and
2570 return its value. */
2573 parser::get_string ()
2575 const cpp_token
*token
= expect (CPP_STRING
);
2576 return (const char *)token
->val
.str
.text
;
2579 /* Read the next token from R and assert it is of type CPP_NAME and
2580 return its value. */
2583 parser::get_ident ()
2585 const cpp_token
*token
= expect (CPP_NAME
);
2586 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2589 /* Eat an identifier token with value S from R. */
2592 parser::eat_ident (const char *s
)
2594 const cpp_token
*token
= peek ();
2595 const char *t
= get_ident ();
2596 if (strcmp (s
, t
) != 0)
2597 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2600 /* Read the next token from R and assert it is of type CPP_NUMBER and
2601 return its value. */
2604 parser::get_number ()
2606 const cpp_token
*token
= expect (CPP_NUMBER
);
2607 return (const char *)token
->val
.str
.text
;
2611 /* Parse the operator ID, special-casing convert?, convert1? and
2615 parser::parse_operation ()
2617 const cpp_token
*id_tok
= peek ();
2618 const char *id
= get_ident ();
2619 const cpp_token
*token
= peek ();
2620 if (strcmp (id
, "convert0") == 0)
2621 fatal_at (id_tok
, "use 'convert?' here");
2622 if (token
->type
== CPP_QUERY
2623 && !(token
->flags
& PREV_WHITE
))
2625 if (strcmp (id
, "convert") == 0)
2627 else if (strcmp (id
, "convert1") == 0)
2629 else if (strcmp (id
, "convert2") == 0)
2632 fatal_at (id_tok
, "non-convert operator conditionalized");
2633 eat_token (CPP_QUERY
);
2635 else if (strcmp (id
, "convert1") == 0
2636 || strcmp (id
, "convert2") == 0)
2637 fatal_at (id_tok
, "expected '?' after conditional operator");
2638 id_base
*op
= get_operator (id
);
2640 fatal_at (id_tok
, "unknown operator %s", id
);
2645 capture = '@'<number> */
2648 parser::parse_capture (operand
*op
)
2650 eat_token (CPP_ATSIGN
);
2651 const cpp_token
*token
= peek ();
2653 if (token
->type
== CPP_NUMBER
)
2655 else if (token
->type
== CPP_NAME
)
2658 fatal_at (token
, "expected number or identifier");
2659 unsigned next_id
= capture_ids
->elements ();
2661 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2664 return new capture (num
, op
);
2667 /* Parse an expression
2668 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2671 parser::parse_expr ()
2673 expr
*e
= new expr (parse_operation ());
2674 const cpp_token
*token
= peek ();
2676 bool is_commutative
= false;
2677 const char *expr_type
= NULL
;
2679 if (token
->type
== CPP_COLON
2680 && !(token
->flags
& PREV_WHITE
))
2682 eat_token (CPP_COLON
);
2684 if (token
->type
== CPP_NAME
2685 && !(token
->flags
& PREV_WHITE
))
2687 const char *s
= get_ident ();
2688 if (s
[0] == 'c' && !s
[1])
2689 is_commutative
= true;
2690 else if (s
[1] != '\0')
2693 fatal_at (token
, "flag %s not recognized", s
);
2697 fatal_at (token
, "expected flag or type specifying identifier");
2700 if (token
->type
== CPP_ATSIGN
2701 && !(token
->flags
& PREV_WHITE
))
2702 op
= parse_capture (e
);
2707 const cpp_token
*token
= peek ();
2708 if (token
->type
== CPP_CLOSE_PAREN
)
2710 if (e
->operation
->nargs
!= -1
2711 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2712 fatal_at (token
, "'%s' expects %u operands, not %u",
2713 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2716 if (e
->ops
.length () == 2)
2717 e
->is_commutative
= true;
2719 fatal_at (token
, "only binary operators or function with "
2720 "two arguments can be marked commutative");
2722 e
->expr_type
= expr_type
;
2725 e
->append_op (parse_op ());
2730 /* Lex native C code delimited by START recording the preprocessing tokens
2731 for later processing.
2732 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2735 parser::parse_c_expr (cpp_ttype start
)
2737 const cpp_token
*token
;
2740 vec
<cpp_token
> code
= vNULL
;
2741 unsigned nr_stmts
= 0;
2743 if (start
== CPP_OPEN_PAREN
)
2744 end
= CPP_CLOSE_PAREN
;
2745 else if (start
== CPP_OPEN_BRACE
)
2746 end
= CPP_CLOSE_BRACE
;
2754 /* Count brace pairs to find the end of the expr to match. */
2755 if (token
->type
== start
)
2757 else if (token
->type
== end
2761 /* This is a lame way of counting the number of statements. */
2762 if (token
->type
== CPP_SEMICOLON
)
2765 /* Record the token. */
2766 code
.safe_push (*token
);
2769 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2772 /* Parse an operand which is either an expression, a predicate or
2773 a standalone capture.
2774 op = predicate | expr | c_expr | capture */
2779 const cpp_token
*token
= peek ();
2780 struct operand
*op
= NULL
;
2781 if (token
->type
== CPP_OPEN_PAREN
)
2783 eat_token (CPP_OPEN_PAREN
);
2785 eat_token (CPP_CLOSE_PAREN
);
2787 else if (token
->type
== CPP_OPEN_BRACE
)
2789 op
= parse_c_expr (CPP_OPEN_BRACE
);
2793 /* Remaining ops are either empty or predicates */
2794 if (token
->type
== CPP_NAME
)
2796 const char *id
= get_ident ();
2797 id_base
*opr
= get_operator (id
);
2799 fatal_at (token
, "expected predicate name");
2800 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2802 if (code
->nargs
!= 0)
2803 fatal_at (token
, "using an operator with operands as predicate");
2804 /* Parse the zero-operand operator "predicates" as
2806 op
= new expr (opr
);
2808 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2809 op
= new predicate (p
);
2811 fatal_at (token
, "using an unsupported operator as predicate");
2813 if (token
->flags
& PREV_WHITE
)
2816 else if (token
->type
!= CPP_COLON
2817 && token
->type
!= CPP_ATSIGN
)
2818 fatal_at (token
, "expected expression or predicate");
2819 /* optionally followed by a capture and a predicate. */
2820 if (token
->type
== CPP_COLON
)
2821 fatal_at (token
, "not implemented: predicate on leaf operand");
2822 if (token
->type
== CPP_ATSIGN
)
2823 op
= parse_capture (op
);
2830 simplify = 'simplify' <expr> <result-op>
2832 match = 'match' <ident> <expr> [<result-op>]
2834 <result-op> = <op> | <if> | <with>
2835 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2836 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2837 and fill SIMPLIFIERS with the results. */
2840 parser::parse_simplify (source_location match_location
,
2841 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2844 /* Reset the capture map. */
2845 capture_ids
= new cid_map_t
;
2847 const cpp_token
*loc
= peek ();
2848 struct operand
*match
= parse_op ();
2849 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2850 fatal_at (loc
, "outermost expression cannot be captured");
2851 if (match
->type
== operand::OP_EXPR
2852 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2853 fatal_at (loc
, "outermost expression cannot be a predicate");
2855 const cpp_token
*token
= peek ();
2857 /* If this if is immediately closed then it is part of a predicate
2858 definition. Push it. */
2859 if (token
->type
== CPP_CLOSE_PAREN
)
2862 fatal_at (token
, "expected transform expression");
2863 simplifiers
.safe_push
2864 (new simplify (match
, match_location
, result
, token
->src_loc
,
2865 active_ifs
.copy (), active_fors
.copy (),
2870 unsigned active_ifs_len
= active_ifs
.length ();
2873 if (token
->type
== CPP_OPEN_PAREN
)
2875 source_location paren_loc
= token
->src_loc
;
2876 eat_token (CPP_OPEN_PAREN
);
2877 if (peek_ident ("if"))
2880 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2881 token
->src_loc
, false));
2882 /* If this if is immediately closed then it contains a
2883 manual matcher or is part of a predicate definition.
2885 if (peek ()->type
== CPP_CLOSE_PAREN
)
2888 fatal_at (token
, "manual transform not implemented");
2889 simplifiers
.safe_push
2890 (new simplify (match
, match_location
, result
,
2891 paren_loc
, active_ifs
.copy (),
2892 active_fors
.copy (), capture_ids
));
2895 else if (peek_ident ("with"))
2898 /* Parse (with c-expr expr) as (if-with (true) expr). */
2899 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2901 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2905 operand
*op
= result
;
2908 simplifiers
.safe_push
2909 (new simplify (match
, match_location
, op
,
2910 token
->src_loc
, active_ifs
.copy (),
2911 active_fors
.copy (), capture_ids
));
2912 eat_token (CPP_CLOSE_PAREN
);
2913 /* A "default" result closes the enclosing scope. */
2914 if (active_ifs
.length () > active_ifs_len
)
2916 eat_token (CPP_CLOSE_PAREN
);
2923 else if (token
->type
== CPP_CLOSE_PAREN
)
2925 /* Close a scope if requested. */
2926 if (active_ifs
.length () > active_ifs_len
)
2928 eat_token (CPP_CLOSE_PAREN
);
2938 fatal_at (token
, "expected match operand expression");
2939 simplifiers
.safe_push
2940 (new simplify (match
, match_location
,
2941 matcher
? result
: parse_op (),
2942 token
->src_loc
, active_ifs
.copy (),
2943 active_fors
.copy (), capture_ids
));
2944 /* A "default" result closes the enclosing scope. */
2945 if (active_ifs
.length () > active_ifs_len
)
2947 eat_token (CPP_CLOSE_PAREN
);
2957 /* Parsing of the outer control structures. */
2959 /* Parse a for expression
2960 for = '(' 'for' <subst>... <pattern> ')'
2961 subst = <ident> '(' <ident>... ')' */
2964 parser::parse_for (source_location
)
2966 vec
<user_id
*> user_ids
= vNULL
;
2967 const cpp_token
*token
;
2968 unsigned min_n_opers
= 0, max_n_opers
= 0;
2972 token
= peek_ident ();
2976 /* Insert the user defined operators into the operator hash. */
2977 const char *id
= get_ident ();
2978 user_id
*op
= new user_id (id
);
2979 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2981 fatal_at (token
, "operator already defined");
2983 user_ids
.safe_push (op
);
2985 eat_token (CPP_OPEN_PAREN
);
2988 while ((token
= peek_ident ()) != 0)
2990 const char *oper
= get_ident ();
2991 id_base
*idb
= get_operator (oper
);
2993 fatal_at (token
, "no such operator '%s'", oper
);
2994 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2995 fatal_at (token
, "conditional operators cannot be used inside for");
2999 else if (idb
->nargs
== -1)
3001 else if (idb
->nargs
!= arity
)
3002 fatal_at (token
, "operator '%s' with arity %d does not match "
3003 "others with arity %d", oper
, idb
->nargs
, arity
);
3005 op
->substitutes
.safe_push (idb
);
3008 token
= expect (CPP_CLOSE_PAREN
);
3010 unsigned nsubstitutes
= op
->substitutes
.length ();
3011 if (nsubstitutes
== 0)
3012 fatal_at (token
, "A user-defined operator must have at least "
3013 "one substitution");
3014 if (max_n_opers
== 0)
3016 min_n_opers
= nsubstitutes
;
3017 max_n_opers
= nsubstitutes
;
3021 if (nsubstitutes
% min_n_opers
!= 0
3022 && min_n_opers
% nsubstitutes
!= 0)
3023 fatal_at (token
, "All user-defined identifiers must have a "
3024 "multiple number of operator substitutions of the "
3025 "smallest number of substitutions");
3026 if (nsubstitutes
< min_n_opers
)
3027 min_n_opers
= nsubstitutes
;
3028 else if (nsubstitutes
> max_n_opers
)
3029 max_n_opers
= nsubstitutes
;
3033 unsigned n_ids
= user_ids
.length ();
3035 fatal_at (token
, "for requires at least one user-defined identifier");
3038 if (token
->type
== CPP_CLOSE_PAREN
)
3039 fatal_at (token
, "no pattern defined in for");
3041 active_fors
.safe_push (user_ids
);
3045 if (token
->type
== CPP_CLOSE_PAREN
)
3051 /* Remove user-defined operators from the hash again. */
3052 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3053 operators
->remove_elt (user_ids
[i
]);
3056 /* Parse an outer if expression.
3057 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3060 parser::parse_if (source_location loc
)
3062 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3064 const cpp_token
*token
= peek ();
3065 if (token
->type
== CPP_CLOSE_PAREN
)
3066 fatal_at (token
, "no pattern defined in if");
3068 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3071 const cpp_token
*token
= peek ();
3072 if (token
->type
== CPP_CLOSE_PAREN
)
3080 /* Parse a list of predefined predicate identifiers.
3081 preds = '(' 'define_predicates' <ident>... ')' */
3084 parser::parse_predicates (source_location
)
3088 const cpp_token
*token
= peek ();
3089 if (token
->type
!= CPP_NAME
)
3092 add_predicate (get_ident ());
3097 /* Parse outer control structures.
3098 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3101 parser::parse_pattern ()
3103 /* All clauses start with '('. */
3104 eat_token (CPP_OPEN_PAREN
);
3105 const cpp_token
*token
= peek ();
3106 const char *id
= get_ident ();
3107 if (strcmp (id
, "simplify") == 0)
3108 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3109 else if (strcmp (id
, "match") == 0)
3111 bool with_args
= false;
3112 if (peek ()->type
== CPP_OPEN_PAREN
)
3114 eat_token (CPP_OPEN_PAREN
);
3117 const char *name
= get_ident ();
3118 id_base
*id
= get_operator (name
);
3122 p
= add_predicate (name
);
3123 user_predicates
.safe_push (p
);
3125 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3128 fatal_at (token
, "cannot add a match to a non-predicate ID");
3129 /* Parse (match <id> <arg>... (match-expr)) here. */
3134 while (peek ()->type
== CPP_ATSIGN
)
3135 e
->append_op (parse_capture (NULL
));
3136 eat_token (CPP_CLOSE_PAREN
);
3139 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3140 || (!e
&& p
->nargs
!= 0)))
3141 fatal_at (token
, "non-matching number of match operands");
3142 p
->nargs
= e
? e
->ops
.length () : 0;
3143 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3145 else if (strcmp (id
, "for") == 0)
3146 parse_for (token
->src_loc
);
3147 else if (strcmp (id
, "if") == 0)
3148 parse_if (token
->src_loc
);
3149 else if (strcmp (id
, "define_predicates") == 0)
3151 if (active_ifs
.length () > 0
3152 || active_fors
.length () > 0)
3153 fatal_at (token
, "define_predicates inside if or for is not supported");
3154 parse_predicates (token
->src_loc
);
3157 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3158 active_ifs
.length () == 0 && active_fors
.length () == 0
3159 ? "'define_predicates', " : "");
3161 eat_token (CPP_CLOSE_PAREN
);
3164 /* Main entry of the parser. Repeatedly parse outer control structures. */
3166 parser::parser (cpp_reader
*r_
)
3170 active_fors
= vNULL
;
3171 simplifiers
= vNULL
;
3172 user_predicates
= vNULL
;
3174 const cpp_token
*token
= next ();
3175 while (token
->type
!= CPP_EOF
)
3177 _cpp_backup_tokens (r
, 1);
3184 /* Helper for the linemap code. */
3187 round_alloc_size (size_t s
)
3193 /* The genmatch generator progam. It reads from a pattern description
3194 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3197 main (int argc
, char **argv
)
3201 progname
= "genmatch";
3207 bool verbose
= false;
3208 char *input
= argv
[argc
-1];
3209 for (int i
= 1; i
< argc
- 1; ++i
)
3211 if (strcmp (argv
[i
], "--gimple") == 0)
3213 else if (strcmp (argv
[i
], "--generic") == 0)
3215 else if (strcmp (argv
[i
], "-v") == 0)
3219 fprintf (stderr
, "Usage: genmatch "
3220 "[--gimple] [--generic] [-v] input\n");
3225 line_table
= XCNEW (struct line_maps
);
3226 linemap_init (line_table
, 0);
3227 line_table
->reallocator
= xrealloc
;
3228 line_table
->round_alloc_size
= round_alloc_size
;
3230 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3231 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3232 cb
->error
= error_cb
;
3234 if (!cpp_read_main_file (r
, input
))
3236 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3237 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3239 /* Pre-seed operators. */
3240 operators
= new hash_table
<id_base
> (1024);
3241 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3242 add_operator (SYM, # SYM, # TYPE, NARGS);
3243 #define END_OF_BASE_TREE_CODES
3245 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3246 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3247 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3248 #undef END_OF_BASE_TREE_CODES
3251 /* Pre-seed builtin functions.
3252 ??? Cannot use N (name) as that is targetm.emultls.get_address
3253 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3254 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3255 add_builtin (ENUM, # ENUM);
3256 #include "builtins.def"
3263 write_header (stdout
, "gimple-match-head.c");
3265 write_header (stdout
, "generic-match-head.c");
3267 /* Go over all predicates defined with patterns and perform
3268 lowering and code generation. */
3269 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3271 predicate_id
*pred
= p
.user_predicates
[i
];
3272 lower (pred
->matchers
);
3275 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3276 print_matches (pred
->matchers
[i
]);
3279 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3280 dt
.insert (pred
->matchers
[i
], i
);
3285 write_predicate (stdout
, pred
, dt
, gimple
);
3288 /* Lower the main simplifiers and generate code for them. */
3289 lower (p
.simplifiers
);
3292 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3293 print_matches (p
.simplifiers
[i
]);
3296 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3297 dt
.insert (p
.simplifiers
[i
], i
);
3303 dt
.gen_gimple (stdout
);
3305 dt
.gen_generic (stdout
);
3308 cpp_finish (r
, NULL
);