diff options
13 files changed, 711 insertions, 69 deletions
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 5bec4e39d7..4fd5404a91 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -25,8 +25,8 @@ import transform._; import backend.icode.{ICodes, GenICode, Checkers}; import backend.ScalaPrimitives; import backend.jvm.GenJVM; -import backend.opt.Inliners; -import backend.icode.analysis.TypeFlowAnalysis; +import backend.opt.{Inliners, ClosureElimination}; +import backend.icode.analysis._; class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable with Trees @@ -69,6 +69,10 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable val global: Global.this.type = Global.this; } + object copyPropagation extends CopyPropagation { + val global: Global.this.type = Global.this; + } + object checkers extends Checkers { val global: Global.this.type = Global.this } @@ -302,6 +306,10 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable val global: Global.this.type = Global.this } + object closser extends ClosureElimination { + val global: Global.this.type = Global.this + } + object genJVM extends GenJVM { val global: Global.this.type = Global.this } @@ -331,6 +339,7 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable cleanup, genicode, inliner, + closser, genJVM, sampleTransform); @@ -558,8 +567,8 @@ class Global(val settings: Settings, val reporter: Reporter) extends SymbolTable val printer = new icodePrinter.TextPrinter(null, icodes.linearizer); icodes.classes.values.foreach((cls) => { var file = getFile(cls.symbol, ".icode"); - if (file.exists()) - file = new File(file.getParentFile(), file.getName() + "1"); +// if (file.exists()) +// file = new File(file.getParentFile(), file.getName() + "1"); try { val stream = new FileOutputStream(file); printer.setWriter(new PrintWriter(stream, true)); diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index 112932be3a..2cca35fa3a 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -107,6 +107,7 @@ class Settings(error: String => unit) { // val showPhases = BooleanSetting("-showphases", "Print a synopsis of compiler phases") val inline = BooleanSetting("-Xinline", "Perform inlining when possible") + val Xcloselim = BooleanSetting("-Xcloselim", "Perform closure elimination") val Xshowcls = StringSetting ("-Xshowcls", "class", "Show class info", "") val Xshowobj = StringSetting ("-Xshowobj", "object", "Show object info", "") val Xshowicode = BooleanSetting("-Xshowicode", "Print the generated ICode") diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index 7bb3d9c8d2..8f694ea764 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -115,6 +115,32 @@ trait BasicBlocks requires ICodes { changed } + def replaceInstruction(iold: Instruction, is: List[Instruction]): Boolean = { + assert(closed, "Instructions can be replaced only after the basic block is closed"); + + var i = 0; + var changed = false; + + while (i < instrs.length && (instrs(i) ne iold)) + i = i + 1; + + if (i < instrs.length) { + val newInstrs = new Array[Instruction](instrs.length + is.length - 1); + changed = true; + System.arraycopy(instrs, 0, newInstrs, 0, i); + var j = i; + for (val x <- is) { + newInstrs(j) = x; + j = j + 1; + } + if (i + 1 < instrs.length - 1) + System.arraycopy(instrs, i + 1, newInstrs, j, instrs.length - i - 1) + instrs = newInstrs; + } + + changed + } + /** Replace all instructions found in the map. */ def subst(map: Map[Instruction, Instruction]) = if (!closed) substOnList(map) else { diff --git a/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala b/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala index 9b03882889..1930f6566f 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Checkers.scala @@ -264,7 +264,7 @@ abstract class Checkers { a + ", " + b + " found"); } - case LOAD_LOCAL(local, isArg) => + case LOAD_LOCAL(local) => checkLocal(local); stack.push(local.kind); @@ -298,7 +298,7 @@ abstract class Checkers { " but " + a + ", " + b + ", " + c + " found"); } - case STORE_LOCAL(local, isArg) => + case STORE_LOCAL(local) => checkLocal(local); checkStack(1); diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala index fd82a4f0d6..4f79ae3f30 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala @@ -160,7 +160,7 @@ abstract class GenICode extends SubComponent { // "Assignment to inexistent local or field: " + lhs.symbol); val ctx1 = genLoad(rhs, ctx, toTypeKind(lhs.symbol.info)); val Some(l) = ctx.method.lookupLocal(lhs.symbol); - ctx1.bb.emit(STORE_LOCAL(l, lhs.symbol.isValueParameter), tree.pos); + ctx1.bb.emit(STORE_LOCAL(l), tree.pos); ctx1 case _ => @@ -346,7 +346,7 @@ abstract class GenICode extends SubComponent { case None => ctx1.labels += tree.symbol -> (new Label(tree.symbol) anchor ctx1.bb setParams (params map (.symbol))); - ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info)))); + ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false))); if (settings.debug.value) log("Adding label " + tree.symbol); } @@ -364,7 +364,7 @@ abstract class GenICode extends SubComponent { case ValDef(_, _, _, rhs) => val sym = tree.symbol; - val local = new Local(sym, toTypeKind(sym.info)); + val local = new Local(sym, toTypeKind(sym.info), false); ctx.method.addLocal(local); if (rhs == EmptyTree) { @@ -377,7 +377,7 @@ abstract class GenICode extends SubComponent { if (rhs != EmptyTree) ctx1 = genLoad(rhs, ctx, local.kind); - ctx1.bb.emit(STORE_LOCAL(local, false), tree.pos); + ctx1.bb.emit(STORE_LOCAL(local), tree.pos); generatedType = UNIT; ctx1 @@ -420,7 +420,7 @@ abstract class GenICode extends SubComponent { val returnedKind = toTypeKind(expr.tpe); val ctx1 = genLoad(expr, ctx, returnedKind); for (val m <- ctx1.monitors) { - ctx1.bb.emit(LOAD_LOCAL(m, false)); + ctx1.bb.emit(LOAD_LOCAL(m)); ctx1.bb.emit(MONITOR_EXIT()); } ctx1.bb.emit(RETURN(returnedKind), tree.pos); @@ -447,12 +447,12 @@ abstract class GenICode extends SubComponent { }) case Bind(name, _) => - val exception = new Local(pat.symbol, toTypeKind(pat.symbol.tpe)); + val exception = new Local(pat.symbol, toTypeKind(pat.symbol.tpe), false); ctx.method.addLocal(exception); Pair(pat.symbol.tpe.symbol, { ctx: Context => - ctx.bb.emit(STORE_LOCAL(exception, false), pat.pos); + ctx.bb.emit(STORE_LOCAL(exception), pat.pos); val ctx1 = genLoad(finalizer, ctx, UNIT); genLoad(body, ctx1, kind) }) @@ -636,12 +636,12 @@ abstract class GenICode extends SubComponent { ctx1 = afterCtx; } else if (code == scalaPrimitives.SYNCHRONIZED) { val monitor = new Local(ctx.method.symbol.newVariable(tree.pos, unit.fresh.newName("monitor")).setInfo(definitions.ObjectClass.tpe), - ANY_REF_CLASS); + ANY_REF_CLASS, false); ctx.method.addLocal(monitor); ctx1 = genLoadQualifier(fun, ctx1); ctx1.bb.emit(DUP(ANY_REF_CLASS)); - ctx1.bb.emit(STORE_LOCAL(monitor, false)); + ctx1.bb.emit(STORE_LOCAL(monitor)); ctx1.bb.emit(MONITOR_ENTER(), tree.pos); ctx1.enterSynchronized(monitor); @@ -650,12 +650,12 @@ abstract class GenICode extends SubComponent { ctx1 = ctx1.Try( bodyCtx => { val ctx1 = genLoad(args.head, bodyCtx, expectedType /* toTypeKind(tree.tpe.resultType) */); - ctx1.bb.emit(LOAD_LOCAL(monitor, false)); + ctx1.bb.emit(LOAD_LOCAL(monitor)); ctx1.bb.emit(MONITOR_EXIT(), tree.pos); ctx1 }, List( Pair(NoSymbol, exhCtx => { - exhCtx.bb.emit(LOAD_LOCAL(monitor, false)); + exhCtx.bb.emit(LOAD_LOCAL(monitor)); exhCtx.bb.emit(MONITOR_EXIT(), tree.pos); exhCtx.bb.emit(THROW()); exhCtx.bb.enterIgnoreMode; @@ -748,7 +748,7 @@ abstract class GenICode extends SubComponent { } else { try { val Some(l) = ctx.method.lookupLocal(tree.symbol); - ctx.bb.emit(LOAD_LOCAL(l, tree.symbol.isValueParameter), tree.pos); + ctx.bb.emit(LOAD_LOCAL(l), tree.pos); generatedType = l.kind; } catch { case ex: MatchError => @@ -904,7 +904,7 @@ abstract class GenICode extends SubComponent { arg = args.reverse; param = label.params.reverse; while (arg != Nil) { val Some(l) = ctx.method.lookupLocal(param.head); - ctx1.bb.emit(STORE_LOCAL(l, param.head.isValueParameter), arg.head.pos); + ctx1.bb.emit(STORE_LOCAL(l), arg.head.pos); arg = arg.tail; param = param.tail; } @@ -1122,7 +1122,7 @@ abstract class GenICode extends SubComponent { case LabelDef(name, params, rhs) => if (!ctx.labels.contains(tree.symbol)) { ctx.labels += tree.symbol -> (new Label(tree.symbol) setParams(params map (.symbol))); - ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info)))); + ctx.method.addLocals(params map (p => new Local(p.symbol, toTypeKind(p.symbol.info), false))); } super.traverse(rhs); @@ -1232,7 +1232,7 @@ abstract class GenICode extends SubComponent { case None => eqEqTempVar = ctx.method.symbol.newVariable(l.pos, eqEqTemp); eqEqTempVar.setInfo(definitions.AnyRefClass.typeConstructor); - eqEqTempLocal = new Local(eqEqTempVar, REFERENCE(definitions.AnyRefClass)); + eqEqTempLocal = new Local(eqEqTempVar, REFERENCE(definitions.AnyRefClass), false); ctx.method.addLocal(eqEqTempLocal); } @@ -1240,17 +1240,17 @@ abstract class GenICode extends SubComponent { ctx1 = genLoad(r, ctx1, ANY_REF_CLASS); val tmpNullCtx = ctx1.newBlock; val tmpNonNullCtx = ctx1.newBlock; - ctx1.bb.emit(STORE_LOCAL(eqEqTempLocal, false), l.pos); + ctx1.bb.emit(STORE_LOCAL(eqEqTempLocal), l.pos); ctx1.bb.emit(DUP(ANY_REF_CLASS)); ctx1.bb.emit(CZJUMP(tmpNullCtx.bb, tmpNonNullCtx.bb, EQ, ANY_REF_CLASS)); ctx1.bb.close; tmpNullCtx.bb.emit(DROP(ANY_REF_CLASS), l.pos); // type of AnyRef - tmpNullCtx.bb.emit(LOAD_LOCAL(eqEqTempLocal, false)); + tmpNullCtx.bb.emit(LOAD_LOCAL(eqEqTempLocal)); tmpNullCtx.bb.emit(CZJUMP(thenCtx.bb, elseCtx.bb, EQ, ANY_REF_CLASS)); tmpNullCtx.bb.close; - tmpNonNullCtx.bb.emit(LOAD_LOCAL(eqEqTempLocal, false), l.pos); + tmpNonNullCtx.bb.emit(LOAD_LOCAL(eqEqTempLocal), l.pos); tmpNonNullCtx.bb.emit(CALL_METHOD(definitions.Object_equals, Dynamic)); tmpNonNullCtx.bb.emit(CZJUMP(thenCtx.bb, elseCtx.bb, NE, BOOL)); tmpNonNullCtx.bb.close; @@ -1279,7 +1279,7 @@ abstract class GenICode extends SubComponent { case vparams :: Nil => for (val p <- vparams) - ctx.method.addParam(new Local(p.symbol, toTypeKind(p.symbol.info))); + ctx.method.addParam(new Local(p.symbol, toTypeKind(p.symbol.info), true)); ctx.method.params = ctx.method.params.reverse; case _ => diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala index c93d318d5a..62ce35732e 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala @@ -208,7 +208,7 @@ trait Members requires ICodes { } /** Represent local variables and parameters */ - class Local(val sym: Symbol, val kind: TypeKind) { + class Local(val sym: Symbol, val kind: TypeKind, val arg: Boolean) { var index: Int = -1; override def equals(other: Any): Boolean = ( diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index d2a4e38ff2..ea280b6fd2 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -17,11 +17,11 @@ import scala.tools.nsc.util.Position; case THIS(clasz) => case CONSTANT(const) => case LOAD_ARRAY_ITEM(kind) => - case LOAD_LOCAL(local, isArg) => + case LOAD_LOCAL(local) => case LOAD_FIELD(field, isStatic) => case LOAD_MODULE(module) => case STORE_ARRAY_ITEM(kind) => - case STORE_LOCAL(local, isArg) => + case STORE_LOCAL(local) => case STORE_FIELD(field, isStatic) => case CALL_PRIMITIVE(primitive) => case CALL_METHOD(method, style) => @@ -112,7 +112,7 @@ trait Opcodes requires ICodes { * Stack: ... * ->: ...:value */ - case class LOAD_LOCAL(local: Local, isArgument: boolean) extends Instruction { + case class LOAD_LOCAL(local: Local) extends Instruction { /** Returns a string representation of this instruction */ override def toString(): String = "LOAD_LOCAL "+local.toString(); //+isArgument?" (argument)":""; @@ -161,7 +161,7 @@ trait Opcodes requires ICodes { * Stack: ...:value * ->: ... */ - case class STORE_LOCAL(local: Local, isArgument: boolean) extends Instruction { + case class STORE_LOCAL(local: Local) extends Instruction { /** Returns a string representation of this instruction */ override def toString(): String = "STORE_LOCAL "+local.toString(); //+isArgument?" (argument)":""; @@ -195,6 +195,7 @@ trait Opcodes requires ICodes { case Test(_,_,true) => 1; case Test(_,_,false) => 2; case Comparison(_,_) => 2; + case Arithmetic(NOT,_) => 1; case Arithmetic(_,_) => 2; case Logical(_,_) => 2; case Shift(_,_) => 2; diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala index 5e249cf17f..629c4e0d5b 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala @@ -87,6 +87,7 @@ abstract class Printers { if (!m.isDeferred) { println(" {"); println("locals: " + m.locals.mkString("", ", ", "")); + println("startBlock: " + m.code.startBlock); println; lin.linearize(m) foreach printBlock; println("}"); diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala new file mode 100644 index 0000000000..4de2e24014 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala @@ -0,0 +1,437 @@ +package scala.tools.nsc.backend.icode.analysis; + +import scala.collection.mutable.{Map, HashMap}; + +/** + * A modified copy-propagation like analysis. It + * is augmented with a record-like value which is used + * to represent closures. + */ +abstract class CopyPropagation { + val global: Global; + import global._; + import icodes._; + + /** Locations can be local variables. */ + abstract sealed class Location; + case class LocalVar(l: Local) extends Location; + + /** Values that can be on the stack. */ + abstract class Value; + case class This extends Value; + case class Record(cls: Symbol, bindings: Map[Symbol, Value]) extends Value; + case class Deref(l: Location) extends Value; + case class Field(r: Record, sym: Symbol) extends Value; + case object Unknown extends Value; + + /** The lattice for this analysis. */ + object copyLattice extends CompleteLattice { + type Bindings = Map[Location, Value]; + + def emptyBinding = new HashMap[Location, Value](); + + class State(val bindings: Bindings, var stack: List[Value]) { + override def equals(that: Any): Boolean = + (this eq that.asInstanceOf[AnyRef]) || + that.isInstanceOf[State] && { + val other = that.asInstanceOf[State]; + + /* comparison with bottom is reference equality! */ + if ((other eq bottom) || (this eq bottom)) + (this eq other) + else { + this.bindings == other.bindings && + List.forall2(this.stack, other.stack) { (a, b) => a == b } + } + } + + /* Return the binding for the given local (another local) */ + def getAlias(l: Local): Local = { + var target = l; + var stop = false; + + while (bindings.isDefinedAt(LocalVar(target)) && !stop) { + Console.println("finding alias for " + target); + bindings(LocalVar(target)) match { + case Deref(LocalVar(t)) => target = t; + case _ => stop = true; + } + } + target + } + + /* Return the binding for the given local. */ + def getBinding(l: Local): Value = { + var target = l; + var stop = false; + var value: Value = Deref(LocalVar(target)); + + while (bindings.isDefinedAt(LocalVar(target)) && !stop) { +// Console.println("finding binding for " + target); + value = bindings(LocalVar(target)); + value match { + case Deref(LocalVar(t)) => target = t; + case _ => stop = true; + } + } + value + } + + + + /* Return the binding for the given field of the given record */ + def getBinding(r: Record, f: Symbol): Value = { + assert(r.bindings.isDefinedAt(f), + "Record " + r + " does not contain a field " + f); + + var target: Value = r.bindings(f); + target match { + case Deref(LocalVar(sym)) => getBinding(sym) + case _ => target + } + } + + override def toString(): String = { + "\nBindings: " + bindings + "\nStack: " + stack; + } + + def dup: State = { + val b: Bindings = new HashMap(); + b ++= bindings; + new State(b, stack) + } + } + + type Elem = State; + + val top = new State(emptyBinding, Nil); + val bottom = new State(emptyBinding, Nil); + + def lub2(a: Elem, b: Elem): Elem = { + if (a eq bottom) b + else if (b eq bottom) a + else if (a == b) a + else { + assert(a.stack.length == b.stack.length, + "Invalid stacks in states: " + a + b); + val resStack = List.map2(a.stack, b.stack) { (v1, v2) => + if (v1 == v2) v1 else Unknown + } + val commonPairs = a.bindings.toList intersect (b.bindings.toList); + val resBindings = new HashMap[Location, Value]; + for (val Pair(k, v) <- commonPairs) + resBindings += k -> v; + new State(resBindings, resStack) + } + } + } + + final class CopyAnalysis extends DataFlowAnalysis[copyLattice.type] { + type P = BasicBlock; + val lattice = copyLattice; + + var method: IMethod = _; + + def init(m: IMethod): Unit = { + this.method = m; + + init { + worklist += m.code.startBlock; + worklist ++= (m.exh map (.startBlock)); + m.code.blocks.foreach { b => + in(b) = lattice.bottom; + out(b) = lattice.bottom; + } + m.exh foreach { e => + in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, Unknown :: Nil); + } + } + } + + override def run: Unit = { + forwardAnalysis(blockTransfer); + if (settings.debug.value) { + linearizer.linearize(method).foreach(b => if (b != method.code.startBlock) + assert(in(b) != lattice.bottom, + "Block " + b + " in " + this.method + " has input equal to bottom -- not visited?")); + } + } + + def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { + b.toList.foldLeft(in)(interpret) + } + + import opcodes._; + + /** Abstract interpretation for one instruction. */ + def interpret(in: copyLattice.Elem, i: Instruction): copyLattice.Elem = { + var out = in.dup; + + if (settings.debug.value) { + Console.println("- " + i); + Console.println("in: " + in); + Console.println("\n"); + } + + i match { + case THIS(_) => + out.stack = This :: out.stack; + + case CONSTANT(_) => + out.stack = Unknown :: out.stack; + + case LOAD_ARRAY_ITEM(_) => + out.stack = (Unknown :: out.stack.drop(2)); + + case LOAD_LOCAL(local) => + out.stack = Deref(LocalVar(local)) :: out.stack; + + case LOAD_FIELD(field, isStatic) => + if (isStatic) + out.stack = Unknown :: out.stack; /* ignore static fields */ + else { + val v1 = in.stack match { + case (r @ Record(cls, bindings)) :: xs => + Field(r, field) + + case _ => Unknown + } + out.stack = v1 :: out.stack.drop(1); + } + + case LOAD_MODULE(module) => + out.stack = Unknown :: out.stack; + + case STORE_ARRAY_ITEM(kind) => + out.stack = out.stack.drop(3); + + case STORE_LOCAL(local) => + cleanReferencesTo(out, local.sym); + in.stack match { + case Unknown :: xs => (); + case v :: vs => + v match { + case Deref(LocalVar(other)) => + if (other != local) + out.bindings += LocalVar(local) -> v; + case _ => + out.bindings += LocalVar(local) -> v; + } + } + out.stack = out.stack drop 1; + + case STORE_FIELD(field, isStatic) => + if (isStatic) + out.stack = out.stack.drop(1); + else { + out.stack = out.stack.drop(2); + cleanReferencesTo(out, field); + in.stack match { + case v :: Record(_, bindings) :: vs => + bindings += field -> v; + case _ => (); + } + } + + case CALL_PRIMITIVE(primitive) => + out.stack = Unknown :: out.stack.drop(i.consumed); + + case CALL_METHOD(method, style) => style match { + case Dynamic => + out = simulateCall(in, method, false); + + case Static(onInstance) => + if (onInstance) { + val obj = out.stack.drop(method.info.paramTypes.length).head; + if (method.isConstructor) { + obj match { + case Record(_, bindings) => + for (val v <- out.stack.take(method.info.paramTypes.length + 1); + v ne obj) { + bindings ++= getBindingsForClosure(in, method); + } + case _ => () + } + // put the Record back on the stack and remove the 'returned' value + out.stack = out.stack.drop(1 + method.info.paramTypes.length); + } else + out = simulateCall(in, method, false); + } else + out = simulateCall(in, method, true); + + case SuperCall(_) => + out = simulateCall(in, method, false); + } + + case NEW(kind) => + val v1 = + kind match { + case REFERENCE(cls) => + if (isClosureClass(cls)) + Record(cls, new HashMap[Symbol, Value]) + else Unknown + + case _ => + Unknown + } + out.stack = v1 :: out.stack + + case CREATE_ARRAY(elem) => + out.stack = Unknown :: out.stack.drop(1); + + case IS_INSTANCE(tpe) => + out.stack = Unknown :: out.stack.drop(1); + + case CHECK_CAST(tpe) => + out.stack = Unknown :: out.stack.drop(1); + + case SWITCH(tags, labels) => + out.stack = out.stack.drop(1); + + case JUMP(where) => + () + + case CJUMP(success, failure, cond, kind) => + out.stack = out.stack.drop(2); + + case CZJUMP(success, failure, cond, kind) => + out.stack = out.stack.drop(1); + + case RETURN(kind) => + if (kind != UNIT) + out.stack = out.stack.drop(1); + + case THROW() => + out.stack = out.stack.drop(1); + + case DROP(kind) => + out.stack = out.stack.drop(1); + + case DUP(kind) => + out.stack = out.stack.head :: out.stack; + + case MONITOR_ENTER() => + out.stack = out.stack.drop(1); + + case MONITOR_EXIT() => + out.stack = out.stack.drop(1); + + case _ => + dump; + abort("Unknown instruction: " + i); + } + out + } /* def interpret */ + + /** Remove all references to this local variable from both stack + * and bindings. It is called when a new assignment destroys + * previous copy-relations. + */ + final def cleanReferencesTo(s: copyLattice.State, sym: Symbol): Unit = { + def cleanRecord(r: Record): Record = { + r.bindings filter { (loc, value) => + value match { + case Deref(LocalVar(sym1)) if (sym1 == sym) => false + case Field(_, sym1) if (sym1 == sym) => false + case _ => true + } + } + r + } + + s.stack = s.stack map { v => v match { + case Record(_, bindings) => + cleanRecord(v.asInstanceOf[Record]) + case _ => v + }} + + s.bindings filter { (loc, value) => + value match { + case Deref(LocalVar(sym1)) if (sym1 == sym) => false + case Field(_, sym1) if (sym1 == sym) => false + case Record(_, _) => + cleanRecord(value.asInstanceOf[Record]); + true + case _ => true + } + } + } + + /** Update the state 's' after the call to 'method'. The stack elements are dropped and replaced + * by the result of the call. If the method is impure, all bindings to record fields are cleared. + */ + final def simulateCall(s: copyLattice.State, method: Symbol, static: Boolean): copyLattice.State = { +// if (static) +// Console.println("Method type is: " + method.info); + + val out = new copyLattice.State(s.bindings, s.stack); + out.stack = out.stack.drop(method.info.paramTypes.length + (if (static) 0 else 1)); +// if (static) +// Console.println("Stack after drops: " + out.stack); + if (method.info.resultType != definitions.UnitClass.tpe) + out.stack = Unknown :: out.stack; +// if (static) +// Console.println("Stack after return type: " + out.stack); + if (!isPureMethod(method)) + invalidateRecords(out); + out + } + + /** Drop everything known about record fields. */ + final def invalidateRecords(s: copyLattice.State): Unit = { + s.stack = s.stack map { v => v match { + case Record(cls, bindings) => + Record(cls, new HashMap[Symbol, Value]); + case _ => v + }} + + s.bindings filter { (loc, value) => + value match { + case Field(_, _) => false + case _ => true + } + } + } + + /** + * Return bindings from closure's fields to the values on the stack. This + * method has to find the correct mapping from fields to the order in which + * they are passed on the stack. + */ + private def getBindingsForClosure(in: copyLattice.State, ctor: Symbol): Map[Symbol, Value] = { + val paramAccessors = ctor.owner.constrParamAccessors; + var values = in.stack.take(1 + ctor.info.paramTypes.length).reverse.drop(1); + val bindings = new HashMap[Symbol, Value]; + + // this relies on having the same order in paramAccessors and + // the arguments on the stack. It should be the same! + for (val p <- paramAccessors) { + bindings += p -> values.head; + values = values.tail; + } + + bindings + } + + /** Is `cls' a closure class? */ + final def isClosureClass(cls: Symbol): Boolean = + cls.isFinal && + cls.tpe.parents.exists { t => + val TypeRef(_, sym, _) = t; + definitions.FunctionClass exists sym.== + } + + /** Is `m' a pure method? */ + final def isPureMethod(m: Symbol): Boolean = + m.isGetter; + + final override def toString(): String = { + var res = ""; + for (val b <- this.method.code.blocks.toList) + res = (res + "\nIN(" + b.label + "):\t Bindings: " + in(b).bindings + + "\nIN(" + b.label +"):\t Stack: " + in(b).stack) + "\n"; + res + } + + } /* class CopyAnalysis */ +} 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 91b4ee4e68..39fa5d2a32 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -163,7 +163,7 @@ abstract class TypeFlowAnalysis { val Pair(INT, ARRAY(elem)) = stack.pop2; stack.push(elem); - case LOAD_LOCAL(local, isArg) => + case LOAD_LOCAL(local) => val t = bindings(local); stack push (if (t == typeLattice.bottom) local.kind else t); @@ -178,7 +178,7 @@ abstract class TypeFlowAnalysis { case STORE_ARRAY_ITEM(kind) => stack.pop3; - case STORE_LOCAL(local, isArg) => + case STORE_LOCAL(local) => val t = stack.pop; bindings += local -> t; diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index 979f94f75c..2fdbadf2fd 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -457,11 +457,8 @@ abstract class GenJVM extends SubComponent { case LOAD_ARRAY_ITEM(kind) => jcode.emitALOAD(javaType(kind)); - case LOAD_LOCAL(local, isArg) => - if (isArg) - jcode.emitLOAD(indexOf(local), javaType(local.kind)); - else - jcode.emitLOAD(indexOf(local), javaType(local.kind)); + case LOAD_LOCAL(local) => + jcode.emitLOAD(indexOf(local), javaType(local.kind)); case LOAD_FIELD(field, isStatic) => var owner = javaName(field.owner); @@ -489,11 +486,8 @@ abstract class GenJVM extends SubComponent { case STORE_ARRAY_ITEM(kind) => jcode.emitASTORE(javaType(kind)); - case STORE_LOCAL(local, isArg) => - if (isArg) - jcode.emitSTORE(indexOf(local), javaType(local.kind)); - else - jcode.emitSTORE(indexOf(local), javaType(local.kind)); + case STORE_LOCAL(local) => + jcode.emitSTORE(indexOf(local), javaType(local.kind)); case STORE_FIELD(field, isStatic) => val owner = javaName(field.owner); // + (if (field.owner.hasFlag(Flags.MODULE)) "$" else ""); diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala new file mode 100644 index 0000000000..414f51365f --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala @@ -0,0 +1,179 @@ +/* NSC -- new scala compiler + * Copyright 2005 LAMP/EPFL + * @author Iulian Dragos + */ + +// $Id: $ + +package scala.tools.nsc.backend.opt; + +import scala.collection.mutable.{Map, HashMap}; +import scala.tools.nsc.symtab._; + +/** + */ +abstract class ClosureElimination extends SubComponent { + import global._; + import icodes._; + import icodes.opcodes._; + + val phaseName = "closurelim"; + + /** Create a new phase */ + override def newPhase(p: Phase) = new ClosureEliminationPhase(p); + + /** The Inlining phase. + */ + class ClosureEliminationPhase(prev: Phase) extends GlobalPhase(prev) { + def name = phaseName; + override def newFlags = phaseNewFlags; + + override def erasedTypes = true; + val closser = new ClosureElim; + + override def run: Unit = { + if (settings.debug.value) inform("[running phase " + name + " on icode]"); + classes.values foreach closser.analyzeClass; + } + override def apply(unit: CompilationUnit): Unit = + abort("Inlining works on icode classes, not on compilation units!"); + } + + /** + * Remove references to the environemnt through fields of a closure object. + * This has to be run after an 'apply' method has been inlined, but it still + * references the closure object. + * + */ + class ClosureElim { + + /* fresh name counter */ + var count = 0; + + def freshName(s: String) = { + val ret = s + this.count; + this.count = this.count + 1; + ret + } + + def analyzeClass(cls: IClass): Unit = if (settings.Xcloselim.value) { + if (settings.debug.value) + log("Analyzing " + cls); + cls.methods.foreach { m => analyzeMethod(m) + }} + + + val cpp = new copyPropagation.CopyAnalysis; + + + import copyPropagation._; + + /* Some embryonic copy propagation. */ + def analyzeMethod(m: IMethod): Unit = if (m.code ne null) { + Console.println("Analyzing " + m); + cpp.init(m); + cpp.run; + + for (val bb <- linearizer.linearize(m)) { + var info = cpp.in(bb); + + for (val i <- bb.toList) { + i match { + case LOAD_LOCAL(l) if (info.bindings.isDefinedAt(LocalVar(l))) => + val t = info.getBinding(l); + t match { + case Deref(LocalVar(v)) => + bb.replaceInstruction(i, valueToInstruction(t)); + Console.println("replaced " + i + " with " + t); + + case This() => + bb.replaceInstruction(i, valueToInstruction(t)); + Console.println("replaced " + i + " with " + t); + + case _ => + bb.replaceInstruction(i, LOAD_LOCAL(info.getAlias(l))); + Console.println("replaced " + i + " with " + info.getAlias(l)); + + } + + case LOAD_FIELD(f, false) => + Console.println(" * * * \n" + i + "\n" + info); + + info.stack(0) match { + case r @ Record(cls, bindings) if bindings.isDefinedAt(f) => + bb.replaceInstruction(i, + DROP(REFERENCE(cls)) :: + valueToInstruction(info.getBinding(r, f)) :: Nil); + Console.println("Replaced " + i + " with " + info.getBinding(r, f)); + + case Deref(LocalVar(l)) => + info.getBinding(l) match { + case r @ Record(cls, bindings) if bindings.isDefinedAt(f) => + bb.replaceInstruction(i, + DROP(REFERENCE(cls)) :: + valueToInstruction(info.getBinding(r, f)) :: Nil); + Console.println("Replaced " + i + " with " + info.getBinding(r, f)); + case _ => (); + } + Console.println(info.getBinding(l)); + + case _ => (); + } + + case _ => (); + } + info = cpp.interpret(info, i); + } + } + } + + /* Partial mapping from values to instructions that load them. */ + def valueToInstruction(v: Value): Instruction = v match { + case Deref(LocalVar(v)) => + LOAD_LOCAL(v) + + case This() => + THIS(definitions.ObjectClass) + } + + } /* class ClosureElim */ + + + /** Peephole optimization. */ +/* class PeepholeOpt(f: (Instruction, Instruction) => List[Instruction]) { + + private var method: IMethod = null; + + def transformMethod(m: IMethod): Unit = if (m.code ne null) { + method = m; + for (val b <- m.code.blocks) + transformBlock(b); + } + + def transformBlock(b: BasicBlock): Unit = { + var newInstructions: List[Instruction] = Nil; + var first: Instruction = null; + var second: Instruction = null; + + def emit(i: Instruction) = { + if (first == null) + first = i; + else if (second == null) + second = i + else { + newInstructions = second :: newInstructions; + first = second; + second = i; + } + } + + for (val i <- b.toList) { + if (first && second) { + first = null; second = null; + f(first, second) foreach emit; + } + } + } + } +*/ +} /* class ClosureElimination */ diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 62692cdec9..ef17fc478a 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -78,12 +78,12 @@ abstract class Inliners extends SubComponent { assert(!instrAfter.isEmpty, "CALL_METHOD cannot be the last instrcution in block!"); // store the '$this' into the special local - val inlinedThis = new Local(caller.symbol.newVariable(instr.pos, freshName("$inlThis")), REFERENCE(definitions.ObjectClass)); + val inlinedThis = new Local(caller.symbol.newVariable(instr.pos, freshName("$inlThis")), REFERENCE(definitions.ObjectClass), false); /** buffer for the returned value */ val retVal = if (callee.returnType != UNIT) - new Local(caller.symbol.newVariable(instr.pos, freshName("$retVal")), callee.returnType); + new Local(caller.symbol.newVariable(instr.pos, freshName("$retVal")), callee.returnType, false); else null; @@ -106,13 +106,7 @@ abstract class Inliners extends SubComponent { /** Map an instruction from the callee to one suitable for the caller. */ def map(i: Instruction): Instruction = i match { case THIS(clasz) => - LOAD_LOCAL(inlinedThis, false); - - case LOAD_LOCAL(local, isArg) if (isArg) => - LOAD_LOCAL(local, false); - - case STORE_LOCAL(local, isArg) if (isArg) => - STORE_LOCAL(local, false); + LOAD_LOCAL(inlinedThis); case JUMP(where) => JUMP(inlinedBlock(where)); @@ -150,9 +144,9 @@ abstract class Inliners extends SubComponent { // store the arguments into special locals callee.params.reverse.foreach { param => - block.emit(STORE_LOCAL(param, false)); + block.emit(STORE_LOCAL(param)); } - block.emit(STORE_LOCAL(inlinedThis, false)); + block.emit(STORE_LOCAL(inlinedThis)); // jump to the start block of the callee block.emit(JUMP(inlinedBlock(callee.code.startBlock))); @@ -165,16 +159,14 @@ abstract class Inliners extends SubComponent { i match { case RETURN(kind) => kind match { case UNIT => - if (!info._2.types.isEmpty) { - log("** Dumping useless stack elements"); - info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t)); } + if (!info._2.types.isEmpty) { + info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t)); } } case _ => if (info._2.length > 1) { - log("** Dumping useless stack elements"); - inlinedBlock(bb).emit(STORE_LOCAL(retVal, false)); + inlinedBlock(bb).emit(STORE_LOCAL(retVal)); info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t)); } - inlinedBlock(bb).emit(LOAD_LOCAL(retVal, false)); + inlinedBlock(bb).emit(LOAD_LOCAL(retVal)); } } case _ => (); @@ -198,17 +190,18 @@ abstract class Inliners extends SubComponent { * necessary because we use symbols to refer to locals. */ def addLocals(m: IMethod, ls: List[Local]): Unit = { - m.locals = m.locals ::: ls; + m.locals = m.locals ::: ls map { l => new Local(l.sym, l.kind, false) }; } def addLocal(m: IMethod, l: Local): Unit = - m.locals = m.locals ::: List(l); + addLocals(m, List(l)); val InlineAttr = if (settings.inline.value) global.definitions.getClass("scala.inline").tpe else null; def analyzeClass(cls: IClass): Unit = if (settings.inline.value) { + if (settings.debug.value) log("Analyzing " + cls); - cls.methods.foreach { m => analyzeMethod(m) + cls.methods.foreach { m => analyzeMethod(m) }} @@ -239,7 +232,8 @@ abstract class Inliners extends SubComponent { var concreteMethod = msym; if (receiver != msym.owner && receiver != NoSymbol) { concreteMethod = msym.overridingSymbol(receiver); - log("" + i + " has actual receiver: " + receiver); + if (settings.debug.value) + log("" + i + " has actual receiver: " + receiver); } if ( classes.contains(receiver) @@ -249,9 +243,7 @@ abstract class Inliners extends SubComponent { classes(receiver).lookupMethod(concreteMethod) match { case Some(inc) => if (inc != m && (inc.code ne null) - && { - val res = isSafeToInline(m, inc, info._2) - log("isSafeToInline: " + inc + " " + res); res }) { + && isSafeToInline(m, inc, info._2)) { retry = true; count = count + 1; inline(m, bb, i, inc); @@ -261,7 +253,7 @@ abstract class Inliners extends SubComponent { callsPrivate -= m; } case None => - log("Couldn't find " + msym.name); + (); } } @@ -316,7 +308,8 @@ abstract class Inliners extends SubComponent { case LOAD_FIELD(f, _) => if (f.hasFlag(Flags.PRIVATE)) if (f.hasFlag(Flags.SYNTHETIC) || f.hasFlag(Flags.PARAMACCESSOR)) { - log("Making not-private symbol out of synthetic: " + f); + if (settings.debug.value) + log("Making not-private symbol out of synthetic: " + f); f.setFlag(Flags.notPRIVATE) } else callsPrivateMember = true; @@ -324,7 +317,8 @@ abstract class Inliners extends SubComponent { case STORE_FIELD(f, _) => if (f.hasFlag(Flags.PRIVATE)) if (f.hasFlag(Flags.SYNTHETIC) || f.hasFlag(Flags.PARAMACCESSOR)) { - log("Making not-private symbol out of synthetic: " + f); + if (settings.debug.value) + log("Making not-private symbol out of synthetic: " + f); f.setFlag(Flags.notPRIVATE) } else callsPrivateMember = true; |