gcc/lra-eliminations.c

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