[committed 7/13][odr] Combine decls duplicate chain with def duplicate chain

[committed 7/13][odr] Combine decls duplicate chain with def duplicate chain

[Tom de Vries]

Hi,

Add an optimization mode ODR_LINK in which we combine the decl chain with one
of the defs chains.

The duplicate chain containing the decls, combined with one type of def cannot
be handled by the backend if it starts with a decl.  So, we reorder it to
make sure it doesn't start with a decl.

We do this reordering ALAP, because the order of the duplicate chain is
required to be in increasing die_cu (die)->cu_chunk order starting from
the qsort in partition_dups (which sorts the array with duplicate chains into
equivalence classes with the same set of referrer CUs) up until the outer
loops of partition_dups_1 (which determine the equivalence class boundaries in
the array with duplicate chains).

Committed to trunk.

Thanks,
- Tom

[odr] Combine decls duplicate chain with def duplicate chain

2020-01-06  Tom de Vries  <tdevries@suse.de>

	* dwz.c (enum odr_mode): New enum.
	(merge_dups): New function.
	(split_dups): Call merge_dups if odr_mode != ODR_BASIC.
	(reorder_dups): New function.
	(partition_dups_1): Call reorder_dups if odr_mode != ODR_BASIC.

---
 dwz.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 140 insertions(+), 3 deletions(-)

diff --git a/dwz.c b/dwz.c
index 9684adc..661cdb0 100644
--- a/dwz.c
+++ b/dwz.c
@@ -214,6 +214,8 @@ enum die_count_methods
 static enum die_count_methods die_count_method = estimate;
 
 int odr = 0;
+enum odr_mode { ODR_BASIC, ODR_LINK };
+enum odr_mode odr_mode = ODR_LINK;
 
 typedef struct
 {
@@ -6234,9 +6236,67 @@ sort_dups (dw_die_ref head)
   head->die_nextdup = prev;
 }
 
+/* Merge duplicate chains D and D2, and return the head of the merged
+chain.  */
+static dw_die_ref
+merge_dups (dw_die_ref d, dw_die_ref d2)
+{
+  if (d == NULL)
+    return d2;
+  if (d2 == NULL)
+    return d;
+
+  dw_die_ref tail = NULL;
+  dw_die_ref head = NULL;
+  while (true)
+    {
+      dw_die_ref next;
+      if (d && d2)
+	{
+	  if (d->die_offset < d2->die_offset)
+	    {
+	      next = d;
+	      d = d->die_nextdup;
+	    }
+	  else
+	    {
+	      next = d2;
+	      d2 = d2->die_nextdup;
+	    }
+	}
+      else if (d)
+	{
+	  next = d;
+	  d = d->die_nextdup;
+	}
+      else if (d2)
+	{
+	  next = d2;
+	  d2 = d2->die_nextdup;
+	}
+      else
+	break;
+      if (!head)
+	head = next;
+      if (tail)
+	tail->die_nextdup = next;
+      tail = next;
+    }
+
+  for (d = head; d; d = d->die_nextdup)
+    if (d == head)
+      d->die_dup = NULL;
+    else
+      d->die_dup = head;
+
+  if (unlikely (verify_dups_p))
+    verify_dups (head, true);
+  return head;
+}
+
 /* Split maximal duplicate chain DIE into smaller chains that contain
-   structurally equal defs.  Return the first chain, and call
-   partition_found_dups for the others.  */
+   structurally equal defs, and combine the decls with one of those.
+   Return the first chain, and call partition_found_dups for the others.  */
 static dw_die_ref
 split_dups (dw_die_ref die, struct obstack *vec)
 {
@@ -6277,6 +6337,7 @@ split_dups (dw_die_ref die, struct obstack *vec)
 	d->die_dup = head;
       tail = d;
     }
+  dw_die_ref decls = head;
 
   /* Build def duplicate chains.  */
   unsigned int j;
@@ -6299,6 +6360,24 @@ split_dups (dw_die_ref die, struct obstack *vec)
       sort_dups (d);
     }
 
+  if (odr_mode != ODR_BASIC)
+    {
+      /* Find the first duplicate chain containing defs.  */
+      dw_die_ref def = NULL;
+      for (i = 0; i < count; i++)
+	{
+	  d = arr[i];
+	  if (die_odr_state (NULL, d) == ODR_DECL
+	      || d->die_dup != NULL)
+	    continue;
+	  def = d;
+	  break;
+	}
+
+      /* Merge the def chain with the decls.  */
+      merge_dups (def, decls);
+    }
+
   /* If some DIEs are no longer part of a duplicate chain, don't remove
      them.  */
   for (i = 0; i < count; i++)
@@ -6358,6 +6437,62 @@ partition_find_dups (struct obstack *vec, dw_die_ref parent)
     }
 }
 
+/* Reorder duplicate chain DIE to make sure it doesn't start with a decl.  */
+static dw_die_ref
+reorder_dups (dw_die_ref die)
+{
+  unsigned decl_count = 0;
+  unsigned def_count = 0;
+  dw_die_ref d;
+
+  if (die_odr_state (NULL, die) == ODR_NONE)
+    return die;
+
+  for (d = die; d; d = d->die_nextdup)
+    {
+      if (die_odr_state (NULL, d) == ODR_DECL)
+	decl_count++;
+      else
+	def_count++;
+    }
+  if (def_count == 0 || decl_count == 0)
+    return die;
+
+  if (die_odr_state (NULL, die) != ODR_DECL)
+    return die;
+
+  dw_die_ref def = NULL;
+  dw_die_ref prev = NULL;
+  for (d = die; d; prev = d, d = d->die_nextdup)
+    {
+      if (die_odr_state (NULL, d) == ODR_DECL)
+	continue;
+      def = d;
+      break;
+    }
+
+  assert (!die->die_remove);
+  assert (def->die_remove);
+  def->die_remove = 0;
+  die->die_remove = 1;
+  def->die_ref_seen = die->die_ref_seen;
+  dw_die_ref next = def->die_nextdup;
+  if (prev)
+    prev->die_nextdup = next;
+  def->die_nextdup = die;
+  for (d = def; d; prev = d, d = d->die_nextdup)
+    {
+      if (d == def)
+	d->die_dup = NULL;
+      else
+	d->die_dup = def;
+    }
+
+  if (unlikely (verify_dups_p))
+    verify_dups (def, false);
+  return def;
+}
+
 /* Copy DIE tree of DIE, as children of new DIE PARENT.  */
 static dw_die_ref
 copy_die_tree (dw_die_ref parent, dw_die_ref die)
@@ -6565,11 +6700,13 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
 	      dw_die_ref child;
 	      if (second_phase && !arr[k]->die_ref_seen)
 		continue;
+	      if (odr && odr_mode != ODR_BASIC)
+		arr[k] = reorder_dups (arr[k]);
 	      child = copy_die_tree (die, arr[k]);
 	      for (ref = arr[k]->die_nextdup; ref; ref = ref->die_nextdup)
 		ref->die_dup = child;
 	      if (unlikely (verify_dups_p))
-		verify_dups (child, true);
+		verify_dups (child, odr_mode == ODR_BASIC);
 	      if (namespaces)
 		{
 		  for (ref = arr[k]->die_parent;