1/* Register renaming for the GNU compiler. 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005 3 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 15 License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING. If not, write to the Free 19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "rtl.h" 27#include "tm_p.h" 28#include "insn-config.h" 29#include "regs.h" 30#include "addresses.h" 31#include "hard-reg-set.h" 32#include "basic-block.h" 33#include "reload.h" 34#include "output.h" 35#include "function.h" 36#include "recog.h" 37#include "flags.h" 38#include "toplev.h" 39#include "obstack.h" 40#include "timevar.h" 41#include "tree-pass.h" 42 43struct du_chain 44{ 45 struct du_chain *next_chain; 46 struct du_chain *next_use; 47 48 rtx insn; 49 rtx *loc; 50 ENUM_BITFIELD(reg_class) cl : 16; 51 unsigned int need_caller_save_reg:1; 52 unsigned int earlyclobber:1; 53}; 54 55enum scan_actions 56{ 57 terminate_all_read, 58 terminate_overlapping_read, 59 terminate_write, 60 terminate_dead, 61 mark_read, 62 mark_write, 63 /* mark_access is for marking the destination regs in 64 REG_FRAME_RELATED_EXPR notes (as if they were read) so that the 65 note is updated properly. */ 66 mark_access 67}; 68 69static const char * const scan_actions_name[] = 70{ 71 "terminate_all_read", 72 "terminate_overlapping_read", 73 "terminate_write", 74 "terminate_dead", 75 "mark_read", 76 "mark_write", 77 "mark_access" 78}; 79 80static struct obstack rename_obstack; 81 82static void do_replace (struct du_chain *, int); 83static void scan_rtx_reg (rtx, rtx *, enum reg_class, 84 enum scan_actions, enum op_type, int); 85static void scan_rtx_address (rtx, rtx *, enum reg_class, 86 enum scan_actions, enum machine_mode); 87static void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions, 88 enum op_type, int); 89static struct du_chain *build_def_use (basic_block); 90static void dump_def_use_chain (struct du_chain *); 91static void note_sets (rtx, rtx, void *); 92static void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx); 93static void merge_overlapping_regs (basic_block, HARD_REG_SET *, 94 struct du_chain *); 95 96/* Called through note_stores from update_life. Find sets of registers, and 97 record them in *DATA (which is actually a HARD_REG_SET *). */ 98 99static void 100note_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data) 101{ 102 HARD_REG_SET *pset = (HARD_REG_SET *) data; 103 unsigned int regno; 104 int nregs; 105 106 if (GET_CODE (x) == SUBREG) 107 x = SUBREG_REG (x); 108 if (!REG_P (x)) 109 return; 110 regno = REGNO (x); 111 nregs = hard_regno_nregs[regno][GET_MODE (x)]; 112 113 /* There must not be pseudos at this point. */ 114 gcc_assert (regno + nregs <= FIRST_PSEUDO_REGISTER); 115 116 while (nregs-- > 0) 117 SET_HARD_REG_BIT (*pset, regno + nregs); 118} 119 120/* Clear all registers from *PSET for which a note of kind KIND can be found 121 in the list NOTES. */ 122 123static void 124clear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes) 125{ 126 rtx note; 127 for (note = notes; note; note = XEXP (note, 1)) 128 if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0))) 129 { 130 rtx reg = XEXP (note, 0); 131 unsigned int regno = REGNO (reg); 132 int nregs = hard_regno_nregs[regno][GET_MODE (reg)]; 133 134 /* There must not be pseudos at this point. */ 135 gcc_assert (regno + nregs <= FIRST_PSEUDO_REGISTER); 136 137 while (nregs-- > 0) 138 CLEAR_HARD_REG_BIT (*pset, regno + nregs); 139 } 140} 141 142/* For a def-use chain CHAIN in basic block B, find which registers overlap 143 its lifetime and set the corresponding bits in *PSET. */ 144 145static void 146merge_overlapping_regs (basic_block b, HARD_REG_SET *pset, 147 struct du_chain *chain) 148{ 149 struct du_chain *t = chain; 150 rtx insn; 151 HARD_REG_SET live; 152 153 REG_SET_TO_HARD_REG_SET (live, b->il.rtl->global_live_at_start); 154 insn = BB_HEAD (b); 155 while (t) 156 { 157 /* Search forward until the next reference to the register to be 158 renamed. */ 159 while (insn != t->insn) 160 { 161 if (INSN_P (insn)) 162 { 163 clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn)); 164 note_stores (PATTERN (insn), note_sets, (void *) &live); 165 /* Only record currently live regs if we are inside the 166 reg's live range. */ 167 if (t != chain) 168 IOR_HARD_REG_SET (*pset, live); 169 clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn)); 170 } 171 insn = NEXT_INSN (insn); 172 } 173 174 IOR_HARD_REG_SET (*pset, live); 175 176 /* For the last reference, also merge in all registers set in the 177 same insn. 178 @@@ We only have take earlyclobbered sets into account. */ 179 if (! t->next_use) 180 note_stores (PATTERN (insn), note_sets, (void *) pset); 181 182 t = t->next_use; 183 } 184} 185 186/* Perform register renaming on the current function. */ 187 188static void 189regrename_optimize (void) 190{ 191 int tick[FIRST_PSEUDO_REGISTER]; 192 int this_tick = 0; 193 basic_block bb; 194 char *first_obj; 195 196 memset (tick, 0, sizeof tick); 197 198 gcc_obstack_init (&rename_obstack); 199 first_obj = obstack_alloc (&rename_obstack, 0); 200 201 FOR_EACH_BB (bb) 202 { 203 struct du_chain *all_chains = 0; 204 HARD_REG_SET unavailable; 205 HARD_REG_SET regs_seen; 206 207 CLEAR_HARD_REG_SET (unavailable); 208 209 if (dump_file) 210 fprintf (dump_file, "\nBasic block %d:\n", bb->index); 211 212 all_chains = build_def_use (bb); 213 214 if (dump_file) 215 dump_def_use_chain (all_chains); 216 217 CLEAR_HARD_REG_SET (unavailable); 218 /* Don't clobber traceback for noreturn functions. */ 219 if (frame_pointer_needed) 220 { 221 int i; 222 223 for (i = hard_regno_nregs[FRAME_POINTER_REGNUM][Pmode]; i--;) 224 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i); 225 226#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 227 for (i = hard_regno_nregs[HARD_FRAME_POINTER_REGNUM][Pmode]; i--;) 228 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i); 229#endif 230 } 231 232 CLEAR_HARD_REG_SET (regs_seen); 233 while (all_chains) 234 { 235 int new_reg, best_new_reg; 236 int n_uses; 237 struct du_chain *this = all_chains; 238 struct du_chain *tmp, *last; 239 HARD_REG_SET this_unavailable; 240 int reg = REGNO (*this->loc); 241 int i; 242 243 all_chains = this->next_chain; 244 245 best_new_reg = reg; 246 247#if 0 /* This just disables optimization opportunities. */ 248 /* Only rename once we've seen the reg more than once. */ 249 if (! TEST_HARD_REG_BIT (regs_seen, reg)) 250 { 251 SET_HARD_REG_BIT (regs_seen, reg); 252 continue; 253 } 254#endif 255 256 if (fixed_regs[reg] || global_regs[reg] 257#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 258 || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) 259#else 260 || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) 261#endif 262 ) 263 continue; 264 265 COPY_HARD_REG_SET (this_unavailable, unavailable); 266 267 /* Find last entry on chain (which has the need_caller_save bit), 268 count number of uses, and narrow the set of registers we can 269 use for renaming. */ 270 n_uses = 0; 271 for (last = this; last->next_use; last = last->next_use) 272 { 273 n_uses++; 274 IOR_COMPL_HARD_REG_SET (this_unavailable, 275 reg_class_contents[last->cl]); 276 } 277 if (n_uses < 1) 278 continue; 279 280 IOR_COMPL_HARD_REG_SET (this_unavailable, 281 reg_class_contents[last->cl]); 282 283 if (this->need_caller_save_reg) 284 IOR_HARD_REG_SET (this_unavailable, call_used_reg_set); 285 286 merge_overlapping_regs (bb, &this_unavailable, this); 287 288 /* Now potential_regs is a reasonable approximation, let's 289 have a closer look at each register still in there. */ 290 for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) 291 { 292 int nregs = hard_regno_nregs[new_reg][GET_MODE (*this->loc)]; 293 294 for (i = nregs - 1; i >= 0; --i) 295 if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) 296 || fixed_regs[new_reg + i] 297 || global_regs[new_reg + i] 298 /* Can't use regs which aren't saved by the prologue. */ 299 || (! regs_ever_live[new_reg + i] 300 && ! call_used_regs[new_reg + i]) 301#ifdef LEAF_REGISTERS 302 /* We can't use a non-leaf register if we're in a 303 leaf function. */ 304 || (current_function_is_leaf 305 && !LEAF_REGISTERS[new_reg + i]) 306#endif 307#ifdef HARD_REGNO_RENAME_OK 308 || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) 309#endif 310 ) 311 break; 312 if (i >= 0) 313 continue; 314 315 /* See whether it accepts all modes that occur in 316 definition and uses. */ 317 for (tmp = this; tmp; tmp = tmp->next_use) 318 if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc)) 319 || (tmp->need_caller_save_reg 320 && ! (HARD_REGNO_CALL_PART_CLOBBERED 321 (reg, GET_MODE (*tmp->loc))) 322 && (HARD_REGNO_CALL_PART_CLOBBERED 323 (new_reg, GET_MODE (*tmp->loc))))) 324 break; 325 if (! tmp) 326 { 327 if (tick[best_new_reg] > tick[new_reg]) 328 best_new_reg = new_reg; 329 } 330 } 331 332 if (dump_file) 333 { 334 fprintf (dump_file, "Register %s in insn %d", 335 reg_names[reg], INSN_UID (last->insn)); 336 if (last->need_caller_save_reg) 337 fprintf (dump_file, " crosses a call"); 338 } 339 340 if (best_new_reg == reg) 341 { 342 tick[reg] = ++this_tick; 343 if (dump_file) 344 fprintf (dump_file, "; no available better choice\n"); 345 continue; 346 } 347 348 do_replace (this, best_new_reg); 349 tick[best_new_reg] = ++this_tick; 350 regs_ever_live[best_new_reg] = 1; 351 352 if (dump_file) 353 fprintf (dump_file, ", renamed as %s\n", reg_names[best_new_reg]); 354 } 355 356 obstack_free (&rename_obstack, first_obj); 357 } 358 359 obstack_free (&rename_obstack, NULL); 360 361 if (dump_file) 362 fputc ('\n', dump_file); 363 364 count_or_remove_death_notes (NULL, 1); 365 update_life_info (NULL, UPDATE_LIFE_LOCAL, 366 PROP_DEATH_NOTES); 367} 368 369static void 370do_replace (struct du_chain *chain, int reg) 371{ 372 while (chain) 373 { 374 unsigned int regno = ORIGINAL_REGNO (*chain->loc); 375 struct reg_attrs * attr = REG_ATTRS (*chain->loc); 376 377 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); 378 if (regno >= FIRST_PSEUDO_REGISTER) 379 ORIGINAL_REGNO (*chain->loc) = regno; 380 REG_ATTRS (*chain->loc) = attr; 381 chain = chain->next_use; 382 } 383} 384 385 386static struct du_chain *open_chains; 387static struct du_chain *closed_chains; 388 389static void 390scan_rtx_reg (rtx insn, rtx *loc, enum reg_class cl, 391 enum scan_actions action, enum op_type type, int earlyclobber) 392{ 393 struct du_chain **p; 394 rtx x = *loc; 395 enum machine_mode mode = GET_MODE (x); 396 int this_regno = REGNO (x); 397 int this_nregs = hard_regno_nregs[this_regno][mode]; 398 399 if (action == mark_write) 400 { 401 if (type == OP_OUT) 402 { 403 struct du_chain *this 404 = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 405 this->next_use = 0; 406 this->next_chain = open_chains; 407 this->loc = loc; 408 this->insn = insn; 409 this->cl = cl; 410 this->need_caller_save_reg = 0; 411 this->earlyclobber = earlyclobber; 412 open_chains = this; 413 } 414 return; 415 } 416 417 if ((type == OP_OUT) != (action == terminate_write || action == mark_access)) 418 return; 419 420 for (p = &open_chains; *p;) 421 { 422 struct du_chain *this = *p; 423 424 /* Check if the chain has been terminated if it has then skip to 425 the next chain. 426 427 This can happen when we've already appended the location to 428 the chain in Step 3, but are trying to hide in-out operands 429 from terminate_write in Step 5. */ 430 431 if (*this->loc == cc0_rtx) 432 p = &this->next_chain; 433 else 434 { 435 int regno = REGNO (*this->loc); 436 int nregs = hard_regno_nregs[regno][GET_MODE (*this->loc)]; 437 int exact_match = (regno == this_regno && nregs == this_nregs); 438 439 if (regno + nregs <= this_regno 440 || this_regno + this_nregs <= regno) 441 { 442 p = &this->next_chain; 443 continue; 444 } 445 446 if (action == mark_read || action == mark_access) 447 { 448 gcc_assert (exact_match); 449 450 /* ??? Class NO_REGS can happen if the md file makes use of 451 EXTRA_CONSTRAINTS to match registers. Which is arguably 452 wrong, but there we are. Since we know not what this may 453 be replaced with, terminate the chain. */ 454 if (cl != NO_REGS) 455 { 456 this = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 457 this->next_use = 0; 458 this->next_chain = (*p)->next_chain; 459 this->loc = loc; 460 this->insn = insn; 461 this->cl = cl; 462 this->need_caller_save_reg = 0; 463 while (*p) 464 p = &(*p)->next_use; 465 *p = this; 466 return; 467 } 468 } 469 470 if (action != terminate_overlapping_read || ! exact_match) 471 { 472 struct du_chain *next = this->next_chain; 473 474 /* Whether the terminated chain can be used for renaming 475 depends on the action and this being an exact match. 476 In either case, we remove this element from open_chains. */ 477 478 if ((action == terminate_dead || action == terminate_write) 479 && exact_match) 480 { 481 this->next_chain = closed_chains; 482 closed_chains = this; 483 if (dump_file) 484 fprintf (dump_file, 485 "Closing chain %s at insn %d (%s)\n", 486 reg_names[REGNO (*this->loc)], INSN_UID (insn), 487 scan_actions_name[(int) action]); 488 } 489 else 490 { 491 if (dump_file) 492 fprintf (dump_file, 493 "Discarding chain %s at insn %d (%s)\n", 494 reg_names[REGNO (*this->loc)], INSN_UID (insn), 495 scan_actions_name[(int) action]); 496 } 497 *p = next; 498 } 499 else 500 p = &this->next_chain; 501 } 502 } 503} 504 505/* Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or 506 BASE_REG_CLASS depending on how the register is being considered. */ 507 508static void 509scan_rtx_address (rtx insn, rtx *loc, enum reg_class cl, 510 enum scan_actions action, enum machine_mode mode) 511{ 512 rtx x = *loc; 513 RTX_CODE code = GET_CODE (x); 514 const char *fmt; 515 int i, j; 516 517 if (action == mark_write || action == mark_access) 518 return; 519 520 switch (code) 521 { 522 case PLUS: 523 { 524 rtx orig_op0 = XEXP (x, 0); 525 rtx orig_op1 = XEXP (x, 1); 526 RTX_CODE code0 = GET_CODE (orig_op0); 527 RTX_CODE code1 = GET_CODE (orig_op1); 528 rtx op0 = orig_op0; 529 rtx op1 = orig_op1; 530 rtx *locI = NULL; 531 rtx *locB = NULL; 532 enum rtx_code index_code = SCRATCH; 533 534 if (GET_CODE (op0) == SUBREG) 535 { 536 op0 = SUBREG_REG (op0); 537 code0 = GET_CODE (op0); 538 } 539 540 if (GET_CODE (op1) == SUBREG) 541 { 542 op1 = SUBREG_REG (op1); 543 code1 = GET_CODE (op1); 544 } 545 546 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 547 || code0 == ZERO_EXTEND || code1 == MEM) 548 { 549 locI = &XEXP (x, 0); 550 locB = &XEXP (x, 1); 551 index_code = GET_CODE (*locI); 552 } 553 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 554 || code1 == ZERO_EXTEND || code0 == MEM) 555 { 556 locI = &XEXP (x, 1); 557 locB = &XEXP (x, 0); 558 index_code = GET_CODE (*locI); 559 } 560 else if (code0 == CONST_INT || code0 == CONST 561 || code0 == SYMBOL_REF || code0 == LABEL_REF) 562 { 563 locB = &XEXP (x, 1); 564 index_code = GET_CODE (XEXP (x, 0)); 565 } 566 else if (code1 == CONST_INT || code1 == CONST 567 || code1 == SYMBOL_REF || code1 == LABEL_REF) 568 { 569 locB = &XEXP (x, 0); 570 index_code = GET_CODE (XEXP (x, 1)); 571 } 572 else if (code0 == REG && code1 == REG) 573 { 574 int index_op; 575 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1); 576 577 if (REGNO_OK_FOR_INDEX_P (regno0) 578 && regno_ok_for_base_p (regno1, mode, PLUS, REG)) 579 index_op = 0; 580 else if (REGNO_OK_FOR_INDEX_P (regno1) 581 && regno_ok_for_base_p (regno0, mode, PLUS, REG)) 582 index_op = 1; 583 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG)) 584 index_op = 0; 585 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)) 586 index_op = 1; 587 else if (REGNO_OK_FOR_INDEX_P (regno1)) 588 index_op = 1; 589 else 590 index_op = 0; 591 592 locI = &XEXP (x, index_op); 593 locB = &XEXP (x, !index_op); 594 index_code = GET_CODE (*locI); 595 } 596 else if (code0 == REG) 597 { 598 locI = &XEXP (x, 0); 599 locB = &XEXP (x, 1); 600 index_code = GET_CODE (*locI); 601 } 602 else if (code1 == REG) 603 { 604 locI = &XEXP (x, 1); 605 locB = &XEXP (x, 0); 606 index_code = GET_CODE (*locI); 607 } 608 609 if (locI) 610 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode); 611 if (locB) 612 scan_rtx_address (insn, locB, base_reg_class (mode, PLUS, index_code), 613 action, mode); 614 615 return; 616 } 617 618 case POST_INC: 619 case POST_DEC: 620 case POST_MODIFY: 621 case PRE_INC: 622 case PRE_DEC: 623 case PRE_MODIFY: 624#ifndef AUTO_INC_DEC 625 /* If the target doesn't claim to handle autoinc, this must be 626 something special, like a stack push. Kill this chain. */ 627 action = terminate_all_read; 628#endif 629 break; 630 631 case MEM: 632 scan_rtx_address (insn, &XEXP (x, 0), 633 base_reg_class (GET_MODE (x), MEM, SCRATCH), action, 634 GET_MODE (x)); 635 return; 636 637 case REG: 638 scan_rtx_reg (insn, loc, cl, action, OP_IN, 0); 639 return; 640 641 default: 642 break; 643 } 644 645 fmt = GET_RTX_FORMAT (code); 646 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 647 { 648 if (fmt[i] == 'e') 649 scan_rtx_address (insn, &XEXP (x, i), cl, action, mode); 650 else if (fmt[i] == 'E') 651 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 652 scan_rtx_address (insn, &XVECEXP (x, i, j), cl, action, mode); 653 } 654} 655 656static void 657scan_rtx (rtx insn, rtx *loc, enum reg_class cl, 658 enum scan_actions action, enum op_type type, int earlyclobber) 659{ 660 const char *fmt; 661 rtx x = *loc; 662 enum rtx_code code = GET_CODE (x); 663 int i, j; 664 665 code = GET_CODE (x); 666 switch (code) 667 { 668 case CONST: 669 case CONST_INT: 670 case CONST_DOUBLE: 671 case CONST_VECTOR: 672 case SYMBOL_REF: 673 case LABEL_REF: 674 case CC0: 675 case PC: 676 return; 677 678 case REG: 679 scan_rtx_reg (insn, loc, cl, action, type, earlyclobber); 680 return; 681 682 case MEM: 683 scan_rtx_address (insn, &XEXP (x, 0), 684 base_reg_class (GET_MODE (x), MEM, SCRATCH), action, 685 GET_MODE (x)); 686 return; 687 688 case SET: 689 scan_rtx (insn, &SET_SRC (x), cl, action, OP_IN, 0); 690 scan_rtx (insn, &SET_DEST (x), cl, action, 691 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0); 692 return; 693 694 case STRICT_LOW_PART: 695 scan_rtx (insn, &XEXP (x, 0), cl, action, OP_INOUT, earlyclobber); 696 return; 697 698 case ZERO_EXTRACT: 699 case SIGN_EXTRACT: 700 scan_rtx (insn, &XEXP (x, 0), cl, action, 701 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber); 702 scan_rtx (insn, &XEXP (x, 1), cl, action, OP_IN, 0); 703 scan_rtx (insn, &XEXP (x, 2), cl, action, OP_IN, 0); 704 return; 705 706 case POST_INC: 707 case PRE_INC: 708 case POST_DEC: 709 case PRE_DEC: 710 case POST_MODIFY: 711 case PRE_MODIFY: 712 /* Should only happen inside MEM. */ 713 gcc_unreachable (); 714 715 case CLOBBER: 716 scan_rtx (insn, &SET_DEST (x), cl, action, 717 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0); 718 return; 719 720 case EXPR_LIST: 721 scan_rtx (insn, &XEXP (x, 0), cl, action, type, 0); 722 if (XEXP (x, 1)) 723 scan_rtx (insn, &XEXP (x, 1), cl, action, type, 0); 724 return; 725 726 default: 727 break; 728 } 729 730 fmt = GET_RTX_FORMAT (code); 731 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 732 { 733 if (fmt[i] == 'e') 734 scan_rtx (insn, &XEXP (x, i), cl, action, type, 0); 735 else if (fmt[i] == 'E') 736 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 737 scan_rtx (insn, &XVECEXP (x, i, j), cl, action, type, 0); 738 } 739} 740 741/* Build def/use chain. */ 742 743static struct du_chain * 744build_def_use (basic_block bb) 745{ 746 rtx insn; 747 748 open_chains = closed_chains = NULL; 749 750 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 751 { 752 if (INSN_P (insn)) 753 { 754 int n_ops; 755 rtx note; 756 rtx old_operands[MAX_RECOG_OPERANDS]; 757 rtx old_dups[MAX_DUP_OPERANDS]; 758 int i, icode; 759 int alt; 760 int predicated; 761 762 /* Process the insn, determining its effect on the def-use 763 chains. We perform the following steps with the register 764 references in the insn: 765 (1) Any read that overlaps an open chain, but doesn't exactly 766 match, causes that chain to be closed. We can't deal 767 with overlaps yet. 768 (2) Any read outside an operand causes any chain it overlaps 769 with to be closed, since we can't replace it. 770 (3) Any read inside an operand is added if there's already 771 an open chain for it. 772 (4) For any REG_DEAD note we find, close open chains that 773 overlap it. 774 (5) For any write we find, close open chains that overlap it. 775 (6) For any write we find in an operand, make a new chain. 776 (7) For any REG_UNUSED, close any chains we just opened. */ 777 778 icode = recog_memoized (insn); 779 extract_insn (insn); 780 if (! constrain_operands (1)) 781 fatal_insn_not_found (insn); 782 preprocess_constraints (); 783 alt = which_alternative; 784 n_ops = recog_data.n_operands; 785 786 /* Simplify the code below by rewriting things to reflect 787 matching constraints. Also promote OP_OUT to OP_INOUT 788 in predicated instructions. */ 789 790 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 791 for (i = 0; i < n_ops; ++i) 792 { 793 int matches = recog_op_alt[i][alt].matches; 794 if (matches >= 0) 795 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl; 796 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 797 || (predicated && recog_data.operand_type[i] == OP_OUT)) 798 recog_data.operand_type[i] = OP_INOUT; 799 } 800 801 /* Step 1: Close chains for which we have overlapping reads. */ 802 for (i = 0; i < n_ops; i++) 803 scan_rtx (insn, recog_data.operand_loc[i], 804 NO_REGS, terminate_overlapping_read, 805 recog_data.operand_type[i], 0); 806 807 /* Step 2: Close chains for which we have reads outside operands. 808 We do this by munging all operands into CC0, and closing 809 everything remaining. */ 810 811 for (i = 0; i < n_ops; i++) 812 { 813 old_operands[i] = recog_data.operand[i]; 814 /* Don't squash match_operator or match_parallel here, since 815 we don't know that all of the contained registers are 816 reachable by proper operands. */ 817 if (recog_data.constraints[i][0] == '\0') 818 continue; 819 *recog_data.operand_loc[i] = cc0_rtx; 820 } 821 for (i = 0; i < recog_data.n_dups; i++) 822 { 823 int dup_num = recog_data.dup_num[i]; 824 825 old_dups[i] = *recog_data.dup_loc[i]; 826 *recog_data.dup_loc[i] = cc0_rtx; 827 828 /* For match_dup of match_operator or match_parallel, share 829 them, so that we don't miss changes in the dup. */ 830 if (icode >= 0 831 && insn_data[icode].operand[dup_num].eliminable == 0) 832 old_dups[i] = recog_data.operand[dup_num]; 833 } 834 835 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, 836 OP_IN, 0); 837 838 for (i = 0; i < recog_data.n_dups; i++) 839 *recog_data.dup_loc[i] = old_dups[i]; 840 for (i = 0; i < n_ops; i++) 841 *recog_data.operand_loc[i] = old_operands[i]; 842 843 /* Step 2B: Can't rename function call argument registers. */ 844 if (CALL_P (insn) && CALL_INSN_FUNCTION_USAGE (insn)) 845 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), 846 NO_REGS, terminate_all_read, OP_IN, 0); 847 848 /* Step 2C: Can't rename asm operands that were originally 849 hard registers. */ 850 if (asm_noperands (PATTERN (insn)) > 0) 851 for (i = 0; i < n_ops; i++) 852 { 853 rtx *loc = recog_data.operand_loc[i]; 854 rtx op = *loc; 855 856 if (REG_P (op) 857 && REGNO (op) == ORIGINAL_REGNO (op) 858 && (recog_data.operand_type[i] == OP_IN 859 || recog_data.operand_type[i] == OP_INOUT)) 860 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0); 861 } 862 863 /* Step 3: Append to chains for reads inside operands. */ 864 for (i = 0; i < n_ops + recog_data.n_dups; i++) 865 { 866 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 867 rtx *loc = (i < n_ops 868 ? recog_data.operand_loc[opn] 869 : recog_data.dup_loc[i - n_ops]); 870 enum reg_class cl = recog_op_alt[opn][alt].cl; 871 enum op_type type = recog_data.operand_type[opn]; 872 873 /* Don't scan match_operand here, since we've no reg class 874 information to pass down. Any operands that we could 875 substitute in will be represented elsewhere. */ 876 if (recog_data.constraints[opn][0] == '\0') 877 continue; 878 879 if (recog_op_alt[opn][alt].is_address) 880 scan_rtx_address (insn, loc, cl, mark_read, VOIDmode); 881 else 882 scan_rtx (insn, loc, cl, mark_read, type, 0); 883 } 884 885 /* Step 3B: Record updates for regs in REG_INC notes, and 886 source regs in REG_FRAME_RELATED_EXPR notes. */ 887 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 888 if (REG_NOTE_KIND (note) == REG_INC 889 || REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) 890 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, 891 OP_INOUT, 0); 892 893 /* Step 4: Close chains for registers that die here. */ 894 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 895 if (REG_NOTE_KIND (note) == REG_DEAD) 896 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 897 OP_IN, 0); 898 899 /* Step 4B: If this is a call, any chain live at this point 900 requires a caller-saved reg. */ 901 if (CALL_P (insn)) 902 { 903 struct du_chain *p; 904 for (p = open_chains; p; p = p->next_chain) 905 p->need_caller_save_reg = 1; 906 } 907 908 /* Step 5: Close open chains that overlap writes. Similar to 909 step 2, we hide in-out operands, since we do not want to 910 close these chains. */ 911 912 for (i = 0; i < n_ops; i++) 913 { 914 old_operands[i] = recog_data.operand[i]; 915 if (recog_data.operand_type[i] == OP_INOUT) 916 *recog_data.operand_loc[i] = cc0_rtx; 917 } 918 for (i = 0; i < recog_data.n_dups; i++) 919 { 920 int opn = recog_data.dup_num[i]; 921 old_dups[i] = *recog_data.dup_loc[i]; 922 if (recog_data.operand_type[opn] == OP_INOUT) 923 *recog_data.dup_loc[i] = cc0_rtx; 924 } 925 926 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0); 927 928 for (i = 0; i < recog_data.n_dups; i++) 929 *recog_data.dup_loc[i] = old_dups[i]; 930 for (i = 0; i < n_ops; i++) 931 *recog_data.operand_loc[i] = old_operands[i]; 932 933 /* Step 6: Begin new chains for writes inside operands. */ 934 /* ??? Many targets have output constraints on the SET_DEST 935 of a call insn, which is stupid, since these are certainly 936 ABI defined hard registers. Don't change calls at all. 937 Similarly take special care for asm statement that originally 938 referenced hard registers. */ 939 if (asm_noperands (PATTERN (insn)) > 0) 940 { 941 for (i = 0; i < n_ops; i++) 942 if (recog_data.operand_type[i] == OP_OUT) 943 { 944 rtx *loc = recog_data.operand_loc[i]; 945 rtx op = *loc; 946 enum reg_class cl = recog_op_alt[i][alt].cl; 947 948 if (REG_P (op) 949 && REGNO (op) == ORIGINAL_REGNO (op)) 950 continue; 951 952 scan_rtx (insn, loc, cl, mark_write, OP_OUT, 953 recog_op_alt[i][alt].earlyclobber); 954 } 955 } 956 else if (!CALL_P (insn)) 957 for (i = 0; i < n_ops + recog_data.n_dups; i++) 958 { 959 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 960 rtx *loc = (i < n_ops 961 ? recog_data.operand_loc[opn] 962 : recog_data.dup_loc[i - n_ops]); 963 enum reg_class cl = recog_op_alt[opn][alt].cl; 964 965 if (recog_data.operand_type[opn] == OP_OUT) 966 scan_rtx (insn, loc, cl, mark_write, OP_OUT, 967 recog_op_alt[opn][alt].earlyclobber); 968 } 969 970 /* Step 6B: Record destination regs in REG_FRAME_RELATED_EXPR 971 notes for update. */ 972 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 973 if (REG_NOTE_KIND (note) == REG_FRAME_RELATED_EXPR) 974 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_access, 975 OP_INOUT, 0); 976 977 /* Step 7: Close chains for registers that were never 978 really used here. */ 979 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 980 if (REG_NOTE_KIND (note) == REG_UNUSED) 981 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 982 OP_IN, 0); 983 } 984 if (insn == BB_END (bb)) 985 break; 986 } 987 988 /* Since we close every chain when we find a REG_DEAD note, anything that 989 is still open lives past the basic block, so it can't be renamed. */ 990 return closed_chains; 991} 992 993/* Dump all def/use chains in CHAINS to DUMP_FILE. They are 994 printed in reverse order as that's how we build them. */ 995 996static void 997dump_def_use_chain (struct du_chain *chains) 998{ 999 while (chains) 1000 { 1001 struct du_chain *this = chains; 1002 int r = REGNO (*this->loc); 1003 int nregs = hard_regno_nregs[r][GET_MODE (*this->loc)]; 1004 fprintf (dump_file, "Register %s (%d):", reg_names[r], nregs); 1005 while (this) 1006 { 1007 fprintf (dump_file, " %d [%s]", INSN_UID (this->insn), 1008 reg_class_names[this->cl]); 1009 this = this->next_use; 1010 } 1011 fprintf (dump_file, "\n"); 1012 chains = chains->next_chain; 1013 } 1014} 1015 1016/* The following code does forward propagation of hard register copies. 1017 The object is to eliminate as many dependencies as possible, so that 1018 we have the most scheduling freedom. As a side effect, we also clean 1019 up some silly register allocation decisions made by reload. This 1020 code may be obsoleted by a new register allocator. */ 1021 1022/* For each register, we have a list of registers that contain the same 1023 value. The OLDEST_REGNO field points to the head of the list, and 1024 the NEXT_REGNO field runs through the list. The MODE field indicates 1025 what mode the data is known to be in; this field is VOIDmode when the 1026 register is not known to contain valid data. */ 1027 1028struct value_data_entry 1029{ 1030 enum machine_mode mode; 1031 unsigned int oldest_regno; 1032 unsigned int next_regno; 1033}; 1034 1035struct value_data 1036{ 1037 struct value_data_entry e[FIRST_PSEUDO_REGISTER]; 1038 unsigned int max_value_regs; 1039}; 1040 1041static void kill_value_one_regno (unsigned, struct value_data *); 1042static void kill_value_regno (unsigned, unsigned, struct value_data *); 1043static void kill_value (rtx, struct value_data *); 1044static void set_value_regno (unsigned, enum machine_mode, struct value_data *); 1045static void init_value_data (struct value_data *); 1046static void kill_clobbered_value (rtx, rtx, void *); 1047static void kill_set_value (rtx, rtx, void *); 1048static int kill_autoinc_value (rtx *, void *); 1049static void copy_value (rtx, rtx, struct value_data *); 1050static bool mode_change_ok (enum machine_mode, enum machine_mode, 1051 unsigned int); 1052static rtx maybe_mode_change (enum machine_mode, enum machine_mode, 1053 enum machine_mode, unsigned int, unsigned int); 1054static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *); 1055static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx, 1056 struct value_data *); 1057static bool replace_oldest_value_addr (rtx *, enum reg_class, 1058 enum machine_mode, rtx, 1059 struct value_data *); 1060static bool replace_oldest_value_mem (rtx, rtx, struct value_data *); 1061static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *); 1062extern void debug_value_data (struct value_data *); 1063#ifdef ENABLE_CHECKING 1064static void validate_value_data (struct value_data *); 1065#endif 1066 1067/* Kill register REGNO. This involves removing it from any value 1068 lists, and resetting the value mode to VOIDmode. This is only a 1069 helper function; it does not handle any hard registers overlapping 1070 with REGNO. */ 1071 1072static void 1073kill_value_one_regno (unsigned int regno, struct value_data *vd) 1074{ 1075 unsigned int i, next; 1076 1077 if (vd->e[regno].oldest_regno != regno) 1078 { 1079 for (i = vd->e[regno].oldest_regno; 1080 vd->e[i].next_regno != regno; 1081 i = vd->e[i].next_regno) 1082 continue; 1083 vd->e[i].next_regno = vd->e[regno].next_regno; 1084 } 1085 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) 1086 { 1087 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) 1088 vd->e[i].oldest_regno = next; 1089 } 1090 1091 vd->e[regno].mode = VOIDmode; 1092 vd->e[regno].oldest_regno = regno; 1093 vd->e[regno].next_regno = INVALID_REGNUM; 1094 1095#ifdef ENABLE_CHECKING 1096 validate_value_data (vd); 1097#endif 1098} 1099 1100/* Kill the value in register REGNO for NREGS, and any other registers 1101 whose values overlap. */ 1102 1103static void 1104kill_value_regno (unsigned int regno, unsigned int nregs, 1105 struct value_data *vd) 1106{ 1107 unsigned int j; 1108 1109 /* Kill the value we're told to kill. */ 1110 for (j = 0; j < nregs; ++j) 1111 kill_value_one_regno (regno + j, vd); 1112 1113 /* Kill everything that overlapped what we're told to kill. */ 1114 if (regno < vd->max_value_regs) 1115 j = 0; 1116 else 1117 j = regno - vd->max_value_regs; 1118 for (; j < regno; ++j) 1119 { 1120 unsigned int i, n; 1121 if (vd->e[j].mode == VOIDmode) 1122 continue; 1123 n = hard_regno_nregs[j][vd->e[j].mode]; 1124 if (j + n > regno) 1125 for (i = 0; i < n; ++i) 1126 kill_value_one_regno (j + i, vd); 1127 } 1128} 1129 1130/* Kill X. This is a convenience function wrapping kill_value_regno 1131 so that we mind the mode the register is in. */ 1132 1133static void 1134kill_value (rtx x, struct value_data *vd) 1135{ 1136 rtx orig_rtx = x; 1137 1138 if (GET_CODE (x) == SUBREG) 1139 { 1140 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x), 1141 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); 1142 if (x == NULL_RTX) 1143 x = SUBREG_REG (orig_rtx); 1144 } 1145 if (REG_P (x)) 1146 { 1147 unsigned int regno = REGNO (x); 1148 unsigned int n = hard_regno_nregs[regno][GET_MODE (x)]; 1149 1150 kill_value_regno (regno, n, vd); 1151 } 1152} 1153 1154/* Remember that REGNO is valid in MODE. */ 1155 1156static void 1157set_value_regno (unsigned int regno, enum machine_mode mode, 1158 struct value_data *vd) 1159{ 1160 unsigned int nregs; 1161 1162 vd->e[regno].mode = mode; 1163 1164 nregs = hard_regno_nregs[regno][mode]; 1165 if (nregs > vd->max_value_regs) 1166 vd->max_value_regs = nregs; 1167} 1168 1169/* Initialize VD such that there are no known relationships between regs. */ 1170 1171static void 1172init_value_data (struct value_data *vd) 1173{ 1174 int i; 1175 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1176 { 1177 vd->e[i].mode = VOIDmode; 1178 vd->e[i].oldest_regno = i; 1179 vd->e[i].next_regno = INVALID_REGNUM; 1180 } 1181 vd->max_value_regs = 0; 1182} 1183 1184/* Called through note_stores. If X is clobbered, kill its value. */ 1185 1186static void 1187kill_clobbered_value (rtx x, rtx set, void *data) 1188{ 1189 struct value_data *vd = data; 1190 if (GET_CODE (set) == CLOBBER) 1191 kill_value (x, vd); 1192} 1193 1194/* Called through note_stores. If X is set, not clobbered, kill its 1195 current value and install it as the root of its own value list. */ 1196 1197static void 1198kill_set_value (rtx x, rtx set, void *data) 1199{ 1200 struct value_data *vd = data; 1201 if (GET_CODE (set) != CLOBBER) 1202 { 1203 kill_value (x, vd); 1204 if (REG_P (x)) 1205 set_value_regno (REGNO (x), GET_MODE (x), vd); 1206 } 1207} 1208 1209/* Called through for_each_rtx. Kill any register used as the base of an 1210 auto-increment expression, and install that register as the root of its 1211 own value list. */ 1212 1213static int 1214kill_autoinc_value (rtx *px, void *data) 1215{ 1216 rtx x = *px; 1217 struct value_data *vd = data; 1218 1219 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC) 1220 { 1221 x = XEXP (x, 0); 1222 kill_value (x, vd); 1223 set_value_regno (REGNO (x), Pmode, vd); 1224 return -1; 1225 } 1226 1227 return 0; 1228} 1229 1230/* Assert that SRC has been copied to DEST. Adjust the data structures 1231 to reflect that SRC contains an older copy of the shared value. */ 1232 1233static void 1234copy_value (rtx dest, rtx src, struct value_data *vd) 1235{ 1236 unsigned int dr = REGNO (dest); 1237 unsigned int sr = REGNO (src); 1238 unsigned int dn, sn; 1239 unsigned int i; 1240 1241 /* ??? At present, it's possible to see noop sets. It'd be nice if 1242 this were cleaned up beforehand... */ 1243 if (sr == dr) 1244 return; 1245 1246 /* Do not propagate copies to the stack pointer, as that can leave 1247 memory accesses with no scheduling dependency on the stack update. */ 1248 if (dr == STACK_POINTER_REGNUM) 1249 return; 1250 1251 /* Likewise with the frame pointer, if we're using one. */ 1252 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) 1253 return; 1254 1255 /* Do not propagate copies to fixed or global registers, patterns 1256 can be relying to see particular fixed register or users can 1257 expect the chosen global register in asm. */ 1258 if (fixed_regs[dr] || global_regs[dr]) 1259 return; 1260 1261 /* If SRC and DEST overlap, don't record anything. */ 1262 dn = hard_regno_nregs[dr][GET_MODE (dest)]; 1263 sn = hard_regno_nregs[sr][GET_MODE (dest)]; 1264 if ((dr > sr && dr < sr + sn) 1265 || (sr > dr && sr < dr + dn)) 1266 return; 1267 1268 /* If SRC had no assigned mode (i.e. we didn't know it was live) 1269 assign it now and assume the value came from an input argument 1270 or somesuch. */ 1271 if (vd->e[sr].mode == VOIDmode) 1272 set_value_regno (sr, vd->e[dr].mode, vd); 1273 1274 /* If we are narrowing the input to a smaller number of hard regs, 1275 and it is in big endian, we are really extracting a high part. 1276 Since we generally associate a low part of a value with the value itself, 1277 we must not do the same for the high part. 1278 Note we can still get low parts for the same mode combination through 1279 a two-step copy involving differently sized hard regs. 1280 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each: 1281 (set (reg:DI r0) (reg:DI fr0)) 1282 (set (reg:SI fr2) (reg:SI r0)) 1283 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while: 1284 (set (reg:SI fr2) (reg:SI fr0)) 1285 loads the high part of (reg:DI fr0) into fr2. 1286 1287 We can't properly represent the latter case in our tables, so don't 1288 record anything then. */ 1289 else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode] 1290 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD 1291 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) 1292 return; 1293 1294 /* If SRC had been assigned a mode narrower than the copy, we can't 1295 link DEST into the chain, because not all of the pieces of the 1296 copy came from oldest_regno. */ 1297 else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]) 1298 return; 1299 1300 /* Link DR at the end of the value chain used by SR. */ 1301 1302 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; 1303 1304 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) 1305 continue; 1306 vd->e[i].next_regno = dr; 1307 1308#ifdef ENABLE_CHECKING 1309 validate_value_data (vd); 1310#endif 1311} 1312 1313/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ 1314 1315static bool 1316mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode, 1317 unsigned int regno ATTRIBUTE_UNUSED) 1318{ 1319 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) 1320 return false; 1321 1322#ifdef CANNOT_CHANGE_MODE_CLASS 1323 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode); 1324#endif 1325 1326 return true; 1327} 1328 1329/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it - 1330 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed 1331 in NEW_MODE. 1332 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */ 1333 1334static rtx 1335maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode, 1336 enum machine_mode new_mode, unsigned int regno, 1337 unsigned int copy_regno ATTRIBUTE_UNUSED) 1338{ 1339 if (orig_mode == new_mode) 1340 return gen_rtx_raw_REG (new_mode, regno); 1341 else if (mode_change_ok (orig_mode, new_mode, regno)) 1342 { 1343 int copy_nregs = hard_regno_nregs[copy_regno][copy_mode]; 1344 int use_nregs = hard_regno_nregs[copy_regno][new_mode]; 1345 int copy_offset 1346 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs); 1347 int offset 1348 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset; 1349 int byteoffset = offset % UNITS_PER_WORD; 1350 int wordoffset = offset - byteoffset; 1351 1352 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0) 1353 + (BYTES_BIG_ENDIAN ? byteoffset : 0)); 1354 return gen_rtx_raw_REG (new_mode, 1355 regno + subreg_regno_offset (regno, orig_mode, 1356 offset, 1357 new_mode)); 1358 } 1359 return NULL_RTX; 1360} 1361 1362/* Find the oldest copy of the value contained in REGNO that is in 1363 register class CL and has mode MODE. If found, return an rtx 1364 of that oldest register, otherwise return NULL. */ 1365 1366static rtx 1367find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd) 1368{ 1369 unsigned int regno = REGNO (reg); 1370 enum machine_mode mode = GET_MODE (reg); 1371 unsigned int i; 1372 1373 /* If we are accessing REG in some mode other that what we set it in, 1374 make sure that the replacement is valid. In particular, consider 1375 (set (reg:DI r11) (...)) 1376 (set (reg:SI r9) (reg:SI r11)) 1377 (set (reg:SI r10) (...)) 1378 (set (...) (reg:DI r9)) 1379 Replacing r9 with r11 is invalid. */ 1380 if (mode != vd->e[regno].mode) 1381 { 1382 if (hard_regno_nregs[regno][mode] 1383 > hard_regno_nregs[regno][vd->e[regno].mode]) 1384 return NULL_RTX; 1385 } 1386 1387 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) 1388 { 1389 enum machine_mode oldmode = vd->e[i].mode; 1390 rtx new; 1391 unsigned int last; 1392 1393 for (last = i; last < i + hard_regno_nregs[i][mode]; last++) 1394 if (!TEST_HARD_REG_BIT (reg_class_contents[cl], last)) 1395 return NULL_RTX; 1396 1397 new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno); 1398 if (new) 1399 { 1400 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg); 1401 REG_ATTRS (new) = REG_ATTRS (reg); 1402 return new; 1403 } 1404 } 1405 1406 return NULL_RTX; 1407} 1408 1409/* If possible, replace the register at *LOC with the oldest register 1410 in register class CL. Return true if successfully replaced. */ 1411 1412static bool 1413replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn, 1414 struct value_data *vd) 1415{ 1416 rtx new = find_oldest_value_reg (cl, *loc, vd); 1417 if (new) 1418 { 1419 if (dump_file) 1420 fprintf (dump_file, "insn %u: replaced reg %u with %u\n", 1421 INSN_UID (insn), REGNO (*loc), REGNO (new)); 1422 1423 validate_change (insn, loc, new, 1); 1424 return true; 1425 } 1426 return false; 1427} 1428 1429/* Similar to replace_oldest_value_reg, but *LOC contains an address. 1430 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or 1431 BASE_REG_CLASS depending on how the register is being considered. */ 1432 1433static bool 1434replace_oldest_value_addr (rtx *loc, enum reg_class cl, 1435 enum machine_mode mode, rtx insn, 1436 struct value_data *vd) 1437{ 1438 rtx x = *loc; 1439 RTX_CODE code = GET_CODE (x); 1440 const char *fmt; 1441 int i, j; 1442 bool changed = false; 1443 1444 switch (code) 1445 { 1446 case PLUS: 1447 { 1448 rtx orig_op0 = XEXP (x, 0); 1449 rtx orig_op1 = XEXP (x, 1); 1450 RTX_CODE code0 = GET_CODE (orig_op0); 1451 RTX_CODE code1 = GET_CODE (orig_op1); 1452 rtx op0 = orig_op0; 1453 rtx op1 = orig_op1; 1454 rtx *locI = NULL; 1455 rtx *locB = NULL; 1456 enum rtx_code index_code = SCRATCH; 1457 1458 if (GET_CODE (op0) == SUBREG) 1459 { 1460 op0 = SUBREG_REG (op0); 1461 code0 = GET_CODE (op0); 1462 } 1463 1464 if (GET_CODE (op1) == SUBREG) 1465 { 1466 op1 = SUBREG_REG (op1); 1467 code1 = GET_CODE (op1); 1468 } 1469 1470 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 1471 || code0 == ZERO_EXTEND || code1 == MEM) 1472 { 1473 locI = &XEXP (x, 0); 1474 locB = &XEXP (x, 1); 1475 index_code = GET_CODE (*locI); 1476 } 1477 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 1478 || code1 == ZERO_EXTEND || code0 == MEM) 1479 { 1480 locI = &XEXP (x, 1); 1481 locB = &XEXP (x, 0); 1482 index_code = GET_CODE (*locI); 1483 } 1484 else if (code0 == CONST_INT || code0 == CONST 1485 || code0 == SYMBOL_REF || code0 == LABEL_REF) 1486 { 1487 locB = &XEXP (x, 1); 1488 index_code = GET_CODE (XEXP (x, 0)); 1489 } 1490 else if (code1 == CONST_INT || code1 == CONST 1491 || code1 == SYMBOL_REF || code1 == LABEL_REF) 1492 { 1493 locB = &XEXP (x, 0); 1494 index_code = GET_CODE (XEXP (x, 1)); 1495 } 1496 else if (code0 == REG && code1 == REG) 1497 { 1498 int index_op; 1499 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1); 1500 1501 if (REGNO_OK_FOR_INDEX_P (regno0) 1502 && regno_ok_for_base_p (regno1, mode, PLUS, REG)) 1503 index_op = 0; 1504 else if (REGNO_OK_FOR_INDEX_P (regno1) 1505 && regno_ok_for_base_p (regno0, mode, PLUS, REG)) 1506 index_op = 1; 1507 else if (regno_ok_for_base_p (regno1, mode, PLUS, REG)) 1508 index_op = 0; 1509 else if (regno_ok_for_base_p (regno0, mode, PLUS, REG)) 1510 index_op = 1; 1511 else if (REGNO_OK_FOR_INDEX_P (regno1)) 1512 index_op = 1; 1513 else 1514 index_op = 0; 1515 1516 locI = &XEXP (x, index_op); 1517 locB = &XEXP (x, !index_op); 1518 index_code = GET_CODE (*locI); 1519 } 1520 else if (code0 == REG) 1521 { 1522 locI = &XEXP (x, 0); 1523 locB = &XEXP (x, 1); 1524 index_code = GET_CODE (*locI); 1525 } 1526 else if (code1 == REG) 1527 { 1528 locI = &XEXP (x, 1); 1529 locB = &XEXP (x, 0); 1530 index_code = GET_CODE (*locI); 1531 } 1532 1533 if (locI) 1534 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode, 1535 insn, vd); 1536 if (locB) 1537 changed |= replace_oldest_value_addr (locB, 1538 base_reg_class (mode, PLUS, 1539 index_code), 1540 mode, insn, vd); 1541 return changed; 1542 } 1543 1544 case POST_INC: 1545 case POST_DEC: 1546 case POST_MODIFY: 1547 case PRE_INC: 1548 case PRE_DEC: 1549 case PRE_MODIFY: 1550 return false; 1551 1552 case MEM: 1553 return replace_oldest_value_mem (x, insn, vd); 1554 1555 case REG: 1556 return replace_oldest_value_reg (loc, cl, insn, vd); 1557 1558 default: 1559 break; 1560 } 1561 1562 fmt = GET_RTX_FORMAT (code); 1563 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1564 { 1565 if (fmt[i] == 'e') 1566 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode, 1567 insn, vd); 1568 else if (fmt[i] == 'E') 1569 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1570 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl, 1571 mode, insn, vd); 1572 } 1573 1574 return changed; 1575} 1576 1577/* Similar to replace_oldest_value_reg, but X contains a memory. */ 1578 1579static bool 1580replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd) 1581{ 1582 return replace_oldest_value_addr (&XEXP (x, 0), 1583 base_reg_class (GET_MODE (x), MEM, 1584 SCRATCH), 1585 GET_MODE (x), insn, vd); 1586} 1587 1588/* Perform the forward copy propagation on basic block BB. */ 1589 1590static bool 1591copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd) 1592{ 1593 bool changed = false; 1594 rtx insn; 1595 1596 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 1597 { 1598 int n_ops, i, alt, predicated; 1599 bool is_asm, any_replacements; 1600 rtx set; 1601 bool replaced[MAX_RECOG_OPERANDS]; 1602 1603 if (! INSN_P (insn)) 1604 { 1605 if (insn == BB_END (bb)) 1606 break; 1607 else 1608 continue; 1609 } 1610 1611 set = single_set (insn); 1612 extract_insn (insn); 1613 if (! constrain_operands (1)) 1614 fatal_insn_not_found (insn); 1615 preprocess_constraints (); 1616 alt = which_alternative; 1617 n_ops = recog_data.n_operands; 1618 is_asm = asm_noperands (PATTERN (insn)) >= 0; 1619 1620 /* Simplify the code below by rewriting things to reflect 1621 matching constraints. Also promote OP_OUT to OP_INOUT 1622 in predicated instructions. */ 1623 1624 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 1625 for (i = 0; i < n_ops; ++i) 1626 { 1627 int matches = recog_op_alt[i][alt].matches; 1628 if (matches >= 0) 1629 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl; 1630 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 1631 || (predicated && recog_data.operand_type[i] == OP_OUT)) 1632 recog_data.operand_type[i] = OP_INOUT; 1633 } 1634 1635 /* For each earlyclobber operand, zap the value data. */ 1636 for (i = 0; i < n_ops; i++) 1637 if (recog_op_alt[i][alt].earlyclobber) 1638 kill_value (recog_data.operand[i], vd); 1639 1640 /* Within asms, a clobber cannot overlap inputs or outputs. 1641 I wouldn't think this were true for regular insns, but 1642 scan_rtx treats them like that... */ 1643 note_stores (PATTERN (insn), kill_clobbered_value, vd); 1644 1645 /* Kill all auto-incremented values. */ 1646 /* ??? REG_INC is useless, since stack pushes aren't done that way. */ 1647 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); 1648 1649 /* Kill all early-clobbered operands. */ 1650 for (i = 0; i < n_ops; i++) 1651 if (recog_op_alt[i][alt].earlyclobber) 1652 kill_value (recog_data.operand[i], vd); 1653 1654 /* Special-case plain move instructions, since we may well 1655 be able to do the move from a different register class. */ 1656 if (set && REG_P (SET_SRC (set))) 1657 { 1658 rtx src = SET_SRC (set); 1659 unsigned int regno = REGNO (src); 1660 enum machine_mode mode = GET_MODE (src); 1661 unsigned int i; 1662 rtx new; 1663 1664 /* If we are accessing SRC in some mode other that what we 1665 set it in, make sure that the replacement is valid. */ 1666 if (mode != vd->e[regno].mode) 1667 { 1668 if (hard_regno_nregs[regno][mode] 1669 > hard_regno_nregs[regno][vd->e[regno].mode]) 1670 goto no_move_special_case; 1671 } 1672 1673 /* If the destination is also a register, try to find a source 1674 register in the same class. */ 1675 if (REG_P (SET_DEST (set))) 1676 { 1677 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); 1678 if (new && validate_change (insn, &SET_SRC (set), new, 0)) 1679 { 1680 if (dump_file) 1681 fprintf (dump_file, 1682 "insn %u: replaced reg %u with %u\n", 1683 INSN_UID (insn), regno, REGNO (new)); 1684 changed = true; 1685 goto did_replacement; 1686 } 1687 } 1688 1689 /* Otherwise, try all valid registers and see if its valid. */ 1690 for (i = vd->e[regno].oldest_regno; i != regno; 1691 i = vd->e[i].next_regno) 1692 { 1693 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode, 1694 mode, i, regno); 1695 if (new != NULL_RTX) 1696 { 1697 if (validate_change (insn, &SET_SRC (set), new, 0)) 1698 { 1699 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src); 1700 REG_ATTRS (new) = REG_ATTRS (src); 1701 if (dump_file) 1702 fprintf (dump_file, 1703 "insn %u: replaced reg %u with %u\n", 1704 INSN_UID (insn), regno, REGNO (new)); 1705 changed = true; 1706 goto did_replacement; 1707 } 1708 } 1709 } 1710 } 1711 no_move_special_case: 1712 1713 any_replacements = false; 1714 1715 /* For each input operand, replace a hard register with the 1716 eldest live copy that's in an appropriate register class. */ 1717 for (i = 0; i < n_ops; i++) 1718 { 1719 replaced[i] = false; 1720 1721 /* Don't scan match_operand here, since we've no reg class 1722 information to pass down. Any operands that we could 1723 substitute in will be represented elsewhere. */ 1724 if (recog_data.constraints[i][0] == '\0') 1725 continue; 1726 1727 /* Don't replace in asms intentionally referencing hard regs. */ 1728 if (is_asm && REG_P (recog_data.operand[i]) 1729 && (REGNO (recog_data.operand[i]) 1730 == ORIGINAL_REGNO (recog_data.operand[i]))) 1731 continue; 1732 1733 if (recog_data.operand_type[i] == OP_IN) 1734 { 1735 if (recog_op_alt[i][alt].is_address) 1736 replaced[i] 1737 = replace_oldest_value_addr (recog_data.operand_loc[i], 1738 recog_op_alt[i][alt].cl, 1739 VOIDmode, insn, vd); 1740 else if (REG_P (recog_data.operand[i])) 1741 replaced[i] 1742 = replace_oldest_value_reg (recog_data.operand_loc[i], 1743 recog_op_alt[i][alt].cl, 1744 insn, vd); 1745 else if (MEM_P (recog_data.operand[i])) 1746 replaced[i] = replace_oldest_value_mem (recog_data.operand[i], 1747 insn, vd); 1748 } 1749 else if (MEM_P (recog_data.operand[i])) 1750 replaced[i] = replace_oldest_value_mem (recog_data.operand[i], 1751 insn, vd); 1752 1753 /* If we performed any replacement, update match_dups. */ 1754 if (replaced[i]) 1755 { 1756 int j; 1757 rtx new; 1758 1759 new = *recog_data.operand_loc[i]; 1760 recog_data.operand[i] = new; 1761 for (j = 0; j < recog_data.n_dups; j++) 1762 if (recog_data.dup_num[j] == i) 1763 validate_change (insn, recog_data.dup_loc[j], new, 1); 1764 1765 any_replacements = true; 1766 } 1767 } 1768 1769 if (any_replacements) 1770 { 1771 if (! apply_change_group ()) 1772 { 1773 for (i = 0; i < n_ops; i++) 1774 if (replaced[i]) 1775 { 1776 rtx old = *recog_data.operand_loc[i]; 1777 recog_data.operand[i] = old; 1778 } 1779 1780 if (dump_file) 1781 fprintf (dump_file, 1782 "insn %u: reg replacements not verified\n", 1783 INSN_UID (insn)); 1784 } 1785 else 1786 changed = true; 1787 } 1788 1789 did_replacement: 1790 /* Clobber call-clobbered registers. */ 1791 if (CALL_P (insn)) 1792 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1793 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1794 kill_value_regno (i, 1, vd); 1795 1796 /* Notice stores. */ 1797 note_stores (PATTERN (insn), kill_set_value, vd); 1798 1799 /* Notice copies. */ 1800 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) 1801 copy_value (SET_DEST (set), SET_SRC (set), vd); 1802 1803 if (insn == BB_END (bb)) 1804 break; 1805 } 1806 1807 return changed; 1808} 1809 1810/* Main entry point for the forward copy propagation optimization. */ 1811 1812static void 1813copyprop_hardreg_forward (void) 1814{ 1815 struct value_data *all_vd; 1816 bool need_refresh; 1817 basic_block bb; 1818 sbitmap visited; 1819 1820 need_refresh = false; 1821 1822 all_vd = XNEWVEC (struct value_data, last_basic_block); 1823 1824 visited = sbitmap_alloc (last_basic_block); 1825 sbitmap_zero (visited); 1826 1827 FOR_EACH_BB (bb) 1828 { 1829 SET_BIT (visited, bb->index); 1830 1831 /* If a block has a single predecessor, that we've already 1832 processed, begin with the value data that was live at 1833 the end of the predecessor block. */ 1834 /* ??? Ought to use more intelligent queuing of blocks. */ 1835 if (single_pred_p (bb) 1836 && TEST_BIT (visited, single_pred (bb)->index) 1837 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))) 1838 all_vd[bb->index] = all_vd[single_pred (bb)->index]; 1839 else 1840 init_value_data (all_vd + bb->index); 1841 1842 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index)) 1843 need_refresh = true; 1844 } 1845 1846 sbitmap_free (visited); 1847 1848 if (need_refresh) 1849 { 1850 if (dump_file) 1851 fputs ("\n\n", dump_file); 1852 1853 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks 1854 to scan, so we have to do a life update with no initial set of 1855 blocks Just In Case. */ 1856 delete_noop_moves (); 1857 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 1858 PROP_DEATH_NOTES 1859 | PROP_SCAN_DEAD_CODE 1860 | PROP_KILL_DEAD_CODE); 1861 } 1862 1863 free (all_vd); 1864} 1865 1866/* Dump the value chain data to stderr. */ 1867 1868void 1869debug_value_data (struct value_data *vd) 1870{ 1871 HARD_REG_SET set; 1872 unsigned int i, j; 1873 1874 CLEAR_HARD_REG_SET (set); 1875 1876 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1877 if (vd->e[i].oldest_regno == i) 1878 { 1879 if (vd->e[i].mode == VOIDmode) 1880 { 1881 if (vd->e[i].next_regno != INVALID_REGNUM) 1882 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", 1883 i, vd->e[i].next_regno); 1884 continue; 1885 } 1886 1887 SET_HARD_REG_BIT (set, i); 1888 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); 1889 1890 for (j = vd->e[i].next_regno; 1891 j != INVALID_REGNUM; 1892 j = vd->e[j].next_regno) 1893 { 1894 if (TEST_HARD_REG_BIT (set, j)) 1895 { 1896 fprintf (stderr, "[%u] Loop in regno chain\n", j); 1897 return; 1898 } 1899 1900 if (vd->e[j].oldest_regno != i) 1901 { 1902 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", 1903 j, vd->e[j].oldest_regno); 1904 return; 1905 } 1906 SET_HARD_REG_BIT (set, j); 1907 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); 1908 } 1909 fputc ('\n', stderr); 1910 } 1911 1912 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1913 if (! TEST_HARD_REG_BIT (set, i) 1914 && (vd->e[i].mode != VOIDmode 1915 || vd->e[i].oldest_regno != i 1916 || vd->e[i].next_regno != INVALID_REGNUM)) 1917 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", 1918 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1919 vd->e[i].next_regno); 1920} 1921 1922#ifdef ENABLE_CHECKING 1923static void 1924validate_value_data (struct value_data *vd) 1925{ 1926 HARD_REG_SET set; 1927 unsigned int i, j; 1928 1929 CLEAR_HARD_REG_SET (set); 1930 1931 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1932 if (vd->e[i].oldest_regno == i) 1933 { 1934 if (vd->e[i].mode == VOIDmode) 1935 { 1936 if (vd->e[i].next_regno != INVALID_REGNUM) 1937 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", 1938 i, vd->e[i].next_regno); 1939 continue; 1940 } 1941 1942 SET_HARD_REG_BIT (set, i); 1943 1944 for (j = vd->e[i].next_regno; 1945 j != INVALID_REGNUM; 1946 j = vd->e[j].next_regno) 1947 { 1948 if (TEST_HARD_REG_BIT (set, j)) 1949 internal_error ("validate_value_data: Loop in regno chain (%u)", 1950 j); 1951 if (vd->e[j].oldest_regno != i) 1952 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", 1953 j, vd->e[j].oldest_regno); 1954 1955 SET_HARD_REG_BIT (set, j); 1956 } 1957 } 1958 1959 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1960 if (! TEST_HARD_REG_BIT (set, i) 1961 && (vd->e[i].mode != VOIDmode 1962 || vd->e[i].oldest_regno != i 1963 || vd->e[i].next_regno != INVALID_REGNUM)) 1964 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", 1965 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1966 vd->e[i].next_regno); 1967} 1968#endif 1969 1970static bool 1971gate_handle_regrename (void) 1972{ 1973 return (optimize > 0 && (flag_rename_registers || flag_cprop_registers)); 1974} 1975 1976 1977/* Run the regrename and cprop passes. */ 1978static unsigned int 1979rest_of_handle_regrename (void) 1980{ 1981 if (flag_rename_registers) 1982 regrename_optimize (); 1983 if (flag_cprop_registers) 1984 copyprop_hardreg_forward (); 1985 return 0; 1986} 1987 1988struct tree_opt_pass pass_regrename = 1989{ 1990 "rnreg", /* name */ 1991 gate_handle_regrename, /* gate */ 1992 rest_of_handle_regrename, /* execute */ 1993 NULL, /* sub */ 1994 NULL, /* next */ 1995 0, /* static_pass_number */ 1996 TV_RENAME_REGISTERS, /* tv_id */ 1997 0, /* properties_required */ 1998 0, /* properties_provided */ 1999 0, /* properties_destroyed */ 2000 0, /* todo_flags_start */ 2001 TODO_dump_func, /* todo_flags_finish */ 2002 'n' /* letter */ 2003}; 2004 2005