* sched-int.h (struct _dep): Rename field 'kind' to 'type'.

	(DEP_KIND): Rename to DEP_TYPE.  Update all uses.
	(dep_def): New typedef.
	(init_dep_1, sd_debug_dep): Declare functions.
	(DEP_LINK_KIND): Rename to DEP_LINK_TYPE.
	(debug_dep_links): Remove.
	(struct _deps_list): New field 'n_links'.
	(DEPS_LIST_N_LINKS): New macro.
	(FOR_EACH_DEP_LINK): Remove.
	(create_deps_list, free_deps_list, delete_deps_list): Remove
	declaration.
	(deps_list_empty_p, debug_deps_list, add_back_dep_to_deps_list): Ditto.
	(find_link_by_pro_in_deps_list, find_link_by_con_in_deps_list): Ditto.
	(copy_deps_list_change_con, move_dep_link): Ditto.
	(struct haifa_insn_data): Split field 'back_deps' into 'hard_back_deps'
	and 'spec_back_deps'.  New field 'resolved_forw_deps'.  Remove field
	'dep_count'.
	(INSN_BACK_DEPS): Remove.
	(INSN_HARD_BACK_DEPS, INSN_SPEC_BACK_DEPS, INSN_RESOLVED_FORW_DEPS):
	New macros.
	(INSN_DEP_COUNT): Remove.
	(enum DEPS_ADJUST_RESULT): Add new constant DEP_NODEP.  Fix comments.
	(spec_info, haifa_recovery_block_was_added_during_scheduling_p):
	Declare global variables.
	(deps_pools_are_empty_p, sched_free_deps): Declare functions.
	(add_forw_dep, compute_forward_dependences): Remove declarations.
	(add_or_update_back_dep, add_or_update_back_forw_dep): Ditto.
	(add_back_forw_dep, delete_back_forw_dep): Ditto.
	(debug_ds, sched_insn_is_legitimate_for_speculation_p): Declare
	functions.
	(SD_LIST_NONE, SD_LIST_HARD_BACK, SD_LIST_SPEC_BACK, SD_LIST_FORW): New
	constants.
	(SD_LIST_RES_BACK, SD_LIST_RES_FORW, SD_LIST_BACK): Ditto.
	(sd_list_types_def): New typedef.
	(sd_next_list): Declare function.
	(struct _sd_iterator): New type.
	(sd_iterator_def): New typedef.
	(sd_iterator_start, sd_iterator_cond, sd_iterator_next): New inline
	functions.
	(FOR_EACH_DEP): New cycle wrapper.
	(sd_lists_size, sd_lists_empty_p, sd_init_insn, sd_finish_insn):
	Declare functions.
	(sd_find_dep_between, sd_add_dep, sd_add_or_update_dep): Ditto.
	(sd_resolve_dep, sd_copy_back_deps, sd_delete_dep, sd_debug_lists):
	Ditto.

	* sched-deps.c (init_dep_1): Make global.
	(DUMP_DEP_PRO, DUMP_DEP_CON, DUMP_DEP_STATUS, DUMP_DEP_ALL): New
	constants.
	(dump_dep): New static function.
	(dump_dep_flags): New static variable.
	(sd_debug_dep): New function.
	(add_to_deps_list, remove_from_deps_list): Update 'n_links' field of
	the list.
	(move_dep_link): Use remove_from_deps_list (), instead of
	detach_dep_link ().
	(dep_links_consistent_p, dump_dep_links, debug_dep_links): Remove.
	(dep_link_is_detached_p): New static function.
	(deps_obstack, dl_obstack, dn_obstack): Remove.  Use dn_pool, dl_pool
	instead.
	(dn_pool, dl_pool): New alloc_pools.
	(dn_pool_diff, dl_pool_diff): New static variables.
	(create_dep_node, delete_dep_node): New static function.
	(create_deps_list): Make it static.  Use alloc_pool 'dl_pool'.
	(deps_list_empty_p): Make it static.  Use 'n_links' field.
	(deps_pools_are_empty_p): New static function.
	(alloc_deps_list, delete_deps_list): Remove.
	(dump_deps_list, debug_deps_list, add_back_dep_to_deps_list): Remove.
	(find_link_by_pro_in_deps_list, find_link_by_con_in_deps_list): Ditto.
	(copy_deps_list_change_con): Remove.  Use sd_copy_back_deps () instead.
	(forward_dependency_cache): Remove.
	(maybe_add_or_update_back_dep_1, add_or_update_back_dep_1): Remove
	'back' from the names.  Change signature to use dep_t instead of
	equivalent quad.
	(add_back_dep): Ditto.  Make global.
	(check_dep_status): Rename to check_dep ().
	(sd_next_list, sd_lists_size, sd_lists_empty_p, sd_init_insn):
	New functions.
	(sd_finish_insn): Ditto.
	(sd_find_dep_between_no_cache): New static function.
	(sd_find_dep_between): New function.
	(ask_dependency_caches, set_dependency_caches): New static functions.
	(update_dependency_caches, change_spec_dep_to_hard, update_dep): Ditto.
	(add_or_update_dep_1): Separate pieces of functionality into
	ask_dependency_caches (), update_dependency_caches (),
	change_spec_dep_to_hard (), update_dep ().
	(get_back_and_forw_lists): New static function.
	(sd_add_dep): Separate setting of dependency caches into
	set_dependency_caches ().
	(sd_add_or_update_dep, sd_resolve_dep, sd_copy_back_deps):
	New functions.
	(sd_delete_dep): Ditto.
	(DUMP_LISTS_SIZE, DUMP_LISTS_DEPS, DUMP_LISTS_ALL): New constants.
	(dump_lists): New static function.
	(sd_debug_lists): New debug function.
	(delete_all_dependences, fixup_sched_groups): Update to use
	sd_* infrastructure.
	(sched_analyze_2): Create data-speculative dependency only if
	data-speculation is enabled.
	(sched_analyze_insn): If insn cannot be speculative, make all its
	dependencies non-speculative.
	(sched_analyze): Use sd_init_insn ().
	(add_forw_dep, compute_forward_dependencies): Remove.
	(delete_dep_nodes_in_back_deps): New static function.
	(sched_free_deps): New function.
	(init_dependency_caches): Init alloc_pools.
	(extend_depedency_caches): Update after removing of
	forward_dependency_cache.
	(free_dependency_caches): Ditto.  Free alloc_pools.
	(adjust_add_sorted_back_dep, adjust_back_add_forw_dep): Remove.
	(delete_forw_dep, add_or_update_back_dep, add_or_update_back_forw_dep):
	Ditto.
	(add_back_forw_dep, delete_back_forw_dep): Ditto.
	(add_dependence): Use init_dep ().
	(get_dep_weak_1): New static function.
	(get_dep_weak): Move logic to get_dep_weak_1 ().
	(dump_ds): New static function moved from haifa-sched.c:
	debug_spec_status ().
	(debug_ds): New debug function.
	(check_dep_status): Rename to check_dep ().  Update to check whole
	dependencies.

	* haifa-sched.c (spec_info): Make global.
	(added_recovery_block_p): Rename to
	'haifa_recovery_block_was_added_during_current_schedule_block_p'.
	(haifa_recovery_block_was_added_during_scheduling_p): New variable.
	(dep_cost, priority, rank_for_schedule, schedule_insn): Update
	to use new interfaces.
	(ok_for_early_queue_removal): Ditto.
	(schedule_block): Initialize logical uids of insns emitted by the
	target.
	(sched_init): Initialize new variable.
	(fix_inter_tick, try_ready, fix_tick_ready): Update to use new
	interfaces.
	(extend_global): Initialize insn data.
	(init_h_i_d): Remove code that is now handled in sd_init_insn ().
	(process_insn_forw_deps_be_in_spec): Change signature.  Update to use
	new interfaces.
	(add_to_speculative_block): Update to use new interfaces.
	(create_recovery_block): Set new variables.
	(create_check_block_twin, fix_recovery_deps): Update to use new
	interfaces.
	(sched_insn_is_legitimate_for_speculation_p): New function.
	(speculate_insn): Move checking logic to
	sched_insn_is_legitimate_for_speculation_p ().
	(sched_remove_insn): Finalize sched-deps information of instruction.
	(clear_priorities, add_jump_dependencies): Update to use new
	interfaces.
	(debug_spec_status): Rename to dump_ds () and move to sched-deps.c.
	
	* sched-rgn.c (set_spec_fed, find_conditional_protection): Update
	to use new interfaces.
	(is_conditionally_protected, is_pfree, is_prisky) Ditto.
	(new_ready): Try to use control speculation only if it is available.
	(add_branch_dependences): Update to use new interfaces.
	(compute_block_backward_dependences): Rename to
	compute_block_dependences ().  Call
	targetm.sched.dependencies_evaluation_hook ().
	(free_block_dependencies): New static function.
	(debug_dependencies): Update to use new interfaces.
	(schedule_region): Remove separate computation of forward dependencies.
	Move call of targetm.sched.dependencies_evaluation_hook () to
	compute_block_dependences ().  Free dependencies at the end of
	scheduling the region.

	* sched-ebb.c (earliest_block_with_similiar_load): Update to use
	new interfaces.
	(add_deps_for_risky_insns): Ditto.
	(schedule_ebb): Remove separate computation of forward dependencies.
	Free dependencies at the end of	scheduling the ebb.

	* ddg.c (create_ddg_dependence): Update to use new interfaces.
	(build_intra_loop_deps): Ditto.  Remove separate computation of forward
	dependencies.  Free sched-deps dependencies.

	* config/ia64/ia64.c (ia64_dependencies_evaluation_hook): Update
	to use new interfaces.
	(ia64_dfa_new_cycle, ia64_gen_check): Ditto.

	* config/rs6000/rs6000.c (rs6000_is_costly_dependence): Update to use
	new interfaces.
	(is_costly_group): Ditto.


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

