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