[LLVMdev] [RFC] Less memory and greater maintainability for debug info IR

[Duncan P. N. Exon Smith]

> On Oct 13, 2014, at 3:23 PM, David Blaikie <dblaikie at gmail.com> wrote:
> 
> 
> 
> On Mon, Oct 13, 2014 at 3:02 PM, Duncan P. N. Exon Smith <dexonsmith at apple.com> wrote:
>> In r219010, I merged integer and string fields into a single header
>> field.  By reducing the number of metadata operands used in debug info,
>> this saved 2.2GB on an `llvm-lto` bootstrap.  I've done some profiling
>> of DW_TAGs to see what parts of PR17891 and PR17892 to tackle next, and
>> I've concluded that they will be insufficient.
>> 
> Could you explain what your end-goal here looked like and what data you used to evaluate its insufficiency?

In the links of C++ programs I've looked at, most `Value`s are line
tables and local variables.  E.g., for the `llvm-lto.lto.bc` case
I've used for memory numbers:

  - 23967800 Value
      - 16837368 MDNode
          - 7611669 DIDescriptor
              - 4373879 DW_TAG_arg_variable
              - 1341021 DW_TAG_subprogram
              -  554992 DW_TAG_auto_variable
              -  360390 DW_TAG_lexical_block
              -  354166 DW_TAG_subroutine_type
          - 7500000 line table entries
      -  5850877 User
      -   693869 MDString

IIUC, line tables and local variables need to be referenced directly
from the rest of the IR, so they can't be sunk into other nodes.

Relevant to your question, I didn't a way to sufficiently decrease
the numbers of these (or the number of their operands).

