Cleanup of constant optimization

This commit cleans up constant optimization from the review of
https://github.com/scala/scala/pull/2214 .

* drops are done using the instruction's consumed count rather than a
  numeric literal
* drops are moved into one common method in the main instruction
  interpreter
* One instance of x.length > y.length is replaced with
  x.lengthCompare(y.length) > 0
* NaN is dealt with by treating it as an UNKNOWN
* A test is added to make sure NaN semantics aren't broken.
* The constant-optmization test is improved with tests for switch
  statements

7 files changed, 245 insertions, 144 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala b/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala
index b3da012e1a..b80acc2324 100644
--- a/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala
+++ b/src/compiler/scala/tools/nsc/backend/opt/ConstantOptimization.scala
@@ -84,17 +84,17 @@ abstract class ConstantOptimization extends SubComponent {
       }
 
       /**
-       * True if this constant has the same representation (and therefore would compare true under eq) as another constant
+       * True if this constant would compare to other as true under primitive eq
        */
-      override def equals(other: Any) = (other match {
+      override def equals(other: Any) = other match {
         case oc @ Const(o) => (this eq oc) || (if (this.isIntAssignable && oc.isIntAssignable) this.toInt == oc.toInt else c.value == o.value)
         case _ => false
-      })
+      }
 
       /**
-       * Hash code based on representation of the constant, consistent with equals
+       * Hash code consistent with equals
        */
-      override def hashCode = if (c.isIntRange) c.intValue else c.hashCode
+      override def hashCode = if (this.isIntAssignable) this.toInt else c.hashCode
 
     }
     /**
@@ -296,142 +296,123 @@ abstract class ConstantOptimization extends SubComponent {
     /**
      * interpret a single instruction to find its impact on the abstract state
      */
