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/>. */
30 #include "coretypes.h"
34 #include "hash-table.h"
41 static struct line_maps
*line_table
;
44 #if GCC_VERSION >= 4001
45 __attribute__((format (printf
, 6, 0)))
47 error_cb (cpp_reader
*, int, int, source_location location
,
48 unsigned int, const char *msg
, va_list *ap
)
51 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
52 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
53 fprintf (stderr
, "%s:%d:%d error: ", loc
.file
, loc
.line
, loc
.column
);
54 vfprintf (stderr
, msg
, *ap
);
55 fprintf (stderr
, "\n");
56 FILE *f
= fopen (loc
.file
, "r");
62 if (!fgets (buf
, 128, f
))
64 if (buf
[strlen (buf
) - 1] != '\n')
71 fprintf (stderr
, "%s", buf
);
72 for (int i
= 0; i
< loc
.column
- 1; ++i
)
83 #if GCC_VERSION >= 4001
84 __attribute__((format (printf
, 2, 3)))
86 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
90 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
95 output_line_directive (FILE *f
, source_location location
,
96 bool dumpfile
= false)
99 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
100 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
103 /* When writing to a dumpfile only dump the filename. */
104 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
109 fprintf (f
, "%s:%d", file
, loc
.line
);
112 /* Other gen programs really output line directives here, at least for
113 development it's right now more convenient to have line information
114 from the generated file. Still keep the directives as comment for now
115 to easily back-point to the meta-description. */
116 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
120 /* Pull in tree codes and builtin function codes from their
123 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
133 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
134 enum built_in_function
{
135 #include "builtins.def"
141 /* Base class for all identifiers the parser knows. */
143 struct id_base
: typed_noop_remove
<id_base
>
145 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
147 id_base (id_kind
, const char *, int = -1);
153 /* hash_table support. */
154 typedef id_base value_type
;
155 typedef id_base compare_type
;
156 static inline hashval_t
hash (const value_type
*);
157 static inline int equal (const value_type
*, const compare_type
*);
161 id_base::hash (const value_type
*op
)
167 id_base::equal (const value_type
*op1
,
168 const compare_type
*op2
)
170 return (op1
->hashval
== op2
->hashval
171 && strcmp (op1
->id
, op2
->id
) == 0);
174 /* Hashtable of known pattern operators. This is pre-seeded from
175 all known tree codes and all known builtin function ids. */
176 static hash_table
<id_base
> *operators
;
178 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
183 hashval
= htab_hash_string (id
);
186 /* Identifier that maps to a tree code. */
188 struct operator_id
: public id_base
190 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
192 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
197 /* Identifier that maps to a builtin function code. */
199 struct fn_id
: public id_base
201 fn_id (enum built_in_function fn_
, const char *id_
)
202 : id_base (id_base::FN
, id_
), fn (fn_
) {}
203 enum built_in_function fn
;
208 /* Identifier that maps to a user-defined predicate. */
210 struct predicate_id
: public id_base
212 predicate_id (const char *id_
)
213 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
214 vec
<simplify
*> matchers
;
217 /* Identifier that maps to a operator defined by a 'for' directive. */
219 struct user_id
: public id_base
221 user_id (const char *id_
)
222 : id_base (id_base::USER
, id_
), substitutes (vNULL
) {}
223 vec
<id_base
*> substitutes
;
229 is_a_helper
<fn_id
*>::test (id_base
*id
)
231 return id
->kind
== id_base::FN
;
237 is_a_helper
<operator_id
*>::test (id_base
*id
)
239 return id
->kind
== id_base::CODE
;
245 is_a_helper
<predicate_id
*>::test (id_base
*id
)
247 return id
->kind
== id_base::PREDICATE
;
253 is_a_helper
<user_id
*>::test (id_base
*id
)
255 return id
->kind
== id_base::USER
;
258 /* Add a predicate identifier to the hash. */
260 static predicate_id
*
261 add_predicate (const char *id
)
263 predicate_id
*p
= new predicate_id (id
);
264 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
266 fatal ("duplicate id definition");
271 /* Add a tree code identifier to the hash. */
274 add_operator (enum tree_code code
, const char *id
,
275 const char *tcc
, unsigned nargs
)
277 if (strcmp (tcc
, "tcc_unary") != 0
278 && strcmp (tcc
, "tcc_binary") != 0
279 && strcmp (tcc
, "tcc_comparison") != 0
280 && strcmp (tcc
, "tcc_expression") != 0
281 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
282 && strcmp (tcc
, "tcc_reference") != 0
283 /* To have INTEGER_CST and friends as "predicate operators". */
284 && strcmp (tcc
, "tcc_constant") != 0)
286 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
287 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
289 fatal ("duplicate id definition");
293 /* Add a builtin identifier to the hash. */
296 add_builtin (enum built_in_function code
, const char *id
)
298 fn_id
*fn
= new fn_id (code
, id
);
299 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
301 fatal ("duplicate id definition");
305 /* Helper for easy comparing ID with tree code CODE. */
308 operator==(id_base
&id
, enum tree_code code
)
310 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
311 return oid
->code
== code
;
315 /* Lookup the identifier ID. */
318 get_operator (const char *id
)
320 id_base
tem (id_base::CODE
, id
);
322 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
326 /* Try all-uppercase. */
327 char *id2
= xstrdup (id
);
328 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
329 id2
[i
] = TOUPPER (id2
[i
]);
330 new (&tem
) id_base (id_base::CODE
, id2
);
331 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
338 /* Try _EXPR appended. */
339 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
340 strcat (id2
, "_EXPR");
341 new (&tem
) id_base (id_base::CODE
, id2
);
342 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
354 /* The AST produced by parsing of the pattern definitions. */
358 /* The base class for operands. */
361 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
362 operand (enum op_type type_
) : type (type_
) {}
364 virtual void gen_transform (FILE *, const char *, bool, int,
365 const char *, dt_operand
** = 0)
366 { gcc_unreachable (); }
369 /* A predicate operand. Predicates are leafs in the AST. */
371 struct predicate
: public operand
373 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
377 /* An operand that constitutes an expression. Expressions include
378 function calls and user-defined predicate invocations. */
380 struct expr
: public operand
382 expr (id_base
*operation_
, bool is_commutative_
= false)
383 : operand (OP_EXPR
), operation (operation_
),
384 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
) {}
385 void append_op (operand
*op
) { ops
.safe_push (op
); }
386 /* The operator and its operands. */
389 /* An explicitely specified type - used exclusively for conversions. */
390 const char *expr_type
;
391 /* Whether the operation is to be applied commutatively. This is
392 later lowered to two separate patterns. */
394 virtual void gen_transform (FILE *f
, const char *, bool, int,
395 const char *, dt_operand
** = 0);
398 /* An operator that is represented by native C code. This is always
399 a leaf operand in the AST. This class is also used to represent
400 the code to be generated for 'if' and 'with' expressions. */
402 struct c_expr
: public operand
404 /* A mapping of an identifier and its replacement. Used to apply
409 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
412 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
413 vec
<id_tab
> ids_
, std::map
<std::string
, unsigned> *capture_ids_
)
414 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
415 nr_stmts (nr_stmts_
), ids (ids_
) {}
416 /* cpplib tokens and state to transform this back to source. */
419 std::map
<std::string
, unsigned> *capture_ids
;
420 /* The number of statements parsed (well, the number of ';'s). */
422 /* The identifier replacement vector. */
424 virtual void gen_transform (FILE *f
, const char *, bool, int,
425 const char *, dt_operand
**);
428 /* A wrapper around another operand that captures its value. */
430 struct capture
: public operand
432 capture (unsigned where_
, operand
*what_
)
433 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
434 /* Identifier index for the value. */
436 /* The captured value. */
438 virtual void gen_transform (FILE *f
, const char *, bool, int,
439 const char *, dt_operand
** = 0);
445 is_a_helper
<capture
*>::test (operand
*op
)
447 return op
->type
== operand::OP_CAPTURE
;
453 is_a_helper
<predicate
*>::test (operand
*op
)
455 return op
->type
== operand::OP_PREDICATE
;
461 is_a_helper
<c_expr
*>::test (operand
*op
)
463 return op
->type
== operand::OP_C_EXPR
;
469 is_a_helper
<expr
*>::test (operand
*op
)
471 return op
->type
== operand::OP_EXPR
;
474 /* Helper to distinguish 'if' from 'with' expressions. */
478 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
479 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
480 source_location location
;
485 /* The main class of a pattern and its transform. This is used to
486 represent both (simplify ...) and (match ...) kinds. The AST
487 duplicates all outer 'if' and 'for' expressions here so each
488 simplify can exist in isolation. */
492 simplify (operand
*match_
, source_location match_location_
,
493 struct operand
*result_
, source_location result_location_
,
494 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
495 std::map
<std::string
, unsigned> *capture_ids_
)
496 : match (match_
), match_location (match_location_
),
497 result (result_
), result_location (result_location_
),
498 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
499 capture_ids (capture_ids_
), capture_max (capture_ids_
->size () - 1) {}
501 /* The expression that is matched against the GENERIC or GIMPLE IL. */
503 source_location match_location
;
504 /* For a (simplify ...) the expression produced when the pattern applies.
505 For a (match ...) either NULL if it is a simple predicate or the
506 single expression specifying the matched operands. */
507 struct operand
*result
;
508 source_location result_location
;
509 /* Collected 'if' expressions that need to evaluate to true to make
510 the pattern apply. */
511 vec
<if_or_with
> ifexpr_vec
;
512 /* Collected 'for' expression operators that have to be replaced
513 in the lowering phase. */
514 vec
<vec
<user_id
*> > for_vec
;
515 /* A map of capture identifiers to indexes. */
516 std::map
<std::string
, unsigned> *capture_ids
;
520 /* Debugging routines for dumping the AST. */
523 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
525 if (capture
*c
= dyn_cast
<capture
*> (o
))
527 fprintf (f
, "@%u", c
->where
);
528 if (c
->what
&& flattened
== false)
531 print_operand (c
->what
, f
, flattened
);
536 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
537 fprintf (f
, "%s", p
->p
->id
);
539 else if (is_a
<c_expr
*> (o
))
540 fprintf (f
, "c_expr");
542 else if (expr
*e
= dyn_cast
<expr
*> (o
))
544 fprintf (f
, "(%s", e
->operation
->id
);
546 if (flattened
== false)
549 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
551 print_operand (e
->ops
[i
], f
, flattened
);
563 print_matches (struct simplify
*s
, FILE *f
= stderr
)
565 fprintf (f
, "for expression: ");
566 print_operand (s
->match
, f
);
573 /* Lowering of commutative operators. */
576 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
577 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
579 if (n
== ops_vector
.length ())
581 vec
<operand
*> xv
= v
.copy ();
582 result
.safe_push (xv
);
586 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
588 v
[n
] = ops_vector
[n
][i
];
589 cartesian_product (ops_vector
, result
, v
, n
+ 1);
593 /* Lower OP to two operands in case it is marked as commutative. */
595 static vec
<operand
*>
596 commutate (operand
*op
)
598 vec
<operand
*> ret
= vNULL
;
600 if (capture
*c
= dyn_cast
<capture
*> (op
))
607 vec
<operand
*> v
= commutate (c
->what
);
608 for (unsigned i
= 0; i
< v
.length (); ++i
)
610 capture
*nc
= new capture (c
->where
, v
[i
]);
616 expr
*e
= dyn_cast
<expr
*> (op
);
617 if (!e
|| e
->ops
.length () == 0)
623 vec
< vec
<operand
*> > ops_vector
= vNULL
;
624 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
625 ops_vector
.safe_push (commutate (e
->ops
[i
]));
627 auto_vec
< vec
<operand
*> > result
;
628 auto_vec
<operand
*> v (e
->ops
.length ());
629 v
.quick_grow_cleared (e
->ops
.length ());
630 cartesian_product (ops_vector
, result
, v
, 0);
633 for (unsigned i
= 0; i
< result
.length (); ++i
)
635 expr
*ne
= new expr (e
->operation
);
636 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
637 ne
->append_op (result
[i
][j
]);
641 if (!e
->is_commutative
)
644 for (unsigned i
= 0; i
< result
.length (); ++i
)
646 expr
*ne
= new expr (e
->operation
);
647 // result[i].length () is 2 since e->operation is binary
648 for (unsigned j
= result
[i
].length (); j
; --j
)
649 ne
->append_op (result
[i
][j
-1]);
656 /* Lower operations marked as commutative in the AST of S and push
657 the resulting patterns to SIMPLIFIERS. */
660 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
662 vec
<operand
*> matchers
= commutate (s
->match
);
663 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
665 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
666 s
->result
, s
->result_location
, s
->ifexpr_vec
,
667 s
->for_vec
, s
->capture_ids
);
668 simplifiers
.safe_push (ns
);
672 /* Strip conditional conversios using operator OPER from O and its
673 children if STRIP, else replace them with an unconditional convert. */
676 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
678 if (capture
*c
= dyn_cast
<capture
*> (o
))
681 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
686 expr
*e
= dyn_cast
<expr
*> (o
);
690 if (*e
->operation
== oper
)
693 return lower_opt_convert (e
->ops
[0], oper
, strip
);
695 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
696 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
700 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
701 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
702 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
707 /* Determine whether O or its children uses the conditional conversion
711 has_opt_convert (operand
*o
, enum tree_code oper
)
713 if (capture
*c
= dyn_cast
<capture
*> (o
))
716 return has_opt_convert (c
->what
, oper
);
721 expr
*e
= dyn_cast
<expr
*> (o
);
725 if (*e
->operation
== oper
)
728 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
729 if (has_opt_convert (e
->ops
[i
], oper
))
735 /* Lower conditional convert operators in O, expanding it to a vector
738 static vec
<operand
*>
739 lower_opt_convert (operand
*o
)
741 vec
<operand
*> v1
= vNULL
, v2
;
745 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
747 /* Conditional converts are lowered to a pattern with the
748 conversion and one without. The three different conditional
749 convert codes are lowered separately. */
751 for (unsigned i
= 0; i
< 3; ++i
)
754 for (unsigned j
= 0; j
< v1
.length (); ++j
)
755 if (has_opt_convert (v1
[j
], opers
[i
]))
757 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
758 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
764 for (unsigned j
= 0; j
< v2
.length (); ++j
)
765 v1
.safe_push (v2
[j
]);
772 /* Lower conditional convert operators in the AST of S and push
773 the resulting multiple patterns to SIMPLIFIERS. */
776 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
778 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
779 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
781 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
782 s
->result
, s
->result_location
, s
->ifexpr_vec
,
783 s
->for_vec
, s
->capture_ids
);
784 simplifiers
.safe_push (ns
);
788 /* In AST operand O replace operator ID with operator WITH. */
791 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
793 /* Deep-copy captures and expressions, replacing operations as
795 if (capture
*c
= dyn_cast
<capture
*> (o
))
799 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
801 else if (expr
*e
= dyn_cast
<expr
*> (o
))
803 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
805 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
806 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
810 /* For c_expr we simply record a string replacement table which is
811 applied at code-generation time. */
812 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
814 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
815 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
816 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
822 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
825 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
827 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
828 unsigned worklist_start
= 0;
829 auto_vec
<simplify
*> worklist
;
830 worklist
.safe_push (sin
);
832 /* Lower each recorded for separately, operating on the
833 set of simplifiers created by the previous one.
834 Lower inner-to-outer so inner for substitutes can refer
835 to operators replaced by outer fors. */
836 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
838 vec
<user_id
*>& ids
= for_vec
[fi
];
839 unsigned n_ids
= ids
.length ();
840 unsigned max_n_opers
= 0;
841 for (unsigned i
= 0; i
< n_ids
; ++i
)
842 if (ids
[i
]->substitutes
.length () > max_n_opers
)
843 max_n_opers
= ids
[i
]->substitutes
.length ();
845 unsigned worklist_end
= worklist
.length ();
846 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
848 simplify
*s
= worklist
[si
];
849 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
851 operand
*match_op
= s
->match
;
852 operand
*result_op
= s
->result
;
853 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
855 for (unsigned i
= 0; i
< n_ids
; ++i
)
857 user_id
*id
= ids
[i
];
858 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
859 match_op
= replace_id (match_op
, id
, oper
);
861 result_op
= replace_id (result_op
, id
, oper
);
862 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
863 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
866 simplify
*ns
= new simplify (match_op
, s
->match_location
,
867 result_op
, s
->result_location
,
868 ifexpr_vec
, vNULL
, s
->capture_ids
);
869 worklist
.safe_push (ns
);
872 worklist_start
= worklist_end
;
875 /* Copy out the result from the last for lowering. */
876 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
877 simplifiers
.safe_push (worklist
[i
]);
880 /* Lower the AST for everything in SIMPLIFIERS. */
883 lower (vec
<simplify
*>& simplifiers
)
885 auto_vec
<simplify
*> out_simplifiers0
;
886 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
887 lower_opt_convert (simplifiers
[i
], out_simplifiers0
);
889 auto_vec
<simplify
*> out_simplifiers1
;
890 for (unsigned i
= 0; i
< out_simplifiers0
.length (); ++i
)
891 lower_commutative (out_simplifiers0
[i
], out_simplifiers1
);
893 simplifiers
.truncate (0);
894 for (unsigned i
= 0; i
< out_simplifiers1
.length (); ++i
)
895 lower_for (out_simplifiers1
[i
], simplifiers
);
901 /* The decision tree built for generating GIMPLE and GENERIC pattern
902 matching code. It represents the 'match' expression of all
903 simplifies and has those as its leafs. */
905 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
909 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
915 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
917 dt_node
*append_node (dt_node
*);
918 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
919 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
920 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
921 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
923 virtual void gen (FILE *, bool) {}
925 void gen_kids (FILE *, bool);
928 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
930 struct dt_operand
: public dt_node
933 dt_operand
*match_dop
;
937 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
938 dt_operand
*parent_
= 0, unsigned pos_
= 0)
939 : dt_node (type
), op (op_
), match_dop (match_dop_
),
940 parent (parent_
), pos (pos_
) {}
942 void gen (FILE *, bool);
943 unsigned gen_predicate (FILE *, const char *, bool);
944 unsigned gen_match_op (FILE *, const char *);
946 unsigned gen_gimple_expr (FILE *);
947 unsigned gen_generic_expr (FILE *, const char *);
949 char *get_name (char *);
950 void gen_opname (char *, unsigned);
953 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
955 struct dt_simplify
: public dt_node
959 dt_operand
**indexes
;
961 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
962 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
963 indexes (indexes_
) {}
965 void gen (FILE *f
, bool);
971 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
973 return (n
->type
== dt_node::DT_OPERAND
974 || n
->type
== dt_node::DT_MATCH
);
977 /* A container for the actual decision tree. */
983 void insert (struct simplify
*, unsigned);
984 void gen_gimple (FILE *f
= stderr
);
985 void gen_generic (FILE *f
= stderr
);
986 void print (FILE *f
= stderr
);
988 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
990 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
991 unsigned pos
= 0, dt_node
*parent
= 0);
992 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
993 static bool cmp_node (dt_node
*, dt_node
*);
994 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
997 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1000 cmp_operand (operand
*o1
, operand
*o2
)
1002 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1005 if (o1
->type
== operand::OP_PREDICATE
)
1007 predicate
*p1
= as_a
<predicate
*>(o1
);
1008 predicate
*p2
= as_a
<predicate
*>(o2
);
1009 return p1
->p
== p2
->p
;
1011 else if (o1
->type
== operand::OP_EXPR
)
1013 expr
*e1
= static_cast<expr
*>(o1
);
1014 expr
*e2
= static_cast<expr
*>(o2
);
1015 return e1
->operation
== e2
->operation
;
1021 /* Compare two decision tree nodes N1 and N2 and return true if they
1025 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1027 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1030 if (n1
== n2
|| n1
->type
== dt_node::DT_TRUE
)
1033 if (n1
->type
== dt_node::DT_OPERAND
)
1034 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1035 (as_a
<dt_operand
*> (n2
))->op
);
1036 else if (n1
->type
== dt_node::DT_MATCH
)
1037 return ((as_a
<dt_operand
*> (n1
))->match_dop
1038 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1042 /* Search OPS for a decision tree node like P and return it if found. */
1045 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1047 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1048 if (decision_tree::cmp_node (ops
[i
], p
))
1054 /* Append N to the decision tree if it there is not already an existing
1058 dt_node::append_node (dt_node
*n
)
1062 kid
= decision_tree::find_node (kids
, n
);
1067 n
->level
= this->level
+ 1;
1069 unsigned len
= kids
.length ();
1071 if (len
> 1 && kids
[len
- 2]->type
== dt_node::DT_TRUE
)
1073 dt_node
*p
= kids
[len
- 2];
1074 kids
[len
- 2] = kids
[len
- 1];
1081 /* Append OP to the decision tree. */
1084 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1086 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1087 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1088 return append_node (n
);
1091 /* Append a DT_TRUE decision tree node. */
1094 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1096 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1097 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1098 return append_node (n
);
1101 /* Append a DT_MATCH decision tree node. */
1104 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1106 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1107 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1108 return append_node (n
);
1111 /* Append S to the decision tree. */
1114 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1115 dt_operand
**indexes
)
1117 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1118 return append_node (n
);
1121 /* Insert O into the decision tree and return the decision tree node found
1125 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1126 unsigned pos
, dt_node
*parent
)
1128 dt_node
*q
, *elm
= 0;
1130 if (capture
*c
= dyn_cast
<capture
*> (o
))
1132 unsigned capt_index
= c
->where
;
1134 if (indexes
[capt_index
] == 0)
1137 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1140 q
= elm
= p
->append_true_op (parent
, pos
);
1143 // get to the last capture
1144 for (operand
*what
= c
->what
;
1145 what
&& is_a
<capture
*> (what
);
1146 c
= as_a
<capture
*> (what
), what
= c
->what
)
1151 unsigned cc_index
= c
->where
;
1152 dt_operand
*match_op
= indexes
[cc_index
];
1154 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1155 elm
= decision_tree::find_node (p
->kids
, &temp
);
1159 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1160 elm
= decision_tree::find_node (p
->kids
, &temp
);
1165 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1166 elm
= decision_tree::find_node (p
->kids
, &temp
);
1170 gcc_assert (elm
->type
== dt_node::DT_TRUE
1171 || elm
->type
== dt_node::DT_OPERAND
1172 || elm
->type
== dt_node::DT_MATCH
);
1173 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1178 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1180 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1185 p
= p
->append_op (o
, parent
, pos
);
1188 if (expr
*e
= dyn_cast
<expr
*>(o
))
1190 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1191 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1197 /* Insert S into the decision tree. */
1200 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1202 if (s
->match
->type
!= operand::OP_EXPR
)
1205 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1206 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1207 p
->append_simplify (s
, pattern_no
, indexes
);
1210 /* Debug functions to dump the decision tree. */
1213 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1215 if (p
->type
== dt_node::DT_NODE
)
1216 fprintf (f
, "root");
1220 for (unsigned i
= 0; i
< indent
; i
++)
1223 if (p
->type
== dt_node::DT_OPERAND
)
1225 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1226 print_operand (dop
->op
, f
, true);
1228 else if (p
->type
== dt_node::DT_TRUE
)
1229 fprintf (f
, "true");
1230 else if (p
->type
== dt_node::DT_MATCH
)
1231 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1232 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1234 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1235 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1236 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1237 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1242 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1244 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1245 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1249 decision_tree::print (FILE *f
)
1251 return decision_tree::print_node (root
, f
);
1256 /* Code generation off the decision tree and the refered AST nodes. */
1259 is_conversion (id_base
*op
)
1261 return (*op
== CONVERT_EXPR
1263 || *op
== FLOAT_EXPR
1264 || *op
== FIX_TRUNC_EXPR
1265 || *op
== VIEW_CONVERT_EXPR
);
1268 /* Get the type to be used for generating operands of OP from the
1272 get_operand_type (id_base
*op
, const char *in_type
,
1273 const char *expr_type
,
1274 const char *other_oprnd_type
)
1276 /* Generally operands whose type does not match the type of the
1277 expression generated need to know their types but match and
1278 thus can fall back to 'other_oprnd_type'. */
1279 if (is_conversion (op
))
1280 return other_oprnd_type
;
1281 else if (*op
== REALPART_EXPR
1282 || *op
== IMAGPART_EXPR
)
1283 return other_oprnd_type
;
1284 else if (is_a
<operator_id
*> (op
)
1285 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1286 return other_oprnd_type
;
1289 /* Otherwise all types should match - choose one in order of
1296 return other_oprnd_type
;
1300 /* Generate transform code for an expression. */
1303 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1304 const char *in_type
, dt_operand
**indexes
)
1306 bool conversion_p
= is_conversion (operation
);
1307 const char *type
= expr_type
;
1310 /* If there was a type specification in the pattern use it. */
1312 else if (conversion_p
)
1313 /* For conversions we need to build the expression using the
1314 outer type passed in. */
1316 else if (*operation
== REALPART_EXPR
1317 || *operation
== IMAGPART_EXPR
)
1319 /* __real and __imag use the component type of its operand. */
1320 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1323 else if (is_a
<operator_id
*> (operation
)
1324 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1326 /* comparisons use boolean_type_node (or what gets in), but
1327 their operands need to figure out the types themselves. */
1328 sprintf (optype
, "boolean_type_node");
1333 /* Other operations are of the same type as their first operand. */
1334 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1338 fatal ("two conversions in a row");
1341 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1343 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1344 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1347 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1349 = get_operand_type (operation
, in_type
, expr_type
,
1350 i
== 0 ? NULL
: op0type
);
1351 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, indexes
);
1356 /* ??? Have another helper that is like gimple_build but may
1357 fail if seq == NULL. */
1358 fprintf (f
, " if (!seq)\n"
1360 " res = gimple_simplify (%s, %s",
1361 operation
->id
, type
);
1362 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1363 fprintf (f
, ", ops%d[%u]", depth
, i
);
1364 fprintf (f
, ", seq, valueize);\n");
1365 fprintf (f
, " if (!res) return false;\n");
1366 fprintf (f
, " }\n");
1367 fprintf (f
, " else\n");
1368 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1369 operation
->id
, type
);
1370 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1371 fprintf (f
, ", ops%d[%u]", depth
, i
);
1372 fprintf (f
, ", valueize);\n");
1376 if (operation
->kind
== id_base::CODE
)
1377 fprintf (f
, " res = fold_build%d (%s, %s",
1378 ops
.length(), operation
->id
, type
);
1380 fprintf (f
, " res = build_call_expr (builtin_decl_implicit (%s), %d",
1381 operation
->id
, ops
.length());
1382 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1383 fprintf (f
, ", ops%d[%u]", depth
, i
);
1384 fprintf (f
, ");\n");
1386 fprintf (f
, " %s = res;\n", dest
);
1390 /* Generate code for a c_expr which is either the expression inside
1391 an if statement or a sequence of statements which computes a
1392 result to be stored to DEST. */
1395 c_expr::gen_transform (FILE *f
, const char *dest
,
1396 bool, int, const char *, dt_operand
**)
1398 if (dest
&& nr_stmts
== 1)
1399 fprintf (f
, "%s = ", dest
);
1401 unsigned stmt_nr
= 1;
1402 for (unsigned i
= 0; i
< code
.length (); ++i
)
1404 const cpp_token
*token
= &code
[i
];
1406 /* Replace captures for code-gen. */
1407 if (token
->type
== CPP_ATSIGN
)
1409 const cpp_token
*n
= &code
[i
+1];
1410 if ((n
->type
== CPP_NUMBER
1411 || n
->type
== CPP_NAME
)
1412 && !(n
->flags
& PREV_WHITE
))
1414 if (token
->flags
& PREV_WHITE
)
1417 if (n
->type
== CPP_NUMBER
)
1418 id
= (const char *)n
->val
.str
.text
;
1420 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1421 fprintf (f
, "captures[%u]", (*capture_ids
)[id
]);
1427 if (token
->flags
& PREV_WHITE
)
1430 if (token
->type
== CPP_NAME
)
1432 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1434 for (j
= 0; j
< ids
.length (); ++j
)
1436 if (strcmp (id
, ids
[j
].id
) == 0)
1438 fprintf (f
, "%s", ids
[j
].oper
);
1442 if (j
< ids
.length ())
1446 /* Output the token as string. */
1447 char *tk
= (char *)cpp_token_as_text (r
, token
);
1450 if (token
->type
== CPP_SEMICOLON
)
1453 if (dest
&& stmt_nr
== nr_stmts
)
1454 fprintf (f
, "\n %s = ", dest
);
1461 /* Generate transform code for a capture. */
1464 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1465 const char *in_type
, dt_operand
**indexes
)
1467 if (what
&& is_a
<expr
*> (what
))
1469 if (indexes
[where
] == 0)
1472 sprintf (buf
, "captures[%u]", where
);
1473 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1477 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1480 /* Return the name of the operand representing the decision tree node.
1481 Use NAME as space to generate it. */
1484 dt_operand::get_name (char *name
)
1487 sprintf (name
, "t");
1488 else if (parent
->level
== 1)
1489 sprintf (name
, "op%u", pos
);
1490 else if (parent
->type
== dt_node::DT_MATCH
)
1491 return parent
->get_name (name
);
1493 sprintf (name
, "o%u%u", parent
->level
, pos
);
1497 /* Fill NAME with the operand name at position POS. */
1500 dt_operand::gen_opname (char *name
, unsigned pos
)
1503 sprintf (name
, "op%u", pos
);
1505 sprintf (name
, "o%u%u", level
, pos
);
1508 /* Generate matching code for the decision tree operand which is
1512 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1514 predicate
*p
= as_a
<predicate
*> (op
);
1516 if (p
->p
->matchers
.exists ())
1518 /* If this is a predicate generated from a pattern mangle its
1519 name and pass on the valueize hook. */
1521 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1523 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1526 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1531 /* Generate matching code for the decision tree operand which is
1535 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1537 char match_opname
[20];
1538 match_dop
->get_name (match_opname
);
1539 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1540 opname
, match_opname
, opname
, match_opname
);
1545 /* Generate GIMPLE matching code for the decision tree operand. */
1548 dt_operand::gen_gimple_expr (FILE *f
)
1550 expr
*e
= static_cast<expr
*> (op
);
1551 id_base
*id
= e
->operation
;
1552 unsigned n_ops
= e
->ops
.length ();
1554 for (unsigned i
= 0; i
< n_ops
; ++i
)
1556 char child_opname
[20];
1557 gen_opname (child_opname
, i
);
1559 if (id
->kind
== id_base::CODE
)
1561 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1562 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1564 /* ??? If this is a memory operation we can't (and should not)
1565 match this. The only sensible operand types are
1566 SSA names and invariants. */
1567 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1569 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1570 "|| is_gimple_min_invariant (%s))\n"
1571 "&& (%s = do_valueize (valueize, %s)))\n"
1572 "{\n", child_opname
, child_opname
, child_opname
,
1577 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1578 child_opname
, i
+ 1);
1581 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1583 fprintf (f
, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
1584 child_opname
, child_opname
);
1591 /* Generate GENERIC matching code for the decision tree operand. */
1594 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1596 expr
*e
= static_cast<expr
*> (op
);
1597 unsigned n_ops
= e
->ops
.length ();
1599 for (unsigned i
= 0; i
< n_ops
; ++i
)
1601 char child_opname
[20];
1602 gen_opname (child_opname
, i
);
1604 if (e
->operation
->kind
== id_base::CODE
)
1605 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1606 child_opname
, opname
, i
);
1608 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1609 child_opname
, opname
, i
);
1615 /* Generate matching code for the children of the decision tree node. */
1618 dt_node::gen_kids (FILE *f
, bool gimple
)
1620 auto_vec
<dt_operand
*> gimple_exprs
;
1621 auto_vec
<dt_operand
*> generic_exprs
;
1622 auto_vec
<dt_operand
*> fns
;
1623 auto_vec
<dt_operand
*> generic_fns
;
1624 auto_vec
<dt_operand
*> preds
;
1625 auto_vec
<dt_node
*> others
;
1626 dt_node
*true_operand
= NULL
;
1628 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1630 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1632 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1633 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1635 if (e
->ops
.length () == 0)
1636 generic_exprs
.safe_push (op
);
1637 else if (e
->operation
->kind
== id_base::FN
)
1642 generic_fns
.safe_push (op
);
1644 else if (e
->operation
->kind
== id_base::PREDICATE
)
1645 preds
.safe_push (op
);
1649 gimple_exprs
.safe_push (op
);
1651 generic_exprs
.safe_push (op
);
1654 else if (op
->op
->type
== operand::OP_PREDICATE
)
1655 others
.safe_push (kids
[i
]);
1659 else if (kids
[i
]->type
== dt_node::DT_MATCH
1660 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1661 others
.safe_push (kids
[i
]);
1662 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1663 true_operand
= kids
[i
];
1669 char *kid_opname
= buf
;
1671 unsigned exprs_len
= gimple_exprs
.length ();
1672 unsigned gexprs_len
= generic_exprs
.length ();
1673 unsigned fns_len
= fns
.length ();
1674 unsigned gfns_len
= generic_fns
.length ();
1676 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1679 gimple_exprs
[0]->get_name (kid_opname
);
1681 fns
[0]->get_name (kid_opname
);
1683 generic_fns
[0]->get_name (kid_opname
);
1685 generic_exprs
[0]->get_name (kid_opname
);
1687 fprintf (f
, "switch (TREE_CODE (%s))\n"
1691 if (exprs_len
|| fns_len
)
1693 fprintf (f
, "case SSA_NAME:\n");
1695 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1699 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1700 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1702 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1704 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1705 id_base
*op
= e
->operation
;
1706 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1707 fprintf (f
, "CASE_CONVERT:\n");
1709 fprintf (f
, "case %s:\n", op
->id
);
1711 gimple_exprs
[i
]->gen (f
, true);
1712 fprintf (f
, "break;\n"
1715 fprintf (f
, "default:;\n"
1722 fprintf (f
, "else ");
1724 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1726 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1727 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1730 for (unsigned i
= 0; i
< fns_len
; ++i
)
1732 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1733 fprintf (f
, "case %s:\n"
1734 "{\n", e
->operation
->id
);
1735 fns
[i
]->gen (f
, true);
1736 fprintf (f
, "break;\n"
1740 fprintf (f
, "default:;\n"
1745 fprintf (f
, "break;\n"
1749 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1751 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1752 id_base
*op
= e
->operation
;
1753 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1754 fprintf (f
, "CASE_CONVERT:\n");
1756 fprintf (f
, "case %s:\n", op
->id
);
1758 generic_exprs
[i
]->gen (f
, gimple
);
1759 fprintf (f
, "break;\n"
1765 fprintf (f
, "case CALL_EXPR:\n"
1767 "tree fndecl = get_callee_fndecl (%s);\n"
1768 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1769 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1772 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1774 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1775 gcc_assert (e
->operation
->kind
== id_base::FN
);
1777 fprintf (f
, "case %s:\n"
1778 "{\n", e
->operation
->id
);
1779 generic_fns
[j
]->gen (f
, false);
1780 fprintf (f
, "break;\n"
1784 fprintf (f
, "default:;\n"
1790 /* Close switch (TREE_CODE ()). */
1791 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1792 fprintf (f
, "default:;\n"
1795 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1797 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1798 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1799 preds
[i
]->get_name (kid_opname
);
1800 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1801 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1802 gimple
? "gimple" : "tree",
1803 p
->id
, kid_opname
, kid_opname
,
1804 gimple
? ", valueize" : "");
1806 for (int j
= 0; j
< p
->nargs
; ++j
)
1808 char child_opname
[20];
1809 preds
[i
]->gen_opname (child_opname
, j
);
1810 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1812 preds
[i
]->gen_kids (f
, gimple
);
1816 for (unsigned i
= 0; i
< others
.length (); ++i
)
1817 others
[i
]->gen (f
, gimple
);
1820 true_operand
->gen (f
, gimple
);
1823 /* Generate matching code for the decision tree operand. */
1826 dt_operand::gen (FILE *f
, bool gimple
)
1831 unsigned n_braces
= 0;
1833 if (type
== DT_OPERAND
)
1836 case operand::OP_PREDICATE
:
1837 n_braces
= gen_predicate (f
, opname
, gimple
);
1840 case operand::OP_EXPR
:
1842 n_braces
= gen_gimple_expr (f
);
1844 n_braces
= gen_generic_expr (f
, opname
);
1850 else if (type
== DT_TRUE
)
1852 else if (type
== DT_MATCH
)
1853 n_braces
= gen_match_op (f
, opname
);
1857 gen_kids (f
, gimple
);
1859 for (unsigned i
= 0; i
< n_braces
; ++i
)
1863 /* Generate code for the '(if ...)', '(with ..)' and actual transform
1864 step of a '(simplify ...)' or '(match ...)'. This handles everything
1865 that is not part of the decision tree (simplify->match). */
1868 dt_simplify::gen (FILE *f
, bool gimple
)
1871 output_line_directive (f
, s
->result_location
);
1872 if (s
->capture_max
>= 0)
1873 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
1874 s
->capture_max
+ 1);
1876 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1880 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
1883 unsigned n_braces
= 0;
1884 if (s
->ifexpr_vec
!= vNULL
)
1886 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1888 if_or_with
&w
= s
->ifexpr_vec
[i
];
1892 output_line_directive (f
, w
.location
);
1893 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
1898 output_line_directive (f
, w
.location
);
1899 fprintf (f
, "if (");
1900 if (i
== s
->ifexpr_vec
.length () - 1
1901 || s
->ifexpr_vec
[i
+1].is_with
)
1902 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
1911 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
1915 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
1920 while (j
< s
->ifexpr_vec
.length ()
1921 && !s
->ifexpr_vec
[j
].is_with
);
1931 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
1932 "fprintf (dump_file, \"Applying pattern ");
1933 output_line_directive (f
, s
->result_location
, true);
1934 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
1938 /* If there is no result then this is a predicate implementation. */
1939 fprintf (f
, "return true;\n");
1943 if (s
->result
->type
== operand::OP_EXPR
)
1945 expr
*e
= as_a
<expr
*> (s
->result
);
1946 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
1948 fprintf (f
, "*res_code = %s;\n", e
->operation
->id
);
1949 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
1952 snprintf (dest
, 32, " res_ops[%d]", j
);
1954 = get_operand_type (e
->operation
,
1955 "type", e
->expr_type
,
1957 ? NULL
: "TREE_TYPE (res_ops[0])");
1958 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
1961 /* Re-fold the toplevel result. It's basically an embedded
1962 gimple_build w/o actually building the stmt. */
1964 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
1965 "res_ops, valueize);\n", e
->ops
.length ());
1967 else if (s
->result
->type
== operand::OP_CAPTURE
1968 || s
->result
->type
== operand::OP_C_EXPR
)
1970 s
->result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
1971 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
1975 fprintf (f
, "return true;\n");
1979 if (s
->result
->type
== operand::OP_EXPR
)
1981 expr
*e
= as_a
<expr
*> (s
->result
);
1982 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
1983 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
1987 snprintf (dest
, 32, "res_ops[%d]", j
);
1990 fprintf (f
, " tree res_op%d;\n", j
);
1991 snprintf (dest
, 32, " res_op%d", j
);
1994 = get_operand_type (e
->operation
,
1995 "type", e
->expr_type
,
1997 ? NULL
: "TREE_TYPE (res_op0)");
1998 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2000 if (is_a
<predicate_id
*> (e
->operation
))
2001 fprintf (f
, "return true;\n");
2004 /* Re-fold the toplevel result. */
2005 if (e
->operation
->kind
== id_base::CODE
)
2006 fprintf (f
, " return fold_build%d (%s, type",
2007 e
->ops
.length (), e
->operation
->id
);
2009 fprintf (f
, " return build_call_expr "
2010 "(builtin_decl_implicit (%s), %d",
2011 e
->operation
->id
, e
->ops
.length());
2012 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2013 fprintf (f
, ", res_op%d", j
);
2014 fprintf (f
, ");\n");
2017 else if (s
->result
->type
== operand::OP_CAPTURE
2018 || s
->result
->type
== operand::OP_C_EXPR
)
2020 fprintf (f
, " tree res;\n");
2021 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2022 fprintf (f
, " return res;\n");
2028 for (unsigned i
= 0; i
< n_braces
; ++i
)
2034 /* Main entry to generate code for matching GIMPLE IL off the decision
2038 decision_tree::gen_gimple (FILE *f
)
2040 for (unsigned n
= 1; n
<= 3; ++n
)
2042 fprintf (f
, "\nstatic bool\n"
2043 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2044 " gimple_seq *seq, tree (*valueize)(tree),\n"
2045 " code_helper code, tree type");
2046 for (unsigned i
= 0; i
< n
; ++i
)
2047 fprintf (f
, ", tree op%d", i
);
2051 fprintf (f
, "switch (code.get_rep())\n"
2053 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2055 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2056 expr
*e
= static_cast<expr
*>(dop
->op
);
2057 if (e
->ops
.length () != n
)
2060 if (*e
->operation
== CONVERT_EXPR
2061 || *e
->operation
== NOP_EXPR
)
2062 fprintf (f
, "CASE_CONVERT:\n");
2064 fprintf (f
, "case %s%s:\n",
2065 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2068 dop
->gen_kids (f
, true);
2069 fprintf (f
, "break;\n");
2072 fprintf (f
, "default:;\n"
2075 fprintf (f
, "return false;\n");
2080 /* Main entry to generate code for matching GENERIC IL off the decision
2084 decision_tree::gen_generic (FILE *f
)
2086 for (unsigned n
= 1; n
<= 3; ++n
)
2088 fprintf (f
, "\ntree\n"
2089 "generic_simplify (enum tree_code code, "
2090 "tree type ATTRIBUTE_UNUSED");
2091 for (unsigned i
= 0; i
< n
; ++i
)
2092 fprintf (f
, ", tree op%d", i
);
2096 /* ??? For now reject all simplifications on operands with
2097 side-effects as we are not prepared to properly wrap
2098 omitted parts with omit_one_operand and friends. In
2099 principle we can do that automagically for a subset of
2100 transforms (and only reject the remaining cases).
2101 This fixes for example gcc.c-torture/execute/20050131-1.c. */
2102 fprintf (f
, "if ((op0 && TREE_SIDE_EFFECTS (op0))");
2103 for (unsigned i
= 1; i
< n
; ++i
)
2104 fprintf (f
, "|| (op%d && TREE_SIDE_EFFECTS (op%d))", i
, i
);
2106 " return NULL_TREE;\n");
2108 fprintf (f
, "switch (code)\n"
2110 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2112 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2113 expr
*e
= static_cast<expr
*>(dop
->op
);
2114 if (e
->ops
.length () != n
2115 /* Builtin simplifications are somewhat premature on
2116 GENERIC. The following drops patterns with outermost
2117 calls. It's easy to emit overloads for function code
2118 though if necessary. */
2119 || e
->operation
->kind
!= id_base::CODE
)
2122 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2123 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2124 fprintf (f
, "CASE_CONVERT:\n");
2126 fprintf (f
, "case %s:\n", e
->operation
->id
);
2128 dop
->gen_kids (f
, false);
2129 fprintf (f
, "break;\n"
2132 fprintf (f
, "default:;\n"
2135 fprintf (f
, "return NULL_TREE;\n");
2140 /* Output code to implement the predicate P from the decision tree DT. */
2143 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2145 fprintf (f
, "\nbool\n"
2146 "%s%s (tree t%s%s)\n"
2147 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2148 p
->nargs
> 0 ? ", tree *res_ops" : "",
2149 gimple
? ", tree (*valueize)(tree)" : "");
2150 /* Conveniently make 'type' available. */
2151 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2154 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2155 dt
.root
->gen_kids (f
, gimple
);
2157 fprintf (f
, "return false;\n"
2161 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2164 write_header (FILE *f
, const char *head
)
2166 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2167 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2169 /* Include the header instead of writing it awkwardly quoted here. */
2170 fprintf (f
, "\n#include \"%s\"\n", head
);
2180 parser (cpp_reader
*);
2183 const cpp_token
*next ();
2184 const cpp_token
*peek ();
2185 const cpp_token
*peek_ident (const char * = NULL
);
2186 const cpp_token
*expect (enum cpp_ttype
);
2187 void eat_token (enum cpp_ttype
);
2188 const char *get_string ();
2189 const char *get_ident ();
2190 void eat_ident (const char *);
2191 const char *get_number ();
2193 id_base
*parse_operation ();
2194 operand
*parse_capture (operand
*);
2195 operand
*parse_expr ();
2196 c_expr
*parse_c_expr (cpp_ttype
);
2197 operand
*parse_op ();
2199 void parse_pattern ();
2200 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2202 void parse_for (source_location
);
2203 void parse_if (source_location
);
2204 void parse_predicates (source_location
);
2207 vec
<if_or_with
> active_ifs
;
2208 vec
<vec
<user_id
*> > active_fors
;
2210 std::map
<std::string
, unsigned> *capture_ids
;
2213 vec
<simplify
*> simplifiers
;
2214 vec
<predicate_id
*> user_predicates
;
2217 /* Lexing helpers. */
2219 /* Read the next non-whitespace token from R. */
2224 const cpp_token
*token
;
2227 token
= cpp_get_token (r
);
2229 while (token
->type
== CPP_PADDING
2230 && token
->type
!= CPP_EOF
);
2234 /* Peek at the next non-whitespace token from R. */
2239 const cpp_token
*token
;
2243 token
= cpp_peek_token (r
, i
++);
2245 while (token
->type
== CPP_PADDING
2246 && token
->type
!= CPP_EOF
);
2247 /* If we peek at EOF this is a fatal error as it leaves the
2248 cpp_reader in unusable state. Assume we really wanted a
2249 token and thus this EOF is unexpected. */
2250 if (token
->type
== CPP_EOF
)
2251 fatal_at (token
, "unexpected end of file");
2255 /* Peek at the next identifier token (or return NULL if the next
2256 token is not an identifier or equal to ID if supplied). */
2259 parser::peek_ident (const char *id
)
2261 const cpp_token
*token
= peek ();
2262 if (token
->type
!= CPP_NAME
)
2268 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2269 if (strcmp (id
, t
) == 0)
2275 /* Read the next token from R and assert it is of type TK. */
2278 parser::expect (enum cpp_ttype tk
)
2280 const cpp_token
*token
= next ();
2281 if (token
->type
!= tk
)
2282 fatal_at (token
, "expected %s, got %s",
2283 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2288 /* Consume the next token from R and assert it is of type TK. */
2291 parser::eat_token (enum cpp_ttype tk
)
2296 /* Read the next token from R and assert it is of type CPP_STRING and
2297 return its value. */
2300 parser::get_string ()
2302 const cpp_token
*token
= expect (CPP_STRING
);
2303 return (const char *)token
->val
.str
.text
;
2306 /* Read the next token from R and assert it is of type CPP_NAME and
2307 return its value. */
2310 parser::get_ident ()
2312 const cpp_token
*token
= expect (CPP_NAME
);
2313 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2316 /* Eat an identifier token with value S from R. */
2319 parser::eat_ident (const char *s
)
2321 const cpp_token
*token
= peek ();
2322 const char *t
= get_ident ();
2323 if (strcmp (s
, t
) != 0)
2324 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2327 /* Read the next token from R and assert it is of type CPP_NUMBER and
2328 return its value. */
2331 parser::get_number ()
2333 const cpp_token
*token
= expect (CPP_NUMBER
);
2334 return (const char *)token
->val
.str
.text
;
2338 /* Parse the operator ID, special-casing convert?, convert1? and
2342 parser::parse_operation ()
2344 const cpp_token
*id_tok
= peek ();
2345 const char *id
= get_ident ();
2346 const cpp_token
*token
= peek ();
2347 if (strcmp (id
, "convert0") == 0)
2348 fatal_at (id_tok
, "use 'convert?' here");
2349 if (token
->type
== CPP_QUERY
2350 && !(token
->flags
& PREV_WHITE
))
2352 if (strcmp (id
, "convert") == 0)
2354 else if (strcmp (id
, "convert1") == 0)
2356 else if (strcmp (id
, "convert2") == 0)
2359 fatal_at (id_tok
, "non-convert operator conditionalized");
2360 eat_token (CPP_QUERY
);
2362 else if (strcmp (id
, "convert1") == 0
2363 || strcmp (id
, "convert2") == 0)
2364 fatal_at (id_tok
, "expected '?' after conditional operator");
2365 id_base
*op
= get_operator (id
);
2367 fatal_at (id_tok
, "unknown operator %s", id
);
2372 capture = '@'<number> */
2375 parser::parse_capture (operand
*op
)
2377 eat_token (CPP_ATSIGN
);
2378 const cpp_token
*token
= peek ();
2380 if (token
->type
== CPP_NUMBER
)
2382 else if (token
->type
== CPP_NAME
)
2385 fatal_at (token
, "expected number or identifier");
2386 unsigned next_id
= capture_ids
->size ();
2387 std::pair
<std::map
<std::string
, unsigned>::iterator
, bool> res
2388 = capture_ids
->insert (std::pair
<std::string
, unsigned>(id
, next_id
));
2389 return new capture ((*res
.first
).second
, op
);
2392 /* Parse an expression
2393 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2396 parser::parse_expr ()
2398 expr
*e
= new expr (parse_operation ());
2399 const cpp_token
*token
= peek ();
2401 bool is_commutative
= false;
2402 const char *expr_type
= NULL
;
2404 if (token
->type
== CPP_COLON
2405 && !(token
->flags
& PREV_WHITE
))
2407 eat_token (CPP_COLON
);
2409 if (token
->type
== CPP_NAME
2410 && !(token
->flags
& PREV_WHITE
))
2412 const char *s
= get_ident ();
2413 if (s
[0] == 'c' && !s
[1])
2414 is_commutative
= true;
2415 else if (s
[1] != '\0')
2418 fatal_at (token
, "flag %s not recognized", s
);
2422 fatal_at (token
, "expected flag or type specifying identifier");
2425 if (token
->type
== CPP_ATSIGN
2426 && !(token
->flags
& PREV_WHITE
))
2427 op
= parse_capture (e
);
2432 const cpp_token
*token
= peek ();
2433 if (token
->type
== CPP_CLOSE_PAREN
)
2435 if (e
->operation
->nargs
!= -1
2436 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2437 fatal_at (token
, "'%s' expects %u operands, not %u",
2438 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2441 if (e
->ops
.length () == 2)
2442 e
->is_commutative
= true;
2444 fatal_at (token
, "only binary operators or function with "
2445 "two arguments can be marked commutative");
2447 e
->expr_type
= expr_type
;
2450 e
->append_op (parse_op ());
2455 /* Lex native C code delimited by START recording the preprocessing tokens
2456 for later processing.
2457 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2460 parser::parse_c_expr (cpp_ttype start
)
2462 const cpp_token
*token
;
2465 vec
<cpp_token
> code
= vNULL
;
2466 unsigned nr_stmts
= 0;
2468 if (start
== CPP_OPEN_PAREN
)
2469 end
= CPP_CLOSE_PAREN
;
2470 else if (start
== CPP_OPEN_BRACE
)
2471 end
= CPP_CLOSE_BRACE
;
2479 /* Count brace pairs to find the end of the expr to match. */
2480 if (token
->type
== start
)
2482 else if (token
->type
== end
2486 /* This is a lame way of counting the number of statements. */
2487 if (token
->type
== CPP_SEMICOLON
)
2490 /* Record the token. */
2491 code
.safe_push (*token
);
2494 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2497 /* Parse an operand which is either an expression, a predicate or
2498 a standalone capture.
2499 op = predicate | expr | c_expr | capture */
2504 const cpp_token
*token
= peek ();
2505 struct operand
*op
= NULL
;
2506 if (token
->type
== CPP_OPEN_PAREN
)
2508 eat_token (CPP_OPEN_PAREN
);
2510 eat_token (CPP_CLOSE_PAREN
);
2512 else if (token
->type
== CPP_OPEN_BRACE
)
2514 op
= parse_c_expr (CPP_OPEN_BRACE
);
2518 /* Remaining ops are either empty or predicates */
2519 if (token
->type
== CPP_NAME
)
2521 const char *id
= get_ident ();
2522 id_base
*opr
= get_operator (id
);
2524 fatal_at (token
, "expected predicate name");
2525 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2527 if (code
->nargs
!= 0)
2528 fatal_at (token
, "using an operator with operands as predicate");
2529 /* Parse the zero-operand operator "predicates" as
2531 op
= new expr (opr
);
2533 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2534 op
= new predicate (p
);
2536 fatal_at (token
, "using an unsupported operator as predicate");
2538 if (token
->flags
& PREV_WHITE
)
2541 else if (token
->type
!= CPP_COLON
2542 && token
->type
!= CPP_ATSIGN
)
2543 fatal_at (token
, "expected expression or predicate");
2544 /* optionally followed by a capture and a predicate. */
2545 if (token
->type
== CPP_COLON
)
2546 fatal_at (token
, "not implemented: predicate on leaf operand");
2547 if (token
->type
== CPP_ATSIGN
)
2548 op
= parse_capture (op
);
2555 simplify = 'simplify' <expr> <result-op>
2557 match = 'match' <ident> <expr> [<result-op>]
2559 <result-op> = <op> | <if> | <with>
2560 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2561 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2562 and fill SIMPLIFIERS with the results. */
2565 parser::parse_simplify (source_location match_location
,
2566 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2569 /* Reset the capture map. */
2570 capture_ids
= new std::map
<std::string
, unsigned>;
2572 const cpp_token
*loc
= peek ();
2573 struct operand
*match
= parse_op ();
2574 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2575 fatal_at (loc
, "outermost expression cannot be captured");
2576 if (match
->type
== operand::OP_EXPR
2577 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2578 fatal_at (loc
, "outermost expression cannot be a predicate");
2580 const cpp_token
*token
= peek ();
2582 /* If this if is immediately closed then it is part of a predicate
2583 definition. Push it. */
2584 if (token
->type
== CPP_CLOSE_PAREN
)
2587 fatal_at (token
, "expected transform expression");
2588 simplifiers
.safe_push
2589 (new simplify (match
, match_location
, result
, token
->src_loc
,
2590 active_ifs
.copy (), active_fors
.copy (),
2595 unsigned active_ifs_len
= active_ifs
.length ();
2598 if (token
->type
== CPP_OPEN_PAREN
)
2600 source_location paren_loc
= token
->src_loc
;
2601 eat_token (CPP_OPEN_PAREN
);
2602 if (peek_ident ("if"))
2605 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2606 token
->src_loc
, false));
2607 /* If this if is immediately closed then it contains a
2608 manual matcher or is part of a predicate definition.
2610 if (peek ()->type
== CPP_CLOSE_PAREN
)
2613 fatal_at (token
, "manual transform not implemented");
2614 simplifiers
.safe_push
2615 (new simplify (match
, match_location
, result
,
2616 paren_loc
, active_ifs
.copy (),
2617 active_fors
.copy (), capture_ids
));
2620 else if (peek_ident ("with"))
2623 /* Parse (with c-expr expr) as (if-with (true) expr). */
2624 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2626 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2630 operand
*op
= result
;
2633 simplifiers
.safe_push
2634 (new simplify (match
, match_location
, op
,
2635 token
->src_loc
, active_ifs
.copy (),
2636 active_fors
.copy (), capture_ids
));
2637 eat_token (CPP_CLOSE_PAREN
);
2638 /* A "default" result closes the enclosing scope. */
2639 if (active_ifs
.length () > active_ifs_len
)
2641 eat_token (CPP_CLOSE_PAREN
);
2648 else if (token
->type
== CPP_CLOSE_PAREN
)
2650 /* Close a scope if requested. */
2651 if (active_ifs
.length () > active_ifs_len
)
2653 eat_token (CPP_CLOSE_PAREN
);
2663 fatal_at (token
, "expected match operand expression");
2664 simplifiers
.safe_push
2665 (new simplify (match
, match_location
,
2666 matcher
? result
: parse_op (),
2667 token
->src_loc
, active_ifs
.copy (),
2668 active_fors
.copy (), capture_ids
));
2669 /* A "default" result closes the enclosing scope. */
2670 if (active_ifs
.length () > active_ifs_len
)
2672 eat_token (CPP_CLOSE_PAREN
);
2682 /* Parsing of the outer control structures. */
2684 /* Parse a for expression
2685 for = '(' 'for' <subst>... <pattern> ')'
2686 subst = <ident> '(' <ident>... ')' */
2689 parser::parse_for (source_location
)
2691 vec
<user_id
*> user_ids
= vNULL
;
2692 const cpp_token
*token
;
2693 unsigned min_n_opers
= 0, max_n_opers
= 0;
2697 token
= peek_ident ();
2701 /* Insert the user defined operators into the operator hash. */
2702 const char *id
= get_ident ();
2703 user_id
*op
= new user_id (id
);
2704 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2706 fatal_at (token
, "operator already defined");
2708 user_ids
.safe_push (op
);
2710 eat_token (CPP_OPEN_PAREN
);
2713 while ((token
= peek_ident ()) != 0)
2715 const char *oper
= get_ident ();
2716 id_base
*idb
= get_operator (oper
);
2718 fatal_at (token
, "no such operator '%s'", oper
);
2719 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2720 fatal_at (token
, "conditional operators cannot be used inside for");
2724 else if (idb
->nargs
== -1)
2726 else if (idb
->nargs
!= arity
)
2727 fatal_at (token
, "operator '%s' with arity %d does not match "
2728 "others with arity %d", oper
, idb
->nargs
, arity
);
2730 op
->substitutes
.safe_push (idb
);
2733 token
= expect (CPP_CLOSE_PAREN
);
2735 unsigned nsubstitutes
= op
->substitutes
.length ();
2736 if (nsubstitutes
== 0)
2737 fatal_at (token
, "A user-defined operator must have at least "
2738 "one substitution");
2739 if (max_n_opers
== 0)
2741 min_n_opers
= nsubstitutes
;
2742 max_n_opers
= nsubstitutes
;
2746 if (nsubstitutes
% min_n_opers
!= 0
2747 && min_n_opers
% nsubstitutes
!= 0)
2748 fatal_at (token
, "All user-defined identifiers must have a "
2749 "multiple number of operator substitutions of the "
2750 "smallest number of substitutions");
2751 if (nsubstitutes
< min_n_opers
)
2752 min_n_opers
= nsubstitutes
;
2753 else if (nsubstitutes
> max_n_opers
)
2754 max_n_opers
= nsubstitutes
;
2758 unsigned n_ids
= user_ids
.length ();
2760 fatal_at (token
, "for requires at least one user-defined identifier");
2763 if (token
->type
== CPP_CLOSE_PAREN
)
2764 fatal_at (token
, "no pattern defined in for");
2766 active_fors
.safe_push (user_ids
);
2770 if (token
->type
== CPP_CLOSE_PAREN
)
2776 /* Remove user-defined operators from the hash again. */
2777 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
2778 operators
->remove_elt (user_ids
[i
]);
2781 /* Parse an outer if expression.
2782 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
2785 parser::parse_if (source_location loc
)
2787 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
2789 const cpp_token
*token
= peek ();
2790 if (token
->type
== CPP_CLOSE_PAREN
)
2791 fatal_at (token
, "no pattern defined in if");
2793 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
2796 const cpp_token
*token
= peek ();
2797 if (token
->type
== CPP_CLOSE_PAREN
)
2805 /* Parse a list of predefined predicate identifiers.
2806 preds = '(' 'define_predicates' <ident>... ')' */
2809 parser::parse_predicates (source_location
)
2813 const cpp_token
*token
= peek ();
2814 if (token
->type
!= CPP_NAME
)
2817 add_predicate (get_ident ());
2822 /* Parse outer control structures.
2823 pattern = <preds>|<for>|<if>|<simplify>|<match> */
2826 parser::parse_pattern ()
2828 /* All clauses start with '('. */
2829 eat_token (CPP_OPEN_PAREN
);
2830 const cpp_token
*token
= peek ();
2831 const char *id
= get_ident ();
2832 if (strcmp (id
, "simplify") == 0)
2833 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
2834 else if (strcmp (id
, "match") == 0)
2836 bool with_args
= false;
2837 if (peek ()->type
== CPP_OPEN_PAREN
)
2839 eat_token (CPP_OPEN_PAREN
);
2842 const char *name
= get_ident ();
2843 id_base
*id
= get_operator (name
);
2847 p
= add_predicate (name
);
2848 user_predicates
.safe_push (p
);
2850 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
2853 fatal_at (token
, "cannot add a match to a non-predicate ID");
2854 /* Parse (match <id> <arg>... (match-expr)) here. */
2859 while (peek ()->type
== CPP_ATSIGN
)
2860 e
->append_op (parse_capture (NULL
));
2861 eat_token (CPP_CLOSE_PAREN
);
2864 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
2865 || (!e
&& p
->nargs
!= 0)))
2866 fatal_at (token
, "non-matching number of match operands");
2867 p
->nargs
= e
? e
->ops
.length () : 0;
2868 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
2870 else if (strcmp (id
, "for") == 0)
2871 parse_for (token
->src_loc
);
2872 else if (strcmp (id
, "if") == 0)
2873 parse_if (token
->src_loc
);
2874 else if (strcmp (id
, "define_predicates") == 0)
2876 if (active_ifs
.length () > 0
2877 || active_fors
.length () > 0)
2878 fatal_at (token
, "define_predicates inside if or for is not supported");
2879 parse_predicates (token
->src_loc
);
2882 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
2883 active_ifs
.length () == 0 && active_fors
.length () == 0
2884 ? "'define_predicates', " : "");
2886 eat_token (CPP_CLOSE_PAREN
);
2889 /* Main entry of the parser. Repeatedly parse outer control structures. */
2891 parser::parser (cpp_reader
*r_
)
2895 active_fors
= vNULL
;
2896 simplifiers
= vNULL
;
2897 user_predicates
= vNULL
;
2899 const cpp_token
*token
= next ();
2900 while (token
->type
!= CPP_EOF
)
2902 _cpp_backup_tokens (r
, 1);
2909 /* Helper for the linemap code. */
2912 round_alloc_size (size_t s
)
2918 /* The genmatch generator progam. It reads from a pattern description
2919 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
2922 main (int argc
, char **argv
)
2926 progname
= "genmatch";
2932 bool verbose
= false;
2933 char *input
= argv
[argc
-1];
2934 for (int i
= 1; i
< argc
- 1; ++i
)
2936 if (strcmp (argv
[i
], "--gimple") == 0)
2938 else if (strcmp (argv
[i
], "--generic") == 0)
2940 else if (strcmp (argv
[i
], "-v") == 0)
2944 fprintf (stderr
, "Usage: genmatch "
2945 "[--gimple] [--generic] [-v] input\n");
2950 line_table
= XCNEW (struct line_maps
);
2951 linemap_init (line_table
, 0);
2952 line_table
->reallocator
= xrealloc
;
2953 line_table
->round_alloc_size
= round_alloc_size
;
2955 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
2956 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
2957 cb
->error
= error_cb
;
2959 if (!cpp_read_main_file (r
, input
))
2961 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
2962 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
2964 /* Pre-seed operators. */
2965 operators
= new hash_table
<id_base
> (1024);
2966 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
2967 add_operator (SYM, # SYM, # TYPE, NARGS);
2968 #define END_OF_BASE_TREE_CODES
2970 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
2971 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
2972 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
2973 #undef END_OF_BASE_TREE_CODES
2976 /* Pre-seed builtin functions.
2977 ??? Cannot use N (name) as that is targetm.emultls.get_address
2978 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
2979 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
2980 add_builtin (ENUM, # ENUM);
2981 #include "builtins.def"
2988 write_header (stdout
, "gimple-match-head.c");
2990 write_header (stdout
, "generic-match-head.c");
2992 /* Go over all predicates defined with patterns and perform
2993 lowering and code generation. */
2994 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
2996 predicate_id
*pred
= p
.user_predicates
[i
];
2997 lower (pred
->matchers
);
3000 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3001 print_matches (pred
->matchers
[i
]);
3004 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3005 dt
.insert (pred
->matchers
[i
], i
);
3010 write_predicate (stdout
, pred
, dt
, gimple
);
3013 /* Lower the main simplifiers and generate code for them. */
3014 lower (p
.simplifiers
);
3017 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3018 print_matches (p
.simplifiers
[i
]);
3021 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3022 dt
.insert (p
.simplifiers
[i
], i
);
3028 dt
.gen_gimple (stdout
);
3030 dt
.gen_generic (stdout
);
3033 cpp_finish (r
, NULL
);