Eliminate unnecessary casts

Eliminate casts that are statically known to succeed. This enables
boxes to be eliminated and simplifies the implementation of closure
allocation elimination.

4 files changed, 97 insertions, 34 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala
index e4fdcdc542..739b775e56 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/BackendUtils.scala
@@ -57,6 +57,8 @@ class BackendUtils[BT <: BTypes](val btypes: BT) {
 
   class ProdConsAnalyzer(val methodNode: MethodNode, classInternalName: InternalName) extends AsmAnalyzer(methodNode, classInternalName, new Analyzer(new InitialProducerSourceInterpreter)) with ProdConsAnalyzerImpl
 
+  class NonLubbingTypeFlowAnalyzer(val methodNode: MethodNode, classInternalName: InternalName) extends AsmAnalyzer(methodNode, classInternalName, new Analyzer(new NonLubbingTypeFlowInterpreter))
+
   /**
    * Add:
    * private static java.util.Map $deserializeLambdaCache$ = null
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/TypeFlowInterpreter.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/TypeFlowInterpreter.scala
new file mode 100644
index 0000000000..bcf9978c16
--- /dev/null
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/TypeFlowInterpreter.scala
@@ -0,0 +1,36 @@
+package scala.tools.nsc
+package backend.jvm
+package analysis
+
+import scala.tools.asm.Type
+import scala.tools.asm.tree.analysis.{BasicValue, BasicInterpreter}
+
+abstract class TypeFlowInterpreter extends BasicInterpreter {
+  override def newValue(tp: Type) = {
+    if (tp == null) super.newValue(tp)
+    else if (isRef(tp)) new BasicValue(tp)
+    else super.newValue(tp)
+  }
+
+  def isRef(tp: Type) = tp != null && (tp.getSort match {
+    case Type.OBJECT | Type.ARRAY => true
+    case _ => false
+  })
+
+  def refLub(a: BasicValue, b: BasicValue): BasicValue
+
+  override def merge(a: BasicValue, b: BasicValue): BasicValue = {
+    if (a == b) a
+    else if (isRef(a.getType) && isRef(b.getType)) refLub(a, b)
+    else BasicValue.UNINITIALIZED_VALUE
+  }
+}
+
+/**
+ * A [[TypeFlowInterpreter]] which collapses LUBs of non-equal reference types to Object.
+ * This could be made more precise by looking up ClassBTypes for the two reference types and using
+ * the `jvmWiseLUB` method.
+ */
+class NonLubbingTypeFlowInterpreter extends TypeFlowInterpreter {
+  def refLub(a: BasicValue, b: BasicValue): BasicValue = BasicValue.REFERENCE_VALUE // java/lang/Object
+}
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
index ae5a0954ad..3b03a12405 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -46,6 +46,8 @@ import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
  *   + enables downstream:
  *     - copy propagation (new locals are introduced, may be aliases of existing)
  *     - stale stores (multi-value boxes where not all values are used)
+ *     - redundant casts (`("a", "b")._1`: the generic `_1` method returns `Object`, a cast
+ *       to String is added. The cast is redundant after eliminating the tuple.)
  *     - empty local variable descriptors (local variables that were holding the box may become unused)
  *
  * copy propagation (replaces LOAD n to the LOAD m for the smallest m that is an alias of n)
@@ -60,6 +62,12 @@ import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
  *   + enables downstream:
  *     - push-pop (the new pop may be the single consumer for an instruction)
  *
+ * redundant casts: eliminates casts that are statically known to succeed (uses type propagation)
+ *   + enables UPSTREAM:
+ *     - box-unbox elimination (a removed checkcast may be a box consumer)
+ *   + enables downstream:
+ *     - push-pop for closure allocation elimination (every indyLambda is followed by a checkcast, see SI-9540)
+ *
  * push-pop (when a POP is the only consumer of a value, remove the POP and its producer)
  *   + enables UPSTREAM:
  *     - stale stores (if a LOAD is removed, a corresponding STORE may become stale)
@@ -120,6 +128,7 @@ import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._
 class LocalOpt[BT <: BTypes](val btypes: BT) {
   import LocalOptImpls._
   import btypes._
+  import coreBTypes._
   import backendUtils._
 
   val boxUnbox = new BoxUnbox(btypes)
@@ -242,8 +251,12 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
       val runStaleStores = compilerSettings.YoptCopyPropagation && (requestStaleStores || codeRemoved || boxUnboxChanged || copyPropChanged)
       val storesRemoved = runStaleStores && eliminateStaleStores(method, ownerClassName)
 
+      // REDUNDANT CASTS
+      val runRedundantCasts = compilerSettings.YoptRedundantCasts && (firstIteration || boxUnboxChanged)
+      val castRemoved = runRedundantCasts && eliminateRedundantCasts(method, ownerClassName)
+
       // PUSH-POP
-      val runPushPop = compilerSettings.YoptCopyPropagation && (firstIteration || storesRemoved)
+      val runPushPop = compilerSettings.YoptCopyPropagation && (firstIteration || storesRemoved || castRemoved)
       val pushPopRemoved = runPushPop && eliminatePushPop(method, ownerClassName)
 
       // STORE-LOAD PAIRS
@@ -262,7 +275,7 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
 
       // See doc comment in the beginning of this file (optimizations marked UPSTREAM)
       val runDCEAgain = liveHandlerRemoved || jumpsChanged
-      val runBoxUnboxAgain = boxUnboxChanged || pushPopRemoved || liveHandlerRemoved
+      val runBoxUnboxAgain = boxUnboxChanged || castRemoved || pushPopRemoved || liveHandlerRemoved
       val runStaleStoresAgain = pushPopRemoved
       val runStoreLoadAgain = jumpsChanged
       val runAgain = runDCEAgain || runBoxUnboxAgain || pushPopRemoved || runStaleStoresAgain || runStoreLoadAgain
@@ -282,7 +295,7 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
         storeLoadRemoved ||
         handlersRemoved
 
-      val codeChanged = codeRemoved || boxUnboxChanged || copyPropChanged || storesRemoved || pushPopRemoved || storeLoadRemoved || handlersRemoved || jumpsChanged
+      val codeChanged = codeRemoved || boxUnboxChanged || castRemoved || copyPropChanged || storesRemoved || pushPopRemoved || storeLoadRemoved || handlersRemoved || jumpsChanged
       (codeChanged, requireEliminateUnusedLocals)
     }
 
@@ -716,36 +729,6 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
               case _ => popAfterProd()
             }
 
