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