[llvm-dev] Optimizing memory allocation for custom allocatorsand non C code

[Nuno Lopes via llvm-dev]

> On 01/04/2016 10:37 AM, Amaury SECHET wrote:
>> I had this on my TODO list for a while, but the recent introduction of 
>> inaccessiblememonly makes it suddenly more urgent, as there is a risk to 
>> waste effort in duplicated work and/or end up with suboptimal solutions. 
>> I collected 2 use cases for inaccessiblememonly :
>>  - Allocation like functions.
>>  - Runtime functions for managed languages, that touch state that the 
>> program itself can never touch directly.
>>
>> My initial reflection was that MemoryBuiltins use a set of hardcoded 
>> functions to do its magic. Doing so, it support the C API fairly well, 
>> some variation of the operator new, and that's it. It seems unlikely and 
>> counter productive that all language dump their runtime in there, and 
>> won't work when feature like C++ templates comes in.
> I've been looking at this some over the last week and have been trying to 
> separate the component properties MemoryBuiltins provides.  So far, I have 
> the following distinct properties:
> 1) Aliasing - malloc and calloc are assumed not to modify any module 
> visible value in MemoryDependenceAnalysis.  I believe this should be 
> replaceable with inaccessiblememonly.
> 2) Observability - We assume in InstCombine that allocation itself is not 
> directly observable.  That is, we will remove an allocation site which is 
> not otherwise used.  We assume the same for free.
> 3) Infinite abstract heap - We assume that malloc only fails if out of 
> memory and that out of memory is not a observable condition.  In 
> particular, we will fold null checks to an unused malloc to false meaning 
> that OOM may fail to be observed.
> 4) Nullability - Operator new was hardcoded to return null.  This is split 
> out in http://reviews.llvm.org/D15820 which I'll be submitting shortly.
> 5) noalias - We assume that allocation returns a noalias pointer and that 
> stores to that location are not observable unless the pointer is captured.
> 6) Malloc/Free pairing - We assume that using the incorrect form of free 
> is UB and thus we can pretend the proper form was used for all of the 
> preceding.

Seems fairly complete list of the properties that currently used by the 
optimizers.
I can remember of two more:
- Allocated size: MemoryBuiltins knows how to compute the size of an 
allocated object by malloc/new/strdup/etc.  This information is used for 
e.g. aliasing, lowering __builtin_object_size, bounds checks 
instrumentation, etc.  It would be interesting to generalize this support 
for custom allocators.
- Initialization: LLVM knows that calloc/strdup/.. return initialized 
memory, while malloc doesn't.  A load from a malloc'ed pointer is folded to 
undef.

Nuno