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: https://gcc.gnu.org/svn/gcc/trunk@192719 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 429 insertions, 155 deletions

diff --git a/gcc/ira.c b/gcc/ira.c
index 78b3f92db00..e91d37ddaa5 100644
--- a/gcc/ira.c
+++ b/gcc/ira.c
@@ -382,6 +382,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "function.h"
 #include "ggc.h"
 #include "ira-int.h"
+#include "lra.h"
 #include "dce.h"
 #include "dbgcnt.h"
 
@@ -1201,6 +1202,7 @@ setup_reg_class_relations (void)
 	{
 	  ira_reg_classes_intersect_p[cl1][cl2] = false;
 	  ira_reg_class_intersect[cl1][cl2] = NO_REGS;
+	  ira_reg_class_subset[cl1][cl2] = NO_REGS;
 	  COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl1]);
 	  AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 	  COPY_HARD_REG_SET (temp_set2, reg_class_contents[cl2]);
@@ -1248,9 +1250,8 @@ setup_reg_class_relations (void)
 	  COPY_HARD_REG_SET (union_set, reg_class_contents[cl1]);
 	  IOR_HARD_REG_SET (union_set, reg_class_contents[cl2]);
 	  AND_COMPL_HARD_REG_SET (union_set, no_unit_alloc_regs);
-	  for (i = 0; i < ira_important_classes_num; i++)
+	  for (cl3 = 0; cl3 < N_REG_CLASSES; cl3++)
 	    {
-	      cl3 = ira_important_classes[i];
 	      COPY_HARD_REG_SET (temp_hard_regset, reg_class_contents[cl3]);
 	      AND_COMPL_HARD_REG_SET (temp_hard_regset, no_unit_alloc_regs);
 	      if (hard_reg_set_subset_p (temp_hard_regset, intersection_set))
@@ -1258,25 +1259,45 @@ setup_reg_class_relations (void)
 		  /* CL3 allocatable hard register set is inside of
 		     intersection of allocatable hard register sets
 		     of CL1 and CL2.  */
+		  if (important_class_p[cl3])
+		    {
+		      COPY_HARD_REG_SET
+			(temp_set2,
+			 reg_class_contents
+			 [(int) ira_reg_class_intersect[cl1][cl2]]);
+		      AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
+		      if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
+			  /* If the allocatable hard register sets are
+			     the same, prefer GENERAL_REGS or the
+			     smallest class for debugging
+			     purposes.  */
+			  || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
+			      && (cl3 == GENERAL_REGS
+				  || ((ira_reg_class_intersect[cl1][cl2]
+				       != GENERAL_REGS)
+				      && hard_reg_set_subset_p
+				         (reg_class_contents[cl3],
+					  reg_class_contents
+					  [(int)
+					   ira_reg_class_intersect[cl1][cl2]])))))
+			ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
+		    }
 		  COPY_HARD_REG_SET
 		    (temp_set2,
-		     reg_class_contents[(int)
-					ira_reg_class_intersect[cl1][cl2]]);
+		     reg_class_contents[(int) ira_reg_class_subset[cl1][cl2]]);
 		  AND_COMPL_HARD_REG_SET (temp_set2, no_unit_alloc_regs);
-	 	  if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
-		      /* If the allocatable hard register sets are the
-			 same, prefer GENERAL_REGS or the smallest
-			 class for debugging purposes.  */
+		  if (! hard_reg_set_subset_p (temp_hard_regset, temp_set2)
+		      /* Ignore unavailable hard registers and prefer
+			 smallest class for debugging purposes.  */
 		      || (hard_reg_set_equal_p (temp_hard_regset, temp_set2)
-			  && (cl3 == GENERAL_REGS
-			      || (ira_reg_class_intersect[cl1][cl2] != GENERAL_REGS
-				  && hard_reg_set_subset_p
-				     (reg_class_contents[cl3],
-				      reg_class_contents
-				      [(int) ira_reg_class_intersect[cl1][cl2]])))))
-		    ira_reg_class_intersect[cl1][cl2] = (enum reg_class) cl3;
+			  && hard_reg_set_subset_p
+			     (reg_class_contents[cl3],
+			      reg_class_contents
+			      [(int) ira_reg_class_subset[cl1][cl2]])))
+		    ira_reg_class_subset[cl1][cl2] = (enum reg_class) cl3;
 		}
