2008-08-31 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.
	(sched-vis.o): Add dependency on $(INSN_ATTR_H).
	* cfghooks.h (get_cfg_hooks, set_cfg_hooks): New prototypes.
	* cfghooks.c (get_cfg_hooks, set_cfg_hooks): New functions.
	(make_forwarder_block): Update loop latch if we have redirected
	the loop latch edge.
	* cfgloop.c (get_loop_body_in_custom_order): New function.
	* cfgloop.h (LOOPS_HAVE_FALLTHRU_PREHEADERS): New enum field.
	(CP_FALLTHRU_PREHEADERS): Likewise.
	(get_loop_body_in_custom_order): Declare.
	* cfgloopmanip.c (has_preds_from_loop): New.
	(create_preheader): Honor CP_FALLTHRU_PREHEADERS.
	Assert that the preheader edge will be fall thru when it is set.
	* common.opt (fsel-sched-bookkeeping, fsel-sched-pipelining,
	fsel-sched-pipelining-outer-loops, fsel-sched-renaming,
	fsel-sched-substitution, fselective-scheduling): New flags.
    	* cse.c (hash_rtx_cb): New.
	(hash_rtx): Use it.
	* dbgcnt.def (sel_sched_cnt, sel_sched_region_cnt,
	sel_sched_insn_cnt): New counters. 
	* final.c (compute_alignments): Export.  Free dominance info after loop_optimizer_finalize.
	* genattr.c (main): Output maximal_insn_latency prototype.
	* genautomata.c (output_default_latencies): New. Factor its code from ...
	(output_internal_insn_latency_func): ... here.
	(output_internal_maximal_insn_latency_func): New.
	(output_maximal_insn_latency_func): New.
	* hard-reg-set.h (UHOST_BITS_PER_WIDE_INT): Define unconditionally.
	(struct hard_reg_set_iterator): New.
	(hard_reg_set_iter_init, hard_reg_set_iter_set,
	hard_reg_set_iter_next): New functions.
	(EXECUTE_IF_SET_IN_HARD_REG_SET): New macro.
	* lists.c (remove_free_INSN_LIST_node,
	remove_free_EXPR_LIST_node): New functions.
	* loop-init.c (loop_optimizer_init): When LOOPS_HAVE_FALLTHRU_PREHEADERS,
	set CP_FALLTHRU_PREHEADERS when calling create_preheaders.
	(loop_optimizer_finalize): Do not verify flow info after reload.
	* recog.c (validate_replace_rtx_1): New parameter simplify.
	Default it to true.  Update all uses.  Factor out simplifying
	code to ...
	(simplify_while_replacing): ... this new function.
	(validate_replace_rtx_part,
	validate_replace_rtx_part_nosimplify): New.
	* recog.h (validate_replace_rtx_part,
	validate_replace_rtx_part_nosimplify): Declare.
	* rtl.c (rtx_equal_p_cb): New.
	(rtx_equal_p): Use it.
	* rtl.h (rtx_equal_p_cb, hash_rtx_cb): Declare.
	(remove_free_INSN_LIST_NODE, remove_free_EXPR_LIST_node,
	debug_bb_n_slim, debug_bb_slim,    print_rtl_slim): Likewise.
	* vecprim.h: Add a vector type for unsigned int. 
	* haifa-sched.c: Include vecprim.h and cfgloop.h.
	(issue_rate, sched_verbose_param, note_list, dfa_state_size,
	ready_try, cycle_issued_insns, spec_info): Make global.
	(readyp): Initialize.
	(dfa_lookahead): New global variable.
	(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.
	(haifa_init_h_i_d, haifa_finish_h_i_d):
	New functions to initialize / finalize haifa instruction data.
	(extend_h_i_d, init_h_i_d): Rewrite.
	(unlink_other_notes): Move logic to add_to_note_list.  Handle
	selective scheduler.
	(ready_lastpos, ready_element, ready_sort, reemit_notes,
	find_fallthru_edge): Make global, remove static prototypes.
	(max_issue): Make global.  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): New static function.
	(sched_init_bbs): New function.
	(current_sched_info): Change type to struct haifa_sched_info.
	(insn_cost): Adjust for selective scheduling.
	(dep_cost_1): New function.  Move logic from ...
	(dep_cost): ... here.
	(dep_cost): Use dep_cost_1.
	(contributes_to_priority_p): Use sched_deps_info instead of
	current_sched_info.
	(priority): Adjust to work with selective scheduling.  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): Add two arguments.  Update assert.  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 use 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.  Factor out code from
	create_check_block_twin to ...
	(sched_create_recovery_edges) ... this new function.
	(add_block): Remove.
	(sched_scan_info): New.
	(extend_bb): Use sched_scan_info.
	(init_bb, extend_insn, init_insn, init_insns_in_bb, sched_scan): New
	static functions for walking through scheduling region.
	(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.
	(increase_insn_priority): New.
	* modulo-sched.c: (issue_rate): Remove static declaration.
	(sms_sched_info): Change type to haifa_sched_info.
	(sms_sched_deps_info, sms_common_sched_info): New variables.
	(setup_sched_infos): New.
	(sms_schedule): Initialize them.  Call haifa_sched_init/finish.
	Do not call regstat_free_calls_crossed.
	(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,
	PARAM_SCHED_MEM_TRUE_DEP_COST): 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.
	(estimate_dep_weak): Remove static declaration.
	(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.	
	(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, extend_deps_reg_info, maybe_extend_reg_info_p): New
	functions.
	(init_deps): Initialize last_reg_pending_barrier and deps->readonly.
	(free_deps): Initialize deps->reg_last.
	(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.  Remove.
	(init_deps_data_vector): New.
	(sched_deps_finish): New function.  Move code from ...
	(free_dependency_caches): ... here.  Remove.
	(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.
	(begin_schedule_ready): Use sched_init_only_bb.
	(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.
	(add_block1): Remove to ebb_add_block.
	(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 vecprim.h, remove rtl.h.
	(struct ready_list): Delete declaration.
	(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, 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.
	(ebb_compute_jump_reg_dependencies, 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): Rename to haifa_sched_info.  Use const_rtx for
	print_insn field.  Move add_block and fix_recovery_cfg to
	common_sched_info_def.  Move compute_jump_reg_dependencies, use_cselib  ...
	(struct sched_deps_info_def): ... this new structure.
	(sched_deps_info): Declare.
	(struct spec_info_def): Remove weakness_cutoff, add
	data_weakness_cutoff and control_weakness_cutoff.
	(spec_info): Declare.
	(struct _haifa_deps_insn_data): Split from haifa_insn_data.  Add
	dep_count field.
	(struct haifa_insn_data): Rename to struct _haifa_insn_data.
	(haifa_insn_data_def, haifa_insn_data_t): New typedefs.
	(current_sched_info): Change type to struct haifa_sched_info.
	(haifa_deps_insn_data_def, haifa_deps_insn_data_t): New typedefs.
	(h_d_i_d): New variable.
	(HDID): New accessor macro.
	(h_i_d): Change type to VEC (haifa_insn_data_def, heap) *.
	(HID): New accessor macro.  Rewrite h_i_d accessor macros through HID
	and HDID.
	(IS_SPECULATION_CHECK_P): Update for selective scheduler.
	(enum SCHED_FLAGS): Update for selective scheduler.
	(enum SPEC_SCHED_FLAGS): New flag SEL_SCHED_SPEC_DONT_CHECK_CONTROL.
	(init_dependency_caches, free_dependency_caches): Delete declarations.
	(deps_analyze_insn, remove_from_deps, get_dep_weak_1,
	estimate_dep_weak, ds_full_merge, ds_max_merge, ds_weak,
	ds_get_speculation_types, ds_get_max_dep_weak, sched_deps_init,
	sched_deps_finish, haifa_note_reg_set, haifa_note_reg_use,
	haifa_note_reg_clobber, maybe_extend_reg_info_p, deps_start_bb,
	ds_to_dt): Export.
	(rm_other_notes): Delete declaration.
	(schedule_block): Remove one argument.
	(cycle_issued_insns, issue_rate, dfa_lookahead, ready_sort,
	ready_element, ready_lastpos, sched_extend_ready_list,
	sched_finish_ready_list, sched_change_pattern, sched_speculate_insn,
	concat_note_lists): Export.
	(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.
	(dep_cost_1, 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.
	(get_rgn_sched_max_insns_priority, sel_add_to_insn_priority, 
	increase_insn_priority): Likewise.
	* sched-rgn.c: Include sel-sched.h.
	(ref_counts): New static variable.  Use it ...
	(INSN_REF_COUNT): ... here.  Rewrite and move closer to uses.
	(FED_BY_SPEC_LOAD, IS_LOAD_INSN): Rewrite to use HID accessor macro.
	(sched_is_disabled_for_current_region_p): Delete static declaration.
	(struct region): Move to sched-int.h.
	(nr_regions, rgn_table, rgn_bb_table, block_to_bb, containing_rgn,
	ebb_head): Define and initialize.
	(RGN_NR_BLOCKS, RGN_BLOCKS, RGN_DONT_CALC_DEPS, RGN_HAS_REAL_EBB,
	BLOCK_TO_BB, CONTAINING_RGN, debug_regions, extend_regions,
	BB_TO_BLOCK, EBB_FIRST_BB, EBB_LAST_BB): Move to
	sched-int.h.
	(find_single_block_region): Add new argument to indicate that EBB
	regions should be constructed.
	(debug_live): Delete declaration.
	(current_nr_blocks, current_blocks, target_bb): Remove static qualifiers.
	(compute_dom_prob_ps, check_live, update_live, set_spec_fed): Delete
	declaration.
	(init_regions): Delete declaration.
	(debug_region, bb_in_region_p, dump_region_dot_file, dump_region_dot,
	rgn_estimate_number_of_insns): 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_print_insn): Use const_rtx.
	(contributes_to_priority, extend_regions): Delete static declaration.
	(add_remove_insn, fix_recovery_cfg): Add rgn_ to function names.
	(add_block1): Rename to rgn_add_block.
	(debug_rgn_dependencies): Delete static qualifier.
	(new_ready): Use sched_deps_info.  Simplify.
	(rgn_common_sched_info, rgn_const_sched_deps_info,
	rgn_const_sel_sched_deps_info, rgn_sched_deps_info, rgn_sched_info): New.
	(region_sched_info): Rename to rgn_const_sched_info.
	(deps_join): New, extracted from ...
	(propagate_deps): ... here.
	(compute_block_dependences, debug_dependencies): Update for selective
	scheduling.
	(free_rgn_deps, compute_priorities): New functions.
	(sched_rgn_init, sched_rgn_finish, rgn_setup_region,
	sched_rgn_compute_dependencies): New functions.
	(schedule_region): Use them.
	(sched_rgn_local_init, sched_rgn_local_free, sched_rgn_local_finish,
	rgn_setup_common_sched_info, rgn_setup_sched_infos):
	New functions.
	(schedule_insns): Call new functions that were split out.
	(rgn_make_new_region_out_of_new_block): New.
	(get_rgn_sched_max_insns_priority): New.
	(rest_of_handle_sched, rest_of_handle_sched2): Call selective
	scheduling when appropriate.
	* sched-vis.c: Include insn-attr.h.
	(print_value, print_pattern): Make global.
	(print_rtl_slim, debug_bb_slim, debug_bb_n_slim): New functions.
	* target-def.h (TARGET_SCHED_ADJUST_COST_2,
	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, TARGET_SCHED_GET_INSN_CHECKED_DS,
	TARGET_SCHED_GET_INSN_SPEC_DS, TARGET_SCHED_SKIP_RTX_P): New target
	hooks.  Initialize them to 0.
	(TARGET_SCHED_GEN_CHECK): Rename to TARGET_SCHED_GEN_SPEC_CHECK.
	* target.h (struct gcc_target): Add them.  Rename gen_check field to
	gen_spec_check.
	* flags.h (sel_sched_switch_set): Declare.
	* opts.c (sel_sched_switch_set): New variable.
	(decode_options): Unset flag_sel_sched_pipelining_outer_loops if
	pipelining is disabled from command line.
	(common_handle_option): Record whether selective scheduling is
	requested from command line.
	* doc/invoke.texi: Document new flags and parameters.
	* doc/tm.texi: Document new target hooks.
	* config/ia64/ia64.c (TARGET_SCHED_GEN_SPEC_CHECK): Define to ia64_gen_check.
	(dfa_state_size): Do not declare locally.
	* config/ia64/ia64.opt (msched-ar-data-spec): Default to 0.
	* config/rs6000/rs6000.c (rs6000_init_sched_context,
	rs6000_alloc_sched_context, rs6000_set_sched_context,
	rs6000_free_sched_context): New functions.
	(struct _rs6000_sched_context): New.
	(rs6000_sched_reorder2): Do not modify INSN_PRIORITY for selective
	scheduling.
	(rs6000_sched_finish): Do not run for selective scheduling. 


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

1 files changed, 464 insertions, 83 deletions

diff --git a/gcc/sched-int.h b/gcc/sched-int.h
index bfbb8612456..2f9b7818eaa 100644
--- a/gcc/sched-int.h
+++ b/gcc/sched-int.h
@@ -26,18 +26,196 @@ along with GCC; see the file COPYING3.  If not see
 
 /* For state_t.  */
 #include "insn-attr.h"
-/* For regset_head.  */
-#include "basic-block.h"
-/* For reg_note.  */
-#include "rtl.h"
 #include "df.h"
+#include "basic-block.h"
+
+/* For VEC (int, heap).  */
+#include "vecprim.h"
+
+/* Identificator of a scheduler pass.  */
+enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,
+		       SCHED_SMS_PASS, SCHED_SEL_PASS };
+
+typedef VEC (basic_block, heap) *bb_vec_t;
+typedef VEC (rtx, heap) *insn_vec_t;
+typedef VEC(rtx, heap) *rtx_vec_t;
+
+struct sched_scan_info_def
+{
+  /* This hook notifies scheduler frontend to extend its internal per basic
+     block data structures.  This hook should be called once before a series of
+     calls to bb_init ().  */
+  void (*extend_bb) (void);
+
+  /* This hook makes scheduler frontend to initialize its internal data
+     structures for the passed basic block.  */
+  void (*init_bb) (basic_block);
+
+  /* This hook notifies scheduler frontend to extend its internal per insn data
+     structures.  This hook should be called once before a series of calls to
+     insn_init ().  */
+  void (*extend_insn) (void);
+
+  /* This hook makes scheduler frontend to initialize its internal data
+     structures for the passed insn.  */
+  void (*init_insn) (rtx);
+};
+
+extern const struct sched_scan_info_def *sched_scan_info;
+
+extern void sched_scan (const struct sched_scan_info_def *,
+			bb_vec_t, basic_block, insn_vec_t, rtx);
+
+extern void sched_init_bbs (void);
+
+extern void sched_init_luids (bb_vec_t, basic_block, insn_vec_t, rtx);
+extern void sched_finish_luids (void);
+
+extern void sched_extend_target (void);
+
+extern void haifa_init_h_i_d (bb_vec_t, basic_block, insn_vec_t, rtx);
+extern void haifa_finish_h_i_d (void);
+
+/* Hooks that are common to all the schedulers.  */
+struct common_sched_info_def
+{
+  /* Called after blocks were rearranged due to movement of jump instruction.
+     The first parameter - index of basic block, in which jump currently is.
+     The second parameter - index of basic block, in which jump used
+     to be.
+     The third parameter - index of basic block, that follows the second
+     parameter.  */
+  void (*fix_recovery_cfg) (int, int, int);
+
+  /* Called to notify frontend, that new basic block is being added.
+     The first parameter - new basic block.
+     The second parameter - block, after which new basic block is being added,
+     or EXIT_BLOCK_PTR, if recovery block is being added,
+     or NULL, if standalone block is being added.  */
+  void (*add_block) (basic_block, basic_block);
+
+  /* Estimate number of insns in the basic block.  */
+  int (*estimate_number_of_insns) (basic_block);
+
+  /* Given a non-insn (!INSN_P (x)) return
+     -1 - if this rtx don't need a luid.
+     0 - if it should have the same luid as the previous insn.
+     1 - if it needs a separate luid.  */
+  int (*luid_for_non_insn) (rtx);
+
+  /* Scheduler pass identifier.  It is preferably used in assertions.  */
+  enum sched_pass_id_t sched_pass_id;
+};
+
+extern struct common_sched_info_def *common_sched_info;
+
+extern const struct common_sched_info_def haifa_common_sched_info;
+
+/* Return true if selective scheduling pass is working.  */
+static inline bool
+sel_sched_p (void)
+{
+  return common_sched_info->sched_pass_id == SCHED_SEL_PASS;
+}
+
+/* Returns maximum priority that an insn was assigned to.  */
+extern int get_rgn_sched_max_insns_priority (void);
+
+/* Increases effective priority for INSN by AMOUNT.  */
+extern void sel_add_to_insn_priority (rtx, int);
+
+/* True if during selective scheduling we need to emulate some of haifa
+   scheduler behaviour.  */
+extern int sched_emulate_haifa_p;
+
+/* Mapping from INSN_UID to INSN_LUID.  In the end all other per insn data
+   structures should be indexed by luid.  */
+extern VEC (int, heap) *sched_luids;
+#define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))
+#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))
+
+#define SET_INSN_LUID(INSN, LUID) \
+(VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))
+
+/* The highest INSN_LUID.  */
+extern int sched_max_luid;
+
+extern int insn_luid (rtx);
+
+/* This list holds ripped off notes from the current block.  These notes will
+   be attached to the beginning of the block when its scheduling is
+   finished.  */
+extern rtx note_list;
+
+extern void remove_notes (rtx, rtx);
+extern rtx restore_other_notes (rtx, basic_block);
+extern void sched_insns_init (rtx);
+extern void sched_insns_finish (void);
+
+extern void *xrecalloc (void *, size_t, size_t, size_t);
+extern rtx bb_note (basic_block);
+
+extern void reemit_notes (rtx);
+
+/* Functions in sched-vis.c.  */
+extern void print_insn (char *, const_rtx, int);
+extern void print_pattern (char *, const_rtx, int);
+extern void print_value (char *, const_rtx, int);
+
+/* Functions in haifa-sched.c.  */
+extern int haifa_classify_insn (const_rtx);
+
+/* Functions in sel-sched-ir.c.  */
+extern void sel_find_rgns (void);
+extern void sel_mark_hard_insn (rtx);
+
+extern size_t dfa_state_size;
+
+extern void advance_state (state_t);
+
+extern void setup_sched_dump (void);
+extern void sched_init (void);
+extern void sched_finish (void);
+
+extern bool sel_insn_is_speculation_check (rtx);
+
+/* Describe the ready list of the scheduler.
+   VEC holds space enough for all insns in the current region.  VECLEN
+   says how many exactly.
+   FIRST is the index of the element with the highest priority; i.e. the
+   last one in the ready list, since elements are ordered by ascending
+   priority.
+   N_READY determines how many insns are on the ready list.  */
+struct ready_list
+{
+  rtx *vec;
+  int veclen;
+  int first;
+  int n_ready;
+};
+
+extern char *ready_try;
+extern struct ready_list ready;
+
+extern int max_issue (struct ready_list *, int, state_t, int *);
+
+extern void ebb_compute_jump_reg_dependencies (rtx, regset, regset, regset);
+
+extern edge find_fallthru_edge (basic_block);
+
+extern void (* sched_init_only_bb) (basic_block, basic_block);
+extern basic_block (* sched_split_block) (basic_block, rtx);
+extern basic_block sched_split_block_1 (basic_block, rtx);
+extern basic_block (* sched_create_empty_bb) (basic_block);
+extern basic_block sched_create_empty_bb_1 (basic_block);
+
+extern basic_block sched_create_recovery_block (basic_block *);
+extern void sched_create_recovery_edges (basic_block, basic_block,
+					 basic_block);
 
 /* Pointer to data describing the current DFA state.  */
 extern state_t curr_state;
 
-/* Forward declaration.  */
-struct ready_list;
-
 /* Type to represent status of a dependence.  */
 typedef int ds_t;
 
@@ -242,6 +420,16 @@ struct _dep_node
 #define DEP_NODE_DEP(N) (&(N)->dep)
 #define DEP_NODE_FORW(N) (&(N)->forw)
 
+/* The following enumeration values tell us what dependencies we
+   should use to implement the barrier.  We use true-dependencies for
+   TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */
+enum reg_pending_barrier_mode
+{
+  NOT_A_BARRIER = 0,
+  MOVE_BARRIER,
+  TRUE_BARRIER
+};
+
 /* Describe state of dependencies used during sched_analyze phase.  */
 struct deps
 {
@@ -330,14 +518,23 @@ struct deps
 
   /* Element N is set for each register that is conditionally set.  */
   regset_head reg_conditional_sets;
+
+  /* Shows the last value of reg_pending_barrier associated with the insn.  */
+  enum reg_pending_barrier_mode last_reg_pending_barrier;
+
+  /* True when this context should be treated as a readonly by 
+     the analysis.  */
+  BOOL_BITFIELD readonly : 1;
 };
 
+typedef struct deps *deps_t;
+
 /* This structure holds some state of the current scheduling pass, and
    contains some function pointers that abstract out some of the non-generic
    functionality from functions such as schedule_block or schedule_insn.
    There is one global variable, current_sched_info, which points to the
    sched_info structure currently in use.  */
-struct sched_info
+struct haifa_sched_info
 {
   /* Add all insns that are initially ready to the ready list.  Called once
      before scheduling a set of insns.  */
@@ -361,14 +558,10 @@ struct sched_info
      necessary to identify this insn in an output.  It's valid to use a
      static buffer for this.  The ALIGNED parameter should cause the string
      to be formatted so that multiple output lines will line up nicely.  */
-  const char *(*print_insn) (rtx, int);
+  const char *(*print_insn) (const_rtx, int);
   /* Return nonzero if an insn should be included in priority
      calculations.  */
   int (*contributes_to_priority) (rtx, rtx);
-  /* Called when computing dependencies for a JUMP_INSN.  This function
-     should store the set of registers that must be considered as set by
-     the jump in the regset.  */
-  void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 
   /* The boundaries of the set of insns to be scheduled.  */
   rtx prev_head, next_tail;
@@ -379,11 +572,6 @@ struct sched_info
 
   /* If nonzero, enables an additional sanity check in schedule_block.  */
   unsigned int queue_must_finish_empty:1;
-  /* Nonzero if we should use cselib for better alias analysis.  This
-     must be 0 if the dependency information is used after sched_analyze
-     has completed, e.g. if we're using it to initialize state for successor
-     blocks in region scheduling.  */
-  unsigned int use_cselib:1;
 
   /* Maximum priority that has been assigned to an insn.  */
   int sched_max_insns_priority;
@@ -399,27 +587,12 @@ struct sched_info
      last scheduled instruction.  */
   void (*begin_schedule_ready) (rtx, rtx);
 
-  /* Called to notify frontend, that new basic block is being added.
-     The first parameter - new basic block.
-     The second parameter - block, after which new basic block is being added,
-     or EXIT_BLOCK_PTR, if recovery block is being added,
-     or NULL, if standalone block is being added.  */
-  void (*add_block) (basic_block, basic_block);
-
   /* If the second parameter is not NULL, return nonnull value, if the
      basic block should be advanced.
      If the second parameter is NULL, return the next basic block in EBB.
      The first parameter is the current basic block in EBB.  */
   basic_block (*advance_target_bb) (basic_block, rtx);
 
-  /* Called after blocks were rearranged due to movement of jump instruction.
-     The first parameter - index of basic block, in which jump currently is.
-     The second parameter - index of basic block, in which jump used
-     to be.
-     The third parameter - index of basic block, that follows the second
-     parameter.  */
-  void (*fix_recovery_cfg) (int, int, int);
-
   /* ??? FIXME: should use straight bitfields inside sched_info instead of
      this flag field.  */
   unsigned int flags;
@@ -438,23 +611,40 @@ struct spec_info_def
 
   /* Minimal cumulative weakness of speculative instruction's
      dependencies, so that insn will be scheduled.  */
-  dw_t weakness_cutoff;
+  dw_t data_weakness_cutoff;
+
+  /* Minimal usefulness of speculative instruction to be considered for
+     scheduling.  */
+  int control_weakness_cutoff;
 
   /* Flags from the enum SPEC_SCHED_FLAGS.  */
   int flags;
 };
 typedef struct spec_info_def *spec_info_t;
 
-extern struct sched_info *current_sched_info;
+extern spec_info_t spec_info;
+
+extern struct haifa_sched_info *current_sched_info;
 
 /* Indexed by INSN_UID, the collection of all data associated with
    a single instruction.  */
 
-struct haifa_insn_data
+struct _haifa_deps_insn_data
 {
-  /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
-     because when h_i_d extends, addresses of the deps_list->first
-     change without updating deps_list->first->next->prev_nextp.  */
+  /* The number of incoming edges in the forward dependency graph.
+     As scheduling proceeds, counts are decreased.  An insn moves to
+     the ready queue when its counter reaches zero.  */
+  int dep_count;
+
+  /* Nonzero if instruction has internal dependence
+     (e.g. add_dependence was invoked with (insn == elem)).  */
+  unsigned int has_internal_dep;
+
+  /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
+     h_i_d because when h_i_d extends, addresses of the deps_list->first
+     change without updating deps_list->first->next->prev_nextp.  Thus
+     BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
+     list is allocated on the obstack.  */
 
   /* A list of hard backward dependencies.  The insn is a consumer of all the
      deps mentioned here.  */
@@ -476,7 +666,17 @@ struct haifa_insn_data
      from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the
      search in 'forw_deps'.  */
   deps_list_t resolved_forw_deps;
- 
+
+  /* Some insns (e.g. call) are not allowed to move across blocks.  */
+  unsigned int cant_move : 1;
+};
+
+struct _haifa_insn_data
+{
+  /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t
+     because when h_i_d extends, addresses of the deps_list->first
+     change without updating deps_list->first->next->prev_nextp.  */
+
   /* Logical uid gives the original ordering of the insns.  */
   int luid;
 
@@ -503,9 +703,6 @@ struct haifa_insn_data
      register pressure.  */
   short reg_weight;
 
-  /* Some insns (e.g. call) are not allowed to move across blocks.  */
-  unsigned int cant_move : 1;
-
   /* Set if there's DEF-USE dependence between some speculatively
      moved load insn and this one.  */
   unsigned int fed_by_spec_load : 1;
@@ -516,14 +713,12 @@ struct haifa_insn_data
      '< 0' if priority in invalid and should be recomputed.  */
   signed char priority_status;
 
-  /* Nonzero if instruction has internal dependence
-     (e.g. add_dependence was invoked with (insn == elem)).  */
-  unsigned int has_internal_dep : 1;
-  
   /* What speculations are necessary to apply to schedule the instruction.  */
   ds_t todo_spec;
+
   /* What speculations were already applied.  */
   ds_t done_spec; 
+
   /* What speculations are checked by this instruction.  */
   ds_t check_spec;
 
@@ -534,33 +729,56 @@ struct haifa_insn_data
   rtx orig_pat;
 };
 
-extern struct haifa_insn_data *h_i_d;
+typedef struct _haifa_insn_data haifa_insn_data_def;
+typedef haifa_insn_data_def *haifa_insn_data_t;
+
+DEF_VEC_O (haifa_insn_data_def);
+DEF_VEC_ALLOC_O (haifa_insn_data_def, heap);
+
+extern VEC(haifa_insn_data_def, heap) *h_i_d;
+
+#define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN)))
 
 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
    sched-rgn.c.  */
-
-#define INSN_HARD_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].hard_back_deps)
-#define INSN_SPEC_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].spec_back_deps)
-#define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
-#define INSN_RESOLVED_BACK_DEPS(INSN) \
-  (h_i_d[INSN_UID (INSN)].resolved_back_deps)
-#define INSN_RESOLVED_FORW_DEPS(INSN) \
-  (h_i_d[INSN_UID (INSN)].resolved_forw_deps)
-#define INSN_LUID(INSN)		(h_i_d[INSN_UID (INSN)].luid)
-#define CANT_MOVE(insn)		(h_i_d[INSN_UID (insn)].cant_move)
-#define INSN_PRIORITY(INSN)	(h_i_d[INSN_UID (INSN)].priority)
-#define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status)
+#define INSN_PRIORITY(INSN) (HID (INSN)->priority)
+#define INSN_REG_WEIGHT(INSN) (HID (INSN)->reg_weight)
+#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
+
+typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def;
+typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t;
+
+DEF_VEC_O (haifa_deps_insn_data_def);
+DEF_VEC_ALLOC_O (haifa_deps_insn_data_def, heap);
+
+extern VEC(haifa_deps_insn_data_def, heap) *h_d_i_d;
+
+#define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d,	\
+			       INSN_LUID (INSN)))
+#define INSN_DEP_COUNT(INSN)	(HDID (INSN)->dep_count)
+#define HAS_INTERNAL_DEP(INSN)  (HDID (INSN)->has_internal_dep)
+#define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps)
+#define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps)
+#define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps)
+#define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps)
+#define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps)
+#define CANT_MOVE(INSN)	(HDID (INSN)->cant_move)
+#define CANT_MOVE_BY_LUID(LUID)	(VEC_index (haifa_deps_insn_data_def, h_d_i_d, \
+                                            LUID)->cant_move)
+
+
+#define INSN_PRIORITY(INSN)	(HID (INSN)->priority)
+#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status)
 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
-#define INSN_REG_WEIGHT(INSN)	(h_i_d[INSN_UID (INSN)].reg_weight)
-#define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
-#define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
-#define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
-#define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
-#define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
-#define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
+#define TODO_SPEC(INSN) (HID (INSN)->todo_spec)
+#define DONE_SPEC(INSN) (HID (INSN)->done_spec)
+#define CHECK_SPEC(INSN) (HID (INSN)->check_spec)
+#define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block)
+#define ORIG_PAT(INSN) (HID (INSN)->orig_pat)
 
 /* INSN is either a simple or a branchy speculation check.  */
-#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
+#define IS_SPECULATION_CHECK_P(INSN) \
+  (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL)
 
 /* INSN is a speculation check that will simply reexecute the speculatively
    scheduled instruction if the speculation fails.  */
@@ -706,14 +924,16 @@ enum SCHED_FLAGS {
   DO_SPECULATION = USE_DEPS_LIST << 1,
   SCHED_RGN = DO_SPECULATION << 1,
   SCHED_EBB = SCHED_RGN << 1,
-  /* Scheduler can possible create new basic blocks.  Used for assertions.  */
-  NEW_BBS = SCHED_EBB << 1
+  /* Scheduler can possibly create new basic blocks.  Used for assertions.  */
+  NEW_BBS = SCHED_EBB << 1,
+  SEL_SCHED = NEW_BBS << 1
 };
 
 enum SPEC_SCHED_FLAGS {
   COUNT_SPEC_IN_CRITICAL_PATH = 1,
   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
-  PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
+  PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1,
+  SEL_SCHED_SPEC_DONT_CHECK_CONTROL = PREFER_NON_CONTROL_SPEC << 1
 };
 
 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE)	\
@@ -803,23 +1023,104 @@ enum INSN_TRAP_CLASS
 #define HAIFA_INLINE __inline
 #endif
 
+struct sched_deps_info_def
+{
+  /* Called when computing dependencies for a JUMP_INSN.  This function
+     should store the set of registers that must be considered as set by
+     the jump in the regset.  */
+  void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
+
+  /* Start analyzing insn.  */
+  void (*start_insn) (rtx);
+
+  /* Finish analyzing insn.  */
+  void (*finish_insn) (void);
+
+  /* Start analyzing insn LHS (Left Hand Side).  */
+  void (*start_lhs) (rtx);
+
+  /* Finish analyzing insn LHS.  */
+  void (*finish_lhs) (void);
+
+  /* Start analyzing insn RHS (Right Hand Side).  */
+  void (*start_rhs) (rtx);
+
+  /* Finish analyzing insn RHS.  */
+  void (*finish_rhs) (void);
+
+  /* Note set of the register.  */
+  void (*note_reg_set) (int);
+
+  /* Note clobber of the register.  */
+  void (*note_reg_clobber) (int);
+
+  /* Note use of the register.  */
+  void (*note_reg_use) (int);
+
+  /* Note memory dependence of type DS between MEM1 and MEM2 (which is
+     in the INSN2).  */
+  void (*note_mem_dep) (rtx mem1, rtx mem2, rtx insn2, ds_t ds);
+
+  /* Note a dependence of type DS from the INSN.  */
+  void (*note_dep) (rtx insn, ds_t ds);
+
+  /* Nonzero if we should use cselib for better alias analysis.  This
+     must be 0 if the dependency information is used after sched_analyze
+     has completed, e.g. if we're using it to initialize state for successor
+     blocks in region scheduling.  */
+  unsigned int use_cselib : 1;
+
+  /* If set, generate links between instruction as DEPS_LIST.
+     Otherwise, generate usual INSN_LIST links.  */
+  unsigned int use_deps_list : 1;
+
+  /* Generate data and control speculative dependencies.
+     Requires USE_DEPS_LIST set.  */
+  unsigned int generate_spec_deps : 1;
+};
+
+extern struct sched_deps_info_def *sched_deps_info;
+
+
 /* Functions in sched-deps.c.  */
 extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx);
 extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t);
 extern void add_dependence (rtx, rtx, enum reg_note);
 extern void sched_analyze (struct deps *, rtx, rtx);
