[Dwarf-discuss] Proposal: `DW_LNS_indirect_line`

[Jacob Young]

> On 12/07/2024 19:04, David Blaikie wrote:
> > Thanks for all the context (I noticed you replied directly to me - are
> > you happy/OK having this discussion on the mailing list, rather than
> > in private? It'd help to keep all the history visible, linkable, etc)
> Yes, apologies, that was just a mistake on my part -- I meant to do
> this, then realised I accidentally replied to you directly, so went to
> forward it to the list, and only now realised that I accidentally
> forwarded it to a completely unrelated list :P
> > While I can appreciate the desire to make this update O(N) in the
> > number of source lines affected - would it be acceptable for this to
> > be O(N) in the number of machine/object level functions?
> >
> > Like if we had a feature for resetting the line table program part-way
> > through a line table - would that be adequate? Then your external data
> > could keep track of the line number setting operation at the start of
> > the new/distinct/indepednent sequence and update that?
> While not ideal for us, this would certainly be an improvement. Dealing
> with the relative line number offsets is definitely the biggest pain
> point wrt constructing the LNP today.
> > Such a feature would have some more generality/usefulness directly
> > without external/side data - for instance it would make chunks of the
> > line table discardable, which could make it easier for a producer to
> > use comdats to isolate the line table data associated with an inline
> > function and allow the linker to discard such a contribution if desired.

My idea for solving this problem without additional side data is to instead
add a line table opcode that references an existing DIE with DECL attributes
and sets the state machine's line register to the value of its DW_AT_decl_line
attribute.  Similarly, DW_AT_decl_file and DW_AT_decl_column could also
be copied to file and column for consistency.  By itself, this doesn't reduce
the number of updates required, but it could be combined with an additional
DIE tag for representing the source decl before inlining/instantiation and a
DIE attribute for referencing the source decl from the inlined/instantiated
DIE which would indicate that DECL attributes are copied from the source
decl.  That way, the DECL attributes would only ever need to be updated in
a single place, the source decl DIE.

Instead of creating a new tag, it also seems pretty straightforward to just
reuse DW_AT_subprogram for the source decl.  Since uninstantiated
functions would not correspond to any program addresses, a missing
DW_AT_low_pc or new flag attribute could indicate this. The intended
meaning of DW_AT_abstract_origin already links an inlined function to
the source decl.  For instantiations, it's possible to add meaning to either
DW_AT_abstract_origin or DW_AT_specification, or create a new attribute.
Both of these existing attributes already indicate that the referenced DIE
contains some of the attributes of the referencing DIE, but I am probably
stretching the intended meaning of the latter too far for this particular use
case.  (Actually, I wrote that reading DW_AT_abstract_origin as being only
documented as related to inlined functions, but I see now that it explicitly
"can be used with almost any debugging information entry" and the name
already seems to me to fit this instantiation use case perfectly.)

I should note that I'm already in the process of considering whether new
tags/attributes will be needed, some to support incremental, and some to
support Zig Language concepts that do not exist in DWARF yet.  It seems
likely that at least some number of new definitions will be needed anyway,
and I would expect that being able to represent source decls in a separate
DIE with references from the generated decls is useful independently of
whether this proposed line table opcode is accepted.  (Although with my
newfound understanding of DW_AT_abstract_origin, I'm now back down
to only one new DIE tag and one new DIE attribute to support incremental.)

I'm sure this could easily be converted into a more concrete proposal,
but I am interested in getting some feedback first, since I don't know if
there are any pre-existing constraints preventing .debug_info from being
referenced from .debug_line.  As I hope I have demonstrated, this seems
much more extensible to new use cases than the previous proposal.

> This is a good use case, but I would point out that it would (if I am
> understanding you correctly) also be solved by my original proposal. To
> be clear, by "more generality/usefulness", do you mean compared to my
> proposal, or compared to status quo? With that being said, I can
> understand the aversion to, as you put it, storing external/side data.
> Just for the record, I don't think the original issue is unique to the
> Zig project; any sufficiently incremental compiler (which admittedly is
> a rarity today, but could perhaps see more adoption as a concept if Zig
> is able to prove its viability for native builds in a systems language)
> should benefit from the proposal if the language in question contains
> some kind of generic/template system (which, of course, most source
> languages today do). However, I am happy to concede this point and
> discuss a more tame proposal if you view the external data as too
> significant of a change for a perhaps seldom-used feature.
>
> > On Tue, Jul 9, 2024 at 2:27 AM Matthew Lugg <mlugg@mlugg.co.uk> wrote:
> >
> > On 08/07/2024 22:18, David Blaikie via Dwarf-discuss wrote:
> > > Hi Matthew,
> > >
> > > I'm looking into your issue & I have some broad questions:
> > >
> > > This seems like it'd speed up generics-heavy code, to be sure -
> > though
> > > I assume you hit a perf issue in some prototype tool already, that
> > > lead you to this issue? Do you have further details on the tooling
> > > you've prototyped/the problems you've encountered? Or is this
> > proposal
> > > more based on an assumption/predicted issue?
> >
> > Thanks very much for the quick response!
> >
> > We haven't hit a performance issue thus far, because the current
> > implementation of incremental compilation in the Zig compiler is
> > incomplete. However, I'm happy to give some further context as to the
> > usage of this proposal in the Zig compiler.
> >
> > Zig allows a function to be generic by taking certain arguments at
> > compile-time, and each separate set of arguments creates a different
> > instantiation of the function. Such functions can also create types
> > on-the-fly, which can themselves contain more functions, which might
> > reference the compile-time known arguments from above, so we get
> > distinct instances of the type. This essentially leads to our
> > implementation of templates, which use the fact that types are
> > first-class values at compile time in Zig. Sorry if that was a little
> > badly worded -- it's hard to explain the design of Zig's templates
> > without getting into more concepts about the language! That said,
> > it's
> > not important to really understand this mechanism; what matters is
> > that
> > it essentially gives us templates a la C++.
> >
> > As far as I'm aware, our current incremental linker implementation
> > doesn't really handle updating the DWARF LNP at the minute (we've
> > mainly
> > been focused on trying to make the actual binaries work first).
> > The Zig
> > project has recently been making heavy progress towards incremental
> > compilation, and analysis of the problem space here is what led to
> > this
> > proposal. Under status quo, an incremental update would require the
> > linker to potentially update a lot more line numbers than have
> > logically
> > changed. Consider making a trivial change to the `ArrayList` code
> > in the
> > standard library, say moving the `ArrayList.init` function down by a
> > single line. In that case, we would need to update the line number
> > corresponding to every distinct instantiation of the `ArrayList`
> > type,
> > which in a complex application, could potentially be in the low
> > hundreds. There are also more pathological cases: for instance, if
> > the
> > standard library code for formatted printing has its line number
> > changed, then potentially thousands of LNP entries would have to be
> > changed, since every distinct format string creates a separate
> > function
> > instantiation in our standard library. This is also made more
> > complex by
> > the fact that line number updates are currently all relative, which I
> > will discuss below...
> >
> > > Also, while I imagine this feature could simplify the situation
> > even
> > > when there aren't shared lines/generics (by centralizing the
> > place to
> > > update) -- I wouldn't've thought a naive... oh, I see, there's no
> > > "reset the line number".
> > >
> > > So even between sequences there's no resetting of the line
> > number, so
> > > you can't just look for the line at the start of some functions,
> > etc.
> > Indeed -- our biggest problem at the moment is that all line number
> > updates are relative, which means that if, say, one function is
> > moved in
> > the file, we actually need to perform some arithmetic on the line
> > number
> > of the preceding function in the LNP so as to compute the new offset.
> > So, the linker would need to preserve state about what the `line`
> > register is expected to contain going into the LNP fragment for each
> > function. This is doable, it just seems like unnecessary extra work,
> > since I don't see any reason relative line number offsets would be
> > preferable for debuggers and other tooling, so don't immediately
> > see an
> > issue with having a way to provide an absolute line number offset (or
> > just an opcode to reset it to 0). If this specific proposal is
> > ultimately rejected, something like that may still be worth
> > considering.
> > > Equally, though, putting some otherwise "random" line numbers in a
> > > list in the header of the line table doesn't seem like a generally
> > > usable feature - It'd be unclear how the DWARF modifying-tool would
> > > know which line numbers to update (couldn't rely on unique
> > numbers -
> > > they might collide between different files, and some files might
> > need
> > > updating and some not, etc)