1 files changed, 309 insertions, 279 deletions

diff --git a/gcc/haifa-sched.c b/gcc/haifa-sched.c
index d5bd29cc4ce..d9a8f782a64 100644
--- a/gcc/haifa-sched.c
+++ b/gcc/haifa-sched.c
@@ -206,11 +206,16 @@ static rtx note_list;
 static struct spec_info_def spec_info_var;
 /* Description of the speculative part of the scheduling.
    If NULL - no speculation.  */
-static spec_info_t spec_info;
+spec_info_t spec_info;
 
 /* True, if recovery block was added during scheduling of current block.
    Used to determine, if we need to fix INSN_TICKs.  */
-static bool added_recovery_block_p;
+static bool haifa_recovery_bb_recently_added_p;
+
+/* True, if recovery block was added during this scheduling pass.
+   Used to determine if we should have empty memory pools of dependencies
+   after finishing current region.  */
+bool haifa_recovery_bb_ever_added_p;
 
 /* Counters of different types of speculative instructions.  */
 static int nr_begin_data, nr_be_in_data, nr_begin_control, nr_be_in_control;
@@ -553,7 +558,7 @@ static void extend_global (rtx);
 static void extend_all (rtx);
 static void init_h_i_d (rtx);
 static void generate_recovery_code (rtx);
-static void process_insn_forw_deps_be_in_spec (deps_list_t, rtx, ds_t);
+static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t);
 static void begin_speculative_block (rtx);
 static void add_to_speculative_block (rtx);
 static dw_t dep_weak (ds_t);
@@ -654,7 +659,7 @@ dep_cost (dep_t link)
   else
     {
       rtx insn = DEP_PRO (link);
-      enum reg_note dep_type = DEP_KIND (link);
+      enum reg_note dep_type = DEP_TYPE (link);
 
       cost = insn_cost (insn);
 
@@ -684,7 +689,7 @@ dep_cost (dep_t link)
 	  XEXP (dep_cost_rtx_link, 1) = dep_cost_rtx_link;
 
 	  /* Targets use only REG_NOTE_KIND of the link.  */
-	  PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_KIND (link));
+	  PUT_REG_NOTE_KIND (dep_cost_rtx_link, DEP_TYPE (link));
 
 	  cost = targetm.sched.adjust_cost (used, dep_cost_rtx_link,
 					    insn, cost);
