2012-10-23 Vladimir Makarov <vmakarov@redhat.com>

	* dbxout.c (dbxout_symbol_location): Pass new argument to
	alter_subreg.
	* dwarf2out.c: Include ira.h and lra.h.
	(based_loc_descr, compute_frame_pointer_to_fb_displacement): Use
	lra_eliminate_regs for LRA instead of eliminate_regs.
	* expr.c (emit_move_insn_1): Pass an additional argument to
	emit_move_via_integer.  Use emit_move_via_integer for LRA only if
	the insn is recognized.
	* emit-rtl.c (gen_rtx_REG): Add lra_in_progress.
	(validate_subreg): Don't check offset for LRA and floating point
	modes.
	* final.c (final_scan_insn, cleanup_subreg_operands): Pass new
	argument to alter_subreg.
	(walk_alter_subreg, output_operand): Ditto.
	(alter_subreg): Add new argument.
	* gcse.c (calculate_bb_reg_pressure): Add parameter to
	ira_setup_eliminable_regset call.
	* ira.c: Include lra.h.
	(ira_init_once, ira_init, ira_finish_once): Call lra_start_once,
	lra_init, lra_finish_once in anyway.
	(ira_setup_eliminable_regset): Add parameter.  Remove need_fp.
	Call lra_init_elimination and mark HARD_FRAME_POINTER_REGNUM as
	living forever if frame_pointer_needed.
	(setup_reg_class_relations): Set up ira_reg_class_subset.
	(ira_reg_equiv_invariant_p, ira_reg_equiv_const): Remove.
	(find_reg_equiv_invariant_const): Ditto.
	(setup_reg_renumber): Use ira_equiv_no_lvalue_p instead of
	ira_reg_equiv_invariant_p.  Skip caps for LRA.
	(setup_reg_equiv_init, ira_update_equiv_info_by_shuffle_insn): New
	functions.
	(ira_reg_equiv_len, ira_reg_equiv): New externals.
	(ira_reg_equiv): New.
	(ira_expand_reg_equiv, init_reg_equiv, finish_reg_equiv): New
	functions.
	(no_equiv, update_equiv_regs): Use ira_reg_equiv instead of
	reg_equiv_init.
	(setup_reg_equiv): New function.
	(ira_use_lra_p): New global.
	(ira): Set up lra_simple_p and ira_conflicts_p.  Set up and
	restore flag_caller_saves and flag_ira_region.  Move
	initialization of ira_obstack and ira_bitmap_obstack upper.  Call
	init_reg_equiv, setup_reg_equiv, and setup_reg_equiv_init instead
	of initialization of ira_reg_equiv_len, ira_reg_equiv_invariant_p,
	and ira_reg_equiv_const.  Call ira_setup_eliminable_regset with a
	new argument.  Don't flatten IRA IRA for LRA.  Don't reassign
	conflict allocnos for LRA. Call finish_reg_equiv.
        (do_reload): Prepare code for LRA call.  Call LRA.
	* ira.h (ira_use_lra_p): New external.
	(struct target_ira): Add members x_ira_class_subset_p
	x_ira_reg_class_subset, and x_ira_reg_classes_intersect_p.
	(ira_class_subset_p, ira_reg_class_subset): New macros.
	(ira_reg_classes_intersect_p): New macro.
	(struct ira_reg_equiv): New.
	(ira_setup_eliminable_regset): Add an argument.
	(ira_expand_reg_equiv, ira_update_equiv_info_by_shuffle_insn): New
	prototypes.
	* ira-color.c (color_pass, move_spill_restore, coalesce_allocnos):
	Use ira_equiv_no_lvalue_p.
	(coalesce_spill_slots, ira_sort_regnos_for_alter_reg): Ditto.
	* ira-emit.c (ira_create_new_reg): Call ira_expand_reg_equiv.
	(generate_edge_moves, change_loop) Use ira_equiv_no_lvalue_p.
	(emit_move_list): Simplify code.  Call
	ira_update_equiv_info_by_shuffle_insn.  Use ira_reg_equiv instead
	of ira_reg_equiv_invariant_p and ira_reg_equiv_const.  Change
	assert.
	* ira-int.h (struct target_ira_int): Remove x_ira_class_subset_p
	and x_ira_reg_classes_intersect_p.
	(ira_class_subset_p, ira_reg_classes_intersect_p): Remove.
	(ira_reg_equiv_len, ira_reg_equiv_invariant_p): Ditto.
	(ira_reg_equiv_const): Ditto.
	(ira_equiv_no_lvalue_p): New function.
	* jump.c (true_regnum): Always use hard_regno for subreg_get_info
	when lra is in progress.
	* haifa-sched.c (sched_init): Pass new argument to
	ira_setup_eliminable_regset.
	* loop-invariant.c (calculate_loop_reg_pressure): Pass new
	argument to ira_setup_eliminable_regset.
	* lra.h: New.
	* lra-int.h: Ditto.
	* lra.c: Ditto.
	* lra-assigns.c: Ditto.
	* lra-constraints.c: Ditto.
	* lra-coalesce.c: Ditto.
	* lra-eliminations.c: Ditto.
	* lra-lives.c: Ditto.
	* lra-spills.c: Ditto.
	* Makefile.in (LRA_INT_H): New.
	(OBJS): Add lra.o, lra-assigns.o, lra-coalesce.o,
	lra-constraints.o, lra-eliminations.o, lra-lives.o, and
	lra-spills.o.
	(dwarf2out.o): Add dependence on ira.h and lra.h.
	(ira.o): Add dependence on lra.h.
	(lra.o, lra-assigns.o, lra-coalesce.o, lra-constraints.o): New
	entries.
	(lra-eliminations.o, lra-lives.o, lra-spills.o): Ditto.
	* output.h (alter_subreg): Add new argument.
	* rtlanal.c (simplify_subreg_regno): Permit mode changes for LRA.
	Permit ARG_POINTER_REGNUM and STACK_POINTER_REGNUM for LRA.
	* recog.c (general_operand, register_operand): Accept paradoxical
	FLOAT_MODE subregs for LRA.
	(scratch_operand): Accept pseudos for LRA.
	* rtl.h (lra_in_progress): New external.
	(debug_bb_n_slim, debug_bb_slim, print_value_slim): New
	prototypes.
	(debug_rtl_slim, debug_insn_slim): Ditto.
	* sdbout.c (sdbout_symbol): Pass new argument to alter_subreg.
	* sched-vis.c (print_value_slim): New.
	* target.def (lra_p): New hook.
	(register_priority): Ditto.
	(different_addr_displacement_p): Ditto.
	(spill_class): Ditto.
	* target-globals.h (this_target_lra_int): New external.
	(target_globals): New member lra_int.
	(restore_target_globals): Restore this_target_lra_int.
	* target-globals.c: Include lra-int.h.
	(default_target_globals): Add &default_target_lra_int.
	* targhooks.c (default_lra_p): New function.
	(default_register_priority): Ditto.
	(default_different_addr_displacement_p): Ditto.
	* targhooks.h (default_lra_p): Declare.
	(default_register_priority): Ditto.
	(default_different_addr_displacement_p): Ditto.
	* timevar.def (TV_LRA, TV_LRA_ELIMINATE, TV_LRA_INHERITANCE): New.
	(TV_LRA_CREATE_LIVE_RANGES, TV_LRA_ASSIGN, TV_LRA_COALESCE): New.
	* config/arm/arm.c (load_multiple_sequence): Pass new argument toOB
	alter_subreg.
	(store_multiple_sequence): Ditto.
	* config/i386/i386.h (enum ix86_tune_indices): Add
	X86_TUNE_GENERAL_REGS_SSE_SPILL.
	(TARGET_GENERAL_REGS_SSE_SPILL): New macro.
	* config/i386/i386.c (initial_ix86_tune_features): Set up
	X86_TUNE_GENERAL_REGS_SSE_SPILL for m_COREI7 and m_CORE2I7.
	(ix86_lra_p, ix86_register_priority): New functions.
	(ix86_secondary_reload): Add NON_Q_REGS, SIREG, DIREG.
	(inline_secondary_memory_needed): Change assert.
	(ix86_spill_class): New function.
	(TARGET_LRA_P, TARGET_REGISTER_BANK, TARGET_SPILL_CLASS): New
	macros.
	* config/m68k/m68k.c (emit_move_sequence): Pass new argument to
	alter_subreg.
	* config/m32r/m32r.c (gen_split_move_double): Ditto.
	* config/pa/pa.c (pa_emit_move_sequence): Ditto.
	* config/sh/sh.md: Ditto.
	* config/v850/v850.c (v850_reorg): Ditto.
	* config/xtensa/xtensa.c (fixup_subreg_mem): Ditto.
	* doc/md.texi: Add new interpretation of hint * for LRA.
	* doc/passes.texi: Describe LRA pass.
	* doc/tm.texi.in: Add TARGET_LRA_P, TARGET_REGISTER_PRIORITY,
	TARGET_DIFFERENT_ADDR_DISPLACEMENT_P, and TARGET_SPILL_CLASS.
	* doc/tm.texi: Update.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@192719 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1301 insertions, 0 deletions