-	      if (hard_reg_set_subset_p (temp_hard_regset, union_set))
+	      if (important_class_p[cl3]
+		  && hard_reg_set_subset_p (temp_hard_regset, union_set))
 		{
 		  /* CL3 allocatbale hard register set is inside of
 		     union of allocatable hard register sets of CL1
@@ -1632,6 +1653,7 @@ void
 ira_init_once (void)
 {
   ira_init_costs_once ();
+  lra_init_once ();
 }
 
 /* Free ira_max_register_move_cost, ira_may_move_in_cost and
@@ -1679,6 +1701,7 @@ ira_init (void)
   clarify_prohibited_class_mode_regs ();
   setup_hard_regno_aclass ();
   ira_init_costs ();
+  lra_init ();
 }
 
 /* Function called once at the end of compiler work.  */
@@ -1687,6 +1710,7 @@ ira_finish_once (void)
 {
   ira_finish_costs_once ();
   free_register_move_costs ();
+  lra_finish_once ();
 }
 
 
@@ -1823,9 +1847,11 @@ compute_regs_asm_clobbered (void)
 }
 
 
-/* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.  */
+/* Set up ELIMINABLE_REGSET, IRA_NO_ALLOC_REGS, and REGS_EVER_LIVE.
+   If the function is called from IRA (not from the insn scheduler or
+   RTL loop invariant motion), FROM_IRA_P is true.  */
 void
-ira_setup_eliminable_regset (void)
+ira_setup_eliminable_regset (bool from_ira_p)
 {
 #ifdef ELIMINABLE_REGS
   int i;
@@ -1835,7 +1861,7 @@ ira_setup_eliminable_regset (void)
      sp for alloca.  So we can't eliminate the frame pointer in that
      case.  At some point, we should improve this by emitting the
      sp-adjusting insns for this case.  */
-  int need_fp
+  frame_pointer_needed
     = (! flag_omit_frame_pointer
        || (cfun->calls_alloca && EXIT_IGNORE_STACK)
        /* We need the frame pointer to catch stack overflow exceptions
@@ -1845,8 +1871,14 @@ ira_setup_eliminable_regset (void)
        || crtl->stack_realign_needed
        || targetm.frame_pointer_required ());
 
-  frame_pointer_needed = need_fp;
+  if (from_ira_p && ira_use_lra_p)
+    /* It can change FRAME_POINTER_NEEDED.  We call it only from IRA
+       because it is expensive.  */
+    lra_init_elimination ();
 
+  if (frame_pointer_needed)
+    df_set_regs_ever_live (HARD_FRAME_POINTER_REGNUM, true);
+    
   COPY_HARD_REG_SET (ira_no_alloc_regs, no_unit_alloc_regs);
   CLEAR_HARD_REG_SET (eliminable_regset);
 
@@ -1859,7 +1891,7 @@ ira_setup_eliminable_regset (void)
     {
       bool cannot_elim
 	= (! targetm.can_eliminate (eliminables[i].from, eliminables[i].to)
-	   || (eliminables[i].to == STACK_POINTER_REGNUM && need_fp));
+	   || (eliminables[i].to == STACK_POINTER_REGNUM && frame_pointer_needed));
 
       if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, eliminables[i].from))
 	{
@@ -1878,10 +1910,10 @@ ira_setup_eliminable_regset (void)
   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
     {
       SET_HARD_REG_BIT (eliminable_regset, HARD_FRAME_POINTER_REGNUM);
-      if (need_fp)
+      if (frame_pointer_needed)
 	SET_HARD_REG_BIT (ira_no_alloc_regs, HARD_FRAME_POINTER_REGNUM);
     }
-  else if (need_fp)
+  else if (frame_pointer_needed)
     error ("%s cannot be used in asm here",
 	   reg_names[HARD_FRAME_POINTER_REGNUM]);
   else
@@ -1892,10 +1924,10 @@ ira_setup_eliminable_regset (void)
   if (!TEST_HARD_REG_BIT (crtl->asm_clobbers, HARD_FRAME_POINTER_REGNUM))
     {
       SET_HARD_REG_BIT (eliminable_regset, FRAME_POINTER_REGNUM);
-      if (need_fp)
+      if (frame_pointer_needed)
 	SET_HARD_REG_BIT (ira_no_alloc_regs, FRAME_POINTER_REGNUM);
     }
-  else if (need_fp)
+  else if (frame_pointer_needed)
     error ("%s cannot be used in asm here", reg_names[FRAME_POINTER_REGNUM]);
   else
     df_set_regs_ever_live (FRAME_POINTER_REGNUM, true);
@@ -1904,66 +1936,6 @@ ira_setup_eliminable_regset (void)
 
 
 
-/* The length of the following two arrays.  */
-int ira_reg_equiv_len;
-
-/* The element value is TRUE if the corresponding regno value is
-   invariant.  */
-bool *ira_reg_equiv_invariant_p;
-
-/* The element value is equiv constant of given pseudo-register or
-   NULL_RTX.  */
-rtx *ira_reg_equiv_const;
-
-/* Set up the two arrays declared above.  */
-static void
-find_reg_equiv_invariant_const (void)
-{
-  unsigned int i;
-  bool invariant_p;
-  rtx list, insn, note, constant, x;
-
-  for (i = FIRST_PSEUDO_REGISTER; i < VEC_length (reg_equivs_t, reg_equivs); i++)
-    {
-      constant = NULL_RTX;
-      invariant_p = false;
-      for (list = reg_equiv_init (i); list != NULL_RTX; list = XEXP (list, 1))
-	{
-	  insn = XEXP (list, 0);
-	  note = find_reg_note (insn, REG_EQUIV, NULL_RTX);
-
-	  if (note == NULL_RTX)
-	    continue;
-
-	  x = XEXP (note, 0);
-
-	  if (! CONSTANT_P (x)
-	      || ! flag_pic || LEGITIMATE_PIC_OPERAND_P (x))
-	    {
-	      /* It can happen that a REG_EQUIV note contains a MEM
-		 that is not a legitimate memory operand.  As later
-		 stages of the reload assume that all addresses found
-		 in the reg_equiv_* arrays were originally legitimate,
-		 we ignore such REG_EQUIV notes.  */
-	      if (memory_operand (x, VOIDmode))
-		invariant_p = MEM_READONLY_P (x);
-	      else if (function_invariant_p (x))
-		{
-		  if (GET_CODE (x) == PLUS
-		      || x == frame_pointer_rtx || x == arg_pointer_rtx)
-		    invariant_p = true;
-		  else
-		    constant = x;
-		}
-	    }
-	}
-      ira_reg_equiv_invariant_p[i] = invariant_p;
-      ira_reg_equiv_const[i] = constant;
-    }
-}
-
-
-
 /* Vector of substitutions of register numbers,
    used to map pseudo regs into hardware regs.
    This is set up as a result of register allocation.
@@ -1984,6 +1956,8 @@ setup_reg_renumber (void)
   caller_save_needed = 0;
   FOR_EACH_ALLOCNO (a, ai)
     {
+      if (ira_use_lra_p && ALLOCNO_CAP_MEMBER (a) != NULL)
+	continue;
       /* There are no caps at this point.  */
       ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
       if (! ALLOCNO_ASSIGNED_P (a))
@@ -2015,9 +1989,7 @@ setup_reg_renumber (void)
 	      ira_assert (!optimize || flag_caller_saves
 			  || (ALLOCNO_CALLS_CROSSED_NUM (a)
 			      == ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a))
-			  || regno >= ira_reg_equiv_len
-			  || ira_reg_equiv_const[regno]
-			  || ira_reg_equiv_invariant_p[regno]);
+			  || ira_equiv_no_lvalue_p (regno));
 	      caller_save_needed = 1;
 	    }
 	}