@@ -726,8 +731,6 @@ contributes_to_priority_p (dep_t dep)
 static int
 priority (rtx insn)
 {
-  dep_link_t link;
-
   if (! INSN_P (insn))
     return 0;
 
@@ -738,7 +741,7 @@ priority (rtx insn)
     {
       int this_priority = 0;
 
-      if (deps_list_empty_p (INSN_FORW_DEPS (insn)))
+      if (sd_lists_empty_p (insn, SD_LIST_FORW))
 	/* ??? We should set INSN_PRIORITY to insn_cost when and insn has
 	   some forward deps but all of them are ignored by
 	   contributes_to_priority hook.  At the moment we set priority of
@@ -769,11 +772,13 @@ priority (rtx insn)
 
 	  do
 	    {
-	      FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (twin))
+	      sd_iterator_def sd_it;
+	      dep_t dep;
+
+	      FOR_EACH_DEP (twin, SD_LIST_FORW, sd_it, dep)
 		{
 		  rtx next;
 		  int next_priority;
-		  dep_t dep = DEP_LINK_DEP (link);
 
 		  next = DEP_CON (dep);
 
@@ -832,7 +837,6 @@ rank_for_schedule (const void *x, const void *y)
 {
   rtx tmp = *(const rtx *) y;
   rtx tmp2 = *(const rtx *) x;
-  dep_link_t link1, link2;
   int tmp_class, tmp2_class;
   int val, priority_val, weight_val, info_val;
 
@@ -885,31 +889,30 @@ rank_for_schedule (const void *x, const void *y)
   /* Compare insns based on their relation to the last-scheduled-insn.  */
   if (INSN_P (last_scheduled_insn))
     {
+      dep_t dep1;
+      dep_t dep2;
+
       /* Classify the instructions into three classes:
          1) Data dependent on last schedule insn.
          2) Anti/Output dependent on last scheduled insn.
          3) Independent of last scheduled insn, or has latency of one.
          Choose the insn from the highest numbered class if different.  */
-      link1
-	= find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn),
-					 tmp);
+      dep1 = sd_find_dep_between (last_scheduled_insn, tmp, true);
 
-      if (link1 == NULL || dep_cost (DEP_LINK_DEP (link1)) == 1)
+      if (dep1 == NULL || dep_cost (dep1) == 1)
 	tmp_class = 3;
       else if (/* Data dependence.  */
-	       DEP_LINK_KIND (link1) == REG_DEP_TRUE)
+	       DEP_TYPE (dep1) == REG_DEP_TRUE)
 	tmp_class = 1;
       else
 	tmp_class = 2;
 
-      link2
-	= find_link_by_con_in_deps_list (INSN_FORW_DEPS (last_scheduled_insn),
-					 tmp2);
+      dep2 = sd_find_dep_between (last_scheduled_insn, tmp2, true);
 
-      if (link2 == NULL || dep_cost (DEP_LINK_DEP (link2))  == 1)
+      if (dep2 == NULL || dep_cost (dep2)  == 1)
 	tmp2_class = 3;
       else if (/* Data dependence.  */
-	       DEP_LINK_KIND (link2) == REG_DEP_TRUE)
+	       DEP_TYPE (dep2) == REG_DEP_TRUE)
 	tmp2_class = 1;
       else
 	tmp2_class = 2;
@@ -922,21 +925,11 @@ rank_for_schedule (const void *x, const void *y)
      This gives the scheduler more freedom when scheduling later
      instructions at the expense of added register pressure.  */
 
-  link1 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp));
-  link2 = DEPS_LIST_FIRST (INSN_FORW_DEPS (tmp2));
+  val = (sd_lists_size (tmp2, SD_LIST_FORW)
+	 - sd_lists_size (tmp, SD_LIST_FORW));
 
-  while (link1 != NULL && link2 != NULL)
-    {
-      link1 = DEP_LINK_NEXT (link1);
-      link2 = DEP_LINK_NEXT (link2);
-    }
-
-  if (link1 != NULL && link2 == NULL)
-    /* TMP (Y) has more insns that depend on it.  */
-    return -1;
-  if (link1 == NULL && link2 != NULL)
-    /* TMP2 (X) has more insns that depend on it.  */
-    return 1;
+  if (val != 0)
+    return val;
 
   /* If insns are equally good, sort by INSN_LUID (original insn order),
      so that we make the sort stable.  This minimizes instruction movement,
@@ -1172,7 +1165,8 @@ static int last_clock_var;
 static int
 schedule_insn (rtx insn)
 {
-  dep_link_t link;
+  sd_iterator_def sd_it;
+  dep_t dep;
   int advance = 0;
 
   if (sched_verbose >= 1)
@@ -1192,12 +1186,7 @@ schedule_insn (rtx insn)
 
   /* Scheduling instruction should have all its dependencies resolved and
      should have been removed from the ready list.  */
-  gcc_assert (INSN_DEP_COUNT (insn) == 0
-	      && deps_list_empty_p (INSN_BACK_DEPS (insn)));
-  free_deps_list (INSN_BACK_DEPS (insn));
-
-  /* Now we can free INSN_RESOLVED_BACK_DEPS list.  */
-  delete_deps_list (INSN_RESOLVED_BACK_DEPS (insn));
+  gcc_assert (sd_lists_empty_p (insn, SD_LIST_BACK));
 
   gcc_assert (QUEUE_INDEX (insn) == QUEUE_NOWHERE);
   QUEUE_INDEX (insn) = QUEUE_SCHEDULED;
@@ -1213,19 +1202,15 @@ schedule_insn (rtx insn)
   INSN_TICK (insn) = clock_var;
 
   /* Update dependent instructions.  */
-  FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (insn))
+  for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+       sd_iterator_cond (&sd_it, &dep);)
     {
-      rtx next = DEP_LINK_CON (link);
-
-      /* Resolve the dependence between INSN and NEXT.  */
-
-      INSN_DEP_COUNT (next)--;
+      rtx next = DEP_CON (dep);
 
-      move_dep_link (DEP_NODE_BACK (DEP_LINK_NODE (link)),
-			INSN_RESOLVED_BACK_DEPS (next));
-
-      gcc_assert ((INSN_DEP_COUNT (next) == 0)
-		  == deps_list_empty_p (INSN_BACK_DEPS (next)));
+      /* Resolve the dependence between INSN and NEXT.
+	 sd_resolve_dep () moves current dep to another list thus
+	 advancing the iterator.  */
+      sd_resolve_dep (sd_it);
 
       if (!IS_SPECULATION_BRANCHY_CHECK_P (insn))
 	{
@@ -1242,11 +1227,23 @@ schedule_insn (rtx insn)
 	/* Check always has only one forward dependence (to the first insn in
 	   the recovery block), therefore, this will be executed only once.  */
 	{
-	  gcc_assert (DEP_LINK_NEXT (link) == NULL);
+	  gcc_assert (sd_lists_empty_p (insn, SD_LIST_FORW));
 	  fix_recovery_deps (RECOVERY_BLOCK (insn));
 	}
     }
 
+  /* This is the place where scheduler doesn't *basically* need backward and
+     forward dependencies for INSN anymore.  Nevertheless they are used in
+     heuristics in rank_for_schedule (), early_queue_to_ready () and in
+     some targets (e.g. rs6000).  Thus the earliest place where we *can*
+     remove dependencies is after targetm.sched.md_finish () call in
+     schedule_block ().  But, on the other side, the safest place to remove
+     dependencies is when we are finishing scheduling entire region.  As we
+     don't generate [many] dependencies during scheduling itself, we won't
+     need memory until beginning of next region.
+     Bottom line: Dependencies are removed for all insns in the end of
+     scheduling the region.  */
+
   /* Annotate the instruction with issue information -- TImode
      indicates that the instruction is expected not to be able
      to issue on the same cycle as the previous insn.  A machine
@@ -1589,15 +1586,12 @@ ok_for_early_queue_removal (rtx insn)
 
 	      if (!NOTE_P (prev_insn))
 		{
-		  dep_link_t dep_link;
+		  dep_t dep;
 
-		  dep_link = (find_link_by_con_in_deps_list
-			      (INSN_FORW_DEPS (prev_insn), insn));
+		  dep = sd_find_dep_between (prev_insn, insn, true);
 
-		  if (dep_link)
+		  if (dep != NULL)
 		    {
-		      dep_t dep = DEP_LINK_DEP (dep_link);
-
 		      cost = dep_cost (dep);
 
 		      if (targetm.sched.is_costly_dependence (dep, cost,
@@ -2148,7 +2142,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1)
 
   gcc_assert (head != tail || INSN_P (head));
 
-  added_recovery_block_p = false;
+  haifa_recovery_bb_recently_added_p = false;
 
   /* Debug info.  */
   if (sched_verbose)
@@ -2539,7 +2533,7 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1)
     }
 
   if (!current_sched_info->queue_must_finish_empty
-      || added_recovery_block_p)
+      || haifa_recovery_bb_recently_added_p)
     {
       /* INSN_TICK (minimum clock tick at which the insn becomes
          ready) may be not correct for the insn in the subsequent
@@ -2551,7 +2545,15 @@ schedule_block (basic_block *target_bb, int rgn_n_insns1)
     }
 
   if (targetm.sched.md_finish)
-    targetm.sched.md_finish (sched_dump, sched_verbose);
+    {
+      targetm.sched.md_finish (sched_dump, sched_verbose);
+
+      /* Target might have added some instructions to the scheduled block.
+	 in its md_finish () hook.  These new insns don't have any data
+	 initialized and to identify them we extend h_i_d so that they'll
+	 get zero luids.*/
+      extend_h_i_d ();
+    }
 
   /* Update head/tail boundaries.  */
   head = NEXT_INSN (prev_head);
