Copy propagation, remove unused values (closures!) and local variables

Copy propagation uses an AliasingAnalyzer: it replaces a `LOAD n`
instruction by `LOAD m` where m is the smallest alias of n. This
leads to stale STORE instructions.

Stale STOREs are identified using a ProdCons analyzer and replaced by
POPs.

Values that are pushed on the stack by a side-effect free instruction
and consumed by a POP are then removed by `eliminatePushPop`. This
includes elimination of unused closure allocations and unused boxes
and  tuple allocations (*).

A final cleanup eliminates `STORE x; LOADx` pairs where the stored
value is not otherwise used.

Fixes
  - https://github.com/scala/scala-dev/issues/25
  - https://github.com/scala/scala-dev/issues/7
  - https://github.com/scala/scala-dev/issues/14
  - https://github.com/scala/scala-dev/issues/12

(*) We don't yet rewrite reads of boxes and tuples yet. For example,
`val x = (1, 2); x._1` remains a method invocation and the tuple
cannot be eliminated (https://github.com/scala/scala-dev/issues/11).

Inspired in many ways by Miguel's work!

3 files changed, 184 insertions, 27 deletions

diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
index 735bbefbbb..54724458e2 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/ClosureOptimizerTest.scala
@@ -49,7 +49,7 @@ class ClosureOptimizerTest extends ClearAfterClass {
       """.stripMargin
 
     val List(c) = compileClasses(compiler)(code)
-    val t = c.methods.asScala.toList.find(_.name == "t").get
+    val t = findAsmMethod(c, "t")
     val List(bodyCall) = findInstr(t, "INVOKESTATIC C.C$$$anonfun$1 ()Lscala/runtime/Nothing$")
     assert(bodyCall.getNext.getOpcode == ATHROW)
   }
@@ -65,7 +65,7 @@ class ClosureOptimizerTest extends ClearAfterClass {
       """.stripMargin
 
     val List(c) = compileClasses(compiler)(code)
-    val t = c.methods.asScala.toList.find(_.name == "t").get
+    val t = findAsmMethod(c, "t")
     val List(bodyCall) = findInstr(t, "INVOKESTATIC C.C$$$anonfun$1 ()Lscala/runtime/Null$")
     assert(bodyCall.getNext.getOpcode == POP)
     assert(bodyCall.getNext.getNext.getOpcode == ACONST_NULL)
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 1e01627969..1037fd5221 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala
@@ -23,8 +23,9 @@ import scala.collection.convert.decorateAsScala._
 import scala.tools.testing.ClearAfterClass
 
 object InlinerTest extends ClearAfterClass.Clearable {
-  val args = "-Ybackend:GenBCode -Yopt:l:classpath -Yopt-warnings"
+  val args = "-Yopt:l:classpath -Yopt-warnings"
   var compiler = newCompiler(extraArgs = args)
+  var inlineOnlyCompiler = newCompiler(extraArgs = "-Yopt:inline-project")
 
   // allows inspecting the caches after a compilation run
   def notPerRun: List[Clearable] = List(
@@ -34,7 +35,7 @@ object InlinerTest extends ClearAfterClass.Clearable {
     compiler.genBCode.bTypes.callGraph.callsites)
   notPerRun foreach compiler.perRunCaches.unrecordCache
 
-  def clear(): Unit = { compiler = null }
+  def clear(): Unit = { compiler = null; inlineOnlyCompiler = null }
 
   implicit class listStringLines[T](val l: List[T]) extends AnyVal {
     def stringLines = l.mkString("\n")
@@ -65,6 +66,8 @@ class InlinerTest extends ClearAfterClass {
   import compiler.genBCode.bTypes.backendUtils._
   import inlinerHeuristics._
 
+  val inlineOnlyCompiler = InlinerTest.inlineOnlyCompiler
+
   def compile(scalaCode: String, javaCode: List[(String, String)] = Nil, allowMessage: StoreReporter#Info => Boolean = _ => false): List[ClassNode] = {
     InlinerTest.notPerRun.foreach(_.clear())
     compileClasses(compiler)(scalaCode, javaCode, allowMessage)
@@ -148,15 +151,22 @@ class InlinerTest extends ClearAfterClass {
     // See also discussion around ATHROW in BCodeBodyBuilder
 
     val g = inlineTest(code)
-    val expectedInlined = List(
-      VarOp(ALOAD, 0), VarOp(ASTORE, 1), // store this
-      Field(GETSTATIC, "scala/Predef$", "MODULE$", "Lscala/Predef$;"), Invoke(INVOKEVIRTUAL, "scala/Predef$", "$qmark$qmark$qmark", "()Lscala/runtime/Nothing$;", false)) // inlined call to ???
 
-    assertSameCode(convertMethod(g).instructions.dropNonOp.take(4), expectedInlined)
+    val invokeQQQ = List(
+      Field(GETSTATIC, "scala/Predef$", "MODULE$", "Lscala/Predef$;"),
+      Invoke(INVOKEVIRTUAL, "scala/Predef$", "$qmark$qmark$qmark", "()Lscala/runtime/Nothing$;", false))
+
+    val gBeforeLocalOpt = VarOp(ALOAD, 0) :: VarOp(ASTORE, 1) :: invokeQQQ ::: List(
+      VarOp(ASTORE, 2),
+      Jump(GOTO, Label(11)),
+      Label(11),
+      VarOp(ALOAD, 2),
+      Op(ATHROW))
+
+    assertSameCode(convertMethod(g).instructions.dropNonOp, gBeforeLocalOpt)
 
     compiler.genBCode.bTypes.localOpt.methodOptimizations(g, "C")
-    assertSameCode(convertMethod(g).instructions.dropNonOp,
-      expectedInlined ++ List(VarOp(ASTORE, 2), VarOp(ALOAD, 2), Op(ATHROW)))
+    assertSameCode(convertMethod(g).instructions.dropNonOp, invokeQQQ :+ Op(ATHROW))
   }
 
   @Test
@@ -396,7 +406,8 @@ class InlinerTest extends ClearAfterClass {
         |}
       """.stripMargin
 
-    val List(c) = compile(code)
+    // use a compiler without local optimizations (cleanups)
+    val List(c) = compileClasses(inlineOnlyCompiler)(code)
     val ms @ List(f1, f2, g1, g2) = c.methods.asScala.filter(_.name.length == 2).toList
 
     // stack height at callsite of f1 is 1, so max of g1 after inlining is max of f1 + 1
@@ -959,7 +970,7 @@ class InlinerTest extends ClearAfterClass {
     val List(c) = compile(code)
     val t = getSingleMethod(c, "t").instructions
     assertNoInvoke(t)
-    assert(2 == t.collect({case Ldc(_, "hai!") => }).size)     // twice the body of f
+    assert(1 == t.collect({case Ldc(_, "hai!") => }).size)     // push-pop eliminates the first LDC("hai!")
     assert(1 == t.collect({case Jump(IFNONNULL, _) => }).size) // one single null check
   }
 
@@ -985,17 +996,17 @@ class InlinerTest extends ClearAfterClass {
     val List(c, _, _) = compile(code)
 
     val t1 = getSingleMethod(c, "t1")
-    assert(t1.instructions exists {
-      case _: InvokeDynamic => true
-      case _ => false
+    assert(t1.instructions forall { // indy is eliminated by push-pop
+      case _: InvokeDynamic => false
+      case _ => true
     })
     // the indy call is inlined into t, and the closure elimination rewrites the closure invocation to the body method
     assertInvoke(t1, "C", "C$$$anonfun$2")
 
     val t2 = getSingleMethod(c, "t2")
-    assert(t2.instructions exists {
-      case _: InvokeDynamic => true
-      case _ => false
+    assert(t2.instructions forall { // indy is eliminated by push-pop
+      case _: InvokeDynamic => false
+      case _ => true
     })
     assertInvoke(t2, "M$", "M$$$anonfun$1")
   }
diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
index 8d910629ca..734b5d9172 100644
--- a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
+++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala
@@ -8,6 +8,7 @@ import org.junit.Test
 import scala.tools.asm.Opcodes._
 import org.junit.Assert._
 
+import scala.tools.nsc.backend.jvm.AsmUtils._
 import scala.tools.testing.AssertUtil._
 
 import CodeGenTools._
@@ -36,12 +37,13 @@ class MethodLevelOpts extends ClearAfterClass {
   }
 
   @Test
-  def cannotEliminateLoadBoxedUnit(): Unit = {
+  def eliminateLoadBoxedUnit(): Unit = {
     // the compiler inserts a boxed into the try block. it's therefore non-empty (and live) and not eliminated.
     val code = "def f = { try {} catch { case _: Throwable => 0 }; 1 }"
     val m = singleMethod(methodOptCompiler)(code)
-    assertTrue(m.handlers.length == 1)
-    assertSameCode(m.instructions.take(3), List(Label(0), LineNumber(1, Label(0)), Field(GETSTATIC, "scala/runtime/BoxedUnit", "UNIT", "Lscala/runtime/BoxedUnit;")))
+    assertTrue(m.handlers.length == 0)
+    assertSameCode(m.instructions.dropNonOp,
+      List(Op(ICONST_1), Op(IRETURN)))
   }
 
   @Test
@@ -75,18 +77,162 @@ class MethodLevelOpts extends ClearAfterClass {
         |    case _: Throwable =>
         |    return 2
         |  } finally {
-        |    return 2
+        |    return 3
         |    // dead
         |    val x = try 10 catch { case _: Throwable => 11 }
         |    println(x)
         |  }
       """.stripMargin
     val m = singleMethod(methodOptCompiler)(code)
-    assertTrue(m.handlers.length == 2)
-    assertSameCode(m.instructions.dropNonOp, // drop line numbers and labels that are only used by line numbers
+    assertTrue(m.handlers.isEmpty)
+    assertSameCode(m.instructions.dropNonOp, List(Op(ICONST_3), Op(IRETURN)))
+  }
 
-      // one single label left :-)
-      List(Op(ICONST_1), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), Op(POP), Op(ICONST_2), VarOp(ISTORE, 2), Jump(GOTO, Label(20)), VarOp(ASTORE, 3), Op(ICONST_2), Op(IRETURN), Label(20), Op(ICONST_2), Op(IRETURN))
-    )
+  @Test
+  def nullStoreLoadElim(): Unit = {
+    // point of this test: we have two cleanups
+    //   - remove `ACONST_NULL; ASTORE x` if x is otherwise not live
+    //   - remove `ASTORE x; ALOAD x` if x is otherwise not live
+    // in the example below, we have `ACONST_NULL; ASTORE x; ALOAD x`. in this case the store-load
+    // should be removed (even though it looks like a null-store at first).
+    val code =
+      """class C {
+        |  def t = {
+        |    val x = null
+        |    x.toString
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertSameCode(getSingleMethod(c, "t").instructions.dropNonOp,
+      List(Op(ACONST_NULL), Invoke(INVOKEVIRTUAL, "java/lang/Object", "toString", "()Ljava/lang/String;", false), Op(ARETURN)))
+  }
+
+  @Test
+  def deadStoreReferenceElim(): Unit = {
+    val code =
+      """class C {
+        |  def t = {
+        |    var a = "a"   // assign to non-initialized, directly removed by dead store
+        |    a = "b"       // assign to initialized, replaced by null-store, which is then removed: the var is not live, the uses are null-store or store-load
+        |    a = "c"
+        |    a             // store-load pair will be eliminated
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertSameCode(
+      getSingleMethod(c, "t").instructions.dropNonOp,
+      List(Ldc(LDC, "c"), Op(ARETURN)))
+  }
+
+  @Test
+  def deadStoreReferenceKeepNull(): Unit = {
+    val code =
+      """class C {
+        |  def t = {
+        |    var a = "el"  // this store is live, used in the println.
+        |    println(a)
+        |    a = "met"     // since it's an ASTORE to a live variable, cannot elim the store (SI-5313), but store null instead.
+        |                  // so we get `LDC met; POP; ACONST_NULL; ASTORE 1`. the `LDC met; POP` is eliminated by push-pop.
+        |    a = "zit"     // this store is live, so we get `LDC zit; ASOTRE 1; ALOAD 1; ARETURN`.
+        |                  // we cannot eliminated the store-load sequence, because the local is live (again SI-5313).
+        |    a
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+
+    assertEquals(
+      getSingleMethod(c, "t").instructions.dropNonOp,
+      List(
+        Ldc(LDC, "el"), VarOp(ASTORE, 1),
+        Field(GETSTATIC, "scala/Predef$", "MODULE$", "Lscala/Predef$;"), VarOp(ALOAD, 1), Invoke(INVOKEVIRTUAL, "scala/Predef$", "println", "(Ljava/lang/Object;)V", false),
+        Op(ACONST_NULL), VarOp(ASTORE, 1),
+        Ldc(LDC, "zit"), VarOp(ASTORE, 1), VarOp(ALOAD, 1), Op(ARETURN)))
+  }
+
+  @Test
+  def elimUnusedTupleObjectStringBox(): Unit = {
+    val code =
+      """class C {
+        |  def t(x: Int, y: Int): Int = {
+        |    val a = (x, y)                            // Tuple2$mcII$sp
+        |    val b = (a, y)                            // Tuple2
+        |    val c = (new Object, "krik", new String)  // unused java/lang/Object, java/lang/String allocation and string constant is also eliminated
+        |    val d = new java.lang.Integer(x)
+        |    val e = new String(new Array[Char](23))
+        |    val f = new scala.runtime.IntRef(11)
+        |    x + y
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertEquals(getSingleMethod(c, "t").instructions.dropNonOp,
+      List(VarOp(ILOAD, 1), VarOp(ILOAD, 2), Op(IADD), Op(IRETURN)))
+  }
+
+  @Test
+  def noElimImpureConstructor(): Unit = {
+    val code =
+      """class C {
+        |  def t(x: Int, y: Int): Int = {
+        |    val a = new java.lang.Integer("nono")
+        |    x + y
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertEquals(getSingleMethod(c, "t").instructions.dropNonOp,
+      List(TypeOp(NEW, "java/lang/Integer"), Ldc(LDC, "nono"), Invoke(INVOKESPECIAL, "java/lang/Integer", "<init>", "(Ljava/lang/String;)V", false),
+        VarOp(ILOAD, 1), VarOp(ILOAD, 2), Op(IADD), Op(IRETURN)))
+  }
+
+  @Test
+  def elimUnusedBoxUnbox(): Unit = {
+    val code =
+      """class C {
+        |  def t(a: Long): Int = {
+        |    val t = 3 + a
+        |    val u = a + t
+        |    val v: Any = u // scala/runtime/BoxesRunTime.boxToLong
+        |
+        |    val w = (v, a) // a Tuple2 (not specialized because first value is Any)
+        |                   // so calls scala/runtime/BoxesRunTime.boxToLong on the second value
+        |
+        |    val x = v.asInstanceOf[Long] // scala/runtime/BoxesRunTime.unboxToLong
+        |
+        |    val z = (java.lang.Long.valueOf(a), t)  // java box call on the left, scala/runtime/BoxesRunTime.boxToLong on the right
+        |
+        |    0
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertEquals(getSingleMethod(c, "t").instructions.dropNonOp,
+      List(Op(ICONST_0), Op(IRETURN)))
+  }
+
+  @Test
+  def elimUnusedClosure(): Unit = {
+    val code =
+      """class C {
+        |  def t(x: Int, y: Int): Int = {
+        |    val f = (a: Int) => a + x + y
+        |    val g = (b: Int) => b - x
+        |    val h = (s: String) => println(s)
+        |    f(30)
+        |  }
+        |}
+      """.stripMargin
+    val List(c) = compileClasses(methodOptCompiler)(code)
+    assertEquals(
+      getSingleMethod(c, "t").instructions.dropNonOp,
+      List(
+        IntOp(BIPUSH, 30), VarOp(ISTORE, 3),  // no constant propagation, so we keep the store (and load below) of a const
+        VarOp(ILOAD, 1),
+        VarOp(ILOAD, 2),
+        VarOp(ILOAD, 3),
+        Invoke(INVOKESTATIC, "C", "C$$$anonfun$1", "(III)I", false), Op(IRETURN)))
   }
 }