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