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