@@ -2184,6 +2156,109 @@ check_allocation (void)
 }
 #endif
 
+/* Allocate REG_EQUIV_INIT.  Set up it from IRA_REG_EQUIV which should
+   be already calculated.  */
+static void
+setup_reg_equiv_init (void)
+{
+  int i;
+  int max_regno = max_reg_num ();
+
+  for (i = 0; i < max_regno; i++)
+    reg_equiv_init (i) = ira_reg_equiv[i].init_insns;
+}
+
+/* Update equiv regno from movement of FROM_REGNO to TO_REGNO.  INSNS
+   are insns which were generated for such movement.  It is assumed
+   that FROM_REGNO and TO_REGNO always have the same value at the
+   point of any move containing such registers. This function is used
+   to update equiv info for register shuffles on the region borders
+   and for caller save/restore insns.  */
+void
+ira_update_equiv_info_by_shuffle_insn (int to_regno, int from_regno, rtx insns)
+{
+  rtx insn, x, note;
+
+  if (! ira_reg_equiv[from_regno].defined_p
+      && (! ira_reg_equiv[to_regno].defined_p
+	  || ((x = ira_reg_equiv[to_regno].memory) != NULL_RTX
+	      && ! MEM_READONLY_P (x))))
+      return;
+  insn = insns;
+  if (NEXT_INSN (insn) != NULL_RTX)
+    {
+      if (! ira_reg_equiv[to_regno].defined_p)
+	{
+	  ira_assert (ira_reg_equiv[to_regno].init_insns == NULL_RTX);
+	  return;
+	}
+      ira_reg_equiv[to_regno].defined_p = false;
+      ira_reg_equiv[to_regno].memory
+	= ira_reg_equiv[to_regno].constant
+	= ira_reg_equiv[to_regno].invariant
+	= ira_reg_equiv[to_regno].init_insns = NULL_RTX;
+      if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+	fprintf (ira_dump_file,
+		 "      Invalidating equiv info for reg %d\n", to_regno);
+      return;
+    }
+  /* It is possible that FROM_REGNO still has no equivalence because
+     in shuffles to_regno<-from_regno and from_regno<-to_regno the 2nd
+     insn was not processed yet.  */
+  if (ira_reg_equiv[from_regno].defined_p)
+    {
+      ira_reg_equiv[to_regno].defined_p = true;
+      if ((x = ira_reg_equiv[from_regno].memory) != NULL_RTX)
+	{
+	  ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX
+		      && ira_reg_equiv[from_regno].constant == NULL_RTX);
+	  ira_assert (ira_reg_equiv[to_regno].memory == NULL_RTX
+		      || rtx_equal_p (ira_reg_equiv[to_regno].memory, x));
+	  ira_reg_equiv[to_regno].memory = x;
+	  if (! MEM_READONLY_P (x))
+	    /* We don't add the insn to insn init list because memory
+	       equivalence is just to say what memory is better to use
+	       when the pseudo is spilled.  */
+	    return;
+	}
+      else if ((x = ira_reg_equiv[from_regno].constant) != NULL_RTX)
+	{
+	  ira_assert (ira_reg_equiv[from_regno].invariant == NULL_RTX);
+	  ira_assert (ira_reg_equiv[to_regno].constant == NULL_RTX
+		      || rtx_equal_p (ira_reg_equiv[to_regno].constant, x));
+	  ira_reg_equiv[to_regno].constant = x;
+	}
+      else
+	{
+	  x = ira_reg_equiv[from_regno].invariant;
+	  ira_assert (x != NULL_RTX);
+	  ira_assert (ira_reg_equiv[to_regno].invariant == NULL_RTX
+		      || rtx_equal_p (ira_reg_equiv[to_regno].invariant, x));
+	  ira_reg_equiv[to_regno].invariant = x;
+	}
+      if (find_reg_note (insn, REG_EQUIV, x) == NULL_RTX)
+	{
+	  note = set_unique_reg_note (insn, REG_EQUIV, x);
+	  gcc_assert (note != NULL_RTX);
+	  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+	    {
+	      fprintf (ira_dump_file,
+		       "      Adding equiv note to insn %u for reg %d ",
+		       INSN_UID (insn), to_regno);
+	      print_value_slim (ira_dump_file, x, 1);
+	      fprintf (ira_dump_file, "\n");
+	    }
+	}
+    }
+  ira_reg_equiv[to_regno].init_insns
+    = gen_rtx_INSN_LIST (VOIDmode, insn,
+			 ira_reg_equiv[to_regno].init_insns);
+  if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
+    fprintf (ira_dump_file,
+	     "      Adding equiv init move insn %u to reg %d\n",
+	     INSN_UID (insn), to_regno);
+}
+
 /* Fix values of array REG_EQUIV_INIT after live range splitting done
    by IRA.  */
 static void