-          case CHECKCAST =>
-            // Special case for `IndyLambda JFunctionN; CHECKCAST FuncionN`. This sequence is emitted
-            // for all closure instantiations, see https://issues.scala-lang.org/browse/SI-9540
-            val castType = prod.asInstanceOf[TypeInsnNode].desc
-            if (isScalaFunctionType(castType)) {
-
-              // the `FunctionN` part of an internal name (e.g. `scala/runtime/java8/JFunction1$mcDI$sp`)
-              def funPart(funType: String): String = {
-                var end = funType.indexOf('$')
-                if (end == -1) end = funType.length
-                funType.substring(funType.lastIndexOf('/') + 1, end)
-              }
-
-              // true if the cast will always succeed
-              def castOk(indy: InvokeDynamicInsnNode): Boolean = {
-                val generatedFunctionType = Type.getReturnType(indy.desc).getInternalName
-                isrJFunctionType(generatedFunctionType) && funPart(generatedFunctionType) == "J" + funPart(castType)
-              }
-
-              val castProd = producersIfSingleConsumer(prod, prodCons.frameAt(prod).stackTop)
-              if (castProd.size == 1) castProd.head match {
-                case callGraph.LambdaMetaFactoryCall(indy, _, _, _) if castOk(indy) =>
-                  toRemove += prod        // remove the cast
-                  handleClosureInst(indy) // remove the indyLambda
-                case _ => popAfterProd()
-              } else
-                popAfterProd()
-            } else
-              popAfterProd()
-
           case NEW =>
             if (isNewForSideEffectFreeConstructor(prod)) toRemove += prod
             else popAfterProd()
