1 /* Generate pattern matching and transform code shared between
2 GENERIC and GIMPLE folding code from match-and-simplify description.
3
4 Copyright (C) 2014-2018 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
7
8 This file is part of GCC.
9
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
13 version.
14
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
18 for more details.
19
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/>. */
23
24 #include "bconfig.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include <cpplib.h>
28 #include "errors.h"
29 #include "hash-table.h"
30 #include "hash-set.h"
31 #include "is-a.h"
32
33
34 /* Stubs for GGC referenced through instantiations triggered by hash-map. */
ggc_internal_cleared_alloc(size_t,void (*)(void *),size_t,size_t MEM_STAT_DECL)35 void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL)
37 {
38 return NULL;
39 }
ggc_free(void *)40 void ggc_free (void *)
41 {
42 }
43
44
45 /* Global state. */
46
47 /* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
48 unsigned verbose;
49
50
51 /* libccp helpers. */
52
53 static struct line_maps *line_table;
54
55 /* The rich_location class within libcpp requires a way to expand
56 source_location instances, and relies on the client code
57 providing a symbol named
58 linemap_client_expand_location_to_spelling_point
59 to do this.
60
61 This is the implementation for genmatch. */
62
63 expanded_location
linemap_client_expand_location_to_spelling_point(source_location loc,enum location_aspect)64 linemap_client_expand_location_to_spelling_point (source_location loc,
65 enum location_aspect)
66 {
67 const struct line_map_ordinary *map;
68 loc = linemap_resolve_location (line_table, loc, LRK_SPELLING_LOCATION, &map);
69 return linemap_expand_location (line_table, map, loc);
70 }
71
72 static bool
73 #if GCC_VERSION >= 4001
74 __attribute__((format (printf, 5, 0)))
75 #endif
error_cb(cpp_reader *,int errtype,int,rich_location * richloc,const char * msg,va_list * ap)76 error_cb (cpp_reader *, int errtype, int, rich_location *richloc,
77 const char *msg, va_list *ap)
78 {
79 const line_map_ordinary *map;
80 source_location location = richloc->get_loc ();
81 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
82 expanded_location loc = linemap_expand_location (line_table, map, location);
83 fprintf (stderr, "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
84 (errtype == CPP_DL_WARNING) ? "warning" : "error");
85 vfprintf (stderr, msg, *ap);
86 fprintf (stderr, "\n");
87 FILE *f = fopen (loc.file, "r");
88 if (f)
89 {
90 char buf[128];
91 while (loc.line > 0)
92 {
93 if (!fgets (buf, 128, f))
94 goto notfound;
95 if (buf[strlen (buf) - 1] != '\n')
96 {
97 if (loc.line > 1)
98 loc.line++;
99 }
100 loc.line--;
101 }
102 fprintf (stderr, "%s", buf);
103 for (int i = 0; i < loc.column - 1; ++i)
104 fputc (' ', stderr);
105 fputc ('^', stderr);
106 fputc ('\n', stderr);
107 notfound:
108 fclose (f);
109 }
110
111 if (errtype == CPP_DL_FATAL)
112 exit (1);
113 return false;
114 }
115
116 static void
117 #if GCC_VERSION >= 4001
118 __attribute__((format (printf, 2, 3)))
119 #endif
fatal_at(const cpp_token * tk,const char * msg,...)120 fatal_at (const cpp_token *tk, const char *msg, ...)
121 {
122 rich_location richloc (line_table, tk->src_loc);
123 va_list ap;
124 va_start (ap, msg);
125 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
126 va_end (ap);
127 }
128
129 static void
130 #if GCC_VERSION >= 4001
131 __attribute__((format (printf, 2, 3)))
132 #endif
fatal_at(source_location loc,const char * msg,...)133 fatal_at (source_location loc, const char *msg, ...)
134 {
135 rich_location richloc (line_table, loc);
136 va_list ap;
137 va_start (ap, msg);
138 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
139 va_end (ap);
140 }
141
142 static void
143 #if GCC_VERSION >= 4001
144 __attribute__((format (printf, 2, 3)))
145 #endif
warning_at(const cpp_token * tk,const char * msg,...)146 warning_at (const cpp_token *tk, const char *msg, ...)
147 {
148 rich_location richloc (line_table, tk->src_loc);
149 va_list ap;
150 va_start (ap, msg);
151 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
152 va_end (ap);
153 }
154
155 static void
156 #if GCC_VERSION >= 4001
157 __attribute__((format (printf, 2, 3)))
158 #endif
warning_at(source_location loc,const char * msg,...)159 warning_at (source_location loc, const char *msg, ...)
160 {
161 rich_location richloc (line_table, loc);
162 va_list ap;
163 va_start (ap, msg);
164 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
165 va_end (ap);
166 }
167
168 /* Like fprintf, but print INDENT spaces at the beginning. */
169
170 static void
171 #if GCC_VERSION >= 4001
172 __attribute__((format (printf, 3, 4)))
173 #endif
fprintf_indent(FILE * f,unsigned int indent,const char * format,...)174 fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
175 {
176 va_list ap;
177 for (; indent >= 8; indent -= 8)
178 fputc ('\t', f);
179 fprintf (f, "%*s", indent, "");
180 va_start (ap, format);
181 vfprintf (f, format, ap);
182 va_end (ap);
183 }
184
185 static void
186 output_line_directive (FILE *f, source_location location,
187 bool dumpfile = false)
188 {
189 const line_map_ordinary *map;
190 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
191 expanded_location loc = linemap_expand_location (line_table, map, location);
192 if (dumpfile)
193 {
194 /* When writing to a dumpfile only dump the filename. */
195 const char *file = strrchr (loc.file, DIR_SEPARATOR);
196 #if defined(DIR_SEPARATOR_2)
197 const char *pos2 = strrchr (loc.file, DIR_SEPARATOR_2);
198 if (pos2 && (!file || (pos2 > file)))
199 file = pos2;
200 #endif
201 if (!file)
202 file = loc.file;
203 else
204 ++file;
205 fprintf (f, "%s:%d", file, loc.line);
206 }
207 else
208 /* Other gen programs really output line directives here, at least for
209 development it's right now more convenient to have line information
210 from the generated file. Still keep the directives as comment for now
211 to easily back-point to the meta-description. */
212 fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
213 }
214
215
216 /* Pull in tree codes and builtin function codes from their
217 definition files. */
218
219 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
220 enum tree_code {
221 #include "tree.def"
222 CONVERT0,
223 CONVERT1,
224 CONVERT2,
225 VIEW_CONVERT0,
226 VIEW_CONVERT1,
227 VIEW_CONVERT2,
228 MAX_TREE_CODES
229 };
230 #undef DEFTREECODE
231
232 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
233 enum built_in_function {
234 #include "builtins.def"
235 END_BUILTINS
236 };
237
238 #define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239 enum internal_fn {
240 #include "internal-fn.def"
241 IFN_LAST
242 };
243
244 /* Return true if CODE represents a commutative tree code. Otherwise
245 return false. */
246 bool
commutative_tree_code(enum tree_code code)247 commutative_tree_code (enum tree_code code)
248 {
249 switch (code)
250 {
251 case PLUS_EXPR:
252 case MULT_EXPR:
253 case MULT_HIGHPART_EXPR:
254 case MIN_EXPR:
255 case MAX_EXPR:
256 case BIT_IOR_EXPR:
257 case BIT_XOR_EXPR:
258 case BIT_AND_EXPR:
259 case NE_EXPR:
260 case EQ_EXPR:
261 case UNORDERED_EXPR:
262 case ORDERED_EXPR:
263 case UNEQ_EXPR:
264 case LTGT_EXPR:
265 case TRUTH_AND_EXPR:
266 case TRUTH_XOR_EXPR:
267 case TRUTH_OR_EXPR:
268 case WIDEN_MULT_EXPR:
269 case VEC_WIDEN_MULT_HI_EXPR:
270 case VEC_WIDEN_MULT_LO_EXPR:
271 case VEC_WIDEN_MULT_EVEN_EXPR:
272 case VEC_WIDEN_MULT_ODD_EXPR:
273 return true;
274
275 default:
276 break;
277 }
278 return false;
279 }
280
281 /* Return true if CODE represents a ternary tree code for which the
282 first two operands are commutative. Otherwise return false. */
283 bool
commutative_ternary_tree_code(enum tree_code code)284 commutative_ternary_tree_code (enum tree_code code)
285 {
286 switch (code)
287 {
288 case WIDEN_MULT_PLUS_EXPR:
289 case WIDEN_MULT_MINUS_EXPR:
290 case DOT_PROD_EXPR:
291 case FMA_EXPR:
292 return true;
293
294 default:
295 break;
296 }
297 return false;
298 }
299
300 /* Return true if CODE is a comparison. */
301
302 bool
comparison_code_p(enum tree_code code)303 comparison_code_p (enum tree_code code)
304 {
305 switch (code)
306 {
307 case EQ_EXPR:
308 case NE_EXPR:
309 case ORDERED_EXPR:
310 case UNORDERED_EXPR:
311 case LTGT_EXPR:
312 case UNEQ_EXPR:
313 case GT_EXPR:
314 case GE_EXPR:
315 case LT_EXPR:
316 case LE_EXPR:
317 case UNGT_EXPR:
318 case UNGE_EXPR:
319 case UNLT_EXPR:
320 case UNLE_EXPR:
321 return true;
322
323 default:
324 break;
325 }
326 return false;
327 }
328
329
330 /* Base class for all identifiers the parser knows. */
331
332 struct id_base : nofree_ptr_hash<id_base>
333 {
334 enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
335
336 id_base (id_kind, const char *, int = -1);
337
338 hashval_t hashval;
339 int nargs;
340 const char *id;
341
342 /* hash_table support. */
343 static inline hashval_t hash (const id_base *);
344 static inline int equal (const id_base *, const id_base *);
345 };
346
347 inline hashval_t
hash(const id_base * op)348 id_base::hash (const id_base *op)
349 {
350 return op->hashval;
351 }
352
353 inline int
equal(const id_base * op1,const id_base * op2)354 id_base::equal (const id_base *op1,
355 const id_base *op2)
356 {
357 return (op1->hashval == op2->hashval
358 && strcmp (op1->id, op2->id) == 0);
359 }
360
361 /* The special id "null", which matches nothing. */
362 static id_base *null_id;
363
364 /* Hashtable of known pattern operators. This is pre-seeded from
365 all known tree codes and all known builtin function ids. */
366 static hash_table<id_base> *operators;
367
id_base(id_kind kind_,const char * id_,int nargs_)368 id_base::id_base (id_kind kind_, const char *id_, int nargs_)
369 {
370 kind = kind_;
371 id = id_;
372 nargs = nargs_;
373 hashval = htab_hash_string (id);
374 }
375
376 /* Identifier that maps to a tree code. */
377
378 struct operator_id : public id_base
379 {
operator_idoperator_id380 operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
381 const char *tcc_)
382 : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
383 enum tree_code code;
384 const char *tcc;
385 };
386
387 /* Identifier that maps to a builtin or internal function code. */
388
389 struct fn_id : public id_base
390 {
fn_idfn_id391 fn_id (enum built_in_function fn_, const char *id_)
392 : id_base (id_base::FN, id_), fn (fn_) {}
fn_idfn_id393 fn_id (enum internal_fn fn_, const char *id_)
394 : id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
395 unsigned int fn;
396 };
397
398 struct simplify;
399
400 /* Identifier that maps to a user-defined predicate. */
401
402 struct predicate_id : public id_base
403 {
predicate_idpredicate_id404 predicate_id (const char *id_)
405 : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
406 vec<simplify *> matchers;
407 };
408
409 /* Identifier that maps to a operator defined by a 'for' directive. */
410
411 struct user_id : public id_base
412 {
413 user_id (const char *id_, bool is_oper_list_ = false)
id_baseuser_id414 : id_base (id_base::USER, id_), substitutes (vNULL),
415 used (false), is_oper_list (is_oper_list_) {}
416 vec<id_base *> substitutes;
417 bool used;
418 bool is_oper_list;
419 };
420
421 template<>
422 template<>
423 inline bool
test(id_base * id)424 is_a_helper <fn_id *>::test (id_base *id)
425 {
426 return id->kind == id_base::FN;
427 }
428
429 template<>
430 template<>
431 inline bool
test(id_base * id)432 is_a_helper <operator_id *>::test (id_base *id)
433 {
434 return id->kind == id_base::CODE;
435 }
436
437 template<>
438 template<>
439 inline bool
test(id_base * id)440 is_a_helper <predicate_id *>::test (id_base *id)
441 {
442 return id->kind == id_base::PREDICATE;
443 }
444
445 template<>
446 template<>
447 inline bool
test(id_base * id)448 is_a_helper <user_id *>::test (id_base *id)
449 {
450 return id->kind == id_base::USER;
451 }
452
453 /* Add a predicate identifier to the hash. */
454
455 static predicate_id *
add_predicate(const char * id)456 add_predicate (const char *id)
457 {
458 predicate_id *p = new predicate_id (id);
459 id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
460 if (*slot)
461 fatal ("duplicate id definition");
462 *slot = p;
463 return p;
464 }
465
466 /* Add a tree code identifier to the hash. */
467
468 static void
add_operator(enum tree_code code,const char * id,const char * tcc,unsigned nargs)469 add_operator (enum tree_code code, const char *id,
470 const char *tcc, unsigned nargs)
471 {
472 if (strcmp (tcc, "tcc_unary") != 0
473 && strcmp (tcc, "tcc_binary") != 0
474 && strcmp (tcc, "tcc_comparison") != 0
475 && strcmp (tcc, "tcc_expression") != 0
476 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
477 && strcmp (tcc, "tcc_reference") != 0
478 /* To have INTEGER_CST and friends as "predicate operators". */
479 && strcmp (tcc, "tcc_constant") != 0
480 /* And allow CONSTRUCTOR for vector initializers. */
481 && !(code == CONSTRUCTOR)
482 /* Allow SSA_NAME as predicate operator. */
483 && !(code == SSA_NAME))
484 return;
485 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
486 if (code == ADDR_EXPR)
487 nargs = 0;
488 operator_id *op = new operator_id (code, id, nargs, tcc);
489 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
490 if (*slot)
491 fatal ("duplicate id definition");
492 *slot = op;
493 }
494
495 /* Add a built-in or internal function identifier to the hash. ID is
496 the name of its CFN_* enumeration value. */
497
498 template <typename T>
499 static void
add_function(T code,const char * id)500 add_function (T code, const char *id)
501 {
502 fn_id *fn = new fn_id (code, id);
503 id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
504 if (*slot)
505 fatal ("duplicate id definition");
506 *slot = fn;
507 }
508
509 /* Helper for easy comparing ID with tree code CODE. */
510
511 static bool
512 operator==(id_base &id, enum tree_code code)
513 {
514 if (operator_id *oid = dyn_cast <operator_id *> (&id))
515 return oid->code == code;
516 return false;
517 }
518
519 /* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
520
521 id_base *
522 get_operator (const char *id, bool allow_null = false)
523 {
524 if (allow_null && strcmp (id, "null") == 0)
525 return null_id;
526
527 id_base tem (id_base::CODE, id);
528
529 id_base *op = operators->find_with_hash (&tem, tem.hashval);
530 if (op)
531 {
532 /* If this is a user-defined identifier track whether it was used. */
533 if (user_id *uid = dyn_cast<user_id *> (op))
534 uid->used = true;
535 return op;
536 }
537
538 char *id2;
539 bool all_upper = true;
540 bool all_lower = true;
541 for (unsigned int i = 0; id[i]; ++i)
542 if (ISUPPER (id[i]))
543 all_lower = false;
544 else if (ISLOWER (id[i]))
545 all_upper = false;
546 if (all_lower)
547 {
548 /* Try in caps with _EXPR appended. */
549 id2 = ACONCAT ((id, "_EXPR", NULL));
550 for (unsigned int i = 0; id2[i]; ++i)
551 id2[i] = TOUPPER (id2[i]);
552 }
553 else if (all_upper && strncmp (id, "IFN_", 4) == 0)
554 /* Try CFN_ instead of IFN_. */
555 id2 = ACONCAT (("CFN_", id + 4, NULL));
556 else if (all_upper && strncmp (id, "BUILT_IN_", 9) == 0)
557 /* Try prepending CFN_. */
558 id2 = ACONCAT (("CFN_", id, NULL));
559 else
560 return NULL;
561
562 new (&tem) id_base (id_base::CODE, id2);
563 return operators->find_with_hash (&tem, tem.hashval);
564 }
565
566 /* Return the comparison operators that results if the operands are
567 swapped. This is safe for floating-point. */
568
569 id_base *
swap_tree_comparison(operator_id * p)570 swap_tree_comparison (operator_id *p)
571 {
572 switch (p->code)
573 {
574 case EQ_EXPR:
575 case NE_EXPR:
576 case ORDERED_EXPR:
577 case UNORDERED_EXPR:
578 case LTGT_EXPR:
579 case UNEQ_EXPR:
580 return p;
581 case GT_EXPR:
582 return get_operator ("LT_EXPR");
583 case GE_EXPR:
584 return get_operator ("LE_EXPR");
585 case LT_EXPR:
586 return get_operator ("GT_EXPR");
587 case LE_EXPR:
588 return get_operator ("GE_EXPR");
589 case UNGT_EXPR:
590 return get_operator ("UNLT_EXPR");
591 case UNGE_EXPR:
592 return get_operator ("UNLE_EXPR");
593 case UNLT_EXPR:
594 return get_operator ("UNGT_EXPR");
595 case UNLE_EXPR:
596 return get_operator ("UNGE_EXPR");
597 default:
598 gcc_unreachable ();
599 }
600 }
601
602 typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
603
604
605 /* The AST produced by parsing of the pattern definitions. */
606
607 struct dt_operand;
608 struct capture_info;
609
610 /* The base class for operands. */
611
612 struct operand {
613 enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
operandoperand614 operand (enum op_type type_, source_location loc_)
615 : type (type_), location (loc_) {}
616 enum op_type type;
617 source_location location;
618 virtual void gen_transform (FILE *, int, const char *, bool, int,
619 const char *, capture_info *,
620 dt_operand ** = 0,
621 int = 0)
622 { gcc_unreachable (); }
623 };
624
625 /* A predicate operand. Predicates are leafs in the AST. */
626
627 struct predicate : public operand
628 {
predicatepredicate629 predicate (predicate_id *p_, source_location loc)
630 : operand (OP_PREDICATE, loc), p (p_) {}
631 predicate_id *p;
632 };
633
634 /* An operand that constitutes an expression. Expressions include
635 function calls and user-defined predicate invocations. */
636
637 struct expr : public operand
638 {
639 expr (id_base *operation_, source_location loc, bool is_commutative_ = false)
operandexpr640 : operand (OP_EXPR, loc), operation (operation_),
641 ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
642 is_generic (false), force_single_use (false) {}
exprexpr643 expr (expr *e)
644 : operand (OP_EXPR, e->location), operation (e->operation),
645 ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
646 is_generic (e->is_generic), force_single_use (e->force_single_use) {}
append_opexpr647 void append_op (operand *op) { ops.safe_push (op); }
648 /* The operator and its operands. */
649 id_base *operation;
650 vec<operand *> ops;
651 /* An explicitely specified type - used exclusively for conversions. */
652 const char *expr_type;
653 /* Whether the operation is to be applied commutatively. This is
654 later lowered to two separate patterns. */
655 bool is_commutative;
656 /* Whether the expression is expected to be in GENERIC form. */
657 bool is_generic;
658 /* Whether pushing any stmt to the sequence should be conditional
659 on this expression having a single-use. */
660 bool force_single_use;
661 virtual void gen_transform (FILE *f, int, const char *, bool, int,
662 const char *, capture_info *,
663 dt_operand ** = 0, int = 0);
664 };
665
666 /* An operator that is represented by native C code. This is always
667 a leaf operand in the AST. This class is also used to represent
668 the code to be generated for 'if' and 'with' expressions. */
669
670 struct c_expr : public operand
671 {
672 /* A mapping of an identifier and its replacement. Used to apply
673 'for' lowering. */
674 struct id_tab {
675 const char *id;
676 const char *oper;
id_tabc_expr::id_tab677 id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
678 };
679
c_exprc_expr680 c_expr (cpp_reader *r_, source_location loc,
681 vec<cpp_token> code_, unsigned nr_stmts_,
682 vec<id_tab> ids_, cid_map_t *capture_ids_)
683 : operand (OP_C_EXPR, loc), r (r_), code (code_),
684 capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
685 /* cpplib tokens and state to transform this back to source. */
686 cpp_reader *r;
687 vec<cpp_token> code;
688 cid_map_t *capture_ids;
689 /* The number of statements parsed (well, the number of ';'s). */
690 unsigned nr_stmts;
691 /* The identifier replacement vector. */
692 vec<id_tab> ids;
693 virtual void gen_transform (FILE *f, int, const char *, bool, int,
694 const char *, capture_info *,
695 dt_operand ** = 0, int = 0);
696 };
697
698 /* A wrapper around another operand that captures its value. */
699
700 struct capture : public operand
701 {
capturecapture702 capture (source_location loc, unsigned where_, operand *what_, bool value_)
703 : operand (OP_CAPTURE, loc), where (where_), value_match (value_),
704 what (what_) {}
705 /* Identifier index for the value. */
706 unsigned where;
707 /* Whether in a match of two operands the compare should be for
708 equal values rather than equal atoms (boils down to a type
709 check or not). */
710 bool value_match;
711 /* The captured value. */
712 operand *what;
713 virtual void gen_transform (FILE *f, int, const char *, bool, int,
714 const char *, capture_info *,
715 dt_operand ** = 0, int = 0);
716 };
717
718 /* if expression. */
719
720 struct if_expr : public operand
721 {
if_exprif_expr722 if_expr (source_location loc)
723 : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
724 c_expr *cond;
725 operand *trueexpr;
726 operand *falseexpr;
727 };
728
729 /* with expression. */
730
731 struct with_expr : public operand
732 {
with_exprwith_expr733 with_expr (source_location loc)
734 : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
735 c_expr *with;
736 operand *subexpr;
737 };
738
739 template<>
740 template<>
741 inline bool
test(operand * op)742 is_a_helper <capture *>::test (operand *op)
743 {
744 return op->type == operand::OP_CAPTURE;
745 }
746
747 template<>
748 template<>
749 inline bool
test(operand * op)750 is_a_helper <predicate *>::test (operand *op)
751 {
752 return op->type == operand::OP_PREDICATE;
753 }
754
755 template<>
756 template<>
757 inline bool
test(operand * op)758 is_a_helper <c_expr *>::test (operand *op)
759 {
760 return op->type == operand::OP_C_EXPR;
761 }
762
763 template<>
764 template<>
765 inline bool
test(operand * op)766 is_a_helper <expr *>::test (operand *op)
767 {
768 return op->type == operand::OP_EXPR;
769 }
770
771 template<>
772 template<>
773 inline bool
test(operand * op)774 is_a_helper <if_expr *>::test (operand *op)
775 {
776 return op->type == operand::OP_IF;
777 }
778
779 template<>
780 template<>
781 inline bool
test(operand * op)782 is_a_helper <with_expr *>::test (operand *op)
783 {
784 return op->type == operand::OP_WITH;
785 }
786
787 /* The main class of a pattern and its transform. This is used to
788 represent both (simplify ...) and (match ...) kinds. The AST
789 duplicates all outer 'if' and 'for' expressions here so each
790 simplify can exist in isolation. */
791
792 struct simplify
793 {
794 enum simplify_kind { SIMPLIFY, MATCH };
795
simplifysimplify796 simplify (simplify_kind kind_, unsigned id_, operand *match_,
797 operand *result_, vec<vec<user_id *> > for_vec_,
798 cid_map_t *capture_ids_)
799 : kind (kind_), id (id_), match (match_), result (result_),
800 for_vec (for_vec_), for_subst_vec (vNULL),
801 capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
802
803 simplify_kind kind;
804 /* ID. This is kept to easily associate related simplifies expanded
805 from the same original one. */
806 unsigned id;
807 /* The expression that is matched against the GENERIC or GIMPLE IL. */
808 operand *match;
809 /* For a (simplify ...) an expression with ifs and withs with the expression
810 produced when the pattern applies in the leafs.
811 For a (match ...) the leafs are either empty if it is a simple predicate
812 or the single expression specifying the matched operands. */
813 struct operand *result;
814 /* Collected 'for' expression operators that have to be replaced
815 in the lowering phase. */
816 vec<vec<user_id *> > for_vec;
817 vec<std::pair<user_id *, id_base *> > for_subst_vec;
818 /* A map of capture identifiers to indexes. */
819 cid_map_t *capture_ids;
820 int capture_max;
821 };
822
823 /* Debugging routines for dumping the AST. */
824
825 DEBUG_FUNCTION void
826 print_operand (operand *o, FILE *f = stderr, bool flattened = false)
827 {
828 if (capture *c = dyn_cast<capture *> (o))
829 {
830 if (c->what && flattened == false)
831 print_operand (c->what, f, flattened);
832 fprintf (f, "@%u", c->where);
833 }
834
835 else if (predicate *p = dyn_cast<predicate *> (o))
836 fprintf (f, "%s", p->p->id);
837
838 else if (is_a<c_expr *> (o))
839 fprintf (f, "c_expr");
840
841 else if (expr *e = dyn_cast<expr *> (o))
842 {
843 if (e->ops.length () == 0)
844 fprintf (f, "%s", e->operation->id);
845 else
846 {
847 fprintf (f, "(%s", e->operation->id);
848
849 if (flattened == false)
850 {
851 for (unsigned i = 0; i < e->ops.length (); ++i)
852 {
853 putc (' ', f);
854 print_operand (e->ops[i], f, flattened);
855 }
856 }
857 putc (')', f);
858 }
859 }
860
861 else
862 gcc_unreachable ();
863 }
864
865 DEBUG_FUNCTION void
866 print_matches (struct simplify *s, FILE *f = stderr)
867 {
868 fprintf (f, "for expression: ");
869 print_operand (s->match, f);
870 putc ('\n', f);
871 }
872
873
874 /* AST lowering. */
875
876 /* Lowering of commutative operators. */
877
878 static void
cartesian_product(const vec<vec<operand * >> & ops_vector,vec<vec<operand * >> & result,vec<operand * > & v,unsigned n)879 cartesian_product (const vec< vec<operand *> >& ops_vector,
880 vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
881 {
882 if (n == ops_vector.length ())
883 {
884 vec<operand *> xv = v.copy ();
885 result.safe_push (xv);
886 return;
887 }
888
889 for (unsigned i = 0; i < ops_vector[n].length (); ++i)
890 {
891 v[n] = ops_vector[n][i];
892 cartesian_product (ops_vector, result, v, n + 1);
893 }
894 }
895
896 /* Lower OP to two operands in case it is marked as commutative. */
897
898 static vec<operand *>
commutate(operand * op,vec<vec<user_id * >> & for_vec)899 commutate (operand *op, vec<vec<user_id *> > &for_vec)
900 {
901 vec<operand *> ret = vNULL;
902
903 if (capture *c = dyn_cast <capture *> (op))
904 {
905 if (!c->what)
906 {
907 ret.safe_push (op);
908 return ret;
909 }
910 vec<operand *> v = commutate (c->what, for_vec);
911 for (unsigned i = 0; i < v.length (); ++i)
912 {
913 capture *nc = new capture (c->location, c->where, v[i],
914 c->value_match);
915 ret.safe_push (nc);
916 }
917 return ret;
918 }
919
920 expr *e = dyn_cast <expr *> (op);
921 if (!e || e->ops.length () == 0)
922 {
923 ret.safe_push (op);
924 return ret;
925 }
926
927 vec< vec<operand *> > ops_vector = vNULL;
928 for (unsigned i = 0; i < e->ops.length (); ++i)
929 ops_vector.safe_push (commutate (e->ops[i], for_vec));
930
931 auto_vec< vec<operand *> > result;
932 auto_vec<operand *> v (e->ops.length ());
933 v.quick_grow_cleared (e->ops.length ());
934 cartesian_product (ops_vector, result, v, 0);
935
936
937 for (unsigned i = 0; i < result.length (); ++i)
938 {
939 expr *ne = new expr (e);
940 ne->is_commutative = false;
941 for (unsigned j = 0; j < result[i].length (); ++j)
942 ne->append_op (result[i][j]);
943 ret.safe_push (ne);
944 }
945
946 if (!e->is_commutative)
947 return ret;
948
949 for (unsigned i = 0; i < result.length (); ++i)
950 {
951 expr *ne = new expr (e);
952 if (operator_id *p = dyn_cast <operator_id *> (ne->operation))
953 {
954 if (comparison_code_p (p->code))
955 ne->operation = swap_tree_comparison (p);
956 }
957 else if (user_id *p = dyn_cast <user_id *> (ne->operation))
958 {
959 bool found_compare = false;
960 for (unsigned j = 0; j < p->substitutes.length (); ++j)
961 if (operator_id *q = dyn_cast <operator_id *> (p->substitutes[j]))
962 {
963 if (comparison_code_p (q->code)
964 && swap_tree_comparison (q) != q)
965 {
966 found_compare = true;
967 break;
968 }
969 }
970 if (found_compare)
971 {
972 user_id *newop = new user_id ("<internal>");
973 for (unsigned j = 0; j < p->substitutes.length (); ++j)
974 {
975 id_base *subst = p->substitutes[j];
976 if (operator_id *q = dyn_cast <operator_id *> (subst))
977 {
978 if (comparison_code_p (q->code))
979 subst = swap_tree_comparison (q);
980 }
981 newop->substitutes.safe_push (subst);
982 }
983 ne->operation = newop;
984 /* Search for 'p' inside the for vector and push 'newop'
985 to the same level. */
986 for (unsigned j = 0; newop && j < for_vec.length (); ++j)
987 for (unsigned k = 0; k < for_vec[j].length (); ++k)
988 if (for_vec[j][k] == p)
989 {
990 for_vec[j].safe_push (newop);
991 newop = NULL;
992 break;
993 }
994 }
995 }
996 ne->is_commutative = false;
997 // result[i].length () is 2 since e->operation is binary
998 for (unsigned j = result[i].length (); j; --j)
999 ne->append_op (result[i][j-1]);
1000 ret.safe_push (ne);
1001 }
1002
1003 return ret;
1004 }
1005
1006 /* Lower operations marked as commutative in the AST of S and push
1007 the resulting patterns to SIMPLIFIERS. */
1008
1009 static void
lower_commutative(simplify * s,vec<simplify * > & simplifiers)1010 lower_commutative (simplify *s, vec<simplify *>& simplifiers)
1011 {
1012 vec<operand *> matchers = commutate (s->match, s->for_vec);
1013 for (unsigned i = 0; i < matchers.length (); ++i)
1014 {
1015 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1016 s->for_vec, s->capture_ids);
1017 simplifiers.safe_push (ns);
1018 }
1019 }
1020
1021 /* Strip conditional conversios using operator OPER from O and its
1022 children if STRIP, else replace them with an unconditional convert. */
1023
1024 operand *
lower_opt_convert(operand * o,enum tree_code oper,enum tree_code to_oper,bool strip)1025 lower_opt_convert (operand *o, enum tree_code oper,
1026 enum tree_code to_oper, bool strip)
1027 {
1028 if (capture *c = dyn_cast<capture *> (o))
1029 {
1030 if (c->what)
1031 return new capture (c->location, c->where,
1032 lower_opt_convert (c->what, oper, to_oper, strip),
1033 c->value_match);
1034 else
1035 return c;
1036 }
1037
1038 expr *e = dyn_cast<expr *> (o);
1039 if (!e)
1040 return o;
1041
1042 if (*e->operation == oper)
1043 {
1044 if (strip)
1045 return lower_opt_convert (e->ops[0], oper, to_oper, strip);
1046
1047 expr *ne = new expr (e);
1048 ne->operation = (to_oper == CONVERT_EXPR
1049 ? get_operator ("CONVERT_EXPR")
1050 : get_operator ("VIEW_CONVERT_EXPR"));
1051 ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
1052 return ne;
1053 }
1054
1055 expr *ne = new expr (e);
1056 for (unsigned i = 0; i < e->ops.length (); ++i)
1057 ne->append_op (lower_opt_convert (e->ops[i], oper, to_oper, strip));
1058
1059 return ne;
1060 }
1061
1062 /* Determine whether O or its children uses the conditional conversion
1063 operator OPER. */
1064
1065 static bool
has_opt_convert(operand * o,enum tree_code oper)1066 has_opt_convert (operand *o, enum tree_code oper)
1067 {
1068 if (capture *c = dyn_cast<capture *> (o))
1069 {
1070 if (c->what)
1071 return has_opt_convert (c->what, oper);
1072 else
1073 return false;
1074 }
1075
1076 expr *e = dyn_cast<expr *> (o);
1077 if (!e)
1078 return false;
1079
1080 if (*e->operation == oper)
1081 return true;
1082
1083 for (unsigned i = 0; i < e->ops.length (); ++i)
1084 if (has_opt_convert (e->ops[i], oper))
1085 return true;
1086
1087 return false;
1088 }
1089
1090 /* Lower conditional convert operators in O, expanding it to a vector
1091 if required. */
1092
1093 static vec<operand *>
lower_opt_convert(operand * o)1094 lower_opt_convert (operand *o)
1095 {
1096 vec<operand *> v1 = vNULL, v2;
1097
1098 v1.safe_push (o);
1099
1100 enum tree_code opers[]
1101 = { CONVERT0, CONVERT_EXPR,
1102 CONVERT1, CONVERT_EXPR,
1103 CONVERT2, CONVERT_EXPR,
1104 VIEW_CONVERT0, VIEW_CONVERT_EXPR,
1105 VIEW_CONVERT1, VIEW_CONVERT_EXPR,
1106 VIEW_CONVERT2, VIEW_CONVERT_EXPR };
1107
1108 /* Conditional converts are lowered to a pattern with the
1109 conversion and one without. The three different conditional
1110 convert codes are lowered separately. */
1111
1112 for (unsigned i = 0; i < sizeof (opers) / sizeof (enum tree_code); i += 2)
1113 {
1114 v2 = vNULL;
1115 for (unsigned j = 0; j < v1.length (); ++j)
1116 if (has_opt_convert (v1[j], opers[i]))
1117 {
1118 v2.safe_push (lower_opt_convert (v1[j],
1119 opers[i], opers[i+1], false));
1120 v2.safe_push (lower_opt_convert (v1[j],
1121 opers[i], opers[i+1], true));
1122 }
1123
1124 if (v2 != vNULL)
1125 {
1126 v1 = vNULL;
1127 for (unsigned j = 0; j < v2.length (); ++j)
1128 v1.safe_push (v2[j]);
1129 }
1130 }
1131
1132 return v1;
1133 }
1134
1135 /* Lower conditional convert operators in the AST of S and push
1136 the resulting multiple patterns to SIMPLIFIERS. */
1137
1138 static void
lower_opt_convert(simplify * s,vec<simplify * > & simplifiers)1139 lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
1140 {
1141 vec<operand *> matchers = lower_opt_convert (s->match);
1142 for (unsigned i = 0; i < matchers.length (); ++i)
1143 {
1144 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1145 s->for_vec, s->capture_ids);
1146 simplifiers.safe_push (ns);
1147 }
1148 }
1149
1150 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1151 GENERIC and a GIMPLE variant. */
1152
1153 static vec<operand *>
lower_cond(operand * o)1154 lower_cond (operand *o)
1155 {
1156 vec<operand *> ro = vNULL;
1157
1158 if (capture *c = dyn_cast<capture *> (o))
1159 {
1160 if (c->what)
1161 {
1162 vec<operand *> lop = vNULL;
1163 lop = lower_cond (c->what);
1164
1165 for (unsigned i = 0; i < lop.length (); ++i)
1166 ro.safe_push (new capture (c->location, c->where, lop[i],
1167 c->value_match));
1168 return ro;
1169 }
1170 }
1171
1172 expr *e = dyn_cast<expr *> (o);
1173 if (!e || e->ops.length () == 0)
1174 {
1175 ro.safe_push (o);
1176 return ro;
1177 }
1178
1179 vec< vec<operand *> > ops_vector = vNULL;
1180 for (unsigned i = 0; i < e->ops.length (); ++i)
1181 ops_vector.safe_push (lower_cond (e->ops[i]));
1182
1183 auto_vec< vec<operand *> > result;
1184 auto_vec<operand *> v (e->ops.length ());
1185 v.quick_grow_cleared (e->ops.length ());
1186 cartesian_product (ops_vector, result, v, 0);
1187
1188 for (unsigned i = 0; i < result.length (); ++i)
1189 {
1190 expr *ne = new expr (e);
1191 for (unsigned j = 0; j < result[i].length (); ++j)
1192 ne->append_op (result[i][j]);
1193 ro.safe_push (ne);
1194 /* If this is a COND with a captured expression or an
1195 expression with two operands then also match a GENERIC
1196 form on the compare. */
1197 if ((*e->operation == COND_EXPR
1198 || *e->operation == VEC_COND_EXPR)
1199 && ((is_a <capture *> (e->ops[0])
1200 && as_a <capture *> (e->ops[0])->what
1201 && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1202 && as_a <expr *>
1203 (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1204 || (is_a <expr *> (e->ops[0])
1205 && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1206 {
1207 expr *ne = new expr (e);
1208 for (unsigned j = 0; j < result[i].length (); ++j)
1209 ne->append_op (result[i][j]);
1210 if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1211 {
1212 expr *ocmp = as_a <expr *> (c->what);
1213 expr *cmp = new expr (ocmp);
1214 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1215 cmp->append_op (ocmp->ops[j]);
1216 cmp->is_generic = true;
1217 ne->ops[0] = new capture (c->location, c->where, cmp,
1218 c->value_match);
1219 }
1220 else
1221 {
1222 expr *ocmp = as_a <expr *> (ne->ops[0]);
1223 expr *cmp = new expr (ocmp);
1224 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1225 cmp->append_op (ocmp->ops[j]);
1226 cmp->is_generic = true;
1227 ne->ops[0] = cmp;
1228 }
1229 ro.safe_push (ne);
1230 }
1231 }
1232
1233 return ro;
1234 }
1235
1236 /* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1237 GENERIC and a GIMPLE variant. */
1238
1239 static void
lower_cond(simplify * s,vec<simplify * > & simplifiers)1240 lower_cond (simplify *s, vec<simplify *>& simplifiers)
1241 {
1242 vec<operand *> matchers = lower_cond (s->match);
1243 for (unsigned i = 0; i < matchers.length (); ++i)
1244 {
1245 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1246 s->for_vec, s->capture_ids);
1247 simplifiers.safe_push (ns);
1248 }
1249 }
1250
1251 /* Return true if O refers to ID. */
1252
1253 bool
contains_id(operand * o,user_id * id)1254 contains_id (operand *o, user_id *id)
1255 {
1256 if (capture *c = dyn_cast<capture *> (o))
1257 return c->what && contains_id (c->what, id);
1258
1259 if (expr *e = dyn_cast<expr *> (o))
1260 {
1261 if (e->operation == id)
1262 return true;
1263 for (unsigned i = 0; i < e->ops.length (); ++i)
1264 if (contains_id (e->ops[i], id))
1265 return true;
1266 return false;
1267 }
1268
1269 if (with_expr *w = dyn_cast <with_expr *> (o))
1270 return (contains_id (w->with, id)
1271 || contains_id (w->subexpr, id));
1272
1273 if (if_expr *ife = dyn_cast <if_expr *> (o))
1274 return (contains_id (ife->cond, id)
1275 || contains_id (ife->trueexpr, id)
1276 || (ife->falseexpr && contains_id (ife->falseexpr, id)));
1277
1278 if (c_expr *ce = dyn_cast<c_expr *> (o))
1279 return ce->capture_ids && ce->capture_ids->get (id->id);
1280
1281 return false;
1282 }
1283
1284
1285 /* In AST operand O replace operator ID with operator WITH. */
1286
1287 operand *
replace_id(operand * o,user_id * id,id_base * with)1288 replace_id (operand *o, user_id *id, id_base *with)
1289 {
1290 /* Deep-copy captures and expressions, replacing operations as
1291 needed. */
1292 if (capture *c = dyn_cast<capture *> (o))
1293 {
1294 if (!c->what)
1295 return c;
1296 return new capture (c->location, c->where,
1297 replace_id (c->what, id, with), c->value_match);
1298 }
1299 else if (expr *e = dyn_cast<expr *> (o))
1300 {
1301 expr *ne = new expr (e);
1302 if (e->operation == id)
1303 ne->operation = with;
1304 for (unsigned i = 0; i < e->ops.length (); ++i)
1305 ne->append_op (replace_id (e->ops[i], id, with));
1306 return ne;
1307 }
1308 else if (with_expr *w = dyn_cast <with_expr *> (o))
1309 {
1310 with_expr *nw = new with_expr (w->location);
1311 nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1312 nw->subexpr = replace_id (w->subexpr, id, with);
1313 return nw;
1314 }
1315 else if (if_expr *ife = dyn_cast <if_expr *> (o))
1316 {
1317 if_expr *nife = new if_expr (ife->location);
1318 nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1319 nife->trueexpr = replace_id (ife->trueexpr, id, with);
1320 if (ife->falseexpr)
1321 nife->falseexpr = replace_id (ife->falseexpr, id, with);
1322 return nife;
1323 }
1324
1325 /* For c_expr we simply record a string replacement table which is
1326 applied at code-generation time. */
1327 if (c_expr *ce = dyn_cast<c_expr *> (o))
1328 {
1329 vec<c_expr::id_tab> ids = ce->ids.copy ();
1330 ids.safe_push (c_expr::id_tab (id->id, with->id));
1331 return new c_expr (ce->r, ce->location,
1332 ce->code, ce->nr_stmts, ids, ce->capture_ids);
1333 }
1334
1335 return o;
1336 }
1337
1338 /* Return true if the binary operator OP is ok for delayed substitution
1339 during for lowering. */
1340
1341 static bool
binary_ok(operator_id * op)1342 binary_ok (operator_id *op)
1343 {
1344 switch (op->code)
1345 {
1346 case PLUS_EXPR:
1347 case MINUS_EXPR:
1348 case MULT_EXPR:
1349 case TRUNC_DIV_EXPR:
1350 case CEIL_DIV_EXPR:
1351 case FLOOR_DIV_EXPR:
1352 case ROUND_DIV_EXPR:
1353 case TRUNC_MOD_EXPR:
1354 case CEIL_MOD_EXPR:
1355 case FLOOR_MOD_EXPR:
1356 case ROUND_MOD_EXPR:
1357 case RDIV_EXPR:
1358 case EXACT_DIV_EXPR:
1359 case MIN_EXPR:
1360 case MAX_EXPR:
1361 case BIT_IOR_EXPR:
1362 case BIT_XOR_EXPR:
1363 case BIT_AND_EXPR:
1364 return true;
1365 default:
1366 return false;
1367 }
1368 }
1369
1370 /* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1371
1372 static void
lower_for(simplify * sin,vec<simplify * > & simplifiers)1373 lower_for (simplify *sin, vec<simplify *>& simplifiers)
1374 {
1375 vec<vec<user_id *> >& for_vec = sin->for_vec;
1376 unsigned worklist_start = 0;
1377 auto_vec<simplify *> worklist;
1378 worklist.safe_push (sin);
1379
1380 /* Lower each recorded for separately, operating on the
1381 set of simplifiers created by the previous one.
1382 Lower inner-to-outer so inner for substitutes can refer
1383 to operators replaced by outer fors. */
1384 for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1385 {
1386 vec<user_id *>& ids = for_vec[fi];
1387 unsigned n_ids = ids.length ();
1388 unsigned max_n_opers = 0;
1389 bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
1390 for (unsigned i = 0; i < n_ids; ++i)
1391 {
1392 if (ids[i]->substitutes.length () > max_n_opers)
1393 max_n_opers = ids[i]->substitutes.length ();
1394 /* Require that all substitutes are of the same kind so that
1395 if we delay substitution to the result op code generation
1396 can look at the first substitute for deciding things like
1397 types of operands. */
1398 enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1399 for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1400 if (ids[i]->substitutes[j]->kind != kind)
1401 can_delay_subst = false;
1402 else if (operator_id *op
1403 = dyn_cast <operator_id *> (ids[i]->substitutes[j]))
1404 {
1405 operator_id *op0
1406 = as_a <operator_id *> (ids[i]->substitutes[0]);
1407 if (strcmp (op->tcc, "tcc_comparison") == 0
1408 && strcmp (op0->tcc, "tcc_comparison") == 0)
1409 ;
1410 /* Unfortunately we can't just allow all tcc_binary. */
1411 else if (strcmp (op->tcc, "tcc_binary") == 0
1412 && strcmp (op0->tcc, "tcc_binary") == 0
1413 && binary_ok (op)
1414 && binary_ok (op0))
1415 ;
1416 else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
1417 || strcmp (op->id + 1, "ROTATE_EXPR") == 0)
1418 && (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
1419 || strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
1420 ;
1421 else
1422 can_delay_subst = false;
1423 }
1424 else if (is_a <fn_id *> (ids[i]->substitutes[j]))
1425 ;
1426 else
1427 can_delay_subst = false;
1428 }
1429
1430 unsigned worklist_end = worklist.length ();
1431 for (unsigned si = worklist_start; si < worklist_end; ++si)
1432 {
1433 simplify *s = worklist[si];
1434 for (unsigned j = 0; j < max_n_opers; ++j)
1435 {
1436 operand *match_op = s->match;
1437 operand *result_op = s->result;
1438 auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
1439 bool skip = false;
1440 for (unsigned i = 0; i < n_ids; ++i)
1441 {
1442 user_id *id = ids[i];
1443 id_base *oper = id->substitutes[j % id->substitutes.length ()];
1444 if (oper == null_id
1445 && (contains_id (match_op, id)
1446 || contains_id (result_op, id)))
1447 {
1448 skip = true;
1449 break;
1450 }
1451 subst.quick_push (std::make_pair (id, oper));
1452 match_op = replace_id (match_op, id, oper);
1453 if (result_op
1454 && !can_delay_subst)
1455 result_op = replace_id (result_op, id, oper);
1456 }
1457 if (skip)
1458 continue;
1459
1460 simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
1461 vNULL, s->capture_ids);
1462 ns->for_subst_vec.safe_splice (s->for_subst_vec);
1463 if (result_op
1464 && can_delay_subst)
1465 ns->for_subst_vec.safe_splice (subst);
1466
1467 worklist.safe_push (ns);
1468 }
1469 }
1470 worklist_start = worklist_end;
1471 }
1472
1473 /* Copy out the result from the last for lowering. */
1474 for (unsigned i = worklist_start; i < worklist.length (); ++i)
1475 simplifiers.safe_push (worklist[i]);
1476 }
1477
1478 /* Lower the AST for everything in SIMPLIFIERS. */
1479
1480 static void
lower(vec<simplify * > & simplifiers,bool gimple)1481 lower (vec<simplify *>& simplifiers, bool gimple)
1482 {
1483 auto_vec<simplify *> out_simplifiers;
1484 for (unsigned i = 0; i < simplifiers.length (); ++i)
1485 lower_opt_convert (simplifiers[i], out_simplifiers);
1486
1487 simplifiers.truncate (0);
1488 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1489 lower_commutative (out_simplifiers[i], simplifiers);
1490
1491 out_simplifiers.truncate (0);
1492 if (gimple)
1493 for (unsigned i = 0; i < simplifiers.length (); ++i)
1494 lower_cond (simplifiers[i], out_simplifiers);
1495 else
1496 out_simplifiers.safe_splice (simplifiers);
1497
1498
1499 simplifiers.truncate (0);
1500 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1501 lower_for (out_simplifiers[i], simplifiers);
1502 }
1503
1504
1505
1506
1507 /* The decision tree built for generating GIMPLE and GENERIC pattern
1508 matching code. It represents the 'match' expression of all
1509 simplifies and has those as its leafs. */
1510
1511 struct dt_simplify;
1512
1513 /* A hash-map collecting semantically equivalent leafs in the decision
1514 tree for splitting out to separate functions. */
1515 struct sinfo
1516 {
1517 dt_simplify *s;
1518
1519 const char *fname;
1520 unsigned cnt;
1521 };
1522
1523 struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1524 sinfo *>
1525 {
1526 static inline hashval_t hash (const key_type &);
1527 static inline bool equal_keys (const key_type &, const key_type &);
removesinfo_hashmap_traits1528 template <typename T> static inline void remove (T &) {}
1529 };
1530
1531 typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1532 sinfo_map_t;
1533
1534 /* Current simplifier ID we are processing during insertion into the
1535 decision tree. */
1536 static unsigned current_id;
1537
1538 /* Decision tree base class, used for DT_NODE. */
1539
1540 struct dt_node
1541 {
1542 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1543
1544 enum dt_type type;
1545 unsigned level;
1546 dt_node *parent;
1547 vec<dt_node *> kids;
1548
1549 /* Statistics. */
1550 unsigned num_leafs;
1551 unsigned total_size;
1552 unsigned max_level;
1553
dt_nodedt_node1554 dt_node (enum dt_type type_, dt_node *parent_)
1555 : type (type_), level (0), parent (parent_), kids (vNULL) {}
1556
1557 dt_node *append_node (dt_node *);
1558 dt_node *append_op (operand *, dt_node *parent, unsigned pos);
1559 dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
1560 dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
1561 unsigned pos);
1562 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1563
gendt_node1564 virtual void gen (FILE *, int, bool) {}
1565
1566 void gen_kids (FILE *, int, bool);
1567 void gen_kids_1 (FILE *, int, bool,
1568 vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1569 vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1570
1571 void analyze (sinfo_map_t &);
1572 };
1573
1574 /* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1575
1576 struct dt_operand : public dt_node
1577 {
1578 operand *op;
1579 dt_operand *match_dop;
1580 unsigned pos;
1581 bool value_match;
1582 unsigned for_id;
1583
dt_operanddt_operand1584 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1585 dt_operand *parent_, unsigned pos_)
1586 : dt_node (type, parent_), op (op_), match_dop (match_dop_),
1587 pos (pos_), value_match (false), for_id (current_id) {}
1588
1589 void gen (FILE *, int, bool);
1590 unsigned gen_predicate (FILE *, int, const char *, bool);
1591 unsigned gen_match_op (FILE *, int, const char *, bool);
1592
1593 unsigned gen_gimple_expr (FILE *, int);
1594 unsigned gen_generic_expr (FILE *, int, const char *);
1595
1596 char *get_name (char *);
1597 void gen_opname (char *, unsigned);
1598 };
1599
1600 /* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1601
1602 struct dt_simplify : public dt_node
1603 {
1604 simplify *s;
1605 unsigned pattern_no;
1606 dt_operand **indexes;
1607 sinfo *info;
1608
dt_simplifydt_simplify1609 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1610 : dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
1611 indexes (indexes_), info (NULL) {}
1612
1613 void gen_1 (FILE *, int, bool, operand *);
1614 void gen (FILE *f, int, bool);
1615 };
1616
1617 template<>
1618 template<>
1619 inline bool
test(dt_node * n)1620 is_a_helper <dt_operand *>::test (dt_node *n)
1621 {
1622 return (n->type == dt_node::DT_OPERAND
1623 || n->type == dt_node::DT_MATCH
1624 || n->type == dt_node::DT_TRUE);
1625 }
1626
1627 template<>
1628 template<>
1629 inline bool
test(dt_node * n)1630 is_a_helper <dt_simplify *>::test (dt_node *n)
1631 {
1632 return n->type == dt_node::DT_SIMPLIFY;
1633 }
1634
1635
1636
1637 /* A container for the actual decision tree. */
1638
1639 struct decision_tree
1640 {
1641 dt_node *root;
1642
1643 void insert (struct simplify *, unsigned);
1644 void gen (FILE *f, bool gimple);
1645 void print (FILE *f = stderr);
1646
decision_treedecision_tree1647 decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
1648
1649 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1650 unsigned pos = 0, dt_node *parent = 0);
1651 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1652 static bool cmp_node (dt_node *, dt_node *);
1653 static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1654 };
1655
1656 /* Compare two AST operands O1 and O2 and return true if they are equal. */
1657
1658 bool
cmp_operand(operand * o1,operand * o2)1659 cmp_operand (operand *o1, operand *o2)
1660 {
1661 if (!o1 || !o2 || o1->type != o2->type)
1662 return false;
1663
1664 if (o1->type == operand::OP_PREDICATE)
1665 {
1666 predicate *p1 = as_a<predicate *>(o1);
1667 predicate *p2 = as_a<predicate *>(o2);
1668 return p1->p == p2->p;
1669 }
1670 else if (o1->type == operand::OP_EXPR)
1671 {
1672 expr *e1 = static_cast<expr *>(o1);
1673 expr *e2 = static_cast<expr *>(o2);
1674 return (e1->operation == e2->operation
1675 && e1->is_generic == e2->is_generic);
1676 }
1677 else
1678 return false;
1679 }
1680
1681 /* Compare two decision tree nodes N1 and N2 and return true if they
1682 are equal. */
1683
1684 bool
cmp_node(dt_node * n1,dt_node * n2)1685 decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1686 {
1687 if (!n1 || !n2 || n1->type != n2->type)
1688 return false;
1689
1690 if (n1 == n2)
1691 return true;
1692
1693 if (n1->type == dt_node::DT_TRUE)
1694 return false;
1695
1696 if (n1->type == dt_node::DT_OPERAND)
1697 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1698 (as_a<dt_operand *> (n2))->op);
1699 else if (n1->type == dt_node::DT_MATCH)
1700 return (((as_a<dt_operand *> (n1))->match_dop
1701 == (as_a<dt_operand *> (n2))->match_dop)
1702 && ((as_a<dt_operand *> (n1))->value_match
1703 == (as_a<dt_operand *> (n2))->value_match));
1704 return false;
1705 }
1706
1707 /* Search OPS for a decision tree node like P and return it if found. */
1708
1709 dt_node *
find_node(vec<dt_node * > & ops,dt_node * p)1710 decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1711 {
1712 /* We can merge adjacent DT_TRUE. */
1713 if (p->type == dt_node::DT_TRUE
1714 && !ops.is_empty ()
1715 && ops.last ()->type == dt_node::DT_TRUE)
1716 return ops.last ();
1717 dt_operand *true_node = NULL;
1718 for (int i = ops.length () - 1; i >= 0; --i)
1719 {
1720 /* But we can't merge across DT_TRUE nodes as they serve as
1721 pattern order barriers to make sure that patterns apply
1722 in order of appearance in case multiple matches are possible. */
1723 if (ops[i]->type == dt_node::DT_TRUE)
1724 {
1725 if (! true_node
1726 || as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
1727 true_node = as_a <dt_operand *> (ops[i]);
1728 }
1729 if (decision_tree::cmp_node (ops[i], p))
1730 {
1731 /* Unless we are processing the same pattern or the blocking
1732 pattern is before the one we are going to merge with. */
1733 if (true_node
1734 && true_node->for_id != current_id
1735 && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
1736 {
1737 if (verbose >= 1)
1738 {
1739 source_location p_loc = 0;
1740 if (p->type == dt_node::DT_OPERAND)
1741 p_loc = as_a <dt_operand *> (p)->op->location;
1742 source_location op_loc = 0;
1743 if (ops[i]->type == dt_node::DT_OPERAND)
1744 op_loc = as_a <dt_operand *> (ops[i])->op->location;
1745 source_location true_loc = 0;
1746 true_loc = true_node->op->location;
1747 warning_at (p_loc,
1748 "failed to merge decision tree node");
1749 warning_at (op_loc,
1750 "with the following");
1751 warning_at (true_loc,
1752 "because of the following which serves as ordering "
1753 "barrier");
1754 }
1755 return NULL;
1756 }
1757 return ops[i];
1758 }
1759 }
1760 return NULL;
1761 }
1762
1763 /* Append N to the decision tree if it there is not already an existing
1764 identical child. */
1765
1766 dt_node *
append_node(dt_node * n)1767 dt_node::append_node (dt_node *n)
1768 {
1769 dt_node *kid;
1770
1771 kid = decision_tree::find_node (kids, n);
1772 if (kid)
1773 return kid;
1774
1775 kids.safe_push (n);
1776 n->level = this->level + 1;
1777
1778 return n;
1779 }
1780
1781 /* Append OP to the decision tree. */
1782
1783 dt_node *
append_op(operand * op,dt_node * parent,unsigned pos)1784 dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1785 {
1786 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1787 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1788 return append_node (n);
1789 }
1790
1791 /* Append a DT_TRUE decision tree node. */
1792
1793 dt_node *
append_true_op(operand * op,dt_node * parent,unsigned pos)1794 dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
1795 {
1796 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1797 dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
1798 return append_node (n);
1799 }
1800
1801 /* Append a DT_MATCH decision tree node. */
1802
1803 dt_node *
append_match_op(operand * op,dt_operand * match_dop,dt_node * parent,unsigned pos)1804 dt_node::append_match_op (operand *op, dt_operand *match_dop,
1805 dt_node *parent, unsigned pos)
1806 {
1807 dt_operand *parent_ = as_a<dt_operand *> (parent);
1808 dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
1809 return append_node (n);
1810 }
1811
1812 /* Append S to the decision tree. */
1813
1814 dt_node *
append_simplify(simplify * s,unsigned pattern_no,dt_operand ** indexes)1815 dt_node::append_simplify (simplify *s, unsigned pattern_no,
1816 dt_operand **indexes)
1817 {
1818 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1819 for (unsigned i = 0; i < kids.length (); ++i)
1820 if (dt_simplify *s2 = dyn_cast <dt_simplify *> (kids[i]))
1821 {
1822 warning_at (s->match->location, "duplicate pattern");
1823 warning_at (s2->s->match->location, "previous pattern defined here");
1824 print_operand (s->match, stderr);
1825 fprintf (stderr, "\n");
1826 }
1827 return append_node (n);
1828 }
1829
1830 /* Analyze the node and its children. */
1831
1832 void
analyze(sinfo_map_t & map)1833 dt_node::analyze (sinfo_map_t &map)
1834 {
1835 num_leafs = 0;
1836 total_size = 1;
1837 max_level = level;
1838
1839 if (type == DT_SIMPLIFY)
1840 {
1841 /* Populate the map of equivalent simplifies. */
1842 dt_simplify *s = as_a <dt_simplify *> (this);
1843 bool existed;
1844 sinfo *&si = map.get_or_insert (s, &existed);
1845 if (!existed)
1846 {
1847 si = new sinfo;
1848 si->s = s;
1849 si->cnt = 1;
1850 si->fname = NULL;
1851 }
1852 else
1853 si->cnt++;
1854 s->info = si;
1855 num_leafs = 1;
1856 return;
1857 }
1858
1859 for (unsigned i = 0; i < kids.length (); ++i)
1860 {
1861 kids[i]->analyze (map);
1862 num_leafs += kids[i]->num_leafs;
1863 total_size += kids[i]->total_size;
1864 max_level = MAX (max_level, kids[i]->max_level);
1865 }
1866 }
1867
1868 /* Insert O into the decision tree and return the decision tree node found
1869 or created. */
1870
1871 dt_node *
insert_operand(dt_node * p,operand * o,dt_operand ** indexes,unsigned pos,dt_node * parent)1872 decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1873 unsigned pos, dt_node *parent)
1874 {
1875 dt_node *q, *elm = 0;
1876
1877 if (capture *c = dyn_cast<capture *> (o))
1878 {
1879 unsigned capt_index = c->where;
1880
1881 if (indexes[capt_index] == 0)
1882 {
1883 if (c->what)
1884 q = insert_operand (p, c->what, indexes, pos, parent);
1885 else
1886 {
1887 q = elm = p->append_true_op (o, parent, pos);
1888 goto at_assert_elm;
1889 }
1890 // get to the last capture
1891 for (operand *what = c->what;
1892 what && is_a<capture *> (what);
1893 c = as_a<capture *> (what), what = c->what)
1894 ;
1895
1896 if (!c->what)
1897 {
1898 unsigned cc_index = c->where;
1899 dt_operand *match_op = indexes[cc_index];
1900
1901 dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
1902 elm = decision_tree::find_node (p->kids, &temp);
1903
1904 if (elm == 0)
1905 {
1906 dt_operand temp (dt_node::DT_MATCH, 0, match_op, 0, 0);
1907 temp.value_match = c->value_match;
1908 elm = decision_tree::find_node (p->kids, &temp);
1909 }
1910 }
1911 else
1912 {
1913 dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
1914 elm = decision_tree::find_node (p->kids, &temp);
1915 }
1916
1917 at_assert_elm:
1918 gcc_assert (elm->type == dt_node::DT_TRUE
1919 || elm->type == dt_node::DT_OPERAND
1920 || elm->type == dt_node::DT_MATCH);
1921 indexes[capt_index] = static_cast<dt_operand *> (elm);
1922 return q;
1923 }
1924 else
1925 {
1926 p = p->append_match_op (o, indexes[capt_index], parent, pos);
1927 as_a <dt_operand *>(p)->value_match = c->value_match;
1928 if (c->what)
1929 return insert_operand (p, c->what, indexes, 0, p);
1930 else
1931 return p;
1932 }
1933 }
1934 p = p->append_op (o, parent, pos);
1935 q = p;
1936
1937 if (expr *e = dyn_cast <expr *>(o))
1938 {
1939 for (unsigned i = 0; i < e->ops.length (); ++i)
1940 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1941 }
1942
1943 return q;
1944 }
1945
1946 /* Insert S into the decision tree. */
1947
1948 void
insert(struct simplify * s,unsigned pattern_no)1949 decision_tree::insert (struct simplify *s, unsigned pattern_no)
1950 {
1951 current_id = s->id;
1952 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1953 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1954 p->append_simplify (s, pattern_no, indexes);
1955 }
1956
1957 /* Debug functions to dump the decision tree. */
1958
1959 DEBUG_FUNCTION void
print_node(dt_node * p,FILE * f,unsigned indent)1960 decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1961 {
1962 if (p->type == dt_node::DT_NODE)
1963 fprintf (f, "root");
1964 else
1965 {
1966 fprintf (f, "|");
1967 for (unsigned i = 0; i < indent; i++)
1968 fprintf (f, "-");
1969
1970 if (p->type == dt_node::DT_OPERAND)
1971 {
1972 dt_operand *dop = static_cast<dt_operand *>(p);
1973 print_operand (dop->op, f, true);
1974 }
1975 else if (p->type == dt_node::DT_TRUE)
1976 fprintf (f, "true");
1977 else if (p->type == dt_node::DT_MATCH)
1978 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1979 else if (p->type == dt_node::DT_SIMPLIFY)
1980 {
1981 dt_simplify *s = static_cast<dt_simplify *> (p);
1982 fprintf (f, "simplify_%u { ", s->pattern_no);
1983 for (int i = 0; i <= s->s->capture_max; ++i)
1984 fprintf (f, "%p, ", (void *) s->indexes[i]);
1985 fprintf (f, " } ");
1986 }
1987 if (is_a <dt_operand *> (p))
1988 fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
1989 }
1990
1991 fprintf (stderr, " (%p, %p), %u, %u\n",
1992 (void *) p, (void *) p->parent, p->level, p->kids.length ());
1993
1994 for (unsigned i = 0; i < p->kids.length (); ++i)
1995 decision_tree::print_node (p->kids[i], f, indent + 2);
1996 }
1997
1998 DEBUG_FUNCTION void
print(FILE * f)1999 decision_tree::print (FILE *f)
2000 {
2001 return decision_tree::print_node (root, f);
2002 }
2003
2004
2005 /* For GENERIC we have to take care of wrapping multiple-used
2006 expressions with side-effects in save_expr and preserve side-effects
2007 of expressions with omit_one_operand. Analyze captures in
2008 match, result and with expressions and perform early-outs
2009 on the outermost match expression operands for cases we cannot
2010 handle. */
2011
2012 struct capture_info
2013 {
2014 capture_info (simplify *s, operand *, bool);
2015 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
2016 bool walk_result (operand *o, bool, operand *);
2017 void walk_c_expr (c_expr *);
2018
2019 struct cinfo
2020 {
2021 bool expr_p;
2022 bool cse_p;
2023 bool force_no_side_effects_p;
2024 bool force_single_use;
2025 bool cond_expr_cond_p;
2026 unsigned long toplevel_msk;
2027 unsigned match_use_count;
2028 unsigned result_use_count;
2029 unsigned same_as;
2030 capture *c;
2031 };
2032
2033 auto_vec<cinfo> info;
2034 unsigned long force_no_side_effects;
2035 bool gimple;
2036 };
2037
2038 /* Analyze captures in S. */
2039
capture_info(simplify * s,operand * result,bool gimple_)2040 capture_info::capture_info (simplify *s, operand *result, bool gimple_)
2041 {
2042 gimple = gimple_;
2043
2044 expr *e;
2045 if (s->kind == simplify::MATCH)
2046 {
2047 force_no_side_effects = -1;
2048 return;
2049 }
2050
2051 force_no_side_effects = 0;
2052 info.safe_grow_cleared (s->capture_max + 1);
2053 for (int i = 0; i <= s->capture_max; ++i)
2054 info[i].same_as = i;
2055
2056 e = as_a <expr *> (s->match);
2057 for (unsigned i = 0; i < e->ops.length (); ++i)
2058 walk_match (e->ops[i], i,
2059 (i != 0 && *e->operation == COND_EXPR)
2060 || *e->operation == TRUTH_ANDIF_EXPR
2061 || *e->operation == TRUTH_ORIF_EXPR,
2062 i == 0
2063 && (*e->operation == COND_EXPR
2064 || *e->operation == VEC_COND_EXPR));
2065
2066 walk_result (s->result, false, result);
2067 }
2068
2069 /* Analyze captures in the match expression piece O. */
2070
2071 void
walk_match(operand * o,unsigned toplevel_arg,bool conditional_p,bool cond_expr_cond_p)2072 capture_info::walk_match (operand *o, unsigned toplevel_arg,
2073 bool conditional_p, bool cond_expr_cond_p)
2074 {
2075 if (capture *c = dyn_cast <capture *> (o))
2076 {
2077 unsigned where = c->where;
2078 info[where].match_use_count++;
2079 info[where].toplevel_msk |= 1 << toplevel_arg;
2080 info[where].force_no_side_effects_p |= conditional_p;
2081 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2082 if (!info[where].c)
2083 info[where].c = c;
2084 if (!c->what)
2085 return;
2086 /* Recurse to exprs and captures. */
2087 if (is_a <capture *> (c->what)
2088 || is_a <expr *> (c->what))
2089 walk_match (c->what, toplevel_arg, conditional_p, false);
2090 /* We need to look past multiple captures to find a captured
2091 expression as with conditional converts two captures
2092 can be collapsed onto the same expression. Also collect
2093 what captures capture the same thing. */
2094 while (c->what && is_a <capture *> (c->what))
2095 {
2096 c = as_a <capture *> (c->what);
2097 if (info[c->where].same_as != c->where
2098 && info[c->where].same_as != info[where].same_as)
2099 fatal_at (c->location, "cannot handle this collapsed capture");
2100 info[c->where].same_as = info[where].same_as;
2101 }
2102 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2103 expr *e;
2104 if (c->what
2105 && (e = dyn_cast <expr *> (c->what)))
2106 {
2107 /* Zero-operand expression captures like ADDR_EXPR@0 are
2108 similar as predicates -- if they are not mentioned in
2109 the result we have to force them to have no side-effects. */
2110 if (e->ops.length () != 0)
2111 info[where].expr_p = true;
2112 info[where].force_single_use |= e->force_single_use;
2113 }
2114 }
2115 else if (expr *e = dyn_cast <expr *> (o))
2116 {
2117 for (unsigned i = 0; i < e->ops.length (); ++i)
2118 {
2119 bool cond_p = conditional_p;
2120 bool cond_expr_cond_p = false;
2121 if (i != 0 && *e->operation == COND_EXPR)
2122 cond_p = true;
2123 else if (*e->operation == TRUTH_ANDIF_EXPR
2124 || *e->operation == TRUTH_ORIF_EXPR)
2125 cond_p = true;
2126 if (i == 0
2127 && (*e->operation == COND_EXPR
2128 || *e->operation == VEC_COND_EXPR))
2129 cond_expr_cond_p = true;
2130 walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
2131 }
2132 }
2133 else if (is_a <predicate *> (o))
2134 {
2135 /* Mark non-captured leafs toplevel arg for checking. */
2136 force_no_side_effects |= 1 << toplevel_arg;
2137 if (verbose >= 1
2138 && !gimple)
2139 warning_at (o->location,
2140 "forcing no side-effects on possibly lost leaf");
2141 }
2142 else
2143 gcc_unreachable ();
2144 }
2145
2146 /* Analyze captures in the result expression piece O. Return true
2147 if RESULT was visited in one of the children. Only visit
2148 non-if/with children if they are rooted on RESULT. */
2149
2150 bool
walk_result(operand * o,bool conditional_p,operand * result)2151 capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2152 {
2153 if (capture *c = dyn_cast <capture *> (o))
2154 {
2155 unsigned where = info[c->where].same_as;
2156 info[where].result_use_count++;
2157 /* If we substitute an expression capture we don't know
2158 which captures this will end up using (well, we don't
2159 compute that). Force the uses to be side-effect free
2160 which means forcing the toplevels that reach the
2161 expression side-effect free. */
2162 if (info[where].expr_p)
2163 force_no_side_effects |= info[where].toplevel_msk;
2164 /* Mark CSE capture uses as forced to have no side-effects. */
2165 if (c->what
2166 && is_a <expr *> (c->what))
2167 {
2168 info[where].cse_p = true;
2169 walk_result (c->what, true, result);
2170 }
2171 }
2172 else if (expr *e = dyn_cast <expr *> (o))
2173 {
2174 id_base *opr = e->operation;
2175 if (user_id *uid = dyn_cast <user_id *> (opr))
2176 opr = uid->substitutes[0];
2177 for (unsigned i = 0; i < e->ops.length (); ++i)
2178 {
2179 bool cond_p = conditional_p;
2180 if (i != 0 && *e->operation == COND_EXPR)
2181 cond_p = true;
2182 else if (*e->operation == TRUTH_ANDIF_EXPR
2183 || *e->operation == TRUTH_ORIF_EXPR)
2184 cond_p = true;
2185 walk_result (e->ops[i], cond_p, result);
2186 }
2187 }
2188 else if (if_expr *e = dyn_cast <if_expr *> (o))
2189 {
2190 /* 'if' conditions should be all fine. */
2191 if (e->trueexpr == result)
2192 {
2193 walk_result (e->trueexpr, false, result);
2194 return true;
2195 }
2196 if (e->falseexpr == result)
2197 {
2198 walk_result (e->falseexpr, false, result);
2199 return true;
2200 }
2201 bool res = false;
2202 if (is_a <if_expr *> (e->trueexpr)
2203 || is_a <with_expr *> (e->trueexpr))
2204 res |= walk_result (e->trueexpr, false, result);
2205 if (e->falseexpr
2206 && (is_a <if_expr *> (e->falseexpr)
2207 || is_a <with_expr *> (e->falseexpr)))
2208 res |= walk_result (e->falseexpr, false, result);
2209 return res;
2210 }
2211 else if (with_expr *e = dyn_cast <with_expr *> (o))
2212 {
2213 bool res = (e->subexpr == result);
2214 if (res
2215 || is_a <if_expr *> (e->subexpr)
2216 || is_a <with_expr *> (e->subexpr))
2217 res |= walk_result (e->subexpr, false, result);
2218 if (res)
2219 walk_c_expr (e->with);
2220 return res;
2221 }
2222 else if (c_expr *e = dyn_cast <c_expr *> (o))
2223 walk_c_expr (e);
2224 else
2225 gcc_unreachable ();
2226
2227 return false;
2228 }
2229
2230 /* Look for captures in the C expr E. */
2231
2232 void
walk_c_expr(c_expr * e)2233 capture_info::walk_c_expr (c_expr *e)
2234 {
2235 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2236 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2237 really escape through. */
2238 unsigned p_depth = 0;
2239 for (unsigned i = 0; i < e->code.length (); ++i)
2240 {
2241 const cpp_token *t = &e->code[i];
2242 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2243 id_base *id;
2244 if (t->type == CPP_NAME
2245 && (strcmp ((const char *)CPP_HASHNODE
2246 (t->val.node.node)->ident.str, "TREE_TYPE") == 0
2247 || strcmp ((const char *)CPP_HASHNODE
2248 (t->val.node.node)->ident.str, "TREE_CODE") == 0
2249 || strcmp ((const char *)CPP_HASHNODE
2250 (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
2251 || ((id = get_operator ((const char *)CPP_HASHNODE
2252 (t->val.node.node)->ident.str))
2253 && is_a <predicate_id *> (id)))
2254 && n->type == CPP_OPEN_PAREN)
2255 p_depth++;
2256 else if (t->type == CPP_CLOSE_PAREN
2257 && p_depth > 0)
2258 p_depth--;
2259 else if (p_depth == 0
2260 && t->type == CPP_ATSIGN
2261 && (n->type == CPP_NUMBER
2262 || n->type == CPP_NAME)
2263 && !(n->flags & PREV_WHITE))
2264 {
2265 const char *id;
2266 if (n->type == CPP_NUMBER)
2267 id = (const char *)n->val.str.text;
2268 else
2269 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2270 unsigned *where = e->capture_ids->get(id);
2271 if (! where)
2272 fatal_at (n, "unknown capture id '%s'", id);
2273 info[info[*where].same_as].force_no_side_effects_p = true;
2274 if (verbose >= 1
2275 && !gimple)
2276 warning_at (t, "capture escapes");
2277 }
2278 }
2279 }
2280
2281
2282 /* Code generation off the decision tree and the refered AST nodes. */
2283
2284 bool
is_conversion(id_base * op)2285 is_conversion (id_base *op)
2286 {
2287 return (*op == CONVERT_EXPR
2288 || *op == NOP_EXPR
2289 || *op == FLOAT_EXPR
2290 || *op == FIX_TRUNC_EXPR
2291 || *op == VIEW_CONVERT_EXPR);
2292 }
2293
2294 /* Get the type to be used for generating operand POS of OP from the
2295 various sources. */
2296
2297 static const char *
get_operand_type(id_base * op,unsigned pos,const char * in_type,const char * expr_type,const char * other_oprnd_type)2298 get_operand_type (id_base *op, unsigned pos,
2299 const char *in_type,
2300 const char *expr_type,
2301 const char *other_oprnd_type)
2302 {
2303 /* Generally operands whose type does not match the type of the
2304 expression generated need to know their types but match and
2305 thus can fall back to 'other_oprnd_type'. */
2306 if (is_conversion (op))
2307 return other_oprnd_type;
2308 else if (*op == REALPART_EXPR
2309 || *op == IMAGPART_EXPR)
2310 return other_oprnd_type;
2311 else if (is_a <operator_id *> (op)
2312 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2313 return other_oprnd_type;
2314 else if (*op == COND_EXPR
2315 && pos == 0)
2316 return "boolean_type_node";
2317 else
2318 {
2319 /* Otherwise all types should match - choose one in order of
2320 preference. */
2321 if (expr_type)
2322 return expr_type;
2323 else if (in_type)
2324 return in_type;
2325 else
2326 return other_oprnd_type;
2327 }
2328 }
2329
2330 /* Generate transform code for an expression. */
2331
2332 void
gen_transform(FILE * f,int indent,const char * dest,bool gimple,int depth,const char * in_type,capture_info * cinfo,dt_operand ** indexes,int)2333 expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2334 int depth, const char *in_type, capture_info *cinfo,
2335 dt_operand **indexes, int)
2336 {
2337 id_base *opr = operation;
2338 /* When we delay operator substituting during lowering of fors we
2339 make sure that for code-gen purposes the effects of each substitute
2340 are the same. Thus just look at that. */
2341 if (user_id *uid = dyn_cast <user_id *> (opr))
2342 opr = uid->substitutes[0];
2343
2344 bool conversion_p = is_conversion (opr);
2345 const char *type = expr_type;
2346 char optype[64];
2347 if (type)
2348 /* If there was a type specification in the pattern use it. */
2349 ;
2350 else if (conversion_p)
2351 /* For conversions we need to build the expression using the
2352 outer type passed in. */
2353 type = in_type;
2354 else if (*opr == REALPART_EXPR
2355 || *opr == IMAGPART_EXPR)
2356 {
2357 /* __real and __imag use the component type of its operand. */
2358 sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
2359 type = optype;
2360 }
2361 else if (is_a <operator_id *> (opr)
2362 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2363 {
2364 /* comparisons use boolean_type_node (or what gets in), but
2365 their operands need to figure out the types themselves. */
2366 if (in_type)
2367 type = in_type;
2368 else
2369 {
2370 sprintf (optype, "boolean_type_node");
2371 type = optype;
2372 }
2373 in_type = NULL;
2374 }
2375 else if (*opr == COND_EXPR
2376 || *opr == VEC_COND_EXPR)
2377 {
2378 /* Conditions are of the same type as their first alternative. */
2379 sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
2380 type = optype;
2381 }
2382 else
2383 {
2384 /* Other operations are of the same type as their first operand. */
2385 sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
2386 type = optype;
2387 }
2388 if (!type)
2389 fatal_at (location, "cannot determine type of operand");
2390
2391 fprintf_indent (f, indent, "{\n");
2392 indent += 2;
2393 fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
2394 char op0type[64];
2395 snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
2396 for (unsigned i = 0; i < ops.length (); ++i)
2397 {
2398 char dest[32];
2399 snprintf (dest, 32, "ops%d[%u]", depth, i);
2400 const char *optype
2401 = get_operand_type (opr, i, in_type, expr_type,
2402 i == 0 ? NULL : op0type);
2403 ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
2404 cinfo, indexes,
2405 (*opr == COND_EXPR
2406 || *opr == VEC_COND_EXPR) && i == 0 ? 1 : 2);
2407 }
2408
2409 const char *opr_name;
2410 if (*operation == CONVERT_EXPR)
2411 opr_name = "NOP_EXPR";
2412 else
2413 opr_name = operation->id;
2414
2415 if (gimple)
2416 {
2417 if (*opr == CONVERT_EXPR)
2418 {
2419 fprintf_indent (f, indent,
2420 "if (%s != TREE_TYPE (ops%d[0])\n",
2421 type, depth);
2422 fprintf_indent (f, indent,
2423 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2424 type, depth);
2425 fprintf_indent (f, indent + 2, "{\n");
2426 indent += 4;
2427 }
2428 /* ??? Building a stmt can fail for various reasons here, seq being
2429 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2430 So if we fail here we should continue matching other patterns. */
2431 fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr_name);
2432 fprintf_indent (f, indent, "tree tem_ops[3] = { ");
2433 for (unsigned i = 0; i < ops.length (); ++i)
2434 fprintf (f, "ops%d[%u]%s", depth, i,
2435 i == ops.length () - 1 ? " };\n" : ", ");
2436 fprintf_indent (f, indent,
2437 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2438 ops.length (), type);
2439 fprintf_indent (f, indent,
2440 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2441 type);
2442 fprintf_indent (f, indent,
2443 "if (!res) return false;\n");
2444 if (*opr == CONVERT_EXPR)
2445 {
2446 indent -= 4;
2447 fprintf_indent (f, indent, " }\n");
2448 fprintf_indent (f, indent, "else\n");
2449 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2450 }
2451 }
2452 else
2453 {
2454 if (*opr == CONVERT_EXPR)
2455 {
2456 fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2457 depth, type);
2458 indent += 2;
2459 }
2460 if (opr->kind == id_base::CODE)
2461 fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
2462 ops.length(), opr_name, type);
2463 else
2464 {
2465 fprintf_indent (f, indent, "{\n");
2466 fprintf_indent (f, indent, " res = maybe_build_call_expr_loc (loc, "
2467 "%s, %s, %d", opr_name, type, ops.length());
2468 }
2469 for (unsigned i = 0; i < ops.length (); ++i)
2470 fprintf (f, ", ops%d[%u]", depth, i);
2471 fprintf (f, ");\n");
2472 if (opr->kind != id_base::CODE)
2473 {
2474 fprintf_indent (f, indent, " if (!res)\n");
2475 fprintf_indent (f, indent, " return NULL_TREE;\n");
2476 fprintf_indent (f, indent, "}\n");
2477 }
2478 if (*opr == CONVERT_EXPR)
2479 {
2480 indent -= 2;
2481 fprintf_indent (f, indent, "else\n");
2482 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2483 }
2484 }
2485 fprintf_indent (f, indent, "%s = res;\n", dest);
2486 indent -= 2;
2487 fprintf_indent (f, indent, "}\n");
2488 }
2489
2490 /* Generate code for a c_expr which is either the expression inside
2491 an if statement or a sequence of statements which computes a
2492 result to be stored to DEST. */
2493
2494 void
gen_transform(FILE * f,int indent,const char * dest,bool,int,const char *,capture_info *,dt_operand **,int)2495 c_expr::gen_transform (FILE *f, int indent, const char *dest,
2496 bool, int, const char *, capture_info *,
2497 dt_operand **, int)
2498 {
2499 if (dest && nr_stmts == 1)
2500 fprintf_indent (f, indent, "%s = ", dest);
2501
2502 unsigned stmt_nr = 1;
2503 for (unsigned i = 0; i < code.length (); ++i)
2504 {
2505 const cpp_token *token = &code[i];
2506
2507 /* Replace captures for code-gen. */
2508 if (token->type == CPP_ATSIGN)
2509 {
2510 const cpp_token *n = &code[i+1];
2511 if ((n->type == CPP_NUMBER
2512 || n->type == CPP_NAME)
2513 && !(n->flags & PREV_WHITE))
2514 {
2515 if (token->flags & PREV_WHITE)
2516 fputc (' ', f);
2517 const char *id;
2518 if (n->type == CPP_NUMBER)
2519 id = (const char *)n->val.str.text;
2520 else
2521 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2522 unsigned *cid = capture_ids->get (id);
2523 if (!cid)
2524 fatal_at (token, "unknown capture id");
2525 fprintf (f, "captures[%u]", *cid);
2526 ++i;
2527 continue;
2528 }
2529 }
2530
2531 if (token->flags & PREV_WHITE)
2532 fputc (' ', f);
2533
2534 if (token->type == CPP_NAME)
2535 {
2536 const char *id = (const char *) NODE_NAME (token->val.node.node);
2537 unsigned j;
2538 for (j = 0; j < ids.length (); ++j)
2539 {
2540 if (strcmp (id, ids[j].id) == 0)
2541 {
2542 fprintf (f, "%s", ids[j].oper);
2543 break;
2544 }
2545 }
2546 if (j < ids.length ())
2547 continue;
2548 }
2549
2550 /* Output the token as string. */
2551 char *tk = (char *)cpp_token_as_text (r, token);
2552 fputs (tk, f);
2553
2554 if (token->type == CPP_SEMICOLON)
2555 {
2556 stmt_nr++;
2557 fputc ('\n', f);
2558 if (dest && stmt_nr == nr_stmts)
2559 fprintf_indent (f, indent, "%s = ", dest);
2560 }
2561 }
2562 }
2563
2564 /* Generate transform code for a capture. */
2565
2566 void
gen_transform(FILE * f,int indent,const char * dest,bool gimple,int depth,const char * in_type,capture_info * cinfo,dt_operand ** indexes,int cond_handling)2567 capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2568 int depth, const char *in_type, capture_info *cinfo,
2569 dt_operand **indexes, int cond_handling)
2570 {
2571 if (what && is_a<expr *> (what))
2572 {
2573 if (indexes[where] == 0)
2574 {
2575 char buf[20];
2576 sprintf (buf, "captures[%u]", where);
2577 what->gen_transform (f, indent, buf, gimple, depth, in_type,
2578 cinfo, NULL);
2579 }
2580 }
2581
2582 /* If in GENERIC some capture is used multiple times, unshare it except
2583 when emitting the last use. */
2584 if (!gimple
2585 && cinfo->info.exists ()
2586 && cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
2587 {
2588 fprintf_indent (f, indent, "%s = unshare_expr (captures[%u]);\n",
2589 dest, where);
2590 cinfo->info[cinfo->info[where].same_as].result_use_count--;
2591 }
2592 else
2593 fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2594
2595 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2596 with substituting a capture of that. */
2597 if (gimple
2598 && cond_handling != 0
2599 && cinfo->info[where].cond_expr_cond_p)
2600 {
2601 /* If substituting into a cond_expr condition, unshare. */
2602 if (cond_handling == 1)
2603 fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
2604 /* If substituting elsewhere we might need to decompose it. */
2605 else if (cond_handling == 2)
2606 {
2607 /* ??? Returning false here will also not allow any other patterns
2608 to match unless this generator was split out. */
2609 fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2610 fprintf_indent (f, indent, " {\n");
2611 fprintf_indent (f, indent, " if (!seq) return false;\n");
2612 fprintf_indent (f, indent, " %s = gimple_build (seq,"
2613 " TREE_CODE (%s),"
2614 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2615 " TREE_OPERAND (%s, 1));\n",
2616 dest, dest, dest, dest, dest);
2617 fprintf_indent (f, indent, " }\n");
2618 }
2619 }
2620 }
2621
2622 /* Return the name of the operand representing the decision tree node.
2623 Use NAME as space to generate it. */
2624
2625 char *
get_name(char * name)2626 dt_operand::get_name (char *name)
2627 {
2628 if (! parent)
2629 sprintf (name, "t");
2630 else if (parent->level == 1)
2631 sprintf (name, "op%u", pos);
2632 else if (parent->type == dt_node::DT_MATCH)
2633 return as_a <dt_operand *> (parent)->get_name (name);
2634 else
2635 sprintf (name, "o%u%u", parent->level, pos);
2636 return name;
2637 }
2638
2639 /* Fill NAME with the operand name at position POS. */
2640
2641 void
gen_opname(char * name,unsigned pos)2642 dt_operand::gen_opname (char *name, unsigned pos)
2643 {
2644 if (! parent)
2645 sprintf (name, "op%u", pos);
2646 else
2647 sprintf (name, "o%u%u", level, pos);
2648 }
2649
2650 /* Generate matching code for the decision tree operand which is
2651 a predicate. */
2652
2653 unsigned
gen_predicate(FILE * f,int indent,const char * opname,bool gimple)2654 dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2655 {
2656 predicate *p = as_a <predicate *> (op);
2657
2658 if (p->p->matchers.exists ())
2659 {
2660 /* If this is a predicate generated from a pattern mangle its
2661 name and pass on the valueize hook. */
2662 if (gimple)
2663 fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2664 p->p->id, opname);
2665 else
2666 fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2667 }
2668 else
2669 fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2670 fprintf_indent (f, indent + 2, "{\n");
2671 return 1;
2672 }
2673
2674 /* Generate matching code for the decision tree operand which is
2675 a capture-match. */
2676
2677 unsigned
gen_match_op(FILE * f,int indent,const char * opname,bool)2678 dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
2679 {
2680 char match_opname[20];
2681 match_dop->get_name (match_opname);
2682 if (value_match)
2683 fprintf_indent (f, indent, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2684 "|| operand_equal_p (%s, %s, 0))\n",
2685 opname, match_opname, opname, opname, match_opname);
2686 else
2687 fprintf_indent (f, indent, "if ((%s == %s && ! TREE_SIDE_EFFECTS (%s)) "
2688 "|| (operand_equal_p (%s, %s, 0) "
2689 "&& types_match (%s, %s)))\n",
2690 opname, match_opname, opname, opname, match_opname,
2691 opname, match_opname);
2692 fprintf_indent (f, indent + 2, "{\n");
2693 return 1;
2694 }
2695
2696 /* Generate GIMPLE matching code for the decision tree operand. */
2697
2698 unsigned
gen_gimple_expr(FILE * f,int indent)2699 dt_operand::gen_gimple_expr (FILE *f, int indent)
2700 {
2701 expr *e = static_cast<expr *> (op);
2702 id_base *id = e->operation;
2703 unsigned n_ops = e->ops.length ();
2704 unsigned n_braces = 0;
2705
2706 for (unsigned i = 0; i < n_ops; ++i)
2707 {
2708 char child_opname[20];
2709 gen_opname (child_opname, i);
2710
2711 if (id->kind == id_base::CODE)
2712 {
2713 if (e->is_generic
2714 || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2715 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2716 {
2717 /* ??? If this is a memory operation we can't (and should not)
2718 match this. The only sensible operand types are
2719 SSA names and invariants. */
2720 if (e->is_generic)
2721 {
2722 char opname[20];
2723 get_name (opname);
2724 fprintf_indent (f, indent,
2725 "tree %s = TREE_OPERAND (%s, %i);\n",
2726 child_opname, opname, i);
2727 }
2728 else
2729 fprintf_indent (f, indent,
2730 "tree %s = TREE_OPERAND "
2731 "(gimple_assign_rhs1 (def), %i);\n",
2732 child_opname, i);
2733 fprintf_indent (f, indent,
2734 "if ((TREE_CODE (%s) == SSA_NAME\n",
2735 child_opname);
2736 fprintf_indent (f, indent,
2737 " || is_gimple_min_invariant (%s)))\n",
2738 child_opname);
2739 fprintf_indent (f, indent,
2740 " {\n");
2741 indent += 4;
2742 n_braces++;
2743 fprintf_indent (f, indent,
2744 "%s = do_valueize (valueize, %s);\n",
2745 child_opname, child_opname);
2746 continue;
2747 }
2748 else
2749 fprintf_indent (f, indent,
2750 "tree %s = gimple_assign_rhs%u (def);\n",
2751 child_opname, i + 1);
2752 }
2753 else
2754 fprintf_indent (f, indent,
2755 "tree %s = gimple_call_arg (def, %u);\n",
2756 child_opname, i);
2757 fprintf_indent (f, indent,
2758 "%s = do_valueize (valueize, %s);\n",
2759 child_opname, child_opname);
2760 }
2761 /* While the toplevel operands are canonicalized by the caller
2762 after valueizing operands of sub-expressions we have to
2763 re-canonicalize operand order. */
2764 if (operator_id *code = dyn_cast <operator_id *> (id))
2765 {
2766 /* ??? We can't canonicalize tcc_comparison operands here
2767 because that requires changing the comparison code which
2768 we already matched... */
2769 if (commutative_tree_code (code->code)
2770 || commutative_ternary_tree_code (code->code))
2771 {
2772 char child_opname0[20], child_opname1[20];
2773 gen_opname (child_opname0, 0);
2774 gen_opname (child_opname1, 1);
2775 fprintf_indent (f, indent,
2776 "if (tree_swap_operands_p (%s, %s))\n",
2777 child_opname0, child_opname1);
2778 fprintf_indent (f, indent,
2779 " std::swap (%s, %s);\n",
2780 child_opname0, child_opname1);
2781 }
2782 }
2783
2784 return n_braces;
2785 }
2786
2787 /* Generate GENERIC matching code for the decision tree operand. */
2788
2789 unsigned
gen_generic_expr(FILE * f,int indent,const char * opname)2790 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2791 {
2792 expr *e = static_cast<expr *> (op);
2793 unsigned n_ops = e->ops.length ();
2794
2795 for (unsigned i = 0; i < n_ops; ++i)
2796 {
2797 char child_opname[20];
2798 gen_opname (child_opname, i);
2799
2800 if (e->operation->kind == id_base::CODE)
2801 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2802 child_opname, opname, i);
2803 else
2804 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2805 child_opname, opname, i);
2806 }
2807
2808 return 0;
2809 }
2810
2811 /* Generate matching code for the children of the decision tree node. */
2812
2813 void
gen_kids(FILE * f,int indent,bool gimple)2814 dt_node::gen_kids (FILE *f, int indent, bool gimple)
2815 {
2816 auto_vec<dt_operand *> gimple_exprs;
2817 auto_vec<dt_operand *> generic_exprs;
2818 auto_vec<dt_operand *> fns;
2819 auto_vec<dt_operand *> generic_fns;
2820 auto_vec<dt_operand *> preds;
2821 auto_vec<dt_node *> others;
2822
2823 for (unsigned i = 0; i < kids.length (); ++i)
2824 {
2825 if (kids[i]->type == dt_node::DT_OPERAND)
2826 {
2827 dt_operand *op = as_a<dt_operand *> (kids[i]);
2828 if (expr *e = dyn_cast <expr *> (op->op))
2829 {
2830 if (e->ops.length () == 0
2831 && (!gimple || !(*e->operation == CONSTRUCTOR)))
2832 generic_exprs.safe_push (op);
2833 else if (e->operation->kind == id_base::FN)
2834 {
2835 if (gimple)
2836 fns.safe_push (op);
2837 else
2838 generic_fns.safe_push (op);
2839 }
2840 else if (e->operation->kind == id_base::PREDICATE)
2841 preds.safe_push (op);
2842 else
2843 {
2844 if (gimple && !e->is_generic)
2845 gimple_exprs.safe_push (op);
2846 else
2847 generic_exprs.safe_push (op);
2848 }
2849 }
2850 else if (op->op->type == operand::OP_PREDICATE)
2851 others.safe_push (kids[i]);
2852 else
2853 gcc_unreachable ();
2854 }
2855 else if (kids[i]->type == dt_node::DT_SIMPLIFY)
2856 others.safe_push (kids[i]);
2857 else if (kids[i]->type == dt_node::DT_MATCH
2858 || kids[i]->type == dt_node::DT_TRUE)
2859 {
2860 /* A DT_TRUE operand serves as a barrier - generate code now
2861 for what we have collected sofar.
2862 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2863 dependent matches to get out-of-order. Generate code now
2864 for what we have collected sofar. */
2865 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2866 fns, generic_fns, preds, others);
2867 /* And output the true operand itself. */
2868 kids[i]->gen (f, indent, gimple);
2869 gimple_exprs.truncate (0);
2870 generic_exprs.truncate (0);
2871 fns.truncate (0);
2872 generic_fns.truncate (0);
2873 preds.truncate (0);
2874 others.truncate (0);
2875 }
2876 else
2877 gcc_unreachable ();
2878 }
2879
2880 /* Generate code for the remains. */
2881 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2882 fns, generic_fns, preds, others);
2883 }
2884
2885 /* Generate matching code for the children of the decision tree node. */
2886
2887 void
gen_kids_1(FILE * f,int indent,bool gimple,vec<dt_operand * > gimple_exprs,vec<dt_operand * > generic_exprs,vec<dt_operand * > fns,vec<dt_operand * > generic_fns,vec<dt_operand * > preds,vec<dt_node * > others)2888 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2889 vec<dt_operand *> gimple_exprs,
2890 vec<dt_operand *> generic_exprs,
2891 vec<dt_operand *> fns,
2892 vec<dt_operand *> generic_fns,
2893 vec<dt_operand *> preds,
2894 vec<dt_node *> others)
2895 {
2896 char buf[128];
2897 char *kid_opname = buf;
2898
2899 unsigned exprs_len = gimple_exprs.length ();
2900 unsigned gexprs_len = generic_exprs.length ();
2901 unsigned fns_len = fns.length ();
2902 unsigned gfns_len = generic_fns.length ();
2903
2904 if (exprs_len || fns_len || gexprs_len || gfns_len)
2905 {
2906 if (exprs_len)
2907 gimple_exprs[0]->get_name (kid_opname);
2908 else if (fns_len)
2909 fns[0]->get_name (kid_opname);
2910 else if (gfns_len)
2911 generic_fns[0]->get_name (kid_opname);
2912 else
2913 generic_exprs[0]->get_name (kid_opname);
2914
2915 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2916 fprintf_indent (f, indent, " {\n");
2917 indent += 2;
2918 }
2919
2920 if (exprs_len || fns_len)
2921 {
2922 fprintf_indent (f, indent,
2923 "case SSA_NAME:\n");
2924 fprintf_indent (f, indent,
2925 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2926 kid_opname);
2927 fprintf_indent (f, indent,
2928 " {\n");
2929 indent += 6;
2930 if (exprs_len)
2931 {
2932 fprintf_indent (f, indent,
2933 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2934 fprintf_indent (f, indent,
2935 " switch (gimple_assign_rhs_code (def))\n");
2936 indent += 4;
2937 fprintf_indent (f, indent, "{\n");
2938 for (unsigned i = 0; i < exprs_len; ++i)
2939 {
2940 expr *e = as_a <expr *> (gimple_exprs[i]->op);
2941 id_base *op = e->operation;
2942 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2943 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2944 else
2945 fprintf_indent (f, indent, "case %s:\n", op->id);
2946 fprintf_indent (f, indent, " {\n");
2947 gimple_exprs[i]->gen (f, indent + 4, true);
2948 fprintf_indent (f, indent, " break;\n");
2949 fprintf_indent (f, indent, " }\n");
2950 }
2951 fprintf_indent (f, indent, "default:;\n");
2952 fprintf_indent (f, indent, "}\n");
2953 indent -= 4;
2954 }
2955
2956 if (fns_len)
2957 {
2958 fprintf_indent (f, indent,
2959 "%sif (gcall *def = dyn_cast <gcall *>"
2960 " (def_stmt))\n",
2961 exprs_len ? "else " : "");
2962 fprintf_indent (f, indent,
2963 " switch (gimple_call_combined_fn (def))\n");
2964
2965 indent += 4;
2966 fprintf_indent (f, indent, "{\n");
2967 for (unsigned i = 0; i < fns_len; ++i)
2968 {
2969 expr *e = as_a <expr *>(fns[i]->op);
2970 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2971 fprintf_indent (f, indent, " {\n");
2972 fns[i]->gen (f, indent + 4, true);
2973 fprintf_indent (f, indent, " break;\n");
2974 fprintf_indent (f, indent, " }\n");
2975 }
2976
2977 fprintf_indent (f, indent, "default:;\n");
2978 fprintf_indent (f, indent, "}\n");
2979 indent -= 4;
2980 }
2981
2982 indent -= 6;
2983 fprintf_indent (f, indent, " }\n");
2984 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
2985 here rather than in the next loop. */
2986 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2987 {
2988 expr *e = as_a <expr *>(generic_exprs[i]->op);
2989 id_base *op = e->operation;
2990 if (*op == SSA_NAME && (exprs_len || fns_len))
2991 {
2992 fprintf_indent (f, indent + 4, "{\n");
2993 generic_exprs[i]->gen (f, indent + 6, gimple);
2994 fprintf_indent (f, indent + 4, "}\n");
2995 }
2996 }
2997
2998 fprintf_indent (f, indent, " break;\n");
2999 }
3000
3001 for (unsigned i = 0; i < generic_exprs.length (); ++i)
3002 {
3003 expr *e = as_a <expr *>(generic_exprs[i]->op);
3004 id_base *op = e->operation;
3005 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3006 fprintf_indent (f, indent, "CASE_CONVERT:\n");
3007 else if (*op == SSA_NAME && (exprs_len || fns_len))
3008 /* Already handled above. */
3009 continue;
3010 else
3011 fprintf_indent (f, indent, "case %s:\n", op->id);
3012 fprintf_indent (f, indent, " {\n");
3013 generic_exprs[i]->gen (f, indent + 4, gimple);
3014 fprintf_indent (f, indent, " break;\n");
3015 fprintf_indent (f, indent, " }\n");
3016 }
3017
3018 if (gfns_len)
3019 {
3020 fprintf_indent (f, indent,
3021 "case CALL_EXPR:\n");
3022 fprintf_indent (f, indent,
3023 " switch (get_call_combined_fn (%s))\n",
3024 kid_opname);
3025 fprintf_indent (f, indent,
3026 " {\n");
3027 indent += 4;
3028
3029 for (unsigned j = 0; j < generic_fns.length (); ++j)
3030 {
3031 expr *e = as_a <expr *>(generic_fns[j]->op);
3032 gcc_assert (e->operation->kind == id_base::FN);
3033
3034 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
3035 fprintf_indent (f, indent, " {\n");
3036 generic_fns[j]->gen (f, indent + 4, false);
3037 fprintf_indent (f, indent, " break;\n");
3038 fprintf_indent (f, indent, " }\n");
3039 }
3040 fprintf_indent (f, indent, "default:;\n");
3041
3042 indent -= 4;
3043 fprintf_indent (f, indent, " }\n");
3044 fprintf_indent (f, indent, " break;\n");
3045 }
3046
3047 /* Close switch (TREE_CODE ()). */
3048 if (exprs_len || fns_len || gexprs_len || gfns_len)
3049 {
3050 indent -= 4;
3051 fprintf_indent (f, indent, " default:;\n");
3052 fprintf_indent (f, indent, " }\n");
3053 }
3054
3055 for (unsigned i = 0; i < preds.length (); ++i)
3056 {
3057 expr *e = as_a <expr *> (preds[i]->op);
3058 predicate_id *p = as_a <predicate_id *> (e->operation);
3059 preds[i]->get_name (kid_opname);
3060 fprintf_indent (f, indent, "{\n");
3061 indent += 2;
3062 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
3063 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
3064 gimple ? "gimple" : "tree",
3065 p->id, kid_opname, kid_opname,
3066 gimple ? ", valueize" : "");
3067 fprintf_indent (f, indent, " {\n");
3068 for (int j = 0; j < p->nargs; ++j)
3069 {
3070 char child_opname[20];
3071 preds[i]->gen_opname (child_opname, j);
3072 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
3073 child_opname, kid_opname, j);
3074 }
3075 preds[i]->gen_kids (f, indent + 4, gimple);
3076 fprintf (f, "}\n");
3077 indent -= 2;
3078 fprintf_indent (f, indent, "}\n");
3079 }
3080
3081 for (unsigned i = 0; i < others.length (); ++i)
3082 others[i]->gen (f, indent, gimple);
3083 }
3084
3085 /* Generate matching code for the decision tree operand. */
3086
3087 void
gen(FILE * f,int indent,bool gimple)3088 dt_operand::gen (FILE *f, int indent, bool gimple)
3089 {
3090 char opname[20];
3091 get_name (opname);
3092
3093 unsigned n_braces = 0;
3094
3095 if (type == DT_OPERAND)
3096 switch (op->type)
3097 {
3098 case operand::OP_PREDICATE:
3099 n_braces = gen_predicate (f, indent, opname, gimple);
3100 break;
3101
3102 case operand::OP_EXPR:
3103 if (gimple)
3104 n_braces = gen_gimple_expr (f, indent);
3105 else
3106 n_braces = gen_generic_expr (f, indent, opname);
3107 break;
3108
3109 default:
3110 gcc_unreachable ();
3111 }
3112 else if (type == DT_TRUE)
3113 ;
3114 else if (type == DT_MATCH)
3115 n_braces = gen_match_op (f, indent, opname, gimple);
3116 else
3117 gcc_unreachable ();
3118
3119 indent += 4 * n_braces;
3120 gen_kids (f, indent, gimple);
3121
3122 for (unsigned i = 0; i < n_braces; ++i)
3123 {
3124 indent -= 4;
3125 if (indent < 0)
3126 indent = 0;
3127 fprintf_indent (f, indent, " }\n");
3128 }
3129 }
3130
3131
3132 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3133 step of a '(simplify ...)' or '(match ...)'. This handles everything
3134 that is not part of the decision tree (simplify->match).
3135 Main recursive worker. */
3136
3137 void
gen_1(FILE * f,int indent,bool gimple,operand * result)3138 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3139 {
3140 if (result)
3141 {
3142 if (with_expr *w = dyn_cast <with_expr *> (result))
3143 {
3144 fprintf_indent (f, indent, "{\n");
3145 indent += 4;
3146 output_line_directive (f, w->location);
3147 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3148 gen_1 (f, indent, gimple, w->subexpr);
3149 indent -= 4;
3150 fprintf_indent (f, indent, "}\n");
3151 return;
3152 }
3153 else if (if_expr *ife = dyn_cast <if_expr *> (result))
3154 {
3155 output_line_directive (f, ife->location);
3156 fprintf_indent (f, indent, "if (");
3157 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3158 fprintf (f, ")\n");
3159 fprintf_indent (f, indent + 2, "{\n");
3160 indent += 4;
3161 gen_1 (f, indent, gimple, ife->trueexpr);
3162 indent -= 4;
3163 fprintf_indent (f, indent + 2, "}\n");
3164 if (ife->falseexpr)
3165 {
3166 fprintf_indent (f, indent, "else\n");
3167 fprintf_indent (f, indent + 2, "{\n");
3168 indent += 4;
3169 gen_1 (f, indent, gimple, ife->falseexpr);
3170 indent -= 4;
3171 fprintf_indent (f, indent + 2, "}\n");
3172 }
3173 return;
3174 }
3175 }
3176
3177 /* Analyze captures and perform early-outs on the incoming arguments
3178 that cover cases we cannot handle. */
3179 capture_info cinfo (s, result, gimple);
3180 if (s->kind == simplify::SIMPLIFY)
3181 {
3182 if (!gimple)
3183 {
3184 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3185 if (cinfo.force_no_side_effects & (1 << i))
3186 {
3187 fprintf_indent (f, indent,
3188 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3189 i);
3190 if (verbose >= 1)
3191 warning_at (as_a <expr *> (s->match)->ops[i]->location,
3192 "forcing toplevel operand to have no "
3193 "side-effects");
3194 }
3195 for (int i = 0; i <= s->capture_max; ++i)
3196 if (cinfo.info[i].cse_p)
3197 ;
3198 else if (cinfo.info[i].force_no_side_effects_p
3199 && (cinfo.info[i].toplevel_msk
3200 & cinfo.force_no_side_effects) == 0)
3201 {
3202 fprintf_indent (f, indent,
3203 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3204 "return NULL_TREE;\n", i);
3205 if (verbose >= 1)
3206 warning_at (cinfo.info[i].c->location,
3207 "forcing captured operand to have no "
3208 "side-effects");
3209 }
3210 else if ((cinfo.info[i].toplevel_msk
3211 & cinfo.force_no_side_effects) != 0)
3212 /* Mark capture as having no side-effects if we had to verify
3213 that via forced toplevel operand checks. */
3214 cinfo.info[i].force_no_side_effects_p = true;
3215 }
3216 if (gimple)
3217 {
3218 /* Force single-use restriction by only allowing simple
3219 results via setting seq to NULL. */
3220 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
3221 bool first_p = true;
3222 for (int i = 0; i <= s->capture_max; ++i)
3223 if (cinfo.info[i].force_single_use)
3224 {
3225 if (first_p)
3226 {
3227 fprintf_indent (f, indent, "if (lseq\n");
3228 fprintf_indent (f, indent, " && (");
3229 first_p = false;
3230 }
3231 else
3232 {
3233 fprintf (f, "\n");
3234 fprintf_indent (f, indent, " || ");
3235 }
3236 fprintf (f, "!single_use (captures[%d])", i);
3237 }
3238 if (!first_p)
3239 {
3240 fprintf (f, "))\n");
3241 fprintf_indent (f, indent, " lseq = NULL;\n");
3242 }
3243 }
3244 }
3245
3246 fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_FOLDING)) "
3247 "fprintf (dump_file, \"Applying pattern ");
3248 output_line_directive (f,
3249 result ? result->location : s->match->location, true);
3250 fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3251
3252 if (!result)
3253 {
3254 /* If there is no result then this is a predicate implementation. */
3255 fprintf_indent (f, indent, "return true;\n");
3256 }
3257 else if (gimple)
3258 {
3259 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3260 in outermost position). */
3261 if (result->type == operand::OP_EXPR
3262 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
3263 result = as_a <expr *> (result)->ops[0];
3264 if (result->type == operand::OP_EXPR)
3265 {
3266 expr *e = as_a <expr *> (result);
3267 id_base *opr = e->operation;
3268 bool is_predicate = false;
3269 /* When we delay operator substituting during lowering of fors we
3270 make sure that for code-gen purposes the effects of each substitute
3271 are the same. Thus just look at that. */
3272 if (user_id *uid = dyn_cast <user_id *> (opr))
3273 opr = uid->substitutes[0];
3274 else if (is_a <predicate_id *> (opr))
3275 is_predicate = true;
3276 if (!is_predicate)
3277 fprintf_indent (f, indent, "*res_code = %s;\n",
3278 *e->operation == CONVERT_EXPR
3279 ? "NOP_EXPR" : e->operation->id);
3280 for (unsigned j = 0; j < e->ops.length (); ++j)
3281 {
3282 char dest[32];
3283 snprintf (dest, 32, "res_ops[%d]", j);
3284 const char *optype
3285 = get_operand_type (opr, j,
3286 "type", e->expr_type,
3287 j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
3288 /* We need to expand GENERIC conditions we captured from
3289 COND_EXPRs and we need to unshare them when substituting
3290 into COND_EXPRs. */
3291 int cond_handling = 0;
3292 if (!is_predicate)
3293 cond_handling = ((*opr == COND_EXPR
3294 || *opr == VEC_COND_EXPR) && j == 0) ? 1 : 2;
3295 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3296 &cinfo, indexes, cond_handling);
3297 }
3298
3299 /* Re-fold the toplevel result. It's basically an embedded
3300 gimple_build w/o actually building the stmt. */
3301 if (!is_predicate)
3302 fprintf_indent (f, indent,
3303 "gimple_resimplify%d (lseq, res_code, type, "
3304 "res_ops, valueize);\n", e->ops.length ());
3305 }
3306 else if (result->type == operand::OP_CAPTURE
3307 || result->type == operand::OP_C_EXPR)
3308 {
3309 result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
3310 &cinfo, indexes);
3311 fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
3312 if (is_a <capture *> (result)
3313 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3314 {
3315 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3316 with substituting a capture of that. */
3317 fprintf_indent (f, indent,
3318 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3319 fprintf_indent (f, indent,
3320 " {\n");
3321 fprintf_indent (f, indent,
3322 " tree tem = res_ops[0];\n");
3323 fprintf_indent (f, indent,
3324 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3325 fprintf_indent (f, indent,
3326 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3327 fprintf_indent (f, indent,
3328 " }\n");
3329 }
3330 }
3331 else
3332 gcc_unreachable ();
3333 fprintf_indent (f, indent, "return true;\n");
3334 }
3335 else /* GENERIC */
3336 {
3337 bool is_predicate = false;
3338 if (result->type == operand::OP_EXPR)
3339 {
3340 expr *e = as_a <expr *> (result);
3341 id_base *opr = e->operation;
3342 /* When we delay operator substituting during lowering of fors we
3343 make sure that for code-gen purposes the effects of each substitute
3344 are the same. Thus just look at that. */
3345 if (user_id *uid = dyn_cast <user_id *> (opr))
3346 opr = uid->substitutes[0];
3347 else if (is_a <predicate_id *> (opr))
3348 is_predicate = true;
3349 /* Search for captures used multiple times in the result expression
3350 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3351 original expression. */
3352 if (!is_predicate)
3353 for (int i = 0; i < s->capture_max + 1; ++i)
3354 {
3355 if (cinfo.info[i].same_as != (unsigned)i
3356 || cinfo.info[i].cse_p)
3357 continue;
3358 if (cinfo.info[i].result_use_count
3359 > cinfo.info[i].match_use_count)
3360 fprintf_indent (f, indent,
3361 "if (! tree_invariant_p (captures[%d])) "
3362 "return NULL_TREE;\n", i);
3363 }
3364 for (unsigned j = 0; j < e->ops.length (); ++j)
3365 {
3366 char dest[32];
3367 if (is_predicate)
3368 snprintf (dest, 32, "res_ops[%d]", j);
3369 else
3370 {
3371 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3372 snprintf (dest, 32, "res_op%d", j);
3373 }
3374 const char *optype
3375 = get_operand_type (opr, j,
3376 "type", e->expr_type,
3377 j == 0
3378 ? NULL : "TREE_TYPE (res_op0)");
3379 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3380 &cinfo, indexes);
3381 }
3382 if (is_predicate)
3383 fprintf_indent (f, indent, "return true;\n");
3384 else
3385 {
3386 fprintf_indent (f, indent, "tree res;\n");
3387 /* Re-fold the toplevel result. Use non_lvalue to
3388 build NON_LVALUE_EXPRs so they get properly
3389 ignored when in GIMPLE form. */
3390 if (*opr == NON_LVALUE_EXPR)
3391 fprintf_indent (f, indent,
3392 "res = non_lvalue_loc (loc, res_op0);\n");
3393 else
3394 {
3395 if (is_a <operator_id *> (opr))
3396 fprintf_indent (f, indent,
3397 "res = fold_build%d_loc (loc, %s, type",
3398 e->ops.length (),
3399 *e->operation == CONVERT_EXPR
3400 ? "NOP_EXPR" : e->operation->id);
3401 else
3402 fprintf_indent (f, indent,
3403 "res = maybe_build_call_expr_loc (loc, "
3404 "%s, type, %d", e->operation->id,
3405 e->ops.length());
3406 for (unsigned j = 0; j < e->ops.length (); ++j)
3407 fprintf (f, ", res_op%d", j);
3408 fprintf (f, ");\n");
3409 if (!is_a <operator_id *> (opr))
3410 {
3411 fprintf_indent (f, indent, "if (!res)\n");
3412 fprintf_indent (f, indent, " return NULL_TREE;\n");
3413 }
3414 }
3415 }
3416 }
3417 else if (result->type == operand::OP_CAPTURE
3418 || result->type == operand::OP_C_EXPR)
3419
3420 {
3421 fprintf_indent (f, indent, "tree res;\n");
3422 result->gen_transform (f, indent, "res", false, 1, "type",
3423 &cinfo, indexes);
3424 }
3425 else
3426 gcc_unreachable ();
3427 if (!is_predicate)
3428 {
3429 /* Search for captures not used in the result expression and dependent
3430 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3431 for (int i = 0; i < s->capture_max + 1; ++i)
3432 {
3433 if (cinfo.info[i].same_as != (unsigned)i)
3434 continue;
3435 if (!cinfo.info[i].force_no_side_effects_p
3436 && !cinfo.info[i].expr_p
3437 && cinfo.info[i].result_use_count == 0)
3438 {
3439 fprintf_indent (f, indent,
3440 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3441 i);
3442 fprintf_indent (f, indent + 2,
3443 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3444 "fold_ignored_result (captures[%d]), res);\n",
3445 i);
3446 }
3447 }
3448 fprintf_indent (f, indent, "return res;\n");
3449 }
3450 }
3451 }
3452
3453 /* Generate code for the '(if ...)', '(with ..)' and actual transform
3454 step of a '(simplify ...)' or '(match ...)'. This handles everything
3455 that is not part of the decision tree (simplify->match). */
3456
3457 void
gen(FILE * f,int indent,bool gimple)3458 dt_simplify::gen (FILE *f, int indent, bool gimple)
3459 {
3460 fprintf_indent (f, indent, "{\n");
3461 indent += 2;
3462 output_line_directive (f,
3463 s->result ? s->result->location : s->match->location);
3464 if (s->capture_max >= 0)
3465 {
3466 char opname[20];
3467 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3468 s->capture_max + 1, indexes[0]->get_name (opname));
3469
3470 for (int i = 1; i <= s->capture_max; ++i)
3471 {
3472 if (!indexes[i])
3473 break;
3474 fprintf (f, ", %s", indexes[i]->get_name (opname));
3475 }
3476 fprintf (f, " };\n");
3477 }
3478
3479 /* If we have a split-out function for the actual transform, call it. */
3480 if (info && info->fname)
3481 {
3482 if (gimple)
3483 {
3484 fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
3485 "valueize, type, captures", info->fname);
3486 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3487 if (s->for_subst_vec[i].first->used)
3488 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3489 fprintf (f, "))\n");
3490 fprintf_indent (f, indent, " return true;\n");
3491 }
3492 else
3493 {
3494 fprintf_indent (f, indent, "tree res = %s (loc, type",
3495 info->fname);
3496 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3497 fprintf (f, ", op%d", i);
3498 fprintf (f, ", captures");
3499 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3500 {
3501 if (s->for_subst_vec[i].first->used)
3502 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3503 }
3504 fprintf (f, ");\n");
3505 fprintf_indent (f, indent, "if (res) return res;\n");
3506 }
3507 }
3508 else
3509 {
3510 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3511 {
3512 if (! s->for_subst_vec[i].first->used)
3513 continue;
3514 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3515 fprintf_indent (f, indent, "const enum tree_code %s = %s;\n",
3516 s->for_subst_vec[i].first->id,
3517 s->for_subst_vec[i].second->id);
3518 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3519 fprintf_indent (f, indent, "const combined_fn %s = %s;\n",
3520 s->for_subst_vec[i].first->id,
3521 s->for_subst_vec[i].second->id);
3522 else
3523 gcc_unreachable ();
3524 }
3525 gen_1 (f, indent, gimple, s->result);
3526 }
3527
3528 indent -= 2;
3529 fprintf_indent (f, indent, "}\n");
3530 }
3531
3532
3533 /* Hash function for finding equivalent transforms. */
3534
3535 hashval_t
hash(const key_type & v)3536 sinfo_hashmap_traits::hash (const key_type &v)
3537 {
3538 /* Only bother to compare those originating from the same source pattern. */
3539 return v->s->result->location;
3540 }
3541
3542 /* Compare function for finding equivalent transforms. */
3543
3544 static bool
compare_op(operand * o1,simplify * s1,operand * o2,simplify * s2)3545 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3546 {
3547 if (o1->type != o2->type)
3548 return false;
3549
3550 switch (o1->type)
3551 {
3552 case operand::OP_IF:
3553 {
3554 if_expr *if1 = as_a <if_expr *> (o1);
3555 if_expr *if2 = as_a <if_expr *> (o2);
3556 /* ??? Properly compare c-exprs. */
3557 if (if1->cond != if2->cond)
3558 return false;
3559 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3560 return false;
3561 if (if1->falseexpr != if2->falseexpr
3562 || (if1->falseexpr
3563 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3564 return false;
3565 return true;
3566 }
3567 case operand::OP_WITH:
3568 {
3569 with_expr *with1 = as_a <with_expr *> (o1);
3570 with_expr *with2 = as_a <with_expr *> (o2);
3571 if (with1->with != with2->with)
3572 return false;
3573 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3574 }
3575 default:;
3576 }
3577
3578 /* We've hit a result. Time to compare capture-infos - this is required
3579 in addition to the conservative pointer-equivalency of the result IL. */
3580 capture_info cinfo1 (s1, o1, true);
3581 capture_info cinfo2 (s2, o2, true);
3582
3583 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3584 || cinfo1.info.length () != cinfo2.info.length ())
3585 return false;
3586
3587 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3588 {
3589 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3590 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3591 || (cinfo1.info[i].force_no_side_effects_p
3592 != cinfo2.info[i].force_no_side_effects_p)
3593 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3594 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3595 /* toplevel_msk is an optimization */
3596 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3597 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3598 /* the pointer back to the capture is for diagnostics only */)
3599 return false;
3600 }
3601
3602 /* ??? Deep-compare the actual result. */
3603 return o1 == o2;
3604 }
3605
3606 bool
equal_keys(const key_type & v,const key_type & candidate)3607 sinfo_hashmap_traits::equal_keys (const key_type &v,
3608 const key_type &candidate)
3609 {
3610 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3611 }
3612
3613
3614 /* Main entry to generate code for matching GIMPLE IL off the decision
3615 tree. */
3616
3617 void
gen(FILE * f,bool gimple)3618 decision_tree::gen (FILE *f, bool gimple)
3619 {
3620 sinfo_map_t si;
3621
3622 root->analyze (si);
3623
3624 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3625 "a total number of %u nodes\n",
3626 gimple ? "GIMPLE" : "GENERIC",
3627 root->num_leafs, root->max_level, root->total_size);
3628
3629 /* First split out the transform part of equal leafs. */
3630 unsigned rcnt = 0;
3631 unsigned fcnt = 1;
3632 for (sinfo_map_t::iterator iter = si.begin ();
3633 iter != si.end (); ++iter)
3634 {
3635 sinfo *s = (*iter).second;
3636 /* Do not split out single uses. */
3637 if (s->cnt <= 1)
3638 continue;
3639
3640 rcnt += s->cnt - 1;
3641 if (verbose >= 1)
3642 {
3643 fprintf (stderr, "found %u uses of", s->cnt);
3644 output_line_directive (stderr, s->s->s->result->location);
3645 }
3646
3647 /* Generate a split out function with the leaf transform code. */
3648 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3649 fcnt++);
3650 if (gimple)
3651 fprintf (f, "\nstatic bool\n"
3652 "%s (code_helper *res_code, tree *res_ops,\n"
3653 " gimple_seq *seq, tree (*valueize)(tree) "
3654 "ATTRIBUTE_UNUSED,\n"
3655 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3656 "(captures)\n",
3657 s->fname);
3658 else
3659 {
3660 fprintf (f, "\nstatic tree\n"
3661 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3662 (*iter).second->fname);
3663 for (unsigned i = 0;
3664 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3665 fprintf (f, " tree ARG_UNUSED (op%d),", i);
3666 fprintf (f, " tree *captures\n");
3667 }
3668 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3669 {
3670 if (! s->s->s->for_subst_vec[i].first->used)
3671 continue;
3672 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3673 fprintf (f, ", const enum tree_code ARG_UNUSED (%s)",
3674 s->s->s->for_subst_vec[i].first->id);
3675 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3676 fprintf (f, ", const combined_fn ARG_UNUSED (%s)",
3677 s->s->s->for_subst_vec[i].first->id);
3678 }
3679
3680 fprintf (f, ")\n{\n");
3681 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3682 if (gimple)
3683 fprintf (f, " return false;\n");
3684 else
3685 fprintf (f, " return NULL_TREE;\n");
3686 fprintf (f, "}\n");
3687 }
3688 fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3689
3690 for (unsigned n = 1; n <= 3; ++n)
3691 {
3692 /* First generate split-out functions. */
3693 for (unsigned i = 0; i < root->kids.length (); i++)
3694 {
3695 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3696 expr *e = static_cast<expr *>(dop->op);
3697 if (e->ops.length () != n
3698 /* Builtin simplifications are somewhat premature on
3699 GENERIC. The following drops patterns with outermost
3700 calls. It's easy to emit overloads for function code
3701 though if necessary. */
3702 || (!gimple
3703 && e->operation->kind != id_base::CODE))
3704 continue;
3705
3706 if (gimple)
3707 fprintf (f, "\nstatic bool\n"
3708 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3709 " gimple_seq *seq, tree (*valueize)(tree) "
3710 "ATTRIBUTE_UNUSED,\n"
3711 " code_helper ARG_UNUSED (code), tree "
3712 "ARG_UNUSED (type)\n",
3713 e->operation->id);
3714 else
3715 fprintf (f, "\nstatic tree\n"
3716 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3717 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3718 e->operation->id);
3719 for (unsigned i = 0; i < n; ++i)
3720 fprintf (f, ", tree op%d", i);
3721 fprintf (f, ")\n");
3722 fprintf (f, "{\n");
3723 dop->gen_kids (f, 2, gimple);
3724 if (gimple)
3725 fprintf (f, " return false;\n");
3726 else
3727 fprintf (f, " return NULL_TREE;\n");
3728 fprintf (f, "}\n");
3729 }
3730
3731 /* Then generate the main entry with the outermost switch and
3732 tail-calls to the split-out functions. */
3733 if (gimple)
3734 fprintf (f, "\nstatic bool\n"
3735 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3736 " gimple_seq *seq, tree (*valueize)(tree),\n"
3737 " code_helper code, const tree type");
3738 else
3739 fprintf (f, "\ntree\n"
3740 "generic_simplify (location_t loc, enum tree_code code, "
3741 "const tree type ATTRIBUTE_UNUSED");
3742 for (unsigned i = 0; i < n; ++i)
3743 fprintf (f, ", tree op%d", i);
3744 fprintf (f, ")\n");
3745 fprintf (f, "{\n");
3746
3747 if (gimple)
3748 fprintf (f, " switch (code.get_rep())\n"
3749 " {\n");
3750 else
3751 fprintf (f, " switch (code)\n"
3752 " {\n");
3753 for (unsigned i = 0; i < root->kids.length (); i++)
3754 {
3755 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3756 expr *e = static_cast<expr *>(dop->op);
3757 if (e->ops.length () != n
3758 /* Builtin simplifications are somewhat premature on
3759 GENERIC. The following drops patterns with outermost
3760 calls. It's easy to emit overloads for function code
3761 though if necessary. */
3762 || (!gimple
3763 && e->operation->kind != id_base::CODE))
3764 continue;
3765
3766 if (*e->operation == CONVERT_EXPR
3767 || *e->operation == NOP_EXPR)
3768 fprintf (f, " CASE_CONVERT:\n");
3769 else
3770 fprintf (f, " case %s%s:\n",
3771 is_a <fn_id *> (e->operation) ? "-" : "",
3772 e->operation->id);
3773 if (gimple)
3774 fprintf (f, " return gimple_simplify_%s (res_code, res_ops, "
3775 "seq, valueize, code, type", e->operation->id);
3776 else
3777 fprintf (f, " return generic_simplify_%s (loc, code, type",
3778 e->operation->id);
3779 for (unsigned i = 0; i < n; ++i)
3780 fprintf (f, ", op%d", i);
3781 fprintf (f, ");\n");
3782 }
3783 fprintf (f, " default:;\n"
3784 " }\n");
3785
3786 if (gimple)
3787 fprintf (f, " return false;\n");
3788 else
3789 fprintf (f, " return NULL_TREE;\n");
3790 fprintf (f, "}\n");
3791 }
3792 }
3793
3794 /* Output code to implement the predicate P from the decision tree DT. */
3795
3796 void
write_predicate(FILE * f,predicate_id * p,decision_tree & dt,bool gimple)3797 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple)
3798 {
3799 fprintf (f, "\nbool\n"
3800 "%s%s (tree t%s%s)\n"
3801 "{\n", gimple ? "gimple_" : "tree_", p->id,
3802 p->nargs > 0 ? ", tree *res_ops" : "",
3803 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : "");
3804 /* Conveniently make 'type' available. */
3805 fprintf_indent (f, 2, "const tree type = TREE_TYPE (t);\n");
3806
3807 if (!gimple)
3808 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n");
3809 dt.root->gen_kids (f, 2, gimple);
3810
3811 fprintf_indent (f, 2, "return false;\n"
3812 "}\n");
3813 }
3814
3815 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */
3816
3817 static void
write_header(FILE * f,const char * head)3818 write_header (FILE *f, const char *head)
3819 {
3820 fprintf (f, "/* Generated automatically by the program `genmatch' from\n");
3821 fprintf (f, " a IL pattern matching and simplification description. */\n");
3822
3823 /* Include the header instead of writing it awkwardly quoted here. */
3824 fprintf (f, "\n#include \"%s\"\n", head);
3825 }
3826
3827
3828
3829 /* AST parsing. */
3830
3831 class parser
3832 {
3833 public:
3834 parser (cpp_reader *);
3835
3836 private:
3837 const cpp_token *next ();
3838 const cpp_token *peek (unsigned = 1);
3839 const cpp_token *peek_ident (const char * = NULL, unsigned = 1);
3840 const cpp_token *expect (enum cpp_ttype);
3841 const cpp_token *eat_token (enum cpp_ttype);
3842 const char *get_string ();
3843 const char *get_ident ();
3844 const cpp_token *eat_ident (const char *);
3845 const char *get_number ();
3846
3847 unsigned get_internal_capture_id ();
3848
3849 id_base *parse_operation ();
3850 operand *parse_capture (operand *, bool);
3851 operand *parse_expr ();
3852 c_expr *parse_c_expr (cpp_ttype);
3853 operand *parse_op ();
3854
3855 void record_operlist (source_location, user_id *);
3856
3857 void parse_pattern ();
3858 operand *parse_result (operand *, predicate_id *);
3859 void push_simplify (simplify::simplify_kind,
3860 vec<simplify *>&, operand *, operand *);
3861 void parse_simplify (simplify::simplify_kind,
3862 vec<simplify *>&, predicate_id *, operand *);
3863 void parse_for (source_location);
3864 void parse_if (source_location);
3865 void parse_predicates (source_location);
3866 void parse_operator_list (source_location);
3867
3868 void finish_match_operand (operand *);
3869
3870 cpp_reader *r;
3871 vec<c_expr *> active_ifs;
3872 vec<vec<user_id *> > active_fors;
3873 hash_set<user_id *> *oper_lists_set;
3874 vec<user_id *> oper_lists;
3875
3876 cid_map_t *capture_ids;
3877 unsigned last_id;
3878
3879 public:
3880 vec<simplify *> simplifiers;
3881 vec<predicate_id *> user_predicates;
3882 bool parsing_match_operand;
3883 };
3884
3885 /* Lexing helpers. */
3886
3887 /* Read the next non-whitespace token from R. */
3888
3889 const cpp_token *
next()3890 parser::next ()
3891 {
3892 const cpp_token *token;
3893 do
3894 {
3895 token = cpp_get_token (r);
3896 }
3897 while (token->type == CPP_PADDING);
3898 return token;
3899 }
3900
3901 /* Peek at the next non-whitespace token from R. */
3902
3903 const cpp_token *
peek(unsigned num)3904 parser::peek (unsigned num)
3905 {
3906 const cpp_token *token;
3907 unsigned i = 0;
3908 do
3909 {
3910 token = cpp_peek_token (r, i++);
3911 }
3912 while (token->type == CPP_PADDING
3913 || (--num > 0));
3914 /* If we peek at EOF this is a fatal error as it leaves the
3915 cpp_reader in unusable state. Assume we really wanted a
3916 token and thus this EOF is unexpected. */
3917 if (token->type == CPP_EOF)
3918 fatal_at (token, "unexpected end of file");
3919 return token;
3920 }
3921
3922 /* Peek at the next identifier token (or return NULL if the next
3923 token is not an identifier or equal to ID if supplied). */
3924
3925 const cpp_token *
peek_ident(const char * id,unsigned num)3926 parser::peek_ident (const char *id, unsigned num)
3927 {
3928 const cpp_token *token = peek (num);
3929 if (token->type != CPP_NAME)
3930 return 0;
3931
3932 if (id == 0)
3933 return token;
3934
3935 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str;
3936 if (strcmp (id, t) == 0)
3937 return token;
3938
3939 return 0;
3940 }
3941
3942 /* Read the next token from R and assert it is of type TK. */
3943
3944 const cpp_token *
expect(enum cpp_ttype tk)3945 parser::expect (enum cpp_ttype tk)
3946 {
3947 const cpp_token *token = next ();
3948 if (token->type != tk)
3949 fatal_at (token, "expected %s, got %s",
3950 cpp_type2name (tk, 0), cpp_type2name (token->type, 0));
3951
3952 return token;
3953 }
3954
3955 /* Consume the next token from R and assert it is of type TK. */
3956
3957 const cpp_token *
eat_token(enum cpp_ttype tk)3958 parser::eat_token (enum cpp_ttype tk)
3959 {
3960 return expect (tk);
3961 }
3962
3963 /* Read the next token from R and assert it is of type CPP_STRING and
3964 return its value. */
3965
3966 const char *
get_string()3967 parser::get_string ()
3968 {
3969 const cpp_token *token = expect (CPP_STRING);
3970 return (const char *)token->val.str.text;
3971 }
3972
3973 /* Read the next token from R and assert it is of type CPP_NAME and
3974 return its value. */
3975
3976 const char *
get_ident()3977 parser::get_ident ()
3978 {
3979 const cpp_token *token = expect (CPP_NAME);
3980 return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str;
3981 }
3982
3983 /* Eat an identifier token with value S from R. */
3984
3985 const cpp_token *
eat_ident(const char * s)3986 parser::eat_ident (const char *s)
3987 {
3988 const cpp_token *token = peek ();
3989 const char *t = get_ident ();
3990 if (strcmp (s, t) != 0)
3991 fatal_at (token, "expected '%s' got '%s'\n", s, t);
3992 return token;
3993 }
3994
3995 /* Read the next token from R and assert it is of type CPP_NUMBER and
3996 return its value. */
3997
3998 const char *
get_number()3999 parser::get_number ()
4000 {
4001 const cpp_token *token = expect (CPP_NUMBER);
4002 return (const char *)token->val.str.text;
4003 }
4004
4005 /* Return a capture ID that can be used internally. */
4006
4007 unsigned
get_internal_capture_id()4008 parser::get_internal_capture_id ()
4009 {
4010 unsigned newid = capture_ids->elements ();
4011 /* Big enough for a 32-bit UINT_MAX plus prefix. */
4012 char id[13];
4013 bool existed;
4014 sprintf (id, "__%u", newid);
4015 capture_ids->get_or_insert (xstrdup (id), &existed);
4016 if (existed)
4017 fatal ("reserved capture id '%s' already used", id);
4018 return newid;
4019 }
4020
4021 /* Record an operator-list use for transparent for handling. */
4022
4023 void
record_operlist(source_location loc,user_id * p)4024 parser::record_operlist (source_location loc, user_id *p)
4025 {
4026 if (!oper_lists_set->add (p))
4027 {
4028 if (!oper_lists.is_empty ()
4029 && oper_lists[0]->substitutes.length () != p->substitutes.length ())
4030 fatal_at (loc, "User-defined operator list does not have the "
4031 "same number of entries as others used in the pattern");
4032 oper_lists.safe_push (p);
4033 }
4034 }
4035
4036 /* Parse the operator ID, special-casing convert?, convert1? and
4037 convert2? */
4038
4039 id_base *
parse_operation()4040 parser::parse_operation ()
4041 {
4042 const cpp_token *id_tok = peek ();
4043 const char *id = get_ident ();
4044 const cpp_token *token = peek ();
4045 if (strcmp (id, "convert0") == 0)
4046 fatal_at (id_tok, "use 'convert?' here");
4047 else if (strcmp (id, "view_convert0") == 0)
4048 fatal_at (id_tok, "use 'view_convert?' here");
4049 if (token->type == CPP_QUERY
4050 && !(token->flags & PREV_WHITE))
4051 {
4052 if (strcmp (id, "convert") == 0)
4053 id = "convert0";
4054 else if (strcmp (id, "convert1") == 0)
4055 ;
4056 else if (strcmp (id, "convert2") == 0)
4057 ;
4058 else if (strcmp (id, "view_convert") == 0)
4059 id = "view_convert0";
4060 else if (strcmp (id, "view_convert1") == 0)
4061 ;
4062 else if (strcmp (id, "view_convert2") == 0)
4063 ;
4064 else
4065 fatal_at (id_tok, "non-convert operator conditionalized");
4066
4067 if (!parsing_match_operand)
4068 fatal_at (id_tok, "conditional convert can only be used in "
4069 "match expression");
4070 eat_token (CPP_QUERY);
4071 }
4072 else if (strcmp (id, "convert1") == 0
4073 || strcmp (id, "convert2") == 0
4074 || strcmp (id, "view_convert1") == 0
4075 || strcmp (id, "view_convert2") == 0)
4076 fatal_at (id_tok, "expected '?' after conditional operator");
4077 id_base *op = get_operator (id);
4078 if (!op)
4079 fatal_at (id_tok, "unknown operator %s", id);
4080
4081 user_id *p = dyn_cast<user_id *> (op);
4082 if (p && p->is_oper_list)
4083 {
4084 if (active_fors.length() == 0)
4085 record_operlist (id_tok->src_loc, p);
4086 else
4087 fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id);
4088 }
4089 return op;
4090 }
4091
4092 /* Parse a capture.
4093 capture = '@'<number> */
4094
4095 struct operand *
parse_capture(operand * op,bool require_existing)4096 parser::parse_capture (operand *op, bool require_existing)
4097 {
4098 source_location src_loc = eat_token (CPP_ATSIGN)->src_loc;
4099 const cpp_token *token = peek ();
4100 const char *id = NULL;
4101 bool value_match = false;
4102 /* For matches parse @@ as a value-match denoting the prevailing operand. */
4103 if (token->type == CPP_ATSIGN
4104 && ! (token->flags & PREV_WHITE)
4105 && parsing_match_operand)
4106 {
4107 eat_token (CPP_ATSIGN);
4108 token = peek ();
4109 value_match = true;
4110 }
4111 if (token->type == CPP_NUMBER)
4112 id = get_number ();
4113 else if (token->type == CPP_NAME)
4114 id = get_ident ();
4115 else
4116 fatal_at (token, "expected number or identifier");
4117 unsigned next_id = capture_ids->elements ();
4118 bool existed;
4119 unsigned &num = capture_ids->get_or_insert (id, &existed);
4120 if (!existed)
4121 {
4122 if (require_existing)
4123 fatal_at (src_loc, "unknown capture id");
4124 num = next_id;
4125 }
4126 return new capture (src_loc, num, op, value_match);
4127 }
4128
4129 /* Parse an expression
4130 expr = '(' <operation>[capture][flag][type] <operand>... ')' */
4131
4132 struct operand *
parse_expr()4133 parser::parse_expr ()
4134 {
4135 const cpp_token *token = peek ();
4136 expr *e = new expr (parse_operation (), token->src_loc);
4137 token = peek ();
4138 operand *op;
4139 bool is_commutative = false;
4140 bool force_capture = false;
4141 const char *expr_type = NULL;
4142
4143 if (token->type == CPP_COLON
4144 && !(token->flags & PREV_WHITE))
4145 {
4146 eat_token (CPP_COLON);
4147 token = peek ();
4148 if (token->type == CPP_NAME
4149 && !(token->flags & PREV_WHITE))
4150 {
4151 const char *s = get_ident ();
4152 if (!parsing_match_operand)
4153 expr_type = s;
4154 else
4155 {
4156 const char *sp = s;
4157 while (*sp)
4158 {
4159 if (*sp == 'c')
4160 {
4161 if (operator_id *p
4162 = dyn_cast<operator_id *> (e->operation))
4163 {
4164 if (!commutative_tree_code (p->code)
4165 && !comparison_code_p (p->code))
4166 fatal_at (token, "operation is not commutative");
4167 }
4168 else if (user_id *p = dyn_cast<user_id *> (e->operation))
4169 for (unsigned i = 0;
4170 i < p->substitutes.length (); ++i)
4171 {
4172 if (operator_id *q
4173 = dyn_cast<operator_id *> (p->substitutes[i]))
4174 {
4175 if (!commutative_tree_code (q->code)
4176 && !comparison_code_p (q->code))
4177 fatal_at (token, "operation %s is not "
4178 "commutative", q->id);
4179 }
4180 }
4181 is_commutative = true;
4182 }
4183 else if (*sp == 'C')
4184 is_commutative = true;
4185 else if (*sp == 's')
4186 {
4187 e->force_single_use = true;
4188 force_capture = true;
4189 }
4190 else
4191 fatal_at (token, "flag %c not recognized", *sp);
4192 sp++;
4193 }
4194 }
4195 token = peek ();
4196 }
4197 else
4198 fatal_at (token, "expected flag or type specifying identifier");
4199 }
4200
4201 if (token->type == CPP_ATSIGN
4202 && !(token->flags & PREV_WHITE))
4203 op = parse_capture (e, false);
4204 else if (force_capture)
4205 {
4206 unsigned num = get_internal_capture_id ();
4207 op = new capture (token->src_loc, num, e, false);
4208 }
4209 else
4210 op = e;
4211 do
4212 {
4213 const cpp_token *token = peek ();
4214 if (token->type == CPP_CLOSE_PAREN)
4215 {
4216 if (e->operation->nargs != -1
4217 && e->operation->nargs != (int) e->ops.length ())
4218 fatal_at (token, "'%s' expects %u operands, not %u",
4219 e->operation->id, e->operation->nargs, e->ops.length ());
4220 if (is_commutative)
4221 {
4222 if (e->ops.length () == 2)
4223 e->is_commutative = true;
4224 else
4225 fatal_at (token, "only binary operators or function with "
4226 "two arguments can be marked commutative");
4227 }
4228 e->expr_type = expr_type;
4229 return op;
4230 }
4231 else if (!(token->flags & PREV_WHITE))
4232 fatal_at (token, "expected expression operand");
4233
4234 e->append_op (parse_op ());
4235 }
4236 while (1);
4237 }
4238
4239 /* Lex native C code delimited by START recording the preprocessing tokens
4240 for later processing.
4241 c_expr = ('{'|'(') <pp token>... ('}'|')') */
4242
4243 c_expr *
parse_c_expr(cpp_ttype start)4244 parser::parse_c_expr (cpp_ttype start)
4245 {
4246 const cpp_token *token;
4247 cpp_ttype end;
4248 unsigned opencnt;
4249 vec<cpp_token> code = vNULL;
4250 unsigned nr_stmts = 0;
4251 source_location loc = eat_token (start)->src_loc;
4252 if (start == CPP_OPEN_PAREN)
4253 end = CPP_CLOSE_PAREN;
4254 else if (start == CPP_OPEN_BRACE)
4255 end = CPP_CLOSE_BRACE;
4256 else
4257 gcc_unreachable ();
4258 opencnt = 1;
4259 do
4260 {
4261 token = next ();
4262
4263 /* Count brace pairs to find the end of the expr to match. */
4264 if (token->type == start)
4265 opencnt++;
4266 else if (token->type == end
4267 && --opencnt == 0)
4268 break;
4269 else if (token->type == CPP_EOF)
4270 fatal_at (token, "unexpected end of file");
4271
4272 /* This is a lame way of counting the number of statements. */
4273 if (token->type == CPP_SEMICOLON)
4274 nr_stmts++;
4275
4276 /* If this is possibly a user-defined identifier mark it used. */
4277 if (token->type == CPP_NAME)
4278 {
4279 id_base *idb = get_operator ((const char *)CPP_HASHNODE
4280 (token->val.node.node)->ident.str);
4281 user_id *p;
4282 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list)
4283 record_operlist (token->src_loc, p);
4284 }
4285
4286 /* Record the token. */
4287 code.safe_push (*token);
4288 }
4289 while (1);
4290 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids);
4291 }
4292
4293 /* Parse an operand which is either an expression, a predicate or
4294 a standalone capture.
4295 op = predicate | expr | c_expr | capture */
4296
4297 struct operand *
parse_op()4298 parser::parse_op ()
4299 {
4300 const cpp_token *token = peek ();
4301 struct operand *op = NULL;
4302 if (token->type == CPP_OPEN_PAREN)
4303 {
4304 eat_token (CPP_OPEN_PAREN);
4305 op = parse_expr ();
4306 eat_token (CPP_CLOSE_PAREN);
4307 }
4308 else if (token->type == CPP_OPEN_BRACE)
4309 {
4310 op = parse_c_expr (CPP_OPEN_BRACE);
4311 }
4312 else
4313 {
4314 /* Remaining ops are either empty or predicates */
4315 if (token->type == CPP_NAME)
4316 {
4317 const char *id = get_ident ();
4318 id_base *opr = get_operator (id);
4319 if (!opr)
4320 fatal_at (token, "expected predicate name");
4321 if (operator_id *code = dyn_cast <operator_id *> (opr))
4322 {
4323 if (code->nargs != 0)
4324 fatal_at (token, "using an operator with operands as predicate");
4325 /* Parse the zero-operand operator "predicates" as
4326 expression. */
4327 op = new expr (opr, token->src_loc);
4328 }
4329 else if (user_id *code = dyn_cast <user_id *> (opr))
4330 {
4331 if (code->nargs != 0)
4332 fatal_at (token, "using an operator with operands as predicate");
4333 /* Parse the zero-operand operator "predicates" as
4334 expression. */
4335 op = new expr (opr, token->src_loc);
4336 }
4337 else if (predicate_id *p = dyn_cast <predicate_id *> (opr))
4338 op = new predicate (p, token->src_loc);
4339 else
4340 fatal_at (token, "using an unsupported operator as predicate");
4341 if (!parsing_match_operand)
4342 fatal_at (token, "predicates are only allowed in match expression");
4343 token = peek ();
4344 if (token->flags & PREV_WHITE)
4345 return op;
4346 }
4347 else if (token->type != CPP_COLON
4348 && token->type != CPP_ATSIGN)
4349 fatal_at (token, "expected expression or predicate");
4350 /* optionally followed by a capture and a predicate. */
4351 if (token->type == CPP_COLON)
4352 fatal_at (token, "not implemented: predicate on leaf operand");
4353 if (token->type == CPP_ATSIGN)
4354 op = parse_capture (op, !parsing_match_operand);
4355 }
4356
4357 return op;
4358 }
4359
4360 /* Create a new simplify from the current parsing state and MATCH,
4361 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */
4362
4363 void
push_simplify(simplify::simplify_kind kind,vec<simplify * > & simplifiers,operand * match,operand * result)4364 parser::push_simplify (simplify::simplify_kind kind,
4365 vec<simplify *>& simplifiers,
4366 operand *match, operand *result)
4367 {
4368 /* Build and push a temporary for operator list uses in expressions. */
4369 if (!oper_lists.is_empty ())
4370 active_fors.safe_push (oper_lists);
4371
4372 simplifiers.safe_push
4373 (new simplify (kind, last_id++, match, result,
4374 active_fors.copy (), capture_ids));
4375
4376 if (!oper_lists.is_empty ())
4377 active_fors.pop ();
4378 }
4379
4380 /* Parse
4381 <result-op> = <op> | <if> | <with>
4382 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')'
4383 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')'
4384 and return it. */
4385
4386 operand *
parse_result(operand * result,predicate_id * matcher)4387 parser::parse_result (operand *result, predicate_id *matcher)
4388 {
4389 const cpp_token *token = peek ();
4390 if (token->type != CPP_OPEN_PAREN)
4391 return parse_op ();
4392
4393 eat_token (CPP_OPEN_PAREN);
4394 if (peek_ident ("if"))
4395 {
4396 eat_ident ("if");
4397 if_expr *ife = new if_expr (token->src_loc);
4398 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4399 if (peek ()->type == CPP_OPEN_PAREN)
4400 {
4401 ife->trueexpr = parse_result (result, matcher);
4402 if (peek ()->type == CPP_OPEN_PAREN)
4403 ife->falseexpr = parse_result (result, matcher);
4404 else if (peek ()->type != CPP_CLOSE_PAREN)
4405 ife->falseexpr = parse_op ();
4406 }
4407 else if (peek ()->type != CPP_CLOSE_PAREN)
4408 {
4409 ife->trueexpr = parse_op ();
4410 if (peek ()->type == CPP_OPEN_PAREN)
4411 ife->falseexpr = parse_result (result, matcher);
4412 else if (peek ()->type != CPP_CLOSE_PAREN)
4413 ife->falseexpr = parse_op ();
4414 }
4415 /* If this if is immediately closed then it contains a
4416 manual matcher or is part of a predicate definition. */
4417 else /* if (peek ()->type == CPP_CLOSE_PAREN) */
4418 {
4419 if (!matcher)
4420 fatal_at (peek (), "manual transform not implemented");
4421 ife->trueexpr = result;
4422 }
4423 eat_token (CPP_CLOSE_PAREN);
4424 return ife;
4425 }
4426 else if (peek_ident ("with"))
4427 {
4428 eat_ident ("with");
4429 with_expr *withe = new with_expr (token->src_loc);
4430 /* Parse (with c-expr expr) as (if-with (true) expr). */
4431 withe->with = parse_c_expr (CPP_OPEN_BRACE);
4432 withe->with->nr_stmts = 0;
4433 withe->subexpr = parse_result (result, matcher);
4434 eat_token (CPP_CLOSE_PAREN);
4435 return withe;
4436 }
4437 else if (peek_ident ("switch"))
4438 {
4439 token = eat_ident ("switch");
4440 source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4441 eat_ident ("if");
4442 if_expr *ife = new if_expr (ifloc);
4443 operand *res = ife;
4444 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4445 if (peek ()->type == CPP_OPEN_PAREN)
4446 ife->trueexpr = parse_result (result, matcher);
4447 else
4448 ife->trueexpr = parse_op ();
4449 eat_token (CPP_CLOSE_PAREN);
4450 if (peek ()->type != CPP_OPEN_PAREN
4451 || !peek_ident ("if", 2))
4452 fatal_at (token, "switch can be implemented with a single if");
4453 while (peek ()->type != CPP_CLOSE_PAREN)
4454 {
4455 if (peek ()->type == CPP_OPEN_PAREN)
4456 {
4457 if (peek_ident ("if", 2))
4458 {
4459 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc;
4460 eat_ident ("if");
4461 ife->falseexpr = new if_expr (ifloc);
4462 ife = as_a <if_expr *> (ife->falseexpr);
4463 ife->cond = parse_c_expr (CPP_OPEN_PAREN);
4464 if (peek ()->type == CPP_OPEN_PAREN)
4465 ife->trueexpr = parse_result (result, matcher);
4466 else
4467 ife->trueexpr = parse_op ();
4468 eat_token (CPP_CLOSE_PAREN);
4469 }
4470 else
4471 {
4472 /* switch default clause */
4473 ife->falseexpr = parse_result (result, matcher);
4474 eat_token (CPP_CLOSE_PAREN);
4475 return res;
4476 }
4477 }
4478 else
4479 {
4480 /* switch default clause */
4481 ife->falseexpr = parse_op ();
4482 eat_token (CPP_CLOSE_PAREN);
4483 return res;
4484 }
4485 }
4486 eat_token (CPP_CLOSE_PAREN);
4487 return res;
4488 }
4489 else
4490 {
4491 operand *op = result;
4492 if (!matcher)
4493 op = parse_expr ();
4494 eat_token (CPP_CLOSE_PAREN);
4495 return op;
4496 }
4497 }
4498
4499 /* Parse
4500 simplify = 'simplify' <expr> <result-op>
4501 or
4502 match = 'match' <ident> <expr> [<result-op>]
4503 and fill SIMPLIFIERS with the results. */
4504
4505 void
parse_simplify(simplify::simplify_kind kind,vec<simplify * > & simplifiers,predicate_id * matcher,operand * result)4506 parser::parse_simplify (simplify::simplify_kind kind,
4507 vec<simplify *>& simplifiers, predicate_id *matcher,
4508 operand *result)
4509 {
4510 /* Reset the capture map. */
4511 if (!capture_ids)
4512 capture_ids = new cid_map_t;
4513 /* Reset oper_lists and set. */
4514 hash_set <user_id *> olist;
4515 oper_lists_set = &olist;
4516 oper_lists = vNULL;
4517
4518 const cpp_token *loc = peek ();
4519 parsing_match_operand = true;
4520 struct operand *match = parse_op ();
4521 finish_match_operand (match);
4522 parsing_match_operand = false;
4523 if (match->type == operand::OP_CAPTURE && !matcher)
4524 fatal_at (loc, "outermost expression cannot be captured");
4525 if (match->type == operand::OP_EXPR
4526 && is_a <predicate_id *> (as_a <expr *> (match)->operation))
4527 fatal_at (loc, "outermost expression cannot be a predicate");
4528
4529 /* Splice active_ifs onto result and continue parsing the
4530 "then" expr. */
4531 if_expr *active_if = NULL;
4532 for (int i = active_ifs.length (); i > 0; --i)
4533 {
4534 if_expr *ifc = new if_expr (active_ifs[i-1]->location);
4535 ifc->cond = active_ifs[i-1];
4536 ifc->trueexpr = active_if;
4537 active_if = ifc;
4538 }
4539 if_expr *outermost_if = active_if;
4540 while (active_if && active_if->trueexpr)
4541 active_if = as_a <if_expr *> (active_if->trueexpr);
4542
4543 const cpp_token *token = peek ();
4544
4545 /* If this if is immediately closed then it is part of a predicate
4546 definition. Push it. */
4547 if (token->type == CPP_CLOSE_PAREN)
4548 {
4549 if (!matcher)
4550 fatal_at (token, "expected transform expression");
4551 if (active_if)
4552 {
4553 active_if->trueexpr = result;
4554 result = outermost_if;
4555 }
4556 push_simplify (kind, simplifiers, match, result);
4557 return;
4558 }
4559
4560 operand *tem = parse_result (result, matcher);
4561 if (active_if)
4562 {
4563 active_if->trueexpr = tem;
4564 result = outermost_if;
4565 }
4566 else
4567 result = tem;
4568
4569 push_simplify (kind, simplifiers, match, result);
4570 }
4571
4572 /* Parsing of the outer control structures. */
4573
4574 /* Parse a for expression
4575 for = '(' 'for' <subst>... <pattern> ')'
4576 subst = <ident> '(' <ident>... ')' */
4577
4578 void
parse_for(source_location)4579 parser::parse_for (source_location)
4580 {
4581 auto_vec<const cpp_token *> user_id_tokens;
4582 vec<user_id *> user_ids = vNULL;
4583 const cpp_token *token;
4584 unsigned min_n_opers = 0, max_n_opers = 0;
4585
4586 while (1)
4587 {
4588 token = peek ();
4589 if (token->type != CPP_NAME)
4590 break;
4591
4592 /* Insert the user defined operators into the operator hash. */
4593 const char *id = get_ident ();
4594 if (get_operator (id, true) != NULL)
4595 fatal_at (token, "operator already defined");
4596 user_id *op = new user_id (id);
4597 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4598 *slot = op;
4599 user_ids.safe_push (op);
4600 user_id_tokens.safe_push (token);
4601
4602 eat_token (CPP_OPEN_PAREN);
4603
4604 int arity = -1;
4605 while ((token = peek_ident ()) != 0)
4606 {
4607 const char *oper = get_ident ();
4608 id_base *idb = get_operator (oper, true);
4609 if (idb == NULL)
4610 fatal_at (token, "no such operator '%s'", oper);
4611 if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2
4612 || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1
4613 || *idb == VIEW_CONVERT2)
4614 fatal_at (token, "conditional operators cannot be used inside for");
4615
4616 if (arity == -1)
4617 arity = idb->nargs;
4618 else if (idb->nargs == -1)
4619 ;
4620 else if (idb->nargs != arity)
4621 fatal_at (token, "operator '%s' with arity %d does not match "
4622 "others with arity %d", oper, idb->nargs, arity);
4623
4624 user_id *p = dyn_cast<user_id *> (idb);
4625 if (p)
4626 {
4627 if (p->is_oper_list)
4628 op->substitutes.safe_splice (p->substitutes);
4629 else
4630 fatal_at (token, "iterator cannot be used as operator-list");
4631 }
4632 else
4633 op->substitutes.safe_push (idb);
4634 }
4635 op->nargs = arity;
4636 token = expect (CPP_CLOSE_PAREN);
4637
4638 unsigned nsubstitutes = op->substitutes.length ();
4639 if (nsubstitutes == 0)
4640 fatal_at (token, "A user-defined operator must have at least "
4641 "one substitution");
4642 if (max_n_opers == 0)
4643 {
4644 min_n_opers = nsubstitutes;
4645 max_n_opers = nsubstitutes;
4646 }
4647 else
4648 {
4649 if (nsubstitutes % min_n_opers != 0
4650 && min_n_opers % nsubstitutes != 0)
4651 fatal_at (token, "All user-defined identifiers must have a "
4652 "multiple number of operator substitutions of the "
4653 "smallest number of substitutions");
4654 if (nsubstitutes < min_n_opers)
4655 min_n_opers = nsubstitutes;
4656 else if (nsubstitutes > max_n_opers)
4657 max_n_opers = nsubstitutes;
4658 }
4659 }
4660
4661 unsigned n_ids = user_ids.length ();
4662 if (n_ids == 0)
4663 fatal_at (token, "for requires at least one user-defined identifier");
4664
4665 token = peek ();
4666 if (token->type == CPP_CLOSE_PAREN)
4667 fatal_at (token, "no pattern defined in for");
4668
4669 active_fors.safe_push (user_ids);
4670 while (1)
4671 {
4672 token = peek ();
4673 if (token->type == CPP_CLOSE_PAREN)
4674 break;
4675 parse_pattern ();
4676 }
4677 active_fors.pop ();
4678
4679 /* Remove user-defined operators from the hash again. */
4680 for (unsigned i = 0; i < user_ids.length (); ++i)
4681 {
4682 if (!user_ids[i]->used)
4683 warning_at (user_id_tokens[i],
4684 "operator %s defined but not used", user_ids[i]->id);
4685 operators->remove_elt (user_ids[i]);
4686 }
4687 }
4688
4689 /* Parse an identifier associated with a list of operators.
4690 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */
4691
4692 void
parse_operator_list(source_location)4693 parser::parse_operator_list (source_location)
4694 {
4695 const cpp_token *token = peek ();
4696 const char *id = get_ident ();
4697
4698 if (get_operator (id, true) != 0)
4699 fatal_at (token, "operator %s already defined", id);
4700
4701 user_id *op = new user_id (id, true);
4702 int arity = -1;
4703
4704 while ((token = peek_ident ()) != 0)
4705 {
4706 token = peek ();
4707 const char *oper = get_ident ();
4708 id_base *idb = get_operator (oper, true);
4709
4710 if (idb == 0)
4711 fatal_at (token, "no such operator '%s'", oper);
4712
4713 if (arity == -1)
4714 arity = idb->nargs;
4715 else if (idb->nargs == -1)
4716 ;
4717 else if (arity != idb->nargs)
4718 fatal_at (token, "operator '%s' with arity %d does not match "
4719 "others with arity %d", oper, idb->nargs, arity);
4720
4721 /* We allow composition of multiple operator lists. */
4722 if (user_id *p = dyn_cast<user_id *> (idb))
4723 op->substitutes.safe_splice (p->substitutes);
4724 else
4725 op->substitutes.safe_push (idb);
4726 }
4727
4728 // Check that there is no junk after id-list
4729 token = peek();
4730 if (token->type != CPP_CLOSE_PAREN)
4731 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0));
4732
4733 if (op->substitutes.length () == 0)
4734 fatal_at (token, "operator-list cannot be empty");
4735
4736 op->nargs = arity;
4737 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
4738 *slot = op;
4739 }
4740
4741 /* Parse an outer if expression.
4742 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */
4743
4744 void
parse_if(source_location)4745 parser::parse_if (source_location)
4746 {
4747 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN);
4748
4749 const cpp_token *token = peek ();
4750 if (token->type == CPP_CLOSE_PAREN)
4751 fatal_at (token, "no pattern defined in if");
4752
4753 active_ifs.safe_push (ifexpr);
4754 while (1)
4755 {
4756 const cpp_token *token = peek ();
4757 if (token->type == CPP_CLOSE_PAREN)
4758 break;
4759
4760 parse_pattern ();
4761 }
4762 active_ifs.pop ();
4763 }
4764
4765 /* Parse a list of predefined predicate identifiers.
4766 preds = '(' 'define_predicates' <ident>... ')' */
4767
4768 void
parse_predicates(source_location)4769 parser::parse_predicates (source_location)
4770 {
4771 do
4772 {
4773 const cpp_token *token = peek ();
4774 if (token->type != CPP_NAME)
4775 break;
4776
4777 add_predicate (get_ident ());
4778 }
4779 while (1);
4780 }
4781
4782 /* Parse outer control structures.
4783 pattern = <preds>|<for>|<if>|<simplify>|<match> */
4784
4785 void
parse_pattern()4786 parser::parse_pattern ()
4787 {
4788 /* All clauses start with '('. */
4789 eat_token (CPP_OPEN_PAREN);
4790 const cpp_token *token = peek ();
4791 const char *id = get_ident ();
4792 if (strcmp (id, "simplify") == 0)
4793 {
4794 parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL);
4795 capture_ids = NULL;
4796 }
4797 else if (strcmp (id, "match") == 0)
4798 {
4799 bool with_args = false;
4800 source_location e_loc = peek ()->src_loc;
4801 if (peek ()->type == CPP_OPEN_PAREN)
4802 {
4803 eat_token (CPP_OPEN_PAREN);
4804 with_args = true;
4805 }
4806 const char *name = get_ident ();
4807 id_base *id = get_operator (name);
4808 predicate_id *p;
4809 if (!id)
4810 {
4811 p = add_predicate (name);
4812 user_predicates.safe_push (p);
4813 }
4814 else if ((p = dyn_cast <predicate_id *> (id)))
4815 ;
4816 else
4817 fatal_at (token, "cannot add a match to a non-predicate ID");
4818 /* Parse (match <id> <arg>... (match-expr)) here. */
4819 expr *e = NULL;
4820 if (with_args)
4821 {
4822 capture_ids = new cid_map_t;
4823 e = new expr (p, e_loc);
4824 while (peek ()->type == CPP_ATSIGN)
4825 e->append_op (parse_capture (NULL, false));
4826 eat_token (CPP_CLOSE_PAREN);
4827 }
4828 if (p->nargs != -1
4829 && ((e && e->ops.length () != (unsigned)p->nargs)
4830 || (!e && p->nargs != 0)))
4831 fatal_at (token, "non-matching number of match operands");
4832 p->nargs = e ? e->ops.length () : 0;
4833 parse_simplify (simplify::MATCH, p->matchers, p, e);
4834 capture_ids = NULL;
4835 }
4836 else if (strcmp (id, "for") == 0)
4837 parse_for (token->src_loc);
4838 else if (strcmp (id, "if") == 0)
4839 parse_if (token->src_loc);
4840 else if (strcmp (id, "define_predicates") == 0)
4841 {
4842 if (active_ifs.length () > 0
4843 || active_fors.length () > 0)
4844 fatal_at (token, "define_predicates inside if or for is not supported");
4845 parse_predicates (token->src_loc);
4846 }
4847 else if (strcmp (id, "define_operator_list") == 0)
4848 {
4849 if (active_ifs.length () > 0
4850 || active_fors.length () > 0)
4851 fatal_at (token, "operator-list inside if or for is not supported");
4852 parse_operator_list (token->src_loc);
4853 }
4854 else
4855 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'",
4856 active_ifs.length () == 0 && active_fors.length () == 0
4857 ? "'define_predicates', " : "");
4858
4859 eat_token (CPP_CLOSE_PAREN);
4860 }
4861
4862 /* Helper for finish_match_operand, collecting captures of OP in CPTS
4863 recursively. */
4864
4865 static void
walk_captures(operand * op,vec<vec<capture * >> cpts)4866 walk_captures (operand *op, vec<vec<capture *> > cpts)
4867 {
4868 if (! op)
4869 return;
4870
4871 if (capture *c = dyn_cast <capture *> (op))
4872 {
4873 cpts[c->where].safe_push (c);
4874 walk_captures (c->what, cpts);
4875 }
4876 else if (expr *e = dyn_cast <expr *> (op))
4877 for (unsigned i = 0; i < e->ops.length (); ++i)
4878 walk_captures (e->ops[i], cpts);
4879 }
4880
4881 /* Finish up OP which is a match operand. */
4882
4883 void
finish_match_operand(operand * op)4884 parser::finish_match_operand (operand *op)
4885 {
4886 /* Look for matching captures, diagnose mis-uses of @@ and apply
4887 early lowering and distribution of value_match. */
4888 auto_vec<vec<capture *> > cpts;
4889 cpts.safe_grow_cleared (capture_ids->elements ());
4890 walk_captures (op, cpts);
4891 for (unsigned i = 0; i < cpts.length (); ++i)
4892 {
4893 capture *value_match = NULL;
4894 for (unsigned j = 0; j < cpts[i].length (); ++j)
4895 {
4896 if (cpts[i][j]->value_match)
4897 {
4898 if (value_match)
4899 fatal_at (cpts[i][j]->location, "duplicate @@");
4900 value_match = cpts[i][j];
4901 }
4902 }
4903 if (cpts[i].length () == 1 && value_match)
4904 fatal_at (value_match->location, "@@ without a matching capture");
4905 if (value_match)
4906 {
4907 /* Duplicate prevailing capture with the existing ID, create
4908 a fake ID and rewrite all captures to use it. This turns
4909 @@1 into @__<newid>@1 and @1 into @__<newid>. */
4910 value_match->what = new capture (value_match->location,
4911 value_match->where,
4912 value_match->what, false);
4913 /* Create a fake ID and rewrite all captures to use it. */
4914 unsigned newid = get_internal_capture_id ();
4915 for (unsigned j = 0; j < cpts[i].length (); ++j)
4916 {
4917 cpts[i][j]->where = newid;
4918 cpts[i][j]->value_match = true;
4919 }
4920 }
4921 cpts[i].release ();
4922 }
4923 }
4924
4925 /* Main entry of the parser. Repeatedly parse outer control structures. */
4926
parser(cpp_reader * r_)4927 parser::parser (cpp_reader *r_)
4928 {
4929 r = r_;
4930 active_ifs = vNULL;
4931 active_fors = vNULL;
4932 simplifiers = vNULL;
4933 oper_lists_set = NULL;
4934 oper_lists = vNULL;
4935 capture_ids = NULL;
4936 user_predicates = vNULL;
4937 parsing_match_operand = false;
4938 last_id = 0;
4939
4940 const cpp_token *token = next ();
4941 while (token->type != CPP_EOF)
4942 {
4943 _cpp_backup_tokens (r, 1);
4944 parse_pattern ();
4945 token = next ();
4946 }
4947 }
4948
4949
4950 /* Helper for the linemap code. */
4951
4952 static size_t
round_alloc_size(size_t s)4953 round_alloc_size (size_t s)
4954 {
4955 return s;
4956 }
4957
4958
4959 /* The genmatch generator progam. It reads from a pattern description
4960 and outputs GIMPLE or GENERIC IL matching and simplification routines. */
4961
4962 int
main(int argc,char ** argv)4963 main (int argc, char **argv)
4964 {
4965 cpp_reader *r;
4966
4967 progname = "genmatch";
4968
4969 if (argc < 2)
4970 return 1;
4971
4972 bool gimple = true;
4973 char *input = argv[argc-1];
4974 for (int i = 1; i < argc - 1; ++i)
4975 {
4976 if (strcmp (argv[i], "--gimple") == 0)
4977 gimple = true;
4978 else if (strcmp (argv[i], "--generic") == 0)
4979 gimple = false;
4980 else if (strcmp (argv[i], "-v") == 0)
4981 verbose = 1;
4982 else if (strcmp (argv[i], "-vv") == 0)
4983 verbose = 2;
4984 else
4985 {
4986 fprintf (stderr, "Usage: genmatch "
4987 "[--gimple] [--generic] [-v[v]] input\n");
4988 return 1;
4989 }
4990 }
4991
4992 line_table = XCNEW (struct line_maps);
4993 linemap_init (line_table, 0);
4994 line_table->reallocator = xrealloc;
4995 line_table->round_alloc_size = round_alloc_size;
4996
4997 r = cpp_create_reader (CLK_GNUC99, NULL, line_table);
4998 cpp_callbacks *cb = cpp_get_callbacks (r);
4999 cb->error = error_cb;
5000
5001 /* Add the build directory to the #include "" search path. */
5002 cpp_dir *dir = XCNEW (cpp_dir);
5003 dir->name = getpwd ();
5004 if (!dir->name)
5005 dir->name = ASTRDUP (".");
5006 cpp_set_include_chains (r, dir, NULL, false);
5007
5008 if (!cpp_read_main_file (r, input))
5009 return 1;
5010 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1");
5011 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0");
5012
5013 null_id = new id_base (id_base::NULL_ID, "null");
5014
5015 /* Pre-seed operators. */
5016 operators = new hash_table<id_base> (1024);
5017 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \
5018 add_operator (SYM, # SYM, # TYPE, NARGS);
5019 #define END_OF_BASE_TREE_CODES
5020 #include "tree.def"
5021 add_operator (CONVERT0, "convert0", "tcc_unary", 1);
5022 add_operator (CONVERT1, "convert1", "tcc_unary", 1);
5023 add_operator (CONVERT2, "convert2", "tcc_unary", 1);
5024 add_operator (VIEW_CONVERT0, "view_convert0", "tcc_unary", 1);
5025 add_operator (VIEW_CONVERT1, "view_convert1", "tcc_unary", 1);
5026 add_operator (VIEW_CONVERT2, "view_convert2", "tcc_unary", 1);
5027 #undef END_OF_BASE_TREE_CODES
5028 #undef DEFTREECODE
5029
5030 /* Pre-seed builtin functions.
5031 ??? Cannot use N (name) as that is targetm.emultls.get_address
5032 for BUILT_IN_EMUTLS_GET_ADDRESS ... */
5033 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \
5034 add_function (ENUM, "CFN_" # ENUM);
5035 #include "builtins.def"
5036
5037 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \
5038 add_function (IFN_##CODE, "CFN_" #CODE);
5039 #include "internal-fn.def"
5040
5041 /* Parse ahead! */
5042 parser p (r);
5043
5044 if (gimple)
5045 write_header (stdout, "gimple-match-head.c");
5046 else
5047 write_header (stdout, "generic-match-head.c");
5048
5049 /* Go over all predicates defined with patterns and perform
5050 lowering and code generation. */
5051 for (unsigned i = 0; i < p.user_predicates.length (); ++i)
5052 {
5053 predicate_id *pred = p.user_predicates[i];
5054 lower (pred->matchers, gimple);
5055
5056 if (verbose == 2)
5057 for (unsigned i = 0; i < pred->matchers.length (); ++i)
5058 print_matches (pred->matchers[i]);
5059
5060 decision_tree dt;
5061 for (unsigned i = 0; i < pred->matchers.length (); ++i)
5062 dt.insert (pred->matchers[i], i);
5063
5064 if (verbose == 2)
5065 dt.print (stderr);
5066
5067 write_predicate (stdout, pred, dt, gimple);
5068 }
5069
5070 /* Lower the main simplifiers and generate code for them. */
5071 lower (p.simplifiers, gimple);
5072
5073 if (verbose == 2)
5074 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5075 print_matches (p.simplifiers[i]);
5076
5077 decision_tree dt;
5078 for (unsigned i = 0; i < p.simplifiers.length (); ++i)
5079 dt.insert (p.simplifiers[i], i);
5080
5081 if (verbose == 2)
5082 dt.print (stderr);
5083
5084 dt.gen (stdout, gimple);
5085
5086 /* Finalize. */
5087 cpp_finish (r, NULL);
5088 cpp_destroy (r);
5089
5090 delete operators;
5091
5092 return 0;
5093 }
5094