[committed] Add estimate_nr_dies

[committed] Add estimate_nr_dies

[Tom de Vries]

Hi,

For various reasons, it can be useful to known the amount of DIEs present in
the .debug_info section.  While the exact amount will be known after parsing,
unfortunately there's nothing in the DWARF format that tells us the exact
amount before that.

However, we could try to estimate the number of DIEs, based on the size of the
debug section.

I've written a script bytes-per-die.sh that for a given ELF file with debug
info reports:
- the .debug_info bytes per die ratio,
- the .debug_info size in bytes, and
- the number of DIEs

I've used the bytes-per-die.sh script in dir
build/testsuite/dwz-external.tests/execs:
...
$ for f in *; do echo $f; ~/dwz/src/contrib/bytes-per-die.sh "$f"; done
cc1
10.94   size: 111527248 nr_dies: 10188941
cc1.dwz-processed
11.66   size: 61570632  nr_dies: 5277812
fixdep.debug
13.32   size: 653       nr_dies: 49
objtool.debug
12.67   size: 142776    nr_dies: 11265
vdso32.so.debug
11.19   size: 42068     nr_dies: 3758
vdso64.so.debug
11.10   size: 70175     nr_dies: 6322
vdsox32.so.debug
11.10   size: 70175     nr_dies: 6322
vmlinux-4.20.13-0-vanilla.debug
11.25   size: 196322379 nr_dies: 17450165
...

Also, I've used the script on the files from PR dwz/25024:
...
./lib64/libLTO.so.10svn-10.0.0-0.20190817snap5.fc30.x86_64.debug
10.97   size: 530164789 nr_dies: 48314979
./lib64/libRemarks.so.10svn-10.0.0-0.20190817snap5.fc30.x86_64.debug
9.26    size: 380       nr_dies: 41
./lib64/libclang-cpp.so.10svn-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.11   size: 1090944953        nr_dies: 98118220
./lib64/libclang.so.10-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.10   size: 745710093 nr_dies: 67138506
./lib64/liblldb.so.10.0.0svn-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.10   size: 1024731352        nr_dies: 92269815
./lib64/CheckerOptionHandlingAnalyzerPlugin.so-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.15   size: 542547271 nr_dies: 48634711
./lib64/CheckerDependencyHandlingAnalyzerPlugin.so-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.15   size: 542252625 nr_dies: 48605854
./lib64/liblldbIntelFeatures.so.10svn-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.97   size: 3234906   nr_dies: 270201
./lib64/SampleAnalyzerPlugin.so-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.15   size: 542477225 nr_dies: 48627034
./bin/lldb-argdumper-10.0.0-0.20190817snap5.fc30.x86_64.debug
12.04   size: 3335640   nr_dies: 276989
./bin/lldb-vscode-10.0.0-0.20190817snap5.fc30.x86_64.debug
12.36   size: 5553517   nr_dies: 449251
./bin/clang-10-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.03   size: 1228973097        nr_dies: 111352420
./bin/llvm-tblgen-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.76   size: 35650816  nr_dies: 3031484
./bin/diagtool-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.36   size: 346832994 nr_dies: 30525204
./bin/lldb-instr-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.18   size: 760784804 nr_dies: 68045685
./bin/clang-scan-deps-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.36   size: 350701276 nr_dies: 30861308
./bin/clang-format-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.36   size: 48478831  nr_dies: 4266687
./bin/clang-extdef-mapping-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.40   size: 364063479 nr_dies: 31932433
./bin/lld-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.04   size: 587832448 nr_dies: 53232003
./bin/clang-check-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.05   size: 888995514 nr_dies: 80427950
./bin/clang-refactor-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.35   size: 374647793 nr_dies: 33003358
./bin/clang-offload-bundler-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.47   size: 58554454  nr_dies: 5101759
./bin/lldb-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.91   size: 3795612   nr_dies: 318622
./bin/lldb-server-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.22   size: 698251917 nr_dies: 62210070
./bin/clang-rename-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.36   size: 368478475 nr_dies: 32425465
./bin/clang-import-test-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.28   size: 543086338 nr_dies: 48128547
./bin/c-index-test-10.0.0-0.20190817snap5.fc30.x86_64.debug
11.17   size: 763302508 nr_dies: 68334164
...

It seems that for larger files the ratio 11 is a good match.

Add a function estimate_nr_dies, that estimates the number of DIEs in the
.debug_info section based on the size of that section.

Committed to trunk.

Thanks,
- Tom

Add estimate_nr_dies

2019-11-20  Tom de Vries  <tdevries@suse.de>

	* dwz.c (UNUSED): Define.
	(estimate_nr_dies): New function.
	* contrib/bytes-per-die.sh: New file.

---
 contrib/bytes-per-die.sh | 16 ++++++++++++++++
 dwz.c                    | 12 ++++++++++++
 2 files changed, 28 insertions(+)

diff --git a/contrib/bytes-per-die.sh b/contrib/bytes-per-die.sh
new file mode 100755
index 0000000..969f733
--- /dev/null
+++ b/contrib/bytes-per-die.sh
@@ -0,0 +1,16 @@
+#!/bin/bash
+
+f="$1"
+
+size=$(readelf -WS "$f" \
+	   | egrep "[ \t]\.debug_info" \
+	   | sed 's/.*\.debug_info//' \
+	   | awk '{print $4}')
+size=$((16#$size))
+
+nr_dies=$(readelf -wi "$f" \
+	      | grep -c ': Abbrev Number.*(DW_TAG')
+
+res=$(echo "scale=2; $size / $nr_dies" \
+	  | bc)
+echo -e "$res\tsize: $size\tnr_dies: $nr_dies"
diff --git a/dwz.c b/dwz.c
index 44e745a..846e42f 100644
--- a/dwz.c
+++ b/dwz.c
@@ -117,8 +117,10 @@
 
 #if defined __GNUC__
 # define FORCE_INLINE __attribute__((always_inline))
+# define UNUSED __attribute__((unused))
 #else
 # define FORCE_INLINE
+# define UNUSED
 #endif
 
 #define obstack_chunk_alloc     malloc
@@ -1185,6 +1187,16 @@ read_debug_line (DSO *dso, dw_cu_ref cu, uint32_t off)
   return 0;
 }
 
+/* Estimate the amount of DIEs in the .debug_info section, based on the size
+   of that section.  */
+static unsigned int UNUSED
+estimate_nr_dies (void)
+{
+  unsigned int average_die_size = 11;
+  unsigned int nr_dies = debug_sections[DEBUG_INFO].size / average_die_size;
+  return nr_dies;
+}
+
 /* Hash function for off_htab hash table.  */
 static hashval_t
 off_hash (const void *p)