public class FindTailCalls extends ExpExpVisitor<Expression>
The main goal of this pass is to figure of which functions can and
should be inlined. We inline a function where possible to avoid
closure allocation and related overheads, and also (more importantly)
to enable tail-call-optiomization: A tail-call can be implemented cheaply
and correctly using a goto bytecode instruction - but only for
functions inlined in the same JVM method.
We currently restrict inlining to cases when we can do so without code duplication: When the function is only called once, not counting tail-calls. Because passing a "return link" is difficult, we require that all calls to the function have the same "return continuation".
The extra visitor parameter is the returnContinuation - the
expression we "return to" - i.e. when done evaluating an expression, we're
also done with the returnContinuation. Normally it is is same
Expression as we are visiting, but (for example) when visiting the
last expression of a BeginExp the returnContinuation
is the same as that of the containing BeginExp. We're in a
tail-context (in the sense of the Scheme reports) iff the current
returnContinuation is the body of the current
LambdaExp.
For each non-inlined function f we define inlineSet(f)
as the set of functions g such that g.inlinedIn(f).
There are various requirements for a function g to be inlined;
for example we require that it have a fixed number of arguments.
Because of the no-duplication policy, all calls to g have
to be known, and all calls have to be from other inlined functions:
If h calls g, then h==f || h.inlinedIn(f).
In addition all calls must have the same returnContinuation.
This analysis is done in two parts: First the main expression-walker,
and at the end (in visitModuleExp) we check each procedure
using the data from the main pass.
When this vistor is done, it has set the returnContinuation,
tailCallers, and inlineHome fields of a LambdaExp.
If function f tail-calls g, then f is added
to the set of g's tailCallers.
If there is a non-tail-call to g then we try to set g's
returnContinuation to the current (context)
returnContinuation, if the former hasn't been set yet;
otherwise we set it to the special unknownContinuation value.
We also construct tailCallers as the list of functions h
that make a tail-call to g.
At the end of this pass, if a function's returnContinuation is
is non-null and not unknown then it has a unique continuation,
and the function can potentially be inlined at the location of the
continuation. However, that depends on if any tail-calls also have same
return-continuation; that analysis happens later in checkInlineable.
(In addition a validate method (executed during the earlier
InlinedCalls pass may pre-initialized the returnContinuation
inlineHome fields, but only for a LambdaExp that will be
inlined during code generation in a custom compile method.)
SourceLocator.Simple| Modifier and Type | Field and Description |
|---|---|
java.util.HashMap<Expression,Expression> |
savedReturnContinuations |
currentLambda, exitValue, messages| Constructor and Description |
|---|
FindTailCalls() |
defaultValue, error, error, updateerror, getColumnNumber, getCompilation, getCurrentLambda, getEndColumn, getEndLine, getExitValue, getFileName, getLanguage, getLineNumber, getMessages, getPublicId, getStartColumn, getStartLine, getSystemId, isStableSourceLocation, noteError, setColumn, setContext, setFile, setLine, setLine, visit, visit, visitAndUpdate, visitDeclarationType, visitDeclarationTypes, visitExps, visitExps, visitLangExp, visitObjectExp, visitQuoteExp, visitReferenceExp, visitScopeExp, visitThisExppublic java.util.HashMap<Expression,Expression> savedReturnContinuations
public static void findTailCalls(Expression exp, Compilation comp)
protected Expression visitExpression(Expression exp, Expression returnContinuation)
visitExpression in class ExpVisitor<Expression,Expression>public Expression[] visitExps(Expression[] exps)
protected Expression visitApplyExp(ApplyExp exp, Expression returnContinuation)
visitApplyExp in class ExpVisitor<Expression,Expression>protected Expression visitBlockExp(BlockExp exp, Expression returnContinuation)
visitBlockExp in class ExpVisitor<Expression,Expression>protected Expression visitExitExp(ExitExp exp, Expression returnContinuation)
visitExitExp in class ExpVisitor<Expression,Expression>protected Expression visitBeginExp(BeginExp exp, Expression returnContinuation)
visitBeginExp in class ExpVisitor<Expression,Expression>protected Expression visitFluidLetExp(FluidLetExp exp, Expression returnContinuation)
visitFluidLetExp in class ExpVisitor<Expression,Expression>protected Expression visitLetExp(LetExp exp, Expression returnContinuation)
visitLetExp in class ExpVisitor<Expression,Expression>public void postVisitDecls(ScopeExp exp)
protected Expression visitIfExp(IfExp exp, Expression returnContinuation)
visitIfExp in class ExpVisitor<Expression,Expression>protected Expression visitCaseExp(CaseExp exp, Expression returnContinuation)
visitCaseExp in class ExpVisitor<Expression,Expression>protected Expression visitLambdaExp(LambdaExp exp, Expression returnContinuation)
visitLambdaExp in class ExpVisitor<Expression,Expression>public void visitDefaultArgs(LambdaExp exp, Expression d)
visitDefaultArgs in class ExpVisitor<Expression,Expression>protected Expression visitClassExp(ClassExp exp, Expression returnContinuation)
visitClassExp in class ExpVisitor<Expression,Expression>protected Expression visitSetExp(SetExp exp, Expression returnContinuation)
visitSetExp in class ExpVisitor<Expression,Expression>protected Expression visitTryExp(TryExp exp, Expression returnContinuation)
visitTryExp in class ExpVisitor<Expression,Expression>protected Expression visitSynchronizedExp(SynchronizedExp exp, Expression returnContinuation)
visitSynchronizedExp in class ExpVisitor<Expression,Expression>protected Expression visitModuleExp(ModuleExp exp, Expression returnContinuation)
visitModuleExp in class ExpVisitor<Expression,Expression>