df.h (df_mw_hardreg, [...]): Add a link pointer.

gcc/
	* df.h (df_mw_hardreg, df_base_ref): Add a link pointer.
	(df_insn_info): Turn defs, uses, eq_uses and mw_hardregs into linked
	lists.
	(df_scan_bb_info): Likewise artificial_defs and artificial_uses.
	(DF_REF_NEXT_LOC, DF_MWS_NEXT): New macros.
	(FOR_EACH_INSN_INFO_DEF, FOR_EACH_INSN_INFO_USE)
	(FOR_EACH_INSN_INFO_EQ_USE, FOR_EACH_INSN_INFO_MW)
	(FOR_EACH_ARTIFICIAL_USE, FOR_EACH_ARTIFICIAL_DEF)
	(df_get_artificial_defs, df_get_artificial_uses)
	(df_single_def, df_single_use): Update accordingly.
	(df_refs_chain_dump): Take the first element in a linked list as
	parameter, rather than a pointer to an array of pointers.
	* df-core.c (df_refs_chain_dump, df_mws_dump): Likewise.
	* df-problems.c (df_rd_bb_local_compute_process_def): Likewise.
	(df_chain_create_bb_process_use): Likewise.
	(df_md_bb_local_compute_process_def): Likewise.
	* fwprop.c (process_defs, process_uses): Likewise.
	(register_active_defs, update_uses): Likewise.
	(forward_propagate_asm): Update for new df_ref linking.
	* df-scan.c (df_scan_free_ref_vec, df_scan_free_mws_vec): Delete.
	(df_null_ref_rec, df_null_mw_rec): Likewise.
	(df_scan_free_internal): Don't free df_ref and df_mw_hardreg lists
	explicitly.
	(df_scan_free_bb_info): Remove check for null artificial_defs.
	(df_install_ref_incremental): Adjust for new df_ref linking.
	Use a single-element insertion rather than a full sort.
	(df_ref_chain_delete_du_chain): Take the first element
	in a linked list as parameter, rather than a pointer to an array of
	pointers.
	(df_ref_chain_delete, df_mw_hardreg_chain_delete): Likewise.
	(df_add_refs_to_table, df_refs_verify, df_mws_verify): Likewise.
	(df_insn_info_delete): Remove check for null defs and call to
	df_scan_free_mws_vec.
	(df_insn_rescan): Initialize df_ref and df_mw_hardreg lists to
	null rather than df_null_*_rec.
	(df_insn_rescan_debug_internal): Likewise, and update null
	checks in the same way.  Remove check for null defs.
	(df_ref_change_reg_with_loc_1): Fix choice of list for defs.
	Move a single element rather doing a full sort.
	(df_mw_hardreg_chain_delete_eq_uses): Adjust for new df_mw_hardreg
	linking.
	(df_notes_rescan): Likewise.  Use a merge rather than a full sort.
	Initialize df_ref and df_mw_hardreg lists to null rather than
	df_null_*_rec.
	(df_ref_compare): Take df_refs as parameter, transferring the
	old interface to...
	(df_ref_ptr_compare): ...this new function.
	(df_sort_and_compress_refs): Update accordingly.
	(df_mw_compare): Take df_mw_hardregs as parameter, transferring the
	old interface to...
	(df_mw_ptr_compare): ...this new function.
	(df_sort_and_compress_mws): Update accordingly.
	(df_install_refs, df_install_mws): Return a linked list rather than
	an array of pointers.
	(df_refs_add_to_chains): Assert that old lists are empty rather
	than freeing them.
	(df_insn_refs_verify): Don't handle null defs speciailly.
	* web.c (union_match_dups): Update for new df_ref linking.

From-SVN: r211683

1 files changed, 181 insertions, 328 deletions

diff --git a/gcc/df-scan.c b/gcc/df-scan.c
index 0033d6d..f1ba808 100644
--- a/gcc/df-scan.c
+++ b/gcc/df-scan.c
@@ -62,21 +62,6 @@ typedef struct df_mw_hardreg *df_mw_hardreg_ptr;
 #define EPILOGUE_USES(REGNO)  0
 #endif
 
-/* The following two macros free the vecs that hold either the refs or
-   the mw refs.  They are a little tricky because the vec has 0
-   elements is special and is not to be freed.  */
-#define df_scan_free_ref_vec(V) \
-  do { \
-    if (V && *V) \
-      free (V);  \
-  } while (0)
-
-#define df_scan_free_mws_vec(V) \
-  do { \
-    if (V && *V) \
-      free (V);  \
-  } while (0)
-
 /* The set of hard registers in eliminables[i].from. */
 
 static HARD_REG_SET elim_reg_set;
@@ -92,9 +77,6 @@ struct df_collection_rec
   auto_vec<df_mw_hardreg_ptr, 32> mw_vec;
 };
 
