regrename.c revision 90075
11602Srgrimes/* Register renaming for the GNU compiler. 21602Srgrimes Copyright (C) 2000, 2001, 2002 Free Software Foundation, Inc. 31602Srgrimes 41602Srgrimes This file is part of GCC. 51602Srgrimes 61602Srgrimes GCC is free software; you can redistribute it and/or modify it 71602Srgrimes under the terms of the GNU General Public License as published by 81602Srgrimes the Free Software Foundation; either version 2, or (at your option) 91602Srgrimes any later version. 101602Srgrimes 111602Srgrimes GCC is distributed in the hope that it will be useful, but WITHOUT 121602Srgrimes ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 131602Srgrimes or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 141602Srgrimes License for more details. 151602Srgrimes 161602Srgrimes You should have received a copy of the GNU General Public License 171602Srgrimes along with GCC; see the file COPYING. If not, write to the Free 181602Srgrimes Software Foundation, 59 Temple Place - Suite 330, Boston, MA 191602Srgrimes 02111-1307, USA. */ 201602Srgrimes 211602Srgrimes#define REG_OK_STRICT 221602Srgrimes 231602Srgrimes#include "config.h" 241602Srgrimes#include "system.h" 251602Srgrimes#include "rtl.h" 261602Srgrimes#include "tm_p.h" 271602Srgrimes#include "insn-config.h" 281602Srgrimes#include "regs.h" 291602Srgrimes#include "hard-reg-set.h" 301602Srgrimes#include "basic-block.h" 311602Srgrimes#include "reload.h" 321602Srgrimes#include "output.h" 331602Srgrimes#include "function.h" 3483551Sdillon#include "recog.h" 3583551Sdillon#include "flags.h" 3683551Sdillon#include "toplev.h" 371602Srgrimes#include "obstack.h" 3855127Speter 391602Srgrimes#define obstack_chunk_alloc xmalloc 4055127Speter#define obstack_chunk_free free 411602Srgrimes 421602Srgrimes#ifndef REGNO_MODE_OK_FOR_BASE_P 431602Srgrimes#define REGNO_MODE_OK_FOR_BASE_P(REGNO, MODE) REGNO_OK_FOR_BASE_P (REGNO) 448870Srgrimes#endif 451602Srgrimes 461602Srgrimes#ifndef REG_MODE_OK_FOR_BASE_P 471602Srgrimes#define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO) 481602Srgrimes#endif 491602Srgrimes 501602Srgrimesstatic const char *const reg_class_names[] = REG_CLASS_NAMES; 511602Srgrimes 52147672Speterstruct du_chain 5317141Sjkh{ 54194186Sed struct du_chain *next_chain; 551602Srgrimes struct du_chain *next_use; 561602Srgrimes 571602Srgrimes rtx insn; 581602Srgrimes rtx *loc; 591602Srgrimes enum reg_class class; 601602Srgrimes unsigned int need_caller_save_reg:1; 611602Srgrimes unsigned int earlyclobber:1; 62147672Speter}; 63147672Speter 641602Srgrimesenum scan_actions 651602Srgrimes{ 661602Srgrimes terminate_all_read, 671602Srgrimes terminate_overlapping_read, 681602Srgrimes terminate_write, 691603Srgrimes terminate_dead, 701603Srgrimes mark_read, 711602Srgrimes mark_write 721602Srgrimes}; 73147672Speter 74147672Speterstatic const char * const scan_actions_name[] = 75147672Speter{ 76147672Speter "terminate_all_read", 77147672Speter "terminate_overlapping_read", 78157911Speter "terminate_write", 791602Srgrimes "terminate_dead", 80157911Speter "mark_read", 81147672Speter "mark_write" 82147672Speter}; 83147672Speter 84147672Speterstatic struct obstack rename_obstack; 851602Srgrimes 861602Srgrimesstatic void do_replace PARAMS ((struct du_chain *, int)); 87147672Speterstatic void scan_rtx_reg PARAMS ((rtx, rtx *, enum reg_class, 88147672Speter enum scan_actions, enum op_type, int)); 89147672Speterstatic void scan_rtx_address PARAMS ((rtx, rtx *, enum reg_class, 90147672Speter enum scan_actions, enum machine_mode)); 91147672Speterstatic void scan_rtx PARAMS ((rtx, rtx *, enum reg_class, 92147672Speter enum scan_actions, enum op_type, int)); 93147672Speterstatic struct du_chain *build_def_use PARAMS ((basic_block)); 94147672Speterstatic void dump_def_use_chain PARAMS ((struct du_chain *)); 95147672Speterstatic void note_sets PARAMS ((rtx, rtx, void *)); 96147672Speterstatic void clear_dead_regs PARAMS ((HARD_REG_SET *, enum machine_mode, rtx)); 97147672Speterstatic void merge_overlapping_regs PARAMS ((basic_block, HARD_REG_SET *, 98147672Speter struct du_chain *)); 99147672Speter 100147672Speter/* Called through note_stores from update_life. Find sets of registers, and 101147672Speter record them in *DATA (which is actually a HARD_REG_SET *). */ 102147672Speter 103147672Speterstatic void 104147672Speternote_sets (x, set, data) 105147672Speter rtx x; 106147672Speter rtx set ATTRIBUTE_UNUSED; 107147672Speter void *data; 108147672Speter{ 109147672Speter HARD_REG_SET *pset = (HARD_REG_SET *) data; 110147672Speter unsigned int regno; 111147672Speter int nregs; 112147672Speter if (GET_CODE (x) != REG) 113147672Speter return; 114147672Speter regno = REGNO (x); 115147672Speter nregs = HARD_REGNO_NREGS (regno, GET_MODE (x)); 116147672Speter 117147672Speter /* There must not be pseudos at this point. */ 118147672Speter if (regno + nregs > FIRST_PSEUDO_REGISTER) 119147672Speter abort (); 120170772Ssimokawa 121170772Ssimokawa while (nregs-- > 0) 122147672Speter SET_HARD_REG_BIT (*pset, regno + nregs); 123170772Ssimokawa} 124170772Ssimokawa 125170772Ssimokawa/* Clear all registers from *PSET for which a note of kind KIND can be found 126170772Ssimokawa in the list NOTES. */ 127170772Ssimokawa 128170772Ssimokawastatic void 129170772Ssimokawaclear_dead_regs (pset, kind, notes) 130147672Speter HARD_REG_SET *pset; 131147672Speter enum machine_mode kind; 132147672Speter rtx notes; 133147672Speter{ 134147672Speter rtx note; 135147672Speter for (note = notes; note; note = XEXP (note, 1)) 136147672Speter if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0))) 137147672Speter { 1381602Srgrimes rtx reg = XEXP (note, 0); 13918798Speter unsigned int regno = REGNO (reg); 14018798Speter int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 141147672Speter 142147672Speter /* There must not be pseudos at this point. */ 143157911Speter if (regno + nregs > FIRST_PSEUDO_REGISTER) 144157911Speter abort (); 145147672Speter 146147672Speter while (nregs-- > 0) 147147672Speter CLEAR_HARD_REG_BIT (*pset, regno + nregs); 148147672Speter } 149147672Speter} 150147672Speter 1511602Srgrimes/* For a def-use chain CHAIN in basic block B, find which registers overlap 1521602Srgrimes its lifetime and set the corresponding bits in *PSET. */ 1531602Srgrimes 15418798Speterstatic void 15518798Spetermerge_overlapping_regs (b, pset, chain) 156217744Suqs basic_block b; 15718798Speter HARD_REG_SET *pset; 15882263Speter struct du_chain *chain; 159147672Speter{ 160147672Speter struct du_chain *t = chain; 161147672Speter rtx insn; 162147672Speter HARD_REG_SET live; 163157911Speter 1641602Srgrimes REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start); 165170772Ssimokawa insn = b->head; 166157911Speter while (t) 167157911Speter { 168157911Speter /* Search forward until the next reference to the register to be 169147672Speter renamed. */ 170147672Speter while (insn != t->insn) 1711603Srgrimes { 1721602Srgrimes if (INSN_P (insn)) 1731603Srgrimes { 174147672Speter clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn)); 1751602Srgrimes note_stores (PATTERN (insn), note_sets, (void *) &live); 176170772Ssimokawa /* Only record currently live regs if we are inside the 177170772Ssimokawa reg's live range. */ 178170772Ssimokawa if (t != chain) 179147672Speter IOR_HARD_REG_SET (*pset, live); 180170772Ssimokawa clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn)); 181170772Ssimokawa } 182170772Ssimokawa insn = NEXT_INSN (insn); 183170772Ssimokawa } 184170772Ssimokawa 185147672Speter IOR_HARD_REG_SET (*pset, live); 186217744Suqs 187217744Suqs /* For the last reference, also merge in all registers set in the 1881602Srgrimes same insn. 189217744Suqs @@@ We only have take earlyclobbered sets into account. */ 19082263Speter if (! t->next_use) 19182263Speter note_stores (PATTERN (insn), note_sets, (void *) pset); 192217744Suqs 19382263Speter t = t->next_use; 194217744Suqs } 195217744Suqs} 19682263Speter 197217744Suqs/* Perform register renaming on the current function. */ 198147672Speter 199147672Spetervoid 200217744Suqsregrename_optimize () 201147672Speter{ 202147672Speter int tick[FIRST_PSEUDO_REGISTER]; 203147672Speter int this_tick = 0; 204147672Speter int b; 205147672Speter char *first_obj; 206147672Speter 207147672Speter memset (tick, 0, sizeof tick); 208147672Speter 209147672Speter gcc_obstack_init (&rename_obstack); 210147672Speter first_obj = (char *) obstack_alloc (&rename_obstack, 0); 211147672Speter 212147672Speter for (b = 0; b < n_basic_blocks; b++) 213147672Speter { 214147672Speter basic_block bb = BASIC_BLOCK (b); 215147672Speter struct du_chain *all_chains = 0; 216147672Speter HARD_REG_SET unavailable; 217147672Speter HARD_REG_SET regs_seen; 218147672Speter 219147672Speter CLEAR_HARD_REG_SET (unavailable); 220147672Speter 221147672Speter if (rtl_dump_file) 222147672Speter fprintf (rtl_dump_file, "\nBasic block %d:\n", b); 223217744Suqs 224217744Suqs all_chains = build_def_use (bb); 225147672Speter 226217744Suqs if (rtl_dump_file) 227147672Speter dump_def_use_chain (all_chains); 228147672Speter 229147672Speter CLEAR_HARD_REG_SET (unavailable); 230217744Suqs /* Don't clobber traceback for noreturn functions. */ 231147672Speter if (frame_pointer_needed) 232147672Speter { 233147672Speter int i; 234147672Speter 235147672Speter for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;) 236147672Speter SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i); 237147672Speter 238147672Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 239147672Speter for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;) 240147672Speter SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i); 241147672Speter#endif 2421602Srgrimes } 2431602Srgrimes 2441602Srgrimes CLEAR_HARD_REG_SET (regs_seen); 2451602Srgrimes while (all_chains) 2461602Srgrimes { 247147672Speter int new_reg, best_new_reg = -1; 24818798Speter int n_uses; 24918798Speter struct du_chain *this = all_chains; 25018798Speter struct du_chain *tmp, *last; 25118798Speter HARD_REG_SET this_unavailable; 252147672Speter int reg = REGNO (*this->loc); 25318798Speter int i; 25418798Speter 25518798Speter all_chains = this->next_chain; 25618798Speter 257147672Speter#if 0 /* This just disables optimization opportunities. */ 258147672Speter /* Only rename once we've seen the reg more than once. */ 259147672Speter if (! TEST_HARD_REG_BIT (regs_seen, reg)) 260147672Speter { 2611602Srgrimes SET_HARD_REG_BIT (regs_seen, reg); 26218798Speter continue; 263147672Speter } 26418798Speter#endif 26518798Speter 26618798Speter if (fixed_regs[reg] || global_regs[reg] 26718798Speter#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 26818798Speter || (frame_pointer_needed && reg == HARD_FRAME_POINTER_REGNUM) 26918798Speter#else 270147672Speter || (frame_pointer_needed && reg == FRAME_POINTER_REGNUM) 271147672Speter#endif 272147672Speter ) 273147672Speter continue; 274147672Speter 275147672Speter COPY_HARD_REG_SET (this_unavailable, unavailable); 276147672Speter 277147672Speter /* Find last entry on chain (which has the need_caller_save bit), 27818798Speter count number of uses, and narrow the set of registers we can 27918798Speter use for renaming. */ 28018798Speter n_uses = 0; 281147672Speter for (last = this; last->next_use; last = last->next_use) 282147672Speter { 283147672Speter n_uses++; 28418798Speter IOR_COMPL_HARD_REG_SET (this_unavailable, 285147672Speter reg_class_contents[last->class]); 28618798Speter } 28728318Stegge if (n_uses < 1) 28828318Stegge continue; 28928318Stegge 29028318Stegge IOR_COMPL_HARD_REG_SET (this_unavailable, 291147672Speter reg_class_contents[last->class]); 29228318Stegge 29328318Stegge if (this->need_caller_save_reg) 29428318Stegge IOR_HARD_REG_SET (this_unavailable, call_used_reg_set); 295147672Speter 296147672Speter merge_overlapping_regs (bb, &this_unavailable, this); 297198986Sjhb 298198986Sjhb /* Now potential_regs is a reasonable approximation, let's 299198986Sjhb have a closer look at each register still in there. */ 300147672Speter for (new_reg = 0; new_reg < FIRST_PSEUDO_REGISTER; new_reg++) 301147672Speter { 302147672Speter int nregs = HARD_REGNO_NREGS (new_reg, GET_MODE (*this->loc)); 30328318Stegge 30428318Stegge for (i = nregs - 1; i >= 0; --i) 30528318Stegge if (TEST_HARD_REG_BIT (this_unavailable, new_reg + i) 30618798Speter || fixed_regs[new_reg + i] 307147672Speter || global_regs[new_reg + i] 30818798Speter /* Can't use regs which aren't saved by the prologue. */ 309147672Speter || (! regs_ever_live[new_reg + i] 310151492Speter && ! call_used_regs[new_reg + i]) 311147672Speter#ifdef LEAF_REGISTERS 312147672Speter /* We can't use a non-leaf register if we're in a 313147672Speter leaf function. */ 314147672Speter || (current_function_is_leaf 31518798Speter && !LEAF_REGISTERS[new_reg + i]) 316147672Speter#endif 31718798Speter#ifdef HARD_REGNO_RENAME_OK 31818798Speter || ! HARD_REGNO_RENAME_OK (reg + i, new_reg + i) 31918798Speter#endif 32018798Speter ) 32118798Speter break; 32218798Speter if (i >= 0) 32318798Speter continue; 324147672Speter 325147672Speter /* See whether it accepts all modes that occur in 32618798Speter definition and uses. */ 327147672Speter for (tmp = this; tmp; tmp = tmp->next_use) 32818798Speter if (! HARD_REGNO_MODE_OK (new_reg, GET_MODE (*tmp->loc))) 329147672Speter break; 330147672Speter if (! tmp) 331147672Speter { 332147672Speter if (best_new_reg == -1 333147672Speter || tick[best_new_reg] > tick[new_reg]) 334147672Speter best_new_reg = new_reg; 335147672Speter } 33618798Speter } 33718798Speter 338147672Speter if (rtl_dump_file) 33918798Speter { 3401602Srgrimes fprintf (rtl_dump_file, "Register %s in insn %d", 3411602Srgrimes reg_names[reg], INSN_UID (last->insn)); 342147672Speter if (last->need_caller_save_reg) 343147672Speter fprintf (rtl_dump_file, " crosses a call"); 344147672Speter } 345147672Speter 346147672Speter if (best_new_reg == -1) 347147672Speter { 348147672Speter if (rtl_dump_file) 349147672Speter fprintf (rtl_dump_file, "; no available registers\n"); 350147672Speter continue; 351147672Speter } 352147672Speter 353147672Speter do_replace (this, best_new_reg); 354147672Speter tick[best_new_reg] = this_tick++; 355147672Speter 356147672Speter if (rtl_dump_file) 357147672Speter fprintf (rtl_dump_file, ", renamed as %s\n", reg_names[best_new_reg]); 358147672Speter } 359147672Speter 360147672Speter obstack_free (&rename_obstack, first_obj); 361147672Speter } 362147672Speter 363147672Speter obstack_free (&rename_obstack, NULL); 364147672Speter 365147672Speter if (rtl_dump_file) 366147672Speter fputc ('\n', rtl_dump_file); 367147672Speter 368147672Speter count_or_remove_death_notes (NULL, 1); 369147672Speter update_life_info (NULL, UPDATE_LIFE_LOCAL, 370147672Speter PROP_REG_INFO | PROP_DEATH_NOTES); 371147672Speter} 372147672Speter 373147672Speterstatic void 374147672Speterdo_replace (chain, reg) 375147672Speter struct du_chain *chain; 376147672Speter int reg; 377147672Speter{ 378147672Speter while (chain) 379147672Speter { 380147672Speter unsigned int regno = ORIGINAL_REGNO (*chain->loc); 381147672Speter *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); 382147672Speter if (regno >= FIRST_PSEUDO_REGISTER) 383147672Speter ORIGINAL_REGNO (*chain->loc) = regno; 384147672Speter chain = chain->next_use; 385147672Speter } 386147672Speter} 387147672Speter 388147672Speter 389147672Speterstatic struct du_chain *open_chains; 390147672Speterstatic struct du_chain *closed_chains; 391147672Speter 392147672Speterstatic void 393198986Sjhbscan_rtx_reg (insn, loc, class, action, type, earlyclobber) 394198986Sjhb rtx insn; 395198986Sjhb rtx *loc; 396147672Speter enum reg_class class; 397147672Speter enum scan_actions action; 398147672Speter enum op_type type; 399147672Speter int earlyclobber; 400147672Speter{ 401147672Speter struct du_chain **p; 402147672Speter rtx x = *loc; 403147672Speter enum machine_mode mode = GET_MODE (x); 404147672Speter int this_regno = REGNO (x); 405147672Speter int this_nregs = HARD_REGNO_NREGS (this_regno, mode); 406151492Speter 407147672Speter if (action == mark_write) 408147672Speter { 409147672Speter if (type == OP_OUT) 410147672Speter { 411147672Speter struct du_chain *this = (struct du_chain *) 412147672Speter obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 413147672Speter this->next_use = 0; 414147672Speter this->next_chain = open_chains; 415147672Speter this->loc = loc; 416147672Speter this->insn = insn; 417147672Speter this->class = class; 418147672Speter this->need_caller_save_reg = 0; 419147672Speter this->earlyclobber = earlyclobber; 420147672Speter open_chains = this; 421147672Speter } 422147672Speter return; 423147672Speter } 424147672Speter 425147672Speter if ((type == OP_OUT && action != terminate_write) 426147672Speter || (type != OP_OUT && action == terminate_write)) 427147672Speter return; 428147672Speter 429147672Speter for (p = &open_chains; *p;) 430147672Speter { 431147672Speter struct du_chain *this = *p; 432147672Speter 433147672Speter /* Check if the chain has been terminated if it has then skip to 434147672Speter the next chain. 435147672Speter 436147672Speter This can happen when we've already appended the location to 437147672Speter the chain in Step 3, but are trying to hide in-out operands 438147672Speter from terminate_write in Step 5. */ 4391602Srgrimes 440147678Sps if (*this->loc == cc0_rtx) 44118798Speter p = &this->next_chain; 442147672Speter else 443157911Speter { 444157911Speter int regno = REGNO (*this->loc); 445147672Speter int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc)); 446147672Speter int exact_match = (regno == this_regno && nregs == this_nregs); 447147672Speter 448147672Speter if (regno + nregs <= this_regno 449147672Speter || this_regno + this_nregs <= regno) 450147672Speter { 451147672Speter p = &this->next_chain; 452147672Speter continue; 4531602Srgrimes } 454 455 if (action == mark_read) 456 { 457 if (! exact_match) 458 abort (); 459 460 /* ??? Class NO_REGS can happen if the md file makes use of 461 EXTRA_CONSTRAINTS to match registers. Which is arguably 462 wrong, but there we are. Since we know not what this may 463 be replaced with, terminate the chain. */ 464 if (class != NO_REGS) 465 { 466 this = (struct du_chain *) 467 obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 468 this->next_use = 0; 469 this->next_chain = (*p)->next_chain; 470 this->loc = loc; 471 this->insn = insn; 472 this->class = class; 473 this->need_caller_save_reg = 0; 474 while (*p) 475 p = &(*p)->next_use; 476 *p = this; 477 return; 478 } 479 } 480 481 if (action != terminate_overlapping_read || ! exact_match) 482 { 483 struct du_chain *next = this->next_chain; 484 485 /* Whether the terminated chain can be used for renaming 486 depends on the action and this being an exact match. 487 In either case, we remove this element from open_chains. */ 488 489 if ((action == terminate_dead || action == terminate_write) 490 && exact_match) 491 { 492 this->next_chain = closed_chains; 493 closed_chains = this; 494 if (rtl_dump_file) 495 fprintf (rtl_dump_file, 496 "Closing chain %s at insn %d (%s)\n", 497 reg_names[REGNO (*this->loc)], INSN_UID (insn), 498 scan_actions_name[(int) action]); 499 } 500 else 501 { 502 if (rtl_dump_file) 503 fprintf (rtl_dump_file, 504 "Discarding chain %s at insn %d (%s)\n", 505 reg_names[REGNO (*this->loc)], INSN_UID (insn), 506 scan_actions_name[(int) action]); 507 } 508 *p = next; 509 } 510 else 511 p = &this->next_chain; 512 } 513 } 514} 515 516/* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 517 BASE_REG_CLASS depending on how the register is being considered. */ 518 519static void 520scan_rtx_address (insn, loc, class, action, mode) 521 rtx insn; 522 rtx *loc; 523 enum reg_class class; 524 enum scan_actions action; 525 enum machine_mode mode; 526{ 527 rtx x = *loc; 528 RTX_CODE code = GET_CODE (x); 529 const char *fmt; 530 int i, j; 531 532 if (action == mark_write) 533 return; 534 535 switch (code) 536 { 537 case PLUS: 538 { 539 rtx orig_op0 = XEXP (x, 0); 540 rtx orig_op1 = XEXP (x, 1); 541 RTX_CODE code0 = GET_CODE (orig_op0); 542 RTX_CODE code1 = GET_CODE (orig_op1); 543 rtx op0 = orig_op0; 544 rtx op1 = orig_op1; 545 rtx *locI = NULL; 546 rtx *locB = NULL; 547 548 if (GET_CODE (op0) == SUBREG) 549 { 550 op0 = SUBREG_REG (op0); 551 code0 = GET_CODE (op0); 552 } 553 554 if (GET_CODE (op1) == SUBREG) 555 { 556 op1 = SUBREG_REG (op1); 557 code1 = GET_CODE (op1); 558 } 559 560 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 561 || code0 == ZERO_EXTEND || code1 == MEM) 562 { 563 locI = &XEXP (x, 0); 564 locB = &XEXP (x, 1); 565 } 566 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 567 || code1 == ZERO_EXTEND || code0 == MEM) 568 { 569 locI = &XEXP (x, 1); 570 locB = &XEXP (x, 0); 571 } 572 else if (code0 == CONST_INT || code0 == CONST 573 || code0 == SYMBOL_REF || code0 == LABEL_REF) 574 locB = &XEXP (x, 1); 575 else if (code1 == CONST_INT || code1 == CONST 576 || code1 == SYMBOL_REF || code1 == LABEL_REF) 577 locB = &XEXP (x, 0); 578 else if (code0 == REG && code1 == REG) 579 { 580 int index_op; 581 582 if (REG_OK_FOR_INDEX_P (op0) 583 && REG_MODE_OK_FOR_BASE_P (op1, mode)) 584 index_op = 0; 585 else if (REG_OK_FOR_INDEX_P (op1) 586 && REG_MODE_OK_FOR_BASE_P (op0, mode)) 587 index_op = 1; 588 else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 589 index_op = 0; 590 else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 591 index_op = 1; 592 else if (REG_OK_FOR_INDEX_P (op1)) 593 index_op = 1; 594 else 595 index_op = 0; 596 597 locI = &XEXP (x, index_op); 598 locB = &XEXP (x, !index_op); 599 } 600 else if (code0 == REG) 601 { 602 locI = &XEXP (x, 0); 603 locB = &XEXP (x, 1); 604 } 605 else if (code1 == REG) 606 { 607 locI = &XEXP (x, 1); 608 locB = &XEXP (x, 0); 609 } 610 611 if (locI) 612 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode); 613 if (locB) 614 scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode); 615 return; 616 } 617 618 case POST_INC: 619 case POST_DEC: 620 case POST_MODIFY: 621 case PRE_INC: 622 case PRE_DEC: 623 case PRE_MODIFY: 624#ifndef AUTO_INC_DEC 625 /* If the target doesn't claim to handle autoinc, this must be 626 something special, like a stack push. Kill this chain. */ 627 action = terminate_all_read; 628#endif 629 break; 630 631 case MEM: 632 scan_rtx_address (insn, &XEXP (x, 0), 633 MODE_BASE_REG_CLASS (GET_MODE (x)), action, 634 GET_MODE (x)); 635 return; 636 637 case REG: 638 scan_rtx_reg (insn, loc, class, action, OP_IN, 0); 639 return; 640 641 default: 642 break; 643 } 644 645 fmt = GET_RTX_FORMAT (code); 646 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 647 { 648 if (fmt[i] == 'e') 649 scan_rtx_address (insn, &XEXP (x, i), class, action, mode); 650 else if (fmt[i] == 'E') 651 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 652 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode); 653 } 654} 655 656static void 657scan_rtx (insn, loc, class, action, type, earlyclobber) 658 rtx insn; 659 rtx *loc; 660 enum reg_class class; 661 enum scan_actions action; 662 enum op_type type; 663 int earlyclobber; 664{ 665 const char *fmt; 666 rtx x = *loc; 667 enum rtx_code code = GET_CODE (x); 668 int i, j; 669 670 code = GET_CODE (x); 671 switch (code) 672 { 673 case CONST: 674 case CONST_INT: 675 case CONST_DOUBLE: 676 case SYMBOL_REF: 677 case LABEL_REF: 678 case CC0: 679 case PC: 680 return; 681 682 case REG: 683 scan_rtx_reg (insn, loc, class, action, type, earlyclobber); 684 return; 685 686 case MEM: 687 scan_rtx_address (insn, &XEXP (x, 0), 688 MODE_BASE_REG_CLASS (GET_MODE (x)), action, 689 GET_MODE (x)); 690 return; 691 692 case SET: 693 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0); 694 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 0); 695 return; 696 697 case STRICT_LOW_PART: 698 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber); 699 return; 700 701 case ZERO_EXTRACT: 702 case SIGN_EXTRACT: 703 scan_rtx (insn, &XEXP (x, 0), class, action, 704 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber); 705 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0); 706 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0); 707 return; 708 709 case POST_INC: 710 case PRE_INC: 711 case POST_DEC: 712 case PRE_DEC: 713 case POST_MODIFY: 714 case PRE_MODIFY: 715 /* Should only happen inside MEM. */ 716 abort (); 717 718 case CLOBBER: 719 scan_rtx (insn, &SET_DEST (x), class, action, OP_OUT, 1); 720 return; 721 722 case EXPR_LIST: 723 scan_rtx (insn, &XEXP (x, 0), class, action, type, 0); 724 if (XEXP (x, 1)) 725 scan_rtx (insn, &XEXP (x, 1), class, action, type, 0); 726 return; 727 728 default: 729 break; 730 } 731 732 fmt = GET_RTX_FORMAT (code); 733 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 734 { 735 if (fmt[i] == 'e') 736 scan_rtx (insn, &XEXP (x, i), class, action, type, 0); 737 else if (fmt[i] == 'E') 738 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 739 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0); 740 } 741} 742 743/* Build def/use chain */ 744 745static struct du_chain * 746build_def_use (bb) 747 basic_block bb; 748{ 749 rtx insn; 750 751 open_chains = closed_chains = NULL; 752 753 for (insn = bb->head; ; insn = NEXT_INSN (insn)) 754 { 755 if (INSN_P (insn)) 756 { 757 int n_ops; 758 rtx note; 759 rtx old_operands[MAX_RECOG_OPERANDS]; 760 rtx old_dups[MAX_DUP_OPERANDS]; 761 int i; 762 int alt; 763 int predicated; 764 765 /* Process the insn, determining its effect on the def-use 766 chains. We perform the following steps with the register 767 references in the insn: 768 (1) Any read that overlaps an open chain, but doesn't exactly 769 match, causes that chain to be closed. We can't deal 770 with overlaps yet. 771 (2) Any read outside an operand causes any chain it overlaps 772 with to be closed, since we can't replace it. 773 (3) Any read inside an operand is added if there's already 774 an open chain for it. 775 (4) For any REG_DEAD note we find, close open chains that 776 overlap it. 777 (5) For any write we find, close open chains that overlap it. 778 (6) For any write we find in an operand, make a new chain. 779 (7) For any REG_UNUSED, close any chains we just opened. */ 780 781 extract_insn (insn); 782 constrain_operands (1); 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 old_dups[i] = *recog_data.dup_loc[i]; 825 *recog_data.dup_loc[i] = cc0_rtx; 826 } 827 828 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, 829 OP_IN, 0); 830 831 for (i = 0; i < recog_data.n_dups; i++) 832 *recog_data.dup_loc[i] = old_dups[i]; 833 for (i = 0; i < n_ops; i++) 834 *recog_data.operand_loc[i] = old_operands[i]; 835 836 /* Step 2B: Can't rename function call argument registers. */ 837 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn)) 838 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), 839 NO_REGS, terminate_all_read, OP_IN, 0); 840 841 /* Step 2C: Can't rename asm operands that were originally 842 hard registers. */ 843 if (asm_noperands (PATTERN (insn)) > 0) 844 for (i = 0; i < n_ops; i++) 845 { 846 rtx *loc = recog_data.operand_loc[i]; 847 rtx op = *loc; 848 849 if (GET_CODE (op) == REG 850 && REGNO (op) == ORIGINAL_REGNO (op) 851 && (recog_data.operand_type[i] == OP_IN 852 || recog_data.operand_type[i] == OP_INOUT)) 853 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0); 854 } 855 856 /* Step 3: Append to chains for reads inside operands. */ 857 for (i = 0; i < n_ops + recog_data.n_dups; i++) 858 { 859 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 860 rtx *loc = (i < n_ops 861 ? recog_data.operand_loc[opn] 862 : recog_data.dup_loc[i - n_ops]); 863 enum reg_class class = recog_op_alt[opn][alt].class; 864 enum op_type type = recog_data.operand_type[opn]; 865 866 /* Don't scan match_operand here, since we've no reg class 867 information to pass down. Any operands that we could 868 substitute in will be represented elsewhere. */ 869 if (recog_data.constraints[opn][0] == '\0') 870 continue; 871 872 if (recog_op_alt[opn][alt].is_address) 873 scan_rtx_address (insn, loc, class, mark_read, VOIDmode); 874 else 875 scan_rtx (insn, loc, class, mark_read, type, 0); 876 } 877 878 /* Step 4: Close chains for registers that die here. 879 Also record updates for REG_INC notes. */ 880 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 881 { 882 if (REG_NOTE_KIND (note) == REG_DEAD) 883 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 884 OP_IN, 0); 885 else if (REG_NOTE_KIND (note) == REG_INC) 886 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, 887 OP_INOUT, 0); 888 } 889 890 /* Step 4B: If this is a call, any chain live at this point 891 requires a caller-saved reg. */ 892 if (GET_CODE (insn) == CALL_INSN) 893 { 894 struct du_chain *p; 895 for (p = open_chains; p; p = p->next_chain) 896 p->need_caller_save_reg = 1; 897 } 898 899 /* Step 5: Close open chains that overlap writes. Similar to 900 step 2, we hide in-out operands, since we do not want to 901 close these chains. */ 902 903 for (i = 0; i < n_ops; i++) 904 { 905 old_operands[i] = recog_data.operand[i]; 906 if (recog_data.operand_type[i] == OP_INOUT) 907 *recog_data.operand_loc[i] = cc0_rtx; 908 } 909 for (i = 0; i < recog_data.n_dups; i++) 910 { 911 int opn = recog_data.dup_num[i]; 912 old_dups[i] = *recog_data.dup_loc[i]; 913 if (recog_data.operand_type[opn] == OP_INOUT) 914 *recog_data.dup_loc[i] = cc0_rtx; 915 } 916 917 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0); 918 919 for (i = 0; i < recog_data.n_dups; i++) 920 *recog_data.dup_loc[i] = old_dups[i]; 921 for (i = 0; i < n_ops; i++) 922 *recog_data.operand_loc[i] = old_operands[i]; 923 924 /* Step 6: Begin new chains for writes inside operands. */ 925 /* ??? Many targets have output constraints on the SET_DEST 926 of a call insn, which is stupid, since these are certainly 927 ABI defined hard registers. Don't change calls at all. 928 Similarly take special care for asm statement that originally 929 referenced hard registers. */ 930 if (asm_noperands (PATTERN (insn)) > 0) 931 { 932 for (i = 0; i < n_ops; i++) 933 if (recog_data.operand_type[i] == OP_OUT) 934 { 935 rtx *loc = recog_data.operand_loc[i]; 936 rtx op = *loc; 937 enum reg_class class = recog_op_alt[i][alt].class; 938 939 if (GET_CODE (op) == REG 940 && REGNO (op) == ORIGINAL_REGNO (op)) 941 continue; 942 943 scan_rtx (insn, loc, class, mark_write, OP_OUT, 944 recog_op_alt[i][alt].earlyclobber); 945 } 946 } 947 else if (GET_CODE (insn) != CALL_INSN) 948 for (i = 0; i < n_ops + recog_data.n_dups; i++) 949 { 950 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 951 rtx *loc = (i < n_ops 952 ? recog_data.operand_loc[opn] 953 : recog_data.dup_loc[i - n_ops]); 954 enum reg_class class = recog_op_alt[opn][alt].class; 955 956 if (recog_data.operand_type[opn] == OP_OUT) 957 scan_rtx (insn, loc, class, mark_write, OP_OUT, 958 recog_op_alt[opn][alt].earlyclobber); 959 } 960 961 /* Step 7: Close chains for registers that were never 962 really used here. */ 963 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 964 if (REG_NOTE_KIND (note) == REG_UNUSED) 965 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 966 OP_IN, 0); 967 } 968 if (insn == bb->end) 969 break; 970 } 971 972 /* Since we close every chain when we find a REG_DEAD note, anything that 973 is still open lives past the basic block, so it can't be renamed. */ 974 return closed_chains; 975} 976 977/* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are 978 printed in reverse order as that's how we build them. */ 979 980static void 981dump_def_use_chain (chains) 982 struct du_chain *chains; 983{ 984 while (chains) 985 { 986 struct du_chain *this = chains; 987 int r = REGNO (*this->loc); 988 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc)); 989 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs); 990 while (this) 991 { 992 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn), 993 reg_class_names[this->class]); 994 this = this->next_use; 995 } 996 fprintf (rtl_dump_file, "\n"); 997 chains = chains->next_chain; 998 } 999} 1000 1001/* The following code does forward propagation of hard register copies. 1002 The object is to eliminate as many dependencies as possible, so that 1003 we have the most scheduling freedom. As a side effect, we also clean 1004 up some silly register allocation decisions made by reload. This 1005 code may be obsoleted by a new register allocator. */ 1006 1007/* For each register, we have a list of registers that contain the same 1008 value. The OLDEST_REGNO field points to the head of the list, and 1009 the NEXT_REGNO field runs through the list. The MODE field indicates 1010 what mode the data is known to be in; this field is VOIDmode when the 1011 register is not known to contain valid data. */ 1012 1013struct value_data_entry 1014{ 1015 enum machine_mode mode; 1016 unsigned int oldest_regno; 1017 unsigned int next_regno; 1018}; 1019 1020struct value_data 1021{ 1022 struct value_data_entry e[FIRST_PSEUDO_REGISTER]; 1023 unsigned int max_value_regs; 1024}; 1025 1026static void kill_value_regno PARAMS ((unsigned, struct value_data *)); 1027static void kill_value PARAMS ((rtx, struct value_data *)); 1028static void set_value_regno PARAMS ((unsigned, enum machine_mode, 1029 struct value_data *)); 1030static void init_value_data PARAMS ((struct value_data *)); 1031static void kill_clobbered_value PARAMS ((rtx, rtx, void *)); 1032static void kill_set_value PARAMS ((rtx, rtx, void *)); 1033static int kill_autoinc_value PARAMS ((rtx *, void *)); 1034static void copy_value PARAMS ((rtx, rtx, struct value_data *)); 1035static bool mode_change_ok PARAMS ((enum machine_mode, enum machine_mode, 1036 unsigned int)); 1037static rtx find_oldest_value_reg PARAMS ((enum reg_class, rtx, 1038 struct value_data *)); 1039static bool replace_oldest_value_reg PARAMS ((rtx *, enum reg_class, rtx, 1040 struct value_data *)); 1041static bool replace_oldest_value_addr PARAMS ((rtx *, enum reg_class, 1042 enum machine_mode, rtx, 1043 struct value_data *)); 1044static bool replace_oldest_value_mem PARAMS ((rtx, rtx, struct value_data *)); 1045static bool copyprop_hardreg_forward_1 PARAMS ((basic_block, 1046 struct value_data *)); 1047extern void debug_value_data PARAMS ((struct value_data *)); 1048#ifdef ENABLE_CHECKING 1049static void validate_value_data PARAMS ((struct value_data *)); 1050#endif 1051 1052/* Kill register REGNO. This involves removing it from any value lists, 1053 and resetting the value mode to VOIDmode. */ 1054 1055static void 1056kill_value_regno (regno, vd) 1057 unsigned int regno; 1058 struct value_data *vd; 1059{ 1060 unsigned int i, next; 1061 1062 if (vd->e[regno].oldest_regno != regno) 1063 { 1064 for (i = vd->e[regno].oldest_regno; 1065 vd->e[i].next_regno != regno; 1066 i = vd->e[i].next_regno) 1067 continue; 1068 vd->e[i].next_regno = vd->e[regno].next_regno; 1069 } 1070 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) 1071 { 1072 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) 1073 vd->e[i].oldest_regno = next; 1074 } 1075 1076 vd->e[regno].mode = VOIDmode; 1077 vd->e[regno].oldest_regno = regno; 1078 vd->e[regno].next_regno = INVALID_REGNUM; 1079 1080#ifdef ENABLE_CHECKING 1081 validate_value_data (vd); 1082#endif 1083} 1084 1085/* Kill X. This is a convenience function for kill_value_regno 1086 so that we mind the mode the register is in. */ 1087 1088static void 1089kill_value (x, vd) 1090 rtx x; 1091 struct value_data *vd; 1092{ 1093 if (REG_P (x)) 1094 { 1095 unsigned int regno = REGNO (x); 1096 unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); 1097 unsigned int i, j; 1098 1099 /* Kill the value we're told to kill. */ 1100 for (i = 0; i < n; ++i) 1101 kill_value_regno (regno + i, vd); 1102 1103 /* Kill everything that overlapped what we're told to kill. */ 1104 if (regno < vd->max_value_regs) 1105 j = 0; 1106 else 1107 j = regno - vd->max_value_regs; 1108 for (; j < regno; ++j) 1109 { 1110 if (vd->e[j].mode == VOIDmode) 1111 continue; 1112 n = HARD_REGNO_NREGS (j, vd->e[j].mode); 1113 if (j + n > regno) 1114 for (i = 0; i < n; ++i) 1115 kill_value_regno (j + i, vd); 1116 } 1117 } 1118} 1119 1120/* Remember that REGNO is valid in MODE. */ 1121 1122static void 1123set_value_regno (regno, mode, vd) 1124 unsigned int regno; 1125 enum machine_mode mode; 1126 struct value_data *vd; 1127{ 1128 unsigned int nregs; 1129 1130 vd->e[regno].mode = mode; 1131 1132 nregs = HARD_REGNO_NREGS (regno, mode); 1133 if (nregs > vd->max_value_regs) 1134 vd->max_value_regs = nregs; 1135} 1136 1137/* Initialize VD such that there are no known relationships between regs. */ 1138 1139static void 1140init_value_data (vd) 1141 struct value_data *vd; 1142{ 1143 int i; 1144 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1145 { 1146 vd->e[i].mode = VOIDmode; 1147 vd->e[i].oldest_regno = i; 1148 vd->e[i].next_regno = INVALID_REGNUM; 1149 } 1150 vd->max_value_regs = 0; 1151} 1152 1153/* Called through note_stores. If X is clobbered, kill its value. */ 1154 1155static void 1156kill_clobbered_value (x, set, data) 1157 rtx x; 1158 rtx set; 1159 void *data; 1160{ 1161 struct value_data *vd = data; 1162 if (GET_CODE (set) == CLOBBER) 1163 kill_value (x, vd); 1164} 1165 1166/* Called through note_stores. If X is set, not clobbered, kill its 1167 current value and install it as the root of its own value list. */ 1168 1169static void 1170kill_set_value (x, set, data) 1171 rtx x; 1172 rtx set; 1173 void *data; 1174{ 1175 struct value_data *vd = data; 1176 if (GET_CODE (set) != CLOBBER && REG_P (x)) 1177 { 1178 kill_value (x, vd); 1179 set_value_regno (REGNO (x), GET_MODE (x), vd); 1180 } 1181} 1182 1183/* Called through for_each_rtx. Kill any register used as the base of an 1184 auto-increment expression, and install that register as the root of its 1185 own value list. */ 1186 1187static int 1188kill_autoinc_value (px, data) 1189 rtx *px; 1190 void *data; 1191{ 1192 rtx x = *px; 1193 struct value_data *vd = data; 1194 1195 if (GET_RTX_CLASS (GET_CODE (x)) == 'a') 1196 { 1197 x = XEXP (x, 0); 1198 kill_value (x, vd); 1199 set_value_regno (REGNO (x), Pmode, vd); 1200 return -1; 1201 } 1202 1203 return 0; 1204} 1205 1206/* Assert that SRC has been copied to DEST. Adjust the data structures 1207 to reflect that SRC contains an older copy of the shared value. */ 1208 1209static void 1210copy_value (dest, src, vd) 1211 rtx dest; 1212 rtx src; 1213 struct value_data *vd; 1214{ 1215 unsigned int dr = REGNO (dest); 1216 unsigned int sr = REGNO (src); 1217 unsigned int dn, sn; 1218 unsigned int i; 1219 1220 /* ??? At present, it's possible to see noop sets. It'd be nice if 1221 this were cleaned up beforehand... */ 1222 if (sr == dr) 1223 return; 1224 1225 /* Do not propagate copies to the stack pointer, as that can leave 1226 memory accesses with no scheduling dependancy on the stack update. */ 1227 if (dr == STACK_POINTER_REGNUM) 1228 return; 1229 1230 /* Likewise with the frame pointer, if we're using one. */ 1231 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) 1232 return; 1233 1234 /* If SRC and DEST overlap, don't record anything. */ 1235 dn = HARD_REGNO_NREGS (dr, GET_MODE (dest)); 1236 sn = HARD_REGNO_NREGS (sr, GET_MODE (dest)); 1237 if ((dr > sr && dr < sr + sn) 1238 || (sr > dr && sr < dr + dn)) 1239 return; 1240 1241 /* If SRC had no assigned mode (i.e. we didn't know it was live) 1242 assign it now and assume the value came from an input argument 1243 or somesuch. */ 1244 if (vd->e[sr].mode == VOIDmode) 1245 set_value_regno (sr, vd->e[dr].mode, vd); 1246 1247 /* If SRC had been assigned a mode narrower than the copy, we can't 1248 link DEST into the chain, because not all of the pieces of the 1249 copy came from oldest_regno. */ 1250 else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)) 1251 return; 1252 1253 /* Link DR at the end of the value chain used by SR. */ 1254 1255 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; 1256 1257 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) 1258 continue; 1259 vd->e[i].next_regno = dr; 1260 1261#ifdef ENABLE_CHECKING 1262 validate_value_data (vd); 1263#endif 1264} 1265 1266/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ 1267 1268static bool 1269mode_change_ok (orig_mode, new_mode, regno) 1270 enum machine_mode orig_mode, new_mode; 1271 unsigned int regno ATTRIBUTE_UNUSED; 1272{ 1273 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) 1274 return false; 1275 1276#ifdef CLASS_CANNOT_CHANGE_MODE 1277 if (TEST_HARD_REG_BIT (reg_class_contents[CLASS_CANNOT_CHANGE_MODE], regno) 1278 && CLASS_CANNOT_CHANGE_MODE_P (orig_mode, new_mode)) 1279 return false; 1280#endif 1281 1282 return true; 1283} 1284 1285/* Find the oldest copy of the value contained in REGNO that is in 1286 register class CLASS and has mode MODE. If found, return an rtx 1287 of that oldest register, otherwise return NULL. */ 1288 1289static rtx 1290find_oldest_value_reg (class, reg, vd) 1291 enum reg_class class; 1292 rtx reg; 1293 struct value_data *vd; 1294{ 1295 unsigned int regno = REGNO (reg); 1296 enum machine_mode mode = GET_MODE (reg); 1297 unsigned int i; 1298 1299 /* If we are accessing REG in some mode other that what we set it in, 1300 make sure that the replacement is valid. In particular, consider 1301 (set (reg:DI r11) (...)) 1302 (set (reg:SI r9) (reg:SI r11)) 1303 (set (reg:SI r10) (...)) 1304 (set (...) (reg:DI r9)) 1305 Replacing r9 with r11 is invalid. */ 1306 if (mode != vd->e[regno].mode) 1307 { 1308 if (HARD_REGNO_NREGS (regno, mode) 1309 > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 1310 return NULL_RTX; 1311 } 1312 1313 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) 1314 if (TEST_HARD_REG_BIT (reg_class_contents[class], i) 1315 && (vd->e[i].mode == mode 1316 || mode_change_ok (vd->e[i].mode, mode, i))) 1317 { 1318 rtx new = gen_rtx_raw_REG (mode, i); 1319 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg); 1320 return new; 1321 } 1322 1323 return NULL_RTX; 1324} 1325 1326/* If possible, replace the register at *LOC with the oldest register 1327 in register class CLASS. Return true if successfully replaced. */ 1328 1329static bool 1330replace_oldest_value_reg (loc, class, insn, vd) 1331 rtx *loc; 1332 enum reg_class class; 1333 rtx insn; 1334 struct value_data *vd; 1335{ 1336 rtx new = find_oldest_value_reg (class, *loc, vd); 1337 if (new) 1338 { 1339 if (rtl_dump_file) 1340 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n", 1341 INSN_UID (insn), REGNO (*loc), REGNO (new)); 1342 1343 *loc = new; 1344 return true; 1345 } 1346 return false; 1347} 1348 1349/* Similar to replace_oldest_value_reg, but *LOC contains an address. 1350 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 1351 BASE_REG_CLASS depending on how the register is being considered. */ 1352 1353static bool 1354replace_oldest_value_addr (loc, class, mode, insn, vd) 1355 rtx *loc; 1356 enum reg_class class; 1357 enum machine_mode mode; 1358 rtx insn; 1359 struct value_data *vd; 1360{ 1361 rtx x = *loc; 1362 RTX_CODE code = GET_CODE (x); 1363 const char *fmt; 1364 int i, j; 1365 bool changed = false; 1366 1367 switch (code) 1368 { 1369 case PLUS: 1370 { 1371 rtx orig_op0 = XEXP (x, 0); 1372 rtx orig_op1 = XEXP (x, 1); 1373 RTX_CODE code0 = GET_CODE (orig_op0); 1374 RTX_CODE code1 = GET_CODE (orig_op1); 1375 rtx op0 = orig_op0; 1376 rtx op1 = orig_op1; 1377 rtx *locI = NULL; 1378 rtx *locB = NULL; 1379 1380 if (GET_CODE (op0) == SUBREG) 1381 { 1382 op0 = SUBREG_REG (op0); 1383 code0 = GET_CODE (op0); 1384 } 1385 1386 if (GET_CODE (op1) == SUBREG) 1387 { 1388 op1 = SUBREG_REG (op1); 1389 code1 = GET_CODE (op1); 1390 } 1391 1392 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 1393 || code0 == ZERO_EXTEND || code1 == MEM) 1394 { 1395 locI = &XEXP (x, 0); 1396 locB = &XEXP (x, 1); 1397 } 1398 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 1399 || code1 == ZERO_EXTEND || code0 == MEM) 1400 { 1401 locI = &XEXP (x, 1); 1402 locB = &XEXP (x, 0); 1403 } 1404 else if (code0 == CONST_INT || code0 == CONST 1405 || code0 == SYMBOL_REF || code0 == LABEL_REF) 1406 locB = &XEXP (x, 1); 1407 else if (code1 == CONST_INT || code1 == CONST 1408 || code1 == SYMBOL_REF || code1 == LABEL_REF) 1409 locB = &XEXP (x, 0); 1410 else if (code0 == REG && code1 == REG) 1411 { 1412 int index_op; 1413 1414 if (REG_OK_FOR_INDEX_P (op0) 1415 && REG_MODE_OK_FOR_BASE_P (op1, mode)) 1416 index_op = 0; 1417 else if (REG_OK_FOR_INDEX_P (op1) 1418 && REG_MODE_OK_FOR_BASE_P (op0, mode)) 1419 index_op = 1; 1420 else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 1421 index_op = 0; 1422 else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 1423 index_op = 1; 1424 else if (REG_OK_FOR_INDEX_P (op1)) 1425 index_op = 1; 1426 else 1427 index_op = 0; 1428 1429 locI = &XEXP (x, index_op); 1430 locB = &XEXP (x, !index_op); 1431 } 1432 else if (code0 == REG) 1433 { 1434 locI = &XEXP (x, 0); 1435 locB = &XEXP (x, 1); 1436 } 1437 else if (code1 == REG) 1438 { 1439 locI = &XEXP (x, 1); 1440 locB = &XEXP (x, 0); 1441 } 1442 1443 if (locI) 1444 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode, 1445 insn, vd); 1446 if (locB) 1447 changed |= replace_oldest_value_addr (locB, 1448 MODE_BASE_REG_CLASS (mode), 1449 mode, insn, vd); 1450 return changed; 1451 } 1452 1453 case POST_INC: 1454 case POST_DEC: 1455 case POST_MODIFY: 1456 case PRE_INC: 1457 case PRE_DEC: 1458 case PRE_MODIFY: 1459 return false; 1460 1461 case MEM: 1462 return replace_oldest_value_mem (x, insn, vd); 1463 1464 case REG: 1465 return replace_oldest_value_reg (loc, class, insn, vd); 1466 1467 default: 1468 break; 1469 } 1470 1471 fmt = GET_RTX_FORMAT (code); 1472 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1473 { 1474 if (fmt[i] == 'e') 1475 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode, 1476 insn, vd); 1477 else if (fmt[i] == 'E') 1478 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1479 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class, 1480 mode, insn, vd); 1481 } 1482 1483 return changed; 1484} 1485 1486/* Similar to replace_oldest_value_reg, but X contains a memory. */ 1487 1488static bool 1489replace_oldest_value_mem (x, insn, vd) 1490 rtx x; 1491 rtx insn; 1492 struct value_data *vd; 1493{ 1494 return replace_oldest_value_addr (&XEXP (x, 0), 1495 MODE_BASE_REG_CLASS (GET_MODE (x)), 1496 GET_MODE (x), insn, vd); 1497} 1498 1499/* Perform the forward copy propagation on basic block BB. */ 1500 1501static bool 1502copyprop_hardreg_forward_1 (bb, vd) 1503 basic_block bb; 1504 struct value_data *vd; 1505{ 1506 bool changed = false; 1507 rtx insn; 1508 1509 for (insn = bb->head; ; insn = NEXT_INSN (insn)) 1510 { 1511 int n_ops, i, alt, predicated; 1512 bool is_asm; 1513 rtx set; 1514 1515 if (! INSN_P (insn)) 1516 { 1517 if (insn == bb->end) 1518 break; 1519 else 1520 continue; 1521 } 1522 1523 set = single_set (insn); 1524 extract_insn (insn); 1525 constrain_operands (1); 1526 preprocess_constraints (); 1527 alt = which_alternative; 1528 n_ops = recog_data.n_operands; 1529 is_asm = asm_noperands (PATTERN (insn)) >= 0; 1530 1531 /* Simplify the code below by rewriting things to reflect 1532 matching constraints. Also promote OP_OUT to OP_INOUT 1533 in predicated instructions. */ 1534 1535 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 1536 for (i = 0; i < n_ops; ++i) 1537 { 1538 int matches = recog_op_alt[i][alt].matches; 1539 if (matches >= 0) 1540 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; 1541 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 1542 || (predicated && recog_data.operand_type[i] == OP_OUT)) 1543 recog_data.operand_type[i] = OP_INOUT; 1544 } 1545 1546 /* For each earlyclobber operand, zap the value data. */ 1547 for (i = 0; i < n_ops; i++) 1548 if (recog_op_alt[i][alt].earlyclobber) 1549 kill_value (recog_data.operand[i], vd); 1550 1551 /* Within asms, a clobber cannot overlap inputs or outputs. 1552 I wouldn't think this were true for regular insns, but 1553 scan_rtx treats them like that... */ 1554 note_stores (PATTERN (insn), kill_clobbered_value, vd); 1555 1556 /* Kill all auto-incremented values. */ 1557 /* ??? REG_INC is useless, since stack pushes aren't done that way. */ 1558 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); 1559 1560 /* Kill all early-clobbered operands. */ 1561 for (i = 0; i < n_ops; i++) 1562 if (recog_op_alt[i][alt].earlyclobber) 1563 kill_value (recog_data.operand[i], vd); 1564 1565 /* Special-case plain move instructions, since we may well 1566 be able to do the move from a different register class. */ 1567 if (set && REG_P (SET_SRC (set))) 1568 { 1569 rtx src = SET_SRC (set); 1570 unsigned int regno = REGNO (src); 1571 enum machine_mode mode = GET_MODE (src); 1572 unsigned int i; 1573 rtx new; 1574 1575 /* If we are accessing SRC in some mode other that what we 1576 set it in, make sure that the replacement is valid. */ 1577 if (mode != vd->e[regno].mode) 1578 { 1579 if (HARD_REGNO_NREGS (regno, mode) 1580 > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 1581 goto no_move_special_case; 1582 } 1583 1584 /* If the destination is also a register, try to find a source 1585 register in the same class. */ 1586 if (REG_P (SET_DEST (set))) 1587 { 1588 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); 1589 if (new && validate_change (insn, &SET_SRC (set), new, 0)) 1590 { 1591 if (rtl_dump_file) 1592 fprintf (rtl_dump_file, 1593 "insn %u: replaced reg %u with %u\n", 1594 INSN_UID (insn), regno, REGNO (new)); 1595 changed = true; 1596 goto did_replacement; 1597 } 1598 } 1599 1600 /* Otherwise, try all valid registers and see if its valid. */ 1601 for (i = vd->e[regno].oldest_regno; i != regno; 1602 i = vd->e[i].next_regno) 1603 if (vd->e[i].mode == mode 1604 || mode_change_ok (vd->e[i].mode, mode, i)) 1605 { 1606 new = gen_rtx_raw_REG (mode, i); 1607 if (validate_change (insn, &SET_SRC (set), new, 0)) 1608 { 1609 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src); 1610 if (rtl_dump_file) 1611 fprintf (rtl_dump_file, 1612 "insn %u: replaced reg %u with %u\n", 1613 INSN_UID (insn), regno, REGNO (new)); 1614 changed = true; 1615 goto did_replacement; 1616 } 1617 } 1618 } 1619 no_move_special_case: 1620 1621 /* For each input operand, replace a hard register with the 1622 eldest live copy that's in an appropriate register class. */ 1623 for (i = 0; i < n_ops; i++) 1624 { 1625 bool replaced = false; 1626 1627 /* Don't scan match_operand here, since we've no reg class 1628 information to pass down. Any operands that we could 1629 substitute in will be represented elsewhere. */ 1630 if (recog_data.constraints[i][0] == '\0') 1631 continue; 1632 1633 /* Don't replace in asms intentionally referencing hard regs. */ 1634 if (is_asm && GET_CODE (recog_data.operand[i]) == REG 1635 && (REGNO (recog_data.operand[i]) 1636 == ORIGINAL_REGNO (recog_data.operand[i]))) 1637 continue; 1638 1639 if (recog_data.operand_type[i] == OP_IN) 1640 { 1641 if (recog_op_alt[i][alt].is_address) 1642 replaced 1643 = replace_oldest_value_addr (recog_data.operand_loc[i], 1644 recog_op_alt[i][alt].class, 1645 VOIDmode, insn, vd); 1646 else if (REG_P (recog_data.operand[i])) 1647 replaced 1648 = replace_oldest_value_reg (recog_data.operand_loc[i], 1649 recog_op_alt[i][alt].class, 1650 insn, vd); 1651 else if (GET_CODE (recog_data.operand[i]) == MEM) 1652 replaced = replace_oldest_value_mem (recog_data.operand[i], 1653 insn, vd); 1654 } 1655 else if (GET_CODE (recog_data.operand[i]) == MEM) 1656 replaced = replace_oldest_value_mem (recog_data.operand[i], 1657 insn, vd); 1658 1659 /* If we performed any replacement, update match_dups. */ 1660 if (replaced) 1661 { 1662 int j; 1663 rtx new; 1664 1665 changed = true; 1666 1667 new = *recog_data.operand_loc[i]; 1668 recog_data.operand[i] = new; 1669 for (j = 0; j < recog_data.n_dups; j++) 1670 if (recog_data.dup_num[j] == i) 1671 *recog_data.dup_loc[j] = new; 1672 } 1673 } 1674 1675 did_replacement: 1676 /* Clobber call-clobbered registers. */ 1677 if (GET_CODE (insn) == CALL_INSN) 1678 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1679 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1680 kill_value_regno (i, vd); 1681 1682 /* Notice stores. */ 1683 note_stores (PATTERN (insn), kill_set_value, vd); 1684 1685 /* Notice copies. */ 1686 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) 1687 copy_value (SET_DEST (set), SET_SRC (set), vd); 1688 1689 if (insn == bb->end) 1690 break; 1691 } 1692 1693 return changed; 1694} 1695 1696/* Main entry point for the forward copy propagation optimization. */ 1697 1698void 1699copyprop_hardreg_forward () 1700{ 1701 struct value_data *all_vd; 1702 bool need_refresh; 1703 int b; 1704 1705 need_refresh = false; 1706 1707 all_vd = xmalloc (sizeof (struct value_data) * n_basic_blocks); 1708 1709 for (b = 0; b < n_basic_blocks; b++) 1710 { 1711 basic_block bb = BASIC_BLOCK (b); 1712 1713 /* If a block has a single predecessor, that we've already 1714 processed, begin with the value data that was live at 1715 the end of the predecessor block. */ 1716 /* ??? Ought to use more intelligent queueing of blocks. */ 1717 if (bb->pred 1718 && ! bb->pred->pred_next 1719 && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 1720 && bb->pred->src->index != ENTRY_BLOCK 1721 && bb->pred->src->index < b) 1722 all_vd[b] = all_vd[bb->pred->src->index]; 1723 else 1724 init_value_data (all_vd + b); 1725 1726 if (copyprop_hardreg_forward_1 (bb, all_vd + b)) 1727 need_refresh = true; 1728 } 1729 1730 if (need_refresh) 1731 { 1732 if (rtl_dump_file) 1733 fputs ("\n\n", rtl_dump_file); 1734 1735 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks 1736 to scan, so we have to do a life update with no initial set of 1737 blocks Just In Case. */ 1738 delete_noop_moves (get_insns ()); 1739 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 1740 PROP_DEATH_NOTES 1741 | PROP_SCAN_DEAD_CODE 1742 | PROP_KILL_DEAD_CODE); 1743 } 1744 1745 free (all_vd); 1746} 1747 1748/* Dump the value chain data to stderr. */ 1749 1750void 1751debug_value_data (vd) 1752 struct value_data *vd; 1753{ 1754 HARD_REG_SET set; 1755 unsigned int i, j; 1756 1757 CLEAR_HARD_REG_SET (set); 1758 1759 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1760 if (vd->e[i].oldest_regno == i) 1761 { 1762 if (vd->e[i].mode == VOIDmode) 1763 { 1764 if (vd->e[i].next_regno != INVALID_REGNUM) 1765 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", 1766 i, vd->e[i].next_regno); 1767 continue; 1768 } 1769 1770 SET_HARD_REG_BIT (set, i); 1771 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); 1772 1773 for (j = vd->e[i].next_regno; 1774 j != INVALID_REGNUM; 1775 j = vd->e[j].next_regno) 1776 { 1777 if (TEST_HARD_REG_BIT (set, j)) 1778 { 1779 fprintf (stderr, "[%u] Loop in regno chain\n", j); 1780 return; 1781 } 1782 1783 if (vd->e[j].oldest_regno != i) 1784 { 1785 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", 1786 j, vd->e[j].oldest_regno); 1787 return; 1788 } 1789 SET_HARD_REG_BIT (set, j); 1790 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); 1791 } 1792 fputc ('\n', stderr); 1793 } 1794 1795 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1796 if (! TEST_HARD_REG_BIT (set, i) 1797 && (vd->e[i].mode != VOIDmode 1798 || vd->e[i].oldest_regno != i 1799 || vd->e[i].next_regno != INVALID_REGNUM)) 1800 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", 1801 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1802 vd->e[i].next_regno); 1803} 1804 1805#ifdef ENABLE_CHECKING 1806static void 1807validate_value_data (vd) 1808 struct value_data *vd; 1809{ 1810 HARD_REG_SET set; 1811 unsigned int i, j; 1812 1813 CLEAR_HARD_REG_SET (set); 1814 1815 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1816 if (vd->e[i].oldest_regno == i) 1817 { 1818 if (vd->e[i].mode == VOIDmode) 1819 { 1820 if (vd->e[i].next_regno != INVALID_REGNUM) 1821 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", 1822 i, vd->e[i].next_regno); 1823 continue; 1824 } 1825 1826 SET_HARD_REG_BIT (set, i); 1827 1828 for (j = vd->e[i].next_regno; 1829 j != INVALID_REGNUM; 1830 j = vd->e[j].next_regno) 1831 { 1832 if (TEST_HARD_REG_BIT (set, j)) 1833 internal_error ("validate_value_data: Loop in regno chain (%u)", 1834 j); 1835 if (vd->e[j].oldest_regno != i) 1836 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", 1837 j, vd->e[j].oldest_regno); 1838 1839 SET_HARD_REG_BIT (set, j); 1840 } 1841 } 1842 1843 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1844 if (! TEST_HARD_REG_BIT (set, i) 1845 && (vd->e[i].mode != VOIDmode 1846 || vd->e[i].oldest_regno != i 1847 || vd->e[i].next_regno != INVALID_REGNUM)) 1848 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", 1849 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1850 vd->e[i].next_regno); 1851} 1852#endif 1853