[LLVMdev] Nested functions

[Dirk Muysers]

On Nov 22, 2004, at 10:00 AM, Vikram S. Adve wrote:
> 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

Very true. Manipulation of thread-local storage is the reason why displays,
after the early Algol implementations, have never been in favour with
compiler writers. The first generation of Modula-3 compilers (with C
backends) generally opted for inlining nested functions. Nowadays the use of
static links is the only game in town.

llvm makes this difficult as the static link technique obliges to reify
stack frames as structures in order for individual entries to be accessible
through the "getelementptr" instruction. This becomes very unwieldy in the
case of a large nesting tree (nested function may also call each other at
intermediate levels). While llvm's ban on pointer arithmetic _is_ a good
thing (TM), it has also its drawbacks.

We should not single out the case of shallow nesting, which can be easily
optimised away through lambda lifting etc. I know about whole language
front-end parsers where the grammar is reflected through a huge tree of
nested functions. These are the only occasions, beside container mapping
functions, where the use of nested function becomes really interesting and a
thoroughly clean implementation becomes a must.

The fact remains that Pascal and Modula features such as lexical nesting are
generally shunned upon by the C subculture and thus receive a poor deal in
the world of open software where there is no life beyond GNU, C and Unix.

/dm