[LLVMdev] RFC: Reduce the memory footprint of DIEs (and DIEValues)

Sean Silva chisophugis at gmail.com
Wed May 20 18:10:50 PDT 2015


Just wanted to say awesome data!

-- Sean Silva

On Wed, May 20, 2015 at 11:28 AM, Duncan P. N. Exon Smith <
duncan at exonsmith.com> wrote:

> Pete Cooper and I have been looking at memory profiles of running llc on
> verify-uselistorder.lto.opt.bc (ld -save-temps dump just before CodeGen
> of building verify-uselistorder with -flto -g).  I've attached
> leak-backend.patch, which we're using to make Intrustruments more
> accurate (instead of effectively leaking things onto BumpPtrAllocators,
> really leak them with malloc()).  (I've collected this data on top of a
> few not-yet-committed patches to cheapen `MCSymbol` and
> `EmitLabelDifference()` that chop around 8% of memory off the top, but
> otherwise these numbers should be reproducible in ToT.)
>
> The `DIE` class is huge.  Directly, it accounts for about 15% of backend
> memory:
>
>     Bytes Used  Count           Symbol Name
>       77.87 MB       8.4%       318960
>  llvm::DwarfUnit::createAndAddDIE(unsigned int, llvm::DIE&, llvm::DINode
> const*)
>       46.34 MB       5.0%       189810
>  llvm::DwarfCompileUnit::constructVariableDIEImpl(llvm::DbgVariable const&,
> bool)
>       25.57 MB       2.7%       104752
>  llvm::DwarfCompileUnit::constructInlinedScopeDIE(llvm::LexicalScope*)
>        8.19 MB       0.8%       33547
> llvm::DwarfCompileUnit::constructImportedEntityDIE(llvm::DIImportedEntity
> const*)
>
> A lot of this is the pair of `SmallVector<, 12>` it has for its values
> (look into `DIEAbbrev` for the second one).  Here's a histogram of how
> many DIEs have each value count:
>
>     # of Values  DIEs with #  with # or fewer
>               0         3128             3128
>               1       109522           112650
>               2       180382           293032
>               3        90836           383868
>               4       115552           499420
>               5        90713           590133
>               6         4125           594258
>               7        17211           611469
>               8        18144           629613
>               9        22805           652418
>              10          325           652743
>              11          203           652946
>              12          245           653191
>
> It's crazy that we're paying for 12 up front on every DIE.  (This is
> a reformatted version of num-values-with-totals.txt, which I've
> attached along with a few other histograms Pete collected.)
>
> The `DIEValue`s themselves, which get leaked on the BumpPtrAllocator,
> also take up a huge amount of memory (around 4%):
>
>     Graph        Category       Persistent Bytes        # Persistent    #
> Transient     Total Bytes     # Total Transient/Total Bytes
>     0   llvm::DIEInteger        19.91 MB        652389  0       19.91 MB
>       652389  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIEString 13.83 MB        302181  0       13.83 MB
> 302181  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIEEntry  10.91 MB        357506  0       10.91 MB
> 357506  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIEDelta  10.03 MB        328542  0       10.03 MB
> 328542  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIELabel  5.14 MB 168551  0       5.14 MB 168551
> <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIELoc    3.41 MB 13154   0       3.41 MB 13154
>  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIELocList        1.86 MB 61055   0       1.86 MB 61055
>  <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIEBlock  11.69 KB        44      0       11.69 KB
> 44      <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>     0   llvm::DIEExpr   32 Bytes        1       0       32 Bytes        1
>      <XRRatioObject: 0x608025658ea0>  %0.00, %0.00
>
> We can do better.
>
>  1. DIEValue should be a discriminated union that's passed by value
>     instead of pointer.  Most types just have 1 pointer of data.  There
>     are four "big" ones, which still need a side-allocation on the
>     BumpPtrAllocator: DIELoc, DIEBlock, DIEString, and DIEDelta.
>     Even for these, the side allocation just needs to store the data
>     itself (skipping the discriminator and the vtable entry).
>  2. The contents of DIE's Abbrev field should be integrated with the
>     list of DIEValues.  In particular, DIEValue should contain a
>     `dwarf::Form` and `dwarf::Attribute`.  In total, `sizeof(DIEValue)`
>     will still be just two pointers (1st pointer: discriminator, Form,
>     and Attribute; 2nd pointer: data).  DIE should stop storing a
>     `DIEAbbrev` itself, instead constructing one on demand, renaming
>     `DIE::getAbbrev()` to
>     `DIE::getOrCreateAbbrev(FoldingSet<DIEAbbrev>&)` or some such.
>  3. DIE's list of DIEValues is currently a `SmallVector<, 12>`, but a
>     histogram Pete ran shows that half of DIEs have 2 or fewer values,
>     and 85% have 4 or fewer values.  We're paying for 12 (!) upfront
>     right now for each DIE.  Instead, we should optimize for 2-4
>     DIEValues.  Not sure whether a std::forward_list would suffice, or if
>     we should do something fancy like:
>
>         struct List {
>           DIEValue Values[2];
>           PointerIntPair<List *, 1> NextAndSize;
>         };
>
>     Either way we should move the allocations to a BumpPtrAllocator
>     (trivial if it's a list instead of vector).
>  4. `DIEBlock` and `DIELoc` inherit both from `DIEValue` and `DIE`, but
>     they're only ever used as the former.  This is just a convenience
>     for building up and emitting their DIEValues.  Now that we've trimmed
>     down and simplified that functionality in `DIE`, we can extract it
>     out and make it reusable -- `DIELoc` should "have-a" DIEValue list,
>     not "be-a" DIE.
>  5. The children of DIE are stored in a `vector<unique_ptr<DIE>>`, which
>     requires side allocations.  If we use an intrusively linked list,
>     it'll be easy to avoid side allocations without hitting the
>     pointer-validity problem highlighted in the header file.
>  6. Now that DIE has no side allocations, we can move all the DIEs to a
>     BumpPtrAllocator and remove the malloc traffic.
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150520/4afaf612/attachment.html>


More information about the llvm-dev mailing list