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 | |
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')
-rw-r--r-- | sources/scalac/transformer/TailCall.java | 368 | ||||
-rw-r--r-- | sources/scalac/transformer/TailCallPhase.java | 172 |
2 files changed, 169 insertions, 371 deletions
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; + } + } + + }; + + //######################################################################## } |