diff --git a/gcc/lra-eliminations.c b/gcc/lra-eliminations.c
new file mode 100644
index 00000000000..2222d805f1b
--- /dev/null
+++ b/gcc/lra-eliminations.c
@@ -0,0 +1,1301 @@
+/* Code for RTL register eliminations.
+   Copyright (C) 2010, 2011, 2012
+   Free Software Foundation, Inc.
+   Contributed by Vladimir Makarov <vmakarov@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.	If not see
+<http://www.gnu.org/licenses/>.	 */
+
+/* Eliminable registers (like a soft argument or frame pointer) are
+   widely used in RTL.  These eliminable registers should be replaced
+   by real hard registers (like the stack pointer or hard frame
+   pointer) plus some offset.  The offsets usually change whenever the
+   stack is expanded.  We know the final offsets only at the very end
+   of LRA.
+
+   Within LRA, we usually keep the RTL in such a state that the
+   eliminable registers can be replaced by just the corresponding hard
+   register (without any offset).  To achieve this we should add the
+   initial elimination offset at the beginning of LRA and update the
+   offsets whenever the stack is expanded.  We need to do this before
+   every constraint pass because the choice of offset often affects
+   whether a particular address or memory constraint is satisfied.
+
+   We keep RTL code at most time in such state that the virtual
+   registers can be changed by just the corresponding hard registers
+   (with zero offsets) and we have the right RTL code.	To achieve this
+   we should add initial offset at the beginning of LRA work and update
+   offsets after each stack expanding.	But actually we update virtual
+   registers to the same virtual registers + corresponding offsets
+   before every constraint pass because it affects constraint
+   satisfaction (e.g. an address displacement became too big for some
+   target).
+
+   The final change of eliminable registers to the corresponding hard
+   registers are done at the very end of LRA when there were no change
+   in offsets anymore:
+
+		     fp + 42	 =>	sp + 42
+
+*/
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "regs.h"
+#include "insn-config.h"
+#include "insn-codes.h"
+#include "recog.h"
+#include "output.h"
+#include "addresses.h"
+#include "target.h"
+#include "function.h"
+#include "expr.h"
+#include "basic-block.h"
+#include "except.h"
+#include "optabs.h"
+#include "df.h"
+#include "ira.h"
+#include "rtl-error.h"
+#include "lra-int.h"
+
+/* This structure is used to record information about hard register
+   eliminations.  */
+struct elim_table
+{
+  /* Hard register number to be eliminated.  */
+  int from;			
+  /* Hard register number used as replacement.	*/
+  int to;			
+  /* Difference between values of the two hard registers above on
+     previous iteration.  */
+  HOST_WIDE_INT previous_offset;
+  /* Difference between the values on the current iteration.  */
+  HOST_WIDE_INT offset;		
+  /* Nonzero if this elimination can be done.  */
+  bool can_eliminate;		
+  /* CAN_ELIMINATE since the last check.  */
+  bool prev_can_eliminate;
+  /* REG rtx for the register to be eliminated.	 We cannot simply
+     compare the number since we might then spuriously replace a hard
+     register corresponding to a pseudo assigned to the reg to be
+     eliminated.  */
+  rtx from_rtx;			
+  /* REG rtx for the replacement.  */
+  rtx to_rtx;			
+};
+
+/* The elimination table.  Each array entry describes one possible way
+   of eliminating a register in favor of another.  If there is more
+   than one way of eliminating a particular register, the most
+   preferred should be specified first.	 */
+static struct elim_table *reg_eliminate = 0;
+
+/* This is an intermediate structure to initialize the table.  It has
+   exactly the members provided by ELIMINABLE_REGS.  */
+static const struct elim_table_1
+{
+  const int from;
+  const int to;
+} reg_eliminate_1[] =
+
+/* If a set of eliminable hard registers was specified, define the
+   table from it.  Otherwise, default to the normal case of the frame
+   pointer being replaced by the stack pointer.	 */
+
+#ifdef ELIMINABLE_REGS
+  ELIMINABLE_REGS;
+#else
+  {{ FRAME_POINTER_REGNUM, STACK_POINTER_REGNUM}};
+#endif
+
+#define NUM_ELIMINABLE_REGS ARRAY_SIZE (reg_eliminate_1)
+
+/* Print info about elimination table to file F.  */
+static void
+print_elim_table (FILE *f)
+{
+  struct elim_table *ep;
+
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    fprintf (f, "%s eliminate %d to %d (offset=" HOST_WIDE_INT_PRINT_DEC
+	     ", prev_offset=" HOST_WIDE_INT_PRINT_DEC ")\n",
+	     ep->can_eliminate ? "Can" : "Can't",
+	     ep->from, ep->to, ep->offset, ep->previous_offset);
+}
+
+/* Print info about elimination table to stderr.  */
+void
+lra_debug_elim_table (void)
+{
+  print_elim_table (stderr);
+}
+
+/* Setup possibility of elimination in elimination table element EP to
+   VALUE.  Setup FRAME_POINTER_NEEDED if elimination from frame
+   pointer to stack pointer is not possible anymore.  */
+static void
+setup_can_eliminate (struct elim_table *ep, bool value)
+{
+  ep->can_eliminate = ep->prev_can_eliminate = value;
+  if (! value
+      && ep->from == FRAME_POINTER_REGNUM && ep->to == STACK_POINTER_REGNUM)
+    frame_pointer_needed = 1;
+}
+
+/* Map: eliminable "from" register -> its current elimination,
+   or NULL if none.  The elimination table may contain more than
+   one elimination for the same hard register, but this map specifies
+   the one that we are currently using.  */
+static struct elim_table *elimination_map[FIRST_PSEUDO_REGISTER];
+
+/* When an eliminable hard register becomes not eliminable, we use the
+   following special structure to restore original offsets for the
+   register.  */
+static struct elim_table self_elim_table;
+
+/* Offsets should be used to restore original offsets for eliminable
+   hard register which just became not eliminable.  Zero,
+   otherwise.  */
+static HOST_WIDE_INT self_elim_offsets[FIRST_PSEUDO_REGISTER];
+
+/* Map: hard regno -> RTL presentation.	 RTL presentations of all
+   potentially eliminable hard registers are stored in the map.	 */
+static rtx eliminable_reg_rtx[FIRST_PSEUDO_REGISTER];
+
+/* Set up ELIMINATION_MAP of the currently used eliminations.  */
+static void
+setup_elimination_map (void)
+{
+  int i;
+  struct elim_table *ep;
+
+  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+    elimination_map[i] = NULL;
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    if (ep->can_eliminate && elimination_map[ep->from] == NULL)
+      elimination_map[ep->from] = ep;
+}
+
+
+
+/* Compute the sum of X and Y, making canonicalizations assumed in an
+   address, namely: sum constant integers, surround the sum of two
+   constants with a CONST, put the constant as the second operand, and
+   group the constant on the outermost sum.
+
+   This routine assumes both inputs are already in canonical form.  */
+static rtx
+form_sum (rtx x, rtx y)
+{
+  rtx tem;
+  enum machine_mode mode = GET_MODE (x);
+
+  if (mode == VOIDmode)
+    mode = GET_MODE (y);
+
+  if (mode == VOIDmode)
+    mode = Pmode;
+
+  if (CONST_INT_P (x))
+    return plus_constant (mode, y, INTVAL (x));
+  else if (CONST_INT_P (y))
+    return plus_constant (mode, x, INTVAL (y));
+  else if (CONSTANT_P (x))
+    tem = x, x = y, y = tem;
+
+  if (GET_CODE (x) == PLUS && CONSTANT_P (XEXP (x, 1)))
+    return form_sum (XEXP (x, 0), form_sum (XEXP (x, 1), y));
+
+  /* Note that if the operands of Y are specified in the opposite
+     order in the recursive calls below, infinite recursion will
+     occur.  */
+  if (GET_CODE (y) == PLUS && CONSTANT_P (XEXP (y, 1)))
+    return form_sum (form_sum (x, XEXP (y, 0)), XEXP (y, 1));
+
+  /* If both constant, encapsulate sum.	 Otherwise, just form sum.  A
+     constant will have been placed second.  */
+  if (CONSTANT_P (x) && CONSTANT_P (y))
+    {
+      if (GET_CODE (x) == CONST)
+	x = XEXP (x, 0);
+      if (GET_CODE (y) == CONST)
+	y = XEXP (y, 0);
+
+      return gen_rtx_CONST (VOIDmode, gen_rtx_PLUS (mode, x, y));
+    }
+
+  return gen_rtx_PLUS (mode, x, y);
+}
+
+/* Return the current substitution hard register of the elimination of
+   HARD_REGNO.	If HARD_REGNO is not eliminable, return itself.	 */
+int
+lra_get_elimination_hard_regno (int hard_regno)
+{
+  struct elim_table *ep;
+
+  if (hard_regno < 0 || hard_regno >= FIRST_PSEUDO_REGISTER)
+    return hard_regno;
+  if ((ep = elimination_map[hard_regno]) == NULL)
+    return hard_regno;
+  return ep->to;
+}
+
+/* Return elimination which will be used for hard reg REG, NULL
+   otherwise.  */
+static struct elim_table *
+get_elimination (rtx reg)
+{
+  int hard_regno;
+  struct elim_table *ep;
+  HOST_WIDE_INT offset;
+
+  lra_assert (REG_P (reg));
+  if ((hard_regno = REGNO (reg)) < 0 || hard_regno >= FIRST_PSEUDO_REGISTER)
+    return NULL;
+  if ((ep = elimination_map[hard_regno]) != NULL)
+    return ep->from_rtx != reg ? NULL : ep;
+  if ((offset = self_elim_offsets[hard_regno]) == 0)
+    return NULL;
+  /* This is an iteration to restore offsets just after HARD_REGNO
+     stopped to be eliminable.	*/
+  self_elim_table.from = self_elim_table.to = hard_regno;
+  self_elim_table.from_rtx
+    = self_elim_table.to_rtx
+    = eliminable_reg_rtx[hard_regno];
+  lra_assert (self_elim_table.from_rtx != NULL);
+  self_elim_table.offset = offset;
+  return &self_elim_table;
+}
+
+/* Scan X and replace any eliminable registers (such as fp) with a
+   replacement (such as sp) if SUBST_P, plus an offset.	 The offset is
+   a change in the offset between the eliminable register and its
+   substitution if UPDATE_P, or the full offset if FULL_P, or
+   otherwise zero.
+
+   MEM_MODE is the mode of an enclosing MEM.  We need this to know how
+   much to adjust a register for, e.g., PRE_DEC.  Also, if we are
+   inside a MEM, we are allowed to replace a sum of a hard register
+   and the constant zero with the hard register, which we cannot do
+   outside a MEM.  In addition, we need to record the fact that a
+   hard register is referenced outside a MEM.
+
+   Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
+   That's used when we eliminate in expressions stored in notes.  */
+rtx
+lra_eliminate_regs_1 (rtx x, enum machine_mode mem_mode,
+		      bool subst_p, bool update_p, bool full_p)
+{
+  enum rtx_code code = GET_CODE (x);
+  struct elim_table *ep;
+  rtx new_rtx;
+  int i, j;
+  const char *fmt;
+  int copied = 0;
+
+  if (! current_function_decl)
+    return x;
+
+  switch (code)
+    {
+    CASE_CONST_ANY:
+    case CONST:
+    case SYMBOL_REF:
+    case CODE_LABEL:
+    case PC:
+    case CC0:
+    case ASM_INPUT:
+    case ADDR_VEC:
+    case ADDR_DIFF_VEC:
+    case RETURN:
+      return x;
+
+    case REG:
+      /* First handle the case where we encounter a bare hard register
+	 that is eliminable.  Replace it with a PLUS.  */
+      if ((ep = get_elimination (x)) != NULL)
+	{
+	  rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
+	  
+	  if (update_p)
+	    return plus_constant (Pmode, to, ep->offset - ep->previous_offset);
+	  else if (full_p)
+	    return plus_constant (Pmode, to, ep->offset);
+	  else
+	    return to;
+	}
+      return x;
+
+    case PLUS:
+      /* If this is the sum of an eliminable register and a constant, rework
+	 the sum.  */
+      if (REG_P (XEXP (x, 0)) && CONSTANT_P (XEXP (x, 1)))
+	{
+	  if ((ep = get_elimination (XEXP (x, 0))) != NULL)
+	    {
+	      HOST_WIDE_INT offset;
+	      rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
+	      
+	      if (! update_p && ! full_p)
+		return gen_rtx_PLUS (Pmode, to, XEXP (x, 1));
+	      
+	      offset = (update_p
+			? ep->offset - ep->previous_offset : ep->offset);
+	      if (CONST_INT_P (XEXP (x, 1))
+		  && INTVAL (XEXP (x, 1)) == -offset)
+		return to;
+	      else
+		return gen_rtx_PLUS (Pmode, to,
+				     plus_constant (Pmode,
+						    XEXP (x, 1), offset));
+	    }
+
+	  /* If the hard register is not eliminable, we are done since
+	     the other operand is a constant.  */
+	  return x;
+	}
+
+      /* If this is part of an address, we want to bring any constant
+	 to the outermost PLUS.  We will do this by doing hard
+	 register replacement in our operands and seeing if a constant
+	 shows up in one of them.
+
+	 Note that there is no risk of modifying the structure of the
+	 insn, since we only get called for its operands, thus we are
+	 either modifying the address inside a MEM, or something like
+	 an address operand of a load-address insn.  */
+
+      {
+	rtx new0 = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode,
+					 subst_p, update_p, full_p);
+	rtx new1 = lra_eliminate_regs_1 (XEXP (x, 1), mem_mode,
+					 subst_p, update_p, full_p);
+
+	if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
+	  return form_sum (new0, new1);
+      }
+      return x;
+
+    case MULT:
+      /* If this is the product of an eliminable hard register and a
+	 constant, apply the distribute law and move the constant out
+	 so that we have (plus (mult ..) ..).  This is needed in order
+	 to keep load-address insns valid.  This case is pathological.
+	 We ignore the possibility of overflow here.  */
+      if (REG_P (XEXP (x, 0)) && CONST_INT_P (XEXP (x, 1))
+	  && (ep = get_elimination (XEXP (x, 0))) != NULL)
+	{
+	  rtx to = subst_p ? ep->to_rtx : ep->from_rtx;
+	  
+	  if (update_p)
+	    return
+	      plus_constant (Pmode,
+			     gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
+			     (ep->offset - ep->previous_offset)
+			     * INTVAL (XEXP (x, 1)));
+	  else if (full_p)
+	    return
+	      plus_constant (Pmode,
+			     gen_rtx_MULT (Pmode, to, XEXP (x, 1)),
+			     ep->offset * INTVAL (XEXP (x, 1)));
+	  else
+	    return gen_rtx_MULT (Pmode, to, XEXP (x, 1));
+	}
+      
+      /* ... fall through ...  */
+
+    case CALL:
+    case COMPARE:
+    /* See comments before PLUS about handling MINUS.  */
+    case MINUS:
+    case DIV:	   case UDIV:
+    case MOD:	   case UMOD:
+    case AND:	   case IOR:	  case XOR:
+    case ROTATERT: case ROTATE:
+    case ASHIFTRT: case LSHIFTRT: case ASHIFT:
+    case NE:	   case EQ:
+    case GE:	   case GT:	  case GEU:    case GTU:
+    case LE:	   case LT:	  case LEU:    case LTU:
+      {
+	rtx new0 = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode,
+					 subst_p, update_p, full_p);
+	rtx new1 = XEXP (x, 1)
+		   ? lra_eliminate_regs_1 (XEXP (x, 1), mem_mode,
+					   subst_p, update_p, full_p) : 0;
+
+	if (new0 != XEXP (x, 0) || new1 != XEXP (x, 1))
+	  return gen_rtx_fmt_ee (code, GET_MODE (x), new0, new1);
+      }
+      return x;
+
+    case EXPR_LIST:
+      /* If we have something in XEXP (x, 0), the usual case,
+	 eliminate it.	*/
+      if (XEXP (x, 0))
+	{
+	  new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode,
+					  subst_p, update_p, full_p);
+	  if (new_rtx != XEXP (x, 0))
+	    {
+	      /* If this is a REG_DEAD note, it is not valid anymore.
+		 Using the eliminated version could result in creating a
+		 REG_DEAD note for the stack or frame pointer.	*/
+	      if (REG_NOTE_KIND (x) == REG_DEAD)
+		return (XEXP (x, 1)
+			? lra_eliminate_regs_1 (XEXP (x, 1), mem_mode,
+						subst_p, update_p, full_p)
+			: NULL_RTX);
+
+	      x = alloc_reg_note (REG_NOTE_KIND (x), new_rtx, XEXP (x, 1));
+	    }
+	}
+
+      /* ... fall through ...  */
+
+    case INSN_LIST:
+      /* Now do eliminations in the rest of the chain.	If this was
+	 an EXPR_LIST, this might result in allocating more memory than is
+	 strictly needed, but it simplifies the code.  */
+      if (XEXP (x, 1))
+	{
+	  new_rtx = lra_eliminate_regs_1 (XEXP (x, 1), mem_mode,
+					  subst_p, update_p, full_p);
+	  if (new_rtx != XEXP (x, 1))
+	    return
+	      gen_rtx_fmt_ee (GET_CODE (x), GET_MODE (x),
+			      XEXP (x, 0), new_rtx);
+	}
+      return x;
+
+    case PRE_INC:
+    case POST_INC:
+    case PRE_DEC:
+    case POST_DEC:
+      /* We do not support elimination of a register that is modified.
+	 elimination_effects has already make sure that this does not
+	 happen.  */
+      return x;
+
+    case PRE_MODIFY:
+    case POST_MODIFY:
+      /* We do not support elimination of a hard register that is
+	 modified.  LRA has already make sure that this does not
+	 happen. The only remaining case we need to consider here is
+	 that the increment value may be an eliminable register.  */
+      if (GET_CODE (XEXP (x, 1)) == PLUS
+	  && XEXP (XEXP (x, 1), 0) == XEXP (x, 0))
+	{
+	  rtx new_rtx = lra_eliminate_regs_1 (XEXP (XEXP (x, 1), 1), mem_mode,
+					      subst_p, update_p, full_p);
+
+	  if (new_rtx != XEXP (XEXP (x, 1), 1))
+	    return gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (x, 0),
+				   gen_rtx_PLUS (GET_MODE (x),
+						 XEXP (x, 0), new_rtx));
+	}
+      return x;
+
+    case STRICT_LOW_PART:
+    case NEG:	       case NOT:
+    case SIGN_EXTEND:  case ZERO_EXTEND:
+    case TRUNCATE:     case FLOAT_EXTEND: case FLOAT_TRUNCATE:
+    case FLOAT:	       case FIX:
+    case UNSIGNED_FIX: case UNSIGNED_FLOAT:
+    case ABS:
+    case SQRT:
+    case FFS:
+    case CLZ:
+    case CTZ:
+    case POPCOUNT:
+    case PARITY:
+    case BSWAP:
+      new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), mem_mode,
+				      subst_p, update_p, full_p);
+      if (new_rtx != XEXP (x, 0))
+	return gen_rtx_fmt_e (code, GET_MODE (x), new_rtx);
+      return x;
+
+    case SUBREG:
+      new_rtx = lra_eliminate_regs_1 (SUBREG_REG (x), mem_mode,
+				      subst_p, update_p, full_p);
+
+      if (new_rtx != SUBREG_REG (x))
+	{
+	  int x_size = GET_MODE_SIZE (GET_MODE (x));
+	  int new_size = GET_MODE_SIZE (GET_MODE (new_rtx));
+
+	  if (MEM_P (new_rtx) && x_size <= new_size)
+	    {
+	      SUBREG_REG (x) = new_rtx;
+	      alter_subreg (&x, false);
+	      return x;
+	    }
+	  else
+	    return gen_rtx_SUBREG (GET_MODE (x), new_rtx, SUBREG_BYTE (x));
+	}
+
+      return x;
+
+    case MEM:
+      /* Our only special processing is to pass the mode of the MEM to our
+	 recursive call and copy the flags.  While we are here, handle this
+	 case more efficiently.	 */
+      return
+	replace_equiv_address_nv
+	(x,
+	 lra_eliminate_regs_1 (XEXP (x, 0), GET_MODE (x),
+			       subst_p, update_p, full_p));
+
+    case USE:
+      /* Handle insn_list USE that a call to a pure function may generate.  */
+      new_rtx = lra_eliminate_regs_1 (XEXP (x, 0), VOIDmode,
+				      subst_p, update_p, full_p);
+      if (new_rtx != XEXP (x, 0))
+	return gen_rtx_USE (GET_MODE (x), new_rtx);
+      return x;
+
+    case CLOBBER:
+    case SET:
+      gcc_unreachable ();
+
+    default:
+      break;
+    }
+
+  /* Process each of our operands recursively.	If any have changed, make a
+     copy of the rtx.  */
+  fmt = GET_RTX_FORMAT (code);
+  for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
+    {
+      if (*fmt == 'e')
+	{
+	  new_rtx = lra_eliminate_regs_1 (XEXP (x, i), mem_mode,
+					  subst_p, update_p, full_p);
+	  if (new_rtx != XEXP (x, i) && ! copied)
+	    {
+	      x = shallow_copy_rtx (x);
+	      copied = 1;
+	    }
+	  XEXP (x, i) = new_rtx;
+	}
+      else if (*fmt == 'E')
+	{
+	  int copied_vec = 0;
+	  for (j = 0; j < XVECLEN (x, i); j++)
+	    {
+	      new_rtx = lra_eliminate_regs_1 (XVECEXP (x, i, j), mem_mode,
+					      subst_p, update_p, full_p);
+	      if (new_rtx != XVECEXP (x, i, j) && ! copied_vec)
+		{
+		  rtvec new_v = gen_rtvec_v (XVECLEN (x, i),
+					     XVEC (x, i)->elem);
+		  if (! copied)
+		    {
+		      x = shallow_copy_rtx (x);
+		      copied = 1;
+		    }
+		  XVEC (x, i) = new_v;
+		  copied_vec = 1;
+		}
+	      XVECEXP (x, i, j) = new_rtx;
+	    }
+	}
+    }
+
+  return x;
+}
+
+/* This function is used externally in subsequent passes of GCC.  It
+   always does a full elimination of X.	 */
+rtx
+lra_eliminate_regs (rtx x, enum machine_mode mem_mode,
+		    rtx insn ATTRIBUTE_UNUSED)
+{
+  return lra_eliminate_regs_1 (x, mem_mode, true, false, true);
+}
+
+/* Scan rtx X for references to elimination source or target registers
+   in contexts that would prevent the elimination from happening.
+   Update the table of eliminables to reflect the changed state.
+   MEM_MODE is the mode of an enclosing MEM rtx, or VOIDmode if not
+   within a MEM.  */
+static void
+mark_not_eliminable (rtx x)
+{
+  enum rtx_code code = GET_CODE (x);
+  struct elim_table *ep;
+  int i, j;
+  const char *fmt;
+
+  switch (code)
+    {
+    case PRE_INC:
+    case POST_INC:
+    case PRE_DEC:
+    case POST_DEC:
+    case POST_MODIFY:
+    case PRE_MODIFY:
+      if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
+	/* If we modify the source of an elimination rule, disable
+	   it. Do the same if it is the source and not the hard frame
+	   register.  */
+	for (ep = reg_eliminate;
+	     ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
+	       ep++)
+	  if (ep->from_rtx == XEXP (x, 0)
+	      || (ep->to_rtx == XEXP (x, 0)
+		  && ep->to_rtx != hard_frame_pointer_rtx))
+	    setup_can_eliminate (ep, false);
+      return;
+
+    case USE:
+      if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
+	/* If using a hard register that is the source of an eliminate
+	   we still think can be performed, note it cannot be
+	   performed since we don't know how this hard register is
+	   used.  */
+	for (ep = reg_eliminate;
+	     ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
+	     ep++)
+	  if (ep->from_rtx == XEXP (x, 0)
+	      && ep->to_rtx != hard_frame_pointer_rtx)
+	    setup_can_eliminate (ep, false);
+      return;
+
+    case CLOBBER:
+      if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
+	/* If clobbering a hard register that is the replacement
+	   register for an elimination we still think can be
+	   performed, note that it cannot be performed.	 Otherwise, we
+	   need not be concerned about it.  */
+	for (ep = reg_eliminate;
+	     ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
+	     ep++)
+	  if (ep->to_rtx == XEXP (x, 0)
+	      && ep->to_rtx != hard_frame_pointer_rtx)
+	    setup_can_eliminate (ep, false);
+      return;
+
+    case SET:
+      /* Check for setting a hard register that we know about.	*/
+      if (REG_P (SET_DEST (x)) && REGNO (SET_DEST (x)) < FIRST_PSEUDO_REGISTER)
+	{
+	  /* See if this is setting the replacement hard register for
+	     an elimination.
+
+	     If DEST is the hard frame pointer, we do nothing because
+	     we assume that all assignments to the frame pointer are
+	     for non-local gotos and are being done at a time when
+	     they are valid and do not disturb anything else.  Some
+	     machines want to eliminate a fake argument pointer (or
+	     even a fake frame pointer) with either the real frame
+	     pointer or the stack pointer.  Assignments to the hard
+	     frame pointer must not prevent this elimination.  */
+
+	  for (ep = reg_eliminate;
+	       ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
+	       ep++)
+	    if (ep->to_rtx == SET_DEST (x)
+		&& SET_DEST (x) != hard_frame_pointer_rtx)
+	      setup_can_eliminate (ep, false);
+	}
+
+      mark_not_eliminable (SET_DEST (x));
+      mark_not_eliminable (SET_SRC (x));
+      return;
+
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = 0; i < GET_RTX_LENGTH (code); i++, fmt++)
+    {
+      if (*fmt == 'e')
+	mark_not_eliminable (XEXP (x, i));
+      else if (*fmt == 'E')
+	for (j = 0; j < XVECLEN (x, i); j++)
+	  mark_not_eliminable (XVECEXP (x, i, j));
+    }
+}
+
+
+
+/* Scan INSN and eliminate all eliminable hard registers in it.
+
+   If REPLACE_P is true, do the replacement destructively.  Also
+   delete the insn as dead it if it is setting an eliminable register.
+
+   If REPLACE_P is false, just update the offsets while keeping the
+   base register the same.  */
+
+static void
+eliminate_regs_in_insn (rtx insn, bool replace_p)
+{
+  int icode = recog_memoized (insn);
+  rtx old_set = single_set (insn);
+  bool validate_p;
+  int i;
+  rtx substed_operand[MAX_RECOG_OPERANDS];
+  rtx orig_operand[MAX_RECOG_OPERANDS];
+  struct elim_table *ep;
+  rtx plus_src, plus_cst_src;
+  lra_insn_recog_data_t id;
+  struct lra_static_insn_data *static_id;
+
+  if (icode < 0 && asm_noperands (PATTERN (insn)) < 0 && ! DEBUG_INSN_P (insn))
+    {
+      lra_assert (GET_CODE (PATTERN (insn)) == USE
+		  || GET_CODE (PATTERN (insn)) == CLOBBER
+		  || GET_CODE (PATTERN (insn)) == ADDR_VEC
+		  || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC
+		  || GET_CODE (PATTERN (insn)) == ASM_INPUT);
+      return;
+    }
+
+  /* Check for setting an eliminable register.	*/
+  if (old_set != 0 && REG_P (SET_DEST (old_set))
+      && (ep = get_elimination (SET_DEST (old_set))) != NULL)
+    {
+      bool delete_p = replace_p;
+      
+#ifdef HARD_FRAME_POINTER_REGNUM
+      /* If this is setting the frame pointer register to the hardware
+	 frame pointer register and this is an elimination that will
+	 be done (tested above), this insn is really adjusting the
+	 frame pointer downward to compensate for the adjustment done
+	 before a nonlocal goto.  */
+      if (ep->from == FRAME_POINTER_REGNUM
+	  && ep->to == HARD_FRAME_POINTER_REGNUM)
+	{
+	  if (replace_p)
+	    {
+	      SET_DEST (old_set) = ep->to_rtx;
+	      lra_update_insn_recog_data (insn);
+	      return;
+	    }
+	  else
+	    {
+	      rtx base = SET_SRC (old_set);
+	      HOST_WIDE_INT offset = 0;
+	      rtx base_insn = insn;
+	      
+	      while (base != ep->to_rtx)
+		{
+		  rtx prev_insn, prev_set;
+		  
+		  if (GET_CODE (base) == PLUS && CONST_INT_P (XEXP (base, 1)))
+		    {
+		      offset += INTVAL (XEXP (base, 1));
+		      base = XEXP (base, 0);
+		    }
+		  else if ((prev_insn = prev_nonnote_insn (base_insn)) != 0
+			   && (prev_set = single_set (prev_insn)) != 0
+			   && rtx_equal_p (SET_DEST (prev_set), base))
+		    {
+		      base = SET_SRC (prev_set);
+		      base_insn = prev_insn;
+		    }
+		  else
+		    break;
+		}
+	      
+	      if (base == ep->to_rtx)
+		{
+		  rtx src;
+		  
+		  offset -= (ep->offset - ep->previous_offset);
+		  src = plus_constant (Pmode, ep->to_rtx, offset);
+		  
+		  /* First see if this insn remains valid when we make
+		     the change.  If not, keep the INSN_CODE the same
+		     and let the constraint pass fit it up.  */
+		  validate_change (insn, &SET_SRC (old_set), src, 1);
+		  validate_change (insn, &SET_DEST (old_set),
+				   ep->from_rtx, 1);
+		  if (! apply_change_group ())
+		    {
+		      SET_SRC (old_set) = src;
+		      SET_DEST (old_set) = ep->from_rtx;
+		    }
+		  lra_update_insn_recog_data (insn);
+		  return;
+		}
+	    }
+	  
+	  
+	  /* We can't delete this insn, but needn't process it
+	     since it won't be used unless something changes.  */
+	  delete_p = false;
+	}
+#endif
+      
+      /* This insn isn't serving a useful purpose.  We delete it
+	 when REPLACE is set.  */
+      if (delete_p)
+	lra_delete_dead_insn (insn);
+      return;
+    }
+
+  /* We allow one special case which happens to work on all machines we
+     currently support: a single set with the source or a REG_EQUAL
+     note being a PLUS of an eliminable register and a constant.  */
+  plus_src = plus_cst_src = 0;
+  if (old_set && REG_P (SET_DEST (old_set)))
+    {
+      if (GET_CODE (SET_SRC (old_set)) == PLUS)
+	plus_src = SET_SRC (old_set);
+      /* First see if the source is of the form (plus (...) CST).  */
+      if (plus_src
+	  && CONST_INT_P (XEXP (plus_src, 1)))
+	plus_cst_src = plus_src;
+      /* Check that the first operand of the PLUS is a hard reg or
+	 the lowpart subreg of one.  */
+      if (plus_cst_src)
+	{
+	  rtx reg = XEXP (plus_cst_src, 0);
+
+	  if (GET_CODE (reg) == SUBREG && subreg_lowpart_p (reg))
+	    reg = SUBREG_REG (reg);
+
+	  if (!REG_P (reg) || REGNO (reg) >= FIRST_PSEUDO_REGISTER)
+	    plus_cst_src = 0;
+	}
+    }
+  if (plus_cst_src)
+    {
+      rtx reg = XEXP (plus_cst_src, 0);
+      HOST_WIDE_INT offset = INTVAL (XEXP (plus_cst_src, 1));
+
+      if (GET_CODE (reg) == SUBREG)
+	reg = SUBREG_REG (reg);
+
+      if (REG_P (reg) && (ep = get_elimination (reg)) != NULL)
+	{
+	  rtx to_rtx = replace_p ? ep->to_rtx : ep->from_rtx;
+	  
+	  if (! replace_p)
+	    {
+	      offset += (ep->offset - ep->previous_offset);
+	      offset = trunc_int_for_mode (offset, GET_MODE (plus_cst_src));
+	    }
+	  
+	  if (GET_CODE (XEXP (plus_cst_src, 0)) == SUBREG)
+	    to_rtx = gen_lowpart (GET_MODE (XEXP (plus_cst_src, 0)), to_rtx);
+	  /* If we have a nonzero offset, and the source is already a
+	     simple REG, the following transformation would increase
+	     the cost of the insn by replacing a simple REG with (plus
+	     (reg sp) CST).  So try only when we already had a PLUS
+	     before.  */
+	  if (offset == 0 || plus_src)
+	    {
+	      rtx new_src = plus_constant (GET_MODE (to_rtx), to_rtx, offset);
+	      
+	      old_set = single_set (insn);
+
+	      /* First see if this insn remains valid when we make the
+		 change.  If not, try to replace the whole pattern
+		 with a simple set (this may help if the original insn
+		 was a PARALLEL that was only recognized as single_set
+		 due to REG_UNUSED notes).  If this isn't valid
+		 either, keep the INSN_CODE the same and let the
+		 constraint pass fix it up.  */
+	      if (! validate_change (insn, &SET_SRC (old_set), new_src, 0))
+		{
+		  rtx new_pat = gen_rtx_SET (VOIDmode,
+					     SET_DEST (old_set), new_src);
+		  
+		  if (! validate_change (insn, &PATTERN (insn), new_pat, 0))
+		    SET_SRC (old_set) = new_src;
+		}
+	      lra_update_insn_recog_data (insn);
+	      /* This can't have an effect on elimination offsets, so skip
+		 right to the end.  */
+	      return;
+	    }
+	}
+    }
+
+  /* Eliminate all eliminable registers occurring in operands that
+     can be handled by the constraint pass.  */
+  id = lra_get_insn_recog_data (insn);
+  static_id = id->insn_static_data;
+  validate_p = false;
+  for (i = 0; i < static_id->n_operands; i++)
+    {
+      orig_operand[i] = *id->operand_loc[i];
+      substed_operand[i] = *id->operand_loc[i];
+
+      /* For an asm statement, every operand is eliminable.  */
+      if (icode < 0 || insn_data[icode].operand[i].eliminable)
+	{
+	  /* Check for setting a hard register that we know about.  */
+	  if (static_id->operand[i].type != OP_IN
+	      && REG_P (orig_operand[i]))
+	    {
+	      /* If we are assigning to a hard register that can be
+		 eliminated, it must be as part of a PARALLEL, since
+		 the code above handles single SETs.  This reg can not
+		 be longer eliminated -- it is forced by
+		 mark_not_eliminable.  */
+	      for (ep = reg_eliminate;
+		   ep < &reg_eliminate[NUM_ELIMINABLE_REGS];
+		   ep++)
+		lra_assert (ep->from_rtx != orig_operand[i]
+			    || ! ep->can_eliminate);
+	    }
+
+	  /* Companion to the above plus substitution, we can allow
+	     invariants as the source of a plain move.	*/
+	  substed_operand[i]
+	    = lra_eliminate_regs_1 (*id->operand_loc[i], VOIDmode,
+				    replace_p, ! replace_p, false);
+	  if (substed_operand[i] != orig_operand[i])
+	    validate_p = true;
+	}
+    }
+
+  /* Substitute the operands; the new values are in the substed_operand
+     array.  */
+  for (i = 0; i < static_id->n_operands; i++)
+    *id->operand_loc[i] = substed_operand[i];
+  for (i = 0; i < static_id->n_dups; i++)
+    *id->dup_loc[i] = substed_operand[(int) static_id->dup_num[i]];
+
+  if (validate_p)
+    {
+      /* If we had a move insn but now we don't, re-recognize it.
+	 This will cause spurious re-recognition if the old move had a
+	 PARALLEL since the new one still will, but we can't call
+	 single_set without having put new body into the insn and the
+	 re-recognition won't hurt in this rare case.  */
+      id = lra_update_insn_recog_data (insn);
+      static_id = id->insn_static_data;
+    }
+}
+
+/* Spill pseudos which are assigned to hard registers in SET.  Add
+   affected insns for processing in the subsequent constraint
+   pass.  */
+static void
+spill_pseudos (HARD_REG_SET set)
+{
+  int i;
+  bitmap_head to_process;
+  rtx insn;
+
+  if (hard_reg_set_empty_p (set))
+    return;
+  if (lra_dump_file != NULL)
+    {
+      fprintf (lra_dump_file, "	   Spilling non-eliminable hard regs:");
+      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+	if (TEST_HARD_REG_BIT (set, i))
+	  fprintf (lra_dump_file, " %d", i);
+      fprintf (lra_dump_file, "\n");
+    }
+  bitmap_initialize (&to_process, &reg_obstack);
+  for (i = FIRST_PSEUDO_REGISTER; i < max_reg_num (); i++)
+    if (lra_reg_info[i].nrefs != 0 && reg_renumber[i] >= 0
+	&& overlaps_hard_reg_set_p (set,
+				    PSEUDO_REGNO_MODE (i), reg_renumber[i]))
+      {
+	if (lra_dump_file != NULL)
+	  fprintf (lra_dump_file, "	 Spilling r%d(%d)\n",
+		   i, reg_renumber[i]);
+	reg_renumber[i] = -1;
+	bitmap_ior_into (&to_process, &lra_reg_info[i].insn_bitmap);
+      }
+  IOR_HARD_REG_SET (lra_no_alloc_regs, set);
+  for (insn = get_insns (); insn != NULL_RTX; insn = NEXT_INSN (insn))
+    if (bitmap_bit_p (&to_process, INSN_UID (insn)))
+      {
+	lra_push_insn (insn);
+	lra_set_used_insn_alternative (insn, -1);
+      }
+  bitmap_clear (&to_process);
+}
+
+/* Update all offsets and possibility for elimination on eliminable
+   registers.  Spill pseudos assigned to registers which became
+   uneliminable, update LRA_NO_ALLOC_REGS and ELIMINABLE_REG_SET.  Add
+   insns to INSNS_WITH_CHANGED_OFFSETS containing eliminable hard
+   registers whose offsets should be changed.  */
+static void
+update_reg_eliminate (bitmap insns_with_changed_offsets)
+{
+  bool prev;
+  struct elim_table *ep, *ep1;
+  HARD_REG_SET temp_hard_reg_set;
+
+  /* Clear self elimination offsets.  */
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    self_elim_offsets[ep->from] = 0;
+  CLEAR_HARD_REG_SET (temp_hard_reg_set);
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    {
+      /* If it is a currently used elimination: update the previous
+	 offset.  */
+      if (elimination_map[ep->from] == ep)
+	ep->previous_offset = ep->offset;
+
+      prev = ep->prev_can_eliminate;
+      setup_can_eliminate (ep, targetm.can_eliminate (ep->from, ep->to));
+      if (ep->can_eliminate && ! prev)
+	{
+	  /* It is possible that not eliminable register becomes
+	     eliminable because we took other reasons into account to
+	     set up eliminable regs in the initial set up.  Just
+	     ignore new eliminable registers.  */
+	  setup_can_eliminate (ep, false);
+	  continue;
+	}
+      if (ep->can_eliminate != prev && elimination_map[ep->from] == ep)
+	{
+	  /* We cannot use this elimination anymore -- find another
+	     one.  */
+	  if (lra_dump_file != NULL)
+	    fprintf (lra_dump_file,
+		     "	Elimination %d to %d is not possible anymore\n",
+		     ep->from, ep->to);
+	  /* Mark that is not eliminable anymore.  */
+	  elimination_map[ep->from] = NULL;
+	  for (ep1 = ep + 1; ep1 < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep1++)
+	    if (ep1->can_eliminate && ep1->from == ep->from)
+	      break;
+	  if (ep1 < &reg_eliminate[NUM_ELIMINABLE_REGS])
+	    {
+	      if (lra_dump_file != NULL)
+		fprintf (lra_dump_file, "    Using elimination %d to %d now\n",
+			 ep1->from, ep1->to);
+	      /* Prevent the hard register into which we eliminate now
+		 from the usage for pseudos.  */
+	      SET_HARD_REG_BIT (temp_hard_reg_set, ep1->to);
+	      lra_assert (ep1->previous_offset == 0);
+	      ep1->previous_offset = ep->offset;
+	    }
+	  else
+	    {
+	      /* There is no elimination anymore just use the hard
+		 register `from' itself.  Setup self elimination
+		 offset to restore the original offset values.	*/
+	      if (lra_dump_file != NULL)
+		fprintf (lra_dump_file, "    %d is not eliminable at all\n",
+			 ep->from);
+	      self_elim_offsets[ep->from] = -ep->offset;
+	      SET_HARD_REG_BIT (temp_hard_reg_set, ep->from);
+	      if (ep->offset != 0)
+		bitmap_ior_into (insns_with_changed_offsets,
+				 &lra_reg_info[ep->from].insn_bitmap);
+	    }
+	}
+
+#ifdef ELIMINABLE_REGS
+      INITIAL_ELIMINATION_OFFSET (ep->from, ep->to, ep->offset);
+#else
+      INITIAL_FRAME_POINTER_OFFSET (ep->offset);
+#endif
+    }
+  IOR_HARD_REG_SET (lra_no_alloc_regs, temp_hard_reg_set);
+  AND_COMPL_HARD_REG_SET (eliminable_regset, temp_hard_reg_set);
+  spill_pseudos (temp_hard_reg_set);
+  setup_elimination_map ();
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    if (elimination_map[ep->from] == ep && ep->previous_offset != ep->offset)
+      bitmap_ior_into (insns_with_changed_offsets,
+		       &lra_reg_info[ep->from].insn_bitmap);
+}
+
+/* Initialize the table of hard registers to eliminate.
+   Pre-condition: global flag frame_pointer_needed has been set before
+   calling this function.  */
+static void
+init_elim_table (void)
+{
+  bool value_p;
+  struct elim_table *ep;
+#ifdef ELIMINABLE_REGS
+  const struct elim_table_1 *ep1;
+#endif
+
+  if (!reg_eliminate)
+    reg_eliminate = XCNEWVEC (struct elim_table, NUM_ELIMINABLE_REGS);
+
+  memset (self_elim_offsets, 0, sizeof (self_elim_offsets));
+  /* Initiate member values which will be never changed.  */
+  self_elim_table.can_eliminate = self_elim_table.prev_can_eliminate = true;
+  self_elim_table.previous_offset = 0;
+#ifdef ELIMINABLE_REGS
+  for (ep = reg_eliminate, ep1 = reg_eliminate_1;
+       ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++, ep1++)
+    {
+      ep->offset = ep->previous_offset = 0;
+      ep->from = ep1->from;
+      ep->to = ep1->to;
+      value_p = (targetm.can_eliminate (ep->from, ep->to)
+		 && ! (ep->to == STACK_POINTER_REGNUM
+		       && frame_pointer_needed 
+		       && (! SUPPORTS_STACK_ALIGNMENT
+			   || ! stack_realign_fp)));
+      setup_can_eliminate (ep, value_p);
+    }
+#else
+  reg_eliminate[0].offset = reg_eliminate[0].previous_offset = 0;
+  reg_eliminate[0].from = reg_eliminate_1[0].from;
+  reg_eliminate[0].to = reg_eliminate_1[0].to;
+  setup_can_eliminate (&reg_eliminate[0], ! frame_pointer_needed);
+#endif
+
+  /* Count the number of eliminable registers and build the FROM and TO
+     REG rtx's.	 Note that code in gen_rtx_REG will cause, e.g.,
+     gen_rtx_REG (Pmode, STACK_POINTER_REGNUM) to equal stack_pointer_rtx.
+     We depend on this.	 */
+  for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+    {
+      ep->from_rtx = gen_rtx_REG (Pmode, ep->from);
+      ep->to_rtx = gen_rtx_REG (Pmode, ep->to);
+      eliminable_reg_rtx[ep->from] = ep->from_rtx;
+    }
+}
+
+/* Entry function for initialization of elimination once per
+   function.  */
+void
+lra_init_elimination (void)
+{
+  basic_block bb;
+  rtx insn;
+
+  init_elim_table ();
+  FOR_EACH_BB (bb)
+    FOR_BB_INSNS (bb, insn)
+    if (NONDEBUG_INSN_P (insn))
+      mark_not_eliminable (PATTERN (insn));
+  setup_elimination_map ();
+}
+
+/* Eliminate hard reg given by its location LOC.  */
+void
+lra_eliminate_reg_if_possible (rtx *loc)
+{
+  int regno;
+  struct elim_table *ep;
+
+  lra_assert (REG_P (*loc));
+  if ((regno = REGNO (*loc)) >= FIRST_PSEUDO_REGISTER
+      || ! TEST_HARD_REG_BIT (lra_no_alloc_regs, regno))
+    return;
+  if ((ep = get_elimination (*loc)) != NULL)
+    *loc = ep->to_rtx;
+}
+
+/* Do (final if FINAL_P) elimination in INSN.  Add the insn for
+   subsequent processing in the constraint pass, update the insn info.	*/
+static void
+process_insn_for_elimination (rtx insn, bool final_p)
+{
+  eliminate_regs_in_insn (insn, final_p);
+  if (! final_p)
+    {
+      /* Check that insn changed its code.  This is a case when a move
+	 insn becomes an add insn and we do not want to process the
+	 insn as a move anymore.  */
+      int icode = recog (PATTERN (insn), insn, 0);
+
+      if (icode >= 0 && icode != INSN_CODE (insn))
+	{
+	  INSN_CODE (insn) = icode;
+	  lra_update_insn_recog_data (insn);
+	}
+      lra_update_insn_regno_info (insn);
+      lra_push_insn (insn);
+      lra_set_used_insn_alternative (insn, -1);
+    }
+}
+
+/* Entry function to do final elimination if FINAL_P or to update
+   elimination register offsets.  */
+void
+lra_eliminate (bool final_p)
+{
+  int i;
+  unsigned int uid;
+  rtx mem_loc, invariant;
+  bitmap_head insns_with_changed_offsets;
+  bitmap_iterator bi;
+  struct elim_table *ep;
+  int regs_num = max_reg_num ();
+
+  timevar_push (TV_LRA_ELIMINATE);
+
+  bitmap_initialize (&insns_with_changed_offsets, &reg_obstack);
+  if (final_p)
+    {
+#ifdef ENABLE_CHECKING
+      update_reg_eliminate (&insns_with_changed_offsets);
+      if (! bitmap_empty_p (&insns_with_changed_offsets))
+	gcc_unreachable ();
+#endif
+      /* We change eliminable hard registers in insns so we should do
+	 this for all insns containing any eliminable hard
+	 register.  */
+      for (ep = reg_eliminate; ep < &reg_eliminate[NUM_ELIMINABLE_REGS]; ep++)
+	if (elimination_map[ep->from] != NULL)
+	  bitmap_ior_into (&insns_with_changed_offsets,
+			   &lra_reg_info[ep->from].insn_bitmap);
+    }
+  else
+    {
+      update_reg_eliminate (&insns_with_changed_offsets);
+      if (bitmap_empty_p (&insns_with_changed_offsets))
+	goto lra_eliminate_done;
+    }
+  if (lra_dump_file != NULL)
+    {
+      fprintf (lra_dump_file, "New elimination table:\n");
+      print_elim_table (lra_dump_file);
+    }
+  for (i = FIRST_PSEUDO_REGISTER; i < regs_num; i++)
+    if (lra_reg_info[i].nrefs != 0)
+      {
+	mem_loc = ira_reg_equiv[i].memory;
+	if (mem_loc != NULL_RTX)
+	  mem_loc = lra_eliminate_regs_1 (mem_loc, VOIDmode,
+					  final_p, ! final_p, false);
+	ira_reg_equiv[i].memory = mem_loc;
+	invariant = ira_reg_equiv[i].invariant;
+	if (invariant != NULL_RTX)
+	  invariant = lra_eliminate_regs_1 (invariant, VOIDmode,
+					    final_p, ! final_p, false);
+	ira_reg_equiv[i].invariant = invariant;
+	if (lra_dump_file != NULL
+	    && (mem_loc != NULL_RTX || invariant != NULL))
+	  fprintf (lra_dump_file,
+		   "Updating elimination of equiv for reg %d\n", i);
+      }
+  EXECUTE_IF_SET_IN_BITMAP (&insns_with_changed_offsets, 0, uid, bi)
+    process_insn_for_elimination (lra_insn_recog_data[uid]->insn, final_p);
+  bitmap_clear (&insns_with_changed_offsets);
+
+lra_eliminate_done:
+  timevar_pop (TV_LRA_ELIMINATE);
+}