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