diff options
author | Lukas Rytz <lukas.rytz@gmail.com> | 2014-08-22 09:50:44 +0200 |
---|---|---|
committer | Lukas Rytz <lukas.rytz@gmail.com> | 2014-09-09 23:56:52 +0200 |
commit | 90781e874adb1af44a43d3e64d403230970b423d (patch) | |
tree | df7e054a165e0026e6b69bee03c13ea670d96990 | |
parent | a3dfb43263a9d29d47f34ad8d183f7a01f3a1ea7 (diff) | |
download | scala-90781e874adb1af44a43d3e64d403230970b423d.tar.gz scala-90781e874adb1af44a43d3e64d403230970b423d.tar.bz2 scala-90781e874adb1af44a43d3e64d403230970b423d.zip |
Eliminate unreachable code in GenBCode
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
information for reachable instructions. Instructions for which no
data is available after the analyis are unreachable.
There's one issue with the ASM framework (or the way we use it): Data
flow analysis requires the maxlocals and maxstack of each method to be
computed. The ASM framework calculates these maxes only when
writing the classfiles, not during code generation. In order to run
DCE, we therefore run a MethodWriter beforehand on every method. This
assings the MethodNode's maxStack/maxLocals, but it does more work
(writes the instructions to a byte array).
This is also what Miguel uses on his branch. The change is basically
the same as https://github.com/lrytz/scala/commit/bfadf92c20.
We could probably make this faster (and allocate less memory) by
hacking the ASM framework: create a subclass of MethodWriter with a
/dev/null byteVector. Another option would be to create a separate
visitor for computing those values, duplicating the functionality from
the MethodWriter.
For now, I added some timers to be able to measure the time DCE takes.
Here's compiling the library with -Ystatistics:jvm
time in backend : 1 spans, 6597ms
bcode initialization : 1 spans, 8ms (0.1%)
code generation : 1 spans, 4580ms (69.4%)
dead code elimination : 3771 spans, 742ms (11.2%)
classfile writing : 1 spans, 879ms (13.3%)
6 files changed, 134 insertions, 4 deletions
diff --git a/src/asm/scala/tools/asm/MethodWriter.java b/src/asm/scala/tools/asm/MethodWriter.java index 0c4130e499..d30e04c625 100644 --- a/src/asm/scala/tools/asm/MethodWriter.java +++ b/src/asm/scala/tools/asm/MethodWriter.java @@ -37,7 +37,7 @@ package scala.tools.asm; * @author Eric Bruneton * @author Eugene Kuleshov */ -class MethodWriter extends MethodVisitor { +public class MethodWriter extends MethodVisitor { /** * Pseudo access flag used to denote constructors. @@ -235,11 +235,19 @@ class MethodWriter extends MethodVisitor { */ private int maxStack; + public int getMaxStack() { + return maxStack; + } + /** * Maximum number of local variables for this method. */ private int maxLocals; + public int getMaxLocals() { + return maxLocals; + } + /** * Number of local variables in the current stack map frame. */ diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala index 7bf61b4f51..53ac5bfdc7 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala @@ -713,6 +713,8 @@ abstract class BTypes { // TODO @lry I don't really understand the reasoning here. // Both this and other are classes. The code takes (transitively) all superclasses and // finds the first common one. + // MOST LIKELY the answer can be found here, see the comments and links by Miguel: + // - https://issues.scala-lang.org/browse/SI-3872 firstCommonSuffix(this :: this.superClassesTransitive, other :: other.superClassesTransitive) } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala new file mode 100644 index 0000000000..921aef7aca --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/BackendStats.scala @@ -0,0 +1,19 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2014 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm + +import scala.reflect.internal.util.Statistics + +object BackendStats { + import Statistics.{newTimer, newSubTimer} + val bcodeTimer = newTimer("time in backend", "jvm") + + val bcodeInitTimer = newSubTimer("bcode initialization", bcodeTimer) + val bcodeGenStat = newSubTimer("code generation", bcodeTimer) + val bcodeDceTimer = newSubTimer("dead code elimination", bcodeTimer) + val bcodeWriteTimer = newSubTimer("classfile writing", bcodeTimer) +} diff --git a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala index 0a7c894a69..a7cc1f69cf 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/GenBCode.scala @@ -11,6 +11,7 @@ package jvm import scala.collection.{ mutable, immutable } import scala.annotation.switch +import scala.reflect.internal.util.Statistics import scala.tools.asm @@ -222,8 +223,12 @@ abstract class GenBCode extends BCodeSyncAndTry { return } else { - try { addToQ3(item) } - catch { + try { + val dceStart = Statistics.startTimer(BackendStats.bcodeDceTimer) + opt.LocalOpt.removeUnreachableCode(item.plain) + Statistics.stopTimer(BackendStats.bcodeDceTimer, dceStart) + addToQ3(item) + } catch { case ex: Throwable => ex.printStackTrace() error(s"Error while emitting ${item.plain.name}\n${ex.getMessage}") @@ -272,10 +277,13 @@ abstract class GenBCode extends BCodeSyncAndTry { * */ override def run() { + val bcodeStart = Statistics.startTimer(BackendStats.bcodeTimer) + val initStart = Statistics.startTimer(BackendStats.bcodeInitTimer) arrivalPos = 0 // just in case scalaPrimitives.init() bTypes.intializeCoreBTypes() + Statistics.stopTimer(BackendStats.bcodeInitTimer, initStart) // initBytecodeWriter invokes fullName, thus we have to run it before the typer-dependent thread is activated. bytecodeWriter = initBytecodeWriter(cleanup.getEntryPoints) @@ -287,6 +295,7 @@ abstract class GenBCode extends BCodeSyncAndTry { // closing output files. bytecodeWriter.close() + Statistics.stopTimer(BackendStats.bcodeTimer, bcodeStart) /* TODO Bytecode can be verified (now that all classfiles have been written to disk) * @@ -312,9 +321,15 @@ abstract class GenBCode extends BCodeSyncAndTry { private def buildAndSendToDisk(needsOutFolder: Boolean) { feedPipeline1() + val genStart = Statistics.startTimer(BackendStats.bcodeGenStat) (new Worker1(needsOutFolder)).run() + Statistics.stopTimer(BackendStats.bcodeGenStat, genStart) + (new Worker2).run() + + val writeStart = Statistics.startTimer(BackendStats.bcodeWriteTimer) drainQ3() + Statistics.stopTimer(BackendStats.bcodeWriteTimer, writeStart) } diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala new file mode 100644 index 0000000000..b3a515c2ae --- /dev/null +++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala @@ -0,0 +1,86 @@ +/* NSC -- new Scala compiler + * Copyright 2005-2014 LAMP/EPFL + * @author Martin Odersky + */ + +package scala.tools.nsc +package backend.jvm +package opt + +import scala.tools.asm.{MethodWriter, ClassWriter} +import scala.tools.asm.tree.analysis.{Analyzer, BasicValue, BasicInterpreter} +import scala.tools.asm.tree.{LabelNode, ClassNode, MethodNode} +import scala.collection.convert.decorateAsScala._ + +/** + * Intra-Method optimizations. + */ +object LocalOpt { + /** + * Remove unreachable instructions from all (non-abstract) methods. + * + * @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) || 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. + */ + private def removeUnreachableCode(method: MethodNode, ownerClass: ClassNode): Boolean = { + val initialSize = method.instructions.size + if (initialSize == 0) return false + + // 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(ownerClass.name, method) + val frames = a.getFrames + + var i = 0 + 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() + } + i += 1 + } + + method.instructions.size == initialSize + } + + /** + * In order to run an Analyzer, the maxLocals / maxStack fields need to be available. The ASM + * framework only computes these values during bytecode generation. + * + * Sicne there's currently no better way, we run a bytecode generator on the method and extract + * the computed values. This required changes to the ASM codebase: + * - the [[MethodWriter]] class was made public + * - accessors for maxLocals / maxStack were added to the MethodWriter class + * + * We could probably make this faster (and allocate less memory) by hacking the ASM framework + * more: create a subclass of MethodWriter with a /dev/null byteVector. Another option would be + * to create a separate visitor for computing those values, duplicating the functionality from the + * MethodWriter. + */ + private def computeMaxLocalsMaxStack(method: MethodNode) { + val cw = new ClassWriter(ClassWriter.COMPUTE_MAXS) + val excs = method.exceptions.asScala.toArray + val mw = cw.visitMethod(method.access, method.name, method.desc, method.signature, excs).asInstanceOf[MethodWriter] + method.accept(mw) + method.maxLocals = mw.getMaxLocals + method.maxStack = mw.getMaxStack + } +} diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 91b03869e5..98eb831a9d 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -211,7 +211,7 @@ trait ScalaSettings extends AbsScalaSettings 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." - object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup = Value } + object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup, jvm = Value } val Ystatistics = { val description = "Print compiler statistics for specific phases" MultiChoiceSetting( |