1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
32 #include "hash-table.h"
38 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
39 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
45 void ggc_free (void *)
52 static struct line_maps
*line_table
;
55 #if GCC_VERSION >= 4001
56 __attribute__((format (printf
, 6, 0)))
58 error_cb (cpp_reader
*, int, int, source_location location
,
59 unsigned int, const char *msg
, va_list *ap
)
62 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
63 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
64 fprintf (stderr
, "%s:%d:%d error: ", loc
.file
, loc
.line
, loc
.column
);
65 vfprintf (stderr
, msg
, *ap
);
66 fprintf (stderr
, "\n");
67 FILE *f
= fopen (loc
.file
, "r");
73 if (!fgets (buf
, 128, f
))
75 if (buf
[strlen (buf
) - 1] != '\n')
82 fprintf (stderr
, "%s", buf
);
83 for (int i
= 0; i
< loc
.column
- 1; ++i
)
94 #if GCC_VERSION >= 4001
95 __attribute__((format (printf
, 2, 3)))
97 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
101 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
106 output_line_directive (FILE *f
, source_location location
,
107 bool dumpfile
= false)
110 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
111 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
114 /* When writing to a dumpfile only dump the filename. */
115 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
120 fprintf (f
, "%s:%d", file
, loc
.line
);
123 /* Other gen programs really output line directives here, at least for
124 development it's right now more convenient to have line information
125 from the generated file. Still keep the directives as comment for now
126 to easily back-point to the meta-description. */
127 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
131 /* Pull in tree codes and builtin function codes from their
134 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
144 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
145 enum built_in_function
{
146 #include "builtins.def"
152 /* Base class for all identifiers the parser knows. */
154 struct id_base
: typed_noop_remove
<id_base
>
156 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
158 id_base (id_kind
, const char *, int = -1);
164 /* hash_table support. */
165 typedef id_base value_type
;
166 typedef id_base compare_type
;
167 static inline hashval_t
hash (const value_type
*);
168 static inline int equal (const value_type
*, const compare_type
*);
172 id_base::hash (const value_type
*op
)
178 id_base::equal (const value_type
*op1
,
179 const compare_type
*op2
)
181 return (op1
->hashval
== op2
->hashval
182 && strcmp (op1
->id
, op2
->id
) == 0);
185 /* Hashtable of known pattern operators. This is pre-seeded from
186 all known tree codes and all known builtin function ids. */
187 static hash_table
<id_base
> *operators
;
189 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
194 hashval
= htab_hash_string (id
);
197 /* Identifier that maps to a tree code. */
199 struct operator_id
: public id_base
201 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
203 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
208 /* Identifier that maps to a builtin function code. */
210 struct fn_id
: public id_base
212 fn_id (enum built_in_function fn_
, const char *id_
)
213 : id_base (id_base::FN
, id_
), fn (fn_
) {}
214 enum built_in_function fn
;
219 /* Identifier that maps to a user-defined predicate. */
221 struct predicate_id
: public id_base
223 predicate_id (const char *id_
)
224 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
225 vec
<simplify
*> matchers
;
228 /* Identifier that maps to a operator defined by a 'for' directive. */
230 struct user_id
: public id_base
232 user_id (const char *id_
)
233 : id_base (id_base::USER
, id_
), substitutes (vNULL
) {}
234 vec
<id_base
*> substitutes
;
240 is_a_helper
<fn_id
*>::test (id_base
*id
)
242 return id
->kind
== id_base::FN
;
248 is_a_helper
<operator_id
*>::test (id_base
*id
)
250 return id
->kind
== id_base::CODE
;
256 is_a_helper
<predicate_id
*>::test (id_base
*id
)
258 return id
->kind
== id_base::PREDICATE
;
264 is_a_helper
<user_id
*>::test (id_base
*id
)
266 return id
->kind
== id_base::USER
;
269 /* Add a predicate identifier to the hash. */
271 static predicate_id
*
272 add_predicate (const char *id
)
274 predicate_id
*p
= new predicate_id (id
);
275 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
277 fatal ("duplicate id definition");
282 /* Add a tree code identifier to the hash. */
285 add_operator (enum tree_code code
, const char *id
,
286 const char *tcc
, unsigned nargs
)
288 if (strcmp (tcc
, "tcc_unary") != 0
289 && strcmp (tcc
, "tcc_binary") != 0
290 && strcmp (tcc
, "tcc_comparison") != 0
291 && strcmp (tcc
, "tcc_expression") != 0
292 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
293 && strcmp (tcc
, "tcc_reference") != 0
294 /* To have INTEGER_CST and friends as "predicate operators". */
295 && strcmp (tcc
, "tcc_constant") != 0)
297 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
298 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
300 fatal ("duplicate id definition");
304 /* Add a builtin identifier to the hash. */
307 add_builtin (enum built_in_function code
, const char *id
)
309 fn_id
*fn
= new fn_id (code
, id
);
310 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
312 fatal ("duplicate id definition");
316 /* Helper for easy comparing ID with tree code CODE. */
319 operator==(id_base
&id
, enum tree_code code
)
321 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
322 return oid
->code
== code
;
326 /* Lookup the identifier ID. */
329 get_operator (const char *id
)
331 id_base
tem (id_base::CODE
, id
);
333 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
337 /* Try all-uppercase. */
338 char *id2
= xstrdup (id
);
339 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
340 id2
[i
] = TOUPPER (id2
[i
]);
341 new (&tem
) id_base (id_base::CODE
, id2
);
342 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
349 /* Try _EXPR appended. */
350 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
351 strcat (id2
, "_EXPR");
352 new (&tem
) id_base (id_base::CODE
, id2
);
353 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
364 /* Helper for the capture-id map. */
366 struct capture_id_map_hasher
: default_hashmap_traits
368 static inline hashval_t
hash (const char *);
369 static inline bool equal_keys (const char *, const char *);
373 capture_id_map_hasher::hash (const char *id
)
375 return htab_hash_string (id
);
379 capture_id_map_hasher::equal_keys (const char *id1
, const char *id2
)
381 return strcmp (id1
, id2
) == 0;
384 typedef hash_map
<const char *, unsigned, capture_id_map_hasher
> cid_map_t
;
387 /* The AST produced by parsing of the pattern definitions. */
391 /* The base class for operands. */
394 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
};
395 operand (enum op_type type_
) : type (type_
) {}
397 virtual void gen_transform (FILE *, const char *, bool, int,
398 const char *, dt_operand
** = 0)
399 { gcc_unreachable (); }
402 /* A predicate operand. Predicates are leafs in the AST. */
404 struct predicate
: public operand
406 predicate (predicate_id
*p_
) : operand (OP_PREDICATE
), p (p_
) {}
410 /* An operand that constitutes an expression. Expressions include
411 function calls and user-defined predicate invocations. */
413 struct expr
: public operand
415 expr (id_base
*operation_
, bool is_commutative_
= false)
416 : operand (OP_EXPR
), operation (operation_
),
417 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
) {}
418 void append_op (operand
*op
) { ops
.safe_push (op
); }
419 /* The operator and its operands. */
422 /* An explicitely specified type - used exclusively for conversions. */
423 const char *expr_type
;
424 /* Whether the operation is to be applied commutatively. This is
425 later lowered to two separate patterns. */
427 virtual void gen_transform (FILE *f
, const char *, bool, int,
428 const char *, dt_operand
** = 0);
431 /* An operator that is represented by native C code. This is always
432 a leaf operand in the AST. This class is also used to represent
433 the code to be generated for 'if' and 'with' expressions. */
435 struct c_expr
: public operand
437 /* A mapping of an identifier and its replacement. Used to apply
442 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
445 c_expr (cpp_reader
*r_
, vec
<cpp_token
> code_
, unsigned nr_stmts_
,
446 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
447 : operand (OP_C_EXPR
), r (r_
), code (code_
), capture_ids (capture_ids_
),
448 nr_stmts (nr_stmts_
), ids (ids_
) {}
449 /* cpplib tokens and state to transform this back to source. */
452 cid_map_t
*capture_ids
;
453 /* The number of statements parsed (well, the number of ';'s). */
455 /* The identifier replacement vector. */
457 virtual void gen_transform (FILE *f
, const char *, bool, int,
458 const char *, dt_operand
**);
461 /* A wrapper around another operand that captures its value. */
463 struct capture
: public operand
465 capture (unsigned where_
, operand
*what_
)
466 : operand (OP_CAPTURE
), where (where_
), what (what_
) {}
467 /* Identifier index for the value. */
469 /* The captured value. */
471 virtual void gen_transform (FILE *f
, const char *, bool, int,
472 const char *, dt_operand
** = 0);
478 is_a_helper
<capture
*>::test (operand
*op
)
480 return op
->type
== operand::OP_CAPTURE
;
486 is_a_helper
<predicate
*>::test (operand
*op
)
488 return op
->type
== operand::OP_PREDICATE
;
494 is_a_helper
<c_expr
*>::test (operand
*op
)
496 return op
->type
== operand::OP_C_EXPR
;
502 is_a_helper
<expr
*>::test (operand
*op
)
504 return op
->type
== operand::OP_EXPR
;
507 /* Helper to distinguish 'if' from 'with' expressions. */
511 if_or_with (operand
*cexpr_
, source_location location_
, bool is_with_
)
512 : location (location_
), cexpr (cexpr_
), is_with (is_with_
) {}
513 source_location location
;
518 /* The main class of a pattern and its transform. This is used to
519 represent both (simplify ...) and (match ...) kinds. The AST
520 duplicates all outer 'if' and 'for' expressions here so each
521 simplify can exist in isolation. */
525 simplify (operand
*match_
, source_location match_location_
,
526 struct operand
*result_
, source_location result_location_
,
527 vec
<if_or_with
> ifexpr_vec_
, vec
<vec
<user_id
*> > for_vec_
,
528 cid_map_t
*capture_ids_
)
529 : match (match_
), match_location (match_location_
),
530 result (result_
), result_location (result_location_
),
531 ifexpr_vec (ifexpr_vec_
), for_vec (for_vec_
),
532 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
534 /* The expression that is matched against the GENERIC or GIMPLE IL. */
536 source_location match_location
;
537 /* For a (simplify ...) the expression produced when the pattern applies.
538 For a (match ...) either NULL if it is a simple predicate or the
539 single expression specifying the matched operands. */
540 struct operand
*result
;
541 source_location result_location
;
542 /* Collected 'if' expressions that need to evaluate to true to make
543 the pattern apply. */
544 vec
<if_or_with
> ifexpr_vec
;
545 /* Collected 'for' expression operators that have to be replaced
546 in the lowering phase. */
547 vec
<vec
<user_id
*> > for_vec
;
548 /* A map of capture identifiers to indexes. */
549 cid_map_t
*capture_ids
;
553 /* Debugging routines for dumping the AST. */
556 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
558 if (capture
*c
= dyn_cast
<capture
*> (o
))
560 fprintf (f
, "@%u", c
->where
);
561 if (c
->what
&& flattened
== false)
564 print_operand (c
->what
, f
, flattened
);
569 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
570 fprintf (f
, "%s", p
->p
->id
);
572 else if (is_a
<c_expr
*> (o
))
573 fprintf (f
, "c_expr");
575 else if (expr
*e
= dyn_cast
<expr
*> (o
))
577 fprintf (f
, "(%s", e
->operation
->id
);
579 if (flattened
== false)
582 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
584 print_operand (e
->ops
[i
], f
, flattened
);
596 print_matches (struct simplify
*s
, FILE *f
= stderr
)
598 fprintf (f
, "for expression: ");
599 print_operand (s
->match
, f
);
606 /* Lowering of commutative operators. */
609 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
610 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
612 if (n
== ops_vector
.length ())
614 vec
<operand
*> xv
= v
.copy ();
615 result
.safe_push (xv
);
619 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
621 v
[n
] = ops_vector
[n
][i
];
622 cartesian_product (ops_vector
, result
, v
, n
+ 1);
626 /* Lower OP to two operands in case it is marked as commutative. */
628 static vec
<operand
*>
629 commutate (operand
*op
)
631 vec
<operand
*> ret
= vNULL
;
633 if (capture
*c
= dyn_cast
<capture
*> (op
))
640 vec
<operand
*> v
= commutate (c
->what
);
641 for (unsigned i
= 0; i
< v
.length (); ++i
)
643 capture
*nc
= new capture (c
->where
, v
[i
]);
649 expr
*e
= dyn_cast
<expr
*> (op
);
650 if (!e
|| e
->ops
.length () == 0)
656 vec
< vec
<operand
*> > ops_vector
= vNULL
;
657 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
658 ops_vector
.safe_push (commutate (e
->ops
[i
]));
660 auto_vec
< vec
<operand
*> > result
;
661 auto_vec
<operand
*> v (e
->ops
.length ());
662 v
.quick_grow_cleared (e
->ops
.length ());
663 cartesian_product (ops_vector
, result
, v
, 0);
666 for (unsigned i
= 0; i
< result
.length (); ++i
)
668 expr
*ne
= new expr (e
->operation
);
669 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
670 ne
->append_op (result
[i
][j
]);
674 if (!e
->is_commutative
)
677 for (unsigned i
= 0; i
< result
.length (); ++i
)
679 expr
*ne
= new expr (e
->operation
);
680 // result[i].length () is 2 since e->operation is binary
681 for (unsigned j
= result
[i
].length (); j
; --j
)
682 ne
->append_op (result
[i
][j
-1]);
689 /* Lower operations marked as commutative in the AST of S and push
690 the resulting patterns to SIMPLIFIERS. */
693 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
695 vec
<operand
*> matchers
= commutate (s
->match
);
696 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
698 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
699 s
->result
, s
->result_location
, s
->ifexpr_vec
,
700 s
->for_vec
, s
->capture_ids
);
701 simplifiers
.safe_push (ns
);
705 /* Strip conditional conversios using operator OPER from O and its
706 children if STRIP, else replace them with an unconditional convert. */
709 lower_opt_convert (operand
*o
, enum tree_code oper
, bool strip
)
711 if (capture
*c
= dyn_cast
<capture
*> (o
))
714 return new capture (c
->where
, lower_opt_convert (c
->what
, oper
, strip
));
719 expr
*e
= dyn_cast
<expr
*> (o
);
723 if (*e
->operation
== oper
)
726 return lower_opt_convert (e
->ops
[0], oper
, strip
);
728 expr
*ne
= new expr (get_operator ("CONVERT_EXPR"));
729 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, strip
));
733 expr
*ne
= new expr (e
->operation
, e
->is_commutative
);
734 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
735 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, strip
));
740 /* Determine whether O or its children uses the conditional conversion
744 has_opt_convert (operand
*o
, enum tree_code oper
)
746 if (capture
*c
= dyn_cast
<capture
*> (o
))
749 return has_opt_convert (c
->what
, oper
);
754 expr
*e
= dyn_cast
<expr
*> (o
);
758 if (*e
->operation
== oper
)
761 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
762 if (has_opt_convert (e
->ops
[i
], oper
))
768 /* Lower conditional convert operators in O, expanding it to a vector
771 static vec
<operand
*>
772 lower_opt_convert (operand
*o
)
774 vec
<operand
*> v1
= vNULL
, v2
;
778 enum tree_code opers
[] = { CONVERT0
, CONVERT1
, CONVERT2
};
780 /* Conditional converts are lowered to a pattern with the
781 conversion and one without. The three different conditional
782 convert codes are lowered separately. */
784 for (unsigned i
= 0; i
< 3; ++i
)
787 for (unsigned j
= 0; j
< v1
.length (); ++j
)
788 if (has_opt_convert (v1
[j
], opers
[i
]))
790 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], false));
791 v2
.safe_push (lower_opt_convert (v1
[j
], opers
[i
], true));
797 for (unsigned j
= 0; j
< v2
.length (); ++j
)
798 v1
.safe_push (v2
[j
]);
805 /* Lower conditional convert operators in the AST of S and push
806 the resulting multiple patterns to SIMPLIFIERS. */
809 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
811 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
812 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
814 simplify
*ns
= new simplify (matchers
[i
], s
->match_location
,
815 s
->result
, s
->result_location
, s
->ifexpr_vec
,
816 s
->for_vec
, s
->capture_ids
);
817 simplifiers
.safe_push (ns
);
821 /* In AST operand O replace operator ID with operator WITH. */
824 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
826 /* Deep-copy captures and expressions, replacing operations as
828 if (capture
*c
= dyn_cast
<capture
*> (o
))
832 return new capture (c
->where
, replace_id (c
->what
, id
, with
));
834 else if (expr
*e
= dyn_cast
<expr
*> (o
))
836 expr
*ne
= new expr (e
->operation
== id
? with
: e
->operation
,
838 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
839 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
843 /* For c_expr we simply record a string replacement table which is
844 applied at code-generation time. */
845 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
847 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
848 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
849 return new c_expr (ce
->r
, ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
855 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
858 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
860 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
861 unsigned worklist_start
= 0;
862 auto_vec
<simplify
*> worklist
;
863 worklist
.safe_push (sin
);
865 /* Lower each recorded for separately, operating on the
866 set of simplifiers created by the previous one.
867 Lower inner-to-outer so inner for substitutes can refer
868 to operators replaced by outer fors. */
869 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
871 vec
<user_id
*>& ids
= for_vec
[fi
];
872 unsigned n_ids
= ids
.length ();
873 unsigned max_n_opers
= 0;
874 for (unsigned i
= 0; i
< n_ids
; ++i
)
875 if (ids
[i
]->substitutes
.length () > max_n_opers
)
876 max_n_opers
= ids
[i
]->substitutes
.length ();
878 unsigned worklist_end
= worklist
.length ();
879 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
881 simplify
*s
= worklist
[si
];
882 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
884 operand
*match_op
= s
->match
;
885 operand
*result_op
= s
->result
;
886 vec
<if_or_with
> ifexpr_vec
= s
->ifexpr_vec
.copy ();
888 for (unsigned i
= 0; i
< n_ids
; ++i
)
890 user_id
*id
= ids
[i
];
891 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
892 match_op
= replace_id (match_op
, id
, oper
);
894 result_op
= replace_id (result_op
, id
, oper
);
895 for (unsigned k
= 0; k
< s
->ifexpr_vec
.length (); ++k
)
896 ifexpr_vec
[k
].cexpr
= replace_id (ifexpr_vec
[k
].cexpr
,
899 simplify
*ns
= new simplify (match_op
, s
->match_location
,
900 result_op
, s
->result_location
,
901 ifexpr_vec
, vNULL
, s
->capture_ids
);
902 worklist
.safe_push (ns
);
905 worklist_start
= worklist_end
;
908 /* Copy out the result from the last for lowering. */
909 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
910 simplifiers
.safe_push (worklist
[i
]);
913 /* Lower the AST for everything in SIMPLIFIERS. */
916 lower (vec
<simplify
*>& simplifiers
)
918 auto_vec
<simplify
*> out_simplifiers0
;
919 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
920 lower_opt_convert (simplifiers
[i
], out_simplifiers0
);
922 auto_vec
<simplify
*> out_simplifiers1
;
923 for (unsigned i
= 0; i
< out_simplifiers0
.length (); ++i
)
924 lower_commutative (out_simplifiers0
[i
], out_simplifiers1
);
926 simplifiers
.truncate (0);
927 for (unsigned i
= 0; i
< out_simplifiers1
.length (); ++i
)
928 lower_for (out_simplifiers1
[i
], simplifiers
);
934 /* The decision tree built for generating GIMPLE and GENERIC pattern
935 matching code. It represents the 'match' expression of all
936 simplifies and has those as its leafs. */
938 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
942 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
948 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
950 dt_node
*append_node (dt_node
*);
951 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
952 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
953 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
954 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
956 virtual void gen (FILE *, bool) {}
958 void gen_kids (FILE *, bool);
961 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
963 struct dt_operand
: public dt_node
966 dt_operand
*match_dop
;
970 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
971 dt_operand
*parent_
= 0, unsigned pos_
= 0)
972 : dt_node (type
), op (op_
), match_dop (match_dop_
),
973 parent (parent_
), pos (pos_
) {}
975 void gen (FILE *, bool);
976 unsigned gen_predicate (FILE *, const char *, bool);
977 unsigned gen_match_op (FILE *, const char *);
979 unsigned gen_gimple_expr (FILE *);
980 unsigned gen_generic_expr (FILE *, const char *);
982 char *get_name (char *);
983 void gen_opname (char *, unsigned);
986 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
988 struct dt_simplify
: public dt_node
992 dt_operand
**indexes
;
994 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
995 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
996 indexes (indexes_
) {}
998 void gen (FILE *f
, bool);
1004 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1006 return (n
->type
== dt_node::DT_OPERAND
1007 || n
->type
== dt_node::DT_MATCH
);
1010 /* A container for the actual decision tree. */
1012 struct decision_tree
1016 void insert (struct simplify
*, unsigned);
1017 void gen_gimple (FILE *f
= stderr
);
1018 void gen_generic (FILE *f
= stderr
);
1019 void print (FILE *f
= stderr
);
1021 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1023 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1024 unsigned pos
= 0, dt_node
*parent
= 0);
1025 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1026 static bool cmp_node (dt_node
*, dt_node
*);
1027 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1030 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1033 cmp_operand (operand
*o1
, operand
*o2
)
1035 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1038 if (o1
->type
== operand::OP_PREDICATE
)
1040 predicate
*p1
= as_a
<predicate
*>(o1
);
1041 predicate
*p2
= as_a
<predicate
*>(o2
);
1042 return p1
->p
== p2
->p
;
1044 else if (o1
->type
== operand::OP_EXPR
)
1046 expr
*e1
= static_cast<expr
*>(o1
);
1047 expr
*e2
= static_cast<expr
*>(o2
);
1048 return e1
->operation
== e2
->operation
;
1054 /* Compare two decision tree nodes N1 and N2 and return true if they
1058 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1060 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1063 if (n1
== n2
|| n1
->type
== dt_node::DT_TRUE
)
1066 if (n1
->type
== dt_node::DT_OPERAND
)
1067 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1068 (as_a
<dt_operand
*> (n2
))->op
);
1069 else if (n1
->type
== dt_node::DT_MATCH
)
1070 return ((as_a
<dt_operand
*> (n1
))->match_dop
1071 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1075 /* Search OPS for a decision tree node like P and return it if found. */
1078 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1080 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1081 if (decision_tree::cmp_node (ops
[i
], p
))
1087 /* Append N to the decision tree if it there is not already an existing
1091 dt_node::append_node (dt_node
*n
)
1095 kid
= decision_tree::find_node (kids
, n
);
1100 n
->level
= this->level
+ 1;
1102 unsigned len
= kids
.length ();
1104 if (len
> 1 && kids
[len
- 2]->type
== dt_node::DT_TRUE
)
1106 dt_node
*p
= kids
[len
- 2];
1107 kids
[len
- 2] = kids
[len
- 1];
1114 /* Append OP to the decision tree. */
1117 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1119 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1120 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1121 return append_node (n
);
1124 /* Append a DT_TRUE decision tree node. */
1127 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1129 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1130 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1131 return append_node (n
);
1134 /* Append a DT_MATCH decision tree node. */
1137 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1139 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1140 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1141 return append_node (n
);
1144 /* Append S to the decision tree. */
1147 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1148 dt_operand
**indexes
)
1150 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1151 return append_node (n
);
1154 /* Insert O into the decision tree and return the decision tree node found
1158 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1159 unsigned pos
, dt_node
*parent
)
1161 dt_node
*q
, *elm
= 0;
1163 if (capture
*c
= dyn_cast
<capture
*> (o
))
1165 unsigned capt_index
= c
->where
;
1167 if (indexes
[capt_index
] == 0)
1170 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1173 q
= elm
= p
->append_true_op (parent
, pos
);
1176 // get to the last capture
1177 for (operand
*what
= c
->what
;
1178 what
&& is_a
<capture
*> (what
);
1179 c
= as_a
<capture
*> (what
), what
= c
->what
)
1184 unsigned cc_index
= c
->where
;
1185 dt_operand
*match_op
= indexes
[cc_index
];
1187 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1188 elm
= decision_tree::find_node (p
->kids
, &temp
);
1192 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1193 elm
= decision_tree::find_node (p
->kids
, &temp
);
1198 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1199 elm
= decision_tree::find_node (p
->kids
, &temp
);
1203 gcc_assert (elm
->type
== dt_node::DT_TRUE
1204 || elm
->type
== dt_node::DT_OPERAND
1205 || elm
->type
== dt_node::DT_MATCH
);
1206 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1211 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1213 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1218 p
= p
->append_op (o
, parent
, pos
);
1221 if (expr
*e
= dyn_cast
<expr
*>(o
))
1223 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1224 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1230 /* Insert S into the decision tree. */
1233 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1235 if (s
->match
->type
!= operand::OP_EXPR
)
1238 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1239 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1240 p
->append_simplify (s
, pattern_no
, indexes
);
1243 /* Debug functions to dump the decision tree. */
1246 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1248 if (p
->type
== dt_node::DT_NODE
)
1249 fprintf (f
, "root");
1253 for (unsigned i
= 0; i
< indent
; i
++)
1256 if (p
->type
== dt_node::DT_OPERAND
)
1258 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1259 print_operand (dop
->op
, f
, true);
1261 else if (p
->type
== dt_node::DT_TRUE
)
1262 fprintf (f
, "true");
1263 else if (p
->type
== dt_node::DT_MATCH
)
1264 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1265 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1267 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1268 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1269 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1270 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1275 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1277 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1278 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1282 decision_tree::print (FILE *f
)
1284 return decision_tree::print_node (root
, f
);
1289 /* Code generation off the decision tree and the refered AST nodes. */
1292 is_conversion (id_base
*op
)
1294 return (*op
== CONVERT_EXPR
1296 || *op
== FLOAT_EXPR
1297 || *op
== FIX_TRUNC_EXPR
1298 || *op
== VIEW_CONVERT_EXPR
);
1301 /* Get the type to be used for generating operands of OP from the
1305 get_operand_type (id_base
*op
, const char *in_type
,
1306 const char *expr_type
,
1307 const char *other_oprnd_type
)
1309 /* Generally operands whose type does not match the type of the
1310 expression generated need to know their types but match and
1311 thus can fall back to 'other_oprnd_type'. */
1312 if (is_conversion (op
))
1313 return other_oprnd_type
;
1314 else if (*op
== REALPART_EXPR
1315 || *op
== IMAGPART_EXPR
)
1316 return other_oprnd_type
;
1317 else if (is_a
<operator_id
*> (op
)
1318 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
1319 return other_oprnd_type
;
1322 /* Otherwise all types should match - choose one in order of
1329 return other_oprnd_type
;
1333 /* Generate transform code for an expression. */
1336 expr::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1337 const char *in_type
, dt_operand
**indexes
)
1339 bool conversion_p
= is_conversion (operation
);
1340 const char *type
= expr_type
;
1343 /* If there was a type specification in the pattern use it. */
1345 else if (conversion_p
)
1346 /* For conversions we need to build the expression using the
1347 outer type passed in. */
1349 else if (*operation
== REALPART_EXPR
1350 || *operation
== IMAGPART_EXPR
)
1352 /* __real and __imag use the component type of its operand. */
1353 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
1356 else if (is_a
<operator_id
*> (operation
)
1357 && !strcmp (as_a
<operator_id
*> (operation
)->tcc
, "tcc_comparison"))
1359 /* comparisons use boolean_type_node (or what gets in), but
1360 their operands need to figure out the types themselves. */
1361 sprintf (optype
, "boolean_type_node");
1366 /* Other operations are of the same type as their first operand. */
1367 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
1371 fatal ("two conversions in a row");
1374 fprintf (f
, " tree ops%d[%u], res;\n", depth
, ops
.length ());
1376 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
1377 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1380 snprintf (dest
, 32, " ops%d[%u]", depth
, i
);
1382 = get_operand_type (operation
, in_type
, expr_type
,
1383 i
== 0 ? NULL
: op0type
);
1384 ops
[i
]->gen_transform (f
, dest
, gimple
, depth
+ 1, optype
, indexes
);
1389 /* ??? Have another helper that is like gimple_build but may
1390 fail if seq == NULL. */
1391 fprintf (f
, " if (!seq)\n"
1393 " res = gimple_simplify (%s, %s",
1394 operation
->id
, type
);
1395 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1396 fprintf (f
, ", ops%d[%u]", depth
, i
);
1397 fprintf (f
, ", seq, valueize);\n");
1398 fprintf (f
, " if (!res) return false;\n");
1399 fprintf (f
, " }\n");
1400 fprintf (f
, " else\n");
1401 fprintf (f
, " res = gimple_build (seq, UNKNOWN_LOCATION, %s, %s",
1402 operation
->id
, type
);
1403 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1404 fprintf (f
, ", ops%d[%u]", depth
, i
);
1405 fprintf (f
, ", valueize);\n");
1409 if (operation
->kind
== id_base::CODE
)
1410 fprintf (f
, " res = fold_build%d_loc (loc, %s, %s",
1411 ops
.length(), operation
->id
, type
);
1413 fprintf (f
, " res = build_call_expr_loc (loc, "
1414 "builtin_decl_implicit (%s), %d",
1415 operation
->id
, ops
.length());
1416 for (unsigned i
= 0; i
< ops
.length (); ++i
)
1417 fprintf (f
, ", ops%d[%u]", depth
, i
);
1418 fprintf (f
, ");\n");
1420 fprintf (f
, " %s = res;\n", dest
);
1424 /* Generate code for a c_expr which is either the expression inside
1425 an if statement or a sequence of statements which computes a
1426 result to be stored to DEST. */
1429 c_expr::gen_transform (FILE *f
, const char *dest
,
1430 bool, int, const char *, dt_operand
**)
1432 if (dest
&& nr_stmts
== 1)
1433 fprintf (f
, "%s = ", dest
);
1435 unsigned stmt_nr
= 1;
1436 for (unsigned i
= 0; i
< code
.length (); ++i
)
1438 const cpp_token
*token
= &code
[i
];
1440 /* Replace captures for code-gen. */
1441 if (token
->type
== CPP_ATSIGN
)
1443 const cpp_token
*n
= &code
[i
+1];
1444 if ((n
->type
== CPP_NUMBER
1445 || n
->type
== CPP_NAME
)
1446 && !(n
->flags
& PREV_WHITE
))
1448 if (token
->flags
& PREV_WHITE
)
1451 if (n
->type
== CPP_NUMBER
)
1452 id
= (const char *)n
->val
.str
.text
;
1454 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1455 fprintf (f
, "captures[%u]", *capture_ids
->get(id
));
1461 if (token
->flags
& PREV_WHITE
)
1464 if (token
->type
== CPP_NAME
)
1466 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
1468 for (j
= 0; j
< ids
.length (); ++j
)
1470 if (strcmp (id
, ids
[j
].id
) == 0)
1472 fprintf (f
, "%s", ids
[j
].oper
);
1476 if (j
< ids
.length ())
1480 /* Output the token as string. */
1481 char *tk
= (char *)cpp_token_as_text (r
, token
);
1484 if (token
->type
== CPP_SEMICOLON
)
1487 if (dest
&& stmt_nr
== nr_stmts
)
1488 fprintf (f
, "\n %s = ", dest
);
1495 /* Generate transform code for a capture. */
1498 capture::gen_transform (FILE *f
, const char *dest
, bool gimple
, int depth
,
1499 const char *in_type
, dt_operand
**indexes
)
1501 if (what
&& is_a
<expr
*> (what
))
1503 if (indexes
[where
] == 0)
1506 sprintf (buf
, "captures[%u]", where
);
1507 what
->gen_transform (f
, buf
, gimple
, depth
, in_type
, NULL
);
1511 fprintf (f
, "%s = captures[%u];\n", dest
, where
);
1514 /* Return the name of the operand representing the decision tree node.
1515 Use NAME as space to generate it. */
1518 dt_operand::get_name (char *name
)
1521 sprintf (name
, "t");
1522 else if (parent
->level
== 1)
1523 sprintf (name
, "op%u", pos
);
1524 else if (parent
->type
== dt_node::DT_MATCH
)
1525 return parent
->get_name (name
);
1527 sprintf (name
, "o%u%u", parent
->level
, pos
);
1531 /* Fill NAME with the operand name at position POS. */
1534 dt_operand::gen_opname (char *name
, unsigned pos
)
1537 sprintf (name
, "op%u", pos
);
1539 sprintf (name
, "o%u%u", level
, pos
);
1542 /* Generate matching code for the decision tree operand which is
1546 dt_operand::gen_predicate (FILE *f
, const char *opname
, bool gimple
)
1548 predicate
*p
= as_a
<predicate
*> (op
);
1550 if (p
->p
->matchers
.exists ())
1552 /* If this is a predicate generated from a pattern mangle its
1553 name and pass on the valueize hook. */
1555 fprintf (f
, "if (gimple_%s (%s, valueize))\n", p
->p
->id
, opname
);
1557 fprintf (f
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
1560 fprintf (f
, "if (%s (%s))\n", p
->p
->id
, opname
);
1565 /* Generate matching code for the decision tree operand which is
1569 dt_operand::gen_match_op (FILE *f
, const char *opname
)
1571 char match_opname
[20];
1572 match_dop
->get_name (match_opname
);
1573 fprintf (f
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
1574 opname
, match_opname
, opname
, match_opname
);
1579 /* Generate GIMPLE matching code for the decision tree operand. */
1582 dt_operand::gen_gimple_expr (FILE *f
)
1584 expr
*e
= static_cast<expr
*> (op
);
1585 id_base
*id
= e
->operation
;
1586 unsigned n_ops
= e
->ops
.length ();
1588 for (unsigned i
= 0; i
< n_ops
; ++i
)
1590 char child_opname
[20];
1591 gen_opname (child_opname
, i
);
1593 if (id
->kind
== id_base::CODE
)
1595 if (*id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
1596 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
1598 /* ??? If this is a memory operation we can't (and should not)
1599 match this. The only sensible operand types are
1600 SSA names and invariants. */
1601 fprintf (f
, "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), %i);\n",
1603 fprintf (f
, "if ((TREE_CODE (%s) == SSA_NAME\n"
1604 "|| is_gimple_min_invariant (%s))\n"
1605 "&& (%s = do_valueize (valueize, %s)))\n"
1606 "{\n", child_opname
, child_opname
, child_opname
,
1611 fprintf (f
, "tree %s = gimple_assign_rhs%u (def_stmt);\n",
1612 child_opname
, i
+ 1);
1615 fprintf (f
, "tree %s = gimple_call_arg (def_stmt, %u);\n",
1617 fprintf (f
, "if ((%s = do_valueize (valueize, %s)) != 0)\n",
1618 child_opname
, child_opname
);
1625 /* Generate GENERIC matching code for the decision tree operand. */
1628 dt_operand::gen_generic_expr (FILE *f
, const char *opname
)
1630 expr
*e
= static_cast<expr
*> (op
);
1631 unsigned n_ops
= e
->ops
.length ();
1633 for (unsigned i
= 0; i
< n_ops
; ++i
)
1635 char child_opname
[20];
1636 gen_opname (child_opname
, i
);
1638 if (e
->operation
->kind
== id_base::CODE
)
1639 fprintf (f
, "tree %s = TREE_OPERAND (%s, %u);\n",
1640 child_opname
, opname
, i
);
1642 fprintf (f
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
1643 child_opname
, opname
, i
);
1649 /* Generate matching code for the children of the decision tree node. */
1652 dt_node::gen_kids (FILE *f
, bool gimple
)
1654 auto_vec
<dt_operand
*> gimple_exprs
;
1655 auto_vec
<dt_operand
*> generic_exprs
;
1656 auto_vec
<dt_operand
*> fns
;
1657 auto_vec
<dt_operand
*> generic_fns
;
1658 auto_vec
<dt_operand
*> preds
;
1659 auto_vec
<dt_node
*> others
;
1660 dt_node
*true_operand
= NULL
;
1662 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1664 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
1666 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
1667 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
1669 if (e
->ops
.length () == 0)
1670 generic_exprs
.safe_push (op
);
1671 else if (e
->operation
->kind
== id_base::FN
)
1676 generic_fns
.safe_push (op
);
1678 else if (e
->operation
->kind
== id_base::PREDICATE
)
1679 preds
.safe_push (op
);
1683 gimple_exprs
.safe_push (op
);
1685 generic_exprs
.safe_push (op
);
1688 else if (op
->op
->type
== operand::OP_PREDICATE
)
1689 others
.safe_push (kids
[i
]);
1693 else if (kids
[i
]->type
== dt_node::DT_MATCH
1694 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
1695 others
.safe_push (kids
[i
]);
1696 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
1697 true_operand
= kids
[i
];
1703 char *kid_opname
= buf
;
1705 unsigned exprs_len
= gimple_exprs
.length ();
1706 unsigned gexprs_len
= generic_exprs
.length ();
1707 unsigned fns_len
= fns
.length ();
1708 unsigned gfns_len
= generic_fns
.length ();
1710 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1713 gimple_exprs
[0]->get_name (kid_opname
);
1715 fns
[0]->get_name (kid_opname
);
1717 generic_fns
[0]->get_name (kid_opname
);
1719 generic_exprs
[0]->get_name (kid_opname
);
1721 fprintf (f
, "switch (TREE_CODE (%s))\n"
1725 if (exprs_len
|| fns_len
)
1727 fprintf (f
, "case SSA_NAME:\n");
1729 fprintf (f
, "gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n", kid_opname
);
1733 fprintf (f
, "if (is_gimple_assign (def_stmt))\n");
1734 fprintf (f
, "switch (gimple_assign_rhs_code (def_stmt))\n"
1736 for (unsigned i
= 0; i
< exprs_len
; ++i
)
1738 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
1739 id_base
*op
= e
->operation
;
1740 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1741 fprintf (f
, "CASE_CONVERT:\n");
1743 fprintf (f
, "case %s:\n", op
->id
);
1745 gimple_exprs
[i
]->gen (f
, true);
1746 fprintf (f
, "break;\n"
1749 fprintf (f
, "default:;\n"
1756 fprintf (f
, "else ");
1758 fprintf (f
, "if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n"
1760 "tree fndecl = gimple_call_fndecl (def_stmt);\n"
1761 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1764 for (unsigned i
= 0; i
< fns_len
; ++i
)
1766 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
1767 fprintf (f
, "case %s:\n"
1768 "{\n", e
->operation
->id
);
1769 fns
[i
]->gen (f
, true);
1770 fprintf (f
, "break;\n"
1774 fprintf (f
, "default:;\n"
1779 fprintf (f
, "break;\n"
1783 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
1785 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
1786 id_base
*op
= e
->operation
;
1787 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
1788 fprintf (f
, "CASE_CONVERT:\n");
1790 fprintf (f
, "case %s:\n", op
->id
);
1792 generic_exprs
[i
]->gen (f
, gimple
);
1793 fprintf (f
, "break;\n"
1799 fprintf (f
, "case CALL_EXPR:\n"
1801 "tree fndecl = get_callee_fndecl (%s);\n"
1802 "if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n"
1803 "switch (DECL_FUNCTION_CODE (fndecl))\n"
1806 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
1808 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
1809 gcc_assert (e
->operation
->kind
== id_base::FN
);
1811 fprintf (f
, "case %s:\n"
1812 "{\n", e
->operation
->id
);
1813 generic_fns
[j
]->gen (f
, false);
1814 fprintf (f
, "break;\n"
1818 fprintf (f
, "default:;\n"
1824 /* Close switch (TREE_CODE ()). */
1825 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
1826 fprintf (f
, "default:;\n"
1829 for (unsigned i
= 0; i
< preds
.length (); ++i
)
1831 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
1832 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
1833 preds
[i
]->get_name (kid_opname
);
1834 fprintf (f
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
1835 fprintf (f
, "if (%s_%s (%s, %s_pops%s))\n",
1836 gimple
? "gimple" : "tree",
1837 p
->id
, kid_opname
, kid_opname
,
1838 gimple
? ", valueize" : "");
1840 for (int j
= 0; j
< p
->nargs
; ++j
)
1842 char child_opname
[20];
1843 preds
[i
]->gen_opname (child_opname
, j
);
1844 fprintf (f
, "tree %s = %s_pops[%d];\n", child_opname
, kid_opname
, j
);
1846 preds
[i
]->gen_kids (f
, gimple
);
1850 for (unsigned i
= 0; i
< others
.length (); ++i
)
1851 others
[i
]->gen (f
, gimple
);
1854 true_operand
->gen (f
, gimple
);
1857 /* Generate matching code for the decision tree operand. */
1860 dt_operand::gen (FILE *f
, bool gimple
)
1865 unsigned n_braces
= 0;
1867 if (type
== DT_OPERAND
)
1870 case operand::OP_PREDICATE
:
1871 n_braces
= gen_predicate (f
, opname
, gimple
);
1874 case operand::OP_EXPR
:
1876 n_braces
= gen_gimple_expr (f
);
1878 n_braces
= gen_generic_expr (f
, opname
);
1884 else if (type
== DT_TRUE
)
1886 else if (type
== DT_MATCH
)
1887 n_braces
= gen_match_op (f
, opname
);
1891 gen_kids (f
, gimple
);
1893 for (unsigned i
= 0; i
< n_braces
; ++i
)
1898 /* For GENERIC we have to take care of wrapping multiple-used
1899 expressions with side-effects in save_expr and preserve side-effects
1900 of expressions with omit_one_operand. Analyze captures in
1901 match, result and with expressions and perform early-outs
1902 on the outermost match expression operands for cases we cannot
1907 capture_info (simplify
*s
);
1908 void walk_match (operand
*o
, unsigned toplevel_arg
, bool);
1909 void walk_result (operand
*o
, bool);
1910 void walk_c_expr (c_expr
*);
1916 bool force_no_side_effects_p
;
1917 unsigned long toplevel_msk
;
1918 int result_use_count
;
1921 auto_vec
<cinfo
> info
;
1922 unsigned long force_no_side_effects
;
1925 /* Analyze captures in S. */
1927 capture_info::capture_info (simplify
*s
)
1931 || ((e
= dyn_cast
<expr
*> (s
->result
))
1932 && is_a
<predicate_id
*> (e
->operation
)))
1934 force_no_side_effects
= -1;
1938 force_no_side_effects
= 0;
1939 info
.safe_grow_cleared (s
->capture_max
+ 1);
1940 e
= as_a
<expr
*> (s
->match
);
1941 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1942 walk_match (e
->ops
[i
], i
, false);
1944 walk_result (s
->result
, false);
1946 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
1947 if (s
->ifexpr_vec
[i
].is_with
)
1948 walk_c_expr (as_a
<c_expr
*>(s
->ifexpr_vec
[i
].cexpr
));
1951 /* Analyze captures in the match expression piece O. */
1954 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
, bool conditional_p
)
1956 if (capture
*c
= dyn_cast
<capture
*> (o
))
1958 info
[c
->where
].toplevel_msk
|= 1 << toplevel_arg
;
1959 info
[c
->where
].force_no_side_effects_p
|= conditional_p
;
1960 /* Mark expr (non-leaf) captures and recurse. */
1962 && is_a
<expr
*> (c
->what
))
1964 info
[c
->where
].expr_p
= true;
1965 walk_match (c
->what
, toplevel_arg
, conditional_p
);
1968 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1970 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1972 bool cond_p
= conditional_p
;
1974 && *e
->operation
== COND_EXPR
)
1976 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1977 || *e
->operation
== TRUTH_ORIF_EXPR
)
1979 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
);
1982 else if (is_a
<predicate
*> (o
))
1984 /* Mark non-captured leafs toplevel arg for checking. */
1985 force_no_side_effects
|= 1 << toplevel_arg
;
1991 /* Analyze captures in the result expression piece O. */
1994 capture_info::walk_result (operand
*o
, bool conditional_p
)
1996 if (capture
*c
= dyn_cast
<capture
*> (o
))
1998 info
[c
->where
].result_use_count
++;
1999 /* If we substitute an expression capture we don't know
2000 which captures this will end up using (well, we don't
2001 compute that). Force the uses to be side-effect free
2002 which means forcing the toplevels that reach the
2003 expression side-effect free. */
2004 if (info
[c
->where
].expr_p
)
2005 force_no_side_effects
|= info
[c
->where
].toplevel_msk
;
2006 /* Mark CSE capture capture uses as forced to have
2009 && is_a
<expr
*> (c
->what
))
2011 info
[c
->where
].cse_p
= true;
2012 walk_result (c
->what
, true);
2015 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2017 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2019 bool cond_p
= conditional_p
;
2021 && *e
->operation
== COND_EXPR
)
2023 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2024 || *e
->operation
== TRUTH_ORIF_EXPR
)
2026 walk_result (e
->ops
[i
], cond_p
);
2029 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2035 /* Look for captures in the C expr E. */
2038 capture_info::walk_c_expr (c_expr
*e
)
2040 /* Give up for C exprs mentioning captures not inside TREE_TYPE (). */
2041 unsigned p_depth
= 0;
2042 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2044 const cpp_token
*t
= &e
->code
[i
];
2045 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2046 if (t
->type
== CPP_NAME
2047 && strcmp ((const char *)CPP_HASHNODE
2048 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2049 && n
->type
== CPP_OPEN_PAREN
)
2051 else if (t
->type
== CPP_CLOSE_PAREN
2054 else if (p_depth
== 0
2055 && t
->type
== CPP_ATSIGN
2056 && (n
->type
== CPP_NUMBER
2057 || n
->type
== CPP_NAME
)
2058 && !(n
->flags
& PREV_WHITE
))
2061 if (n
->type
== CPP_NUMBER
)
2062 id
= (const char *)n
->val
.str
.text
;
2064 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2065 info
[*e
->capture_ids
->get(id
)].force_no_side_effects_p
= true;
2071 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2072 step of a '(simplify ...)' or '(match ...)'. This handles everything
2073 that is not part of the decision tree (simplify->match). */
2076 dt_simplify::gen (FILE *f
, bool gimple
)
2079 output_line_directive (f
, s
->result_location
);
2080 if (s
->capture_max
>= 0)
2081 fprintf (f
, "tree captures[%u] ATTRIBUTE_UNUSED = {};\n",
2082 s
->capture_max
+ 1);
2084 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2088 fprintf (f
, "captures[%u] = %s;\n", i
, indexes
[i
]->get_name (opname
));
2091 unsigned n_braces
= 0;
2092 if (s
->ifexpr_vec
!= vNULL
)
2094 for (unsigned i
= 0; i
< s
->ifexpr_vec
.length (); ++i
)
2096 if_or_with
&w
= s
->ifexpr_vec
[i
];
2100 output_line_directive (f
, w
.location
);
2101 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2106 output_line_directive (f
, w
.location
);
2107 fprintf (f
, "if (");
2108 if (i
== s
->ifexpr_vec
.length () - 1
2109 || s
->ifexpr_vec
[i
+1].is_with
)
2110 w
.cexpr
->gen_transform (f
, NULL
, true, 1, "type");
2119 output_line_directive (f
, s
->ifexpr_vec
[j
].location
);
2123 s
->ifexpr_vec
[j
].cexpr
->gen_transform (f
, NULL
,
2128 while (j
< s
->ifexpr_vec
.length ()
2129 && !s
->ifexpr_vec
[j
].is_with
);
2139 /* Analyze captures and perform early-outs on the incoming arguments
2140 that cover cases we cannot handle. */
2141 capture_info
cinfo (s
);
2145 && !((e
= dyn_cast
<expr
*> (s
->result
))
2146 && is_a
<predicate_id
*> (e
->operation
)))
2148 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2149 if (cinfo
.force_no_side_effects
& (1 << i
))
2150 fprintf (f
, "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", i
);
2151 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2152 if (cinfo
.info
[i
].cse_p
)
2154 else if (cinfo
.info
[i
].force_no_side_effects_p
2155 && (cinfo
.info
[i
].toplevel_msk
2156 & cinfo
.force_no_side_effects
) == 0)
2157 fprintf (f
, "if (TREE_SIDE_EFFECTS (captures[%d])) "
2158 "return NULL_TREE;\n", i
);
2159 else if ((cinfo
.info
[i
].toplevel_msk
2160 & cinfo
.force_no_side_effects
) != 0)
2161 /* Mark capture as having no side-effects if we had to verify
2162 that via forced toplevel operand checks. */
2163 cinfo
.info
[i
].force_no_side_effects_p
= true;
2166 fprintf (f
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2167 "fprintf (dump_file, \"Applying pattern ");
2168 output_line_directive (f
, s
->result_location
, true);
2169 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2171 operand
*result
= s
->result
;
2174 /* If there is no result then this is a predicate implementation. */
2175 fprintf (f
, "return true;\n");
2179 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2180 in outermost position). */
2181 if (result
->type
== operand::OP_EXPR
2182 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2183 result
= as_a
<expr
*> (result
)->ops
[0];
2184 if (result
->type
== operand::OP_EXPR
)
2186 expr
*e
= as_a
<expr
*> (result
);
2187 bool is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2189 fprintf (f
, "*res_code = %s;\n", e
->operation
->id
);
2190 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2193 snprintf (dest
, 32, " res_ops[%d]", j
);
2195 = get_operand_type (e
->operation
,
2196 "type", e
->expr_type
,
2198 ? NULL
: "TREE_TYPE (res_ops[0])");
2199 e
->ops
[j
]->gen_transform (f
, dest
, true, 1, optype
, indexes
);
2202 /* Re-fold the toplevel result. It's basically an embedded
2203 gimple_build w/o actually building the stmt. */
2205 fprintf (f
, "gimple_resimplify%d (seq, res_code, type, "
2206 "res_ops, valueize);\n", e
->ops
.length ());
2208 else if (result
->type
== operand::OP_CAPTURE
2209 || result
->type
== operand::OP_C_EXPR
)
2211 result
->gen_transform (f
, "res_ops[0]", true, 1, "type", indexes
);
2212 fprintf (f
, "*res_code = TREE_CODE (res_ops[0]);\n");
2216 fprintf (f
, "return true;\n");
2220 bool is_predicate
= false;
2221 if (result
->type
== operand::OP_EXPR
)
2223 expr
*e
= as_a
<expr
*> (result
);
2224 is_predicate
= is_a
<predicate_id
*> (e
->operation
);
2225 /* Search for captures used multiple times in the result expression
2226 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
2228 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2230 if (!cinfo
.info
[i
].force_no_side_effects_p
2231 && cinfo
.info
[i
].result_use_count
> 1)
2232 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2233 " captures[%d] = save_expr (captures[%d]);\n",
2236 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2240 snprintf (dest
, 32, "res_ops[%d]", j
);
2243 fprintf (f
, " tree res_op%d;\n", j
);
2244 snprintf (dest
, 32, " res_op%d", j
);
2247 = get_operand_type (e
->operation
,
2248 "type", e
->expr_type
,
2250 ? NULL
: "TREE_TYPE (res_op0)");
2251 e
->ops
[j
]->gen_transform (f
, dest
, false, 1, optype
, indexes
);
2254 fprintf (f
, "return true;\n");
2257 fprintf (f
, " tree res;\n");
2258 /* Re-fold the toplevel result. Use non_lvalue to
2259 build NON_LVALUE_EXPRs so they get properly
2260 ignored when in GIMPLE form. */
2261 if (*e
->operation
== NON_LVALUE_EXPR
)
2262 fprintf (f
, " res = non_lvalue_loc (loc, res_op0);\n");
2265 if (e
->operation
->kind
== id_base::CODE
)
2266 fprintf (f
, " res = fold_build%d_loc (loc, %s, type",
2267 e
->ops
.length (), e
->operation
->id
);
2269 fprintf (f
, " res = build_call_expr_loc "
2270 "(loc, builtin_decl_implicit (%s), %d",
2271 e
->operation
->id
, e
->ops
.length());
2272 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2273 fprintf (f
, ", res_op%d", j
);
2274 fprintf (f
, ");\n");
2278 else if (result
->type
== operand::OP_CAPTURE
2279 || result
->type
== operand::OP_C_EXPR
)
2282 fprintf (f
, " tree res;\n");
2283 s
->result
->gen_transform (f
, " res", false, 1, "type", indexes
);
2289 /* Search for captures not used in the result expression and dependent
2290 on TREE_SIDE_EFFECTS emit omit_one_operand. */
2291 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
2293 if (!cinfo
.info
[i
].force_no_side_effects_p
2294 && !cinfo
.info
[i
].expr_p
2295 && cinfo
.info
[i
].result_use_count
== 0)
2296 fprintf (f
, " if (TREE_SIDE_EFFECTS (captures[%d]))\n"
2297 " res = build2_loc (loc, COMPOUND_EXPR, type,"
2298 " fold_ignored_result (captures[%d]), res);\n",
2301 fprintf (f
, " return res;\n");
2305 for (unsigned i
= 0; i
< n_braces
; ++i
)
2311 /* Main entry to generate code for matching GIMPLE IL off the decision
2315 decision_tree::gen_gimple (FILE *f
)
2317 for (unsigned n
= 1; n
<= 3; ++n
)
2319 fprintf (f
, "\nstatic bool\n"
2320 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
2321 " gimple_seq *seq, tree (*valueize)(tree),\n"
2322 " code_helper code, tree type");
2323 for (unsigned i
= 0; i
< n
; ++i
)
2324 fprintf (f
, ", tree op%d", i
);
2328 fprintf (f
, "switch (code.get_rep())\n"
2330 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2332 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2333 expr
*e
= static_cast<expr
*>(dop
->op
);
2334 if (e
->ops
.length () != n
)
2337 if (*e
->operation
== CONVERT_EXPR
2338 || *e
->operation
== NOP_EXPR
)
2339 fprintf (f
, "CASE_CONVERT:\n");
2341 fprintf (f
, "case %s%s:\n",
2342 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
2345 dop
->gen_kids (f
, true);
2346 fprintf (f
, "break;\n");
2349 fprintf (f
, "default:;\n"
2352 fprintf (f
, "return false;\n");
2357 /* Main entry to generate code for matching GENERIC IL off the decision
2361 decision_tree::gen_generic (FILE *f
)
2363 for (unsigned n
= 1; n
<= 3; ++n
)
2365 fprintf (f
, "\ntree\n"
2366 "generic_simplify (location_t loc, enum tree_code code, "
2367 "tree type ATTRIBUTE_UNUSED");
2368 for (unsigned i
= 0; i
< n
; ++i
)
2369 fprintf (f
, ", tree op%d", i
);
2373 fprintf (f
, "switch (code)\n"
2375 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
2377 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
2378 expr
*e
= static_cast<expr
*>(dop
->op
);
2379 if (e
->ops
.length () != n
2380 /* Builtin simplifications are somewhat premature on
2381 GENERIC. The following drops patterns with outermost
2382 calls. It's easy to emit overloads for function code
2383 though if necessary. */
2384 || e
->operation
->kind
!= id_base::CODE
)
2387 operator_id
*op_id
= static_cast <operator_id
*> (e
->operation
);
2388 if (op_id
->code
== NOP_EXPR
|| op_id
->code
== CONVERT_EXPR
)
2389 fprintf (f
, "CASE_CONVERT:\n");
2391 fprintf (f
, "case %s:\n", e
->operation
->id
);
2393 dop
->gen_kids (f
, false);
2394 fprintf (f
, "break;\n"
2397 fprintf (f
, "default:;\n"
2400 fprintf (f
, "return NULL_TREE;\n");
2405 /* Output code to implement the predicate P from the decision tree DT. */
2408 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
2410 fprintf (f
, "\nbool\n"
2411 "%s%s (tree t%s%s)\n"
2412 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
2413 p
->nargs
> 0 ? ", tree *res_ops" : "",
2414 gimple
? ", tree (*valueize)(tree)" : "");
2415 /* Conveniently make 'type' available. */
2416 fprintf (f
, "tree type = TREE_TYPE (t);\n");
2419 fprintf (f
, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
2420 dt
.root
->gen_kids (f
, gimple
);
2422 fprintf (f
, "return false;\n"
2426 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
2429 write_header (FILE *f
, const char *head
)
2431 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
2432 fprintf (f
, " a IL pattern matching and simplification description. */\n");
2434 /* Include the header instead of writing it awkwardly quoted here. */
2435 fprintf (f
, "\n#include \"%s\"\n", head
);
2445 parser (cpp_reader
*);
2448 const cpp_token
*next ();
2449 const cpp_token
*peek ();
2450 const cpp_token
*peek_ident (const char * = NULL
);
2451 const cpp_token
*expect (enum cpp_ttype
);
2452 void eat_token (enum cpp_ttype
);
2453 const char *get_string ();
2454 const char *get_ident ();
2455 void eat_ident (const char *);
2456 const char *get_number ();
2458 id_base
*parse_operation ();
2459 operand
*parse_capture (operand
*);
2460 operand
*parse_expr ();
2461 c_expr
*parse_c_expr (cpp_ttype
);
2462 operand
*parse_op ();
2464 void parse_pattern ();
2465 void parse_simplify (source_location
, vec
<simplify
*>&, predicate_id
*,
2467 void parse_for (source_location
);
2468 void parse_if (source_location
);
2469 void parse_predicates (source_location
);
2472 vec
<if_or_with
> active_ifs
;
2473 vec
<vec
<user_id
*> > active_fors
;
2475 cid_map_t
*capture_ids
;
2478 vec
<simplify
*> simplifiers
;
2479 vec
<predicate_id
*> user_predicates
;
2482 /* Lexing helpers. */
2484 /* Read the next non-whitespace token from R. */
2489 const cpp_token
*token
;
2492 token
= cpp_get_token (r
);
2494 while (token
->type
== CPP_PADDING
2495 && token
->type
!= CPP_EOF
);
2499 /* Peek at the next non-whitespace token from R. */
2504 const cpp_token
*token
;
2508 token
= cpp_peek_token (r
, i
++);
2510 while (token
->type
== CPP_PADDING
2511 && token
->type
!= CPP_EOF
);
2512 /* If we peek at EOF this is a fatal error as it leaves the
2513 cpp_reader in unusable state. Assume we really wanted a
2514 token and thus this EOF is unexpected. */
2515 if (token
->type
== CPP_EOF
)
2516 fatal_at (token
, "unexpected end of file");
2520 /* Peek at the next identifier token (or return NULL if the next
2521 token is not an identifier or equal to ID if supplied). */
2524 parser::peek_ident (const char *id
)
2526 const cpp_token
*token
= peek ();
2527 if (token
->type
!= CPP_NAME
)
2533 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2534 if (strcmp (id
, t
) == 0)
2540 /* Read the next token from R and assert it is of type TK. */
2543 parser::expect (enum cpp_ttype tk
)
2545 const cpp_token
*token
= next ();
2546 if (token
->type
!= tk
)
2547 fatal_at (token
, "expected %s, got %s",
2548 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
2553 /* Consume the next token from R and assert it is of type TK. */
2556 parser::eat_token (enum cpp_ttype tk
)
2561 /* Read the next token from R and assert it is of type CPP_STRING and
2562 return its value. */
2565 parser::get_string ()
2567 const cpp_token
*token
= expect (CPP_STRING
);
2568 return (const char *)token
->val
.str
.text
;
2571 /* Read the next token from R and assert it is of type CPP_NAME and
2572 return its value. */
2575 parser::get_ident ()
2577 const cpp_token
*token
= expect (CPP_NAME
);
2578 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
2581 /* Eat an identifier token with value S from R. */
2584 parser::eat_ident (const char *s
)
2586 const cpp_token
*token
= peek ();
2587 const char *t
= get_ident ();
2588 if (strcmp (s
, t
) != 0)
2589 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
2592 /* Read the next token from R and assert it is of type CPP_NUMBER and
2593 return its value. */
2596 parser::get_number ()
2598 const cpp_token
*token
= expect (CPP_NUMBER
);
2599 return (const char *)token
->val
.str
.text
;
2603 /* Parse the operator ID, special-casing convert?, convert1? and
2607 parser::parse_operation ()
2609 const cpp_token
*id_tok
= peek ();
2610 const char *id
= get_ident ();
2611 const cpp_token
*token
= peek ();
2612 if (strcmp (id
, "convert0") == 0)
2613 fatal_at (id_tok
, "use 'convert?' here");
2614 if (token
->type
== CPP_QUERY
2615 && !(token
->flags
& PREV_WHITE
))
2617 if (strcmp (id
, "convert") == 0)
2619 else if (strcmp (id
, "convert1") == 0)
2621 else if (strcmp (id
, "convert2") == 0)
2624 fatal_at (id_tok
, "non-convert operator conditionalized");
2625 eat_token (CPP_QUERY
);
2627 else if (strcmp (id
, "convert1") == 0
2628 || strcmp (id
, "convert2") == 0)
2629 fatal_at (id_tok
, "expected '?' after conditional operator");
2630 id_base
*op
= get_operator (id
);
2632 fatal_at (id_tok
, "unknown operator %s", id
);
2637 capture = '@'<number> */
2640 parser::parse_capture (operand
*op
)
2642 eat_token (CPP_ATSIGN
);
2643 const cpp_token
*token
= peek ();
2645 if (token
->type
== CPP_NUMBER
)
2647 else if (token
->type
== CPP_NAME
)
2650 fatal_at (token
, "expected number or identifier");
2651 unsigned next_id
= capture_ids
->elements ();
2653 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
2656 return new capture (num
, op
);
2659 /* Parse an expression
2660 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
2663 parser::parse_expr ()
2665 expr
*e
= new expr (parse_operation ());
2666 const cpp_token
*token
= peek ();
2668 bool is_commutative
= false;
2669 const char *expr_type
= NULL
;
2671 if (token
->type
== CPP_COLON
2672 && !(token
->flags
& PREV_WHITE
))
2674 eat_token (CPP_COLON
);
2676 if (token
->type
== CPP_NAME
2677 && !(token
->flags
& PREV_WHITE
))
2679 const char *s
= get_ident ();
2680 if (s
[0] == 'c' && !s
[1])
2681 is_commutative
= true;
2682 else if (s
[1] != '\0')
2685 fatal_at (token
, "flag %s not recognized", s
);
2689 fatal_at (token
, "expected flag or type specifying identifier");
2692 if (token
->type
== CPP_ATSIGN
2693 && !(token
->flags
& PREV_WHITE
))
2694 op
= parse_capture (e
);
2699 const cpp_token
*token
= peek ();
2700 if (token
->type
== CPP_CLOSE_PAREN
)
2702 if (e
->operation
->nargs
!= -1
2703 && e
->operation
->nargs
!= (int) e
->ops
.length ())
2704 fatal_at (token
, "'%s' expects %u operands, not %u",
2705 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
2708 if (e
->ops
.length () == 2)
2709 e
->is_commutative
= true;
2711 fatal_at (token
, "only binary operators or function with "
2712 "two arguments can be marked commutative");
2714 e
->expr_type
= expr_type
;
2717 e
->append_op (parse_op ());
2722 /* Lex native C code delimited by START recording the preprocessing tokens
2723 for later processing.
2724 c_expr = ('{'|'(') <pp token>... ('}'|')') */
2727 parser::parse_c_expr (cpp_ttype start
)
2729 const cpp_token
*token
;
2732 vec
<cpp_token
> code
= vNULL
;
2733 unsigned nr_stmts
= 0;
2735 if (start
== CPP_OPEN_PAREN
)
2736 end
= CPP_CLOSE_PAREN
;
2737 else if (start
== CPP_OPEN_BRACE
)
2738 end
= CPP_CLOSE_BRACE
;
2746 /* Count brace pairs to find the end of the expr to match. */
2747 if (token
->type
== start
)
2749 else if (token
->type
== end
2753 /* This is a lame way of counting the number of statements. */
2754 if (token
->type
== CPP_SEMICOLON
)
2757 /* Record the token. */
2758 code
.safe_push (*token
);
2761 return new c_expr (r
, code
, nr_stmts
, vNULL
, capture_ids
);
2764 /* Parse an operand which is either an expression, a predicate or
2765 a standalone capture.
2766 op = predicate | expr | c_expr | capture */
2771 const cpp_token
*token
= peek ();
2772 struct operand
*op
= NULL
;
2773 if (token
->type
== CPP_OPEN_PAREN
)
2775 eat_token (CPP_OPEN_PAREN
);
2777 eat_token (CPP_CLOSE_PAREN
);
2779 else if (token
->type
== CPP_OPEN_BRACE
)
2781 op
= parse_c_expr (CPP_OPEN_BRACE
);
2785 /* Remaining ops are either empty or predicates */
2786 if (token
->type
== CPP_NAME
)
2788 const char *id
= get_ident ();
2789 id_base
*opr
= get_operator (id
);
2791 fatal_at (token
, "expected predicate name");
2792 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
2794 if (code
->nargs
!= 0)
2795 fatal_at (token
, "using an operator with operands as predicate");
2796 /* Parse the zero-operand operator "predicates" as
2798 op
= new expr (opr
);
2800 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
2801 op
= new predicate (p
);
2803 fatal_at (token
, "using an unsupported operator as predicate");
2805 if (token
->flags
& PREV_WHITE
)
2808 else if (token
->type
!= CPP_COLON
2809 && token
->type
!= CPP_ATSIGN
)
2810 fatal_at (token
, "expected expression or predicate");
2811 /* optionally followed by a capture and a predicate. */
2812 if (token
->type
== CPP_COLON
)
2813 fatal_at (token
, "not implemented: predicate on leaf operand");
2814 if (token
->type
== CPP_ATSIGN
)
2815 op
= parse_capture (op
);
2822 simplify = 'simplify' <expr> <result-op>
2824 match = 'match' <ident> <expr> [<result-op>]
2826 <result-op> = <op> | <if> | <with>
2827 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
2828 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
2829 and fill SIMPLIFIERS with the results. */
2832 parser::parse_simplify (source_location match_location
,
2833 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
2836 /* Reset the capture map. */
2837 capture_ids
= new cid_map_t
;
2839 const cpp_token
*loc
= peek ();
2840 struct operand
*match
= parse_op ();
2841 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
2842 fatal_at (loc
, "outermost expression cannot be captured");
2843 if (match
->type
== operand::OP_EXPR
2844 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
2845 fatal_at (loc
, "outermost expression cannot be a predicate");
2847 const cpp_token
*token
= peek ();
2849 /* If this if is immediately closed then it is part of a predicate
2850 definition. Push it. */
2851 if (token
->type
== CPP_CLOSE_PAREN
)
2854 fatal_at (token
, "expected transform expression");
2855 simplifiers
.safe_push
2856 (new simplify (match
, match_location
, result
, token
->src_loc
,
2857 active_ifs
.copy (), active_fors
.copy (),
2862 unsigned active_ifs_len
= active_ifs
.length ();
2865 if (token
->type
== CPP_OPEN_PAREN
)
2867 source_location paren_loc
= token
->src_loc
;
2868 eat_token (CPP_OPEN_PAREN
);
2869 if (peek_ident ("if"))
2872 active_ifs
.safe_push (if_or_with (parse_c_expr (CPP_OPEN_PAREN
),
2873 token
->src_loc
, false));
2874 /* If this if is immediately closed then it contains a
2875 manual matcher or is part of a predicate definition.
2877 if (peek ()->type
== CPP_CLOSE_PAREN
)
2880 fatal_at (token
, "manual transform not implemented");
2881 simplifiers
.safe_push
2882 (new simplify (match
, match_location
, result
,
2883 paren_loc
, active_ifs
.copy (),
2884 active_fors
.copy (), capture_ids
));
2887 else if (peek_ident ("with"))
2890 /* Parse (with c-expr expr) as (if-with (true) expr). */
2891 c_expr
*e
= parse_c_expr (CPP_OPEN_BRACE
);
2893 active_ifs
.safe_push (if_or_with (e
, token
->src_loc
, true));
2897 operand
*op
= result
;
2900 simplifiers
.safe_push
2901 (new simplify (match
, match_location
, op
,
2902 token
->src_loc
, active_ifs
.copy (),
2903 active_fors
.copy (), capture_ids
));
2904 eat_token (CPP_CLOSE_PAREN
);
2905 /* A "default" result closes the enclosing scope. */
2906 if (active_ifs
.length () > active_ifs_len
)
2908 eat_token (CPP_CLOSE_PAREN
);
2915 else if (token
->type
== CPP_CLOSE_PAREN
)
2917 /* Close a scope if requested. */
2918 if (active_ifs
.length () > active_ifs_len
)
2920 eat_token (CPP_CLOSE_PAREN
);
2930 fatal_at (token
, "expected match operand expression");
2931 simplifiers
.safe_push
2932 (new simplify (match
, match_location
,
2933 matcher
? result
: parse_op (),
2934 token
->src_loc
, active_ifs
.copy (),
2935 active_fors
.copy (), capture_ids
));
2936 /* A "default" result closes the enclosing scope. */
2937 if (active_ifs
.length () > active_ifs_len
)
2939 eat_token (CPP_CLOSE_PAREN
);
2949 /* Parsing of the outer control structures. */
2951 /* Parse a for expression
2952 for = '(' 'for' <subst>... <pattern> ')'
2953 subst = <ident> '(' <ident>... ')' */
2956 parser::parse_for (source_location
)
2958 vec
<user_id
*> user_ids
= vNULL
;
2959 const cpp_token
*token
;
2960 unsigned min_n_opers
= 0, max_n_opers
= 0;
2964 token
= peek_ident ();
2968 /* Insert the user defined operators into the operator hash. */
2969 const char *id
= get_ident ();
2970 user_id
*op
= new user_id (id
);
2971 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
2973 fatal_at (token
, "operator already defined");
2975 user_ids
.safe_push (op
);
2977 eat_token (CPP_OPEN_PAREN
);
2980 while ((token
= peek_ident ()) != 0)
2982 const char *oper
= get_ident ();
2983 id_base
*idb
= get_operator (oper
);
2985 fatal_at (token
, "no such operator '%s'", oper
);
2986 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
)
2987 fatal_at (token
, "conditional operators cannot be used inside for");
2991 else if (idb
->nargs
== -1)
2993 else if (idb
->nargs
!= arity
)
2994 fatal_at (token
, "operator '%s' with arity %d does not match "
2995 "others with arity %d", oper
, idb
->nargs
, arity
);
2997 op
->substitutes
.safe_push (idb
);
3000 token
= expect (CPP_CLOSE_PAREN
);
3002 unsigned nsubstitutes
= op
->substitutes
.length ();
3003 if (nsubstitutes
== 0)
3004 fatal_at (token
, "A user-defined operator must have at least "
3005 "one substitution");
3006 if (max_n_opers
== 0)
3008 min_n_opers
= nsubstitutes
;
3009 max_n_opers
= nsubstitutes
;
3013 if (nsubstitutes
% min_n_opers
!= 0
3014 && min_n_opers
% nsubstitutes
!= 0)
3015 fatal_at (token
, "All user-defined identifiers must have a "
3016 "multiple number of operator substitutions of the "
3017 "smallest number of substitutions");
3018 if (nsubstitutes
< min_n_opers
)
3019 min_n_opers
= nsubstitutes
;
3020 else if (nsubstitutes
> max_n_opers
)
3021 max_n_opers
= nsubstitutes
;
3025 unsigned n_ids
= user_ids
.length ();
3027 fatal_at (token
, "for requires at least one user-defined identifier");
3030 if (token
->type
== CPP_CLOSE_PAREN
)
3031 fatal_at (token
, "no pattern defined in for");
3033 active_fors
.safe_push (user_ids
);
3037 if (token
->type
== CPP_CLOSE_PAREN
)
3043 /* Remove user-defined operators from the hash again. */
3044 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
3045 operators
->remove_elt (user_ids
[i
]);
3048 /* Parse an outer if expression.
3049 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
3052 parser::parse_if (source_location loc
)
3054 operand
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
3056 const cpp_token
*token
= peek ();
3057 if (token
->type
== CPP_CLOSE_PAREN
)
3058 fatal_at (token
, "no pattern defined in if");
3060 active_ifs
.safe_push (if_or_with (ifexpr
, loc
, false));
3063 const cpp_token
*token
= peek ();
3064 if (token
->type
== CPP_CLOSE_PAREN
)
3072 /* Parse a list of predefined predicate identifiers.
3073 preds = '(' 'define_predicates' <ident>... ')' */
3076 parser::parse_predicates (source_location
)
3080 const cpp_token
*token
= peek ();
3081 if (token
->type
!= CPP_NAME
)
3084 add_predicate (get_ident ());
3089 /* Parse outer control structures.
3090 pattern = <preds>|<for>|<if>|<simplify>|<match> */
3093 parser::parse_pattern ()
3095 /* All clauses start with '('. */
3096 eat_token (CPP_OPEN_PAREN
);
3097 const cpp_token
*token
= peek ();
3098 const char *id
= get_ident ();
3099 if (strcmp (id
, "simplify") == 0)
3100 parse_simplify (token
->src_loc
, simplifiers
, NULL
, NULL
);
3101 else if (strcmp (id
, "match") == 0)
3103 bool with_args
= false;
3104 if (peek ()->type
== CPP_OPEN_PAREN
)
3106 eat_token (CPP_OPEN_PAREN
);
3109 const char *name
= get_ident ();
3110 id_base
*id
= get_operator (name
);
3114 p
= add_predicate (name
);
3115 user_predicates
.safe_push (p
);
3117 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
3120 fatal_at (token
, "cannot add a match to a non-predicate ID");
3121 /* Parse (match <id> <arg>... (match-expr)) here. */
3126 while (peek ()->type
== CPP_ATSIGN
)
3127 e
->append_op (parse_capture (NULL
));
3128 eat_token (CPP_CLOSE_PAREN
);
3131 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
3132 || (!e
&& p
->nargs
!= 0)))
3133 fatal_at (token
, "non-matching number of match operands");
3134 p
->nargs
= e
? e
->ops
.length () : 0;
3135 parse_simplify (token
->src_loc
, p
->matchers
, p
, e
);
3137 else if (strcmp (id
, "for") == 0)
3138 parse_for (token
->src_loc
);
3139 else if (strcmp (id
, "if") == 0)
3140 parse_if (token
->src_loc
);
3141 else if (strcmp (id
, "define_predicates") == 0)
3143 if (active_ifs
.length () > 0
3144 || active_fors
.length () > 0)
3145 fatal_at (token
, "define_predicates inside if or for is not supported");
3146 parse_predicates (token
->src_loc
);
3149 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
3150 active_ifs
.length () == 0 && active_fors
.length () == 0
3151 ? "'define_predicates', " : "");
3153 eat_token (CPP_CLOSE_PAREN
);
3156 /* Main entry of the parser. Repeatedly parse outer control structures. */
3158 parser::parser (cpp_reader
*r_
)
3162 active_fors
= vNULL
;
3163 simplifiers
= vNULL
;
3164 user_predicates
= vNULL
;
3166 const cpp_token
*token
= next ();
3167 while (token
->type
!= CPP_EOF
)
3169 _cpp_backup_tokens (r
, 1);
3176 /* Helper for the linemap code. */
3179 round_alloc_size (size_t s
)
3185 /* The genmatch generator progam. It reads from a pattern description
3186 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
3189 main (int argc
, char **argv
)
3193 progname
= "genmatch";
3199 bool verbose
= false;
3200 char *input
= argv
[argc
-1];
3201 for (int i
= 1; i
< argc
- 1; ++i
)
3203 if (strcmp (argv
[i
], "--gimple") == 0)
3205 else if (strcmp (argv
[i
], "--generic") == 0)
3207 else if (strcmp (argv
[i
], "-v") == 0)
3211 fprintf (stderr
, "Usage: genmatch "
3212 "[--gimple] [--generic] [-v] input\n");
3217 line_table
= XCNEW (struct line_maps
);
3218 linemap_init (line_table
, 0);
3219 line_table
->reallocator
= xrealloc
;
3220 line_table
->round_alloc_size
= round_alloc_size
;
3222 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
3223 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
3224 cb
->error
= error_cb
;
3226 if (!cpp_read_main_file (r
, input
))
3228 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
3229 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
3231 /* Pre-seed operators. */
3232 operators
= new hash_table
<id_base
> (1024);
3233 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
3234 add_operator (SYM, # SYM, # TYPE, NARGS);
3235 #define END_OF_BASE_TREE_CODES
3237 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
3238 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
3239 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
3240 #undef END_OF_BASE_TREE_CODES
3243 /* Pre-seed builtin functions.
3244 ??? Cannot use N (name) as that is targetm.emultls.get_address
3245 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
3246 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
3247 add_builtin (ENUM, # ENUM);
3248 #include "builtins.def"
3255 write_header (stdout
, "gimple-match-head.c");
3257 write_header (stdout
, "generic-match-head.c");
3259 /* Go over all predicates defined with patterns and perform
3260 lowering and code generation. */
3261 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
3263 predicate_id
*pred
= p
.user_predicates
[i
];
3264 lower (pred
->matchers
);
3267 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3268 print_matches (pred
->matchers
[i
]);
3271 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
3272 dt
.insert (pred
->matchers
[i
], i
);
3277 write_predicate (stdout
, pred
, dt
, gimple
);
3280 /* Lower the main simplifiers and generate code for them. */
3281 lower (p
.simplifiers
);
3284 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3285 print_matches (p
.simplifiers
[i
]);
3288 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
3289 dt
.insert (p
.simplifiers
[i
], i
);
3295 dt
.gen_gimple (stdout
);
3297 dt
.gen_generic (stdout
);
3300 cpp_finish (r
, NULL
);