Avoid running data flow analyses on very large methods

Data flow analyses take a long time to converge (many seconds) when
analyzing large methods. This commit prevents running analyses that
would take too long. This means for example that callsites in very
large methods are not added to the call graph and will therefore not
be inlined.

5 files changed, 100 insertions, 62 deletions

diff --git a/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala b/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala
index 3734c63e93..bb5c6e3820 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/analysis/Analyzers.scala
@@ -25,5 +25,24 @@ class Analyzers[BT <: BTypes](val btypes: BT) {
     def frameAt(instruction: AbstractInsnNode): Frame[V] = analyzer.frameAt(instruction, methodNode)
   }
 
+  /**
+   * See the doc comment on package object `analysis` for a discussion on performance.
+   */
+  object AsmAnalyzer {
+    // jvm limit is 65535 for both number of instructions and number of locals
+
+    private def size(method: MethodNode) = method.instructions.size.toLong * method.maxLocals * method.maxLocals
+
+    // with the limits below, analysis should not take more than one second
+
+    private val nullnessSizeLimit    = 5000l * 600l  * 600l    // 5000 insns, 600 locals
+    private val basicValueSizeLimit  = 9000l * 1000l * 1000l
+    private val sourceValueSizeLimit = 8000l * 950l  * 950l
+
+    def sizeOKForNullness(method: MethodNode): Boolean = size(method) < nullnessSizeLimit
+    def sizeOKForBasicValue(method: MethodNode): Boolean = size(method) < basicValueSizeLimit
+    def sizeOKForSourceValue(method: MethodNode): Boolean = size(method) < sourceValueSizeLimit
+  }
+
   class ProdConsAnalyzer(val methodNode: MethodNode, classInternalName: InternalName) extends AsmAnalyzer(methodNode, classInternalName, new Analyzer(new InitialProducerSourceInterpreter)) with ProdConsAnalyzerImpl
 }
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
index aea4058752..b9788c3f56 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/CallGraph.scala
@@ -30,6 +30,11 @@ class CallGraph[BT <: BTypes](val btypes: BT) {
    * finding callsites efficiently. For example, an inlining heuristic might want to know all
    * callsites withing a callee method.
    *
+   * Note that the call graph is not guaranteed to be complete: callsites may be missing. In
+   * particular, if a method is very large, all of its callsites might not be in the hash map.
+   * The reason is that adding a method to the call graph requires running an ASM analyzer, which
+   * can be too slow.
+   *
    * Note that call graph entries (Callsite instances) keep a reference to the invocation
    * MethodInsnNode, which keeps all AbstractInsnNodes of the method reachable. Adding classes
    * from the classpath to the call graph (in addition to classes being compiled) may prevent
@@ -97,75 +102,81 @@ class CallGraph[BT <: BTypes](val btypes: BT) {
     // It is also used to get the stack height at the call site.
 
     val analyzer = {
-      if (compilerSettings.YoptNullnessTracking) new AsmAnalyzer(methodNode, definingClass.internalName, new NullnessAnalyzer)
-      else new AsmAnalyzer(methodNode, definingClass.internalName)
+      if (compilerSettings.YoptNullnessTracking && AsmAnalyzer.sizeOKForNullness(methodNode)) {
+        Some(new AsmAnalyzer(methodNode, definingClass.internalName, new NullnessAnalyzer))
+      } else if (AsmAnalyzer.sizeOKForBasicValue(methodNode)) {
+        Some(new AsmAnalyzer(methodNode, definingClass.internalName))
+      } else None
     }
 
-    def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = analyzer.analyzer match {
-      case nullnessAnalyzer: NullnessAnalyzer =>
-        val frame = nullnessAnalyzer.frameAt(call, methodNode)
-        frame.getStack(frame.getStackSize - 1 - numArgs) eq NotNullValue
+    // if the method is too large to run an analyzer, it is not added to the call graph
+    if (analyzer.nonEmpty) {
+      val Some(a) = analyzer
+      def receiverNotNullByAnalysis(call: MethodInsnNode, numArgs: Int) = a.analyzer match {
+        case nullnessAnalyzer: NullnessAnalyzer =>
+          val frame = nullnessAnalyzer.frameAt(call, methodNode)
+          frame.getStack(frame.getStackSize - 1 - numArgs) eq NotNullValue
+        case _ => false
+      }
 
-      case _ => false
-    }
+      var methodCallsites = Map.empty[MethodInsnNode, Callsite]
+      var methodClosureInstantiations = Map.empty[InvokeDynamicInsnNode, ClosureInstantiation]
+
+      // lazy so it is only computed if actually used by computeArgInfos
+      lazy val prodCons = new ProdConsAnalyzer(methodNode, definingClass.internalName)
+
+      methodNode.instructions.iterator.asScala foreach {
+        case call: MethodInsnNode if a.frameAt(call) != null => // skips over unreachable code
+          val callee: Either[OptimizerWarning, Callee] = for {
+            (method, declarationClass)     <- byteCodeRepository.methodNode(call.owner, call.name, call.desc): Either[OptimizerWarning, (MethodNode, InternalName)]
+            (declarationClassNode, source) <- byteCodeRepository.classNodeAndSource(declarationClass): Either[OptimizerWarning, (ClassNode, Source)]
+            declarationClassBType          =  classBTypeFromClassNode(declarationClassNode)
+          } yield {
+              val CallsiteInfo(safeToInline, safeToRewrite, annotatedInline, annotatedNoInline, samParamTypes, warning) = analyzeCallsite(method, declarationClassBType, call.owner, source)
+              Callee(
+                callee = method,
+                calleeDeclarationClass = declarationClassBType,
+                safeToInline = safeToInline,
+                safeToRewrite = safeToRewrite,
+                annotatedInline = annotatedInline,
+                annotatedNoInline = annotatedNoInline,
+                samParamTypes = samParamTypes,
+                calleeInfoWarning = warning)
+            }
 
-    var methodCallsites = Map.empty[MethodInsnNode, Callsite]
-    var methodClosureInstantiations = Map.empty[InvokeDynamicInsnNode, ClosureInstantiation]
-
-    // lazy so it is only computed if actually used by computeArgInfos
-    lazy val prodCons = new ProdConsAnalyzer(methodNode, definingClass.internalName)
-
-    methodNode.instructions.iterator.asScala foreach {
-      case call: MethodInsnNode if analyzer.frameAt(call) != null => // skips over unreachable code
-        val callee: Either[OptimizerWarning, Callee] = for {
-          (method, declarationClass)     <- byteCodeRepository.methodNode(call.owner, call.name, call.desc): Either[OptimizerWarning, (MethodNode, InternalName)]
-          (declarationClassNode, source) <- byteCodeRepository.classNodeAndSource(declarationClass): Either[OptimizerWarning, (ClassNode, Source)]
-          declarationClassBType          =  classBTypeFromClassNode(declarationClassNode)
-        } yield {
-          val CallsiteInfo(safeToInline, safeToRewrite, annotatedInline, annotatedNoInline, samParamTypes, warning) = analyzeCallsite(method, declarationClassBType, call.owner, source)
-          Callee(
-            callee = method,
-            calleeDeclarationClass = declarationClassBType,
-            safeToInline = safeToInline,
-            safeToRewrite = safeToRewrite,
-            annotatedInline = annotatedInline,
-            annotatedNoInline = annotatedNoInline,
-            samParamTypes = samParamTypes,
-            calleeInfoWarning = warning)
-        }
+          val argInfos = computeArgInfos(callee, call, prodCons)
 
-        val argInfos = computeArgInfos(callee, call, prodCons)
+          val receiverNotNull = call.getOpcode == Opcodes.INVOKESTATIC || {
+            val numArgs = Type.getArgumentTypes(call.desc).length
+            receiverNotNullByAnalysis(call, numArgs)
+          }
 
-        val receiverNotNull = call.getOpcode == Opcodes.INVOKESTATIC || {
-          val numArgs = Type.getArgumentTypes(call.desc).length
-          receiverNotNullByAnalysis(call, numArgs)
-        }
+          methodCallsites += call -> Callsite(
+            callsiteInstruction = call,
+            callsiteMethod = methodNode,
+            callsiteClass = definingClass,
+            callee = callee,
+            argInfos = argInfos,
+            callsiteStackHeight = a.frameAt(call).getStackSize,
+            receiverKnownNotNull = receiverNotNull,
+            callsitePosition = callsitePositions.getOrElse(call, NoPosition)
+          )
+
+        case LambdaMetaFactoryCall(indy, samMethodType, implMethod, instantiatedMethodType) if a.frameAt(indy) != null =>
+          val lmf = LambdaMetaFactoryCall(indy, samMethodType, implMethod, instantiatedMethodType)
+          val capturedArgInfos = computeCapturedArgInfos(lmf, prodCons)
+          methodClosureInstantiations += indy -> ClosureInstantiation(
+            lmf,
+            methodNode,
+            definingClass,
+            capturedArgInfos)
 
-        methodCallsites += call -> Callsite(
-          callsiteInstruction = call,
-          callsiteMethod = methodNode,
-          callsiteClass = definingClass,
-          callee = callee,
-          argInfos = argInfos,
-          callsiteStackHeight = analyzer.frameAt(call).getStackSize,
-          receiverKnownNotNull = receiverNotNull,
-          callsitePosition = callsitePositions.getOrElse(call, NoPosition)
-        )
-
-      case LambdaMetaFactoryCall(indy, samMethodType, implMethod, instantiatedMethodType) if analyzer.frameAt(indy) != null =>
-        val lmf = LambdaMetaFactoryCall(indy, samMethodType, implMethod, instantiatedMethodType)
-        val capturedArgInfos = computeCapturedArgInfos(lmf, prodCons)
-        methodClosureInstantiations += indy -> ClosureInstantiation(
-          lmf,
-          methodNode,
-          definingClass,
-          capturedArgInfos)
-
-      case _ =>
-    }
+        case _ =>
+      }
 
-    callsites(methodNode) = methodCallsites
-    closureInstantiations(methodNode) = methodClosureInstantiations
+      callsites(methodNode) = methodCallsites
+      closureInstantiations(methodNode) = methodClosureInstantiations
+    }
   }
 
   def computeArgInfos(callee: Either[OptimizerWarning, Callee], callsiteInsn: MethodInsnNode, prodCons: => ProdConsAnalyzer): IntMap[ArgInfo] = {
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
index 23b85d175e..5d3b7ff272 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/ClosureOptimizer.scala
@@ -78,6 +78,8 @@ class ClosureOptimizer[BT <: BTypes](val btypes: BT) {
       closureInstantiations.iterator.flatMap({
         case (methodNode, closureInits) =>
           // A lazy val to ensure the analysis only runs if necessary (the value is passed by name to `closureCallsites`)
+          // We don't need to worry about the method being too large for running an analysis: large
+          // methods are not added to the call graph / closureInstantiations map.
           lazy val prodCons = new ProdConsAnalyzer(methodNode, closureInits.valuesIterator.next().ownerClass.internalName)
           val sortedInits = immutable.TreeSet.empty ++ closureInits.values
           sortedInits.iterator.map(init => (init, closureCallsites(init, prodCons))).filter(_._2.nonEmpty)
diff --git a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
index 4c36377128..54f1b99876 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -143,6 +143,8 @@ class Inliner[BT <: BTypes](val btypes: BT) {
         // VerifyError. We run a `SourceInterpreter` to find all producer instructions of the
         // receiver value and add a cast to the self type after each.
         if (!selfTypeOk) {
+          // We don't need to worry about the method being too large for running an analysis.
+          // Callsites of large methods are not added to the call graph.
           localOpt.minimalRemoveUnreachableCode(callsite.callsiteMethod, callsite.callsiteClass.internalName)
           val analyzer = new AsmAnalyzer(callsite.callsiteMethod, callsite.callsiteClass.internalName, new Analyzer(new SourceInterpreter))
           val receiverValue = analyzer.frameAt(callsite.callsiteInstruction).peekStack(traitMethodArgumentTypes.length)
@@ -367,6 +369,8 @@ class Inliner[BT <: BTypes](val btypes: BT) {
 
     // We run an interpreter to know the stack height at each xRETURN instruction and the sizes
     // of the values on the stack.
+    // We don't need to worry about the method being too large for running an analysis. Callsites of
+    // large methods are not added to the call graph.
     val analyzer = new AsmAnalyzer(callee, calleeDeclarationClass.internalName)
 
     for (originalReturn <- callee.instructions.iterator().asScala if isReturn(originalReturn)) {
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 684ef30adf..1e7b46012e 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/LocalOpt.scala
@@ -94,6 +94,7 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
   def minimalRemoveUnreachableCode(method: MethodNode, ownerClassName: InternalName): Set[AbstractInsnNode] = {
     if (method.instructions.size == 0) return Set.empty     // fast path for abstract methods
     if (unreachableCodeEliminated(method)) return Set.empty // we know there is no unreachable code
+    if (!AsmAnalyzer.sizeOKForBasicValue(method)) return Set.empty // the method is too large for running an analyzer
 
     // For correctness, after removing unreachable code, we have to eliminate empty exception
     // handlers, see scaladoc of def methodOptimizations. Removing an live handler may render more
@@ -169,9 +170,10 @@ class LocalOpt[BT <: BTypes](val btypes: BT) {
     // This triggers "ClassFormatError: Illegal exception table range in class file C". Similar
     // for local variables in dead blocks. Maybe that's a bug in the ASM framework.
 
+    def canRunDCE = AsmAnalyzer.sizeOKForBasicValue(method)
     def removalRound(): Boolean = {
       // unreachable-code, empty-handlers and simplify-jumps run until reaching a fixpoint (see doc on class LocalOpt)
-      val (codeRemoved, handlersRemoved, liveHandlerRemoved) = if (compilerSettings.YoptUnreachableCode) {
+      val (codeRemoved, handlersRemoved, liveHandlerRemoved) = if (compilerSettings.YoptUnreachableCode && canRunDCE) {
         val (removedInstructions, liveLabels) = removeUnreachableCodeImpl(method, ownerClassName)
         val removedHandlers = removeEmptyExceptionHandlers(method)
         (removedInstructions.nonEmpty, removedHandlers.nonEmpty, removedHandlers.exists(h => liveLabels(h.start)))