@@ -2221,6 +2296,7 @@ fix_reg_equiv_init (void)
 	      prev = x;
 	    else
 	      {
+		/* Remove the wrong list element.  */
 		if (prev == NULL_RTX)
 		  reg_equiv_init (i) = next;
 		else
@@ -2360,6 +2436,46 @@ mark_elimination (int from, int to)
 
 
 
+/* The length of the following array.  */
+int ira_reg_equiv_len;
+
+/* Info about equiv. info for each register.  */
+struct ira_reg_equiv *ira_reg_equiv;
+
+/* Expand ira_reg_equiv if necessary.  */
+void
+ira_expand_reg_equiv (void)
+{
+  int old = ira_reg_equiv_len;
+
+  if (ira_reg_equiv_len > max_reg_num ())
+    return;
+  ira_reg_equiv_len = max_reg_num () * 3 / 2 + 1;
+  ira_reg_equiv
+    = (struct ira_reg_equiv *) xrealloc (ira_reg_equiv,
+					 ira_reg_equiv_len
+					 * sizeof (struct ira_reg_equiv));
+  gcc_assert (old < ira_reg_equiv_len);
+  memset (ira_reg_equiv + old, 0,
+	  sizeof (struct ira_reg_equiv) * (ira_reg_equiv_len - old));
+}
+
+static void
+init_reg_equiv (void)
+{
+  ira_reg_equiv_len = 0;
+  ira_reg_equiv = NULL;
+  ira_expand_reg_equiv ();
+}
+
+static void
+finish_reg_equiv (void)
+{
+  free (ira_reg_equiv);
+}
+
+
+
 struct equivalence
 {
   /* Set when a REG_EQUIV note is found or created.  Use to
@@ -2733,7 +2849,8 @@ no_equiv (rtx reg, const_rtx store ATTRIBUTE_UNUSED,
      should keep their initialization insns.  */
   if (reg_equiv[regno].is_arg_equivalence)
     return;
-  reg_equiv_init (regno) = NULL_RTX;
+  ira_reg_equiv[regno].defined_p = false;
+  ira_reg_equiv[regno].init_insns = NULL_RTX;
   for (; list; list =  XEXP (list, 1))
     {
       rtx insn = XEXP (list, 0);
@@ -2769,7 +2886,7 @@ static int recorded_label_ref;
    value into the using insn.  If it succeeds, we can eliminate the
    register completely.
 
-   Initialize the REG_EQUIV_INIT array of initializing insns.
+   Initialize init_insns in ira_reg_equiv array.
 
    Return non-zero if jump label rebuilding should be done.  */
 static int
@@ -2844,14 +2961,16 @@ update_equiv_regs (void)
 	      gcc_assert (REG_P (dest));
 	      regno = REGNO (dest);
 
-	      /* Note that we don't want to clear reg_equiv_init even if there
-		 are multiple sets of this register.  */
+	      /* Note that we don't want to clear init_insns in
+		 ira_reg_equiv even if there are multiple sets of this
+		 register.  */
 	      reg_equiv[regno].is_arg_equivalence = 1;
 
 	      /* Record for reload that this is an equivalencing insn.  */
 	      if (rtx_equal_p (src, XEXP (note, 0)))
-		reg_equiv_init (regno)
-		  = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
+		ira_reg_equiv[regno].init_insns
+		  = gen_rtx_INSN_LIST (VOIDmode, insn,
+				       ira_reg_equiv[regno].init_insns);
 
 	      /* Continue normally in case this is a candidate for
 		 replacements.  */
@@ -2951,8 +3070,9 @@ update_equiv_regs (void)
 	      /* If we haven't done so, record for reload that this is an
 		 equivalencing insn.  */
 	      if (!reg_equiv[regno].is_arg_equivalence)
-		reg_equiv_init (regno)
-		  = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
+		ira_reg_equiv[regno].init_insns
+		  = gen_rtx_INSN_LIST (VOIDmode, insn,
+				       ira_reg_equiv[regno].init_insns);
 
 	      /* Record whether or not we created a REG_EQUIV note for a LABEL_REF.
 		 We might end up substituting the LABEL_REF for uses of the
@@ -3052,7 +3172,7 @@ update_equiv_regs (void)
 	    {
 	      /* This insn makes the equivalence, not the one initializing
 		 the register.  */
-	      reg_equiv_init (regno)
+	      ira_reg_equiv[regno].init_insns
 		= gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX);
 	      df_notes_rescan (init_insn);
 	    }
@@ -3106,9 +3226,10 @@ update_equiv_regs (void)
 
 		  /* reg_equiv[REGNO].replace gets set only when
 		     REG_N_REFS[REGNO] is 2, i.e. the register is set
-		     once and used once.  (If it were only set, but not used,
-		     flow would have deleted the setting insns.)  Hence
-		     there can only be one insn in reg_equiv[REGNO].init_insns.  */
+		     once and used once.  (If it were only set, but
+		     not used, flow would have deleted the setting
+		     insns.)  Hence there can only be one insn in
+		     reg_equiv[REGNO].init_insns.  */
 		  gcc_assert (reg_equiv[regno].init_insns
 			      && !XEXP (reg_equiv[regno].init_insns, 1));
 		  equiv_insn = XEXP (reg_equiv[regno].init_insns, 0);
@@ -3155,7 +3276,7 @@ update_equiv_regs (void)
 		      reg_equiv[regno].init_insns
 			= XEXP (reg_equiv[regno].init_insns, 1);
 
-		      reg_equiv_init (regno) = NULL_RTX;
+		      ira_reg_equiv[regno].init_insns = NULL_RTX;
 		      bitmap_set_bit (cleared_regs, regno);
 		    }
 		  /* Move the initialization of the register to just before
@@ -3188,7 +3309,7 @@ update_equiv_regs (void)
 		      if (insn == BB_HEAD (bb))
 			BB_HEAD (bb) = PREV_INSN (insn);
 
-		      reg_equiv_init (regno)
+		      ira_reg_equiv[regno].init_insns
 			= gen_rtx_INSN_LIST (VOIDmode, new_insn, NULL_RTX);
 		      bitmap_set_bit (cleared_regs, regno);
 		    }
@@ -3236,6 +3357,88 @@ update_equiv_regs (void)
 
 
 
+/* Set up fields memory, constant, and invariant from init_insns in
+   the structures of array ira_reg_equiv.  */
+static void
+setup_reg_equiv (void)
+{
+  int i;
+  rtx elem, insn, set, x;
+
+  for (i = FIRST_PSEUDO_REGISTER; i < ira_reg_equiv_len; i++)
+    for (elem = ira_reg_equiv[i].init_insns; elem; elem = XEXP (elem, 1))
+      {
+	insn = XEXP (elem, 0);
+	set = single_set (insn);
+	
+	/* Init insns can set up equivalence when the reg is a destination or
+	   a source (in this case the destination is memory).  */
+	if (set != 0 && (REG_P (SET_DEST (set)) || REG_P (SET_SRC (set))))
+	  {
+	    if ((x = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != NULL)
+	      x = XEXP (x, 0);
+	    else if (REG_P (SET_DEST (set))
+		     && REGNO (SET_DEST (set)) == (unsigned int) i)
+	      x = SET_SRC (set);
+	    else
+	      {      
+		gcc_assert (REG_P (SET_SRC (set))
+			    && REGNO (SET_SRC (set)) == (unsigned int) i);
+		x = SET_DEST (set);
+	      }
+	    if (! function_invariant_p (x)
+		|| ! flag_pic
+		/* A function invariant is often CONSTANT_P but may
+		   include a register.  We promise to only pass
+		   CONSTANT_P objects to LEGITIMATE_PIC_OPERAND_P.  */
+		|| (CONSTANT_P (x) && LEGITIMATE_PIC_OPERAND_P (x)))
+	      {
+		/* It can happen that a REG_EQUIV note contains a MEM
+		   that is not a legitimate memory operand.  As later
+		   stages of reload assume that all addresses found in
+		   the lra_regno_equiv_* arrays were originally
+		   legitimate, we ignore such REG_EQUIV notes.  */
+		if (memory_operand (x, VOIDmode))
+		  {
+		    ira_reg_equiv[i].defined_p = true;
+		    ira_reg_equiv[i].memory = x;
+		    continue;
+		  }
+		else if (function_invariant_p (x))
+		  {
+		    enum machine_mode mode;
+		    
+		    mode = GET_MODE (SET_DEST (set));
+		    if (GET_CODE (x) == PLUS
+			|| x == frame_pointer_rtx || x == arg_pointer_rtx)
+		      /* This is PLUS of frame pointer and a constant,
+			 or fp, or argp.  */
+		      ira_reg_equiv[i].invariant = x;
+		    else if (targetm.legitimate_constant_p (mode, x))
+		      ira_reg_equiv[i].constant = x;
+		    else
+		      {
+			ira_reg_equiv[i].memory = force_const_mem (mode, x);
+			if (ira_reg_equiv[i].memory == NULL_RTX)
+			  {
+			    ira_reg_equiv[i].defined_p = false;
+			    ira_reg_equiv[i].init_insns = NULL_RTX;
+			    break;
+			  }
+		      }
+		    ira_reg_equiv[i].defined_p = true;
+		    continue;
+		  }
+	      }
+	  }
+	ira_reg_equiv[i].defined_p = false;
+	ira_reg_equiv[i].init_insns = NULL_RTX;
+	break;
+      }
+}
+
+
+
 /* Print chain C to FILE.  */
 static void
 print_insn_chain (FILE *file, struct insn_chain *c)
@@ -4130,6 +4333,11 @@ allocate_initial_values (void)
     }
 }
 
