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