@@ -2759,6 +2761,8 @@ sched_init (void)
   nr_begin_data = nr_begin_control = nr_be_in_data = nr_be_in_control = 0;
   before_recovery = 0;
 
+  haifa_recovery_bb_ever_added_p = false;
+
 #ifdef ENABLE_CHECKING
   /* This is used preferably for finding bugs in check_cfg () itself.  */
   check_cfg (0, 0);
@@ -2817,6 +2821,10 @@ fix_inter_tick (rtx head, rtx tail)
 {
   /* Set of instructions with corrected INSN_TICK.  */
   bitmap_head processed;
+  /* ??? It is doubtful if we should assume that cycle advance happens on
+     basic block boundaries.  Basically insns that are unconditionally ready
+     on the start of the block are more preferable then those which have
+     a one cycle dependency over insn from the previous block.  */
   int next_clock = clock_var + 1;
 
   bitmap_initialize (&processed, 0);
@@ -2829,7 +2837,8 @@ fix_inter_tick (rtx head, rtx tail)
       if (INSN_P (head))
 	{
 	  int tick;
-	  dep_link_t link;
+	  sd_iterator_def sd_it;
+	  dep_t dep;
                   
 	  tick = INSN_TICK (head);
 	  gcc_assert (tick >= MIN_TICK);
@@ -2846,11 +2855,11 @@ fix_inter_tick (rtx head, rtx tail)
 	      INSN_TICK (head) = tick;		 
 	    }
 	  
-	  FOR_EACH_DEP_LINK (link, INSN_FORW_DEPS (head))
+	  FOR_EACH_DEP (head, SD_LIST_RES_FORW, sd_it, dep)
 	    {
 	      rtx next;
 	      
-	      next = DEP_LINK_CON (link);
+	      next = DEP_CON (dep);
 	      tick = INSN_TICK (next);
 
 	      if (tick != INVALID_TICK
@@ -2869,7 +2878,7 @@ fix_inter_tick (rtx head, rtx tail)
 		    INTER_TICK (next) = tick;
 		  else
 		    tick = INTER_TICK (next);
-		  
+
 		  INSN_TICK (next) = tick;
 		}
 	    }
@@ -2888,7 +2897,6 @@ int
 try_ready (rtx next)
 {  
   ds_t old_ts, *ts;
-  dep_link_t link;
 
   ts = &TODO_SPEC (next);
   old_ts = *ts;
@@ -2897,44 +2905,52 @@ try_ready (rtx next)
 	      && ((old_ts & HARD_DEP)
 		  || (old_ts & SPECULATIVE)));
   
-  if (!(current_sched_info->flags & DO_SPECULATION))
+  if (sd_lists_empty_p (next, SD_LIST_BACK))
+    /* NEXT has all its dependencies resolved.  */
     {
-      if (deps_list_empty_p (INSN_BACK_DEPS (next)))
-        *ts &= ~HARD_DEP;
+      /* Remove HARD_DEP bit from NEXT's status.  */
+      *ts &= ~HARD_DEP;
+
+      if (current_sched_info->flags & DO_SPECULATION)
+	/* Remove all speculative bits from NEXT's status.  */
+	*ts &= ~SPECULATIVE;
     }
   else
     {
+      /* One of the NEXT's dependencies has been resolved.
+	 Recalcute NEXT's status.  */
+
       *ts &= ~SPECULATIVE & ~HARD_DEP;
 
-      link = DEPS_LIST_FIRST (INSN_BACK_DEPS (next));
+      if (sd_lists_empty_p (next, SD_LIST_HARD_BACK))
+	/* Now we've got NEXT with speculative deps only.
+	   1. Look at the deps to see what we have to do.
+	   2. Check if we can do 'todo'.  */
+	{
+	  sd_iterator_def sd_it;
+	  dep_t dep;
+	  bool first_p = true;
 
-      if (link != NULL)
-        {
-	  ds_t ds = DEP_LINK_STATUS (link) & SPECULATIVE;
-
-          /* Backward dependencies of the insn are maintained sorted. 
-             So if DEP_STATUS of the first dep is SPECULATIVE,
-             than all other deps are speculative too.  */
-          if (ds != 0)
-            {          
-              /* Now we've got NEXT with speculative deps only.
-                 1. Look at the deps to see what we have to do.
-                 2. Check if we can do 'todo'.  */
-	      *ts = ds;
-
-              while ((link = DEP_LINK_NEXT (link)) != NULL)
+	  FOR_EACH_DEP (next, SD_LIST_BACK, sd_it, dep)
+	    {
+	      ds_t ds = DEP_STATUS (dep) & SPECULATIVE;
+
+	      if (first_p)
 		{
-		  ds = DEP_LINK_STATUS (link) & SPECULATIVE;
-		  *ts = ds_merge (*ts, ds);
-		}
+		  first_p = false;
 
-	      if (dep_weak (*ts) < spec_info->weakness_cutoff)
-		/* Too few points.  */
-		*ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+		  *ts = ds;
+		}
+	      else
+		*ts = ds_merge (*ts, ds);
 	    }
-          else
-            *ts |= HARD_DEP;
-        }
+
+	  if (dep_weak (*ts) < spec_info->weakness_cutoff)
+	    /* Too few points.  */
+	    *ts = (*ts & ~SPECULATIVE) | HARD_DEP;
+	}
+      else
+	*ts |= HARD_DEP;
     }
 
   if (*ts & HARD_DEP)
@@ -3053,10 +3069,11 @@ fix_tick_ready (rtx next)
 {
   int tick, delay;
 
-  if (!deps_list_empty_p (INSN_RESOLVED_BACK_DEPS (next)))
+  if (!sd_lists_empty_p (next, SD_LIST_RES_BACK))
     {
       int full_p;
-      dep_link_t link;
+      sd_iterator_def sd_it;
+      dep_t dep;
 
       tick = INSN_TICK (next);
       /* if tick is not equal to INVALID_TICK, then update
@@ -3064,9 +3081,8 @@ fix_tick_ready (rtx next)
 	 cost.  Otherwise, recalculate from scratch.  */
       full_p = (tick == INVALID_TICK);
 
-      FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (next))
+      FOR_EACH_DEP (next, SD_LIST_RES_BACK, sd_it, dep)
         {       
-	  dep_t dep = DEP_LINK_DEP (link);
           rtx pro = DEP_PRO (dep);
           int tick1;
               
@@ -3180,11 +3196,18 @@ static void
 extend_global (rtx insn)
 {
   gcc_assert (INSN_P (insn));
+
   /* These structures have scheduler scope.  */
+
+  /* Init h_i_d.  */
   extend_h_i_d ();
   init_h_i_d (insn);
 
-  extend_dependency_caches (1, 0);
+  /* Init data handled in sched-deps.c.  */
+  sd_init_insn (insn);
+
+  /* Extend dependency caches by one element.  */
+  extend_dependency_caches (1, false);
 }
 
 /* Extends global and local scheduler structures to include information
@@ -3212,14 +3235,6 @@ init_h_i_d (rtx insn)
   INSN_TICK (insn) = INVALID_TICK;
   INTER_TICK (insn) = INVALID_TICK;
   find_insn_reg_weight1 (insn);
-
-  /* These two lists will be freed in schedule_insn ().  */
-  INSN_BACK_DEPS (insn) = create_deps_list (false);
-  INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list (false);
-
-  /* This one should be allocated on the obstack because it should live till
-     the scheduling ends.  */
-  INSN_FORW_DEPS (insn) = create_deps_list (true);
 }
 
 /* Generates recovery code for INSN.  */
@@ -3240,18 +3255,19 @@ generate_recovery_code (rtx insn)
    Tries to add speculative dependencies of type FS between instructions
    in deps_list L and TWIN.  */
 static void
-process_insn_forw_deps_be_in_spec (deps_list_t l, rtx twin, ds_t fs)
+process_insn_forw_deps_be_in_spec (rtx insn, rtx twin, ds_t fs)
 {
-  dep_link_t link;
+  sd_iterator_def sd_it;
+  dep_t dep;
 
-  FOR_EACH_DEP_LINK (link, l)
+  FOR_EACH_DEP (insn, SD_LIST_FORW, sd_it, dep)
     {
       ds_t ds;
       rtx consumer;
 
-      consumer = DEP_LINK_CON (link);
+      consumer = DEP_CON (dep);
 
-      ds = DEP_LINK_STATUS (link);
+      ds = DEP_STATUS (dep);
 
       if (/* If we want to create speculative dep.  */
 	  fs
@@ -3278,7 +3294,12 @@ process_insn_forw_deps_be_in_spec (deps_list_t l, rtx twin, ds_t fs)
 	    ds |= fs;
 	}
 
-      add_back_forw_dep (consumer, twin, DEP_LINK_KIND (link), ds);
+      {
+	dep_def _new_dep, *new_dep = &_new_dep;
+
+	init_dep_1 (new_dep, twin, consumer, DEP_TYPE (dep), ds);
+	sd_add_dep (new_dep, false);
+      }
     }
 }
 
@@ -3301,7 +3322,8 @@ static void
 add_to_speculative_block (rtx insn)
 {
   ds_t ts;
-  dep_link_t link;
+  sd_iterator_def sd_it;
+  dep_t dep;
   rtx twins = NULL;
   rtx_vec_t priorities_roots;
 
@@ -3319,50 +3341,52 @@ add_to_speculative_block (rtx insn)
   DONE_SPEC (insn) |= ts;
 
   /* First we convert all simple checks to branchy.  */
-  for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
+  for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+       sd_iterator_cond (&sd_it, &dep);)
     {
-      rtx check = DEP_LINK_PRO (link);
+      rtx check = DEP_PRO (dep);
 
       if (IS_SPECULATION_SIMPLE_CHECK_P (check))
 	{
 	  create_check_block_twin (check, true);
 
 	  /* Restart search.  */
-	  link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
+	  sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
 	}
       else
 	/* Continue search.  */
-	link = DEP_LINK_NEXT (link);
+	sd_iterator_next (&sd_it);
     }
 
   priorities_roots = NULL;
   clear_priorities (insn, &priorities_roots);
- 
-  do
+
+  while (1)
     {
-      dep_link_t link;
       rtx check, twin;
       basic_block rec;
 
-      link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
+      /* Get the first backward dependency of INSN.  */
+      sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+      if (!sd_iterator_cond (&sd_it, &dep))
+	/* INSN has no backward dependencies left.  */
+	break;
 
-      gcc_assert ((DEP_LINK_STATUS (link) & BEGIN_SPEC) == 0
-		  && (DEP_LINK_STATUS (link) & BE_IN_SPEC) != 0
-		  && (DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+      gcc_assert ((DEP_STATUS (dep) & BEGIN_SPEC) == 0
+		  && (DEP_STATUS (dep) & BE_IN_SPEC) != 0
+		  && (DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
 
-      check = DEP_LINK_PRO (link);
+      check = DEP_PRO (dep);
 
       gcc_assert (!IS_SPECULATION_CHECK_P (check) && !ORIG_PAT (check)
 		  && QUEUE_INDEX (check) == QUEUE_NOWHERE);
-      
+
       rec = BLOCK_FOR_INSN (check);
-      
+
       twin = emit_insn_before (copy_insn (PATTERN (insn)), BB_END (rec));
       extend_global (twin);
 
-      copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin),
-				 INSN_RESOLVED_BACK_DEPS (insn),
-				 twin);
+      sd_copy_back_deps (twin, insn, true);
 
       if (sched_verbose && spec_info->dump)
         /* INSN_BB (insn) isn't determined for twin insns yet.
@@ -3374,47 +3398,38 @@ add_to_speculative_block (rtx insn)
 
       /* Add dependences between TWIN and all appropriate
 	 instructions from REC.  */
-      do
-	{	  
-	  add_back_forw_dep (twin, check, REG_DEP_TRUE, DEP_TRUE);
-	  
-	  do	    	  
-	    {  
-	      link = DEP_LINK_NEXT (link);
+      FOR_EACH_DEP (insn, SD_LIST_SPEC_BACK, sd_it, dep)
+	{
+	  rtx pro = DEP_PRO (dep);
 
-	      if (link != NULL)
-		{
-		  check = DEP_LINK_PRO (link);
-		  if (BLOCK_FOR_INSN (check) == rec)
-		    break;
-		}
-	      else
-		break;
+	  gcc_assert (DEP_TYPE (dep) == REG_DEP_TRUE);
+
+	  /* INSN might have dependencies from the instructions from
+	     several recovery blocks.  At this iteration we process those
+	     producers that reside in REC.  */
+	  if (BLOCK_FOR_INSN (pro) == rec)
+	    {
+	      dep_def _new_dep, *new_dep = &_new_dep;
+
+	      init_dep (new_dep, pro, twin, REG_DEP_TRUE);
+	      sd_add_dep (new_dep, false);
 	    }
-	  while (1);
 	}
-      while (link != NULL);
 
-      process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, ts);
+      process_insn_forw_deps_be_in_spec (insn, twin, ts);
 
       /* Remove all dependencies between INSN and insns in REC.  */
-      for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
+      for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+	   sd_iterator_cond (&sd_it, &dep);)
 	{
-	  check = DEP_LINK_PRO (link);
-
-	  if (BLOCK_FOR_INSN (check) == rec)
-	    {
-	      delete_back_forw_dep (link);
+	  rtx pro = DEP_PRO (dep);
 
-	      /* Restart search.  */
-	      link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
-	    }
+	  if (BLOCK_FOR_INSN (pro) == rec)
+	    sd_delete_dep (sd_it);
 	  else
-	    /* Continue search.  */
-	    link = DEP_LINK_NEXT (link);
+	    sd_iterator_next (&sd_it);
 	}
     }
-  while (!deps_list_empty_p (INSN_BACK_DEPS (insn)));
 
   /* We couldn't have added the dependencies between INSN and TWINS earlier
      because that would make TWINS appear in the INSN_BACK_DEPS (INSN).  */
@@ -3423,7 +3438,13 @@ add_to_speculative_block (rtx insn)
       rtx twin;
 
       twin = XEXP (twins, 0);
-      add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
+
+      {
+	dep_def _new_dep, *new_dep = &_new_dep;
+
+	init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
+	sd_add_dep (new_dep, false);
+      }
 
       twin = XEXP (twins, 1);
       free_INSN_LIST_node (twins);
@@ -3579,7 +3600,8 @@ create_recovery_block (void)
   rtx barrier;
   basic_block rec;
   
-  added_recovery_block_p = true;
+  haifa_recovery_bb_recently_added_p = true;
+  haifa_recovery_bb_ever_added_p = true;
 
   if (!before_recovery)
     init_before_recovery ();
@@ -3613,8 +3635,10 @@ create_check_block_twin (rtx insn, bool mutate_p)
 {
   basic_block rec;
   rtx label, check, twin;
-  dep_link_t link;
   ds_t fs;
+  sd_iterator_def sd_it;
+  dep_t dep;
+  dep_def _new_dep, *new_dep = &_new_dep;
 
   gcc_assert (ORIG_PAT (insn)
 	      && (!mutate_p 
@@ -3663,14 +3687,17 @@ create_check_block_twin (rtx insn, bool mutate_p)
      in the recovery block).  */
   if (rec != EXIT_BLOCK_PTR)
     {
-      FOR_EACH_DEP_LINK (link, INSN_RESOLVED_BACK_DEPS (insn))
-	if ((DEP_LINK_STATUS (link) & DEP_OUTPUT) != 0)
+      sd_iterator_def sd_it;
+      dep_t dep;
+
+      FOR_EACH_DEP (insn, SD_LIST_RES_BACK, sd_it, dep)
+	if ((DEP_STATUS (dep) & DEP_OUTPUT) != 0)
 	  {
-	    struct _dep _dep, *dep = &_dep;
+	    struct _dep _dep2, *dep2 = &_dep2;
 
-	    init_dep (dep, DEP_LINK_PRO (link), check, REG_DEP_TRUE);
+	    init_dep (dep2, DEP_PRO (dep), check, REG_DEP_TRUE);
 
-	    add_back_dep_to_deps_list (INSN_RESOLVED_BACK_DEPS (check), dep);
+	    sd_add_dep (dep2, true);
 	  }
 
       twin = emit_insn_after (ORIG_PAT (insn), BB_END (rec));
@@ -3691,9 +3718,9 @@ create_check_block_twin (rtx insn, bool mutate_p)
 	 (TRUE | OUTPUT).  */
     }
 
-  copy_deps_list_change_con (INSN_RESOLVED_BACK_DEPS (twin),
-			     INSN_RESOLVED_BACK_DEPS (insn),
-			     twin);
+  /* Copy all resolved back dependencies of INSN to TWIN.  This will
+     provide correct value for INSN_TICK (TWIN).  */
+  sd_copy_back_deps (twin, insn, true);
 
   if (rec != EXIT_BLOCK_PTR)
     /* In case of branchy check, fix CFG.  */
@@ -3756,10 +3783,11 @@ create_check_block_twin (rtx insn, bool mutate_p)
 
   /* Move backward dependences from INSN to CHECK and 
      move forward dependences from INSN to TWIN.  */
-  FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
+
+  /* First, create dependencies between INSN's producers and CHECK & TWIN.  */
+  FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
     {
-      rtx pro = DEP_LINK_PRO (link);
-      enum reg_note dk = DEP_LINK_KIND (link);
+      rtx pro = DEP_PRO (dep);
       ds_t ds;
 
       /* If BEGIN_DATA: [insn ~~TRUE~~> producer]:
@@ -3777,7 +3805,7 @@ create_check_block_twin (rtx insn, bool mutate_p)
 	 twin  ~~TRUE~~> producer
 	 twin  --ANTI--> check  */	      	  
 
-      ds = DEP_LINK_STATUS (link);
+      ds = DEP_STATUS (dep);
 
       if (ds & BEGIN_SPEC)
 	{
@@ -3785,30 +3813,30 @@ create_check_block_twin (rtx insn, bool mutate_p)
 	  ds &= ~BEGIN_SPEC;
 	}
 
+      init_dep_1 (new_dep, pro, check, DEP_TYPE (dep), ds);
+      sd_add_dep (new_dep, false);
+
       if (rec != EXIT_BLOCK_PTR)
 	{
-	  add_back_forw_dep (check, pro, dk, ds);
-	  add_back_forw_dep (twin, pro, dk, ds);
+	  DEP_CON (new_dep) = twin;
+	  sd_add_dep (new_dep, false);
 	}    
-      else
-	add_back_forw_dep (check, pro, dk, ds);
     }
 
-  for (link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn)); link != NULL;)
-    if ((DEP_LINK_STATUS (link) & BEGIN_SPEC)
-	|| mutate_p)
-      /* We can delete this dep only if we totally overcome it with
-	 BEGIN_SPECULATION.  */
-      {
-        delete_back_forw_dep (link);
-
-	/* Restart search.  */
-        link = DEPS_LIST_FIRST (INSN_BACK_DEPS (insn));
-      }
-    else
-      /* Continue search.  */
-      link = DEP_LINK_NEXT (link);    
+  /* Second, remove backward dependencies of INSN.  */
+  for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK);
+       sd_iterator_cond (&sd_it, &dep);)
+    {
+      if ((DEP_STATUS (dep) & BEGIN_SPEC)
+	  || mutate_p)
+	/* We can delete this dep because we overcome it with
+	   BEGIN_SPECULATION.  */
+	sd_delete_dep (sd_it);
+      else
+	sd_iterator_next (&sd_it);
+    }
 
+  /* Future Speculations.  Determine what BE_IN speculations will be like.  */
   fs = 0;
 
   /* Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
@@ -3823,16 +3851,19 @@ create_check_block_twin (rtx insn, bool mutate_p)
       DONE_SPEC (insn) = ts & BEGIN_SPEC;
       CHECK_SPEC (check) = ts & BEGIN_SPEC;
 
+      /* Luckyness of future speculations solely depends upon initial
+	 BEGIN speculation.  */
       if (ts & BEGIN_DATA)
 	fs = set_dep_weak (fs, BE_IN_DATA, get_dep_weak (ts, BEGIN_DATA));
       if (ts & BEGIN_CONTROL)
-	fs = set_dep_weak (fs, BE_IN_CONTROL, get_dep_weak (ts, BEGIN_CONTROL));
+	fs = set_dep_weak (fs, BE_IN_CONTROL,
+			   get_dep_weak (ts, BEGIN_CONTROL));
     }
   else
     CHECK_SPEC (check) = CHECK_SPEC (insn);
 
   /* Future speculations: call the helper.  */
-  process_insn_forw_deps_be_in_spec (INSN_FORW_DEPS (insn), twin, fs);
+  process_insn_forw_deps_be_in_spec (insn, twin, fs);
 
   if (rec != EXIT_BLOCK_PTR)
     {
@@ -3842,35 +3873,45 @@ create_check_block_twin (rtx insn, bool mutate_p)
 
       if (!mutate_p)
 	{
-	  add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE);
-	  add_back_forw_dep (twin, insn, REG_DEP_OUTPUT, DEP_OUTPUT);
+	  init_dep (new_dep, insn, check, REG_DEP_TRUE);
+	  sd_add_dep (new_dep, false);
+
+	  init_dep (new_dep, insn, twin, REG_DEP_OUTPUT);
+	  sd_add_dep (new_dep, false);
 	}
       else
 	{
-	  dep_link_t link;
-
 	  if (spec_info->dump)    
 	    fprintf (spec_info->dump, ";;\t\tRemoved simple check : %s\n",
 		     (*current_sched_info->print_insn) (insn, 0));
 
-	  /* Remove all forward dependencies of the INSN.  */
-	  link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
-	  while (link != NULL)
-	    {
-	      delete_back_forw_dep (link);
-	      link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
-	    }
+	  /* Remove all dependencies of the INSN.  */
+	  {
+	    sd_it = sd_iterator_start (insn, (SD_LIST_FORW
+					      | SD_LIST_BACK
+					      | SD_LIST_RES_BACK));
+	    while (sd_iterator_cond (&sd_it, &dep))
+	      sd_delete_dep (sd_it);
+	  }
 
+	  /* If former check (INSN) already was moved to the ready (or queue)
+	     list, add new check (CHECK) there too.  */
 	  if (QUEUE_INDEX (insn) != QUEUE_NOWHERE)
 	    try_ready (check);
 
+	  /* Remove old check from instruction stream and free its
+	     data.  */
 	  sched_remove_insn (insn);
 	}
 
-      add_back_forw_dep (twin, check, REG_DEP_ANTI, DEP_ANTI);
+      init_dep (new_dep, check, twin, REG_DEP_ANTI);
+      sd_add_dep (new_dep, false);
     }
   else