+
+/* True when we use LRA instead of reload pass for the current
+   function.  */
+bool ira_use_lra_p;
+
 /* All natural loops.  */
 struct loops ira_loops;
 
@@ -4147,6 +4355,31 @@ ira (FILE *f)
   bool loops_p;
   int max_regno_before_ira, ira_max_point_before_emit;
   int rebuild_p;
+  bool saved_flag_caller_saves = flag_caller_saves;
+  enum ira_region saved_flag_ira_region = flag_ira_region;
+
+  ira_conflicts_p = optimize > 0;
+
+  ira_use_lra_p = targetm.lra_p ();
+  /* If there are too many pseudos and/or basic blocks (e.g. 10K
+     pseudos and 10K blocks or 100K pseudos and 1K blocks), we will
+     use simplified and faster algorithms in LRA.  */
+  lra_simple_p
+    = (ira_use_lra_p && max_reg_num () >= (1 << 26) / last_basic_block);
+  if (lra_simple_p)
+    {
+      /* It permits to skip live range splitting in LRA.  */
+      flag_caller_saves = false;
+      /* There is no sense to do regional allocation when we use
+	 simplified LRA.  */
+      flag_ira_region = IRA_REGION_ONE;
+      ira_conflicts_p = false;
+    }
+
+#ifndef IRA_NO_OBSTACK
+  gcc_obstack_init (&ira_obstack);
+#endif
+  bitmap_obstack_initialize (&ira_bitmap_obstack);
 
   if (flag_caller_saves)
     init_caller_save ();
