regrename.c revision 161651
1185029Spjd/* Register renaming for the GNU compiler. 2185029Spjd Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 3185029Spjd 4185029Spjd This file is part of GCC. 5185029Spjd 6185029Spjd GCC is free software; you can redistribute it and/or modify it 7185029Spjd under the terms of the GNU General Public License as published by 8185029Spjd the Free Software Foundation; either version 2, or (at your option) 9185029Spjd any later version. 10185029Spjd 11185029Spjd GCC is distributed in the hope that it will be useful, but WITHOUT 12185029Spjd ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13185029Spjd or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14185029Spjd License for more details. 15185029Spjd 16185029Spjd You should have received a copy of the GNU General Public License 17185029Spjd along with GCC; see the file COPYING. If not, write to the Free 18185029Spjd Software Foundation, 59 Temple Place - Suite 330, Boston, MA 19185029Spjd 02111-1307, USA. */ 20185029Spjd 21185029Spjd#define REG_OK_STRICT 22185029Spjd 23185029Spjd#include "config.h" 24185029Spjd#include "system.h" 25185029Spjd#include "coretypes.h" 26185029Spjd#include "tm.h" 27185029Spjd#include "rtl.h" 28185029Spjd#include "tm_p.h" 29185029Spjd#include "insn-config.h" 30185029Spjd#include "regs.h" 31185029Spjd#include "hard-reg-set.h" 32185029Spjd#include "basic-block.h" 33185029Spjd#include "reload.h" 34185029Spjd#include "output.h" 35185029Spjd#include "function.h" 36185029Spjd#include "recog.h" 37185029Spjd#include "flags.h" 38185029Spjd#include "toplev.h" 39185029Spjd#include "obstack.h" 40185029Spjd 41185029Spjd#ifndef REG_MODE_OK_FOR_BASE_P 42185029Spjd#define REG_MODE_OK_FOR_BASE_P(REGNO, MODE) REG_OK_FOR_BASE_P (REGNO) 43185029Spjd#endif 44185029Spjd 45185029Spjdstatic const char *const reg_class_names[] = REG_CLASS_NAMES; 46185029Spjd 47185029Spjdstruct du_chain 48185029Spjd{ 49185029Spjd struct du_chain *next_chain; 50185029Spjd struct du_chain *next_use; 51185029Spjd 52185029Spjd rtx insn; 53185029Spjd rtx *loc; 54185029Spjd ENUM_BITFIELD(reg_class) class : 16; 55185029Spjd unsigned int need_caller_save_reg:1; 56185029Spjd unsigned int earlyclobber:1; 57185029Spjd}; 58185029Spjd 59185029Spjdenum scan_actions 60185029Spjd{ 61185029Spjd terminate_all_read, 62185029Spjd terminate_overlapping_read, 63185029Spjd terminate_write, 64185029Spjd terminate_dead, 65185029Spjd mark_read, 66185029Spjd mark_write 67185029Spjd}; 68185029Spjd 69185029Spjdstatic const char * const scan_actions_name[] = 70185029Spjd{ 71185029Spjd "terminate_all_read", 72185029Spjd "terminate_overlapping_read", 73185029Spjd "terminate_write", 74185029Spjd "terminate_dead", 75185029Spjd "mark_read", 76185029Spjd "mark_write" 77185029Spjd}; 78185029Spjd 79185029Spjdstatic struct obstack rename_obstack; 80185029Spjd 81185029Spjdstatic void do_replace (struct du_chain *, int); 82185029Spjdstatic void scan_rtx_reg (rtx, rtx *, enum reg_class, 83185029Spjd enum scan_actions, enum op_type, int); 84185029Spjdstatic void scan_rtx_address (rtx, rtx *, enum reg_class, 85185029Spjd enum scan_actions, enum machine_mode); 86185029Spjdstatic void scan_rtx (rtx, rtx *, enum reg_class, enum scan_actions, 87185029Spjd enum op_type, int); 88185029Spjdstatic struct du_chain *build_def_use (basic_block); 89185029Spjdstatic void dump_def_use_chain (struct du_chain *); 90185029Spjdstatic void note_sets (rtx, rtx, void *); 91185029Spjdstatic void clear_dead_regs (HARD_REG_SET *, enum machine_mode, rtx); 92185029Spjdstatic void merge_overlapping_regs (basic_block, HARD_REG_SET *, 93185029Spjd struct du_chain *); 94185029Spjd 95185029Spjd/* Called through note_stores from update_life. Find sets of registers, and 96185029Spjd record them in *DATA (which is actually a HARD_REG_SET *). */ 97185029Spjd 98185029Spjdstatic void 99185029Spjdnote_sets (rtx x, rtx set ATTRIBUTE_UNUSED, void *data) 100185029Spjd{ 101185029Spjd HARD_REG_SET *pset = (HARD_REG_SET *) data; 102185029Spjd unsigned int regno; 103185029Spjd int nregs; 104185029Spjd 105185029Spjd if (GET_CODE (x) == SUBREG) 106185029Spjd x = SUBREG_REG (x); 107185029Spjd if (GET_CODE (x) != REG) 108185029Spjd return; 109185029Spjd 110185029Spjd regno = REGNO (x); 111185029Spjd nregs = HARD_REGNO_NREGS (regno, GET_MODE (x)); 112185029Spjd 113185029Spjd /* There must not be pseudos at this point. */ 114185029Spjd if (regno + nregs > FIRST_PSEUDO_REGISTER) 115185029Spjd abort (); 116185029Spjd 117185029Spjd while (nregs-- > 0) 118185029Spjd SET_HARD_REG_BIT (*pset, regno + nregs); 119185029Spjd} 120185029Spjd 121185029Spjd/* Clear all registers from *PSET for which a note of kind KIND can be found 122185029Spjd in the list NOTES. */ 123185029Spjd 124185029Spjdstatic void 125185029Spjdclear_dead_regs (HARD_REG_SET *pset, enum machine_mode kind, rtx notes) 126185029Spjd{ 127185029Spjd rtx note; 128185029Spjd for (note = notes; note; note = XEXP (note, 1)) 129185029Spjd if (REG_NOTE_KIND (note) == kind && REG_P (XEXP (note, 0))) 130185029Spjd { 131185029Spjd rtx reg = XEXP (note, 0); 132185029Spjd unsigned int regno = REGNO (reg); 133185029Spjd int nregs = HARD_REGNO_NREGS (regno, GET_MODE (reg)); 134185029Spjd 135185029Spjd /* There must not be pseudos at this point. */ 136185029Spjd if (regno + nregs > FIRST_PSEUDO_REGISTER) 137185029Spjd abort (); 138185029Spjd 139185029Spjd while (nregs-- > 0) 140185029Spjd CLEAR_HARD_REG_BIT (*pset, regno + nregs); 141185029Spjd } 142185029Spjd} 143185029Spjd 144185029Spjd/* For a def-use chain CHAIN in basic block B, find which registers overlap 145185029Spjd its lifetime and set the corresponding bits in *PSET. */ 146185029Spjd 147185029Spjdstatic void 148185029Spjdmerge_overlapping_regs (basic_block b, HARD_REG_SET *pset, 149185029Spjd struct du_chain *chain) 150185029Spjd{ 151185029Spjd struct du_chain *t = chain; 152185029Spjd rtx insn; 153185029Spjd HARD_REG_SET live; 154185029Spjd 155185029Spjd REG_SET_TO_HARD_REG_SET (live, b->global_live_at_start); 156185029Spjd insn = BB_HEAD (b); 157185029Spjd while (t) 158185029Spjd { 159185029Spjd /* Search forward until the next reference to the register to be 160185029Spjd renamed. */ 161185029Spjd while (insn != t->insn) 162185029Spjd { 163185029Spjd if (INSN_P (insn)) 164185029Spjd { 165185029Spjd clear_dead_regs (&live, REG_DEAD, REG_NOTES (insn)); 166185029Spjd note_stores (PATTERN (insn), note_sets, (void *) &live); 167185029Spjd /* Only record currently live regs if we are inside the 168185029Spjd reg's live range. */ 169185029Spjd if (t != chain) 170185029Spjd IOR_HARD_REG_SET (*pset, live); 171185029Spjd clear_dead_regs (&live, REG_UNUSED, REG_NOTES (insn)); 172185029Spjd } 173185029Spjd insn = NEXT_INSN (insn); 174185029Spjd } 175185029Spjd 176185029Spjd IOR_HARD_REG_SET (*pset, live); 177185029Spjd 178185029Spjd /* For the last reference, also merge in all registers set in the 179185029Spjd same insn. 180185029Spjd @@@ We only have take earlyclobbered sets into account. */ 181185029Spjd if (! t->next_use) 182185029Spjd note_stores (PATTERN (insn), note_sets, (void *) pset); 183185029Spjd 184185029Spjd t = t->next_use; 185185029Spjd } 186185029Spjd} 187185029Spjd 188185029Spjd/* Perform register renaming on the current function. */ 189185029Spjd 190185029Spjdvoid 191185029Spjdregrename_optimize (void) 192185029Spjd{ 193185029Spjd int tick[FIRST_PSEUDO_REGISTER]; 194185029Spjd int this_tick = 0; 195185029Spjd basic_block bb; 196185029Spjd char *first_obj; 197185029Spjd 198185029Spjd memset (tick, 0, sizeof tick); 199185029Spjd 200185029Spjd gcc_obstack_init (&rename_obstack); 201185029Spjd first_obj = obstack_alloc (&rename_obstack, 0); 202185029Spjd 203185029Spjd FOR_EACH_BB (bb) 204185029Spjd { 205185029Spjd struct du_chain *all_chains = 0; 206185029Spjd HARD_REG_SET unavailable; 207185029Spjd HARD_REG_SET regs_seen; 208185029Spjd 209 CLEAR_HARD_REG_SET (unavailable); 210 211 if (rtl_dump_file) 212 fprintf (rtl_dump_file, "\nBasic block %d:\n", bb->index); 213 214 all_chains = build_def_use (bb); 215 216 if (rtl_dump_file) 217 dump_def_use_chain (all_chains); 218 219 CLEAR_HARD_REG_SET (unavailable); 220 /* Don't clobber traceback for noreturn functions. */ 221 if (frame_pointer_needed) 222 { 223 int i; 224 225 for (i = HARD_REGNO_NREGS (FRAME_POINTER_REGNUM, Pmode); i--;) 226 SET_HARD_REG_BIT (unavailable, FRAME_POINTER_REGNUM + i); 227 228#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM 229 for (i = HARD_REGNO_NREGS (HARD_FRAME_POINTER_REGNUM, Pmode); i--;) 230 SET_HARD_REG_BIT (unavailable, HARD_FRAME_POINTER_REGNUM + i); 231#endif 232 } 233 234 CLEAR_HARD_REG_SET (regs_seen); 235 while (all_chains) 236 { 237 int new_reg, best_new_reg; 238 int n_uses; 239 struct du_chain *this = all_chains; 240 struct du_chain *tmp, *last; 241 HARD_REG_SET this_unavailable; 242 int reg = REGNO (*this->loc); 243 int i; 244 245 all_chains = this->next_chain; 246 247 best_new_reg = reg; 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 (tick[best_new_reg] > tick[new_reg]) 330 best_new_reg = new_reg; 331 } 332 } 333 334 if (rtl_dump_file) 335 { 336 fprintf (rtl_dump_file, "Register %s in insn %d", 337 reg_names[reg], INSN_UID (last->insn)); 338 if (last->need_caller_save_reg) 339 fprintf (rtl_dump_file, " crosses a call"); 340 } 341 342 if (best_new_reg == reg) 343 { 344 tick[reg] = ++this_tick; 345 if (rtl_dump_file) 346 fprintf (rtl_dump_file, "; no available better choice\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 (struct du_chain *chain, int reg) 372{ 373 while (chain) 374 { 375 unsigned int regno = ORIGINAL_REGNO (*chain->loc); 376 struct reg_attrs * attr = REG_ATTRS (*chain->loc); 377 378 *chain->loc = gen_raw_REG (GET_MODE (*chain->loc), reg); 379 if (regno >= FIRST_PSEUDO_REGISTER) 380 ORIGINAL_REGNO (*chain->loc) = regno; 381 REG_ATTRS (*chain->loc) = attr; 382 chain = chain->next_use; 383 } 384} 385 386 387static struct du_chain *open_chains; 388static struct du_chain *closed_chains; 389 390static void 391scan_rtx_reg (rtx insn, rtx *loc, enum reg_class class, 392 enum scan_actions action, enum op_type type, int earlyclobber) 393{ 394 struct du_chain **p; 395 rtx x = *loc; 396 enum machine_mode mode = GET_MODE (x); 397 int this_regno = REGNO (x); 398 int this_nregs = HARD_REGNO_NREGS (this_regno, mode); 399 400 if (action == mark_write) 401 { 402 if (type == OP_OUT) 403 { 404 struct du_chain *this 405 = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 406 this->next_use = 0; 407 this->next_chain = open_chains; 408 this->loc = loc; 409 this->insn = insn; 410 this->class = class; 411 this->need_caller_save_reg = 0; 412 this->earlyclobber = earlyclobber; 413 open_chains = this; 414 } 415 return; 416 } 417 418 if ((type == OP_OUT && action != terminate_write) 419 || (type != OP_OUT && action == terminate_write)) 420 return; 421 422 for (p = &open_chains; *p;) 423 { 424 struct du_chain *this = *p; 425 426 /* Check if the chain has been terminated if it has then skip to 427 the next chain. 428 429 This can happen when we've already appended the location to 430 the chain in Step 3, but are trying to hide in-out operands 431 from terminate_write in Step 5. */ 432 433 if (*this->loc == cc0_rtx) 434 p = &this->next_chain; 435 else 436 { 437 int regno = REGNO (*this->loc); 438 int nregs = HARD_REGNO_NREGS (regno, GET_MODE (*this->loc)); 439 int exact_match = (regno == this_regno && nregs == this_nregs); 440 441 if (regno + nregs <= this_regno 442 || this_regno + this_nregs <= regno) 443 { 444 p = &this->next_chain; 445 continue; 446 } 447 448 if (action == mark_read) 449 { 450 if (! exact_match) 451 abort (); 452 453 /* ??? Class NO_REGS can happen if the md file makes use of 454 EXTRA_CONSTRAINTS to match registers. Which is arguably 455 wrong, but there we are. Since we know not what this may 456 be replaced with, terminate the chain. */ 457 if (class != NO_REGS) 458 { 459 this = obstack_alloc (&rename_obstack, sizeof (struct du_chain)); 460 this->next_use = 0; 461 this->next_chain = (*p)->next_chain; 462 this->loc = loc; 463 this->insn = insn; 464 this->class = class; 465 this->need_caller_save_reg = 0; 466 while (*p) 467 p = &(*p)->next_use; 468 *p = this; 469 return; 470 } 471 } 472 473 if (action != terminate_overlapping_read || ! exact_match) 474 { 475 struct du_chain *next = this->next_chain; 476 477 /* Whether the terminated chain can be used for renaming 478 depends on the action and this being an exact match. 479 In either case, we remove this element from open_chains. */ 480 481 if ((action == terminate_dead || action == terminate_write) 482 && exact_match) 483 { 484 this->next_chain = closed_chains; 485 closed_chains = this; 486 if (rtl_dump_file) 487 fprintf (rtl_dump_file, 488 "Closing chain %s at insn %d (%s)\n", 489 reg_names[REGNO (*this->loc)], INSN_UID (insn), 490 scan_actions_name[(int) action]); 491 } 492 else 493 { 494 if (rtl_dump_file) 495 fprintf (rtl_dump_file, 496 "Discarding chain %s at insn %d (%s)\n", 497 reg_names[REGNO (*this->loc)], INSN_UID (insn), 498 scan_actions_name[(int) action]); 499 } 500 *p = next; 501 } 502 else 503 p = &this->next_chain; 504 } 505 } 506} 507 508/* Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 509 BASE_REG_CLASS depending on how the register is being considered. */ 510 511static void 512scan_rtx_address (rtx insn, rtx *loc, enum reg_class class, 513 enum scan_actions action, enum machine_mode mode) 514{ 515 rtx x = *loc; 516 RTX_CODE code = GET_CODE (x); 517 const char *fmt; 518 int i, j; 519 520 if (action == mark_write) 521 return; 522 523 switch (code) 524 { 525 case PLUS: 526 { 527 rtx orig_op0 = XEXP (x, 0); 528 rtx orig_op1 = XEXP (x, 1); 529 RTX_CODE code0 = GET_CODE (orig_op0); 530 RTX_CODE code1 = GET_CODE (orig_op1); 531 rtx op0 = orig_op0; 532 rtx op1 = orig_op1; 533 rtx *locI = NULL; 534 rtx *locB = NULL; 535 536 if (GET_CODE (op0) == SUBREG) 537 { 538 op0 = SUBREG_REG (op0); 539 code0 = GET_CODE (op0); 540 } 541 542 if (GET_CODE (op1) == SUBREG) 543 { 544 op1 = SUBREG_REG (op1); 545 code1 = GET_CODE (op1); 546 } 547 548 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 549 || code0 == ZERO_EXTEND || code1 == MEM) 550 { 551 locI = &XEXP (x, 0); 552 locB = &XEXP (x, 1); 553 } 554 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 555 || code1 == ZERO_EXTEND || code0 == MEM) 556 { 557 locI = &XEXP (x, 1); 558 locB = &XEXP (x, 0); 559 } 560 else if (code0 == CONST_INT || code0 == CONST 561 || code0 == SYMBOL_REF || code0 == LABEL_REF) 562 locB = &XEXP (x, 1); 563 else if (code1 == CONST_INT || code1 == CONST 564 || code1 == SYMBOL_REF || code1 == LABEL_REF) 565 locB = &XEXP (x, 0); 566 else if (code0 == REG && code1 == REG) 567 { 568 int index_op; 569 570 if (REG_OK_FOR_INDEX_P (op0) 571 && REG_MODE_OK_FOR_BASE_P (op1, mode)) 572 index_op = 0; 573 else if (REG_OK_FOR_INDEX_P (op1) 574 && REG_MODE_OK_FOR_BASE_P (op0, mode)) 575 index_op = 1; 576 else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 577 index_op = 0; 578 else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 579 index_op = 1; 580 else if (REG_OK_FOR_INDEX_P (op1)) 581 index_op = 1; 582 else 583 index_op = 0; 584 585 locI = &XEXP (x, index_op); 586 locB = &XEXP (x, !index_op); 587 } 588 else if (code0 == REG) 589 { 590 locI = &XEXP (x, 0); 591 locB = &XEXP (x, 1); 592 } 593 else if (code1 == REG) 594 { 595 locI = &XEXP (x, 1); 596 locB = &XEXP (x, 0); 597 } 598 599 if (locI) 600 scan_rtx_address (insn, locI, INDEX_REG_CLASS, action, mode); 601 if (locB) 602 scan_rtx_address (insn, locB, MODE_BASE_REG_CLASS (mode), action, mode); 603 return; 604 } 605 606 case POST_INC: 607 case POST_DEC: 608 case POST_MODIFY: 609 case PRE_INC: 610 case PRE_DEC: 611 case PRE_MODIFY: 612#ifndef AUTO_INC_DEC 613 /* If the target doesn't claim to handle autoinc, this must be 614 something special, like a stack push. Kill this chain. */ 615 action = terminate_all_read; 616#endif 617 break; 618 619 case MEM: 620 scan_rtx_address (insn, &XEXP (x, 0), 621 MODE_BASE_REG_CLASS (GET_MODE (x)), action, 622 GET_MODE (x)); 623 return; 624 625 case REG: 626 scan_rtx_reg (insn, loc, class, action, OP_IN, 0); 627 return; 628 629 default: 630 break; 631 } 632 633 fmt = GET_RTX_FORMAT (code); 634 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 635 { 636 if (fmt[i] == 'e') 637 scan_rtx_address (insn, &XEXP (x, i), class, action, mode); 638 else if (fmt[i] == 'E') 639 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 640 scan_rtx_address (insn, &XVECEXP (x, i, j), class, action, mode); 641 } 642} 643 644static void 645scan_rtx (rtx insn, rtx *loc, enum reg_class class, 646 enum scan_actions action, enum op_type type, int earlyclobber) 647{ 648 const char *fmt; 649 rtx x = *loc; 650 enum rtx_code code = GET_CODE (x); 651 int i, j; 652 653 code = GET_CODE (x); 654 switch (code) 655 { 656 case CONST: 657 case CONST_INT: 658 case CONST_DOUBLE: 659 case CONST_VECTOR: 660 case SYMBOL_REF: 661 case LABEL_REF: 662 case CC0: 663 case PC: 664 return; 665 666 case REG: 667 scan_rtx_reg (insn, loc, class, action, type, earlyclobber); 668 return; 669 670 case MEM: 671 scan_rtx_address (insn, &XEXP (x, 0), 672 MODE_BASE_REG_CLASS (GET_MODE (x)), action, 673 GET_MODE (x)); 674 return; 675 676 case SET: 677 scan_rtx (insn, &SET_SRC (x), class, action, OP_IN, 0); 678 scan_rtx (insn, &SET_DEST (x), class, action, 679 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 0); 680 return; 681 682 case STRICT_LOW_PART: 683 scan_rtx (insn, &XEXP (x, 0), class, action, OP_INOUT, earlyclobber); 684 return; 685 686 case ZERO_EXTRACT: 687 case SIGN_EXTRACT: 688 scan_rtx (insn, &XEXP (x, 0), class, action, 689 type == OP_IN ? OP_IN : OP_INOUT, earlyclobber); 690 scan_rtx (insn, &XEXP (x, 1), class, action, OP_IN, 0); 691 scan_rtx (insn, &XEXP (x, 2), class, action, OP_IN, 0); 692 return; 693 694 case POST_INC: 695 case PRE_INC: 696 case POST_DEC: 697 case PRE_DEC: 698 case POST_MODIFY: 699 case PRE_MODIFY: 700 /* Should only happen inside MEM. */ 701 abort (); 702 703 case CLOBBER: 704 scan_rtx (insn, &SET_DEST (x), class, action, 705 GET_CODE (PATTERN (insn)) == COND_EXEC ? OP_INOUT : OP_OUT, 1); 706 return; 707 708 case EXPR_LIST: 709 scan_rtx (insn, &XEXP (x, 0), class, action, type, 0); 710 if (XEXP (x, 1)) 711 scan_rtx (insn, &XEXP (x, 1), class, action, type, 0); 712 return; 713 714 default: 715 break; 716 } 717 718 fmt = GET_RTX_FORMAT (code); 719 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 720 { 721 if (fmt[i] == 'e') 722 scan_rtx (insn, &XEXP (x, i), class, action, type, 0); 723 else if (fmt[i] == 'E') 724 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 725 scan_rtx (insn, &XVECEXP (x, i, j), class, action, type, 0); 726 } 727} 728 729/* Build def/use chain. */ 730 731static struct du_chain * 732build_def_use (basic_block bb) 733{ 734 rtx insn; 735 736 open_chains = closed_chains = NULL; 737 738 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 739 { 740 if (INSN_P (insn)) 741 { 742 int n_ops; 743 rtx note; 744 rtx old_operands[MAX_RECOG_OPERANDS]; 745 rtx old_dups[MAX_DUP_OPERANDS]; 746 int i, icode; 747 int alt; 748 int predicated; 749 750 /* Process the insn, determining its effect on the def-use 751 chains. We perform the following steps with the register 752 references in the insn: 753 (1) Any read that overlaps an open chain, but doesn't exactly 754 match, causes that chain to be closed. We can't deal 755 with overlaps yet. 756 (2) Any read outside an operand causes any chain it overlaps 757 with to be closed, since we can't replace it. 758 (3) Any read inside an operand is added if there's already 759 an open chain for it. 760 (4) For any REG_DEAD note we find, close open chains that 761 overlap it. 762 (5) For any write we find, close open chains that overlap it. 763 (6) For any write we find in an operand, make a new chain. 764 (7) For any REG_UNUSED, close any chains we just opened. */ 765 766 icode = recog_memoized (insn); 767 extract_insn (insn); 768 if (! constrain_operands (1)) 769 fatal_insn_not_found (insn); 770 preprocess_constraints (); 771 alt = which_alternative; 772 n_ops = recog_data.n_operands; 773 774 /* Simplify the code below by rewriting things to reflect 775 matching constraints. Also promote OP_OUT to OP_INOUT 776 in predicated instructions. */ 777 778 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 779 for (i = 0; i < n_ops; ++i) 780 { 781 int matches = recog_op_alt[i][alt].matches; 782 if (matches >= 0) 783 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; 784 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 785 || (predicated && recog_data.operand_type[i] == OP_OUT)) 786 recog_data.operand_type[i] = OP_INOUT; 787 } 788 789 /* Step 1: Close chains for which we have overlapping reads. */ 790 for (i = 0; i < n_ops; i++) 791 scan_rtx (insn, recog_data.operand_loc[i], 792 NO_REGS, terminate_overlapping_read, 793 recog_data.operand_type[i], 0); 794 795 /* Step 2: Close chains for which we have reads outside operands. 796 We do this by munging all operands into CC0, and closing 797 everything remaining. */ 798 799 for (i = 0; i < n_ops; i++) 800 { 801 old_operands[i] = recog_data.operand[i]; 802 /* Don't squash match_operator or match_parallel here, since 803 we don't know that all of the contained registers are 804 reachable by proper operands. */ 805 if (recog_data.constraints[i][0] == '\0') 806 continue; 807 *recog_data.operand_loc[i] = cc0_rtx; 808 } 809 for (i = 0; i < recog_data.n_dups; i++) 810 { 811 int dup_num = recog_data.dup_num[i]; 812 813 old_dups[i] = *recog_data.dup_loc[i]; 814 *recog_data.dup_loc[i] = cc0_rtx; 815 816 /* For match_dup of match_operator or match_parallel, share 817 them, so that we don't miss changes in the dup. */ 818 if (icode >= 0 819 && insn_data[icode].operand[dup_num].eliminable == 0) 820 old_dups[i] = recog_data.operand[dup_num]; 821 } 822 823 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_all_read, 824 OP_IN, 0); 825 826 for (i = 0; i < recog_data.n_dups; i++) 827 *recog_data.dup_loc[i] = old_dups[i]; 828 for (i = 0; i < n_ops; i++) 829 *recog_data.operand_loc[i] = old_operands[i]; 830 831 /* Step 2B: Can't rename function call argument registers. */ 832 if (GET_CODE (insn) == CALL_INSN && CALL_INSN_FUNCTION_USAGE (insn)) 833 scan_rtx (insn, &CALL_INSN_FUNCTION_USAGE (insn), 834 NO_REGS, terminate_all_read, OP_IN, 0); 835 836 /* Step 2C: Can't rename asm operands that were originally 837 hard registers. */ 838 if (asm_noperands (PATTERN (insn)) > 0) 839 for (i = 0; i < n_ops; i++) 840 { 841 rtx *loc = recog_data.operand_loc[i]; 842 rtx op = *loc; 843 844 if (GET_CODE (op) == REG 845 && REGNO (op) == ORIGINAL_REGNO (op) 846 && (recog_data.operand_type[i] == OP_IN 847 || recog_data.operand_type[i] == OP_INOUT)) 848 scan_rtx (insn, loc, NO_REGS, terminate_all_read, OP_IN, 0); 849 } 850 851 /* Step 3: Append to chains for reads inside operands. */ 852 for (i = 0; i < n_ops + recog_data.n_dups; i++) 853 { 854 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 855 rtx *loc = (i < n_ops 856 ? recog_data.operand_loc[opn] 857 : recog_data.dup_loc[i - n_ops]); 858 enum reg_class class = recog_op_alt[opn][alt].class; 859 enum op_type type = recog_data.operand_type[opn]; 860 861 /* Don't scan match_operand here, since we've no reg class 862 information to pass down. Any operands that we could 863 substitute in will be represented elsewhere. */ 864 if (recog_data.constraints[opn][0] == '\0') 865 continue; 866 867 if (recog_op_alt[opn][alt].is_address) 868 scan_rtx_address (insn, loc, class, mark_read, VOIDmode); 869 else 870 scan_rtx (insn, loc, class, mark_read, type, 0); 871 } 872 873 /* Step 4: Close chains for registers that die here. 874 Also record updates for REG_INC notes. */ 875 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 876 { 877 if (REG_NOTE_KIND (note) == REG_DEAD) 878 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 879 OP_IN, 0); 880 else if (REG_NOTE_KIND (note) == REG_INC) 881 scan_rtx (insn, &XEXP (note, 0), ALL_REGS, mark_read, 882 OP_INOUT, 0); 883 } 884 885 /* Step 4B: If this is a call, any chain live at this point 886 requires a caller-saved reg. */ 887 if (GET_CODE (insn) == CALL_INSN) 888 { 889 struct du_chain *p; 890 for (p = open_chains; p; p = p->next_chain) 891 p->need_caller_save_reg = 1; 892 } 893 894 /* Step 5: Close open chains that overlap writes. Similar to 895 step 2, we hide in-out operands, since we do not want to 896 close these chains. */ 897 898 for (i = 0; i < n_ops; i++) 899 { 900 old_operands[i] = recog_data.operand[i]; 901 if (recog_data.operand_type[i] == OP_INOUT) 902 *recog_data.operand_loc[i] = cc0_rtx; 903 } 904 for (i = 0; i < recog_data.n_dups; i++) 905 { 906 int opn = recog_data.dup_num[i]; 907 old_dups[i] = *recog_data.dup_loc[i]; 908 if (recog_data.operand_type[opn] == OP_INOUT) 909 *recog_data.dup_loc[i] = cc0_rtx; 910 } 911 912 scan_rtx (insn, &PATTERN (insn), NO_REGS, terminate_write, OP_IN, 0); 913 914 for (i = 0; i < recog_data.n_dups; i++) 915 *recog_data.dup_loc[i] = old_dups[i]; 916 for (i = 0; i < n_ops; i++) 917 *recog_data.operand_loc[i] = old_operands[i]; 918 919 /* Step 6: Begin new chains for writes inside operands. */ 920 /* ??? Many targets have output constraints on the SET_DEST 921 of a call insn, which is stupid, since these are certainly 922 ABI defined hard registers. Don't change calls at all. 923 Similarly take special care for asm statement that originally 924 referenced hard registers. */ 925 if (asm_noperands (PATTERN (insn)) > 0) 926 { 927 for (i = 0; i < n_ops; i++) 928 if (recog_data.operand_type[i] == OP_OUT) 929 { 930 rtx *loc = recog_data.operand_loc[i]; 931 rtx op = *loc; 932 enum reg_class class = recog_op_alt[i][alt].class; 933 934 if (GET_CODE (op) == REG 935 && REGNO (op) == ORIGINAL_REGNO (op)) 936 continue; 937 938 scan_rtx (insn, loc, class, mark_write, OP_OUT, 939 recog_op_alt[i][alt].earlyclobber); 940 } 941 } 942 else if (GET_CODE (insn) != CALL_INSN) 943 for (i = 0; i < n_ops + recog_data.n_dups; i++) 944 { 945 int opn = i < n_ops ? i : recog_data.dup_num[i - n_ops]; 946 rtx *loc = (i < n_ops 947 ? recog_data.operand_loc[opn] 948 : recog_data.dup_loc[i - n_ops]); 949 enum reg_class class = recog_op_alt[opn][alt].class; 950 951 if (recog_data.operand_type[opn] == OP_OUT) 952 scan_rtx (insn, loc, class, mark_write, OP_OUT, 953 recog_op_alt[opn][alt].earlyclobber); 954 } 955 956 /* Step 7: Close chains for registers that were never 957 really used here. */ 958 for (note = REG_NOTES (insn); note; note = XEXP (note, 1)) 959 if (REG_NOTE_KIND (note) == REG_UNUSED) 960 scan_rtx (insn, &XEXP (note, 0), NO_REGS, terminate_dead, 961 OP_IN, 0); 962 } 963 if (insn == BB_END (bb)) 964 break; 965 } 966 967 /* Since we close every chain when we find a REG_DEAD note, anything that 968 is still open lives past the basic block, so it can't be renamed. */ 969 return closed_chains; 970} 971 972/* Dump all def/use chains in CHAINS to RTL_DUMP_FILE. They are 973 printed in reverse order as that's how we build them. */ 974 975static void 976dump_def_use_chain (struct du_chain *chains) 977{ 978 while (chains) 979 { 980 struct du_chain *this = chains; 981 int r = REGNO (*this->loc); 982 int nregs = HARD_REGNO_NREGS (r, GET_MODE (*this->loc)); 983 fprintf (rtl_dump_file, "Register %s (%d):", reg_names[r], nregs); 984 while (this) 985 { 986 fprintf (rtl_dump_file, " %d [%s]", INSN_UID (this->insn), 987 reg_class_names[this->class]); 988 this = this->next_use; 989 } 990 fprintf (rtl_dump_file, "\n"); 991 chains = chains->next_chain; 992 } 993} 994 995/* The following code does forward propagation of hard register copies. 996 The object is to eliminate as many dependencies as possible, so that 997 we have the most scheduling freedom. As a side effect, we also clean 998 up some silly register allocation decisions made by reload. This 999 code may be obsoleted by a new register allocator. */ 1000 1001/* For each register, we have a list of registers that contain the same 1002 value. The OLDEST_REGNO field points to the head of the list, and 1003 the NEXT_REGNO field runs through the list. The MODE field indicates 1004 what mode the data is known to be in; this field is VOIDmode when the 1005 register is not known to contain valid data. */ 1006 1007struct value_data_entry 1008{ 1009 enum machine_mode mode; 1010 unsigned int oldest_regno; 1011 unsigned int next_regno; 1012}; 1013 1014struct value_data 1015{ 1016 struct value_data_entry e[FIRST_PSEUDO_REGISTER]; 1017 unsigned int max_value_regs; 1018}; 1019 1020static void kill_value_regno (unsigned, struct value_data *); 1021static void kill_value (rtx, struct value_data *); 1022static void set_value_regno (unsigned, enum machine_mode, struct value_data *); 1023static void init_value_data (struct value_data *); 1024static void kill_clobbered_value (rtx, rtx, void *); 1025static void kill_set_value (rtx, rtx, void *); 1026static int kill_autoinc_value (rtx *, void *); 1027static void copy_value (rtx, rtx, struct value_data *); 1028static bool mode_change_ok (enum machine_mode, enum machine_mode, 1029 unsigned int); 1030static rtx maybe_mode_change (enum machine_mode, enum machine_mode, 1031 enum machine_mode, unsigned int, unsigned int); 1032static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *); 1033static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx, 1034 struct value_data *); 1035static bool replace_oldest_value_addr (rtx *, enum reg_class, 1036 enum machine_mode, rtx, 1037 struct value_data *); 1038static bool replace_oldest_value_mem (rtx, rtx, struct value_data *); 1039static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *); 1040extern void debug_value_data (struct value_data *); 1041#ifdef ENABLE_CHECKING 1042static void validate_value_data (struct value_data *); 1043#endif 1044 1045/* Kill register REGNO. This involves removing it from any value lists, 1046 and resetting the value mode to VOIDmode. */ 1047 1048static void 1049kill_value_regno (unsigned int regno, struct value_data *vd) 1050{ 1051 unsigned int i, next; 1052 1053 if (vd->e[regno].oldest_regno != regno) 1054 { 1055 for (i = vd->e[regno].oldest_regno; 1056 vd->e[i].next_regno != regno; 1057 i = vd->e[i].next_regno) 1058 continue; 1059 vd->e[i].next_regno = vd->e[regno].next_regno; 1060 } 1061 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) 1062 { 1063 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) 1064 vd->e[i].oldest_regno = next; 1065 } 1066 1067 vd->e[regno].mode = VOIDmode; 1068 vd->e[regno].oldest_regno = regno; 1069 vd->e[regno].next_regno = INVALID_REGNUM; 1070 1071#ifdef ENABLE_CHECKING 1072 validate_value_data (vd); 1073#endif 1074} 1075 1076/* Kill X. This is a convenience function for kill_value_regno 1077 so that we mind the mode the register is in. */ 1078 1079static void 1080kill_value (rtx x, struct value_data *vd) 1081{ 1082 /* SUBREGS are supposed to have been eliminated by now. But some 1083 ports, e.g. i386 sse, use them to smuggle vector type information 1084 through to instruction selection. Each such SUBREG should simplify, 1085 so if we get a NULL we've done something wrong elsewhere. */ 1086 1087 if (GET_CODE (x) == SUBREG) 1088 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x), 1089 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); 1090 if (REG_P (x)) 1091 { 1092 unsigned int regno = REGNO (x); 1093 unsigned int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); 1094 unsigned int i, j; 1095 1096 /* Kill the value we're told to kill. */ 1097 for (i = 0; i < n; ++i) 1098 kill_value_regno (regno + i, vd); 1099 1100 /* Kill everything that overlapped what we're told to kill. */ 1101 if (regno < vd->max_value_regs) 1102 j = 0; 1103 else 1104 j = regno - vd->max_value_regs; 1105 for (; j < regno; ++j) 1106 { 1107 if (vd->e[j].mode == VOIDmode) 1108 continue; 1109 n = HARD_REGNO_NREGS (j, vd->e[j].mode); 1110 if (j + n > regno) 1111 for (i = 0; i < n; ++i) 1112 kill_value_regno (j + i, vd); 1113 } 1114 } 1115} 1116 1117/* Remember that REGNO is valid in MODE. */ 1118 1119static void 1120set_value_regno (unsigned int regno, enum machine_mode mode, 1121 struct value_data *vd) 1122{ 1123 unsigned int nregs; 1124 1125 vd->e[regno].mode = mode; 1126 1127 nregs = HARD_REGNO_NREGS (regno, mode); 1128 if (nregs > vd->max_value_regs) 1129 vd->max_value_regs = nregs; 1130} 1131 1132/* Initialize VD such that there are no known relationships between regs. */ 1133 1134static void 1135init_value_data (struct value_data *vd) 1136{ 1137 int i; 1138 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1139 { 1140 vd->e[i].mode = VOIDmode; 1141 vd->e[i].oldest_regno = i; 1142 vd->e[i].next_regno = INVALID_REGNUM; 1143 } 1144 vd->max_value_regs = 0; 1145} 1146 1147/* Called through note_stores. If X is clobbered, kill its value. */ 1148 1149static void 1150kill_clobbered_value (rtx x, rtx set, void *data) 1151{ 1152 struct value_data *vd = data; 1153 if (GET_CODE (set) == CLOBBER) 1154 kill_value (x, vd); 1155} 1156 1157/* Called through note_stores. If X is set, not clobbered, kill its 1158 current value and install it as the root of its own value list. */ 1159 1160static void 1161kill_set_value (rtx x, rtx set, void *data) 1162{ 1163 struct value_data *vd = data; 1164 if (GET_CODE (set) != CLOBBER) 1165 { 1166 kill_value (x, vd); 1167 if (REG_P (x)) 1168 set_value_regno (REGNO (x), GET_MODE (x), vd); 1169 } 1170} 1171 1172/* Called through for_each_rtx. Kill any register used as the base of an 1173 auto-increment expression, and install that register as the root of its 1174 own value list. */ 1175 1176static int 1177kill_autoinc_value (rtx *px, void *data) 1178{ 1179 rtx x = *px; 1180 struct value_data *vd = data; 1181 1182 if (GET_RTX_CLASS (GET_CODE (x)) == 'a') 1183 { 1184 x = XEXP (x, 0); 1185 kill_value (x, vd); 1186 set_value_regno (REGNO (x), Pmode, vd); 1187 return -1; 1188 } 1189 1190 return 0; 1191} 1192 1193/* Assert that SRC has been copied to DEST. Adjust the data structures 1194 to reflect that SRC contains an older copy of the shared value. */ 1195 1196static void 1197copy_value (rtx dest, rtx src, struct value_data *vd) 1198{ 1199 unsigned int dr = REGNO (dest); 1200 unsigned int sr = REGNO (src); 1201 unsigned int dn, sn; 1202 unsigned int i; 1203 1204 /* ??? At present, it's possible to see noop sets. It'd be nice if 1205 this were cleaned up beforehand... */ 1206 if (sr == dr) 1207 return; 1208 1209 /* Do not propagate copies to the stack pointer, as that can leave 1210 memory accesses with no scheduling dependency on the stack update. */ 1211 if (dr == STACK_POINTER_REGNUM) 1212 return; 1213 1214 /* Likewise with the frame pointer, if we're using one. */ 1215 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) 1216 return; 1217 1218 /* If SRC and DEST overlap, don't record anything. */ 1219 dn = HARD_REGNO_NREGS (dr, GET_MODE (dest)); 1220 sn = HARD_REGNO_NREGS (sr, GET_MODE (dest)); 1221 if ((dr > sr && dr < sr + sn) 1222 || (sr > dr && sr < dr + dn)) 1223 return; 1224 1225 /* If SRC had no assigned mode (i.e. we didn't know it was live) 1226 assign it now and assume the value came from an input argument 1227 or somesuch. */ 1228 if (vd->e[sr].mode == VOIDmode) 1229 set_value_regno (sr, vd->e[dr].mode, vd); 1230 1231 /* If we are narrowing the input to a smaller number of hard regs, 1232 and it is in big endian, we are really extracting a high part. 1233 Since we generally associate a low part of a value with the value itself, 1234 we must not do the same for the high part. 1235 Note we can still get low parts for the same mode combination through 1236 a two-step copy involving differently sized hard regs. 1237 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each: 1238 (set (reg:DI r0) (reg:DI fr0)) 1239 (set (reg:SI fr2) (reg:SI r0)) 1240 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while: 1241 (set (reg:SI fr2) (reg:SI fr0)) 1242 loads the high part of (reg:DI fr0) into fr2. 1243 1244 We can't properly represent the latter case in our tables, so don't 1245 record anything then. */ 1246 else if (sn < (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode) 1247 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD 1248 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) 1249 return; 1250 1251 /* If SRC had been assigned a mode narrower than the copy, we can't 1252 link DEST into the chain, because not all of the pieces of the 1253 copy came from oldest_regno. */ 1254 else if (sn > (unsigned int) HARD_REGNO_NREGS (sr, vd->e[sr].mode)) 1255 return; 1256 1257 /* Link DR at the end of the value chain used by SR. */ 1258 1259 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; 1260 1261 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) 1262 continue; 1263 vd->e[i].next_regno = dr; 1264 1265#ifdef ENABLE_CHECKING 1266 validate_value_data (vd); 1267#endif 1268} 1269 1270/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ 1271 1272static bool 1273mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode, 1274 unsigned int regno ATTRIBUTE_UNUSED) 1275{ 1276 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) 1277 return false; 1278 1279#ifdef CANNOT_CHANGE_MODE_CLASS 1280 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode); 1281#endif 1282 1283 return true; 1284} 1285 1286/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it - 1287 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed 1288 in NEW_MODE. 1289 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */ 1290 1291static rtx 1292maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode, 1293 enum machine_mode new_mode, unsigned int regno, 1294 unsigned int copy_regno ATTRIBUTE_UNUSED) 1295{ 1296 if (orig_mode == new_mode) 1297 return gen_rtx_raw_REG (new_mode, regno); 1298 else if (mode_change_ok (orig_mode, new_mode, regno)) 1299 { 1300 int copy_nregs = HARD_REGNO_NREGS (copy_regno, copy_mode); 1301 int use_nregs = HARD_REGNO_NREGS (copy_regno, new_mode); 1302 int copy_offset 1303 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs); 1304 int offset 1305 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset; 1306 int byteoffset = offset % UNITS_PER_WORD; 1307 int wordoffset = offset - byteoffset; 1308 1309 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0) 1310 + (BYTES_BIG_ENDIAN ? byteoffset : 0)); 1311 return gen_rtx_raw_REG (new_mode, 1312 regno + subreg_regno_offset (regno, orig_mode, 1313 offset, 1314 new_mode)); 1315 } 1316 return NULL_RTX; 1317} 1318 1319/* Find the oldest copy of the value contained in REGNO that is in 1320 register class CLASS and has mode MODE. If found, return an rtx 1321 of that oldest register, otherwise return NULL. */ 1322 1323static rtx 1324find_oldest_value_reg (enum reg_class class, rtx reg, struct value_data *vd) 1325{ 1326 unsigned int regno = REGNO (reg); 1327 enum machine_mode mode = GET_MODE (reg); 1328 unsigned int i; 1329 1330 /* If we are accessing REG in some mode other that what we set it in, 1331 make sure that the replacement is valid. In particular, consider 1332 (set (reg:DI r11) (...)) 1333 (set (reg:SI r9) (reg:SI r11)) 1334 (set (reg:SI r10) (...)) 1335 (set (...) (reg:DI r9)) 1336 Replacing r9 with r11 is invalid. */ 1337 if (mode != vd->e[regno].mode) 1338 { 1339 if (HARD_REGNO_NREGS (regno, mode) 1340 > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 1341 return NULL_RTX; 1342 } 1343 1344 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) 1345 { 1346 enum machine_mode oldmode = vd->e[i].mode; 1347 rtx new; 1348 unsigned int last; 1349 1350 for (last = i; last < i + HARD_REGNO_NREGS (i, mode); last++) 1351 if (!TEST_HARD_REG_BIT (reg_class_contents[class], last)) 1352 return NULL_RTX; 1353 1354 new = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno); 1355 if (new) 1356 { 1357 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (reg); 1358 REG_ATTRS (new) = REG_ATTRS (reg); 1359 return new; 1360 } 1361 } 1362 1363 return NULL_RTX; 1364} 1365 1366/* If possible, replace the register at *LOC with the oldest register 1367 in register class CLASS. Return true if successfully replaced. */ 1368 1369static bool 1370replace_oldest_value_reg (rtx *loc, enum reg_class class, rtx insn, 1371 struct value_data *vd) 1372{ 1373 rtx new = find_oldest_value_reg (class, *loc, vd); 1374 if (new) 1375 { 1376 if (rtl_dump_file) 1377 fprintf (rtl_dump_file, "insn %u: replaced reg %u with %u\n", 1378 INSN_UID (insn), REGNO (*loc), REGNO (new)); 1379 1380 *loc = new; 1381 return true; 1382 } 1383 return false; 1384} 1385 1386/* Similar to replace_oldest_value_reg, but *LOC contains an address. 1387 Adapted from find_reloads_address_1. CLASS is INDEX_REG_CLASS or 1388 BASE_REG_CLASS depending on how the register is being considered. */ 1389 1390static bool 1391replace_oldest_value_addr (rtx *loc, enum reg_class class, 1392 enum machine_mode mode, rtx insn, 1393 struct value_data *vd) 1394{ 1395 rtx x = *loc; 1396 RTX_CODE code = GET_CODE (x); 1397 const char *fmt; 1398 int i, j; 1399 bool changed = false; 1400 1401 switch (code) 1402 { 1403 case PLUS: 1404 { 1405 rtx orig_op0 = XEXP (x, 0); 1406 rtx orig_op1 = XEXP (x, 1); 1407 RTX_CODE code0 = GET_CODE (orig_op0); 1408 RTX_CODE code1 = GET_CODE (orig_op1); 1409 rtx op0 = orig_op0; 1410 rtx op1 = orig_op1; 1411 rtx *locI = NULL; 1412 rtx *locB = NULL; 1413 1414 if (GET_CODE (op0) == SUBREG) 1415 { 1416 op0 = SUBREG_REG (op0); 1417 code0 = GET_CODE (op0); 1418 } 1419 1420 if (GET_CODE (op1) == SUBREG) 1421 { 1422 op1 = SUBREG_REG (op1); 1423 code1 = GET_CODE (op1); 1424 } 1425 1426 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 1427 || code0 == ZERO_EXTEND || code1 == MEM) 1428 { 1429 locI = &XEXP (x, 0); 1430 locB = &XEXP (x, 1); 1431 } 1432 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 1433 || code1 == ZERO_EXTEND || code0 == MEM) 1434 { 1435 locI = &XEXP (x, 1); 1436 locB = &XEXP (x, 0); 1437 } 1438 else if (code0 == CONST_INT || code0 == CONST 1439 || code0 == SYMBOL_REF || code0 == LABEL_REF) 1440 locB = &XEXP (x, 1); 1441 else if (code1 == CONST_INT || code1 == CONST 1442 || code1 == SYMBOL_REF || code1 == LABEL_REF) 1443 locB = &XEXP (x, 0); 1444 else if (code0 == REG && code1 == REG) 1445 { 1446 int index_op; 1447 1448 if (REG_OK_FOR_INDEX_P (op0) 1449 && REG_MODE_OK_FOR_BASE_P (op1, mode)) 1450 index_op = 0; 1451 else if (REG_OK_FOR_INDEX_P (op1) 1452 && REG_MODE_OK_FOR_BASE_P (op0, mode)) 1453 index_op = 1; 1454 else if (REG_MODE_OK_FOR_BASE_P (op1, mode)) 1455 index_op = 0; 1456 else if (REG_MODE_OK_FOR_BASE_P (op0, mode)) 1457 index_op = 1; 1458 else if (REG_OK_FOR_INDEX_P (op1)) 1459 index_op = 1; 1460 else 1461 index_op = 0; 1462 1463 locI = &XEXP (x, index_op); 1464 locB = &XEXP (x, !index_op); 1465 } 1466 else if (code0 == REG) 1467 { 1468 locI = &XEXP (x, 0); 1469 locB = &XEXP (x, 1); 1470 } 1471 else if (code1 == REG) 1472 { 1473 locI = &XEXP (x, 1); 1474 locB = &XEXP (x, 0); 1475 } 1476 1477 if (locI) 1478 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, mode, 1479 insn, vd); 1480 if (locB) 1481 changed |= replace_oldest_value_addr (locB, 1482 MODE_BASE_REG_CLASS (mode), 1483 mode, insn, vd); 1484 return changed; 1485 } 1486 1487 case POST_INC: 1488 case POST_DEC: 1489 case POST_MODIFY: 1490 case PRE_INC: 1491 case PRE_DEC: 1492 case PRE_MODIFY: 1493 return false; 1494 1495 case MEM: 1496 return replace_oldest_value_mem (x, insn, vd); 1497 1498 case REG: 1499 return replace_oldest_value_reg (loc, class, insn, vd); 1500 1501 default: 1502 break; 1503 } 1504 1505 fmt = GET_RTX_FORMAT (code); 1506 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1507 { 1508 if (fmt[i] == 'e') 1509 changed |= replace_oldest_value_addr (&XEXP (x, i), class, mode, 1510 insn, vd); 1511 else if (fmt[i] == 'E') 1512 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 1513 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), class, 1514 mode, insn, vd); 1515 } 1516 1517 return changed; 1518} 1519 1520/* Similar to replace_oldest_value_reg, but X contains a memory. */ 1521 1522static bool 1523replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd) 1524{ 1525 return replace_oldest_value_addr (&XEXP (x, 0), 1526 MODE_BASE_REG_CLASS (GET_MODE (x)), 1527 GET_MODE (x), insn, vd); 1528} 1529 1530/* Perform the forward copy propagation on basic block BB. */ 1531 1532static bool 1533copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd) 1534{ 1535 bool changed = false; 1536 rtx insn; 1537 1538 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 1539 { 1540 int n_ops, i, alt, predicated; 1541 bool is_asm; 1542 rtx set; 1543 1544 if (! INSN_P (insn)) 1545 { 1546 if (insn == BB_END (bb)) 1547 break; 1548 else 1549 continue; 1550 } 1551 1552 set = single_set (insn); 1553 extract_insn (insn); 1554 if (! constrain_operands (1)) 1555 fatal_insn_not_found (insn); 1556 preprocess_constraints (); 1557 alt = which_alternative; 1558 n_ops = recog_data.n_operands; 1559 is_asm = asm_noperands (PATTERN (insn)) >= 0; 1560 1561 /* Simplify the code below by rewriting things to reflect 1562 matching constraints. Also promote OP_OUT to OP_INOUT 1563 in predicated instructions. */ 1564 1565 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 1566 for (i = 0; i < n_ops; ++i) 1567 { 1568 int matches = recog_op_alt[i][alt].matches; 1569 if (matches >= 0) 1570 recog_op_alt[i][alt].class = recog_op_alt[matches][alt].class; 1571 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 1572 || (predicated && recog_data.operand_type[i] == OP_OUT)) 1573 recog_data.operand_type[i] = OP_INOUT; 1574 } 1575 1576 /* For each earlyclobber operand, zap the value data. */ 1577 for (i = 0; i < n_ops; i++) 1578 if (recog_op_alt[i][alt].earlyclobber) 1579 kill_value (recog_data.operand[i], vd); 1580 1581 /* Within asms, a clobber cannot overlap inputs or outputs. 1582 I wouldn't think this were true for regular insns, but 1583 scan_rtx treats them like that... */ 1584 note_stores (PATTERN (insn), kill_clobbered_value, vd); 1585 1586 /* Kill all auto-incremented values. */ 1587 /* ??? REG_INC is useless, since stack pushes aren't done that way. */ 1588 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); 1589 1590 /* Kill all early-clobbered operands. */ 1591 for (i = 0; i < n_ops; i++) 1592 if (recog_op_alt[i][alt].earlyclobber) 1593 kill_value (recog_data.operand[i], vd); 1594 1595 /* Special-case plain move instructions, since we may well 1596 be able to do the move from a different register class. */ 1597 if (set && REG_P (SET_SRC (set))) 1598 { 1599 rtx src = SET_SRC (set); 1600 unsigned int regno = REGNO (src); 1601 enum machine_mode mode = GET_MODE (src); 1602 unsigned int i; 1603 rtx new; 1604 1605 /* If we are accessing SRC in some mode other that what we 1606 set it in, make sure that the replacement is valid. */ 1607 if (mode != vd->e[regno].mode) 1608 { 1609 if (HARD_REGNO_NREGS (regno, mode) 1610 > HARD_REGNO_NREGS (regno, vd->e[regno].mode)) 1611 goto no_move_special_case; 1612 } 1613 1614 /* If the destination is also a register, try to find a source 1615 register in the same class. */ 1616 if (REG_P (SET_DEST (set))) 1617 { 1618 new = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); 1619 if (new && validate_change (insn, &SET_SRC (set), new, 0)) 1620 { 1621 if (rtl_dump_file) 1622 fprintf (rtl_dump_file, 1623 "insn %u: replaced reg %u with %u\n", 1624 INSN_UID (insn), regno, REGNO (new)); 1625 changed = true; 1626 goto did_replacement; 1627 } 1628 } 1629 1630 /* Otherwise, try all valid registers and see if its valid. */ 1631 for (i = vd->e[regno].oldest_regno; i != regno; 1632 i = vd->e[i].next_regno) 1633 { 1634 new = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode, 1635 mode, i, regno); 1636 if (new != NULL_RTX) 1637 { 1638 if (validate_change (insn, &SET_SRC (set), new, 0)) 1639 { 1640 ORIGINAL_REGNO (new) = ORIGINAL_REGNO (src); 1641 REG_ATTRS (new) = REG_ATTRS (src); 1642 if (rtl_dump_file) 1643 fprintf (rtl_dump_file, 1644 "insn %u: replaced reg %u with %u\n", 1645 INSN_UID (insn), regno, REGNO (new)); 1646 changed = true; 1647 goto did_replacement; 1648 } 1649 } 1650 } 1651 } 1652 no_move_special_case: 1653 1654 /* For each input operand, replace a hard register with the 1655 eldest live copy that's in an appropriate register class. */ 1656 for (i = 0; i < n_ops; i++) 1657 { 1658 bool replaced = false; 1659 1660 /* Don't scan match_operand here, since we've no reg class 1661 information to pass down. Any operands that we could 1662 substitute in will be represented elsewhere. */ 1663 if (recog_data.constraints[i][0] == '\0') 1664 continue; 1665 1666 /* Don't replace in asms intentionally referencing hard regs. */ 1667 if (is_asm && GET_CODE (recog_data.operand[i]) == REG 1668 && (REGNO (recog_data.operand[i]) 1669 == ORIGINAL_REGNO (recog_data.operand[i]))) 1670 continue; 1671 1672 if (recog_data.operand_type[i] == OP_IN) 1673 { 1674 if (recog_op_alt[i][alt].is_address) 1675 replaced 1676 = replace_oldest_value_addr (recog_data.operand_loc[i], 1677 recog_op_alt[i][alt].class, 1678 VOIDmode, insn, vd); 1679 else if (REG_P (recog_data.operand[i])) 1680 replaced 1681 = replace_oldest_value_reg (recog_data.operand_loc[i], 1682 recog_op_alt[i][alt].class, 1683 insn, vd); 1684 else if (GET_CODE (recog_data.operand[i]) == MEM) 1685 replaced = replace_oldest_value_mem (recog_data.operand[i], 1686 insn, vd); 1687 } 1688 else if (GET_CODE (recog_data.operand[i]) == MEM) 1689 replaced = replace_oldest_value_mem (recog_data.operand[i], 1690 insn, vd); 1691 1692 /* If we performed any replacement, update match_dups. */ 1693 if (replaced) 1694 { 1695 int j; 1696 rtx new; 1697 1698 changed = true; 1699 1700 new = *recog_data.operand_loc[i]; 1701 recog_data.operand[i] = new; 1702 for (j = 0; j < recog_data.n_dups; j++) 1703 if (recog_data.dup_num[j] == i) 1704 *recog_data.dup_loc[j] = new; 1705 } 1706 } 1707 1708 did_replacement: 1709 /* Clobber call-clobbered registers. */ 1710 if (GET_CODE (insn) == CALL_INSN) 1711 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1712 if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1713 kill_value_regno (i, vd); 1714 1715 /* Notice stores. */ 1716 note_stores (PATTERN (insn), kill_set_value, vd); 1717 1718 /* Notice copies. */ 1719 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) 1720 copy_value (SET_DEST (set), SET_SRC (set), vd); 1721 1722 if (insn == BB_END (bb)) 1723 break; 1724 } 1725 1726 return changed; 1727} 1728 1729/* Main entry point for the forward copy propagation optimization. */ 1730 1731void 1732copyprop_hardreg_forward (void) 1733{ 1734 struct value_data *all_vd; 1735 bool need_refresh; 1736 basic_block bb, bbp = 0; 1737 1738 need_refresh = false; 1739 1740 all_vd = xmalloc (sizeof (struct value_data) * last_basic_block); 1741 1742 FOR_EACH_BB (bb) 1743 { 1744 /* If a block has a single predecessor, that we've already 1745 processed, begin with the value data that was live at 1746 the end of the predecessor block. */ 1747 /* ??? Ought to use more intelligent queuing of blocks. */ 1748 if (bb->pred) 1749 for (bbp = bb; bbp && bbp != bb->pred->src; bbp = bbp->prev_bb); 1750 if (bb->pred 1751 && ! bb->pred->pred_next 1752 && ! (bb->pred->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)) 1753 && bb->pred->src != ENTRY_BLOCK_PTR 1754 && bbp) 1755 all_vd[bb->index] = all_vd[bb->pred->src->index]; 1756 else 1757 init_value_data (all_vd + bb->index); 1758 1759 if (copyprop_hardreg_forward_1 (bb, all_vd + bb->index)) 1760 need_refresh = true; 1761 } 1762 1763 if (need_refresh) 1764 { 1765 if (rtl_dump_file) 1766 fputs ("\n\n", rtl_dump_file); 1767 1768 /* ??? Irritatingly, delete_noop_moves does not take a set of blocks 1769 to scan, so we have to do a life update with no initial set of 1770 blocks Just In Case. */ 1771 delete_noop_moves (get_insns ()); 1772 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 1773 PROP_DEATH_NOTES 1774 | PROP_SCAN_DEAD_CODE 1775 | PROP_KILL_DEAD_CODE); 1776 } 1777 1778 free (all_vd); 1779} 1780 1781/* Dump the value chain data to stderr. */ 1782 1783void 1784debug_value_data (struct value_data *vd) 1785{ 1786 HARD_REG_SET set; 1787 unsigned int i, j; 1788 1789 CLEAR_HARD_REG_SET (set); 1790 1791 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1792 if (vd->e[i].oldest_regno == i) 1793 { 1794 if (vd->e[i].mode == VOIDmode) 1795 { 1796 if (vd->e[i].next_regno != INVALID_REGNUM) 1797 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", 1798 i, vd->e[i].next_regno); 1799 continue; 1800 } 1801 1802 SET_HARD_REG_BIT (set, i); 1803 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); 1804 1805 for (j = vd->e[i].next_regno; 1806 j != INVALID_REGNUM; 1807 j = vd->e[j].next_regno) 1808 { 1809 if (TEST_HARD_REG_BIT (set, j)) 1810 { 1811 fprintf (stderr, "[%u] Loop in regno chain\n", j); 1812 return; 1813 } 1814 1815 if (vd->e[j].oldest_regno != i) 1816 { 1817 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", 1818 j, vd->e[j].oldest_regno); 1819 return; 1820 } 1821 SET_HARD_REG_BIT (set, j); 1822 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); 1823 } 1824 fputc ('\n', stderr); 1825 } 1826 1827 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1828 if (! TEST_HARD_REG_BIT (set, i) 1829 && (vd->e[i].mode != VOIDmode 1830 || vd->e[i].oldest_regno != i 1831 || vd->e[i].next_regno != INVALID_REGNUM)) 1832 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", 1833 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1834 vd->e[i].next_regno); 1835} 1836 1837#ifdef ENABLE_CHECKING 1838static void 1839validate_value_data (struct value_data *vd) 1840{ 1841 HARD_REG_SET set; 1842 unsigned int i, j; 1843 1844 CLEAR_HARD_REG_SET (set); 1845 1846 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1847 if (vd->e[i].oldest_regno == i) 1848 { 1849 if (vd->e[i].mode == VOIDmode) 1850 { 1851 if (vd->e[i].next_regno != INVALID_REGNUM) 1852 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", 1853 i, vd->e[i].next_regno); 1854 continue; 1855 } 1856 1857 SET_HARD_REG_BIT (set, i); 1858 1859 for (j = vd->e[i].next_regno; 1860 j != INVALID_REGNUM; 1861 j = vd->e[j].next_regno) 1862 { 1863 if (TEST_HARD_REG_BIT (set, j)) 1864 internal_error ("validate_value_data: Loop in regno chain (%u)", 1865 j); 1866 if (vd->e[j].oldest_regno != i) 1867 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", 1868 j, vd->e[j].oldest_regno); 1869 1870 SET_HARD_REG_BIT (set, j); 1871 } 1872 } 1873 1874 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1875 if (! TEST_HARD_REG_BIT (set, i) 1876 && (vd->e[i].mode != VOIDmode 1877 || vd->e[i].oldest_regno != i 1878 || vd->e[i].next_regno != INVALID_REGNUM)) 1879 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", 1880 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1881 vd->e[i].next_regno); 1882} 1883#endif 1884