-    private def interpretInst(in: State, inst: Instruction): State = inst match {
-      case THIS(_) =>
-        in load THIS_LOCAL
-
-      case CONSTANT(k) =>
-        in push SinglePossible(Const(k))
-
-      case LOAD_ARRAY_ITEM(_) =>
-        in drop 2 push UNKNOWN
-
-      case LOAD_LOCAL(local) =>
-        // TODO if a local is known to hold a constant then we can replace this instruction with a push of that constant
-        in load local
-
-      case LOAD_FIELD(_, isStatic) =>
-        val drops = if (isStatic) 0 else 1
-        in drop drops push UNKNOWN
-
-      case LOAD_MODULE(_) =>
-        in push NOT_NULL
-
-      case STORE_ARRAY_ITEM(_) =>
-        in drop 3
-
-      case STORE_LOCAL(local) =>
-        in store local
-
-      case STORE_THIS(_) =>
-        // if a local is already known to have a constant and we're replacing with the same constant then we can
-        // replace this with a drop
-        in store THIS_LOCAL
-
-      case STORE_FIELD(_, isStatic) =>
-        val drops = if (isStatic) 1 else 2
-        in drop drops
-
-      case CALL_PRIMITIVE(_) =>
-        in drop inst.consumed push UNKNOWN
-
-      case CALL_METHOD(_, _) =>
-        // TODO we could special case implementations of equals that are known, e.g. String#equals
-        // We could turn Possible(string constants).equals(Possible(string constants) into an eq check
-        // We could turn nonConstantString.equals(constantString) into constantString.equals(nonConstantString)
-        //  and eliminate the null check that likely precedes this call
-        val initial = in drop inst.consumed
-        (0 until inst.produced).foldLeft(initial) { case (know, _) => know push UNKNOWN }
-
-      case BOX(_) =>
-        val value = in peek 0
-        // we simulate boxing by, um, boxing the possible/impossible contents
-        // so if we have Possible(1,2) originally then we'll end up with
-        // a Possible(Boxed(1), Boxed(2))
-        // Similarly, if we know the input is not a 0 then we'll know the
-        // output is not a Boxed(0)
-        val newValue = value match {
-          case Possible(values) => Possible(values map Boxed)
-          case Impossible(values) => Impossible(values map Boxed)
-        }
-        in drop 1 push newValue
-
-      case UNBOX(_) =>
-        val value = in peek 0
-        val newValue = value match {
-          // if we have a Possible, then all the possibilities
-          // should themselves be Boxes. In that
-          // case we can merge them to figure out what the UNBOX will produce
-          case Possible(inners) =>
-            assert(inners.nonEmpty, "Empty possible set indicating an uninitialized location")
-            val sanitized: Set[Contents] = (inners map {
-              case Boxed(content) => SinglePossible(content)
-              case _ => UNKNOWN
-            })
-            sanitized reduce (_ merge _)
-          // if we have an impossible then the thing that's impossible
-          // should be a box. We'll unbox that to see what we get
-          case unknown@Impossible(inners) =>
-            if (inners.isEmpty) {
-              unknown
-            } else {
+    private def interpretInst(in: State, inst: Instruction): State = {
+      // pop the consumed number of values off the `in` state's stack, producing a new state
+      def dropConsumed: State = in drop inst.consumed
+      
+      inst match {
+        case THIS(_) =>
+          in load THIS_LOCAL
+  
+        case CONSTANT(k) =>
+          // treat NaN as UNKNOWN because NaN must never equal NaN
+          val const = if (k.isNaN) UNKNOWN
+          else SinglePossible(Const(k))
+          in push const
+  
+        case LOAD_ARRAY_ITEM(_) | LOAD_FIELD(_, _) | CALL_PRIMITIVE(_) =>
+          dropConsumed push UNKNOWN
+
+        case LOAD_LOCAL(local) =>
+          // TODO if a local is known to hold a constant then we can replace this instruction with a push of that constant
+          in load local
+  
+        case STORE_LOCAL(local) =>
+          in store local
+  
+        case STORE_THIS(_) =>
+          // if a local is already known to have a constant and we're replacing with the same constant then we can
+          // replace this with a drop
+          in store THIS_LOCAL
+    
+        case CALL_METHOD(_, _) =>
+          // TODO we could special case implementations of equals that are known, e.g. String#equals
+          // We could turn Possible(string constants).equals(Possible(string constants) into an eq check
+          // We could turn nonConstantString.equals(constantString) into constantString.equals(nonConstantString)
+          //  and eliminate the null check that likely precedes this call
+          val initial = dropConsumed
+          (0 until inst.produced).foldLeft(initial) { case (know, _) => know push UNKNOWN }
+  
+        case BOX(_) =>
+          val value = in peek 0
+          // we simulate boxing by, um, boxing the possible/impossible contents
+          // so if we have Possible(1,2) originally then we'll end up with
+          // a Possible(Boxed(1), Boxed(2))
+          // Similarly, if we know the input is not a 0 then we'll know the
+          // output is not a Boxed(0)
+          val newValue = value match {
+            case Possible(values) => Possible(values map Boxed)
+            case Impossible(values) => Impossible(values map Boxed)
+          }
+          dropConsumed push newValue
+  
+        case UNBOX(_) =>
+          val value = in peek 0
+          val newValue = value match {
+            // if we have a Possible, then all the possibilities
+            // should themselves be Boxes. In that
+            // case we can merge them to figure out what the UNBOX will produce
+            case Possible(inners) =>
+              assert(inners.nonEmpty, "Empty possible set indicating an uninitialized location")
               val sanitized: Set[Contents] = (inners map {
-                case Boxed(content) => SingleImpossible(content)
+                case Boxed(content) => SinglePossible(content)
                 case _ => UNKNOWN
               })
               sanitized reduce (_ merge _)
-            }
-        }
-        in drop 1 push newValue
-
-      case NEW(_) =>
-        in push NOT_NULL
-
-      case CREATE_ARRAY(_, dims) =>
-        in drop dims push NOT_NULL
-
-      case IS_INSTANCE(_) =>
-        // TODO IS_INSTANCE is going to be followed by a C(Z)JUMP
-        // and if IS_INSTANCE/C(Z)JUMP the branch for "true" can
-        // know that whatever was checked was not a null
-        // see the TODO on CJUMP for more information about propagating null
-        // information
-        // TODO if the top of stack is guaranteed null then we can eliminate this IS_INSTANCE check and 
-        // replace with a constant false, but how often is a knowable null checked for instanceof?
-        // TODO we could track type information and statically know to eliminate IS_INSTANCE
-        // but that's probably not a huge win
-        in drop 1 push UNKNOWN // it's actually a Possible(true, false) but since the following instruction
-      // will be a conditional jump comparing to true or false there
-      // nothing to be gained by being more precise
-
-      case CHECK_CAST(_) =>
-        // TODO we could track type information and statically know to eliminate CHECK_CAST
-        // but that's probably not a huge win
-        in
-
-      case DROP(_) =>
-        in drop 1
-
-      case DUP(_) =>
-        val value = in peek 0
-        in push value
-
-      case MONITOR_ENTER() =>
-        in drop 1
-
-      case MONITOR_EXIT() =>
-        in drop 1
-
-      case SCOPE_ENTER(_) | SCOPE_EXIT(_) =>
-        in
-
-      case LOAD_EXCEPTION(_) =>
-        in push NOT_NULL
-
-      case JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | RETURN(_) | THROW(_) | SWITCH(_, _) =>
-        dumpClassesAndAbort("Unexpected block ending instruction: " + inst)
-    }
+            // if we have an impossible then the thing that's impossible
+            // should be a box. We'll unbox that to see what we get
+            case unknown@Impossible(inners) =>
+              if (inners.isEmpty) {
+                unknown
+              } else {
+                val sanitized: Set[Contents] = (inners map {
+                  case Boxed(content) => SingleImpossible(content)
+                  case _ => UNKNOWN
+                })
+                sanitized reduce (_ merge _)
+              }
+          }
+          dropConsumed push newValue
+  
+        case LOAD_MODULE(_) | NEW(_) | LOAD_EXCEPTION(_) =>
+          in push NOT_NULL
 
+        case CREATE_ARRAY(_, _) =>
+          dropConsumed push NOT_NULL
+    
+        case IS_INSTANCE(_) =>
+          // TODO IS_INSTANCE is going to be followed by a C(Z)JUMP
+          // and if IS_INSTANCE/C(Z)JUMP the branch for "true" can
+          // know that whatever was checked was not a null
+          // see the TODO on CJUMP for more information about propagating null
+          // information
+          // TODO if the top of stack is guaranteed null then we can eliminate this IS_INSTANCE check and 
+          // replace with a constant false, but how often is a knowable null checked for instanceof?
+          // TODO we could track type information and statically know to eliminate IS_INSTANCE
+          // which might be a nice win under specialization
+          dropConsumed push UNKNOWN // it's actually a Possible(true, false) but since the following instruction
+        // will be a conditional jump comparing to true or false there
+        // nothing to be gained by being more precise
+  
+        case CHECK_CAST(_) =>
+          // TODO we could track type information and statically know to eliminate CHECK_CAST
+          // but that's probably not a huge win
+          in
+  
+        case DUP(_) =>
+          val value = in peek 0
+          in push value
+  
+        case DROP(_) | MONITOR_ENTER() | MONITOR_EXIT() | STORE_ARRAY_ITEM(_) | STORE_FIELD(_, _) =>
+          dropConsumed
+
+        case SCOPE_ENTER(_) | SCOPE_EXIT(_) =>
+          in
+  
+        case JUMP(_) | CJUMP(_, _, _, _) | CZJUMP(_, _, _, _) | RETURN(_) | THROW(_) | SWITCH(_, _) =>
+          dumpClassesAndAbort("Unexpected block ending instruction: " + inst)
+      }
+    }
     /**
      * interpret the last instruction of a block which will be jump, a conditional branch, a throw, or a return.
      * It will result in a map from target blocks to the input state computed for that block. It
@@ -445,7 +426,7 @@ abstract class ConstantOptimization extends SubComponent {
       /**
        * common code for interpreting CJUMP and CZJUMP
        */
