From e2565c03562743d04f2f2c3557f5342ea5b76fbe Mon Sep 17 00:00:00 2001 From: Iulian Dragos Date: Thu, 11 Oct 2007 14:39:17 +0000 Subject: - Improved tail call elimination to handle call... - Improved tail call elimination to handle calls on a different instance. - Improved tail calls by skipping trivial arguments (when the argument to the call is the parameter itself) - added preliminary support for incremental DFA. --- .../tools/nsc/backend/icode/BasicBlocks.scala | 4 ++ .../scala/tools/nsc/backend/icode/GenICode.scala | 30 ++++++---- .../scala/tools/nsc/backend/icode/Opcodes.scala | 16 ++++++ .../backend/icode/analysis/CopyPropagation.scala | 12 ++-- .../backend/icode/analysis/DataFlowAnalysis.scala | 20 ++++++- .../backend/icode/analysis/TypeFlowAnalysis.scala | 25 ++++++++ .../scala/tools/nsc/backend/jvm/GenJVM.scala | 5 ++ .../scala/tools/nsc/backend/msil/GenMSIL.scala | 5 ++ .../tools/nsc/backend/opt/ClosureElimination.scala | 4 +- .../nsc/backend/opt/DeadCodeElimination.scala | 2 +- .../scala/tools/nsc/backend/opt/Inliners.scala | 6 +- src/compiler/scala/tools/nsc/symtab/StdNames.scala | 1 + src/compiler/scala/tools/nsc/transform/Mixin.scala | 4 +- .../scala/tools/nsc/transform/TailCalls.scala | 67 ++++++++++++---------- 14 files changed, 148 insertions(+), 53 deletions(-) (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index f02dfa07f5..bc5133e3a3 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -319,6 +319,10 @@ trait BasicBlocks { } } + def emit(instrs: Seq[Instruction]) { + instrs foreach (i => emit(i, i.pos)) + } + /** Close the block */ def close = { assert(instructionList.length > 0, diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala index 06c8585840..2575982184 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala @@ -1076,24 +1076,32 @@ abstract class GenICode extends SubComponent { var ctx1 = ctx var arg = args var param = label.params + val stores: ListBuffer[Instruction] = new ListBuffer // store arguments in reverse order on the stack while (arg != Nil) { - val Some(l) = ctx.method.lookupLocal(param.head) - ctx1 = genLoad(arg.head, ctx1, l.kind) - arg = arg.tail - param = param.tail - } - - // store arguments in the right variables - arg = args.reverse; param = label.params.reverse; - while (arg != Nil) { - val Some(l) = ctx.method.lookupLocal(param.head) - ctx1.bb.emit(STORE_LOCAL(l), arg.head.pos) + arg.head match { + case This(_) if param.head.name == nme.THIS => + //println("skipping trivial argument for " + param.head) + () // skip trivial arguments + case Ident(_) if arg.head.symbol == param.head => + //println("skipping trivial argument for " + param.head) + () // skip trivial arguments + case _ => + val Some(l) = ctx.method.lookupLocal(param.head) + ctx1 = genLoad(arg.head, ctx1, l.kind) + if (param.head.name == nme.THIS) + STORE_THIS(toTypeKind(ctx1.clazz.symbol.tpe)).setPos(arg.head.pos) +: stores + else { + STORE_LOCAL(l).setPos(arg.head.pos) +: stores + } + } arg = arg.tail param = param.tail } + //println("stores: " + stores) + ctx1.bb.emit(stores) ctx1 } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index 2064f84af0..f53be450d9 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -81,6 +81,11 @@ trait Opcodes { self: ICodes => /** Used by dead code elimination. */ var useful: Boolean = false + + def setPos(p: Position): this.type = { + pos = p + this + } } object opcodes { @@ -220,6 +225,17 @@ trait Opcodes { self: ICodes => List(REFERENCE(field.owner), toTypeKind(field.tpe)); } + /** Store a value into the 'this' pointer. + * Stack: ...:ref + * ->: ... + */ + case class STORE_THIS(kind: TypeKind) extends Instruction { + override def toString() = "STORE_THIS(" + kind + ")" + override def consumed = 1 + override def produced = 0 + override def consumedTypes = List(kind) + } + /** Call a primitive function. * Stack: ...:arg1:arg2:...:argn * ->: ...:result diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala index cca21adc98..8b2aecafe8 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala @@ -21,16 +21,16 @@ abstract class CopyPropagation { import global._ import icodes._ - /** Locations can be local variables and fields. */ + /** Locations can be local variables, this, and fields. */ abstract sealed class Location; case class LocalVar(l: Local) extends Location case class Field(r: Record, sym: Symbol) extends Location + case object This extends Location /** Values that can be on the stack. */ abstract class Value { def isRecord = false } - case class This extends Value case class Record(cls: Symbol, bindings: Map[Symbol, Value]) extends Value { override def isRecord = true } @@ -114,7 +114,7 @@ abstract class CopyPropagation { var target: Value = r.bindings(f) target match { case Deref(LocalVar(l)) => Some(Deref(LocalVar(getAlias(l)))) - case This() => Some(target) + case Deref(This) => Some(target) case _ => None } } @@ -220,7 +220,7 @@ abstract class CopyPropagation { i match { case THIS(_) => - out.stack = This :: out.stack + out.stack = Deref(This) :: out.stack case CONSTANT(k) => if (k.tag != UnitTag) @@ -267,6 +267,10 @@ abstract class CopyPropagation { } out.stack = out.stack drop 1; + case STORE_THIS(_) => + cleanReferencesTo(out, This) + out.stack = out.stack drop 1 + case STORE_FIELD(field, isStatic) => if (isStatic) out.stack = out.stack.drop(1); diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala index e5838245c3..aa0fa31f0f 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -23,12 +23,28 @@ trait DataFlowAnalysis[L <: CompleteLattice] { val out: Map[P, lattice.Elem] = new HashMap val visited: HashSet[P] = new HashSet + /** collect statistics? */ + var stat = false + + /** the number of times we iterated before reaching a fixpoint. */ + var iterations = 0 + /* Implement this function to initialize the worklist. */ def init(f: => Unit): Unit = { + iterations = 0 in.clear; out.clear; worklist.clear; visited.clear; f } + /** Reinitialize, but keep the old solutions. Should be used when reanalyzing the + * same method, after some code transformation. + */ + def reinit(f: => Unit): Unit = { + iterations = 0 + worklist.clear; visited.clear; + f + } + def run: Unit /** Implements forward dataflow analysis: the transfer function is @@ -39,10 +55,11 @@ trait DataFlowAnalysis[L <: CompleteLattice] { */ def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = try { while (!worklist.isEmpty) { + if (stat) iterations += 1 // Console.println("worklist in: " + worklist); val point = worklist.elements.next; worklist -= point; visited += point; + //Console.println("taking out point: " + point + " worklist out: " + worklist); val output = f(point, in(point)) -// Console.println("taking out point: " + point + " worklist out: " + worklist); if ((lattice.bottom == out(point)) || output != out(point)) { // Console.println("Output changed at " + point + " from: " + out(point) + " to: " + output + " and they are different: " + (output != out(point))) @@ -69,6 +86,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] { */ def backwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = while (!worklist.isEmpty) { + if (stat) iterations += 1 val point = worklist.elements.next; worklist -= point out(point) = lattice.lub(point.successors map in.apply) diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala index 56c1e2b83b..e8dd927156 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -128,6 +128,28 @@ abstract class TypeFlowAnalysis { } } + /** reinitialize the analysis, keeping around solutions from a previous run. */ + def reinit(m: icodes.IMethod) { + if ((this.method eq null) || (this.method.symbol != m.symbol)) + init(m) + else reinit { + for (b <- m.code.blocks; if !in.isDefinedAt(b)) { + for (p <- b.predecessors) { + worklist += p + if (out.isDefinedAt(p)) + in(b) = out(p) + else + in(b) = typeFlowLattice.bottom + } + out(b) = typeFlowLattice.bottom + } + for (exh <- m.exh; if !in.isDefinedAt(exh.startBlock)) { + worklist += exh.startBlock + in(exh.startBlock) = lattice.IState(in(exh.startBlock).vars, typeStackLattice.exceptionHandlerStack) + } + } + } + def this(m: icodes.IMethod) { this() init(m) @@ -187,6 +209,9 @@ abstract class TypeFlowAnalysis { val t = stack.pop bindings += local -> t + case STORE_THIS(_) => + stack.pop + case STORE_FIELD(field, isStatic) => if (isStatic) stack.pop diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index f793346d66..63f4daed46 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -744,6 +744,11 @@ abstract class GenJVM extends SubComponent { case STORE_LOCAL(local) => jcode.emitSTORE(indexOf(local), javaType(local.kind)) + case STORE_THIS(_) => + // this only works for impl classes because the self parameter comes first + // in the method signature. If that changes, this code has to be revisited. + jcode.emitASTORE_0() + case STORE_FIELD(field, isStatic) => val owner = javaName(field.owner) // + (if (field.owner.hasFlag(Flags.MODULE)) "$" else ""); if (isStatic) diff --git a/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala b/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala index 047bf656eb..362a4f0347 100644 --- a/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala +++ b/src/compiler/scala/tools/nsc/backend/msil/GenMSIL.scala @@ -1334,6 +1334,11 @@ abstract class GenMSIL extends SubComponent { } } + case STORE_THIS(_) => + // this only works for impl classes because the self parameter comes first + // in the method signature. If that changes, this code has to be revisited. + mcode.Emit(OpCodes.Starg_S, 0) + case STORE_FIELD(field, isStatic) => val fieldInfo: FieldInfo = fields.get(field) match { case Some(fInfo) => fInfo diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala index e51e89ddbd..f303ced787 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala @@ -109,7 +109,7 @@ abstract class ClosureElimination extends SubComponent { bb.replaceInstruction(i, valueToInstruction(t)); log("replaced " + i + " with " + t) - case This() => + case Deref(This) => bb.replaceInstruction(i, valueToInstruction(t)); log("replaced " + i + " with " + t) @@ -182,7 +182,7 @@ abstract class ClosureElimination extends SubComponent { case Deref(LocalVar(v)) => LOAD_LOCAL(v) - case This() => + case Deref(This) => THIS(definitions.ObjectClass) } diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala index 3bcb9e98bf..9c3bd176d0 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -99,7 +99,7 @@ abstract class DeadCodeElimination extends SubComponent { defs = defs + ((bb, idx)) -> rd.vars // Console.println(i + ": " + (bb, idx) + " rd: " + rd + " and having: " + defs) case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | STORE_FIELD(_, _) | - THROW() | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | + THROW() | STORE_ARRAY_ITEM(_) | SCOPE_ENTER(_) | SCOPE_EXIT(_) | STORE_THIS(_) | LOAD_EXCEPTION() | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() => worklist += ((bb, idx)) case CALL_METHOD(m1, _) if isSideEffecting(m1) => worklist += ((bb, idx)); log("marking " + m1) case CALL_METHOD(m1, SuperCall(_)) => diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 8dabbd3173..c37c2b48cb 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -271,6 +271,7 @@ abstract class Inliners extends SubComponent { val tfa = new analysis.MethodTFA(); + tfa.stat = settings.statistics.value def analyzeMethod(m: IMethod): Unit = try { var retry = false; @@ -355,8 +356,9 @@ abstract class Inliners extends SubComponent { case _ => (); } info = tfa.interpret(info, i) - }}}} - } while (retry && count < 15) + }}} + if (tfa.stat) log(m.symbol.fullNameString + " iterations: " + tfa.iterations + " (size: " + m.code.blocks.length + ")") + }} while (retry && count < 15) m.normalize } catch { case e => diff --git a/src/compiler/scala/tools/nsc/symtab/StdNames.scala b/src/compiler/scala/tools/nsc/symtab/StdNames.scala index 5cc4bd2542..ed3348e838 100644 --- a/src/compiler/scala/tools/nsc/symtab/StdNames.scala +++ b/src/compiler/scala/tools/nsc/symtab/StdNames.scala @@ -178,6 +178,7 @@ trait StdNames { val BYNAME_PARAM_CLASS_NAME = newTermName("") val EQUALS_PATTERN_NAME = newTermName("") val SELF = newTermName("$this") + val THIS = newTermName("_$this") val CONSTRUCTOR = newTermName("") val MIXIN_CONSTRUCTOR = newTermName("$init$") diff --git a/src/compiler/scala/tools/nsc/transform/Mixin.scala b/src/compiler/scala/tools/nsc/transform/Mixin.scala index 5ba3db1afa..7289468406 100644 --- a/src/compiler/scala/tools/nsc/transform/Mixin.scala +++ b/src/compiler/scala/tools/nsc/transform/Mixin.scala @@ -352,7 +352,9 @@ abstract class Mixin extends InfoTransform { * - For every static implementation method: * - remove override flag * - create a new method definition that also has a `self' parameter - * (which comes first) + * (which comes first) Iuli: this position is assumed by tail call elimination + * on a different receiver. Storing a new 'this' assumes it is located at + * index 0 in the local variable table. See 'STORE_THIS' and GenJVM/GenMSIL. * - Map implementation class types in type-apply's to their interfaces * - Remove all fields in implementation classes */ diff --git a/src/compiler/scala/tools/nsc/transform/TailCalls.scala b/src/compiler/scala/tools/nsc/transform/TailCalls.scala index f59a509e33..b2e7fb079e 100644 --- a/src/compiler/scala/tools/nsc/transform/TailCalls.scala +++ b/src/compiler/scala/tools/nsc/transform/TailCalls.scala @@ -61,11 +61,15 @@ abstract class TailCalls extends Transform * 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 + * A method call is self-recursive if it calls the current method 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. + * parameters as type arguments. Recursive calls on a different instance + * are optimized. Since 'this' is not a local variable, a dummy local val + * is added and used as a label parameter. The backend knows to load + * the corresponding argument in the 'this' (local at index 0). This dummy local + * is never used and should be cleand up by dead code elmination (when enabled). *

*

* This phase has been moved before pattern matching to catch more @@ -150,7 +154,7 @@ abstract class TailCalls extends Transform val newCtx = mkContext(ctx) newCtx.currentMethod = tree.symbol newCtx.makeLabel() - newCtx.label.setInfo(tree.symbol.info) + newCtx.label.setInfo(MethodType(currentClass.tpe :: tree.symbol.tpe.paramTypes, tree.symbol.tpe.finalResultType)) newCtx.tailPos = true val t1 = if (newCtx.currentMethod.isFinal || @@ -161,19 +165,24 @@ abstract class TailCalls extends Transform case PolyType(tpes, restpe) => newCtx.tparams = tparams map (_.symbol) newCtx.label.setInfo( - restpe.substSym(tpes, tparams map (_.symbol))) + newCtx.label.tpe.substSym(tpes, tparams map (_.symbol))) case _ => () } + //println("label.tpe: " + newCtx.label.tpe) var newRHS = transform(rhs, newCtx); if (newCtx.accessed) { log("Rewrote def " + newCtx.currentMethod) + val newThis = newCtx.currentMethod.newValue(tree.pos, nme.THIS) + .setInfo(currentClass.tpe) + .setFlag(Flags.SYNTHETIC) newRHS = - typed(atPos(tree.pos)( + typed(atPos(tree.pos)(Block(List( + ValDef(newThis, This(currentClass))), LabelDef(newCtx.label, - List.flatten(vparams) map (_.symbol), - newRHS))); + newThis :: (List.flatten(vparams) map (_.symbol)), + newRHS)))); copy.DefDef(tree, mods, name, tparams, vparams, tpt, newRHS); } else copy.DefDef(tree, mods, name, tparams, vparams, tpt, newRHS); @@ -242,10 +251,13 @@ abstract class TailCalls extends Transform if ( ctx.currentMethod.isFinal && ctx.tailPos && isSameTypes(ctx.tparams, targs map (_.tpe.typeSymbol)) && - isRecursiveCall(fun)) - rewriteTailCall(fun, transformTrees(vargs, mkContext(ctx, false))) - else - copy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false))) + isRecursiveCall(fun)) { + fun match { + case Select(receiver, _) => rewriteTailCall(fun, receiver :: transformTrees(vargs, mkContext(ctx, false))) + case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(vargs, mkContext(ctx, false))) + } + } else + copy.Apply(tree, tapply, transformTrees(vargs, mkContext(ctx, false))) case TypeApply(fun, args) => super.transform(tree) @@ -257,9 +269,12 @@ abstract class TailCalls extends Transform case Apply(fun, args) => if (ctx.currentMethod.isFinal && ctx.tailPos && - isRecursiveCall(fun)) - rewriteTailCall(fun, transformTrees(args, mkContext(ctx, false))) - else + isRecursiveCall(fun)) { + fun match { + case Select(receiver, _) => rewriteTailCall(fun, receiver :: transformTrees(args, mkContext(ctx, false))) + case _ => rewriteTailCall(fun, This(currentClass) :: transformTrees(args, mkContext(ctx, false))) + } + } else copy.Apply(tree, fun, transformTrees(args, mkContext(ctx, false))) case Super(qual, mix) => @@ -286,6 +301,7 @@ abstract class TailCalls extends Transform log("Rewriting tail recursive method call at: " + (fun.pos)) ctx.accessed = true + //println("fun: " + fun + " args: " + args) typed(atPos(fun.pos)( Apply(Ident(ctx.label), args))) } @@ -298,25 +314,14 @@ abstract class TailCalls extends Transform } /** Returns true if the fun tree refers to the same method as - * the one saved in ctx. If it is a method call, we check - * that it is applied to this. + * the one saved in ctx. * - * @param fun ... - * @return true ... + * @param fun the expression that is applied + * @return true if the tree symbol refers to the innermost + * enclosing method */ private def isRecursiveCall(fun: Tree): Boolean = - if (fun.symbol eq ctx.currentMethod) - fun match { - case Select(t @ This(_), _) => - assert(t.symbol == ctx.currentMethod.owner, "This refers to other class: " + - t.symbol + ": " + ctx.currentMethod.owner) - true - - case Ident(_) => true - case _ => false - } - else - false + (fun.symbol eq ctx.currentMethod) } } -- cgit v1.2.3