[multiple changes]

2008-08-26  Vladimir Makarov  <vmakarov@redhat.com>

	* ira-build.c, ira-color.c, ira-costs.c, ira.h, ira-lives.c,
	ira.c, ira-conflicts.c, ira-emit.c, ira-int.h: New files.

	* doc/passes.texi: Describe IRA.

	* doc/tm.texi (IRA_COVER_CLASSES,
	IRA_HARD_REGNO_ADD_COST_MULTIPLIER): Describe the new macros.

	* doc/invoke.texi (ira-max-loops-num): Describe the new parameter.
	(-fira, -fira-algorithm, -fira-coalesce, -fno-ira-move-spills,
	-fira-propagate-cost, -fno-ira-share-save-slots,
	-fno-ira-share-spill-slots, -fira-verbose): Describe new options.

	* flags.h (ira_algorithm): New enumeration.
	(flag_ira_algorithm, flag_ira_verbose): New external variable
	declarations.

	* postreload.c (gate_handle_postreload): Don't do post reload
	optimizations unless the reload is completed.

	* reload.c (push_reload, find_dummy_reload): Use DF_LR_OUT for
	IRA.

	* tree-pass.h (pass_ira): New external variable declaration.

	* reload.h: Add 2008 to the Copyright.
    
	* cfgloopanal.c: Include params.h.
	(estimate_reg_pressure_cost): Decrease cost for IRA optimization
	mode.
    
	* params.h (IRA_MAX_LOOPS_NUM): New macro.

	* toplev.c (ira.h): New include.
	(flag_ira_algorithm, flag_ira_verbose): New external variables.
	(backend_init_target): Call ira_init.
	(backend_init): Call ira_init_once.
	(finalize): Call finish_ira_once.

	* toplev.h (flag_ira, flag_ira_coalesce, flag_ira_move_spills,
	flag_ira_share_save_slots, flag_ira_share_spill_slots): New
	external variables.

	* regs.h (contains_reg_of_mode, move_cost, may_move_in_cost,
	may_move_out_cost): New external variable declarations.
	(move_table): New typedef.
    
	* caller-save.c: Include headers output.h and ira.h.
	(no_caller_save_reg_set): New global variable.
	(save_slots_num, save_slots): New variables.
	(reg_save_code, reg_restore_code, add_stored_regs): Add
	prototypes.
	(init_caller_save): Set up no_caller_save_reg_set.
	(init_save_areas): Reset save_slots_num.
	(saved_hard_reg): New structure.
	(hard_reg_map, saved_regs_num, all_saved_regs): New variables.
	(initiate_saved_hard_regs, new_saved_hard_reg,
	finish_saved_hard_regs, saved_hard_reg_compare_func): New
	functions.
	(setup_save_areas): Add code for sharing stack slots.
	(all_blocks): New variable.
	(save_call_clobbered_regs): Process pseudo-register too.
	(mark_set_regs): Process pseudo-register too.
	(insert_one_insn): Put the insn after bb note in a empty basic
	block.  Add insn check.
    
	* global.c (eliminable_regset): Make it external.
	(mark_elimination): Use DF_LR_IN for IRA.
	(pseudo_for_reload_consideration_p): New.
	(build_insn_chain): Make it external.  Don't ignore spilled
	pseudos for IRA.  Use pseudo_for_reload_consideration_p.
	(gate_handle_global_alloc): New function.
	(pass_global_alloc): Add the gate function.

	* opts.c (decode_options): Set up flag_ira.  Print the warning for
	-fira.
	(common_handle_option): Process -fira-algorithm and -fira-verbose.

	* timevar.def (TV_IRA, TV_RELOAD): New passes.

	* regmove.c (regmove_optimize): Don't do replacement of output for
	IRA.

	* hard-reg-set.h (no_caller_save_reg_set, reg_class_subclasses):
	New external variable declarations.

	* local-alloc.c (update_equiv_regs): Make it external.  Return
	true if jump label rebuilding should be done.  Rescan new_insn for
	notes.
	(gate_handle_local_alloc): New function.
	(pass_local_alloc): Add the gate function.

	* alias.c (value_addr_p, stack_addr_p): New functions.
	(nonoverlapping_memrefs_p): Use them for IRA.

	* common.opt (fira, fira-algorithm, fira-coalesce,
	fira-move-spills, fira-share-save-slots, fira-share-spill-slots,
	fira-verbose): New options.

	* regclass.c (reg_class_subclasses, contains_reg_of_mode,
	move_cost, may_move_in_cost, may_move_out_cost): Make the
	variables external.
	(move_table): Remove typedef.
	(init_move_cost): Make it external.
	(allocate_reg_info, resize_reg_info, setup_reg_classes): New
	functions.

	* rtl.h (init_move_cost, allocate_reg_info, resize_reg_info,
	setup_reg_classes): New function prototypes.
	(eliminable_regset): New external variable declaration.
	(build_insn_chain, update_equiv_regs): New function prototypes.
    
	* Makefile.in (IRA_INT_H): New definition.
	(OBJS-common): Add ira.o, ira-build.o, ira-costs.o,
	ira-conflicts.o, ira-color.o, ira-emit.o, and ira-lives.o.
	(reload1.o, toplev.o): Add dependence on ira.h.
	(cfgloopanal.o): Add PARAMS_H.
	(caller-save.o): Add dependence on output.h and ira.h.
	(ira.o, ira-build.o, ira-costs.o, ira-conflicts.o, ira-color.o,
	ira-emit.o, ira-lives.o): New entries.

	* passes.c (pass_ira): New pass.

	* params.def (PARAM_IRA_MAX_LOOPS_NUM): New parameter.

	* reload1.c (ira.h): Include the header.
	(changed_allocation_pseudos): New bitmap.
	(init_reload): Initiate the bitmap.
	(compute_use_by_pseudos): Permits spilled registers in FROM.
	(temp_pseudo_reg_arr): New variable.
	(reload): Allocate and free temp_pseudo_reg_arr.  Sort pseudos for
	IRA.  Call alter_reg with the additional parameter.  Don't clear
	spilled_pseudos for IRA.  Restore original insn chain for IRA.
	Clear changed_allocation_pseudos at the end of reload.
	(calculate_needs_all_insns): Call IRA's mark_memory_move_deletion.
	(hard_regno_to_pseudo_regno): New variable.
	(count_pseudo): Check spilled pseudos.  Set up
	hard_regno_to_pseudo_regno.
	(count_spilled_pseudo): Check spilled pseudos. Update
	hard_regno_to_pseudo_regno.
	(find_reg): Use better_spill_reload_regno_p.  Check
	hard_regno_to_pseudo_regno.
	(alter_reg): Set up spilled_pseudos.  Add a new parameter.  Add
	code for IRA.
	(eliminate_regs_1): Use additional parameter for alter_reg.
	(finish_spills): Set up pseudo_previous_regs only for spilled
	pseudos.  Call reassign_pseudos once for all spilled pseudos, pass
	more arguments.  Don't clear live_throughout and dead_or_set for
	spilled pseudos.  Use additional parameter for alter_reg.  Call
	mark_allocation_change.  Set up changed_allocation_pseudos.
	Remove sanity check.
	(emit_input_reload_insns, delete_output_reload): Use additional
	parameter for alter_reg.  Call mark_allocation_change.
	(substitute, gen_reload_chain_without_interm_reg_p): New
	functions.
	(reloads_conflict): Use gen_reload_chain_without_interm_reg_p.
    
	* testsuite/gcc.dg/20080410-1.c: New file.
	
	* config/s390/s390.h (IRA_COVER_CLASSES,
	IRA_HARD_REGNO_ADD_COST_MULTIPLIER): Define.

	* config/sparc/sparc.h (IRA_COVER_CLASSES): New macro.

	* config/i386/i386.h (IRA_COVER_CLASSES): Ditto.

	* config/ia64/ia64.h (IRA_COVER_CLASSES): Ditto.

	* config/rs6000/rs6000.h (IRA_COVER_CLASSES): Ditto.

	* config/arm/arm.h (IRA_COVER_CLASSES): Ditto.
    
	* config/alpha/alpha.h (IRA_COVER_CLASSES): Ditto.
    
	2008-08-24  Jeff Law  <law@redhat.com>
	* ira.c (setup_reg_class_intersect_union): Prefer smallest class
	when ignoring unavailable registers.

	2008-08-24  Jeff Law  <law@redhat.com>
	* ira-color.c (coalesced_pseudo_reg_slot_compare): Check
	FRAME_GROWS_DOWNWARD and STACK_GROWS_DOWNWARD.
	* ira.c (setup_eliminable_regset): Check stack_realign_needed.
	* config/mn10300/mn10300.h (IRA_COVER_CLASSES): New macro.

	2008-06-03 Steve Chamberlain <steve.chamberlain@gmail.com>
	* ira-build.c (allocno_range_compare_func): Stabilize sort.

	2008-05-29 Andy Hutchinson <hutchinsonandy@aim.com>
	* config/avr/avr.h (IRA_COVER_CLASSES): New macro.
	* reload1.c (find_reg): Process registers in register allocation order.

	2008-05-10 Richard Sandiford <rsandifo@nildram.co.uk>
	* toplev.c (backend_init_target): Move ira_init call from
	here...
	(lang_dependent_init_target): ...to here.

	2008-05-10 Richard Sandiford <rsandifo@nildram.co.uk>
	* ira.c (setup_class_subset_and_memory_move_costs): Don't
	calculate memory move costs for NO_REGS.

	2008-05-05 Kaz Kojima <kkojima@gcc.gnu.org>
	* ira-color.c (ira_fast_allocation): Use no_stack_reg_p only if
	STACK_REGS is defined.

	2008-04-08 Andrew Pinski <andrew_pinski@playstation.sony.com>
	* config/spu/spu.h (IRA_COVER_CLASSES): New macro.

	2008-04-04 Bernd Schmidt <bernd.schmidt@analog.com>
	* config/bfin/bfin.h (IRA_COVER_CLASSES): New macro.

	2008-04-04 Kaz Kojima <kkojima@gcc.gnu.org>
	* config/sh/sh.h (IRA_COVER_CLASSES): Define.
	* config/sh/sh.md (movsicc_true+3): Check if emit returns a
	barrier.

