[RFC] Refactoring DILocation to use compact function-local storage

[StephenTozer]

tl;dr by changing source locations (DILocations) from being global MDNode objects to being efficiently-stored function-local data, memory usage in debug info builds can be significantly cut; this comes with significant disruption to downstream forks and users of LLVM’s API, and so needs careful consideration.

Background

In LLVM’s debug info metadata, source locations of instructions are represented with the DILocation class, a subclass of MDNode, which contains the fields (Scope, InlinedAt, Line, Column, IsImplicitCode). Although it is necessary for debug info, DILocation ends up comprising a significant portion of LLVM’s memory consumption depending on the input. The exact percentage varies greatly depending on the source and build configuration, anywhere from <0.1% to 10% at peak memory usage (and often significantly higher during optimization passes). The reason for the heavy memory consumption can roughly be summarized as follows:

• DILocation uses 16-24 bytes to store source location data, and 24 bytes to store generic MDNode data; this data is useful in some contexts, such as parsing, but is wasted throughout most of compilation.
• DILocations are far more numerous than other MDNodes; in the cases I looked through they generally comprised anywhere from 30-80% of all MDNodes, scaling with the amount of inlining that takes place as we duplicate every inlined DILocation.
• For each DILocation, we must also add a DenseMap entry in the LLVM context object as part of the uniquing behaviour of metadata, which can quickly end up consuming a measurable % of program memory.

It is certainly possible to make a variety of improvements that partially address each of these points, but they can’t be fundamentally changed without breaking some of the behaviours that LLVM currently relies on. With that in mind, we (Sony) decided to experiment with completely reworking source locations, and believe the result is worth implementing in full.

Proposal

In the prototype, we’ve split the DILocation fields above into two separate structs - “Context” data, (Scope, InlinedAt), and “Location” data, (Line, Column, IsImplicitCode). These are stored in two separate arrays owned by a DISubprogram, such that source locations are now function-local metadata. Finally, instead of each Instruction holding a pointer to a DILocation, they instead hold a pair of uint32_t indexes into the context and location arrays.

This has some significant implications for usage of source locations: Instructions no longer have a direct reference to their own source location, so a reference to the owning DISubprogram is needed. Although this is sometimes inconvenient, it is a logical limitation: DILocations are only used in a function-local context, and so everywhere that they are used, a reference to the owning DISubprogram is either present or easily-obtainable. In return, so far the prototype reduces the overall memory cost of DILocations significantly, around 50% for most inputs tested in the CTMark suite, and as the current implementation is very much unrefined and unoptimized we expect further improvements to be made.

For this post I’ll leave the technical explanation at just a rough overview, as the implementation is very much a work-in-progress - the MIR backend has yet to be fully implemented, the prototype as a whole is not review-ready, and there are a number of core components that will change before the final implementation. For more details on the implementation however, see the draft prototype and accompanying documentation here: Prototype: Replace DILocations with function-local source locations by SLTozer · Pull Request #133949 · llvm/llvm-project · GitHub

What comes next

The concept is not fully proven yet, though the prototype fundamentally works: there are still bugs and missing features, but the “tricky” cases are solved or have known solutions. Runtime performance impacts are still unclear - the prototype currently has a high runtime cost in Clang (which will be fixed later), and is about equal during optimizations, but this may change either way as the implementation is finalized.

More challenging than the mere implementation of this change however is the rollout - the change fundamentally affects all APIs that interact with source locations, such as the C API, which currently uses opaque MetadataRefs to pass debug locations around. While the in-tree updates to uses of DILocations are mostly trivial, this still creates work for any maintainers of downstream forks; unlike other significant rewrites, such as the replacing debug intrinsics with debug records, there is no simple runtime fallback for this change. Therefore, if the approach is accepted, the transition would need some careful planning to avoid causing too much disruption.

What we’re interested in right now is input from stakeholders, primarily anyone who:

• has experience working with LLVM’s metadata model,
• has a strong interest in reducing memory consumption in debug info builds,
• consumes any of LLVM’s APIs that may be affected by these changes,
• maintains a downstream fork of LLVM, particularly with any debug-info-related changes.

Any input is welcome, but we would particularly appreciate any technical feedback on the design direction, any issues you foresee with this approach, how this change could/would affect your own usage of or modifications to LLVM, and any suggestions for how this change could be made easier to work with/transition into.

