Cleanups and performance fixes in Nullness analysis

3 files changed, 89 insertions, 98 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
index f6d249db7b..f9ac12eb4d 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
@@ -33,56 +33,34 @@ import BytecodeUtils._
  */
 
 /**
- * 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]].
+ * Note that nullness of primitive values is not tracked, it will be always unknown.
  */
-sealed trait NullnessValue extends Value {
-  /**
-   * The nullness of this value.
-   */
-  def nullness: Nullness
-
-  /**
-   * 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`.
-   */
-  def isSize2: Boolean
+sealed abstract class NullnessValue(final val isSize2: Boolean) extends Value {
   /**
    * 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 (isSize2) 2 else 1
 
-  def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, isSize2)
+  def merge(other: NullnessValue) = {
+    if (this eq other) this
+    else if (this eq UnknownValue2) this // the only possible value of size two
+    else UnknownValue1
+  }
+
+  final override def equals(other: Any) = this eq other.asInstanceOf[Object]
 }
 
-object NullValue     extends NullnessValue { def nullness = Null;    def isSize2 = false; override def toString = "Null"     }
-object UnknownValue1 extends NullnessValue { def nullness = Unknown; def isSize2 = false; override def toString = "Unknown1" }
-object UnknownValue2 extends NullnessValue { def nullness = Unknown; def isSize2 = true;  override def toString = "Unknown2" }
-object NotNullValue  extends NullnessValue { def nullness = NotNull; def isSize2 = false; override def toString = "NotNull"  }
+object NullValue     extends NullnessValue(isSize2 = false) { override def toString = "Null"     }
+object UnknownValue1 extends NullnessValue(isSize2 = false) { override def toString = "Unknown1" }
+object UnknownValue2 extends NullnessValue(isSize2 = true ) { override def toString = "Unknown2" }
+object NotNullValue  extends NullnessValue(isSize2 = false) { override def toString = "NotNull"  }
 
 object NullnessValue {
-  def apply(nullness: Nullness, isSize2: Boolean): NullnessValue = {
-    if      (nullness == Null)    NullValue
-    else if (nullness == NotNull) NotNullValue
-    else if (isSize2)             UnknownValue2
-    else                          UnknownValue1
-  }
-
-  def apply(nullness: Nullness, insn: AbstractInsnNode): NullnessValue = {
-    apply(nullness, isSize2 = BytecodeUtils.instructionResultSize(insn) == 2)
-  }
+  def unknown(isSize2: Boolean) = if (isSize2) UnknownValue2 else UnknownValue1
+  def unknown(insn: AbstractInsnNode) = if (BytecodeUtils.instructionResultSize(insn) == 2) UnknownValue2 else UnknownValue1
 }
 
 final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) {
@@ -97,29 +75,25 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5)
     // (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, isSize2 = tp != null /*(2)*/ && tp.getSize == 2 )
+    else NullnessValue.unknown(isSize2 = 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, isSize2 = false)
+    if (isInstanceMethod && local == 0) NotNullValue
     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
-      }
+  def newOperation(insn: AbstractInsnNode): NullnessValue = (insn.getOpcode: @switch) match {
+    case Opcodes.ACONST_NULL => NullValue
 
-      case _ => Unknown
+    case Opcodes.LDC => insn.asInstanceOf[LdcInsnNode].cst match {
+      case _: String | _: Type => NotNullValue
+      case _ => NullnessValue.unknown(insn)
     }
 
     // for Opcodes.NEW, we use Unknown. The value will become NotNull after the constructor call.
-    NullnessValue(nullness, insn)
+    case _ => NullnessValue.unknown(insn)
   }
 
   def copyOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = value
@@ -128,26 +102,24 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5)
     case Opcodes.CHECKCAST => value
 
     case Opcodes.NEWARRAY |
-         Opcodes.ANEWARRAY => NullnessValue(NotNull, isSize2 = false)
+         Opcodes.ANEWARRAY => NotNullValue
 
-    case _ => NullnessValue(Unknown, insn)
+    case _ => NullnessValue.unknown(insn)
   }
 
   def binaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue): NullnessValue = {
-    NullnessValue(Unknown, insn)
+    NullnessValue.unknown(insn)
   }
 
-  def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = {
-    NullnessValue(Unknown, isSize2 = false)
-  }
+  def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = UnknownValue1
 
   def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match {
     case Opcodes.MULTIANEWARRAY =>
-      NullnessValue(NotNull, isSize2 = false)
+      NotNullValue
 
     case _ =>
       // TODO: use a list of methods that are known to return non-null values
-      NullnessValue(Unknown, insn)
+      NullnessValue.unknown(insn)
   }
 
   def returnOperation(insn: AbstractInsnNode, value: NullnessValue, expected: NullnessValue): Unit = ()
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 5eb4d033e6..87b51c55b4 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
@@ -16,7 +16,7 @@ import scala.collection.{concurrent, mutable}
 import scala.collection.convert.decorateAsScala._
 import scala.tools.nsc.backend.jvm.BTypes.InternalName
 import scala.tools.nsc.backend.jvm.BackendReporting._
