Nullness Analysis

Tracks nullness of values using an ASM analyzer.

Tracking nullness requires alias tracking for local variables and
stack values. For example, after an instance call, local variables
that point to the same object as the receiver are treated not-null.

6 files changed, 1031 insertions, 7 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala
new file mode 100644
index 0000000000..9494553ce1
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala
@@ -0,0 +1,247 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import scala.annotation.switch
+import scala.collection.{mutable, immutable}
+import scala.tools.asm.Opcodes
+import scala.tools.asm.tree._
+import scala.tools.asm.tree.analysis.{Analyzer, Value, Frame, Interpreter}
+import opt.BytecodeUtils._
+
+object AliasingFrame {
+  private var _idCounter: Long = 0l
+  private def nextId = { _idCounter += 1; _idCounter }
+}
+
+class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLocals, nStack) {
+  import Opcodes._
+
+  // Auxiliary constructor required for implementing `AliasingAnalyzer.newFrame`
+  def this(src: Frame[_ <: V]) {
+    this(src.getLocals, src.getMaxStackSize)
+    init(src)
+  }
+
+  /**
+   * For each slot (entry in the `values` array of the frame), an id that uniquely represents
+   * the object stored in it. If two values have the same id, they are aliases of the same
+   * object.
+   */
+  private val aliasIds: Array[Long] = Array.fill(nLocals + nStack)(AliasingFrame.nextId)
+
+  /**
+   * The object alias id of for a value index.
+   */
+  def aliasId(entry: Int) = aliasIds(entry)
+
+  /**
+   * Returns the indices of the values array which are aliases of the object `id`.
+   */
+  def valuesWithAliasId(id: Long): Set[Int] = immutable.BitSet.empty ++ aliasIds.indices.filter(i => aliasId(i) == id)
+
+  /**
+   * The set of aliased values for a given entry in the `values` array.
+   */
+  def aliasesOf(entry: Int): Set[Int] = valuesWithAliasId(aliasIds(entry))
+
+  /**
+   * Define a new alias. For example, given
+   *   var a = this       // this, a have the same aliasId
+   * then an assignment
+   *   b = a
+   * will set the same the aliasId for `b`.
+   */
+  private def newAlias(assignee: Int, source: Int): Unit = {
+    aliasIds(assignee) = aliasIds(source)
+  }
+
+  /**
+   * An assignment
+   *   a = someUnknownValue()
+   * sets a fresh alias id for `a`.
+   * A stack value is also removed from its alias set when being consumed.
+   */
+  private def removeAlias(assignee: Int): Unit = {
+    aliasIds(assignee) = AliasingFrame.nextId
+  }
+
+  override def execute(insn: AbstractInsnNode, interpreter: Interpreter[V]): Unit = {
+    // Make the extendsion methods easier to use (otherwise we have to repeat `this`.stackTop)
+    def stackTop: Int = this.stackTop
+    def peekStack(n: Int): V = this.peekStack(n)
+
+    val (consumed, produced) = InstructionStackEffect(insn, this) // needs to be called before super.execute, see its doc
+    super.execute(insn, interpreter)
+
+    (insn.getOpcode: @switch) match {
+      case ALOAD =>
+        newAlias(assignee = stackTop, source = insn.asInstanceOf[VarInsnNode].`var`)
+
+      case DUP =>
+        val top = stackTop
+        newAlias(assignee = top, source = top - 1)
+
+      case DUP_X1 =>
+        val top = stackTop
+        newAlias(assignee = top,     source = top - 1)
+        newAlias(assignee = top - 1, source = top - 2)
+        newAlias(assignee = top - 2, source = top)
+
+      case DUP_X2 =>
+        // Check if the second element on the stack is size 2
+        // https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.dup_x2
+        val isSize2 = peekStack(1).getSize == 2
+        val top = stackTop
+        newAlias(assignee = top,     source = top - 1)
+        newAlias(assignee = top - 1, source = top - 2)
+        if (isSize2) {
+          // Size 2 values on the stack only take one slot in the `values` array
+          newAlias(assignee = top - 2, source = top)
+        } else {
+          newAlias(assignee = top - 2, source = top - 3)
+          newAlias(assignee = top - 3, source = top)
+        }
+
+      case DUP2 =>
+        val isSize2 = peekStack(0).getSize == 2
+        val top = stackTop
+        if (isSize2) {
+          newAlias(assignee = top, source = top - 1)
+        } else {
+          newAlias(assignee = top - 1, source = top - 3)
+          newAlias(assignee = top,     source = top - 2)
+        }
+
+      case DUP2_X1 =>
+        val isSize2 = peekStack(0).getSize == 2
+        val top = stackTop
+        if (isSize2) {
+          newAlias(assignee = top,     source = top - 1)
+          newAlias(assignee = top - 1, source = top - 2)
+          newAlias(assignee = top - 2, source = top)
+        } else {
+          newAlias(assignee = top,     source = top - 2)
+          newAlias(assignee = top - 1, source = top - 3)
+          newAlias(assignee = top - 2, source = top - 4)
+          newAlias(assignee = top - 4, source = top)
+          newAlias(assignee = top - 5, source = top - 1)
+        }
+
+      case DUP2_X2 =>
+        val top = stackTop
+        // https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.html#jvms-6.5.dup2_x2
+        val v1isSize2 = peekStack(0).getSize == 2
+        if (v1isSize2) {
+          newAlias(assignee = top,     source = top - 1)
+          newAlias(assignee = top - 1, source = top - 2)
+          val v2isSize2 = peekStack(1).getSize == 2
+          if (v2isSize2) {
+            // Form 4
+            newAlias(assignee = top - 2, source = top)
+          } else {
+            // Form 2
+            newAlias(assignee = top - 2, source = top - 3)
+            newAlias(assignee = top - 3, source = top)
+          }
+        } else {
+          newAlias(assignee = top,     source = top - 2)
+          newAlias(assignee = top - 1, source = top - 3)
+          newAlias(assignee = top - 2, source = top - 4)
+          val v3isSize2 = peekStack(2).getSize == 2
+          if (v3isSize2) {
+            // Form 3
+            newAlias(assignee = top - 3, source = top)
+            newAlias(assignee = top - 4, source = top - 1)
+          } else {
+            // Form 1
+            newAlias(assignee = top - 3, source = top - 5)
+            newAlias(assignee = top - 4, source = top)
+            newAlias(assignee = top - 5, source = top - 1)
+          }
+        }
+
+      case SWAP =>
+        val top = stackTop
+        val idTop = aliasIds(top)
+        aliasIds(top)     = aliasIds(top - 1)
+        aliasIds(top - 1) = idTop
+
+      case opcode =>
+        if (opcode == ASTORE) {
+          // Not a separate case because we need to remove the consumed stack value from alias sets after.
+          val stackTopBefore = stackTop - produced + consumed
+          val local = insn.asInstanceOf[VarInsnNode].`var`
+          newAlias(assignee = local, source = stackTopBefore)
+          // if the value written is size 2, it overwrites the subsequent slot, which is then no
+          // longer an alias of anything. see the corresponding case in `Frame.execute`.
+          if (getLocal(local).getSize == 2)
+            removeAlias(local + 1)
+
+          // if the value at the preceding index is size 2, it is no longer valid, so we remove its
+          // aliasing. see corresponding case in `Frame.execute`
+          if (local > 0) {
+            val precedingValue = getLocal(local - 1)
+            if (precedingValue != null && precedingValue.getSize == 2)
+              removeAlias(local - 1)
+          }
+        }
+
+        // Remove consumed stack values from aliasing sets.
+        // Example: iadd
+        //  - before: local1, local2, stack1, consumed1, consumed2
+        //  - after:  local1, local2, stack1, produced1             // stackTop = 3
+        val firstConsumed = stackTop - produced + 1                 // firstConsumed = 3
+        for (i <- 0 until consumed)
+          removeAlias(firstConsumed + i)                            // remove aliases for 3 and 4
+
+        // We don't need to set the aliases ids for the produced values: the aliasIds array already
+        // contains fresh ids for non-used stack values (ensured by removeAlias).
+    }
+  }
+
+  /**
+   * Merge the AliasingFrame `other` into this AliasingFrame.
+   *
+   * Aliases that are common in both frames are kept. Example:
+   *
+   * var x, y = null
+   * if (...) {
+   *   x = a
+   *   y = a     // (x, y, a) are aliases
+   * } else {
+   *   x = a
+   *   y = b     // (x, a) and (y, b)
+   * }
+   * [...]       // (x, a)
+   */
+  override def merge(other: Frame[_ <: V], interpreter: Interpreter[V]): Boolean = {
+    val valuesChanged = super.merge(other, interpreter)
+    var aliasesChanged = false
+    val aliasingOther = other.asInstanceOf[AliasingFrame[_]]
+    for (i <- aliasIds.indices) {
+      val thisAliases = aliasesOf(i)
+      val thisNotOther = thisAliases diff (thisAliases intersect aliasingOther.aliasesOf(i))
+      if (thisNotOther.nonEmpty) {
+        aliasesChanged = true
+        thisNotOther foreach removeAlias
+      }
+    }
+    valuesChanged || aliasesChanged
+  }
+
+  override def init(src: Frame[_ <: V]): Frame[V] = {
+    super.init(src)
+    compat.Platform.arraycopy(src.asInstanceOf[AliasingFrame[_]].aliasIds, 0, aliasIds, 0, aliasIds.length)
+    this
+  }
+}
+
+/**
+ * An analyzer that uses AliasingFrames instead of bare Frames. This can be used when an analysis
+ * needs to track aliases, but doesn't require a more specific Frame subclass.
+ */
+class AliasingAnalyzer[V <: Value](interpreter: Interpreter[V]) extends Analyzer[V](interpreter) {
+  override def newFrame(nLocals: Int, nStack: Int): AliasingFrame[V] = new AliasingFrame(nLocals, nStack)
+  override def newFrame(src: Frame[_ <: V]): AliasingFrame[V] = new AliasingFrame(src)
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
new file mode 100644
index 0000000000..3d6c53765e
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
@@ -0,0 +1,248 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import scala.annotation.switch
+import scala.tools.asm.Opcodes._
+import scala.tools.asm.Type
+import scala.tools.asm.tree.{MultiANewArrayInsnNode, InvokeDynamicInsnNode, MethodInsnNode, AbstractInsnNode}
+import scala.tools.asm.tree.analysis.{Frame, Value}
+import opt.BytecodeUtils._
+
+object InstructionStackEffect {
+  /**
+   * Returns a pair with the number of stack values consumed and produced by `insn`.
+   * This method requires the `frame` to be in the state **before** executing / interpreting
+   * the `insn`.
+   */
+  def apply[V <: Value](insn: AbstractInsnNode, frame: Frame[V]): (Int, Int) = {
+    def peekStack(n: Int): V = frame.peekStack(n)
+
+    (insn.getOpcode: @switch) match {
+      // The order of opcodes is the same as in Frame.execute.
+      case NOP => (0, 0)
+
+      case ACONST_NULL |
+           ICONST_M1 |
+           ICONST_0 |
+           ICONST_1 |
+           ICONST_2 |
+           ICONST_3 |
+           ICONST_4 |
+           ICONST_5 |
+           LCONST_0 |
+           LCONST_1 |
+           FCONST_0 |
+           FCONST_1 |
+           FCONST_2 |
+           DCONST_0 |
+           DCONST_1 |
+           BIPUSH |
+           SIPUSH |
+           LDC |
+           ILOAD |
+           LLOAD |
+           FLOAD |
+           DLOAD |
+           ALOAD => (0, 1)
+
+      case IALOAD |
+           LALOAD |
+           FALOAD |
+           DALOAD |
+           AALOAD |
+           BALOAD |
+           CALOAD |
+           SALOAD => (2, 1)
+
+      case ISTORE |
+           LSTORE |
+           FSTORE |
+           DSTORE |
+           ASTORE => (1, 0)
+
+      case IASTORE |
+           LASTORE |
+           FASTORE |
+           DASTORE |
+           AASTORE |
+           BASTORE |
+           CASTORE |
+           SASTORE => (3, 0)
+
+      case POP => (1, 0)
+
+      case POP2 =>
+        val isSize2 = peekStack(0).getSize == 2
+        if (isSize2) (1, 0) else (2, 0)
+
+      case DUP => (0, 1)
+
+      case DUP_X1 => (2, 3)
+
+      case DUP_X2 =>
+        val isSize2 = peekStack(1).getSize == 2
+        if (isSize2) (2, 3) else (3, 4)
+
+      case DUP2 =>
+        val isSize2 = peekStack(0).getSize == 2
+        if (isSize2) (0, 1) else (0, 2)
+
+      case DUP2_X1 =>
+        val isSize2 = peekStack(0).getSize == 2
+        if (isSize2) (2, 3) else (3, 4)
+
+      case DUP2_X2 =>
+        val v1isSize2 = peekStack(0).getSize == 2
+        if (v1isSize2) {
+          val v2isSize2 = peekStack(1).getSize == 2
+          if (v2isSize2) (2, 3) else (3, 4)
+        } else {
+          val v3isSize2 = peekStack(2).getSize == 2
+          if (v3isSize2) (3, 5) else (4, 6)
+        }
+
+      case SWAP => (2, 2)
+
+      case IADD |
+           LADD |
+           FADD |
+           DADD |
+           ISUB |
+           LSUB |
+           FSUB |
+           DSUB |
+           IMUL |
+           LMUL |
+           FMUL |
+           DMUL |
+           IDIV |
+           LDIV |
+           FDIV |
+           DDIV |
+           IREM |
+           LREM |
+           FREM |
+           DREM => (2, 1)
+
+      case INEG |
+           LNEG |
+           FNEG |
+           DNEG => (1, 1)
+
+      case ISHL |
+           LSHL |
+           ISHR |
+           LSHR |
+           IUSHR |
+           LUSHR |
+           IAND |
+           LAND |
+           IOR |
+           LOR |
+           IXOR |
+           LXOR => (2, 1)
+
+      case IINC => (0, 0)
+
+      case I2L |
+           I2F |
+           I2D |
+           L2I |
+           L2F |
+           L2D |
+           F2I |
+           F2L |
+           F2D |
+           D2I |
+           D2L |
+           D2F |
+           I2B |
+           I2C |
+           I2S => (1, 1)
+
+      case LCMP |
+           FCMPL |
+           FCMPG |
+           DCMPL |
+           DCMPG => (2, 1)
+
+      case IFEQ |
+           IFNE |
+           IFLT |
+           IFGE |
+           IFGT |
+           IFLE => (1, 0)
+
+      case IF_ICMPEQ |
+           IF_ICMPNE |
+           IF_ICMPLT |
+           IF_ICMPGE |
+           IF_ICMPGT |
+           IF_ICMPLE |
+           IF_ACMPEQ |
+           IF_ACMPNE => (2, 0)
+
+      case GOTO => (0, 0)
+
+      case JSR => (0, 1)
+
+      case RET => (0, 0)
+
+      case TABLESWITCH |
+           LOOKUPSWITCH => (1, 0)
+
+      case IRETURN |
+           LRETURN |
+           FRETURN |
+           DRETURN |
+           ARETURN => (frame.getStackSize, 0)
+
+      case RETURN => (frame.getStackSize, 0)
+
+      case GETSTATIC => (0, 1)
+
+      case PUTSTATIC => (1, 0)
+
+      case GETFIELD => (1, 1)
+
+      case PUTFIELD => (2, 0)
+
+      case INVOKEVIRTUAL |
+           INVOKESPECIAL |
+           INVOKESTATIC |
+           INVOKEINTERFACE =>
+        val desc = insn.asInstanceOf[MethodInsnNode].desc
+        val cons = Type.getArgumentTypes(desc).length + (if (insn.getOpcode == INVOKESTATIC) 0 else 1)
+        val prod = if (Type.getReturnType(desc) == Type.VOID_TYPE) 0 else 1
+        (cons, prod)
+
+      case INVOKEDYNAMIC =>
+        val desc = insn.asInstanceOf[InvokeDynamicInsnNode].desc
+        val cons = Type.getArgumentTypes(desc).length
+        val prod = if (Type.getReturnType(desc) == Type.VOID_TYPE) 0 else 1
+        (cons, prod)
+
+      case NEW => (0, 1)
+
+      case NEWARRAY |
+           ANEWARRAY |
+           ARRAYLENGTH => (1, 1)
+
+      case ATHROW => (frame.getStackSize, 0)
+
+      case CHECKCAST => (0, 0)
+
+      case INSTANCEOF => (1, 1)
+
+      case MONITORENTER |
+           MONITOREXIT => (1, 0)
+
+      case MULTIANEWARRAY => (insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1)
+
+      case IFNULL |
+           IFNONNULL => (1, 0)
+    }
+  }
+
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
new file mode 100644
index 0000000000..18c17bc992
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
@@ -0,0 +1,262 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import java.util
+
+import scala.annotation.switch
+import scala.tools.asm.{Type, Opcodes}
+import scala.tools.asm.tree.{MethodInsnNode, LdcInsnNode, AbstractInsnNode}
+import scala.tools.asm.tree.analysis.{Frame, Analyzer, Interpreter, Value}
+import scala.tools.nsc.backend.jvm.opt.BytecodeUtils
+import BytecodeUtils._
+
+/**
+ * Some notes on the ASM ananlyzer framework.
+ *
+ * Value
+ *  - Abstract, needs to be implemented for each analysis.
+ *  - Represents the desired information about local variables and stack values, for example:
+ *    - Is this value known to be null / not null?
+ *    - What are the instructions that could potentially have produced this value?
+ *
+ * Interpreter
+ *  - Abstract, needs to be implemented for each analysis. Sometimes one can subclass an existing
+ *    interpreter, e.g., SourceInterpreter or BasicInterpreter.
+ *  - Multiple abstract methods that receive an instruction and the instruction's input values, and
+ *    return a value representing the result of that instruction.
+ *    - Note: due to control flow, the interpreter can be invoked multiple times for the same
+ *      instruction, until reaching a fixed point.
+ *  - Abstract `merge` function that computes the least upper bound of two values. Used by
+ *    Frame.merge (see below).
+ *
+ * Frame
+ *  - Can be used directly for many analyses, no subclass required.
+ *  - Every frame has an array of values: one for each local variable and for each stack slot.
+ *    - 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.
+ *  - 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
+ *      - pass them to the interpreter together with the instruction
+ *      - if applicable, push the resulting value on the stack
+ *  - Defines the `merge(otherFrame)` method
+ *    - called by the analyzer when multiple control flow paths lead to an instruction
+ *      - the frame at the branching instruction is merged into the current frame of the
+ *        instruction (held by the analyzer)
+ *      - mutates the values of the current frame, merges all values using interpreter.merge.
+ *
+ * Analyzer
+ *   - Stores a frame for each instruction
+ *   - `merge` function takes an instruction and a frame, merges the existing frame for that instr
+ *     (from the frames array) with the new frame passed as argument.
+ *     if the frame changed, puts the instruction on the work queue (fixpiont).
+ *   - initial frame: initialized for first instr by calling interpreter.new[...]Value
+ *     for each slot (locals and params), stored in frames[firstInstr] by calling `merge`
+ *   - work queue of instructions (`queue` array, `top` index for next instruction to analyze)
+ *   - analyze(method): simulate control flow. while work queue non-empty:
+ *     - copy the state of `frames[instr]` into a local frame `current`
+ *     - call `current.execute(instr, interpreter)`, mutating the `current` frame
+ *     - if it's a branching instruction
+ *       - for all potential destination instructions
+ *         - merge the destination instruction frame with the `current` frame
+ *           (this enqueues the destination instr if its frame changed)
+ *       - invoke `newControlFlowEdge` (see below)
+ *   - the analyzer also tracks active exception handlers at each instruction
+ *   - the empty method `newControlFlowEdge` can be overridden to track control flow if required
+ *
+ *
+ * Some notes on nullness analysis.
+ *
+ * For an instance method, `this` is non-null at entry. So we have to return a NotNull value when
+ * the analyzer is initializing the first frame of a method (see above). This required a change of
+ * the analyzer: before it would simply call `interpreter.newValue`, where we don't have the
+ * required context. See https://github.com/scala/scala-asm/commit/8133d75032.
+ *
+ * After some operations we know that a certain value is not null (e.g. the receiver of an instance
+ * call). However, the receiver is an value on the stack and consumed while interpreting the
+ * instruction - so we can only gain some knowledge if we know that the receiver was an alias of
+ * some other local variable or stack slot. Therefore we use the AliasingFrame class.
+ *
+ * TODO:
+ * Finally, we'd also like to exploit the knowledge gained from `if (x == null)` tests: x is known
+ * to be null in one branch, not null in the other. This will make use of alias tracking as well.
+ * We still have to figure out how to do this exactly in the analyzer framework.
+ */
+
+/**
+ * Type to represent nullness of values.
+ */
+sealed trait Nullness {
+  final def merge(other: Nullness) = if (this == other) this else Unknown
+}
+case object NotNull extends Nullness
+case object Unknown extends Nullness
+case object Null    extends Nullness
+
+/**
+ * Represents the nullness state for a local variable or stack value.
+ *
+ * Note that nullness of primitive values is not tracked, it will be always [[Unknown]].
+ *
+ * @param nullness     The nullness of this value.
+ * @param longOrDouble True if this value is a long or double. The Analyzer framework needs to know
+ *                     the size of each value when interpreting instructions, see `Frame.execute`.
+ */
+final case class NullnessValue(nullness: Nullness, longOrDouble: Boolean) extends Value {
+  def this(nullness: Nullness, insn: AbstractInsnNode) = this(nullness, longOrDouble = BytecodeUtils.instructionResultSize(insn) == 2)
+
+  /**
+   * The size of the slot described by this value. Cannot be 0 because no values are allocated
+   * for void-typed slots, see NullnessInterpreter.newValue.
+   **/
+  def getSize: Int = if (longOrDouble) 2 else 1
+
+  def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, longOrDouble)
+}
+
+object NullnessValue {
+  def apply(nullness: Nullness, insn: AbstractInsnNode) = new NullnessValue(nullness, insn)
+}
+
+final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) {
+  def newValue(tp: Type): NullnessValue = {
+    // ASM loves giving semantics to null. The behavior here is the same as in SourceInterpreter,
+    // which is provided by the framework.
+    //
+    // (1) For the void type, the ASM framework expects newValue to return `null`.
+    //     Also, the Frame.returnValue field is `null` for methods with return type void.
+    //     Example callsite passing VOID_TYPE: in Analyzer, `newValue(Type.getReturnType(m.desc))`.
+    //
+    // (2) `tp` may also be `null`. When creating the initial frame, the analyzer invokes
+    //     `newValue(null)` for each local variable. We have to return a value of size 1.
+    if (tp == Type.VOID_TYPE) null // (1)
+    else NullnessValue(Unknown, longOrDouble = tp != null /*(2)*/ && tp.getSize == 2 )
+  }
+
+  override def newParameterValue(isInstanceMethod: Boolean, local: Int, tp: Type): NullnessValue = {
+    // For instance methods, the `this` parameter is known to be not null.
+    if (isInstanceMethod && local == 0) NullnessValue(NotNull, longOrDouble = false)
+    else super.newParameterValue(isInstanceMethod, local, tp)
+  }
+
+  def newOperation(insn: AbstractInsnNode): NullnessValue = {
+    val nullness = (insn.getOpcode: @switch) match {
+      case Opcodes.ACONST_NULL => Null
+
+      case Opcodes.LDC => insn.asInstanceOf[LdcInsnNode].cst match {
+        case _: String | _: Type => NotNull
+        case _ => Unknown
+      }
+
+      case _ => Unknown
+    }
+
+    // for Opcodes.NEW, we use Unknown. The value will become NotNull after the constructor call.
+    NullnessValue(nullness, insn)
+  }
+
+  def copyOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = value
+
+  def unaryOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = (insn.getOpcode: @switch) match {
+    case Opcodes.NEWARRAY |
+         Opcodes.ANEWARRAY => NullnessValue(NotNull, longOrDouble = false)
+
+    case _ => NullnessValue(Unknown, insn)
+  }
+
+  def binaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue): NullnessValue = {
+    NullnessValue(Unknown, insn)
+  }
+
+  def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = {
+    NullnessValue(Unknown, longOrDouble = false)
+  }
+
+  def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match {
+    case Opcodes.MULTIANEWARRAY =>
+      NullnessValue(NotNull, longOrDouble = false)
+
+    case _ =>
+      // TODO: use a list of methods that are known to return non-null values
+      NullnessValue(Unknown, insn)
+  }
+
+  def returnOperation(insn: AbstractInsnNode, value: NullnessValue, expected: NullnessValue): Unit = ()
+
+  def merge(a: NullnessValue, b: NullnessValue): NullnessValue = a merge b
+}
+
+class NullnessFrame(nLocals: Int, nStack: Int) extends AliasingFrame[NullnessValue](nLocals, nStack) {
+  // Auxiliary constructor required for implementing `NullnessAnalyzer.newFrame`
+  def this(src: Frame[_ <: NullnessValue]) {
+    this(src.getLocals, src.getMaxStackSize)
+    init(src)
+  }
+
+  override def execute(insn: AbstractInsnNode, interpreter: Interpreter[NullnessValue]): Unit = {
+    import Opcodes._
+
+    // get the object id of the object that is known to be not-null after this operation
+    val nullCheckedAliasId: Long = (insn.getOpcode: @switch) match {
+      case IALOAD |
+           LALOAD |
+           FALOAD |
+           DALOAD |
+           AALOAD |
+           BALOAD |
+           CALOAD |
+           SALOAD =>
+        aliasId(this.stackTop - 1)
+
+      case IASTORE |
+           FASTORE |
+           AASTORE |
+           BASTORE |
+           CASTORE |
+           SASTORE |
+           LASTORE |
+           DASTORE =>
+        aliasId(this.stackTop - 2)
+
+      case GETFIELD =>
+        aliasId(this.stackTop)
+
+      case PUTFIELD =>
+        aliasId(this.stackTop - 1)
+
+      case INVOKEVIRTUAL |
+           INVOKESPECIAL |
+           INVOKEINTERFACE =>
+        val desc = insn.asInstanceOf[MethodInsnNode].desc
+        val numArgs = Type.getArgumentTypes(desc).length
+        aliasId(this.stackTop - numArgs)
+
+      case ARRAYLENGTH |
+           MONITORENTER |
+           MONITOREXIT =>
+        aliasId(this.stackTop)
+
+      case _ =>
+        -1
+    }
+
+    super.execute(insn, interpreter)
+
+    if (nullCheckedAliasId != -1) {
+      for (i <- valuesWithAliasId(nullCheckedAliasId))
+        this.setValue(i, this.getValue(i).copy(nullness = NotNull))
+    }
+  }
+}
+
+/**
+ * This class is required to override the `newFrame` methods, which makes makes sure the analyzer
+ * uses NullnessFrames.
+ */
+class NullnessAnalyzer extends Analyzer[NullnessValue](new NullnessInterpreter) {
+  override def newFrame(nLocals: Int, nStack: Int): NullnessFrame = new NullnessFrame(nLocals, nStack)
+  override def newFrame(src: Frame[_ <: NullnessValue]): NullnessFrame = new NullnessFrame(src)
+}
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 201ab15177..314105da44 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/BytecodeUtils.scala
@@ -170,6 +170,8 @@ object BytecodeUtils {
     new InsnNode(op)
   }
 
