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