Skip to content
← Back

src/ir/llvm/llvm_objects.ghul

1
namespace IR.LLVMTarget is
2
use IR.Program
3
4
use Collections.LIST
5
use Collections.MAP
6
7
use Semantic.Scope
8
use Semantic.Types.Type
9
use Semantic.Symbols.Symbol
10
use Semantic.Symbols.Classy
11
use Semantic.Symbols.Function
12
13
use IR.Emitter.SRM_MEMBER_ORDER
14
use IR.Emitter.SRM_EMITTED_TYPE
15
16
use LLVM.GLOBAL_VARIABLE
17
use LLVM.Linkage
18
use LLVM.MODULE
19
use LLVM.Types
20
use LLVM.Values
21
22
/// The program's classes on the LLVM target: one object layout and one
23
/// constant descriptor for each class instantiation the program uses,
24
/// the vtables and the trait table calls dispatch through, and the
25
/// globals holding static fields and namespace-level variables.
26
///
27
/// An object is `{ ptr descriptor, superclass fields..., own fields... }`,
28
/// each field held as the lowering holds a value of its type, so a field
29
/// is at the same offset in every instance that has it.
30
///
31
/// A descriptor is `{ i32 class number, i32 last descendant's number,
32
/// ptr superclass descriptor, ptr name, ptr display function, ptr type
33
/// object, i64 instance size, [N x ptr] vtable }`. The name is a string
34
/// literal. The display function is null for a type with no displayer,
35
/// and the type object is null until the program first asks for it, when
36
/// it is made and cached there, so descriptors are writable.
37
///
38
/// The trait table is one constant `[N x ptr]`, indexed by a row's offset
39
/// plus the receiver's class number.
40
///
41
/// Classes are found while the program's reach is discovered, then
42
/// numbered and laid out by `build`, and the descriptors and the trait
43
/// table are written by `finish` once every function is declared.
44
class LLVM_OBJECTS: DispatchTarget, DisplayTarget is
45
_module: MODULE
46
_classes: CLASS_SET
47
_dispatched: DISPATCHED_METHODS
48
_plan: DISPATCH_PLAN
49
50
_is_built: bool
51
52
_layouts: MAP[CLASS_INSTANCE, LIST[LLVM.Type]]
53
_sizes: MAP[CLASS_INSTANCE, int]
54
_field_positions: MAP[Symbol, int]
55
56
_statics: MAP[CLASS_INSTANCE, MAP[Symbol, (name: string, type: LLVM.Type)]]
57
_globals: MAP[Symbol, (name: string, type: LLVM.Type)]
58
_box_hashes: MAP[CLASS_INSTANCE, LLVM.FUNCTION]
59
_box_equalities: MAP[CLASS_INSTANCE, LLVM.FUNCTION]
60
_static_constructors: MAP[CLASS_INSTANCE, (constructor: FUNCTION_INSTANCE, flag: string)?]
61
_unit_variants: Collections.SET[CLASS_INSTANCE]
62
_global_names: MAP[(CLASS_INSTANCE, string), string]
63
_trait_instances: LIST[CLASS_INSTANCE]
64
_seen_trait_instances: Collections.SET[CLASS_INSTANCE]
65
_declared_methods: MAP[Classy, Collections.List[Function]]
66
_found_instantiated: Collections.SET[CLASS_INSTANCE]
67
_allocated: Collections.SET[CLASS_INSTANCE]
68
_generic_calls: LIST[(method: Function, arguments: Collections.List[Type])]
69
_added_methods: MAP[Classy, LIST[Function]]
70
71
_unsupported: LIST[(location: Source.LOCATION, construct: string)]
72
_string: CLASS_INSTANCE?
73
_boxes_made: Collections.SET[CLASS_INSTANCE]
74
_display_state: CLASS_INSTANCE?
75
_displayers: MAP[CLASS_INSTANCE, LLVM.FUNCTION]
76
77
/// The offset of the class number within a descriptor.
78
DESCRIPTOR_CLASS_ID: int static => 0
79
80
/// The offset of the number of the class's last descendant within a
81
/// descriptor.
82
DESCRIPTOR_LAST_DESCENDANT: int static => 4
83
84
/// The offset of the superclass's descriptor within a descriptor,
85
/// null for the root.
86
DESCRIPTOR_SUPERCLASS: int static => 8
87
88
/// The offset of the type's name, a string, within a descriptor.
89
DESCRIPTOR_NAME: int static => 16
90
91
/// The offset of the function that writes a value of the class for
92
/// display within a descriptor, null where it has none.
93
DESCRIPTOR_DISPLAY: int static => 24
94
95
/// The offset within a descriptor of the type object `get_type`
96
/// answers, a constant built beside the descriptor.
97
DESCRIPTOR_TYPE_OBJECT: int static => 32
98
99
/// The offset of an instance's size in bytes within a descriptor.
100
DESCRIPTOR_SIZE: int static => 40
101
102
/// The offset of the first vtable entry within a descriptor.
103
DESCRIPTOR_VTABLE: int static => 48
104
105
/// The offset of the value within a box.
106
BOX_VALUE_OFFSET: int static => 8
107
108
/// The name of the trait table.
109
TRAIT_TABLE_NAME: string static => "$trait_table"
110
111
/// The names the module's functions and globals are given.
112
names: LLVM_NAMES
113
114
/// - module: where the descriptors, the trait table and the globals are added
115
/// - names: the names the module's functions and globals are given
116
/// - classes: the program's classes, rooted at `object`
117
/// - string_type: the string type, or null where the program has none
118
init(module: MODULE, names: LLVM_NAMES, classes: CLASS_SET, string_type: Classy?) is
119
_module = module
120
self.names = names
121
_classes = classes
122
123
if let definition = string_type then
124
_string = classes.intern(CLASS_INSTANCE.of(definition))
125
fi
126
_dispatched = DISPATCHED_METHODS()
127
_plan = DISPATCH_PLAN(self)
128
129
_layouts = MAP[CLASS_INSTANCE, LIST[LLVM.Type]]()
130
_sizes = MAP[CLASS_INSTANCE, int]()
131
_field_positions = MAP[Symbol, int]()
132
133
_statics = MAP[CLASS_INSTANCE, MAP[Symbol, (name: string, type: LLVM.Type)]]()
134
_globals = MAP[Symbol, (name: string, type: LLVM.Type)]()
135
_box_hashes = MAP[CLASS_INSTANCE, LLVM.FUNCTION]()
136
_box_equalities = MAP[CLASS_INSTANCE, LLVM.FUNCTION]()
137
_static_constructors = MAP[CLASS_INSTANCE, (constructor: FUNCTION_INSTANCE, flag: string)?]()
138
_unit_variants = Collections.SET[CLASS_INSTANCE]()
139
_global_names = MAP[(CLASS_INSTANCE, string), string]()
140
_trait_instances = LIST[CLASS_INSTANCE]()
141
_seen_trait_instances = Collections.SET[CLASS_INSTANCE]()
142
_declared_methods = MAP[Classy, Collections.List[Function]]()
143
_found_instantiated = Collections.SET[CLASS_INSTANCE]()
144
exact = LLVM_EXACT_TYPES()
145
_allocated = Collections.SET[CLASS_INSTANCE]()
146
_generic_calls = LIST[(method: Function, arguments: Collections.List[Type])]()
147
_added_methods = MAP[Classy, LIST[Function]]()
148
149
_unsupported = LIST[(location: Source.LOCATION, construct: string)]()
150
_boxes_made = Collections.SET[CLASS_INSTANCE]()
151
_displayers = MAP[CLASS_INSTANCE, LLVM.FUNCTION]()
152
si
153
154
/// Where function values' thunks and descriptor are made, once the
155
/// program is being compiled rather than discovered.
156
closures: LLVM_CLOSURES? public
157
158
/// The methods calls dispatch on, found while discovering.
159
dispatched: DISPATCHED_METHODS => _dispatched
160
161
/// The program's classes.
162
classes: CLASS_SET => _classes
163
164
/// Whether `build` has numbered and laid out the classes. Until it
165
/// has, positions, slots and offsets are placeholders, since what is
166
/// lowered then is thrown away.
167
is_built: bool => _is_built
168
169
/// What the classes use that the target cannot compile yet, each
170
/// with where it is declared.
171
unsupported: Collections.List[(location: Source.LOCATION, construct: string)] => _unsupported
172
173
/// Takes every class declared under `root` that is not generic, and a
174
/// box for each scalar and each enum.
175
collect(root: Scope) => _classes.collect(root, CLASS_SET.innate_scalar_types())
176
177
/// The box a value of the scalar `type` is held in, or null where
178
/// `type` is not a scalar.
179
box_type(type: Type?) -> CLASS_INSTANCE? => _classes.box_type(type)
180
181
/// Records that the program boxes a value in `box`, so a value of it
182
/// can exist.
183
note_boxed(box: CLASS_INSTANCE) is
184
_boxes_made.add(box)
185
si
186
187
/// Records, while discovering, that the program allocates an object
188
/// of `type`, so a call through a vtable or a trait table can reach
189
/// its implementation.
190
note_allocated(type: CLASS_INSTANCE) is
191
if !_is_built then
192
_allocated.add(type)
193
fi
194
si
195
196
/// The class a value of `type` is an instance of, or null where the
197
/// program has none.
198
class_of(type: Type?) -> CLASS_INSTANCE? => if LLVM_TYPES.is_string(type) then _string else _classes.class_of(type) fi
199
200
/// The class `definition` at the arguments `type_map` gives its
201
/// parameters, or null where it is not a class the target represents.
202
class_of(definition: Classy, type_map: Collections.Map[Symbol, Type]) -> CLASS_INSTANCE? =>
203
_classes.class_of(definition, type_map)
204
205
/// The one instance of the trait a value of `type` is.
206
trait_of(type: Type) -> CLASS_INSTANCE? => _plan.trait_of(type)
207
208
/// The one instance of the trait `definition` at the arguments
209
/// `type_map` gives its parameters.
210
trait_of(definition: Classy, type_map: Collections.Map[Symbol, Type]) -> CLASS_INSTANCE? =>
211
_plan.trait_of(definition, type_map)
212
213
/// Numbers the classes, lays each out and plans its vtable, and plans
214
/// the trait table. Nothing is added to the classes afterwards.
215
build() is
216
_classes.number()
217
218
let ordered = LIST[CLASS_INSTANCE]()
219
220
for type in _classes.numbering.in_order() do
221
if !_classes.is_array(type) then
222
_lay_out(type)
223
fi
224
225
ordered.add(type)
226
od
227
228
_plan.plan_slots(ordered)
229
_plan.plan_traits()
230
231
_is_built = true
232
si
233
234
// An object's fields follow its superclass's, after the descriptor.
235
_lay_out(type: CLASS_INSTANCE) is
236
let layout = LIST[LLVM.Type]()
237
238
if _layouts.contains_key(type) then
239
return
240
fi
241
242
// A struct is held in place, its fields and nothing more.
243
if is_struct(type) then
244
// Marked laid out first, so a struct that holds itself is caught
245
// by the type checker rather than recursing here.
246
_layouts[type] = layout
247
elif let parent = _classes.superclass_of(type) ?? (if type != _classes.root then _classes.root else null fi) then
248
_lay_out(parent)
249
layout.add_range(_layouts[parent])
250
else
251
layout.add(Types.pointer)
252
fi
253
254
if is_string(type) then
255
layout.add(Types.i32)
256
layout.add(Types.i32)
257
elif is_bigint(type) then
258
layout.add(Types.i64)
259
layout.add(Types.pointer)
260
elif let boxed = _classes.boxed_type(type) then
261
layout.add(LLVM_TYPES.stored_type(boxed) ?? LLVM_TYPES.value_type(boxed) ?? Types.i32)
262
elif is_object_type(type) then
263
for `field in SRM_MEMBER_ORDER.fields(SRM_EMITTED_TYPE(type.definition)) do
264
if `field.is_instance then
265
_field_positions[`field] = layout.count
266
267
if let stored = stored_type(type.specialize(`field.type)) then
268
layout.add(stored)
269
else
270
_unsupported.add((`field.location, "a field of type {type.specialize(`field.type)}"))
271
layout.add(Types.pointer)
272
fi
273
fi
274
od
275
fi
276
277
_layouts[type] = layout
278
_sizes[type] = LLVM_TYPES.size_of(Types.structure(layout.to_array()))
279
si
280
281
/// The LLVM type a value of `type` is held in: a scalar's or a
282
/// reference's as LLVM_TYPES gives it, a struct as its fields, in
283
/// place, and an optional value type as whether it is present and
284
/// its value, `{ i1, T }`. Null where the target holds no values of the type.
285
held_type(type: Type?) -> LLVM.Type? is
286
if isa Semantic.Types.REFERENCE(type) then
287
return Types.pointer
288
elif let t = type /\ t.is_optional /\ t.is_value_type /\ !t.is_maybe then
289
if let inner = stored_type(t.optional_inner_type) then
290
return Types.structure([Types.i8, inner])
291
fi
292
293
return null
294
elif let held = LLVM_TYPES.value_type(type) then
295
return held
296
elif bigint_of(type)? then
297
return Types.pointer
298
elif let s = struct_of(type) then
299
_lay_out(s)
300
301
return Types.structure(_layouts[s].to_array())
302
fi
303
304
return null
305
si
306
307
/// The LLVM type a value of `type` is stored as in memory: a scalar at
308
/// the width of its kind, anything else as it is held. Null where the
309
/// target holds no values of the type.
310
stored_type(type: Type?) -> LLVM.Type? => LLVM_TYPES.stored_type(type) ?? held_type(type)
311
312
/// A value of `type` loaded in `block` from `pointer`, where it is held
313
/// as stored, widened to the width it is computed with; null where the
314
/// target holds no values of the type.
315
load_stored(block: LLVM.BLOCK, type: Type?, pointer: LLVM.Value) -> LLVM.Value? is
316
let stored = stored_type(type)
317
318
if !stored? then
319
return null
320
fi
321
322
let value = block.load(stored, pointer, 0)
323
324
return if let scalar = LLVM_TYPES.scalar(type) then LLVM_TYPES.widen(block, value, scalar) else value fi
325
si
326
327
/// The struct a value of `type` is, held in place, or null where it
328
/// is not one: a scalar, an enum or an optional struct is not.
329
struct_of(type: Type?) -> CLASS_INSTANCE? is
330
if !type? \/ (type.is_optional /\ !type.is_maybe) \/ LLVM_TYPES.value_type(type)? then
331
return null
332
fi
333
334
if let s = _classes.class_of(type) /\ is_struct(s) then
335
return s
336
fi
337
338
return null
339
si
340
341
/// Whether `type` is a struct, which is held in place rather than
342
/// through a reference. A bigint is not: it is a reference to its
343
/// box, which is never changed once made.
344
is_struct(type: CLASS_INSTANCE) -> bool =>
345
isa Semantic.Symbols.STRUCT(type.definition) /\ !_classes.is_box(type) /\ _classes.is_object_type(type.definition) /\ !is_bigint(type)
346
347
/// The bigint class a value of `type` is, or null where it is not one.
348
bigint_of(type: Type?) -> CLASS_INSTANCE? is
349
if !type? \/ type.is_optional then
350
return null
351
fi
352
353
if let b = _classes.class_of(type) /\ is_bigint(b) then
354
return b
355
fi
356
357
return null
358
si
359
360
/// The position of a bigint box's i64 field, which holds its value
361
/// where that fits.
362
BIGINT_SMALL: int static => 1
363
364
/// The position of a bigint box's field holding the runtime's
365
/// integer, or null where its value is in the i64 field.
366
BIGINT_BIG: int static => 2
367
368
/// The LLVM struct type an instance of `type` is.
369
struct_type(type: CLASS_INSTANCE) -> LLVM.Type =>
370
if _is_built then Types.structure(_layouts[type].to_array()) else Types.structure([Types.pointer]) fi
371
372
/// The size in bytes of an instance of `type`.
373
size_of(type: CLASS_INSTANCE) -> int =>
374
if !_is_built then
375
8
376
elif _classes.is_array(type) then
377
LLVM_ARRAYS.ELEMENTS_OFFSET
378
else
379
_sizes[type]
380
fi
381
382
/// The instance fields of `type` the target holds, its superclasses'
383
/// first, each with its type at `type`'s arguments and its position
384
/// in `type`'s struct type. Empty until the classes are laid out.
385
fields_of(type: CLASS_INSTANCE) -> LIST[(`field: Symbol, type: Type, position: int)] is
386
let result = LIST[(`field: Symbol, type: Type, position: int)]()
387
388
if !_is_built \/ !is_object_type(type) then
389
return result
390
fi
391
392
if let parent = _classes.superclass_of(type) then
393
result.add_range(fields_of(parent))
394
fi
395
396
for `field in SRM_MEMBER_ORDER.fields(SRM_EMITTED_TYPE(type.definition)) do
397
let position: int mut
398
399
if `field.is_instance /\ _field_positions.try_get_value(`field, position ref) then
400
if let field_type = type.specialize(`field.type) then
401
result.add((`field, field_type, position))
402
fi
403
fi
404
od
405
406
return result
407
si
408
409
/// The position in its owner's struct type of the instance field
410
/// `field`, or null where the target does not hold it.
411
field_position(`field: Symbol) -> int? is
412
if !_is_built then
413
return 0
414
fi
415
416
let position mut = 0
417
418
if _field_positions.try_get_value(`field.root_specialized_from, position ref) then
419
return position
420
fi
421
422
return null
423
si
424
425
/// The name of the global holding `type`'s descriptor.
426
descriptor_name(type: CLASS_INSTANCE) -> string =>
427
if is_string(type) then
428
LLVM_STRINGS.DESCRIPTOR_NAME
429
elif _is_built then _named(type, "$descriptor") else "$descriptor" fi
430
431
/// The name of the global holding the one instance of the unit variant
432
/// `type`.
433
unit_variant_name(type: CLASS_INSTANCE) -> string is
434
_unit_variants.add(type)
435
436
return if _is_built then _named(type, "$instance") else "$instance" fi
437
si
438
439
// The name of the global holding `type`'s `part`, given the first
440
// time it is asked for.
441
_named(type: CLASS_INSTANCE, part: string) -> string is
442
let key = (type, part)
443
let found: string mut
444
445
if _global_names.try_get_value(key, found ref) then
446
return found
447
fi
448
449
let name = names.unique("{names.type_label(type)}.{part}")
450
451
_global_names[key] = name
452
453
return name
454
si
455
456
/// The number of `type` and of its last descendant, so a value is
457
/// an instance of `type` exactly when its class number is between
458
/// the two.
459
class_range(type: CLASS_INSTANCE) -> (first: int, last: int) =>
460
if _is_built then
461
(_classes.numbering.id(type), _classes.numbering.last_descendant(type))
462
else
463
(0, 0)
464
fi
465
466
/// The class number ranges a value of the array type `type` can be in:
467
/// `type` itself and, where its element is a reference type, every array
468
/// type whose element is a subtype of it, as an array of a class is an
469
/// array of its superclass.
470
array_ranges(type: CLASS_INSTANCE) -> LIST[(first: int, last: int)] is
471
let result = LIST[(first: int, last: int)]()
472
473
if !_is_built then
474
return result
475
fi
476
477
let target = _classes.array_element(type)
478
479
for (array, element) in _classes.arrays do
480
if array =~ type \/ (!target.is_value_type /\ !element.is_value_type /\ target.is_assignable_from(element)) then
481
result.add(class_range(array))
482
fi
483
od
484
485
return result
486
si
487
488
/// The global holding the static field `field` of `owner`, or the
489
/// namespace-level variable `field` where `owner` is null, or null
490
/// where its type is one the target holds no values of.
491
global_of(`field: Symbol, owner: CLASS_INSTANCE?, type: Type?) -> (name: string, type: LLVM.Type)? is
492
let held = stored_type(type)
493
494
if !held? then
495
return null
496
fi
497
498
let globals =
499
if let o = owner then
500
if !_statics.contains_key(o) then
501
_statics[o] = MAP[Symbol, (name: string, type: LLVM.Type)]()
502
fi
503
504
_statics[o]
505
else
506
_globals
507
fi
508
509
let root = `field.root_specialized_from
510
let found: (name: string, type: LLVM.Type) mut
511
512
if globals.try_get_value(root, found ref) then
513
return found
514
fi
515
516
let label = if let o = owner then "{names.type_label(o)}.{`field.name}" else `field.qualified_name fi
517
let result = (names.unique(label), held)
518
519
globals[root] = result
520
521
return result
522
si
523
524
/// The static constructor of `type` and the name of the global flag
525
/// recording that it has run, or null where `type` has none.
526
static_constructor(type: CLASS_INSTANCE) -> (constructor: FUNCTION_INSTANCE, flag: string)? is
527
let found: (constructor: FUNCTION_INSTANCE, flag: string)? mut
528
529
if _static_constructors.try_get_value(type, found ref) then
530
return found
531
fi
532
533
let result: (constructor: FUNCTION_INSTANCE, flag: string)? mut = null
534
535
for method in SRM_MEMBER_ORDER.methods(SRM_EMITTED_TYPE(type.definition)) do
536
if method.is_static_constructor then
537
result = (FUNCTION_INSTANCE(method, type.type_map), names.unique("{names.type_label(type)}.$initialised"))
538
fi
539
od
540
541
_static_constructors[type] = result
542
543
return result
544
si
545
546
/// Reaches, while discovering, a function the program compiles: one a
547
/// dispatched call can run without naming it.
548
reach: ((FUNCTION_INSTANCE) -> void)? public
549
550
/// Records, while discovering, that a call dispatches on `method`.
551
note_dispatched(method: Function) is
552
if _dispatched.is_dispatched_to(cast Function?(method.root_specialized_from)!) then
553
return
554
fi
555
556
_dispatched.note(method)
557
558
if !_is_built /\ reach? then
559
for trait_type in LIST[CLASS_INSTANCE](_trait_instances) do
560
_reach_dispatched_defaults(trait_type)
561
od
562
fi
563
si
564
565
/// Records, while discovering, that a value of `type` can exist.
566
note_instantiated(type: CLASS_INSTANCE) is
567
_found_instantiated.add(type)
568
569
if !_is_built /\ reach? then
570
_note_trait_instances(type.definition, type.type_map)
571
572
for call in LIST[(method: Function, arguments: Collections.List[Type])](_generic_calls) do
573
_reach_generic(type, call.method, call.arguments)
574
od
575
fi
576
si
577
578
/// Records, while discovering, a call to the generic trait method
579
/// `method` through `trait_type` at `arguments`, its own type
580
/// arguments, and reaches its implementation in every class that can
581
/// exist; a class found later is reached when it is.
582
///
583
/// - method: the trait method called
584
/// - trait_type: the trait instance the call goes through
585
/// - arguments: the method's own type arguments at the call
586
note_generic_call(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) is
587
if _is_built \/ !reach? \/ !_plan.note_generic_call(method, trait_type, arguments)? then
588
return
589
fi
590
591
_generic_calls.add((method, arguments))
592
593
for type in LIST[CLASS_INSTANCE](_found_instantiated) do
594
_reach_generic(type, method, arguments)
595
od
596
si
597
598
_reach_generic(type: CLASS_INSTANCE, method: Function, arguments: Collections.List[Type]) is
599
if let implementation = _plan.generic_implementation(type, method, arguments) then
600
reach!(implementation)
601
fi
602
si
603
604
/// The trait table row a call to the generic trait method `method`
605
/// at `arguments` on an instance of `trait_type` goes through, or
606
/// null where it has none.
607
generic_selector_of(method: Function, trait_type: CLASS_INSTANCE, arguments: Collections.List[Type]) -> TRAIT_SELECTOR? =>
608
_plan.generic_selector_of(method, trait_type, arguments)
609
610
// The default methods of the traits an instantiated class implements
611
// that a call dispatches on are reached through the trait table,
612
// which names them only once it is planned, so they are reached
613
// here. A generic trait's are reached at each instance of it a class
614
// implements. Each trait instance is collected once, so a newly
615
// dispatched method is checked against every one of them without
616
// walking the classes again.
617
_note_trait_instances(from: Classy, map: Collections.Map[Symbol, Type]) is
618
for ancestor in from.ancestors do
619
let specialized = TYPE_MAPS.specialize(ancestor, map)!
620
621
if ancestor.is_trait then
622
if let trait_type = _plan.trait_of(specialized) /\ _seen_trait_instances.add(trait_type) then
623
_trait_instances.add(trait_type)
624
_reach_dispatched_defaults(trait_type)
625
_note_trait_instances(trait_type.definition, trait_type.type_map)
626
fi
627
elif let superclass = _classes.class_of(specialized) then
628
_note_trait_instances(superclass.definition, superclass.type_map)
629
fi
630
od
631
si
632
633
_reach_dispatched_defaults(trait_type: CLASS_INSTANCE) is
634
for method in methods_of(trait_type.definition) do
635
if DISPATCH_PLAN.is_dispatched(method) /\ !method.is_abstract /\ _dispatched.is_dispatched_to(method) then
636
reach!(FUNCTION_INSTANCE(method, trait_type.type_map))
637
fi
638
od
639
si
640
641
/// The vtable slot a virtual call to `method` goes through, or null
642
/// where it has none.
643
slot_of(method: FUNCTION_INSTANCE) -> DISPATCH_SLOT? => _plan.slot_of(method)
644
645
/// The trait table row a call to the trait method `method` on an
646
/// instance of `trait_type` goes through, or null where it has none.
647
selector_of(method: Function, trait_type: CLASS_INSTANCE) -> TRAIT_SELECTOR? =>
648
_plan.selector_of(method, trait_type)
649
650
/// The one implementation a call to `selector` can run on a value
651
/// that can exist, or null where there is more than one.
652
only_implementation(selector: TRAIT_SELECTOR) -> FUNCTION_INSTANCE? =>
653
if _is_built then
654
_plan.only_implementation(selector, id => _can_exist_by_id(id)) ?? _plan.only_implementation(selector)
655
else
656
_plan.only_implementation(selector)
657
fi
658
659
/// The exact classes of what functions return and locals hold.
660
exact: LLVM_EXACT_TYPES
661
662
/// The method a call through `slot` runs on a value of exactly
663
/// `type`, or null where there is none.
664
exact_slot_implementation(slot: DISPATCH_SLOT, type: CLASS_INSTANCE) -> FUNCTION_INSTANCE? =>
665
_plan.slot_implementation(slot, type)
666
667
/// The method a call to `selector` runs on a value of exactly
668
/// `type`, or null where there is none.
669
exact_implementation(selector: TRAIT_SELECTOR, type: CLASS_INSTANCE) -> FUNCTION_INSTANCE? =>
670
_plan.implementation(selector, _classes.numbering.id(type))
671
672
/// Every method a call to `method` through a vtable can run, or null
673
/// where that is not known.
674
slot_targets(method: FUNCTION_INSTANCE) -> Collections.Iterable[FUNCTION_INSTANCE]? =>
675
if let slot = slot_of(method) then _plan.slot_implementations(slot, type => _is_allocated(type)) else null fi
676
677
/// Every method a call to `root` through `trait_type`'s table can
678
/// run, or null where that is not known.
679
trait_targets(root: Function, trait_type: CLASS_INSTANCE) -> Collections.Iterable[FUNCTION_INSTANCE]? =>
680
if let selector = selector_of(root, trait_type) then _plan.implementations(selector, id => _can_exist_by_id(id)) else null fi
681
682
/// The one implementation a call through `slot` can run on a value
683
/// that can exist, or null where there is more than one.
684
only_slot_implementation(slot: DISPATCH_SLOT) -> FUNCTION_INSTANCE? =>
685
if _is_built then _plan.only_slot_implementation(slot, type => _is_allocated(type)) else null fi
686
687
_by_number: MAP[int, CLASS_INSTANCE]?
688
689
_can_exist_by_id(id: int) -> bool is
690
let by_number mut = _by_number
691
692
if !by_number? then
693
let built = MAP[int, CLASS_INSTANCE]()
694
695
for type in _classes.numbering.in_order() do
696
built[_classes.numbering.id(type)] = type
697
od
698
699
_by_number = built
700
by_number = built
701
fi
702
703
let type: CLASS_INSTANCE mut
704
705
return by_number.try_get_value(id, type ref) /\ _is_allocated(type)
706
si
707
708
// Whether an object of `type` can exist at run time: something
709
// allocates one, it is an array or a unit variant's one instance, or
710
// the runtime makes it itself.
711
_is_allocated(type: CLASS_INSTANCE) -> bool =>
712
_can_exist(type) /\
713
(is_string(type) \/ _classes.is_array(type) \/ _allocated.contains(type) \/ _unit_variants.contains(type) \/ _classes.is_box(type) \/ _is_made_by_runtime(type))
714
715
// The runtime makes a type object for each class, and the exception
716
// a read through null raises.
717
_is_made_by_runtime(type: CLASS_INSTANCE) -> bool =>
718
_type_class_instance() =~ type \/
719
type.definition == IR.Program.CORE_LIBRARY.exception_class(Semantic.Lookups.RuntimeException.NULL_REFERENCE)
720
721
/// The classes implementing `trait_type`, or null where the program
722
/// has none.
723
implementors(trait_type: CLASS_INSTANCE) -> Collections.List[CLASS_INSTANCE]? => _plan.implementors(trait_type)
724
725
/// Whether the program allocates a value of exactly `type`.
726
is_allocated(type: CLASS_INSTANCE) -> bool => _is_allocated(type)
727
728
/// Whether no class the program has derives from `type`.
729
has_no_subclasses(type: CLASS_INSTANCE) -> bool =>
730
_classes.numbering.id(type) == _classes.numbering.last_descendant(type)
731
732
/// The position in `type`'s layout of the field holding the member
733
/// it declares as `name`, or null where it has no such field.
734
field_position_of(type: CLASS_INSTANCE, name: string) -> int? is
735
for (`field, _, position) in fields_of(type) do
736
if `field.name =~ name \/ `field.name =~ "${name}" then
737
return position
738
fi
739
od
740
741
return null
742
si
743
744
/// Adds every descriptor, the trait table and the globals to the
745
/// module, each function referred to by the LLVM function `callee`
746
/// answers for it, null where the program never compiles it.
747
finish(strings: LLVM_STRINGS, callee: (FUNCTION_INSTANCE) -> LLVM.FUNCTION?) is
748
for type in _classes.numbering.in_order() do
749
_add_descriptor(type, strings, callee)
750
od
751
752
_add_trait_table(callee)
753
754
for (_, globals) in _statics do
755
for (_, (name, type)) in globals do
756
_add_global(name, type)
757
od
758
od
759
760
for (_, (name, type)) in _globals do
761
_add_global(name, type)
762
od
763
764
for type in LIST[CLASS_INSTANCE](_unit_variants) do
765
let layout = _layouts[type]
766
let values = LIST[LLVM.Value]()
767
768
values.add(Values.global(descriptor_name(type)))
769
770
for i in 1..layout.count do
771
values.add(LLVM_TYPES.zero(layout[i]))
772
od
773
774
let struct_type = struct_type(type)
775
let global = GLOBAL_VARIABLE(unit_variant_name(type), struct_type, LLVM.Value.AGGREGATE(values.to_array(), struct_type), false)
776
777
global.linkage = Linkage.INTERNAL
778
global.alignment = 8
779
780
_module.add_global(global)
781
od
782
783
for (_, constructor) in _static_constructors do
784
if let (_, flag) = constructor then
785
_add_global(flag, Types.i32)
786
fi
787
od
788
si
789
790
/// The type object of the class whose descriptor is `descriptor_name`:
791
/// a constant instance of the core library's `Type`, built here with
792
/// `name` as its full name, so `get_type` is a load of a constant.
793
/// Null where the program holds no `Type`, which is then never asked
794
/// for.
795
///
796
/// - descriptor_name: the name of the descriptor the type object
797
/// stands beside
798
/// - name: the type's full name, a string literal
799
type_object(descriptor_name: string, name: LLVM.Value) -> LLVM.Value is
800
let type_class = _type_class_instance()
801
802
if !type_class? then
803
return Values.null_pointer
804
fi
805
806
let layout = struct_type(type_class)
807
808
let fields =
809
if let s: LLVM.Type.STRUCT = layout then
810
s.fields
811
else
812
return Values.null_pointer
813
fi
814
815
let values = LIST[LLVM.Value]()
816
817
for field_type in fields do
818
values.add(LLVM_TYPES.zero(field_type))
819
od
820
821
values[0] = Values.global(descriptor_name(type_class))
822
823
for (`field, _, position) in fields_of(type_class) do
824
if `field.name =~ "_full_name" then
825
values[position] = name
826
fi
827
od
828
829
let global_name =
830
if descriptor_name.ends_with(".$descriptor") then
831
"{descriptor_name.substring(0, descriptor_name.length - ".$descriptor".length)}.$type"
832
else
833
"{descriptor_name}.$type"
834
fi
835
836
names.reserve(global_name)
837
838
let global = GLOBAL_VARIABLE(global_name, layout, LLVM.Value.AGGREGATE(values.to_array(), layout), true)
839
840
global.linkage = Linkage.INTERNAL
841
global.alignment = 8
842
843
_module.add_global(global)
844
845
return Values.global(global_name)
846
si
847
848
// The core library's `Type`, where the program holds one.
849
_type_class_instance() -> CLASS_INSTANCE? is
850
if let definition = IR.Program.CORE_LIBRARY.type_class(), found = class_of(definition, Collections.MAP[Symbol, Type]()) /\ is_object_type(found) then
851
return found
852
fi
853
854
return null
855
si
856
857
_add_global(name: string, type: LLVM.Type) is
858
let global = GLOBAL_VARIABLE(name, type, LLVM_TYPES.zero(type), false)
859
860
global.linkage = Linkage.INTERNAL
861
862
_module.add_global(global)
863
si
864
865
_add_descriptor(type: CLASS_INSTANCE, strings: LLVM_STRINGS, callee: (FUNCTION_INSTANCE) -> LLVM.FUNCTION?) is
866
let entries = LIST[LLVM.Value]()
867
868
if _plan.has_slots(type) then
869
for entry in _plan.slot_entries(type) do
870
// An entry a call can reach must be compiled, or the call
871
// would go through a null pointer. An abstract method's
872
// entry stays null: only a subclass that implements it
873
// can be instantiated, and its own entry is the one used.
874
if let e = entry /\ _can_exist(type) /\ !e.definition.is_abstract /\ _dispatched.is_dispatched_to(e.definition) /\ !callee(e)? then
875
_unsupported.add((e.definition.location, "a method of {type} called through a vtable"))
876
fi
877
878
entries.add(_reference(entry, callee, type))
879
od
880
fi
881
882
let vtable_type = LLVM.Type.ARRAY(entries.count, Types.pointer)
883
884
let superclass =
885
if let parent = _plan.parent(type) then
886
Values.global(descriptor_name(parent))
887
else
888
Values.null_pointer
889
fi
890
891
let descriptor_type =
892
Types.structure([
893
Types.i32, Types.i32, Types.pointer, Types.pointer, Types.pointer, Types.pointer, Types.i64, vtable_type
894
])
895
896
let name = strings.literal(TYPE_NAMES.name_of(type, _classes, null, t => LLVM_TYPES.scalar(t), t => LLVM_TYPES.is_string(t)))
897
898
let initializer =
899
LLVM.Value.AGGREGATE(
900
[
901
Values.i32(_classes.numbering.id(type)),
902
Values.i32(_classes.numbering.last_descendant(type)),
903
superclass,
904
name,
905
_displayer_reference(type),
906
type_object(descriptor_name(type), name),
907
Values.i64(cast long(size_of(type))),
908
LLVM.Value.AGGREGATE(entries.to_array(), vtable_type)
909
],
910
descriptor_type)
911
912
let global = GLOBAL_VARIABLE(descriptor_name(type), descriptor_type, initializer, true)
913
914
global.linkage = Linkage.INTERNAL
915
global.alignment = 8
916
917
_module.add_global(global)
918
si
919
920
_add_trait_table(callee: (FUNCTION_INSTANCE) -> LLVM.FUNCTION?) is
921
let by_number = MAP[int, CLASS_INSTANCE]()
922
923
for type in _classes.numbering.in_order() do
924
by_number[_classes.numbering.id(type)] = type
925
od
926
927
// A call through a row of no implementors still names the table.
928
let size = if _plan.table_size > 0 then _plan.table_size else 1 fi
929
930
let entries = LIST[LLVM.Value]()
931
932
for i in 0..size do
933
entries.add(Values.null_pointer)
934
od
935
936
for (method, row) in _plan.rows do
937
let offset = _plan.selector(method).offset
938
939
for (class_id, implementation) in row do
940
// An entry a call can reach must be compiled, or the call would
941
// go through a null pointer. A call reaches it only where a
942
// value of its class can exist, as for a vtable entry: a call
943
// is recorded against the trait method rather than the
944
// instance of the trait it goes through, so the rows of
945
// every instance count as dispatched once any one is.
946
if _dispatched.is_dispatched_to(method.definition) /\ by_number.contains_key(class_id) /\ _can_exist(by_number[class_id]) /\ !callee(implementation)? then
947
_unsupported.add((implementation.definition.location, "a method called through a trait"))
948
fi
949
950
entries[offset + class_id] = _reference(implementation, callee, if by_number.contains_key(class_id) then by_number[class_id] else null fi)
951
od
952
od
953
954
let type = LLVM.Type.ARRAY(size, Types.pointer)
955
956
let global = GLOBAL_VARIABLE(TRAIT_TABLE_NAME, type, LLVM.Value.AGGREGATE(entries.to_array(), type), true)
957
958
global.linkage = Linkage.INTERNAL
959
960
_module.add_global(global)
961
si
962
963
/// The entries of the root's vtable, which every object without a
964
/// class of its own, a closure, answers virtual calls through.
965
root_vtable(callee: (FUNCTION_INSTANCE) -> LLVM.FUNCTION?) -> LIST[LLVM.Value] is
966
let entries = LIST[LLVM.Value]()
967
968
if let root = _classes.root /\ _plan.has_slots(root) then
969
for entry in _plan.slot_entries(root) do
970
entries.add(_reference(entry, callee, root))
971
od
972
fi
973
974
return entries
975
si
976
977
// The entry for `instance` in `owner`'s vtable or trait table row. A
978
// box, of a scalar or a struct, reaches a method of the value it
979
// boxes through a thunk that passes the method the value's address
980
// rather than the box.
981
_reference(instance: FUNCTION_INSTANCE?, callee: (FUNCTION_INSTANCE) -> LLVM.FUNCTION?, owner: CLASS_INSTANCE?) -> LLVM.Value is
982
if let i = instance, function = callee(i) then
983
if let o = owner /\ is_box(o) /\ _is_root_hash(i), hash = _box_hash(o) then
984
return hash.reference
985
fi
986
987
if let o = owner /\ is_box(o) /\ _is_root_equals(i), equals = _box_equals(o, function) then
988
return equals.reference
989
fi
990
991
if let o = owner /\ (is_box(o) \/ is_struct(o)) /\ isa Semantic.Symbols.STRUCT(i.definition.owner), c = closures then
992
return c.unboxing_thunk(function).reference
993
fi
994
995
if let o = owner /\ is_bigint(o) /\ isa Semantic.Symbols.STRUCT(i.definition.owner), c = closures then
996
return c.referencing_thunk(function).reference
997
fi
998
999
return function.reference
1000
fi
1001
1002
return Values.null_pointer
1003
si
1004
1005
// Whether `instance` is the root's `get_hash_code`, which a box of a
1006
// scalar answers with the hash of the scalar it holds instead.
1007
_is_root_hash(instance: FUNCTION_INSTANCE) -> bool =>
1008
instance.definition.name =~ "get_hash_code" /\
1009
instance.definition.arguments.count == 0 /\
1010
(cast Classy?(instance.definition.owner)?.is_object ?? false)
1011
1012
// The function the box `type` answers `get_hash_code` with: the hash
1013
// of the scalar it holds, or null where it holds no scalar.
1014
_box_hash(type: CLASS_INSTANCE) -> LLVM.FUNCTION? is
1015
let found: LLVM.FUNCTION mut
1016
1017
if _box_hashes.try_get_value(type, found ref) then
1018
return found
1019
fi
1020
1021
let boxed = _classes.boxed_type(type)
1022
1023
if !LLVM_TYPES.value_type(boxed)? then
1024
return null
1025
fi
1026
1027
let function = LLVM.FUNCTION(names.unique("{names.type_label(type)}.$hash"), Types.i32, [LLVM.PARAMETER(Types.pointer, "box")])
1028
1029
function.linkage = Linkage.INTERNAL
1030
1031
let block = function.add_block("entry")
1032
let address = block.element_pointer(Types.i8, function.parameter(0), [Values.i32(BOX_VALUE_OFFSET)], true)
1033
1034
block.return_value(LLVM_SCALAR_HASH.hash(block, load_stored(block, boxed, address)!))
1035
1036
_module.add_function(function)
1037
1038
_box_hashes[type] = function
1039
1040
return function
1041
si
1042
1043
// Whether `instance` is the root's `equals`, which a box of a scalar
1044
// answers by comparing the scalar it holds instead.
1045
_is_root_equals(instance: FUNCTION_INSTANCE) -> bool =>
1046
instance.definition.name =~ "equals" /\
1047
instance.definition.arguments.count == 1 /\
1048
(cast Classy?(instance.definition.owner)?.is_object ?? false)
1049
1050
// The function the box `type` answers `equals` with, of the same type
1051
// as `root_equals`, the root's: true where the other object is a box
1052
// with the same descriptor holding a value equal to this one's, a NaN
1053
// equal to another as .NET has it. Null where it holds no scalar.
1054
_box_equals(type: CLASS_INSTANCE, root_equals: LLVM.FUNCTION) -> LLVM.FUNCTION? is
1055
let found: LLVM.FUNCTION mut
1056
1057
if _box_equalities.try_get_value(type, found ref) then
1058
return found
1059
fi
1060
1061
let boxed = _classes.boxed_type(type)
1062
1063
if !LLVM_TYPES.value_type(boxed)? then
1064
return null
1065
fi
1066
1067
let function =
1068
LLVM.FUNCTION(
1069
names.unique("{names.type_label(type)}.$equals"),
1070
root_equals.result,
1071
[LLVM.PARAMETER(Types.pointer, "box"), LLVM.PARAMETER(Types.pointer, "other")])
1072
1073
function.linkage = Linkage.INTERNAL
1074
1075
let entry = function.add_block("entry")
1076
let same_type = function.add_block("same_type")
1077
let compare = function.add_block("compare")
1078
let different = function.add_block("different")
1079
1080
let box = function.parameter(0)
1081
let other = function.parameter(1)
1082
1083
entry.branch(entry.compare(LLVM.IntegerPredicate.EQ, other, Values.null_pointer), different, same_type)
1084
1085
let descriptor = same_type.load(Types.pointer, box, 8)
1086
let other_descriptor = same_type.load(Types.pointer, other, 8)
1087
1088
same_type.branch(same_type.compare(LLVM.IntegerPredicate.EQ, descriptor, other_descriptor), compare, different)
1089
1090
let left = load_stored(compare, boxed, compare.element_pointer(Types.i8, box, [Values.i32(BOX_VALUE_OFFSET)], true))!
1091
let right = load_stored(compare, boxed, compare.element_pointer(Types.i8, other, [Values.i32(BOX_VALUE_OFFSET)], true))!
1092
1093
let equal =
1094
if LLVM_TYPES.is_floating(left.type) then
1095
compare.binary(
1096
LLVM.BinaryOperator.OR,
1097
LLVM.IntegerFlags.NONE,
1098
compare.compare(LLVM.FloatPredicate.OEQ, left, right),
1099
compare.binary(
1100
LLVM.BinaryOperator.AND,
1101
LLVM.IntegerFlags.NONE,
1102
compare.compare(LLVM.FloatPredicate.UNO, left, left),
1103
compare.compare(LLVM.FloatPredicate.UNO, right, right)))
1104
else
1105
compare.compare(LLVM.IntegerPredicate.EQ, left, right)
1106
fi
1107
1108
compare.return_value(_as_result(compare, equal, root_equals.result))
1109
different.return_value(_as_result(different, Values.boolean(false), root_equals.result))
1110
1111
_module.add_function(function)
1112
1113
_box_equalities[type] = function
1114
1115
return function
1116
si
1117
1118
// `value`, an `i1`, as a function returning `result` returns a bool.
1119
_as_result(block: LLVM.BLOCK, value: LLVM.Value, result: LLVM.Type) -> LLVM.Value =>
1120
if result =~ Types.i1 then value else block.convert(LLVM.Conversion.ZERO_EXTEND, value, result) fi
1121
1122
root: CLASS_INSTANCE? => _classes.root
1123
numbering: CLASS_ID_NUMBERING[CLASS_INSTANCE] => _classes.numbering
1124
superclass_of(type: CLASS_INSTANCE) -> CLASS_INSTANCE? => _classes.superclass_of(type)
1125
/// Gives `owner` a method that no symbol of it declares, which dispatch
1126
/// reaches as it reaches the methods `owner` declares.
1127
add_method(owner: Classy, method: Function) is
1128
if !_added_methods.contains_key(owner) then
1129
_added_methods[owner] = LIST[Function]()
1130
fi
1131
1132
_added_methods[owner].add(method)
1133
si
1134
1135
/// The methods `definition` has: those it declares, then any it was
1136
/// given.
1137
methods_of(definition: Classy) -> Collections.List[Function] is
1138
let declared: Collections.List[Function] mut
1139
1140
if !_declared_methods.try_get_value(definition, declared ref) then
1141
declared = SRM_MEMBER_ORDER.methods(SRM_EMITTED_TYPE(definition))
1142
_declared_methods[definition] = declared
1143
fi
1144
1145
let added: LIST[Function] mut
1146
1147
if !_added_methods.try_get_value(definition, added ref) then
1148
return declared
1149
fi
1150
1151
let result = LIST[Function](declared)
1152
1153
result.add_range(added)
1154
1155
return result
1156
si
1157
is_object(type: CLASS_INSTANCE) -> bool => type == _classes.root
1158
is_object_type(type: CLASS_INSTANCE) -> bool => !_classes.is_box(type) /\ _classes.is_object_type(type.definition)
1159
is_box(type: CLASS_INSTANCE) -> bool => _classes.is_box(type)
1160
is_array(type: CLASS_INSTANCE) -> bool => _classes.is_array(type)
1161
1162
/// Whether `type` is the string type.
1163
is_string(type: CLASS_INSTANCE) -> bool => _string? /\ type == _string
1164
1165
/// Whether the program has a string type, whose descriptor this adds.
1166
has_string_type: bool => _string?
1167
1168
is_bigint(type: CLASS_INSTANCE) -> bool => type.definition == _classes.core.bigint
1169
1170
/// The element type of the array type `type`.
1171
array_element(type: CLASS_INSTANCE) -> Type => _classes.array_element(type)
1172
1173
/// The core library's display state class, where the program renders
1174
/// values for display.
1175
display_state: CLASS_INSTANCE? => _display_state
1176
1177
/// Records that the program renders values for display, through
1178
/// the core library's state class `state`.
1179
note_display(state: CLASS_INSTANCE) is
1180
_display_state = state
1181
si
1182
1183
/// Records `displayer` as the function that writes a value of
1184
/// `type` for display, which its descriptor holds.
1185
set_displayer(type: CLASS_INSTANCE, displayer: LLVM.FUNCTION) is
1186
_displayers[type] = displayer
1187
si
1188
1189
_displayer_reference(type: CLASS_INSTANCE) -> LLVM.Value is
1190
let displayer: LLVM.FUNCTION mut
1191
1192
if _displayers.try_get_value(type, displayer ref) then
1193
return displayer.reference
1194
fi
1195
1196
return Values.null_pointer
1197
si
1198
1199
/// Whether a value of `type` can exist: a box only where something
1200
/// boxes a value in it.
1201
is_instantiated(type: CLASS_INSTANCE) -> bool => !_classes.is_box(type) \/ _boxes_made.contains(type)
1202
1203
// Whether a value of `type` can exist in the program: discovery found it
1204
// instantiated. A vtable or trait table entry a call can reach must be
1205
// compiled exactly where this holds, so both tables ask it.
1206
_can_exist(type: CLASS_INSTANCE) -> bool => _found_instantiated.contains(type) /\ is_instantiated(type)
1207
1208
// Every receiver is a `ptr`, so a slot or a row needs no signature
1209
// of its own: the call site gives the function type.
1210
slot_signature(owner: CLASS_INSTANCE, method: FUNCTION_INSTANCE) -> int? => 0
1211
selector_signature(method: FUNCTION_INSTANCE) -> int? => 0
1212
si
1213
si