regmove.c revision 117395
1/* Move registers around to reduce number of move instructions needed. 2 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2002111-1307, USA. */ 21 22 23/* This module looks for cases where matching constraints would force 24 an instruction to need a reload, and this reload would be a register 25 to register move. It then attempts to change the registers used by the 26 instruction to avoid the move instruction. */ 27 28#include "config.h" 29#include "system.h" 30#include "rtl.h" /* stdio.h must precede rtl.h for FFS. */ 31#include "tm_p.h" 32#include "insn-config.h" 33#include "recog.h" 34#include "output.h" 35#include "regs.h" 36#include "hard-reg-set.h" 37#include "flags.h" 38#include "function.h" 39#include "expr.h" 40#include "basic-block.h" 41#include "except.h" 42#include "toplev.h" 43#include "reload.h" 44 45 46/* Turn STACK_GROWS_DOWNWARD into a boolean. */ 47#ifdef STACK_GROWS_DOWNWARD 48#undef STACK_GROWS_DOWNWARD 49#define STACK_GROWS_DOWNWARD 1 50#else 51#define STACK_GROWS_DOWNWARD 0 52#endif 53 54static int perhaps_ends_bb_p PARAMS ((rtx)); 55static int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx)); 56static void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx)); 57static void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx)); 58static void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int)); 59static int *regmove_bb_head; 60 61struct match { 62 int with[MAX_RECOG_OPERANDS]; 63 enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS]; 64 int commutative[MAX_RECOG_OPERANDS]; 65 int early_clobber[MAX_RECOG_OPERANDS]; 66}; 67 68static rtx discover_flags_reg PARAMS ((void)); 69static void mark_flags_life_zones PARAMS ((rtx)); 70static void flags_set_1 PARAMS ((rtx, rtx, void *)); 71 72static int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int)); 73static int find_matches PARAMS ((rtx, struct match *)); 74static void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx)); 75static int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *)) 76; 77static int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx)); 78static int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx)); 79static int regclass_compatible_p PARAMS ((int, int)); 80static int replacement_quality PARAMS ((rtx)); 81static int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *)); 82 83/* Return nonzero if registers with CLASS1 and CLASS2 can be merged without 84 causing too much register allocation problems. */ 85static int 86regclass_compatible_p (class0, class1) 87 int class0, class1; 88{ 89 return (class0 == class1 90 || (reg_class_subset_p (class0, class1) 91 && ! CLASS_LIKELY_SPILLED_P (class0)) 92 || (reg_class_subset_p (class1, class0) 93 && ! CLASS_LIKELY_SPILLED_P (class1))); 94} 95 96/* INC_INSN is an instruction that adds INCREMENT to REG. 97 Try to fold INC_INSN as a post/pre in/decrement into INSN. 98 Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src. 99 Return nonzero for success. */ 100static int 101try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre) 102 rtx reg, insn, inc_insn ,inc_insn_set; 103 HOST_WIDE_INT increment; 104 int pre; 105{ 106 enum rtx_code inc_code; 107 108 rtx pset = single_set (insn); 109 if (pset) 110 { 111 /* Can't use the size of SET_SRC, we might have something like 112 (sign_extend:SI (mem:QI ... */ 113 rtx use = find_use_as_address (pset, reg, 0); 114 if (use != 0 && use != (rtx) (size_t) 1) 115 { 116 int size = GET_MODE_SIZE (GET_MODE (use)); 117 if (0 118 || (HAVE_POST_INCREMENT 119 && pre == 0 && (inc_code = POST_INC, increment == size)) 120 || (HAVE_PRE_INCREMENT 121 && pre == 1 && (inc_code = PRE_INC, increment == size)) 122 || (HAVE_POST_DECREMENT 123 && pre == 0 && (inc_code = POST_DEC, increment == -size)) 124 || (HAVE_PRE_DECREMENT 125 && pre == 1 && (inc_code = PRE_DEC, increment == -size)) 126 ) 127 { 128 if (inc_insn_set) 129 validate_change 130 (inc_insn, 131 &SET_SRC (inc_insn_set), 132 XEXP (SET_SRC (inc_insn_set), 0), 1); 133 validate_change (insn, &XEXP (use, 0), 134 gen_rtx_fmt_e (inc_code, Pmode, reg), 1); 135 if (apply_change_group ()) 136 { 137 /* If there is a REG_DEAD note on this insn, we must 138 change this not to REG_UNUSED meaning that the register 139 is set, but the value is dead. Failure to do so will 140 result in a sched1 abort -- when it recomputes lifetime 141 information, the number of REG_DEAD notes will have 142 changed. */ 143 rtx note = find_reg_note (insn, REG_DEAD, reg); 144 if (note) 145 PUT_MODE (note, REG_UNUSED); 146 147 REG_NOTES (insn) 148 = gen_rtx_EXPR_LIST (REG_INC, 149 reg, REG_NOTES (insn)); 150 if (! inc_insn_set) 151 delete_insn (inc_insn); 152 return 1; 153 } 154 } 155 } 156 } 157 return 0; 158} 159 160/* Determine if the pattern generated by add_optab has a clobber, 161 such as might be issued for a flags hard register. To make the 162 code elsewhere simpler, we handle cc0 in this same framework. 163 164 Return the register if one was discovered. Return NULL_RTX if 165 if no flags were found. Return pc_rtx if we got confused. */ 166 167static rtx 168discover_flags_reg () 169{ 170 rtx tmp; 171 tmp = gen_rtx_REG (word_mode, 10000); 172 tmp = gen_add3_insn (tmp, tmp, GEN_INT (2)); 173 174 /* If we get something that isn't a simple set, or a 175 [(set ..) (clobber ..)], this whole function will go wrong. */ 176 if (GET_CODE (tmp) == SET) 177 return NULL_RTX; 178 else if (GET_CODE (tmp) == PARALLEL) 179 { 180 int found; 181 182 if (XVECLEN (tmp, 0) != 2) 183 return pc_rtx; 184 tmp = XVECEXP (tmp, 0, 1); 185 if (GET_CODE (tmp) != CLOBBER) 186 return pc_rtx; 187 tmp = XEXP (tmp, 0); 188 189 /* Don't do anything foolish if the md wanted to clobber a 190 scratch or something. We only care about hard regs. 191 Moreover we don't like the notion of subregs of hard regs. */ 192 if (GET_CODE (tmp) == SUBREG 193 && GET_CODE (SUBREG_REG (tmp)) == REG 194 && REGNO (SUBREG_REG (tmp)) < FIRST_PSEUDO_REGISTER) 195 return pc_rtx; 196 found = (GET_CODE (tmp) == REG && REGNO (tmp) < FIRST_PSEUDO_REGISTER); 197 198 return (found ? tmp : NULL_RTX); 199 } 200 201 return pc_rtx; 202} 203 204/* It is a tedious task identifying when the flags register is live and 205 when it is safe to optimize. Since we process the instruction stream 206 multiple times, locate and record these live zones by marking the 207 mode of the instructions -- 208 209 QImode is used on the instruction at which the flags becomes live. 210 211 HImode is used within the range (exclusive) that the flags are 212 live. Thus the user of the flags is not marked. 213 214 All other instructions are cleared to VOIDmode. */ 215 216/* Used to communicate with flags_set_1. */ 217static rtx flags_set_1_rtx; 218static int flags_set_1_set; 219 220static void 221mark_flags_life_zones (flags) 222 rtx flags; 223{ 224 int flags_regno; 225 int flags_nregs; 226 basic_block block; 227 228#ifdef HAVE_cc0 229 /* If we found a flags register on a cc0 host, bail. */ 230 if (flags == NULL_RTX) 231 flags = cc0_rtx; 232 else if (flags != cc0_rtx) 233 flags = pc_rtx; 234#endif 235 236 /* Simple cases first: if no flags, clear all modes. If confusing, 237 mark the entire function as being in a flags shadow. */ 238 if (flags == NULL_RTX || flags == pc_rtx) 239 { 240 enum machine_mode mode = (flags ? HImode : VOIDmode); 241 rtx insn; 242 for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) 243 PUT_MODE (insn, mode); 244 return; 245 } 246 247#ifdef HAVE_cc0 248 flags_regno = -1; 249 flags_nregs = 1; 250#else 251 flags_regno = REGNO (flags); 252 flags_nregs = HARD_REGNO_NREGS (flags_regno, GET_MODE (flags)); 253#endif 254 flags_set_1_rtx = flags; 255 256 /* Process each basic block. */ 257 FOR_EACH_BB_REVERSE (block) 258 { 259 rtx insn, end; 260 int live; 261 262 insn = block->head; 263 end = block->end; 264 265 /* Look out for the (unlikely) case of flags being live across 266 basic block boundaries. */ 267 live = 0; 268#ifndef HAVE_cc0 269 { 270 int i; 271 for (i = 0; i < flags_nregs; ++i) 272 live |= REGNO_REG_SET_P (block->global_live_at_start, 273 flags_regno + i); 274 } 275#endif 276 277 while (1) 278 { 279 /* Process liveness in reverse order of importance -- 280 alive, death, birth. This lets more important info 281 overwrite the mode of lesser info. */ 282 283 if (INSN_P (insn)) 284 { 285#ifdef HAVE_cc0 286 /* In the cc0 case, death is not marked in reg notes, 287 but is instead the mere use of cc0 when it is alive. */ 288 if (live && reg_mentioned_p (cc0_rtx, PATTERN (insn))) 289 live = 0; 290#else 291 /* In the hard reg case, we watch death notes. */ 292 if (live && find_regno_note (insn, REG_DEAD, flags_regno)) 293 live = 0; 294#endif 295 PUT_MODE (insn, (live ? HImode : VOIDmode)); 296 297 /* In either case, birth is denoted simply by it's presence 298 as the destination of a set. */ 299 flags_set_1_set = 0; 300 note_stores (PATTERN (insn), flags_set_1, NULL); 301 if (flags_set_1_set) 302 { 303 live = 1; 304 PUT_MODE (insn, QImode); 305 } 306 } 307 else 308 PUT_MODE (insn, (live ? HImode : VOIDmode)); 309 310 if (insn == end) 311 break; 312 insn = NEXT_INSN (insn); 313 } 314 } 315} 316 317/* A subroutine of mark_flags_life_zones, called through note_stores. */ 318 319static void 320flags_set_1 (x, pat, data) 321 rtx x, pat; 322 void *data ATTRIBUTE_UNUSED; 323{ 324 if (GET_CODE (pat) == SET 325 && reg_overlap_mentioned_p (x, flags_set_1_rtx)) 326 flags_set_1_set = 1; 327} 328 329static int *regno_src_regno; 330 331/* Indicate how good a choice REG (which appears as a source) is to replace 332 a destination register with. The higher the returned value, the better 333 the choice. The main objective is to avoid using a register that is 334 a candidate for tying to a hard register, since the output might in 335 turn be a candidate to be tied to a different hard register. */ 336static int 337replacement_quality (reg) 338 rtx reg; 339{ 340 int src_regno; 341 342 /* Bad if this isn't a register at all. */ 343 if (GET_CODE (reg) != REG) 344 return 0; 345 346 /* If this register is not meant to get a hard register, 347 it is a poor choice. */ 348 if (REG_LIVE_LENGTH (REGNO (reg)) < 0) 349 return 0; 350 351 src_regno = regno_src_regno[REGNO (reg)]; 352 353 /* If it was not copied from another register, it is fine. */ 354 if (src_regno < 0) 355 return 3; 356 357 /* Copied from a hard register? */ 358 if (src_regno < FIRST_PSEUDO_REGISTER) 359 return 1; 360 361 /* Copied from a pseudo register - not as bad as from a hard register, 362 yet still cumbersome, since the register live length will be lengthened 363 when the registers get tied. */ 364 return 2; 365} 366 367/* Return 1 if INSN might end a basic block. */ 368 369static int perhaps_ends_bb_p (insn) 370 rtx insn; 371{ 372 switch (GET_CODE (insn)) 373 { 374 case CODE_LABEL: 375 case JUMP_INSN: 376 /* These always end a basic block. */ 377 return 1; 378 379 case CALL_INSN: 380 /* A CALL_INSN might be the last insn of a basic block, if it is inside 381 an EH region or if there are nonlocal gotos. Note that this test is 382 very conservative. */ 383 if (nonlocal_goto_handler_labels) 384 return 1; 385 /* FALLTHRU */ 386 default: 387 return can_throw_internal (insn); 388 } 389} 390 391/* INSN is a copy from SRC to DEST, both registers, and SRC does not die 392 in INSN. 393 394 Search forward to see if SRC dies before either it or DEST is modified, 395 but don't scan past the end of a basic block. If so, we can replace SRC 396 with DEST and let SRC die in INSN. 397 398 This will reduce the number of registers live in that range and may enable 399 DEST to be tied to SRC, thus often saving one register in addition to a 400 register-register copy. */ 401 402static int 403optimize_reg_copy_1 (insn, dest, src) 404 rtx insn; 405 rtx dest; 406 rtx src; 407{ 408 rtx p, q; 409 rtx note; 410 rtx dest_death = 0; 411 int sregno = REGNO (src); 412 int dregno = REGNO (dest); 413 414 /* We don't want to mess with hard regs if register classes are small. */ 415 if (sregno == dregno 416 || (SMALL_REGISTER_CLASSES 417 && (sregno < FIRST_PSEUDO_REGISTER 418 || dregno < FIRST_PSEUDO_REGISTER)) 419 /* We don't see all updates to SP if they are in an auto-inc memory 420 reference, so we must disallow this optimization on them. */ 421 || sregno == STACK_POINTER_REGNUM || dregno == STACK_POINTER_REGNUM) 422 return 0; 423 424 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 425 { 426 /* ??? We can't scan past the end of a basic block without updating 427 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 428 if (perhaps_ends_bb_p (p)) 429 break; 430 else if (! INSN_P (p)) 431 continue; 432 433 if (reg_set_p (src, p) || reg_set_p (dest, p) 434 /* If SRC is an asm-declared register, it must not be replaced 435 in any asm. Unfortunately, the REG_EXPR tree for the asm 436 variable may be absent in the SRC rtx, so we can't check the 437 actual register declaration easily (the asm operand will have 438 it, though). To avoid complicating the test for a rare case, 439 we just don't perform register replacement for a hard reg 440 mentioned in an asm. */ 441 || (sregno < FIRST_PSEUDO_REGISTER 442 && asm_noperands (PATTERN (p)) >= 0 443 && reg_overlap_mentioned_p (src, PATTERN (p))) 444 /* Don't change a USE of a register. */ 445 || (GET_CODE (PATTERN (p)) == USE 446 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0)))) 447 break; 448 449 /* See if all of SRC dies in P. This test is slightly more 450 conservative than it needs to be. */ 451 if ((note = find_regno_note (p, REG_DEAD, sregno)) != 0 452 && GET_MODE (XEXP (note, 0)) == GET_MODE (src)) 453 { 454 int failed = 0; 455 int d_length = 0; 456 int s_length = 0; 457 int d_n_calls = 0; 458 int s_n_calls = 0; 459 460 /* We can do the optimization. Scan forward from INSN again, 461 replacing regs as we go. Set FAILED if a replacement can't 462 be done. In that case, we can't move the death note for SRC. 463 This should be rare. */ 464 465 /* Set to stop at next insn. */ 466 for (q = next_real_insn (insn); 467 q != next_real_insn (p); 468 q = next_real_insn (q)) 469 { 470 if (reg_overlap_mentioned_p (src, PATTERN (q))) 471 { 472 /* If SRC is a hard register, we might miss some 473 overlapping registers with validate_replace_rtx, 474 so we would have to undo it. We can't if DEST is 475 present in the insn, so fail in that combination 476 of cases. */ 477 if (sregno < FIRST_PSEUDO_REGISTER 478 && reg_mentioned_p (dest, PATTERN (q))) 479 failed = 1; 480 481 /* Replace all uses and make sure that the register 482 isn't still present. */ 483 else if (validate_replace_rtx (src, dest, q) 484 && (sregno >= FIRST_PSEUDO_REGISTER 485 || ! reg_overlap_mentioned_p (src, 486 PATTERN (q)))) 487 ; 488 else 489 { 490 validate_replace_rtx (dest, src, q); 491 failed = 1; 492 } 493 } 494 495 /* For SREGNO, count the total number of insns scanned. 496 For DREGNO, count the total number of insns scanned after 497 passing the death note for DREGNO. */ 498 s_length++; 499 if (dest_death) 500 d_length++; 501 502 /* If the insn in which SRC dies is a CALL_INSN, don't count it 503 as a call that has been crossed. Otherwise, count it. */ 504 if (q != p && GET_CODE (q) == CALL_INSN) 505 { 506 /* Similarly, total calls for SREGNO, total calls beyond 507 the death note for DREGNO. */ 508 s_n_calls++; 509 if (dest_death) 510 d_n_calls++; 511 } 512 513 /* If DEST dies here, remove the death note and save it for 514 later. Make sure ALL of DEST dies here; again, this is 515 overly conservative. */ 516 if (dest_death == 0 517 && (dest_death = find_regno_note (q, REG_DEAD, dregno)) != 0) 518 { 519 if (GET_MODE (XEXP (dest_death, 0)) != GET_MODE (dest)) 520 failed = 1, dest_death = 0; 521 else 522 remove_note (q, dest_death); 523 } 524 } 525 526 if (! failed) 527 { 528 /* These counters need to be updated if and only if we are 529 going to move the REG_DEAD note. */ 530 if (sregno >= FIRST_PSEUDO_REGISTER) 531 { 532 if (REG_LIVE_LENGTH (sregno) >= 0) 533 { 534 REG_LIVE_LENGTH (sregno) -= s_length; 535 /* REG_LIVE_LENGTH is only an approximation after 536 combine if sched is not run, so make sure that we 537 still have a reasonable value. */ 538 if (REG_LIVE_LENGTH (sregno) < 2) 539 REG_LIVE_LENGTH (sregno) = 2; 540 } 541 542 REG_N_CALLS_CROSSED (sregno) -= s_n_calls; 543 } 544 545 /* Move death note of SRC from P to INSN. */ 546 remove_note (p, note); 547 XEXP (note, 1) = REG_NOTES (insn); 548 REG_NOTES (insn) = note; 549 } 550 551 /* DEST is also dead if INSN has a REG_UNUSED note for DEST. */ 552 if (! dest_death 553 && (dest_death = find_regno_note (insn, REG_UNUSED, dregno))) 554 { 555 PUT_REG_NOTE_KIND (dest_death, REG_DEAD); 556 remove_note (insn, dest_death); 557 } 558 559 /* Put death note of DEST on P if we saw it die. */ 560 if (dest_death) 561 { 562 XEXP (dest_death, 1) = REG_NOTES (p); 563 REG_NOTES (p) = dest_death; 564 565 if (dregno >= FIRST_PSEUDO_REGISTER) 566 { 567 /* If and only if we are moving the death note for DREGNO, 568 then we need to update its counters. */ 569 if (REG_LIVE_LENGTH (dregno) >= 0) 570 REG_LIVE_LENGTH (dregno) += d_length; 571 REG_N_CALLS_CROSSED (dregno) += d_n_calls; 572 } 573 } 574 575 return ! failed; 576 } 577 578 /* If SRC is a hard register which is set or killed in some other 579 way, we can't do this optimization. */ 580 else if (sregno < FIRST_PSEUDO_REGISTER 581 && dead_or_set_p (p, src)) 582 break; 583 } 584 return 0; 585} 586 587/* INSN is a copy of SRC to DEST, in which SRC dies. See if we now have 588 a sequence of insns that modify DEST followed by an insn that sets 589 SRC to DEST in which DEST dies, with no prior modification of DEST. 590 (There is no need to check if the insns in between actually modify 591 DEST. We should not have cases where DEST is not modified, but 592 the optimization is safe if no such modification is detected.) 593 In that case, we can replace all uses of DEST, starting with INSN and 594 ending with the set of SRC to DEST, with SRC. We do not do this 595 optimization if a CALL_INSN is crossed unless SRC already crosses a 596 call or if DEST dies before the copy back to SRC. 597 598 It is assumed that DEST and SRC are pseudos; it is too complicated to do 599 this for hard registers since the substitutions we may make might fail. */ 600 601static void 602optimize_reg_copy_2 (insn, dest, src) 603 rtx insn; 604 rtx dest; 605 rtx src; 606{ 607 rtx p, q; 608 rtx set; 609 int sregno = REGNO (src); 610 int dregno = REGNO (dest); 611 612 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 613 { 614 /* ??? We can't scan past the end of a basic block without updating 615 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 616 if (perhaps_ends_bb_p (p)) 617 break; 618 else if (! INSN_P (p)) 619 continue; 620 621 set = single_set (p); 622 if (set && SET_SRC (set) == dest && SET_DEST (set) == src 623 && find_reg_note (p, REG_DEAD, dest)) 624 { 625 /* We can do the optimization. Scan forward from INSN again, 626 replacing regs as we go. */ 627 628 /* Set to stop at next insn. */ 629 for (q = insn; q != NEXT_INSN (p); q = NEXT_INSN (q)) 630 if (INSN_P (q)) 631 { 632 if (reg_mentioned_p (dest, PATTERN (q))) 633 PATTERN (q) = replace_rtx (PATTERN (q), dest, src); 634 635 636 if (GET_CODE (q) == CALL_INSN) 637 { 638 REG_N_CALLS_CROSSED (dregno)--; 639 REG_N_CALLS_CROSSED (sregno)++; 640 } 641 } 642 643 remove_note (p, find_reg_note (p, REG_DEAD, dest)); 644 REG_N_DEATHS (dregno)--; 645 remove_note (insn, find_reg_note (insn, REG_DEAD, src)); 646 REG_N_DEATHS (sregno)--; 647 return; 648 } 649 650 if (reg_set_p (src, p) 651 || find_reg_note (p, REG_DEAD, dest) 652 || (GET_CODE (p) == CALL_INSN && REG_N_CALLS_CROSSED (sregno) == 0)) 653 break; 654 } 655} 656/* INSN is a ZERO_EXTEND or SIGN_EXTEND of SRC to DEST. 657 Look if SRC dies there, and if it is only set once, by loading 658 it from memory. If so, try to encorporate the zero/sign extension 659 into the memory read, change SRC to the mode of DEST, and alter 660 the remaining accesses to use the appropriate SUBREG. This allows 661 SRC and DEST to be tied later. */ 662static void 663optimize_reg_copy_3 (insn, dest, src) 664 rtx insn; 665 rtx dest; 666 rtx src; 667{ 668 rtx src_reg = XEXP (src, 0); 669 int src_no = REGNO (src_reg); 670 int dst_no = REGNO (dest); 671 rtx p, set, subreg; 672 enum machine_mode old_mode; 673 674 if (src_no < FIRST_PSEUDO_REGISTER 675 || dst_no < FIRST_PSEUDO_REGISTER 676 || ! find_reg_note (insn, REG_DEAD, src_reg) 677 || REG_N_DEATHS (src_no) != 1 678 || REG_N_SETS (src_no) != 1) 679 return; 680 for (p = PREV_INSN (insn); p && ! reg_set_p (src_reg, p); p = PREV_INSN (p)) 681 /* ??? We can't scan past the end of a basic block without updating 682 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 683 if (perhaps_ends_bb_p (p)) 684 break; 685 686 if (! p) 687 return; 688 689 if (! (set = single_set (p)) 690 || GET_CODE (SET_SRC (set)) != MEM 691 /* If there's a REG_EQUIV note, this must be an insn that loads an 692 argument. Prefer keeping the note over doing this optimization. */ 693 || find_reg_note (p, REG_EQUIV, NULL_RTX) 694 || SET_DEST (set) != src_reg) 695 return; 696 697 /* Be conserative: although this optimization is also valid for 698 volatile memory references, that could cause trouble in later passes. */ 699 if (MEM_VOLATILE_P (SET_SRC (set))) 700 return; 701 702 /* Do not use a SUBREG to truncate from one mode to another if truncation 703 is not a nop. */ 704 if (GET_MODE_BITSIZE (GET_MODE (src_reg)) <= GET_MODE_BITSIZE (GET_MODE (src)) 705 && !TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (src)), 706 GET_MODE_BITSIZE (GET_MODE (src_reg)))) 707 return; 708 709 old_mode = GET_MODE (src_reg); 710 PUT_MODE (src_reg, GET_MODE (src)); 711 XEXP (src, 0) = SET_SRC (set); 712 713 /* Include this change in the group so that it's easily undone if 714 one of the changes in the group is invalid. */ 715 validate_change (p, &SET_SRC (set), src, 1); 716 717 /* Now walk forward making additional replacements. We want to be able 718 to undo all the changes if a later substitution fails. */ 719 subreg = gen_lowpart_SUBREG (old_mode, src_reg); 720 while (p = NEXT_INSN (p), p != insn) 721 { 722 if (! INSN_P (p)) 723 continue; 724 725 /* Make a tenative change. */ 726 validate_replace_rtx_group (src_reg, subreg, p); 727 } 728 729 validate_replace_rtx_group (src, src_reg, insn); 730 731 /* Now see if all the changes are valid. */ 732 if (! apply_change_group ()) 733 { 734 /* One or more changes were no good. Back out everything. */ 735 PUT_MODE (src_reg, old_mode); 736 XEXP (src, 0) = src_reg; 737 } 738 else 739 { 740 rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX); 741 if (note) 742 remove_note (p, note); 743 } 744} 745 746 747/* If we were not able to update the users of src to use dest directly, try 748 instead moving the value to dest directly before the operation. */ 749 750static void 751copy_src_to_dest (insn, src, dest, old_max_uid) 752 rtx insn; 753 rtx src; 754 rtx dest; 755 int old_max_uid; 756{ 757 rtx seq; 758 rtx link; 759 rtx next; 760 rtx set; 761 rtx move_insn; 762 rtx *p_insn_notes; 763 rtx *p_move_notes; 764 int src_regno; 765 int dest_regno; 766 int bb; 767 int insn_uid; 768 int move_uid; 769 770 /* A REG_LIVE_LENGTH of -1 indicates the register is equivalent to a constant 771 or memory location and is used infrequently; a REG_LIVE_LENGTH of -2 is 772 parameter when there is no frame pointer that is not allocated a register. 773 For now, we just reject them, rather than incrementing the live length. */ 774 775 if (GET_CODE (src) == REG 776 && REG_LIVE_LENGTH (REGNO (src)) > 0 777 && GET_CODE (dest) == REG 778 && !RTX_UNCHANGING_P (dest) 779 && REG_LIVE_LENGTH (REGNO (dest)) > 0 780 && (set = single_set (insn)) != NULL_RTX 781 && !reg_mentioned_p (dest, SET_SRC (set)) 782 && GET_MODE (src) == GET_MODE (dest)) 783 { 784 int old_num_regs = reg_rtx_no; 785 786 /* Generate the src->dest move. */ 787 start_sequence (); 788 emit_move_insn (dest, src); 789 seq = get_insns (); 790 end_sequence (); 791 /* If this sequence uses new registers, we may not use it. */ 792 if (old_num_regs != reg_rtx_no 793 || ! validate_replace_rtx (src, dest, insn)) 794 { 795 /* We have to restore reg_rtx_no to its old value, lest 796 recompute_reg_usage will try to compute the usage of the 797 new regs, yet reg_n_info is not valid for them. */ 798 reg_rtx_no = old_num_regs; 799 return; 800 } 801 emit_insn_before (seq, insn); 802 move_insn = PREV_INSN (insn); 803 p_move_notes = ®_NOTES (move_insn); 804 p_insn_notes = ®_NOTES (insn); 805 806 /* Move any notes mentioning src to the move instruction. */ 807 for (link = REG_NOTES (insn); link != NULL_RTX; link = next) 808 { 809 next = XEXP (link, 1); 810 if (XEXP (link, 0) == src) 811 { 812 *p_move_notes = link; 813 p_move_notes = &XEXP (link, 1); 814 } 815 else 816 { 817 *p_insn_notes = link; 818 p_insn_notes = &XEXP (link, 1); 819 } 820 } 821 822 *p_move_notes = NULL_RTX; 823 *p_insn_notes = NULL_RTX; 824 825 /* Is the insn the head of a basic block? If so extend it. */ 826 insn_uid = INSN_UID (insn); 827 move_uid = INSN_UID (move_insn); 828 if (insn_uid < old_max_uid) 829 { 830 bb = regmove_bb_head[insn_uid]; 831 if (bb >= 0) 832 { 833 BLOCK_HEAD (bb) = move_insn; 834 regmove_bb_head[insn_uid] = -1; 835 } 836 } 837 838 /* Update the various register tables. */ 839 dest_regno = REGNO (dest); 840 REG_N_SETS (dest_regno) ++; 841 REG_LIVE_LENGTH (dest_regno)++; 842 if (REGNO_FIRST_UID (dest_regno) == insn_uid) 843 REGNO_FIRST_UID (dest_regno) = move_uid; 844 845 src_regno = REGNO (src); 846 if (! find_reg_note (move_insn, REG_DEAD, src)) 847 REG_LIVE_LENGTH (src_regno)++; 848 849 if (REGNO_FIRST_UID (src_regno) == insn_uid) 850 REGNO_FIRST_UID (src_regno) = move_uid; 851 852 if (REGNO_LAST_UID (src_regno) == insn_uid) 853 REGNO_LAST_UID (src_regno) = move_uid; 854 855 if (REGNO_LAST_NOTE_UID (src_regno) == insn_uid) 856 REGNO_LAST_NOTE_UID (src_regno) = move_uid; 857 } 858} 859 860 861/* Return whether REG is set in only one location, and is set to a 862 constant, but is set in a different basic block from INSN (an 863 instructions which uses REG). In this case REG is equivalent to a 864 constant, and we don't want to break that equivalence, because that 865 may increase register pressure and make reload harder. If REG is 866 set in the same basic block as INSN, we don't worry about it, 867 because we'll probably need a register anyhow (??? but what if REG 868 is used in a different basic block as well as this one?). FIRST is 869 the first insn in the function. */ 870 871static int 872reg_is_remote_constant_p (reg, insn, first) 873 rtx reg; 874 rtx insn; 875 rtx first; 876{ 877 rtx p; 878 879 if (REG_N_SETS (REGNO (reg)) != 1) 880 return 0; 881 882 /* Look for the set. */ 883 for (p = LOG_LINKS (insn); p; p = XEXP (p, 1)) 884 { 885 rtx s; 886 887 if (REG_NOTE_KIND (p) != 0) 888 continue; 889 s = single_set (XEXP (p, 0)); 890 if (s != 0 891 && GET_CODE (SET_DEST (s)) == REG 892 && REGNO (SET_DEST (s)) == REGNO (reg)) 893 { 894 /* The register is set in the same basic block. */ 895 return 0; 896 } 897 } 898 899 for (p = first; p && p != insn; p = NEXT_INSN (p)) 900 { 901 rtx s; 902 903 if (! INSN_P (p)) 904 continue; 905 s = single_set (p); 906 if (s != 0 907 && GET_CODE (SET_DEST (s)) == REG 908 && REGNO (SET_DEST (s)) == REGNO (reg)) 909 { 910 /* This is the instruction which sets REG. If there is a 911 REG_EQUAL note, then REG is equivalent to a constant. */ 912 if (find_reg_note (p, REG_EQUAL, NULL_RTX)) 913 return 1; 914 return 0; 915 } 916 } 917 918 return 0; 919} 920 921/* INSN is adding a CONST_INT to a REG. We search backwards looking for 922 another add immediate instruction with the same source and dest registers, 923 and if we find one, we change INSN to an increment, and return 1. If 924 no changes are made, we return 0. 925 926 This changes 927 (set (reg100) (plus reg1 offset1)) 928 ... 929 (set (reg100) (plus reg1 offset2)) 930 to 931 (set (reg100) (plus reg1 offset1)) 932 ... 933 (set (reg100) (plus reg100 offset2-offset1)) */ 934 935/* ??? What does this comment mean? */ 936/* cse disrupts preincrement / postdecrement squences when it finds a 937 hard register as ultimate source, like the frame pointer. */ 938 939static int 940fixup_match_2 (insn, dst, src, offset, regmove_dump_file) 941 rtx insn, dst, src, offset; 942 FILE *regmove_dump_file; 943{ 944 rtx p, dst_death = 0; 945 int length, num_calls = 0; 946 947 /* If SRC dies in INSN, we'd have to move the death note. This is 948 considered to be very unlikely, so we just skip the optimization 949 in this case. */ 950 if (find_regno_note (insn, REG_DEAD, REGNO (src))) 951 return 0; 952 953 /* Scan backward to find the first instruction that sets DST. */ 954 955 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p)) 956 { 957 rtx pset; 958 959 /* ??? We can't scan past the end of a basic block without updating 960 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 961 if (perhaps_ends_bb_p (p)) 962 break; 963 else if (! INSN_P (p)) 964 continue; 965 966 if (find_regno_note (p, REG_DEAD, REGNO (dst))) 967 dst_death = p; 968 if (! dst_death) 969 length++; 970 971 pset = single_set (p); 972 if (pset && SET_DEST (pset) == dst 973 && GET_CODE (SET_SRC (pset)) == PLUS 974 && XEXP (SET_SRC (pset), 0) == src 975 && GET_CODE (XEXP (SET_SRC (pset), 1)) == CONST_INT) 976 { 977 HOST_WIDE_INT newconst 978 = INTVAL (offset) - INTVAL (XEXP (SET_SRC (pset), 1)); 979 rtx add = gen_add3_insn (dst, dst, GEN_INT (newconst)); 980 981 if (add && validate_change (insn, &PATTERN (insn), add, 0)) 982 { 983 /* Remove the death note for DST from DST_DEATH. */ 984 if (dst_death) 985 { 986 remove_death (REGNO (dst), dst_death); 987 REG_LIVE_LENGTH (REGNO (dst)) += length; 988 REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls; 989 } 990 991 if (regmove_dump_file) 992 fprintf (regmove_dump_file, 993 "Fixed operand of insn %d.\n", 994 INSN_UID (insn)); 995 996#ifdef AUTO_INC_DEC 997 for (p = PREV_INSN (insn); p; p = PREV_INSN (p)) 998 { 999 if (GET_CODE (p) == CODE_LABEL 1000 || GET_CODE (p) == JUMP_INSN) 1001 break; 1002 if (! INSN_P (p)) 1003 continue; 1004 if (reg_overlap_mentioned_p (dst, PATTERN (p))) 1005 { 1006 if (try_auto_increment (p, insn, 0, dst, newconst, 0)) 1007 return 1; 1008 break; 1009 } 1010 } 1011 for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 1012 { 1013 if (GET_CODE (p) == CODE_LABEL 1014 || GET_CODE (p) == JUMP_INSN) 1015 break; 1016 if (! INSN_P (p)) 1017 continue; 1018 if (reg_overlap_mentioned_p (dst, PATTERN (p))) 1019 { 1020 try_auto_increment (p, insn, 0, dst, newconst, 1); 1021 break; 1022 } 1023 } 1024#endif 1025 return 1; 1026 } 1027 } 1028 1029 if (reg_set_p (dst, PATTERN (p))) 1030 break; 1031 1032 /* If we have passed a call instruction, and the 1033 pseudo-reg SRC is not already live across a call, 1034 then don't perform the optimization. */ 1035 /* reg_set_p is overly conservative for CALL_INSNS, thinks that all 1036 hard regs are clobbered. Thus, we only use it for src for 1037 non-call insns. */ 1038 if (GET_CODE (p) == CALL_INSN) 1039 { 1040 if (! dst_death) 1041 num_calls++; 1042 1043 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0) 1044 break; 1045 1046 if (call_used_regs [REGNO (dst)] 1047 || find_reg_fusage (p, CLOBBER, dst)) 1048 break; 1049 } 1050 else if (reg_set_p (src, PATTERN (p))) 1051 break; 1052 } 1053 1054 return 0; 1055} 1056 1057/* Main entry for the register move optimization. 1058 F is the first instruction. 1059 NREGS is one plus the highest pseudo-reg number used in the instruction. 1060 REGMOVE_DUMP_FILE is a stream for output of a trace of actions taken 1061 (or 0 if none should be output). */ 1062 1063void 1064regmove_optimize (f, nregs, regmove_dump_file) 1065 rtx f; 1066 int nregs; 1067 FILE *regmove_dump_file; 1068{ 1069 int old_max_uid = get_max_uid (); 1070 rtx insn; 1071 struct match match; 1072 int pass; 1073 int i; 1074 rtx copy_src, copy_dst; 1075 basic_block bb; 1076 1077 /* ??? Hack. Regmove doesn't examine the CFG, and gets mightily 1078 confused by non-call exceptions ending blocks. */ 1079 if (flag_non_call_exceptions) 1080 return; 1081 1082 /* Find out where a potential flags register is live, and so that we 1083 can supress some optimizations in those zones. */ 1084 mark_flags_life_zones (discover_flags_reg ()); 1085 1086 regno_src_regno = (int *) xmalloc (sizeof *regno_src_regno * nregs); 1087 for (i = nregs; --i >= 0; ) regno_src_regno[i] = -1; 1088 1089 regmove_bb_head = (int *) xmalloc (sizeof (int) * (old_max_uid + 1)); 1090 for (i = old_max_uid; i >= 0; i--) regmove_bb_head[i] = -1; 1091 FOR_EACH_BB (bb) 1092 regmove_bb_head[INSN_UID (bb->head)] = bb->index; 1093 1094 /* A forward/backward pass. Replace output operands with input operands. */ 1095 1096 for (pass = 0; pass <= 2; pass++) 1097 { 1098 if (! flag_regmove && pass >= flag_expensive_optimizations) 1099 goto done; 1100 1101 if (regmove_dump_file) 1102 fprintf (regmove_dump_file, "Starting %s pass...\n", 1103 pass ? "backward" : "forward"); 1104 1105 for (insn = pass ? get_last_insn () : f; insn; 1106 insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn)) 1107 { 1108 rtx set; 1109 int op_no, match_no; 1110 1111 set = single_set (insn); 1112 if (! set) 1113 continue; 1114 1115 if (flag_expensive_optimizations && ! pass 1116 && (GET_CODE (SET_SRC (set)) == SIGN_EXTEND 1117 || GET_CODE (SET_SRC (set)) == ZERO_EXTEND) 1118 && GET_CODE (XEXP (SET_SRC (set), 0)) == REG 1119 && GET_CODE (SET_DEST (set)) == REG) 1120 optimize_reg_copy_3 (insn, SET_DEST (set), SET_SRC (set)); 1121 1122 if (flag_expensive_optimizations && ! pass 1123 && GET_CODE (SET_SRC (set)) == REG 1124 && GET_CODE (SET_DEST (set)) == REG) 1125 { 1126 /* If this is a register-register copy where SRC is not dead, 1127 see if we can optimize it. If this optimization succeeds, 1128 it will become a copy where SRC is dead. */ 1129 if ((find_reg_note (insn, REG_DEAD, SET_SRC (set)) 1130 || optimize_reg_copy_1 (insn, SET_DEST (set), SET_SRC (set))) 1131 && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) 1132 { 1133 /* Similarly for a pseudo-pseudo copy when SRC is dead. */ 1134 if (REGNO (SET_SRC (set)) >= FIRST_PSEUDO_REGISTER) 1135 optimize_reg_copy_2 (insn, SET_DEST (set), SET_SRC (set)); 1136 if (regno_src_regno[REGNO (SET_DEST (set))] < 0 1137 && SET_SRC (set) != SET_DEST (set)) 1138 { 1139 int srcregno = REGNO (SET_SRC (set)); 1140 if (regno_src_regno[srcregno] >= 0) 1141 srcregno = regno_src_regno[srcregno]; 1142 regno_src_regno[REGNO (SET_DEST (set))] = srcregno; 1143 } 1144 } 1145 } 1146 if (! flag_regmove) 1147 continue; 1148 1149 if (! find_matches (insn, &match)) 1150 continue; 1151 1152 /* Now scan through the operands looking for a source operand 1153 which is supposed to match the destination operand. 1154 Then scan forward for an instruction which uses the dest 1155 operand. 1156 If it dies there, then replace the dest in both operands with 1157 the source operand. */ 1158 1159 for (op_no = 0; op_no < recog_data.n_operands; op_no++) 1160 { 1161 rtx src, dst, src_subreg; 1162 enum reg_class src_class, dst_class; 1163 1164 match_no = match.with[op_no]; 1165 1166 /* Nothing to do if the two operands aren't supposed to match. */ 1167 if (match_no < 0) 1168 continue; 1169 1170 src = recog_data.operand[op_no]; 1171 dst = recog_data.operand[match_no]; 1172 1173 if (GET_CODE (src) != REG) 1174 continue; 1175 1176 src_subreg = src; 1177 if (GET_CODE (dst) == SUBREG 1178 && GET_MODE_SIZE (GET_MODE (dst)) 1179 >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst)))) 1180 { 1181 src_subreg 1182 = gen_rtx_SUBREG (GET_MODE (SUBREG_REG (dst)), 1183 src, SUBREG_BYTE (dst)); 1184 dst = SUBREG_REG (dst); 1185 } 1186 if (GET_CODE (dst) != REG 1187 || REGNO (dst) < FIRST_PSEUDO_REGISTER) 1188 continue; 1189 1190 if (REGNO (src) < FIRST_PSEUDO_REGISTER) 1191 { 1192 if (match.commutative[op_no] < op_no) 1193 regno_src_regno[REGNO (dst)] = REGNO (src); 1194 continue; 1195 } 1196 1197 if (REG_LIVE_LENGTH (REGNO (src)) < 0) 1198 continue; 1199 1200 /* op_no/src must be a read-only operand, and 1201 match_operand/dst must be a write-only operand. */ 1202 if (match.use[op_no] != READ 1203 || match.use[match_no] != WRITE) 1204 continue; 1205 1206 if (match.early_clobber[match_no] 1207 && count_occurrences (PATTERN (insn), src, 0) > 1) 1208 continue; 1209 1210 /* Make sure match_operand is the destination. */ 1211 if (recog_data.operand[match_no] != SET_DEST (set)) 1212 continue; 1213 1214 /* If the operands already match, then there is nothing to do. */ 1215 if (operands_match_p (src, dst)) 1216 continue; 1217 1218 /* But in the commutative case, we might find a better match. */ 1219 if (match.commutative[op_no] >= 0) 1220 { 1221 rtx comm = recog_data.operand[match.commutative[op_no]]; 1222 if (operands_match_p (comm, dst) 1223 && (replacement_quality (comm) 1224 >= replacement_quality (src))) 1225 continue; 1226 } 1227 1228 src_class = reg_preferred_class (REGNO (src)); 1229 dst_class = reg_preferred_class (REGNO (dst)); 1230 if (! regclass_compatible_p (src_class, dst_class)) 1231 continue; 1232 1233 if (GET_MODE (src) != GET_MODE (dst)) 1234 continue; 1235 1236 if (fixup_match_1 (insn, set, src, src_subreg, dst, pass, 1237 op_no, match_no, 1238 regmove_dump_file)) 1239 break; 1240 } 1241 } 1242 } 1243 1244 /* A backward pass. Replace input operands with output operands. */ 1245 1246 if (regmove_dump_file) 1247 fprintf (regmove_dump_file, "Starting backward pass...\n"); 1248 1249 for (insn = get_last_insn (); insn; insn = PREV_INSN (insn)) 1250 { 1251 if (INSN_P (insn)) 1252 { 1253 int op_no, match_no; 1254 int success = 0; 1255 1256 if (! find_matches (insn, &match)) 1257 continue; 1258 1259 /* Now scan through the operands looking for a destination operand 1260 which is supposed to match a source operand. 1261 Then scan backward for an instruction which sets the source 1262 operand. If safe, then replace the source operand with the 1263 dest operand in both instructions. */ 1264 1265 copy_src = NULL_RTX; 1266 copy_dst = NULL_RTX; 1267 for (op_no = 0; op_no < recog_data.n_operands; op_no++) 1268 { 1269 rtx set, p, src, dst; 1270 rtx src_note, dst_note; 1271 int num_calls = 0; 1272 enum reg_class src_class, dst_class; 1273 int length; 1274 1275 match_no = match.with[op_no]; 1276 1277 /* Nothing to do if the two operands aren't supposed to match. */ 1278 if (match_no < 0) 1279 continue; 1280 1281 dst = recog_data.operand[match_no]; 1282 src = recog_data.operand[op_no]; 1283 1284 if (GET_CODE (src) != REG) 1285 continue; 1286 1287 if (GET_CODE (dst) != REG 1288 || REGNO (dst) < FIRST_PSEUDO_REGISTER 1289 || REG_LIVE_LENGTH (REGNO (dst)) < 0 1290 || RTX_UNCHANGING_P (dst)) 1291 continue; 1292 1293 /* If the operands already match, then there is nothing to do. */ 1294 if (operands_match_p (src, dst)) 1295 continue; 1296 1297 if (match.commutative[op_no] >= 0) 1298 { 1299 rtx comm = recog_data.operand[match.commutative[op_no]]; 1300 if (operands_match_p (comm, dst)) 1301 continue; 1302 } 1303 1304 set = single_set (insn); 1305 if (! set) 1306 continue; 1307 1308 /* Note that single_set ignores parts of a parallel set for 1309 which one of the destinations is REG_UNUSED. We can't 1310 handle that here, since we can wind up rewriting things 1311 such that a single register is set twice within a single 1312 parallel. */ 1313 if (reg_set_p (src, insn)) 1314 continue; 1315 1316 /* match_no/dst must be a write-only operand, and 1317 operand_operand/src must be a read-only operand. */ 1318 if (match.use[op_no] != READ 1319 || match.use[match_no] != WRITE) 1320 continue; 1321 1322 if (match.early_clobber[match_no] 1323 && count_occurrences (PATTERN (insn), src, 0) > 1) 1324 continue; 1325 1326 /* Make sure match_no is the destination. */ 1327 if (recog_data.operand[match_no] != SET_DEST (set)) 1328 continue; 1329 1330 if (REGNO (src) < FIRST_PSEUDO_REGISTER) 1331 { 1332 if (GET_CODE (SET_SRC (set)) == PLUS 1333 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT 1334 && XEXP (SET_SRC (set), 0) == src 1335 && fixup_match_2 (insn, dst, src, 1336 XEXP (SET_SRC (set), 1), 1337 regmove_dump_file)) 1338 break; 1339 continue; 1340 } 1341 src_class = reg_preferred_class (REGNO (src)); 1342 dst_class = reg_preferred_class (REGNO (dst)); 1343 1344 if (! (src_note = find_reg_note (insn, REG_DEAD, src))) 1345 { 1346 /* We used to force the copy here like in other cases, but 1347 it produces worse code, as it eliminates no copy 1348 instructions and the copy emitted will be produced by 1349 reload anyway. On patterns with multiple alternatives, 1350 there may be better sollution availble. 1351 1352 In particular this change produced slower code for numeric 1353 i387 programs. */ 1354 1355 continue; 1356 } 1357 1358 if (! regclass_compatible_p (src_class, dst_class)) 1359 { 1360 if (!copy_src) 1361 { 1362 copy_src = src; 1363 copy_dst = dst; 1364 } 1365 continue; 1366 } 1367 1368 /* Can not modify an earlier insn to set dst if this insn 1369 uses an old value in the source. */ 1370 if (reg_overlap_mentioned_p (dst, SET_SRC (set))) 1371 { 1372 if (!copy_src) 1373 { 1374 copy_src = src; 1375 copy_dst = dst; 1376 } 1377 continue; 1378 } 1379 1380 /* If src is set once in a different basic block, 1381 and is set equal to a constant, then do not use 1382 it for this optimization, as this would make it 1383 no longer equivalent to a constant. */ 1384 1385 if (reg_is_remote_constant_p (src, insn, f)) 1386 { 1387 if (!copy_src) 1388 { 1389 copy_src = src; 1390 copy_dst = dst; 1391 } 1392 continue; 1393 } 1394 1395 1396 if (regmove_dump_file) 1397 fprintf (regmove_dump_file, 1398 "Could fix operand %d of insn %d matching operand %d.\n", 1399 op_no, INSN_UID (insn), match_no); 1400 1401 /* Scan backward to find the first instruction that uses 1402 the input operand. If the operand is set here, then 1403 replace it in both instructions with match_no. */ 1404 1405 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p)) 1406 { 1407 rtx pset; 1408 1409 /* ??? We can't scan past the end of a basic block without 1410 updating the register lifetime info 1411 (REG_DEAD/basic_block_live_at_start). */ 1412 if (perhaps_ends_bb_p (p)) 1413 break; 1414 else if (! INSN_P (p)) 1415 continue; 1416 1417 length++; 1418 1419 /* ??? See if all of SRC is set in P. This test is much 1420 more conservative than it needs to be. */ 1421 pset = single_set (p); 1422 if (pset && SET_DEST (pset) == src) 1423 { 1424 /* We use validate_replace_rtx, in case there 1425 are multiple identical source operands. All of 1426 them have to be changed at the same time. */ 1427 if (validate_replace_rtx (src, dst, insn)) 1428 { 1429 if (validate_change (p, &SET_DEST (pset), 1430 dst, 0)) 1431 success = 1; 1432 else 1433 { 1434 /* Change all source operands back. 1435 This modifies the dst as a side-effect. */ 1436 validate_replace_rtx (dst, src, insn); 1437 /* Now make sure the dst is right. */ 1438 validate_change (insn, 1439 recog_data.operand_loc[match_no], 1440 dst, 0); 1441 } 1442 } 1443 break; 1444 } 1445 1446 if (reg_overlap_mentioned_p (src, PATTERN (p)) 1447 || reg_overlap_mentioned_p (dst, PATTERN (p))) 1448 break; 1449 1450 /* If we have passed a call instruction, and the 1451 pseudo-reg DST is not already live across a call, 1452 then don't perform the optimization. */ 1453 if (GET_CODE (p) == CALL_INSN) 1454 { 1455 num_calls++; 1456 1457 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0) 1458 break; 1459 } 1460 } 1461 1462 if (success) 1463 { 1464 int dstno, srcno; 1465 1466 /* Remove the death note for SRC from INSN. */ 1467 remove_note (insn, src_note); 1468 /* Move the death note for SRC to P if it is used 1469 there. */ 1470 if (reg_overlap_mentioned_p (src, PATTERN (p))) 1471 { 1472 XEXP (src_note, 1) = REG_NOTES (p); 1473 REG_NOTES (p) = src_note; 1474 } 1475 /* If there is a REG_DEAD note for DST on P, then remove 1476 it, because DST is now set there. */ 1477 if ((dst_note = find_reg_note (p, REG_DEAD, dst))) 1478 remove_note (p, dst_note); 1479 1480 dstno = REGNO (dst); 1481 srcno = REGNO (src); 1482 1483 REG_N_SETS (dstno)++; 1484 REG_N_SETS (srcno)--; 1485 1486 REG_N_CALLS_CROSSED (dstno) += num_calls; 1487 REG_N_CALLS_CROSSED (srcno) -= num_calls; 1488 1489 REG_LIVE_LENGTH (dstno) += length; 1490 if (REG_LIVE_LENGTH (srcno) >= 0) 1491 { 1492 REG_LIVE_LENGTH (srcno) -= length; 1493 /* REG_LIVE_LENGTH is only an approximation after 1494 combine if sched is not run, so make sure that we 1495 still have a reasonable value. */ 1496 if (REG_LIVE_LENGTH (srcno) < 2) 1497 REG_LIVE_LENGTH (srcno) = 2; 1498 } 1499 1500 if (regmove_dump_file) 1501 fprintf (regmove_dump_file, 1502 "Fixed operand %d of insn %d matching operand %d.\n", 1503 op_no, INSN_UID (insn), match_no); 1504 1505 break; 1506 } 1507 } 1508 1509 /* If we weren't able to replace any of the alternatives, try an 1510 alternative appoach of copying the source to the destination. */ 1511 if (!success && copy_src != NULL_RTX) 1512 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid); 1513 1514 } 1515 } 1516 1517 /* In fixup_match_1, some insns may have been inserted after basic block 1518 ends. Fix that here. */ 1519 FOR_EACH_BB (bb) 1520 { 1521 rtx end = bb->end; 1522 rtx new = end; 1523 rtx next = NEXT_INSN (new); 1524 while (next != 0 && INSN_UID (next) >= old_max_uid 1525 && (bb->next_bb == EXIT_BLOCK_PTR || bb->next_bb->head != next)) 1526 new = next, next = NEXT_INSN (new); 1527 bb->end = new; 1528 } 1529 1530 done: 1531 /* Clean up. */ 1532 free (regno_src_regno); 1533 free (regmove_bb_head); 1534} 1535 1536/* Returns nonzero if INSN's pattern has matching constraints for any operand. 1537 Returns 0 if INSN can't be recognized, or if the alternative can't be 1538 determined. 1539 1540 Initialize the info in MATCHP based on the constraints. */ 1541 1542static int 1543find_matches (insn, matchp) 1544 rtx insn; 1545 struct match *matchp; 1546{ 1547 int likely_spilled[MAX_RECOG_OPERANDS]; 1548 int op_no; 1549 int any_matches = 0; 1550 1551 extract_insn (insn); 1552 if (! constrain_operands (0)) 1553 return 0; 1554 1555 /* Must initialize this before main loop, because the code for 1556 the commutative case may set matches for operands other than 1557 the current one. */ 1558 for (op_no = recog_data.n_operands; --op_no >= 0; ) 1559 matchp->with[op_no] = matchp->commutative[op_no] = -1; 1560 1561 for (op_no = 0; op_no < recog_data.n_operands; op_no++) 1562 { 1563 const char *p; 1564 char c; 1565 int i = 0; 1566 1567 p = recog_data.constraints[op_no]; 1568 1569 likely_spilled[op_no] = 0; 1570 matchp->use[op_no] = READ; 1571 matchp->early_clobber[op_no] = 0; 1572 if (*p == '=') 1573 matchp->use[op_no] = WRITE; 1574 else if (*p == '+') 1575 matchp->use[op_no] = READWRITE; 1576 1577 for (;*p && i < which_alternative; p++) 1578 if (*p == ',') 1579 i++; 1580 1581 while ((c = *p++) != '\0' && c != ',') 1582 switch (c) 1583 { 1584 case '=': 1585 break; 1586 case '+': 1587 break; 1588 case '&': 1589 matchp->early_clobber[op_no] = 1; 1590 break; 1591 case '%': 1592 matchp->commutative[op_no] = op_no + 1; 1593 matchp->commutative[op_no + 1] = op_no; 1594 break; 1595 1596 case '0': case '1': case '2': case '3': case '4': 1597 case '5': case '6': case '7': case '8': case '9': 1598 { 1599 char *end; 1600 unsigned long match_ul = strtoul (p - 1, &end, 10); 1601 int match = match_ul; 1602 1603 p = end; 1604 1605 if (match < op_no && likely_spilled[match]) 1606 break; 1607 matchp->with[op_no] = match; 1608 any_matches = 1; 1609 if (matchp->commutative[op_no] >= 0) 1610 matchp->with[matchp->commutative[op_no]] = match; 1611 } 1612 break; 1613 1614 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h': 1615 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u': 1616 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B': 1617 case 'C': case 'D': case 'W': case 'Y': case 'Z': 1618 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char) c))) 1619 likely_spilled[op_no] = 1; 1620 break; 1621 } 1622 } 1623 return any_matches; 1624} 1625 1626/* Try to replace all occurrences of DST_REG with SRC in LOC, that is 1627 assumed to be in INSN. */ 1628 1629static void 1630replace_in_call_usage (loc, dst_reg, src, insn) 1631 rtx *loc; 1632 unsigned int dst_reg; 1633 rtx src; 1634 rtx insn; 1635{ 1636 rtx x = *loc; 1637 enum rtx_code code; 1638 const char *fmt; 1639 int i, j; 1640 1641 if (! x) 1642 return; 1643 1644 code = GET_CODE (x); 1645 if (code == REG) 1646 { 1647 if (REGNO (x) != dst_reg) 1648 return; 1649 1650 validate_change (insn, loc, src, 1); 1651 1652 return; 1653 } 1654 1655 /* Process each of our operands recursively. */ 1656 fmt = GET_RTX_FORMAT (code); 1657 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) 1658 if (*fmt == 'e') 1659 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn); 1660 else if (*fmt == 'E') 1661 for (j = 0; j < XVECLEN (x, i); j++) 1662 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn); 1663} 1664 1665/* Try to replace output operand DST in SET, with input operand SRC. SET is 1666 the only set in INSN. INSN has just been recognized and constrained. 1667 SRC is operand number OPERAND_NUMBER in INSN. 1668 DST is operand number MATCH_NUMBER in INSN. 1669 If BACKWARD is nonzero, we have been called in a backward pass. 1670 Return nonzero for success. */ 1671 1672static int 1673fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number, 1674 match_number, regmove_dump_file) 1675 rtx insn, set, src, src_subreg, dst; 1676 int backward, operand_number, match_number; 1677 FILE *regmove_dump_file; 1678{ 1679 rtx p; 1680 rtx post_inc = 0, post_inc_set = 0, search_end = 0; 1681 int success = 0; 1682 int num_calls = 0, s_num_calls = 0; 1683 enum rtx_code code = NOTE; 1684 HOST_WIDE_INT insn_const = 0, newconst; 1685 rtx overlap = 0; /* need to move insn ? */ 1686 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX; 1687 int length, s_length; 1688 1689 /* If SRC is marked as unchanging, we may not change it. 1690 ??? Maybe we could get better code by removing the unchanging bit 1691 instead, and changing it back if we don't succeed? */ 1692 if (RTX_UNCHANGING_P (src)) 1693 return 0; 1694 1695 if (! src_note) 1696 { 1697 /* Look for (set (regX) (op regA constX)) 1698 (set (regY) (op regA constY)) 1699 and change that to 1700 (set (regA) (op regA constX)). 1701 (set (regY) (op regA constY-constX)). 1702 This works for add and shift operations, if 1703 regA is dead after or set by the second insn. */ 1704 1705 code = GET_CODE (SET_SRC (set)); 1706 if ((code == PLUS || code == LSHIFTRT 1707 || code == ASHIFT || code == ASHIFTRT) 1708 && XEXP (SET_SRC (set), 0) == src 1709 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT) 1710 insn_const = INTVAL (XEXP (SET_SRC (set), 1)); 1711 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst)) 1712 return 0; 1713 else 1714 /* We might find a src_note while scanning. */ 1715 code = NOTE; 1716 } 1717 1718 if (regmove_dump_file) 1719 fprintf (regmove_dump_file, 1720 "Could fix operand %d of insn %d matching operand %d.\n", 1721 operand_number, INSN_UID (insn), match_number); 1722 1723 /* If SRC is equivalent to a constant set in a different basic block, 1724 then do not use it for this optimization. We want the equivalence 1725 so that if we have to reload this register, we can reload the 1726 constant, rather than extending the lifespan of the register. */ 1727 if (reg_is_remote_constant_p (src, insn, get_insns ())) 1728 return 0; 1729 1730 /* Scan forward to find the next instruction that 1731 uses the output operand. If the operand dies here, 1732 then replace it in both instructions with 1733 operand_number. */ 1734 1735 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 1736 { 1737 if (GET_CODE (p) == CALL_INSN) 1738 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p), 1739 REGNO (dst), src, p); 1740 1741 /* ??? We can't scan past the end of a basic block without updating 1742 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 1743 if (perhaps_ends_bb_p (p)) 1744 break; 1745 else if (! INSN_P (p)) 1746 continue; 1747 1748 length++; 1749 if (src_note) 1750 s_length++; 1751 1752 if (reg_set_p (src, p) || reg_set_p (dst, p) 1753 || (GET_CODE (PATTERN (p)) == USE 1754 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0)))) 1755 break; 1756 1757 /* See if all of DST dies in P. This test is 1758 slightly more conservative than it needs to be. */ 1759 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst))) 1760 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst))) 1761 { 1762 /* If we would be moving INSN, check that we won't move it 1763 into the shadow of a live a live flags register. */ 1764 /* ??? We only try to move it in front of P, although 1765 we could move it anywhere between OVERLAP and P. */ 1766 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode) 1767 break; 1768 1769 if (! src_note) 1770 { 1771 rtx q; 1772 rtx set2 = NULL_RTX; 1773 1774 /* If an optimization is done, the value of SRC while P 1775 is executed will be changed. Check that this is OK. */ 1776 if (reg_overlap_mentioned_p (src, PATTERN (p))) 1777 break; 1778 for (q = p; q; q = NEXT_INSN (q)) 1779 { 1780 /* ??? We can't scan past the end of a basic block without 1781 updating the register lifetime info 1782 (REG_DEAD/basic_block_live_at_start). */ 1783 if (perhaps_ends_bb_p (q)) 1784 { 1785 q = 0; 1786 break; 1787 } 1788 else if (! INSN_P (q)) 1789 continue; 1790 else if (reg_overlap_mentioned_p (src, PATTERN (q)) 1791 || reg_set_p (src, q)) 1792 break; 1793 } 1794 if (q) 1795 set2 = single_set (q); 1796 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code 1797 || XEXP (SET_SRC (set2), 0) != src 1798 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT 1799 || (SET_DEST (set2) != src 1800 && ! find_reg_note (q, REG_DEAD, src))) 1801 { 1802 /* If this is a PLUS, we can still save a register by doing 1803 src += insn_const; 1804 P; 1805 src -= insn_const; . 1806 This also gives opportunities for subsequent 1807 optimizations in the backward pass, so do it there. */ 1808 if (code == PLUS && backward 1809 /* Don't do this if we can likely tie DST to SET_DEST 1810 of P later; we can't do this tying here if we got a 1811 hard register. */ 1812 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst)) 1813 && single_set (p) 1814 && GET_CODE (SET_DEST (single_set (p))) == REG 1815 && (REGNO (SET_DEST (single_set (p))) 1816 < FIRST_PSEUDO_REGISTER)) 1817 /* We may only emit an insn directly after P if we 1818 are not in the shadow of a live flags register. */ 1819 && GET_MODE (p) == VOIDmode) 1820 { 1821 search_end = q; 1822 q = insn; 1823 set2 = set; 1824 newconst = -insn_const; 1825 code = MINUS; 1826 } 1827 else 1828 break; 1829 } 1830 else 1831 { 1832 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const; 1833 /* Reject out of range shifts. */ 1834 if (code != PLUS 1835 && (newconst < 0 1836 || ((unsigned HOST_WIDE_INT) newconst 1837 >= (GET_MODE_BITSIZE (GET_MODE 1838 (SET_SRC (set2))))))) 1839 break; 1840 if (code == PLUS) 1841 { 1842 post_inc = q; 1843 if (SET_DEST (set2) != src) 1844 post_inc_set = set2; 1845 } 1846 } 1847 /* We use 1 as last argument to validate_change so that all 1848 changes are accepted or rejected together by apply_change_group 1849 when it is called by validate_replace_rtx . */ 1850 validate_change (q, &XEXP (SET_SRC (set2), 1), 1851 GEN_INT (newconst), 1); 1852 } 1853 validate_change (insn, recog_data.operand_loc[match_number], src, 1); 1854 if (validate_replace_rtx (dst, src_subreg, p)) 1855 success = 1; 1856 break; 1857 } 1858 1859 if (reg_overlap_mentioned_p (dst, PATTERN (p))) 1860 break; 1861 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p))) 1862 { 1863 /* INSN was already checked to be movable wrt. the registers that it 1864 sets / uses when we found no REG_DEAD note for src on it, but it 1865 still might clobber the flags register. We'll have to check that 1866 we won't insert it into the shadow of a live flags register when 1867 we finally know where we are to move it. */ 1868 overlap = p; 1869 src_note = find_reg_note (p, REG_DEAD, src); 1870 } 1871 1872 /* If we have passed a call instruction, and the pseudo-reg SRC is not 1873 already live across a call, then don't perform the optimization. */ 1874 if (GET_CODE (p) == CALL_INSN) 1875 { 1876 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0) 1877 break; 1878 1879 num_calls++; 1880 1881 if (src_note) 1882 s_num_calls++; 1883 1884 } 1885 } 1886 1887 if (! success) 1888 return 0; 1889 1890 /* Remove the death note for DST from P. */ 1891 remove_note (p, dst_note); 1892 if (code == MINUS) 1893 { 1894 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p); 1895 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT) 1896 && search_end 1897 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1)) 1898 post_inc = 0; 1899 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0); 1900 REG_N_SETS (REGNO (src))++; 1901 REG_LIVE_LENGTH (REGNO (src))++; 1902 } 1903 if (overlap) 1904 { 1905 /* The lifetime of src and dest overlap, 1906 but we can change this by moving insn. */ 1907 rtx pat = PATTERN (insn); 1908 if (src_note) 1909 remove_note (overlap, src_note); 1910 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT) 1911 && code == PLUS 1912 && try_auto_increment (overlap, insn, 0, src, insn_const, 0)) 1913 insn = overlap; 1914 else 1915 { 1916 rtx notes = REG_NOTES (insn); 1917 1918 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn); 1919 delete_insn (insn); 1920 /* emit_insn_after_with_line_notes has no 1921 return value, so search for the new insn. */ 1922 insn = p; 1923 while (! INSN_P (insn) || PATTERN (insn) != pat) 1924 insn = PREV_INSN (insn); 1925 1926 REG_NOTES (insn) = notes; 1927 } 1928 } 1929 /* Sometimes we'd generate src = const; src += n; 1930 if so, replace the instruction that set src 1931 in the first place. */ 1932 1933 if (! overlap && (code == PLUS || code == MINUS)) 1934 { 1935 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 1936 rtx q, set2 = NULL_RTX; 1937 int num_calls2 = 0, s_length2 = 0; 1938 1939 if (note && CONSTANT_P (XEXP (note, 0))) 1940 { 1941 for (q = PREV_INSN (insn); q; q = PREV_INSN (q)) 1942 { 1943 /* ??? We can't scan past the end of a basic block without 1944 updating the register lifetime info 1945 (REG_DEAD/basic_block_live_at_start). */ 1946 if (perhaps_ends_bb_p (q)) 1947 { 1948 q = 0; 1949 break; 1950 } 1951 else if (! INSN_P (q)) 1952 continue; 1953 1954 s_length2++; 1955 if (reg_set_p (src, q)) 1956 { 1957 set2 = single_set (q); 1958 break; 1959 } 1960 if (reg_overlap_mentioned_p (src, PATTERN (q))) 1961 { 1962 q = 0; 1963 break; 1964 } 1965 if (GET_CODE (p) == CALL_INSN) 1966 num_calls2++; 1967 } 1968 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2)) 1969 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0)) 1970 { 1971 delete_insn (q); 1972 REG_N_SETS (REGNO (src))--; 1973 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2; 1974 REG_LIVE_LENGTH (REGNO (src)) -= s_length2; 1975 insn_const = 0; 1976 } 1977 } 1978 } 1979 1980 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT) 1981 && (code == PLUS || code == MINUS) && insn_const 1982 && try_auto_increment (p, insn, 0, src, insn_const, 1)) 1983 insn = p; 1984 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT) 1985 && post_inc 1986 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0)) 1987 post_inc = 0; 1988 /* If post_inc still prevails, try to find an 1989 insn where it can be used as a pre-in/decrement. 1990 If code is MINUS, this was already tried. */ 1991 if (post_inc && code == PLUS 1992 /* Check that newconst is likely to be usable 1993 in a pre-in/decrement before starting the search. */ 1994 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX) 1995 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX)) 1996 && exact_log2 (newconst)) 1997 { 1998 rtx q, inc_dest; 1999 2000 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src; 2001 for (q = post_inc; (q = NEXT_INSN (q)); ) 2002 { 2003 /* ??? We can't scan past the end of a basic block without updating 2004 the register lifetime info 2005 (REG_DEAD/basic_block_live_at_start). */ 2006 if (perhaps_ends_bb_p (q)) 2007 break; 2008 else if (! INSN_P (q)) 2009 continue; 2010 else if (src != inc_dest 2011 && (reg_overlap_mentioned_p (src, PATTERN (q)) 2012 || reg_set_p (src, q))) 2013 break; 2014 else if (reg_set_p (inc_dest, q)) 2015 break; 2016 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q))) 2017 { 2018 try_auto_increment (q, post_inc, 2019 post_inc_set, inc_dest, newconst, 1); 2020 break; 2021 } 2022 } 2023 } 2024 2025 /* Move the death note for DST to INSN if it is used 2026 there. */ 2027 if (reg_overlap_mentioned_p (dst, PATTERN (insn))) 2028 { 2029 XEXP (dst_note, 1) = REG_NOTES (insn); 2030 REG_NOTES (insn) = dst_note; 2031 } 2032 2033 if (src_note) 2034 { 2035 /* Move the death note for SRC from INSN to P. */ 2036 if (! overlap) 2037 remove_note (insn, src_note); 2038 XEXP (src_note, 1) = REG_NOTES (p); 2039 REG_NOTES (p) = src_note; 2040 2041 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls; 2042 } 2043 2044 REG_N_SETS (REGNO (src))++; 2045 REG_N_SETS (REGNO (dst))--; 2046 2047 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls; 2048 2049 REG_LIVE_LENGTH (REGNO (src)) += s_length; 2050 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0) 2051 { 2052 REG_LIVE_LENGTH (REGNO (dst)) -= length; 2053 /* REG_LIVE_LENGTH is only an approximation after 2054 combine if sched is not run, so make sure that we 2055 still have a reasonable value. */ 2056 if (REG_LIVE_LENGTH (REGNO (dst)) < 2) 2057 REG_LIVE_LENGTH (REGNO (dst)) = 2; 2058 } 2059 if (regmove_dump_file) 2060 fprintf (regmove_dump_file, 2061 "Fixed operand %d of insn %d matching operand %d.\n", 2062 operand_number, INSN_UID (insn), match_number); 2063 return 1; 2064} 2065 2066 2067/* return nonzero if X is stable and mentions no regsiters but for 2068 mentioning SRC or mentioning / changing DST . If in doubt, presume 2069 it is unstable. 2070 The rationale is that we want to check if we can move an insn easily 2071 while just paying attention to SRC and DST. A register is considered 2072 stable if it has the RTX_UNCHANGING_P bit set, but that would still 2073 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't 2074 want any registers but SRC and DST. */ 2075static int 2076stable_and_no_regs_but_for_p (x, src, dst) 2077 rtx x, src, dst; 2078{ 2079 RTX_CODE code = GET_CODE (x); 2080 switch (GET_RTX_CLASS (code)) 2081 { 2082 case '<': case '1': case 'c': case '2': case 'b': case '3': 2083 { 2084 int i; 2085 const char *fmt = GET_RTX_FORMAT (code); 2086 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2087 if (fmt[i] == 'e' 2088 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst)) 2089 return 0; 2090 return 1; 2091 } 2092 case 'o': 2093 if (code == REG) 2094 return x == src || x == dst; 2095 /* If this is a MEM, look inside - there might be a register hidden in 2096 the address of an unchanging MEM. */ 2097 if (code == MEM 2098 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst)) 2099 return 0; 2100 /* fall through */ 2101 default: 2102 return ! rtx_unstable_p (x); 2103 } 2104} 2105 2106/* Track stack adjustments and stack memory references. Attempt to 2107 reduce the number of stack adjustments by back-propagating across 2108 the memory references. 2109 2110 This is intended primarily for use with targets that do not define 2111 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to 2112 targets that define PREFERRED_STACK_BOUNDARY more aligned than 2113 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed 2114 (e.g. x86 fp regs) which would ordinarily have to be implemented 2115 as a sub/mov pair due to restrictions in calls.c. 2116 2117 Propagation stops when any of the insns that need adjusting are 2118 (a) no longer valid because we've exceeded their range, (b) a 2119 non-trivial push instruction, or (c) a call instruction. 2120 2121 Restriction B is based on the assumption that push instructions 2122 are smaller or faster. If a port really wants to remove all 2123 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The 2124 one exception that is made is for an add immediately followed 2125 by a push. */ 2126 2127/* This structure records stack memory references between stack adjusting 2128 instructions. */ 2129 2130struct csa_memlist 2131{ 2132 HOST_WIDE_INT sp_offset; 2133 rtx insn, *mem; 2134 struct csa_memlist *next; 2135}; 2136 2137static int stack_memref_p PARAMS ((rtx)); 2138static rtx single_set_for_csa PARAMS ((rtx)); 2139static void free_csa_memlist PARAMS ((struct csa_memlist *)); 2140static struct csa_memlist *record_one_stack_memref 2141 PARAMS ((rtx, rtx *, struct csa_memlist *)); 2142static int try_apply_stack_adjustment 2143 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT)); 2144static void combine_stack_adjustments_for_block PARAMS ((basic_block)); 2145static int record_stack_memrefs PARAMS ((rtx *, void *)); 2146 2147 2148/* Main entry point for stack adjustment combination. */ 2149 2150void 2151combine_stack_adjustments () 2152{ 2153 basic_block bb; 2154 2155 FOR_EACH_BB (bb) 2156 combine_stack_adjustments_for_block (bb); 2157} 2158 2159/* Recognize a MEM of the form (sp) or (plus sp const). */ 2160 2161static int 2162stack_memref_p (x) 2163 rtx x; 2164{ 2165 if (GET_CODE (x) != MEM) 2166 return 0; 2167 x = XEXP (x, 0); 2168 2169 if (x == stack_pointer_rtx) 2170 return 1; 2171 if (GET_CODE (x) == PLUS 2172 && XEXP (x, 0) == stack_pointer_rtx 2173 && GET_CODE (XEXP (x, 1)) == CONST_INT) 2174 return 1; 2175 2176 return 0; 2177} 2178 2179/* Recognize either normal single_set or the hack in i386.md for 2180 tying fp and sp adjustments. */ 2181 2182static rtx 2183single_set_for_csa (insn) 2184 rtx insn; 2185{ 2186 int i; 2187 rtx tmp = single_set (insn); 2188 if (tmp) 2189 return tmp; 2190 2191 if (GET_CODE (insn) != INSN 2192 || GET_CODE (PATTERN (insn)) != PARALLEL) 2193 return NULL_RTX; 2194 2195 tmp = PATTERN (insn); 2196 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET) 2197 return NULL_RTX; 2198 2199 for (i = 1; i < XVECLEN (tmp, 0); ++i) 2200 { 2201 rtx this = XVECEXP (tmp, 0, i); 2202 2203 /* The special case is allowing a no-op set. */ 2204 if (GET_CODE (this) == SET 2205 && SET_SRC (this) == SET_DEST (this)) 2206 ; 2207 else if (GET_CODE (this) != CLOBBER 2208 && GET_CODE (this) != USE) 2209 return NULL_RTX; 2210 } 2211 2212 return XVECEXP (tmp, 0, 0); 2213} 2214 2215/* Free the list of csa_memlist nodes. */ 2216 2217static void 2218free_csa_memlist (memlist) 2219 struct csa_memlist *memlist; 2220{ 2221 struct csa_memlist *next; 2222 for (; memlist ; memlist = next) 2223 { 2224 next = memlist->next; 2225 free (memlist); 2226 } 2227} 2228 2229/* Create a new csa_memlist node from the given memory reference. 2230 It is already known that the memory is stack_memref_p. */ 2231 2232static struct csa_memlist * 2233record_one_stack_memref (insn, mem, next_memlist) 2234 rtx insn, *mem; 2235 struct csa_memlist *next_memlist; 2236{ 2237 struct csa_memlist *ml; 2238 2239 ml = (struct csa_memlist *) xmalloc (sizeof (*ml)); 2240 2241 if (XEXP (*mem, 0) == stack_pointer_rtx) 2242 ml->sp_offset = 0; 2243 else 2244 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1)); 2245 2246 ml->insn = insn; 2247 ml->mem = mem; 2248 ml->next = next_memlist; 2249 2250 return ml; 2251} 2252 2253/* Attempt to apply ADJUST to the stack adjusting insn INSN, as well 2254 as each of the memories in MEMLIST. Return true on success. */ 2255 2256static int 2257try_apply_stack_adjustment (insn, memlist, new_adjust, delta) 2258 rtx insn; 2259 struct csa_memlist *memlist; 2260 HOST_WIDE_INT new_adjust, delta; 2261{ 2262 struct csa_memlist *ml; 2263 rtx set; 2264 2265 set = single_set_for_csa (insn); 2266 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1); 2267 2268 for (ml = memlist; ml ; ml = ml->next) 2269 validate_change 2270 (ml->insn, ml->mem, 2271 replace_equiv_address_nv (*ml->mem, 2272 plus_constant (stack_pointer_rtx, 2273 ml->sp_offset - delta)), 1); 2274 2275 if (apply_change_group ()) 2276 { 2277 /* Succeeded. Update our knowledge of the memory references. */ 2278 for (ml = memlist; ml ; ml = ml->next) 2279 ml->sp_offset -= delta; 2280 2281 return 1; 2282 } 2283 else 2284 return 0; 2285} 2286 2287/* Called via for_each_rtx and used to record all stack memory references in 2288 the insn and discard all other stack pointer references. */ 2289struct record_stack_memrefs_data 2290{ 2291 rtx insn; 2292 struct csa_memlist *memlist; 2293}; 2294 2295static int 2296record_stack_memrefs (xp, data) 2297 rtx *xp; 2298 void *data; 2299{ 2300 rtx x = *xp; 2301 struct record_stack_memrefs_data *d = 2302 (struct record_stack_memrefs_data *) data; 2303 if (!x) 2304 return 0; 2305 switch (GET_CODE (x)) 2306 { 2307 case MEM: 2308 if (!reg_mentioned_p (stack_pointer_rtx, x)) 2309 return -1; 2310 /* We are not able to handle correctly all possible memrefs containing 2311 stack pointer, so this check is necessary. */ 2312 if (stack_memref_p (x)) 2313 { 2314 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist); 2315 return -1; 2316 } 2317 return 1; 2318 case REG: 2319 /* ??? We want be able to handle non-memory stack pointer 2320 references later. For now just discard all insns refering to 2321 stack pointer outside mem expressions. We would probably 2322 want to teach validate_replace to simplify expressions first. 2323 2324 We can't just compare with STACK_POINTER_RTX because the 2325 reference to the stack pointer might be in some other mode. 2326 In particular, an explict clobber in an asm statement will 2327 result in a QImode clober. */ 2328 if (REGNO (x) == STACK_POINTER_REGNUM) 2329 return 1; 2330 break; 2331 default: 2332 break; 2333 } 2334 return 0; 2335} 2336 2337/* Subroutine of combine_stack_adjustments, called for each basic block. */ 2338 2339static void 2340combine_stack_adjustments_for_block (bb) 2341 basic_block bb; 2342{ 2343 HOST_WIDE_INT last_sp_adjust = 0; 2344 rtx last_sp_set = NULL_RTX; 2345 struct csa_memlist *memlist = NULL; 2346 rtx insn, next, set; 2347 struct record_stack_memrefs_data data; 2348 bool end_of_block = false; 2349 2350 for (insn = bb->head; !end_of_block ; insn = next) 2351 { 2352 end_of_block = insn == bb->end; 2353 next = NEXT_INSN (insn); 2354 2355 if (! INSN_P (insn)) 2356 continue; 2357 2358 set = single_set_for_csa (insn); 2359 if (set) 2360 { 2361 rtx dest = SET_DEST (set); 2362 rtx src = SET_SRC (set); 2363 2364 /* Find constant additions to the stack pointer. */ 2365 if (dest == stack_pointer_rtx 2366 && GET_CODE (src) == PLUS 2367 && XEXP (src, 0) == stack_pointer_rtx 2368 && GET_CODE (XEXP (src, 1)) == CONST_INT) 2369 { 2370 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1)); 2371 2372 /* If we've not seen an adjustment previously, record 2373 it now and continue. */ 2374 if (! last_sp_set) 2375 { 2376 last_sp_set = insn; 2377 last_sp_adjust = this_adjust; 2378 continue; 2379 } 2380 2381 /* If not all recorded memrefs can be adjusted, or the 2382 adjustment is now too large for a constant addition, 2383 we cannot merge the two stack adjustments. 2384 2385 Also we need to be carefull to not move stack pointer 2386 such that we create stack accesses outside the allocated 2387 area. We can combine an allocation into the first insn, 2388 or a deallocation into the second insn. We can not 2389 combine an allocation followed by a deallocation. 2390 2391 The only somewhat frequent occurrence of the later is when 2392 a function allocates a stack frame but does not use it. 2393 For this case, we would need to analyze rtl stream to be 2394 sure that allocated area is really unused. This means not 2395 only checking the memory references, but also all registers 2396 or global memory references possibly containing a stack 2397 frame address. 2398 2399 Perhaps the best way to address this problem is to teach 2400 gcc not to allocate stack for objects never used. */ 2401 2402 /* Combine an allocation into the first instruction. */ 2403 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0) 2404 { 2405 if (try_apply_stack_adjustment (last_sp_set, memlist, 2406 last_sp_adjust + this_adjust, 2407 this_adjust)) 2408 { 2409 /* It worked! */ 2410 delete_insn (insn); 2411 last_sp_adjust += this_adjust; 2412 continue; 2413 } 2414 } 2415 2416 /* Otherwise we have a deallocation. Do not combine with 2417 a previous allocation. Combine into the second insn. */ 2418 else if (STACK_GROWS_DOWNWARD 2419 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 2420 { 2421 if (try_apply_stack_adjustment (insn, memlist, 2422 last_sp_adjust + this_adjust, 2423 -last_sp_adjust)) 2424 { 2425 /* It worked! */ 2426 delete_insn (last_sp_set); 2427 last_sp_set = insn; 2428 last_sp_adjust += this_adjust; 2429 free_csa_memlist (memlist); 2430 memlist = NULL; 2431 continue; 2432 } 2433 } 2434 2435 /* Combination failed. Restart processing from here. If 2436 deallocation+allocation conspired to cancel, we can 2437 delete the old deallocation insn. */ 2438 if (last_sp_set && last_sp_adjust == 0) 2439 delete_insn (insn); 2440 free_csa_memlist (memlist); 2441 memlist = NULL; 2442 last_sp_set = insn; 2443 last_sp_adjust = this_adjust; 2444 continue; 2445 } 2446 2447 /* Find a predecrement of exactly the previous adjustment and 2448 turn it into a direct store. Obviously we can't do this if 2449 there were any intervening uses of the stack pointer. */ 2450 if (memlist == NULL 2451 && GET_CODE (dest) == MEM 2452 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC 2453 && (last_sp_adjust 2454 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))) 2455 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY 2456 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS 2457 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx 2458 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 2459 == CONST_INT) 2460 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 2461 == -last_sp_adjust))) 2462 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx 2463 && ! reg_mentioned_p (stack_pointer_rtx, src) 2464 && memory_address_p (GET_MODE (dest), stack_pointer_rtx) 2465 && validate_change (insn, &SET_DEST (set), 2466 replace_equiv_address (dest, 2467 stack_pointer_rtx), 2468 0)) 2469 { 2470 delete_insn (last_sp_set); 2471 free_csa_memlist (memlist); 2472 memlist = NULL; 2473 last_sp_set = NULL_RTX; 2474 last_sp_adjust = 0; 2475 continue; 2476 } 2477 } 2478 2479 data.insn = insn; 2480 data.memlist = memlist; 2481 if (GET_CODE (insn) != CALL_INSN && last_sp_set 2482 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data)) 2483 { 2484 memlist = data.memlist; 2485 continue; 2486 } 2487 memlist = data.memlist; 2488 2489 /* Otherwise, we were not able to process the instruction. 2490 Do not continue collecting data across such a one. */ 2491 if (last_sp_set 2492 && (GET_CODE (insn) == CALL_INSN 2493 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn)))) 2494 { 2495 if (last_sp_set && last_sp_adjust == 0) 2496 delete_insn (last_sp_set); 2497 free_csa_memlist (memlist); 2498 memlist = NULL; 2499 last_sp_set = NULL_RTX; 2500 last_sp_adjust = 0; 2501 } 2502 } 2503 2504 if (last_sp_set && last_sp_adjust == 0) 2505 delete_insn (last_sp_set); 2506} 2507