From-SVN: r139590

13 files changed, 167 insertions, 2 deletions

diff --git a/gcc/config/alpha/alpha.h b/gcc/config/alpha/alpha.h
index b37a19d..4336e6c 100644
--- a/gcc/config/alpha/alpha.h
+++ b/gcc/config/alpha/alpha.h
@@ -553,6 +553,19 @@ enum reg_class {
   {0x00000000, 0x7fffffff},	/* FLOAT_REGS */	\
   {0xffffffff, 0xffffffff} }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, FLOAT_REGS, LIM_REG_CLASSES				     \
+}
+
 /* The same information, inverted:
    Return the class number of the smallest class containing
    reg number REGNO.  This could be a conditional expression
diff --git a/gcc/config/arm/arm.h b/gcc/config/arm/arm.h
index d99f77d..fd5067a 100644
--- a/gcc/config/arm/arm.h
+++ b/gcc/config/arm/arm.h
@@ -1185,6 +1185,20 @@ enum reg_class
    or could index an array.  */
 #define REGNO_REG_CLASS(REGNO)  arm_regno_class (REGNO)
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, FPA_REGS, CIRRUS_REGS, VFP_REGS, IWMMXT_GR_REGS, IWMMXT_REGS,\
+  LIM_REG_CLASSES							     \
+}
+
 /* FPA registers can't do subreg as all values are reformatted to internal
    precision.  VFP registers may only be accessed in the mode they
    were set.  */
