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 || operand_equal_p (%s, %s, 0))\n", 2684 opname, match_opname, opname, match_opname); 2685 else 2686 fprintf_indent (f, indent, "if (%s == %s || (operand_equal_p (%s, %s, 0) " 2687 "&& types_match (%s, %s)))\n", 2688 opname, match_opname, opname, match_opname, 2689 opname, match_opname); 2690 fprintf_indent (f, indent + 2, "{\n"); 2691 return 1; 2692 } 2693 2694 /* Generate GIMPLE matching code for the decision tree operand. */ 2695 2696 unsigned 2697 dt_operand::gen_gimple_expr (FILE *f, int indent) 2698 { 2699 expr *e = static_cast<expr *> (op); 2700 id_base *id = e->operation; 2701 unsigned n_ops = e->ops.length (); 2702 unsigned n_braces = 0; 2703 2704 for (unsigned i = 0; i < n_ops; ++i) 2705 { 2706 char child_opname[20]; 2707 gen_opname (child_opname, i); 2708 2709 if (id->kind == id_base::CODE) 2710 { 2711 if (e->is_generic 2712 || *id == REALPART_EXPR || *id == IMAGPART_EXPR 2713 || *id == BIT_FIELD_REF || *id == VIEW_CONVERT_EXPR) 2714 { 2715 /* ??? If this is a memory operation we can't (and should not) 2716 match this. The only sensible operand types are 2717 SSA names and invariants. */ 2718 if (e->is_generic) 2719 { 2720 char opname[20]; 2721 get_name (opname); 2722 fprintf_indent (f, indent, 2723 "tree %s = TREE_OPERAND (%s, %i);\n", 2724 child_opname, opname, i); 2725 } 2726 else 2727 fprintf_indent (f, indent, 2728 "tree %s = TREE_OPERAND " 2729 "(gimple_assign_rhs1 (def), %i);\n", 2730 child_opname, i); 2731 fprintf_indent (f, indent, 2732 "if ((TREE_CODE (%s) == SSA_NAME\n", 2733 child_opname); 2734 fprintf_indent (f, indent, 2735 " || is_gimple_min_invariant (%s)))\n", 2736 child_opname); 2737 fprintf_indent (f, indent, 2738 " {\n"); 2739 indent += 4; 2740 n_braces++; 2741 fprintf_indent (f, indent, 2742 "%s = do_valueize (valueize, %s);\n", 2743 child_opname, child_opname); 2744 continue; 2745 } 2746 else 2747 fprintf_indent (f, indent, 2748 "tree %s = gimple_assign_rhs%u (def);\n", 2749 child_opname, i + 1); 2750 } 2751 else 2752 fprintf_indent (f, indent, 2753 "tree %s = gimple_call_arg (def, %u);\n", 2754 child_opname, i); 2755 fprintf_indent (f, indent, 2756 "%s = do_valueize (valueize, %s);\n", 2757 child_opname, child_opname); 2758 } 2759 /* While the toplevel operands are canonicalized by the caller 2760 after valueizing operands of sub-expressions we have to 2761 re-canonicalize operand order. */ 2762 if (operator_id *code = dyn_cast <operator_id *> (id)) 2763 { 2764 /* ??? We can't canonicalize tcc_comparison operands here 2765 because that requires changing the comparison code which 2766 we already matched... */ 2767 if (commutative_tree_code (code->code) 2768 || commutative_ternary_tree_code (code->code)) 2769 { 2770 char child_opname0[20], child_opname1[20]; 2771 gen_opname (child_opname0, 0); 2772 gen_opname (child_opname1, 1); 2773 fprintf_indent (f, indent, 2774 "if (tree_swap_operands_p (%s, %s))\n", 2775 child_opname0, child_opname1); 2776 fprintf_indent (f, indent, 2777 " std::swap (%s, %s);\n", 2778 child_opname0, child_opname1); 2779 } 2780 } 2781 2782 return n_braces; 2783 } 2784 2785 /* Generate GENERIC matching code for the decision tree operand. */ 2786 2787 unsigned 2788 dt_operand::gen_generic_expr (FILE *f, int indent, const char *opname) 2789 { 2790 expr *e = static_cast<expr *> (op); 2791 unsigned n_ops = e->ops.length (); 2792 2793 for (unsigned i = 0; i < n_ops; ++i) 2794 { 2795 char child_opname[20]; 2796 gen_opname (child_opname, i); 2797 2798 if (e->operation->kind == id_base::CODE) 2799 fprintf_indent (f, indent, "tree %s = TREE_OPERAND (%s, %u);\n", 2800 child_opname, opname, i); 2801 else 2802 fprintf_indent (f, indent, "tree %s = CALL_EXPR_ARG (%s, %u);\n", 2803 child_opname, opname, i); 2804 } 2805 2806 return 0; 2807 } 2808 2809 /* Generate matching code for the children of the decision tree node. */ 2810 2811 void 2812 dt_node::gen_kids (FILE *f, int indent, bool gimple) 2813 { 2814 auto_vec<dt_operand *> gimple_exprs; 2815 auto_vec<dt_operand *> generic_exprs; 2816 auto_vec<dt_operand *> fns; 2817 auto_vec<dt_operand *> generic_fns; 2818 auto_vec<dt_operand *> preds; 2819 auto_vec<dt_node *> others; 2820 2821 for (unsigned i = 0; i < kids.length (); ++i) 2822 { 2823 if (kids[i]->type == dt_node::DT_OPERAND) 2824 { 2825 dt_operand *op = as_a<dt_operand *> (kids[i]); 2826 if (expr *e = dyn_cast <expr *> (op->op)) 2827 { 2828 if (e->ops.length () == 0 2829 && (!gimple || !(*e->operation == CONSTRUCTOR))) 2830 generic_exprs.safe_push (op); 2831 else if (e->operation->kind == id_base::FN) 2832 { 2833 if (gimple) 2834 fns.safe_push (op); 2835 else 2836 generic_fns.safe_push (op); 2837 } 2838 else if (e->operation->kind == id_base::PREDICATE) 2839 preds.safe_push (op); 2840 else 2841 { 2842 if (gimple && !e->is_generic) 2843 gimple_exprs.safe_push (op); 2844 else 2845 generic_exprs.safe_push (op); 2846 } 2847 } 2848 else if (op->op->type == operand::OP_PREDICATE) 2849 others.safe_push (kids[i]); 2850 else 2851 gcc_unreachable (); 2852 } 2853 else if (kids[i]->type == dt_node::DT_SIMPLIFY) 2854 others.safe_push (kids[i]); 2855 else if (kids[i]->type == dt_node::DT_MATCH 2856 || kids[i]->type == dt_node::DT_TRUE) 2857 { 2858 /* A DT_TRUE operand serves as a barrier - generate code now 2859 for what we have collected sofar. 2860 Like DT_TRUE, DT_MATCH serves as a barrier as it can cause 2861 dependent matches to get out-of-order. Generate code now 2862 for what we have collected sofar. */ 2863 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs, 2864 fns, generic_fns, preds, others); 2865 /* And output the true operand itself. */ 2866 kids[i]->gen (f, indent, gimple); 2867 gimple_exprs.truncate (0); 2868 generic_exprs.truncate (0); 2869 fns.truncate (0); 2870 generic_fns.truncate (0); 2871 preds.truncate (0); 2872 others.truncate (0); 2873 } 2874 else 2875 gcc_unreachable (); 2876 } 2877 2878 /* Generate code for the remains. */ 2879 gen_kids_1 (f, indent, gimple, gimple_exprs, generic_exprs, 2880 fns, generic_fns, preds, others); 2881 } 2882 2883 /* Generate matching code for the children of the decision tree node. */ 2884 2885 void 2886 dt_node::gen_kids_1 (FILE *f, int indent, bool gimple, 2887 vec<dt_operand *> gimple_exprs, 2888 vec<dt_operand *> generic_exprs, 2889 vec<dt_operand *> fns, 2890 vec<dt_operand *> generic_fns, 2891 vec<dt_operand *> preds, 2892 vec<dt_node *> others) 2893 { 2894 char buf[128]; 2895 char *kid_opname = buf; 2896 2897 unsigned exprs_len = gimple_exprs.length (); 2898 unsigned gexprs_len = generic_exprs.length (); 2899 unsigned fns_len = fns.length (); 2900 unsigned gfns_len = generic_fns.length (); 2901 2902 if (exprs_len || fns_len || gexprs_len || gfns_len) 2903 { 2904 if (exprs_len) 2905 gimple_exprs[0]->get_name (kid_opname); 2906 else if (fns_len) 2907 fns[0]->get_name (kid_opname); 2908 else if (gfns_len) 2909 generic_fns[0]->get_name (kid_opname); 2910 else 2911 generic_exprs[0]->get_name (kid_opname); 2912 2913 fprintf_indent (f, indent, "switch (TREE_CODE (%s))\n", kid_opname); 2914 fprintf_indent (f, indent, " {\n"); 2915 indent += 2; 2916 } 2917 2918 if (exprs_len || fns_len) 2919 { 2920 fprintf_indent (f, indent, 2921 "case SSA_NAME:\n"); 2922 fprintf_indent (f, indent, 2923 " if (gimple *def_stmt = get_def (valueize, %s))\n", 2924 kid_opname); 2925 fprintf_indent (f, indent, 2926 " {\n"); 2927 indent += 6; 2928 if (exprs_len) 2929 { 2930 fprintf_indent (f, indent, 2931 "if (gassign *def = dyn_cast <gassign *> (def_stmt))\n"); 2932 fprintf_indent (f, indent, 2933 " switch (gimple_assign_rhs_code (def))\n"); 2934 indent += 4; 2935 fprintf_indent (f, indent, "{\n"); 2936 for (unsigned i = 0; i < exprs_len; ++i) 2937 { 2938 expr *e = as_a <expr *> (gimple_exprs[i]->op); 2939 id_base *op = e->operation; 2940 if (*op == CONVERT_EXPR || *op == NOP_EXPR) 2941 fprintf_indent (f, indent, "CASE_CONVERT:\n"); 2942 else 2943 fprintf_indent (f, indent, "case %s:\n", op->id); 2944 fprintf_indent (f, indent, " {\n"); 2945 gimple_exprs[i]->gen (f, indent + 4, true); 2946 fprintf_indent (f, indent, " break;\n"); 2947 fprintf_indent (f, indent, " }\n"); 2948 } 2949 fprintf_indent (f, indent, "default:;\n"); 2950 fprintf_indent (f, indent, "}\n"); 2951 indent -= 4; 2952 } 2953 2954 if (fns_len) 2955 { 2956 fprintf_indent (f, indent, 2957 "%sif (gcall *def = dyn_cast <gcall *>" 2958 " (def_stmt))\n", 2959 exprs_len ? "else " : ""); 2960 fprintf_indent (f, indent, 2961 " switch (gimple_call_combined_fn (def))\n"); 2962 2963 indent += 4; 2964 fprintf_indent (f, indent, "{\n"); 2965 for (unsigned i = 0; i < fns_len; ++i) 2966 { 2967 expr *e = as_a <expr *>(fns[i]->op); 2968 fprintf_indent (f, indent, "case %s:\n", e->operation->id); 2969 fprintf_indent (f, indent, " {\n"); 2970 fns[i]->gen (f, indent + 4, true); 2971 fprintf_indent (f, indent, " break;\n"); 2972 fprintf_indent (f, indent, " }\n"); 2973 } 2974 2975 fprintf_indent (f, indent, "default:;\n"); 2976 fprintf_indent (f, indent, "}\n"); 2977 indent -= 4; 2978 } 2979 2980 indent -= 6; 2981 fprintf_indent (f, indent, " }\n"); 2982 /* See if there is SSA_NAME among generic_exprs and if yes, emit it 2983 here rather than in the next loop. */ 2984 for (unsigned i = 0; i < generic_exprs.length (); ++i) 2985 { 2986 expr *e = as_a <expr *>(generic_exprs[i]->op); 2987 id_base *op = e->operation; 2988 if (*op == SSA_NAME && (exprs_len || fns_len)) 2989 { 2990 fprintf_indent (f, indent + 4, "{\n"); 2991 generic_exprs[i]->gen (f, indent + 6, gimple); 2992 fprintf_indent (f, indent + 4, "}\n"); 2993 } 2994 } 2995 2996 fprintf_indent (f, indent, " break;\n"); 2997 } 2998 2999 for (unsigned i = 0; i < generic_exprs.length (); ++i) 3000 { 3001 expr *e = as_a <expr *>(generic_exprs[i]->op); 3002 id_base *op = e->operation; 3003 if (*op == CONVERT_EXPR || *op == NOP_EXPR) 3004 fprintf_indent (f, indent, "CASE_CONVERT:\n"); 3005 else if (*op == SSA_NAME && (exprs_len || fns_len)) 3006 /* Already handled above. */ 3007 continue; 3008 else 3009 fprintf_indent (f, indent, "case %s:\n", op->id); 3010 fprintf_indent (f, indent, " {\n"); 3011 generic_exprs[i]->gen (f, indent + 4, gimple); 3012 fprintf_indent (f, indent, " break;\n"); 3013 fprintf_indent (f, indent, " }\n"); 3014 } 3015 3016 if (gfns_len) 3017 { 3018 fprintf_indent (f, indent, 3019 "case CALL_EXPR:\n"); 3020 fprintf_indent (f, indent, 3021 " switch (get_call_combined_fn (%s))\n", 3022 kid_opname); 3023 fprintf_indent (f, indent, 3024 " {\n"); 3025 indent += 4; 3026 3027 for (unsigned j = 0; j < generic_fns.length (); ++j) 3028 { 3029 expr *e = as_a <expr *>(generic_fns[j]->op); 3030 gcc_assert (e->operation->kind == id_base::FN); 3031 3032 fprintf_indent (f, indent, "case %s:\n", e->operation->id); 3033 fprintf_indent (f, indent, " {\n"); 3034 generic_fns[j]->gen (f, indent + 4, false); 3035 fprintf_indent (f, indent, " break;\n"); 3036 fprintf_indent (f, indent, " }\n"); 3037 } 3038 fprintf_indent (f, indent, "default:;\n"); 3039 3040 indent -= 4; 3041 fprintf_indent (f, indent, " }\n"); 3042 fprintf_indent (f, indent, " break;\n"); 3043 } 3044 3045 /* Close switch (TREE_CODE ()). */ 3046 if (exprs_len || fns_len || gexprs_len || gfns_len) 3047 { 3048 indent -= 4; 3049 fprintf_indent (f, indent, " default:;\n"); 3050 fprintf_indent (f, indent, " }\n"); 3051 } 3052 3053 for (unsigned i = 0; i < preds.length (); ++i) 3054 { 3055 expr *e = as_a <expr *> (preds[i]->op); 3056 predicate_id *p = as_a <predicate_id *> (e->operation); 3057 preds[i]->get_name (kid_opname); 3058 fprintf_indent (f, indent, "{\n"); 3059 indent += 2; 3060 fprintf_indent (f, indent, "tree %s_pops[%d];\n", kid_opname, p->nargs); 3061 fprintf_indent (f, indent, "if (%s_%s (%s, %s_pops%s))\n", 3062 gimple ? "gimple" : "tree", 3063 p->id, kid_opname, kid_opname, 3064 gimple ? ", valueize" : ""); 3065 fprintf_indent (f, indent, " {\n"); 3066 for (int j = 0; j < p->nargs; ++j) 3067 { 3068 char child_opname[20]; 3069 preds[i]->gen_opname (child_opname, j); 3070 fprintf_indent (f, indent + 4, "tree %s = %s_pops[%d];\n", 3071 child_opname, kid_opname, j); 3072 } 3073 preds[i]->gen_kids (f, indent + 4, gimple); 3074 fprintf (f, "}\n"); 3075 indent -= 2; 3076 fprintf_indent (f, indent, "}\n"); 3077 } 3078 3079 for (unsigned i = 0; i < others.length (); ++i) 3080 others[i]->gen (f, indent, gimple); 3081 } 3082 3083 /* Generate matching code for the decision tree operand. */ 3084 3085 void 3086 dt_operand::gen (FILE *f, int indent, bool gimple) 3087 { 3088 char opname[20]; 3089 get_name (opname); 3090 3091 unsigned n_braces = 0; 3092 3093 if (type == DT_OPERAND) 3094 switch (op->type) 3095 { 3096 case operand::OP_PREDICATE: 3097 n_braces = gen_predicate (f, indent, opname, gimple); 3098 break; 3099 3100 case operand::OP_EXPR: 3101 if (gimple) 3102 n_braces = gen_gimple_expr (f, indent); 3103 else 3104 n_braces = gen_generic_expr (f, indent, opname); 3105 break; 3106 3107 default: 3108 gcc_unreachable (); 3109 } 3110 else if (type == DT_TRUE) 3111 ; 3112 else if (type == DT_MATCH) 3113 n_braces = gen_match_op (f, indent, opname, gimple); 3114 else 3115 gcc_unreachable (); 3116 3117 indent += 4 * n_braces; 3118 gen_kids (f, indent, gimple); 3119 3120 for (unsigned i = 0; i < n_braces; ++i) 3121 { 3122 indent -= 4; 3123 if (indent < 0) 3124 indent = 0; 3125 fprintf_indent (f, indent, " }\n"); 3126 } 3127 } 3128 3129 3130 /* Generate code for the '(if ...)', '(with ..)' and actual transform 3131 step of a '(simplify ...)' or '(match ...)'. This handles everything 3132 that is not part of the decision tree (simplify->match). 3133 Main recursive worker. */ 3134 3135 void 3136 dt_simplify::gen_1 (FILE *f, int indent, bool gimple, operand *result) 3137 { 3138 if (result) 3139 { 3140 if (with_expr *w = dyn_cast <with_expr *> (result)) 3141 { 3142 fprintf_indent (f, indent, "{\n"); 3143 indent += 4; 3144 output_line_directive (f, w->location); 3145 w->with->gen_transform (f, indent, NULL, true, 1, "type", NULL); 3146 gen_1 (f, indent, gimple, w->subexpr); 3147 indent -= 4; 3148 fprintf_indent (f, indent, "}\n"); 3149 return; 3150 } 3151 else if (if_expr *ife = dyn_cast <if_expr *> (result)) 3152 { 3153 output_line_directive (f, ife->location); 3154 fprintf_indent (f, indent, "if ("); 3155 ife->cond->gen_transform (f, indent, NULL, true, 1, "type", NULL); 3156 fprintf (f, ")\n"); 3157 fprintf_indent (f, indent + 2, "{\n"); 3158 indent += 4; 3159 gen_1 (f, indent, gimple, ife->trueexpr); 3160 indent -= 4; 3161 fprintf_indent (f, indent + 2, "}\n"); 3162 if (ife->falseexpr) 3163 { 3164 fprintf_indent (f, indent, "else\n"); 3165 fprintf_indent (f, indent + 2, "{\n"); 3166 indent += 4; 3167 gen_1 (f, indent, gimple, ife->falseexpr); 3168 indent -= 4; 3169 fprintf_indent (f, indent + 2, "}\n"); 3170 } 3171 return; 3172 } 3173 } 3174 3175 /* Analyze captures and perform early-outs on the incoming arguments 3176 that cover cases we cannot handle. */ 3177 capture_info cinfo (s, result, gimple); 3178 if (s->kind == simplify::SIMPLIFY) 3179 { 3180 if (!gimple) 3181 { 3182 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i) 3183 if (cinfo.force_no_side_effects & (1 << i)) 3184 { 3185 fprintf_indent (f, indent, 3186 "if (TREE_SIDE_EFFECTS (op%d)) return NULL_TREE;\n", 3187 i); 3188 if (verbose >= 1) 3189 warning_at (as_a <expr *> (s->match)->ops[i]->location, 3190 "forcing toplevel operand to have no " 3191 "side-effects"); 3192 } 3193 for (int i = 0; i <= s->capture_max; ++i) 3194 if (cinfo.info[i].cse_p) 3195 ; 3196 else if (cinfo.info[i].force_no_side_effects_p 3197 && (cinfo.info[i].toplevel_msk 3198 & cinfo.force_no_side_effects) == 0) 3199 { 3200 fprintf_indent (f, indent, 3201 "if (TREE_SIDE_EFFECTS (captures[%d])) " 3202 "return NULL_TREE;\n", i); 3203 if (verbose >= 1) 3204 warning_at (cinfo.info[i].c->location, 3205 "forcing captured operand to have no " 3206 "side-effects"); 3207 } 3208 else if ((cinfo.info[i].toplevel_msk 3209 & cinfo.force_no_side_effects) != 0) 3210 /* Mark capture as having no side-effects if we had to verify 3211 that via forced toplevel operand checks. */ 3212 cinfo.info[i].force_no_side_effects_p = true; 3213 } 3214 if (gimple) 3215 { 3216 /* Force single-use restriction by only allowing simple 3217 results via setting seq to NULL. */ 3218 fprintf_indent (f, indent, "gimple_seq *lseq = seq;\n"); 3219 bool first_p = true; 3220 for (int i = 0; i <= s->capture_max; ++i) 3221 if (cinfo.info[i].force_single_use) 3222 { 3223 if (first_p) 3224 { 3225 fprintf_indent (f, indent, "if (lseq\n"); 3226 fprintf_indent (f, indent, " && ("); 3227 first_p = false; 3228 } 3229 else 3230 { 3231 fprintf (f, "\n"); 3232 fprintf_indent (f, indent, " || "); 3233 } 3234 fprintf (f, "!single_use (captures[%d])", i); 3235 } 3236 if (!first_p) 3237 { 3238 fprintf (f, "))\n"); 3239 fprintf_indent (f, indent, " lseq = NULL;\n"); 3240 } 3241 } 3242 } 3243 3244 fprintf_indent (f, indent, "if (dump_file && (dump_flags & TDF_FOLDING)) " 3245 "fprintf (dump_file, \"Applying pattern "); 3246 output_line_directive (f, 3247 result ? result->location : s->match->location, true); 3248 fprintf (f, ", %%s:%%d\\n\", __FILE__, __LINE__);\n"); 3249 3250 if (!result) 3251 { 3252 /* If there is no result then this is a predicate implementation. */ 3253 fprintf_indent (f, indent, "return true;\n"); 3254 } 3255 else if (gimple) 3256 { 3257 /* For GIMPLE simply drop NON_LVALUE_EXPR (which only appears 3258 in outermost position). */ 3259 if (result->type == operand::OP_EXPR 3260 && *as_a <expr *> (result)->operation == NON_LVALUE_EXPR) 3261 result = as_a <expr *> (result)->ops[0]; 3262 if (result->type == operand::OP_EXPR) 3263 { 3264 expr *e = as_a <expr *> (result); 3265 id_base *opr = e->operation; 3266 bool is_predicate = false; 3267 /* When we delay operator substituting during lowering of fors we 3268 make sure that for code-gen purposes the effects of each substitute 3269 are the same. Thus just look at that. */ 3270 if (user_id *uid = dyn_cast <user_id *> (opr)) 3271 opr = uid->substitutes[0]; 3272 else if (is_a <predicate_id *> (opr)) 3273 is_predicate = true; 3274 if (!is_predicate) 3275 fprintf_indent (f, indent, "*res_code = %s;\n", 3276 *e->operation == CONVERT_EXPR 3277 ? "NOP_EXPR" : e->operation->id); 3278 for (unsigned j = 0; j < e->ops.length (); ++j) 3279 { 3280 char dest[32]; 3281 snprintf (dest, 32, "res_ops[%d]", j); 3282 const char *optype 3283 = get_operand_type (opr, j, 3284 "type", e->expr_type, 3285 j == 0 ? NULL : "TREE_TYPE (res_ops[0])"); 3286 /* We need to expand GENERIC conditions we captured from 3287 COND_EXPRs and we need to unshare them when substituting 3288 into COND_EXPRs. */ 3289 int cond_handling = 0; 3290 if (!is_predicate) 3291 cond_handling = ((*opr == COND_EXPR 3292 || *opr == VEC_COND_EXPR) && j == 0) ? 1 : 2; 3293 e->ops[j]->gen_transform (f, indent, dest, true, 1, optype, 3294 &cinfo, indexes, cond_handling); 3295 } 3296 3297 /* Re-fold the toplevel result. It's basically an embedded 3298 gimple_build w/o actually building the stmt. */ 3299 if (!is_predicate) 3300 fprintf_indent (f, indent, 3301 "gimple_resimplify%d (lseq, res_code, type, " 3302 "res_ops, valueize);\n", e->ops.length ()); 3303 } 3304 else if (result->type == operand::OP_CAPTURE 3305 || result->type == operand::OP_C_EXPR) 3306 { 3307 result->gen_transform (f, indent, "res_ops[0]", true, 1, "type", 3308 &cinfo, indexes); 3309 fprintf_indent (f, indent, "*res_code = TREE_CODE (res_ops[0]);\n"); 3310 if (is_a <capture *> (result) 3311 && cinfo.info[as_a <capture *> (result)->where].cond_expr_cond_p) 3312 { 3313 /* ??? Stupid tcc_comparison GENERIC trees in COND_EXPRs. Deal 3314 with substituting a capture of that. */ 3315 fprintf_indent (f, indent, 3316 "if (COMPARISON_CLASS_P (res_ops[0]))\n"); 3317 fprintf_indent (f, indent, 3318 " {\n"); 3319 fprintf_indent (f, indent, 3320 " tree tem = res_ops[0];\n"); 3321 fprintf_indent (f, indent, 3322 " res_ops[0] = TREE_OPERAND (tem, 0);\n"); 3323 fprintf_indent (f, indent, 3324 " res_ops[1] = TREE_OPERAND (tem, 1);\n"); 3325 fprintf_indent (f, indent, 3326 " }\n"); 3327 } 3328 } 3329 else 3330 gcc_unreachable (); 3331 fprintf_indent (f, indent, "return true;\n"); 3332 } 3333 else /* GENERIC */ 3334 { 3335 bool is_predicate = false; 3336 if (result->type == operand::OP_EXPR) 3337 { 3338 expr *e = as_a <expr *> (result); 3339 id_base *opr = e->operation; 3340 /* When we delay operator substituting during lowering of fors we 3341 make sure that for code-gen purposes the effects of each substitute 3342 are the same. Thus just look at that. */ 3343 if (user_id *uid = dyn_cast <user_id *> (opr)) 3344 opr = uid->substitutes[0]; 3345 else if (is_a <predicate_id *> (opr)) 3346 is_predicate = true; 3347 /* Search for captures used multiple times in the result expression 3348 and wrap them in a SAVE_EXPR. Allow as many uses as in the 3349 original expression. */ 3350 if (!is_predicate) 3351 for (int i = 0; i < s->capture_max + 1; ++i) 3352 { 3353 if (cinfo.info[i].same_as != (unsigned)i 3354 || cinfo.info[i].cse_p) 3355 continue; 3356 if (cinfo.info[i].result_use_count 3357 > cinfo.info[i].match_use_count) 3358 fprintf_indent (f, indent, 3359 "if (! tree_invariant_p (captures[%d])) " 3360 "return NULL_TREE;\n", i); 3361 } 3362 for (unsigned j = 0; j < e->ops.length (); ++j) 3363 { 3364 char dest[32]; 3365 if (is_predicate) 3366 snprintf (dest, 32, "res_ops[%d]", j); 3367 else 3368 { 3369 fprintf_indent (f, indent, "tree res_op%d;\n", j); 3370 snprintf (dest, 32, "res_op%d", j); 3371 } 3372 const char *optype 3373 = get_operand_type (opr, j, 3374 "type", e->expr_type, 3375 j == 0 3376 ? NULL : "TREE_TYPE (res_op0)"); 3377 e->ops[j]->gen_transform (f, indent, dest, false, 1, optype, 3378 &cinfo, indexes); 3379 } 3380 if (is_predicate) 3381 fprintf_indent (f, indent, "return true;\n"); 3382 else 3383 { 3384 fprintf_indent (f, indent, "tree res;\n"); 3385 /* Re-fold the toplevel result. Use non_lvalue to 3386 build NON_LVALUE_EXPRs so they get properly 3387 ignored when in GIMPLE form. */ 3388 if (*opr == NON_LVALUE_EXPR) 3389 fprintf_indent (f, indent, 3390 "res = non_lvalue_loc (loc, res_op0);\n"); 3391 else 3392 { 3393 if (is_a <operator_id *> (opr)) 3394 fprintf_indent (f, indent, 3395 "res = fold_build%d_loc (loc, %s, type", 3396 e->ops.length (), 3397 *e->operation == CONVERT_EXPR 3398 ? "NOP_EXPR" : e->operation->id); 3399 else 3400 fprintf_indent (f, indent, 3401 "res = maybe_build_call_expr_loc (loc, " 3402 "%s, type, %d", e->operation->id, 3403 e->ops.length()); 3404 for (unsigned j = 0; j < e->ops.length (); ++j) 3405 fprintf (f, ", res_op%d", j); 3406 fprintf (f, ");\n"); 3407 if (!is_a <operator_id *> (opr)) 3408 { 3409 fprintf_indent (f, indent, "if (!res)\n"); 3410 fprintf_indent (f, indent, " return NULL_TREE;\n"); 3411 } 3412 } 3413 } 3414 } 3415 else if (result->type == operand::OP_CAPTURE 3416 || result->type == operand::OP_C_EXPR) 3417 3418 { 3419 fprintf_indent (f, indent, "tree res;\n"); 3420 result->gen_transform (f, indent, "res", false, 1, "type", 3421 &cinfo, indexes); 3422 } 3423 else 3424 gcc_unreachable (); 3425 if (!is_predicate) 3426 { 3427 /* Search for captures not used in the result expression and dependent 3428 on TREE_SIDE_EFFECTS emit omit_one_operand. */ 3429 for (int i = 0; i < s->capture_max + 1; ++i) 3430 { 3431 if (cinfo.info[i].same_as != (unsigned)i) 3432 continue; 3433 if (!cinfo.info[i].force_no_side_effects_p 3434 && !cinfo.info[i].expr_p 3435 && cinfo.info[i].result_use_count == 0) 3436 { 3437 fprintf_indent (f, indent, 3438 "if (TREE_SIDE_EFFECTS (captures[%d]))\n", 3439 i); 3440 fprintf_indent (f, indent + 2, 3441 "res = build2_loc (loc, COMPOUND_EXPR, type, " 3442 "fold_ignored_result (captures[%d]), res);\n", 3443 i); 3444 } 3445 } 3446 fprintf_indent (f, indent, "return res;\n"); 3447 } 3448 } 3449 } 3450 3451 /* Generate code for the '(if ...)', '(with ..)' and actual transform 3452 step of a '(simplify ...)' or '(match ...)'. This handles everything 3453 that is not part of the decision tree (simplify->match). */ 3454 3455 void 3456 dt_simplify::gen (FILE *f, int indent, bool gimple) 3457 { 3458 fprintf_indent (f, indent, "{\n"); 3459 indent += 2; 3460 output_line_directive (f, 3461 s->result ? s->result->location : s->match->location); 3462 if (s->capture_max >= 0) 3463 { 3464 char opname[20]; 3465 fprintf_indent (f, indent, "tree captures[%u] ATTRIBUTE_UNUSED = { %s", 3466 s->capture_max + 1, indexes[0]->get_name (opname)); 3467 3468 for (int i = 1; i <= s->capture_max; ++i) 3469 { 3470 if (!indexes[i]) 3471 break; 3472 fprintf (f, ", %s", indexes[i]->get_name (opname)); 3473 } 3474 fprintf (f, " };\n"); 3475 } 3476 3477 /* If we have a split-out function for the actual transform, call it. */ 3478 if (info && info->fname) 3479 { 3480 if (gimple) 3481 { 3482 fprintf_indent (f, indent, "if (%s (res_code, res_ops, seq, " 3483 "valueize, type, captures", info->fname); 3484 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i) 3485 if (s->for_subst_vec[i].first->used) 3486 fprintf (f, ", %s", s->for_subst_vec[i].second->id); 3487 fprintf (f, "))\n"); 3488 fprintf_indent (f, indent, " return true;\n"); 3489 } 3490 else 3491 { 3492 fprintf_indent (f, indent, "tree res = %s (loc, type", 3493 info->fname); 3494 for (unsigned i = 0; i < as_a <expr *> (s->match)->ops.length (); ++i) 3495 fprintf (f, ", op%d", i); 3496 fprintf (f, ", captures"); 3497 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i) 3498 { 3499 if (s->for_subst_vec[i].first->used) 3500 fprintf (f, ", %s", s->for_subst_vec[i].second->id); 3501 } 3502 fprintf (f, ");\n"); 3503 fprintf_indent (f, indent, "if (res) return res;\n"); 3504 } 3505 } 3506 else 3507 { 3508 for (unsigned i = 0; i < s->for_subst_vec.length (); ++i) 3509 { 3510 if (! s->for_subst_vec[i].first->used) 3511 continue; 3512 if (is_a <operator_id *> (s->for_subst_vec[i].second)) 3513 fprintf_indent (f, indent, "const enum tree_code %s = %s;\n", 3514 s->for_subst_vec[i].first->id, 3515 s->for_subst_vec[i].second->id); 3516 else if (is_a <fn_id *> (s->for_subst_vec[i].second)) 3517 fprintf_indent (f, indent, "const combined_fn %s = %s;\n", 3518 s->for_subst_vec[i].first->id, 3519 s->for_subst_vec[i].second->id); 3520 else 3521 gcc_unreachable (); 3522 } 3523 gen_1 (f, indent, gimple, s->result); 3524 } 3525 3526 indent -= 2; 3527 fprintf_indent (f, indent, "}\n"); 3528 } 3529 3530 3531 /* Hash function for finding equivalent transforms. */ 3532 3533 hashval_t 3534 sinfo_hashmap_traits::hash (const key_type &v) 3535 { 3536 /* Only bother to compare those originating from the same source pattern. */ 3537 return v->s->result->location; 3538 } 3539 3540 /* Compare function for finding equivalent transforms. */ 3541 3542 static bool 3543 compare_op (operand *o1, simplify *s1, operand *o2, simplify *s2) 3544 { 3545 if (o1->type != o2->type) 3546 return false; 3547 3548 switch (o1->type) 3549 { 3550 case operand::OP_IF: 3551 { 3552 if_expr *if1 = as_a <if_expr *> (o1); 3553 if_expr *if2 = as_a <if_expr *> (o2); 3554 /* ??? Properly compare c-exprs. */ 3555 if (if1->cond != if2->cond) 3556 return false; 3557 if (!compare_op (if1->trueexpr, s1, if2->trueexpr, s2)) 3558 return false; 3559 if (if1->falseexpr != if2->falseexpr 3560 || (if1->falseexpr 3561 && !compare_op (if1->falseexpr, s1, if2->falseexpr, s2))) 3562 return false; 3563 return true; 3564 } 3565 case operand::OP_WITH: 3566 { 3567 with_expr *with1 = as_a <with_expr *> (o1); 3568 with_expr *with2 = as_a <with_expr *> (o2); 3569 if (with1->with != with2->with) 3570 return false; 3571 return compare_op (with1->subexpr, s1, with2->subexpr, s2); 3572 } 3573 default:; 3574 } 3575 3576 /* We've hit a result. Time to compare capture-infos - this is required 3577 in addition to the conservative pointer-equivalency of the result IL. */ 3578 capture_info cinfo1 (s1, o1, true); 3579 capture_info cinfo2 (s2, o2, true); 3580 3581 if (cinfo1.force_no_side_effects != cinfo2.force_no_side_effects 3582 || cinfo1.info.length () != cinfo2.info.length ()) 3583 return false; 3584 3585 for (unsigned i = 0; i < cinfo1.info.length (); ++i) 3586 { 3587 if (cinfo1.info[i].expr_p != cinfo2.info[i].expr_p 3588 || cinfo1.info[i].cse_p != cinfo2.info[i].cse_p 3589 || (cinfo1.info[i].force_no_side_effects_p 3590 != cinfo2.info[i].force_no_side_effects_p) 3591 || cinfo1.info[i].force_single_use != cinfo2.info[i].force_single_use 3592 || cinfo1.info[i].cond_expr_cond_p != cinfo2.info[i].cond_expr_cond_p 3593 /* toplevel_msk is an optimization */ 3594 || cinfo1.info[i].result_use_count != cinfo2.info[i].result_use_count 3595 || cinfo1.info[i].same_as != cinfo2.info[i].same_as 3596 /* the pointer back to the capture is for diagnostics only */) 3597 return false; 3598 } 3599 3600 /* ??? Deep-compare the actual result. */ 3601 return o1 == o2; 3602 } 3603 3604 bool 3605 sinfo_hashmap_traits::equal_keys (const key_type &v, 3606 const key_type &candidate) 3607 { 3608 return compare_op (v->s->result, v->s, candidate->s->result, candidate->s); 3609 } 3610 3611 3612 /* Main entry to generate code for matching GIMPLE IL off the decision 3613 tree. */ 3614 3615 void 3616 decision_tree::gen (FILE *f, bool gimple) 3617 { 3618 sinfo_map_t si; 3619 3620 root->analyze (si); 3621 3622 fprintf (stderr, "%s decision tree has %u leafs, maximum depth %u and " 3623 "a total number of %u nodes\n", 3624 gimple ? "GIMPLE" : "GENERIC", 3625 root->num_leafs, root->max_level, root->total_size); 3626 3627 /* First split out the transform part of equal leafs. */ 3628 unsigned rcnt = 0; 3629 unsigned fcnt = 1; 3630 for (sinfo_map_t::iterator iter = si.begin (); 3631 iter != si.end (); ++iter) 3632 { 3633 sinfo *s = (*iter).second; 3634 /* Do not split out single uses. */ 3635 if (s->cnt <= 1) 3636 continue; 3637 3638 rcnt += s->cnt - 1; 3639 if (verbose >= 1) 3640 { 3641 fprintf (stderr, "found %u uses of", s->cnt); 3642 output_line_directive (stderr, s->s->s->result->location); 3643 } 3644 3645 /* Generate a split out function with the leaf transform code. */ 3646 s->fname = xasprintf ("%s_simplify_%u", gimple ? "gimple" : "generic", 3647 fcnt++); 3648 if (gimple) 3649 fprintf (f, "\nstatic bool\n" 3650 "%s (code_helper *res_code, tree *res_ops,\n" 3651 " gimple_seq *seq, tree (*valueize)(tree) " 3652 "ATTRIBUTE_UNUSED,\n" 3653 " const tree ARG_UNUSED (type), tree *ARG_UNUSED " 3654 "(captures)\n", 3655 s->fname); 3656 else 3657 { 3658 fprintf (f, "\nstatic tree\n" 3659 "%s (location_t ARG_UNUSED (loc), const tree ARG_UNUSED (type),\n", 3660 (*iter).second->fname); 3661 for (unsigned i = 0; 3662 i < as_a <expr *>(s->s->s->match)->ops.length (); ++i) 3663 fprintf (f, " tree ARG_UNUSED (op%d),", i); 3664 fprintf (f, " tree *captures\n"); 3665 } 3666 for (unsigned i = 0; i < s->s->s->for_subst_vec.length (); ++i) 3667 { 3668 if (! s->s->s->for_subst_vec[i].first->used) 3669 continue; 3670 if (is_a <operator_id *> (s->s->s->for_subst_vec[i].second)) 3671 fprintf (f, ", const enum tree_code ARG_UNUSED (%s)", 3672 s->s->s->for_subst_vec[i].first->id); 3673 else if (is_a <fn_id *> (s->s->s->for_subst_vec[i].second)) 3674 fprintf (f, ", const combined_fn ARG_UNUSED (%s)", 3675 s->s->s->for_subst_vec[i].first->id); 3676 } 3677 3678 fprintf (f, ")\n{\n"); 3679 s->s->gen_1 (f, 2, gimple, s->s->s->result); 3680 if (gimple) 3681 fprintf (f, " return false;\n"); 3682 else 3683 fprintf (f, " return NULL_TREE;\n"); 3684 fprintf (f, "}\n"); 3685 } 3686 fprintf (stderr, "removed %u duplicate tails\n", rcnt); 3687 3688 for (unsigned n = 1; n <= 3; ++n) 3689 { 3690 /* First generate split-out functions. */ 3691 for (unsigned i = 0; i < root->kids.length (); i++) 3692 { 3693 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]); 3694 expr *e = static_cast<expr *>(dop->op); 3695 if (e->ops.length () != n 3696 /* Builtin simplifications are somewhat premature on 3697 GENERIC. The following drops patterns with outermost 3698 calls. It's easy to emit overloads for function code 3699 though if necessary. */ 3700 || (!gimple 3701 && e->operation->kind != id_base::CODE)) 3702 continue; 3703 3704 if (gimple) 3705 fprintf (f, "\nstatic bool\n" 3706 "gimple_simplify_%s (code_helper *res_code, tree *res_ops,\n" 3707 " gimple_seq *seq, tree (*valueize)(tree) " 3708 "ATTRIBUTE_UNUSED,\n" 3709 " code_helper ARG_UNUSED (code), tree " 3710 "ARG_UNUSED (type)\n", 3711 e->operation->id); 3712 else 3713 fprintf (f, "\nstatic tree\n" 3714 "generic_simplify_%s (location_t ARG_UNUSED (loc), enum " 3715 "tree_code ARG_UNUSED (code), const tree ARG_UNUSED (type)", 3716 e->operation->id); 3717 for (unsigned i = 0; i < n; ++i) 3718 fprintf (f, ", tree op%d", i); 3719 fprintf (f, ")\n"); 3720 fprintf (f, "{\n"); 3721 dop->gen_kids (f, 2, gimple); 3722 if (gimple) 3723 fprintf (f, " return false;\n"); 3724 else 3725 fprintf (f, " return NULL_TREE;\n"); 3726 fprintf (f, "}\n"); 3727 } 3728 3729 /* Then generate the main entry with the outermost switch and 3730 tail-calls to the split-out functions. */ 3731 if (gimple) 3732 fprintf (f, "\nstatic bool\n" 3733 "gimple_simplify (code_helper *res_code, tree *res_ops,\n" 3734 " gimple_seq *seq, tree (*valueize)(tree),\n" 3735 " code_helper code, const tree type"); 3736 else 3737 fprintf (f, "\ntree\n" 3738 "generic_simplify (location_t loc, enum tree_code code, " 3739 "const tree type ATTRIBUTE_UNUSED"); 3740 for (unsigned i = 0; i < n; ++i) 3741 fprintf (f, ", tree op%d", i); 3742 fprintf (f, ")\n"); 3743 fprintf (f, "{\n"); 3744 3745 if (gimple) 3746 fprintf (f, " switch (code.get_rep())\n" 3747 " {\n"); 3748 else 3749 fprintf (f, " switch (code)\n" 3750 " {\n"); 3751 for (unsigned i = 0; i < root->kids.length (); i++) 3752 { 3753 dt_operand *dop = static_cast<dt_operand *>(root->kids[i]); 3754 expr *e = static_cast<expr *>(dop->op); 3755 if (e->ops.length () != n 3756 /* Builtin simplifications are somewhat premature on 3757 GENERIC. The following drops patterns with outermost 3758 calls. It's easy to emit overloads for function code 3759 though if necessary. */ 3760 || (!gimple 3761 && e->operation->kind != id_base::CODE)) 3762 continue; 3763 3764 if (*e->operation == CONVERT_EXPR 3765 || *e->operation == NOP_EXPR) 3766 fprintf (f, " CASE_CONVERT:\n"); 3767 else 3768 fprintf (f, " case %s%s:\n", 3769 is_a <fn_id *> (e->operation) ? "-" : "", 3770 e->operation->id); 3771 if (gimple) 3772 fprintf (f, " return gimple_simplify_%s (res_code, res_ops, " 3773 "seq, valueize, code, type", e->operation->id); 3774 else 3775 fprintf (f, " return generic_simplify_%s (loc, code, type", 3776 e->operation->id); 3777 for (unsigned i = 0; i < n; ++i) 3778 fprintf (f, ", op%d", i); 3779 fprintf (f, ");\n"); 3780 } 3781 fprintf (f, " default:;\n" 3782 " }\n"); 3783 3784 if (gimple) 3785 fprintf (f, " return false;\n"); 3786 else 3787 fprintf (f, " return NULL_TREE;\n"); 3788 fprintf (f, "}\n"); 3789 } 3790 } 3791 3792 /* Output code to implement the predicate P from the decision tree DT. */ 3793 3794 void 3795 write_predicate (FILE *f, predicate_id *p, decision_tree &dt, bool gimple) 3796 { 3797 fprintf (f, "\nbool\n" 3798 "%s%s (tree t%s%s)\n" 3799 "{\n", gimple ? "gimple_" : "tree_", p->id, 3800 p->nargs > 0 ? ", tree *res_ops" : "", 3801 gimple ? ", tree (*valueize)(tree) ATTRIBUTE_UNUSED" : ""); 3802 /* Conveniently make 'type' available. */ 3803 fprintf_indent (f, 2, "const tree type = TREE_TYPE (t);\n"); 3804 3805 if (!gimple) 3806 fprintf_indent (f, 2, "if (TREE_SIDE_EFFECTS (t)) return false;\n"); 3807 dt.root->gen_kids (f, 2, gimple); 3808 3809 fprintf_indent (f, 2, "return false;\n" 3810 "}\n"); 3811 } 3812 3813 /* Write the common header for the GIMPLE/GENERIC IL matching routines. */ 3814 3815 static void 3816 write_header (FILE *f, const char *head) 3817 { 3818 fprintf (f, "/* Generated automatically by the program `genmatch' from\n"); 3819 fprintf (f, " a IL pattern matching and simplification description. */\n"); 3820 3821 /* Include the header instead of writing it awkwardly quoted here. */ 3822 fprintf (f, "\n#include \"%s\"\n", head); 3823 } 3824 3825 3826 3827 /* AST parsing. */ 3828 3829 class parser 3830 { 3831 public: 3832 parser (cpp_reader *); 3833 3834 private: 3835 const cpp_token *next (); 3836 const cpp_token *peek (unsigned = 1); 3837 const cpp_token *peek_ident (const char * = NULL, unsigned = 1); 3838 const cpp_token *expect (enum cpp_ttype); 3839 const cpp_token *eat_token (enum cpp_ttype); 3840 const char *get_string (); 3841 const char *get_ident (); 3842 const cpp_token *eat_ident (const char *); 3843 const char *get_number (); 3844 3845 unsigned get_internal_capture_id (); 3846 3847 id_base *parse_operation (); 3848 operand *parse_capture (operand *, bool); 3849 operand *parse_expr (); 3850 c_expr *parse_c_expr (cpp_ttype); 3851 operand *parse_op (); 3852 3853 void record_operlist (source_location, user_id *); 3854 3855 void parse_pattern (); 3856 operand *parse_result (operand *, predicate_id *); 3857 void push_simplify (simplify::simplify_kind, 3858 vec<simplify *>&, operand *, operand *); 3859 void parse_simplify (simplify::simplify_kind, 3860 vec<simplify *>&, predicate_id *, operand *); 3861 void parse_for (source_location); 3862 void parse_if (source_location); 3863 void parse_predicates (source_location); 3864 void parse_operator_list (source_location); 3865 3866 void finish_match_operand (operand *); 3867 3868 cpp_reader *r; 3869 vec<c_expr *> active_ifs; 3870 vec<vec<user_id *> > active_fors; 3871 hash_set<user_id *> *oper_lists_set; 3872 vec<user_id *> oper_lists; 3873 3874 cid_map_t *capture_ids; 3875 unsigned last_id; 3876 3877 public: 3878 vec<simplify *> simplifiers; 3879 vec<predicate_id *> user_predicates; 3880 bool parsing_match_operand; 3881 }; 3882 3883 /* Lexing helpers. */ 3884 3885 /* Read the next non-whitespace token from R. */ 3886 3887 const cpp_token * 3888 parser::next () 3889 { 3890 const cpp_token *token; 3891 do 3892 { 3893 token = cpp_get_token (r); 3894 } 3895 while (token->type == CPP_PADDING); 3896 return token; 3897 } 3898 3899 /* Peek at the next non-whitespace token from R. */ 3900 3901 const cpp_token * 3902 parser::peek (unsigned num) 3903 { 3904 const cpp_token *token; 3905 unsigned i = 0; 3906 do 3907 { 3908 token = cpp_peek_token (r, i++); 3909 } 3910 while (token->type == CPP_PADDING 3911 || (--num > 0)); 3912 /* If we peek at EOF this is a fatal error as it leaves the 3913 cpp_reader in unusable state. Assume we really wanted a 3914 token and thus this EOF is unexpected. */ 3915 if (token->type == CPP_EOF) 3916 fatal_at (token, "unexpected end of file"); 3917 return token; 3918 } 3919 3920 /* Peek at the next identifier token (or return NULL if the next 3921 token is not an identifier or equal to ID if supplied). */ 3922 3923 const cpp_token * 3924 parser::peek_ident (const char *id, unsigned num) 3925 { 3926 const cpp_token *token = peek (num); 3927 if (token->type != CPP_NAME) 3928 return 0; 3929 3930 if (id == 0) 3931 return token; 3932 3933 const char *t = (const char *) CPP_HASHNODE (token->val.node.node)->ident.str; 3934 if (strcmp (id, t) == 0) 3935 return token; 3936 3937 return 0; 3938 } 3939 3940 /* Read the next token from R and assert it is of type TK. */ 3941 3942 const cpp_token * 3943 parser::expect (enum cpp_ttype tk) 3944 { 3945 const cpp_token *token = next (); 3946 if (token->type != tk) 3947 fatal_at (token, "expected %s, got %s", 3948 cpp_type2name (tk, 0), cpp_type2name (token->type, 0)); 3949 3950 return token; 3951 } 3952 3953 /* Consume the next token from R and assert it is of type TK. */ 3954 3955 const cpp_token * 3956 parser::eat_token (enum cpp_ttype tk) 3957 { 3958 return expect (tk); 3959 } 3960 3961 /* Read the next token from R and assert it is of type CPP_STRING and 3962 return its value. */ 3963 3964 const char * 3965 parser::get_string () 3966 { 3967 const cpp_token *token = expect (CPP_STRING); 3968 return (const char *)token->val.str.text; 3969 } 3970 3971 /* Read the next token from R and assert it is of type CPP_NAME and 3972 return its value. */ 3973 3974 const char * 3975 parser::get_ident () 3976 { 3977 const cpp_token *token = expect (CPP_NAME); 3978 return (const char *)CPP_HASHNODE (token->val.node.node)->ident.str; 3979 } 3980 3981 /* Eat an identifier token with value S from R. */ 3982 3983 const cpp_token * 3984 parser::eat_ident (const char *s) 3985 { 3986 const cpp_token *token = peek (); 3987 const char *t = get_ident (); 3988 if (strcmp (s, t) != 0) 3989 fatal_at (token, "expected '%s' got '%s'\n", s, t); 3990 return token; 3991 } 3992 3993 /* Read the next token from R and assert it is of type CPP_NUMBER and 3994 return its value. */ 3995 3996 const char * 3997 parser::get_number () 3998 { 3999 const cpp_token *token = expect (CPP_NUMBER); 4000 return (const char *)token->val.str.text; 4001 } 4002 4003 /* Return a capture ID that can be used internally. */ 4004 4005 unsigned 4006 parser::get_internal_capture_id () 4007 { 4008 unsigned newid = capture_ids->elements (); 4009 /* Big enough for a 32-bit UINT_MAX plus prefix. */ 4010 char id[13]; 4011 bool existed; 4012 sprintf (id, "__%u", newid); 4013 capture_ids->get_or_insert (xstrdup (id), &existed); 4014 if (existed) 4015 fatal ("reserved capture id '%s' already used", id); 4016 return newid; 4017 } 4018 4019 /* Record an operator-list use for transparent for handling. */ 4020 4021 void 4022 parser::record_operlist (source_location loc, user_id *p) 4023 { 4024 if (!oper_lists_set->add (p)) 4025 { 4026 if (!oper_lists.is_empty () 4027 && oper_lists[0]->substitutes.length () != p->substitutes.length ()) 4028 fatal_at (loc, "User-defined operator list does not have the " 4029 "same number of entries as others used in the pattern"); 4030 oper_lists.safe_push (p); 4031 } 4032 } 4033 4034 /* Parse the operator ID, special-casing convert?, convert1? and 4035 convert2? */ 4036 4037 id_base * 4038 parser::parse_operation () 4039 { 4040 const cpp_token *id_tok = peek (); 4041 const char *id = get_ident (); 4042 const cpp_token *token = peek (); 4043 if (strcmp (id, "convert0") == 0) 4044 fatal_at (id_tok, "use 'convert?' here"); 4045 else if (strcmp (id, "view_convert0") == 0) 4046 fatal_at (id_tok, "use 'view_convert?' here"); 4047 if (token->type == CPP_QUERY 4048 && !(token->flags & PREV_WHITE)) 4049 { 4050 if (strcmp (id, "convert") == 0) 4051 id = "convert0"; 4052 else if (strcmp (id, "convert1") == 0) 4053 ; 4054 else if (strcmp (id, "convert2") == 0) 4055 ; 4056 else if (strcmp (id, "view_convert") == 0) 4057 id = "view_convert0"; 4058 else if (strcmp (id, "view_convert1") == 0) 4059 ; 4060 else if (strcmp (id, "view_convert2") == 0) 4061 ; 4062 else 4063 fatal_at (id_tok, "non-convert operator conditionalized"); 4064 4065 if (!parsing_match_operand) 4066 fatal_at (id_tok, "conditional convert can only be used in " 4067 "match expression"); 4068 eat_token (CPP_QUERY); 4069 } 4070 else if (strcmp (id, "convert1") == 0 4071 || strcmp (id, "convert2") == 0 4072 || strcmp (id, "view_convert1") == 0 4073 || strcmp (id, "view_convert2") == 0) 4074 fatal_at (id_tok, "expected '?' after conditional operator"); 4075 id_base *op = get_operator (id); 4076 if (!op) 4077 fatal_at (id_tok, "unknown operator %s", id); 4078 4079 user_id *p = dyn_cast<user_id *> (op); 4080 if (p && p->is_oper_list) 4081 { 4082 if (active_fors.length() == 0) 4083 record_operlist (id_tok->src_loc, p); 4084 else 4085 fatal_at (id_tok, "operator-list %s cannot be exapnded inside 'for'", id); 4086 } 4087 return op; 4088 } 4089 4090 /* Parse a capture. 4091 capture = '@'<number> */ 4092 4093 struct operand * 4094 parser::parse_capture (operand *op, bool require_existing) 4095 { 4096 source_location src_loc = eat_token (CPP_ATSIGN)->src_loc; 4097 const cpp_token *token = peek (); 4098 const char *id = NULL; 4099 bool value_match = false; 4100 /* For matches parse @@ as a value-match denoting the prevailing operand. */ 4101 if (token->type == CPP_ATSIGN 4102 && ! (token->flags & PREV_WHITE) 4103 && parsing_match_operand) 4104 { 4105 eat_token (CPP_ATSIGN); 4106 token = peek (); 4107 value_match = true; 4108 } 4109 if (token->type == CPP_NUMBER) 4110 id = get_number (); 4111 else if (token->type == CPP_NAME) 4112 id = get_ident (); 4113 else 4114 fatal_at (token, "expected number or identifier"); 4115 unsigned next_id = capture_ids->elements (); 4116 bool existed; 4117 unsigned &num = capture_ids->get_or_insert (id, &existed); 4118 if (!existed) 4119 { 4120 if (require_existing) 4121 fatal_at (src_loc, "unknown capture id"); 4122 num = next_id; 4123 } 4124 return new capture (src_loc, num, op, value_match); 4125 } 4126 4127 /* Parse an expression 4128 expr = '(' <operation>[capture][flag][type] <operand>... ')' */ 4129 4130 struct operand * 4131 parser::parse_expr () 4132 { 4133 const cpp_token *token = peek (); 4134 expr *e = new expr (parse_operation (), token->src_loc); 4135 token = peek (); 4136 operand *op; 4137 bool is_commutative = false; 4138 bool force_capture = false; 4139 const char *expr_type = NULL; 4140 4141 if (token->type == CPP_COLON 4142 && !(token->flags & PREV_WHITE)) 4143 { 4144 eat_token (CPP_COLON); 4145 token = peek (); 4146 if (token->type == CPP_NAME 4147 && !(token->flags & PREV_WHITE)) 4148 { 4149 const char *s = get_ident (); 4150 if (!parsing_match_operand) 4151 expr_type = s; 4152 else 4153 { 4154 const char *sp = s; 4155 while (*sp) 4156 { 4157 if (*sp == 'c') 4158 { 4159 if (operator_id *p 4160 = dyn_cast<operator_id *> (e->operation)) 4161 { 4162 if (!commutative_tree_code (p->code) 4163 && !comparison_code_p (p->code)) 4164 fatal_at (token, "operation is not commutative"); 4165 } 4166 else if (user_id *p = dyn_cast<user_id *> (e->operation)) 4167 for (unsigned i = 0; 4168 i < p->substitutes.length (); ++i) 4169 { 4170 if (operator_id *q 4171 = dyn_cast<operator_id *> (p->substitutes[i])) 4172 { 4173 if (!commutative_tree_code (q->code) 4174 && !comparison_code_p (q->code)) 4175 fatal_at (token, "operation %s is not " 4176 "commutative", q->id); 4177 } 4178 } 4179 is_commutative = true; 4180 } 4181 else if (*sp == 'C') 4182 is_commutative = true; 4183 else if (*sp == 's') 4184 { 4185 e->force_single_use = true; 4186 force_capture = true; 4187 } 4188 else 4189 fatal_at (token, "flag %c not recognized", *sp); 4190 sp++; 4191 } 4192 } 4193 token = peek (); 4194 } 4195 else 4196 fatal_at (token, "expected flag or type specifying identifier"); 4197 } 4198 4199 if (token->type == CPP_ATSIGN 4200 && !(token->flags & PREV_WHITE)) 4201 op = parse_capture (e, false); 4202 else if (force_capture) 4203 { 4204 unsigned num = get_internal_capture_id (); 4205 op = new capture (token->src_loc, num, e, false); 4206 } 4207 else 4208 op = e; 4209 do 4210 { 4211 const cpp_token *token = peek (); 4212 if (token->type == CPP_CLOSE_PAREN) 4213 { 4214 if (e->operation->nargs != -1 4215 && e->operation->nargs != (int) e->ops.length ()) 4216 fatal_at (token, "'%s' expects %u operands, not %u", 4217 e->operation->id, e->operation->nargs, e->ops.length ()); 4218 if (is_commutative) 4219 { 4220 if (e->ops.length () == 2) 4221 e->is_commutative = true; 4222 else 4223 fatal_at (token, "only binary operators or function with " 4224 "two arguments can be marked commutative"); 4225 } 4226 e->expr_type = expr_type; 4227 return op; 4228 } 4229 else if (!(token->flags & PREV_WHITE)) 4230 fatal_at (token, "expected expression operand"); 4231 4232 e->append_op (parse_op ()); 4233 } 4234 while (1); 4235 } 4236 4237 /* Lex native C code delimited by START recording the preprocessing tokens 4238 for later processing. 4239 c_expr = ('{'|'(') <pp token>... ('}'|')') */ 4240 4241 c_expr * 4242 parser::parse_c_expr (cpp_ttype start) 4243 { 4244 const cpp_token *token; 4245 cpp_ttype end; 4246 unsigned opencnt; 4247 vec<cpp_token> code = vNULL; 4248 unsigned nr_stmts = 0; 4249 source_location loc = eat_token (start)->src_loc; 4250 if (start == CPP_OPEN_PAREN) 4251 end = CPP_CLOSE_PAREN; 4252 else if (start == CPP_OPEN_BRACE) 4253 end = CPP_CLOSE_BRACE; 4254 else 4255 gcc_unreachable (); 4256 opencnt = 1; 4257 do 4258 { 4259 token = next (); 4260 4261 /* Count brace pairs to find the end of the expr to match. */ 4262 if (token->type == start) 4263 opencnt++; 4264 else if (token->type == end 4265 && --opencnt == 0) 4266 break; 4267 else if (token->type == CPP_EOF) 4268 fatal_at (token, "unexpected end of file"); 4269 4270 /* This is a lame way of counting the number of statements. */ 4271 if (token->type == CPP_SEMICOLON) 4272 nr_stmts++; 4273 4274 /* If this is possibly a user-defined identifier mark it used. */ 4275 if (token->type == CPP_NAME) 4276 { 4277 id_base *idb = get_operator ((const char *)CPP_HASHNODE 4278 (token->val.node.node)->ident.str); 4279 user_id *p; 4280 if (idb && (p = dyn_cast<user_id *> (idb)) && p->is_oper_list) 4281 record_operlist (token->src_loc, p); 4282 } 4283 4284 /* Record the token. */ 4285 code.safe_push (*token); 4286 } 4287 while (1); 4288 return new c_expr (r, loc, code, nr_stmts, vNULL, capture_ids); 4289 } 4290 4291 /* Parse an operand which is either an expression, a predicate or 4292 a standalone capture. 4293 op = predicate | expr | c_expr | capture */ 4294 4295 struct operand * 4296 parser::parse_op () 4297 { 4298 const cpp_token *token = peek (); 4299 struct operand *op = NULL; 4300 if (token->type == CPP_OPEN_PAREN) 4301 { 4302 eat_token (CPP_OPEN_PAREN); 4303 op = parse_expr (); 4304 eat_token (CPP_CLOSE_PAREN); 4305 } 4306 else if (token->type == CPP_OPEN_BRACE) 4307 { 4308 op = parse_c_expr (CPP_OPEN_BRACE); 4309 } 4310 else 4311 { 4312 /* Remaining ops are either empty or predicates */ 4313 if (token->type == CPP_NAME) 4314 { 4315 const char *id = get_ident (); 4316 id_base *opr = get_operator (id); 4317 if (!opr) 4318 fatal_at (token, "expected predicate name"); 4319 if (operator_id *code = dyn_cast <operator_id *> (opr)) 4320 { 4321 if (code->nargs != 0) 4322 fatal_at (token, "using an operator with operands as predicate"); 4323 /* Parse the zero-operand operator "predicates" as 4324 expression. */ 4325 op = new expr (opr, token->src_loc); 4326 } 4327 else if (user_id *code = dyn_cast <user_id *> (opr)) 4328 { 4329 if (code->nargs != 0) 4330 fatal_at (token, "using an operator with operands as predicate"); 4331 /* Parse the zero-operand operator "predicates" as 4332 expression. */ 4333 op = new expr (opr, token->src_loc); 4334 } 4335 else if (predicate_id *p = dyn_cast <predicate_id *> (opr)) 4336 op = new predicate (p, token->src_loc); 4337 else 4338 fatal_at (token, "using an unsupported operator as predicate"); 4339 if (!parsing_match_operand) 4340 fatal_at (token, "predicates are only allowed in match expression"); 4341 token = peek (); 4342 if (token->flags & PREV_WHITE) 4343 return op; 4344 } 4345 else if (token->type != CPP_COLON 4346 && token->type != CPP_ATSIGN) 4347 fatal_at (token, "expected expression or predicate"); 4348 /* optionally followed by a capture and a predicate. */ 4349 if (token->type == CPP_COLON) 4350 fatal_at (token, "not implemented: predicate on leaf operand"); 4351 if (token->type == CPP_ATSIGN) 4352 op = parse_capture (op, !parsing_match_operand); 4353 } 4354 4355 return op; 4356 } 4357 4358 /* Create a new simplify from the current parsing state and MATCH, 4359 MATCH_LOC, RESULT and RESULT_LOC and push it to SIMPLIFIERS. */ 4360 4361 void 4362 parser::push_simplify (simplify::simplify_kind kind, 4363 vec<simplify *>& simplifiers, 4364 operand *match, operand *result) 4365 { 4366 /* Build and push a temporary for operator list uses in expressions. */ 4367 if (!oper_lists.is_empty ()) 4368 active_fors.safe_push (oper_lists); 4369 4370 simplifiers.safe_push 4371 (new simplify (kind, last_id++, match, result, 4372 active_fors.copy (), capture_ids)); 4373 4374 if (!oper_lists.is_empty ()) 4375 active_fors.pop (); 4376 } 4377 4378 /* Parse 4379 <result-op> = <op> | <if> | <with> 4380 <if> = '(' 'if' '(' <c-expr> ')' <result-op> ')' 4381 <with> = '(' 'with' '{' <c-expr> '}' <result-op> ')' 4382 and return it. */ 4383 4384 operand * 4385 parser::parse_result (operand *result, predicate_id *matcher) 4386 { 4387 const cpp_token *token = peek (); 4388 if (token->type != CPP_OPEN_PAREN) 4389 return parse_op (); 4390 4391 eat_token (CPP_OPEN_PAREN); 4392 if (peek_ident ("if")) 4393 { 4394 eat_ident ("if"); 4395 if_expr *ife = new if_expr (token->src_loc); 4396 ife->cond = parse_c_expr (CPP_OPEN_PAREN); 4397 if (peek ()->type == CPP_OPEN_PAREN) 4398 { 4399 ife->trueexpr = parse_result (result, matcher); 4400 if (peek ()->type == CPP_OPEN_PAREN) 4401 ife->falseexpr = parse_result (result, matcher); 4402 else if (peek ()->type != CPP_CLOSE_PAREN) 4403 ife->falseexpr = parse_op (); 4404 } 4405 else if (peek ()->type != CPP_CLOSE_PAREN) 4406 { 4407 ife->trueexpr = parse_op (); 4408 if (peek ()->type == CPP_OPEN_PAREN) 4409 ife->falseexpr = parse_result (result, matcher); 4410 else if (peek ()->type != CPP_CLOSE_PAREN) 4411 ife->falseexpr = parse_op (); 4412 } 4413 /* If this if is immediately closed then it contains a 4414 manual matcher or is part of a predicate definition. */ 4415 else /* if (peek ()->type == CPP_CLOSE_PAREN) */ 4416 { 4417 if (!matcher) 4418 fatal_at (peek (), "manual transform not implemented"); 4419 ife->trueexpr = result; 4420 } 4421 eat_token (CPP_CLOSE_PAREN); 4422 return ife; 4423 } 4424 else if (peek_ident ("with")) 4425 { 4426 eat_ident ("with"); 4427 with_expr *withe = new with_expr (token->src_loc); 4428 /* Parse (with c-expr expr) as (if-with (true) expr). */ 4429 withe->with = parse_c_expr (CPP_OPEN_BRACE); 4430 withe->with->nr_stmts = 0; 4431 withe->subexpr = parse_result (result, matcher); 4432 eat_token (CPP_CLOSE_PAREN); 4433 return withe; 4434 } 4435 else if (peek_ident ("switch")) 4436 { 4437 token = eat_ident ("switch"); 4438 source_location ifloc = eat_token (CPP_OPEN_PAREN)->src_loc; 4439 eat_ident ("if"); 4440 if_expr *ife = new if_expr (ifloc); 4441 operand *res = ife; 4442 ife->cond = parse_c_expr (CPP_OPEN_PAREN); 4443 if (peek ()->type == CPP_OPEN_PAREN) 4444 ife->trueexpr = parse_result (result, matcher); 4445 else 4446 ife->trueexpr = parse_op (); 4447 eat_token (CPP_CLOSE_PAREN); 4448 if (peek ()->type != CPP_OPEN_PAREN 4449 || !peek_ident ("if", 2)) 4450 fatal_at (token, "switch can be implemented with a single if"); 4451 while (peek ()->type != CPP_CLOSE_PAREN) 4452 { 4453 if (peek ()->type == CPP_OPEN_PAREN) 4454 { 4455 if (peek_ident ("if", 2)) 4456 { 4457 ifloc = eat_token (CPP_OPEN_PAREN)->src_loc; 4458 eat_ident ("if"); 4459 ife->falseexpr = new if_expr (ifloc); 4460 ife = as_a <if_expr *> (ife->falseexpr); 4461 ife->cond = parse_c_expr (CPP_OPEN_PAREN); 4462 if (peek ()->type == CPP_OPEN_PAREN) 4463 ife->trueexpr = parse_result (result, matcher); 4464 else 4465 ife->trueexpr = parse_op (); 4466 eat_token (CPP_CLOSE_PAREN); 4467 } 4468 else 4469 { 4470 /* switch default clause */ 4471 ife->falseexpr = parse_result (result, matcher); 4472 eat_token (CPP_CLOSE_PAREN); 4473 return res; 4474 } 4475 } 4476 else 4477 { 4478 /* switch default clause */ 4479 ife->falseexpr = parse_op (); 4480 eat_token (CPP_CLOSE_PAREN); 4481 return res; 4482 } 4483 } 4484 eat_token (CPP_CLOSE_PAREN); 4485 return res; 4486 } 4487 else 4488 { 4489 operand *op = result; 4490 if (!matcher) 4491 op = parse_expr (); 4492 eat_token (CPP_CLOSE_PAREN); 4493 return op; 4494 } 4495 } 4496 4497 /* Parse 4498 simplify = 'simplify' <expr> <result-op> 4499 or 4500 match = 'match' <ident> <expr> [<result-op>] 4501 and fill SIMPLIFIERS with the results. */ 4502 4503 void 4504 parser::parse_simplify (simplify::simplify_kind kind, 4505 vec<simplify *>& simplifiers, predicate_id *matcher, 4506 operand *result) 4507 { 4508 /* Reset the capture map. */ 4509 if (!capture_ids) 4510 capture_ids = new cid_map_t; 4511 /* Reset oper_lists and set. */ 4512 hash_set <user_id *> olist; 4513 oper_lists_set = &olist; 4514 oper_lists = vNULL; 4515 4516 const cpp_token *loc = peek (); 4517 parsing_match_operand = true; 4518 struct operand *match = parse_op (); 4519 finish_match_operand (match); 4520 parsing_match_operand = false; 4521 if (match->type == operand::OP_CAPTURE && !matcher) 4522 fatal_at (loc, "outermost expression cannot be captured"); 4523 if (match->type == operand::OP_EXPR 4524 && is_a <predicate_id *> (as_a <expr *> (match)->operation)) 4525 fatal_at (loc, "outermost expression cannot be a predicate"); 4526 4527 /* Splice active_ifs onto result and continue parsing the 4528 "then" expr. */ 4529 if_expr *active_if = NULL; 4530 for (int i = active_ifs.length (); i > 0; --i) 4531 { 4532 if_expr *ifc = new if_expr (active_ifs[i-1]->location); 4533 ifc->cond = active_ifs[i-1]; 4534 ifc->trueexpr = active_if; 4535 active_if = ifc; 4536 } 4537 if_expr *outermost_if = active_if; 4538 while (active_if && active_if->trueexpr) 4539 active_if = as_a <if_expr *> (active_if->trueexpr); 4540 4541 const cpp_token *token = peek (); 4542 4543 /* If this if is immediately closed then it is part of a predicate 4544 definition. Push it. */ 4545 if (token->type == CPP_CLOSE_PAREN) 4546 { 4547 if (!matcher) 4548 fatal_at (token, "expected transform expression"); 4549 if (active_if) 4550 { 4551 active_if->trueexpr = result; 4552 result = outermost_if; 4553 } 4554 push_simplify (kind, simplifiers, match, result); 4555 return; 4556 } 4557 4558 operand *tem = parse_result (result, matcher); 4559 if (active_if) 4560 { 4561 active_if->trueexpr = tem; 4562 result = outermost_if; 4563 } 4564 else 4565 result = tem; 4566 4567 push_simplify (kind, simplifiers, match, result); 4568 } 4569 4570 /* Parsing of the outer control structures. */ 4571 4572 /* Parse a for expression 4573 for = '(' 'for' <subst>... <pattern> ')' 4574 subst = <ident> '(' <ident>... ')' */ 4575 4576 void 4577 parser::parse_for (source_location) 4578 { 4579 auto_vec<const cpp_token *> user_id_tokens; 4580 vec<user_id *> user_ids = vNULL; 4581 const cpp_token *token; 4582 unsigned min_n_opers = 0, max_n_opers = 0; 4583 4584 while (1) 4585 { 4586 token = peek (); 4587 if (token->type != CPP_NAME) 4588 break; 4589 4590 /* Insert the user defined operators into the operator hash. */ 4591 const char *id = get_ident (); 4592 if (get_operator (id, true) != NULL) 4593 fatal_at (token, "operator already defined"); 4594 user_id *op = new user_id (id); 4595 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT); 4596 *slot = op; 4597 user_ids.safe_push (op); 4598 user_id_tokens.safe_push (token); 4599 4600 eat_token (CPP_OPEN_PAREN); 4601 4602 int arity = -1; 4603 while ((token = peek_ident ()) != 0) 4604 { 4605 const char *oper = get_ident (); 4606 id_base *idb = get_operator (oper, true); 4607 if (idb == NULL) 4608 fatal_at (token, "no such operator '%s'", oper); 4609 if (*idb == CONVERT0 || *idb == CONVERT1 || *idb == CONVERT2 4610 || *idb == VIEW_CONVERT0 || *idb == VIEW_CONVERT1 4611 || *idb == VIEW_CONVERT2) 4612 fatal_at (token, "conditional operators cannot be used inside for"); 4613 4614 if (arity == -1) 4615 arity = idb->nargs; 4616 else if (idb->nargs == -1) 4617 ; 4618 else if (idb->nargs != arity) 4619 fatal_at (token, "operator '%s' with arity %d does not match " 4620 "others with arity %d", oper, idb->nargs, arity); 4621 4622 user_id *p = dyn_cast<user_id *> (idb); 4623 if (p) 4624 { 4625 if (p->is_oper_list) 4626 op->substitutes.safe_splice (p->substitutes); 4627 else 4628 fatal_at (token, "iterator cannot be used as operator-list"); 4629 } 4630 else 4631 op->substitutes.safe_push (idb); 4632 } 4633 op->nargs = arity; 4634 token = expect (CPP_CLOSE_PAREN); 4635 4636 unsigned nsubstitutes = op->substitutes.length (); 4637 if (nsubstitutes == 0) 4638 fatal_at (token, "A user-defined operator must have at least " 4639 "one substitution"); 4640 if (max_n_opers == 0) 4641 { 4642 min_n_opers = nsubstitutes; 4643 max_n_opers = nsubstitutes; 4644 } 4645 else 4646 { 4647 if (nsubstitutes % min_n_opers != 0 4648 && min_n_opers % nsubstitutes != 0) 4649 fatal_at (token, "All user-defined identifiers must have a " 4650 "multiple number of operator substitutions of the " 4651 "smallest number of substitutions"); 4652 if (nsubstitutes < min_n_opers) 4653 min_n_opers = nsubstitutes; 4654 else if (nsubstitutes > max_n_opers) 4655 max_n_opers = nsubstitutes; 4656 } 4657 } 4658 4659 unsigned n_ids = user_ids.length (); 4660 if (n_ids == 0) 4661 fatal_at (token, "for requires at least one user-defined identifier"); 4662 4663 token = peek (); 4664 if (token->type == CPP_CLOSE_PAREN) 4665 fatal_at (token, "no pattern defined in for"); 4666 4667 active_fors.safe_push (user_ids); 4668 while (1) 4669 { 4670 token = peek (); 4671 if (token->type == CPP_CLOSE_PAREN) 4672 break; 4673 parse_pattern (); 4674 } 4675 active_fors.pop (); 4676 4677 /* Remove user-defined operators from the hash again. */ 4678 for (unsigned i = 0; i < user_ids.length (); ++i) 4679 { 4680 if (!user_ids[i]->used) 4681 warning_at (user_id_tokens[i], 4682 "operator %s defined but not used", user_ids[i]->id); 4683 operators->remove_elt (user_ids[i]); 4684 } 4685 } 4686 4687 /* Parse an identifier associated with a list of operators. 4688 oprs = '(' 'define_operator_list' <ident> <ident>... ')' */ 4689 4690 void 4691 parser::parse_operator_list (source_location) 4692 { 4693 const cpp_token *token = peek (); 4694 const char *id = get_ident (); 4695 4696 if (get_operator (id, true) != 0) 4697 fatal_at (token, "operator %s already defined", id); 4698 4699 user_id *op = new user_id (id, true); 4700 int arity = -1; 4701 4702 while ((token = peek_ident ()) != 0) 4703 { 4704 token = peek (); 4705 const char *oper = get_ident (); 4706 id_base *idb = get_operator (oper, true); 4707 4708 if (idb == 0) 4709 fatal_at (token, "no such operator '%s'", oper); 4710 4711 if (arity == -1) 4712 arity = idb->nargs; 4713 else if (idb->nargs == -1) 4714 ; 4715 else if (arity != idb->nargs) 4716 fatal_at (token, "operator '%s' with arity %d does not match " 4717 "others with arity %d", oper, idb->nargs, arity); 4718 4719 /* We allow composition of multiple operator lists. */ 4720 if (user_id *p = dyn_cast<user_id *> (idb)) 4721 op->substitutes.safe_splice (p->substitutes); 4722 else 4723 op->substitutes.safe_push (idb); 4724 } 4725 4726 // Check that there is no junk after id-list 4727 token = peek(); 4728 if (token->type != CPP_CLOSE_PAREN) 4729 fatal_at (token, "expected identifier got %s", cpp_type2name (token->type, 0)); 4730 4731 if (op->substitutes.length () == 0) 4732 fatal_at (token, "operator-list cannot be empty"); 4733 4734 op->nargs = arity; 4735 id_base **slot = operators->find_slot_with_hash (op, op->hashval, INSERT); 4736 *slot = op; 4737 } 4738 4739 /* Parse an outer if expression. 4740 if = '(' 'if' '(' <c-expr> ')' <pattern> ')' */ 4741 4742 void 4743 parser::parse_if (source_location) 4744 { 4745 c_expr *ifexpr = parse_c_expr (CPP_OPEN_PAREN); 4746 4747 const cpp_token *token = peek (); 4748 if (token->type == CPP_CLOSE_PAREN) 4749 fatal_at (token, "no pattern defined in if"); 4750 4751 active_ifs.safe_push (ifexpr); 4752 while (1) 4753 { 4754 const cpp_token *token = peek (); 4755 if (token->type == CPP_CLOSE_PAREN) 4756 break; 4757 4758 parse_pattern (); 4759 } 4760 active_ifs.pop (); 4761 } 4762 4763 /* Parse a list of predefined predicate identifiers. 4764 preds = '(' 'define_predicates' <ident>... ')' */ 4765 4766 void 4767 parser::parse_predicates (source_location) 4768 { 4769 do 4770 { 4771 const cpp_token *token = peek (); 4772 if (token->type != CPP_NAME) 4773 break; 4774 4775 add_predicate (get_ident ()); 4776 } 4777 while (1); 4778 } 4779 4780 /* Parse outer control structures. 4781 pattern = <preds>|<for>|<if>|<simplify>|<match> */ 4782 4783 void 4784 parser::parse_pattern () 4785 { 4786 /* All clauses start with '('. */ 4787 eat_token (CPP_OPEN_PAREN); 4788 const cpp_token *token = peek (); 4789 const char *id = get_ident (); 4790 if (strcmp (id, "simplify") == 0) 4791 { 4792 parse_simplify (simplify::SIMPLIFY, simplifiers, NULL, NULL); 4793 capture_ids = NULL; 4794 } 4795 else if (strcmp (id, "match") == 0) 4796 { 4797 bool with_args = false; 4798 source_location e_loc = peek ()->src_loc; 4799 if (peek ()->type == CPP_OPEN_PAREN) 4800 { 4801 eat_token (CPP_OPEN_PAREN); 4802 with_args = true; 4803 } 4804 const char *name = get_ident (); 4805 id_base *id = get_operator (name); 4806 predicate_id *p; 4807 if (!id) 4808 { 4809 p = add_predicate (name); 4810 user_predicates.safe_push (p); 4811 } 4812 else if ((p = dyn_cast <predicate_id *> (id))) 4813 ; 4814 else 4815 fatal_at (token, "cannot add a match to a non-predicate ID"); 4816 /* Parse (match <id> <arg>... (match-expr)) here. */ 4817 expr *e = NULL; 4818 if (with_args) 4819 { 4820 capture_ids = new cid_map_t; 4821 e = new expr (p, e_loc); 4822 while (peek ()->type == CPP_ATSIGN) 4823 e->append_op (parse_capture (NULL, false)); 4824 eat_token (CPP_CLOSE_PAREN); 4825 } 4826 if (p->nargs != -1 4827 && ((e && e->ops.length () != (unsigned)p->nargs) 4828 || (!e && p->nargs != 0))) 4829 fatal_at (token, "non-matching number of match operands"); 4830 p->nargs = e ? e->ops.length () : 0; 4831 parse_simplify (simplify::MATCH, p->matchers, p, e); 4832 capture_ids = NULL; 4833 } 4834 else if (strcmp (id, "for") == 0) 4835 parse_for (token->src_loc); 4836 else if (strcmp (id, "if") == 0) 4837 parse_if (token->src_loc); 4838 else if (strcmp (id, "define_predicates") == 0) 4839 { 4840 if (active_ifs.length () > 0 4841 || active_fors.length () > 0) 4842 fatal_at (token, "define_predicates inside if or for is not supported"); 4843 parse_predicates (token->src_loc); 4844 } 4845 else if (strcmp (id, "define_operator_list") == 0) 4846 { 4847 if (active_ifs.length () > 0 4848 || active_fors.length () > 0) 4849 fatal_at (token, "operator-list inside if or for is not supported"); 4850 parse_operator_list (token->src_loc); 4851 } 4852 else 4853 fatal_at (token, "expected %s'simplify', 'match', 'for' or 'if'", 4854 active_ifs.length () == 0 && active_fors.length () == 0 4855 ? "'define_predicates', " : ""); 4856 4857 eat_token (CPP_CLOSE_PAREN); 4858 } 4859 4860 /* Helper for finish_match_operand, collecting captures of OP in CPTS 4861 recursively. */ 4862 4863 static void 4864 walk_captures (operand *op, vec<vec<capture *> > cpts) 4865 { 4866 if (! op) 4867 return; 4868 4869 if (capture *c = dyn_cast <capture *> (op)) 4870 { 4871 cpts[c->where].safe_push (c); 4872 walk_captures (c->what, cpts); 4873 } 4874 else if (expr *e = dyn_cast <expr *> (op)) 4875 for (unsigned i = 0; i < e->ops.length (); ++i) 4876 walk_captures (e->ops[i], cpts); 4877 } 4878 4879 /* Finish up OP which is a match operand. */ 4880 4881 void 4882 parser::finish_match_operand (operand *op) 4883 { 4884 /* Look for matching captures, diagnose mis-uses of @@ and apply 4885 early lowering and distribution of value_match. */ 4886 auto_vec<vec<capture *> > cpts; 4887 cpts.safe_grow_cleared (capture_ids->elements ()); 4888 walk_captures (op, cpts); 4889 for (unsigned i = 0; i < cpts.length (); ++i) 4890 { 4891 capture *value_match = NULL; 4892 for (unsigned j = 0; j < cpts[i].length (); ++j) 4893 { 4894 if (cpts[i][j]->value_match) 4895 { 4896 if (value_match) 4897 fatal_at (cpts[i][j]->location, "duplicate @@"); 4898 value_match = cpts[i][j]; 4899 } 4900 } 4901 if (cpts[i].length () == 1 && value_match) 4902 fatal_at (value_match->location, "@@ without a matching capture"); 4903 if (value_match) 4904 { 4905 /* Duplicate prevailing capture with the existing ID, create 4906 a fake ID and rewrite all captures to use it. This turns 4907 @@1 into @__<newid>@1 and @1 into @__<newid>. */ 4908 value_match->what = new capture (value_match->location, 4909 value_match->where, 4910 value_match->what, false); 4911 /* Create a fake ID and rewrite all captures to use it. */ 4912 unsigned newid = get_internal_capture_id (); 4913 for (unsigned j = 0; j < cpts[i].length (); ++j) 4914 { 4915 cpts[i][j]->where = newid; 4916 cpts[i][j]->value_match = true; 4917 } 4918 } 4919 cpts[i].release (); 4920 } 4921 } 4922 4923 /* Main entry of the parser. Repeatedly parse outer control structures. */ 4924 4925 parser::parser (cpp_reader *r_) 4926 { 4927 r = r_; 4928 active_ifs = vNULL; 4929 active_fors = vNULL; 4930 simplifiers = vNULL; 4931 oper_lists_set = NULL; 4932 oper_lists = vNULL; 4933 capture_ids = NULL; 4934 user_predicates = vNULL; 4935 parsing_match_operand = false; 4936 last_id = 0; 4937 4938 const cpp_token *token = next (); 4939 while (token->type != CPP_EOF) 4940 { 4941 _cpp_backup_tokens (r, 1); 4942 parse_pattern (); 4943 token = next (); 4944 } 4945 } 4946 4947 4948 /* Helper for the linemap code. */ 4949 4950 static size_t 4951 round_alloc_size (size_t s) 4952 { 4953 return s; 4954 } 4955 4956 4957 /* The genmatch generator progam. It reads from a pattern description 4958 and outputs GIMPLE or GENERIC IL matching and simplification routines. */ 4959 4960 int 4961 main (int argc, char **argv) 4962 { 4963 cpp_reader *r; 4964 4965 progname = "genmatch"; 4966 4967 if (argc < 2) 4968 return 1; 4969 4970 bool gimple = true; 4971 char *input = argv[argc-1]; 4972 for (int i = 1; i < argc - 1; ++i) 4973 { 4974 if (strcmp (argv[i], "--gimple") == 0) 4975 gimple = true; 4976 else if (strcmp (argv[i], "--generic") == 0) 4977 gimple = false; 4978 else if (strcmp (argv[i], "-v") == 0) 4979 verbose = 1; 4980 else if (strcmp (argv[i], "-vv") == 0) 4981 verbose = 2; 4982 else 4983 { 4984 fprintf (stderr, "Usage: genmatch " 4985 "[--gimple] [--generic] [-v[v]] input\n"); 4986 return 1; 4987 } 4988 } 4989 4990 line_table = XCNEW (struct line_maps); 4991 linemap_init (line_table, 0); 4992 line_table->reallocator = xrealloc; 4993 line_table->round_alloc_size = round_alloc_size; 4994 4995 r = cpp_create_reader (CLK_GNUC99, NULL, line_table); 4996 cpp_callbacks *cb = cpp_get_callbacks (r); 4997 cb->error = error_cb; 4998 4999 /* Add the build directory to the #include "" search path. */ 5000 cpp_dir *dir = XCNEW (cpp_dir); 5001 dir->name = getpwd (); 5002 if (!dir->name) 5003 dir->name = ASTRDUP ("."); 5004 cpp_set_include_chains (r, dir, NULL, false); 5005 5006 if (!cpp_read_main_file (r, input)) 5007 return 1; 5008 cpp_define (r, gimple ? "GIMPLE=1": "GENERIC=1"); 5009 cpp_define (r, gimple ? "GENERIC=0": "GIMPLE=0"); 5010 5011 null_id = new id_base (id_base::NULL_ID, "null"); 5012 5013 /* Pre-seed operators. */ 5014 operators = new hash_table<id_base> (1024); 5015 #define DEFTREECODE(SYM, STRING, TYPE, NARGS) \ 5016 add_operator (SYM, # SYM, # TYPE, NARGS); 5017 #define END_OF_BASE_TREE_CODES 5018 #include "tree.def" 5019 add_operator (CONVERT0, "convert0", "tcc_unary", 1); 5020 add_operator (CONVERT1, "convert1", "tcc_unary", 1); 5021 add_operator (CONVERT2, "convert2", "tcc_unary", 1); 5022 add_operator (VIEW_CONVERT0, "view_convert0", "tcc_unary", 1); 5023 add_operator (VIEW_CONVERT1, "view_convert1", "tcc_unary", 1); 5024 add_operator (VIEW_CONVERT2, "view_convert2", "tcc_unary", 1); 5025 #undef END_OF_BASE_TREE_CODES 5026 #undef DEFTREECODE 5027 5028 /* Pre-seed builtin functions. 5029 ??? Cannot use N (name) as that is targetm.emultls.get_address 5030 for BUILT_IN_EMUTLS_GET_ADDRESS ... */ 5031 #define DEF_BUILTIN(ENUM, N, C, T, LT, B, F, NA, AT, IM, COND) \ 5032 add_function (ENUM, "CFN_" # ENUM); 5033 #include "builtins.def" 5034 5035 #define DEF_INTERNAL_FN(CODE, NAME, FNSPEC) \ 5036 add_function (IFN_##CODE, "CFN_" #CODE); 5037 #include "internal-fn.def" 5038 5039 /* Parse ahead! */ 5040 parser p (r); 5041 5042 if (gimple) 5043 write_header (stdout, "gimple-match-head.c"); 5044 else 5045 write_header (stdout, "generic-match-head.c"); 5046 5047 /* Go over all predicates defined with patterns and perform 5048 lowering and code generation. */ 5049 for (unsigned i = 0; i < p.user_predicates.length (); ++i) 5050 { 5051 predicate_id *pred = p.user_predicates[i]; 5052 lower (pred->matchers, gimple); 5053 5054 if (verbose == 2) 5055 for (unsigned i = 0; i < pred->matchers.length (); ++i) 5056 print_matches (pred->matchers[i]); 5057 5058 decision_tree dt; 5059 for (unsigned i = 0; i < pred->matchers.length (); ++i) 5060 dt.insert (pred->matchers[i], i); 5061 5062 if (verbose == 2) 5063 dt.print (stderr); 5064 5065 write_predicate (stdout, pred, dt, gimple); 5066 } 5067 5068 /* Lower the main simplifiers and generate code for them. */ 5069 lower (p.simplifiers, gimple); 5070 5071 if (verbose == 2) 5072 for (unsigned i = 0; i < p.simplifiers.length (); ++i) 5073 print_matches (p.simplifiers[i]); 5074 5075 decision_tree dt; 5076 for (unsigned i = 0; i < p.simplifiers.length (); ++i) 5077 dt.insert (p.simplifiers[i], i); 5078 5079 if (verbose == 2) 5080 dt.print (stderr); 5081 5082 dt.gen (stdout, gimple); 5083 5084 /* Finalize. */ 5085 cpp_finish (r, NULL); 5086 cpp_destroy (r); 5087 5088 delete operators; 5089 5090 return 0; 5091 } 5092