-    add_back_forw_dep (check, insn, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
+    {
+      init_dep_1 (new_dep, insn, check, REG_DEP_TRUE, DEP_TRUE | DEP_OUTPUT);
+      sd_add_dep (new_dep, false);
+    }
 
   if (!mutate_p)
     /* Fix priorities.  If MUTATE_P is nonzero, this is not necessary,
@@ -3890,10 +3931,9 @@ create_check_block_twin (rtx insn, bool mutate_p)
 static void
 fix_recovery_deps (basic_block rec)
 {
-  dep_link_t link;
   rtx note, insn, jump, ready_list = 0;
   bitmap_head in_ready;
-  rtx link1;
+  rtx link;
 
   bitmap_initialize (&in_ready, 0);
   
@@ -3905,32 +3945,30 @@ fix_recovery_deps (basic_block rec)
   insn = PREV_INSN (insn);
 
   do
-    {    
-      for (link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn)); link != NULL;)
-	{
-	  rtx consumer;
+    {
+      sd_iterator_def sd_it;
+      dep_t dep;
 
-	  consumer = DEP_LINK_CON (link);
+      for (sd_it = sd_iterator_start (insn, SD_LIST_FORW);
+	   sd_iterator_cond (&sd_it, &dep);)
+	{
+	  rtx consumer = DEP_CON (dep);
 
 	  if (BLOCK_FOR_INSN (consumer) != rec)
 	    {
-	      delete_back_forw_dep (link);
+	      sd_delete_dep (sd_it);
 
 	      if (!bitmap_bit_p (&in_ready, INSN_LUID (consumer)))
 		{
 		  ready_list = alloc_INSN_LIST (consumer, ready_list);
 		  bitmap_set_bit (&in_ready, INSN_LUID (consumer));
 		}
-
-	      /* Restart search.  */
-	      link = DEPS_LIST_FIRST (INSN_FORW_DEPS (insn));
 	    }
 	  else
 	    {
-	      gcc_assert ((DEP_LINK_STATUS (link) & DEP_TYPES) == DEP_TRUE);
+	      gcc_assert ((DEP_STATUS (dep) & DEP_TYPES) == DEP_TRUE);
 
-	      /* Continue search.  */
-	      link = DEP_LINK_NEXT (link);
+	      sd_iterator_next (&sd_it);
 	    }
 	}
       
