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