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