1 /* Generate code from machine description to recognize rtl as insns. 2 Copyright (C) 1987-2018 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14 License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20 21 /* This program is used to produce insn-recog.c, which contains a 22 function called `recog' plus its subroutines. These functions 23 contain a decision tree that recognizes whether an rtx, the 24 argument given to recog, is a valid instruction. 25 26 recog returns -1 if the rtx is not valid. If the rtx is valid, 27 recog returns a nonnegative number which is the insn code number 28 for the pattern that matched. This is the same as the order in the 29 machine description of the entry that matched. This number can be 30 used as an index into various insn_* tables, such as insn_template, 31 insn_outfun, and insn_n_operands (found in insn-output.c). 32 33 The third argument to recog is an optional pointer to an int. If 34 present, recog will accept a pattern if it matches except for 35 missing CLOBBER expressions at the end. In that case, the value 36 pointed to by the optional pointer will be set to the number of 37 CLOBBERs that need to be added (it should be initialized to zero by 38 the caller). If it is set nonzero, the caller should allocate a 39 PARALLEL of the appropriate size, copy the initial entries, and 40 call add_clobbers (found in insn-emit.c) to fill in the CLOBBERs. 41 42 This program also generates the function `split_insns', which 43 returns 0 if the rtl could not be split, or it returns the split 44 rtl as an INSN list. 45 46 This program also generates the function `peephole2_insns', which 47 returns 0 if the rtl could not be matched. If there was a match, 48 the new rtl is returned in an INSN list, and LAST_INSN will point 49 to the last recognized insn in the old sequence. 50 51 52 At a high level, the algorithm used in this file is as follows: 53 54 1. Build up a decision tree for each routine, using the following 55 approach to matching an rtx: 56 57 - First determine the "shape" of the rtx, based on GET_CODE, 58 XVECLEN and XINT. This phase examines SET_SRCs before SET_DESTs 59 since SET_SRCs tend to be more distinctive. It examines other 60 operands in numerical order, since the canonicalization rules 61 prefer putting complex operands of commutative operators first. 62 63 - Next check modes and predicates. This phase examines all 64 operands in numerical order, even for SETs, since the mode of a 65 SET_DEST is exact while the mode of a SET_SRC can be VOIDmode 66 for constant integers. 67 68 - Next check match_dups. 69 70 - Finally check the C condition and (where appropriate) pnum_clobbers. 71 72 2. Try to optimize the tree by removing redundant tests, CSEing tests, 73 folding tests together, etc. 74 75 3. Look for common subtrees and split them out into "pattern" routines. 76 These common subtrees can be identical or they can differ in mode, 77 code, or integer (usually an UNSPEC or UNSPEC_VOLATILE code). 78 In the latter case the users of the pattern routine pass the 79 appropriate mode, etc., as argument. For example, if two patterns 80 contain: 81 82 (plus:SI (match_operand:SI 1 "register_operand") 83 (match_operand:SI 2 "register_operand")) 84 85 we can split the associated matching code out into a subroutine. 86 If a pattern contains: 87 88 (minus:DI (match_operand:DI 1 "register_operand") 89 (match_operand:DI 2 "register_operand")) 90 91 then we can consider using the same matching routine for both 92 the plus and minus expressions, passing PLUS and SImode in the 93 former case and MINUS and DImode in the latter case. 94 95 The main aim of this phase is to reduce the compile time of the 96 insn-recog.c code and to reduce the amount of object code in 97 insn-recog.o. 98 99 4. Split the matching trees into functions, trying to limit the 100 size of each function to a sensible amount. 101 102 Again, the main aim of this phase is to reduce the compile time 103 of insn-recog.c. (It doesn't help with the size of insn-recog.o.) 104 105 5. Write out C++ code for each function. */ 106 107 #include "bconfig.h" 108 #define INCLUDE_ALGORITHM 109 #include "system.h" 110 #include "coretypes.h" 111 #include "tm.h" 112 #include "rtl.h" 113 #include "errors.h" 114 #include "read-md.h" 115 #include "gensupport.h" 116 117 #undef GENERATOR_FILE 118 enum true_rtx_doe { 119 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS) TRUE_##ENUM, 120 #include "rtl.def" 121 #undef DEF_RTL_EXPR 122 FIRST_GENERATOR_RTX_CODE 123 }; 124 #define NUM_TRUE_RTX_CODE ((int) FIRST_GENERATOR_RTX_CODE) 125 #define GENERATOR_FILE 1 126 127 /* Debugging variables to control which optimizations are performed. 128 Note that disabling merge_states_p leads to very large output. */ 129 static const bool merge_states_p = true; 130 static const bool collapse_optional_decisions_p = true; 131 static const bool cse_tests_p = true; 132 static const bool simplify_tests_p = true; 133 static const bool use_operand_variables_p = true; 134 static const bool use_subroutines_p = true; 135 static const bool use_pattern_routines_p = true; 136 137 /* Whether to add comments for optional tests that we decided to keep. 138 Can be useful when debugging the generator itself but is noise when 139 debugging the generated code. */ 140 static const bool mark_optional_transitions_p = false; 141 142 /* Whether pattern routines should calculate positions relative to their 143 rtx parameter rather than use absolute positions. This e.g. allows 144 a pattern routine to be shared between a plain SET and a PARALLEL 145 that includes a SET. 146 147 In principle it sounds like this should be useful, especially for 148 recog_for_combine, where the plain SET form is generated automatically 149 from a PARALLEL of a single SET and some CLOBBERs. In practice it doesn't 150 seem to help much and leads to slightly bigger object files. */ 151 static const bool relative_patterns_p = false; 152 153 /* Whether pattern routines should be allowed to test whether pnum_clobbers 154 is null. This requires passing pnum_clobbers around as a parameter. */ 155 static const bool pattern_have_num_clobbers_p = true; 156 157 /* Whether pattern routines should be allowed to test .md file C conditions. 158 This requires passing insn around as a parameter, in case the C 159 condition refers to it. In practice this tends to lead to bigger 160 object files. */ 161 static const bool pattern_c_test_p = false; 162 163 /* Whether to require each parameter passed to a pattern routine to be 164 unique. Disabling this check for example allows unary operators with 165 matching modes (like NEG) and unary operators with mismatched modes 166 (like ZERO_EXTEND) to be matched by a single pattern. However, we then 167 often have cases where the same value is passed too many times. */ 168 static const bool force_unique_params_p = true; 169 170 /* The maximum (approximate) depth of block nesting that an individual 171 routine or subroutine should have. This limit is about keeping the 172 output readable rather than reducing compile time. */ 173 static const unsigned int MAX_DEPTH = 6; 174 175 /* The minimum number of pseudo-statements that a state must have before 176 we split it out into a subroutine. */ 177 static const unsigned int MIN_NUM_STATEMENTS = 5; 178 179 /* The number of pseudo-statements a state can have before we consider 180 splitting out substates into subroutines. This limit is about avoiding 181 compile-time problems with very big functions (and also about keeping 182 functions within --param optimization limits, etc.). */ 183 static const unsigned int MAX_NUM_STATEMENTS = 200; 184 185 /* The minimum number of pseudo-statements that can be used in a pattern 186 routine. */ 187 static const unsigned int MIN_COMBINE_COST = 4; 188 189 /* The maximum number of arguments that a pattern routine can have. 190 The idea is to prevent one pattern getting a ridiculous number of 191 arguments when it would be more beneficial to have a separate pattern 192 routine instead. */ 193 static const unsigned int MAX_PATTERN_PARAMS = 5; 194 195 /* The maximum operand number plus one. */ 196 int num_operands; 197 198 /* Ways of obtaining an rtx to be tested. */ 199 enum position_type { 200 /* PATTERN (peep2_next_insn (ARG)). */ 201 POS_PEEP2_INSN, 202 203 /* XEXP (BASE, ARG). */ 204 POS_XEXP, 205 206 /* XVECEXP (BASE, 0, ARG). */ 207 POS_XVECEXP0 208 }; 209 210 /* The position of an rtx relative to X0. Each useful position is 211 represented by exactly one instance of this structure. */ 212 struct position 213 { 214 /* The parent rtx. This is the root position for POS_PEEP2_INSNs. */ 215 struct position *base; 216 217 /* A position with the same BASE and TYPE, but with the next value 218 of ARG. */ 219 struct position *next; 220 221 /* A list of all POS_XEXP positions that use this one as their base, 222 chained by NEXT fields. The first entry represents XEXP (this, 0), 223 the second represents XEXP (this, 1), and so on. */ 224 struct position *xexps; 225 226 /* A list of POS_XVECEXP0 positions that use this one as their base, 227 chained by NEXT fields. The first entry represents XVECEXP (this, 0, 0), 228 the second represents XVECEXP (this, 0, 1), and so on. */ 229 struct position *xvecexp0s; 230 231 /* The type of position. */ 232 enum position_type type; 233 234 /* The argument to TYPE (shown as ARG in the position_type comments). */ 235 int arg; 236 237 /* The instruction to which the position belongs. */ 238 unsigned int insn_id; 239 240 /* The depth of this position relative to the instruction pattern. 241 E.g. if the instruction pattern is a SET, the SET itself has a 242 depth of 0 while the SET_DEST and SET_SRC have depths of 1. */ 243 unsigned int depth; 244 245 /* A unique identifier for this position. */ 246 unsigned int id; 247 }; 248 249 enum routine_type { 250 SUBPATTERN, RECOG, SPLIT, PEEPHOLE2 251 }; 252 253 /* The root position (x0). */ 254 static struct position root_pos; 255 256 /* The number of positions created. Also one higher than the maximum 257 position id. */ 258 static unsigned int num_positions = 1; 259 260 /* A list of all POS_PEEP2_INSNs. The entry for insn 0 is the root position, 261 since we are given that instruction's pattern as x0. */ 262 static struct position *peep2_insn_pos_list = &root_pos; 263 264 /* Return a position with the given BASE, TYPE and ARG. NEXT_PTR 265 points to where the unique object that represents the position 266 should be stored. Create the object if it doesn't already exist, 267 otherwise reuse the object that is already there. */ 268 269 static struct position * 270 next_position (struct position **next_ptr, struct position *base, 271 enum position_type type, int arg) 272 { 273 struct position *pos; 274 275 pos = *next_ptr; 276 if (!pos) 277 { 278 pos = XCNEW (struct position); 279 pos->type = type; 280 pos->arg = arg; 281 if (type == POS_PEEP2_INSN) 282 { 283 pos->base = 0; 284 pos->insn_id = arg; 285 pos->depth = base->depth; 286 } 287 else 288 { 289 pos->base = base; 290 pos->insn_id = base->insn_id; 291 pos->depth = base->depth + 1; 292 } 293 pos->id = num_positions++; 294 *next_ptr = pos; 295 } 296 return pos; 297 } 298 299 /* Compare positions POS1 and POS2 lexicographically. */ 300 301 static int 302 compare_positions (struct position *pos1, struct position *pos2) 303 { 304 int diff; 305 306 diff = pos1->depth - pos2->depth; 307 if (diff < 0) 308 do 309 pos2 = pos2->base; 310 while (pos1->depth != pos2->depth); 311 else if (diff > 0) 312 do 313 pos1 = pos1->base; 314 while (pos1->depth != pos2->depth); 315 while (pos1 != pos2) 316 { 317 diff = (int) pos1->type - (int) pos2->type; 318 if (diff == 0) 319 diff = pos1->arg - pos2->arg; 320 pos1 = pos1->base; 321 pos2 = pos2->base; 322 } 323 return diff; 324 } 325 326 /* Return the most deeply-nested position that is common to both 327 POS1 and POS2. If the positions are from different instructions, 328 return the one with the lowest insn_id. */ 329 330 static struct position * 331 common_position (struct position *pos1, struct position *pos2) 332 { 333 if (pos1->insn_id != pos2->insn_id) 334 return pos1->insn_id < pos2->insn_id ? pos1 : pos2; 335 if (pos1->depth > pos2->depth) 336 std::swap (pos1, pos2); 337 while (pos1->depth != pos2->depth) 338 pos2 = pos2->base; 339 while (pos1 != pos2) 340 { 341 pos1 = pos1->base; 342 pos2 = pos2->base; 343 } 344 return pos1; 345 } 346 347 /* Search for and return operand N, stop when reaching node STOP. */ 348 349 static rtx 350 find_operand (rtx pattern, int n, rtx stop) 351 { 352 const char *fmt; 353 RTX_CODE code; 354 int i, j, len; 355 rtx r; 356 357 if (pattern == stop) 358 return stop; 359 360 code = GET_CODE (pattern); 361 if ((code == MATCH_SCRATCH 362 || code == MATCH_OPERAND 363 || code == MATCH_OPERATOR 364 || code == MATCH_PARALLEL) 365 && XINT (pattern, 0) == n) 366 return pattern; 367 368 fmt = GET_RTX_FORMAT (code); 369 len = GET_RTX_LENGTH (code); 370 for (i = 0; i < len; i++) 371 { 372 switch (fmt[i]) 373 { 374 case 'e': case 'u': 375 if ((r = find_operand (XEXP (pattern, i), n, stop)) != NULL_RTX) 376 return r; 377 break; 378 379 case 'V': 380 if (! XVEC (pattern, i)) 381 break; 382 /* Fall through. */ 383 384 case 'E': 385 for (j = 0; j < XVECLEN (pattern, i); j++) 386 if ((r = find_operand (XVECEXP (pattern, i, j), n, stop)) 387 != NULL_RTX) 388 return r; 389 break; 390 391 case 'r': case 'p': case 'i': case 'w': case '0': case 's': 392 break; 393 394 default: 395 gcc_unreachable (); 396 } 397 } 398 399 return NULL; 400 } 401 402 /* Search for and return operand M, such that it has a matching 403 constraint for operand N. */ 404 405 static rtx 406 find_matching_operand (rtx pattern, int n) 407 { 408 const char *fmt; 409 RTX_CODE code; 410 int i, j, len; 411 rtx r; 412 413 code = GET_CODE (pattern); 414 if (code == MATCH_OPERAND 415 && (XSTR (pattern, 2)[0] == '0' + n 416 || (XSTR (pattern, 2)[0] == '%' 417 && XSTR (pattern, 2)[1] == '0' + n))) 418 return pattern; 419 420 fmt = GET_RTX_FORMAT (code); 421 len = GET_RTX_LENGTH (code); 422 for (i = 0; i < len; i++) 423 { 424 switch (fmt[i]) 425 { 426 case 'e': case 'u': 427 if ((r = find_matching_operand (XEXP (pattern, i), n))) 428 return r; 429 break; 430 431 case 'V': 432 if (! XVEC (pattern, i)) 433 break; 434 /* Fall through. */ 435 436 case 'E': 437 for (j = 0; j < XVECLEN (pattern, i); j++) 438 if ((r = find_matching_operand (XVECEXP (pattern, i, j), n))) 439 return r; 440 break; 441 442 case 'r': case 'p': case 'i': case 'w': case '0': case 's': 443 break; 444 445 default: 446 gcc_unreachable (); 447 } 448 } 449 450 return NULL; 451 } 452 453 /* In DEFINE_EXPAND, DEFINE_SPLIT, and DEFINE_PEEPHOLE2, we 454 don't use the MATCH_OPERAND constraint, only the predicate. 455 This is confusing to folks doing new ports, so help them 456 not make the mistake. */ 457 458 static bool 459 constraints_supported_in_insn_p (rtx insn) 460 { 461 return !(GET_CODE (insn) == DEFINE_EXPAND 462 || GET_CODE (insn) == DEFINE_SPLIT 463 || GET_CODE (insn) == DEFINE_PEEPHOLE2); 464 } 465 466 /* Return the name of the predicate matched by MATCH_RTX. */ 467 468 static const char * 469 predicate_name (rtx match_rtx) 470 { 471 if (GET_CODE (match_rtx) == MATCH_SCRATCH) 472 return "scratch_operand"; 473 else 474 return XSTR (match_rtx, 1); 475 } 476 477 /* Return true if OPERAND is a MATCH_OPERAND using a special predicate 478 function. */ 479 480 static bool 481 special_predicate_operand_p (rtx operand) 482 { 483 if (GET_CODE (operand) == MATCH_OPERAND) 484 { 485 const char *pred_name = predicate_name (operand); 486 if (pred_name[0] != 0) 487 { 488 const struct pred_data *pred; 489 490 pred = lookup_predicate (pred_name); 491 return pred != NULL && pred->special; 492 } 493 } 494 495 return false; 496 } 497 498 /* Check for various errors in PATTERN, which is part of INFO. 499 SET is nonnull for a destination, and is the complete set pattern. 500 SET_CODE is '=' for normal sets, and '+' within a context that 501 requires in-out constraints. */ 502 503 static void 504 validate_pattern (rtx pattern, md_rtx_info *info, rtx set, int set_code) 505 { 506 const char *fmt; 507 RTX_CODE code; 508 size_t i, len; 509 int j; 510 511 code = GET_CODE (pattern); 512 switch (code) 513 { 514 case MATCH_SCRATCH: 515 { 516 const char constraints0 = XSTR (pattern, 1)[0]; 517 518 if (!constraints_supported_in_insn_p (info->def)) 519 { 520 if (constraints0) 521 { 522 error_at (info->loc, "constraints not supported in %s", 523 GET_RTX_NAME (GET_CODE (info->def))); 524 } 525 return; 526 } 527 528 /* If a MATCH_SCRATCH is used in a context requiring an write-only 529 or read/write register, validate that. */ 530 if (set_code == '=' 531 && constraints0 532 && constraints0 != '=' 533 && constraints0 != '+') 534 { 535 error_at (info->loc, "operand %d missing output reload", 536 XINT (pattern, 0)); 537 } 538 return; 539 } 540 case MATCH_DUP: 541 case MATCH_OP_DUP: 542 case MATCH_PAR_DUP: 543 if (find_operand (info->def, XINT (pattern, 0), pattern) == pattern) 544 error_at (info->loc, "operand %i duplicated before defined", 545 XINT (pattern, 0)); 546 break; 547 case MATCH_OPERAND: 548 case MATCH_OPERATOR: 549 { 550 const char *pred_name = XSTR (pattern, 1); 551 const struct pred_data *pred; 552 const char *c_test; 553 554 c_test = get_c_test (info->def); 555 556 if (pred_name[0] != 0) 557 { 558 pred = lookup_predicate (pred_name); 559 if (!pred) 560 error_at (info->loc, "unknown predicate '%s'", pred_name); 561 } 562 else 563 pred = 0; 564 565 if (code == MATCH_OPERAND) 566 { 567 const char *constraints = XSTR (pattern, 2); 568 const char constraints0 = constraints[0]; 569 570 if (!constraints_supported_in_insn_p (info->def)) 571 { 572 if (constraints0) 573 { 574 error_at (info->loc, "constraints not supported in %s", 575 GET_RTX_NAME (GET_CODE (info->def))); 576 } 577 } 578 579 /* A MATCH_OPERAND that is a SET should have an output reload. */ 580 else if (set && constraints0) 581 { 582 if (set_code == '+') 583 { 584 if (constraints0 == '+') 585 ; 586 /* If we've only got an output reload for this operand, 587 we'd better have a matching input operand. */ 588 else if (constraints0 == '=' 589 && find_matching_operand (info->def, 590 XINT (pattern, 0))) 591 ; 592 else 593 error_at (info->loc, "operand %d missing in-out reload", 594 XINT (pattern, 0)); 595 } 596 else if (constraints0 != '=' && constraints0 != '+') 597 error_at (info->loc, "operand %d missing output reload", 598 XINT (pattern, 0)); 599 } 600 601 /* For matching constraint in MATCH_OPERAND, the digit must be a 602 smaller number than the number of the operand that uses it in the 603 constraint. */ 604 while (1) 605 { 606 while (constraints[0] 607 && (constraints[0] == ' ' || constraints[0] == ',')) 608 constraints++; 609 if (!constraints[0]) 610 break; 611 612 if (constraints[0] >= '0' && constraints[0] <= '9') 613 { 614 int val; 615 616 sscanf (constraints, "%d", &val); 617 if (val >= XINT (pattern, 0)) 618 error_at (info->loc, "constraint digit %d is not" 619 " smaller than operand %d", 620 val, XINT (pattern, 0)); 621 } 622 623 while (constraints[0] && constraints[0] != ',') 624 constraints++; 625 } 626 } 627 628 /* Allowing non-lvalues in destinations -- particularly CONST_INT -- 629 while not likely to occur at runtime, results in less efficient 630 code from insn-recog.c. */ 631 if (set && pred && pred->allows_non_lvalue) 632 error_at (info->loc, "destination operand %d allows non-lvalue", 633 XINT (pattern, 0)); 634 635 /* A modeless MATCH_OPERAND can be handy when we can check for 636 multiple modes in the c_test. In most other cases, it is a 637 mistake. Only DEFINE_INSN is eligible, since SPLIT and 638 PEEP2 can FAIL within the output pattern. Exclude special 639 predicates, which check the mode themselves. Also exclude 640 predicates that allow only constants. Exclude the SET_DEST 641 of a call instruction, as that is a common idiom. */ 642 643 if (GET_MODE (pattern) == VOIDmode 644 && code == MATCH_OPERAND 645 && GET_CODE (info->def) == DEFINE_INSN 646 && pred 647 && !pred->special 648 && pred->allows_non_const 649 && strstr (c_test, "operands") == NULL 650 && ! (set 651 && GET_CODE (set) == SET 652 && GET_CODE (SET_SRC (set)) == CALL)) 653 message_at (info->loc, "warning: operand %d missing mode?", 654 XINT (pattern, 0)); 655 return; 656 } 657 658 case SET: 659 { 660 machine_mode dmode, smode; 661 rtx dest, src; 662 663 dest = SET_DEST (pattern); 664 src = SET_SRC (pattern); 665 666 /* STRICT_LOW_PART is a wrapper. Its argument is the real 667 destination, and it's mode should match the source. */ 668 if (GET_CODE (dest) == STRICT_LOW_PART) 669 dest = XEXP (dest, 0); 670 671 /* Find the referent for a DUP. */ 672 673 if (GET_CODE (dest) == MATCH_DUP 674 || GET_CODE (dest) == MATCH_OP_DUP 675 || GET_CODE (dest) == MATCH_PAR_DUP) 676 dest = find_operand (info->def, XINT (dest, 0), NULL); 677 678 if (GET_CODE (src) == MATCH_DUP 679 || GET_CODE (src) == MATCH_OP_DUP 680 || GET_CODE (src) == MATCH_PAR_DUP) 681 src = find_operand (info->def, XINT (src, 0), NULL); 682 683 dmode = GET_MODE (dest); 684 smode = GET_MODE (src); 685 686 /* Mode checking is not performed for special predicates. */ 687 if (special_predicate_operand_p (src) 688 || special_predicate_operand_p (dest)) 689 ; 690 691 /* The operands of a SET must have the same mode unless one 692 is VOIDmode. */ 693 else if (dmode != VOIDmode && smode != VOIDmode && dmode != smode) 694 error_at (info->loc, "mode mismatch in set: %smode vs %smode", 695 GET_MODE_NAME (dmode), GET_MODE_NAME (smode)); 696 697 /* If only one of the operands is VOIDmode, and PC or CC0 is 698 not involved, it's probably a mistake. */ 699 else if (dmode != smode 700 && GET_CODE (dest) != PC 701 && GET_CODE (dest) != CC0 702 && GET_CODE (src) != PC 703 && GET_CODE (src) != CC0 704 && !CONST_INT_P (src) 705 && !CONST_WIDE_INT_P (src) 706 && GET_CODE (src) != CALL) 707 { 708 const char *which; 709 which = (dmode == VOIDmode ? "destination" : "source"); 710 message_at (info->loc, "warning: %s missing a mode?", which); 711 } 712 713 if (dest != SET_DEST (pattern)) 714 validate_pattern (dest, info, pattern, '='); 715 validate_pattern (SET_DEST (pattern), info, pattern, '='); 716 validate_pattern (SET_SRC (pattern), info, NULL_RTX, 0); 717 return; 718 } 719 720 case CLOBBER: 721 validate_pattern (SET_DEST (pattern), info, pattern, '='); 722 return; 723 724 case ZERO_EXTRACT: 725 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0); 726 validate_pattern (XEXP (pattern, 1), info, NULL_RTX, 0); 727 validate_pattern (XEXP (pattern, 2), info, NULL_RTX, 0); 728 return; 729 730 case STRICT_LOW_PART: 731 validate_pattern (XEXP (pattern, 0), info, set, set ? '+' : 0); 732 return; 733 734 case LABEL_REF: 735 if (GET_MODE (XEXP (pattern, 0)) != VOIDmode) 736 error_at (info->loc, "operand to label_ref %smode not VOIDmode", 737 GET_MODE_NAME (GET_MODE (XEXP (pattern, 0)))); 738 break; 739 740 case VEC_SELECT: 741 if (GET_MODE (pattern) != VOIDmode) 742 { 743 machine_mode mode = GET_MODE (pattern); 744 machine_mode imode = GET_MODE (XEXP (pattern, 0)); 745 machine_mode emode 746 = VECTOR_MODE_P (mode) ? GET_MODE_INNER (mode) : mode; 747 if (GET_CODE (XEXP (pattern, 1)) == PARALLEL) 748 { 749 int expected = 1; 750 unsigned int nelems; 751 if (VECTOR_MODE_P (mode) 752 && !GET_MODE_NUNITS (mode).is_constant (&expected)) 753 error_at (info->loc, 754 "vec_select with variable-sized mode %s", 755 GET_MODE_NAME (mode)); 756 else if (XVECLEN (XEXP (pattern, 1), 0) != expected) 757 error_at (info->loc, 758 "vec_select parallel with %d elements, expected %d", 759 XVECLEN (XEXP (pattern, 1), 0), expected); 760 else if (VECTOR_MODE_P (imode) 761 && GET_MODE_NUNITS (imode).is_constant (&nelems)) 762 { 763 int i; 764 for (i = 0; i < expected; ++i) 765 if (CONST_INT_P (XVECEXP (XEXP (pattern, 1), 0, i)) 766 && (UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)) 767 >= nelems)) 768 error_at (info->loc, 769 "out of bounds selector %u in vec_select, " 770 "expected at most %u", 771 (unsigned) 772 UINTVAL (XVECEXP (XEXP (pattern, 1), 0, i)), 773 nelems - 1); 774 } 775 } 776 if (imode != VOIDmode && !VECTOR_MODE_P (imode)) 777 error_at (info->loc, "%smode of first vec_select operand is not a " 778 "vector mode", GET_MODE_NAME (imode)); 779 else if (imode != VOIDmode && GET_MODE_INNER (imode) != emode) 780 error_at (info->loc, "element mode mismatch between vec_select " 781 "%smode and its operand %smode", 782 GET_MODE_NAME (emode), 783 GET_MODE_NAME (GET_MODE_INNER (imode))); 784 } 785 break; 786 787 default: 788 break; 789 } 790 791 fmt = GET_RTX_FORMAT (code); 792 len = GET_RTX_LENGTH (code); 793 for (i = 0; i < len; i++) 794 { 795 switch (fmt[i]) 796 { 797 case 'e': case 'u': 798 validate_pattern (XEXP (pattern, i), info, NULL_RTX, 0); 799 break; 800 801 case 'E': 802 for (j = 0; j < XVECLEN (pattern, i); j++) 803 validate_pattern (XVECEXP (pattern, i, j), info, NULL_RTX, 0); 804 break; 805 806 case 'r': case 'p': case 'i': case 'w': case '0': case 's': 807 break; 808 809 default: 810 gcc_unreachable (); 811 } 812 } 813 } 814 815 /* Simple list structure for items of type T, for use when being part 816 of a list is an inherent property of T. T must have members equivalent 817 to "T *prev, *next;" and a function "void set_parent (list_head <T> *)" 818 to set the parent list. */ 819 template <typename T> 820 struct list_head 821 { 822 /* A range of linked items. */ 823 struct range 824 { 825 range (T *); 826 range (T *, T *); 827 828 T *start, *end; 829 void set_parent (list_head *); 830 }; 831 832 list_head (); 833 range release (); 834 void push_back (range); 835 range remove (range); 836 void replace (range, range); 837 T *singleton () const; 838 839 T *first, *last; 840 }; 841 842 /* Create a range [START_IN, START_IN]. */ 843 844 template <typename T> 845 list_head <T>::range::range (T *start_in) : start (start_in), end (start_in) {} 846 847 /* Create a range [START_IN, END_IN], linked by next and prev fields. */ 848 849 template <typename T> 850 list_head <T>::range::range (T *start_in, T *end_in) 851 : start (start_in), end (end_in) {} 852 853 template <typename T> 854 void 855 list_head <T>::range::set_parent (list_head <T> *owner) 856 { 857 for (T *item = start; item != end; item = item->next) 858 item->set_parent (owner); 859 end->set_parent (owner); 860 } 861 862 template <typename T> 863 list_head <T>::list_head () : first (0), last (0) {} 864 865 /* Add R to the end of the list. */ 866 867 template <typename T> 868 void 869 list_head <T>::push_back (range r) 870 { 871 if (last) 872 last->next = r.start; 873 else 874 first = r.start; 875 r.start->prev = last; 876 last = r.end; 877 r.set_parent (this); 878 } 879 880 /* Remove R from the list. R remains valid and can be inserted into 881 other lists. */ 882 883 template <typename T> 884 typename list_head <T>::range 885 list_head <T>::remove (range r) 886 { 887 if (r.start->prev) 888 r.start->prev->next = r.end->next; 889 else 890 first = r.end->next; 891 if (r.end->next) 892 r.end->next->prev = r.start->prev; 893 else 894 last = r.start->prev; 895 r.start->prev = 0; 896 r.end->next = 0; 897 r.set_parent (0); 898 return r; 899 } 900 901 /* Replace OLDR with NEWR. OLDR remains valid and can be inserted into 902 other lists. */ 903 904 template <typename T> 905 void 906 list_head <T>::replace (range oldr, range newr) 907 { 908 newr.start->prev = oldr.start->prev; 909 newr.end->next = oldr.end->next; 910 911 oldr.start->prev = 0; 912 oldr.end->next = 0; 913 oldr.set_parent (0); 914 915 if (newr.start->prev) 916 newr.start->prev->next = newr.start; 917 else 918 first = newr.start; 919 if (newr.end->next) 920 newr.end->next->prev = newr.end; 921 else 922 last = newr.end; 923 newr.set_parent (this); 924 } 925 926 /* Empty the list and return the previous contents as a range that can 927 be inserted into other lists. */ 928 929 template <typename T> 930 typename list_head <T>::range 931 list_head <T>::release () 932 { 933 range r (first, last); 934 first = 0; 935 last = 0; 936 r.set_parent (0); 937 return r; 938 } 939 940 /* If the list contains a single item, return that item, otherwise return 941 null. */ 942 943 template <typename T> 944 T * 945 list_head <T>::singleton () const 946 { 947 return first == last ? first : 0; 948 } 949 950 struct state; 951 952 /* Describes a possible successful return from a routine. */ 953 struct acceptance_type 954 { 955 /* The type of routine we're returning from. */ 956 routine_type type : 16; 957 958 /* True if this structure only really represents a partial match, 959 and if we must call a subroutine of type TYPE to complete the match. 960 In this case we'll call the subroutine and, if it succeeds, return 961 whatever the subroutine returned. 962 963 False if this structure presents a full match. */ 964 unsigned int partial_p : 1; 965 966 union 967 { 968 /* If PARTIAL_P, this is the number of the subroutine to call. */ 969 int subroutine_id; 970 971 /* Valid if !PARTIAL_P. */ 972 struct 973 { 974 /* The identifier of the matching pattern. For SUBPATTERNs this 975 value belongs to an ad-hoc routine-specific enum. For the 976 others it's the number of an .md file pattern. */ 977 int code; 978 union 979 { 980 /* For RECOG, the number of clobbers that must be added to the 981 pattern in order for it to match CODE. */ 982 int num_clobbers; 983 984 /* For PEEPHOLE2, the number of additional instructions that were 985 included in the optimization. */ 986 int match_len; 987 } u; 988 } full; 989 } u; 990 }; 991 992 bool 993 operator == (const acceptance_type &a, const acceptance_type &b) 994 { 995 if (a.partial_p != b.partial_p) 996 return false; 997 if (a.partial_p) 998 return a.u.subroutine_id == b.u.subroutine_id; 999 else 1000 return a.u.full.code == b.u.full.code; 1001 } 1002 1003 bool 1004 operator != (const acceptance_type &a, const acceptance_type &b) 1005 { 1006 return !operator == (a, b); 1007 } 1008 1009 /* Represents a parameter to a pattern routine. */ 1010 struct parameter 1011 { 1012 /* The C type of parameter. */ 1013 enum type_enum { 1014 /* Represents an invalid parameter. */ 1015 UNSET, 1016 1017 /* A machine_mode parameter. */ 1018 MODE, 1019 1020 /* An rtx_code parameter. */ 1021 CODE, 1022 1023 /* An int parameter. */ 1024 INT, 1025 1026 /* An unsigned int parameter. */ 1027 UINT, 1028 1029 /* A HOST_WIDE_INT parameter. */ 1030 WIDE_INT 1031 }; 1032 1033 parameter (); 1034 parameter (type_enum, bool, uint64_t); 1035 1036 /* The type of the parameter. */ 1037 type_enum type; 1038 1039 /* True if the value passed is variable, false if it is constant. */ 1040 bool is_param; 1041 1042 /* If IS_PARAM, this is the number of the variable passed, for an "i%d" 1043 format string. If !IS_PARAM, this is the constant value passed. */ 1044 uint64_t value; 1045 }; 1046 1047 parameter::parameter () 1048 : type (UNSET), is_param (false), value (0) {} 1049 1050 parameter::parameter (type_enum type_in, bool is_param_in, uint64_t value_in) 1051 : type (type_in), is_param (is_param_in), value (value_in) {} 1052 1053 bool 1054 operator == (const parameter ¶m1, const parameter ¶m2) 1055 { 1056 return (param1.type == param2.type 1057 && param1.is_param == param2.is_param 1058 && param1.value == param2.value); 1059 } 1060 1061 bool 1062 operator != (const parameter ¶m1, const parameter ¶m2) 1063 { 1064 return !operator == (param1, param2); 1065 } 1066 1067 /* Represents a routine that matches a partial rtx pattern, returning 1068 an ad-hoc enum value on success and -1 on failure. The routine can 1069 be used by any subroutine type. The match can be parameterized by 1070 things like mode, code and UNSPEC number. */ 1071 struct pattern_routine 1072 { 1073 /* The state that implements the pattern. */ 1074 state *s; 1075 1076 /* The deepest root position from which S can access all the rtxes it needs. 1077 This is NULL if the pattern doesn't need an rtx input, usually because 1078 all matching is done on operands[] instead. */ 1079 position *pos; 1080 1081 /* A unique identifier for the routine. */ 1082 unsigned int pattern_id; 1083 1084 /* True if the routine takes pnum_clobbers as argument. */ 1085 bool pnum_clobbers_p; 1086 1087 /* True if the routine takes the enclosing instruction as argument. */ 1088 bool insn_p; 1089 1090 /* The types of the other parameters to the routine, if any. */ 1091 auto_vec <parameter::type_enum, MAX_PATTERN_PARAMS> param_types; 1092 }; 1093 1094 /* All defined patterns. */ 1095 static vec <pattern_routine *> patterns; 1096 1097 /* Represents one use of a pattern routine. */ 1098 struct pattern_use 1099 { 1100 /* The pattern routine to use. */ 1101 pattern_routine *routine; 1102 1103 /* The values to pass as parameters. This vector has the same length 1104 as ROUTINE->PARAM_TYPES. */ 1105 auto_vec <parameter, MAX_PATTERN_PARAMS> params; 1106 }; 1107 1108 /* Represents a test performed by a decision. */ 1109 struct rtx_test 1110 { 1111 rtx_test (); 1112 1113 /* The types of test that can be performed. Most of them take as input 1114 an rtx X. Some also take as input a transition label LABEL; the others 1115 are booleans for which the transition label is always "true". 1116 1117 The order of the enum isn't important. */ 1118 enum kind_enum { 1119 /* Check GET_CODE (X) == LABEL. */ 1120 CODE, 1121 1122 /* Check GET_MODE (X) == LABEL. */ 1123 MODE, 1124 1125 /* Check REGNO (X) == LABEL. */ 1126 REGNO_FIELD, 1127 1128 /* Check known_eq (SUBREG_BYTE (X), LABEL). */ 1129 SUBREG_FIELD, 1130 1131 /* Check XINT (X, u.opno) == LABEL. */ 1132 INT_FIELD, 1133 1134 /* Check XWINT (X, u.opno) == LABEL. */ 1135 WIDE_INT_FIELD, 1136 1137 /* Check XVECLEN (X, 0) == LABEL. */ 1138 VECLEN, 1139 1140 /* Check peep2_current_count >= u.min_len. */ 1141 PEEP2_COUNT, 1142 1143 /* Check XVECLEN (X, 0) >= u.min_len. */ 1144 VECLEN_GE, 1145 1146 /* Check whether X is a cached const_int with value u.integer. */ 1147 SAVED_CONST_INT, 1148 1149 /* Check u.predicate.data (X, u.predicate.mode). */ 1150 PREDICATE, 1151 1152 /* Check rtx_equal_p (X, operands[u.opno]). */ 1153 DUPLICATE, 1154 1155 /* Check whether X matches pattern u.pattern. */ 1156 PATTERN, 1157 1158 /* Check whether pnum_clobbers is nonnull (RECOG only). */ 1159 HAVE_NUM_CLOBBERS, 1160 1161 /* Check whether general C test u.string holds. In general the condition 1162 needs access to "insn" and the full operand list. */ 1163 C_TEST, 1164 1165 /* Execute operands[u.opno] = X. (Always succeeds.) */ 1166 SET_OP, 1167 1168 /* Accept u.acceptance. Always succeeds for SUBPATTERN, RECOG and SPLIT. 1169 May fail for PEEPHOLE2 if the define_peephole2 C code executes FAIL. */ 1170 ACCEPT 1171 }; 1172 1173 /* The position of rtx X in the above description, relative to the 1174 incoming instruction "insn". The position is null if the test 1175 doesn't take an X as input. */ 1176 position *pos; 1177 1178 /* Which element of operands[] already contains POS, or -1 if no element 1179 is known to hold POS. */ 1180 int pos_operand; 1181 1182 /* The type of test and its parameters, as described above. */ 1183 kind_enum kind; 1184 union 1185 { 1186 int opno; 1187 int min_len; 1188 struct 1189 { 1190 bool is_param; 1191 int value; 1192 } integer; 1193 struct 1194 { 1195 const struct pred_data *data; 1196 /* True if the mode is taken from a machine_mode parameter 1197 to the routine rather than a constant machine_mode. If true, 1198 MODE is the number of the parameter (for an "i%d" format string), 1199 otherwise it is the mode itself. */ 1200 bool mode_is_param; 1201 unsigned int mode; 1202 } predicate; 1203 pattern_use *pattern; 1204 const char *string; 1205 acceptance_type acceptance; 1206 } u; 1207 1208 static rtx_test code (position *); 1209 static rtx_test mode (position *); 1210 static rtx_test regno_field (position *); 1211 static rtx_test subreg_field (position *); 1212 static rtx_test int_field (position *, int); 1213 static rtx_test wide_int_field (position *, int); 1214 static rtx_test veclen (position *); 1215 static rtx_test peep2_count (int); 1216 static rtx_test veclen_ge (position *, int); 1217 static rtx_test predicate (position *, const pred_data *, machine_mode); 1218 static rtx_test duplicate (position *, int); 1219 static rtx_test pattern (position *, pattern_use *); 1220 static rtx_test have_num_clobbers (); 1221 static rtx_test c_test (const char *); 1222 static rtx_test set_op (position *, int); 1223 static rtx_test accept (const acceptance_type &); 1224 1225 bool terminal_p () const; 1226 bool single_outcome_p () const; 1227 1228 private: 1229 rtx_test (position *, kind_enum); 1230 }; 1231 1232 rtx_test::rtx_test () {} 1233 1234 rtx_test::rtx_test (position *pos_in, kind_enum kind_in) 1235 : pos (pos_in), pos_operand (-1), kind (kind_in) {} 1236 1237 rtx_test 1238 rtx_test::code (position *pos) 1239 { 1240 return rtx_test (pos, rtx_test::CODE); 1241 } 1242 1243 rtx_test 1244 rtx_test::mode (position *pos) 1245 { 1246 return rtx_test (pos, rtx_test::MODE); 1247 } 1248 1249 rtx_test 1250 rtx_test::regno_field (position *pos) 1251 { 1252 rtx_test res (pos, rtx_test::REGNO_FIELD); 1253 return res; 1254 } 1255 1256 rtx_test 1257 rtx_test::subreg_field (position *pos) 1258 { 1259 rtx_test res (pos, rtx_test::SUBREG_FIELD); 1260 return res; 1261 } 1262 1263 rtx_test 1264 rtx_test::int_field (position *pos, int opno) 1265 { 1266 rtx_test res (pos, rtx_test::INT_FIELD); 1267 res.u.opno = opno; 1268 return res; 1269 } 1270 1271 rtx_test 1272 rtx_test::wide_int_field (position *pos, int opno) 1273 { 1274 rtx_test res (pos, rtx_test::WIDE_INT_FIELD); 1275 res.u.opno = opno; 1276 return res; 1277 } 1278 1279 rtx_test 1280 rtx_test::veclen (position *pos) 1281 { 1282 return rtx_test (pos, rtx_test::VECLEN); 1283 } 1284 1285 rtx_test 1286 rtx_test::peep2_count (int min_len) 1287 { 1288 rtx_test res (0, rtx_test::PEEP2_COUNT); 1289 res.u.min_len = min_len; 1290 return res; 1291 } 1292 1293 rtx_test 1294 rtx_test::veclen_ge (position *pos, int min_len) 1295 { 1296 rtx_test res (pos, rtx_test::VECLEN_GE); 1297 res.u.min_len = min_len; 1298 return res; 1299 } 1300 1301 rtx_test 1302 rtx_test::predicate (position *pos, const struct pred_data *data, 1303 machine_mode mode) 1304 { 1305 rtx_test res (pos, rtx_test::PREDICATE); 1306 res.u.predicate.data = data; 1307 res.u.predicate.mode_is_param = false; 1308 res.u.predicate.mode = mode; 1309 return res; 1310 } 1311 1312 rtx_test 1313 rtx_test::duplicate (position *pos, int opno) 1314 { 1315 rtx_test res (pos, rtx_test::DUPLICATE); 1316 res.u.opno = opno; 1317 return res; 1318 } 1319 1320 rtx_test 1321 rtx_test::pattern (position *pos, pattern_use *pattern) 1322 { 1323 rtx_test res (pos, rtx_test::PATTERN); 1324 res.u.pattern = pattern; 1325 return res; 1326 } 1327 1328 rtx_test 1329 rtx_test::have_num_clobbers () 1330 { 1331 return rtx_test (0, rtx_test::HAVE_NUM_CLOBBERS); 1332 } 1333 1334 rtx_test 1335 rtx_test::c_test (const char *string) 1336 { 1337 rtx_test res (0, rtx_test::C_TEST); 1338 res.u.string = string; 1339 return res; 1340 } 1341 1342 rtx_test 1343 rtx_test::set_op (position *pos, int opno) 1344 { 1345 rtx_test res (pos, rtx_test::SET_OP); 1346 res.u.opno = opno; 1347 return res; 1348 } 1349 1350 rtx_test 1351 rtx_test::accept (const acceptance_type &acceptance) 1352 { 1353 rtx_test res (0, rtx_test::ACCEPT); 1354 res.u.acceptance = acceptance; 1355 return res; 1356 } 1357 1358 /* Return true if the test represents an unconditionally successful match. */ 1359 1360 bool 1361 rtx_test::terminal_p () const 1362 { 1363 return kind == rtx_test::ACCEPT && u.acceptance.type != PEEPHOLE2; 1364 } 1365 1366 /* Return true if the test is a boolean that is always true. */ 1367 1368 bool 1369 rtx_test::single_outcome_p () const 1370 { 1371 return terminal_p () || kind == rtx_test::SET_OP; 1372 } 1373 1374 bool 1375 operator == (const rtx_test &a, const rtx_test &b) 1376 { 1377 if (a.pos != b.pos || a.kind != b.kind) 1378 return false; 1379 switch (a.kind) 1380 { 1381 case rtx_test::CODE: 1382 case rtx_test::MODE: 1383 case rtx_test::REGNO_FIELD: 1384 case rtx_test::SUBREG_FIELD: 1385 case rtx_test::VECLEN: 1386 case rtx_test::HAVE_NUM_CLOBBERS: 1387 return true; 1388 1389 case rtx_test::PEEP2_COUNT: 1390 case rtx_test::VECLEN_GE: 1391 return a.u.min_len == b.u.min_len; 1392 1393 case rtx_test::INT_FIELD: 1394 case rtx_test::WIDE_INT_FIELD: 1395 case rtx_test::DUPLICATE: 1396 case rtx_test::SET_OP: 1397 return a.u.opno == b.u.opno; 1398 1399 case rtx_test::SAVED_CONST_INT: 1400 return (a.u.integer.is_param == b.u.integer.is_param 1401 && a.u.integer.value == b.u.integer.value); 1402 1403 case rtx_test::PREDICATE: 1404 return (a.u.predicate.data == b.u.predicate.data 1405 && a.u.predicate.mode_is_param == b.u.predicate.mode_is_param 1406 && a.u.predicate.mode == b.u.predicate.mode); 1407 1408 case rtx_test::PATTERN: 1409 return (a.u.pattern->routine == b.u.pattern->routine 1410 && a.u.pattern->params == b.u.pattern->params); 1411 1412 case rtx_test::C_TEST: 1413 return strcmp (a.u.string, b.u.string) == 0; 1414 1415 case rtx_test::ACCEPT: 1416 return a.u.acceptance == b.u.acceptance; 1417 } 1418 gcc_unreachable (); 1419 } 1420 1421 bool 1422 operator != (const rtx_test &a, const rtx_test &b) 1423 { 1424 return !operator == (a, b); 1425 } 1426 1427 /* A simple set of transition labels. Most transitions have a singleton 1428 label, so try to make that case as efficient as possible. */ 1429 struct int_set : public auto_vec <uint64_t, 1> 1430 { 1431 typedef uint64_t *iterator; 1432 1433 int_set (); 1434 int_set (uint64_t); 1435 int_set (const int_set &); 1436 1437 int_set &operator = (const int_set &); 1438 1439 iterator begin (); 1440 iterator end (); 1441 }; 1442 1443 int_set::int_set () : auto_vec<uint64_t, 1> () {} 1444 1445 int_set::int_set (uint64_t label) : 1446 auto_vec<uint64_t, 1> () 1447 { 1448 safe_push (label); 1449 } 1450 1451 int_set::int_set (const int_set &other) : 1452 auto_vec<uint64_t, 1> () 1453 { 1454 safe_splice (other); 1455 } 1456 1457 int_set & 1458 int_set::operator = (const int_set &other) 1459 { 1460 truncate (0); 1461 safe_splice (other); 1462 return *this; 1463 } 1464 1465 int_set::iterator 1466 int_set::begin () 1467 { 1468 return address (); 1469 } 1470 1471 int_set::iterator 1472 int_set::end () 1473 { 1474 return address () + length (); 1475 } 1476 1477 bool 1478 operator == (const int_set &a, const int_set &b) 1479 { 1480 if (a.length () != b.length ()) 1481 return false; 1482 for (unsigned int i = 0; i < a.length (); ++i) 1483 if (a[i] != b[i]) 1484 return false; 1485 return true; 1486 } 1487 1488 bool 1489 operator != (const int_set &a, const int_set &b) 1490 { 1491 return !operator == (a, b); 1492 } 1493 1494 struct decision; 1495 1496 /* Represents a transition between states, dependent on the result of 1497 a test T. */ 1498 struct transition 1499 { 1500 transition (const int_set &, state *, bool); 1501 1502 void set_parent (list_head <transition> *); 1503 1504 /* Links to other transitions for T. Always null for boolean tests. */ 1505 transition *prev, *next; 1506 1507 /* The transition should be taken when T has one of these values. 1508 E.g. for rtx_test::CODE this is a set of codes, while for booleans like 1509 rtx_test::PREDICATE it is always a singleton "true". The labels are 1510 sorted in ascending order. */ 1511 int_set labels; 1512 1513 /* The source decision. */ 1514 decision *from; 1515 1516 /* The target state. */ 1517 state *to; 1518 1519 /* True if TO would function correctly even if TEST wasn't performed. 1520 E.g. it isn't necessary to check whether GET_MODE (x1) is SImode 1521 before calling register_operand (x1, SImode), since register_operand 1522 performs its own mode check. However, checking GET_MODE can be a cheap 1523 way of disambiguating SImode and DImode register operands. */ 1524 bool optional; 1525 1526 /* True if LABELS contains parameter numbers rather than constants. 1527 E.g. if this is true for a rtx_test::CODE, the label is the number 1528 of an rtx_code parameter rather than an rtx_code itself. 1529 LABELS is always a singleton when this variable is true. */ 1530 bool is_param; 1531 }; 1532 1533 /* Represents a test and the action that should be taken on the result. 1534 If a transition exists for the test outcome, the machine switches 1535 to the transition's target state. If no suitable transition exists, 1536 the machine either falls through to the next decision or, if there are no 1537 more decisions to try, fails the match. */ 1538 struct decision : list_head <transition> 1539 { 1540 decision (const rtx_test &); 1541 1542 void set_parent (list_head <decision> *s); 1543 bool if_statement_p (uint64_t * = 0) const; 1544 1545 /* The state to which this decision belongs. */ 1546 state *s; 1547 1548 /* Links to other decisions in the same state. */ 1549 decision *prev, *next; 1550 1551 /* The test to perform. */ 1552 rtx_test test; 1553 }; 1554 1555 /* Represents one machine state. For each state the machine tries a list 1556 of decisions, in order, and acts on the first match. It fails without 1557 further backtracking if no decisions match. */ 1558 struct state : list_head <decision> 1559 { 1560 void set_parent (list_head <state> *) {} 1561 }; 1562 1563 transition::transition (const int_set &labels_in, state *to_in, 1564 bool optional_in) 1565 : prev (0), next (0), labels (labels_in), from (0), to (to_in), 1566 optional (optional_in), is_param (false) {} 1567 1568 /* Set the source decision of the transition. */ 1569 1570 void 1571 transition::set_parent (list_head <transition> *from_in) 1572 { 1573 from = static_cast <decision *> (from_in); 1574 } 1575 1576 decision::decision (const rtx_test &test_in) 1577 : prev (0), next (0), test (test_in) {} 1578 1579 /* Set the state to which this decision belongs. */ 1580 1581 void 1582 decision::set_parent (list_head <decision> *s_in) 1583 { 1584 s = static_cast <state *> (s_in); 1585 } 1586 1587 /* Return true if the decision has a single transition with a single label. 1588 If so, return the label in *LABEL if nonnull. */ 1589 1590 inline bool 1591 decision::if_statement_p (uint64_t *label) const 1592 { 1593 if (singleton () && first->labels.length () == 1) 1594 { 1595 if (label) 1596 *label = first->labels[0]; 1597 return true; 1598 } 1599 return false; 1600 } 1601 1602 /* Add to FROM a decision that performs TEST and has a single transition 1603 TRANS. */ 1604 1605 static void 1606 add_decision (state *from, const rtx_test &test, transition *trans) 1607 { 1608 decision *d = new decision (test); 1609 from->push_back (d); 1610 d->push_back (trans); 1611 } 1612 1613 /* Add a transition from FROM to a new, empty state that is taken 1614 when TEST == LABELS. OPTIONAL says whether the new transition 1615 should be optional. Return the new state. */ 1616 1617 static state * 1618 add_decision (state *from, const rtx_test &test, int_set labels, bool optional) 1619 { 1620 state *to = new state; 1621 add_decision (from, test, new transition (labels, to, optional)); 1622 return to; 1623 } 1624 1625 /* Insert a decision before decisions R to make them dependent on 1626 TEST == LABELS. OPTIONAL says whether the new transition should be 1627 optional. */ 1628 1629 static decision * 1630 insert_decision_before (state::range r, const rtx_test &test, 1631 const int_set &labels, bool optional) 1632 { 1633 decision *newd = new decision (test); 1634 state *news = new state; 1635 newd->push_back (new transition (labels, news, optional)); 1636 r.start->s->replace (r, newd); 1637 news->push_back (r); 1638 return newd; 1639 } 1640 1641 /* Remove any optional transitions from S that turned out not to be useful. */ 1642 1643 static void 1644 collapse_optional_decisions (state *s) 1645 { 1646 decision *d = s->first; 1647 while (d) 1648 { 1649 decision *next = d->next; 1650 for (transition *trans = d->first; trans; trans = trans->next) 1651 collapse_optional_decisions (trans->to); 1652 /* A decision with a single optional transition doesn't help 1653 partition the potential matches and so is unlikely to be 1654 worthwhile. In particular, if the decision that performs the 1655 test is the last in the state, the best it could do is reject 1656 an invalid pattern slightly earlier. If instead the decision 1657 is not the last in the state, the condition it tests could hold 1658 even for the later decisions in the state. The best it can do 1659 is save work in some cases where only the later decisions can 1660 succeed. 1661 1662 In both cases the optional transition would add extra work to 1663 successful matches when the tested condition holds. */ 1664 if (transition *trans = d->singleton ()) 1665 if (trans->optional) 1666 s->replace (d, trans->to->release ()); 1667 d = next; 1668 } 1669 } 1670 1671 /* Try to squash several separate tests into simpler ones. */ 1672 1673 static void 1674 simplify_tests (state *s) 1675 { 1676 for (decision *d = s->first; d; d = d->next) 1677 { 1678 uint64_t label; 1679 /* Convert checks for GET_CODE (x) == CONST_INT and XWINT (x, 0) == N 1680 into checks for const_int_rtx[N'], if N is suitably small. */ 1681 if (d->test.kind == rtx_test::CODE 1682 && d->if_statement_p (&label) 1683 && label == CONST_INT) 1684 if (decision *second = d->first->to->singleton ()) 1685 if (d->test.pos == second->test.pos 1686 && second->test.kind == rtx_test::WIDE_INT_FIELD 1687 && second->test.u.opno == 0 1688 && second->if_statement_p (&label) 1689 && IN_RANGE (int64_t (label), 1690 -MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT)) 1691 { 1692 d->test.kind = rtx_test::SAVED_CONST_INT; 1693 d->test.u.integer.is_param = false; 1694 d->test.u.integer.value = label; 1695 d->replace (d->first, second->release ()); 1696 d->first->labels[0] = true; 1697 } 1698 /* If we have a CODE test followed by a PREDICATE test, rely on 1699 the predicate to test the code. 1700 1701 This case exists for match_operators. We initially treat the 1702 CODE test for a match_operator as non-optional so that we can 1703 safely move down to its operands. It may turn out that all 1704 paths that reach that code test require the same predicate 1705 to be true. cse_tests will then put the predicate test in 1706 series with the code test. */ 1707 if (d->test.kind == rtx_test::CODE) 1708 if (transition *trans = d->singleton ()) 1709 { 1710 state *s = trans->to; 1711 while (decision *d2 = s->singleton ()) 1712 { 1713 if (d->test.pos != d2->test.pos) 1714 break; 1715 transition *trans2 = d2->singleton (); 1716 if (!trans2) 1717 break; 1718 if (d2->test.kind == rtx_test::PREDICATE) 1719 { 1720 d->test = d2->test; 1721 trans->labels = int_set (true); 1722 s->replace (d2, trans2->to->release ()); 1723 break; 1724 } 1725 s = trans2->to; 1726 } 1727 } 1728 for (transition *trans = d->first; trans; trans = trans->next) 1729 simplify_tests (trans->to); 1730 } 1731 } 1732 1733 /* Return true if all successful returns passing through D require the 1734 condition tested by COMMON to be true. 1735 1736 When returning true, add all transitions like COMMON in D to WHERE. 1737 WHERE may contain a partial result on failure. */ 1738 1739 static bool 1740 common_test_p (decision *d, transition *common, vec <transition *> *where) 1741 { 1742 if (d->test.kind == rtx_test::ACCEPT) 1743 /* We found a successful return that didn't require COMMON. */ 1744 return false; 1745 if (d->test == common->from->test) 1746 { 1747 transition *trans = d->singleton (); 1748 if (!trans 1749 || trans->optional != common->optional 1750 || trans->labels != common->labels) 1751 return false; 1752 where->safe_push (trans); 1753 return true; 1754 } 1755 for (transition *trans = d->first; trans; trans = trans->next) 1756 for (decision *subd = trans->to->first; subd; subd = subd->next) 1757 if (!common_test_p (subd, common, where)) 1758 return false; 1759 return true; 1760 } 1761 1762 /* Indicates that we have tested GET_CODE (X) for a particular rtx X. */ 1763 const unsigned char TESTED_CODE = 1; 1764 1765 /* Indicates that we have tested XVECLEN (X, 0) for a particular rtx X. */ 1766 const unsigned char TESTED_VECLEN = 2; 1767 1768 /* Represents a set of conditions that are known to hold. */ 1769 struct known_conditions 1770 { 1771 /* A mask of TESTED_ values for each position, indexed by the position's 1772 id field. */ 1773 auto_vec <unsigned char> position_tests; 1774 1775 /* Index N says whether operands[N] has been set. */ 1776 auto_vec <bool> set_operands; 1777 1778 /* A guranteed lower bound on the value of peep2_current_count. */ 1779 int peep2_count; 1780 }; 1781 1782 /* Return true if TEST can safely be performed at D, where 1783 the conditions in KC hold. TEST is known to occur along the 1784 first path from D (i.e. always following the first transition 1785 of the first decision). Any intervening tests can be used as 1786 negative proof that hoisting isn't safe, but only KC can be used 1787 as positive proof. */ 1788 1789 static bool 1790 safe_to_hoist_p (decision *d, const rtx_test &test, known_conditions *kc) 1791 { 1792 switch (test.kind) 1793 { 1794 case rtx_test::C_TEST: 1795 /* In general, C tests require everything else to have been 1796 verified and all operands to have been set up. */ 1797 return false; 1798 1799 case rtx_test::ACCEPT: 1800 /* Don't accept something before all conditions have been tested. */ 1801 return false; 1802 1803 case rtx_test::PREDICATE: 1804 /* Don't move a predicate over a test for VECLEN_GE, since the 1805 predicate used in a match_parallel can legitimately expect the 1806 length to be checked first. */ 1807 for (decision *subd = d; 1808 subd->test != test; 1809 subd = subd->first->to->first) 1810 if (subd->test.pos == test.pos 1811 && subd->test.kind == rtx_test::VECLEN_GE) 1812 return false; 1813 goto any_rtx; 1814 1815 case rtx_test::DUPLICATE: 1816 /* Don't test for a match_dup until the associated operand has 1817 been set. */ 1818 if (!kc->set_operands[test.u.opno]) 1819 return false; 1820 goto any_rtx; 1821 1822 case rtx_test::CODE: 1823 case rtx_test::MODE: 1824 case rtx_test::SAVED_CONST_INT: 1825 case rtx_test::SET_OP: 1826 any_rtx: 1827 /* Check whether it is safe to access the rtx under test. */ 1828 switch (test.pos->type) 1829 { 1830 case POS_PEEP2_INSN: 1831 return test.pos->arg < kc->peep2_count; 1832 1833 case POS_XEXP: 1834 return kc->position_tests[test.pos->base->id] & TESTED_CODE; 1835 1836 case POS_XVECEXP0: 1837 return kc->position_tests[test.pos->base->id] & TESTED_VECLEN; 1838 } 1839 gcc_unreachable (); 1840 1841 case rtx_test::REGNO_FIELD: 1842 case rtx_test::SUBREG_FIELD: 1843 case rtx_test::INT_FIELD: 1844 case rtx_test::WIDE_INT_FIELD: 1845 case rtx_test::VECLEN: 1846 case rtx_test::VECLEN_GE: 1847 /* These tests access a specific part of an rtx, so are only safe 1848 once we know what the rtx is. */ 1849 return kc->position_tests[test.pos->id] & TESTED_CODE; 1850 1851 case rtx_test::PEEP2_COUNT: 1852 case rtx_test::HAVE_NUM_CLOBBERS: 1853 /* These tests can be performed anywhere. */ 1854 return true; 1855 1856 case rtx_test::PATTERN: 1857 gcc_unreachable (); 1858 } 1859 gcc_unreachable (); 1860 } 1861 1862 /* Look for a transition that is taken by all successful returns from a range 1863 of decisions starting at OUTER and that would be better performed by 1864 OUTER's state instead. On success, store all instances of that transition 1865 in WHERE and return the last decision in the range. The range could 1866 just be OUTER, or it could include later decisions as well. 1867 1868 WITH_POSITION_P is true if only tests with position POS should be tried, 1869 false if any test should be tried. WORTHWHILE_SINGLE_P is true if the 1870 result is useful even when the range contains just a single decision 1871 with a single transition. KC are the conditions that are known to 1872 hold at OUTER. */ 1873 1874 static decision * 1875 find_common_test (decision *outer, bool with_position_p, 1876 position *pos, bool worthwhile_single_p, 1877 known_conditions *kc, vec <transition *> *where) 1878 { 1879 /* After this, WORTHWHILE_SINGLE_P indicates whether a range that contains 1880 just a single decision is useful, regardless of the number of 1881 transitions it has. */ 1882 if (!outer->singleton ()) 1883 worthwhile_single_p = true; 1884 /* Quick exit if we don't have enough decisions to form a worthwhile 1885 range. */ 1886 if (!worthwhile_single_p && !outer->next) 1887 return 0; 1888 /* Follow the first chain down, as one example of a path that needs 1889 to contain the common test. */ 1890 for (decision *d = outer; d; d = d->first->to->first) 1891 { 1892 transition *trans = d->singleton (); 1893 if (trans 1894 && (!with_position_p || d->test.pos == pos) 1895 && safe_to_hoist_p (outer, d->test, kc)) 1896 { 1897 if (common_test_p (outer, trans, where)) 1898 { 1899 if (!outer->next) 1900 /* We checked above whether the move is worthwhile. */ 1901 return outer; 1902 /* See how many decisions in OUTER's chain could reuse 1903 the same test. */ 1904 decision *outer_end = outer; 1905 do 1906 { 1907 unsigned int length = where->length (); 1908 if (!common_test_p (outer_end->next, trans, where)) 1909 { 1910 where->truncate (length); 1911 break; 1912 } 1913 outer_end = outer_end->next; 1914 } 1915 while (outer_end->next); 1916 /* It is worth moving TRANS if it can be shared by more than 1917 one decision. */ 1918 if (outer_end != outer || worthwhile_single_p) 1919 return outer_end; 1920 } 1921 where->truncate (0); 1922 } 1923 } 1924 return 0; 1925 } 1926 1927 /* Try to promote common subtests in S to a single, shared decision. 1928 Also try to bunch tests for the same position together. POS is the 1929 position of the rtx tested before reaching S. KC are the conditions 1930 that are known to hold on entry to S. */ 1931 1932 static void 1933 cse_tests (position *pos, state *s, known_conditions *kc) 1934 { 1935 for (decision *d = s->first; d; d = d->next) 1936 { 1937 auto_vec <transition *, 16> where; 1938 if (d->test.pos) 1939 { 1940 /* Try to find conditions that don't depend on a particular rtx, 1941 such as pnum_clobbers != NULL or peep2_current_count >= X. 1942 It's usually better to check these conditions as soon as 1943 possible, so the change is worthwhile even if there is 1944 only one copy of the test. */ 1945 decision *endd = find_common_test (d, true, 0, true, kc, &where); 1946 if (!endd && d->test.pos != pos) 1947 /* Try to find other conditions related to position POS 1948 before moving to the new position. Again, this is 1949 worthwhile even if there is only one copy of the test, 1950 since it means that fewer position variables are live 1951 at a given time. */ 1952 endd = find_common_test (d, true, pos, true, kc, &where); 1953 if (!endd) 1954 /* Try to find any condition that is used more than once. */ 1955 endd = find_common_test (d, false, 0, false, kc, &where); 1956 if (endd) 1957 { 1958 transition *common = where[0]; 1959 /* Replace [D, ENDD] with a test like COMMON. We'll recurse 1960 on the common test and see the original D again next time. */ 1961 d = insert_decision_before (state::range (d, endd), 1962 common->from->test, 1963 common->labels, 1964 common->optional); 1965 /* Remove the old tests. */ 1966 while (!where.is_empty ()) 1967 { 1968 transition *trans = where.pop (); 1969 trans->from->s->replace (trans->from, trans->to->release ()); 1970 } 1971 } 1972 } 1973 1974 /* Make sure that safe_to_hoist_p isn't being overly conservative. 1975 It should realize that D's test is safe in the current 1976 environment. */ 1977 gcc_assert (d->test.kind == rtx_test::C_TEST 1978 || d->test.kind == rtx_test::ACCEPT 1979 || safe_to_hoist_p (d, d->test, kc)); 1980 1981 /* D won't be changed any further by the current optimization. 1982 Recurse with the state temporarily updated to include D. */ 1983 int prev = 0; 1984 switch (d->test.kind) 1985 { 1986 case rtx_test::CODE: 1987 prev = kc->position_tests[d->test.pos->id]; 1988 kc->position_tests[d->test.pos->id] |= TESTED_CODE; 1989 break; 1990 1991 case rtx_test::VECLEN: 1992 case rtx_test::VECLEN_GE: 1993 prev = kc->position_tests[d->test.pos->id]; 1994 kc->position_tests[d->test.pos->id] |= TESTED_VECLEN; 1995 break; 1996 1997 case rtx_test::SET_OP: 1998 prev = kc->set_operands[d->test.u.opno]; 1999 gcc_assert (!prev); 2000 kc->set_operands[d->test.u.opno] = true; 2001 break; 2002 2003 case rtx_test::PEEP2_COUNT: 2004 prev = kc->peep2_count; 2005 kc->peep2_count = MAX (prev, d->test.u.min_len); 2006 break; 2007 2008 default: 2009 break; 2010 } 2011 for (transition *trans = d->first; trans; trans = trans->next) 2012 cse_tests (d->test.pos ? d->test.pos : pos, trans->to, kc); 2013 switch (d->test.kind) 2014 { 2015 case rtx_test::CODE: 2016 case rtx_test::VECLEN: 2017 case rtx_test::VECLEN_GE: 2018 kc->position_tests[d->test.pos->id] = prev; 2019 break; 2020 2021 case rtx_test::SET_OP: 2022 kc->set_operands[d->test.u.opno] = prev; 2023 break; 2024 2025 case rtx_test::PEEP2_COUNT: 2026 kc->peep2_count = prev; 2027 break; 2028 2029 default: 2030 break; 2031 } 2032 } 2033 } 2034 2035 /* Return the type of value that can be used to parameterize test KIND, 2036 or parameter::UNSET if none. */ 2037 2038 parameter::type_enum 2039 transition_parameter_type (rtx_test::kind_enum kind) 2040 { 2041 switch (kind) 2042 { 2043 case rtx_test::CODE: 2044 return parameter::CODE; 2045 2046 case rtx_test::MODE: 2047 return parameter::MODE; 2048 2049 case rtx_test::REGNO_FIELD: 2050 case rtx_test::SUBREG_FIELD: 2051 return parameter::UINT; 2052 2053 case rtx_test::INT_FIELD: 2054 case rtx_test::VECLEN: 2055 case rtx_test::PATTERN: 2056 return parameter::INT; 2057 2058 case rtx_test::WIDE_INT_FIELD: 2059 return parameter::WIDE_INT; 2060 2061 case rtx_test::PEEP2_COUNT: 2062 case rtx_test::VECLEN_GE: 2063 case rtx_test::SAVED_CONST_INT: 2064 case rtx_test::PREDICATE: 2065 case rtx_test::DUPLICATE: 2066 case rtx_test::HAVE_NUM_CLOBBERS: 2067 case rtx_test::C_TEST: 2068 case rtx_test::SET_OP: 2069 case rtx_test::ACCEPT: 2070 return parameter::UNSET; 2071 } 2072 gcc_unreachable (); 2073 } 2074 2075 /* Initialize the pos_operand fields of each state reachable from S. 2076 If OPERAND_POS[ID] >= 0, the position with id ID is stored in 2077 operands[OPERAND_POS[ID]] on entry to S. */ 2078 2079 static void 2080 find_operand_positions (state *s, vec <int> &operand_pos) 2081 { 2082 for (decision *d = s->first; d; d = d->next) 2083 { 2084 int this_operand = (d->test.pos ? operand_pos[d->test.pos->id] : -1); 2085 if (this_operand >= 0) 2086 d->test.pos_operand = this_operand; 2087 if (d->test.kind == rtx_test::SET_OP) 2088 operand_pos[d->test.pos->id] = d->test.u.opno; 2089 for (transition *trans = d->first; trans; trans = trans->next) 2090 find_operand_positions (trans->to, operand_pos); 2091 if (d->test.kind == rtx_test::SET_OP) 2092 operand_pos[d->test.pos->id] = this_operand; 2093 } 2094 } 2095 2096 /* Statistics about a matching routine. */ 2097 struct stats 2098 { 2099 stats (); 2100 2101 /* The total number of decisions in the routine, excluding trivial 2102 ones that never fail. */ 2103 unsigned int num_decisions; 2104 2105 /* The number of non-trivial decisions on the longest path through 2106 the routine, and the return value that contributes most to that 2107 long path. */ 2108 unsigned int longest_path; 2109 int longest_path_code; 2110 2111 /* The maximum number of times that a single call to the routine 2112 can backtrack, and the value returned at the end of that path. 2113 "Backtracking" here means failing one decision in state and 2114 going onto to the next. */ 2115 unsigned int longest_backtrack; 2116 int longest_backtrack_code; 2117 }; 2118 2119 stats::stats () 2120 : num_decisions (0), longest_path (0), longest_path_code (-1), 2121 longest_backtrack (0), longest_backtrack_code (-1) {} 2122 2123 /* Return statistics about S. */ 2124 2125 static stats 2126 get_stats (state *s) 2127 { 2128 stats for_s; 2129 unsigned int longest_path = 0; 2130 for (decision *d = s->first; d; d = d->next) 2131 { 2132 /* Work out the statistics for D. */ 2133 stats for_d; 2134 for (transition *trans = d->first; trans; trans = trans->next) 2135 { 2136 stats for_trans = get_stats (trans->to); 2137 for_d.num_decisions += for_trans.num_decisions; 2138 /* Each transition is mutually-exclusive, so just pick the 2139 longest of the individual paths. */ 2140 if (for_d.longest_path <= for_trans.longest_path) 2141 { 2142 for_d.longest_path = for_trans.longest_path; 2143 for_d.longest_path_code = for_trans.longest_path_code; 2144 } 2145 /* Likewise for backtracking. */ 2146 if (for_d.longest_backtrack <= for_trans.longest_backtrack) 2147 { 2148 for_d.longest_backtrack = for_trans.longest_backtrack; 2149 for_d.longest_backtrack_code = for_trans.longest_backtrack_code; 2150 } 2151 } 2152 2153 /* Account for D's test in its statistics. */ 2154 if (!d->test.single_outcome_p ()) 2155 { 2156 for_d.num_decisions += 1; 2157 for_d.longest_path += 1; 2158 } 2159 if (d->test.kind == rtx_test::ACCEPT) 2160 { 2161 for_d.longest_path_code = d->test.u.acceptance.u.full.code; 2162 for_d.longest_backtrack_code = d->test.u.acceptance.u.full.code; 2163 } 2164 2165 /* Keep a running count of the number of backtracks. */ 2166 if (d->prev) 2167 for_s.longest_backtrack += 1; 2168 2169 /* Accumulate D's statistics into S's. */ 2170 for_s.num_decisions += for_d.num_decisions; 2171 for_s.longest_path += for_d.longest_path; 2172 for_s.longest_backtrack += for_d.longest_backtrack; 2173 2174 /* Use the code from the decision with the longest individual path, 2175 since that's more likely to be useful if trying to make the 2176 path shorter. In the event of a tie, pick the later decision, 2177 since that's closer to the end of the path. */ 2178 if (longest_path <= for_d.longest_path) 2179 { 2180 longest_path = for_d.longest_path; 2181 for_s.longest_path_code = for_d.longest_path_code; 2182 } 2183 2184 /* Later decisions in a state are necessarily in a longer backtrack 2185 than earlier decisions. */ 2186 for_s.longest_backtrack_code = for_d.longest_backtrack_code; 2187 } 2188 return for_s; 2189 } 2190 2191 /* Optimize ROOT. Use TYPE to describe ROOT in status messages. */ 2192 2193 static void 2194 optimize_subroutine_group (const char *type, state *root) 2195 { 2196 /* Remove optional transitions that turned out not to be worthwhile. */ 2197 if (collapse_optional_decisions_p) 2198 collapse_optional_decisions (root); 2199 2200 /* Try to remove duplicated tests and to rearrange tests into a more 2201 logical order. */ 2202 if (cse_tests_p) 2203 { 2204 known_conditions kc; 2205 kc.position_tests.safe_grow_cleared (num_positions); 2206 kc.set_operands.safe_grow_cleared (num_operands); 2207 kc.peep2_count = 1; 2208 cse_tests (&root_pos, root, &kc); 2209 } 2210 2211 /* Try to simplify two or more tests into one. */ 2212 if (simplify_tests_p) 2213 simplify_tests (root); 2214 2215 /* Try to use operands[] instead of xN variables. */ 2216 if (use_operand_variables_p) 2217 { 2218 auto_vec <int> operand_pos (num_positions); 2219 for (unsigned int i = 0; i < num_positions; ++i) 2220 operand_pos.quick_push (-1); 2221 find_operand_positions (root, operand_pos); 2222 } 2223 2224 /* Print a summary of the new state. */ 2225 stats st = get_stats (root); 2226 fprintf (stderr, "Statistics for %s:\n", type); 2227 fprintf (stderr, " Number of decisions: %6d\n", st.num_decisions); 2228 fprintf (stderr, " longest path: %6d (code: %6d)\n", 2229 st.longest_path, st.longest_path_code); 2230 fprintf (stderr, " longest backtrack: %6d (code: %6d)\n", 2231 st.longest_backtrack, st.longest_backtrack_code); 2232 } 2233 2234 struct merge_pattern_info; 2235 2236 /* Represents a transition from one pattern to another. */ 2237 struct merge_pattern_transition 2238 { 2239 merge_pattern_transition (merge_pattern_info *); 2240 2241 /* The target pattern. */ 2242 merge_pattern_info *to; 2243 2244 /* The parameters that the source pattern passes to the target pattern. 2245 "parameter (TYPE, true, I)" represents parameter I of the source 2246 pattern. */ 2247 auto_vec <parameter, MAX_PATTERN_PARAMS> params; 2248 }; 2249 2250 merge_pattern_transition::merge_pattern_transition (merge_pattern_info *to_in) 2251 : to (to_in) 2252 { 2253 } 2254 2255 /* Represents a pattern that can might match several states. The pattern 2256 may replace parts of the test with a parameter value. It may also 2257 replace transition labels with parameters. */ 2258 struct merge_pattern_info 2259 { 2260 merge_pattern_info (unsigned int); 2261 2262 /* If PARAM_TEST_P, the state's singleton test should be generalized 2263 to use the runtime value of PARAMS[PARAM_TEST]. */ 2264 unsigned int param_test : 8; 2265 2266 /* If PARAM_TRANSITION_P, the state's single transition label should 2267 be replaced by the runtime value of PARAMS[PARAM_TRANSITION]. */ 2268 unsigned int param_transition : 8; 2269 2270 /* True if we have decided to generalize the root decision's test, 2271 as per PARAM_TEST. */ 2272 unsigned int param_test_p : 1; 2273 2274 /* Likewise for the root decision's transition, as per PARAM_TRANSITION. */ 2275 unsigned int param_transition_p : 1; 2276 2277 /* True if the contents of the structure are completely filled in. */ 2278 unsigned int complete_p : 1; 2279 2280 /* The number of pseudo-statements in the pattern. Used to decide 2281 whether it's big enough to break out into a subroutine. */ 2282 unsigned int num_statements; 2283 2284 /* The number of states that use this pattern. */ 2285 unsigned int num_users; 2286 2287 /* The number of distinct success values that the pattern returns. */ 2288 unsigned int num_results; 2289 2290 /* This array has one element for each runtime parameter to the pattern. 2291 PARAMS[I] gives the default value of parameter I, which is always 2292 constant. 2293 2294 These default parameters are used in cases where we match the 2295 pattern against some state S1, then add more parameters while 2296 matching against some state S2. S1 is then left passing fewer 2297 parameters than S2. The array gives us enough informatino to 2298 construct a full parameter list for S1 (see update_parameters). 2299 2300 If we decide to create a subroutine for this pattern, 2301 PARAMS[I].type determines the C type of parameter I. */ 2302 auto_vec <parameter, MAX_PATTERN_PARAMS> params; 2303 2304 /* All states that match this pattern must have the same number of 2305 transitions. TRANSITIONS[I] describes the subpattern for transition 2306 number I; it is null if transition I represents a successful return 2307 from the pattern. */ 2308 auto_vec <merge_pattern_transition *, 1> transitions; 2309 2310 /* The routine associated with the pattern, or null if we haven't generated 2311 one yet. */ 2312 pattern_routine *routine; 2313 }; 2314 2315 merge_pattern_info::merge_pattern_info (unsigned int num_transitions) 2316 : param_test (0), 2317 param_transition (0), 2318 param_test_p (false), 2319 param_transition_p (false), 2320 complete_p (false), 2321 num_statements (0), 2322 num_users (0), 2323 num_results (0), 2324 routine (0) 2325 { 2326 transitions.safe_grow_cleared (num_transitions); 2327 } 2328 2329 /* Describes one way of matching a particular state to a particular 2330 pattern. */ 2331 struct merge_state_result 2332 { 2333 merge_state_result (merge_pattern_info *, position *, merge_state_result *); 2334 2335 /* A pattern that matches the state. */ 2336 merge_pattern_info *pattern; 2337 2338 /* If we decide to use this match and create a subroutine for PATTERN, 2339 the state should pass the rtx at position ROOT to the pattern's 2340 rtx parameter. A null root means that the pattern doesn't need 2341 an rtx parameter; all the rtxes it matches come from elsewhere. */ 2342 position *root; 2343 2344 /* The parameters that should be passed to PATTERN for this state. 2345 If the array is shorter than PATTERN->params, the missing entries 2346 should be taken from the corresponding element of PATTERN->params. */ 2347 auto_vec <parameter, MAX_PATTERN_PARAMS> params; 2348 2349 /* An earlier match for the same state, or null if none. Patterns 2350 matched by earlier entries are smaller than PATTERN. */ 2351 merge_state_result *prev; 2352 }; 2353 2354 merge_state_result::merge_state_result (merge_pattern_info *pattern_in, 2355 position *root_in, 2356 merge_state_result *prev_in) 2357 : pattern (pattern_in), root (root_in), prev (prev_in) 2358 {} 2359 2360 /* Information about a state, used while trying to match it against 2361 a pattern. */ 2362 struct merge_state_info 2363 { 2364 merge_state_info (state *); 2365 2366 /* The state itself. */ 2367 state *s; 2368 2369 /* Index I gives information about the target of transition I. */ 2370 merge_state_info *to_states; 2371 2372 /* The number of transitions in S. */ 2373 unsigned int num_transitions; 2374 2375 /* True if the state has been deleted in favor of a call to a 2376 pattern routine. */ 2377 bool merged_p; 2378 2379 /* The previous state that might be a merge candidate for S, or null 2380 if no previous states could be merged with S. */ 2381 merge_state_info *prev_same_test; 2382 2383 /* A list of pattern matches for this state. */ 2384 merge_state_result *res; 2385 }; 2386 2387 merge_state_info::merge_state_info (state *s_in) 2388 : s (s_in), 2389 to_states (0), 2390 num_transitions (0), 2391 merged_p (false), 2392 prev_same_test (0), 2393 res (0) {} 2394 2395 /* True if PAT would be useful as a subroutine. */ 2396 2397 static bool 2398 useful_pattern_p (merge_pattern_info *pat) 2399 { 2400 return pat->num_statements >= MIN_COMBINE_COST; 2401 } 2402 2403 /* PAT2 is a subpattern of PAT1. Return true if PAT2 should be inlined 2404 into PAT1's C routine. */ 2405 2406 static bool 2407 same_pattern_p (merge_pattern_info *pat1, merge_pattern_info *pat2) 2408 { 2409 return pat1->num_users == pat2->num_users || !useful_pattern_p (pat2); 2410 } 2411 2412 /* PAT was previously matched against SINFO based on tentative matches 2413 for the target states of SINFO's state. Return true if the match 2414 still holds; that is, if the target states of SINFO's state still 2415 match the corresponding transitions of PAT. */ 2416 2417 static bool 2418 valid_result_p (merge_pattern_info *pat, merge_state_info *sinfo) 2419 { 2420 for (unsigned int j = 0; j < sinfo->num_transitions; ++j) 2421 if (merge_pattern_transition *ptrans = pat->transitions[j]) 2422 { 2423 merge_state_result *to_res = sinfo->to_states[j].res; 2424 if (!to_res || to_res->pattern != ptrans->to) 2425 return false; 2426 } 2427 return true; 2428 } 2429 2430 /* Remove any matches that are no longer valid from the head of SINFO's 2431 list of matches. */ 2432 2433 static void 2434 prune_invalid_results (merge_state_info *sinfo) 2435 { 2436 while (sinfo->res && !valid_result_p (sinfo->res->pattern, sinfo)) 2437 { 2438 sinfo->res = sinfo->res->prev; 2439 gcc_assert (sinfo->res); 2440 } 2441 } 2442 2443 /* Return true if PAT represents the biggest posssible match for SINFO; 2444 that is, if the next action of SINFO's state on return from PAT will 2445 be something that cannot be merged with any other state. */ 2446 2447 static bool 2448 complete_result_p (merge_pattern_info *pat, merge_state_info *sinfo) 2449 { 2450 for (unsigned int j = 0; j < sinfo->num_transitions; ++j) 2451 if (sinfo->to_states[j].res && !pat->transitions[j]) 2452 return false; 2453 return true; 2454 } 2455 2456 /* Update TO for any parameters that have been added to FROM since TO 2457 was last set. The extra parameters in FROM will be constants or 2458 instructions to duplicate earlier parameters. */ 2459 2460 static void 2461 update_parameters (vec <parameter> &to, const vec <parameter> &from) 2462 { 2463 for (unsigned int i = to.length (); i < from.length (); ++i) 2464 to.quick_push (from[i]); 2465 } 2466 2467 /* Return true if A and B can be tested by a single test. If the test 2468 can be parameterised, store the parameter value for A in *PARAMA and 2469 the parameter value for B in *PARAMB, otherwise leave PARAMA and 2470 PARAMB alone. */ 2471 2472 static bool 2473 compatible_tests_p (const rtx_test &a, const rtx_test &b, 2474 parameter *parama, parameter *paramb) 2475 { 2476 if (a.kind != b.kind) 2477 return false; 2478 switch (a.kind) 2479 { 2480 case rtx_test::PREDICATE: 2481 if (a.u.predicate.data != b.u.predicate.data) 2482 return false; 2483 *parama = parameter (parameter::MODE, false, a.u.predicate.mode); 2484 *paramb = parameter (parameter::MODE, false, b.u.predicate.mode); 2485 return true; 2486 2487 case rtx_test::SAVED_CONST_INT: 2488 *parama = parameter (parameter::INT, false, a.u.integer.value); 2489 *paramb = parameter (parameter::INT, false, b.u.integer.value); 2490 return true; 2491 2492 default: 2493 return a == b; 2494 } 2495 } 2496 2497 /* PARAMS is an array of the parameters that a state is going to pass 2498 to a pattern routine. It is still incomplete; index I has a kind of 2499 parameter::UNSET if we don't yet know what the state will pass 2500 as parameter I. Try to make parameter ID equal VALUE, returning 2501 true on success. */ 2502 2503 static bool 2504 set_parameter (vec <parameter> ¶ms, unsigned int id, 2505 const parameter &value) 2506 { 2507 if (params[id].type == parameter::UNSET) 2508 { 2509 if (force_unique_params_p) 2510 for (unsigned int i = 0; i < params.length (); ++i) 2511 if (params[i] == value) 2512 return false; 2513 params[id] = value; 2514 return true; 2515 } 2516 return params[id] == value; 2517 } 2518 2519 /* PARAMS2 is the "params" array for a pattern and PARAMS1 is the 2520 set of parameters that a particular state is going to pass to 2521 that pattern. 2522 2523 Try to extend PARAMS1 and PARAMS2 so that there is a parameter 2524 that is equal to PARAM1 for the state and has a default value of 2525 PARAM2. Parameters beginning at START were added as part of the 2526 same match and so may be reused. */ 2527 2528 static bool 2529 add_parameter (vec <parameter> ¶ms1, vec <parameter> ¶ms2, 2530 const parameter ¶m1, const parameter ¶m2, 2531 unsigned int start, unsigned int *res) 2532 { 2533 gcc_assert (params1.length () == params2.length ()); 2534 gcc_assert (!param1.is_param && !param2.is_param); 2535 2536 for (unsigned int i = start; i < params2.length (); ++i) 2537 if (params1[i] == param1 && params2[i] == param2) 2538 { 2539 *res = i; 2540 return true; 2541 } 2542 2543 if (force_unique_params_p) 2544 for (unsigned int i = 0; i < params2.length (); ++i) 2545 if (params1[i] == param1 || params2[i] == param2) 2546 return false; 2547 2548 if (params2.length () >= MAX_PATTERN_PARAMS) 2549 return false; 2550 2551 *res = params2.length (); 2552 params1.quick_push (param1); 2553 params2.quick_push (param2); 2554 return true; 2555 } 2556 2557 /* If *ROOTA is nonnull, return true if the same sequence of steps are 2558 required to reach A from *ROOTA as to reach B from ROOTB. If *ROOTA 2559 is null, update it if necessary in order to make the condition hold. */ 2560 2561 static bool 2562 merge_relative_positions (position **roota, position *a, 2563 position *rootb, position *b) 2564 { 2565 if (!relative_patterns_p) 2566 { 2567 if (a != b) 2568 return false; 2569 if (!*roota) 2570 { 2571 *roota = rootb; 2572 return true; 2573 } 2574 return *roota == rootb; 2575 } 2576 /* If B does not belong to the same instruction as ROOTB, we don't 2577 start with ROOTB but instead start with a call to peep2_next_insn. 2578 In that case the sequences for B and A are identical iff B and A 2579 are themselves identical. */ 2580 if (rootb->insn_id != b->insn_id) 2581 return a == b; 2582 while (rootb != b) 2583 { 2584 if (!a || b->type != a->type || b->arg != a->arg) 2585 return false; 2586 b = b->base; 2587 a = a->base; 2588 } 2589 if (!*roota) 2590 *roota = a; 2591 return *roota == a; 2592 } 2593 2594 /* A hasher of states that treats two states as "equal" if they might be 2595 merged (but trying to be more discriminating than "return true"). */ 2596 struct test_pattern_hasher : nofree_ptr_hash <merge_state_info> 2597 { 2598 static inline hashval_t hash (const value_type &); 2599 static inline bool equal (const value_type &, const compare_type &); 2600 }; 2601 2602 hashval_t 2603 test_pattern_hasher::hash (merge_state_info *const &sinfo) 2604 { 2605 inchash::hash h; 2606 decision *d = sinfo->s->singleton (); 2607 h.add_int (d->test.pos_operand + 1); 2608 if (!relative_patterns_p) 2609 h.add_int (d->test.pos ? d->test.pos->id + 1 : 0); 2610 h.add_int (d->test.kind); 2611 h.add_int (sinfo->num_transitions); 2612 return h.end (); 2613 } 2614 2615 bool 2616 test_pattern_hasher::equal (merge_state_info *const &sinfo1, 2617 merge_state_info *const &sinfo2) 2618 { 2619 decision *d1 = sinfo1->s->singleton (); 2620 decision *d2 = sinfo2->s->singleton (); 2621 gcc_assert (d1 && d2); 2622 2623 parameter new_param1, new_param2; 2624 return (d1->test.pos_operand == d2->test.pos_operand 2625 && (relative_patterns_p || d1->test.pos == d2->test.pos) 2626 && compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2) 2627 && sinfo1->num_transitions == sinfo2->num_transitions); 2628 } 2629 2630 /* Try to make the state described by SINFO1 use the same pattern as the 2631 state described by SINFO2. Return true on success. 2632 2633 SINFO1 and SINFO2 are known to have the same hash value. */ 2634 2635 static bool 2636 merge_patterns (merge_state_info *sinfo1, merge_state_info *sinfo2) 2637 { 2638 merge_state_result *res2 = sinfo2->res; 2639 merge_pattern_info *pat = res2->pattern; 2640 2641 /* Write to temporary arrays while matching, in case we have to abort 2642 half way through. */ 2643 auto_vec <parameter, MAX_PATTERN_PARAMS> params1; 2644 auto_vec <parameter, MAX_PATTERN_PARAMS> params2; 2645 params1.quick_grow_cleared (pat->params.length ()); 2646 params2.splice (pat->params); 2647 unsigned int start_param = params2.length (); 2648 2649 /* An array for recording changes to PAT->transitions[?].params. 2650 All changes involve replacing a constant parameter with some 2651 PAT->params[N], where N is the second element of the pending_param. */ 2652 typedef std::pair <parameter *, unsigned int> pending_param; 2653 auto_vec <pending_param, 32> pending_params; 2654 2655 decision *d1 = sinfo1->s->singleton (); 2656 decision *d2 = sinfo2->s->singleton (); 2657 gcc_assert (d1 && d2); 2658 2659 /* If D2 tests a position, SINFO1's root relative to D1 is the same 2660 as SINFO2's root relative to D2. */ 2661 position *root1 = 0; 2662 position *root2 = res2->root; 2663 if (d2->test.pos_operand < 0 2664 && d1->test.pos 2665 && !merge_relative_positions (&root1, d1->test.pos, 2666 root2, d2->test.pos)) 2667 return false; 2668 2669 /* Check whether the patterns have the same shape. */ 2670 unsigned int num_transitions = sinfo1->num_transitions; 2671 gcc_assert (num_transitions == sinfo2->num_transitions); 2672 for (unsigned int i = 0; i < num_transitions; ++i) 2673 if (merge_pattern_transition *ptrans = pat->transitions[i]) 2674 { 2675 merge_state_result *to1_res = sinfo1->to_states[i].res; 2676 merge_state_result *to2_res = sinfo2->to_states[i].res; 2677 merge_pattern_info *to_pat = ptrans->to; 2678 gcc_assert (to2_res && to2_res->pattern == to_pat); 2679 if (!to1_res || to1_res->pattern != to_pat) 2680 return false; 2681 if (to2_res->root 2682 && !merge_relative_positions (&root1, to1_res->root, 2683 root2, to2_res->root)) 2684 return false; 2685 /* Match the parameters that TO1_RES passes to TO_PAT with the 2686 parameters that PAT passes to TO_PAT. */ 2687 update_parameters (to1_res->params, to_pat->params); 2688 for (unsigned int j = 0; j < to1_res->params.length (); ++j) 2689 { 2690 const parameter ¶m1 = to1_res->params[j]; 2691 const parameter ¶m2 = ptrans->params[j]; 2692 gcc_assert (!param1.is_param); 2693 if (param2.is_param) 2694 { 2695 if (!set_parameter (params1, param2.value, param1)) 2696 return false; 2697 } 2698 else if (param1 != param2) 2699 { 2700 unsigned int id; 2701 if (!add_parameter (params1, params2, 2702 param1, param2, start_param, &id)) 2703 return false; 2704 /* Record that PAT should now pass parameter ID to TO_PAT, 2705 instead of the current contents of *PARAM2. We only 2706 make the change if the rest of the match succeeds. */ 2707 pending_params.safe_push 2708 (pending_param (&ptrans->params[j], id)); 2709 } 2710 } 2711 } 2712 2713 unsigned int param_test = pat->param_test; 2714 unsigned int param_transition = pat->param_transition; 2715 bool param_test_p = pat->param_test_p; 2716 bool param_transition_p = pat->param_transition_p; 2717 2718 /* If the tests don't match exactly, try to parameterize them. */ 2719 parameter new_param1, new_param2; 2720 if (!compatible_tests_p (d1->test, d2->test, &new_param1, &new_param2)) 2721 gcc_unreachable (); 2722 if (new_param1.type != parameter::UNSET) 2723 { 2724 /* If the test has not already been parameterized, all existing 2725 matches use constant NEW_PARAM2. */ 2726 if (param_test_p) 2727 { 2728 if (!set_parameter (params1, param_test, new_param1)) 2729 return false; 2730 } 2731 else if (new_param1 != new_param2) 2732 { 2733 if (!add_parameter (params1, params2, new_param1, new_param2, 2734 start_param, ¶m_test)) 2735 return false; 2736 param_test_p = true; 2737 } 2738 } 2739 2740 /* Match the transitions. */ 2741 transition *trans1 = d1->first; 2742 transition *trans2 = d2->first; 2743 for (unsigned int i = 0; i < num_transitions; ++i) 2744 { 2745 if (param_transition_p || trans1->labels != trans2->labels) 2746 { 2747 /* We can only generalize a single transition with a single 2748 label. */ 2749 if (num_transitions != 1 2750 || trans1->labels.length () != 1 2751 || trans2->labels.length () != 1) 2752 return false; 2753 2754 /* Although we can match wide-int fields, in practice it leads 2755 to some odd results for const_vectors. We end up 2756 parameterizing the first N const_ints of the vector 2757 and then (once we reach the maximum number of parameters) 2758 we go on to match the other elements exactly. */ 2759 if (d1->test.kind == rtx_test::WIDE_INT_FIELD) 2760 return false; 2761 2762 /* See whether the label has a generalizable type. */ 2763 parameter::type_enum param_type 2764 = transition_parameter_type (d1->test.kind); 2765 if (param_type == parameter::UNSET) 2766 return false; 2767 2768 /* Match the labels using parameters. */ 2769 new_param1 = parameter (param_type, false, trans1->labels[0]); 2770 if (param_transition_p) 2771 { 2772 if (!set_parameter (params1, param_transition, new_param1)) 2773 return false; 2774 } 2775 else 2776 { 2777 new_param2 = parameter (param_type, false, trans2->labels[0]); 2778 if (!add_parameter (params1, params2, new_param1, new_param2, 2779 start_param, ¶m_transition)) 2780 return false; 2781 param_transition_p = true; 2782 } 2783 } 2784 trans1 = trans1->next; 2785 trans2 = trans2->next; 2786 } 2787 2788 /* Set any unset parameters to their default values. This occurs if some 2789 other state needed something to be parameterized in order to match SINFO2, 2790 but SINFO1 on its own does not. */ 2791 for (unsigned int i = 0; i < params1.length (); ++i) 2792 if (params1[i].type == parameter::UNSET) 2793 params1[i] = params2[i]; 2794 2795 /* The match was successful. Commit all pending changes to PAT. */ 2796 update_parameters (pat->params, params2); 2797 { 2798 pending_param *pp; 2799 unsigned int i; 2800 FOR_EACH_VEC_ELT (pending_params, i, pp) 2801 *pp->first = parameter (pp->first->type, true, pp->second); 2802 } 2803 pat->param_test = param_test; 2804 pat->param_transition = param_transition; 2805 pat->param_test_p = param_test_p; 2806 pat->param_transition_p = param_transition_p; 2807 2808 /* Record the match of SINFO1. */ 2809 merge_state_result *new_res1 = new merge_state_result (pat, root1, 2810 sinfo1->res); 2811 new_res1->params.splice (params1); 2812 sinfo1->res = new_res1; 2813 return true; 2814 } 2815 2816 /* The number of states that were removed by calling pattern routines. */ 2817 static unsigned int pattern_use_states; 2818 2819 /* The number of states used while defining pattern routines. */ 2820 static unsigned int pattern_def_states; 2821 2822 /* Information used while constructing a use or definition of a pattern 2823 routine. */ 2824 struct create_pattern_info 2825 { 2826 /* The routine itself. */ 2827 pattern_routine *routine; 2828 2829 /* The first unclaimed return value for this particular use or definition. 2830 We walk the substates of uses and definitions in the same order 2831 so each return value always refers to the same position within 2832 the pattern. */ 2833 unsigned int next_result; 2834 }; 2835 2836 static void populate_pattern_routine (create_pattern_info *, 2837 merge_state_info *, state *, 2838 const vec <parameter> &); 2839 2840 /* SINFO matches a pattern for which we've decided to create a C routine. 2841 Return a decision that performs a call to the pattern routine, 2842 but leave the caller to add the transitions to it. Initialize CPI 2843 for this purpose. Also create a definition for the pattern routine, 2844 if it doesn't already have one. 2845 2846 PARAMS are the parameters that SINFO passes to its pattern. */ 2847 2848 static decision * 2849 init_pattern_use (create_pattern_info *cpi, merge_state_info *sinfo, 2850 const vec <parameter> ¶ms) 2851 { 2852 state *s = sinfo->s; 2853 merge_state_result *res = sinfo->res; 2854 merge_pattern_info *pat = res->pattern; 2855 cpi->routine = pat->routine; 2856 if (!cpi->routine) 2857 { 2858 /* We haven't defined the pattern routine yet, so create 2859 a definition now. */ 2860 pattern_routine *routine = new pattern_routine; 2861 pat->routine = routine; 2862 cpi->routine = routine; 2863 routine->s = new state; 2864 routine->insn_p = false; 2865 routine->pnum_clobbers_p = false; 2866 2867 /* Create an "idempotent" mapping of parameter I to parameter I. 2868 Also record the C type of each parameter to the routine. */ 2869 auto_vec <parameter, MAX_PATTERN_PARAMS> def_params; 2870 for (unsigned int i = 0; i < pat->params.length (); ++i) 2871 { 2872 def_params.quick_push (parameter (pat->params[i].type, true, i)); 2873 routine->param_types.quick_push (pat->params[i].type); 2874 } 2875 2876 /* Any of the states that match the pattern could be used to 2877 create the routine definition. We might as well use SINFO 2878 since it's already to hand. This means that all positions 2879 in the definition will be relative to RES->root. */ 2880 routine->pos = res->root; 2881 cpi->next_result = 0; 2882 populate_pattern_routine (cpi, sinfo, routine->s, def_params); 2883 gcc_assert (cpi->next_result == pat->num_results); 2884 2885 /* Add the routine to the global list, after the subroutines 2886 that it calls. */ 2887 routine->pattern_id = patterns.length (); 2888 patterns.safe_push (routine); 2889 } 2890 2891 /* Create a decision to call the routine, passing PARAMS to it. */ 2892 pattern_use *use = new pattern_use; 2893 use->routine = pat->routine; 2894 use->params.splice (params); 2895 decision *d = new decision (rtx_test::pattern (res->root, use)); 2896 2897 /* If the original decision could use an element of operands[] instead 2898 of an rtx variable, try to transfer it to the new decision. */ 2899 if (s->first->test.pos && res->root == s->first->test.pos) 2900 d->test.pos_operand = s->first->test.pos_operand; 2901 2902 cpi->next_result = 0; 2903 return d; 2904 } 2905 2906 /* Make S return the next unclaimed pattern routine result for CPI. */ 2907 2908 static void 2909 add_pattern_acceptance (create_pattern_info *cpi, state *s) 2910 { 2911 acceptance_type acceptance; 2912 acceptance.type = SUBPATTERN; 2913 acceptance.partial_p = false; 2914 acceptance.u.full.code = cpi->next_result; 2915 add_decision (s, rtx_test::accept (acceptance), true, false); 2916 cpi->next_result += 1; 2917 } 2918 2919 /* Initialize new empty state NEWS so that it implements SINFO's pattern 2920 (here referred to as "P"). P may be the top level of a pattern routine 2921 or a subpattern that should be inlined into its parent pattern's routine 2922 (as per same_pattern_p). The choice of SINFO for a top-level pattern is 2923 arbitrary; it could be any of the states that use P. The choice for 2924 subpatterns follows the choice for the parent pattern. 2925 2926 PARAMS gives the value of each parameter to P in terms of the parameters 2927 to the top-level pattern. If P itself is the top level pattern, PARAMS[I] 2928 is always "parameter (TYPE, true, I)". */ 2929 2930 static void 2931 populate_pattern_routine (create_pattern_info *cpi, merge_state_info *sinfo, 2932 state *news, const vec <parameter> ¶ms) 2933 { 2934 pattern_def_states += 1; 2935 2936 decision *d = sinfo->s->singleton (); 2937 merge_pattern_info *pat = sinfo->res->pattern; 2938 pattern_routine *routine = cpi->routine; 2939 2940 /* Create a copy of D's test for the pattern routine and generalize it 2941 as appropriate. */ 2942 decision *newd = new decision (d->test); 2943 gcc_assert (newd->test.pos_operand >= 0 2944 || !newd->test.pos 2945 || common_position (newd->test.pos, 2946 routine->pos) == routine->pos); 2947 if (pat->param_test_p) 2948 { 2949 const parameter ¶m = params[pat->param_test]; 2950 switch (newd->test.kind) 2951 { 2952 case rtx_test::PREDICATE: 2953 newd->test.u.predicate.mode_is_param = param.is_param; 2954 newd->test.u.predicate.mode = param.value; 2955 break; 2956 2957 case rtx_test::SAVED_CONST_INT: 2958 newd->test.u.integer.is_param = param.is_param; 2959 newd->test.u.integer.value = param.value; 2960 break; 2961 2962 default: 2963 gcc_unreachable (); 2964 break; 2965 } 2966 } 2967 if (d->test.kind == rtx_test::C_TEST) 2968 routine->insn_p = true; 2969 else if (d->test.kind == rtx_test::HAVE_NUM_CLOBBERS) 2970 routine->pnum_clobbers_p = true; 2971 news->push_back (newd); 2972 2973 /* Fill in the transitions of NEWD. */ 2974 unsigned int i = 0; 2975 for (transition *trans = d->first; trans; trans = trans->next) 2976 { 2977 /* Create a new state to act as the target of the new transition. */ 2978 state *to_news = new state; 2979 if (merge_pattern_transition *ptrans = pat->transitions[i]) 2980 { 2981 /* The pattern hasn't finished matching yet. Get the target 2982 pattern and the corresponding target state of SINFO. */ 2983 merge_pattern_info *to_pat = ptrans->to; 2984 merge_state_info *to = sinfo->to_states + i; 2985 gcc_assert (to->res->pattern == to_pat); 2986 gcc_assert (ptrans->params.length () == to_pat->params.length ()); 2987 2988 /* Express the parameters to TO_PAT in terms of the parameters 2989 to the top-level pattern. */ 2990 auto_vec <parameter, MAX_PATTERN_PARAMS> to_params; 2991 for (unsigned int j = 0; j < ptrans->params.length (); ++j) 2992 { 2993 const parameter ¶m = ptrans->params[j]; 2994 to_params.quick_push (param.is_param 2995 ? params[param.value] 2996 : param); 2997 } 2998 2999 if (same_pattern_p (pat, to_pat)) 3000 /* TO_PAT is part of the current routine, so just recurse. */ 3001 populate_pattern_routine (cpi, to, to_news, to_params); 3002 else 3003 { 3004 /* TO_PAT should be matched by calling a separate routine. */ 3005 create_pattern_info sub_cpi; 3006 decision *subd = init_pattern_use (&sub_cpi, to, to_params); 3007 routine->insn_p |= sub_cpi.routine->insn_p; 3008 routine->pnum_clobbers_p |= sub_cpi.routine->pnum_clobbers_p; 3009 3010 /* Add the pattern routine call to the new target state. */ 3011 to_news->push_back (subd); 3012 3013 /* Add a transition for each successful call result. */ 3014 for (unsigned int j = 0; j < to_pat->num_results; ++j) 3015 { 3016 state *res = new state; 3017 add_pattern_acceptance (cpi, res); 3018 subd->push_back (new transition (j, res, false)); 3019 } 3020 } 3021 } 3022 else 3023 /* This transition corresponds to a successful match. */ 3024 add_pattern_acceptance (cpi, to_news); 3025 3026 /* Create the transition itself, generalizing as necessary. */ 3027 transition *new_trans = new transition (trans->labels, to_news, 3028 trans->optional); 3029 if (pat->param_transition_p) 3030 { 3031 const parameter ¶m = params[pat->param_transition]; 3032 new_trans->is_param = param.is_param; 3033 new_trans->labels[0] = param.value; 3034 } 3035 newd->push_back (new_trans); 3036 i += 1; 3037 } 3038 } 3039 3040 /* USE is a decision that calls a pattern routine and SINFO is part of the 3041 original state tree that the call is supposed to replace. Add the 3042 transitions for SINFO and its substates to USE. */ 3043 3044 static void 3045 populate_pattern_use (create_pattern_info *cpi, decision *use, 3046 merge_state_info *sinfo) 3047 { 3048 pattern_use_states += 1; 3049 gcc_assert (!sinfo->merged_p); 3050 sinfo->merged_p = true; 3051 merge_state_result *res = sinfo->res; 3052 merge_pattern_info *pat = res->pattern; 3053 decision *d = sinfo->s->singleton (); 3054 unsigned int i = 0; 3055 for (transition *trans = d->first; trans; trans = trans->next) 3056 { 3057 if (pat->transitions[i]) 3058 /* The target state is also part of the pattern. */ 3059 populate_pattern_use (cpi, use, sinfo->to_states + i); 3060 else 3061 { 3062 /* The transition corresponds to a successful return from the 3063 pattern routine. */ 3064 use->push_back (new transition (cpi->next_result, trans->to, false)); 3065 cpi->next_result += 1; 3066 } 3067 i += 1; 3068 } 3069 } 3070 3071 /* We have decided to replace SINFO's state with a call to a pattern 3072 routine. Make the change, creating a definition of the pattern routine 3073 if it doesn't have one already. */ 3074 3075 static void 3076 use_pattern (merge_state_info *sinfo) 3077 { 3078 merge_state_result *res = sinfo->res; 3079 merge_pattern_info *pat = res->pattern; 3080 state *s = sinfo->s; 3081 3082 /* The pattern may have acquired new parameters after it was matched 3083 against SINFO. Update the parameters that SINFO passes accordingly. */ 3084 update_parameters (res->params, pat->params); 3085 3086 create_pattern_info cpi; 3087 decision *d = init_pattern_use (&cpi, sinfo, res->params); 3088 populate_pattern_use (&cpi, d, sinfo); 3089 s->release (); 3090 s->push_back (d); 3091 } 3092 3093 /* Look through the state trees in STATES for common patterns and 3094 split them into subroutines. */ 3095 3096 static void 3097 split_out_patterns (vec <merge_state_info> &states) 3098 { 3099 unsigned int first_transition = states.length (); 3100 hash_table <test_pattern_hasher> hashtab (128); 3101 /* Stage 1: Create an order in which parent states come before their child 3102 states and in which sibling states are at consecutive locations. 3103 Having consecutive sibling states allows merge_state_info to have 3104 a single to_states pointer. */ 3105 for (unsigned int i = 0; i < states.length (); ++i) 3106 for (decision *d = states[i].s->first; d; d = d->next) 3107 for (transition *trans = d->first; trans; trans = trans->next) 3108 { 3109 states.safe_push (trans->to); 3110 states[i].num_transitions += 1; 3111 } 3112 /* Stage 2: Now that the addresses are stable, set up the to_states 3113 pointers. Look for states that might be merged and enter them 3114 into the hash table. */ 3115 for (unsigned int i = 0; i < states.length (); ++i) 3116 { 3117 merge_state_info *sinfo = &states[i]; 3118 if (sinfo->num_transitions) 3119 { 3120 sinfo->to_states = &states[first_transition]; 3121 first_transition += sinfo->num_transitions; 3122 } 3123 /* For simplicity, we only try to merge states that have a single 3124 decision. This is in any case the best we can do for peephole2, 3125 since whether a peephole2 ACCEPT succeeds or not depends on the 3126 specific peephole2 pattern (which is unique to each ACCEPT 3127 and so couldn't be shared between states). */ 3128 if (decision *d = sinfo->s->singleton ()) 3129 /* ACCEPT states are unique, so don't even try to merge them. */ 3130 if (d->test.kind != rtx_test::ACCEPT 3131 && (pattern_have_num_clobbers_p 3132 || d->test.kind != rtx_test::HAVE_NUM_CLOBBERS) 3133 && (pattern_c_test_p 3134 || d->test.kind != rtx_test::C_TEST)) 3135 { 3136 merge_state_info **slot = hashtab.find_slot (sinfo, INSERT); 3137 sinfo->prev_same_test = *slot; 3138 *slot = sinfo; 3139 } 3140 } 3141 /* Stage 3: Walk backwards through the list of states and try to merge 3142 them. This is a greedy, bottom-up match; parent nodes can only start 3143 a new leaf pattern if they fail to match when combined with all child 3144 nodes that have matching patterns. 3145 3146 For each state we keep a list of potential matches, with each 3147 potential match being larger (and deeper) than the next match in 3148 the list. The final element in the list is a leaf pattern that 3149 matches just a single state. 3150 3151 Each candidate pattern created in this loop is unique -- it won't 3152 have been seen by an earlier iteration. We try to match each pattern 3153 with every state that appears earlier in STATES. 3154 3155 Because the patterns created in the loop are unique, any state 3156 that already has a match must have a final potential match that 3157 is different from any new leaf pattern. Therefore, when matching 3158 leaf patterns, we need only consider states whose list of matches 3159 is empty. 3160 3161 The non-leaf patterns that we try are as deep as possible 3162 and are an extension of the state's previous best candidate match (PB). 3163 We need only consider states whose current potential match is also PB; 3164 any states that don't match as much as PB cannnot match the new pattern, 3165 while any states that already match more than PB must be different from 3166 the new pattern. */ 3167 for (unsigned int i2 = states.length (); i2-- > 0; ) 3168 { 3169 merge_state_info *sinfo2 = &states[i2]; 3170 3171 /* Enforce the bottom-upness of the match: remove matches with later 3172 states if SINFO2's child states ended up finding a better match. */ 3173 prune_invalid_results (sinfo2); 3174 3175 /* Do nothing if the state doesn't match a later one and if there are 3176 no earlier states it could match. */ 3177 if (!sinfo2->res && !sinfo2->prev_same_test) 3178 continue; 3179 3180 merge_state_result *res2 = sinfo2->res; 3181 decision *d2 = sinfo2->s->singleton (); 3182 position *root2 = (d2->test.pos_operand < 0 ? d2->test.pos : 0); 3183 unsigned int num_transitions = sinfo2->num_transitions; 3184 3185 /* If RES2 is null then SINFO2's test in isolation has not been seen 3186 before. First try matching that on its own. */ 3187 if (!res2) 3188 { 3189 merge_pattern_info *new_pat 3190 = new merge_pattern_info (num_transitions); 3191 merge_state_result *new_res2 3192 = new merge_state_result (new_pat, root2, res2); 3193 sinfo2->res = new_res2; 3194 3195 new_pat->num_statements = !d2->test.single_outcome_p (); 3196 new_pat->num_results = num_transitions; 3197 bool matched_p = false; 3198 /* Look for states that don't currently match anything but 3199 can be made to match SINFO2 on its own. */ 3200 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1; 3201 sinfo1 = sinfo1->prev_same_test) 3202 if (!sinfo1->res && merge_patterns (sinfo1, sinfo2)) 3203 matched_p = true; 3204 if (!matched_p) 3205 { 3206 /* No other states match. */ 3207 sinfo2->res = res2; 3208 delete new_pat; 3209 delete new_res2; 3210 continue; 3211 } 3212 else 3213 res2 = new_res2; 3214 } 3215 3216 /* Keep the existing pattern if it's as good as anything we'd 3217 create for SINFO2. */ 3218 if (complete_result_p (res2->pattern, sinfo2)) 3219 { 3220 res2->pattern->num_users += 1; 3221 continue; 3222 } 3223 3224 /* Create a new pattern for SINFO2. */ 3225 merge_pattern_info *new_pat = new merge_pattern_info (num_transitions); 3226 merge_state_result *new_res2 3227 = new merge_state_result (new_pat, root2, res2); 3228 sinfo2->res = new_res2; 3229 3230 /* Fill in details about the pattern. */ 3231 new_pat->num_statements = !d2->test.single_outcome_p (); 3232 new_pat->num_results = 0; 3233 for (unsigned int j = 0; j < num_transitions; ++j) 3234 if (merge_state_result *to_res = sinfo2->to_states[j].res) 3235 { 3236 /* Count the target state as part of this pattern. 3237 First update the root position so that it can reach 3238 the target state's root. */ 3239 if (to_res->root) 3240 { 3241 if (new_res2->root) 3242 new_res2->root = common_position (new_res2->root, 3243 to_res->root); 3244 else 3245 new_res2->root = to_res->root; 3246 } 3247 merge_pattern_info *to_pat = to_res->pattern; 3248 merge_pattern_transition *ptrans 3249 = new merge_pattern_transition (to_pat); 3250 3251 /* TO_PAT may have acquired more parameters when matching 3252 states earlier in STATES than TO_RES's, but the list is 3253 now final. Make sure that TO_RES is up to date. */ 3254 update_parameters (to_res->params, to_pat->params); 3255 3256 /* Start out by assuming that every user of NEW_PAT will 3257 want to pass the same (constant) parameters as TO_RES. */ 3258 update_parameters (ptrans->params, to_res->params); 3259 3260 new_pat->transitions[j] = ptrans; 3261 new_pat->num_statements += to_pat->num_statements; 3262 new_pat->num_results += to_pat->num_results; 3263 } 3264 else 3265 /* The target state doesn't match anything and so is not part 3266 of the pattern. */ 3267 new_pat->num_results += 1; 3268 3269 /* See if any earlier states that match RES2's pattern also match 3270 NEW_PAT. */ 3271 bool matched_p = false; 3272 for (merge_state_info *sinfo1 = sinfo2->prev_same_test; sinfo1; 3273 sinfo1 = sinfo1->prev_same_test) 3274 { 3275 prune_invalid_results (sinfo1); 3276 if (sinfo1->res 3277 && sinfo1->res->pattern == res2->pattern 3278 && merge_patterns (sinfo1, sinfo2)) 3279 matched_p = true; 3280 } 3281 if (!matched_p) 3282 { 3283 /* Nothing else matches NEW_PAT, so go back to the previous 3284 pattern (possibly just a single-state one). */ 3285 sinfo2->res = res2; 3286 delete new_pat; 3287 delete new_res2; 3288 } 3289 /* Assume that SINFO2 will use RES. At this point we don't know 3290 whether earlier states that match the same pattern will use 3291 that match or a different one. */ 3292 sinfo2->res->pattern->num_users += 1; 3293 } 3294 /* Step 4: Finalize the choice of pattern for each state, ignoring 3295 patterns that were only used once. Update each pattern's size 3296 so that it doesn't include subpatterns that are going to be split 3297 out into subroutines. */ 3298 for (unsigned int i = 0; i < states.length (); ++i) 3299 { 3300 merge_state_info *sinfo = &states[i]; 3301 merge_state_result *res = sinfo->res; 3302 /* Wind past patterns that are only used by SINFO. */ 3303 while (res && res->pattern->num_users == 1) 3304 { 3305 res = res->prev; 3306 sinfo->res = res; 3307 if (res) 3308 res->pattern->num_users += 1; 3309 } 3310 if (!res) 3311 continue; 3312 3313 /* We have a shared pattern and are now committed to the match. */ 3314 merge_pattern_info *pat = res->pattern; 3315 gcc_assert (valid_result_p (pat, sinfo)); 3316 3317 if (!pat->complete_p) 3318 { 3319 /* Look for subpatterns that are going to be split out and remove 3320 them from the number of statements. */ 3321 for (unsigned int j = 0; j < sinfo->num_transitions; ++j) 3322 if (merge_pattern_transition *ptrans = pat->transitions[j]) 3323 { 3324 merge_pattern_info *to_pat = ptrans->to; 3325 if (!same_pattern_p (pat, to_pat)) 3326 pat->num_statements -= to_pat->num_statements; 3327 } 3328 pat->complete_p = true; 3329 } 3330 } 3331 /* Step 5: Split out the patterns. */ 3332 for (unsigned int i = 0; i < states.length (); ++i) 3333 { 3334 merge_state_info *sinfo = &states[i]; 3335 merge_state_result *res = sinfo->res; 3336 if (!sinfo->merged_p && res && useful_pattern_p (res->pattern)) 3337 use_pattern (sinfo); 3338 } 3339 fprintf (stderr, "Shared %d out of %d states by creating %d new states," 3340 " saving %d\n", 3341 pattern_use_states, states.length (), pattern_def_states, 3342 pattern_use_states - pattern_def_states); 3343 } 3344 3345 /* Information about a state tree that we're considering splitting into a 3346 subroutine. */ 3347 struct state_size 3348 { 3349 /* The number of pseudo-statements in the state tree. */ 3350 unsigned int num_statements; 3351 3352 /* The approximate number of nested "if" and "switch" statements that 3353 would be required if control could fall through to a later state. */ 3354 unsigned int depth; 3355 }; 3356 3357 /* Pairs a transition with information about its target state. */ 3358 typedef std::pair <transition *, state_size> subroutine_candidate; 3359 3360 /* Sort two subroutine_candidates so that the one with the largest 3361 number of statements comes last. */ 3362 3363 static int 3364 subroutine_candidate_cmp (const void *a, const void *b) 3365 { 3366 return int (((const subroutine_candidate *) a)->second.num_statements 3367 - ((const subroutine_candidate *) b)->second.num_statements); 3368 } 3369 3370 /* Turn S into a subroutine of type TYPE and add it to PROCS. Return a new 3371 state that performs a subroutine call to S. */ 3372 3373 static state * 3374 create_subroutine (routine_type type, state *s, vec <state *> &procs) 3375 { 3376 procs.safe_push (s); 3377 acceptance_type acceptance; 3378 acceptance.type = type; 3379 acceptance.partial_p = true; 3380 acceptance.u.subroutine_id = procs.length (); 3381 state *news = new state; 3382 add_decision (news, rtx_test::accept (acceptance), true, false); 3383 return news; 3384 } 3385 3386 /* Walk state tree S, of type TYPE, and look for subtrees that would be 3387 better split into subroutines. Accumulate all such subroutines in PROCS. 3388 Return the size of the new state tree (excluding subroutines). */ 3389 3390 static state_size 3391 find_subroutines (routine_type type, state *s, vec <state *> &procs) 3392 { 3393 auto_vec <subroutine_candidate, 16> candidates; 3394 state_size size; 3395 size.num_statements = 0; 3396 size.depth = 0; 3397 for (decision *d = s->first; d; d = d->next) 3398 { 3399 if (!d->test.single_outcome_p ()) 3400 size.num_statements += 1; 3401 for (transition *trans = d->first; trans; trans = trans->next) 3402 { 3403 /* Keep chains of simple decisions together if we know that no 3404 change of position is required. We'll output this chain as a 3405 single "if" statement, so it counts as a single nesting level. */ 3406 if (d->test.pos && d->if_statement_p ()) 3407 for (;;) 3408 { 3409 decision *newd = trans->to->singleton (); 3410 if (!newd 3411 || (newd->test.pos 3412 && newd->test.pos_operand < 0 3413 && newd->test.pos != d->test.pos) 3414 || !newd->if_statement_p ()) 3415 break; 3416 if (!newd->test.single_outcome_p ()) 3417 size.num_statements += 1; 3418 trans = newd->singleton (); 3419 if (newd->test.kind == rtx_test::SET_OP 3420 || newd->test.kind == rtx_test::ACCEPT) 3421 break; 3422 } 3423 /* The target of TRANS is a subroutine candidate. First recurse 3424 on it to see how big it is after subroutines have been 3425 split out. */ 3426 state_size to_size = find_subroutines (type, trans->to, procs); 3427 if (d->next && to_size.depth > MAX_DEPTH) 3428 /* Keeping the target state in the same routine would lead 3429 to an excessive nesting of "if" and "switch" statements. 3430 Split it out into a subroutine so that it can use 3431 inverted tests that return early on failure. */ 3432 trans->to = create_subroutine (type, trans->to, procs); 3433 else 3434 { 3435 size.num_statements += to_size.num_statements; 3436 if (to_size.num_statements < MIN_NUM_STATEMENTS) 3437 /* The target state is too small to be worth splitting. 3438 Keep it in the same routine as S. */ 3439 size.depth = MAX (size.depth, to_size.depth); 3440 else 3441 /* Assume for now that we'll keep the target state in the 3442 same routine as S, but record it as a subroutine candidate 3443 if S grows too big. */ 3444 candidates.safe_push (subroutine_candidate (trans, to_size)); 3445 } 3446 } 3447 } 3448 if (size.num_statements > MAX_NUM_STATEMENTS) 3449 { 3450 /* S is too big. Sort the subroutine candidates so that bigger ones 3451 are nearer the end. */ 3452 candidates.qsort (subroutine_candidate_cmp); 3453 while (!candidates.is_empty () 3454 && size.num_statements > MAX_NUM_STATEMENTS) 3455 { 3456 /* Peel off a candidate and force it into a subroutine. */ 3457 subroutine_candidate cand = candidates.pop (); 3458 size.num_statements -= cand.second.num_statements; 3459 cand.first->to = create_subroutine (type, cand.first->to, procs); 3460 } 3461 } 3462 /* Update the depth for subroutine candidates that we decided not to 3463 split out. */ 3464 for (unsigned int i = 0; i < candidates.length (); ++i) 3465 size.depth = MAX (size.depth, candidates[i].second.depth); 3466 size.depth += 1; 3467 return size; 3468 } 3469 3470 /* Return true if, for all X, PRED (X, MODE) implies that X has mode MODE. */ 3471 3472 static bool 3473 safe_predicate_mode (const struct pred_data *pred, machine_mode mode) 3474 { 3475 /* Scalar integer constants have VOIDmode. */ 3476 if (GET_MODE_CLASS (mode) == MODE_INT 3477 && (pred->codes[CONST_INT] 3478 || pred->codes[CONST_DOUBLE] 3479 || pred->codes[CONST_WIDE_INT] 3480 || pred->codes[LABEL_REF])) 3481 return false; 3482 3483 return !pred->special && mode != VOIDmode; 3484 } 3485 3486 /* Fill CODES with the set of codes that could be matched by PRED. */ 3487 3488 static void 3489 get_predicate_codes (const struct pred_data *pred, int_set *codes) 3490 { 3491 for (int i = 0; i < NUM_TRUE_RTX_CODE; ++i) 3492 if (!pred || pred->codes[i]) 3493 codes->safe_push (i); 3494 } 3495 3496 /* Return true if the first path through D1 tests the same thing as D2. */ 3497 3498 static bool 3499 has_same_test_p (decision *d1, decision *d2) 3500 { 3501 do 3502 { 3503 if (d1->test == d2->test) 3504 return true; 3505 d1 = d1->first->to->first; 3506 } 3507 while (d1); 3508 return false; 3509 } 3510 3511 /* Return true if D1 and D2 cannot match the same rtx. All states reachable 3512 from D2 have single decisions and all those decisions have single 3513 transitions. */ 3514 3515 static bool 3516 mutually_exclusive_p (decision *d1, decision *d2) 3517 { 3518 /* If one path through D1 fails to test the same thing as D2, assume 3519 that D2's test could be true for D1 and look for a later, more useful, 3520 test. This isn't as expensive as it looks in practice. */ 3521 while (!has_same_test_p (d1, d2)) 3522 { 3523 d2 = d2->singleton ()->to->singleton (); 3524 if (!d2) 3525 return false; 3526 } 3527 if (d1->test == d2->test) 3528 { 3529 /* Look for any transitions from D1 that have the same labels as 3530 the transition from D2. */ 3531 transition *trans2 = d2->singleton (); 3532 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next) 3533 { 3534 int_set::iterator i1 = trans1->labels.begin (); 3535 int_set::iterator end1 = trans1->labels.end (); 3536 int_set::iterator i2 = trans2->labels.begin (); 3537 int_set::iterator end2 = trans2->labels.end (); 3538 while (i1 != end1 && i2 != end2) 3539 if (*i1 < *i2) 3540 ++i1; 3541 else if (*i2 < *i1) 3542 ++i2; 3543 else 3544 { 3545 /* TRANS1 has some labels in common with TRANS2. Assume 3546 that D1 and D2 could match the same rtx if the target 3547 of TRANS1 could match the same rtx as D2. */ 3548 for (decision *subd1 = trans1->to->first; 3549 subd1; subd1 = subd1->next) 3550 if (!mutually_exclusive_p (subd1, d2)) 3551 return false; 3552 break; 3553 } 3554 } 3555 return true; 3556 } 3557 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next) 3558 for (decision *subd1 = trans1->to->first; subd1; subd1 = subd1->next) 3559 if (!mutually_exclusive_p (subd1, d2)) 3560 return false; 3561 return true; 3562 } 3563 3564 /* Try to merge S2's decision into D1, given that they have the same test. 3565 Fail only if EXCLUDE is nonnull and the new transition would have the 3566 same labels as *EXCLUDE. When returning true, set *NEXT_S1, *NEXT_S2 3567 and *NEXT_EXCLUDE as for merge_into_state_1, or set *NEXT_S2 to null 3568 if the merge is complete. */ 3569 3570 static bool 3571 merge_into_decision (decision *d1, state *s2, const int_set *exclude, 3572 state **next_s1, state **next_s2, 3573 const int_set **next_exclude) 3574 { 3575 decision *d2 = s2->singleton (); 3576 transition *trans2 = d2->singleton (); 3577 3578 /* Get a list of the transitions that intersect TRANS2. */ 3579 auto_vec <transition *, 32> intersecting; 3580 for (transition *trans1 = d1->first; trans1; trans1 = trans1->next) 3581 { 3582 int_set::iterator i1 = trans1->labels.begin (); 3583 int_set::iterator end1 = trans1->labels.end (); 3584 int_set::iterator i2 = trans2->labels.begin (); 3585 int_set::iterator end2 = trans2->labels.end (); 3586 bool trans1_is_subset = true; 3587 bool trans2_is_subset = true; 3588 bool intersect_p = false; 3589 while (i1 != end1 && i2 != end2) 3590 if (*i1 < *i2) 3591 { 3592 trans1_is_subset = false; 3593 ++i1; 3594 } 3595 else if (*i2 < *i1) 3596 { 3597 trans2_is_subset = false; 3598 ++i2; 3599 } 3600 else 3601 { 3602 intersect_p = true; 3603 ++i1; 3604 ++i2; 3605 } 3606 if (i1 != end1) 3607 trans1_is_subset = false; 3608 if (i2 != end2) 3609 trans2_is_subset = false; 3610 if (trans1_is_subset && trans2_is_subset) 3611 { 3612 /* There's already a transition that matches exactly. 3613 Merge the target states. */ 3614 trans1->optional &= trans2->optional; 3615 *next_s1 = trans1->to; 3616 *next_s2 = trans2->to; 3617 *next_exclude = 0; 3618 return true; 3619 } 3620 if (trans2_is_subset) 3621 { 3622 /* TRANS1 has all the labels that TRANS2 needs. Merge S2 into 3623 the target of TRANS1, but (to avoid infinite recursion) 3624 make sure that we don't end up creating another transition 3625 like TRANS1. */ 3626 *next_s1 = trans1->to; 3627 *next_s2 = s2; 3628 *next_exclude = &trans1->labels; 3629 return true; 3630 } 3631 if (intersect_p) 3632 intersecting.safe_push (trans1); 3633 } 3634 3635 if (intersecting.is_empty ()) 3636 { 3637 /* No existing labels intersect the new ones. We can just add 3638 TRANS2 itself. */ 3639 d1->push_back (d2->release ()); 3640 *next_s1 = 0; 3641 *next_s2 = 0; 3642 *next_exclude = 0; 3643 return true; 3644 } 3645 3646 /* Take the union of the labels in INTERSECTING and TRANS2. Store the 3647 result in COMBINED and use NEXT as a temporary. */ 3648 int_set tmp1 = trans2->labels, tmp2; 3649 int_set *combined = &tmp1, *next = &tmp2; 3650 for (unsigned int i = 0; i < intersecting.length (); ++i) 3651 { 3652 transition *trans1 = intersecting[i]; 3653 next->truncate (0); 3654 next->safe_grow (trans1->labels.length () + combined->length ()); 3655 int_set::iterator end 3656 = std::set_union (trans1->labels.begin (), trans1->labels.end (), 3657 combined->begin (), combined->end (), 3658 next->begin ()); 3659 next->truncate (end - next->begin ()); 3660 std::swap (next, combined); 3661 } 3662 3663 /* Stop now if we've been told not to create a transition with these 3664 labels. */ 3665 if (exclude && *combined == *exclude) 3666 return false; 3667 3668 /* Get the transition that should carry the new labels. */ 3669 transition *new_trans = intersecting[0]; 3670 if (intersecting.length () == 1) 3671 { 3672 /* We're merging with one existing transition whose labels are a 3673 subset of those required. If both transitions are optional, 3674 we can just expand the set of labels so that it's suitable 3675 for both transitions. It isn't worth preserving the original 3676 transitions since we know that they can't be merged; we would 3677 need to backtrack to S2 if TRANS1->to fails. In contrast, 3678 we might be able to merge the targets of the transitions 3679 without any backtracking. 3680 3681 If instead the existing transition is not optional, ensure that 3682 all target decisions are suitably protected. Some decisions 3683 might already have a more specific requirement than NEW_TRANS, 3684 in which case there's no point testing NEW_TRANS as well. E.g. this 3685 would have happened if a test for an (eq ...) rtx had been 3686 added to a decision that tested whether the code is suitable 3687 for comparison_operator. The original comparison_operator 3688 transition would have been non-optional and the (eq ...) test 3689 would be performed by a second decision in the target of that 3690 transition. 3691 3692 The remaining case -- keeping the original optional transition 3693 when adding a non-optional TRANS2 -- is a wash. Preserving 3694 the optional transition only helps if we later merge another 3695 state S3 that is mutually exclusive with S2 and whose labels 3696 belong to *COMBINED - TRANS1->labels. We can then test the 3697 original NEW_TRANS and S3 in the same decision. We keep the 3698 optional transition around for that case, but it occurs very 3699 rarely. */ 3700 gcc_assert (new_trans->labels != *combined); 3701 if (!new_trans->optional || !trans2->optional) 3702 { 3703 decision *start = 0; 3704 for (decision *end = new_trans->to->first; end; end = end->next) 3705 { 3706 if (!start && end->test != d1->test) 3707 /* END belongs to a range of decisions that need to be 3708 protected by NEW_TRANS. */ 3709 start = end; 3710 if (start && (!end->next || end->next->test == d1->test)) 3711 { 3712 /* Protect [START, END] with NEW_TRANS. The decisions 3713 move to NEW_S and NEW_D becomes part of NEW_TRANS->to. */ 3714 state *new_s = new state; 3715 decision *new_d = new decision (d1->test); 3716 new_d->push_back (new transition (new_trans->labels, new_s, 3717 new_trans->optional)); 3718 state::range r (start, end); 3719 new_trans->to->replace (r, new_d); 3720 new_s->push_back (r); 3721 3722 /* Continue with an empty range. */ 3723 start = 0; 3724 3725 /* Continue from the decision after NEW_D. */ 3726 end = new_d; 3727 } 3728 } 3729 } 3730 new_trans->optional = true; 3731 new_trans->labels = *combined; 3732 } 3733 else 3734 { 3735 /* We're merging more than one existing transition together. 3736 Those transitions are successfully dividing the matching space 3737 and so we want to preserve them, even if they're optional. 3738 3739 Create a new transition with the union set of labels and make 3740 it go to a state that has the original transitions. */ 3741 decision *new_d = new decision (d1->test); 3742 for (unsigned int i = 0; i < intersecting.length (); ++i) 3743 new_d->push_back (d1->remove (intersecting[i])); 3744 3745 state *new_s = new state; 3746 new_s->push_back (new_d); 3747 3748 new_trans = new transition (*combined, new_s, true); 3749 d1->push_back (new_trans); 3750 } 3751 3752 /* We now have an optional transition with labels *COMBINED. Decide 3753 whether we can use it as TRANS2 or whether we need to merge S2 3754 into the target of NEW_TRANS. */ 3755 gcc_assert (new_trans->optional); 3756 if (new_trans->labels == trans2->labels) 3757 { 3758 /* NEW_TRANS matches TRANS2. Just merge the target states. */ 3759 new_trans->optional = trans2->optional; 3760 *next_s1 = new_trans->to; 3761 *next_s2 = trans2->to; 3762 *next_exclude = 0; 3763 } 3764 else 3765 { 3766 /* Try to merge TRANS2 into the target of the overlapping transition, 3767 but (to prevent infinite recursion or excessive redundancy) without 3768 creating another transition of the same type. */ 3769 *next_s1 = new_trans->to; 3770 *next_s2 = s2; 3771 *next_exclude = &new_trans->labels; 3772 } 3773 return true; 3774 } 3775 3776 /* Make progress in merging S2 into S1, given that each state in S2 3777 has a single decision. If EXCLUDE is nonnull, avoid creating a new 3778 transition with the same test as S2's decision and with the labels 3779 in *EXCLUDE. 3780 3781 Return true if there is still work to do. When returning true, 3782 set *NEXT_S1, *NEXT_S2 and *NEXT_EXCLUDE to the values that 3783 S1, S2 and EXCLUDE should have next time round. 3784 3785 If S1 and S2 both match a particular rtx, give priority to S1. */ 3786 3787 static bool 3788 merge_into_state_1 (state *s1, state *s2, const int_set *exclude, 3789 state **next_s1, state **next_s2, 3790 const int_set **next_exclude) 3791 { 3792 decision *d2 = s2->singleton (); 3793 if (decision *d1 = s1->last) 3794 { 3795 if (d1->test.terminal_p ()) 3796 /* D1 is an unconditional return, so S2 can never match. This can 3797 sometimes be a bug in the .md description, but might also happen 3798 if genconditions forces some conditions to true for certain 3799 configurations. */ 3800 return false; 3801 3802 /* Go backwards through the decisions in S1, stopping once we find one 3803 that could match the same thing as S2. */ 3804 while (d1->prev && mutually_exclusive_p (d1, d2)) 3805 d1 = d1->prev; 3806 3807 /* Search forwards from that point, merging D2 into the first 3808 decision we can. */ 3809 for (; d1; d1 = d1->next) 3810 { 3811 /* If S2 performs some optional tests before testing the same thing 3812 as D1, those tests do not help to distinguish D1 and S2, so it's 3813 better to drop them. Search through such optional decisions 3814 until we find something that tests the same thing as D1. */ 3815 state *sub_s2 = s2; 3816 for (;;) 3817 { 3818 decision *sub_d2 = sub_s2->singleton (); 3819 if (d1->test == sub_d2->test) 3820 { 3821 /* Only apply EXCLUDE if we're testing the same thing 3822 as D2. */ 3823 const int_set *sub_exclude = (d2 == sub_d2 ? exclude : 0); 3824 3825 /* Try to merge SUB_S2 into D1. This can only fail if 3826 it would involve creating a new transition with 3827 labels SUB_EXCLUDE. */ 3828 if (merge_into_decision (d1, sub_s2, sub_exclude, 3829 next_s1, next_s2, next_exclude)) 3830 return *next_s2 != 0; 3831 3832 /* Can't merge with D1; try a later decision. */ 3833 break; 3834 } 3835 transition *sub_trans2 = sub_d2->singleton (); 3836 if (!sub_trans2->optional) 3837 /* Can't merge with D1; try a later decision. */ 3838 break; 3839 sub_s2 = sub_trans2->to; 3840 } 3841 } 3842 } 3843 3844 /* We can't merge D2 with any existing decision. Just add it to the end. */ 3845 s1->push_back (s2->release ()); 3846 return false; 3847 } 3848 3849 /* Merge S2 into S1. If they both match a particular rtx, give 3850 priority to S1. Each state in S2 has a single decision. */ 3851 3852 static void 3853 merge_into_state (state *s1, state *s2) 3854 { 3855 const int_set *exclude = 0; 3856 while (s2 && merge_into_state_1 (s1, s2, exclude, &s1, &s2, &exclude)) 3857 continue; 3858 } 3859 3860 /* Pairs a pattern that needs to be matched with the rtx position at 3861 which the pattern should occur. */ 3862 struct pattern_pos { 3863 pattern_pos () {} 3864 pattern_pos (rtx, position *); 3865 3866 rtx pattern; 3867 position *pos; 3868 }; 3869 3870 pattern_pos::pattern_pos (rtx pattern_in, position *pos_in) 3871 : pattern (pattern_in), pos (pos_in) 3872 {} 3873 3874 /* Compare entries according to their depth-first order. There shouldn't 3875 be two entries at the same position. */ 3876 3877 bool 3878 operator < (const pattern_pos &e1, const pattern_pos &e2) 3879 { 3880 int diff = compare_positions (e1.pos, e2.pos); 3881 gcc_assert (diff != 0 || e1.pattern == e2.pattern); 3882 return diff < 0; 3883 } 3884 3885 /* Add new decisions to S that check whether the rtx at position POS 3886 matches PATTERN. Return the state that is reached in that case. 3887 TOP_PATTERN is the overall pattern, as passed to match_pattern_1. */ 3888 3889 static state * 3890 match_pattern_2 (state *s, md_rtx_info *info, position *pos, rtx pattern) 3891 { 3892 auto_vec <pattern_pos, 32> worklist; 3893 auto_vec <pattern_pos, 32> pred_and_mode_tests; 3894 auto_vec <pattern_pos, 32> dup_tests; 3895 3896 worklist.safe_push (pattern_pos (pattern, pos)); 3897 while (!worklist.is_empty ()) 3898 { 3899 pattern_pos next = worklist.pop (); 3900 pattern = next.pattern; 3901 pos = next.pos; 3902 unsigned int reverse_s = worklist.length (); 3903 3904 enum rtx_code code = GET_CODE (pattern); 3905 switch (code) 3906 { 3907 case MATCH_OP_DUP: 3908 case MATCH_DUP: 3909 case MATCH_PAR_DUP: 3910 /* Add a test that the rtx matches the earlier one, but only 3911 after the structure and predicates have been checked. */ 3912 dup_tests.safe_push (pattern_pos (pattern, pos)); 3913 3914 /* Use the same code check as the original operand. */ 3915 pattern = find_operand (info->def, XINT (pattern, 0), NULL_RTX); 3916 /* Fall through. */ 3917 3918 case MATCH_PARALLEL: 3919 case MATCH_OPERAND: 3920 case MATCH_SCRATCH: 3921 case MATCH_OPERATOR: 3922 { 3923 const char *pred_name = predicate_name (pattern); 3924 const struct pred_data *pred = 0; 3925 if (pred_name[0] != 0) 3926 { 3927 pred = lookup_predicate (pred_name); 3928 /* Only report errors once per rtx. */ 3929 if (code == GET_CODE (pattern)) 3930 { 3931 if (!pred) 3932 error_at (info->loc, "unknown predicate '%s' used in %s", 3933 pred_name, GET_RTX_NAME (code)); 3934 else if (code == MATCH_PARALLEL 3935 && pred->singleton != PARALLEL) 3936 error_at (info->loc, "predicate '%s' used in" 3937 " match_parallel does not allow only PARALLEL", 3938 pred->name); 3939 } 3940 } 3941 3942 if (code == MATCH_PARALLEL || code == MATCH_PAR_DUP) 3943 { 3944 /* Check that we have a parallel with enough elements. */ 3945 s = add_decision (s, rtx_test::code (pos), PARALLEL, false); 3946 int min_len = XVECLEN (pattern, 2); 3947 s = add_decision (s, rtx_test::veclen_ge (pos, min_len), 3948 true, false); 3949 } 3950 else 3951 { 3952 /* Check that the rtx has one of codes accepted by the 3953 predicate. This is necessary when matching suboperands 3954 of a MATCH_OPERATOR or MATCH_OP_DUP, since we can't 3955 call XEXP (X, N) without checking that X has at least 3956 N+1 operands. */ 3957 int_set codes; 3958 get_predicate_codes (pred, &codes); 3959 bool need_codes = (pred 3960 && (code == MATCH_OPERATOR 3961 || code == MATCH_OP_DUP)); 3962 s = add_decision (s, rtx_test::code (pos), codes, !need_codes); 3963 } 3964 3965 /* Postpone the predicate check until we've checked the rest 3966 of the rtx structure. */ 3967 if (code == GET_CODE (pattern)) 3968 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos)); 3969 3970 /* If we need to match suboperands, add them to the worklist. */ 3971 if (code == MATCH_OPERATOR || code == MATCH_PARALLEL) 3972 { 3973 position **subpos_ptr; 3974 enum position_type pos_type; 3975 int i; 3976 if (code == MATCH_OPERATOR || code == MATCH_OP_DUP) 3977 { 3978 pos_type = POS_XEXP; 3979 subpos_ptr = &pos->xexps; 3980 i = (code == MATCH_OPERATOR ? 2 : 1); 3981 } 3982 else 3983 { 3984 pos_type = POS_XVECEXP0; 3985 subpos_ptr = &pos->xvecexp0s; 3986 i = 2; 3987 } 3988 for (int j = 0; j < XVECLEN (pattern, i); ++j) 3989 { 3990 position *subpos = next_position (subpos_ptr, pos, 3991 pos_type, j); 3992 worklist.safe_push (pattern_pos (XVECEXP (pattern, i, j), 3993 subpos)); 3994 subpos_ptr = &subpos->next; 3995 } 3996 } 3997 break; 3998 } 3999 4000 default: 4001 { 4002 /* Check that the rtx has the right code. */ 4003 s = add_decision (s, rtx_test::code (pos), code, false); 4004 4005 /* Queue a test for the mode if one is specified. */ 4006 if (GET_MODE (pattern) != VOIDmode) 4007 pred_and_mode_tests.safe_push (pattern_pos (pattern, pos)); 4008 4009 /* Push subrtxes onto the worklist. Match nonrtx operands now. */ 4010 const char *fmt = GET_RTX_FORMAT (code); 4011 position **subpos_ptr = &pos->xexps; 4012 for (size_t i = 0; fmt[i]; ++i) 4013 { 4014 position *subpos = next_position (subpos_ptr, pos, 4015 POS_XEXP, i); 4016 switch (fmt[i]) 4017 { 4018 case 'e': case 'u': 4019 worklist.safe_push (pattern_pos (XEXP (pattern, i), 4020 subpos)); 4021 break; 4022 4023 case 'E': 4024 { 4025 /* Make sure the vector has the right number of 4026 elements. */ 4027 int length = XVECLEN (pattern, i); 4028 s = add_decision (s, rtx_test::veclen (pos), 4029 length, false); 4030 4031 position **subpos2_ptr = &pos->xvecexp0s; 4032 for (int j = 0; j < length; j++) 4033 { 4034 position *subpos2 = next_position (subpos2_ptr, pos, 4035 POS_XVECEXP0, j); 4036 rtx x = XVECEXP (pattern, i, j); 4037 worklist.safe_push (pattern_pos (x, subpos2)); 4038 subpos2_ptr = &subpos2->next; 4039 } 4040 break; 4041 } 4042 4043 case 'i': 4044 /* Make sure that XINT (X, I) has the right value. */ 4045 s = add_decision (s, rtx_test::int_field (pos, i), 4046 XINT (pattern, i), false); 4047 break; 4048 4049 case 'r': 4050 /* Make sure that REGNO (X) has the right value. */ 4051 gcc_assert (i == 0); 4052 s = add_decision (s, rtx_test::regno_field (pos), 4053 REGNO (pattern), false); 4054 break; 4055 4056 case 'w': 4057 /* Make sure that XWINT (X, I) has the right value. */ 4058 s = add_decision (s, rtx_test::wide_int_field (pos, i), 4059 XWINT (pattern, 0), false); 4060 break; 4061 4062 case 'p': 4063 /* We don't have a way of parsing polynomial offsets yet, 4064 and hopefully never will. */ 4065 s = add_decision (s, rtx_test::subreg_field (pos), 4066 SUBREG_BYTE (pattern).to_constant (), 4067 false); 4068 break; 4069 4070 case '0': 4071 break; 4072 4073 default: 4074 gcc_unreachable (); 4075 } 4076 subpos_ptr = &subpos->next; 4077 } 4078 } 4079 break; 4080 } 4081 /* Operands are pushed onto the worklist so that later indices are 4082 nearer the top. That's what we want for SETs, since a SET_SRC 4083 is a better discriminator than a SET_DEST. In other cases it's 4084 usually better to match earlier indices first. This is especially 4085 true of PARALLELs, where the first element tends to be the most 4086 individual. It's also true for commutative operators, where the 4087 canonicalization rules say that the more complex operand should 4088 come first. */ 4089 if (code != SET && worklist.length () > reverse_s) 4090 std::reverse (&worklist[0] + reverse_s, 4091 &worklist[0] + worklist.length ()); 4092 } 4093 4094 /* Sort the predicate and mode tests so that they're in depth-first order. 4095 The main goal of this is to put SET_SRC match_operands after SET_DEST 4096 match_operands and after mode checks for the enclosing SET_SRC operators 4097 (such as the mode of a PLUS in an addition instruction). The latter 4098 two types of test can determine the mode exactly, whereas a SET_SRC 4099 match_operand often has to cope with the possibility of the operand 4100 being a modeless constant integer. E.g. something that matches 4101 register_operand (x, SImode) never matches register_operand (x, DImode), 4102 but a const_int that matches immediate_operand (x, SImode) also matches 4103 immediate_operand (x, DImode). The register_operand cases can therefore 4104 be distinguished by a switch on the mode, but the immediate_operand 4105 cases can't. */ 4106 if (pred_and_mode_tests.length () > 1) 4107 std::sort (&pred_and_mode_tests[0], 4108 &pred_and_mode_tests[0] + pred_and_mode_tests.length ()); 4109 4110 /* Add the mode and predicate tests. */ 4111 pattern_pos *e; 4112 unsigned int i; 4113 FOR_EACH_VEC_ELT (pred_and_mode_tests, i, e) 4114 { 4115 switch (GET_CODE (e->pattern)) 4116 { 4117 case MATCH_PARALLEL: 4118 case MATCH_OPERAND: 4119 case MATCH_SCRATCH: 4120 case MATCH_OPERATOR: 4121 { 4122 int opno = XINT (e->pattern, 0); 4123 num_operands = MAX (num_operands, opno + 1); 4124 const char *pred_name = predicate_name (e->pattern); 4125 if (pred_name[0]) 4126 { 4127 const struct pred_data *pred = lookup_predicate (pred_name); 4128 /* Check the mode first, to distinguish things like SImode 4129 and DImode register_operands, as described above. */ 4130 machine_mode mode = GET_MODE (e->pattern); 4131 if (pred && safe_predicate_mode (pred, mode)) 4132 s = add_decision (s, rtx_test::mode (e->pos), mode, true); 4133 4134 /* Assign to operands[] first, so that the rtx usually doesn't 4135 need to be live across the call to the predicate. 4136 4137 This shouldn't cause a problem with dirtying the page, 4138 since we fully expect to assign to operands[] at some point, 4139 and since the caller usually writes to other parts of 4140 recog_data anyway. */ 4141 s = add_decision (s, rtx_test::set_op (e->pos, opno), 4142 true, false); 4143 s = add_decision (s, rtx_test::predicate (e->pos, pred, mode), 4144 true, false); 4145 } 4146 else 4147 /* Historically we've ignored the mode when there's no 4148 predicate. Just set up operands[] unconditionally. */ 4149 s = add_decision (s, rtx_test::set_op (e->pos, opno), 4150 true, false); 4151 break; 4152 } 4153 4154 default: 4155 s = add_decision (s, rtx_test::mode (e->pos), 4156 GET_MODE (e->pattern), false); 4157 break; 4158 } 4159 } 4160 4161 /* Finally add rtx_equal_p checks for duplicated operands. */ 4162 FOR_EACH_VEC_ELT (dup_tests, i, e) 4163 s = add_decision (s, rtx_test::duplicate (e->pos, XINT (e->pattern, 0)), 4164 true, false); 4165 return s; 4166 } 4167 4168 /* Add new decisions to S that make it return ACCEPTANCE if: 4169 4170 (1) the rtx doesn't match anything already matched by S 4171 (2) the rtx matches TOP_PATTERN and 4172 (3) the C test required by INFO->def is true 4173 4174 For peephole2, TOP_PATTERN is a SEQUENCE of the instruction patterns 4175 to match, otherwise it is a single instruction pattern. */ 4176 4177 static void 4178 match_pattern_1 (state *s, md_rtx_info *info, rtx pattern, 4179 acceptance_type acceptance) 4180 { 4181 if (acceptance.type == PEEPHOLE2) 4182 { 4183 /* Match each individual instruction. */ 4184 position **subpos_ptr = &peep2_insn_pos_list; 4185 int count = 0; 4186 for (int i = 0; i < XVECLEN (pattern, 0); ++i) 4187 { 4188 rtx x = XVECEXP (pattern, 0, i); 4189 position *subpos = next_position (subpos_ptr, &root_pos, 4190 POS_PEEP2_INSN, count); 4191 if (count > 0) 4192 s = add_decision (s, rtx_test::peep2_count (count + 1), 4193 true, false); 4194 s = match_pattern_2 (s, info, subpos, x); 4195 subpos_ptr = &subpos->next; 4196 count += 1; 4197 } 4198 acceptance.u.full.u.match_len = count - 1; 4199 } 4200 else 4201 { 4202 /* Make the rtx itself. */ 4203 s = match_pattern_2 (s, info, &root_pos, pattern); 4204 4205 /* If the match is only valid when extra clobbers are added, 4206 make sure we're able to pass that information to the caller. */ 4207 if (acceptance.type == RECOG && acceptance.u.full.u.num_clobbers) 4208 s = add_decision (s, rtx_test::have_num_clobbers (), true, false); 4209 } 4210 4211 /* Make sure that the C test is true. */ 4212 const char *c_test = get_c_test (info->def); 4213 if (maybe_eval_c_test (c_test) != 1) 4214 s = add_decision (s, rtx_test::c_test (c_test), true, false); 4215 4216 /* Accept the pattern. */ 4217 add_decision (s, rtx_test::accept (acceptance), true, false); 4218 } 4219 4220 /* Like match_pattern_1, but (if merge_states_p) try to merge the 4221 decisions with what's already in S, to reduce the amount of 4222 backtracking. */ 4223 4224 static void 4225 match_pattern (state *s, md_rtx_info *info, rtx pattern, 4226 acceptance_type acceptance) 4227 { 4228 if (merge_states_p) 4229 { 4230 state root; 4231 /* Add the decisions to a fresh state and then merge the full tree 4232 into the existing one. */ 4233 match_pattern_1 (&root, info, pattern, acceptance); 4234 merge_into_state (s, &root); 4235 } 4236 else 4237 match_pattern_1 (s, info, pattern, acceptance); 4238 } 4239 4240 /* Begin the output file. */ 4241 4242 static void 4243 write_header (void) 4244 { 4245 puts ("\ 4246 /* Generated automatically by the program `genrecog' from the target\n\ 4247 machine description file. */\n\ 4248 \n\ 4249 #define IN_TARGET_CODE 1\n\ 4250 \n\ 4251 #include \"config.h\"\n\ 4252 #include \"system.h\"\n\ 4253 #include \"coretypes.h\"\n\ 4254 #include \"backend.h\"\n\ 4255 #include \"predict.h\"\n\ 4256 #include \"rtl.h\"\n\ 4257 #include \"memmodel.h\"\n\ 4258 #include \"tm_p.h\"\n\ 4259 #include \"emit-rtl.h\"\n\ 4260 #include \"insn-config.h\"\n\ 4261 #include \"recog.h\"\n\ 4262 #include \"output.h\"\n\ 4263 #include \"flags.h\"\n\ 4264 #include \"df.h\"\n\ 4265 #include \"resource.h\"\n\ 4266 #include \"diagnostic-core.h\"\n\ 4267 #include \"reload.h\"\n\ 4268 #include \"regs.h\"\n\ 4269 #include \"tm-constrs.h\"\n\ 4270 \n"); 4271 4272 puts ("\n\ 4273 /* `recog' contains a decision tree that recognizes whether the rtx\n\ 4274 X0 is a valid instruction.\n\ 4275 \n\ 4276 recog returns -1 if the rtx is not valid. If the rtx is valid, recog\n\ 4277 returns a nonnegative number which is the insn code number for the\n\ 4278 pattern that matched. This is the same as the order in the machine\n\ 4279 description of the entry that matched. This number can be used as an\n\ 4280 index into `insn_data' and other tables.\n"); 4281 puts ("\ 4282 The third parameter to recog is an optional pointer to an int. If\n\ 4283 present, recog will accept a pattern if it matches except for missing\n\ 4284 CLOBBER expressions at the end. In that case, the value pointed to by\n\ 4285 the optional pointer will be set to the number of CLOBBERs that need\n\ 4286 to be added (it should be initialized to zero by the caller). If it"); 4287 puts ("\ 4288 is set nonzero, the caller should allocate a PARALLEL of the\n\ 4289 appropriate size, copy the initial entries, and call add_clobbers\n\ 4290 (found in insn-emit.c) to fill in the CLOBBERs.\n\ 4291 "); 4292 4293 puts ("\n\ 4294 The function split_insns returns 0 if the rtl could not\n\ 4295 be split or the split rtl as an INSN list if it can be.\n\ 4296 \n\ 4297 The function peephole2_insns returns 0 if the rtl could not\n\ 4298 be matched. If there was a match, the new rtl is returned in an INSN list,\n\ 4299 and LAST_INSN will point to the last recognized insn in the old sequence.\n\ 4300 */\n\n"); 4301 } 4302 4303 /* Return the C type of a parameter with type TYPE. */ 4304 4305 static const char * 4306 parameter_type_string (parameter::type_enum type) 4307 { 4308 switch (type) 4309 { 4310 case parameter::UNSET: 4311 break; 4312 4313 case parameter::CODE: 4314 return "rtx_code"; 4315 4316 case parameter::MODE: 4317 return "machine_mode"; 4318 4319 case parameter::INT: 4320 return "int"; 4321 4322 case parameter::UINT: 4323 return "unsigned int"; 4324 4325 case parameter::WIDE_INT: 4326 return "HOST_WIDE_INT"; 4327 } 4328 gcc_unreachable (); 4329 } 4330 4331 /* Return true if ACCEPTANCE requires only a single C statement even in 4332 a backtracking context. */ 4333 4334 static bool 4335 single_statement_p (const acceptance_type &acceptance) 4336 { 4337 if (acceptance.partial_p) 4338 /* We need to handle failures of the subroutine. */ 4339 return false; 4340 switch (acceptance.type) 4341 { 4342 case SUBPATTERN: 4343 case SPLIT: 4344 return true; 4345 4346 case RECOG: 4347 /* False if we need to assign to pnum_clobbers. */ 4348 return acceptance.u.full.u.num_clobbers == 0; 4349 4350 case PEEPHOLE2: 4351 /* We need to assign to pmatch_len_ and handle null returns from the 4352 peephole2 routine. */ 4353 return false; 4354 } 4355 gcc_unreachable (); 4356 } 4357 4358 /* Return the C failure value for a routine of type TYPE. */ 4359 4360 static const char * 4361 get_failure_return (routine_type type) 4362 { 4363 switch (type) 4364 { 4365 case SUBPATTERN: 4366 case RECOG: 4367 return "-1"; 4368 4369 case SPLIT: 4370 case PEEPHOLE2: 4371 return "NULL"; 4372 } 4373 gcc_unreachable (); 4374 } 4375 4376 /* Indicates whether a block of code always returns or whether it can fall 4377 through. */ 4378 4379 enum exit_state { 4380 ES_RETURNED, 4381 ES_FALLTHROUGH 4382 }; 4383 4384 /* Information used while writing out code. */ 4385 4386 struct output_state 4387 { 4388 /* The type of routine that we're generating. */ 4389 routine_type type; 4390 4391 /* Maps position ids to xN variable numbers. The entry is only valid if 4392 it is less than the length of VAR_TO_ID, but this holds for every position 4393 tested by a state when writing out that state. */ 4394 auto_vec <unsigned int> id_to_var; 4395 4396 /* Maps xN variable numbers to position ids. */ 4397 auto_vec <unsigned int> var_to_id; 4398 4399 /* Index N is true if variable xN has already been set. */ 4400 auto_vec <bool> seen_vars; 4401 }; 4402 4403 /* Return true if D is a call to a pattern routine and if there is some X 4404 such that the transition for pattern result N goes to a successful return 4405 with code X+N. When returning true, set *BASE_OUT to this X and *COUNT_OUT 4406 to the number of return values. (We know that every PATTERN decision has 4407 a transition for every successful return.) */ 4408 4409 static bool 4410 terminal_pattern_p (decision *d, unsigned int *base_out, 4411 unsigned int *count_out) 4412 { 4413 if (d->test.kind != rtx_test::PATTERN) 4414 return false; 4415 unsigned int base = 0; 4416 unsigned int count = 0; 4417 for (transition *trans = d->first; trans; trans = trans->next) 4418 { 4419 if (trans->is_param || trans->labels.length () != 1) 4420 return false; 4421 decision *subd = trans->to->singleton (); 4422 if (!subd || subd->test.kind != rtx_test::ACCEPT) 4423 return false; 4424 unsigned int this_base = (subd->test.u.acceptance.u.full.code 4425 - trans->labels[0]); 4426 if (trans == d->first) 4427 base = this_base; 4428 else if (base != this_base) 4429 return false; 4430 count += 1; 4431 } 4432 *base_out = base; 4433 *count_out = count; 4434 return true; 4435 } 4436 4437 /* Return true if TEST doesn't test an rtx or if the rtx it tests is 4438 already available in state OS. */ 4439 4440 static bool 4441 test_position_available_p (output_state *os, const rtx_test &test) 4442 { 4443 return (!test.pos 4444 || test.pos_operand >= 0 4445 || os->seen_vars[os->id_to_var[test.pos->id]]); 4446 } 4447 4448 /* Like printf, but print INDENT spaces at the beginning. */ 4449 4450 static void ATTRIBUTE_PRINTF_2 4451 printf_indent (unsigned int indent, const char *format, ...) 4452 { 4453 va_list ap; 4454 va_start (ap, format); 4455 printf ("%*s", indent, ""); 4456 vprintf (format, ap); 4457 va_end (ap); 4458 } 4459 4460 /* Emit code to initialize the variable associated with POS, if it isn't 4461 already valid in state OS. Indent each line by INDENT spaces. Update 4462 OS with the new state. */ 4463 4464 static void 4465 change_state (output_state *os, position *pos, unsigned int indent) 4466 { 4467 unsigned int var = os->id_to_var[pos->id]; 4468 gcc_assert (var < os->var_to_id.length () && os->var_to_id[var] == pos->id); 4469 if (os->seen_vars[var]) 4470 return; 4471 switch (pos->type) 4472 { 4473 case POS_PEEP2_INSN: 4474 printf_indent (indent, "x%d = PATTERN (peep2_next_insn (%d));\n", 4475 var, pos->arg); 4476 break; 4477 4478 case POS_XEXP: 4479 change_state (os, pos->base, indent); 4480 printf_indent (indent, "x%d = XEXP (x%d, %d);\n", 4481 var, os->id_to_var[pos->base->id], pos->arg); 4482 break; 4483 4484 case POS_XVECEXP0: 4485 change_state (os, pos->base, indent); 4486 printf_indent (indent, "x%d = XVECEXP (x%d, 0, %d);\n", 4487 var, os->id_to_var[pos->base->id], pos->arg); 4488 break; 4489 } 4490 os->seen_vars[var] = true; 4491 } 4492 4493 /* Print the enumerator constant for CODE -- the upcase version of 4494 the name. */ 4495 4496 static void 4497 print_code (enum rtx_code code) 4498 { 4499 const char *p; 4500 for (p = GET_RTX_NAME (code); *p; p++) 4501 putchar (TOUPPER (*p)); 4502 } 4503 4504 /* Emit a uint64_t as an integer constant expression. We need to take 4505 special care to avoid "decimal constant is so large that it is unsigned" 4506 warnings in the resulting code. */ 4507 4508 static void 4509 print_host_wide_int (uint64_t val) 4510 { 4511 uint64_t min = uint64_t (1) << (HOST_BITS_PER_WIDE_INT - 1); 4512 if (val == min) 4513 printf ("(" HOST_WIDE_INT_PRINT_DEC_C " - 1)", val + 1); 4514 else 4515 printf (HOST_WIDE_INT_PRINT_DEC_C, val); 4516 } 4517 4518 /* Print the C expression for actual parameter PARAM. */ 4519 4520 static void 4521 print_parameter_value (const parameter ¶m) 4522 { 4523 if (param.is_param) 4524 printf ("i%d", (int) param.value + 1); 4525 else 4526 switch (param.type) 4527 { 4528 case parameter::UNSET: 4529 gcc_unreachable (); 4530 break; 4531 4532 case parameter::CODE: 4533 print_code ((enum rtx_code) param.value); 4534 break; 4535 4536 case parameter::MODE: 4537 printf ("E_%smode", GET_MODE_NAME ((machine_mode) param.value)); 4538 break; 4539 4540 case parameter::INT: 4541 printf ("%d", (int) param.value); 4542 break; 4543 4544 case parameter::UINT: 4545 printf ("%u", (unsigned int) param.value); 4546 break; 4547 4548 case parameter::WIDE_INT: 4549 print_host_wide_int (param.value); 4550 break; 4551 } 4552 } 4553 4554 /* Print the C expression for the rtx tested by TEST. */ 4555 4556 static void 4557 print_test_rtx (output_state *os, const rtx_test &test) 4558 { 4559 if (test.pos_operand >= 0) 4560 printf ("operands[%d]", test.pos_operand); 4561 else 4562 printf ("x%d", os->id_to_var[test.pos->id]); 4563 } 4564 4565 /* Print the C expression for non-boolean test TEST. */ 4566 4567 static void 4568 print_nonbool_test (output_state *os, const rtx_test &test) 4569 { 4570 switch (test.kind) 4571 { 4572 case rtx_test::CODE: 4573 printf ("GET_CODE ("); 4574 print_test_rtx (os, test); 4575 printf (")"); 4576 break; 4577 4578 case rtx_test::MODE: 4579 printf ("GET_MODE ("); 4580 print_test_rtx (os, test); 4581 printf (")"); 4582 break; 4583 4584 case rtx_test::VECLEN: 4585 printf ("XVECLEN ("); 4586 print_test_rtx (os, test); 4587 printf (", 0)"); 4588 break; 4589 4590 case rtx_test::INT_FIELD: 4591 printf ("XINT ("); 4592 print_test_rtx (os, test); 4593 printf (", %d)", test.u.opno); 4594 break; 4595 4596 case rtx_test::REGNO_FIELD: 4597 printf ("REGNO ("); 4598 print_test_rtx (os, test); 4599 printf (")"); 4600 break; 4601 4602 case rtx_test::SUBREG_FIELD: 4603 printf ("SUBREG_BYTE ("); 4604 print_test_rtx (os, test); 4605 printf (")"); 4606 break; 4607 4608 case rtx_test::WIDE_INT_FIELD: 4609 printf ("XWINT ("); 4610 print_test_rtx (os, test); 4611 printf (", %d)", test.u.opno); 4612 break; 4613 4614 case rtx_test::PATTERN: 4615 { 4616 pattern_routine *routine = test.u.pattern->routine; 4617 printf ("pattern%d (", routine->pattern_id); 4618 const char *sep = ""; 4619 if (test.pos) 4620 { 4621 print_test_rtx (os, test); 4622 sep = ", "; 4623 } 4624 if (routine->insn_p) 4625 { 4626 printf ("%sinsn", sep); 4627 sep = ", "; 4628 } 4629 if (routine->pnum_clobbers_p) 4630 { 4631 printf ("%spnum_clobbers", sep); 4632 sep = ", "; 4633 } 4634 for (unsigned int i = 0; i < test.u.pattern->params.length (); ++i) 4635 { 4636 fputs (sep, stdout); 4637 print_parameter_value (test.u.pattern->params[i]); 4638 sep = ", "; 4639 } 4640 printf (")"); 4641 break; 4642 } 4643 4644 case rtx_test::PEEP2_COUNT: 4645 case rtx_test::VECLEN_GE: 4646 case rtx_test::SAVED_CONST_INT: 4647 case rtx_test::DUPLICATE: 4648 case rtx_test::PREDICATE: 4649 case rtx_test::SET_OP: 4650 case rtx_test::HAVE_NUM_CLOBBERS: 4651 case rtx_test::C_TEST: 4652 case rtx_test::ACCEPT: 4653 gcc_unreachable (); 4654 } 4655 } 4656 4657 /* IS_PARAM and LABEL are taken from a transition whose source 4658 decision performs TEST. Print the C code for the label. */ 4659 4660 static void 4661 print_label_value (const rtx_test &test, bool is_param, uint64_t value) 4662 { 4663 print_parameter_value (parameter (transition_parameter_type (test.kind), 4664 is_param, value)); 4665 } 4666 4667 /* If IS_PARAM, print code to compare TEST with the C variable i<VALUE+1>. 4668 If !IS_PARAM, print code to compare TEST with the C constant VALUE. 4669 Test for inequality if INVERT_P, otherwise test for equality. */ 4670 4671 static void 4672 print_test (output_state *os, const rtx_test &test, bool is_param, 4673 uint64_t value, bool invert_p) 4674 { 4675 switch (test.kind) 4676 { 4677 /* Handle the non-boolean TESTs. */ 4678 case rtx_test::CODE: 4679 case rtx_test::MODE: 4680 case rtx_test::VECLEN: 4681 case rtx_test::REGNO_FIELD: 4682 case rtx_test::INT_FIELD: 4683 case rtx_test::WIDE_INT_FIELD: 4684 case rtx_test::PATTERN: 4685 print_nonbool_test (os, test); 4686 printf (" %s ", invert_p ? "!=" : "=="); 4687 print_label_value (test, is_param, value); 4688 break; 4689 4690 case rtx_test::SUBREG_FIELD: 4691 printf ("%s (", invert_p ? "maybe_ne" : "known_eq"); 4692 print_nonbool_test (os, test); 4693 printf (", "); 4694 print_label_value (test, is_param, value); 4695 printf (")"); 4696 break; 4697 4698 case rtx_test::SAVED_CONST_INT: 4699 gcc_assert (!is_param && value == 1); 4700 print_test_rtx (os, test); 4701 printf (" %s const_int_rtx[MAX_SAVED_CONST_INT + ", 4702 invert_p ? "!=" : "=="); 4703 print_parameter_value (parameter (parameter::INT, 4704 test.u.integer.is_param, 4705 test.u.integer.value)); 4706 printf ("]"); 4707 break; 4708 4709 case rtx_test::PEEP2_COUNT: 4710 gcc_assert (!is_param && value == 1); 4711 printf ("peep2_current_count %s %d", invert_p ? "<" : ">=", 4712 test.u.min_len); 4713 break; 4714 4715 case rtx_test::VECLEN_GE: 4716 gcc_assert (!is_param && value == 1); 4717 printf ("XVECLEN ("); 4718 print_test_rtx (os, test); 4719 printf (", 0) %s %d", invert_p ? "<" : ">=", test.u.min_len); 4720 break; 4721 4722 case rtx_test::PREDICATE: 4723 gcc_assert (!is_param && value == 1); 4724 printf ("%s%s (", invert_p ? "!" : "", test.u.predicate.data->name); 4725 print_test_rtx (os, test); 4726 printf (", "); 4727 print_parameter_value (parameter (parameter::MODE, 4728 test.u.predicate.mode_is_param, 4729 test.u.predicate.mode)); 4730 printf (")"); 4731 break; 4732 4733 case rtx_test::DUPLICATE: 4734 gcc_assert (!is_param && value == 1); 4735 printf ("%srtx_equal_p (", invert_p ? "!" : ""); 4736 print_test_rtx (os, test); 4737 printf (", operands[%d])", test.u.opno); 4738 break; 4739 4740 case rtx_test::HAVE_NUM_CLOBBERS: 4741 gcc_assert (!is_param && value == 1); 4742 printf ("pnum_clobbers %s NULL", invert_p ? "==" : "!="); 4743 break; 4744 4745 case rtx_test::C_TEST: 4746 gcc_assert (!is_param && value == 1); 4747 if (invert_p) 4748 printf ("!"); 4749 rtx_reader_ptr->print_c_condition (test.u.string); 4750 break; 4751 4752 case rtx_test::ACCEPT: 4753 case rtx_test::SET_OP: 4754 gcc_unreachable (); 4755 } 4756 } 4757 4758 static exit_state print_decision (output_state *, decision *, 4759 unsigned int, bool); 4760 4761 /* Print code to perform S, indent each line by INDENT spaces. 4762 IS_FINAL is true if there are no fallback decisions to test on failure; 4763 if the state fails then the entire routine fails. */ 4764 4765 static exit_state 4766 print_state (output_state *os, state *s, unsigned int indent, bool is_final) 4767 { 4768 exit_state es = ES_FALLTHROUGH; 4769 for (decision *d = s->first; d; d = d->next) 4770 es = print_decision (os, d, indent, is_final && !d->next); 4771 if (es != ES_RETURNED && is_final) 4772 { 4773 printf_indent (indent, "return %s;\n", get_failure_return (os->type)); 4774 es = ES_RETURNED; 4775 } 4776 return es; 4777 } 4778 4779 /* Print the code for subroutine call ACCEPTANCE (for which partial_p 4780 is known to be true). Return the C condition that indicates a successful 4781 match. */ 4782 4783 static const char * 4784 print_subroutine_call (const acceptance_type &acceptance) 4785 { 4786 switch (acceptance.type) 4787 { 4788 case SUBPATTERN: 4789 gcc_unreachable (); 4790 4791 case RECOG: 4792 printf ("recog_%d (x1, insn, pnum_clobbers)", 4793 acceptance.u.subroutine_id); 4794 return ">= 0"; 4795 4796 case SPLIT: 4797 printf ("split_%d (x1, insn)", acceptance.u.subroutine_id); 4798 return "!= NULL_RTX"; 4799 4800 case PEEPHOLE2: 4801 printf ("peephole2_%d (x1, insn, pmatch_len_)", 4802 acceptance.u.subroutine_id); 4803 return "!= NULL_RTX"; 4804 } 4805 gcc_unreachable (); 4806 } 4807 4808 /* Print code for the successful match described by ACCEPTANCE. 4809 INDENT and IS_FINAL are as for print_state. */ 4810 4811 static exit_state 4812 print_acceptance (const acceptance_type &acceptance, unsigned int indent, 4813 bool is_final) 4814 { 4815 if (acceptance.partial_p) 4816 { 4817 /* Defer the rest of the match to a subroutine. */ 4818 if (is_final) 4819 { 4820 printf_indent (indent, "return "); 4821 print_subroutine_call (acceptance); 4822 printf (";\n"); 4823 return ES_RETURNED; 4824 } 4825 else 4826 { 4827 printf_indent (indent, "res = "); 4828 const char *res_test = print_subroutine_call (acceptance); 4829 printf (";\n"); 4830 printf_indent (indent, "if (res %s)\n", res_test); 4831 printf_indent (indent + 2, "return res;\n"); 4832 return ES_FALLTHROUGH; 4833 } 4834 } 4835 switch (acceptance.type) 4836 { 4837 case SUBPATTERN: 4838 printf_indent (indent, "return %d;\n", acceptance.u.full.code); 4839 return ES_RETURNED; 4840 4841 case RECOG: 4842 if (acceptance.u.full.u.num_clobbers != 0) 4843 printf_indent (indent, "*pnum_clobbers = %d;\n", 4844 acceptance.u.full.u.num_clobbers); 4845 printf_indent (indent, "return %d; /* %s */\n", acceptance.u.full.code, 4846 get_insn_name (acceptance.u.full.code)); 4847 return ES_RETURNED; 4848 4849 case SPLIT: 4850 printf_indent (indent, "return gen_split_%d (insn, operands);\n", 4851 acceptance.u.full.code); 4852 return ES_RETURNED; 4853 4854 case PEEPHOLE2: 4855 printf_indent (indent, "*pmatch_len_ = %d;\n", 4856 acceptance.u.full.u.match_len); 4857 if (is_final) 4858 { 4859 printf_indent (indent, "return gen_peephole2_%d (insn, operands);\n", 4860 acceptance.u.full.code); 4861 return ES_RETURNED; 4862 } 4863 else 4864 { 4865 printf_indent (indent, "res = gen_peephole2_%d (insn, operands);\n", 4866 acceptance.u.full.code); 4867 printf_indent (indent, "if (res != NULL_RTX)\n"); 4868 printf_indent (indent + 2, "return res;\n"); 4869 return ES_FALLTHROUGH; 4870 } 4871 } 4872 gcc_unreachable (); 4873 } 4874 4875 /* Print code to perform D. INDENT and IS_FINAL are as for print_state. */ 4876 4877 static exit_state 4878 print_decision (output_state *os, decision *d, unsigned int indent, 4879 bool is_final) 4880 { 4881 uint64_t label; 4882 unsigned int base, count; 4883 4884 /* Make sure the rtx under test is available either in operands[] or 4885 in an xN variable. */ 4886 if (d->test.pos && d->test.pos_operand < 0) 4887 change_state (os, d->test.pos, indent); 4888 4889 /* Look for cases where a pattern routine P1 calls another pattern routine 4890 P2 and where P1 returns X + BASE whenever P2 returns X. If IS_FINAL 4891 is true and BASE is zero we can simply use: 4892 4893 return patternN (...); 4894 4895 Otherwise we can use: 4896 4897 res = patternN (...); 4898 if (res >= 0) 4899 return res + BASE; 4900 4901 However, if BASE is nonzero and patternN only returns 0 or -1, 4902 the usual "return BASE;" is better than "return res + BASE;". 4903 If BASE is zero, "return res;" should be better than "return 0;", 4904 since no assignment to the return register is required. */ 4905 if (os->type == SUBPATTERN 4906 && terminal_pattern_p (d, &base, &count) 4907 && (base == 0 || count > 1)) 4908 { 4909 if (is_final && base == 0) 4910 { 4911 printf_indent (indent, "return "); 4912 print_nonbool_test (os, d->test); 4913 printf ("; /* [-1, %d] */\n", count - 1); 4914 return ES_RETURNED; 4915 } 4916 else 4917 { 4918 printf_indent (indent, "res = "); 4919 print_nonbool_test (os, d->test); 4920 printf (";\n"); 4921 printf_indent (indent, "if (res >= 0)\n"); 4922 printf_indent (indent + 2, "return res"); 4923 if (base != 0) 4924 printf (" + %d", base); 4925 printf ("; /* [%d, %d] */\n", base, base + count - 1); 4926 return ES_FALLTHROUGH; 4927 } 4928 } 4929 else if (d->test.kind == rtx_test::ACCEPT) 4930 return print_acceptance (d->test.u.acceptance, indent, is_final); 4931 else if (d->test.kind == rtx_test::SET_OP) 4932 { 4933 printf_indent (indent, "operands[%d] = ", d->test.u.opno); 4934 print_test_rtx (os, d->test); 4935 printf (";\n"); 4936 return print_state (os, d->singleton ()->to, indent, is_final); 4937 } 4938 /* Handle decisions with a single transition and a single transition 4939 label. */ 4940 else if (d->if_statement_p (&label)) 4941 { 4942 transition *trans = d->singleton (); 4943 if (mark_optional_transitions_p && trans->optional) 4944 printf_indent (indent, "/* OPTIONAL IF */\n"); 4945 4946 /* Print the condition associated with TRANS. Invert it if IS_FINAL, 4947 so that we return immediately on failure and fall through on 4948 success. */ 4949 printf_indent (indent, "if ("); 4950 print_test (os, d->test, trans->is_param, label, is_final); 4951 4952 /* Look for following states that would be handled by this code 4953 on recursion. If they don't need any preparatory statements, 4954 include them in the current "if" statement rather than creating 4955 a new one. */ 4956 for (;;) 4957 { 4958 d = trans->to->singleton (); 4959 if (!d 4960 || d->test.kind == rtx_test::ACCEPT 4961 || d->test.kind == rtx_test::SET_OP 4962 || !d->if_statement_p (&label) 4963 || !test_position_available_p (os, d->test)) 4964 break; 4965 trans = d->first; 4966 printf ("\n"); 4967 if (mark_optional_transitions_p && trans->optional) 4968 printf_indent (indent + 4, "/* OPTIONAL IF */\n"); 4969 printf_indent (indent + 4, "%s ", is_final ? "||" : "&&"); 4970 print_test (os, d->test, trans->is_param, label, is_final); 4971 } 4972 printf (")\n"); 4973 4974 /* Print the conditional code with INDENT + 2 and the fallthrough 4975 code with indent INDENT. */ 4976 state *to = trans->to; 4977 if (is_final) 4978 { 4979 /* We inverted the condition above, so return failure in the 4980 "if" body and fall through to the target of the transition. */ 4981 printf_indent (indent + 2, "return %s;\n", 4982 get_failure_return (os->type)); 4983 return print_state (os, to, indent, is_final); 4984 } 4985 else if (to->singleton () 4986 && to->first->test.kind == rtx_test::ACCEPT 4987 && single_statement_p (to->first->test.u.acceptance)) 4988 { 4989 /* The target of the transition is a simple "return" statement. 4990 It doesn't need any braces and doesn't fall through. */ 4991 if (print_acceptance (to->first->test.u.acceptance, 4992 indent + 2, true) != ES_RETURNED) 4993 gcc_unreachable (); 4994 return ES_FALLTHROUGH; 4995 } 4996 else 4997 { 4998 /* The general case. Output code for the target of the transition 4999 in braces. This will not invalidate any of the xN variables 5000 that are already valid, but we mustn't rely on any that are 5001 set by the "if" body. */ 5002 auto_vec <bool, 32> old_seen; 5003 old_seen.safe_splice (os->seen_vars); 5004 5005 printf_indent (indent + 2, "{\n"); 5006 print_state (os, trans->to, indent + 4, is_final); 5007 printf_indent (indent + 2, "}\n"); 5008 5009 os->seen_vars.truncate (0); 5010 os->seen_vars.splice (old_seen); 5011 return ES_FALLTHROUGH; 5012 } 5013 } 5014 else 5015 { 5016 /* Output the decision as a switch statement. */ 5017 printf_indent (indent, "switch ("); 5018 print_nonbool_test (os, d->test); 5019 printf (")\n"); 5020 5021 /* Each case statement starts with the same set of valid variables. 5022 These are also the only variables will be valid on fallthrough. */ 5023 auto_vec <bool, 32> old_seen; 5024 old_seen.safe_splice (os->seen_vars); 5025 5026 printf_indent (indent + 2, "{\n"); 5027 for (transition *trans = d->first; trans; trans = trans->next) 5028 { 5029 gcc_assert (!trans->is_param); 5030 if (mark_optional_transitions_p && trans->optional) 5031 printf_indent (indent + 2, "/* OPTIONAL CASE */\n"); 5032 for (int_set::iterator j = trans->labels.begin (); 5033 j != trans->labels.end (); ++j) 5034 { 5035 printf_indent (indent + 2, "case "); 5036 print_label_value (d->test, trans->is_param, *j); 5037 printf (":\n"); 5038 } 5039 if (print_state (os, trans->to, indent + 4, is_final)) 5040 { 5041 /* The state can fall through. Add an explicit break. */ 5042 gcc_assert (!is_final); 5043 printf_indent (indent + 4, "break;\n"); 5044 } 5045 printf ("\n"); 5046 5047 /* Restore the original set of valid variables. */ 5048 os->seen_vars.truncate (0); 5049 os->seen_vars.splice (old_seen); 5050 } 5051 /* Add a default case. */ 5052 printf_indent (indent + 2, "default:\n"); 5053 if (is_final) 5054 printf_indent (indent + 4, "return %s;\n", 5055 get_failure_return (os->type)); 5056 else 5057 printf_indent (indent + 4, "break;\n"); 5058 printf_indent (indent + 2, "}\n"); 5059 return is_final ? ES_RETURNED : ES_FALLTHROUGH; 5060 } 5061 } 5062 5063 /* Make sure that OS has a position variable for POS. ROOT_P is true if 5064 POS is the root position for the routine. */ 5065 5066 static void 5067 assign_position_var (output_state *os, position *pos, bool root_p) 5068 { 5069 unsigned int idx = os->id_to_var[pos->id]; 5070 if (idx < os->var_to_id.length () && os->var_to_id[idx] == pos->id) 5071 return; 5072 if (!root_p && pos->type != POS_PEEP2_INSN) 5073 assign_position_var (os, pos->base, false); 5074 os->id_to_var[pos->id] = os->var_to_id.length (); 5075 os->var_to_id.safe_push (pos->id); 5076 } 5077 5078 /* Make sure that OS has the position variables required by S. */ 5079 5080 static void 5081 assign_position_vars (output_state *os, state *s) 5082 { 5083 for (decision *d = s->first; d; d = d->next) 5084 { 5085 /* Positions associated with operands can be read from the 5086 operands[] array. */ 5087 if (d->test.pos && d->test.pos_operand < 0) 5088 assign_position_var (os, d->test.pos, false); 5089 for (transition *trans = d->first; trans; trans = trans->next) 5090 assign_position_vars (os, trans->to); 5091 } 5092 } 5093 5094 /* Print the open brace and variable definitions for a routine that 5095 implements S. ROOT is the deepest rtx from which S can access all 5096 relevant parts of the first instruction it matches. Initialize OS 5097 so that every relevant position has an rtx variable xN and so that 5098 only ROOT's variable has a valid value. */ 5099 5100 static void 5101 print_subroutine_start (output_state *os, state *s, position *root) 5102 { 5103 printf ("{\n rtx * const operands ATTRIBUTE_UNUSED" 5104 " = &recog_data.operand[0];\n"); 5105 os->var_to_id.truncate (0); 5106 os->seen_vars.truncate (0); 5107 if (root) 5108 { 5109 /* Create a fake entry for position 0 so that an id_to_var of 0 5110 is always invalid. This also makes the xN variables naturally 5111 1-based rather than 0-based. */ 5112 os->var_to_id.safe_push (num_positions); 5113 5114 /* Associate ROOT with x1. */ 5115 assign_position_var (os, root, true); 5116 5117 /* Assign xN variables to all other relevant positions. */ 5118 assign_position_vars (os, s); 5119 5120 /* Output the variable declarations (except for ROOT's, which is 5121 passed in as a parameter). */ 5122 unsigned int num_vars = os->var_to_id.length (); 5123 if (num_vars > 2) 5124 { 5125 for (unsigned int i = 2; i < num_vars; ++i) 5126 /* Print 8 rtx variables to a line. */ 5127 printf ("%s x%d", 5128 i == 2 ? " rtx" : (i - 2) % 8 == 0 ? ";\n rtx" : ",", i); 5129 printf (";\n"); 5130 } 5131 5132 /* Say that x1 is valid and the rest aren't. */ 5133 os->seen_vars.safe_grow_cleared (num_vars); 5134 os->seen_vars[1] = true; 5135 } 5136 if (os->type == SUBPATTERN || os->type == RECOG) 5137 printf (" int res ATTRIBUTE_UNUSED;\n"); 5138 else 5139 printf (" rtx_insn *res ATTRIBUTE_UNUSED;\n"); 5140 } 5141 5142 /* Output the definition of pattern routine ROUTINE. */ 5143 5144 static void 5145 print_pattern (output_state *os, pattern_routine *routine) 5146 { 5147 printf ("\nstatic int\npattern%d (", routine->pattern_id); 5148 const char *sep = ""; 5149 /* Add the top-level rtx parameter, if any. */ 5150 if (routine->pos) 5151 { 5152 printf ("%srtx x1", sep); 5153 sep = ", "; 5154 } 5155 /* Add the optional parameters. */ 5156 if (routine->insn_p) 5157 { 5158 /* We can't easily tell whether a C condition actually reads INSN, 5159 so add an ATTRIBUTE_UNUSED just in case. */ 5160 printf ("%srtx_insn *insn ATTRIBUTE_UNUSED", sep); 5161 sep = ", "; 5162 } 5163 if (routine->pnum_clobbers_p) 5164 { 5165 printf ("%sint *pnum_clobbers", sep); 5166 sep = ", "; 5167 } 5168 /* Add the "i" parameters. */ 5169 for (unsigned int i = 0; i < routine->param_types.length (); ++i) 5170 { 5171 printf ("%s%s i%d", sep, 5172 parameter_type_string (routine->param_types[i]), i + 1); 5173 sep = ", "; 5174 } 5175 printf (")\n"); 5176 os->type = SUBPATTERN; 5177 print_subroutine_start (os, routine->s, routine->pos); 5178 print_state (os, routine->s, 2, true); 5179 printf ("}\n"); 5180 } 5181 5182 /* Output a routine of type TYPE that implements S. PROC_ID is the 5183 number of the subroutine associated with S, or 0 if S is the main 5184 routine. */ 5185 5186 static void 5187 print_subroutine (output_state *os, state *s, int proc_id) 5188 { 5189 printf ("\n"); 5190 switch (os->type) 5191 { 5192 case SUBPATTERN: 5193 gcc_unreachable (); 5194 5195 case RECOG: 5196 if (proc_id) 5197 printf ("static int\nrecog_%d", proc_id); 5198 else 5199 printf ("int\nrecog"); 5200 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n" 5201 "\trtx_insn *insn ATTRIBUTE_UNUSED,\n" 5202 "\tint *pnum_clobbers ATTRIBUTE_UNUSED)\n"); 5203 break; 5204 5205 case SPLIT: 5206 if (proc_id) 5207 printf ("static rtx_insn *\nsplit_%d", proc_id); 5208 else 5209 printf ("rtx_insn *\nsplit_insns"); 5210 printf (" (rtx x1 ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED)\n"); 5211 break; 5212 5213 case PEEPHOLE2: 5214 if (proc_id) 5215 printf ("static rtx_insn *\npeephole2_%d", proc_id); 5216 else 5217 printf ("rtx_insn *\npeephole2_insns"); 5218 printf (" (rtx x1 ATTRIBUTE_UNUSED,\n" 5219 "\trtx_insn *insn ATTRIBUTE_UNUSED,\n" 5220 "\tint *pmatch_len_ ATTRIBUTE_UNUSED)\n"); 5221 break; 5222 } 5223 print_subroutine_start (os, s, &root_pos); 5224 if (proc_id == 0) 5225 { 5226 printf (" recog_data.insn = NULL;\n"); 5227 } 5228 print_state (os, s, 2, true); 5229 printf ("}\n"); 5230 } 5231 5232 /* Print out a routine of type TYPE that performs ROOT. */ 5233 5234 static void 5235 print_subroutine_group (output_state *os, routine_type type, state *root) 5236 { 5237 os->type = type; 5238 if (use_subroutines_p) 5239 { 5240 /* Split ROOT up into smaller pieces, both for readability and to 5241 help the compiler. */ 5242 auto_vec <state *> subroutines; 5243 find_subroutines (type, root, subroutines); 5244 5245 /* Output the subroutines (but not ROOT itself). */ 5246 unsigned int i; 5247 state *s; 5248 FOR_EACH_VEC_ELT (subroutines, i, s) 5249 print_subroutine (os, s, i + 1); 5250 } 5251 /* Output the main routine. */ 5252 print_subroutine (os, root, 0); 5253 } 5254 5255 /* Return the rtx pattern for the list of rtxes in a define_peephole2. */ 5256 5257 static rtx 5258 get_peephole2_pattern (md_rtx_info *info) 5259 { 5260 int i, j; 5261 rtvec vec = XVEC (info->def, 0); 5262 rtx pattern = rtx_alloc (SEQUENCE); 5263 XVEC (pattern, 0) = rtvec_alloc (GET_NUM_ELEM (vec)); 5264 for (i = j = 0; i < GET_NUM_ELEM (vec); i++) 5265 { 5266 rtx x = RTVEC_ELT (vec, i); 5267 /* Ignore scratch register requirements. */ 5268 if (GET_CODE (x) != MATCH_SCRATCH && GET_CODE (x) != MATCH_DUP) 5269 { 5270 XVECEXP (pattern, 0, j) = x; 5271 j++; 5272 } 5273 } 5274 XVECLEN (pattern, 0) = j; 5275 if (j == 0) 5276 error_at (info->loc, "empty define_peephole2"); 5277 return pattern; 5278 } 5279 5280 /* Return true if *PATTERN_PTR is a PARALLEL in which at least one trailing 5281 rtx can be added automatically by add_clobbers. If so, update 5282 *ACCEPTANCE_PTR so that its num_clobbers field contains the number 5283 of such trailing rtxes and update *PATTERN_PTR so that it contains 5284 the pattern without those rtxes. */ 5285 5286 static bool 5287 remove_clobbers (acceptance_type *acceptance_ptr, rtx *pattern_ptr) 5288 { 5289 int i; 5290 rtx new_pattern; 5291 5292 /* Find the last non-clobber in the parallel. */ 5293 rtx pattern = *pattern_ptr; 5294 for (i = XVECLEN (pattern, 0); i > 0; i--) 5295 { 5296 rtx x = XVECEXP (pattern, 0, i - 1); 5297 if (GET_CODE (x) != CLOBBER 5298 || (!REG_P (XEXP (x, 0)) 5299 && GET_CODE (XEXP (x, 0)) != MATCH_SCRATCH)) 5300 break; 5301 } 5302 5303 if (i == XVECLEN (pattern, 0)) 5304 return false; 5305 5306 /* Build a similar insn without the clobbers. */ 5307 if (i == 1) 5308 new_pattern = XVECEXP (pattern, 0, 0); 5309 else 5310 { 5311 new_pattern = rtx_alloc (PARALLEL); 5312 XVEC (new_pattern, 0) = rtvec_alloc (i); 5313 for (int j = 0; j < i; ++j) 5314 XVECEXP (new_pattern, 0, j) = XVECEXP (pattern, 0, j); 5315 } 5316 5317 /* Recognize it. */ 5318 acceptance_ptr->u.full.u.num_clobbers = XVECLEN (pattern, 0) - i; 5319 *pattern_ptr = new_pattern; 5320 return true; 5321 } 5322 5323 int 5324 main (int argc, const char **argv) 5325 { 5326 state insn_root, split_root, peephole2_root; 5327 5328 progname = "genrecog"; 5329 5330 if (!init_rtx_reader_args (argc, argv)) 5331 return (FATAL_EXIT_CODE); 5332 5333 write_header (); 5334 5335 /* Read the machine description. */ 5336 5337 md_rtx_info info; 5338 while (read_md_rtx (&info)) 5339 { 5340 rtx def = info.def; 5341 5342 acceptance_type acceptance; 5343 acceptance.partial_p = false; 5344 acceptance.u.full.code = info.index; 5345 5346 rtx pattern; 5347 switch (GET_CODE (def)) 5348 { 5349 case DEFINE_INSN: 5350 { 5351 /* Match the instruction in the original .md form. */ 5352 acceptance.type = RECOG; 5353 acceptance.u.full.u.num_clobbers = 0; 5354 pattern = add_implicit_parallel (XVEC (def, 1)); 5355 validate_pattern (pattern, &info, NULL_RTX, 0); 5356 match_pattern (&insn_root, &info, pattern, acceptance); 5357 5358 /* If the pattern is a PARALLEL with trailing CLOBBERs, 5359 allow recog_for_combine to match without the clobbers. */ 5360 if (GET_CODE (pattern) == PARALLEL 5361 && remove_clobbers (&acceptance, &pattern)) 5362 match_pattern (&insn_root, &info, pattern, acceptance); 5363 break; 5364 } 5365 5366 case DEFINE_SPLIT: 5367 acceptance.type = SPLIT; 5368 pattern = add_implicit_parallel (XVEC (def, 0)); 5369 validate_pattern (pattern, &info, NULL_RTX, 0); 5370 match_pattern (&split_root, &info, pattern, acceptance); 5371 5372 /* Declare the gen_split routine that we'll call if the 5373 pattern matches. The definition comes from insn-emit.c. */ 5374 printf ("extern rtx_insn *gen_split_%d (rtx_insn *, rtx *);\n", 5375 info.index); 5376 break; 5377 5378 case DEFINE_PEEPHOLE2: 5379 acceptance.type = PEEPHOLE2; 5380 pattern = get_peephole2_pattern (&info); 5381 validate_pattern (pattern, &info, NULL_RTX, 0); 5382 match_pattern (&peephole2_root, &info, pattern, acceptance); 5383 5384 /* Declare the gen_peephole2 routine that we'll call if the 5385 pattern matches. The definition comes from insn-emit.c. */ 5386 printf ("extern rtx_insn *gen_peephole2_%d (rtx_insn *, rtx *);\n", 5387 info.index); 5388 break; 5389 5390 default: 5391 /* do nothing */; 5392 } 5393 } 5394 5395 if (have_error) 5396 return FATAL_EXIT_CODE; 5397 5398 puts ("\n\n"); 5399 5400 /* Optimize each routine in turn. */ 5401 optimize_subroutine_group ("recog", &insn_root); 5402 optimize_subroutine_group ("split_insns", &split_root); 5403 optimize_subroutine_group ("peephole2_insns", &peephole2_root); 5404 5405 output_state os; 5406 os.id_to_var.safe_grow_cleared (num_positions); 5407 5408 if (use_pattern_routines_p) 5409 { 5410 /* Look for common patterns and split them out into subroutines. */ 5411 auto_vec <merge_state_info> states; 5412 states.safe_push (&insn_root); 5413 states.safe_push (&split_root); 5414 states.safe_push (&peephole2_root); 5415 split_out_patterns (states); 5416 5417 /* Print out the routines that we just created. */ 5418 unsigned int i; 5419 pattern_routine *routine; 5420 FOR_EACH_VEC_ELT (patterns, i, routine) 5421 print_pattern (&os, routine); 5422 } 5423 5424 /* Print out the matching routines. */ 5425 print_subroutine_group (&os, RECOG, &insn_root); 5426 print_subroutine_group (&os, SPLIT, &split_root); 5427 print_subroutine_group (&os, PEEPHOLE2, &peephole2_root); 5428 5429 fflush (stdout); 5430 return (ferror (stdout) != 0 ? FATAL_EXIT_CODE : SUCCESS_EXIT_CODE); 5431 } 5432