Tools to perform inlining.

The method Inliner.inline clones the bytecode of a method and copies
the new instructions to the callsite with the necessary modifications.
See comments in the code.

More tests are added in a later commit which integrates the inliner
into the backend - tests are easier to write after that.

1 files changed, 197 insertions, 6 deletions

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 6e5e03f730..f964b5b25d 100644
--- a/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
+++ b/src/compiler/scala/tools/nsc/backend/jvm/opt/Inliner.scala
@@ -8,15 +8,206 @@ package backend.jvm
 package opt
 
 import scala.tools.asm
-import asm.Opcodes
+import asm.Opcodes._
 import asm.tree._
 import scala.collection.convert.decorateAsScala._
+import scala.collection.convert.decorateAsJava._
+import AsmUtils._
+import BytecodeUtils._
 import OptimizerReporting._
+import scala.tools.asm.tree.analysis._
 
 class Inliner[BT <: BTypes](val btypes: BT) {
   import btypes._
   import btypes.byteCodeRepository
 
+  /**
+   * Copy and adapt the instructions of a method to a callsite.
+   *
+   * Preconditions:
+   *   - The maxLocals and maxStack values of the callsite method are correctly computed
+   *   - The callsite method contains no unreachable basic blocks, i.e., running an [[Analyzer]]
+   *     does not produce any `null` frames
+   *
+   * @param callsiteInstruction     The invocation instruction
+   * @param callsiteStackHeight     The stack height at the callsite
+   * @param callsiteMethod          The method in which the invocation occurs
+   * @param callsiteClass           The class in which the callsite method is defined
+   * @param callee                  The invoked method
+   * @param calleeDeclarationClass  The class in which the invoked method is defined
+   * @param receiverKnownNotNull    `true` if the receiver is known to be non-null
+   * @param keepLineNumbers         `true` if LineNumberNodes should be copied to the call site
+   * @return                        `Some(message)` if inlining cannot be performed, `None` otherwise
+   */
+  def inline(callsiteInstruction: MethodInsnNode, callsiteStackHeight: Int, callsiteMethod: MethodNode, callsiteClass: ClassBType,
+             callee: MethodNode, calleeDeclarationClass: ClassBType,
+             receiverKnownNotNull: Boolean, keepLineNumbers: Boolean): Option[String] = {
+    canInline(callsiteInstruction, callsiteStackHeight, callsiteMethod, callsiteClass, callee, calleeDeclarationClass) orElse {
+      // New labels for the cloned instructions
+      val labelsMap = cloneLabels(callee)
+      val (clonedInstructions, instructionMap) = cloneInstructions(callee, labelsMap)
+      if (!keepLineNumbers) {
+        removeLineNumberNodes(clonedInstructions)
+      }
+
+      // local vars in the callee are shifted by the number of locals at the callsite
+      val localVarShift = callsiteMethod.maxLocals
+      clonedInstructions.iterator.asScala foreach {
+        case varInstruction: VarInsnNode => varInstruction.`var` += localVarShift
+        case _ => ()
+      }
+
+      // add a STORE instruction for each expected argument, including for THIS instance if any
+      val argStores = new InsnList
+      var nextLocalIndex = callsiteMethod.maxLocals
+      if (!isStaticMethod(callee)) {
+        if (!receiverKnownNotNull) {
+          argStores.add(new InsnNode(DUP))
+          val nonNullLabel = newLabelNode
+          argStores.add(new JumpInsnNode(IFNONNULL, nonNullLabel))
+          argStores.add(new InsnNode(ACONST_NULL))
+          argStores.add(new InsnNode(ATHROW))
+          argStores.add(nonNullLabel)
+        }
+        argStores.add(new VarInsnNode(ASTORE, nextLocalIndex))
+        nextLocalIndex += 1
+      }
+
+      // We just use an asm.Type here, no need to create the MethodBType.
+      val calleAsmType = asm.Type.getMethodType(callee.desc)
+
+      for(argTp <- calleAsmType.getArgumentTypes) {
+        val opc = argTp.getOpcode(ISTORE) // returns the correct xSTORE instruction for argTp
+        argStores.insert(new VarInsnNode(opc, nextLocalIndex)) // "insert" is "prepend" - the last argument is on the top of the stack
+        nextLocalIndex += argTp.getSize
+      }
+
+      clonedInstructions.insert(argStores)
+
+      // label for the exit of the inlined functions. xRETURNs are rplaced by GOTOs to this label.
+      val postCallLabel = newLabelNode
+      clonedInstructions.add(postCallLabel)
+
+      // replace xRETURNs:
+      //   - store the return value (if any)
+      //   - clear the stack of the inlined method (insert DROPs)
+      //   - load the return value
+      //   - GOTO postCallLabel
+
+      val returnType = calleAsmType.getReturnType
+      val hasReturnValue = returnType.getSort != asm.Type.VOID
+      val returnValueIndex = callsiteMethod.maxLocals + callee.maxLocals
+      nextLocalIndex += returnType.getSize
+
+      def returnValueStore(returnInstruction: AbstractInsnNode) = {
+        val opc = returnInstruction.getOpcode match {
+          case IRETURN => ISTORE
+          case LRETURN => LSTORE
+          case FRETURN => FSTORE
+          case DRETURN => DSTORE
+          case ARETURN => ASTORE
+        }
+        new VarInsnNode(opc, returnValueIndex)
+      }
+
+      // We run an interpreter to know the stack height at each xRETURN instruction and the sizes
+      // of the values on the stack.
+      val analyzer = new BasicAnalyzer(callee, calleeDeclarationClass.internalName)
+
+      for (originalReturn <- callee.instructions.iterator().asScala if isReturn(originalReturn)) {
+        val frame = analyzer.frameAt(originalReturn)
+        var stackHeight = frame.getStackSize
+
+        val inlinedReturn = instructionMap(originalReturn)
+        val returnReplacement = new InsnList
+
+        def drop(slot: Int) = returnReplacement add getPop(frame.peekDown(slot).getSize)
+
+        // for non-void methods, store the stack top into the return local variable
+        if (hasReturnValue) {
+          returnReplacement add returnValueStore(originalReturn)
+          stackHeight -= 1
+        }
+
+        // drop the rest of the stack
+        for (i <- 0 until stackHeight) drop(i)
+
+        returnReplacement add new JumpInsnNode(GOTO, postCallLabel)
+        clonedInstructions.insert(inlinedReturn, returnReplacement)
+        clonedInstructions.remove(inlinedReturn)
+      }
+
+      // Load instruction for the return value
+      if (hasReturnValue) {
+        val retVarLoad = {
+          val opc = returnType.getOpcode(ILOAD)
+          new VarInsnNode(opc, returnValueIndex)
+        }
+        clonedInstructions.insert(postCallLabel, retVarLoad)
+      }
+
+      callsiteMethod.instructions.insert(callsiteInstruction, clonedInstructions)
+      callsiteMethod.instructions.remove(callsiteInstruction)
+
+      callsiteMethod.localVariables.addAll(cloneLocalVariableNodes(callee, labelsMap, callee.name + "_").asJava)
+      callsiteMethod.tryCatchBlocks.addAll(cloneTryCatchBlockNodes(callee, labelsMap).asJava)
+
+      callsiteMethod.maxLocals += returnType.getSize + callee.maxLocals
+      callsiteMethod.maxStack = math.max(callsiteMethod.maxStack, callee.maxStack + callsiteStackHeight)
+
+      None
+    }
+  }
+
+  /**
+   * Check whether an inling can be performed. Parmeters are described in method [[inline]].
+   * @return `Some(message)` if inlining cannot be performed, `None` otherwise
+   */
+  def canInline(callsiteInstruction: MethodInsnNode, callsiteStackHeight: Int, callsiteMethod: MethodNode, callsiteClass: ClassBType,
+                callee: MethodNode, calleeDeclarationClass: ClassBType): Option[String] = {
+
+    def calleeDesc = s"${callee.name} of type ${callee.desc} in ${calleeDeclarationClass.internalName}"
+    def methodMismatch = s"Wrong method node for inlining ${textify(callsiteInstruction)}: $calleeDesc"
+    assert(callsiteInstruction.name == callee.name, methodMismatch)
+    assert(callsiteInstruction.desc == callee.desc, methodMismatch)
+    assert(!isConstructor(callee), s"Constructors cannot be inlined: $calleeDesc")
+    assert(!BytecodeUtils.isAbstractMethod(callee), s"Callee is abstract: $calleeDesc")
+    assert(callsiteMethod.instructions.contains(callsiteInstruction), s"Callsite ${textify(callsiteInstruction)} is not an instruction of $calleeDesc")
+
+    // When an exception is thrown, the stack is cleared before jumping to the handler. When
+    // inlining a method that catches an exception, all values that were on the stack before the
+    // call (in addition to the arguments) would be cleared (SI-6157). So we don't inline methods
+    // with handlers in case there are values on the stack.
+    // Alternatively, we could save all stack values below the method arguments into locals, but
+    // that would be inefficient: we'd need to pop all parameters, save the values, and push the
+    // parameters back for the (inlined) invocation. Similarly for the result after the call.
+    def stackHasNonParameters: Boolean = {
+      val expectedArgs = asm.Type.getArgumentTypes(callsiteInstruction.desc).length + (callsiteInstruction.getOpcode match {
+        case INVOKEVIRTUAL | INVOKESPECIAL | INVOKEINTERFACE => 1
+        case INVOKESTATIC => 0
+        case INVOKEDYNAMIC =>
+          assertionError(s"Unexpected opcode, cannot inline ${textify(callsiteInstruction)}")
+      })
+      callsiteStackHeight > expectedArgs
+    }
+
+    if (isSynchronizedMethod(callee)) {
+      // Could be done by locking on the receiver, wrapping the inlined code in a try and unlocking
+      // in finally. But it's probably not worth the effort, scala never emits synchronized methods.
+      Some(s"Method ${methodSignature(calleeDeclarationClass.internalName, callee)} is not inlined because it is synchronized")
+    } else if (!callee.tryCatchBlocks.isEmpty && stackHasNonParameters) {
+      Some(
+        s"""The operand stack at the callsite in ${methodSignature(callsiteClass.internalName, callsiteMethod)} contains more values than the
+           |arguments expected by the callee ${methodSignature(calleeDeclarationClass.internalName, callee)}. These values would be discarded
+           |when entering an exception handler declared in the inlined method.""".stripMargin
+      )
+    } else findIllegalAccess(callee.instructions, callsiteClass) map {
+      case illegalAccessIns =>
+        s"""The callee ${methodSignature(calleeDeclarationClass.internalName, callee)} contains the instruction ${AsmUtils.textify(illegalAccessIns)}
+           |that would cause an IllegalAccessError when inlined into class ${callsiteClass.internalName}""".stripMargin
+    }
+  }
+
   def findIllegalAccess(instructions: InsnList, destinationClass: ClassBType): Option[AbstractInsnNode] = {
 
     /**
@@ -57,14 +248,14 @@ class Inliner[BT <: BTypes](val btypes: BT) {
       // TODO: B3 requires "same run-time package", which seems to be package + classloader (JMVS 5.3.). is the below ok?
       def samePackageAsDestination = memberDeclClass.packageInternalName == destinationClass.packageInternalName
 
-      val key = (Opcodes.ACC_PUBLIC | Opcodes.ACC_PROTECTED | Opcodes.ACC_PRIVATE) & memberFlags
+      val key = (ACC_PUBLIC | ACC_PROTECTED | ACC_PRIVATE) & memberFlags
       key match {
-        case Opcodes.ACC_PUBLIC     =>       // B1
+        case ACC_PUBLIC     =>       // B1
           true
 
-        case Opcodes.ACC_PROTECTED  =>       // B2
+        case ACC_PROTECTED  =>       // B2
           val condB2 = destinationClass.isSubtypeOf(memberDeclClass) && {
-            val isStatic = (Opcodes.ACC_STATIC & memberFlags) != 0
+            val isStatic = (ACC_STATIC & memberFlags) != 0
             isStatic || memberRefClass.isSubtypeOf(destinationClass) || destinationClass.isSubtypeOf(memberRefClass)
           }
           condB2 || samePackageAsDestination // B3 (protected)
@@ -72,7 +263,7 @@ class Inliner[BT <: BTypes](val btypes: BT) {
         case 0 =>                            // B3 (default access)
           samePackageAsDestination
 
-        case Opcodes.ACC_PRIVATE    =>       // B4
+        case ACC_PRIVATE    =>       // B4
           memberDeclClass == destinationClass
       }
     }