Note also that by packing source location data more efficiently, we free up some headroom to expand our representation of source locations: this work was motivated by our work on Key Instructions, a feature which adds new fields to DILocation to improve stepping in a debugger (more details here). This rewrite reduces the cost of adding these fields, and may similarly benefit any other projects that look to extend LLVM’s representation of source locations.

Pinging a few individuals who this may be particularly relevant to: @adrian.prantl @dblaikie @echristo @nikic

[dblaikie]

+@rnk

Awesome - really long standing issue worth looking into.

A couple of questions:

• What’s the impact to a non-debug build? I would’ve thought some concerns about a more built-in representation would add overhead to non-debug builds which might be difficult, but I forget how it’s all organized so I’m not 100% sure on that (like the dbgloc of an instruction is already a special pointer, so replacing that with two ints is size-neutral, maybe?)

• You mention these things are stored in the DISubprogram - but there are some cases where instructions with locations are in functions without subprograms, though the instructions perhaps still have /a/ DISubprogram they may be harder to handle? Specifically the situation I’m thinking of is a function with debug info being inlined into a function without debug info. (we preserve the debug info into the inlining in case the non-debug-info function is further inlined into another function with debug info)

• Two uint32 indexes - any sense of whether that can be shrunk further (perhaps at least the scopes could be int16 or something (though shrinking only one might not save space due to alignment padding taking up the saved space anyway))

[StephenTozer]

Thanks! (Also looks like the @rnk ping might not have registered).

What’s the impact to a non-debug build?

It should be nothing - the storage exists in the DISubprogram (in the current design), so that uses up nothing extra, and the pair of indexes occupy the same space as the old DebugLoc field (which was present with and without debug info).

there are some cases where instructions with locations are in functions without subprograms

Indeed, that’s one of the “tricky” cases I encountered. It’s not a particularly common case (in order for it to matter we need to inline from a debug function to a nodebug function, and then inline that into a debug function), so we can afford tradeoffs that are “expensive only when needed”. The two natural solutions as I see it are to either 1) move the storage into the function instead, which simplifies things but adds a (potentially small) cost to non-debug builds, or 2) create a smaller piece of metadata which just holds the function-local metadata storage, and is attached to nodebug functions (could be a !dbg attachment, but it doesn’t need to be) that have had debug locations inlined into them. The latter seems like the best solution to me, since it only costs anything when this situation arises, but I’ve not jumped in to measure this yet!

Two uint32 indexes - any sense of whether that can be shrunk further

Quite possibly - though in my case I’ve mainly considered whether they could be shrunk to fit more indexes in, to enable further debug info enhancements - but reducing the size of Instruction for all builds would also be a positive outcome! In any case, I don’t have a great sense of what the upper bound of the indexes might be - it seems rather unlikely that you’d ever come close to having 2^32 (scope+inlinedAt) combinations in a function, but 2^16 sounds like the sort of limit that could actually be hit in some pathological case (e.g. giant generated switch blocks where every branch calls into some nested inline functions).

[rnk]

Great work, I’m glad to see folks working on this! I think it would be a great enhancement if we could make source locations sufficiently cheap that we could always track them, which is, BTW, the norm for MLIR.

This comes up when people add backend diagnostics. While they are discouraged, there are many of them, and users continue to ask for more of them. We could make these diagnostics significantly more user-friendly with ubiquitous source location information.

Speaking of the design, the direction I was contemplating before was, what inspiration can we borrow from the Clang SourceManager / SourceLocation representation? I think the Clang SourceManager contains too many details about the C preprocessor to migrate from Clang to LLVM, but we could push down some kind of file/buffer list and token offset encoding table as part of the LLVM IR serialization. Clang is able to represent the source location of every token in the compilation in 32-bits of information (64-bit sloc build configs notwithstanding). LLVM needs to augment that with more information (scope & inlinedAt), but even with one 64-bit integer and some tables, we can represent a lot more sloc information than we do today.

The challenges here probably all have to do with transformations. How do we merge your DISubprogram tables when we inline source locations? If we had module-level source manager-like tables, how do we merge them during full and thin LTO? Are there ways that we could represent the inlined call stack information to make inlining cheap, fast, and convenient? It seems like there are some similarities between source files and inline call frames. I can imagine representing an inlined call site as an array of arbitrary source locations, and the indices which point into them are that source location combined with an inlinedAt call site location. This allows nesting, and could be contained in a module-wide 64-bit source location index space.

