Hello,

This patch is the largest part of the implementation, and it shows 
changes to the scheduler itself as well as the new files.  The main 
changes in the scheduler fall into two categories: changes to the 
dependence analysis and changes to the initialization mechanism.  The 
dependence analysis changes are as follows:

o new hooks are introduced to make the schedulers be able to perform 
actions when a dependence is found, either a memory or a register one. 
  This is needed for on-the-fly dependence analysis, which we have to do 
because it is unclear how we can keep the dependence graph up to date in 
the presence of control dependencies and register renaming.  I think 
that a project for creating a proper dependence graph with e.g. 
distinguishing between control and data dependencies and storing origin 
of a dependence is needed to make this possible.

o readonly dependence contexts, when analysis generates all proper 
dependencies but doesn't change a context it is based on.  This is 
needed to speed up the on-the-fly analysis.

o sched_get_condition is rewritten such that it doesn't generate rtx 
garbage every time it needs to canonicalize the condition.

The initialization changes can be described as an effort to separate 
common scheduler data, private data, and dependence analysis data, and 
to create a uniform mechanism to initialize per-insn and per-basic block 
data.  The former is achieved with factoring the common/private/deps 
data and the code initializing it into separate structures and 
functions.  For example, the functions sched_init/sched_finish 
initialize/finalize the common part (df/aliases/dfa/etc), 
haifa_sched_{init,finish} work with the haifa data and so on.  The 
latter is achieved via sched_scan interface, which allows scanning 
arbitrary array of insns/bbs and to call user-defined hooks 
{init_extend}_{insn,bb} on each of them.  As a followup, the common part 
of the code, which is now in haifa-sched.c, can be moved to the new 
sched-common.c file.  We did not do that for the sake of easier merge 
process.

The overview of the selective scheduler implementation is given at the 
beginning of the sel-sched.c file.  There are also papers in the GCC 
Summit proceedings of 2006 and 2007.  The sel-sched.c file contains the 
main scheduling routines, and the sel-sched-ir.c file contains 
lower-level routines that manipulate the scheduler IR and data 
structures.  There are also sel-sched-dump.[ch] files, which contain 
dumping infrastructure for the scheduler and some code that eases 
debugging.  Some of the code may be emitted from merge, if we find it 
too specific.

OK for trunk?
Andrey


