Next: Local TN assignment, Previous: Virtual Machine Representation Introduction, Up: Design of CMU Common Lisp [Contents]
The basic mechanism for closing over values is to pass the values as additional implicit arguments in the function call. This technique is only applicable when:
The first condition is always true of local function calls. Environment analysis can guarantee that the second condition holds by closing over any needed values in the calling environment.
If the function that closes over values may be called in an environment where the closed over values are not available, then we must store the values in a “closure” so that they are always accessible. Closures are called using the “full call” convention. When a closure is called, control is transferred to the “external entry point”, which fetches the values out of the closure and then does a local call to the real function, passing the closure values as implicit arguments.
In this scheme there is no such thing as a “heap closure variable” in code, since the closure values are moved into TNs by the external entry point. There is some potential for pessimization here, since we may end up moving the values from the closure into a stack memory location, but the advantages are also substantial. Simplicity is gained by always representing closure values the same way, and functions with closure references may still be called locally without allocating a closure. All the TN based VMR optimizations will apply to closure variables, since closure variables are represented in the same way as all other variables in VMR. Closure values will be allocated in registers where appropriate.
Closures are created at the point where the function is referenced, eliminating the need to be able to close over closures. This lazy creation of closures has the additional advantage that when a closure reference is conditionally not done, then the closure consing will never be done at all. The corresponding disadvantage is that a closure over the same values may be created multiple times if there are multiple references. Note however, that VMR loop and common subexpression optimizations can eliminate redundant closure consing. In any case, multiple closures over the same variables doesn’t seem to be that common.
#| Having the Tail-Info would also make return convention determination trivial. We could just look at the type, checking to see if it represents a fixed number of values. To determine if the standard return convention is necessary to preserve tail-recursion, we just iterate over the equivalent functions, looking for XEPs and uses in full calls. |#
The Global TN Assignment pass (GTN) can be considered a post-pass to environment analysis. This phase assigns the TNs used to hold local lexical variables and pass arguments and return values and determines the value-passing strategy used in local calls.
To assign return locations, we look at the function’s tail-set.
If the result continuation for an entry point is used as the continuation for a full call, then we may need to constrain the continuation’s values passing convention to the standard one. This is not necessary when the call is known not to be part of a tail-recursive loop (due to being a known function).
Once we have figured out where we must use the standard value passing strategy, we can use a more flexible strategy to determine the return locations for local functions. We determine the possible numbers of return values from each function by examining the uses of all the result continuations in the equivalence class of the result continuation.
If the tail-set type is for a fixed number of values, then we return that fixed number of values from all the functions whose result continuations are equated. If the number of values is not fixed, then we must use the unknown-values convention, although we are not forced to use the standard locations. We assign the result TNs at this time.
We also use the tail-sets to see what convention we want to use. What we do is use the full convention for any function that has a XEP its tail-set, even if we aren’t required to do so by a tail-recursive full call, as long as there are no non-tail-recursive local calls in the set. This prevents us from gratuitously using a non-standard convention when there is no reason to.
Next: Local TN assignment, Previous: Virtual Machine Representation Introduction, Up: Design of CMU Common Lisp [Contents]