* 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): Fix define.
        * lists.c (remove_free_EXPR_LIST_node): New.
        * rtl.h: Export it.
        * sched-deps.c (remove_from_dependence_list,
        remove_from_both_dependence_lists): New.
        (remove_from_deps): New. Use the above functions.
        * sched-deps.h (remove_from_deps): Export.
        * sel-sched-ir.h (struct _fence): New field `executing_insns'.
        (FENCE_EXECUTING_INSNS): New accessor.
        (struct _sel_insn_data): Remove _expr to expr.  Update all uses.
        Change asm_p to bool_bitfield. New field `ready_cycle'.
        * sel-sched-ir.c (fence_init, flist_add, fence_clear,
        init_fences, merge_fences, new_fences_add, new_fences_add_clean,
        new_fences_add_dirty): Update for FENCE_EXECUTING_INSNS.
        * sel-sched.c (advance_one_cycle): Remove excessive insns from
        FENCE_EXECUTING_INSNS.
        (undo_transformations): Forbid combined speculation.
        (process_use_exprs): Use EXPR_TARGET_AVAILABLE.
        (fill_insns): Set INSN_READY_CYCLE.  Update FENCE_EXECUTING_INSNS.
        (sel_sched_region_2): Likewise.



git-svn-id: https://gcc.gnu.org/svn/gcc/branches/sel-sched-branch@134264 138bc75d-0d04-0410-961f-82ee72b054a4

11 files changed, 327 insertions, 71 deletions

diff --git a/gcc/ChangeLog.sel-sched b/gcc/ChangeLog.sel-sched
index 347f9fbcefe..f3cf4670c1f 100644
--- a/gcc/ChangeLog.sel-sched
+++ b/gcc/ChangeLog.sel-sched
@@ -1,3 +1,31 @@
+2008-04-14  Andrey Belevantsev  <abel@ispras.ru>
+
+	* 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): Fix define.
+	* lists.c (remove_free_EXPR_LIST_node): New.
+	* rtl.h: Export it.
+	* sched-deps.c (remove_from_dependence_list, 
+	remove_from_both_dependence_lists): New.
+	(remove_from_deps): New. Use the above functions.
+	* sched-deps.h (remove_from_deps): Export.
+	* sel-sched-ir.h (struct _fence): New field `executing_insns'.
+	(FENCE_EXECUTING_INSNS): New accessor.
+	(struct _sel_insn_data): Remove _expr to expr.  Update all uses.
+	Change asm_p to bool_bitfield. New field `ready_cycle'.
+	* sel-sched-ir.c (fence_init, flist_add, fence_clear, 
+	init_fences, merge_fences, new_fences_add, new_fences_add_clean, 
+	new_fences_add_dirty): Update for FENCE_EXECUTING_INSNS.
+	* sel-sched.c (advance_one_cycle): Remove excessive insns from 
+	FENCE_EXECUTING_INSNS.
+	(undo_transformations): Forbid combined speculation.
+	(process_use_exprs): Use EXPR_TARGET_AVAILABLE.
+	(fill_insns): Set INSN_READY_CYCLE.  Update FENCE_EXECUTING_INSNS.
+	(sel_sched_region_2): Likewise.
+
 2008-04-14  Dmitry Melnik  <dm@ispras.ru>
 
 	* sel-sched-dump.c (get_print_blocks_num): New.
diff --git a/gcc/genattr.c b/gcc/genattr.c
index 8ff3cd38324..bef41cdc327 100644
--- a/gcc/genattr.c
+++ b/gcc/genattr.c
@@ -184,6 +184,10 @@ main (int argc, char **argv)
       printf ("   Use the function if bypass_p returns nonzero for\n");
       printf ("   the 1st insn. */\n");
       printf ("extern int insn_latency (rtx, rtx);\n\n");
+      printf ("/* Maximal insn latency time possible of all bypasses for this insn.\n");
+      printf ("   Use the function if bypass_p returns nonzero for\n");
+      printf ("   the 1st insn. */\n");
+      printf ("extern int maximal_insn_latency (rtx);\n\n");
       printf ("\n#if AUTOMATON_ALTS\n");
       printf ("/* The following function returns number of alternative\n");
       printf ("   reservations of given insn.  It may be used for better\n");
diff --git a/gcc/genautomata.c b/gcc/genautomata.c
index 96737bcf654..c3bfc8dd9c4 100644
--- a/gcc/genautomata.c
+++ b/gcc/genautomata.c
@@ -8067,13 +8067,11 @@ output_min_insn_conflict_delay_func (void)
   fprintf (output_file, "}\n\n");
 }
 
-/* Output function `internal_insn_latency'.  */
 static void
