[lldb-dev] Question about building line tables

[Greg Clayton via lldb-dev]

The one thing that might confuse you is we actually store line entries using lldb_private::LineTable::Entry structures which do not have the byte size or the file as a FileSpec:

class LineTable {
protected:
  struct Entry
  {
        lldb::addr_t file_addr;                 ///< The file address for this line entry
        uint32_t    line;                       ///< The source line number, or zero if there is no line number information.
        uint16_t    column;                     ///< The column number of the source line, or zero if there is no column information.
        uint16_t    file_idx:11,                ///< The file index into CompileUnit's file table, or zero if there is no file information.
                    is_start_of_statement:1,    ///< Indicates this entry is the beginning of a statement.
                    is_start_of_basic_block:1,  ///< Indicates this entry is the beginning of a basic block.
                    is_prologue_end:1,          ///< Indicates this entry is one (of possibly many) where execution should be suspended for an entry breakpoint of a function.
                    is_epilogue_begin:1,        ///< Indicates this entry is one (of possibly many) where execution should be suspended for an exit breakpoint of a function.
                    is_terminal_entry:1;        ///< Indicates this entry is that of the first byte after the end of a sequence of target machine instructions.
  };
};

These are 16 bytes each since the file is represented as a file index and we only have the "lldb::addr_t file_addr" for the address.

But we dress them up into lldb_private::LineEntry structures for all other clients that consume line entries and those structures _do_ have information like the user wants to see it:

struct LineEntry
{
    AddressRange    range;                      ///< The section offset address range for this line entry.
    FileSpec        file;
    uint32_t        line;                       ///< The source line number, or zero if there is no line number information.
    uint16_t        column;                     ///< The column number of the source line, or zero if there is no column information.
    uint16_t        is_start_of_statement:1,    ///< Indicates this entry is the beginning of a statement.
                    is_start_of_basic_block:1,  ///< Indicates this entry is the beginning of a basic block.
                    is_prologue_end:1,          ///< Indicates this entry is one (of possibly many) where execution should be suspended for an entry breakpoint of a function.
                    is_epilogue_begin:1,        ///< Indicates this entry is one (of possibly many) where execution should be suspended for an exit breakpoint of a function.
                    is_terminal_entry:1;        ///< Indicates this entry is that of the first byte after the end of a sequence of target machine instructions.

};

Each instance is 64 bytes and quite a bit more expensive to copy around.




> On Mar 7, 2016, at 3:13 PM, Greg Clayton via lldb-dev <lldb-dev at lists.llvm.org> 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.
> _______________________________________________
> lldb-dev mailing list
> lldb-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-dev