llvm dev - Feb 2014 - [LLVMdev] Generalized dead allocation elimination?

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?

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.

Can this be done? If not, does the situation change if we implement our
own accurate GC on top of llvm's intrinsics?

Thanks,
Shea

P.S. I am not subscribed to the list so please CC me in replies.

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)

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