Another thing to consider here is the readability of the textual representation. I think readable debug info goes a long way to helping transform authors accurately update source locations. Scoping is an important aspect of project management, so don’t let this derail the project, but it would be good if the in memory data model supports readable textual representations. I’ve been dreaming of locations that look like our asm comments, something like load i32, ptr %x #dbg(!1234:AsmPrinter.cpp:4565:12), where “!1234” is the real scope link (can this also serve for inlinedAt?), and AsmPrinter.cpp is a file basename that exists mainly for readability.

Something else to consider is that sample PGO folks would like to encode more information into the source location. They’ve already loaded up DWARF discriminators with 24-bits of flow-sensitivity information, but this is an extremely opaque bitfield representation (original RFC, but I’d love to see current docs). I’ve been getting questions like, would it be possible to encode which source locations are inside this critical section, as defined by this C++ RAII critical section variable? This roughly maps to the DWARF scope, but I’m not sure it’s sufficient.

cc @ZequanWu , who I was encouraging to look into this space in a few months.

[snehasish]

@rnk

Another thing to consider here is the readability of the textual representation. I think readable debug info goes a long way to helping transform authors accurately update source locations.

+1 since this, in turn, mitigates profile degradation for SamplePGO as optimizations continue to evolve.

[StephenTozer]

Thanks for the detailed response; I’m not familiar enough with Clang’s SourceManager to draw parallels between them, but one of the advantages of using per-function source locations rather than per-module is that we can keep the storage vectors tightly allocated, and we almost never have to perform large or frequent reallocations. I’ll answer to your points, though in case my short explanations don’t suffice I also have a readme on the development branch that explains some details of the implementation and the decisions made.

@rnk

How do we merge your DISubprogram tables when we inline source locations?

Inlining is quite straightforward; essentially, when we inline bar into foo, we can directly copy bar’s context and location arrays to the end of foo’s. Then, for each inlined instruction, we update its source location by incrementing its indexes by the original length of the corresponding array in foo, so that it matches up with the copied entries in the combined array.
For representing inline callstacks, I mentioned that the context array has an inlinedAt field - just as the current inlinedAt field in a DILocation is a pointer to another DILocation, the inlinedAt field in the index-based DebugLoc model is another DebugLoc, i.e. a pair of indexes; these indexes point to the (Context, Location) entries that correspond to the original call. Thus, we traverse an inlined call stack by following the inlinedAt indexes back through the Context array.

@rnk

Another thing to consider here is the readability of the textual representation.

The textual representation I’m using at the moment (purely for development purposes, not intended as a final design) directly prints the indexes for each instruction, e.g. load i32, ptr %x !DebugLoc(loc: 2, context: 1), and then the corresponding DISubprogram contains arrays, e.g. ..., srcLocs: [(0, 0), (5, 1), (6, 5)], context: [(!2), (!4)], .... This does not improve clarity by any means, but it does have one advantage in that it simplifies the parsing of IR; this is not a performance critical task anywhere (to my knowledge) so this may be irrelevant, but it does remove the need for us to track forward references to location metadata - when you parse the indexes, you can store them directly in the instruction without needing to create temporary metadata.
I have, however, started adding information into comments to make visually parsing this easier. For now that just takes the form of printing the subprogram ID for easier lookup, i.e. !DebugLoc(loc: 2, context: 1) ; !2, but I intended to eventually add detailed comment printouts similar to what you described to make it much simpler to understand. Taking your approach as-is might also work, I just haven’t thought about it too much yet; the main difficulty would be in relation to inlining, where we have some distinct DILocations that aren’t attached to instructions but that must be preserved without combining identical-but-distinct inlinedAt locations - which would be tricky if we only printed out location information directly rather than maintaining an explicit index.

@rnk

Something else to consider is that sample PGO folks would like to encode more information into the source location.

