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