-static df_ref df_null_ref_rec[1];
-static struct df_mw_hardreg * df_null_mw_rec[1];
-
 static void df_ref_record (enum df_ref_class, struct df_collection_rec *,
 			   rtx, rtx *,
 			   basic_block, struct df_insn_info *,
@@ -123,8 +105,8 @@ static void df_record_exit_block_uses (bitmap);
 static void df_get_exit_block_use_set (bitmap);
 static void df_get_entry_block_def_set (bitmap);
 static void df_grow_ref_info (struct df_ref_info *, unsigned int);
-static void df_ref_chain_delete_du_chain (df_ref *);
-static void df_ref_chain_delete (df_ref *);
+static void df_ref_chain_delete_du_chain (df_ref);
+static void df_ref_chain_delete (df_ref);
 
 static void df_refs_add_to_chains (struct df_collection_rec *,
 				   basic_block, rtx, unsigned int);
@@ -135,8 +117,10 @@ static void df_exit_block_uses_collect (struct df_collection_rec *, bitmap);
 static void df_install_ref (df_ref, struct df_reg_info *,
 			    struct df_ref_info *, bool);
 
-static int df_ref_compare (const void *, const void *);
-static int df_mw_compare (const void *, const void *);
+static int df_ref_compare (df_ref, df_ref);
+static int df_ref_ptr_compare (const void *, const void *);
+static int df_mw_compare (const df_mw_hardreg *, const df_mw_hardreg *);
+static int df_mw_ptr_compare (const void *, const void *);
 
 static void df_insn_info_delete (unsigned int);
 
@@ -189,36 +173,6 @@ df_scan_free_internal (void)
 {
   struct df_scan_problem_data *problem_data
     = (struct df_scan_problem_data *) df_scan->problem_data;
-  unsigned int i;
-  basic_block bb;
-
-  /* The vectors that hold the refs are not pool allocated because
-     they come in many sizes.  This makes them impossible to delete
-     all at once.  */
-  for (i = 0; i < DF_INSN_SIZE (); i++)
-    {
-      struct df_insn_info *insn_info = DF_INSN_UID_GET (i);
-      /* Skip the insns that have no insn_info or have been
-	 deleted.  */
-      if (insn_info)
-	{
-	  df_scan_free_ref_vec (insn_info->defs);
-	  df_scan_free_ref_vec (insn_info->uses);
-	  df_scan_free_ref_vec (insn_info->eq_uses);
-	  df_scan_free_mws_vec (insn_info->mw_hardregs);
-	}
-    }
-
-  FOR_ALL_BB_FN (bb, cfun)
-    {
-      unsigned int bb_index = bb->index;
-      struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb_index);
-      if (bb_info)
-	{
-	  df_scan_free_ref_vec (bb_info->artificial_defs);
-	  df_scan_free_ref_vec (bb_info->artificial_uses);
-	}
-    }
 
   free (df->def_info.refs);
   free (df->def_info.begin);
@@ -275,31 +229,22 @@ df_scan_free_bb_info (basic_block bb, void *vbb_info)
 {
   struct df_scan_bb_info *bb_info = (struct df_scan_bb_info *) vbb_info;
   unsigned int bb_index = bb->index;
+  rtx insn;
 
-  /* See if bb_info is initialized.  */
-  if (bb_info->artificial_defs)
-    {
-      rtx insn;
-      FOR_BB_INSNS (bb, insn)
-	{
-	  if (INSN_P (insn))
-	    df_insn_info_delete (INSN_UID (insn));
-	}
-
-      if (bb_index < df_scan->block_info_size)
-	bb_info = df_scan_get_bb_info (bb_index);
-
-      /* Get rid of any artificial uses or defs.  */
-      if (bb_info->artificial_defs)
-	{
-	  df_ref_chain_delete_du_chain (bb_info->artificial_defs);
-	  df_ref_chain_delete_du_chain (bb_info->artificial_uses);
-	  df_ref_chain_delete (bb_info->artificial_defs);
-	  df_ref_chain_delete (bb_info->artificial_uses);
-	  bb_info->artificial_defs = NULL;
-	  bb_info->artificial_uses = NULL;
-	}
-    }
+  FOR_BB_INSNS (bb, insn)
+    if (INSN_P (insn))
+      df_insn_info_delete (INSN_UID (insn));
+
+  if (bb_index < df_scan->block_info_size)
+    bb_info = df_scan_get_bb_info (bb_index);
+
+  /* Get rid of any artificial uses or defs.  */
+  df_ref_chain_delete_du_chain (bb_info->artificial_defs);
+  df_ref_chain_delete_du_chain (bb_info->artificial_uses);
+  df_ref_chain_delete (bb_info->artificial_defs);
+  df_ref_chain_delete (bb_info->artificial_uses);
+  bb_info->artificial_defs = NULL;
+  bb_info->artificial_uses = NULL;
 }
 
 
@@ -695,9 +640,7 @@ df_install_ref_incremental (df_ref ref)
 {
   struct df_reg_info **reg_info;
   struct df_ref_info *ref_info;
-  df_ref *ref_rec;
-  df_ref **ref_rec_ptr;
-  unsigned int count = 0;
+  df_ref *ref_ptr;
   bool add_to_table;
 
   rtx insn = DF_REF_INSN (ref);
@@ -707,14 +650,14 @@ df_install_ref_incremental (df_ref ref)
     {
       reg_info = df->def_regs;
       ref_info = &df->def_info;
-      ref_rec_ptr = &DF_INSN_DEFS (insn);
+      ref_ptr = &DF_INSN_DEFS (insn);
       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
     }
   else if (DF_REF_FLAGS (ref) & DF_REF_IN_NOTE)
     {
       reg_info = df->eq_use_regs;
       ref_info = &df->use_info;
-      ref_rec_ptr = &DF_INSN_EQ_USES (insn);
+      ref_ptr = &DF_INSN_EQ_USES (insn);
       switch (ref_info->ref_order)
 	{
 	case DF_REF_ORDER_UNORDERED_WITH_NOTES:
@@ -731,7 +674,7 @@ df_install_ref_incremental (df_ref ref)
     {
       reg_info = df->use_regs;
       ref_info = &df->use_info;
-      ref_rec_ptr = &DF_INSN_USES (insn);
+      ref_ptr = &DF_INSN_USES (insn);
       add_to_table = ref_info->ref_order != DF_REF_ORDER_NO_TABLE;
     }
 
@@ -754,29 +697,11 @@ df_install_ref_incremental (df_ref ref)
 	break;
       }
 
-  ref_rec = *ref_rec_ptr;
-  while (*ref_rec)
-    {
-      count++;
-      ref_rec++;
-    }
+  while (*ref_ptr && df_ref_compare (*ref_ptr, ref) < 0)
+    ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
 
-  ref_rec = *ref_rec_ptr;
-  if (count)
-    {
-      ref_rec = XRESIZEVEC (df_ref, ref_rec, count+2);
-      *ref_rec_ptr = ref_rec;
-      ref_rec[count] = ref;
-      ref_rec[count+1] = NULL;
-      qsort (ref_rec, count + 1, sizeof (df_ref), df_ref_compare);
-    }
-  else
-    {
-      df_ref *ref_rec = XNEWVEC (df_ref, 2);
-      ref_rec[0] = ref;
-      ref_rec[1] = NULL;
-      *ref_rec_ptr = ref_rec;
-    }
+  DF_REF_NEXT_LOC (ref) = *ref_ptr;
+  *ref_ptr = ref;
 
 #if 0
   if (dump_file)
@@ -930,55 +855,43 @@ df_insn_create_insn_record (rtx insn)
 /* Delete all du chain (DF_REF_CHAIN()) of all refs in the ref chain.  */
 
 static void
-df_ref_chain_delete_du_chain (df_ref *ref_rec)
+df_ref_chain_delete_du_chain (df_ref ref)
 {
-  while (*ref_rec)
-    {
-      df_ref ref = *ref_rec;
-      /* CHAIN is allocated by DF_CHAIN. So make sure to
-         pass df_scan instance for the problem.  */
-      if (DF_REF_CHAIN (ref))
-        df_chain_unlink (ref);
-      ref_rec++;
-    }
+  for (; ref; ref = DF_REF_NEXT_LOC (ref))
+    /* CHAIN is allocated by DF_CHAIN. So make sure to
+       pass df_scan instance for the problem.  */
+    if (DF_REF_CHAIN (ref))
+      df_chain_unlink (ref);
 }
 
 
 /* Delete all refs in the ref chain.  */
 
 static void
-df_ref_chain_delete (df_ref *ref_rec)
+df_ref_chain_delete (df_ref ref)
 {
-  df_ref *start = ref_rec;
-  while (*ref_rec)
+  df_ref next;
+  for (; ref; ref = next)
     {
-      df_reg_chain_unlink (*ref_rec);
-      ref_rec++;
+      next = DF_REF_NEXT_LOC (ref);
+      df_reg_chain_unlink (ref);
     }
-
-  /* If the list is empty, it has a special shared element that is not
-     to be deleted.  */
-  if (*start)
-    free (start);
 }
 
 
 /* Delete the hardreg chain.  */
 
 static void
-df_mw_hardreg_chain_delete (struct df_mw_hardreg **hardregs)
+df_mw_hardreg_chain_delete (struct df_mw_hardreg *hardregs)
 {
-  struct df_scan_problem_data *problem_data;
-
-  if (!hardregs)
-    return;
-
-  problem_data = (struct df_scan_problem_data *) df_scan->problem_data;
+  struct df_scan_problem_data *problem_data
+    = (struct df_scan_problem_data *) df_scan->problem_data;
+  df_mw_hardreg *next;
 
-  while (*hardregs)
+  for (; hardregs; hardregs = next)
     {
-      pool_free (problem_data->mw_reg_pool, *hardregs);
-      hardregs++;
+      next = DF_MWS_NEXT (hardregs);
+      pool_free (problem_data->mw_reg_pool, hardregs);
     }
 }
 
@@ -1006,22 +919,19 @@ df_insn_info_delete (unsigned int uid)
 	 to notes.  How clever.  So we cannot just check if it is a
 	 valid insn before short circuiting this code, we need to see
 	 if we actually initialized it.  */
-      if (insn_info->defs)
+      df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
+
+      if (df_chain)
 	{
-	  df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
+	  df_ref_chain_delete_du_chain (insn_info->defs);
+	  df_ref_chain_delete_du_chain (insn_info->uses);
+	  df_ref_chain_delete_du_chain (insn_info->eq_uses);
+	}
 
-	  if (df_chain)
-	    {
-	      df_ref_chain_delete_du_chain (insn_info->defs);
-	      df_ref_chain_delete_du_chain (insn_info->uses);
-	      df_ref_chain_delete_du_chain (insn_info->eq_uses);
-	    }
+      df_ref_chain_delete (insn_info->defs);
+      df_ref_chain_delete (insn_info->uses);
+      df_ref_chain_delete (insn_info->eq_uses);
 
-	  df_ref_chain_delete (insn_info->defs);
-	  df_ref_chain_delete (insn_info->uses);
-	  df_ref_chain_delete (insn_info->eq_uses);
-	  df_scan_free_mws_vec (insn_info->mw_hardregs);
-	}
       pool_free (problem_data->insn_pool, insn_info);
       DF_INSN_UID_SET (uid, NULL);
     }
@@ -1149,10 +1059,10 @@ df_insn_rescan (rtx insn)
       if (!insn_info)
 	{
 	  insn_info = df_insn_create_insn_record (insn);
-	  insn_info->defs = df_null_ref_rec;
-	  insn_info->uses = df_null_ref_rec;
-	  insn_info->eq_uses = df_null_ref_rec;
-	  insn_info->mw_hardregs = df_null_mw_rec;
+	  insn_info->defs = 0;
+	  insn_info->uses = 0;
+	  insn_info->eq_uses = 0;
+	  insn_info->mw_hardregs = 0;
 	}
       if (dump_file)
 	fprintf (dump_file, "deferring rescan insn with uid = %d.\n", uid);
@@ -1229,13 +1139,10 @@ df_insn_rescan_debug_internal (rtx insn)
   bitmap_clear_bit (&df->insns_to_rescan, uid);
   bitmap_clear_bit (&df->insns_to_notes_rescan, uid);
 
-  if (!insn_info->defs)
-    return false;
-
-  if (insn_info->defs == df_null_ref_rec
-      && insn_info->uses == df_null_ref_rec
-      && insn_info->eq_uses == df_null_ref_rec
-      && insn_info->mw_hardregs == df_null_mw_rec)
+  if (insn_info->defs == 0
+      && insn_info->uses == 0
+      && insn_info->eq_uses == 0
+      && insn_info->mw_hardregs == 0)
     return false;
 
   df_mw_hardreg_chain_delete (insn_info->mw_hardregs);
@@ -1250,12 +1157,11 @@ df_insn_rescan_debug_internal (rtx insn)
   df_ref_chain_delete (insn_info->defs);
   df_ref_chain_delete (insn_info->uses);
   df_ref_chain_delete (insn_info->eq_uses);
-  df_scan_free_mws_vec (insn_info->mw_hardregs);
 
-  insn_info->defs = df_null_ref_rec;
-  insn_info->uses = df_null_ref_rec;
-  insn_info->eq_uses = df_null_ref_rec;
-  insn_info->mw_hardregs = df_null_mw_rec;
+  insn_info->defs = 0;
+  insn_info->uses = 0;
+  insn_info->eq_uses = 0;
+  insn_info->mw_hardregs = 0;
 
   return true;
 }
