diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2006-05-19 14:57:06 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2006-05-19 14:57:06 +0000 |
commit | 6870553effc28cc2fbedb97b69393e1e3fb467f5 (patch) | |
tree | 00e37ca155f873cbfd4f2466f1b224b502ba3352 | |
parent | ef2de304b1cafdf7bc4f0230f73ed084455fa450 (diff) | |
download | scala-6870553effc28cc2fbedb97b69393e1e3fb467f5.tar.gz scala-6870553effc28cc2fbedb97b69393e1e3fb467f5.tar.bz2 scala-6870553effc28cc2fbedb97b69393e1e3fb467f5.zip |
Fixed some problems with the closure eliminatio...
Fixed some problems with the closure elimination phase.
6 files changed, 168 insertions, 92 deletions
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 4de2e24014..242c9e96fe 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala @@ -15,14 +15,15 @@ abstract class CopyPropagation { /** Locations can be local variables. */ abstract sealed class Location; case class LocalVar(l: Local) extends Location; + case class Field(r: Record, sym: Symbol) 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; + object AllRecords extends Record(NoSymbol, new HashMap[Symbol, Value]); /** The lattice for this analysis. */ object copyLattice extends CompleteLattice { @@ -51,7 +52,6 @@ abstract class CopyPropagation { 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; @@ -112,8 +112,8 @@ abstract class CopyPropagation { 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); + if (a.stack.length != b.stack.length) + throw new LubError(a, b, "Invalid stacks in states: "); val resStack = List.map2(a.stack, b.stack) { (v1, v2) => if (v1 == v2) v1 else Unknown } @@ -145,6 +145,9 @@ abstract class CopyPropagation { m.exh foreach { e => in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, Unknown :: Nil); } + + // first block is special: it's not bottom, but a precisely defined state with no bindings + in(m.code.startBlock) = new lattice.State(lattice.emptyBinding, Nil); } } @@ -168,17 +171,18 @@ abstract class CopyPropagation { var out = in.dup; if (settings.debug.value) { - Console.println("- " + i); - Console.println("in: " + in); - Console.println("\n"); + log("- " + i); + log("in: " + in); + log("\n"); } i match { case THIS(_) => out.stack = This :: out.stack; - case CONSTANT(_) => - out.stack = Unknown :: out.stack; + case CONSTANT(k) => + if (k.tag != UnitTag) + out.stack = Unknown :: out.stack; case LOAD_ARRAY_ITEM(_) => out.stack = (Unknown :: out.stack.drop(2)); @@ -192,7 +196,7 @@ abstract class CopyPropagation { else { val v1 = in.stack match { case (r @ Record(cls, bindings)) :: xs => - Field(r, field) + Deref(Field(r, field)) case _ => Unknown } @@ -206,7 +210,7 @@ abstract class CopyPropagation { out.stack = out.stack.drop(3); case STORE_LOCAL(local) => - cleanReferencesTo(out, local.sym); + cleanReferencesTo(out, LocalVar(local)); in.stack match { case Unknown :: xs => (); case v :: vs => @@ -225,7 +229,7 @@ abstract class CopyPropagation { out.stack = out.stack.drop(1); else { out.stack = out.stack.drop(2); - cleanReferencesTo(out, field); + cleanReferencesTo(out, Field(AllRecords, field)); in.stack match { case v :: Record(_, bindings) :: vs => bindings += field -> v; @@ -327,12 +331,11 @@ abstract class CopyPropagation { * and bindings. It is called when a new assignment destroys * previous copy-relations. */ - final def cleanReferencesTo(s: copyLattice.State, sym: Symbol): Unit = { + final def cleanReferencesTo(s: copyLattice.State, target: Location): 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 Deref(loc1) if (loc1 == target) => false case _ => true } } @@ -346,14 +349,17 @@ abstract class CopyPropagation { }} s.bindings filter { (loc, value) => - value match { - case Deref(LocalVar(sym1)) if (sym1 == sym) => false - case Field(_, sym1) if (sym1 == sym) => false + (value match { + case Deref(loc1) if (loc1 == target) => false case Record(_, _) => cleanRecord(value.asInstanceOf[Record]); true case _ => true - } + }) && + (loc match { + case l: Location if (l == target) => false + case _ => true + }) } } @@ -361,17 +367,10 @@ abstract class CopyPropagation { * 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 @@ -387,7 +386,7 @@ abstract class CopyPropagation { s.bindings filter { (loc, value) => value match { - case Field(_, _) => false + case Deref(Field(_, _)) => false case _ => true } } 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 93d265caac..4c18086d13 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -37,7 +37,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] { succs foreach { p => if (!worklist.contains(p)) worklist += p; - in(p) = lattice.lub(p.predecessors map out.apply) + in(p) = lattice.lub(in(p) :: (p.predecessors map out.apply)) } } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala new file mode 100644 index 0000000000..0271f8ebea --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/LubError.scala @@ -0,0 +1,5 @@ +package scala.tools.nsc.backend.icode.analysis; + +class LubError(a: Any, b: Any, msg: String) extends Exception { + override def toString() = "Lub error: " + msg + a + b; +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index 03c45cef94..4a6d1b2c4e 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -541,6 +541,18 @@ abstract class GenJVM extends SubComponent { var crtPC = 0; b traverse ( instr => { + class CompilationError(msg: String) extends Error { + override def toString(): String = { + msg + + "\nCurrent method: " + method + + "\nCurrent block: " + b + + "\nCurrent instruction: " + instr + + "\n---------------------" + + dump(method) + } + } + def assert(cond: Boolean, msg: String) = if (!cond) throw new CompilationError(msg); + if (b.lastInstruction == instr) endPC(b) = jcode.getPC(); @@ -816,7 +828,9 @@ abstract class GenJVM extends SubComponent { crtPC = jcode.getPC(); val crtLine = try { clasz.cunit.position(instr.pos).line; } catch { - case _: Error => lastLineNr; + case _: Error => + log("Warning: wrong position in: " + method); + lastLineNr; } //System.err.println("CRTLINE: " + instr.pos + " " + // /* (if (instr.pos < clasz.cunit.source.content.length) clasz.cunit.source.content(instr.pos) else '*') + */ " " + crtLine); @@ -1044,13 +1058,13 @@ abstract class GenJVM extends SubComponent { def indexOf(m: IMethod, sym: Symbol): Int = { val Some(local) = m.lookupLocal(sym); assert (local.index >= 0, - "Invalid index for: " + local); + "Invalid index for: " + local + "{" + local.hashCode + "}"); local.index } def indexOf(local: Local): Int = { assert (local.index >= 0, - "Invalid index for: " + local); + "Invalid index for: " + local + "{" + local.hashCode + "}"); local.index } @@ -1065,7 +1079,7 @@ abstract class GenJVM extends SubComponent { for (val l <- m.locals) { if (settings.debug.value) - log("Index value for " + l + ": " + idx); + log("Index value for " + l + "{" + l.hashCode + "}: " + idx); l.index = idx; idx = idx + sizeOf(l.kind); } @@ -1204,5 +1218,12 @@ abstract class GenJVM extends SubComponent { lvTab.array()); jcode.addAttribute(attr); } + + def assert(cond: Boolean, msg: String) = if (!cond) { + dump(method); + throw new Error(msg + "\nMethod: " + method) + } + + def assert(cond: Boolean): Unit = assert(cond, "Assertion failed."); } } diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala index 414f51365f..f13eb65832 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala @@ -1,4 +1,4 @@ -/* NSC -- new scala compiler + /* NSC -- new scala compiler * Copyright 2005 LAMP/EPFL * @author Iulian Dragos */ @@ -8,6 +8,7 @@ package scala.tools.nsc.backend.opt; import scala.collection.mutable.{Map, HashMap}; +import scala.tools.nsc.backend.icode.analysis.LubError; import scala.tools.nsc.symtab._; /** @@ -56,10 +57,34 @@ abstract class ClosureElimination extends SubComponent { ret } + /** A simple peephole optimizer. */ + val peephole = new PeepholeOpt( (i1, i2) => + Pair(i1, i2) match { + case Pair(CONSTANT(c), DROP(_)) => + if (c.tag == UnitTag) + Some(List(i2)) + else + Some(Nil); + + case Pair(LOAD_LOCAL(x), STORE_LOCAL(y)) => + if (x eq y) Some(Nil) else None + + case Pair(LOAD_LOCAL(_), DROP(_)) => + Some(Nil) + + case Pair(LOAD_FIELD(sym, isStatic), DROP(_)) => + if (isStatic) + Some(Nil) + else + Some(DROP(REFERENCE(definitions.ObjectClass)) :: Nil); + + case _ => None; + }); + def analyzeClass(cls: IClass): Unit = if (settings.Xcloselim.value) { - if (settings.debug.value) - log("Analyzing " + cls); - cls.methods.foreach { m => analyzeMethod(m) + cls.methods.foreach { m => + analyzeMethod(m); + peephole.transformMethod(m); }} @@ -69,8 +94,8 @@ abstract class ClosureElimination extends SubComponent { import copyPropagation._; /* Some embryonic copy propagation. */ - def analyzeMethod(m: IMethod): Unit = if (m.code ne null) { - Console.println("Analyzing " + m); + def analyzeMethod(m: IMethod): Unit = try {if (m.code ne null) { + log("Analyzing " + m); cpp.init(m); cpp.run; @@ -84,27 +109,25 @@ abstract class ClosureElimination extends SubComponent { t match { case Deref(LocalVar(v)) => bb.replaceInstruction(i, valueToInstruction(t)); - Console.println("replaced " + i + " with " + t); + log("replaced " + i + " with " + t); case This() => bb.replaceInstruction(i, valueToInstruction(t)); - Console.println("replaced " + i + " with " + t); + log("replaced " + i + " with " + t); case _ => bb.replaceInstruction(i, LOAD_LOCAL(info.getAlias(l))); - Console.println("replaced " + i + " with " + info.getAlias(l)); + log("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)); + log("Replaced " + i + " with " + info.getBinding(r, f)); case Deref(LocalVar(l)) => info.getBinding(l) match { @@ -112,10 +135,9 @@ abstract class ClosureElimination extends SubComponent { bb.replaceInstruction(i, DROP(REFERENCE(cls)) :: valueToInstruction(info.getBinding(r, f)) :: Nil); - Console.println("Replaced " + i + " with " + info.getBinding(r, f)); + log("Replaced " + i + " with " + info.getBinding(r, f)); case _ => (); } - Console.println(info.getBinding(l)); case _ => (); } @@ -125,6 +147,10 @@ abstract class ClosureElimination extends SubComponent { info = cpp.interpret(info, i); } } + }} catch { + case e: LubError => + Console.println("In method: " + m); + Console.println(e); } /* Partial mapping from values to instructions that load them. */ @@ -140,7 +166,7 @@ abstract class ClosureElimination extends SubComponent { /** Peephole optimization. */ -/* class PeepholeOpt(f: (Instruction, Instruction) => List[Instruction]) { + class PeepholeOpt(peep: (Instruction, Instruction) => Option[List[Instruction]]) { private var method: IMethod = null; @@ -150,30 +176,34 @@ abstract class ClosureElimination extends SubComponent { transformBlock(b); } - def transformBlock(b: BasicBlock): Unit = { + def transformBlock(b: BasicBlock): Unit = if (b.size >= 2) { 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; + newInstructions = b.toList; + + var redo = false; + do { + var h = newInstructions.head; + var t = newInstructions.tail; + var seen: List[Instruction] = Nil; + redo = false; + + while (t != Nil) { + peep(h, t.head) match { + case Some(newInstrs) => + Console.println("Replacing " + h + " : " + t.head + " by " + newInstrs); + newInstructions = seen.reverse ::: newInstrs ::: t.tail; + redo = true; + case None => + () + } + seen = h :: seen; + h = t.head; + t = t.tail; } - } + } while (redo); + b.fromList(newInstructions); } } -*/ + } /* 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 ef17fc478a..004969c3c5 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -61,9 +61,10 @@ abstract class Inliners extends SubComponent { block: BasicBlock, instr: Instruction, callee: IMethod): Unit = { - log("Inlining " + callee + " in " + caller + " at pos: " + - classes(caller.symbol.owner).cunit.position(instr.pos)); +// log("Inlining " + callee + " in " + caller + " at pos: " + +// classes(caller.symbol.owner).cunit.position(instr.pos)); + val targetPos = instr.pos; val a = new analysis.MethodTFA(callee); /* The exception handlers that are active at the current block. */ @@ -72,6 +73,9 @@ abstract class Inliners extends SubComponent { /* Map 'original' blocks to the ones inlined in the caller. */ val inlinedBlock: Map[BasicBlock, BasicBlock] = new HashMap; + /* Map callee's parameters to inlined local variables. */ + val argsToLocal: Map[Local, Local] = new HashMap; + val instrBefore = block.toList.takeWhile( i => i ne instr); val instrAfter = block.toList.drop(instrBefore.length + 1); @@ -101,6 +105,23 @@ abstract class Inliners extends SubComponent { handler } + /** Adds parameters from another method as locals */ + def addParamsAsLocals(m: IMethod, ls: List[Local]): Unit = { + m.locals = m.locals ::: (ls map { a => + if (a.arg) { + val l = new Local(a.sym, a.kind, false); + argsToLocal += a -> l; + l + } else + a + }); + } + + def addLocals(m: IMethod, ls: List[Local]) = + m.locals = m.locals ::: ls; + def addLocal(m: IMethod, l: Local): Unit = + addLocals(m, List(l)); + val afterBlock = newBlock; /** Map an instruction from the callee to one suitable for the caller. */ @@ -123,6 +144,14 @@ abstract class Inliners extends SubComponent { case RETURN(kind) => JUMP(afterBlock); + case LOAD_LOCAL(l) if (argsToLocal.isDefinedAt(l)) => + Console.println("Replacing load_local"); + LOAD_LOCAL(argsToLocal(l)) + + case STORE_LOCAL(l) if (argsToLocal.isDefinedAt(l)) => + Console.println("Replacing store_local"); + STORE_LOCAL(argsToLocal(l)) + case _ => i } @@ -140,16 +169,16 @@ abstract class Inliners extends SubComponent { // re-emit the instructions before the call block.open; block.clear; - instrBefore.foreach(block.emit); + instrBefore.foreach(i => block.emit(i, i.pos)); // store the arguments into special locals callee.params.reverse.foreach { param => - block.emit(STORE_LOCAL(param)); + block.emit(STORE_LOCAL(param), targetPos); } - block.emit(STORE_LOCAL(inlinedThis)); + block.emit(STORE_LOCAL(inlinedThis), targetPos); // jump to the start block of the callee - block.emit(JUMP(inlinedBlock(callee.code.startBlock))); + block.emit(JUMP(inlinedBlock(callee.code.startBlock)), targetPos); block.close; // duplicate the other blocks in the callee @@ -160,24 +189,24 @@ abstract class Inliners extends SubComponent { case RETURN(kind) => kind match { case UNIT => if (!info._2.types.isEmpty) { - info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t)); } + info._2.types foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); } } case _ => if (info._2.length > 1) { - inlinedBlock(bb).emit(STORE_LOCAL(retVal)); - info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t)); } - inlinedBlock(bb).emit(LOAD_LOCAL(retVal)); + inlinedBlock(bb).emit(STORE_LOCAL(retVal), targetPos); + info._2.types.drop(1) foreach { t => inlinedBlock(bb).emit(DROP(t), targetPos); } + inlinedBlock(bb).emit(LOAD_LOCAL(retVal), targetPos); } } case _ => (); } - inlinedBlock(bb).emit(map(i), 0); + inlinedBlock(bb).emit(map(i), targetPos); info = a.interpret(info, i); } inlinedBlock(bb).close; } - instrAfter.foreach(afterBlock.emit); + instrAfter.foreach(i => afterBlock.emit(i, i.pos)); afterBlock.close; count = count + 1; @@ -185,17 +214,6 @@ abstract class Inliners extends SubComponent { caller.exh = (callee.exh map translateExh) ::: caller.exh; } - - /** Add a local to this method, alfa-renaming is not - * necessary because we use symbols to refer to locals. - */ - def addLocals(m: IMethod, ls: List[Local]): Unit = { - m.locals = m.locals ::: ls map { l => new Local(l.sym, l.kind, false) }; - } - - def addLocal(m: IMethod, l: Local): Unit = - 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) { @@ -214,7 +232,7 @@ abstract class Inliners extends SubComponent { do { retry = false; if (m.code ne null) { - this.count = 0; +// this.count = 0; if (settings.debug.value) log("Analyzing " + m + " count " + count); tfa.init(m); @@ -262,9 +280,12 @@ abstract class Inliners extends SubComponent { info = tfa.interpret(info, i); }}}} } while (retry && count < 5); + normalize(m); } catch { case e => Console.println("############# Cought exception: " + e + " #################"); + Console.println("\nMethod: " + m + + "\nMethod owner: " + m.symbol.owner); e.printStackTrace(); dump(m); throw e; |