<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Sep 18, 2019 at 7:25 AM Alexey Lapshin <<a href="mailto:a.v.lapshin@mail.ru">a.v.lapshin@mail.ru</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<p><br>
</p>
<div class="gmail-m_-6621197048798399580moz-cite-prefix">17.09.2019 3:12, David Blaikie пишет:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, Sep 11, 2019 at 3:32
PM Alexey Lapshin via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>Debuginfo and linker folks, we (AccessSoftek) would
like to suggest a proposal for removing obsolete debug
info. If you find it useful we will be happy to work on
improving it. Thank you for any opinions and suggestions.<br>
<br>
Alexey.<br>
<br>
Currently when the linker does garbage collection a
lot of abandoned debug info is left behind (see Appendix A
for documentation). Besides inflated debug info size, we
ended up with overlapping address ranges and no way to say
valid vs garbage ranges. We propose removing debug info
along with removing code. This would reduce debug info
size and make sure debug info accuracy.<br>
<br>
There are several approaches which could be used to solve
that problem:<br>
<br>
1. Require dwarf producers to generate fragmented debug
data according to DWARF5 specification: "E.3.3
Single-function-per-DWARF-compilation-unit" page 388. That
approach assumes fragmenting the whole debug info per
function basis and glue fragmented sections at the link
time using section groups.<br>
<br>
2. Use an additional tool, which would optimize out
unnecessary debug data, something similar to dwz (dwarf
compressor tool), dsymutil (links the DWARF debug
information). This approach assumes additional post-link
binaries processing.<br>
<br>
3. Teach the linker to parse debug data and let it remove
unused debug data. <br>
<br>
In this proposal, we focus on approach #3. We show that
this approach is viable and discuss some preliminary
results, leaving particular implementation out of the
scope. We attach the Proof of Concept (PoC)
implementation(<a href="https://reviews.llvm.org/D67469" target="_blank">https://reviews.llvm.org/D67469</a>)
for illustrative purposes. Please keep in mind that it is
not final, and there is room for improvements (see
Appendix B). However, the achieved results look quite
promising and demonstrate up to 2 times size reduction and
performance overhead is 30% of linking time (which is in
the same ballpark as the already done section compressing
(see table 2 point F)).<br>
</div>
</blockquote>
<div><br>
</div>
<div>Have you considered/tried reusing the DWARF
minimization/deduplication/linking logic that's already in
llvm's dsymutil implementation? If we're going to do that
having a singular implementation would be desirable.<br>
<br>
(bonus points if we could do something like the dsymutil
approach when using Split DWARF and building a DWP - taking
some address table output from the linker, and using that to
help trim things (or, even when having no input from the
linker - at least doing more aggressive deduplication during
DWP construction than can be currently done with only type
units (& potentially removing/avoiding type unit
overhead too))<br>
</div>
<div> </div>
</div>
</div>
</blockquote>
Generally speaking, dsymutil does a very similar thing. It parses
DWARF DIEs, analyzes relocations, scans through references and
throws out unused DIEs. But it`s current interface does not allow to
use it at link stage. <br>
I think it would be perfect to have a singular implementation. <br>
Though I did not analyze how easy or is it possible to reuse its
code at the link stage, it looked like it needs a significant
rework. <br>
<br>
Implementation from this proposal does removing of obsolete debug
info at link stage. <br>
And so has benefits of already loaded object files, already created
liveness information, <br>
generating an optimized binary from scratch.<br>
<p><br>
</p>
<p>If dsymutil could be refactored in such manner that could be used
at the link stage, then it`s implementation could be reused. I
would research the possibility of such a refactoring.</p></div></blockquote><div>Yeah, if this is going to be implemented, I think that would be strongly preferred - though I realize it may be substantial work to refactor. The alternative - duplicating all this work - doesn't seem like something that would be good for the LLVM project.<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>1. Minimize or entirely avoid references from
subprograms into other parts of .debug_info section. That
would simplify splitting and removing subprograms out in
that sense that it would minimize the number of references
that should be parsed and followed.
(DW_FORM_ref_subroutine instead of DW_FORM_ref_*, ?)<br>
</div>
</blockquote>
<div><br>
Not sure I follow - by "other parts of the .debug_info
section" do you mean in the same CU, or cross CU references?
Any particular references you have in mind? Or encountered
in practice?<br>
</div>
</div>
</div>
</blockquote>
I mean here all kinds of references into .debug_info section.</div></blockquote><div><br></div><div>Ah, not only references from other places /into/ .debug_info (which don't really exist, so far as I know) but any references to locations within debug_info.<br><br>Reducing these isn't super-viable - types being the most common examples. Though now I understand what you're getting at partly around the debug_type_table idea - adding a level of indirection to type references. So it'd be easy to find only one place to fix when removing chunks of debug_info (updating only the type table without having to find all the places inside debug_info to touch). That indirection would come at a size cost, of course - and an overhead for DWARF parsers having to follow that indirection. Doesn't make it impossible - just tradeoffs to be aware of.<br><br>Though that's not the only DIE references - without removing them all there'd still be a fair bit of overhead for finding any remaining ones and applying them. If an indirection table is to be added, maybe a generalized one (for any DIE reference) rather than one only for types would be good.<br><br>(aspects of this have been discusesd before - we've sometimes nicknamed it "bag of DWARF" when discussing it in the context of type units (currently you can only reference the type DIE in a type unit - which adds overhead when wanting to reference subprogram declaration DIEs, etc (or maybe multiple types are clustered together and don't need a separate type unit each - if only you could refer to multiple types in a type unit) - so we've discussed generalizing the type unit header (actually it could generalize even as far as the classic CU header) to have N type DIE offset+hash pairs (zero for a normal CU, one for a classic type unit, and any number for more interesting cases))</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"> Going
through references is the time-consuming task. <br>
Thus the fewer references there should be followed then the faster
it works.<br>
<br>
For the cross CU references - It requires to load referenced CU. I
do not know use cases where cross CU references are used.</div></blockquote><div><br>Cross-CU inlining due to LTO. Try something like this:<br><br><font face="monospace">a.cpp:<br> void f2();<br> __attribute__((always_inline)) void f1() {<br> f2();<br> }<br><br>b.cpp:<br> void f1();<br> int main() {<br> f1();<br> }<br><br>$ clang++ a.cpp b.cpp -emit-llvm -S -c -g<br>$ llvm-link a.ll b.ll -o ab.bc<br>$ clang++ ab.bc -c<br>$ llvm-dwarfdump ab.o -v -debug-info | <br>0x0b: DW_TAG_compile_unit<br> DW_AT_name "a.cpp"<br>0x2a: DW_TAG_subprogram<br> DW_AT_abstract_origin [DW_FORM_ref4] (cu + 0x0056 => {0x00000056} "_Z2f1v")<br> DW_TAG_subprogram<br> DW_AT_name "f1"<br>0x6e: DW_TAG_compile_unit<br> DW_AT_name "b.cpp"<br>0x8d: DW_TAG_subprogram<br> DW_AT_name "main"<br>0xa6: DW_TAG_inlined_subroutine<br> DW_AT_abstract_origin [DW_FORM_ref_addr] (0x0000000000000056 "_Z2f1v")</font><br><br>ueaueoa</div><div>ueaoueoa<br><br>Notice that the inlined_subroutine's abstract_origin uses a linker relocation into the debug_info section to give an absolute offset within the finally linked debug_info section (since the debugger wouldn't know that these two compile_units are bound together and to use some particular compile_unit as the base offset - either it's absolute across the whole debug_info section (FORM_ref_addr) or it's local to the CU (FORM_refN (such as FORM_ref4 above)))<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"> If that is
the specific case and is not used inside subprograms usually, then
probably it is possible to avoid it.<br></div></blockquote><div><br>It's fairly specifically used inside subprograms (& would need to be adjusted even if it wasn't inside a subprogram - when bytes are removed, etc) - though possibly general relocation handling in the linker could be used to implement handling ref_addr.<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">For the same CU - there could probably be cases when references
could be ignored: <a class="gmail-m_-6621197048798399580moz-txt-link-freetext" href="https://reviews.llvm.org/P8165" target="_blank">https://reviews.llvm.org/P8165</a></div></blockquote><div><br>How would references be ignored while keeping them correct? Ah, by making subprograms more self-contained - maybe, but the work to figure out which things are only referenced from one place and structure the DWARF differently probably wouldn't be ideal in the compiler & wouldn't save the debug info linker from having to haev code to handle the case where it wasn't only used from that subprogram anyway.<br> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>2. Create additional section - global types table
(.debug_types_table). That would significantly reduce the
number of references inside .debug_info section. It also
makes it possible to have a 4-byte reference in this
section instead of 8-bytes reference into type unit
(DW_FORM_ref_types instead of DW_FORM_ref_sig8). It also
makes it possible to place base types into this section
and avoid per-compile unit duplication of them.
Additionally, there could be achieved size reduction by
not generating type unit header. Note, that new section -
.debug_types_table - differs from DWARF4 section
.debug_types in that sense that: it contains unique type
descriptors referenced by offsets instead of list of type
units referenced by DW_FORM_ref_sig8; all table entries
share the same abbreviations and do not have type unit
headers.<br>
</div>
</blockquote>
<div><br>
What do you mean when you say "global types table" the
phrasing in the above paragraph is present-tense, as though
this thing exists but doesn't seem to describe what it
actually is and how it achieves the things the text says it
achieves. Perhaps I've missed some context here.<br>
</div>
</div>
</div>
</blockquote>
<p><br>
</p>
<p>The "global types table" does not exist yet. It could be created
if the discussed approach would be considered useful. <br></p></div></blockquote><div><br></div><div>Ah, the present-tense language was a bit confusing for me when discussing a thing that doesn't exist yet & not having provided a description of what it might be or might contain and why it would exist/what it would achieve.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"><p>
Please check the comparison of possible "global types table" and
currently existed type units: <a class="gmail-m_-6621197048798399580moz-txt-link-freetext" href="https://reviews.llvm.org/P8164" target="_blank">https://reviews.llvm.org/P8164</a></p></div></blockquote><div>Ah, that proposed version makes it easy to remove subprograms from debug_info without having to fix up type references (but you still have to have the code to fix up other cross-CU references, like abstract_origin, so I'm not sure it provides that much value) but doesn't make it easy to remove types (becaues you'd have to go looking through the debug_info section to update all the type offsets (which I guess you have to do anyway to find the type references) and removing the types still also requires fixing up the types that reference each other... <br><br>So I'm not seeing a big win there.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">
<p>The benefit of using "global types table" is that it saves the
space required to keep types comparing with type units solution.
</p>
<p><br>
</p>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div>3. Define the limited scope for line programs which
could be removed independently. I.e. currently .debug_line
section contains a program in byte-coded language for a
state machine. That program actually represents a matrix
[instruction][line information]. In general, it is hard to
cut out part of that program and to keep the whole program
correct. Thus it would be good to specify separate scopes
(related to address ranges) which could be easily removed
from the program body.<br>
</div>
</blockquote>
<div><br>
In my experience line tables are /tiny/ - have you
prototyped any change in this space to have a sense of
whether it would have significant savings? (it'd potentially
help address the address ambiguity issues when the linker
discards code, though - so might be a correctness issue
rather than a size performance issue)<br>
</div>
</div>
</div>
</blockquote>
<p>I did not measure the value of size reduction for line table,
though I think that it would be a small value.<br>
The more important thing is a correctness issue. Line table could
contain information for overlapping address ranges.<br>
</p>
<p>There is another attempt to fix that issue -
<a class="gmail-m_-6621197048798399580moz-txt-link-freetext" href="https://reviews.llvm.org/D59553" target="_blank">https://reviews.llvm.org/D59553</a>.<br></p></div></blockquote><div>Yep. It's a complicated problem, and fixing the line table would be a good way to deal with some of it. (Split DWARF makes it hard to fix up the rest of the debug info, though - so there would still be some ambiguity in the DWARF with a binary using Split DWARF).</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF"><p>
</p>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div><br>
We evaluated the approach on LLVM and Clang codebases. The
results obtained are summarized in the tables below:<br>
</div>
</blockquote>
<div><br>
Memory usage statistics (& confidence intervals for the
build time) would probably be especially useful for
comparing these tradeoffs.<br>
Doubly so when using compression (since the decompression
would need to use more memory, as would the recompression -
so, two different tradeoffs (compressed input, compressed
output, and then both at the same time))<br>
</div>
</div>
</div>
</blockquote>
<p>I would measure memory impact for that PoC implementation, but I
expect it would be significant. <br>
Memory usage was not optimized yet. There are several things which
might be done to reduce memory footprint:<br>
do not load all compile units into memory, avoid adding Parent
field to all DIEs.</p></div></blockquote><div>Yep, this is the sort of thing where I suspect the dsymutil implementation may've already had at least some of that work done - or, if not, that doing the work once for both/all implementations would be very preferable to duplicating the effort.<br><br>- Dave </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div bgcolor="#FFFFFF">
<p>Alexey.<br>
</p>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div><br>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote>
</div>
</div>
</blockquote>
</div>
</blockquote></div></div>