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