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 fprintf (f
, "@%u", c
->where
);
714 if (c
->what
&& flattened
== false)
717 print_operand (c
->what
, f
, flattened
);
722 else if (predicate
*p
= dyn_cast
<predicate
*> (o
))
723 fprintf (f
, "%s", p
->p
->id
);
725 else if (is_a
<c_expr
*> (o
))
726 fprintf (f
, "c_expr");
728 else if (expr
*e
= dyn_cast
<expr
*> (o
))
730 fprintf (f
, "(%s", e
->operation
->id
);
732 if (flattened
== false)
735 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 return append_node (n
);
1569 /* Analyze the node and its children. */
1572 dt_node::analyze (sinfo_map_t
&map
)
1578 if (type
== DT_SIMPLIFY
)
1580 /* Populate the map of equivalent simplifies. */
1581 dt_simplify
*s
= as_a
<dt_simplify
*> (this);
1583 sinfo
*&si
= map
.get_or_insert (s
, &existed
);
1598 for (unsigned i
= 0; i
< kids
.length (); ++i
)
1600 kids
[i
]->analyze (map
);
1601 num_leafs
+= kids
[i
]->num_leafs
;
1602 total_size
+= kids
[i
]->total_size
;
1603 max_level
= MAX (max_level
, kids
[i
]->max_level
);
1607 /* Insert O into the decision tree and return the decision tree node found
1611 decision_tree::insert_operand (dt_node
*p
, operand
*o
, dt_operand
**indexes
,
1612 unsigned pos
, dt_node
*parent
)
1614 dt_node
*q
, *elm
= 0;
1616 if (capture
*c
= dyn_cast
<capture
*> (o
))
1618 unsigned capt_index
= c
->where
;
1620 if (indexes
[capt_index
] == 0)
1623 q
= insert_operand (p
, c
->what
, indexes
, pos
, parent
);
1626 q
= elm
= p
->append_true_op (parent
, pos
);
1629 // get to the last capture
1630 for (operand
*what
= c
->what
;
1631 what
&& is_a
<capture
*> (what
);
1632 c
= as_a
<capture
*> (what
), what
= c
->what
)
1637 unsigned cc_index
= c
->where
;
1638 dt_operand
*match_op
= indexes
[cc_index
];
1640 dt_operand
temp (dt_node::DT_TRUE
, 0, 0);
1641 elm
= decision_tree::find_node (p
->kids
, &temp
);
1645 dt_operand
temp (dt_node::DT_MATCH
, 0, match_op
);
1646 elm
= decision_tree::find_node (p
->kids
, &temp
);
1651 dt_operand
temp (dt_node::DT_OPERAND
, c
->what
, 0);
1652 elm
= decision_tree::find_node (p
->kids
, &temp
);
1656 gcc_assert (elm
->type
== dt_node::DT_TRUE
1657 || elm
->type
== dt_node::DT_OPERAND
1658 || elm
->type
== dt_node::DT_MATCH
);
1659 indexes
[capt_index
] = static_cast<dt_operand
*> (elm
);
1664 p
= p
->append_match_op (indexes
[capt_index
], parent
, pos
);
1666 return insert_operand (p
, c
->what
, indexes
, 0, p
);
1671 p
= p
->append_op (o
, parent
, pos
);
1674 if (expr
*e
= dyn_cast
<expr
*>(o
))
1676 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1677 q
= decision_tree::insert_operand (q
, e
->ops
[i
], indexes
, i
, p
);
1683 /* Insert S into the decision tree. */
1686 decision_tree::insert (struct simplify
*s
, unsigned pattern_no
)
1688 dt_operand
**indexes
= XCNEWVEC (dt_operand
*, s
->capture_max
+ 1);
1689 dt_node
*p
= decision_tree::insert_operand (root
, s
->match
, indexes
);
1690 p
->append_simplify (s
, pattern_no
, indexes
);
1693 /* Debug functions to dump the decision tree. */
1696 decision_tree::print_node (dt_node
*p
, FILE *f
, unsigned indent
)
1698 if (p
->type
== dt_node::DT_NODE
)
1699 fprintf (f
, "root");
1703 for (unsigned i
= 0; i
< indent
; i
++)
1706 if (p
->type
== dt_node::DT_OPERAND
)
1708 dt_operand
*dop
= static_cast<dt_operand
*>(p
);
1709 print_operand (dop
->op
, f
, true);
1711 else if (p
->type
== dt_node::DT_TRUE
)
1712 fprintf (f
, "true");
1713 else if (p
->type
== dt_node::DT_MATCH
)
1714 fprintf (f
, "match (%p)", (void *)((as_a
<dt_operand
*>(p
))->match_dop
));
1715 else if (p
->type
== dt_node::DT_SIMPLIFY
)
1717 dt_simplify
*s
= static_cast<dt_simplify
*> (p
);
1718 fprintf (f
, "simplify_%u { ", s
->pattern_no
);
1719 for (int i
= 0; i
<= s
->s
->capture_max
; ++i
)
1720 fprintf (f
, "%p, ", (void *) s
->indexes
[i
]);
1725 fprintf (stderr
, " (%p), %u, %u\n", (void *) p
, p
->level
, p
->kids
.length ());
1727 for (unsigned i
= 0; i
< p
->kids
.length (); ++i
)
1728 decision_tree::print_node (p
->kids
[i
], f
, indent
+ 2);
1732 decision_tree::print (FILE *f
)
1734 return decision_tree::print_node (root
, f
);
1738 /* For GENERIC we have to take care of wrapping multiple-used
1739 expressions with side-effects in save_expr and preserve side-effects
1740 of expressions with omit_one_operand. Analyze captures in
1741 match, result and with expressions and perform early-outs
1742 on the outermost match expression operands for cases we cannot
1747 capture_info (simplify
*s
, operand
*, bool);
1748 void walk_match (operand
*o
, unsigned toplevel_arg
, bool, bool);
1749 bool walk_result (operand
*o
, bool, operand
*);
1750 void walk_c_expr (c_expr
*);
1756 bool force_no_side_effects_p
;
1757 bool force_single_use
;
1758 bool cond_expr_cond_p
;
1759 unsigned long toplevel_msk
;
1760 int result_use_count
;
1765 auto_vec
<cinfo
> info
;
1766 unsigned long force_no_side_effects
;
1770 /* Analyze captures in S. */
1772 capture_info::capture_info (simplify
*s
, operand
*result
, bool gimple_
)
1777 if (s
->kind
== simplify::MATCH
)
1779 force_no_side_effects
= -1;
1783 force_no_side_effects
= 0;
1784 info
.safe_grow_cleared (s
->capture_max
+ 1);
1785 for (int i
= 0; i
<= s
->capture_max
; ++i
)
1786 info
[i
].same_as
= i
;
1788 e
= as_a
<expr
*> (s
->match
);
1789 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1790 walk_match (e
->ops
[i
], i
,
1791 (i
!= 0 && *e
->operation
== COND_EXPR
)
1792 || *e
->operation
== TRUTH_ANDIF_EXPR
1793 || *e
->operation
== TRUTH_ORIF_EXPR
,
1795 && (*e
->operation
== COND_EXPR
1796 || *e
->operation
== VEC_COND_EXPR
));
1798 walk_result (s
->result
, false, result
);
1801 /* Analyze captures in the match expression piece O. */
1804 capture_info::walk_match (operand
*o
, unsigned toplevel_arg
,
1805 bool conditional_p
, bool cond_expr_cond_p
)
1807 if (capture
*c
= dyn_cast
<capture
*> (o
))
1809 unsigned where
= c
->where
;
1810 info
[where
].toplevel_msk
|= 1 << toplevel_arg
;
1811 info
[where
].force_no_side_effects_p
|= conditional_p
;
1812 info
[where
].cond_expr_cond_p
|= cond_expr_cond_p
;
1817 /* Recurse to exprs and captures. */
1818 if (is_a
<capture
*> (c
->what
)
1819 || is_a
<expr
*> (c
->what
))
1820 walk_match (c
->what
, toplevel_arg
, conditional_p
, false);
1821 /* We need to look past multiple captures to find a captured
1822 expression as with conditional converts two captures
1823 can be collapsed onto the same expression. Also collect
1824 what captures capture the same thing. */
1825 while (c
->what
&& is_a
<capture
*> (c
->what
))
1827 c
= as_a
<capture
*> (c
->what
);
1828 if (info
[c
->where
].same_as
!= c
->where
1829 && info
[c
->where
].same_as
!= info
[where
].same_as
)
1830 fatal_at (c
->location
, "cannot handle this collapsed capture");
1831 info
[c
->where
].same_as
= info
[where
].same_as
;
1833 /* Mark expr (non-leaf) captures and forced single-use exprs. */
1836 && (e
= dyn_cast
<expr
*> (c
->what
)))
1838 info
[where
].expr_p
= true;
1839 info
[where
].force_single_use
|= e
->force_single_use
;
1842 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1844 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1846 bool cond_p
= conditional_p
;
1847 bool cond_expr_cond_p
= false;
1848 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1850 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1851 || *e
->operation
== TRUTH_ORIF_EXPR
)
1854 && (*e
->operation
== COND_EXPR
1855 || *e
->operation
== VEC_COND_EXPR
))
1856 cond_expr_cond_p
= true;
1857 walk_match (e
->ops
[i
], toplevel_arg
, cond_p
, cond_expr_cond_p
);
1860 else if (is_a
<predicate
*> (o
))
1862 /* Mark non-captured leafs toplevel arg for checking. */
1863 force_no_side_effects
|= 1 << toplevel_arg
;
1866 warning_at (o
->location
,
1867 "forcing no side-effects on possibly lost leaf");
1873 /* Analyze captures in the result expression piece O. Return true
1874 if RESULT was visited in one of the children. Only visit
1875 non-if/with children if they are rooted on RESULT. */
1878 capture_info::walk_result (operand
*o
, bool conditional_p
, operand
*result
)
1880 if (capture
*c
= dyn_cast
<capture
*> (o
))
1882 unsigned where
= info
[c
->where
].same_as
;
1883 info
[where
].result_use_count
++;
1884 /* If we substitute an expression capture we don't know
1885 which captures this will end up using (well, we don't
1886 compute that). Force the uses to be side-effect free
1887 which means forcing the toplevels that reach the
1888 expression side-effect free. */
1889 if (info
[where
].expr_p
)
1890 force_no_side_effects
|= info
[where
].toplevel_msk
;
1891 /* Mark CSE capture uses as forced to have no side-effects. */
1893 && is_a
<expr
*> (c
->what
))
1895 info
[where
].cse_p
= true;
1896 walk_result (c
->what
, true, result
);
1899 else if (expr
*e
= dyn_cast
<expr
*> (o
))
1901 id_base
*opr
= e
->operation
;
1902 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
1903 opr
= uid
->substitutes
[0];
1904 for (unsigned i
= 0; i
< e
->ops
.length (); ++i
)
1906 bool cond_p
= conditional_p
;
1907 if (i
!= 0 && *e
->operation
== COND_EXPR
)
1909 else if (*e
->operation
== TRUTH_ANDIF_EXPR
1910 || *e
->operation
== TRUTH_ORIF_EXPR
)
1912 walk_result (e
->ops
[i
], cond_p
, result
);
1915 else if (if_expr
*e
= dyn_cast
<if_expr
*> (o
))
1917 /* 'if' conditions should be all fine. */
1918 if (e
->trueexpr
== result
)
1920 walk_result (e
->trueexpr
, false, result
);
1923 if (e
->falseexpr
== result
)
1925 walk_result (e
->falseexpr
, false, result
);
1929 if (is_a
<if_expr
*> (e
->trueexpr
)
1930 || is_a
<with_expr
*> (e
->trueexpr
))
1931 res
|= walk_result (e
->trueexpr
, false, result
);
1933 && (is_a
<if_expr
*> (e
->falseexpr
)
1934 || is_a
<with_expr
*> (e
->falseexpr
)))
1935 res
|= walk_result (e
->falseexpr
, false, result
);
1938 else if (with_expr
*e
= dyn_cast
<with_expr
*> (o
))
1940 bool res
= (e
->subexpr
== result
);
1942 || is_a
<if_expr
*> (e
->subexpr
)
1943 || is_a
<with_expr
*> (e
->subexpr
))
1944 res
|= walk_result (e
->subexpr
, false, result
);
1946 walk_c_expr (e
->with
);
1949 else if (c_expr
*e
= dyn_cast
<c_expr
*> (o
))
1957 /* Look for captures in the C expr E. */
1960 capture_info::walk_c_expr (c_expr
*e
)
1962 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
1963 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
1964 really escape through. */
1965 unsigned p_depth
= 0;
1966 for (unsigned i
= 0; i
< e
->code
.length (); ++i
)
1968 const cpp_token
*t
= &e
->code
[i
];
1969 const cpp_token
*n
= i
< e
->code
.length () - 1 ? &e
->code
[i
+1] : NULL
;
1971 if (t
->type
== CPP_NAME
1972 && (strcmp ((const char *)CPP_HASHNODE
1973 (t
->val
.node
.node
)->ident
.str
, "TREE_TYPE") == 0
1974 || strcmp ((const char *)CPP_HASHNODE
1975 (t
->val
.node
.node
)->ident
.str
, "TREE_CODE") == 0
1976 || strcmp ((const char *)CPP_HASHNODE
1977 (t
->val
.node
.node
)->ident
.str
, "TREE_REAL_CST") == 0
1978 || ((id
= get_operator ((const char *)CPP_HASHNODE
1979 (t
->val
.node
.node
)->ident
.str
))
1980 && is_a
<predicate_id
*> (id
)))
1981 && n
->type
== CPP_OPEN_PAREN
)
1983 else if (t
->type
== CPP_CLOSE_PAREN
1986 else if (p_depth
== 0
1987 && t
->type
== CPP_ATSIGN
1988 && (n
->type
== CPP_NUMBER
1989 || n
->type
== CPP_NAME
)
1990 && !(n
->flags
& PREV_WHITE
))
1993 if (n
->type
== CPP_NUMBER
)
1994 id
= (const char *)n
->val
.str
.text
;
1996 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
1997 unsigned where
= *e
->capture_ids
->get(id
);
1998 info
[info
[where
].same_as
].force_no_side_effects_p
= true;
2001 warning_at (t
, "capture escapes");
2007 /* Code generation off the decision tree and the refered AST nodes. */
2010 is_conversion (id_base
*op
)
2012 return (*op
== CONVERT_EXPR
2014 || *op
== FLOAT_EXPR
2015 || *op
== FIX_TRUNC_EXPR
2016 || *op
== VIEW_CONVERT_EXPR
);
2019 /* Get the type to be used for generating operands of OP from the
2023 get_operand_type (id_base
*op
, const char *in_type
,
2024 const char *expr_type
,
2025 const char *other_oprnd_type
)
2027 /* Generally operands whose type does not match the type of the
2028 expression generated need to know their types but match and
2029 thus can fall back to 'other_oprnd_type'. */
2030 if (is_conversion (op
))
2031 return other_oprnd_type
;
2032 else if (*op
== REALPART_EXPR
2033 || *op
== IMAGPART_EXPR
)
2034 return other_oprnd_type
;
2035 else if (is_a
<operator_id
*> (op
)
2036 && strcmp (as_a
<operator_id
*> (op
)->tcc
, "tcc_comparison") == 0)
2037 return other_oprnd_type
;
2040 /* Otherwise all types should match - choose one in order of
2047 return other_oprnd_type
;
2051 /* Generate transform code for an expression. */
2054 expr::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2055 int depth
, const char *in_type
, capture_info
*cinfo
,
2056 dt_operand
**indexes
, bool)
2058 id_base
*opr
= operation
;
2059 /* When we delay operator substituting during lowering of fors we
2060 make sure that for code-gen purposes the effects of each substitute
2061 are the same. Thus just look at that. */
2062 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2063 opr
= uid
->substitutes
[0];
2065 bool conversion_p
= is_conversion (opr
);
2066 const char *type
= expr_type
;
2069 /* If there was a type specification in the pattern use it. */
2071 else if (conversion_p
)
2072 /* For conversions we need to build the expression using the
2073 outer type passed in. */
2075 else if (*opr
== REALPART_EXPR
2076 || *opr
== IMAGPART_EXPR
)
2078 /* __real and __imag use the component type of its operand. */
2079 sprintf (optype
, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth
);
2082 else if (is_a
<operator_id
*> (opr
)
2083 && !strcmp (as_a
<operator_id
*> (opr
)->tcc
, "tcc_comparison"))
2085 /* comparisons use boolean_type_node (or what gets in), but
2086 their operands need to figure out the types themselves. */
2087 sprintf (optype
, "boolean_type_node");
2090 else if (*opr
== COND_EXPR
2091 || *opr
== VEC_COND_EXPR
)
2093 /* Conditions are of the same type as their first alternative. */
2094 sprintf (optype
, "TREE_TYPE (ops%d[1])", depth
);
2099 /* Other operations are of the same type as their first operand. */
2100 sprintf (optype
, "TREE_TYPE (ops%d[0])", depth
);
2104 fatal_at (location
, "cannot determine type of operand");
2106 fprintf_indent (f
, indent
, "{\n");
2108 fprintf_indent (f
, indent
, "tree ops%d[%u], res;\n", depth
, ops
.length ());
2110 snprintf (op0type
, 64, "TREE_TYPE (ops%d[0])", depth
);
2111 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2114 snprintf (dest
, 32, "ops%d[%u]", depth
, i
);
2116 = get_operand_type (opr
, in_type
, expr_type
,
2117 i
== 0 ? NULL
: op0type
);
2118 ops
[i
]->gen_transform (f
, indent
, dest
, gimple
, depth
+ 1, optype
,
2120 ((!(*opr
== COND_EXPR
)
2121 && !(*opr
== VEC_COND_EXPR
))
2125 const char *opr_name
;
2126 if (*operation
== CONVERT_EXPR
)
2127 opr_name
= "NOP_EXPR";
2129 opr_name
= operation
->id
;
2133 if (*opr
== CONVERT_EXPR
)
2135 fprintf_indent (f
, indent
,
2136 "if (%s != TREE_TYPE (ops%d[0])\n",
2138 fprintf_indent (f
, indent
,
2139 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2141 fprintf_indent (f
, indent
+ 2, "{\n");
2144 /* ??? Building a stmt can fail for various reasons here, seq being
2145 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2146 So if we fail here we should continue matching other patterns. */
2147 fprintf_indent (f
, indent
, "code_helper tem_code = %s;\n", opr_name
);
2148 fprintf_indent (f
, indent
, "tree tem_ops[3] = { ");
2149 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2150 fprintf (f
, "ops%d[%u]%s", depth
, i
,
2151 i
== ops
.length () - 1 ? " };\n" : ", ");
2152 fprintf_indent (f
, indent
,
2153 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2154 ops
.length (), type
);
2155 fprintf_indent (f
, indent
,
2156 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2158 fprintf_indent (f
, indent
,
2159 "if (!res) return false;\n");
2160 if (*opr
== CONVERT_EXPR
)
2163 fprintf_indent (f
, indent
, " }\n");
2164 fprintf_indent (f
, indent
, "else\n");
2165 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2170 if (*opr
== CONVERT_EXPR
)
2172 fprintf_indent (f
, indent
, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2176 if (opr
->kind
== id_base::CODE
)
2177 fprintf_indent (f
, indent
, "res = fold_build%d_loc (loc, %s, %s",
2178 ops
.length(), opr_name
, type
);
2181 fprintf_indent (f
, indent
, "{\n");
2182 fprintf_indent (f
, indent
, " tree decl = builtin_decl_implicit (%s);\n",
2184 fprintf_indent (f
, indent
, " if (!decl) return NULL_TREE;\n");
2185 fprintf_indent (f
, indent
, " res = build_call_expr_loc (loc, "
2186 "decl, %d", ops
.length());
2188 for (unsigned i
= 0; i
< ops
.length (); ++i
)
2189 fprintf (f
, ", ops%d[%u]", depth
, i
);
2190 fprintf (f
, ");\n");
2191 if (opr
->kind
!= id_base::CODE
)
2192 fprintf_indent (f
, indent
, "}\n");
2193 if (*opr
== CONVERT_EXPR
)
2196 fprintf_indent (f
, indent
, "else\n");
2197 fprintf_indent (f
, indent
, " res = ops%d[0];\n", depth
);
2200 fprintf_indent (f
, indent
, "%s = res;\n", dest
);
2202 fprintf_indent (f
, indent
, "}\n");
2205 /* Generate code for a c_expr which is either the expression inside
2206 an if statement or a sequence of statements which computes a
2207 result to be stored to DEST. */
2210 c_expr::gen_transform (FILE *f
, int indent
, const char *dest
,
2211 bool, int, const char *, capture_info
*,
2212 dt_operand
**, bool)
2214 if (dest
&& nr_stmts
== 1)
2215 fprintf_indent (f
, indent
, "%s = ", dest
);
2217 unsigned stmt_nr
= 1;
2218 for (unsigned i
= 0; i
< code
.length (); ++i
)
2220 const cpp_token
*token
= &code
[i
];
2222 /* Replace captures for code-gen. */
2223 if (token
->type
== CPP_ATSIGN
)
2225 const cpp_token
*n
= &code
[i
+1];
2226 if ((n
->type
== CPP_NUMBER
2227 || n
->type
== CPP_NAME
)
2228 && !(n
->flags
& PREV_WHITE
))
2230 if (token
->flags
& PREV_WHITE
)
2233 if (n
->type
== CPP_NUMBER
)
2234 id
= (const char *)n
->val
.str
.text
;
2236 id
= (const char *)CPP_HASHNODE (n
->val
.node
.node
)->ident
.str
;
2237 unsigned *cid
= capture_ids
->get (id
);
2239 fatal_at (token
, "unknown capture id");
2240 fprintf (f
, "captures[%u]", *cid
);
2246 if (token
->flags
& PREV_WHITE
)
2249 if (token
->type
== CPP_NAME
)
2251 const char *id
= (const char *) NODE_NAME (token
->val
.node
.node
);
2253 for (j
= 0; j
< ids
.length (); ++j
)
2255 if (strcmp (id
, ids
[j
].id
) == 0)
2257 fprintf (f
, "%s", ids
[j
].oper
);
2261 if (j
< ids
.length ())
2265 /* Output the token as string. */
2266 char *tk
= (char *)cpp_token_as_text (r
, token
);
2269 if (token
->type
== CPP_SEMICOLON
)
2273 if (dest
&& stmt_nr
== nr_stmts
)
2274 fprintf_indent (f
, indent
, "%s = ", dest
);
2279 /* Generate transform code for a capture. */
2282 capture::gen_transform (FILE *f
, int indent
, const char *dest
, bool gimple
,
2283 int depth
, const char *in_type
, capture_info
*cinfo
,
2284 dt_operand
**indexes
, bool expand_compares
)
2286 if (what
&& is_a
<expr
*> (what
))
2288 if (indexes
[where
] == 0)
2291 sprintf (buf
, "captures[%u]", where
);
2292 what
->gen_transform (f
, indent
, buf
, gimple
, depth
, in_type
,
2297 fprintf_indent (f
, indent
, "%s = captures[%u];\n", dest
, where
);
2299 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2300 with substituting a capture of that.
2301 ??? Returning false here will also not allow any other patterns
2303 if (gimple
&& expand_compares
2304 && cinfo
->info
[where
].cond_expr_cond_p
)
2306 fprintf_indent (f
, indent
, "if (COMPARISON_CLASS_P (%s))\n", dest
);
2307 fprintf_indent (f
, indent
, " {\n");
2308 fprintf_indent (f
, indent
, " if (!seq) return false;\n");
2309 fprintf_indent (f
, indent
, " %s = gimple_build (seq, TREE_CODE (%s),"
2310 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2311 " TREE_OPERAND (%s, 1));\n",
2312 dest
, dest
, dest
, dest
, dest
);
2313 fprintf_indent (f
, indent
, " }\n");
2317 /* Return the name of the operand representing the decision tree node.
2318 Use NAME as space to generate it. */
2321 dt_operand::get_name (char *name
)
2324 sprintf (name
, "t");
2325 else if (parent
->level
== 1)
2326 sprintf (name
, "op%u", pos
);
2327 else if (parent
->type
== dt_node::DT_MATCH
)
2328 return parent
->get_name (name
);
2330 sprintf (name
, "o%u%u", parent
->level
, pos
);
2334 /* Fill NAME with the operand name at position POS. */
2337 dt_operand::gen_opname (char *name
, unsigned pos
)
2340 sprintf (name
, "op%u", pos
);
2342 sprintf (name
, "o%u%u", level
, pos
);
2345 /* Generate matching code for the decision tree operand which is
2349 dt_operand::gen_predicate (FILE *f
, int indent
, const char *opname
, bool gimple
)
2351 predicate
*p
= as_a
<predicate
*> (op
);
2353 if (p
->p
->matchers
.exists ())
2355 /* If this is a predicate generated from a pattern mangle its
2356 name and pass on the valueize hook. */
2358 fprintf_indent (f
, indent
, "if (gimple_%s (%s, valueize))\n",
2361 fprintf_indent (f
, indent
, "if (tree_%s (%s))\n", p
->p
->id
, opname
);
2364 fprintf_indent (f
, indent
, "if (%s (%s))\n", p
->p
->id
, opname
);
2365 fprintf_indent (f
, indent
+ 2, "{\n");
2369 /* Generate matching code for the decision tree operand which is
2373 dt_operand::gen_match_op (FILE *f
, int indent
, const char *opname
)
2375 char match_opname
[20];
2376 match_dop
->get_name (match_opname
);
2377 fprintf_indent (f
, indent
, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2378 opname
, match_opname
, opname
, match_opname
);
2379 fprintf_indent (f
, indent
+ 2, "{\n");
2383 /* Generate GIMPLE matching code for the decision tree operand. */
2386 dt_operand::gen_gimple_expr (FILE *f
, int indent
)
2388 expr
*e
= static_cast<expr
*> (op
);
2389 id_base
*id
= e
->operation
;
2390 unsigned n_ops
= e
->ops
.length ();
2392 for (unsigned i
= 0; i
< n_ops
; ++i
)
2394 char child_opname
[20];
2395 gen_opname (child_opname
, i
);
2397 if (id
->kind
== id_base::CODE
)
2400 || *id
== REALPART_EXPR
|| *id
== IMAGPART_EXPR
2401 || *id
== BIT_FIELD_REF
|| *id
== VIEW_CONVERT_EXPR
)
2403 /* ??? If this is a memory operation we can't (and should not)
2404 match this. The only sensible operand types are
2405 SSA names and invariants. */
2406 fprintf_indent (f
, indent
,
2407 "tree %s = TREE_OPERAND (gimple_assign_rhs1 (def), %i);\n",
2409 fprintf_indent (f
, indent
,
2410 "if ((TREE_CODE (%s) == SSA_NAME\n",
2412 fprintf_indent (f
, indent
,
2413 " || is_gimple_min_invariant (%s))\n",
2415 fprintf_indent (f
, indent
,
2416 " && (%s = do_valueize (valueize, %s)))\n",
2417 child_opname
, child_opname
);
2418 fprintf_indent (f
, indent
,
2424 fprintf_indent (f
, indent
,
2425 "tree %s = gimple_assign_rhs%u (def);\n",
2426 child_opname
, i
+ 1);
2429 fprintf_indent (f
, indent
,
2430 "tree %s = gimple_call_arg (def, %u);\n",
2432 fprintf_indent (f
, indent
,
2433 "if ((%s = do_valueize (valueize, %s)))\n",
2434 child_opname
, child_opname
);
2435 fprintf_indent (f
, indent
, " {\n");
2438 /* While the toplevel operands are canonicalized by the caller
2439 after valueizing operands of sub-expressions we have to
2440 re-canonicalize operand order. */
2441 if (operator_id
*code
= dyn_cast
<operator_id
*> (id
))
2443 /* ??? We can't canonicalize tcc_comparison operands here
2444 because that requires changing the comparison code which
2445 we already matched... */
2446 if (commutative_tree_code (code
->code
)
2447 || commutative_ternary_tree_code (code
->code
))
2449 char child_opname0
[20], child_opname1
[20];
2450 gen_opname (child_opname0
, 0);
2451 gen_opname (child_opname1
, 1);
2452 fprintf_indent (f
, indent
,
2453 "if (tree_swap_operands_p (%s, %s, false))\n",
2454 child_opname0
, child_opname1
);
2455 fprintf_indent (f
, indent
,
2456 " std::swap (%s, %s);\n",
2457 child_opname0
, child_opname1
);
2464 /* Generate GENERIC matching code for the decision tree operand. */
2467 dt_operand::gen_generic_expr (FILE *f
, int indent
, const char *opname
)
2469 expr
*e
= static_cast<expr
*> (op
);
2470 unsigned n_ops
= e
->ops
.length ();
2472 for (unsigned i
= 0; i
< n_ops
; ++i
)
2474 char child_opname
[20];
2475 gen_opname (child_opname
, i
);
2477 if (e
->operation
->kind
== id_base::CODE
)
2478 fprintf_indent (f
, indent
, "tree %s = TREE_OPERAND (%s, %u);\n",
2479 child_opname
, opname
, i
);
2481 fprintf_indent (f
, indent
, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2482 child_opname
, opname
, i
);
2488 /* Generate matching code for the children of the decision tree node. */
2491 dt_node::gen_kids (FILE *f
, int indent
, bool gimple
)
2493 auto_vec
<dt_operand
*> gimple_exprs
;
2494 auto_vec
<dt_operand
*> generic_exprs
;
2495 auto_vec
<dt_operand
*> fns
;
2496 auto_vec
<dt_operand
*> generic_fns
;
2497 auto_vec
<dt_operand
*> preds
;
2498 auto_vec
<dt_node
*> others
;
2500 for (unsigned i
= 0; i
< kids
.length (); ++i
)
2502 if (kids
[i
]->type
== dt_node::DT_OPERAND
)
2504 dt_operand
*op
= as_a
<dt_operand
*> (kids
[i
]);
2505 if (expr
*e
= dyn_cast
<expr
*> (op
->op
))
2507 if (e
->ops
.length () == 0
2508 && (!gimple
|| !(*e
->operation
== CONSTRUCTOR
)))
2509 generic_exprs
.safe_push (op
);
2510 else if (e
->operation
->kind
== id_base::FN
)
2515 generic_fns
.safe_push (op
);
2517 else if (e
->operation
->kind
== id_base::PREDICATE
)
2518 preds
.safe_push (op
);
2522 gimple_exprs
.safe_push (op
);
2524 generic_exprs
.safe_push (op
);
2527 else if (op
->op
->type
== operand::OP_PREDICATE
)
2528 others
.safe_push (kids
[i
]);
2532 else if (kids
[i
]->type
== dt_node::DT_MATCH
2533 || kids
[i
]->type
== dt_node::DT_SIMPLIFY
)
2534 others
.safe_push (kids
[i
]);
2535 else if (kids
[i
]->type
== dt_node::DT_TRUE
)
2537 /* A DT_TRUE operand serves as a barrier - generate code now
2538 for what we have collected sofar. */
2539 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2540 fns
, generic_fns
, preds
, others
);
2541 /* And output the true operand itself. */
2542 kids
[i
]->gen (f
, indent
, gimple
);
2543 gimple_exprs
.truncate (0);
2544 generic_exprs
.truncate (0);
2546 generic_fns
.truncate (0);
2548 others
.truncate (0);
2554 /* Generate code for the remains. */
2555 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2556 fns
, generic_fns
, preds
, others
);
2559 /* Generate matching code for the children of the decision tree node. */
2562 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2563 vec
<dt_operand
*> gimple_exprs
,
2564 vec
<dt_operand
*> generic_exprs
,
2565 vec
<dt_operand
*> fns
,
2566 vec
<dt_operand
*> generic_fns
,
2567 vec
<dt_operand
*> preds
,
2568 vec
<dt_node
*> others
)
2571 char *kid_opname
= buf
;
2573 unsigned exprs_len
= gimple_exprs
.length ();
2574 unsigned gexprs_len
= generic_exprs
.length ();
2575 unsigned fns_len
= fns
.length ();
2576 unsigned gfns_len
= generic_fns
.length ();
2578 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2581 gimple_exprs
[0]->get_name (kid_opname
);
2583 fns
[0]->get_name (kid_opname
);
2585 generic_fns
[0]->get_name (kid_opname
);
2587 generic_exprs
[0]->get_name (kid_opname
);
2589 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2590 fprintf_indent (f
, indent
, " {\n");
2594 if (exprs_len
|| fns_len
)
2596 fprintf_indent (f
, indent
,
2597 "case SSA_NAME:\n");
2598 fprintf_indent (f
, indent
,
2599 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2601 fprintf_indent (f
, indent
,
2603 fprintf_indent (f
, indent
,
2604 " gimple def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2610 fprintf_indent (f
, indent
,
2611 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2612 fprintf_indent (f
, indent
,
2613 " switch (gimple_assign_rhs_code (def))\n");
2615 fprintf_indent (f
, indent
, "{\n");
2616 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2618 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2619 id_base
*op
= e
->operation
;
2620 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2621 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2623 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2624 fprintf_indent (f
, indent
, " {\n");
2625 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2626 fprintf_indent (f
, indent
, " break;\n");
2627 fprintf_indent (f
, indent
, " }\n");
2629 fprintf_indent (f
, indent
, "default:;\n");
2630 fprintf_indent (f
, indent
, "}\n");
2636 fprintf_indent (f
, indent
,
2637 "%sif (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n",
2638 exprs_len
? "else " : "");
2639 fprintf_indent (f
, indent
,
2641 fprintf_indent (f
, indent
,
2642 " gcall *def = as_a <gcall *> (def_stmt);\n");
2643 fprintf_indent (f
, indent
,
2644 " tree fndecl = gimple_call_fndecl (def);\n");
2645 fprintf_indent (f
, indent
,
2646 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2647 fprintf_indent (f
, indent
,
2651 for (unsigned i
= 0; i
< fns_len
; ++i
)
2653 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2654 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2655 fprintf_indent (f
, indent
, " {\n");
2656 fns
[i
]->gen (f
, indent
+ 4, true);
2657 fprintf_indent (f
, indent
, " break;\n");
2658 fprintf_indent (f
, indent
, " }\n");
2661 fprintf_indent (f
, indent
, "default:;\n");
2662 fprintf_indent (f
, indent
, "}\n");
2664 fprintf_indent (f
, indent
, " }\n");
2668 fprintf_indent (f
, indent
, " }\n");
2669 fprintf_indent (f
, indent
, " break;\n");
2672 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2674 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2675 id_base
*op
= e
->operation
;
2676 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2677 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2679 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2680 fprintf_indent (f
, indent
, " {\n");
2681 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2682 fprintf_indent (f
, indent
, " break;\n");
2683 fprintf_indent (f
, indent
, " }\n");
2688 fprintf_indent (f
, indent
,
2689 "case CALL_EXPR:\n");
2690 fprintf_indent (f
, indent
,
2692 fprintf_indent (f
, indent
,
2693 " tree fndecl = get_callee_fndecl (%s);\n",
2695 fprintf_indent (f
, indent
,
2696 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2697 fprintf_indent (f
, indent
,
2698 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2699 fprintf_indent (f
, indent
,
2703 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2705 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2706 gcc_assert (e
->operation
->kind
== id_base::FN
);
2708 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2709 fprintf_indent (f
, indent
, " {\n");
2710 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2711 fprintf_indent (f
, indent
, " break;\n");
2712 fprintf_indent (f
, indent
, " }\n");
2716 fprintf_indent (f
, indent
, " default:;\n");
2717 fprintf_indent (f
, indent
, " }\n");
2718 fprintf_indent (f
, indent
, " break;\n");
2719 fprintf_indent (f
, indent
, " }\n");
2722 /* Close switch (TREE_CODE ()). */
2723 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2726 fprintf_indent (f
, indent
, " default:;\n");
2727 fprintf_indent (f
, indent
, " }\n");
2730 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2732 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2733 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2734 preds
[i
]->get_name (kid_opname
);
2735 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2736 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2737 gimple
? "gimple" : "tree",
2738 p
->id
, kid_opname
, kid_opname
,
2739 gimple
? ", valueize" : "");
2740 fprintf_indent (f
, indent
, " {\n");
2741 for (int j
= 0; j
< p
->nargs
; ++j
)
2743 char child_opname
[20];
2744 preds
[i
]->gen_opname (child_opname
, j
);
2745 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2746 child_opname
, kid_opname
, j
);
2748 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2752 for (unsigned i
= 0; i
< others
.length (); ++i
)
2753 others
[i
]->gen (f
, indent
, gimple
);
2756 /* Generate matching code for the decision tree operand. */
2759 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2764 unsigned n_braces
= 0;
2766 if (type
== DT_OPERAND
)
2769 case operand::OP_PREDICATE
:
2770 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2773 case operand::OP_EXPR
:
2775 n_braces
= gen_gimple_expr (f
, indent
);
2777 n_braces
= gen_generic_expr (f
, indent
, opname
);
2783 else if (type
== DT_TRUE
)
2785 else if (type
== DT_MATCH
)
2786 n_braces
= gen_match_op (f
, indent
, opname
);
2790 indent
+= 4 * n_braces
;
2791 gen_kids (f
, indent
, gimple
);
2793 for (unsigned i
= 0; i
< n_braces
; ++i
)
2798 fprintf_indent (f
, indent
, " }\n");
2803 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2804 step of a '(simplify ...)' or '(match ...)'. This handles everything
2805 that is not part of the decision tree (simplify->match).
2806 Main recursive worker. */
2809 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2813 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2815 fprintf_indent (f
, indent
, "{\n");
2817 output_line_directive (f
, w
->location
);
2818 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2819 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2821 fprintf_indent (f
, indent
, "}\n");
2824 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2826 output_line_directive (f
, ife
->location
);
2827 fprintf_indent (f
, indent
, "if (");
2828 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2830 fprintf_indent (f
, indent
+ 2, "{\n");
2832 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2834 fprintf_indent (f
, indent
+ 2, "}\n");
2837 fprintf_indent (f
, indent
, "else\n");
2838 fprintf_indent (f
, indent
+ 2, "{\n");
2840 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2842 fprintf_indent (f
, indent
+ 2, "}\n");
2848 /* Analyze captures and perform early-outs on the incoming arguments
2849 that cover cases we cannot handle. */
2850 capture_info
cinfo (s
, result
, gimple
);
2851 if (s
->kind
== simplify::SIMPLIFY
)
2855 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2856 if (cinfo
.force_no_side_effects
& (1 << i
))
2858 fprintf_indent (f
, indent
,
2859 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2862 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
2863 "forcing toplevel operand to have no "
2866 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2867 if (cinfo
.info
[i
].cse_p
)
2869 else if (cinfo
.info
[i
].force_no_side_effects_p
2870 && (cinfo
.info
[i
].toplevel_msk
2871 & cinfo
.force_no_side_effects
) == 0)
2873 fprintf_indent (f
, indent
,
2874 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2875 "return NULL_TREE;\n", i
);
2877 warning_at (cinfo
.info
[i
].c
->location
,
2878 "forcing captured operand to have no "
2881 else if ((cinfo
.info
[i
].toplevel_msk
2882 & cinfo
.force_no_side_effects
) != 0)
2883 /* Mark capture as having no side-effects if we had to verify
2884 that via forced toplevel operand checks. */
2885 cinfo
.info
[i
].force_no_side_effects_p
= true;
2889 /* Force single-use restriction by only allowing simple
2890 results via setting seq to NULL. */
2891 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2892 bool first_p
= true;
2893 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2894 if (cinfo
.info
[i
].force_single_use
)
2898 fprintf_indent (f
, indent
, "if (lseq\n");
2899 fprintf_indent (f
, indent
, " && (");
2905 fprintf_indent (f
, indent
, " || ");
2907 fprintf (f
, "!single_use (captures[%d])", i
);
2911 fprintf (f
, "))\n");
2912 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2917 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2918 "fprintf (dump_file, \"Applying pattern ");
2919 output_line_directive (f
,
2920 result
? result
->location
: s
->match
->location
, true);
2921 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2925 /* If there is no result then this is a predicate implementation. */
2926 fprintf_indent (f
, indent
, "return true;\n");
2930 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2931 in outermost position). */
2932 if (result
->type
== operand::OP_EXPR
2933 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2934 result
= as_a
<expr
*> (result
)->ops
[0];
2935 if (result
->type
== operand::OP_EXPR
)
2937 expr
*e
= as_a
<expr
*> (result
);
2938 id_base
*opr
= e
->operation
;
2939 bool is_predicate
= false;
2940 /* When we delay operator substituting during lowering of fors we
2941 make sure that for code-gen purposes the effects of each substitute
2942 are the same. Thus just look at that. */
2943 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2944 opr
= uid
->substitutes
[0];
2945 else if (is_a
<predicate_id
*> (opr
))
2946 is_predicate
= true;
2948 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2949 *e
->operation
== CONVERT_EXPR
2950 ? "NOP_EXPR" : e
->operation
->id
);
2951 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2954 snprintf (dest
, 32, "res_ops[%d]", j
);
2956 = get_operand_type (opr
,
2957 "type", e
->expr_type
,
2958 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2959 /* We need to expand GENERIC conditions we captured from
2961 bool expand_generic_cond_exprs_p
2963 /* But avoid doing that if the GENERIC condition is
2964 valid - which it is in the first operand of COND_EXPRs
2965 and VEC_COND_EXRPs. */
2966 && ((!(*opr
== COND_EXPR
)
2967 && !(*opr
== VEC_COND_EXPR
))
2969 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
2971 indexes
, expand_generic_cond_exprs_p
);
2974 /* Re-fold the toplevel result. It's basically an embedded
2975 gimple_build w/o actually building the stmt. */
2977 fprintf_indent (f
, indent
,
2978 "gimple_resimplify%d (lseq, res_code, type, "
2979 "res_ops, valueize);\n", e
->ops
.length ());
2981 else if (result
->type
== operand::OP_CAPTURE
2982 || result
->type
== operand::OP_C_EXPR
)
2984 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
2985 &cinfo
, indexes
, false);
2986 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
2987 if (is_a
<capture
*> (result
)
2988 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2990 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2991 with substituting a capture of that. */
2992 fprintf_indent (f
, indent
,
2993 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2994 fprintf_indent (f
, indent
,
2996 fprintf_indent (f
, indent
,
2997 " tree tem = res_ops[0];\n");
2998 fprintf_indent (f
, indent
,
2999 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3000 fprintf_indent (f
, indent
,
3001 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3002 fprintf_indent (f
, indent
,
3008 fprintf_indent (f
, indent
, "return true;\n");
3012 bool is_predicate
= false;
3013 if (result
->type
== operand::OP_EXPR
)
3015 expr
*e
= as_a
<expr
*> (result
);
3016 id_base
*opr
= e
->operation
;
3017 /* When we delay operator substituting during lowering of fors we
3018 make sure that for code-gen purposes the effects of each substitute
3019 are the same. Thus just look at that. */
3020 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3021 opr
= uid
->substitutes
[0];
3022 else if (is_a
<predicate_id
*> (opr
))
3023 is_predicate
= true;
3024 /* Search for captures used multiple times in the result expression
3025 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
3027 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3029 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3031 if (!cinfo
.info
[i
].force_no_side_effects_p
3032 && cinfo
.info
[i
].result_use_count
> 1)
3034 fprintf_indent (f
, indent
,
3035 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3037 fprintf_indent (f
, indent
,
3038 " captures[%d] = save_expr (captures[%d]);\n",
3042 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3046 snprintf (dest
, 32, "res_ops[%d]", j
);
3049 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3050 snprintf (dest
, 32, "res_op%d", j
);
3053 = get_operand_type (opr
,
3054 "type", e
->expr_type
,
3056 ? NULL
: "TREE_TYPE (res_op0)");
3057 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3061 fprintf_indent (f
, indent
, "return true;\n");
3064 fprintf_indent (f
, indent
, "tree res;\n");
3065 /* Re-fold the toplevel result. Use non_lvalue to
3066 build NON_LVALUE_EXPRs so they get properly
3067 ignored when in GIMPLE form. */
3068 if (*opr
== NON_LVALUE_EXPR
)
3069 fprintf_indent (f
, indent
,
3070 "res = non_lvalue_loc (loc, res_op0);\n");
3073 if (is_a
<operator_id
*> (opr
))
3074 fprintf_indent (f
, indent
,
3075 "res = fold_build%d_loc (loc, %s, type",
3077 *e
->operation
== CONVERT_EXPR
3078 ? "NOP_EXPR" : e
->operation
->id
);
3081 fprintf_indent (f
, indent
,
3083 fprintf_indent (f
, indent
,
3084 " tree decl = builtin_decl_implicit (%s);\n",
3086 fprintf_indent (f
, indent
,
3087 " if (!decl) return NULL_TREE;\n");
3088 fprintf_indent (f
, indent
,
3089 " res = build_call_expr_loc "
3093 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3094 fprintf (f
, ", res_op%d", j
);
3095 fprintf (f
, ");\n");
3096 if (!is_a
<operator_id
*> (opr
))
3097 fprintf_indent (f
, indent
, "}\n");
3101 else if (result
->type
== operand::OP_CAPTURE
3102 || result
->type
== operand::OP_C_EXPR
)
3105 fprintf_indent (f
, indent
, "tree res;\n");
3106 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3113 /* Search for captures not used in the result expression and dependent
3114 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3115 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3117 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3119 if (!cinfo
.info
[i
].force_no_side_effects_p
3120 && !cinfo
.info
[i
].expr_p
3121 && cinfo
.info
[i
].result_use_count
== 0)
3123 fprintf_indent (f
, indent
,
3124 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3126 fprintf_indent (f
, indent
+ 2,
3127 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3128 "fold_ignored_result (captures[%d]), res);\n",
3132 fprintf_indent (f
, indent
, "return res;\n");
3137 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3138 step of a '(simplify ...)' or '(match ...)'. This handles everything
3139 that is not part of the decision tree (simplify->match). */
3142 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3144 fprintf_indent (f
, indent
, "{\n");
3146 output_line_directive (f
,
3147 s
->result
? s
->result
->location
: s
->match
->location
);
3148 if (s
->capture_max
>= 0)
3151 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3152 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3154 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3155 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3156 fprintf (f
, " };\n");
3159 /* If we have a split-out function for the actual transform, call it. */
3160 if (info
&& info
->fname
)
3164 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3165 "valueize, type, captures", info
->fname
);
3166 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3167 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3168 fprintf (f
, "))\n");
3169 fprintf_indent (f
, indent
, " return true;\n");
3173 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3175 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3176 fprintf (f
, ", op%d", i
);
3177 fprintf (f
, ", captures");
3178 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3179 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3180 fprintf (f
, ");\n");
3181 fprintf_indent (f
, indent
, "if (res) return res;\n");
3186 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3188 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3189 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3190 s
->for_subst_vec
[i
].first
->id
,
3191 s
->for_subst_vec
[i
].second
->id
);
3192 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3193 fprintf_indent (f
, indent
, "enum built_in_function %s = %s;\n",
3194 s
->for_subst_vec
[i
].first
->id
,
3195 s
->for_subst_vec
[i
].second
->id
);
3199 gen_1 (f
, indent
, gimple
, s
->result
);
3203 fprintf_indent (f
, indent
, "}\n");
3207 /* Hash function for finding equivalent transforms. */
3210 sinfo_hashmap_traits::hash (const key_type
&v
)
3212 /* Only bother to compare those originating from the same source pattern. */
3213 return v
->s
->result
->location
;
3216 /* Compare function for finding equivalent transforms. */
3219 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3221 if (o1
->type
!= o2
->type
)
3226 case operand::OP_IF
:
3228 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3229 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3230 /* ??? Properly compare c-exprs. */
3231 if (if1
->cond
!= if2
->cond
)
3233 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3235 if (if1
->falseexpr
!= if2
->falseexpr
3237 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3241 case operand::OP_WITH
:
3243 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3244 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3245 if (with1
->with
!= with2
->with
)
3247 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3252 /* We've hit a result. Time to compare capture-infos - this is required
3253 in addition to the conservative pointer-equivalency of the result IL. */
3254 capture_info
cinfo1 (s1
, o1
, true);
3255 capture_info
cinfo2 (s2
, o2
, true);
3257 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3258 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3261 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3263 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3264 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3265 || (cinfo1
.info
[i
].force_no_side_effects_p
3266 != cinfo2
.info
[i
].force_no_side_effects_p
)
3267 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3268 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3269 /* toplevel_msk is an optimization */
3270 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3271 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3272 /* the pointer back to the capture is for diagnostics only */)
3276 /* ??? Deep-compare the actual result. */
3281 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3282 const key_type
&candidate
)
3284 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3288 /* Main entry to generate code for matching GIMPLE IL off the decision
3292 decision_tree::gen (FILE *f
, bool gimple
)
3298 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3299 "a total number of %u nodes\n",
3300 gimple
? "GIMPLE" : "GENERIC",
3301 root
->num_leafs
, root
->max_level
, root
->total_size
);
3303 /* First split out the transform part of equal leafs. */
3306 for (sinfo_map_t::iterator iter
= si
.begin ();
3307 iter
!= si
.end (); ++iter
)
3309 sinfo
*s
= (*iter
).second
;
3310 /* Do not split out single uses. */
3317 fprintf (stderr
, "found %u uses of", s
->cnt
);
3318 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3321 /* Generate a split out function with the leaf transform code. */
3322 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3325 fprintf (f
, "\nstatic bool\n"
3326 "%s (code_helper *res_code, tree *res_ops,\n"
3327 " gimple_seq *seq, tree (*valueize)(tree) "
3328 "ATTRIBUTE_UNUSED,\n"
3329 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3334 fprintf (f
, "\nstatic tree\n"
3335 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3336 (*iter
).second
->fname
);
3337 for (unsigned i
= 0;
3338 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3339 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3340 fprintf (f
, " tree *captures\n");
3342 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3344 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3345 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3346 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3347 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3348 fprintf (f
, ", enum built_in_function ARG_UNUSED (%s)",
3349 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3352 fprintf (f
, ")\n{\n");
3353 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3355 fprintf (f
, " return false;\n");
3357 fprintf (f
, " return NULL_TREE;\n");
3360 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3362 for (unsigned n
= 1; n
<= 3; ++n
)
3364 /* First generate split-out functions. */
3365 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3367 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3368 expr
*e
= static_cast<expr
*>(dop
->op
);
3369 if (e
->ops
.length () != n
3370 /* Builtin simplifications are somewhat premature on
3371 GENERIC. The following drops patterns with outermost
3372 calls. It's easy to emit overloads for function code
3373 though if necessary. */
3375 && e
->operation
->kind
!= id_base::CODE
))
3379 fprintf (f
, "\nstatic bool\n"
3380 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3381 " gimple_seq *seq, tree (*valueize)(tree) "
3382 "ATTRIBUTE_UNUSED,\n"
3383 " code_helper ARG_UNUSED (code), tree "
3384 "ARG_UNUSED (type)\n",
3387 fprintf (f
, "\nstatic tree\n"
3388 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3389 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3391 for (unsigned i
= 0; i
< n
; ++i
)
3392 fprintf (f
, ", tree op%d", i
);
3395 dop
->gen_kids (f
, 2, gimple
);
3397 fprintf (f
, " return false;\n");
3399 fprintf (f
, " return NULL_TREE;\n");
3403 /* Then generate the main entry with the outermost switch and
3404 tail-calls to the split-out functions. */
3406 fprintf (f
, "\nstatic bool\n"
3407 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3408 " gimple_seq *seq, tree (*valueize)(tree),\n"
3409 " code_helper code, tree type");
3411 fprintf (f
, "\ntree\n"
3412 "generic_simplify (location_t loc, enum tree_code code, "
3413 "tree type ATTRIBUTE_UNUSED");
3414 for (unsigned i
= 0; i
< n
; ++i
)
3415 fprintf (f
, ", tree op%d", i
);
3420 fprintf (f
, " switch (code.get_rep())\n"
3423 fprintf (f
, " switch (code)\n"
3425 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3427 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3428 expr
*e
= static_cast<expr
*>(dop
->op
);
3429 if (e
->ops
.length () != n
3430 /* Builtin simplifications are somewhat premature on
3431 GENERIC. The following drops patterns with outermost
3432 calls. It's easy to emit overloads for function code
3433 though if necessary. */
3435 && e
->operation
->kind
!= id_base::CODE
))
3438 if (*e
->operation
== CONVERT_EXPR
3439 || *e
->operation
== NOP_EXPR
)
3440 fprintf (f
, " CASE_CONVERT:\n");
3442 fprintf (f
, " case %s%s:\n",
3443 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3446 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3447 "seq, valueize, code, type", e
->operation
->id
);
3449 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3451 for (unsigned i
= 0; i
< n
; ++i
)
3452 fprintf (f
, ", op%d", i
);
3453 fprintf (f
, ");\n");
3455 fprintf (f
, " default:;\n"
3459 fprintf (f
, " return false;\n");
3461 fprintf (f
, " return NULL_TREE;\n");
3466 /* Output code to implement the predicate P from the decision tree DT. */
3469 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3471 fprintf (f
, "\nbool\n"
3472 "%s%s (tree t%s%s)\n"
3473 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3474 p
->nargs
> 0 ? ", tree *res_ops" : "",
3475 gimple
? ", tree (*valueize)(tree)" : "");
3476 /* Conveniently make 'type' available. */
3477 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3480 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3481 dt
.root
->gen_kids (f
, 2, gimple
);
3483 fprintf_indent (f
, 2, "return false;\n"
3487 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3490 write_header (FILE *f
, const char *head
)
3492 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3493 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3495 /* Include the header instead of writing it awkwardly quoted here. */
3496 fprintf (f
, "\n#include \"%s\"\n", head
);
3506 parser (cpp_reader
*);
3509 const cpp_token
*next ();
3510 const cpp_token
*peek (unsigned = 1);
3511 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3512 const cpp_token
*expect (enum cpp_ttype
);
3513 const cpp_token
*eat_token (enum cpp_ttype
);
3514 const char *get_string ();
3515 const char *get_ident ();
3516 const cpp_token
*eat_ident (const char *);
3517 const char *get_number ();
3519 id_base
*parse_operation ();
3520 operand
*parse_capture (operand
*, bool);
3521 operand
*parse_expr ();
3522 c_expr
*parse_c_expr (cpp_ttype
);
3523 operand
*parse_op ();
3525 void record_operlist (source_location
, user_id
*);
3527 void parse_pattern ();
3528 operand
*parse_result (operand
*, predicate_id
*);
3529 void push_simplify (simplify::simplify_kind
,
3530 vec
<simplify
*>&, operand
*, operand
*);
3531 void parse_simplify (simplify::simplify_kind
,
3532 vec
<simplify
*>&, predicate_id
*, operand
*);
3533 void parse_for (source_location
);
3534 void parse_if (source_location
);
3535 void parse_predicates (source_location
);
3536 void parse_operator_list (source_location
);
3539 vec
<c_expr
*> active_ifs
;
3540 vec
<vec
<user_id
*> > active_fors
;
3541 hash_set
<user_id
*> *oper_lists_set
;
3542 vec
<user_id
*> oper_lists
;
3544 cid_map_t
*capture_ids
;
3547 vec
<simplify
*> simplifiers
;
3548 vec
<predicate_id
*> user_predicates
;
3549 bool parsing_match_operand
;
3552 /* Lexing helpers. */
3554 /* Read the next non-whitespace token from R. */
3559 const cpp_token
*token
;
3562 token
= cpp_get_token (r
);
3564 while (token
->type
== CPP_PADDING
3565 && token
->type
!= CPP_EOF
);
3569 /* Peek at the next non-whitespace token from R. */
3572 parser::peek (unsigned num
)
3574 const cpp_token
*token
;
3578 token
= cpp_peek_token (r
, i
++);
3580 while ((token
->type
== CPP_PADDING
3581 && token
->type
!= CPP_EOF
)
3583 /* If we peek at EOF this is a fatal error as it leaves the
3584 cpp_reader in unusable state. Assume we really wanted a
3585 token and thus this EOF is unexpected. */
3586 if (token
->type
== CPP_EOF
)
3587 fatal_at (token
, "unexpected end of file");
3591 /* Peek at the next identifier token (or return NULL if the next
3592 token is not an identifier or equal to ID if supplied). */
3595 parser::peek_ident (const char *id
, unsigned num
)
3597 const cpp_token
*token
= peek (num
);
3598 if (token
->type
!= CPP_NAME
)
3604 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3605 if (strcmp (id
, t
) == 0)
3611 /* Read the next token from R and assert it is of type TK. */
3614 parser::expect (enum cpp_ttype tk
)
3616 const cpp_token
*token
= next ();
3617 if (token
->type
!= tk
)
3618 fatal_at (token
, "expected %s, got %s",
3619 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3624 /* Consume the next token from R and assert it is of type TK. */
3627 parser::eat_token (enum cpp_ttype tk
)
3632 /* Read the next token from R and assert it is of type CPP_STRING and
3633 return its value. */
3636 parser::get_string ()
3638 const cpp_token
*token
= expect (CPP_STRING
);
3639 return (const char *)token
->val
.str
.text
;
3642 /* Read the next token from R and assert it is of type CPP_NAME and
3643 return its value. */
3646 parser::get_ident ()
3648 const cpp_token
*token
= expect (CPP_NAME
);
3649 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3652 /* Eat an identifier token with value S from R. */
3655 parser::eat_ident (const char *s
)
3657 const cpp_token
*token
= peek ();
3658 const char *t
= get_ident ();
3659 if (strcmp (s
, t
) != 0)
3660 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3664 /* Read the next token from R and assert it is of type CPP_NUMBER and
3665 return its value. */
3668 parser::get_number ()
3670 const cpp_token
*token
= expect (CPP_NUMBER
);
3671 return (const char *)token
->val
.str
.text
;
3675 /* Record an operator-list use for transparent for handling. */
3678 parser::record_operlist (source_location loc
, user_id
*p
)
3680 if (!oper_lists_set
->add (p
))
3682 if (!oper_lists
.is_empty ()
3683 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3684 fatal_at (loc
, "User-defined operator list does not have the "
3685 "same number of entries as others used in the pattern");
3686 oper_lists
.safe_push (p
);
3690 /* Parse the operator ID, special-casing convert?, convert1? and
3694 parser::parse_operation ()
3696 const cpp_token
*id_tok
= peek ();
3697 const char *id
= get_ident ();
3698 const cpp_token
*token
= peek ();
3699 if (strcmp (id
, "convert0") == 0)
3700 fatal_at (id_tok
, "use 'convert?' here");
3701 else if (strcmp (id
, "view_convert0") == 0)
3702 fatal_at (id_tok
, "use 'view_convert?' here");
3703 if (token
->type
== CPP_QUERY
3704 && !(token
->flags
& PREV_WHITE
))
3706 if (strcmp (id
, "convert") == 0)
3708 else if (strcmp (id
, "convert1") == 0)
3710 else if (strcmp (id
, "convert2") == 0)
3712 else if (strcmp (id
, "view_convert") == 0)
3713 id
= "view_convert0";
3714 else if (strcmp (id
, "view_convert1") == 0)
3716 else if (strcmp (id
, "view_convert2") == 0)
3719 fatal_at (id_tok
, "non-convert operator conditionalized");
3721 if (!parsing_match_operand
)
3722 fatal_at (id_tok
, "conditional convert can only be used in "
3723 "match expression");
3724 eat_token (CPP_QUERY
);
3726 else if (strcmp (id
, "convert1") == 0
3727 || strcmp (id
, "convert2") == 0
3728 || strcmp (id
, "view_convert1") == 0
3729 || strcmp (id
, "view_convert2") == 0)
3730 fatal_at (id_tok
, "expected '?' after conditional operator");
3731 id_base
*op
= get_operator (id
);
3733 fatal_at (id_tok
, "unknown operator %s", id
);
3735 user_id
*p
= dyn_cast
<user_id
*> (op
);
3736 if (p
&& p
->is_oper_list
)
3738 if (active_fors
.length() == 0)
3739 record_operlist (id_tok
->src_loc
, p
);
3741 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3747 capture = '@'<number> */
3750 parser::parse_capture (operand
*op
, bool require_existing
)
3752 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3753 const cpp_token
*token
= peek ();
3754 const char *id
= NULL
;
3755 if (token
->type
== CPP_NUMBER
)
3757 else if (token
->type
== CPP_NAME
)
3760 fatal_at (token
, "expected number or identifier");
3761 unsigned next_id
= capture_ids
->elements ();
3763 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3766 if (require_existing
)
3767 fatal_at (src_loc
, "unknown capture id");
3770 return new capture (src_loc
, num
, op
);
3773 /* Parse an expression
3774 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3777 parser::parse_expr ()
3779 const cpp_token
*token
= peek ();
3780 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3783 bool is_commutative
= false;
3784 bool force_capture
= false;
3785 const char *expr_type
= NULL
;
3787 if (token
->type
== CPP_COLON
3788 && !(token
->flags
& PREV_WHITE
))
3790 eat_token (CPP_COLON
);
3792 if (token
->type
== CPP_NAME
3793 && !(token
->flags
& PREV_WHITE
))
3795 const char *s
= get_ident ();
3796 if (!parsing_match_operand
)
3804 is_commutative
= true;
3805 else if (*sp
== 's')
3807 e
->force_single_use
= true;
3808 force_capture
= true;
3811 fatal_at (token
, "flag %c not recognized", *sp
);
3818 fatal_at (token
, "expected flag or type specifying identifier");
3821 if (token
->type
== CPP_ATSIGN
3822 && !(token
->flags
& PREV_WHITE
))
3823 op
= parse_capture (e
, !parsing_match_operand
);
3824 else if (force_capture
)
3826 unsigned num
= capture_ids
->elements ();
3829 sprintf (id
, "__%u", num
);
3830 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3832 fatal_at (token
, "reserved capture id '%s' already used", id
);
3833 op
= new capture (token
->src_loc
, num
, e
);
3839 const cpp_token
*token
= peek ();
3840 if (token
->type
== CPP_CLOSE_PAREN
)
3842 if (e
->operation
->nargs
!= -1
3843 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3844 fatal_at (token
, "'%s' expects %u operands, not %u",
3845 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3848 if (e
->ops
.length () == 2)
3849 e
->is_commutative
= true;
3851 fatal_at (token
, "only binary operators or function with "
3852 "two arguments can be marked commutative");
3854 e
->expr_type
= expr_type
;
3857 e
->append_op (parse_op ());
3862 /* Lex native C code delimited by START recording the preprocessing tokens
3863 for later processing.
3864 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3867 parser::parse_c_expr (cpp_ttype start
)
3869 const cpp_token
*token
;
3872 vec
<cpp_token
> code
= vNULL
;
3873 unsigned nr_stmts
= 0;
3874 source_location loc
= eat_token (start
)->src_loc
;
3875 if (start
== CPP_OPEN_PAREN
)
3876 end
= CPP_CLOSE_PAREN
;
3877 else if (start
== CPP_OPEN_BRACE
)
3878 end
= CPP_CLOSE_BRACE
;
3886 /* Count brace pairs to find the end of the expr to match. */
3887 if (token
->type
== start
)
3889 else if (token
->type
== end
3893 /* This is a lame way of counting the number of statements. */
3894 if (token
->type
== CPP_SEMICOLON
)
3897 /* If this is possibly a user-defined identifier mark it used. */
3898 if (token
->type
== CPP_NAME
)
3900 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3901 (token
->val
.node
.node
)->ident
.str
);
3903 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3904 record_operlist (token
->src_loc
, p
);
3907 /* Record the token. */
3908 code
.safe_push (*token
);
3911 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3914 /* Parse an operand which is either an expression, a predicate or
3915 a standalone capture.
3916 op = predicate | expr | c_expr | capture */
3921 const cpp_token
*token
= peek ();
3922 struct operand
*op
= NULL
;
3923 if (token
->type
== CPP_OPEN_PAREN
)
3925 eat_token (CPP_OPEN_PAREN
);
3927 eat_token (CPP_CLOSE_PAREN
);
3929 else if (token
->type
== CPP_OPEN_BRACE
)
3931 op
= parse_c_expr (CPP_OPEN_BRACE
);
3935 /* Remaining ops are either empty or predicates */
3936 if (token
->type
== CPP_NAME
)
3938 const char *id
= get_ident ();
3939 id_base
*opr
= get_operator (id
);
3941 fatal_at (token
, "expected predicate name");
3942 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3944 if (code
->nargs
!= 0)
3945 fatal_at (token
, "using an operator with operands as predicate");
3946 /* Parse the zero-operand operator "predicates" as
3948 op
= new expr (opr
, token
->src_loc
);
3950 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3952 if (code
->nargs
!= 0)
3953 fatal_at (token
, "using an operator with operands as predicate");
3954 /* Parse the zero-operand operator "predicates" as
3956 op
= new expr (opr
, token
->src_loc
);
3958 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3959 op
= new predicate (p
, token
->src_loc
);
3961 fatal_at (token
, "using an unsupported operator as predicate");
3962 if (!parsing_match_operand
)
3963 fatal_at (token
, "predicates are only allowed in match expression");
3965 if (token
->flags
& PREV_WHITE
)
3968 else if (token
->type
!= CPP_COLON
3969 && token
->type
!= CPP_ATSIGN
)
3970 fatal_at (token
, "expected expression or predicate");
3971 /* optionally followed by a capture and a predicate. */
3972 if (token
->type
== CPP_COLON
)
3973 fatal_at (token
, "not implemented: predicate on leaf operand");
3974 if (token
->type
== CPP_ATSIGN
)
3975 op
= parse_capture (op
, !parsing_match_operand
);
3981 /* Create a new simplify from the current parsing state and MATCH,
3982 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3985 parser::push_simplify (simplify::simplify_kind kind
,
3986 vec
<simplify
*>& simplifiers
,
3987 operand
*match
, operand
*result
)
3989 /* Build and push a temporary for operator list uses in expressions. */
3990 if (!oper_lists
.is_empty ())
3991 active_fors
.safe_push (oper_lists
);
3993 simplifiers
.safe_push
3994 (new simplify (kind
, match
, result
,
3995 active_fors
.copy (), capture_ids
));
3997 if (!oper_lists
.is_empty ())
4002 <result-op> = <op> | <if> | <with>
4003 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4004 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4008 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4010 const cpp_token
*token
= peek ();
4011 if (token
->type
!= CPP_OPEN_PAREN
)
4014 eat_token (CPP_OPEN_PAREN
);
4015 if (peek_ident ("if"))
4018 if_expr
*ife
= new if_expr (token
->src_loc
);
4019 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4020 if (peek ()->type
== CPP_OPEN_PAREN
)
4022 ife
->trueexpr
= parse_result (result
, matcher
);
4023 if (peek ()->type
== CPP_OPEN_PAREN
)
4024 ife
->falseexpr
= parse_result (result
, matcher
);
4025 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4026 ife
->falseexpr
= parse_op ();
4028 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4030 ife
->trueexpr
= parse_op ();
4031 if (peek ()->type
== CPP_OPEN_PAREN
)
4032 ife
->falseexpr
= parse_result (result
, matcher
);
4033 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4034 ife
->falseexpr
= parse_op ();
4036 /* If this if is immediately closed then it contains a
4037 manual matcher or is part of a predicate definition. */
4038 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4041 fatal_at (peek (), "manual transform not implemented");
4042 ife
->trueexpr
= result
;
4044 eat_token (CPP_CLOSE_PAREN
);
4047 else if (peek_ident ("with"))
4050 with_expr
*withe
= new with_expr (token
->src_loc
);
4051 /* Parse (with c-expr expr) as (if-with (true) expr). */
4052 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4053 withe
->with
->nr_stmts
= 0;
4054 withe
->subexpr
= parse_result (result
, matcher
);
4055 eat_token (CPP_CLOSE_PAREN
);
4058 else if (peek_ident ("switch"))
4060 token
= eat_ident ("switch");
4061 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4063 if_expr
*ife
= new if_expr (ifloc
);
4065 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4066 if (peek ()->type
== CPP_OPEN_PAREN
)
4067 ife
->trueexpr
= parse_result (result
, matcher
);
4069 ife
->trueexpr
= parse_op ();
4070 eat_token (CPP_CLOSE_PAREN
);
4071 if (peek ()->type
!= CPP_OPEN_PAREN
4072 || !peek_ident ("if", 2))
4073 fatal_at (token
, "switch can be implemented with a single if");
4074 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4076 if (peek ()->type
== CPP_OPEN_PAREN
)
4078 if (peek_ident ("if", 2))
4080 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4082 ife
->falseexpr
= new if_expr (ifloc
);
4083 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4084 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4085 if (peek ()->type
== CPP_OPEN_PAREN
)
4086 ife
->trueexpr
= parse_result (result
, matcher
);
4088 ife
->trueexpr
= parse_op ();
4089 eat_token (CPP_CLOSE_PAREN
);
4093 /* switch default clause */
4094 ife
->falseexpr
= parse_result (result
, matcher
);
4095 eat_token (CPP_CLOSE_PAREN
);
4101 /* switch default clause */
4102 ife
->falseexpr
= parse_op ();
4103 eat_token (CPP_CLOSE_PAREN
);
4107 eat_token (CPP_CLOSE_PAREN
);
4112 operand
*op
= result
;
4115 eat_token (CPP_CLOSE_PAREN
);
4121 simplify = 'simplify' <expr> <result-op>
4123 match = 'match' <ident> <expr> [<result-op>]
4124 and fill SIMPLIFIERS with the results. */
4127 parser::parse_simplify (simplify::simplify_kind kind
,
4128 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4131 /* Reset the capture map. */
4133 capture_ids
= new cid_map_t
;
4134 /* Reset oper_lists and set. */
4135 hash_set
<user_id
*> olist
;
4136 oper_lists_set
= &olist
;
4139 const cpp_token
*loc
= peek ();
4140 parsing_match_operand
= true;
4141 struct operand
*match
= parse_op ();
4142 parsing_match_operand
= false;
4143 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4144 fatal_at (loc
, "outermost expression cannot be captured");
4145 if (match
->type
== operand::OP_EXPR
4146 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4147 fatal_at (loc
, "outermost expression cannot be a predicate");
4149 /* Splice active_ifs onto result and continue parsing the
4151 if_expr
*active_if
= NULL
;
4152 for (int i
= active_ifs
.length (); i
> 0; --i
)
4154 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4155 ifc
->cond
= active_ifs
[i
-1];
4156 ifc
->trueexpr
= active_if
;
4159 if_expr
*outermost_if
= active_if
;
4160 while (active_if
&& active_if
->trueexpr
)
4161 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4163 const cpp_token
*token
= peek ();
4165 /* If this if is immediately closed then it is part of a predicate
4166 definition. Push it. */
4167 if (token
->type
== CPP_CLOSE_PAREN
)
4170 fatal_at (token
, "expected transform expression");
4173 active_if
->trueexpr
= result
;
4174 result
= outermost_if
;
4176 push_simplify (kind
, simplifiers
, match
, result
);
4180 operand
*tem
= parse_result (result
, matcher
);
4183 active_if
->trueexpr
= tem
;
4184 result
= outermost_if
;
4189 push_simplify (kind
, simplifiers
, match
, result
);
4192 /* Parsing of the outer control structures. */
4194 /* Parse a for expression
4195 for = '(' 'for' <subst>... <pattern> ')'
4196 subst = <ident> '(' <ident>... ')' */
4199 parser::parse_for (source_location
)
4201 auto_vec
<const cpp_token
*> user_id_tokens
;
4202 vec
<user_id
*> user_ids
= vNULL
;
4203 const cpp_token
*token
;
4204 unsigned min_n_opers
= 0, max_n_opers
= 0;
4209 if (token
->type
!= CPP_NAME
)
4212 /* Insert the user defined operators into the operator hash. */
4213 const char *id
= get_ident ();
4214 if (get_operator (id
) != NULL
)
4215 fatal_at (token
, "operator already defined");
4216 user_id
*op
= new user_id (id
);
4217 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4219 user_ids
.safe_push (op
);
4220 user_id_tokens
.safe_push (token
);
4222 eat_token (CPP_OPEN_PAREN
);
4225 while ((token
= peek_ident ()) != 0)
4227 const char *oper
= get_ident ();
4228 id_base
*idb
= get_operator (oper
);
4230 fatal_at (token
, "no such operator '%s'", oper
);
4231 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4232 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4233 || *idb
== VIEW_CONVERT2
)
4234 fatal_at (token
, "conditional operators cannot be used inside for");
4238 else if (idb
->nargs
== -1)
4240 else if (idb
->nargs
!= arity
)
4241 fatal_at (token
, "operator '%s' with arity %d does not match "
4242 "others with arity %d", oper
, idb
->nargs
, arity
);
4244 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4247 if (p
->is_oper_list
)
4248 op
->substitutes
.safe_splice (p
->substitutes
);
4250 fatal_at (token
, "iterator cannot be used as operator-list");
4253 op
->substitutes
.safe_push (idb
);
4256 token
= expect (CPP_CLOSE_PAREN
);
4258 unsigned nsubstitutes
= op
->substitutes
.length ();
4259 if (nsubstitutes
== 0)
4260 fatal_at (token
, "A user-defined operator must have at least "
4261 "one substitution");
4262 if (max_n_opers
== 0)
4264 min_n_opers
= nsubstitutes
;
4265 max_n_opers
= nsubstitutes
;
4269 if (nsubstitutes
% min_n_opers
!= 0
4270 && min_n_opers
% nsubstitutes
!= 0)
4271 fatal_at (token
, "All user-defined identifiers must have a "
4272 "multiple number of operator substitutions of the "
4273 "smallest number of substitutions");
4274 if (nsubstitutes
< min_n_opers
)
4275 min_n_opers
= nsubstitutes
;
4276 else if (nsubstitutes
> max_n_opers
)
4277 max_n_opers
= nsubstitutes
;
4281 unsigned n_ids
= user_ids
.length ();
4283 fatal_at (token
, "for requires at least one user-defined identifier");
4286 if (token
->type
== CPP_CLOSE_PAREN
)
4287 fatal_at (token
, "no pattern defined in for");
4289 active_fors
.safe_push (user_ids
);
4293 if (token
->type
== CPP_CLOSE_PAREN
)
4299 /* Remove user-defined operators from the hash again. */
4300 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4302 if (!user_ids
[i
]->used
)
4303 warning_at (user_id_tokens
[i
],
4304 "operator %s defined but not used", user_ids
[i
]->id
);
4305 operators
->remove_elt (user_ids
[i
]);
4309 /* Parse an identifier associated with a list of operators.
4310 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4313 parser::parse_operator_list (source_location
)
4315 const cpp_token
*token
= peek ();
4316 const char *id
= get_ident ();
4318 if (get_operator (id
) != 0)
4319 fatal_at (token
, "operator %s already defined", id
);
4321 user_id
*op
= new user_id (id
, true);
4324 while ((token
= peek_ident ()) != 0)
4327 const char *oper
= get_ident ();
4328 id_base
*idb
= get_operator (oper
);
4331 fatal_at (token
, "no such operator '%s'", oper
);
4335 else if (idb
->nargs
== -1)
4337 else if (arity
!= idb
->nargs
)
4338 fatal_at (token
, "operator '%s' with arity %d does not match "
4339 "others with arity %d", oper
, idb
->nargs
, arity
);
4341 /* We allow composition of multiple operator lists. */
4342 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4343 op
->substitutes
.safe_splice (p
->substitutes
);
4345 op
->substitutes
.safe_push (idb
);
4348 // Check that there is no junk after id-list
4350 if (token
->type
!= CPP_CLOSE_PAREN
)
4351 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4353 if (op
->substitutes
.length () == 0)
4354 fatal_at (token
, "operator-list cannot be empty");
4357 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4361 /* Parse an outer if expression.
4362 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4365 parser::parse_if (source_location
)
4367 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4369 const cpp_token
*token
= peek ();
4370 if (token
->type
== CPP_CLOSE_PAREN
)
4371 fatal_at (token
, "no pattern defined in if");
4373 active_ifs
.safe_push (ifexpr
);
4376 const cpp_token
*token
= peek ();
4377 if (token
->type
== CPP_CLOSE_PAREN
)
4385 /* Parse a list of predefined predicate identifiers.
4386 preds = '(' 'define_predicates' <ident>... ')' */
4389 parser::parse_predicates (source_location
)
4393 const cpp_token
*token
= peek ();
4394 if (token
->type
!= CPP_NAME
)
4397 add_predicate (get_ident ());
4402 /* Parse outer control structures.
4403 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4406 parser::parse_pattern ()
4408 /* All clauses start with '('. */
4409 eat_token (CPP_OPEN_PAREN
);
4410 const cpp_token
*token
= peek ();
4411 const char *id
= get_ident ();
4412 if (strcmp (id
, "simplify") == 0)
4414 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4417 else if (strcmp (id
, "match") == 0)
4419 bool with_args
= false;
4420 source_location e_loc
= peek ()->src_loc
;
4421 if (peek ()->type
== CPP_OPEN_PAREN
)
4423 eat_token (CPP_OPEN_PAREN
);
4426 const char *name
= get_ident ();
4427 id_base
*id
= get_operator (name
);
4431 p
= add_predicate (name
);
4432 user_predicates
.safe_push (p
);
4434 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4437 fatal_at (token
, "cannot add a match to a non-predicate ID");
4438 /* Parse (match <id> <arg>... (match-expr)) here. */
4442 capture_ids
= new cid_map_t
;
4443 e
= new expr (p
, e_loc
);
4444 while (peek ()->type
== CPP_ATSIGN
)
4445 e
->append_op (parse_capture (NULL
, false));
4446 eat_token (CPP_CLOSE_PAREN
);
4449 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4450 || (!e
&& p
->nargs
!= 0)))
4451 fatal_at (token
, "non-matching number of match operands");
4452 p
->nargs
= e
? e
->ops
.length () : 0;
4453 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4456 else if (strcmp (id
, "for") == 0)
4457 parse_for (token
->src_loc
);
4458 else if (strcmp (id
, "if") == 0)
4459 parse_if (token
->src_loc
);
4460 else if (strcmp (id
, "define_predicates") == 0)
4462 if (active_ifs
.length () > 0
4463 || active_fors
.length () > 0)
4464 fatal_at (token
, "define_predicates inside if or for is not supported");
4465 parse_predicates (token
->src_loc
);
4467 else if (strcmp (id
, "define_operator_list") == 0)
4469 if (active_ifs
.length () > 0
4470 || active_fors
.length () > 0)
4471 fatal_at (token
, "operator-list inside if or for is not supported");
4472 parse_operator_list (token
->src_loc
);
4475 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4476 active_ifs
.length () == 0 && active_fors
.length () == 0
4477 ? "'define_predicates', " : "");
4479 eat_token (CPP_CLOSE_PAREN
);
4482 /* Main entry of the parser. Repeatedly parse outer control structures. */
4484 parser::parser (cpp_reader
*r_
)
4488 active_fors
= vNULL
;
4489 simplifiers
= vNULL
;
4490 oper_lists_set
= NULL
;
4493 user_predicates
= vNULL
;
4494 parsing_match_operand
= false;
4496 const cpp_token
*token
= next ();
4497 while (token
->type
!= CPP_EOF
)
4499 _cpp_backup_tokens (r
, 1);
4506 /* Helper for the linemap code. */
4509 round_alloc_size (size_t s
)
4515 /* The genmatch generator progam. It reads from a pattern description
4516 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4519 main (int argc
, char **argv
)
4523 progname
= "genmatch";
4529 char *input
= argv
[argc
-1];
4530 for (int i
= 1; i
< argc
- 1; ++i
)
4532 if (strcmp (argv
[i
], "--gimple") == 0)
4534 else if (strcmp (argv
[i
], "--generic") == 0)
4536 else if (strcmp (argv
[i
], "-v") == 0)
4538 else if (strcmp (argv
[i
], "-vv") == 0)
4542 fprintf (stderr
, "Usage: genmatch "
4543 "[--gimple] [--generic] [-v[v]] input\n");
4548 line_table
= XCNEW (struct line_maps
);
4549 linemap_init (line_table
, 0);
4550 line_table
->reallocator
= xrealloc
;
4551 line_table
->round_alloc_size
= round_alloc_size
;
4553 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4554 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4555 cb
->error
= error_cb
;
4557 if (!cpp_read_main_file (r
, input
))
4559 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4560 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4562 /* Pre-seed operators. */
4563 operators
= new hash_table
<id_base
> (1024);
4564 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4565 add_operator (SYM, # SYM, # TYPE, NARGS);
4566 #define END_OF_BASE_TREE_CODES
4568 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4569 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4570 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4571 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4572 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4573 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4574 #undef END_OF_BASE_TREE_CODES
4577 /* Pre-seed builtin functions.
4578 ??? Cannot use N (name) as that is targetm.emultls.get_address
4579 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4580 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4581 add_builtin (ENUM, # ENUM);
4582 #include "builtins.def"
4589 write_header (stdout
, "gimple-match-head.c");
4591 write_header (stdout
, "generic-match-head.c");
4593 /* Go over all predicates defined with patterns and perform
4594 lowering and code generation. */
4595 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4597 predicate_id
*pred
= p
.user_predicates
[i
];
4598 lower (pred
->matchers
, gimple
);
4601 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4602 print_matches (pred
->matchers
[i
]);
4605 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4606 dt
.insert (pred
->matchers
[i
], i
);
4611 write_predicate (stdout
, pred
, dt
, gimple
);
4614 /* Lower the main simplifiers and generate code for them. */
4615 lower (p
.simplifiers
, gimple
);
4618 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4619 print_matches (p
.simplifiers
[i
]);
4622 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4623 dt
.insert (p
.simplifiers
[i
], i
);
4628 dt
.gen (stdout
, gimple
);
4631 cpp_finish (r
, NULL
);