-output_internal_insn_latency_func (void)
+output_default_latencies (void)
 {
-  decl_t decl;
-  struct bypass_decl *bypass;
   int i, j, col;
+  decl_t decl;
   const char *tabletype = "unsigned char";
 
   /* Find the smallest integer type that can hold all the default
@@ -8089,18 +8087,6 @@ output_internal_insn_latency_func (void)
 	  tabletype = "int";
       }
 
-  fprintf (output_file, "static int\n%s (int %s ATTRIBUTE_UNUSED,\n\tint %s ATTRIBUTE_UNUSED,\n\trtx %s ATTRIBUTE_UNUSED,\n\trtx %s ATTRIBUTE_UNUSED)\n",
-	   INTERNAL_INSN_LATENCY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
-	   INTERNAL_INSN2_CODE_NAME, INSN_PARAMETER_NAME,
-	   INSN2_PARAMETER_NAME);
-  fprintf (output_file, "{\n");
-
-  if (DECL_INSN_RESERV (advance_cycle_insn_decl)->insn_num == 0)
-    {
-      fputs ("  return 0;\n}\n\n", output_file);
-      return;
-    }
-
   fprintf (output_file, "  static const %s default_latencies[] =\n    {",
 	   tabletype);
 
@@ -8117,6 +8103,27 @@ output_internal_insn_latency_func (void)
       }
   gcc_assert (j == DECL_INSN_RESERV (advance_cycle_insn_decl)->insn_num);
   fputs ("\n    };\n", output_file);
+}
+
+/* Output function `internal_insn_latency'.  */
+static void
+output_internal_insn_latency_func (void)
+{
+  int i;
+  decl_t decl;
+  struct bypass_decl *bypass;
+
+  fprintf (output_file, "static int\n%s (int %s ATTRIBUTE_UNUSED,\n\tint %s ATTRIBUTE_UNUSED,\n\trtx %s ATTRIBUTE_UNUSED,\n\trtx %s ATTRIBUTE_UNUSED)\n",
+	   INTERNAL_INSN_LATENCY_FUNC_NAME, INTERNAL_INSN_CODE_NAME,
+	   INTERNAL_INSN2_CODE_NAME, INSN_PARAMETER_NAME,
+	   INSN2_PARAMETER_NAME);
+  fprintf (output_file, "{\n");
+
+  if (DECL_INSN_RESERV (advance_cycle_insn_decl)->insn_num == 0)
+    {
+      fputs ("  return 0;\n}\n\n", output_file);
+      return;
+    }
 
   fprintf (output_file, "  if (%s >= %s || %s >= %s)\n    return 0;\n",
 	   INTERNAL_INSN_CODE_NAME, ADVANCE_CYCLE_VALUE_NAME,
@@ -8162,6 +8169,50 @@ output_internal_insn_latency_func (void)
 	   INTERNAL_INSN_CODE_NAME);
 }
 
+/* Output function `internal_maximum_insn_latency'.  */
+static void
+output_internal_maximal_insn_latency_func (void)
+{
+  decl_t decl;
+  struct bypass_decl *bypass;
+  int i;
+  int max;
+
+  fprintf (output_file, "static int\n%s (int %s ATTRIBUTE_UNUSED,\n\trtx %s ATTRIBUTE_UNUSED)\n",
+	   "internal_maximal_insn_latency", INTERNAL_INSN_CODE_NAME,
+	   INSN_PARAMETER_NAME);
+  fprintf (output_file, "{\n");
+
+  if (DECL_INSN_RESERV (advance_cycle_insn_decl)->insn_num == 0)
+    {
+      fputs ("  return 0;\n}\n\n", output_file);
+      return;
+    }
+
+  fprintf (output_file, "  switch (%s)\n    {\n", INTERNAL_INSN_CODE_NAME);
+  for (i = 0; i < description->decls_num; i++)
+    if (description->decls[i]->mode == dm_insn_reserv
+	&& DECL_INSN_RESERV (description->decls[i])->bypass_list)
+      {
+	decl = description->decls [i];
+        max = DECL_INSN_RESERV (decl)->default_latency;
+	fprintf (output_file,
+		 "    case %d: {",
+		 DECL_INSN_RESERV (decl)->insn_num);
+	for (bypass = DECL_INSN_RESERV (decl)->bypass_list;
+	     bypass != NULL;
+	     bypass = bypass->next)
+	  {
+	    if (bypass->latency > max)
+              max = bypass->latency;
+	  }
+	fprintf (output_file, " return %d; }\n      break;\n", max);
+      }
+
+  fprintf (output_file, "    }\n  return default_latencies[%s];\n}\n\n",
+	   INTERNAL_INSN_CODE_NAME);
+}
+
 /* The function outputs PHR interface function `insn_latency'.  */
 static void
 output_insn_latency_func (void)
@@ -8180,6 +8231,21 @@ output_insn_latency_func (void)
 	   INSN_PARAMETER_NAME, INSN2_PARAMETER_NAME);
 }
 
+/* The function outputs PHR interface function `insn_latency'.  */
+static void
+output_maximal_insn_latency_func (void)
+{
+  fprintf (output_file, "int\n%s (rtx %s)\n",
+	   "maximal_insn_latency", INSN_PARAMETER_NAME);
+  fprintf (output_file, "{\n  int %s;\n",
+	   INTERNAL_INSN_CODE_NAME);
+  output_internal_insn_code_evaluation (INSN_PARAMETER_NAME,
+					INTERNAL_INSN_CODE_NAME, 0);
+  fprintf (output_file, "  return %s (%s, %s);\n}\n\n",
+	   "internal_maximal_insn_latency",
+	   INTERNAL_INSN_CODE_NAME, INSN_PARAMETER_NAME);
+}
+
 /* The function outputs PHR interface function `print_reservation'.  */
 static void
 output_print_reservation_func (void)
@@ -9169,8 +9235,11 @@ write_automata (void)
   output_internal_reset_func ();
   output_reset_func ();
   output_min_insn_conflict_delay_func ();