At the moment, all I can confidently say is that there should be more headroom for adding information to source locations; with a more detailed look at any specific scheme, I could make a better guess as to how it would slot in to the current design. Briefly though, the two ways we can add more information are 1) expanding either “Context” or “Location” to contain more fields, or 2) adding an additional index to DebugLoc. The former is the easier option in most cases, as while it increases the cost of storing all source locations, there is no strict limit in-place for the size of those structs. The latter is riskier, since we only have 64-bits to use for indexes without inflating the size of Instruction, which would be very undesirable; but it may be efficient to try and squeeze a 3rd (probably not a 4th) index in there, if we have some additional information to store that is not highly correlated with either the context or location fields.

[movietravelcode]

@StephenTozer

Prototype: Replace DILocations with function-local source locations by SLTozer · Pull Request #133949 · llvm/llvm-project · GitHub

It’s a really great attempt! DebugInfo is indeed a high memory consumption part during the compilation. However I once wanted to try your PR, but found that the PR build fails. May I ask if this work is still in progress? I’m very interested in reducing memory consumption in debug info builds.

[StephenTozer]

The prototype covers a limited area of the compiler - it has successfully run middle-end optimizations for most of the programs in the LLVM test suite, but I haven’t fully implemented it to perform a full compilation correctly. The work will be completed, but it’s a reasonably large chunk of work that I’ve not yet been able to allocate the time to finish, so unfortunately it may take some time until it’s done.

[StephenTozer]

I’m now preparing to begin work on moving the prototype to a full implementation. Most of the implementation at this point is mechanical; the major edge cases are already handled by the prototype, and so the remaining legwork is updating code across the compiler to handle the new source locations correctly, and polishing/optimizing the implementation further. One major remaining decision however is the IR representation of the new DILocations.

In terms of memory usage, storing each individual source location in its own Metadata object is quite inefficient, and this change aims to remedy that. From an IR perspective however, this has been a very convenient property, and there isn’t prior art in the IR for representing the new model. Currently, source location representation is quite straightforward:

define i32 @addition(i32 %a, i32 %b) !dbg !7 {
%add = add i32 %a, %b, !dbg !10
ret i32 %add, !dbg !12
}
...
!7 = !DISubprogram(name: "addition", ..., inlinedCallLocs: [])
!8 = distinct !DILexicalBlock(scope: !7, file: !4, line: 3, column: 1)
!9 = !DISubprogram(name: "add", ...)
!10 = !DILocation(line: 10, column: 4, scope: !9, inlinedAt: !11)
!11 = distinct !DILocation(line: 5, column: 7, scope: !8)
!12 = !DILocation(line: 6, column: 2, scope: !8)

Each instruction with a source location has a !dbg !<index> metadata attachment, and the numbered metadata section contains !<index> = !DILocation(...) containing the complete source location (referring to other numbered metadata for scope and inlinedAt). This makes it quite easy to find the source location for an instruction and to traverse the scopes/inline chain from a text editor. The new model is intrinsically more complicated; we have a pair of indices into vectors that are stored in the metadata for the current function, which isn’t always easy to navigate to from a particular instruction.

My current proposal for how we might be able to represent this in IR is to inline debug location information, as suggested earlier by @rnk. As all !DILocations are already uniqued (except inlined callsites), this should never result in a loss of information: any locations which are identical in text should be identical in-memory and vice versa. Inlined calls are a little more complicated; these cannot be attached to an instruction, and must be referenceable from other instructions, but cannot be printed out as standalone metadata as they are still function-local. Therefore, these can be printed as an array in the !DISubprogram, and integer-indexed. The resulting representation looks like:

define i32 @addition(i32 %a, i32 %b) !dbg !7 {
%add = add i32 %a, %b, !dbg (line: 10, column: 4, scope: !9, inlinedAt: 0)
ret i32 %add, !dbg (line: 6, column: 2, scope: !8)
}
...
!7 = !DISubprogram(name: "addition", ..., inlinedCallLocs: [(line: 5, column: 7, scope: !8)])
!8 = distinct !DILexicalBlock(scope: !7, file: !4, line: 3, column: 1)
!9 = !DISubprogram(name: "add", ...)

There are some small nitpicks with this - it may not be appropriate to use !dbg as the prefix for location information anymore, since what follows is not an actual metadata object; #dbg might be a valid substitute instead, in-keeping with the similar use of #dbg_records to represent something that isn’t “standard” LLVM metadata (and also resembling asm comments, as was also mentioned by @rnk). The inlinedCallLocs array may also grow to be very long in some cases; besides printing elements on separate lines (with index comments) for sufficiently long arrays however, I don’t see a good way around this without some more substantial extensions.