@@ -4162,7 +4395,6 @@ ira (FILE *f)
       ira_dump_file = stderr;
     }
 
-  ira_conflicts_p = optimize > 0;
   setup_prohibited_mode_move_regs ();
 
   df_note_add_problem ();
@@ -4188,30 +4420,18 @@ ira (FILE *f)
   if (resize_reg_info () && flag_ira_loop_pressure)
     ira_set_pseudo_classes (true, ira_dump_file);
 
+  init_reg_equiv ();
   rebuild_p = update_equiv_regs ();
+  setup_reg_equiv ();
+  setup_reg_equiv_init ();
 
-#ifndef IRA_NO_OBSTACK
-  gcc_obstack_init (&ira_obstack);
-#endif
-  bitmap_obstack_initialize (&ira_bitmap_obstack);
-  if (optimize)
+  if (optimize && rebuild_p)
     {
-      max_regno = max_reg_num ();
-      ira_reg_equiv_len = max_regno;
-      ira_reg_equiv_invariant_p
-	= (bool *) ira_allocate (max_regno * sizeof (bool));
-      memset (ira_reg_equiv_invariant_p, 0, max_regno * sizeof (bool));
-      ira_reg_equiv_const = (rtx *) ira_allocate (max_regno * sizeof (rtx));
-      memset (ira_reg_equiv_const, 0, max_regno * sizeof (rtx));
-      find_reg_equiv_invariant_const ();
-      if (rebuild_p)
-	{
-	  timevar_push (TV_JUMP);
-	  rebuild_jump_labels (get_insns ());
-	  if (purge_all_dead_edges ())
-	    delete_unreachable_blocks ();
-	  timevar_pop (TV_JUMP);
-	}
+      timevar_push (TV_JUMP);
+      rebuild_jump_labels (get_insns ());
+      if (purge_all_dead_edges ())
+	delete_unreachable_blocks ();
+      timevar_pop (TV_JUMP);
     }
 
   allocated_reg_info_size = max_reg_num ();