@@ -1682,19 +1588,15 @@ df_reorganize_refs_by_reg (struct df_ref_info *ref_info,
 static unsigned int
 df_add_refs_to_table (unsigned int offset,
 		      struct df_ref_info *ref_info,
-		      df_ref *ref_vec)
+		      df_ref ref)
 {
-  while (*ref_vec)
-    {
-      df_ref ref = *ref_vec;
-      if ((!(df->changeable_flags & DF_NO_HARD_REGS))
-	  || (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
-	{
-	  ref_info->refs[offset] = ref;
-	  DF_REF_ID (*ref_vec) = offset++;
-	}
-      ref_vec++;
-    }
+  for (; ref; ref = DF_REF_NEXT_LOC (ref))
+    if (!(df->changeable_flags & DF_NO_HARD_REGS)
+	|| (DF_REF_REGNO (ref) >= FIRST_PSEUDO_REGISTER))
+      {
+	ref_info->refs[offset] = ref;
+	DF_REF_ID (ref) = offset++;
+      }
   return offset;
 }
 
@@ -1921,9 +1823,8 @@ df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
 	{
 	  df_ref next_ref = DF_REF_NEXT_REG (the_ref);
 	  df_ref prev_ref = DF_REF_PREV_REG (the_ref);
-	  df_ref *ref_vec, *ref_vec_t;
+	  df_ref *ref_ptr;
 	  struct df_insn_info *insn_info = DF_REF_INSN_INFO (the_ref);
-	  unsigned int count = 0;
 
 	  DF_REF_REGNO (the_ref) = new_regno;
 	  DF_REF_REG (the_ref) = regno_reg_rtx[new_regno];
@@ -1950,23 +1851,42 @@ df_ref_change_reg_with_loc_1 (struct df_reg_info *old_df,
 	  /* Need to sort the record again that the ref was in because
 	     the regno is a sorting key.  First, find the right
 	     record.  */
-	  if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
-	    ref_vec = insn_info->eq_uses;
+	  if (DF_REF_REG_DEF_P (the_ref))
+	    ref_ptr = &insn_info->defs;
+	  else if (DF_REF_FLAGS (the_ref) & DF_REF_IN_NOTE)
+	    ref_ptr = &insn_info->eq_uses;
 	  else
-	    ref_vec = insn_info->uses;
+	    ref_ptr = &insn_info->uses;
 	  if (dump_file)
 	    fprintf (dump_file, "changing reg in insn %d\n",
 		     DF_REF_INSN_UID (the_ref));
 
-	  ref_vec_t = ref_vec;
-
-	  /* Find the length.  */
-	  while (*ref_vec_t)
+	  /* Stop if we find the current reference or where the reference
+	     needs to be.  */
+	  while (*ref_ptr != the_ref && df_ref_compare (*ref_ptr, the_ref) < 0)
+	    ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
+	  if (*ref_ptr != the_ref)
 	    {
-	      count++;
-	      ref_vec_t++;
+	      /* The reference needs to be promoted up the list.  */
+	      df_ref next = DF_REF_NEXT_LOC (the_ref);
+	      DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
+	      *ref_ptr = the_ref;
+	      do
+		ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
+	      while (*ref_ptr != the_ref);
+	      *ref_ptr = next;
+	    }
+	  else if (DF_REF_NEXT_LOC (the_ref)
+		   && df_ref_compare (the_ref, DF_REF_NEXT_LOC (the_ref)) > 0)
+	    {
+	      /* The reference needs to be demoted down the list.  */
+	      *ref_ptr = DF_REF_NEXT_LOC (the_ref);
+	      do
+		ref_ptr = &DF_REF_NEXT_LOC (*ref_ptr);
+	      while (*ref_ptr && df_ref_compare (the_ref, *ref_ptr) > 0);
+	      DF_REF_NEXT_LOC (the_ref) = *ref_ptr;
+	      *ref_ptr = the_ref;
 	    }
-	  qsort (ref_vec, count, sizeof (df_ref ), df_ref_compare);
 
 	  the_ref = next_ref;
 	}
@@ -2000,51 +1920,24 @@ df_ref_change_reg_with_loc (int old_regno, int new_regno, rtx loc)
 
 /* Delete the mw_hardregs that point into the eq_notes.  */
 
-static unsigned int
+static void
 df_mw_hardreg_chain_delete_eq_uses (struct df_insn_info *insn_info)
 {
-  struct df_mw_hardreg **mw_vec = insn_info->mw_hardregs;
-  unsigned int deleted = 0;
-  unsigned int count = 0;
+  struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs;
   struct df_scan_problem_data *problem_data
     = (struct df_scan_problem_data *) df_scan->problem_data;
 
-  if (!*mw_vec)
-    return 0;
-
-  while (*mw_vec)
+  while (*mw_ptr)
     {
-      if ((*mw_vec)->flags & DF_REF_IN_NOTE)
+      df_mw_hardreg *mw = *mw_ptr;
+      if (mw->flags & DF_REF_IN_NOTE)
 	{
-	  struct df_mw_hardreg **temp_vec = mw_vec;
-
-	  pool_free (problem_data->mw_reg_pool, *mw_vec);
-	  temp_vec = mw_vec;
-	  /* Shove the remaining ones down one to fill the gap.  While
-	     this looks n**2, it is highly unusual to have any mw regs
-	     in eq_notes and the chances of more than one are almost
-	     non existent.  */
-	  while (*temp_vec)
-	    {
-	      *temp_vec = *(temp_vec + 1);
-	      temp_vec++;
-	    }
-	  deleted++;
+	  *mw_ptr = DF_MWS_NEXT (mw);
+	  pool_free (problem_data->mw_reg_pool, mw);
 	}
       else
-	{
-	  mw_vec++;
-	  count++;
-	}
+	mw_ptr = &DF_MWS_NEXT (mw);
     }
-
-  if (count == 0)
-    {
-      df_scan_free_mws_vec (insn_info->mw_hardregs);
-      insn_info->mw_hardregs = df_null_mw_rec;
-      return 0;
-    }
-  return deleted;
 }
 
 
@@ -2078,10 +1971,10 @@ df_notes_rescan (rtx insn)
       if (!insn_info)
 	{
 	  insn_info = df_insn_create_insn_record (insn);
-	  insn_info->defs = df_null_ref_rec;
-	  insn_info->uses = df_null_ref_rec;
-	  insn_info->eq_uses = df_null_ref_rec;
-	  insn_info->mw_hardregs = df_null_mw_rec;
+	  insn_info->defs = 0;
+	  insn_info->uses = 0;
+	  insn_info->eq_uses = 0;
+	  insn_info->mw_hardregs = 0;
 	}
 
       bitmap_clear_bit (&df->insns_to_delete, uid);
@@ -2100,10 +1993,9 @@ df_notes_rescan (rtx insn)
       basic_block bb = BLOCK_FOR_INSN (insn);
       rtx note;
       struct df_collection_rec collection_rec;
-      unsigned int num_deleted;
-      unsigned int mw_len;
+      unsigned int i;
 
-      num_deleted = df_mw_hardreg_chain_delete_eq_uses (insn_info);
+      df_mw_hardreg_chain_delete_eq_uses (insn_info);
       df_ref_chain_delete (insn_info->eq_uses);
       insn_info->eq_uses = NULL;
 
@@ -2125,45 +2017,14 @@ df_notes_rescan (rtx insn)
 
       /* Find some place to put any new mw_hardregs.  */
       df_canonize_collection_rec (&collection_rec);
-      mw_len = collection_rec.mw_vec.length ();
-      if (mw_len)
+      struct df_mw_hardreg **mw_ptr = &insn_info->mw_hardregs, *mw;
+      FOR_EACH_VEC_ELT (collection_rec.mw_vec, i, mw)
 	{
-	  unsigned int count = 0;
-	  struct df_mw_hardreg **mw_rec = insn_info->mw_hardregs;
-	  while (*mw_rec)
-	    {
-	      count++;
-	      mw_rec++;
-	    }
-
-	  if (count)
-	    {
-	      /* Append to the end of the existing record after
-		 expanding it if necessary.  */
-	      if (mw_len > num_deleted)
-		{
-		  insn_info->mw_hardregs =
-		    XRESIZEVEC (struct df_mw_hardreg *,
-				insn_info->mw_hardregs,
-				count + 1 + mw_len);
-		}
-	      memcpy (&insn_info->mw_hardregs[count],
-		      collection_rec.mw_vec.address (),
-		      mw_len * sizeof (struct df_mw_hardreg *));
-	      insn_info->mw_hardregs[count + mw_len] = NULL;
-	      qsort (insn_info->mw_hardregs, count + mw_len,
-		     sizeof (struct df_mw_hardreg *), df_mw_compare);
-	    }
-	  else
-	    {
-	      /* No vector there. */
-	      insn_info->mw_hardregs
-		= XNEWVEC (struct df_mw_hardreg*, 1 + mw_len);
-	      memcpy (insn_info->mw_hardregs,
-		      collection_rec.mw_vec.address (),
-		      mw_len * sizeof (struct df_mw_hardreg *));
-	      insn_info->mw_hardregs[mw_len] = NULL;
-	    }
+	  while (*mw_ptr && df_mw_compare (*mw_ptr, mw) < 0)
+	    mw_ptr = &DF_MWS_NEXT (*mw_ptr);
+	  DF_MWS_NEXT (mw) = *mw_ptr;
+	  *mw_ptr = mw;
+	  mw_ptr = &DF_MWS_NEXT (mw);
 	}
       df_refs_add_to_chains (&collection_rec, bb, insn, copy_eq_uses);
     }
@@ -2222,14 +2083,8 @@ df_ref_equal_p (df_ref ref1, df_ref ref2)
    have the same bb.  So these fields are not checked.  */
 
 static int
-df_ref_compare (const void *r1, const void *r2)
+df_ref_compare (df_ref ref1, df_ref ref2)
 {
-  const df_ref ref1 = *(const df_ref *)r1;
-  const df_ref ref2 = *(const df_ref *)r2;
-
-  if (ref1 == ref2)
-    return 0;
-
   if (DF_REF_CLASS (ref1) != DF_REF_CLASS (ref2))
     return (int)DF_REF_CLASS (ref1) - (int)DF_REF_CLASS (ref2);
 
@@ -2264,6 +2119,14 @@ df_ref_compare (const void *r1, const void *r2)
   return (int)DF_REF_ORDER (ref1) - (int)DF_REF_ORDER (ref2);
 }
 
+/* Like df_ref_compare, but compare two df_ref* pointers R1 and R2.  */
+
+static int
+df_ref_ptr_compare (const void *r1, const void *r2)
+{
+  return df_ref_compare (*(const df_ref *) r1, *(const df_ref *) r2);
+}
+
 static void
 df_swap_refs (vec<df_ref, va_heap> *ref_vec, int i, int j)
 {
@@ -2290,7 +2153,7 @@ df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
     {
       df_ref r0 = (*ref_vec)[0];
       df_ref r1 = (*ref_vec)[1];
-      if (df_ref_compare (&r0, &r1) > 0)
+      if (df_ref_compare (r0, r1) > 0)
         df_swap_refs (ref_vec, 0, 1);
     }
   else
@@ -2299,7 +2162,7 @@ df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
 	{
 	  df_ref r0 = (*ref_vec)[i];
 	  df_ref r1 = (*ref_vec)[i + 1];
-	  if (df_ref_compare (&r0, &r1) >= 0)
+	  if (df_ref_compare (r0, r1) >= 0)
 	    break;
 	}
       /* If the array is already strictly ordered,
@@ -2311,7 +2174,7 @@ df_sort_and_compress_refs (vec<df_ref, va_heap> *ref_vec)
          of DF_REF_COMPARE.  */
       if (i == count - 1)
         return;
-      ref_vec->qsort (df_ref_compare);
+      ref_vec->qsort (df_ref_ptr_compare);
     }
 
   for (i=0; i<count-dist; i++)
@@ -2354,14 +2217,8 @@ df_mw_equal_p (struct df_mw_hardreg *mw1, struct df_mw_hardreg *mw2)
 /* Compare MW1 and MW2 for sorting.  */
 
 static int
-df_mw_compare (const void *m1, const void *m2)
+df_mw_compare (const df_mw_hardreg *mw1, const df_mw_hardreg *mw2)
 {
-  const struct df_mw_hardreg *const mw1 = *(const struct df_mw_hardreg *const*)m1;
-  const struct df_mw_hardreg *const mw2 = *(const struct df_mw_hardreg *const*)m2;
-
-  if (mw1 == mw2)
-    return 0;
-
   if (mw1->type != mw2->type)
     return mw1->type - mw2->type;
 
@@ -2380,6 +2237,14 @@ df_mw_compare (const void *m1, const void *m2)
   return 0;
 }
 
+/* Like df_mw_compare, but compare two df_mw_hardreg** pointers R1 and R2.  */
+
+static int
+df_mw_ptr_compare (const void *m1, const void *m2)
+{
+  return df_mw_compare (*(const df_mw_hardreg *const *) m1,
+			*(const df_mw_hardreg *const *) m2);
+}
 
 /* Sort and compress a set of refs.  */
 
@@ -2399,7 +2264,7 @@ df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
     {
       struct df_mw_hardreg *m0 = (*mw_vec)[0];
       struct df_mw_hardreg *m1 = (*mw_vec)[1];
-      if (df_mw_compare (&m0, &m1) > 0)
+      if (df_mw_compare (m0, m1) > 0)
         {
           struct df_mw_hardreg *tmp = (*mw_vec)[0];
 	  (*mw_vec)[0] = (*mw_vec)[1];
@@ -2407,7 +2272,7 @@ df_sort_and_compress_mws (vec<df_mw_hardreg_ptr, va_heap> *mw_vec)
         }
     }
   else
-    mw_vec->qsort (df_mw_compare);
+    mw_vec->qsort (df_mw_ptr_compare);
 
   for (i=0; i<count-dist; i++)
     {
@@ -2493,7 +2358,7 @@ df_install_ref (df_ref this_ref,
    eq_uses) and installs the entire group into the insn.  It also adds
    each of these refs into the appropriate chains.  */
 
-static df_ref *
+static df_ref
 df_install_refs (basic_block bb,
 		 const vec<df_ref, va_heap> *old_vec,
 		 struct df_reg_info **reg_info,
@@ -2503,7 +2368,6 @@ df_install_refs (basic_block bb,
   unsigned int count = old_vec->length ();
   if (count)
     {
-      df_ref *new_vec = XNEWVEC (df_ref, count + 1);
       bool add_to_table;
       df_ref this_ref;
       unsigned int ix;
@@ -2533,37 +2397,35 @@ df_install_refs (basic_block bb,
 
       FOR_EACH_VEC_ELT (*old_vec, ix, this_ref)
 	{
-	  new_vec[ix] = this_ref;
+	  DF_REF_NEXT_LOC (this_ref) = (ix + 1 < old_vec->length ()
+					? (*old_vec)[ix + 1]
+					: NULL);
 	  df_install_ref (this_ref, reg_info[DF_REF_REGNO (this_ref)],
 			  ref_info, add_to_table);
 	}
-
-      new_vec[count] = NULL;
-      return new_vec;
+      return (*old_vec)[0];
     }
   else
-    return df_null_ref_rec;
+    return 0;
 }
 
 
 /* This function takes the mws installs the entire group into the
    insn.  */
 
-static struct df_mw_hardreg **
+static struct df_mw_hardreg *
 df_install_mws (const vec<df_mw_hardreg_ptr, va_heap> *old_vec)
 {
   unsigned int count = old_vec->length ();
   if (count)
     {
-      struct df_mw_hardreg **new_vec
-	= XNEWVEC (struct df_mw_hardreg*, count + 1);
-      memcpy (new_vec, old_vec->address (),
-	      sizeof (struct df_mw_hardreg*) * count);
-      new_vec[count] = NULL;
-      return new_vec;
+      for (unsigned int i = 0; i < count - 1; i++)
+	DF_MWS_NEXT ((*old_vec)[i]) = (*old_vec)[i + 1];
+      DF_MWS_NEXT ((*old_vec)[count - 1]) = 0;
+      return (*old_vec)[0];
     }
   else
-    return df_null_mw_rec;
+    return 0;
 }
 
 
@@ -2582,7 +2444,7 @@ df_refs_add_to_chains (struct df_collection_rec *collection_rec,
 	 chain specially.  */
       if (flags & copy_defs)
 	{
-	  df_scan_free_ref_vec (insn_rec->defs);
+	  gcc_checking_assert (!insn_rec->defs);
 	  insn_rec->defs
 	    = df_install_refs (bb, &collection_rec->def_vec,
 			       df->def_regs,
@@ -2590,7 +2452,7 @@ df_refs_add_to_chains (struct df_collection_rec *collection_rec,
 	}
       if (flags & copy_uses)
 	{
-	  df_scan_free_ref_vec (insn_rec->uses);
+	  gcc_checking_assert (!insn_rec->uses);
 	  insn_rec->uses
 	    = df_install_refs (bb, &collection_rec->use_vec,
 			       df->use_regs,
@@ -2598,7 +2460,7 @@ df_refs_add_to_chains (struct df_collection_rec *collection_rec,
 	}
       if (flags & copy_eq_uses)
 	{
-	  df_scan_free_ref_vec (insn_rec->eq_uses);
+	  gcc_checking_assert (!insn_rec->eq_uses);
 	  insn_rec->eq_uses
 	    = df_install_refs (bb, &collection_rec->eq_use_vec,
 			       df->eq_use_regs,
@@ -2606,7 +2468,7 @@ df_refs_add_to_chains (struct df_collection_rec *collection_rec,
 	}
       if (flags & copy_mw)
 	{
-	  df_scan_free_mws_vec (insn_rec->mw_hardregs);
+	  gcc_checking_assert (!insn_rec->mw_hardregs);
 	  insn_rec->mw_hardregs
 	    = df_install_mws (&collection_rec->mw_vec);
 	}
@@ -2615,12 +2477,12 @@ df_refs_add_to_chains (struct df_collection_rec *collection_rec,
     {
       struct df_scan_bb_info *bb_info = df_scan_get_bb_info (bb->index);
 
-      df_scan_free_ref_vec (bb_info->artificial_defs);
+      gcc_checking_assert (!bb_info->artificial_defs);
       bb_info->artificial_defs
 	= df_install_refs (bb, &collection_rec->def_vec,
 			   df->def_regs,
 			   &df->def_info, false);
-      df_scan_free_ref_vec (bb_info->artificial_uses);
+      gcc_checking_assert (!bb_info->artificial_uses);
       bb_info->artificial_uses
 	= df_install_refs (bb, &collection_rec->use_vec,
 			   df->use_regs,
@@ -4194,7 +4056,7 @@ df_reg_chain_verify_unmarked (df_ref refs)
 /* Verify that NEW_REC and OLD_REC have exactly the same members. */
 
 static bool
-df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref *old_rec,
+df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref old_rec,
 		bool abort_if_fail)
 {
   unsigned int ix;
@@ -4202,7 +4064,7 @@ df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref *old_rec,
 
   FOR_EACH_VEC_ELT (*new_rec, ix, new_ref)
     {
-      if (*old_rec == NULL || !df_ref_equal_p (new_ref, *old_rec))
+      if (old_rec == NULL || !df_ref_equal_p (new_ref, old_rec))
 	{
 	  if (abort_if_fail)
 	    gcc_assert (0);
@@ -4214,17 +4076,17 @@ df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref *old_rec,
 	 that is the context, mark this reg as being seem.  */
       if (abort_if_fail)
 	{
-	  gcc_assert (DF_REF_IS_REG_MARKED (*old_rec));
-	  DF_REF_REG_UNMARK (*old_rec);
+	  gcc_assert (DF_REF_IS_REG_MARKED (old_rec));
+	  DF_REF_REG_UNMARK (old_rec);
 	}
 
-      old_rec++;
+      old_rec = DF_REF_NEXT_LOC (old_rec);
     }
 
   if (abort_if_fail)
-    gcc_assert (*old_rec == NULL);
+    gcc_assert (old_rec == NULL);
   else
-    return *old_rec == NULL;
+    return old_rec == NULL;
   return false;
 }
 
@@ -4233,7 +4095,7 @@ df_refs_verify (const vec<df_ref, va_heap> *new_rec, df_ref *old_rec,
 
 static bool
 df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
-	       struct df_mw_hardreg **old_rec,
+	       struct df_mw_hardreg *old_rec,
 	       bool abort_if_fail)
 {
   unsigned int ix;
@@ -4241,20 +4103,20 @@ df_mws_verify (const vec<df_mw_hardreg_ptr, va_heap> *new_rec,
 
   FOR_EACH_VEC_ELT (*new_rec, ix, new_reg)
     {
-      if (*old_rec == NULL || !df_mw_equal_p (new_reg, *old_rec))
+      if (old_rec == NULL || !df_mw_equal_p (new_reg, old_rec))
 	{
 	  if (abort_if_fail)
 	    gcc_assert (0);
 	  else
 	    return false;
 	}
-      old_rec++;
+      old_rec = DF_MWS_NEXT (old_rec);
     }
 
   if (abort_if_fail)
-    gcc_assert (*old_rec == NULL);
+    gcc_assert (old_rec == NULL);
   else
-    return *old_rec == NULL;
+    return old_rec == NULL;
   return false;
 }
 
@@ -4282,15 +4144,6 @@ df_insn_refs_verify (struct df_collection_rec *collection_rec,
 
   df_insn_refs_collect (collection_rec, bb, insn_info);
 
-  if (!DF_INSN_UID_DEFS (uid))
-    {
-      /* The insn_rec was created but it was never filled out.  */
-      if (abort_if_fail)
-	gcc_assert (0);
-      else
-	return false;
-    }
-
   /* Unfortunately we cannot opt out early if one of these is not
      right because the marks will not get cleared.  */
   ret1 = df_refs_verify (&collection_rec->def_vec, DF_INSN_UID_DEFS (uid),