genrecog.c revision 50397
1/* Generate code from machine description to recognize rtl as insns. 2 Copyright (C) 1987, 88, 92, 93, 94, 95, 97, 98 Free Software Foundation, Inc. 3 4This file is part of GNU CC. 5 6GNU CC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 2, or (at your option) 9any later version. 10 11GNU CC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GNU CC; see the file COPYING. If not, write to 18the Free Software Foundation, 59 Temple Place - Suite 330, 19Boston, MA 02111-1307, USA. */ 20 21 22/* This program is used to produce insn-recog.c, which contains 23 a function called `recog' plus its subroutines. 24 These functions contain a decision tree 25 that recognizes whether an rtx, the argument given to recog, 26 is a valid instruction. 27 28 recog returns -1 if the rtx is not valid. 29 If the rtx is valid, recog returns a nonnegative number 30 which is the insn code number for the pattern that matched. 31 This is the same as the order in the machine description of the 32 entry that matched. This number can be used as an index into various 33 insn_* tables, such as insn_template, insn_outfun, and insn_n_operands 34 (found in insn-output.c). 35 36 The third argument to recog is an optional pointer to an int. 37 If present, recog will accept a pattern if it matches except for 38 missing CLOBBER expressions at the end. In that case, the value 39 pointed to by the optional pointer will be set to the number of 40 CLOBBERs that need to be added (it should be initialized to zero by 41 the caller). If it is set nonzero, the caller should allocate a 42 PARALLEL of the appropriate size, copy the initial entries, and call 43 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. 44 45 This program also generates the function `split_insns', 46 which returns 0 if the rtl could not be split, or 47 it returns the split rtl in a SEQUENCE. */ 48 49#include "hconfig.h" 50#ifdef __STDC__ 51#include <stdarg.h> 52#else 53#include <varargs.h> 54#endif 55#include "system.h" 56#include "rtl.h" 57#include "obstack.h" 58 59static struct obstack obstack; 60struct obstack *rtl_obstack = &obstack; 61 62#define obstack_chunk_alloc xmalloc 63#define obstack_chunk_free free 64 65/* Define this so we can link with print-rtl.o to get debug_rtx function. */ 66char **insn_name_ptr = 0; 67 68/* Data structure for a listhead of decision trees. The alternatives 69 to a node are kept in a doublely-linked list so we can easily add nodes 70 to the proper place when merging. */ 71 72struct decision_head { struct decision *first, *last; }; 73 74/* Data structure for decision tree for recognizing 75 legitimate instructions. */ 76 77struct decision 78{ 79 int number; /* Node number, used for labels */ 80 char *position; /* String denoting position in pattern */ 81 RTX_CODE code; /* Code to test for or UNKNOWN to suppress */ 82 char ignore_code; /* If non-zero, need not test code */ 83 char ignore_mode; /* If non-zero, need not test mode */ 84 int veclen; /* Length of vector, if nonzero */ 85 enum machine_mode mode; /* Machine mode of node */ 86 char enforce_mode; /* If non-zero, test `mode' */ 87 char retest_code, retest_mode; /* See write_tree_1 */ 88 int test_elt_zero_int; /* Nonzero if should test XINT (rtl, 0) */ 89 int elt_zero_int; /* Required value for XINT (rtl, 0) */ 90 int test_elt_one_int; /* Nonzero if should test XINT (rtl, 1) */ 91 int elt_one_int; /* Required value for XINT (rtl, 1) */ 92 int test_elt_zero_wide; /* Nonzero if should test XWINT (rtl, 0) */ 93 HOST_WIDE_INT elt_zero_wide; /* Required value for XWINT (rtl, 0) */ 94 char *tests; /* If nonzero predicate to call */ 95 int pred; /* `preds' index of predicate or -1 */ 96 char *c_test; /* Additional test to perform */ 97 struct decision_head success; /* Nodes to test on success */ 98 int insn_code_number; /* Insn number matched, if success */ 99 int num_clobbers_to_add; /* Number of CLOBBERs to be added to pattern */ 100 struct decision *next; /* Node to test on failure */ 101 struct decision *prev; /* Node whose failure tests us */ 102 struct decision *afterward; /* Node to test on success, but failure of 103 successor nodes */ 104 int opno; /* Operand number, if >= 0 */ 105 int dupno; /* Number of operand to compare against */ 106 int label_needed; /* Nonzero if label needed when writing tree */ 107 int subroutine_number; /* Number of subroutine this node starts */ 108}; 109 110#define SUBROUTINE_THRESHOLD 50 111 112static int next_subroutine_number; 113 114/* We can write two types of subroutines: One for insn recognition and 115 one to split insns. This defines which type is being written. */ 116 117enum routine_type {RECOG, SPLIT}; 118 119/* Next available node number for tree nodes. */ 120 121static int next_number; 122 123/* Next number to use as an insn_code. */ 124 125static int next_insn_code; 126 127/* Similar, but counts all expressions in the MD file; used for 128 error messages. */ 129 130static int next_index; 131 132/* Record the highest depth we ever have so we know how many variables to 133 allocate in each subroutine we make. */ 134 135static int max_depth; 136 137/* This table contains a list of the rtl codes that can possibly match a 138 predicate defined in recog.c. The function `not_both_true' uses it to 139 deduce that there are no expressions that can be matches by certain pairs 140 of tree nodes. Also, if a predicate can match only one code, we can 141 hardwire that code into the node testing the predicate. */ 142 143static struct pred_table 144{ 145 char *name; 146 RTX_CODE codes[NUM_RTX_CODE]; 147} preds[] 148 = {{"general_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 149 LABEL_REF, SUBREG, REG, MEM}}, 150#ifdef PREDICATE_CODES 151 PREDICATE_CODES 152#endif 153 {"address_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 154 LABEL_REF, SUBREG, REG, MEM, PLUS, MINUS, MULT}}, 155 {"register_operand", {SUBREG, REG}}, 156 {"scratch_operand", {SCRATCH, REG}}, 157 {"immediate_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 158 LABEL_REF}}, 159 {"const_int_operand", {CONST_INT}}, 160 {"const_double_operand", {CONST_INT, CONST_DOUBLE}}, 161 {"nonimmediate_operand", {SUBREG, REG, MEM}}, 162 {"nonmemory_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 163 LABEL_REF, SUBREG, REG}}, 164 {"push_operand", {MEM}}, 165 {"memory_operand", {SUBREG, MEM}}, 166 {"indirect_operand", {SUBREG, MEM}}, 167 {"comparison_operator", {EQ, NE, LE, LT, GE, GT, LEU, LTU, GEU, GTU}}, 168 {"mode_independent_operand", {CONST_INT, CONST_DOUBLE, CONST, SYMBOL_REF, 169 LABEL_REF, SUBREG, REG, MEM}}}; 170 171#define NUM_KNOWN_PREDS (sizeof preds / sizeof preds[0]) 172 173static struct decision_head make_insn_sequence PROTO((rtx, enum routine_type)); 174static struct decision *add_to_sequence PROTO((rtx, struct decision_head *, 175 char *)); 176static int not_both_true PROTO((struct decision *, struct decision *, 177 int)); 178static int position_merit PROTO((struct decision *, enum machine_mode, 179 enum rtx_code)); 180static struct decision_head merge_trees PROTO((struct decision_head, 181 struct decision_head)); 182static int break_out_subroutines PROTO((struct decision_head, 183 enum routine_type, int)); 184static void write_subroutine PROTO((struct decision *, enum routine_type)); 185static void write_tree_1 PROTO((struct decision *, char *, 186 struct decision *, enum routine_type)); 187static void print_code PROTO((enum rtx_code)); 188static int same_codes PROTO((struct decision *, enum rtx_code)); 189static void clear_codes PROTO((struct decision *)); 190static int same_modes PROTO((struct decision *, enum machine_mode)); 191static void clear_modes PROTO((struct decision *)); 192static void write_tree PROTO((struct decision *, char *, 193 struct decision *, int, 194 enum routine_type)); 195static void change_state PROTO((char *, char *, int)); 196static char *copystr PROTO((char *)); 197static void mybzero PROTO((char *, unsigned)); 198static void mybcopy PROTO((char *, char *, unsigned)); 199static void fatal PVPROTO((char *, ...)) ATTRIBUTE_PRINTF_1; 200char *xrealloc PROTO((char *, unsigned)); 201char *xmalloc PROTO((unsigned)); 202void fancy_abort PROTO((void)); 203 204/* Construct and return a sequence of decisions 205 that will recognize INSN. 206 207 TYPE says what type of routine we are recognizing (RECOG or SPLIT). */ 208 209static struct decision_head 210make_insn_sequence (insn, type) 211 rtx insn; 212 enum routine_type type; 213{ 214 rtx x; 215 char *c_test = XSTR (insn, type == RECOG ? 2 : 1); 216 struct decision *last; 217 struct decision_head head; 218 219 if (XVECLEN (insn, type == RECOG) == 1) 220 x = XVECEXP (insn, type == RECOG, 0); 221 else 222 { 223 x = rtx_alloc (PARALLEL); 224 XVEC (x, 0) = XVEC (insn, type == RECOG); 225 PUT_MODE (x, VOIDmode); 226 } 227 228 last = add_to_sequence (x, &head, ""); 229 230 if (c_test[0]) 231 last->c_test = c_test; 232 last->insn_code_number = next_insn_code; 233 last->num_clobbers_to_add = 0; 234 235 /* If this is not a DEFINE_SPLIT and X is a PARALLEL, see if it ends with a 236 group of CLOBBERs of (hard) registers or MATCH_SCRATCHes. If so, set up 237 to recognize the pattern without these CLOBBERs. */ 238 239 if (type == RECOG && GET_CODE (x) == PARALLEL) 240 { 241 int i; 242 243 for (i = XVECLEN (x, 0); i > 0; i--) 244 if (GET_CODE (XVECEXP (x, 0, i - 1)) != CLOBBER 245 || (GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != REG 246 && GET_CODE (XEXP (XVECEXP (x, 0, i - 1), 0)) != MATCH_SCRATCH)) 247 break; 248 249 if (i != XVECLEN (x, 0)) 250 { 251 rtx new; 252 struct decision_head clobber_head; 253 254 if (i == 1) 255 new = XVECEXP (x, 0, 0); 256 else 257 { 258 int j; 259 260 new = rtx_alloc (PARALLEL); 261 XVEC (new, 0) = rtvec_alloc (i); 262 for (j = i - 1; j >= 0; j--) 263 XVECEXP (new, 0, j) = XVECEXP (x, 0, j); 264 } 265 266 last = add_to_sequence (new, &clobber_head, ""); 267 268 if (c_test[0]) 269 last->c_test = c_test; 270 last->insn_code_number = next_insn_code; 271 last->num_clobbers_to_add = XVECLEN (x, 0) - i; 272 273 head = merge_trees (head, clobber_head); 274 } 275 } 276 277 next_insn_code++; 278 279 if (type == SPLIT) 280 /* Define the subroutine we will call below and emit in genemit. */ 281 printf ("extern rtx gen_split_%d ();\n", last->insn_code_number); 282 283 return head; 284} 285 286/* Create a chain of nodes to verify that an rtl expression matches 287 PATTERN. 288 289 LAST is a pointer to the listhead in the previous node in the chain (or 290 in the calling function, for the first node). 291 292 POSITION is the string representing the current position in the insn. 293 294 A pointer to the final node in the chain is returned. */ 295 296static struct decision * 297add_to_sequence (pattern, last, position) 298 rtx pattern; 299 struct decision_head *last; 300 char *position; 301{ 302 register RTX_CODE code; 303 register struct decision *new 304 = (struct decision *) xmalloc (sizeof (struct decision)); 305 struct decision *this; 306 char *newpos; 307 register char *fmt; 308 register size_t i; 309 int depth = strlen (position); 310 int len; 311 312 if (depth > max_depth) 313 max_depth = depth; 314 315 new->number = next_number++; 316 new->position = copystr (position); 317 new->ignore_code = 0; 318 new->ignore_mode = 0; 319 new->enforce_mode = 1; 320 new->retest_code = new->retest_mode = 0; 321 new->veclen = 0; 322 new->test_elt_zero_int = 0; 323 new->test_elt_one_int = 0; 324 new->test_elt_zero_wide = 0; 325 new->elt_zero_int = 0; 326 new->elt_one_int = 0; 327 new->elt_zero_wide = 0; 328 new->tests = 0; 329 new->pred = -1; 330 new->c_test = 0; 331 new->success.first = new->success.last = 0; 332 new->insn_code_number = -1; 333 new->num_clobbers_to_add = 0; 334 new->next = 0; 335 new->prev = 0; 336 new->afterward = 0; 337 new->opno = -1; 338 new->dupno = -1; 339 new->label_needed = 0; 340 new->subroutine_number = 0; 341 342 this = new; 343 344 last->first = last->last = new; 345 346 newpos = (char *) alloca (depth + 2); 347 strcpy (newpos, position); 348 newpos[depth + 1] = 0; 349 350 restart: 351 352 new->mode = GET_MODE (pattern); 353 new->code = code = GET_CODE (pattern); 354 355 switch (code) 356 { 357 case MATCH_OPERAND: 358 case MATCH_SCRATCH: 359 case MATCH_OPERATOR: 360 case MATCH_PARALLEL: 361 case MATCH_INSN2: 362 new->opno = XINT (pattern, 0); 363 new->code = (code == MATCH_PARALLEL ? PARALLEL : UNKNOWN); 364 new->enforce_mode = 0; 365 366 if (code == MATCH_SCRATCH) 367 new->tests = "scratch_operand"; 368 else 369 new->tests = XSTR (pattern, 1); 370 371 if (*new->tests == 0) 372 new->tests = 0; 373 374 /* See if we know about this predicate and save its number. If we do, 375 and it only accepts one code, note that fact. The predicate 376 `const_int_operand' only tests for a CONST_INT, so if we do so we 377 can avoid calling it at all. 378 379 Finally, if we know that the predicate does not allow CONST_INT, we 380 know that the only way the predicate can match is if the modes match 381 (here we use the kludge of relying on the fact that "address_operand" 382 accepts CONST_INT; otherwise, it would have to be a special case), 383 so we can test the mode (but we need not). This fact should 384 considerably simplify the generated code. */ 385 386 if (new->tests) 387 { 388 for (i = 0; i < NUM_KNOWN_PREDS; i++) 389 if (! strcmp (preds[i].name, new->tests)) 390 { 391 int j; 392 int allows_const_int = 0; 393 394 new->pred = i; 395 396 if (preds[i].codes[1] == 0 && new->code == UNKNOWN) 397 { 398 new->code = preds[i].codes[0]; 399 if (! strcmp ("const_int_operand", new->tests)) 400 new->tests = 0, new->pred = -1; 401 } 402 403 for (j = 0; j < NUM_RTX_CODE && preds[i].codes[j] != 0; j++) 404 if (preds[i].codes[j] == CONST_INT) 405 allows_const_int = 1; 406 407 if (! allows_const_int) 408 new->enforce_mode = new->ignore_mode= 1; 409 410 break; 411 } 412 413#ifdef PREDICATE_CODES 414 /* If the port has a list of the predicates it uses but omits 415 one, warn. */ 416 if (i == NUM_KNOWN_PREDS) 417 fprintf (stderr, "Warning: `%s' not in PREDICATE_CODES\n", 418 new->tests); 419#endif 420 } 421 422 if (code == MATCH_OPERATOR || code == MATCH_PARALLEL) 423 { 424 for (i = 0; i < XVECLEN (pattern, 2); i++) 425 { 426 newpos[depth] = i + (code == MATCH_OPERATOR ? '0': 'a'); 427 new = add_to_sequence (XVECEXP (pattern, 2, i), 428 &new->success, newpos); 429 } 430 } 431 432 return new; 433 434 case MATCH_OP_DUP: 435 new->opno = XINT (pattern, 0); 436 new->dupno = XINT (pattern, 0); 437 new->code = UNKNOWN; 438 new->tests = 0; 439 for (i = 0; i < XVECLEN (pattern, 1); i++) 440 { 441 newpos[depth] = i + '0'; 442 new = add_to_sequence (XVECEXP (pattern, 1, i), 443 &new->success, newpos); 444 } 445 return new; 446 447 case MATCH_DUP: 448 case MATCH_PAR_DUP: 449 new->dupno = XINT (pattern, 0); 450 new->code = UNKNOWN; 451 new->enforce_mode = 0; 452 return new; 453 454 case ADDRESS: 455 pattern = XEXP (pattern, 0); 456 goto restart; 457 458 case SET: 459 newpos[depth] = '0'; 460 new = add_to_sequence (SET_DEST (pattern), &new->success, newpos); 461 this->success.first->enforce_mode = 1; 462 newpos[depth] = '1'; 463 new = add_to_sequence (SET_SRC (pattern), &new->success, newpos); 464 465 /* If set are setting CC0 from anything other than a COMPARE, we 466 must enforce the mode so that we do not produce ambiguous insns. */ 467 if (GET_CODE (SET_DEST (pattern)) == CC0 468 && GET_CODE (SET_SRC (pattern)) != COMPARE) 469 this->success.first->enforce_mode = 1; 470 return new; 471 472 case SIGN_EXTEND: 473 case ZERO_EXTEND: 474 case STRICT_LOW_PART: 475 newpos[depth] = '0'; 476 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 477 this->success.first->enforce_mode = 1; 478 return new; 479 480 case SUBREG: 481 this->test_elt_one_int = 1; 482 this->elt_one_int = XINT (pattern, 1); 483 newpos[depth] = '0'; 484 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 485 this->success.first->enforce_mode = 1; 486 return new; 487 488 case ZERO_EXTRACT: 489 case SIGN_EXTRACT: 490 newpos[depth] = '0'; 491 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 492 this->success.first->enforce_mode = 1; 493 newpos[depth] = '1'; 494 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos); 495 newpos[depth] = '2'; 496 new = add_to_sequence (XEXP (pattern, 2), &new->success, newpos); 497 return new; 498 499 case EQ: case NE: case LE: case LT: case GE: case GT: 500 case LEU: case LTU: case GEU: case GTU: 501 /* If the first operand is (cc0), we don't have to do anything 502 special. */ 503 if (GET_CODE (XEXP (pattern, 0)) == CC0) 504 break; 505 506 /* ... fall through ... */ 507 508 case COMPARE: 509 /* Enforce the mode on the first operand to avoid ambiguous insns. */ 510 newpos[depth] = '0'; 511 new = add_to_sequence (XEXP (pattern, 0), &new->success, newpos); 512 this->success.first->enforce_mode = 1; 513 newpos[depth] = '1'; 514 new = add_to_sequence (XEXP (pattern, 1), &new->success, newpos); 515 return new; 516 517 default: 518 break; 519 } 520 521 fmt = GET_RTX_FORMAT (code); 522 len = GET_RTX_LENGTH (code); 523 for (i = 0; i < len; i++) 524 { 525 newpos[depth] = '0' + i; 526 if (fmt[i] == 'e' || fmt[i] == 'u') 527 new = add_to_sequence (XEXP (pattern, i), &new->success, newpos); 528 else if (fmt[i] == 'i' && i == 0) 529 { 530 this->test_elt_zero_int = 1; 531 this->elt_zero_int = XINT (pattern, i); 532 } 533 else if (fmt[i] == 'i' && i == 1) 534 { 535 this->test_elt_one_int = 1; 536 this->elt_one_int = XINT (pattern, i); 537 } 538 else if (fmt[i] == 'w' && i == 0) 539 { 540 this->test_elt_zero_wide = 1; 541 this->elt_zero_wide = XWINT (pattern, i); 542 } 543 else if (fmt[i] == 'E') 544 { 545 register int j; 546 /* We do not handle a vector appearing as other than 547 the first item, just because nothing uses them 548 and by handling only the special case 549 we can use one element in newpos for either 550 the item number of a subexpression 551 or the element number in a vector. */ 552 if (i != 0) 553 abort (); 554 this->veclen = XVECLEN (pattern, i); 555 for (j = 0; j < XVECLEN (pattern, i); j++) 556 { 557 newpos[depth] = 'a' + j; 558 new = add_to_sequence (XVECEXP (pattern, i, j), 559 &new->success, newpos); 560 } 561 } 562 else if (fmt[i] != '0') 563 abort (); 564 } 565 return new; 566} 567 568/* Return 1 if we can prove that there is no RTL that can match both 569 D1 and D2. Otherwise, return 0 (it may be that there is an RTL that 570 can match both or just that we couldn't prove there wasn't such an RTL). 571 572 TOPLEVEL is non-zero if we are to only look at the top level and not 573 recursively descend. */ 574 575static int 576not_both_true (d1, d2, toplevel) 577 struct decision *d1, *d2; 578 int toplevel; 579{ 580 struct decision *p1, *p2; 581 582 /* If they are both to test modes and the modes are different, they aren't 583 both true. Similarly for codes, integer elements, and vector lengths. */ 584 585 if ((d1->enforce_mode && d2->enforce_mode 586 && d1->mode != VOIDmode && d2->mode != VOIDmode && d1->mode != d2->mode) 587 || (d1->code != UNKNOWN && d2->code != UNKNOWN && d1->code != d2->code) 588 || (d1->test_elt_zero_int && d2->test_elt_zero_int 589 && d1->elt_zero_int != d2->elt_zero_int) 590 || (d1->test_elt_one_int && d2->test_elt_one_int 591 && d1->elt_one_int != d2->elt_one_int) 592 || (d1->test_elt_zero_wide && d2->test_elt_zero_wide 593 && d1->elt_zero_wide != d2->elt_zero_wide) 594 || (d1->veclen && d2->veclen && d1->veclen != d2->veclen)) 595 return 1; 596 597 /* If either is a wild-card MATCH_OPERAND without a predicate, it can match 598 absolutely anything, so we can't say that no intersection is possible. 599 This case is detected by having a zero TESTS field with a code of 600 UNKNOWN. */ 601 602 if ((d1->tests == 0 && d1->code == UNKNOWN) 603 || (d2->tests == 0 && d2->code == UNKNOWN)) 604 return 0; 605 606 /* If either has a predicate that we know something about, set things up so 607 that D1 is the one that always has a known predicate. Then see if they 608 have any codes in common. */ 609 610 if (d1->pred >= 0 || d2->pred >= 0) 611 { 612 int i, j; 613 614 if (d2->pred >= 0) 615 p1 = d1, d1 = d2, d2 = p1; 616 617 /* If D2 tests an explicit code, see if it is in the list of valid codes 618 for D1's predicate. */ 619 if (d2->code != UNKNOWN) 620 { 621 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++) 622 if (preds[d1->pred].codes[i] == d2->code) 623 break; 624 625 if (preds[d1->pred].codes[i] == 0) 626 return 1; 627 } 628 629 /* Otherwise see if the predicates have any codes in common. */ 630 631 else if (d2->pred >= 0) 632 { 633 for (i = 0; i < NUM_RTX_CODE && preds[d1->pred].codes[i] != 0; i++) 634 { 635 for (j = 0; j < NUM_RTX_CODE; j++) 636 if (preds[d2->pred].codes[j] == 0 637 || preds[d2->pred].codes[j] == preds[d1->pred].codes[i]) 638 break; 639 640 if (preds[d2->pred].codes[j] != 0) 641 break; 642 } 643 644 if (preds[d1->pred].codes[i] == 0) 645 return 1; 646 } 647 } 648 649 /* If we got here, we can't prove that D1 and D2 cannot both be true. 650 If we are only to check the top level, return 0. Otherwise, see if 651 we can prove that all choices in both successors are mutually 652 exclusive. If either does not have any successors, we can't prove 653 they can't both be true. */ 654 655 if (toplevel || d1->success.first == 0 || d2->success.first == 0) 656 return 0; 657 658 for (p1 = d1->success.first; p1; p1 = p1->next) 659 for (p2 = d2->success.first; p2; p2 = p2->next) 660 if (! not_both_true (p1, p2, 0)) 661 return 0; 662 663 return 1; 664} 665 666/* Assuming that we can reorder all the alternatives at a specific point in 667 the tree (see discussion in merge_trees), we would prefer an ordering of 668 nodes where groups of consecutive nodes test the same mode and, within each 669 mode, groups of nodes test the same code. With this order, we can 670 construct nested switch statements, the inner one to test the code and 671 the outer one to test the mode. 672 673 We would like to list nodes testing for specific codes before those 674 that test predicates to avoid unnecessary function calls. Similarly, 675 tests for specific modes should precede nodes that allow any mode. 676 677 This function returns the merit (with 0 being the best) of inserting 678 a test involving the specified MODE and CODE after node P. If P is 679 zero, we are to determine the merit of inserting the test at the front 680 of the list. */ 681 682static int 683position_merit (p, mode, code) 684 struct decision *p; 685 enum machine_mode mode; 686 enum rtx_code code; 687{ 688 enum machine_mode p_mode; 689 690 /* The only time the front of the list is anything other than the worst 691 position is if we are testing a mode that isn't VOIDmode. */ 692 if (p == 0) 693 return mode == VOIDmode ? 3 : 2; 694 695 p_mode = p->enforce_mode ? p->mode : VOIDmode; 696 697 /* The best case is if the codes and modes both match. */ 698 if (p_mode == mode && p->code== code) 699 return 0; 700 701 /* If the codes don't match, the next best case is if the modes match. 702 In that case, the best position for this node depends on whether 703 we are testing for a specific code or not. If we are, the best place 704 is after some other test for an explicit code and our mode or after 705 the last test in the previous mode if every test in our mode is for 706 an unknown code. 707 708 If we are testing for UNKNOWN, then the next best case is at the end of 709 our mode. */ 710 711 if ((code != UNKNOWN 712 && ((p_mode == mode && p->code != UNKNOWN) 713 || (p_mode != mode && p->next 714 && (p->next->enforce_mode ? p->next->mode : VOIDmode) == mode 715 && (p->next->code == UNKNOWN)))) 716 || (code == UNKNOWN && p_mode == mode 717 && (p->next == 0 718 || (p->next->enforce_mode ? p->next->mode : VOIDmode) != mode))) 719 return 1; 720 721 /* The third best case occurs when nothing is testing MODE. If MODE 722 is not VOIDmode, then the third best case is after something of any 723 mode that is not VOIDmode. If we are testing VOIDmode, the third best 724 place is the end of the list. */ 725 726 if (p_mode != mode 727 && ((mode != VOIDmode && p_mode != VOIDmode) 728 || (mode == VOIDmode && p->next == 0))) 729 return 2; 730 731 /* Otherwise, we have the worst case. */ 732 return 3; 733} 734 735/* Merge two decision tree listheads OLDH and ADDH, 736 modifying OLDH destructively, and return the merged tree. */ 737 738static struct decision_head 739merge_trees (oldh, addh) 740 register struct decision_head oldh, addh; 741{ 742 struct decision *add, *next; 743 744 if (oldh.first == 0) 745 return addh; 746 747 if (addh.first == 0) 748 return oldh; 749 750 /* If we are adding things at different positions, something is wrong. */ 751 if (strcmp (oldh.first->position, addh.first->position)) 752 abort (); 753 754 for (add = addh.first; add; add = next) 755 { 756 enum machine_mode add_mode = add->enforce_mode ? add->mode : VOIDmode; 757 struct decision *best_position = 0; 758 int best_merit = 4; 759 struct decision *old; 760 761 next = add->next; 762 763 /* The semantics of pattern matching state that the tests are done in 764 the order given in the MD file so that if an insn matches two 765 patterns, the first one will be used. However, in practice, most, 766 if not all, patterns are unambiguous so that their order is 767 independent. In that case, we can merge identical tests and 768 group all similar modes and codes together. 769 770 Scan starting from the end of OLDH until we reach a point 771 where we reach the head of the list or where we pass a pattern 772 that could also be true if NEW is true. If we find an identical 773 pattern, we can merge them. Also, record the last node that tests 774 the same code and mode and the last one that tests just the same mode. 775 776 If we have no match, place NEW after the closest match we found. */ 777 778 for (old = oldh.last; old; old = old->prev) 779 { 780 int our_merit; 781 782 /* If we don't have anything to test except an additional test, 783 do not consider the two nodes equal. If we did, the test below 784 would cause an infinite recursion. */ 785 if (old->tests == 0 && old->test_elt_zero_int == 0 786 && old->test_elt_one_int == 0 && old->veclen == 0 787 && old->test_elt_zero_wide == 0 788 && old->dupno == -1 && old->mode == VOIDmode 789 && old->code == UNKNOWN 790 && (old->c_test != 0 || add->c_test != 0)) 791 ; 792 793 else if ((old->tests == add->tests 794 || (old->pred >= 0 && old->pred == add->pred) 795 || (old->tests && add->tests 796 && !strcmp (old->tests, add->tests))) 797 && old->test_elt_zero_int == add->test_elt_zero_int 798 && old->elt_zero_int == add->elt_zero_int 799 && old->test_elt_one_int == add->test_elt_one_int 800 && old->elt_one_int == add->elt_one_int 801 && old->test_elt_zero_wide == add->test_elt_zero_wide 802 && old->elt_zero_wide == add->elt_zero_wide 803 && old->veclen == add->veclen 804 && old->dupno == add->dupno 805 && old->opno == add->opno 806 && old->code == add->code 807 && old->enforce_mode == add->enforce_mode 808 && old->mode == add->mode) 809 { 810 /* If the additional test is not the same, split both nodes 811 into nodes that just contain all things tested before the 812 additional test and nodes that contain the additional test 813 and actions when it is true. This optimization is important 814 because of the case where we have almost identical patterns 815 with different tests on target flags. */ 816 817 if (old->c_test != add->c_test 818 && ! (old->c_test && add->c_test 819 && !strcmp (old->c_test, add->c_test))) 820 { 821 if (old->insn_code_number >= 0 || old->opno >= 0) 822 { 823 struct decision *split 824 = (struct decision *) xmalloc (sizeof (struct decision)); 825 826 mybcopy ((char *) old, (char *) split, 827 sizeof (struct decision)); 828 829 old->success.first = old->success.last = split; 830 old->c_test = 0; 831 old->opno = -1; 832 old->insn_code_number = -1; 833 old->num_clobbers_to_add = 0; 834 835 split->number = next_number++; 836 split->next = split->prev = 0; 837 split->mode = VOIDmode; 838 split->code = UNKNOWN; 839 split->veclen = 0; 840 split->test_elt_zero_int = 0; 841 split->test_elt_one_int = 0; 842 split->test_elt_zero_wide = 0; 843 split->tests = 0; 844 split->pred = -1; 845 split->dupno = -1; 846 } 847 848 if (add->insn_code_number >= 0 || add->opno >= 0) 849 { 850 struct decision *split 851 = (struct decision *) xmalloc (sizeof (struct decision)); 852 853 mybcopy ((char *) add, (char *) split, 854 sizeof (struct decision)); 855 856 add->success.first = add->success.last = split; 857 add->c_test = 0; 858 add->opno = -1; 859 add->insn_code_number = -1; 860 add->num_clobbers_to_add = 0; 861 862 split->number = next_number++; 863 split->next = split->prev = 0; 864 split->mode = VOIDmode; 865 split->code = UNKNOWN; 866 split->veclen = 0; 867 split->test_elt_zero_int = 0; 868 split->test_elt_one_int = 0; 869 split->test_elt_zero_wide = 0; 870 split->tests = 0; 871 split->pred = -1; 872 split->dupno = -1; 873 } 874 } 875 876 if (old->insn_code_number >= 0 && add->insn_code_number >= 0) 877 { 878 /* If one node is for a normal insn and the second is 879 for the base insn with clobbers stripped off, the 880 second node should be ignored. */ 881 882 if (old->num_clobbers_to_add == 0 883 && add->num_clobbers_to_add > 0) 884 /* Nothing to do here. */ 885 ; 886 else if (old->num_clobbers_to_add > 0 887 && add->num_clobbers_to_add == 0) 888 { 889 /* In this case, replace OLD with ADD. */ 890 old->insn_code_number = add->insn_code_number; 891 old->num_clobbers_to_add = 0; 892 } 893 else 894 fatal ("Two actions at one point in tree"); 895 } 896 897 if (old->insn_code_number == -1) 898 old->insn_code_number = add->insn_code_number; 899 old->success = merge_trees (old->success, add->success); 900 add = 0; 901 break; 902 } 903 904 /* Unless we have already found the best possible insert point, 905 see if this position is better. If so, record it. */ 906 907 if (best_merit != 0 908 && ((our_merit = position_merit (old, add_mode, add->code)) 909 < best_merit)) 910 best_merit = our_merit, best_position = old; 911 912 if (! not_both_true (old, add, 0)) 913 break; 914 } 915 916 /* If ADD was duplicate, we are done. */ 917 if (add == 0) 918 continue; 919 920 /* Otherwise, find the best place to insert ADD. Normally this is 921 BEST_POSITION. However, if we went all the way to the top of 922 the list, it might be better to insert at the top. */ 923 924 if (best_position == 0) 925 abort (); 926 927 if (old == 0 928 && position_merit (NULL_PTR, add_mode, add->code) < best_merit) 929 { 930 add->prev = 0; 931 add->next = oldh.first; 932 oldh.first->prev = add; 933 oldh.first = add; 934 } 935 936 else 937 { 938 add->prev = best_position; 939 add->next = best_position->next; 940 best_position->next = add; 941 if (best_position == oldh.last) 942 oldh.last = add; 943 else 944 add->next->prev = add; 945 } 946 } 947 948 return oldh; 949} 950 951/* Count the number of subnodes of HEAD. If the number is high enough, 952 make the first node in HEAD start a separate subroutine in the C code 953 that is generated. 954 955 TYPE gives the type of routine we are writing. 956 957 INITIAL is non-zero if this is the highest-level node. We never write 958 it out here. */ 959 960static int 961break_out_subroutines (head, type, initial) 962 struct decision_head head; 963 enum routine_type type; 964 int initial; 965{ 966 int size = 0; 967 struct decision *sub; 968 969 for (sub = head.first; sub; sub = sub->next) 970 size += 1 + break_out_subroutines (sub->success, type, 0); 971 972 if (size > SUBROUTINE_THRESHOLD && ! initial) 973 { 974 head.first->subroutine_number = ++next_subroutine_number; 975 write_subroutine (head.first, type); 976 size = 1; 977 } 978 return size; 979} 980 981/* Write out a subroutine of type TYPE to do comparisons starting at node 982 TREE. */ 983 984static void 985write_subroutine (tree, type) 986 struct decision *tree; 987 enum routine_type type; 988{ 989 int i; 990 991 if (type == SPLIT) 992 printf ("rtx\nsplit"); 993 else 994 printf ("int\nrecog"); 995 996 if (tree != 0 && tree->subroutine_number > 0) 997 printf ("_%d", tree->subroutine_number); 998 else if (type == SPLIT) 999 printf ("_insns"); 1000 1001 printf (" (x0, insn"); 1002 if (type == RECOG) 1003 printf (", pnum_clobbers"); 1004 1005 printf (")\n"); 1006 printf (" register rtx x0;\n rtx insn ATTRIBUTE_UNUSED;\n"); 1007 if (type == RECOG) 1008 printf (" int *pnum_clobbers ATTRIBUTE_UNUSED;\n"); 1009 1010 printf ("{\n"); 1011 printf (" register rtx *ro = &recog_operand[0];\n"); 1012 1013 printf (" register rtx "); 1014 for (i = 1; i < max_depth; i++) 1015 printf ("x%d ATTRIBUTE_UNUSED, ", i); 1016 1017 printf ("x%d ATTRIBUTE_UNUSED;\n", max_depth); 1018 printf (" %s tem ATTRIBUTE_UNUSED;\n", type == SPLIT ? "rtx" : "int"); 1019 write_tree (tree, "", NULL_PTR, 1, type); 1020 printf (" ret0: return %d;\n}\n\n", type == SPLIT ? 0 : -1); 1021} 1022 1023/* This table is used to indent the recog_* functions when we are inside 1024 conditions or switch statements. We only support small indentations 1025 and always indent at least two spaces. */ 1026 1027static char *indents[] 1028 = {" ", " ", " ", " ", " ", " ", " ", " ", 1029 "\t", "\t ", "\t ", "\t ", "\t ", "\t ", "\t ", 1030 "\t\t", "\t\t ", "\t\t ", "\t\t ", "\t\t ", "\t\t "}; 1031 1032/* Write out C code to perform the decisions in TREE for a subroutine of 1033 type TYPE. If all of the choices fail, branch to node AFTERWARD, if 1034 non-zero, otherwise return. PREVPOS is the position of the node that 1035 branched to this test. 1036 1037 When we merged all alternatives, we tried to set up a convenient order. 1038 Specifically, tests involving the same mode are all grouped together, 1039 followed by a group that does not contain a mode test. Within each group 1040 of the same mode, we also group tests with the same code, followed by a 1041 group that does not test a code. 1042 1043 Occasionally, we cannot arbitrarily reorder the tests so that multiple 1044 sequence of groups as described above are present. 1045 1046 We generate two nested switch statements, the outer statement for 1047 testing modes, and the inner switch for testing RTX codes. It is 1048 not worth optimizing cases when only a small number of modes or 1049 codes is tested, since the compiler can do that when compiling the 1050 resulting function. We do check for when every test is the same mode 1051 or code. */ 1052 1053static void 1054write_tree_1 (tree, prevpos, afterward, type) 1055 struct decision *tree; 1056 char *prevpos; 1057 struct decision *afterward; 1058 enum routine_type type; 1059{ 1060 register struct decision *p, *p1; 1061 register int depth = tree ? strlen (tree->position) : 0; 1062 enum machine_mode switch_mode = VOIDmode; 1063 RTX_CODE switch_code = UNKNOWN; 1064 int uncond = 0; 1065 char modemap[NUM_MACHINE_MODES]; 1066 char codemap[NUM_RTX_CODE]; 1067 int indent = 2; 1068 int i; 1069 1070 /* One tricky area is what is the exact state when we branch to a 1071 node's label. There are two cases where we branch: when looking at 1072 successors to a node, or when a set of tests fails. 1073 1074 In the former case, we are always branching to the first node in a 1075 decision list and we want all required tests to be performed. We 1076 put the labels for such nodes in front of any switch or test statements. 1077 These branches are done without updating the position to that of the 1078 target node. 1079 1080 In the latter case, we are branching to a node that is not the first 1081 node in a decision list. We have already checked that it is possible 1082 for both the node we originally tested at this level and the node we 1083 are branching to to both match some pattern. That means that they 1084 usually will be testing the same mode and code. So it is normally safe 1085 for such labels to be inside switch statements, since the tests done 1086 by virtue of arriving at that label will usually already have been 1087 done. The exception is a branch from a node that does not test a 1088 mode or code to one that does. In such cases, we set the `retest_mode' 1089 or `retest_code' flags. That will ensure that we start a new switch 1090 at that position and put the label before the switch. 1091 1092 The branches in the latter case must set the position to that of the 1093 target node. */ 1094 1095 1096 printf ("\n"); 1097 if (tree && tree->subroutine_number == 0) 1098 { 1099 printf (" L%d:\n", tree->number); 1100 tree->label_needed = 0; 1101 } 1102 1103 if (tree) 1104 { 1105 change_state (prevpos, tree->position, 2); 1106 prevpos = tree->position; 1107 } 1108 1109 for (p = tree; p; p = p->next) 1110 { 1111 enum machine_mode mode = p->enforce_mode ? p->mode : VOIDmode; 1112 int need_bracket; 1113 int wrote_bracket = 0; 1114 int inner_indent; 1115 1116 if (p->success.first == 0 && p->insn_code_number < 0) 1117 abort (); 1118 1119 /* Find the next alternative to p that might be true when p is true. 1120 Test that one next if p's successors fail. */ 1121 1122 for (p1 = p->next; p1 && not_both_true (p, p1, 1); p1 = p1->next) 1123 ; 1124 p->afterward = p1; 1125 1126 if (p1) 1127 { 1128 if (mode == VOIDmode && p1->enforce_mode && p1->mode != VOIDmode) 1129 p1->retest_mode = 1; 1130 if (p->code == UNKNOWN && p1->code != UNKNOWN) 1131 p1->retest_code = 1; 1132 p1->label_needed = 1; 1133 } 1134 1135 /* If we have a different code or mode than the last node and 1136 are in a switch on codes, we must either end the switch or 1137 go to another case. We must also end the switch if this 1138 node needs a label and to retest either the mode or code. */ 1139 1140 if (switch_code != UNKNOWN 1141 && (switch_code != p->code || switch_mode != mode 1142 || (p->label_needed && (p->retest_mode || p->retest_code)))) 1143 { 1144 enum rtx_code code = p->code; 1145 1146 /* If P is testing a predicate that we know about and we haven't 1147 seen any of the codes that are valid for the predicate, we 1148 can write a series of "case" statement, one for each possible 1149 code. Since we are already in a switch, these redundant tests 1150 are very cheap and will reduce the number of predicate called. */ 1151 1152 if (p->pred >= 0) 1153 { 1154 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++) 1155 if (codemap[(int) preds[p->pred].codes[i]]) 1156 break; 1157 1158 if (preds[p->pred].codes[i] == 0) 1159 code = MATCH_OPERAND; 1160 } 1161 1162 if (code == UNKNOWN || codemap[(int) code] 1163 || switch_mode != mode 1164 || (p->label_needed && (p->retest_mode || p->retest_code))) 1165 { 1166 printf ("%s}\n", indents[indent - 2]); 1167 switch_code = UNKNOWN; 1168 indent -= 4; 1169 } 1170 else 1171 { 1172 if (! uncond) 1173 printf ("%sbreak;\n", indents[indent]); 1174 1175 if (code == MATCH_OPERAND) 1176 { 1177 for (i = 0; i < NUM_RTX_CODE && preds[p->pred].codes[i] != 0; i++) 1178 { 1179 printf ("%scase ", indents[indent - 2]); 1180 print_code (preds[p->pred].codes[i]); 1181 printf (":\n"); 1182 codemap[(int) preds[p->pred].codes[i]] = 1; 1183 } 1184 } 1185 else 1186 { 1187 printf ("%scase ", indents[indent - 2]); 1188 print_code (code); 1189 printf (":\n"); 1190 codemap[(int) p->code] = 1; 1191 } 1192 1193 switch_code = code; 1194 } 1195 1196 uncond = 0; 1197 } 1198 1199 /* If we were previously in a switch on modes and now have a different 1200 mode, end at least the case, and maybe end the switch if we are 1201 not testing a mode or testing a mode whose case we already saw. */ 1202 1203 if (switch_mode != VOIDmode 1204 && (switch_mode != mode || (p->label_needed && p->retest_mode))) 1205 { 1206 if (mode == VOIDmode || modemap[(int) mode] 1207 || (p->label_needed && p->retest_mode)) 1208 { 1209 printf ("%s}\n", indents[indent - 2]); 1210 switch_mode = VOIDmode; 1211 indent -= 4; 1212 } 1213 else 1214 { 1215 if (! uncond) 1216 printf (" break;\n"); 1217 printf (" case %smode:\n", GET_MODE_NAME (mode)); 1218 switch_mode = mode; 1219 modemap[(int) mode] = 1; 1220 } 1221 1222 uncond = 0; 1223 } 1224 1225 /* If we are about to write dead code, something went wrong. */ 1226 if (! p->label_needed && uncond) 1227 abort (); 1228 1229 /* If we need a label and we will want to retest the mode or code at 1230 that label, write the label now. We have already ensured that 1231 things will be valid for the test. */ 1232 1233 if (p->label_needed && (p->retest_mode || p->retest_code)) 1234 { 1235 printf ("%sL%d:\n", indents[indent - 2], p->number); 1236 p->label_needed = 0; 1237 } 1238 1239 uncond = 0; 1240 1241 /* If we are not in any switches, see if we can shortcut things 1242 by checking for identical modes and codes. */ 1243 1244 if (switch_mode == VOIDmode && switch_code == UNKNOWN) 1245 { 1246 /* If p and its alternatives all want the same mode, 1247 reject all others at once, first, then ignore the mode. */ 1248 1249 if (mode != VOIDmode && p->next && same_modes (p, mode)) 1250 { 1251 printf (" if (GET_MODE (x%d) != %smode)\n", 1252 depth, GET_MODE_NAME (p->mode)); 1253 if (afterward) 1254 { 1255 printf (" {\n"); 1256 change_state (p->position, afterward->position, 6); 1257 printf (" goto L%d;\n }\n", afterward->number); 1258 } 1259 else 1260 printf (" goto ret0;\n"); 1261 clear_modes (p); 1262 mode = VOIDmode; 1263 } 1264 1265 /* If p and its alternatives all want the same code, 1266 reject all others at once, first, then ignore the code. */ 1267 1268 if (p->code != UNKNOWN && p->next && same_codes (p, p->code)) 1269 { 1270 printf (" if (GET_CODE (x%d) != ", depth); 1271 print_code (p->code); 1272 printf (")\n"); 1273 if (afterward) 1274 { 1275 printf (" {\n"); 1276 change_state (p->position, afterward->position, indent + 4); 1277 printf (" goto L%d;\n }\n", afterward->number); 1278 } 1279 else 1280 printf (" goto ret0;\n"); 1281 clear_codes (p); 1282 } 1283 } 1284 1285 /* If we are not in a mode switch and we are testing for a specific 1286 mode, start a mode switch unless we have just one node or the next 1287 node is not testing a mode (we have already tested for the case of 1288 more than one mode, but all of the same mode). */ 1289 1290 if (switch_mode == VOIDmode && mode != VOIDmode && p->next != 0 1291 && p->next->enforce_mode && p->next->mode != VOIDmode) 1292 { 1293 mybzero (modemap, sizeof modemap); 1294 printf ("%sswitch (GET_MODE (x%d))\n", indents[indent], depth); 1295 printf ("%s{\n", indents[indent + 2]); 1296 indent += 4; 1297 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2], 1298 indents[indent]); 1299 printf ("%scase %smode:\n", indents[indent - 2], 1300 GET_MODE_NAME (mode)); 1301 modemap[(int) mode] = 1; 1302 switch_mode = mode; 1303 } 1304 1305 /* Similarly for testing codes. */ 1306 1307 if (switch_code == UNKNOWN && p->code != UNKNOWN && ! p->ignore_code 1308 && p->next != 0 && p->next->code != UNKNOWN) 1309 { 1310 mybzero (codemap, sizeof codemap); 1311 printf ("%sswitch (GET_CODE (x%d))\n", indents[indent], depth); 1312 printf ("%s{\n", indents[indent + 2]); 1313 indent += 4; 1314 printf ("%sdefault:\n%sbreak;\n", indents[indent - 2], 1315 indents[indent]); 1316 printf ("%scase ", indents[indent - 2]); 1317 print_code (p->code); 1318 printf (":\n"); 1319 codemap[(int) p->code] = 1; 1320 switch_code = p->code; 1321 } 1322 1323 /* Now that most mode and code tests have been done, we can write out 1324 a label for an inner node, if we haven't already. */ 1325 if (p->label_needed) 1326 printf ("%sL%d:\n", indents[indent - 2], p->number); 1327 1328 inner_indent = indent; 1329 1330 /* The only way we can have to do a mode or code test here is if 1331 this node needs such a test but is the only node to be tested. 1332 In that case, we won't have started a switch. Note that this is 1333 the only way the switch and test modes can disagree. */ 1334 1335 if ((mode != switch_mode && ! p->ignore_mode) 1336 || (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code) 1337 || p->test_elt_zero_int || p->test_elt_one_int 1338 || p->test_elt_zero_wide || p->veclen 1339 || p->dupno >= 0 || p->tests || p->num_clobbers_to_add) 1340 { 1341 printf ("%sif (", indents[indent]); 1342 1343 if (mode != switch_mode && ! p->ignore_mode) 1344 printf ("GET_MODE (x%d) == %smode && ", 1345 depth, GET_MODE_NAME (mode)); 1346 if (p->code != switch_code && p->code != UNKNOWN && ! p->ignore_code) 1347 { 1348 printf ("GET_CODE (x%d) == ", depth); 1349 print_code (p->code); 1350 printf (" && "); 1351 } 1352 1353 if (p->test_elt_zero_int) 1354 printf ("XINT (x%d, 0) == %d && ", depth, p->elt_zero_int); 1355 if (p->test_elt_one_int) 1356 printf ("XINT (x%d, 1) == %d && ", depth, p->elt_one_int); 1357 if (p->test_elt_zero_wide) 1358 { 1359 /* Set offset to 1 iff the number might get propagated to 1360 unsigned long by ANSI C rules, else 0. 1361 Prospective hosts are required to have at least 32 bit 1362 ints, and integer constants in machine descriptions 1363 must fit in 32 bit, thus it suffices to check only 1364 for 1 << 31 . */ 1365 HOST_WIDE_INT offset = p->elt_zero_wide == -2147483647 - 1; 1366 printf ("XWINT (x%d, 0) == ", depth); 1367 printf (HOST_WIDE_INT_PRINT_DEC, p->elt_zero_wide + offset); 1368 printf ("%s && ", offset ? "-1" : ""); 1369 } 1370 if (p->veclen) 1371 printf ("XVECLEN (x%d, 0) == %d && ", depth, p->veclen); 1372 if (p->dupno >= 0) 1373 printf ("rtx_equal_p (x%d, ro[%d]) && ", depth, p->dupno); 1374 if (p->num_clobbers_to_add) 1375 printf ("pnum_clobbers != 0 && "); 1376 if (p->tests) 1377 printf ("%s (x%d, %smode)", p->tests, depth, 1378 GET_MODE_NAME (p->mode)); 1379 else 1380 printf ("1"); 1381 1382 printf (")\n"); 1383 inner_indent += 2; 1384 } 1385 else 1386 uncond = 1; 1387 1388 need_bracket = ! uncond; 1389 1390 if (p->opno >= 0) 1391 { 1392 if (need_bracket) 1393 { 1394 printf ("%s{\n", indents[inner_indent]); 1395 inner_indent += 2; 1396 wrote_bracket = 1; 1397 need_bracket = 0; 1398 } 1399 1400 printf ("%sro[%d] = x%d;\n", indents[inner_indent], p->opno, depth); 1401 } 1402 1403 if (p->c_test) 1404 { 1405 printf ("%sif (%s)\n", indents[inner_indent], p->c_test); 1406 inner_indent += 2; 1407 uncond = 0; 1408 need_bracket = 1; 1409 } 1410 1411 if (p->insn_code_number >= 0) 1412 { 1413 if (type == SPLIT) 1414 printf ("%sreturn gen_split_%d (operands);\n", 1415 indents[inner_indent], p->insn_code_number); 1416 else 1417 { 1418 if (p->num_clobbers_to_add) 1419 { 1420 if (need_bracket) 1421 { 1422 printf ("%s{\n", indents[inner_indent]); 1423 inner_indent += 2; 1424 } 1425 1426 printf ("%s*pnum_clobbers = %d;\n", 1427 indents[inner_indent], p->num_clobbers_to_add); 1428 printf ("%sreturn %d;\n", 1429 indents[inner_indent], p->insn_code_number); 1430 1431 if (need_bracket) 1432 { 1433 inner_indent -= 2; 1434 printf ("%s}\n", indents[inner_indent]); 1435 } 1436 } 1437 else 1438 printf ("%sreturn %d;\n", 1439 indents[inner_indent], p->insn_code_number); 1440 } 1441 } 1442 else 1443 printf ("%sgoto L%d;\n", indents[inner_indent], 1444 p->success.first->number); 1445 1446 if (wrote_bracket) 1447 printf ("%s}\n", indents[inner_indent - 2]); 1448 } 1449 1450 /* We have now tested all alternatives. End any switches we have open 1451 and branch to the alternative node unless we know that we can't fall 1452 through to the branch. */ 1453 1454 if (switch_code != UNKNOWN) 1455 { 1456 printf ("%s}\n", indents[indent - 2]); 1457 indent -= 4; 1458 uncond = 0; 1459 } 1460 1461 if (switch_mode != VOIDmode) 1462 { 1463 printf ("%s}\n", indents[indent - 2]); 1464 indent -= 4; 1465 uncond = 0; 1466 } 1467 1468 if (indent != 2) 1469 abort (); 1470 1471 if (uncond) 1472 return; 1473 1474 if (afterward) 1475 { 1476 change_state (prevpos, afterward->position, 2); 1477 printf (" goto L%d;\n", afterward->number); 1478 } 1479 else 1480 printf (" goto ret0;\n"); 1481} 1482 1483static void 1484print_code (code) 1485 enum rtx_code code; 1486{ 1487 register char *p1; 1488 for (p1 = GET_RTX_NAME (code); *p1; p1++) 1489 { 1490 if (*p1 >= 'a' && *p1 <= 'z') 1491 putchar (*p1 + 'A' - 'a'); 1492 else 1493 putchar (*p1); 1494 } 1495} 1496 1497static int 1498same_codes (p, code) 1499 register struct decision *p; 1500 register enum rtx_code code; 1501{ 1502 for (; p; p = p->next) 1503 if (p->code != code) 1504 return 0; 1505 1506 return 1; 1507} 1508 1509static void 1510clear_codes (p) 1511 register struct decision *p; 1512{ 1513 for (; p; p = p->next) 1514 p->ignore_code = 1; 1515} 1516 1517static int 1518same_modes (p, mode) 1519 register struct decision *p; 1520 register enum machine_mode mode; 1521{ 1522 for (; p; p = p->next) 1523 if ((p->enforce_mode ? p->mode : VOIDmode) != mode) 1524 return 0; 1525 1526 return 1; 1527} 1528 1529static void 1530clear_modes (p) 1531 register struct decision *p; 1532{ 1533 for (; p; p = p->next) 1534 p->enforce_mode = 0; 1535} 1536 1537/* Write out the decision tree starting at TREE for a subroutine of type TYPE. 1538 1539 PREVPOS is the position at the node that branched to this node. 1540 1541 INITIAL is nonzero if this is the first node we are writing in a subroutine. 1542 1543 If all nodes are false, branch to the node AFTERWARD. */ 1544 1545static void 1546write_tree (tree, prevpos, afterward, initial, type) 1547 struct decision *tree; 1548 char *prevpos; 1549 struct decision *afterward; 1550 int initial; 1551 enum routine_type type; 1552{ 1553 register struct decision *p; 1554 char *name_prefix = (type == SPLIT ? "split" : "recog"); 1555 char *call_suffix = (type == SPLIT ? "" : ", pnum_clobbers"); 1556 1557 if (! initial && tree->subroutine_number > 0) 1558 { 1559 printf (" L%d:\n", tree->number); 1560 1561 if (afterward) 1562 { 1563 printf (" tem = %s_%d (x0, insn%s);\n", 1564 name_prefix, tree->subroutine_number, call_suffix); 1565 if (type == SPLIT) 1566 printf (" if (tem != 0) return tem;\n"); 1567 else 1568 printf (" if (tem >= 0) return tem;\n"); 1569 change_state (tree->position, afterward->position, 2); 1570 printf (" goto L%d;\n", afterward->number); 1571 } 1572 else 1573 printf (" return %s_%d (x0, insn%s);\n", 1574 name_prefix, tree->subroutine_number, call_suffix); 1575 return; 1576 } 1577 1578 write_tree_1 (tree, prevpos, afterward, type); 1579 1580 for (p = tree; p; p = p->next) 1581 if (p->success.first) 1582 write_tree (p->success.first, p->position, 1583 p->afterward ? p->afterward : afterward, 0, type); 1584} 1585 1586 1587/* Assuming that the state of argument is denoted by OLDPOS, take whatever 1588 actions are necessary to move to NEWPOS. 1589 1590 INDENT says how many blanks to place at the front of lines. */ 1591 1592static void 1593change_state (oldpos, newpos, indent) 1594 char *oldpos; 1595 char *newpos; 1596 int indent; 1597{ 1598 int odepth = strlen (oldpos); 1599 int depth = odepth; 1600 int ndepth = strlen (newpos); 1601 1602 /* Pop up as many levels as necessary. */ 1603 1604 while (strncmp (oldpos, newpos, depth)) 1605 --depth; 1606 1607 /* Go down to desired level. */ 1608 1609 while (depth < ndepth) 1610 { 1611 if (newpos[depth] >= 'a' && newpos[depth] <= 'z') 1612 printf ("%sx%d = XVECEXP (x%d, 0, %d);\n", 1613 indents[indent], depth + 1, depth, newpos[depth] - 'a'); 1614 else 1615 printf ("%sx%d = XEXP (x%d, %c);\n", 1616 indents[indent], depth + 1, depth, newpos[depth]); 1617 ++depth; 1618 } 1619} 1620 1621static char * 1622copystr (s1) 1623 char *s1; 1624{ 1625 register char *tem; 1626 1627 if (s1 == 0) 1628 return 0; 1629 1630 tem = (char *) xmalloc (strlen (s1) + 1); 1631 strcpy (tem, s1); 1632 1633 return tem; 1634} 1635 1636static void 1637mybzero (b, length) 1638 register char *b; 1639 register unsigned length; 1640{ 1641 while (length-- > 0) 1642 *b++ = 0; 1643} 1644 1645static void 1646mybcopy (in, out, length) 1647 register char *in, *out; 1648 register unsigned length; 1649{ 1650 while (length-- > 0) 1651 *out++ = *in++; 1652} 1653 1654char * 1655xrealloc (ptr, size) 1656 char *ptr; 1657 unsigned size; 1658{ 1659 char *result = (char *) realloc (ptr, size); 1660 if (!result) 1661 fatal ("virtual memory exhausted"); 1662 return result; 1663} 1664 1665char * 1666xmalloc (size) 1667 unsigned size; 1668{ 1669 register char *val = (char *) malloc (size); 1670 1671 if (val == 0) 1672 fatal ("virtual memory exhausted"); 1673 return val; 1674} 1675 1676static void 1677fatal VPROTO ((char *format, ...)) 1678{ 1679#ifndef __STDC__ 1680 char *format; 1681#endif 1682 va_list ap; 1683 1684 VA_START (ap, format); 1685 1686#ifndef __STDC__ 1687 format = va_arg (ap, char *); 1688#endif 1689 1690 fprintf (stderr, "genrecog: "); 1691 vfprintf (stderr, format, ap); 1692 va_end (ap); 1693 fprintf (stderr, "\n"); 1694 fprintf (stderr, "after %d definitions\n", next_index); 1695 exit (FATAL_EXIT_CODE); 1696} 1697 1698/* More 'friendly' abort that prints the line and file. 1699 config.h can #define abort fancy_abort if you like that sort of thing. */ 1700 1701void 1702fancy_abort () 1703{ 1704 fatal ("Internal gcc abort."); 1705} 1706 1707int 1708main (argc, argv) 1709 int argc; 1710 char **argv; 1711{ 1712 rtx desc; 1713 struct decision_head recog_tree; 1714 struct decision_head split_tree; 1715 FILE *infile; 1716 register int c; 1717 1718 obstack_init (rtl_obstack); 1719 recog_tree.first = recog_tree.last = split_tree.first = split_tree.last = 0; 1720 1721 if (argc <= 1) 1722 fatal ("No input file name."); 1723 1724 infile = fopen (argv[1], "r"); 1725 if (infile == 0) 1726 { 1727 perror (argv[1]); 1728 exit (FATAL_EXIT_CODE); 1729 } 1730 1731 init_rtl (); 1732 next_insn_code = 0; 1733 next_index = 0; 1734 1735 printf ("/* Generated automatically by the program `genrecog'\n\ 1736from the machine description file `md'. */\n\n"); 1737 1738 printf ("#include \"config.h\"\n"); 1739 printf ("#include \"system.h\"\n"); 1740 printf ("#include \"rtl.h\"\n"); 1741 printf ("#include \"insn-config.h\"\n"); 1742 printf ("#include \"recog.h\"\n"); 1743 printf ("#include \"real.h\"\n"); 1744 printf ("#include \"output.h\"\n"); 1745 printf ("#include \"flags.h\"\n"); 1746 printf ("\n"); 1747 1748 /* Read the machine description. */ 1749 1750 while (1) 1751 { 1752 c = read_skip_spaces (infile); 1753 if (c == EOF) 1754 break; 1755 ungetc (c, infile); 1756 1757 desc = read_rtx (infile); 1758 if (GET_CODE (desc) == DEFINE_INSN) 1759 recog_tree = merge_trees (recog_tree, 1760 make_insn_sequence (desc, RECOG)); 1761 else if (GET_CODE (desc) == DEFINE_SPLIT) 1762 split_tree = merge_trees (split_tree, 1763 make_insn_sequence (desc, SPLIT)); 1764 if (GET_CODE (desc) == DEFINE_PEEPHOLE 1765 || GET_CODE (desc) == DEFINE_EXPAND) 1766 next_insn_code++; 1767 next_index++; 1768 } 1769 1770 printf ("\n\ 1771/* `recog' contains a decision tree\n\ 1772 that recognizes whether the rtx X0 is a valid instruction.\n\ 1773\n\ 1774 recog returns -1 if the rtx is not valid.\n\ 1775 If the rtx is valid, recog returns a nonnegative number\n\ 1776 which is the insn code number for the pattern that matched.\n"); 1777 printf (" This is the same as the order in the machine description of\n\ 1778 the entry that matched. This number can be used as an index into various\n\ 1779 insn_* tables, such as insn_templates, insn_outfun, and insn_n_operands\n\ 1780 (found in insn-output.c).\n\n"); 1781 printf (" The third argument to recog is an optional pointer to an int.\n\ 1782 If present, recog will accept a pattern if it matches except for\n\ 1783 missing CLOBBER expressions at the end. In that case, the value\n\ 1784 pointed to by the optional pointer will be set to the number of\n\ 1785 CLOBBERs that need to be added (it should be initialized to zero by\n\ 1786 the caller). If it is set nonzero, the caller should allocate a\n\ 1787 PARALLEL of the appropriate size, copy the initial entries, and call\n\ 1788 add_clobbers (found in insn-emit.c) to fill in the CLOBBERs."); 1789 1790 if (split_tree.first) 1791 printf ("\n\n The function split_insns returns 0 if the rtl could not\n\ 1792 be split or the split rtl in a SEQUENCE if it can be."); 1793 1794 printf ("*/\n\n"); 1795 1796 printf ("rtx recog_operand[MAX_RECOG_OPERANDS];\n\n"); 1797 printf ("rtx *recog_operand_loc[MAX_RECOG_OPERANDS];\n\n"); 1798 printf ("rtx *recog_dup_loc[MAX_DUP_OPERANDS];\n\n"); 1799 printf ("char recog_dup_num[MAX_DUP_OPERANDS];\n\n"); 1800 printf ("#define operands recog_operand\n\n"); 1801 1802 next_subroutine_number = 0; 1803 break_out_subroutines (recog_tree, RECOG, 1); 1804 write_subroutine (recog_tree.first, RECOG); 1805 1806 next_subroutine_number = 0; 1807 break_out_subroutines (split_tree, SPLIT, 1); 1808 write_subroutine (split_tree.first, SPLIT); 1809 1810 fflush (stdout); 1811 exit (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE); 1812 /* NOTREACHED */ 1813 return 0; 1814} 1815