Shea Levy
2014-Feb-05 21:22 UTC
[LLVMdev] [shea@shealevy.com: Re: Generalized dead allocation elimination?]
Whoops, forgot to cc the ml ----- Forwarded message from Shea Levy <shea at shealevy.com> ----- Date: Wed, 5 Feb 2014 16:21:12 -0500 From: Shea Levy <shea at shealevy.com> To: Philip Reames <listmail at philipreames.com> Subject: Re: [LLVMdev] Generalized dead allocation elimination? User-Agent: Mutt/1.5.22 (2013-10-16) Hi Philip, On Wed, Feb 05, 2014 at 09:10:32AM -0800, Philip Reames wrote:> On 2/2/14 8:08 AM, Shea Levy wrote: > >Hi all, > > > >After some discussion on #llvm I learned that there is code > >(isAllocSiteRemovable) that removes superfluous malloc/free pairs. Is > >there any way to generalize this to other allocators? > Looking through the code, it appears to rely on an explicit list of > allocation functions in the LibFunc namespace. I suspect you already found > this from your other question on the mailing list. One thing worth noting is > that the code is fairly strict about the signature of an allocation > function. (See getAllocationData in MemoryBuiltins.cpp) >Yeah, my other mail was after doing more digging on this problem :) Hmm I'll double-check the signature, but I believe in my use case I set the signature to be the same as what clang generated for glibc malloc.> > I believe we also support an function attribute (?) for marking a > malloc-like function. It might be an option to extend MemoryBuildins.cpp > with handling for this attribute. >There is a __malloc__ attribute in gnuc, which clang uses to mark a function noalias, but as far as I can see there's no llvm attribute for alloc specifically. boehm-gc does set that attribute. I'd be happy to try to implement such an attribute, do you think it would be welcome?> > > > >My example use case is this: Idris is a purely functional language which > >has a somewhat experimental llvm backend. I've recently added a pure > >interface to contiguous chunks of memory that uses fill pointers and > >power of 2 allocation for efficient appending. Currently we have > >primitives for appending uint8_ts, uint16_ts, uint32_ts, uint64_ts, and > >other buffers to an existing buffer, but ideally we'd like to reduce it > >to just a primitive for appending uint8_t and implement the rest in > >Idris code on top of that primitive. This can cause a lot of spurious > >intermediate allocations, though: Directly appending a 64-byte buffer to > >an empty one requires just one allocation, while appending a 64-byte > >buffer byte-by-byte will require allocations at 1, 2, 4, 8, etc. bytes. > >Leaving aside for now the question of whether successive appends can be > >combined into one operation by llvm's passes (we still need to test > >this), as far as I can tell there is no way to mark the allocation > >function (we use boehm-gc, so GC_alloc_atomic in this case) such that > >llvm can know that since the intermediate value is just copied into then > >later copied out of into another pointer, the allocation can be elided. > Looking through the code, I only see handling for unused allocations. > Extending this to handle data which is copied into a new buffer (or > realloc'd) seems like a reasonable approach, but if that has been > implemented, I didn't find it. >Not sure where it's implemented, but in tests using malloc in powers of 2 (no realloc) and just copying from one buffer to the next was optimized away to a single allocation.> > >Can this be done? If not, does the situation change if we implement our > >own accurate GC on top of llvm's intrinsics? > I would not expect this to have any effect. > > Philip >Thanks for the feedback! ~Shea ----- End forwarded message -----