+  output_default_latencies ();
   output_internal_insn_latency_func ();
   output_insn_latency_func ();
+  output_internal_maximal_insn_latency_func ();
+  output_maximal_insn_latency_func ();
   output_print_reservation_func ();
   /* Output function get_cpu_unit_code.  */
   fprintf (output_file, "\n#if %s\n\n", CPU_UNITS_QUERY_MACRO_NAME);
diff --git a/gcc/hard-reg-set.h b/gcc/hard-reg-set.h
index e2ce7da22c9..11817d82d35 100644
--- a/gcc/hard-reg-set.h
+++ b/gcc/hard-reg-set.h
@@ -89,6 +89,8 @@ typedef HARD_REG_ELT_TYPE HARD_REG_SET[HARD_REG_SET_LONGS];
    hard_reg_set_intersect_p (X, Y), which returns true if X and Y intersect.
    hard_reg_set_empty_p (X), which returns true if X is empty.  */
 
+#define UHOST_BITS_PER_WIDE_INT ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
+
 #ifdef HARD_REG_SET
 
 #define SET_HARD_REG_BIT(SET, BIT)  \
@@ -135,8 +137,6 @@ hard_reg_set_empty_p (const HARD_REG_SET x)
 
 #else
 
-#define UHOST_BITS_PER_WIDE_INT ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
-
 #define SET_HARD_REG_BIT(SET, BIT)		\
   ((SET)[(BIT) / UHOST_BITS_PER_WIDE_INT]	\
    |= HARD_CONST (1) << ((BIT) % UHOST_BITS_PER_WIDE_INT))
diff --git a/gcc/lists.c b/gcc/lists.c
index 2f3092f0766..77aeac3a09d 100644
--- a/gcc/lists.c
+++ b/gcc/lists.c
@@ -201,4 +201,17 @@ remove_free_INSN_LIST_node (rtx *listp)
   return elem;
 }
 
+/* Remove and free the first node in the EXPR_LIST pointed to by LISTP.  */
+rtx
+remove_free_EXPR_LIST_node (rtx *listp)
+{
+  rtx node = *listp;
+  rtx elem = XEXP (node, 0);
+
+  remove_list_node (listp);
+  free_EXPR_LIST_node (node);
+
+  return elem;
+}
+
 #include "gt-lists.h"
diff --git a/gcc/rtl.h b/gcc/rtl.h
index 6a2fd3f526c..c351846b799 100644
--- a/gcc/rtl.h
+++ b/gcc/rtl.h
@@ -1777,15 +1777,17 @@ extern rtx get_condition (rtx, rtx *, int, int);
 
 /* lists.c */
 
-void free_EXPR_LIST_list		(rtx *);
-void free_INSN_LIST_list		(rtx *);
-void free_EXPR_LIST_node		(rtx);
-void free_INSN_LIST_node		(rtx);
-rtx alloc_INSN_LIST			(rtx, rtx);
-rtx alloc_EXPR_LIST			(int, rtx, rtx);
-void remove_free_INSN_LIST_elem (rtx, rtx *);
-rtx remove_list_elem (rtx, rtx *);
-rtx remove_free_INSN_LIST_node (rtx *);
+extern void free_EXPR_LIST_list		(rtx *);
+extern void free_INSN_LIST_list		(rtx *);
+extern void free_EXPR_LIST_node		(rtx);
+extern void free_INSN_LIST_node		(rtx);
+extern rtx alloc_INSN_LIST			(rtx, rtx);
+extern rtx alloc_EXPR_LIST			(int, rtx, rtx);
+extern void remove_free_INSN_LIST_elem (rtx, rtx *);
+extern rtx remove_list_elem (rtx, rtx *);
+extern rtx remove_free_INSN_LIST_node (rtx *);
+extern rtx remove_free_EXPR_LIST_node (rtx *);
+
 
 /* regclass.c */
 
diff --git a/gcc/sched-deps.c b/gcc/sched-deps.c
index 53607a72e77..e8292fda390 100644
--- a/gcc/sched-deps.c
+++ b/gcc/sched-deps.c
@@ -1339,6 +1339,52 @@ add_dependence_list_and_free (struct deps *deps, rtx insn, rtx *listp,
     }
 }
 
+/* Remove all occurences of INSN from LIST.  Return the number of 
+   occurences removed.  */
+
+static int
+remove_from_dependence_list (rtx insn, rtx* listp)
+{
+  int removed = 0;
+  
+  while (*listp)
+    {
+      if (XEXP (*listp, 0) == insn)
+        {
+          remove_free_INSN_LIST_node (listp);
+          removed++;
+          continue;
+        }
+      
+      listp = &XEXP (*listp, 1);
+    }
+  
+  return removed;
+}
+
+/* Same as above, but process two lists at once.  */
+static int 
+remove_from_both_dependence_lists (rtx insn, rtx *listp, rtx *exprp)
+{
+  int removed = 0;
+  
+  while (*listp)
+    {
+      if (XEXP (*listp, 0) == insn)
+        {
+          remove_free_INSN_LIST_node (listp);
+          remove_free_EXPR_LIST_node (exprp);
+          removed++;
+          continue;
+        }
+      
+      listp = &XEXP (*listp, 1);
+      exprp = &XEXP (*exprp, 1);
+    }
+  
+  return removed;
+}
+
 /* Clear all dependencies for an insn.  */
 static void
 delete_all_dependences (rtx insn)
