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