> Just to be clear, what I was picturing was that, starting with your initial improvement, we'd string-ify more data in the records but eventually we'd start stringifying across records (eg: rolling a DW_TAG_structure_type's members into the structure type itself, one big string). In the end we'd just pull out the non-metadata references (like the llvm::Function* in the DW_TAG_subroutine_type metadata) into a table kept separately from a handful of big strings of debug info (I say a handful, as we'd keep the types separate so they could be easily deduplicated).

I was thinking along the same lines.  Unfortunately, there aren't
enough types left for that to make a big impact.

Unless you envisioned a completely different way of dealing with
`@llvm.dbg.value` and `!dbg` references?

>> Instead, I'd like to implement a more aggressive plan, which as a
>> side-effect cleans up the much "loved" debug info IR assembly syntax.
>> 
>> At a high-level, the idea is to create distinct subclasses of `Value`
>> for each debug info concept, 
> 
> My concern with this is baking parts of our current debug info representation into IR constructs seems rather heavyweight. If we need to add first class IR constructs to cope with debug info I'd hope to find, ideally, one, general purpose extension we can use for this (& possibly for other things). But maybe the bar for adding first class IR constructs is lower than I've imagined it to be.

Since 75% of all `Value`s are debug info, representing them well
seems worthwhile to me.

>> starting with line table entries and moving
>> on to the DIDescriptor hierarchy.  By leveraging the use-list
>> infrastructure for metadata operands -- i.e., only using value handles
>> for non-metadata operands -- we'll improve memory usage and increase
>> RAUW speed.
>> 
>> My rough plan follows.

(Note the following sentence, which I think you missed.)

>> I quote some numbers for memory savings below
>> based on an -flto -g bootstrap of `llvm-lto` (i.e., running `llvm-lto`
>> on `llvm-lto.lto.bc`, an already-linked bitcode file dumped by ld64's
>> -save-temps option) that currently peaks at 15.3GB.
>> 
>>  1. Introduce `MDUser`, which inherits from `User`, and whose `Use`s
>>     must all be metadata.  The cost per operand is 1 pointer, vs. 4
>>     pointers in an `MDNode`.
> 
> Perhaps a generic MD-only-node might be a sufficiently generically valuable IR construct.
> 
> A similar alternative: A schematized metadata node. Much like DWARF, being able to say "this node is of some type T, defined elsewhere in the module - string, int, string, string, etc... ". Heck, this could even be just a generic improvement to llvm IR, maybe? (the textual representation might not need to change at all - IR Generation would just do much like DWARF generation in LLVM does - create abbreviation/type descriptions on the fly and share them rather than having every metadata node include its own self-description)
> 

"Being generic" seems like a defect to me, not a feature.  If you need
to add support for every IR construct to the backend to emit DIEs, etc.,
then what's the benefit in being able to express arbitrary other things?


>>  2. Create `MDLineTable` as the first subclass of `MDUser`.  Use normal
>>     fields (not `Value`s) for the line and column, and use `Use`
>>     operands for the metadata operands.
>> 
>>     On x86-64, this will save 104B / line table entry.  Linking
>>     `llvm-lto` uses ~7M line-table entries, so this on its own saves
>>     ~700MB.
>> 
>>     Sketch of class definition:
>> 
>>         class MDLineTable : public MDUser {
>>           unsigned Line;
>>           unsigned Column;
>>         public:
>>           static MDLineTable *get(unsigned Line, unsigned Column,
>>                                   MDNode *Scope);
>>           static MDLineTable *getInlined(MDLineTable *Base, MDNode *Scope);
>>           static MDLineTable *getBase(MDLineTable *Inlined);
>> 
>>           unsigned getLine() const { return Line; }
>>           unsigned getColumn() const { return Column; }
>>           bool isInlined() const { return getNumOperands() == 2; }
>>           MDNode *getScope() const { return getOperand(0); }
>>           MDNode *getInlinedAt() const { return getOperand(1); }
>>         };
>> 
>>     Proposed assembly syntax:
>> 
>>         ; Not inlined.
>>         !7 = metadata !MDLineTable(line: 45, column: 7, scope: metadata !9)
>> 
>>         ; Inlined.
>>         !7 = metadata !MDLineTable(line: 45, column: 7, scope: metadata !9,
>>                                    inlinedAt: metadata !10)
>> 
>>         ; Column defaulted to 0.
>>         !7 = metadata !MDLineTable(line: 45, scope: metadata !9)
>> 
>>     (What colour should that bike shed be?)
>> 
>>  3. (Optional) Rewrite `DebugLoc` lookup tables.  My profiling shows
>>     that we have 3.5M entries in the `DebugLoc` side-vectors for 7M line
>>     table entries.  The cost of these is ~180B each, for another
>>     ~600MB.
>> 
>>     If we integrate a side-table of `MDLineTable`s into its uniquing,
>>     the overhead is only ~12B / line table entry, or ~80MB.  This saves
>>     520MB. 
>> 
>>     This is somewhat perpendicular to redesigning the metadata format,
>>     but IMO it's worth doing as soon as it's possible.
>> 
>>  4. Create `GenericDebugMDNode`, a transitional subclass of `MDUser`
>>     through an intermediate class `DebugMDNode` with an
>>     allocation-time-optional `CallbackVH` available for referencing
>>     non-metadata.  Change `DIDescriptor` to wrap a `DebugMDNode` instead
>>     of an `MDNode`.
>> 
>>     This saves another ~960MB, 
> 
> 960 from what?

This number references the sentence noted above.

>  
>> for a running total of ~2GB.
> 
> ~2GB is the total of what? (you mention a lot of numbers in this post, but it's not always clear what they're relative to/out of/subtracted from)

This number references the sentence noted above.

>>  
>>     Proposed assembly syntax:
>> 
>>         !7 = metadata !GenericDebugMDNode(tag: DW_TAG_compile_unit,
>>                                           fields: "0\00clang 3.6\00...",
>>                                           operands: { metadata !8, ... })
>> 
>>         !7 = metadata !GenericDebugMDNode(tag: DW_TAG_variable,
>>                                           fields: "global_var\00...",
>>                                           operands: { metadata !8, ... },
>>                                           handle: i32* @global_var)
>> 
>>     This syntax pulls the tag out of the current header-string, calls
>>     the rest of the header "fields", and includes the metadata operands
>>     in "operands".
>> 
>>  5. Incrementally create subclasses of `DebugMDNode`, such as
>>     `MDCompileUnit` and `MDSubprogram`.  Sub-classed nodes replace the
>>     "fields" and "operands" catch-alls with explicit names for each
>>     operand.
> 
> I wouldn't mind seeing how expensive it would be if these schema descriptions were within the module itself - so we didn't have to bake them into the IR spec, but could still share them between every usage within a module.

It's already baked into the IR spec, since the backend needs to
understand debug info to emit it.  We might as well understand what
exactly we're representing by formalizing it.

>  
>> 
>>     Proposed assembly syntax:
>> 
>>         !7 = metadata !MDSubprogram(line: 45, name: "foo", displayName: "foo",
>>                                     linkageName: "_Z3foov", file: metadata !8,
>>                                     function: i32 (i32)* @foo)
>> 
>>  6. Remove the dead code for `GenericDebugMDNode`.
>> 
>>  7. (Optional) Refactor `DebugMDNode` sub-classes to minimize RAUW
>>     traffic during bitcode serialization.  Now that metadata types are
>>     known, we can write debug info out in an order that makes it cheap
>>     to read back in.
>> 
>>     Note that using `MDUser` will make RAUW much cheaper, since we're
>>     using the use-list infrastructure for most of them.  If RAUW isn't
>>     showing up in a profile, I may skip this.
>> 
>> Does this direction seem reasonable?  Any major problems I've missed?