2008-06-03  Andrey Belevantsev  <abel@ispras.ru>
	    Dmitry Melnik  <dm@ispras.ru>
	    Dmitry Zhurikhin  <zhur@ispras.ru>
	    Alexander Monakov  <amonakov@ispras.ru>
	    Maxim Kuvyrkov  <maxim@codesourcery.com>
	
	* sel-sched.h, sel-sched-dump.h, sel-sched-ir.h, sel-sched.c,
	sel-sched-dump.c, sel-sched-ir.c: New files.

	* Makefile.in (OBJS-common): Add selective scheduling object
	files.
	(sel-sched.o, sel-sched-dump.o, sel-sched-ir.o): New entries.
	(SEL_SCHED_IR_H, SEL_SCHED_DUMP_H): New entries.

	* common.opt (fsel-sched-bookkeeping, fsel-sched-pipelining,
	fsel-sched-pipelining-outer-loops, fsel-sched-renaming,
	fsel-sched-substitution, fselective-scheduling): New flags.

	* haifa-sched.c: Include vecprim.h.
	(issue_rate, sched_verbose_param, note_list, dfa_state_size,
	ready_try, cycle_issued_insns, dfa_lookahead, max_luid, spec_info):
	Make global.
	(old_max_uid, old_last_basic_block): Remove.
	(h_i_d): Make it a vector.
	(INSN_TICK, INTER_TICK, QUEUE_INDEX, INSN_COST): Make them work
	through HID macro.
	(after_recovery, adding_bb_to_current_region_p):
	New variables to handle correct insertion of the recovery code.
	(struct ready_list): Move declaration to sched-int.h.
	(rgn_n_insns): Removed.
	(rtx_vec_t): Move to sched-int.h.
	(find_insn_reg_weight): Remove.
	(find_insn_reg_weight1): Rename to find_insn_reg_weight.
	(extend_h_i_d, init_h_i_d, haifa_init_h_i_d, haifa_finish_h_i_d):
	New functions to initialize / finalize haifa instruction data.
	(dep_weak): Move to sched-deps.c.  Rename to ds_weak.
	(unlink_other_notes): Move logic to add_to_note_list.  Handle
	selective scheduler.
	(ready_lastpos, ready_element, ready_sort, reemit_notes, move_insn,
	find_fallthru_edge): Make global, remove static prototypes.
	(max_issue): Add privileged_n and state parameters.  Use them.
	(extend_global, extend_all): Removed.
	(init_before_recovery): Add new param.  Fix the handling of the case
	when we insert a recovery code before the EXIT which has a predecessor
	with a fallthrough edge to it.
	(create_recovery_block): Make global.  Rename to
	sched_create_recovery_block.  Update.
	(change_pattern): Rename to sched_change_pattern.  Make global.
	(speculate_insn): Rename to sched_speculate_insn.  Make global.
	Split haifa-specific functionality into ...
	(haifa_change_pattern): New static function.
	(sched_extend_bb, sched_init_bb): New static functions.
	(sched_extend_bb): Add the prototype.
	(current_sched_info): Change type to ...
	(struct haifa_sched_info): ... this.  New structure.  Move
	Haifa-specific fields from struct sched_info.
	(insn_cost): Adjust for selective scheduling.
	(dep_cost_1): New static function.  Prototype it.  Move logic from ...
	(insn_cost1): ... here.
     	(dep_cost): Use dep_cost_1.
	(priority): Adjust to work with selective scheduling.  Use
	sched_deps_info instead of current_sched_info.  Process the corner
	case when all dependencies don't contribute to priority.
	(rank_for_schedule): Use ds_weak instead of dep_weak.
	(advance_state): New function.  Move logic from ...
	(advance_one_cycle): ... here.
	(add_to_note_list, concat_note_lists): New functions.
	(rm_other_notes): Make static.  Adjust for selective scheduling.
	(remove_notes, restore_other_notes): New functions.
	(move_insn): Don't call reemit_notes.
	(choose_ready): Remove lookahead variable, use dfa_lookahead.
	Remove more_issue, max_points.  Move the code to initialize
	max_lookahead_tries to max_issue.
	(schedule_block): Remove rgn_n_insns1 parameter.  Don't allocate
	ready.  Adjust uses of move_insn.  Call restore_other_notes.
	(luid): Remove.
	(sched_init, sched_finish): Move Haifa-specific initialization/
	finalization to ...
	(haifa_sched_init, haifa_sched_finish): ... respectively.
	New functions.
	(setup_sched_dump): New function.
	(haifa_init_only_bb): New static function.
	(haifa_speculate_insn): New static function.
	(try_ready): Use haifa_* instead of speculate_insn and
	change_pattern.
	(extend_ready, extend_all): Remove.
	(sched_extend_ready_list, sched_finish_ready_list): New functions.
	(create_check_block_twin, add_to_speculative_block): Use
	haifa_insns_init instead of extend_global.  Update to use new
	initialization functions.  Change parameter.
	(add_block): Remove.
	(sched_scan_info): New.
	(extend_bb, init_bb, extend_insn, init_insn, init_insns_in_bb,
	sched_scan): New static functions for walking through scheduling
	region.
	(sched_init_bbs): New functions to init / finalize
	basic block information.
	(sched_luids): New vector variable to replace uid_to_luid.
	(luids_extend_insn): New function.
	(sched_max_luid): New variable.
	(luids_init_insn): New function.
	(sched_init_luids, sched_finish_luids): New functions.
	(insn_luid): New debug function.
	(sched_extend_target): New function.
	(haifa_init_insn): New static function.
	(sched_init_only_bb): New hook.
	(sched_split_block): New hook.
	(sched_split_block_1): New function.
	(sched_create_empty_bb): New hook.
	(sched_create_empty_bb_1): New function.	
	(common_sched_info, ready): New global variables.
	(current_sched_info_var): Remove.
	(move_block_after_check): Use common_sched_info.		
	(haifa_luid_for_non_insn): New static function.	
	(init_before_recovery): Use haifa_init_only_bb instead of
	add_block.

	* modulo-sched.c: (sms_sched_info): Rename to sms_common_sched_info.
	(sms_sched_deps_info, sms_sched_info): New.
	(setup_sched_infos): New.
	(sms_schedule): Initialize them.  Call haifa_sched_init/finish.
	Do not call regstat_free_calls_crossed, as it called by sched_init.
	(sms_print_insn): Use const_rtx.

	* params.def (PARAM_MAX_PIPELINE_REGION_BLOCKS,
	PARAM_MAX_PIPELINE_REGION_INSNS, PARAM_SELSCHED_MAX_LOOKAHEAD,
	PARAM_SELSCHED_MAX_SCHED_TIMES, PARAM_SELSCHED_INSNS_TO_RENAME): New.

	* sched-deps.c (sched_deps_info): New.  Update all relevant uses of
	current_sched_info to use it.
	(enum reg_pending_barrier_mode): Move to sched-int.h.
	(h_d_i_d): New variable. Initialize to NULL.
	({true, output, anti, spec, forward}_dependency_cache): Initialize
	to NULL.
	(sched_has_condition_p): New function.  Adjust users of
	sched_get_condition to use it instead.
	(conditions_mutex_p): Add arguments indicating which conditions are
	reversed.  Use them.
	(sched_get_condition_with_rev): Rename from sched_get_condition.  Add
	argument to indicate whether returned condition is reversed.  Do not
	generate new rtx when condition should be reversed; indicate it by
	setting new argument instead.
	(add_dependence_list_and_free): Add deps parameter.
	Update all users.  Do not free dependence list when
	deps context is readonly.
	(add_insn_mem_dependence, flush_pending_lists): Adjust for readonly
	contexts.
	(remove_from_dependence_list, remove_from_both_dependence_lists): New.
	(remove_from_deps): New. Use the above functions.	
	(deps_analyze_insn): Do not flush pending write lists on speculation
	checks.  Do not make speculation check a scheduling barrier for memory
	references.
	(cur_max_luid, cur_insn, can_start_lhs_rhs_p): New static variables.
	(add_or_update_back_dep_1): Initialize present_dep_type.
	(haifa_start_insn, haifa_finish_insn, haifa_note_reg_set,
	haifa_note_reg_clobber, haifa_note_reg_use, haifa_note_mem_dep,
	haifa_note_dep): New functions implementing dependence hooks for
	the Haifa scheduler.
	(note_reg_use, note_reg_set, note_reg_clobber, note_mem_dep,
	note_dep): New functions.
	(ds_to_dt): New function.
	(sched_analyze_reg, sched_analyze_1, sched_analyze_2,
	sched_analyze_insn): Update to use dependency hooks infrastructure
	and readonly contexts.
	(deps_analyze_insn): New function.  Move part of logic from ...
	(sched_analyze): ... here.  Also move some logic to ...
	(deps_start_bb): ... here.  New function.
	(add_forw_dep, delete_forw_dep): Guard use of INSN_DEP_COUNT with
	sel_sched_p.
	(sched_deps_init): New function.  Move code from ...
	(init_dependency_caches): ... here.
	(init_deps_data_vector): New.
	(sched_deps_finish): New function.  Move code from ...
	(free_dependency_caches): ... here.
	(init_deps_global, finish_deps_global): Adjust for use with
	selective scheduling.
	(get_dep_weak): Move logic to ...
	(get_dep_weak_1): New function.
	(ds_merge): Move logic to ...
	(ds_merge_1): New static function.
	(ds_full_merge, ds_max_merge, ds_get_speculation_types): New functions.
	(ds_get_max_dep_weak): New function.

	* sched-ebb.c (sched_n_insns): Rename to sched_rgn_n_insns.
	(n_insns): Rename to rgn_n_insns.
	(debug_ebb_dependencies): New function.
	(init_ready_list): Use it.
	(ebb_print_insn): Indicate when an insn starts a new cycle.
	(contributes_to_priority, compute_jump_reg_dependencies,
	add_remove_insn, fix_recovery_cfg): Add ebb_ prefix to function names.
	(ebb_sched_deps_info, ebb_common_sched_info): New variables.
	(schedule_ebb): Initialize them.  Use remove_notes instead of
	rm_other_notes.  Use haifa_local_init/finish.
	(schedule_ebbs): Use haifa_sched_init/finish.

	* sched-int.h: Include basic-block.h and vecprim.h.
	(sched_verbose_param, enum sched_pass_id_t,
	bb_vec_t, insn_vec_t, rtx_vec_t): New.
	(struct sched_scan_info_def): New structure.
	(sched_scan_info, sched_scan, sched_init_bbs,
	sched_init_luids, sched_finish_luids, sched_extend_target,
	haifa_init_h_i_d, haifa_finish_h_i_d): Declare.
	(struct common_sched_info_def): New.
	(common_sched_info, haifa_common_sched_info,
	sched_emulate_haifa_p): Declare.
	(sel_sched_p): New.
	(sched_luids): Declare.
	(INSN_LUID, LUID_BY_UID, SET_INSN_LUID): Declare.
	(sched_max_luid, insn_luid): Declare.
	(note_list, remove_notes, restore_other_notes, bb_note): Declare.
	(sched_insns_init, sched_insns_finish, xrecalloc, move_insn,
	reemit_notes, print_insn, print_pattern, print_value,
	haifa_classify_insn, sel_find_rgns, sel_mark_hard_insn,
	dfa_state_size, advance_state, setup_sched_dump, sched_init,
	sched_finish, sel_insn_is_speculation_check): Export.
	(struct ready_list): Move from haifa-sched.c.
	(ready_try, ready, max_issue): Export.
	(find_fallthru_edge, sched_init_only_bb, sched_split_block,
	sched_split_block_1, sched_create_empty_bb, sched_create_empty_bb_1,
	sched_create_recovery_block, sched_create_recovery_edges): Export.
	(enum reg_pending_barrier_mode): Export.
	(struct deps): New fields `last_reg_pending_barrier' and `readonly'.
	(deps_t): New.
	(struct sched_info): Move compute_jump_reg_dependencies, use_cselib  ...
	(struct haifa_insn_data): and cant_move to ...
	(struct sched_deps_info_def): ... this new structure.
	(h_i_d): Export.
	(HID): New accessor macro.  Rewrite h_i_d accessor macros through HID.
	(struct region): Move from sched-rgn.h.
	(nr_regions, rgn_table, rgn_bb_table, block_to_bb, containing_rgn,
	RGN_NR_BLOCKS, RGN_BLOCKS, RGN_DONT_CALC_DEPS, RGN_HAS_REAL_EBB,
	BLOCK_TO_BB, CONTAINING_RGN): Export.
	(ebb_head, BB_TO_BLOCK, EBB_FIRST_BB, EBB_LAST_BB, INSN_BB): Likewise.
	(current_nr_blocks, current_blocks, target_bb): Likewise.
	(sched_is_disabled_for_current_region_p, sched_rgn_init, sched_rgn_finish,
	rgn_setup_region, sched_rgn_compute_dependencies, sched_rgn_local_init,
	extend_regions, rgn_make_new_region_out_of_new_block,
	compute_priorities, debug_rgn_dependencies,
	free_rgn_deps, contributes_to_priority, extend_rgns, deps_join
	rgn_setup_common_sched_info, rgn_setup_sched_infos, debug_regions,
	debug_region, dump_region_dot, 	dump_region_dot_file,
	haifa_sched_init, haifa_sched_finish): Export.

	* sched-rgn.c: Export region data structures.
	(debug_region, bb_in_region_p, dump_region_dot_file, dump_region_dot): New.
	(too_large): Use estimate_number_of_insns.
	(haifa_find_rgns): New. Move the code from ...
	(find_rgns): ... here.  Call either sel_find_rgns or haifa_find_rgns.
	(free_trg_info): New.
	(compute_trg_info): Allocate candidate tables here instead of ...
	(init_ready_list): ... here.
	(rgn_common_sched_info, rgn_const_sched_deps_info,
	rgn_const_sel_sched_deps_info, rgn_sched_deps_info): New.
	(deps_join): New, extracted from ...
	(propagate_deps): ... here.
	(free_rgn_deps, compute_priorities): New function.
	(sched_rgn_init, sched_rgn_finish): New functions.
	(schedule_region): Use them.
	(sched_rgn_local_preinit, sched_rgn_local_init,
	sched_rgn_local_free, sched_rgn_local_finish): New functions.
	(rgn_make_new_region_out_of_new_block): New.

	* sched-vis.c (print_value, print_pattern): Make global.
	(dump_insn_slim_1, print_rtl_slim, debug_bb_slim,
	debug_bb_n_slim): New functions.

	* target-def.h (TARGET_SCHED_ALLOC_SCHED_CONTEXT,
	TARGET_SCHED_INIT_SCHED_CONTEXT, TARGET_SCHED_SET_SCHED_CONTEXT,
	TARGET_SCHED_CLEAR_SCHED_CONTEXT, TARGET_SCHED_FREE_SCHED_CONTEXT):
	New target hooks.  Initialize them to 0.
	* target.h (struct gcc_target): Add them.

	* doc/invoke.texi: Document new flags and parameters.
	* doc/tm.texi: Document new target hooks.