Run computeMaxLocalsMaxStack less often

Introduce a cache to remember which methods have maxLocals and
maxStack already computed. Before we were computing these values
on every run of eliminateUnreachableCode.

Also update the implementation of eliminateUnreachableCode to keep
correct max values.

16 files changed, 192 insertions, 109 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
index 6bc9f76e1a..c8ba0d9dbc 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypes.scala
@@ -11,9 +11,10 @@ import scala.collection.concurrent.TrieMap
 import scala.reflect.internal.util.Position
 import scala.tools.asm
 import asm.Opcodes
-import scala.tools.asm.tree.{MethodNode, MethodInsnNode, InnerClassNode, ClassNode}
+import scala.tools.asm.tree._
 import scala.tools.nsc.backend.jvm.BTypes.{InlineInfo, MethodInlineInfo}
 import scala.tools.nsc.backend.jvm.BackendReporting._
+import scala.tools.nsc.backend.jvm.analysis.Analyzers
 import scala.tools.nsc.backend.jvm.opt._
 import scala.collection.convert.decorateAsScala._
 import scala.tools.nsc.settings.ScalaSettings
@@ -50,6 +51,8 @@ abstract class BTypes {
 
   val callGraph: CallGraph[this.type]
 
+  val analyzers: Analyzers[this.type]
+
   val backendReporting: BackendReporting
 
   // Allows to define per-run caches here and in the CallGraph component, which don't have a global
@@ -58,7 +61,6 @@ abstract class BTypes {
   // Allows access to the compiler settings for backend components that don't have a global in scope
   def compilerSettings: ScalaSettings
 
-
   /**
    * A map from internal names to ClassBTypes. Every ClassBType is added to this map on its
    * construction.
@@ -97,6 +99,13 @@ abstract class BTypes {
   val unreachableCodeEliminated: collection.mutable.Set[MethodNode] = recordPerRunCache(collection.mutable.Set.empty)
 
   /**
+   * Cache of methods which have correct `maxLocals` / `maxStack` values assigned. This allows
+   * invoking `computeMaxLocalsMaxStack` whenever running an analyzer but performing the actual
+   * computation only when necessary.
+   */
+  val maxLocalsMaxStackComputed: collection.mutable.Set[MethodNode] = recordPerRunCache(collection.mutable.Set.empty)
+
+  /**
    * Obtain the BType for a type descriptor or internal name. For class descriptors, the ClassBType
    * is constructed by parsing the corresponding classfile.
    * 
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
index dc87ed631d..8cccc50c69 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/BTypesFromSymbols.scala
@@ -7,6 +7,7 @@ package scala.tools.nsc
 package backend.jvm
 
 import scala.tools.asm
+import scala.tools.nsc.backend.jvm.analysis.Analyzers
 import scala.tools.nsc.backend.jvm.opt._
 import scala.tools.nsc.backend.jvm.BTypes._
 import BackendReporting._
@@ -48,6 +49,8 @@ class BTypesFromSymbols[G <: Global](val global: G) extends BTypes {
 
   val callGraph: CallGraph[this.type] = new CallGraph(this)
 
+  val analyzers: Analyzers[this.type] = new Analyzers(this)
+
   val backendReporting: BackendReporting = new BackendReportingImpl(global)
 
   final def initializeCoreBTypes(): Unit = {
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala
new file mode 100644
index 0000000000..3734c63e93
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala
@@ -0,0 +1,29 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import scala.tools.asm.tree.{AbstractInsnNode, MethodNode}
+import scala.tools.asm.tree.analysis.{Frame, BasicInterpreter, Analyzer, Value}
+import scala.tools.nsc.backend.jvm.BTypes._
+import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
+
+/**
+ * This component hosts tools for running ASM analyzers that require access to a `BTypes` instance.
+ * In particular, the AsmAnalyzer class runs `computeMaxLocalsMaxStack` on the methodNode to be
+ * analyzed. This method in turn lives inside the BTypes assembly because it queries the per-run
+ * cache `maxLocalsMaxStackComputed` defined in there.
+ */
+class Analyzers[BT <: BTypes](val btypes: BT) {
+  import btypes._
+
+  /**
+   * A wrapper to make ASM's Analyzer a bit easier to use.
+   */
+  class AsmAnalyzer[V <: Value](methodNode: MethodNode, classInternalName: InternalName, val analyzer: Analyzer[V] = new Analyzer(new BasicInterpreter)) {
+    localOpt.computeMaxLocalsMaxStack(methodNode)
+    analyzer.analyze(classInternalName, methodNode)
+    def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.frameAt(instruction, methodNode)
+  }
+
+  class ProdConsAnalyzer(val methodNode: MethodNode, classInternalName: InternalName) extends AsmAnalyzer(methodNode, classInternalName, new Analyzer(new InitialProducerSourceInterpreter)) with ProdConsAnalyzerImpl
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerImpl.scala
index f2d8dc910a..ce2fe943e4 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerImpl.scala
@@ -61,23 +61,10 @@ import scala.collection.convert.decorateAsScala._
  * function (merging producer sets) is more complex than merging simple basic values.
  * See also the doc comment in the package object `analysis`.
  */
-class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName) {
+trait ProdConsAnalyzerImpl {
+  val methodNode: MethodNode
 
-  /* Timers for benchmarking ProdCons
-  import scala.reflect.internal.util.Statistics._
-  import ProdConsAnalyzer._
-  val analyzerTimer = newSubTimer(classInternalName + "#" + methodNode.name + " - analysis", prodConsAnalyzerTimer)
-  val consumersTimer = newSubTimer(classInternalName + "#" + methodNode.name + " - consumers", prodConsAnalyzerTimer)
-  */
-
-  val analyzer = new Analyzer(new InitialProducerSourceInterpreter)
-
-//  val start = analyzerTimer.start()
-  analyzer.analyze(classInternalName, methodNode)
-//  analyzerTimer.stop(start)
-//  println(analyzerTimer.line)
-
-  def frameAt(insn: AbstractInsnNode) = analyzer.frameAt(insn, methodNode)
+  def frameAt(insn: AbstractInsnNode): Frame[SourceValue]
 
   /**
    * Returns the potential producer instructions of a (local or stack) value in the frame of `insn`.
@@ -409,7 +396,6 @@ class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName)
 
   /** For each instruction, a set of potential consumers of the produced values. */
   private lazy val _consumersOfOutputsFrom: Map[AbstractInsnNode, Vector[Set[AbstractInsnNode]]] = {
-//    val start = consumersTimer.start()
     var res = Map.empty[AbstractInsnNode, Vector[Set[AbstractInsnNode]]]
     for {
       insn <- methodNode.instructions.iterator.asScala
@@ -422,8 +408,6 @@ class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName)
       val outputIndex = producedSlots.indexOf(i)
       res = res.updated(producer, currentConsumers.updated(outputIndex, currentConsumers(outputIndex) + insn))
     }
-//    consumersTimer.stop(start)
-//    println(consumersTimer.line)
     res
   }
 
@@ -431,11 +415,6 @@ class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName)
   private val _ultimateConsumersCache: mutable.AnyRefMap[(AbstractInsnNode, Int), Set[AbstractInsnNode]] = mutable.AnyRefMap.empty
 }
 
-object ProdConsAnalyzer {
-  import scala.reflect.internal.util.Statistics._
-  val prodConsAnalyzerTimer = newTimer("Time in ProdConsAnalyzer", "jvm")
-}
-
 /**
  * A class for pseudo-instructions representing the initial producers of local values that have
  * no producer instruction in the method:
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/package.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/package.scala
index 402357c55b..c50648acd9 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/package.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/package.scala
@@ -26,7 +26,8 @@ package scala.tools.nsc.backend.jvm
  *    - A `top` index stores the index of the current stack top
  *    - NOTE: for a size-2 local variable at index i, the local variable at i+1 is set to an empty
  *      value. However, for a size-2 value at index i on the stack, the value at i+1 holds the next
- *      stack value.
+ *      stack value. IMPORTANT: this is only the case in ASM's analysis framework, not in bytecode.
+ *      See comment below.
  *  - Defines the `execute(instruction)` method.
  *    - executing mutates the state of the frame according to the effect of the instruction
  *      - pop consumed values from the stack
@@ -58,6 +59,50 @@ package scala.tools.nsc.backend.jvm
  *   - the empty method `newControlFlowEdge` can be overridden to track control flow if required
  *
  *
+ * MaxLocals and MaxStack
+ * ----------------------
+ *
+ * At the JVM level, long and double values occupy two slots, both as local variables and on the
+ * stack, as specified in the JVM spec 2.6.2:
+ *   "At any point in time, an operand stack has an associated depth, where a value of type long or
+ *    double contributes two units to the depth and a value of any other type contributes one unit."
+ *
+ * For example, a method
+ *   class A { def f(a: Long, b: Long) = a + b }
+ * has MAXSTACK=4 in the classfile. This value is computed by the ClassWriter / MethodWriter when
+ * generating the classfile (we always pass COMPUTE_MAXS to the ClassWriter).
+ *
+ * For running an ASM Analyzer, long and double values occupy two local variable slots, but only
+ * a single slot on the call stack, as shown by the following snippet:
+ *
+ *   import scala.tools.nsc.backend.jvm._
+ *   import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
+ *   import scala.collection.convert.decorateAsScala._
+ *   import scala.tools.asm.tree.analysis._
+ *
+ *   val cn = AsmUtils.readClass("/Users/luc/scala/scala/sandbox/A.class")
+ *   val m = cn.methods.iterator.asScala.find(_.name == "f").head
+ *
+ *   // the value is read from the classfile, so it's 4
+ *   println(s"maxLocals: ${m.maxLocals}, maxStack: ${m.maxStack}") // maxLocals: 5, maxStack: 4
+ *
+ *   // we can safely set it to 2 for running the analyzer.
+ *   m.maxStack = 2
+ *
+ *   val a = new Analyzer(new BasicInterpreter)
+ *   a.analyze(cn.name, m)
+ *   val addInsn = m.instructions.iterator.asScala.find(_.getOpcode == 97).get // LADD Opcode
+ *   val addFrame = a.frameAt(addInsn, m)
+ *
+ *   addFrame.getStackSize // 2: the two long values only take one slot each
+ *   addFrame.getLocals    // 5: this takes one slot, the two long parameters take 2 slots each
+ *
+ *
+ * While running the optimizer, we need to make sure that the `maxStack` value of a method is
+ * large enough for running an ASM analyzer. We don't need to worry if the value is incorrect in
+ * the JVM perspective: the value will be re-computed and overwritten in the ClassWriter.
+ *
+ *
  * Lessons learnt while benchmarking the alias tracking analysis
  * -------------------------------------------------------------
  *
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 ede572dfb4..ea186f9a1b 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -173,6 +173,11 @@ object BytecodeUtils {
     case Opcodes.IFNONNULL => Opcodes.IFNULL
   }
 
+  def isSize2LoadOrStore(opcode: Int): Boolean = (opcode: @switch) match {
+    case Opcodes.LLOAD | Opcodes.DLOAD | Opcodes.LSTORE | Opcodes.DSTORE => true
+    case _ => false
+  }
+
   def getPop(size: Int): InsnNode = {
     val op = if (size == 1) Opcodes.POP else Opcodes.POP2
     new InsnNode(op)
@@ -222,29 +227,6 @@ object BytecodeUtils {
     }
   }
 
-  /**
-   * In order to run an Analyzer, the maxLocals / maxStack fields need to be available. The ASM
-   * framework only computes these values during bytecode generation.
-   *
-   * Since 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.
-   */
-  def computeMaxLocalsMaxStack(method: MethodNode): Unit = {
-    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
-  }
-
   def codeSizeOKForInlining(caller: MethodNode, callee: MethodNode): Boolean = {
     // Looking at the implementation of CodeSizeEvaluator, all instructions except tableswitch and
     // lookupswitch are <= 8 bytes. These should be rare enough for 8 to be an OK rough upper bound.
@@ -352,15 +334,6 @@ object BytecodeUtils {
     }
   }
 
-  /**
-   * A wrapper to make ASM's Analyzer a bit easier to use.
-   */
-  class AsmAnalyzer[V <: Value](methodNode: MethodNode, classInternalName: InternalName, interpreter: Interpreter[V] = new BasicInterpreter) {
-    val analyzer = new Analyzer(interpreter)
-    analyzer.analyze(classInternalName, methodNode)
-    def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.frameAt(instruction, methodNode)
-  }
-
   implicit class AnalyzerExtensions[V <: Value](val analyzer: Analyzer[V]) extends AnyVal {
     def frameAt(instruction: AbstractInsnNode, methodNode: MethodNode): Frame[V] = analyzer.getFrames()(methodNode.instructions.indexOf(instruction))
   }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
index 87b51c55b4..535a46f362 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
@@ -9,7 +9,6 @@ package opt
 
 import scala.collection.immutable.IntMap
 import scala.reflect.internal.util.{NoPosition, Position}
-import scala.tools.asm.tree.analysis.{Value, Analyzer, BasicInterpreter}
 import scala.tools.asm.{Opcodes, Type, Handle}
 import scala.tools.asm.tree._
 import scala.collection.{concurrent, mutable}
@@ -22,6 +21,7 @@ import BytecodeUtils._
 
 class CallGraph[BT <: BTypes](val btypes: BT) {
   import btypes._
+  import analyzers._
 
   /**
    * The call graph contains the callsites in the program being compiled.
@@ -97,13 +97,12 @@ class CallGraph[BT <: BTypes](val btypes: BT) {
     // It is also used to get the stack height at the call site.
     localOpt.minimalRemoveUnreachableCode(methodNode, definingClass.internalName)
 
-    val analyzer: Analyzer[_ <: Value] = {
-      if (compilerSettings.YoptNullnessTracking) new NullnessAnalyzer
-      else new Analyzer(new BasicInterpreter)
+    val analyzer = {
+      if (compilerSettings.YoptNullnessTracking) new AsmAnalyzer(methodNode, definingClass.internalName, new NullnessAnalyzer)
+      else new AsmAnalyzer(methodNode, definingClass.internalName)
     }
-    analyzer.analyze(definingClass.internalName, methodNode)
 
-    def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = analyzer match {
+    def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = analyzer.analyzer match {
       case nullnessAnalyzer: NullnessAnalyzer =>
         val frame = nullnessAnalyzer.frameAt(call, methodNode)
         frame.getStack(frame.getStackSize - 1 - numArgs) eq NotNullValue
@@ -149,7 +148,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) {
           callsiteClass = definingClass,
           callee = callee,
           argInfos = argInfos,
-          callsiteStackHeight = analyzer.frameAt(call, methodNode).getStackSize,
+          callsiteStackHeight = analyzer.frameAt(call).getStackSize,
           receiverKnownNotNull = receiverNotNull,
           callsitePosition = callsitePositions.getOrElse(call, NoPosition)
         )
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
index 1a1a6942dc..23b85d175e 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
@@ -14,7 +14,6 @@ import scala.reflect.internal.util.NoPosition
 import scala.tools.asm.{Type, Opcodes}
 import scala.tools.asm.tree._
 import scala.tools.nsc.backend.jvm.BTypes.InternalName
-import scala.tools.nsc.backend.jvm.analysis.ProdConsAnalyzer
 import BytecodeUtils._
 import BackendReporting._
 import Opcodes._
@@ -24,6 +23,7 @@ import scala.collection.convert.decorateAsScala._
 class ClosureOptimizer[BT <: BTypes](val btypes: BT) {
   import btypes._
   import callGraph._
+  import analyzers._
 
   /**
    * If a closure is allocated and invoked within the same method, re-write the invocation to the
@@ -204,7 +204,8 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) {
     insertLoadOps(invocation, ownerMethod, argumentLocalsList)
 
     // update maxStack
-    val numCapturedValues = localsForCapturedValues.locals.length // not `localsForCapturedValues.size`: every value takes 1 slot on the stack (also long / double), JVMS 2.6.2
+    // One slot per value is correct for long / double, see comment in the `analysis` package object.
+    val numCapturedValues = localsForCapturedValues.locals.length
     val invocationStackHeight = stackHeight + numCapturedValues - 1 // -1 because the closure is gone
     if (invocationStackHeight > ownerMethod.maxStack)
       ownerMethod.maxStack = invocationStackHeight
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
index 8dff7ef446..36ace2f4f9 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -8,9 +8,7 @@ package backend.jvm
 package opt
 
 import scala.annotation.tailrec
-import scala.collection.immutable.IntMap
 import scala.tools.asm
-import asm.Handle
 import asm.Opcodes._
 import asm.tree._
 import scala.collection.convert.decorateAsScala._
@@ -18,7 +16,7 @@ import scala.collection.convert.decorateAsJava._
 import AsmUtils._
 import BytecodeUtils._
 import collection.mutable
-import scala.tools.asm.tree.analysis.SourceInterpreter
+import scala.tools.asm.tree.analysis.{Analyzer, SourceInterpreter}
 import BackendReporting._
 import scala.tools.nsc.backend.jvm.BTypes.InternalName
 
@@ -26,6 +24,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
   import btypes._
   import callGraph._
   import inlinerHeuristics._
+  import analyzers._
 
   def eliminateUnreachableCodeAndUpdateCallGraph(methodNode: MethodNode, definingClass: InternalName): Unit = {
     localOpt.minimalRemoveUnreachableCode(methodNode, definingClass) foreach {
@@ -146,7 +145,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
         if (!selfTypeOk) {
           // there's no need to run eliminateUnreachableCode here. building the call graph does that
           // already, no code can become unreachable in the meantime.
-          val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new SourceInterpreter)
+          val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new Analyzer(new SourceInterpreter))
           val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length)
           for (i <- receiverValue.insns.asScala) {
             val cast = new TypeInsnNode(CHECKCAST, selfParamType.internalName)
@@ -410,8 +409,20 @@ class Inliner[BT <: BTypes](val btypes: BT) {
     callsiteMethod.tryCatchBlocks.addAll(cloneTryCatchBlockNodes(callee, labelsMap).asJava)
 
     callsiteMethod.maxLocals += returnType.getSize + callee.maxLocals
-    val numStoredArgs = calleeParamTypes.length + (if (isStaticMethod(callee)) 0 else 1) // every value takes 1 slot on the stack (also long / double), JVMS 2.6.2
-    callsiteMethod.maxStack = math.max(callsiteMethod.maxStack, callee.maxStack + callsiteStackHeight - numStoredArgs)
+    val maxStackOfInlinedCode = {
+      // One slot per value is correct for long / double, see comment in the `analysis` package object.
+      val numStoredArgs = calleeParamTypes.length + (if (isStaticMethod(callee)) 0 else 1)
+      callee.maxStack + callsiteStackHeight - numStoredArgs
+    }
+    val stackHeightAtNullCheck = {
+      // When adding a null check for the receiver, a DUP is inserted, which might cause a new maxStack.
+      // If the callsite has other argument values than the receiver on the stack, these are pop'ed
+      // and stored into locals before the null check, so in that case the maxStack doesn't grow.
+      val stackSlotForNullCheck = if (!isStaticMethod(callee) && !receiverKnownNotNull && calleeParamTypes.isEmpty) 1 else 0
+      callsiteStackHeight + stackSlotForNullCheck
+    }
+
+    callsiteMethod.maxStack = math.max(callsiteMethod.maxStack, math.max(stackHeightAtNullCheck, maxStackOfInlinedCode))
 
     callGraph.addIfMissing(callee, calleeDeclarationClass)
 
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 f5e6653344..fe398ce652 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -8,8 +8,7 @@ package backend.jvm
 package opt
 
 import scala.annotation.switch
-import scala.tools.asm.Opcodes
-import scala.tools.asm.tree.analysis.{Analyzer, BasicInterpreter}
+import scala.tools.asm.{Type, ClassWriter, MethodWriter, Opcodes}
 import scala.tools.asm.tree._
 import scala.collection.convert.decorateAsScala._
 import scala.tools.nsc.backend.jvm.BTypes.InternalName
@@ -49,6 +48,39 @@ import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
 class LocalOpt[BT <: BTypes](val btypes: BT) {
   import LocalOptImpls._
   import btypes._
+  import analyzers._
+
+  /**
+   * In order to run an Analyzer, the maxLocals / maxStack fields need to be available. The ASM
+   * framework only computes these values during bytecode generation.
+   *
+   * Since 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.
+   *
+   * NOTE: the maxStack value computed by this method allocates two slots for long / double values,
+   * as required by the JVM spec. For running an Analyzer, one slot per long / double would be fine.
+   * See comment in `analysis` package object.
+   */
+  def computeMaxLocalsMaxStack(method: MethodNode): Unit = {
+    if (!maxLocalsMaxStackComputed(method)) {
+      method.maxLocals = 0
+      method.maxStack = 0
+      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
+      maxLocalsMaxStackComputed += method
+    }
+  }
 
   /**
    * Remove unreachable code from a method.
@@ -179,46 +211,55 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
     codeHandlersOrJumpsChanged || localsRemoved || lineNumbersRemoved || labelsRemoved
   }
 
-}
-
-object LocalOptImpls {
   /**
    * Removes unreachable basic blocks.
    *
-   * TODO: rewrite, don't use computeMaxLocalsMaxStack (runs a ClassWriter) / Analyzer. Too slow.
-   *
    * @return A set containing eliminated instructions, and a set containing all live label nodes.
    */
   def removeUnreachableCodeImpl(method: MethodNode, ownerClassName: InternalName): (Set[AbstractInsnNode], Set[LabelNode]) = {
-    // The data flow analysis requires the maxLocals / maxStack fields of the method to be computed.
-    computeMaxLocalsMaxStack(method)
-    val a = new Analyzer(new BasicInterpreter)
-    a.analyze(ownerClassName, method)
-    val frames = a.getFrames
+    val a = new AsmAnalyzer(method, ownerClassName)
+    val frames = a.analyzer.getFrames
 
     var i = 0
     var liveLabels = Set.empty[LabelNode]
     var removedInstructions = Set.empty[AbstractInsnNode]
+    var maxLocals = Type.getArgumentsAndReturnSizes(method.desc) >> 2 - (if (BytecodeUtils.isStaticMethod(method)) 1 else 0)
+    var maxStack = 0
     val itr = method.instructions.iterator()
     while (itr.hasNext) {
-      itr.next() match {
-        case l: LabelNode =>
-          if (frames(i) != null) liveLabels += l
+      val insn = itr.next()
+      val isLive = frames(i) != null
+      if (isLive) maxStack = math.max(maxStack, frames(i).getStackSize)
 
-        case ins =>
+      insn match {
+        case l: LabelNode =>
           // label nodes are not removed: they might be referenced for example in a LocalVariableNode
-          if (frames(i) == null || ins.getOpcode == Opcodes.NOP) {
+          if (isLive) liveLabels += l
+
+        case v: VarInsnNode if isLive =>
+          val longSize = if (isSize2LoadOrStore(v.getOpcode)) 1 else 0
+          maxLocals = math.max(maxLocals, v.`var` + longSize + 1) // + 1 becauase local numbers are 0-based
+
+        case i: IincInsnNode if isLive =>
+          maxLocals = math.max(maxLocals, i.`var` + 1)
+
+        case _ =>
+          if (!isLive || insn.getOpcode == Opcodes.NOP) {
             // Instruction iterators allow removing during iteration.
             // Removing is O(1): instructions are doubly linked list elements.
             itr.remove()
-            removedInstructions += ins
+            removedInstructions += insn
           }
       }
       i += 1
     }
+    method.maxLocals = maxLocals
+    method.maxStack  = maxStack
     (removedInstructions, liveLabels)
   }
+}
 
+object LocalOptImpls {
   /**
    * 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.
@@ -311,10 +352,7 @@ object LocalOptImpls {
     // 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
-      }
+      val isWide = isSize2LoadOrStore(varIns.getOpcode)
 
       // Ensure the length of `renumber`. Unused variable indices are mapped to -1.
       val minLength = if (isWide) index + 2 else index + 1
diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
index 9cf6e366d2..f78d450db1 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
@@ -31,25 +31,22 @@ object NullnessAnalyzerTest extends ClearAfterClass.Clearable {
 class NullnessAnalyzerTest extends ClearAfterClass {
   ClearAfterClass.stateToClear = NullnessAnalyzerTest
   val noOptCompiler = NullnessAnalyzerTest.noOptCompiler
+  import noOptCompiler.genBCode.bTypes.analyzers._
 
-  def newNullnessAnalyzer(methodNode: MethodNode, classInternalName: InternalName = "C"): NullnessAnalyzer = {
-    val nullnessAnalyzer = new NullnessAnalyzer
-    nullnessAnalyzer.analyze(classInternalName, methodNode)
-    nullnessAnalyzer
-  }
+  def newNullnessAnalyzer(methodNode: MethodNode, classInternalName: InternalName = "C") = new AsmAnalyzer(methodNode, classInternalName, new NullnessAnalyzer)
 
-  def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: NullnessValue): Unit = {
+  def testNullness(analyzer: AsmAnalyzer[NullnessValue], method: MethodNode, query: String, index: Int, nullness: NullnessValue): Unit = {
     for (i <- findInstr(method, query)) {
-      val r = analyzer.frameAt(i, method).getValue(index)
+      val r = analyzer.frameAt(i).getValue(index)
       assertTrue(s"Expected: $nullness, found: $r. At instr ${textify(i)}", nullness == r)
     }
   }
 
   // debug / helper for writing tests
-  def showAllNullnessFrames(analyzer: NullnessAnalyzer, method: MethodNode): String = {
+  def showAllNullnessFrames(analyzer: AsmAnalyzer[NullnessValue], method: MethodNode): String = {
     val instrLength = method.instructions.iterator.asScala.map(textify(_).length).max
     val lines = for (i <- method.instructions.iterator.asScala) yield {
-      val f = analyzer.frameAt(i, method)
+      val f = analyzer.frameAt(i)
       val frameString = {
         if (f == null) "null"
         else (0 until (f.getLocals + f.getStackSize)).iterator
diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala
index a5b3faced8..72f26d231d 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala
@@ -26,6 +26,7 @@ object ProdConsAnalyzerTest extends ClearAfterClass.Clearable {
 class ProdConsAnalyzerTest extends ClearAfterClass {
   ClearAfterClass.stateToClear = ProdConsAnalyzerTest
   val noOptCompiler = ProdConsAnalyzerTest.noOptCompiler
+  import noOptCompiler.genBCode.bTypes.analyzers._
 
   def prodToString(producer: AbstractInsnNode) = producer match {
     case p: InitialProducer => p.toString
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
index 258813ea68..735bbefbbb 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
@@ -13,7 +13,6 @@ import org.junit.Assert._
 
 import scala.tools.asm.tree._
 import scala.tools.asm.tree.analysis._
-import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.AsmAnalyzer
 import scala.tools.nsc.io._
 import scala.tools.nsc.reporters.StoreReporter
 import scala.tools.testing.AssertUtil._
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlineWarningTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlineWarningTest.scala
index 029caa995c..e78b5071e0 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlineWarningTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlineWarningTest.scala
@@ -13,7 +13,6 @@ import org.junit.Assert._
 
 import scala.tools.asm.tree._
 import scala.tools.asm.tree.analysis._
-import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.AsmAnalyzer
 import scala.tools.nsc.io._
 import scala.tools.nsc.reporters.StoreReporter
 import scala.tools.testing.AssertUtil._
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
index aa7184ffd8..622715ab3a 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -14,7 +14,6 @@ import org.junit.Assert._
 
 import scala.tools.asm.tree._
 import scala.tools.asm.tree.analysis._
-import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.AsmAnalyzer
 import scala.tools.nsc.io._
 import scala.tools.nsc.reporters.StoreReporter
 import scala.tools.testing.AssertUtil._
@@ -69,6 +68,7 @@ class InlinerTest extends ClearAfterClass {
 
   val compiler = InlinerTest.compiler
   import compiler.genBCode.bTypes._
+  import compiler.genBCode.bTypes.analyzers._
 
   def compile(scalaCode: String, javaCode: List[(String, String)] = Nil, allowMessage: StoreReporter#Info => Boolean = _ => false): List[ClassNode] = {
     InlinerTest.notPerRun.foreach(_.clear())
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 0ac206669a..86c8baa3c6 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/UnreachableCodeTest.scala
@@ -39,7 +39,7 @@ class UnreachableCodeTest extends ClearAfterClass {
 
   def assertEliminateDead(code: (Instruction, Boolean)*): Unit = {
     val method = genMethod()(code.map(_._1): _*)
-    LocalOptImpls.removeUnreachableCodeImpl(method, "C")
+    dceCompiler.genBCode.bTypes.localOpt.removeUnreachableCodeImpl(method, "C")
     val nonEliminated = instructionsFromMethod(method)
     val expectedLive = code.filter(_._2).map(_._1).toList
     assertSameCode(nonEliminated, expectedLive)