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? -- ┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ───── │ │ "Home is where, when you have to go there, they have to take you in." │ --- Cordelia Naismith -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 254 bytes Desc: OpenPGP digital signature URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100828/109e611e/attachment.sig>
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?
On 29/08/10 16:28, Kenneth Uildriks wrote: [...]> 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.[...]> 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.If I've understood you correctly, this still requires a run-time memory allocation from the appropriate memory pool --- so I still get the overhead of running a heap, although I do still get some optimisation due to being able to explicitly free the pool rather than relying on the garbage collector to do it. I think all I need is the simple case where I lower calls to malloc to alloca instructions if the result is only ever passed to nocapture functions and is not returned. The function-that-returns-a-pointer case (which my language does a lot) may be trivially manageable by relying on said functions being inlined; I've yet to get LLVM to inline anything yet, so I don't know how well this will work in practice. [...]> Is this project open-source?It will be once I get it into a fit state to release... -- ┌─── ｄｇ＠ｃｏｗｌａｒｋ．ｃｏｍ ───── http://www.cowlark.com ───── │ │ life←{ ↑1 ⍵∨.^3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂⍵ } │ --- Conway's Game Of Life, in one line of APL -------------- next part -------------- A non-text attachment was scrubbed... Name: signature.asc Type: application/pgp-signature Size: 262 bytes Desc: OpenPGP digital signature URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100831/4600b7d3/attachment.sig>