Skip to content
← Back

src/ir/wasmgc/wasmgc_dispatch.ghul

1
namespace IR.WasmGC is
2
use IR.Program
3
4
use Wasm.MODULE
5
use Wasm.SUB_TYPE
6
use Wasm.STRUCT_TYPE
7
use Wasm.FUNC_TYPE
8
use Wasm.FIELD_TYPE
9
use Wasm.VALUE_TYPE
10
use Wasm.HEAP_TYPE
11
use Wasm.TYPE_FIELD_INSTRUCTION
12
use Wasm.FUNCTION
13
use Wasm.TABLE
14
use Wasm.LIMITS
15
use Wasm.ELEMENT_SEGMENT
16
use Wasm.ElementMode
17
use Wasm.AbstractHeapType
18
use Wasm.INSTRUCTION
19
use Wasm.INDEX_INSTRUCTION
20
use Wasm.TYPE_INSTRUCTION
21
use Wasm.HEAP_TYPE_INSTRUCTION
22
use Wasm.NumericType
23
use Wasm.I32_CONSTANT
24
use Wasm.Opcode
25
26
use Collections.LIST
27
use Collections.MAP
28
use Collections.SET
29
30
use Semantic.Types.Type
31
use Semantic.Symbols.Symbol
32
use Semantic.Symbols.Classy
33
use Semantic.Symbols.Function
34
use Semantic.Symbols.GENERIC
35
use Semantic.Symbols.Scope
36
37
use IR.Emitter.SRM_MEMBER_ORDER
38
use IR.Emitter.SRM_EMITTED_TYPE
39
40
/// The WasmGC side of how the program's virtual and trait calls
41
/// dispatch: the function and vtable types the planned slots and
42
/// selectors need, the trait table, and the thunks every vtable and
43
/// table entry calls through.
44
///
45
/// Every entry is a thunk with the slot's or row's own signature, which
46
/// casts the receiver to the implementation's class and calls it.
47
class WASMGC_DISPATCH: DispatchTarget is
48
_registry: WASMGC_TYPE_REGISTRY
49
_plan: DISPATCH_PLAN
50
51
_vtable_types: MAP[CLASS_INSTANCE, int]
52
53
_types: LIST[SUB_TYPE]
54
_next_type: int
55
56
_thunk_indices: MAP[int, MAP[FUNCTION_INSTANCE, int]]
57
_box_hashes: MAP[CLASS_INSTANCE, int]
58
_box_equalities: MAP[CLASS_INSTANCE, int]
59
_generic_calls: LIST[(method: Function, arguments: Collections.List[Type])]
60
_found: LIST[CLASS_INSTANCE]
61
62
/// Reaches, while discovering, a function a dispatched generic call
63
/// can run without naming it.
64
reach: ((FUNCTION_INSTANCE) -> void)? public
65
66
init(registry: WASMGC_TYPE_REGISTRY) is
67
_registry = registry
68
_plan = DISPATCH_PLAN(self)
69
70
_vtable_types = MAP[CLASS_INSTANCE, int]()
71
72
_types = LIST[SUB_TYPE]()
73
74
_thunk_indices = MAP[int, MAP[FUNCTION_INSTANCE, int]]()
75
_box_hashes = MAP[CLASS_INSTANCE, int]()
76
_box_equalities = MAP[CLASS_INSTANCE, int]()
77
_generic_calls = LIST[(method: Function, arguments: Collections.List[Type])]()
78
_found = LIST[CLASS_INSTANCE]()
79
si
80
81
/// The trait table's size, once `plan` has packed it.
82
table_size: int => _plan.table_size
83
84
/// Plans the slots and selectors of the classes in `ordered`, which
85
/// lists parents before children, and answers the function and
86
/// vtable types they need, to be numbered from `first_index` on.
87
plan(ordered: Collections.List[CLASS_INSTANCE], first_index: int) -> Collections.List[SUB_TYPE] is
88
_next_type = first_index
89
90
_plan.plan_slots(ordered)
91
92
for type in ordered do
93
if _plan.has_slots(type) then
94
_add_vtable_type(type)
95
fi
96
od
97
98
_plan.plan_traits()
99
100
return _types
101
si
102
103
root: CLASS_INSTANCE? => _registry.root
104
numbering: CLASS_ID_NUMBERING[CLASS_INSTANCE] => _registry.numbering
105
class_of(type: Type?) -> CLASS_INSTANCE? => _registry.class_of(type)
106
superclass_of(type: CLASS_INSTANCE) -> CLASS_INSTANCE? => _registry.superclass_of(type)
107
methods_of(definition: Classy) -> Collections.List[Function] => _registry.methods_of(definition)
108
is_object(type: CLASS_INSTANCE) -> bool => _registry.is_object(type)
109
is_object_type(type: CLASS_INSTANCE) -> bool => _registry.is_object_type(type)
110
is_box(type: CLASS_INSTANCE) -> bool => _registry.is_box(type)
111
is_array(type: CLASS_INSTANCE) -> bool => _registry.is_array(type)
112
is_string(type: CLASS_INSTANCE) -> bool => _registry.is_string(type)
113
is_bigint(type: CLASS_INSTANCE) -> bool => _registry.is_bigint(type)
114
is_instantiated(type: CLASS_INSTANCE) -> bool => _registry.is_instantiated(type)
115
116
slot_signature(owner: CLASS_INSTANCE, method: FUNCTION_INSTANCE) -> int? =>
117
_signature(VALUE_TYPE.of_type_index(_registry.type_index(owner)!, true), method)
118
119
selector_signature(method: FUNCTION_INSTANCE) -> int? =>
120
_signature(_registry.object_reference, method)
121
122
_add_type(sub_type: SUB_TYPE) -> int is
123
_types.add(sub_type)
124
125
let index = _next_type
126
127
_next_type = _next_type + 1
128
129
return index
130
si
131
132
// A function type in the recursion group: the receiver, then the
133
// method's own arguments, then its result, at the method's
134
// instantiation. Null where one of them is a type the target cannot
135
// hold yet.
136
_signature(receiver: VALUE_TYPE, method: FUNCTION_INSTANCE) -> int? is
137
let parameters = LIST[VALUE_TYPE]()
138
139
parameters.add(receiver)
140
141
for argument in method.definition.arguments do
142
if let value_type = _registry.value_type(method.specialize(argument)) then
143
parameters.add(value_type)
144
else
145
return null
146
fi
147
od
148
149
let results = LIST[VALUE_TYPE]()
150
let return_type = method.specialize(method.definition.return_type)
151
152
if !WASMGC_TYPES.is_void(return_type) then
153
if let value_type = _registry.value_type(return_type) then
154
results.add(value_type)
155
else
156
return null
157
fi
158
fi
159
160
return _add_type(SUB_TYPE(FUNC_TYPE(parameters.to_array(), results.to_array()), true, []))
161
si
162
163
/// Asks the registry, while it is discovering, for the cells and
164
/// boxes the by-reference parameters of the slots and selectors
165
/// `type` takes a place in are held in, which `plan` needs before
166
/// any body that reaches them is compiled.
167
///
168
/// - type: an instantiated class, box, string or array type
169
discover_reference_parameters(type: CLASS_INSTANCE) is
170
_discover_reference_parameters(type, SET[CLASS_INSTANCE]())
171
si
172
173
_discover_reference_parameters(type: CLASS_INSTANCE, seen: SET[CLASS_INSTANCE]) is
174
if !seen.add(type) then
175
return
176
fi
177
178
for method in _registry.methods_of(type.definition) do
179
if DISPATCH_PLAN.is_dispatched(method) then
180
let function = FUNCTION_INSTANCE(method, type.type_map)
181
182
for argument in method.arguments do
183
if let reference: Semantic.Types.REFERENCE = function.specialize(argument) then
184
_registry.value_type(reference)
185
fi
186
od
187
fi
188
od
189
190
for ancestor in type.definition.ancestors do
191
let specialized = TYPE_MAPS.specialize(ancestor, type.type_map)!
192
193
if let ancestor_type = _plan.trait_of(specialized) ?? _registry.class_of(specialized) then
194
_discover_reference_parameters(ancestor_type, seen)
195
fi
196
od
197
si
198
199
_add_vtable_type(type: CLASS_INSTANCE) is
200
let fields = LIST[FIELD_TYPE]()
201
202
for slot in _plan.slots(type) do
203
fields.add(FIELD_TYPE.of_reference(VALUE_TYPE.of_type_index(slot.signature, true), false))
204
od
205
206
let super_types = LIST[int]()
207
208
if let parent = _plan.parent(type) then
209
let parent_vtable mut = 0
210
211
if _vtable_types.try_get_value(parent, parent_vtable ref) then
212
super_types.add(parent_vtable)
213
fi
214
fi
215
216
_vtable_types[type] =
217
_add_type(SUB_TYPE(STRUCT_TYPE(fields.to_array()), !_registry.numbering.has_children(type), super_types.to_array()))
218
si
219
220
/// The one instance of the trait a value of `type` is, at its
221
/// arguments.
222
trait_of(type: Type) -> CLASS_INSTANCE? => _plan.trait_of(type)
223
224
/// The one instance of the trait `definition` at the arguments
225
/// `type_map` gives its parameters.
226
trait_of(definition: Classy, type_map: Collections.Map[Symbol, Type]) -> CLASS_INSTANCE? =>
227
_plan.trait_of(definition, type_map)
228
229
/// The vtable slot a call to `method` reads, or null where nothing
230
/// overrides it.
231
slot_of(method: FUNCTION_INSTANCE) -> DISPATCH_SLOT? => _plan.slot_of(method)
232
233
/// The vtable type of `type`, whose fields are its slots.
234
vtable_type(type: CLASS_INSTANCE) -> int? is
235
let result mut = 0
236
237
if _vtable_types.try_get_value(type, result ref) then
238
return result
239
fi
240
241
return null
242
si
243
244
/// The selector a call to the trait method `method` dispatches on,
245
/// where `method` is called on an instance of `trait_type`, or null
246
/// where it has none.
247
selector_of(method: Function, trait_type: CLASS_INSTANCE) -> TRAIT_SELECTOR? =>
248
_plan.selector_of(method, trait_type)
249
250
/// Records, while discovering, a call to the generic trait method
251
/// `method` through `trait_type` at `arguments`, its own type
252
/// arguments, so the instantiation has a row of its own.
253
///
254
/// - method: the trait method called
255
/// - trait_type: the trait instance the call goes through
256
/// - arguments: the method's own type arguments at the call
257
note_generic_call(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) is
258
if !_plan.note_generic_call(method, trait_type, arguments)? then
259
return
260
fi
261
262
_generic_calls.add((method, arguments))
263
264
for type in LIST[CLASS_INSTANCE](_found) do
265
_reach_generic(type, method, arguments)
266
od
267
si
268
269
/// Records, while discovering, that a value of `type` can exist, and
270
/// reaches its implementation of every generic trait method a call
271
/// was recorded at.
272
///
273
/// - type: the class found instantiated
274
note_generic_implementor(type: CLASS_INSTANCE) is
275
_found.add(type)
276
277
for call in LIST[(method: Function, arguments: Collections.List[Type])](_generic_calls) do
278
_reach_generic(type, call.method, call.arguments)
279
od
280
si
281
282
_reach_generic(type: CLASS_INSTANCE, method: Function, arguments: Collections.List[Type]) is
283
if let implementation = _plan.generic_implementation(type, method, arguments), r = reach then
284
r(implementation)
285
fi
286
si
287
288
/// The selector a call to the generic trait method `method` at
289
/// `arguments` dispatches on, where it is called on an instance of
290
/// `trait_type`, or null where it has none.
291
generic_selector_of(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) -> TRAIT_SELECTOR? =>
292
_plan.generic_selector_of(method, trait_type, arguments)
293
294
/// The one method any call to `selector` can run, or null where the
295
/// row has more than one, or none.
296
only_implementation(selector: TRAIT_SELECTOR) -> FUNCTION_INSTANCE? =>
297
_plan.only_implementation(selector)
298
299
/// The classes implementing `trait_type`, or null where the program
300
/// has none.
301
implementors(trait_type: CLASS_INSTANCE) -> Collections.List[CLASS_INSTANCE]? =>
302
_plan.implementors(trait_type)
303
304
/// Marks every implementation that can fill `slot` as reached, so
305
/// the walk compiles it.
306
use_slot(slot: DISPATCH_SLOT, numbering: WASMGC_FUNCTION_NUMBERING) =>
307
_plan.use_slot(slot, implementation => numbering.index_of(implementation))
308
309
/// Marks every implementation in `selector`'s row as reached, so the
310
/// walk compiles it.
311
use_selector(selector: TRAIT_SELECTOR, numbering: WASMGC_FUNCTION_NUMBERING) =>
312
_plan.use_selector(selector, implementation => numbering.index_of(implementation))
313
314
/// Adds the trait table to `module`, once the walk has reached
315
/// everything. Entries whose implementation the walk did not reach
316
/// stay empty: nothing calls through their selector.
317
finish(module: MODULE, numbering: WASMGC_FUNCTION_NUMBERING) is
318
let entries = LIST[Collections.List[INSTRUCTION]]()
319
320
for i in 0.._plan.table_size do
321
entries.add([HEAP_TYPE_INSTRUCTION(Opcode.REF_NULL, HEAP_TYPE.of_abstract(AbstractHeapType.FUNC))]: INSTRUCTION)
322
od
323
324
for (selector_method, row) in _plan.rows do
325
let selector = _plan.selector(selector_method)
326
327
for (column, implementation) in row do
328
if numbering.indexed(implementation)? then
329
let thunk = _thunk(selector.signature, implementation, numbering)
330
331
entries[selector.offset + column] = [INDEX_INSTRUCTION(Opcode.REF_FUNC, thunk)]: INSTRUCTION
332
fi
333
od
334
od
335
336
if _plan.table_size > 0 then
337
let funcref = VALUE_TYPE.of_abstract(AbstractHeapType.FUNC)
338
339
let table = module.add_table(TABLE(funcref, LIMITS(_plan.table_size, _plan.table_size)))
340
341
module.add_element_segment(
342
ELEMENT_SEGMENT.of_expressions(ElementMode.ACTIVE, table, [I32_CONSTANT(0)]: INSTRUCTION, funcref, entries))
343
fi
344
si
345
346
/// The constant expression building the vtable of `type`, or null
347
/// where it has none. An entry the walk did not reach is null.
348
vtable(type: CLASS_INSTANCE, numbering: WASMGC_FUNCTION_NUMBERING) -> Collections.List[INSTRUCTION]? is
349
let vtable_type = vtable_type(type)
350
351
if !vtable_type? then
352
return null
353
fi
354
355
let result = LIST[INSTRUCTION]()
356
let slots = _plan.slots(type)
357
let entries = _plan.slot_entries(type)
358
359
for i in 0..slots.count do
360
if let implementation = entries[i] /\ _is_box_hash(type, implementation) then
361
result.add(INDEX_INSTRUCTION(Opcode.REF_FUNC, _box_hash(slots[i].signature, type, numbering)))
362
elif let implementation = entries[i] /\ _is_box_equals(type, implementation) then
363
result.add(INDEX_INSTRUCTION(Opcode.REF_FUNC, _box_equals(slots[i].signature, type, numbering)))
364
elif let implementation = entries[i] /\ numbering.indexed(implementation)? then
365
result.add(INDEX_INSTRUCTION(Opcode.REF_FUNC, _thunk(slots[i].signature, implementation, numbering)))
366
else
367
result.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_NULL, HEAP_TYPE.of_type_index(slots[i].signature)))
368
fi
369
od
370
371
result.add(TYPE_INSTRUCTION(Opcode.STRUCT_NEW, vtable_type))
372
373
return result
374
si
375
376
// The thunk with `signature` that calls `implementation`, reserved
377
// the first time it is asked for. It takes the signature's
378
// parameters, casts the receiver to the class the implementation
379
// belongs to, and calls it.
380
_thunk(signature: int, implementation: FUNCTION_INSTANCE, numbering: WASMGC_FUNCTION_NUMBERING) -> int is
381
if !_thunk_indices.contains_key(signature) then
382
_thunk_indices[signature] = MAP[FUNCTION_INSTANCE, int]()
383
fi
384
385
let by_implementation = _thunk_indices[signature]
386
387
let index mut = 0
388
389
if by_implementation.try_get_value(implementation, index ref) then
390
return index
391
fi
392
393
let registry = _registry
394
395
index = numbering.reserve(() is
396
let body = LIST[INSTRUCTION]()
397
398
body.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, 0))
399
400
if let receiver = registry.receiver_type(implementation) then
401
if let heap_type = receiver.heap_type() /\ !heap_type.matches(registry.object_reference.heap_type()!) then
402
body.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST_NULL, heap_type))
403
elif receiver.numeric()? then
404
// A scalar's method takes the value, so the box is
405
// opened first.
406
if let owner: Classy = implementation.definition.owner then
407
if let box = registry.box_index(Semantic.Types.NAMED(owner)) then
408
body.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST, HEAP_TYPE.of_type_index(box)))
409
body.add(TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, box, WASMGC_TYPE_REGISTRY.BOX_VALUE))
410
fi
411
fi
412
fi
413
fi
414
415
for i in 0..implementation.definition.arguments.count do
416
body.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, i + 1))
417
od
418
419
body.add(INDEX_INSTRUCTION(Opcode.CALL, numbering.indexed(implementation)!))
420
421
return FUNCTION(signature, [], body)
422
si)
423
424
by_implementation[implementation] = index
425
426
return index
427
si
428
429
// Whether `implementation` is the root's `get_hash_code` filling a
430
// slot in the vtable of the box `type`, which hashes the scalar it
431
// holds instead.
432
_is_box_hash(type: CLASS_INSTANCE, implementation: FUNCTION_INSTANCE) -> bool =>
433
_registry.is_box(type) /\
434
implementation.definition.name =~ "get_hash_code" /\
435
implementation.definition.arguments.count == 0 /\
436
(cast Classy?(implementation.definition.owner)?.is_object ?? false)
437
438
// A box's `get_hash_code`: the hash of the scalar it holds.
439
_box_hash(signature: int, type: CLASS_INSTANCE, numbering: WASMGC_FUNCTION_NUMBERING) -> int is
440
let index mut = 0
441
442
if _box_hashes.try_get_value(type, index ref) then
443
return index
444
fi
445
446
let registry = _registry
447
448
index = numbering.reserve(() is
449
let box_index = registry.type_index(type)!
450
let numeric = WASMGC_TYPES.numeric_of(registry.boxed_type(type))!
451
452
let body = LIST[INSTRUCTION]()
453
454
body.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, 0))
455
body.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST, HEAP_TYPE.of_type_index(box_index)))
456
body.add(TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, box_index, 1))
457
458
if let scalar = WASMGC_TYPES.scalar(registry.boxed_type(type)) /\ WASMGC_TYPES.is_narrow(scalar) then
459
body.add_range(WASMGC_OPERATIONS.normalise(scalar))
460
fi
461
462
body.add_range(WASMGC_OPERATIONS.hash(numeric, 1, 2))
463
464
return FUNCTION(signature, [VALUE_TYPE.of_numeric(NumericType.I64), VALUE_TYPE.of_numeric(numeric)], body)
465
si)
466
467
_box_hashes[type] = index
468
469
return index
470
si
471
472
// Whether `implementation` is the root's `equals` filling a slot in
473
// the vtable of the box `type`, which compares the scalar it holds
474
// instead, as the scalar's own Equals does on .NET.
475
_is_box_equals(type: CLASS_INSTANCE, implementation: FUNCTION_INSTANCE) -> bool =>
476
_registry.is_box(type) /\
477
WASMGC_TYPES.numeric_of(_registry.boxed_type(type))? /\
478
implementation.definition.name =~ "equals" /\
479
implementation.definition.arguments.count == 1 /\
480
(cast Classy?(implementation.definition.owner)?.is_object ?? false)
481
482
// A box's `equals`: true where the other object is a box of the same
483
// type, with the same descriptor, holding a value `=~` calls equal.
484
_box_equals(signature: int, type: CLASS_INSTANCE, numbering: WASMGC_FUNCTION_NUMBERING) -> int is
485
let index mut = 0
486
487
if _box_equalities.try_get_value(type, index ref) then
488
return index
489
fi
490
491
let registry = _registry
492
493
index = numbering.reserve(() is
494
let box_index = registry.type_index(type)!
495
let numeric = WASMGC_TYPES.numeric_of(registry.boxed_type(type))!
496
let box_heap = HEAP_TYPE.of_type_index(box_index)
497
498
let same = LIST[INSTRUCTION]()
499
500
same.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, 0))
501
same.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST, box_heap))
502
same.add(TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, box_index, 0))
503
same.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, 1))
504
same.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST, box_heap))
505
same.add(TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, box_index, 0))
506
same.add(Wasm.SIMPLE_INSTRUCTION(Opcode.REF_EQ))
507
508
for receiver in [0, 1] do
509
same.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, receiver))
510
same.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_CAST, box_heap))
511
same.add(TYPE_FIELD_INSTRUCTION(Opcode.STRUCT_GET, box_index, 1))
512
same.add_range(WASMGC_OPERATIONS.canonical_bits(numeric, 2))
513
od
514
515
same.add(Wasm.SIMPLE_INSTRUCTION(WASMGC_OPERATIONS.bits_equal(numeric)))
516
same.add(Wasm.SIMPLE_INSTRUCTION(Opcode.I32_AND))
517
518
let body = LIST[INSTRUCTION]()
519
520
body.add(INDEX_INSTRUCTION(Opcode.LOCAL_GET, 1))
521
body.add(HEAP_TYPE_INSTRUCTION(Opcode.REF_TEST, box_heap))
522
body.add(
523
Wasm.IF_INSTRUCTION(
524
Wasm.BLOCK_TYPE.of_value(VALUE_TYPE.of_numeric(NumericType.I32)),
525
same,
526
[I32_CONSTANT(0)]: INSTRUCTION))
527
528
return FUNCTION(signature, [VALUE_TYPE.of_numeric(numeric)], body)
529
si)
530
531
_box_equalities[type] = index
532
533
return index
534
si
535
si
536
si