Right now this design isn’t settled, but I believe it introduces the least friction for both the current implementation and for ongoing maintenance/future extensions - any thoughts or feedback on the IR format before this solidifies into a patch would be appreciated!

[jryans]

@StephenTozer

The inlinedCallLocs array may also grow to be very long in some cases; besides printing elements on separate lines (with index comments) for sufficiently long arrays however, I don’t see a good way around this without some more substantial extensions.

I think it will be okay as a human reader, as long as we ensure the array elements are printed on separate lines with index comments (as you mention) so that it’s easy to visually skim the different entries and quickly jump to the intended line based on info elsewhere in the IR.

I suppose you could still print the inlinedAt location info directly at the referencing instruction in the IR, even if it’s actually stored in memory in some function-level storage. This could also get messy in it’s own way I think, as inlined scope chains can go arbitrarily deep. It would also mean the printed IR representation diverges a bit from the in-memory storage model of the data.

Whichever approach is chosen, I am glad to hear the human reader is being considered, as I often find myself reading this data to sort out issues.

[StephenTozer]

@jryans

I suppose you could still print the inlinedAt location info directly at the referencing instruction in the IR, even if it’s actually stored in memory in some function-level storage.

This is technically possible, but it’s not enough to simply print the inlined-at location inline with the instruction: inline callsites are necessarily distinct DILocations, meaning that they cannot be uniqued based on their contents, in order to distinguish multiple inlined instances of the same call. So, even if we printed the inlined-at location, we would still need to print an “inlinedAt” index value to distinguish otherwise-identical inlined-at locations.

@jryans

It would also mean the printed IR representation diverges a bit from the in-memory storage model of the data.

Yes, the biggest issue with the proposal above in my mind is the divergence it introduces between the textual IR and the in-memory model. While there should be a one-to-one mapping between the two representations, the need for “translation” adds surface area for bugs to emerge. I think it’s worth it for a significantly more readable textual IR over the more “accurate” representation, but I could understand a preference for the latter.

[dblaikie]

@jryans

I suppose you could still print the inlinedAt location info directly at the referencing instruction in the IR, even if it’s actually stored in memory in some function-level storage. This could also get messy in it’s own way I think, as inlined scope chains can go arbitrarily deep. It would also mean the printed IR representation diverges a bit from the in-memory storage model of the data.

The main concern I have with this is that it’s lossy - not just different. It wouldn’t be possible to tell which locations were in the same inlined function and which were in two distinct inline functions from the same location (two calls inside a macro have the same file/line/col, for instance) - if I’m understanding correctly.

If they’re indexed - perhaps we could use some naming scheme like the numbered metadata - rather than an index and a comment? (eg: inlinedAt: @3 and then in the function metadata have @3 = ..., etc - so it can be easily greped, etc)

[StephenTozer]

@dblaikie

If they’re indexed - perhaps we could use some naming scheme like the numbered metadata - rather than an index and a comment? (eg: inlinedAt: @3 and then in the function metadata have @3 = ..., etc - so it can be easily greped, etc)

I’d like a solution where we have a specific IR section/data type to describe function-local metadata (such as inlined call sites), but I feel that it makes the proposal a harder sell for a small gain; we can still make inlined callsites grep-able with comments (e.g. if we comment !7@3 on both the inlinedAt reference and the inlined callsite location), while adding new IR constructs is non-trivial. Though if there’s an existing place in the IR that we could slot this data into that I’m missing, then it becomes much more feasible.

[dblaikie]

I guess I was suggesting something in between - something that renders more like a first class construct, but isn’t necessarily the fully generalized machinery for that.

& yeah, if this is the first instance of function local IR metadata, maybe that’s fine it’s not generalized (either fully, or even the way I’m suggesting) - though maybe the Apple folks (@JDevlieghere @adrian.prantl ) might have an interest in function-local metadata for the CAS stuff - so maybe there’s some more shared value (&then opportunities for shared investment) in that sort of direction sooner or later.

[OCHyams]

We’re on the same team so obviously in terms of upstream consensus this comment probably shouldn’t hold too much weight.

