Analyze constants to remove unnecessary branches

This commit adds analysis and optimization of constants to remove
unnecessary branches. It uses abstract interpretation to determine
what constant(s) a particular stack slot or variable might or might not
hold at a given spot and uses that knowledge to eliminate branches that
cannot be taken. Its primary goal is null check removal, but it also
works for other constants.

Several tests are modified to include the new optimization phase.

Two new tests are added. One verifies that branching still works as
expected. The other verifies that branches are removed.

9 files changed, 74 insertions, 13 deletions

diff --git a/test/files/jvm/constant-optimization/Foo_1.flags b/test/files/jvm/constant-optimization/Foo_1.flags
new file mode 100644
index 0000000000..86f52af447
--- /dev/null
+++ b/test/files/jvm/constant-optimization/Foo_1.flags
@@ -0,0 +1 @@
+-Ynooptimise -Yconst-opt
\ No newline at end of file
diff --git a/test/files/jvm/constant-optimization/Foo_1.scala b/test/files/jvm/constant-optimization/Foo_1.scala
new file mode 100644
index 0000000000..cb67ad4e90
--- /dev/null
+++ b/test/files/jvm/constant-optimization/Foo_1.scala
@@ -0,0 +1,9 @@
+class Foo_1 {
+  def foo() {
+  	// constant optimization should eliminate all branches
+    val i = 1
+    val x = if (i != 1) null else "good"
+    val y = if (x == null) "good" else x + ""
+    println(y)
+  }
+}
\ No newline at end of file
diff --git a/test/files/jvm/constant-optimization/Test.scala b/test/files/jvm/constant-optimization/Test.scala
new file mode 100644
index 0000000000..283aa6f47a
--- /dev/null
+++ b/test/files/jvm/constant-optimization/Test.scala
@@ -0,0 +1,27 @@
+
+import scala.tools.partest.BytecodeTest
+import scala.tools.asm
+import asm.tree.InsnList
+import scala.collection.JavaConverters._
+
+object Test extends BytecodeTest {
+  val comparisons = Set(asm.Opcodes.IF_ACMPEQ, asm.Opcodes.IF_ACMPNE, asm.Opcodes.IF_ICMPEQ, asm.Opcodes.IF_ICMPGE, asm.Opcodes.IF_ICMPGT, asm.Opcodes.IF_ICMPLE,
+    asm.Opcodes.IF_ICMPLT, asm.Opcodes.IF_ICMPNE, asm.Opcodes.IFEQ, asm.Opcodes.IFGE, asm.Opcodes.IFGT, asm.Opcodes.IFLE, asm.Opcodes.IFLT, 
+    asm.Opcodes.IFNE, asm.Opcodes.IFNONNULL, asm.Opcodes.IFNULL)
+
+  def show: Unit = {
+    val classNode = loadClassNode("Foo_1")
+    val methodNode = getMethod(classNode, "foo")
+    // after optimization there should be no comparisons left
+    val expected = 0
+
+    val got = countComparisons(methodNode.instructions)
+    assert(got == expected, s"expected $expected but got $got comparisons")
+  }
+
+  def countComparisons(insnList: InsnList): Int = {
+    def isComparison(node: asm.tree.AbstractInsnNode): Boolean =
+      (comparisons contains node.getOpcode)
+    insnList.iterator.asScala count isComparison
+  }
+}
\ No newline at end of file
diff --git a/test/files/neg/t6446-additional.check b/test/files/neg/t6446-additional.check
index 53dd383941..24201c07c2 100755
--- a/test/files/neg/t6446-additional.check
+++ b/test/files/neg/t6446-additional.check
@@ -25,7 +25,8 @@ superaccessors   6  add super accessors in traits and nested classes
        inliner  23  optimization: do inlining
 inlinehandlers  24  optimization: inline exception handlers
       closelim  25  optimization: eliminate uncalled closures
