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_loc (loc, %s, %s",
1378 ops
.length(), operation
->id
, type
);
1380 fprintf (f
, " res = build_call_expr_loc (loc, "
1381 "builtin_decl_implicit (%s), %d",
1382 operation
->id
, ops
.length());
1383 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1384 fprintf (f
, ", ops%d[%u]", depth
, i
);
1385 fprintf (f
, ");\n");
1387 fprintf (f
, " %s = res;\n", dest
);
1391 /* Generate code for a c_expr which is either the expression inside
1392 an if statement or a sequence of statements which computes a
1393 result to be stored to DEST. */
1396 c_expr::gen_transform (FILE *f
, const char *dest
,
1397 bool, int, const char *, dt_operand
**)
1399 if (dest
&& nr_stmts
== 1)
1400 fprintf (f
, "%s = ", dest
);
1402 unsigned stmt_nr
= 1;
1403 for (unsigned i
= 0; i
< code
.length (); ++i
)
1405 const cpp_token
*token
= &code
[i
];
1407 /* Replace captures for code-gen. */
1408 if (token
->type
== CPP_ATSIGN
)
1410 const cpp_token
*n
= &code
[i
+1];
1411 if ((n
->type
== CPP_NUMBER
1412 || n
->type
== CPP_NAME
)
1413 && !(n
->flags
& PREV_WHITE
))
1415 if (token
->flags
& PREV_WHITE
)
1418 if (n
->type
== CPP_NUMBER
)
1419 id
= (const char *)n
->val
.str
.text
;
1421 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1422 fprintf (f
, "captures[%u]", (*capture_ids
)[id
]);
1428 if (token
->flags
& PREV_WHITE
)
1431 if (token
->type
== CPP_NAME
)
1433 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1435 for (j
= 0; j
< ids
.length (); ++j
)
1437 if (strcmp (id
, ids
[j
].id
) == 0)
1439 fprintf (f
, "%s", ids
[j
].oper
);
1443 if (j
< ids
.length ())
1447 /* Output the token as string. */
1448 char *tk
= (char *)cpp_token_as_text (r
, token
);
1451 if (token
->type
== CPP_SEMICOLON
)
1454 if (dest
&& stmt_nr
== nr_stmts
)
1455 fprintf (f
, "\n %s = ", dest
);
1462 /* Generate transform code for a capture. */
1465 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1466 const char *in_type
, dt_operand
**indexes
)
1468 if (what
&& is_a
<expr
*> (what
))
1470 if (indexes
[where
] == 0)
1473 sprintf (buf
, "captures[%u]", where
);
1474 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1478 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1481 /* Return the name of the operand representing the decision tree node.
1482 Use NAME as space to generate it. */
1485 dt_operand::get_name (char *name
)
1488 sprintf (name
, "t");
1489 else if (parent
->level
== 1)
1490 sprintf (name
, "op%u", pos
);
1491 else if (parent
->type
== dt_node::DT_MATCH
)
1492 return parent
->get_name (name
);
1494 sprintf (name
, "o%u%u", parent
->level
, pos
);
1498 /* Fill NAME with the operand name at position POS. */
1501 dt_operand::gen_opname (char *name
, unsigned pos
)
1504 sprintf (name
, "op%u", pos
);
1506 sprintf (name
, "o%u%u", level
, pos
);
1509 /* Generate matching code for the decision tree operand which is
1513 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1515 predicate
*p
= as_a
<predicate
*> (op
);
1517 if (p
->p
->matchers
.exists ())
1519 /* If this is a predicate generated from a pattern mangle its
1520 name and pass on the valueize hook. */
1522 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1524 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1527 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1532 /* Generate matching code for the decision tree operand which is
1536 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1538 char match_opname
[20];
1539 match_dop
->get_name (match_opname
);
1540 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1541 opname
, match_opname
, opname
, match_opname
);
1546 /* Generate GIMPLE matching code for the decision tree operand. */
1549 dt_operand::gen_gimple_expr (FILE *f
)
1551 expr
*e
= static_cast<expr
*> (op
);
1552 id_base
*id
= e
->operation
;
1553 unsigned n_ops
= e
->ops
.length ();
1555 for (unsigned i
= 0; i
< n_ops
; ++i
)
1557 char child_opname
[20];
1558 gen_opname (child_opname
, i
);
1560 if (id
->kind
== id_base::CODE
)
1562 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1563 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1565 /* ??? If this is a memory operation we can't (and should not)
1566 match this. The only sensible operand types are
1567 SSA names and invariants. */
1568 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1570 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1571 "|| is_gimple_min_invariant (%s))\n"
1572 "&& (%s = do_valueize (valueize, %s)))\n"
1573 "{\n", child_opname
, child_opname
, child_opname
,
1578 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1579 child_opname
, i
+ 1);
1582 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1584 fprintf (f
, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
1585 child_opname
, child_opname
);
1592 /* Generate GENERIC matching code for the decision tree operand. */
1595 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1597 expr
*e
= static_cast<expr
*> (op
);
1598 unsigned n_ops
= e
->ops
.length ();
1600 for (unsigned i
= 0; i
< n_ops
; ++i
)
1602 char child_opname
[20];
1603 gen_opname (child_opname
, i
);
1605 if (e
->operation
->kind
== id_base::CODE
)
1606 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1607 child_opname
, opname
, i
);
1609 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1610 child_opname
, opname
, i
);
1616 /* Generate matching code for the children of the decision tree node. */
1619 dt_node::gen_kids (FILE *f
, bool gimple
)
1621 auto_vec
<dt_operand
*> gimple_exprs
;
1622 auto_vec
<dt_operand
*> generic_exprs
;
1623 auto_vec
<dt_operand
*> fns
;
1624 auto_vec
<dt_operand
*> generic_fns
;
1625 auto_vec
<dt_operand
*> preds
;
1626 auto_vec
<dt_node
*> others
;
1627 dt_node
*true_operand
= NULL
;
1629 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1631 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1633 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1634 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1636 if (e
->ops
.length () == 0)
1637 generic_exprs
.safe_push (op
);
1638 else if (e
->operation
->kind
== id_base::FN
)
1643 generic_fns
.safe_push (op
);
1645 else if (e
->operation
->kind
== id_base::PREDICATE
)
1646 preds
.safe_push (op
);
1650 gimple_exprs
.safe_push (op
);
1652 generic_exprs
.safe_push (op
);
1655 else if (op
->op
->type
== operand::OP_PREDICATE
)
1656 others
.safe_push (kids
[i
]);
1660 else if (kids
[i
]->type
== dt_node::DT_MATCH
1661 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1662 others
.safe_push (kids
[i
]);
1663 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1664 true_operand
= kids
[i
];
1670 char *kid_opname
= buf
;
1672 unsigned exprs_len
= gimple_exprs
.length ();
1673 unsigned gexprs_len
= generic_exprs
.length ();
1674 unsigned fns_len
= fns
.length ();
1675 unsigned gfns_len
= generic_fns
.length ();
1677 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1680 gimple_exprs
[0]->get_name (kid_opname
);
1682 fns
[0]->get_name (kid_opname
);
1684 generic_fns
[0]->get_name (kid_opname
);
1686 generic_exprs
[0]->get_name (kid_opname
);
1688 fprintf (f
, "switch (TREE_CODE (%s))\n"
1692 if (exprs_len
|| fns_len
)
1694 fprintf (f
, "case SSA_NAME:\n");
1696 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1700 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1701 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1703 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1705 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1706 id_base
*op
= e
->operation
;
1707 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1708 fprintf (f
, "CASE_CONVERT:\n");
1710 fprintf (f
, "case %s:\n", op
->id
);
1712 gimple_exprs
[i
]->gen (f
, true);
1713 fprintf (f
, "break;\n"
1716 fprintf (f
, "default:;\n"
1723 fprintf (f
, "else ");
1725 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1727 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1728 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1731 for (unsigned i
= 0; i
< fns_len
; ++i
)
1733 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1734 fprintf (f
, "case %s:\n"
1735 "{\n", e
->operation
->id
);
1736 fns
[i
]->gen (f
, true);
1737 fprintf (f
, "break;\n"
1741 fprintf (f
, "default:;\n"
1746 fprintf (f
, "break;\n"
1750 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1752 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1753 id_base
*op
= e
->operation
;
1754 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1755 fprintf (f
, "CASE_CONVERT:\n");
1757 fprintf (f
, "case %s:\n", op
->id
);
1759 generic_exprs
[i
]->gen (f
, gimple
);
1760 fprintf (f
, "break;\n"
1766 fprintf (f
, "case CALL_EXPR:\n"
1768 "tree fndecl = get_callee_fndecl (%s);\n"
1769 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1770 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1773 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1775 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1776 gcc_assert (e
->operation
->kind
== id_base::FN
);
1778 fprintf (f
, "case %s:\n"
1779 "{\n", e
->operation
->id
);
1780 generic_fns
[j
]->gen (f
, false);
1781 fprintf (f
, "break;\n"
1785 fprintf (f
, "default:;\n"
1791 /* Close switch (TREE_CODE ()). */
1792 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1793 fprintf (f
, "default:;\n"
1796 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1798 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1799 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1800 preds
[i
]->get_name (kid_opname
);
1801 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1802 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1803 gimple
? "gimple" : "tree",
1804 p
->id
, kid_opname
, kid_opname
,
1805 gimple
? ", valueize" : "");
1807 for (int j
= 0; j
< p
->nargs
; ++j
)
1809 char child_opname
[20];
1810 preds
[i
]->gen_opname (child_opname
, j
);
1811 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1813 preds
[i
]->gen_kids (f
, gimple
);
1817 for (unsigned i
= 0; i
< others
.length (); ++i
)
1818 others
[i
]->gen (f
, gimple
);
1821 true_operand
->gen (f
, gimple
);
1824 /* Generate matching code for the decision tree operand. */
1827 dt_operand::gen (FILE *f
, bool gimple
)
1832 unsigned n_braces
= 0;
1834 if (type
== DT_OPERAND
)
1837 case operand::OP_PREDICATE
:
1838 n_braces
= gen_predicate (f
, opname
, gimple
);
1841 case operand::OP_EXPR
:
1843 n_braces
= gen_gimple_expr (f
);
1845 n_braces
= gen_generic_expr (f
, opname
);
1851 else if (type
== DT_TRUE
)
1853 else if (type
== DT_MATCH
)
1854 n_braces
= gen_match_op (f
, opname
);
1858 gen_kids (f
, gimple
);
1860 for (unsigned i
= 0; i
< n_braces
; ++i
)
1865 /* For GENERIC we have to take care of wrapping multiple-used
1866 expressions with side-effects in save_expr and preserve side-effects
1867 of expressions with omit_one_operand. Analyze captures in
1868 match, result and with expressions and perform early-outs
1869 on the outermost match expression operands for cases we cannot
1874 capture_info (simplify
*s
);
1875 void walk_match (operand
*o
, unsigned toplevel_arg
, bool);
1876 void walk_result (operand
*o
, bool);
1877 void walk_c_expr (c_expr
*);
1883 bool force_no_side_effects_p
;
1884 unsigned long toplevel_msk
;
1885 int result_use_count
;
1888 auto_vec
<cinfo
> info
;
1889 unsigned long force_no_side_effects
;
1892 /* Analyze captures in S. */
1894 capture_info::capture_info (simplify
*s
)
1898 || ((e
= dyn_cast
<expr
*> (s
->result
))
1899 && is_a
<predicate_id
*> (e
->operation
)))
1901 force_no_side_effects
= -1;
1905 force_no_side_effects
= 0;
1906 info
.safe_grow_cleared (s
->capture_max
+ 1);
1907 e
= as_a
<expr
*> (s
->match
);
1908 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1909 walk_match (e
->ops
[i
], i
, false);
1911 walk_result (s
->result
, false);
1913 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1914 if (s
->ifexpr_vec
[i
].is_with
)
1915 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1918 /* Analyze captures in the match expression piece O. */
1921 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
, bool conditional_p
)
1923 if (capture
*c
= dyn_cast
<capture
*> (o
))
1925 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1926 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1927 /* Mark expr (non-leaf) captures and recurse. */
1929 && is_a
<expr
*> (c
->what
))
1931 info
[c
->where
].expr_p
= true;
1932 walk_match (c
->what
, toplevel_arg
, conditional_p
);
1935 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1937 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1939 bool cond_p
= conditional_p
;
1941 && *e
->operation
== COND_EXPR
)
1943 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1944 || *e
->operation
== TRUTH_ORIF_EXPR
)
1946 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
);
1949 else if (is_a
<predicate
*> (o
))
1951 /* Mark non-captured leafs toplevel arg for checking. */
1952 force_no_side_effects
|= 1 << toplevel_arg
;
1958 /* Analyze captures in the result expression piece O. */
1961 capture_info::walk_result (operand
*o
, bool conditional_p
)
1963 if (capture
*c
= dyn_cast
<capture
*> (o
))
1965 info
[c
->where
].result_use_count
++;
1966 /* If we substitute an expression capture we don't know
1967 which captures this will end up using (well, we don't
1968 compute that). Force the uses to be side-effect free
1969 which means forcing the toplevels that reach the
1970 expression side-effect free. */
1971 if (info
[c
->where
].expr_p
)
1972 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
1973 /* Mark CSE capture capture uses as forced to have
1976 && is_a
<expr
*> (c
->what
))
1978 info
[c
->where
].cse_p
= true;
1979 walk_result (c
->what
, true);
1982 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1984 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1986 bool cond_p
= conditional_p
;
1988 && *e
->operation
== COND_EXPR
)
1990 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1991 || *e
->operation
== TRUTH_ORIF_EXPR
)
1993 walk_result (e
->ops
[i
], cond_p
);
1996 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2002 /* Look for captures in the C expr E. */
2005 capture_info::walk_c_expr (c_expr
*e
)
2007 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
2008 unsigned p_depth
= 0;
2009 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2011 const cpp_token
*t
= &e
->code
[i
];
2012 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2013 if (t
->type
== CPP_NAME
2014 && strcmp ((const char *)CPP_HASHNODE
2015 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2016 && n
->type
== CPP_OPEN_PAREN
)
2018 else if (t
->type
== CPP_CLOSE_PAREN
2021 else if (p_depth
== 0
2022 && t
->type
== CPP_ATSIGN
2023 && (n
->type
== CPP_NUMBER
2024 || n
->type
== CPP_NAME
)
2025 && !(n
->flags
& PREV_WHITE
))
2028 if (n
->type
== CPP_NUMBER
)
2029 id
= (const char *)n
->val
.str
.text
;
2031 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2032 info
[(*e
->capture_ids
)[id
]].force_no_side_effects_p
= true;
2038 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2039 step of a '(simplify ...)' or '(match ...)'. This handles everything
2040 that is not part of the decision tree (simplify->match). */
2043 dt_simplify::gen (FILE *f
, bool gimple
)
2046 output_line_directive (f
, s
->result_location
);
2047 if (s
->capture_max
>= 0)
2048 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2049 s
->capture_max
+ 1);
2051 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2055 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2058 unsigned n_braces
= 0;
2059 if (s
->ifexpr_vec
!= vNULL
)
2061 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2063 if_or_with
&w
= s
->ifexpr_vec
[i
];
2067 output_line_directive (f
, w
.location
);
2068 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2073 output_line_directive (f
, w
.location
);
2074 fprintf (f
, "if (");
2075 if (i
== s
->ifexpr_vec
.length () - 1
2076 || s
->ifexpr_vec
[i
+1].is_with
)
2077 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2086 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2090 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2095 while (j
< s
->ifexpr_vec
.length ()
2096 && !s
->ifexpr_vec
[j
].is_with
);
2106 /* Analyze captures and perform early-outs on the incoming arguments
2107 that cover cases we cannot handle. */
2108 capture_info
cinfo (s
);
2112 && !((e
= dyn_cast
<expr
*> (s
->result
))
2113 && is_a
<predicate_id
*> (e
->operation
)))
2115 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2116 if (cinfo
.force_no_side_effects
& (1 << i
))
2117 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2118 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2119 if (cinfo
.info
[i
].cse_p
)
2121 else if (cinfo
.info
[i
].force_no_side_effects_p
2122 && (cinfo
.info
[i
].toplevel_msk
2123 & cinfo
.force_no_side_effects
) == 0)
2124 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2125 "return NULL_TREE;\n", i
);
2126 else if ((cinfo
.info
[i
].toplevel_msk
2127 & cinfo
.force_no_side_effects
) != 0)
2128 /* Mark capture as having no side-effects if we had to verify
2129 that via forced toplevel operand checks. */
2130 cinfo
.info
[i
].force_no_side_effects_p
= true;
2133 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2134 "fprintf (dump_file, \"Applying pattern ");
2135 output_line_directive (f
, s
->result_location
, true);
2136 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2138 operand
*result
= s
->result
;
2141 /* If there is no result then this is a predicate implementation. */
2142 fprintf (f
, "return true;\n");
2146 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2147 in outermost position). */
2148 if (result
->type
== operand::OP_EXPR
2149 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2150 result
= as_a
<expr
*> (result
)->ops
[0];
2151 if (result
->type
== operand::OP_EXPR
)
2153 expr
*e
= as_a
<expr
*> (result
);
2154 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2156 fprintf (f
, "*res_code = %s;\n", e
->operation
->id
);
2157 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2160 snprintf (dest
, 32, " res_ops[%d]", j
);
2162 = get_operand_type (e
->operation
,
2163 "type", e
->expr_type
,
2165 ? NULL
: "TREE_TYPE (res_ops[0])");
2166 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
2169 /* Re-fold the toplevel result. It's basically an embedded
2170 gimple_build w/o actually building the stmt. */
2172 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2173 "res_ops, valueize);\n", e
->ops
.length ());
2175 else if (result
->type
== operand::OP_CAPTURE
2176 || result
->type
== operand::OP_C_EXPR
)
2178 result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
2179 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2183 fprintf (f
, "return true;\n");
2187 bool is_predicate
= false;
2188 if (result
->type
== operand::OP_EXPR
)
2190 expr
*e
= as_a
<expr
*> (result
);
2191 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2192 /* Search for captures used multiple times in the result expression
2193 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2195 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2197 if (!cinfo
.info
[i
].force_no_side_effects_p
2198 && cinfo
.info
[i
].result_use_count
> 1)
2199 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2200 " captures[%d] = save_expr (captures[%d]);\n",
2203 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2207 snprintf (dest
, 32, "res_ops[%d]", j
);
2210 fprintf (f
, " tree res_op%d;\n", j
);
2211 snprintf (dest
, 32, " res_op%d", j
);
2214 = get_operand_type (e
->operation
,
2215 "type", e
->expr_type
,
2217 ? NULL
: "TREE_TYPE (res_op0)");
2218 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2221 fprintf (f
, "return true;\n");
2224 fprintf (f
, " tree res;\n");
2225 /* Re-fold the toplevel result. Use non_lvalue to
2226 build NON_LVALUE_EXPRs so they get properly
2227 ignored when in GIMPLE form. */
2228 if (*e
->operation
== NON_LVALUE_EXPR
)
2229 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2232 if (e
->operation
->kind
== id_base::CODE
)
2233 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2234 e
->ops
.length (), e
->operation
->id
);
2236 fprintf (f
, " res = build_call_expr_loc "
2237 "(loc, builtin_decl_implicit (%s), %d",
2238 e
->operation
->id
, e
->ops
.length());
2239 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2240 fprintf (f
, ", res_op%d", j
);
2241 fprintf (f
, ");\n");
2245 else if (result
->type
== operand::OP_CAPTURE
2246 || result
->type
== operand::OP_C_EXPR
)
2249 fprintf (f
, " tree res;\n");
2250 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2256 /* Search for captures not used in the result expression and dependent
2257 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2258 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2260 if (!cinfo
.info
[i
].force_no_side_effects_p
2261 && !cinfo
.info
[i
].expr_p
2262 && cinfo
.info
[i
].result_use_count
== 0)
2263 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2264 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2265 " fold_ignored_result (captures[%d]), res);\n",
2268 fprintf (f
, " return res;\n");
2272 for (unsigned i
= 0; i
< n_braces
; ++i
)
2278 /* Main entry to generate code for matching GIMPLE IL off the decision
2282 decision_tree::gen_gimple (FILE *f
)
2284 for (unsigned n
= 1; n
<= 3; ++n
)
2286 fprintf (f
, "\nstatic bool\n"
2287 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2288 " gimple_seq *seq, tree (*valueize)(tree),\n"
2289 " code_helper code, tree type");
2290 for (unsigned i
= 0; i
< n
; ++i
)
2291 fprintf (f
, ", tree op%d", i
);
2295 fprintf (f
, "switch (code.get_rep())\n"
2297 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2299 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2300 expr
*e
= static_cast<expr
*>(dop
->op
);
2301 if (e
->ops
.length () != n
)
2304 if (*e
->operation
== CONVERT_EXPR
2305 || *e
->operation
== NOP_EXPR
)
2306 fprintf (f
, "CASE_CONVERT:\n");
2308 fprintf (f
, "case %s%s:\n",
2309 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2312 dop
->gen_kids (f
, true);
2313 fprintf (f
, "break;\n");
2316 fprintf (f
, "default:;\n"
2319 fprintf (f
, "return false;\n");
2324 /* Main entry to generate code for matching GENERIC IL off the decision
2328 decision_tree::gen_generic (FILE *f
)
2330 for (unsigned n
= 1; n
<= 3; ++n
)
2332 fprintf (f
, "\ntree\n"
2333 "generic_simplify (location_t loc, enum tree_code code, "
2334 "tree type ATTRIBUTE_UNUSED");
2335 for (unsigned i
= 0; i
< n
; ++i
)
2336 fprintf (f
, ", tree op%d", i
);
2340 fprintf (f
, "switch (code)\n"
2342 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2344 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2345 expr
*e
= static_cast<expr
*>(dop
->op
);
2346 if (e
->ops
.length () != n
2347 /* Builtin simplifications are somewhat premature on
2348 GENERIC. The following drops patterns with outermost
2349 calls. It's easy to emit overloads for function code
2350 though if necessary. */
2351 || e
->operation
->kind
!= id_base::CODE
)
2354 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2355 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2356 fprintf (f
, "CASE_CONVERT:\n");
2358 fprintf (f
, "case %s:\n", e
->operation
->id
);
2360 dop
->gen_kids (f
, false);
2361 fprintf (f
, "break;\n"
2364 fprintf (f
, "default:;\n"
2367 fprintf (f
, "return NULL_TREE;\n");
2372 /* Output code to implement the predicate P from the decision tree DT. */
2375 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2377 fprintf (f
, "\nbool\n"
2378 "%s%s (tree t%s%s)\n"
2379 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2380 p
->nargs
> 0 ? ", tree *res_ops" : "",
2381 gimple
? ", tree (*valueize)(tree)" : "");
2382 /* Conveniently make 'type' available. */
2383 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2386 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2387 dt
.root
->gen_kids (f
, gimple
);
2389 fprintf (f
, "return false;\n"
2393 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2396 write_header (FILE *f
, const char *head
)
2398 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2399 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2401 /* Include the header instead of writing it awkwardly quoted here. */
2402 fprintf (f
, "\n#include \"%s\"\n", head
);
2412 parser (cpp_reader
*);
2415 const cpp_token
*next ();
2416 const cpp_token
*peek ();
2417 const cpp_token
*peek_ident (const char * = NULL
);
2418 const cpp_token
*expect (enum cpp_ttype
);
2419 void eat_token (enum cpp_ttype
);
2420 const char *get_string ();
2421 const char *get_ident ();
2422 void eat_ident (const char *);
2423 const char *get_number ();
2425 id_base
*parse_operation ();
2426 operand
*parse_capture (operand
*);
2427 operand
*parse_expr ();
2428 c_expr
*parse_c_expr (cpp_ttype
);
2429 operand
*parse_op ();
2431 void parse_pattern ();
2432 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2434 void parse_for (source_location
);
2435 void parse_if (source_location
);
2436 void parse_predicates (source_location
);
2439 vec
<if_or_with
> active_ifs
;
2440 vec
<vec
<user_id
*> > active_fors
;
2442 std::map
<std::string
, unsigned> *capture_ids
;
2445 vec
<simplify
*> simplifiers
;
2446 vec
<predicate_id
*> user_predicates
;
2449 /* Lexing helpers. */
2451 /* Read the next non-whitespace token from R. */
2456 const cpp_token
*token
;
2459 token
= cpp_get_token (r
);
2461 while (token
->type
== CPP_PADDING
2462 && token
->type
!= CPP_EOF
);
2466 /* Peek at the next non-whitespace token from R. */
2471 const cpp_token
*token
;
2475 token
= cpp_peek_token (r
, i
++);
2477 while (token
->type
== CPP_PADDING
2478 && token
->type
!= CPP_EOF
);
2479 /* If we peek at EOF this is a fatal error as it leaves the
2480 cpp_reader in unusable state. Assume we really wanted a
2481 token and thus this EOF is unexpected. */
2482 if (token
->type
== CPP_EOF
)
2483 fatal_at (token
, "unexpected end of file");
2487 /* Peek at the next identifier token (or return NULL if the next
2488 token is not an identifier or equal to ID if supplied). */
2491 parser::peek_ident (const char *id
)
2493 const cpp_token
*token
= peek ();
2494 if (token
->type
!= CPP_NAME
)
2500 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2501 if (strcmp (id
, t
) == 0)
2507 /* Read the next token from R and assert it is of type TK. */
2510 parser::expect (enum cpp_ttype tk
)
2512 const cpp_token
*token
= next ();
2513 if (token
->type
!= tk
)
2514 fatal_at (token
, "expected %s, got %s",
2515 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2520 /* Consume the next token from R and assert it is of type TK. */
2523 parser::eat_token (enum cpp_ttype tk
)
2528 /* Read the next token from R and assert it is of type CPP_STRING and
2529 return its value. */
2532 parser::get_string ()
2534 const cpp_token
*token
= expect (CPP_STRING
);
2535 return (const char *)token
->val
.str
.text
;
2538 /* Read the next token from R and assert it is of type CPP_NAME and
2539 return its value. */
2542 parser::get_ident ()
2544 const cpp_token
*token
= expect (CPP_NAME
);
2545 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2548 /* Eat an identifier token with value S from R. */
2551 parser::eat_ident (const char *s
)
2553 const cpp_token
*token
= peek ();
2554 const char *t
= get_ident ();
2555 if (strcmp (s
, t
) != 0)
2556 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2559 /* Read the next token from R and assert it is of type CPP_NUMBER and
2560 return its value. */
2563 parser::get_number ()
2565 const cpp_token
*token
= expect (CPP_NUMBER
);
2566 return (const char *)token
->val
.str
.text
;
2570 /* Parse the operator ID, special-casing convert?, convert1? and
2574 parser::parse_operation ()
2576 const cpp_token
*id_tok
= peek ();
2577 const char *id
= get_ident ();
2578 const cpp_token
*token
= peek ();
2579 if (strcmp (id
, "convert0") == 0)
2580 fatal_at (id_tok
, "use 'convert?' here");
2581 if (token
->type
== CPP_QUERY
2582 && !(token
->flags
& PREV_WHITE
))
2584 if (strcmp (id
, "convert") == 0)
2586 else if (strcmp (id
, "convert1") == 0)
2588 else if (strcmp (id
, "convert2") == 0)
2591 fatal_at (id_tok
, "non-convert operator conditionalized");
2592 eat_token (CPP_QUERY
);
2594 else if (strcmp (id
, "convert1") == 0
2595 || strcmp (id
, "convert2") == 0)
2596 fatal_at (id_tok
, "expected '?' after conditional operator");
2597 id_base
*op
= get_operator (id
);
2599 fatal_at (id_tok
, "unknown operator %s", id
);
2604 capture = '@'<number> */
2607 parser::parse_capture (operand
*op
)
2609 eat_token (CPP_ATSIGN
);
2610 const cpp_token
*token
= peek ();
2612 if (token
->type
== CPP_NUMBER
)
2614 else if (token
->type
== CPP_NAME
)
2617 fatal_at (token
, "expected number or identifier");
2618 unsigned next_id
= capture_ids
->size ();
2619 std::pair
<std::map
<std::string
, unsigned>::iterator
, bool> res
2620 = capture_ids
->insert (std::pair
<std::string
, unsigned>(id
, next_id
));
2621 return new capture ((*res
.first
).second
, op
);
2624 /* Parse an expression
2625 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2628 parser::parse_expr ()
2630 expr
*e
= new expr (parse_operation ());
2631 const cpp_token
*token
= peek ();
2633 bool is_commutative
= false;
2634 const char *expr_type
= NULL
;
2636 if (token
->type
== CPP_COLON
2637 && !(token
->flags
& PREV_WHITE
))
2639 eat_token (CPP_COLON
);
2641 if (token
->type
== CPP_NAME
2642 && !(token
->flags
& PREV_WHITE
))
2644 const char *s
= get_ident ();
2645 if (s
[0] == 'c' && !s
[1])
2646 is_commutative
= true;
2647 else if (s
[1] != '\0')
2650 fatal_at (token
, "flag %s not recognized", s
);
2654 fatal_at (token
, "expected flag or type specifying identifier");
2657 if (token
->type
== CPP_ATSIGN
2658 && !(token
->flags
& PREV_WHITE
))
2659 op
= parse_capture (e
);
2664 const cpp_token
*token
= peek ();
2665 if (token
->type
== CPP_CLOSE_PAREN
)
2667 if (e
->operation
->nargs
!= -1
2668 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2669 fatal_at (token
, "'%s' expects %u operands, not %u",
2670 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2673 if (e
->ops
.length () == 2)
2674 e
->is_commutative
= true;
2676 fatal_at (token
, "only binary operators or function with "
2677 "two arguments can be marked commutative");
2679 e
->expr_type
= expr_type
;
2682 e
->append_op (parse_op ());
2687 /* Lex native C code delimited by START recording the preprocessing tokens
2688 for later processing.
2689 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2692 parser::parse_c_expr (cpp_ttype start
)
2694 const cpp_token
*token
;
2697 vec
<cpp_token
> code
= vNULL
;
2698 unsigned nr_stmts
= 0;
2700 if (start
== CPP_OPEN_PAREN
)
2701 end
= CPP_CLOSE_PAREN
;
2702 else if (start
== CPP_OPEN_BRACE
)
2703 end
= CPP_CLOSE_BRACE
;
2711 /* Count brace pairs to find the end of the expr to match. */
2712 if (token
->type
== start
)
2714 else if (token
->type
== end
2718 /* This is a lame way of counting the number of statements. */
2719 if (token
->type
== CPP_SEMICOLON
)
2722 /* Record the token. */
2723 code
.safe_push (*token
);
2726 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2729 /* Parse an operand which is either an expression, a predicate or
2730 a standalone capture.
2731 op = predicate | expr | c_expr | capture */
2736 const cpp_token
*token
= peek ();
2737 struct operand
*op
= NULL
;
2738 if (token
->type
== CPP_OPEN_PAREN
)
2740 eat_token (CPP_OPEN_PAREN
);
2742 eat_token (CPP_CLOSE_PAREN
);
2744 else if (token
->type
== CPP_OPEN_BRACE
)
2746 op
= parse_c_expr (CPP_OPEN_BRACE
);
2750 /* Remaining ops are either empty or predicates */
2751 if (token
->type
== CPP_NAME
)
2753 const char *id
= get_ident ();
2754 id_base
*opr
= get_operator (id
);
2756 fatal_at (token
, "expected predicate name");
2757 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2759 if (code
->nargs
!= 0)
2760 fatal_at (token
, "using an operator with operands as predicate");
2761 /* Parse the zero-operand operator "predicates" as
2763 op
= new expr (opr
);
2765 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2766 op
= new predicate (p
);
2768 fatal_at (token
, "using an unsupported operator as predicate");
2770 if (token
->flags
& PREV_WHITE
)
2773 else if (token
->type
!= CPP_COLON
2774 && token
->type
!= CPP_ATSIGN
)
2775 fatal_at (token
, "expected expression or predicate");
2776 /* optionally followed by a capture and a predicate. */
2777 if (token
->type
== CPP_COLON
)
2778 fatal_at (token
, "not implemented: predicate on leaf operand");
2779 if (token
->type
== CPP_ATSIGN
)
2780 op
= parse_capture (op
);
2787 simplify = 'simplify' <expr> <result-op>
2789 match = 'match' <ident> <expr> [<result-op>]
2791 <result-op> = <op> | <if> | <with>
2792 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2793 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2794 and fill SIMPLIFIERS with the results. */
2797 parser::parse_simplify (source_location match_location
,
2798 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2801 /* Reset the capture map. */
2802 capture_ids
= new std::map
<std::string
, unsigned>;
2804 const cpp_token
*loc
= peek ();
2805 struct operand
*match
= parse_op ();
2806 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2807 fatal_at (loc
, "outermost expression cannot be captured");
2808 if (match
->type
== operand::OP_EXPR
2809 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2810 fatal_at (loc
, "outermost expression cannot be a predicate");
2812 const cpp_token
*token
= peek ();
2814 /* If this if is immediately closed then it is part of a predicate
2815 definition. Push it. */
2816 if (token
->type
== CPP_CLOSE_PAREN
)
2819 fatal_at (token
, "expected transform expression");
2820 simplifiers
.safe_push
2821 (new simplify (match
, match_location
, result
, token
->src_loc
,
2822 active_ifs
.copy (), active_fors
.copy (),
2827 unsigned active_ifs_len
= active_ifs
.length ();
2830 if (token
->type
== CPP_OPEN_PAREN
)
2832 source_location paren_loc
= token
->src_loc
;
2833 eat_token (CPP_OPEN_PAREN
);
2834 if (peek_ident ("if"))
2837 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2838 token
->src_loc
, false));
2839 /* If this if is immediately closed then it contains a
2840 manual matcher or is part of a predicate definition.
2842 if (peek ()->type
== CPP_CLOSE_PAREN
)
2845 fatal_at (token
, "manual transform not implemented");
2846 simplifiers
.safe_push
2847 (new simplify (match
, match_location
, result
,
2848 paren_loc
, active_ifs
.copy (),
2849 active_fors
.copy (), capture_ids
));
2852 else if (peek_ident ("with"))
2855 /* Parse (with c-expr expr) as (if-with (true) expr). */
2856 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2858 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2862 operand
*op
= result
;
2865 simplifiers
.safe_push
2866 (new simplify (match
, match_location
, op
,
2867 token
->src_loc
, active_ifs
.copy (),
2868 active_fors
.copy (), capture_ids
));
2869 eat_token (CPP_CLOSE_PAREN
);
2870 /* A "default" result closes the enclosing scope. */
2871 if (active_ifs
.length () > active_ifs_len
)
2873 eat_token (CPP_CLOSE_PAREN
);
2880 else if (token
->type
== CPP_CLOSE_PAREN
)
2882 /* Close a scope if requested. */
2883 if (active_ifs
.length () > active_ifs_len
)
2885 eat_token (CPP_CLOSE_PAREN
);
2895 fatal_at (token
, "expected match operand expression");
2896 simplifiers
.safe_push
2897 (new simplify (match
, match_location
,
2898 matcher
? result
: parse_op (),
2899 token
->src_loc
, active_ifs
.copy (),
2900 active_fors
.copy (), capture_ids
));
2901 /* A "default" result closes the enclosing scope. */
2902 if (active_ifs
.length () > active_ifs_len
)
2904 eat_token (CPP_CLOSE_PAREN
);
2914 /* Parsing of the outer control structures. */
2916 /* Parse a for expression
2917 for = '(' 'for' <subst>... <pattern> ')'
2918 subst = <ident> '(' <ident>... ')' */
2921 parser::parse_for (source_location
)
2923 vec
<user_id
*> user_ids
= vNULL
;
2924 const cpp_token
*token
;
2925 unsigned min_n_opers
= 0, max_n_opers
= 0;
2929 token
= peek_ident ();
2933 /* Insert the user defined operators into the operator hash. */
2934 const char *id
= get_ident ();
2935 user_id
*op
= new user_id (id
);
2936 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2938 fatal_at (token
, "operator already defined");
2940 user_ids
.safe_push (op
);
2942 eat_token (CPP_OPEN_PAREN
);
2945 while ((token
= peek_ident ()) != 0)
2947 const char *oper
= get_ident ();
2948 id_base
*idb
= get_operator (oper
);
2950 fatal_at (token
, "no such operator '%s'", oper
);
2951 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2952 fatal_at (token
, "conditional operators cannot be used inside for");
2956 else if (idb
->nargs
== -1)
2958 else if (idb
->nargs
!= arity
)
2959 fatal_at (token
, "operator '%s' with arity %d does not match "
2960 "others with arity %d", oper
, idb
->nargs
, arity
);
2962 op
->substitutes
.safe_push (idb
);
2965 token
= expect (CPP_CLOSE_PAREN
);
2967 unsigned nsubstitutes
= op
->substitutes
.length ();
2968 if (nsubstitutes
== 0)
2969 fatal_at (token
, "A user-defined operator must have at least "
2970 "one substitution");
2971 if (max_n_opers
== 0)
2973 min_n_opers
= nsubstitutes
;
2974 max_n_opers
= nsubstitutes
;
2978 if (nsubstitutes
% min_n_opers
!= 0
2979 && min_n_opers
% nsubstitutes
!= 0)
2980 fatal_at (token
, "All user-defined identifiers must have a "
2981 "multiple number of operator substitutions of the "
2982 "smallest number of substitutions");
2983 if (nsubstitutes
< min_n_opers
)
2984 min_n_opers
= nsubstitutes
;
2985 else if (nsubstitutes
> max_n_opers
)
2986 max_n_opers
= nsubstitutes
;
2990 unsigned n_ids
= user_ids
.length ();
2992 fatal_at (token
, "for requires at least one user-defined identifier");
2995 if (token
->type
== CPP_CLOSE_PAREN
)
2996 fatal_at (token
, "no pattern defined in for");
2998 active_fors
.safe_push (user_ids
);
3002 if (token
->type
== CPP_CLOSE_PAREN
)
3008 /* Remove user-defined operators from the hash again. */
3009 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3010 operators
->remove_elt (user_ids
[i
]);
3013 /* Parse an outer if expression.
3014 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3017 parser::parse_if (source_location loc
)
3019 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3021 const cpp_token
*token
= peek ();
3022 if (token
->type
== CPP_CLOSE_PAREN
)
3023 fatal_at (token
, "no pattern defined in if");
3025 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3028 const cpp_token
*token
= peek ();
3029 if (token
->type
== CPP_CLOSE_PAREN
)
3037 /* Parse a list of predefined predicate identifiers.
3038 preds = '(' 'define_predicates' <ident>... ')' */
3041 parser::parse_predicates (source_location
)
3045 const cpp_token
*token
= peek ();
3046 if (token
->type
!= CPP_NAME
)
3049 add_predicate (get_ident ());
3054 /* Parse outer control structures.
3055 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3058 parser::parse_pattern ()
3060 /* All clauses start with '('. */
3061 eat_token (CPP_OPEN_PAREN
);
3062 const cpp_token
*token
= peek ();
3063 const char *id
= get_ident ();
3064 if (strcmp (id
, "simplify") == 0)
3065 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3066 else if (strcmp (id
, "match") == 0)
3068 bool with_args
= false;
3069 if (peek ()->type
== CPP_OPEN_PAREN
)
3071 eat_token (CPP_OPEN_PAREN
);
3074 const char *name
= get_ident ();
3075 id_base
*id
= get_operator (name
);
3079 p
= add_predicate (name
);
3080 user_predicates
.safe_push (p
);
3082 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3085 fatal_at (token
, "cannot add a match to a non-predicate ID");
3086 /* Parse (match <id> <arg>... (match-expr)) here. */
3091 while (peek ()->type
== CPP_ATSIGN
)
3092 e
->append_op (parse_capture (NULL
));
3093 eat_token (CPP_CLOSE_PAREN
);
3096 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3097 || (!e
&& p
->nargs
!= 0)))
3098 fatal_at (token
, "non-matching number of match operands");
3099 p
->nargs
= e
? e
->ops
.length () : 0;
3100 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3102 else if (strcmp (id
, "for") == 0)
3103 parse_for (token
->src_loc
);
3104 else if (strcmp (id
, "if") == 0)
3105 parse_if (token
->src_loc
);
3106 else if (strcmp (id
, "define_predicates") == 0)
3108 if (active_ifs
.length () > 0
3109 || active_fors
.length () > 0)
3110 fatal_at (token
, "define_predicates inside if or for is not supported");
3111 parse_predicates (token
->src_loc
);
3114 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3115 active_ifs
.length () == 0 && active_fors
.length () == 0
3116 ? "'define_predicates', " : "");
3118 eat_token (CPP_CLOSE_PAREN
);
3121 /* Main entry of the parser. Repeatedly parse outer control structures. */
3123 parser::parser (cpp_reader
*r_
)
3127 active_fors
= vNULL
;
3128 simplifiers
= vNULL
;
3129 user_predicates
= vNULL
;
3131 const cpp_token
*token
= next ();
3132 while (token
->type
!= CPP_EOF
)
3134 _cpp_backup_tokens (r
, 1);
3141 /* Helper for the linemap code. */
3144 round_alloc_size (size_t s
)
3150 /* The genmatch generator progam. It reads from a pattern description
3151 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3154 main (int argc
, char **argv
)
3158 progname
= "genmatch";
3164 bool verbose
= false;
3165 char *input
= argv
[argc
-1];
3166 for (int i
= 1; i
< argc
- 1; ++i
)
3168 if (strcmp (argv
[i
], "--gimple") == 0)
3170 else if (strcmp (argv
[i
], "--generic") == 0)
3172 else if (strcmp (argv
[i
], "-v") == 0)
3176 fprintf (stderr
, "Usage: genmatch "
3177 "[--gimple] [--generic] [-v] input\n");
3182 line_table
= XCNEW (struct line_maps
);
3183 linemap_init (line_table
, 0);
3184 line_table
->reallocator
= xrealloc
;
3185 line_table
->round_alloc_size
= round_alloc_size
;
3187 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3188 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3189 cb
->error
= error_cb
;
3191 if (!cpp_read_main_file (r
, input
))
3193 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3194 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3196 /* Pre-seed operators. */
3197 operators
= new hash_table
<id_base
> (1024);
3198 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3199 add_operator (SYM, # SYM, # TYPE, NARGS);
3200 #define END_OF_BASE_TREE_CODES
3202 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3203 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3204 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3205 #undef END_OF_BASE_TREE_CODES
3208 /* Pre-seed builtin functions.
3209 ??? Cannot use N (name) as that is targetm.emultls.get_address
3210 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3211 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3212 add_builtin (ENUM, # ENUM);
3213 #include "builtins.def"
3220 write_header (stdout
, "gimple-match-head.c");
3222 write_header (stdout
, "generic-match-head.c");
3224 /* Go over all predicates defined with patterns and perform
3225 lowering and code generation. */
3226 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3228 predicate_id
*pred
= p
.user_predicates
[i
];
3229 lower (pred
->matchers
);
3232 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3233 print_matches (pred
->matchers
[i
]);
3236 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3237 dt
.insert (pred
->matchers
[i
], i
);
3242 write_predicate (stdout
, pred
, dt
, gimple
);
3245 /* Lower the main simplifiers and generate code for them. */
3246 lower (p
.simplifiers
);
3249 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3250 print_matches (p
.simplifiers
[i
]);
3253 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3254 dt
.insert (p
.simplifiers
[i
], i
);
3260 dt
.gen_gimple (stdout
);
3262 dt
.gen_generic (stdout
);
3265 cpp_finish (r
, NULL
);