-import scala.tools.nsc.backend.jvm.analysis.{ParameterProducer, ProdConsAnalyzer, NotNull, NullnessAnalyzer}
+import scala.tools.nsc.backend.jvm.analysis._
 import ByteCodeRepository.{Source, CompilationUnit}
 import BytecodeUtils._
 
@@ -106,7 +106,7 @@ class CallGraph[BT <: BTypes](val btypes: BT) {
     def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = analyzer match {
       case nullnessAnalyzer: NullnessAnalyzer =>
         val frame = nullnessAnalyzer.frameAt(call, methodNode)
-        frame.getStack(frame.getStackSize - 1 - numArgs).nullness == NotNull
+        frame.getStack(frame.getStackSize - 1 - numArgs) eq NotNullValue
 
       case _ => false
     }
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 94e776aadb..9cf6e366d2 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
@@ -38,9 +38,9 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     nullnessAnalyzer
   }
 
-  def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: Nullness): Unit = {
+  def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: NullnessValue): Unit = {
     for (i <- findInstr(method, query)) {
-      val r = analyzer.frameAt(i, method).getValue(index).nullness
+      val r = analyzer.frameAt(i, method).getValue(index)
       assertTrue(s"Expected: $nullness, found: $r. At instr ${textify(i)}", nullness == r)
     }
   }
