regmove.c revision 90075
139833Speter/* Move registers around to reduce number of move instructions needed. 239833Speter Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 339833Speter 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 439833Speter 539833SpeterThis file is part of GCC. 639833Speter 739833SpeterGCC is free software; you can redistribute it and/or modify it under 839833Speterthe terms of the GNU General Public License as published by the Free 939833SpeterSoftware Foundation; either version 2, or (at your option) any later 1039833Speterversion. 1139833Speter 1239833SpeterGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1339833SpeterWARRANTY; without even the implied warranty of MERCHANTABILITY or 1439833SpeterFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1539833Speterfor more details. 1639833Speter 1739833SpeterYou should have received a copy of the GNU General Public License 1839833Speteralong with GCC; see the file COPYING. If not, write to the Free 1939833SpeterSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 2039833Speter02111-1307, USA. */ 2139833Speter 2239833Speter 2339833Speter/* This module looks for cases where matching constraints would force 2439833Speter an instruction to need a reload, and this reload would be a register 2539833Speter to register move. It then attempts to change the registers used by the 2650477Speter instruction to avoid the move instruction. */ 2739833Speter 2839833Speter#include "config.h" 2939833Speter#include "system.h" 3039833Speter#include "rtl.h" /* stdio.h must precede rtl.h for FFS. */ 3139833Speter#include "tm_p.h" 3239833Speter#include "insn-config.h" 3339833Speter#include "recog.h" 3439833Speter#include "output.h" 3539833Speter#include "regs.h" 3639833Speter#include "hard-reg-set.h" 3739833Speter#include "flags.h" 3839833Speter#include "function.h" 3939833Speter#include "expr.h" 4039833Speter#include "basic-block.h" 4139833Speter#include "except.h" 4259854Sbp#include "toplev.h" 4339833Speter#include "reload.h" 4459854Sbp 4539833Speter 4639833Speter/* Turn STACK_GROWS_DOWNWARD into a boolean. */ 4739833Speter#ifdef STACK_GROWS_DOWNWARD 4839833Speter#undef STACK_GROWS_DOWNWARD 4939833Speter#define STACK_GROWS_DOWNWARD 1 5039833Speter#else 5139833Speter#define STACK_GROWS_DOWNWARD 0 5239833Speter#endif 5339833Speter 5459854Sbpstatic int perhaps_ends_bb_p PARAMS ((rtx)); 5539833Speterstatic int optimize_reg_copy_1 PARAMS ((rtx, rtx, rtx)); 5659854Sbpstatic void optimize_reg_copy_2 PARAMS ((rtx, rtx, rtx)); 5739833Speterstatic void optimize_reg_copy_3 PARAMS ((rtx, rtx, rtx)); 5839902Smsmithstatic void copy_src_to_dest PARAMS ((rtx, rtx, rtx, int)); 5939902Smsmithstatic int *regmove_bb_head; 6039902Smsmith 6139902Smsmithstruct match { 6239833Speter int with[MAX_RECOG_OPERANDS]; 6359854Sbp enum { READ, WRITE, READWRITE } use[MAX_RECOG_OPERANDS]; 6439833Speter int commutative[MAX_RECOG_OPERANDS]; 6539833Speter int early_clobber[MAX_RECOG_OPERANDS]; 6639833Speter}; 6759854Sbp 6839902Smsmithstatic rtx discover_flags_reg PARAMS ((void)); 6939902Smsmithstatic void mark_flags_life_zones PARAMS ((rtx)); 7039902Smsmithstatic void flags_set_1 PARAMS ((rtx, rtx, void *)); 7139943Smsmith 7259854Sbpstatic int try_auto_increment PARAMS ((rtx, rtx, rtx, rtx, HOST_WIDE_INT, int)); 7339887Speterstatic int find_matches PARAMS ((rtx, struct match *)); 7459854Sbpstatic void replace_in_call_usage PARAMS ((rtx *, unsigned int, rtx, rtx)); 7539887Speterstatic int fixup_match_1 PARAMS ((rtx, rtx, rtx, rtx, rtx, int, int, int, FILE *)) 7639887Speter; 7739887Speterstatic int reg_is_remote_constant_p PARAMS ((rtx, rtx, rtx)); 7839902Smsmithstatic int stable_and_no_regs_but_for_p PARAMS ((rtx, rtx, rtx)); 7940145Speterstatic int regclass_compatible_p PARAMS ((int, int)); 8039902Smsmithstatic int replacement_quality PARAMS ((rtx)); 8139833Speterstatic int fixup_match_2 PARAMS ((rtx, rtx, rtx, rtx, FILE *)); 8239833Speter 8339833Speter/* Return non-zero if registers with CLASS1 and CLASS2 can be merged without 8439833Speter causing too much register allocation problems. */ 8539833Speterstatic int 8639833Speterregclass_compatible_p (class0, class1) 8739902Smsmith int class0, class1; 8839833Speter{ 8939833Speter return (class0 == class1 9039833Speter || (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 if (! regclass_compatible_p (src_class, dst_class)) 1332 { 1333 if (!copy_src) 1334 { 1335 copy_src = src; 1336 copy_dst = dst; 1337 } 1338 continue; 1339 } 1340 1341 /* Can not modify an earlier insn to set dst if this insn 1342 uses an old value in the source. */ 1343 if (reg_overlap_mentioned_p (dst, SET_SRC (set))) 1344 { 1345 if (!copy_src) 1346 { 1347 copy_src = src; 1348 copy_dst = dst; 1349 } 1350 continue; 1351 } 1352 1353 if (! (src_note = find_reg_note (insn, REG_DEAD, src))) 1354 { 1355 if (!copy_src) 1356 { 1357 copy_src = src; 1358 copy_dst = dst; 1359 } 1360 continue; 1361 } 1362 1363 1364 /* If src is set once in a different basic block, 1365 and is set equal to a constant, then do not use 1366 it for this optimization, as this would make it 1367 no longer equivalent to a constant. */ 1368 1369 if (reg_is_remote_constant_p (src, insn, f)) 1370 { 1371 if (!copy_src) 1372 { 1373 copy_src = src; 1374 copy_dst = dst; 1375 } 1376 continue; 1377 } 1378 1379 1380 if (regmove_dump_file) 1381 fprintf (regmove_dump_file, 1382 "Could fix operand %d of insn %d matching operand %d.\n", 1383 op_no, INSN_UID (insn), match_no); 1384 1385 /* Scan backward to find the first instruction that uses 1386 the input operand. If the operand is set here, then 1387 replace it in both instructions with match_no. */ 1388 1389 for (length = 0, p = PREV_INSN (insn); p; p = PREV_INSN (p)) 1390 { 1391 rtx pset; 1392 1393 /* ??? We can't scan past the end of a basic block without 1394 updating the register lifetime info 1395 (REG_DEAD/basic_block_live_at_start). */ 1396 if (perhaps_ends_bb_p (p)) 1397 break; 1398 else if (! INSN_P (p)) 1399 continue; 1400 1401 length++; 1402 1403 /* ??? See if all of SRC is set in P. This test is much 1404 more conservative than it needs to be. */ 1405 pset = single_set (p); 1406 if (pset && SET_DEST (pset) == src) 1407 { 1408 /* We use validate_replace_rtx, in case there 1409 are multiple identical source operands. All of 1410 them have to be changed at the same time. */ 1411 if (validate_replace_rtx (src, dst, insn)) 1412 { 1413 if (validate_change (p, &SET_DEST (pset), 1414 dst, 0)) 1415 success = 1; 1416 else 1417 { 1418 /* Change all source operands back. 1419 This modifies the dst as a side-effect. */ 1420 validate_replace_rtx (dst, src, insn); 1421 /* Now make sure the dst is right. */ 1422 validate_change (insn, 1423 recog_data.operand_loc[match_no], 1424 dst, 0); 1425 } 1426 } 1427 break; 1428 } 1429 1430 if (reg_overlap_mentioned_p (src, PATTERN (p)) 1431 || reg_overlap_mentioned_p (dst, PATTERN (p))) 1432 break; 1433 1434 /* If we have passed a call instruction, and the 1435 pseudo-reg DST is not already live across a call, 1436 then don't perform the optimization. */ 1437 if (GET_CODE (p) == CALL_INSN) 1438 { 1439 num_calls++; 1440 1441 if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0) 1442 break; 1443 } 1444 } 1445 1446 if (success) 1447 { 1448 int dstno, srcno; 1449 1450 /* Remove the death note for SRC from INSN. */ 1451 remove_note (insn, src_note); 1452 /* Move the death note for SRC to P if it is used 1453 there. */ 1454 if (reg_overlap_mentioned_p (src, PATTERN (p))) 1455 { 1456 XEXP (src_note, 1) = REG_NOTES (p); 1457 REG_NOTES (p) = src_note; 1458 } 1459 /* If there is a REG_DEAD note for DST on P, then remove 1460 it, because DST is now set there. */ 1461 if ((dst_note = find_reg_note (p, REG_DEAD, dst))) 1462 remove_note (p, dst_note); 1463 1464 dstno = REGNO (dst); 1465 srcno = REGNO (src); 1466 1467 REG_N_SETS (dstno)++; 1468 REG_N_SETS (srcno)--; 1469 1470 REG_N_CALLS_CROSSED (dstno) += num_calls; 1471 REG_N_CALLS_CROSSED (srcno) -= num_calls; 1472 1473 REG_LIVE_LENGTH (dstno) += length; 1474 if (REG_LIVE_LENGTH (srcno) >= 0) 1475 { 1476 REG_LIVE_LENGTH (srcno) -= length; 1477 /* REG_LIVE_LENGTH is only an approximation after 1478 combine if sched is not run, so make sure that we 1479 still have a reasonable value. */ 1480 if (REG_LIVE_LENGTH (srcno) < 2) 1481 REG_LIVE_LENGTH (srcno) = 2; 1482 } 1483 1484 if (regmove_dump_file) 1485 fprintf (regmove_dump_file, 1486 "Fixed operand %d of insn %d matching operand %d.\n", 1487 op_no, INSN_UID (insn), match_no); 1488 1489 break; 1490 } 1491 } 1492 1493 /* If we weren't able to replace any of the alternatives, try an 1494 alternative appoach of copying the source to the destination. */ 1495 if (!success && copy_src != NULL_RTX) 1496 copy_src_to_dest (insn, copy_src, copy_dst, old_max_uid); 1497 1498 } 1499 } 1500 1501 /* In fixup_match_1, some insns may have been inserted after basic block 1502 ends. Fix that here. */ 1503 for (i = 0; i < n_basic_blocks; i++) 1504 { 1505 rtx end = BLOCK_END (i); 1506 rtx new = end; 1507 rtx next = NEXT_INSN (new); 1508 while (next != 0 && INSN_UID (next) >= old_max_uid 1509 && (i == n_basic_blocks - 1 || BLOCK_HEAD (i + 1) != next)) 1510 new = next, next = NEXT_INSN (new); 1511 BLOCK_END (i) = new; 1512 } 1513 1514 done: 1515 /* Clean up. */ 1516 free (regno_src_regno); 1517 free (regmove_bb_head); 1518} 1519 1520/* Returns nonzero if INSN's pattern has matching constraints for any operand. 1521 Returns 0 if INSN can't be recognized, or if the alternative can't be 1522 determined. 1523 1524 Initialize the info in MATCHP based on the constraints. */ 1525 1526static int 1527find_matches (insn, matchp) 1528 rtx insn; 1529 struct match *matchp; 1530{ 1531 int likely_spilled[MAX_RECOG_OPERANDS]; 1532 int op_no; 1533 int any_matches = 0; 1534 1535 extract_insn (insn); 1536 if (! constrain_operands (0)) 1537 return 0; 1538 1539 /* Must initialize this before main loop, because the code for 1540 the commutative case may set matches for operands other than 1541 the current one. */ 1542 for (op_no = recog_data.n_operands; --op_no >= 0; ) 1543 matchp->with[op_no] = matchp->commutative[op_no] = -1; 1544 1545 for (op_no = 0; op_no < recog_data.n_operands; op_no++) 1546 { 1547 const char *p; 1548 char c; 1549 int i = 0; 1550 1551 p = recog_data.constraints[op_no]; 1552 1553 likely_spilled[op_no] = 0; 1554 matchp->use[op_no] = READ; 1555 matchp->early_clobber[op_no] = 0; 1556 if (*p == '=') 1557 matchp->use[op_no] = WRITE; 1558 else if (*p == '+') 1559 matchp->use[op_no] = READWRITE; 1560 1561 for (;*p && i < which_alternative; p++) 1562 if (*p == ',') 1563 i++; 1564 1565 while ((c = *p++) != '\0' && c != ',') 1566 switch (c) 1567 { 1568 case '=': 1569 break; 1570 case '+': 1571 break; 1572 case '&': 1573 matchp->early_clobber[op_no] = 1; 1574 break; 1575 case '%': 1576 matchp->commutative[op_no] = op_no + 1; 1577 matchp->commutative[op_no + 1] = op_no; 1578 break; 1579 1580 case '0': case '1': case '2': case '3': case '4': 1581 case '5': case '6': case '7': case '8': case '9': 1582 { 1583 char *end; 1584 unsigned long match_ul = strtoul (p - 1, &end, 10); 1585 int match = match_ul; 1586 1587 p = end; 1588 1589 if (match < op_no && likely_spilled[match]) 1590 break; 1591 matchp->with[op_no] = match; 1592 any_matches = 1; 1593 if (matchp->commutative[op_no] >= 0) 1594 matchp->with[matchp->commutative[op_no]] = match; 1595 } 1596 break; 1597 1598 case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': case 'h': 1599 case 'j': case 'k': case 'l': case 'p': case 'q': case 't': case 'u': 1600 case 'v': case 'w': case 'x': case 'y': case 'z': case 'A': case 'B': 1601 case 'C': case 'D': case 'W': case 'Y': case 'Z': 1602 if (CLASS_LIKELY_SPILLED_P (REG_CLASS_FROM_LETTER ((unsigned char) c))) 1603 likely_spilled[op_no] = 1; 1604 break; 1605 } 1606 } 1607 return any_matches; 1608} 1609 1610/* Try to replace all occurrences of DST_REG with SRC in LOC, that is 1611 assumed to be in INSN. */ 1612 1613static void 1614replace_in_call_usage (loc, dst_reg, src, insn) 1615 rtx *loc; 1616 unsigned int dst_reg; 1617 rtx src; 1618 rtx insn; 1619{ 1620 rtx x = *loc; 1621 enum rtx_code code; 1622 const char *fmt; 1623 int i, j; 1624 1625 if (! x) 1626 return; 1627 1628 code = GET_CODE (x); 1629 if (code == REG) 1630 { 1631 if (REGNO (x) != dst_reg) 1632 return; 1633 1634 validate_change (insn, loc, src, 1); 1635 1636 return; 1637 } 1638 1639 /* Process each of our operands recursively. */ 1640 fmt = GET_RTX_FORMAT (code); 1641 for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++) 1642 if (*fmt == 'e') 1643 replace_in_call_usage (&XEXP (x, i), dst_reg, src, insn); 1644 else if (*fmt == 'E') 1645 for (j = 0; j < XVECLEN (x, i); j++) 1646 replace_in_call_usage (& XVECEXP (x, i, j), dst_reg, src, insn); 1647} 1648 1649/* Try to replace output operand DST in SET, with input operand SRC. SET is 1650 the only set in INSN. INSN has just been recognized and constrained. 1651 SRC is operand number OPERAND_NUMBER in INSN. 1652 DST is operand number MATCH_NUMBER in INSN. 1653 If BACKWARD is nonzero, we have been called in a backward pass. 1654 Return nonzero for success. */ 1655 1656static int 1657fixup_match_1 (insn, set, src, src_subreg, dst, backward, operand_number, 1658 match_number, regmove_dump_file) 1659 rtx insn, set, src, src_subreg, dst; 1660 int backward, operand_number, match_number; 1661 FILE *regmove_dump_file; 1662{ 1663 rtx p; 1664 rtx post_inc = 0, post_inc_set = 0, search_end = 0; 1665 int success = 0; 1666 int num_calls = 0, s_num_calls = 0; 1667 enum rtx_code code = NOTE; 1668 HOST_WIDE_INT insn_const = 0, newconst; 1669 rtx overlap = 0; /* need to move insn ? */ 1670 rtx src_note = find_reg_note (insn, REG_DEAD, src), dst_note = NULL_RTX; 1671 int length, s_length; 1672 1673 /* If SRC is marked as unchanging, we may not change it. 1674 ??? Maybe we could get better code by removing the unchanging bit 1675 instead, and changing it back if we don't succeed? */ 1676 if (RTX_UNCHANGING_P (src)) 1677 return 0; 1678 1679 if (! src_note) 1680 { 1681 /* Look for (set (regX) (op regA constX)) 1682 (set (regY) (op regA constY)) 1683 and change that to 1684 (set (regA) (op regA constX)). 1685 (set (regY) (op regA constY-constX)). 1686 This works for add and shift operations, if 1687 regA is dead after or set by the second insn. */ 1688 1689 code = GET_CODE (SET_SRC (set)); 1690 if ((code == PLUS || code == LSHIFTRT 1691 || code == ASHIFT || code == ASHIFTRT) 1692 && XEXP (SET_SRC (set), 0) == src 1693 && GET_CODE (XEXP (SET_SRC (set), 1)) == CONST_INT) 1694 insn_const = INTVAL (XEXP (SET_SRC (set), 1)); 1695 else if (! stable_and_no_regs_but_for_p (SET_SRC (set), src, dst)) 1696 return 0; 1697 else 1698 /* We might find a src_note while scanning. */ 1699 code = NOTE; 1700 } 1701 1702 if (regmove_dump_file) 1703 fprintf (regmove_dump_file, 1704 "Could fix operand %d of insn %d matching operand %d.\n", 1705 operand_number, INSN_UID (insn), match_number); 1706 1707 /* If SRC is equivalent to a constant set in a different basic block, 1708 then do not use it for this optimization. We want the equivalence 1709 so that if we have to reload this register, we can reload the 1710 constant, rather than extending the lifespan of the register. */ 1711 if (reg_is_remote_constant_p (src, insn, get_insns ())) 1712 return 0; 1713 1714 /* Scan forward to find the next instruction that 1715 uses the output operand. If the operand dies here, 1716 then replace it in both instructions with 1717 operand_number. */ 1718 1719 for (length = s_length = 0, p = NEXT_INSN (insn); p; p = NEXT_INSN (p)) 1720 { 1721 if (GET_CODE (p) == CALL_INSN) 1722 replace_in_call_usage (& CALL_INSN_FUNCTION_USAGE (p), 1723 REGNO (dst), src, p); 1724 1725 /* ??? We can't scan past the end of a basic block without updating 1726 the register lifetime info (REG_DEAD/basic_block_live_at_start). */ 1727 if (perhaps_ends_bb_p (p)) 1728 break; 1729 else if (! INSN_P (p)) 1730 continue; 1731 1732 length++; 1733 if (src_note) 1734 s_length++; 1735 1736 if (reg_set_p (src, p) || reg_set_p (dst, p) 1737 || (GET_CODE (PATTERN (p)) == USE 1738 && reg_overlap_mentioned_p (src, XEXP (PATTERN (p), 0)))) 1739 break; 1740 1741 /* See if all of DST dies in P. This test is 1742 slightly more conservative than it needs to be. */ 1743 if ((dst_note = find_regno_note (p, REG_DEAD, REGNO (dst))) 1744 && (GET_MODE (XEXP (dst_note, 0)) == GET_MODE (dst))) 1745 { 1746 /* If we would be moving INSN, check that we won't move it 1747 into the shadow of a live a live flags register. */ 1748 /* ??? We only try to move it in front of P, although 1749 we could move it anywhere between OVERLAP and P. */ 1750 if (overlap && GET_MODE (PREV_INSN (p)) != VOIDmode) 1751 break; 1752 1753 if (! src_note) 1754 { 1755 rtx q; 1756 rtx set2 = NULL_RTX; 1757 1758 /* If an optimization is done, the value of SRC while P 1759 is executed will be changed. Check that this is OK. */ 1760 if (reg_overlap_mentioned_p (src, PATTERN (p))) 1761 break; 1762 for (q = p; q; q = NEXT_INSN (q)) 1763 { 1764 /* ??? We can't scan past the end of a basic block without 1765 updating the register lifetime info 1766 (REG_DEAD/basic_block_live_at_start). */ 1767 if (perhaps_ends_bb_p (q)) 1768 { 1769 q = 0; 1770 break; 1771 } 1772 else if (! INSN_P (q)) 1773 continue; 1774 else if (reg_overlap_mentioned_p (src, PATTERN (q)) 1775 || reg_set_p (src, q)) 1776 break; 1777 } 1778 if (q) 1779 set2 = single_set (q); 1780 if (! q || ! set2 || GET_CODE (SET_SRC (set2)) != code 1781 || XEXP (SET_SRC (set2), 0) != src 1782 || GET_CODE (XEXP (SET_SRC (set2), 1)) != CONST_INT 1783 || (SET_DEST (set2) != src 1784 && ! find_reg_note (q, REG_DEAD, src))) 1785 { 1786 /* If this is a PLUS, we can still save a register by doing 1787 src += insn_const; 1788 P; 1789 src -= insn_const; . 1790 This also gives opportunities for subsequent 1791 optimizations in the backward pass, so do it there. */ 1792 if (code == PLUS && backward 1793 /* Don't do this if we can likely tie DST to SET_DEST 1794 of P later; we can't do this tying here if we got a 1795 hard register. */ 1796 && ! (dst_note && ! REG_N_CALLS_CROSSED (REGNO (dst)) 1797 && single_set (p) 1798 && GET_CODE (SET_DEST (single_set (p))) == REG 1799 && (REGNO (SET_DEST (single_set (p))) 1800 < FIRST_PSEUDO_REGISTER)) 1801 /* We may only emit an insn directly after P if we 1802 are not in the shadow of a live flags register. */ 1803 && GET_MODE (p) == VOIDmode) 1804 { 1805 search_end = q; 1806 q = insn; 1807 set2 = set; 1808 newconst = -insn_const; 1809 code = MINUS; 1810 } 1811 else 1812 break; 1813 } 1814 else 1815 { 1816 newconst = INTVAL (XEXP (SET_SRC (set2), 1)) - insn_const; 1817 /* Reject out of range shifts. */ 1818 if (code != PLUS 1819 && (newconst < 0 1820 || ((unsigned HOST_WIDE_INT) newconst 1821 >= (GET_MODE_BITSIZE (GET_MODE 1822 (SET_SRC (set2))))))) 1823 break; 1824 if (code == PLUS) 1825 { 1826 post_inc = q; 1827 if (SET_DEST (set2) != src) 1828 post_inc_set = set2; 1829 } 1830 } 1831 /* We use 1 as last argument to validate_change so that all 1832 changes are accepted or rejected together by apply_change_group 1833 when it is called by validate_replace_rtx . */ 1834 validate_change (q, &XEXP (SET_SRC (set2), 1), 1835 GEN_INT (newconst), 1); 1836 } 1837 validate_change (insn, recog_data.operand_loc[match_number], src, 1); 1838 if (validate_replace_rtx (dst, src_subreg, p)) 1839 success = 1; 1840 break; 1841 } 1842 1843 if (reg_overlap_mentioned_p (dst, PATTERN (p))) 1844 break; 1845 if (! src_note && reg_overlap_mentioned_p (src, PATTERN (p))) 1846 { 1847 /* INSN was already checked to be movable wrt. the registers that it 1848 sets / uses when we found no REG_DEAD note for src on it, but it 1849 still might clobber the flags register. We'll have to check that 1850 we won't insert it into the shadow of a live flags register when 1851 we finally know where we are to move it. */ 1852 overlap = p; 1853 src_note = find_reg_note (p, REG_DEAD, src); 1854 } 1855 1856 /* If we have passed a call instruction, and the pseudo-reg SRC is not 1857 already live across a call, then don't perform the optimization. */ 1858 if (GET_CODE (p) == CALL_INSN) 1859 { 1860 if (REG_N_CALLS_CROSSED (REGNO (src)) == 0) 1861 break; 1862 1863 num_calls++; 1864 1865 if (src_note) 1866 s_num_calls++; 1867 1868 } 1869 } 1870 1871 if (! success) 1872 return 0; 1873 1874 /* Remove the death note for DST from P. */ 1875 remove_note (p, dst_note); 1876 if (code == MINUS) 1877 { 1878 post_inc = emit_insn_after (copy_rtx (PATTERN (insn)), p); 1879 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT) 1880 && search_end 1881 && try_auto_increment (search_end, post_inc, 0, src, newconst, 1)) 1882 post_inc = 0; 1883 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (insn_const), 0); 1884 REG_N_SETS (REGNO (src))++; 1885 REG_LIVE_LENGTH (REGNO (src))++; 1886 } 1887 if (overlap) 1888 { 1889 /* The lifetime of src and dest overlap, 1890 but we can change this by moving insn. */ 1891 rtx pat = PATTERN (insn); 1892 if (src_note) 1893 remove_note (overlap, src_note); 1894 if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT) 1895 && code == PLUS 1896 && try_auto_increment (overlap, insn, 0, src, insn_const, 0)) 1897 insn = overlap; 1898 else 1899 { 1900 rtx notes = REG_NOTES (insn); 1901 1902 emit_insn_after_with_line_notes (pat, PREV_INSN (p), insn); 1903 delete_insn (insn); 1904 /* emit_insn_after_with_line_notes has no 1905 return value, so search for the new insn. */ 1906 insn = p; 1907 while (! INSN_P (insn) || PATTERN (insn) != pat) 1908 insn = PREV_INSN (insn); 1909 1910 REG_NOTES (insn) = notes; 1911 } 1912 } 1913 /* Sometimes we'd generate src = const; src += n; 1914 if so, replace the instruction that set src 1915 in the first place. */ 1916 1917 if (! overlap && (code == PLUS || code == MINUS)) 1918 { 1919 rtx note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 1920 rtx q, set2 = NULL_RTX; 1921 int num_calls2 = 0, s_length2 = 0; 1922 1923 if (note && CONSTANT_P (XEXP (note, 0))) 1924 { 1925 for (q = PREV_INSN (insn); q; q = PREV_INSN (q)) 1926 { 1927 /* ??? We can't scan past the end of a basic block without 1928 updating the register lifetime info 1929 (REG_DEAD/basic_block_live_at_start). */ 1930 if (perhaps_ends_bb_p (q)) 1931 { 1932 q = 0; 1933 break; 1934 } 1935 else if (! INSN_P (q)) 1936 continue; 1937 1938 s_length2++; 1939 if (reg_set_p (src, q)) 1940 { 1941 set2 = single_set (q); 1942 break; 1943 } 1944 if (reg_overlap_mentioned_p (src, PATTERN (q))) 1945 { 1946 q = 0; 1947 break; 1948 } 1949 if (GET_CODE (p) == CALL_INSN) 1950 num_calls2++; 1951 } 1952 if (q && set2 && SET_DEST (set2) == src && CONSTANT_P (SET_SRC (set2)) 1953 && validate_change (insn, &SET_SRC (set), XEXP (note, 0), 0)) 1954 { 1955 delete_insn (q); 1956 REG_N_SETS (REGNO (src))--; 1957 REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls2; 1958 REG_LIVE_LENGTH (REGNO (src)) -= s_length2; 1959 insn_const = 0; 1960 } 1961 } 1962 } 1963 1964 if ((HAVE_PRE_INCREMENT || HAVE_PRE_DECREMENT) 1965 && (code == PLUS || code == MINUS) && insn_const 1966 && try_auto_increment (p, insn, 0, src, insn_const, 1)) 1967 insn = p; 1968 else if ((HAVE_POST_INCREMENT || HAVE_POST_DECREMENT) 1969 && post_inc 1970 && try_auto_increment (p, post_inc, post_inc_set, src, newconst, 0)) 1971 post_inc = 0; 1972 /* If post_inc still prevails, try to find an 1973 insn where it can be used as a pre-in/decrement. 1974 If code is MINUS, this was already tried. */ 1975 if (post_inc && code == PLUS 1976 /* Check that newconst is likely to be usable 1977 in a pre-in/decrement before starting the search. */ 1978 && ((HAVE_PRE_INCREMENT && newconst > 0 && newconst <= MOVE_MAX) 1979 || (HAVE_PRE_DECREMENT && newconst < 0 && newconst >= -MOVE_MAX)) 1980 && exact_log2 (newconst)) 1981 { 1982 rtx q, inc_dest; 1983 1984 inc_dest = post_inc_set ? SET_DEST (post_inc_set) : src; 1985 for (q = post_inc; (q = NEXT_INSN (q)); ) 1986 { 1987 /* ??? We can't scan past the end of a basic block without updating 1988 the register lifetime info 1989 (REG_DEAD/basic_block_live_at_start). */ 1990 if (perhaps_ends_bb_p (q)) 1991 break; 1992 else if (! INSN_P (q)) 1993 continue; 1994 else if (src != inc_dest 1995 && (reg_overlap_mentioned_p (src, PATTERN (q)) 1996 || reg_set_p (src, q))) 1997 break; 1998 else if (reg_set_p (inc_dest, q)) 1999 break; 2000 else if (reg_overlap_mentioned_p (inc_dest, PATTERN (q))) 2001 { 2002 try_auto_increment (q, post_inc, 2003 post_inc_set, inc_dest, newconst, 1); 2004 break; 2005 } 2006 } 2007 } 2008 2009 /* Move the death note for DST to INSN if it is used 2010 there. */ 2011 if (reg_overlap_mentioned_p (dst, PATTERN (insn))) 2012 { 2013 XEXP (dst_note, 1) = REG_NOTES (insn); 2014 REG_NOTES (insn) = dst_note; 2015 } 2016 2017 if (src_note) 2018 { 2019 /* Move the death note for SRC from INSN to P. */ 2020 if (! overlap) 2021 remove_note (insn, src_note); 2022 XEXP (src_note, 1) = REG_NOTES (p); 2023 REG_NOTES (p) = src_note; 2024 2025 REG_N_CALLS_CROSSED (REGNO (src)) += s_num_calls; 2026 } 2027 2028 REG_N_SETS (REGNO (src))++; 2029 REG_N_SETS (REGNO (dst))--; 2030 2031 REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls; 2032 2033 REG_LIVE_LENGTH (REGNO (src)) += s_length; 2034 if (REG_LIVE_LENGTH (REGNO (dst)) >= 0) 2035 { 2036 REG_LIVE_LENGTH (REGNO (dst)) -= length; 2037 /* REG_LIVE_LENGTH is only an approximation after 2038 combine if sched is not run, so make sure that we 2039 still have a reasonable value. */ 2040 if (REG_LIVE_LENGTH (REGNO (dst)) < 2) 2041 REG_LIVE_LENGTH (REGNO (dst)) = 2; 2042 } 2043 if (regmove_dump_file) 2044 fprintf (regmove_dump_file, 2045 "Fixed operand %d of insn %d matching operand %d.\n", 2046 operand_number, INSN_UID (insn), match_number); 2047 return 1; 2048} 2049 2050 2051/* return nonzero if X is stable and mentions no regsiters but for 2052 mentioning SRC or mentioning / changing DST . If in doubt, presume 2053 it is unstable. 2054 The rationale is that we want to check if we can move an insn easily 2055 while just paying attention to SRC and DST. A register is considered 2056 stable if it has the RTX_UNCHANGING_P bit set, but that would still 2057 leave the burden to update REG_DEAD / REG_UNUSED notes, so we don't 2058 want any registers but SRC and DST. */ 2059static int 2060stable_and_no_regs_but_for_p (x, src, dst) 2061 rtx x, src, dst; 2062{ 2063 RTX_CODE code = GET_CODE (x); 2064 switch (GET_RTX_CLASS (code)) 2065 { 2066 case '<': case '1': case 'c': case '2': case 'b': case '3': 2067 { 2068 int i; 2069 const char *fmt = GET_RTX_FORMAT (code); 2070 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2071 if (fmt[i] == 'e' 2072 && ! stable_and_no_regs_but_for_p (XEXP (x, i), src, dst)) 2073 return 0; 2074 return 1; 2075 } 2076 case 'o': 2077 if (code == REG) 2078 return x == src || x == dst; 2079 /* If this is a MEM, look inside - there might be a register hidden in 2080 the address of an unchanging MEM. */ 2081 if (code == MEM 2082 && ! stable_and_no_regs_but_for_p (XEXP (x, 0), src, dst)) 2083 return 0; 2084 /* fall through */ 2085 default: 2086 return ! rtx_unstable_p (x); 2087 } 2088} 2089 2090/* Track stack adjustments and stack memory references. Attempt to 2091 reduce the number of stack adjustments by back-propagating across 2092 the memory references. 2093 2094 This is intended primarily for use with targets that do not define 2095 ACCUMULATE_OUTGOING_ARGS. It is of significantly more value to 2096 targets that define PREFERRED_STACK_BOUNDARY more aligned than 2097 STACK_BOUNDARY (e.g. x86), or if not all registers can be pushed 2098 (e.g. x86 fp regs) which would ordinarily have to be implemented 2099 as a sub/mov pair due to restrictions in calls.c. 2100 2101 Propagation stops when any of the insns that need adjusting are 2102 (a) no longer valid because we've exceeded their range, (b) a 2103 non-trivial push instruction, or (c) a call instruction. 2104 2105 Restriction B is based on the assumption that push instructions 2106 are smaller or faster. If a port really wants to remove all 2107 pushes, it should have defined ACCUMULATE_OUTGOING_ARGS. The 2108 one exception that is made is for an add immediately followed 2109 by a push. */ 2110 2111/* This structure records stack memory references between stack adjusting 2112 instructions. */ 2113 2114struct csa_memlist 2115{ 2116 HOST_WIDE_INT sp_offset; 2117 rtx insn, *mem; 2118 struct csa_memlist *next; 2119}; 2120 2121static int stack_memref_p PARAMS ((rtx)); 2122static rtx single_set_for_csa PARAMS ((rtx)); 2123static void free_csa_memlist PARAMS ((struct csa_memlist *)); 2124static struct csa_memlist *record_one_stack_memref 2125 PARAMS ((rtx, rtx *, struct csa_memlist *)); 2126static int try_apply_stack_adjustment 2127 PARAMS ((rtx, struct csa_memlist *, HOST_WIDE_INT, HOST_WIDE_INT)); 2128static void combine_stack_adjustments_for_block PARAMS ((basic_block)); 2129static int record_stack_memrefs PARAMS ((rtx *, void *)); 2130 2131 2132/* Main entry point for stack adjustment combination. */ 2133 2134void 2135combine_stack_adjustments () 2136{ 2137 int i; 2138 2139 for (i = 0; i < n_basic_blocks; ++i) 2140 combine_stack_adjustments_for_block (BASIC_BLOCK (i)); 2141} 2142 2143/* Recognize a MEM of the form (sp) or (plus sp const). */ 2144 2145static int 2146stack_memref_p (x) 2147 rtx x; 2148{ 2149 if (GET_CODE (x) != MEM) 2150 return 0; 2151 x = XEXP (x, 0); 2152 2153 if (x == stack_pointer_rtx) 2154 return 1; 2155 if (GET_CODE (x) == PLUS 2156 && XEXP (x, 0) == stack_pointer_rtx 2157 && GET_CODE (XEXP (x, 1)) == CONST_INT) 2158 return 1; 2159 2160 return 0; 2161} 2162 2163/* Recognize either normal single_set or the hack in i386.md for 2164 tying fp and sp adjustments. */ 2165 2166static rtx 2167single_set_for_csa (insn) 2168 rtx insn; 2169{ 2170 int i; 2171 rtx tmp = single_set (insn); 2172 if (tmp) 2173 return tmp; 2174 2175 if (GET_CODE (insn) != INSN 2176 || GET_CODE (PATTERN (insn)) != PARALLEL) 2177 return NULL_RTX; 2178 2179 tmp = PATTERN (insn); 2180 if (GET_CODE (XVECEXP (tmp, 0, 0)) != SET) 2181 return NULL_RTX; 2182 2183 for (i = 1; i < XVECLEN (tmp, 0); ++i) 2184 { 2185 rtx this = XVECEXP (tmp, 0, i); 2186 2187 /* The special case is allowing a no-op set. */ 2188 if (GET_CODE (this) == SET 2189 && SET_SRC (this) == SET_DEST (this)) 2190 ; 2191 else if (GET_CODE (this) != CLOBBER 2192 && GET_CODE (this) != USE) 2193 return NULL_RTX; 2194 } 2195 2196 return XVECEXP (tmp, 0, 0); 2197} 2198 2199/* Free the list of csa_memlist nodes. */ 2200 2201static void 2202free_csa_memlist (memlist) 2203 struct csa_memlist *memlist; 2204{ 2205 struct csa_memlist *next; 2206 for (; memlist ; memlist = next) 2207 { 2208 next = memlist->next; 2209 free (memlist); 2210 } 2211} 2212 2213/* Create a new csa_memlist node from the given memory reference. 2214 It is already known that the memory is stack_memref_p. */ 2215 2216static struct csa_memlist * 2217record_one_stack_memref (insn, mem, next_memlist) 2218 rtx insn, *mem; 2219 struct csa_memlist *next_memlist; 2220{ 2221 struct csa_memlist *ml; 2222 2223 ml = (struct csa_memlist *) xmalloc (sizeof (*ml)); 2224 2225 if (XEXP (*mem, 0) == stack_pointer_rtx) 2226 ml->sp_offset = 0; 2227 else 2228 ml->sp_offset = INTVAL (XEXP (XEXP (*mem, 0), 1)); 2229 2230 ml->insn = insn; 2231 ml->mem = mem; 2232 ml->next = next_memlist; 2233 2234 return ml; 2235} 2236 2237/* Attempt to apply ADJUST to the stack adjusting insn INSN, as well 2238 as each of the memories in MEMLIST. Return true on success. */ 2239 2240static int 2241try_apply_stack_adjustment (insn, memlist, new_adjust, delta) 2242 rtx insn; 2243 struct csa_memlist *memlist; 2244 HOST_WIDE_INT new_adjust, delta; 2245{ 2246 struct csa_memlist *ml; 2247 rtx set; 2248 2249 set = single_set_for_csa (insn); 2250 validate_change (insn, &XEXP (SET_SRC (set), 1), GEN_INT (new_adjust), 1); 2251 2252 for (ml = memlist; ml ; ml = ml->next) 2253 validate_change 2254 (ml->insn, ml->mem, 2255 replace_equiv_address_nv (*ml->mem, 2256 plus_constant (stack_pointer_rtx, 2257 ml->sp_offset - delta)), 1); 2258 2259 if (apply_change_group ()) 2260 { 2261 /* Succeeded. Update our knowledge of the memory references. */ 2262 for (ml = memlist; ml ; ml = ml->next) 2263 ml->sp_offset -= delta; 2264 2265 return 1; 2266 } 2267 else 2268 return 0; 2269} 2270 2271/* Called via for_each_rtx and used to record all stack memory references in 2272 the insn and discard all other stack pointer references. */ 2273struct record_stack_memrefs_data 2274{ 2275 rtx insn; 2276 struct csa_memlist *memlist; 2277}; 2278 2279static int 2280record_stack_memrefs (xp, data) 2281 rtx *xp; 2282 void *data; 2283{ 2284 rtx x = *xp; 2285 struct record_stack_memrefs_data *d = 2286 (struct record_stack_memrefs_data *) data; 2287 if (!x) 2288 return 0; 2289 switch (GET_CODE (x)) 2290 { 2291 case MEM: 2292 if (!reg_mentioned_p (stack_pointer_rtx, x)) 2293 return -1; 2294 /* We are not able to handle correctly all possible memrefs containing 2295 stack pointer, so this check is necessary. */ 2296 if (stack_memref_p (x)) 2297 { 2298 d->memlist = record_one_stack_memref (d->insn, xp, d->memlist); 2299 return -1; 2300 } 2301 return 1; 2302 case REG: 2303 /* ??? We want be able to handle non-memory stack pointer 2304 references later. For now just discard all insns refering to 2305 stack pointer outside mem expressions. We would probably 2306 want to teach validate_replace to simplify expressions first. 2307 2308 We can't just compare with STACK_POINTER_RTX because the 2309 reference to the stack pointer might be in some other mode. 2310 In particular, an explict clobber in an asm statement will 2311 result in a QImode clober. */ 2312 if (REGNO (x) == STACK_POINTER_REGNUM) 2313 return 1; 2314 break; 2315 default: 2316 break; 2317 } 2318 return 0; 2319} 2320 2321/* Subroutine of combine_stack_adjustments, called for each basic block. */ 2322 2323static void 2324combine_stack_adjustments_for_block (bb) 2325 basic_block bb; 2326{ 2327 HOST_WIDE_INT last_sp_adjust = 0; 2328 rtx last_sp_set = NULL_RTX; 2329 struct csa_memlist *memlist = NULL; 2330 rtx pending_delete; 2331 rtx insn, next; 2332 struct record_stack_memrefs_data data; 2333 2334 for (insn = bb->head; ; insn = next) 2335 { 2336 rtx set; 2337 2338 pending_delete = NULL_RTX; 2339 next = NEXT_INSN (insn); 2340 2341 if (! INSN_P (insn)) 2342 goto processed; 2343 2344 set = single_set_for_csa (insn); 2345 if (set) 2346 { 2347 rtx dest = SET_DEST (set); 2348 rtx src = SET_SRC (set); 2349 2350 /* Find constant additions to the stack pointer. */ 2351 if (dest == stack_pointer_rtx 2352 && GET_CODE (src) == PLUS 2353 && XEXP (src, 0) == stack_pointer_rtx 2354 && GET_CODE (XEXP (src, 1)) == CONST_INT) 2355 { 2356 HOST_WIDE_INT this_adjust = INTVAL (XEXP (src, 1)); 2357 2358 /* If we've not seen an adjustment previously, record 2359 it now and continue. */ 2360 if (! last_sp_set) 2361 { 2362 last_sp_set = insn; 2363 last_sp_adjust = this_adjust; 2364 goto processed; 2365 } 2366 2367 /* If not all recorded memrefs can be adjusted, or the 2368 adjustment is now too large for a constant addition, 2369 we cannot merge the two stack adjustments. 2370 2371 Also we need to be carefull to not move stack pointer 2372 such that we create stack accesses outside the allocated 2373 area. We can combine an allocation into the first insn, 2374 or a deallocation into the second insn. We can not 2375 combine an allocation followed by a deallocation. 2376 2377 The only somewhat frequent occurrence of the later is when 2378 a function allocates a stack frame but does not use it. 2379 For this case, we would need to analyze rtl stream to be 2380 sure that allocated area is really unused. This means not 2381 only checking the memory references, but also all registers 2382 or global memory references possibly containing a stack 2383 frame address. 2384 2385 Perhaps the best way to address this problem is to teach 2386 gcc not to allocate stack for objects never used. */ 2387 2388 /* Combine an allocation into the first instruction. */ 2389 if (STACK_GROWS_DOWNWARD ? this_adjust <= 0 : this_adjust >= 0) 2390 { 2391 if (try_apply_stack_adjustment (last_sp_set, memlist, 2392 last_sp_adjust + this_adjust, 2393 this_adjust)) 2394 { 2395 /* It worked! */ 2396 pending_delete = insn; 2397 last_sp_adjust += this_adjust; 2398 goto processed; 2399 } 2400 } 2401 2402 /* Otherwise we have a deallocation. Do not combine with 2403 a previous allocation. Combine into the second insn. */ 2404 else if (STACK_GROWS_DOWNWARD 2405 ? last_sp_adjust >= 0 : last_sp_adjust <= 0) 2406 { 2407 if (try_apply_stack_adjustment (insn, memlist, 2408 last_sp_adjust + this_adjust, 2409 -last_sp_adjust)) 2410 { 2411 /* It worked! */ 2412 delete_insn (last_sp_set); 2413 last_sp_set = insn; 2414 last_sp_adjust += this_adjust; 2415 free_csa_memlist (memlist); 2416 memlist = NULL; 2417 goto processed; 2418 } 2419 } 2420 2421 /* Combination failed. Restart processing from here. */ 2422 free_csa_memlist (memlist); 2423 memlist = NULL; 2424 last_sp_set = insn; 2425 last_sp_adjust = this_adjust; 2426 goto processed; 2427 } 2428 2429 /* Find a predecrement of exactly the previous adjustment and 2430 turn it into a direct store. Obviously we can't do this if 2431 there were any intervening uses of the stack pointer. */ 2432 if (memlist == NULL 2433 && GET_CODE (dest) == MEM 2434 && ((GET_CODE (XEXP (dest, 0)) == PRE_DEC 2435 && (last_sp_adjust 2436 == (HOST_WIDE_INT) GET_MODE_SIZE (GET_MODE (dest)))) 2437 || (GET_CODE (XEXP (dest, 0)) == PRE_MODIFY 2438 && GET_CODE (XEXP (XEXP (dest, 0), 1)) == PLUS 2439 && XEXP (XEXP (XEXP (dest, 0), 1), 0) == stack_pointer_rtx 2440 && (GET_CODE (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 2441 == CONST_INT) 2442 && (INTVAL (XEXP (XEXP (XEXP (dest, 0), 1), 1)) 2443 == -last_sp_adjust))) 2444 && XEXP (XEXP (dest, 0), 0) == stack_pointer_rtx 2445 && ! reg_mentioned_p (stack_pointer_rtx, src) 2446 && memory_address_p (GET_MODE (dest), stack_pointer_rtx) 2447 && validate_change (insn, &SET_DEST (set), 2448 replace_equiv_address (dest, 2449 stack_pointer_rtx), 2450 0)) 2451 { 2452 if (last_sp_set == bb->head) 2453 bb->head = NEXT_INSN (last_sp_set); 2454 delete_insn (last_sp_set); 2455 2456 free_csa_memlist (memlist); 2457 memlist = NULL; 2458 last_sp_set = NULL_RTX; 2459 last_sp_adjust = 0; 2460 goto processed; 2461 } 2462 } 2463 2464 data.insn = insn; 2465 data.memlist = memlist; 2466 if (GET_CODE (insn) != CALL_INSN && last_sp_set 2467 && !for_each_rtx (&PATTERN (insn), record_stack_memrefs, &data)) 2468 { 2469 memlist = data.memlist; 2470 goto processed; 2471 } 2472 memlist = data.memlist; 2473 2474 /* Otherwise, we were not able to process the instruction. 2475 Do not continue collecting data across such a one. */ 2476 if (last_sp_set 2477 && (GET_CODE (insn) == CALL_INSN 2478 || reg_mentioned_p (stack_pointer_rtx, PATTERN (insn)))) 2479 { 2480 free_csa_memlist (memlist); 2481 memlist = NULL; 2482 last_sp_set = NULL_RTX; 2483 last_sp_adjust = 0; 2484 } 2485 2486 processed: 2487 if (insn == bb->end) 2488 break; 2489 2490 if (pending_delete) 2491 delete_insn (pending_delete); 2492 } 2493 2494 if (pending_delete) 2495 delete_insn (pending_delete); 2496} 2497