[committed] Add --devel-gen-cu

[committed] Add --devel-gen-cu

[Tom de Vries]

Hi,

The DWARF standard appendix E.1 describes techniques that can be used for
compression and deduplication.

It explains that DIEs can be factored out into a PU (a compilation unit with
root DIE using DW_TAG_partial_unit), provided the PUs are then imported by
the CUs from which the DIEs where factored out.  This is what dwz implements.

But it explains as well that DIEs can be factored out into a CU (a compilation
unit with root DIE using DW_TAG_compile_unit), which dwz currently doesn't
implement.  This only works for DIEs that are globally visible, something
that is not generally valid, but is the case for C++.  The benefit of
factoring out into CUs is that imports are not required.

Given a partition of duplication chains, if the set of originating CUs are
all C++ CUs, then use a DW_TAG_compile_unit instead of a DW_TAG_partial_unit,
and don't use imports.

We will show here the effect of the option on the cc1 benchmark:
...
$ dwz -lnone cc1 -o 1 --devel-no-uni-lang --devel-no-gen-cu
$ dwz -lnone cc1 -o 2 --devel-no-uni-lang --devel-gen-cu
$ dwz -lnone cc1 -o 3 --devel-uni-lang --devel-no-gen-cu
$ dwz -lnone cc1 -o 4 --devel-uni-lang --devel-gen-cu
...

The benchmark consists of this many CUs:
...
$ readelf -wi cc1 \
  | egrep "\(DW_TAG_(compile|partial)_unit" \
  | awk '{print $5}' \
  | sort \
  | uniq -c
    695 (DW_TAG_compile_unit)
...

After normal compression, we have (file 1):
...
    695 (DW_TAG_compile_unit)
   4206 (DW_TAG_partial_unit)
...

Using --devel-gen-cu (file 2), we get the same result.

Using --devel-uni-lang (file 3), we get slightly less partial units:
...
    695 (DW_TAG_compile_unit)
   4143 (DW_TAG_partial_unit)
...

And when using both --devel-uni-lang and --devel-gen-cu (file 4), we get:
...
   3820 (DW_TAG_compile_unit)
    121 (DW_TAG_partial_unit)
...

The size effect for this example seems to be in the noise range:
...
$ diff.sh cc1 1
.debug_info      red: 44.84%    111527248  61527733
.debug_abbrev    red: 40.28%    1722726  1028968
.debug_str       red: 0%        6609355  6609355
total            red: 42.30%    119859329 69166056
$ diff.sh cc1 2
.debug_info      red: 44.84%    111527248  61527733
.debug_abbrev    red: 40.28%    1722726  1028968
.debug_str       red: 0%        6609355  6609355
total            red: 42.30%    119859329 69166056
$ diff.sh cc1 3
.debug_info      red: 44.84%    111527248  61521767
.debug_abbrev    red: 39.99%    1722726  1033916
.debug_str       red: 0%        6609355  6609355
total            red: 42.30%    119859329 69165038
$ diff.sh cc1 4
.debug_info      red: 44.89%    111527248  61463616
.debug_abbrev    red: 40.20%    1722726  1030280
.debug_str       red: 0%        6609355  6609355
total            red: 42.35%    119859329 69103251
...

Tested on-by-default, in combination with --devel-uni-lang on-by-default.

In that configuration, tested:
- regression testsuite, and
- gdb testsuite using board cc-with-dwz and cc-with-dwz-m.

With the external regression test suite, we see this regression:
...
Running src/testsuite/dwz-external.tests/dwz-external-tests.exp ...
dwz: 1: DWARF compression not beneficial - old size 69210922 new size 69428282
FAIL: src/testsuite/dwz-external.tests/pr24204.sh
...

The test-case uses cc1.dwz-processed, a cc1 binary that has already been
dwz-compressed using an older dwz.  I presume the FAIL to be due to
PR25566 - "[dwz] Take reference size into account in heuristics".

Committed to trunk.

Thanks,
- Tom

Add --devel-gen-cu

2020-02-19  Tom de Vries  <tdevries@suse.de>

	* dwz.c (gen_cu_p): New variable.
	(partition_lang): New function.
	(partition_dups_1): Create compilation unit with root DIE using tag
	DW_TAG_compile_unit, if allowed.  Update heuristics.
	(create_import_tree): Skip compilation unit with root DIE using tag
	DW_TAG_compile_unit.  Assert no imports are generated for such
	compilation units.
	(build_abbrevs_for_die): Add DW_AT_language attribute for compilation
	unit root DIE using tag DW_TAG_compile_unit.

---
 dwz.c | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 52 insertions(+), 6 deletions(-)

diff --git a/dwz.c b/dwz.c
index 344e1ee..7ec0623 100644
--- a/dwz.c
+++ b/dwz.c
@@ -220,6 +220,7 @@ enum deduplication_mode
 };
 static enum deduplication_mode deduplication_mode = dm_inter_cu;
 static int uni_lang_p = 0;
+static int gen_cu_p = 0;
 enum die_count_methods
 {
   none,
@@ -6888,6 +6889,33 @@ copy_die_tree (dw_die_ref parent, dw_die_ref die)
   return new_die;
 }
 