diff --git a/gcc/config/avr/avr.h b/gcc/config/avr/avr.h
index 6a27c3b..b5132e2 100644
--- a/gcc/config/avr/avr.h
+++ b/gcc/config/avr/avr.h
@@ -291,6 +291,19 @@ enum reg_class {
 
 #define REGNO_REG_CLASS(R) avr_regno_reg_class(R)
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES               \
+{                                       \
+  GENERAL_REGS, LIM_REG_CLASSES         \
+}
+
 #define BASE_REG_CLASS (reload_completed ? BASE_POINTER_REGS : POINTER_REGS)
 
 #define INDEX_REG_CLASS NO_REGS
diff --git a/gcc/config/bfin/bfin.h b/gcc/config/bfin/bfin.h
index 6f2d16c..826e60b 100644
--- a/gcc/config/bfin/bfin.h
+++ b/gcc/config/bfin/bfin.h
@@ -711,6 +711,19 @@ enum reg_class
  : (REGNO) >= REG_RETS ? PROLOGUE_REGS			\
  : NO_REGS)
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES				\
+{							\
+    MOST_REGS, AREGS, CCREGS, LIM_REG_CLASSES		\
+}
+
 /* When defined, the compiler allows registers explicitly used in the
    rtl to be used as spill registers but prevents the compiler from
    extending the lifetime of these registers. */
