diff options
14 files changed, 1209 insertions, 155 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/AsmUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/AsmUtils.scala index 2af2037fec..7269910af6 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/AsmUtils.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/AsmUtils.scala @@ -5,7 +5,7 @@ package scala.tools.nsc.backend.jvm -import scala.tools.asm.tree.{ClassNode, MethodNode} +import scala.tools.asm.tree.{AbstractInsnNode, ClassNode, MethodNode} import java.io.PrintWriter import scala.tools.asm.util.{TraceClassVisitor, TraceMethodVisitor, Textifier} import scala.tools.asm.ClassReader @@ -58,4 +58,9 @@ object AsmUtils { new ClassReader(bytes).accept(node, 0) node } + + def instructionString(instruction: AbstractInsnNode): String = instruction.getOpcode match { + case -1 => instruction.toString + case op => scala.tools.asm.util.Printer.OPCODES(op) + } } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala index 4b9383c67c..03306f30aa 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala @@ -14,7 +14,7 @@ object BackendStats { val bcodeInitTimer = newSubTimer("bcode initialization", bcodeTimer) val bcodeGenStat = newSubTimer("code generation", bcodeTimer) - val bcodeDceTimer = newSubTimer("dead code elimination", bcodeTimer) + val methodOptTimer = newSubTimer("intra-method optimizations", bcodeTimer) val bcodeWriteTimer = newSubTimer("classfile writing", bcodeTimer) def timed[T](timer: Statistics.Timer)(body: => T): T = { diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala index ba94a9c44c..a45f586666 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala @@ -9,12 +9,12 @@ package tools.nsc package backend package jvm -import scala.collection.{ mutable, immutable } -import scala.annotation.switch +import scala.collection.mutable import scala.reflect.internal.util.Statistics import scala.tools.asm import scala.tools.asm.tree.ClassNode +import scala.tools.nsc.backend.jvm.opt.LocalOpt /* * Prepare in-memory representations of classfiles using the ASM Tree API, and serialize them to disk. @@ -215,13 +215,10 @@ abstract class GenBCode extends BCodeSyncAndTry { * - converting the plain ClassNode to byte array and placing it on queue-3 */ class Worker2 { - def localOptimizations(classNode: ClassNode): Unit = { - def dce(): Boolean = BackendStats.timed(BackendStats.bcodeDceTimer) { - if (settings.YoptUnreachableCode) opt.LocalOpt.removeUnreachableCode(classNode) - else false - } + lazy val localOpt = new LocalOpt(settings) - dce() + def localOptimizations(classNode: ClassNode): Unit = { + BackendStats.timed(BackendStats.methodOptTimer)(localOpt.methodOptimizations(classNode)) } def run() { diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala new file mode 100644 index 0000000000..6b4047c0a7 --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala @@ -0,0 +1,184 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2014 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm +package opt + +import scala.annotation.{tailrec, switch} +import scala.collection.mutable +import scala.reflect.internal.util.Collections._ +import scala.tools.asm.Opcodes +import scala.tools.asm.tree._ +import scala.collection.convert.decorateAsScala._ + +object BytecodeUtils { + + object Goto { + def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = { + if (instruction.getOpcode == Opcodes.GOTO) Some(instruction.asInstanceOf[JumpInsnNode]) + else None + } + } + + object JumpNonJsr { + def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = { + if (isJumpNonJsr(instruction)) Some(instruction.asInstanceOf[JumpInsnNode]) + else None + } + } + + object ConditionalJump { + def unapply(instruction: AbstractInsnNode): Option[JumpInsnNode] = { + if (isConditionalJump(instruction)) Some(instruction.asInstanceOf[JumpInsnNode]) + else None + } + } + + object VarInstruction { + def unapply(instruction: AbstractInsnNode): Option[VarInsnNode] = { + if (isVarInstruction(instruction)) Some(instruction.asInstanceOf[VarInsnNode]) + else None + } + + } + + def isJumpNonJsr(instruction: AbstractInsnNode): Boolean = { + val op = instruction.getOpcode + // JSR is deprecated in classfile version 50, disallowed in 51. historically, it was used to implement finally. + op == Opcodes.GOTO || isConditionalJump(instruction) + } + + def isConditionalJump(instruction: AbstractInsnNode): Boolean = { + val op = instruction.getOpcode + (op >= Opcodes.IFEQ && op <= Opcodes.IF_ACMPNE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL + } + + def isReturn(instruction: AbstractInsnNode): Boolean = { + val op = instruction.getOpcode + op >= Opcodes.IRETURN && op <= Opcodes.RETURN + } + + def isVarInstruction(instruction: AbstractInsnNode): Boolean = { + val op = instruction.getOpcode + (op >= Opcodes.ILOAD && op <= Opcodes.ALOAD) || (op >= Opcodes.ISTORE && op <= Opcodes.ASTORE) + } + + def isExecutable(instruction: AbstractInsnNode): Boolean = instruction.getOpcode >= 0 + + def nextExecutableInstruction(instruction: AbstractInsnNode, alsoKeep: AbstractInsnNode => Boolean = Set()): Option[AbstractInsnNode] = { + var result = instruction + do { result = result.getNext } + while (result != null && !isExecutable(result) && !alsoKeep(result)) + Option(result) + } + + def sameTargetExecutableInstruction(a: JumpInsnNode, b: JumpInsnNode): Boolean = { + // Compare next executable instead of the the labels. Identifies a, b as the same target: + // LabelNode(a) + // LabelNode(b) + // Instr + nextExecutableInstruction(a.label) == nextExecutableInstruction(b.label) + } + + def removeJumpAndAdjustStack(method: MethodNode, jump: JumpInsnNode) { + val instructions = method.instructions + val op = jump.getOpcode + if ((op >= Opcodes.IFEQ && op <= Opcodes.IFGE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL) { + instructions.insert(jump, getPop(1)) + } else if ((op >= Opcodes.IF_ICMPEQ && op <= Opcodes.IF_ICMPLE) || op == Opcodes.IF_ACMPEQ || op == Opcodes.IF_ACMPNE) { + instructions.insert(jump, getPop(1)) + instructions.insert(jump, getPop(1)) + } else { + // we can't remove JSR: its execution does not only jump, it also adds a return address to the stack + assert(jump.getOpcode == Opcodes.GOTO) + } + instructions.remove(jump) + } + + def finalJumpTarget(source: JumpInsnNode): LabelNode = { + @tailrec def followGoto(label: LabelNode, seenLabels: Set[LabelNode]): LabelNode = nextExecutableInstruction(label) match { + case Some(Goto(dest)) => + if (seenLabels(dest.label)) dest.label + else followGoto(dest.label, seenLabels + dest.label) + + case _ => label + } + followGoto(source.label, Set(source.label)) + } + + def negateJumpOpcode(jumpOpcode: Int): Int = (jumpOpcode: @switch) match { + case Opcodes.IFEQ => Opcodes.IFNE + case Opcodes.IFNE => Opcodes.IFEQ + + case Opcodes.IFLT => Opcodes.IFGE + case Opcodes.IFGE => Opcodes.IFLT + + case Opcodes.IFGT => Opcodes.IFLE + case Opcodes.IFLE => Opcodes.IFGT + + case Opcodes.IF_ICMPEQ => Opcodes.IF_ICMPNE + case Opcodes.IF_ICMPNE => Opcodes.IF_ICMPEQ + + case Opcodes.IF_ICMPLT => Opcodes.IF_ICMPGE + case Opcodes.IF_ICMPGE => Opcodes.IF_ICMPLT + + case Opcodes.IF_ICMPGT => Opcodes.IF_ICMPLE + case Opcodes.IF_ICMPLE => Opcodes.IF_ICMPGT + + case Opcodes.IF_ACMPEQ => Opcodes.IF_ACMPNE + case Opcodes.IF_ACMPNE => Opcodes.IF_ACMPEQ + + case Opcodes.IFNULL => Opcodes.IFNONNULL + case Opcodes.IFNONNULL => Opcodes.IFNULL + } + + def getPop(size: Int): InsnNode = { + val op = if (size == 1) Opcodes.POP else Opcodes.POP2 + new InsnNode(op) + } + + def labelReferences(method: MethodNode): Map[LabelNode, Set[AnyRef]] = { + val res = mutable.Map.empty[LabelNode, Set[AnyRef]] + def add(l: LabelNode, ref: AnyRef) = if (res contains l) res(l) = res(l) + ref else res(l) = Set(ref) + + method.instructions.iterator().asScala foreach { + case jump: JumpInsnNode => add(jump.label, jump) + case line: LineNumberNode => add(line.start, line) + case switch: LookupSwitchInsnNode => switch.labels.asScala.foreach(add(_, switch)); add(switch.dflt, switch) + case switch: TableSwitchInsnNode => switch.labels.asScala.foreach(add(_, switch)); add(switch.dflt, switch) + case _ => + } + if (method.localVariables != null) { + method.localVariables.iterator().asScala.foreach(l => { add(l.start, l); add(l.end, l) }) + } + if (method.tryCatchBlocks != null) { + method.tryCatchBlocks.iterator().asScala.foreach(l => { add(l.start, l); add(l.handler, l); add(l.end, l) }) + } + + res.toMap + } + + def substituteLabel(reference: AnyRef, from: LabelNode, to: LabelNode): Unit = { + def substList(list: java.util.List[LabelNode]) = { + foreachWithIndex(list.asScala.toList) { case (l, i) => + if (l == from) list.set(i, to) + } + } + reference match { + case jump: JumpInsnNode => jump.label = to + case line: LineNumberNode => line.start = to + case switch: LookupSwitchInsnNode => substList(switch.labels); if (switch.dflt == from) switch.dflt = to + case switch: TableSwitchInsnNode => substList(switch.labels); if (switch.dflt == from) switch.dflt = to + case local: LocalVariableNode => + if (local.start == from) local.start = to + if (local.end == from) local.end = to + case handler: TryCatchBlockNode => + if (handler.start == from) handler.start = to + if (handler.handler == from) handler.handler = to + if (handler.end == from) handler.end = to + } + } +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala index 3acd2d6154..273112b93c 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala @@ -7,125 +7,206 @@ package scala.tools.nsc package backend.jvm package opt +import scala.annotation.switch import scala.tools.asm.{Opcodes, MethodWriter, ClassWriter} import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter} import scala.tools.asm.tree._ import scala.collection.convert.decorateAsScala._ -import scala.collection.{ mutable => m } +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._ +import scala.tools.nsc.settings.ScalaSettings /** - * Intra-Method optimizations. + * Optimizations within a single method. + * + * unreachable code + * - removes instrucions of basic blocks to which no branch instruction points + * + enables eliminating some exception handlers and local variable descriptors + * > eliminating them is required for correctness, as explained in `removeUnreachableCode` + * + * empty exception handlers + * - removes exception handlers whose try block is empty + * + eliminating a handler where the try block is empty and reachable will turn the catch block + * unreachble. in this case "unreachable code" is invoked recursively until reaching a fixpiont. + * > for try blocks that are unreachable, "unreachable code" removes also the instructions of the + * catch block, and the recrusive invocation is not necessary. + * + * simplify jumps + * - various simplifications, see doc domments of individual optimizations + * + changing or eliminating jumps may render some code unreachable, therefore "simplify jumps" is + * executed in a loop with "unreachable code" + * + * empty local variable descriptors + * - removes entries from the local variable table where the variable is not actually used + * + enables eliminating labels that the entry points to (if they are not otherwise referenced) + * + * empty line numbers + * - eliminates line number nodes that describe no executable instructions + * + enables eliminating the label of the line number node (if it's not otherwise referenced) + * + * stale labels + * - eliminate labels that are not referenced, merge sequences of label definitions. */ -object LocalOpt { +class LocalOpt(settings: ScalaSettings) { /** - * Remove unreachable instructions from all (non-abstract) methods. + * Remove unreachable instructions from all (non-abstract) methods and apply various other + * cleanups to the bytecode. * * @param clazz The class whose methods are optimized * @return `true` if unreachable code was elminated in some method, `false` otherwise. */ - def removeUnreachableCode(clazz: ClassNode): Boolean = { - clazz.methods.asScala.foldLeft(false) { - case (changed, method) => removeUnreachableCode(method, clazz.name) || changed + def methodOptimizations(clazz: ClassNode): Boolean = { + settings.Yopt.value.nonEmpty && clazz.methods.asScala.foldLeft(false) { + case (changed, method) => methodOptimizations(method, clazz.name) || changed } } /** * Remove unreachable code from a method. + * * We rely on dead code elimination provided by the ASM framework, as described in the ASM User * Guide (http://asm.ow2.org/index.html), Section 8.2.1. It runs a data flow analysis, which only * computes Frame information for reachable instructions. Instructions for which no Frame data is * available after the analyis are unreachable. * - * TODO doc: it also removes empty handlers, unused local vars + * Also simplifies branching instructions, removes unused local variable descriptors, empty + * exception handlers, unnecessary label declarations and empty line number nodes. * - * Returns `true` if dead code in `method` has been eliminated. + * Returns `true` if the bytecode of `method` was changed. */ - private def removeUnreachableCode(method: MethodNode, ownerClassName: String): Boolean = { + private def methodOptimizations(method: MethodNode, ownerClassName: String): Boolean = { if (method.instructions.size == 0) return false // fast path for abstract methods - val codeRemoved = removeUnreachableCodeImpl(method, ownerClassName) - // unreachable-code also removes unused local variable nodes and empty exception handlers. - // This is required for correctness: such nodes are not allowed to refer to instruction offsets - // that don't exist (because they have been eliminated). - val localsRemoved = removeUnusedLocalVariableNodes(method) - val handlersRemoved = removeEmptyExceptionHandlers(method) - - // When eliminating a handler, the catch block becomes unreachable. The recursive invocation - // removes these blocks. - // Note that invoking removeUnreachableCode*Impl* a second time is not enough: removing the dead - // catch block can render other handlers empty, which also have to be removed in turn. - if (handlersRemoved) removeUnreachableCode(method, ownerClassName) - - // assert that we can leave local variable annotations as-is + // This is required for correctness, for example: + // + // def f = { return 0; try { 1 } catch { case _ => 2 } } + // + // The result after removeUnreachableCodeImpl: + // + // TRYCATCHBLOCK L0 L1 L2 java/lang/Exception + // L4 + // ICONST_0 + // IRETURN + // L0 + // L1 + // L2 + // + // If we don't eliminate the handler, the ClassWriter emits: + // + // TRYCATCHBLOCK L0 L0 L0 java/lang/Exception + // L1 + // ICONST_0 + // IRETURN + // L0 + // + // This triggers "ClassFormatError: Illegal exception table range in class file C". Similar + // for local variables in dead blocks. Maybe that's a bug in the ASM framework. + + var recurse = true + var codeHandlersOrJumpsChanged = false + while (recurse) { + // unreachable-code, empty-handlers and simplify-jumps run until reaching a fixpoint (see doc on class LocalOpt) + val (codeRemoved, handlersRemoved, liveHandlerRemoved) = if (settings.YoptUnreachableCode) { + val (codeRemoved, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName) + val removedHandlers = removeEmptyExceptionHandlers(method) + (codeRemoved, removedHandlers.nonEmpty, removedHandlers.exists(h => liveLabels(h.start))) + } else { + (false, false, false) + } + + val jumpsChanged = if (settings.YoptSimplifyJumps) simplifyJumps(method) else false + + codeHandlersOrJumpsChanged ||= (codeRemoved || handlersRemoved || jumpsChanged) + + // The doc comment of class LocalOpt explains why we recurse if jumpsChanged || liveHandlerRemoved + recurse = settings.YoptRecurseUnreachableJumps && (jumpsChanged || liveHandlerRemoved) + } + + // (*) Removing stale local variable descriptors is required for correctness of unreachable-code + val localsRemoved = + if (settings.YoptCompactLocals) compactLocalVariables(method) + else if (settings.YoptUnreachableCode) removeUnusedLocalVariableNodes(method)() // (*) + else false + + val lineNumbersRemoved = if (settings.YoptEmptyLineNumbers) removeEmptyLineNumbers(method) else false + + val labelsRemoved = if (settings.YoptEmptyLabels) removeEmptyLabelNodes(method) else false + + // assert that local variable annotations are empty (we don't emit them) - otherwise we'd have + // to eliminate those covering an empty range, similar to removeUnusedLocalVariableNodes. def nullOrEmpty[T](l: java.util.List[T]) = l == null || l.isEmpty assert(nullOrEmpty(method.visibleLocalVariableAnnotations), method.visibleLocalVariableAnnotations) assert(nullOrEmpty(method.invisibleLocalVariableAnnotations), method.invisibleLocalVariableAnnotations) - codeRemoved || localsRemoved || handlersRemoved + codeHandlersOrJumpsChanged || localsRemoved || lineNumbersRemoved || labelsRemoved } - private def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): Boolean = { - val initialSize = method.instructions.size - if (initialSize == 0) return false - + /** + * Removes unreachable basic blocks. + * + * TODO: rewrite, don't use computeMaxLocalsMaxStack (runs a ClassWriter) / Analyzer. Too slow. + */ + def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: String): (Boolean, Set[LabelNode]) = { // The data flow analysis requires the maxLocals / maxStack fields of the method to be computed. computeMaxLocalsMaxStack(method) val a = new Analyzer[BasicValue](new BasicInterpreter) a.analyze(ownerClassName, method) val frames = a.getFrames + val initialSize = method.instructions.size var i = 0 + var liveLabels = Set.empty[LabelNode] val itr = method.instructions.iterator() while (itr.hasNext) { - val ins = itr.next() - // Don't remove label nodes: they might be referenced for example in a LocalVariableNode - if (frames(i) == null && !ins.isInstanceOf[LabelNode]) { - // Instruction iterators allow removing during iteration. - // Removing is O(1): instructions are doubly linked list elements. - itr.remove() + itr.next() match { + case l: LabelNode => + if (frames(i) != null) liveLabels += l + + case ins => + // label nodes are not removed: they might be referenced for example in a LocalVariableNode + if (frames(i) == null || ins.getOpcode == Opcodes.NOP) { + // Instruction iterators allow removing during iteration. + // Removing is O(1): instructions are doubly linked list elements. + itr.remove() + } } i += 1 } - - method.instructions.size != initialSize - } - - /** - * Remove exception handlers that cover empty code blocks from all methods of `clazz`. - * Returns `true` if any exception handler was eliminated. - */ - def removeEmptyExceptionHandlers(clazz: ClassNode): Boolean = { - clazz.methods.asScala.foldLeft(false) { - case (changed, method) => removeEmptyExceptionHandlers(method) || changed - } + (method.instructions.size != initialSize, liveLabels) } /** * Remove exception handlers that cover empty code blocks. A block is considered empty if it * consist only of labels, frames, line numbers, nops and gotos. * + * There are no executable instructions that we can assume don't throw (eg ILOAD). The JVM spec + * basically says that a VirtualMachineError may be thrown at any time: + * http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.3 + * * Note that no instructions are eliminated. * - * @return `true` if some exception handler was eliminated. + * @return the set of removed handlers */ - def removeEmptyExceptionHandlers(method: MethodNode): Boolean = { + def removeEmptyExceptionHandlers(method: MethodNode): Set[TryCatchBlockNode] = { /** True if there exists code between start and end. */ def containsExecutableCode(start: AbstractInsnNode, end: LabelNode): Boolean = { - start != end && (start.getOpcode match { + start != end && ((start.getOpcode : @switch) match { // FrameNode, LabelNode and LineNumberNode have opcode == -1. - case -1 | Opcodes.NOP | Opcodes.GOTO => containsExecutableCode(start.getNext, end) + case -1 | Opcodes.GOTO => containsExecutableCode(start.getNext, end) case _ => true }) } - val initialNumberHandlers = method.tryCatchBlocks.size + var removedHandlers = Set.empty[TryCatchBlockNode] val handlersIter = method.tryCatchBlocks.iterator() while(handlersIter.hasNext) { val handler = handlersIter.next() - if (!containsExecutableCode(handler.start, handler.end)) handlersIter.remove() + if (!containsExecutableCode(handler.start, handler.end)) { + removedHandlers += handler + handlersIter.remove() + } } - method.tryCatchBlocks.size != initialNumberHandlers + removedHandlers } /** @@ -135,35 +216,107 @@ object LocalOpt { * Note that each entry in the local variable table has a start, end and index. Two entries with * the same index, but distinct start / end ranges are different variables, they may have not the * same type or name. - * - * TODO: also re-allocate locals to occupy fewer slots after eliminating unused ones */ - def removeUnusedLocalVariableNodes(method: MethodNode): Boolean = { + def removeUnusedLocalVariableNodes(method: MethodNode)(fistLocalIndex: Int = parametersSize(method), renumber: Int => Int = identity): Boolean = { def variableIsUsed(start: AbstractInsnNode, end: LabelNode, varIndex: Int): Boolean = { start != end && (start match { - case v: VarInsnNode => v.`var` == varIndex + case v: VarInsnNode if v.`var` == varIndex => true case _ => variableIsUsed(start.getNext, end, varIndex) }) } val initialNumVars = method.localVariables.size val localsIter = method.localVariables.iterator() - // The parameters and `this` (for instance methods) have the lowest indices in the local variables - // table. Note that double / long fields occupy two slots, so we sum up the sizes. Since getSize - // returns 0 for void, we have to add `max 1`. - val paramsSize = scala.tools.asm.Type.getArgumentTypes(method.desc).map(_.getSize max 1).sum - val thisSize = if ((method.access & Opcodes.ACC_STATIC) == 0) 1 else 0 - val endParamIndex = paramsSize + thisSize while (localsIter.hasNext) { val local = localsIter.next() - // parameters and `this` have the lowest indices, starting at 0 - val used = local.index < endParamIndex || variableIsUsed(local.start, local.end, local.index) - if (!used) - localsIter.remove() + val index = local.index + // parameters and `this` (the lowest indices, starting at 0) are never removed or renumbered + if (index >= fistLocalIndex) { + if (!variableIsUsed(local.start, local.end, index)) localsIter.remove() + else if (renumber(index) != index) local.index = renumber(index) + } } - method.localVariables.size == initialNumVars + method.localVariables.size != initialNumVars } + /** + * The number of local varialbe slots used for parameters and for the `this` reference. + */ + private def parametersSize(method: MethodNode): Int = { + // Double / long fields occupy two slots, so we sum up the sizes. Since getSize returns 0 for + // void, we have to add `max 1`. + val paramsSize = scala.tools.asm.Type.getArgumentTypes(method.desc).iterator.map(_.getSize max 1).sum + val thisSize = if ((method.access & Opcodes.ACC_STATIC) == 0) 1 else 0 + paramsSize + thisSize + } + + /** + * Compact the local variable slots used in the method's implementation. This prevents having + * unused slots for example after eliminating unreachable code. + * + * This transformation reduces the size of the frame for invoking the method. For example, if the + * method has an ISTORE instruction to the local variable 3, the maxLocals of the method is at + * least 4, even if some local variable slots below 3 are not used by any instruction. + * + * This could be improved by doing proper register allocation. + */ + def compactLocalVariables(method: MethodNode): Boolean = { + // This array is built up to map local variable indices from old to new. + val renumber = collection.mutable.ArrayBuffer.empty[Int] + + // Add the index of the local variable used by `varIns` to the `renumber` array. + def addVar(varIns: VarInsnNode): Unit = { + val index = varIns.`var` + val isWide = (varIns.getOpcode: @switch) match { + case Opcodes.LLOAD | Opcodes.DLOAD | Opcodes.LSTORE | Opcodes.DSTORE => true + case _ => false + } + + // Ensure the length of `renumber`. Unused variable indices are mapped to -1. + val minLength = if (isWide) index + 2 else index + 1 + for (i <- renumber.length until minLength) renumber += -1 + + renumber(index) = index + if (isWide) renumber(index + 1) = index + } + + // first phase: collect all used local variables. if the variable at index x is used, set + // renumber(x) = x, otherwise renumber(x) = -1. if the variable is wide (long or double), set + // renumber(x+1) = x. + + val firstLocalIndex = parametersSize(method) + for (i <- 0 until firstLocalIndex) renumber += i // parameters and `this` are always used. + method.instructions.iterator().asScala foreach { + case VarInstruction(varIns) => addVar(varIns) + case _ => + } + + // assign the next free slot to each used local variable. + // for example, rewrite (0, 1, -1, 3, -1, 5) to (0, 1, -1, 2, -1, 3). + + var nextIndex = firstLocalIndex + for (i <- firstLocalIndex until renumber.length if renumber(i) != -1) { + renumber(i) = nextIndex + nextIndex += 1 + } + + // Update the local variable descriptors according to the renumber table, and eliminate stale entries + val removedLocalVariableDescriptors = removeUnusedLocalVariableNodes(method)(firstLocalIndex, renumber) + + if (nextIndex == renumber.length) removedLocalVariableDescriptors + else { + // update variable instructions according to the renumber table + method.maxLocals = nextIndex + method.instructions.iterator().asScala.foreach { + case VarInstruction(varIns) => + val oldIndex = varIns.`var` + if (oldIndex >= firstLocalIndex && renumber(oldIndex) != oldIndex) + varIns.`var` = renumber(varIns.`var`) + case _ => + } + true + } + } /** * In order to run an Analyzer, the maxLocals / maxStack fields need to be available. The ASM @@ -187,4 +340,223 @@ object LocalOpt { method.maxLocals = mw.getMaxLocals method.maxStack = mw.getMaxStack } + + /** + * Removes LineNumberNodes that don't describe any executable instructions. + * + * This method expects (and asserts) that the `start` label of each LineNumberNode is the + * lexically preceeding label declaration. + */ + def removeEmptyLineNumbers(method: MethodNode): Boolean = { + def isEmpty(node: AbstractInsnNode): Boolean = node.getNext match { + case null => true + case l: LineNumberNode => true + case n if n.getOpcode >= 0 => false + case n => isEmpty(n) + } + + val initialSize = method.instructions.size + val iterator = method.instructions.iterator() + var previousLabel: LabelNode = null + while (iterator.hasNext) { + iterator.next match { + case label: LabelNode => previousLabel = label + case line: LineNumberNode if isEmpty(line) => + assert(line.start == previousLabel) + iterator.remove() + case _ => + } + } + method.instructions.size != initialSize + } + + /** + * Removes unreferenced label declarations, also squashes sequences of label definitions. + * + * [ops]; Label(a); Label(b); [ops]; + * => subs([ops], b, a); Label(a); subs([ops], b, a); + */ + def removeEmptyLabelNodes(method: MethodNode): Boolean = { + val references = labelReferences(method) + + val initialSize = method.instructions.size + val iterator = method.instructions.iterator() + var prev: LabelNode = null + while (iterator.hasNext) { + iterator.next match { + case label: LabelNode => + if (!references.contains(label)) iterator.remove() + else if (prev != null) { + references(label).foreach(substituteLabel(_, label, prev)) + iterator.remove() + } else prev = label + + case instruction => + if (instruction.getOpcode >= 0) prev = null + } + } + method.instructions.size != initialSize + } + + /** + * Apply various simplifications to branching instructions. + */ + def simplifyJumps(method: MethodNode): Boolean = { + var changed = false + + val allHandlers = method.tryCatchBlocks.asScala.toSet + + // A set of all exception handlers that guard the current instruction, required for simplifyGotoReturn + var activeHandlers = Set.empty[TryCatchBlockNode] + + // Instructions that need to be removed. simplifyBranchOverGoto returns an instruction to be + // removed. It cannot remove it itself because the instruction may be the successor of the current + // instruction of the iterator, which is not supported in ASM. + var instructionsToRemove = Set.empty[AbstractInsnNode] + + val iterator = method.instructions.iterator() + while (iterator.hasNext) { + val instruction = iterator.next() + + instruction match { + case l: LabelNode => + activeHandlers ++= allHandlers.filter(_.start == l) + activeHandlers = activeHandlers.filter(_.end != l) + case _ => + } + + if (instructionsToRemove(instruction)) { + iterator.remove() + instructionsToRemove -= instruction + } else if (isJumpNonJsr(instruction)) { // fast path - all of the below only treat jumps + var jumpRemoved = simplifyThenElseSameTarget(method, instruction) + + if (!jumpRemoved) { + changed = collapseJumpChains(instruction) || changed + jumpRemoved = removeJumpToSuccessor(method, instruction) + + if (!jumpRemoved) { + val staleGoto = simplifyBranchOverGoto(method, instruction) + instructionsToRemove ++= staleGoto + changed ||= staleGoto.nonEmpty + changed = simplifyGotoReturn(method, instruction, inTryBlock = activeHandlers.nonEmpty) || changed + } + } + changed ||= jumpRemoved + } + } + assert(instructionsToRemove.isEmpty, "some optimization required removing a previously traversed instruction. add `instructionsToRemove.foreach(method.instructions.remove)`") + changed + } + + /** + * Removes a conditional jump if it is followed by a GOTO to the same destination. + * + * CondJump l; [nops]; GOTO l; [...] + * POP*; [nops]; GOTO l; [...] + * + * Introduces 1 or 2 POP instructions, depending on the number of values consumed by the CondJump. + */ + private def simplifyThenElseSameTarget(method: MethodNode, instruction: AbstractInsnNode): Boolean = instruction match { + case ConditionalJump(jump) => + nextExecutableInstruction(instruction) match { + case Some(Goto(elseJump)) if sameTargetExecutableInstruction(jump, elseJump) => + removeJumpAndAdjustStack(method, jump) + true + + case _ => false + } + case _ => false + } + + /** + * Replace jumps to a sequence of GOTO instructions by a jump to the final destination. + * + * Jump l; [any ops]; l: GOTO m; [any ops]; m: GOTO n; [any ops]; n: NotGOTO; [...] + * => Jump n; [rest unchaned] + * + * If there's a loop of GOTOs, the initial jump is replaced by one of the labels in the loop. + */ + private def collapseJumpChains(instruction: AbstractInsnNode): Boolean = instruction match { + case JumpNonJsr(jump) => + val target = finalJumpTarget(jump) + if (jump.label == target) false else { + jump.label = target + true + } + + case _ => false + } + + /** + * Eliminates unnecessary jump instructions + * + * Jump l; [nops]; l: [...] + * => POP*; [nops]; l: [...] + * + * Introduces 0, 1 or 2 POP instructions, depending on the number of values consumed by the Jump. + */ + private def removeJumpToSuccessor(method: MethodNode, instruction: AbstractInsnNode) = instruction match { + case JumpNonJsr(jump) if nextExecutableInstruction(jump, alsoKeep = Set(jump.label)) == Some(jump.label) => + removeJumpAndAdjustStack(method, jump) + true + case _ => false + } + + /** + * If the "else" part of a conditional branch is a simple GOTO, negates the conditional branch + * and eliminates the GOTO. + * + * CondJump l; [nops, no labels]; GOTO m; [nops]; l: [...] + * => NegatedCondJump m; [nops, no labels]; [nops]; l: [...] + * + * Note that no label definitions are allowed in the first [nops] section. Otherwsie, there could + * be some other jump to the GOTO, and eliminating it would change behavior. + * + * For technical reasons, we cannot remove the GOTO here (*).Instead this method returns an Option + * containing the GOTO that needs to be eliminated. + * + * (*) The ASM instruction iterator (used in the caller [[simplifyJumps]]) has an undefined + * behavior if the successor of the current instruction is removed, which may be the case here + */ + private def simplifyBranchOverGoto(method: MethodNode, instruction: AbstractInsnNode): Option[JumpInsnNode] = instruction match { + case ConditionalJump(jump) => + // don't skip over labels, see doc comment + nextExecutableInstruction(jump, alsoKeep = _.isInstanceOf[LabelNode]) match { + case Some(Goto(goto)) => + if (nextExecutableInstruction(goto, alsoKeep = Set(jump.label)) == Some(jump.label)) { + val newJump = new JumpInsnNode(negateJumpOpcode(jump.getOpcode), goto.label) + method.instructions.set(jump, newJump) + Some(goto) + } else None + + case _ => None + } + case _ => None + } + + /** + * Inlines xRETURN and ATHROW + * + * GOTO l; [any ops]; l: xRETURN/ATHROW + * => xRETURN/ATHROW; [any ops]; l: xRETURN/ATHROW + * + * inlining is only done if the GOTO instruction is not part of a try block, otherwise the + * rewrite might change the behavior. For xRETURN, the reason is that return insructions may throw + * an IllegalMonitorStateException, as described here: + * http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.return + */ + private def simplifyGotoReturn(method: MethodNode, instruction: AbstractInsnNode, inTryBlock: Boolean): Boolean = !inTryBlock && (instruction match { + case Goto(jump) => + nextExecutableInstruction(jump.label) match { + case Some(target) => + if (isReturn(target) || target.getOpcode == Opcodes.ATHROW) { + method.instructions.set(jump, target.clone(null)) + true + } else false + + case _ => false + } + case _ => false + }) } diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index c59d56d8f8..d6650595eb 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -211,21 +211,26 @@ trait ScalaSettings extends AbsScalaSettings val Ydelambdafy = ChoiceSetting ("-Ydelambdafy", "strategy", "Strategy used for translating lambdas into JVM code.", List("inline", "method"), "inline") object YoptChoices extends MultiChoiceEnumeration { - val unreachableCode = Choice("unreachable-code", "Eliminate unreachable code") + val unreachableCode = Choice("unreachable-code", "Eliminate unreachable code, exception handlers protecting no instructions, debug information of eliminated variables.") + val simplifyJumps = Choice("simplify-jumps", "Simplify branching instructions, eliminate unnecessery ones.") + val recurseUnreachableJumps = Choice("recurse-unreachable-jumps", "Recursively apply unreachable-code and simplify-jumps (if enabled) until reaching a fixpoint.") + val emptyLineNumbers = Choice("empty-line-numbers", "Eliminate unnecessary line number information.") + val emptyLabels = Choice("empty-labels", "Eliminate and collapse redundant labels in the bytecode.") + val compactLocals = Choice("compact-locals", "Eliminate empty slots in the sequence of local variables.") - val lNone = Choice("l:none", "Don't enable any optimizations") + val lNone = Choice("l:none", "Don't enable any optimizations.") private val defaultChoices = List(unreachableCode) - val lDefault = Choice("l:default", "Enable default optimizations: "+ defaultChoices.mkString(","), expandsTo = defaultChoices) + val lDefault = Choice("l:default", "Enable default optimizations: "+ defaultChoices.mkString(","), expandsTo = defaultChoices) - private val methodChoices = List(lDefault) - val lMethod = Choice("l:method", "Intra-method optimizations: "+ methodChoices.mkString(","), expandsTo = methodChoices) + private val methodChoices = List(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels, compactLocals) + val lMethod = Choice("l:method", "Enable intra-method optimizations: "+ methodChoices.mkString(","), expandsTo = methodChoices) private val projectChoices = List(lMethod) - val lProject = Choice("l:project", "Cross-method optimizations within the current project: "+ projectChoices.mkString(","), expandsTo = projectChoices) + val lProject = Choice("l:project", "Enable cross-method optimizations within the current project: "+ projectChoices.mkString(","), expandsTo = projectChoices) private val classpathChoices = List(lProject) - val lClasspath = Choice("l:classpath", "Cross-method optmizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices) + val lClasspath = Choice("l:classpath", "Enable cross-method optimizations across the entire classpath: "+ classpathChoices.mkString(","), expandsTo = classpathChoices) } val Yopt = MultiChoiceSetting( @@ -234,7 +239,12 @@ trait ScalaSettings extends AbsScalaSettings descr = "Enable optimizations", domain = YoptChoices) - def YoptUnreachableCode: Boolean = !Yopt.isSetByUser || Yopt.contains(YoptChoices.unreachableCode) + def YoptUnreachableCode = !Yopt.isSetByUser || Yopt.contains(YoptChoices.unreachableCode) + def YoptSimplifyJumps = Yopt.contains(YoptChoices.simplifyJumps) + def YoptRecurseUnreachableJumps = Yopt.contains(YoptChoices.recurseUnreachableJumps) + def YoptEmptyLineNumbers = Yopt.contains(YoptChoices.emptyLineNumbers) + def YoptEmptyLabels = Yopt.contains(YoptChoices.emptyLabels) + def YoptCompactLocals = Yopt.contains(YoptChoices.compactLocals) private def removalIn212 = "This flag is scheduled for removal in 2.12. If you have a case where you need this flag then please report a bug." diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala index b892eb36cf..c1c5a71b83 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala @@ -7,6 +7,8 @@ import scala.reflect.io.VirtualDirectory import scala.tools.asm.Opcodes import scala.tools.asm.tree.{AbstractInsnNode, LabelNode, ClassNode, MethodNode} import scala.tools.cmd.CommandLineParser +import scala.tools.nsc.backend.jvm.opt.LocalOpt +import scala.tools.nsc.settings.{MutableSettings, ScalaSettings} import scala.tools.nsc.{Settings, Global} import scala.tools.partest.ASMConverters import scala.collection.JavaConverters._ @@ -79,4 +81,23 @@ object CodeGenTools { def getSingleMethod(classNode: ClassNode, name: String): Method = convertMethod(classNode.methods.asScala.toList.find(_.name == name).get) + + def assertHandlerLabelPostions(h: ExceptionHandler, instructions: List[Instruction], startIndex: Int, endIndex: Int, handlerIndex: Int): Unit = { + val insVec = instructions.toVector + assertTrue(h.start == insVec(startIndex) && h.end == insVec(endIndex) && h.handler == insVec(handlerIndex)) + } + + val localOpt = { + val settings = new MutableSettings(msg => throw new IllegalArgumentException(msg)) + settings.processArguments(List("-Yopt:l:method"), processAll = true) + new LocalOpt(settings) + } + + import scala.language.implicitConversions + + implicit def aliveInstruction(ins: Instruction): (Instruction, Boolean) = (ins, true) + + implicit class MortalInstruction(val ins: Instruction) extends AnyVal { + def dead: (Instruction, Boolean) = (ins, false) + } } diff --git a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala index 2fb5bb8052..89900291ca 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/DirectCompileTest.scala @@ -10,13 +10,12 @@ import scala.tools.partest.ASMConverters._ @RunWith(classOf[JUnit4]) class DirectCompileTest { - val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode") + val compiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:method") @Test def testCompile(): Unit = { val List(("C.class", bytes)) = compile(compiler)( - """ - |class C { + """class C { | def f = 1 |} """.stripMargin) @@ -26,19 +25,12 @@ class DirectCompileTest { @Test def testCompileClasses(): Unit = { - val List(cClass, cModuleClass) = compileClasses(compiler)( - """ - |class C - |object C - """.stripMargin) + val List(cClass, cModuleClass) = compileClasses(compiler)("class C; object C") assertTrue(cClass.name == "C") assertTrue(cModuleClass.name == "C$") - val List(dMirror, dModuleClass) = compileClasses(compiler)( - """ - |object D - """.stripMargin) + val List(dMirror, dModuleClass) = compileClasses(compiler)("object D") assertTrue(dMirror.name == "D") assertTrue(dModuleClass.name == "D$") @@ -47,35 +39,35 @@ class DirectCompileTest { @Test def testCompileMethods(): Unit = { val List(f, g) = compileMethods(compiler)( - """ - |def f = 10 + """def f = 10 |def g = f """.stripMargin) assertTrue(f.name == "f") assertTrue(g.name == "g") - assertTrue(instructionsFromMethod(f).dropNonOp === + assertSameCode(instructionsFromMethod(f).dropNonOp, List(IntOp(BIPUSH, 10), Op(IRETURN))) - assertTrue(instructionsFromMethod(g).dropNonOp === - List(VarOp(ALOAD, 0), Invoke(INVOKEVIRTUAL, "C", "f", "()I", false), Op(IRETURN))) + assertSameCode(instructionsFromMethod(g).dropNonOp, + List(VarOp(ALOAD, 0), Invoke(INVOKEVIRTUAL, "C", "f", "()I", itf = false), Op(IRETURN))) } @Test def testDropNonOpAliveLabels(): Unit = { + // makes sure that dropNoOp doesn't drop labels that are being used val List(f) = compileMethods(compiler)("""def f(x: Int) = if (x == 0) "a" else "b"""") - assertTrue(instructionsFromMethod(f).dropNonOp === List( - VarOp(ILOAD, 1), - Op(ICONST_0), - Jump(IF_ICMPEQ, Label(6)), - Jump(GOTO, Label(10)), - Label(6), - Ldc(LDC, "a"), - Jump(GOTO, Label(13)), - Label(10), - Ldc(LDC, "b"), - Label(13), - Op(ARETURN) + assertSameCode(instructionsFromMethod(f).dropLinesFrames, List( + Label(0), + VarOp(ILOAD, 1), + Op(ICONST_0), + Jump(IF_ICMPNE, + Label(7)), + Ldc(LDC, "a"), + Op(ARETURN), + Label(7), + Ldc(LDC, "b"), + Op(ARETURN), + Label(11) )) } } diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala new file mode 100644 index 0000000000..fc748196d0 --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/CompactLocalVariablesTest.scala @@ -0,0 +1,80 @@ +package scala.tools.nsc +package backend.jvm +package opt + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ + +import CodeGenTools._ +import scala.tools.partest.ASMConverters +import ASMConverters._ + +@RunWith(classOf[JUnit4]) +class CompactLocalVariablesTest { + + // recurse-unreachable-jumps is required for eliminating catch blocks, in the first dce round they + // are still live.only after eliminating the empty handler the catch blocks become unreachable. + val methodOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code,recurse-unreachable-jumps,compact-locals") + val noCompactVarsCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code,recurse-unreachable-jumps") + + @Test + def compactUnused(): Unit = { + val code = + """def f: Double = { + | try { } + | catch { + | case _: Throwable => + | // eliminated by dce + | val i = 1 + | val d = 1d + | val f = 1f + | val l = 1l + | } + | + | val i = 1 // variable index 1 (it's an instance method, so at index 0 we have `this`) + | val d = 1d // 2,3 + | val f = 1f // 4 + | val l = 1l // 5,6 + | + | try { } + | catch { + | case _: Throwable => + | // eliminated by dce + | val i = 1 + | val d = 1d + | val f = 1f + | val l = 1l + | } + | + | val ii = 1 // 7 + | val dd = 1d // 8,9 + | val ff = 1f // 10 + | val ll = 1l // 11,12 + | + | i + ii + d + dd + f + ff + l + ll + |} + |""".stripMargin + + val List(noCompact) = compileMethods(noCompactVarsCompiler)(code) + val List(withCompact) = compileMethods(methodOptCompiler)(code) + + // code is the same, except for local var indices + assertTrue(noCompact.instructions.size == withCompact.instructions.size) + + val varOpSlots = convertMethod(withCompact).instructions collect { + case VarOp(_, v) => v + } + assertTrue(varOpSlots.toString, varOpSlots == List(1, 2, 4, 5, 7, 8, 10, 11, // stores + 1, 7, 2, 8, 4, 10, 5, 11)) // loads + + // the local variables descriptor table is cleaned up to remove stale entries after dce, + // also when the slots are not compacted + assertTrue(noCompact.localVariables.size == withCompact.localVariables.size) + + assertTrue(noCompact.maxLocals == 25) + assertTrue(withCompact.maxLocals == 13) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala index 57fa1a7b66..7d83c54b5b 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyExceptionHandlersTest.scala @@ -26,7 +26,7 @@ class EmptyExceptionHandlersTest { Op(RETURN) ) assertTrue(convertMethod(asmMethod).handlers.length == 1) - LocalOpt.removeEmptyExceptionHandlers(asmMethod) + localOpt.removeEmptyExceptionHandlers(asmMethod) assertTrue(convertMethod(asmMethod).handlers.isEmpty) } @@ -35,12 +35,8 @@ class EmptyExceptionHandlersTest { val handlers = List(ExceptionHandler(Label(1), Label(2), Label(2), Some(exceptionDescriptor))) val asmMethod = genMethod(handlers = handlers)( Label(1), // nops only - Op(NOP), - Op(NOP), Jump(GOTO, Label(3)), - Op(NOP), Label(3), - Op(NOP), Jump(GOTO, Label(4)), Label(2), // handler @@ -51,7 +47,7 @@ class EmptyExceptionHandlersTest { Op(RETURN) ) assertTrue(convertMethod(asmMethod).handlers.length == 1) - LocalOpt.removeEmptyExceptionHandlers(asmMethod) + localOpt.removeEmptyExceptionHandlers(asmMethod) assertTrue(convertMethod(asmMethod).handlers.isEmpty) } diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala new file mode 100644 index 0000000000..8c0168826e --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/EmptyLabelsAndLineNumbersTest.scala @@ -0,0 +1,99 @@ +package scala.tools.nsc +package backend.jvm +package opt + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ +import scala.tools.testing.AssertUtil._ + +import CodeGenTools._ +import scala.tools.partest.ASMConverters +import ASMConverters._ + +@RunWith(classOf[JUnit4]) +class EmptyLabelsAndLineNumbersTest { + @Test + def removeEmptyLineNumbers(): Unit = { + val ops = List[(Instruction, Boolean)]( + Label(1), + LineNumber(1, Label(1)), + Label(2), + Label(3), + Op(RETURN), + + Label(4), + LineNumber(4, Label(4)).dead, + LineNumber(5, Label(4)), + Op(RETURN), + + Label(5), + LineNumber(6, Label(5)).dead, + Label(6), + Label(7), + LineNumber(7, Label(7)), + Op(RETURN), + + Label(9), + LineNumber(8, Label(9)).dead, + Label(10) + ) + + val method = genMethod()(ops.map(_._1): _*) + assertTrue(localOpt.removeEmptyLineNumbers(method)) + assertSameCode(instructionsFromMethod(method), ops.filter(_._2).map(_._1)) + } + + @Test + def badlyLocatedLineNumbers(): Unit = { + def t(ops: Instruction*) = + assertThrows[AssertionError](localOpt.removeEmptyLineNumbers(genMethod()(ops: _*))) + + // line numbers have to be right after their referenced label node + t(LineNumber(0, Label(1)), Label(1)) + t(Label(0), Label(1), LineNumber(0, Label(0))) + } + + @Test + def removeEmptyLabels(): Unit = { + val handler = List(ExceptionHandler(Label(4), Label(5), Label(6), Some("java/lang/Throwable"))) + def ops(target1: Int, target2: Int, target3: Int, target4: Int, target5: Int, target6: Int) = List[(Instruction, Boolean)]( + Label(1), + Label(2).dead, + Label(3).dead, + LineNumber(3, Label(target1)), + VarOp(ILOAD, 1), + Jump(IFGE, Label(target2)), + + Label(4), + Label(5).dead, + Label(6).dead, + VarOp(ILOAD, 2), + Jump(IFGE, Label(target3)), + + Label(7), + Label(8).dead, + Label(9).dead, + Op(RETURN), + + LookupSwitch(LOOKUPSWITCH, Label(target4), List(1,2), List(Label(target4), Label(target5))), + TableSwitch(TABLESWITCH, 1, 2, Label(target4), List(Label(target4), Label(target5))), + + Label(10), + LineNumber(10, Label(10)), + Label(11).dead, + LineNumber(12, Label(target6)) + ) + + val method = genMethod(handlers = handler)(ops(2, 3, 8, 8, 9, 11).map(_._1): _*) + assertTrue(localOpt.removeEmptyLabelNodes(method)) + val m = convertMethod(method) + assertSameCode(m.instructions, ops(1, 1, 7, 7, 7, 10).filter(_._2).map(_._1)) + assertTrue(m.handlers match { + case List(ExceptionHandler(Label(4), Label(4), Label(4), _)) => true + case _ => false + }) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala new file mode 100644 index 0000000000..5b0f0f238a --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala @@ -0,0 +1,83 @@ +package scala.tools.nsc +package backend.jvm +package opt + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ + +import scala.tools.testing.AssertUtil._ + +import CodeGenTools._ +import scala.tools.partest.ASMConverters +import ASMConverters._ + +@RunWith(classOf[JUnit4]) +class MethodLevelOpts { + val methodOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:method") + + def wrapInDefault(code: Instruction*) = List(Label(0), LineNumber(1, Label(0))) ::: code.toList ::: List(Label(1)) + + @Test + def eliminateEmptyTry(): Unit = { + val code = "def f = { try {} catch { case _: Throwable => 0; () }; 1 }" + assertSameCode(singleMethodInstructions(methodOptCompiler)(code), wrapInDefault(Op(ICONST_1), Op(IRETURN))) + } + + @Test + def cannotEliminateLoadBoxedUnit(): Unit = { + // the compiler inserts a boxed into the try block. it's therefore non-empty (and live) and not eliminated. + val code = "def f = { try {} catch { case _: Throwable => 0 }; 1 }" + val m = singleMethod(methodOptCompiler)(code) + assertTrue(m.handlers.length == 1) + assertSameCode(m.instructions.take(3), List(Label(0), LineNumber(1, Label(0)), Field(GETSTATIC, "scala/runtime/BoxedUnit", "UNIT", "Lscala/runtime/BoxedUnit;"))) + } + + @Test + def inlineThrowInCatchNotTry(): Unit = { + // the try block does not contain the `ATHROW` instruction, but in the catch block, `ATHROW` is inlined + val code = "def f(e: Exception) = throw { try e catch { case _: Throwable => e } }" + val m = singleMethod(methodOptCompiler)(code) + assertHandlerLabelPostions(m.handlers.head, m.instructions, 0, 3, 5) + assertSameCode(m.instructions, + wrapInDefault(VarOp(ALOAD, 1), Label(3), Op(ATHROW), Label(5), FrameEntry(4, List(), List("java/lang/Throwable")), Op(POP), VarOp(ALOAD, 1), Op(ATHROW)) + ) + } + + @Test + def inlineReturnInCachtNotTry(): Unit = { + val code = "def f: Int = return { try 1 catch { case _: Throwable => 2 } }" + // cannot inline the IRETURN into the try block (because RETURN may throw IllegalMonitorState) + val m = singleMethod(methodOptCompiler)(code) + assertHandlerLabelPostions(m.handlers.head, m.instructions, 0, 3, 5) + assertSameCode(m.instructions, + wrapInDefault(Op(ICONST_1), Label(3), Op(IRETURN), Label(5), FrameEntry(4, List(), List("java/lang/Throwable")), Op(POP), Op(ICONST_2), Op(IRETURN))) + } + + @Test + def simplifyJumpsInTryCatchFinally(): Unit = { + val code = + """def f: Int = + | try { + | return 1 + | } catch { + | case _: Throwable => + | return 2 + | } finally { + | return 2 + | // dead + | val x = try 10 catch { case _: Throwable => 11 } + | println(x) + | } + """.stripMargin + val m = singleMethod(methodOptCompiler)(code) + assertTrue(m.handlers.length == 2) + assertSameCode(m.instructions.dropNonOp, // drop line numbers and lables that are only used by line numbers + + // one single label left :-) + List(Op(ICONST_1), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), Op(POP), Op(ICONST_2), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), VarOp(ASTORE, 3), Op(ICONST_2), Op(IRETURN), Label(20), Op(ICONST_2), Op(IRETURN)) + ) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala new file mode 100644 index 0000000000..360fa1d23d --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/SimplifyJumpsTest.scala @@ -0,0 +1,221 @@ +package scala.tools.nsc +package backend.jvm +package opt + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ + +import CodeGenTools._ +import scala.tools.partest.ASMConverters +import ASMConverters._ + +@RunWith(classOf[JUnit4]) +class SimplifyJumpsTest { + @Test + def simpleGotoReturn(): Unit = { + val ops = List( + Jump(GOTO, Label(2)), // replaced by RETURN + Op(ICONST_1), // need some code, otherwise removeJumpToSuccessor kicks in + Op(POP), + Label(1), // multiple labels OK + Label(2), + Label(3), + Op(RETURN) + ) + val method = genMethod()(ops: _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), Op(RETURN) :: ops.tail) + } + + @Test + def simpleGotoThrow(): Unit = { + val rest = List( + Op(ICONST_1), // need some code, otherwise removeJumpToSuccessor kicks in + Op(POP), + Label(1), + Label(2), + Label(3), + Op(ATHROW) + ) + val method = genMethod()( + Op(ACONST_NULL) :: + Jump(GOTO, Label(2)) :: // replaced by ATHROW + rest: _* + ) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), Op(ACONST_NULL) :: Op(ATHROW) :: rest) + } + + @Test + def gotoThrowInTry(): Unit = { + val handler = List(ExceptionHandler(Label(1), Label(2), Label(4), Some("java/lang/Throwable"))) + val initialInstrs = List( + Label(1), + Op(ACONST_NULL), + Jump(GOTO, Label(3)), // not by ATHROW (would move the ATHROW into a try block) + Label(2), + Op(ICONST_1), // need some code, otherwise removeJumpToSuccessor kicks in + Op(POP), + Label(3), + Op(ATHROW), + Label(4), + Op(POP), + Op(RETURN) + ) + val method = genMethod(handlers = handler)(initialInstrs: _*) + assertFalse(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), initialInstrs) + + val optMethod = genMethod()(initialInstrs: _*) // no handler + assertTrue(localOpt.simplifyJumps(optMethod)) + assertSameCode(instructionsFromMethod(optMethod).take(3), List(Label(1), Op(ACONST_NULL), Op(ATHROW))) + } + + @Test + def simplifyBranchOverGoto(): Unit = { + val begin = List( + VarOp(ILOAD, 1), + Jump(IFGE, Label(2)) + ) + val rest = List( + Jump(GOTO, Label(3)), + Label(11), // other labels here are allowed + Label(2), + VarOp(ILOAD, 1), + Op(RETURN), + Label(3), + VarOp(ILOAD, 1), + Op(IRETURN) + ) + val method = genMethod()(begin ::: rest: _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode( + instructionsFromMethod(method), + List(VarOp(ILOAD, 1), Jump(IFLT, Label(3))) ::: rest.tail ) + + // no label allowed between begin and rest. if there's another label, then there could be a + // branch that label. eliminating the GOTO would change the behavior. + val nonOptMethod = genMethod()(begin ::: Label(22) :: rest: _*) + assertFalse(localOpt.simplifyJumps(nonOptMethod)) + } + + @Test + def ensureGotoRemoved(): Unit = { + def code(jumps: Instruction*) = List( + VarOp(ILOAD, 1)) ::: jumps.toList ::: List( + Label(2), + + Op(RETURN), + Label(3), + Op(RETURN) + ) + + // ensures that the goto is safely removed. ASM supports removing while iterating, but not the + // next element of the current. Here, the current is the IFGE, the next is the GOTO. + val method = genMethod()(code(Jump(IFGE, Label(2)), Jump(GOTO, Label(3))): _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), code(Jump(IFLT, Label(3)))) + } + + @Test + def removeJumpToSuccessor(): Unit = { + val ops = List( + Jump(GOTO, Label(1)), + Label(11), + Label(1), + Label(2), + VarOp(ILOAD, 1), + Op(IRETURN) + ) + val method = genMethod()(ops: _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), ops.tail) + } + + @Test + def collapseJumpChains(): Unit = { + def ops(target1: Int, target2: Int, target3: Int) = List( + VarOp(ILOAD, 1), + Jump(IFGE, Label(target1)), // initially 1, then 3 + VarOp(ILOAD, 1), + Op(IRETURN), + + Label(2), + Jump(GOTO, Label(target3)), + + Label(1), + Jump(GOTO, Label(target2)), // initially 2, then 3 + + VarOp(ILOAD, 1), // some code to prevent jumpToSuccessor optimization (once target2 is replaced by 3) + Op(RETURN), + + Label(3), + VarOp(ILOAD, 1), + Op(IRETURN) + ) + val method = genMethod()(ops(1, 2, 3): _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), ops(3, 3, 3)) + } + + @Test + def collapseJumpChainLoop(): Unit = { + def ops(target: Int) = List( + VarOp(ILOAD, 1), + Jump(IFGE, Label(target)), + + Label(4), + Jump(GOTO, Label(3)), + + VarOp(ILOAD, 1), // some code to prevent jumpToSuccessor (label 3) + Op(IRETURN), + + Label(3), + Jump(GOTO, Label(4)), + + Label(2), + Jump(GOTO, Label(3)) + ) + + val method = genMethod()(ops(2): _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), ops(3)) + } + + @Test + def simplifyThenElseSameTarget(): Unit = { + def ops(jumpOp: Instruction) = List( + VarOp(ILOAD, 1), + jumpOp, + Label(2), + Jump(GOTO, Label(1)), + + VarOp(ILOAD, 1), // some code to prevent jumpToSuccessor (label 1) + Op(IRETURN), + + Label(1), + VarOp(ILOAD, 1), + Op(IRETURN) + ) + + val method = genMethod()(ops(Jump(IFGE, Label(1))): _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), ops(Op(POP))) + } + + @Test + def thenElseSameTargetLoop(): Unit = { + def ops(br: List[Instruction]) = List( + VarOp(ILOAD, 1), + VarOp(ILOAD, 2)) ::: br ::: List( + Label(1), + Jump(GOTO, Label(1)) + ) + val method = genMethod()(ops(List(Jump(IF_ICMPGE, Label(1)))): _*) + assertTrue(localOpt.simplifyJumps(method)) + assertSameCode(instructionsFromMethod(method), ops(List(Op(POP), Op(POP)))) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala index a3bd7ae6fe..4a45dd9138 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala @@ -16,12 +16,20 @@ import ASMConverters._ @RunWith(classOf[JUnit4]) class UnreachableCodeTest { - import UnreachableCodeTest._ + + def assertEliminateDead(code: (Instruction, Boolean)*): Unit = { + val method = genMethod()(code.map(_._1): _*) + localOpt.removeUnreachableCodeImpl(method, "C") + val nonEliminated = instructionsFromMethod(method) + val expectedLive = code.filter(_._2).map(_._1).toList + assertSameCode(nonEliminated, expectedLive) + } // jvm-1.6 enables emitting stack map frames, which impacts the code generation wrt dead basic blocks, // see comment in BCodeBodyBuilder - val dceCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code") - val noOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:none") + val methodOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:method") + val dceCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:unreachable-code") + val noOptCompiler = newCompiler(extraArgs = "-target:jvm-1.6 -Ybackend:GenBCode -Yopt:l:none") // jvm-1.5 disables computing stack map frames, and it emits dead code as-is. val noOptNoFramesCompiler = newCompiler(extraArgs = "-target:jvm-1.5 -Ybackend:GenBCode -Yopt:l:none") @@ -48,8 +56,8 @@ class UnreachableCodeTest { @Test def eliminateNop(): Unit = { assertEliminateDead( - // not dead, since visited by data flow analysis. need a different opt to eliminate it. - Op(NOP), + // reachable, but removed anyway. + Op(NOP).dead, Op(RETURN), Op(NOP).dead ) @@ -136,28 +144,31 @@ class UnreachableCodeTest { @Test def eliminateDeadCatchBlocks(): Unit = { + // the Label(1) is live: it's used in the local variable descriptor table (local variable "this" has a range from 0 to 1). + def wrapInDefault(code: Instruction*) = List(Label(0), LineNumber(1, Label(0))) ::: code.toList ::: List(Label(1)) + val code = "def f: Int = { return 0; try { 1 } catch { case _: Exception => 2 } }" - assertSameCode(singleMethodInstructions(dceCompiler)(code).dropNonOp, - List(Op(ICONST_0), Op(IRETURN))) + val m = singleMethod(dceCompiler)(code) + assertTrue(m.handlers.isEmpty) // redundant (if code is gone, handler is gone), but done once here for extra safety + assertSameCode(m.instructions, + wrapInDefault(Op(ICONST_0), Op(IRETURN))) val code2 = "def f: Unit = { try { } catch { case _: Exception => () }; () }" - // DCE only removes dead basic blocks, but not NOPs, and also not useless jumps - assertSameCode(singleMethodInstructions(dceCompiler)(code2).dropNonOp, - List(Op(NOP), Jump(GOTO, Label(33)), Label(33), Op(RETURN))) + // requires fixpoint optimization of methodOptCompiler (dce alone is not enough): first the handler is eliminated, then it's dead catch block. + assertSameCode(singleMethodInstructions(methodOptCompiler)(code2), wrapInDefault(Op(RETURN))) val code3 = "def f: Unit = { try { } catch { case _: Exception => try { } catch { case _: Exception => () } }; () }" - assertSameCode(singleMethodInstructions(dceCompiler)(code3).dropNonOp, - List(Op(NOP), Jump(GOTO, Label(33)), Label(33), Op(RETURN))) + assertSameCode(singleMethodInstructions(methodOptCompiler)(code3), wrapInDefault(Op(RETURN))) + // this example requires two iterations to get rid of the outer handler. + // the first iteration of DCE cannot remove the inner handler. then the inner (empty) handler is removed. + // then the second iteration of DCE removes the inner catch block, and then the outer handler is removed. val code4 = "def f: Unit = { try { try { } catch { case _: Exception => () } } catch { case _: Exception => () }; () }" - assertSameCode(singleMethodInstructions(dceCompiler)(code4).dropNonOp, - List(Op(NOP), Jump(GOTO, Label(4)), Label(4), Jump(GOTO, Label(7)), Label(7), Op(RETURN))) + assertSameCode(singleMethodInstructions(methodOptCompiler)(code4), wrapInDefault(Op(RETURN))) } @Test // test the dce-testing tools def metaTest(): Unit = { - assertEliminateDead() // no instructions - assertThrows[AssertionError]( assertEliminateDead(Op(RETURN).dead), _.contains("Expected: List()\nActual : List(Op(RETURN))") @@ -198,20 +209,3 @@ class UnreachableCodeTest { List(FrameEntry(F_FULL, List(INTEGER, DOUBLE, Label(1)), List("java/lang/Object", Label(3))), Label(1), Label(3))) } } - -object UnreachableCodeTest { - import scala.language.implicitConversions - implicit def aliveInstruction(ins: Instruction): (Instruction, Boolean) = (ins, true) - - implicit class MortalInstruction(val ins: Instruction) extends AnyVal { - def dead: (Instruction, Boolean) = (ins, false) - } - - def assertEliminateDead(code: (Instruction, Boolean)*): Unit = { - val cls = wrapInClass(genMethod()(code.map(_._1): _*)) - LocalOpt.removeUnreachableCode(cls) - val nonEliminated = instructionsFromMethod(cls.methods.get(0)) - val expectedLive = code.filter(_._2).map(_._1).toList - assertSameCode(nonEliminated, expectedLive) - } -} |