@@ -3941,8 +3979,8 @@ fix_recovery_deps (basic_block rec)
   bitmap_clear (&in_ready);
 
   /* Try to add instructions to the ready or queue list.  */
-  for (link1 = ready_list; link1; link1 = XEXP (link1, 1))
-    try_ready (XEXP (link1, 0));
+  for (link = ready_list; link; link = XEXP (link, 1))
+    try_ready (XEXP (link, 0));
   free_INSN_LIST_list (&ready_list);
 
   /* Fixing jump's dependences.  */
@@ -3971,6 +4009,31 @@ change_pattern (rtx insn, rtx new_pat)
   dfa_clear_single_insn_cache (insn);
 }
 
+/* Return true if INSN can potentially be speculated with type DS.  */
+bool
+sched_insn_is_legitimate_for_speculation_p (rtx insn, ds_t ds)
+{
+  if (HAS_INTERNAL_DEP (insn))
+    return false;
+
+  if (!NONJUMP_INSN_P (insn))
+    return false;
+
+  if (SCHED_GROUP_P (insn))
+    return false;
+
+  if (IS_SPECULATION_CHECK_P (insn))
+    return false;
+
+  if (side_effects_p (PATTERN (insn)))
+    return false;
+
+  if ((ds & BE_IN_SPEC)
+      && may_trap_p (PATTERN (insn)))
+    return false;
+
+  return true;
+}
 
 /* -1 - can't speculate,
    0 - for speculation with REQUEST mode it is OK to use
@@ -3980,25 +4043,15 @@ static int
 speculate_insn (rtx insn, ds_t request, rtx *new_pat)
 {
   gcc_assert (current_sched_info->flags & DO_SPECULATION
-              && (request & SPECULATIVE));
+              && (request & SPECULATIVE)
+	      && sched_insn_is_legitimate_for_speculation_p (insn, request));
 
-  if (!NONJUMP_INSN_P (insn)
-      || HAS_INTERNAL_DEP (insn)
-      || SCHED_GROUP_P (insn)
-      || side_effects_p (PATTERN (insn))
-      || (request & spec_info->mask) != request)    
+  if ((request & spec_info->mask) != request)
     return -1;
-  
-  gcc_assert (!IS_SPECULATION_CHECK_P (insn));
 
-  if (request & BE_IN_SPEC)
-    {            
-      if (may_trap_p (PATTERN (insn)))
-        return -1;
-      
-      if (!(request & BEGIN_SPEC))
-        return 0;
-    }
+  if (request & BE_IN_SPEC
+      && !(request & BEGIN_SPEC))
+    return 0;
 
   return targetm.sched.speculate_insn (insn, request & BEGIN_SPEC, new_pat);
 }
@@ -4244,6 +4297,8 @@ move_succs (VEC(edge,gc) **succsp, basic_block to)
 static void
 sched_remove_insn (rtx insn)
 {
+  sd_finish_insn (insn);
+
   change_queue_index (insn, QUEUE_NOWHERE);
   current_sched_info->add_remove_insn (insn, 1);
   remove_insn (insn);
@@ -4255,14 +4310,14 @@ sched_remove_insn (rtx insn)
 static void
 clear_priorities (rtx insn, rtx_vec_t *roots_ptr)
 {
-  dep_link_t link;
+  sd_iterator_def sd_it;
+  dep_t dep;
   bool insn_is_root_p = true;
 
   gcc_assert (QUEUE_INDEX (insn) != QUEUE_SCHEDULED);
 
-  FOR_EACH_DEP_LINK (link, INSN_BACK_DEPS (insn))
+  FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep)
     {
-      dep_t dep = DEP_LINK_DEP (link);
       rtx pro = DEP_PRO (dep);
 
       if (INSN_PRIORITY_STATUS (pro) >= 0
@@ -4307,12 +4362,17 @@ add_jump_dependencies (rtx insn, rtx jump)
       if (insn == jump)
 	break;
       
-      if (deps_list_empty_p (INSN_FORW_DEPS (insn)))
-	add_back_forw_dep (jump, insn, REG_DEP_ANTI, DEP_ANTI);
+      if (sd_lists_empty_p (insn, SD_LIST_FORW))
+	{
+	  dep_def _new_dep, *new_dep = &_new_dep;
+
+	  init_dep (new_dep, insn, jump, REG_DEP_ANTI);
+	  sd_add_dep (new_dep, false);
+	}
     }
   while (1);
 
-  gcc_assert (!deps_list_empty_p (INSN_BACK_DEPS (jump)));
+  gcc_assert (!sd_lists_empty_p (jump, SD_LIST_BACK));
 }
 
 /* Return the NOTE_INSN_BASIC_BLOCK of BB.  */