@@ -77,6 +77,7 @@ class NullnessAnalyzerTest extends ClearAfterClass {
         |INVOKEVIRTUAL java/lang/Object.toString ()Ljava/lang/String;: 0:  NotNull, 1:  NotNull
         |                                                     ARETURN: 0:  NotNull, 1: Unknown1
         |                                                          L0: null""".stripMargin
+//    println(showAllNullnessFrames(newNullnessAnalyzer(m), m))
     assertEquals(showAllNullnessFrames(newNullnessAnalyzer(m), m), res)
   }
 
@@ -84,15 +85,15 @@ class NullnessAnalyzerTest extends ClearAfterClass {
   def thisNonNull(): Unit = {
     val List(m) = compileMethods(noOptCompiler)("def f = this.toString")
     val a = newNullnessAnalyzer(m)
-    testNullness(a, m, "ALOAD 0", 0, NotNull)
+    testNullness(a, m, "ALOAD 0", 0, NotNullValue)
   }
 
   @Test
   def instanceMethodCall(): Unit = {
     val List(m) = compileMethods(noOptCompiler)("def f(a: String) = a.trim")
     val a = newNullnessAnalyzer(m)
-    testNullness(a, m, "INVOKEVIRTUAL java/lang/String.trim", 1, Unknown)
-    testNullness(a, m, "ARETURN", 1, NotNull)
+    testNullness(a, m, "INVOKEVIRTUAL java/lang/String.trim", 1, UnknownValue1)
+    testNullness(a, m, "ARETURN", 1, NotNullValue)
   }
 
   @Test
@@ -110,13 +111,13 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     //                                 ARETURN: 0: NotNull, 1: NotNull, 2: Unknown
 
     for ((insn, index, nullness) <- List(
-      ("+NEW", 2, Unknown),                                    // new value at slot 2 on the stack
-      ("+DUP", 3, Unknown),
-      ("+INVOKESPECIAL java/lang/Object", 2, NotNull),         // after calling the initializer on 3, the value at 2 becomes NotNull
-      ("ASTORE 1", 1, Unknown),                                // before the ASTORE 1, nullness of the value in local 1 is Unknown
-      ("+ASTORE 1", 1, NotNull),                               // after storing the value at 2 in local 1, the local 1 is NotNull
-      ("+ALOAD 1", 2, NotNull),                                // loading the value 1 puts a NotNull value on the stack (at 2)
-      ("+INVOKEVIRTUAL java/lang/Object.toString", 2, Unknown) // nullness of value returned by `toString` is Unknown
+      ("+NEW", 2, UnknownValue1),                                    // new value at slot 2 on the stack
+      ("+DUP", 3, UnknownValue1),
+      ("+INVOKESPECIAL java/lang/Object", 2, NotNullValue),          // after calling the initializer on 3, the value at 2 becomes NotNull
+      ("ASTORE 1", 1, UnknownValue1),                                // before the ASTORE 1, nullness of the value in local 1 is Unknown
+      ("+ASTORE 1", 1, NotNullValue),                                // after storing the value at 2 in local 1, the local 1 is NotNull
+      ("+ALOAD 1", 2, NotNullValue),                                 // loading the value 1 puts a NotNull value on the stack (at 2)
+      ("+INVOKEVIRTUAL java/lang/Object.toString", 2, UnknownValue1) // nullness of value returned by `toString` is Unknown
     )) testNullness(a, m, insn, index, nullness)
   }
 
@@ -125,9 +126,9 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     val List(m) = compileMethods(noOptCompiler)("def f = { var a: Object = null; a }")
     val a = newNullnessAnalyzer(m)
     for ((insn, index, nullness) <- List(
-      ("+ACONST_NULL", 2, Null),
-      ("+ASTORE 1", 1, Null),
-      ("+ALOAD 1", 2, Null)
+      ("+ACONST_NULL", 2, NullValue),
+      ("+ASTORE 1", 1, NullValue),
+      ("+ALOAD 1", 2, NullValue)
     )) testNullness(a, m, insn, index, nullness)
   }
 
@@ -135,15 +136,33 @@ class NullnessAnalyzerTest extends ClearAfterClass {
   def stringLiteralsNotNull(): Unit = {
     val List(m) = compileMethods(noOptCompiler)("""def f = { val a = "hi"; a.trim }""")
     val a = newNullnessAnalyzer(m)
-    testNullness(a, m, "+ASTORE 1", 1, NotNull)
+    testNullness(a, m, "+ASTORE 1", 1, NotNullValue)
   }
 
   @Test
   def newArraynotNull() {
     val List(m) = compileMethods(noOptCompiler)("def f = { val a = new Array[Int](2); a(0) }")
     val a = newNullnessAnalyzer(m)
-    testNullness(a, m, "+NEWARRAY T_INT", 2, NotNull) // new array on stack
-    testNullness(a, m, "+ASTORE 1", 1, NotNull)       // local var (a)
+    testNullness(a, m, "+NEWARRAY T_INT", 2, NotNullValue) // new array on stack
+    testNullness(a, m, "+ASTORE 1", 1, NotNullValue)       // local var (a)
+  }
+
+  @Test
+  def mergeNullNotNull(): Unit = {
+    val code =
+      """def f(o: Object) = {
+        |  var a: Object = o
+        |  var c: Object = null
+        |  if ("".trim eq "-") {
+        |    c = o
+        |  }
+        |  a.toString
+        |}
+      """.stripMargin
+    val List(m) = compileMethods(noOptCompiler)(code)
+    val a = newNullnessAnalyzer(m)
+    val toSt = "+INVOKEVIRTUAL java/lang/Object.toString"
+    testNullness(a, m, toSt, 3, UnknownValue1)
   }
 
   @Test
@@ -173,22 +192,22 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     val toSt = "INVOKEVIRTUAL java/lang/Object.toString"
     val end  = s"+$toSt"
     for ((insn, index, nullness) <- List(
-      (trim, 0, NotNull), // this
-      (trim, 1, Unknown), // parameter o
-      (trim, 2, Unknown), // a
-      (trim, 3, Null),    // b
-      (trim, 4, Null),    // c
-      (trim, 5, Unknown), // d
-
-      (toSt, 2, Unknown), // a, still the same
-      (toSt, 3, Unknown), // b, was re-assinged in both branches to Unknown
-      (toSt, 4, Unknown), // c, was re-assigned in one branch to Unknown
-      (toSt, 5, Null),    // d, was assigned to null in both branches
-
-      (end, 2, NotNull),  // a, NotNull (alias of b)
-      (end, 3, NotNull),  // b, receiver of toString
-      (end, 4, Unknown),  // c, no change (not an alias of b)
-      (end, 5, Null)      // d, no change
+      (trim, 0, NotNullValue),  // this
+      (trim, 1, UnknownValue1), // parameter o
+      (trim, 2, UnknownValue1), // a
+      (trim, 3, NullValue),     // b
+      (trim, 4, NullValue),     // c
+      (trim, 5, UnknownValue1), // d
+
+      (toSt, 2, UnknownValue1), // a, still the same
+      (toSt, 3, UnknownValue1), // b, was re-assinged in both branches to Unknown
+      (toSt, 4, UnknownValue1), // c, was re-assigned in one branch to Unknown
+      (toSt, 5, NullValue),     // d, was assigned to null in both branches
+
+      (end, 2, NotNullValue),   // a, NotNull (alias of b)
+      (end, 3, NotNullValue),   // b, receiver of toString
+      (end, 4, UnknownValue1),  // c, no change (not an alias of b)
+      (end, 5, NullValue)       // d, no change
     )) testNullness(a, m, insn, index, nullness)
   }
 
@@ -210,11 +229,11 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     val trim   = "INVOKEVIRTUAL java/lang/String.trim"
 
     for ((insn, index, nullness) <- List(
-      (instof, 1, Unknown), // a after INSTANCEOF
-      (instof, 2, Unknown), // x after INSTANCEOF
-      (tost, 1, NotNull),
-      (tost, 2, NotNull),
-      (trim, 3, NotNull)  // receiver at `trim`
+      (instof, 1, UnknownValue1), // a after INSTANCEOF
+      (instof, 2, UnknownValue1), // x after INSTANCEOF
+      (tost, 1, NotNullValue),
+      (tost, 2, NotNullValue),
+      (trim, 3, NotNullValue)  // receiver at `trim`
     )) testNullness(a, m, insn, index, nullness)
   }
 }