gcc/regmove.c

   1 /* Move registers around to reduce number of move instructions needed.
   2    Copyright (C) 1987, 88, 89, 92-5, 1996, 1997 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 /* This module looks for cases where matching constraints would force
  22    an instruction to need a reload, and this reload would be a register
  23    to register move.  It then attempts to change the registers used by the
  24    instruction to avoid the move instruction.  */
  25
  26 #include "config.h"
  27 #ifdef __STDC__
  28 #include <stdarg.h>
  29 #else
  30 #include <varargs.h>
  31 #endif
  32
  33 /* Must precede rtl.h for FFS.  */
  34 #include <stdio.h>
  35
  36 #include "rtl.h"
  37 #include "insn-config.h"
  38 #include "recog.h"
  39 #include "output.h"
  40 #include "reload.h"
  41 #include "regs.h"
  42
  43 static int stable_but_for_p PROTO((rtx, rtx, rtx));
  44
  45 #if defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT) \
  46     || defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT)
  47
  48 /* INC_INSN is an instruction that adds INCREMENT to REG.
  49    Try to fold INC_INSN as a post/pre in/decrement into INSN.
  50    Iff INC_INSN_SET is nonzero, inc_insn has a destination different from src.
  51    Return nonzero for success.  */
  52 static int
  53 try_auto_increment (insn, inc_insn, inc_insn_set, reg, increment, pre)
  54      rtx reg, insn, inc_insn ,inc_insn_set;
  55      HOST_WIDE_INT increment;
  56      int pre;
  57 {
  58   enum rtx_code inc_code;
  59
  60   rtx pset = single_set (insn);
  61   if (pset)
  62     {
  63       /* Can't use the size of SET_SRC, we might have something like
  64          (sign_extend:SI (mem:QI ...  */
  65       rtx use = find_use_as_address (pset, reg, 0);
  66       if (use != 0 && use != (rtx) 1)
  67         {
  68           int size = GET_MODE_SIZE (GET_MODE (use));
  69           if (0
  70 #ifdef HAVE_POST_INCREMENT
  71               || (pre == 0 && (inc_code = POST_INC, increment == size))
  72 #endif
  73 #ifdef HAVE_PRE_INCREMENT
  74               || (pre == 1 && (inc_code = PRE_INC, increment == size))
  75 #endif
  76 #ifdef HAVE_POST_DECREMENT
  77               || (pre == 0 && (inc_code = POST_DEC, increment == -size))
  78 #endif
  79 #ifdef HAVE_PRE_DECREMENT
  80               || (pre == 1 && (inc_code = PRE_DEC, increment == -size))
  81 #endif
  82           )
  83             {
  84               if (inc_insn_set)
  85                 validate_change
  86                   (inc_insn,
  87                    &SET_SRC (inc_insn_set),
  88                    XEXP (SET_SRC (inc_insn_set), 0), 1);
  89               validate_change (insn, &XEXP (use, 0),
  90                                gen_rtx (inc_code,
  91                                         Pmode,
  92                                         reg), 1);
  93               if (apply_change_group ())
  94                 {
  95                   REG_NOTES (insn)
  96                     = gen_rtx (EXPR_LIST, REG_INC,
  97                                reg, REG_NOTES (insn));
  98                   if (! inc_insn_set)
  99                     {
 100                       PUT_CODE (inc_insn, NOTE);
 101                       NOTE_LINE_NUMBER (inc_insn) = NOTE_INSN_DELETED;
 102                       NOTE_SOURCE_FILE (inc_insn) = 0;
 103                     }
 104                   return 1;
 105                 }
 106             }
 107         }
 108     }
 109   return 0;
 110 }
 111 #endif  /* defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT) */
 112
 113 void
 114 regmove_optimize (f, nregs, regmove_dump_file)
 115      rtx f;
 116      int nregs;
 117      FILE *regmove_dump_file;
 118 {
 119 #ifdef REGISTER_CONSTRAINTS
 120   rtx insn;
 121   int matches[MAX_RECOG_OPERANDS][MAX_RECOG_OPERANDS];
 122   int modified[MAX_RECOG_OPERANDS];
 123   int early_clobber[MAX_RECOG_OPERANDS];
 124   int commutative;
 125   int pass;
 126
 127   /* A forward/backward pass.  Replace output operands with input operands.  */
 128
 129   for (pass = 0; pass < 2; pass++)
 130     {
 131       if (regmove_dump_file)
 132         fprintf (regmove_dump_file, "Starting %s pass...\n",
 133                  pass ? "backward" : "forward");
 134
 135       for (insn = pass ? get_last_insn () : f; insn;
 136            insn = pass ? PREV_INSN (insn) : NEXT_INSN (insn))
 137         {
 138           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 139             {
 140               int insn_code_number = recog_memoized (insn);
 141               int operand_number, match_number;
 142
 143               if (insn_code_number < 0)
 144                 continue;
 145
 146               insn_extract (insn);
 147               if (! constrain_operands (insn_code_number, 0))
 148                 continue;
 149
 150               commutative = -1;
 151
 152               /* Must initialize this before the loop, because the code for
 153                  the commutative case may set matches for operands other than
 154                  the current one.  */
 155               bzero ((char *)matches, sizeof (matches));
 156
 157               for (operand_number = 0;
 158                    operand_number < insn_n_operands[insn_code_number];
 159                    operand_number++)
 160                 {
 161                   int output_operand = 0;
 162                   int matching_operand = operand_number;
 163                   char *p, c;
 164                   int i = 0;
 165
 166                   modified[operand_number] = 0;
 167                   early_clobber[operand_number] = 0;
 168
 169                   p = insn_operand_constraint[insn_code_number][operand_number];
 170
 171                   if (*p == '=')
 172                     modified[operand_number] = 2;
 173                   else if (*p == '+')
 174                     modified[operand_number] = 1;
 175
 176                   for (;*p && i < which_alternative; p++)
 177                     if (*p == ',')
 178                       i++;
 179
 180                   while ((c = *p++) != '\0' && c != ',')
 181                     switch (c)
 182                       {
 183                       case '=':
 184                         break;
 185                       case '+':
 186                         break;
 187                       case '&':
 188                         early_clobber[operand_number] = 1;
 189                         break;
 190                       case '%':
 191                         commutative = operand_number;
 192                         break;
 193                       case '0': case '1': case '2': case '3': case '4':
 194                       case '5': case '6': case '7': case '8': case '9':
 195                         c -= '0';
 196                         matches[operand_number][c] = 1;
 197                         if (commutative >= 0)
 198                           {
 199                             if (c == commutative || c == commutative + 1)
 200                               {
 201                                 int other = c + (c == commutative ? 1 : -1);
 202                                 matches[operand_number][other] = 1;
 203                               }
 204                             if (operand_number == commutative
 205                                 || operand_number == commutative + 1)
 206                               {
 207                                 int other = (operand_number
 208                                              + (operand_number == commutative
 209                                                 ? 1 : -1));
 210                                 matches[other][c] = 1;
 211                               }
 212                           }
 213                         break;
 214                       }
 215                 }
 216
 217               /* Now scan through the operands looking for a source operand
 218                  which is supposed to match the destination operand.
 219                  Then scan forward for an instruction which uses the dest
 220                  operand.
 221                  If it dies there, then replace the dest in both operands with
 222                  the source operand.  */
 223
 224               for (operand_number = 0;
 225                    operand_number < insn_n_operands[insn_code_number];
 226                    operand_number++)
 227                 {
 228                   for (match_number = 0;
 229                        match_number < insn_n_operands[insn_code_number];
 230                        match_number++)
 231                     {
 232                       rtx set, p, src, dst, src_subreg;
 233                       rtx post_inc = 0, post_inc_set = 0, search_end = 0;
 234                       rtx src_note, dst_note;
 235                       int success = 0;
 236                       int num_calls = 0;
 237                       enum rtx_code code = NOTE;
 238                       HOST_WIDE_INT insn_const, newconst;
 239                       rtx overlap = 0; /* need to move insn ? */
 240
 241                       /* Nothing to do if the two operands aren't supposed to
 242                          match.  */
 243                       if (matches[operand_number][match_number] == 0)
 244                         continue;
 245
 246                       src = recog_operand[operand_number];
 247                       dst = recog_operand[match_number];
 248
 249                       if (GET_CODE (src) != REG
 250                           || REGNO (src) < FIRST_PSEUDO_REGISTER)
 251                         continue;
 252
 253                       src_subreg = src;
 254                       if (GET_CODE (dst) == SUBREG
 255                           && GET_MODE_SIZE (GET_MODE (dst))
 256                              >= GET_MODE_SIZE (GET_MODE (SUBREG_REG (dst))))
 257                         {
 258                           src_subreg
 259                             = gen_rtx(SUBREG,  GET_MODE (SUBREG_REG (dst)),
 260                                       src, SUBREG_WORD (dst));
 261                           dst = SUBREG_REG (dst);
 262                         }
 263                       if (GET_CODE (dst) != REG
 264                           || REGNO (dst) < FIRST_PSEUDO_REGISTER)
 265                         continue;
 266
 267                       /* If the operands already match, then there is nothing
 268                          to do.  */
 269                       if (operands_match_p (src, dst))
 270                         continue;
 271
 272                       set = single_set (insn);
 273                       if (! set)
 274                         continue;
 275
 276                       /* operand_number/src must be a read-only operand, and
 277                          match_operand/dst must be a write-only operand.  */
 278                       if (modified[match_number] != 2)
 279                         continue;
 280
 281                       if (early_clobber[match_number] == 1)
 282                         continue;
 283
 284                       if (modified[operand_number] != 0)
 285                         continue;
 286
 287                       /* Make sure match_operand is the destination.  */
 288                       if (recog_operand[match_number] != SET_DEST (set))
 289                         continue;
 290
 291                       src_note = find_reg_note (insn, REG_DEAD, src);
 292
 293                       if (! src_note)
 294                         {
 295                           /* Look for (set (regX) (op regA constX))
 296                                       (set (regY) (op regA constY))
 297                              and change that to
 298                                       (set (regA) (op regA constX)).
 299                                       (set (regY) (op regA constY-constX)).
 300                              This works for add and shift operations, if
 301                              regA is dead after or set by the second insn.  */
 302
 303                           code = GET_CODE (SET_SRC (set));
 304                           if ((code == PLUS || code == LSHIFTRT
 305                                || code == ASHIFT || code == ASHIFTRT)
 306                               && XEXP (SET_SRC (set), 0) == src
 307                               && (GET_CODE (XEXP (SET_SRC (set), 1))
 308                                   == CONST_INT))
 309                             insn_const = INTVAL (XEXP (SET_SRC (set), 1));
 310                           else if (! stable_but_for_p (SET_SRC (set), src, dst))
 311                             continue;
 312                           else
 313                             /* We might find a src_note while scanning.  */
 314                             code = NOTE;
 315                         }
 316
 317                       if (regmove_dump_file)
 318                         fprintf (regmove_dump_file,
 319                                  "Could fix operand %d of insn %d matching operand %d.\n",
 320                                  operand_number, INSN_UID (insn), match_number);
 321
 322                       /* ??? If src is set once, and is set equal to a
 323                          constant, then do not use it for this optimization,
 324                          as this would make it no longer equivalent to a
 325                          constant?  */
 326
 327                       /* Scan forward to find the next instruction that
 328                          uses the output operand.  If the operand dies here,
 329                          then replace it in both instructions with
 330                          operand_number.  */
 331
 332                       for (p = NEXT_INSN (insn); p; p = NEXT_INSN (p))
 333                         {
 334                           if (GET_CODE (p) == CODE_LABEL
 335                               || GET_CODE (p) == JUMP_INSN
 336                               || (GET_CODE (p) == NOTE
 337                                   && ((NOTE_LINE_NUMBER (p)
 338                                        == NOTE_INSN_LOOP_BEG)
 339                                       || (NOTE_LINE_NUMBER (p)
 340                                           == NOTE_INSN_LOOP_END))))
 341                             break;
 342
 343                           if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
 344                             continue;
 345
 346                           if (reg_set_p (src, p) || reg_set_p (dst, p)
 347                               || (GET_CODE (PATTERN (p)) == USE
 348                                   && reg_overlap_mentioned_p (src,
 349                                                               XEXP (PATTERN (p),
 350                                                               0))))
 351                             break;
 352
 353                           /* See if all of DST dies in P.  This test is
 354                              slightly more conservative than it needs to be.  */
 355                           if ((dst_note
 356                                 = find_regno_note (p, REG_DEAD, REGNO (dst)))
 357                               && (GET_MODE (XEXP (dst_note, 0))
 358                                   == GET_MODE (dst)))
 359                             {
 360                               if (! src_note)
 361                                 {
 362                                   rtx q;
 363                                   rtx set2;
 364
 365                                   /* If an optimization is done, the value
 366                                      of SRC while P is executed will be
 367                                      changed.  Check that this is OK.  */
 368                                   if (reg_overlap_mentioned_p (src,
 369                                                                PATTERN (p)))
 370                                     break;
 371                                   for (q = p; q; q = NEXT_INSN (q))
 372                                     {
 373                                       if (GET_CODE (q) == CODE_LABEL
 374                                           || GET_CODE (q) == JUMP_INSN
 375                                           || (GET_CODE (q) == NOTE
 376                                               && ((NOTE_LINE_NUMBER (q)
 377                                                    == NOTE_INSN_LOOP_BEG)
 378                                                   || (NOTE_LINE_NUMBER (q)
 379                                                       == NOTE_INSN_LOOP_END))))
 380                                         {
 381                                           q = 0;
 382                                           break;
 383                                         }
 384                                       if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
 385                                         continue;
 386                                       if (reg_overlap_mentioned_p (src,
 387                                                                    PATTERN (q))
 388                                           || reg_set_p (src, q))
 389                                         break;
 390                                     }
 391                                   if (q)
 392                                     set2 = single_set (q);
 393                                   if (! q || ! set2
 394                                       || GET_CODE (SET_SRC (set2)) != code
 395                                       || XEXP (SET_SRC (set2), 0) != src
 396                                       || (GET_CODE (XEXP (SET_SRC (set2), 1))
 397                                           != CONST_INT)
 398                                       || (SET_DEST (set2) != src
 399                                           && !find_reg_note (q, REG_DEAD, src)))
 400                                     {
 401                                       /* If this is a PLUS, we can still save
 402                                          a register by doing
 403                                          src += insn_const;
 404                                          P;
 405                                          src -= insn_const; .
 406                                          This also gives opportunities for
 407                                          subsequent optimizations in the
 408                                          backward pass, so do it there.  */
 409                                       if (code == PLUS && pass == 1
 410 #ifdef HAVE_cc0
 411                                           /* We man not emit an insn directly
 412                                              after P if the latter sets CC0.  */
 413                                           && ! sets_cc0_p (PATTERN (p))
 414 #endif
 415                                           )
 416
 417                                         {
 418                                           search_end = q;
 419                                           q = insn;
 420                                           set2 = set;
 421                                           newconst = -insn_const;
 422                                           code = MINUS;
 423                                         }
 424                                       else
 425                                         break;
 426                                     }
 427                                   else
 428                                     {
 429                                       newconst
 430                                         = (INTVAL (XEXP (SET_SRC (set2), 1))
 431                                            - insn_const);
 432                                       /* Reject out of range shifts.  */
 433                                       if (code != PLUS
 434                                           && (newconst < 0
 435                                               || (newconst
 436                                                   >= GET_MODE_BITSIZE (GET_MODE (SET_SRC (set2))))))
 437                                         break;
 438                                       if (code == PLUS)
 439                                         {
 440                                           post_inc = q;
 441                                           if (SET_DEST (set2) != src)
 442                                             post_inc_set = set2;
 443                                         }
 444                                     }
 445                                   /* We use 1 as last argument to
 446                                      validate_change so that all changes
 447                                      are accepted or rejected together by
 448                                      apply_change_group when it is called
 449                                      by validate_replace_rtx .  */
 450                                   validate_change (q, &XEXP (SET_SRC (set2), 1),
 451                                                    GEN_INT (newconst), 1);
 452                                 }
 453                               validate_change (insn,
 454                                                recog_operand_loc[match_number],
 455                                                src, 1);
 456                               if (validate_replace_rtx (dst, src_subreg, p))
 457                                 success = 1;
 458                               break;
 459                             }
 460
 461                           if (reg_overlap_mentioned_p (dst, PATTERN (p)))
 462                             break;
 463                           if (! src_note
 464                               && reg_overlap_mentioned_p (src, PATTERN (p)))
 465                             {
 466                               /* INSN was already checked to be movable when
 467                                  we found no REG_DEAD note for src on it.  */
 468                               overlap = p;
 469                               src_note = find_reg_note (p, REG_DEAD, src);
 470                             }
 471
 472                           /* If we have passed a call instruction, and the
 473                              pseudo-reg SRC is not already live across a call,
 474                              then don't perform the optimization.  */
 475                           if (GET_CODE (p) == CALL_INSN)
 476                             {
 477                               num_calls++;
 478
 479                               if (REG_N_CALLS_CROSSED (REGNO (src)) == 0)
 480                                 break;
 481                             }
 482                         }
 483
 484                       if (success)
 485                         {
 486                           /* Remove the death note for DST from P.  */
 487                           remove_note (p, dst_note);
 488                           if (code == MINUS)
 489                             {
 490                               post_inc
 491                                 = emit_insn_after (copy_rtx (PATTERN (insn)),
 492                                                    p);
 493 #if defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT)
 494                               if (search_end
 495                                   && try_auto_increment (search_end, post_inc,
 496                                                          0, src, newconst, 1))
 497                                 post_inc = 0;
 498 #endif
 499                               validate_change (insn, &XEXP (SET_SRC (set), 1),
 500                                                GEN_INT (insn_const), 0);
 501                               REG_N_SETS (REGNO (src))++;
 502                             }
 503                           if (overlap)
 504                             {
 505                               /* The lifetime of src and dest overlap,
 506                                  but we can change this by moving insn.  */
 507                               rtx pat = PATTERN (insn);
 508                               if (src_note)
 509                                 remove_note (overlap, src_note);
 510 #if defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT)
 511                               if (code == PLUS
 512                                   && try_auto_increment (overlap, insn, 0,
 513                                                          src, insn_const, 0))
 514                                 insn = overlap;
 515                               else
 516 #endif
 517                                 {
 518                                   rtx notes = REG_NOTES (insn);
 519
 520                                   emit_insn_after_with_line_notes
 521                                     (pat, PREV_INSN (p), insn);
 522                                   PUT_CODE (insn, NOTE);
 523                                   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 524                                   NOTE_SOURCE_FILE (insn) = 0;
 525                                   /* emit_insn_after_with_line_notes
 526                                      has no return value, so search
 527                                      for the new insn.  */
 528                                   for (insn = p; PATTERN (insn) != pat; )
 529                                     insn = PREV_INSN (insn);
 530
 531                                   REG_NOTES (insn) = notes;
 532                                 }
 533                             }
 534                           /* Sometimes we'd generate src = const; src += n;
 535                              if so, replace the instruction that set src
 536                              in the first place.  */
 537
 538                           if (! overlap && (code == PLUS || code == MINUS))
 539                             {
 540                               rtx note
 541                                 = find_reg_note (insn, REG_EQUAL, NULL_RTX);
 542                               rtx q, set2;
 543                               int num_calls2 = 0;
 544
 545                               if (note && CONSTANT_P (XEXP (note, 0)))
 546                                 {
 547                                   for (q = PREV_INSN (insn); q;
 548                                        q = PREV_INSN(q))
 549                                     {
 550                                       if (GET_CODE (q) == JUMP_INSN)
 551                                         {
 552                                           q = 0;
 553                                           break;
 554                                         }
 555                                       if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
 556                                         continue;
 557                                       if (reg_set_p (src, q))
 558                                         {
 559                                           set2 = single_set (q);
 560                                           break;
 561                                         }
 562                                       if (reg_overlap_mentioned_p (src,
 563                                           PATTERN (q)))
 564                                         {
 565                                           q = 0;
 566                                           break;
 567                                         }
 568                                       if (GET_CODE (p) == CALL_INSN)
 569                                         num_calls2++;
 570                                     }
 571                                   if (q && set2 && SET_DEST (set2) == src
 572                                       && CONSTANT_P (SET_SRC (set2))
 573                                       && validate_change (insn, &SET_SRC (set),
 574                                                           XEXP (note, 0), 0))
 575                                     {
 576                                       PUT_CODE (q, NOTE);
 577                                       NOTE_LINE_NUMBER (q) = NOTE_INSN_DELETED;
 578                                       NOTE_SOURCE_FILE (q) = 0;
 579                                       REG_N_SETS (REGNO (src))--;
 580                                       REG_N_CALLS_CROSSED (REGNO (src))
 581                                         -= num_calls2;
 582                                       insn_const = 0;
 583                                     }
 584                                 }
 585                             }
 586                           if (0) ;
 587 #if defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT)
 588                           else if ((code == PLUS || code == MINUS)
 589                                    && insn_const
 590                                    && try_auto_increment (p, insn, 0,
 591                                                           src, insn_const, 1))
 592                             insn = p;
 593 #endif
 594 #if defined (HAVE_POST_INCREMENT) || defined (HAVE_POST_DECREMENT)
 595                           else if (post_inc
 596                                    && try_auto_increment (p, post_inc,
 597                                                           post_inc_set, src,
 598                                                           newconst, 0))
 599                             post_inc = 0;
 600 #endif
 601 #if defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT)
 602                           /* If post_inc still prevails, try to find an
 603                              insn where it can be used as a pre-in/decrement.
 604                              If code is MINUS, this was already tried.  */
 605                           if (post_inc && code == PLUS
 606                           /* Check that newconst is likely to be usable
 607                              in a pre-in/decrement before starting the
 608                              search.  */
 609                               && (0
 610 #if defined (HAVE_PRE_INCREMENT)
 611                                   || (newconst > 0 && newconst <= MOVE_MAX)
 612 #endif
 613 #if defined (HAVE_PRE_DECREMENT)
 614                                   || (newconst < 0 && newconst >= -MOVE_MAX)
 615 #endif
 616                                  ) && exact_log2 (newconst))
 617                             {
 618                               rtx q, inc_dest;
 619
 620                               inc_dest
 621                                 = post_inc_set ? SET_DEST (post_inc_set) : src;
 622                               for (q = post_inc; q = NEXT_INSN (q); )
 623                                 {
 624                                   if (GET_CODE (q) == CODE_LABEL
 625                                       || GET_CODE (q) == JUMP_INSN
 626                                       || (GET_CODE (q) == NOTE
 627                                           && ((NOTE_LINE_NUMBER (q)
 628                                                == NOTE_INSN_LOOP_BEG)
 629                                               || (NOTE_LINE_NUMBER (q)
 630                                                   == NOTE_INSN_LOOP_END))))
 631                                     break;
 632                                   if (GET_RTX_CLASS (GET_CODE (q)) != 'i')
 633                                     continue;
 634                                   if (src != inc_dest
 635                                       && (reg_overlap_mentioned_p (src,
 636                                                                    PATTERN (q))
 637                                           || reg_set_p (src, q)))
 638                                     break;
 639                                   if (reg_set_p (inc_dest, q))
 640                                     break;
 641                                   if (reg_overlap_mentioned_p (inc_dest,
 642                                                                PATTERN (q)))
 643                                     {
 644                                       try_auto_increment (q, post_inc,
 645                                                           post_inc_set,
 646                                                           inc_dest,
 647                                                           newconst, 1);
 648                                       break;
 649                                     }
 650                                 }
 651                             }
 652 #endif /* defined (HAVE_PRE_INCREMENT) || defined (HAVE_PRE_DECREMENT) */
 653                           /* Move the death note for DST to INSN if it is used
 654                              there.  */
 655                           if (reg_overlap_mentioned_p (dst, PATTERN (insn)))
 656                             {
 657                               XEXP (dst_note, 1) = REG_NOTES (insn);
 658                               REG_NOTES (insn) = dst_note;
 659                             }
 660
 661                           if (src_note)
 662                             {
 663                               /* Move the death note for SRC from INSN to P.  */
 664                               if (! overlap)
 665                                 remove_note (insn, src_note);
 666                               XEXP (src_note, 1) = REG_NOTES (p);
 667                               REG_NOTES (p) = src_note;
 668
 669                               REG_N_CALLS_CROSSED (REGNO (src)) += num_calls;
 670                             }
 671
 672                           REG_N_SETS (REGNO (src))++;
 673                           REG_N_SETS (REGNO (dst))--;
 674
 675                           REG_N_CALLS_CROSSED (REGNO (dst)) -= num_calls;
 676
 677                           /* ??? Must adjust reg_live_length, and reg_n_refs for
 678                              both registers.  Must keep track of loop_depth in
 679                              order to get reg_n_refs adjustment correct.  */
 680
 681                           if (regmove_dump_file)
 682                             fprintf (regmove_dump_file,
 683                                      "Fixed operand %d of insn %d matching operand %d.\n",
 684                                      operand_number, INSN_UID (insn),
 685                                      match_number);
 686
 687                           goto done_forwards;
 688                         }
 689                     }
 690                 }
 691             done_forwards:
 692               ;
 693             }
 694         }
 695     }
 696
 697   /* A backward pass.  Replace input operands with output operands.  */
 698
 699   if (regmove_dump_file)
 700     fprintf (regmove_dump_file, "Starting backward pass...\n");
 701
 702   for (insn = get_last_insn (); insn; insn = PREV_INSN (insn))
 703     {
 704       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 705         {
 706           int insn_code_number = recog_memoized (insn);
 707           int operand_number, match_number;
 708
 709           if (insn_code_number < 0)
 710             continue;
 711
 712           insn_extract (insn);
 713           if (! constrain_operands (insn_code_number, 0))
 714             continue;
 715
 716           commutative = -1;
 717
 718           /* Must initialize this before the loop, because the code for
 719              the commutative case may set matches for operands other than
 720              the current one.  */
 721           bzero ((char *) matches, sizeof (matches));
 722
 723           for (operand_number = 0;
 724                operand_number < insn_n_operands[insn_code_number];
 725                operand_number++)
 726             {
 727               int output_operand = 0;
 728               int matching_operand = operand_number;
 729               char *p, c;
 730               int i = 0;
 731
 732               modified[operand_number] = 0;
 733               early_clobber[operand_number] = 0;
 734
 735               p = insn_operand_constraint[insn_code_number][operand_number];
 736
 737               if (*p == '=')
 738                 modified[operand_number] = 2;
 739               else if (*p == '+')
 740                 modified[operand_number] = 1;
 741
 742               for (; *p && i < which_alternative; p++)
 743                 if (*p == ',')
 744                   i++;
 745
 746               while ((c = *p++) != '\0' && c != ',')
 747                 switch (c)
 748                   {
 749                   case '=':
 750                     break;
 751                   case '+':
 752                     break;
 753                   case '&':
 754                     early_clobber[operand_number] = 1;
 755                     break;
 756                   case '%':
 757                     commutative = operand_number;
 758                     break;
 759                   case '0': case '1': case '2': case '3': case '4':
 760                   case '5': case '6': case '7': case '8': case '9':
 761                     c -= '0';
 762                     matches[c][operand_number] = 1;
 763                     if (commutative >= 0)
 764                       {
 765                         if (c == commutative || c == commutative + 1)
 766                           {
 767                             int other = c + (c == commutative ? 1 : -1);
 768                             matches[other][operand_number] = 1;
 769                           }
 770                         if (operand_number == commutative
 771                             || operand_number == commutative + 1)
 772                           {
 773                             int other = (operand_number
 774                                          + (operand_number == commutative
 775                                             ? 1 : -1));
 776                             matches[c][other] = 1;
 777                           }
 778                       }
 779                     break;
 780                   }
 781             }
 782
 783           /* Now scan through the operands looking for a destination operand
 784              which is supposed to match a source operand.
 785              Then scan backward for an instruction which sets the source
 786              operand.  If safe, then replace the source operand with the
 787              dest operand in both instructions.  */
 788
 789           for (operand_number = 0;
 790                operand_number < insn_n_operands[insn_code_number];
 791                operand_number++)
 792             {
 793               for (match_number = 0;
 794                    match_number < insn_n_operands[insn_code_number];
 795                    match_number++)
 796                 {
 797                   rtx set, p, src, dst;
 798                   rtx src_note, dst_note;
 799                   int success = 0;
 800                   int num_calls = 0;
 801
 802                   /* Nothing to do if the two operands aren't supposed to
 803                      match.  */
 804                   if (matches[operand_number][match_number] == 0)
 805                     continue;
 806
 807                   dst = recog_operand[operand_number];
 808                   src = recog_operand[match_number];
 809
 810                   if (GET_CODE (src) != REG
 811                       || REGNO (src) < FIRST_PSEUDO_REGISTER)
 812                     continue;
 813
 814                   if (GET_CODE (dst) != REG
 815                       || REGNO (dst) < FIRST_PSEUDO_REGISTER)
 816                     continue;
 817
 818                   /* If the operands already match, then there is nothing
 819                      to do.  */
 820                   if (operands_match_p (src, dst))
 821                     continue;
 822
 823                   set = single_set (insn);
 824                   if (! set)
 825                     continue;
 826
 827                   /* operand_number/dst must be a write-only operand, and
 828                      match_operand/src must be a read-only operand.  */
 829                   if (modified[match_number] != 0)
 830                     continue;
 831
 832                   if (early_clobber[operand_number] == 1)
 833                     continue;
 834
 835                   if (modified[operand_number] != 2)
 836                     continue;
 837
 838                   /* Make sure operand_number is the destination.  */
 839                   if (recog_operand[operand_number] != SET_DEST (set))
 840                     continue;
 841
 842                   if (! (src_note = find_reg_note (insn, REG_DEAD, src)))
 843                     continue;
 844
 845                   /* Can not modify an earlier insn to set dst if this insn
 846                      uses an old value in the source.  */
 847                   if (reg_overlap_mentioned_p (dst, SET_SRC (set)))
 848                     continue;
 849
 850                   if (regmove_dump_file)
 851                     fprintf (regmove_dump_file,
 852                              "Could fix operand %d of insn %d matching operand %d.\n",
 853                              operand_number, INSN_UID (insn), match_number);
 854
 855                   /* ??? If src is set once, and is set equal to a constant,
 856                      then do not use it for this optimization, as this would
 857                      make it no longer equivalent to a constant?  */
 858
 859                   /* Scan backward to find the first instruction that uses
 860                      the input operand.  If the operand is set here, then
 861                      replace it in both instructions with operand_number.  */
 862
 863                   for (p = PREV_INSN (insn); p; p = PREV_INSN (p))
 864                     {
 865                       rtx pset;
 866
 867                       if (GET_CODE (p) == CODE_LABEL
 868                           || GET_CODE (p) == JUMP_INSN
 869                           || (GET_CODE (p) == NOTE
 870                               && (NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_BEG
 871                                   || NOTE_LINE_NUMBER (p) == NOTE_INSN_LOOP_END)))
 872                         break;
 873
 874                       if (GET_RTX_CLASS (GET_CODE (p)) != 'i')
 875                         continue;
 876
 877                       /* ??? See if all of SRC is set in P.  This test is much
 878                          more conservative than it needs to be.  */
 879                       pset = single_set (p);
 880                       if (pset && SET_DEST (pset) == src)
 881                         {
 882                           /* We use validate_replace_rtx, in case there
 883                              are multiple identical source operands.  All of
 884                              them have to be changed at the same time.  */
 885                           if (validate_replace_rtx (src, dst, insn))
 886                             {
 887                               if (validate_change (p, &SET_DEST (pset),
 888                                                    dst, 0))
 889                                 success = 1;
 890                               else
 891                                 {
 892                                   /* Change all source operands back.
 893                                      This modifies the dst as a side-effect.  */
 894                                   validate_replace_rtx (dst, src, insn);
 895                                   /* Now make sure the dst is right.  */
 896                                   validate_change (insn,
 897                                                    recog_operand_loc[operand_number],
 898                                                    dst, 0);
 899                                 }
 900                             }
 901                           break;
 902                         }
 903
 904                       if (reg_overlap_mentioned_p (src, PATTERN (p))
 905                           || reg_overlap_mentioned_p (dst, PATTERN (p)))
 906                         break;
 907
 908                       /* If we have passed a call instruction, and the
 909                          pseudo-reg DST is not already live across a call,
 910                          then don't perform the optimization.  */
 911                       if (GET_CODE (p) == CALL_INSN)
 912                         {
 913                           num_calls++;
 914
 915                           if (REG_N_CALLS_CROSSED (REGNO (dst)) == 0)
 916                             break;
 917                         }
 918                     }
 919
 920                   if (success)
 921                     {
 922                       /* Remove the death note for SRC from INSN.  */
 923                       remove_note (insn, src_note);
 924                       /* Move the death note for SRC to P if it is used
 925                          there.  */
 926                       if (reg_overlap_mentioned_p (src, PATTERN (p)))
 927                         {
 928                           XEXP (src_note, 1) = REG_NOTES (p);
 929                           REG_NOTES (p) = src_note;
 930                         }
 931                       /* If there is a REG_DEAD note for DST on P, then remove
 932                          it, because DST is now set there.  */
 933                       if (dst_note = find_reg_note (p, REG_DEAD, dst))
 934                         remove_note (p, dst_note);
 935
 936                       REG_N_SETS (REGNO (dst))++;
 937                       REG_N_SETS (REGNO (src))--;
 938
 939                       REG_N_CALLS_CROSSED (REGNO (dst)) += num_calls;
 940                       REG_N_CALLS_CROSSED (REGNO (src)) -= num_calls;
 941
 942                       /* ??? Must adjust reg_live_length, and reg_n_refs for
 943                          both registers.  Must keep track of loop_depth in
 944                          order to get reg_n_refs adjustment correct.  */
 945
 946                       if (regmove_dump_file)
 947                         fprintf (regmove_dump_file,
 948                                  "Fixed operand %d of insn %d matching operand %d.\n",
 949                                  operand_number, INSN_UID (insn), match_number);
 950
 951                       goto done_backwards;
 952                     }
 953                 }
 954             }
 955         done_backwards:
 956           ;
 957         }
 958     }
 959 #endif /* REGISTER_CONSTRAINTS */
 960 }
 961
 962 /* return nonzero if X is stable but for mentioning SRC or mentioning /
 963    changing DST .  If in doubt, presume it is unstable.  */
 964 static int
 965 stable_but_for_p (x, src, dst)
 966      rtx x, src, dst;
 967 {
 968   RTX_CODE code = GET_CODE (x);
 969   switch (GET_RTX_CLASS (code))
 970     {
 971     case '<': case '1': case 'c': case '2': case 'b': case '3':
 972       {
 973         int i;
 974         char *fmt = GET_RTX_FORMAT (code);
 975         for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 976           if (fmt[i] == 'e' && ! stable_but_for_p (XEXP (x, i), src, dst))
 977               return 0;
 978         return 1;
 979       }
 980     case 'o':
 981       if (x == src || x == dst)
 982         return 1;
 983       /* fall through */
 984     default:
 985       return ! rtx_unstable_p (x);
 986     }
 987 }