+/* If all DIEs in the duplication chain DIE are in CUs with the same
+   language, return that language.  Otherwise, return 0.  */
+static enum dwarf_source_language
+partition_lang (dw_die_ref die)
+{
+  enum dwarf_source_language lang;
+  dw_die_ref d;
+
+  if (die == NULL)
+    return 0;
+
+  lang = die_cu (die)->lang;
+  switch (lang)
+    {
+    case DW_LANG_C_plus_plus:
+      break;
+    default:
+      return 0;
+    }
+
+  for (d = die->die_nextdup; d; d = d->die_nextdup)
+    if (die_cu (d)->lang != lang)
+      return 0;
+
+  return lang;
+}
+
 /* Return how many bytes we need to encode VAL.  */
 static unsigned int
 nr_bytes_for (uint64_t val)
@@ -6967,6 +6995,8 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
 	      cnt++;
 	    }
 	}
+      enum dwarf_source_language part_lang
+	= gen_cu_p ? partition_lang (arr[i]) : 0;
       for (k = i; k < j; k++)
 	{
 	  if (second_phase && arr[k]->die_ref_seen)
@@ -7032,7 +7062,7 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
       orig_size = size * cnt;
       /* Estimated size of CU header and DW_TAG_partial_unit
 	 with DW_AT_stmt_list and DW_AT_comp_dir attributes
-	 21 (also child end byte).  */
+	 21 (also child end byte).  With DW_AT_language c++, 22.  */
       size_t pu_size
 	= (/* CU Header: unit length (initial length).
 	      32-bit DWARF: 4 bytes, 64-bit DWARF: 12 bytes.  */
@@ -7059,7 +7089,9 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
 	   + 4
 	  /* CU Root DIE: DW_AT_language (constant).
 	     1 or 2 bytes.  */
-	   + (uni_lang_p ? nr_bytes_for (die_cu (arr[i])->lang) : 0)
+	   + ((uni_lang_p || part_lang)
+	      ? nr_bytes_for (die_cu (arr[i])->lang)
+	      : 0)
 	   /* CU root DIE children terminator: abbreviation code 0
 					       (unsigned LEB128).
 	      1 byte.  */
@@ -7078,7 +7110,7 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
 		  /* Size of PU.  */
 		  + pu_size
 		  /* Size of imports.  */
-		  + import_size * cnt
+		  + (part_lang != 0 ? 0 : import_size * cnt)
 		  /* Size of namespace DIEs.  */
 		  + namespace_size * namespaces);
       if (!second_phase)
@@ -7140,6 +7172,11 @@ partition_dups_1 (dw_die_ref *arr, size_t vec_size,
 		ref->die_dup = child;
 	      if (unlikely (verify_dups_p))
 		verify_dups (child, odr_mode == ODR_BASIC);
+	      if (part_lang != 0)
+		{
+		  die->die_tag = DW_TAG_compile_unit;
+		  partial_cu->lang = part_lang;
+		}
 	      if (namespaces)
 		{
 		  for (ref = arr[k]->die_parent;
@@ -7907,6 +7944,9 @@ create_import_tree (void)
       dw_die_ref die, rdie;
       dw_cu_ref prev_cu;
 
+      if (pu->cu_die->die_tag == DW_TAG_compile_unit)
+	continue;
+
       last_partial_cu = pu;
       for (rdie = pu->cu_die->die_child;
 	   rdie->die_named_namespace; rdie = rdie->die_child)
@@ -7961,7 +8001,7 @@ create_import_tree (void)
 	}
       ipu->incoming_tail = &ipu->incoming[ipu->incoming_count - 1];
     }
-  if (unlikely (fi_multifile) && npus == 0)
+  if (npus == 0)
     {
       obstack_free (&ob2, to_free);
       return 0;
@@ -8624,6 +8664,7 @@ create_import_tree (void)
 	  die->die_offset = -1U;
 	  die->die_nextdup = e->icu->cu->cu_die;
 	  die->die_parent = cu->cu_die;
+	  assert (e->icu->cu->cu_die->die_tag == DW_TAG_partial_unit);
 	  die->die_size = (cu->cu_version == 2 ? 1 + ptr_size : 5);
 	  /* Put the new DW_TAG_imported_unit DIE after all typed DWARF
 	     stack referenced base types and after all previously added
@@ -9885,7 +9926,7 @@ build_abbrevs_for_die (htab_t h, dw_cu_ref cu, dw_die_ref die,
 	    die->die_size += 4;
 	    t->nattr++;
 	  }
-	if (uni_lang_p)
+	if (uni_lang_p || cu->cu_die->die_tag == DW_TAG_compile_unit)
 	  {
 	    unsigned int lang_size = nr_bytes_for (cu->lang);
 	    die->die_size += lang_size;
@@ -14716,6 +14757,10 @@ static struct option dwz_options[] =
 			 no_argument,	    &uni_lang_p, 1 },
   { "devel-no-uni-lang",
 			 no_argument,	    &uni_lang_p, 0 },
+  { "devel-gen-cu",
+			 no_argument,	    &gen_cu_p, 1 },
+  { "devel-no-gen-cu",
+			 no_argument,	    &gen_cu_p, 0 },
 #endif
   { "odr",		 no_argument,	    &odr, 1 },
   { "no-odr",		 no_argument,	    &odr, 0 },
@@ -14966,7 +15011,8 @@ usage (void)
        "  --devel-partition-dups-opt\n"
        "  --devel-die-count-method\n"
        "  --devel-deduplication-mode={none,intra-cu,inter-cu}\n"
-       "  --devel-uni-lang / --devel-no-uni-lang\n");
+       "  --devel-uni-lang / --devel-no-uni-lang\n"
+       "  --devel-gen-cu / --devel-no-gen-cu\n");
   fprintf (stderr, "%s", msg);
 #endif