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