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