diff options
author | Lukas Rytz <lukas.rytz@gmail.com> | 2014-10-13 14:34:24 +0200 |
---|---|---|
committer | Lukas Rytz <lukas.rytz@gmail.com> | 2014-11-04 14:11:21 +0100 |
commit | d39525ac06c8d319b43d3388d624fb2c1dcbd601 (patch) | |
tree | ba1f889e9df2382d9717aa7bfb895bcf7d683bd9 | |
parent | be82759d7f56f1d78b4123fec0706f4f4565133e (diff) | |
download | scala-d39525ac06c8d319b43d3388d624fb2c1dcbd601.tar.gz scala-d39525ac06c8d319b43d3388d624fb2c1dcbd601.tar.bz2 scala-d39525ac06c8d319b43d3388d624fb2c1dcbd601.zip |
GenBCode: Compact local variable slots
After eliminating unreachable code, there may be unused local varaible
slots. Such gaps increase the method's frame size unnecessarily.
The optimization does not attempt to re-use the same local variable
slot for non-overlapping locals (proper register allocation):
def f(b: Boolean) = if (b) { val x = e; x } else { val y = e; y }
x and y will not use the same slot, even though they could.
This was originally implemented by Miguel in
https://github.com/lrytz/scala/commit/09c40359338f8770e4f99d045999af062112973e
4 files changed, 191 insertions, 18 deletions
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala index c206927db9..fd14083cf7 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala @@ -36,6 +36,14 @@ object BytecodeUtils { } } + 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. @@ -47,6 +55,11 @@ object BytecodeUtils { (op >= Opcodes.IFEQ && op <= Opcodes.IF_ACMPNE) || op == Opcodes.IFNULL || op == Opcodes.IFNONNULL } + 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] = { 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 29754d5500..8fff478326 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala @@ -122,8 +122,11 @@ class LocalOpt(settings: ScalaSettings) { recurse = settings.YoptRecurseUnreachableJumps && (jumpsChanged || liveHandlerRemoved) } - // Removing stale local variable descriptors is required for correctness of unreachable-code, therefore no dedicated setting - val localsRemoved = if (settings.YoptUnreachableCode) removeUnusedLocalVariableNodes(method) else false + // (*) 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 @@ -214,7 +217,7 @@ class LocalOpt(settings: ScalaSettings) { * the same index, but distinct start / end ranges are different variables, they may have not the * same type or name. */ - 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 if v.`var` == varIndex => true @@ -224,23 +227,98 @@ class LocalOpt(settings: ScalaSettings) { 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 } /** + * 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).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 minLenght = if (isWide) index + 2 else index + 1 + for (i <- renumber.length until minLenght) 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, otherwsie renumber(x) = -1. if the variable is wide (long or doulbe), 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 * framework only computes these values during bytecode generation. * diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 2406b9e66b..2c9d101106 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -215,20 +215,21 @@ trait ScalaSettings extends AbsScalaSettings 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.") 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(unreachableCode, simplifyJumps, recurseUnreachableJumps, emptyLineNumbers, emptyLabels) - val lMethod = Choice("l:method", "Enable 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", "Enable 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", "Enable 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( @@ -242,6 +243,7 @@ trait ScalaSettings extends AbsScalaSettings 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/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) + } +} |