@@ -2475,9 +2521,6 @@ sched_analyze_insn (struct deps *deps, rtx x, rtx insn)
         CLEAR_REG_SET (&deps->reg_conditional_sets);
       reg_pending_barrier = NOT_A_BARRIER;
     }
-  else
-    {
-    }
 
   CLEAR_REG_SET (reg_pending_uses);
   CLEAR_REG_SET (reg_pending_clobbers);
@@ -2908,6 +2951,42 @@ free_deps (struct deps *deps)
   deps = NULL;
 }
 
+/* Remove INSN from dependence contexts DEPS.  Caution: reg_conditional_sets
+   is not handled.  */
+void
+remove_from_deps (struct deps *deps, rtx insn)
+{
+  int removed;
+  unsigned i;
+  reg_set_iterator rsi;
+  
+  removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns,
+                                               &deps->pending_read_mems);
+  deps->pending_read_list_length -= removed;
+  removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns,
+                                               &deps->pending_write_mems);
+  deps->pending_write_list_length -= removed;
+  removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush);
+  deps->pending_flush_length -= removed;
+
+  EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi)
+    {
+      struct deps_reg *reg_last = &deps->reg_last[i];
+      if (reg_last->uses)
+	remove_from_dependence_list (insn, &reg_last->uses);
+      if (reg_last->sets)
+	remove_from_dependence_list (insn, &reg_last->sets);
+      if (reg_last->clobbers)
+	remove_from_dependence_list (insn, &reg_last->clobbers);
+      if (!reg_last->uses && !reg_last->sets && !reg_last->clobbers)
+        CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, i);
+    }
+
+  if (CALL_P (insn))
+    remove_from_dependence_list (insn, &deps->last_function_call);
+  remove_from_dependence_list (insn, &deps->sched_before_next_call);
+}
+
 /* An array indexed by INSN_UID that holds the data related 
    to insn's dependencies and common to all schedulers.  */
 VEC (deps_insn_data_def, heap) *d_i_d = NULL;
diff --git a/gcc/sched-deps.h b/gcc/sched-deps.h
index 63316e496cc..1b9d6bb589f 100644
--- a/gcc/sched-deps.h
+++ b/gcc/sched-deps.h
@@ -168,6 +168,7 @@ extern void deps_analyze_insn (struct deps *, rtx);
 extern void sched_analyze (struct deps *, rtx, rtx);
 extern void init_deps (struct deps *);
 extern void free_deps (struct deps *);
+extern void remove_from_deps (struct deps *, rtx);
 extern void init_deps_global (void);
 extern void finish_deps_global (void);
 extern void add_forw_dep (dep_link_t);
diff --git a/gcc/sel-sched-ir.c b/gcc/sel-sched-ir.c
index b0d338621f1..3988ecacf45 100644
--- a/gcc/sel-sched-ir.c
+++ b/gcc/sel-sched-ir.c
@@ -133,7 +133,7 @@ bool preheader_removed = false;
 
 /* Forward static declarations.  */
 static void fence_init (fence_t, insn_t, state_t, deps_t, void *,
-                        rtx, rtx, int, int, bool, bool);
+                        rtx, VEC(rtx, gc) *, rtx, int, int, bool, bool);
 static void fence_clear (fence_t);
 
 static void deps_init_id (idata_t, insn_t, bool);
@@ -235,13 +235,14 @@ flist_lookup (flist_t l, insn_t insn)
 /* Add new fence consisting of INSN and STATE to the list pointed to by LP.  */
 void
 flist_add (flist_t *lp, insn_t insn, state_t state, deps_t dc, void *tc, 
-           insn_t last_scheduled_insn, insn_t sched_next, int cycle,
-	   int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
+           insn_t last_scheduled_insn, VEC(rtx,gc) *executing_insns, 
+           insn_t sched_next, int cycle, int cycle_issued_insns, 
+           bool starts_cycle_p, bool after_stall_p)
 {
   _list_add (lp);
   fence_init (FLIST_FENCE (*lp), insn, state, dc, tc, last_scheduled_insn,
-	      sched_next, cycle, cycle_issued_insns, starts_cycle_p,
-	      after_stall_p);
+              executing_insns, sched_next, cycle, cycle_issued_insns, 
+              starts_cycle_p, after_stall_p);
 }
 
 /* Remove the head node of the list pointed to by LP.  */
@@ -517,8 +518,9 @@ state_create_copy (state_t from)
 /* Initialize the fence.  */
 static void
 fence_init (fence_t f, insn_t insn, state_t state, deps_t dc, void *tc,
-	    rtx last_scheduled_insn, rtx sched_next, int cycle,
-	    int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
+	    rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns, 
+            rtx sched_next, int cycle, int cycle_issued_insns, 
+            bool starts_cycle_p, bool after_stall_p)
 {
   FENCE_INSN (f) = insn;
 
@@ -541,6 +543,7 @@ fence_init (fence_t f, insn_t insn, state_t state, deps_t dc, void *tc,
   FENCE_TC (f) = tc;
 
   FENCE_LAST_SCHEDULED_INSN (f) = last_scheduled_insn;
+  FENCE_EXECUTING_INSNS (f) = executing_insns;
   FENCE_SCHED_NEXT (f) = sched_next;
 }
 
@@ -579,6 +582,7 @@ fence_clear (fence_t f)
 
   if (tc != NULL)
     delete_target_context (tc);
+  VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
 }
 
 /* Init a list of fences with successors of OLD_FENCE.  */