diff --git a/gcc/config/i386/i386.h b/gcc/config/i386/i386.h
index 2387156..69c7472 100644
--- a/gcc/config/i386/i386.h
+++ b/gcc/config/i386/i386.h
@@ -1274,6 +1274,19 @@ enum reg_class
 { 0xffffffff,0x1fffff }							\
 }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, FLOAT_REGS, MMX_REGS, SSE_REGS, LIM_REG_CLASSES		     \
+}
+
 /* The same information, inverted:
    Return the class number of the smallest class containing
    reg number REGNO.  This could be a conditional expression
diff --git a/gcc/config/ia64/ia64.h b/gcc/config/ia64/ia64.h
index 60934f2..6fca690 100644
--- a/gcc/config/ia64/ia64.h
+++ b/gcc/config/ia64/ia64.h
@@ -800,6 +800,19 @@ enum reg_class
     0xFFFFFFFF, 0xFFFFFFFF, 0x3FFF },			\
 }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  PR_REGS, BR_REGS, AR_M_REGS, AR_I_REGS, GR_REGS, FR_REGS, LIM_REG_CLASSES  \
+}
+
 /* A C expression whose value is a register class containing hard register
    REGNO.  In general there is more than one such class; choose a class which
    is "minimal", meaning that no smaller class also contains the register.  */
diff --git a/gcc/config/mn10300/mn10300.h b/gcc/config/mn10300/mn10300.h
index 1d2339b..07035fb 100644
--- a/gcc/config/mn10300/mn10300.h
+++ b/gcc/config/mn10300/mn10300.h
@@ -295,6 +295,19 @@ enum reg_class {
  { 0xffffffff, 0x3ffff } /* ALL_REGS 	*/	\
 }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES                                                    \
+{                                                                            \
+  GENERAL_REGS, FP_REGS, LIM_REG_CLASSES \
+}
+
 /* The same information, inverted:
    Return the class number of the smallest class containing
    reg number REGNO.  This could be a conditional expression
diff --git a/gcc/config/rs6000/rs6000.h b/gcc/config/rs6000/rs6000.h
index 1f6d07b..048d163 100644
--- a/gcc/config/rs6000/rs6000.h
+++ b/gcc/config/rs6000/rs6000.h
@@ -1128,6 +1128,22 @@ enum reg_class
   { 0xffffffff, 0xffffffff, 0xffffffff, 0x0003ffff }  /* ALL_REGS */	     \
 }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, SPECIAL_REGS, FLOAT_REGS, ALTIVEC_REGS,			     \
+  /*VRSAVE_REGS,*/ VSCR_REGS, SPE_ACC_REGS, SPEFSCR_REGS,		     \
+  /* MQ_REGS, LINK_REGS, CTR_REGS, */					     \
+  CR_REGS, XER_REGS, LIM_REG_CLASSES					     \
+}
+
 /* The same information, inverted:
    Return the class number of the smallest class containing
    reg number REGNO.  This could be a conditional expression
diff --git a/gcc/config/s390/s390.h b/gcc/config/s390/s390.h
index a8cb477..b96f100 100644
--- a/gcc/config/s390/s390.h
+++ b/gcc/config/s390/s390.h
@@ -478,6 +478,30 @@ enum reg_class
   { 0xffffffff, 0x0000003f },	/* ALL_REGS */		\
 }
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, FP_REGS, CC_REGS, ACCESS_REGS, LIM_REG_CLASSES		     \
+}
+
+/* In some case register allocation order is not enough for IRA to
+   generate a good code.  The following macro (if defined) increases
+   cost of REGNO for a pseudo approximately by pseudo usage frequency
+   multiplied by the macro value.
+
+   We avoid usage of BASE_REGNUM by nonzero macro value because the
+   reload can decide not to use the hard register because some
+   constant was forced to be in memory.  */
+#define IRA_HARD_REGNO_ADD_COST_MULTIPLIER(regno)	\
+  (regno == BASE_REGNUM ? 0.0 : 0.5)
+
 /* Register -> class mapping.  */
 extern const enum reg_class regclass_map[FIRST_PSEUDO_REGISTER];
 #define REGNO_REG_CLASS(REGNO) (regclass_map[REGNO])
