This is an archive of the discontinued LLVM Phabricator instance.

[RFC][Draft] Enable primitive support for Two-Level Line Tables in LLVM
Needs ReviewPublic

Authored by StephenTozer on Jun 12 2023, 6:21 AM.

Details

Reviewers
jdoerfert
Summary
NOTE: This is not intended to be merged into LLVM, as the implementation is incomplete and hacked-in and is not being actively developed; the intention is simply to provide a basic working implementation that can be analyzed and potentially expanded on by any interested parties. For more information see this discourse post.

This patch implements the Two-Level Line Tables (TLLT) proposal currently aiming for Dwarf 6. This proposal allows the line table, which is DWARF's data structure used to map instructions to source locations and vice versa, to be emitted as a pair of tables instead of one, one of which maps source locations to instructions (the Logicals table) and the other of which maps instructions to source locations (the Actuals table). The proposal then extends the Logicals table by adding a context column, allowing entries in that table that represent inlined instructions to refer to another Logicals entry as being the inlined call location for that instruction, creating records for an inlined call stack in the line table and allowing the inlined callsites to be mapped to an instruction in the debugger.

This solves one of the current weaknesses in DWARF debugging, which is the inability to set breakpoints or step onto inlined callsites. However, there are other proposals (such as Location View Numbering) that could achieve the same thing, and the costs of TLLT in storage size and design complexity may make it a non-ideal solution to this problem. We currently have no plans to develop this implementation further, but this small demo may be useful to other developers who have an interest in pursuing this, and it is still possible that a good case may be made for TLLT as the best solution to the problem of representing inlined callsites.

As mentioned in the header, this patch was the result of aiming to get a basic functioning implementation in a very short time; it is not intended to be merged and is not of suitable quality, particularly in LLDB (with which we have no familiarity).

Diff Detail

Event Timeline

StephenTozer created this revision.Jun 12 2023, 6:21 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 12 2023, 6:21 AM
StephenTozer requested review of this revision.Jun 12 2023, 6:21 AM
Herald added projects: Restricted Project, Restricted Project, Restricted Project. · View Herald Transcript
StephenTozer edited the summary of this revision. (Show Details)Jun 12 2023, 6:23 AM

Thanks for prototyping this!

Really appreciate you providing this prototype.

This solves one of the current weaknesses in DWARF debugging, which is the inability to set breakpoints or step onto inlined callsites. However, there are other proposals (such as Location View Numbering) that could achieve the same thing, and the costs of TLLT in storage size and design complexity may make it a non-ideal solution to this problem.

FWIW, one of the major motivations for this was not only to include the stop points, but also to allow symbolizing including stack frames - so you'd need to know that all the inlined instructions come from the inlined call site. I think, maybe, my vague understanding of Location View Numbering wouldn't cover that case, and only covers the "how do I describe the variable when I'm stopped at this synthetic location that exists just before or after the call", for instance?

It is unfortunate to hear that TLLT are a significant size increase, though not entirely surprising - it's a bunch of extra info to encode. I'll be glad to have this example to experiment with.

Are there any known (or vague/unknown) limitations on the implementation with respect to the actual output/on-disk representation? (like, would doing some kind of size analysis of the output when using this patch/feature lead to incorrect conclusions about the cost of the feature?)

StephenTozer added a comment.EditedJun 13 2023, 2:45 AM

It is unfortunate to hear that TLLT are a significant size increase, though not entirely surprising - it's a bunch of extra info to encode. I'll be glad to have this example to experiment with.

For what it's worth, we haven't tested this with any larger programs, so this is more of a rough estimate of size, but the .debug_line section increased in size on the order of 50% for our small test cases. On the other hand, I think that in larger programs the .debug_line section is likely be significantly smaller than the .debug_info section anyway, so if you are interested in producing inline frames without using .debug_info it is probably an improvement in most respects - as an example with a single-source input, flops.c (taken from the LLVM test suite repo), the .debug_line section increased from 3338 to 4758 bytes, and the overall size of the DWARF output from 9467 to 10893.

Are there any known (or vague/unknown) limitations on the implementation with respect to the actual output/on-disk representation?

This patch should follow the spec faithfully - it was written over the span of 4 days so doubtless there are inefficiencies in the program itself and there may be bugs in the output (especially if you try it on a larger codebase), but in theory the output should be an accurate representation of the proposal. With that said, the main cause of the size increase isn't really the amount of additional information encoded, but the fact that the TLLT format does repeat itself a lot by design; generally speaking most instructions are not inlined callsites, and so the additional information for those lines (the context and subprogram fields) has a much smaller impact on size than the fact that we are emitting the (InstructionAddress, SourceLocation) pair twice for every instruction.

We didn't dig deeper into why the representation needs to be split into two separate line number programs rather than either a single line table with some additional column to convey the Instruction->SourceLocation attribution, or keeping two line tables but using a single line number program that can emit Logical and Actual rows simultaneously. Either of these methods would reduce the repetition.

krisb added a subscriber: krisb.Jul 4 2023, 2:39 AM