@@ -4330,36 +4390,6 @@ bb_note (basic_block bb)
 }
 
 #ifdef ENABLE_CHECKING
-extern void debug_spec_status (ds_t);
-
-/* Dump information about the dependence status S.  */
-void
-debug_spec_status (ds_t s)
-{
-  FILE *f = stderr;
-
-  if (s & BEGIN_DATA)
-    fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak (s, BEGIN_DATA));
-  if (s & BE_IN_DATA)
-    fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak (s, BE_IN_DATA));
-  if (s & BEGIN_CONTROL)
-    fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak (s, BEGIN_CONTROL));
-  if (s & BE_IN_CONTROL)
-    fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak (s, BE_IN_CONTROL));
-
-  if (s & HARD_DEP)
-    fprintf (f, "HARD_DEP; ");
-
-  if (s & DEP_TRUE)
-    fprintf (f, "DEP_TRUE; ");
-  if (s & DEP_ANTI)
-    fprintf (f, "DEP_ANTI; ");
-  if (s & DEP_OUTPUT)
-    fprintf (f, "DEP_OUTPUT; ");
-
-  fprintf (f, "\n");
-}
-
 /* Helper function for check_cfg.
    Return nonzero, if edge vector pointed to by EL has edge with TYPE in
    its flags.  */