@@ -4226,7 +4446,7 @@ ira (FILE *f)
     find_moveable_pseudos ();
 
   max_regno_before_ira = max_reg_num ();
-  ira_setup_eliminable_regset ();
+  ira_setup_eliminable_regset (true);
 
   ira_overall_cost = ira_reg_cost = ira_mem_cost = 0;
   ira_load_cost = ira_store_cost = ira_shuffle_cost = 0;
@@ -4263,19 +4483,32 @@ ira (FILE *f)
 
   ira_emit (loops_p);
 
+  max_regno = max_reg_num ();
   if (ira_conflicts_p)
     {
-      max_regno = max_reg_num ();
-
       if (! loops_p)
-	ira_initiate_assign ();
+	{
+	  if (! ira_use_lra_p)
+	    ira_initiate_assign ();
+	}
       else
 	{
 	  expand_reg_info ();
 
-	  if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
-	    fprintf (ira_dump_file, "Flattening IR\n");
-	  ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
+	  if (ira_use_lra_p)
+	    {
+	      ira_allocno_t a;
+	      ira_allocno_iterator ai;
+
+	      FOR_EACH_ALLOCNO (a, ai)
+		ALLOCNO_REGNO (a) = REGNO (ALLOCNO_EMIT_DATA (a)->reg);
+	    }
+	  else
+	    {
+	      if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
+		fprintf (ira_dump_file, "Flattening IR\n");
+	      ira_flattening (max_regno_before_ira, ira_max_point_before_emit);
+	    }
 	  /* New insns were generated: add notes and recalculate live
 	     info.  */
 	  df_analyze ();
@@ -4289,9 +4522,12 @@ ira (FILE *f)
 	  current_loops = &ira_loops;
 	  record_loop_exits ();
 
-	  setup_allocno_assignment_flags ();
-	  ira_initiate_assign ();
-	  ira_reassign_conflict_allocnos (max_regno);
+	  if (! ira_use_lra_p)
+	    {
+	      setup_allocno_assignment_flags ();
+	      ira_initiate_assign ();
+	      ira_reassign_conflict_allocnos (max_regno);
+	    }
 	}
     }
 
