[lldb-dev] Question about building line tables

[Zachary Turner via lldb-dev]

Does DWARF not store this information?  Because it seems like it could be
efficiently stored in an interval tree, the question is just whether it is
efficient to convert what DWARF stores into that format.

PDB returns line entries in the format I described, with a start address
and a byte length, so to determine whether something is a terminal entry I
have to add them to some kind of data structure that collapses ranges and
then manually scan through for breaks in the continuity of the range.

Is there some way we can make this more generic so that it's efficient for
both DWARF and PDB?

On Mon, Mar 7, 2016 at 3:13 PM Greg Clayton <gclayton at apple.com> wrote:

>
> > On Mar 7, 2016, at 3:07 PM, Zachary Turner via lldb-dev <
> lldb-dev at lists.llvm.org> wrote:
> >
> > This discussion originally started on a code review thread, but I
> figured I would continue it here since the patch has landed and I want to
> do more work as a followup.
> >
> > So LLDB's LineTable data structures have the notion of a "terminal
> entry".  As I understand it, LineTables are structured as a sequence of
> "entries".  An entry consists of:
> >
> > Start Line
> > End Line
> > Start Address
> > Byte Length
> > Is Terminal Entry
>
> Not quite correct. There is no end line and there is no byte length. To
> efficiently store line entries that can be efficiently searched, we need to
> not have a length and not have an end line.
>
> > and this represents some piece of source code.  If you were to examine
> all line entries in the debug info, you would find that not all address
> ranges are covered.  For example, line 10 might correspond to address
> 0x12345 - 0x12347, and line 11 might correspond to address 0x12360.  So
> address 0x12348 - 0x12359 do not map to anything.  Probably they are not
> even code, but just space between functions, or other random data in the
> .text section of a binary that isn't code.
> >
> > The problem is, building a line table requires the person parsing the
> debug info to specify where the terminal entries are.  Why?  Isn't it
> trivial to calculate this automatically?  Say you insert a bunch of line
> entries, now they're all sorted by address into some array of LineEntry
> structures.  It seems to me like n is a terminal entry if
> >
> > (entries[n].address + entries[n].length) < entries[n+1].address
> >
> > is true.  Why do we need to store a separate flag for it?
>
> Because there is no size in each LineEntry. We rely on the next line entry
> always terminating the previous one. So one marked with "i am a terminal
> entry" is required to finish off the previous one.
>
> > Is there ever a case where the above condition is true but it is not the
> end of a sequence?  Or where the above condition is false but it is the end
> of a sequence?
>
> Not sure these questions apply after what I said above.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/lldb-dev/attachments/20160307/cd61d429/attachment.html>