Class FindTailCalls
- All Implemented Interfaces:
SourceLocator
,SourceLocator
,Locator
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 tailCaller
s.
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.)
-
Nested Class Summary
Nested classes/interfaces inherited from interface gnu.text.SourceLocator
SourceLocator.Simple
-
Field Summary
FieldsFields inherited from class gnu.expr.ExpVisitor
currentLambda, exitValue, messages
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic void
findTailCalls
(Expression exp, Compilation comp) void
postVisitDecls
(ScopeExp exp) protected Expression
visitApplyExp
(ApplyExp exp, Expression returnContinuation) protected Expression
visitBeginExp
(BeginExp exp, Expression returnContinuation) protected Expression
visitBlockExp
(BlockExp exp, Expression returnContinuation) protected Expression
visitCaseExp
(CaseExp exp, Expression returnContinuation) protected Expression
visitClassExp
(ClassExp exp, Expression returnContinuation) void
visitDefaultArgs
(LambdaExp exp, Expression d) protected Expression
visitExitExp
(ExitExp exp, Expression returnContinuation) protected Expression
visitExpression
(Expression exp, Expression returnContinuation) visitExps
(Expression[] exps) protected Expression
visitFluidLetExp
(FluidLetExp exp, Expression returnContinuation) protected Expression
visitIfExp
(IfExp exp, Expression returnContinuation) protected Expression
visitLambdaExp
(LambdaExp exp, Expression returnContinuation) protected Expression
visitLetExp
(LetExp exp, Expression returnContinuation) protected Expression
visitModuleExp
(ModuleExp exp, Expression returnContinuation) protected Expression
visitSetExp
(SetExp exp, Expression returnContinuation) protected Expression
visitSynchronizedExp
(SynchronizedExp exp, Expression returnContinuation) protected Expression
visitTryExp
(TryExp exp, Expression returnContinuation) Methods inherited from class gnu.expr.ExpExpVisitor
defaultValue, error, error, update
Methods inherited from class gnu.expr.ExpVisitor
error, 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, visitThisExp
-
Field Details
-
savedReturnContinuations
-
-
Constructor Details
-
FindTailCalls
public FindTailCalls()
-
-
Method Details
-
findTailCalls
-
visitExpression
- Overrides:
visitExpression
in classExpVisitor<Expression,
Expression>
-
visitExps
-
visitApplyExp
- Overrides:
visitApplyExp
in classExpVisitor<Expression,
Expression>
-
visitBlockExp
- Overrides:
visitBlockExp
in classExpVisitor<Expression,
Expression>
-
visitExitExp
- Overrides:
visitExitExp
in classExpVisitor<Expression,
Expression>
-
visitBeginExp
- Overrides:
visitBeginExp
in classExpVisitor<Expression,
Expression>
-
visitFluidLetExp
- Overrides:
visitFluidLetExp
in classExpVisitor<Expression,
Expression>
-
visitLetExp
- Overrides:
visitLetExp
in classExpVisitor<Expression,
Expression>
-
postVisitDecls
-
visitIfExp
- Overrides:
visitIfExp
in classExpVisitor<Expression,
Expression>
-
visitCaseExp
- Overrides:
visitCaseExp
in classExpVisitor<Expression,
Expression>
-
visitLambdaExp
- Overrides:
visitLambdaExp
in classExpVisitor<Expression,
Expression>
-
visitDefaultArgs
- Overrides:
visitDefaultArgs
in classExpVisitor<Expression,
Expression>
-
visitClassExp
- Overrides:
visitClassExp
in classExpVisitor<Expression,
Expression>
-
visitSetExp
- Overrides:
visitSetExp
in classExpVisitor<Expression,
Expression>
-
visitTryExp
- Overrides:
visitTryExp
in classExpVisitor<Expression,
Expression>
-
visitSynchronizedExp
- Overrides:
visitSynchronizedExp
in classExpVisitor<Expression,
Expression>
-
visitModuleExp
- Overrides:
visitModuleExp
in classExpVisitor<Expression,
Expression>
-