-           dce  26  optimization: eliminate dead code
-           jvm  27  generate JVM bytecode
-       ploogin  28  A sample phase that does so many things it's kind of hard...
-      terminal  29  The last phase in the compiler chain
+      constopt  26  optimization: optimize null and other constants
+           dce  27  optimization: eliminate dead code
+           jvm  28  generate JVM bytecode
+       ploogin  29  A sample phase that does so many things it's kind of hard...
+      terminal  30  The last phase in the compiler chain
diff --git a/test/files/neg/t6446-missing.check b/test/files/neg/t6446-missing.check
index f976bf480e..6e5bdcf07c 100755
--- a/test/files/neg/t6446-missing.check
+++ b/test/files/neg/t6446-missing.check
@@ -26,6 +26,7 @@ superaccessors   6  add super accessors in traits and nested classes
        inliner  23  optimization: do inlining
 inlinehandlers  24  optimization: inline exception handlers
       closelim  25  optimization: eliminate uncalled closures
-           dce  26  optimization: eliminate dead code
-           jvm  27  generate JVM bytecode
-      terminal  28  The last phase in the compiler chain
+      constopt  26  optimization: optimize null and other constants
+           dce  27  optimization: eliminate dead code
+           jvm  28  generate JVM bytecode
+      terminal  29  The last phase in the compiler chain
diff --git a/test/files/neg/t6446-show-phases.check b/test/files/neg/t6446-show-phases.check
index 5bbe43990c..a1bf408506 100644
--- a/test/files/neg/t6446-show-phases.check
+++ b/test/files/neg/t6446-show-phases.check
@@ -25,6 +25,7 @@ superaccessors   6  add super accessors in traits and nested classes
        inliner  23  optimization: do inlining
 inlinehandlers  24  optimization: inline exception handlers
       closelim  25  optimization: eliminate uncalled closures
-           dce  26  optimization: eliminate dead code
-           jvm  27  generate JVM bytecode
-      terminal  28  The last phase in the compiler chain
+      constopt  26  optimization: optimize null and other constants
+           dce  27  optimization: eliminate dead code
+           jvm  28  generate JVM bytecode
+      terminal  29  The last phase in the compiler chain
diff --git a/test/files/run/constant-optimization.check b/test/files/run/constant-optimization.check
new file mode 100644
index 0000000000..090e53ac40
--- /dev/null
+++ b/test/files/run/constant-optimization.check
@@ -0,0 +1,2 @@
+testBothReachable: good
+testOneReachable: good
diff --git a/test/files/run/constant-optimization.scala b/test/files/run/constant-optimization.scala
new file mode 100644
index 0000000000..86f981e13f
--- /dev/null
+++ b/test/files/run/constant-optimization.scala
@@ -0,0 +1,18 @@
+object Test extends App {
+  def testBothReachable() {
+    val i = util.Random.nextInt
+    val x = if (i % 2 == 0) null else "good"
+    val y = if (x == null) "good" else x + ""
+    println(s"testBothReachable: $y")
+  }
+
+  def testOneReachable() {
+    val i = 1
+    val x = if (i != 1) null else "good"
+    val y = if (x == null) "good" else x + ""
+    println(s"testOneReachable: $y")
+  }
+
+  testBothReachable()
+  testOneReachable()
+}
diff --git a/test/files/run/programmatic-main.check b/test/files/run/programmatic-main.check
index d472c569d2..61b947214c 100644
--- a/test/files/run/programmatic-main.check
+++ b/test/files/run/programmatic-main.check
@@ -25,7 +25,8 @@ superaccessors   6  add super accessors in traits and nested classes
        inliner  23  optimization: do inlining
 inlinehandlers  24  optimization: inline exception handlers
       closelim  25  optimization: eliminate uncalled closures
-           dce  26  optimization: eliminate dead code
-           jvm  27  generate JVM bytecode
-      terminal  28  The last phase in the compiler chain
+      constopt  26  optimization: optimize null and other constants
+           dce  27  optimization: eliminate dead code
+           jvm  28  generate JVM bytecode
+      terminal  29  The last phase in the compiler chain