@@ -4338,6 +4574,13 @@ ira (FILE *f)
   /* See comment for find_moveable_pseudos call.  */
   if (ira_conflicts_p)
     move_unallocated_pseudos ();
+
+  /* Restore original values.  */
+  if (lra_simple_p)
+    {
+      flag_caller_saves = saved_flag_caller_saves;
+      flag_ira_region = saved_flag_ira_region;
+    }
 }
 
 static void
@@ -4349,46 +4592,77 @@ do_reload (void)
   if (flag_ira_verbose < 10)
     ira_dump_file = dump_file;
 
-  df_set_flags (DF_NO_INSN_RESCAN);
-  build_insn_chain ();
+  timevar_push (TV_RELOAD);
+  if (ira_use_lra_p)
+    {
+      if (current_loops != NULL)
+	{
+	  release_recorded_exits ();
+	  flow_loops_free (&ira_loops);
+	  free_dominance_info (CDI_DOMINATORS);
+	}
+      FOR_ALL_BB (bb)
+	bb->loop_father = NULL;
+      current_loops = NULL;
+      
+      if (ira_conflicts_p)
+	ira_free (ira_spilled_reg_stack_slots);
+
+      ira_destroy ();
 
-  need_dce = reload (get_insns (), ira_conflicts_p);
+      lra (ira_dump_file);
+      /* ???!!! Move it before lra () when we use ira_reg_equiv in
+	 LRA.  */
+      VEC_free (reg_equivs_t, gc, reg_equivs);
+      reg_equivs = NULL;
+      need_dce = false;
+    }
+  else
+    {
+      df_set_flags (DF_NO_INSN_RESCAN);
+      build_insn_chain ();
+      
+      need_dce = reload (get_insns (), ira_conflicts_p);
+
+    }
+
+  timevar_pop (TV_RELOAD);
 
   timevar_push (TV_IRA);
 
-  if (ira_conflicts_p)
+  if (ira_conflicts_p && ! ira_use_lra_p)
     {
       ira_free (ira_spilled_reg_stack_slots);
-
       ira_finish_assign ();
     }
+
   if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL
       && overall_cost_before != ira_overall_cost)
     fprintf (ira_dump_file, "+++Overall after reload %d\n", ira_overall_cost);
-  ira_destroy ();
 
   flag_ira_share_spill_slots = saved_flag_ira_share_spill_slots;
 
-  if (current_loops != NULL)
+  if (! ira_use_lra_p)
     {
-      release_recorded_exits ();
-      flow_loops_free (&ira_loops);
-      free_dominance_info (CDI_DOMINATORS);
+      ira_destroy ();
+      if (current_loops != NULL)
+	{
+	  release_recorded_exits ();
+	  flow_loops_free (&ira_loops);
+	  free_dominance_info (CDI_DOMINATORS);
+	}
+      FOR_ALL_BB (bb)
+	bb->loop_father = NULL;
+      current_loops = NULL;
+      
+      regstat_free_ri ();
+      regstat_free_n_sets_and_refs ();
     }
-  FOR_ALL_BB (bb)
-    bb->loop_father = NULL;
-  current_loops = NULL;
-
-  regstat_free_ri ();
-  regstat_free_n_sets_and_refs ();
 
   if (optimize)
-    {
-      cleanup_cfg (CLEANUP_EXPENSIVE);
+    cleanup_cfg (CLEANUP_EXPENSIVE);
 
-      ira_free (ira_reg_equiv_invariant_p);
-      ira_free (ira_reg_equiv_const);
-    }
+  finish_reg_equiv ();
 
   bitmap_obstack_release (&ira_bitmap_obstack);
 #ifndef IRA_NO_OBSTACK