/* ____ ____ ____ ____ ______ *\
** / __// __ \/ __// __ \/ ____/ SOcos COmpiles Scala **
** __\_ \/ /_/ / /__/ /_/ /\_ \ (c) 2002, LAMP/EPFL **
** /_____/\____/\___/\____/____/ **
\* */
// $Id$
package scalac.transformer;
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 {
//########################################################################
// Public Constructors
/** Initializes this instance. */
public TailCallPhase(Global global, PhaseDescriptor descriptor) {
super(global, descriptor);
}
//########################################################################
// Public Methods
/** Applies this phase to the given compilation units. */
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, Tree value):
return gen.Block(tree.pos, stats, transform(value));
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;
}
}
};
//########################################################################
}