A line table opcode that references a DIE should be much easier for tooling
to handle, since existing tooling already supports references to DIEs from
many other contexts.  Additionally, source decl DIE deduplication should
easily be able to follow whatever the existing rules happen to be, since the
DIE naturally attaches uniquing state (aka a file) to the line number.

> > In the context of the Zig compiler, we aren't updating the DWARF
> > information in a vacuum -- we are able to store our own state about
> > which Zig source constructs correspond to which pieces of the binary
> > file and DWARF information. (The compiler has mechanisms to
> > efficiently
> > [de]serialize this state to a separate file across runs of the
> > compiler.) The goal of this proposal is essentially to decrease the
> > amount of state we need to store. Under this proposal, the Zig
> > compiler
> > would be able to store a mapping from a specific instruction in an IR
> > (the instructions corresponding to source-level declarations, in
> > particular function declarations), to the byte offset of the
> > corresponding entry in `indirect_lines`. So, when the declaration
> > corresponding to an IR instruction is relocated -- which our existing
> > infrastructure for incremental compilation allows us to cheaply
> > detect
> > -- our incremental linker can simply look up that IR instruction
> > in the
> > mapping, giving it a byte offset into `indirect_lines`, and update
> > the
> > entry at that offset. Since `indirect_lines` is able to be densely
> > packed, the linker can ensure that there will always be 4 or 5 bytes
> > available for the ULEB128 value, so that it never has to move around
> > other line numbers. Ultimately, this means that the full binary
> > update
> > overhead of e.g. moving one function in source code down one line
> > would
> > be this one hashmap lookup and a 4- or 5-byte write to the output
> > file.
> > Today, however, we would have to maintain additional state about the
> > expected value of `line` before each new LNP fragment, keeping this
> > up-to-date, and we would have to update potentially arbitrarily many
> > line numbers in the file, one for each relevant generic
> > instantiation.
> > We would also have to update the LNP fragment *following* each
> > changed
> > region, to correct the offset to that fragment, since the preceding
> > value of `line` is now different.
> >
> > > @Adrian Prantl <mailto:aprantl@apple.com> and @Jonas Devlieghere
> > > <mailto:jdevlieghere@apple.com> with the CAS DWARF stuff, how
> > are you
> > > folks separating line table fragments for functions? My
> > understanding
> > > was the line table header was too large to have one on every
> > > function's line table fragment, so I would've thought you'd figured
> > > out a way to make line table fragments that could be added/removed
> > > from a line table without disturbing the other flags/state and
> > without
> > > relying on specific values in/out of the line register?
> > >
> > > On Wed, Jun 26, 2024 at 4:06 PM Matthew Lugg via Dwarf-discuss
> > > <dwarf-discuss@lists.dwarfstd.org> wrote:
> > >
> > >     # Add DW_LNS_indirect_line - update `line` to absolute value
> > stored
> > >     indirectly
> > >
> > >     ## Background
> > >
> > >     In many source languages, it is possible for many
> > program-counter
> > >     addresses with arbitrary
> > >     separation to correspond to the same source line due to
> > features like
> > >     templates/generics. When
> > >     designing an incremental compiler, the line number program
> > must be
> > >     updated when line numbers within
> > >     a source file are moved. It would be desirable to have the
> > >     property that
> > >     when moving a source line
> > >     corresponding to a large amount of distinct program-counter
> > >     addresses,
> > >     only one line number value in
> > >     the DWARF information needs to be updated. For this to be
> > true, the
> > >     regions of the line number
> > >     program corresponding to each such address must include the line
> > >     number
> > >     of the source construct not
> > >     directly, but through an indirect reference. This allows one
> > line
> > >     number
> > >     value stored in the binary
> > >     to be shared across arbitrarily many entries in the line number
> > >     matrix.
> > >
> > >     This is not currently possible: all modifications to the `line`
> > >     register
> > >     are given by relative
> > >     offsets, and all of these offsets are directly included in the
> > >     instruction (or implicit in the case
> > >     of a special opcode).
> > >
> > >     ## Overview
> > >
> > >     Introduce new fields to the line number program header,
> > >     `indirect_lines_length` (ULEB128) and
> > >     `indirect_lines` (opaque block of bytes containing ULEB128
> > >     values). The
> > >     `indirect_lines_length`
> > >     field is the length in bytes of the `indirect_lines`
> > section, rather
> > >     than the number of elements.
> > >     Introduce a new standard opcode to the line number program,
> > >     `DW_LNS_indirect_line`. This opcode
> > >     takes a single ULEB128 operand, which represents a byte offset
> > >     into the
> > >     `indirect_lines` stored in
> > >     the header. The effect of this instruction is to set the `line`
> > >     register
> > >     to the ULEB128 value stored
> > >     at the given byte offset into `indirect_lines`. Note that
> > >     `indirect_lines` is not itself validated
> > >     to be a valid sequence of ULEB128 values; decoding only
> > occurs when
> > >     `DW_LNS_indirect_line` is used.
> > >     This allows an incremental compiler to pre-allocate a large
> > amount of
> > >     padding space in
> > >     `indirect_lines` to fill in later as needed.
> > >
> > >     Note that an incremental compiler would not necessarily wish
> > to use
> > >     variable-length integers to
> > >     represent this information, since certain changes of line
> > numbers
> > >     could
> > >     cause a line number which
> > >     was previously encoded using 1 byte to now require 2. However,
> > >     since the
> > >     stored values need not be
> > >     densely packed, an implementation is free to reserve as much
> > space
> > >     as is
> > >     necessary for each entry.
> > >     For instance, the downstream Zig compiler (which is the original
> > >     motivator for this proposal) may
> > >     choose to reserve 4 or 5 bytes for each line number, as line
> > >     numbers in
> > >     Zig source files cannot
> > >     exceed 1<<32. The use of ULEB128 allows the compiler to make an
> > >     appropriate decision here instead of
> > >     codifying such a restriction into the DWARF specification.
> > >
> > >     ## Proposed Changes
> > >
> > >     Pages and line numbers are given for the 2024-06-16 working
> > draft of
> > >     DWARF Version 6, which is the
> > >     latest draft at the time of writing.
> > >
> > >     6.2.4 (pg 163; line 27)
> > >
> > >     21. indirect_lines_length (ULEB128)
> > >          The length in bytes of the data stored in the
> > >     `indirect_lines` field.
> > >     22. indirect_lines (block containing ULEB128 entries)
> > >          A collection of line numbers, each stored as a ULEB128
> > integer.
> > >     These values are referenced by
> > >          DW_LNS_indirect_line instructions to modify the state
> > of the
> > >     line
> > >     number information state
> > >          machine.
> > >
> > >          The data stored in this field is not checked to be a valid
> > >     sequence
> > >     of ULEB128 entries. The
> > >          contained data may include padding bytes or otherwise
> > invalid
> > >     data.
> > >     As such, it is expected that
> > >          bytes of this field be accessed only when a
> > DW_LNS_indirect_line
> > >     instruction references them.
> > >
> > >     6.2.5.2 (pg 170; line 23)
> > >
> > >     14. DW_LNS_indirect_line
> > >          The DW_LNS_indirect_line opcode takes a single unsigned
> > LEB128
> > >     operand. This operand is
> > >          interpreted as a byte offset into the `indirect_lines`
> > field
> > >     of the
> > >     line number program header.
> > >          An unsigned LEB128 value is read from `indirect_lines`
> > at the
> > >     given
> > >     offset, and this value is
> > >          stored into the state machine's `line` register.
> > >
> > >     7.22 (pg 246; table 7.25)
> > >
> > >       Opcode name          | Value
> > >     ----------------------+-------
> > >             ...            |  ...
> > >     DW_LNS_indirect_line  | 0x0d
> > >
> > >     --
> > >     Dwarf-discuss mailing list
> > > Dwarf-discuss@lists.dwarfstd.org
> > > https://lists.dwarfstd.org/mailman/listinfo/dwarf-discuss
> > >
> > >
> >