diff options
author | paltherr <paltherr@epfl.ch> | 2004-01-23 20:39:41 +0000 |
---|---|---|
committer | paltherr <paltherr@epfl.ch> | 2004-01-23 20:39:41 +0000 |
commit | 5069b94720c924af4171863955cb80ac26a18ecb (patch) | |
tree | 9a4a28d18d518801f91a2704cb8a1769d19cff45 /sources/scalac/transformer/TailCallPhase.java | |
parent | 4209d6c8883b36b2116197cdc4f25baf0abd846f (diff) | |
download | scala-5069b94720c924af4171863955cb80ac26a18ecb.tar.gz scala-5069b94720c924af4171863955cb80ac26a18ecb.tar.bz2 scala-5069b94720c924af4171863955cb80ac26a18ecb.zip |
- Simplified and improved tail call optimization
Diffstat (limited to 'sources/scalac/transformer/TailCallPhase.java')
-rw-r--r-- | sources/scalac/transformer/TailCallPhase.java | 172 |
1 files changed, 169 insertions, 3 deletions
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; + } + } + + }; + + //######################################################################## } |