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