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-2017 Free Software Foundation, Inc.
5 Contributed by Richard Biener <rguenther@suse.de>
6 and Prathamesh Kulkarni <bilbotheelffriend@gmail.com>
7
8This file is part of GCC.
9
10GCC is free software; you can redistribute it and/or modify it under
11the terms of the GNU General Public License as published by the Free
12Software Foundation; either version 3, or (at your option) any later
13version.
14
15GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16WARRANTY; without even the implied warranty of MERCHANTABILITY or
17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18for more details.
19
20You should have received a copy of the GNU General Public License
21along 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. */
35void *ggc_internal_cleared_alloc (size_t, void (*)(void *),
36 size_t, size_t MEM_STAT_DECL)
37{
38 return NULL;
39}
40void ggc_free (void *)
41{
42}
43
44
45/* Global state. */
46
47/* Verboseness. 0 is quiet, 1 adds some warnings, 2 is for debugging. */
48unsigned verbose;
49
50
51/* libccp helpers. */
52
53static 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
63expanded_location
64linemap_client_expand_location_to_spelling_point (source_location loc,
65 enum location_aspect)
66{
67 const struct line_map_ordinary *map;
68 loc = linemap_resolve_location (line_table, loc, LRK_SPELLING_LOCATION, &map);
69 return linemap_expand_location (line_table, map, loc);
70}
71
72static bool
73#if GCC_VERSION >= 4001
74__attribute__((format (printf, 5, 0)))
75#endif
76error_cb (cpp_reader *, int errtype, int, rich_location *richloc,
77 const char *msg, va_list *ap)
78{
79 const line_map_ordinary *map;
80 source_location location = richloc->get_loc ();
81 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
82 expanded_location loc = linemap_expand_location (line_table, map, location);
83 fprintf (stderr, "%s:%d:%d %s: ", loc.file, loc.line, loc.column,
84 (errtype == CPP_DL_WARNING) ? "warning" : "error");
85 vfprintf (stderr, msg, *ap);
86 fprintf (stderr, "\n");
87 FILE *f = fopen (loc.file, "r");
88 if (f)
89 {
90 char buf[128];
91 while (loc.line > 0)
92 {
93 if (!fgets (buf, 128, f))
94 goto notfound;
95 if (buf[strlen (buf) - 1] != '\n')
96 {
97 if (loc.line > 1)
98 loc.line++;
99 }
100 loc.line--;
101 }
102 fprintf (stderr, "%s", buf);
103 for (int i = 0; i < loc.column - 1; ++i)
104 fputc (' ', stderr);
105 fputc ('^', stderr);
106 fputc ('\n', stderr);
107notfound:
108 fclose (f);
109 }
110
111 if (errtype == CPP_DL_FATAL)
112 exit (1);
113 return false;
114}
115
116static void
117#if GCC_VERSION >= 4001
118__attribute__((format (printf, 2, 3)))
119#endif
120fatal_at (const cpp_token *tk, const char *msg, ...)
121{
122 rich_location richloc (line_table, tk->src_loc);
123 va_list ap;
124 va_start (ap, msg);
125 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
126 va_end (ap);
127}
128
129static void
130#if GCC_VERSION >= 4001
131__attribute__((format (printf, 2, 3)))
132#endif
133fatal_at (source_location loc, const char *msg, ...)
134{
135 rich_location richloc (line_table, loc);
136 va_list ap;
137 va_start (ap, msg);
138 error_cb (NULL, CPP_DL_FATAL, 0, &richloc, msg, &ap);
139 va_end (ap);
140}
141
142static void
143#if GCC_VERSION >= 4001
144__attribute__((format (printf, 2, 3)))
145#endif
146warning_at (const cpp_token *tk, const char *msg, ...)
147{
148 rich_location richloc (line_table, tk->src_loc);
149 va_list ap;
150 va_start (ap, msg);
151 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
152 va_end (ap);
153}
154
155static void
156#if GCC_VERSION >= 4001
157__attribute__((format (printf, 2, 3)))
158#endif
159warning_at (source_location loc, const char *msg, ...)
160{
161 rich_location richloc (line_table, loc);
162 va_list ap;
163 va_start (ap, msg);
164 error_cb (NULL, CPP_DL_WARNING, 0, &richloc, msg, &ap);
165 va_end (ap);
166}
167
168/* Like fprintf, but print INDENT spaces at the beginning. */
169
170static void
171#if GCC_VERSION >= 4001
172__attribute__((format (printf, 3, 4)))
173#endif
174fprintf_indent (FILE *f, unsigned int indent, const char *format, ...)
175{
176 va_list ap;
177 for (; indent >= 8; indent -= 8)
178 fputc ('\t', f);
179 fprintf (f, "%*s", indent, "");
180 va_start (ap, format);
181 vfprintf (f, format, ap);
182 va_end (ap);
183}
184
185static void
186output_line_directive (FILE *f, source_location location,
187 bool dumpfile = false)
188{
189 const line_map_ordinary *map;
190 linemap_resolve_location (line_table, location, LRK_SPELLING_LOCATION, &map);
191 expanded_location loc = linemap_expand_location (line_table, map, location);
192 if (dumpfile)
193 {
194 /* When writing to a dumpfile only dump the filename. */
195 const char *file = strrchr (loc.file, DIR_SEPARATOR);
196#if defined(DIR_SEPARATOR_2)
197 const char *pos2 = strrchr (loc.file, DIR_SEPARATOR_2);
198 if (pos2 && (!file || (pos2 > file)))
199 file = pos2;
200#endif
201 if (!file)
202 file = loc.file;
203 else
204 ++file;
205 fprintf (f, "%s:%d", file, loc.line);
206 }
207 else
208 /* Other gen programs really output line directives here, at least for
209 development it's right now more convenient to have line information
210 from the generated file. Still keep the directives as comment for now
211 to easily back-point to the meta-description. */
212 fprintf (f, "/* #line %d \"%s\" */\n", loc.line, loc.file);
213}
214
215
216/* Pull in tree codes and builtin function codes from their
217 definition files. */
218
219#define DEFTREECODE(SYM, STRING, TYPE, NARGS) SYM,
220enum tree_code {
221#include "tree.def"
222CONVERT0,
223CONVERT1,
224CONVERT2,
225VIEW_CONVERT0,
226VIEW_CONVERT1,
227VIEW_CONVERT2,
228MAX_TREE_CODES
229};
230#undef DEFTREECODE
231
232#define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) ENUM,
233enum built_in_function {
234#include "builtins.def"
235END_BUILTINS
236};
237
238#define DEF_INTERNAL_FN(CODE, FLAGS, FNSPEC) IFN_##CODE,
239enum internal_fn {
240#include "internal-fn.def"
241 IFN_LAST
242};
243
244/* Return true if CODE represents a commutative tree code. Otherwise
245 return false. */
246bool
247commutative_tree_code (enum tree_code code)
248{
249 switch (code)
250 {
251 case PLUS_EXPR:
252 case MULT_EXPR:
253 case MULT_HIGHPART_EXPR:
254 case MIN_EXPR:
255 case MAX_EXPR:
256 case BIT_IOR_EXPR:
257 case BIT_XOR_EXPR:
258 case BIT_AND_EXPR:
259 case NE_EXPR:
260 case EQ_EXPR:
261 case UNORDERED_EXPR:
262 case ORDERED_EXPR:
263 case UNEQ_EXPR:
264 case LTGT_EXPR:
265 case TRUTH_AND_EXPR:
266 case TRUTH_XOR_EXPR:
267 case TRUTH_OR_EXPR:
268 case WIDEN_MULT_EXPR:
269 case VEC_WIDEN_MULT_HI_EXPR:
270 case VEC_WIDEN_MULT_LO_EXPR:
271 case VEC_WIDEN_MULT_EVEN_EXPR:
272 case VEC_WIDEN_MULT_ODD_EXPR:
273 return true;
274
275 default:
276 break;
277 }
278 return false;
279}
280
281/* Return true if CODE represents a ternary tree code for which the
282 first two operands are commutative. Otherwise return false. */
283bool
284commutative_ternary_tree_code (enum tree_code code)
285{
286 switch (code)
287 {
288 case WIDEN_MULT_PLUS_EXPR:
289 case WIDEN_MULT_MINUS_EXPR:
290 case DOT_PROD_EXPR:
291 case FMA_EXPR:
292 return true;
293
294 default:
295 break;
296 }
297 return false;
298}
299
300/* Return true if CODE is a comparison. */
301
302bool
303comparison_code_p (enum tree_code code)
304{
305 switch (code)
306 {
307 case EQ_EXPR:
308 case NE_EXPR:
309 case ORDERED_EXPR:
310 case UNORDERED_EXPR:
311 case LTGT_EXPR:
312 case UNEQ_EXPR:
313 case GT_EXPR:
314 case GE_EXPR:
315 case LT_EXPR:
316 case LE_EXPR:
317 case UNGT_EXPR:
318 case UNGE_EXPR:
319 case UNLT_EXPR:
320 case UNLE_EXPR:
321 return true;
322
323 default:
324 break;
325 }
326 return false;
327}
328
329
330/* Base class for all identifiers the parser knows. */
331
332struct id_base : nofree_ptr_hash<id_base>
333{
334 enum id_kind { CODE, FN, PREDICATE, USER, NULL_ID } kind;
335
336 id_base (id_kind, const char *, int = -1);
337
338 hashval_t hashval;
339 int nargs;
340 const char *id;
341
342 /* hash_table support. */
343 static inline hashval_t hash (const id_base *);
344 static inline int equal (const id_base *, const id_base *);
345};
346
347inline hashval_t
348id_base::hash (const id_base *op)
349{
350 return op->hashval;
351}
352
353inline int
354id_base::equal (const id_base *op1,
355 const id_base *op2)
356{
357 return (op1->hashval == op2->hashval
358 && strcmp (op1->id, op2->id) == 0);
359}
360
361/* The special id "null", which matches nothing. */
362static id_base *null_id;
363
364/* Hashtable of known pattern operators. This is pre-seeded from
365 all known tree codes and all known builtin function ids. */
366static hash_table<id_base> *operators;
367
368id_base::id_base (id_kind kind_, const char *id_, int nargs_)
369{
370 kind = kind_;
371 id = id_;
372 nargs = nargs_;
373 hashval = htab_hash_string (id);
374}
375
376/* Identifier that maps to a tree code. */
377
378struct operator_id : public id_base
379{
380 operator_id (enum tree_code code_, const char *id_, unsigned nargs_,
381 const char *tcc_)
382 : id_base (id_base::CODE, id_, nargs_), code (code_), tcc (tcc_) {}
383 enum tree_code code;
384 const char *tcc;
385};
386
387/* Identifier that maps to a builtin or internal function code. */
388
389struct fn_id : public id_base
390{
391 fn_id (enum built_in_function fn_, const char *id_)
392 : id_base (id_base::FN, id_), fn (fn_) {}
393 fn_id (enum internal_fn fn_, const char *id_)
394 : id_base (id_base::FN, id_), fn (int (END_BUILTINS) + int (fn_)) {}
395 unsigned int fn;
396};
397
398struct simplify;
399
400/* Identifier that maps to a user-defined predicate. */
401
402struct predicate_id : public id_base
403{
404 predicate_id (const char *id_)
405 : id_base (id_base::PREDICATE, id_), matchers (vNULL) {}
406 vec<simplify *> matchers;
407};
408
409/* Identifier that maps to a operator defined by a 'for' directive. */
410
411struct user_id : public id_base
412{
413 user_id (const char *id_, bool is_oper_list_ = false)
414 : id_base (id_base::USER, id_), substitutes (vNULL),
415 used (false), is_oper_list (is_oper_list_) {}
416 vec<id_base *> substitutes;
417 bool used;
418 bool is_oper_list;
419};
420
421template<>
422template<>
423inline bool
424is_a_helper <fn_id *>::test (id_base *id)
425{
426 return id->kind == id_base::FN;
427}
428
429template<>
430template<>
431inline bool
432is_a_helper <operator_id *>::test (id_base *id)
433{
434 return id->kind == id_base::CODE;
435}
436
437template<>
438template<>
439inline bool
440is_a_helper <predicate_id *>::test (id_base *id)
441{
442 return id->kind == id_base::PREDICATE;
443}
444
445template<>
446template<>
447inline bool
448is_a_helper <user_id *>::test (id_base *id)
449{
450 return id->kind == id_base::USER;
451}
452
453/* Add a predicate identifier to the hash. */
454
455static predicate_id *
456add_predicate (const char *id)
457{
458 predicate_id *p = new predicate_id (id);
459 id_base **slot = operators->find_slot_with_hash (p, p->hashval, INSERT);
460 if (*slot)
461 fatal ("duplicate id definition");
462 *slot = p;
463 return p;
464}
465
466/* Add a tree code identifier to the hash. */
467
468static void
469add_operator (enum tree_code code, const char *id,
470 const char *tcc, unsigned nargs)
471{
472 if (strcmp (tcc, "tcc_unary") != 0
473 && strcmp (tcc, "tcc_binary") != 0
474 && strcmp (tcc, "tcc_comparison") != 0
475 && strcmp (tcc, "tcc_expression") != 0
476 /* For {REAL,IMAG}PART_EXPR and VIEW_CONVERT_EXPR. */
477 && strcmp (tcc, "tcc_reference") != 0
478 /* To have INTEGER_CST and friends as "predicate operators". */
479 && strcmp (tcc, "tcc_constant") != 0
480 /* And allow CONSTRUCTOR for vector initializers. */
481 && !(code == CONSTRUCTOR)
482 /* Allow SSA_NAME as predicate operator. */
483 && !(code == SSA_NAME))
484 return;
485 /* Treat ADDR_EXPR as atom, thus don't allow matching its operand. */
486 if (code == ADDR_EXPR)
487 nargs = 0;
488 operator_id *op = new operator_id (code, id, nargs, tcc);
489 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT);
490 if (*slot)
491 fatal ("duplicate id definition");
492 *slot = op;
493}
494
495/* Add a built-in or internal function identifier to the hash. ID is
496 the name of its CFN_* enumeration value. */
497
498template <typename T>
499static void
500add_function (T code, const char *id)
501{
502 fn_id *fn = new fn_id (code, id);
503 id_base **slot = operators->find_slot_with_hash (fn, fn->hashval, INSERT);
504 if (*slot)
505 fatal ("duplicate id definition");
506 *slot = fn;
507}
508
509/* Helper for easy comparing ID with tree code CODE. */
510
511static bool
512operator==(id_base &id, enum tree_code code)
513{
514 if (operator_id *oid = dyn_cast <operator_id *> (&id))
515 return oid->code == code;
516 return false;
517}
518
519/* Lookup the identifier ID. Allow "null" if ALLOW_NULL. */
520
521id_base *
522get_operator (const char *id, bool allow_null = false)
523{
524 if (allow_null && strcmp (id, "null") == 0)
525 return null_id;
526
527 id_base tem (id_base::CODE, id);
528
529 id_base *op = operators->find_with_hash (&tem, tem.hashval);
530 if (op)
531 {
532 /* If this is a user-defined identifier track whether it was used. */
533 if (user_id *uid = dyn_cast<user_id *> (op))
534 uid->used = true;
535 return op;
536 }
537
538 char *id2;
539 bool all_upper = true;
540 bool all_lower = true;
541 for (unsigned int i = 0; id[i]; ++i)
542 if (ISUPPER (id[i]))
543 all_lower = false;
544 else if (ISLOWER (id[i]))
545 all_upper = false;
546 if (all_lower)
547 {
548 /* Try in caps with _EXPR appended. */
549 id2 = ACONCAT ((id, "_EXPR", NULL));
550 for (unsigned int i = 0; id2[i]; ++i)
551 id2[i] = TOUPPER (id2[i]);
552 }
553 else if (all_upper && strncmp (id, "IFN_", 4) == 0)
554 /* Try CFN_ instead of IFN_. */
555 id2 = ACONCAT (("CFN_", id + 4, NULL));
556 else if (all_upper && strncmp (id, "BUILT_IN_", 9) == 0)
557 /* Try prepending CFN_. */
558 id2 = ACONCAT (("CFN_", id, NULL));
559 else
560 return NULL;
561
562 new (&tem) id_base (id_base::CODE, id2);
563 return operators->find_with_hash (&tem, tem.hashval);
564}
565
566/* Return the comparison operators that results if the operands are
567 swapped. This is safe for floating-point. */
568
569id_base *
570swap_tree_comparison (operator_id *p)
571{
572 switch (p->code)
573 {
574 case EQ_EXPR:
575 case NE_EXPR:
576 case ORDERED_EXPR:
577 case UNORDERED_EXPR:
578 case LTGT_EXPR:
579 case UNEQ_EXPR:
580 return p;
581 case GT_EXPR:
582 return get_operator ("LT_EXPR");
583 case GE_EXPR:
584 return get_operator ("LE_EXPR");
585 case LT_EXPR:
586 return get_operator ("GT_EXPR");
587 case LE_EXPR:
588 return get_operator ("GE_EXPR");
589 case UNGT_EXPR:
590 return get_operator ("UNLT_EXPR");
591 case UNGE_EXPR:
592 return get_operator ("UNLE_EXPR");
593 case UNLT_EXPR:
594 return get_operator ("UNGT_EXPR");
595 case UNLE_EXPR:
596 return get_operator ("UNGE_EXPR");
597 default:
598 gcc_unreachable ();
599 }
600}
601
602typedef hash_map<nofree_string_hash, unsigned> cid_map_t;
603
604
605/* The AST produced by parsing of the pattern definitions. */
606
607struct dt_operand;
608struct capture_info;
609
610/* The base class for operands. */
611
612struct operand {
613 enum op_type { OP_PREDICATE, OP_EXPR, OP_CAPTURE, OP_C_EXPR, OP_IF, OP_WITH };
614 operand (enum op_type type_, source_location loc_)
615 : type (type_), location (loc_) {}
616 enum op_type type;
617 source_location location;
618 virtual void gen_transform (FILE *, int, const char *, bool, int,
619 const char *, capture_info *,
620 dt_operand ** = 0,
621 int = 0)
622 { gcc_unreachable (); }
623};
624
625/* A predicate operand. Predicates are leafs in the AST. */
626
627struct predicate : public operand
628{
629 predicate (predicate_id *p_, source_location loc)
630 : operand (OP_PREDICATE, loc), p (p_) {}
631 predicate_id *p;
632};
633
634/* An operand that constitutes an expression. Expressions include
635 function calls and user-defined predicate invocations. */
636
637struct expr : public operand
638{
639 expr (id_base *operation_, source_location loc, bool is_commutative_ = false)
640 : operand (OP_EXPR, loc), operation (operation_),
641 ops (vNULL), expr_type (NULL), is_commutative (is_commutative_),
642 is_generic (false), force_single_use (false) {}
643 expr (expr *e)
644 : operand (OP_EXPR, e->location), operation (e->operation),
645 ops (vNULL), expr_type (e->expr_type), is_commutative (e->is_commutative),
646 is_generic (e->is_generic), force_single_use (e->force_single_use) {}
647 void append_op (operand *op) { ops.safe_push (op); }
648 /* The operator and its operands. */
649 id_base *operation;
650 vec<operand *> ops;
651 /* An explicitely specified type - used exclusively for conversions. */
652 const char *expr_type;
653 /* Whether the operation is to be applied commutatively. This is
654 later lowered to two separate patterns. */
655 bool is_commutative;
656 /* Whether the expression is expected to be in GENERIC form. */
657 bool is_generic;
658 /* Whether pushing any stmt to the sequence should be conditional
659 on this expression having a single-use. */
660 bool force_single_use;
661 virtual void gen_transform (FILE *f, int, const char *, bool, int,
662 const char *, capture_info *,
663 dt_operand ** = 0, int = 0);
664};
665
666/* An operator that is represented by native C code. This is always
667 a leaf operand in the AST. This class is also used to represent
668 the code to be generated for 'if' and 'with' expressions. */
669
670struct c_expr : public operand
671{
672 /* A mapping of an identifier and its replacement. Used to apply
673 'for' lowering. */
674 struct id_tab {
675 const char *id;
676 const char *oper;
677 id_tab (const char *id_, const char *oper_): id (id_), oper (oper_) {}
678 };
679
680 c_expr (cpp_reader *r_, source_location loc,
681 vec<cpp_token> code_, unsigned nr_stmts_,
682 vec<id_tab> ids_, cid_map_t *capture_ids_)
683 : operand (OP_C_EXPR, loc), r (r_), code (code_),
684 capture_ids (capture_ids_), nr_stmts (nr_stmts_), ids (ids_) {}
685 /* cpplib tokens and state to transform this back to source. */
686 cpp_reader *r;
687 vec<cpp_token> code;
688 cid_map_t *capture_ids;
689 /* The number of statements parsed (well, the number of ';'s). */
690 unsigned nr_stmts;
691 /* The identifier replacement vector. */
692 vec<id_tab> ids;
693 virtual void gen_transform (FILE *f, int, const char *, bool, int,
694 const char *, capture_info *,
695 dt_operand ** = 0, int = 0);
696};
697
698/* A wrapper around another operand that captures its value. */
699
700struct capture : public operand
701{
702 capture (source_location loc, unsigned where_, operand *what_, bool value_)
703 : operand (OP_CAPTURE, loc), where (where_), value_match (value_),
704 what (what_) {}
705 /* Identifier index for the value. */
706 unsigned where;
707 /* Whether in a match of two operands the compare should be for
708 equal values rather than equal atoms (boils down to a type
709 check or not). */
710 bool value_match;
711 /* The captured value. */
712 operand *what;
713 virtual void gen_transform (FILE *f, int, const char *, bool, int,
714 const char *, capture_info *,
715 dt_operand ** = 0, int = 0);
716};
717
718/* if expression. */
719
720struct if_expr : public operand
721{
722 if_expr (source_location loc)
723 : operand (OP_IF, loc), cond (NULL), trueexpr (NULL), falseexpr (NULL) {}
724 c_expr *cond;
725 operand *trueexpr;
726 operand *falseexpr;
727};
728
729/* with expression. */
730
731struct with_expr : public operand
732{
733 with_expr (source_location loc)
734 : operand (OP_WITH, loc), with (NULL), subexpr (NULL) {}
735 c_expr *with;
736 operand *subexpr;
737};
738
739template<>
740template<>
741inline bool
742is_a_helper <capture *>::test (operand *op)
743{
744 return op->type == operand::OP_CAPTURE;
745}
746
747template<>
748template<>
749inline bool
750is_a_helper <predicate *>::test (operand *op)
751{
752 return op->type == operand::OP_PREDICATE;
753}
754
755template<>
756template<>
757inline bool
758is_a_helper <c_expr *>::test (operand *op)
759{
760 return op->type == operand::OP_C_EXPR;
761}
762
763template<>
764template<>
765inline bool
766is_a_helper <expr *>::test (operand *op)
767{
768 return op->type == operand::OP_EXPR;
769}
770
771template<>
772template<>
773inline bool
774is_a_helper <if_expr *>::test (operand *op)
775{
776 return op->type == operand::OP_IF;
777}
778
779template<>
780template<>
781inline bool
782is_a_helper <with_expr *>::test (operand *op)
783{
784 return op->type == operand::OP_WITH;
785}
786
787/* The main class of a pattern and its transform. This is used to
788 represent both (simplify ...) and (match ...) kinds. The AST
789 duplicates all outer 'if' and 'for' expressions here so each
790 simplify can exist in isolation. */
791
792struct simplify
793{
794 enum simplify_kind { SIMPLIFY, MATCH };
795
796 simplify (simplify_kind kind_, unsigned id_, operand *match_,
797 operand *result_, vec<vec<user_id *> > for_vec_,
798 cid_map_t *capture_ids_)
799 : kind (kind_), id (id_), match (match_), result (result_),
800 for_vec (for_vec_), for_subst_vec (vNULL),
801 capture_ids (capture_ids_), capture_max (capture_ids_->elements () - 1) {}
802
803 simplify_kind kind;
804 /* ID. This is kept to easily associate related simplifies expanded
805 from the same original one. */
806 unsigned id;
807 /* The expression that is matched against the GENERIC or GIMPLE IL. */
808 operand *match;
809 /* For a (simplify ...) an expression with ifs and withs with the expression
810 produced when the pattern applies in the leafs.
811 For a (match ...) the leafs are either empty if it is a simple predicate
812 or the single expression specifying the matched operands. */
813 struct operand *result;
814 /* Collected 'for' expression operators that have to be replaced
815 in the lowering phase. */
816 vec<vec<user_id *> > for_vec;
817 vec<std::pair<user_id *, id_base *> > for_subst_vec;
818 /* A map of capture identifiers to indexes. */
819 cid_map_t *capture_ids;
820 int capture_max;
821};
822
823/* Debugging routines for dumping the AST. */
824
825DEBUG_FUNCTION void
826print_operand (operand *o, FILE *f = stderr, bool flattened = false)
827{
828 if (capture *c = dyn_cast<capture *> (o))
829 {
830 if (c->what && flattened == false)
831 print_operand (c->what, f, flattened);
832 fprintf (f, "@%u", c->where);
833 }
834
835 else if (predicate *p = dyn_cast<predicate *> (o))
836 fprintf (f, "%s", p->p->id);
837
838 else if (is_a<c_expr *> (o))
839 fprintf (f, "c_expr");
840
841 else if (expr *e = dyn_cast<expr *> (o))
842 {
843 if (e->ops.length () == 0)
844 fprintf (f, "%s", e->operation->id);
845 else
846 {
847 fprintf (f, "(%s", e->operation->id);
848
849 if (flattened == false)
850 {
851 for (unsigned i = 0; i < e->ops.length (); ++i)
852 {
853 putc (' ', f);
854 print_operand (e->ops[i], f, flattened);
855 }
856 }
857 putc (')', f);
858 }
859 }
860
861 else
862 gcc_unreachable ();
863}
864
865DEBUG_FUNCTION void
866print_matches (struct simplify *s, FILE *f = stderr)
867{
868 fprintf (f, "for expression: ");
869 print_operand (s->match, f);
870 putc ('\n', f);
871}
872
873
874/* AST lowering. */
875
876/* Lowering of commutative operators. */
877
878static void
879cartesian_product (const vec< vec<operand *> >& ops_vector,
880 vec< vec<operand *> >& result, vec<operand *>& v, unsigned n)
881{
882 if (n == ops_vector.length ())
883 {
884 vec<operand *> xv = v.copy ();
885 result.safe_push (xv);
886 return;
887 }
888
889 for (unsigned i = 0; i < ops_vector[n].length (); ++i)
890 {
891 v[n] = ops_vector[n][i];
892 cartesian_product (ops_vector, result, v, n + 1);
893 }
894}
895
896/* Lower OP to two operands in case it is marked as commutative. */
897
898static vec<operand *>
899commutate (operand *op, vec<vec<user_id *> > &for_vec)
900{
901 vec<operand *> ret = vNULL;
902
903 if (capture *c = dyn_cast <capture *> (op))
904 {
905 if (!c->what)
906 {
907 ret.safe_push (op);
908 return ret;
909 }
910 vec<operand *> v = commutate (c->what, for_vec);
911 for (unsigned i = 0; i < v.length (); ++i)
912 {
913 capture *nc = new capture (c->location, c->where, v[i],
914 c->value_match);
915 ret.safe_push (nc);
916 }
917 return ret;
918 }
919
920 expr *e = dyn_cast <expr *> (op);
921 if (!e || e->ops.length () == 0)
922 {
923 ret.safe_push (op);
924 return ret;
925 }
926
927 vec< vec<operand *> > ops_vector = vNULL;
928 for (unsigned i = 0; i < e->ops.length (); ++i)
929 ops_vector.safe_push (commutate (e->ops[i], for_vec));
930
931 auto_vec< vec<operand *> > result;
932 auto_vec<operand *> v (e->ops.length ());
933 v.quick_grow_cleared (e->ops.length ());
934 cartesian_product (ops_vector, result, v, 0);
935
936
937 for (unsigned i = 0; i < result.length (); ++i)
938 {
939 expr *ne = new expr (e);
940 ne->is_commutative = false;
941 for (unsigned j = 0; j < result[i].length (); ++j)
942 ne->append_op (result[i][j]);
943 ret.safe_push (ne);
944 }
945
946 if (!e->is_commutative)
947 return ret;
948
949 for (unsigned i = 0; i < result.length (); ++i)
950 {
951 expr *ne = new expr (e);
952 if (operator_id *p = dyn_cast <operator_id *> (ne->operation))
953 {
954 if (comparison_code_p (p->code))
955 ne->operation = swap_tree_comparison (p);
956 }
957 else if (user_id *p = dyn_cast <user_id *> (ne->operation))
958 {
959 bool found_compare = false;
960 for (unsigned j = 0; j < p->substitutes.length (); ++j)
961 if (operator_id *q = dyn_cast <operator_id *> (p->substitutes[j]))
962 {
963 if (comparison_code_p (q->code)
964 && swap_tree_comparison (q) != q)
965 {
966 found_compare = true;
967 break;
968 }
969 }
970 if (found_compare)
971 {
972 user_id *newop = new user_id ("<internal>");
973 for (unsigned j = 0; j < p->substitutes.length (); ++j)
974 {
975 id_base *subst = p->substitutes[j];
976 if (operator_id *q = dyn_cast <operator_id *> (subst))
977 {
978 if (comparison_code_p (q->code))
979 subst = swap_tree_comparison (q);
980 }
981 newop->substitutes.safe_push (subst);
982 }
983 ne->operation = newop;
984 /* Search for 'p' inside the for vector and push 'newop'
985 to the same level. */
986 for (unsigned j = 0; newop && j < for_vec.length (); ++j)
987 for (unsigned k = 0; k < for_vec[j].length (); ++k)
988 if (for_vec[j][k] == p)
989 {
990 for_vec[j].safe_push (newop);
991 newop = NULL;
992 break;
993 }
994 }
995 }
996 ne->is_commutative = false;
997 // result[i].length () is 2 since e->operation is binary
998 for (unsigned j = result[i].length (); j; --j)
999 ne->append_op (result[i][j-1]);
1000 ret.safe_push (ne);
1001 }
1002
1003 return ret;
1004}
1005
1006/* Lower operations marked as commutative in the AST of S and push
1007 the resulting patterns to SIMPLIFIERS. */
1008
1009static void
1010lower_commutative (simplify *s, vec<simplify *>& simplifiers)
1011{
1012 vec<operand *> matchers = commutate (s->match, s->for_vec);
1013 for (unsigned i = 0; i < matchers.length (); ++i)
1014 {
1015 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1016 s->for_vec, s->capture_ids);
1017 simplifiers.safe_push (ns);
1018 }
1019}
1020
1021/* Strip conditional conversios using operator OPER from O and its
1022 children if STRIP, else replace them with an unconditional convert. */
1023
1024operand *
1025lower_opt_convert (operand *o, enum tree_code oper,
1026 enum tree_code to_oper, bool strip)
1027{
1028 if (capture *c = dyn_cast<capture *> (o))
1029 {
1030 if (c->what)
1031 return new capture (c->location, c->where,
1032 lower_opt_convert (c->what, oper, to_oper, strip),
1033 c->value_match);
1034 else
1035 return c;
1036 }
1037
1038 expr *e = dyn_cast<expr *> (o);
1039 if (!e)
1040 return o;
1041
1042 if (*e->operation == oper)
1043 {
1044 if (strip)
1045 return lower_opt_convert (e->ops[0], oper, to_oper, strip);
1046
1047 expr *ne = new expr (e);
1048 ne->operation = (to_oper == CONVERT_EXPR
1049 ? get_operator ("CONVERT_EXPR")
1050 : get_operator ("VIEW_CONVERT_EXPR"));
1051 ne->append_op (lower_opt_convert (e->ops[0], oper, to_oper, strip));
1052 return ne;
1053 }
1054
1055 expr *ne = new expr (e);
1056 for (unsigned i = 0; i < e->ops.length (); ++i)
1057 ne->append_op (lower_opt_convert (e->ops[i], oper, to_oper, strip));
1058
1059 return ne;
1060}
1061
1062/* Determine whether O or its children uses the conditional conversion
1063 operator OPER. */
1064
1065static bool
1066has_opt_convert (operand *o, enum tree_code oper)
1067{
1068 if (capture *c = dyn_cast<capture *> (o))
1069 {
1070 if (c->what)
1071 return has_opt_convert (c->what, oper);
1072 else
1073 return false;
1074 }
1075
1076 expr *e = dyn_cast<expr *> (o);
1077 if (!e)
1078 return false;
1079
1080 if (*e->operation == oper)
1081 return true;
1082
1083 for (unsigned i = 0; i < e->ops.length (); ++i)
1084 if (has_opt_convert (e->ops[i], oper))
1085 return true;
1086
1087 return false;
1088}
1089
1090/* Lower conditional convert operators in O, expanding it to a vector
1091 if required. */
1092
1093static vec<operand *>
1094lower_opt_convert (operand *o)
1095{
1096 vec<operand *> v1 = vNULL, v2;
1097
1098 v1.safe_push (o);
1099
1100 enum tree_code opers[]
1101 = { CONVERT0, CONVERT_EXPR,
1102 CONVERT1, CONVERT_EXPR,
1103 CONVERT2, CONVERT_EXPR,
1104 VIEW_CONVERT0, VIEW_CONVERT_EXPR,
1105 VIEW_CONVERT1, VIEW_CONVERT_EXPR,
1106 VIEW_CONVERT2, VIEW_CONVERT_EXPR };
1107
1108 /* Conditional converts are lowered to a pattern with the
1109 conversion and one without. The three different conditional
1110 convert codes are lowered separately. */
1111
1112 for (unsigned i = 0; i < sizeof (opers) / sizeof (enum tree_code); i += 2)
1113 {
1114 v2 = vNULL;
1115 for (unsigned j = 0; j < v1.length (); ++j)
1116 if (has_opt_convert (v1[j], opers[i]))
1117 {
1118 v2.safe_push (lower_opt_convert (v1[j],
1119 opers[i], opers[i+1], false));
1120 v2.safe_push (lower_opt_convert (v1[j],
1121 opers[i], opers[i+1], true));
1122 }
1123
1124 if (v2 != vNULL)
1125 {
1126 v1 = vNULL;
1127 for (unsigned j = 0; j < v2.length (); ++j)
1128 v1.safe_push (v2[j]);
1129 }
1130 }
1131
1132 return v1;
1133}
1134
1135/* Lower conditional convert operators in the AST of S and push
1136 the resulting multiple patterns to SIMPLIFIERS. */
1137
1138static void
1139lower_opt_convert (simplify *s, vec<simplify *>& simplifiers)
1140{
1141 vec<operand *> matchers = lower_opt_convert (s->match);
1142 for (unsigned i = 0; i < matchers.length (); ++i)
1143 {
1144 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1145 s->for_vec, s->capture_ids);
1146 simplifiers.safe_push (ns);
1147 }
1148}
1149
1150/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1151 GENERIC and a GIMPLE variant. */
1152
1153static vec<operand *>
1154lower_cond (operand *o)
1155{
1156 vec<operand *> ro = vNULL;
1157
1158 if (capture *c = dyn_cast<capture *> (o))
1159 {
1160 if (c->what)
1161 {
1162 vec<operand *> lop = vNULL;
1163 lop = lower_cond (c->what);
1164
1165 for (unsigned i = 0; i < lop.length (); ++i)
1166 ro.safe_push (new capture (c->location, c->where, lop[i],
1167 c->value_match));
1168 return ro;
1169 }
1170 }
1171
1172 expr *e = dyn_cast<expr *> (o);
1173 if (!e || e->ops.length () == 0)
1174 {
1175 ro.safe_push (o);
1176 return ro;
1177 }
1178
1179 vec< vec<operand *> > ops_vector = vNULL;
1180 for (unsigned i = 0; i < e->ops.length (); ++i)
1181 ops_vector.safe_push (lower_cond (e->ops[i]));
1182
1183 auto_vec< vec<operand *> > result;
1184 auto_vec<operand *> v (e->ops.length ());
1185 v.quick_grow_cleared (e->ops.length ());
1186 cartesian_product (ops_vector, result, v, 0);
1187
1188 for (unsigned i = 0; i < result.length (); ++i)
1189 {
1190 expr *ne = new expr (e);
1191 for (unsigned j = 0; j < result[i].length (); ++j)
1192 ne->append_op (result[i][j]);
1193 ro.safe_push (ne);
1194 /* If this is a COND with a captured expression or an
1195 expression with two operands then also match a GENERIC
1196 form on the compare. */
1197 if ((*e->operation == COND_EXPR
1198 || *e->operation == VEC_COND_EXPR)
1199 && ((is_a <capture *> (e->ops[0])
1200 && as_a <capture *> (e->ops[0])->what
1201 && is_a <expr *> (as_a <capture *> (e->ops[0])->what)
1202 && as_a <expr *>
1203 (as_a <capture *> (e->ops[0])->what)->ops.length () == 2)
1204 || (is_a <expr *> (e->ops[0])
1205 && as_a <expr *> (e->ops[0])->ops.length () == 2)))
1206 {
1207 expr *ne = new expr (e);
1208 for (unsigned j = 0; j < result[i].length (); ++j)
1209 ne->append_op (result[i][j]);
1210 if (capture *c = dyn_cast <capture *> (ne->ops[0]))
1211 {
1212 expr *ocmp = as_a <expr *> (c->what);
1213 expr *cmp = new expr (ocmp);
1214 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1215 cmp->append_op (ocmp->ops[j]);
1216 cmp->is_generic = true;
1217 ne->ops[0] = new capture (c->location, c->where, cmp,
1218 c->value_match);
1219 }
1220 else
1221 {
1222 expr *ocmp = as_a <expr *> (ne->ops[0]);
1223 expr *cmp = new expr (ocmp);
1224 for (unsigned j = 0; j < ocmp->ops.length (); ++j)
1225 cmp->append_op (ocmp->ops[j]);
1226 cmp->is_generic = true;
1227 ne->ops[0] = cmp;
1228 }
1229 ro.safe_push (ne);
1230 }
1231 }
1232
1233 return ro;
1234}
1235
1236/* Lower the compare operand of COND_EXPRs and VEC_COND_EXPRs to a
1237 GENERIC and a GIMPLE variant. */
1238
1239static void
1240lower_cond (simplify *s, vec<simplify *>& simplifiers)
1241{
1242 vec<operand *> matchers = lower_cond (s->match);
1243 for (unsigned i = 0; i < matchers.length (); ++i)
1244 {
1245 simplify *ns = new simplify (s->kind, s->id, matchers[i], s->result,
1246 s->for_vec, s->capture_ids);
1247 simplifiers.safe_push (ns);
1248 }
1249}
1250
1251/* Return true if O refers to ID. */
1252
1253bool
1254contains_id (operand *o, user_id *id)
1255{
1256 if (capture *c = dyn_cast<capture *> (o))
1257 return c->what && contains_id (c->what, id);
1258
1259 if (expr *e = dyn_cast<expr *> (o))
1260 {
1261 if (e->operation == id)
1262 return true;
1263 for (unsigned i = 0; i < e->ops.length (); ++i)
1264 if (contains_id (e->ops[i], id))
1265 return true;
1266 return false;
1267 }
1268
1269 if (with_expr *w = dyn_cast <with_expr *> (o))
1270 return (contains_id (w->with, id)
1271 || contains_id (w->subexpr, id));
1272
1273 if (if_expr *ife = dyn_cast <if_expr *> (o))
1274 return (contains_id (ife->cond, id)
1275 || contains_id (ife->trueexpr, id)
1276 || (ife->falseexpr && contains_id (ife->falseexpr, id)));
1277
1278 if (c_expr *ce = dyn_cast<c_expr *> (o))
1279 return ce->capture_ids && ce->capture_ids->get (id->id);
1280
1281 return false;
1282}
1283
1284
1285/* In AST operand O replace operator ID with operator WITH. */
1286
1287operand *
1288replace_id (operand *o, user_id *id, id_base *with)
1289{
1290 /* Deep-copy captures and expressions, replacing operations as
1291 needed. */
1292 if (capture *c = dyn_cast<capture *> (o))
1293 {
1294 if (!c->what)
1295 return c;
1296 return new capture (c->location, c->where,
1297 replace_id (c->what, id, with), c->value_match);
1298 }
1299 else if (expr *e = dyn_cast<expr *> (o))
1300 {
1301 expr *ne = new expr (e);
1302 if (e->operation == id)
1303 ne->operation = with;
1304 for (unsigned i = 0; i < e->ops.length (); ++i)
1305 ne->append_op (replace_id (e->ops[i], id, with));
1306 return ne;
1307 }
1308 else if (with_expr *w = dyn_cast <with_expr *> (o))
1309 {
1310 with_expr *nw = new with_expr (w->location);
1311 nw->with = as_a <c_expr *> (replace_id (w->with, id, with));
1312 nw->subexpr = replace_id (w->subexpr, id, with);
1313 return nw;
1314 }
1315 else if (if_expr *ife = dyn_cast <if_expr *> (o))
1316 {
1317 if_expr *nife = new if_expr (ife->location);
1318 nife->cond = as_a <c_expr *> (replace_id (ife->cond, id, with));
1319 nife->trueexpr = replace_id (ife->trueexpr, id, with);
1320 if (ife->falseexpr)
1321 nife->falseexpr = replace_id (ife->falseexpr, id, with);
1322 return nife;
1323 }
1324
1325 /* For c_expr we simply record a string replacement table which is
1326 applied at code-generation time. */
1327 if (c_expr *ce = dyn_cast<c_expr *> (o))
1328 {
1329 vec<c_expr::id_tab> ids = ce->ids.copy ();
1330 ids.safe_push (c_expr::id_tab (id->id, with->id));
1331 return new c_expr (ce->r, ce->location,
1332 ce->code, ce->nr_stmts, ids, ce->capture_ids);
1333 }
1334
1335 return o;
1336}
1337
1338/* Return true if the binary operator OP is ok for delayed substitution
1339 during for lowering. */
1340
1341static bool
1342binary_ok (operator_id *op)
1343{
1344 switch (op->code)
1345 {
1346 case PLUS_EXPR:
1347 case MINUS_EXPR:
1348 case MULT_EXPR:
1349 case TRUNC_DIV_EXPR:
1350 case CEIL_DIV_EXPR:
1351 case FLOOR_DIV_EXPR:
1352 case ROUND_DIV_EXPR:
1353 case TRUNC_MOD_EXPR:
1354 case CEIL_MOD_EXPR:
1355 case FLOOR_MOD_EXPR:
1356 case ROUND_MOD_EXPR:
1357 case RDIV_EXPR:
1358 case EXACT_DIV_EXPR:
1359 case MIN_EXPR:
1360 case MAX_EXPR:
1361 case BIT_IOR_EXPR:
1362 case BIT_XOR_EXPR:
1363 case BIT_AND_EXPR:
1364 return true;
1365 default:
1366 return false;
1367 }
1368}
1369
1370/* Lower recorded fors for SIN and output to SIMPLIFIERS. */
1371
1372static void
1373lower_for (simplify *sin, vec<simplify *>& simplifiers)
1374{
1375 vec<vec<user_id *> >& for_vec = sin->for_vec;
1376 unsigned worklist_start = 0;
1377 auto_vec<simplify *> worklist;
1378 worklist.safe_push (sin);
1379
1380 /* Lower each recorded for separately, operating on the
1381 set of simplifiers created by the previous one.
1382 Lower inner-to-outer so inner for substitutes can refer
1383 to operators replaced by outer fors. */
1384 for (int fi = for_vec.length () - 1; fi >= 0; --fi)
1385 {
1386 vec<user_id *>& ids = for_vec[fi];
1387 unsigned n_ids = ids.length ();
1388 unsigned max_n_opers = 0;
1389 bool can_delay_subst = (sin->kind == simplify::SIMPLIFY);
1390 for (unsigned i = 0; i < n_ids; ++i)
1391 {
1392 if (ids[i]->substitutes.length () > max_n_opers)
1393 max_n_opers = ids[i]->substitutes.length ();
1394 /* Require that all substitutes are of the same kind so that
1395 if we delay substitution to the result op code generation
1396 can look at the first substitute for deciding things like
1397 types of operands. */
1398 enum id_base::id_kind kind = ids[i]->substitutes[0]->kind;
1399 for (unsigned j = 0; j < ids[i]->substitutes.length (); ++j)
1400 if (ids[i]->substitutes[j]->kind != kind)
1401 can_delay_subst = false;
1402 else if (operator_id *op
1403 = dyn_cast <operator_id *> (ids[i]->substitutes[j]))
1404 {
1405 operator_id *op0
1406 = as_a <operator_id *> (ids[i]->substitutes[0]);
1407 if (strcmp (op->tcc, "tcc_comparison") == 0
1408 && strcmp (op0->tcc, "tcc_comparison") == 0)
1409 ;
1410 /* Unfortunately we can't just allow all tcc_binary. */
1411 else if (strcmp (op->tcc, "tcc_binary") == 0
1412 && strcmp (op0->tcc, "tcc_binary") == 0
1413 && binary_ok (op)
1414 && binary_ok (op0))
1415 ;
1416 else if ((strcmp (op->id + 1, "SHIFT_EXPR") == 0
1417 || strcmp (op->id + 1, "ROTATE_EXPR") == 0)
1418 && (strcmp (op0->id + 1, "SHIFT_EXPR") == 0
1419 || strcmp (op0->id + 1, "ROTATE_EXPR") == 0))
1420 ;
1421 else
1422 can_delay_subst = false;
1423 }
1424 else if (is_a <fn_id *> (ids[i]->substitutes[j]))
1425 ;
1426 else
1427 can_delay_subst = false;
1428 }
1429
1430 unsigned worklist_end = worklist.length ();
1431 for (unsigned si = worklist_start; si < worklist_end; ++si)
1432 {
1433 simplify *s = worklist[si];
1434 for (unsigned j = 0; j < max_n_opers; ++j)
1435 {
1436 operand *match_op = s->match;
1437 operand *result_op = s->result;
1438 auto_vec<std::pair<user_id *, id_base *> > subst (n_ids);
1439 bool skip = false;
1440 for (unsigned i = 0; i < n_ids; ++i)
1441 {
1442 user_id *id = ids[i];
1443 id_base *oper = id->substitutes[j % id->substitutes.length ()];
1444 if (oper == null_id
1445 && (contains_id (match_op, id)
1446 || contains_id (result_op, id)))
1447 {
1448 skip = true;
1449 break;
1450 }
1451 subst.quick_push (std::make_pair (id, oper));
1452 match_op = replace_id (match_op, id, oper);
1453 if (result_op
1454 && !can_delay_subst)
1455 result_op = replace_id (result_op, id, oper);
1456 }
1457 if (skip)
1458 continue;
1459
1460 simplify *ns = new simplify (s->kind, s->id, match_op, result_op,
1461 vNULL, s->capture_ids);
1462 ns->for_subst_vec.safe_splice (s->for_subst_vec);
1463 if (result_op
1464 && can_delay_subst)
1465 ns->for_subst_vec.safe_splice (subst);
1466
1467 worklist.safe_push (ns);
1468 }
1469 }
1470 worklist_start = worklist_end;
1471 }
1472
1473 /* Copy out the result from the last for lowering. */
1474 for (unsigned i = worklist_start; i < worklist.length (); ++i)
1475 simplifiers.safe_push (worklist[i]);
1476}
1477
1478/* Lower the AST for everything in SIMPLIFIERS. */
1479
1480static void
1481lower (vec<simplify *>& simplifiers, bool gimple)
1482{
1483 auto_vec<simplify *> out_simplifiers;
1484 for (unsigned i = 0; i < simplifiers.length (); ++i)
1485 lower_opt_convert (simplifiers[i], out_simplifiers);
1486
1487 simplifiers.truncate (0);
1488 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1489 lower_commutative (out_simplifiers[i], simplifiers);
1490
1491 out_simplifiers.truncate (0);
1492 if (gimple)
1493 for (unsigned i = 0; i < simplifiers.length (); ++i)
1494 lower_cond (simplifiers[i], out_simplifiers);
1495 else
1496 out_simplifiers.safe_splice (simplifiers);
1497
1498
1499 simplifiers.truncate (0);
1500 for (unsigned i = 0; i < out_simplifiers.length (); ++i)
1501 lower_for (out_simplifiers[i], simplifiers);
1502}
1503
1504
1505
1506
1507/* The decision tree built for generating GIMPLE and GENERIC pattern
1508 matching code. It represents the 'match' expression of all
1509 simplifies and has those as its leafs. */
1510
1511struct dt_simplify;
1512
1513/* A hash-map collecting semantically equivalent leafs in the decision
1514 tree for splitting out to separate functions. */
1515struct sinfo
1516{
1517 dt_simplify *s;
1518
1519 const char *fname;
1520 unsigned cnt;
1521};
1522
1523struct sinfo_hashmap_traits : simple_hashmap_traits<pointer_hash<dt_simplify>,
1524 sinfo *>
1525{
1526 static inline hashval_t hash (const key_type &);
1527 static inline bool equal_keys (const key_type &, const key_type &);
1528 template <typename T> static inline void remove (T &) {}
1529};
1530
1531typedef hash_map<void * /* unused */, sinfo *, sinfo_hashmap_traits>
1532 sinfo_map_t;
1533
1534/* Current simplifier ID we are processing during insertion into the
1535 decision tree. */
1536static unsigned current_id;
1537
1538/* Decision tree base class, used for DT_NODE. */
1539
1540struct dt_node
1541{
1542 enum dt_type { DT_NODE, DT_OPERAND, DT_TRUE, DT_MATCH, DT_SIMPLIFY };
1543
1544 enum dt_type type;
1545 unsigned level;
1546 dt_node *parent;
1547 vec<dt_node *> kids;
1548
1549 /* Statistics. */
1550 unsigned num_leafs;
1551 unsigned total_size;
1552 unsigned max_level;
1553
1554 dt_node (enum dt_type type_, dt_node *parent_)
1555 : type (type_), level (0), parent (parent_), kids (vNULL) {}
1556
1557 dt_node *append_node (dt_node *);
1558 dt_node *append_op (operand *, dt_node *parent, unsigned pos);
1559 dt_node *append_true_op (operand *, dt_node *parent, unsigned pos);
1560 dt_node *append_match_op (operand *, dt_operand *, dt_node *parent,
1561 unsigned pos);
1562 dt_node *append_simplify (simplify *, unsigned, dt_operand **);
1563
1564 virtual void gen (FILE *, int, bool) {}
1565
1566 void gen_kids (FILE *, int, bool);
1567 void gen_kids_1 (FILE *, int, bool,
1568 vec<dt_operand *>, vec<dt_operand *>, vec<dt_operand *>,
1569 vec<dt_operand *>, vec<dt_operand *>, vec<dt_node *>);
1570
1571 void analyze (sinfo_map_t &);
1572};
1573
1574/* Generic decision tree node used for DT_OPERAND, DT_MATCH and DT_TRUE. */
1575
1576struct dt_operand : public dt_node
1577{
1578 operand *op;
1579 dt_operand *match_dop;
1580 unsigned pos;
1581 bool value_match;
1582 unsigned for_id;
1583
1584 dt_operand (enum dt_type type, operand *op_, dt_operand *match_dop_,
1585 dt_operand *parent_, unsigned pos_)
1586 : dt_node (type, parent_), op (op_), match_dop (match_dop_),
1587 pos (pos_), value_match (false), for_id (current_id) {}
1588
1589 void gen (FILE *, int, bool);
1590 unsigned gen_predicate (FILE *, int, const char *, bool);
1591 unsigned gen_match_op (FILE *, int, const char *, bool);
1592
1593 unsigned gen_gimple_expr (FILE *, int);
1594 unsigned gen_generic_expr (FILE *, int, const char *);
1595
1596 char *get_name (char *);
1597 void gen_opname (char *, unsigned);
1598};
1599
1600/* Leaf node of the decision tree, used for DT_SIMPLIFY. */
1601
1602struct dt_simplify : public dt_node
1603{
1604 simplify *s;
1605 unsigned pattern_no;
1606 dt_operand **indexes;
1607 sinfo *info;
1608
1609 dt_simplify (simplify *s_, unsigned pattern_no_, dt_operand **indexes_)
1610 : dt_node (DT_SIMPLIFY, NULL), s (s_), pattern_no (pattern_no_),
1611 indexes (indexes_), info (NULL) {}
1612
1613 void gen_1 (FILE *, int, bool, operand *);
1614 void gen (FILE *f, int, bool);
1615};
1616
1617template<>
1618template<>
1619inline bool
1620is_a_helper <dt_operand *>::test (dt_node *n)
1621{
1622 return (n->type == dt_node::DT_OPERAND
1623 || n->type == dt_node::DT_MATCH
1624 || n->type == dt_node::DT_TRUE);
1625}
1626
1627template<>
1628template<>
1629inline bool
1630is_a_helper <dt_simplify *>::test (dt_node *n)
1631{
1632 return n->type == dt_node::DT_SIMPLIFY;
1633}
1634
1635
1636
1637/* A container for the actual decision tree. */
1638
1639struct decision_tree
1640{
1641 dt_node *root;
1642
1643 void insert (struct simplify *, unsigned);
1644 void gen (FILE *f, bool gimple);
1645 void print (FILE *f = stderr);
1646
1647 decision_tree () { root = new dt_node (dt_node::DT_NODE, NULL); }
1648
1649 static dt_node *insert_operand (dt_node *, operand *, dt_operand **indexes,
1650 unsigned pos = 0, dt_node *parent = 0);
1651 static dt_node *find_node (vec<dt_node *>&, dt_node *);
1652 static bool cmp_node (dt_node *, dt_node *);
1653 static void print_node (dt_node *, FILE *f = stderr, unsigned = 0);
1654};
1655
1656/* Compare two AST operands O1 and O2 and return true if they are equal. */
1657
1658bool
1659cmp_operand (operand *o1, operand *o2)
1660{
1661 if (!o1 || !o2 || o1->type != o2->type)
1662 return false;
1663
1664 if (o1->type == operand::OP_PREDICATE)
1665 {
1666 predicate *p1 = as_a<predicate *>(o1);
1667 predicate *p2 = as_a<predicate *>(o2);
1668 return p1->p == p2->p;
1669 }
1670 else if (o1->type == operand::OP_EXPR)
1671 {
1672 expr *e1 = static_cast<expr *>(o1);
1673 expr *e2 = static_cast<expr *>(o2);
1674 return (e1->operation == e2->operation
1675 && e1->is_generic == e2->is_generic);
1676 }
1677 else
1678 return false;
1679}
1680
1681/* Compare two decision tree nodes N1 and N2 and return true if they
1682 are equal. */
1683
1684bool
1685decision_tree::cmp_node (dt_node *n1, dt_node *n2)
1686{
1687 if (!n1 || !n2 || n1->type != n2->type)
1688 return false;
1689
1690 if (n1 == n2)
1691 return true;
1692
1693 if (n1->type == dt_node::DT_TRUE)
1694 return false;
1695
1696 if (n1->type == dt_node::DT_OPERAND)
1697 return cmp_operand ((as_a<dt_operand *> (n1))->op,
1698 (as_a<dt_operand *> (n2))->op);
1699 else if (n1->type == dt_node::DT_MATCH)
1700 return (((as_a<dt_operand *> (n1))->match_dop
1701 == (as_a<dt_operand *> (n2))->match_dop)
1702 && ((as_a<dt_operand *> (n1))->value_match
1703 == (as_a<dt_operand *> (n2))->value_match));
1704 return false;
1705}
1706
1707/* Search OPS for a decision tree node like P and return it if found. */
1708
1709dt_node *
1710decision_tree::find_node (vec<dt_node *>& ops, dt_node *p)
1711{
1712 /* We can merge adjacent DT_TRUE. */
1713 if (p->type == dt_node::DT_TRUE
1714 && !ops.is_empty ()
1715 && ops.last ()->type == dt_node::DT_TRUE)
1716 return ops.last ();
1717 dt_operand *true_node = NULL;
1718 for (int i = ops.length () - 1; i >= 0; --i)
1719 {
1720 /* But we can't merge across DT_TRUE nodes as they serve as
1721 pattern order barriers to make sure that patterns apply
1722 in order of appearance in case multiple matches are possible. */
1723 if (ops[i]->type == dt_node::DT_TRUE)
1724 {
1725 if (! true_node
1726 || as_a <dt_operand *> (ops[i])->for_id > true_node->for_id)
1727 true_node = as_a <dt_operand *> (ops[i]);
1728 }
1729 if (decision_tree::cmp_node (ops[i], p))
1730 {
1731 /* Unless we are processing the same pattern or the blocking
1732 pattern is before the one we are going to merge with. */
1733 if (true_node
1734 && true_node->for_id != current_id
1735 && true_node->for_id > as_a <dt_operand *> (ops[i])->for_id)
1736 {
1737 if (verbose >= 1)
1738 {
1739 source_location p_loc = 0;
1740 if (p->type == dt_node::DT_OPERAND)
1741 p_loc = as_a <dt_operand *> (p)->op->location;
1742 source_location op_loc = 0;
1743 if (ops[i]->type == dt_node::DT_OPERAND)
1744 op_loc = as_a <dt_operand *> (ops[i])->op->location;
1745 source_location true_loc = 0;
1746 true_loc = true_node->op->location;
1747 warning_at (p_loc,
1748 "failed to merge decision tree node");
1749 warning_at (op_loc,
1750 "with the following");
1751 warning_at (true_loc,
1752 "because of the following which serves as ordering "
1753 "barrier");
1754 }
1755 return NULL;
1756 }
1757 return ops[i];
1758 }
1759 }
1760 return NULL;
1761}
1762
1763/* Append N to the decision tree if it there is not already an existing
1764 identical child. */
1765
1766dt_node *
1767dt_node::append_node (dt_node *n)
1768{
1769 dt_node *kid;
1770
1771 kid = decision_tree::find_node (kids, n);
1772 if (kid)
1773 return kid;
1774
1775 kids.safe_push (n);
1776 n->level = this->level + 1;
1777
1778 return n;
1779}
1780
1781/* Append OP to the decision tree. */
1782
1783dt_node *
1784dt_node::append_op (operand *op, dt_node *parent, unsigned pos)
1785{
1786 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1787 dt_operand *n = new dt_operand (DT_OPERAND, op, 0, parent_, pos);
1788 return append_node (n);
1789}
1790
1791/* Append a DT_TRUE decision tree node. */
1792
1793dt_node *
1794dt_node::append_true_op (operand *op, dt_node *parent, unsigned pos)
1795{
1796 dt_operand *parent_ = safe_as_a<dt_operand *> (parent);
1797 dt_operand *n = new dt_operand (DT_TRUE, op, 0, parent_, pos);
1798 return append_node (n);
1799}
1800
1801/* Append a DT_MATCH decision tree node. */
1802
1803dt_node *
1804dt_node::append_match_op (operand *op, dt_operand *match_dop,
1805 dt_node *parent, unsigned pos)
1806{
1807 dt_operand *parent_ = as_a<dt_operand *> (parent);
1808 dt_operand *n = new dt_operand (DT_MATCH, op, match_dop, parent_, pos);
1809 return append_node (n);
1810}
1811
1812/* Append S to the decision tree. */
1813
1814dt_node *
1815dt_node::append_simplify (simplify *s, unsigned pattern_no,
1816 dt_operand **indexes)
1817{
1818 dt_simplify *n = new dt_simplify (s, pattern_no, indexes);
1819 for (unsigned i = 0; i < kids.length (); ++i)
1820 if (dt_simplify *s2 = dyn_cast <dt_simplify *> (kids[i]))
1821 {
1822 warning_at (s->match->location, "duplicate pattern");
1823 warning_at (s2->s->match->location, "previous pattern defined here");
1824 print_operand (s->match, stderr);
1825 fprintf (stderr, "\n");
1826 }
1827 return append_node (n);
1828}
1829
1830/* Analyze the node and its children. */
1831
1832void
1833dt_node::analyze (sinfo_map_t &map)
1834{
1835 num_leafs = 0;
1836 total_size = 1;
1837 max_level = level;
1838
1839 if (type == DT_SIMPLIFY)
1840 {
1841 /* Populate the map of equivalent simplifies. */
1842 dt_simplify *s = as_a <dt_simplify *> (this);
1843 bool existed;
1844 sinfo *&si = map.get_or_insert (s, &existed);
1845 if (!existed)
1846 {
1847 si = new sinfo;
1848 si->s = s;
1849 si->cnt = 1;
1850 si->fname = NULL;
1851 }
1852 else
1853 si->cnt++;
1854 s->info = si;
1855 num_leafs = 1;
1856 return;
1857 }
1858
1859 for (unsigned i = 0; i < kids.length (); ++i)
1860 {
1861 kids[i]->analyze (map);
1862 num_leafs += kids[i]->num_leafs;
1863 total_size += kids[i]->total_size;
1864 max_level = MAX (max_level, kids[i]->max_level);
1865 }
1866}
1867
1868/* Insert O into the decision tree and return the decision tree node found
1869 or created. */
1870
1871dt_node *
1872decision_tree::insert_operand (dt_node *p, operand *o, dt_operand **indexes,
1873 unsigned pos, dt_node *parent)
1874{
1875 dt_node *q, *elm = 0;
1876
1877 if (capture *c = dyn_cast<capture *> (o))
1878 {
1879 unsigned capt_index = c->where;
1880
1881 if (indexes[capt_index] == 0)
1882 {
1883 if (c->what)
1884 q = insert_operand (p, c->what, indexes, pos, parent);
1885 else
1886 {
1887 q = elm = p->append_true_op (o, parent, pos);
1888 goto at_assert_elm;
1889 }
1890 // get to the last capture
1891 for (operand *what = c->what;
1892 what && is_a<capture *> (what);
1893 c = as_a<capture *> (what), what = c->what)
1894 ;
1895
1896 if (!c->what)
1897 {
1898 unsigned cc_index = c->where;
1899 dt_operand *match_op = indexes[cc_index];
1900
1901 dt_operand temp (dt_node::DT_TRUE, 0, 0, 0, 0);
1902 elm = decision_tree::find_node (p->kids, &temp);
1903
1904 if (elm == 0)
1905 {
1906 dt_operand temp (dt_node::DT_MATCH, 0, match_op, 0, 0);
1907 temp.value_match = c->value_match;
1908 elm = decision_tree::find_node (p->kids, &temp);
1909 }
1910 }
1911 else
1912 {
1913 dt_operand temp (dt_node::DT_OPERAND, c->what, 0, 0, 0);
1914 elm = decision_tree::find_node (p->kids, &temp);
1915 }
1916
1917at_assert_elm:
1918 gcc_assert (elm->type == dt_node::DT_TRUE
1919 || elm->type == dt_node::DT_OPERAND
1920 || elm->type == dt_node::DT_MATCH);
1921 indexes[capt_index] = static_cast<dt_operand *> (elm);
1922 return q;
1923 }
1924 else
1925 {
1926 p = p->append_match_op (o, indexes[capt_index], parent, pos);
1927 as_a <dt_operand *>(p)->value_match = c->value_match;
1928 if (c->what)
1929 return insert_operand (p, c->what, indexes, 0, p);
1930 else
1931 return p;
1932 }
1933 }
1934 p = p->append_op (o, parent, pos);
1935 q = p;
1936
1937 if (expr *e = dyn_cast <expr *>(o))
1938 {
1939 for (unsigned i = 0; i < e->ops.length (); ++i)
1940 q = decision_tree::insert_operand (q, e->ops[i], indexes, i, p);
1941 }
1942
1943 return q;
1944}
1945
1946/* Insert S into the decision tree. */
1947
1948void
1949decision_tree::insert (struct simplify *s, unsigned pattern_no)
1950{
1951 current_id = s->id;
1952 dt_operand **indexes = XCNEWVEC (dt_operand *, s->capture_max + 1);
1953 dt_node *p = decision_tree::insert_operand (root, s->match, indexes);
1954 p->append_simplify (s, pattern_no, indexes);
1955}
1956
1957/* Debug functions to dump the decision tree. */
1958
1959DEBUG_FUNCTION void
1960decision_tree::print_node (dt_node *p, FILE *f, unsigned indent)
1961{
1962 if (p->type == dt_node::DT_NODE)
1963 fprintf (f, "root");
1964 else
1965 {
1966 fprintf (f, "|");
1967 for (unsigned i = 0; i < indent; i++)
1968 fprintf (f, "-");
1969
1970 if (p->type == dt_node::DT_OPERAND)
1971 {
1972 dt_operand *dop = static_cast<dt_operand *>(p);
1973 print_operand (dop->op, f, true);
1974 }
1975 else if (p->type == dt_node::DT_TRUE)
1976 fprintf (f, "true");
1977 else if (p->type == dt_node::DT_MATCH)
1978 fprintf (f, "match (%p)", (void *)((as_a<dt_operand *>(p))->match_dop));
1979 else if (p->type == dt_node::DT_SIMPLIFY)
1980 {
1981 dt_simplify *s = static_cast<dt_simplify *> (p);
1982 fprintf (f, "simplify_%u { ", s->pattern_no);
1983 for (int i = 0; i <= s->s->capture_max; ++i)
1984 fprintf (f, "%p, ", (void *) s->indexes[i]);
1985 fprintf (f, " } ");
1986 }
1987 if (is_a <dt_operand *> (p))
1988 fprintf (f, " [%u]", as_a <dt_operand *> (p)->for_id);
1989 }
1990
1991 fprintf (stderr, " (%p, %p), %u, %u\n",
1992 (void *) p, (void *) p->parent, p->level, p->kids.length ());
1993
1994 for (unsigned i = 0; i < p->kids.length (); ++i)
1995 decision_tree::print_node (p->kids[i], f, indent + 2);
1996}
1997
1998DEBUG_FUNCTION void
1999decision_tree::print (FILE *f)
2000{
2001 return decision_tree::print_node (root, f);
2002}
2003
2004
2005/* For GENERIC we have to take care of wrapping multiple-used
2006 expressions with side-effects in save_expr and preserve side-effects
2007 of expressions with omit_one_operand. Analyze captures in
2008 match, result and with expressions and perform early-outs
2009 on the outermost match expression operands for cases we cannot
2010 handle. */
2011
2012struct capture_info
2013{
2014 capture_info (simplify *s, operand *, bool);
2015 void walk_match (operand *o, unsigned toplevel_arg, bool, bool);
2016 bool walk_result (operand *o, bool, operand *);
2017 void walk_c_expr (c_expr *);
2018
2019 struct cinfo
2020 {
2021 bool expr_p;
2022 bool cse_p;
2023 bool force_no_side_effects_p;
2024 bool force_single_use;
2025 bool cond_expr_cond_p;
2026 unsigned long toplevel_msk;
2027 unsigned match_use_count;
2028 unsigned result_use_count;
2029 unsigned same_as;
2030 capture *c;
2031 };
2032
2033 auto_vec<cinfo> info;
2034 unsigned long force_no_side_effects;
2035 bool gimple;
2036};
2037
2038/* Analyze captures in S. */
2039
2040capture_info::capture_info (simplify *s, operand *result, bool gimple_)
2041{
2042 gimple = gimple_;
2043
2044 expr *e;
2045 if (s->kind == simplify::MATCH)
2046 {
2047 force_no_side_effects = -1;
2048 return;
2049 }
2050
2051 force_no_side_effects = 0;
2052 info.safe_grow_cleared (s->capture_max + 1);
2053 for (int i = 0; i <= s->capture_max; ++i)
2054 info[i].same_as = i;
2055
2056 e = as_a <expr *> (s->match);
2057 for (unsigned i = 0; i < e->ops.length (); ++i)
2058 walk_match (e->ops[i], i,
2059 (i != 0 && *e->operation == COND_EXPR)
2060 || *e->operation == TRUTH_ANDIF_EXPR
2061 || *e->operation == TRUTH_ORIF_EXPR,
2062 i == 0
2063 && (*e->operation == COND_EXPR
2064 || *e->operation == VEC_COND_EXPR));
2065
2066 walk_result (s->result, false, result);
2067}
2068
2069/* Analyze captures in the match expression piece O. */
2070
2071void
2072capture_info::walk_match (operand *o, unsigned toplevel_arg,
2073 bool conditional_p, bool cond_expr_cond_p)
2074{
2075 if (capture *c = dyn_cast <capture *> (o))
2076 {
2077 unsigned where = c->where;
2078 info[where].match_use_count++;
2079 info[where].toplevel_msk |= 1 << toplevel_arg;
2080 info[where].force_no_side_effects_p |= conditional_p;
2081 info[where].cond_expr_cond_p |= cond_expr_cond_p;
2082 if (!info[where].c)
2083 info[where].c = c;
2084 if (!c->what)
2085 return;
2086 /* Recurse to exprs and captures. */
2087 if (is_a <capture *> (c->what)
2088 || is_a <expr *> (c->what))
2089 walk_match (c->what, toplevel_arg, conditional_p, false);
2090 /* We need to look past multiple captures to find a captured
2091 expression as with conditional converts two captures
2092 can be collapsed onto the same expression. Also collect
2093 what captures capture the same thing. */
2094 while (c->what && is_a <capture *> (c->what))
2095 {
2096 c = as_a <capture *> (c->what);
2097 if (info[c->where].same_as != c->where
2098 && info[c->where].same_as != info[where].same_as)
2099 fatal_at (c->location, "cannot handle this collapsed capture");
2100 info[c->where].same_as = info[where].same_as;
2101 }
2102 /* Mark expr (non-leaf) captures and forced single-use exprs. */
2103 expr *e;
2104 if (c->what
2105 && (e = dyn_cast <expr *> (c->what)))
2106 {
2107 info[where].expr_p = true;
2108 info[where].force_single_use |= e->force_single_use;
2109 }
2110 }
2111 else if (expr *e = dyn_cast <expr *> (o))
2112 {
2113 for (unsigned i = 0; i < e->ops.length (); ++i)
2114 {
2115 bool cond_p = conditional_p;
2116 bool cond_expr_cond_p = false;
2117 if (i != 0 && *e->operation == COND_EXPR)
2118 cond_p = true;
2119 else if (*e->operation == TRUTH_ANDIF_EXPR
2120 || *e->operation == TRUTH_ORIF_EXPR)
2121 cond_p = true;
2122 if (i == 0
2123 && (*e->operation == COND_EXPR
2124 || *e->operation == VEC_COND_EXPR))
2125 cond_expr_cond_p = true;
2126 walk_match (e->ops[i], toplevel_arg, cond_p, cond_expr_cond_p);
2127 }
2128 }
2129 else if (is_a <predicate *> (o))
2130 {
2131 /* Mark non-captured leafs toplevel arg for checking. */
2132 force_no_side_effects |= 1 << toplevel_arg;
2133 if (verbose >= 1
2134 && !gimple)
2135 warning_at (o->location,
2136 "forcing no side-effects on possibly lost leaf");
2137 }
2138 else
2139 gcc_unreachable ();
2140}
2141
2142/* Analyze captures in the result expression piece O. Return true
2143 if RESULT was visited in one of the children. Only visit
2144 non-if/with children if they are rooted on RESULT. */
2145
2146bool
2147capture_info::walk_result (operand *o, bool conditional_p, operand *result)
2148{
2149 if (capture *c = dyn_cast <capture *> (o))
2150 {
2151 unsigned where = info[c->where].same_as;
2152 info[where].result_use_count++;
2153 /* If we substitute an expression capture we don't know
2154 which captures this will end up using (well, we don't
2155 compute that). Force the uses to be side-effect free
2156 which means forcing the toplevels that reach the
2157 expression side-effect free. */
2158 if (info[where].expr_p)
2159 force_no_side_effects |= info[where].toplevel_msk;
2160 /* Mark CSE capture uses as forced to have no side-effects. */
2161 if (c->what
2162 && is_a <expr *> (c->what))
2163 {
2164 info[where].cse_p = true;
2165 walk_result (c->what, true, result);
2166 }
2167 }
2168 else if (expr *e = dyn_cast <expr *> (o))
2169 {
2170 id_base *opr = e->operation;
2171 if (user_id *uid = dyn_cast <user_id *> (opr))
2172 opr = uid->substitutes[0];
2173 for (unsigned i = 0; i < e->ops.length (); ++i)
2174 {
2175 bool cond_p = conditional_p;
2176 if (i != 0 && *e->operation == COND_EXPR)
2177 cond_p = true;
2178 else if (*e->operation == TRUTH_ANDIF_EXPR
2179 || *e->operation == TRUTH_ORIF_EXPR)
2180 cond_p = true;
2181 walk_result (e->ops[i], cond_p, result);
2182 }
2183 }
2184 else if (if_expr *e = dyn_cast <if_expr *> (o))
2185 {
2186 /* 'if' conditions should be all fine. */
2187 if (e->trueexpr == result)
2188 {
2189 walk_result (e->trueexpr, false, result);
2190 return true;
2191 }
2192 if (e->falseexpr == result)
2193 {
2194 walk_result (e->falseexpr, false, result);
2195 return true;
2196 }
2197 bool res = false;
2198 if (is_a <if_expr *> (e->trueexpr)
2199 || is_a <with_expr *> (e->trueexpr))
2200 res |= walk_result (e->trueexpr, false, result);
2201 if (e->falseexpr
2202 && (is_a <if_expr *> (e->falseexpr)
2203 || is_a <with_expr *> (e->falseexpr)))
2204 res |= walk_result (e->falseexpr, false, result);
2205 return res;
2206 }
2207 else if (with_expr *e = dyn_cast <with_expr *> (o))
2208 {
2209 bool res = (e->subexpr == result);
2210 if (res
2211 || is_a <if_expr *> (e->subexpr)
2212 || is_a <with_expr *> (e->subexpr))
2213 res |= walk_result (e->subexpr, false, result);
2214 if (res)
2215 walk_c_expr (e->with);
2216 return res;
2217 }
2218 else if (c_expr *e = dyn_cast <c_expr *> (o))
2219 walk_c_expr (e);
2220 else
2221 gcc_unreachable ();
2222
2223 return false;
2224}
2225
2226/* Look for captures in the C expr E. */
2227
2228void
2229capture_info::walk_c_expr (c_expr *e)
2230{
2231 /* Give up for C exprs mentioning captures not inside TREE_TYPE,
2232 TREE_REAL_CST, TREE_CODE or a predicate where they cannot
2233 really escape through. */
2234 unsigned p_depth = 0;
2235 for (unsigned i = 0; i < e->code.length (); ++i)
2236 {
2237 const cpp_token *t = &e->code[i];
2238 const cpp_token *n = i < e->code.length () - 1 ? &e->code[i+1] : NULL;
2239 id_base *id;
2240 if (t->type == CPP_NAME
2241 && (strcmp ((const char *)CPP_HASHNODE
2242 (t->val.node.node)->ident.str, "TREE_TYPE") == 0
2243 || strcmp ((const char *)CPP_HASHNODE
2244 (t->val.node.node)->ident.str, "TREE_CODE") == 0
2245 || strcmp ((const char *)CPP_HASHNODE
2246 (t->val.node.node)->ident.str, "TREE_REAL_CST") == 0
2247 || ((id = get_operator ((const char *)CPP_HASHNODE
2248 (t->val.node.node)->ident.str))
2249 && is_a <predicate_id *> (id)))
2250 && n->type == CPP_OPEN_PAREN)
2251 p_depth++;
2252 else if (t->type == CPP_CLOSE_PAREN
2253 && p_depth > 0)
2254 p_depth--;
2255 else if (p_depth == 0
2256 && t->type == CPP_ATSIGN
2257 && (n->type == CPP_NUMBER
2258 || n->type == CPP_NAME)
2259 && !(n->flags & PREV_WHITE))
2260 {
2261 const char *id;
2262 if (n->type == CPP_NUMBER)
2263 id = (const char *)n->val.str.text;
2264 else
2265 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2266 unsigned *where = e->capture_ids->get(id);
2267 if (! where)
2268 fatal_at (n, "unknown capture id '%s'", id);
2269 info[info[*where].same_as].force_no_side_effects_p = true;
2270 if (verbose >= 1
2271 && !gimple)
2272 warning_at (t, "capture escapes");
2273 }
2274 }
2275}
2276
2277
2278/* Code generation off the decision tree and the refered AST nodes. */
2279
2280bool
2281is_conversion (id_base *op)
2282{
2283 return (*op == CONVERT_EXPR
2284 || *op == NOP_EXPR
2285 || *op == FLOAT_EXPR
2286 || *op == FIX_TRUNC_EXPR
2287 || *op == VIEW_CONVERT_EXPR);
2288}
2289
2290/* Get the type to be used for generating operand POS of OP from the
2291 various sources. */
2292
2293static const char *
2294get_operand_type (id_base *op, unsigned pos,
2295 const char *in_type,
2296 const char *expr_type,
2297 const char *other_oprnd_type)
2298{
2299 /* Generally operands whose type does not match the type of the
2300 expression generated need to know their types but match and
2301 thus can fall back to 'other_oprnd_type'. */
2302 if (is_conversion (op))
2303 return other_oprnd_type;
2304 else if (*op == REALPART_EXPR
2305 || *op == IMAGPART_EXPR)
2306 return other_oprnd_type;
2307 else if (is_a <operator_id *> (op)
2308 && strcmp (as_a <operator_id *> (op)->tcc, "tcc_comparison") == 0)
2309 return other_oprnd_type;
2310 else if (*op == COND_EXPR
2311 && pos == 0)
2312 return "boolean_type_node";
2313 else
2314 {
2315 /* Otherwise all types should match - choose one in order of
2316 preference. */
2317 if (expr_type)
2318 return expr_type;
2319 else if (in_type)
2320 return in_type;
2321 else
2322 return other_oprnd_type;
2323 }
2324}
2325
2326/* Generate transform code for an expression. */
2327
2328void
2329expr::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2330 int depth, const char *in_type, capture_info *cinfo,
2331 dt_operand **indexes, int)
2332{
2333 id_base *opr = operation;
2334 /* When we delay operator substituting during lowering of fors we
2335 make sure that for code-gen purposes the effects of each substitute
2336 are the same. Thus just look at that. */
2337 if (user_id *uid = dyn_cast <user_id *> (opr))
2338 opr = uid->substitutes[0];
2339
2340 bool conversion_p = is_conversion (opr);
2341 const char *type = expr_type;
2342 char optype[64];
2343 if (type)
2344 /* If there was a type specification in the pattern use it. */
2345 ;
2346 else if (conversion_p)
2347 /* For conversions we need to build the expression using the
2348 outer type passed in. */
2349 type = in_type;
2350 else if (*opr == REALPART_EXPR
2351 || *opr == IMAGPART_EXPR)
2352 {
2353 /* __real and __imag use the component type of its operand. */
2354 sprintf (optype, "TREE_TYPE (TREE_TYPE (ops%d[0]))", depth);
2355 type = optype;
2356 }
2357 else if (is_a <operator_id *> (opr)
2358 && !strcmp (as_a <operator_id *> (opr)->tcc, "tcc_comparison"))
2359 {
2360 /* comparisons use boolean_type_node (or what gets in), but
2361 their operands need to figure out the types themselves. */
2362 if (in_type)
2363 type = in_type;
2364 else
2365 {
2366 sprintf (optype, "boolean_type_node");
2367 type = optype;
2368 }
2369 in_type = NULL;
2370 }
2371 else if (*opr == COND_EXPR
2372 || *opr == VEC_COND_EXPR)
2373 {
2374 /* Conditions are of the same type as their first alternative. */
2375 sprintf (optype, "TREE_TYPE (ops%d[1])", depth);
2376 type = optype;
2377 }
2378 else
2379 {
2380 /* Other operations are of the same type as their first operand. */
2381 sprintf (optype, "TREE_TYPE (ops%d[0])", depth);
2382 type = optype;
2383 }
2384 if (!type)
2385 fatal_at (location, "cannot determine type of operand");
2386
2387 fprintf_indent (f, indent, "{\n");
2388 indent += 2;
2389 fprintf_indent (f, indent, "tree ops%d[%u], res;\n", depth, ops.length ());
2390 char op0type[64];
2391 snprintf (op0type, 64, "TREE_TYPE (ops%d[0])", depth);
2392 for (unsigned i = 0; i < ops.length (); ++i)
2393 {
2394 char dest[32];
2395 snprintf (dest, 32, "ops%d[%u]", depth, i);
2396 const char *optype
2397 = get_operand_type (opr, i, in_type, expr_type,
2398 i == 0 ? NULL : op0type);
2399 ops[i]->gen_transform (f, indent, dest, gimple, depth + 1, optype,
2400 cinfo, indexes,
2401 (*opr == COND_EXPR
2402 || *opr == VEC_COND_EXPR) && i == 0 ? 1 : 2);
2403 }
2404
2405 const char *opr_name;
2406 if (*operation == CONVERT_EXPR)
2407 opr_name = "NOP_EXPR";
2408 else
2409 opr_name = operation->id;
2410
2411 if (gimple)
2412 {
2413 if (*opr == CONVERT_EXPR)
2414 {
2415 fprintf_indent (f, indent,
2416 "if (%s != TREE_TYPE (ops%d[0])\n",
2417 type, depth);
2418 fprintf_indent (f, indent,
2419 " && !useless_type_conversion_p (%s, TREE_TYPE (ops%d[0])))\n",
2420 type, depth);
2421 fprintf_indent (f, indent + 2, "{\n");
2422 indent += 4;
2423 }
2424 /* ??? Building a stmt can fail for various reasons here, seq being
2425 NULL or the stmt referencing SSA names occuring in abnormal PHIs.
2426 So if we fail here we should continue matching other patterns. */
2427 fprintf_indent (f, indent, "code_helper tem_code = %s;\n", opr_name);
2428 fprintf_indent (f, indent, "tree tem_ops[3] = { ");
2429 for (unsigned i = 0; i < ops.length (); ++i)
2430 fprintf (f, "ops%d[%u]%s", depth, i,
2431 i == ops.length () - 1 ? " };\n" : ", ");
2432 fprintf_indent (f, indent,
2433 "gimple_resimplify%d (lseq, &tem_code, %s, tem_ops, valueize);\n",
2434 ops.length (), type);
2435 fprintf_indent (f, indent,
2436 "res = maybe_push_res_to_seq (tem_code, %s, tem_ops, lseq);\n",
2437 type);
2438 fprintf_indent (f, indent,
2439 "if (!res) return false;\n");
2440 if (*opr == CONVERT_EXPR)
2441 {
2442 indent -= 4;
2443 fprintf_indent (f, indent, " }\n");
2444 fprintf_indent (f, indent, "else\n");
2445 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2446 }
2447 }
2448 else
2449 {
2450 if (*opr == CONVERT_EXPR)
2451 {
2452 fprintf_indent (f, indent, "if (TREE_TYPE (ops%d[0]) != %s)\n",
2453 depth, type);
2454 indent += 2;
2455 }
2456 if (opr->kind == id_base::CODE)
2457 fprintf_indent (f, indent, "res = fold_build%d_loc (loc, %s, %s",
2458 ops.length(), opr_name, type);
2459 else
2460 {
2461 fprintf_indent (f, indent, "{\n");
2462 fprintf_indent (f, indent, " res = maybe_build_call_expr_loc (loc, "
2463 "%s, %s, %d", opr_name, type, ops.length());
2464 }
2465 for (unsigned i = 0; i < ops.length (); ++i)
2466 fprintf (f, ", ops%d[%u]", depth, i);
2467 fprintf (f, ");\n");
2468 if (opr->kind != id_base::CODE)
2469 {
2470 fprintf_indent (f, indent, " if (!res)\n");
2471 fprintf_indent (f, indent, " return NULL_TREE;\n");
2472 fprintf_indent (f, indent, "}\n");
2473 }
2474 if (*opr == CONVERT_EXPR)
2475 {
2476 indent -= 2;
2477 fprintf_indent (f, indent, "else\n");
2478 fprintf_indent (f, indent, " res = ops%d[0];\n", depth);
2479 }
2480 }
2481 fprintf_indent (f, indent, "%s = res;\n", dest);
2482 indent -= 2;
2483 fprintf_indent (f, indent, "}\n");
2484}
2485
2486/* Generate code for a c_expr which is either the expression inside
2487 an if statement or a sequence of statements which computes a
2488 result to be stored to DEST. */
2489
2490void
2491c_expr::gen_transform (FILE *f, int indent, const char *dest,
2492 bool, int, const char *, capture_info *,
2493 dt_operand **, int)
2494{
2495 if (dest && nr_stmts == 1)
2496 fprintf_indent (f, indent, "%s = ", dest);
2497
2498 unsigned stmt_nr = 1;
2499 for (unsigned i = 0; i < code.length (); ++i)
2500 {
2501 const cpp_token *token = &code[i];
2502
2503 /* Replace captures for code-gen. */
2504 if (token->type == CPP_ATSIGN)
2505 {
2506 const cpp_token *n = &code[i+1];
2507 if ((n->type == CPP_NUMBER
2508 || n->type == CPP_NAME)
2509 && !(n->flags & PREV_WHITE))
2510 {
2511 if (token->flags & PREV_WHITE)
2512 fputc (' ', f);
2513 const char *id;
2514 if (n->type == CPP_NUMBER)
2515 id = (const char *)n->val.str.text;
2516 else
2517 id = (const char *)CPP_HASHNODE (n->val.node.node)->ident.str;
2518 unsigned *cid = capture_ids->get (id);
2519 if (!cid)
2520 fatal_at (token, "unknown capture id");
2521 fprintf (f, "captures[%u]", *cid);
2522 ++i;
2523 continue;
2524 }
2525 }
2526
2527 if (token->flags & PREV_WHITE)
2528 fputc (' ', f);
2529
2530 if (token->type == CPP_NAME)
2531 {
2532 const char *id = (const char *) NODE_NAME (token->val.node.node);
2533 unsigned j;
2534 for (j = 0; j < ids.length (); ++j)
2535 {
2536 if (strcmp (id, ids[j].id) == 0)
2537 {
2538 fprintf (f, "%s", ids[j].oper);
2539 break;
2540 }
2541 }
2542 if (j < ids.length ())
2543 continue;
2544 }
2545
2546 /* Output the token as string. */
2547 char *tk = (char *)cpp_token_as_text (r, token);
2548 fputs (tk, f);
2549
2550 if (token->type == CPP_SEMICOLON)
2551 {
2552 stmt_nr++;
2553 fputc ('\n', f);
2554 if (dest && stmt_nr == nr_stmts)
2555 fprintf_indent (f, indent, "%s = ", dest);
2556 }
2557 }
2558}
2559
2560/* Generate transform code for a capture. */
2561
2562void
2563capture::gen_transform (FILE *f, int indent, const char *dest, bool gimple,
2564 int depth, const char *in_type, capture_info *cinfo,
2565 dt_operand **indexes, int cond_handling)
2566{
2567 if (what && is_a<expr *> (what))
2568 {
2569 if (indexes[where] == 0)
2570 {
2571 char buf[20];
2572 sprintf (buf, "captures[%u]", where);
2573 what->gen_transform (f, indent, buf, gimple, depth, in_type,
2574 cinfo, NULL);
2575 }
2576 }
2577
2578 /* If in GENERIC some capture is used multiple times, unshare it except
2579 when emitting the last use. */
2580 if (!gimple
2581 && cinfo->info.exists ()
2582 && cinfo->info[cinfo->info[where].same_as].result_use_count > 1)
2583 {
2584 fprintf_indent (f, indent, "%s = unshare_expr (captures[%u]);\n",
2585 dest, where);
2586 cinfo->info[cinfo->info[where].same_as].result_use_count--;
2587 }
2588 else
2589 fprintf_indent (f, indent, "%s = captures[%u];\n", dest, where);
2590
2591 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
2592 with substituting a capture of that. */
2593 if (gimple
2594 && cond_handling != 0
2595 && cinfo->info[where].cond_expr_cond_p)
2596 {
2597 /* If substituting into a cond_expr condition, unshare. */
2598 if (cond_handling == 1)
2599 fprintf_indent (f, indent, "%s = unshare_expr (%s);\n", dest, dest);
2600 /* If substituting elsewhere we might need to decompose it. */
2601 else if (cond_handling == 2)
2602 {
2603 /* ??? Returning false here will also not allow any other patterns
2604 to match unless this generator was split out. */
2605 fprintf_indent (f, indent, "if (COMPARISON_CLASS_P (%s))\n", dest);
2606 fprintf_indent (f, indent, " {\n");
2607 fprintf_indent (f, indent, " if (!seq) return false;\n");
2608 fprintf_indent (f, indent, " %s = gimple_build (seq,"
2609 " TREE_CODE (%s),"
2610 " TREE_TYPE (%s), TREE_OPERAND (%s, 0),"
2611 " TREE_OPERAND (%s, 1));\n",
2612 dest, dest, dest, dest, dest);
2613 fprintf_indent (f, indent, " }\n");
2614 }
2615 }
2616}
2617
2618/* Return the name of the operand representing the decision tree node.
2619 Use NAME as space to generate it. */
2620
2621char *
2622dt_operand::get_name (char *name)
2623{
2624 if (! parent)
2625 sprintf (name, "t");
2626 else if (parent->level == 1)
2627 sprintf (name, "op%u", pos);
2628 else if (parent->type == dt_node::DT_MATCH)
2629 return as_a <dt_operand *> (parent)->get_name (name);
2630 else
2631 sprintf (name, "o%u%u", parent->level, pos);
2632 return name;
2633}
2634
2635/* Fill NAME with the operand name at position POS. */
2636
2637void
2638dt_operand::gen_opname (char *name, unsigned pos)
2639{
2640 if (! parent)
2641 sprintf (name, "op%u", pos);
2642 else
2643 sprintf (name, "o%u%u", level, pos);
2644}
2645
2646/* Generate matching code for the decision tree operand which is
2647 a predicate. */
2648
2649unsigned
2650dt_operand::gen_predicate (FILE *f, int indent, const char *opname, bool gimple)
2651{
2652 predicate *p = as_a <predicate *> (op);
2653
2654 if (p->p->matchers.exists ())
2655 {
2656 /* If this is a predicate generated from a pattern mangle its
2657 name and pass on the valueize hook. */
2658 if (gimple)
2659 fprintf_indent (f, indent, "if (gimple_%s (%s, valueize))\n",
2660 p->p->id, opname);
2661 else
2662 fprintf_indent (f, indent, "if (tree_%s (%s))\n", p->p->id, opname);
2663 }
2664 else
2665 fprintf_indent (f, indent, "if (%s (%s))\n", p->p->id, opname);
2666 fprintf_indent (f, indent + 2, "{\n");
2667 return 1;
2668}
2669
2670/* Generate matching code for the decision tree operand which is
2671 a capture-match. */
2672
2673unsigned
2674dt_operand::gen_match_op (FILE *f, int indent, const char *opname, bool)
2675{
2676 char match_opname[20];
2677 match_dop->get_name (match_opname);
2678 if (value_match)
2679 fprintf_indent (f, indent, "if (%s == %s || operand_equal_p (%s, %s, 0))\n",
2680 opname, match_opname, opname, match_opname);
2681 else
2682 fprintf_indent (f, indent, "if (%s == %s || (operand_equal_p (%s, %s, 0) "
2683 "&& types_match (%s, %s)))\n",
2684 opname, match_opname, opname, match_opname,
2685 opname, match_opname);
2686 fprintf_indent (f, indent + 2, "{\n");
2687 return 1;
2688}
2689
2690/* Generate GIMPLE matching code for the decision tree operand. */
2691
2692unsigned
2693dt_operand::gen_gimple_expr (FILE *f, int indent)
2694{
2695 expr *e = static_cast<expr *> (op);
2696 id_base *id = e->operation;
2697 unsigned n_ops = e->ops.length ();
2698 unsigned n_braces = 0;
2699
2700 for (unsigned i = 0; i < n_ops; ++i)
2701 {
2702 char child_opname[20];
2703 gen_opname (child_opname, i);
2704
2705 if (id->kind == id_base::CODE)
2706 {
2707 if (e->is_generic
2708 || *id == REALPART_EXPR || *id == IMAGPART_EXPR
2709 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR)
2710 {
2711 /* ??? If this is a memory operation we can't (and should not)
2712 match this. The only sensible operand types are
2713 SSA names and invariants. */
2714 if (e->is_generic)
2715 {
2716 char opname[20];
2717 get_name (opname);
2718 fprintf_indent (f, indent,
2719 "tree %s = TREE_OPERAND (%s, %i);\n",
2720 child_opname, opname, i);
2721 }
2722 else
2723 fprintf_indent (f, indent,
2724 "tree %s = TREE_OPERAND "
2725 "(gimple_assign_rhs1 (def), %i);\n",
2726 child_opname, i);
2727 fprintf_indent (f, indent,
2728 "if ((TREE_CODE (%s) == SSA_NAME\n",
2729 child_opname);
2730 fprintf_indent (f, indent,
2731 " || is_gimple_min_invariant (%s)))\n",
2732 child_opname);
2733 fprintf_indent (f, indent,
2734 " {\n");
2735 indent += 4;
2736 n_braces++;
2737 fprintf_indent (f, indent,
2738 "%s = do_valueize (valueize, %s);\n",
2739 child_opname, child_opname);
2740 continue;
2741 }
2742 else
2743 fprintf_indent (f, indent,
2744 "tree %s = gimple_assign_rhs%u (def);\n",
2745 child_opname, i + 1);
2746 }
2747 else
2748 fprintf_indent (f, indent,
2749 "tree %s = gimple_call_arg (def, %u);\n",
2750 child_opname, i);
2751 fprintf_indent (f, indent,
2752 "%s = do_valueize (valueize, %s);\n",
2753 child_opname, child_opname);
2754 }
2755 /* While the toplevel operands are canonicalized by the caller
2756 after valueizing operands of sub-expressions we have to
2757 re-canonicalize operand order. */
2758 if (operator_id *code = dyn_cast <operator_id *> (id))
2759 {
2760 /* ??? We can't canonicalize tcc_comparison operands here
2761 because that requires changing the comparison code which
2762 we already matched... */
2763 if (commutative_tree_code (code->code)
2764 || commutative_ternary_tree_code (code->code))
2765 {
2766 char child_opname0[20], child_opname1[20];
2767 gen_opname (child_opname0, 0);
2768 gen_opname (child_opname1, 1);
2769 fprintf_indent (f, indent,
2770 "if (tree_swap_operands_p (%s, %s))\n",
2771 child_opname0, child_opname1);
2772 fprintf_indent (f, indent,
2773 " std::swap (%s, %s);\n",
2774 child_opname0, child_opname1);
2775 }
2776 }
2777
2778 return n_braces;
2779}
2780
2781/* Generate GENERIC matching code for the decision tree operand. */
2782
2783unsigned
2784dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname)
2785{
2786 expr *e = static_cast<expr *> (op);
2787 unsigned n_ops = e->ops.length ();
2788
2789 for (unsigned i = 0; i < n_ops; ++i)
2790 {
2791 char child_opname[20];
2792 gen_opname (child_opname, i);
2793
2794 if (e->operation->kind == id_base::CODE)
2795 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n",
2796 child_opname, opname, i);
2797 else
2798 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n",
2799 child_opname, opname, i);
2800 }
2801
2802 return 0;
2803}
2804
2805/* Generate matching code for the children of the decision tree node. */
2806
2807void
2808dt_node::gen_kids (FILE *f, int indent, bool gimple)
2809{
2810 auto_vec<dt_operand *> gimple_exprs;
2811 auto_vec<dt_operand *> generic_exprs;
2812 auto_vec<dt_operand *> fns;
2813 auto_vec<dt_operand *> generic_fns;
2814 auto_vec<dt_operand *> preds;
2815 auto_vec<dt_node *> others;
2816
2817 for (unsigned i = 0; i < kids.length (); ++i)
2818 {
2819 if (kids[i]->type == dt_node::DT_OPERAND)
2820 {
2821 dt_operand *op = as_a<dt_operand *> (kids[i]);
2822 if (expr *e = dyn_cast <expr *> (op->op))
2823 {
2824 if (e->ops.length () == 0
2825 && (!gimple || !(*e->operation == CONSTRUCTOR)))
2826 generic_exprs.safe_push (op);
2827 else if (e->operation->kind == id_base::FN)
2828 {
2829 if (gimple)
2830 fns.safe_push (op);
2831 else
2832 generic_fns.safe_push (op);
2833 }
2834 else if (e->operation->kind == id_base::PREDICATE)
2835 preds.safe_push (op);
2836 else
2837 {
2838 if (gimple && !e->is_generic)
2839 gimple_exprs.safe_push (op);
2840 else
2841 generic_exprs.safe_push (op);
2842 }
2843 }
2844 else if (op->op->type == operand::OP_PREDICATE)
2845 others.safe_push (kids[i]);
2846 else
2847 gcc_unreachable ();
2848 }
2849 else if (kids[i]->type == dt_node::DT_SIMPLIFY)
2850 others.safe_push (kids[i]);
2851 else if (kids[i]->type == dt_node::DT_MATCH
2852 || kids[i]->type == dt_node::DT_TRUE)
2853 {
2854 /* A DT_TRUE operand serves as a barrier - generate code now
2855 for what we have collected sofar.
2856 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause
2857 dependent matches to get out-of-order. Generate code now
2858 for what we have collected sofar. */
2859 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2860 fns, generic_fns, preds, others);
2861 /* And output the true operand itself. */
2862 kids[i]->gen (f, indent, gimple);
2863 gimple_exprs.truncate (0);
2864 generic_exprs.truncate (0);
2865 fns.truncate (0);
2866 generic_fns.truncate (0);
2867 preds.truncate (0);
2868 others.truncate (0);
2869 }
2870 else
2871 gcc_unreachable ();
2872 }
2873
2874 /* Generate code for the remains. */
2875 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs,
2876 fns, generic_fns, preds, others);
2877}
2878
2879/* Generate matching code for the children of the decision tree node. */
2880
2881void
2882dt_node::gen_kids_1 (FILE *f, int indent, bool gimple,
2883 vec<dt_operand *> gimple_exprs,
2884 vec<dt_operand *> generic_exprs,
2885 vec<dt_operand *> fns,
2886 vec<dt_operand *> generic_fns,
2887 vec<dt_operand *> preds,
2888 vec<dt_node *> others)
2889{
2890 char buf[128];
2891 char *kid_opname = buf;
2892
2893 unsigned exprs_len = gimple_exprs.length ();
2894 unsigned gexprs_len = generic_exprs.length ();
2895 unsigned fns_len = fns.length ();
2896 unsigned gfns_len = generic_fns.length ();
2897
2898 if (exprs_len || fns_len || gexprs_len || gfns_len)
2899 {
2900 if (exprs_len)
2901 gimple_exprs[0]->get_name (kid_opname);
2902 else if (fns_len)
2903 fns[0]->get_name (kid_opname);
2904 else if (gfns_len)
2905 generic_fns[0]->get_name (kid_opname);
2906 else
2907 generic_exprs[0]->get_name (kid_opname);
2908
2909 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname);
2910 fprintf_indent (f, indent, " {\n");
2911 indent += 2;
2912 }
2913
2914 if (exprs_len || fns_len)
2915 {
2916 fprintf_indent (f, indent,
2917 "case SSA_NAME:\n");
2918 fprintf_indent (f, indent,
2919 " if (gimple *def_stmt = get_def (valueize, %s))\n",
2920 kid_opname);
2921 fprintf_indent (f, indent,
2922 " {\n");
2923 indent += 6;
2924 if (exprs_len)
2925 {
2926 fprintf_indent (f, indent,
2927 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n");
2928 fprintf_indent (f, indent,
2929 " switch (gimple_assign_rhs_code (def))\n");
2930 indent += 4;
2931 fprintf_indent (f, indent, "{\n");
2932 for (unsigned i = 0; i < exprs_len; ++i)
2933 {
2934 expr *e = as_a <expr *> (gimple_exprs[i]->op);
2935 id_base *op = e->operation;
2936 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
2937 fprintf_indent (f, indent, "CASE_CONVERT:\n");
2938 else
2939 fprintf_indent (f, indent, "case %s:\n", op->id);
2940 fprintf_indent (f, indent, " {\n");
2941 gimple_exprs[i]->gen (f, indent + 4, true);
2942 fprintf_indent (f, indent, " break;\n");
2943 fprintf_indent (f, indent, " }\n");
2944 }
2945 fprintf_indent (f, indent, "default:;\n");
2946 fprintf_indent (f, indent, "}\n");
2947 indent -= 4;
2948 }
2949
2950 if (fns_len)
2951 {
2952 fprintf_indent (f, indent,
2953 "%sif (gcall *def = dyn_cast <gcall *>"
2954 " (def_stmt))\n",
2955 exprs_len ? "else " : "");
2956 fprintf_indent (f, indent,
2957 " switch (gimple_call_combined_fn (def))\n");
2958
2959 indent += 4;
2960 fprintf_indent (f, indent, "{\n");
2961 for (unsigned i = 0; i < fns_len; ++i)
2962 {
2963 expr *e = as_a <expr *>(fns[i]->op);
2964 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
2965 fprintf_indent (f, indent, " {\n");
2966 fns[i]->gen (f, indent + 4, true);
2967 fprintf_indent (f, indent, " break;\n");
2968 fprintf_indent (f, indent, " }\n");
2969 }
2970
2971 fprintf_indent (f, indent, "default:;\n");
2972 fprintf_indent (f, indent, "}\n");
2973 indent -= 4;
2974 }
2975
2976 indent -= 6;
2977 fprintf_indent (f, indent, " }\n");
2978 /* See if there is SSA_NAME among generic_exprs and if yes, emit it
2979 here rather than in the next loop. */
2980 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2981 {
2982 expr *e = as_a <expr *>(generic_exprs[i]->op);
2983 id_base *op = e->operation;
2984 if (*op == SSA_NAME && (exprs_len || fns_len))
2985 {
2986 fprintf_indent (f, indent + 4, "{\n");
2987 generic_exprs[i]->gen (f, indent + 6, gimple);
2988 fprintf_indent (f, indent + 4, "}\n");
2989 }
2990 }
2991
2992 fprintf_indent (f, indent, " break;\n");
2993 }
2994
2995 for (unsigned i = 0; i < generic_exprs.length (); ++i)
2996 {
2997 expr *e = as_a <expr *>(generic_exprs[i]->op);
2998 id_base *op = e->operation;
2999 if (*op == CONVERT_EXPR || *op == NOP_EXPR)
3000 fprintf_indent (f, indent, "CASE_CONVERT:\n");
3001 else if (*op == SSA_NAME && (exprs_len || fns_len))
3002 /* Already handled above. */
3003 continue;
3004 else
3005 fprintf_indent (f, indent, "case %s:\n", op->id);
3006 fprintf_indent (f, indent, " {\n");
3007 generic_exprs[i]->gen (f, indent + 4, gimple);
3008 fprintf_indent (f, indent, " break;\n");
3009 fprintf_indent (f, indent, " }\n");
3010 }
3011
3012 if (gfns_len)
3013 {
3014 fprintf_indent (f, indent,
3015 "case CALL_EXPR:\n");
3016 fprintf_indent (f, indent,
3017 " switch (get_call_combined_fn (%s))\n",
3018 kid_opname);
3019 fprintf_indent (f, indent,
3020 " {\n");
3021 indent += 4;
3022
3023 for (unsigned j = 0; j < generic_fns.length (); ++j)
3024 {
3025 expr *e = as_a <expr *>(generic_fns[j]->op);
3026 gcc_assert (e->operation->kind == id_base::FN);
3027
3028 fprintf_indent (f, indent, "case %s:\n", e->operation->id);
3029 fprintf_indent (f, indent, " {\n");
3030 generic_fns[j]->gen (f, indent + 4, false);
3031 fprintf_indent (f, indent, " break;\n");
3032 fprintf_indent (f, indent, " }\n");
3033 }
3034 fprintf_indent (f, indent, "default:;\n");
3035
3036 indent -= 4;
3037 fprintf_indent (f, indent, " }\n");
3038 fprintf_indent (f, indent, " break;\n");
3039 }
3040
3041 /* Close switch (TREE_CODE ()). */
3042 if (exprs_len || fns_len || gexprs_len || gfns_len)
3043 {
3044 indent -= 4;
3045 fprintf_indent (f, indent, " default:;\n");
3046 fprintf_indent (f, indent, " }\n");
3047 }
3048
3049 for (unsigned i = 0; i < preds.length (); ++i)
3050 {
3051 expr *e = as_a <expr *> (preds[i]->op);
3052 predicate_id *p = as_a <predicate_id *> (e->operation);
3053 preds[i]->get_name (kid_opname);
3054 fprintf_indent (f, indent, "{\n");
3055 indent += 2;
3056 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs);
3057 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n",
3058 gimple ? "gimple" : "tree",
3059 p->id, kid_opname, kid_opname,
3060 gimple ? ", valueize" : "");
3061 fprintf_indent (f, indent, " {\n");
3062 for (int j = 0; j < p->nargs; ++j)
3063 {
3064 char child_opname[20];
3065 preds[i]->gen_opname (child_opname, j);
3066 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n",
3067 child_opname, kid_opname, j);
3068 }
3069 preds[i]->gen_kids (f, indent + 4, gimple);
3070 fprintf (f, "}\n");
3071 indent -= 2;
3072 fprintf_indent (f, indent, "}\n");
3073 }
3074
3075 for (unsigned i = 0; i < others.length (); ++i)
3076 others[i]->gen (f, indent, gimple);
3077}
3078
3079/* Generate matching code for the decision tree operand. */
3080
3081void
3082dt_operand::gen (FILE *f, int indent, bool gimple)
3083{
3084 char opname[20];
3085 get_name (opname);
3086
3087 unsigned n_braces = 0;
3088
3089 if (type == DT_OPERAND)
3090 switch (op->type)
3091 {
3092 case operand::OP_PREDICATE:
3093 n_braces = gen_predicate (f, indent, opname, gimple);
3094 break;
3095
3096 case operand::OP_EXPR:
3097 if (gimple)
3098 n_braces = gen_gimple_expr (f, indent);
3099 else
3100 n_braces = gen_generic_expr (f, indent, opname);
3101 break;
3102
3103 default:
3104 gcc_unreachable ();
3105 }
3106 else if (type == DT_TRUE)
3107 ;
3108 else if (type == DT_MATCH)
3109 n_braces = gen_match_op (f, indent, opname, gimple);
3110 else
3111 gcc_unreachable ();
3112
3113 indent += 4 * n_braces;
3114 gen_kids (f, indent, gimple);
3115
3116 for (unsigned i = 0; i < n_braces; ++i)
3117 {
3118 indent -= 4;
3119 if (indent < 0)
3120 indent = 0;
3121 fprintf_indent (f, indent, " }\n");
3122 }
3123}
3124
3125
3126/* Generate code for the '(if ...)', '(with ..)' and actual transform
3127 step of a '(simplify ...)' or '(match ...)'. This handles everything
3128 that is not part of the decision tree (simplify->match).
3129 Main recursive worker. */
3130
3131void
3132dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result)
3133{
3134 if (result)
3135 {
3136 if (with_expr *w = dyn_cast <with_expr *> (result))
3137 {
3138 fprintf_indent (f, indent, "{\n");
3139 indent += 4;
3140 output_line_directive (f, w->location);
3141 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3142 gen_1 (f, indent, gimple, w->subexpr);
3143 indent -= 4;
3144 fprintf_indent (f, indent, "}\n");
3145 return;
3146 }
3147 else if (if_expr *ife = dyn_cast <if_expr *> (result))
3148 {
3149 output_line_directive (f, ife->location);
3150 fprintf_indent (f, indent, "if (");
3151 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL);
3152 fprintf (f, ")\n");
3153 fprintf_indent (f, indent + 2, "{\n");
3154 indent += 4;
3155 gen_1 (f, indent, gimple, ife->trueexpr);
3156 indent -= 4;
3157 fprintf_indent (f, indent + 2, "}\n");
3158 if (ife->falseexpr)
3159 {
3160 fprintf_indent (f, indent, "else\n");
3161 fprintf_indent (f, indent + 2, "{\n");
3162 indent += 4;
3163 gen_1 (f, indent, gimple, ife->falseexpr);
3164 indent -= 4;
3165 fprintf_indent (f, indent + 2, "}\n");
3166 }
3167 return;
3168 }
3169 }
3170
3171 /* Analyze captures and perform early-outs on the incoming arguments
3172 that cover cases we cannot handle. */
3173 capture_info cinfo (s, result, gimple);
3174 if (s->kind == simplify::SIMPLIFY)
3175 {
3176 if (!gimple)
3177 {
3178 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3179 if (cinfo.force_no_side_effects & (1 << i))
3180 {
3181 fprintf_indent (f, indent,
3182 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n",
3183 i);
3184 if (verbose >= 1)
3185 warning_at (as_a <expr *> (s->match)->ops[i]->location,
3186 "forcing toplevel operand to have no "
3187 "side-effects");
3188 }
3189 for (int i = 0; i <= s->capture_max; ++i)
3190 if (cinfo.info[i].cse_p)
3191 ;
3192 else if (cinfo.info[i].force_no_side_effects_p
3193 && (cinfo.info[i].toplevel_msk
3194 & cinfo.force_no_side_effects) == 0)
3195 {
3196 fprintf_indent (f, indent,
3197 "if (TREE_SIDE_EFFECTS (captures[%d])) "
3198 "return NULL_TREE;\n", i);
3199 if (verbose >= 1)
3200 warning_at (cinfo.info[i].c->location,
3201 "forcing captured operand to have no "
3202 "side-effects");
3203 }
3204 else if ((cinfo.info[i].toplevel_msk
3205 & cinfo.force_no_side_effects) != 0)
3206 /* Mark capture as having no side-effects if we had to verify
3207 that via forced toplevel operand checks. */
3208 cinfo.info[i].force_no_side_effects_p = true;
3209 }
3210 if (gimple)
3211 {
3212 /* Force single-use restriction by only allowing simple
3213 results via setting seq to NULL. */
3214 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n");
3215 bool first_p = true;
3216 for (int i = 0; i <= s->capture_max; ++i)
3217 if (cinfo.info[i].force_single_use)
3218 {
3219 if (first_p)
3220 {
3221 fprintf_indent (f, indent, "if (lseq\n");
3222 fprintf_indent (f, indent, " && (");
3223 first_p = false;
3224 }
3225 else
3226 {
3227 fprintf (f, "\n");
3228 fprintf_indent (f, indent, " || ");
3229 }
3230 fprintf (f, "!single_use (captures[%d])", i);
3231 }
3232 if (!first_p)
3233 {
3234 fprintf (f, "))\n");
3235 fprintf_indent (f, indent, " lseq = NULL;\n");
3236 }
3237 }
3238 }
3239
3240 fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_FOLDING)) "
3241 "fprintf (dump_file, \"Applying pattern ");
3242 output_line_directive (f,
3243 result ? result->location : s->match->location, true);
3244 fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n");
3245
3246 if (!result)
3247 {
3248 /* If there is no result then this is a predicate implementation. */
3249 fprintf_indent (f, indent, "return true;\n");
3250 }
3251 else if (gimple)
3252 {
3253 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears
3254 in outermost position). */
3255 if (result->type == operand::OP_EXPR
3256 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR)
3257 result = as_a <expr *> (result)->ops[0];
3258 if (result->type == operand::OP_EXPR)
3259 {
3260 expr *e = as_a <expr *> (result);
3261 id_base *opr = e->operation;
3262 bool is_predicate = false;
3263 /* When we delay operator substituting during lowering of fors we
3264 make sure that for code-gen purposes the effects of each substitute
3265 are the same. Thus just look at that. */
3266 if (user_id *uid = dyn_cast <user_id *> (opr))
3267 opr = uid->substitutes[0];
3268 else if (is_a <predicate_id *> (opr))
3269 is_predicate = true;
3270 if (!is_predicate)
3271 fprintf_indent (f, indent, "*res_code = %s;\n",
3272 *e->operation == CONVERT_EXPR
3273 ? "NOP_EXPR" : e->operation->id);
3274 for (unsigned j = 0; j < e->ops.length (); ++j)
3275 {
3276 char dest[32];
3277 snprintf (dest, 32, "res_ops[%d]", j);
3278 const char *optype
3279 = get_operand_type (opr, j,
3280 "type", e->expr_type,
3281 j == 0 ? NULL : "TREE_TYPE (res_ops[0])");
3282 /* We need to expand GENERIC conditions we captured from
3283 COND_EXPRs and we need to unshare them when substituting
3284 into COND_EXPRs. */
3285 int cond_handling = 0;
3286 if (!is_predicate)
3287 cond_handling = ((*opr == COND_EXPR
3288 || *opr == VEC_COND_EXPR) && j == 0) ? 1 : 2;
3289 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype,
3290 &cinfo, indexes, cond_handling);
3291 }
3292
3293 /* Re-fold the toplevel result. It's basically an embedded
3294 gimple_build w/o actually building the stmt. */
3295 if (!is_predicate)
3296 fprintf_indent (f, indent,
3297 "gimple_resimplify%d (lseq, res_code, type, "
3298 "res_ops, valueize);\n", e->ops.length ());
3299 }
3300 else if (result->type == operand::OP_CAPTURE
3301 || result->type == operand::OP_C_EXPR)
3302 {
3303 result->gen_transform (f, indent, "res_ops[0]", true, 1, "type",
3304 &cinfo, indexes);
3305 fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n");
3306 if (is_a <capture *> (result)
3307 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p)
3308 {
3309 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal
3310 with substituting a capture of that. */
3311 fprintf_indent (f, indent,
3312 "if (COMPARISON_CLASS_P (res_ops[0]))\n");
3313 fprintf_indent (f, indent,
3314 " {\n");
3315 fprintf_indent (f, indent,
3316 " tree tem = res_ops[0];\n");
3317 fprintf_indent (f, indent,
3318 " res_ops[0] = TREE_OPERAND (tem, 0);\n");
3319 fprintf_indent (f, indent,
3320 " res_ops[1] = TREE_OPERAND (tem, 1);\n");
3321 fprintf_indent (f, indent,
3322 " }\n");
3323 }
3324 }
3325 else
3326 gcc_unreachable ();
3327 fprintf_indent (f, indent, "return true;\n");
3328 }
3329 else /* GENERIC */
3330 {
3331 bool is_predicate = false;
3332 if (result->type == operand::OP_EXPR)
3333 {
3334 expr *e = as_a <expr *> (result);
3335 id_base *opr = e->operation;
3336 /* When we delay operator substituting during lowering of fors we
3337 make sure that for code-gen purposes the effects of each substitute
3338 are the same. Thus just look at that. */
3339 if (user_id *uid = dyn_cast <user_id *> (opr))
3340 opr = uid->substitutes[0];
3341 else if (is_a <predicate_id *> (opr))
3342 is_predicate = true;
3343 /* Search for captures used multiple times in the result expression
3344 and wrap them in a SAVE_EXPR. Allow as many uses as in the
3345 original expression. */
3346 if (!is_predicate)
3347 for (int i = 0; i < s->capture_max + 1; ++i)
3348 {
3349 if (cinfo.info[i].same_as != (unsigned)i
3350 || cinfo.info[i].cse_p)
3351 continue;
3352 if (cinfo.info[i].result_use_count
3353 > cinfo.info[i].match_use_count)
3354 fprintf_indent (f, indent,
3355 "if (! tree_invariant_p (captures[%d])) "
3356 "return NULL_TREE;\n", i);
3357 }
3358 for (unsigned j = 0; j < e->ops.length (); ++j)
3359 {
3360 char dest[32];
3361 if (is_predicate)
3362 snprintf (dest, 32, "res_ops[%d]", j);
3363 else
3364 {
3365 fprintf_indent (f, indent, "tree res_op%d;\n", j);
3366 snprintf (dest, 32, "res_op%d", j);
3367 }
3368 const char *optype
3369 = get_operand_type (opr, j,
3370 "type", e->expr_type,
3371 j == 0
3372 ? NULL : "TREE_TYPE (res_op0)");
3373 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype,
3374 &cinfo, indexes);
3375 }
3376 if (is_predicate)
3377 fprintf_indent (f, indent, "return true;\n");
3378 else
3379 {
3380 fprintf_indent (f, indent, "tree res;\n");
3381 /* Re-fold the toplevel result. Use non_lvalue to
3382 build NON_LVALUE_EXPRs so they get properly
3383 ignored when in GIMPLE form. */
3384 if (*opr == NON_LVALUE_EXPR)
3385 fprintf_indent (f, indent,
3386 "res = non_lvalue_loc (loc, res_op0);\n");
3387 else
3388 {
3389 if (is_a <operator_id *> (opr))
3390 fprintf_indent (f, indent,
3391 "res = fold_build%d_loc (loc, %s, type",
3392 e->ops.length (),
3393 *e->operation == CONVERT_EXPR
3394 ? "NOP_EXPR" : e->operation->id);
3395 else
3396 fprintf_indent (f, indent,
3397 "res = maybe_build_call_expr_loc (loc, "
3398 "%s, type, %d", e->operation->id,
3399 e->ops.length());
3400 for (unsigned j = 0; j < e->ops.length (); ++j)
3401 fprintf (f, ", res_op%d", j);
3402 fprintf (f, ");\n");
3403 if (!is_a <operator_id *> (opr))
3404 {
3405 fprintf_indent (f, indent, "if (!res)\n");
3406 fprintf_indent (f, indent, " return NULL_TREE;\n");
3407 }
3408 }
3409 }
3410 }
3411 else if (result->type == operand::OP_CAPTURE
3412 || result->type == operand::OP_C_EXPR)
3413
3414 {
3415 fprintf_indent (f, indent, "tree res;\n");
3416 result->gen_transform (f, indent, "res", false, 1, "type",
3417 &cinfo, indexes);
3418 }
3419 else
3420 gcc_unreachable ();
3421 if (!is_predicate)
3422 {
3423 /* Search for captures not used in the result expression and dependent
3424 on TREE_SIDE_EFFECTS emit omit_one_operand. */
3425 for (int i = 0; i < s->capture_max + 1; ++i)
3426 {
3427 if (cinfo.info[i].same_as != (unsigned)i)
3428 continue;
3429 if (!cinfo.info[i].force_no_side_effects_p
3430 && !cinfo.info[i].expr_p
3431 && cinfo.info[i].result_use_count == 0)
3432 {
3433 fprintf_indent (f, indent,
3434 "if (TREE_SIDE_EFFECTS (captures[%d]))\n",
3435 i);
3436 fprintf_indent (f, indent + 2,
3437 "res = build2_loc (loc, COMPOUND_EXPR, type, "
3438 "fold_ignored_result (captures[%d]), res);\n",
3439 i);
3440 }
3441 }
3442 fprintf_indent (f, indent, "return res;\n");
3443 }
3444 }
3445}
3446
3447/* Generate code for the '(if ...)', '(with ..)' and actual transform
3448 step of a '(simplify ...)' or '(match ...)'. This handles everything
3449 that is not part of the decision tree (simplify->match). */
3450
3451void
3452dt_simplify::gen (FILE *f, int indent, bool gimple)
3453{
3454 fprintf_indent (f, indent, "{\n");
3455 indent += 2;
3456 output_line_directive (f,
3457 s->result ? s->result->location : s->match->location);
3458 if (s->capture_max >= 0)
3459 {
3460 char opname[20];
3461 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s",
3462 s->capture_max + 1, indexes[0]->get_name (opname));
3463
3464 for (int i = 1; i <= s->capture_max; ++i)
3465 {
3466 if (!indexes[i])
3467 break;
3468 fprintf (f, ", %s", indexes[i]->get_name (opname));
3469 }
3470 fprintf (f, " };\n");
3471 }
3472
3473 /* If we have a split-out function for the actual transform, call it. */
3474 if (info && info->fname)
3475 {
3476 if (gimple)
3477 {
3478 fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, "
3479 "valueize, type, captures", info->fname);
3480 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3481 if (s->for_subst_vec[i].first->used)
3482 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3483 fprintf (f, "))\n");
3484 fprintf_indent (f, indent, " return true;\n");
3485 }
3486 else
3487 {
3488 fprintf_indent (f, indent, "tree res = %s (loc, type",
3489 info->fname);
3490 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i)
3491 fprintf (f, ", op%d", i);
3492 fprintf (f, ", captures");
3493 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3494 {
3495 if (s->for_subst_vec[i].first->used)
3496 fprintf (f, ", %s", s->for_subst_vec[i].second->id);
3497 }
3498 fprintf (f, ");\n");
3499 fprintf_indent (f, indent, "if (res) return res;\n");
3500 }
3501 }
3502 else
3503 {
3504 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i)
3505 {
3506 if (! s->for_subst_vec[i].first->used)
3507 continue;
3508 if (is_a <operator_id *> (s->for_subst_vec[i].second))
3509 fprintf_indent (f, indent, "const enum tree_code %s = %s;\n",
3510 s->for_subst_vec[i].first->id,
3511 s->for_subst_vec[i].second->id);
3512 else if (is_a <fn_id *> (s->for_subst_vec[i].second))
3513 fprintf_indent (f, indent, "const combined_fn %s = %s;\n",
3514 s->for_subst_vec[i].first->id,
3515 s->for_subst_vec[i].second->id);
3516 else
3517 gcc_unreachable ();
3518 }
3519 gen_1 (f, indent, gimple, s->result);
3520 }
3521
3522 indent -= 2;
3523 fprintf_indent (f, indent, "}\n");
3524}
3525
3526
3527/* Hash function for finding equivalent transforms. */
3528
3529hashval_t
3530sinfo_hashmap_traits::hash (const key_type &v)
3531{
3532 /* Only bother to compare those originating from the same source pattern. */
3533 return v->s->result->location;
3534}
3535
3536/* Compare function for finding equivalent transforms. */
3537
3538static bool
3539compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2)
3540{
3541 if (o1->type != o2->type)
3542 return false;
3543
3544 switch (o1->type)
3545 {
3546 case operand::OP_IF:
3547 {
3548 if_expr *if1 = as_a <if_expr *> (o1);
3549 if_expr *if2 = as_a <if_expr *> (o2);
3550 /* ??? Properly compare c-exprs. */
3551 if (if1->cond != if2->cond)
3552 return false;
3553 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2))
3554 return false;
3555 if (if1->falseexpr != if2->falseexpr
3556 || (if1->falseexpr
3557 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2)))
3558 return false;
3559 return true;
3560 }
3561 case operand::OP_WITH:
3562 {
3563 with_expr *with1 = as_a <with_expr *> (o1);
3564 with_expr *with2 = as_a <with_expr *> (o2);
3565 if (with1->with != with2->with)
3566 return false;
3567 return compare_op (with1->subexpr, s1, with2->subexpr, s2);
3568 }
3569 default:;
3570 }
3571
3572 /* We've hit a result. Time to compare capture-infos - this is required
3573 in addition to the conservative pointer-equivalency of the result IL. */
3574 capture_info cinfo1 (s1, o1, true);
3575 capture_info cinfo2 (s2, o2, true);
3576
3577 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects
3578 || cinfo1.info.length () != cinfo2.info.length ())
3579 return false;
3580
3581 for (unsigned i = 0; i < cinfo1.info.length (); ++i)
3582 {
3583 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p
3584 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p
3585 || (cinfo1.info[i].force_no_side_effects_p
3586 != cinfo2.info[i].force_no_side_effects_p)
3587 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use
3588 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p
3589 /* toplevel_msk is an optimization */
3590 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count
3591 || cinfo1.info[i].same_as != cinfo2.info[i].same_as
3592 /* the pointer back to the capture is for diagnostics only */)
3593 return false;
3594 }
3595
3596 /* ??? Deep-compare the actual result. */
3597 return o1 == o2;
3598}
3599
3600bool
3601sinfo_hashmap_traits::equal_keys (const key_type &v,
3602 const key_type &candidate)
3603{
3604 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s);
3605}
3606
3607
3608/* Main entry to generate code for matching GIMPLE IL off the decision
3609 tree. */
3610
3611void
3612decision_tree::gen (FILE *f, bool gimple)
3613{
3614 sinfo_map_t si;
3615
3616 root->analyze (si);
3617
3618 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and "
3619 "a total number of %u nodes\n",
3620 gimple ? "GIMPLE" : "GENERIC",
3621 root->num_leafs, root->max_level, root->total_size);
3622
3623 /* First split out the transform part of equal leafs. */
3624 unsigned rcnt = 0;
3625 unsigned fcnt = 1;
3626 for (sinfo_map_t::iterator iter = si.begin ();
3627 iter != si.end (); ++iter)
3628 {
3629 sinfo *s = (*iter).second;
3630 /* Do not split out single uses. */
3631 if (s->cnt <= 1)
3632 continue;
3633
3634 rcnt += s->cnt - 1;
3635 if (verbose >= 1)
3636 {
3637 fprintf (stderr, "found %u uses of", s->cnt);
3638 output_line_directive (stderr, s->s->s->result->location);
3639 }
3640
3641 /* Generate a split out function with the leaf transform code. */
3642 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic",
3643 fcnt++);
3644 if (gimple)
3645 fprintf (f, "\nstatic bool\n"
3646 "%s (code_helper *res_code, tree *res_ops,\n"
3647 " gimple_seq *seq, tree (*valueize)(tree) "
3648 "ATTRIBUTE_UNUSED,\n"
3649 " const tree ARG_UNUSED (type), tree *ARG_UNUSED "
3650 "(captures)\n",
3651 s->fname);
3652 else
3653 {
3654 fprintf (f, "\nstatic tree\n"
3655 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n",
3656 (*iter).second->fname);
3657 for (unsigned i = 0;
3658 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i)
3659 fprintf (f, " tree ARG_UNUSED (op%d),", i);
3660 fprintf (f, " tree *captures\n");
3661 }
3662 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i)
3663 {
3664 if (! s->s->s->for_subst_vec[i].first->used)
3665 continue;
3666 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second))
3667 fprintf (f, ", const enum tree_code ARG_UNUSED (%s)",
3668 s->s->s->for_subst_vec[i].first->id);
3669 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second))
3670 fprintf (f, ", const combined_fn ARG_UNUSED (%s)",
3671 s->s->s->for_subst_vec[i].first->id);
3672 }
3673
3674 fprintf (f, ")\n{\n");
3675 s->s->gen_1 (f, 2, gimple, s->s->s->result);
3676 if (gimple)
3677 fprintf (f, " return false;\n");
3678 else
3679 fprintf (f, " return NULL_TREE;\n");
3680 fprintf (f, "}\n");
3681 }
3682 fprintf (stderr, "removed %u duplicate tails\n", rcnt);
3683
3684 for (unsigned n = 1; n <= 3; ++n)
3685 {
3686 /* First generate split-out functions. */
3687 for (unsigned i = 0; i < root->kids.length (); i++)
3688 {
3689 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3690 expr *e = static_cast<expr *>(dop->op);
3691 if (e->ops.length () != n
3692 /* Builtin simplifications are somewhat premature on
3693 GENERIC. The following drops patterns with outermost
3694 calls. It's easy to emit overloads for function code
3695 though if necessary. */
3696 || (!gimple
3697 && e->operation->kind != id_base::CODE))
3698 continue;
3699
3700 if (gimple)
3701 fprintf (f, "\nstatic bool\n"
3702 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n"
3703 " gimple_seq *seq, tree (*valueize)(tree) "
3704 "ATTRIBUTE_UNUSED,\n"
3705 " code_helper ARG_UNUSED (code), tree "
3706 "ARG_UNUSED (type)\n",
3707 e->operation->id);
3708 else
3709 fprintf (f, "\nstatic tree\n"
3710 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum "
3711 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)",
3712 e->operation->id);
3713 for (unsigned i = 0; i < n; ++i)
3714 fprintf (f, ", tree op%d", i);
3715 fprintf (f, ")\n");
3716 fprintf (f, "{\n");
3717 dop->gen_kids (f, 2, gimple);
3718 if (gimple)
3719 fprintf (f, " return false;\n");
3720 else
3721 fprintf (f, " return NULL_TREE;\n");
3722 fprintf (f, "}\n");
3723 }
3724
3725 /* Then generate the main entry with the outermost switch and
3726 tail-calls to the split-out functions. */
3727 if (gimple)
3728 fprintf (f, "\nstatic bool\n"
3729 "gimple_simplify (code_helper *res_code, tree *res_ops,\n"
3730 " gimple_seq *seq, tree (*valueize)(tree),\n"
3731 " code_helper code, const tree type");
3732 else
3733 fprintf (f, "\ntree\n"
3734 "generic_simplify (location_t loc, enum tree_code code, "
3735 "const tree type ATTRIBUTE_UNUSED");
3736 for (unsigned i = 0; i < n; ++i)
3737 fprintf (f, ", tree op%d", i);
3738 fprintf (f, ")\n");
3739 fprintf (f, "{\n");
3740
3741 if (gimple)
3742 fprintf (f, " switch (code.get_rep())\n"
3743 " {\n");
3744 else
3745 fprintf (f, " switch (code)\n"
3746 " {\n");
3747 for (unsigned i = 0; i < root->kids.length (); i++)
3748 {
3749 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]);
3750 expr *e = static_cast<expr *>(dop->op);