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