contrib/gcc-5.0/gcc/lra-eliminations.c

   1 /* Code for RTL register eliminations.
   2    Copyright (C) 2010-2015 Free Software Foundation, Inc.
   3    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* Eliminable registers (like a soft argument or frame pointer) are
  22    widely used in RTL.  These eliminable registers should be replaced
  23    by real hard registers (like the stack pointer or hard frame
  24    pointer) plus some offset.  The offsets usually change whenever the
  25    stack is expanded.  We know the final offsets only at the very end
  26    of LRA.
  27
  28    Within LRA, we usually keep the RTL in such a state that the
  29    eliminable registers can be replaced by just the corresponding hard
  30    register (without any offset).  To achieve this we should add the
  31    initial elimination offset at the beginning of LRA and update the
  32    offsets whenever the stack is expanded.  We need to do this before
  33    every constraint pass because the choice of offset often affects
  34    whether a particular address or memory constraint is satisfied.
  35
  36    We keep RTL code at most time in such state that the virtual
  37    registers can be changed by just the corresponding hard registers
  38    (with zero offsets) and we have the right RTL code.  To achieve this
  39    we should add initial offset at the beginning of LRA work and update
  40    offsets after each stack expanding.  But actually we update virtual
  41    registers to the same virtual registers + corresponding offsets
  42    before every constraint pass because it affects constraint
  43    satisfaction (e.g. an address displacement became too big for some
  44    target).
  45
  46    The final change of eliminable registers to the corresponding hard
  47    registers are done at the very end of LRA when there were no change
  48    in offsets anymore:
  49
  50                      fp + 42     =>     sp + 42
  51
  52 */
  53
  54 #include "config.h"
  55 #include "system.h"
  56 #include "coretypes.h"
  57 #include "tm.h"
  58 #include "hard-reg-set.h"
  59 #include "rtl.h"
  60 #include "tm_p.h"
  61 #include "regs.h"
  62 #include "insn-config.h"
  63 #include "insn-codes.h"
  64 #include "recog.h"
  65 #include "output.h"
  66 #include "addresses.h"
  67 #include "target.h"
  68 #include "hashtab.h"
  69 #include "hash-set.h"
  70 #include "vec.h"
  71 #include "machmode.h"
  72 #include "input.h"
  73 #include "function.h"
  74 #include "symtab.h"
  75 #include "flags.h"
  76 #include "statistics.h"
  77 #include "double-int.h"
  78 #include "real.h"
  79 #include "fixed-value.h"
  80 #include "alias.h"
  81 #include "wide-int.h"
  82 #include "inchash.h"
  83 #include "tree.h"
  84 #include "expmed.h"
  85 #include "dojump.h"
  86 #include "explow.h"
  87 #include "calls.h"
  88 #include "emit-rtl.h"
  89 #include "varasm.h"
  90 #include "stmt.h"
  91 #include "expr.h"
  92 #include "predict.h"
  93 #include "dominance.h"
  94 #include "cfg.h"
  95 #include "basic-block.h"
  96 #include "except.h"
  97 #include "optabs.h"
  98 #include "df.h"
  99 #include "ira.h"
 100 #include "rtl-error.h"
 101 #include "lra-int.h"
 102
 103 /* This structure is used to record information about hard register
 104    eliminations.  */
 105 struct lra_elim_table
 106 {
 107   /* Hard register number to be eliminated.  */
 108   int from;
 109   /* Hard register number used as replacement.  */
 110   int to;
 111   /* Difference between values of the two hard registers above on
 112      previous iteration.  */
 113   HOST_WIDE_INT previous_offset;
 114   /* Difference between the values on the current iteration.  */
 115   HOST_WIDE_INT offset;
 116   /* Nonzero if this elimination can be done.  */
 117   bool can_eliminate;
 118   /* CAN_ELIMINATE since the last check.  */
 119   bool prev_can_eliminate;
 120   /* REG rtx for the register to be eliminated.  We cannot simply
 121      compare the number since we might then spuriously replace a hard
 122      register corresponding to a pseudo assigned to the reg to be
 123      eliminated.  */
 124   rtx from_rtx;
 125   /* REG rtx for the replacement.  */
 126   rtx to_rtx;
 127 };
 128
 129 /* The elimination table.  Each array entry describes one possible way
 130    of eliminating a register in favor of another.  If there is more
 131    than one way of eliminating a particular register, the most
 132    preferred should be specified first.  */
 133 static struct lra_elim_table *reg_eliminate = 0;
 134
 135 /* This is an intermediate structure to initialize the table.  It has
 136    exactly the members provided by ELIMINABLE_REGS.  */
 137 static const struct elim_table_1
 138 {
 139   const int from;
 140   const int to;
 141 } reg_eliminate_1[] =
 142
 143 /* If a set of eliminable hard registers was specified, define the
 144    table from it.  Otherwise, default to the normal case of the frame
 145    pointer being replaced by the stack pointer.  */
 146
 147 #ifdef ELIMINABLE_REGS
 148   ELIMINABLE_REGS;
 149 #else
 150   {{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}};
 151 #endif
 152
 153 #define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1)
 154
 155 /* Print info about elimination table to file F.  */
 156 static void
 157 print_elim_table (FILE *f)
 158 {
 159   struct lra_elim_table *ep;
 160
 161   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
 162     fprintf (f, "%s eliminate %d to %d (offset=" HOST_WIDE_INT_PRINT_DEC
 163              ", prev_offset=" HOST_WIDE_INT_PRINT_DEC ")\n",
 164              ep->can_eliminate ? "Can" : "Can't",
 165              ep->from, ep->to, ep->offset, ep->previous_offset);
 166 }
 167
 168 /* Print info about elimination table to stderr.  */
 169 void
 170 lra_debug_elim_table (void)
 171 {
 172   print_elim_table (stderr);
 173 }
 174
 175 /* Setup possibility of elimination in elimination table element EP to
 176    VALUE.  Setup FRAME_POINTER_NEEDED if elimination from frame
 177    pointer to stack pointer is not possible anymore.  */
 178 static void
 179 setup_can_eliminate (struct lra_elim_table *ep, bool value)
 180 {
 181   ep->can_eliminate = ep->prev_can_eliminate = value;
 182   if (! value
 183       && ep->from == FRAME_POINTER_REGNUM && ep->to == STACK_POINTER_REGNUM)
 184     frame_pointer_needed = 1;
 185 }
 186
 187 /* Map: eliminable "from" register -> its current elimination,
 188    or NULL if none.  The elimination table may contain more than
 189    one elimination for the same hard register, but this map specifies
 190    the one that we are currently using.  */
 191 static struct lra_elim_table *elimination_map[FIRST_PSEUDO_REGISTER];
 192
 193 /* When an eliminable hard register becomes not eliminable, we use the
 194    following special structure to restore original offsets for the
 195    register.  */
 196 static struct lra_elim_table self_elim_table;
 197
 198 /* Offsets should be used to restore original offsets for eliminable
 199    hard register which just became not eliminable.  Zero,
 200    otherwise.  */
 201 static HOST_WIDE_INT self_elim_offsets[FIRST_PSEUDO_REGISTER];
 202
 203 /* Map: hard regno -> RTL presentation.  RTL presentations of all
 204    potentially eliminable hard registers are stored in the map.  */
 205 static rtx eliminable_reg_rtx[FIRST_PSEUDO_REGISTER];
 206
 207 /* Set up ELIMINATION_MAP of the currently used eliminations.  */
 208 static void
 209 setup_elimination_map (void)
 210 {
 211   int i;
 212   struct lra_elim_table *ep;
 213
 214   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
 215     elimination_map[i] = NULL;
 216   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
 217     if (ep->can_eliminate && elimination_map[ep->from] == NULL)
 218       elimination_map[ep->from] = ep;
 219 }
 220
 221 \f
 222
 223 /* Compute the sum of X and Y, making canonicalizations assumed in an
 224    address, namely: sum constant integers, surround the sum of two
 225    constants with a CONST, put the constant as the second operand, and
 226    group the constant on the outermost sum.
 227
 228    This routine assumes both inputs are already in canonical form.  */
 229 static rtx
 230 form_sum (rtx x, rtx y)
 231 {
 232   rtx tem;
 233   machine_mode mode = GET_MODE (x);
 234
 235   if (mode == VOIDmode)
 236     mode = GET_MODE (y);
 237
 238   if (mode == VOIDmode)
 239     mode = Pmode;
 240
 241   if (CONST_INT_P (x))
 242     return plus_constant (mode, y, INTVAL (x));
 243   else if (CONST_INT_P (y))
 244     return plus_constant (mode, x, INTVAL (y));
 245   else if (CONSTANT_P (x))
 246     tem = x, x = y, y = tem;
 247
 248   if (GET_CODE (x) == PLUS && CONSTANT_P (XEXP (x, 1)))
 249     return form_sum (XEXP (x, 0), form_sum (XEXP (x, 1), y));
 250
 251   /* Note that if the operands of Y are specified in the opposite
 252      order in the recursive calls below, infinite recursion will
 253      occur.  */
 254   if (GET_CODE (y) == PLUS && CONSTANT_P (XEXP (y, 1)))
 255     return form_sum (form_sum (x, XEXP (y, 0)), XEXP (y, 1));
 256
 257   /* If both constant, encapsulate sum.  Otherwise, just form sum.  A
 258      constant will have been placed second.  */
 259   if (CONSTANT_P (x) && CONSTANT_P (y))
 260     {
 261       if (GET_CODE (x) == CONST)
 262         x = XEXP (x, 0);
 263       if (GET_CODE (y) == CONST)
 264         y = XEXP (y, 0);
 265
 266       return gen_rtx_CONST (VOIDmode, gen_rtx_PLUS (mode, x, y));
 267     }
 268
 269   return gen_rtx_PLUS (mode, x, y);
 270 }
 271
 272 /* Return the current substitution hard register of the elimination of
 273    HARD_REGNO.  If HARD_REGNO is not eliminable, return itself.  */
 274 int
 275 lra_get_elimination_hard_regno (int hard_regno)
 276 {
 277   struct lra_elim_table *ep;
 278
 279   if (hard_regno < 0 || hard_regno >= FIRST_PSEUDO_REGISTER)
 280     return hard_regno;
 281   if ((ep = elimination_map[hard_regno]) == NULL)
 282     return hard_regno;
 283   return ep->to;
 284 }
 285
 286 /* Return elimination which will be used for hard reg REG, NULL
 287    otherwise.  */
 288 static struct lra_elim_table *
 289 get_elimination (rtx reg)
 290 {
 291   int hard_regno;
 292   struct lra_elim_table *ep;
 293   HOST_WIDE_INT offset;
 294
 295   lra_assert (REG_P (reg));
 296   if ((hard_regno = REGNO (reg)) < 0 || hard_regno >= FIRST_PSEUDO_REGISTER)
 297     return NULL;
 298   if ((ep = elimination_map[hard_regno]) != NULL)
 299     return ep->from_rtx != reg ? NULL : ep;
 300   if ((offset = self_elim_offsets[hard_regno]) == 0)
 301     return NULL;
 302   /* This is an iteration to restore offsets just after HARD_REGNO
 303      stopped to be eliminable.  */
 304   self_elim_table.from = self_elim_table.to = hard_regno;
 305   self_elim_table.from_rtx
 306     = self_elim_table.to_rtx
 307     = eliminable_reg_rtx[hard_regno];
 308   lra_assert (self_elim_table.from_rtx != NULL);
 309   self_elim_table.offset = offset;
 310   return &self_elim_table;
 311 }
 312
 313 /* Scan X and replace any eliminable registers (such as fp) with a
 314    replacement (such as sp) if SUBST_P, plus an offset.  The offset is
 315    a change in the offset between the eliminable register and its
 316    substitution if UPDATE_P, or the full offset if FULL_P, or
 317    otherwise zero.  If FULL_P, we also use the SP offsets for
 318    elimination to SP.  If UPDATE_P, use UPDATE_SP_OFFSET for updating
 319    offsets of register elimnable to SP.
 320
 321    MEM_MODE is the mode of an enclosing MEM.  We need this to know how
 322    much to adjust a register for, e.g., PRE_DEC.  Also, if we are
 323    inside a MEM, we are allowed to replace a sum of a hard register
 324    and the constant zero with the hard register, which we cannot do
 325    outside a MEM.  In addition, we need to record the fact that a
 326    hard register is referenced outside a MEM.
 327
 328    If we make full substitution to SP for non-null INSN, add the insn
 329    sp offset.  */
 330 rtx
 331 lra_eliminate_regs_1 (rtx_insn *insn, rtx x, machine_mode mem_mode,
 332                       bool subst_p, bool update_p,
 333                       HOST_WIDE_INT update_sp_offset, bool full_p)
 334 {
 335   enum rtx_code code = GET_CODE (x);
 336   struct lra_elim_table *ep;
 337   rtx new_rtx;
 338   int i, j;
 339   const char *fmt;
 340   int copied = 0;
 341
 342   gcc_assert (!update_p || !full_p);
 343   if (! current_function_decl)
 344     return x;
 345
 346   switch (code)
 347     {
 348     CASE_CONST_ANY:
 349     case CONST:
 350     case SYMBOL_REF:
 351     case CODE_LABEL:
 352     case PC:
 353     case CC0:
 354     case ASM_INPUT:
 355     case ADDR_VEC:
 356     case ADDR_DIFF_VEC:
 357     case RETURN:
 358       return x;
 359
 360     case REG:
 361       /* First handle the case where we encounter a bare hard register
 362          that is eliminable.  Replace it with a PLUS.  */
 363       if ((ep = get_elimination (x)) != NULL)
 364         {
 365           rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
 366
 367           if (update_p)
 368             return plus_constant (Pmode, to,
 369                                   ep->offset - ep->previous_offset
 370                                   + (ep->to_rtx == stack_pointer_rtx
 371                                      ? update_sp_offset : 0));
 372           else if (full_p)
 373             return plus_constant (Pmode, to,
 374                                   ep->offset
 375                                   - (insn != NULL_RTX
 376                                      && ep->to_rtx == stack_pointer_rtx
 377                                      ? lra_get_insn_recog_data (insn)->sp_offset
 378                                      : 0));
 379           else
 380             return to;
 381         }
 382       return x;
 383
 384     case PLUS:
 385       /* If this is the sum of an eliminable register and a constant, rework
 386          the sum.  */
 387       if (REG_P (XEXP (x, 0)) && CONSTANT_P (XEXP (x, 1)))
 388         {
 389           if ((ep = get_elimination (XEXP (x, 0))) != NULL)
 390             {
 391               HOST_WIDE_INT offset;
 392               rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
 393
 394               if (! update_p && ! full_p)
 395                 return gen_rtx_PLUS (Pmode, to, XEXP (x, 1));
 396
 397               offset = (update_p
 398                         ? ep->offset - ep->previous_offset
 399                         + (ep->to_rtx == stack_pointer_rtx
 400                            ? update_sp_offset : 0)
 401                         : ep->offset);
 402               if (full_p && insn != NULL_RTX && ep->to_rtx == stack_pointer_rtx)
 403                 offset -= lra_get_insn_recog_data (insn)->sp_offset;
 404               if (CONST_INT_P (XEXP (x, 1))
 405                   && INTVAL (XEXP (x, 1)) == -offset)
 406                 return to;
 407               else
 408                 return gen_rtx_PLUS (Pmode, to,
 409                                      plus_constant (Pmode,
 410                                                     XEXP (x, 1), offset));
 411             }
 412
 413           /* If the hard register is not eliminable, we are done since
 414              the other operand is a constant.  */
 415           return x;
 416         }
 417
 418       /* If this is part of an address, we want to bring any constant
 419          to the outermost PLUS.  We will do this by doing hard
 420          register replacement in our operands and seeing if a constant
 421          shows up in one of them.
 422
 423          Note that there is no risk of modifying the structure of the
 424          insn, since we only get called for its operands, thus we are
 425          either modifying the address inside a MEM, or something like
 426          an address operand of a load-address insn.  */
 427
 428       {
 429         rtx new0 = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
 430                                          subst_p, update_p,
 431                                          update_sp_offset, full_p);
 432         rtx new1 = lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
 433                                          subst_p, update_p,
 434                                          update_sp_offset, full_p);
 435
 436         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
 437           return form_sum (new0, new1);
 438       }
 439       return x;
 440
 441     case MULT:
 442       /* If this is the product of an eliminable hard register and a
 443          constant, apply the distribute law and move the constant out
 444          so that we have (plus (mult ..) ..).  This is needed in order
 445          to keep load-address insns valid.  This case is pathological.
 446          We ignore the possibility of overflow here.  */
 447       if (REG_P (XEXP (x, 0)) && CONST_INT_P (XEXP (x, 1))
 448           && (ep = get_elimination (XEXP (x, 0))) != NULL)
 449         {
 450           rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
 451
 452           if (update_p)
 453             return plus_constant (Pmode,
 454                                   gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
 455                                   (ep->offset - ep->previous_offset
 456                                    + (ep->to_rtx == stack_pointer_rtx
 457                                       ? update_sp_offset : 0))
 458                                   * INTVAL (XEXP (x, 1)));
 459           else if (full_p)
 460             {
 461               HOST_WIDE_INT offset = ep->offset;
 462
 463               if (insn != NULL_RTX && ep->to_rtx == stack_pointer_rtx)
 464                 offset -= lra_get_insn_recog_data (insn)->sp_offset;
 465               return
 466                 plus_constant (Pmode,
 467                                gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
 468                                offset * INTVAL (XEXP (x, 1)));
 469             }
 470           else
 471             return gen_rtx_MULT (Pmode, to, XEXP (x, 1));
 472         }
 473
 474       /* ... fall through ...  */
 475
 476     case CALL:
 477     case COMPARE:
 478     /* See comments before PLUS about handling MINUS.  */
 479     case MINUS:
 480     case DIV:      case UDIV:
 481     case MOD:      case UMOD:
 482     case AND:      case IOR:      case XOR:
 483     case ROTATERT: case ROTATE:
 484     case ASHIFTRT: case LSHIFTRT: case ASHIFT:
 485     case NE:       case EQ:
 486     case GE:       case GT:       case GEU:    case GTU:
 487     case LE:       case LT:       case LEU:    case LTU:
 488       {
 489         rtx new0 = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
 490                                          subst_p, update_p,
 491                                          update_sp_offset, full_p);
 492         rtx new1 = XEXP (x, 1)
 493                    ? lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
 494                                            subst_p, update_p,
 495                                            update_sp_offset, full_p) : 0;
 496
 497         if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
 498           return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
 499       }
 500       return x;
 501
 502     case EXPR_LIST:
 503       /* If we have something in XEXP (x, 0), the usual case,
 504          eliminate it.  */
 505       if (XEXP (x, 0))
 506         {
 507           new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
 508                                           subst_p, update_p,
 509                                           update_sp_offset, full_p);
 510           if (new_rtx != XEXP (x, 0))
 511             {
 512               /* If this is a REG_DEAD note, it is not valid anymore.
 513                  Using the eliminated version could result in creating a
 514                  REG_DEAD note for the stack or frame pointer.  */
 515               if (REG_NOTE_KIND (x) == REG_DEAD)
 516                 return (XEXP (x, 1)
 517                         ? lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
 518                                                 subst_p, update_p,
 519                                                 update_sp_offset, full_p)
 520                         : NULL_RTX);
 521
 522               x = alloc_reg_note (REG_NOTE_KIND (x), new_rtx, XEXP (x, 1));
 523             }
 524         }
 525
 526       /* ... fall through ...  */
 527
 528     case INSN_LIST:
 529     case INT_LIST:
 530       /* Now do eliminations in the rest of the chain.  If this was
 531          an EXPR_LIST, this might result in allocating more memory than is
 532          strictly needed, but it simplifies the code.  */
 533       if (XEXP (x, 1))
 534         {
 535           new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 1), mem_mode,
 536                                           subst_p, update_p,
 537                                           update_sp_offset, full_p);
 538           if (new_rtx != XEXP (x, 1))
 539             return
 540               gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x),
 541                               XEXP (x, 0), new_rtx);
 542         }
 543       return x;
 544
 545     case PRE_INC:
 546     case POST_INC:
 547     case PRE_DEC:
 548     case POST_DEC:
 549       /* We do not support elimination of a register that is modified.
 550          elimination_effects has already make sure that this does not
 551          happen.  */
 552       return x;
 553
 554     case PRE_MODIFY:
 555     case POST_MODIFY:
 556       /* We do not support elimination of a hard register that is
 557          modified.  LRA has already make sure that this does not
 558          happen. The only remaining case we need to consider here is
 559          that the increment value may be an eliminable register.  */
 560       if (GET_CODE (XEXP (x, 1)) == PLUS
 561           && XEXP (XEXP (x, 1), 0) == XEXP (x, 0))
 562         {
 563           rtx new_rtx = lra_eliminate_regs_1 (insn, XEXP (XEXP (x, 1), 1),
 564                                               mem_mode, subst_p, update_p,
 565                                               update_sp_offset, full_p);
 566
 567           if (new_rtx != XEXP (XEXP (x, 1), 1))
 568             return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0),
 569                                    gen_rtx_PLUS (GET_MODE (x),
 570                                                  XEXP (x, 0), new_rtx));
 571         }
 572       return x;
 573
 574     case STRICT_LOW_PART:
 575     case NEG:          case NOT:
 576     case SIGN_EXTEND:  case ZERO_EXTEND:
 577     case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
 578     case FLOAT:        case FIX:
 579     case UNSIGNED_FIX: case UNSIGNED_FLOAT:
 580     case ABS:
 581     case SQRT:
 582     case FFS:
 583     case CLZ:
 584     case CTZ:
 585     case POPCOUNT:
 586     case PARITY:
 587     case BSWAP:
 588       new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), mem_mode,
 589                                       subst_p, update_p,
 590                                       update_sp_offset, full_p);
 591       if (new_rtx != XEXP (x, 0))
 592         return gen_rtx_fmt_e (code, GET_MODE (x), new_rtx);
 593       return x;
 594
 595     case SUBREG:
 596       new_rtx = lra_eliminate_regs_1 (insn, SUBREG_REG (x), mem_mode,
 597                                       subst_p, update_p,
 598                                       update_sp_offset, full_p);
 599
 600       if (new_rtx != SUBREG_REG (x))
 601         {
 602           int x_size = GET_MODE_SIZE (GET_MODE (x));
 603           int new_size = GET_MODE_SIZE (GET_MODE (new_rtx));
 604
 605           if (MEM_P (new_rtx) && x_size <= new_size)
 606             {
 607               SUBREG_REG (x) = new_rtx;
 608               alter_subreg (&x, false);
 609               return x;
 610             }
 611           else if (! subst_p)
 612             {
 613               /* LRA can transform subregs itself.  So don't call
 614                  simplify_gen_subreg until LRA transformations are
 615                  finished.  Function simplify_gen_subreg can do
 616                  non-trivial transformations (like truncation) which
 617                  might make LRA work to fail.  */
 618               SUBREG_REG (x) = new_rtx;
 619               return x;
 620             }
 621           else
 622             return simplify_gen_subreg (GET_MODE (x), new_rtx,
 623                                         GET_MODE (new_rtx), SUBREG_BYTE (x));
 624         }
 625
 626       return x;
 627
 628     case MEM:
 629       /* Our only special processing is to pass the mode of the MEM to our
 630          recursive call and copy the flags.  While we are here, handle this
 631          case more efficiently.  */
 632       return
 633         replace_equiv_address_nv
 634         (x,
 635          lra_eliminate_regs_1 (insn, XEXP (x, 0), GET_MODE (x),
 636                                subst_p, update_p, update_sp_offset, full_p));
 637
 638     case USE:
 639       /* Handle insn_list USE that a call to a pure function may generate.  */
 640       new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, 0), VOIDmode,
 641                                       subst_p, update_p, update_sp_offset, full_p);
 642       if (new_rtx != XEXP (x, 0))
 643         return gen_rtx_USE (GET_MODE (x), new_rtx);
 644       return x;
 645
 646     case CLOBBER:
 647     case SET:
 648       gcc_unreachable ();
 649
 650     default:
 651       break;
 652     }
 653
 654   /* Process each of our operands recursively.  If any have changed, make a
 655      copy of the rtx.  */
 656   fmt = GET_RTX_FORMAT (code);
 657   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
 658     {
 659       if (*fmt == 'e')
 660         {
 661           new_rtx = lra_eliminate_regs_1 (insn, XEXP (x, i), mem_mode,
 662                                           subst_p, update_p,
 663                                           update_sp_offset, full_p);
 664           if (new_rtx != XEXP (x, i) && ! copied)
 665             {
 666               x = shallow_copy_rtx (x);
 667               copied = 1;
 668             }
 669           XEXP (x, i) = new_rtx;
 670         }
 671       else if (*fmt == 'E')
 672         {
 673           int copied_vec = 0;
 674           for (j = 0; j < XVECLEN (x, i); j++)
 675             {
 676               new_rtx = lra_eliminate_regs_1 (insn, XVECEXP (x, i, j), mem_mode,
 677                                               subst_p, update_p,
 678                                               update_sp_offset, full_p);
 679               if (new_rtx != XVECEXP (x, i, j) && ! copied_vec)
 680                 {
 681                   rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
 682                                              XVEC (x, i)->elem);
 683                   if (! copied)
 684                     {
 685                       x = shallow_copy_rtx (x);
 686                       copied = 1;
 687                     }
 688                   XVEC (x, i) = new_v;
 689                   copied_vec = 1;
 690                 }
 691               XVECEXP (x, i, j) = new_rtx;
 692             }
 693         }
 694     }
 695
 696   return x;
 697 }
 698
 699 /* This function is used externally in subsequent passes of GCC.  It
 700    always does a full elimination of X.  */
 701 rtx
 702 lra_eliminate_regs (rtx x, machine_mode mem_mode,
 703                     rtx insn ATTRIBUTE_UNUSED)
 704 {
 705   return lra_eliminate_regs_1 (NULL, x, mem_mode, true, false, 0, true);
 706 }
 707
 708 /* Stack pointer offset before the current insn relative to one at the
 709    func start.  RTL insns can change SP explicitly.  We keep the
 710    changes from one insn to another through this variable.  */
 711 static HOST_WIDE_INT curr_sp_change;
 712
 713 /* Scan rtx X for references to elimination source or target registers
 714    in contexts that would prevent the elimination from happening.
 715    Update the table of eliminables to reflect the changed state.
 716    MEM_MODE is the mode of an enclosing MEM rtx, or VOIDmode if not
 717    within a MEM.  */
 718 static void
 719 mark_not_eliminable (rtx x, machine_mode mem_mode)
 720 {
 721   enum rtx_code code = GET_CODE (x);
 722   struct lra_elim_table *ep;
 723   int i, j;
 724   const char *fmt;
 725
 726   switch (code)
 727     {
 728     case PRE_INC:
 729     case POST_INC:
 730     case PRE_DEC:
 731     case POST_DEC:
 732     case POST_MODIFY:
 733     case PRE_MODIFY:
 734       if (XEXP (x, 0) == stack_pointer_rtx
 735           && ((code != PRE_MODIFY && code != POST_MODIFY)
 736               || (GET_CODE (XEXP (x, 1)) == PLUS
 737                   && XEXP (x, 0) == XEXP (XEXP (x, 1), 0)
 738                   && CONST_INT_P (XEXP (XEXP (x, 1), 1)))))
 739         {
 740           int size = GET_MODE_SIZE (mem_mode);
 741
 742 #ifdef PUSH_ROUNDING
 743           /* If more bytes than MEM_MODE are pushed, account for
 744              them.  */
 745           size = PUSH_ROUNDING (size);
 746 #endif
 747           if (code == PRE_DEC || code == POST_DEC)
 748             curr_sp_change -= size;
 749           else if (code == PRE_INC || code == POST_INC)
 750             curr_sp_change += size;
 751           else if (code == PRE_MODIFY || code == POST_MODIFY)
 752             curr_sp_change += INTVAL (XEXP (XEXP (x, 1), 1));
 753         }
 754       else if (REG_P (XEXP (x, 0))
 755                && REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER)
 756         {
 757           /* If we modify the source of an elimination rule, disable
 758              it.  Do the same if it is the destination and not the
 759              hard frame register.  */
 760           for (ep = reg_eliminate;
 761                ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
 762                ep++)
 763             if (ep->from_rtx == XEXP (x, 0)
 764                 || (ep->to_rtx == XEXP (x, 0)
 765                     && ep->to_rtx != hard_frame_pointer_rtx))
 766               setup_can_eliminate (ep, false);
 767         }
 768       return;
 769
 770     case USE:
 771       if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
 772         /* If using a hard register that is the source of an eliminate
 773            we still think can be performed, note it cannot be
 774            performed since we don't know how this hard register is
 775            used.  */
 776         for (ep = reg_eliminate;
 777              ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
 778              ep++)
 779           if (ep->from_rtx == XEXP (x, 0)
 780               && ep->to_rtx != hard_frame_pointer_rtx)
 781             setup_can_eliminate (ep, false);
 782       return;
 783
 784     case CLOBBER:
 785       if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
 786         /* If clobbering a hard register that is the replacement
 787            register for an elimination we still think can be
 788            performed, note that it cannot be performed.  Otherwise, we
 789            need not be concerned about it.  */
 790         for (ep = reg_eliminate;
 791              ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
 792              ep++)
 793           if (ep->to_rtx == XEXP (x, 0)
 794               && ep->to_rtx != hard_frame_pointer_rtx)
 795             setup_can_eliminate (ep, false);
 796       return;
 797
 798     case SET:
 799       if (SET_DEST (x) == stack_pointer_rtx
 800           && GET_CODE (SET_SRC (x)) == PLUS
 801           && XEXP (SET_SRC (x), 0) == SET_DEST (x)
 802           && CONST_INT_P (XEXP (SET_SRC (x), 1)))
 803         {
 804           curr_sp_change += INTVAL (XEXP (SET_SRC (x), 1));
 805           return;
 806         }
 807       if (! REG_P (SET_DEST (x))
 808           || REGNO (SET_DEST (x)) >= FIRST_PSEUDO_REGISTER)
 809         mark_not_eliminable (SET_DEST (x), mem_mode);
 810       else
 811         {
 812           /* See if this is setting the replacement hard register for
 813              an elimination.
 814
 815              If DEST is the hard frame pointer, we do nothing because
 816              we assume that all assignments to the frame pointer are
 817              for non-local gotos and are being done at a time when
 818              they are valid and do not disturb anything else.  Some
 819              machines want to eliminate a fake argument pointer (or
 820              even a fake frame pointer) with either the real frame
 821              pointer or the stack pointer.  Assignments to the hard
 822              frame pointer must not prevent this elimination.  */
 823           for (ep = reg_eliminate;
 824                ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
 825                ep++)
 826             if (ep->to_rtx == SET_DEST (x)
 827                 && SET_DEST (x) != hard_frame_pointer_rtx)
 828               setup_can_eliminate (ep, false);
 829         }
 830
 831       mark_not_eliminable (SET_SRC (x), mem_mode);
 832       return;
 833
 834     case MEM:
 835       /* Our only special processing is to pass the mode of the MEM to
 836          our recursive call.  */
 837       mark_not_eliminable (XEXP (x, 0), GET_MODE (x));
 838       return;
 839
 840     default:
 841       break;
 842     }
 843
 844   fmt = GET_RTX_FORMAT (code);
 845   for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
 846     {
 847       if (*fmt == 'e')
 848         mark_not_eliminable (XEXP (x, i), mem_mode);
 849       else if (*fmt == 'E')
 850         for (j = 0; j < XVECLEN (x, i); j++)
 851           mark_not_eliminable (XVECEXP (x, i, j), mem_mode);
 852     }
 853 }
 854
 855 \f
 856
 857 #ifdef HARD_FRAME_POINTER_REGNUM
 858
 859 /* Find offset equivalence note for reg WHAT in INSN and return the
 860    found elmination offset.  If the note is not found, return NULL.
 861    Remove the found note.  */
 862 static rtx
 863 remove_reg_equal_offset_note (rtx insn, rtx what)
 864 {
 865   rtx link, *link_loc;
 866
 867   for (link_loc = &REG_NOTES (insn);
 868        (link = *link_loc) != NULL_RTX;
 869        link_loc = &XEXP (link, 1))
 870     if (REG_NOTE_KIND (link) == REG_EQUAL
 871         && GET_CODE (XEXP (link, 0)) == PLUS
 872         && XEXP (XEXP (link, 0), 0) == what
 873         && CONST_INT_P (XEXP (XEXP (link, 0), 1)))
 874       {
 875         *link_loc = XEXP (link, 1);
 876         return XEXP (XEXP (link, 0), 1);
 877       }
 878   return NULL_RTX;
 879 }
 880
 881 #endif
 882
 883 /* Scan INSN and eliminate all eliminable hard registers in it.
 884
 885    If REPLACE_P is true, do the replacement destructively.  Also
 886    delete the insn as dead it if it is setting an eliminable register.
 887
 888    If REPLACE_P is false, just update the offsets while keeping the
 889    base register the same.  If FIRST_P, use the sp offset for
 890    elimination to sp.  Otherwise, use UPDATE_SP_OFFSET for this.
 891    Attach the note about used elimination for insns setting frame
 892    pointer to update elimination easy (without parsing already
 893    generated elimination insns to find offset previously used) in
 894    future.  */
 895
 896 void
 897 eliminate_regs_in_insn (rtx_insn *insn, bool replace_p, bool first_p,
 898                         HOST_WIDE_INT update_sp_offset)
 899 {
 900   int icode = recog_memoized (insn);
 901   rtx old_set = single_set (insn);
 902   bool validate_p;
 903   int i;
 904   rtx substed_operand[MAX_RECOG_OPERANDS];
 905   rtx orig_operand[MAX_RECOG_OPERANDS];
 906   struct lra_elim_table *ep;
 907   rtx plus_src, plus_cst_src;
 908   lra_insn_recog_data_t id;
 909   struct lra_static_insn_data *static_id;
 910
 911   if (icode < 0 && asm_noperands (PATTERN (insn)) < 0 && ! DEBUG_INSN_P (insn))
 912     {
 913       lra_assert (GET_CODE (PATTERN (insn)) == USE
 914                   || GET_CODE (PATTERN (insn)) == CLOBBER
 915                   || GET_CODE (PATTERN (insn)) == ASM_INPUT);
 916       return;
 917     }
 918
 919   /* Check for setting an eliminable register.  */
 920   if (old_set != 0 && REG_P (SET_DEST (old_set))
 921       && (ep = get_elimination (SET_DEST (old_set))) != NULL)
 922     {
 923       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
 924         if (ep->from_rtx == SET_DEST (old_set) && ep->can_eliminate)
 925           {
 926             bool delete_p = replace_p;
 927
 928 #ifdef HARD_FRAME_POINTER_REGNUM
 929             if (ep->from == FRAME_POINTER_REGNUM
 930                 && ep->to == HARD_FRAME_POINTER_REGNUM)
 931               /* If this is setting the frame pointer register to the
 932                  hardware frame pointer register and this is an
 933                  elimination that will be done (tested above), this
 934                  insn is really adjusting the frame pointer downward
 935                  to compensate for the adjustment done before a
 936                  nonlocal goto.  */
 937               {
 938                 rtx src = SET_SRC (old_set);
 939                 rtx off = remove_reg_equal_offset_note (insn, ep->to_rtx);
 940
 941                 if (off != NULL_RTX
 942                     || src == ep->to_rtx
 943                     || (GET_CODE (src) == PLUS
 944                         && XEXP (src, 0) == ep->to_rtx
 945                         && CONST_INT_P (XEXP (src, 1))))
 946                   {
 947                     HOST_WIDE_INT offset;
 948
 949                     if (replace_p)
 950                       {
 951                         SET_DEST (old_set) = ep->to_rtx;
 952                         lra_update_insn_recog_data (insn);
 953                         return;
 954                       }
 955                     offset = (off != NULL_RTX ? INTVAL (off)
 956                               : src == ep->to_rtx ? 0 : INTVAL (XEXP (src, 1)));
 957                     offset -= (ep->offset - ep->previous_offset);
 958                     src = plus_constant (Pmode, ep->to_rtx, offset);
 959
 960                     /* First see if this insn remains valid when we
 961                        make the change.  If not, keep the INSN_CODE
 962                        the same and let the constraint pass fit it
 963                        up.  */
 964                     validate_change (insn, &SET_SRC (old_set), src, 1);
 965                     validate_change (insn, &SET_DEST (old_set),
 966                                      ep->from_rtx, 1);
 967                     if (! apply_change_group ())
 968                       {
 969                         SET_SRC (old_set) = src;
 970                         SET_DEST (old_set) = ep->from_rtx;
 971                       }
 972                     lra_update_insn_recog_data (insn);
 973                     /* Add offset note for future updates.  */
 974                     add_reg_note (insn, REG_EQUAL, src);
 975                     return;
 976                   }
 977               }
 978 #endif
 979
 980             /* This insn isn't serving a useful purpose.  We delete it
 981                when REPLACE is set.  */
 982             if (delete_p)
 983               lra_delete_dead_insn (insn);
 984             return;
 985           }
 986     }
 987
 988   /* We allow one special case which happens to work on all machines we
 989      currently support: a single set with the source or a REG_EQUAL
 990      note being a PLUS of an eliminable register and a constant.  */
 991   plus_src = plus_cst_src = 0;
 992   if (old_set && REG_P (SET_DEST (old_set)))
 993     {
 994       if (GET_CODE (SET_SRC (old_set)) == PLUS)
 995         plus_src = SET_SRC (old_set);
 996       /* First see if the source is of the form (plus (...) CST).  */
 997       if (plus_src
 998           && CONST_INT_P (XEXP (plus_src, 1)))
 999         plus_cst_src = plus_src;
1000       /* Check that the first operand of the PLUS is a hard reg or
1001          the lowpart subreg of one.  */
1002       if (plus_cst_src)
1003         {
1004           rtx reg = XEXP (plus_cst_src, 0);
1005
1006           if (GET_CODE (reg) == SUBREG && subreg_lowpart_p (reg))
1007             reg = SUBREG_REG (reg);
1008
1009           if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
1010             plus_cst_src = 0;
1011         }
1012     }
1013   if (plus_cst_src)
1014     {
1015       rtx reg = XEXP (plus_cst_src, 0);
1016       HOST_WIDE_INT offset = INTVAL (XEXP (plus_cst_src, 1));
1017
1018       if (GET_CODE (reg) == SUBREG)
1019         reg = SUBREG_REG (reg);
1020
1021       if (REG_P (reg) && (ep = get_elimination (reg)) != NULL)
1022         {
1023           rtx to_rtx = replace_p ? ep->to_rtx : ep->from_rtx;
1024
1025           if (! replace_p)
1026             {
1027               offset += (ep->offset - ep->previous_offset);
1028               if (ep->to_rtx == stack_pointer_rtx)
1029                 {
1030                   if (first_p)
1031                     offset -= lra_get_insn_recog_data (insn)->sp_offset;
1032                   else
1033                     offset += update_sp_offset;
1034                 }
1035               offset = trunc_int_for_mode (offset, GET_MODE (plus_cst_src));
1036             }
1037
1038           if (GET_CODE (XEXP (plus_cst_src, 0)) == SUBREG)
1039             to_rtx = gen_lowpart (GET_MODE (XEXP (plus_cst_src, 0)), to_rtx);
1040           /* If we have a nonzero offset, and the source is already a
1041              simple REG, the following transformation would increase
1042              the cost of the insn by replacing a simple REG with (plus
1043              (reg sp) CST).  So try only when we already had a PLUS
1044              before.  */
1045           if (offset == 0 || plus_src)
1046             {
1047               rtx new_src = plus_constant (GET_MODE (to_rtx), to_rtx, offset);
1048
1049               old_set = single_set (insn);
1050
1051               /* First see if this insn remains valid when we make the
1052                  change.  If not, try to replace the whole pattern
1053                  with a simple set (this may help if the original insn
1054                  was a PARALLEL that was only recognized as single_set
1055                  due to REG_UNUSED notes).  If this isn't valid
1056                  either, keep the INSN_CODE the same and let the
1057                  constraint pass fix it up.  */
1058               if (! validate_change (insn, &SET_SRC (old_set), new_src, 0))
1059                 {
1060                   rtx new_pat = gen_rtx_SET (VOIDmode,
1061                                              SET_DEST (old_set), new_src);
1062
1063                   if (! validate_change (insn, &PATTERN (insn), new_pat, 0))
1064                     SET_SRC (old_set) = new_src;
1065                 }
1066               lra_update_insn_recog_data (insn);
1067               /* This can't have an effect on elimination offsets, so skip
1068                  right to the end.  */
1069               return;
1070             }
1071         }
1072     }
1073
1074   /* Eliminate all eliminable registers occurring in operands that
1075      can be handled by the constraint pass.  */
1076   id = lra_get_insn_recog_data (insn);
1077   static_id = id->insn_static_data;
1078   validate_p = false;
1079   for (i = 0; i < static_id->n_operands; i++)
1080     {
1081       orig_operand[i] = *id->operand_loc[i];
1082       substed_operand[i] = *id->operand_loc[i];
1083
1084       /* For an asm statement, every operand is eliminable.  */
1085       if (icode < 0 || insn_data[icode].operand[i].eliminable)
1086         {
1087           /* Check for setting a hard register that we know about.  */
1088           if (static_id->operand[i].type != OP_IN
1089               && REG_P (orig_operand[i]))
1090             {
1091               /* If we are assigning to a hard register that can be
1092                  eliminated, it must be as part of a PARALLEL, since
1093                  the code above handles single SETs.  This reg can not
1094                  be longer eliminated -- it is forced by
1095                  mark_not_eliminable.  */
1096               for (ep = reg_eliminate;
1097                    ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
1098                    ep++)
1099                 lra_assert (ep->from_rtx != orig_operand[i]
1100                             || ! ep->can_eliminate);
1101             }
1102
1103           /* Companion to the above plus substitution, we can allow
1104              invariants as the source of a plain move.  */
1105           substed_operand[i]
1106             = lra_eliminate_regs_1 (insn, *id->operand_loc[i], VOIDmode,
1107                                     replace_p, ! replace_p && ! first_p,
1108                                     update_sp_offset, first_p);
1109           if (substed_operand[i] != orig_operand[i])
1110             validate_p = true;
1111         }
1112     }
1113
1114   if (! validate_p)
1115     return;
1116
1117   /* Substitute the operands; the new values are in the substed_operand
1118      array.  */
1119   for (i = 0; i < static_id->n_operands; i++)
1120     *id->operand_loc[i] = substed_operand[i];
1121   for (i = 0; i < static_id->n_dups; i++)
1122     *id->dup_loc[i] = substed_operand[(int) static_id->dup_num[i]];
1123
1124   /* If we had a move insn but now we don't, re-recognize it.
1125      This will cause spurious re-recognition if the old move had a
1126      PARALLEL since the new one still will, but we can't call
1127      single_set without having put new body into the insn and the
1128      re-recognition won't hurt in this rare case.  */
1129   id = lra_update_insn_recog_data (insn);
1130   static_id = id->insn_static_data;
1131 }
1132
1133 /* Spill pseudos which are assigned to hard registers in SET.  Add
1134    affected insns for processing in the subsequent constraint
1135    pass.  */
1136 static void
1137 spill_pseudos (HARD_REG_SET set)
1138 {
1139   int i;
1140   bitmap_head to_process;
1141   rtx_insn *insn;
1142
1143   if (hard_reg_set_empty_p (set))
1144     return;
1145   if (lra_dump_file != NULL)
1146     {
1147       fprintf (lra_dump_file, "    Spilling non-eliminable hard regs:");
1148       for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1149         if (TEST_HARD_REG_BIT (set, i))
1150           fprintf (lra_dump_file, " %d", i);
1151       fprintf (lra_dump_file, "\n");
1152     }
1153   bitmap_initialize (&to_process, &reg_obstack);
1154   for (i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
1155     if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
1156         && overlaps_hard_reg_set_p (set,
1157                                     PSEUDO_REGNO_MODE (i), reg_renumber[i]))
1158       {
1159         if (lra_dump_file != NULL)
1160           fprintf (lra_dump_file, "      Spilling r%d(%d)\n",
1161                    i, reg_renumber[i]);
1162         reg_renumber[i] = -1;
1163         bitmap_ior_into (&to_process, &lra_reg_info[i].insn_bitmap);
1164       }
1165   IOR_HARD_REG_SET (lra_no_alloc_regs, set);
1166   for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
1167     if (bitmap_bit_p (&to_process, INSN_UID (insn)))
1168       {
1169         lra_push_insn (insn);
1170         lra_set_used_insn_alternative (insn, -1);
1171       }
1172   bitmap_clear (&to_process);
1173 }
1174
1175 /* Update all offsets and possibility for elimination on eliminable
1176    registers.  Spill pseudos assigned to registers which are
1177    uneliminable, update LRA_NO_ALLOC_REGS and ELIMINABLE_REG_SET.  Add
1178    insns to INSNS_WITH_CHANGED_OFFSETS containing eliminable hard
1179    registers whose offsets should be changed.  Return true if any
1180    elimination offset changed.  */
1181 static bool
1182 update_reg_eliminate (bitmap insns_with_changed_offsets)
1183 {
1184   bool prev, result;
1185   struct lra_elim_table *ep, *ep1;
1186   HARD_REG_SET temp_hard_reg_set;
1187
1188   /* Clear self elimination offsets.  */
1189   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1190     self_elim_offsets[ep->from] = 0;
1191   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1192     {
1193       /* If it is a currently used elimination: update the previous
1194          offset.  */
1195       if (elimination_map[ep->from] == ep)
1196         ep->previous_offset = ep->offset;
1197
1198       prev = ep->prev_can_eliminate;
1199       setup_can_eliminate (ep, targetm.can_eliminate (ep->from, ep->to));
1200       if (ep->can_eliminate && ! prev)
1201         {
1202           /* It is possible that not eliminable register becomes
1203              eliminable because we took other reasons into account to
1204              set up eliminable regs in the initial set up.  Just
1205              ignore new eliminable registers.  */
1206           setup_can_eliminate (ep, false);
1207           continue;
1208         }
1209       if (ep->can_eliminate != prev && elimination_map[ep->from] == ep)
1210         {
1211           /* We cannot use this elimination anymore -- find another
1212              one.  */
1213           if (lra_dump_file != NULL)
1214             fprintf (lra_dump_file,
1215                      "  Elimination %d to %d is not possible anymore\n",
1216                      ep->from, ep->to);
1217           /* If after processing RTL we decides that SP can be used as
1218              a result of elimination, it can not be changed.  */
1219           gcc_assert ((ep->to_rtx != stack_pointer_rtx)
1220                       || (ep->from < FIRST_PSEUDO_REGISTER
1221                           && fixed_regs [ep->from]));
1222           /* Mark that is not eliminable anymore.  */
1223           elimination_map[ep->from] = NULL;
1224           for (ep1 = ep + 1; ep1 < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep1++)
1225             if (ep1->can_eliminate && ep1->from == ep->from)
1226               break;
1227           if (ep1 < &reg_eliminate[NUM_ELIMINABLE_REGS])
1228             {
1229               if (lra_dump_file != NULL)
1230                 fprintf (lra_dump_file, "    Using elimination %d to %d now\n",
1231                          ep1->from, ep1->to);
1232               lra_assert (ep1->previous_offset == 0);
1233               ep1->previous_offset = ep->offset;
1234             }
1235           else
1236             {
1237               /* There is no elimination anymore just use the hard
1238                  register `from' itself.  Setup self elimination
1239                  offset to restore the original offset values.  */
1240               if (lra_dump_file != NULL)
1241                 fprintf (lra_dump_file, "    %d is not eliminable at all\n",
1242                          ep->from);
1243               self_elim_offsets[ep->from] = -ep->offset;
1244               if (ep->offset != 0)
1245                 bitmap_ior_into (insns_with_changed_offsets,
1246                                  &lra_reg_info[ep->from].insn_bitmap);
1247             }
1248         }
1249
1250 #ifdef ELIMINABLE_REGS
1251       INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, ep->offset);
1252 #else
1253       INITIAL_FRAME_POINTER_OFFSET (ep->offset);
1254 #endif
1255     }
1256   setup_elimination_map ();
1257   result = false;
1258   CLEAR_HARD_REG_SET (temp_hard_reg_set);
1259   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1260     if (elimination_map[ep->from] == NULL)
1261       SET_HARD_REG_BIT (temp_hard_reg_set, ep->from);
1262     else if (elimination_map[ep->from] == ep)
1263       {
1264         /* Prevent the hard register into which we eliminate from
1265            the usage for pseudos.  */
1266         if (ep->from != ep->to)
1267           SET_HARD_REG_BIT (temp_hard_reg_set, ep->to);
1268         if (ep->previous_offset != ep->offset)
1269           {
1270             bitmap_ior_into (insns_with_changed_offsets,
1271                              &lra_reg_info[ep->from].insn_bitmap);
1272
1273             /* Update offset when the eliminate offset have been
1274                changed.  */
1275             lra_update_reg_val_offset (lra_reg_info[ep->from].val,
1276                                        ep->offset - ep->previous_offset);
1277             result = true;
1278           }
1279       }
1280   IOR_HARD_REG_SET (lra_no_alloc_regs, temp_hard_reg_set);
1281   AND_COMPL_HARD_REG_SET (eliminable_regset, temp_hard_reg_set);
1282   spill_pseudos (temp_hard_reg_set);
1283   return result;
1284 }
1285
1286 /* Initialize the table of hard registers to eliminate.
1287    Pre-condition: global flag frame_pointer_needed has been set before
1288    calling this function.  */
1289 static void
1290 init_elim_table (void)
1291 {
1292   struct lra_elim_table *ep;
1293 #ifdef ELIMINABLE_REGS
1294   bool value_p;
1295   const struct elim_table_1 *ep1;
1296 #endif
1297
1298   if (!reg_eliminate)
1299     reg_eliminate = XCNEWVEC (struct lra_elim_table, NUM_ELIMINABLE_REGS);
1300
1301   memset (self_elim_offsets, 0, sizeof (self_elim_offsets));
1302   /* Initiate member values which will be never changed.  */
1303   self_elim_table.can_eliminate = self_elim_table.prev_can_eliminate = true;
1304   self_elim_table.previous_offset = 0;
1305 #ifdef ELIMINABLE_REGS
1306   for (ep = reg_eliminate, ep1 = reg_eliminate_1;
1307        ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++, ep1++)
1308     {
1309       ep->offset = ep->previous_offset = 0;
1310       ep->from = ep1->from;
1311       ep->to = ep1->to;
1312       value_p = (targetm.can_eliminate (ep->from, ep->to)
1313                  && ! (ep->to == STACK_POINTER_REGNUM
1314                        && frame_pointer_needed
1315                        && (! SUPPORTS_STACK_ALIGNMENT
1316                            || ! stack_realign_fp)));
1317       setup_can_eliminate (ep, value_p);
1318     }
1319 #else
1320   reg_eliminate[0].offset = reg_eliminate[0].previous_offset = 0;
1321   reg_eliminate[0].from = reg_eliminate_1[0].from;
1322   reg_eliminate[0].to = reg_eliminate_1[0].to;
1323   setup_can_eliminate (&reg_eliminate[0], ! frame_pointer_needed);
1324 #endif
1325
1326   /* Build the FROM and TO REG rtx's.  Note that code in gen_rtx_REG
1327      will cause, e.g., gen_rtx_REG (Pmode, STACK_POINTER_REGNUM) to
1328      equal stack_pointer_rtx.  We depend on this. Threfore we switch
1329      off that we are in LRA temporarily.  */
1330   lra_in_progress = 0;
1331   for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1332     {
1333       ep->from_rtx = gen_rtx_REG (Pmode, ep->from);
1334       ep->to_rtx = gen_rtx_REG (Pmode, ep->to);
1335       eliminable_reg_rtx[ep->from] = ep->from_rtx;
1336     }
1337   lra_in_progress = 1;
1338 }
1339
1340 /* Function for initialization of elimination once per function.  It
1341    sets up sp offset for each insn.  */
1342 static void
1343 init_elimination (void)
1344 {
1345   bool stop_to_sp_elimination_p;
1346   basic_block bb;
1347   rtx_insn *insn;
1348   struct lra_elim_table *ep;
1349
1350   init_elim_table ();
1351   FOR_EACH_BB_FN (bb, cfun)
1352     {
1353       curr_sp_change = 0;
1354       stop_to_sp_elimination_p = false;
1355       FOR_BB_INSNS (bb, insn)
1356         if (INSN_P (insn))
1357           {
1358             lra_get_insn_recog_data (insn)->sp_offset = curr_sp_change;
1359             if (NONDEBUG_INSN_P (insn))
1360               {
1361                 mark_not_eliminable (PATTERN (insn), VOIDmode);
1362                 if (curr_sp_change != 0
1363                     && find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX))
1364                   stop_to_sp_elimination_p = true;
1365               }
1366           }
1367       if (! frame_pointer_needed
1368           && (curr_sp_change != 0 || stop_to_sp_elimination_p)
1369           && bb->succs && bb->succs->length () != 0)
1370         for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1371           if (ep->to == STACK_POINTER_REGNUM)
1372             setup_can_eliminate (ep, false);
1373     }
1374   setup_elimination_map ();
1375 }
1376
1377 /* Eliminate hard reg given by its location LOC.  */
1378 void
1379 lra_eliminate_reg_if_possible (rtx *loc)
1380 {
1381   int regno;
1382   struct lra_elim_table *ep;
1383
1384   lra_assert (REG_P (*loc));
1385   if ((regno = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER
1386       || ! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno))
1387     return;
1388   if ((ep = get_elimination (*loc)) != NULL)
1389     *loc = ep->to_rtx;
1390 }
1391
1392 /* Do (final if FINAL_P or first if FIRST_P) elimination in INSN.  Add
1393    the insn for subsequent processing in the constraint pass, update
1394    the insn info.  */
1395 static void
1396 process_insn_for_elimination (rtx_insn *insn, bool final_p, bool first_p)
1397 {
1398   eliminate_regs_in_insn (insn, final_p, first_p, 0);
1399   if (! final_p)
1400     {
1401       /* Check that insn changed its code.  This is a case when a move
1402          insn becomes an add insn and we do not want to process the
1403          insn as a move anymore.  */
1404       int icode = recog (PATTERN (insn), insn, 0);
1405
1406       if (icode >= 0 && icode != INSN_CODE (insn))
1407         {
1408           INSN_CODE (insn) = icode;
1409           lra_update_insn_recog_data (insn);
1410         }
1411       lra_update_insn_regno_info (insn);
1412       lra_push_insn (insn);
1413       lra_set_used_insn_alternative (insn, -1);
1414     }
1415 }
1416
1417 /* Entry function to do final elimination if FINAL_P or to update
1418    elimination register offsets (FIRST_P if we are doing it the first
1419    time).  */
1420 void
1421 lra_eliminate (bool final_p, bool first_p)
1422 {
1423   unsigned int uid;
1424   bitmap_head insns_with_changed_offsets;
1425   bitmap_iterator bi;
1426   struct lra_elim_table *ep;
1427
1428   gcc_assert (! final_p || ! first_p);
1429
1430   timevar_push (TV_LRA_ELIMINATE);
1431
1432   if (first_p)
1433     init_elimination ();
1434
1435   bitmap_initialize (&insns_with_changed_offsets, &reg_obstack);
1436   if (final_p)
1437     {
1438 #ifdef ENABLE_CHECKING
1439       update_reg_eliminate (&insns_with_changed_offsets);
1440       if (! bitmap_empty_p (&insns_with_changed_offsets))
1441         gcc_unreachable ();
1442 #endif
1443       /* We change eliminable hard registers in insns so we should do
1444          this for all insns containing any eliminable hard
1445          register.  */
1446       for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
1447         if (elimination_map[ep->from] != NULL)
1448           bitmap_ior_into (&insns_with_changed_offsets,
1449                            &lra_reg_info[ep->from].insn_bitmap);
1450     }
1451   else if (! update_reg_eliminate (&insns_with_changed_offsets))
1452     goto lra_eliminate_done;
1453   if (lra_dump_file != NULL)
1454     {
1455       fprintf (lra_dump_file, "New elimination table:\n");
1456       print_elim_table (lra_dump_file);
1457     }
1458   EXECUTE_IF_SET_IN_BITMAP (&insns_with_changed_offsets, 0, uid, bi)
1459     /* A dead insn can be deleted in process_insn_for_elimination.  */
1460     if (lra_insn_recog_data[uid] != NULL)
1461       process_insn_for_elimination (lra_insn_recog_data[uid]->insn,
1462                                     final_p, first_p);
1463   bitmap_clear (&insns_with_changed_offsets);
1464
1465 lra_eliminate_done:
1466   timevar_pop (TV_LRA_ELIMINATE);
1467 }