-      def interpretConditional(kind: TypeKind, in: State, toDrop: Int, val1: Contents, val2: Contents, success: BasicBlock, failure: BasicBlock, cond: TestOp): (Map[BasicBlock, State], List[Instruction]) = {
+      def interpretConditional(kind: TypeKind, val1: Contents, val2: Contents, success: BasicBlock, failure: BasicBlock, cond: TestOp): (Map[BasicBlock, State], List[Instruction]) = {
         // TODO use reaching analysis to update the state in the two branches
         // e.g. if the comparison was checking null equality on local x
         // then the in the success branch we know x is null and
@@ -476,7 +457,7 @@ abstract class ConstantOptimization extends SubComponent {
           case LE | GE => !guaranteedEqual // if the two are guaranteed to be equal then they must be LE/GE
         }
 
-        val out = in drop toDrop
+        val out = in drop inst.consumed
 
         var result = Map[BasicBlock, State]()
         if (succPossible) {
@@ -487,8 +468,10 @@ abstract class ConstantOptimization extends SubComponent {
           result += ((failure, out))
         }
 
-        if (result.size == 1) (result, List.fill(toDrop)(DROP(kind)) :+ JUMP(result.keySet.head))
-        else (result, inst :: Nil)
+        val replacements = if (result.size == 1) List.fill(inst.consumed)(DROP(kind)) :+ JUMP(result.keySet.head)
+        else inst :: Nil
+        
+        (result, replacements)
       }
 
       inst match {
@@ -498,18 +481,18 @@ abstract class ConstantOptimization extends SubComponent {
         case CJUMP(success, failure, cond, kind) =>
           val in1 = in peek 0
           val in2 = in peek 1
-          interpretConditional(kind, in, 2, in1, in2, success, failure, cond)
+          interpretConditional(kind, in1, in2, success, failure, cond)
 
         case CZJUMP(success, failure, cond, kind) =>
           val in1 = in peek 0
           val in2 = getZeroOf(kind)
-          interpretConditional(kind, in, 1, in1, in2, success, failure, cond)
+          interpretConditional(kind, in1, in2, success, failure, cond)
 
         case SWITCH(tags, labels) =>
           val in1 = in peek 0
           val newStuff = tags zip labels filter { case (tagSet, _) => canSwitch(in1, tagSet) }
           val (reachableTags, reachableNormalLabels) = (tags zip labels filter { case (tagSet, _) => canSwitch(in1, tagSet) }).unzip
-          val reachableLabels = if (labels.size > tags.size) {
+          val reachableLabels = if (labels.lengthCompare(tags.length) > 0) {
             // if we've got an extra label then it's the default
             val defaultLabel = labels.last
             // see if the default is reachable by seeing if the input might be out of the set
@@ -528,7 +511,7 @@ abstract class ConstantOptimization extends SubComponent {
           // are the same we need to merge State rather than clobber
 
           // alternative, maybe we should simplify the SWITCH to not have same target labels
-          val newState = in drop 1
+          val newState = in drop inst.consumed
           val result = Map(reachableLabels map { label => (label, newState) }: _*)
           if (reachableLabels.size == 1) (result, DROP(INT) :: JUMP(reachableLabels.head) :: Nil)
           else (result, inst :: Nil)
diff --git a/test/files/run/blame_eye_triple_eee.check b/test/files/run/blame_eye_triple_eee.check
new file mode 100644
index 0000000000..5e46d91a8f
--- /dev/null
+++ b/test/files/run/blame_eye_triple_eee.check
@@ -0,0 +1,9 @@
+if (NaN == NaN) is good
+if (x == x) is good
+if (x == NaN) is good
+if (NaN != NaN) is good
+if (x != x) is good
+if (NaN != x) is good
+x matching was good
+NaN matching was good
+loop with NaN was goood
diff --git a/test/files/run/blame_eye_triple_eee.flags b/test/files/run/blame_eye_triple_eee.flags
new file mode 100644
index 0000000000..c9b68d70dc
--- /dev/null
+++ b/test/files/run/blame_eye_triple_eee.flags
@@ -0,0 +1 @@
+-optimise
diff --git a/test/files/run/blame_eye_triple_eee.scala b/test/files/run/blame_eye_triple_eee.scala
new file mode 100644
index 0000000000..1640aead40
--- /dev/null
+++ b/test/files/run/blame_eye_triple_eee.scala
@@ -0,0 +1,61 @@
+object Test extends App {
+  import Double.NaN
+
+  // NaN must not equal NaN no matter what optimizations are applied
+  // All the following will seem redundant, but to an optimizer
+  // they can appear different
+
+  val x = NaN
+
+  if (NaN == NaN)
+    println("if (NaN == NaN) is broken")
+  else
+    println("if (NaN == NaN) is good")
+
+  if (x == x)
+    println("if (x == x) is broken")
+  else
+    println("if (x == x) is good")
+
+  if (x == NaN)
+    println("if (x == NaN) is broken")
+  else
+    println("if (x == NaN) is good")
+
+  if (NaN != NaN)
+    println("if (NaN != NaN) is good")
+  else
+    println("if (NaN != NaN) broken")
+
+  if (x != x)
+    println("if (x != x) is good")
+  else
+    println("if (x != x) broken")
+
+  if (NaN != x)
+    println("if (NaN != x) is good")
+  else
+    println("if (NaN != x) is broken")
+
+  x match {
+    case 0.0d => println("x matched 0!")
+    case NaN => println("x matched NaN!")
+    case _ => println("x matching was good")
+  }
+
+  NaN match {
+    case 0.0d => println("NaN matched 0!")
+    case NaN => println("NaN matched NaN!")
+    case _ => println("NaN matching was good")
+  }
+
+  var z = 0.0d
+  var i = 0
+  while (i < 10) {
+    if (i % 2 == 0) z = NaN
+    else z = NaN
+    i += 1
+  }
+  if (z.isNaN && i == 10) println("loop with NaN was goood")
+  else println("loop with NaN was broken")
+}
diff --git a/test/files/run/constant-optimization.check b/test/files/run/constant-optimization.check
index 090e53ac40..957ffc5a87 100644
--- a/test/files/run/constant-optimization.check
+++ b/test/files/run/constant-optimization.check
@@ -1,2 +1,5 @@
 testBothReachable: good
 testOneReachable: good
+testAllReachable: good
+testOneUnreachable: good
+testDefaultUnreachable: good
diff --git a/test/files/run/constant-optimization.flags b/test/files/run/constant-optimization.flags
new file mode 100644
index 0000000000..c9b68d70dc
--- /dev/null
+++ b/test/files/run/constant-optimization.flags
@@ -0,0 +1 @@
+-optimise
diff --git a/test/files/run/constant-optimization.scala b/test/files/run/constant-optimization.scala
index 86f981e13f..5d13272f3b 100644
--- a/test/files/run/constant-optimization.scala
+++ b/test/files/run/constant-optimization.scala
@@ -13,6 +13,49 @@ object Test extends App {
     println(s"testOneReachable: $y")
   }
 
+  def testAllReachable() {
+    val i = util.Random.nextInt
+    val y = (i % 2) match {
+      case 0 => "good"
+      case 1 => "good"
+      case _ => "good"
+    }
+    println(s"testAllReachable: $y")
+  }
+
+  def testOneUnreachable() {
+    val i = util.Random.nextInt
+    val x = if (i % 2 == 0) {
+      1
+    } else {
+      2
+    }
+    val y = x match {
+      case 0 => "good"
+      case 1 => "good"
+      case _ => "good"
+    }
+    println(s"testOneUnreachable: $y")
+  }
+
+  def testDefaultUnreachable() {
+    val i = util.Random.nextInt
+    val x = if (i % 2 == 0) {
+      1
+    } else {
+      2
+    }
+    val y = x match {
+      case 1 => "good"
+      case 2 => "good"
+      case _ => "good"
+    }
+    println(s"testDefaultUnreachable: $y")
+  }
+
   testBothReachable()
   testOneReachable()
+  testAllReachable()
+  testOneUnreachable()
+  testDefaultUnreachable()
 }