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