[LLVMdev] Generalized dead allocation elimination?

[Philip Reames]

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