@@ -601,7 +605,9 @@ init_fences (insn_t old_fence)
 		 state_create (),
 		 create_deps_context () /* dc */,
 		 create_target_context (true) /* tc */,
-		 NULL_RTX /* last_scheduled_insn */, NULL_RTX /* sched_next */,
+		 NULL_RTX /* last_scheduled_insn */, 
+                 NULL, /* executing_insns */
+                 NULL_RTX /* sched_next */,
 		 1 /* cycle */, 0 /* cycle_issued_insns */, 
 		 1 /* starts_cycle_p */, 0 /* after_stall_p */);  
     }
@@ -609,12 +615,13 @@ init_fences (insn_t old_fence)
 
 /* Merges two fences (filling fields of OLD_FENCE with resulting values) by
    following rules: 1) state, target context and last scheduled insn are
-   propagated from fallthrough edge if it is availiable; 
+   propagated from fallthrough edge if it is available; 
    2) deps context and cycle is propagated from more probable edge;
    3) all other fields are set to corresponding constant values.  */
 static void
 merge_fences (fence_t f, insn_t insn,
-	      state_t state, deps_t dc, void *tc, rtx last_scheduled_insn, 
+	      state_t state, deps_t dc, void *tc, 
+              rtx last_scheduled_insn, VEC(rtx, gc) *executing_insns,
 	      rtx sched_next, int cycle, bool after_stall_p)
 {
   insn_t last_scheduled_insn_old = FENCE_LAST_SCHEDULED_INSN (f);
@@ -645,6 +652,10 @@ merge_fences (fence_t f, insn_t insn,
         FENCE_CYCLE (f) = cycle;
 
       FENCE_LAST_SCHEDULED_INSN (f) = NULL;
+      VEC_free (rtx, gc, executing_insns);
+      if (FENCE_EXECUTING_INSNS (f))
+        VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0, 
+                          VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
     }
   else
     {
@@ -725,21 +736,27 @@ merge_fences (fence_t f, insn_t insn,
           {
             reset_deps_context (FENCE_DC (f));
             delete_deps_context (dc);
+            VEC_free (rtx, gc, executing_insns);
   
             FENCE_CYCLE (f) = MAX (FENCE_CYCLE (f), cycle);
+            if (FENCE_EXECUTING_INSNS (f))
+              VEC_block_remove (rtx, FENCE_EXECUTING_INSNS (f), 0, 
+                                VEC_length (rtx, FENCE_EXECUTING_INSNS (f)));
           }
         else
           if (edge_new->probability > edge_old->probability)
             {
               delete_deps_context (FENCE_DC (f));
               FENCE_DC (f) = dc;
-
+              VEC_free (rtx, gc, FENCE_EXECUTING_INSNS (f));
+              FENCE_EXECUTING_INSNS (f) = executing_insns;
               FENCE_CYCLE (f) = cycle;
             }
           else
             {
               /* Leave DC and CYCLE untouched.  */
               delete_deps_context (dc);
+              VEC_free (rtx, gc, executing_insns);
             }
     }
 
@@ -757,15 +774,16 @@ merge_fences (fence_t f, insn_t insn,
 void
 new_fences_add (flist_tail_t new_fences, insn_t insn,
 		state_t state, deps_t dc, void *tc, rtx last_scheduled_insn, 
-		rtx sched_next, int cycle, int cycle_issued_insns, 
-                bool starts_cycle_p, bool after_stall_p)
+                VEC(rtx, gc) *executing_insns, rtx sched_next, int cycle, 
+                int cycle_issued_insns, bool starts_cycle_p, bool after_stall_p)
 {
   fence_t f = flist_lookup (FLIST_TAIL_HEAD (new_fences), insn);
 
   if (!f)
     {
       flist_add (FLIST_TAIL_TAILP (new_fences), insn, state, dc, tc,
-		 last_scheduled_insn, sched_next, cycle, cycle_issued_insns,
+		 last_scheduled_insn, executing_insns, 
+                 sched_next, cycle, cycle_issued_insns,
 		 starts_cycle_p, after_stall_p);
 
       FLIST_TAIL_TAILP (new_fences)
@@ -773,8 +791,8 @@ new_fences_add (flist_tail_t new_fences, insn_t insn,
     }
   else
     {
-      merge_fences (f, insn, state, dc, tc, last_scheduled_insn, sched_next, 
-                    cycle, after_stall_p);
+      merge_fences (f, insn, state, dc, tc, last_scheduled_insn, 
+                    executing_insns, sched_next, cycle, after_stall_p);
 
     }
 }
@@ -787,7 +805,7 @@ new_fences_add_clean (flist_tail_t new_fences, insn_t succ, fence_t fence)
   new_fences_add (new_fences,
 		  succ, state_create (), create_deps_context (),
 		  create_target_context (true),
-		  NULL_RTX, NULL_RTX, FENCE_CYCLE (fence) + 1,
+		  NULL_RTX, NULL, NULL_RTX, FENCE_CYCLE (fence) + 1,
 		  0, 1, FENCE_AFTER_STALL_P (fence));
 }
 
@@ -800,7 +818,9 @@ new_fences_add_dirty (flist_tail_t new_fences, insn_t succ, fence_t fence)
 		  succ, state_create_copy (FENCE_STATE (fence)),
 		  create_copy_of_deps_context (FENCE_DC (fence)),
 		  create_copy_of_target_context (FENCE_TC (fence)),
-		  FENCE_LAST_SCHEDULED_INSN (fence), FENCE_SCHED_NEXT (fence),
+		  FENCE_LAST_SCHEDULED_INSN (fence), 
+                  VEC_copy (rtx, gc, FENCE_EXECUTING_INSNS (fence)),
+                  FENCE_SCHED_NEXT (fence),
 		  FENCE_CYCLE (fence),
 		  FENCE_ISSUED_INSNS (fence),
 		  FENCE_STARTS_CYCLE_P (fence),
@@ -3292,6 +3312,8 @@ tick_check_p (rhs_t rhs, deps_t dc, fence_t fence)
   
   gcc_assert (!dc->readonly);
   dc->readonly = 1;
+  print ("context: %d %d %d\n", dc->pending_read_list_length,
+         dc->pending_write_list_length, dc->pending_flush_length);
   deps_analyze_insn (dc, RHS_INSN (rhs));
   dc->readonly = 0;
 
@@ -3659,6 +3681,8 @@ finish_insns (void)
           htab_delete (sid_entry->transformed_insns);
 	  free_deps (&sid_entry->deps_context);
 	}
+      if (EXPR_VINSN (&sid_entry->expr))
+	clear_expr (&sid_entry->expr);
     }
   
   VEC_free (sel_insn_data_def, heap, s_i_d);
