1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
/* NSC -- new Scala compiler
* Copyright 2005-2014 LAMP/EPFL
* @author Martin Odersky
*/
package scala.tools.nsc
package backend.jvm
package opt
import scala.reflect.internal.util.{NoPosition, Position}
import scala.tools.asm.tree._
import scala.collection.convert.decorateAsScala._
import scala.tools.nsc.backend.jvm.BTypes.{MethodInlineInfo, InternalName}
import scala.tools.nsc.backend.jvm.BackendReporting._
import scala.tools.nsc.backend.jvm.opt.BytecodeUtils.AsmAnalyzer
import ByteCodeRepository.{Source, CompilationUnit}
class CallGraph[BT <: BTypes](val btypes: BT) {
import btypes._
val callsites: collection.concurrent.Map[MethodInsnNode, Callsite] = recordPerRunCache(collection.concurrent.TrieMap.empty[MethodInsnNode, Callsite])
def addClass(classNode: ClassNode): Unit = {
for (m <- classNode.methods.asScala; callsite <- analyzeCallsites(m, classBTypeFromClassNode(classNode)))
callsites(callsite.callsiteInstruction) = callsite
}
def analyzeCallsites(methodNode: MethodNode, definingClass: ClassBType): List[Callsite] = {
case class CallsiteInfo(safeToInline: Boolean, safeToRewrite: Boolean,
annotatedInline: Boolean, annotatedNoInline: Boolean,
warning: Option[CalleeInfoWarning])
/**
* Analyze a callsite and gather meta-data that can be used for inlining decisions.
*/
def analyzeCallsite(calleeMethodNode: MethodNode, calleeDeclarationClassBType: ClassBType, receiverTypeInternalName: InternalName, calleeSource: Source): CallsiteInfo = {
val methodSignature = calleeMethodNode.name + calleeMethodNode.desc
try {
// The inlineInfo.methodInfos of a ClassBType holds an InlineInfo for each method *declared*
// within a class (not for inherited methods). Since we already have the classBType of the
// callee, we only check there for the methodInlineInfo, we should find it there.
calleeDeclarationClassBType.info.orThrow.inlineInfo.methodInfos.get(methodSignature) match {
case Some(methodInlineInfo) =>
val canInlineFromSource = inlineGlobalEnabled || calleeSource == CompilationUnit
val isAbstract = BytecodeUtils.isAbstractMethod(calleeMethodNode)
// (1) A non-final method can be safe to inline if the receiver type is a final subclass. Example:
// class A { @inline def f = 1 }; object B extends A; B.f // can be inlined
//
// TODO: type analysis can render more calls statically resolved. Example˜∫
// new A.f // can be inlined, the receiver type is known to be exactly A.
val isStaticallyResolved: Boolean = {
methodInlineInfo.effectivelyFinal ||
classBTypeFromParsedClassfile(receiverTypeInternalName).info.orThrow.inlineInfo.isEffectivelyFinal // (1)
}
val isRewritableTraitCall = isStaticallyResolved && methodInlineInfo.traitMethodWithStaticImplementation
val warning = calleeDeclarationClassBType.info.orThrow.inlineInfo.warning.map(
MethodInlineInfoIncomplete(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, _))
// (1) For invocations of final trait methods, the callee isStaticallyResolved but also
// abstract. Such a callee is not safe to inline - it needs to be re-written to the
// static impl method first (safeToRewrite).
// (2) Final trait methods can be rewritten from the interface to the static implementation
// method to enable inlining.
CallsiteInfo(
safeToInline = canInlineFromSource && isStaticallyResolved && !isAbstract, // (1)
safeToRewrite = canInlineFromSource && isRewritableTraitCall, // (2)
annotatedInline = methodInlineInfo.annotatedInline,
annotatedNoInline = methodInlineInfo.annotatedNoInline,
warning = warning)
case None =>
val warning = MethodInlineInfoMissing(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, calleeDeclarationClassBType.info.orThrow.inlineInfo.warning)
CallsiteInfo(false, false, false, false, Some(warning))
}
} catch {
case Invalid(noInfo: NoClassBTypeInfo) =>
val warning = MethodInlineInfoError(calleeDeclarationClassBType.internalName, calleeMethodNode.name, calleeMethodNode.desc, noInfo)
CallsiteInfo(false, false, false, false, Some(warning))
}
}
// TODO: run dataflow analyses to make the call graph more precise
// - producers to get forwarded parameters (ForwardedParam)
// - typeAnalysis for more precise argument types, more precise callee
// - nullAnalysis to skip emitting the receiver-null-check when inlining
// TODO: for now we run a basic analyzer to get the stack height at the call site.
// once we run a more elaborate analyzer (types, nullness), we can get the stack height out of there.
val analyzer = new AsmAnalyzer(methodNode, definingClass.internalName)
methodNode.instructions.iterator.asScala.collect({
case call: MethodInsnNode =>
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, warning) = analyzeCallsite(method, declarationClassBType, call.owner, source)
Callee(
callee = method,
calleeDeclarationClass = declarationClassBType,
safeToInline = safeToInline,
safeToRewrite = safeToRewrite,
annotatedInline = annotatedInline,
annotatedNoInline = annotatedNoInline,
calleeInfoWarning = warning)
}
val argInfos = if (callee.isLeft) Nil else {
// TODO: for now it's Nil, because we don't run any data flow analysis
// there's no point in using the parameter types, that doesn't add any information.
// NOTE: need to run the same analyses after inlining, to re-compute the argInfos for the
// new duplicated callsites, see Inliner.inline
Nil
}
Callsite(
callsiteInstruction = call,
callsiteMethod = methodNode,
callsiteClass = definingClass,
callee = callee,
argInfos = argInfos,
callsiteStackHeight = analyzer.frameAt(call).getStackSize,
callsitePosition = callsitePositions.getOrElse(call, NoPosition)
)
}).toList
}
/**
* A callsite in the call graph.
*
* @param callsiteInstruction The invocation instruction
* @param callsiteMethod The method containing the callsite
* @param callsiteClass The class containing the callsite
* @param callee The callee, as it appears in the invocation instruction. For virtual
* calls, an override of the callee might be invoked. Also, the callee
* can be abstract. Contains a warning message if the callee MethodNode
* cannot be found in the bytecode repository.
* @param argInfos Information about the invocation receiver and arguments
* @param callsiteStackHeight The stack height at the callsite, required by the inliner
* @param callsitePosition The source position of the callsite, used for inliner warnings.
*/
final case class Callsite(callsiteInstruction: MethodInsnNode, callsiteMethod: MethodNode, callsiteClass: ClassBType,
callee: Either[OptimizerWarning, Callee], argInfos: List[ArgInfo],
callsiteStackHeight: Int, callsitePosition: Position) {
override def toString =
"Invocation of" +
s" ${callee.map(_.calleeDeclarationClass.internalName).getOrElse("?")}.${callsiteInstruction.name + callsiteInstruction.desc}" +
s"@${callsiteMethod.instructions.indexOf(callsiteInstruction)}" +
s" in ${callsiteClass.internalName}.${callsiteMethod.name}"
}
/**
* Information about invocation arguments, obtained through data flow analysis of the callsite method.
*/
sealed trait ArgInfo
final case class ArgTypeInfo(argType: BType, isPrecise: Boolean, knownNotNull: Boolean) extends ArgInfo
final case class ForwardedParam(index: Int) extends ArgInfo
// can be extended, e.g., with constant types
/**
* A callee in the call graph.
*
* @param callee The callee, as it appears in the invocation instruction. For
* virtual calls, an override of the callee might be invoked. Also,
* the callee can be abstract.
* @param calleeDeclarationClass The class in which the callee is declared
* @param safeToInline True if the callee can be safely inlined: it cannot be overridden,
* and the inliner settings (project / global) allow inlining it.
* @param safeToRewrite True if the callee the interface method of a concrete trait method
* that can be safely re-written to the static implementation method.
* @param annotatedInline True if the callee is annotated @inline
* @param annotatedNoInline True if the callee is annotated @noinline
* @param calleeInfoWarning An inliner warning if some information was not available while
* gathering the information about this callee.
*/
final case class Callee(callee: MethodNode, calleeDeclarationClass: ClassBType,
safeToInline: Boolean, safeToRewrite: Boolean,
annotatedInline: Boolean, annotatedNoInline: Boolean,
calleeInfoWarning: Option[CalleeInfoWarning]) {
assert(!(safeToInline && safeToRewrite), s"A callee of ${callee.name} can be either safeToInline or safeToRewrite, but not both.")
}
}
|
