Class FindTailCalls
- java.lang.Object
-
- gnu.expr.ExpVisitor<Expression,D>
-
- gnu.expr.ExpExpVisitor<Expression>
-
- gnu.expr.FindTailCalls
-
- All Implemented Interfaces:
SourceLocator
,SourceLocator
,Locator
public class FindTailCalls extends ExpExpVisitor<Expression>
A visitor that checks for tails-calls; also notes read/write/call accesses.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 thereturnContinuation
. Normally it is is sameExpression
as we are visiting, but (for example) when visiting the last expression of aBeginExp
thereturnContinuation
is the same as that of the containingBeginExp
. We're in a tail-context (in the sense of the Scheme reports) iff the currentreturnContinuation
is thebody
of the currentLambdaExp
.For each non-inlined function
f
we defineinlineSet(f)
as the set of functionsg
such thatg.inlinedIn(f)
. There are various requirements for a functiong
to be inlined; for example we require that it have a fixed number of arguments. Because of the no-duplication policy, all calls tog
have to be known, and all calls have to be from other inlined functions: Ifh
callsg
, thenh==f || h.inlinedIn(f)
. In addition all calls must have the samereturnContinuation
.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
, andinlineHome
fields of aLambdaExp
. If functionf
tail-callsg
, thenf
is added to the set ofg
'stailCaller
s.If there is a non-tail-call to
g
then we try to setg
'sreturnContinuation
to the current (context)returnContinuation
, if the former hasn't been set yet; otherwise we set it to the specialunknownContinuation
value. We also constructtailCallers
as the list of functionsh
that make a tail-call tog
. At the end of this pass, if a function'sreturnContinuation
is is non-null and notunknown
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 incheckInlineable
.(In addition a
validate
method (executed during the earlierInlinedCalls
pass may pre-initialized thereturnContinuation
inlineHome
fields, but only for aLambdaExp
that will be inlined during code generation in a customcompile
method.)
-
-
Nested Class Summary
-
Nested classes/interfaces inherited from interface gnu.text.SourceLocator
SourceLocator.Simple
-
-
Field Summary
Fields Modifier and Type Field Description HashMap<Expression,Expression>
savedReturnContinuations
-
Fields inherited from class gnu.expr.ExpVisitor
currentLambda, exitValue, messages
-
-
Constructor Summary
Constructors Constructor Description FindTailCalls()
-
Method Summary
-
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 Detail
-
savedReturnContinuations
public HashMap<Expression,Expression> savedReturnContinuations
-
-
Method Detail
-
findTailCalls
public static void findTailCalls(Expression exp, Compilation comp)
-
visitExpression
protected Expression visitExpression(Expression exp, Expression returnContinuation)
- Overrides:
visitExpression
in classExpVisitor<Expression,Expression>
-
visitExps
public Expression[] visitExps(Expression[] exps)
-
visitApplyExp
protected Expression visitApplyExp(ApplyExp exp, Expression returnContinuation)
- Overrides:
visitApplyExp
in classExpVisitor<Expression,Expression>
-
visitBlockExp
protected Expression visitBlockExp(BlockExp exp, Expression returnContinuation)
- Overrides:
visitBlockExp
in classExpVisitor<Expression,Expression>
-
visitExitExp
protected Expression visitExitExp(ExitExp exp, Expression returnContinuation)
- Overrides:
visitExitExp
in classExpVisitor<Expression,Expression>
-
visitBeginExp
protected Expression visitBeginExp(BeginExp exp, Expression returnContinuation)
- Overrides:
visitBeginExp
in classExpVisitor<Expression,Expression>
-
visitFluidLetExp
protected Expression visitFluidLetExp(FluidLetExp exp, Expression returnContinuation)
- Overrides:
visitFluidLetExp
in classExpVisitor<Expression,Expression>
-
visitLetExp
protected Expression visitLetExp(LetExp exp, Expression returnContinuation)
- Overrides:
visitLetExp
in classExpVisitor<Expression,Expression>
-
postVisitDecls
public void postVisitDecls(ScopeExp exp)
-
visitIfExp
protected Expression visitIfExp(IfExp exp, Expression returnContinuation)
- Overrides:
visitIfExp
in classExpVisitor<Expression,Expression>
-
visitCaseExp
protected Expression visitCaseExp(CaseExp exp, Expression returnContinuation)
- Overrides:
visitCaseExp
in classExpVisitor<Expression,Expression>
-
visitLambdaExp
protected Expression visitLambdaExp(LambdaExp exp, Expression returnContinuation)
- Overrides:
visitLambdaExp
in classExpVisitor<Expression,Expression>
-
visitDefaultArgs
public void visitDefaultArgs(LambdaExp exp, Expression d)
- Overrides:
visitDefaultArgs
in classExpVisitor<Expression,Expression>
-
visitClassExp
protected Expression visitClassExp(ClassExp exp, Expression returnContinuation)
- Overrides:
visitClassExp
in classExpVisitor<Expression,Expression>
-
visitSetExp
protected Expression visitSetExp(SetExp exp, Expression returnContinuation)
- Overrides:
visitSetExp
in classExpVisitor<Expression,Expression>
-
visitTryExp
protected Expression visitTryExp(TryExp exp, Expression returnContinuation)
- Overrides:
visitTryExp
in classExpVisitor<Expression,Expression>
-
visitSynchronizedExp
protected Expression visitSynchronizedExp(SynchronizedExp exp, Expression returnContinuation)
- Overrides:
visitSynchronizedExp
in classExpVisitor<Expression,Expression>
-
visitModuleExp
protected Expression visitModuleExp(ModuleExp exp, Expression returnContinuation)
- Overrides:
visitModuleExp
in classExpVisitor<Expression,Expression>
-
-