TailCall optimization for jvm.

1 files changed, 362 insertions, 0 deletions

diff --git a/sources/scalac/transformer/TailCall.java b/sources/scalac/transformer/TailCall.java
new file mode 100644
index 0000000000..e4f5bb4fb5
--- /dev/null
+++ b/sources/scalac/transformer/TailCall.java
@@ -0,0 +1,362 @@
+/*     ____ ____  ____ ____  ______                                     *\
+**    / __// __ \/ __// __ \/ ____/    SOcos COmpiles Scala             **
+**  __\_ \/ /_/ / /__/ /_/ /\_ \       (c) 2002, LAMP/EPFL              **
+** /_____/\____/\___/\____/____/                                        **
+\*                                                                      */
+
+// $Id$
+
+package scalac.transformer;
+
+import java.io.*;
+import java.util.HashMap;
+import scalac.*;
+import scalac.util.*;
+import scalac.ast.*;
+import scalac.symtab.*;
+import Tree.*;
+
+/** A Tail Call transformer
+ *
+ *  @author     Erik Stenman
+ *  @version    1.0
+ *
+ *  What it does:
+ *  Finds calls in tail-positions and
+ *  replaces them with direct calls to LabelDefs.
+ *  A call is in a tail-position if it is the last
+ *  instruciton to be executed in the body of a function.
+ *  This is done by recursing over the tree keeping track
+ *  of whether we are in a tail position or not.
+ *
+ *  At the moment this transformation is tageted towards the
+ *  JVM. Since the JVM only supports jumps to known locations
+ *  within a function some special care has to be taken.
+ *  First we have to check that the call is self-recursive.
+ *  Then we check that the function (or the class) is final.
+ *  (Otherwise it could be a call to an overridden function in
+ *  a subclass.)
+ *  If all conditions are met we introduce a labelDef at the
+ *  beginning of the function, and redirects the call (apply)
+ *  to this label.
+ *
+ *  While traversing the tree we use a stack of States to keep track of
+ *  information about the current node in the tree.
+ *	inTailPosition  -- True iff the curent node is in a tail position
+ *	currentClass    -- The symbol of the enclosing class of the node
+ *                         if there is one.
+ *	currentFunction -- The symbol of the enclosing function of the node
+ *                         if there is one.
+ *	newLabel        -- When in a function this is the symbol of the
+ *                         LabelDef to recurse back to if a tail-call occures.
+ *      needLabelDef    -- Set to true when a tail call is encounterd to
+ *                         indicate that the LabelDef needs to be inserted.
+ */
+
+public class TailCall extends Transformer {
+    final Global global;
+    final Definitions definitions;
+    private State state = new State();
+
+    public TailCall(Global global, PhaseDescriptor descr) {
+        super(global);
+	this.global = global;
+	this.definitions = global.definitions;
+    }
+
+    /* Keep track of information about the current node. */
+    private class State {
+	State next = null;
+	boolean inTailPosition = false;
+	Symbol currentClass = null;
+	Symbol currentFunction = null;
+	Symbol newLabel = null;
+	boolean needLabelDef = false;
+    }
+
+    /* Push a new empty state on the state stack */
+    private void push_new() {
+	State old = state;
+	state = new State();
+	state.next=old;
+    }
+
+    /* Push a copy of the current state on the stack,
+       with aditional information about a new LabelDef. */
+    private void push_label(Symbol label) {
+	State old = state;
+	state = new State();
+	state.next=old;
+	state.inTailPosition = old.inTailPosition;
+	state.currentClass = old.currentClass;
+	state.currentFunction = old.currentFunction;
+	state.newLabel = label;
+	state.needLabelDef = false;
+    }
+
+    /* Pop a state from the state stack. */
+    private void pop() {
+	state = state.next;
+    }
+
+
+    public Tree transform(Tree tree) {
+        switch (tree) {
+
+	case DefDef(int mods, Name name, AbsTypeDef[] tparams, ValDef[][] vparams, Tree tpe, Tree rhs): {
+	    AbsTypeDef[] newTparams  = tail_transform(tparams,false);
+	    ValDef[][] newVparams = tail_transform(vparams,false);
+	    Tree newTpe   = tail_transform(tpe,false);
+
+	    /* Create a new symbol for the LabelDef */
+	    Symbol newLabel = new TermSymbol(tree.pos, name, tree.symbol(), Modifiers.LABEL);
+	    newLabel.setInfo(tree.symbol().type());
+
+	    /* Push information about the label on the state stack. */
+	    push_label(newLabel);
+	    state.inTailPosition = true;
+	    state.currentFunction = tree.symbol();
+
+	    /* Traverse the body of the function */
+	    Tree newRhs   = transform(rhs);
+
+	    /* Was a tail-call inserted? */
+	    if (state.needLabelDef) {
+		pop(); // Pop the label-state from the stack.
+		// The LabelDef needs identifiers as parameters.
+		Ident [] args = to_ident(newVparams[0]);
+		// Create a new LabelDef with the new body of the function as the rhs
+		Tree labelDef = new ExtLabelDef(newLabel,args,newRhs).setType(newRhs.type());
+		// Create a new function node with the LabelDef as the rhs.
+		return copy.DefDef(tree,tree.symbol(), newTparams,
+				   newVparams, newTpe, labelDef);
+	    } else { // No recursive tail-vall inserted.
+		pop(); // Pop the label-state from the stack.
+		// Don't insert the LabelDef.
+		return copy.DefDef(tree,tree.symbol(), newTparams,
+				   newVparams, newTpe, newRhs);
+	    }
+	}
+
+	case Apply(Tree fun, Tree[] args): {
+	    if (state.inTailPosition) {  // This is a tail-call
+		switch (fun) {
+		case Select(Tree qual, Name name):
+		    if (state.currentFunction == fun.symbol()) { // Is is self-recursive?
+			// Make sure that function is from the same class as we are in.
+			if (qual.type.isSameAs(state.currentClass.thisType().widen())) {
+			    // We can only rewrite final functions in a safe way.
+			    // (Local lifted functions should be safe but they should
+			    //  have the final flag set.)
+			    Modifiers.Helper H = new Modifiers.Helper();
+			    if(H.isFinal(state.currentFunction.flags)) { // Is the function final?
+				Tree[] newArgs = tail_transform(args,false);
+				// Redirect the call to the LabelDef.
+				Tree newTarget = new ExtIdent(state.newLabel).setType(fun.type());
+				// Indicate that we have inserted a tail call.
+				state.needLabelDef = true;
+				return copy.Apply(tree,newTarget,newArgs);
+			    }
+			}
+		    }
+		    break;
+		default:
+		    break;
+		}
+	    }
+	    // Call not in tail-pos: recurse over the arguments.
+	    Tree[] newArgs = tail_transform(args,false);
+	    Tree newFun = tail_transform(fun,false);
+	    //  global.debugPrinter.print("OldApply fun "+newFun.symbol().name).println().end();
+	    return copy.Apply(tree, newFun, newArgs);
+
+	}
+
+
+	case ClassDef(int mods, Name name, AbsTypeDef[] tparams,
+		      ValDef[][] vparams, Tree tpe, Template impl): {
+	    return copy.ClassDef(tree, tree.symbol(),tparams,vparams,tpe,
+				 transform_class(impl,tree.symbol()));
+	}
+
+
+        case AbsTypeDef(int mods, Name name, Tree rhs, Tree lobound):
+	    return copy.AbsTypeDef(tree, tree.symbol(),
+				   tail_transform(rhs,false),
+				   tail_transform(lobound,false));
+
+       case CaseDef(Tree pat, Tree guard, Tree body):
+            return copy.CaseDef(tree,
+				tail_transform(pat,false),
+				tail_transform(guard,false),
+				transform(body));
+
+
+       case Template(Tree[] parents, Tree[] body):
+	   return copy.Template(tree, tree.symbol(),
+				tail_transform(parents,false),
+				transform(body));
+
+	case Block(Tree[] stats): {
+	    int last = stats.length-1;
+	    // All statements except the last will not be tail-calls
+	    for (int i = 0; i < last; i++) {
+		Tree t = tail_transform(stats[i],false);
+		// We are a bit paranoid about creating garbage...
+		if (t != stats[i]) { // ... so we only copy the tree if it changes.
+		    Tree[] res = new Tree[stats.length];
+		    // copy all the preceding statements to the new array.
+		    System.arraycopy(stats, 0, res, 0, i);
+		    res[i++] = t;
+		    // Put all the following statements in the new array.
+		    for (; i < last; i++)
+			res[i] = tail_transform(stats[i],false);
+		    // The last statement might be in a tail position.
+		    res[last] = transform(stats[last]);
+		    return copy.Block(tree,res);
+		}
+	    } // No change in the tree after handling all but the last statement.
+	    if (last > 0) {
+		Tree t = transform(stats[last]);
+		if (t != stats[last]) {
+		    Tree[] res = new Tree[stats.length];
+		    System.arraycopy(stats, 0, res, 0, last);
+		    res[last] = t;
+		    return copy.Block(tree,res);
+		}
+	    }
+	    // No change at all
+            return copy.Block(tree,stats);
+	}
+
+
+        case Sequence(Tree[] trees):
+            return copy.Sequence(tree, tail_transform(trees,false));
+
+
+
+        case Assign(Tree lhs, Tree rhs):
+            return copy.Assign(tree,
+			       tail_transform(lhs,false),
+			       tail_transform(rhs,false));
+
+
+	case If(Tree cond, Tree thenp, Tree elsep): {
+            return copy.If(tree, tail_transform(cond,false),
+			   transform(thenp),
+			   transform(elsep));
+	}
+
+	case New(Template templ):
+	    // At the moment we assume that the call to the constructor can not be
+	    // a tailcall.
+            return copy.New(tree, tail_transform(templ,false));
+
+        case Typed(Tree expr, Tree tpe):
+            return copy.Typed(tree,
+			      transform(expr),
+			      tail_transform(tpe,false));
+
+        case TypeApply(Tree fun, Tree[] args):
+            return copy.TypeApply(tree,
+				  tail_transform(fun,false),
+				  tail_transform(args,false));
+
+        default:
+            return super.transform(tree);
+        }
+    }
+
+    public Tree transform_new(Tree tree) {
+	push_new();
+	Tree res = transform(tree);
+	pop();
+	return res;
+    }
+
+
+    public Template transform_new(Template t) {
+	push_new();
+	Template res = (Template)transform((Tree)t);
+	pop();
+	return res;
+    }
+
+    public Tree tail_transform(Tree tree,boolean inTailPosition) {
+	boolean save = state.inTailPosition;
+	state.inTailPosition = inTailPosition;
+	Tree res = transform(tree);
+	state.inTailPosition = save;
+	return res;
+    }
+
+    public Tree[] tail_transform(Tree[] tree,boolean inTailPosition) {
+	boolean save = state.inTailPosition;
+	state.inTailPosition = inTailPosition;
+	Tree[] res = transform(tree);
+	state.inTailPosition = save;
+	return res;
+    }
+
+    public Template tail_transform(Template tree,boolean inTailPosition) {
+	boolean save = state.inTailPosition;
+	state.inTailPosition = inTailPosition;
+	Template res = (Template)transform((Tree)tree);
+	state.inTailPosition = save;
+	return res;
+    }
+
+    public AbsTypeDef[] tail_transform(AbsTypeDef[] tree,boolean inTailPosition) {
+	boolean save = state.inTailPosition;
+	state.inTailPosition = inTailPosition;
+	AbsTypeDef[] res = transform(tree);
+	state.inTailPosition = save;
+	return res;
+    }
+
+    public ValDef[][] tail_transform(ValDef[][] tree,boolean inTailPosition) {
+	boolean save = state.inTailPosition;
+	state.inTailPosition = inTailPosition;
+	ValDef[][] res = transform(tree);
+	state.inTailPosition = save;
+	return res;
+    }
+
+
+    public Template transform_class(Template t, Symbol currentClass) {
+	Symbol saveClass = state.currentClass;
+	Symbol saveFunction = state.currentFunction;
+	state.currentFunction = null;
+	state.currentClass = currentClass;
+	Template res = (Template)transform((Tree)t);
+	state.currentFunction = saveFunction;
+	state.currentClass = saveClass;
+	return res;
+    }
+
+
+
+    private Ident[] to_ident(Tree[] tree) {
+	Ident[] ids = new Ident[tree.length];
+	for (int i = 0; i < tree.length; i++) {
+	    switch (tree[i]) {
+	    case AbsTypeDef(int mods, Name name, Tree bound, Tree lobound):
+		Ident arg = new ExtIdent(tree[i].symbol());
+		arg.setType(tree[i].type());
+		ids[i]= arg;
+		break;
+
+	    case ValDef(int mods, Name name, Tree tpe, Tree.Empty):
+		Ident arg = new ExtIdent(tree[i].symbol());
+		arg.setType(tree[i].type());
+		ids[i]= arg;
+		break;
+
+	    default:
+		Debug.abort("bad parameter: " + tree[i]);
+	    }
+	}
+	return ids;
+    }
+
+}