Was there already some reflection about how to lower the concept of nested functions (and the corresponding static links) into llvm? Dirk Muysers.
On Nov 21, 2004, at 4:11 AM, Dirk Muysers wrote:> Was there already some reflection about how to lower the concept of > nested > functions (and the corresponding static links) into llvm? > > Dirk Muysers.I have not seen a discussion of this and none of our current front-ends need it. A straightforward way to add support for this would be: (a) Lower nested procedures into ordinary top-level functions in LLVM, with name-mangling to enforce scopes for each name. (b) I assume you don't want to use a display (a global static link array) because of threads. For explicit static links: (i) Add an intrinsic function to get/set the access link out of the current stack frame. It should take the current stack frame as an argument (so you can walk the access link chain on the stack). Also, add an intrinsic to get a pointer to the current stack frame. I don't know a portable way to implement this in C, but the other back-ends should not have a problem. (ii) Add the access link as the first parameter to each nested function and use the intrinsic to set the link in the stack frame on entry. This argument is not traditionally needed but it makes things easier in LLVM, and may even make the common case (accessing a variable in the immediate parent function) faster. (iii) Before a call, walk the link chain to find the right access link (or the current stack frame) and pass it to the callee. As an optimization for shallow nested functions (e.g., 3 levels or less), it seems to me you could just avoid the stack walking entirely and add $k-1$ arguments to each function at level $k$, i.e., at most 2 arguments in all. This may even be an easy first implementation. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.cs.uiuc.edu/
On Nov 22, 2004, at 12:05 PM, Chris Lattner wrote:> On Sun, 21 Nov 2004, Dirk Muysers wrote: > >> Was there already some reflection about how to lower the concept of >> nested >> functions (and the corresponding static links) into llvm? > > This was discussed back in August, which discusses it, provides a > solution > and an example: > http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001828.html > http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001829.html > http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001834.html > http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001836.htmlThat's a rather simplistic example. I wouldn't recommend doing it this way -- I see at least 2 problems with it: (1) With recursion, the inlining being assumed here would not happen. This means the struct initialization won't be optimized away so nicely and it can get really expensive. Even without recursion, inlining would be impractical if you have many nested procedures and deep nesting. (2) If you don't rely on inlining, initializing the structs you have to pass around will get horrendously expensive with large numbers of local variables. (Note that without inlining, the structs will *not* be scalar-replaced because they have to passed as arguments.) There's a reason why code generators use static links. --Vikram http://www.cs.uiuc.edu/~vadve http://llvm.cs.uiuc.edu/
On Sun, 21 Nov 2004, Dirk Muysers wrote:> Was there already some reflection about how to lower the concept of nested > functions (and the corresponding static links) into llvm?This was discussed back in August, which discusses it, provides a solution and an example: http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001828.html http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001829.html http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001834.html http://mail.cs.uiuc.edu/pipermail/llvmdev/2004-August/001836.html I don't think that we need anything added to LLVM to support nested functions. -Chris -- http://llvm.org/ http://nondot.org/sabre/
> As an optimization for shallow nested functions (e.g., 3 levels or less), > it seems to me you could just avoid the stack walking entirely and add > $k-1$ arguments to each function at level $k$, i.e., at most 2 arguments > in all. This may even be an easy first implementation.I use this method with filtering unused in nested function args and local vars in my YAFL frontend (not finished :(( - at this moment generate LLVM bytecode but doesn't have all runtime suport code writed) Vladimir