-extern bool deps_pools_are_empty_p (void);
-extern void sched_free_deps (rtx, rtx, bool);
 extern void init_deps (struct deps *);
 extern void free_deps (struct deps *);
 extern void init_deps_global (void);
 extern void finish_deps_global (void);
-extern void init_dependency_caches (int);
-extern void free_dependency_caches (void);
-extern void extend_dependency_caches (int, bool);
+extern void deps_analyze_insn (struct deps *, rtx);
+extern void remove_from_deps (struct deps *, rtx);
+
+extern dw_t get_dep_weak_1 (ds_t, ds_t);
 extern dw_t get_dep_weak (ds_t, ds_t);
 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
+extern dw_t estimate_dep_weak (rtx, rtx);
 extern ds_t ds_merge (ds_t, ds_t);
+extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx);
+extern ds_t ds_max_merge (ds_t, ds_t);
+extern dw_t ds_weak (ds_t);
+extern ds_t ds_get_speculation_types (ds_t);
+extern ds_t ds_get_max_dep_weak (ds_t);
+
+extern void sched_deps_init (bool);
+extern void sched_deps_finish (void);
+
+extern void haifa_note_reg_set (int);
+extern void haifa_note_reg_clobber (int);
+extern void haifa_note_reg_use (int);
+
+extern void maybe_extend_reg_info_p (void);
+
+extern void deps_start_bb (struct deps *, rtx);
+extern enum reg_note ds_to_dt (ds_t);
+
+extern bool deps_pools_are_empty_p (void);
+extern void sched_free_deps (rtx, rtx, bool);
+extern void extend_dependency_caches (int, bool);
+
 extern void debug_ds (ds_t);
 
 /* Functions in haifa-sched.c.  */
