gcc/regmove.c

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