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
*p
= dyn_cast
<operator_id
*> (ne
->operation
))
1027 if (comparison_code_p (p
->code
))
1028 ne
->operation
= swap_tree_comparison (p
);
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)))
1282 expr
*ne
= new expr (e
);
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) {}
1642 void gen_kids (FILE *, int, bool);
1643 void gen_kids_1 (FILE *, int, bool,
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);
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);
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);
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
)
1897 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1898 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1899 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1901 warning_at (s
->match
->location
, "duplicate pattern");
1902 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1903 print_operand (s
->match
, stderr
);
1904 fprintf (stderr
, "\n");
1906 return append_node (n
);
1909 /* Analyze the node and its children. */
1912 dt_node::analyze (sinfo_map_t
&map
)
1918 if (type
== DT_SIMPLIFY
)
1920 /* Populate the map of equivalent simplifies. */
1921 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1923 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1938 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1940 kids
[i
]->analyze (map
);
1941 num_leafs
+= kids
[i
]->num_leafs
;
1942 total_size
+= kids
[i
]->total_size
;
1943 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1947 /* Insert O into the decision tree and return the decision tree node found
1951 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1952 unsigned pos
, dt_node
*parent
)
1954 dt_node
*q
, *elm
= 0;
1956 if (capture
*c
= dyn_cast
<capture
*> (o
))
1958 unsigned capt_index
= c
->where
;
1960 if (indexes
[capt_index
] == 0)
1963 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1966 q
= elm
= p
->append_true_op (o
, parent
, pos
);
1969 // get to the last capture
1970 for (operand
*what
= c
->what
;
1971 what
&& is_a
<capture
*> (what
);
1972 c
= as_a
<capture
*> (what
), what
= c
->what
)
1977 unsigned cc_index
= c
->where
;
1978 dt_operand
*match_op
= indexes
[cc_index
];
1980 dt_operand
temp (dt_node::DT_TRUE
, 0, 0, 0, 0);
1981 elm
= decision_tree::find_node (p
->kids
, &temp
);
1985 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
, 0, 0);
1986 temp
.value_match
= c
->value_match
;
1987 elm
= decision_tree::find_node (p
->kids
, &temp
);
1992 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0, 0, 0);
1993 elm
= decision_tree::find_node (p
->kids
, &temp
);
1997 gcc_assert (elm
->type
== dt_node::DT_TRUE
1998 || elm
->type
== dt_node::DT_OPERAND
1999 || elm
->type
== dt_node::DT_MATCH
);
2000 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
2005 p
= p
->append_match_op (o
, indexes
[capt_index
], parent
, pos
);
2006 as_a
<dt_operand
*>(p
)->value_match
= c
->value_match
;
2008 return insert_operand (p
, c
->what
, indexes
, 0, p
);
2013 p
= p
->append_op (o
, parent
, pos
);
2016 if (expr
*e
= dyn_cast
<expr
*>(o
))
2018 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2019 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
2025 /* Insert S into the decision tree. */
2028 decision_tree::insert (class simplify
*s
, unsigned pattern_no
)
2031 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
2032 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
2033 p
->append_simplify (s
, pattern_no
, indexes
);
2036 /* Debug functions to dump the decision tree. */
2039 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
2041 if (p
->type
== dt_node::DT_NODE
)
2042 fprintf (f
, "root");
2046 for (unsigned i
= 0; i
< indent
; i
++)
2049 if (p
->type
== dt_node::DT_OPERAND
)
2051 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
2052 print_operand (dop
->op
, f
, true);
2054 else if (p
->type
== dt_node::DT_TRUE
)
2055 fprintf (f
, "true");
2056 else if (p
->type
== dt_node::DT_MATCH
)
2057 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
2058 else if (p
->type
== dt_node::DT_SIMPLIFY
)
2060 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
2061 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
2062 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
2063 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
2066 if (is_a
<dt_operand
*> (p
))
2067 fprintf (f
, " [%u]", as_a
<dt_operand
*> (p
)->for_id
);
2070 fprintf (stderr
, " (%p, %p), %u, %u\n",
2071 (void *) p
, (void *) p
->parent
, p
->level
, p
->kids
.length ());
2073 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
2074 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
2078 decision_tree::print (FILE *f
)
2080 return decision_tree::print_node (root
, f
);
2084 /* For GENERIC we have to take care of wrapping multiple-used
2085 expressions with side-effects in save_expr and preserve side-effects
2086 of expressions with omit_one_operand. Analyze captures in
2087 match, result and with expressions and perform early-outs
2088 on the outermost match expression operands for cases we cannot
2094 capture_info (simplify
*s
, operand
*, bool);
2095 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
2096 bool walk_result (operand
*o
, bool, operand
*);
2097 void walk_c_expr (c_expr
*);
2103 bool force_no_side_effects_p
;
2104 bool force_single_use
;
2105 bool cond_expr_cond_p
;
2106 unsigned long toplevel_msk
;
2107 unsigned match_use_count
;
2108 unsigned result_use_count
;
2113 auto_vec
<cinfo
> info
;
2114 unsigned long force_no_side_effects
;
2118 /* Analyze captures in S. */
2120 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
2125 if (s
->kind
== simplify::MATCH
)
2127 force_no_side_effects
= -1;
2131 force_no_side_effects
= 0;
2132 info
.safe_grow_cleared (s
->capture_max
+ 1);
2133 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2134 info
[i
].same_as
= i
;
2136 e
= as_a
<expr
*> (s
->match
);
2137 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2138 walk_match (e
->ops
[i
], i
,
2139 (i
!= 0 && *e
->operation
== COND_EXPR
)
2140 || *e
->operation
== TRUTH_ANDIF_EXPR
2141 || *e
->operation
== TRUTH_ORIF_EXPR
,
2143 && (*e
->operation
== COND_EXPR
2144 || *e
->operation
== VEC_COND_EXPR
));
2146 walk_result (s
->result
, false, result
);
2149 /* Analyze captures in the match expression piece O. */
2152 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
2153 bool conditional_p
, bool cond_expr_cond_p
)
2155 if (capture
*c
= dyn_cast
<capture
*> (o
))
2157 unsigned where
= c
->where
;
2158 info
[where
].match_use_count
++;
2159 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
2160 info
[where
].force_no_side_effects_p
|= conditional_p
;
2161 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
2166 /* Recurse to exprs and captures. */
2167 if (is_a
<capture
*> (c
->what
)
2168 || is_a
<expr
*> (c
->what
))
2169 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
2170 /* We need to look past multiple captures to find a captured
2171 expression as with conditional converts two captures
2172 can be collapsed onto the same expression. Also collect
2173 what captures capture the same thing. */
2174 while (c
->what
&& is_a
<capture
*> (c
->what
))
2176 c
= as_a
<capture
*> (c
->what
);
2177 if (info
[c
->where
].same_as
!= c
->where
2178 && info
[c
->where
].same_as
!= info
[where
].same_as
)
2179 fatal_at (c
->location
, "cannot handle this collapsed capture");
2180 info
[c
->where
].same_as
= info
[where
].same_as
;
2182 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2185 && (e
= dyn_cast
<expr
*> (c
->what
)))
2187 /* Zero-operand expression captures like ADDR_EXPR@0 are
2188 similar as predicates -- if they are not mentioned in
2189 the result we have to force them to have no side-effects. */
2190 if (e
->ops
.length () != 0)
2191 info
[where
].expr_p
= true;
2192 info
[where
].force_single_use
|= e
->force_single_use
;
2195 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2197 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2199 bool cond_p
= conditional_p
;
2200 bool cond_expr_cond_p
= false;
2201 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2203 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2204 || *e
->operation
== TRUTH_ORIF_EXPR
)
2207 && (*e
->operation
== COND_EXPR
2208 || *e
->operation
== VEC_COND_EXPR
))
2209 cond_expr_cond_p
= true;
2210 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
2213 else if (is_a
<predicate
*> (o
))
2215 /* Mark non-captured leafs toplevel arg for checking. */
2216 force_no_side_effects
|= 1 << toplevel_arg
;
2219 warning_at (o
->location
,
2220 "forcing no side-effects on possibly lost leaf");
2226 /* Analyze captures in the result expression piece O. Return true
2227 if RESULT was visited in one of the children. Only visit
2228 non-if/with children if they are rooted on RESULT. */
2231 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
2233 if (capture
*c
= dyn_cast
<capture
*> (o
))
2235 unsigned where
= info
[c
->where
].same_as
;
2236 info
[where
].result_use_count
++;
2237 /* If we substitute an expression capture we don't know
2238 which captures this will end up using (well, we don't
2239 compute that). Force the uses to be side-effect free
2240 which means forcing the toplevels that reach the
2241 expression side-effect free. */
2242 if (info
[where
].expr_p
)
2243 force_no_side_effects
|= info
[where
].toplevel_msk
;
2244 /* Mark CSE capture uses as forced to have no side-effects. */
2246 && is_a
<expr
*> (c
->what
))
2248 info
[where
].cse_p
= true;
2249 walk_result (c
->what
, true, result
);
2252 else if (expr
*e
= dyn_cast
<expr
*> (o
))
2254 id_base
*opr
= e
->operation
;
2255 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2256 opr
= uid
->substitutes
[0];
2257 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
2259 bool cond_p
= conditional_p
;
2260 if (i
!= 0 && *e
->operation
== COND_EXPR
)
2262 else if (*e
->operation
== TRUTH_ANDIF_EXPR
2263 || *e
->operation
== TRUTH_ORIF_EXPR
)
2265 walk_result (e
->ops
[i
], cond_p
, result
);
2268 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
2270 /* 'if' conditions should be all fine. */
2271 if (e
->trueexpr
== result
)
2273 walk_result (e
->trueexpr
, false, result
);
2276 if (e
->falseexpr
== result
)
2278 walk_result (e
->falseexpr
, false, result
);
2282 if (is_a
<if_expr
*> (e
->trueexpr
)
2283 || is_a
<with_expr
*> (e
->trueexpr
))
2284 res
|= walk_result (e
->trueexpr
, false, result
);
2286 && (is_a
<if_expr
*> (e
->falseexpr
)
2287 || is_a
<with_expr
*> (e
->falseexpr
)))
2288 res
|= walk_result (e
->falseexpr
, false, result
);
2291 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
2293 bool res
= (e
->subexpr
== result
);
2295 || is_a
<if_expr
*> (e
->subexpr
)
2296 || is_a
<with_expr
*> (e
->subexpr
))
2297 res
|= walk_result (e
->subexpr
, false, result
);
2299 walk_c_expr (e
->with
);
2302 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
2310 /* Look for captures in the C expr E. */
2313 capture_info::walk_c_expr (c_expr
*e
)
2315 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2316 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2317 really escape through. */
2318 unsigned p_depth
= 0;
2319 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
2321 const cpp_token
*t
= &e
->code
[i
];
2322 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
2324 if (t
->type
== CPP_NAME
2325 && (strcmp ((const char *)CPP_HASHNODE
2326 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
2327 || strcmp ((const char *)CPP_HASHNODE
2328 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
2329 || strcmp ((const char *)CPP_HASHNODE
2330 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
2331 || ((id
= get_operator ((const char *)CPP_HASHNODE
2332 (t
->val
.node
.node
)->ident
.str
))
2333 && is_a
<predicate_id
*> (id
)))
2334 && n
->type
== CPP_OPEN_PAREN
)
2336 else if (t
->type
== CPP_CLOSE_PAREN
2339 else if (p_depth
== 0
2340 && t
->type
== CPP_ATSIGN
2341 && (n
->type
== CPP_NUMBER
2342 || n
->type
== CPP_NAME
)
2343 && !(n
->flags
& PREV_WHITE
))
2346 if (n
->type
== CPP_NUMBER
)
2347 id
= (const char *)n
->val
.str
.text
;
2349 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2350 unsigned *where
= e
->capture_ids
->get(id
);
2352 fatal_at (n
, "unknown capture id '%s'", id
);
2353 info
[info
[*where
].same_as
].force_no_side_effects_p
= true;
2356 warning_at (t
, "capture escapes");
2362 /* Code generation off the decision tree and the refered AST nodes. */
2365 is_conversion (id_base
*op
)
2367 return (*op
== CONVERT_EXPR
2369 || *op
== FLOAT_EXPR
2370 || *op
== FIX_TRUNC_EXPR
2371 || *op
== VIEW_CONVERT_EXPR
);
2374 /* Get the type to be used for generating operand POS of OP from the
2378 get_operand_type (id_base
*op
, unsigned pos
,
2379 const char *in_type
,
2380 const char *expr_type
,
2381 const char *other_oprnd_type
)
2383 /* Generally operands whose type does not match the type of the
2384 expression generated need to know their types but match and
2385 thus can fall back to 'other_oprnd_type'. */
2386 if (is_conversion (op
))
2387 return other_oprnd_type
;
2388 else if (*op
== REALPART_EXPR
2389 || *op
== IMAGPART_EXPR
)
2390 return other_oprnd_type
;
2391 else if (is_a
<operator_id
*> (op
)
2392 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2393 return other_oprnd_type
;
2394 else if (*op
== COND_EXPR
2396 return "boolean_type_node";
2397 else if (strncmp (op
->id
, "CFN_COND_", 9) == 0)
2399 /* IFN_COND_* operands 1 and later by default have the same type
2400 as the result. The type of operand 0 needs to be specified
2402 if (pos
> 0 && expr_type
)
2404 else if (pos
> 0 && in_type
)
2411 /* Otherwise all types should match - choose one in order of
2418 return other_oprnd_type
;
2422 /* Generate transform code for an expression. */
2425 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2426 int depth
, const char *in_type
, capture_info
*cinfo
,
2427 dt_operand
**indexes
, int)
2429 id_base
*opr
= operation
;
2430 /* When we delay operator substituting during lowering of fors we
2431 make sure that for code-gen purposes the effects of each substitute
2432 are the same. Thus just look at that. */
2433 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2434 opr
= uid
->substitutes
[0];
2436 bool conversion_p
= is_conversion (opr
);
2437 const char *type
= expr_type
;
2440 /* If there was a type specification in the pattern use it. */
2442 else if (conversion_p
)
2443 /* For conversions we need to build the expression using the
2444 outer type passed in. */
2446 else if (*opr
== REALPART_EXPR
2447 || *opr
== IMAGPART_EXPR
)
2449 /* __real and __imag use the component type of its operand. */
2450 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2453 else if (is_a
<operator_id
*> (opr
)
2454 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2456 /* comparisons use boolean_type_node (or what gets in), but
2457 their operands need to figure out the types themselves. */
2462 sprintf (optype
, "boolean_type_node");
2467 else if (*opr
== COND_EXPR
2468 || *opr
== VEC_COND_EXPR
2469 || strncmp (opr
->id
, "CFN_COND_", 9) == 0)
2471 /* Conditions are of the same type as their first alternative. */
2472 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2477 /* Other operations are of the same type as their first operand. */
2478 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2482 fatal_at (location
, "cannot determine type of operand");
2484 fprintf_indent (f
, indent
, "{\n");
2486 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2488 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2489 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2492 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2494 = get_operand_type (opr
, i
, in_type
, expr_type
,
2495 i
== 0 ? NULL
: op0type
);
2496 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2499 || *opr
== VEC_COND_EXPR
) && i
== 0 ? 1 : 2);
2502 const char *opr_name
;
2503 if (*operation
== CONVERT_EXPR
)
2504 opr_name
= "NOP_EXPR";
2506 opr_name
= operation
->id
;
2510 if (*opr
== CONVERT_EXPR
)
2512 fprintf_indent (f
, indent
,
2513 "if (%s != TREE_TYPE (ops%d[0])\n",
2515 fprintf_indent (f
, indent
,
2516 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2518 fprintf_indent (f
, indent
+ 2, "{\n");
2521 /* ??? Building a stmt can fail for various reasons here, seq being
2522 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2523 So if we fail here we should continue matching other patterns. */
2524 fprintf_indent (f
, indent
, "gimple_match_op tem_op "
2525 "(res_op->cond.any_else (), %s, %s", opr_name
, type
);
2526 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2527 fprintf (f
, ", ops%d[%u]", depth
, i
);
2528 fprintf (f
, ");\n");
2529 fprintf_indent (f
, indent
,
2530 "gimple_resimplify%d (lseq, &tem_op, valueize);\n",
2532 fprintf_indent (f
, indent
,
2533 "res = maybe_push_res_to_seq (&tem_op, lseq);\n");
2534 fprintf_indent (f
, indent
,
2535 "if (!res) return false;\n");
2536 if (*opr
== CONVERT_EXPR
)
2539 fprintf_indent (f
, indent
, " }\n");
2540 fprintf_indent (f
, indent
, "else\n");
2541 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2546 if (*opr
== CONVERT_EXPR
)
2548 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2552 if (opr
->kind
== id_base::CODE
)
2553 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2554 ops
.length(), opr_name
, type
);
2557 fprintf_indent (f
, indent
, "{\n");
2558 fprintf_indent (f
, indent
, " res = maybe_build_call_expr_loc (loc, "
2559 "%s, %s, %d", opr_name
, type
, ops
.length());
2561 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2562 fprintf (f
, ", ops%d[%u]", depth
, i
);
2563 fprintf (f
, ");\n");
2564 if (opr
->kind
!= id_base::CODE
)
2566 fprintf_indent (f
, indent
, " if (!res)\n");
2567 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
2568 fprintf_indent (f
, indent
, "}\n");
2570 if (*opr
== CONVERT_EXPR
)
2573 fprintf_indent (f
, indent
, "else\n");
2574 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2577 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2579 fprintf_indent (f
, indent
, "}\n");
2582 /* Generate code for a c_expr which is either the expression inside
2583 an if statement or a sequence of statements which computes a
2584 result to be stored to DEST. */
2587 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2588 bool, int, const char *, capture_info
*,
2591 if (dest
&& nr_stmts
== 1)
2592 fprintf_indent (f
, indent
, "%s = ", dest
);
2594 unsigned stmt_nr
= 1;
2595 for (unsigned i
= 0; i
< code
.length (); ++i
)
2597 const cpp_token
*token
= &code
[i
];
2599 /* Replace captures for code-gen. */
2600 if (token
->type
== CPP_ATSIGN
)
2602 const cpp_token
*n
= &code
[i
+1];
2603 if ((n
->type
== CPP_NUMBER
2604 || n
->type
== CPP_NAME
)
2605 && !(n
->flags
& PREV_WHITE
))
2607 if (token
->flags
& PREV_WHITE
)
2610 if (n
->type
== CPP_NUMBER
)
2611 id
= (const char *)n
->val
.str
.text
;
2613 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2614 unsigned *cid
= capture_ids
->get (id
);
2616 fatal_at (token
, "unknown capture id");
2617 fprintf (f
, "captures[%u]", *cid
);
2623 if (token
->flags
& PREV_WHITE
)
2626 if (token
->type
== CPP_NAME
)
2628 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2630 for (j
= 0; j
< ids
.length (); ++j
)
2632 if (strcmp (id
, ids
[j
].id
) == 0)
2634 fprintf (f
, "%s", ids
[j
].oper
);
2638 if (j
< ids
.length ())
2642 /* Output the token as string. */
2643 char *tk
= (char *)cpp_token_as_text (r
, token
);
2646 if (token
->type
== CPP_SEMICOLON
)
2650 if (dest
&& stmt_nr
== nr_stmts
)
2651 fprintf_indent (f
, indent
, "%s = ", dest
);
2656 /* Generate transform code for a capture. */
2659 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2660 int depth
, const char *in_type
, capture_info
*cinfo
,
2661 dt_operand
**indexes
, int cond_handling
)
2663 if (what
&& is_a
<expr
*> (what
))
2665 if (indexes
[where
] == 0)
2668 sprintf (buf
, "captures[%u]", where
);
2669 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2674 /* If in GENERIC some capture is used multiple times, unshare it except
2675 when emitting the last use. */
2677 && cinfo
->info
.exists ()
2678 && cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
> 1)
2680 fprintf_indent (f
, indent
, "%s = unshare_expr (captures[%u]);\n",
2682 cinfo
->info
[cinfo
->info
[where
].same_as
].result_use_count
--;
2685 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2687 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2688 with substituting a capture of that. */
2690 && cond_handling
!= 0
2691 && cinfo
->info
[where
].cond_expr_cond_p
)
2693 /* If substituting into a cond_expr condition, unshare. */
2694 if (cond_handling
== 1)
2695 fprintf_indent (f
, indent
, "%s = unshare_expr (%s);\n", dest
, dest
);
2696 /* If substituting elsewhere we might need to decompose it. */
2697 else if (cond_handling
== 2)
2699 /* ??? Returning false here will also not allow any other patterns
2700 to match unless this generator was split out. */
2701 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2702 fprintf_indent (f
, indent
, " {\n");
2703 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2704 fprintf_indent (f
, indent
, " %s = gimple_build (seq,"
2706 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2707 " TREE_OPERAND (%s, 1));\n",
2708 dest
, dest
, dest
, dest
, dest
);
2709 fprintf_indent (f
, indent
, " }\n");
2714 /* Return the name of the operand representing the decision tree node.
2715 Use NAME as space to generate it. */
2718 dt_operand::get_name (char *name
)
2721 sprintf (name
, "t");
2722 else if (parent
->level
== 1)
2723 sprintf (name
, "op%u", pos
);
2724 else if (parent
->type
== dt_node::DT_MATCH
)
2725 return as_a
<dt_operand
*> (parent
)->get_name (name
);
2727 sprintf (name
, "o%u%u", parent
->level
, pos
);
2731 /* Fill NAME with the operand name at position POS. */
2734 dt_operand::gen_opname (char *name
, unsigned pos
)
2737 sprintf (name
, "op%u", pos
);
2739 sprintf (name
, "o%u%u", level
, pos
);
2742 /* Generate matching code for the decision tree operand which is
2746 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2748 predicate
*p
= as_a
<predicate
*> (op
);
2750 if (p
->p
->matchers
.exists ())
2752 /* If this is a predicate generated from a pattern mangle its
2753 name and pass on the valueize hook. */
2755 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2758 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2761 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2762 fprintf_indent (f
, indent
+ 2, "{\n");
2766 /* Generate matching code for the decision tree operand which is
2770 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
, bool)
2772 char match_opname
[20];
2773 match_dop
->get_name (match_opname
);
2775 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2776 "|| operand_equal_p (%s, %s, 0))\n",
2777 opname
, match_opname
, opname
, opname
, match_opname
);
2779 fprintf_indent (f
, indent
, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2780 "|| (operand_equal_p (%s, %s, 0) "
2781 "&& types_match (%s, %s)))\n",
2782 opname
, match_opname
, opname
, opname
, match_opname
,
2783 opname
, match_opname
);
2784 fprintf_indent (f
, indent
+ 2, "{\n");
2788 /* Generate GIMPLE matching code for the decision tree operand. */
2791 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2793 expr
*e
= static_cast<expr
*> (op
);
2794 id_base
*id
= e
->operation
;
2795 unsigned n_ops
= e
->ops
.length ();
2796 unsigned n_braces
= 0;
2798 for (unsigned i
= 0; i
< n_ops
; ++i
)
2800 char child_opname
[20];
2801 gen_opname (child_opname
, i
);
2803 if (id
->kind
== id_base::CODE
)
2806 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2807 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2809 /* ??? If this is a memory operation we can't (and should not)
2810 match this. The only sensible operand types are
2811 SSA names and invariants. */
2816 fprintf_indent (f
, indent
,
2817 "tree %s = TREE_OPERAND (%s, %i);\n",
2818 child_opname
, opname
, i
);
2821 fprintf_indent (f
, indent
,
2822 "tree %s = TREE_OPERAND "
2823 "(gimple_assign_rhs1 (def), %i);\n",
2825 fprintf_indent (f
, indent
,
2826 "if ((TREE_CODE (%s) == SSA_NAME\n",
2828 fprintf_indent (f
, indent
,
2829 " || is_gimple_min_invariant (%s)))\n",
2831 fprintf_indent (f
, indent
,
2835 fprintf_indent (f
, indent
,
2836 "%s = do_valueize (valueize, %s);\n",
2837 child_opname
, child_opname
);
2841 fprintf_indent (f
, indent
,
2842 "tree %s = gimple_assign_rhs%u (def);\n",
2843 child_opname
, i
+ 1);
2846 fprintf_indent (f
, indent
,
2847 "tree %s = gimple_call_arg (def, %u);\n",
2849 fprintf_indent (f
, indent
,
2850 "%s = do_valueize (valueize, %s);\n",
2851 child_opname
, child_opname
);
2853 /* While the toplevel operands are canonicalized by the caller
2854 after valueizing operands of sub-expressions we have to
2855 re-canonicalize operand order. */
2856 int opno
= commutative_op (id
);
2859 char child_opname0
[20], child_opname1
[20];
2860 gen_opname (child_opname0
, opno
);
2861 gen_opname (child_opname1
, opno
+ 1);
2862 fprintf_indent (f
, indent
,
2863 "if (tree_swap_operands_p (%s, %s))\n",
2864 child_opname0
, child_opname1
);
2865 fprintf_indent (f
, indent
,
2866 " std::swap (%s, %s);\n",
2867 child_opname0
, child_opname1
);
2873 /* Generate GENERIC matching code for the decision tree operand. */
2876 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2878 expr
*e
= static_cast<expr
*> (op
);
2879 unsigned n_ops
= e
->ops
.length ();
2881 for (unsigned i
= 0; i
< n_ops
; ++i
)
2883 char child_opname
[20];
2884 gen_opname (child_opname
, i
);
2886 if (e
->operation
->kind
== id_base::CODE
)
2887 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2888 child_opname
, opname
, i
);
2890 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2891 child_opname
, opname
, i
);
2897 /* Generate matching code for the children of the decision tree node. */
2900 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2902 auto_vec
<dt_operand
*> gimple_exprs
;
2903 auto_vec
<dt_operand
*> generic_exprs
;
2904 auto_vec
<dt_operand
*> fns
;
2905 auto_vec
<dt_operand
*> generic_fns
;
2906 auto_vec
<dt_operand
*> preds
;
2907 auto_vec
<dt_node
*> others
;
2909 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2911 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2913 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2914 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2916 if (e
->ops
.length () == 0
2917 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2918 generic_exprs
.safe_push (op
);
2919 else if (e
->operation
->kind
== id_base::FN
)
2924 generic_fns
.safe_push (op
);
2926 else if (e
->operation
->kind
== id_base::PREDICATE
)
2927 preds
.safe_push (op
);
2930 if (gimple
&& !e
->is_generic
)
2931 gimple_exprs
.safe_push (op
);
2933 generic_exprs
.safe_push (op
);
2936 else if (op
->op
->type
== operand::OP_PREDICATE
)
2937 others
.safe_push (kids
[i
]);
2941 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2942 others
.safe_push (kids
[i
]);
2943 else if (kids
[i
]->type
== dt_node::DT_MATCH
2944 || kids
[i
]->type
== dt_node::DT_TRUE
)
2946 /* A DT_TRUE operand serves as a barrier - generate code now
2947 for what we have collected sofar.
2948 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2949 dependent matches to get out-of-order. Generate code now
2950 for what we have collected sofar. */
2951 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2952 fns
, generic_fns
, preds
, others
);
2953 /* And output the true operand itself. */
2954 kids
[i
]->gen (f
, indent
, gimple
);
2955 gimple_exprs
.truncate (0);
2956 generic_exprs
.truncate (0);
2958 generic_fns
.truncate (0);
2960 others
.truncate (0);
2966 /* Generate code for the remains. */
2967 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2968 fns
, generic_fns
, preds
, others
);
2971 /* Generate matching code for the children of the decision tree node. */
2974 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2975 vec
<dt_operand
*> gimple_exprs
,
2976 vec
<dt_operand
*> generic_exprs
,
2977 vec
<dt_operand
*> fns
,
2978 vec
<dt_operand
*> generic_fns
,
2979 vec
<dt_operand
*> preds
,
2980 vec
<dt_node
*> others
)
2983 char *kid_opname
= buf
;
2985 unsigned exprs_len
= gimple_exprs
.length ();
2986 unsigned gexprs_len
= generic_exprs
.length ();
2987 unsigned fns_len
= fns
.length ();
2988 unsigned gfns_len
= generic_fns
.length ();
2990 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2993 gimple_exprs
[0]->get_name (kid_opname
);
2995 fns
[0]->get_name (kid_opname
);
2997 generic_fns
[0]->get_name (kid_opname
);
2999 generic_exprs
[0]->get_name (kid_opname
);
3001 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
3002 fprintf_indent (f
, indent
, " {\n");
3006 if (exprs_len
|| fns_len
)
3008 fprintf_indent (f
, indent
,
3009 "case SSA_NAME:\n");
3010 fprintf_indent (f
, indent
,
3011 " if (gimple *def_stmt = get_def (valueize, %s))\n",
3013 fprintf_indent (f
, indent
,
3018 fprintf_indent (f
, indent
,
3019 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
3020 fprintf_indent (f
, indent
,
3021 " switch (gimple_assign_rhs_code (def))\n");
3023 fprintf_indent (f
, indent
, "{\n");
3024 for (unsigned i
= 0; i
< exprs_len
; ++i
)
3026 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
3027 id_base
*op
= e
->operation
;
3028 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3029 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3031 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3032 fprintf_indent (f
, indent
, " {\n");
3033 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
3034 fprintf_indent (f
, indent
, " break;\n");
3035 fprintf_indent (f
, indent
, " }\n");
3037 fprintf_indent (f
, indent
, "default:;\n");
3038 fprintf_indent (f
, indent
, "}\n");
3044 fprintf_indent (f
, indent
,
3045 "%sif (gcall *def = dyn_cast <gcall *>"
3047 exprs_len
? "else " : "");
3048 fprintf_indent (f
, indent
,
3049 " switch (gimple_call_combined_fn (def))\n");
3052 fprintf_indent (f
, indent
, "{\n");
3053 for (unsigned i
= 0; i
< fns_len
; ++i
)
3055 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
3056 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3057 fprintf_indent (f
, indent
, " {\n");
3058 fns
[i
]->gen (f
, indent
+ 4, true);
3059 fprintf_indent (f
, indent
, " break;\n");
3060 fprintf_indent (f
, indent
, " }\n");
3063 fprintf_indent (f
, indent
, "default:;\n");
3064 fprintf_indent (f
, indent
, "}\n");
3069 fprintf_indent (f
, indent
, " }\n");
3070 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
3071 here rather than in the next loop. */
3072 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3074 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3075 id_base
*op
= e
->operation
;
3076 if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3078 fprintf_indent (f
, indent
+ 4, "{\n");
3079 generic_exprs
[i
]->gen (f
, indent
+ 6, gimple
);
3080 fprintf_indent (f
, indent
+ 4, "}\n");
3084 fprintf_indent (f
, indent
, " break;\n");
3087 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
3089 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
3090 id_base
*op
= e
->operation
;
3091 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
3092 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
3093 else if (*op
== SSA_NAME
&& (exprs_len
|| fns_len
))
3094 /* Already handled above. */
3097 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
3098 fprintf_indent (f
, indent
, " {\n");
3099 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
3100 fprintf_indent (f
, indent
, " break;\n");
3101 fprintf_indent (f
, indent
, " }\n");
3106 fprintf_indent (f
, indent
,
3107 "case CALL_EXPR:\n");
3108 fprintf_indent (f
, indent
,
3109 " switch (get_call_combined_fn (%s))\n",
3111 fprintf_indent (f
, indent
,
3115 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
3117 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
3118 gcc_assert (e
->operation
->kind
== id_base::FN
);
3120 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
3121 fprintf_indent (f
, indent
, " {\n");
3122 generic_fns
[j
]->gen (f
, indent
+ 4, false);
3123 fprintf_indent (f
, indent
, " break;\n");
3124 fprintf_indent (f
, indent
, " }\n");
3126 fprintf_indent (f
, indent
, "default:;\n");
3129 fprintf_indent (f
, indent
, " }\n");
3130 fprintf_indent (f
, indent
, " break;\n");
3133 /* Close switch (TREE_CODE ()). */
3134 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
3137 fprintf_indent (f
, indent
, " default:;\n");
3138 fprintf_indent (f
, indent
, " }\n");
3141 for (unsigned i
= 0; i
< preds
.length (); ++i
)
3143 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
3144 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
3145 preds
[i
]->get_name (kid_opname
);
3146 fprintf_indent (f
, indent
, "{\n");
3148 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
3149 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
3150 gimple
? "gimple" : "tree",
3151 p
->id
, kid_opname
, kid_opname
,
3152 gimple
? ", valueize" : "");
3153 fprintf_indent (f
, indent
, " {\n");
3154 for (int j
= 0; j
< p
->nargs
; ++j
)
3156 char child_opname
[20];
3157 preds
[i
]->gen_opname (child_opname
, j
);
3158 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
3159 child_opname
, kid_opname
, j
);
3161 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
3164 fprintf_indent (f
, indent
, "}\n");
3167 for (unsigned i
= 0; i
< others
.length (); ++i
)
3168 others
[i
]->gen (f
, indent
, gimple
);
3171 /* Generate matching code for the decision tree operand. */
3174 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
3179 unsigned n_braces
= 0;
3181 if (type
== DT_OPERAND
)
3184 case operand::OP_PREDICATE
:
3185 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
3188 case operand::OP_EXPR
:
3190 n_braces
= gen_gimple_expr (f
, indent
);
3192 n_braces
= gen_generic_expr (f
, indent
, opname
);
3198 else if (type
== DT_TRUE
)
3200 else if (type
== DT_MATCH
)
3201 n_braces
= gen_match_op (f
, indent
, opname
, gimple
);
3205 indent
+= 4 * n_braces
;
3206 gen_kids (f
, indent
, gimple
);
3208 for (unsigned i
= 0; i
< n_braces
; ++i
)
3213 fprintf_indent (f
, indent
, " }\n");
3218 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3219 step of a '(simplify ...)' or '(match ...)'. This handles everything
3220 that is not part of the decision tree (simplify->match).
3221 Main recursive worker. */
3224 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
3228 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
3230 fprintf_indent (f
, indent
, "{\n");
3232 output_line_directive (f
, w
->location
);
3233 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3234 gen_1 (f
, indent
, gimple
, w
->subexpr
);
3236 fprintf_indent (f
, indent
, "}\n");
3239 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
3241 output_line_directive (f
, ife
->location
);
3242 fprintf_indent (f
, indent
, "if (");
3243 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
3245 fprintf_indent (f
, indent
+ 2, "{\n");
3247 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
3249 fprintf_indent (f
, indent
+ 2, "}\n");
3252 fprintf_indent (f
, indent
, "else\n");
3253 fprintf_indent (f
, indent
+ 2, "{\n");
3255 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
3257 fprintf_indent (f
, indent
+ 2, "}\n");
3263 /* Analyze captures and perform early-outs on the incoming arguments
3264 that cover cases we cannot handle. */
3265 capture_info
cinfo (s
, result
, gimple
);
3266 if (s
->kind
== simplify::SIMPLIFY
)
3270 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3271 if (cinfo
.force_no_side_effects
& (1 << i
))
3273 fprintf_indent (f
, indent
,
3274 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3277 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
3278 "forcing toplevel operand to have no "
3281 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3282 if (cinfo
.info
[i
].cse_p
)
3284 else if (cinfo
.info
[i
].force_no_side_effects_p
3285 && (cinfo
.info
[i
].toplevel_msk
3286 & cinfo
.force_no_side_effects
) == 0)
3288 fprintf_indent (f
, indent
,
3289 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3290 "return NULL_TREE;\n", i
);
3292 warning_at (cinfo
.info
[i
].c
->location
,
3293 "forcing captured operand to have no "
3296 else if ((cinfo
.info
[i
].toplevel_msk
3297 & cinfo
.force_no_side_effects
) != 0)
3298 /* Mark capture as having no side-effects if we had to verify
3299 that via forced toplevel operand checks. */
3300 cinfo
.info
[i
].force_no_side_effects_p
= true;
3304 /* Force single-use restriction by only allowing simple
3305 results via setting seq to NULL. */
3306 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
3307 bool first_p
= true;
3308 for (int i
= 0; i
<= s
->capture_max
; ++i
)
3309 if (cinfo
.info
[i
].force_single_use
)
3313 fprintf_indent (f
, indent
, "if (lseq\n");
3314 fprintf_indent (f
, indent
, " && (");
3320 fprintf_indent (f
, indent
, " || ");
3322 fprintf (f
, "!single_use (captures[%d])", i
);
3326 fprintf (f
, "))\n");
3327 fprintf_indent (f
, indent
, " lseq = NULL;\n");
3332 if (s
->kind
== simplify::SIMPLIFY
)
3333 fprintf_indent (f
, indent
, "if (__builtin_expect (!dbg_cnt (match), 0)) return %s;\n",
3334 gimple
? "false" : "NULL_TREE");
3336 fprintf_indent (f
, indent
, "if (__builtin_expect (dump_file && (dump_flags & TDF_FOLDING), 0)) "
3337 "fprintf (dump_file, \"%s ",
3338 s
->kind
== simplify::SIMPLIFY
3339 ? "Applying pattern" : "Matching expression");
3340 fprintf (f
, "%%s:%%d, %%s:%%d\\n\", ");
3341 output_line_directive (f
,
3342 result
? result
->location
: s
->match
->location
, true,
3344 fprintf (f
, ", __FILE__, __LINE__);\n");
3348 /* If there is no result then this is a predicate implementation. */
3349 fprintf_indent (f
, indent
, "return true;\n");
3353 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3354 in outermost position). */
3355 if (result
->type
== operand::OP_EXPR
3356 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
3357 result
= as_a
<expr
*> (result
)->ops
[0];
3358 if (result
->type
== operand::OP_EXPR
)
3360 expr
*e
= as_a
<expr
*> (result
);
3361 id_base
*opr
= e
->operation
;
3362 bool is_predicate
= false;
3363 /* When we delay operator substituting during lowering of fors we
3364 make sure that for code-gen purposes the effects of each substitute
3365 are the same. Thus just look at that. */
3366 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3367 opr
= uid
->substitutes
[0];
3368 else if (is_a
<predicate_id
*> (opr
))
3369 is_predicate
= true;
3371 fprintf_indent (f
, indent
, "res_op->set_op (%s, type, %d);\n",
3372 *e
->operation
== CONVERT_EXPR
3373 ? "NOP_EXPR" : e
->operation
->id
,
3375 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3379 snprintf (dest
, 32, "res_ops[%d]", j
);
3381 snprintf (dest
, 32, "res_op->ops[%d]", j
);
3383 = get_operand_type (opr
, j
,
3384 "type", e
->expr_type
,
3386 : "TREE_TYPE (res_op->ops[0])");
3387 /* We need to expand GENERIC conditions we captured from
3388 COND_EXPRs and we need to unshare them when substituting
3390 int cond_handling
= 0;
3392 cond_handling
= ((*opr
== COND_EXPR
3393 || *opr
== VEC_COND_EXPR
) && j
== 0) ? 1 : 2;
3394 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
3395 &cinfo
, indexes
, cond_handling
);
3398 /* Re-fold the toplevel result. It's basically an embedded
3399 gimple_build w/o actually building the stmt. */
3401 fprintf_indent (f
, indent
,
3402 "gimple_resimplify%d (lseq, res_op,"
3403 " valueize);\n", e
->ops
.length ());
3405 else if (result
->type
== operand::OP_CAPTURE
3406 || result
->type
== operand::OP_C_EXPR
)
3408 fprintf_indent (f
, indent
, "tree tem;\n");
3409 result
->gen_transform (f
, indent
, "tem", true, 1, "type",
3411 fprintf_indent (f
, indent
, "res_op->set_value (tem);\n");
3412 if (is_a
<capture
*> (result
)
3413 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3415 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3416 with substituting a capture of that. */
3417 fprintf_indent (f
, indent
,
3418 "if (COMPARISON_CLASS_P (tem))\n");
3419 fprintf_indent (f
, indent
,
3421 fprintf_indent (f
, indent
,
3422 " res_op->ops[0] = TREE_OPERAND (tem, 0);\n");
3423 fprintf_indent (f
, indent
,
3424 " res_op->ops[1] = TREE_OPERAND (tem, 1);\n");
3425 fprintf_indent (f
, indent
,
3431 fprintf_indent (f
, indent
, "return true;\n");
3435 bool is_predicate
= false;
3436 if (result
->type
== operand::OP_EXPR
)
3438 expr
*e
= as_a
<expr
*> (result
);
3439 id_base
*opr
= e
->operation
;
3440 /* When we delay operator substituting during lowering of fors we
3441 make sure that for code-gen purposes the effects of each substitute
3442 are the same. Thus just look at that. */
3443 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3444 opr
= uid
->substitutes
[0];
3445 else if (is_a
<predicate_id
*> (opr
))
3446 is_predicate
= true;
3447 /* Search for captures used multiple times in the result expression
3448 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3449 original expression. */
3451 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3453 if (cinfo
.info
[i
].same_as
!= (unsigned)i
3454 || cinfo
.info
[i
].cse_p
)
3456 if (cinfo
.info
[i
].result_use_count
3457 > cinfo
.info
[i
].match_use_count
)
3458 fprintf_indent (f
, indent
,
3459 "if (! tree_invariant_p (captures[%d])) "
3460 "return NULL_TREE;\n", i
);
3462 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3466 snprintf (dest
, 32, "res_ops[%d]", j
);
3469 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3470 snprintf (dest
, 32, "res_op%d", j
);
3473 = get_operand_type (opr
, j
,
3474 "type", e
->expr_type
,
3476 ? NULL
: "TREE_TYPE (res_op0)");
3477 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3481 fprintf_indent (f
, indent
, "return true;\n");
3484 fprintf_indent (f
, indent
, "tree res;\n");
3485 /* Re-fold the toplevel result. Use non_lvalue to
3486 build NON_LVALUE_EXPRs so they get properly
3487 ignored when in GIMPLE form. */
3488 if (*opr
== NON_LVALUE_EXPR
)
3489 fprintf_indent (f
, indent
,
3490 "res = non_lvalue_loc (loc, res_op0);\n");
3493 if (is_a
<operator_id
*> (opr
))
3494 fprintf_indent (f
, indent
,
3495 "res = fold_build%d_loc (loc, %s, type",
3497 *e
->operation
== CONVERT_EXPR
3498 ? "NOP_EXPR" : e
->operation
->id
);
3500 fprintf_indent (f
, indent
,
3501 "res = maybe_build_call_expr_loc (loc, "
3502 "%s, type, %d", e
->operation
->id
,
3504 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3505 fprintf (f
, ", res_op%d", j
);
3506 fprintf (f
, ");\n");
3507 if (!is_a
<operator_id
*> (opr
))
3509 fprintf_indent (f
, indent
, "if (!res)\n");
3510 fprintf_indent (f
, indent
, " return NULL_TREE;\n");
3515 else if (result
->type
== operand::OP_CAPTURE
3516 || result
->type
== operand::OP_C_EXPR
)
3519 fprintf_indent (f
, indent
, "tree res;\n");
3520 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3527 /* Search for captures not used in the result expression and dependent
3528 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3529 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3531 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3533 if (!cinfo
.info
[i
].force_no_side_effects_p
3534 && !cinfo
.info
[i
].expr_p
3535 && cinfo
.info
[i
].result_use_count
== 0)
3537 fprintf_indent (f
, indent
,
3538 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3540 fprintf_indent (f
, indent
+ 2,
3541 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3542 "fold_ignored_result (captures[%d]), res);\n",
3546 fprintf_indent (f
, indent
, "return res;\n");
3551 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3552 step of a '(simplify ...)' or '(match ...)'. This handles everything
3553 that is not part of the decision tree (simplify->match). */
3556 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3558 fprintf_indent (f
, indent
, "{\n");
3560 output_line_directive (f
,
3561 s
->result
? s
->result
->location
: s
->match
->location
);
3562 if (s
->capture_max
>= 0)
3565 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3566 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3568 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3572 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3574 fprintf (f
, " };\n");
3577 /* If we have a split-out function for the actual transform, call it. */
3578 if (info
&& info
->fname
)
3582 fprintf_indent (f
, indent
, "if (%s (res_op, seq, "
3583 "valueize, type, captures", info
->fname
);
3584 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3585 if (s
->for_subst_vec
[i
].first
->used
)
3586 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3587 fprintf (f
, "))\n");
3588 fprintf_indent (f
, indent
, " return true;\n");
3592 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3594 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3595 fprintf (f
, ", op%d", i
);
3596 fprintf (f
, ", captures");
3597 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3599 if (s
->for_subst_vec
[i
].first
->used
)
3600 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3602 fprintf (f
, ");\n");
3603 fprintf_indent (f
, indent
, "if (res) return res;\n");
3608 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3610 if (! s
->for_subst_vec
[i
].first
->used
)
3612 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3613 fprintf_indent (f
, indent
, "const enum tree_code %s = %s;\n",
3614 s
->for_subst_vec
[i
].first
->id
,
3615 s
->for_subst_vec
[i
].second
->id
);
3616 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3617 fprintf_indent (f
, indent
, "const combined_fn %s = %s;\n",
3618 s
->for_subst_vec
[i
].first
->id
,
3619 s
->for_subst_vec
[i
].second
->id
);
3623 gen_1 (f
, indent
, gimple
, s
->result
);
3627 fprintf_indent (f
, indent
, "}\n");
3631 /* Hash function for finding equivalent transforms. */
3634 sinfo_hashmap_traits::hash (const key_type
&v
)
3636 /* Only bother to compare those originating from the same source pattern. */
3637 return v
->s
->result
->location
;
3640 /* Compare function for finding equivalent transforms. */
3643 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3645 if (o1
->type
!= o2
->type
)
3650 case operand::OP_IF
:
3652 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3653 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3654 /* ??? Properly compare c-exprs. */
3655 if (if1
->cond
!= if2
->cond
)
3657 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3659 if (if1
->falseexpr
!= if2
->falseexpr
3661 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3665 case operand::OP_WITH
:
3667 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3668 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3669 if (with1
->with
!= with2
->with
)
3671 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3676 /* We've hit a result. Time to compare capture-infos - this is required
3677 in addition to the conservative pointer-equivalency of the result IL. */
3678 capture_info
cinfo1 (s1
, o1
, true);
3679 capture_info
cinfo2 (s2
, o2
, true);
3681 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3682 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3685 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3687 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3688 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3689 || (cinfo1
.info
[i
].force_no_side_effects_p
3690 != cinfo2
.info
[i
].force_no_side_effects_p
)
3691 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3692 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3693 /* toplevel_msk is an optimization */
3694 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3695 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3696 /* the pointer back to the capture is for diagnostics only */)
3700 /* ??? Deep-compare the actual result. */
3705 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3706 const key_type
&candidate
)
3708 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3712 /* Main entry to generate code for matching GIMPLE IL off the decision
3716 decision_tree::gen (FILE *f
, bool gimple
)
3722 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3723 "a total number of %u nodes\n",
3724 gimple
? "GIMPLE" : "GENERIC",
3725 root
->num_leafs
, root
->max_level
, root
->total_size
);
3727 /* First split out the transform part of equal leafs. */
3730 for (sinfo_map_t::iterator iter
= si
.begin ();
3731 iter
!= si
.end (); ++iter
)
3733 sinfo
*s
= (*iter
).second
;
3734 /* Do not split out single uses. */
3741 fprintf (stderr
, "found %u uses of", s
->cnt
);
3742 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3745 /* Generate a split out function with the leaf transform code. */
3746 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3749 fprintf (f
, "\nstatic bool\n"
3750 "%s (gimple_match_op *res_op, gimple_seq *seq,\n"
3751 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3752 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3757 fprintf (f
, "\nstatic tree\n"
3758 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3759 (*iter
).second
->fname
);
3760 for (unsigned i
= 0;
3761 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3762 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3763 fprintf (f
, " tree *captures\n");
3765 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3767 if (! s
->s
->s
->for_subst_vec
[i
].first
->used
)
3769 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3770 fprintf (f
, ", const enum tree_code ARG_UNUSED (%s)",
3771 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3772 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3773 fprintf (f
, ", const combined_fn ARG_UNUSED (%s)",
3774 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3777 fprintf (f
, ")\n{\n");
3778 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3780 fprintf (f
, " return false;\n");
3782 fprintf (f
, " return NULL_TREE;\n");
3785 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3787 for (unsigned n
= 1; n
<= 5; ++n
)
3789 /* First generate split-out functions. */
3790 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3792 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3793 expr
*e
= static_cast<expr
*>(dop
->op
);
3794 if (e
->ops
.length () != n
3795 /* Builtin simplifications are somewhat premature on
3796 GENERIC. The following drops patterns with outermost
3797 calls. It's easy to emit overloads for function code
3798 though if necessary. */
3800 && e
->operation
->kind
!= id_base::CODE
))
3804 fprintf (f
, "\nstatic bool\n"
3805 "gimple_simplify_%s (gimple_match_op *res_op,"
3806 " gimple_seq *seq,\n"
3807 " tree (*valueize)(tree) "
3808 "ATTRIBUTE_UNUSED,\n"
3809 " code_helper ARG_UNUSED (code), tree "
3810 "ARG_UNUSED (type)\n",
3813 fprintf (f
, "\nstatic tree\n"
3814 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3815 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3817 for (unsigned i
= 0; i
< n
; ++i
)
3818 fprintf (f
, ", tree op%d", i
);
3821 dop
->gen_kids (f
, 2, gimple
);
3823 fprintf (f
, " return false;\n");
3825 fprintf (f
, " return NULL_TREE;\n");
3829 /* Then generate the main entry with the outermost switch and
3830 tail-calls to the split-out functions. */
3832 fprintf (f
, "\nstatic bool\n"
3833 "gimple_simplify (gimple_match_op *res_op, gimple_seq *seq,\n"
3834 " tree (*valueize)(tree) ATTRIBUTE_UNUSED,\n"
3835 " code_helper code, const tree type");
3837 fprintf (f
, "\ntree\n"
3838 "generic_simplify (location_t loc, enum tree_code code, "
3839 "const tree type ATTRIBUTE_UNUSED");
3840 for (unsigned i
= 0; i
< n
; ++i
)
3841 fprintf (f
, ", tree op%d", i
);
3846 fprintf (f
, " switch (code.get_rep())\n"
3849 fprintf (f
, " switch (code)\n"
3851 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3853 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3854 expr
*e
= static_cast<expr
*>(dop
->op
);
3855 if (e
->ops
.length () != n
3856 /* Builtin simplifications are somewhat premature on
3857 GENERIC. The following drops patterns with outermost
3858 calls. It's easy to emit overloads for function code
3859 though if necessary. */
3861 && e
->operation
->kind
!= id_base::CODE
))
3864 if (*e
->operation
== CONVERT_EXPR
3865 || *e
->operation
== NOP_EXPR
)
3866 fprintf (f
, " CASE_CONVERT:\n");
3868 fprintf (f
, " case %s%s:\n",
3869 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3872 fprintf (f
, " return gimple_simplify_%s (res_op, "
3873 "seq, valueize, code, type", e
->operation
->id
);
3875 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3877 for (unsigned i
= 0; i
< n
; ++i
)
3878 fprintf (f
, ", op%d", i
);
3879 fprintf (f
, ");\n");
3881 fprintf (f
, " default:;\n"
3885 fprintf (f
, " return false;\n");
3887 fprintf (f
, " return NULL_TREE;\n");
3892 /* Output code to implement the predicate P from the decision tree DT. */
3895 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3897 fprintf (f
, "\nbool\n"
3898 "%s%s (tree t%s%s)\n"
3899 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3900 p
->nargs
> 0 ? ", tree *res_ops" : "",
3901 gimple
? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3902 /* Conveniently make 'type' available. */
3903 fprintf_indent (f
, 2, "const tree type = TREE_TYPE (t);\n");
3906 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3907 dt
.root
->gen_kids (f
, 2, gimple
);
3909 fprintf_indent (f
, 2, "return false;\n"
3913 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3916 write_header (FILE *f
, const char *head
)
3918 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3919 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3921 /* Include the header instead of writing it awkwardly quoted here. */
3922 fprintf (f
, "\n#include \"%s\"\n", head
);
3932 parser (cpp_reader
*);
3935 const cpp_token
*next ();
3936 const cpp_token
*peek (unsigned = 1);
3937 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3938 const cpp_token
*expect (enum cpp_ttype
);
3939 const cpp_token
*eat_token (enum cpp_ttype
);
3940 const char *get_string ();
3941 const char *get_ident ();
3942 const cpp_token
*eat_ident (const char *);
3943 const char *get_number ();
3945 unsigned get_internal_capture_id ();
3947 id_base
*parse_operation ();
3948 operand
*parse_capture (operand
*, bool);
3949 operand
*parse_expr ();
3950 c_expr
*parse_c_expr (cpp_ttype
);
3951 operand
*parse_op ();
3953 void record_operlist (location_t
, user_id
*);
3955 void parse_pattern ();
3956 operand
*parse_result (operand
*, predicate_id
*);
3957 void push_simplify (simplify::simplify_kind
,
3958 vec
<simplify
*>&, operand
*, operand
*);
3959 void parse_simplify (simplify::simplify_kind
,
3960 vec
<simplify
*>&, predicate_id
*, operand
*);
3961 void parse_for (location_t
);
3962 void parse_if (location_t
);
3963 void parse_predicates (location_t
);
3964 void parse_operator_list (location_t
);
3966 void finish_match_operand (operand
*);
3969 vec
<c_expr
*> active_ifs
;
3970 vec
<vec
<user_id
*> > active_fors
;
3971 hash_set
<user_id
*> *oper_lists_set
;
3972 vec
<user_id
*> oper_lists
;
3974 cid_map_t
*capture_ids
;
3978 vec
<simplify
*> simplifiers
;
3979 vec
<predicate_id
*> user_predicates
;
3980 bool parsing_match_operand
;
3983 /* Lexing helpers. */
3985 /* Read the next non-whitespace token from R. */
3990 const cpp_token
*token
;
3993 token
= cpp_get_token (r
);
3995 while (token
->type
== CPP_PADDING
);
3999 /* Peek at the next non-whitespace token from R. */
4002 parser::peek (unsigned num
)
4004 const cpp_token
*token
;
4008 token
= cpp_peek_token (r
, i
++);
4010 while (token
->type
== CPP_PADDING
4012 /* If we peek at EOF this is a fatal error as it leaves the
4013 cpp_reader in unusable state. Assume we really wanted a
4014 token and thus this EOF is unexpected. */
4015 if (token
->type
== CPP_EOF
)
4016 fatal_at (token
, "unexpected end of file");
4020 /* Peek at the next identifier token (or return NULL if the next
4021 token is not an identifier or equal to ID if supplied). */
4024 parser::peek_ident (const char *id
, unsigned num
)
4026 const cpp_token
*token
= peek (num
);
4027 if (token
->type
!= CPP_NAME
)
4033 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4034 if (strcmp (id
, t
) == 0)
4040 /* Read the next token from R and assert it is of type TK. */
4043 parser::expect (enum cpp_ttype tk
)
4045 const cpp_token
*token
= next ();
4046 if (token
->type
!= tk
)
4047 fatal_at (token
, "expected %s, got %s",
4048 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
4053 /* Consume the next token from R and assert it is of type TK. */
4056 parser::eat_token (enum cpp_ttype tk
)
4061 /* Read the next token from R and assert it is of type CPP_STRING and
4062 return its value. */
4065 parser::get_string ()
4067 const cpp_token
*token
= expect (CPP_STRING
);
4068 return (const char *)token
->val
.str
.text
;
4071 /* Read the next token from R and assert it is of type CPP_NAME and
4072 return its value. */
4075 parser::get_ident ()
4077 const cpp_token
*token
= expect (CPP_NAME
);
4078 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
4081 /* Eat an identifier token with value S from R. */
4084 parser::eat_ident (const char *s
)
4086 const cpp_token
*token
= peek ();
4087 const char *t
= get_ident ();
4088 if (strcmp (s
, t
) != 0)
4089 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
4093 /* Read the next token from R and assert it is of type CPP_NUMBER and
4094 return its value. */
4097 parser::get_number ()
4099 const cpp_token
*token
= expect (CPP_NUMBER
);
4100 return (const char *)token
->val
.str
.text
;
4103 /* Return a capture ID that can be used internally. */
4106 parser::get_internal_capture_id ()
4108 unsigned newid
= capture_ids
->elements ();
4109 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4112 sprintf (id
, "__%u", newid
);
4113 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
4115 fatal ("reserved capture id '%s' already used", id
);
4119 /* Record an operator-list use for transparent for handling. */
4122 parser::record_operlist (location_t loc
, user_id
*p
)
4124 if (!oper_lists_set
->add (p
))
4126 if (!oper_lists
.is_empty ()
4127 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
4128 fatal_at (loc
, "User-defined operator list does not have the "
4129 "same number of entries as others used in the pattern");
4130 oper_lists
.safe_push (p
);
4134 /* Parse the operator ID, special-casing convert?, convert1? and
4138 parser::parse_operation ()
4140 const cpp_token
*id_tok
= peek ();
4141 const char *id
= get_ident ();
4142 const cpp_token
*token
= peek ();
4143 if (strcmp (id
, "convert0") == 0)
4144 fatal_at (id_tok
, "use 'convert?' here");
4145 else if (strcmp (id
, "view_convert0") == 0)
4146 fatal_at (id_tok
, "use 'view_convert?' here");
4147 if (token
->type
== CPP_QUERY
4148 && !(token
->flags
& PREV_WHITE
))
4150 if (strcmp (id
, "convert") == 0)
4152 else if (strcmp (id
, "convert1") == 0)
4154 else if (strcmp (id
, "convert2") == 0)
4156 else if (strcmp (id
, "view_convert") == 0)
4157 id
= "view_convert0";
4158 else if (strcmp (id
, "view_convert1") == 0)
4160 else if (strcmp (id
, "view_convert2") == 0)
4163 fatal_at (id_tok
, "non-convert operator conditionalized");
4165 if (!parsing_match_operand
)
4166 fatal_at (id_tok
, "conditional convert can only be used in "
4167 "match expression");
4168 eat_token (CPP_QUERY
);
4170 else if (strcmp (id
, "convert1") == 0
4171 || strcmp (id
, "convert2") == 0
4172 || strcmp (id
, "view_convert1") == 0
4173 || strcmp (id
, "view_convert2") == 0)
4174 fatal_at (id_tok
, "expected '?' after conditional operator");
4175 id_base
*op
= get_operator (id
);
4177 fatal_at (id_tok
, "unknown operator %s", id
);
4179 user_id
*p
= dyn_cast
<user_id
*> (op
);
4180 if (p
&& p
->is_oper_list
)
4182 if (active_fors
.length() == 0)
4183 record_operlist (id_tok
->src_loc
, p
);
4185 fatal_at (id_tok
, "operator-list %s cannot be expanded inside 'for'", id
);
4191 capture = '@'<number> */
4194 parser::parse_capture (operand
*op
, bool require_existing
)
4196 location_t src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
4197 const cpp_token
*token
= peek ();
4198 const char *id
= NULL
;
4199 bool value_match
= false;
4200 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4201 if (token
->type
== CPP_ATSIGN
4202 && ! (token
->flags
& PREV_WHITE
)
4203 && parsing_match_operand
)
4205 eat_token (CPP_ATSIGN
);
4209 if (token
->type
== CPP_NUMBER
)
4211 else if (token
->type
== CPP_NAME
)
4214 fatal_at (token
, "expected number or identifier");
4215 unsigned next_id
= capture_ids
->elements ();
4217 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
4220 if (require_existing
)
4221 fatal_at (src_loc
, "unknown capture id");
4224 return new capture (src_loc
, num
, op
, value_match
);
4227 /* Parse an expression
4228 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4231 parser::parse_expr ()
4233 const cpp_token
*token
= peek ();
4234 expr
*e
= new expr (parse_operation (), token
->src_loc
);
4237 bool is_commutative
= false;
4238 bool force_capture
= false;
4239 const char *expr_type
= NULL
;
4241 if (token
->type
== CPP_COLON
4242 && !(token
->flags
& PREV_WHITE
))
4244 eat_token (CPP_COLON
);
4246 if (token
->type
== CPP_NAME
4247 && !(token
->flags
& PREV_WHITE
))
4249 const char *s
= get_ident ();
4250 if (!parsing_match_operand
)
4260 = dyn_cast
<operator_id
*> (e
->operation
))
4262 if (!commutative_tree_code (p
->code
)
4263 && !comparison_code_p (p
->code
))
4264 fatal_at (token
, "operation is not commutative");
4266 else if (user_id
*p
= dyn_cast
<user_id
*> (e
->operation
))
4267 for (unsigned i
= 0;
4268 i
< p
->substitutes
.length (); ++i
)
4271 = dyn_cast
<operator_id
*> (p
->substitutes
[i
]))
4273 if (!commutative_tree_code (q
->code
)
4274 && !comparison_code_p (q
->code
))
4275 fatal_at (token
, "operation %s is not "
4276 "commutative", q
->id
);
4279 is_commutative
= true;
4281 else if (*sp
== 'C')
4282 is_commutative
= true;
4283 else if (*sp
== 's')
4285 e
->force_single_use
= true;
4286 force_capture
= true;
4289 fatal_at (token
, "flag %c not recognized", *sp
);
4296 fatal_at (token
, "expected flag or type specifying identifier");
4299 if (token
->type
== CPP_ATSIGN
4300 && !(token
->flags
& PREV_WHITE
))
4301 op
= parse_capture (e
, false);
4302 else if (force_capture
)
4304 unsigned num
= get_internal_capture_id ();
4305 op
= new capture (token
->src_loc
, num
, e
, false);
4311 const cpp_token
*token
= peek ();
4312 if (token
->type
== CPP_CLOSE_PAREN
)
4314 if (e
->operation
->nargs
!= -1
4315 && e
->operation
->nargs
!= (int) e
->ops
.length ())
4316 fatal_at (token
, "'%s' expects %u operands, not %u",
4317 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
4320 if (e
->ops
.length () == 2
4321 || commutative_op (e
->operation
) >= 0)
4322 e
->is_commutative
= true;
4324 fatal_at (token
, "only binary operators or functions with "
4325 "two arguments can be marked commutative, "
4326 "unless the operation is known to be inherently "
4329 e
->expr_type
= expr_type
;
4332 else if (!(token
->flags
& PREV_WHITE
))
4333 fatal_at (token
, "expected expression operand");
4335 e
->append_op (parse_op ());
4340 /* Lex native C code delimited by START recording the preprocessing tokens
4341 for later processing.
4342 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4345 parser::parse_c_expr (cpp_ttype start
)
4347 const cpp_token
*token
;
4350 vec
<cpp_token
> code
= vNULL
;
4351 unsigned nr_stmts
= 0;
4352 location_t loc
= eat_token (start
)->src_loc
;
4353 if (start
== CPP_OPEN_PAREN
)
4354 end
= CPP_CLOSE_PAREN
;
4355 else if (start
== CPP_OPEN_BRACE
)
4356 end
= CPP_CLOSE_BRACE
;
4364 /* Count brace pairs to find the end of the expr to match. */
4365 if (token
->type
== start
)
4367 else if (token
->type
== end
4370 else if (token
->type
== CPP_EOF
)
4371 fatal_at (token
, "unexpected end of file");
4373 /* This is a lame way of counting the number of statements. */
4374 if (token
->type
== CPP_SEMICOLON
)
4377 /* If this is possibly a user-defined identifier mark it used. */
4378 if (token
->type
== CPP_NAME
)
4380 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
4381 (token
->val
.node
.node
)->ident
.str
);
4383 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
4384 record_operlist (token
->src_loc
, p
);
4387 /* Record the token. */
4388 code
.safe_push (*token
);
4391 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
4394 /* Parse an operand which is either an expression, a predicate or
4395 a standalone capture.
4396 op = predicate | expr | c_expr | capture */
4401 const cpp_token
*token
= peek ();
4402 class operand
*op
= NULL
;
4403 if (token
->type
== CPP_OPEN_PAREN
)
4405 eat_token (CPP_OPEN_PAREN
);
4407 eat_token (CPP_CLOSE_PAREN
);
4409 else if (token
->type
== CPP_OPEN_BRACE
)
4411 op
= parse_c_expr (CPP_OPEN_BRACE
);
4415 /* Remaining ops are either empty or predicates */
4416 if (token
->type
== CPP_NAME
)
4418 const char *id
= get_ident ();
4419 id_base
*opr
= get_operator (id
);
4421 fatal_at (token
, "expected predicate name");
4422 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
4424 if (code
->nargs
!= 0)
4425 fatal_at (token
, "using an operator with operands as predicate");
4426 /* Parse the zero-operand operator "predicates" as
4428 op
= new expr (opr
, token
->src_loc
);
4430 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
4432 if (code
->nargs
!= 0)
4433 fatal_at (token
, "using an operator with operands as predicate");
4434 /* Parse the zero-operand operator "predicates" as
4436 op
= new expr (opr
, token
->src_loc
);
4438 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
4439 op
= new predicate (p
, token
->src_loc
);
4441 fatal_at (token
, "using an unsupported operator as predicate");
4442 if (!parsing_match_operand
)
4443 fatal_at (token
, "predicates are only allowed in match expression");
4445 if (token
->flags
& PREV_WHITE
)
4448 else if (token
->type
!= CPP_COLON
4449 && token
->type
!= CPP_ATSIGN
)
4450 fatal_at (token
, "expected expression or predicate");
4451 /* optionally followed by a capture and a predicate. */
4452 if (token
->type
== CPP_COLON
)
4453 fatal_at (token
, "not implemented: predicate on leaf operand");
4454 if (token
->type
== CPP_ATSIGN
)
4455 op
= parse_capture (op
, !parsing_match_operand
);
4461 /* Create a new simplify from the current parsing state and MATCH,
4462 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4465 parser::push_simplify (simplify::simplify_kind kind
,
4466 vec
<simplify
*>& simplifiers
,
4467 operand
*match
, operand
*result
)
4469 /* Build and push a temporary for operator list uses in expressions. */
4470 if (!oper_lists
.is_empty ())
4471 active_fors
.safe_push (oper_lists
);
4473 simplifiers
.safe_push
4474 (new simplify (kind
, last_id
++, match
, result
,
4475 active_fors
.copy (), capture_ids
));
4477 if (!oper_lists
.is_empty ())
4482 <result-op> = <op> | <if> | <with>
4483 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4484 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4488 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4490 const cpp_token
*token
= peek ();
4491 if (token
->type
!= CPP_OPEN_PAREN
)
4494 eat_token (CPP_OPEN_PAREN
);
4495 if (peek_ident ("if"))
4498 if_expr
*ife
= new if_expr (token
->src_loc
);
4499 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4500 if (peek ()->type
== CPP_OPEN_PAREN
)
4502 ife
->trueexpr
= parse_result (result
, matcher
);
4503 if (peek ()->type
== CPP_OPEN_PAREN
)
4504 ife
->falseexpr
= parse_result (result
, matcher
);
4505 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4506 ife
->falseexpr
= parse_op ();
4508 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4510 ife
->trueexpr
= parse_op ();
4511 if (peek ()->type
== CPP_OPEN_PAREN
)
4512 ife
->falseexpr
= parse_result (result
, matcher
);
4513 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4514 ife
->falseexpr
= parse_op ();
4516 /* If this if is immediately closed then it contains a
4517 manual matcher or is part of a predicate definition. */
4518 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4521 fatal_at (peek (), "manual transform not implemented");
4522 ife
->trueexpr
= result
;
4524 eat_token (CPP_CLOSE_PAREN
);
4527 else if (peek_ident ("with"))
4530 with_expr
*withe
= new with_expr (token
->src_loc
);
4531 /* Parse (with c-expr expr) as (if-with (true) expr). */
4532 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4533 withe
->with
->nr_stmts
= 0;
4534 withe
->subexpr
= parse_result (result
, matcher
);
4535 eat_token (CPP_CLOSE_PAREN
);
4538 else if (peek_ident ("switch"))
4540 token
= eat_ident ("switch");
4541 location_t ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4543 if_expr
*ife
= new if_expr (ifloc
);
4545 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4546 if (peek ()->type
== CPP_OPEN_PAREN
)
4547 ife
->trueexpr
= parse_result (result
, matcher
);
4549 ife
->trueexpr
= parse_op ();
4550 eat_token (CPP_CLOSE_PAREN
);
4551 if (peek ()->type
!= CPP_OPEN_PAREN
4552 || !peek_ident ("if", 2))
4553 fatal_at (token
, "switch can be implemented with a single if");
4554 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4556 if (peek ()->type
== CPP_OPEN_PAREN
)
4558 if (peek_ident ("if", 2))
4560 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4562 ife
->falseexpr
= new if_expr (ifloc
);
4563 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4564 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4565 if (peek ()->type
== CPP_OPEN_PAREN
)
4566 ife
->trueexpr
= parse_result (result
, matcher
);
4568 ife
->trueexpr
= parse_op ();
4569 eat_token (CPP_CLOSE_PAREN
);
4573 /* switch default clause */
4574 ife
->falseexpr
= parse_result (result
, matcher
);
4575 eat_token (CPP_CLOSE_PAREN
);
4581 /* switch default clause */
4582 ife
->falseexpr
= parse_op ();
4583 eat_token (CPP_CLOSE_PAREN
);
4587 eat_token (CPP_CLOSE_PAREN
);
4592 operand
*op
= result
;
4595 eat_token (CPP_CLOSE_PAREN
);
4601 simplify = 'simplify' <expr> <result-op>
4603 match = 'match' <ident> <expr> [<result-op>]
4604 and fill SIMPLIFIERS with the results. */
4607 parser::parse_simplify (simplify::simplify_kind kind
,
4608 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4611 /* Reset the capture map. */
4613 capture_ids
= new cid_map_t
;
4614 /* Reset oper_lists and set. */
4615 hash_set
<user_id
*> olist
;
4616 oper_lists_set
= &olist
;
4619 const cpp_token
*loc
= peek ();
4620 parsing_match_operand
= true;
4621 class operand
*match
= parse_op ();
4622 finish_match_operand (match
);
4623 parsing_match_operand
= false;
4624 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4625 fatal_at (loc
, "outermost expression cannot be captured");
4626 if (match
->type
== operand::OP_EXPR
4627 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4628 fatal_at (loc
, "outermost expression cannot be a predicate");
4630 /* Splice active_ifs onto result and continue parsing the
4632 if_expr
*active_if
= NULL
;
4633 for (int i
= active_ifs
.length (); i
> 0; --i
)
4635 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4636 ifc
->cond
= active_ifs
[i
-1];
4637 ifc
->trueexpr
= active_if
;
4640 if_expr
*outermost_if
= active_if
;
4641 while (active_if
&& active_if
->trueexpr
)
4642 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4644 const cpp_token
*token
= peek ();
4646 /* If this if is immediately closed then it is part of a predicate
4647 definition. Push it. */
4648 if (token
->type
== CPP_CLOSE_PAREN
)
4651 fatal_at (token
, "expected transform expression");
4654 active_if
->trueexpr
= result
;
4655 result
= outermost_if
;
4657 push_simplify (kind
, simplifiers
, match
, result
);
4661 operand
*tem
= parse_result (result
, matcher
);
4664 active_if
->trueexpr
= tem
;
4665 result
= outermost_if
;
4670 push_simplify (kind
, simplifiers
, match
, result
);
4673 /* Parsing of the outer control structures. */
4675 /* Parse a for expression
4676 for = '(' 'for' <subst>... <pattern> ')'
4677 subst = <ident> '(' <ident>... ')' */
4680 parser::parse_for (location_t
)
4682 auto_vec
<const cpp_token
*> user_id_tokens
;
4683 vec
<user_id
*> user_ids
= vNULL
;
4684 const cpp_token
*token
;
4685 unsigned min_n_opers
= 0, max_n_opers
= 0;
4690 if (token
->type
!= CPP_NAME
)
4693 /* Insert the user defined operators into the operator hash. */
4694 const char *id
= get_ident ();
4695 if (get_operator (id
, true) != NULL
)
4696 fatal_at (token
, "operator already defined");
4697 user_id
*op
= new user_id (id
);
4698 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4700 user_ids
.safe_push (op
);
4701 user_id_tokens
.safe_push (token
);
4703 eat_token (CPP_OPEN_PAREN
);
4706 while ((token
= peek_ident ()) != 0)
4708 const char *oper
= get_ident ();
4709 id_base
*idb
= get_operator (oper
, true);
4711 fatal_at (token
, "no such operator '%s'", oper
);
4712 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4713 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4714 || *idb
== VIEW_CONVERT2
)
4715 fatal_at (token
, "conditional operators cannot be used inside for");
4719 else if (idb
->nargs
== -1)
4721 else if (idb
->nargs
!= arity
)
4722 fatal_at (token
, "operator '%s' with arity %d does not match "
4723 "others with arity %d", oper
, idb
->nargs
, arity
);
4725 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4728 if (p
->is_oper_list
)
4729 op
->substitutes
.safe_splice (p
->substitutes
);
4731 fatal_at (token
, "iterator cannot be used as operator-list");
4734 op
->substitutes
.safe_push (idb
);
4737 token
= expect (CPP_CLOSE_PAREN
);
4739 unsigned nsubstitutes
= op
->substitutes
.length ();
4740 if (nsubstitutes
== 0)
4741 fatal_at (token
, "A user-defined operator must have at least "
4742 "one substitution");
4743 if (max_n_opers
== 0)
4745 min_n_opers
= nsubstitutes
;
4746 max_n_opers
= nsubstitutes
;
4750 if (nsubstitutes
% min_n_opers
!= 0
4751 && min_n_opers
% nsubstitutes
!= 0)
4752 fatal_at (token
, "All user-defined identifiers must have a "
4753 "multiple number of operator substitutions of the "
4754 "smallest number of substitutions");
4755 if (nsubstitutes
< min_n_opers
)
4756 min_n_opers
= nsubstitutes
;
4757 else if (nsubstitutes
> max_n_opers
)
4758 max_n_opers
= nsubstitutes
;
4762 unsigned n_ids
= user_ids
.length ();
4764 fatal_at (token
, "for requires at least one user-defined identifier");
4767 if (token
->type
== CPP_CLOSE_PAREN
)
4768 fatal_at (token
, "no pattern defined in for");
4770 active_fors
.safe_push (user_ids
);
4774 if (token
->type
== CPP_CLOSE_PAREN
)
4780 /* Remove user-defined operators from the hash again. */
4781 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4783 if (!user_ids
[i
]->used
)
4784 warning_at (user_id_tokens
[i
],
4785 "operator %s defined but not used", user_ids
[i
]->id
);
4786 operators
->remove_elt (user_ids
[i
]);
4790 /* Parse an identifier associated with a list of operators.
4791 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4794 parser::parse_operator_list (location_t
)
4796 const cpp_token
*token
= peek ();
4797 const char *id
= get_ident ();
4799 if (get_operator (id
, true) != 0)
4800 fatal_at (token
, "operator %s already defined", id
);
4802 user_id
*op
= new user_id (id
, true);
4805 while ((token
= peek_ident ()) != 0)
4808 const char *oper
= get_ident ();
4809 id_base
*idb
= get_operator (oper
, true);
4812 fatal_at (token
, "no such operator '%s'", oper
);
4816 else if (idb
->nargs
== -1)
4818 else if (arity
!= idb
->nargs
)
4819 fatal_at (token
, "operator '%s' with arity %d does not match "
4820 "others with arity %d", oper
, idb
->nargs
, arity
);
4822 /* We allow composition of multiple operator lists. */
4823 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4824 op
->substitutes
.safe_splice (p
->substitutes
);
4826 op
->substitutes
.safe_push (idb
);
4829 // Check that there is no junk after id-list
4831 if (token
->type
!= CPP_CLOSE_PAREN
)
4832 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4834 if (op
->substitutes
.length () == 0)
4835 fatal_at (token
, "operator-list cannot be empty");
4838 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4842 /* Parse an outer if expression.
4843 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4846 parser::parse_if (location_t
)
4848 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4850 const cpp_token
*token
= peek ();
4851 if (token
->type
== CPP_CLOSE_PAREN
)
4852 fatal_at (token
, "no pattern defined in if");
4854 active_ifs
.safe_push (ifexpr
);
4857 const cpp_token
*token
= peek ();
4858 if (token
->type
== CPP_CLOSE_PAREN
)
4866 /* Parse a list of predefined predicate identifiers.
4867 preds = '(' 'define_predicates' <ident>... ')' */
4870 parser::parse_predicates (location_t
)
4874 const cpp_token
*token
= peek ();
4875 if (token
->type
!= CPP_NAME
)
4878 add_predicate (get_ident ());
4883 /* Parse outer control structures.
4884 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4887 parser::parse_pattern ()
4889 /* All clauses start with '('. */
4890 eat_token (CPP_OPEN_PAREN
);
4891 const cpp_token
*token
= peek ();
4892 const char *id
= get_ident ();
4893 if (strcmp (id
, "simplify") == 0)
4895 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4898 else if (strcmp (id
, "match") == 0)
4900 bool with_args
= false;
4901 location_t e_loc
= peek ()->src_loc
;
4902 if (peek ()->type
== CPP_OPEN_PAREN
)
4904 eat_token (CPP_OPEN_PAREN
);
4907 const char *name
= get_ident ();
4908 id_base
*id
= get_operator (name
);
4912 p
= add_predicate (name
);
4913 user_predicates
.safe_push (p
);
4915 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4918 fatal_at (token
, "cannot add a match to a non-predicate ID");
4919 /* Parse (match <id> <arg>... (match-expr)) here. */
4923 capture_ids
= new cid_map_t
;
4924 e
= new expr (p
, e_loc
);
4925 while (peek ()->type
== CPP_ATSIGN
)
4926 e
->append_op (parse_capture (NULL
, false));
4927 eat_token (CPP_CLOSE_PAREN
);
4930 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4931 || (!e
&& p
->nargs
!= 0)))
4932 fatal_at (token
, "non-matching number of match operands");
4933 p
->nargs
= e
? e
->ops
.length () : 0;
4934 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4937 else if (strcmp (id
, "for") == 0)
4938 parse_for (token
->src_loc
);
4939 else if (strcmp (id
, "if") == 0)
4940 parse_if (token
->src_loc
);
4941 else if (strcmp (id
, "define_predicates") == 0)
4943 if (active_ifs
.length () > 0
4944 || active_fors
.length () > 0)
4945 fatal_at (token
, "define_predicates inside if or for is not supported");
4946 parse_predicates (token
->src_loc
);
4948 else if (strcmp (id
, "define_operator_list") == 0)
4950 if (active_ifs
.length () > 0
4951 || active_fors
.length () > 0)
4952 fatal_at (token
, "operator-list inside if or for is not supported");
4953 parse_operator_list (token
->src_loc
);
4956 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4957 active_ifs
.length () == 0 && active_fors
.length () == 0
4958 ? "'define_predicates', " : "");
4960 eat_token (CPP_CLOSE_PAREN
);
4963 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4967 walk_captures (operand
*op
, vec
<vec
<capture
*> > cpts
)
4972 if (capture
*c
= dyn_cast
<capture
*> (op
))
4974 cpts
[c
->where
].safe_push (c
);
4975 walk_captures (c
->what
, cpts
);
4977 else if (expr
*e
= dyn_cast
<expr
*> (op
))
4978 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
4979 walk_captures (e
->ops
[i
], cpts
);
4982 /* Finish up OP which is a match operand. */
4985 parser::finish_match_operand (operand
*op
)
4987 /* Look for matching captures, diagnose mis-uses of @@ and apply
4988 early lowering and distribution of value_match. */
4989 auto_vec
<vec
<capture
*> > cpts
;
4990 cpts
.safe_grow_cleared (capture_ids
->elements ());
4991 walk_captures (op
, cpts
);
4992 for (unsigned i
= 0; i
< cpts
.length (); ++i
)
4994 capture
*value_match
= NULL
;
4995 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
4997 if (cpts
[i
][j
]->value_match
)
5000 fatal_at (cpts
[i
][j
]->location
, "duplicate @@");
5001 value_match
= cpts
[i
][j
];
5004 if (cpts
[i
].length () == 1 && value_match
)
5005 fatal_at (value_match
->location
, "@@ without a matching capture");
5008 /* Duplicate prevailing capture with the existing ID, create
5009 a fake ID and rewrite all captures to use it. This turns
5010 @@1 into @__<newid>@1 and @1 into @__<newid>. */
5011 value_match
->what
= new capture (value_match
->location
,
5013 value_match
->what
, false);
5014 /* Create a fake ID and rewrite all captures to use it. */
5015 unsigned newid
= get_internal_capture_id ();
5016 for (unsigned j
= 0; j
< cpts
[i
].length (); ++j
)
5018 cpts
[i
][j
]->where
= newid
;
5019 cpts
[i
][j
]->value_match
= true;
5026 /* Main entry of the parser. Repeatedly parse outer control structures. */
5028 parser::parser (cpp_reader
*r_
)
5032 active_fors
= vNULL
;
5033 simplifiers
= vNULL
;
5034 oper_lists_set
= NULL
;
5037 user_predicates
= vNULL
;
5038 parsing_match_operand
= false;
5041 const cpp_token
*token
= next ();
5042 while (token
->type
!= CPP_EOF
)
5044 _cpp_backup_tokens (r
, 1);
5051 /* Helper for the linemap code. */
5054 round_alloc_size (size_t s
)
5060 /* The genmatch generator progam. It reads from a pattern description
5061 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
5064 main (int argc
, char **argv
)
5068 progname
= "genmatch";
5074 char *input
= argv
[argc
-1];
5075 for (int i
= 1; i
< argc
- 1; ++i
)
5077 if (strcmp (argv
[i
], "--gimple") == 0)
5079 else if (strcmp (argv
[i
], "--generic") == 0)
5081 else if (strcmp (argv
[i
], "-v") == 0)
5083 else if (strcmp (argv
[i
], "-vv") == 0)
5087 fprintf (stderr
, "Usage: genmatch "
5088 "[--gimple] [--generic] [-v[v]] input\n");
5093 line_table
= XCNEW (class line_maps
);
5094 linemap_init (line_table
, 0);
5095 line_table
->reallocator
= xrealloc
;
5096 line_table
->round_alloc_size
= round_alloc_size
;
5098 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
5099 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
5100 cb
->diagnostic
= diagnostic_cb
;
5102 /* Add the build directory to the #include "" search path. */
5103 cpp_dir
*dir
= XCNEW (cpp_dir
);
5104 dir
->name
= getpwd ();
5106 dir
->name
= ASTRDUP (".");
5107 cpp_set_include_chains (r
, dir
, NULL
, false);
5109 if (!cpp_read_main_file (r
, input
))
5111 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
5112 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
5114 null_id
= new id_base (id_base::NULL_ID
, "null");
5116 /* Pre-seed operators. */
5117 operators
= new hash_table
<id_base
> (1024);
5118 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5119 add_operator (SYM, # SYM, # TYPE, NARGS);
5120 #define END_OF_BASE_TREE_CODES
5122 add_operator (CONVERT0
, "convert0", "tcc_unary", 1);
5123 add_operator (CONVERT1
, "convert1", "tcc_unary", 1);
5124 add_operator (CONVERT2
, "convert2", "tcc_unary", 1);
5125 add_operator (VIEW_CONVERT0
, "view_convert0", "tcc_unary", 1);
5126 add_operator (VIEW_CONVERT1
, "view_convert1", "tcc_unary", 1);
5127 add_operator (VIEW_CONVERT2
, "view_convert2", "tcc_unary", 1);
5128 #undef END_OF_BASE_TREE_CODES
5131 /* Pre-seed builtin functions.
5132 ??? Cannot use N (name) as that is targetm.emultls.get_address
5133 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5134 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5135 add_function (ENUM, "CFN_" # ENUM);
5136 #include "builtins.def"
5138 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5139 add_function (IFN_##CODE, "CFN_" #CODE);
5140 #include "internal-fn.def"
5146 write_header (stdout
, "gimple-match-head.c");
5148 write_header (stdout
, "generic-match-head.c");
5150 /* Go over all predicates defined with patterns and perform
5151 lowering and code generation. */
5152 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
5154 predicate_id
*pred
= p
.user_predicates
[i
];
5155 lower (pred
->matchers
, gimple
);
5158 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5159 print_matches (pred
->matchers
[i
]);
5162 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
5163 dt
.insert (pred
->matchers
[i
], i
);
5168 write_predicate (stdout
, pred
, dt
, gimple
);
5171 /* Lower the main simplifiers and generate code for them. */
5172 lower (p
.simplifiers
, gimple
);
5175 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5176 print_matches (p
.simplifiers
[i
]);
5179 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
5180 dt
.insert (p
.simplifiers
[i
], i
);
5185 dt
.gen (stdout
, gimple
);
5188 cpp_finish (r
, NULL
);