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