@@ -827,25 +1128,105 @@ extern int haifa_classify_insn (const_rtx);
 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
 extern int no_real_insns_p (const_rtx, const_rtx);
 
-extern void rm_other_notes (rtx, rtx);
-
 extern int insn_cost (rtx);
+extern int dep_cost_1 (dep_t, dw_t);
 extern int dep_cost (dep_t);
 extern int set_priorities (rtx, rtx);
 
-extern void schedule_block (basic_block *, int);
-extern void sched_init (void);
-extern void sched_finish (void);
+extern void schedule_block (basic_block *);
+
+extern int cycle_issued_insns;
+extern int issue_rate;
+extern int dfa_lookahead;
+
+extern void ready_sort (struct ready_list *);
+extern rtx ready_element (struct ready_list *, int);
+extern rtx *ready_lastpos (struct ready_list *);
 
 extern int try_ready (rtx);
-extern void * xrecalloc (void *, size_t, size_t, size_t);
+extern void sched_extend_ready_list (int);
+extern void sched_finish_ready_list (void);
+extern void sched_change_pattern (rtx, rtx);
+extern int sched_speculate_insn (rtx, ds_t, rtx *);
 extern void unlink_bb_notes (basic_block, basic_block);
 extern void add_block (basic_block, basic_block);
 extern rtx bb_note (basic_block);