@@ -848,6 +831,46 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
   }
 
   /**
+   * Eliminate `CHECKCAST` instructions that are statically known to succeed. This is safe if the
+   * tested object is null: `null.asInstanceOf` always succeeds.
+   *
+   * The type of the tested object is determined using a NonLubbingTypeFlowAnalyzer. Note that this
+   * analysis collapses LUBs of non-equal references types to Object for simplicity. Example:
+   * given `B <: A <: Object`, the cast in `(if (..) new B else new A).asInstanceOf[A]` would not
+   * be eliminated.
+   *
+   * Note: we cannot replace `INSTANCEOF` tests by only looking at the types, `null.isInstanceOf`
+   * always returns false, so we'd also need nullness information.
+   */
+  def eliminateRedundantCasts(method: MethodNode, owner: InternalName): Boolean = {
+    AsmAnalyzer.sizeOKForBasicValue(method) && {
+      def isSubType(aRefDesc: String, bClass: InternalName): Boolean = aRefDesc == bClass || bClass == ObjectRef.internalName || {
+        (bTypeForDescriptorOrInternalNameFromClassfile(aRefDesc) conformsTo classBTypeFromParsedClassfile(bClass)).getOrElse(false)
+      }
+
+      lazy val typeAnalyzer = new NonLubbingTypeFlowAnalyzer(method, owner)
+
+      // cannot remove instructions while iterating, it gets the analysis out of synch (indexed by instructions)
+      val toRemove = mutable.Set.empty[TypeInsnNode]
+
+      val it = method.instructions.iterator()
+      while (it.hasNext) it.next() match {
+        case ti: TypeInsnNode if ti.getOpcode == CHECKCAST =>
+          val frame = typeAnalyzer.frameAt(ti)
+          val valueTp = frame.getValue(frame.stackTop)
+          if (valueTp.isReference && isSubType(valueTp.getType.getDescriptor, ti.desc)) {
+            toRemove += ti
+          }
+
+        case _ =>
+      }
+
+      toRemove foreach method.instructions.remove
+      toRemove.nonEmpty
+    }
+  }
+
+  /**
    * Remove `xSTORE n; xLOAD n` paris if
    *   - the local variable n is not used anywhere else in the method (1), and
    *   - there are no executable instructions and no live labels (jump targets) between the two (2)
diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index 42ed9ef935..87a9c262f4 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -229,6 +229,7 @@ trait ScalaSettings extends AbsScalaSettings
     val simplifyJumps           = Choice("simplify-jumps",            "Simplify branching instructions, eliminate unnecessary ones.")
     val compactLocals           = Choice("compact-locals",            "Eliminate empty slots in the sequence of local variables.")
     val copyPropagation         = Choice("copy-propagation",          "Eliminate redundant local variables and unused values (including closures). Enables unreachable-code.")
+    val redundantCasts          = Choice("redundant-casts",           "Eliminate redundant casts using a type propagation analysis.")
     val boxUnbox                = Choice("box-unbox",                 "Eliminate box-unbox pairs within the same method (also tuples, xRefs, value class instances). Enables unreachable-code.")
     val nullnessTracking        = Choice("nullness-tracking",         "Track nullness / non-nullness of local variables and apply optimizations.")
     val closureInvocations      = Choice("closure-invocations" ,      "Rewrite closure invocations to the implementation method.")
@@ -240,7 +241,7 @@ trait ScalaSettings extends AbsScalaSettings
     private val defaultChoices = List(unreachableCode)
     val lDefault        = Choice("l:default",   "Enable default optimizations: "+ defaultChoices.mkString(","),                                    expandsTo = defaultChoices)
 
-    private val methodChoices = List(unreachableCode, simplifyJumps, compactLocals, copyPropagation, boxUnbox, nullnessTracking, closureInvocations)
+    private val methodChoices = List(unreachableCode, simplifyJumps, compactLocals, copyPropagation, redundantCasts, boxUnbox, nullnessTracking, closureInvocations)
     val lMethod         = Choice("l:method",    "Enable intra-method optimizations: "+ methodChoices.mkString(","),                                expandsTo = methodChoices)
 
     private val projectChoices = List(lMethod, inlineProject)
@@ -261,6 +262,7 @@ trait ScalaSettings extends AbsScalaSettings
   def YoptSimplifyJumps           = Yopt.contains(YoptChoices.simplifyJumps)
   def YoptCompactLocals           = Yopt.contains(YoptChoices.compactLocals)
   def YoptCopyPropagation         = Yopt.contains(YoptChoices.copyPropagation)
+  def YoptRedundantCasts          = Yopt.contains(YoptChoices.redundantCasts)
   def YoptBoxUnbox                = Yopt.contains(YoptChoices.boxUnbox)
   def YoptNullnessTracking        = Yopt.contains(YoptChoices.nullnessTracking)
   def YoptClosureInvocations      = Yopt.contains(YoptChoices.closureInvocations)