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