1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2019 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/>. */
26 #include "coretypes.h"
29 #include "hash-table.h"
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL
)
40 void ggc_free (void *)
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
53 static class line_maps
*line_table
;
55 /* The rich_location class within libcpp requires a way to expand
56 location_t instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
61 This is the implementation for genmatch. */
64 linemap_client_expand_location_to_spelling_point (location_t loc
,
67 const struct line_map_ordinary
*map
;
68 loc
= linemap_resolve_location (line_table
, loc
, LRK_SPELLING_LOCATION
, &map
);
69 return linemap_expand_location (line_table
, map
, loc
);
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf
, 5, 0)))
76 diagnostic_cb (cpp_reader
*, enum cpp_diagnostic_level errtype
,
77 enum cpp_warning_reason
, rich_location
*richloc
,
78 const char *msg
, va_list *ap
)
80 const line_map_ordinary
*map
;
81 location_t location
= richloc
->get_loc ();
82 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
83 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
84 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
85 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
86 vfprintf (stderr
, msg
, *ap
);
87 fprintf (stderr
, "\n");
88 FILE *f
= fopen (loc
.file
, "r");
94 if (!fgets (buf
, 128, f
))
96 if (buf
[strlen (buf
) - 1] != '\n')
103 fprintf (stderr
, "%s", buf
);
104 for (int i
= 0; i
< loc
.column
- 1; ++i
)
107 fputc ('\n', stderr
);
112 if (errtype
== CPP_DL_FATAL
)
118 #if GCC_VERSION >= 4001
119 __attribute__((format (printf
, 2, 3)))
121 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
123 rich_location
richloc (line_table
, tk
->src_loc
);
126 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
131 #if GCC_VERSION >= 4001
132 __attribute__((format (printf
, 2, 3)))
134 fatal_at (location_t loc
, const char *msg
, ...)
136 rich_location
richloc (line_table
, loc
);
139 diagnostic_cb (NULL
, CPP_DL_FATAL
, CPP_W_NONE
, &richloc
, msg
, &ap
);
144 #if GCC_VERSION >= 4001
145 __attribute__((format (printf
, 2, 3)))
147 warning_at (const cpp_token
*tk
, const char *msg
, ...)
149 rich_location
richloc (line_table
, tk
->src_loc
);
152 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
157 #if GCC_VERSION >= 4001
158 __attribute__((format (printf
, 2, 3)))
160 warning_at (location_t loc
, const char *msg
, ...)
162 rich_location
richloc (line_table
, loc
);
165 diagnostic_cb (NULL
, CPP_DL_WARNING
, CPP_W_NONE
, &richloc
, msg
, &ap
);
169 /* Like fprintf, but print INDENT spaces at the beginning. */
172 #if GCC_VERSION >= 4001
173 __attribute__((format (printf
, 3, 4)))
175 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
178 for (; indent
>= 8; indent
-= 8)
180 fprintf (f
, "%*s", indent
, "");
181 va_start (ap
, format
);
182 vfprintf (f
, format
, ap
);
187 output_line_directive (FILE *f
, location_t location
,
188 bool dumpfile
= false, bool fnargs
= false)
190 const line_map_ordinary
*map
;
191 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
192 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
195 /* When writing to a dumpfile only dump the filename. */
196 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
197 #if defined(DIR_SEPARATOR_2)
198 const char *pos2
= strrchr (loc
.file
, DIR_SEPARATOR_2
);
199 if (pos2
&& (!file
|| (pos2
> file
)))
208 fprintf (f
, "\"%s\", %d", file
, loc
.line
);
210 fprintf (f
, "%s:%d", file
, loc
.line
);
213 /* Other gen programs really output line directives here, at least for
214 development it's right now more convenient to have line information
215 from the generated file. Still keep the directives as comment for now
216 to easily back-point to the meta-description. */
217 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
221 /* Pull in tree codes and builtin function codes from their
224 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
237 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
238 enum built_in_function
{
239 #include "builtins.def"
243 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
245 #include "internal-fn.def"
250 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
251 CFN_##ENUM = int (ENUM),
252 #include "builtins.def"
254 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) \
255 CFN_##CODE = int (END_BUILTINS) + int (IFN_##CODE),
256 #include "internal-fn.def"
261 #include "case-cfn-macros.h"
263 /* Return true if CODE represents a commutative tree code. Otherwise
266 commutative_tree_code (enum tree_code code
)
272 case MULT_HIGHPART_EXPR
:
287 case WIDEN_MULT_EXPR
:
288 case VEC_WIDEN_MULT_HI_EXPR
:
289 case VEC_WIDEN_MULT_LO_EXPR
:
290 case VEC_WIDEN_MULT_EVEN_EXPR
:
291 case VEC_WIDEN_MULT_ODD_EXPR
:
300 /* Return true if CODE represents a ternary tree code for which the
301 first two operands are commutative. Otherwise return false. */
303 commutative_ternary_tree_code (enum tree_code code
)
307 case WIDEN_MULT_PLUS_EXPR
:
308 case WIDEN_MULT_MINUS_EXPR
:
318 /* Return true if CODE is a comparison. */
321 comparison_code_p (enum tree_code code
)
348 /* Base class for all identifiers the parser knows. */
350 class id_base
: public nofree_ptr_hash
<id_base
>
353 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
, NULL_ID
} kind
;
355 id_base (id_kind
, const char *, int = -1);
361 /* hash_table support. */
362 static inline hashval_t
hash (const id_base
*);
363 static inline int equal (const id_base
*, const id_base
*);
367 id_base::hash (const id_base
*op
)
373 id_base::equal (const id_base
*op1
,
376 return (op1
->hashval
== op2
->hashval
377 && strcmp (op1
->id
, op2
->id
) == 0);
380 /* The special id "null", which matches nothing. */
381 static id_base
*null_id
;
383 /* Hashtable of known pattern operators. This is pre-seeded from
384 all known tree codes and all known builtin function ids. */
385 static hash_table
<id_base
> *operators
;
387 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
392 hashval
= htab_hash_string (id
);
395 /* Identifier that maps to a tree code. */
397 class operator_id
: public id_base
400 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
402 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
407 /* Identifier that maps to a builtin or internal function code. */
409 class fn_id
: public id_base
412 fn_id (enum built_in_function fn_
, const char *id_
)
413 : id_base (id_base::FN
, id_
), fn (fn_
) {}
414 fn_id (enum internal_fn fn_
, const char *id_
)
415 : id_base (id_base::FN
, id_
), fn (int (END_BUILTINS
) + int (fn_
)) {}
421 /* Identifier that maps to a user-defined predicate. */
423 class predicate_id
: public id_base
426 predicate_id (const char *id_
)
427 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
428 vec
<simplify
*> matchers
;
431 /* Identifier that maps to a operator defined by a 'for' directive. */
433 class user_id
: public id_base
436 user_id (const char *id_
, bool is_oper_list_
= false)
437 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
438 used (false), is_oper_list (is_oper_list_
) {}
439 vec
<id_base
*> substitutes
;
447 is_a_helper
<fn_id
*>::test (id_base
*id
)
449 return id
->kind
== id_base::FN
;
455 is_a_helper
<operator_id
*>::test (id_base
*id
)
457 return id
->kind
== id_base::CODE
;
463 is_a_helper
<predicate_id
*>::test (id_base
*id
)
465 return id
->kind
== id_base::PREDICATE
;
471 is_a_helper
<user_id
*>::test (id_base
*id
)
473 return id
->kind
== id_base::USER
;
476 /* If ID has a pair of consecutive, commutative operands, return the
477 index of the first, otherwise return -1. */
480 commutative_op (id_base
*id
)
482 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
484 if (commutative_tree_code (code
->code
)
485 || commutative_ternary_tree_code (code
->code
))
489 if (fn_id
*fn
= dyn_cast
<fn_id
*> (id
))
501 if (user_id
*uid
= dyn_cast
<user_id
*> (id
))
503 int res
= commutative_op (uid
->substitutes
[0]);
506 for (unsigned i
= 1; i
< uid
->substitutes
.length (); ++i
)
507 if (res
!= commutative_op (uid
->substitutes
[i
]))
514 /* Add a predicate identifier to the hash. */
516 static predicate_id
*
517 add_predicate (const char *id
)
519 predicate_id
*p
= new predicate_id (id
);
520 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
522 fatal ("duplicate id definition");
527 /* Add a tree code identifier to the hash. */
530 add_operator (enum tree_code code
, const char *id
,
531 const char *tcc
, unsigned nargs
)
533 if (strcmp (tcc
, "tcc_unary") != 0
534 && strcmp (tcc
, "tcc_binary") != 0
535 && strcmp (tcc
, "tcc_comparison") != 0
536 && strcmp (tcc
, "tcc_expression") != 0
537 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
538 && strcmp (tcc
, "tcc_reference") != 0
539 /* To have INTEGER_CST and friends as "predicate operators". */
540 && strcmp (tcc
, "tcc_constant") != 0
541 /* And allow CONSTRUCTOR for vector initializers. */
542 && !(code
== CONSTRUCTOR
)
543 /* Allow SSA_NAME as predicate operator. */
544 && !(code
== SSA_NAME
))
546 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
547 if (code
== ADDR_EXPR
)
549 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
550 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
552 fatal ("duplicate id definition");
556 /* Add a built-in or internal function identifier to the hash. ID is
557 the name of its CFN_* enumeration value. */
559 template <typename T
>
561 add_function (T code
, const char *id
)
563 fn_id
*fn
= new fn_id (code
, id
);
564 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
566 fatal ("duplicate id definition");
570 /* Helper for easy comparing ID with tree code CODE. */
573 operator==(id_base
&id
, enum tree_code code
)
575 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
576 return oid
->code
== code
;
580 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
583 get_operator (const char *id
, bool allow_null
= false)
585 if (allow_null
&& strcmp (id
, "null") == 0)
588 id_base
tem (id_base::CODE
, id
);
590 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
593 /* If this is a user-defined identifier track whether it was used. */
594 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
600 bool all_upper
= true;
601 bool all_lower
= true;
602 for (unsigned int i
= 0; id
[i
]; ++i
)
605 else if (ISLOWER (id
[i
]))
609 /* Try in caps with _EXPR appended. */
610 id2
= ACONCAT ((id
, "_EXPR", NULL
));
611 for (unsigned int i
= 0; id2
[i
]; ++i
)
612 id2
[i
] = TOUPPER (id2
[i
]);
614 else if (all_upper
&& strncmp (id
, "IFN_", 4) == 0)
615 /* Try CFN_ instead of IFN_. */
616 id2
= ACONCAT (("CFN_", id
+ 4, NULL
));
617 else if (all_upper
&& strncmp (id
, "BUILT_IN_", 9) == 0)
618 /* Try prepending CFN_. */
619 id2
= ACONCAT (("CFN_", id
, NULL
));
623 new (&tem
) id_base (id_base::CODE
, id2
);
624 return operators
->find_with_hash (&tem
, tem
.hashval
);
627 /* Return the comparison operators that results if the operands are
628 swapped. This is safe for floating-point. */
631 swap_tree_comparison (operator_id
*p
)
643 return get_operator ("LT_EXPR");
645 return get_operator ("LE_EXPR");
647 return get_operator ("GT_EXPR");
649 return get_operator ("GE_EXPR");
651 return get_operator ("UNLT_EXPR");
653 return get_operator ("UNLE_EXPR");
655 return get_operator ("UNGT_EXPR");
657 return get_operator ("UNGE_EXPR");
663 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
666 /* The AST produced by parsing of the pattern definitions. */
671 /* The base class for operands. */
675 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
676 operand (enum op_type type_
, location_t loc_
)
677 : type (type_
), location (loc_
) {}
680 virtual void gen_transform (FILE *, int, const char *, bool, int,
681 const char *, capture_info
*,
684 { gcc_unreachable (); }
687 /* A predicate operand. Predicates are leafs in the AST. */
689 class predicate
: public operand
692 predicate (predicate_id
*p_
, location_t loc
)
693 : operand (OP_PREDICATE
, loc
), p (p_
) {}
697 /* An operand that constitutes an expression. Expressions include
698 function calls and user-defined predicate invocations. */
700 class expr
: public operand
703 expr (id_base
*operation_
, location_t loc
, bool is_commutative_
= false)
704 : operand (OP_EXPR
, loc
), operation (operation_
),
705 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
706 is_generic (false), force_single_use (false) {}
708 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
709 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
710 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
711 void append_op (operand
*op
) { ops
.safe_push (op
); }
712 /* The operator and its operands. */
715 /* An explicitely specified type - used exclusively for conversions. */
716 const char *expr_type
;
717 /* Whether the operation is to be applied commutatively. This is
718 later lowered to two separate patterns. */
720 /* Whether the expression is expected to be in GENERIC form. */
722 /* Whether pushing any stmt to the sequence should be conditional
723 on this expression having a single-use. */
724 bool force_single_use
;
725 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
726 const char *, capture_info
*,
727 dt_operand
** = 0, int = 0);
730 /* An operator that is represented by native C code. This is always
731 a leaf operand in the AST. This class is also used to represent
732 the code to be generated for 'if' and 'with' expressions. */
734 class c_expr
: public operand
737 /* A mapping of an identifier and its replacement. Used to apply
743 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
746 c_expr (cpp_reader
*r_
, location_t loc
,
747 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
748 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
749 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
750 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
751 /* cpplib tokens and state to transform this back to source. */
754 cid_map_t
*capture_ids
;
755 /* The number of statements parsed (well, the number of ';'s). */
757 /* The identifier replacement vector. */
759 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
760 const char *, capture_info
*,
761 dt_operand
** = 0, int = 0);
764 /* A wrapper around another operand that captures its value. */
766 class capture
: public operand
769 capture (location_t loc
, unsigned where_
, operand
*what_
, bool value_
)
770 : operand (OP_CAPTURE
, loc
), where (where_
), value_match (value_
),
772 /* Identifier index for the value. */
774 /* Whether in a match of two operands the compare should be for
775 equal values rather than equal atoms (boils down to a type
778 /* The captured value. */
780 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
781 const char *, capture_info
*,
782 dt_operand
** = 0, int = 0);
787 class if_expr
: public operand
790 if_expr (location_t loc
)
791 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
797 /* with expression. */
799 class with_expr
: public operand
802 with_expr (location_t loc
)
803 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
811 is_a_helper
<capture
*>::test (operand
*op
)
813 return op
->type
== operand::OP_CAPTURE
;
819 is_a_helper
<predicate
*>::test (operand
*op
)
821 return op
->type
== operand::OP_PREDICATE
;
827 is_a_helper
<c_expr
*>::test (operand
*op
)
829 return op
->type
== operand::OP_C_EXPR
;
835 is_a_helper
<expr
*>::test (operand
*op
)
837 return op
->type
== operand::OP_EXPR
;
843 is_a_helper
<if_expr
*>::test (operand
*op
)
845 return op
->type
== operand::OP_IF
;
851 is_a_helper
<with_expr
*>::test (operand
*op
)
853 return op
->type
== operand::OP_WITH
;
856 /* The main class of a pattern and its transform. This is used to
857 represent both (simplify ...) and (match ...) kinds. The AST
858 duplicates all outer 'if' and 'for' expressions here so each
859 simplify can exist in isolation. */
864 enum simplify_kind
{ SIMPLIFY
, MATCH
};
866 simplify (simplify_kind kind_
, unsigned id_
, operand
*match_
,
867 operand
*result_
, vec
<vec
<user_id
*> > for_vec_
,
868 cid_map_t
*capture_ids_
)
869 : kind (kind_
), id (id_
), match (match_
), result (result_
),
870 for_vec (for_vec_
), for_subst_vec (vNULL
),
871 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
874 /* ID. This is kept to easily associate related simplifies expanded
875 from the same original one. */
877 /* The expression that is matched against the GENERIC or GIMPLE IL. */
879 /* For a (simplify ...) an expression with ifs and withs with the expression
880 produced when the pattern applies in the leafs.
881 For a (match ...) the leafs are either empty if it is a simple predicate
882 or the single expression specifying the matched operands. */
883 class operand
*result
;
884 /* Collected 'for' expression operators that have to be replaced
885 in the lowering phase. */
886 vec
<vec
<user_id
*> > for_vec
;
887 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
888 /* A map of capture identifiers to indexes. */
889 cid_map_t
*capture_ids
;
893 /* Debugging routines for dumping the AST. */
896 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
898 if (capture
*c
= dyn_cast
<capture
*> (o
))
900 if (c
->what
&& flattened
== false)
901 print_operand (c
->what
, f
, flattened
);
902 fprintf (f
, "@%u", c
->where
);
905 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
906 fprintf (f
, "%s", p
->p
->id
);
908 else if (is_a
<c_expr
*> (o
))
909 fprintf (f
, "c_expr");
911 else if (expr
*e
= dyn_cast
<expr
*> (o
))
913 if (e
->ops
.length () == 0)
914 fprintf (f
, "%s", e
->operation
->id
);
917 fprintf (f
, "(%s", e
->operation
->id
);
919 if (flattened
== false)
921 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
924 print_operand (e
->ops
[i
], f
, flattened
);
936 print_matches (class simplify
*s
, FILE *f
= stderr
)
938 fprintf (f
, "for expression: ");
939 print_operand (s
->match
, f
);
946 /* Lowering of commutative operators. */
949 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
950 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
952 if (n
== ops_vector
.length ())
954 vec
<operand
*> xv
= v
.copy ();
955 result
.safe_push (xv
);
959 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
961 v
[n
] = ops_vector
[n
][i
];
962 cartesian_product (ops_vector
, result
, v
, n
+ 1);
966 /* Lower OP to two operands in case it is marked as commutative. */
968 static vec
<operand
*>
969 commutate (operand
*op
, vec
<vec
<user_id
*> > &for_vec
)
971 vec
<operand
*> ret
= vNULL
;
973 if (capture
*c
= dyn_cast
<capture
*> (op
))
980 vec
<operand
*> v
= commutate (c
->what
, for_vec
);
981 for (unsigned i
= 0; i
< v
.length (); ++i
)
983 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
],
990 expr
*e
= dyn_cast
<expr
*> (op
);
991 if (!e
|| e
->ops
.length () == 0)
997 vec
< vec
<operand
*> > ops_vector
= vNULL
;
998 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
999 ops_vector
.safe_push (commutate (e
->ops
[i
], for_vec
));
1001 auto_vec
< vec
<operand
*> > result
;
1002 auto_vec
<operand
*> v (e
->ops
.length ());
1003 v
.quick_grow_cleared (e
->ops
.length ());
1004 cartesian_product (ops_vector
, result
, v
, 0);
1007 for (unsigned i
= 0; i
< result
.length (); ++i
)
1009 expr
*ne
= new expr (e
);
1010 ne
->is_commutative
= false;
1011 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1012 ne
->append_op (result
[i
][j
]);
1016 if (!e
->is_commutative
)
1019 /* The operation is always binary if it isn't inherently commutative. */
1020 int natural_opno
= commutative_op (e
->operation
);
1021 unsigned int opno
= natural_opno
>= 0 ? natural_opno
: 0;
1022 for (unsigned i
= 0; i
< result
.length (); ++i
)
1024 expr
*ne
= new expr (e
);
1025 if (operator_id
*r
= dyn_cast
<operator_id
*> (ne
->operation
))
1027 if (comparison_code_p (r
->code
))
1028 ne
->operation
= swap_tree_comparison (r
);
1030 else if (user_id
*p
= dyn_cast
<user_id
*> (ne
->operation
))
1032 bool found_compare
= false;
1033 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1034 if (operator_id
*q
= dyn_cast
<operator_id
*> (p
->substitutes
[j
]))
1036 if (comparison_code_p (q
->code
)
1037 && swap_tree_comparison (q
) != q
)
1039 found_compare
= true;
1045 user_id
*newop
= new user_id ("<internal>");
1046 for (unsigned j
= 0; j
< p
->substitutes
.length (); ++j
)
1048 id_base
*subst
= p
->substitutes
[j
];
1049 if (operator_id
*q
= dyn_cast
<operator_id
*> (subst
))
1051 if (comparison_code_p (q
->code
))
1052 subst
= swap_tree_comparison (q
);
1054 newop
->substitutes
.safe_push (subst
);
1056 ne
->operation
= newop
;
1057 /* Search for 'p' inside the for vector and push 'newop'
1058 to the same level. */
1059 for (unsigned j
= 0; newop
&& j
< for_vec
.length (); ++j
)
1060 for (unsigned k
= 0; k
< for_vec
[j
].length (); ++k
)
1061 if (for_vec
[j
][k
] == p
)
1063 for_vec
[j
].safe_push (newop
);
1069 ne
->is_commutative
= false;
1070 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1072 int old_j
= (j
== opno
? opno
+ 1 : j
== opno
+ 1 ? opno
: j
);
1073 ne
->append_op (result
[i
][old_j
]);
1081 /* Lower operations marked as commutative in the AST of S and push
1082 the resulting patterns to SIMPLIFIERS. */
1085 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
1087 vec
<operand
*> matchers
= commutate (s
->match
, s
->for_vec
);
1088 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1090 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1091 s
->for_vec
, s
->capture_ids
);
1092 simplifiers
.safe_push (ns
);
1096 /* Strip conditional conversios using operator OPER from O and its
1097 children if STRIP, else replace them with an unconditional convert. */
1100 lower_opt_convert (operand
*o
, enum tree_code oper
,
1101 enum tree_code to_oper
, bool strip
)
1103 if (capture
*c
= dyn_cast
<capture
*> (o
))
1106 return new capture (c
->location
, c
->where
,
1107 lower_opt_convert (c
->what
, oper
, to_oper
, strip
),
1113 expr
*e
= dyn_cast
<expr
*> (o
);
1117 if (*e
->operation
== oper
)
1120 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
1122 expr
*ne
= new expr (e
);
1123 ne
->operation
= (to_oper
== CONVERT_EXPR
1124 ? get_operator ("CONVERT_EXPR")
1125 : get_operator ("VIEW_CONVERT_EXPR"));
1126 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
1130 expr
*ne
= new expr (e
);
1131 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1132 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
1137 /* Determine whether O or its children uses the conditional conversion
1141 has_opt_convert (operand
*o
, enum tree_code oper
)
1143 if (capture
*c
= dyn_cast
<capture
*> (o
))
1146 return has_opt_convert (c
->what
, oper
);
1151 expr
*e
= dyn_cast
<expr
*> (o
);
1155 if (*e
->operation
== oper
)
1158 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1159 if (has_opt_convert (e
->ops
[i
], oper
))
1165 /* Lower conditional convert operators in O, expanding it to a vector
1168 static vec
<operand
*>
1169 lower_opt_convert (operand
*o
)
1171 vec
<operand
*> v1
= vNULL
, v2
;
1175 enum tree_code opers
[]
1176 = { CONVERT0
, CONVERT_EXPR
,
1177 CONVERT1
, CONVERT_EXPR
,
1178 CONVERT2
, CONVERT_EXPR
,
1179 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
1180 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
1181 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
1183 /* Conditional converts are lowered to a pattern with the
1184 conversion and one without. The three different conditional
1185 convert codes are lowered separately. */
1187 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
1190 for (unsigned j
= 0; j
< v1
.length (); ++j
)
1191 if (has_opt_convert (v1
[j
], opers
[i
]))
1193 v2
.safe_push (lower_opt_convert (v1
[j
],
1194 opers
[i
], opers
[i
+1], false));
1195 v2
.safe_push (lower_opt_convert (v1
[j
],
1196 opers
[i
], opers
[i
+1], true));
1202 for (unsigned j
= 0; j
< v2
.length (); ++j
)
1203 v1
.safe_push (v2
[j
]);
1210 /* Lower conditional convert operators in the AST of S and push
1211 the resulting multiple patterns to SIMPLIFIERS. */
1214 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
1216 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
1217 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1219 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1220 s
->for_vec
, s
->capture_ids
);
1221 simplifiers
.safe_push (ns
);
1225 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1226 GENERIC and a GIMPLE variant. */
1228 static vec
<operand
*>
1229 lower_cond (operand
*o
)
1231 vec
<operand
*> ro
= vNULL
;
1233 if (capture
*c
= dyn_cast
<capture
*> (o
))
1237 vec
<operand
*> lop
= vNULL
;
1238 lop
= lower_cond (c
->what
);
1240 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1241 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
],
1247 expr
*e
= dyn_cast
<expr
*> (o
);
1248 if (!e
|| e
->ops
.length () == 0)
1254 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1255 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1256 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1258 auto_vec
< vec
<operand
*> > result
;
1259 auto_vec
<operand
*> v (e
->ops
.length ());
1260 v
.quick_grow_cleared (e
->ops
.length ());
1261 cartesian_product (ops_vector
, result
, v
, 0);
1263 for (unsigned i
= 0; i
< result
.length (); ++i
)
1265 expr
*ne
= new expr (e
);
1266 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1267 ne
->append_op (result
[i
][j
]);
1269 /* If this is a COND with a captured expression or an
1270 expression with two operands then also match a GENERIC
1271 form on the compare. */
1272 if ((*e
->operation
== COND_EXPR
1273 || *e
->operation
== VEC_COND_EXPR
)
1274 && ((is_a
<capture
*> (e
->ops
[0])
1275 && as_a
<capture
*> (e
->ops
[0])->what
1276 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1278 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1279 || (is_a
<expr
*> (e
->ops
[0])
1280 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1283 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1284 ne
->append_op (result
[i
][j
]);
1285 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1287 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1288 expr
*cmp
= new expr (ocmp
);
1289 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1290 cmp
->append_op (ocmp
->ops
[j
]);
1291 cmp
->is_generic
= true;
1292 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
,
1297 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1298 expr
*cmp
= new expr (ocmp
);
1299 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1300 cmp
->append_op (ocmp
->ops
[j
]);
1301 cmp
->is_generic
= true;
1311 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1312 GENERIC and a GIMPLE variant. */
1315 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1317 vec
<operand
*> matchers
= lower_cond (s
->match
);
1318 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1320 simplify
*ns
= new simplify (s
->kind
, s
->id
, matchers
[i
], s
->result
,
1321 s
->for_vec
, s
->capture_ids
);
1322 simplifiers
.safe_push (ns
);
1326 /* Return true if O refers to ID. */
1329 contains_id (operand
*o
, user_id
*id
)
1331 if (capture
*c
= dyn_cast
<capture
*> (o
))
1332 return c
->what
&& contains_id (c
->what
, id
);
1334 if (expr
*e
= dyn_cast
<expr
*> (o
))
1336 if (e
->operation
== id
)
1338 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1339 if (contains_id (e
->ops
[i
], id
))
1344 if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1345 return (contains_id (w
->with
, id
)
1346 || contains_id (w
->subexpr
, id
));
1348 if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1349 return (contains_id (ife
->cond
, id
)
1350 || contains_id (ife
->trueexpr
, id
)
1351 || (ife
->falseexpr
&& contains_id (ife
->falseexpr
, id
)));
1353 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1354 return ce
->capture_ids
&& ce
->capture_ids
->get (id
->id
);
1360 /* In AST operand O replace operator ID with operator WITH. */
1363 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1365 /* Deep-copy captures and expressions, replacing operations as
1367 if (capture
*c
= dyn_cast
<capture
*> (o
))
1371 return new capture (c
->location
, c
->where
,
1372 replace_id (c
->what
, id
, with
), c
->value_match
);
1374 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1376 expr
*ne
= new expr (e
);
1377 if (e
->operation
== id
)
1378 ne
->operation
= with
;
1379 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1380 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1383 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1385 with_expr
*nw
= new with_expr (w
->location
);
1386 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1387 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1390 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1392 if_expr
*nife
= new if_expr (ife
->location
);
1393 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1394 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1396 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1400 /* For c_expr we simply record a string replacement table which is
1401 applied at code-generation time. */
1402 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1404 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1405 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1406 return new c_expr (ce
->r
, ce
->location
,
1407 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1413 /* Return true if the binary operator OP is ok for delayed substitution
1414 during for lowering. */
1417 binary_ok (operator_id
*op
)
1424 case TRUNC_DIV_EXPR
:
1426 case FLOOR_DIV_EXPR
:
1427 case ROUND_DIV_EXPR
:
1428 case TRUNC_MOD_EXPR
:
1430 case FLOOR_MOD_EXPR
:
1431 case ROUND_MOD_EXPR
:
1433 case EXACT_DIV_EXPR
:
1445 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1448 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1450 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1451 unsigned worklist_start
= 0;
1452 auto_vec
<simplify
*> worklist
;
1453 worklist
.safe_push (sin
);
1455 /* Lower each recorded for separately, operating on the
1456 set of simplifiers created by the previous one.
1457 Lower inner-to-outer so inner for substitutes can refer
1458 to operators replaced by outer fors. */
1459 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1461 vec
<user_id
*>& ids
= for_vec
[fi
];
1462 unsigned n_ids
= ids
.length ();
1463 unsigned max_n_opers
= 0;
1464 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1465 for (unsigned i
= 0; i
< n_ids
; ++i
)
1467 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1468 max_n_opers
= ids
[i
]->substitutes
.length ();
1469 /* Require that all substitutes are of the same kind so that
1470 if we delay substitution to the result op code generation
1471 can look at the first substitute for deciding things like
1472 types of operands. */
1473 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1474 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1475 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1476 can_delay_subst
= false;
1477 else if (operator_id
*op
1478 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1481 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1482 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1483 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1485 /* Unfortunately we can't just allow all tcc_binary. */
1486 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1487 && strcmp (op0
->tcc
, "tcc_binary") == 0
1491 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1492 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1493 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1494 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1497 can_delay_subst
= false;
1499 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1502 can_delay_subst
= false;
1505 unsigned worklist_end
= worklist
.length ();
1506 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1508 simplify
*s
= worklist
[si
];
1509 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1511 operand
*match_op
= s
->match
;
1512 operand
*result_op
= s
->result
;
1513 auto_vec
<std::pair
<user_id
*, id_base
*> > subst (n_ids
);
1515 for (unsigned i
= 0; i
< n_ids
; ++i
)
1517 user_id
*id
= ids
[i
];
1518 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1520 && (contains_id (match_op
, id
)
1521 || contains_id (result_op
, id
)))
1526 subst
.quick_push (std::make_pair (id
, oper
));
1527 match_op
= replace_id (match_op
, id
, oper
);
1529 && !can_delay_subst
)
1530 result_op
= replace_id (result_op
, id
, oper
);
1535 simplify
*ns
= new simplify (s
->kind
, s
->id
, match_op
, result_op
,
1536 vNULL
, s
->capture_ids
);
1537 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1540 ns
->for_subst_vec
.safe_splice (subst
);
1542 worklist
.safe_push (ns
);
1545 worklist_start
= worklist_end
;
1548 /* Copy out the result from the last for lowering. */
1549 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1550 simplifiers
.safe_push (worklist
[i
]);
1553 /* Lower the AST for everything in SIMPLIFIERS. */
1556 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1558 auto_vec
<simplify
*> out_simplifiers
;
1559 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1560 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1562 simplifiers
.truncate (0);
1563 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1564 lower_commutative (out_simplifiers
[i
], simplifiers
);
1566 out_simplifiers
.truncate (0);
1568 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1569 lower_cond (simplifiers
[i
], out_simplifiers
);
1571 out_simplifiers
.safe_splice (simplifiers
);
1574 simplifiers
.truncate (0);
1575 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1576 lower_for (out_simplifiers
[i
], simplifiers
);
1582 /* The decision tree built for generating GIMPLE and GENERIC pattern
1583 matching code. It represents the 'match' expression of all
1584 simplifies and has those as its leafs. */
1588 /* A hash-map collecting semantically equivalent leafs in the decision
1589 tree for splitting out to separate functions. */
1598 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
>,
1601 static inline hashval_t
hash (const key_type
&);
1602 static inline bool equal_keys (const key_type
&, const key_type
&);
1603 template <typename T
> static inline void remove (T
&) {}
1606 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1609 /* Current simplifier ID we are processing during insertion into the
1611 static unsigned current_id
;
1613 /* Decision tree base class, used for DT_NODE. */
1618 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1623 vec
<dt_node
*> kids
;
1627 unsigned total_size
;
1630 dt_node (enum dt_type type_
, dt_node
*parent_
)
1631 : type (type_
), level (0), parent (parent_
), kids (vNULL
) {}
1633 dt_node
*append_node (dt_node
*);
1634 dt_node
*append_op (operand
*, dt_node
*parent
, unsigned pos
);
1635 dt_node
*append_true_op (operand
*, dt_node
*parent
, unsigned pos
);
1636 dt_node
*append_match_op (operand
*, dt_operand
*, dt_node
*parent
,
1638 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1640 virtual void gen (FILE *, int, bool, int) {}
1642 void gen_kids (FILE *, int, bool, int);
1643 void gen_kids_1 (FILE *, int, bool, int,
1644 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1645 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1647 void analyze (sinfo_map_t
&);
1650 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1652 class dt_operand
: public dt_node
1656 dt_operand
*match_dop
;
1661 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1662 dt_operand
*parent_
, unsigned pos_
)
1663 : dt_node (type
, parent_
), op (op_
), match_dop (match_dop_
),
1664 pos (pos_
), value_match (false), for_id (current_id
) {}
1666 void gen (FILE *, int, bool, int);
1667 unsigned gen_predicate (FILE *, int, const char *, bool);
1668 unsigned gen_match_op (FILE *, int, const char *, bool);
1670 unsigned gen_gimple_expr (FILE *, int, int);
1671 unsigned gen_generic_expr (FILE *, int, const char *);
1673 char *get_name (char *);
1674 void gen_opname (char *, unsigned);
1677 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1679 class dt_simplify
: public dt_node
1683 unsigned pattern_no
;
1684 dt_operand
**indexes
;
1687 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1688 : dt_node (DT_SIMPLIFY
, NULL
), s (s_
), pattern_no (pattern_no_
),
1689 indexes (indexes_
), info (NULL
) {}
1691 void gen_1 (FILE *, int, bool, operand
*);
1692 void gen (FILE *f
, int, bool, int);
1698 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1700 return (n
->type
== dt_node::DT_OPERAND
1701 || n
->type
== dt_node::DT_MATCH
1702 || n
->type
== dt_node::DT_TRUE
);
1708 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1710 return n
->type
== dt_node::DT_SIMPLIFY
;
1715 /* A container for the actual decision tree. */
1722 void insert (class simplify
*, unsigned);
1723 void gen (FILE *f
, bool gimple
);
1724 void print (FILE *f
= stderr
);
1726 decision_tree () { root
= new dt_node (dt_node::DT_NODE
, NULL
); }
1728 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1729 unsigned pos
= 0, dt_node
*parent
= 0);
1730 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1731 static bool cmp_node (dt_node
*, dt_node
*);
1732 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1735 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1738 cmp_operand (operand
*o1
, operand
*o2
)
1740 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1743 if (o1
->type
== operand::OP_PREDICATE
)
1745 predicate
*p1
= as_a
<predicate
*>(o1
);
1746 predicate
*p2
= as_a
<predicate
*>(o2
);
1747 return p1
->p
== p2
->p
;
1749 else if (o1
->type
== operand::OP_EXPR
)
1751 expr
*e1
= static_cast<expr
*>(o1
);
1752 expr
*e2
= static_cast<expr
*>(o2
);
1753 return (e1
->operation
== e2
->operation
1754 && e1
->is_generic
== e2
->is_generic
);
1760 /* Compare two decision tree nodes N1 and N2 and return true if they
1764 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1766 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1772 if (n1
->type
== dt_node::DT_TRUE
)
1775 if (n1
->type
== dt_node::DT_OPERAND
)
1776 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1777 (as_a
<dt_operand
*> (n2
))->op
);
1778 else if (n1
->type
== dt_node::DT_MATCH
)
1779 return (((as_a
<dt_operand
*> (n1
))->match_dop
1780 == (as_a
<dt_operand
*> (n2
))->match_dop
)
1781 && ((as_a
<dt_operand
*> (n1
))->value_match
1782 == (as_a
<dt_operand
*> (n2
))->value_match
));
1786 /* Search OPS for a decision tree node like P and return it if found. */
1789 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1791 /* We can merge adjacent DT_TRUE. */
1792 if (p
->type
== dt_node::DT_TRUE
1794 && ops
.last ()->type
== dt_node::DT_TRUE
)
1796 dt_operand
*true_node
= NULL
;
1797 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1799 /* But we can't merge across DT_TRUE nodes as they serve as
1800 pattern order barriers to make sure that patterns apply
1801 in order of appearance in case multiple matches are possible. */
1802 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1805 || as_a
<dt_operand
*> (ops
[i
])->for_id
> true_node
->for_id
)
1806 true_node
= as_a
<dt_operand
*> (ops
[i
]);
1808 if (decision_tree::cmp_node (ops
[i
], p
))
1810 /* Unless we are processing the same pattern or the blocking
1811 pattern is before the one we are going to merge with. */
1813 && true_node
->for_id
!= current_id
1814 && true_node
->for_id
> as_a
<dt_operand
*> (ops
[i
])->for_id
)
1818 location_t p_loc
= 0;
1819 if (p
->type
== dt_node::DT_OPERAND
)
1820 p_loc
= as_a
<dt_operand
*> (p
)->op
->location
;
1821 location_t op_loc
= 0;
1822 if (ops
[i
]->type
== dt_node::DT_OPERAND
)
1823 op_loc
= as_a
<dt_operand
*> (ops
[i
])->op
->location
;
1824 location_t true_loc
= 0;
1825 true_loc
= true_node
->op
->location
;
1827 "failed to merge decision tree node");
1829 "with the following");
1830 warning_at (true_loc
,
1831 "because of the following which serves as ordering "
1842 /* Append N to the decision tree if it there is not already an existing
1846 dt_node::append_node (dt_node
*n
)
1850 kid
= decision_tree::find_node (kids
, n
);
1855 n
->level
= this->level
+ 1;
1860 /* Append OP to the decision tree. */
1863 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1865 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1866 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1867 return append_node (n
);
1870 /* Append a DT_TRUE decision tree node. */
1873 dt_node::append_true_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1875 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1876 dt_operand
*n
= new dt_operand (DT_TRUE
, op
, 0, parent_
, pos
);
1877 return append_node (n
);
1880 /* Append a DT_MATCH decision tree node. */
1883 dt_node::append_match_op (operand
*op
, dt_operand
*match_dop
,
1884 dt_node
*parent
, unsigned pos
)
1886 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1887 dt_operand
*n
= new dt_operand (DT_MATCH
, op
, match_dop
, parent_
, pos
);
1888 return append_node (n
);
1891 /* Append S to the decision tree. */
1894 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1895 dt_operand
**indexes
)
1898 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1899 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1900 if ((s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1902 || s
->match
->location
!= s2
->s
->match
->location
))
1904 /* With a nested patters, it's hard to avoid these in order
1905 to keep match.pd rules relatively small. */
1906 warning_at (s
->match
->location
, "duplicate pattern");
1907 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1908 print_operand (s
->match
, stderr
);
1909 fprintf (stderr
, "\n");
1911 return append_node (n
);
1914 /* Analyze the node and its children. */
1917 dt_node::analyze (sinfo_map_t
&map
)
1923 if (type
== DT_SIMPLIFY
)
1925 /* Populate the map of equivalent simplifies. */
1926 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1928 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1943 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1945 kids
[i
]->analyze (map
);
1946 num_leafs
+= kids
[i
]->num_leafs
;
1947 total_size
+= kids
[i
]->total_size
;
1948 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1952 /* Insert O into the decision tree and return the decision tree node found
1956 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1957 unsigned pos
, dt_node
*parent
)
1959 dt_node
*q
, *elm
= 0;
1961 if (capture
*c
= dyn_cast
<capture
*> (o
))
1963 unsigned capt_index
= c
->where
;
1965 if (indexes
[capt_index
] == 0)
1968 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1971 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1974 // get to the last capture
1975 for (operand
*what
= c
->what
;
1976 what
&& is_a
<capture
*> (what
);
1977 c
= as_a
<capture
*> (what
), what
= c
->what
)
1982 unsigned cc_index
= c
->where
;
1983 dt_operand
*match_op
= indexes
[cc_index
];
1985 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1986 elm
= decision_tree::find_node (p
->kids
, &temp
);
1990 dt_operand
match (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1991 match
.value_match
= c
->value_match
;
1992 elm
= decision_tree::find_node (p
->kids
, &match
);
1997 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1998 elm
= decision_tree::find_node (p
->kids
, &temp
);
2002 gcc_assert (elm
->type
== dt_node::DT_TRUE
2003 || elm
->type
== dt_node::DT_OPERAND
2004 || elm
->type
== dt_node::DT_MATCH
);
2005 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2010 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2011 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2013 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2018 p
= p
->append_op (o
, parent
, pos
);
2021 if (expr
*e
= dyn_cast
<expr
*>(o
))
2023 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2024 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2030 /* Insert S into the decision tree. */
2033 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2036 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2037 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2038 p
->append_simplify (s
, pattern_no
, indexes
);
2041 /* Debug functions to dump the decision tree. */
2044 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2046 if (p
->type
== dt_node::DT_NODE
)
2047 fprintf (f
, "root");
2051 for (unsigned i
= 0; i
< indent
; i
++)
2054 if (p
->type
== dt_node::DT_OPERAND
)
2056 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2057 print_operand (dop
->op
, f
, true);
2059 else if (p
->type
== dt_node::DT_TRUE
)
2060 fprintf (f
, "true");
2061 else if (p
->type
== dt_node::DT_MATCH
)
2062 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2063 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2065 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2066 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2067 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2068 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2071 if (is_a
<dt_operand
*> (p
))
2072 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2075 fprintf (stderr
, " (%p, %p), %u, %u\n",
2076 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2078 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2079 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2083 decision_tree::print (FILE *f
)
2085 return decision_tree::print_node (root
, f
);
2089 /* For GENERIC we have to take care of wrapping multiple-used
2090 expressions with side-effects in save_expr and preserve side-effects
2091 of expressions with omit_one_operand. Analyze captures in
2092 match, result and with expressions and perform early-outs
2093 on the outermost match expression operands for cases we cannot
2099 capture_info (simplify
*s
, operand
*, bool);
2100 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2101 bool walk_result (operand
*o
, bool, operand
*);
2102 void walk_c_expr (c_expr
*);
2108 bool force_no_side_effects_p
;
2109 bool force_single_use
;
2110 bool cond_expr_cond_p
;
2111 unsigned long toplevel_msk
;
2112 unsigned match_use_count
;
2113 unsigned result_use_count
;
2118 auto_vec
<cinfo
> info
;
2119 unsigned long force_no_side_effects
;
2123 /* Analyze captures in S. */
2125 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2130 if (s
->kind
== simplify::MATCH
)
2132 force_no_side_effects
= -1;
2136 force_no_side_effects
= 0;
2137 info
.safe_grow_cleared (s
->capture_max
+ 1);
2138 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2139 info
[i
].same_as
= i
;
2141 e
= as_a
<expr
*> (s
->match
);
2142 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2143 walk_match (e
->ops
[i
], i
,
2144 (i
!= 0 && *e
->operation
== COND_EXPR
)
2145 || *e
->operation
== TRUTH_ANDIF_EXPR
2146 || *e
->operation
== TRUTH_ORIF_EXPR
,
2148 && (*e
->operation
== COND_EXPR
2149 || *e
->operation
== VEC_COND_EXPR
));
2151 walk_result (s
->result
, false, result
);
2154 /* Analyze captures in the match expression piece O. */
2157 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2158 bool conditional_p
, bool cond_expr_cond_p
)
2160 if (capture
*c
= dyn_cast
<capture
*> (o
))
2162 unsigned where
= c
->where
;
2163 info
[where
].match_use_count
++;
2164 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2165 info
[where
].force_no_side_effects_p
|= conditional_p
;
2166 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2171 /* Recurse to exprs and captures. */
2172 if (is_a
<capture
*> (c
->what
)
2173 || is_a
<expr
*> (c
->what
))
2174 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2175 /* We need to look past multiple captures to find a captured
2176 expression as with conditional converts two captures
2177 can be collapsed onto the same expression. Also collect
2178 what captures capture the same thing. */
2179 while (c
->what
&& is_a
<capture
*> (c
->what
))
2181 c
= as_a
<capture
*> (c
->what
);
2182 if (info
[c
->where
].same_as
!= c
->where
2183 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2184 fatal_at (c
->location
, "cannot handle this collapsed capture");
2185 info
[c
->where
].same_as
= info
[where
].same_as
;
2187 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2190 && (e
= dyn_cast
<expr
*> (c
->what
)))
2192 /* Zero-operand expression captures like ADDR_EXPR@0 are
2193 similar as predicates -- if they are not mentioned in
2194 the result we have to force them to have no side-effects. */
2195 if (e
->ops
.length () != 0)
2196 info
[where
].expr_p
= true;
2197 info
[where
].force_single_use
|= e
->force_single_use
;
2200 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2202 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2204 bool cond_p
= conditional_p
;
2205 bool expr_cond_p
= false;
2206 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2208 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2209 || *e
->operation
== TRUTH_ORIF_EXPR
)
2212 && (*e
->operation
== COND_EXPR
2213 || *e
->operation
== VEC_COND_EXPR
))
2215 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, expr_cond_p
);
2218 else if (is_a
<predicate
*> (o
))
2220 /* Mark non-captured leafs toplevel arg for checking. */
2221 force_no_side_effects
|= 1 << toplevel_arg
;
2224 warning_at (o
->location
,
2225 "forcing no side-effects on possibly lost leaf");
2231 /* Analyze captures in the result expression piece O. Return true
2232 if RESULT was visited in one of the children. Only visit
2233 non-if/with children if they are rooted on RESULT. */
2236 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2238 if (capture
*c
= dyn_cast
<capture
*> (o
))
2240 unsigned where
= info
[c
->where
].same_as
;
2241 info
[where
].result_use_count
++;
2242 /* If we substitute an expression capture we don't know
2243 which captures this will end up using (well, we don't
2244 compute that). Force the uses to be side-effect free
2245 which means forcing the toplevels that reach the
2246 expression side-effect free. */
2247 if (info
[where
].expr_p
)
2248 force_no_side_effects
|= info
[where
].toplevel_msk
;
2249 /* Mark CSE capture uses as forced to have no side-effects. */
2251 && is_a
<expr
*> (c
->what
))
2253 info
[where
].cse_p
= true;
2254 walk_result (c
->what
, true, result
);
2257 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2259 id_base
*opr
= e
->operation
;
2260 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2261 opr
= uid
->substitutes
[0];
2262 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2264 bool cond_p
= conditional_p
;
2265 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2267 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2268 || *e
->operation
== TRUTH_ORIF_EXPR
)
2270 walk_result (e
->ops
[i
], cond_p
, result
);
2273 else if (if_expr
*ie
= dyn_cast
<if_expr
*> (o
))
2275 /* 'if' conditions should be all fine. */
2276 if (ie
->trueexpr
== result
)
2278 walk_result (ie
->trueexpr
, false, result
);
2281 if (ie
->falseexpr
== result
)
2283 walk_result (ie
->falseexpr
, false, result
);
2287 if (is_a
<if_expr
*> (ie
->trueexpr
)
2288 || is_a
<with_expr
*> (ie
->trueexpr
))
2289 res
|= walk_result (ie
->trueexpr
, false, result
);
2291 && (is_a
<if_expr
*> (ie
->falseexpr
)
2292 || is_a
<with_expr
*> (ie
->falseexpr
)))
2293 res
|= walk_result (ie
->falseexpr
, false, result
);
2296 else if (with_expr
*we
= dyn_cast
<with_expr
*> (o
))
2298 bool res
= (we
->subexpr
== result
);
2300 || is_a
<if_expr
*> (we
->subexpr
)
2301 || is_a
<with_expr
*> (we
->subexpr
))
2302 res
|= walk_result (we
->subexpr
, false, result
);
2304 walk_c_expr (we
->with
);
2307 else if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
2315 /* Look for captures in the C expr E. */
2318 capture_info::walk_c_expr (c_expr
*e
)
2320 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2321 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2322 really escape through. */
2323 unsigned p_depth
= 0;
2324 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2326 const cpp_token
*t
= &e
->code
[i
];
2327 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2329 if (t
->type
== CPP_NAME
2330 && (strcmp ((const char *)CPP_HASHNODE
2331 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2332 || strcmp ((const char *)CPP_HASHNODE
2333 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2334 || strcmp ((const char *)CPP_HASHNODE
2335 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2336 || ((id
= get_operator ((const char *)CPP_HASHNODE
2337 (t
->val
.node
.node
)->ident
.str
))
2338 && is_a
<predicate_id
*> (id
)))
2339 && n
->type
== CPP_OPEN_PAREN
)
2341 else if (t
->type
== CPP_CLOSE_PAREN
2344 else if (p_depth
== 0
2345 && t
->type
== CPP_ATSIGN
2346 && (n
->type
== CPP_NUMBER
2347 || n
->type
== CPP_NAME
)
2348 && !(n
->flags
& PREV_WHITE
))
2351 if (n
->type
== CPP_NUMBER
)
2352 id1
= (const char *)n
->val
.str
.text
;
2354 id1
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2355 unsigned *where
= e
->capture_ids
->get(id1
);
2357 fatal_at (n
, "unknown capture id '%s'", id1
);
2358 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2361 warning_at (t
, "capture escapes");
2367 /* Code generation off the decision tree and the refered AST nodes. */
2370 is_conversion (id_base
*op
)
2372 return (*op
== CONVERT_EXPR
2374 || *op
== FLOAT_EXPR
2375 || *op
== FIX_TRUNC_EXPR
2376 || *op
== VIEW_CONVERT_EXPR
);
2379 /* Get the type to be used for generating operand POS of OP from the
2383 get_operand_type (id_base
*op
, unsigned pos
,
2384 const char *in_type
,
2385 const char *expr_type
,
2386 const char *other_oprnd_type
)
2388 /* Generally operands whose type does not match the type of the
2389 expression generated need to know their types but match and
2390 thus can fall back to 'other_oprnd_type'. */
2391 if (is_conversion (op
))
2392 return other_oprnd_type
;
2393 else if (*op
== REALPART_EXPR
2394 || *op
== IMAGPART_EXPR
)
2395 return other_oprnd_type
;
2396 else if (is_a
<operator_id
*> (op
)
2397 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2398 return other_oprnd_type
;
2399 else if (*op
== COND_EXPR
2401 return "boolean_type_node";
2402 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2404 /* IFN_COND_* operands 1 and later by default have the same type
2405 as the result. The type of operand 0 needs to be specified
2407 if (pos
> 0 && expr_type
)
2409 else if (pos
> 0 && in_type
)
2416 /* Otherwise all types should match - choose one in order of
2423 return other_oprnd_type
;
2427 /* Generate transform code for an expression. */
2430 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2431 int depth
, const char *in_type
, capture_info
*cinfo
,
2432 dt_operand
**indexes
, int)
2434 id_base
*opr
= operation
;
2435 /* When we delay operator substituting during lowering of fors we
2436 make sure that for code-gen purposes the effects of each substitute
2437 are the same. Thus just look at that. */
2438 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2439 opr
= uid
->substitutes
[0];
2441 bool conversion_p
= is_conversion (opr
);
2442 const char *type
= expr_type
;
2445 /* If there was a type specification in the pattern use it. */
2447 else if (conversion_p
)
2448 /* For conversions we need to build the expression using the
2449 outer type passed in. */
2451 else if (*opr
== REALPART_EXPR
2452 || *opr
== IMAGPART_EXPR
)
2454 /* __real and __imag use the component type of its operand. */
2455 snprintf (optype
, sizeof (optype
), "TREE_TYPE (TREE_TYPE (_o%d[0]))",
2459 else if (is_a
<operator_id
*> (opr
)
2460 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2462 /* comparisons use boolean_type_node (or what gets in), but
2463 their operands need to figure out the types themselves. */
2468 snprintf (optype
, sizeof (optype
), "boolean_type_node");
2473 else if (*opr
== COND_EXPR
2474 || *opr
== VEC_COND_EXPR
2475 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2477 /* Conditions are of the same type as their first alternative. */
2478 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[1])", depth
);
2483 /* Other operations are of the same type as their first operand. */
2484 snprintf (optype
, sizeof (optype
), "TREE_TYPE (_o%d[0])", depth
);
2488 fatal_at (location
, "cannot determine type of operand");
2490 fprintf_indent (f
, indent
, "{\n");
2492 fprintf_indent (f
, indent
,
2493 "tree _o%d[%u], _r%d;\n", depth
, ops
.length (), depth
);
2495 snprintf (op0type
, sizeof (op0type
), "TREE_TYPE (_o%d[0])", depth
);
2496 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2499 snprintf (dest1
, sizeof (dest1
), "_o%d[%u]", depth
, i
);
2501 = get_operand_type (opr
, i
, in_type
, expr_type
,
2502 i
== 0 ? NULL
: op0type
);
2503 ops
[i
]->gen_transform (f
, indent
, dest1
, gimple
, depth
+ 1, optype1
,
2506 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2509 const char *opr_name
;
2510 if (*operation
== CONVERT_EXPR
)
2511 opr_name
= "NOP_EXPR";
2513 opr_name
= operation
->id
;
2517 if (*opr
== CONVERT_EXPR
)
2519 fprintf_indent (f
, indent
,
2520 "if (%s != TREE_TYPE (_o%d[0])\n",
2522 fprintf_indent (f
, indent
,
2523 " && !useless_type_conversion_p (%s, TREE_TYPE "
2526 fprintf_indent (f
, indent
+ 2, "{\n");
2529 /* ??? Building a stmt can fail for various reasons here, seq being
2530 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2531 So if we fail here we should continue matching other patterns. */
2532 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2533 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2534 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2535 fprintf (f
, ", _o%d[%u]", depth
, i
);
2536 fprintf (f
, ");\n");
2537 fprintf_indent (f
, indent
, "tem_op.resimplify (lseq, valueize);\n");
2538 fprintf_indent (f
, indent
,
2539 "_r%d = maybe_push_res_to_seq (&tem_op, lseq);\n", depth
);
2540 fprintf_indent (f
, indent
,
2541 "if (!_r%d) return false;\n",
2543 if (*opr
== CONVERT_EXPR
)
2546 fprintf_indent (f
, indent
, " }\n");
2547 fprintf_indent (f
, indent
, "else\n");
2548 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2553 if (*opr
== CONVERT_EXPR
)
2555 fprintf_indent (f
, indent
, "if (TREE_TYPE (_o%d[0]) != %s)\n",
2559 if (opr
->kind
== id_base::CODE
)
2560 fprintf_indent (f
, indent
, "_r%d = fold_build%d_loc (loc, %s, %s",
2561 depth
, ops
.length(), opr_name
, type
);
2564 fprintf_indent (f
, indent
, "{\n");
2565 fprintf_indent (f
, indent
, " _r%d = maybe_build_call_expr_loc (loc, "
2566 "%s, %s, %d", depth
, opr_name
, type
, ops
.length());
2568 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2569 fprintf (f
, ", _o%d[%u]", depth
, i
);
2570 fprintf (f
, ");\n");
2571 if (opr
->kind
!= id_base::CODE
)
2573 fprintf_indent (f
, indent
, " if (!_r%d)\n", depth
);
2574 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2575 fprintf_indent (f
, indent
, "}\n");
2577 if (*opr
== CONVERT_EXPR
)
2580 fprintf_indent (f
, indent
, "else\n");
2581 fprintf_indent (f
, indent
, " _r%d = _o%d[0];\n", depth
, depth
);
2584 fprintf_indent (f
, indent
, "%s = _r%d;\n", dest
, depth
);
2586 fprintf_indent (f
, indent
, "}\n");
2589 /* Generate code for a c_expr which is either the expression inside
2590 an if statement or a sequence of statements which computes a
2591 result to be stored to DEST. */
2594 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2595 bool, int, const char *, capture_info
*,
2598 if (dest
&& nr_stmts
== 1)
2599 fprintf_indent (f
, indent
, "%s = ", dest
);
2601 unsigned stmt_nr
= 1;
2602 for (unsigned i
= 0; i
< code
.length (); ++i
)
2604 const cpp_token
*token
= &code
[i
];
2606 /* Replace captures for code-gen. */
2607 if (token
->type
== CPP_ATSIGN
)
2609 const cpp_token
*n
= &code
[i
+1];
2610 if ((n
->type
== CPP_NUMBER
2611 || n
->type
== CPP_NAME
)
2612 && !(n
->flags
& PREV_WHITE
))
2614 if (token
->flags
& PREV_WHITE
)
2617 if (n
->type
== CPP_NUMBER
)
2618 id
= (const char *)n
->val
.str
.text
;
2620 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2621 unsigned *cid
= capture_ids
->get (id
);
2623 fatal_at (token
, "unknown capture id");
2624 fprintf (f
, "captures[%u]", *cid
);
2630 if (token
->flags
& PREV_WHITE
)
2633 if (token
->type
== CPP_NAME
)
2635 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2637 for (j
= 0; j
< ids
.length (); ++j
)
2639 if (strcmp (id
, ids
[j
].id
) == 0)
2641 fprintf (f
, "%s", ids
[j
].oper
);
2645 if (j
< ids
.length ())
2649 /* Output the token as string. */
2650 char *tk
= (char *)cpp_token_as_text (r
, token
);
2653 if (token
->type
== CPP_SEMICOLON
)
2657 if (dest
&& stmt_nr
== nr_stmts
)
2658 fprintf_indent (f
, indent
, "%s = ", dest
);
2663 /* Generate transform code for a capture. */
2666 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2667 int depth
, const char *in_type
, capture_info
*cinfo
,
2668 dt_operand
**indexes
, int cond_handling
)
2670 if (what
&& is_a
<expr
*> (what
))
2672 if (indexes
[where
] == 0)
2675 snprintf (buf
, sizeof (buf
), "captures[%u]", where
);
2676 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2681 /* If in GENERIC some capture is used multiple times, unshare it except
2682 when emitting the last use. */
2684 && cinfo
->info
.exists ()
2685 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2687 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2689 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2692 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2694 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2695 with substituting a capture of that. */
2697 && cond_handling
!= 0
2698 && cinfo
->info
[where
].cond_expr_cond_p
)
2700 /* If substituting into a cond_expr condition, unshare. */
2701 if (cond_handling
== 1)
2702 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2703 /* If substituting elsewhere we might need to decompose it. */
2704 else if (cond_handling
== 2)
2706 /* ??? Returning false here will also not allow any other patterns
2707 to match unless this generator was split out. */
2708 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2709 fprintf_indent (f
, indent
, " {\n");
2710 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2711 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2713 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2714 " TREE_OPERAND (%s, 1));\n",
2715 dest
, dest
, dest
, dest
, dest
);
2716 fprintf_indent (f
, indent
, " }\n");
2721 /* Return the name of the operand representing the decision tree node.
2722 Use NAME as space to generate it. */
2725 dt_operand::get_name (char *name
)
2728 sprintf (name
, "t");
2729 else if (parent
->level
== 1)
2730 sprintf (name
, "_p%u", pos
);
2731 else if (parent
->type
== dt_node::DT_MATCH
)
2732 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2734 sprintf (name
, "_q%u%u", parent
->level
, pos
);
2738 /* Fill NAME with the operand name at position POS. */
2741 dt_operand::gen_opname (char *name
, unsigned pos
)
2744 sprintf (name
, "_p%u", pos
);
2746 sprintf (name
, "_q%u%u", level
, pos
);
2749 /* Generate matching code for the decision tree operand which is
2753 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2755 predicate
*p
= as_a
<predicate
*> (op
);
2757 if (p
->p
->matchers
.exists ())
2759 /* If this is a predicate generated from a pattern mangle its
2760 name and pass on the valueize hook. */
2762 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2765 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2768 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2769 fprintf_indent (f
, indent
+ 2, "{\n");
2773 /* Generate matching code for the decision tree operand which is
2777 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2779 char match_opname
[20];
2780 match_dop
->get_name (match_opname
);
2782 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2783 "|| operand_equal_p (%s, %s, 0))\n",
2784 opname
, match_opname
, opname
, opname
, match_opname
);
2786 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2787 "|| (operand_equal_p (%s, %s, 0) "
2788 "&& types_match (%s, %s)))\n",
2789 opname
, match_opname
, opname
, opname
, match_opname
,
2790 opname
, match_opname
);
2791 fprintf_indent (f
, indent
+ 2, "{\n");
2795 /* Generate GIMPLE matching code for the decision tree operand. */
2798 dt_operand::gen_gimple_expr (FILE *f
, int indent
, int depth
)
2800 expr
*e
= static_cast<expr
*> (op
);
2801 id_base
*id
= e
->operation
;
2802 unsigned n_ops
= e
->ops
.length ();
2803 unsigned n_braces
= 0;
2805 for (unsigned i
= 0; i
< n_ops
; ++i
)
2807 char child_opname
[20];
2808 gen_opname (child_opname
, i
);
2810 if (id
->kind
== id_base::CODE
)
2813 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2814 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2816 /* ??? If this is a memory operation we can't (and should not)
2817 match this. The only sensible operand types are
2818 SSA names and invariants. */
2823 fprintf_indent (f
, indent
,
2824 "tree %s = TREE_OPERAND (%s, %i);\n",
2825 child_opname
, opname
, i
);
2828 fprintf_indent (f
, indent
,
2829 "tree %s = TREE_OPERAND "
2830 "(gimple_assign_rhs1 (_a%d), %i);\n",
2831 child_opname
, depth
, i
);
2832 fprintf_indent (f
, indent
,
2833 "if ((TREE_CODE (%s) == SSA_NAME\n",
2835 fprintf_indent (f
, indent
,
2836 " || is_gimple_min_invariant (%s)))\n",
2838 fprintf_indent (f
, indent
,
2842 fprintf_indent (f
, indent
,
2843 "%s = do_valueize (valueize, %s);\n",
2844 child_opname
, child_opname
);
2848 fprintf_indent (f
, indent
,
2849 "tree %s = gimple_assign_rhs%u (_a%d);\n",
2850 child_opname
, i
+ 1, depth
);
2853 fprintf_indent (f
, indent
,
2854 "tree %s = gimple_call_arg (_c%d, %u);\n",
2855 child_opname
, depth
, i
);
2856 fprintf_indent (f
, indent
,
2857 "%s = do_valueize (valueize, %s);\n",
2858 child_opname
, child_opname
);
2860 /* While the toplevel operands are canonicalized by the caller
2861 after valueizing operands of sub-expressions we have to
2862 re-canonicalize operand order. */
2863 int opno
= commutative_op (id
);
2866 char child_opname0
[20], child_opname1
[20];
2867 gen_opname (child_opname0
, opno
);
2868 gen_opname (child_opname1
, opno
+ 1);
2869 fprintf_indent (f
, indent
,
2870 "if (tree_swap_operands_p (%s, %s))\n",
2871 child_opname0
, child_opname1
);
2872 fprintf_indent (f
, indent
,
2873 " std::swap (%s, %s);\n",
2874 child_opname0
, child_opname1
);
2880 /* Generate GENERIC matching code for the decision tree operand. */
2883 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2885 expr
*e
= static_cast<expr
*> (op
);
2886 unsigned n_ops
= e
->ops
.length ();
2888 for (unsigned i
= 0; i
< n_ops
; ++i
)
2890 char child_opname
[20];
2891 gen_opname (child_opname
, i
);
2893 if (e
->operation
->kind
== id_base::CODE
)
2894 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2895 child_opname
, opname
, i
);
2897 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2898 child_opname
, opname
, i
);
2904 /* Generate matching code for the children of the decision tree node. */
2907 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
, int depth
)
2909 auto_vec
<dt_operand
*> gimple_exprs
;
2910 auto_vec
<dt_operand
*> generic_exprs
;
2911 auto_vec
<dt_operand
*> fns
;
2912 auto_vec
<dt_operand
*> generic_fns
;
2913 auto_vec
<dt_operand
*> preds
;
2914 auto_vec
<dt_node
*> others
;
2916 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2918 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2920 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2921 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2923 if (e
->ops
.length () == 0
2924 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2925 generic_exprs
.safe_push (op
);
2926 else if (e
->operation
->kind
== id_base::FN
)
2931 generic_fns
.safe_push (op
);
2933 else if (e
->operation
->kind
== id_base::PREDICATE
)
2934 preds
.safe_push (op
);
2937 if (gimple
&& !e
->is_generic
)
2938 gimple_exprs
.safe_push (op
);
2940 generic_exprs
.safe_push (op
);
2943 else if (op
->op
->type
== operand::OP_PREDICATE
)
2944 others
.safe_push (kids
[i
]);
2948 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2949 others
.safe_push (kids
[i
]);
2950 else if (kids
[i
]->type
== dt_node::DT_MATCH
2951 || kids
[i
]->type
== dt_node::DT_TRUE
)
2953 /* A DT_TRUE operand serves as a barrier - generate code now
2954 for what we have collected sofar.
2955 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2956 dependent matches to get out-of-order. Generate code now
2957 for what we have collected sofar. */
2958 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2959 fns
, generic_fns
, preds
, others
);
2960 /* And output the true operand itself. */
2961 kids
[i
]->gen (f
, indent
, gimple
, depth
);
2962 gimple_exprs
.truncate (0);
2963 generic_exprs
.truncate (0);
2965 generic_fns
.truncate (0);
2967 others
.truncate (0);
2973 /* Generate code for the remains. */
2974 gen_kids_1 (f
, indent
, gimple
, depth
, gimple_exprs
, generic_exprs
,
2975 fns
, generic_fns
, preds
, others
);
2978 /* Generate matching code for the children of the decision tree node. */
2981 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
, int depth
,
2982 vec
<dt_operand
*> gimple_exprs
,
2983 vec
<dt_operand
*> generic_exprs
,
2984 vec
<dt_operand
*> fns
,
2985 vec
<dt_operand
*> generic_fns
,
2986 vec
<dt_operand
*> preds
,
2987 vec
<dt_node
*> others
)
2990 char *kid_opname
= buf
;
2992 unsigned exprs_len
= gimple_exprs
.length ();
2993 unsigned gexprs_len
= generic_exprs
.length ();
2994 unsigned fns_len
= fns
.length ();
2995 unsigned gfns_len
= generic_fns
.length ();
2997 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3000 gimple_exprs
[0]->get_name (kid_opname
);
3002 fns
[0]->get_name (kid_opname
);
3004 generic_fns
[0]->get_name (kid_opname
);
3006 generic_exprs
[0]->get_name (kid_opname
);
3008 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3009 fprintf_indent (f
, indent
, " {\n");
3013 if (exprs_len
|| fns_len
)
3016 fprintf_indent (f
, indent
,
3017 "case SSA_NAME:\n");
3018 fprintf_indent (f
, indent
,
3019 " if (gimple *_d%d = get_def (valueize, %s))\n",
3021 fprintf_indent (f
, indent
,
3026 fprintf_indent (f
, indent
,
3027 "if (gassign *_a%d = dyn_cast <gassign *> (_d%d))\n",
3029 fprintf_indent (f
, indent
,
3030 " switch (gimple_assign_rhs_code (_a%d))\n",
3033 fprintf_indent (f
, indent
, "{\n");
3034 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3036 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3037 id_base
*op
= e
->operation
;
3038 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3039 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3041 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3042 fprintf_indent (f
, indent
, " {\n");
3043 gimple_exprs
[i
]->gen (f
, indent
+ 4, true, depth
);
3044 fprintf_indent (f
, indent
, " break;\n");
3045 fprintf_indent (f
, indent
, " }\n");
3047 fprintf_indent (f
, indent
, "default:;\n");
3048 fprintf_indent (f
, indent
, "}\n");
3054 fprintf_indent (f
, indent
,
3055 "%sif (gcall *_c%d = dyn_cast <gcall *> (_d%d))\n",
3056 exprs_len
? "else " : "", depth
, depth
);
3057 fprintf_indent (f
, indent
,
3058 " switch (gimple_call_combined_fn (_c%d))\n",
3062 fprintf_indent (f
, indent
, "{\n");
3063 for (unsigned i
= 0; i
< fns_len
; ++i
)
3065 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3066 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3067 fprintf_indent (f
, indent
, " {\n");
3068 fns
[i
]->gen (f
, indent
+ 4, true, depth
);
3069 fprintf_indent (f
, indent
, " break;\n");
3070 fprintf_indent (f
, indent
, " }\n");
3073 fprintf_indent (f
, indent
, "default:;\n");
3074 fprintf_indent (f
, indent
, "}\n");
3080 fprintf_indent (f
, indent
, " }\n");
3081 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3082 here rather than in the next loop. */
3083 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3085 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3086 id_base
*op
= e
->operation
;
3087 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3089 fprintf_indent (f
, indent
+ 4, "{\n");
3090 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
, depth
);
3091 fprintf_indent (f
, indent
+ 4, "}\n");
3095 fprintf_indent (f
, indent
, " break;\n");
3098 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3100 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3101 id_base
*op
= e
->operation
;
3102 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3103 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3104 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3105 /* Already handled above. */
3108 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3109 fprintf_indent (f
, indent
, " {\n");
3110 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
, depth
);
3111 fprintf_indent (f
, indent
, " break;\n");
3112 fprintf_indent (f
, indent
, " }\n");
3117 fprintf_indent (f
, indent
,
3118 "case CALL_EXPR:\n");
3119 fprintf_indent (f
, indent
,
3120 " switch (get_call_combined_fn (%s))\n",
3122 fprintf_indent (f
, indent
,
3126 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3128 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3129 gcc_assert (e
->operation
->kind
== id_base::FN
);
3131 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3132 fprintf_indent (f
, indent
, " {\n");
3133 generic_fns
[j
]->gen (f
, indent
+ 4, false, depth
);
3134 fprintf_indent (f
, indent
, " break;\n");
3135 fprintf_indent (f
, indent
, " }\n");
3137 fprintf_indent (f
, indent
, "default:;\n");
3140 fprintf_indent (f
, indent
, " }\n");
3141 fprintf_indent (f
, indent
, " break;\n");
3144 /* Close switch (TREE_CODE ()). */
3145 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3148 fprintf_indent (f
, indent
, " default:;\n");
3149 fprintf_indent (f
, indent
, " }\n");
3152 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3154 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3155 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3156 preds
[i
]->get_name (kid_opname
);
3157 fprintf_indent (f
, indent
, "{\n");
3159 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3160 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3161 gimple
? "gimple" : "tree",
3162 p
->id
, kid_opname
, kid_opname
,
3163 gimple
? ", valueize" : "");
3164 fprintf_indent (f
, indent
, " {\n");
3165 for (int j
= 0; j
< p
->nargs
; ++j
)
3167 char child_opname
[20];
3168 preds
[i
]->gen_opname (child_opname
, j
);
3169 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3170 child_opname
, kid_opname
, j
);
3172 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
, depth
);
3175 fprintf_indent (f
, indent
, "}\n");
3178 for (unsigned i
= 0; i
< others
.length (); ++i
)
3179 others
[i
]->gen (f
, indent
, gimple
, depth
);
3182 /* Generate matching code for the decision tree operand. */
3185 dt_operand::gen (FILE *f
, int indent
, bool gimple
, int depth
)
3190 unsigned n_braces
= 0;
3192 if (type
== DT_OPERAND
)
3195 case operand::OP_PREDICATE
:
3196 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3199 case operand::OP_EXPR
:
3201 n_braces
= gen_gimple_expr (f
, indent
, depth
);
3203 n_braces
= gen_generic_expr (f
, indent
, opname
);
3209 else if (type
== DT_TRUE
)
3211 else if (type
== DT_MATCH
)
3212 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3216 indent
+= 4 * n_braces
;
3217 gen_kids (f
, indent
, gimple
, depth
);
3219 for (unsigned i
= 0; i
< n_braces
; ++i
)
3224 fprintf_indent (f
, indent
, " }\n");
3229 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3230 step of a '(simplify ...)' or '(match ...)'. This handles everything
3231 that is not part of the decision tree (simplify->match).
3232 Main recursive worker. */
3235 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3239 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3241 fprintf_indent (f
, indent
, "{\n");
3243 output_line_directive (f
, w
->location
);
3244 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3245 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3247 fprintf_indent (f
, indent
, "}\n");
3250 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3252 output_line_directive (f
, ife
->location
);
3253 fprintf_indent (f
, indent
, "if (");
3254 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3256 fprintf_indent (f
, indent
+ 2, "{\n");
3258 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3260 fprintf_indent (f
, indent
+ 2, "}\n");
3263 fprintf_indent (f
, indent
, "else\n");
3264 fprintf_indent (f
, indent
+ 2, "{\n");
3266 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3268 fprintf_indent (f
, indent
+ 2, "}\n");
3274 /* Analyze captures and perform early-outs on the incoming arguments
3275 that cover cases we cannot handle. */
3276 capture_info
cinfo (s
, result
, gimple
);
3277 if (s
->kind
== simplify::SIMPLIFY
)
3281 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3282 if (cinfo
.force_no_side_effects
& (1 << i
))
3284 fprintf_indent (f
, indent
,
3285 "if (TREE_SIDE_EFFECTS (_p%d)) return NULL_TREE;\n",
3288 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3289 "forcing toplevel operand to have no "
3292 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3293 if (cinfo
.info
[i
].cse_p
)
3295 else if (cinfo
.info
[i
].force_no_side_effects_p
3296 && (cinfo
.info
[i
].toplevel_msk
3297 & cinfo
.force_no_side_effects
) == 0)
3299 fprintf_indent (f
, indent
,
3300 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3301 "return NULL_TREE;\n", i
);
3303 warning_at (cinfo
.info
[i
].c
->location
,
3304 "forcing captured operand to have no "
3307 else if ((cinfo
.info
[i
].toplevel_msk
3308 & cinfo
.force_no_side_effects
) != 0)
3309 /* Mark capture as having no side-effects if we had to verify
3310 that via forced toplevel operand checks. */
3311 cinfo
.info
[i
].force_no_side_effects_p
= true;
3315 /* Force single-use restriction by only allowing simple
3316 results via setting seq to NULL. */
3317 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3318 bool first_p
= true;
3319 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3320 if (cinfo
.info
[i
].force_single_use
)
3324 fprintf_indent (f
, indent
, "if (lseq\n");
3325 fprintf_indent (f
, indent
, " && (");
3331 fprintf_indent (f
, indent
, " || ");
3333 fprintf (f
, "!single_use (captures[%d])", i
);
3337 fprintf (f
, "))\n");
3338 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3343 if (s
->kind
== simplify::SIMPLIFY
)
3344 fprintf_indent (f
, indent
, "if (__builtin_expect (!dbg_cnt (match), 0)) return %s;\n",
3345 gimple
? "false" : "NULL_TREE");
3347 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3348 "fprintf (dump_file, \"%s ",
3349 s
->kind
== simplify::SIMPLIFY
3350 ? "Applying pattern" : "Matching expression");
3351 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3352 output_line_directive (f
,
3353 result
? result
->location
: s
->match
->location
, true,
3355 fprintf (f
, ", __FILE__, __LINE__);\n");
3359 /* If there is no result then this is a predicate implementation. */
3360 fprintf_indent (f
, indent
, "return true;\n");
3364 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3365 in outermost position). */
3366 if (result
->type
== operand::OP_EXPR
3367 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3368 result
= as_a
<expr
*> (result
)->ops
[0];
3369 if (result
->type
== operand::OP_EXPR
)
3371 expr
*e
= as_a
<expr
*> (result
);
3372 id_base
*opr
= e
->operation
;
3373 bool is_predicate
= false;
3374 /* When we delay operator substituting during lowering of fors we
3375 make sure that for code-gen purposes the effects of each substitute
3376 are the same. Thus just look at that. */
3377 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3378 opr
= uid
->substitutes
[0];
3379 else if (is_a
<predicate_id
*> (opr
))
3380 is_predicate
= true;
3382 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3383 *e
->operation
== CONVERT_EXPR
3384 ? "NOP_EXPR" : e
->operation
->id
,
3386 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3390 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3392 snprintf (dest
, sizeof (dest
), "res_op->ops[%d]", j
);
3394 = get_operand_type (opr
, j
,
3395 "type", e
->expr_type
,
3397 : "TREE_TYPE (res_op->ops[0])");
3398 /* We need to expand GENERIC conditions we captured from
3399 COND_EXPRs and we need to unshare them when substituting
3401 int cond_handling
= 0;
3403 cond_handling
= ((*opr
== COND_EXPR
3404 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3405 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3406 &cinfo
, indexes
, cond_handling
);
3409 /* Re-fold the toplevel result. It's basically an embedded
3410 gimple_build w/o actually building the stmt. */
3412 fprintf_indent (f
, indent
,
3413 "res_op->resimplify (lseq, valueize);\n");
3415 else if (result
->type
== operand::OP_CAPTURE
3416 || result
->type
== operand::OP_C_EXPR
)
3418 fprintf_indent (f
, indent
, "tree tem;\n");
3419 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3421 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3422 if (is_a
<capture
*> (result
)
3423 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3425 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3426 with substituting a capture of that. */
3427 fprintf_indent (f
, indent
,
3428 "if (COMPARISON_CLASS_P (tem))\n");
3429 fprintf_indent (f
, indent
,
3431 fprintf_indent (f
, indent
,
3432 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3433 fprintf_indent (f
, indent
,
3434 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3435 fprintf_indent (f
, indent
,
3441 fprintf_indent (f
, indent
, "return true;\n");
3445 bool is_predicate
= false;
3446 if (result
->type
== operand::OP_EXPR
)
3448 expr
*e
= as_a
<expr
*> (result
);
3449 id_base
*opr
= e
->operation
;
3450 /* When we delay operator substituting during lowering of fors we
3451 make sure that for code-gen purposes the effects of each substitute
3452 are the same. Thus just look at that. */
3453 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3454 opr
= uid
->substitutes
[0];
3455 else if (is_a
<predicate_id
*> (opr
))
3456 is_predicate
= true;
3457 /* Search for captures used multiple times in the result expression
3458 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3459 original expression. */
3461 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3463 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3464 || cinfo
.info
[i
].cse_p
)
3466 if (cinfo
.info
[i
].result_use_count
3467 > cinfo
.info
[i
].match_use_count
)
3468 fprintf_indent (f
, indent
,
3469 "if (! tree_invariant_p (captures[%d])) "
3470 "return NULL_TREE;\n", i
);
3472 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3476 snprintf (dest
, sizeof (dest
), "res_ops[%d]", j
);
3479 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3480 snprintf (dest
, sizeof (dest
), "res_op%d", j
);
3483 = get_operand_type (opr
, j
,
3484 "type", e
->expr_type
,
3486 ? NULL
: "TREE_TYPE (res_op0)");
3487 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3491 fprintf_indent (f
, indent
, "return true;\n");
3494 fprintf_indent (f
, indent
, "tree _r;\n");
3495 /* Re-fold the toplevel result. Use non_lvalue to
3496 build NON_LVALUE_EXPRs so they get properly
3497 ignored when in GIMPLE form. */
3498 if (*opr
== NON_LVALUE_EXPR
)
3499 fprintf_indent (f
, indent
,
3500 "_r = non_lvalue_loc (loc, res_op0);\n");
3503 if (is_a
<operator_id
*> (opr
))
3504 fprintf_indent (f
, indent
,
3505 "_r = fold_build%d_loc (loc, %s, type",
3507 *e
->operation
== CONVERT_EXPR
3508 ? "NOP_EXPR" : e
->operation
->id
);
3510 fprintf_indent (f
, indent
,
3511 "_r = maybe_build_call_expr_loc (loc, "
3512 "%s, type, %d", e
->operation
->id
,
3514 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3515 fprintf (f
, ", res_op%d", j
);
3516 fprintf (f
, ");\n");
3517 if (!is_a
<operator_id
*> (opr
))
3519 fprintf_indent (f
, indent
, "if (!_r)\n");
3520 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3525 else if (result
->type
== operand::OP_CAPTURE
3526 || result
->type
== operand::OP_C_EXPR
)
3529 fprintf_indent (f
, indent
, "tree _r;\n");
3530 result
->gen_transform (f
, indent
, "_r", false, 1, "type",
3537 /* Search for captures not used in the result expression and dependent
3538 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3539 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3541 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3543 if (!cinfo
.info
[i
].force_no_side_effects_p
3544 && !cinfo
.info
[i
].expr_p
3545 && cinfo
.info
[i
].result_use_count
== 0)
3547 fprintf_indent (f
, indent
,
3548 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3550 fprintf_indent (f
, indent
+ 2,
3551 "_r = build2_loc (loc, COMPOUND_EXPR, type, "
3552 "fold_ignored_result (captures[%d]), _r);\n",
3556 fprintf_indent (f
, indent
, "return _r;\n");
3561 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3562 step of a '(simplify ...)' or '(match ...)'. This handles everything
3563 that is not part of the decision tree (simplify->match). */
3566 dt_simplify::gen (FILE *f
, int indent
, bool gimple
, int depth ATTRIBUTE_UNUSED
)
3568 fprintf_indent (f
, indent
, "{\n");
3570 output_line_directive (f
,
3571 s
->result
? s
->result
->location
: s
->match
->location
);
3572 if (s
->capture_max
>= 0)
3575 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3576 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3578 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3582 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3584 fprintf (f
, " };\n");
3587 /* If we have a split-out function for the actual transform, call it. */
3588 if (info
&& info
->fname
)
3592 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3593 "valueize, type, captures", info
->fname
);
3594 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3595 if (s
->for_subst_vec
[i
].first
->used
)
3596 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3597 fprintf (f
, "))\n");
3598 fprintf_indent (f
, indent
, " return true;\n");
3602 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3604 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3605 fprintf (f
, ", _p%d", i
);
3606 fprintf (f
, ", captures");
3607 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3609 if (s
->for_subst_vec
[i
].first
->used
)
3610 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3612 fprintf (f
, ");\n");
3613 fprintf_indent (f
, indent
, "if (res) return res;\n");
3618 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3620 if (! s
->for_subst_vec
[i
].first
->used
)
3622 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3623 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3624 s
->for_subst_vec
[i
].first
->id
,
3625 s
->for_subst_vec
[i
].second
->id
);
3626 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3627 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3628 s
->for_subst_vec
[i
].first
->id
,
3629 s
->for_subst_vec
[i
].second
->id
);
3633 gen_1 (f
, indent
, gimple
, s
->result
);
3637 fprintf_indent (f
, indent
, "}\n");
3641 /* Hash function for finding equivalent transforms. */
3644 sinfo_hashmap_traits::hash (const key_type
&v
)
3646 /* Only bother to compare those originating from the same source pattern. */
3647 return v
->s
->result
->location
;
3650 /* Compare function for finding equivalent transforms. */
3653 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3655 if (o1
->type
!= o2
->type
)
3660 case operand::OP_IF
:
3662 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3663 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3664 /* ??? Properly compare c-exprs. */
3665 if (if1
->cond
!= if2
->cond
)
3667 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3669 if (if1
->falseexpr
!= if2
->falseexpr
3671 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3675 case operand::OP_WITH
:
3677 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3678 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3679 if (with1
->with
!= with2
->with
)
3681 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3686 /* We've hit a result. Time to compare capture-infos - this is required
3687 in addition to the conservative pointer-equivalency of the result IL. */
3688 capture_info
cinfo1 (s1
, o1
, true);
3689 capture_info
cinfo2 (s2
, o2
, true);
3691 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3692 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3695 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3697 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3698 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3699 || (cinfo1
.info
[i
].force_no_side_effects_p
3700 != cinfo2
.info
[i
].force_no_side_effects_p
)
3701 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3702 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3703 /* toplevel_msk is an optimization */
3704 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3705 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3706 /* the pointer back to the capture is for diagnostics only */)
3710 /* ??? Deep-compare the actual result. */
3715 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3716 const key_type
&candidate
)
3718 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3722 /* Main entry to generate code for matching GIMPLE IL off the decision
3726 decision_tree::gen (FILE *f
, bool gimple
)
3732 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3733 "a total number of %u nodes\n",
3734 gimple
? "GIMPLE" : "GENERIC",
3735 root
->num_leafs
, root
->max_level
, root
->total_size
);
3737 /* First split out the transform part of equal leafs. */
3740 for (sinfo_map_t::iterator iter
= si
.begin ();
3741 iter
!= si
.end (); ++iter
)
3743 sinfo
*s
= (*iter
).second
;
3744 /* Do not split out single uses. */
3751 fprintf (stderr
, "found %u uses of", s
->cnt
);
3752 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3755 /* Generate a split out function with the leaf transform code. */
3756 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3759 fprintf (f
, "\nstatic bool\n"
3760 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3761 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3762 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3767 fprintf (f
, "\nstatic tree\n"
3768 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3769 (*iter
).second
->fname
);
3770 for (unsigned i
= 0;
3771 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3772 fprintf (f
, " tree ARG_UNUSED (_p%d),", i
);
3773 fprintf (f
, " tree *captures\n");
3775 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3777 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3779 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3780 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3781 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3782 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3783 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3784 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3787 fprintf (f
, ")\n{\n");
3788 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3790 fprintf (f
, " return false;\n");
3792 fprintf (f
, " return NULL_TREE;\n");
3795 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3797 for (unsigned n
= 1; n
<= 5; ++n
)
3799 /* First generate split-out functions. */
3800 for (unsigned j
= 0; j
< root
->kids
.length (); j
++)
3802 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[j
]);
3803 expr
*e
= static_cast<expr
*>(dop
->op
);
3804 if (e
->ops
.length () != n
3805 /* Builtin simplifications are somewhat premature on
3806 GENERIC. The following drops patterns with outermost
3807 calls. It's easy to emit overloads for function code
3808 though if necessary. */
3810 && e
->operation
->kind
!= id_base::CODE
))
3814 fprintf (f
, "\nstatic bool\n"
3815 "gimple_simplify_%s (gimple_match_op *res_op,"
3816 " gimple_seq *seq,\n"
3817 " tree (*valueize)(tree) "
3818 "ATTRIBUTE_UNUSED,\n"
3819 " code_helper ARG_UNUSED (code), tree "
3820 "ARG_UNUSED (type)\n",
3823 fprintf (f
, "\nstatic tree\n"
3824 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3825 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3827 for (unsigned i
= 0; i
< n
; ++i
)
3828 fprintf (f
, ", tree _p%d", i
);
3831 dop
->gen_kids (f
, 2, gimple
, 0);
3833 fprintf (f
, " return false;\n");
3835 fprintf (f
, " return NULL_TREE;\n");
3839 /* Then generate the main entry with the outermost switch and
3840 tail-calls to the split-out functions. */
3842 fprintf (f
, "\nstatic bool\n"
3843 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3844 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3845 " code_helper code, const tree type");
3847 fprintf (f
, "\ntree\n"
3848 "generic_simplify (location_t loc, enum tree_code code, "
3849 "const tree type ATTRIBUTE_UNUSED");
3850 for (unsigned i
= 0; i
< n
; ++i
)
3851 fprintf (f
, ", tree _p%d", i
);
3856 fprintf (f
, " switch (code.get_rep())\n"
3859 fprintf (f
, " switch (code)\n"
3861 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3863 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3864 expr
*e
= static_cast<expr
*>(dop
->op
);
3865 if (e
->ops
.length () != n
3866 /* Builtin simplifications are somewhat premature on
3867 GENERIC. The following drops patterns with outermost
3868 calls. It's easy to emit overloads for function code
3869 though if necessary. */
3871 && e
->operation
->kind
!= id_base::CODE
))
3874 if (*e
->operation
== CONVERT_EXPR
3875 || *e
->operation
== NOP_EXPR
)
3876 fprintf (f
, " CASE_CONVERT:\n");
3878 fprintf (f
, " case %s%s:\n",
3879 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3882 fprintf (f
, " return gimple_simplify_%s (res_op, "
3883 "seq, valueize, code, type", e
->operation
->id
);
3885 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3887 for (unsigned j
= 0; j
< n
; ++j
)
3888 fprintf (f
, ", _p%d", j
);
3889 fprintf (f
, ");\n");
3891 fprintf (f
, " default:;\n"
3895 fprintf (f
, " return false;\n");
3897 fprintf (f
, " return NULL_TREE;\n");
3902 /* Output code to implement the predicate P from the decision tree DT. */
3905 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3907 fprintf (f
, "\nbool\n"
3908 "%s%s (tree t%s%s)\n"
3909 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3910 p
->nargs
> 0 ? ", tree *res_ops" : "",
3911 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3912 /* Conveniently make 'type' available. */
3913 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3916 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3917 dt
.root
->gen_kids (f
, 2, gimple
, 0);
3919 fprintf_indent (f
, 2, "return false;\n"
3923 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3926 write_header (FILE *f
, const char *head
)
3928 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3929 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3931 /* Include the header instead of writing it awkwardly quoted here. */
3932 fprintf (f
, "\n#include \"%s\"\n", head
);
3942 parser (cpp_reader
*);
3945 const cpp_token
*next ();
3946 const cpp_token
*peek (unsigned = 1);
3947 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3948 const cpp_token
*expect (enum cpp_ttype
);
3949 const cpp_token
*eat_token (enum cpp_ttype
);
3950 const char *get_string ();
3951 const char *get_ident ();
3952 const cpp_token
*eat_ident (const char *);
3953 const char *get_number ();
3955 unsigned get_internal_capture_id ();
3957 id_base
*parse_operation ();
3958 operand
*parse_capture (operand
*, bool);
3959 operand
*parse_expr ();
3960 c_expr
*parse_c_expr (cpp_ttype
);
3961 operand
*parse_op ();
3963 void record_operlist (location_t
, user_id
*);
3965 void parse_pattern ();
3966 operand
*parse_result (operand
*, predicate_id
*);
3967 void push_simplify (simplify::simplify_kind
,
3968 vec
<simplify
*>&, operand
*, operand
*);
3969 void parse_simplify (simplify::simplify_kind
,
3970 vec
<simplify
*>&, predicate_id
*, operand
*);
3971 void parse_for (location_t
);
3972 void parse_if (location_t
);
3973 void parse_predicates (location_t
);
3974 void parse_operator_list (location_t
);
3976 void finish_match_operand (operand
*);
3979 vec
<c_expr
*> active_ifs
;
3980 vec
<vec
<user_id
*> > active_fors
;
3981 hash_set
<user_id
*> *oper_lists_set
;
3982 vec
<user_id
*> oper_lists
;
3984 cid_map_t
*capture_ids
;
3988 vec
<simplify
*> simplifiers
;
3989 vec
<predicate_id
*> user_predicates
;
3990 bool parsing_match_operand
;
3993 /* Lexing helpers. */
3995 /* Read the next non-whitespace token from R. */
4000 const cpp_token
*token
;
4003 token
= cpp_get_token (r
);
4005 while (token
->type
== CPP_PADDING
);
4009 /* Peek at the next non-whitespace token from R. */
4012 parser::peek (unsigned num
)
4014 const cpp_token
*token
;
4018 token
= cpp_peek_token (r
, i
++);
4020 while (token
->type
== CPP_PADDING
4022 /* If we peek at EOF this is a fatal error as it leaves the
4023 cpp_reader in unusable state. Assume we really wanted a
4024 token and thus this EOF is unexpected. */
4025 if (token
->type
== CPP_EOF
)
4026 fatal_at (token
, "unexpected end of file");
4030 /* Peek at the next identifier token (or return NULL if the next
4031 token is not an identifier or equal to ID if supplied). */
4034 parser::peek_ident (const char *id
, unsigned num
)
4036 const cpp_token
*token
= peek (num
);
4037 if (token
->type
!= CPP_NAME
)
4043 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4044 if (strcmp (id
, t
) == 0)
4050 /* Read the next token from R and assert it is of type TK. */
4053 parser::expect (enum cpp_ttype tk
)
4055 const cpp_token
*token
= next ();
4056 if (token
->type
!= tk
)
4057 fatal_at (token
, "expected %s, got %s",
4058 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4063 /* Consume the next token from R and assert it is of type TK. */
4066 parser::eat_token (enum cpp_ttype tk
)
4071 /* Read the next token from R and assert it is of type CPP_STRING and
4072 return its value. */
4075 parser::get_string ()
4077 const cpp_token
*token
= expect (CPP_STRING
);
4078 return (const char *)token
->val
.str
.text
;
4081 /* Read the next token from R and assert it is of type CPP_NAME and
4082 return its value. */
4085 parser::get_ident ()
4087 const cpp_token
*token
= expect (CPP_NAME
);
4088 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4091 /* Eat an identifier token with value S from R. */
4094 parser::eat_ident (const char *s
)
4096 const cpp_token
*token
= peek ();
4097 const char *t
= get_ident ();
4098 if (strcmp (s
, t
) != 0)
4099 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4103 /* Read the next token from R and assert it is of type CPP_NUMBER and
4104 return its value. */
4107 parser::get_number ()
4109 const cpp_token
*token
= expect (CPP_NUMBER
);
4110 return (const char *)token
->val
.str
.text
;
4113 /* Return a capture ID that can be used internally. */
4116 parser::get_internal_capture_id ()
4118 unsigned newid
= capture_ids
->elements ();
4119 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4122 snprintf (id
, sizeof (id
), "__%u", newid
);
4123 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4125 fatal ("reserved capture id '%s' already used", id
);
4129 /* Record an operator-list use for transparent for handling. */
4132 parser::record_operlist (location_t loc
, user_id
*p
)
4134 if (!oper_lists_set
->add (p
))
4136 if (!oper_lists
.is_empty ()
4137 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4138 fatal_at (loc
, "User-defined operator list does not have the "
4139 "same number of entries as others used in the pattern");
4140 oper_lists
.safe_push (p
);
4144 /* Parse the operator ID, special-casing convert?, convert1? and
4148 parser::parse_operation ()
4150 const cpp_token
*id_tok
= peek ();
4151 const char *id
= get_ident ();
4152 const cpp_token
*token
= peek ();
4153 if (strcmp (id
, "convert0") == 0)
4154 fatal_at (id_tok
, "use 'convert?' here");
4155 else if (strcmp (id
, "view_convert0") == 0)
4156 fatal_at (id_tok
, "use 'view_convert?' here");
4157 if (token
->type
== CPP_QUERY
4158 && !(token
->flags
& PREV_WHITE
))
4160 if (strcmp (id
, "convert") == 0)
4162 else if (strcmp (id
, "convert1") == 0)
4164 else if (strcmp (id
, "convert2") == 0)
4166 else if (strcmp (id
, "view_convert") == 0)
4167 id
= "view_convert0";
4168 else if (strcmp (id
, "view_convert1") == 0)
4170 else if (strcmp (id
, "view_convert2") == 0)
4173 fatal_at (id_tok
, "non-convert operator conditionalized");
4175 if (!parsing_match_operand
)
4176 fatal_at (id_tok
, "conditional convert can only be used in "
4177 "match expression");
4178 eat_token (CPP_QUERY
);
4180 else if (strcmp (id
, "convert1") == 0
4181 || strcmp (id
, "convert2") == 0
4182 || strcmp (id
, "view_convert1") == 0
4183 || strcmp (id
, "view_convert2") == 0)
4184 fatal_at (id_tok
, "expected '?' after conditional operator");
4185 id_base
*op
= get_operator (id
);
4187 fatal_at (id_tok
, "unknown operator %s", id
);
4189 user_id
*p
= dyn_cast
<user_id
*> (op
);
4190 if (p
&& p
->is_oper_list
)
4192 if (active_fors
.length() == 0)
4193 record_operlist (id_tok
->src_loc
, p
);
4195 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4201 capture = '@'<number> */
4204 parser::parse_capture (operand
*op
, bool require_existing
)
4206 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4207 const cpp_token
*token
= peek ();
4208 const char *id
= NULL
;
4209 bool value_match
= false;
4210 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4211 if (token
->type
== CPP_ATSIGN
4212 && ! (token
->flags
& PREV_WHITE
)
4213 && parsing_match_operand
)
4215 eat_token (CPP_ATSIGN
);
4219 if (token
->type
== CPP_NUMBER
)
4221 else if (token
->type
== CPP_NAME
)
4224 fatal_at (token
, "expected number or identifier");
4225 unsigned next_id
= capture_ids
->elements ();
4227 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4230 if (require_existing
)
4231 fatal_at (src_loc
, "unknown capture id");
4234 return new capture (src_loc
, num
, op
, value_match
);
4237 /* Parse an expression
4238 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4241 parser::parse_expr ()
4243 const cpp_token
*token
= peek ();
4244 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4247 bool is_commutative
= false;
4248 bool force_capture
= false;
4249 const char *expr_type
= NULL
;
4251 if (token
->type
== CPP_COLON
4252 && !(token
->flags
& PREV_WHITE
))
4254 eat_token (CPP_COLON
);
4256 if (token
->type
== CPP_NAME
4257 && !(token
->flags
& PREV_WHITE
))
4259 const char *s
= get_ident ();
4260 if (!parsing_match_operand
)
4270 = dyn_cast
<operator_id
*> (e
->operation
))
4272 if (!commutative_tree_code (o
->code
)
4273 && !comparison_code_p (o
->code
))
4274 fatal_at (token
, "operation is not commutative");
4276 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4277 for (unsigned i
= 0;
4278 i
< p
->substitutes
.length (); ++i
)
4281 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4283 if (!commutative_tree_code (q
->code
)
4284 && !comparison_code_p (q
->code
))
4285 fatal_at (token
, "operation %s is not "
4286 "commutative", q
->id
);
4289 is_commutative
= true;
4291 else if (*sp
== 'C')
4292 is_commutative
= true;
4293 else if (*sp
== 's')
4295 e
->force_single_use
= true;
4296 force_capture
= true;
4299 fatal_at (token
, "flag %c not recognized", *sp
);
4306 fatal_at (token
, "expected flag or type specifying identifier");
4309 if (token
->type
== CPP_ATSIGN
4310 && !(token
->flags
& PREV_WHITE
))
4311 op
= parse_capture (e
, false);
4312 else if (force_capture
)
4314 unsigned num
= get_internal_capture_id ();
4315 op
= new capture (token
->src_loc
, num
, e
, false);
4322 if (token
->type
== CPP_CLOSE_PAREN
)
4324 if (e
->operation
->nargs
!= -1
4325 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4326 fatal_at (token
, "'%s' expects %u operands, not %u",
4327 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4330 if (e
->ops
.length () == 2
4331 || commutative_op (e
->operation
) >= 0)
4332 e
->is_commutative
= true;
4334 fatal_at (token
, "only binary operators or functions with "
4335 "two arguments can be marked commutative, "
4336 "unless the operation is known to be inherently "
4339 e
->expr_type
= expr_type
;
4342 else if (!(token
->flags
& PREV_WHITE
))
4343 fatal_at (token
, "expected expression operand");
4345 e
->append_op (parse_op ());
4350 /* Lex native C code delimited by START recording the preprocessing tokens
4351 for later processing.
4352 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4355 parser::parse_c_expr (cpp_ttype start
)
4357 const cpp_token
*token
;
4360 vec
<cpp_token
> code
= vNULL
;
4361 unsigned nr_stmts
= 0;
4362 location_t loc
= eat_token (start
)->src_loc
;
4363 if (start
== CPP_OPEN_PAREN
)
4364 end
= CPP_CLOSE_PAREN
;
4365 else if (start
== CPP_OPEN_BRACE
)
4366 end
= CPP_CLOSE_BRACE
;
4374 /* Count brace pairs to find the end of the expr to match. */
4375 if (token
->type
== start
)
4377 else if (token
->type
== end
4380 else if (token
->type
== CPP_EOF
)
4381 fatal_at (token
, "unexpected end of file");
4383 /* This is a lame way of counting the number of statements. */
4384 if (token
->type
== CPP_SEMICOLON
)
4387 /* If this is possibly a user-defined identifier mark it used. */
4388 if (token
->type
== CPP_NAME
)
4390 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4391 (token
->val
.node
.node
)->ident
.str
);
4393 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4394 record_operlist (token
->src_loc
, p
);
4397 /* Record the token. */
4398 code
.safe_push (*token
);
4401 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4404 /* Parse an operand which is either an expression, a predicate or
4405 a standalone capture.
4406 op = predicate | expr | c_expr | capture */
4411 const cpp_token
*token
= peek ();
4412 class operand
*op
= NULL
;
4413 if (token
->type
== CPP_OPEN_PAREN
)
4415 eat_token (CPP_OPEN_PAREN
);
4417 eat_token (CPP_CLOSE_PAREN
);
4419 else if (token
->type
== CPP_OPEN_BRACE
)
4421 op
= parse_c_expr (CPP_OPEN_BRACE
);
4425 /* Remaining ops are either empty or predicates */
4426 if (token
->type
== CPP_NAME
)
4428 const char *id
= get_ident ();
4429 id_base
*opr
= get_operator (id
);
4431 fatal_at (token
, "expected predicate name");
4432 if (operator_id
*code1
= dyn_cast
<operator_id
*> (opr
))
4434 if (code1
->nargs
!= 0)
4435 fatal_at (token
, "using an operator with operands as predicate");
4436 /* Parse the zero-operand operator "predicates" as
4438 op
= new expr (opr
, token
->src_loc
);
4440 else if (user_id
*code2
= dyn_cast
<user_id
*> (opr
))
4442 if (code2
->nargs
!= 0)
4443 fatal_at (token
, "using an operator with operands as predicate");
4444 /* Parse the zero-operand operator "predicates" as
4446 op
= new expr (opr
, token
->src_loc
);
4448 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4449 op
= new predicate (p
, token
->src_loc
);
4451 fatal_at (token
, "using an unsupported operator as predicate");
4452 if (!parsing_match_operand
)
4453 fatal_at (token
, "predicates are only allowed in match expression");
4455 if (token
->flags
& PREV_WHITE
)
4458 else if (token
->type
!= CPP_COLON
4459 && token
->type
!= CPP_ATSIGN
)
4460 fatal_at (token
, "expected expression or predicate");
4461 /* optionally followed by a capture and a predicate. */
4462 if (token
->type
== CPP_COLON
)
4463 fatal_at (token
, "not implemented: predicate on leaf operand");
4464 if (token
->type
== CPP_ATSIGN
)
4465 op
= parse_capture (op
, !parsing_match_operand
);
4471 /* Create a new simplify from the current parsing state and MATCH,
4472 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4475 parser::push_simplify (simplify::simplify_kind kind
,
4476 vec
<simplify
*>& simplifiers
,
4477 operand
*match
, operand
*result
)
4479 /* Build and push a temporary for operator list uses in expressions. */
4480 if (!oper_lists
.is_empty ())
4481 active_fors
.safe_push (oper_lists
);
4483 simplifiers
.safe_push
4484 (new simplify (kind
, last_id
++, match
, result
,
4485 active_fors
.copy (), capture_ids
));
4487 if (!oper_lists
.is_empty ())
4492 <result-op> = <op> | <if> | <with>
4493 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4494 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4498 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4500 const cpp_token
*token
= peek ();
4501 if (token
->type
!= CPP_OPEN_PAREN
)
4504 eat_token (CPP_OPEN_PAREN
);
4505 if (peek_ident ("if"))
4508 if_expr
*ife
= new if_expr (token
->src_loc
);
4509 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4510 if (peek ()->type
== CPP_OPEN_PAREN
)
4512 ife
->trueexpr
= parse_result (result
, matcher
);
4513 if (peek ()->type
== CPP_OPEN_PAREN
)
4514 ife
->falseexpr
= parse_result (result
, matcher
);
4515 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4516 ife
->falseexpr
= parse_op ();
4518 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4520 ife
->trueexpr
= parse_op ();
4521 if (peek ()->type
== CPP_OPEN_PAREN
)
4522 ife
->falseexpr
= parse_result (result
, matcher
);
4523 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4524 ife
->falseexpr
= parse_op ();
4526 /* If this if is immediately closed then it contains a
4527 manual matcher or is part of a predicate definition. */
4528 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4531 fatal_at (peek (), "manual transform not implemented");
4532 ife
->trueexpr
= result
;
4534 eat_token (CPP_CLOSE_PAREN
);
4537 else if (peek_ident ("with"))
4540 with_expr
*withe
= new with_expr (token
->src_loc
);
4541 /* Parse (with c-expr expr) as (if-with (true) expr). */
4542 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4543 withe
->with
->nr_stmts
= 0;
4544 withe
->subexpr
= parse_result (result
, matcher
);
4545 eat_token (CPP_CLOSE_PAREN
);
4548 else if (peek_ident ("switch"))
4550 token
= eat_ident ("switch");
4551 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4553 if_expr
*ife
= new if_expr (ifloc
);
4555 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4556 if (peek ()->type
== CPP_OPEN_PAREN
)
4557 ife
->trueexpr
= parse_result (result
, matcher
);
4559 ife
->trueexpr
= parse_op ();
4560 eat_token (CPP_CLOSE_PAREN
);
4561 if (peek ()->type
!= CPP_OPEN_PAREN
4562 || !peek_ident ("if", 2))
4563 fatal_at (token
, "switch can be implemented with a single if");
4564 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4566 if (peek ()->type
== CPP_OPEN_PAREN
)
4568 if (peek_ident ("if", 2))
4570 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4572 ife
->falseexpr
= new if_expr (ifloc
);
4573 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4574 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4575 if (peek ()->type
== CPP_OPEN_PAREN
)
4576 ife
->trueexpr
= parse_result (result
, matcher
);
4578 ife
->trueexpr
= parse_op ();
4579 eat_token (CPP_CLOSE_PAREN
);
4583 /* switch default clause */
4584 ife
->falseexpr
= parse_result (result
, matcher
);
4585 eat_token (CPP_CLOSE_PAREN
);
4591 /* switch default clause */
4592 ife
->falseexpr
= parse_op ();
4593 eat_token (CPP_CLOSE_PAREN
);
4597 eat_token (CPP_CLOSE_PAREN
);
4602 operand
*op
= result
;
4605 eat_token (CPP_CLOSE_PAREN
);
4611 simplify = 'simplify' <expr> <result-op>
4613 match = 'match' <ident> <expr> [<result-op>]
4614 and fill SIMPLIFIERS with the results. */
4617 parser::parse_simplify (simplify::simplify_kind kind
,
4618 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4621 /* Reset the capture map. */
4623 capture_ids
= new cid_map_t
;
4624 /* Reset oper_lists and set. */
4625 hash_set
<user_id
*> olist
;
4626 oper_lists_set
= &olist
;
4629 const cpp_token
*loc
= peek ();
4630 parsing_match_operand
= true;
4631 class operand
*match
= parse_op ();
4632 finish_match_operand (match
);
4633 parsing_match_operand
= false;
4634 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4635 fatal_at (loc
, "outermost expression cannot be captured");
4636 if (match
->type
== operand::OP_EXPR
4637 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4638 fatal_at (loc
, "outermost expression cannot be a predicate");
4640 /* Splice active_ifs onto result and continue parsing the
4642 if_expr
*active_if
= NULL
;
4643 for (int i
= active_ifs
.length (); i
> 0; --i
)
4645 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4646 ifc
->cond
= active_ifs
[i
-1];
4647 ifc
->trueexpr
= active_if
;
4650 if_expr
*outermost_if
= active_if
;
4651 while (active_if
&& active_if
->trueexpr
)
4652 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4654 const cpp_token
*token
= peek ();
4656 /* If this if is immediately closed then it is part of a predicate
4657 definition. Push it. */
4658 if (token
->type
== CPP_CLOSE_PAREN
)
4661 fatal_at (token
, "expected transform expression");
4664 active_if
->trueexpr
= result
;
4665 result
= outermost_if
;
4667 push_simplify (kind
, simplifiers
, match
, result
);
4671 operand
*tem
= parse_result (result
, matcher
);
4674 active_if
->trueexpr
= tem
;
4675 result
= outermost_if
;
4680 push_simplify (kind
, simplifiers
, match
, result
);
4683 /* Parsing of the outer control structures. */
4685 /* Parse a for expression
4686 for = '(' 'for' <subst>... <pattern> ')'
4687 subst = <ident> '(' <ident>... ')' */
4690 parser::parse_for (location_t
)
4692 auto_vec
<const cpp_token
*> user_id_tokens
;
4693 vec
<user_id
*> user_ids
= vNULL
;
4694 const cpp_token
*token
;
4695 unsigned min_n_opers
= 0, max_n_opers
= 0;
4700 if (token
->type
!= CPP_NAME
)
4703 /* Insert the user defined operators into the operator hash. */
4704 const char *id
= get_ident ();
4705 if (get_operator (id
, true) != NULL
)
4706 fatal_at (token
, "operator already defined");
4707 user_id
*op
= new user_id (id
);
4708 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4710 user_ids
.safe_push (op
);
4711 user_id_tokens
.safe_push (token
);
4713 eat_token (CPP_OPEN_PAREN
);
4716 while ((token
= peek_ident ()) != 0)
4718 const char *oper
= get_ident ();
4719 id_base
*idb
= get_operator (oper
, true);
4721 fatal_at (token
, "no such operator '%s'", oper
);
4722 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4723 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4724 || *idb
== VIEW_CONVERT2
)
4725 fatal_at (token
, "conditional operators cannot be used inside for");
4729 else if (idb
->nargs
== -1)
4731 else if (idb
->nargs
!= arity
)
4732 fatal_at (token
, "operator '%s' with arity %d does not match "
4733 "others with arity %d", oper
, idb
->nargs
, arity
);
4735 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4738 if (p
->is_oper_list
)
4739 op
->substitutes
.safe_splice (p
->substitutes
);
4741 fatal_at (token
, "iterator cannot be used as operator-list");
4744 op
->substitutes
.safe_push (idb
);
4747 token
= expect (CPP_CLOSE_PAREN
);
4749 unsigned nsubstitutes
= op
->substitutes
.length ();
4750 if (nsubstitutes
== 0)
4751 fatal_at (token
, "A user-defined operator must have at least "
4752 "one substitution");
4753 if (max_n_opers
== 0)
4755 min_n_opers
= nsubstitutes
;
4756 max_n_opers
= nsubstitutes
;
4760 if (nsubstitutes
% min_n_opers
!= 0
4761 && min_n_opers
% nsubstitutes
!= 0)
4762 fatal_at (token
, "All user-defined identifiers must have a "
4763 "multiple number of operator substitutions of the "
4764 "smallest number of substitutions");
4765 if (nsubstitutes
< min_n_opers
)
4766 min_n_opers
= nsubstitutes
;
4767 else if (nsubstitutes
> max_n_opers
)
4768 max_n_opers
= nsubstitutes
;
4772 unsigned n_ids
= user_ids
.length ();
4774 fatal_at (token
, "for requires at least one user-defined identifier");
4777 if (token
->type
== CPP_CLOSE_PAREN
)
4778 fatal_at (token
, "no pattern defined in for");
4780 active_fors
.safe_push (user_ids
);
4784 if (token
->type
== CPP_CLOSE_PAREN
)
4790 /* Remove user-defined operators from the hash again. */
4791 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4793 if (!user_ids
[i
]->used
)
4794 warning_at (user_id_tokens
[i
],
4795 "operator %s defined but not used", user_ids
[i
]->id
);
4796 operators
->remove_elt (user_ids
[i
]);
4800 /* Parse an identifier associated with a list of operators.
4801 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4804 parser::parse_operator_list (location_t
)
4806 const cpp_token
*token
= peek ();
4807 const char *id
= get_ident ();
4809 if (get_operator (id
, true) != 0)
4810 fatal_at (token
, "operator %s already defined", id
);
4812 user_id
*op
= new user_id (id
, true);
4815 while ((token
= peek_ident ()) != 0)
4818 const char *oper
= get_ident ();
4819 id_base
*idb
= get_operator (oper
, true);
4822 fatal_at (token
, "no such operator '%s'", oper
);
4826 else if (idb
->nargs
== -1)
4828 else if (arity
!= idb
->nargs
)
4829 fatal_at (token
, "operator '%s' with arity %d does not match "
4830 "others with arity %d", oper
, idb
->nargs
, arity
);
4832 /* We allow composition of multiple operator lists. */
4833 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4834 op
->substitutes
.safe_splice (p
->substitutes
);
4836 op
->substitutes
.safe_push (idb
);
4839 // Check that there is no junk after id-list
4841 if (token
->type
!= CPP_CLOSE_PAREN
)
4842 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4844 if (op
->substitutes
.length () == 0)
4845 fatal_at (token
, "operator-list cannot be empty");
4848 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4852 /* Parse an outer if expression.
4853 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4856 parser::parse_if (location_t
)
4858 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4860 const cpp_token
*token
= peek ();
4861 if (token
->type
== CPP_CLOSE_PAREN
)
4862 fatal_at (token
, "no pattern defined in if");
4864 active_ifs
.safe_push (ifexpr
);
4868 if (token
->type
== CPP_CLOSE_PAREN
)
4876 /* Parse a list of predefined predicate identifiers.
4877 preds = '(' 'define_predicates' <ident>... ')' */
4880 parser::parse_predicates (location_t
)
4884 const cpp_token
*token
= peek ();
4885 if (token
->type
!= CPP_NAME
)
4888 add_predicate (get_ident ());
4893 /* Parse outer control structures.
4894 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4897 parser::parse_pattern ()
4899 /* All clauses start with '('. */
4900 eat_token (CPP_OPEN_PAREN
);
4901 const cpp_token
*token
= peek ();
4902 const char *id
= get_ident ();
4903 if (strcmp (id
, "simplify") == 0)
4905 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4908 else if (strcmp (id
, "match") == 0)
4910 bool with_args
= false;
4911 location_t e_loc
= peek ()->src_loc
;
4912 if (peek ()->type
== CPP_OPEN_PAREN
)
4914 eat_token (CPP_OPEN_PAREN
);
4917 const char *name
= get_ident ();
4918 id_base
*id1
= get_operator (name
);
4922 p
= add_predicate (name
);
4923 user_predicates
.safe_push (p
);
4925 else if ((p
= dyn_cast
<predicate_id
*> (id1
)))
4928 fatal_at (token
, "cannot add a match to a non-predicate ID");
4929 /* Parse (match <id> <arg>... (match-expr)) here. */
4933 capture_ids
= new cid_map_t
;
4934 e
= new expr (p
, e_loc
);
4935 while (peek ()->type
== CPP_ATSIGN
)
4936 e
->append_op (parse_capture (NULL
, false));
4937 eat_token (CPP_CLOSE_PAREN
);
4940 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4941 || (!e
&& p
->nargs
!= 0)))
4942 fatal_at (token
, "non-matching number of match operands");
4943 p
->nargs
= e
? e
->ops
.length () : 0;
4944 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4947 else if (strcmp (id
, "for") == 0)
4948 parse_for (token
->src_loc
);
4949 else if (strcmp (id
, "if") == 0)
4950 parse_if (token
->src_loc
);
4951 else if (strcmp (id
, "define_predicates") == 0)
4953 if (active_ifs
.length () > 0
4954 || active_fors
.length () > 0)
4955 fatal_at (token
, "define_predicates inside if or for is not supported");
4956 parse_predicates (token
->src_loc
);
4958 else if (strcmp (id
, "define_operator_list") == 0)
4960 if (active_ifs
.length () > 0
4961 || active_fors
.length () > 0)
4962 fatal_at (token
, "operator-list inside if or for is not supported");
4963 parse_operator_list (token
->src_loc
);
4966 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4967 active_ifs
.length () == 0 && active_fors
.length () == 0
4968 ? "'define_predicates', " : "");
4970 eat_token (CPP_CLOSE_PAREN
);
4973 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4977 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4982 if (capture
*c
= dyn_cast
<capture
*> (op
))
4984 cpts
[c
->where
].safe_push (c
);
4985 walk_captures (c
->what
, cpts
);
4987 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4988 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4989 walk_captures (e
->ops
[i
], cpts
);
4992 /* Finish up OP which is a match operand. */
4995 parser::finish_match_operand (operand
*op
)
4997 /* Look for matching captures, diagnose mis-uses of @@ and apply
4998 early lowering and distribution of value_match. */
4999 auto_vec
<vec
<capture
*> > cpts
;
5000 cpts
.safe_grow_cleared (capture_ids
->elements ());
5001 walk_captures (op
, cpts
);
5002 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
5004 capture
*value_match
= NULL
;
5005 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5007 if (cpts
[i
][j
]->value_match
)
5010 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5011 value_match
= cpts
[i
][j
];
5014 if (cpts
[i
].length () == 1 && value_match
)
5015 fatal_at (value_match
->location
, "@@ without a matching capture");
5018 /* Duplicate prevailing capture with the existing ID, create
5019 a fake ID and rewrite all captures to use it. This turns
5020 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5021 value_match
->what
= new capture (value_match
->location
,
5023 value_match
->what
, false);
5024 /* Create a fake ID and rewrite all captures to use it. */
5025 unsigned newid
= get_internal_capture_id ();
5026 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5028 cpts
[i
][j
]->where
= newid
;
5029 cpts
[i
][j
]->value_match
= true;
5036 /* Main entry of the parser. Repeatedly parse outer control structures. */
5038 parser::parser (cpp_reader
*r_
)
5042 active_fors
= vNULL
;
5043 simplifiers
= vNULL
;
5044 oper_lists_set
= NULL
;
5047 user_predicates
= vNULL
;
5048 parsing_match_operand
= false;
5051 const cpp_token
*token
= next ();
5052 while (token
->type
!= CPP_EOF
)
5054 _cpp_backup_tokens (r
, 1);
5061 /* Helper for the linemap code. */
5064 round_alloc_size (size_t s
)
5070 /* The genmatch generator progam. It reads from a pattern description
5071 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5074 main (int argc
, char **argv
)
5078 progname
= "genmatch";
5084 char *input
= argv
[argc
-1];
5085 for (int i
= 1; i
< argc
- 1; ++i
)
5087 if (strcmp (argv
[i
], "--gimple") == 0)
5089 else if (strcmp (argv
[i
], "--generic") == 0)
5091 else if (strcmp (argv
[i
], "-v") == 0)
5093 else if (strcmp (argv
[i
], "-vv") == 0)
5097 fprintf (stderr
, "Usage: genmatch "
5098 "[--gimple] [--generic] [-v[v]] input\n");
5103 line_table
= XCNEW (class line_maps
);
5104 linemap_init (line_table
, 0);
5105 line_table
->reallocator
= xrealloc
;
5106 line_table
->round_alloc_size
= round_alloc_size
;
5108 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5109 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5110 cb
->diagnostic
= diagnostic_cb
;
5112 /* Add the build directory to the #include "" search path. */
5113 cpp_dir
*dir
= XCNEW (cpp_dir
);
5114 dir
->name
= getpwd ();
5116 dir
->name
= ASTRDUP (".");
5117 cpp_set_include_chains (r
, dir
, NULL
, false);
5119 if (!cpp_read_main_file (r
, input
))
5121 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5122 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5124 null_id
= new id_base (id_base::NULL_ID
, "null");
5126 /* Pre-seed operators. */
5127 operators
= new hash_table
<id_base
> (1024);
5128 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5129 add_operator (SYM, # SYM, # TYPE, NARGS);
5130 #define END_OF_BASE_TREE_CODES
5132 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5133 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5134 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5135 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5136 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5137 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5138 #undef END_OF_BASE_TREE_CODES
5141 /* Pre-seed builtin functions.
5142 ??? Cannot use N (name) as that is targetm.emultls.get_address
5143 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5144 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5145 add_function (ENUM, "CFN_" # ENUM);
5146 #include "builtins.def"
5148 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5149 add_function (IFN_##CODE, "CFN_" #CODE);
5150 #include "internal-fn.def"
5156 write_header (stdout
, "gimple-match-head.c");
5158 write_header (stdout
, "generic-match-head.c");
5160 /* Go over all predicates defined with patterns and perform
5161 lowering and code generation. */
5162 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5164 predicate_id
*pred
= p
.user_predicates
[i
];
5165 lower (pred
->matchers
, gimple
);
5168 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5169 print_matches (pred
->matchers
[j
]);
5172 for (unsigned j
= 0; j
< pred
->matchers
.length (); ++j
)
5173 dt
.insert (pred
->matchers
[j
], j
);
5178 write_predicate (stdout
, pred
, dt
, gimple
);
5181 /* Lower the main simplifiers and generate code for them. */
5182 lower (p
.simplifiers
, gimple
);
5185 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5186 print_matches (p
.simplifiers
[i
]);
5189 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5190 dt
.insert (p
.simplifiers
[i
], i
);
5195 dt
.gen (stdout
, gimple
);
5198 cpp_finish (r
, NULL
);