[RFA] The Integrated Register Allocator

[Vladimir Makarov <vmakarov at redhat dot com>]

 Hi, here is the Integrated Register Allocator (IRA).  To make review
more convenient, I am submitting IRA as a patch relative to recent
trunk (at revision 133688).

IRA is not a default register allocator.  To switch it on, option
-fira should be used.  IRA is currently implemented only for
x86/x86_64/ppc/itanium/sparc/arm/s390.  For all other targets, the
compiler will issue a warning for -fira and will use the old register
allocator as previously.

The compiler has been successfully bootstrapped on
x86/x86_64/ppc64/itanium (other targets were not tried because of
hardware absence).  Several IRA option sets (up to 7 sets on a fast
core2 machine) have been tried.  And all mentioned targets were
bootstraped with at least `-O2 -fira -g'.

On gcc torture tests there is one additional regression for x86_64 and
one for ppc64 in comparison with the trunk.  These two regressions are
not critical: some particular code generation is expected.  The code
is different with IRA usage but it is still correct.  I'll see what
can I do with the tests.

Is it ok to commit it to the trunk?

Vlad



2008-03-29  Vladimir Makarov  <vmakarov@redhat.com>

	* ira.h, ira-int.h, ira.c, ira-costs.c, ira-lives.c,
	ira-conflicts.c, ira-build.c, ira-color.c, ira-emit.c: New files.
	
	* regrename.c (copyprop_hardreg_forward_1): Use function
	get_call_invalidated_used_regs.

	* 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.
	(-fdump-simple-rtl, -fira, -fira-algorithm, -fira-coalesce,
	-fira-ipra, -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.

	* gengtype.c (main): Add HARD_REG_SET.

	* cgraph.c (cgraph_create_node): Initialize function_used_regs.

	* cgraph.h (cgraph_node): New member function_used_regs.

	* postreload-gcse.c (record_opr_changes,
	reg_set_between_after_reload_p, reg_used_between_after_reload_p):
	Use function get_call_invalidated_used_regs.

	* postreload.c (reload_combine, reload_cse_move2add): Use function
	get_call_invalidated_used_regs.
	(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.
	 (debug_save_data): New definition.
	
	* rtlanal.c (reg_set_between_p): Use function
	get_call_invalidated_used_regs.

	* final.c (update_regs_ever_live): New function.
	(rest_of_handle_final): Set up function_used_regs and
	call_used_regs.

	* cfgloopanal.c: Include params.h.
	(estimate_reg_pressure_cost): Return zero when we use regional RA.

	* 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 init_ira.
	(backend_init): Call init_ira_once.
	(finalize): Call finish_ira_once.

	* toplev.h (flag_ira, flag_ira_coalesce, flag_ira_ipra,
	flag_ira_move_spills, flag_ira_propagate_cost,
	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.
	
	* df-scan.c (df_get_call_refs): Use
	get_call_invalidated_used_regs.

	* caller-save.c: Include headers output.h and ira.h.
	(reg_save_code, reg_restore_code, add_stored_regs): Add prototypes.
	(no_caller_save_reg_set): New global variable.
	(save_slots_num, save_slots): New variables.
	(init_caller_save): Set up no_caller_save_reg_set.
	(saved_hard_reg): New structure.
	(hard_reg_map, hard_reg_map, 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.
	(struct bb_info): New.
	(BB_INFO, BB_INFO_BY_INDEX): New macros.
	(calculate_local_save_info, set_up_bb_rts_numbers, rpost_cmp,
	calculate_save_in_out, calculate_save_here,
	make_global_save_analysis, print_hard_reg_set_and_mode,
	print_hard_reg_set, print_save_data, debug_save_data,
	set_hard_reg_saved): New functions.
	(save_call_clobbered_regs): Make global save analysis and use it
	to put save/restore code.  Use function
	get_call_invalidated_used_regs.
	(mark_set_regs): Process pseudo-register too.
	* caller-save.c (insert_restore, insert_save): Use
	adjust_address_nv instead of adjust_address.  Check the mode by
	reg_save_code.

	* cse.c (invalidate_for_call): Use function
	get_call_invalidated_used_regs.  Add parameter.
	(cse_insn): Pass the parameter.

	* global.c (eliminable_regset): Make it external.
	(global_alloc): Dump information about register assigning.
	(mark_elimination): Use DF_LR_IN for IRA.
	(build_insn_chain): Make it external.  Don't ignore spilled
	pseudos for IRA.
	(gate_handle_global_alloc): New function.
	(pass_global_alloc): Add the gate function.

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

	* timevar.def (TV_IRA): New pass.

	* hard-reg-set.h (no_caller_save_reg_set): New external variable
	declaration.

	* recog.c (peep2_free_reg_search_ofs): New static variable.
	(peep2_find_free_register): Remove search_ofs.  Use
	peep2_free_reg_search_ofs instead of it.
	(peephole2_optimize): Reset peep2_free_reg_search_ofs.
	
	* regmove.c (regmove_optimize): Don't do replacement of output
       (rest_of_handle_regmove): Don't do CFG cleanup for IRA.

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

	* function.c (get_call, get_call_invalidated_used_regs): New
	functions.

	* function.h: Add hard-reg-set.h header.
	(emit_status): New member call_used_regs.
	(get_call_invalidated_used_regs): New definition.

	* print-rtl.c (flag_simple): Rename to flag_dump_simple_rtl.

	* gcse.c (compute_hash_table_work, compute_store_table):  Use function
	get_call_invalidated_used_regs.

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

	* cselib.c (cselib_process_insn): Use function
	get_call_invalidated_used_regs.

       * loop-iv.c (simplify_using_assignment): Ditto.

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

	* sched-deps.c (sched_analyze): Use function
	get_call_invalidated_used_regs.

	* regclass.c (contains_reg_of_mode, move_cost, may_move_in_cost,
	may_move_out_cost): Make the variables external.
	(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.
	
	* combine.c (record_dead_and_set_regs): Use function
	get_call_invalidated_used_regs.

	* resource.c (mark_set_resources, mark_target_live_regs): Ditto.

	* var-tracking.c (compute_bb_dataflow, emit_notes_in_bb): Ditto.

	* Makefile.in (FUNCTION_H): Add hard-reg-set.h.
	(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.

	* 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.
	
	* params.def (PARAM_IRA_MAX_LOOPS_NUM): New parameter.

	* reload1.c (ira.h): Include the header.
	 (compute_use_by_pseudos): Permits spilled registers in FROM.
	(temp_pseudo_reg_arr): New variable.
	(reload): Allocate and free temp_pseudo_reg_arr of pseudo_regs.
	 Sort pseudos for IRA.  Call alter_reg with the additional
	 parameter.  Don't clear spilled_pseudos for IRA.  Restore
	 original insn chain for IRA.  Use function
	 get_call_invalidated_used_regs.
	(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.
	(order_regs_for_reload): Initialize 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.
	(emit_input_reload_insns, delete_output_reload): Use additional
	parameter for alter_reg.  Call mark_allocation_change.

Attachment: ira.patch.gz
Description: GNU Zip compressed data