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