This is the mail archive of the
kawa@sourceware.org
mailing list for the Kawa project.
Re: Tail sets
- From: Helmut Eller <eller dot helmut at gmail dot com>
- To: kawa at sources dot redhat dot com
- Date: Thu, 14 May 2009 17:11:43 +0200
- Subject: Re: Tail sets
- References: <87zlfnjhwt.fsf@lifebook.lan> <49BDDA63.6020009@bothner.com>
* Per Bothner [2009-03-16 05:49+0100] writes:
> The goal of the commented-out algorithm in FindTailsCalls.walkLambdaExp
> is to find such "inline sets". Once we have those inline sets code
> generation should be easy,
>
> So no, I don't think it would be hard to optimize this.
> In fact I think it would be a very worthwhile project for someone
> who wants to learn more of Kawa internals ...
I played a bit with this inline set algorithm, but it turned out to be
more complicated than I had hoped. The attached patch seems to pass the
testsuite but there are only a handful of non-trivial inline sets in the
Kawa source base.
One problem was that code generation for self-tailcalls doesn't quite
work for the more general case. For self-tailcalls the situation looks
like:
<popparms>
start:
<body>
...
<pushargs>
<popparams>
jmp start
i.e. argument values are moved into the right locations before
jumping. This doesn't work so nicely for tailcalls which are
outside of the scope of the parameter variables. I did this instead:
start:
<popparms>
<body>
...
<pushargs>
jmp start
i.e. the caller leaves the values on the stack and the callee shuffles
them to the right locations. I guess a better approach would have been
to emit two labels and use one for self-tailcalls and the other for
calls from the outside.
I'm sure that there are problems with this patch but I'm sending it
anyway because I don't understand enough of Kawa to enhance it much
further and it might save you, or somebody else interested in this
stuff, some work.
With the patch, code like this runs without stack-overflow:
(define (foo x)
(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? x)))
(foo 10000000)
Helmut.
Index: gnu/expr/ApplyExp.java
===================================================================
--- gnu/expr/ApplyExp.java (revision 6250)
+++ gnu/expr/ApplyExp.java (working copy)
@@ -18,6 +18,7 @@
public static final int TAILCALL = NEXT_AVAIL_FLAG;
public static final int INLINE_IF_CONSTANT = NEXT_AVAIL_FLAG << 1;
+ public static final int LOCAL_TAILCALL = NEXT_AVAIL_FLAG << 2;
/** Containing LambdaExp. */
LambdaExp context;
@@ -35,6 +36,9 @@
public final boolean isTailCall() { return getFlag(TAILCALL); }
public final void setTailCall(boolean tailCall)
{ setFlag(tailCall, TAILCALL); }
+ public final boolean isLocalTailCall() { return getFlag(LOCAL_TAILCALL); }
+ public final void setLocalTailCall(boolean localTailCall)
+ { setFlag(localTailCall, LOCAL_TAILCALL); }
/** If getFunction() is constant, return its value; otherwise null. */
public final Object getFunctionValue()
@@ -277,7 +281,9 @@
// Check for tail-recursion.
boolean tail_recurse
= exp.isTailCall()
- && func_lambda != null && func_lambda == comp.curLambda;
+ && func_lambda != null
+ && (func_lambda == comp.curLambda
+ || (exp.isLocalTailCall() && func_lambda.localCallScope != null));
if (func_lambda != null && func_lambda.getInlineOnly() && !tail_recurse
&& func_lambda.min_args == args_length)
@@ -287,8 +293,19 @@
comp.curLambda = func_lambda;
func_lambda.allocChildClasses(comp);
func_lambda.allocParameters(comp);
- popParams (code, func_lambda, null, false);
- func_lambda.enterFunction(comp);
+ if (!exp.isLocalTailCall())
+ {
+ popParams (code, func_lambda, null, false);
+ func_lambda.enterFunction(comp);
+ }
+ else
+ {
+ System.out.println("inlining: " + func_lambda
+ + " [in " + exp.context + "]");
+ func_lambda.enterFunction(comp);
+ func_lambda.localCallScope = func_lambda.getVarScope();
+ popParams (code, func_lambda, null, false);
+ }
func_lambda.body.compileWithPosition(comp, target);
func_lambda.compileEnd(comp);
func_lambda.popScope(code);
@@ -351,8 +368,9 @@
}
else if (tail_recurse)
{
- incValues = new int[exp.args.length];
- pushArgs(func_lambda, exp.args, incValues, comp);
+ if (!exp.isLocalTailCall())
+ incValues = new int[exp.args.length];
+ pushArgs(func_lambda, exp.args, incValues, comp);
method = null;
}
else
@@ -372,9 +390,17 @@
}
if (tail_recurse)
{
- popParams(code, func_lambda, incValues, toArray);
- code.emitTailCall(false, func_lambda.getVarScope());
- return;
+ if (func_lambda.localCallScope == null)
+ {
+ popParams(code, func_lambda, incValues, toArray);
+ code.emitTailCall(false, func_lambda.getVarScope());
+ return;
+ }
+ else
+ {
+ code.emitTailCall(false, func_lambda.localCallScope);
+ return;
+ }
}
code.emitInvokeVirtual(method);
target.compileFromStack(comp, Type.pointer_type);
Index: gnu/expr/ChangeLog
===================================================================
--- gnu/expr/ChangeLog (revision 6250)
+++ gnu/expr/ChangeLog (working copy)
@@ -1,3 +1,32 @@
+2009-05-14 Helmut Eller <eller.helmut@gmail.com>
+
+ Inline mutually tail-recursive functions.
+
+ * FindTailCalls.java (walkLambdaExp): Compute inlineSet, a set of
+ tail-called child lambdas that are candidates for inlining. Set
+ the INLINE_ONLY and LOCAL_TAILCALL flags on such lambdas. The
+ exp.home and exp.callSites fields of the lambda are initialized as
+ side effect.
+ (isInlinableChild, isInlinable, mergeChild, hasNonTailCaller): New
+ helper functions.
+ * LambdaExp.java (callSites, home, localCallScope): New variables
+ used be for inlining.
+ (setInlineOnly): New helper with home lambda as parameter.
+ (getInlineHome): Renamed from getCaller. Some of the inlined
+ functions have multiple callers, so the old name didn't seem
+ appropriate.
+ * ApplyExp.java (LOCAL_TAILCALL): New flag to mark jumps to
+ inlined lambdas.
+ (isLocalTailCall, setLocalTailCall): Getter&setter.
+ (compile): Generate different code for LOCAL_TAILCALLs.
+ LOCAL_TAILCALLs are handled almost like self-tailcalls but
+ arguments are always left on the stack, as opposed to move them
+ directly to the home locations. That was necessary because the
+ home locations are in general not in scope of the apply
+ expression.
+ * FindCapturedVars.java (capture): Use Lambda.getInlineHome
+ instead of relying on the Lambda.returnContinuation field.
+
2009-04-21 Per Bothner <per@bothner.com>
* Compilation.java (makeRunnable): New method.
Index: gnu/expr/FindTailCalls.java
===================================================================
--- gnu/expr/FindTailCalls.java (revision 6250)
+++ gnu/expr/FindTailCalls.java (working copy)
@@ -75,6 +75,10 @@
lexp.returnContinuation = exp;
else
lexp.returnContinuation = LambdaExp.unknownContinuation;
+ {
+ if (!lexp.callSites.contains(exp))
+ lexp.callSites = new gnu.lists.Pair(exp, lexp.callSites);
+ }
}
if (isAppendValues && exp.args.length > 0)
{
@@ -257,12 +261,9 @@
}
}
}
-
- for (LambdaExp child = exp.firstChild; child != null;
- child = child.nextSibling)
+
+ if (true)
{
- if ((child.flags & (LambdaExp.CANNOT_INLINE|LambdaExp.INLINE_ONLY))!=0)
- continue;
// We can inline child if it is a member of a set of functions
// which can all be inlined in the same method, and for which
// all callers are known and members of the same set,
@@ -289,13 +290,86 @@
add caller.returnContinuation.context to inlineSet;
}
*/
- }
+
+ java.util.Set<LambdaExp> inlineSet = new java.util.LinkedHashSet();
+ for (LambdaExp fun = exp.firstChild; fun != null; fun = fun.nextSibling)
+ if (isInlinableChild(fun, exp))
+ mergeChild(fun, exp, inlineSet);
+
+ if (!inlineSet.isEmpty())
+ System.out.println("Inlineset: " + inlineSet + " in " + exp);
+
+ for (LambdaExp child : inlineSet)
+ {
+ if (!child.getInlineOnly()) // don't change self-tail-recursive code
+ {
+ child.setInlineOnly(true, exp);
+ for (ApplyExp app : child.callSites)
+ app.setLocalTailCall(true);
+ }
+ }
+ }
+
}
// Map LambdaExp to ApplyExp[], which is the set of non-self tails
// calls that call the key.
// Hashtable applications = new Hashtable();
+ // Return true if lambda can be merged into home.
+ private static boolean isInlinableChild (LambdaExp lambda, LambdaExp home)
+ {
+ java.util.Set seen = new java.util.HashSet();
+ seen.add(home);
+ return isInlinable(lambda, seen);
+ }
+
+ // Return true if lambda can be inlined to a set of lambdas
+ private static boolean isInlinable (LambdaExp lambda, java.util.Set blob)
+ {
+ if ((lambda.flags & LambdaExp.CANNOT_INLINE) != 0)
+ return false;
+ else if (hasNonTailCaller(lambda))
+ return false;
+ else
+ {
+ blob.add(lambda);
+ for (ApplyExp app : lambda.callSites)
+ {
+ LambdaExp context = app.context;
+ if (blob.contains(context))
+ continue;
+ else if (!isInlinable(context, blob))
+ return false;
+ }
+ return true;
+ }
+ }
+
+ // Adjoin any lambdas to inlineSet needed when inlineing lambda into home
+ private static void mergeChild (LambdaExp lambda, LambdaExp home,
+ java.util.Set inlineSet)
+ {
+ if (inlineSet.contains(lambda)
+ || lambda == home)
+ return;
+ else
+ {
+ inlineSet.add(lambda);
+ for (ApplyExp app : lambda.callSites)
+ mergeChild(app.context, home, inlineSet);
+ }
+ }
+
+ // Return true if lambda is called in a non-tail position.
+ private static boolean hasNonTailCaller (LambdaExp lambda)
+ {
+ for (ApplyExp app : lambda.callSites)
+ if (!app.isTailCall())
+ return true;
+ return false;
+ }
+
protected Expression walkClassExp (ClassExp exp)
{
boolean save = inTailContext;
Index: gnu/expr/LambdaExp.java
===================================================================
--- gnu/expr/LambdaExp.java (revision 6250)
+++ gnu/expr/LambdaExp.java (working copy)
@@ -83,6 +83,16 @@
call site. */
public ApplyExp returnContinuation;
+ /** Set of (known) ApplyExps which call this lambda. */
+ public java.util.List<ApplyExp> callSites = LList.Empty;
+ /** If this lambda gets inlined this is the surrounding lambda.
+ Otherwise this is null. */
+ public LambdaExp home;
+ /** Used during code generation. If null, no code was emitted
+ yet and we generate inline code. If non-null, we emit a jump
+ to this label. */
+ Scope localCallScope = null;
+
/** Expressions that name classes that may be thrown. */
ReferenceExp[] throwsSpecification;
@@ -137,6 +147,11 @@
public final void setInlineOnly(boolean inlineOnly)
{ setFlag(inlineOnly, INLINE_ONLY); }
+ public final void setInlineOnly(boolean inlineOnly, LambdaExp home)
+ { setFlag(inlineOnly, INLINE_ONLY);
+ this.home = home;
+ }
+
public final boolean getNeedsClosureEnv ()
{ return (flags & (NEEDS_STATIC_LINK|IMPORTS_LEX_VARS)) != 0; }
@@ -378,7 +393,7 @@
* except in the case that outer.getInlineOnly(). */
boolean inlinedIn (LambdaExp outer)
{
- for (LambdaExp exp = this; exp.getInlineOnly(); exp = exp.getCaller())
+ for (LambdaExp exp = this; exp.getInlineOnly(); exp = exp.getInlineHome())
{
if (exp == outer)
return true;
@@ -387,9 +402,12 @@
}
/** For an INLINE_ONLY function, return the function it gets inlined in. */
- public LambdaExp getCaller ()
+ public LambdaExp getInlineHome ()
{
- return returnContinuation.context;
+ assert getInlineOnly();
+ return (returnContinuation != unknownContinuation
+ ? returnContinuation.context
+ : home);
}
Variable thisVariable;
@@ -475,7 +493,7 @@
{
LambdaExp curLambda = comp.curLambda;
while (curLambda != this && curLambda.getInlineOnly())
- curLambda = curLambda.getCaller();
+ curLambda = curLambda.getInlineHome();
gnu.bytecode.CodeAttr code = comp.getCode();
if (curLambda.heapFrame != null && this == curLambda)
Index: gnu/expr/FindCapturedVars.java
===================================================================
--- gnu/expr/FindCapturedVars.java (revision 6250)
+++ gnu/expr/FindCapturedVars.java (working copy)
@@ -256,7 +256,7 @@
curLambda.setCanCall(false);
return;
}
- curLambda = curReturn.context;
+ curLambda = curLambda.getInlineHome();
chain = chain.nextSibling;
}
if (comp.usingCPStyle())