- Simplified and improved tail call optimization

3 files changed, 169 insertions, 372 deletions

diff --git a/config/list/compiler.lst b/config/list/compiler.lst
index f01229d81b..0d78ffa024 100644
--- a/config/list/compiler.lst
+++ b/config/list/compiler.lst
@@ -120,7 +120,6 @@ transformer/LambdaLift.java
 transformer/LambdaLiftPhase.java
 transformer/MakeBoxingExplicitPhase.java
 transformer/OwnerTransformer.java
-transformer/TailCall.java
 transformer/TailCallPhase.java
 transformer/TransMatch.java
 transformer/TransMatchPhase.java
diff --git a/sources/scalac/transformer/TailCall.java b/sources/scalac/transformer/TailCall.java
deleted file mode 100644
index 48c5a233e8..0000000000
--- a/sources/scalac/transformer/TailCall.java
+++ /dev/null
@@ -1,368 +0,0 @@
-/*     ____ ____  ____ ____  ______                                     *\
-**    / __// __ \/ __// __ \/ ____/    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().cloneType(tree.symbol(), newLabel));
-
-	    /* 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.getType());
-		// 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 instance of the class as we are in.
-			// If it is an Object (Module) we don't necessarily have a THIS, so we compare
-			// the types.
-			// If it's a class we have to make sure that the qulifier is a THIS node.
-			if ((state.currentClass.isModuleClass() &&
-			     qual.type.isSameAs(state.currentClass.thisType().widen())) ||
-			    (qual instanceof This && qual.symbol() == state.currentClass)){
-
-			    // We can only rewrite final functions in a safe way.
-			    if(state.currentFunction.isMethodFinal()) {
-
-				Tree[] newArgs = tail_transform(args,false);
-				// Redirect the call to the LabelDef.
-				Tree newTarget = new ExtIdent(state.newLabel).setType(fun.getType());
-				// Indicate that we have inserted a tail call.
-				state.needLabelDef = true;
-				return copy.Apply(tree,newTarget,newArgs);
-			    }
-			}
-		    }
-		    break;
-		    // TODO: Handle the case of Apply(TypeApply(T))
-		    // Have to check that the type T is the same as currentFunction.type()
-		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].getType());
-		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].getType());
-		ids[i]= arg;
-		break;
-
-	    default:
-		Debug.abort("bad parameter: " + tree[i]);
-	    }
-	}
-	return ids;
-    }
-
-}
diff --git a/sources/scalac/transformer/TailCallPhase.java b/sources/scalac/transformer/TailCallPhase.java
index 487f40743b..60574ad00c 100644
--- a/sources/scalac/transformer/TailCallPhase.java
+++ b/sources/scalac/transformer/TailCallPhase.java
@@ -12,7 +12,42 @@ import scalac.Global;
 import scalac.Phase;
 import scalac.PhaseDescriptor;
 import scalac.Unit;
+import scalac.ast.Tree;
+import scalac.ast.GenTransformer;
+import scalac.symtab.LabelSymbol;
+import scalac.symtab.Symbol;
+import scalac.symtab.Type;
+import scalac.util.Debug;
 
+/**
+ * A Tail Call Transformer
+ *
+ * @author     Erik Stenman
+ * @version    1.0
+ *
+ * What it does:
+ *
+ * Finds method calls in tail-position and replaces them with jumps.
+ * A call is in a tail-position if it is the last instruction to be
+ * executed in the body of a method.  This is done by recursing over
+ * the trees that may contain calls in tail-position (trees that can't
+ * contain such calls are not transformed).
+ *
+ * Self-recursive calls in tail-position are replaced by jumps to a
+ * label at the beginning of the method. As the JVM provides no way to
+ * jump from a method to another one, non-recursive calls in
+ * tail-position are not optimized.
+ *
+ * A method call is self-recursive if it calls the current method on
+ * the current instance and the method is final (otherwise, it could
+ * be a call to an overridden method in a subclass). Furthermore, If
+ * the method has type parameters, the call must contain these
+ * parameters as type arguments.
+ *
+ * If a method contains self-recursive calls, a label is added to at
+ * the beginning of its body and the calls are replaced by jumps to
+ * that label.
+ */
 public class TailCallPhase extends Phase {
 
     //########################################################################
@@ -27,10 +62,141 @@ public class TailCallPhase extends Phase {
     // Public Methods
 
     /** Applies this phase to the given compilation units. */
-     public void apply(Unit[] units) {
-        for (int i = 0; i < units.length; i++)
-            new TailCall(global, descriptor).apply(units[i]);
+    public void apply(Unit[] units) {
+        treeTransformer.apply(units);
     }
 
+   //########################################################################
+    // Private Classes
+
+    /** The tree transformer */
+    private final GenTransformer treeTransformer = new GenTransformer(global) {
+
+        /** The current method */
+        private Symbol method;
+
+        /** The current tail-call label */
+        private Symbol label;
+
+        /** The expected type arguments of self-recursive calls */
+        private Type[] types;
+
+        /** Transforms the given tree. */
+        public Tree transform(Tree tree) {
+            switch (tree) {
+
+            case DefDef(_, _, _, _, _, Tree rhs):
+                assert method == null: Debug.show(method) + " -- " + tree;
+                method = tree.symbol();
+                if (method.isMethodFinal()) {
+                    label = new LabelSymbol(method);
+                    types = Type.EMPTY_ARRAY;
+                    Type type = method.type();
+                    switch (type) {
+                    case PolyType(Symbol[] tparams, Type result):
+                        types = Symbol.type(tparams);
+                        type = result;
+                    }
+                    label.setInfo(type.cloneType(method, label));
+                    rhs = transform(rhs);
+                    if (label.isAccessed()) {
+                        rhs = gen.LabelDef(label, method.valueParams(), rhs);
+                        tree = gen.DefDef(method, rhs);
+                    }
+                    types = null;
+                    label = null;
+                }
+                method = null;
+                return tree;
+
+            case Block(Tree[] stats):
+                if (stats.length == 0) return tree;
+                Tree expr = transform(stats[stats.length - 1]);
+                if (expr == stats[stats.length - 1]) return tree;
+                stats = Tree.cloneArray(stats);
+                stats[stats.length - 1] = expr;
+                return gen.Block(tree.pos, stats);
+
+            case If(Tree cond, Tree thenp, Tree elsep):
+                Type type = tree.type();
+                thenp = transform(thenp);
+                elsep = transform(elsep);
+                return gen.If(tree.pos, cond, thenp, elsep, type);
 
+            case Switch(Tree test, int[] tags, Tree[] bodies, Tree otherwise):
+                Type type = tree.type();
+                bodies = transform(bodies);
+                otherwise = transform(otherwise);
+                return gen.Switch(tree.pos, test, tags, bodies,otherwise,type);
+
+            case Apply(TypeApply(Tree fun, Tree[] targs), Tree[] vargs):
+                if (!Type.isSameAs(Tree.typeOf(targs), types)) return tree;
+                return transform(tree, fun, vargs);
+            case Apply(Tree fun, Tree[] vargs):
+                return transform(tree, fun, vargs);
+
+            case ClassDef(_, _, _, _, _, _):
+            case PackageDef(_, _):
+            case LabelDef(_, _, _):
+            case Return(_):
+                return super.transform(tree);
+
+            case Empty:
+            case ValDef(_, _, _, _):
+            case Assign(_, _):
+            case New(_):
+            case Super(_, _):
+            case This(_):
+            case Select(_, _):
+            case Ident(_):
+            case Literal(_):
+            case TypeTerm():
+                return tree;
+
+            default:
+                throw Debug.abort("illegal case", tree);
+            }
+        }
+
+        /** Transforms the given function call. */
+        private Tree transform(Tree tree, Tree fun, Tree[] vargs) {
+            Symbol symbol = fun.symbol();
+            if (symbol != method) return tree;
+            switch (fun) {
+            case Select(Tree qual, _):
+                if (!isReferenceToThis(qual, method.owner())) return tree;
+                return gen.Apply(tree.pos, gen.Ident(qual.pos, label), vargs);
+            case Ident(_):
+                assert fun.symbol().isLabel();
+                return tree;
+            default:
+                throw Debug.abort("illegal case", fun);
+            }
+        }
+
+        /**
+         * Returns true if the tree represents the current instance of
+         * given class.
+         */
+        private boolean isReferenceToThis(Tree tree, Symbol clasz) {
+            switch (tree) {
+            case This(_):
+                assert tree.symbol() == clasz: tree +" -- "+ Debug.show(clasz);
+                return true;
+            case Select(Tree qual, _):
+                if (!clasz.isModuleClass()) return false;
+                if (tree.symbol() != clasz.module()) return false;
+                return isReferenceToThis(qual, clasz.owner());
+            case Ident(_):
+                if (!clasz.isModuleClass()) return false;
+                if (tree.symbol() != clasz.module()) return false;
+                return true;
+            default:
+                return false;
+            }
+        }
+
+    };
+
+    //########################################################################
 }