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_SIMPLIFY
)
2533 others
.safe_push (kids
[i
]);
2534 else if (kids
[i
]->type
== dt_node::DT_MATCH
2535 || 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 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2540 dependent matches to get out-of-order. Generate code now
2541 for what we have collected sofar. */
2542 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2543 fns
, generic_fns
, preds
, others
);
2544 /* And output the true operand itself. */
2545 kids
[i
]->gen (f
, indent
, gimple
);
2546 gimple_exprs
.truncate (0);
2547 generic_exprs
.truncate (0);
2549 generic_fns
.truncate (0);
2551 others
.truncate (0);
2557 /* Generate code for the remains. */
2558 gen_kids_1 (f
, indent
, gimple
, gimple_exprs
, generic_exprs
,
2559 fns
, generic_fns
, preds
, others
);
2562 /* Generate matching code for the children of the decision tree node. */
2565 dt_node::gen_kids_1 (FILE *f
, int indent
, bool gimple
,
2566 vec
<dt_operand
*> gimple_exprs
,
2567 vec
<dt_operand
*> generic_exprs
,
2568 vec
<dt_operand
*> fns
,
2569 vec
<dt_operand
*> generic_fns
,
2570 vec
<dt_operand
*> preds
,
2571 vec
<dt_node
*> others
)
2574 char *kid_opname
= buf
;
2576 unsigned exprs_len
= gimple_exprs
.length ();
2577 unsigned gexprs_len
= generic_exprs
.length ();
2578 unsigned fns_len
= fns
.length ();
2579 unsigned gfns_len
= generic_fns
.length ();
2581 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2584 gimple_exprs
[0]->get_name (kid_opname
);
2586 fns
[0]->get_name (kid_opname
);
2588 generic_fns
[0]->get_name (kid_opname
);
2590 generic_exprs
[0]->get_name (kid_opname
);
2592 fprintf_indent (f
, indent
, "switch (TREE_CODE (%s))\n", kid_opname
);
2593 fprintf_indent (f
, indent
, " {\n");
2597 if (exprs_len
|| fns_len
)
2599 fprintf_indent (f
, indent
,
2600 "case SSA_NAME:\n");
2601 fprintf_indent (f
, indent
,
2602 " if (do_valueize (valueize, %s) != NULL_TREE)\n",
2604 fprintf_indent (f
, indent
,
2606 fprintf_indent (f
, indent
,
2607 " gimple *def_stmt = SSA_NAME_DEF_STMT (%s);\n",
2613 fprintf_indent (f
, indent
,
2614 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2615 fprintf_indent (f
, indent
,
2616 " switch (gimple_assign_rhs_code (def))\n");
2618 fprintf_indent (f
, indent
, "{\n");
2619 for (unsigned i
= 0; i
< exprs_len
; ++i
)
2621 expr
*e
= as_a
<expr
*> (gimple_exprs
[i
]->op
);
2622 id_base
*op
= e
->operation
;
2623 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2624 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2626 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2627 fprintf_indent (f
, indent
, " {\n");
2628 gimple_exprs
[i
]->gen (f
, indent
+ 4, true);
2629 fprintf_indent (f
, indent
, " break;\n");
2630 fprintf_indent (f
, indent
, " }\n");
2632 fprintf_indent (f
, indent
, "default:;\n");
2633 fprintf_indent (f
, indent
, "}\n");
2639 fprintf_indent (f
, indent
,
2640 "%sif (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL))\n",
2641 exprs_len
? "else " : "");
2642 fprintf_indent (f
, indent
,
2644 fprintf_indent (f
, indent
,
2645 " gcall *def = as_a <gcall *> (def_stmt);\n");
2646 fprintf_indent (f
, indent
,
2647 " tree fndecl = gimple_call_fndecl (def);\n");
2648 fprintf_indent (f
, indent
,
2649 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2650 fprintf_indent (f
, indent
,
2654 for (unsigned i
= 0; i
< fns_len
; ++i
)
2656 expr
*e
= as_a
<expr
*>(fns
[i
]->op
);
2657 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2658 fprintf_indent (f
, indent
, " {\n");
2659 fns
[i
]->gen (f
, indent
+ 4, true);
2660 fprintf_indent (f
, indent
, " break;\n");
2661 fprintf_indent (f
, indent
, " }\n");
2664 fprintf_indent (f
, indent
, "default:;\n");
2665 fprintf_indent (f
, indent
, "}\n");
2667 fprintf_indent (f
, indent
, " }\n");
2671 fprintf_indent (f
, indent
, " }\n");
2672 fprintf_indent (f
, indent
, " break;\n");
2675 for (unsigned i
= 0; i
< generic_exprs
.length (); ++i
)
2677 expr
*e
= as_a
<expr
*>(generic_exprs
[i
]->op
);
2678 id_base
*op
= e
->operation
;
2679 if (*op
== CONVERT_EXPR
|| *op
== NOP_EXPR
)
2680 fprintf_indent (f
, indent
, "CASE_CONVERT:\n");
2682 fprintf_indent (f
, indent
, "case %s:\n", op
->id
);
2683 fprintf_indent (f
, indent
, " {\n");
2684 generic_exprs
[i
]->gen (f
, indent
+ 4, gimple
);
2685 fprintf_indent (f
, indent
, " break;\n");
2686 fprintf_indent (f
, indent
, " }\n");
2691 fprintf_indent (f
, indent
,
2692 "case CALL_EXPR:\n");
2693 fprintf_indent (f
, indent
,
2695 fprintf_indent (f
, indent
,
2696 " tree fndecl = get_callee_fndecl (%s);\n",
2698 fprintf_indent (f
, indent
,
2699 " if (fndecl && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL)\n");
2700 fprintf_indent (f
, indent
,
2701 " switch (DECL_FUNCTION_CODE (fndecl))\n");
2702 fprintf_indent (f
, indent
,
2706 for (unsigned j
= 0; j
< generic_fns
.length (); ++j
)
2708 expr
*e
= as_a
<expr
*>(generic_fns
[j
]->op
);
2709 gcc_assert (e
->operation
->kind
== id_base::FN
);
2711 fprintf_indent (f
, indent
, "case %s:\n", e
->operation
->id
);
2712 fprintf_indent (f
, indent
, " {\n");
2713 generic_fns
[j
]->gen (f
, indent
+ 4, false);
2714 fprintf_indent (f
, indent
, " break;\n");
2715 fprintf_indent (f
, indent
, " }\n");
2719 fprintf_indent (f
, indent
, " default:;\n");
2720 fprintf_indent (f
, indent
, " }\n");
2721 fprintf_indent (f
, indent
, " break;\n");
2722 fprintf_indent (f
, indent
, " }\n");
2725 /* Close switch (TREE_CODE ()). */
2726 if (exprs_len
|| fns_len
|| gexprs_len
|| gfns_len
)
2729 fprintf_indent (f
, indent
, " default:;\n");
2730 fprintf_indent (f
, indent
, " }\n");
2733 for (unsigned i
= 0; i
< preds
.length (); ++i
)
2735 expr
*e
= as_a
<expr
*> (preds
[i
]->op
);
2736 predicate_id
*p
= as_a
<predicate_id
*> (e
->operation
);
2737 preds
[i
]->get_name (kid_opname
);
2738 fprintf_indent (f
, indent
, "tree %s_pops[%d];\n", kid_opname
, p
->nargs
);
2739 fprintf_indent (f
, indent
, "if (%s_%s (%s, %s_pops%s))\n",
2740 gimple
? "gimple" : "tree",
2741 p
->id
, kid_opname
, kid_opname
,
2742 gimple
? ", valueize" : "");
2743 fprintf_indent (f
, indent
, " {\n");
2744 for (int j
= 0; j
< p
->nargs
; ++j
)
2746 char child_opname
[20];
2747 preds
[i
]->gen_opname (child_opname
, j
);
2748 fprintf_indent (f
, indent
+ 4, "tree %s = %s_pops[%d];\n",
2749 child_opname
, kid_opname
, j
);
2751 preds
[i
]->gen_kids (f
, indent
+ 4, gimple
);
2755 for (unsigned i
= 0; i
< others
.length (); ++i
)
2756 others
[i
]->gen (f
, indent
, gimple
);
2759 /* Generate matching code for the decision tree operand. */
2762 dt_operand::gen (FILE *f
, int indent
, bool gimple
)
2767 unsigned n_braces
= 0;
2769 if (type
== DT_OPERAND
)
2772 case operand::OP_PREDICATE
:
2773 n_braces
= gen_predicate (f
, indent
, opname
, gimple
);
2776 case operand::OP_EXPR
:
2778 n_braces
= gen_gimple_expr (f
, indent
);
2780 n_braces
= gen_generic_expr (f
, indent
, opname
);
2786 else if (type
== DT_TRUE
)
2788 else if (type
== DT_MATCH
)
2789 n_braces
= gen_match_op (f
, indent
, opname
);
2793 indent
+= 4 * n_braces
;
2794 gen_kids (f
, indent
, gimple
);
2796 for (unsigned i
= 0; i
< n_braces
; ++i
)
2801 fprintf_indent (f
, indent
, " }\n");
2806 /* Generate code for the '(if ...)', '(with ..)' and actual transform
2807 step of a '(simplify ...)' or '(match ...)'. This handles everything
2808 that is not part of the decision tree (simplify->match).
2809 Main recursive worker. */
2812 dt_simplify::gen_1 (FILE *f
, int indent
, bool gimple
, operand
*result
)
2816 if (with_expr
*w
= dyn_cast
<with_expr
*> (result
))
2818 fprintf_indent (f
, indent
, "{\n");
2820 output_line_directive (f
, w
->location
);
2821 w
->with
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2822 gen_1 (f
, indent
, gimple
, w
->subexpr
);
2824 fprintf_indent (f
, indent
, "}\n");
2827 else if (if_expr
*ife
= dyn_cast
<if_expr
*> (result
))
2829 output_line_directive (f
, ife
->location
);
2830 fprintf_indent (f
, indent
, "if (");
2831 ife
->cond
->gen_transform (f
, indent
, NULL
, true, 1, "type", NULL
);
2833 fprintf_indent (f
, indent
+ 2, "{\n");
2835 gen_1 (f
, indent
, gimple
, ife
->trueexpr
);
2837 fprintf_indent (f
, indent
+ 2, "}\n");
2840 fprintf_indent (f
, indent
, "else\n");
2841 fprintf_indent (f
, indent
+ 2, "{\n");
2843 gen_1 (f
, indent
, gimple
, ife
->falseexpr
);
2845 fprintf_indent (f
, indent
+ 2, "}\n");
2851 /* Analyze captures and perform early-outs on the incoming arguments
2852 that cover cases we cannot handle. */
2853 capture_info
cinfo (s
, result
, gimple
);
2854 if (s
->kind
== simplify::SIMPLIFY
)
2858 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
2859 if (cinfo
.force_no_side_effects
& (1 << i
))
2861 fprintf_indent (f
, indent
,
2862 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
2865 warning_at (as_a
<expr
*> (s
->match
)->ops
[i
]->location
,
2866 "forcing toplevel operand to have no "
2869 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2870 if (cinfo
.info
[i
].cse_p
)
2872 else if (cinfo
.info
[i
].force_no_side_effects_p
2873 && (cinfo
.info
[i
].toplevel_msk
2874 & cinfo
.force_no_side_effects
) == 0)
2876 fprintf_indent (f
, indent
,
2877 "if (TREE_SIDE_EFFECTS (captures[%d])) "
2878 "return NULL_TREE;\n", i
);
2880 warning_at (cinfo
.info
[i
].c
->location
,
2881 "forcing captured operand to have no "
2884 else if ((cinfo
.info
[i
].toplevel_msk
2885 & cinfo
.force_no_side_effects
) != 0)
2886 /* Mark capture as having no side-effects if we had to verify
2887 that via forced toplevel operand checks. */
2888 cinfo
.info
[i
].force_no_side_effects_p
= true;
2892 /* Force single-use restriction by only allowing simple
2893 results via setting seq to NULL. */
2894 fprintf_indent (f
, indent
, "gimple_seq *lseq = seq;\n");
2895 bool first_p
= true;
2896 for (int i
= 0; i
<= s
->capture_max
; ++i
)
2897 if (cinfo
.info
[i
].force_single_use
)
2901 fprintf_indent (f
, indent
, "if (lseq\n");
2902 fprintf_indent (f
, indent
, " && (");
2908 fprintf_indent (f
, indent
, " || ");
2910 fprintf (f
, "!single_use (captures[%d])", i
);
2914 fprintf (f
, "))\n");
2915 fprintf_indent (f
, indent
, " lseq = NULL;\n");
2920 fprintf_indent (f
, indent
, "if (dump_file && (dump_flags & TDF_DETAILS)) "
2921 "fprintf (dump_file, \"Applying pattern ");
2922 output_line_directive (f
,
2923 result
? result
->location
: s
->match
->location
, true);
2924 fprintf (f
, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
2928 /* If there is no result then this is a predicate implementation. */
2929 fprintf_indent (f
, indent
, "return true;\n");
2933 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
2934 in outermost position). */
2935 if (result
->type
== operand::OP_EXPR
2936 && *as_a
<expr
*> (result
)->operation
== NON_LVALUE_EXPR
)
2937 result
= as_a
<expr
*> (result
)->ops
[0];
2938 if (result
->type
== operand::OP_EXPR
)
2940 expr
*e
= as_a
<expr
*> (result
);
2941 id_base
*opr
= e
->operation
;
2942 bool is_predicate
= false;
2943 /* When we delay operator substituting during lowering of fors we
2944 make sure that for code-gen purposes the effects of each substitute
2945 are the same. Thus just look at that. */
2946 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
2947 opr
= uid
->substitutes
[0];
2948 else if (is_a
<predicate_id
*> (opr
))
2949 is_predicate
= true;
2951 fprintf_indent (f
, indent
, "*res_code = %s;\n",
2952 *e
->operation
== CONVERT_EXPR
2953 ? "NOP_EXPR" : e
->operation
->id
);
2954 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
2957 snprintf (dest
, 32, "res_ops[%d]", j
);
2959 = get_operand_type (opr
,
2960 "type", e
->expr_type
,
2961 j
== 0 ? NULL
: "TREE_TYPE (res_ops[0])");
2962 /* We need to expand GENERIC conditions we captured from
2964 bool expand_generic_cond_exprs_p
2966 /* But avoid doing that if the GENERIC condition is
2967 valid - which it is in the first operand of COND_EXPRs
2968 and VEC_COND_EXRPs. */
2969 && ((!(*opr
== COND_EXPR
)
2970 && !(*opr
== VEC_COND_EXPR
))
2972 e
->ops
[j
]->gen_transform (f
, indent
, dest
, true, 1, optype
,
2974 indexes
, expand_generic_cond_exprs_p
);
2977 /* Re-fold the toplevel result. It's basically an embedded
2978 gimple_build w/o actually building the stmt. */
2980 fprintf_indent (f
, indent
,
2981 "gimple_resimplify%d (lseq, res_code, type, "
2982 "res_ops, valueize);\n", e
->ops
.length ());
2984 else if (result
->type
== operand::OP_CAPTURE
2985 || result
->type
== operand::OP_C_EXPR
)
2987 result
->gen_transform (f
, indent
, "res_ops[0]", true, 1, "type",
2988 &cinfo
, indexes
, false);
2989 fprintf_indent (f
, indent
, "*res_code = TREE_CODE (res_ops[0]);\n");
2990 if (is_a
<capture
*> (result
)
2991 && cinfo
.info
[as_a
<capture
*> (result
)->where
].cond_expr_cond_p
)
2993 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2994 with substituting a capture of that. */
2995 fprintf_indent (f
, indent
,
2996 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
2997 fprintf_indent (f
, indent
,
2999 fprintf_indent (f
, indent
,
3000 " tree tem = res_ops[0];\n");
3001 fprintf_indent (f
, indent
,
3002 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3003 fprintf_indent (f
, indent
,
3004 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3005 fprintf_indent (f
, indent
,
3011 fprintf_indent (f
, indent
, "return true;\n");
3015 bool is_predicate
= false;
3016 if (result
->type
== operand::OP_EXPR
)
3018 expr
*e
= as_a
<expr
*> (result
);
3019 id_base
*opr
= e
->operation
;
3020 /* When we delay operator substituting during lowering of fors we
3021 make sure that for code-gen purposes the effects of each substitute
3022 are the same. Thus just look at that. */
3023 if (user_id
*uid
= dyn_cast
<user_id
*> (opr
))
3024 opr
= uid
->substitutes
[0];
3025 else if (is_a
<predicate_id
*> (opr
))
3026 is_predicate
= true;
3027 /* Search for captures used multiple times in the result expression
3028 and dependent on TREE_SIDE_EFFECTS emit a SAVE_EXPR. */
3030 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3032 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3034 if (!cinfo
.info
[i
].force_no_side_effects_p
3035 && cinfo
.info
[i
].result_use_count
> 1)
3037 fprintf_indent (f
, indent
,
3038 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3040 fprintf_indent (f
, indent
,
3041 " captures[%d] = save_expr (captures[%d]);\n",
3045 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3049 snprintf (dest
, 32, "res_ops[%d]", j
);
3052 fprintf_indent (f
, indent
, "tree res_op%d;\n", j
);
3053 snprintf (dest
, 32, "res_op%d", j
);
3056 = get_operand_type (opr
,
3057 "type", e
->expr_type
,
3059 ? NULL
: "TREE_TYPE (res_op0)");
3060 e
->ops
[j
]->gen_transform (f
, indent
, dest
, false, 1, optype
,
3064 fprintf_indent (f
, indent
, "return true;\n");
3067 fprintf_indent (f
, indent
, "tree res;\n");
3068 /* Re-fold the toplevel result. Use non_lvalue to
3069 build NON_LVALUE_EXPRs so they get properly
3070 ignored when in GIMPLE form. */
3071 if (*opr
== NON_LVALUE_EXPR
)
3072 fprintf_indent (f
, indent
,
3073 "res = non_lvalue_loc (loc, res_op0);\n");
3076 if (is_a
<operator_id
*> (opr
))
3077 fprintf_indent (f
, indent
,
3078 "res = fold_build%d_loc (loc, %s, type",
3080 *e
->operation
== CONVERT_EXPR
3081 ? "NOP_EXPR" : e
->operation
->id
);
3084 fprintf_indent (f
, indent
,
3086 fprintf_indent (f
, indent
,
3087 " tree decl = builtin_decl_implicit (%s);\n",
3089 fprintf_indent (f
, indent
,
3090 " if (!decl) return NULL_TREE;\n");
3091 fprintf_indent (f
, indent
,
3092 " res = build_call_expr_loc "
3096 for (unsigned j
= 0; j
< e
->ops
.length (); ++j
)
3097 fprintf (f
, ", res_op%d", j
);
3098 fprintf (f
, ");\n");
3099 if (!is_a
<operator_id
*> (opr
))
3100 fprintf_indent (f
, indent
, "}\n");
3104 else if (result
->type
== operand::OP_CAPTURE
3105 || result
->type
== operand::OP_C_EXPR
)
3108 fprintf_indent (f
, indent
, "tree res;\n");
3109 result
->gen_transform (f
, indent
, "res", false, 1, "type",
3116 /* Search for captures not used in the result expression and dependent
3117 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3118 for (int i
= 0; i
< s
->capture_max
+ 1; ++i
)
3120 if (cinfo
.info
[i
].same_as
!= (unsigned)i
)
3122 if (!cinfo
.info
[i
].force_no_side_effects_p
3123 && !cinfo
.info
[i
].expr_p
3124 && cinfo
.info
[i
].result_use_count
== 0)
3126 fprintf_indent (f
, indent
,
3127 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3129 fprintf_indent (f
, indent
+ 2,
3130 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3131 "fold_ignored_result (captures[%d]), res);\n",
3135 fprintf_indent (f
, indent
, "return res;\n");
3140 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3141 step of a '(simplify ...)' or '(match ...)'. This handles everything
3142 that is not part of the decision tree (simplify->match). */
3145 dt_simplify::gen (FILE *f
, int indent
, bool gimple
)
3147 fprintf_indent (f
, indent
, "{\n");
3149 output_line_directive (f
,
3150 s
->result
? s
->result
->location
: s
->match
->location
);
3151 if (s
->capture_max
>= 0)
3154 fprintf_indent (f
, indent
, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3155 s
->capture_max
+ 1, indexes
[0]->get_name (opname
));
3157 for (int i
= 1; i
<= s
->capture_max
; ++i
)
3158 fprintf (f
, ", %s", indexes
[i
]->get_name (opname
));
3159 fprintf (f
, " };\n");
3162 /* If we have a split-out function for the actual transform, call it. */
3163 if (info
&& info
->fname
)
3167 fprintf_indent (f
, indent
, "if (%s (res_code, res_ops, seq, "
3168 "valueize, type, captures", info
->fname
);
3169 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3170 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3171 fprintf (f
, "))\n");
3172 fprintf_indent (f
, indent
, " return true;\n");
3176 fprintf_indent (f
, indent
, "tree res = %s (loc, type",
3178 for (unsigned i
= 0; i
< as_a
<expr
*> (s
->match
)->ops
.length (); ++i
)
3179 fprintf (f
, ", op%d", i
);
3180 fprintf (f
, ", captures");
3181 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3182 fprintf (f
, ", %s", s
->for_subst_vec
[i
].second
->id
);
3183 fprintf (f
, ");\n");
3184 fprintf_indent (f
, indent
, "if (res) return res;\n");
3189 for (unsigned i
= 0; i
< s
->for_subst_vec
.length (); ++i
)
3191 if (is_a
<operator_id
*> (s
->for_subst_vec
[i
].second
))
3192 fprintf_indent (f
, indent
, "enum tree_code %s = %s;\n",
3193 s
->for_subst_vec
[i
].first
->id
,
3194 s
->for_subst_vec
[i
].second
->id
);
3195 else if (is_a
<fn_id
*> (s
->for_subst_vec
[i
].second
))
3196 fprintf_indent (f
, indent
, "enum built_in_function %s = %s;\n",
3197 s
->for_subst_vec
[i
].first
->id
,
3198 s
->for_subst_vec
[i
].second
->id
);
3202 gen_1 (f
, indent
, gimple
, s
->result
);
3206 fprintf_indent (f
, indent
, "}\n");
3210 /* Hash function for finding equivalent transforms. */
3213 sinfo_hashmap_traits::hash (const key_type
&v
)
3215 /* Only bother to compare those originating from the same source pattern. */
3216 return v
->s
->result
->location
;
3219 /* Compare function for finding equivalent transforms. */
3222 compare_op (operand
*o1
, simplify
*s1
, operand
*o2
, simplify
*s2
)
3224 if (o1
->type
!= o2
->type
)
3229 case operand::OP_IF
:
3231 if_expr
*if1
= as_a
<if_expr
*> (o1
);
3232 if_expr
*if2
= as_a
<if_expr
*> (o2
);
3233 /* ??? Properly compare c-exprs. */
3234 if (if1
->cond
!= if2
->cond
)
3236 if (!compare_op (if1
->trueexpr
, s1
, if2
->trueexpr
, s2
))
3238 if (if1
->falseexpr
!= if2
->falseexpr
3240 && !compare_op (if1
->falseexpr
, s1
, if2
->falseexpr
, s2
)))
3244 case operand::OP_WITH
:
3246 with_expr
*with1
= as_a
<with_expr
*> (o1
);
3247 with_expr
*with2
= as_a
<with_expr
*> (o2
);
3248 if (with1
->with
!= with2
->with
)
3250 return compare_op (with1
->subexpr
, s1
, with2
->subexpr
, s2
);
3255 /* We've hit a result. Time to compare capture-infos - this is required
3256 in addition to the conservative pointer-equivalency of the result IL. */
3257 capture_info
cinfo1 (s1
, o1
, true);
3258 capture_info
cinfo2 (s2
, o2
, true);
3260 if (cinfo1
.force_no_side_effects
!= cinfo2
.force_no_side_effects
3261 || cinfo1
.info
.length () != cinfo2
.info
.length ())
3264 for (unsigned i
= 0; i
< cinfo1
.info
.length (); ++i
)
3266 if (cinfo1
.info
[i
].expr_p
!= cinfo2
.info
[i
].expr_p
3267 || cinfo1
.info
[i
].cse_p
!= cinfo2
.info
[i
].cse_p
3268 || (cinfo1
.info
[i
].force_no_side_effects_p
3269 != cinfo2
.info
[i
].force_no_side_effects_p
)
3270 || cinfo1
.info
[i
].force_single_use
!= cinfo2
.info
[i
].force_single_use
3271 || cinfo1
.info
[i
].cond_expr_cond_p
!= cinfo2
.info
[i
].cond_expr_cond_p
3272 /* toplevel_msk is an optimization */
3273 || cinfo1
.info
[i
].result_use_count
!= cinfo2
.info
[i
].result_use_count
3274 || cinfo1
.info
[i
].same_as
!= cinfo2
.info
[i
].same_as
3275 /* the pointer back to the capture is for diagnostics only */)
3279 /* ??? Deep-compare the actual result. */
3284 sinfo_hashmap_traits::equal_keys (const key_type
&v
,
3285 const key_type
&candidate
)
3287 return compare_op (v
->s
->result
, v
->s
, candidate
->s
->result
, candidate
->s
);
3291 /* Main entry to generate code for matching GIMPLE IL off the decision
3295 decision_tree::gen (FILE *f
, bool gimple
)
3301 fprintf (stderr
, "%s decision tree has %u leafs, maximum depth %u and "
3302 "a total number of %u nodes\n",
3303 gimple
? "GIMPLE" : "GENERIC",
3304 root
->num_leafs
, root
->max_level
, root
->total_size
);
3306 /* First split out the transform part of equal leafs. */
3309 for (sinfo_map_t::iterator iter
= si
.begin ();
3310 iter
!= si
.end (); ++iter
)
3312 sinfo
*s
= (*iter
).second
;
3313 /* Do not split out single uses. */
3320 fprintf (stderr
, "found %u uses of", s
->cnt
);
3321 output_line_directive (stderr
, s
->s
->s
->result
->location
);
3324 /* Generate a split out function with the leaf transform code. */
3325 s
->fname
= xasprintf ("%s_simplify_%u", gimple
? "gimple" : "generic",
3328 fprintf (f
, "\nstatic bool\n"
3329 "%s (code_helper *res_code, tree *res_ops,\n"
3330 " gimple_seq *seq, tree (*valueize)(tree) "
3331 "ATTRIBUTE_UNUSED,\n"
3332 " tree ARG_UNUSED (type), tree *ARG_UNUSED "
3337 fprintf (f
, "\nstatic tree\n"
3338 "%s (location_t ARG_UNUSED (loc), tree ARG_UNUSED (type),\n",
3339 (*iter
).second
->fname
);
3340 for (unsigned i
= 0;
3341 i
< as_a
<expr
*>(s
->s
->s
->match
)->ops
.length (); ++i
)
3342 fprintf (f
, " tree ARG_UNUSED (op%d),", i
);
3343 fprintf (f
, " tree *captures\n");
3345 for (unsigned i
= 0; i
< s
->s
->s
->for_subst_vec
.length (); ++i
)
3347 if (is_a
<operator_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3348 fprintf (f
, ", enum tree_code ARG_UNUSED (%s)",
3349 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3350 else if (is_a
<fn_id
*> (s
->s
->s
->for_subst_vec
[i
].second
))
3351 fprintf (f
, ", enum built_in_function ARG_UNUSED (%s)",
3352 s
->s
->s
->for_subst_vec
[i
].first
->id
);
3355 fprintf (f
, ")\n{\n");
3356 s
->s
->gen_1 (f
, 2, gimple
, s
->s
->s
->result
);
3358 fprintf (f
, " return false;\n");
3360 fprintf (f
, " return NULL_TREE;\n");
3363 fprintf (stderr
, "removed %u duplicate tails\n", rcnt
);
3365 for (unsigned n
= 1; n
<= 3; ++n
)
3367 /* First generate split-out functions. */
3368 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3370 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3371 expr
*e
= static_cast<expr
*>(dop
->op
);
3372 if (e
->ops
.length () != n
3373 /* Builtin simplifications are somewhat premature on
3374 GENERIC. The following drops patterns with outermost
3375 calls. It's easy to emit overloads for function code
3376 though if necessary. */
3378 && e
->operation
->kind
!= id_base::CODE
))
3382 fprintf (f
, "\nstatic bool\n"
3383 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3384 " gimple_seq *seq, tree (*valueize)(tree) "
3385 "ATTRIBUTE_UNUSED,\n"
3386 " code_helper ARG_UNUSED (code), tree "
3387 "ARG_UNUSED (type)\n",
3390 fprintf (f
, "\nstatic tree\n"
3391 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3392 "tree_code ARG_UNUSED (code), tree ARG_UNUSED (type)",
3394 for (unsigned i
= 0; i
< n
; ++i
)
3395 fprintf (f
, ", tree op%d", i
);
3398 dop
->gen_kids (f
, 2, gimple
);
3400 fprintf (f
, " return false;\n");
3402 fprintf (f
, " return NULL_TREE;\n");
3406 /* Then generate the main entry with the outermost switch and
3407 tail-calls to the split-out functions. */
3409 fprintf (f
, "\nstatic bool\n"
3410 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3411 " gimple_seq *seq, tree (*valueize)(tree),\n"
3412 " code_helper code, tree type");
3414 fprintf (f
, "\ntree\n"
3415 "generic_simplify (location_t loc, enum tree_code code, "
3416 "tree type ATTRIBUTE_UNUSED");
3417 for (unsigned i
= 0; i
< n
; ++i
)
3418 fprintf (f
, ", tree op%d", i
);
3423 fprintf (f
, " switch (code.get_rep())\n"
3426 fprintf (f
, " switch (code)\n"
3428 for (unsigned i
= 0; i
< root
->kids
.length (); i
++)
3430 dt_operand
*dop
= static_cast<dt_operand
*>(root
->kids
[i
]);
3431 expr
*e
= static_cast<expr
*>(dop
->op
);
3432 if (e
->ops
.length () != n
3433 /* Builtin simplifications are somewhat premature on
3434 GENERIC. The following drops patterns with outermost
3435 calls. It's easy to emit overloads for function code
3436 though if necessary. */
3438 && e
->operation
->kind
!= id_base::CODE
))
3441 if (*e
->operation
== CONVERT_EXPR
3442 || *e
->operation
== NOP_EXPR
)
3443 fprintf (f
, " CASE_CONVERT:\n");
3445 fprintf (f
, " case %s%s:\n",
3446 is_a
<fn_id
*> (e
->operation
) ? "-" : "",
3449 fprintf (f
, " return gimple_simplify_%s (res_code, res_ops, "
3450 "seq, valueize, code, type", e
->operation
->id
);
3452 fprintf (f
, " return generic_simplify_%s (loc, code, type",
3454 for (unsigned i
= 0; i
< n
; ++i
)
3455 fprintf (f
, ", op%d", i
);
3456 fprintf (f
, ");\n");
3458 fprintf (f
, " default:;\n"
3462 fprintf (f
, " return false;\n");
3464 fprintf (f
, " return NULL_TREE;\n");
3469 /* Output code to implement the predicate P from the decision tree DT. */
3472 write_predicate (FILE *f
, predicate_id
*p
, decision_tree
&dt
, bool gimple
)
3474 fprintf (f
, "\nbool\n"
3475 "%s%s (tree t%s%s)\n"
3476 "{\n", gimple
? "gimple_" : "tree_", p
->id
,
3477 p
->nargs
> 0 ? ", tree *res_ops" : "",
3478 gimple
? ", tree (*valueize)(tree)" : "");
3479 /* Conveniently make 'type' available. */
3480 fprintf_indent (f
, 2, "tree type = TREE_TYPE (t);\n");
3483 fprintf_indent (f
, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3484 dt
.root
->gen_kids (f
, 2, gimple
);
3486 fprintf_indent (f
, 2, "return false;\n"
3490 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3493 write_header (FILE *f
, const char *head
)
3495 fprintf (f
, "/* Generated automatically by the program `genmatch' from\n");
3496 fprintf (f
, " a IL pattern matching and simplification description. */\n");
3498 /* Include the header instead of writing it awkwardly quoted here. */
3499 fprintf (f
, "\n#include \"%s\"\n", head
);
3509 parser (cpp_reader
*);
3512 const cpp_token
*next ();
3513 const cpp_token
*peek (unsigned = 1);
3514 const cpp_token
*peek_ident (const char * = NULL
, unsigned = 1);
3515 const cpp_token
*expect (enum cpp_ttype
);
3516 const cpp_token
*eat_token (enum cpp_ttype
);
3517 const char *get_string ();
3518 const char *get_ident ();
3519 const cpp_token
*eat_ident (const char *);
3520 const char *get_number ();
3522 id_base
*parse_operation ();
3523 operand
*parse_capture (operand
*, bool);
3524 operand
*parse_expr ();
3525 c_expr
*parse_c_expr (cpp_ttype
);
3526 operand
*parse_op ();
3528 void record_operlist (source_location
, user_id
*);
3530 void parse_pattern ();
3531 operand
*parse_result (operand
*, predicate_id
*);
3532 void push_simplify (simplify::simplify_kind
,
3533 vec
<simplify
*>&, operand
*, operand
*);
3534 void parse_simplify (simplify::simplify_kind
,
3535 vec
<simplify
*>&, predicate_id
*, operand
*);
3536 void parse_for (source_location
);
3537 void parse_if (source_location
);
3538 void parse_predicates (source_location
);
3539 void parse_operator_list (source_location
);
3542 vec
<c_expr
*> active_ifs
;
3543 vec
<vec
<user_id
*> > active_fors
;
3544 hash_set
<user_id
*> *oper_lists_set
;
3545 vec
<user_id
*> oper_lists
;
3547 cid_map_t
*capture_ids
;
3550 vec
<simplify
*> simplifiers
;
3551 vec
<predicate_id
*> user_predicates
;
3552 bool parsing_match_operand
;
3555 /* Lexing helpers. */
3557 /* Read the next non-whitespace token from R. */
3562 const cpp_token
*token
;
3565 token
= cpp_get_token (r
);
3567 while (token
->type
== CPP_PADDING
3568 && token
->type
!= CPP_EOF
);
3572 /* Peek at the next non-whitespace token from R. */
3575 parser::peek (unsigned num
)
3577 const cpp_token
*token
;
3581 token
= cpp_peek_token (r
, i
++);
3583 while ((token
->type
== CPP_PADDING
3584 && token
->type
!= CPP_EOF
)
3586 /* If we peek at EOF this is a fatal error as it leaves the
3587 cpp_reader in unusable state. Assume we really wanted a
3588 token and thus this EOF is unexpected. */
3589 if (token
->type
== CPP_EOF
)
3590 fatal_at (token
, "unexpected end of file");
3594 /* Peek at the next identifier token (or return NULL if the next
3595 token is not an identifier or equal to ID if supplied). */
3598 parser::peek_ident (const char *id
, unsigned num
)
3600 const cpp_token
*token
= peek (num
);
3601 if (token
->type
!= CPP_NAME
)
3607 const char *t
= (const char *) CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3608 if (strcmp (id
, t
) == 0)
3614 /* Read the next token from R and assert it is of type TK. */
3617 parser::expect (enum cpp_ttype tk
)
3619 const cpp_token
*token
= next ();
3620 if (token
->type
!= tk
)
3621 fatal_at (token
, "expected %s, got %s",
3622 cpp_type2name (tk
, 0), cpp_type2name (token
->type
, 0));
3627 /* Consume the next token from R and assert it is of type TK. */
3630 parser::eat_token (enum cpp_ttype tk
)
3635 /* Read the next token from R and assert it is of type CPP_STRING and
3636 return its value. */
3639 parser::get_string ()
3641 const cpp_token
*token
= expect (CPP_STRING
);
3642 return (const char *)token
->val
.str
.text
;
3645 /* Read the next token from R and assert it is of type CPP_NAME and
3646 return its value. */
3649 parser::get_ident ()
3651 const cpp_token
*token
= expect (CPP_NAME
);
3652 return (const char *)CPP_HASHNODE (token
->val
.node
.node
)->ident
.str
;
3655 /* Eat an identifier token with value S from R. */
3658 parser::eat_ident (const char *s
)
3660 const cpp_token
*token
= peek ();
3661 const char *t
= get_ident ();
3662 if (strcmp (s
, t
) != 0)
3663 fatal_at (token
, "expected '%s' got '%s'\n", s
, t
);
3667 /* Read the next token from R and assert it is of type CPP_NUMBER and
3668 return its value. */
3671 parser::get_number ()
3673 const cpp_token
*token
= expect (CPP_NUMBER
);
3674 return (const char *)token
->val
.str
.text
;
3678 /* Record an operator-list use for transparent for handling. */
3681 parser::record_operlist (source_location loc
, user_id
*p
)
3683 if (!oper_lists_set
->add (p
))
3685 if (!oper_lists
.is_empty ()
3686 && oper_lists
[0]->substitutes
.length () != p
->substitutes
.length ())
3687 fatal_at (loc
, "User-defined operator list does not have the "
3688 "same number of entries as others used in the pattern");
3689 oper_lists
.safe_push (p
);
3693 /* Parse the operator ID, special-casing convert?, convert1? and
3697 parser::parse_operation ()
3699 const cpp_token
*id_tok
= peek ();
3700 const char *id
= get_ident ();
3701 const cpp_token
*token
= peek ();
3702 if (strcmp (id
, "convert0") == 0)
3703 fatal_at (id_tok
, "use 'convert?' here");
3704 else if (strcmp (id
, "view_convert0") == 0)
3705 fatal_at (id_tok
, "use 'view_convert?' here");
3706 if (token
->type
== CPP_QUERY
3707 && !(token
->flags
& PREV_WHITE
))
3709 if (strcmp (id
, "convert") == 0)
3711 else if (strcmp (id
, "convert1") == 0)
3713 else if (strcmp (id
, "convert2") == 0)
3715 else if (strcmp (id
, "view_convert") == 0)
3716 id
= "view_convert0";
3717 else if (strcmp (id
, "view_convert1") == 0)
3719 else if (strcmp (id
, "view_convert2") == 0)
3722 fatal_at (id_tok
, "non-convert operator conditionalized");
3724 if (!parsing_match_operand
)
3725 fatal_at (id_tok
, "conditional convert can only be used in "
3726 "match expression");
3727 eat_token (CPP_QUERY
);
3729 else if (strcmp (id
, "convert1") == 0
3730 || strcmp (id
, "convert2") == 0
3731 || strcmp (id
, "view_convert1") == 0
3732 || strcmp (id
, "view_convert2") == 0)
3733 fatal_at (id_tok
, "expected '?' after conditional operator");
3734 id_base
*op
= get_operator (id
);
3736 fatal_at (id_tok
, "unknown operator %s", id
);
3738 user_id
*p
= dyn_cast
<user_id
*> (op
);
3739 if (p
&& p
->is_oper_list
)
3741 if (active_fors
.length() == 0)
3742 record_operlist (id_tok
->src_loc
, p
);
3744 fatal_at (id_tok
, "operator-list %s cannot be exapnded inside 'for'", id
);
3750 capture = '@'<number> */
3753 parser::parse_capture (operand
*op
, bool require_existing
)
3755 source_location src_loc
= eat_token (CPP_ATSIGN
)->src_loc
;
3756 const cpp_token
*token
= peek ();
3757 const char *id
= NULL
;
3758 if (token
->type
== CPP_NUMBER
)
3760 else if (token
->type
== CPP_NAME
)
3763 fatal_at (token
, "expected number or identifier");
3764 unsigned next_id
= capture_ids
->elements ();
3766 unsigned &num
= capture_ids
->get_or_insert (id
, &existed
);
3769 if (require_existing
)
3770 fatal_at (src_loc
, "unknown capture id");
3773 return new capture (src_loc
, num
, op
);
3776 /* Parse an expression
3777 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
3780 parser::parse_expr ()
3782 const cpp_token
*token
= peek ();
3783 expr
*e
= new expr (parse_operation (), token
->src_loc
);
3786 bool is_commutative
= false;
3787 bool force_capture
= false;
3788 const char *expr_type
= NULL
;
3790 if (token
->type
== CPP_COLON
3791 && !(token
->flags
& PREV_WHITE
))
3793 eat_token (CPP_COLON
);
3795 if (token
->type
== CPP_NAME
3796 && !(token
->flags
& PREV_WHITE
))
3798 const char *s
= get_ident ();
3799 if (!parsing_match_operand
)
3807 is_commutative
= true;
3808 else if (*sp
== 's')
3810 e
->force_single_use
= true;
3811 force_capture
= true;
3814 fatal_at (token
, "flag %c not recognized", *sp
);
3821 fatal_at (token
, "expected flag or type specifying identifier");
3824 if (token
->type
== CPP_ATSIGN
3825 && !(token
->flags
& PREV_WHITE
))
3826 op
= parse_capture (e
, !parsing_match_operand
);
3827 else if (force_capture
)
3829 unsigned num
= capture_ids
->elements ();
3832 sprintf (id
, "__%u", num
);
3833 capture_ids
->get_or_insert (xstrdup (id
), &existed
);
3835 fatal_at (token
, "reserved capture id '%s' already used", id
);
3836 op
= new capture (token
->src_loc
, num
, e
);
3842 const cpp_token
*token
= peek ();
3843 if (token
->type
== CPP_CLOSE_PAREN
)
3845 if (e
->operation
->nargs
!= -1
3846 && e
->operation
->nargs
!= (int) e
->ops
.length ())
3847 fatal_at (token
, "'%s' expects %u operands, not %u",
3848 e
->operation
->id
, e
->operation
->nargs
, e
->ops
.length ());
3851 if (e
->ops
.length () == 2)
3852 e
->is_commutative
= true;
3854 fatal_at (token
, "only binary operators or function with "
3855 "two arguments can be marked commutative");
3857 e
->expr_type
= expr_type
;
3860 else if (!(token
->flags
& PREV_WHITE
))
3861 fatal_at (token
, "expected expression operand");
3863 e
->append_op (parse_op ());
3868 /* Lex native C code delimited by START recording the preprocessing tokens
3869 for later processing.
3870 c_expr = ('{'|'(') <pp token>... ('}'|')') */
3873 parser::parse_c_expr (cpp_ttype start
)
3875 const cpp_token
*token
;
3878 vec
<cpp_token
> code
= vNULL
;
3879 unsigned nr_stmts
= 0;
3880 source_location loc
= eat_token (start
)->src_loc
;
3881 if (start
== CPP_OPEN_PAREN
)
3882 end
= CPP_CLOSE_PAREN
;
3883 else if (start
== CPP_OPEN_BRACE
)
3884 end
= CPP_CLOSE_BRACE
;
3892 /* Count brace pairs to find the end of the expr to match. */
3893 if (token
->type
== start
)
3895 else if (token
->type
== end
3899 /* This is a lame way of counting the number of statements. */
3900 if (token
->type
== CPP_SEMICOLON
)
3903 /* If this is possibly a user-defined identifier mark it used. */
3904 if (token
->type
== CPP_NAME
)
3906 id_base
*idb
= get_operator ((const char *)CPP_HASHNODE
3907 (token
->val
.node
.node
)->ident
.str
);
3909 if (idb
&& (p
= dyn_cast
<user_id
*> (idb
)) && p
->is_oper_list
)
3910 record_operlist (token
->src_loc
, p
);
3913 /* Record the token. */
3914 code
.safe_push (*token
);
3917 return new c_expr (r
, loc
, code
, nr_stmts
, vNULL
, capture_ids
);
3920 /* Parse an operand which is either an expression, a predicate or
3921 a standalone capture.
3922 op = predicate | expr | c_expr | capture */
3927 const cpp_token
*token
= peek ();
3928 struct operand
*op
= NULL
;
3929 if (token
->type
== CPP_OPEN_PAREN
)
3931 eat_token (CPP_OPEN_PAREN
);
3933 eat_token (CPP_CLOSE_PAREN
);
3935 else if (token
->type
== CPP_OPEN_BRACE
)
3937 op
= parse_c_expr (CPP_OPEN_BRACE
);
3941 /* Remaining ops are either empty or predicates */
3942 if (token
->type
== CPP_NAME
)
3944 const char *id
= get_ident ();
3945 id_base
*opr
= get_operator (id
);
3947 fatal_at (token
, "expected predicate name");
3948 if (operator_id
*code
= dyn_cast
<operator_id
*> (opr
))
3950 if (code
->nargs
!= 0)
3951 fatal_at (token
, "using an operator with operands as predicate");
3952 /* Parse the zero-operand operator "predicates" as
3954 op
= new expr (opr
, token
->src_loc
);
3956 else if (user_id
*code
= dyn_cast
<user_id
*> (opr
))
3958 if (code
->nargs
!= 0)
3959 fatal_at (token
, "using an operator with operands as predicate");
3960 /* Parse the zero-operand operator "predicates" as
3962 op
= new expr (opr
, token
->src_loc
);
3964 else if (predicate_id
*p
= dyn_cast
<predicate_id
*> (opr
))
3965 op
= new predicate (p
, token
->src_loc
);
3967 fatal_at (token
, "using an unsupported operator as predicate");
3968 if (!parsing_match_operand
)
3969 fatal_at (token
, "predicates are only allowed in match expression");
3971 if (token
->flags
& PREV_WHITE
)
3974 else if (token
->type
!= CPP_COLON
3975 && token
->type
!= CPP_ATSIGN
)
3976 fatal_at (token
, "expected expression or predicate");
3977 /* optionally followed by a capture and a predicate. */
3978 if (token
->type
== CPP_COLON
)
3979 fatal_at (token
, "not implemented: predicate on leaf operand");
3980 if (token
->type
== CPP_ATSIGN
)
3981 op
= parse_capture (op
, !parsing_match_operand
);
3987 /* Create a new simplify from the current parsing state and MATCH,
3988 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
3991 parser::push_simplify (simplify::simplify_kind kind
,
3992 vec
<simplify
*>& simplifiers
,
3993 operand
*match
, operand
*result
)
3995 /* Build and push a temporary for operator list uses in expressions. */
3996 if (!oper_lists
.is_empty ())
3997 active_fors
.safe_push (oper_lists
);
3999 simplifiers
.safe_push
4000 (new simplify (kind
, match
, result
,
4001 active_fors
.copy (), capture_ids
));
4003 if (!oper_lists
.is_empty ())
4008 <result-op> = <op> | <if> | <with>
4009 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4010 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4014 parser::parse_result (operand
*result
, predicate_id
*matcher
)
4016 const cpp_token
*token
= peek ();
4017 if (token
->type
!= CPP_OPEN_PAREN
)
4020 eat_token (CPP_OPEN_PAREN
);
4021 if (peek_ident ("if"))
4024 if_expr
*ife
= new if_expr (token
->src_loc
);
4025 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4026 if (peek ()->type
== CPP_OPEN_PAREN
)
4028 ife
->trueexpr
= parse_result (result
, matcher
);
4029 if (peek ()->type
== CPP_OPEN_PAREN
)
4030 ife
->falseexpr
= parse_result (result
, matcher
);
4031 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4032 ife
->falseexpr
= parse_op ();
4034 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4036 ife
->trueexpr
= parse_op ();
4037 if (peek ()->type
== CPP_OPEN_PAREN
)
4038 ife
->falseexpr
= parse_result (result
, matcher
);
4039 else if (peek ()->type
!= CPP_CLOSE_PAREN
)
4040 ife
->falseexpr
= parse_op ();
4042 /* If this if is immediately closed then it contains a
4043 manual matcher or is part of a predicate definition. */
4044 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4047 fatal_at (peek (), "manual transform not implemented");
4048 ife
->trueexpr
= result
;
4050 eat_token (CPP_CLOSE_PAREN
);
4053 else if (peek_ident ("with"))
4056 with_expr
*withe
= new with_expr (token
->src_loc
);
4057 /* Parse (with c-expr expr) as (if-with (true) expr). */
4058 withe
->with
= parse_c_expr (CPP_OPEN_BRACE
);
4059 withe
->with
->nr_stmts
= 0;
4060 withe
->subexpr
= parse_result (result
, matcher
);
4061 eat_token (CPP_CLOSE_PAREN
);
4064 else if (peek_ident ("switch"))
4066 token
= eat_ident ("switch");
4067 source_location ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4069 if_expr
*ife
= new if_expr (ifloc
);
4071 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4072 if (peek ()->type
== CPP_OPEN_PAREN
)
4073 ife
->trueexpr
= parse_result (result
, matcher
);
4075 ife
->trueexpr
= parse_op ();
4076 eat_token (CPP_CLOSE_PAREN
);
4077 if (peek ()->type
!= CPP_OPEN_PAREN
4078 || !peek_ident ("if", 2))
4079 fatal_at (token
, "switch can be implemented with a single if");
4080 while (peek ()->type
!= CPP_CLOSE_PAREN
)
4082 if (peek ()->type
== CPP_OPEN_PAREN
)
4084 if (peek_ident ("if", 2))
4086 ifloc
= eat_token (CPP_OPEN_PAREN
)->src_loc
;
4088 ife
->falseexpr
= new if_expr (ifloc
);
4089 ife
= as_a
<if_expr
*> (ife
->falseexpr
);
4090 ife
->cond
= parse_c_expr (CPP_OPEN_PAREN
);
4091 if (peek ()->type
== CPP_OPEN_PAREN
)
4092 ife
->trueexpr
= parse_result (result
, matcher
);
4094 ife
->trueexpr
= parse_op ();
4095 eat_token (CPP_CLOSE_PAREN
);
4099 /* switch default clause */
4100 ife
->falseexpr
= parse_result (result
, matcher
);
4101 eat_token (CPP_CLOSE_PAREN
);
4107 /* switch default clause */
4108 ife
->falseexpr
= parse_op ();
4109 eat_token (CPP_CLOSE_PAREN
);
4113 eat_token (CPP_CLOSE_PAREN
);
4118 operand
*op
= result
;
4121 eat_token (CPP_CLOSE_PAREN
);
4127 simplify = 'simplify' <expr> <result-op>
4129 match = 'match' <ident> <expr> [<result-op>]
4130 and fill SIMPLIFIERS with the results. */
4133 parser::parse_simplify (simplify::simplify_kind kind
,
4134 vec
<simplify
*>& simplifiers
, predicate_id
*matcher
,
4137 /* Reset the capture map. */
4139 capture_ids
= new cid_map_t
;
4140 /* Reset oper_lists and set. */
4141 hash_set
<user_id
*> olist
;
4142 oper_lists_set
= &olist
;
4145 const cpp_token
*loc
= peek ();
4146 parsing_match_operand
= true;
4147 struct operand
*match
= parse_op ();
4148 parsing_match_operand
= false;
4149 if (match
->type
== operand::OP_CAPTURE
&& !matcher
)
4150 fatal_at (loc
, "outermost expression cannot be captured");
4151 if (match
->type
== operand::OP_EXPR
4152 && is_a
<predicate_id
*> (as_a
<expr
*> (match
)->operation
))
4153 fatal_at (loc
, "outermost expression cannot be a predicate");
4155 /* Splice active_ifs onto result and continue parsing the
4157 if_expr
*active_if
= NULL
;
4158 for (int i
= active_ifs
.length (); i
> 0; --i
)
4160 if_expr
*ifc
= new if_expr (active_ifs
[i
-1]->location
);
4161 ifc
->cond
= active_ifs
[i
-1];
4162 ifc
->trueexpr
= active_if
;
4165 if_expr
*outermost_if
= active_if
;
4166 while (active_if
&& active_if
->trueexpr
)
4167 active_if
= as_a
<if_expr
*> (active_if
->trueexpr
);
4169 const cpp_token
*token
= peek ();
4171 /* If this if is immediately closed then it is part of a predicate
4172 definition. Push it. */
4173 if (token
->type
== CPP_CLOSE_PAREN
)
4176 fatal_at (token
, "expected transform expression");
4179 active_if
->trueexpr
= result
;
4180 result
= outermost_if
;
4182 push_simplify (kind
, simplifiers
, match
, result
);
4186 operand
*tem
= parse_result (result
, matcher
);
4189 active_if
->trueexpr
= tem
;
4190 result
= outermost_if
;
4195 push_simplify (kind
, simplifiers
, match
, result
);
4198 /* Parsing of the outer control structures. */
4200 /* Parse a for expression
4201 for = '(' 'for' <subst>... <pattern> ')'
4202 subst = <ident> '(' <ident>... ')' */
4205 parser::parse_for (source_location
)
4207 auto_vec
<const cpp_token
*> user_id_tokens
;
4208 vec
<user_id
*> user_ids
= vNULL
;
4209 const cpp_token
*token
;
4210 unsigned min_n_opers
= 0, max_n_opers
= 0;
4215 if (token
->type
!= CPP_NAME
)
4218 /* Insert the user defined operators into the operator hash. */
4219 const char *id
= get_ident ();
4220 if (get_operator (id
) != NULL
)
4221 fatal_at (token
, "operator already defined");
4222 user_id
*op
= new user_id (id
);
4223 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4225 user_ids
.safe_push (op
);
4226 user_id_tokens
.safe_push (token
);
4228 eat_token (CPP_OPEN_PAREN
);
4231 while ((token
= peek_ident ()) != 0)
4233 const char *oper
= get_ident ();
4234 id_base
*idb
= get_operator (oper
);
4236 fatal_at (token
, "no such operator '%s'", oper
);
4237 if (*idb
== CONVERT0
|| *idb
== CONVERT1
|| *idb
== CONVERT2
4238 || *idb
== VIEW_CONVERT0
|| *idb
== VIEW_CONVERT1
4239 || *idb
== VIEW_CONVERT2
)
4240 fatal_at (token
, "conditional operators cannot be used inside for");
4244 else if (idb
->nargs
== -1)
4246 else if (idb
->nargs
!= arity
)
4247 fatal_at (token
, "operator '%s' with arity %d does not match "
4248 "others with arity %d", oper
, idb
->nargs
, arity
);
4250 user_id
*p
= dyn_cast
<user_id
*> (idb
);
4253 if (p
->is_oper_list
)
4254 op
->substitutes
.safe_splice (p
->substitutes
);
4256 fatal_at (token
, "iterator cannot be used as operator-list");
4259 op
->substitutes
.safe_push (idb
);
4262 token
= expect (CPP_CLOSE_PAREN
);
4264 unsigned nsubstitutes
= op
->substitutes
.length ();
4265 if (nsubstitutes
== 0)
4266 fatal_at (token
, "A user-defined operator must have at least "
4267 "one substitution");
4268 if (max_n_opers
== 0)
4270 min_n_opers
= nsubstitutes
;
4271 max_n_opers
= nsubstitutes
;
4275 if (nsubstitutes
% min_n_opers
!= 0
4276 && min_n_opers
% nsubstitutes
!= 0)
4277 fatal_at (token
, "All user-defined identifiers must have a "
4278 "multiple number of operator substitutions of the "
4279 "smallest number of substitutions");
4280 if (nsubstitutes
< min_n_opers
)
4281 min_n_opers
= nsubstitutes
;
4282 else if (nsubstitutes
> max_n_opers
)
4283 max_n_opers
= nsubstitutes
;
4287 unsigned n_ids
= user_ids
.length ();
4289 fatal_at (token
, "for requires at least one user-defined identifier");
4292 if (token
->type
== CPP_CLOSE_PAREN
)
4293 fatal_at (token
, "no pattern defined in for");
4295 active_fors
.safe_push (user_ids
);
4299 if (token
->type
== CPP_CLOSE_PAREN
)
4305 /* Remove user-defined operators from the hash again. */
4306 for (unsigned i
= 0; i
< user_ids
.length (); ++i
)
4308 if (!user_ids
[i
]->used
)
4309 warning_at (user_id_tokens
[i
],
4310 "operator %s defined but not used", user_ids
[i
]->id
);
4311 operators
->remove_elt (user_ids
[i
]);
4315 /* Parse an identifier associated with a list of operators.
4316 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4319 parser::parse_operator_list (source_location
)
4321 const cpp_token
*token
= peek ();
4322 const char *id
= get_ident ();
4324 if (get_operator (id
) != 0)
4325 fatal_at (token
, "operator %s already defined", id
);
4327 user_id
*op
= new user_id (id
, true);
4330 while ((token
= peek_ident ()) != 0)
4333 const char *oper
= get_ident ();
4334 id_base
*idb
= get_operator (oper
);
4337 fatal_at (token
, "no such operator '%s'", oper
);
4341 else if (idb
->nargs
== -1)
4343 else if (arity
!= idb
->nargs
)
4344 fatal_at (token
, "operator '%s' with arity %d does not match "
4345 "others with arity %d", oper
, idb
->nargs
, arity
);
4347 /* We allow composition of multiple operator lists. */
4348 if (user_id
*p
= dyn_cast
<user_id
*> (idb
))
4349 op
->substitutes
.safe_splice (p
->substitutes
);
4351 op
->substitutes
.safe_push (idb
);
4354 // Check that there is no junk after id-list
4356 if (token
->type
!= CPP_CLOSE_PAREN
)
4357 fatal_at (token
, "expected identifier got %s", cpp_type2name (token
->type
, 0));
4359 if (op
->substitutes
.length () == 0)
4360 fatal_at (token
, "operator-list cannot be empty");
4363 id_base
**slot
= operators
->find_slot_with_hash (op
, op
->hashval
, INSERT
);
4367 /* Parse an outer if expression.
4368 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4371 parser::parse_if (source_location
)
4373 c_expr
*ifexpr
= parse_c_expr (CPP_OPEN_PAREN
);
4375 const cpp_token
*token
= peek ();
4376 if (token
->type
== CPP_CLOSE_PAREN
)
4377 fatal_at (token
, "no pattern defined in if");
4379 active_ifs
.safe_push (ifexpr
);
4382 const cpp_token
*token
= peek ();
4383 if (token
->type
== CPP_CLOSE_PAREN
)
4391 /* Parse a list of predefined predicate identifiers.
4392 preds = '(' 'define_predicates' <ident>... ')' */
4395 parser::parse_predicates (source_location
)
4399 const cpp_token
*token
= peek ();
4400 if (token
->type
!= CPP_NAME
)
4403 add_predicate (get_ident ());
4408 /* Parse outer control structures.
4409 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4412 parser::parse_pattern ()
4414 /* All clauses start with '('. */
4415 eat_token (CPP_OPEN_PAREN
);
4416 const cpp_token
*token
= peek ();
4417 const char *id
= get_ident ();
4418 if (strcmp (id
, "simplify") == 0)
4420 parse_simplify (simplify::SIMPLIFY
, simplifiers
, NULL
, NULL
);
4423 else if (strcmp (id
, "match") == 0)
4425 bool with_args
= false;
4426 source_location e_loc
= peek ()->src_loc
;
4427 if (peek ()->type
== CPP_OPEN_PAREN
)
4429 eat_token (CPP_OPEN_PAREN
);
4432 const char *name
= get_ident ();
4433 id_base
*id
= get_operator (name
);
4437 p
= add_predicate (name
);
4438 user_predicates
.safe_push (p
);
4440 else if ((p
= dyn_cast
<predicate_id
*> (id
)))
4443 fatal_at (token
, "cannot add a match to a non-predicate ID");
4444 /* Parse (match <id> <arg>... (match-expr)) here. */
4448 capture_ids
= new cid_map_t
;
4449 e
= new expr (p
, e_loc
);
4450 while (peek ()->type
== CPP_ATSIGN
)
4451 e
->append_op (parse_capture (NULL
, false));
4452 eat_token (CPP_CLOSE_PAREN
);
4455 && ((e
&& e
->ops
.length () != (unsigned)p
->nargs
)
4456 || (!e
&& p
->nargs
!= 0)))
4457 fatal_at (token
, "non-matching number of match operands");
4458 p
->nargs
= e
? e
->ops
.length () : 0;
4459 parse_simplify (simplify::MATCH
, p
->matchers
, p
, e
);
4462 else if (strcmp (id
, "for") == 0)
4463 parse_for (token
->src_loc
);
4464 else if (strcmp (id
, "if") == 0)
4465 parse_if (token
->src_loc
);
4466 else if (strcmp (id
, "define_predicates") == 0)
4468 if (active_ifs
.length () > 0
4469 || active_fors
.length () > 0)
4470 fatal_at (token
, "define_predicates inside if or for is not supported");
4471 parse_predicates (token
->src_loc
);
4473 else if (strcmp (id
, "define_operator_list") == 0)
4475 if (active_ifs
.length () > 0
4476 || active_fors
.length () > 0)
4477 fatal_at (token
, "operator-list inside if or for is not supported");
4478 parse_operator_list (token
->src_loc
);
4481 fatal_at (token
, "expected %s'simplify', 'match', 'for' or 'if'",
4482 active_ifs
.length () == 0 && active_fors
.length () == 0
4483 ? "'define_predicates', " : "");
4485 eat_token (CPP_CLOSE_PAREN
);
4488 /* Main entry of the parser. Repeatedly parse outer control structures. */
4490 parser::parser (cpp_reader
*r_
)
4494 active_fors
= vNULL
;
4495 simplifiers
= vNULL
;
4496 oper_lists_set
= NULL
;
4499 user_predicates
= vNULL
;
4500 parsing_match_operand
= false;
4502 const cpp_token
*token
= next ();
4503 while (token
->type
!= CPP_EOF
)
4505 _cpp_backup_tokens (r
, 1);
4512 /* Helper for the linemap code. */
4515 round_alloc_size (size_t s
)
4521 /* The genmatch generator progam. It reads from a pattern description
4522 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4525 main (int argc
, char **argv
)
4529 progname
= "genmatch";
4535 char *input
= argv
[argc
-1];
4536 for (int i
= 1; i
< argc
- 1; ++i
)
4538 if (strcmp (argv
[i
], "--gimple") == 0)
4540 else if (strcmp (argv
[i
], "--generic") == 0)
4542 else if (strcmp (argv
[i
], "-v") == 0)
4544 else if (strcmp (argv
[i
], "-vv") == 0)
4548 fprintf (stderr
, "Usage: genmatch "
4549 "[--gimple] [--generic] [-v[v]] input\n");
4554 line_table
= XCNEW (struct line_maps
);
4555 linemap_init (line_table
, 0);
4556 line_table
->reallocator
= xrealloc
;
4557 line_table
->round_alloc_size
= round_alloc_size
;
4559 r
= cpp_create_reader (CLK_GNUC99
, NULL
, line_table
);
4560 cpp_callbacks
*cb
= cpp_get_callbacks (r
);
4561 cb
->error
= error_cb
;
4563 if (!cpp_read_main_file (r
, input
))
4565 cpp_define (r
, gimple
? "GIMPLE=1": "GENERIC=1");
4566 cpp_define (r
, gimple
? "GENERIC=0": "GIMPLE=0");
4568 /* Pre-seed operators. */
4569 operators
= new hash_table
<id_base
> (1024);
4570 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
4571 add_operator (SYM, # SYM, # TYPE, NARGS);
4572 #define END_OF_BASE_TREE_CODES
4574 add_operator (CONVERT0
, "CONVERT0", "tcc_unary", 1);
4575 add_operator (CONVERT1
, "CONVERT1", "tcc_unary", 1);
4576 add_operator (CONVERT2
, "CONVERT2", "tcc_unary", 1);
4577 add_operator (VIEW_CONVERT0
, "VIEW_CONVERT0", "tcc_unary", 1);
4578 add_operator (VIEW_CONVERT1
, "VIEW_CONVERT1", "tcc_unary", 1);
4579 add_operator (VIEW_CONVERT2
, "VIEW_CONVERT2", "tcc_unary", 1);
4580 #undef END_OF_BASE_TREE_CODES
4583 /* Pre-seed builtin functions.
4584 ??? Cannot use N (name) as that is targetm.emultls.get_address
4585 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
4586 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
4587 add_builtin (ENUM, # ENUM);
4588 #include "builtins.def"
4595 write_header (stdout
, "gimple-match-head.c");
4597 write_header (stdout
, "generic-match-head.c");
4599 /* Go over all predicates defined with patterns and perform
4600 lowering and code generation. */
4601 for (unsigned i
= 0; i
< p
.user_predicates
.length (); ++i
)
4603 predicate_id
*pred
= p
.user_predicates
[i
];
4604 lower (pred
->matchers
, gimple
);
4607 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4608 print_matches (pred
->matchers
[i
]);
4611 for (unsigned i
= 0; i
< pred
->matchers
.length (); ++i
)
4612 dt
.insert (pred
->matchers
[i
], i
);
4617 write_predicate (stdout
, pred
, dt
, gimple
);
4620 /* Lower the main simplifiers and generate code for them. */
4621 lower (p
.simplifiers
, gimple
);
4624 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4625 print_matches (p
.simplifiers
[i
]);
4628 for (unsigned i
= 0; i
< p
.simplifiers
.length (); ++i
)
4629 dt
.insert (p
.simplifiers
[i
], i
);
4634 dt
.gen (stdout
, gimple
);
4637 cpp_finish (r
, NULL
);