@@ -3726,7 +3750,7 @@ static bool insn_init_create_new_vinsn_p;
 static expr_t
 set_insn_init (expr_t expr, vinsn_t vi, int seqno)
 {
-  expr_t x = &insn_init_ssid->_expr;
+  expr_t x = &insn_init_ssid->expr;
   ds_t ds_x;
 
   copy_expr_onside (x, expr);
@@ -3768,7 +3792,7 @@ init_insn (insn_t insn)
   gcc_assert (INSN_P (insn) && INSN_LUID (insn) > 0);
 
   expr = INSN_EXPR (insn);
-  copy_expr (expr, &ssid->_expr);
+  copy_expr (expr, &ssid->expr);
 
   INSN_SEQNO (insn) = ssid->seqno;
   EXPR_ORIG_BB_INDEX (expr) = BLOCK_NUM (insn);
@@ -3817,7 +3841,7 @@ sel_init_new_insns (void)
 
       sched_scan (&ssi, NULL, NULL, new_insns, NULL);
 
-      clear_expr (&insn_init_ssid->_expr);
+      clear_expr (&insn_init_ssid->expr);
     }
 
   if (todo & INSN_INIT_TODO_SIMPLEJUMP)
diff --git a/gcc/sel-sched-ir.h b/gcc/sel-sched-ir.h
index 4433dffc4a0..3ee71b6450b 100644
--- a/gcc/sel-sched-ir.h
+++ b/gcc/sel-sched-ir.h
@@ -283,6 +283,9 @@ struct _fence
      scheduling information when changing fences.  */
   tc_t tc;
 
+  /* A vector of insns that are scheduled but not yet completed.  */
+  VEC (rtx,gc) *executing_insns;
+      
   /* Insn, which has been scheduled last on this fence.  */
   rtx last_scheduled_insn;
 
@@ -315,6 +318,7 @@ typedef struct _fence *fence_t;
 #define FENCE_DC(F) ((F)->dc)
 #define FENCE_TC(F) ((F)->tc)
 #define FENCE_LAST_SCHEDULED_INSN(F) ((F)->last_scheduled_insn)
+#define FENCE_EXECUTING_INSNS(F) ((F)->executing_insns)
 #define FENCE_SCHED_NEXT(F) ((F)->sched_next)
 
 /* List of fences.  */
@@ -673,7 +677,7 @@ struct _sel_insn_data
      Much of the information, that reflect information about the insn itself
      (e.g. not about where it stands in CFG) is contained in the VINSN_ID
      field of this home VI.  */
-  expr_def _expr;
+  expr_def expr;
 
   /* If (WS_LEVEL == GLOBAL_LEVEL) then AV is empty.  */
   int ws_level;
@@ -698,9 +702,6 @@ struct _sel_insn_data
   /* A context incapsulating this insn.  */
   struct deps deps_context;
 
-  /* Insn is an ASM.  */
-  bool asm_p;
-
   /* This field is initialized at the beginning of scheduling and is used
      to handle sched group instructions.  If it is non-null, then it points
      to the instruction, which should be forced to schedule next.  Such
@@ -708,13 +709,18 @@ struct _sel_insn_data
   insn_t sched_next;
 
   /* Cycle at which insn was scheduled.  It is greater than zero if insn was
-     scheduled.
-     This is used for bundling.  */
+     scheduled.  This is used for bundling.  */
   int sched_cycle;
 
+  /* Cycle at which insn's data will be fully ready.  */
+  int ready_cycle;
+
   /* Speculations that are being checked by this insn.  */
   ds_t spec_checked_ds;
 
