diff options
author | Iulian Dragos <jaguarul@gmail.com> | 2007-03-21 19:25:44 +0000 |
---|---|---|
committer | Iulian Dragos <jaguarul@gmail.com> | 2007-03-21 19:25:44 +0000 |
commit | 6a2134b1b056da1c32115b4ab87e11c7b78b53ab (patch) | |
tree | 21a7f25e9118098af611356f21b59f68a2e84fcc /src | |
parent | 1052ad2f1ea1d162f65c3e3663a54d44e5566578 (diff) | |
download | scala-6a2134b1b056da1c32115b4ab87e11c7b78b53ab.tar.gz scala-6a2134b1b056da1c32115b4ab87e11c7b78b53ab.tar.bz2 scala-6a2134b1b056da1c32115b4ab87e11c7b78b53ab.zip |
Major rewrite of optimization phases.
Diffstat (limited to 'src')
22 files changed, 616 insertions, 212 deletions
diff --git a/src/compiler/scala/tools/nsc/Settings.scala b/src/compiler/scala/tools/nsc/Settings.scala index ee02445fc6..a61d878258 100644 --- a/src/compiler/scala/tools/nsc/Settings.scala +++ b/src/compiler/scala/tools/nsc/Settings.scala @@ -120,6 +120,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 XO = BooleanSetting("-XO", "Optimize. implies -Xinline, -Xcloselim and -Xdce") val Xcloselim = BooleanSetting("-Xcloselim", "Perform closure elimination") val Xdce = BooleanSetting("-Xdce", "Perform dead code elimination") val Xwarndeadcode = BooleanSetting("-Xwarndeadcode", "Emit warnings for dead code") diff --git a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala index f56c50cfc5..2704345841 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/BasicBlocks.scala @@ -9,7 +9,7 @@ package scala.tools.nsc.backend.icode import compat.StringBuilder import scala.tools.nsc.ast._ -import scala.collection.mutable.{Map, Set, HashSet} +import scala.collection.mutable.{Map, Set, LinkedHashSet} import scala.tools.nsc.util.Position import scala.tools.nsc.backend.icode.analysis.ProgramPoint @@ -21,10 +21,12 @@ trait BasicBlocks requires ICodes { * either executed all, or none. No jumps * to/from the "middle" of the basic block are allowed. */ - class BasicBlock (theLabel: int, val code: Code) + class BasicBlock (theLabel: int, val method: IMethod) extends AnyRef with ProgramPoint[BasicBlock] { + def code = method.code + /** The label of the block */ val label = theLabel @@ -36,10 +38,13 @@ trait BasicBlocks requires ICodes { /** Is this block the head of a while? */ var loopHeader = false + /** Is this block the start block of an exception handler? */ + var exceptionHandlerHeader = false + /** Local variables that are in scope at entry of this basic block. Used * for debugging information. */ - var varsInScope: Set[Local] = HashSet.empty + var varsInScope: Set[Local] = new LinkedHashSet() /** ICode instructions, used as temporary storage while emitting code. * Once closed is called, only the `instrs' array should be used. @@ -59,6 +64,12 @@ trait BasicBlocks requires ICodes { instructionList } + /** return the underlying array of instructions */ + def getArray: Array[Instruction] = { + assert(closed) + instrs + } + def fromList(is: List[Instruction]): Unit = { instrs = toInstructionArray(is) closed = true @@ -123,32 +134,6 @@ trait BasicBlocks requires ICodes { None } - def findDefs(idx: Int, m: Int): List[(BasicBlock, Int)] = { - assert(closed) - var res: List[(BasicBlock, Int)] = Nil - var i = idx - var n = m - // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack" - var d = 0 - while (n > 0) { - i = i - 1 - val prod = instrs(i).produced - if (prod > d) { - res = (this, i) :: res - n = n - (prod - d) - } - d = d + (instrs(i).consumed - instrs(i).produced); - } - res - } - - def findDefs(bb: BasicBlock, d: Int, n: Int): List[(BasicBlock, Int)] = { - var i = bb.size - while (n > 0 && i > 0) { - - } - Nil - } /** Return the n-th instruction. */ def apply(n: Int): Instruction = @@ -226,6 +211,25 @@ trait BasicBlocks requires ICodes { changed } + /** Insert instructions in 'is' immediately after index 'idx'. */ + def insertAfter(idx: Int, is: List[Instruction]) { + assert(closed, "Instructions can be replaced only after the basic block is closed") + + var i = idx + 1 + if (i < instrs.length) { + val newInstrs = new Array[Instruction](instrs.length + is.length); + Array.copy(instrs, 0, newInstrs, 0, i) + var j = i + for (val x <- is) { + newInstrs(j) = x + j = j + 1 + } + if (i + 1 < instrs.length) + Array.copy(instrs, i + 1, newInstrs, j, instrs.length - i) + instrs = newInstrs; + } + } + /** Removes instructions found at the given positions. * * @param positions ... @@ -324,6 +328,7 @@ trait BasicBlocks requires ICodes { } def open = { + assert(closed) closed = false ignore = false instructionList = instructionList.reverse // prepare for appending to the head @@ -373,8 +378,8 @@ trait BasicBlocks requires ICodes { def isClosed = closed // TODO: Take care of exception handlers! - def successors : List[BasicBlock] = if (isEmpty) Nil else - lastInstruction match { + def successors : List[BasicBlock] = if (isEmpty) Nil else { + var res = lastInstruction match { case JUMP (where) => List(where) case CJUMP(success, failure, _, _) => success :: failure :: Nil case CZJUMP(success, failure, _, _) => success :: failure :: Nil @@ -388,6 +393,11 @@ trait BasicBlocks requires ICodes { } else Nil } + method.exh.foreach { e: ExceptionHandler => + if (e.covers(this)) res = e.startBlock :: res + } + res + } /** Returns the precessors of this block, in the current 'code' chunk. * This is signifficant only if there are exception handlers, which live @@ -399,7 +409,7 @@ trait BasicBlocks requires ICodes { } override def equals(other: Any): Boolean = other match { - case that: BasicBlock => that.label == label && that.code == code + case that: BasicBlock => (that.label == label) && (that.code == code) case _ => false } diff --git a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala b/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala index dd6a0a4487..43f6a8d3dd 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/ExceptionHandlers.scala @@ -26,7 +26,10 @@ trait ExceptionHandlers requires ICodes { var resultKind: TypeKind = _; - def setStartBlock(b: BasicBlock) = _startBlock = b; + def setStartBlock(b: BasicBlock) = { + _startBlock = b; + b.exceptionHandlerHeader = true + } def startBlock = _startBlock; /** The list of blocks that are covered by this exception handler */ diff --git a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala index 7276a7ff12..0dab705502 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/GenICode.scala @@ -507,9 +507,11 @@ abstract class GenICode extends SubComponent { (pat.symbol.tpe.symbol, kind, { ctx: Context => + if (settings.Xdce.value) + ctx.bb.emit(LOAD_EXCEPTION(), pat.pos) ctx.bb.emit(STORE_LOCAL(exception), pat.pos); - val ctx1 = genLoad(body, ctx, kind); - genLoad(finalizer, ctx1, UNIT); + val ctx1 = genLoad(body, ctx, kind); + genLoad(finalizer, ctx1, UNIT); }) } @@ -522,6 +524,8 @@ abstract class GenICode extends SubComponent { .setInfo(definitions.ThrowableClass.tpe), REFERENCE(definitions.ThrowableClass), false); ctx.method.addLocal(exception); + if (settings.Xdce.value) + ctx.bb.emit(LOAD_EXCEPTION()) ctx.bb.emit(STORE_LOCAL(exception)); val ctx1 = genLoad(finalizer, ctx, UNIT); ctx1.bb.emit(LOAD_LOCAL(exception)); @@ -541,6 +545,8 @@ abstract class GenICode extends SubComponent { val tmp = new Local(ctx.method.symbol.newVariable(tree.pos, unit.fresh.newName("tmp")).setInfo(tree.tpe).setFlag(Flags.SYNTHETIC), kind, false); ctx1.method.addLocal(tmp) + if (settings.Xdce.value) + ctx.bb.emit(LOAD_EXCEPTION()) ctx1.bb.emit(STORE_LOCAL(tmp)) val ctx2 = genLoad(duppedFinalizer, ctx1, UNIT) ctx2.bb.emit(LOAD_LOCAL(tmp)) @@ -571,7 +577,7 @@ abstract class GenICode extends SubComponent { else if (sym == definitions.Object_asInstanceOf) cast = true else - abort("Unexpected type application " + fun + "[sym: " + sym + "]") + abort("Unexpected type application " + fun + "[sym: " + sym.fullNameString + "]" + " in: " + tree) val Select(obj, _) = fun val l = toTypeKind(obj.tpe) @@ -642,11 +648,14 @@ abstract class GenICode extends SubComponent { case rt @ REFERENCE(cls) => assert(ctor.owner == cls, "Symbol " + ctor.owner.fullNameString + " is different than " + tpt) - ctx1.bb.emit(NEW(rt), tree.pos) + val nw = NEW(rt) + ctx1.bb.emit(nw, tree.pos) ctx1.bb.emit(DUP(generatedType)) ctx1 = genLoadArguments(args, ctor.info.paramTypes, ctx) - ctx1.bb.emit(CALL_METHOD(ctor, Static(true)), tree.pos) + val init = CALL_METHOD(ctor, Static(true)) + nw.init = init + ctx1.bb.emit(init, tree.pos) case _ => abort("Cannot instantiate " + tpt + "of kind: " + generatedType) @@ -797,6 +806,9 @@ abstract class GenICode extends SubComponent { if (settings.debug.value && hostClass != sym.owner) log("Set more precise host class for " + sym.fullNameString + " host: " + hostClass); ctx1.bb.emit(CALL_METHOD(sym, invokeStyle) setHostClass hostClass, tree.pos) + if (sym == ctx1.method.symbol) { + ctx1.method.recursive = true + } generatedType = if (sym.isClassConstructor) UNIT else toTypeKind(sym.info.resultType); @@ -1524,22 +1536,27 @@ abstract class GenICode extends SubComponent { if (settings.debug.value) log("Pruning empty if branch."); changed = true - assert(p.replaceInstruction(p.lastInstruction, + p.replaceInstruction(p.lastInstruction, if (block == succ) - CJUMP(cont, fail, cond, kind) + if (block == fail) + CJUMP(cont, cont, cond, kind) + else + CJUMP(cont, fail, cond, kind) else if (block == fail) CJUMP(succ, cont, cond, kind) else - abort("Could not find block in preds")), - "Didn't find p.lastInstruction") + abort("Could not find block in preds")) case CZJUMP(succ, fail, cond, kind) => if (settings.debug.value) - log("Pruning empty if branch."); + log("Pruning empty ifz branch."); changed = true p.replaceInstruction(p.lastInstruction, if (block == succ) - CZJUMP(cont, fail, cond, kind) + if (block == fail) + CZJUMP(cont, cont, cond, kind) + else + CZJUMP(cont, fail, cond, kind) else if (block == fail) CZJUMP(succ, cont, cond, kind) else @@ -1547,20 +1564,21 @@ abstract class GenICode extends SubComponent { case JUMP(b) => if (settings.debug.value) - log("Pruning empty if branch."); + log("Pruning empty JMP branch."); changed = true assert(p.replaceInstruction(p.lastInstruction, JUMP(cont)), "Didn't find p.lastInstruction") case SWITCH(tags, labels) => if (settings.debug.value) - log("Pruning empty if branch."); + log("Pruning empty SWITCH branch."); changed = true p.replaceInstruction(p.lastInstruction, SWITCH(tags, labels map (l => if (l == block) cont else l))) } } if (changed) { + log("Removing block: " + block) method.code.removeBlock(block); for (val e <- method.exh) { e.covered = e.covered filter (.!=(block)) @@ -1788,7 +1806,7 @@ abstract class GenICode extends SubComponent { def enterMethod(m: IMethod, d: DefDef): Context = { val ctx1 = new Context(this) setMethod(m) ctx1.labels = new HashMap() - ctx1.method.code = new Code(m.symbol.simpleName.toString()) + ctx1.method.code = new Code(m.symbol.simpleName.toString(), m) ctx1.bb = ctx1.method.code.startBlock ctx1.defdef = d ctx1.scope = EmptyScope diff --git a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala index 404ebd649f..b73b0db448 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/ICodes.scala @@ -60,7 +60,17 @@ abstract class ICodes extends AnyRef val global: ICodes.this.global.type = ICodes.this.global; } - def init = { } + var AnyRefReference: TypeKind = _ + def init = { + AnyRefReference = REFERENCE(global.definitions.AnyRefClass) + } + + import global.settings + if (settings.XO.value) { + settings.inline.value = true + settings.Xcloselim.value = true + settings.Xdce.value = true + } /** A phase which works on icode. */ abstract class ICodePhase(prev: Phase) extends global.GlobalPhase(prev) { diff --git a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala index c25dc4aa3b..dd60378bcd 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Linearizers.scala @@ -15,6 +15,7 @@ trait Linearizers requires ICodes { abstract class Linearizer { def linearize(c: IMethod): List[BasicBlock]; + def linearizeAt(c: IMethod, start: BasicBlock): List[BasicBlock] } /** @@ -44,6 +45,12 @@ trait Linearizers requires ICodes { blocks.reverse; } + def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { + blocks = Nil + worklist.clear + linearize(start) + } + /** Linearize another subtree and append it to the existing blocks. */ def linearize(startBlock: BasicBlock): List[BasicBlock] = { //blocks = startBlock :: Nil; @@ -102,6 +109,12 @@ trait Linearizers requires ICodes { blocks.reverse } + def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { + blocks = Nil + dfs(start) + blocks.reverse + } + def dfs(b: BasicBlock): Unit = if (b.size > 0 && add(b)) b.successors foreach dfs; @@ -144,6 +157,13 @@ trait Linearizers requires ICodes { m.code.startBlock :: (blocks.remove(.==(m.code.startBlock))) } + def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { + blocks = Nil + visited.clear + rpo(start) + blocks + } + def rpo(b: BasicBlock): Unit = if (b.size > 0 && !(visited contains b)) { visited += b; @@ -168,5 +188,10 @@ trait Linearizers requires ICodes { class DumpLinearizer extends Linearizer { def linearize(m: IMethod): List[BasicBlock] = m.code.blocks.toList; + + def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = { + error("not implemented") + } } + } diff --git a/src/compiler/scala/tools/nsc/backend/icode/Members.scala b/src/compiler/scala/tools/nsc/backend/icode/Members.scala index 6f01d7ce18..d3ecef16a8 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Members.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Members.scala @@ -10,7 +10,7 @@ package scala.tools.nsc.backend.icode; import java.io.PrintWriter; import scala.collection.mutable.HashMap; -import scala.collection.mutable.{Set, HashSet}; +import scala.collection.mutable.{Set, HashSet, ListBuffer}; import scala.{Symbol => scala_Symbol}; import scala.tools.nsc.symtab.Flags; @@ -22,10 +22,10 @@ trait Members requires ICodes { * This class represents the intermediate code of a method or * other multi-block piece of code, like exception handlers. */ - class Code(label: String) { + class Code(label: String, method: IMethod) { /** The set of all blocks */ - val blocks: HashSet[BasicBlock] = new HashSet; + val blocks: ListBuffer[BasicBlock] = new ListBuffer /** The start block of the method */ var startBlock: BasicBlock = null; @@ -41,7 +41,7 @@ trait Members requires ICodes { def removeBlock(b: BasicBlock) = { if (settings.debug.value) { assert(blocks.forall(p => !(p.successors.contains(b))), - "Removing block that is still referenced in method code " + label); + "Removing block that is still referenced in method code " + b + "preds: " + b.predecessors); if (b == startBlock) assert(b.successors.length == 1, "Removing start block with more than one successor."); @@ -74,7 +74,7 @@ trait Members requires ICodes { traverse0(startBlock :: Nil) } - def traverse(f: BasicBlock => Unit) = blocks foreach f; + def traverse(f: BasicBlock => Unit) = blocks.toList foreach f; /* This method applies the given function to each basic block. */ def traverseFeedBack(f: (BasicBlock, HashMap[BasicBlock, Boolean]) => Unit) = { @@ -110,7 +110,7 @@ trait Members requires ICodes { /* Create a new block and append it to the list */ def newBlock: BasicBlock = { - val block = new BasicBlock(nextLabel, this); + val block = new BasicBlock(nextLabel, method); blocks += block; block; } @@ -167,6 +167,8 @@ trait Members requires ICodes { var sourceFile: String = _; var returnType: TypeKind = _; + var recursive: Boolean = false + /** local variables and method parameters */ var locals: List[Local] = Nil; @@ -248,7 +250,8 @@ trait Members requires ICodes { succ ne b; succ.predecessors.length == 1; succ.predecessors.head eq b; - !(exh.contains { (e: ExceptionHandler) => e.covers(b) && !e.covers(succ) })) { + !(exh.exists { (e: ExceptionHandler) => + (e.covers(succ) && !e.covers(b)) || (e.covers(b) && !e.covers(succ)) })) { nextBlock(b) = succ } @@ -261,8 +264,9 @@ trait Members requires ICodes { succ = nextBlock(succ); bb.removeLastInstruction succ.toList foreach { i => bb.emit(i, i.pos) } - code.blocks -= succ + code.removeBlock(succ) nextBlock -= bb + exh foreach { e => e.covered = e.covered.remove { b1 => b1 == succ } } } while (nextBlock.isDefinedAt(succ)) bb.close } else diff --git a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala index c02f121ae0..4cd6c6312f 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Opcodes.scala @@ -39,6 +39,9 @@ import scala.tools.nsc.util.Position; case DUP(kind) => case MONITOR_ENTER() => case MONITOR_EXIT() => + case SCOPE_ENTER(lv) => + case SCOPE_EXIT(lv) => + case LOAD_EXCEPTION() => */ @@ -75,7 +78,7 @@ trait Opcodes requires ICodes { var pos: Int = Position.NOPOS; /** Used by dead code elimination. */ - var useful: Boolean = true + var useful: Boolean = false } object opcodes { @@ -296,28 +299,48 @@ trait Opcodes requires ICodes { case Dynamic => 1 case Static(true) => 1 case Static(false) => 0 - case SuperCall(_) => 0 + case SuperCall(_) => 1 }); result; } + + override def consumedTypes = { + val args = method.tpe.paramTypes map toTypeKind + style match { + case Dynamic | Static(true) => AnyRefReference :: args + case _ => args + } + } + override def produced = if(toTypeKind(method.tpe.resultType) == UNIT) 0 else if(method.isConstructor) 0 else 1 + + /** object idenity is equality for CALL_METHODs. Needed for + * being able to store such instructions into maps, when more + * than one CALL_METHOD to the same method might exist. + */ + override def equals(other: Any) = other match { + case o: AnyRef => this eq o + case _ => false + } } case class BOX(boxType: TypeKind) extends Instruction { override def toString(): String = "BOX " + boxType override def consumed = 1 + override def consumedTypes = boxType :: Nil override def produced = 1 } case class UNBOX(boxType: TypeKind) extends Instruction { override def toString(): String = "UNBOX " + boxType override def consumed = 1 + override def consumedTypes = AnyRefReference :: Nil override def produced = 1 } @@ -331,6 +354,9 @@ trait Opcodes requires ICodes { override def consumed = 0; override def produced = 1; + + /** The corresponding constructor call. */ + var init: CALL_METHOD = _ } @@ -343,6 +369,7 @@ trait Opcodes requires ICodes { override def toString(): String ="CREATE_ARRAY "+elem.toString(); override def consumed = 1; + override def consumedTypes = INT :: Nil override def produced = 1; } @@ -355,6 +382,7 @@ trait Opcodes requires ICodes { override def toString(): String ="IS_INSTANCE "+typ.toString(); override def consumed = 1; + override def consumedTypes = AnyRefReference :: Nil override def produced = 1; } @@ -368,7 +396,7 @@ trait Opcodes requires ICodes { override def consumed = 1; override def produced = 1; - override val consumedTypes = List(REFERENCE(global.definitions.ObjectClass)) + override val consumedTypes = List(AnyRefReference) override def producedTypes = List(typ) } @@ -535,6 +563,18 @@ trait Opcodes requires ICodes { override def produced = 0 } + /** Fake instruction. It designates the VM who pushes an exception + * on top of the /empty/ stack at the beginning of each exception handler. + * Note: Unlike other instructions, it consumes all elements on the stack! + * then pushes one exception instance. + */ + case class LOAD_EXCEPTION() extends Instruction { + override def toString(): String = "LOAD_EXCEPTION" + override def consumed = error("LOAD_EXCEPTION does clean the whole stack, no idea how many things it consumes!") + override def produced = 1 + override def producedTypes = AnyRefReference :: Nil + } + /** This class represents a method invocation style. */ sealed abstract class InvokeStyle { diff --git a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala index 06785a45ea..97fb9c2d21 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/Printers.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/Printers.scala @@ -124,8 +124,8 @@ trait Printers requires ICodes { } def printInstruction(i: Instruction): Unit = { -// if (settings.debug.value) -// print("/* " + Position.line(clazz.cunit.source, i.pos) + " */ "); + if (settings.Xdce.value) + print(if (i.useful) " " else " * "); println(i.toString()); } } diff --git a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala index a95865e13b..f9476842a0 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/TypeKinds.scala @@ -104,7 +104,11 @@ trait TypeKinds requires ICodes { else if (a == b) a else if (a == REFERENCE(definitions.AllClass)) b else if (b == REFERENCE(definitions.AllClass)) a - else throw new CheckerError("Incompatible types: " + a + " with " + b) + else (a, b) match { + case (BOXED(a1), BOXED(b1)) => if (a1 == b1) a else REFERENCE(definitions.AnyRefClass) + case (BOXED(_), REFERENCE(_)) | (REFERENCE(_), BOXED(_)) => REFERENCE(definitions.AnyRefClass) + case _ => throw new CheckerError("Incompatible types: " + a + " with " + b) + } } /** The unit value */ diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala index 3e0aa892d8..f124ea777f 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CompleteLattice.scala @@ -22,5 +22,11 @@ trait CompleteLattice { def bottom: Elem /** Compute the least upper bound of a list of elements. */ - def lub(xs: List[Elem]): Elem = if (xs == Nil) bottom else xs reduceLeft lub2 + def lub(xs: List[Elem]): Elem = try { + if (xs == Nil) bottom else xs reduceLeft lub2 + } catch { + case e: LubError => + Console.println("Lub on blocks: " + xs) + throw e + } } 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 8084a409fb..1bb33a5ca9 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/CopyPropagation.scala @@ -131,16 +131,30 @@ abstract class CopyPropagation { val top = new State(emptyBinding, Nil) val bottom = new State(emptyBinding, Nil) + val exceptionHandlerStack = Unknown :: 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 { - if (a.stack.length != b.stack.length) + val resStack = + if (a.stack eq exceptionHandlerStack) a.stack + else if (b.stack eq exceptionHandlerStack) b.stack + else { + if (a.stack.length != b.stack.length) + throw new LubError(a, b, "Invalid stacks in states: "); + List.map2(a.stack, b.stack) { (v1, v2) => + if (v1 == v2) v1 else Unknown + } + } + +/* 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 } + */ val commonPairs = a.bindings.toList intersect (b.bindings.toList) val resBindings = new HashMap[Location, Value] for (val Pair(k, v) <- commonPairs) @@ -165,9 +179,11 @@ abstract class CopyPropagation { m.code.blocks.foreach { b => in(b) = lattice.bottom out(b) = lattice.bottom + assert(out.contains(b)) + log("Added point: " + b) } m.exh foreach { e => - in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, Unknown :: Nil); + in(e.startBlock) = new copyLattice.State(copyLattice.emptyBinding, copyLattice.exceptionHandlerStack); } // first block is special: it's not bottom, but a precisely defined state with no bindings @@ -244,7 +260,7 @@ abstract class CopyPropagation { case _ => out.bindings += LocalVar(local) -> v; } - case Nil => error("Incorrect icode. Expecting something on the stack.") + case Nil => Predef.error("Incorrect icode in " + method + ". Expecting something on the stack.") } out.stack = out.stack drop 1; @@ -271,7 +287,8 @@ abstract class CopyPropagation { case Static(onInstance) => if (onInstance) { val obj = out.stack.drop(method.info.paramTypes.length).head - if (method.isPrimaryConstructor) { +// if (method.isPrimaryConstructor) { + if (method.isPrimaryConstructor/* && isClosureClass(method.owner)*/) { obj match { case Record(_, bindings) => for (val v <- out.stack.take(method.info.paramTypes.length + 1); @@ -353,6 +370,9 @@ abstract class CopyPropagation { case SCOPE_ENTER(_) | SCOPE_EXIT(_) => () + case LOAD_EXCEPTION() => + out.stack = Unknown :: Nil + case _ => dump abort("Unknown instruction: " + i) @@ -408,7 +428,7 @@ abstract class CopyPropagation { final def simulateCall(state: copyLattice.State, method: Symbol, static: Boolean): copyLattice.State = { val out = new copyLattice.State(state.bindings, state.stack); out.stack = out.stack.drop(method.info.paramTypes.length + (if (static) 0 else 1)); - if (method.info.resultType != definitions.UnitClass.tpe) + if (method.info.resultType != definitions.UnitClass.tpe && !method.isConstructor) out.stack = Unknown :: out.stack; if (!isPureMethod(method)) invalidateRecords(out); @@ -446,8 +466,9 @@ abstract class CopyPropagation { // this relies on having the same order in paramAccessors and // the arguments on the stack. It should be the same! for (val (p, i) <- paramAccessors.zipWithIndex) { - assert(p.tpe == ctor.tpe.paramTypes(i)) - bindings += p -> values.head; +// assert(p.tpe == ctor.tpe.paramTypes(i), "In: " + ctor.fullNameString + " having: " + (paramAccessors map (.tpe))+ " vs. " + ctor.tpe.paramTypes) + if (p.tpe == ctor.tpe.paramTypes(i)) + bindings += p -> values.head; values = values.tail; } 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 3d4d3e6f14..7a3e858baa 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/DataFlowAnalysis.scala @@ -18,8 +18,8 @@ trait DataFlowAnalysis[L <: CompleteLattice] { val worklist: Set[P] = new LinkedHashSet - val in: Map[P, lattice.Elem] = new HashMap - val out: Map[P, lattice.Elem] = new HashMap + val in: Map[P, lattice.Elem] = new collection.jcl.HashMap + val out: Map[P, lattice.Elem] = new collection.jcl.HashMap val visited: HashSet[P] = new HashSet /* Implement this function to initialize the worklist. */ @@ -36,7 +36,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] { * * @param f the transfer function. */ - def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = + def forwardAnalysis(f: (P, lattice.Elem) => lattice.Elem): Unit = try { while (!worklist.isEmpty) { // Console.println("worklist in: " + worklist); val point = worklist.elements.next; worklist -= point; visited += point; @@ -44,8 +44,7 @@ trait DataFlowAnalysis[L <: CompleteLattice] { // Console.println("taking out point: " + point + " worklist out: " + worklist); if ((lattice.bottom == out(point)) || output != out(point)) { -// Console.println("Output changed at " + point + " added to worklist: ") -// Console.println("\t" + worklist) +// Console.println("Output changed at " + point + " from: " + out(point) + " to: " + output + " and they are different: " + (output != out(point))) out(point) = output val succs = point.successors succs foreach { p => @@ -55,6 +54,13 @@ trait DataFlowAnalysis[L <: CompleteLattice] { } } } + } catch { + case e: NoSuchElementException => + Console.println("in: " + in.mkString("", "\n", "")) + Console.println("out: " + out.mkString("", "\n", "")) + e.printStackTrace + Predef.error("Could not find element " + e.getMessage) + } /** ... * diff --git a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala index 9f99e942fa..3b610e11bc 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/ReachingDefinitions.scala @@ -26,39 +26,67 @@ abstract class ReachingDefinitions { */ object rdefLattice extends CompleteLattice { type Definition = (Local, BasicBlock, Int) - type Elem = Set[Definition] + type Elem = (Set[Definition], Stack) + type StackPos = Set[(BasicBlock, Int)] + type Stack = List[StackPos] - val top: Elem = new ListSet[Definition]() { + val top: Elem = (new ListSet[Definition]() { override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef] - } + }, Nil) - val bottom: Elem = new ListSet[Definition]() { + val bottom: Elem = (new ListSet[Definition]() { override def equals(that: Any): Boolean = this eq that.asInstanceOf[AnyRef] - } - - def lub2(a: Elem, b: Elem): Elem = a incl b + override def toString = "<bottom>" + }, Nil) + + /** The least upper bound is set inclusion for locals, and pairwise set inclusion for stacks. */ + def lub2(a: Elem, b: Elem): Elem = + if (bottom == a) b + else if (bottom == b) a + else { + val locals = a._1 incl b._1 + val stack = if (a._2 == Nil) + b._2 + else if (b._2 == Nil) a._2 + else List.map2(a._2, b._2) (_ incl _) + + val res = (locals, stack) + +// Console.println("\tlub2: " + a + ", " + b) +// Console.println("\tis: " + res) + +// if (res._1 eq bottom._1) (new ListSet[Definition], Nil) +// else res + res + } } class ReachingDefinitionsAnalysis extends DataFlowAnalysis[rdefLattice.type] { type P = BasicBlock val lattice = rdefLattice import lattice.Definition + import lattice.Stack import lattice.Elem var method: IMethod = _ val gen: Map[BasicBlock, Set[Definition]] = new HashMap() val kill:Map[BasicBlock, Set[Local]] = new HashMap() + val drops: Map[BasicBlock, Int] = new HashMap() + val outStack: Map[BasicBlock, Stack] = new HashMap() def init(m: IMethod): Unit = { this.method = m - gen.clear - kill.clear + gen.clear; kill.clear + drops.clear; outStack.clear for (val b <- m.code.blocks.toList; - val (g, k) = genAndKill(b)) { + val (g, k) = genAndKill(b); + val (d, st) = dropsAndGen(b)) { gen += b -> g kill += b -> k + drops += b -> d + outStack += b -> st } init { @@ -67,6 +95,10 @@ abstract class ReachingDefinitions { in(b) = lattice.bottom out(b) = lattice.bottom } + m.exh foreach { e => + in(e.startBlock) = (new ListSet[Definition], List(new ListSet[(BasicBlock, Int)])) + } + } } @@ -84,6 +116,34 @@ abstract class ReachingDefinitions { (genSet, killSet) } + private def dropsAndGen(b: BasicBlock): (Int, List[Set[(BasicBlock, Int)]]) = { + var depth = 0 + var drops = 0 + var stackOut: List[Set[(BasicBlock, Int)]] = Nil + + for (val (instr, idx) <- b.toList.zipWithIndex) { + if (instr == LOAD_EXCEPTION()) + () + else if (instr.consumed > depth) { + drops = drops + (instr.consumed - depth) + depth = 0 + stackOut = Nil + } else { + stackOut = stackOut.drop(instr.consumed) + depth = depth - instr.consumed + } + var prod = instr.produced + depth = depth + prod + while (prod > 0) { + stackOut = (new collection.immutable.Set1((b, idx))) :: stackOut + prod = prod - 1 + } + } +// Console.println("drops(" + b + ") = " + drops) +// Console.println("stackout(" + b + ") = " + stackOut) + (drops, stackOut) + } + override def run: Unit = { forwardAnalysis(blockTransfer) if (settings.debug.value) { @@ -100,20 +160,34 @@ abstract class ReachingDefinitions { (rd filter { case (l, _, _) => l != tmp }) + ((tmp, b, idx)) } - private def blockTransfer(b: BasicBlock, in: Set[Definition]): Set[Definition] = - (in filter { case (l, _, _) => !kill(b)(l) }) incl gen(b) + private def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { + var locals: Set[Definition] = (in._1 filter { case (l, _, _) => !kill(b)(l) }) incl gen(b) + if (locals eq lattice.bottom._1) locals = new ListSet[Definition] + (locals, outStack(b) ::: in._2.drop(drops(b))) + } /** Return the reaching definitions corresponding to the point after idx. */ def interpret(b: BasicBlock, idx: Int, in: lattice.Elem): Elem = { - var out = in - b(idx) match { + var locals = in._1 + var stack = in._2 + val instr = b(idx) + instr match { case STORE_LOCAL(l1) => - out = updateReachingDefinition(b, idx, out) + locals = updateReachingDefinition(b, idx, locals) + stack = stack.drop(instr.consumed) + case LOAD_EXCEPTION() => + stack = Nil case _ => - () + stack = stack.drop(instr.consumed) + } + + var prod = instr.produced + while (prod > 0) { + stack = (new collection.immutable.Set1((b, idx))) :: stack + prod = prod - 1 } - out + (locals, stack) } override def toString: String = { 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 9d27858b0a..e7f4738b5e 100644 --- a/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala +++ b/src/compiler/scala/tools/nsc/backend/icode/analysis/TypeFlowAnalysis.scala @@ -43,10 +43,13 @@ abstract class TypeFlowAnalysis { override val top = new TypeStack override val bottom = new TypeStack + val exceptionHandlerStack: TypeStack = new TypeStack(List(REFERENCE(definitions.AnyRefClass))) def lub2(s1: TypeStack, s2: TypeStack) = { if (s1 eq bottom) s2 else if (s2 eq bottom) s1 + else if (s1 eq exceptionHandlerStack) s1 + else if (s2 eq exceptionHandlerStack) s2 else { if (s1.length != s2.length) throw new CheckerError("Incompatible stacks: " + s1 + " and " + s2); @@ -124,10 +127,7 @@ abstract class TypeFlowAnalysis { out(b) = typeFlowLattice.bottom } m.exh foreach { e => - val stack = new TypeStack - stack.push( - REFERENCE(if (e.cls eq NoSymbol) definitions.ObjectClass else e.cls)) - in(e.startBlock) = Pair(in(e.startBlock)._1, stack) + in(e.startBlock) = Pair(in(e.startBlock)._1, typeStackLattice.exceptionHandlerStack) } } } @@ -146,8 +146,9 @@ abstract class TypeFlowAnalysis { } } - def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = + def blockTransfer(b: BasicBlock, in: lattice.Elem): lattice.Elem = { b.toList.foldLeft(in)(interpret) + } /** Abstract interpretation for one instruction. */ def interpret(in: typeFlowLattice.Elem, i: Instruction): typeFlowLattice.Elem = { @@ -155,10 +156,10 @@ abstract class TypeFlowAnalysis { val bindings = out._1 val stack = out._2 -/* if (settings.debug.value) { - Console.println("Stack: " + stack); - Console.println(i); - } */ +// if (settings.debug.value) { +// Console.println("Stack: " + stack); +// Console.println(i); +// } i match { case THIS(clasz) => @@ -319,6 +320,10 @@ abstract class TypeFlowAnalysis { case SCOPE_ENTER(_) | SCOPE_EXIT(_) => () + case LOAD_EXCEPTION() => + stack.pop(stack.length) + stack.push(typeLattice.Object) + case _ => dump abort("Unknown instruction: " + i) diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala index 939238062c..97a101a1a9 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenJVM.scala @@ -132,9 +132,6 @@ abstract class GenJVM extends SubComponent { var remoteClass: Boolean = false def genClass(c: IClass): Unit = { - if (settings.debug.value) - log("Generating class " + c.symbol + - " flags: " + Flags.flagsToString(c.symbol.flags)) clasz = c innerClasses = ListSet.empty @@ -388,10 +385,7 @@ abstract class GenJVM extends SubComponent { } def genMethod(m: IMethod): Unit = { - if (settings.debug.value) - log("Generating method " + m.symbol + - " flags: " + Flags.flagsToString(m.symbol.flags) + - " owner: " + m.symbol.owner); + log("Generating method " + m.symbol.fullNameString) method = m endPC.clear computeLocalVarsIndex(m) @@ -624,19 +618,20 @@ abstract class GenJVM extends SubComponent { ranges } - this.method.exh foreach ((e) => { + this.method.exh foreach { e => ranges(e).sort({ (p1, p2) => p1._1 < p2._1 }) - .foreach ((p) => { - if (settings.debug.value) - log("Adding exception handler " + e + "at block: " + e.startBlock + " for " + method + - " from: " + p._1 + " to: " + p._2 + " catching: " + e.cls); - jcode.addExceptionHandler(p._1, p._2, - labels(e.startBlock).getAnchor(), - if (e.cls == NoSymbol) - null - else javaName(e.cls)) - }) - }); + .foreach { p => + if (p._1 < p._2) { + if (settings.debug.value) + log("Adding exception handler " + e + "at block: " + e.startBlock + " for " + method + + " from: " + p._1 + " to: " + p._2 + " catching: " + e.cls); + jcode.addExceptionHandler(p._1, p._2, + labels(e.startBlock).getAnchor(), + if (e.cls == NoSymbol) null else javaName(e.cls)) + } else + log("Empty exception range: " + p) + } + } } /** local variables whose scope appears in this block. */ @@ -998,6 +993,9 @@ abstract class GenJVM extends SubComponent { b.varsInScope -= lv } else assert(false, "Illegal local var nesting: " + method) + + case LOAD_EXCEPTION() => + () } crtPC = jcode.getPC() diff --git a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala index 9bdd2f64e9..b13656353a 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/ClosureElimination.scala @@ -115,7 +115,7 @@ abstract class ClosureElimination extends SubComponent { } - case LOAD_FIELD(f, false) => + case LOAD_FIELD(f, false) if accessible(f, m.symbol) => info.stack(0) match { case r @ Record(cls, bindings) if bindings.isDefinedAt(f) => info.getLocalForField(r, f) match { @@ -151,6 +151,7 @@ abstract class ClosureElimination extends SubComponent { case e: LubError => Console.println("In method: " + m); Console.println(e); + e.printStackTrace } /* Partial mapping from values to instructions that load them. */ @@ -162,6 +163,13 @@ abstract class ClosureElimination extends SubComponent { THIS(definitions.ObjectClass) } + /** is field 'f' accessible from method 'm'? */ + def accessible(f: Symbol, m: Symbol): Boolean = + f.isPublic || (f.hasFlag(Flags.PROTECTED) && (enclPackage(f) == enclPackage(m))) + + private def enclPackage(sym: Symbol): Symbol = + if ((sym == NoSymbol) || sym.isPackageClass) sym else enclPackage(sym.owner) + } /* class ClosureElim */ @@ -191,7 +199,6 @@ abstract class ClosureElimination extends SubComponent { 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 => diff --git a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala index a2818d08f0..28fcda23b2 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/DeadCodeElimination.scala @@ -41,34 +41,55 @@ abstract class DeadCodeElimination extends SubComponent { class DeadCode { def analyzeClass(cls: IClass): Unit = cls.methods.foreach { m => + this.method = m // analyzeMethod(m); - collectRDef(m) + dieCodeDie(m) } - val a = new liveness.LivenessAnalysis(); val rdef = new reachingDefinitions.ReachingDefinitionsAnalysis; /** Use-def chain: give the reaching definitions at the beginning of given instruction. */ var defs: Map[(BasicBlock, Int), Set[rdef.lattice.Definition]] = HashMap.empty /** Useful instructions which have not been scanned yet. */ - val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.HashSet + val worklist: mutable.Set[(BasicBlock, Int)] = new mutable.LinkedHashSet + + /** what instructions have been marked as useful? */ + val useful: mutable.Map[BasicBlock, mutable.BitSet] = new mutable.HashMap + + /** the current method. */ + var method: IMethod = _ + + def dieCodeDie(m: IMethod): Unit = if (m.code ne null) { + log("dead code elimination on " + m); +// (new DepthFirstLinerizer).linearize(m) + m.code.blocks.clear + m.code.blocks ++= linearizer.linearize(m) + collectRDef(m) + mark + sweep(m) + } /** collect reaching definitions and initial useful instructions for this method. */ def collectRDef(m: IMethod): Unit = if (m.code ne null) { - log("rdef on " + m); - defs = HashMap.empty; worklist.clear + defs = HashMap.empty; worklist.clear; useful.clear; rdef.init(m); rdef.run; for (val bb <- m.code.blocks.toList) { + useful(bb) = new mutable.BitSet(bb.size) var rd = rdef.in(bb); - Console.println("** Block " + bb + " **") for (val Pair(i, idx) <- bb.toList.zipWithIndex) { i match { - case LOAD_LOCAL(l) => defs((bb, idx)) = rd - case RETURN(_) => worklist += ((bb, idx)) - case CALL_METHOD(m, _) if isSideEffecting(m) => worklist += ((bb, idx)) + case LOAD_LOCAL(l) => + defs = defs + ((bb, idx)) -> rd._1 +// Console.println(i + ": " + (bb, idx) + " rd: " + rd + " and having: " + defs) + case RETURN(_) | JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | + DROP(_) | THROW() | STORE_FIELD(_, _) | STORE_ARRAY_ITEM(_) | + LOAD_EXCEPTION() | SWITCH(_, _) | MONITOR_ENTER() | MONITOR_EXIT() => worklist += ((bb, idx)) + case CALL_METHOD(m1, _) if isSideEffecting(m1) => worklist += ((bb, idx)) + case CALL_METHOD(m1, SuperCall(_)) => + worklist += ((bb, idx)) // super calls to constructor case _ => () } rd = rdef.interpret(bb, idx, rd); @@ -80,81 +101,155 @@ abstract class DeadCodeElimination extends SubComponent { * dependecies are marked useful too, and added to the worklist. */ def mark { +// log("Starting with worklist: " + worklist) while (!worklist.isEmpty) { val (bb, idx) = worklist.elements.next worklist -= ((bb, idx)) + if (settings.debug.value) + log("Marking instr: \tBB_" + bb + ": " + idx + " " + bb(idx)) val instr = bb(idx) - assert(!instr.useful) - instr match { - case LOAD_LOCAL(l1) => - for (val (_, bb1, idx1) <- defs((bb, idx)); !bb1(idx1).useful) - worklist += ((bb1, idx1)) - case _ => - for (val (bb1, idx1) <- bb.findDefs(idx, 0); !bb1(idx1).useful) - worklist += ((bb1, idx1)) + if (!useful(bb)(idx)) { + useful(bb) += idx + instr match { + case LOAD_LOCAL(l1) => + for (val (l2, bb1, idx1) <- defs((bb, idx)); l1 == l2; !useful(bb1)(idx1)) + worklist += ((bb1, idx1)) + + case nw @ NEW(_) => + assert(nw.init ne null, "null new.init at: " + bb + ": " + idx + "(" + instr + ")") + worklist += findInstruction(bb, nw.init) + + case LOAD_EXCEPTION() => + () + + case _ => + for (val (bb1, idx1) <- findDefs(bb, idx, instr.consumed); !useful(bb1)(idx1)) + worklist += ((bb1, idx1)) + } } } } - def analyzeMethod(m: IMethod): Unit = if (m.code ne null) { - log("DCE on " + m); - a.init(m); - a.run; + def sweep(m: IMethod) { + val compensations = computeCompensations(m) for (val bb <- m.code.blocks.toList) { - var live = a.out(bb); - for (val Pair(i, pos) <- bb.toList.zipWithIndex.reverse) { - i match { - case STORE_LOCAL(l) if (!live(l)) => - removeDefUse(bb, i); - case _ => () +// Console.println("** Sweeping block " + bb + " **") + val oldInstr = bb.toList + bb.open + bb.clear + for (val Pair(i, idx) <- oldInstr.zipWithIndex) { + if (useful(bb)(idx)) { +// log(" " + i + " is useful") + bb.emit(i, i.pos) + compensations.get(bb, idx) match { + case Some(is) => is foreach bb.emit + case None => () + } + } else { + i match { + case NEW(REFERENCE(sym)) => + log("skipped object creation: " + sym) + //Console.println("skipping class file altogether: " + sym.fullNameString) + icodes.classes -= sym + case _ => () + } + log("Skipped: bb_" + bb + ": " + idx + "( " + i + ")") } - live = a.interpret(live, i); } + + if (bb.size > 0) + bb.close + else + log("empty block encountered") } } - /** Remove a pair def-use, if safe to do so. The `use' is given by index - * in the basic block. The `def' is the closest previous instruction which - * produced the top value on the stack. - */ - def removeDefUse(bb: BasicBlock, use: Instruction): Unit = { - val usePos = bb.indexOf(use) - bb.findDef(usePos) match { - case Some(defPos) => - val definition = bb(defPos); - if (isSafeToRemove(definition)) { - log("Removing instructions at BB " + bb + " def: " + definition + ", use: " + use); - - if (definition.consumed == 0) { - bb.removeInstructionsAt(defPos, usePos) - } else { - bb.removeInstructionsAt(usePos); - bb.replaceInstruction(definition, definition.consumedTypes map DROP); + private def computeCompensations(m: IMethod): mutable.Map[(BasicBlock, Int), List[Instruction]] = { + val compensations: mutable.Map[(BasicBlock, Int), List[Instruction]] = new mutable.HashMap + + for (val bb <- m.code.blocks.toList) { + assert(bb.isClosed, "Open block in computeCompensations") + for (val (i, idx) <- bb.toList.zipWithIndex) { + if (!useful(bb)(idx)) { + val defs = findDefs(bb, idx, i.consumed) + for (val d <- defs) { + if (!compensations.isDefinedAt(d)) + compensations(d) = i.consumedTypes map DROP } } - case None => - bb.replaceInstruction(use, use.consumedTypes map DROP); - log("Replaced dead " + use + " by DROP in bb " + bb); + } } + compensations } - /** Is 'sym' a side-effecting method? TODO: proper analysis. */ - private def isSideEffecting(sym: Symbol): Boolean = { - sym.isClassConstructor // for testing only + private def withClosed[a](bb: BasicBlock)(f: => a): a = { + if (bb.size > 0) bb.close + val res = f + if (bb.size > 0) bb.open + res } - def isSafeToRemove(i: Instruction): Boolean = i match { -/* case LOAD_LOCAL(l) => true - case LOAD_FIELD(_, _) => true - case THIS(_) => true -*/ - case CALL_METHOD(m, style) => - (m.isClassConstructor && - definitions.refClass.values.contains(m.owner)); - case _ => true; + private def findInstruction(bb: BasicBlock, i: Instruction): (BasicBlock, Int) = { + def find(bb: BasicBlock): Option[(BasicBlock, Int)] = { + var xs = bb.toList + xs.zipWithIndex find { hd => hd._1 eq i } match { + case Some(_, idx) => Some(bb, idx) + case None => None + } + } + + for (val b <- linearizer.linearizeAt(method, bb)) + find(b) match { + case Some(p) => return p + case None => () + } + abort("could not find init in: " + method) } + def findDefs(bb: BasicBlock, idx: Int, m: Int): List[(BasicBlock, Int)] = if (idx > 0) { + assert(bb.isClosed) + var instrs = bb.getArray + var res: List[(BasicBlock, Int)] = Nil + var i = idx + var n = m + var d = 0 + // "I look for who produced the 'n' elements below the 'd' topmost slots of the stack" + while (n > 0 && i > 0) { + i = i - 1 + val prod = instrs(i).produced + if (prod > d) { + res = (bb, i) :: res + n = n - (prod - d) + if (bb(i) != LOAD_EXCEPTION) + d = instrs(i).consumed + } else { + d = d - prod + d = d + instrs(i).consumed; + } + } + + if (n > 0) { + val stack = rdef.in(bb)._2 + assert(stack.length >= n, "entry stack is too small, expected: " + n + " found: " + stack) + stack.drop(d).take(n) foreach { defs => + res = defs.toList ::: res + } + } + res + } else { + val stack = rdef.in(bb)._2 + assert(stack.length >= m, "entry stack is too small, expected: " + m + " found: " + stack) + stack.take(m) flatMap (.toList) + } + + /** Is 'sym' a side-effecting method? TODO: proper analysis. */ + private def isSideEffecting(sym: Symbol): Boolean = { + !(sym.isGetter // for testing only + || (sym.isConstructor + && sym.owner.owner == definitions.getModule("scala.runtime").moduleClass) + || (sym.isConstructor && inliner.isClosureClass(sym.owner))) + } } /* DeadCode */ } diff --git a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala index 31d648e129..a98bb82155 100644 --- a/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala +++ b/src/compiler/scala/tools/nsc/backend/opt/Inliners.scala @@ -20,6 +20,9 @@ abstract class Inliners extends SubComponent { val phaseName = "inliner"; + /** The maximum size in basic blocks of methods considered for inlining. */ + final val MAX_INLINE_SIZE = 16 + /** Create a new phase */ override def newPhase(p: Phase) = new InliningPhase(p); @@ -63,7 +66,11 @@ abstract class Inliners extends SubComponent { instr: Instruction, callee: IMethod): Unit = { log("Inlining " + callee + " in " + caller + " at pos: " + - classes(caller.symbol.owner).cunit.position(instr.pos)); + (try { + classes(caller.symbol.owner).cunit.position(instr.pos).toString + } catch { + case _ => "<nopos>" + })); val targetPos = instr.pos; val a = new analysis.MethodTFA(callee); @@ -99,7 +106,7 @@ abstract class Inliners extends SubComponent { /** Add a new block in the current context. */ def newBlock = { val b = caller.code.newBlock; - activeHandlers.foreach (.addBlock(b)); + activeHandlers.foreach (.addCoveredBlock(b)); if (retVal ne null) b.varsInScope += retVal b.varsInScope += inlinedThis b.varsInScope ++= varsInScope @@ -131,8 +138,12 @@ abstract class Inliners extends SubComponent { val afterBlock = newBlock; + /** Map from nw.init instructions to their matching NEW call */ + val pending: collection.jcl.Map[Instruction, NEW] = new collection.jcl.HashMap + /** Map an instruction from the callee to one suitable for the caller. */ - def map(i: Instruction): Instruction = i match { + def map(i: Instruction): Instruction = { + val newInstr = i match { case THIS(clasz) => LOAD_LOCAL(inlinedThis); @@ -172,8 +183,23 @@ abstract class Inliners extends SubComponent { case SCOPE_EXIT(l) if inlinedLocals.isDefinedAt(l) => SCOPE_EXIT(inlinedLocals(l)) + case nw @ NEW(sym) => + val r = NEW(sym) + pending(nw.init) = r + r + + case CALL_METHOD(meth, Static(true)) if (meth.isClassConstructor) => + CALL_METHOD(meth, Static(true)) + case _ => i } + // check any pending NEW's + if (pending isDefinedAt i) { + pending(i).init = newInstr.asInstanceOf[CALL_METHOD] + pending -= i + } + newInstr + } addLocals(caller, callee.locals map dupLocal); addLocal(caller, inlinedThis); @@ -233,6 +259,7 @@ abstract class Inliners extends SubComponent { // add exception handlers of the callee caller.exh = (callee.exh map translateExh) ::: caller.exh; + assert(pending.isEmpty, "Pending NEW elements: " + pending) } val InlineAttr = if (settings.inline.value) try { @@ -254,11 +281,14 @@ abstract class Inliners extends SubComponent { var retry = false; var count = 0; fresh.clear + // how many times have we already inlined this method here? + val inlinedMethods: Map[Symbol, Int] = new HashMap[Symbol, Int] { + override def default(k: Symbol) = 0 + } do { retry = false; if (m.code ne null) { -// this.count = 0; if (settings.debug.value) log("Analyzing " + m + " count " + count); tfa.init(m); @@ -280,7 +310,9 @@ abstract class Inliners extends SubComponent { log("" + i + " has actual receiver: " + receiver); } if (settings.debug.value) - log("Treating " + i); + log("Treating " + i + + "\n\tclasses.contains: " + classes.contains(receiver) + + "\n\tconcreteMethod.isFinal: " + concreteMethod.isFinal); if ( classes.contains(receiver) && (isClosureClass(receiver) @@ -288,16 +320,28 @@ abstract class Inliners extends SubComponent { || msym.attributes.exists(a => a.atp == InlineAttr))) { classes(receiver).lookupMethod(concreteMethod) match { case Some(inc) => - if (inc != m && (inc.code ne null) + if (inc.symbol != m.symbol + && (inlinedMethods(inc.symbol) < 2) + && (inc.code ne null) + && shouldInline(m, inc) + && (inc.code.blocks.length <= MAX_INLINE_SIZE) && isSafeToInline(m, inc, info._2)) { retry = true; if (!isClosureClass(receiver)) // only count non-closures count = count + 1; inline(m, bb, i, inc); + inlinedMethods(inc.symbol) = inlinedMethods(inc.symbol) + 1 /* Remove this method from the cache, as the calls-private relation might have changed after the inlining. */ callsPrivate -= m; + } else { + if (settings.debug.value) + log("inline failed because:\n\tinc.symbol != m.symbol: " + (inc.symbol != m.symbol) + + "\n\t(inlinedMethods(inc.symbol) < 2): " + (inlinedMethods(inc.symbol) < 2) + + "\n\tinc.code ne null: " + (inc.code ne null) + + "\n\tinc.code.blocks.length < MAX_INLINE_SIZE: " + (inc.code.blocks.length < MAX_INLINE_SIZE) + "(" + inc.code.blocks.length + ")" + + "\n\tisSafeToInline(m, inc, info._2): " + isSafeToInline(m, inc, info._2)); } case None => (); @@ -320,30 +364,25 @@ abstract class Inliners extends SubComponent { throw e; } - def isClosureClass(cls: Symbol): Boolean = { - val res = - cls.isFinal && - cls.tpe.parents.exists { t => - val TypeRef(_, sym, _) = t; - definitions.FunctionClass exists sym.== - } - res - } - /** Cache whether a method calls private members. */ val callsPrivate: Map[IMethod, Boolean] = new HashMap; + def isRecursive(m: IMethod): Boolean = m.recursive + /** A method is safe to inline when: * - it does not contain calls to private methods when * called from another class * - it is not inlined into a position with non-empty stack, * while having a top-level finalizer (see liftedTry problem) + * - it is not recursive * Note: * - synthetic private members are made public in this pass. */ def isSafeToInline(caller: IMethod, callee: IMethod, stack: TypeStack): Boolean = { var callsPrivateMember = false; + if (callee.recursive) return false; + callsPrivate get (callee) match { case Some(b) => callsPrivateMember = b; case None => @@ -382,7 +421,8 @@ abstract class Inliners extends SubComponent { return false; if (stack.length > (1 + callee.symbol.info.paramTypes.length) && - (callee.exh exists (.covered.contains(callee.code.startBlock)))) { + callee.exh != Nil) { +// (callee.exh exists (.covered.contains(callee.code.startBlock)))) { if (settings.debug.value) log("method " + callee.symbol + " is used on a non-empty stack with finalizer."); false } else @@ -390,4 +430,41 @@ abstract class Inliners extends SubComponent { } } /* class Inliner */ + + def isClosureClass(cls: Symbol): Boolean = { + val res = + cls.isFinal && + cls.tpe.parents.exists { t => + val TypeRef(_, sym, _) = t; + definitions.FunctionClass exists sym.== + } + res + } + + /** small method size (in blocks) */ + val SMALL_METHOD_SIZE = 4 + + /** Decide whether to inline or not. Heuristics: + * - it's bad to make the caller larger (> SMALL_METHOD_SIZE) + * if it was small + * - it's good to inline higher order functions + * - it's good to inline closures functions. + * - it's bad (useless) to inline inside bridge methods + */ + def shouldInline(caller: IMethod, callee: IMethod): Boolean = { + if (caller.symbol.hasFlag(Flags.BRIDGE)) return false; + + var score = 0 + if (callee.code.blocks.length <= SMALL_METHOD_SIZE) score = score + 1 + if (caller.code.blocks.length <= SMALL_METHOD_SIZE + && (caller.code.blocks.length + callee.code.blocks.length) < SMALL_METHOD_SIZE) + score = score - 1 + + if (callee.symbol.tpe.paramTypes.exists(definitions.isFunctionType)) + score = score + 2 + if (isClosureClass(callee.symbol.owner)) + score = score + 2 + + score > 0 + } } /* class Inliners */ diff --git a/src/compiler/scala/tools/nsc/symtab/Types.scala b/src/compiler/scala/tools/nsc/symtab/Types.scala index 66bdf9dfd1..166c455dff 100644 --- a/src/compiler/scala/tools/nsc/symtab/Types.scala +++ b/src/compiler/scala/tools/nsc/symtab/Types.scala @@ -2560,15 +2560,15 @@ trait Types requires SymbolTable { if (lubType.decls.isEmpty) lubBase else lubType } } - if (settings.debug.value) { - log(indent + "lub of " + ts + " at depth "+depth)//debug - indent = indent + " " - } +// if (settings.debug.value) { +// log(indent + "lub of " + ts + " at depth "+depth)//debug +// indent = indent + " " +// } val res = lub0(ts) - if (settings.debug.value) { - indent = indent.substring(0, indent.length() - 2) - log(indent + "lub of " + ts + " is " + res)//debug - } +// if (settings.debug.value) { +// indent = indent.substring(0, indent.length() - 2) +// log(indent + "lub of " + ts + " is " + res)//debug +// } res } diff --git a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala index c5f1e2115c..320b9a6286 100644 --- a/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala +++ b/src/compiler/scala/tools/nsc/symtab/classfile/ICodeReader.scala @@ -587,7 +587,7 @@ abstract class ICodeReader extends ClassfileParser { def toBasicBlock: Code = { import opcodes._ - val code = new Code(method.symbol.name.toString); + val code = new Code(method.symbol.name.toString, method); method.setCode(code) var bb = code.startBlock diff --git a/src/library/scala/List.scala b/src/library/scala/List.scala index 73d633515a..b6723b5517 100644 --- a/src/library/scala/List.scala +++ b/src/library/scala/List.scala @@ -666,7 +666,7 @@ sealed abstract class List[+a] extends Seq[a] { * @param f function to apply to each element. * @return <code>[f(a0), ..., f(an)]</code> if this list is <code>[a0, ..., an]</code>. */ - override def map[b](f: a => b): List[b] = { + final override def map[b](f: a => b): List[b] = { val b = new ListBuffer[b] var these = this while (!these.isEmpty) { @@ -696,7 +696,7 @@ sealed abstract class List[+a] extends Seq[a] { * * @param f the treatment to apply to each element. */ - override def foreach(f: a => Unit): Unit = { + final override def foreach(f: a => Unit): Unit = { var these = this while (!these.isEmpty) { f(these.head) @@ -710,7 +710,7 @@ sealed abstract class List[+a] extends Seq[a] { * @param p the predicate used to filter the list. * @return the elements of this list satisfying <code>p</code>. */ - override def filter(p: a => Boolean): List[a] = { + final override def filter(p: a => Boolean): List[a] = { // return same list if all elements satisfy p var these = this while (!these.isEmpty && p(these.head)) { @@ -964,7 +964,7 @@ sealed abstract class List[+a] extends Seq[a] { * @return <code>f(a<sub>0</sub>) ::: ... ::: f(a<sub>n</sub>)</code> if * this list is <code>[a<sub>0</sub>, ..., a<sub>n</sub>]</code>. */ - override def flatMap[b](f: a => Iterable[b]): List[b] = { + final override def flatMap[b](f: a => Iterable[b]): List[b] = { val b = new ListBuffer[b] var these = this while (!these.isEmpty) { |