/* NSC -- new Scala compiler * Copyright 2005-2014 LAMP/EPFL * @author Martin Odersky */ package scala.tools.nsc package backend.jvm package opt import scala.annotation.tailrec import scala.tools.asm import asm.Opcodes._ import asm.tree._ import scala.collection.JavaConverters._ import AsmUtils._ import BytecodeUtils._ import collection.mutable import BackendReporting._ import scala.tools.nsc.backend.jvm.BTypes.InternalName class Inliner[BT <: BTypes](val btypes: BT) { import btypes._ import callGraph._ import inlinerHeuristics._ import backendUtils._ sealed trait InlineLog { def request: InlineRequest } final case class InlineLogSuccess(request: InlineRequest, sizeBefore: Int, sizeInlined: Int) extends InlineLog { var downstreamLog: mutable.Buffer[InlineLog] = mutable.ListBuffer.empty } final case class InlineLogFail(request: InlineRequest, warning: CannotInlineWarning) extends InlineLog final case class InlineLogRollback(request: InlineRequest, warnings: List[CannotInlineWarning]) extends InlineLog object InlineLog { private def shouldLog(request: InlineRequest): Boolean = { def logEnabled = compilerSettings.YoptLogInline.isSetByUser def matchesName = { val prefix = compilerSettings.YoptLogInline.value match { case "_" => "" case p => p } val name: String = request.callsite.callsiteClass.internalName + "." + request.callsite.callsiteMethod.name name startsWith prefix } logEnabled && (upstream != null || (isTopLevel && matchesName)) } // indexed by callsite method private val logs = mutable.Map.empty[MethodNode, mutable.LinkedHashSet[InlineLog]] private var upstream: InlineLogSuccess = _ private var isTopLevel = true def withInlineLogging[T](request: InlineRequest)(inlineRequest: => Unit)(inlinePost: => T): T = { def doInlinePost(): T = { val savedIsTopLevel = isTopLevel isTopLevel = false try inlinePost finally isTopLevel = savedIsTopLevel } if (shouldLog(request)) { val sizeBefore = request.callsite.callsiteMethod.instructions.size inlineRequest val log = InlineLogSuccess(request, sizeBefore, request.callsite.callee.get.callee.instructions.size) apply(log) val savedUpstream = upstream upstream = log try doInlinePost() finally upstream = savedUpstream } else { inlineRequest doInlinePost() } } def apply(log: => InlineLog): Unit = if (shouldLog(log.request)) { if (upstream != null) upstream.downstreamLog += log else { val methodLogs = logs.getOrElseUpdate(log.request.callsite.callsiteMethod, mutable.LinkedHashSet.empty) methodLogs += log } } def entryString(log: InlineLog, indent: Int = 0): String = { val callee = log.request.callsite.callee.get val calleeString = callee.calleeDeclarationClass.internalName + "." + callee.callee.name val indentString = " " * indent log match { case s @ InlineLogSuccess(_, sizeBefore, sizeInlined) => val self = s"${indentString}inlined $calleeString. Before: $sizeBefore ins, inlined: $sizeInlined ins." if (s.downstreamLog.isEmpty) self else s.downstreamLog.iterator.map(entryString(_, indent + 2)).mkString(self + "\n", "\n", "") case InlineLogFail(_, w) => s"${indentString}failed $calleeString. ${w.toString.replace('\n', ' ')}" case InlineLogRollback(_, _) => s"${indentString}rolling back, nested inline failed." } } def print(): Unit = if (compilerSettings.YoptLogInline.isSetByUser) { val byClassAndMethod: List[(InternalName, mutable.Map[MethodNode, mutable.LinkedHashSet[InlineLog]])] = { logs. groupBy(_._2.head.request.callsite.callsiteClass.internalName). toList.sortBy(_._1) } for { (c, methodLogs) <- byClassAndMethod (m, mLogs) <- methodLogs.toList.sortBy(_._1.name) mLog <- mLogs // insertion order } { println(s"Inline into $c.${m.name}: ${entryString(mLog)}") } } } def runInliner(): Unit = { for (request <- collectAndOrderInlineRequests) { val Right(callee) = request.callsite.callee // collectAndOrderInlineRequests returns callsites with a known callee val warnings = inline(request) for (warning <- warnings) { if (warning.emitWarning(compilerSettings)) backendReporting.inlinerWarning(request.callsite.callsitePosition, warning.toString) } } InlineLog.print() } /** * Ordering for inline requests. Required to make the inliner deterministic: * - Always remove the same request when breaking inlining cycles * - Perform inlinings in a consistent order */ object callsiteOrdering extends Ordering[InlineRequest] { override def compare(x: InlineRequest, y: InlineRequest): Int = { val xCs = x.callsite val yCs = y.callsite val cls = xCs.callsiteClass.internalName compareTo yCs.callsiteClass.internalName if (cls != 0) return cls val name = xCs.callsiteMethod.name compareTo yCs.callsiteMethod.name if (name != 0) return name val desc = xCs.callsiteMethod.desc compareTo yCs.callsiteMethod.desc if (desc != 0) return desc def pos(c: Callsite) = c.callsiteMethod.instructions.indexOf(c.callsiteInstruction) pos(xCs) - pos(yCs) } } /** * Returns the callsites that can be inlined. Ensures that the returned inline request graph does * not contain cycles. * * The resulting list is sorted such that the leaves of the inline request graph are on the left. * Once these leaves are inlined, the successive elements will be leaves, etc. */ private def collectAndOrderInlineRequests: List[InlineRequest] = { val requestsByMethod = selectCallsitesForInlining withDefaultValue Set.empty val elided = mutable.Set.empty[InlineRequest] def nonElidedRequests(methodNode: MethodNode): Set[InlineRequest] = requestsByMethod(methodNode) diff elided def allCallees(r: InlineRequest): Set[MethodNode] = r.post.flatMap(allCallees).toSet + r.callsite.callee.get.callee /** * Break cycles in the inline request graph by removing callsites. * * The list `requests` is traversed left-to-right, removing those callsites that are part of a * cycle. Elided callsites are also removed from the `inlineRequestsForMethod` map. */ def breakInlineCycles: List[InlineRequest] = { // is there a path of inline requests from start to goal? def isReachable(start: Set[MethodNode], goal: MethodNode): Boolean = { @tailrec def reachableImpl(check: Set[MethodNode], visited: Set[MethodNode]): Boolean = { if (check.isEmpty) false else { val x = check.head if (x == goal) true else if (visited(x)) reachableImpl(check - x, visited) else { val callees = nonElidedRequests(x).flatMap(allCallees) reachableImpl(check - x ++ callees, visited + x) } } } reachableImpl(start, Set.empty) } val result = new mutable.ListBuffer[InlineRequest]() val requests = requestsByMethod.valuesIterator.flatten.toArray // sort the inline requests to ensure that removing requests is deterministic java.util.Arrays.sort(requests, callsiteOrdering) for (r <- requests) { // is there a chain of inlining requests that would inline the callsite method into the callee? if (isReachable(allCallees(r), r.callsite.callsiteMethod)) elided += r else result += r () } result.toList } // sort the remaining inline requests such that the leaves appear first, then those requests // that become leaves, etc. def leavesFirst(requests: List[InlineRequest], visited: Set[InlineRequest] = Set.empty): List[InlineRequest] = { if (requests.isEmpty) Nil else { val (leaves, others) = requests.partition(r => { val inlineRequestsForCallees = allCallees(r).flatMap(nonElidedRequests) inlineRequestsForCallees.forall(visited) }) assert(leaves.nonEmpty, requests) leaves ::: leavesFirst(others, visited ++ leaves) } } leavesFirst(breakInlineCycles) } /** * Given an InlineRequest(mainCallsite, post = List(postCallsite)), the postCallsite is a callsite * in the method `mainCallsite.callee`. Once the mainCallsite is inlined into the target method * (mainCallsite.callsiteMethod), we need to find the cloned callsite that corresponds to the * postCallsite so we can inline that into the target method as well. * * However, it is possible that there is no cloned callsite at all that corresponds to the * postCallsite, for example if the corresponding callsite already inlined. Example: * * def a() = 1 * def b() = a() + 2 * def c() = b() + 3 * def d() = c() + 4 * * We have the following callsite objects in the call graph: * * c1 = a() in b * c2 = b() in c * c3 = c() in d * * Assume we have the following inline request * r = InlineRequest(c3, * post = List(InlineRequest(c2, * post = List(InlineRequest(c1, post = Nil))))) * * But before inlining r, assume a separate InlineRequest(c2, post = Nil) is inlined first. We get * * c1' = a() in c // added to the call graph * c1.inlinedClones += (c1' at c2) // remember that c1' was created when inlining c2 * ~c2~ // c2 is removed from the call graph * * If we now inline r, we first inline c3. We get * * c1'' = a() in d // added to call graph * c1'.inlinedClones += (c1'' at c3) // remember that c1'' was created when inlining c3 * ~c3~ * * Now we continue with the post-requests for r, i.e. c2. * - we try to find the clone of c2 that was created when inlining c3 - but there is none. c2 * was already inlined before * - we continue with the post-request of c2: c1 * - we search for the callsite of c1 that was cloned when inlining c2, we find c1' * - recursively we search for the callsite of c1' that was cloned when inlining c3, we find c1'' * - so we create an inline request for c1'' */ def adaptPostRequestForMainCallsite(post: InlineRequest, mainCallsite: Callsite): List[InlineRequest] = { def impl(post: InlineRequest, at: Callsite): List[InlineRequest] = { post.callsite.inlinedClones.find(_.clonedWhenInlining == at) match { case Some(clonedCallsite) => List(InlineRequest(clonedCallsite.callsite, post.post, post.reason)) case None => post.post.flatMap(impl(_, post.callsite)).flatMap(impl(_, at)) } } impl(post, mainCallsite) } class UndoLog(active: Boolean = true) { import java.util.{ ArrayList => JArrayList } private var actions = List.empty[() => Unit] private var methodStateSaved = false def apply(a: => Unit): Unit = if (active) actions = (() => a) :: actions def rollback(): Unit = if (active) actions.foreach(_.apply()) def saveMethodState(methodNode: MethodNode): Unit = if (active && !methodStateSaved) { methodStateSaved = true val currentInstructions = methodNode.instructions.toArray val currentLocalVariables = new JArrayList(methodNode.localVariables) val currentTryCatchBlocks = new JArrayList(methodNode.tryCatchBlocks) val currentMaxLocals = methodNode.maxLocals val currentMaxStack = methodNode.maxStack apply { // `methodNode.instructions.clear()` doesn't work: it keeps the `prev` / `next` / `index` of // instruction nodes. `instructions.removeAll(true)` would work, but is not public. methodNode.instructions.iterator.asScala.toList.foreach(methodNode.instructions.remove) for (i <- currentInstructions) methodNode.instructions.add(i) methodNode.localVariables.clear() methodNode.localVariables.addAll(currentLocalVariables) methodNode.tryCatchBlocks.clear() methodNode.tryCatchBlocks.addAll(currentTryCatchBlocks) methodNode.maxLocals = currentMaxLocals methodNode.maxStack = currentMaxStack } } } val NoUndoLogging = new UndoLog(active = false) /** * Inline the callsite of an inlining request and its post-inlining requests. * * @return An inliner warning for each callsite that could not be inlined. */ def inline(request: InlineRequest, undo: UndoLog = NoUndoLogging): List[CannotInlineWarning] = { def doInline(undo: UndoLog, callRollback: Boolean = false): List[CannotInlineWarning] = { InlineLog.withInlineLogging(request) { inlineCallsite(request.callsite, undo) } { val postRequests = request.post.flatMap(adaptPostRequestForMainCallsite(_, request.callsite)) val warnings = postRequests.flatMap(inline(_, undo)) if (callRollback && warnings.nonEmpty) { undo.rollback() InlineLog(InlineLogRollback(request, warnings)) } warnings } } def inlinedByPost(insns: List[AbstractInsnNode]): Boolean = insns.nonEmpty && insns.forall(ins => request.post.exists(_.callsite.callsiteInstruction == ins)) canInlineCallsite(request.callsite) match { case None => doInline(undo) case Some((_, illegalAccessInsns)) if inlinedByPost(illegalAccessInsns) => // speculatively inline, roll back if an illegalAccessInsn cannot be eliminated if (undo == NoUndoLogging) doInline(new UndoLog(), callRollback = true) else doInline(undo) case Some((w, _)) => InlineLog(InlineLogFail(request, w)) List(w) } } /** * Copy and adapt the instructions of a method to a callsite. * * Preconditions: * - The callsite can safely be inlined (canInlineBody is true) * - The maxLocals and maxStack values of the callsite method are correctly computed * * @return A map associating instruction nodes of the callee with the corresponding cloned * instruction in the callsite method. */ def inlineCallsite(callsite: Callsite, undo: UndoLog = NoUndoLogging): Unit = { import callsite.{callsiteClass, callsiteMethod, callsiteInstruction, receiverKnownNotNull, callsiteStackHeight} val Right(callsiteCallee) = callsite.callee import callsiteCallee.{callee, calleeDeclarationClass, sourceFilePath} // Inlining requires the callee not to have unreachable code, the analyzer used below should not // return any `null` frames. Note that inlining a method can create unreachable code. Example: // def f = throw e // def g = f; println() // println is unreachable after inlining f // If we have an inline request for a call to g, and f has been already inlined into g, we // need to run DCE on g's body before inlining g. localOpt.minimalRemoveUnreachableCode(callee, calleeDeclarationClass.internalName) // If the callsite was eliminated by DCE, do nothing. if (!callGraph.containsCallsite(callsite)) return // New labels for the cloned instructions val labelsMap = cloneLabels(callee) val sameSourceFile = sourceFilePath match { case Some(calleeSource) => byteCodeRepository.compilingClasses.get(callsiteClass.internalName) match { case Some((_, `calleeSource`)) => true case _ => false } case _ => false } val (clonedInstructions, instructionMap, targetHandles) = cloneInstructions(callee, labelsMap, keepLineNumbers = sameSourceFile) // 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 iinc: IincInsnNode => iinc.`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) val calleeParamTypes = calleAsmType.getArgumentTypes for(argTp <- calleeParamTypes) { 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 replaced 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. // 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)) { 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.peekStack(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) } undo.saveMethodState(callsiteMethod) callsiteMethod.instructions.insert(callsiteInstruction, clonedInstructions) callsiteMethod.instructions.remove(callsiteInstruction) callsiteMethod.localVariables.addAll(cloneLocalVariableNodes(callee, labelsMap, callee.name, localVarShift).asJava) // prepend the handlers of the callee. the order of handlers matters: when an exception is thrown // at some instruction, the first handler guarding that instruction and having a matching exception // type is executed. prepending the callee's handlers makes sure to test those handlers first if // an exception is thrown in the inlined code. callsiteMethod.tryCatchBlocks.addAll(0, cloneTryCatchBlockNodes(callee, labelsMap).asJava) callsiteMethod.maxLocals += returnType.getSize + callee.maxLocals val maxStackOfInlinedCode = { // One slot per value is correct for long / double, see comment in the `analysis` package object. val numStoredArgs = calleeParamTypes.length + (if (isStaticMethod(callee)) 0 else 1) callee.maxStack + callsiteStackHeight - numStoredArgs } val stackHeightAtNullCheck = { // When adding a null check for the receiver, a DUP is inserted, which might cause a new maxStack. // If the callsite has other argument values than the receiver on the stack, these are pop'ed // and stored into locals before the null check, so in that case the maxStack doesn't grow. val stackSlotForNullCheck = if (!isStaticMethod(callee) && !receiverKnownNotNull && calleeParamTypes.isEmpty) 1 else 0 callsiteStackHeight + stackSlotForNullCheck } callsiteMethod.maxStack = math.max(callsiteMethod.maxStack, math.max(stackHeightAtNullCheck, maxStackOfInlinedCode)) val added = addIndyLambdaImplMethod(callsiteClass.internalName, targetHandles) undo { removeIndyLambdaImplMethod(callsiteClass.internalName, added) } callGraph.addIfMissing(callee, calleeDeclarationClass) def mapArgInfo(argInfo: (Int, ArgInfo)): Option[(Int, ArgInfo)] = argInfo match { case lit @ (_, FunctionLiteral) => Some(lit) case (argIndex, ForwardedParam(paramIndex)) => callsite.argInfos.get(paramIndex).map((argIndex, _)) } // Add all invocation instructions and closure instantiations that were inlined to the call graph callGraph.callsites(callee).valuesIterator foreach { originalCallsite => val newCallsiteIns = instructionMap(originalCallsite.callsiteInstruction).asInstanceOf[MethodInsnNode] val argInfos = originalCallsite.argInfos flatMap mapArgInfo val newCallsite = originalCallsite.copy( callsiteInstruction = newCallsiteIns, callsiteMethod = callsiteMethod, callsiteClass = callsiteClass, argInfos = argInfos, callsiteStackHeight = callsiteStackHeight + originalCallsite.callsiteStackHeight ) val clonedCallsite = ClonedCallsite(newCallsite, callsite) originalCallsite.inlinedClones += clonedCallsite callGraph.addCallsite(newCallsite) undo { originalCallsite.inlinedClones -= clonedCallsite callGraph.removeCallsite(newCallsite.callsiteInstruction, newCallsite.callsiteMethod) } } callGraph.closureInstantiations(callee).valuesIterator foreach { originalClosureInit => val newIndy = instructionMap(originalClosureInit.lambdaMetaFactoryCall.indy).asInstanceOf[InvokeDynamicInsnNode] val capturedArgInfos = originalClosureInit.capturedArgInfos flatMap mapArgInfo val newClosureInit = ClosureInstantiation( originalClosureInit.lambdaMetaFactoryCall.copy(indy = newIndy), callsiteMethod, callsiteClass, capturedArgInfos) originalClosureInit.inlinedClones += newClosureInit callGraph.addClosureInstantiation(newClosureInit) undo { callGraph.removeClosureInstantiation(newClosureInit.lambdaMetaFactoryCall.indy, newClosureInit.ownerMethod) } } // Remove the elided invocation from the call graph callGraph.removeCallsite(callsiteInstruction, callsiteMethod) undo { callGraph.addCallsite(callsite) } // Inlining a method body can render some code unreachable, see example above in this method. unreachableCodeEliminated -= callsiteMethod } /** * Check whether an inlining can be performed. This method performs tests that don't change even * if the body of the callee is changed by the inliner / optimizer, so it can be used early * (when looking at the call graph and collecting inline requests for the program). * * The tests that inspect the callee's instructions are implemented in method `canInlineBody`, * which is queried when performing an inline. * * @return `Some(message)` if inlining cannot be performed, `None` otherwise */ def earlyCanInlineCheck(callsite: Callsite): Option[CannotInlineWarning] = { import callsite.{callsiteMethod, callsiteClass} val Right(callsiteCallee) = callsite.callee import callsiteCallee.{callee, calleeDeclarationClass} 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(SynchronizedMethod(calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated)) } else if (isStrictfpMethod(callsiteMethod) != isStrictfpMethod(callee)) { Some(StrictfpMismatch( calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated, callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc)) } else None } /** * Check whether the body of the callee contains any instructions that prevent the callsite from * being inlined. See also method `earlyCanInlineCheck`. * * The result of this check depends on changes to the callee method's body. For example, if the * callee initially invokes a private method, it cannot be inlined into a different class. If the * private method is inlined into the callee, inlining the callee becomes possible. Therefore * we don't query it while traversing the call graph and selecting callsites to inline - it might * rule out callsites that can be inlined just fine. * * Returns * - `None` if the callsite can be inlined * - `Some((message, Nil))` if there was an issue performing the access checks, for example * because of a missing classfile * - `Some((message, instructions))` if inlining `instructions` into the callsite method would * cause an IllegalAccessError */ def canInlineCallsite(callsite: Callsite): Option[(CannotInlineWarning, List[AbstractInsnNode])] = { import callsite.{callsiteInstruction, callsiteMethod, callsiteClass, callsiteStackHeight} val Right(callsiteCallee) = callsite.callee import callsiteCallee.{callee, calleeDeclarationClass} 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 (codeSizeOKForInlining(callsiteMethod, callee)) { val warning = ResultingMethodTooLarge( calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated, callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc) Some((warning, Nil)) } else if (!callee.tryCatchBlocks.isEmpty && stackHasNonParameters) { val warning = MethodWithHandlerCalledOnNonEmptyStack( calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated, callsiteClass.internalName, callsiteMethod.name, callsiteMethod.desc) Some((warning, Nil)) } else findIllegalAccess(callee.instructions, calleeDeclarationClass, callsiteClass) match { case Right(Nil) => None case Right(illegalAccessInsns) => val warning = IllegalAccessInstruction( calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated, callsiteClass.internalName, illegalAccessInsns.head) Some((warning, illegalAccessInsns)) case Left((illegalAccessIns, cause)) => val warning = IllegalAccessCheckFailed( calleeDeclarationClass.internalName, callee.name, callee.desc, callsite.isInlineAnnotated, callsiteClass.internalName, illegalAccessIns, cause) Some((warning, Nil)) } } /** * Check if a type is accessible to some class, as defined in JVMS 5.4.4. * (A1) C is public * (A2) C and D are members of the same run-time package */ def classIsAccessible(accessed: BType, from: ClassBType): Either[OptimizerWarning, Boolean] = (accessed: @unchecked) match { // TODO: A2 requires "same run-time package", which seems to be package + classloader (JVMS 5.3.). is the below ok? case c: ClassBType => c.isPublic.map(_ || c.packageInternalName == from.packageInternalName) case a: ArrayBType => classIsAccessible(a.elementType, from) case _: PrimitiveBType => Right(true) } /** * Check if a member reference is accessible from the [[destinationClass]], as defined in the * JVMS 5.4.4. Note that the class name in a field / method reference is not necessarily the * class in which the member is declared: * * class A { def f = 0 }; class B extends A { f } * * The INVOKEVIRTUAL instruction uses a method reference "B.f ()I". Therefore this method has * two parameters: * * @param memberDeclClass The class in which the member is declared (A) * @param memberRefClass The class used in the member reference (B) * * (B0) JVMS 5.4.3.2 / 5.4.3.3: when resolving a member of class C in D, the class C is resolved * first. According to 5.4.3.1, this requires C to be accessible in D. * * JVMS 5.4.4 summary: A field or method R is accessible to a class D (destinationClass) iff * (B1) R is public * (B2) R is protected, declared in C (memberDeclClass) and D is a subclass of C. * If R is not static, R must contain a symbolic reference to a class T (memberRefClass), * such that T is either a subclass of D, a superclass of D, or D itself. * Also (P) needs to be satisfied. * (B3) R is either protected or has default access and declared by a class in the same * run-time package as D. * If R is protected, also (P) needs to be satisfied. * (B4) R is private and is declared in D. * * (P) When accessing a protected instance member, the target object on the stack (the receiver) * has to be a subtype of D (destinationClass). This is enforced by classfile verification * (https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.8). * * TODO: we cannot currently implement (P) because we don't have the necessary information * available. Once we have a type propagation analysis implemented, we can extract the receiver * type from there (https://github.com/scala-opt/scala/issues/13). */ def memberIsAccessible(memberFlags: Int, memberDeclClass: ClassBType, memberRefClass: ClassBType, from: ClassBType): Either[OptimizerWarning, Boolean] = { // TODO: B3 requires "same run-time package", which seems to be package + classloader (JVMS 5.3.). is the below ok? def samePackageAsDestination = memberDeclClass.packageInternalName == from.packageInternalName def targetObjectConformsToDestinationClass = false // needs type propagation analysis, see above def memberIsAccessibleImpl = { val key = (ACC_PUBLIC | ACC_PROTECTED | ACC_PRIVATE) & memberFlags key match { case ACC_PUBLIC => // B1 Right(true) case ACC_PROTECTED => // B2 val isStatic = (ACC_STATIC & memberFlags) != 0 tryEither { val condB2 = from.isSubtypeOf(memberDeclClass).orThrow && { isStatic || memberRefClass.isSubtypeOf(from).orThrow || from.isSubtypeOf(memberRefClass).orThrow } Right( (condB2 || samePackageAsDestination /* B3 (protected) */) && (isStatic || targetObjectConformsToDestinationClass) // (P) ) } case 0 => // B3 (default access) Right(samePackageAsDestination) case ACC_PRIVATE => // B4 Right(memberDeclClass == from) } } classIsAccessible(memberDeclClass, from) match { // B0 case Right(true) => memberIsAccessibleImpl case r => r } } /** * Returns * - `Right(Nil)` if all instructions can be safely inlined * - `Right(insns)` if inlining any of `insns` would cause a [[java.lang.IllegalAccessError]] * when inlined into the `destinationClass` * - `Left((insn, warning))` if validity of some instruction could not be checked because an * error occurred */ def findIllegalAccess(instructions: InsnList, calleeDeclarationClass: ClassBType, destinationClass: ClassBType): Either[(AbstractInsnNode, OptimizerWarning), List[AbstractInsnNode]] = { /** * Check if `instruction` can be transplanted to `destinationClass`. * * If the instruction references a class, method or field that cannot be found in the * byteCodeRepository, it is considered as not legal. This is known to happen in mixed * compilation: for Java classes there is no classfile that could be parsed, nor does the * compiler generate any bytecode. * * Returns a warning message describing the problem if checking the legality for the instruction * failed. */ def isLegal(instruction: AbstractInsnNode): Either[OptimizerWarning, Boolean] = instruction match { case ti: TypeInsnNode => // NEW, ANEWARRAY, CHECKCAST or INSTANCEOF. For these instructions, the reference // "must be a symbolic reference to a class, array, or interface type" (JVMS 6), so // it can be an internal name, or a full array descriptor. classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ti.desc), destinationClass) case ma: MultiANewArrayInsnNode => // "a symbolic reference to a class, array, or interface type" classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(ma.desc), destinationClass) case fi: FieldInsnNode => val fieldRefClass = classBTypeFromParsedClassfile(fi.owner) for { (fieldNode, fieldDeclClassNode) <- byteCodeRepository.fieldNode(fieldRefClass.internalName, fi.name, fi.desc): Either[OptimizerWarning, (FieldNode, InternalName)] fieldDeclClass = classBTypeFromParsedClassfile(fieldDeclClassNode) res <- memberIsAccessible(fieldNode.access, fieldDeclClass, fieldRefClass, destinationClass) } yield { res } case mi: MethodInsnNode => if (mi.owner.charAt(0) == '[') Right(true) // array methods are accessible else { def canInlineCall(opcode: Int, methodFlags: Int, methodDeclClass: ClassBType, methodRefClass: ClassBType): Either[OptimizerWarning, Boolean] = { opcode match { case INVOKESPECIAL if mi.name != GenBCode.INSTANCE_CONSTRUCTOR_NAME => // invokespecial is used for private method calls, super calls and instance constructor calls. // private method and super calls can only be inlined into the same class. Right(destinationClass == calleeDeclarationClass) case _ => // INVOKEVIRTUAL, INVOKESTATIC, INVOKEINTERFACE and INVOKESPECIAL of constructors memberIsAccessible(methodFlags, methodDeclClass, methodRefClass, destinationClass) } } val methodRefClass = classBTypeFromParsedClassfile(mi.owner) for { (methodNode, methodDeclClassNode) <- byteCodeRepository.methodNode(methodRefClass.internalName, mi.name, mi.desc): Either[OptimizerWarning, (MethodNode, InternalName)] methodDeclClass = classBTypeFromParsedClassfile(methodDeclClassNode) res <- canInlineCall(mi.getOpcode, methodNode.access, methodDeclClass, methodRefClass) } yield { res } } case _: InvokeDynamicInsnNode if destinationClass == calleeDeclarationClass => // within the same class, any indy instruction can be inlined Right(true) // does the InvokeDynamicInsnNode call LambdaMetaFactory? case LambdaMetaFactoryCall(_, _, implMethod, _) => // an indy instr points to a "call site specifier" (CSP) [1] // - a reference to a bootstrap method [2] // - bootstrap method name // - references to constant arguments, which can be: // - constant (string, long, int, float, double) // - class // - method type (without name) // - method handle // - a method name+type // // execution [3] // - resolve the CSP, yielding the bootstrap method handle, the static args and the name+type // - resolution entails accessibility checking [4] // - execute the `invoke` method of the bootstrap method handle (which is signature polymorphic, check its javadoc) // - the descriptor for the call is made up from the actual arguments on the stack: // - the first parameters are "MethodHandles.Lookup, String, MethodType", then the types of the constant arguments, // - the return type is CallSite // - the values for the call are // - the bootstrap method handle of the CSP is the receiver // - the Lookup object for the class in which the callsite occurs (obtained as through calling MethodHandles.lookup()) // - the method name of the CSP // - the method type of the CSP // - the constants of the CSP (primitives are not boxed) // - the resulting `CallSite` object // - has as `type` the method type of the CSP // - is popped from the operand stack // - the `invokeExact` method (signature polymorphic!) of the `target` method handle of the CallSite is invoked // - the method descriptor is that of the CSP // - the receiver is the target of the CallSite // - the other argument values are those that were on the operand stack at the indy instruction (indyLambda: the captured values) // // [1] http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.4.10 // [2] http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.7.23 // [3] http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html#jvms-6.5.invokedynamic // [4] http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-5.html#jvms-5.4.3 // We cannot generically check if an `invokedynamic` instruction can be safely inlined into // a different class, that depends on the bootstrap method. The Lookup object passed to the // bootstrap method is a capability to access private members of the callsite class. We can // only move the invokedynamic to a new class if we know that the bootstrap method doesn't // use this capability for otherwise non-accessible members. // In the case of indyLambda, it depends on the visibility of the implMethod handle. If // the implMethod is public, lambdaMetaFactory doesn't use the Lookup object's extended // capability, and we can safely inline the instruction into a different class. val methodRefClass = classBTypeFromParsedClassfile(implMethod.getOwner) for { (methodNode, methodDeclClassNode) <- byteCodeRepository.methodNode(methodRefClass.internalName, implMethod.getName, implMethod.getDesc): Either[OptimizerWarning, (MethodNode, InternalName)] methodDeclClass = classBTypeFromParsedClassfile(methodDeclClassNode) res <- memberIsAccessible(methodNode.access, methodDeclClass, methodRefClass, destinationClass) } yield { res } case _: InvokeDynamicInsnNode => Left(UnknownInvokeDynamicInstruction) case ci: LdcInsnNode => ci.cst match { case t: asm.Type => classIsAccessible(bTypeForDescriptorOrInternalNameFromClassfile(t.getInternalName), destinationClass) case _ => Right(true) } case _ => Right(true) } val it = instructions.iterator.asScala val illegalAccess = mutable.ListBuffer.empty[AbstractInsnNode] while (it.hasNext) { val i = it.next() isLegal(i) match { case Left(warning) => return Left((i, warning)) // checking isLegal for i failed case Right(false) => illegalAccess += i // an illegal instruction was found case _ => } } Right(illegalAccess.toList) } }