genrecog.c revision 117395
1/* Generate code from machine description to recognize rtl as insns. 2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1997, 1998, 3 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 15 License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING. If not, write to the Free 19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA 20 02111-1307, USA. */ 21 22 23/* This program is used to produce insn-recog.c, which contains a 24 function called `recog' plus its subroutines. These functions 25 contain a decision tree that recognizes whether an rtx, the 26 argument given to recog, is a valid instruction. 27 28 recog returns -1 if the rtx is not valid. If the rtx is valid, 29 recog returns a nonnegative number which is the insn code number 30 for the pattern that matched. This is the same as the order in the 31 machine description of the entry that matched. This number can be 32 used as an index into various insn_* tables, such as insn_template, 33 insn_outfun, and insn_n_operands (found in insn-output.c). 34 35 The third argument to recog is an optional pointer to an int. If 36 present, recog will accept a pattern if it matches except for 37 missing CLOBBER expressions at the end. In that case, the value 38 pointed to by the optional pointer will be set to the number of 39 CLOBBERs that need to be added (it should be initialized to zero by 40 the caller). If it is set nonzero, the caller should allocate a 41 PARALLEL of the appropriate size, copy the initial entries, and 42 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. 43 44 This program also generates the function `split_insns', which 45 returns 0 if the rtl could not be split, or it returns the split 46 rtl as an INSN list. 47 48 This program also generates the function `peephole2_insns', which 49 returns 0 if the rtl could not be matched. If there was a match, 50 the new rtl is returned in an INSN list, and LAST_INSN will point 51 to the last recognized insn in the old sequence. */ 52 53#include "hconfig.h" 54#include "system.h" 55#include "rtl.h" 56#include "errors.h" 57#include "gensupport.h" 58 59 60#define OUTPUT_LABEL(INDENT_STRING, LABEL_NUMBER) \ 61 printf("%sL%d: ATTRIBUTE_UNUSED_LABEL\n", (INDENT_STRING), (LABEL_NUMBER)) 62 63/* Holds an array of names indexed by insn_code_number. */ 64static char **insn_name_ptr = 0; 65static int insn_name_ptr_size = 0; 66 67/* A listhead of decision trees. The alternatives to a node are kept 68 in a doublely-linked list so we can easily add nodes to the proper 69 place when merging. */ 70 71struct decision_head 72{ 73 struct decision *first; 74 struct decision *last; 75}; 76 77/* A single test. The two accept types aren't tests per-se, but 78 their equality (or lack thereof) does affect tree merging so 79 it is convenient to keep them here. */ 80 81struct decision_test 82{ 83 /* A linked list through the tests attached to a node. */ 84 struct decision_test *next; 85 86 /* These types are roughly in the order in which we'd like to test them. */ 87 enum decision_type 88 { 89 DT_mode, DT_code, DT_veclen, 90 DT_elt_zero_int, DT_elt_one_int, DT_elt_zero_wide, DT_elt_zero_wide_safe, 91 DT_veclen_ge, DT_dup, DT_pred, DT_c_test, 92 DT_accept_op, DT_accept_insn 93 } type; 94 95 union 96 { 97 enum machine_mode mode; /* Machine mode of node. */ 98 RTX_CODE code; /* Code to test. */ 99 100 struct 101 { 102 const char *name; /* Predicate to call. */ 103 int index; /* Index into `preds' or -1. */ 104 enum machine_mode mode; /* Machine mode for node. */ 105 } pred; 106 107 const char *c_test; /* Additional test to perform. */ 108 int veclen; /* Length of vector. */ 109 int dup; /* Number of operand to compare against. */ 110 HOST_WIDE_INT intval; /* Value for XINT for XWINT. */ 111 int opno; /* Operand number matched. */ 112 113 struct { 114 int code_number; /* Insn number matched. */ 115 int lineno; /* Line number of the insn. */ 116 int num_clobbers_to_add; /* Number of CLOBBERs to be added. */ 117 } insn; 118 } u; 119}; 120 121/* Data structure for decision tree for recognizing legitimate insns. */ 122 123struct decision 124{ 125 struct decision_head success; /* Nodes to test on success. */ 126 struct decision *next; /* Node to test on failure. */ 127 struct decision *prev; /* Node whose failure tests us. */ 128 struct decision *afterward; /* Node to test on success, 129 but failure of successor nodes. */ 130 131 const char *position; /* String denoting position in pattern. */ 132 133 struct decision_test *tests; /* The tests for this node. */ 134 135 int number; /* Node number, used for labels */ 136 int subroutine_number; /* Number of subroutine this node starts */ 137 int need_label; /* Label needs to be output. */ 138}; 139 140#define SUBROUTINE_THRESHOLD 100 141 142static int next_subroutine_number; 143 144/* We can write three types of subroutines: One for insn recognition, 145 one to split insns, and one for peephole-type optimizations. This 146 defines which type is being written. */ 147 148enum routine_type { 149 RECOG, SPLIT, PEEPHOLE2 150}; 151 152#define IS_SPLIT(X) ((X) != RECOG) 153 154/* Next available node number for tree nodes. */ 155 156static int next_number; 157 158/* Next number to use as an insn_code. */ 159 160static int next_insn_code; 161 162/* Similar, but counts all expressions in the MD file; used for 163 error messages. */ 164 165static int next_index; 166 167/* Record the highest depth we ever have so we know how many variables to 168 allocate in each subroutine we make. */ 169 170static int max_depth; 171 172/* The line number of the start of the pattern currently being processed. */ 173static int pattern_lineno; 174 175/* Count of errors. */ 176static int error_count; 177 178/* This table contains a list of the rtl codes that can possibly match a 179 predicate defined in recog.c. The function `maybe_both_true' uses it to 180 deduce that there are no expressions that can be matches by certain pairs 181 of tree nodes. Also, if a predicate can match only one code, we can 182 hardwire that code into the node testing the predicate. */ 183 184static const struct pred_table 185{ 186 const char *const name; 187 const RTX_CODE codes[NUM_RTX_CODE]; 188} preds[] = { 189 {"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 190 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}}, 191#ifdef PREDICATE_CODES 192 PREDICATE_CODES 193#endif 194 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 195 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF, 196 PLUS, MINUS, MULT}}, 197 {"register_operand", {SUBREG, REG, ADDRESSOF}}, 198 {"pmode_register_operand", {SUBREG, REG, ADDRESSOF}}, 199 {"scratch_operand", {SCRATCH, REG}}, 200 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 201 LABEL_REF}}, 202 {"const_int_operand", {CONST_INT}}, 203 {"const_double_operand", {CONST_INT, CONST_DOUBLE}}, 204 {"nonimmediate_operand", {SUBREG, REG, MEM, ADDRESSOF}}, 205 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 206 LABEL_REF, SUBREG, REG, ADDRESSOF}}, 207 {"push_operand", {MEM}}, 208 {"pop_operand", {MEM}}, 209 {"memory_operand", {SUBREG, MEM}}, 210 {"indirect_operand", {SUBREG, MEM}}, 211 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU, 212 UNORDERED, ORDERED, UNEQ, UNGE, UNGT, UNLE, 213 UNLT, LTGT}}, 214 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 215 LABEL_REF, SUBREG, REG, MEM, ADDRESSOF}} 216}; 217 218#define NUM_KNOWN_PREDS ARRAY_SIZE (preds) 219 220static const char *const special_mode_pred_table[] = { 221#ifdef SPECIAL_MODE_PREDICATES 222 SPECIAL_MODE_PREDICATES 223#endif 224 "pmode_register_operand" 225}; 226 227#define NUM_SPECIAL_MODE_PREDS ARRAY_SIZE (special_mode_pred_table) 228 229static struct decision *new_decision 230 PARAMS ((const char *, struct decision_head *)); 231static struct decision_test *new_decision_test 232 PARAMS ((enum decision_type, struct decision_test ***)); 233static rtx find_operand 234 PARAMS ((rtx, int)); 235static rtx find_matching_operand 236 PARAMS ((rtx, int)); 237static void validate_pattern 238 PARAMS ((rtx, rtx, rtx, int)); 239static struct decision *add_to_sequence 240 PARAMS ((rtx, struct decision_head *, const char *, enum routine_type, int)); 241 242static int maybe_both_true_2 243 PARAMS ((struct decision_test *, struct decision_test *)); 244static int maybe_both_true_1 245 PARAMS ((struct decision_test *, struct decision_test *)); 246static int maybe_both_true 247 PARAMS ((struct decision *, struct decision *, int)); 248 249static int nodes_identical_1 250 PARAMS ((struct decision_test *, struct decision_test *)); 251static int nodes_identical 252 PARAMS ((struct decision *, struct decision *)); 253static void merge_accept_insn 254 PARAMS ((struct decision *, struct decision *)); 255static void merge_trees 256 PARAMS ((struct decision_head *, struct decision_head *)); 257 258static void factor_tests 259 PARAMS ((struct decision_head *)); 260static void simplify_tests 261 PARAMS ((struct decision_head *)); 262static int break_out_subroutines 263 PARAMS ((struct decision_head *, int)); 264static void find_afterward 265 PARAMS ((struct decision_head *, struct decision *)); 266 267static void change_state 268 PARAMS ((const char *, const char *, struct decision *, const char *)); 269static void print_code 270 PARAMS ((enum rtx_code)); 271static void write_afterward 272 PARAMS ((struct decision *, struct decision *, const char *)); 273static struct decision *write_switch 274 PARAMS ((struct decision *, int)); 275static void write_cond 276 PARAMS ((struct decision_test *, int, enum routine_type)); 277static void write_action 278 PARAMS ((struct decision *, struct decision_test *, int, int, 279 struct decision *, enum routine_type)); 280static int is_unconditional 281 PARAMS ((struct decision_test *, enum routine_type)); 282static int write_node 283 PARAMS ((struct decision *, int, enum routine_type)); 284static void write_tree_1 285 PARAMS ((struct decision_head *, int, enum routine_type)); 286static void write_tree 287 PARAMS ((struct decision_head *, const char *, enum routine_type, int)); 288static void write_subroutine 289 PARAMS ((struct decision_head *, enum routine_type)); 290static void write_subroutines 291 PARAMS ((struct decision_head *, enum routine_type)); 292static void write_header 293 PARAMS ((void)); 294 295static struct decision_head make_insn_sequence 296 PARAMS ((rtx, enum routine_type)); 297static void process_tree 298 PARAMS ((struct decision_head *, enum routine_type)); 299 300static void record_insn_name 301 PARAMS ((int, const char *)); 302 303static void debug_decision_0 304 PARAMS ((struct decision *, int, int)); 305static void debug_decision_1 306 PARAMS ((struct decision *, int)); 307static void debug_decision_2 308 PARAMS ((struct decision_test *)); 309extern void debug_decision 310 PARAMS ((struct decision *)); 311extern void debug_decision_list 312 PARAMS ((struct decision *)); 313 314/* Create a new node in sequence after LAST. */ 315 316static struct decision * 317new_decision (position, last) 318 const char *position; 319 struct decision_head *last; 320{ 321 struct decision *new 322 = (struct decision *) xmalloc (sizeof (struct decision)); 323 324 memset (new, 0, sizeof (*new)); 325 new->success = *last; 326 new->position = xstrdup (position); 327 new->number = next_number++; 328 329 last->first = last->last = new; 330 return new; 331} 332 333/* Create a new test and link it in at PLACE. */ 334 335static struct decision_test * 336new_decision_test (type, pplace) 337 enum decision_type type; 338 struct decision_test ***pplace; 339{ 340 struct decision_test **place = *pplace; 341 struct decision_test *test; 342 343 test = (struct decision_test *) xmalloc (sizeof (*test)); 344 test->next = *place; 345 test->type = type; 346 *place = test; 347 348 place = &test->next; 349 *pplace = place; 350 351 return test; 352} 353 354/* Search for and return operand N. */ 355 356static rtx 357find_operand (pattern, n) 358 rtx pattern; 359 int n; 360{ 361 const char *fmt; 362 RTX_CODE code; 363 int i, j, len; 364 rtx r; 365 366 code = GET_CODE (pattern); 367 if ((code == MATCH_SCRATCH 368 || code == MATCH_INSN 369 || code == MATCH_OPERAND 370 || code == MATCH_OPERATOR 371 || code == MATCH_PARALLEL) 372 && XINT (pattern, 0) == n) 373 return pattern; 374 375 fmt = GET_RTX_FORMAT (code); 376 len = GET_RTX_LENGTH (code); 377 for (i = 0; i < len; i++) 378 { 379 switch (fmt[i]) 380 { 381 case 'e': case 'u': 382 if ((r = find_operand (XEXP (pattern, i), n)) != NULL_RTX) 383 return r; 384 break; 385 386 case 'V': 387 if (! XVEC (pattern, i)) 388 break; 389 /* FALLTHRU */ 390 391 case 'E': 392 for (j = 0; j < XVECLEN (pattern, i); j++) 393 if ((r = find_operand (XVECEXP (pattern, i, j), n)) != NULL_RTX) 394 return r; 395 break; 396 397 case 'i': case 'w': case '0': case 's': 398 break; 399 400 default: 401 abort (); 402 } 403 } 404 405 return NULL; 406} 407 408/* Search for and return operand M, such that it has a matching 409 constraint for operand N. */ 410 411static rtx 412find_matching_operand (pattern, n) 413 rtx pattern; 414 int n; 415{ 416 const char *fmt; 417 RTX_CODE code; 418 int i, j, len; 419 rtx r; 420 421 code = GET_CODE (pattern); 422 if (code == MATCH_OPERAND 423 && (XSTR (pattern, 2)[0] == '0' + n 424 || (XSTR (pattern, 2)[0] == '%' 425 && XSTR (pattern, 2)[1] == '0' + n))) 426 return pattern; 427 428 fmt = GET_RTX_FORMAT (code); 429 len = GET_RTX_LENGTH (code); 430 for (i = 0; i < len; i++) 431 { 432 switch (fmt[i]) 433 { 434 case 'e': case 'u': 435 if ((r = find_matching_operand (XEXP (pattern, i), n))) 436 return r; 437 break; 438 439 case 'V': 440 if (! XVEC (pattern, i)) 441 break; 442 /* FALLTHRU */ 443 444 case 'E': 445 for (j = 0; j < XVECLEN (pattern, i); j++) 446 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n))) 447 return r; 448 break; 449 450 case 'i': case 'w': case '0': case 's': 451 break; 452 453 default: 454 abort (); 455 } 456 } 457 458 return NULL; 459} 460 461 462/* Check for various errors in patterns. SET is nonnull for a destination, 463 and is the complete set pattern. SET_CODE is '=' for normal sets, and 464 '+' within a context that requires in-out constraints. */ 465 466static void 467validate_pattern (pattern, insn, set, set_code) 468 rtx pattern; 469 rtx insn; 470 rtx set; 471 int set_code; 472{ 473 const char *fmt; 474 RTX_CODE code; 475 size_t i, len; 476 int j; 477 478 code = GET_CODE (pattern); 479 switch (code) 480 { 481 case MATCH_SCRATCH: 482 return; 483 484 case MATCH_INSN: 485 case MATCH_OPERAND: 486 case MATCH_OPERATOR: 487 { 488 const char *pred_name = XSTR (pattern, 1); 489 int allows_non_lvalue = 1, allows_non_const = 1; 490 int special_mode_pred = 0; 491 const char *c_test; 492 493 if (GET_CODE (insn) == DEFINE_INSN) 494 c_test = XSTR (insn, 2); 495 else 496 c_test = XSTR (insn, 1); 497 498 if (pred_name[0] != 0) 499 { 500 for (i = 0; i < NUM_KNOWN_PREDS; i++) 501 if (! strcmp (preds[i].name, pred_name)) 502 break; 503 504 if (i < NUM_KNOWN_PREDS) 505 { 506 int j; 507 508 allows_non_lvalue = allows_non_const = 0; 509 for (j = 0; preds[i].codes[j] != 0; j++) 510 { 511 RTX_CODE c = preds[i].codes[j]; 512 if (c != LABEL_REF 513 && c != SYMBOL_REF 514 && c != CONST_INT 515 && c != CONST_DOUBLE 516 && c != CONST 517 && c != HIGH 518 && c != CONSTANT_P_RTX) 519 allows_non_const = 1; 520 521 if (c != REG 522 && c != SUBREG 523 && c != MEM 524 && c != ADDRESSOF 525 && c != CONCAT 526 && c != PARALLEL 527 && c != STRICT_LOW_PART) 528 allows_non_lvalue = 1; 529 } 530 } 531 else 532 { 533#ifdef PREDICATE_CODES 534 /* If the port has a list of the predicates it uses but 535 omits one, warn. */ 536 message_with_line (pattern_lineno, 537 "warning: `%s' not in PREDICATE_CODES", 538 pred_name); 539#endif 540 } 541 542 for (i = 0; i < NUM_SPECIAL_MODE_PREDS; ++i) 543 if (strcmp (pred_name, special_mode_pred_table[i]) == 0) 544 { 545 special_mode_pred = 1; 546 break; 547 } 548 } 549 550 if (code == MATCH_OPERAND) 551 { 552 const char constraints0 = XSTR (pattern, 2)[0]; 553 554 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we 555 don't use the MATCH_OPERAND constraint, only the predicate. 556 This is confusing to folks doing new ports, so help them 557 not make the mistake. */ 558 if (GET_CODE (insn) == DEFINE_EXPAND 559 || GET_CODE (insn) == DEFINE_SPLIT 560 || GET_CODE (insn) == DEFINE_PEEPHOLE2) 561 { 562 if (constraints0) 563 message_with_line (pattern_lineno, 564 "warning: constraints not supported in %s", 565 rtx_name[GET_CODE (insn)]); 566 } 567 568 /* A MATCH_OPERAND that is a SET should have an output reload. */ 569 else if (set && constraints0) 570 { 571 if (set_code == '+') 572 { 573 if (constraints0 == '+') 574 ; 575 /* If we've only got an output reload for this operand, 576 we'd better have a matching input operand. */ 577 else if (constraints0 == '=' 578 && find_matching_operand (insn, XINT (pattern, 0))) 579 ; 580 else 581 { 582 message_with_line (pattern_lineno, 583 "operand %d missing in-out reload", 584 XINT (pattern, 0)); 585 error_count++; 586 } 587 } 588 else if (constraints0 != '=' && constraints0 != '+') 589 { 590 message_with_line (pattern_lineno, 591 "operand %d missing output reload", 592 XINT (pattern, 0)); 593 error_count++; 594 } 595 } 596 } 597 598 /* Allowing non-lvalues in destinations -- particularly CONST_INT -- 599 while not likely to occur at runtime, results in less efficient 600 code from insn-recog.c. */ 601 if (set 602 && pred_name[0] != '\0' 603 && allows_non_lvalue) 604 { 605 message_with_line (pattern_lineno, 606 "warning: destination operand %d allows non-lvalue", 607 XINT (pattern, 0)); 608 } 609 610 /* A modeless MATCH_OPERAND can be handy when we can 611 check for multiple modes in the c_test. In most other cases, 612 it is a mistake. Only DEFINE_INSN is eligible, since SPLIT 613 and PEEP2 can FAIL within the output pattern. Exclude 614 address_operand, since its mode is related to the mode of 615 the memory not the operand. Exclude the SET_DEST of a call 616 instruction, as that is a common idiom. */ 617 618 if (GET_MODE (pattern) == VOIDmode 619 && code == MATCH_OPERAND 620 && GET_CODE (insn) == DEFINE_INSN 621 && allows_non_const 622 && ! special_mode_pred 623 && pred_name[0] != '\0' 624 && strcmp (pred_name, "address_operand") != 0 625 && strstr (c_test, "operands") == NULL 626 && ! (set 627 && GET_CODE (set) == SET 628 && GET_CODE (SET_SRC (set)) == CALL)) 629 { 630 message_with_line (pattern_lineno, 631 "warning: operand %d missing mode?", 632 XINT (pattern, 0)); 633 } 634 return; 635 } 636 637 case SET: 638 { 639 enum machine_mode dmode, smode; 640 rtx dest, src; 641 642 dest = SET_DEST (pattern); 643 src = SET_SRC (pattern); 644 645 /* STRICT_LOW_PART is a wrapper. Its argument is the real 646 destination, and it's mode should match the source. */ 647 if (GET_CODE (dest) == STRICT_LOW_PART) 648 dest = XEXP (dest, 0); 649 650 /* Find the referant for a DUP. */ 651 652 if (GET_CODE (dest) == MATCH_DUP 653 || GET_CODE (dest) == MATCH_OP_DUP 654 || GET_CODE (dest) == MATCH_PAR_DUP) 655 dest = find_operand (insn, XINT (dest, 0)); 656 657 if (GET_CODE (src) == MATCH_DUP 658 || GET_CODE (src) == MATCH_OP_DUP 659 || GET_CODE (src) == MATCH_PAR_DUP) 660 src = find_operand (insn, XINT (src, 0)); 661 662 dmode = GET_MODE (dest); 663 smode = GET_MODE (src); 664 665 /* The mode of an ADDRESS_OPERAND is the mode of the memory 666 reference, not the mode of the address. */ 667 if (GET_CODE (src) == MATCH_OPERAND 668 && ! strcmp (XSTR (src, 1), "address_operand")) 669 ; 670 671 /* The operands of a SET must have the same mode unless one 672 is VOIDmode. */ 673 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode) 674 { 675 message_with_line (pattern_lineno, 676 "mode mismatch in set: %smode vs %smode", 677 GET_MODE_NAME (dmode), GET_MODE_NAME (smode)); 678 error_count++; 679 } 680 681 /* If only one of the operands is VOIDmode, and PC or CC0 is 682 not involved, it's probably a mistake. */ 683 else if (dmode != smode 684 && GET_CODE (dest) != PC 685 && GET_CODE (dest) != CC0 686 && GET_CODE (src) != PC 687 && GET_CODE (src) != CC0 688 && GET_CODE (src) != CONST_INT) 689 { 690 const char *which; 691 which = (dmode == VOIDmode ? "destination" : "source"); 692 message_with_line (pattern_lineno, 693 "warning: %s missing a mode?", which); 694 } 695 696 if (dest != SET_DEST (pattern)) 697 validate_pattern (dest, insn, pattern, '='); 698 validate_pattern (SET_DEST (pattern), insn, pattern, '='); 699 validate_pattern (SET_SRC (pattern), insn, NULL_RTX, 0); 700 return; 701 } 702 703 case CLOBBER: 704 validate_pattern (SET_DEST (pattern), insn, pattern, '='); 705 return; 706 707 case ZERO_EXTRACT: 708 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0); 709 validate_pattern (XEXP (pattern, 1), insn, NULL_RTX, 0); 710 validate_pattern (XEXP (pattern, 2), insn, NULL_RTX, 0); 711 return; 712 713 case STRICT_LOW_PART: 714 validate_pattern (XEXP (pattern, 0), insn, set, set ? '+' : 0); 715 return; 716 717 case LABEL_REF: 718 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode) 719 { 720 message_with_line (pattern_lineno, 721 "operand to label_ref %smode not VOIDmode", 722 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0)))); 723 error_count++; 724 } 725 break; 726 727 default: 728 break; 729 } 730 731 fmt = GET_RTX_FORMAT (code); 732 len = GET_RTX_LENGTH (code); 733 for (i = 0; i < len; i++) 734 { 735 switch (fmt[i]) 736 { 737 case 'e': case 'u': 738 validate_pattern (XEXP (pattern, i), insn, NULL_RTX, 0); 739 break; 740 741 case 'E': 742 for (j = 0; j < XVECLEN (pattern, i); j++) 743 validate_pattern (XVECEXP (pattern, i, j), insn, NULL_RTX, 0); 744 break; 745 746 case 'i': case 'w': case '0': case 's': 747 break; 748 749 default: 750 abort (); 751 } 752 } 753} 754 755/* Create a chain of nodes to verify that an rtl expression matches 756 PATTERN. 757 758 LAST is a pointer to the listhead in the previous node in the chain (or 759 in the calling function, for the first node). 760 761 POSITION is the string representing the current position in the insn. 762 763 INSN_TYPE is the type of insn for which we are emitting code. 764 765 A pointer to the final node in the chain is returned. */ 766 767static struct decision * 768add_to_sequence (pattern, last, position, insn_type, top) 769 rtx pattern; 770 struct decision_head *last; 771 const char *position; 772 enum routine_type insn_type; 773 int top; 774{ 775 RTX_CODE code; 776 struct decision *this, *sub; 777 struct decision_test *test; 778 struct decision_test **place; 779 char *subpos; 780 size_t i; 781 const char *fmt; 782 int depth = strlen (position); 783 int len; 784 enum machine_mode mode; 785 786 if (depth > max_depth) 787 max_depth = depth; 788 789 subpos = (char *) xmalloc (depth + 2); 790 strcpy (subpos, position); 791 subpos[depth + 1] = 0; 792 793 sub = this = new_decision (position, last); 794 place = &this->tests; 795 796 restart: 797 mode = GET_MODE (pattern); 798 code = GET_CODE (pattern); 799 800 switch (code) 801 { 802 case PARALLEL: 803 /* Toplevel peephole pattern. */ 804 if (insn_type == PEEPHOLE2 && top) 805 { 806 /* We don't need the node we just created -- unlink it. */ 807 last->first = last->last = NULL; 808 809 for (i = 0; i < (size_t) XVECLEN (pattern, 0); i++) 810 { 811 /* Which insn we're looking at is represented by A-Z. We don't 812 ever use 'A', however; it is always implied. */ 813 814 subpos[depth] = (i > 0 ? 'A' + i : 0); 815 sub = add_to_sequence (XVECEXP (pattern, 0, i), 816 last, subpos, insn_type, 0); 817 last = &sub->success; 818 } 819 goto ret; 820 } 821 822 /* Else nothing special. */ 823 break; 824 825 case MATCH_PARALLEL: 826 /* The explicit patterns within a match_parallel enforce a minimum 827 length on the vector. The match_parallel predicate may allow 828 for more elements. We do need to check for this minimum here 829 or the code generated to match the internals may reference data 830 beyond the end of the vector. */ 831 test = new_decision_test (DT_veclen_ge, &place); 832 test->u.veclen = XVECLEN (pattern, 2); 833 /* FALLTHRU */ 834 835 case MATCH_OPERAND: 836 case MATCH_SCRATCH: 837 case MATCH_OPERATOR: 838 case MATCH_INSN: 839 { 840 const char *pred_name; 841 RTX_CODE was_code = code; 842 int allows_const_int = 1; 843 844 if (code == MATCH_SCRATCH) 845 { 846 pred_name = "scratch_operand"; 847 code = UNKNOWN; 848 } 849 else 850 { 851 pred_name = XSTR (pattern, 1); 852 if (code == MATCH_PARALLEL) 853 code = PARALLEL; 854 else 855 code = UNKNOWN; 856 } 857 858 if (pred_name[0] != 0) 859 { 860 test = new_decision_test (DT_pred, &place); 861 test->u.pred.name = pred_name; 862 test->u.pred.mode = mode; 863 864 /* See if we know about this predicate and save its number. 865 If we do, and it only accepts one code, note that fact. 866 867 If we know that the predicate does not allow CONST_INT, 868 we know that the only way the predicate can match is if 869 the modes match (here we use the kludge of relying on the 870 fact that "address_operand" accepts CONST_INT; otherwise, 871 it would have to be a special case), so we can test the 872 mode (but we need not). This fact should considerably 873 simplify the generated code. */ 874 875 for (i = 0; i < NUM_KNOWN_PREDS; i++) 876 if (! strcmp (preds[i].name, pred_name)) 877 break; 878 879 if (i < NUM_KNOWN_PREDS) 880 { 881 int j; 882 883 test->u.pred.index = i; 884 885 if (preds[i].codes[1] == 0 && code == UNKNOWN) 886 code = preds[i].codes[0]; 887 888 allows_const_int = 0; 889 for (j = 0; preds[i].codes[j] != 0; j++) 890 if (preds[i].codes[j] == CONST_INT) 891 { 892 allows_const_int = 1; 893 break; 894 } 895 } 896 else 897 test->u.pred.index = -1; 898 } 899 900 /* Can't enforce a mode if we allow const_int. */ 901 if (allows_const_int) 902 mode = VOIDmode; 903 904 /* Accept the operand, ie. record it in `operands'. */ 905 test = new_decision_test (DT_accept_op, &place); 906 test->u.opno = XINT (pattern, 0); 907 908 if (was_code == MATCH_OPERATOR || was_code == MATCH_PARALLEL) 909 { 910 char base = (was_code == MATCH_OPERATOR ? '0' : 'a'); 911 for (i = 0; i < (size_t) XVECLEN (pattern, 2); i++) 912 { 913 subpos[depth] = i + base; 914 sub = add_to_sequence (XVECEXP (pattern, 2, i), 915 &sub->success, subpos, insn_type, 0); 916 } 917 } 918 goto fini; 919 } 920 921 case MATCH_OP_DUP: 922 code = UNKNOWN; 923 924 test = new_decision_test (DT_dup, &place); 925 test->u.dup = XINT (pattern, 0); 926 927 test = new_decision_test (DT_accept_op, &place); 928 test->u.opno = XINT (pattern, 0); 929 930 for (i = 0; i < (size_t) XVECLEN (pattern, 1); i++) 931 { 932 subpos[depth] = i + '0'; 933 sub = add_to_sequence (XVECEXP (pattern, 1, i), 934 &sub->success, subpos, insn_type, 0); 935 } 936 goto fini; 937 938 case MATCH_DUP: 939 case MATCH_PAR_DUP: 940 code = UNKNOWN; 941 942 test = new_decision_test (DT_dup, &place); 943 test->u.dup = XINT (pattern, 0); 944 goto fini; 945 946 case ADDRESS: 947 pattern = XEXP (pattern, 0); 948 goto restart; 949 950 default: 951 break; 952 } 953 954 fmt = GET_RTX_FORMAT (code); 955 len = GET_RTX_LENGTH (code); 956 957 /* Do tests against the current node first. */ 958 for (i = 0; i < (size_t) len; i++) 959 { 960 if (fmt[i] == 'i') 961 { 962 if (i == 0) 963 { 964 test = new_decision_test (DT_elt_zero_int, &place); 965 test->u.intval = XINT (pattern, i); 966 } 967 else if (i == 1) 968 { 969 test = new_decision_test (DT_elt_one_int, &place); 970 test->u.intval = XINT (pattern, i); 971 } 972 else 973 abort (); 974 } 975 else if (fmt[i] == 'w') 976 { 977 /* If this value actually fits in an int, we can use a switch 978 statement here, so indicate that. */ 979 enum decision_type type 980 = ((int) XWINT (pattern, i) == XWINT (pattern, i)) 981 ? DT_elt_zero_wide_safe : DT_elt_zero_wide; 982 983 if (i != 0) 984 abort (); 985 986 test = new_decision_test (type, &place); 987 test->u.intval = XWINT (pattern, i); 988 } 989 else if (fmt[i] == 'E') 990 { 991 if (i != 0) 992 abort (); 993 994 test = new_decision_test (DT_veclen, &place); 995 test->u.veclen = XVECLEN (pattern, i); 996 } 997 } 998 999 /* Now test our sub-patterns. */ 1000 for (i = 0; i < (size_t) len; i++) 1001 { 1002 switch (fmt[i]) 1003 { 1004 case 'e': case 'u': 1005 subpos[depth] = '0' + i; 1006 sub = add_to_sequence (XEXP (pattern, i), &sub->success, 1007 subpos, insn_type, 0); 1008 break; 1009 1010 case 'E': 1011 { 1012 int j; 1013 for (j = 0; j < XVECLEN (pattern, i); j++) 1014 { 1015 subpos[depth] = 'a' + j; 1016 sub = add_to_sequence (XVECEXP (pattern, i, j), 1017 &sub->success, subpos, insn_type, 0); 1018 } 1019 break; 1020 } 1021 1022 case 'i': case 'w': 1023 /* Handled above. */ 1024 break; 1025 case '0': 1026 break; 1027 1028 default: 1029 abort (); 1030 } 1031 } 1032 1033 fini: 1034 /* Insert nodes testing mode and code, if they're still relevant, 1035 before any of the nodes we may have added above. */ 1036 if (code != UNKNOWN) 1037 { 1038 place = &this->tests; 1039 test = new_decision_test (DT_code, &place); 1040 test->u.code = code; 1041 } 1042 1043 if (mode != VOIDmode) 1044 { 1045 place = &this->tests; 1046 test = new_decision_test (DT_mode, &place); 1047 test->u.mode = mode; 1048 } 1049 1050 /* If we didn't insert any tests or accept nodes, hork. */ 1051 if (this->tests == NULL) 1052 abort (); 1053 1054 ret: 1055 free (subpos); 1056 return sub; 1057} 1058 1059/* A subroutine of maybe_both_true; examines only one test. 1060 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */ 1061 1062static int 1063maybe_both_true_2 (d1, d2) 1064 struct decision_test *d1, *d2; 1065{ 1066 if (d1->type == d2->type) 1067 { 1068 switch (d1->type) 1069 { 1070 case DT_mode: 1071 return d1->u.mode == d2->u.mode; 1072 1073 case DT_code: 1074 return d1->u.code == d2->u.code; 1075 1076 case DT_veclen: 1077 return d1->u.veclen == d2->u.veclen; 1078 1079 case DT_elt_zero_int: 1080 case DT_elt_one_int: 1081 case DT_elt_zero_wide: 1082 case DT_elt_zero_wide_safe: 1083 return d1->u.intval == d2->u.intval; 1084 1085 default: 1086 break; 1087 } 1088 } 1089 1090 /* If either has a predicate that we know something about, set 1091 things up so that D1 is the one that always has a known 1092 predicate. Then see if they have any codes in common. */ 1093 1094 if (d1->type == DT_pred || d2->type == DT_pred) 1095 { 1096 if (d2->type == DT_pred) 1097 { 1098 struct decision_test *tmp; 1099 tmp = d1, d1 = d2, d2 = tmp; 1100 } 1101 1102 /* If D2 tests a mode, see if it matches D1. */ 1103 if (d1->u.pred.mode != VOIDmode) 1104 { 1105 if (d2->type == DT_mode) 1106 { 1107 if (d1->u.pred.mode != d2->u.mode 1108 /* The mode of an address_operand predicate is the 1109 mode of the memory, not the operand. It can only 1110 be used for testing the predicate, so we must 1111 ignore it here. */ 1112 && strcmp (d1->u.pred.name, "address_operand") != 0) 1113 return 0; 1114 } 1115 /* Don't check two predicate modes here, because if both predicates 1116 accept CONST_INT, then both can still be true even if the modes 1117 are different. If they don't accept CONST_INT, there will be a 1118 separate DT_mode that will make maybe_both_true_1 return 0. */ 1119 } 1120 1121 if (d1->u.pred.index >= 0) 1122 { 1123 /* If D2 tests a code, see if it is in the list of valid 1124 codes for D1's predicate. */ 1125 if (d2->type == DT_code) 1126 { 1127 const RTX_CODE *c = &preds[d1->u.pred.index].codes[0]; 1128 while (*c != 0) 1129 { 1130 if (*c == d2->u.code) 1131 break; 1132 ++c; 1133 } 1134 if (*c == 0) 1135 return 0; 1136 } 1137 1138 /* Otherwise see if the predicates have any codes in common. */ 1139 else if (d2->type == DT_pred && d2->u.pred.index >= 0) 1140 { 1141 const RTX_CODE *c1 = &preds[d1->u.pred.index].codes[0]; 1142 int common = 0; 1143 1144 while (*c1 != 0 && !common) 1145 { 1146 const RTX_CODE *c2 = &preds[d2->u.pred.index].codes[0]; 1147 while (*c2 != 0 && !common) 1148 { 1149 common = (*c1 == *c2); 1150 ++c2; 1151 } 1152 ++c1; 1153 } 1154 1155 if (!common) 1156 return 0; 1157 } 1158 } 1159 } 1160 1161 /* Tests vs veclen may be known when strict equality is involved. */ 1162 if (d1->type == DT_veclen && d2->type == DT_veclen_ge) 1163 return d1->u.veclen >= d2->u.veclen; 1164 if (d1->type == DT_veclen_ge && d2->type == DT_veclen) 1165 return d2->u.veclen >= d1->u.veclen; 1166 1167 return -1; 1168} 1169 1170/* A subroutine of maybe_both_true; examines all the tests for a given node. 1171 Returns > 0 for "definitely both true" and < 0 for "maybe both true". */ 1172 1173static int 1174maybe_both_true_1 (d1, d2) 1175 struct decision_test *d1, *d2; 1176{ 1177 struct decision_test *t1, *t2; 1178 1179 /* A match_operand with no predicate can match anything. Recognize 1180 this by the existence of a lone DT_accept_op test. */ 1181 if (d1->type == DT_accept_op || d2->type == DT_accept_op) 1182 return 1; 1183 1184 /* Eliminate pairs of tests while they can exactly match. */ 1185 while (d1 && d2 && d1->type == d2->type) 1186 { 1187 if (maybe_both_true_2 (d1, d2) == 0) 1188 return 0; 1189 d1 = d1->next, d2 = d2->next; 1190 } 1191 1192 /* After that, consider all pairs. */ 1193 for (t1 = d1; t1 ; t1 = t1->next) 1194 for (t2 = d2; t2 ; t2 = t2->next) 1195 if (maybe_both_true_2 (t1, t2) == 0) 1196 return 0; 1197 1198 return -1; 1199} 1200 1201/* Return 0 if we can prove that there is no RTL that can match both 1202 D1 and D2. Otherwise, return 1 (it may be that there is an RTL that 1203 can match both or just that we couldn't prove there wasn't such an RTL). 1204 1205 TOPLEVEL is nonzero if we are to only look at the top level and not 1206 recursively descend. */ 1207 1208static int 1209maybe_both_true (d1, d2, toplevel) 1210 struct decision *d1, *d2; 1211 int toplevel; 1212{ 1213 struct decision *p1, *p2; 1214 int cmp; 1215 1216 /* Don't compare strings on the different positions in insn. Doing so 1217 is incorrect and results in false matches from constructs like 1218 1219 [(set (subreg:HI (match_operand:SI "register_operand" "r") 0) 1220 (subreg:HI (match_operand:SI "register_operand" "r") 0))] 1221 vs 1222 [(set (match_operand:HI "register_operand" "r") 1223 (match_operand:HI "register_operand" "r"))] 1224 1225 If we are presented with such, we are recursing through the remainder 1226 of a node's success nodes (from the loop at the end of this function). 1227 Skip forward until we come to a position that matches. 1228 1229 Due to the way position strings are constructed, we know that iterating 1230 forward from the lexically lower position (e.g. "00") will run into 1231 the lexically higher position (e.g. "1") and not the other way around. 1232 This saves a bit of effort. */ 1233 1234 cmp = strcmp (d1->position, d2->position); 1235 if (cmp != 0) 1236 { 1237 if (toplevel) 1238 abort (); 1239 1240 /* If the d2->position was lexically lower, swap. */ 1241 if (cmp > 0) 1242 p1 = d1, d1 = d2, d2 = p1; 1243 1244 if (d1->success.first == 0) 1245 return 1; 1246 for (p1 = d1->success.first; p1; p1 = p1->next) 1247 if (maybe_both_true (p1, d2, 0)) 1248 return 1; 1249 1250 return 0; 1251 } 1252 1253 /* Test the current level. */ 1254 cmp = maybe_both_true_1 (d1->tests, d2->tests); 1255 if (cmp >= 0) 1256 return cmp; 1257 1258 /* We can't prove that D1 and D2 cannot both be true. If we are only 1259 to check the top level, return 1. Otherwise, see if we can prove 1260 that all choices in both successors are mutually exclusive. If 1261 either does not have any successors, we can't prove they can't both 1262 be true. */ 1263 1264 if (toplevel || d1->success.first == 0 || d2->success.first == 0) 1265 return 1; 1266 1267 for (p1 = d1->success.first; p1; p1 = p1->next) 1268 for (p2 = d2->success.first; p2; p2 = p2->next) 1269 if (maybe_both_true (p1, p2, 0)) 1270 return 1; 1271 1272 return 0; 1273} 1274 1275/* A subroutine of nodes_identical. Examine two tests for equivalence. */ 1276 1277static int 1278nodes_identical_1 (d1, d2) 1279 struct decision_test *d1, *d2; 1280{ 1281 switch (d1->type) 1282 { 1283 case DT_mode: 1284 return d1->u.mode == d2->u.mode; 1285 1286 case DT_code: 1287 return d1->u.code == d2->u.code; 1288 1289 case DT_pred: 1290 return (d1->u.pred.mode == d2->u.pred.mode 1291 && strcmp (d1->u.pred.name, d2->u.pred.name) == 0); 1292 1293 case DT_c_test: 1294 return strcmp (d1->u.c_test, d2->u.c_test) == 0; 1295 1296 case DT_veclen: 1297 case DT_veclen_ge: 1298 return d1->u.veclen == d2->u.veclen; 1299 1300 case DT_dup: 1301 return d1->u.dup == d2->u.dup; 1302 1303 case DT_elt_zero_int: 1304 case DT_elt_one_int: 1305 case DT_elt_zero_wide: 1306 case DT_elt_zero_wide_safe: 1307 return d1->u.intval == d2->u.intval; 1308 1309 case DT_accept_op: 1310 return d1->u.opno == d2->u.opno; 1311 1312 case DT_accept_insn: 1313 /* Differences will be handled in merge_accept_insn. */ 1314 return 1; 1315 1316 default: 1317 abort (); 1318 } 1319} 1320 1321/* True iff the two nodes are identical (on one level only). Due 1322 to the way these lists are constructed, we shouldn't have to 1323 consider different orderings on the tests. */ 1324 1325static int 1326nodes_identical (d1, d2) 1327 struct decision *d1, *d2; 1328{ 1329 struct decision_test *t1, *t2; 1330 1331 for (t1 = d1->tests, t2 = d2->tests; t1 && t2; t1 = t1->next, t2 = t2->next) 1332 { 1333 if (t1->type != t2->type) 1334 return 0; 1335 if (! nodes_identical_1 (t1, t2)) 1336 return 0; 1337 } 1338 1339 /* For success, they should now both be null. */ 1340 if (t1 != t2) 1341 return 0; 1342 1343 /* Check that their subnodes are at the same position, as any one set 1344 of sibling decisions must be at the same position. Allowing this 1345 requires complications to find_afterward and when change_state is 1346 invoked. */ 1347 if (d1->success.first 1348 && d2->success.first 1349 && strcmp (d1->success.first->position, d2->success.first->position)) 1350 return 0; 1351 1352 return 1; 1353} 1354 1355/* A subroutine of merge_trees; given two nodes that have been declared 1356 identical, cope with two insn accept states. If they differ in the 1357 number of clobbers, then the conflict was created by make_insn_sequence 1358 and we can drop the with-clobbers version on the floor. If both 1359 nodes have no additional clobbers, we have found an ambiguity in the 1360 source machine description. */ 1361 1362static void 1363merge_accept_insn (oldd, addd) 1364 struct decision *oldd, *addd; 1365{ 1366 struct decision_test *old, *add; 1367 1368 for (old = oldd->tests; old; old = old->next) 1369 if (old->type == DT_accept_insn) 1370 break; 1371 if (old == NULL) 1372 return; 1373 1374 for (add = addd->tests; add; add = add->next) 1375 if (add->type == DT_accept_insn) 1376 break; 1377 if (add == NULL) 1378 return; 1379 1380 /* If one node is for a normal insn and the second is for the base 1381 insn with clobbers stripped off, the second node should be ignored. */ 1382 1383 if (old->u.insn.num_clobbers_to_add == 0 1384 && add->u.insn.num_clobbers_to_add > 0) 1385 { 1386 /* Nothing to do here. */ 1387 } 1388 else if (old->u.insn.num_clobbers_to_add > 0 1389 && add->u.insn.num_clobbers_to_add == 0) 1390 { 1391 /* In this case, replace OLD with ADD. */ 1392 old->u.insn = add->u.insn; 1393 } 1394 else 1395 { 1396 message_with_line (add->u.insn.lineno, "`%s' matches `%s'", 1397 get_insn_name (add->u.insn.code_number), 1398 get_insn_name (old->u.insn.code_number)); 1399 message_with_line (old->u.insn.lineno, "previous definition of `%s'", 1400 get_insn_name (old->u.insn.code_number)); 1401 error_count++; 1402 } 1403} 1404 1405/* Merge two decision trees OLDH and ADDH, modifying OLDH destructively. */ 1406 1407static void 1408merge_trees (oldh, addh) 1409 struct decision_head *oldh, *addh; 1410{ 1411 struct decision *next, *add; 1412 1413 if (addh->first == 0) 1414 return; 1415 if (oldh->first == 0) 1416 { 1417 *oldh = *addh; 1418 return; 1419 } 1420 1421 /* Trying to merge bits at different positions isn't possible. */ 1422 if (strcmp (oldh->first->position, addh->first->position)) 1423 abort (); 1424 1425 for (add = addh->first; add ; add = next) 1426 { 1427 struct decision *old, *insert_before = NULL; 1428 1429 next = add->next; 1430 1431 /* The semantics of pattern matching state that the tests are 1432 done in the order given in the MD file so that if an insn 1433 matches two patterns, the first one will be used. However, 1434 in practice, most, if not all, patterns are unambiguous so 1435 that their order is independent. In that case, we can merge 1436 identical tests and group all similar modes and codes together. 1437 1438 Scan starting from the end of OLDH until we reach a point 1439 where we reach the head of the list or where we pass a 1440 pattern that could also be true if NEW is true. If we find 1441 an identical pattern, we can merge them. Also, record the 1442 last node that tests the same code and mode and the last one 1443 that tests just the same mode. 1444 1445 If we have no match, place NEW after the closest match we found. */ 1446 1447 for (old = oldh->last; old; old = old->prev) 1448 { 1449 if (nodes_identical (old, add)) 1450 { 1451 merge_accept_insn (old, add); 1452 merge_trees (&old->success, &add->success); 1453 goto merged_nodes; 1454 } 1455 1456 if (maybe_both_true (old, add, 0)) 1457 break; 1458 1459 /* Insert the nodes in DT test type order, which is roughly 1460 how expensive/important the test is. Given that the tests 1461 are also ordered within the list, examining the first is 1462 sufficient. */ 1463 if ((int) add->tests->type < (int) old->tests->type) 1464 insert_before = old; 1465 } 1466 1467 if (insert_before == NULL) 1468 { 1469 add->next = NULL; 1470 add->prev = oldh->last; 1471 oldh->last->next = add; 1472 oldh->last = add; 1473 } 1474 else 1475 { 1476 if ((add->prev = insert_before->prev) != NULL) 1477 add->prev->next = add; 1478 else 1479 oldh->first = add; 1480 add->next = insert_before; 1481 insert_before->prev = add; 1482 } 1483 1484 merged_nodes:; 1485 } 1486} 1487 1488/* Walk the tree looking for sub-nodes that perform common tests. 1489 Factor out the common test into a new node. This enables us 1490 (depending on the test type) to emit switch statements later. */ 1491 1492static void 1493factor_tests (head) 1494 struct decision_head *head; 1495{ 1496 struct decision *first, *next; 1497 1498 for (first = head->first; first && first->next; first = next) 1499 { 1500 enum decision_type type; 1501 struct decision *new, *old_last; 1502 1503 type = first->tests->type; 1504 next = first->next; 1505 1506 /* Want at least two compatible sequential nodes. */ 1507 if (next->tests->type != type) 1508 continue; 1509 1510 /* Don't want all node types, just those we can turn into 1511 switch statements. */ 1512 if (type != DT_mode 1513 && type != DT_code 1514 && type != DT_veclen 1515 && type != DT_elt_zero_int 1516 && type != DT_elt_one_int 1517 && type != DT_elt_zero_wide_safe) 1518 continue; 1519 1520 /* If we'd been performing more than one test, create a new node 1521 below our first test. */ 1522 if (first->tests->next != NULL) 1523 { 1524 new = new_decision (first->position, &first->success); 1525 new->tests = first->tests->next; 1526 first->tests->next = NULL; 1527 } 1528 1529 /* Crop the node tree off after our first test. */ 1530 first->next = NULL; 1531 old_last = head->last; 1532 head->last = first; 1533 1534 /* For each compatible test, adjust to perform only one test in 1535 the top level node, then merge the node back into the tree. */ 1536 do 1537 { 1538 struct decision_head h; 1539 1540 if (next->tests->next != NULL) 1541 { 1542 new = new_decision (next->position, &next->success); 1543 new->tests = next->tests->next; 1544 next->tests->next = NULL; 1545 } 1546 new = next; 1547 next = next->next; 1548 new->next = NULL; 1549 h.first = h.last = new; 1550 1551 merge_trees (head, &h); 1552 } 1553 while (next && next->tests->type == type); 1554 1555 /* After we run out of compatible tests, graft the remaining nodes 1556 back onto the tree. */ 1557 if (next) 1558 { 1559 next->prev = head->last; 1560 head->last->next = next; 1561 head->last = old_last; 1562 } 1563 } 1564 1565 /* Recurse. */ 1566 for (first = head->first; first; first = first->next) 1567 factor_tests (&first->success); 1568} 1569 1570/* After factoring, try to simplify the tests on any one node. 1571 Tests that are useful for switch statements are recognizable 1572 by having only a single test on a node -- we'll be manipulating 1573 nodes with multiple tests: 1574 1575 If we have mode tests or code tests that are redundant with 1576 predicates, remove them. */ 1577 1578static void 1579simplify_tests (head) 1580 struct decision_head *head; 1581{ 1582 struct decision *tree; 1583 1584 for (tree = head->first; tree; tree = tree->next) 1585 { 1586 struct decision_test *a, *b; 1587 1588 a = tree->tests; 1589 b = a->next; 1590 if (b == NULL) 1591 continue; 1592 1593 /* Find a predicate node. */ 1594 while (b && b->type != DT_pred) 1595 b = b->next; 1596 if (b) 1597 { 1598 /* Due to how these tests are constructed, we don't even need 1599 to check that the mode and code are compatible -- they were 1600 generated from the predicate in the first place. */ 1601 while (a->type == DT_mode || a->type == DT_code) 1602 a = a->next; 1603 tree->tests = a; 1604 } 1605 } 1606 1607 /* Recurse. */ 1608 for (tree = head->first; tree; tree = tree->next) 1609 simplify_tests (&tree->success); 1610} 1611 1612/* Count the number of subnodes of HEAD. If the number is high enough, 1613 make the first node in HEAD start a separate subroutine in the C code 1614 that is generated. */ 1615 1616static int 1617break_out_subroutines (head, initial) 1618 struct decision_head *head; 1619 int initial; 1620{ 1621 int size = 0; 1622 struct decision *sub; 1623 1624 for (sub = head->first; sub; sub = sub->next) 1625 size += 1 + break_out_subroutines (&sub->success, 0); 1626 1627 if (size > SUBROUTINE_THRESHOLD && ! initial) 1628 { 1629 head->first->subroutine_number = ++next_subroutine_number; 1630 size = 1; 1631 } 1632 return size; 1633} 1634 1635/* For each node p, find the next alternative that might be true 1636 when p is true. */ 1637 1638static void 1639find_afterward (head, real_afterward) 1640 struct decision_head *head; 1641 struct decision *real_afterward; 1642{ 1643 struct decision *p, *q, *afterward; 1644 1645 /* We can't propagate alternatives across subroutine boundaries. 1646 This is not incorrect, merely a minor optimization loss. */ 1647 1648 p = head->first; 1649 afterward = (p->subroutine_number > 0 ? NULL : real_afterward); 1650 1651 for ( ; p ; p = p->next) 1652 { 1653 /* Find the next node that might be true if this one fails. */ 1654 for (q = p->next; q ; q = q->next) 1655 if (maybe_both_true (p, q, 1)) 1656 break; 1657 1658 /* If we reached the end of the list without finding one, 1659 use the incoming afterward position. */ 1660 if (!q) 1661 q = afterward; 1662 p->afterward = q; 1663 if (q) 1664 q->need_label = 1; 1665 } 1666 1667 /* Recurse. */ 1668 for (p = head->first; p ; p = p->next) 1669 if (p->success.first) 1670 find_afterward (&p->success, p->afterward); 1671 1672 /* When we are generating a subroutine, record the real afterward 1673 position in the first node where write_tree can find it, and we 1674 can do the right thing at the subroutine call site. */ 1675 p = head->first; 1676 if (p->subroutine_number > 0) 1677 p->afterward = real_afterward; 1678} 1679 1680/* Assuming that the state of argument is denoted by OLDPOS, take whatever 1681 actions are necessary to move to NEWPOS. If we fail to move to the 1682 new state, branch to node AFTERWARD if nonzero, otherwise return. 1683 1684 Failure to move to the new state can only occur if we are trying to 1685 match multiple insns and we try to step past the end of the stream. */ 1686 1687static void 1688change_state (oldpos, newpos, afterward, indent) 1689 const char *oldpos; 1690 const char *newpos; 1691 struct decision *afterward; 1692 const char *indent; 1693{ 1694 int odepth = strlen (oldpos); 1695 int ndepth = strlen (newpos); 1696 int depth; 1697 int old_has_insn, new_has_insn; 1698 1699 /* Pop up as many levels as necessary. */ 1700 for (depth = odepth; strncmp (oldpos, newpos, depth) != 0; --depth) 1701 continue; 1702 1703 /* Hunt for the last [A-Z] in both strings. */ 1704 for (old_has_insn = odepth - 1; old_has_insn >= 0; --old_has_insn) 1705 if (ISUPPER (oldpos[old_has_insn])) 1706 break; 1707 for (new_has_insn = ndepth - 1; new_has_insn >= 0; --new_has_insn) 1708 if (ISUPPER (newpos[new_has_insn])) 1709 break; 1710 1711 /* Go down to desired level. */ 1712 while (depth < ndepth) 1713 { 1714 /* It's a different insn from the first one. */ 1715 if (ISUPPER (newpos[depth])) 1716 { 1717 /* We can only fail if we're moving down the tree. */ 1718 if (old_has_insn >= 0 && oldpos[old_has_insn] >= newpos[depth]) 1719 { 1720 printf ("%stem = peep2_next_insn (%d);\n", 1721 indent, newpos[depth] - 'A'); 1722 } 1723 else 1724 { 1725 printf ("%stem = peep2_next_insn (%d);\n", 1726 indent, newpos[depth] - 'A'); 1727 printf ("%sif (tem == NULL_RTX)\n", indent); 1728 if (afterward) 1729 printf ("%s goto L%d;\n", indent, afterward->number); 1730 else 1731 printf ("%s goto ret0;\n", indent); 1732 } 1733 printf ("%sx%d = PATTERN (tem);\n", indent, depth + 1); 1734 } 1735 else if (ISLOWER (newpos[depth])) 1736 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n", 1737 indent, depth + 1, depth, newpos[depth] - 'a'); 1738 else 1739 printf ("%sx%d = XEXP (x%d, %c);\n", 1740 indent, depth + 1, depth, newpos[depth]); 1741 ++depth; 1742 } 1743} 1744 1745/* Print the enumerator constant for CODE -- the upcase version of 1746 the name. */ 1747 1748static void 1749print_code (code) 1750 enum rtx_code code; 1751{ 1752 const char *p; 1753 for (p = GET_RTX_NAME (code); *p; p++) 1754 putchar (TOUPPER (*p)); 1755} 1756 1757/* Emit code to cross an afterward link -- change state and branch. */ 1758 1759static void 1760write_afterward (start, afterward, indent) 1761 struct decision *start; 1762 struct decision *afterward; 1763 const char *indent; 1764{ 1765 if (!afterward || start->subroutine_number > 0) 1766 printf("%sgoto ret0;\n", indent); 1767 else 1768 { 1769 change_state (start->position, afterward->position, NULL, indent); 1770 printf ("%sgoto L%d;\n", indent, afterward->number); 1771 } 1772} 1773 1774/* Emit a switch statement, if possible, for an initial sequence of 1775 nodes at START. Return the first node yet untested. */ 1776 1777static struct decision * 1778write_switch (start, depth) 1779 struct decision *start; 1780 int depth; 1781{ 1782 struct decision *p = start; 1783 enum decision_type type = p->tests->type; 1784 struct decision *needs_label = NULL; 1785 1786 /* If we have two or more nodes in sequence that test the same one 1787 thing, we may be able to use a switch statement. */ 1788 1789 if (!p->next 1790 || p->tests->next 1791 || p->next->tests->type != type 1792 || p->next->tests->next 1793 || nodes_identical_1 (p->tests, p->next->tests)) 1794 return p; 1795 1796 /* DT_code is special in that we can do interesting things with 1797 known predicates at the same time. */ 1798 if (type == DT_code) 1799 { 1800 char codemap[NUM_RTX_CODE]; 1801 struct decision *ret; 1802 RTX_CODE code; 1803 1804 memset (codemap, 0, sizeof(codemap)); 1805 1806 printf (" switch (GET_CODE (x%d))\n {\n", depth); 1807 code = p->tests->u.code; 1808 do 1809 { 1810 if (p != start && p->need_label && needs_label == NULL) 1811 needs_label = p; 1812 1813 printf (" case "); 1814 print_code (code); 1815 printf (":\n goto L%d;\n", p->success.first->number); 1816 p->success.first->need_label = 1; 1817 1818 codemap[code] = 1; 1819 p = p->next; 1820 } 1821 while (p 1822 && ! p->tests->next 1823 && p->tests->type == DT_code 1824 && ! codemap[code = p->tests->u.code]); 1825 1826 /* If P is testing a predicate that we know about and we haven't 1827 seen any of the codes that are valid for the predicate, we can 1828 write a series of "case" statement, one for each possible code. 1829 Since we are already in a switch, these redundant tests are very 1830 cheap and will reduce the number of predicates called. */ 1831 1832 /* Note that while we write out cases for these predicates here, 1833 we don't actually write the test here, as it gets kinda messy. 1834 It is trivial to leave this to later by telling our caller that 1835 we only processed the CODE tests. */ 1836 if (needs_label != NULL) 1837 ret = needs_label; 1838 else 1839 ret = p; 1840 1841 while (p && p->tests->type == DT_pred 1842 && p->tests->u.pred.index >= 0) 1843 { 1844 const RTX_CODE *c; 1845 1846 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c) 1847 if (codemap[(int) *c] != 0) 1848 goto pred_done; 1849 1850 for (c = &preds[p->tests->u.pred.index].codes[0]; *c ; ++c) 1851 { 1852 printf (" case "); 1853 print_code (*c); 1854 printf (":\n"); 1855 codemap[(int) *c] = 1; 1856 } 1857 1858 printf (" goto L%d;\n", p->number); 1859 p->need_label = 1; 1860 p = p->next; 1861 } 1862 1863 pred_done: 1864 /* Make the default case skip the predicates we managed to match. */ 1865 1866 printf (" default:\n"); 1867 if (p != ret) 1868 { 1869 if (p) 1870 { 1871 printf (" goto L%d;\n", p->number); 1872 p->need_label = 1; 1873 } 1874 else 1875 write_afterward (start, start->afterward, " "); 1876 } 1877 else 1878 printf (" break;\n"); 1879 printf (" }\n"); 1880 1881 return ret; 1882 } 1883 else if (type == DT_mode 1884 || type == DT_veclen 1885 || type == DT_elt_zero_int 1886 || type == DT_elt_one_int 1887 || type == DT_elt_zero_wide_safe) 1888 { 1889 const char *indent = ""; 1890 1891 /* We cast switch parameter to integer, so we must ensure that the value 1892 fits. */ 1893 if (type == DT_elt_zero_wide_safe) 1894 { 1895 indent = " "; 1896 printf(" if ((int) XWINT (x%d, 0) == XWINT (x%d, 0))\n", depth, depth); 1897 } 1898 printf ("%s switch (", indent); 1899 switch (type) 1900 { 1901 case DT_mode: 1902 printf ("GET_MODE (x%d)", depth); 1903 break; 1904 case DT_veclen: 1905 printf ("XVECLEN (x%d, 0)", depth); 1906 break; 1907 case DT_elt_zero_int: 1908 printf ("XINT (x%d, 0)", depth); 1909 break; 1910 case DT_elt_one_int: 1911 printf ("XINT (x%d, 1)", depth); 1912 break; 1913 case DT_elt_zero_wide_safe: 1914 /* Convert result of XWINT to int for portability since some C 1915 compilers won't do it and some will. */ 1916 printf ("(int) XWINT (x%d, 0)", depth); 1917 break; 1918 default: 1919 abort (); 1920 } 1921 printf (")\n%s {\n", indent); 1922 1923 do 1924 { 1925 /* Merge trees will not unify identical nodes if their 1926 sub-nodes are at different levels. Thus we must check 1927 for duplicate cases. */ 1928 struct decision *q; 1929 for (q = start; q != p; q = q->next) 1930 if (nodes_identical_1 (p->tests, q->tests)) 1931 goto case_done; 1932 1933 if (p != start && p->need_label && needs_label == NULL) 1934 needs_label = p; 1935 1936 printf ("%s case ", indent); 1937 switch (type) 1938 { 1939 case DT_mode: 1940 printf ("%smode", GET_MODE_NAME (p->tests->u.mode)); 1941 break; 1942 case DT_veclen: 1943 printf ("%d", p->tests->u.veclen); 1944 break; 1945 case DT_elt_zero_int: 1946 case DT_elt_one_int: 1947 case DT_elt_zero_wide: 1948 case DT_elt_zero_wide_safe: 1949 printf (HOST_WIDE_INT_PRINT_DEC_C, p->tests->u.intval); 1950 break; 1951 default: 1952 abort (); 1953 } 1954 printf (":\n%s goto L%d;\n", indent, p->success.first->number); 1955 p->success.first->need_label = 1; 1956 1957 p = p->next; 1958 } 1959 while (p && p->tests->type == type && !p->tests->next); 1960 1961 case_done: 1962 printf ("%s default:\n%s break;\n%s }\n", 1963 indent, indent, indent); 1964 1965 return needs_label != NULL ? needs_label : p; 1966 } 1967 else 1968 { 1969 /* None of the other tests are ameanable. */ 1970 return p; 1971 } 1972} 1973 1974/* Emit code for one test. */ 1975 1976static void 1977write_cond (p, depth, subroutine_type) 1978 struct decision_test *p; 1979 int depth; 1980 enum routine_type subroutine_type; 1981{ 1982 switch (p->type) 1983 { 1984 case DT_mode: 1985 printf ("GET_MODE (x%d) == %smode", depth, GET_MODE_NAME (p->u.mode)); 1986 break; 1987 1988 case DT_code: 1989 printf ("GET_CODE (x%d) == ", depth); 1990 print_code (p->u.code); 1991 break; 1992 1993 case DT_veclen: 1994 printf ("XVECLEN (x%d, 0) == %d", depth, p->u.veclen); 1995 break; 1996 1997 case DT_elt_zero_int: 1998 printf ("XINT (x%d, 0) == %d", depth, (int) p->u.intval); 1999 break; 2000 2001 case DT_elt_one_int: 2002 printf ("XINT (x%d, 1) == %d", depth, (int) p->u.intval); 2003 break; 2004 2005 case DT_elt_zero_wide: 2006 case DT_elt_zero_wide_safe: 2007 printf ("XWINT (x%d, 0) == ", depth); 2008 printf (HOST_WIDE_INT_PRINT_DEC_C, p->u.intval); 2009 break; 2010 2011 case DT_veclen_ge: 2012 printf ("XVECLEN (x%d, 0) >= %d", depth, p->u.veclen); 2013 break; 2014 2015 case DT_dup: 2016 printf ("rtx_equal_p (x%d, operands[%d])", depth, p->u.dup); 2017 break; 2018 2019 case DT_pred: 2020 printf ("%s (x%d, %smode)", p->u.pred.name, depth, 2021 GET_MODE_NAME (p->u.pred.mode)); 2022 break; 2023 2024 case DT_c_test: 2025 printf ("(%s)", p->u.c_test); 2026 break; 2027 2028 case DT_accept_insn: 2029 switch (subroutine_type) 2030 { 2031 case RECOG: 2032 if (p->u.insn.num_clobbers_to_add == 0) 2033 abort (); 2034 printf ("pnum_clobbers != NULL"); 2035 break; 2036 2037 default: 2038 abort (); 2039 } 2040 break; 2041 2042 default: 2043 abort (); 2044 } 2045} 2046 2047/* Emit code for one action. The previous tests have succeeded; 2048 TEST is the last of the chain. In the normal case we simply 2049 perform a state change. For the `accept' tests we must do more work. */ 2050 2051static void 2052write_action (p, test, depth, uncond, success, subroutine_type) 2053 struct decision *p; 2054 struct decision_test *test; 2055 int depth, uncond; 2056 struct decision *success; 2057 enum routine_type subroutine_type; 2058{ 2059 const char *indent; 2060 int want_close = 0; 2061 2062 if (uncond) 2063 indent = " "; 2064 else if (test->type == DT_accept_op || test->type == DT_accept_insn) 2065 { 2066 fputs (" {\n", stdout); 2067 indent = " "; 2068 want_close = 1; 2069 } 2070 else 2071 indent = " "; 2072 2073 if (test->type == DT_accept_op) 2074 { 2075 printf("%soperands[%d] = x%d;\n", indent, test->u.opno, depth); 2076 2077 /* Only allow DT_accept_insn to follow. */ 2078 if (test->next) 2079 { 2080 test = test->next; 2081 if (test->type != DT_accept_insn) 2082 abort (); 2083 } 2084 } 2085 2086 /* Sanity check that we're now at the end of the list of tests. */ 2087 if (test->next) 2088 abort (); 2089 2090 if (test->type == DT_accept_insn) 2091 { 2092 switch (subroutine_type) 2093 { 2094 case RECOG: 2095 if (test->u.insn.num_clobbers_to_add != 0) 2096 printf ("%s*pnum_clobbers = %d;\n", 2097 indent, test->u.insn.num_clobbers_to_add); 2098 printf ("%sreturn %d;\n", indent, test->u.insn.code_number); 2099 break; 2100 2101 case SPLIT: 2102 printf ("%sreturn gen_split_%d (operands);\n", 2103 indent, test->u.insn.code_number); 2104 break; 2105 2106 case PEEPHOLE2: 2107 { 2108 int match_len = 0, i; 2109 2110 for (i = strlen (p->position) - 1; i >= 0; --i) 2111 if (ISUPPER (p->position[i])) 2112 { 2113 match_len = p->position[i] - 'A'; 2114 break; 2115 } 2116 printf ("%s*_pmatch_len = %d;\n", indent, match_len); 2117 printf ("%stem = gen_peephole2_%d (insn, operands);\n", 2118 indent, test->u.insn.code_number); 2119 printf ("%sif (tem != 0)\n%s return tem;\n", indent, indent); 2120 } 2121 break; 2122 2123 default: 2124 abort (); 2125 } 2126 } 2127 else 2128 { 2129 printf("%sgoto L%d;\n", indent, success->number); 2130 success->need_label = 1; 2131 } 2132 2133 if (want_close) 2134 fputs (" }\n", stdout); 2135} 2136 2137/* Return 1 if the test is always true and has no fallthru path. Return -1 2138 if the test does have a fallthru path, but requires that the condition be 2139 terminated. Otherwise return 0 for a normal test. */ 2140/* ??? is_unconditional is a stupid name for a tri-state function. */ 2141 2142static int 2143is_unconditional (t, subroutine_type) 2144 struct decision_test *t; 2145 enum routine_type subroutine_type; 2146{ 2147 if (t->type == DT_accept_op) 2148 return 1; 2149 2150 if (t->type == DT_accept_insn) 2151 { 2152 switch (subroutine_type) 2153 { 2154 case RECOG: 2155 return (t->u.insn.num_clobbers_to_add == 0); 2156 case SPLIT: 2157 return 1; 2158 case PEEPHOLE2: 2159 return -1; 2160 default: 2161 abort (); 2162 } 2163 } 2164 2165 return 0; 2166} 2167 2168/* Emit code for one node -- the conditional and the accompanying action. 2169 Return true if there is no fallthru path. */ 2170 2171static int 2172write_node (p, depth, subroutine_type) 2173 struct decision *p; 2174 int depth; 2175 enum routine_type subroutine_type; 2176{ 2177 struct decision_test *test, *last_test; 2178 int uncond; 2179 2180 last_test = test = p->tests; 2181 uncond = is_unconditional (test, subroutine_type); 2182 if (uncond == 0) 2183 { 2184 printf (" if ("); 2185 write_cond (test, depth, subroutine_type); 2186 2187 while ((test = test->next) != NULL) 2188 { 2189 int uncond2; 2190 2191 last_test = test; 2192 uncond2 = is_unconditional (test, subroutine_type); 2193 if (uncond2 != 0) 2194 break; 2195 2196 printf ("\n && "); 2197 write_cond (test, depth, subroutine_type); 2198 } 2199 2200 printf (")\n"); 2201 } 2202 2203 write_action (p, last_test, depth, uncond, p->success.first, subroutine_type); 2204 2205 return uncond > 0; 2206} 2207 2208/* Emit code for all of the sibling nodes of HEAD. */ 2209 2210static void 2211write_tree_1 (head, depth, subroutine_type) 2212 struct decision_head *head; 2213 int depth; 2214 enum routine_type subroutine_type; 2215{ 2216 struct decision *p, *next; 2217 int uncond = 0; 2218 2219 for (p = head->first; p ; p = next) 2220 { 2221 /* The label for the first element was printed in write_tree. */ 2222 if (p != head->first && p->need_label) 2223 OUTPUT_LABEL (" ", p->number); 2224 2225 /* Attempt to write a switch statement for a whole sequence. */ 2226 next = write_switch (p, depth); 2227 if (p != next) 2228 uncond = 0; 2229 else 2230 { 2231 /* Failed -- fall back and write one node. */ 2232 uncond = write_node (p, depth, subroutine_type); 2233 next = p->next; 2234 } 2235 } 2236 2237 /* Finished with this chain. Close a fallthru path by branching 2238 to the afterward node. */ 2239 if (! uncond) 2240 write_afterward (head->last, head->last->afterward, " "); 2241} 2242 2243/* Write out the decision tree starting at HEAD. PREVPOS is the 2244 position at the node that branched to this node. */ 2245 2246static void 2247write_tree (head, prevpos, type, initial) 2248 struct decision_head *head; 2249 const char *prevpos; 2250 enum routine_type type; 2251 int initial; 2252{ 2253 struct decision *p = head->first; 2254 2255 putchar ('\n'); 2256 if (p->need_label) 2257 OUTPUT_LABEL (" ", p->number); 2258 2259 if (! initial && p->subroutine_number > 0) 2260 { 2261 static const char * const name_prefix[] = { 2262 "recog", "split", "peephole2" 2263 }; 2264 2265 static const char * const call_suffix[] = { 2266 ", pnum_clobbers", "", ", _pmatch_len" 2267 }; 2268 2269 /* This node has been broken out into a separate subroutine. 2270 Call it, test the result, and branch accordingly. */ 2271 2272 if (p->afterward) 2273 { 2274 printf (" tem = %s_%d (x0, insn%s);\n", 2275 name_prefix[type], p->subroutine_number, call_suffix[type]); 2276 if (IS_SPLIT (type)) 2277 printf (" if (tem != 0)\n return tem;\n"); 2278 else 2279 printf (" if (tem >= 0)\n return tem;\n"); 2280 2281 change_state (p->position, p->afterward->position, NULL, " "); 2282 printf (" goto L%d;\n", p->afterward->number); 2283 } 2284 else 2285 { 2286 printf (" return %s_%d (x0, insn%s);\n", 2287 name_prefix[type], p->subroutine_number, call_suffix[type]); 2288 } 2289 } 2290 else 2291 { 2292 int depth = strlen (p->position); 2293 2294 change_state (prevpos, p->position, head->last->afterward, " "); 2295 write_tree_1 (head, depth, type); 2296 2297 for (p = head->first; p; p = p->next) 2298 if (p->success.first) 2299 write_tree (&p->success, p->position, type, 0); 2300 } 2301} 2302 2303/* Write out a subroutine of type TYPE to do comparisons starting at 2304 node TREE. */ 2305 2306static void 2307write_subroutine (head, type) 2308 struct decision_head *head; 2309 enum routine_type type; 2310{ 2311 int subfunction = head->first ? head->first->subroutine_number : 0; 2312 const char *s_or_e; 2313 char extension[32]; 2314 int i; 2315 2316 s_or_e = subfunction ? "static " : ""; 2317 2318 if (subfunction) 2319 sprintf (extension, "_%d", subfunction); 2320 else if (type == RECOG) 2321 extension[0] = '\0'; 2322 else 2323 strcpy (extension, "_insns"); 2324 2325 switch (type) 2326 { 2327 case RECOG: 2328 printf ("%sint recog%s PARAMS ((rtx, rtx, int *));\n", s_or_e, extension); 2329 printf ("%sint\n\ 2330recog%s (x0, insn, pnum_clobbers)\n\ 2331 rtx x0 ATTRIBUTE_UNUSED;\n\ 2332 rtx insn ATTRIBUTE_UNUSED;\n\ 2333 int *pnum_clobbers ATTRIBUTE_UNUSED;\n", s_or_e, extension); 2334 break; 2335 case SPLIT: 2336 printf ("%srtx split%s PARAMS ((rtx, rtx));\n", s_or_e, extension); 2337 printf ("%srtx\n\ 2338split%s (x0, insn)\n\ 2339 rtx x0 ATTRIBUTE_UNUSED;\n\ 2340 rtx insn ATTRIBUTE_UNUSED;\n", s_or_e, extension); 2341 break; 2342 case PEEPHOLE2: 2343 printf ("%srtx peephole2%s PARAMS ((rtx, rtx, int *));\n", 2344 s_or_e, extension); 2345 printf ("%srtx\n\ 2346peephole2%s (x0, insn, _pmatch_len)\n\ 2347 rtx x0 ATTRIBUTE_UNUSED;\n\ 2348 rtx insn ATTRIBUTE_UNUSED;\n\ 2349 int *_pmatch_len ATTRIBUTE_UNUSED;\n", s_or_e, extension); 2350 break; 2351 } 2352 2353 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED = &recog_data.operand[0];\n"); 2354 for (i = 1; i <= max_depth; i++) 2355 printf (" rtx x%d ATTRIBUTE_UNUSED;\n", i); 2356 2357 printf (" %s tem ATTRIBUTE_UNUSED;\n", IS_SPLIT (type) ? "rtx" : "int"); 2358 2359 if (!subfunction) 2360 printf (" recog_data.insn = NULL_RTX;\n"); 2361 2362 if (head->first) 2363 write_tree (head, "", type, 1); 2364 else 2365 printf (" goto ret0;\n"); 2366 2367 printf (" ret0:\n return %d;\n}\n\n", IS_SPLIT (type) ? 0 : -1); 2368} 2369 2370/* In break_out_subroutines, we discovered the boundaries for the 2371 subroutines, but did not write them out. Do so now. */ 2372 2373static void 2374write_subroutines (head, type) 2375 struct decision_head *head; 2376 enum routine_type type; 2377{ 2378 struct decision *p; 2379 2380 for (p = head->first; p ; p = p->next) 2381 if (p->success.first) 2382 write_subroutines (&p->success, type); 2383 2384 if (head->first->subroutine_number > 0) 2385 write_subroutine (head, type); 2386} 2387 2388/* Begin the output file. */ 2389 2390static void 2391write_header () 2392{ 2393 puts ("\ 2394/* Generated automatically by the program `genrecog' from the target\n\ 2395 machine description file. */\n\ 2396\n\ 2397#include \"config.h\"\n\ 2398#include \"system.h\"\n\ 2399#include \"rtl.h\"\n\ 2400#include \"tm_p.h\"\n\ 2401#include \"function.h\"\n\ 2402#include \"insn-config.h\"\n\ 2403#include \"recog.h\"\n\ 2404#include \"real.h\"\n\ 2405#include \"output.h\"\n\ 2406#include \"flags.h\"\n\ 2407#include \"hard-reg-set.h\"\n\ 2408#include \"resource.h\"\n\ 2409#include \"toplev.h\"\n\ 2410#include \"reload.h\"\n\ 2411\n"); 2412 2413 puts ("\n\ 2414/* `recog' contains a decision tree that recognizes whether the rtx\n\ 2415 X0 is a valid instruction.\n\ 2416\n\ 2417 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\ 2418 returns a nonnegative number which is the insn code number for the\n\ 2419 pattern that matched. This is the same as the order in the machine\n\ 2420 description of the entry that matched. This number can be used as an\n\ 2421 index into `insn_data' and other tables.\n"); 2422 puts ("\ 2423 The third argument to recog is an optional pointer to an int. If\n\ 2424 present, recog will accept a pattern if it matches except for missing\n\ 2425 CLOBBER expressions at the end. In that case, the value pointed to by\n\ 2426 the optional pointer will be set to the number of CLOBBERs that need\n\ 2427 to be added (it should be initialized to zero by the caller). If it"); 2428 puts ("\ 2429 is set nonzero, the caller should allocate a PARALLEL of the\n\ 2430 appropriate size, copy the initial entries, and call add_clobbers\n\ 2431 (found in insn-emit.c) to fill in the CLOBBERs.\n\ 2432"); 2433 2434 puts ("\n\ 2435 The function split_insns returns 0 if the rtl could not\n\ 2436 be split or the split rtl as an INSN list if it can be.\n\ 2437\n\ 2438 The function peephole2_insns returns 0 if the rtl could not\n\ 2439 be matched. If there was a match, the new rtl is returned in an INSN list,\n\ 2440 and LAST_INSN will point to the last recognized insn in the old sequence.\n\ 2441*/\n\n"); 2442} 2443 2444 2445/* Construct and return a sequence of decisions 2446 that will recognize INSN. 2447 2448 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */ 2449 2450static struct decision_head 2451make_insn_sequence (insn, type) 2452 rtx insn; 2453 enum routine_type type; 2454{ 2455 rtx x; 2456 const char *c_test = XSTR (insn, type == RECOG ? 2 : 1); 2457 int truth = maybe_eval_c_test (c_test); 2458 struct decision *last; 2459 struct decision_test *test, **place; 2460 struct decision_head head; 2461 char c_test_pos[2]; 2462 2463 /* We should never see an insn whose C test is false at compile time. */ 2464 if (truth == 0) 2465 abort (); 2466 2467 record_insn_name (next_insn_code, (type == RECOG ? XSTR (insn, 0) : NULL)); 2468 2469 c_test_pos[0] = '\0'; 2470 if (type == PEEPHOLE2) 2471 { 2472 int i, j; 2473 2474 /* peephole2 gets special treatment: 2475 - X always gets an outer parallel even if it's only one entry 2476 - we remove all traces of outer-level match_scratch and match_dup 2477 expressions here. */ 2478 x = rtx_alloc (PARALLEL); 2479 PUT_MODE (x, VOIDmode); 2480 XVEC (x, 0) = rtvec_alloc (XVECLEN (insn, 0)); 2481 for (i = j = 0; i < XVECLEN (insn, 0); i++) 2482 { 2483 rtx tmp = XVECEXP (insn, 0, i); 2484 if (GET_CODE (tmp) != MATCH_SCRATCH && GET_CODE (tmp) != MATCH_DUP) 2485 { 2486 XVECEXP (x, 0, j) = tmp; 2487 j++; 2488 } 2489 } 2490 XVECLEN (x, 0) = j; 2491 2492 c_test_pos[0] = 'A' + j - 1; 2493 c_test_pos[1] = '\0'; 2494 } 2495 else if (XVECLEN (insn, type == RECOG) == 1) 2496 x = XVECEXP (insn, type == RECOG, 0); 2497 else 2498 { 2499 x = rtx_alloc (PARALLEL); 2500 XVEC (x, 0) = XVEC (insn, type == RECOG); 2501 PUT_MODE (x, VOIDmode); 2502 } 2503 2504 validate_pattern (x, insn, NULL_RTX, 0); 2505 2506 memset(&head, 0, sizeof(head)); 2507 last = add_to_sequence (x, &head, "", type, 1); 2508 2509 /* Find the end of the test chain on the last node. */ 2510 for (test = last->tests; test->next; test = test->next) 2511 continue; 2512 place = &test->next; 2513 2514 /* Skip the C test if it's known to be true at compile time. */ 2515 if (truth == -1) 2516 { 2517 /* Need a new node if we have another test to add. */ 2518 if (test->type == DT_accept_op) 2519 { 2520 last = new_decision (c_test_pos, &last->success); 2521 place = &last->tests; 2522 } 2523 test = new_decision_test (DT_c_test, &place); 2524 test->u.c_test = c_test; 2525 } 2526 2527 test = new_decision_test (DT_accept_insn, &place); 2528 test->u.insn.code_number = next_insn_code; 2529 test->u.insn.lineno = pattern_lineno; 2530 test->u.insn.num_clobbers_to_add = 0; 2531 2532 switch (type) 2533 { 2534 case RECOG: 2535 /* If this is an DEFINE_INSN and X is a PARALLEL, see if it ends 2536 with a group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. 2537 If so, set up to recognize the pattern without these CLOBBERs. */ 2538 2539 if (GET_CODE (x) == PARALLEL) 2540 { 2541 int i; 2542 2543 /* Find the last non-clobber in the parallel. */ 2544 for (i = XVECLEN (x, 0); i > 0; i--) 2545 { 2546 rtx y = XVECEXP (x, 0, i - 1); 2547 if (GET_CODE (y) != CLOBBER 2548 || (GET_CODE (XEXP (y, 0)) != REG 2549 && GET_CODE (XEXP (y, 0)) != MATCH_SCRATCH)) 2550 break; 2551 } 2552 2553 if (i != XVECLEN (x, 0)) 2554 { 2555 rtx new; 2556 struct decision_head clobber_head; 2557 2558 /* Build a similar insn without the clobbers. */ 2559 if (i == 1) 2560 new = XVECEXP (x, 0, 0); 2561 else 2562 { 2563 int j; 2564 2565 new = rtx_alloc (PARALLEL); 2566 XVEC (new, 0) = rtvec_alloc (i); 2567 for (j = i - 1; j >= 0; j--) 2568 XVECEXP (new, 0, j) = XVECEXP (x, 0, j); 2569 } 2570 2571 /* Recognize it. */ 2572 memset (&clobber_head, 0, sizeof(clobber_head)); 2573 last = add_to_sequence (new, &clobber_head, "", type, 1); 2574 2575 /* Find the end of the test chain on the last node. */ 2576 for (test = last->tests; test->next; test = test->next) 2577 continue; 2578 2579 /* We definitely have a new test to add -- create a new 2580 node if needed. */ 2581 place = &test->next; 2582 if (test->type == DT_accept_op) 2583 { 2584 last = new_decision ("", &last->success); 2585 place = &last->tests; 2586 } 2587 2588 /* Skip the C test if it's known to be true at compile 2589 time. */ 2590 if (truth == -1) 2591 { 2592 test = new_decision_test (DT_c_test, &place); 2593 test->u.c_test = c_test; 2594 } 2595 2596 test = new_decision_test (DT_accept_insn, &place); 2597 test->u.insn.code_number = next_insn_code; 2598 test->u.insn.lineno = pattern_lineno; 2599 test->u.insn.num_clobbers_to_add = XVECLEN (x, 0) - i; 2600 2601 merge_trees (&head, &clobber_head); 2602 } 2603 } 2604 break; 2605 2606 case SPLIT: 2607 /* Define the subroutine we will call below and emit in genemit. */ 2608 printf ("extern rtx gen_split_%d PARAMS ((rtx *));\n", next_insn_code); 2609 break; 2610 2611 case PEEPHOLE2: 2612 /* Define the subroutine we will call below and emit in genemit. */ 2613 printf ("extern rtx gen_peephole2_%d PARAMS ((rtx, rtx *));\n", 2614 next_insn_code); 2615 break; 2616 } 2617 2618 return head; 2619} 2620 2621static void 2622process_tree (head, subroutine_type) 2623 struct decision_head *head; 2624 enum routine_type subroutine_type; 2625{ 2626 if (head->first == NULL) 2627 { 2628 /* We can elide peephole2_insns, but not recog or split_insns. */ 2629 if (subroutine_type == PEEPHOLE2) 2630 return; 2631 } 2632 else 2633 { 2634 factor_tests (head); 2635 2636 next_subroutine_number = 0; 2637 break_out_subroutines (head, 1); 2638 find_afterward (head, NULL); 2639 2640 /* We run this after find_afterward, because find_afterward needs 2641 the redundant DT_mode tests on predicates to determine whether 2642 two tests can both be true or not. */ 2643 simplify_tests(head); 2644 2645 write_subroutines (head, subroutine_type); 2646 } 2647 2648 write_subroutine (head, subroutine_type); 2649} 2650 2651extern int main PARAMS ((int, char **)); 2652 2653int 2654main (argc, argv) 2655 int argc; 2656 char **argv; 2657{ 2658 rtx desc; 2659 struct decision_head recog_tree, split_tree, peephole2_tree, h; 2660 2661 progname = "genrecog"; 2662 2663 memset (&recog_tree, 0, sizeof recog_tree); 2664 memset (&split_tree, 0, sizeof split_tree); 2665 memset (&peephole2_tree, 0, sizeof peephole2_tree); 2666 2667 if (argc <= 1) 2668 fatal ("no input file name"); 2669 2670 if (init_md_reader_args (argc, argv) != SUCCESS_EXIT_CODE) 2671 return (FATAL_EXIT_CODE); 2672 2673 next_insn_code = 0; 2674 next_index = 0; 2675 2676 write_header (); 2677 2678 /* Read the machine description. */ 2679 2680 while (1) 2681 { 2682 desc = read_md_rtx (&pattern_lineno, &next_insn_code); 2683 if (desc == NULL) 2684 break; 2685 2686 if (GET_CODE (desc) == DEFINE_INSN) 2687 { 2688 h = make_insn_sequence (desc, RECOG); 2689 merge_trees (&recog_tree, &h); 2690 } 2691 else if (GET_CODE (desc) == DEFINE_SPLIT) 2692 { 2693 h = make_insn_sequence (desc, SPLIT); 2694 merge_trees (&split_tree, &h); 2695 } 2696 else if (GET_CODE (desc) == DEFINE_PEEPHOLE2) 2697 { 2698 h = make_insn_sequence (desc, PEEPHOLE2); 2699 merge_trees (&peephole2_tree, &h); 2700 } 2701 2702 next_index++; 2703 } 2704 2705 if (error_count) 2706 return FATAL_EXIT_CODE; 2707 2708 puts ("\n\n"); 2709 2710 process_tree (&recog_tree, RECOG); 2711 process_tree (&split_tree, SPLIT); 2712 process_tree (&peephole2_tree, PEEPHOLE2); 2713 2714 fflush (stdout); 2715 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE); 2716} 2717 2718/* Define this so we can link with print-rtl.o to get debug_rtx function. */ 2719const char * 2720get_insn_name (code) 2721 int code; 2722{ 2723 if (code < insn_name_ptr_size) 2724 return insn_name_ptr[code]; 2725 else 2726 return NULL; 2727} 2728 2729static void 2730record_insn_name (code, name) 2731 int code; 2732 const char *name; 2733{ 2734 static const char *last_real_name = "insn"; 2735 static int last_real_code = 0; 2736 char *new; 2737 2738 if (insn_name_ptr_size <= code) 2739 { 2740 int new_size; 2741 new_size = (insn_name_ptr_size ? insn_name_ptr_size * 2 : 512); 2742 insn_name_ptr = 2743 (char **) xrealloc (insn_name_ptr, sizeof(char *) * new_size); 2744 memset (insn_name_ptr + insn_name_ptr_size, 0, 2745 sizeof(char *) * (new_size - insn_name_ptr_size)); 2746 insn_name_ptr_size = new_size; 2747 } 2748 2749 if (!name || name[0] == '\0') 2750 { 2751 new = xmalloc (strlen (last_real_name) + 10); 2752 sprintf (new, "%s+%d", last_real_name, code - last_real_code); 2753 } 2754 else 2755 { 2756 last_real_name = new = xstrdup (name); 2757 last_real_code = code; 2758 } 2759 2760 insn_name_ptr[code] = new; 2761} 2762 2763static void 2764debug_decision_2 (test) 2765 struct decision_test *test; 2766{ 2767 switch (test->type) 2768 { 2769 case DT_mode: 2770 fprintf (stderr, "mode=%s", GET_MODE_NAME (test->u.mode)); 2771 break; 2772 case DT_code: 2773 fprintf (stderr, "code=%s", GET_RTX_NAME (test->u.code)); 2774 break; 2775 case DT_veclen: 2776 fprintf (stderr, "veclen=%d", test->u.veclen); 2777 break; 2778 case DT_elt_zero_int: 2779 fprintf (stderr, "elt0_i=%d", (int) test->u.intval); 2780 break; 2781 case DT_elt_one_int: 2782 fprintf (stderr, "elt1_i=%d", (int) test->u.intval); 2783 break; 2784 case DT_elt_zero_wide: 2785 fprintf (stderr, "elt0_w="); 2786 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval); 2787 break; 2788 case DT_elt_zero_wide_safe: 2789 fprintf (stderr, "elt0_ws="); 2790 fprintf (stderr, HOST_WIDE_INT_PRINT_DEC, test->u.intval); 2791 break; 2792 case DT_veclen_ge: 2793 fprintf (stderr, "veclen>=%d", test->u.veclen); 2794 break; 2795 case DT_dup: 2796 fprintf (stderr, "dup=%d", test->u.dup); 2797 break; 2798 case DT_pred: 2799 fprintf (stderr, "pred=(%s,%s)", 2800 test->u.pred.name, GET_MODE_NAME(test->u.pred.mode)); 2801 break; 2802 case DT_c_test: 2803 { 2804 char sub[16+4]; 2805 strncpy (sub, test->u.c_test, sizeof(sub)); 2806 memcpy (sub+16, "...", 4); 2807 fprintf (stderr, "c_test=\"%s\"", sub); 2808 } 2809 break; 2810 case DT_accept_op: 2811 fprintf (stderr, "A_op=%d", test->u.opno); 2812 break; 2813 case DT_accept_insn: 2814 fprintf (stderr, "A_insn=(%d,%d)", 2815 test->u.insn.code_number, test->u.insn.num_clobbers_to_add); 2816 break; 2817 2818 default: 2819 abort (); 2820 } 2821} 2822 2823static void 2824debug_decision_1 (d, indent) 2825 struct decision *d; 2826 int indent; 2827{ 2828 int i; 2829 struct decision_test *test; 2830 2831 if (d == NULL) 2832 { 2833 for (i = 0; i < indent; ++i) 2834 putc (' ', stderr); 2835 fputs ("(nil)\n", stderr); 2836 return; 2837 } 2838 2839 for (i = 0; i < indent; ++i) 2840 putc (' ', stderr); 2841 2842 putc ('{', stderr); 2843 test = d->tests; 2844 if (test) 2845 { 2846 debug_decision_2 (test); 2847 while ((test = test->next) != NULL) 2848 { 2849 fputs (" + ", stderr); 2850 debug_decision_2 (test); 2851 } 2852 } 2853 fprintf (stderr, "} %d n %d a %d\n", d->number, 2854 (d->next ? d->next->number : -1), 2855 (d->afterward ? d->afterward->number : -1)); 2856} 2857 2858static void 2859debug_decision_0 (d, indent, maxdepth) 2860 struct decision *d; 2861 int indent, maxdepth; 2862{ 2863 struct decision *n; 2864 int i; 2865 2866 if (maxdepth < 0) 2867 return; 2868 if (d == NULL) 2869 { 2870 for (i = 0; i < indent; ++i) 2871 putc (' ', stderr); 2872 fputs ("(nil)\n", stderr); 2873 return; 2874 } 2875 2876 debug_decision_1 (d, indent); 2877 for (n = d->success.first; n ; n = n->next) 2878 debug_decision_0 (n, indent + 2, maxdepth - 1); 2879} 2880 2881void 2882debug_decision (d) 2883 struct decision *d; 2884{ 2885 debug_decision_0 (d, 0, 1000000); 2886} 2887 2888void 2889debug_decision_list (d) 2890 struct decision *d; 2891{ 2892 while (d) 2893 { 2894 debug_decision_0 (d, 0, 0); 2895 d = d->next; 2896 } 2897} 2898