I like the proposed IR format, so +1 from me. The fact that inlinedAt fields are indices is essentially “not a regression” from a readability perspective as long as (as already discussed by others) it’s easy to grep to the indexed location. And having the rest printed inline is an improvement to debug info readability. It does add some noise for cases where the debug info is uninteresting, but I think we already have precedent for this in MIR?

I don’t have any strong opinion/insight into the function-local section discussion right now though. (Agree it sounds like potentially a useful direction, but I don’t have a good idea as to whether or not it’s worth it, what else it enables etc)

[aengelke]

Love this, thanks for working on this! Also happy to see that DebugLoc will no longer store a TrackingMDRef (I expect so, at least?) – this pointless tracking is fairly expensive and even now only used for parsing.

@StephenTozer

instead of each Instruction holding a pointer to a DILocation, they instead hold a pair of uint32_t indexes into the context and location arrays.

Do you have data on how much the two-value encoding in instruction saves over a single-value encoding (where, e.g., the location has a reference to the context or vice versa) in terms of memory usage and perf? I’d be interested in using another 4 bytes from Instruction for auxiliary data to be used by passes, preferably without growing by 8 bytes. (Put differently, I’d be interested in the cost of less efficient location encoding vs. the cost of growing Instruction by 8 bytes.)

[StephenTozer]

@aengelke

Do you have data on how much the two-value encoding in instruction saves over a single-value encoding (where, e.g., the location has a reference to the context or vice versa) in terms of memory usage and perf?

This could work - there are some notable conveniences to separating location and context, such as not having to allocate new location entries every time we create a line-0 location in a scope that doesn’t already have one, but the potential inconveniences may ultimately be low-impact; I’m certainly open to evaluating the idea it if it means preventing the size of Instruction from increasing by 8 bytes.

[StephenTozer]

@aengelke

I’d be interested in using another 4 bytes from Instruction for auxiliary data to be used by passes, preferably without growing by 8 bytes.

Revisiting this as I’m diving into the potential design of both reducing the size of DebugLoc information in Instruction as you discuss here, and including support for Multi-Sloc debug locations as discussed here. There are different tradeoffs to supporting each of these, and also of supporting both of these changes. I can imagine some of the benefits of reserving spare bytes for passes to use within Instruction, but do you have any information that you are currently able to share about how the auxillary bytes might be used and how much we might gain from them?

[aengelke]

@StephenTozer

I can imagine some of the benefits of reserving spare bytes for passes to use within Instruction, but do you have any information that you are currently able to share about how the auxillary bytes might be used and how much we might gain from them?

I began prototyping two years ago, but didn’t get around to work on this again — so this is largely ideas + estimates. My primary motivations are:

• InstCombine worklist. InstCombine is currently our most expensive pass and tracking the worklist index of instructions is a single expensive part. Might be 0.3–0.4% O3?
• FunctionLoweringInfo::ValueMap, mapping instructions to MIR registers. -0.18% stage2-O0g.
• ADCE liveness tracking. Little, but measurable impact. (NB: this is from 2024, the gain might be a bit larger now after some recent optimizations to ADCE.)
• GVN (+NewGVN), numbering values. Don’t have numbers off the top of my head.
• SROA/PromoteMemToReg numbers instructions already, could store this inline. Don’t have numbers off the top of my head.
• CloneFunction, mapping values to new values. Hard to estimate, because I’m quite unsure how to use that in a helper function.
• (Out-of-tree use case: TPDE-LLVM needs storage for instr numbers, this gives a >30% speedup over a hash table.)

There are probably several other passes that build large sets or maps of instructions and could benefit.

I see three ways how 4 bytes could be used, which could be mixed:

• Arbitrary inline storage. Must be reset before use, or set to a value lower than X after use.
• Set storage; Function tracks maximum “old” value, adding to a set gives higher value.
• Unique “unmodifyable” number, could be used in analyses.

Not really thought this through to the end, though. There’s some danger involved with the first two, because only one use of these can exist at a time, effectively preventing use outside of passes themselves in helpers/utils/analyses. This needs careful consideration and is part of the reason I haven’t pushed for this so far.

[StephenTozer]

Noting that a more recent version of this proposal has been posted here: [RFC] Function-Local Metadata: IR and API changes