+extern void concat_note_lists (rtx, rtx *);
+
 
-/* Functions in sched-rgn.c.  */
+/* Types and functions in sched-rgn.c.  */
 
+/* A region is the main entity for interblock scheduling: insns
+   are allowed to move between blocks in the same region, along
+   control flow graph edges, in the 'up' direction.  */
+typedef struct
+{
+  /* Number of extended basic blocks in region.  */
+  int rgn_nr_blocks;
+  /* cblocks in the region (actually index in rgn_bb_table).  */
+  int rgn_blocks;
+  /* Dependencies for this region are already computed.  Basically, indicates,
+     that this is a recovery block.  */
+  unsigned int dont_calc_deps : 1;
+  /* This region has at least one non-trivial ebb.  */
+  unsigned int has_real_ebb : 1;
+}
+region;
+
+extern int nr_regions;
+extern region *rgn_table;
+extern int *rgn_bb_table;
+extern int *block_to_bb;
+extern int *containing_rgn;
+
+#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks)
+#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks)
+#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps)
+#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb)
+#define BLOCK_TO_BB(block) (block_to_bb[block])
+#define CONTAINING_RGN(block) (containing_rgn[block])
+
+/* The mapping from ebb to block.  */
+extern int *ebb_head;
+#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]])
+#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb))
+#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1])
+#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN)))
+
+extern int current_nr_blocks;
+extern int current_blocks;
+extern int target_bb;
+
+extern bool sched_is_disabled_for_current_region_p (void);
+extern void sched_rgn_init (bool);
+extern void sched_rgn_finish (void);
+extern void rgn_setup_region (int);
+extern void sched_rgn_compute_dependencies (int);
+extern void sched_rgn_local_init (int);
+extern void sched_rgn_local_finish (void);
+extern void sched_rgn_local_free (void);
+extern void extend_regions (void);
+extern void rgn_make_new_region_out_of_new_block (basic_block);
+
+extern void compute_priorities (void);
+extern void increase_insn_priority (rtx, int);
+extern void debug_rgn_dependencies (int);
 extern void debug_dependencies (rtx, rtx);
+extern void free_rgn_deps (void);          
+extern int contributes_to_priority (rtx, rtx);
+extern void extend_rgns (int *, int *, sbitmap, int *);
+extern void deps_join (struct deps *, struct deps *);
+
+extern void rgn_setup_common_sched_info (void);
+extern void rgn_setup_sched_infos (void);
+
+extern void debug_regions (void);
+extern void debug_region (int);
+extern void dump_region_dot (FILE *, int);
+extern void dump_region_dot_file (const char *, int);
+
+extern void haifa_sched_init (void);
+extern void haifa_sched_finish (void);
 
 /* sched-deps.c interface to walk, add, search, update, resolve, delete
    and debug instruction dependencies.  */