[LLVMdev] [shea at shealevy.com: Re: Generalized dead allocation elimination?]

[Shea Levy]

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 -----