I'm working on an LLVM-based compiler for a very closure-centric language. It's becoming apparent that it's going to suffer heavily from garbage collector churn, as all the useful programming idioms the language makes possible are going to involve memory allocations, either to create objects or to allocate storage for upvalues. However, it's possible to optimise away a lot of heap allocations, and replace them with allocas instead, *if* we know that the lifetime of the object is going to be shorter than the lifetime of the stack frame --- in other words, the object will be used strictly inside the function and nowhere else. This applies to both upvalues and objects. Does LLVM have any mechanism for doing the kind of dataflow analysis required to track object lifetime like this? -- ┌─── dg@cowlark.com ───── 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/8bd77191/attachment.sig>
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. There may be other possibilities for proving an object dead, but this should definitely be safe. On Fri, Aug 27, 2010 at 7:16 PM, David Given <dg at cowlark.com> wrote:> I'm working on an LLVM-based compiler for a very closure-centric > language. It's becoming apparent that it's going to suffer heavily from > garbage collector churn, as all the useful programming idioms the > language makes possible are going to involve memory allocations, either > to create objects or to allocate storage for upvalues. > > However, it's possible to optimise away a lot of heap allocations, and > replace them with allocas instead, *if* we know that the lifetime of the > object is going to be shorter than the lifetime of the stack frame --- > in other words, the object will be used strictly inside the function and > nowhere else. This applies to both upvalues and objects. > > Does LLVM have any mechanism for doing the kind of dataflow analysis > required to track object lifetime like this? > > -- > ┌─── dg@cowlark.com ───── http://www.cowlark.com ───── > │ > │ "Home is where, when you have to go there, they have to take you in." > │ --- Cordelia Naismith > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
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? -- ┌─── dg@cowlark.com ───── 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>