regcprop.c revision 1.3
1/* Copy propagation on hard registers for the GNU compiler. 2 Copyright (C) 2000-2013 Free Software Foundation, Inc. 3 4 This file is part of GCC. 5 6 GCC is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 3, or (at your option) 9 any later version. 10 11 GCC is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14 License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with GCC; see the file COPYING3. If not see 18 <http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "rtl.h" 25#include "tm_p.h" 26#include "insn-config.h" 27#include "regs.h" 28#include "addresses.h" 29#include "hard-reg-set.h" 30#include "basic-block.h" 31#include "reload.h" 32#include "function.h" 33#include "recog.h" 34#include "flags.h" 35#include "diagnostic-core.h" 36#include "obstack.h" 37#include "tree-pass.h" 38#include "df.h" 39 40/* The following code does forward propagation of hard register copies. 41 The object is to eliminate as many dependencies as possible, so that 42 we have the most scheduling freedom. As a side effect, we also clean 43 up some silly register allocation decisions made by reload. This 44 code may be obsoleted by a new register allocator. */ 45 46/* DEBUG_INSNs aren't changed right away, as doing so might extend the 47 lifetime of a register and get the DEBUG_INSN subsequently reset. 48 So they are queued instead, and updated only when the register is 49 used in some subsequent real insn before it is set. */ 50struct queued_debug_insn_change 51{ 52 struct queued_debug_insn_change *next; 53 rtx insn; 54 rtx *loc; 55 rtx new_rtx; 56}; 57 58/* For each register, we have a list of registers that contain the same 59 value. The OLDEST_REGNO field points to the head of the list, and 60 the NEXT_REGNO field runs through the list. The MODE field indicates 61 what mode the data is known to be in; this field is VOIDmode when the 62 register is not known to contain valid data. */ 63 64struct value_data_entry 65{ 66 enum machine_mode mode; 67 unsigned int oldest_regno; 68 unsigned int next_regno; 69 struct queued_debug_insn_change *debug_insn_changes; 70}; 71 72struct value_data 73{ 74 struct value_data_entry e[FIRST_PSEUDO_REGISTER]; 75 unsigned int max_value_regs; 76 unsigned int n_debug_insn_changes; 77}; 78 79static alloc_pool debug_insn_changes_pool; 80 81static void kill_value_one_regno (unsigned, struct value_data *); 82static void kill_value_regno (unsigned, unsigned, struct value_data *); 83static void kill_value (rtx, struct value_data *); 84static void set_value_regno (unsigned, enum machine_mode, struct value_data *); 85static void init_value_data (struct value_data *); 86static void kill_clobbered_value (rtx, const_rtx, void *); 87static void kill_set_value (rtx, const_rtx, void *); 88static int kill_autoinc_value (rtx *, void *); 89static void copy_value (rtx, rtx, struct value_data *); 90static bool mode_change_ok (enum machine_mode, enum machine_mode, 91 unsigned int); 92static rtx maybe_mode_change (enum machine_mode, enum machine_mode, 93 enum machine_mode, unsigned int, unsigned int); 94static rtx find_oldest_value_reg (enum reg_class, rtx, struct value_data *); 95static bool replace_oldest_value_reg (rtx *, enum reg_class, rtx, 96 struct value_data *); 97static bool replace_oldest_value_addr (rtx *, enum reg_class, 98 enum machine_mode, addr_space_t, rtx, 99 struct value_data *); 100static bool replace_oldest_value_mem (rtx, rtx, struct value_data *); 101static bool copyprop_hardreg_forward_1 (basic_block, struct value_data *); 102extern void debug_value_data (struct value_data *); 103#ifdef ENABLE_CHECKING 104static void validate_value_data (struct value_data *); 105#endif 106 107/* Free all queued updates for DEBUG_INSNs that change some reg to 108 register REGNO. */ 109 110static void 111free_debug_insn_changes (struct value_data *vd, unsigned int regno) 112{ 113 struct queued_debug_insn_change *cur, *next; 114 for (cur = vd->e[regno].debug_insn_changes; cur; cur = next) 115 { 116 next = cur->next; 117 --vd->n_debug_insn_changes; 118 pool_free (debug_insn_changes_pool, cur); 119 } 120 vd->e[regno].debug_insn_changes = NULL; 121} 122 123/* Kill register REGNO. This involves removing it from any value 124 lists, and resetting the value mode to VOIDmode. This is only a 125 helper function; it does not handle any hard registers overlapping 126 with REGNO. */ 127 128static void 129kill_value_one_regno (unsigned int regno, struct value_data *vd) 130{ 131 unsigned int i, next; 132 133 if (vd->e[regno].oldest_regno != regno) 134 { 135 for (i = vd->e[regno].oldest_regno; 136 vd->e[i].next_regno != regno; 137 i = vd->e[i].next_regno) 138 continue; 139 vd->e[i].next_regno = vd->e[regno].next_regno; 140 } 141 else if ((next = vd->e[regno].next_regno) != INVALID_REGNUM) 142 { 143 for (i = next; i != INVALID_REGNUM; i = vd->e[i].next_regno) 144 vd->e[i].oldest_regno = next; 145 } 146 147 vd->e[regno].mode = VOIDmode; 148 vd->e[regno].oldest_regno = regno; 149 vd->e[regno].next_regno = INVALID_REGNUM; 150 if (vd->e[regno].debug_insn_changes) 151 free_debug_insn_changes (vd, regno); 152 153#ifdef ENABLE_CHECKING 154 validate_value_data (vd); 155#endif 156} 157 158/* Kill the value in register REGNO for NREGS, and any other registers 159 whose values overlap. */ 160 161static void 162kill_value_regno (unsigned int regno, unsigned int nregs, 163 struct value_data *vd) 164{ 165 unsigned int j; 166 167 /* Kill the value we're told to kill. */ 168 for (j = 0; j < nregs; ++j) 169 kill_value_one_regno (regno + j, vd); 170 171 /* Kill everything that overlapped what we're told to kill. */ 172 if (regno < vd->max_value_regs) 173 j = 0; 174 else 175 j = regno - vd->max_value_regs; 176 for (; j < regno; ++j) 177 { 178 unsigned int i, n; 179 if (vd->e[j].mode == VOIDmode) 180 continue; 181 n = hard_regno_nregs[j][vd->e[j].mode]; 182 if (j + n > regno) 183 for (i = 0; i < n; ++i) 184 kill_value_one_regno (j + i, vd); 185 } 186} 187 188/* Kill X. This is a convenience function wrapping kill_value_regno 189 so that we mind the mode the register is in. */ 190 191static void 192kill_value (rtx x, struct value_data *vd) 193{ 194 rtx orig_rtx = x; 195 196 if (GET_CODE (x) == SUBREG) 197 { 198 x = simplify_subreg (GET_MODE (x), SUBREG_REG (x), 199 GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); 200 if (x == NULL_RTX) 201 x = SUBREG_REG (orig_rtx); 202 } 203 if (REG_P (x)) 204 { 205 unsigned int regno = REGNO (x); 206 unsigned int n = hard_regno_nregs[regno][GET_MODE (x)]; 207 208 kill_value_regno (regno, n, vd); 209 } 210} 211 212/* Remember that REGNO is valid in MODE. */ 213 214static void 215set_value_regno (unsigned int regno, enum machine_mode mode, 216 struct value_data *vd) 217{ 218 unsigned int nregs; 219 220 vd->e[regno].mode = mode; 221 222 nregs = hard_regno_nregs[regno][mode]; 223 if (nregs > vd->max_value_regs) 224 vd->max_value_regs = nregs; 225} 226 227/* Initialize VD such that there are no known relationships between regs. */ 228 229static void 230init_value_data (struct value_data *vd) 231{ 232 int i; 233 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 234 { 235 vd->e[i].mode = VOIDmode; 236 vd->e[i].oldest_regno = i; 237 vd->e[i].next_regno = INVALID_REGNUM; 238 vd->e[i].debug_insn_changes = NULL; 239 } 240 vd->max_value_regs = 0; 241 vd->n_debug_insn_changes = 0; 242} 243 244/* Called through note_stores. If X is clobbered, kill its value. */ 245 246static void 247kill_clobbered_value (rtx x, const_rtx set, void *data) 248{ 249 struct value_data *const vd = (struct value_data *) data; 250 if (GET_CODE (set) == CLOBBER) 251 kill_value (x, vd); 252} 253 254/* A structure passed as data to kill_set_value through note_stores. */ 255struct kill_set_value_data 256{ 257 struct value_data *vd; 258 rtx ignore_set_reg; 259}; 260 261/* Called through note_stores. If X is set, not clobbered, kill its 262 current value and install it as the root of its own value list. */ 263 264static void 265kill_set_value (rtx x, const_rtx set, void *data) 266{ 267 struct kill_set_value_data *ksvd = (struct kill_set_value_data *) data; 268 if (rtx_equal_p (x, ksvd->ignore_set_reg)) 269 return; 270 if (GET_CODE (set) != CLOBBER) 271 { 272 kill_value (x, ksvd->vd); 273 if (REG_P (x)) 274 set_value_regno (REGNO (x), GET_MODE (x), ksvd->vd); 275 } 276} 277 278/* Called through for_each_rtx. Kill any register used as the base of an 279 auto-increment expression, and install that register as the root of its 280 own value list. */ 281 282static int 283kill_autoinc_value (rtx *px, void *data) 284{ 285 rtx x = *px; 286 struct value_data *const vd = (struct value_data *) data; 287 288 if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC) 289 { 290 x = XEXP (x, 0); 291 kill_value (x, vd); 292 set_value_regno (REGNO (x), GET_MODE (x), vd); 293 return -1; 294 } 295 296 return 0; 297} 298 299/* Assert that SRC has been copied to DEST. Adjust the data structures 300 to reflect that SRC contains an older copy of the shared value. */ 301 302static void 303copy_value (rtx dest, rtx src, struct value_data *vd) 304{ 305 unsigned int dr = REGNO (dest); 306 unsigned int sr = REGNO (src); 307 unsigned int dn, sn; 308 unsigned int i; 309 310 /* ??? At present, it's possible to see noop sets. It'd be nice if 311 this were cleaned up beforehand... */ 312 if (sr == dr) 313 return; 314 315 /* Do not propagate copies to the stack pointer, as that can leave 316 memory accesses with no scheduling dependency on the stack update. */ 317 if (dr == STACK_POINTER_REGNUM) 318 return; 319 320 /* Likewise with the frame pointer, if we're using one. */ 321 if (frame_pointer_needed && dr == HARD_FRAME_POINTER_REGNUM) 322 return; 323 324 /* Do not propagate copies to fixed or global registers, patterns 325 can be relying to see particular fixed register or users can 326 expect the chosen global register in asm. */ 327 if (fixed_regs[dr] || global_regs[dr]) 328 return; 329 330 /* If SRC and DEST overlap, don't record anything. */ 331 dn = hard_regno_nregs[dr][GET_MODE (dest)]; 332 sn = hard_regno_nregs[sr][GET_MODE (dest)]; 333 if ((dr > sr && dr < sr + sn) 334 || (sr > dr && sr < dr + dn)) 335 return; 336 337 /* If SRC had no assigned mode (i.e. we didn't know it was live) 338 assign it now and assume the value came from an input argument 339 or somesuch. */ 340 if (vd->e[sr].mode == VOIDmode) 341 set_value_regno (sr, vd->e[dr].mode, vd); 342 343 /* If we are narrowing the input to a smaller number of hard regs, 344 and it is in big endian, we are really extracting a high part. 345 Since we generally associate a low part of a value with the value itself, 346 we must not do the same for the high part. 347 Note we can still get low parts for the same mode combination through 348 a two-step copy involving differently sized hard regs. 349 Assume hard regs fr* are 32 bits bits each, while r* are 64 bits each: 350 (set (reg:DI r0) (reg:DI fr0)) 351 (set (reg:SI fr2) (reg:SI r0)) 352 loads the low part of (reg:DI fr0) - i.e. fr1 - into fr2, while: 353 (set (reg:SI fr2) (reg:SI fr0)) 354 loads the high part of (reg:DI fr0) into fr2. 355 356 We can't properly represent the latter case in our tables, so don't 357 record anything then. */ 358 else if (sn < (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode] 359 && (GET_MODE_SIZE (vd->e[sr].mode) > UNITS_PER_WORD 360 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) 361 return; 362 363 /* If SRC had been assigned a mode narrower than the copy, we can't 364 link DEST into the chain, because not all of the pieces of the 365 copy came from oldest_regno. */ 366 else if (sn > (unsigned int) hard_regno_nregs[sr][vd->e[sr].mode]) 367 return; 368 369 /* Link DR at the end of the value chain used by SR. */ 370 371 vd->e[dr].oldest_regno = vd->e[sr].oldest_regno; 372 373 for (i = sr; vd->e[i].next_regno != INVALID_REGNUM; i = vd->e[i].next_regno) 374 continue; 375 vd->e[i].next_regno = dr; 376 377#ifdef ENABLE_CHECKING 378 validate_value_data (vd); 379#endif 380} 381 382/* Return true if a mode change from ORIG to NEW is allowed for REGNO. */ 383 384static bool 385mode_change_ok (enum machine_mode orig_mode, enum machine_mode new_mode, 386 unsigned int regno ATTRIBUTE_UNUSED) 387{ 388 if (GET_MODE_SIZE (orig_mode) < GET_MODE_SIZE (new_mode)) 389 return false; 390 391#ifdef CANNOT_CHANGE_MODE_CLASS 392 return !REG_CANNOT_CHANGE_MODE_P (regno, orig_mode, new_mode); 393#endif 394 395 return true; 396} 397 398/* Register REGNO was originally set in ORIG_MODE. It - or a copy of it - 399 was copied in COPY_MODE to COPY_REGNO, and then COPY_REGNO was accessed 400 in NEW_MODE. 401 Return a NEW_MODE rtx for REGNO if that's OK, otherwise return NULL_RTX. */ 402 403static rtx 404maybe_mode_change (enum machine_mode orig_mode, enum machine_mode copy_mode, 405 enum machine_mode new_mode, unsigned int regno, 406 unsigned int copy_regno ATTRIBUTE_UNUSED) 407{ 408 if (GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (orig_mode) 409 && GET_MODE_SIZE (copy_mode) < GET_MODE_SIZE (new_mode)) 410 return NULL_RTX; 411 412 if (orig_mode == new_mode) 413 return gen_rtx_raw_REG (new_mode, regno); 414 else if (mode_change_ok (orig_mode, new_mode, regno)) 415 { 416 int copy_nregs = hard_regno_nregs[copy_regno][copy_mode]; 417 int use_nregs = hard_regno_nregs[copy_regno][new_mode]; 418 int copy_offset 419 = GET_MODE_SIZE (copy_mode) / copy_nregs * (copy_nregs - use_nregs); 420 int offset 421 = GET_MODE_SIZE (orig_mode) - GET_MODE_SIZE (new_mode) - copy_offset; 422 int byteoffset = offset % UNITS_PER_WORD; 423 int wordoffset = offset - byteoffset; 424 425 offset = ((WORDS_BIG_ENDIAN ? wordoffset : 0) 426 + (BYTES_BIG_ENDIAN ? byteoffset : 0)); 427 regno += subreg_regno_offset (regno, orig_mode, offset, new_mode); 428 if (HARD_REGNO_MODE_OK (regno, new_mode)) 429 return gen_rtx_raw_REG (new_mode, regno); 430 } 431 return NULL_RTX; 432} 433 434/* Find the oldest copy of the value contained in REGNO that is in 435 register class CL and has mode MODE. If found, return an rtx 436 of that oldest register, otherwise return NULL. */ 437 438static rtx 439find_oldest_value_reg (enum reg_class cl, rtx reg, struct value_data *vd) 440{ 441 unsigned int regno = REGNO (reg); 442 enum machine_mode mode = GET_MODE (reg); 443 unsigned int i; 444 445 /* If we are accessing REG in some mode other that what we set it in, 446 make sure that the replacement is valid. In particular, consider 447 (set (reg:DI r11) (...)) 448 (set (reg:SI r9) (reg:SI r11)) 449 (set (reg:SI r10) (...)) 450 (set (...) (reg:DI r9)) 451 Replacing r9 with r11 is invalid. */ 452 if (mode != vd->e[regno].mode) 453 { 454 if (hard_regno_nregs[regno][mode] 455 > hard_regno_nregs[regno][vd->e[regno].mode]) 456 return NULL_RTX; 457 } 458 459 for (i = vd->e[regno].oldest_regno; i != regno; i = vd->e[i].next_regno) 460 { 461 enum machine_mode oldmode = vd->e[i].mode; 462 rtx new_rtx; 463 464 if (!in_hard_reg_set_p (reg_class_contents[cl], mode, i)) 465 continue; 466 467 new_rtx = maybe_mode_change (oldmode, vd->e[regno].mode, mode, i, regno); 468 if (new_rtx) 469 { 470 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (reg); 471 REG_ATTRS (new_rtx) = REG_ATTRS (reg); 472 REG_POINTER (new_rtx) = REG_POINTER (reg); 473 return new_rtx; 474 } 475 } 476 477 return NULL_RTX; 478} 479 480/* If possible, replace the register at *LOC with the oldest register 481 in register class CL. Return true if successfully replaced. */ 482 483static bool 484replace_oldest_value_reg (rtx *loc, enum reg_class cl, rtx insn, 485 struct value_data *vd) 486{ 487 rtx new_rtx = find_oldest_value_reg (cl, *loc, vd); 488 if (new_rtx) 489 { 490 if (DEBUG_INSN_P (insn)) 491 { 492 struct queued_debug_insn_change *change; 493 494 if (dump_file) 495 fprintf (dump_file, "debug_insn %u: queued replacing reg %u with %u\n", 496 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx)); 497 498 change = (struct queued_debug_insn_change *) 499 pool_alloc (debug_insn_changes_pool); 500 change->next = vd->e[REGNO (new_rtx)].debug_insn_changes; 501 change->insn = insn; 502 change->loc = loc; 503 change->new_rtx = new_rtx; 504 vd->e[REGNO (new_rtx)].debug_insn_changes = change; 505 ++vd->n_debug_insn_changes; 506 return true; 507 } 508 if (dump_file) 509 fprintf (dump_file, "insn %u: replaced reg %u with %u\n", 510 INSN_UID (insn), REGNO (*loc), REGNO (new_rtx)); 511 512 validate_change (insn, loc, new_rtx, 1); 513 return true; 514 } 515 return false; 516} 517 518/* Similar to replace_oldest_value_reg, but *LOC contains an address. 519 Adapted from find_reloads_address_1. CL is INDEX_REG_CLASS or 520 BASE_REG_CLASS depending on how the register is being considered. */ 521 522static bool 523replace_oldest_value_addr (rtx *loc, enum reg_class cl, 524 enum machine_mode mode, addr_space_t as, 525 rtx insn, struct value_data *vd) 526{ 527 rtx x = *loc; 528 RTX_CODE code = GET_CODE (x); 529 const char *fmt; 530 int i, j; 531 bool changed = false; 532 533 switch (code) 534 { 535 case PLUS: 536 if (DEBUG_INSN_P (insn)) 537 break; 538 539 { 540 rtx orig_op0 = XEXP (x, 0); 541 rtx orig_op1 = XEXP (x, 1); 542 RTX_CODE code0 = GET_CODE (orig_op0); 543 RTX_CODE code1 = GET_CODE (orig_op1); 544 rtx op0 = orig_op0; 545 rtx op1 = orig_op1; 546 rtx *locI = NULL; 547 rtx *locB = NULL; 548 enum rtx_code index_code = SCRATCH; 549 550 if (GET_CODE (op0) == SUBREG) 551 { 552 op0 = SUBREG_REG (op0); 553 code0 = GET_CODE (op0); 554 } 555 556 if (GET_CODE (op1) == SUBREG) 557 { 558 op1 = SUBREG_REG (op1); 559 code1 = GET_CODE (op1); 560 } 561 562 if (code0 == MULT || code0 == SIGN_EXTEND || code0 == TRUNCATE 563 || code0 == ZERO_EXTEND || code1 == MEM) 564 { 565 locI = &XEXP (x, 0); 566 locB = &XEXP (x, 1); 567 index_code = GET_CODE (*locI); 568 } 569 else if (code1 == MULT || code1 == SIGN_EXTEND || code1 == TRUNCATE 570 || code1 == ZERO_EXTEND || code0 == MEM) 571 { 572 locI = &XEXP (x, 1); 573 locB = &XEXP (x, 0); 574 index_code = GET_CODE (*locI); 575 } 576 else if (code0 == CONST_INT || code0 == CONST 577 || code0 == SYMBOL_REF || code0 == LABEL_REF) 578 { 579 locB = &XEXP (x, 1); 580 index_code = GET_CODE (XEXP (x, 0)); 581 } 582 else if (code1 == CONST_INT || code1 == CONST 583 || code1 == SYMBOL_REF || code1 == LABEL_REF) 584 { 585 locB = &XEXP (x, 0); 586 index_code = GET_CODE (XEXP (x, 1)); 587 } 588 else if (code0 == REG && code1 == REG) 589 { 590 int index_op; 591 unsigned regno0 = REGNO (op0), regno1 = REGNO (op1); 592 593 if (REGNO_OK_FOR_INDEX_P (regno1) 594 && regno_ok_for_base_p (regno0, mode, as, PLUS, REG)) 595 index_op = 1; 596 else if (REGNO_OK_FOR_INDEX_P (regno0) 597 && regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) 598 index_op = 0; 599 else if (regno_ok_for_base_p (regno0, mode, as, PLUS, REG) 600 || REGNO_OK_FOR_INDEX_P (regno1)) 601 index_op = 1; 602 else if (regno_ok_for_base_p (regno1, mode, as, PLUS, REG)) 603 index_op = 0; 604 else 605 index_op = 1; 606 607 locI = &XEXP (x, index_op); 608 locB = &XEXP (x, !index_op); 609 index_code = GET_CODE (*locI); 610 } 611 else if (code0 == REG) 612 { 613 locI = &XEXP (x, 0); 614 locB = &XEXP (x, 1); 615 index_code = GET_CODE (*locI); 616 } 617 else if (code1 == REG) 618 { 619 locI = &XEXP (x, 1); 620 locB = &XEXP (x, 0); 621 index_code = GET_CODE (*locI); 622 } 623 624 if (locI) 625 changed |= replace_oldest_value_addr (locI, INDEX_REG_CLASS, 626 mode, as, insn, vd); 627 if (locB) 628 changed |= replace_oldest_value_addr (locB, 629 base_reg_class (mode, as, PLUS, 630 index_code), 631 mode, as, insn, vd); 632 return changed; 633 } 634 635 case POST_INC: 636 case POST_DEC: 637 case POST_MODIFY: 638 case PRE_INC: 639 case PRE_DEC: 640 case PRE_MODIFY: 641 return false; 642 643 case MEM: 644 return replace_oldest_value_mem (x, insn, vd); 645 646 case REG: 647 return replace_oldest_value_reg (loc, cl, insn, vd); 648 649 default: 650 break; 651 } 652 653 fmt = GET_RTX_FORMAT (code); 654 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 655 { 656 if (fmt[i] == 'e') 657 changed |= replace_oldest_value_addr (&XEXP (x, i), cl, mode, as, 658 insn, vd); 659 else if (fmt[i] == 'E') 660 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 661 changed |= replace_oldest_value_addr (&XVECEXP (x, i, j), cl, 662 mode, as, insn, vd); 663 } 664 665 return changed; 666} 667 668/* Similar to replace_oldest_value_reg, but X contains a memory. */ 669 670static bool 671replace_oldest_value_mem (rtx x, rtx insn, struct value_data *vd) 672{ 673 enum reg_class cl; 674 675 if (DEBUG_INSN_P (insn)) 676 cl = ALL_REGS; 677 else 678 cl = base_reg_class (GET_MODE (x), MEM_ADDR_SPACE (x), MEM, SCRATCH); 679 680 return replace_oldest_value_addr (&XEXP (x, 0), cl, 681 GET_MODE (x), MEM_ADDR_SPACE (x), 682 insn, vd); 683} 684 685/* Apply all queued updates for DEBUG_INSNs that change some reg to 686 register REGNO. */ 687 688static void 689apply_debug_insn_changes (struct value_data *vd, unsigned int regno) 690{ 691 struct queued_debug_insn_change *change; 692 rtx last_insn = vd->e[regno].debug_insn_changes->insn; 693 694 for (change = vd->e[regno].debug_insn_changes; 695 change; 696 change = change->next) 697 { 698 if (last_insn != change->insn) 699 { 700 apply_change_group (); 701 last_insn = change->insn; 702 } 703 validate_change (change->insn, change->loc, change->new_rtx, 1); 704 } 705 apply_change_group (); 706} 707 708/* Called via for_each_rtx, for all used registers in a real 709 insn apply DEBUG_INSN changes that change registers to the 710 used register. */ 711 712static int 713cprop_find_used_regs_1 (rtx *loc, void *data) 714{ 715 if (REG_P (*loc)) 716 { 717 struct value_data *vd = (struct value_data *) data; 718 if (vd->e[REGNO (*loc)].debug_insn_changes) 719 { 720 apply_debug_insn_changes (vd, REGNO (*loc)); 721 free_debug_insn_changes (vd, REGNO (*loc)); 722 } 723 } 724 return 0; 725} 726 727/* Called via note_uses, for all used registers in a real insn 728 apply DEBUG_INSN changes that change registers to the used 729 registers. */ 730 731static void 732cprop_find_used_regs (rtx *loc, void *vd) 733{ 734 for_each_rtx (loc, cprop_find_used_regs_1, vd); 735} 736 737/* Perform the forward copy propagation on basic block BB. */ 738 739static bool 740copyprop_hardreg_forward_1 (basic_block bb, struct value_data *vd) 741{ 742 bool anything_changed = false; 743 rtx insn; 744 745 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn)) 746 { 747 int n_ops, i, alt, predicated; 748 bool is_asm, any_replacements; 749 rtx set; 750 rtx link; 751 bool replaced[MAX_RECOG_OPERANDS]; 752 bool changed = false; 753 struct kill_set_value_data ksvd; 754 755 if (!NONDEBUG_INSN_P (insn)) 756 { 757 if (DEBUG_INSN_P (insn)) 758 { 759 rtx loc = INSN_VAR_LOCATION_LOC (insn); 760 if (!VAR_LOC_UNKNOWN_P (loc)) 761 replace_oldest_value_addr (&INSN_VAR_LOCATION_LOC (insn), 762 ALL_REGS, GET_MODE (loc), 763 ADDR_SPACE_GENERIC, insn, vd); 764 } 765 766 if (insn == BB_END (bb)) 767 break; 768 else 769 continue; 770 } 771 772 set = single_set (insn); 773 extract_insn (insn); 774 if (! constrain_operands (1)) 775 fatal_insn_not_found (insn); 776 preprocess_constraints (); 777 alt = which_alternative; 778 n_ops = recog_data.n_operands; 779 is_asm = asm_noperands (PATTERN (insn)) >= 0; 780 781 /* Simplify the code below by rewriting things to reflect 782 matching constraints. Also promote OP_OUT to OP_INOUT 783 in predicated instructions. */ 784 785 predicated = GET_CODE (PATTERN (insn)) == COND_EXEC; 786 for (i = 0; i < n_ops; ++i) 787 { 788 int matches = recog_op_alt[i][alt].matches; 789 if (matches >= 0) 790 recog_op_alt[i][alt].cl = recog_op_alt[matches][alt].cl; 791 if (matches >= 0 || recog_op_alt[i][alt].matched >= 0 792 || (predicated && recog_data.operand_type[i] == OP_OUT)) 793 recog_data.operand_type[i] = OP_INOUT; 794 } 795 796 /* Apply changes to earlier DEBUG_INSNs if possible. */ 797 if (vd->n_debug_insn_changes) 798 note_uses (&PATTERN (insn), cprop_find_used_regs, vd); 799 800 /* For each earlyclobber operand, zap the value data. */ 801 for (i = 0; i < n_ops; i++) 802 if (recog_op_alt[i][alt].earlyclobber) 803 kill_value (recog_data.operand[i], vd); 804 805 /* Within asms, a clobber cannot overlap inputs or outputs. 806 I wouldn't think this were true for regular insns, but 807 scan_rtx treats them like that... */ 808 note_stores (PATTERN (insn), kill_clobbered_value, vd); 809 810 /* Kill all auto-incremented values. */ 811 /* ??? REG_INC is useless, since stack pushes aren't done that way. */ 812 for_each_rtx (&PATTERN (insn), kill_autoinc_value, vd); 813 814 /* Kill all early-clobbered operands. */ 815 for (i = 0; i < n_ops; i++) 816 if (recog_op_alt[i][alt].earlyclobber) 817 kill_value (recog_data.operand[i], vd); 818 819 /* If we have dead sets in the insn, then we need to note these as we 820 would clobbers. */ 821 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 822 { 823 if (REG_NOTE_KIND (link) == REG_UNUSED) 824 { 825 kill_value (XEXP (link, 0), vd); 826 /* Furthermore, if the insn looked like a single-set, 827 but the dead store kills the source value of that 828 set, then we can no-longer use the plain move 829 special case below. */ 830 if (set 831 && reg_overlap_mentioned_p (XEXP (link, 0), SET_SRC (set))) 832 set = NULL; 833 } 834 } 835 836 /* Special-case plain move instructions, since we may well 837 be able to do the move from a different register class. */ 838 if (set && REG_P (SET_SRC (set))) 839 { 840 rtx src = SET_SRC (set); 841 unsigned int regno = REGNO (src); 842 enum machine_mode mode = GET_MODE (src); 843 unsigned int i; 844 rtx new_rtx; 845 846 /* If we are accessing SRC in some mode other that what we 847 set it in, make sure that the replacement is valid. */ 848 if (mode != vd->e[regno].mode) 849 { 850 if (hard_regno_nregs[regno][mode] 851 > hard_regno_nregs[regno][vd->e[regno].mode]) 852 goto no_move_special_case; 853 854 /* And likewise, if we are narrowing on big endian the transformation 855 is also invalid. */ 856 if (hard_regno_nregs[regno][mode] 857 < hard_regno_nregs[regno][vd->e[regno].mode] 858 && (GET_MODE_SIZE (vd->e[regno].mode) > UNITS_PER_WORD 859 ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) 860 goto no_move_special_case; 861 } 862 863 /* If the destination is also a register, try to find a source 864 register in the same class. */ 865 if (REG_P (SET_DEST (set))) 866 { 867 new_rtx = find_oldest_value_reg (REGNO_REG_CLASS (regno), src, vd); 868 if (new_rtx && validate_change (insn, &SET_SRC (set), new_rtx, 0)) 869 { 870 if (dump_file) 871 fprintf (dump_file, 872 "insn %u: replaced reg %u with %u\n", 873 INSN_UID (insn), regno, REGNO (new_rtx)); 874 changed = true; 875 goto did_replacement; 876 } 877 /* We need to re-extract as validate_change clobbers 878 recog_data. */ 879 extract_insn (insn); 880 if (! constrain_operands (1)) 881 fatal_insn_not_found (insn); 882 preprocess_constraints (); 883 } 884 885 /* Otherwise, try all valid registers and see if its valid. */ 886 for (i = vd->e[regno].oldest_regno; i != regno; 887 i = vd->e[i].next_regno) 888 { 889 new_rtx = maybe_mode_change (vd->e[i].mode, vd->e[regno].mode, 890 mode, i, regno); 891 if (new_rtx != NULL_RTX) 892 { 893 if (validate_change (insn, &SET_SRC (set), new_rtx, 0)) 894 { 895 ORIGINAL_REGNO (new_rtx) = ORIGINAL_REGNO (src); 896 REG_ATTRS (new_rtx) = REG_ATTRS (src); 897 REG_POINTER (new_rtx) = REG_POINTER (src); 898 if (dump_file) 899 fprintf (dump_file, 900 "insn %u: replaced reg %u with %u\n", 901 INSN_UID (insn), regno, REGNO (new_rtx)); 902 changed = true; 903 goto did_replacement; 904 } 905 /* We need to re-extract as validate_change clobbers 906 recog_data. */ 907 extract_insn (insn); 908 if (! constrain_operands (1)) 909 fatal_insn_not_found (insn); 910 preprocess_constraints (); 911 } 912 } 913 } 914 no_move_special_case: 915 916 any_replacements = false; 917 918 /* For each input operand, replace a hard register with the 919 eldest live copy that's in an appropriate register class. */ 920 for (i = 0; i < n_ops; i++) 921 { 922 replaced[i] = false; 923 924 /* Don't scan match_operand here, since we've no reg class 925 information to pass down. Any operands that we could 926 substitute in will be represented elsewhere. */ 927 if (recog_data.constraints[i][0] == '\0') 928 continue; 929 930 /* Don't replace in asms intentionally referencing hard regs. */ 931 if (is_asm && REG_P (recog_data.operand[i]) 932 && (REGNO (recog_data.operand[i]) 933 == ORIGINAL_REGNO (recog_data.operand[i]))) 934 continue; 935 936 if (recog_data.operand_type[i] == OP_IN) 937 { 938 if (recog_op_alt[i][alt].is_address) 939 replaced[i] 940 = replace_oldest_value_addr (recog_data.operand_loc[i], 941 recog_op_alt[i][alt].cl, 942 VOIDmode, ADDR_SPACE_GENERIC, 943 insn, vd); 944 else if (REG_P (recog_data.operand[i])) 945 replaced[i] 946 = replace_oldest_value_reg (recog_data.operand_loc[i], 947 recog_op_alt[i][alt].cl, 948 insn, vd); 949 else if (MEM_P (recog_data.operand[i])) 950 replaced[i] = replace_oldest_value_mem (recog_data.operand[i], 951 insn, vd); 952 } 953 else if (MEM_P (recog_data.operand[i])) 954 replaced[i] = replace_oldest_value_mem (recog_data.operand[i], 955 insn, vd); 956 957 /* If we performed any replacement, update match_dups. */ 958 if (replaced[i]) 959 { 960 int j; 961 rtx new_rtx; 962 963 new_rtx = *recog_data.operand_loc[i]; 964 recog_data.operand[i] = new_rtx; 965 for (j = 0; j < recog_data.n_dups; j++) 966 if (recog_data.dup_num[j] == i) 967 validate_unshare_change (insn, recog_data.dup_loc[j], new_rtx, 1); 968 969 any_replacements = true; 970 } 971 } 972 973 if (any_replacements) 974 { 975 if (! apply_change_group ()) 976 { 977 for (i = 0; i < n_ops; i++) 978 if (replaced[i]) 979 { 980 rtx old = *recog_data.operand_loc[i]; 981 recog_data.operand[i] = old; 982 } 983 984 if (dump_file) 985 fprintf (dump_file, 986 "insn %u: reg replacements not verified\n", 987 INSN_UID (insn)); 988 } 989 else 990 changed = true; 991 } 992 993 did_replacement: 994 if (changed) 995 { 996 anything_changed = true; 997 998 /* If something changed, perhaps further changes to earlier 999 DEBUG_INSNs can be applied. */ 1000 if (vd->n_debug_insn_changes) 1001 note_uses (&PATTERN (insn), cprop_find_used_regs, vd); 1002 } 1003 1004 ksvd.vd = vd; 1005 ksvd.ignore_set_reg = NULL_RTX; 1006 1007 /* Clobber call-clobbered registers. */ 1008 if (CALL_P (insn)) 1009 { 1010 unsigned int set_regno = INVALID_REGNUM; 1011 unsigned int set_nregs = 0; 1012 unsigned int regno; 1013 rtx exp; 1014 hard_reg_set_iterator hrsi; 1015 1016 for (exp = CALL_INSN_FUNCTION_USAGE (insn); exp; exp = XEXP (exp, 1)) 1017 { 1018 rtx x = XEXP (exp, 0); 1019 if (GET_CODE (x) == SET) 1020 { 1021 rtx dest = SET_DEST (x); 1022 kill_value (dest, vd); 1023 set_value_regno (REGNO (dest), GET_MODE (dest), vd); 1024 copy_value (dest, SET_SRC (x), vd); 1025 ksvd.ignore_set_reg = dest; 1026 set_regno = REGNO (dest); 1027 set_nregs 1028 = hard_regno_nregs[set_regno][GET_MODE (dest)]; 1029 break; 1030 } 1031 } 1032 1033 EXECUTE_IF_SET_IN_HARD_REG_SET (regs_invalidated_by_call, 0, regno, hrsi) 1034 if (regno < set_regno || regno >= set_regno + set_nregs) 1035 kill_value_regno (regno, 1, vd); 1036 1037 /* If SET was seen in CALL_INSN_FUNCTION_USAGE, and SET_SRC 1038 of the SET isn't in regs_invalidated_by_call hard reg set, 1039 but instead among CLOBBERs on the CALL_INSN, we could wrongly 1040 assume the value in it is still live. */ 1041 if (ksvd.ignore_set_reg) 1042 { 1043 note_stores (PATTERN (insn), kill_clobbered_value, vd); 1044 for (exp = CALL_INSN_FUNCTION_USAGE (insn); 1045 exp; 1046 exp = XEXP (exp, 1)) 1047 { 1048 rtx x = XEXP (exp, 0); 1049 if (GET_CODE (x) == CLOBBER) 1050 kill_value (SET_DEST (x), vd); 1051 } 1052 } 1053 } 1054 1055 /* Notice stores. */ 1056 note_stores (PATTERN (insn), kill_set_value, &ksvd); 1057 1058 /* Notice copies. */ 1059 if (set && REG_P (SET_DEST (set)) && REG_P (SET_SRC (set))) 1060 copy_value (SET_DEST (set), SET_SRC (set), vd); 1061 1062 if (insn == BB_END (bb)) 1063 break; 1064 } 1065 1066 return anything_changed; 1067} 1068 1069/* Main entry point for the forward copy propagation optimization. */ 1070 1071static unsigned int 1072copyprop_hardreg_forward (void) 1073{ 1074 struct value_data *all_vd; 1075 basic_block bb; 1076 sbitmap visited; 1077 bool analyze_called = false; 1078 1079 all_vd = XNEWVEC (struct value_data, last_basic_block); 1080 1081 visited = sbitmap_alloc (last_basic_block); 1082 bitmap_clear (visited); 1083 1084 if (MAY_HAVE_DEBUG_INSNS) 1085 debug_insn_changes_pool 1086 = create_alloc_pool ("debug insn changes pool", 1087 sizeof (struct queued_debug_insn_change), 256); 1088 1089 FOR_EACH_BB (bb) 1090 { 1091 bitmap_set_bit (visited, bb->index); 1092 1093 /* If a block has a single predecessor, that we've already 1094 processed, begin with the value data that was live at 1095 the end of the predecessor block. */ 1096 /* ??? Ought to use more intelligent queuing of blocks. */ 1097 if (single_pred_p (bb) 1098 && bitmap_bit_p (visited, single_pred (bb)->index) 1099 && ! (single_pred_edge (bb)->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))) 1100 { 1101 all_vd[bb->index] = all_vd[single_pred (bb)->index]; 1102 if (all_vd[bb->index].n_debug_insn_changes) 1103 { 1104 unsigned int regno; 1105 1106 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 1107 { 1108 if (all_vd[bb->index].e[regno].debug_insn_changes) 1109 { 1110 all_vd[bb->index].e[regno].debug_insn_changes = NULL; 1111 if (--all_vd[bb->index].n_debug_insn_changes == 0) 1112 break; 1113 } 1114 } 1115 } 1116 } 1117 else 1118 init_value_data (all_vd + bb->index); 1119 1120 copyprop_hardreg_forward_1 (bb, all_vd + bb->index); 1121 } 1122 1123 if (MAY_HAVE_DEBUG_INSNS) 1124 { 1125 FOR_EACH_BB (bb) 1126 if (bitmap_bit_p (visited, bb->index) 1127 && all_vd[bb->index].n_debug_insn_changes) 1128 { 1129 unsigned int regno; 1130 bitmap live; 1131 1132 if (!analyze_called) 1133 { 1134 df_analyze (); 1135 analyze_called = true; 1136 } 1137 live = df_get_live_out (bb); 1138 for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++) 1139 if (all_vd[bb->index].e[regno].debug_insn_changes) 1140 { 1141 if (REGNO_REG_SET_P (live, regno)) 1142 apply_debug_insn_changes (all_vd + bb->index, regno); 1143 if (all_vd[bb->index].n_debug_insn_changes == 0) 1144 break; 1145 } 1146 } 1147 1148 free_alloc_pool (debug_insn_changes_pool); 1149 } 1150 1151 sbitmap_free (visited); 1152 free (all_vd); 1153 return 0; 1154} 1155 1156/* Dump the value chain data to stderr. */ 1157 1158DEBUG_FUNCTION void 1159debug_value_data (struct value_data *vd) 1160{ 1161 HARD_REG_SET set; 1162 unsigned int i, j; 1163 1164 CLEAR_HARD_REG_SET (set); 1165 1166 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1167 if (vd->e[i].oldest_regno == i) 1168 { 1169 if (vd->e[i].mode == VOIDmode) 1170 { 1171 if (vd->e[i].next_regno != INVALID_REGNUM) 1172 fprintf (stderr, "[%u] Bad next_regno for empty chain (%u)\n", 1173 i, vd->e[i].next_regno); 1174 continue; 1175 } 1176 1177 SET_HARD_REG_BIT (set, i); 1178 fprintf (stderr, "[%u %s] ", i, GET_MODE_NAME (vd->e[i].mode)); 1179 1180 for (j = vd->e[i].next_regno; 1181 j != INVALID_REGNUM; 1182 j = vd->e[j].next_regno) 1183 { 1184 if (TEST_HARD_REG_BIT (set, j)) 1185 { 1186 fprintf (stderr, "[%u] Loop in regno chain\n", j); 1187 return; 1188 } 1189 1190 if (vd->e[j].oldest_regno != i) 1191 { 1192 fprintf (stderr, "[%u] Bad oldest_regno (%u)\n", 1193 j, vd->e[j].oldest_regno); 1194 return; 1195 } 1196 SET_HARD_REG_BIT (set, j); 1197 fprintf (stderr, "[%u %s] ", j, GET_MODE_NAME (vd->e[j].mode)); 1198 } 1199 fputc ('\n', stderr); 1200 } 1201 1202 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1203 if (! TEST_HARD_REG_BIT (set, i) 1204 && (vd->e[i].mode != VOIDmode 1205 || vd->e[i].oldest_regno != i 1206 || vd->e[i].next_regno != INVALID_REGNUM)) 1207 fprintf (stderr, "[%u] Non-empty reg in chain (%s %u %i)\n", 1208 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1209 vd->e[i].next_regno); 1210} 1211 1212#ifdef ENABLE_CHECKING 1213static void 1214validate_value_data (struct value_data *vd) 1215{ 1216 HARD_REG_SET set; 1217 unsigned int i, j; 1218 1219 CLEAR_HARD_REG_SET (set); 1220 1221 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1222 if (vd->e[i].oldest_regno == i) 1223 { 1224 if (vd->e[i].mode == VOIDmode) 1225 { 1226 if (vd->e[i].next_regno != INVALID_REGNUM) 1227 internal_error ("validate_value_data: [%u] Bad next_regno for empty chain (%u)", 1228 i, vd->e[i].next_regno); 1229 continue; 1230 } 1231 1232 SET_HARD_REG_BIT (set, i); 1233 1234 for (j = vd->e[i].next_regno; 1235 j != INVALID_REGNUM; 1236 j = vd->e[j].next_regno) 1237 { 1238 if (TEST_HARD_REG_BIT (set, j)) 1239 internal_error ("validate_value_data: Loop in regno chain (%u)", 1240 j); 1241 if (vd->e[j].oldest_regno != i) 1242 internal_error ("validate_value_data: [%u] Bad oldest_regno (%u)", 1243 j, vd->e[j].oldest_regno); 1244 1245 SET_HARD_REG_BIT (set, j); 1246 } 1247 } 1248 1249 for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i) 1250 if (! TEST_HARD_REG_BIT (set, i) 1251 && (vd->e[i].mode != VOIDmode 1252 || vd->e[i].oldest_regno != i 1253 || vd->e[i].next_regno != INVALID_REGNUM)) 1254 internal_error ("validate_value_data: [%u] Non-empty reg in chain (%s %u %i)", 1255 i, GET_MODE_NAME (vd->e[i].mode), vd->e[i].oldest_regno, 1256 vd->e[i].next_regno); 1257} 1258#endif 1259 1260static bool 1261gate_handle_cprop (void) 1262{ 1263 return (optimize > 0 && (flag_cprop_registers)); 1264} 1265 1266 1267struct rtl_opt_pass pass_cprop_hardreg = 1268{ 1269 { 1270 RTL_PASS, 1271 "cprop_hardreg", /* name */ 1272 OPTGROUP_NONE, /* optinfo_flags */ 1273 gate_handle_cprop, /* gate */ 1274 copyprop_hardreg_forward, /* execute */ 1275 NULL, /* sub */ 1276 NULL, /* next */ 1277 0, /* static_pass_number */ 1278 TV_CPROP_REGISTERS, /* tv_id */ 1279 0, /* properties_required */ 1280 0, /* properties_provided */ 1281 0, /* properties_destroyed */ 1282 0, /* todo_flags_start */ 1283 TODO_df_finish 1284 | TODO_verify_rtl_sharing /* todo_flags_finish */ 1285 } 1286}; 1287