[committed 1/13][odr, c++] Cover letter -- One Definition Rule for struct, class and union

[committed 1/13][odr, c++] Cover letter -- One Definition Rule for struct, class and union

[Tom de Vries]

Hi,

This patch series adds optimization option --odr, that exploits the
one-definition-rule for C++ for struct, class and union.  It's on by
default.

I.   Patch series
II.  Optimization description
III. Optimization modes basic and link
IV.  Effect
V.   Cost
VI.  Testing
VII. Todo

I. Patch series

[odr] Add odr variable
[odr] Add lang field to struct dw_cu
[odr] Add die_odr_state field to struct dw_die
[odr] Construct maximal duplicate chains
[odr] Split the maximal duplicate chains
[odr] Combine decls duplicate chain with def duplicate chain
[odr] Add --odr/--no-odr and --odr-mode={basic,link} command line options
[odr, testsuite] Add test-cases odr-{struct,class,union}.sh
[odr, testsuite] Add test-case odr-loc.sh
[odr, testsuite] Add odr-def-decl.sh
[odr] Enable --odr by default
[odr] Add --odr/--no-odr and --odr-mode entries to man page

II. Optimization description

When passing --odr, dwz merges a struct/class/union declaration in one CU
with a corresponding definition with the same name in another CU.

F.i., for dwarf describing compilation units:
...
struct bbb;            // decl
struct ccc { int c; }; // def
struct aaa {
  struct bbb *b;       // pointer to decl
  struct ccc *c;       // pointer to def
};
...
and:
...
struct bbb { int b; }; // def
struct ccc;            // decl
struct aaa {
  struct bbb *b;       // pointer to def
  struct ccc *c;       // pointer to decl
};
...
we manage to get a partial unit containing dwarf describing:
...
struct bbb { int b; }; // def
struct ccc { int c; }; // def
struct aaa {
  struct bbb *b;       // pointer to def
  struct ccc *c;       // pointer to def
}
...

So, instead of two, we get one definition of aaa with both fields pointing to
definitions of bbb and ccc.

III. Optimization modes basic and link

The result at I describes the default optimization mode --odr-mode=link.

A less aggressive optimization mode --odr-mode=basic gets us instead a partial
unit containing dwarf describing:
...
struct aaa {
  struct bbb *b;       // pointer to decl
  struct ccc *c;       // pointer to def
};
...

This mode is provided as a fall back, in case there are problems in
--odr-mode=link.

IV. Effect

We use a cc1 executable to generate executables compressed with and without odr:
...
$ dwz cc1 -lnone --no-odr -o cc1.dwz
$ dwz cc1 -lnone --odr -o cc1.dwz.odr
...

Then we can inspect the difference:
...
$ diff.sh cc1 cc1.dwz
.debug_info      red: 44.84%    111527248  61527733
.debug_abbrev    red: 40.28%      1722726   1028968
.debug_str       red:  0.00%      6609355   6609355
total            red: 42.30%    119859329  69166056
$ diff.sh cc1 cc1.dwz.odr
.debug_info      red: 57.40%    111527248  47512463
.debug_abbrev    red: 73.30%      1722726    460072
.debug_str       red:  0.00%      6609355   6609355
total            red: 54.47%    119859329  54581890
...

[ Note that the total mentioned here relates to the 3 mentioned debug
sections, not the size of all the debug sections or the entire executable.  ]

In summary, the mentioned debug sections are reduced in size by:
- by 42.30% when not using odr, and
- by 54.47% when using --odr,
making the impact of --odr an extra 12.17% of size reduction.

The result for --odr-mode=basic is:
...
$ dwz cc1 -lnone --odr --odr-mode=basic -o cc1.dwz.odr.basic
$ diff.sh cc1 cc1.dwz.odr.basic
.debug_info      red: 56.16%    111527248  48894897
.debug_abbrev    red: 71.49%      1722726    491150
.debug_str       red:  0.00%      6609355   6609355
total            red: 53.29%    119859329  55995402
...
making the impact of --odr --odr-mode=basic a (slightly lesser) extra 10.99%
of size reduction.

V. Cost

Using the same cc1 example as in IV, we can see the cost of the optimization:
...
$ time.sh dwz cc1 -lnone --no-odr -o cc1.dwz
maxmem: 1260420
real: 5.35
user: 5.14
system: 0.20
$ time.sh dwz cc1 -lnone --odr -o cc1.dwz.odr
maxmem: 1253500
real: 5.54
user: 5.37
system: 0.16
...
So, roughly the same amount of memory, and a bit (~4.5%) slower.

A more detailed measurement of execution time confirms that:
...
real:  mean:  5158.20  100.00%  stddev:  43.89
       mean:  5454.00  105.73%  stddev:  34.47
user:  mean:  5068.10  100.00%  stddev:  44.34
       mean:  5350.10  105.56%  stddev:  34.31
sys:   mean:    89.60  100.00%  stddev:  31.79
       mean:   103.20  115.18%  stddev:  31.09
...

It's good to note though that without the patch series applied, we use 6.5% less
memory (in absolute numbers: 80.3 MB) than with --no-odr, due to the struct
dw_die not having the die_hash2 field:
...
$ time.sh dwz cc1 -lnone -o cc1.dwz
maxmem: 1178168
real: 5.16
user: 4.99
system: 0.16
...
It needs to be investigated whether it makes sense to get rid of this memory
usage regression for --no-odr.

VI. Testing

The patch series contains test-cases exercising the --odr optimization option.

The patch series has been in conjunction with the gdb testsuite, using target
boards cc-with-dwz.exp and cc-with-dwz-m.exp, both using --odr-mode=basic and
--odr-mode=link.

The patch series has been verified to produce the same result for cc1 with
--no-odr as without the patch series.

VII. Todo

The optimization is disabled in low memory mode.  It needs to be investigated
whether it makes sense to enable it in low memory mode.  The optimization
requires extra memory (in theory, atm we lazily claim the same amount with
and without the optimization, but that might change), which conflicts with
the idea of the low memory mode.

Committed to trunk.

Thanks,
- Tom

[odr, c++] Cover letter -- One Definition Rule for struct, class and union

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

	* COVER-LETTER: New file, meant to avoid dropping empty commits
	containing the cover letter in the log message.

---
 COVER-LETTER | 1 +
 1 file changed, 1 insertion(+)

diff --git a/COVER-LETTER b/COVER-LETTER
new file mode 100644
index 0000000..9176886
--- /dev/null
+++ b/COVER-LETTER
@@ -0,0 +1 @@
+One definition rule optimization