1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
4 Copyright (C) 2014-2015 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
27 #include "coretypes.h"
30 #include "hash-table.h"
35 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
36 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
37 size_t, size_t MEM_STAT_DECL
)
41 void ggc_free (void *)
48 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
54 static struct line_maps
*line_table
;
57 #if GCC_VERSION >= 4001
58 __attribute__((format (printf
, 6, 0)))
60 error_cb (cpp_reader
*, int errtype
, int, source_location location
,
61 unsigned int, const char *msg
, va_list *ap
)
63 const line_map_ordinary
*map
;
64 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
65 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
66 fprintf (stderr
, "%s:%d:%d %s: ", loc
.file
, loc
.line
, loc
.column
,
67 (errtype
== CPP_DL_WARNING
) ? "warning" : "error");
68 vfprintf (stderr
, msg
, *ap
);
69 fprintf (stderr
, "\n");
70 FILE *f
= fopen (loc
.file
, "r");
76 if (!fgets (buf
, 128, f
))
78 if (buf
[strlen (buf
) - 1] != '\n')
85 fprintf (stderr
, "%s", buf
);
86 for (int i
= 0; i
< loc
.column
- 1; ++i
)
94 if (errtype
== CPP_DL_FATAL
)
100 #if GCC_VERSION >= 4001
101 __attribute__((format (printf
, 2, 3)))
103 fatal_at (const cpp_token
*tk
, const char *msg
, ...)
107 error_cb (NULL
, CPP_DL_FATAL
, 0, tk
->src_loc
, 0, msg
, &ap
);
112 #if GCC_VERSION >= 4001
113 __attribute__((format (printf
, 2, 3)))
115 fatal_at (source_location loc
, const char *msg
, ...)
119 error_cb (NULL
, CPP_DL_FATAL
, 0, loc
, 0, msg
, &ap
);
124 #if GCC_VERSION >= 4001
125 __attribute__((format (printf
, 2, 3)))
127 warning_at (const cpp_token
*tk
, const char *msg
, ...)
131 error_cb (NULL
, CPP_DL_WARNING
, 0, tk
->src_loc
, 0, msg
, &ap
);
136 #if GCC_VERSION >= 4001
137 __attribute__((format (printf
, 2, 3)))
139 warning_at (source_location loc
, const char *msg
, ...)
143 error_cb (NULL
, CPP_DL_WARNING
, 0, loc
, 0, msg
, &ap
);
147 /* Like fprintf, but print INDENT spaces at the beginning. */
150 #if GCC_VERSION >= 4001
151 __attribute__((format (printf
, 3, 4)))
153 fprintf_indent (FILE *f
, unsigned int indent
, const char *format
, ...)
156 for (; indent
>= 8; indent
-= 8)
158 fprintf (f
, "%*s", indent
, "");
159 va_start (ap
, format
);
160 vfprintf (f
, format
, ap
);
165 output_line_directive (FILE *f
, source_location location
,
166 bool dumpfile
= false)
168 const line_map_ordinary
*map
;
169 linemap_resolve_location (line_table
, location
, LRK_SPELLING_LOCATION
, &map
);
170 expanded_location loc
= linemap_expand_location (line_table
, map
, location
);
173 /* When writing to a dumpfile only dump the filename. */
174 const char *file
= strrchr (loc
.file
, DIR_SEPARATOR
);
179 fprintf (f
, "%s:%d", file
, loc
.line
);
182 /* Other gen programs really output line directives here, at least for
183 development it's right now more convenient to have line information
184 from the generated file. Still keep the directives as comment for now
185 to easily back-point to the meta-description. */
186 fprintf (f
, "/* #line %d \"%s\" */\n", loc
.line
, loc
.file
);
190 /* Pull in tree codes and builtin function codes from their
193 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
206 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
207 enum built_in_function
{
208 #include "builtins.def"
213 /* Return true if CODE represents a commutative tree code. Otherwise
216 commutative_tree_code (enum tree_code code
)
222 case MULT_HIGHPART_EXPR
:
237 case WIDEN_MULT_EXPR
:
238 case VEC_WIDEN_MULT_HI_EXPR
:
239 case VEC_WIDEN_MULT_LO_EXPR
:
240 case VEC_WIDEN_MULT_EVEN_EXPR
:
241 case VEC_WIDEN_MULT_ODD_EXPR
:
250 /* Return true if CODE represents a ternary tree code for which the
251 first two operands are commutative. Otherwise return false. */
253 commutative_ternary_tree_code (enum tree_code code
)
257 case WIDEN_MULT_PLUS_EXPR
:
258 case WIDEN_MULT_MINUS_EXPR
:
270 /* Base class for all identifiers the parser knows. */
272 struct id_base
: nofree_ptr_hash
<id_base
>
274 enum id_kind
{ CODE
, FN
, PREDICATE
, USER
} kind
;
276 id_base (id_kind
, const char *, int = -1);
282 /* hash_table support. */
283 static inline hashval_t
hash (const id_base
*);
284 static inline int equal (const id_base
*, const id_base
*);
288 id_base::hash (const id_base
*op
)
294 id_base::equal (const id_base
*op1
,
297 return (op1
->hashval
== op2
->hashval
298 && strcmp (op1
->id
, op2
->id
) == 0);
301 /* Hashtable of known pattern operators. This is pre-seeded from
302 all known tree codes and all known builtin function ids. */
303 static hash_table
<id_base
> *operators
;
305 id_base::id_base (id_kind kind_
, const char *id_
, int nargs_
)
310 hashval
= htab_hash_string (id
);
313 /* Identifier that maps to a tree code. */
315 struct operator_id
: public id_base
317 operator_id (enum tree_code code_
, const char *id_
, unsigned nargs_
,
319 : id_base (id_base::CODE
, id_
, nargs_
), code (code_
), tcc (tcc_
) {}
324 /* Identifier that maps to a builtin function code. */
326 struct fn_id
: public id_base
328 fn_id (enum built_in_function fn_
, const char *id_
)
329 : id_base (id_base::FN
, id_
), fn (fn_
) {}
330 enum built_in_function fn
;
335 /* Identifier that maps to a user-defined predicate. */
337 struct predicate_id
: public id_base
339 predicate_id (const char *id_
)
340 : id_base (id_base::PREDICATE
, id_
), matchers (vNULL
) {}
341 vec
<simplify
*> matchers
;
344 /* Identifier that maps to a operator defined by a 'for' directive. */
346 struct user_id
: public id_base
348 user_id (const char *id_
, bool is_oper_list_
= false)
349 : id_base (id_base::USER
, id_
), substitutes (vNULL
),
350 used (false), is_oper_list (is_oper_list_
) {}
351 vec
<id_base
*> substitutes
;
359 is_a_helper
<fn_id
*>::test (id_base
*id
)
361 return id
->kind
== id_base::FN
;
367 is_a_helper
<operator_id
*>::test (id_base
*id
)
369 return id
->kind
== id_base::CODE
;
375 is_a_helper
<predicate_id
*>::test (id_base
*id
)
377 return id
->kind
== id_base::PREDICATE
;
383 is_a_helper
<user_id
*>::test (id_base
*id
)
385 return id
->kind
== id_base::USER
;
388 /* Add a predicate identifier to the hash. */
390 static predicate_id
*
391 add_predicate (const char *id
)
393 predicate_id
*p
= new predicate_id (id
);
394 id_base
**slot
= operators
->find_slot_with_hash (p
, p
->hashval
, INSERT
);
396 fatal ("duplicate id definition");
401 /* Add a tree code identifier to the hash. */
404 add_operator (enum tree_code code
, const char *id
,
405 const char *tcc
, unsigned nargs
)
407 if (strcmp (tcc
, "tcc_unary") != 0
408 && strcmp (tcc
, "tcc_binary") != 0
409 && strcmp (tcc
, "tcc_comparison") != 0
410 && strcmp (tcc
, "tcc_expression") != 0
411 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
412 && strcmp (tcc
, "tcc_reference") != 0
413 /* To have INTEGER_CST and friends as "predicate operators". */
414 && strcmp (tcc
, "tcc_constant") != 0
415 /* And allow CONSTRUCTOR for vector initializers. */
416 && !(code
== CONSTRUCTOR
)
417 /* Allow SSA_NAME as predicate operator. */
418 && !(code
== SSA_NAME
))
420 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
421 if (code
== ADDR_EXPR
)
423 operator_id
*op
= new operator_id (code
, id
, nargs
, tcc
);
424 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
426 fatal ("duplicate id definition");
430 /* Add a builtin identifier to the hash. */
433 add_builtin (enum built_in_function code
, const char *id
)
435 fn_id
*fn
= new fn_id (code
, id
);
436 id_base
**slot
= operators
->find_slot_with_hash (fn
, fn
->hashval
, INSERT
);
438 fatal ("duplicate id definition");
442 /* Helper for easy comparing ID with tree code CODE. */
445 operator==(id_base
&id
, enum tree_code code
)
447 if (operator_id
*oid
= dyn_cast
<operator_id
*> (&id
))
448 return oid
->code
== code
;
452 /* Lookup the identifier ID. */
455 get_operator (const char *id
)
457 id_base
tem (id_base::CODE
, id
);
459 id_base
*op
= operators
->find_with_hash (&tem
, tem
.hashval
);
462 /* If this is a user-defined identifier track whether it was used. */
463 if (user_id
*uid
= dyn_cast
<user_id
*> (op
))
468 /* Try all-uppercase. */
469 char *id2
= xstrdup (id
);
470 for (unsigned i
= 0; i
< strlen (id2
); ++i
)
471 id2
[i
] = TOUPPER (id2
[i
]);
472 new (&tem
) id_base (id_base::CODE
, id2
);
473 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
480 /* Try _EXPR appended. */
481 id2
= (char *)xrealloc (id2
, strlen (id2
) + sizeof ("_EXPR") + 1);
482 strcat (id2
, "_EXPR");
483 new (&tem
) id_base (id_base::CODE
, id2
);
484 op
= operators
->find_with_hash (&tem
, tem
.hashval
);
494 typedef hash_map
<nofree_string_hash
, unsigned> cid_map_t
;
497 /* The AST produced by parsing of the pattern definitions. */
502 /* The base class for operands. */
505 enum op_type
{ OP_PREDICATE
, OP_EXPR
, OP_CAPTURE
, OP_C_EXPR
, OP_IF
, OP_WITH
};
506 operand (enum op_type type_
, source_location loc_
)
507 : type (type_
), location (loc_
) {}
509 source_location location
;
510 virtual void gen_transform (FILE *, int, const char *, bool, int,
511 const char *, capture_info
*,
514 { gcc_unreachable (); }
517 /* A predicate operand. Predicates are leafs in the AST. */
519 struct predicate
: public operand
521 predicate (predicate_id
*p_
, source_location loc
)
522 : operand (OP_PREDICATE
, loc
), p (p_
) {}
526 /* An operand that constitutes an expression. Expressions include
527 function calls and user-defined predicate invocations. */
529 struct expr
: public operand
531 expr (id_base
*operation_
, source_location loc
, bool is_commutative_
= false)
532 : operand (OP_EXPR
, loc
), operation (operation_
),
533 ops (vNULL
), expr_type (NULL
), is_commutative (is_commutative_
),
534 is_generic (false), force_single_use (false) {}
536 : operand (OP_EXPR
, e
->location
), operation (e
->operation
),
537 ops (vNULL
), expr_type (e
->expr_type
), is_commutative (e
->is_commutative
),
538 is_generic (e
->is_generic
), force_single_use (e
->force_single_use
) {}
539 void append_op (operand
*op
) { ops
.safe_push (op
); }
540 /* The operator and its operands. */
543 /* An explicitely specified type - used exclusively for conversions. */
544 const char *expr_type
;
545 /* Whether the operation is to be applied commutatively. This is
546 later lowered to two separate patterns. */
548 /* Whether the expression is expected to be in GENERIC form. */
550 /* Whether pushing any stmt to the sequence should be conditional
551 on this expression having a single-use. */
552 bool force_single_use
;
553 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
554 const char *, capture_info
*,
555 dt_operand
** = 0, bool = true);
558 /* An operator that is represented by native C code. This is always
559 a leaf operand in the AST. This class is also used to represent
560 the code to be generated for 'if' and 'with' expressions. */
562 struct c_expr
: public operand
564 /* A mapping of an identifier and its replacement. Used to apply
569 id_tab (const char *id_
, const char *oper_
): id (id_
), oper (oper_
) {}
572 c_expr (cpp_reader
*r_
, source_location loc
,
573 vec
<cpp_token
> code_
, unsigned nr_stmts_
,
574 vec
<id_tab
> ids_
, cid_map_t
*capture_ids_
)
575 : operand (OP_C_EXPR
, loc
), r (r_
), code (code_
),
576 capture_ids (capture_ids_
), nr_stmts (nr_stmts_
), ids (ids_
) {}
577 /* cpplib tokens and state to transform this back to source. */
580 cid_map_t
*capture_ids
;
581 /* The number of statements parsed (well, the number of ';'s). */
583 /* The identifier replacement vector. */
585 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
586 const char *, capture_info
*,
587 dt_operand
** = 0, bool = true);
590 /* A wrapper around another operand that captures its value. */
592 struct capture
: public operand
594 capture (source_location loc
, unsigned where_
, operand
*what_
)
595 : operand (OP_CAPTURE
, loc
), where (where_
), what (what_
) {}
596 /* Identifier index for the value. */
598 /* The captured value. */
600 virtual void gen_transform (FILE *f
, int, const char *, bool, int,
601 const char *, capture_info
*,
602 dt_operand
** = 0, bool = true);
607 struct if_expr
: public operand
609 if_expr (source_location loc
)
610 : operand (OP_IF
, loc
), cond (NULL
), trueexpr (NULL
), falseexpr (NULL
) {}
616 /* with expression. */
618 struct with_expr
: public operand
620 with_expr (source_location loc
)
621 : operand (OP_WITH
, loc
), with (NULL
), subexpr (NULL
) {}
629 is_a_helper
<capture
*>::test (operand
*op
)
631 return op
->type
== operand::OP_CAPTURE
;
637 is_a_helper
<predicate
*>::test (operand
*op
)
639 return op
->type
== operand::OP_PREDICATE
;
645 is_a_helper
<c_expr
*>::test (operand
*op
)
647 return op
->type
== operand::OP_C_EXPR
;
653 is_a_helper
<expr
*>::test (operand
*op
)
655 return op
->type
== operand::OP_EXPR
;
661 is_a_helper
<if_expr
*>::test (operand
*op
)
663 return op
->type
== operand::OP_IF
;
669 is_a_helper
<with_expr
*>::test (operand
*op
)
671 return op
->type
== operand::OP_WITH
;
674 /* The main class of a pattern and its transform. This is used to
675 represent both (simplify ...) and (match ...) kinds. The AST
676 duplicates all outer 'if' and 'for' expressions here so each
677 simplify can exist in isolation. */
681 enum simplify_kind
{ SIMPLIFY
, MATCH
};
683 simplify (simplify_kind kind_
, operand
*match_
, operand
*result_
,
684 vec
<vec
<user_id
*> > for_vec_
, cid_map_t
*capture_ids_
)
685 : kind (kind_
), match (match_
), result (result_
),
686 for_vec (for_vec_
), for_subst_vec (vNULL
),
687 capture_ids (capture_ids_
), capture_max (capture_ids_
->elements () - 1) {}
690 /* The expression that is matched against the GENERIC or GIMPLE IL. */
692 /* For a (simplify ...) an expression with ifs and withs with the expression
693 produced when the pattern applies in the leafs.
694 For a (match ...) the leafs are either empty if it is a simple predicate
695 or the single expression specifying the matched operands. */
696 struct operand
*result
;
697 /* Collected 'for' expression operators that have to be replaced
698 in the lowering phase. */
699 vec
<vec
<user_id
*> > for_vec
;
700 vec
<std::pair
<user_id
*, id_base
*> > for_subst_vec
;
701 /* A map of capture identifiers to indexes. */
702 cid_map_t
*capture_ids
;
706 /* Debugging routines for dumping the AST. */
709 print_operand (operand
*o
, FILE *f
= stderr
, bool flattened
= false)
711 if (capture
*c
= dyn_cast
<capture
*> (o
))
713 if (c
->what
&& flattened
== false)
714 print_operand (c
->what
, f
, flattened
);
715 fprintf (f
, "@%u", c
->where
);
718 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
719 fprintf (f
, "%s", p
->p
->id
);
721 else if (is_a
<c_expr
*> (o
))
722 fprintf (f
, "c_expr");
724 else if (expr
*e
= dyn_cast
<expr
*> (o
))
726 if (e
->ops
.length () == 0)
727 fprintf (f
, "%s", e
->operation
->id
);
730 fprintf (f
, "(%s", e
->operation
->id
);
732 if (flattened
== false)
734 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
737 print_operand (e
->ops
[i
], f
, flattened
);
749 print_matches (struct simplify
*s
, FILE *f
= stderr
)
751 fprintf (f
, "for expression: ");
752 print_operand (s
->match
, f
);
759 /* Lowering of commutative operators. */
762 cartesian_product (const vec
< vec
<operand
*> >& ops_vector
,
763 vec
< vec
<operand
*> >& result
, vec
<operand
*>& v
, unsigned n
)
765 if (n
== ops_vector
.length ())
767 vec
<operand
*> xv
= v
.copy ();
768 result
.safe_push (xv
);
772 for (unsigned i
= 0; i
< ops_vector
[n
].length (); ++i
)
774 v
[n
] = ops_vector
[n
][i
];
775 cartesian_product (ops_vector
, result
, v
, n
+ 1);
779 /* Lower OP to two operands in case it is marked as commutative. */
781 static vec
<operand
*>
782 commutate (operand
*op
)
784 vec
<operand
*> ret
= vNULL
;
786 if (capture
*c
= dyn_cast
<capture
*> (op
))
793 vec
<operand
*> v
= commutate (c
->what
);
794 for (unsigned i
= 0; i
< v
.length (); ++i
)
796 capture
*nc
= new capture (c
->location
, c
->where
, v
[i
]);
802 expr
*e
= dyn_cast
<expr
*> (op
);
803 if (!e
|| e
->ops
.length () == 0)
809 vec
< vec
<operand
*> > ops_vector
= vNULL
;
810 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
811 ops_vector
.safe_push (commutate (e
->ops
[i
]));
813 auto_vec
< vec
<operand
*> > result
;
814 auto_vec
<operand
*> v (e
->ops
.length ());
815 v
.quick_grow_cleared (e
->ops
.length ());
816 cartesian_product (ops_vector
, result
, v
, 0);
819 for (unsigned i
= 0; i
< result
.length (); ++i
)
821 expr
*ne
= new expr (e
);
822 ne
->is_commutative
= false;
823 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
824 ne
->append_op (result
[i
][j
]);
828 if (!e
->is_commutative
)
831 for (unsigned i
= 0; i
< result
.length (); ++i
)
833 expr
*ne
= new expr (e
);
834 ne
->is_commutative
= false;
835 // result[i].length () is 2 since e->operation is binary
836 for (unsigned j
= result
[i
].length (); j
; --j
)
837 ne
->append_op (result
[i
][j
-1]);
844 /* Lower operations marked as commutative in the AST of S and push
845 the resulting patterns to SIMPLIFIERS. */
848 lower_commutative (simplify
*s
, vec
<simplify
*>& simplifiers
)
850 vec
<operand
*> matchers
= commutate (s
->match
);
851 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
853 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
854 s
->for_vec
, s
->capture_ids
);
855 simplifiers
.safe_push (ns
);
859 /* Strip conditional conversios using operator OPER from O and its
860 children if STRIP, else replace them with an unconditional convert. */
863 lower_opt_convert (operand
*o
, enum tree_code oper
,
864 enum tree_code to_oper
, bool strip
)
866 if (capture
*c
= dyn_cast
<capture
*> (o
))
869 return new capture (c
->location
, c
->where
,
870 lower_opt_convert (c
->what
, oper
, to_oper
, strip
));
875 expr
*e
= dyn_cast
<expr
*> (o
);
879 if (*e
->operation
== oper
)
882 return lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
);
884 expr
*ne
= new expr (e
);
885 ne
->operation
= (to_oper
== CONVERT_EXPR
886 ? get_operator ("CONVERT_EXPR")
887 : get_operator ("VIEW_CONVERT_EXPR"));
888 ne
->append_op (lower_opt_convert (e
->ops
[0], oper
, to_oper
, strip
));
892 expr
*ne
= new expr (e
);
893 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
894 ne
->append_op (lower_opt_convert (e
->ops
[i
], oper
, to_oper
, strip
));
899 /* Determine whether O or its children uses the conditional conversion
903 has_opt_convert (operand
*o
, enum tree_code oper
)
905 if (capture
*c
= dyn_cast
<capture
*> (o
))
908 return has_opt_convert (c
->what
, oper
);
913 expr
*e
= dyn_cast
<expr
*> (o
);
917 if (*e
->operation
== oper
)
920 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
921 if (has_opt_convert (e
->ops
[i
], oper
))
927 /* Lower conditional convert operators in O, expanding it to a vector
930 static vec
<operand
*>
931 lower_opt_convert (operand
*o
)
933 vec
<operand
*> v1
= vNULL
, v2
;
937 enum tree_code opers
[]
938 = { CONVERT0
, CONVERT_EXPR
,
939 CONVERT1
, CONVERT_EXPR
,
940 CONVERT2
, CONVERT_EXPR
,
941 VIEW_CONVERT0
, VIEW_CONVERT_EXPR
,
942 VIEW_CONVERT1
, VIEW_CONVERT_EXPR
,
943 VIEW_CONVERT2
, VIEW_CONVERT_EXPR
};
945 /* Conditional converts are lowered to a pattern with the
946 conversion and one without. The three different conditional
947 convert codes are lowered separately. */
949 for (unsigned i
= 0; i
< sizeof (opers
) / sizeof (enum tree_code
); i
+= 2)
952 for (unsigned j
= 0; j
< v1
.length (); ++j
)
953 if (has_opt_convert (v1
[j
], opers
[i
]))
955 v2
.safe_push (lower_opt_convert (v1
[j
],
956 opers
[i
], opers
[i
+1], false));
957 v2
.safe_push (lower_opt_convert (v1
[j
],
958 opers
[i
], opers
[i
+1], true));
964 for (unsigned j
= 0; j
< v2
.length (); ++j
)
965 v1
.safe_push (v2
[j
]);
972 /* Lower conditional convert operators in the AST of S and push
973 the resulting multiple patterns to SIMPLIFIERS. */
976 lower_opt_convert (simplify
*s
, vec
<simplify
*>& simplifiers
)
978 vec
<operand
*> matchers
= lower_opt_convert (s
->match
);
979 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
981 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
982 s
->for_vec
, s
->capture_ids
);
983 simplifiers
.safe_push (ns
);
987 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
988 GENERIC and a GIMPLE variant. */
990 static vec
<operand
*>
991 lower_cond (operand
*o
)
993 vec
<operand
*> ro
= vNULL
;
995 if (capture
*c
= dyn_cast
<capture
*> (o
))
999 vec
<operand
*> lop
= vNULL
;
1000 lop
= lower_cond (c
->what
);
1002 for (unsigned i
= 0; i
< lop
.length (); ++i
)
1003 ro
.safe_push (new capture (c
->location
, c
->where
, lop
[i
]));
1008 expr
*e
= dyn_cast
<expr
*> (o
);
1009 if (!e
|| e
->ops
.length () == 0)
1015 vec
< vec
<operand
*> > ops_vector
= vNULL
;
1016 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1017 ops_vector
.safe_push (lower_cond (e
->ops
[i
]));
1019 auto_vec
< vec
<operand
*> > result
;
1020 auto_vec
<operand
*> v (e
->ops
.length ());
1021 v
.quick_grow_cleared (e
->ops
.length ());
1022 cartesian_product (ops_vector
, result
, v
, 0);
1024 for (unsigned i
= 0; i
< result
.length (); ++i
)
1026 expr
*ne
= new expr (e
);
1027 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1028 ne
->append_op (result
[i
][j
]);
1030 /* If this is a COND with a captured expression or an
1031 expression with two operands then also match a GENERIC
1032 form on the compare. */
1033 if ((*e
->operation
== COND_EXPR
1034 || *e
->operation
== VEC_COND_EXPR
)
1035 && ((is_a
<capture
*> (e
->ops
[0])
1036 && as_a
<capture
*> (e
->ops
[0])->what
1037 && is_a
<expr
*> (as_a
<capture
*> (e
->ops
[0])->what
)
1039 (as_a
<capture
*> (e
->ops
[0])->what
)->ops
.length () == 2)
1040 || (is_a
<expr
*> (e
->ops
[0])
1041 && as_a
<expr
*> (e
->ops
[0])->ops
.length () == 2)))
1043 expr
*ne
= new expr (e
);
1044 for (unsigned j
= 0; j
< result
[i
].length (); ++j
)
1045 ne
->append_op (result
[i
][j
]);
1046 if (capture
*c
= dyn_cast
<capture
*> (ne
->ops
[0]))
1048 expr
*ocmp
= as_a
<expr
*> (c
->what
);
1049 expr
*cmp
= new expr (ocmp
);
1050 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1051 cmp
->append_op (ocmp
->ops
[j
]);
1052 cmp
->is_generic
= true;
1053 ne
->ops
[0] = new capture (c
->location
, c
->where
, cmp
);
1057 expr
*ocmp
= as_a
<expr
*> (ne
->ops
[0]);
1058 expr
*cmp
= new expr (ocmp
);
1059 for (unsigned j
= 0; j
< ocmp
->ops
.length (); ++j
)
1060 cmp
->append_op (ocmp
->ops
[j
]);
1061 cmp
->is_generic
= true;
1071 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1072 GENERIC and a GIMPLE variant. */
1075 lower_cond (simplify
*s
, vec
<simplify
*>& simplifiers
)
1077 vec
<operand
*> matchers
= lower_cond (s
->match
);
1078 for (unsigned i
= 0; i
< matchers
.length (); ++i
)
1080 simplify
*ns
= new simplify (s
->kind
, matchers
[i
], s
->result
,
1081 s
->for_vec
, s
->capture_ids
);
1082 simplifiers
.safe_push (ns
);
1086 /* In AST operand O replace operator ID with operator WITH. */
1089 replace_id (operand
*o
, user_id
*id
, id_base
*with
)
1091 /* Deep-copy captures and expressions, replacing operations as
1093 if (capture
*c
= dyn_cast
<capture
*> (o
))
1097 return new capture (c
->location
, c
->where
,
1098 replace_id (c
->what
, id
, with
));
1100 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1102 expr
*ne
= new expr (e
);
1103 if (e
->operation
== id
)
1104 ne
->operation
= with
;
1105 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1106 ne
->append_op (replace_id (e
->ops
[i
], id
, with
));
1109 else if (with_expr
*w
= dyn_cast
<with_expr
*> (o
))
1111 with_expr
*nw
= new with_expr (w
->location
);
1112 nw
->with
= as_a
<c_expr
*> (replace_id (w
->with
, id
, with
));
1113 nw
->subexpr
= replace_id (w
->subexpr
, id
, with
);
1116 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (o
))
1118 if_expr
*nife
= new if_expr (ife
->location
);
1119 nife
->cond
= as_a
<c_expr
*> (replace_id (ife
->cond
, id
, with
));
1120 nife
->trueexpr
= replace_id (ife
->trueexpr
, id
, with
);
1122 nife
->falseexpr
= replace_id (ife
->falseexpr
, id
, with
);
1126 /* For c_expr we simply record a string replacement table which is
1127 applied at code-generation time. */
1128 if (c_expr
*ce
= dyn_cast
<c_expr
*> (o
))
1130 vec
<c_expr::id_tab
> ids
= ce
->ids
.copy ();
1131 ids
.safe_push (c_expr::id_tab (id
->id
, with
->id
));
1132 return new c_expr (ce
->r
, ce
->location
,
1133 ce
->code
, ce
->nr_stmts
, ids
, ce
->capture_ids
);
1139 /* Return true if the binary operator OP is ok for delayed substitution
1140 during for lowering. */
1143 binary_ok (operator_id
*op
)
1150 case TRUNC_DIV_EXPR
:
1152 case FLOOR_DIV_EXPR
:
1153 case ROUND_DIV_EXPR
:
1154 case TRUNC_MOD_EXPR
:
1156 case FLOOR_MOD_EXPR
:
1157 case ROUND_MOD_EXPR
:
1159 case EXACT_DIV_EXPR
:
1171 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1174 lower_for (simplify
*sin
, vec
<simplify
*>& simplifiers
)
1176 vec
<vec
<user_id
*> >& for_vec
= sin
->for_vec
;
1177 unsigned worklist_start
= 0;
1178 auto_vec
<simplify
*> worklist
;
1179 worklist
.safe_push (sin
);
1181 /* Lower each recorded for separately, operating on the
1182 set of simplifiers created by the previous one.
1183 Lower inner-to-outer so inner for substitutes can refer
1184 to operators replaced by outer fors. */
1185 for (int fi
= for_vec
.length () - 1; fi
>= 0; --fi
)
1187 vec
<user_id
*>& ids
= for_vec
[fi
];
1188 unsigned n_ids
= ids
.length ();
1189 unsigned max_n_opers
= 0;
1190 bool can_delay_subst
= (sin
->kind
== simplify::SIMPLIFY
);
1191 for (unsigned i
= 0; i
< n_ids
; ++i
)
1193 if (ids
[i
]->substitutes
.length () > max_n_opers
)
1194 max_n_opers
= ids
[i
]->substitutes
.length ();
1195 /* Require that all substitutes are of the same kind so that
1196 if we delay substitution to the result op code generation
1197 can look at the first substitute for deciding things like
1198 types of operands. */
1199 enum id_base::id_kind kind
= ids
[i
]->substitutes
[0]->kind
;
1200 for (unsigned j
= 0; j
< ids
[i
]->substitutes
.length (); ++j
)
1201 if (ids
[i
]->substitutes
[j
]->kind
!= kind
)
1202 can_delay_subst
= false;
1203 else if (operator_id
*op
1204 = dyn_cast
<operator_id
*> (ids
[i
]->substitutes
[j
]))
1207 = as_a
<operator_id
*> (ids
[i
]->substitutes
[0]);
1208 if (strcmp (op
->tcc
, "tcc_comparison") == 0
1209 && strcmp (op0
->tcc
, "tcc_comparison") == 0)
1211 /* Unfortunately we can't just allow all tcc_binary. */
1212 else if (strcmp (op
->tcc
, "tcc_binary") == 0
1213 && strcmp (op0
->tcc
, "tcc_binary") == 0
1217 else if ((strcmp (op
->id
+ 1, "SHIFT_EXPR") == 0
1218 || strcmp (op
->id
+ 1, "ROTATE_EXPR") == 0)
1219 && (strcmp (op0
->id
+ 1, "SHIFT_EXPR") == 0
1220 || strcmp (op0
->id
+ 1, "ROTATE_EXPR") == 0))
1223 can_delay_subst
= false;
1225 else if (is_a
<fn_id
*> (ids
[i
]->substitutes
[j
]))
1228 can_delay_subst
= false;
1231 unsigned worklist_end
= worklist
.length ();
1232 for (unsigned si
= worklist_start
; si
< worklist_end
; ++si
)
1234 simplify
*s
= worklist
[si
];
1235 for (unsigned j
= 0; j
< max_n_opers
; ++j
)
1237 operand
*match_op
= s
->match
;
1238 operand
*result_op
= s
->result
;
1239 vec
<std::pair
<user_id
*, id_base
*> > subst
;
1240 subst
.create (n_ids
);
1241 for (unsigned i
= 0; i
< n_ids
; ++i
)
1243 user_id
*id
= ids
[i
];
1244 id_base
*oper
= id
->substitutes
[j
% id
->substitutes
.length ()];
1245 subst
.quick_push (std::make_pair (id
, oper
));
1246 match_op
= replace_id (match_op
, id
, oper
);
1248 && !can_delay_subst
)
1249 result_op
= replace_id (result_op
, id
, oper
);
1251 simplify
*ns
= new simplify (s
->kind
, match_op
, result_op
,
1252 vNULL
, s
->capture_ids
);
1253 ns
->for_subst_vec
.safe_splice (s
->for_subst_vec
);
1256 ns
->for_subst_vec
.safe_splice (subst
);
1259 worklist
.safe_push (ns
);
1262 worklist_start
= worklist_end
;
1265 /* Copy out the result from the last for lowering. */
1266 for (unsigned i
= worklist_start
; i
< worklist
.length (); ++i
)
1267 simplifiers
.safe_push (worklist
[i
]);
1270 /* Lower the AST for everything in SIMPLIFIERS. */
1273 lower (vec
<simplify
*>& simplifiers
, bool gimple
)
1275 auto_vec
<simplify
*> out_simplifiers
;
1276 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1277 lower_opt_convert (simplifiers
[i
], out_simplifiers
);
1279 simplifiers
.truncate (0);
1280 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1281 lower_commutative (out_simplifiers
[i
], simplifiers
);
1283 out_simplifiers
.truncate (0);
1285 for (unsigned i
= 0; i
< simplifiers
.length (); ++i
)
1286 lower_cond (simplifiers
[i
], out_simplifiers
);
1288 out_simplifiers
.safe_splice (simplifiers
);
1291 simplifiers
.truncate (0);
1292 for (unsigned i
= 0; i
< out_simplifiers
.length (); ++i
)
1293 lower_for (out_simplifiers
[i
], simplifiers
);
1299 /* The decision tree built for generating GIMPLE and GENERIC pattern
1300 matching code. It represents the 'match' expression of all
1301 simplifies and has those as its leafs. */
1305 /* A hash-map collecting semantically equivalent leafs in the decision
1306 tree for splitting out to separate functions. */
1315 struct sinfo_hashmap_traits
: simple_hashmap_traits
<pointer_hash
<dt_simplify
> >
1317 static inline hashval_t
hash (const key_type
&);
1318 static inline bool equal_keys (const key_type
&, const key_type
&);
1319 template <typename T
> static inline void remove (T
&) {}
1322 typedef hash_map
<void * /* unused */, sinfo
*, sinfo_hashmap_traits
>
1326 /* Decision tree base class, used for DT_TRUE and DT_NODE. */
1330 enum dt_type
{ DT_NODE
, DT_OPERAND
, DT_TRUE
, DT_MATCH
, DT_SIMPLIFY
};
1334 vec
<dt_node
*> kids
;
1338 unsigned total_size
;
1341 dt_node (enum dt_type type_
): type (type_
), level (0), kids (vNULL
) {}
1343 dt_node
*append_node (dt_node
*);
1344 dt_node
*append_op (operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1345 dt_node
*append_true_op (dt_node
*parent
= 0, unsigned pos
= 0);
1346 dt_node
*append_match_op (dt_operand
*, dt_node
*parent
= 0, unsigned pos
= 0);
1347 dt_node
*append_simplify (simplify
*, unsigned, dt_operand
**);
1349 virtual void gen (FILE *, int, bool) {}
1351 void gen_kids (FILE *, int, bool);
1352 void gen_kids_1 (FILE *, int, bool,
1353 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_operand
*>,
1354 vec
<dt_operand
*>, vec
<dt_operand
*>, vec
<dt_node
*>);
1356 void analyze (sinfo_map_t
&);
1359 /* Generic decision tree node used for DT_OPERAND and DT_MATCH. */
1361 struct dt_operand
: public dt_node
1364 dt_operand
*match_dop
;
1368 dt_operand (enum dt_type type
, operand
*op_
, dt_operand
*match_dop_
,
1369 dt_operand
*parent_
= 0, unsigned pos_
= 0)
1370 : dt_node (type
), op (op_
), match_dop (match_dop_
),
1371 parent (parent_
), pos (pos_
) {}
1373 void gen (FILE *, int, bool);
1374 unsigned gen_predicate (FILE *, int, const char *, bool);
1375 unsigned gen_match_op (FILE *, int, const char *);
1377 unsigned gen_gimple_expr (FILE *, int);
1378 unsigned gen_generic_expr (FILE *, int, const char *);
1380 char *get_name (char *);
1381 void gen_opname (char *, unsigned);
1384 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1386 struct dt_simplify
: public dt_node
1389 unsigned pattern_no
;
1390 dt_operand
**indexes
;
1393 dt_simplify (simplify
*s_
, unsigned pattern_no_
, dt_operand
**indexes_
)
1394 : dt_node (DT_SIMPLIFY
), s (s_
), pattern_no (pattern_no_
),
1395 indexes (indexes_
), info (NULL
) {}
1397 void gen_1 (FILE *, int, bool, operand
*);
1398 void gen (FILE *f
, int, bool);
1404 is_a_helper
<dt_operand
*>::test (dt_node
*n
)
1406 return (n
->type
== dt_node::DT_OPERAND
1407 || n
->type
== dt_node::DT_MATCH
);
1413 is_a_helper
<dt_simplify
*>::test (dt_node
*n
)
1415 return n
->type
== dt_node::DT_SIMPLIFY
;
1420 /* A container for the actual decision tree. */
1422 struct decision_tree
1426 void insert (struct simplify
*, unsigned);
1427 void gen (FILE *f
, bool gimple
);
1428 void print (FILE *f
= stderr
);
1430 decision_tree () { root
= new dt_node (dt_node::DT_NODE
); }
1432 static dt_node
*insert_operand (dt_node
*, operand
*, dt_operand
**indexes
,
1433 unsigned pos
= 0, dt_node
*parent
= 0);
1434 static dt_node
*find_node (vec
<dt_node
*>&, dt_node
*);
1435 static bool cmp_node (dt_node
*, dt_node
*);
1436 static void print_node (dt_node
*, FILE *f
= stderr
, unsigned = 0);
1439 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1442 cmp_operand (operand
*o1
, operand
*o2
)
1444 if (!o1
|| !o2
|| o1
->type
!= o2
->type
)
1447 if (o1
->type
== operand::OP_PREDICATE
)
1449 predicate
*p1
= as_a
<predicate
*>(o1
);
1450 predicate
*p2
= as_a
<predicate
*>(o2
);
1451 return p1
->p
== p2
->p
;
1453 else if (o1
->type
== operand::OP_EXPR
)
1455 expr
*e1
= static_cast<expr
*>(o1
);
1456 expr
*e2
= static_cast<expr
*>(o2
);
1457 return (e1
->operation
== e2
->operation
1458 && e1
->is_generic
== e2
->is_generic
);
1464 /* Compare two decision tree nodes N1 and N2 and return true if they
1468 decision_tree::cmp_node (dt_node
*n1
, dt_node
*n2
)
1470 if (!n1
|| !n2
|| n1
->type
!= n2
->type
)
1476 if (n1
->type
== dt_node::DT_TRUE
)
1479 if (n1
->type
== dt_node::DT_OPERAND
)
1480 return cmp_operand ((as_a
<dt_operand
*> (n1
))->op
,
1481 (as_a
<dt_operand
*> (n2
))->op
);
1482 else if (n1
->type
== dt_node::DT_MATCH
)
1483 return ((as_a
<dt_operand
*> (n1
))->match_dop
1484 == (as_a
<dt_operand
*> (n2
))->match_dop
);
1488 /* Search OPS for a decision tree node like P and return it if found. */
1491 decision_tree::find_node (vec
<dt_node
*>& ops
, dt_node
*p
)
1493 /* We can merge adjacent DT_TRUE. */
1494 if (p
->type
== dt_node::DT_TRUE
1496 && ops
.last ()->type
== dt_node::DT_TRUE
)
1498 for (int i
= ops
.length () - 1; i
>= 0; --i
)
1500 /* But we can't merge across DT_TRUE nodes as they serve as
1501 pattern order barriers to make sure that patterns apply
1502 in order of appearance in case multiple matches are possible. */
1503 if (ops
[i
]->type
== dt_node::DT_TRUE
)
1505 if (decision_tree::cmp_node (ops
[i
], p
))
1511 /* Append N to the decision tree if it there is not already an existing
1515 dt_node::append_node (dt_node
*n
)
1519 kid
= decision_tree::find_node (kids
, n
);
1524 n
->level
= this->level
+ 1;
1529 /* Append OP to the decision tree. */
1532 dt_node::append_op (operand
*op
, dt_node
*parent
, unsigned pos
)
1534 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1535 dt_operand
*n
= new dt_operand (DT_OPERAND
, op
, 0, parent_
, pos
);
1536 return append_node (n
);
1539 /* Append a DT_TRUE decision tree node. */
1542 dt_node::append_true_op (dt_node
*parent
, unsigned pos
)
1544 dt_operand
*parent_
= safe_as_a
<dt_operand
*> (parent
);
1545 dt_operand
*n
= new dt_operand (DT_TRUE
, 0, 0, parent_
, pos
);
1546 return append_node (n
);
1549 /* Append a DT_MATCH decision tree node. */
1552 dt_node::append_match_op (dt_operand
*match_dop
, dt_node
*parent
, unsigned pos
)
1554 dt_operand
*parent_
= as_a
<dt_operand
*> (parent
);
1555 dt_operand
*n
= new dt_operand (DT_MATCH
, 0, match_dop
, parent_
, pos
);
1556 return append_node (n
);
1559 /* Append S to the decision tree. */
1562 dt_node::append_simplify (simplify
*s
, unsigned pattern_no
,
1563 dt_operand
**indexes
)
1565 dt_simplify
*n
= new dt_simplify (s
, pattern_no
, indexes
);
1566 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1567 if (dt_simplify
*s2
= dyn_cast
<dt_simplify
*> (kids
[i
]))
1569 warning_at (s
->match
->location
, "duplicate pattern");
1570 warning_at (s2
->s
->match
->location
, "previous pattern defined here");
1571 print_operand (s
->match
, stderr
);
1572 fprintf (stderr
, "\n");
1574 return append_node (n
);
1577 /* Analyze the node and its children. */
1580 dt_node::analyze (sinfo_map_t
&map
)
1586 if (type
== DT_SIMPLIFY
)
1588 /* Populate the map of equivalent simplifies. */
1589 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1591 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1606 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1608 kids
[i
]->analyze (map
);
1609 num_leafs
+= kids
[i
]->num_leafs
;
1610 total_size
+= kids
[i
]->total_size
;
1611 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1615 /* Insert O into the decision tree and return the decision tree node found
1619 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1620 unsigned pos
, dt_node
*parent
)
1622 dt_node
*q
, *elm
= 0;
1624 if (capture
*c
= dyn_cast
<capture
*> (o
))
1626 unsigned capt_index
= c
->where
;
1628 if (indexes
[capt_index
] == 0)
1631 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1634 q
= elm
= p
->append_true_op (parent
, pos
);
1637 // get to the last capture
1638 for (operand
*what
= c
->what
;
1639 what
&& is_a
<capture
*> (what
);
1640 c
= as_a
<capture
*> (what
), what
= c
->what
)
1645 unsigned cc_index
= c
->where
;
1646 dt_operand
*match_op
= indexes
[cc_index
];
1648 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1649 elm
= decision_tree::find_node (p
->kids
, &temp
);
1653 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1654 elm
= decision_tree::find_node (p
->kids
, &temp
);
1659 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1660 elm
= decision_tree::find_node (p
->kids
, &temp
);
1664 gcc_assert (elm
->type
== dt_node::DT_TRUE
1665 || elm
->type
== dt_node::DT_OPERAND
1666 || elm
->type
== dt_node::DT_MATCH
);
1667 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1672 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1674 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1679 p
= p
->append_op (o
, parent
, pos
);
1682 if (expr
*e
= dyn_cast
<expr
*>(o
))
1684 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1685 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1691 /* Insert S into the decision tree. */
1694 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1696 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1697 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1698 p
->append_simplify (s
, pattern_no
, indexes
);
1701 /* Debug functions to dump the decision tree. */
1704 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1706 if (p
->type
== dt_node::DT_NODE
)
1707 fprintf (f
, "root");
1711 for (unsigned i
= 0; i
< indent
; i
++)
1714 if (p
->type
== dt_node::DT_OPERAND
)
1716 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1717 print_operand (dop
->op
, f
, true);
1719 else if (p
->type
== dt_node::DT_TRUE
)
1720 fprintf (f
, "true");
1721 else if (p
->type
== dt_node::DT_MATCH
)
1722 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1723 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1725 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1726 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1727 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1728 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1733 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1735 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1736 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1740 decision_tree::print (FILE *f
)
1742 return decision_tree::print_node (root
, f
);
1746 /* For GENERIC we have to take care of wrapping multiple-used
1747 expressions with side-effects in save_expr and preserve side-effects
1748 of expressions with omit_one_operand. Analyze captures in
1749 match, result and with expressions and perform early-outs
1750 on the outermost match expression operands for cases we cannot
1755 capture_info (simplify
*s
, operand
*, bool);
1756 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1757 bool walk_result (operand
*o
, bool, operand
*);
1758 void walk_c_expr (c_expr
*);
1764 bool force_no_side_effects_p
;
1765 bool force_single_use
;
1766 bool cond_expr_cond_p
;
1767 unsigned long toplevel_msk
;
1768 int result_use_count
;
1773 auto_vec
<cinfo
> info
;
1774 unsigned long force_no_side_effects
;
1778 /* Analyze captures in S. */
1780 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
1785 if (s
->kind
== simplify::MATCH
)
1787 force_no_side_effects
= -1;
1791 force_no_side_effects
= 0;
1792 info
.safe_grow_cleared (s
->capture_max
+ 1);
1793 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1794 info
[i
].same_as
= i
;
1796 e
= as_a
<expr
*> (s
->match
);
1797 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1798 walk_match (e
->ops
[i
], i
,
1799 (i
!= 0 && *e
->operation
== COND_EXPR
)
1800 || *e
->operation
== TRUTH_ANDIF_EXPR
1801 || *e
->operation
== TRUTH_ORIF_EXPR
,
1803 && (*e
->operation
== COND_EXPR
1804 || *e
->operation
== VEC_COND_EXPR
));
1806 walk_result (s
->result
, false, result
);
1809 /* Analyze captures in the match expression piece O. */
1812 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1813 bool conditional_p
, bool cond_expr_cond_p
)
1815 if (capture
*c
= dyn_cast
<capture
*> (o
))
1817 unsigned where
= c
->where
;
1818 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
1819 info
[where
].force_no_side_effects_p
|= conditional_p
;
1820 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1825 /* Recurse to exprs and captures. */
1826 if (is_a
<capture
*> (c
->what
)
1827 || is_a
<expr
*> (c
->what
))
1828 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1829 /* We need to look past multiple captures to find a captured
1830 expression as with conditional converts two captures
1831 can be collapsed onto the same expression. Also collect
1832 what captures capture the same thing. */
1833 while (c
->what
&& is_a
<capture
*> (c
->what
))
1835 c
= as_a
<capture
*> (c
->what
);
1836 if (info
[c
->where
].same_as
!= c
->where
1837 && info
[c
->where
].same_as
!= info
[where
].same_as
)
1838 fatal_at (c
->location
, "cannot handle this collapsed capture");
1839 info
[c
->where
].same_as
= info
[where
].same_as
;
1841 /* Mark expr (non-leaf) captures and forced single-use exprs. */
1844 && (e
= dyn_cast
<expr
*> (c
->what
)))
1846 info
[where
].expr_p
= true;
1847 info
[where
].force_single_use
|= e
->force_single_use
;
1850 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1852 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1854 bool cond_p
= conditional_p
;
1855 bool cond_expr_cond_p
= false;
1856 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1858 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1859 || *e
->operation
== TRUTH_ORIF_EXPR
)
1862 && (*e
->operation
== COND_EXPR
1863 || *e
->operation
== VEC_COND_EXPR
))
1864 cond_expr_cond_p
= true;
1865 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1868 else if (is_a
<predicate
*> (o
))
1870 /* Mark non-captured leafs toplevel arg for checking. */
1871 force_no_side_effects
|= 1 << toplevel_arg
;
1874 warning_at (o
->location
,
1875 "forcing no side-effects on possibly lost leaf");
1881 /* Analyze captures in the result expression piece O. Return true
1882 if RESULT was visited in one of the children. Only visit
1883 non-if/with children if they are rooted on RESULT. */
1886 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
1888 if (capture
*c
= dyn_cast
<capture
*> (o
))
1890 unsigned where
= info
[c
->where
].same_as
;
1891 info
[where
].result_use_count
++;
1892 /* If we substitute an expression capture we don't know
1893 which captures this will end up using (well, we don't
1894 compute that). Force the uses to be side-effect free
1895 which means forcing the toplevels that reach the
1896 expression side-effect free. */
1897 if (info
[where
].expr_p
)
1898 force_no_side_effects
|= info
[where
].toplevel_msk
;
1899 /* Mark CSE capture uses as forced to have no side-effects. */
1901 && is_a
<expr
*> (c
->what
))
1903 info
[where
].cse_p
= true;
1904 walk_result (c
->what
, true, result
);
1907 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1909 id_base
*opr
= e
->operation
;
1910 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
1911 opr
= uid
->substitutes
[0];
1912 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1914 bool cond_p
= conditional_p
;
1915 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1917 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1918 || *e
->operation
== TRUTH_ORIF_EXPR
)
1920 walk_result (e
->ops
[i
], cond_p
, result
);
1923 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
1925 /* 'if' conditions should be all fine. */
1926 if (e
->trueexpr
== result
)
1928 walk_result (e
->trueexpr
, false, result
);
1931 if (e
->falseexpr
== result
)
1933 walk_result (e
->falseexpr
, false, result
);
1937 if (is_a
<if_expr
*> (e
->trueexpr
)
1938 || is_a
<with_expr
*> (e
->trueexpr
))
1939 res
|= walk_result (e
->trueexpr
, false, result
);
1941 && (is_a
<if_expr
*> (e
->falseexpr
)
1942 || is_a
<with_expr
*> (e
->falseexpr
)))
1943 res
|= walk_result (e
->falseexpr
, false, result
);
1946 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
1948 bool res
= (e
->subexpr
== result
);
1950 || is_a
<if_expr
*> (e
->subexpr
)
1951 || is_a
<with_expr
*> (e
->subexpr
))
1952 res
|= walk_result (e
->subexpr
, false, result
);
1954 walk_c_expr (e
->with
);
1957 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1965 /* Look for captures in the C expr E. */
1968 capture_info::walk_c_expr (c_expr
*e
)
1970 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
1971 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
1972 really escape through. */
1973 unsigned p_depth
= 0;
1974 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1976 const cpp_token
*t
= &e
->code
[i
];
1977 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1979 if (t
->type
== CPP_NAME
1980 && (strcmp ((const char *)CPP_HASHNODE
1981 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1982 || strcmp ((const char *)CPP_HASHNODE
1983 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
1984 || strcmp ((const char *)CPP_HASHNODE
1985 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
1986 || ((id
= get_operator ((const char *)CPP_HASHNODE
1987 (t
->val
.node
.node
)->ident
.str
))
1988 && is_a
<predicate_id
*> (id
)))
1989 && n
->type
== CPP_OPEN_PAREN
)
1991 else if (t
->type
== CPP_CLOSE_PAREN
1994 else if (p_depth
== 0
1995 && t
->type
== CPP_ATSIGN
1996 && (n
->type
== CPP_NUMBER
1997 || n
->type
== CPP_NAME
)
1998 && !(n
->flags
& PREV_WHITE
))
2001 if (n
->type
== CPP_NUMBER
)
2002 id
= (const char *)n
->val
.str
.text
;
2004 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2005 unsigned where
= *e
->capture_ids
->get(id
);
2006 info
[info
[where
].same_as
].force_no_side_effects_p
= true;
2009 warning_at (t
, "capture escapes");
2015 /* Code generation off the decision tree and the refered AST nodes. */
2018 is_conversion (id_base
*op
)
2020 return (*op
== CONVERT_EXPR
2022 || *op
== FLOAT_EXPR
2023 || *op
== FIX_TRUNC_EXPR
2024 || *op
== VIEW_CONVERT_EXPR
);
2027 /* Get the type to be used for generating operands of OP from the
2031 get_operand_type (id_base
*op
, const char *in_type
,
2032 const char *expr_type
,
2033 const char *other_oprnd_type
)
2035 /* Generally operands whose type does not match the type of the
2036 expression generated need to know their types but match and
2037 thus can fall back to 'other_oprnd_type'. */
2038 if (is_conversion (op
))
2039 return other_oprnd_type
;
2040 else if (*op
== REALPART_EXPR
2041 || *op
== IMAGPART_EXPR
)
2042 return other_oprnd_type
;
2043 else if (is_a
<operator_id
*> (op
)
2044 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2045 return other_oprnd_type
;
2048 /* Otherwise all types should match - choose one in order of
2055 return other_oprnd_type
;
2059 /* Generate transform code for an expression. */
2062 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2063 int depth
, const char *in_type
, capture_info
*cinfo
,
2064 dt_operand
**indexes
, bool)
2066 id_base
*opr
= operation
;
2067 /* When we delay operator substituting during lowering of fors we
2068 make sure that for code-gen purposes the effects of each substitute
2069 are the same. Thus just look at that. */
2070 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2071 opr
= uid
->substitutes
[0];
2073 bool conversion_p
= is_conversion (opr
);
2074 const char *type
= expr_type
;
2077 /* If there was a type specification in the pattern use it. */
2079 else if (conversion_p
)
2080 /* For conversions we need to build the expression using the
2081 outer type passed in. */
2083 else if (*opr
== REALPART_EXPR
2084 || *opr
== IMAGPART_EXPR
)
2086 /* __real and __imag use the component type of its operand. */
2087 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2090 else if (is_a
<operator_id
*> (opr
)
2091 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2093 /* comparisons use boolean_type_node (or what gets in), but
2094 their operands need to figure out the types themselves. */
2095 sprintf (optype
, "boolean_type_node");
2098 else if (*opr
== COND_EXPR
2099 || *opr
== VEC_COND_EXPR
)
2101 /* Conditions are of the same type as their first alternative. */
2102 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2107 /* Other operations are of the same type as their first operand. */
2108 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2112 fatal_at (location
, "cannot determine type of operand");
2114 fprintf_indent (f
, indent
, "{\n");
2116 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2118 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2119 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2122 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2124 = get_operand_type (opr
, in_type
, expr_type
,
2125 i
== 0 ? NULL
: op0type
);
2126 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2128 ((!(*opr
== COND_EXPR
)
2129 && !(*opr
== VEC_COND_EXPR
))
2133 const char *opr_name
;
2134 if (*operation
== CONVERT_EXPR
)
2135 opr_name
= "NOP_EXPR";
2137 opr_name
= operation
->id
;
2141 if (*opr
== CONVERT_EXPR
)
2143 fprintf_indent (f
, indent
,
2144 "if (%s != TREE_TYPE (ops%d[0])\n",
2146 fprintf_indent (f
, indent
,
2147 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2149 fprintf_indent (f
, indent
+ 2, "{\n");
2152 /* ??? Building a stmt can fail for various reasons here, seq being
2153 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2154 So if we fail here we should continue matching other patterns. */
2155 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2156 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2157 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2158 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2159 i
== ops
.length () - 1 ? " };\n" : ", ");
2160 fprintf_indent (f
, indent
,
2161 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2162 ops
.length (), type
);
2163 fprintf_indent (f
, indent
,
2164 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2166 fprintf_indent (f
, indent
,
2167 "if (!res) return false;\n");
2168 if (*opr
== CONVERT_EXPR
)
2171 fprintf_indent (f
, indent
, " }\n");
2172 fprintf_indent (f
, indent
, "else\n");
2173 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2178 if (*opr
== CONVERT_EXPR
)
2180 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2184 if (opr
->kind
== id_base::CODE
)
2185 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2186 ops
.length(), opr_name
, type
);
2189 fprintf_indent (f
, indent
, "{\n");
2190 fprintf_indent (f
, indent
, " tree decl = builtin_decl_implicit (%s);\n",
2192 fprintf_indent (f
, indent
, " if (!decl) return NULL_TREE;\n");
2193 fprintf_indent (f
, indent
, " res = build_call_expr_loc (loc, "
2194 "decl, %d", ops
.length());
2196 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2197 fprintf (f
, ", ops%d[%u]", depth
, i
);
2198 fprintf (f
, ");\n");
2199 if (opr
->kind
!= id_base::CODE
)
2200 fprintf_indent (f
, indent
, "}\n");
2201 if (*opr
== CONVERT_EXPR
)
2204 fprintf_indent (f
, indent
, "else\n");
2205 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2208 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2210 fprintf_indent (f
, indent
, "}\n");
2213 /* Generate code for a c_expr which is either the expression inside
2214 an if statement or a sequence of statements which computes a
2215 result to be stored to DEST. */
2218 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2219 bool, int, const char *, capture_info
*,
2220 dt_operand
**, bool)
2222 if (dest
&& nr_stmts
== 1)
2223 fprintf_indent (f
, indent
, "%s = ", dest
);
2225 unsigned stmt_nr
= 1;
2226 for (unsigned i
= 0; i
< code
.length (); ++i
)
2228 const cpp_token
*token
= &code
[i
];
2230 /* Replace captures for code-gen. */
2231 if (token
->type
== CPP_ATSIGN
)
2233 const cpp_token
*n
= &code
[i
+1];
2234 if ((n
->type
== CPP_NUMBER
2235 || n
->type
== CPP_NAME
)
2236 && !(n
->flags
& PREV_WHITE
))
2238 if (token
->flags
& PREV_WHITE
)
2241 if (n
->type
== CPP_NUMBER
)
2242 id
= (const char *)n
->val
.str
.text
;
2244 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2245 unsigned *cid
= capture_ids
->get (id
);
2247 fatal_at (token
, "unknown capture id");
2248 fprintf (f
, "captures[%u]", *cid
);
2254 if (token
->flags
& PREV_WHITE
)
2257 if (token
->type
== CPP_NAME
)
2259 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2261 for (j
= 0; j
< ids
.length (); ++j
)
2263 if (strcmp (id
, ids
[j
].id
) == 0)
2265 fprintf (f
, "%s", ids
[j
].oper
);
2269 if (j
< ids
.length ())
2273 /* Output the token as string. */
2274 char *tk
= (char *)cpp_token_as_text (r
, token
);
2277 if (token
->type
== CPP_SEMICOLON
)
2281 if (dest
&& stmt_nr
== nr_stmts
)
2282 fprintf_indent (f
, indent
, "%s = ", dest
);
2287 /* Generate transform code for a capture. */
2290 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2291 int depth
, const char *in_type
, capture_info
*cinfo
,
2292 dt_operand
**indexes
, bool expand_compares
)
2294 if (what
&& is_a
<expr
*> (what
))
2296 if (indexes
[where
] == 0)
2299 sprintf (buf
, "captures[%u]", where
);
2300 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2305 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2307 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2308 with substituting a capture of that.
2309 ??? Returning false here will also not allow any other patterns
2311 if (gimple
&& expand_compares
2312 && cinfo
->info
[where
].cond_expr_cond_p
)
2314 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2315 fprintf_indent (f
, indent
, " {\n");
2316 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2317 fprintf_indent (f
, indent
, " %s = gimple_build (seq, TREE_CODE (%s),"
2318 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2319 " TREE_OPERAND (%s, 1));\n",
2320 dest
, dest
, dest
, dest
, dest
);
2321 fprintf_indent (f
, indent
, " }\n");
2325 /* Return the name of the operand representing the decision tree node.
2326 Use NAME as space to generate it. */
2329 dt_operand::get_name (char *name
)
2332 sprintf (name
, "t");
2333 else if (parent
->level
== 1)
2334 sprintf (name
, "op%u", pos
);
2335 else if (parent
->type
== dt_node::DT_MATCH
)
2336 return parent
->get_name (name
);
2338 sprintf (name
, "o%u%u", parent
->level
, pos
);
2342 /* Fill NAME with the operand name at position POS. */
2345 dt_operand::gen_opname (char *name
, unsigned pos
)
2348 sprintf (name
, "op%u", pos
);
2350 sprintf (name
, "o%u%u", level
, pos
);
2353 /* Generate matching code for the decision tree operand which is
2357 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2359 predicate
*p
= as_a
<predicate
*> (op
);
2361 if (p
->p
->matchers
.exists ())
2363 /* If this is a predicate generated from a pattern mangle its
2364 name and pass on the valueize hook. */
2366 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2369 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2372 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2373 fprintf_indent (f
, indent
+ 2, "{\n");
2377 /* Generate matching code for the decision tree operand which is
2381 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
)
2383 char match_opname
[20];
2384 match_dop
->get_name (match_opname
);
2385 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2386 opname
, match_opname
, opname
, match_opname
);
2387 fprintf_indent (f
, indent
+ 2, "{\n");
2391 /* Generate GIMPLE matching code for the decision tree operand. */
2394 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2396 expr
*e
= static_cast<expr
*> (op
);
2397 id_base
*id
= e
->operation
;
2398 unsigned n_ops
= e
->ops
.length ();
2400 for (unsigned i
= 0; i
< n_ops
; ++i
)
2402 char child_opname
[20];
2403 gen_opname (child_opname
, i
);
2405 if (id
->kind
== id_base::CODE
)
2408 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2409 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2411 /* ??? If this is a memory operation we can't (and should not)
2412 match this. The only sensible operand types are
2413 SSA names and invariants. */
2414 fprintf_indent (f
, indent
,
2415 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def), %i);\n",
2417 fprintf_indent (f
, indent
,
2418 "if ((TREE_CODE (%s) == SSA_NAME\n",
2420 fprintf_indent (f
, indent
,
2421 " || is_gimple_min_invariant (%s))\n",
2423 fprintf_indent (f
, indent
,
2424 " && (%s = do_valueize (valueize, %s)))\n",
2425 child_opname
, child_opname
);
2426 fprintf_indent (f
, indent
,
2432 fprintf_indent (f
, indent
,
2433 "tree %s = gimple_assign_rhs%u (def);\n",
2434 child_opname
, i
+ 1);
2437 fprintf_indent (f
, indent
,
2438 "tree %s = gimple_call_arg (def, %u);\n",
2440 fprintf_indent (f
, indent
,
2441 "if ((%s = do_valueize (valueize, %s)))\n",
2442 child_opname
, child_opname
);
2443 fprintf_indent (f
, indent
, " {\n");
2446 /* While the toplevel operands are canonicalized by the caller
2447 after valueizing operands of sub-expressions we have to
2448 re-canonicalize operand order. */
2449 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2451 /* ??? We can't canonicalize tcc_comparison operands here
2452 because that requires changing the comparison code which
2453 we already matched... */
2454 if (commutative_tree_code (code
->code
)
2455 || commutative_ternary_tree_code (code
->code
))
2457 char child_opname0
[20], child_opname1
[20];
2458 gen_opname (child_opname0
, 0);
2459 gen_opname (child_opname1
, 1);
2460 fprintf_indent (f
, indent
,
2461 "if (tree_swap_operands_p (%s, %s, false))\n",
2462 child_opname0
, child_opname1
);
2463 fprintf_indent (f
, indent
,
2464 " std::swap (%s, %s);\n",
2465 child_opname0
, child_opname1
);
2472 /* Generate GENERIC matching code for the decision tree operand. */
2475 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2477 expr
*e
= static_cast<expr
*> (op
);
2478 unsigned n_ops
= e
->ops
.length ();
2480 for (unsigned i
= 0; i
< n_ops
; ++i
)
2482 char child_opname
[20];
2483 gen_opname (child_opname
, i
);
2485 if (e
->operation
->kind
== id_base::CODE
)
2486 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2487 child_opname
, opname
, i
);
2489 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2490 child_opname
, opname
, i
);
2496 /* Generate matching code for the children of the decision tree node. */
2499 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2501 auto_vec
<dt_operand
*> gimple_exprs
;
2502 auto_vec
<dt_operand
*> generic_exprs
;
2503 auto_vec
<dt_operand
*> fns
;
2504 auto_vec
<dt_operand
*> generic_fns
;
2505 auto_vec
<dt_operand
*> preds
;
2506 auto_vec
<dt_node
*> others
;
2508 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2510 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2512 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2513 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2515 if (e
->ops
.length () == 0
2516 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2517 generic_exprs
.safe_push (op
);
2518 else if (e
->operation
->kind
== id_base::FN
)
2523 generic_fns
.safe_push (op
);
2525 else if (e
->operation
->kind
== id_base::PREDICATE
)
2526 preds
.safe_push (op
);
2530 gimple_exprs
.safe_push (op
);
2532 generic_exprs
.safe_push (op
);
2535 else if (op
->op
->type
== operand::OP_PREDICATE
)
2536 others
.safe_push (kids
[i
]);
2540 else if (kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2541 others
.safe_push (kids
[i
]);
2542 else if (kids
[i
]->type
== dt_node::DT_MATCH
2543 || kids
[i
]->type
== dt_node::DT_TRUE
)
2545 /* A DT_TRUE operand serves as a barrier - generate code now
2546 for what we have collected sofar.
2547 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2548 dependent matches to get out-of-order. Generate code now
2549 for what we have collected sofar. */
2550 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2551 fns
, generic_fns
, preds
, others
);
2552 /* And output the true operand itself. */
2553 kids
[i
]->gen (f
, indent
, gimple
);
2554 gimple_exprs
.truncate (0);
2555 generic_exprs
.truncate (0);
2557 generic_fns
.truncate (0);
2559 others
.truncate (0);
2565 /* Generate code for the remains. */
2566 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2567 fns
, generic_fns
, preds
, others
);
2570 /* Generate matching code for the children of the decision tree node. */
2573 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2574 vec
<dt_operand
*> gimple_exprs
,
2575 vec
<dt_operand
*> generic_exprs
,
2576 vec
<dt_operand
*> fns
,
2577 vec
<dt_operand
*> generic_fns
,
2578 vec
<dt_operand
*> preds
,
2579 vec
<dt_node
*> others
)
2582 char *kid_opname
= buf
;
2584 unsigned exprs_len
= gimple_exprs
.length ();
2585 unsigned gexprs_len
= generic_exprs
.length ();
2586 unsigned fns_len
= fns
.length ();
2587 unsigned gfns_len
= generic_fns
.length ();
2589 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2592 gimple_exprs
[0]->get_name (kid_opname
);
2594 fns
[0]->get_name (kid_opname
);
2596 generic_fns
[0]->get_name (kid_opname
);
2598 generic_exprs
[0]->get_name (kid_opname
);
2600 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2601 fprintf_indent (f
, indent
, " {\n");
2605 if (exprs_len
|| fns_len
)
2607 fprintf_indent (f
, indent
,
2608 "case SSA_NAME:\n");
2609 fprintf_indent (f
, indent
,
2610 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2612 fprintf_indent (f
, indent
,
2614 fprintf_indent (f
, indent
,
2615 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2621 fprintf_indent (f
, indent
,
2622 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2623 fprintf_indent (f
, indent
,
2624 " switch (gimple_assign_rhs_code (def))\n");
2626 fprintf_indent (f
, indent
, "{\n");
2627 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2629 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2630 id_base
*op
= e
->operation
;
2631 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2632 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2634 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2635 fprintf_indent (f
, indent
, " {\n");
2636 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2637 fprintf_indent (f
, indent
, " break;\n");
2638 fprintf_indent (f
, indent
, " }\n");
2640 fprintf_indent (f
, indent
, "default:;\n");
2641 fprintf_indent (f
, indent
, "}\n");
2647 fprintf_indent (f
, indent
,
2648 "%sif (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n",
2649 exprs_len
? "else " : "");
2650 fprintf_indent (f
, indent
,
2652 fprintf_indent (f
, indent
,
2653 " gcall *def = as_a <gcall *> (def_stmt);\n");
2654 fprintf_indent (f
, indent
,
2655 " tree fndecl = gimple_call_fndecl (def);\n");
2656 fprintf_indent (f
, indent
,
2657 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2658 fprintf_indent (f
, indent
,
2662 for (unsigned i
= 0; i
< fns_len
; ++i
)
2664 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2665 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2666 fprintf_indent (f
, indent
, " {\n");
2667 fns
[i
]->gen (f
, indent
+ 4, true);
2668 fprintf_indent (f
, indent
, " break;\n");
2669 fprintf_indent (f
, indent
, " }\n");
2672 fprintf_indent (f
, indent
, "default:;\n");
2673 fprintf_indent (f
, indent
, "}\n");
2675 fprintf_indent (f
, indent
, " }\n");
2679 fprintf_indent (f
, indent
, " }\n");
2680 fprintf_indent (f
, indent
, " break;\n");
2683 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2685 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2686 id_base
*op
= e
->operation
;
2687 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2688 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2690 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2691 fprintf_indent (f
, indent
, " {\n");
2692 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2693 fprintf_indent (f
, indent
, " break;\n");
2694 fprintf_indent (f
, indent
, " }\n");
2699 fprintf_indent (f
, indent
,
2700 "case CALL_EXPR:\n");
2701 fprintf_indent (f
, indent
,
2703 fprintf_indent (f
, indent
,
2704 " tree fndecl = get_callee_fndecl (%s);\n",
2706 fprintf_indent (f
, indent
,
2707 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2708 fprintf_indent (f
, indent
,
2709 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2710 fprintf_indent (f
, indent
,
2714 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2716 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2717 gcc_assert (e
->operation
->kind
== id_base::FN
);
2719 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2720 fprintf_indent (f
, indent
, " {\n");
2721 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2722 fprintf_indent (f
, indent
, " break;\n");
2723 fprintf_indent (f
, indent
, " }\n");
2727 fprintf_indent (f
, indent
, " default:;\n");
2728 fprintf_indent (f
, indent
, " }\n");
2729 fprintf_indent (f
, indent
, " break;\n");
2730 fprintf_indent (f
, indent
, " }\n");
2733 /* Close switch (TREE_CODE ()). */
2734 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2737 fprintf_indent (f
, indent
, " default:;\n");
2738 fprintf_indent (f
, indent
, " }\n");
2741 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2743 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2744 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2745 preds
[i
]->get_name (kid_opname
);
2746 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2747 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2748 gimple
? "gimple" : "tree",
2749 p
->id
, kid_opname
, kid_opname
,
2750 gimple
? ", valueize" : "");
2751 fprintf_indent (f
, indent
, " {\n");
2752 for (int j
= 0; j
< p
->nargs
; ++j
)
2754 char child_opname
[20];
2755 preds
[i
]->gen_opname (child_opname
, j
);
2756 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2757 child_opname
, kid_opname
, j
);
2759 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2763 for (unsigned i
= 0; i
< others
.length (); ++i
)
2764 others
[i
]->gen (f
, indent
, gimple
);
2767 /* Generate matching code for the decision tree operand. */
2770 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2775 unsigned n_braces
= 0;
2777 if (type
== DT_OPERAND
)
2780 case operand::OP_PREDICATE
:
2781 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2784 case operand::OP_EXPR
:
2786 n_braces
= gen_gimple_expr (f
, indent
);
2788 n_braces
= gen_generic_expr (f
, indent
, opname
);
2794 else if (type
== DT_TRUE
)
2796 else if (type
== DT_MATCH
)
2797 n_braces
= gen_match_op (f
, indent
, opname
);
2801 indent
+= 4 * n_braces
;
2802 gen_kids (f
, indent
, gimple
);
2804 for (unsigned i
= 0; i
< n_braces
; ++i
)
2809 fprintf_indent (f
, indent
, " }\n");
2814 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2815 step of a '(simplify ...)' or '(match ...)'. This handles everything
2816 that is not part of the decision tree (simplify->match).
2817 Main recursive worker. */
2820 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2824 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2826 fprintf_indent (f
, indent
, "{\n");
2828 output_line_directive (f
, w
->location
);
2829 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2830 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2832 fprintf_indent (f
, indent
, "}\n");
2835 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2837 output_line_directive (f
, ife
->location
);
2838 fprintf_indent (f
, indent
, "if (");
2839 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2841 fprintf_indent (f
, indent
+ 2, "{\n");
2843 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2845 fprintf_indent (f
, indent
+ 2, "}\n");
2848 fprintf_indent (f
, indent
, "else\n");
2849 fprintf_indent (f
, indent
+ 2, "{\n");
2851 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2853 fprintf_indent (f
, indent
+ 2, "}\n");
2859 /* Analyze captures and perform early-outs on the incoming arguments
2860 that cover cases we cannot handle. */
2861 capture_info
cinfo (s
, result
, gimple
);
2862 if (s
->kind
== simplify::SIMPLIFY
)
2866 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2867 if (cinfo
.force_no_side_effects
& (1 << i
))
2869 fprintf_indent (f
, indent
,
2870 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2873 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
2874 "forcing toplevel operand to have no "
2877 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2878 if (cinfo
.info
[i
].cse_p
)
2880 else if (cinfo
.info
[i
].force_no_side_effects_p
2881 && (cinfo
.info
[i
].toplevel_msk
2882 & cinfo
.force_no_side_effects
) == 0)
2884 fprintf_indent (f
, indent
,
2885 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2886 "return NULL_TREE;\n", i
);
2888 warning_at (cinfo
.info
[i
].c
->location
,
2889 "forcing captured operand to have no "
2892 else if ((cinfo
.info
[i
].toplevel_msk
2893 & cinfo
.force_no_side_effects
) != 0)
2894 /* Mark capture as having no side-effects if we had to verify
2895 that via forced toplevel operand checks. */
2896 cinfo
.info
[i
].force_no_side_effects_p
= true;
2900 /* Force single-use restriction by only allowing simple
2901 results via setting seq to NULL. */
2902 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2903 bool first_p
= true;
2904 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2905 if (cinfo
.info
[i
].force_single_use
)
2909 fprintf_indent (f
, indent
, "if (lseq\n");
2910 fprintf_indent (f
, indent
, " && (");
2916 fprintf_indent (f
, indent
, " || ");
2918 fprintf (f
, "!single_use (captures[%d])", i
);
2922 fprintf (f
, "))\n");
2923 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2928 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2929 "fprintf (dump_file, \"Applying pattern ");
2930 output_line_directive (f
,
2931 result
? result
->location
: s
->match
->location
, true);
2932 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2936 /* If there is no result then this is a predicate implementation. */
2937 fprintf_indent (f
, indent
, "return true;\n");
2941 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2942 in outermost position). */
2943 if (result
->type
== operand::OP_EXPR
2944 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2945 result
= as_a
<expr
*> (result
)->ops
[0];
2946 if (result
->type
== operand::OP_EXPR
)
2948 expr
*e
= as_a
<expr
*> (result
);
2949 id_base
*opr
= e
->operation
;
2950 bool is_predicate
= false;
2951 /* When we delay operator substituting during lowering of fors we
2952 make sure that for code-gen purposes the effects of each substitute
2953 are the same. Thus just look at that. */
2954 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2955 opr
= uid
->substitutes
[0];
2956 else if (is_a
<predicate_id
*> (opr
))
2957 is_predicate
= true;
2959 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2960 *e
->operation
== CONVERT_EXPR
2961 ? "NOP_EXPR" : e
->operation
->id
);
2962 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2965 snprintf (dest
, 32, "res_ops[%d]", j
);
2967 = get_operand_type (opr
,
2968 "type", e
->expr_type
,
2969 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2970 /* We need to expand GENERIC conditions we captured from
2972 bool expand_generic_cond_exprs_p
2974 /* But avoid doing that if the GENERIC condition is
2975 valid - which it is in the first operand of COND_EXPRs
2976 and VEC_COND_EXRPs. */
2977 && ((!(*opr
== COND_EXPR
)
2978 && !(*opr
== VEC_COND_EXPR
))
2980 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
2982 indexes
, expand_generic_cond_exprs_p
);
2985 /* Re-fold the toplevel result. It's basically an embedded
2986 gimple_build w/o actually building the stmt. */
2988 fprintf_indent (f
, indent
,
2989 "gimple_resimplify%d (lseq, res_code, type, "
2990 "res_ops, valueize);\n", e
->ops
.length ());
2992 else if (result
->type
== operand::OP_CAPTURE
2993 || result
->type
== operand::OP_C_EXPR
)
2995 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
2996 &cinfo
, indexes
, false);
2997 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
2998 if (is_a
<capture
*> (result
)
2999 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
3001 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3002 with substituting a capture of that. */
3003 fprintf_indent (f
, indent
,
3004 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3005 fprintf_indent (f
, indent
,
3007 fprintf_indent (f
, indent
,
3008 " tree tem = res_ops[0];\n");
3009 fprintf_indent (f
, indent
,
3010 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3011 fprintf_indent (f
, indent
,
3012 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3013 fprintf_indent (f
, indent
,
3019 fprintf_indent (f
, indent
, "return true;\n");
3023 bool is_predicate
= false;
3024 if (result
->type
== operand::OP_EXPR
)
3026 expr
*e
= as_a
<expr
*> (result
);
3027 id_base
*opr
= e
->operation
;
3028 /* When we delay operator substituting during lowering of fors we
3029 make sure that for code-gen purposes the effects of each substitute
3030 are the same. Thus just look at that. */
3031 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3032 opr
= uid
->substitutes
[0];
3033 else if (is_a
<predicate_id
*> (opr
))
3034 is_predicate
= true;
3035 /* Search for captures used multiple times in the result expression
3036 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
3038 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3040 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3042 if (!cinfo
.info
[i
].force_no_side_effects_p
3043 && cinfo
.info
[i
].result_use_count
> 1)
3045 fprintf_indent (f
, indent
,
3046 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3048 fprintf_indent (f
, indent
,
3049 " captures[%d] = save_expr (captures[%d]);\n",
3053 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3057 snprintf (dest
, 32, "res_ops[%d]", j
);
3060 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3061 snprintf (dest
, 32, "res_op%d", j
);
3064 = get_operand_type (opr
,
3065 "type", e
->expr_type
,
3067 ? NULL
: "TREE_TYPE (res_op0)");
3068 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3072 fprintf_indent (f
, indent
, "return true;\n");
3075 fprintf_indent (f
, indent
, "tree res;\n");
3076 /* Re-fold the toplevel result. Use non_lvalue to
3077 build NON_LVALUE_EXPRs so they get properly
3078 ignored when in GIMPLE form. */
3079 if (*opr
== NON_LVALUE_EXPR
)
3080 fprintf_indent (f
, indent
,
3081 "res = non_lvalue_loc (loc, res_op0);\n");
3084 if (is_a
<operator_id
*> (opr
))
3085 fprintf_indent (f
, indent
,
3086 "res = fold_build%d_loc (loc, %s, type",
3088 *e
->operation
== CONVERT_EXPR
3089 ? "NOP_EXPR" : e
->operation
->id
);
3092 fprintf_indent (f
, indent
,
3094 fprintf_indent (f
, indent
,
3095 " tree decl = builtin_decl_implicit (%s);\n",
3097 fprintf_indent (f
, indent
,
3098 " if (!decl) return NULL_TREE;\n");
3099 fprintf_indent (f
, indent
,
3100 " res = build_call_expr_loc "
3104 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3105 fprintf (f
, ", res_op%d", j
);
3106 fprintf (f
, ");\n");
3107 if (!is_a
<operator_id
*> (opr
))
3108 fprintf_indent (f
, indent
, "}\n");
3112 else if (result
->type
== operand::OP_CAPTURE
3113 || result
->type
== operand::OP_C_EXPR
)
3116 fprintf_indent (f
, indent
, "tree res;\n");
3117 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3124 /* Search for captures not used in the result expression and dependent
3125 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3126 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3128 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3130 if (!cinfo
.info
[i
].force_no_side_effects_p
3131 && !cinfo
.info
[i
].expr_p
3132 && cinfo
.info
[i
].result_use_count
== 0)
3134 fprintf_indent (f
, indent
,
3135 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3137 fprintf_indent (f
, indent
+ 2,
3138 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3139 "fold_ignored_result (captures[%d]), res);\n",
3143 fprintf_indent (f
, indent
, "return res;\n");
3148 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3149 step of a '(simplify ...)' or '(match ...)'. This handles everything
3150 that is not part of the decision tree (simplify->match). */
3153 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3155 fprintf_indent (f
, indent
, "{\n");
3157 output_line_directive (f
,
3158 s
->result
? s
->result
->location
: s
->match
->location
);
3159 if (s
->capture_max
>= 0)
3162 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3163 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3165 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3166 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3167 fprintf (f
, " };\n");
3170 /* If we have a split-out function for the actual transform, call it. */
3171 if (info
&& info
->fname
)
3175 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3176 "valueize, type, captures", info
->fname
);
3177 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3178 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3179 fprintf (f
, "))\n");
3180 fprintf_indent (f
, indent
, " return true;\n");
3184 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3186 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3187 fprintf (f
, ", op%d", i
);
3188 fprintf (f
, ", captures");
3189 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3190 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3191 fprintf (f
, ");\n");
3192 fprintf_indent (f
, indent
, "if (res) return res;\n");
3197 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3199 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3200 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3201 s
->for_subst_vec
[i
].first
->id
,
3202 s
->for_subst_vec
[i
].second
->id
);
3203 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3204 fprintf_indent (f
, indent
, "enum built_in_function %s = %s;\n",
3205 s
->for_subst_vec
[i
].first
->id
,
3206 s
->for_subst_vec
[i
].second
->id
);
3210 gen_1 (f
, indent
, gimple
, s
->result
);
3214 fprintf_indent (f
, indent
, "}\n");
3218 /* Hash function for finding equivalent transforms. */
3221 sinfo_hashmap_traits::hash (const key_type
&v
)
3223 /* Only bother to compare those originating from the same source pattern. */
3224 return v
->s
->result
->location
;
3227 /* Compare function for finding equivalent transforms. */
3230 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3232 if (o1
->type
!= o2
->type
)
3237 case operand::OP_IF
:
3239 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3240 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3241 /* ??? Properly compare c-exprs. */
3242 if (if1
->cond
!= if2
->cond
)
3244 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3246 if (if1
->falseexpr
!= if2
->falseexpr
3248 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3252 case operand::OP_WITH
:
3254 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3255 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3256 if (with1
->with
!= with2
->with
)
3258 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3263 /* We've hit a result. Time to compare capture-infos - this is required
3264 in addition to the conservative pointer-equivalency of the result IL. */
3265 capture_info
cinfo1 (s1
, o1
, true);
3266 capture_info
cinfo2 (s2
, o2
, true);
3268 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3269 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3272 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3274 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3275 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3276 || (cinfo1
.info
[i
].force_no_side_effects_p
3277 != cinfo2
.info
[i
].force_no_side_effects_p
)
3278 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3279 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3280 /* toplevel_msk is an optimization */
3281 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3282 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3283 /* the pointer back to the capture is for diagnostics only */)
3287 /* ??? Deep-compare the actual result. */
3292 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3293 const key_type
&candidate
)
3295 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3299 /* Main entry to generate code for matching GIMPLE IL off the decision
3303 decision_tree::gen (FILE *f
, bool gimple
)
3309 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3310 "a total number of %u nodes\n",
3311 gimple
? "GIMPLE" : "GENERIC",
3312 root
->num_leafs
, root
->max_level
, root
->total_size
);
3314 /* First split out the transform part of equal leafs. */
3317 for (sinfo_map_t::iterator iter
= si
.begin ();
3318 iter
!= si
.end (); ++iter
)
3320 sinfo
*s
= (*iter
).second
;
3321 /* Do not split out single uses. */
3328 fprintf (stderr
, "found %u uses of", s
->cnt
);
3329 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3332 /* Generate a split out function with the leaf transform code. */
3333 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3336 fprintf (f
, "\nstatic bool\n"
3337 "%s (code_helper *res_code, tree *res_ops,\n"
3338 " gimple_seq *seq, tree (*valueize)(tree) "
3339 "ATTRIBUTE_UNUSED,\n"
3340 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3345 fprintf (f
, "\nstatic tree\n"
3346 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3347 (*iter
).second
->fname
);
3348 for (unsigned i
= 0;
3349 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3350 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3351 fprintf (f
, " tree *captures\n");
3353 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3355 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3356 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3357 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3358 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3359 fprintf (f
, ", enum built_in_function ARG_UNUSED (%s)",
3360 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3363 fprintf (f
, ")\n{\n");
3364 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3366 fprintf (f
, " return false;\n");
3368 fprintf (f
, " return NULL_TREE;\n");
3371 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3373 for (unsigned n
= 1; n
<= 3; ++n
)
3375 /* First generate split-out functions. */
3376 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3378 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3379 expr
*e
= static_cast<expr
*>(dop
->op
);
3380 if (e
->ops
.length () != n
3381 /* Builtin simplifications are somewhat premature on
3382 GENERIC. The following drops patterns with outermost
3383 calls. It's easy to emit overloads for function code
3384 though if necessary. */
3386 && e
->operation
->kind
!= id_base::CODE
))
3390 fprintf (f
, "\nstatic bool\n"
3391 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3392 " gimple_seq *seq, tree (*valueize)(tree) "
3393 "ATTRIBUTE_UNUSED,\n"
3394 " code_helper ARG_UNUSED (code), tree "
3395 "ARG_UNUSED (type)\n",
3398 fprintf (f
, "\nstatic tree\n"
3399 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3400 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3402 for (unsigned i
= 0; i
< n
; ++i
)
3403 fprintf (f
, ", tree op%d", i
);
3406 dop
->gen_kids (f
, 2, gimple
);
3408 fprintf (f
, " return false;\n");
3410 fprintf (f
, " return NULL_TREE;\n");
3414 /* Then generate the main entry with the outermost switch and
3415 tail-calls to the split-out functions. */
3417 fprintf (f
, "\nstatic bool\n"
3418 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3419 " gimple_seq *seq, tree (*valueize)(tree),\n"
3420 " code_helper code, tree type");
3422 fprintf (f
, "\ntree\n"
3423 "generic_simplify (location_t loc, enum tree_code code, "
3424 "tree type ATTRIBUTE_UNUSED");
3425 for (unsigned i
= 0; i
< n
; ++i
)
3426 fprintf (f
, ", tree op%d", i
);
3431 fprintf (f
, " switch (code.get_rep())\n"
3434 fprintf (f
, " switch (code)\n"
3436 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3438 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3439 expr
*e
= static_cast<expr
*>(dop
->op
);
3440 if (e
->ops
.length () != n
3441 /* Builtin simplifications are somewhat premature on
3442 GENERIC. The following drops patterns with outermost
3443 calls. It's easy to emit overloads for function code
3444 though if necessary. */
3446 && e
->operation
->kind
!= id_base::CODE
))
3449 if (*e
->operation
== CONVERT_EXPR
3450 || *e
->operation
== NOP_EXPR
)
3451 fprintf (f
, " CASE_CONVERT:\n");
3453 fprintf (f
, " case %s%s:\n",
3454 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3457 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3458 "seq, valueize, code, type", e
->operation
->id
);
3460 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3462 for (unsigned i
= 0; i
< n
; ++i
)
3463 fprintf (f
, ", op%d", i
);
3464 fprintf (f
, ");\n");
3466 fprintf (f
, " default:;\n"
3470 fprintf (f
, " return false;\n");
3472 fprintf (f
, " return NULL_TREE;\n");
3477 /* Output code to implement the predicate P from the decision tree DT. */
3480 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3482 fprintf (f
, "\nbool\n"
3483 "%s%s (tree t%s%s)\n"
3484 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3485 p
->nargs
> 0 ? ", tree *res_ops" : "",
3486 gimple
? ", tree (*valueize)(tree)" : "");
3487 /* Conveniently make 'type' available. */
3488 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3491 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3492 dt
.root
->gen_kids (f
, 2, gimple
);
3494 fprintf_indent (f
, 2, "return false;\n"
3498 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3501 write_header (FILE *f
, const char *head
)
3503 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3504 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3506 /* Include the header instead of writing it awkwardly quoted here. */
3507 fprintf (f
, "\n#include \"%s\"\n", head
);
3517 parser (cpp_reader
*);
3520 const cpp_token
*next ();
3521 const cpp_token
*peek (unsigned = 1);
3522 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3523 const cpp_token
*expect (enum cpp_ttype
);
3524 const cpp_token
*eat_token (enum cpp_ttype
);
3525 const char *get_string ();
3526 const char *get_ident ();
3527 const cpp_token
*eat_ident (const char *);
3528 const char *get_number ();
3530 id_base
*parse_operation ();
3531 operand
*parse_capture (operand
*, bool);
3532 operand
*parse_expr ();
3533 c_expr
*parse_c_expr (cpp_ttype
);
3534 operand
*parse_op ();
3536 void record_operlist (source_location
, user_id
*);
3538 void parse_pattern ();
3539 operand
*parse_result (operand
*, predicate_id
*);
3540 void push_simplify (simplify::simplify_kind
,
3541 vec
<simplify
*>&, operand
*, operand
*);
3542 void parse_simplify (simplify::simplify_kind
,
3543 vec
<simplify
*>&, predicate_id
*, operand
*);
3544 void parse_for (source_location
);
3545 void parse_if (source_location
);
3546 void parse_predicates (source_location
);
3547 void parse_operator_list (source_location
);
3550 vec
<c_expr
*> active_ifs
;
3551 vec
<vec
<user_id
*> > active_fors
;
3552 hash_set
<user_id
*> *oper_lists_set
;
3553 vec
<user_id
*> oper_lists
;
3555 cid_map_t
*capture_ids
;
3558 vec
<simplify
*> simplifiers
;
3559 vec
<predicate_id
*> user_predicates
;
3560 bool parsing_match_operand
;
3563 /* Lexing helpers. */
3565 /* Read the next non-whitespace token from R. */
3570 const cpp_token
*token
;
3573 token
= cpp_get_token (r
);
3575 while (token
->type
== CPP_PADDING
3576 && token
->type
!= CPP_EOF
);
3580 /* Peek at the next non-whitespace token from R. */
3583 parser::peek (unsigned num
)
3585 const cpp_token
*token
;
3589 token
= cpp_peek_token (r
, i
++);
3591 while ((token
->type
== CPP_PADDING
3592 && token
->type
!= CPP_EOF
)
3594 /* If we peek at EOF this is a fatal error as it leaves the
3595 cpp_reader in unusable state. Assume we really wanted a
3596 token and thus this EOF is unexpected. */
3597 if (token
->type
== CPP_EOF
)
3598 fatal_at (token
, "unexpected end of file");
3602 /* Peek at the next identifier token (or return NULL if the next
3603 token is not an identifier or equal to ID if supplied). */
3606 parser::peek_ident (const char *id
, unsigned num
)
3608 const cpp_token
*token
= peek (num
);
3609 if (token
->type
!= CPP_NAME
)
3615 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3616 if (strcmp (id
, t
) == 0)
3622 /* Read the next token from R and assert it is of type TK. */
3625 parser::expect (enum cpp_ttype tk
)
3627 const cpp_token
*token
= next ();
3628 if (token
->type
!= tk
)
3629 fatal_at (token
, "expected %s, got %s",
3630 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3635 /* Consume the next token from R and assert it is of type TK. */
3638 parser::eat_token (enum cpp_ttype tk
)
3643 /* Read the next token from R and assert it is of type CPP_STRING and
3644 return its value. */
3647 parser::get_string ()
3649 const cpp_token
*token
= expect (CPP_STRING
);
3650 return (const char *)token
->val
.str
.text
;
3653 /* Read the next token from R and assert it is of type CPP_NAME and
3654 return its value. */
3657 parser::get_ident ()
3659 const cpp_token
*token
= expect (CPP_NAME
);
3660 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3663 /* Eat an identifier token with value S from R. */
3666 parser::eat_ident (const char *s
)
3668 const cpp_token
*token
= peek ();
3669 const char *t
= get_ident ();
3670 if (strcmp (s
, t
) != 0)
3671 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3675 /* Read the next token from R and assert it is of type CPP_NUMBER and
3676 return its value. */
3679 parser::get_number ()
3681 const cpp_token
*token
= expect (CPP_NUMBER
);
3682 return (const char *)token
->val
.str
.text
;
3686 /* Record an operator-list use for transparent for handling. */
3689 parser::record_operlist (source_location loc
, user_id
*p
)
3691 if (!oper_lists_set
->add (p
))
3693 if (!oper_lists
.is_empty ()
3694 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3695 fatal_at (loc
, "User-defined operator list does not have the "
3696 "same number of entries as others used in the pattern");
3697 oper_lists
.safe_push (p
);
3701 /* Parse the operator ID, special-casing convert?, convert1? and
3705 parser::parse_operation ()
3707 const cpp_token
*id_tok
= peek ();
3708 const char *id
= get_ident ();
3709 const cpp_token
*token
= peek ();
3710 if (strcmp (id
, "convert0") == 0)
3711 fatal_at (id_tok
, "use 'convert?' here");
3712 else if (strcmp (id
, "view_convert0") == 0)
3713 fatal_at (id_tok
, "use 'view_convert?' here");
3714 if (token
->type
== CPP_QUERY
3715 && !(token
->flags
& PREV_WHITE
))
3717 if (strcmp (id
, "convert") == 0)
3719 else if (strcmp (id
, "convert1") == 0)
3721 else if (strcmp (id
, "convert2") == 0)
3723 else if (strcmp (id
, "view_convert") == 0)
3724 id
= "view_convert0";
3725 else if (strcmp (id
, "view_convert1") == 0)
3727 else if (strcmp (id
, "view_convert2") == 0)
3730 fatal_at (id_tok
, "non-convert operator conditionalized");
3732 if (!parsing_match_operand
)
3733 fatal_at (id_tok
, "conditional convert can only be used in "
3734 "match expression");
3735 eat_token (CPP_QUERY
);
3737 else if (strcmp (id
, "convert1") == 0
3738 || strcmp (id
, "convert2") == 0
3739 || strcmp (id
, "view_convert1") == 0
3740 || strcmp (id
, "view_convert2") == 0)
3741 fatal_at (id_tok
, "expected '?' after conditional operator");
3742 id_base
*op
= get_operator (id
);
3744 fatal_at (id_tok
, "unknown operator %s", id
);
3746 user_id
*p
= dyn_cast
<user_id
*> (op
);
3747 if (p
&& p
->is_oper_list
)
3749 if (active_fors
.length() == 0)
3750 record_operlist (id_tok
->src_loc
, p
);
3752 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3758 capture = '@'<number> */
3761 parser::parse_capture (operand
*op
, bool require_existing
)
3763 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3764 const cpp_token
*token
= peek ();
3765 const char *id
= NULL
;
3766 if (token
->type
== CPP_NUMBER
)
3768 else if (token
->type
== CPP_NAME
)
3771 fatal_at (token
, "expected number or identifier");
3772 unsigned next_id
= capture_ids
->elements ();
3774 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3777 if (require_existing
)
3778 fatal_at (src_loc
, "unknown capture id");
3781 return new capture (src_loc
, num
, op
);
3784 /* Parse an expression
3785 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3788 parser::parse_expr ()
3790 const cpp_token
*token
= peek ();
3791 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3794 bool is_commutative
= false;
3795 bool force_capture
= false;
3796 const char *expr_type
= NULL
;
3798 if (token
->type
== CPP_COLON
3799 && !(token
->flags
& PREV_WHITE
))
3801 eat_token (CPP_COLON
);
3803 if (token
->type
== CPP_NAME
3804 && !(token
->flags
& PREV_WHITE
))
3806 const char *s
= get_ident ();
3807 if (!parsing_match_operand
)
3815 is_commutative
= true;
3816 else if (*sp
== 's')
3818 e
->force_single_use
= true;
3819 force_capture
= true;
3822 fatal_at (token
, "flag %c not recognized", *sp
);
3829 fatal_at (token
, "expected flag or type specifying identifier");
3832 if (token
->type
== CPP_ATSIGN
3833 && !(token
->flags
& PREV_WHITE
))
3834 op
= parse_capture (e
, !parsing_match_operand
);
3835 else if (force_capture
)
3837 unsigned num
= capture_ids
->elements ();
3840 sprintf (id
, "__%u", num
);
3841 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3843 fatal_at (token
, "reserved capture id '%s' already used", id
);
3844 op
= new capture (token
->src_loc
, num
, e
);
3850 const cpp_token
*token
= peek ();
3851 if (token
->type
== CPP_CLOSE_PAREN
)
3853 if (e
->operation
->nargs
!= -1
3854 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3855 fatal_at (token
, "'%s' expects %u operands, not %u",
3856 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3859 if (e
->ops
.length () == 2)
3860 e
->is_commutative
= true;
3862 fatal_at (token
, "only binary operators or function with "
3863 "two arguments can be marked commutative");
3865 e
->expr_type
= expr_type
;
3868 else if (!(token
->flags
& PREV_WHITE
))
3869 fatal_at (token
, "expected expression operand");
3871 e
->append_op (parse_op ());
3876 /* Lex native C code delimited by START recording the preprocessing tokens
3877 for later processing.
3878 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3881 parser::parse_c_expr (cpp_ttype start
)
3883 const cpp_token
*token
;
3886 vec
<cpp_token
> code
= vNULL
;
3887 unsigned nr_stmts
= 0;
3888 source_location loc
= eat_token (start
)->src_loc
;
3889 if (start
== CPP_OPEN_PAREN
)
3890 end
= CPP_CLOSE_PAREN
;
3891 else if (start
== CPP_OPEN_BRACE
)
3892 end
= CPP_CLOSE_BRACE
;
3900 /* Count brace pairs to find the end of the expr to match. */
3901 if (token
->type
== start
)
3903 else if (token
->type
== end
3907 /* This is a lame way of counting the number of statements. */
3908 if (token
->type
== CPP_SEMICOLON
)
3911 /* If this is possibly a user-defined identifier mark it used. */
3912 if (token
->type
== CPP_NAME
)
3914 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3915 (token
->val
.node
.node
)->ident
.str
);
3917 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3918 record_operlist (token
->src_loc
, p
);
3921 /* Record the token. */
3922 code
.safe_push (*token
);
3925 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3928 /* Parse an operand which is either an expression, a predicate or
3929 a standalone capture.
3930 op = predicate | expr | c_expr | capture */
3935 const cpp_token
*token
= peek ();
3936 struct operand
*op
= NULL
;
3937 if (token
->type
== CPP_OPEN_PAREN
)
3939 eat_token (CPP_OPEN_PAREN
);
3941 eat_token (CPP_CLOSE_PAREN
);
3943 else if (token
->type
== CPP_OPEN_BRACE
)
3945 op
= parse_c_expr (CPP_OPEN_BRACE
);
3949 /* Remaining ops are either empty or predicates */
3950 if (token
->type
== CPP_NAME
)
3952 const char *id
= get_ident ();
3953 id_base
*opr
= get_operator (id
);
3955 fatal_at (token
, "expected predicate name");
3956 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3958 if (code
->nargs
!= 0)
3959 fatal_at (token
, "using an operator with operands as predicate");
3960 /* Parse the zero-operand operator "predicates" as
3962 op
= new expr (opr
, token
->src_loc
);
3964 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3966 if (code
->nargs
!= 0)
3967 fatal_at (token
, "using an operator with operands as predicate");
3968 /* Parse the zero-operand operator "predicates" as
3970 op
= new expr (opr
, token
->src_loc
);
3972 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3973 op
= new predicate (p
, token
->src_loc
);
3975 fatal_at (token
, "using an unsupported operator as predicate");
3976 if (!parsing_match_operand
)
3977 fatal_at (token
, "predicates are only allowed in match expression");
3979 if (token
->flags
& PREV_WHITE
)
3982 else if (token
->type
!= CPP_COLON
3983 && token
->type
!= CPP_ATSIGN
)
3984 fatal_at (token
, "expected expression or predicate");
3985 /* optionally followed by a capture and a predicate. */
3986 if (token
->type
== CPP_COLON
)
3987 fatal_at (token
, "not implemented: predicate on leaf operand");
3988 if (token
->type
== CPP_ATSIGN
)
3989 op
= parse_capture (op
, !parsing_match_operand
);
3995 /* Create a new simplify from the current parsing state and MATCH,
3996 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3999 parser::push_simplify (simplify::simplify_kind kind
,
4000 vec
<simplify
*>& simplifiers
,
4001 operand
*match
, operand
*result
)
4003 /* Build and push a temporary for operator list uses in expressions. */
4004 if (!oper_lists
.is_empty ())
4005 active_fors
.safe_push (oper_lists
);
4007 simplifiers
.safe_push
4008 (new simplify (kind
, match
, result
,
4009 active_fors
.copy (), capture_ids
));
4011 if (!oper_lists
.is_empty ())
4016 <result-op> = <op> | <if> | <with>
4017 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4018 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4022 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4024 const cpp_token
*token
= peek ();
4025 if (token
->type
!= CPP_OPEN_PAREN
)
4028 eat_token (CPP_OPEN_PAREN
);
4029 if (peek_ident ("if"))
4032 if_expr
*ife
= new if_expr (token
->src_loc
);
4033 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4034 if (peek ()->type
== CPP_OPEN_PAREN
)
4036 ife
->trueexpr
= parse_result (result
, matcher
);
4037 if (peek ()->type
== CPP_OPEN_PAREN
)
4038 ife
->falseexpr
= parse_result (result
, matcher
);
4039 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4040 ife
->falseexpr
= parse_op ();
4042 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4044 ife
->trueexpr
= parse_op ();
4045 if (peek ()->type
== CPP_OPEN_PAREN
)
4046 ife
->falseexpr
= parse_result (result
, matcher
);
4047 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4048 ife
->falseexpr
= parse_op ();
4050 /* If this if is immediately closed then it contains a
4051 manual matcher or is part of a predicate definition. */
4052 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4055 fatal_at (peek (), "manual transform not implemented");
4056 ife
->trueexpr
= result
;
4058 eat_token (CPP_CLOSE_PAREN
);
4061 else if (peek_ident ("with"))
4064 with_expr
*withe
= new with_expr (token
->src_loc
);
4065 /* Parse (with c-expr expr) as (if-with (true) expr). */
4066 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4067 withe
->with
->nr_stmts
= 0;
4068 withe
->subexpr
= parse_result (result
, matcher
);
4069 eat_token (CPP_CLOSE_PAREN
);
4072 else if (peek_ident ("switch"))
4074 token
= eat_ident ("switch");
4075 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4077 if_expr
*ife
= new if_expr (ifloc
);
4079 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4080 if (peek ()->type
== CPP_OPEN_PAREN
)
4081 ife
->trueexpr
= parse_result (result
, matcher
);
4083 ife
->trueexpr
= parse_op ();
4084 eat_token (CPP_CLOSE_PAREN
);
4085 if (peek ()->type
!= CPP_OPEN_PAREN
4086 || !peek_ident ("if", 2))
4087 fatal_at (token
, "switch can be implemented with a single if");
4088 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4090 if (peek ()->type
== CPP_OPEN_PAREN
)
4092 if (peek_ident ("if", 2))
4094 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4096 ife
->falseexpr
= new if_expr (ifloc
);
4097 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4098 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4099 if (peek ()->type
== CPP_OPEN_PAREN
)
4100 ife
->trueexpr
= parse_result (result
, matcher
);
4102 ife
->trueexpr
= parse_op ();
4103 eat_token (CPP_CLOSE_PAREN
);
4107 /* switch default clause */
4108 ife
->falseexpr
= parse_result (result
, matcher
);
4109 eat_token (CPP_CLOSE_PAREN
);
4115 /* switch default clause */
4116 ife
->falseexpr
= parse_op ();
4117 eat_token (CPP_CLOSE_PAREN
);
4121 eat_token (CPP_CLOSE_PAREN
);
4126 operand
*op
= result
;
4129 eat_token (CPP_CLOSE_PAREN
);
4135 simplify = 'simplify' <expr> <result-op>
4137 match = 'match' <ident> <expr> [<result-op>]
4138 and fill SIMPLIFIERS with the results. */
4141 parser::parse_simplify (simplify::simplify_kind kind
,
4142 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4145 /* Reset the capture map. */
4147 capture_ids
= new cid_map_t
;
4148 /* Reset oper_lists and set. */
4149 hash_set
<user_id
*> olist
;
4150 oper_lists_set
= &olist
;
4153 const cpp_token
*loc
= peek ();
4154 parsing_match_operand
= true;
4155 struct operand
*match
= parse_op ();
4156 parsing_match_operand
= false;
4157 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4158 fatal_at (loc
, "outermost expression cannot be captured");
4159 if (match
->type
== operand::OP_EXPR
4160 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4161 fatal_at (loc
, "outermost expression cannot be a predicate");
4163 /* Splice active_ifs onto result and continue parsing the
4165 if_expr
*active_if
= NULL
;
4166 for (int i
= active_ifs
.length (); i
> 0; --i
)
4168 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4169 ifc
->cond
= active_ifs
[i
-1];
4170 ifc
->trueexpr
= active_if
;
4173 if_expr
*outermost_if
= active_if
;
4174 while (active_if
&& active_if
->trueexpr
)
4175 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4177 const cpp_token
*token
= peek ();
4179 /* If this if is immediately closed then it is part of a predicate
4180 definition. Push it. */
4181 if (token
->type
== CPP_CLOSE_PAREN
)
4184 fatal_at (token
, "expected transform expression");
4187 active_if
->trueexpr
= result
;
4188 result
= outermost_if
;
4190 push_simplify (kind
, simplifiers
, match
, result
);
4194 operand
*tem
= parse_result (result
, matcher
);
4197 active_if
->trueexpr
= tem
;
4198 result
= outermost_if
;
4203 push_simplify (kind
, simplifiers
, match
, result
);
4206 /* Parsing of the outer control structures. */
4208 /* Parse a for expression
4209 for = '(' 'for' <subst>... <pattern> ')'
4210 subst = <ident> '(' <ident>... ')' */
4213 parser::parse_for (source_location
)
4215 auto_vec
<const cpp_token
*> user_id_tokens
;
4216 vec
<user_id
*> user_ids
= vNULL
;
4217 const cpp_token
*token
;
4218 unsigned min_n_opers
= 0, max_n_opers
= 0;
4223 if (token
->type
!= CPP_NAME
)
4226 /* Insert the user defined operators into the operator hash. */
4227 const char *id
= get_ident ();
4228 if (get_operator (id
) != NULL
)
4229 fatal_at (token
, "operator already defined");
4230 user_id
*op
= new user_id (id
);
4231 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4233 user_ids
.safe_push (op
);
4234 user_id_tokens
.safe_push (token
);
4236 eat_token (CPP_OPEN_PAREN
);
4239 while ((token
= peek_ident ()) != 0)
4241 const char *oper
= get_ident ();
4242 id_base
*idb
= get_operator (oper
);
4244 fatal_at (token
, "no such operator '%s'", oper
);
4245 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4246 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4247 || *idb
== VIEW_CONVERT2
)
4248 fatal_at (token
, "conditional operators cannot be used inside for");
4252 else if (idb
->nargs
== -1)
4254 else if (idb
->nargs
!= arity
)
4255 fatal_at (token
, "operator '%s' with arity %d does not match "
4256 "others with arity %d", oper
, idb
->nargs
, arity
);
4258 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4261 if (p
->is_oper_list
)
4262 op
->substitutes
.safe_splice (p
->substitutes
);
4264 fatal_at (token
, "iterator cannot be used as operator-list");
4267 op
->substitutes
.safe_push (idb
);
4270 token
= expect (CPP_CLOSE_PAREN
);
4272 unsigned nsubstitutes
= op
->substitutes
.length ();
4273 if (nsubstitutes
== 0)
4274 fatal_at (token
, "A user-defined operator must have at least "
4275 "one substitution");
4276 if (max_n_opers
== 0)
4278 min_n_opers
= nsubstitutes
;
4279 max_n_opers
= nsubstitutes
;
4283 if (nsubstitutes
% min_n_opers
!= 0
4284 && min_n_opers
% nsubstitutes
!= 0)
4285 fatal_at (token
, "All user-defined identifiers must have a "
4286 "multiple number of operator substitutions of the "
4287 "smallest number of substitutions");
4288 if (nsubstitutes
< min_n_opers
)
4289 min_n_opers
= nsubstitutes
;
4290 else if (nsubstitutes
> max_n_opers
)
4291 max_n_opers
= nsubstitutes
;
4295 unsigned n_ids
= user_ids
.length ();
4297 fatal_at (token
, "for requires at least one user-defined identifier");
4300 if (token
->type
== CPP_CLOSE_PAREN
)
4301 fatal_at (token
, "no pattern defined in for");
4303 active_fors
.safe_push (user_ids
);
4307 if (token
->type
== CPP_CLOSE_PAREN
)
4313 /* Remove user-defined operators from the hash again. */
4314 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4316 if (!user_ids
[i
]->used
)
4317 warning_at (user_id_tokens
[i
],
4318 "operator %s defined but not used", user_ids
[i
]->id
);
4319 operators
->remove_elt (user_ids
[i
]);
4323 /* Parse an identifier associated with a list of operators.
4324 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4327 parser::parse_operator_list (source_location
)
4329 const cpp_token
*token
= peek ();
4330 const char *id
= get_ident ();
4332 if (get_operator (id
) != 0)
4333 fatal_at (token
, "operator %s already defined", id
);
4335 user_id
*op
= new user_id (id
, true);
4338 while ((token
= peek_ident ()) != 0)
4341 const char *oper
= get_ident ();
4342 id_base
*idb
= get_operator (oper
);
4345 fatal_at (token
, "no such operator '%s'", oper
);
4349 else if (idb
->nargs
== -1)
4351 else if (arity
!= idb
->nargs
)
4352 fatal_at (token
, "operator '%s' with arity %d does not match "
4353 "others with arity %d", oper
, idb
->nargs
, arity
);
4355 /* We allow composition of multiple operator lists. */
4356 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4357 op
->substitutes
.safe_splice (p
->substitutes
);
4359 op
->substitutes
.safe_push (idb
);
4362 // Check that there is no junk after id-list
4364 if (token
->type
!= CPP_CLOSE_PAREN
)
4365 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4367 if (op
->substitutes
.length () == 0)
4368 fatal_at (token
, "operator-list cannot be empty");
4371 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4375 /* Parse an outer if expression.
4376 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4379 parser::parse_if (source_location
)
4381 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4383 const cpp_token
*token
= peek ();
4384 if (token
->type
== CPP_CLOSE_PAREN
)
4385 fatal_at (token
, "no pattern defined in if");
4387 active_ifs
.safe_push (ifexpr
);
4390 const cpp_token
*token
= peek ();
4391 if (token
->type
== CPP_CLOSE_PAREN
)
4399 /* Parse a list of predefined predicate identifiers.
4400 preds = '(' 'define_predicates' <ident>... ')' */
4403 parser::parse_predicates (source_location
)
4407 const cpp_token
*token
= peek ();
4408 if (token
->type
!= CPP_NAME
)
4411 add_predicate (get_ident ());
4416 /* Parse outer control structures.
4417 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4420 parser::parse_pattern ()
4422 /* All clauses start with '('. */
4423 eat_token (CPP_OPEN_PAREN
);
4424 const cpp_token
*token
= peek ();
4425 const char *id
= get_ident ();
4426 if (strcmp (id
, "simplify") == 0)
4428 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4431 else if (strcmp (id
, "match") == 0)
4433 bool with_args
= false;
4434 source_location e_loc
= peek ()->src_loc
;
4435 if (peek ()->type
== CPP_OPEN_PAREN
)
4437 eat_token (CPP_OPEN_PAREN
);
4440 const char *name
= get_ident ();
4441 id_base
*id
= get_operator (name
);
4445 p
= add_predicate (name
);
4446 user_predicates
.safe_push (p
);
4448 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4451 fatal_at (token
, "cannot add a match to a non-predicate ID");
4452 /* Parse (match <id> <arg>... (match-expr)) here. */
4456 capture_ids
= new cid_map_t
;
4457 e
= new expr (p
, e_loc
);
4458 while (peek ()->type
== CPP_ATSIGN
)
4459 e
->append_op (parse_capture (NULL
, false));
4460 eat_token (CPP_CLOSE_PAREN
);
4463 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4464 || (!e
&& p
->nargs
!= 0)))
4465 fatal_at (token
, "non-matching number of match operands");
4466 p
->nargs
= e
? e
->ops
.length () : 0;
4467 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4470 else if (strcmp (id
, "for") == 0)
4471 parse_for (token
->src_loc
);
4472 else if (strcmp (id
, "if") == 0)
4473 parse_if (token
->src_loc
);
4474 else if (strcmp (id
, "define_predicates") == 0)
4476 if (active_ifs
.length () > 0
4477 || active_fors
.length () > 0)
4478 fatal_at (token
, "define_predicates inside if or for is not supported");
4479 parse_predicates (token
->src_loc
);
4481 else if (strcmp (id
, "define_operator_list") == 0)
4483 if (active_ifs
.length () > 0
4484 || active_fors
.length () > 0)
4485 fatal_at (token
, "operator-list inside if or for is not supported");
4486 parse_operator_list (token
->src_loc
);
4489 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4490 active_ifs
.length () == 0 && active_fors
.length () == 0
4491 ? "'define_predicates', " : "");
4493 eat_token (CPP_CLOSE_PAREN
);
4496 /* Main entry of the parser. Repeatedly parse outer control structures. */
4498 parser::parser (cpp_reader
*r_
)
4502 active_fors
= vNULL
;
4503 simplifiers
= vNULL
;
4504 oper_lists_set
= NULL
;
4507 user_predicates
= vNULL
;
4508 parsing_match_operand
= false;
4510 const cpp_token
*token
= next ();
4511 while (token
->type
!= CPP_EOF
)
4513 _cpp_backup_tokens (r
, 1);
4520 /* Helper for the linemap code. */
4523 round_alloc_size (size_t s
)
4529 /* The genmatch generator progam. It reads from a pattern description
4530 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4533 main (int argc
, char **argv
)
4537 progname
= "genmatch";
4543 char *input
= argv
[argc
-1];
4544 for (int i
= 1; i
< argc
- 1; ++i
)
4546 if (strcmp (argv
[i
], "--gimple") == 0)
4548 else if (strcmp (argv
[i
], "--generic") == 0)
4550 else if (strcmp (argv
[i
], "-v") == 0)
4552 else if (strcmp (argv
[i
], "-vv") == 0)
4556 fprintf (stderr
, "Usage: genmatch "
4557 "[--gimple] [--generic] [-v[v]] input\n");
4562 line_table
= XCNEW (struct line_maps
);
4563 linemap_init (line_table
, 0);
4564 line_table
->reallocator
= xrealloc
;
4565 line_table
->round_alloc_size
= round_alloc_size
;
4567 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4568 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4569 cb
->error
= error_cb
;
4571 if (!cpp_read_main_file (r
, input
))
4573 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4574 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4576 /* Pre-seed operators. */
4577 operators
= new hash_table
<id_base
> (1024);
4578 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4579 add_operator (SYM, # SYM, # TYPE, NARGS);
4580 #define END_OF_BASE_TREE_CODES
4582 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4583 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4584 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4585 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4586 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4587 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4588 #undef END_OF_BASE_TREE_CODES
4591 /* Pre-seed builtin functions.
4592 ??? Cannot use N (name) as that is targetm.emultls.get_address
4593 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4594 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4595 add_builtin (ENUM, # ENUM);
4596 #include "builtins.def"
4603 write_header (stdout
, "gimple-match-head.c");
4605 write_header (stdout
, "generic-match-head.c");
4607 /* Go over all predicates defined with patterns and perform
4608 lowering and code generation. */
4609 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4611 predicate_id
*pred
= p
.user_predicates
[i
];
4612 lower (pred
->matchers
, gimple
);
4615 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4616 print_matches (pred
->matchers
[i
]);
4619 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4620 dt
.insert (pred
->matchers
[i
], i
);
4625 write_predicate (stdout
, pred
, dt
, gimple
);
4628 /* Lower the main simplifiers and generate code for them. */
4629 lower (p
.simplifiers
, gimple
);
4632 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4633 print_matches (p
.simplifiers
[i
]);
4636 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4637 dt
.insert (p
.simplifiers
[i
], i
);
4642 dt
.gen (stdout
, gimple
);
4645 cpp_finish (r
, NULL
);