Address review feedback

Address feedback in  #4516 / 57b8da4cd8. Save allocations of
NullnessValue - there's only 4 possible instances. Also save tuple
allocations in InstructionStackEffect.

4 files changed, 109 insertions, 69 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
index 9494553ce1..7bbe1e2a49 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/AliasingFrame.scala
@@ -38,7 +38,7 @@ class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLoc
   /**
    * 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)
+  def valuesWithAliasId(id: Long): Set[Int] = immutable.BitSet.empty ++ aliasIds.indices.iterator.filter(i => aliasId(i) == id)
 
   /**
    * The set of aliased values for a given entry in the `values` array.
@@ -71,7 +71,11 @@ class AliasingFrame[V <: Value](nLocals: Int, nStack: Int) extends Frame[V](nLoc
     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
+    // the val pattern `val (p, c) = f` still allocates a tuple (https://github.com/scala-opt/scala/issues/28)
+    val prodCons = InstructionStackEffect(insn, this) // needs to be called before super.execute, see its doc
+    val consumed = prodCons._1
+    val produced = prodCons._2
+
     super.execute(insn, interpreter)
 
     (insn.getOpcode: @switch) match {
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 56c8c2e4e3..a7d6f74557 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/InstructionStackEffect.scala
@@ -8,8 +8,26 @@ 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._
+import collection.immutable
 
 object InstructionStackEffect {
+  private var cache: immutable.IntMap[(Int, Int)] = immutable.IntMap.empty
+  private def t(x: Int, y: Int): (Int, Int) = {
+    // x can go up to 255 (number of parameters of a method, dimensions in multianewarray) we cache
+    // x up to 10, which covers most cases and limits the cache. y doesn't go above 6 (see cases).
+    if (x > 10 || y > 6) (x, y)
+    else {
+      val key = (x << 8) + y // this would work for any x < 256
+      if (cache contains key) {
+        cache(key)
+      } else {
+        val r = (x, y)
+        cache += key -> r
+        r
+      }
+    }
+  }
+
   /**
    * 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
@@ -20,7 +38,7 @@ object InstructionStackEffect {
 
     (insn.getOpcode: @switch) match {
       // The order of opcodes is the same as in Frame.execute.
-      case NOP => (0, 0)
+      case NOP => t(0, 0)
 
       case ACONST_NULL |
            ICONST_M1 |
@@ -44,7 +62,7 @@ object InstructionStackEffect {
            LLOAD |
            FLOAD |
            DLOAD |
-           ALOAD => (0, 1)
+           ALOAD => t(0, 1)
 
       case IALOAD |
            LALOAD |
@@ -53,13 +71,13 @@ object InstructionStackEffect {
            AALOAD |
            BALOAD |
            CALOAD |
-           SALOAD => (2, 1)
+           SALOAD => t(2, 1)
 
       case ISTORE |
            LSTORE |
            FSTORE |
            DSTORE |
-           ASTORE => (1, 0)
+           ASTORE => t(1, 0)
 
       case IASTORE |
            LASTORE |
@@ -68,41 +86,41 @@ object InstructionStackEffect {
            AASTORE |
            BASTORE |
            CASTORE |
-           SASTORE => (3, 0)
+           SASTORE => t(3, 0)
 
-      case POP => (1, 0)
+      case POP => t(1, 0)
 
       case POP2 =>
         val isSize2 = peekStack(0).getSize == 2
-        if (isSize2) (1, 0) else (2, 0)
+        if (isSize2) t(1, 0) else t(2, 0)
 
-      case DUP => (0, 1)
+      case DUP => t(0, 1)
 
-      case DUP_X1 => (2, 3)
+      case DUP_X1 => t(2, 3)
 
       case DUP_X2 =>
         val isSize2 = peekStack(1).getSize == 2
-        if (isSize2) (2, 3) else (3, 4)
+        if (isSize2) t(2, 3) else t(3, 4)
 
       case DUP2 =>
         val isSize2 = peekStack(0).getSize == 2
-        if (isSize2) (0, 1) else (0, 2)
+        if (isSize2) t(0, 1) else t(0, 2)
 
       case DUP2_X1 =>
         val isSize2 = peekStack(0).getSize == 2
-        if (isSize2) (2, 3) else (3, 4)
+        if (isSize2) t(2, 3) else t(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)
+          if (v2isSize2) t(2, 3) else t(3, 4)
         } else {
           val v3isSize2 = peekStack(2).getSize == 2
-          if (v3isSize2) (3, 5) else (4, 6)
+          if (v3isSize2) t(3, 5) else t(4, 6)
         }
 
-      case SWAP => (2, 2)
+      case SWAP => t(2, 2)
 
       case IADD |
            LADD |
@@ -123,12 +141,12 @@ object InstructionStackEffect {
            IREM |
            LREM |
            FREM |
-           DREM => (2, 1)
+           DREM => t(2, 1)
 
       case INEG |
            LNEG |
            FNEG |
-           DNEG => (1, 1)
+           DNEG => t(1, 1)
 
       case ISHL |
            LSHL |
@@ -141,9 +159,9 @@ object InstructionStackEffect {
            IOR |
            LOR |
            IXOR |
-           LXOR => (2, 1)
+           LXOR => t(2, 1)
 
-      case IINC => (0, 0)
+      case IINC => t(0, 0)
 
       case I2L |
            I2F |
@@ -159,20 +177,20 @@ object InstructionStackEffect {
            D2F |
            I2B |
            I2C |
-           I2S => (1, 1)
+           I2S => t(1, 1)
 
       case LCMP |
            FCMPL |
            FCMPG |
            DCMPL |
-           DCMPG => (2, 1)
+           DCMPG => t(2, 1)
 
       case IFEQ |
            IFNE |
            IFLT |
            IFGE |
            IFGT |
-           IFLE => (1, 0)
+           IFLE => t(1, 0)
 
       case IF_ICMPEQ |
            IF_ICMPNE |
@@ -181,32 +199,32 @@ object InstructionStackEffect {
            IF_ICMPGT |
            IF_ICMPLE |
            IF_ACMPEQ |
-           IF_ACMPNE => (2, 0)
+           IF_ACMPNE => t(2, 0)
 
-      case GOTO => (0, 0)
+      case GOTO => t(0, 0)
 
-      case JSR => (0, 1)
+      case JSR => t(0, 1)
 
-      case RET => (0, 0)
+      case RET => t(0, 0)
 
       case TABLESWITCH |
-           LOOKUPSWITCH => (1, 0)
+           LOOKUPSWITCH => t(1, 0)
 
       case IRETURN |
            LRETURN |
            FRETURN |
            DRETURN |
-           ARETURN => (1, 0) // Frame.execute consumes one stack value
+           ARETURN => t(1, 0) // Frame.execute consumes one stack value
 
-      case RETURN => (0, 0) // Frame.execute does not change the stack
+      case RETURN => t(0, 0) // Frame.execute does not change the stack
 
-      case GETSTATIC => (0, 1)
+      case GETSTATIC => t(0, 1)
 
-      case PUTSTATIC => (1, 0)
+      case PUTSTATIC => t(1, 0)
 
-      case GETFIELD => (1, 1)
+      case GETFIELD => t(1, 1)
 
-      case PUTFIELD => (2, 0)
+      case PUTFIELD => t(2, 0)
 
       case INVOKEVIRTUAL |
            INVOKESPECIAL |
@@ -215,33 +233,33 @@ object InstructionStackEffect {
         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)
+        t(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)
+        t(cons, prod)
 
-      case NEW => (0, 1)
+      case NEW => t(0, 1)
 
       case NEWARRAY |
            ANEWARRAY |
-           ARRAYLENGTH => (1, 1)
+           ARRAYLENGTH => t(1, 1)
 
-      case ATHROW => (1, 0) // Frame.execute consumes one stack value
+      case ATHROW => t(1, 0) // Frame.execute consumes one stack value
 
-      case CHECKCAST => (0, 0)
+      case CHECKCAST => t(0, 0)
 
-      case INSTANCEOF => (1, 1)
+      case INSTANCEOF => t(1, 1)
 
       case MONITORENTER |
-           MONITOREXIT => (1, 0)
+           MONITOREXIT => t(1, 0)
 
-      case MULTIANEWARRAY => (insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1)
+      case MULTIANEWARRAY => t(insn.asInstanceOf[MultiANewArrayInsnNode].dims, 1)
 
       case IFNULL |
-           IFNONNULL => (1, 0)
+           IFNONNULL => t(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
index 18c17bc992..4c81b85d0a 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzer.scala
@@ -100,25 +100,43 @@ 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)
+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
+  /**
    * 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 getSize: Int = if (isSize2) 2 else 1
 
-  def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, longOrDouble)
+  def merge(other: NullnessValue) = NullnessValue(nullness merge other.nullness, isSize2)
 }
 
+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 NullnessValue {
-  def apply(nullness: Nullness, insn: AbstractInsnNode) = new NullnessValue(nullness, insn)
+  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)
+  }
 }
 
 final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5) {
@@ -133,12 +151,12 @@ 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, longOrDouble = 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, longOrDouble = false)
+    if (isInstanceMethod && local == 0) NullnessValue(NotNull, isSize2 = false)
     else super.newParameterValue(isInstanceMethod, local, tp)
   }
 
@@ -162,7 +180,7 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5)
 
   def unaryOperation(insn: AbstractInsnNode, value: NullnessValue): NullnessValue = (insn.getOpcode: @switch) match {
     case Opcodes.NEWARRAY |
-         Opcodes.ANEWARRAY => NullnessValue(NotNull, longOrDouble = false)
+         Opcodes.ANEWARRAY => NullnessValue(NotNull, isSize2 = false)
 
     case _ => NullnessValue(Unknown, insn)
   }
@@ -172,12 +190,12 @@ final class NullnessInterpreter extends Interpreter[NullnessValue](Opcodes.ASM5)
   }
 
   def ternaryOperation(insn: AbstractInsnNode, value1: NullnessValue, value2: NullnessValue, value3: NullnessValue): NullnessValue = {
-    NullnessValue(Unknown, longOrDouble = false)
+    NullnessValue(Unknown, isSize2 = false)
   }
 
   def naryOperation(insn: AbstractInsnNode, values: util.List[_ <: NullnessValue]): NullnessValue = (insn.getOpcode: @switch) match {
     case Opcodes.MULTIANEWARRAY =>
-      NullnessValue(NotNull, longOrDouble = false)
+      NullnessValue(NotNull, isSize2 = false)
 
     case _ =>
       // TODO: use a list of methods that are known to return non-null values
@@ -247,7 +265,7 @@ class NullnessFrame(nLocals: Int, nStack: Int) extends AliasingFrame[NullnessVal
 
     if (nullCheckedAliasId != -1) {
       for (i <- valuesWithAliasId(nullCheckedAliasId))
-        this.setValue(i, this.getValue(i).copy(nullness = NotNull))
+        this.setValue(i, NotNullValue)
     }
   }
 }
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 92574329db..3d5343e395 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala
@@ -63,9 +63,9 @@ class NullnessAnalyzerTest extends ClearAfterClass {
       val f = analyzer.frameAt(i, method)
       val frameString = {
         if (f == null) "null"
-        else f.toString.split("NullnessValue").iterator
-          .map(_.trim).filter(_.nonEmpty)
-          .map(s => "%7s".format(s.replaceAll("""\((.*),false\)""", "$1")))
+        else (0 until (f.getLocals + f.getStackSize)).iterator
+          .map(f.getValue(_).toString)
+          .map(s => "%8s".format(s))
           .zipWithIndex.map({case (s, i) => s"$i: $s"})
           .mkString(", ")
       }
@@ -82,13 +82,13 @@ class NullnessAnalyzerTest extends ClearAfterClass {
     // So in the frame for `ALOAD 0`, the stack is still empty.
 
     val res =
-      """                                                          L0: 0: NotNull
-        |                                             LINENUMBER 1 L0: 0: NotNull
-        |                                                     ALOAD 0: 0: NotNull
-        |INVOKEVIRTUAL java/lang/Object.toString ()Ljava/lang/String;: 0: NotNull, 1: NotNull
-        |                                                     ARETURN: 0: NotNull, 1: Unknown
+      """                                                          L0: 0:  NotNull
+        |                                             LINENUMBER 1 L0: 0:  NotNull
+        |                                                     ALOAD 0: 0:  NotNull
+        |INVOKEVIRTUAL java/lang/Object.toString ()Ljava/lang/String;: 0:  NotNull, 1:  NotNull
+        |                                                     ARETURN: 0:  NotNull, 1: Unknown1
         |                                                          L0: null""".stripMargin
-    assertTrue(showAllNullnessFrames(newNullnessAnalyzer(m), m) == res)
+    assertEquals(showAllNullnessFrames(newNullnessAnalyzer(m), m), res)
   }
 
   @Test