+  def instructionResultSize(instruction: AbstractInsnNode) = InstructionResultSize(instruction)
+
   def labelReferences(method: MethodNode): Map[LabelNode, Set[AnyRef]] = {
     val res = mutable.Map.empty[LabelNode, Set[AnyRef]]
     def add(l: LabelNode, ref: AnyRef) = if (res contains l) res(l) = res(l) + ref else res(l) = Set(ref)
@@ -328,13 +330,38 @@ object BytecodeUtils {
   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.getFrames()(methodNode.instructions.indexOf(instruction))
+    def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.frameAt(instruction, methodNode)
+  }
+
+  implicit class AnalyzerExtendsions[V <: Value](val analyzer: Analyzer[V]) extends AnyVal {
+    def frameAt(instruction: AbstractInsnNode, methodNode: MethodNode): Frame[V] = analyzer.getFrames()(methodNode.instructions.indexOf(instruction))
   }
 
-  implicit class `frame extensions`[V <: Value](val frame: Frame[V]) extends AnyVal {
-    def peekDown(n: Int): V = {
-      val topIndex = frame.getStackSize - 1
-      frame.getStack(topIndex - n)
+  implicit class FrameExtensions[V <: Value](val frame: Frame[V]) extends AnyVal {
+    /**
+     * The value `n` positions down the stack.
+     */
+    def peekStack(n: Int): V = frame.getStack(frame.getMaxStackSize - 1 - n)
+
+    /**
+     * The index of the current stack top.
+     */
+    def stackTop = frame.getLocals + frame.getStackSize - 1
+
+    /**
+     * Gets the value at slot i, where i may be a local or a stack index.
+     */
+    def getValue(i: Int): V = {
+      if (i < frame.getLocals) frame.getLocal(i)
+      else frame.getStack(i - frame.getLocals)
+    }
+
+    /**
+     * Sets the value at slot i, where i may be a local or a stack index.
+     */
+    def setValue(i: Int, value: V): Unit = {
+      if (i < frame.getLocals) frame.setLocal(i, value)
+      else frame.setStack(i - frame.getLocals, value)
     }
   }
 }
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 ac5c9ce2e6..3aca15da69 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -189,7 +189,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
           // 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 receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekDown(traitMethodArgumentTypes.length)
+          val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length)
           for (i <- receiverValue.insns.asScala) {
             val cast = new TypeInsnNode(CHECKCAST, selfParamType.internalName)
             callsite.callsiteMethod.instructions.insert(i, cast)
@@ -400,7 +400,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
         val inlinedReturn = instructionMap(originalReturn)
         val returnReplacement = new InsnList
 
-        def drop(slot: Int) = returnReplacement add getPop(frame.peekDown(slot).getSize)
+        def drop(slot: Int) = returnReplacement add getPop(frame.peekStack(slot).getSize)
 
         // for non-void methods, store the stack top into the return local variable
         if (hasReturnValue) {
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala
new file mode 100644
index 0000000000..8d744f6d13
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/InstructionResultSize.scala
@@ -0,0 +1,240 @@
+package scala.tools.nsc.backend.jvm.opt
+
+import scala.annotation.switch
+import scala.tools.asm.{Handle, Type, Opcodes}
+import scala.tools.asm.tree._
+
+object InstructionResultSize {
+  import Opcodes._
+  def apply(instruction: AbstractInsnNode): Int = (instruction.getOpcode: @switch) match {
+    // The order of opcodes is (almost) the same as in Opcodes.java
+    case ACONST_NULL => 1
+
+    case ICONST_M1 |
+         ICONST_0 |
+         ICONST_1 |
+         ICONST_2 |
+         ICONST_3 |
+         ICONST_4 |
+         ICONST_5 => 1
+
+    case LCONST_0 |
+         LCONST_1 => 2
+
+    case FCONST_0 |
+         FCONST_1 |
+         FCONST_2 => 1
+
+    case DCONST_0 |
+         DCONST_1 => 2
+
+    case BIPUSH |
+         SIPUSH => 1
+
+    case LDC =>
+      instruction.asInstanceOf[LdcInsnNode].cst match {
+        case _: java.lang.Integer |
+             _: java.lang.Float |
+             _: String |
+             _: Type |
+             _: Handle => 1
+
+        case _: java.lang.Long |
+             _: java.lang.Double => 2
+      }
+
+    case ILOAD |
+         FLOAD |
+         ALOAD => 1
+
+    case LLOAD |
+         DLOAD => 2
+
+    case IALOAD |
+         FALOAD |
+         AALOAD |
+         BALOAD |
+         CALOAD |
+         SALOAD => 1
+
+    case LALOAD |
+         DALOAD => 2
+
+    case ISTORE |
+         LSTORE |
+         FSTORE |
+         DSTORE |
+         ASTORE => 0
+
+    case IASTORE |
+         LASTORE |
+         FASTORE |
+         DASTORE |
+         AASTORE |
+         BASTORE |
+         CASTORE |
+         SASTORE => 0
+
+    case POP |
+         POP2 => 0
+
+    case DUP |
+         DUP_X1 |
+         DUP_X2 |
+         DUP2 |
+         DUP2_X1 |
+         DUP2_X2 |
+         SWAP => throw new IllegalArgumentException("Can't compute the size of DUP/SWAP without knowing what's on stack top")
+
+    case IADD |
+         FADD => 1
+
+    case LADD |
+         DADD => 2
+
+    case ISUB |
+         FSUB => 1
+
+    case LSUB |
+         DSUB => 2
+
+    case IMUL |
+         FMUL => 1
+
+    case LMUL |
+         DMUL => 2
+
+    case IDIV |
+         FDIV => 1
+
+    case LDIV |
+         DDIV => 2
+
+    case IREM |
+         FREM => 1
+
+    case LREM |
+         DREM => 2
+
+    case INEG |
+         FNEG => 1
+
+    case LNEG |
+         DNEG => 2
+
+    case ISHL |
+         ISHR => 1
+
+    case LSHL |
+         LSHR => 2
+
+    case IUSHR => 1
+
+    case LUSHR => 2
+
+    case IAND |
+         IOR |
+         IXOR => 1
+
+    case LAND |
+         LOR |
+         LXOR => 2
+
+    case IINC => 1
+
+    case I2F |
+         L2I |
+         L2F |
+         F2I |
+         D2I |
+         D2F |
+         I2B |
+         I2C |
+         I2S => 1
+
+    case I2L |
+         I2D |
+         L2D |
+         F2L |
+         F2D |
+         D2L => 2
+
+    case LCMP |
+         FCMPL |
+         FCMPG |
+         DCMPL |
+         DCMPG => 1
+
+    case IFEQ |
+         IFNE |
+         IFLT |
+         IFGE |
+         IFGT |
+         IFLE => 0
+
+    case IF_ICMPEQ |
+         IF_ICMPNE |
+         IF_ICMPLT |
+         IF_ICMPGE |
+         IF_ICMPGT |
+         IF_ICMPLE |
+         IF_ACMPEQ |
+         IF_ACMPNE => 0
+
+    case GOTO => 0
+
+    case JSR => throw new IllegalArgumentException("Subroutines are not supported.")
+
+    case RET => 0
+
+    case TABLESWITCH |
+         LOOKUPSWITCH => 0
+
+    case IRETURN |
+         FRETURN |
+         ARETURN => 1
+
+    case LRETURN |
+         DRETURN => 2
+
+    case RETURN => 0
+
+    case GETSTATIC => Type.getType(instruction.asInstanceOf[FieldInsnNode].desc).getSize
+
+    case PUTSTATIC => 0
+
+    case GETFIELD => Type.getType(instruction.asInstanceOf[FieldInsnNode].desc).getSize
+
+    case PUTFIELD => 0
+
+    case INVOKEVIRTUAL |
+         INVOKESPECIAL |
+         INVOKESTATIC |
+         INVOKEINTERFACE =>
+      val desc = instruction.asInstanceOf[MethodInsnNode].desc
+      Type.getReturnType(desc).getSize
+
+    case INVOKEDYNAMIC =>
+      val desc = instruction.asInstanceOf[InvokeDynamicInsnNode].desc
+      Type.getReturnType(desc).getSize
+
+    case NEW => 1
+
+    case NEWARRAY |
+         ANEWARRAY |
+         ARRAYLENGTH => 1
+
+    case ATHROW => 0
+
+    case CHECKCAST |
+         INSTANCEOF => 1
+
+    case MONITORENTER |
+         MONITOREXIT => 0
+
+    case MULTIANEWARRAY => 1
+
+    case IFNULL |
+         IFNONNULL => 0
+  }
+}