Producers / Consumers Analysis

ASM has a built-in `SourceValue` analysis which computes for each
value a set of instructions that may possibly have constructed it.

The ProdConsAnalyzer class provides additional queries over the
result of the SourceValue analysis:
  - consumers of values
  - tracking producers / consumers through copying operations (load,
    store, etc)

A fix to (and therefore a new version of) ASM was required. See here:
https://github.com/scala/scala-asm/commit/94106a5472

7 files changed, 724 insertions, 18 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
index 98e93c125b..8d8ea839e6 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
@@ -94,7 +94,7 @@ object InstructionStackEffect {
         val isSize2 = peekStack(0).getSize == 2
         if (isSize2) t(1, 0) else t(2, 0)
 
-      case DUP => t(0, 1)
+      case DUP => t(1, 2)
 
       case DUP_X1 => t(2, 3)
 
@@ -104,7 +104,7 @@ object InstructionStackEffect {
 
       case DUP2 =>
         val isSize2 = peekStack(0).getSize == 2
-        if (isSize2) t(0, 1) else t(0, 2)
+        if (isSize2) t(1, 2) else t(2, 4)
 
       case DUP2_X1 =>
         val isSize2 = peekStack(0).getSize == 2
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala
new file mode 100644
index 0000000000..40f91cbed4
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzer.scala
@@ -0,0 +1,450 @@
+/* NSC -- new Scala compiler
+ * Copyright 2005-2015 LAMP/EPFL
+ * @author Martin Odersky
+ */
+
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import java.util
+
+import scala.annotation.switch
+import scala.collection.mutable
+import scala.tools.asm.{Type, MethodVisitor}
+import scala.tools.asm.Opcodes._
+import scala.tools.asm.tree._
+import scala.tools.asm.tree.analysis._
+import scala.tools.nsc.backend.jvm.BTypes.InternalName
+
+import opt.BytecodeUtils._
+
+import scala.collection.convert.decorateAsScala._
+
+/**
+ * This class provides additional queries over ASM's built-in `SourceValue` analysis.
+ *
+ * The analysis computes for each value in a frame a set of source instructions, which are the
+ * potential producers. Most instructions produce either nothing or a stack value. For example,
+ * a `LOAD` instruction is the producer of the value pushed onto the stack. The exception are
+ * `STORE` instructions, which produce a new value for a local variable slot, so they are used
+ * as producers for the value they stored.
+ *
+ * Note that pseudo-instructions are used as initial producers for parameters and local variables.
+ * See the documentation on class InitialProducer.
+ *
+ * This class implements the following queries over the data computed by the SourceValue analysis:
+ *
+ *   - producersForValueAt(insn, slot)
+ *   - consumersOfValueAt(insn, slot)
+ *
+ *   - producersForInputsOf(insn)
+ *   - consumersOfOutputsFrom(insn)
+ *
+ *   - initialProducersForValueAt(insn, slot)
+ *   - ultimateConsumersOfValueAt(insn, slot)
+ *
+ *   - initialProducersForInputsOf(insn)
+ *   - ultimateConsumersOfOutputsFrom(insn)
+ *
+ * The following operations are considered as copying operations:
+ *   - xLOAD, xSTORE
+ *   - DUP, DUP2, DUP_X1, DUP_X2, DUP2_X1, DUP2_X2
+ *   - SWAP
+ *   - CHECKCAST
+ *
+ * If ever needed, we could introduce a mode where primitive conversions (l2i) are considered as
+ * copying operations.
+ */
+class ProdConsAnalyzer(methodNode: MethodNode, classInternalName: InternalName) {
+  val analyzer = new Analyzer(new InitialProducerSourceInterpreter)
+  analyzer.analyze(classInternalName, methodNode)
+
+  def frameAt(insn: AbstractInsnNode) = analyzer.frameAt(insn, methodNode)
+
+  /**
+   * Returns the potential producer instructions of a (local or stack) value in the frame of `insn`.
+   * This method simply returns the producer information computed by the SourceValue analysis.
+   */
+  def producersForValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = {
+    frameAt(insn).getValue(slot).insns.asScala.toSet
+  }
+
+  /**
+   * Returns the potential consumer instructions of a (local or stack) value in the frame of `insn`.
+   * This is the counterpart of `producersForValueAt`.
+   */
+  def consumersOfValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = {
+    producersForValueAt(insn, slot).flatMap(prod => {
+      val outputNumber = outputValueSlots(prod).indexOf(slot)
+      _consumersOfOutputsFrom.get(prod).map(v => {
+        v(outputNumber)
+      }).getOrElse(Set.empty)
+    })
+  }
+
+  /**
+   * Returns the potential producer instructions of any of the values consumed by `insn`.
+   */
+  def producersForInputsOf(insn: AbstractInsnNode): Set[AbstractInsnNode] = {
+    inputValues(insn).iterator.flatMap(v => v.insns.asScala).toSet
+  }
+
+  def consumersOfOutputsFrom(insn: AbstractInsnNode): Set[AbstractInsnNode] =
+    _consumersOfOutputsFrom.get(insn).map(v => v.indices.flatMap(v.apply)(collection.breakOut): Set[AbstractInsnNode]).getOrElse(Set.empty)
+
+  /**
+   * Returns the potential initial producer instructions of a value in the frame of `insn`.
+   *
+   * Unlike `producersForValueAt`, producers are tracked through copying instructions such as STORE
+   * and LOAD. If the producer of the value is a LOAD, then the producers of the stored value(s) are
+   * returned instead.
+   */
+  def initialProducersForValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = {
+    def initialProducers(insn: AbstractInsnNode, producedSlot: Int): Set[AbstractInsnNode] = {
+      if (isCopyOperation(insn)) {
+        _initialProducersCache.getOrElseUpdate((insn, producedSlot), {
+          val (sourceValue, sourceValueSlot) = copyOperationSourceValue(insn, producedSlot)
+          sourceValue.insns.iterator.asScala.flatMap(initialProducers(_, sourceValueSlot)).toSet
+        })
+      } else {
+        Set(insn)
+      }
+    }
+    producersForValueAt(insn, slot).flatMap(initialProducers(_, slot))
+  }
+
+  /**
+   * Returns the potential ultimate consumers of a value in the frame of `insn`. Consumers are
+   * tracked through copying operations such as SOTRE and LOAD.
+   */
+  def ultimateConsumersOfValueAt(insn: AbstractInsnNode, slot: Int): Set[AbstractInsnNode] = {
+    def ultimateConsumers(insn: AbstractInsnNode, consumedSlot: Int): Set[AbstractInsnNode] = {
+      if (isCopyOperation(insn)) {
+        _ultimateConsumersCache.getOrElseUpdate((insn, consumedSlot), {
+          for {
+            producedSlot     <- copyOperationProducedValueSlots(insn, consumedSlot)
+            consumer         <- consumersOfValueAt(insn.getNext, producedSlot)
+            ultimateConsumer <- ultimateConsumers(consumer, producedSlot)
+          } yield ultimateConsumer
+        })
+      } else {
+        Set(insn)
+      }
+    }
+    consumersOfValueAt(insn, slot).flatMap(ultimateConsumers(_, slot))
+  }
+
+  def initialProducersForInputsOf(insn: AbstractInsnNode): Set[AbstractInsnNode] = {
+    inputValueSlots(insn).flatMap(slot => initialProducersForValueAt(insn, slot)).toSet
+  }
+
+  def ultimateConsumersOfOutputsFrom(insn: AbstractInsnNode): Set[AbstractInsnNode] = {
+    lazy val next = insn.getNext
+    outputValueSlots(insn).flatMap(slot => ultimateConsumersOfValueAt(next, slot)).toSet
+  }
+
+  private def isCopyOperation(insn: AbstractInsnNode): Boolean = {
+    isVarInstruction(insn) || {
+      (insn.getOpcode: @switch) match {
+        case DUP | DUP_X1 | DUP_X2 | DUP2 | DUP2_X1 | DUP2_X2 | SWAP | CHECKCAST => true
+        case _ => false
+      }
+    }
+  }
+
+  /**
+   * Returns the value and its frame slot that `copyOp` copies into `producedSlot`.
+   *
+   * Example:
+   *   - copyOp = DUP_X1, assume it produces slots 2,3,4
+   *   - producedSlot = 3
+   *   - the result is the value at slot 2 in the frame of `copyOp`
+   */
+  private def copyOperationSourceValue(copyOp: AbstractInsnNode, producedSlot: Int): (SourceValue, Int) = {
+    val frame = frameAt(copyOp)
+
+    // Index of the produced value. Example: DUP_X1 produces 3 values, so producedIndex is 0, 1 or 2,
+    // where 0 corresponds to the lowest value on the stack.
+    def producedIndex(numConsumed: Int) = {
+      val numUsedSlotsBeforeCopy = frame.stackTop + 1
+      producedSlot - (numUsedSlotsBeforeCopy - numConsumed)
+    }
+
+    def stackValue(n: Int) = (frame.peekStack(n), frame.stackTop - n)
+
+    def dupX1Case = (producedIndex(2): @switch) match {
+      case 0 | 2 => stackValue(0)
+      case 1     => stackValue(1)
+    }
+
+    // Form 1 of dup_x2
+    def dupX2Case = (producedIndex(3): @switch) match {
+      case 0 | 3 => stackValue(0)
+      case 1     => stackValue(2)
+      case 2     => stackValue(1)
+    }
+
+    // Form 1 of dup2_x1
+    def dup2X1Case = (producedIndex(3): @switch) match {
+      case 0 | 3 => stackValue(1)
+      case 1 | 4 => stackValue(0)
+      case 2     => stackValue(2)
+    }
+
+    if (isLoad(copyOp)) {
+      val slot = copyOp.asInstanceOf[VarInsnNode].`var`
+      (frame.getLocal(slot), slot)
+    } else if (isStore(copyOp)) {
+      stackValue(0)
+    } else (copyOp.getOpcode: @switch) match {
+      case DUP =>
+        stackValue(0) // the current stack top is the source of both produced values
+
+      case DUP_X1 =>
+        dupX1Case
+
+      case DUP_X2 =>
+        if (frame.peekStack(1).getSize == 2) dupX1Case
+        else dupX2Case
+
+      case DUP2 =>
+        if (frame.peekStack(0).getSize == 2) stackValue(0)
+        else {
+          (producedIndex(2): @switch) match {
+            case 0 | 2 => stackValue(1)
+            case 1 | 3 => stackValue(0)
+          }
+        }
+
+      case DUP2_X1 =>
+        if (frame.peekStack(0).getSize == 2) dupX1Case
+        else dup2X1Case
+
+      case DUP2_X2 =>
+        val v1isSize2 = frame.peekStack(0).getSize == 2
+        if (v1isSize2) {
+          val v2isSize2 = frame.peekStack(1).getSize == 2
+          if (v2isSize2) dupX1Case // Form 4
+          else dupX2Case // Form 2
+        } else {
+          val v3isSize2 = frame.peekStack(2).getSize == 2
+          if (v3isSize2) dup2X1Case // Form 3
+          else {
+            // Form 1
+            (producedIndex(4): @switch) match {
+              case 0 | 4 => stackValue(1)
+              case 1 | 5 => stackValue(0)
+              case 2     => stackValue(3)
+              case 3     => stackValue(2)
+            }
+          }
+        }
+
+      case SWAP =>
+        if (producedIndex(2) == 0) stackValue(0)
+        else stackValue(1)
+
+      case CHECKCAST =>
+        stackValue(0)
+    }
+  }
+
+  /**
+   * Returns the value slots into which `copyOp` copies the value at `consumedSlot`.
+   *
+   * Example:
+   *   - copyOp = DUP_X1, assume it consumes slots 2,3 and produces 2,3,4
+   *   - if consumedSlot == 2, the result is Set(3)
+   *   - if consumedSlot == 3, the result is Set(2, 4)
+   */
+  private def copyOperationProducedValueSlots(copyOp: AbstractInsnNode, consumedSlot: Int): Set[Int] = {
+    if (isStore(copyOp)) Set(copyOp.asInstanceOf[VarInsnNode].`var`)
+    else {
+      val nextFrame = frameAt(copyOp.getNext)
+      val top = nextFrame.stackTop
+
+      // Index of the consumed value. Example: DUP_X1 consumes two values, so consumedIndex is
+      // 0 or 1, where 0 corresponds to the lower value on the stack.
+      def consumedIndex(numProduced: Int) = {
+        val numUsedSlotsAfterCopy = top + 1
+        consumedSlot - (numUsedSlotsAfterCopy - numProduced)
+      }
+
+      def dupX1Case = (consumedIndex(3): @switch) match {
+        case 0 => Set(top - 1)
+        case 1 => Set(top - 2, top)
+      }
+
+      def dupX2Case = (consumedIndex(4): @switch) match {
+        case 0 => Set(top - 2)
+        case 1 => Set(top - 1)
+        case 2 => Set(top - 3, top)
+      }
+
+      def dup2X1Case = (consumedIndex(5): @switch) match {
+        case 0 => Set(top - 2)
+        case 1 => Set(top - 4, top - 1)
+        case 2 => Set(top - 3, top)
+      }
+
+      if (isLoad(copyOp)) Set(top)
+      else (copyOp.getOpcode: @switch) match {
+        case DUP =>
+          Set(top - 1, top)
+
+        case DUP_X1 =>
+          dupX1Case
+
+        case DUP_X2 =>
+          if (nextFrame.peekStack(1).getSize == 2) dupX1Case
+          else dupX2Case
+
+        case DUP2 =>
+          if (nextFrame.peekStack(0).getSize == 2) Set(top - 1, top)
+          else (consumedIndex(4): @switch) match {
+            case 0 => Set(top - 3, top - 1)
+            case 1 => Set(top - 2, top)
+          }
+
+        case DUP2_X1 =>
+          if (nextFrame.peekStack(0).getSize == 2) dupX1Case
+          else dup2X1Case
+
+        case DUP2_X2 =>
+          val v1isSize2 = nextFrame.peekStack(0).getSize == 2
+          if (v1isSize2) {
+            val v2isSize2 = nextFrame.peekStack(1).getSize == 2
+            if (v2isSize2) dupX1Case // Form 4
+            else dupX2Case // Form 2
+          } else {
+            val v3isSize2 = nextFrame.peekStack(2).getSize == 2
+            if (v3isSize2) dup2X1Case // Form 3
+            else {
+              // Form 1
+              (consumedIndex(6): @switch) match {
+                case 0 => Set(top - 3)
+                case 1 => Set(top - 2)
+                case 2 => Set(top - 5, top - 1)
+                case 3 => Set(top - 4, top)
+              }
+            }
+          }
+
+        case SWAP =>
+          if (consumedIndex(2) == 0) Set(top)
+          else Set(top - 1)
+
+        case CHECKCAST =>
+          Set(top)
+      }
+    }
+  }
+
+  /** Returns the frame values consumed by executing `insn`. */
+  private def inputValues(insn: AbstractInsnNode): Seq[SourceValue] = {
+    lazy val frame = frameAt(insn)
+    inputValueSlots(insn) map frame.getValue
+  }
+
+  /** Returns the frame slots holding the values consumed by executing `insn`. */
+  private def inputValueSlots(insn: AbstractInsnNode): Seq[Int] = {
+    if (insn.getOpcode == -1) return Seq.empty
+    if (isLoad(insn)) {
+      Seq(insn.asInstanceOf[VarInsnNode].`var`)
+    } else if (insn.getOpcode == IINC) {
+      Seq(insn.asInstanceOf[IincInsnNode].`var`)
+    } else {
+      val frame = frameAt(insn)
+      val stackEffect = InstructionStackEffect(insn, frame)
+      val stackSize = frame.getLocals + frame.getStackSize
+      (stackSize - stackEffect._1) until stackSize
+    }
+  }
+
+  /** Returns the frame slots holding the values produced by executing `insn`. */
+  private def outputValueSlots(insn: AbstractInsnNode): Seq[Int] = insn match {
+    case ParameterProducer(local)          => Seq(local)
+    case UninitializedLocalProducer(local) => Seq(local)
+    case ExceptionProducer(frame)          => Seq(frame.stackTop)
+    case _ =>
+      if (insn.getOpcode == -1) return Seq.empty
+      if (isStore(insn)) {
+        Seq(insn.asInstanceOf[VarInsnNode].`var`)
+      } else if (insn.getOpcode == IINC) {
+        Seq(insn.asInstanceOf[IincInsnNode].`var`)
+      } else {
+        val frame = frameAt(insn)
+        val stackEffect = InstructionStackEffect(insn, frame)
+        val nextFrame = frameAt(insn.getNext)
+        val stackSize = nextFrame.getLocals + nextFrame.getStackSize
+        (stackSize - stackEffect._2) until stackSize
+      }
+  }
+
+  /** For each instruction, a set of potential consumers of the produced values. */
+  private lazy val _consumersOfOutputsFrom: Map[AbstractInsnNode, Vector[Set[AbstractInsnNode]]] = {
+    var res = Map.empty[AbstractInsnNode, Vector[Set[AbstractInsnNode]]]
+    for {
+      insn <- methodNode.instructions.iterator.asScala
+      frame = frameAt(insn)
+      i <- inputValueSlots(insn)
+      producer <- frame.getValue(i).insns.asScala
+    } {
+      val producedSlots = outputValueSlots(producer)
+      val currentConsumers = res.getOrElse(producer, Vector.fill(producedSlots.size)(Set.empty[AbstractInsnNode]))
+      val outputIndex = producedSlots.indexOf(i)
+      res = res.updated(producer, currentConsumers.updated(outputIndex, currentConsumers(outputIndex) + insn))
+    }
+    res
+  }
+
+  private val _initialProducersCache:  mutable.AnyRefMap[(AbstractInsnNode, Int), Set[AbstractInsnNode]] = mutable.AnyRefMap.empty
+  private val _ultimateConsumersCache: mutable.AnyRefMap[(AbstractInsnNode, Int), Set[AbstractInsnNode]] = mutable.AnyRefMap.empty
+}
+
+/**
+ * A class for pseudo-instructions representing the initial producers of local values that have
+ * no producer instruction in the method:
+ *   - parameters, including `this`
+ *   - uninitialized local variables
+ *   - exception values in handlers
+ *
+ * The ASM built-in SourceValue analysis yields an empty producers set for such values. This leads
+ * to ambiguities. Example (in Java one can re-assign parameter):
+ *
+ *   void foo(int a) {
+ *     if (a == 0) a = 1;
+ *     return a;
+ *   }
+ *
+ * In the first frame of the method, the SoruceValue for parameter `a` gives an empty set of
+ * producer instructions.
+ *
+ * In the frame of the `IRETURN` instruction, the SoruceValue for parameter `a` lists a single
+ * producer instruction: the `ISTORE 1`. This makes it look as if there was a single producer for
+ * `a`, where in fact it might still hold the parameter's initial value.
+ */
+abstract class InitialProducer extends AbstractInsnNode(-1) {
+  override def getType: Int = throw new UnsupportedOperationException
+  override def clone(labels: util.Map[LabelNode, LabelNode]): AbstractInsnNode = throw new UnsupportedOperationException
+  override def accept(cv: MethodVisitor): Unit = throw new UnsupportedOperationException
+}
+
+case class ParameterProducer(local: Int)                      extends InitialProducer
+case class UninitializedLocalProducer(local: Int)             extends InitialProducer
+case class ExceptionProducer(handlerFrame: Frame[_ <: Value]) extends InitialProducer
+
+class InitialProducerSourceInterpreter extends SourceInterpreter {
+  override def newParameterValue(isInstanceMethod: Boolean, local: Int, tp: Type): SourceValue = {
+    new SourceValue(tp.getSize, ParameterProducer(local))
+  }
+
+  override def newEmptyNonParameterLocalValue(local: Int): SourceValue = {
+    new SourceValue(1, UninitializedLocalProducer(local))
+  }
+
+  override def newExceptionValue(tryCatchBlockNode: TryCatchBlockNode, handlerFrame: Frame[_ <: Value], exceptionType: Type): SourceValue = {
+    new SourceValue(1, ExceptionProducer(handlerFrame))
+  }
+}
\ No newline at end of file
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 9bd016f964..0ec550981a 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -14,7 +14,6 @@ import scala.tools.asm.commons.CodeSizeEvaluator
 import scala.tools.asm.tree.analysis._
 import scala.tools.asm.{MethodWriter, ClassWriter, Label, Opcodes}
 import scala.tools.asm.tree._
-import scala.collection.convert.decorateAsScala._
 import GenBCode._
 import scala.collection.convert.decorateAsScala._
 import scala.collection.convert.decorateAsJava._
@@ -73,11 +72,18 @@ object BytecodeUtils {
     op >= Opcodes.IRETURN && op <= Opcodes.RETURN
   }
 
-  def isVarInstruction(instruction: AbstractInsnNode): Boolean = {
+  def isLoad(instruction: AbstractInsnNode): Boolean = {
     val op = instruction.getOpcode
-    (op >= Opcodes.ILOAD  && op <= Opcodes.ALOAD) || (op >= Opcodes.ISTORE && op <= Opcodes.ASTORE)
+    op >= Opcodes.ILOAD  && op <= Opcodes.ALOAD
   }
 
+  def isStore(instruction: AbstractInsnNode): Boolean = {
+    val op = instruction.getOpcode
+    op >= Opcodes.ISTORE && op <= Opcodes.ASTORE
+  }
+
+  def isVarInstruction(instruction: AbstractInsnNode): Boolean = isLoad(instruction) || isStore(instruction)
+
   def isExecutable(instruction: AbstractInsnNode): Boolean = instruction.getOpcode >= 0
 
   def isConstructor(methodNode: MethodNode): Boolean = {
diff --git a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
index d0ffd06b01..ee9580c1c3 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/CodeGenTools.scala
@@ -6,7 +6,7 @@ import scala.collection.mutable.ListBuffer
 import scala.reflect.internal.util.BatchSourceFile
 import scala.reflect.io.VirtualDirectory
 import scala.tools.asm.Opcodes
-import scala.tools.asm.tree.{ClassNode, MethodNode}
+import scala.tools.asm.tree.{AbstractInsnNode, ClassNode, MethodNode}
 import scala.tools.cmd.CommandLineParser
 import scala.tools.nsc.io.AbstractFile
 import scala.tools.nsc.reporters.StoreReporter
@@ -15,6 +15,7 @@ import scala.tools.nsc.{Settings, Global}
 import scala.tools.partest.ASMConverters
 import scala.collection.JavaConverters._
 import scala.tools.testing.TempDir
+import AsmUtils._
 
 object CodeGenTools {
   import ASMConverters._
@@ -151,6 +152,17 @@ object CodeGenTools {
   def getSingleMethod(classNode: ClassNode, name: String): Method =
     convertMethod(classNode.methods.asScala.toList.find(_.name == name).get)
 
+  /**
+   * Instructions that match `query` when textified.
+   * If `query` starts with a `+`, the next instruction is returned.
+   */
+  def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = {
+    val useNext = query(0) == '+'
+    val instrPart = if (useNext) query.drop(1) else query
+    val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList
+    if (useNext) insns.map(_.getNext) else insns
+  }
+
   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))
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 3a85f03da2..94e776aadb 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
@@ -38,17 +38,6 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     nullnessAnalyzer
   }
 
-  /**
-   * Instructions that match `query` when textified.
-   * If `query` starts with a `+`, the next instruction is returned.
-   */
-  def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = {
-    val useNext = query(0) == '+'
-    val instrPart = if (useNext) query.drop(1) else query
-    val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList
-    if (useNext) insns.map(_.getNext) else insns
-  }
-
   def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: Nullness): Unit = {
     for (i <- findInstr(method, query)) {
       val r = analyzer.frameAt(i, method).getValue(index).nullness
diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala
new file mode 100644
index 0000000000..9af9ef54fc
--- /dev/null
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/ProdConsAnalyzerTest.scala
@@ -0,0 +1,249 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.junit.Assert._
+
+import scala.tools.asm.Opcodes
+import scala.tools.asm.tree.AbstractInsnNode
+import scala.tools.partest.ASMConverters._
+import scala.tools.testing.ClearAfterClass
+import CodeGenTools._
+import AsmUtils._
+
+object ProdConsAnalyzerTest extends ClearAfterClass.Clearable {
+  var noOptCompiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:none")
+
+  def clear(): Unit = {
+    noOptCompiler = null
+  }
+}
+
+@RunWith(classOf[JUnit4])
+class ProdConsAnalyzerTest extends ClearAfterClass {
+  ClearAfterClass.stateToClear = ProdConsAnalyzerTest
+  val noOptCompiler = ProdConsAnalyzerTest.noOptCompiler
+
+  def prodToString(producer: AbstractInsnNode) = producer match {
+    case p: InitialProducer => p.toString
+    case p => textify(p)
+  }
+
+  def testSingleInsn(singletonInsns: Traversable[AbstractInsnNode], expected: String): Unit = {
+    testInsn(single(singletonInsns), expected)
+  }
+
+  def testMultiInsns(insns: Traversable[AbstractInsnNode], expected: Traversable[String]): Unit = {
+    assertTrue(s"Sizes don't match: ${insns.size} vs ${expected.size}", insns.size == expected.size)
+    for (insn <- insns) {
+      val txt = prodToString(insn)
+      assertTrue(s"Instruction $txt not found in ${expected mkString ", "}", expected.exists(txt.contains))
+    }
+  }
+
+  def testInsn(insn: AbstractInsnNode, expected: String): Unit = {
+    val txt = prodToString(insn)
+    assertTrue(s"Expected $expected, found $txt", txt contains expected)
+  }
+
+  def single[T](c: Traversable[T]): T = {
+    assertTrue(s"Expected singleton collection, got $c", c.size == 1)
+    c.head
+  }
+
+  @Test
+  def parameters(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f = this.toString")
+    val a = new ProdConsAnalyzer(m, "C")
+    val call = findInstr(m, "INVOKEVIRTUAL").head
+
+    testSingleInsn(a.producersForValueAt(call, 1), "ALOAD 0") // producer of stack value
+    testSingleInsn(a.producersForInputsOf(call), "ALOAD 0")
+
+    testSingleInsn(a.consumersOfValueAt(call.getNext, 1), "ARETURN")  // consumer of `toString` result
+    testSingleInsn(a.consumersOfOutputsFrom(call), "ARETURN")
+
+    testSingleInsn(a.ultimateConsumersOfValueAt(call.getNext, 1), "ARETURN")
+
+    testSingleInsn(a.initialProducersForValueAt(call, 1), "ParameterProducer")
+    testSingleInsn(a.producersForValueAt(call, 0), "ParameterProducer")
+  }
+
+  @Test
+  def parametersInitialProducer(): Unit = {
+    // mutates a parameter local (not possible in scala, but in bytecode)
+    import Opcodes._
+    val m = genMethod(descriptor = "(I)I")(
+      Label(0),
+      VarOp(ILOAD, 1),
+      Jump(IFNE, Label(1)),
+      Op(ICONST_1),
+      VarOp(ISTORE, 1),
+      Label(1),
+      VarOp(ILOAD, 1),
+      Op(IRETURN),
+      Label(2)
+    )
+    m.maxLocals = 2
+    m.maxStack = 1
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val ifne = findInstr(m, "IFNE").head
+    testSingleInsn(a.producersForValueAt(ifne, 1), "ParameterProducer")
+
+    val ret = findInstr(m, "IRETURN").head
+    testMultiInsns(a.producersForValueAt(ret, 1), List("ParameterProducer", "ISTORE 1"))
+  }
+
+  @Test
+  def branching(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f(x: Int) = { var a = x; if (a == 0) a = 12; a }")
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(ret) = findInstr(m, "IRETURN")
+    testMultiInsns(a.producersForValueAt(ret, 2), List("ISTORE 2", "ISTORE 2"))
+    testMultiInsns(a.initialProducersForValueAt(ret, 2), List("BIPUSH 12", "ParameterProducer"))
+
+    val List(bipush) = findInstr(m, "BIPUSH 12")
+    testSingleInsn(a.consumersOfOutputsFrom(bipush), "ISTORE 2")
+    testSingleInsn(a.ultimateConsumersOfValueAt(bipush.getNext, 3), "IRETURN")
+  }
+
+  @Test
+  def checkCast(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f(o: Object) = o.asInstanceOf[String]")
+    val a = new ProdConsAnalyzer(m, "C")
+    assert(findInstr(m, "CHECKCAST java/lang/String").length == 1)
+
+    val List(ret) = findInstr(m, "ARETURN")
+    testSingleInsn(a.initialProducersForInputsOf(ret), "ParameterProducer(1)")
+  }
+
+  @Test
+  def instanceOf(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f(o: Object) = o.isInstanceOf[String]")
+    val a = new ProdConsAnalyzer(m, "C")
+    assert(findInstr(m, "INSTANCEOF java/lang/String").length == 1)
+
+    val List(ret) = findInstr(m, "IRETURN")
+    testSingleInsn(a.initialProducersForInputsOf(ret), "INSTANCEOF")
+  }
+
+  @Test
+  def unInitLocal(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f(b: Boolean) = { if (b) { var a = 0; println(a) }; 1 }")
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(store) = findInstr(m, "ISTORE")
+    val List(call)  = findInstr(m, "INVOKEVIRTUAL")
+    val List(ret)   = findInstr(m, "IRETURN")
+
+    testSingleInsn(a.producersForValueAt(store, 2), "UninitializedLocalProducer(2)")
+    testSingleInsn(a.producersForValueAt(call, 2), "ISTORE")
+    testMultiInsns(a.producersForValueAt(ret, 2), List("UninitializedLocalProducer", "ISTORE"))
+  }
+
+  @Test
+  def dupCopying(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f = new Object")
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(newO)   = findInstr(m, "NEW")
+    val List(constr) = findInstr(m, "INVOKESPECIAL")
+
+    testSingleInsn(a.producersForInputsOf(constr), "DUP")
+    testSingleInsn(a.initialProducersForInputsOf(constr), "NEW")
+
+    testSingleInsn(a.consumersOfOutputsFrom(newO), "DUP")
+    testMultiInsns(a.ultimateConsumersOfOutputsFrom(newO), List("INVOKESPECIAL", "ARETURN"))
+  }
+
+  @Test
+  def multiProducer(): Unit = {
+    import Opcodes._
+    val m = genMethod(descriptor = "(I)I")(
+      VarOp(ILOAD, 1),
+      VarOp(ILOAD, 1),
+      Op(DUP2),
+      Op(IADD),
+      Op(SWAP),
+      VarOp(ISTORE, 1),
+      Op(IRETURN)
+    )
+    m.maxLocals = 2
+    m.maxStack = 4
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(dup2)  = findInstr(m, "DUP2")
+    val List(add)   = findInstr(m, "IADD")
+    val List(swap)  = findInstr(m, "SWAP")
+    val List(store) = findInstr(m, "ISTORE")
+    val List(ret)   = findInstr(m, "IRETURN")
+
+    testMultiInsns(a.producersForInputsOf(dup2), List("ILOAD", "ILOAD"))
+    testSingleInsn(a.consumersOfValueAt(dup2.getNext, 4), "IADD")
+    testSingleInsn(a.consumersOfValueAt(dup2.getNext, 5), "IADD")
+    testMultiInsns(a.consumersOfOutputsFrom(dup2), List("IADD", "SWAP"))
+
+    testSingleInsn(a.ultimateConsumersOfOutputsFrom(dup2), "IADD") // the 'store' is not here: it's a copying instr, so not an ultimate consumer.
+    testMultiInsns(a.consumersOfOutputsFrom(swap), List("IRETURN", "ISTORE"))
+    testSingleInsn(a.ultimateConsumersOfOutputsFrom(swap), "IRETURN") // again, no store
+    testSingleInsn(a.initialProducersForInputsOf(add), "ParameterProducer(1)")
+
+    testMultiInsns(a.producersForInputsOf(swap), List("IADD", "DUP2"))
+    testSingleInsn(a.consumersOfValueAt(swap.getNext, 4), "ISTORE")
+    testSingleInsn(a.consumersOfValueAt(swap.getNext, 3), "IRETURN")
+    testSingleInsn(a.initialProducersForInputsOf(store), "ParameterProducer(1)")
+    testSingleInsn(a.initialProducersForInputsOf(ret), "IADD")
+  }
+
+  @Test
+  def iincProdCons(): Unit = {
+    import Opcodes._
+    val m = genMethod(descriptor = "(I)I")(
+      Incr(IINC, 1, 1), // producer and cosumer of local variable 1
+      VarOp(ILOAD, 1),
+      Op(IRETURN)
+    )
+    m.maxLocals = 2
+    m.maxStack = 1
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(inc) = findInstr(m, "IINC")
+    val List(load) = findInstr(m, "ILOAD")
+    val List(ret) = findInstr(m, "IRETURN")
+
+    testSingleInsn(a.producersForInputsOf(inc), "ParameterProducer(1)")
+    testSingleInsn(a.consumersOfOutputsFrom(inc), "ILOAD")
+    testSingleInsn(a.ultimateConsumersOfOutputsFrom(inc), "IRETURN")
+    testSingleInsn(a.consumersOfValueAt(inc, 1), "IINC") // parameter value has a single consumer, the IINC
+    testSingleInsn(a.ultimateConsumersOfValueAt(inc, 1), "IINC")
+
+    testSingleInsn(a.producersForInputsOf(load), "IINC")
+    testSingleInsn(a.producersForValueAt(load, 1), "IINC")
+
+    testSingleInsn(a.initialProducersForInputsOf(ret), "IINC")
+  }
+
+  @Test
+  def copyingInsns(): Unit = {
+    val List(m) = compileMethods(noOptCompiler)("def f = 0l.asInstanceOf[Int]")
+    val a = new ProdConsAnalyzer(m, "C")
+
+    val List(cnst) = findInstr(m, "LCONST_0")
+    val List(l2i)  = findInstr(m, "L2I") // l2i is not a copying instruction
+    val List(ret)  = findInstr(m, "IRETURN")
+
+    testSingleInsn(a.consumersOfOutputsFrom(cnst), "L2I")
+    testSingleInsn(a.ultimateConsumersOfOutputsFrom(cnst), "L2I")
+
+    testSingleInsn(a.producersForInputsOf(l2i), "LCONST_0")
+    testSingleInsn(a.initialProducersForInputsOf(l2i), "LCONST_0")
+
+    testSingleInsn(a.consumersOfOutputsFrom(l2i), "IRETURN")
+    testSingleInsn(a.producersForInputsOf(ret), "L2I")
+  }
+}
diff --git a/versions.properties b/versions.properties
index a7ec8caedc..9f297e9b93 100644
--- a/versions.properties
+++ b/versions.properties
@@ -33,7 +33,7 @@ scala-swing.version.number=1.0.2
 akka-actor.version.number=2.3.10
 actors-migration.version.number=1.1.0
 jline.version=2.12.1
-scala-asm.version=5.0.4-scala-1
+scala-asm.version=5.0.4-scala-2
 
 # external modules, used internally (not shipped)
 partest.version.number=1.0.7