+  /* Insn is an ASM.  */
+  BOOL_BITFIELD asm_p : 1;
+
   /* True when an insn is scheduled after we've determined that a stall is
      required.
      This is used when emulating the Haifa scheduler for bundling.  */
@@ -743,7 +749,7 @@ extern sel_insn_data_def insn_sid (insn_t);
 #define INSN_ORIGINATORS_BY_UID(UID) (SID_BY_UID (UID)->originators)
 #define INSN_TRANSFORMED_INSNS(INSN) (SID (INSN)->transformed_insns)
 
-#define INSN_EXPR(INSN) (&SID (INSN)->_expr)
+#define INSN_EXPR(INSN) (&SID (INSN)->expr)
 #define INSN_VINSN(INSN) (RHS_VINSN (INSN_EXPR (INSN)))
 #define INSN_TYPE(INSN) (VINSN_TYPE (INSN_VINSN (INSN)))
 #define INSN_SIMPLEJUMP_P(INSN) (INSN_TYPE (INSN) == PC)
@@ -756,6 +762,7 @@ extern sel_insn_data_def insn_sid (insn_t);
 #define INSN_SEQNO(INSN) (SID (INSN)->seqno)
 #define INSN_AFTER_STALL_P(INSN) (SID (INSN)->after_stall_p)
 #define INSN_SCHED_CYCLE(INSN) (SID (INSN)->sched_cycle)
+#define INSN_READY_CYCLE(INSN) (SID (INSN)->ready_cycle)
 #define INSN_SPEC_CHECKED_DS(INSN) (SID (INSN)->spec_checked_ds)
 
 /* A global level shows whether an insn is valid or not.  */
@@ -1438,7 +1445,7 @@ extern void blist_add (blist_t *, insn_t, ilist_t, deps_t);
 extern void blist_remove (blist_t *);
 extern void flist_tail_init (flist_tail_t);
 extern void flist_add (flist_t *, insn_t, state_t, deps_t, void *, 
-                       insn_t, insn_t, int, int, bool, bool);
+                       insn_t, VEC(rtx, gc) *, insn_t, int, int, bool, bool);
 
 extern fence_t flist_lookup (flist_t, insn_t);
 extern void flist_clear (flist_t *);
@@ -1455,7 +1462,7 @@ extern void advance_deps_context (deps_t, insn_t);
 /* Fences functions.  */
 extern void init_fences (insn_t);
 extern void new_fences_add (flist_tail_t, insn_t, state_t, deps_t, void *, rtx,
-                       rtx, int, int, bool, bool);
+                            VEC(rtx, gc) *, rtx, int, int, bool, bool);
 extern void new_fences_add_clean (flist_tail_t, insn_t, fence_t);
 extern void new_fences_add_dirty (flist_tail_t, insn_t, fence_t);
 
diff --git a/gcc/sel-sched.c b/gcc/sel-sched.c
index a2e324c9b08..e2ad7d746af 100644
--- a/gcc/sel-sched.c
+++ b/gcc/sel-sched.c
@@ -370,11 +370,26 @@ static av_set_t compute_av_set_inside_bb (insn_t, ilist_t, int, bool);
 static void
 advance_one_cycle (fence_t fence)
 {
+  unsigned i;
+  int cycle;
+  rtx insn;
+  
   advance_state (FENCE_STATE (fence));
-  FENCE_CYCLE (fence)++;
+  cycle = ++FENCE_CYCLE (fence);
   FENCE_ISSUED_INSNS (fence) = 0;
   FENCE_STARTS_CYCLE_P (fence) = 1;
   can_issue_more = issue_rate;
+
+  for (i = 0; VEC_iterate (rtx, FENCE_EXECUTING_INSNS (fence), i, insn); )
+    {
+      if (INSN_READY_CYCLE (insn) < cycle)
+        {
+          remove_from_deps (FENCE_DC (fence), insn);
+          VEC_unordered_remove (rtx, FENCE_EXECUTING_INSNS (fence), i);
+          continue;
+        }
+      i++;
+    }
   print ("Finished a cycle.  Current cycle = %d", FENCE_CYCLE (fence));
 }
 
@@ -1643,8 +1658,7 @@ undo_transformations (av_set_t *av_ptr, rtx insn)
         av_set_iter_remove (&av_iter);
       }
 
