/
Inlining.cs
338 lines (313 loc) · 13 KB
/
Inlining.cs
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;
using Flame.Compiler.Flow;
using Flame.Compiler.Instructions;
using Flame.Compiler.Pipeline;
using Flame.Constants;
using Flame.TypeSystem;
namespace Flame.Compiler.Transforms
{
/// <summary>
/// The inlining optimization: a transform that copies the function bodies
/// of callees into the caller, replacing the call with its implementation.
/// </summary>
public class Inlining : Optimization
{
/// <summary>
/// Creates an instance of the inlining optimization.
/// </summary>
protected Inlining()
{ }
/// <summary>
/// An instance of the inlining transformation.
/// </summary>
/// <value>A call-inlining transform.</value>
public static readonly Inlining Instance
= new Inlining();
/// <inheritdoc/>
public override bool IsCheckpoint => false;
/// <inheritdoc/>
public override async Task<MethodBody> ApplyAsync(MethodBody body, OptimizationState state)
{
var graph = body.Implementation.ToBuilder();
// Find all inlinable instructions in the method body, map them
// to their callees.
var candidates = new Dictionary<InstructionBuilder, IMethod>();
foreach (var instruction in graph.Instructions)
{
IMethod callee;
if (TryGetCallee(instruction, out callee)
&& ShouldConsider(callee, state.Method))
{
candidates[instruction] = callee;
}
}
// Request method bodies for all callees.
var bodies = await state.GetBodiesAsync(candidates.Values);
// Actually inline method bodies.
foreach (var pair in candidates)
{
var instruction = pair.Key;
var calleeBody = bodies[pair.Value];
if (calleeBody == null || !CanInline(calleeBody, state.Method, graph.ImmutableGraph))
{
continue;
}
TryInlineCall(instruction, calleeBody);
}
return body.WithImplementation(graph.ToImmutable());
}
private void TryInlineCall(InstructionBuilder instruction, MethodBody calleeBody)
{
var graph = instruction.Graph;
var proto = instruction.Prototype;
if (proto is CallPrototype)
{
if (ShouldInline(calleeBody, instruction.Arguments, graph.ImmutableGraph))
{
instruction.ReplaceInstruction(calleeBody.Implementation, instruction.Arguments);
}
}
else if (proto is NewObjectPrototype)
{
graph.TryForkAndMerge(builder =>
{
// Synthesize a sequence of instructions that creates a zero-filled
// object of the right type.
var builderInsn = builder.GetInstruction(instruction);
var elementType = ((NewObjectPrototype)proto).Constructor.ParentType;
var defaultConst = builderInsn.InsertBefore(
Instruction.CreateConstant(DefaultConstant.Instance, elementType));
var objInstance = builderInsn.InsertBefore(
Instruction.CreateBox(elementType, defaultConst));
var allArgs = new ValueTag[] { objInstance }.Concat(builderInsn.Arguments).ToArray();
if (ShouldInline(calleeBody, allArgs, builder.ImmutableGraph))
{
// Actually inline the newobj call. To do so, we'll rewrite all 'return'
// flows in the callee to return the 'this' pointer and then inline that
// like a regular method call.
var modifiedImpl = calleeBody.Implementation.ToBuilder();
foreach (var block in modifiedImpl.BasicBlocks)
{
if (block.Flow is ReturnFlow)
{
block.Flow = new ReturnFlow(
Instruction.CreateCopy(
modifiedImpl.EntryPoint.Parameters[0].Type,
modifiedImpl.EntryPoint.Parameters[0].Tag));
}
}
builderInsn.ReplaceInstruction(modifiedImpl.ToImmutable(), allArgs);
return true;
}
else
{
// We won't be inlining after all. Nix our changes.
return false;
}
});
}
}
private bool TryGetCallee(InstructionBuilder instruction, out IMethod callee)
{
var proto = instruction.Prototype;
if (proto is CallPrototype)
{
var callProto = (CallPrototype)proto;
if (callProto.Lookup == MethodLookup.Static)
{
callee = callProto.Callee;
return true;
}
}
else if (proto is NewObjectPrototype)
{
var newObjproto = (NewObjectPrototype)proto;
callee = newObjproto.Constructor;
return true;
}
callee = null;
return false;
}
// The methods and properties below constitute the inlining heuristic to use.
// To implement a custom inlining heuristic, inherit from this class and
// override them.
/// <summary>
/// Tells if a method should be considered for inlining.
/// </summary>
/// <param name="callee">A method that might be inlined.</param>
/// <param name="caller">
/// A method that calls <paramref name="callee"/>; it's not sure if it
/// should consider inlining <paramref name="callee"/>.
/// </param>
/// <returns>
/// <c>true</c> if inlining may proceed; otherwise, <c>false</c>.
/// </returns>
protected virtual bool ShouldConsider(IMethod callee, IMethod caller)
{
// Don't inline recursive calls. We have the infrastructure to do
// so, but inlining recursive calls if often pointless.
callee = callee.GetRecursiveGenericDeclaration();
if (callee == caller)
{
return false;
}
// By default, we don't want to inline methods across assemblies
// because doing so anyway introduces dependencies on implementation
// details in external dependencies that may be notice to change.
var calleeAsm = callee.GetDefiningAssemblyOrNull();
if (calleeAsm == null)
{
return true;
}
var callerAsm = caller.GetDefiningAssemblyOrNull();
if (callerAsm == null)
{
return true;
}
else
{
return calleeAsm == callerAsm;
}
}
/// <summary>
/// Determines if a method body can be inlined, that is, if invalid
/// code will be generated by inlining it.
/// </summary>
/// <param name="calleeBody">
/// A method body that is an inlining candidate.
/// </param>
/// <param name="caller">
/// The caller that wants to inline <paramref name="calleeBody"/>.
/// </param>
/// <param name="callerBody">
/// The method body for <paramref name="caller"/>.
/// </param>
/// <returns>
/// <c>true</c> if inlining <paramref name="calleeBody"/> into <paramref name="caller"/> is
/// safe; otherwise, <c>false</c>.
/// </returns>
protected virtual bool CanInline(MethodBody calleeBody, IMethod caller, FlowGraph callerBody)
{
// To determine if we can inline a method, we essentially just need to
// consider all members that show up in the method body and see if the
// caller is allowed to access them.
var rules = callerBody.GetAnalysisResult<AccessRules>();
var members = calleeBody.Implementation
.NamedInstructions.Select(insn => insn.Instruction)
.Concat(calleeBody.Implementation.BasicBlocks.SelectMany(block => block.Flow.Instructions))
.SelectMany(insn => insn.Prototype.Members);
foreach (var item in members)
{
if (item is IType && !rules.CanAccess(caller, (IType)item))
{
return false;
}
else if (item is ITypeMember && !rules.CanAccess(caller, (ITypeMember)item))
{
return false;
}
}
return true;
}
/// <summary>
/// Determines if a method body is worth inlining.
/// </summary>
/// <param name="body">
/// The method body to inline.
/// </param>
/// <param name="arguments">
/// The list of arguments to feed to <paramref name="body"/>.
/// </param>
/// <param name="caller">
/// The control-flow graph of the caller, which defines the arguments.
/// </param>
/// <returns>
/// <c>true</c> if the method body should be inlined; otherwise, <c>false,</c>.
/// </returns>
protected bool ShouldInline(
MethodBody body,
IReadOnlyList<ValueTag> arguments,
FlowGraph caller)
{
return GetInlineCost(body) <= GetInlineGain(body, arguments, caller);
}
/// <summary>
/// Gauges a particular method body's inline cost.
/// </summary>
/// <param name="body">A method body that might be inlined.</param>
/// <returns>A number that represents the method body's inline cost.</returns>
protected virtual int GetInlineCost(MethodBody body)
{
// The bigger a method body is, the less inclined we'll be to inline it.
return body.Implementation.NamedInstructions.Count()
+ body.Implementation.BasicBlocks.Count();
}
/// <summary>
/// Gauges a particular method body's inline gain.
/// </summary>
/// <param name="body">A method body that might be inlined.</param>
/// <param name="arguments">
/// The list of arguments to feed to <paramref name="body"/>.
/// </param>
/// <param name="caller">
/// The control-flow graph of the caller, which defines the arguments.
/// </param>
/// <returns>
/// A number that represents how much new information we expect to gain from inlining.
/// </returns>
protected virtual int GetInlineGain(
MethodBody body,
IReadOnlyList<ValueTag> arguments,
FlowGraph caller)
{
// Inline method bodies containing up to ten instructions/blocks.
// TODO: be smarter about arguments:
// * Inlining a method that takes a more derived type as argument
// may result in a direct call getting turned into an indirect
// call.
int gain = 10;
foreach (var arg in arguments)
{
NamedInstruction argInstruction;
if (caller.TryGetInstruction(arg, out argInstruction))
{
if (argInstruction.Prototype is AllocaPrototype)
{
// Inlining a method that takes an `alloca` argument may result
// in a level of memory indirection getting stripped away.
gain += 4;
continue;
}
}
var type = caller.GetValueType(arg);
// Inlining means that we don't have to pass around big arguments.
// Encourage inlining methods that take hefty arguments.
gain += EstimateTypeSize(type) / 4;
}
gain += EstimateTypeSize(body.ReturnParameter.Type) / 4;
return gain;
}
private static int EstimateTypeSize(IType type)
{
var intSpec = type.GetIntegerSpecOrNull();
if (intSpec != null)
{
return intSpec.Size / 8;
}
else if (type is PointerType || type.IsSpecialType())
{
return 8;
}
else
{
return type.GetAllInstanceFields()
.Select(field => field.FieldType)
.Select(EstimateTypeSize)
.Sum();
}
}
}
}