diff --git a/gcc/config/sh/sh.h b/gcc/config/sh/sh.h
index 2305872..8af2f43 100644
--- a/gcc/config/sh/sh.h
+++ b/gcc/config/sh/sh.h
@@ -1499,6 +1499,20 @@ enum reg_class
 extern enum reg_class regno_reg_class[FIRST_PSEUDO_REGISTER];
 #define REGNO_REG_CLASS(REGNO) regno_reg_class[(REGNO)]
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, FP_REGS, PR_REGS, T_REGS, MAC_REGS, TARGET_REGS,  	     \
+  LIM_REG_CLASSES							     \
+}
+
 /* When defined, the compiler allows registers explicitly used in the
    rtl to be used as spill registers but prevents the compiler from
    extending the lifetime of these registers.  */
diff --git a/gcc/config/sh/sh.md b/gcc/config/sh/sh.md
index 6300054..b6e56aa 100644
--- a/gcc/config/sh/sh.md
+++ b/gcc/config/sh/sh.md
@@ -1143,7 +1143,7 @@
    (set (match_dup 4) (match_dup 5))]
   "
 {
-  rtx set1, set2;
+  rtx set1, set2, insn2;
   rtx replacements[4];
 
   /* We want to replace occurrences of operands[0] with operands[1] and
@@ -1173,7 +1173,10 @@
   extract_insn (emit_insn (set1));
   if (! constrain_operands (1))
     goto failure;
-  extract_insn (emit (set2));
+  insn2 = emit (set2);
+  if (GET_CODE (insn2) == BARRIER)
+    goto failure;
+  extract_insn (insn2);
   if (! constrain_operands (1))
     {
       rtx tmp;
diff --git a/gcc/config/sparc/sparc.h b/gcc/config/sparc/sparc.h
index 4d180da..4289470 100644
--- a/gcc/config/sparc/sparc.h
+++ b/gcc/config/sparc/sparc.h
@@ -1078,6 +1078,19 @@ enum reg_class { NO_REGS, FPCC_REGS, I64_REGS, GENERAL_REGS, FP_REGS,
    {-1, -1, -1, 0x20},	/* GENERAL_OR_EXTRA_FP_REGS */	\
    {-1, -1, -1, 0x3f}}	/* ALL_REGS */
 
+/* The following macro defines cover classes for Integrated Register
+   Allocator.  Cover classes is a set of non-intersected register
+   classes covering all hard registers used for register allocation
+   purpose.  Any move between two registers of a cover class should be
+   cheaper than load or store of the registers.  The macro value is
+   array of register classes with LIM_REG_CLASSES used as the end
+   marker.  */
+
+#define IRA_COVER_CLASSES						     \
+{									     \
+  GENERAL_REGS, EXTRA_FP_REGS, FPCC_REGS, LIM_REG_CLASSES		     \
+}
+
 /* Defines invalid mode changes.  Borrowed from pa64-regs.h.
 
    SImode loads to floating-point registers are not zero-extended.
diff --git a/gcc/config/spu/spu.h b/gcc/config/spu/spu.h
index 0bd69d3..86042aa 100644
--- a/gcc/config/spu/spu.h
+++ b/gcc/config/spu/spu.h
@@ -196,6 +196,9 @@ enum reg_class {
    LIM_REG_CLASSES 
 };
 
+/* SPU is simple, it really only has one class of registers.  */
+#define IRA_COVER_CLASSES { GENERAL_REGS, LIM_REG_CLASSES }
+
 #define N_REG_CLASSES (int) LIM_REG_CLASSES
 
 #define REG_CLASS_NAMES \