-  /* FIXME: we need to determine whether RHS was changed on this insn 
-     just once.  */
+  /* Undo transformations looking at the history vector.  */
   FOR_EACH_RHS (rhs, av_iter, *av_ptr)
     {
       int index = find_in_history_vect (EXPR_HISTORY_OF_CHANGES (rhs),
@@ -3065,7 +3079,10 @@ process_spec_exprs (av_set_t *av_ptr)
       /* The probability of a success is too low - don't speculate.  */
       if ((ds & SPECULATIVE)
           && (ds_weak (ds) < spec_info->data_weakness_cutoff
-              || EXPR_USEFULNESS (rhs) < spec_info->control_weakness_cutoff))
+              || EXPR_USEFULNESS (rhs) < spec_info->control_weakness_cutoff		
+	      || (pipelining_p
+	      	  && (ds & DATA_SPEC)
+		  && (ds & CONTROL_SPEC))))
         {
           av_set_iter_remove (&si);
           continue;
@@ -3106,13 +3123,12 @@ process_spec_exprs (av_set_t *av_ptr)
    Note that we check here whether a USE could be scheduled to avoid
    an infinite loop later.  */
 static rhs_t
-process_use_exprs (av_set_t *av_ptr, blist_t bnds)
+process_use_exprs (av_set_t *av_ptr)
 {
   rhs_t rhs;
   av_set_iterator si;
   bool uses_present_p = false;
   bool try_uses_p = true;
-  bool is_orig_reg = false;
 
   FOR_EACH_RHS_1 (rhs, si, av_ptr)
     {
@@ -3123,7 +3139,7 @@ process_use_exprs (av_set_t *av_ptr, blist_t bnds)
              do so because it will do good only.  */
           if (EXPR_SCHED_TIMES (rhs) <= 0)
             {
-              if (find_best_reg_for_rhs (rhs, bnds, &is_orig_reg))
+              if (EXPR_TARGET_AVAILABLE (rhs) == 1)
                 return rhs;
 
               av_set_iter_remove (&si);
@@ -3155,7 +3171,7 @@ process_use_exprs (av_set_t *av_ptr, blist_t bnds)
             {
               gcc_assert (INSN_CODE (EXPR_INSN_RTX (rhs)) < 0);
 
-              if (find_best_reg_for_rhs (rhs, bnds, &is_orig_reg))
+              if (EXPR_TARGET_AVAILABLE (rhs) == 1)
                 return rhs;
 
               av_set_iter_remove (&si);
@@ -3180,6 +3196,8 @@ expr_blocked_by_bookkeeping_p (expr_t expr)
   return false;
 }
 
+/* Return true if either of expressions from ORIG_OPS can be blocked
+   by previously created bookkeeping code.  */
 static bool
 av_set_could_be_blocked_by_bookkeeping_p (av_set_t orig_ops)
 {
@@ -3454,7 +3472,7 @@ fill_ready_list (av_set_t *av_ptr, blist_t bnds, fence_t fence)
   process_spec_exprs (av_ptr);
 
   /* A USE could be scheduled immediately.  */
-  rhs = process_use_exprs (av_ptr, bnds);
+  rhs = process_use_exprs (av_ptr);
   if (rhs)
     return rhs;
 
@@ -4673,6 +4691,14 @@ fill_insns (fence_t fence, int seqno, ilist_t **scheduled_insns_tailpp)
           memcpy (temp_state, FENCE_STATE (fence), dfa_state_size);
           INSN_AFTER_STALL_P (insn) = FENCE_AFTER_STALL_P (fence);
           INSN_SCHED_CYCLE (insn) = FENCE_CYCLE (fence);
+
+          /* This does not account for adjust_cost hooks, just add the biggest
+             constant the hook may add to the latency.  TODO: make this 
+             a target dependent constant.  */
+          INSN_READY_CYCLE (insn) 
+            = FENCE_CYCLE (fence) + (INSN_CODE (insn) < 0 
+                                     ? 1
+                                     : maximal_insn_latency (insn) + 1);
 	  EXPR_TARGET_AVAILABLE (INSN_EXPR (insn)) = true;
 
 	  if (asm_p)
@@ -4681,6 +4707,7 @@ fill_insns (fence_t fence, int seqno, ilist_t **scheduled_insns_tailpp)
           FENCE_AFTER_STALL_P (fence) = 0;
           FENCE_STARTS_CYCLE_P (fence) = 0;
 	  FENCE_LAST_SCHEDULED_INSN (fence) = insn;
+          VEC_safe_push (rtx, gc, FENCE_EXECUTING_INSNS (fence), insn);
           if (SCHED_GROUP_P (insn))
             {
               FENCE_SCHED_NEXT (fence) = INSN_SCHED_NEXT (insn);
@@ -5526,17 +5553,17 @@ move_op_process_successors (insn_t insn, av_set_t orig_ops, ilist_t path,
   return res;
 }
 
+
+/* Perform a cleanup when the driver is about to terminate.  */
 static inline void
 code_motion_path_driver_cleanup (av_set_t *orig_ops_p, ilist_t *path_p,
 				 int save_print_blocks_n)
 {
   ilist_remove (path_p);
-
   av_set_clear (orig_ops_p);
 
   while (get_print_blocks_num () > save_print_blocks_n)
     block_finish ();
-
 }
 
 /* The driver function that implements move_op or find_used_regs 
@@ -6475,6 +6502,7 @@ sel_sched_region_2 (sel_sched_region_2_data_t data)
 				  insn, state, FENCE_DC (fence), 
                                   FENCE_TC (fence), 
                                   FENCE_LAST_SCHEDULED_INSN (fence), 
+                                  FENCE_EXECUTING_INSNS (fence),
                                   FENCE_SCHED_NEXT (fence),
                                   FENCE_CYCLE (fence), 
 				  FENCE_ISSUED_INSNS (fence),
@@ -6485,6 +6513,7 @@ sel_sched_region_2 (sel_sched_region_2_data_t data)
 		  FENCE_STATE (fence) = NULL;
 		  FENCE_DC (fence) = NULL;
                   FENCE_TC (fence) = NULL;
+                  FENCE_EXECUTING_INSNS (fence) = NULL;
 		}
 
 	      continue;