On Tue, Jul 9, 2024 at 2:27 AM Matthew Lugg <ml...@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)
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:apra...@apple.com> and @Jonas Devlieghere
> <mailto:jdevliegh...@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
>
>
