Eliminate non-escaping boxes, tuples and refs

Eliminate boxes, tuples and refs that are created and used within a
single method without escaping. For details on the implementation see
the doc comment in class BoxUnbox.

This commit also cleans up the logic of inter-dependent method-level
optimizations that run until reaching a fixpoint.

2 files changed, 332 insertions, 55 deletions

diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
index bf10b88a24..7b3936f867 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -1313,88 +1313,128 @@ class InlinerTest extends ClearAfterClass {
       """.stripMargin
     val List(c, _, _) = compile(code)
 
-    def instructionSummary(m: Method): List[Any] = m.instructions.dropNonOp map {
-      case i: Invoke => i.name
-      case i => i.opcode
-    }
-
-    assertEquals(instructionSummary(getSingleMethod(c, "t1")),
+    assertEquals(getSingleMethod(c, "t1").instructions.summary,
       List(BIPUSH, "C$$$anonfun$1", IRETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t1a")),
+    assertEquals(getSingleMethod(c, "t1a").instructions.summary,
       List(LCONST_1, "C$$$anonfun$2", IRETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t2")), List(
-      ICONST_1, "boxToByte",
-      ICONST_2, "boxToInteger", ASTORE,
-      "unboxToByte",
-      ALOAD, "unboxToInt",
-      "C$$$anonfun$3",
-      "boxToInteger", "unboxToInt", IRETURN))
+    assertEquals(getSingleMethod(c, "t2").instructions.summary, List(
+      ICONST_1, ICONST_2, "C$$$anonfun$3",IRETURN))
 
     // val a = new ValKl(n); new ValKl(anonfun(a.x)).x
     // value class instantiation-extraction should be optimized by boxing elim
-    assertEquals(instructionSummary(getSingleMethod(c, "t3")), List(
+    assertEquals(getSingleMethod(c, "t3").instructions.summary, List(
       NEW, DUP, ICONST_1, "<init>", ASTORE,
       NEW, DUP, ALOAD, CHECKCAST, "x",
       "C$$$anonfun$4",
       "<init>", CHECKCAST,
       "x", IRETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t4")), List(
-      BIPUSH, "boxToInteger", "unboxToInt",
-      "C$$$anonfun$5",
-      "boxToInteger", ARETURN))
-
-    assertEquals(instructionSummary(getSingleMethod(c, "t4a")), List(
-      ICONST_1, "boxToInteger",
-      LDC, "boxToDouble", "unboxToDouble", DSTORE,
-      "unboxToInt", DLOAD, "C$$$anonfun$6",
-      "boxToLong", "unboxToLong", LRETURN))
-
-    assertEquals(instructionSummary(getSingleMethod(c, "t5")), List(
-      BIPUSH, "boxToInteger",
-      ICONST_3, "boxToByte", ASTORE,
-      "unboxToInt", ALOAD,
-      "unboxToByte",
-      "C$$$anonfun$7",
-      "boxToInteger", ARETURN))
-
-    assertEquals(instructionSummary(getSingleMethod(c, "t5a")), List(
-      BIPUSH, "boxToInteger",
-      BIPUSH, I2B, "boxToByte", ASTORE,
-      "unboxToInt", ALOAD,
-      "unboxToByte",
-      "C$$$anonfun$8",
-      "boxToInteger", "unboxToInt", IRETURN))
-
-    assertEquals(instructionSummary(getSingleMethod(c, "t6")), List(
+    assertEquals(getSingleMethod(c, "t4").instructions.summary, List(
+      BIPUSH, "C$$$anonfun$5", "boxToInteger", ARETURN))
+
+    assertEquals(getSingleMethod(c, "t4a").instructions.summary, List(
+      ICONST_1, LDC, "C$$$anonfun$6", LRETURN))
+
+    assertEquals(getSingleMethod(c, "t5").instructions.summary, List(
+      BIPUSH, ICONST_3, "C$$$anonfun$7", "boxToInteger", ARETURN))
+
+    assertEquals(getSingleMethod(c, "t5a").instructions.summary, List(
+      BIPUSH, BIPUSH, I2B, "C$$$anonfun$8", IRETURN))
+
+    assertEquals(getSingleMethod(c, "t6").instructions.summary, List(
       BIPUSH, "C$$$anonfun$9", RETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t7")), List(
-      ICONST_1, "boxToBoolean", "unboxToBoolean",
-      "C$$$anonfun$10", RETURN))
+    assertEquals(getSingleMethod(c, "t7").instructions.summary, List(
+      ICONST_1, "C$$$anonfun$10", RETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t8")), List(
-      ICONST_1, "boxToInteger",
-      LDC, "boxToDouble", "unboxToDouble", DSTORE,
-      "unboxToInt", DLOAD, "C$$$anonfun$11",
-      "boxToLong", "unboxToLong", LRETURN))
+    assertEquals(getSingleMethod(c, "t8").instructions.summary, List(
+      ICONST_1, LDC, "C$$$anonfun$11", LRETURN))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t9")), List(
+    assertEquals(getSingleMethod(c, "t9").instructions.summary, List(
       ICONST_1, "boxToInteger", "C$$$anonfun$12", RETURN))
 
     // t9a inlines Range.foreach, which is quite a bit of code, so just testing the core
     assertInvoke(getSingleMethod(c, "t9a"), "C", "C$$$anonfun$13")
-    assert(instructionSummary(getSingleMethod(c, "t9a")).contains("boxToInteger"))
+    assert(getSingleMethod(c, "t9a").instructions.summary.contains("boxToInteger"))
 
-    assertEquals(instructionSummary(getSingleMethod(c, "t10")), List(
+    assertEquals(getSingleMethod(c, "t10").instructions.summary, List(
       ICONST_1, ISTORE,
       ALOAD, ILOAD,
       "C$$$anonfun$14", RETURN))
 
     // t10a inlines Range.foreach
     assertInvoke(getSingleMethod(c, "t10a"), "C", "C$$$anonfun$15")
-    assert(!instructionSummary(getSingleMethod(c, "t10a")).contains("boxToInteger"))
+    assert(!getSingleMethod(c, "t10a").instructions.summary.contains("boxToInteger"))
+  }
+
+  @Test
+  def refElimination(): Unit = {
+    val code =
+      """class C {
+        |  def t1 = {
+        |    var i = 0
+        |    @inline def inner() = i += 1
+        |    inner()
+        |    i
+        |  }
+        |
+        |  final def m(f: Int => Unit) = f(10)
+        |  def t2 = {
+        |    var x = -1                  // IntRef not yet eliminated: closure elimination does not
+        |    m(i => if (i == 10) x = 1)  // yet inline the anonfun method, need to improve the heuristsics
+        |    x
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    assertSameCode(getSingleMethod(c, "t1").instructions.dropNonOp, List(Op(ICONST_0), Op(ICONST_1), Op(IADD), Op(IRETURN)))
+    assertEquals(getSingleMethod(c, "t2").instructions collect { case i: Invoke => i.owner +"."+ i.name }, List(
+      "scala/runtime/IntRef.create", "C.C$$$anonfun$1"))
+  }
+
+  @Test
+  def tupleElimination(): Unit = {
+    val code =
+      """class C {
+        |  @inline final def tpl[A, B](a: A, b: B) = (a, b)
+        |  @inline final def t_1[A, B](t: (A, B)) = t._1
+        |  @inline final def t_2[A, B](t: (A, B)) = t._2
+        |
+        |  def t1 = {
+        |    val t = (3, 4)  // specialized tuple
+        |    t_1(t) + t_2(t) // invocations to generic _1 / _2, box operation inserted when eliminated
+        |  }
+        |
+        |  def t2 = {
+        |    val t = tpl(1, 2) // generic Tuple2[Integer, Integer] created
+        |    t._1 + t._2       // invokes the specialized _1$mcI$sp, eliminating requires adding an unbox operation
+        |  }
+        |
+        |  @inline final def m = (1, 3)
+        |  def t3 = {
+        |    val (a, b) = m
+        |    a - b
+        |  }
+        |
+        |  def t4 = {
+        |    val ((a, b), (c, d)) = (m, m)
+        |    a + b + c + d
+        |  }
+        |
+        |  def t5 = m match {
+        |    case (1, y) => y
+        |    case (x, y) => x * y
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compile(code)
+    assertSameCode(getSingleMethod(c, "t1").instructions.dropNonOp, List(Op(ICONST_3), Op(ICONST_4), Op(IADD), Op(IRETURN)))
+    assertSameCode(getSingleMethod(c, "t2").instructions.dropNonOp, List(Op(ICONST_1), Op(ICONST_2), Op(IADD), Op(IRETURN)))
+    // tuple not yet eliminated due to null checks, casts
+    assert(getSingleMethod(c, "t3").instructions.exists(_.opcode == IFNONNULL))
+    assert(getSingleMethod(c, "t4").instructions.exists(_.opcode == CHECKCAST))
+    assert(getSingleMethod(c, "t5").instructions.exists(_.opcode == IFNULL))
   }
 }
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOptsTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOptsTest.scala
index f4524f0bb1..94c9f55728 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOptsTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOptsTest.scala
@@ -252,4 +252,241 @@ class MethodLevelOptsTest extends ClearAfterClass {
     val t = getSingleMethod(c, "t")
     assert(!t.instructions.exists(_.opcode == INVOKEDYNAMIC), t)
   }
+
+  @Test
+  def boxUnboxPrimitive(): Unit = {
+    val code =
+      """class C {
+        |  def t1 = {
+        |    val a: Any = runtime.BoxesRunTime.boxToInteger(1)
+        |    runtime.BoxesRunTime.unboxToInt(a) + 1
+        |  }
+        |
+        |  // two box and two unbox operations
+        |  def t2(b: Boolean) = {
+        |    val a = if (b) (3l: Any) else 2l
+        |    a.asInstanceOf[Long] + 1 + a.asInstanceOf[Long]
+        |  }
+        |
+        |  def t3(i: Integer): Int = i.asInstanceOf[Int]
+        |
+        |  def t4(l: Long): Any = l
+        |
+        |  def t5(i: Int): Int = {
+        |    val b = Integer.valueOf(i)
+        |    val c: Integer = i
+        |    b.asInstanceOf[Int] + c.intValue
+        |  }
+        |
+        |  def t6: Long = {
+        |    val y = new java.lang.Boolean(true)
+        |    val i: Integer = if (y) new Integer(10) else 13
+        |    val j: java.lang.Long = 3l
+        |    j + i
+        |  }
+        |
+        |  def t7: Int = {
+        |    val a: Any = 3
+        |    a.asInstanceOf[Int] + a.asInstanceOf[Int]
+        |  }
+        |
+        |  def t8 = null.asInstanceOf[Int]
+        |
+        |  def t9: Int = {
+        |    val a = Integer.valueOf(10)
+        |    val b = runtime.BoxesRunTime.unboxToInt(a)
+        |    a + b
+        |  }
+        |
+        |  @noinline def escape(a: Any) = ()
+        |
+        |  // example E4 in BoxUnbox doc comment
+        |  def t10: Int = {
+        |    val a = Integer.valueOf(10) // int 10 is stored into local
+        |    escape(a)
+        |    a                           // no unbox, 10 is read from local
+        |  }
+        |
+        |  // the boxes here cannot be eliminated. see doc comment in BoxUnbox, example E1.
+        |  def t11(b: Boolean): Int = {
+        |    val i = Integer.valueOf(10)
+        |    val j = Integer.valueOf(41)
+        |    escape(i)                          // force rewrite method M1 (see doc in BoxUnbox)
+        |    val res: Integer = if (b) i else j
+        |    res.toInt                          // cannot be re-written to a local variable read - we don't know which local to read
+        |  }
+        |
+        |  // both boxes have a single unboxing consumer, and the escape. note that the escape does
+        |  // NOT put the two boxes into the same set of rewrite operations: we can rewrite both
+        |  // boxes with their unbox individually. in both cases the box also escapes, so method
+        |  // M1 will keep the box around.
+        |  def t12(b: Boolean): Int = {
+        |    val i = Integer.valueOf(10)
+        |    val j = Integer.valueOf(32)
+        |    escape(if (b) i else j)      // force method M1. the escape here is a consumer for both boxes
+        |    if (b) i.toInt else j.toInt  // both boxes (i, j) have their own unboxing consumer
+        |  }
+        |}
+      """.stripMargin
+
+    val List(c) = compileClasses(methodOptCompiler)(code)
+
+    assertNoInvoke(getSingleMethod(c, "t1"))
+    assertNoInvoke(getSingleMethod(c, "t2"))
+    assertInvoke(getSingleMethod(c, "t3"), "scala/runtime/BoxesRunTime", "unboxToInt")
+    assertInvoke(getSingleMethod(c, "t4"), "scala/runtime/BoxesRunTime", "boxToLong")
+    assertNoInvoke(getSingleMethod(c, "t5"))
+    assertNoInvoke(getSingleMethod(c, "t6"))
+    assertNoInvoke(getSingleMethod(c, "t7"))
+    assertEquals(getSingleMethod(c, "t8").instructions.summary, List(ACONST_NULL, "unboxToInt", IRETURN))
+    assertNoInvoke(getSingleMethod(c, "t9"))
+    // t10: no invocation of unbox
+    assertEquals(getSingleMethod(c, "t10").instructions collect { case Invoke(_, owner, name, _, _) => (owner, name) }, List(
+      ("java/lang/Integer", "valueOf"),
+      ("C", "escape")))
+
+    assertEquals(getSingleMethod(c, "t11").instructions.summary, List(
+      BIPUSH, "valueOf", ASTORE /*2*/,
+      BIPUSH, "valueOf", ASTORE /*3*/,
+      ALOAD /*0*/, ALOAD /*2*/, "escape",
+      ILOAD /*1*/, IFEQ /*L1*/, ALOAD /*2*/, GOTO /*L2*/,  /*Label L1*/ -1, ALOAD /*3*/,  /*Label L2*/ -1,
+      ASTORE /*4*/, GETSTATIC /*Predef*/, ALOAD /*4*/, "Integer2int", IRETURN))
+
+    // no unbox invocations
+    assertEquals(getSingleMethod(c, "t12").instructions collect { case Invoke(_, owner, name, _, _) => (owner, name) }, List(
+      ("java/lang/Integer", "valueOf"),
+      ("java/lang/Integer", "valueOf"),
+      ("C", "escape")))
+  }
+
+  @Test
+  def refEliminiation(): Unit = {
+    val code =
+      """class C {
+        |  import runtime._
+        |  @noinline def escape(a: Any) = ()
+        |
+        |  def t1 = { // box eliminated
+        |    val r = new IntRef(0)
+        |    r.elem
+        |  }
+        |
+        |  def t2(b: Boolean) = {
+        |    val r1 = IntRef.zero()    // both eliminated
+        |    val r2 = IntRef.create(1)
+        |    val res: IntRef = if (b) r1 else r2
+        |    res.elem
+        |  }
+        |
+        |  def t3 = {
+        |    val r = LongRef.create(10l) // eliminated
+        |    r.elem += 3
+        |    r.elem
+        |  }
+        |
+        |  def t4(b: Boolean) = {
+        |    val x = BooleanRef.create(false) // eliminated
+        |    if (b) x.elem = true
+        |    if (x.elem) "a" else "b"
+        |  }
+        |
+        |  def t5 = {
+        |    val r = IntRef.create(10) // not eliminated: the box might be modified in the escape
+        |    escape(r)
+        |    r.elem
+        |  }
+        |
+        |  def t6(b: Boolean) = {
+        |    val r1 = IntRef.zero()
+        |    val r2 = IntRef.create(1)
+        |    r1.elem = 39
+        |    val res: IntRef = if (b) r1 else r2
+        |    res.elem // boxes remain: can't rewrite this read, don't know which local
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertEquals(getSingleMethod(c, "t1").instructions.summary, List(ICONST_0, IRETURN))
+    assertNoInvoke(getSingleMethod(c, "t2"))
+    assertEquals(getSingleMethod(c, "t3").instructions.summary, List(LDC, LDC, LADD, LRETURN))
+    assertNoInvoke(getSingleMethod(c, "t4"))
+    assertEquals(getSingleMethod(c, "t5").instructions collect { case Field(_, owner, name, _) => s"$owner.$name" },
+      List("scala/runtime/IntRef.elem"))
+    assertEquals(getSingleMethod(c, "t6").instructions collect { case Field(op, owner, name, _) => s"$op $owner.$name" },
+      List(s"$PUTFIELD scala/runtime/IntRef.elem", s"$GETFIELD scala/runtime/IntRef.elem"))
+  }
+
+  @Test
+  def tupleElimination(): Unit = {
+    val code =
+      """class C {
+        |  def t1(b: Boolean) = {
+        |    val t = ("hi", "fish")
+        |    if (b) t._1 else t._2
+        |  }
+        |
+        |  def t2 = {
+        |    val t = (1, 3) // specialized tuple
+        |    t._1 + t._2    // specialized accessors (_1$mcII$sp)
+        |  }
+        |
+        |  def t3 = {
+        |    // boxed before tuple creation, a non-specialized tuple is created
+        |    val t = (new Integer(3), Integer.valueOf(4))
+        |    t._1 + t._2 // invokes the generic `_1` / `_2` getters, both values unboxed by Integer2int
+        |  }
+        |
+        |  def t4: Any = {
+        |    val t = (3, 3) // specialized tuple is created, ints are not boxed
+        |    (t: Tuple2[Any, Any])._1 // when eliminating the _1 call, need to insert a boxing operation
+        |  }
+        |
+        |  // the inverse of t4 also happens: an Tuple[Integer] where _1$mcI$sp is invoked. In this
+        |  // case, an unbox operation needs to be added when eliminating the extraction. The only
+        |  // way I found to test this is with an inlined generic method, see InlinerTest.tupleElimination.
+        |  def tpl[A, B](a: A, b: B) = (a, b)
+        |  def t5: Int = tpl(1, 2)._1 // invokes _1$mcI$sp
+        |
+        |  def t6 = {
+        |    val (a, b) = (1, 2)
+        |    a - b
+        |  }
+        |
+        |  def t7 = {
+        |    // this example is more tricky to handle than it looks, see doc comment in BoxUnbox.
+        |    val ((a, b), c) = ((1, 2), 3)
+        |    a + b + c
+        |  }
+        |
+        |  def t8 = {
+        |    val ((a, b), (c, d)) = ((1, 2), (3, Integer.valueOf(10)))
+        |    a + b + c + d
+        |  }
+        |
+        |  def t9(a: Int, b: Int) = (a, b) match { // tuple is optimized away
+        |    case (x, y) if x == y => 0
+        |    case (x, y) => x + y
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertNoInvoke(getSingleMethod(c, "t1"))
+    assertEquals(getSingleMethod(c, "t2").instructions.summary, List(ICONST_1, ICONST_3, IADD, IRETURN))
+    // cannot eliminate boxes because of casts
+    assertEquals(getSingleMethod(c, "t3").instructions collect { case TypeOp(CHECKCAST, tp) => tp }, List("java/lang/Integer", "java/lang/Integer"))
+    assertEquals(getSingleMethod(c, "t4").instructions.summary, List(ICONST_3, "boxToInteger", ARETURN))
+    assertEquals(getSingleMethod(c, "t5").instructions collect { case Invoke(_, owner, name, _, _) => (owner, name) }, List(
+      ("scala/runtime/BoxesRunTime", "boxToInteger"),
+      ("scala/runtime/BoxesRunTime", "boxToInteger"),
+      ("C", "tpl"),
+      ("scala/Tuple2", "_1$mcI$sp")))
+    // cannot eliminate boxes because of null checks
+    assert(getSingleMethod(c, "t6").instructions.exists(_.opcode == IFNONNULL))
+    // cannot eliminate boxed because of casts and null checks
+    def castsNullChecks(m: String) = getSingleMethod(c, m).instructions collect { case op if op.opcode == IFNULL || op.opcode == CHECKCAST => op }
+    assertEquals(castsNullChecks("t7"),
+      List(Jump(IFNULL, Label(29)), TypeOp(CHECKCAST, "scala/Tuple2"), Jump(IFNULL, Label(29))))
+    assertEquals(castsNullChecks("t8").size, 7)
+    assertEquals(castsNullChecks("t9").size, 2)
+  }
 }