[LLVMdev] Dataflow analysis based optimisations

Kenneth Uildriks kennethuil at gmail.com
Sun Aug 29 08:28:04 PDT 2010


On Sat, Aug 28, 2010 at 10:53 AM, David Given <dg at cowlark.com> wrote:
> On 28/08/10 02:20, Kenneth Uildriks wrote:
>> There are passes which mark function parameters as "nocapture", which
>> means that the function does not store the passed-in pointer for use
>> after that function returns.  If pointers to a newly created object
>> are only ever passed through "nocapture" parameters, never stored in a
>> global, and not returned from the function, then that object is dead
>> when the function that created the object returns.
>
> That sounds ideal; thanks!
>
> I assume that I would need to implement my own memory-allocation
> instruction and then produce a custom pass, running after the
> FunctionAttrsPass, which would then lower the instructions to either a
> call to malloc or an alloca instruction. I see vague references to an
> LLVM malloc instruction; did this disappear after 2.6?

Yes, the LLVM malloc instruction is no more.  There might still be an
IRBuilder::CreateMalloc, but that now emits a regular call to library
"malloc".

Now the case where function A calls function B, and function B needs
to return a pointer to a freshly-allocated object, is fairly common.
One way to attack this is to have each function create its own
"region" or "memory pool" and destroy it when it returns.  Then,
functions that need to return pointers to newly allocated objects get
a "memory pool" parameter added, and use that memory pool instance to
allocate the memory.  A global "memory pool" instance maps to the GC
heap.  Anyway, if function A observes the restrictions I mentioned
earlier with respect to that object, it passes its own memory pool
instance to function B.  If function A returns the pointer itself but
observes all the other restrictions, then it will declare a memory
pool parameter and pass whatever its caller passed in down to B.  This
scheme will allow any call depth to be handled without a GC heap
allocation, as long as no pointer to the object is ever stored in a
global or heap object or passed through a capturing function
parameter.

That leaves the case where a pointer to one object is stored in
another object.  If the containing object is allocated in a pool that
is not higher in the call stack than the referenced object, it is safe
to keep it out of the GC heap.  There might be cases where that
determination can be made at compile time, and it may or may not be
worth it to try to determine it at run time.

Since the allocator can either allocate from a memory pool or the GC
heap, the allocation needs to be done through a virtual function.  A
"partial specialization" pass exists that might help devirtualize
this, but it needs more development and testing.  You could always
codegen both specialized versions of each function yourself and let
dead code elimination clean it up for you, but you might not want the
compile/optimization overhead of that.

Is this project open-source?




More information about the llvm-dev mailing list